[analyzer] Improve `CallDescription` to handle c++ method.

[MTC]

Summary

CallDecription can only handle function for the time being. If we want to match c++ method, we can only use method name to match and can't improve the matching accuracy through the qualifiers.

This patch add the support for QualifiedName matching to improve the matching accuracy.

[MTC]

The implementation is not complicated, the difficulty is that there is no good way to get the qualified name without template arguments. For std::basic_string::c_str(), its qualified name may be std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::c_str, it is almost impossible for users to provide such a name. So one possible implementation is to use std, basic_string and c_str to match in the std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::c_str sequentially.

[MTC]

Remove useless header files for testing.

[xazax.hun]

Having C++ support would be awesome!
Thanks for working on this!

While I do agree matching is not trivial with qualified names, this problem is already solved with AST matchers.

I wonder if using matchers or reusing the HasNameMatcher class would make this easier. That code path is already well tested and optimized.

[MTC]

In D48027#1128301, @xazax.hun wrote:

Having C++ support would be awesome!
Thanks for working on this!

While I do agree matching is not trivial with qualified names, this problem is already solved with AST matchers.

I wonder if using matchers or reusing the HasNameMatcher class would make this easier. That code path is already well tested and optimized.

Thank you for pointing out the direction, xazax.hun!

I will looking into the matchers and try to give a better solution.

[MTC]

• Use hasName matcher to match the qualified name.
• Use the full name, like std::basic_string<char>::c_str instead of c_str to match the c_str method in DanglingInternalBufferChecker.cpp.

[xazax.hun]

lib/StaticAnalyzer/Checkers/DanglingInternalBufferChecker.cpp

32 ↗

(On Diff #151166)

I am not sure if this is the right solution in case of this check. We should track c_str calls regardless of what the template parameter is, so supporting any instantiation of basic_string is desired. This might not be the case, however, for other checks.

If we think it is more likely we do not care about the template arguments, maybe a separate API could be used, where we pass the qualified name of the class separately without the template arguments.
Alternatively, we could use matches name so the users could use regexps.

At this point I also wonder what isCalled API gives us compared to matchers? Maybe it is more convenient to use than calling a match. Also, isCalled API has an IdentifierInfo cached which could be used for relatively efficient checks.

@NoQ what do you think?

65 ↗

(On Diff #151166)

If we check for fully qualified names, this check might be redundant.

lib/StaticAnalyzer/Core/CallEvent.cpp

374

Doesn't match also traverse the subtree of the AST? We only need to check if that particular node matches the qualified name. I wonder if we could, during the traversal, find another node that is a match unintentionally.

[NoQ]

lib/StaticAnalyzer/Checkers/DanglingInternalBufferChecker.cpp

32 ↗

(On Diff #151166)

I agree that it's better to match the chain of classes and namespaces (in as much detail as the user cares to provide) and discard template parameters.

For example, i wish that a CallDescription that's defined as {"std", "basic_string", "c_str"} would be able to match both std::string::c_str() and std::__1::string::c_str().

[MTC]

lib/StaticAnalyzer/Checkers/DanglingInternalBufferChecker.cpp

32 ↗

(On Diff #151166)

Yea, checker writers may can't provide all the template arguments, and it's not convenient to use!

I will try to give a better solution!

65 ↗

(On Diff #151166)

Right, thanks!

lib/StaticAnalyzer/Core/CallEvent.cpp

374

Yea, this maybe a problem, I will test whether this is going to happen and give a fine-grained match. Thanks!

[MTC]

Sorry for the long long delay, I was on the Dragon Boat Festival a few days ago.

This update has two parts:

• Use the matchesName to match the AST node with the specified name, matchesName use regex to match the specified name.
• Use std::vector to record the list of qualified name, user can provide information as much as possible to improve matching accuracy. But can also provide only the function name.

There are two remain issues:

• There is possible match the wrong AST node, e.g. for the NamedDecl foo(), if the function body has the a::b::x, when we match a::b::X(), we will match foo() . Because I'm not familiar with ASTMatcher, my bad, I can't think of a perfect way to match only the specified nodes.
• The std::vector to record the information provide by the users may be not the best data structure.
• I'm not the regex expert, the regex used in this patch definitely has the chance to improve.
  
  And I am not good at English writing, if any comments are not very clear, please correct me. Thanks for the help!

[MTC]

kindly ping!

[NoQ]

lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp

68 ↗

(On Diff #152702)

I wish the old syntax for simple C functions was preserved.

This could be accidentally achieved by using ArrayRef<StringRef> instead of std::vector<StringRef> for your constructor's argument.

lib/StaticAnalyzer/Core/CallEvent.cpp

374–381

Uhm, i think we don't need to flatten the class name to a string and then regex to do this.

We can just unwrap the declaration and see if the newly unwrapped layer matches the expected name on every step, until all expected names have been found.

[MTC]

Thanks for your review, NoQ!

lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp

68 ↗

(On Diff #152702)

ArrayRef<StringRef> can't achieve this goal. The only way I can figure out is changing the declaration to the following form.

CallDescription(StringRef FuncName, unsigned RequiredArgs = NoArgRequirement, ArrayRef<StringRef> QualifiedName = None) {}

lib/StaticAnalyzer/Core/CallEvent.cpp

374–381

Is the way you mentioned above is similar NamedDecl::printQualifiedName()? Get the full name through the DeclContext chain. See https://github.com/llvm-mirror/clang/blob/master/lib/AST/Decl.cpp#L1511.

Or ignore namespace ,like std, just only consider the CXXRecordDecl? If so, dyn_cast<> might be enough.

[xazax.hun]

In D48027#1142324, @MTC wrote:

• There is possible match the wrong AST node, e.g. for the NamedDecl foo(), if the function body has the a::b::x, when we match a::b::X(), we will match foo() . Because I'm not familiar with ASTMatcher, my bad, I can't think of a perfect way to match only the specified nodes.

Hmm, instead of using the match function which will traverse the ast, we could use the HasNameMatcher class which can be invoked on only one node. That class is in an internal namespace though, so I think the best would be to ask the maintainers whether it is ok to use that class externally, or were whe should put the functionality we need.

[MTC]

@xazax.hun Thanks for your tips! After some investigation, MatchFinder::match just traverse one ASTNode, that means match(namedDecl(HasNameMatcher())) and match(namedDecl(matchesName())) both not traverse children. So there are three ways to match the specified AST node.

1. match(namedDecl(HasNameMatcher())) matches the full qualified name that contains template parameter and that's not what we want to see.
2. match(namedDecl(matchesName())) uses llvm regex to match the full qualified name.
3. Unwrap the declaration and match each layer, similar to HasNameMatcher::matchesNodeFullFast().

In this update, I use the third way to match the specified AST node. This is simpler than I thought.

In addition, add a redundant constructor that is only used to construct a CallDescription with one name, this avoids the modification of the existing checker, like BlockInCriticalSectionChecker.cpp. Any suggestions?

[MTC]

kindly ping!

[NoQ]

This looks great, thanks, this is exactly how i imagined it!

[xazax.hun]

Generally looks good, I only wonder if this works well with inline namespaces. Could you test? Probably it will.

[MTC]

• rebase
• Since we have enhanced the ability of CallDescription, remove the helper method isCalledOnStringObject().

[MTC]

In D48027#1201248, @xazax.hun wrote:

Generally looks good, I only wonder if this works well with inline namespaces. Could you test? Probably it will.

Thank you for reminding me! Yea, this can handle inline namespaces.

However this approach has limit. Given the code below, we cannot distinguish whether the basic_string is user-defined struct or namespace. That's means when the user provide {"std", "basic_string", "append"}, we can only know the qualified name of the call sequentially contains std, basic_string, append. We don't know if these names come from RecordDecl or NamespaceDecl.

namespace  std {
  namespace basic_string {
    struct A {
      void append() {}
    };
  }
}

void foo() {
  std::basic_string::A a;
  a.append(); // Match
}

@rnkovacs What do you think? Can this approach meet InnerPointerChecker's needs?

[MTC]

@xazax.hun What do you think?

[xazax.hun]

Sorry for the delay, I think this is OK to commit.
As a possible improvement, I can imagine making it slightly stricter, e.g. you could only skip QualifiedNames for inline namespaces and the beginning. Maybe add support for staring with "" or :: to even disable skipping namespaces at the beginning?
But these are just nice to have features, I am perfectly ok with not having them or doing it in a followup patch.

[xazax.hun]

Oh, and thanks for working on this, this improvement was long overdue, but everybody was busy with something else :)

[rnkovacs]

In D48027#1203944, @MTC wrote:

However this approach has limit. Given the code below, we cannot distinguish whether the basic_string is user-defined struct or namespace. That's means when the user provide {"std", "basic_string", "append"}, we can only know the qualified name of the call sequentially contains std, basic_string, append. We don't know if these names come from RecordDecl or NamespaceDecl.

namespace  std {
  namespace basic_string {
    struct A {
      void append() {}
    };
  }
}

void foo() {
  std::basic_string::A a;
  a.append(); // Match
}

@rnkovacs What do you think? Can this approach meet InnerPointerChecker's needs?

I guess it is highly unlikely for someone to write namespaces like that, and if they do, I think they deserve to have them treated as a std::string.
Thanks, Henry, this is great!

[MTC]

In D48027#1207645, @xazax.hun wrote:

Sorry for the delay, I think this is OK to commit.
As a possible improvement, I can imagine making it slightly stricter, e.g. you could only skip QualifiedNames for inline namespaces and the beginning. Maybe add support for staring with "" or :: to even disable skipping namespaces at the beginning?
But these are just nice to have features, I am perfectly ok with not having them or doing it in a followup patch.

Thanks, Gábor!
I will land it first and do the improvement according to the mismatch case in the followup patch!

[NoQ]

In D48027#1207721, @rnkovacs wrote:

I guess it is highly unlikely for someone to write namespaces like that, and if they do, I think they deserve to have them treated as a std::string.

Yup. On the other hand, if we specify our method as {"basic_string", "c_str"} and they make a namespace basic_string { const char *c_str(); }, we are pretty likely to crash when we try to obtain this-value for the call that isn't a method. This is still not a big deal because it's still highly unlikely, but we've seen crash reports of this sort, and the easier our spec is, the more likely it becomes that somebody has a different thing with the same name. For example, if we want to model iterators and we specify {"begin"} without specifying the base class (so that all sorts of containers were covered), we still want to specify that we're looking for a method call and not for a global function call.

So i believe that one of the important remaining problems with CallDescription is to teach it to discriminate between global functions and methods. We can do it in a number of ways:

1. Make a special sub-class for CallDescription depending on the sort of the function (too verbose),
2. Tag all items in the list as "record" vs. "namespace" (too many tags),
3. Dunno, tons of other boring and verbose approaches,
4. Change our PreCall/PostCall callbacks to callback templates that let allow the user subscribe to specific sub-classes of CallEvent similarly to how he can subscribe to different kinds of statements in PreStmt<Class>/PostStmt<Class>, and then the user doesn't need to write any code to check it dynamically.

[MTC]

In D48027#1209844, @NoQ wrote:

So i believe that one of the important remaining problems with CallDescription is to teach it to discriminate between global functions and methods. We can do it in a number of ways:

1. Make a special sub-class for CallDescription depending on the sort of the function (too verbose),
2. Tag all items in the list as "record" vs. "namespace" (too many tags),
3. Dunno, tons of other boring and verbose approaches,
4. Change our PreCall/PostCall callbacks to callback templates that let allow the user subscribe to specific sub-classes of CallEvent similarly to how he can subscribe to different kinds of statements in PreStmt<Class>/PostStmt<Class>, and then the user doesn't need to write any code to check it dynamically.

Personally, I prefer 4. It is more checker developer friendly!

include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h

 
 /// This class represents a description of a function call using the number of
 /// arguments and the name of the function.
 class CallDescription {
   friend CallEvent;
 
   mutable IdentifierInfo *II = nullptr;
   mutable bool IsLookupDone = false;
-  StringRef FuncName;
+  // The list of the qualified names used to identify the specified CallEvent,
+  // e.g. "{a, b}" represent the qualified names, like "a::b".
+  std::vector<StringRef> QualifiedName;
   unsigned RequiredArgs;
 
 public:
   const static unsigned NoArgRequirement = std::numeric_limits<unsigned>::max();
 
   /// Constructs a CallDescription object.
   ///
+  /// @param QualifiedName The list of the qualified names of the function that
+  /// will be matched. It does not require the user to provide the full list of
+  /// the qualified name. The more details provided, the more accurate the
+  /// matching.
+  ///
+  /// @param RequiredArgs The number of arguments that is expected to match a
+  /// call. Omit this parameter to match every occurrence of call with a given
+  /// name regardless the number of arguments.
+  CallDescription(std::vector<StringRef> QualifiedName,
+                  unsigned RequiredArgs = NoArgRequirement)
+      : QualifiedName(QualifiedName), RequiredArgs(RequiredArgs) {}
+
+  /// Constructs a CallDescription object.
+  ///
   /// @param FuncName The name of the function that will be matched.
   ///
   /// @param RequiredArgs The number of arguments that is expected to match a
   /// call. Omit this parameter to match every occurrence of call with a given
   /// name regardless the number of arguments.
   CallDescription(StringRef FuncName, unsigned RequiredArgs = NoArgRequirement)
-      : FuncName(FuncName), RequiredArgs(RequiredArgs) {}
+      : CallDescription(std::vector<StringRef>({FuncName}), NoArgRequirement) {
+  }
 
   /// Get the name of the function that this object matches.
-  StringRef getFunctionName() const { return FuncName; }
+  StringRef getFunctionName() const { return QualifiedName.back(); }
 };
 
 template<typename T = CallEvent>
 class CallEventRef : public IntrusiveRefCntPtr<const T> {
 public:
   CallEventRef(const T *Call) : IntrusiveRefCntPtr<const T>(Call) {}
   CallEventRef(const CallEventRef &Orig) : IntrusiveRefCntPtr<const T>(Orig) {}
 

lib/StaticAnalyzer/Checkers/InnerPointerChecker.cpp

bool isSymbolTracked(ProgramStateRef State, SymbolRef Sym) {
         if (Entry.second.contains(Sym))
           return true;
       }
       return false;
     }
   };
 
   InnerPointerChecker()
-      : AppendFn("append"), AssignFn("assign"), ClearFn("clear"),
-        CStrFn("c_str"), DataFn("data"), EraseFn("erase"), InsertFn("insert"),
-        PopBackFn("pop_back"), PushBackFn("push_back"), ReplaceFn("replace"),
-        ReserveFn("reserve"), ResizeFn("resize"),
-        ShrinkToFitFn("shrink_to_fit"), SwapFn("swap") {}
-
-  /// Check if the object of this member function call is a `basic_string`.
-  bool isCalledOnStringObject(const CXXInstanceCall *ICall) const;
+      : AppendFn({"std", "basic_string", "append"}),
+        AssignFn({"std", "basic_string", "assign"}),
+        ClearFn({"std", "basic_string", "clear"}),
+        CStrFn({"std", "basic_string", "c_str"}),
+        DataFn({"std", "basic_string", "data"}),
+        EraseFn({"std", "basic_string", "erase"}),
+        InsertFn({"std", "basic_string", "insert"}),
+        PopBackFn({"std", "basic_string", "pop_back"}),
+        PushBackFn({"std", "basic_string", "push_back"}),
+        ReplaceFn({"std", "basic_string", "replace"}),
+        ReserveFn({"std", "basic_string", "reserve"}),
+        ResizeFn({"std", "basic_string", "resize"}),
+        ShrinkToFitFn({"std", "basic_string", "shrink_to_fit"}),
+        SwapFn({"std", "basic_string", "swap"}) {}
 
   /// Check whether the called member function potentially invalidates
   /// pointers referring to the container object's inner buffer.
   bool isInvalidatingMemberFunction(const CallEvent &Call) const;
 
   /// Mark pointer symbols associated with the given memory region released
   /// in the program state.
   void markPtrSymbolsReleased(const CallEvent &Call, ProgramStateRef State,
public:
   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
 
   /// Clean up the program state map.
   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
 };
 
 } // end anonymous namespace
 
-bool InnerPointerChecker::isCalledOnStringObject(
-        const CXXInstanceCall *ICall) const {
-  const auto *ObjRegion =
-    dyn_cast_or_null<TypedValueRegion>(ICall->getCXXThisVal().getAsRegion());
-  if (!ObjRegion)
-    return false;
-
-  QualType ObjTy = ObjRegion->getValueType();
-  if (ObjTy.isNull())
-    return false;
-
-  CXXRecordDecl *Decl = ObjTy->getAsCXXRecordDecl();
-  return Decl && Decl->getName() == "basic_string";
-}
-
 bool InnerPointerChecker::isInvalidatingMemberFunction(
         const CallEvent &Call) const {
   if (const auto *MemOpCall = dyn_cast<CXXMemberOperatorCall>(&Call)) {
     OverloadedOperatorKind Opc = MemOpCall->getOriginExpr()->getOperator();
     if (Opc == OO_Equal || Opc == OO_PlusEqual)
       return true;
     return false;
   }

 // -- Calling non-const member functions, except operator[], at, front, back,
 // begin, rbegin, end, and rend."
 
 void InnerPointerChecker::checkPostCall(const CallEvent &Call,
                                         CheckerContext &C) const {
   ProgramStateRef State = C.getState();
 
   if (const auto *ICall = dyn_cast<CXXInstanceCall>(&Call)) {
-    if (isCalledOnStringObject(ICall)) {
-      const auto *ObjRegion = dyn_cast_or_null<TypedValueRegion>(
-              ICall->getCXXThisVal().getAsRegion());
 
-      if (Call.isCalled(CStrFn) || Call.isCalled(DataFn)) {
-        SVal RawPtr = Call.getReturnValue();
-        if (SymbolRef Sym = RawPtr.getAsSymbol(/*IncludeBaseRegions=*/true)) {
-          // Start tracking this raw pointer by adding it to the set of symbols
-          // associated with this container object in the program state map.
 
-          PtrSet::Factory &F = State->getStateManager().get_context<PtrSet>();
-          const PtrSet *SetPtr = State->get<RawPtrMap>(ObjRegion);
-          PtrSet Set = SetPtr ? *SetPtr : F.getEmptySet();
-          assert(C.wasInlined || !Set.contains(Sym));
-          Set = F.add(Set, Sym);
 
-          State = State->set<RawPtrMap>(ObjRegion, Set);
-          C.addTransition(State);
-        }
-        return;
-      }
 
-      // Check [string.require] / second point.
-      if (isInvalidatingMemberFunction(Call)) {
-        markPtrSymbolsReleased(Call, State, ObjRegion, C);
-        return;
-      }
-    }
-  }
 
   // Check [string.require] / first point.
   checkFunctionArguments(Call, State, C);
 }
 
 void InnerPointerChecker::checkDeadSymbols(SymbolReaper &SymReaper,
                                            CheckerContext &C) const {
   ProgramStateRef State = C.getState();

lib/StaticAnalyzer/Core/CallEvent.cpp

 }
 
 bool CallEvent::isCalled(const CallDescription &CD) const {
   // FIXME: Add ObjC Message support.
   if (getKind() == CE_ObjCMessage)
     return false;
   if (!CD.IsLookupDone) {
     CD.IsLookupDone = true;
-    CD.II = &getState()->getStateManager().getContext().Idents.get(CD.FuncName);
+    CD.II = &getState()->getStateManager().getContext().Idents.get(
+        CD.getFunctionName());
   }
   const IdentifierInfo *II = getCalleeIdentifier();
   if (!II || II != CD.II)
     return false;
+
+  const Decl *D = getDecl();
+  // If CallDescription provides prefix names, use them to improve matching
+  // accuracy.
+  if (CD.QualifiedName.size() > 1 && D) {
+    const DeclContext *Ctx = D->getDeclContext();
+    std::vector<StringRef> QualifiedName = CD.QualifiedName;
+    QualifiedName.pop_back();
+    for (; Ctx && isa<NamedDecl>(Ctx); Ctx = Ctx->getParent()) {
+      if (const auto *ND = dyn_cast<NamespaceDecl>(Ctx)) {
+        if (!QualifiedName.empty() && ND->getName() == QualifiedName.back())
+          QualifiedName.pop_back();
+        continue;
+      }
+
+      if (const auto *RD = dyn_cast<RecordDecl>(Ctx)) {
+        if (!QualifiedName.empty() && RD->getName() == QualifiedName.back())
+          QualifiedName.pop_back();
+        continue;
+      }
+    }
+
+    if (!QualifiedName.empty())
+      return false;
+  }
+
   return (CD.RequiredArgs == CallDescription::NoArgRequirement ||
           CD.RequiredArgs == getNumArgs());
 }
 
 SVal CallEvent::getArgSVal(unsigned Index) const {
   const Expr *ArgE = getArgExpr(Index);
   if (!ArgE)
     return UnknownVal();