[NFC][analyzer] Allow CallDescriptions to be matched with CallExprs

[Szelethus]

Summary

As of now, we have two interfaces to for defining signatures: StdLibraryFunctionsChecker::Signature and CallDescription. An example for how Signatures are used can be seen here:

addToFunctionSummaryMap(
    "isprint", Signature(ArgTypes{IntTy}, RetType{IntTy}),
    Summary(EvalCallAsPure)
        .Case({ArgumentCondition(0U, WithinRange, Range(32, 126)),
               ReturnValueCondition(OutOfRange, SingleValue(0))})
        .Case({ArgumentCondition(0U, OutOfRange, Range(32, 126)),
               ReturnValueCondition(WithinRange, SingleValue(0))}));

The name of the function is searched for in translation unit's identifier table, then the Signature is matched against each decl Decl with the same name. Ideally, this yields a FunctionDecl, which is mapped to its Summary.

This works well for C functions, but doesn't support C++ at all.

CallDescription emerged with a strong emphasis on recognizing C++ functions. The common example brough up is std::string, which in some standard library implementations is actually called something like std::__cxx11::basic_string, but not in others. Matching this can be a nightmare for checker developers. For this reason, CallDescriptions can be defined like this:

InnerPointerChecker()
    : AppendFn({"std", "basic_string", "append"}),
      AssignFn({"std", "basic_string", "assign"}),
      AddressofFn({"std", "addressof"}),
      ClearFn({"std", "basic_string", "clear"}),
      CStrFn({"std", "basic_string", "c_str"}), DataFn({"std", "data"}, 1),
      DataMemberFn({"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"}) {}

Any identifier which matches at least these identifiers are considered a match (which sometimes leads to incorrect matching, e.g. D81745).

CallDescriptions are (usually) not used for digging up FunctionDecls from the translation unit, but rather during symbolic execution to check in a pre/post call event whether the called function matches the CallDescription:

bool InnerPointerChecker::isInnerPointerAccessFunction(
    const CallEvent &Call) const {
  return matchesAny(Call, CStrFn, DataFn, DataMemberFn);
}

Most of the new checkers implementing pre/post condition checks on functions now use CallDescriptionMap or CallDescriptionSet. Its up to debate whether the newer Signature approach is better, but its not obvious, and converting from one to the other may be non-trivial as well.

---

Now, onto this patch. Since CallDescriptions can only be matched against CallEvents that are created during symbolic execution, it was not possible to use it in syntactic-only contexts. For example, even though InnerPointerChecker can check with its set of CallDescriptions whether a function call is interested during analysis, its unable to check without hassle whether a non-analyzer piece of code also calls such a function.

The patch adds the ability to use CallDescriptions in syntactic contexts as well. While we already have that in Signature, we still want to leverage the ability to use dynamic information when we have it (function pointers, for example). This could be done with Signature as well (StdLibraryFunctionsChecker does it), but it makes it even less of a drop-in replacement.

[steakhal]

I strongly belive that this should be an overload to the existing 'matches' API. Maybe add a comment that prefer the other overload if can. But having an overload for that alread implies this anyway. That being said, digging out a callexpr from a CallEvent and calling the callexpr overload seems to be too artifical to me to worry about.

[Szelethus]

In D119004#3297025, @steakhal wrote:

I strongly belive that this should be an overload to the existing 'matches' API. Maybe add a comment that prefer the other overload if can. But having an overload for that alread implies this anyway.

I somewhat disagree. CallDescription is one of the interfaces that newcomers come by rather fast, and a descriptive name would be a nice piece of guidance. I am not sure what can be gained by turning this to an overload.

That being said, digging out a callexpr from a CallEvent and calling the callexpr overload seems to be too artifical to me to worry about.

Well, a tiny bit more is happening than that with the argument count -- what do you mean with this statement exactly?

[Szelethus]

Now that I remember, the ever so slightly different overloads of ProgramState::getSVal is a prime example I think. I always percieved that I have the means to invoke several of them at any point, but I never really knew which one. Though, to be fair, they were not documented particularly well (at least as I remember it).

[NoQ]

The original lookup() isn't exactly precise either, it's just slightly more precise as it has better access to path-sensitive information such as current values of function pointers, but this doesn't necessarily help given that these pointers can still be unknown. And when the information is not available the lookup silently fails in both cases.

But I can certainly get behind demotivating callers from calling the new function unless they know what they're doing. Maybe lookupAsWritten() to indicate that the function intentionally ignores the runtime state of the program and looks at the syntax only?

[steakhal]

In D119004#3299971, @NoQ wrote:

The original lookup() isn't exactly precise either, it's just slightly more precise as it has better access to path-sensitive information such as current values of function pointers, but this doesn't necessarily help given that these pointers can still be unknown. And when the information is not available the lookup silently fails in both cases.

But I can certainly get behind demotivating callers from calling the new function unless they know what they're doing. Maybe lookupAsWritten() to indicate that the function intentionally ignores the runtime state of the program and looks at the syntax only?

I still don't see the benefit of introducing another API.
This is actually a difference between the CallEvent and a CallExpr, thus it has not much to do with the CallDescription. For choosing the right matches() overload inherently depends on knowing about the parameter, on which we overload on.
We should have this as a comment for the type CallEvent, and I'm okay with reminding users even at the matches(CallExpr) overload.
I'm still heavily against introducing a new API instead of an overload.

[NoQ]

It's definitely a bug-prone scenario. I can totally see people stuffing whatever happens to be more readily available in the code into the API without thinking too much about the pros and cons. The difference between CallExpr and CallEvent is large in general but with respect to this API it's very subtle. I can easily imagine people missing it even when they know the difference between CallExpr and CallEvent in general. So I think it's worth attracting attention to.

Also technically a new overload *is* a new API. It just happens to have the same name as the old one.

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

102–103

182–183

In doxygen these comments will be below :)

I think this should be a full comment so that people didn't have to click.

[steakhal]

I think I don't have much to add. I still haven't changed my mind, but let's go with what the majority of people want.
To make the whole stack consistent, consider mocking the variadic free function matchesAny() as well for CallExprs.

[Szelethus]

• Rename from .*Imprecise to .*AsWritten.
• Copy comments to relevant functions.

[steakhal]

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

102–103

ping

133

I think it's a free function. I know that copydoc did not work for this example.
Are you sure adding the ::CallDescription fixes the doc comment?

clang/unittests/StaticAnalyzer/CallDescriptionTest.cpp

50

.

501

You could have define ResultMap ad a virtual base class, which would be implemented by two different classes. One of which would use the asWritten lookups, etc.
You could make_unique of the required one and inject it to the Action.

That way those tests would look just the same as the previous ones.

[Szelethus]

Remove a newline.

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

102–103

This is actually the CallEvent variant, I corrected the CallExpr one :)

133

Yes! Its still in CallDescriptions "namespace", as its defined in-class. I ran doxygen-clang and can confirm that this works, but only without line breaks (or at least I haven't figured out how to do it without it, not even with backslash)

clang/unittests/StaticAnalyzer/CallDescriptionTest.cpp

501

My rationale was that reusing an already existing machinery which is already used in many of the static analyzer unit tests is far friendlier for beginners. I think fracturing the file specific stuff here would increase the barrier of entry for very little gain.

One of the things I like a lot on unit tests is that they demonstrate on a small scale a part of the analyzer's core machinery. I think dividing this up would go against that as well.

[steakhal]

I think it deserves an accept, however, as I don't agree with the rationale I'll let someone else for doing this.

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

133

Ah, thanks!

clang/unittests/StaticAnalyzer/CallDescriptionTest.cpp

501

If you really think this way, you should port the existing tests of this file to the new format to get rid of the already existing "machinery".
I'm okay either way, but not with mixing the two approaches.

[NoQ]

Looks great, thanks!

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

public:
 
   /// 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 if the CallEvent is a call to a function that matches
+  /// the CallDescription.
+  ///
+  /// When available, always prefer matching with a CallEvent! This function
+  /// exists only when that is not available, for example, when _only_
+  /// syntactic check is done on a piece of code.
+  ///
+  /// Also, StdLibraryFunctionsChecker::Signature is likely a better candicade
+  /// for syntactic only matching if you are writing a new checker. This is
+  /// handy if a CallDescriptionMap is already there.
+  ///
+  /// The function is imprecise because CallEvent understands the precise
+  /// argument count better (see comments for CallEvent::getNumArgs), may
+  /// know the called function if it was called through a function pointer,
+  /// and other information not available syntactically.
+  bool matchesImprecise(const CallExpr &CE) const;
+
+private:
+  bool matchesImpl(const FunctionDecl *Callee, size_t ArgCount,
+                   size_t ParamCount) const;
+
+public:
   /// 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...);
   }
   /// @}
 };
 
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 (I.first.matches(Call))
         return &I.second;
 
     return nullptr;
   }
+
+  /// ALWAYS prefer lookup with a CallEvent, when available. See comments above
+  /// CallDescription::matchesImprecise.
+  LLVM_NODISCARD const T *lookupImprecise(const CallExpr &Call) const {
+    // Slow path: linear lookup.
+    // TODO: Implement some sort of fast path.
+    for (const std::pair<CallDescription, T> &I : LinearMap)
+      if (I.first.matchesImprecise(Call))
+        return &I.second;
+
+    return nullptr;
+  }
 };
 
 /// An immutable set of CallDescriptions.
 /// Checkers can efficiently decide if a given CallEvent matches any
 /// CallDescription in the set.
 class CallDescriptionSet {
   CallDescriptionMap<bool /*unused*/> Impl = {};
 
 public:
   CallDescriptionSet(std::initializer_list<CallDescription> &&List);
 
   CallDescriptionSet(const CallDescriptionSet &) = delete;
   CallDescriptionSet &operator=(const CallDescription &) = delete;
 
   LLVM_NODISCARD bool contains(const CallEvent &Call) const;
+  LLVM_NODISCARD bool containsImprecise(const CallExpr &CE) const;
 };
 
 } // namespace ento
 } // namespace clang
 
 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CALLDESCRIPTION_H

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/AST/Decl.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"
 #include <iterator>
 
 using namespace llvm;
 using namespace clang;
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;
 
+  return matchesImpl(FD, Call.getNumArgs(), Call.parameters().size());
+}
+
+bool ento::CallDescription::matchesImprecise(const CallExpr &CE) const {
+  const auto *FD = dyn_cast_or_null<FunctionDecl>(CE.getCalleeDecl());
+  if (!FD)
+    return false;
+
+  return matchesImpl(FD, CE.getNumArgs(), FD->param_size());
+}
+
+bool ento::CallDescription::matchesImpl(const FunctionDecl *Callee,
+                                        size_t ArgCount,
+                                        size_t ParamCount) const {
+  const auto *FD = Callee;
+  if (!FD)
+    return false;
+
   if (Flags & CDF_MaybeBuiltin) {
     return CheckerContext::isCLibraryFunction(FD, getFunctionName()) &&
-           (!RequiredArgs || *RequiredArgs <= Call.getNumArgs()) &&
-           (!RequiredParams || *RequiredParams <= Call.parameters().size());
+           (!RequiredArgs || *RequiredArgs <= ArgCount) &&
+           (!RequiredParams || *RequiredParams <= ParamCount);
   }
 
   if (!II.hasValue()) {
-    II = &Call.getState()->getStateManager().getContext().Idents.get(
-        getFunctionName());
+    II = &FD->getASTContext().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();
+      [](size_t ArgCount, size_t ParamCount,
+         const CallDescription &CD) -> bool {
+    const bool ArgsMatch = !CD.RequiredArgs || *CD.RequiredArgs == ArgCount;
     const bool ParamsMatch =
-        !CD.RequiredParams || *CD.RequiredParams == Call.parameters().size();
+        !CD.RequiredParams || *CD.RequiredParams == ParamCount;
     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))
for (; Ctx && QualifierPartsIt != QualifierPartsEndIt;
       ++QualifierPartsIt;
     }
 
     // We matched if we consumed all expected qualifier segments.
     return QualifierPartsIt == QualifierPartsEndIt;
   };
 
   // Let's start matching...
-  if (!ExactMatchArgAndParamCounts(Call, *this))
+  if (!ExactMatchArgAndParamCounts(ArgCount, ParamCount, *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));
 }
+
+bool ento::CallDescriptionSet::containsImprecise(const CallExpr &CE) const {
+  return static_cast<bool>(Impl.lookupImprecise(CE));
+}

clang/unittests/StaticAnalyzer/CallDescriptionTest.cpp

 //===- unittests/StaticAnalyzer/CallDescriptionTest.cpp -------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
+#include "CheckerRegistration.h"
 #include "Reusables.h"
 
 #include "clang/AST/ExprCXX.h"
+#include "clang/Analysis/PathDiagnostic.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Frontend/AnalysisConsumer.h"
+#include "clang/StaticAnalyzer/Frontend/CheckerRegistry.h"
 #include "clang/Tooling/Tooling.h"
 #include "gtest/gtest.h"
 #include <type_traits>
 
 namespace clang {
 namespace ento {
 namespace {
 
ResultMap(std::initializer_list<std::pair<CallDescription, bool>> Data)
                             })),
         Impl(std::move(Data)) {}
 
   const bool *lookup(const CallEvent &Call) {
     const bool *Result = Impl.lookup(Call);
     // If it's a function we expected to find, remember that we've found it.
     if (Result && *Result)
       ++Found;
+
     return Result;
   }
 
   // Fail the test if we haven't found all the true-calls we were looking for.
   ~ResultMap() { EXPECT_EQ(Found, Total); }
 };
 
 // Scan the code body for call expressions and see if we find all calls that
EXPECT_TRUE(tooling::runToolOnCode(
           {{{"memset", 3}, false}, {{CDF_MaybeBuiltin, "memset", 3}, true}})),
       "void foo() {"
       "  int x;"
       "  __builtin___memset_chk(&x, 0, sizeof(x),"
       "                         __builtin_object_size(&x, 0));"
       "}"));
 }
 
+//===----------------------------------------------------------------------===//
+// Testing through a checker interface.
+//
+// Above, the static analyzer isn't run properly, only the bare minimum to
+// create CallEvents. This causes CallEvents through function pointers to not
+// refer to the pointee function, but this works fine if we run
+// AnalysisASTConsumer.
+//===----------------------------------------------------------------------===//
+
+class CallDescChecker
+    : public Checker<check::PreCall, check::PreStmt<CallExpr>> {
+  CallDescriptionSet Set = {{"bar", 0}};
+
+public:
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const {
+    if (Set.contains(Call)) {
+      C.getBugReporter().EmitBasicReport(
+          Call.getDecl(), this, "CallEvent match", categories::LogicError,
+          "CallEvent match",
+          PathDiagnosticLocation{Call.getDecl(), C.getSourceManager()});
+    }
+  }
+
+  void checkPreStmt(const CallExpr *CE, CheckerContext &C) const {
+    if (Set.containsImprecise(*CE)) {
+      C.getBugReporter().EmitBasicReport(
+          CE->getCalleeDecl(), this, "CallExpr match", categories::LogicError,
+          "CallExpr match",
+          PathDiagnosticLocation{CE->getCalleeDecl(), C.getSourceManager()});
+    }
+  }
+};
+
+void addCallDescChecker(AnalysisASTConsumer &AnalysisConsumer,
+                        AnalyzerOptions &AnOpts) {
+  AnOpts.CheckersAndPackages = {{"test.CallDescChecker", true}};
+  AnalysisConsumer.AddCheckerRegistrationFn([](CheckerRegistry &Registry) {
+    Registry.addChecker<CallDescChecker>("test.CallDescChecker", "Description",
+                                         "");
+  });
+}
+
+TEST(CallDescription, CheckCallExprMatching) {
+  // Imprecise matching shouldn't catch the call to bar, because its obscured
+  // by a function pointer.
+  constexpr StringRef FnPtrCode = R"code(
+    void bar();
+    void foo() {
+      void (*fnptr)() = bar;
+      fnptr();
+    })code";
+  std::string Diags;
+  EXPECT_TRUE(runCheckerOnCode<addCallDescChecker>(FnPtrCode.str(), Diags,
+                                                   /*OnlyEmitWarnings*/ true));
+  EXPECT_EQ("test.CallDescChecker: CallEvent match\n", Diags);
+
+  // This should be caught properly by imprecise matching, as the call is done
+  // purely through syntactic means.
+  constexpr StringRef Code = R"code(
+    void bar();
+    void foo() {
+      bar();
+    })code";
+  Diags.clear();
+  EXPECT_TRUE(runCheckerOnCode<addCallDescChecker>(Code.str(), Diags,
+                                                   /*OnlyEmitWarnings*/ true));
+  EXPECT_EQ("test.CallDescChecker: CallEvent match\n"
+            "test.CallDescChecker: CallExpr match\n",
+            Diags);
+}
+
 } // namespace
 } // namespace ento
 } // namespace clang