[analyzer][NFC] Refactor CallEvent::isCalled()

[steakhal]

Summary

Refactor the code to make it more readable.

It will set up further changes, and improvements to this code in subsequent patches.
This is a non-functional change.

[steakhal]

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

370–373

I'd like to enable this, but we need to reach consensus about this.

[martong]

What is the test coverage of the newly added lines?

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

1287–1289

qualifier is an overloaded term. One might think about type qualifiers like const and volatile. I'd rather call this something like begin_qualified_name_parts or begin_qualified_name.

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

325–329

can we make it pure?

345–363

383

Should we check names before arg/param count? Just to preserve the non-functional change attribute of this patch.

386–387

Why? I don't see this logic in the original code. Even if it was there, it is not obvious why we do this and what justifies it.

[steakhal]

In D111534#3060865, @martong wrote:

What is the test coverage of the newly added lines?

I'm pretty sure they all are covered.
Let me check this, after we decided if we want to enable L370.

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

1287–1289

I agree! I'll update accordingly.

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

325–329

We could. My intention was to express the most important parameter it will depend on.
I'm okay with either approach.

However, if we pursue this goal, the ExactMatchArgAndParamCounts should be also changed to follow this pattern.
But that would result in less readable code IMO.
So, I would rather stick to the current style. WDYT?

370–373

Really, just check return-value-guaranteed.cpp for more insight.

383

The order in which we check the conditions should not matter. Regarless of the fact we return false, we return false.
My point was to match param counts first, since that is O(1), while the name matching could be more complex in the case of non-identifiers which involves stringification and string comparisons.
So, I would keep the order as-is.
I'll add a comment about this to make this decision clear.

386–387

tldr; this if condition only makes sense if L370 is enabled.

---

CD.QualifiedName.size() == 1 means that we don't have any qualifier parts, but only a single function name which was previously matched at L381.

Consider this example: CD: { "getenv" } and Call: std::getenv()
The name part and param count would match, thus we need to match the qualifier parts.

Now comes L370 into play. It will reject any match, where by the end of the match we still have unmatched qualifier parts of Call.
For instance, CD: { "my_namespace", "std", "invoke" } and Call: test_good::my_namespace::std::invoke.
Previously, we would have accept the Call by the CallDescription CD. Now, I'm proposing to tighten the behavior, by rejecting these, and only accept if by the end of the matching the Call does not have any qualifier parts left.

Now imagine that the if (CD.QualifiedName.size() == 1) at L384 is missing.
We would reject the match of qualifier parts using the example Call and CD, when we don't even specified any qualifier parts - which seems odd. We should have match for any qualifier sequence if none is specified in the CallDescription.

This property was implicitly encoded by the invariant of the loop. The loop entered only once, but it immediately broke out due to L340, since NumUnmatched is 0. After the loop, at L355 the branch is not taken, thus it will fallthrough and accept the qualifier segments.

[steakhal]

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

370–373

Actually, it might be cleaner to enable this in a follow-up patch.
It will need a lot of fixup in the return-value-guaranteed.cpp file.

[martong]

The way I see now, we should break this into 2 patches. 1) the strictly NFC changes 2) the return-value-guaranteed.cpp related FIXME and the reordering of the matching logic.

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

325–329

For me, a function with a name match suggests that there should at least two things we'd like to match or compare, that is why I consider having the compared things passed as parameters more readable.

And ExactMatchArgAndParamCounts takes the CallDescription as a parameter while other matcher lambdas don't, this is not consistent. IMHO, CD should be a parameter for all matcher lambda because that is the thingy that we want to compare/match with (and the other parameter should be the other thing we compare to).

370–373

Umm, could you please elaborate? There are 3 structs in that test file. What is the exact problem? Or rather just do that in a follow-up patch and just remove this FIXME together with the uncommented block?

383

Ok. But then it's no longer an NFC patch, because we do change the original behavior, this could perhaps result that a CallEvent is not processed by a checker, isn't it? I still don't see why the changed order in which we check the conditions should not matter.

Since you already started to work out a follow-up patch for the return-value-guaranteed.cpp cases, perhaps it'd make sense to do this reordering in a follow-up patch? That way, we could more confidently state that this patch is indeed NFC.

386–387

Okay, makes sense, could you please add a comment then to this if block that it means that we don't have any qualifier parts, but only a single function name which was previously matched ?

[xazax.hun]

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

1240

If we are about to refactor this, maybe IsLookupDone and II can be merged into a single optional.

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

331–334

You probably mean C++ overloaded operator. We can get a name for most overloaded function from getDeclName.

370–373

What do you mean by this comment? It is probably perfectly valid to have unmatched NamespaceDecl when the namespace is inline. Do I miss something?

380

I wonder if it would be nicer to have the definitions of these closer to their use.

[steakhal]

Addressed review comments.

[steakhal]

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

1240

I'm gonna fix this, thanks.

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

331–334

Actually, I'm doing exactly that in the child revision.
This patch is an NFC change, preparing that one you pointed at.

370–373

Oh well, I completely forgot about inline namespaces.
You are right, if we have only inline namespaces beyond this point, we should still match.
I'm gonna address this in a follow-up patch, enforcing this property while ignoring inline and anonymous namespaces.

380

TBH, they should be private member functions of CallDescription IMO.

383

What I wanted to highlight is that the order of the properties in which we check them does not matter.
The logical and operator is commutative: PropertyA && PropertyB && PropertyC is the same as PropertyB && PropertyA && PropertyC.
In our case, all properties should match to accept the Call. That being said, I'm pretty sure it's still NFC.

386–387

You are right that we should not directly access QualifiedName, and we should use a member function call here.
Check the updated version of this patch.

[martong]

LGTM (with nits)! Thanks!

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

1240

Lovely.

1275

Good!

1293

Maybe a comment would be useful here with an example. Something like e.g. 'std::sort' has a qualified part ('std') but the global 'memset' does not have

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

325–329

This is the only lambda where we still have [&CD], with all other lambda's you pass CD as a param.

380

That's a good idea!

383

Okay, makes sense!

[steakhal]

• purified lambda
• added doc comments for hasQualifiedNameParts()

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

1293

Yeah, sure.

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

325–329

Oh, I must have missed that, sorry.

380

I'm not planning to do that.

[steakhal]

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

349

TBH I don't understand why doesn't isa<NamespaceDecl, RecordDecl>() work. I could have used this variadic form so many times.
WDYT, should I propose turning isa and isa_and_nonnull˙into variadic functions?

[martong]

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

349

TBH I don't understand why doesn't isa<NamespaceDecl, RecordDecl>() work. I could have used this variadic form so many times.
WDYT, should I propose turning isa and isa_and_nonnull˙into variadic functions?

Yes, that's a good idea!

[ASDenysPetrov]

Thank you for adding me. I'll make a deeper review later.

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

1289

What rules did you use to name this functions? It seems that it goes against LLVM naming rules.

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

336–352

Can we move these lambdas in separate functions? IMO it could make the code even more readable.

[steakhal]

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

1289

Not exactly. There is an exception for begin() and end().
That being said, begin should have been a suffix instead of being a prefix.
But I still like this more :D

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

336–352

We could, but I'm not planning to move them.
That would be more appropriate to move all CallDescription implementation to its own translation unit.

349

Actually, it's already variadic :D
I created a follow-up patch for addressing similar issues in D111982.

[ASDenysPetrov]

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

1289

Oh, now I see the exception. I also prefer begin as a prefix because it makes better search through the popup hints of IDEs.

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

enum CallDescriptionFlags : int {
   /// number of arguments.
   CDF_MaybeBuiltin = 1 << 0,
 };
 
 /// 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;
+  mutable Optional<const IdentifierInfo *> II;
   // 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<const char *> QualifiedName;
   Optional<unsigned> RequiredArgs;
   Optional<size_t> RequiredParams;
   int Flags;
 
   // A constructor helper.
public:
   /// @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(int Flags, ArrayRef<const char *> QualifiedName,
                   Optional<unsigned> RequiredArgs = None,
                   Optional<size_t> RequiredParams = None)
       : QualifiedName(QualifiedName), RequiredArgs(RequiredArgs),
         RequiredParams(readRequiredParams(RequiredArgs, RequiredParams)),
-        Flags(Flags) {}
+        Flags(Flags) {
+    assert(!QualifiedName.empty());
+  }
 
   /// Construct a CallDescription with default flags.
   CallDescription(ArrayRef<const char *> QualifiedName,
                   Optional<unsigned> RequiredArgs = None,
                   Optional<size_t> RequiredParams = None)
       : CallDescription(0, QualifiedName, RequiredArgs, RequiredParams) {}
 
   /// Get the name of the function that this object matches.
   StringRef getFunctionName() const { return QualifiedName.back(); }
+
+  /// Get the qualified name parts in reversed order.
+  /// E.g. { "std", "vector", "data" } -> "vector", "std"
+  auto begin_qualified_name_parts() const {
+    return std::next(QualifiedName.rbegin());
+  }
+  auto end_qualified_name_parts() const { return QualifiedName.rend(); }
+
+  /// It's false, if and only if we expect a single identifier, such as
+  /// `getenv`. It's true for `std::swap`, or `my::detail::container::data`.
+  bool hasQualifiedNameParts() const { return QualifiedName.size() > 1; }
 };
 
 /// An immutable map from CallDescriptions to arbitrary data. Provides a unified
 /// way for checkers to react on function calls.
 template <typename T> class CallDescriptionMap {
   // Some call descriptions aren't easily hashable (eg., the ones with qualified
   // names in which some sections are omitted), so let's put them
   // in a simple vector and use linear lookup.

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

ProgramPoint CallEvent::getProgramPoint(bool IsPreVisit,
   return PostImplicitCall(D, Loc, getLocationContext(), Tag);
 }
 
 bool CallEvent::isCalled(const CallDescription &CD) const {
   // FIXME: Add ObjC Message support.
   if (getKind() == CE_ObjCMessage)
     return false;
 
-  const IdentifierInfo *II = getCalleeIdentifier();
-  if (!II)
-    return false;
-  const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(getDecl());
+  const auto *FD = dyn_cast_or_null<FunctionDecl>(getDecl());
   if (!FD)
     return false;
 
   if (CD.Flags & CDF_MaybeBuiltin) {
     return CheckerContext::isCLibraryFunction(FD, CD.getFunctionName()) &&
            (!CD.RequiredArgs || CD.RequiredArgs <= getNumArgs()) &&
            (!CD.RequiredParams || CD.RequiredParams <= parameters().size());
   }
 
-  if (!CD.IsLookupDone) {
-    CD.IsLookupDone = true;
+  if (!CD.II.hasValue()) {
     CD.II = &getState()->getStateManager().getContext().Idents.get(
         CD.getFunctionName());
   }
 
-  if (II != CD.II)
+  const auto MatchNameOnly = [](const CallDescription &CD,
+                                const NamedDecl *ND) -> bool {
+    DeclarationName Name = ND->getDeclName();
+    if (const auto *II = Name.getAsIdentifierInfo())
+      return II == CD.II.getValue(); // Fast case.
+
+    // Simply report mismatch for:
+    // C++ overloaded operators, constructors, destructors, etc.
     return false;
+  };
 
-  // If CallDescription provides prefix names, use them to improve matching
-  // accuracy.
-  if (CD.QualifiedName.size() > 1 && FD) {
-    const DeclContext *Ctx = FD->getDeclContext();
-    // See if we'll be able to match them all.
-    size_t NumUnmatched = CD.QualifiedName.size() - 1;
-    for (; Ctx && isa<NamedDecl>(Ctx); Ctx = Ctx->getParent()) {
-      if (NumUnmatched == 0)
-        break;
+  const auto ExactMatchArgAndParamCounts =
+      [](const CallEvent &Call, const CallDescription &CD) -> bool {
+    const bool ArgsMatch =
+        !CD.RequiredArgs || CD.RequiredArgs == Call.getNumArgs();
+    const bool ParamsMatch =
+        !CD.RequiredParams || CD.RequiredParams == Call.parameters().size();
+    return ArgsMatch && ParamsMatch;
+  };
 
-      if (const auto *ND = dyn_cast<NamespaceDecl>(Ctx)) {
-        if (ND->getName() == CD.QualifiedName[NumUnmatched - 1])
-          --NumUnmatched;
-        continue;
-      }
+  const auto MatchQualifiedNameParts = [](const CallDescription &CD,
+                                          const Decl *D) -> bool {
+    const auto FindNextNamespaceOrRecord =
+        [](const DeclContext *Ctx) -> const DeclContext * {
+      while (Ctx && !isa<NamespaceDecl, RecordDecl>(Ctx))
+        Ctx = Ctx->getParent();
+      return Ctx;
+    };
 
-      if (const auto *RD = dyn_cast<RecordDecl>(Ctx)) {
-        if (RD->getName() == CD.QualifiedName[NumUnmatched - 1])
-          --NumUnmatched;
+    auto QualifierPartsIt = CD.begin_qualified_name_parts();
+    const auto QualifierPartsEndIt = CD.end_qualified_name_parts();
+
+    // Match namespace and record names. Skip unrelated names if they don't
+    // match.
+    const DeclContext *Ctx = FindNextNamespaceOrRecord(D->getDeclContext());
+    for (; Ctx && QualifierPartsIt != QualifierPartsEndIt;
+         Ctx = FindNextNamespaceOrRecord(Ctx->getParent())) {
+      // If not matched just continue and try matching for the next one.
+      if (cast<NamedDecl>(Ctx)->getName() != *QualifierPartsIt)
         continue;
-      }
+      ++QualifierPartsIt;
     }
 
-    if (NumUnmatched > 0)
-      return false;
-  }
+    // We matched if we consumed all expected qualifier segments.
+    return QualifierPartsIt == QualifierPartsEndIt;
+  };
+
+  // Let's start matching...
+  if (!ExactMatchArgAndParamCounts(*this, CD))
 
-  return (!CD.RequiredArgs || CD.RequiredArgs == getNumArgs()) &&
-         (!CD.RequiredParams || CD.RequiredParams == parameters().size());
+  if (!MatchNameOnly(CD, FD))
+    return false;
+
+  if (!CD.hasQualifiedNameParts())
+    return true;
+
+  return MatchQualifiedNameParts(CD, FD);
 }
 
 SVal CallEvent::getArgSVal(unsigned Index) const {
   const Expr *ArgE = getArgExpr(Index);
   if (!ArgE)
     return UnknownVal();
   return getSVal(ArgE);
 }
 
 SourceRange CallEvent::getArgSourceRange(unsigned Index) const {
   const Expr *ArgE = getArgExpr(Index);
   if (!ArgE)
     return {};