[analyzer][NFC] Introduce CallDescription::matches() in addition to isCalled()

[steakhal]

Summary

This patch introduces CallDescription::matches() member function,
accepting a CallEvent.
Semantically, Call.isCalled(CD) is the same as CD.matches(Call).

The patch also introduces the matchesAny() variadic free function template.
It accepts a CallEvent and at least one CallDescription to match
against.

[steakhal]

use free-function instead of a CallDescription static one to enable terser syntax for calling this by using ADL.
Also, add Doxygen group comment.

[xazax.hun]

I like the idea of introducing variadic versions of the matching. But what is the motivation behind introducing new methods that are discouraged to use? I think the motivation behind these changes should be included in the description and the commit message.

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

100

I am confused. When do we use snake_case and when do we use likeThis?

109

What is the C++ standard used in LLVM nowadays? If C++17 or above, couldn't you simplify this using fold expressions?

[steakhal]

In D113590#3127720, @xazax.hun wrote:

I like the idea of introducing variadic versions of the matching.

They existed earlier but they were actually never used for some reason.

But what is the motivation behind introducing new methods that are discouraged to use?

CallDescriptions are meant to be a value-type groupping/holding all data necessary to 'consume' a function call event.
They are not designed to do caching but to blindly do a matching to see if the given call event is interesting or not.
Matching a CallDescription can be quite expensive, even more so in the future when I will propose introducing AST-matchers
for matching the types of the functions to let us select the right overload.
By doing so, we could read config files and populate CallDescriptionMaps at runtime, opening further configuration possibilities.

In contrast to this, CallDescriptionMaps are designed so that they are supposed to use some sort of caching mechanism.
In theory, we should try hard to reduce the matching complexity to O(1), since this operation is heavily used by the checkers.
One way to achieve this is to associate a function decl pointer to a CallDescription and compare only the call event's function decl against the cached one, which would achieve our O(1) goal.
At least if the call description is supposed to handle only a specific overload, which I presume dominates the rest of the use-cases, but I haven't checked this assumption yet, nor implemented any of these.

I think the motivation behind these changes should be included in the description and the commit message.

Sorry about that, I'll add it to the head commit of the stack.

[NoQ]

In theory, we should try hard to reduce the matching complexity to O(1), since this operation is heavily used by the checkers.

It is but I don't recall this ever being an actual problem. These maps are usually tiny and function calls are so expensive on their own that such iteration becomes negligible. But generally, yeah, one of the reasons we have CallDescriptionMap is so that we didn't have to copy-paste such optimization from checker to checker.

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

108

Ts is always CallDescription, right? I'm not good with variadic templates but it sounds like we should be able to specify this.

109

I think we're still on C++14.

[ASDenysPetrov]

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

100

According to the coding standards we use snake_case for STL-like functions, but I couldn't find matches and matches_any among them.

109

What is the C++ standard used in LLVM nowadays?

As we can see, it is C++14. So fold expressions are not the case unfortunately.

[martong]

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

87

95–97

Instead of this comment, let's enforce what you mean by making these member functions private and making CallDescriptionMap a friend!

(And by doing that you have to update the summary of the patch as well to reflect the changes ...)

[martong]

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

95

Actually you are talking about just one function aren't you?
bool matches(const CallEvent &Call) const

The friend functions below are part of the public API we provide for the checkers looking at the next patch:

bool BlockInCriticalSectionChecker::isBlockingFunction(const CallEvent &Call) const {
  return matches_any(Call, SleepFn, GetcFn, FgetsFn, ReadFn, RecvFn);

[steakhal]

• matches_any() -> matchesAny()
• fixed some typos
• removed the discouraging comment reminding users not using CallDescriptions directly

[steakhal]

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

95

I actually meant the whole overload set in the broadest term, including matches and matches_any as well.
But I decided to remove this comment since it doesn't make much sense to enforce a specific usage/pattern unless we have a compelling reason to do so. Since I cannot see (yet) how could we implement caching in an efficient way I would rather push these to the future.

95–97

I'm not sure about that, I would rather remove the note altogether. See my previous comment why.

108

AFAIK this is the best we can do, unless of course we want heavy TMP stuff achieving the same thing at the end of the day.
If you don't pass a CallDescription, the recursion won't match with the base-case, thus we get a compile error. However, I think we shouldn't really worry about usercode misusing this API.

109

I miss them so much! Although we have to comply with c++14.
https://github.com/llvm/llvm-project/blob/main/llvm/CMakeLists.txt#L48-L49

[martong]

Okay, LGTM!

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

public:
   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; }
+
+  /// @name Matching CallDescriptions against a CallEvent
+  /// @{
+
+  /// Returns true if the CallEvent is a call to a function that matches
+  /// the CallDescription.
+  ///
+  /// \note This function is not intended to be used to match Obj-C method
+  /// calls.
+  bool matches(const CallEvent &Call) const;
+
+  /// Returns true whether the CallEvent matches on any of the CallDescriptions
+  /// supplied.
+  ///
+  /// \note This function is not intended to be used to match Obj-C method
+  /// calls.
+  friend bool matchesAny(const CallEvent &Call, const CallDescription &CD1) {
+    return CD1.matches(Call);
+  }
+
+  /// \copydoc clang::ento::matchesAny(const CallEvent &, const CallDescription &)
+  template <typename... Ts>
+  friend bool matchesAny(const CallEvent &Call, const CallDescription &CD1,
+                         const Ts &...CDs) {
+    return CD1.matches(Call) || matchesAny(Call, CDs...);
+  }
+  /// @}
 };
 
 /// An immutable map from CallDescriptions to arbitrary data. Provides a unified
 /// way for checkers to react on function calls.
 template <typename T> class CallDescriptionMap {
   friend class CallDescriptionSet;
 
   // Some call descriptions aren't easily hashable (eg., the ones with qualified
public:
   // we don't do redundant copies.
   CallDescriptionMap(const CallDescriptionMap &) = delete;
   CallDescriptionMap &operator=(const CallDescription &) = delete;
 
   LLVM_NODISCARD const T *lookup(const CallEvent &Call) const {
     // Slow path: linear lookup.
     // TODO: Implement some sort of fast path.
     for (const std::pair<CallDescription, T> &I : LinearMap)
-      if (Call.isCalled(I.first))
+      if (I.first.matches(Call))
         return &I.second;
 
     return nullptr;
   }
 };
 
 /// An immutable set of CallDescriptions.
 /// Checkers can efficiently decide if a given CallEvent matches any

clang/lib/StaticAnalyzer/Core/CallDescription.cpp

 //===- CallDescription.cpp - function/method call matching     --*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file This file defines a generic mechanism for matching for function and
 /// method calls of C, C++, and Objective-C languages. Instances of these
 /// classes are frequently used together with the CallEvent classes.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 
 using namespace llvm;
 using namespace clang;
 
 // A constructor helper.
 static Optional<size_t> readRequiredParams(Optional<unsigned> RequiredArgs,

 
 /// Construct a CallDescription with default flags.
 ento::CallDescription::CallDescription(
     ArrayRef<const char *> QualifiedName,
     Optional<unsigned> RequiredArgs /*= None*/,
     Optional<size_t> RequiredParams /*= None*/)
     : CallDescription(0, QualifiedName, RequiredArgs, RequiredParams) {}
 
+bool ento::CallDescription::matches(const CallEvent &Call) const {
+  // FIXME: Add ObjC Message support.
+  if (Call.getKind() == CE_ObjCMessage)
+    return false;
+
+  const auto *FD = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+  if (!FD)
+    return false;
+
+  if (Flags & CDF_MaybeBuiltin) {
+    return CheckerContext::isCLibraryFunction(FD, getFunctionName()) &&
+           (!RequiredArgs || RequiredArgs <= Call.getNumArgs()) &&
+           (!RequiredParams || RequiredParams <= Call.parameters().size());
+  }
+
+  if (!II.hasValue()) {
+    II = &Call.getState()->getStateManager().getContext().Idents.get(
+        getFunctionName());
+  }
+
+  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.
+
+    // Fallback to the slow stringification and comparison for:
+    // C++ overloaded operators, constructors, destructors, etc.
+    // FIXME This comparison is way SLOWER than comparing pointers.
+    // At some point in the future, we should compare FunctionDecl pointers.
+    return Name.getAsString() == CD.getFunctionName();
+  };
+
+  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;
+  };
+
+  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;
+    };
+
+    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;
+    }
+
+    // We matched if we consumed all expected qualifier segments.
+    return QualifierPartsIt == QualifierPartsEndIt;
+  };
+
+  // Let's start matching...
+  if (!ExactMatchArgAndParamCounts(Call, *this))
+    return false;
+
+  if (!MatchNameOnly(*this, FD))
+    return false;
+
+  if (!hasQualifiedNameParts())
+    return true;
+
+  return MatchQualifiedNameParts(*this, FD);
+}
+
 ento::CallDescriptionSet::CallDescriptionSet(
     std::initializer_list<CallDescription> &&List) {
   Impl.LinearMap.reserve(List.size());
   for (const CallDescription &CD : List)
     Impl.LinearMap.push_back({CD, /*unused*/ true});
 }
 
 bool ento::CallDescriptionSet::contains(const CallEvent &Call) const {
   return static_cast<bool>(Impl.lookup(Call));
 }

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

ProgramPoint CallEvent::getProgramPoint(bool IsPreVisit,
 
   SourceLocation Loc = getSourceRange().getBegin();
   if (IsPreVisit)
     return PreImplicitCall(D, Loc, getLocationContext(), Tag);
   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 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.II.hasValue()) {
-    CD.II = &getState()->getStateManager().getContext().Idents.get(
-        CD.getFunctionName());
-  }
-
-  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.
-
-    // Fallback to the slow stringification and comparison for:
-    // C++ overloaded operators, constructors, destructors, etc.
-    // FIXME This comparison is way SLOWER than comparing pointers.
-    // At some point in the future, we should compare FunctionDecl pointers.
-    return Name.getAsString() == CD.getFunctionName();
-  };
-
-  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;
-  };
-
-  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;
-    };
-
-    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;
-    }
-
-    // We matched if we consumed all expected qualifier segments.
-    return QualifierPartsIt == QualifierPartsEndIt;
-  };
-
-  // Let's start matching...
-  if (!ExactMatchArgAndParamCounts(*this, CD))
-    return false;
-
-  if (!MatchNameOnly(CD, FD))
-    return false;
-
-  if (!CD.hasQualifiedNameParts())
-    return true;
-
-  return MatchQualifiedNameParts(CD, FD);
+  return CD.matches(*this);
 }
 
 SVal CallEvent::getArgSVal(unsigned Index) const {
   const Expr *ArgE = getArgExpr(Index);
   if (!ArgE)
     return UnknownVal();
   return getSVal(ArgE);
 }