[analyzer] NFC: Introduce a convenient CallDescriptionMap class.

[NoQ]

Summary

"When choosing a container, remember vector is best;
Leave a comment to explain if you choose from the rest!"

-Tony Van Eerd, Postmodern C++.

CallDescriptionMap would encapsulate the procedure of figuring out if any of the supported CallDescriptions apply to a given CallEvent. Without such facility i constantly worry about somebody bashing me on reviews for using slow string switches and stuff. However when a CallDescription isn't a simple string, a linear lookup is almost unavoidable. So even though for now i only implement a linear lookup, i guess with a single interface we can later afford a string-map optimization specifically for simple CallDescriptions.

I also add a few unittests for CallDescription with the help of this class.

[NoQ]

Bring back an assertion in findNode<>().

[Szelethus]

This is why I love unit tests so much, you get the learn a lot about how things work! Thanks!

The idea for the patch is great, can't wait to get rid of the mess we have in MallocChecker.

[xazax.hun]

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

1088 ↗

(On Diff #201382)

Will the move constructor work as intended with const members?

1097 ↗

(On Diff #201382)

I think in this case copy assignment should also be deleted. Or is it deleted automatically in this case?

[NoQ]

Indeed. Subtle!

[Charusso]

Great patch, thanks you! I wanted to make my own IdentifierInfo array previously.

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

1060 ↗

(On Diff #206951)

What about Optional<>? When I first met that function I have fallen in love.

clang/unittests/StaticAnalyzer/CallDescriptionTest.cpp

72 ↗

(On Diff #206951)

May it worth to mention the second true/false business stands for the call being called.

103 ↗

(On Diff #206951)

So {{"bar", "foo"}, true}? I like puzzles, but it would be cool to state out why it is negative as other tests all have negative sub-tests.

[NoQ]

Address comments.

Improve the tests so that they failed when not all requested functions were found - it's pretty crude as it only checks that the number of hits is correct, but, i guess, that's what you get when you're trying to write unittests for an intentionally constrained interface.

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

1060 ↗

(On Diff #206951)

I didn't really touch this code, just moved it around, but it's definitely a valid point.

clang/unittests/StaticAnalyzer/CallDescriptionTest.cpp

103 ↗

(On Diff #206951)

{{"bar", "foo"}, false}!

Nice catch tho, typo.

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

enum CallEventKind {
   CE_CXXAllocator,
   CE_BEG_FUNCTION_CALLS = CE_Function,
   CE_END_FUNCTION_CALLS = CE_CXXAllocator,
   CE_Block,
   CE_ObjCMessage
 };
 
 class CallEvent;
-
-/// 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;
-  // 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;
-  unsigned RequiredArgs;
-
-public:
-  const static unsigned NoArgRequirement = std::numeric_limits<unsigned>::max();
-
-  /// Constructs a CallDescription object.
-  ///
-  /// @param QualifiedName The list of the name qualifiers of the function that
-  /// will be matched. The user is allowed to skip any of the qualifiers.
-  /// For example, {"std", "basic_string", "c_str"} would match both
-  /// std::basic_string<...>::c_str() and std::__1::basic_string<...>::c_str().
-  ///
-  /// @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(ArrayRef<const char *> QualifiedName,
-                  unsigned RequiredArgs = NoArgRequirement)
-      : QualifiedName(QualifiedName), RequiredArgs(RequiredArgs) {}
-
-  /// Get the name of the function that this object matches.
-  StringRef getFunctionName() const { return QualifiedName.back(); }
-};
+class CallDescription;
 
 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) {}
 
   CallEventRef<T> cloneWithState(ProgramStateRef State) const {
public:
 
   Kind getKind() const override { return CE_ObjCMessage; }
 
   static bool classof(const CallEvent *CA) {
     return CA->getKind() == CE_ObjCMessage;
   }
 };
 
+/// 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;
+  // 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;
+
+public:
+  /// Constructs a CallDescription object.
+  ///
+  /// @param QualifiedName The list of the name qualifiers of the function that
+  /// will be matched. The user is allowed to skip any of the qualifiers.
+  /// For example, {"std", "basic_string", "c_str"} would match both
+  /// std::basic_string<...>::c_str() and std::__1::basic_string<...>::c_str().
+  ///
+  /// @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(ArrayRef<const char *> QualifiedName,
+                  Optional<unsigned> RequiredArgs = None)
+      : QualifiedName(QualifiedName), RequiredArgs(RequiredArgs) {}
+
+  /// Get the name of the function that this object matches.
+  StringRef getFunctionName() const { return QualifiedName.back(); }
+};
+
+/// 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.
+  // TODO: Implement an actual map for fast lookup for "hashable" call
+  // descriptions (eg., the ones for C functions that just match the name).
+  std::vector<std::pair<CallDescription, T>> LinearMap;
+
+public:
+  CallDescriptionMap(
+      std::initializer_list<std::pair<CallDescription, T>> &&List)
+      : LinearMap(List) {}
+
+  ~CallDescriptionMap() = default;
+
+  // These maps are usually stored once per checker, so let's make sure
+  // we don't do redundant copies.
+  CallDescriptionMap(const CallDescriptionMap &) = delete;
+  CallDescriptionMap &operator=(const CallDescription &) = delete;
+
+  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))
+        return &I.second;
+
+    return nullptr;
+  }
+};
+
 /// Manages the lifetime of CallEvent objects.
 ///
 /// CallEventManager provides a way to create arbitrary CallEvents "on the
 /// stack" as if they were value objects by keeping a cache of CallEvent-sized
 /// memory blocks. The CallEvents created by CallEventManager are only valid
 /// for the lifetime of the OwnedCallEvent that holds them; right now these
 /// objects cannot be copied and ownership cannot be transferred.
 class CallEventManager {

cfe/trunk/lib/StaticAnalyzer/Core/CallEvent.cpp

for (; Ctx && isa<NamedDecl>(Ctx); Ctx = Ctx->getParent()) {
         continue;
       }
     }
 
     if (NumUnmatched > 0)
       return false;
   }
 
-  return (CD.RequiredArgs == CallDescription::NoArgRequirement ||
-          CD.RequiredArgs == getNumArgs());
+  return (!CD.RequiredArgs || CD.RequiredArgs == getNumArgs());
 }
 
 SVal CallEvent::getArgSVal(unsigned Index) const {
   const Expr *ArgE = getArgExpr(Index);
   if (!ArgE)
     return UnknownVal();
   return getSVal(ArgE);
 }

cfe/trunk/unittests/StaticAnalyzer/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_unittest(StaticAnalysisTests
   AnalyzerOptionsTest.cpp
+  CallDescriptionTest.cpp
   StoreTest.cpp
   RegisterCustomCheckersTest.cpp
   SymbolReaperTest.cpp
   )
 
 target_link_libraries(StaticAnalysisTests
   PRIVATE
   clangBasic

cfe/trunk/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 "Reusables.h"
+
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace ento {
+namespace {
+
+// A wrapper around CallDescriptionMap<bool> that allows verifying that
+// all functions have been found. This is needed because CallDescriptionMap
+// isn't supposed to support iteration.
+class ResultMap {
+  size_t Found, Total;
+  CallDescriptionMap<bool> Impl;
+
+public:
+  ResultMap(std::initializer_list<std::pair<CallDescription, bool>> Data)
+      : Found(0),
+        Total(std::count_if(Data.begin(), Data.end(),
+                            [](const std::pair<CallDescription, bool> &Pair) {
+                              return Pair.second == true;
+                            })),
+        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
+// we were supposed to find ("true" in the provided ResultMap) and that we
+// don't find the ones that we weren't supposed to find
+// ("false" in the ResultMap).
+class CallDescriptionConsumer : public ExprEngineConsumer {
+  ResultMap &RM;
+  void performTest(const Decl *D) {
+    using namespace ast_matchers;
+
+    if (!D->hasBody())
+      return;
+
+    const CallExpr *CE = findNode<CallExpr>(D, callExpr());
+    const StackFrameContext *SFC =
+        Eng.getAnalysisDeclContextManager().getStackFrame(D);
+    ProgramStateRef State = Eng.getInitialState(SFC);
+    CallEventRef<> Call =
+        Eng.getStateManager().getCallEventManager().getCall(CE, State, SFC);
+
+    const bool *LookupResult = RM.lookup(*Call);
+    // Check that we've found the function in the map
+    // with the correct description.
+    EXPECT_TRUE(LookupResult && *LookupResult);
+
+    // ResultMap is responsible for making sure that we've found *all* calls.
+  }
+
+public:
+  CallDescriptionConsumer(CompilerInstance &C,
+                          ResultMap &RM)
+      : ExprEngineConsumer(C), RM(RM) {}
+
+  bool HandleTopLevelDecl(DeclGroupRef DG) override {
+    for (const auto *D : DG)
+      performTest(D);
+    return true;
+  }
+};
+
+class CallDescriptionAction : public ASTFrontendAction {
+  ResultMap RM;
+
+public:
+  CallDescriptionAction(
+      std::initializer_list<std::pair<CallDescription, bool>> Data)
+      : RM(Data) {}
+
+  std::unique_ptr<ASTConsumer> CreateASTConsumer(CompilerInstance &Compiler,
+                                                 StringRef File) override {
+    return llvm::make_unique<CallDescriptionConsumer>(Compiler, RM);
+  }
+};
+
+TEST(CallEvent, CallDescription) {
+  // Test simple name matching.
+  EXPECT_TRUE(tooling::runToolOnCode(
+      new CallDescriptionAction({
+          {{"bar"}, false}, // false: there's no call to 'bar' in this code.
+          {{"foo"}, true},  // true: there's a call to 'foo' in this code.
+      }), "void foo(); void bar() { foo(); }"));
+
+  // Test arguments check.
+  EXPECT_TRUE(tooling::runToolOnCode(
+      new CallDescriptionAction({
+          {{"foo", 1}, true},
+          {{"foo", 2}, false},
+      }), "void foo(int); void foo(int, int); void bar() { foo(1); }"));
+
+  // Test lack of arguments check.
+  EXPECT_TRUE(tooling::runToolOnCode(
+      new CallDescriptionAction({
+          {{"foo", None}, true},
+          {{"foo", 2}, false},
+      }), "void foo(int); void foo(int, int); void bar() { foo(1); }"));
+
+  // Test qualified names.
+  EXPECT_TRUE(tooling::runToolOnCode(
+      new CallDescriptionAction({
+          {{{"std", "basic_string", "c_str"}}, true},
+      }),
+      "namespace std { inline namespace __1 {"
+      "  template<typename T> class basic_string {"
+      "  public:"
+      "    T *c_str();"
+      "  };"
+      "}}"
+      "void foo() {"
+      "  using namespace std;"
+      "  basic_string<char> s;"
+      "  s.c_str();"
+      "}"));
+
+  // A negative test for qualified names.
+  EXPECT_TRUE(tooling::runToolOnCode(
+      new CallDescriptionAction({
+          {{{"foo", "bar"}}, false},
+          {{{"bar", "foo"}}, false},
+          {{"foo"}, true},
+      }), "void foo(); struct bar { void foo(); }; void test() { foo(); }"));
+}
+
+} // namespace
+} // namespace ento
+} // namespace clang

cfe/trunk/unittests/StaticAnalyzer/Reusables.h

 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/CrossTU/CrossTranslationUnit.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
 
 namespace clang {
 namespace ento {
 
+// Find a node in the current AST that matches a matcher.
+template <typename T, typename MatcherT>
+const T *findNode(const Decl *Where, MatcherT What) {
+  using namespace ast_matchers;
+  auto Matches = match(decl(hasDescendant(What.bind("root"))),
+                       *Where, Where->getASTContext());
+  assert(Matches.size() <= 1 && "Ambiguous match!");
+  assert(Matches.size() >= 1 && "Match not found!");
+  const T *Node = selectFirst<T>("root", Matches);
+  assert(Node && "Type mismatch!");
+  return Node;
+}
+
 // Find a declaration in the current AST by name.
 template <typename T>
 const T *findDeclByName(const Decl *Where, StringRef Name) {
   using namespace ast_matchers;
-  auto Matcher = decl(hasDescendant(namedDecl(hasName(Name)).bind("d")));
-  auto Matches = match(Matcher, *Where, Where->getASTContext());
-  assert(Matches.size() == 1 && "Ambiguous name!");
-  const T *Node = selectFirst<T>("d", Matches);
-  assert(Node && "Name not found!");
-  return Node;
+  return findNode<T>(Where, namedDecl(hasName(Name)));
 }
 
 // A re-usable consumer that constructs ExprEngine out of CompilerInvocation.
 class ExprEngineConsumer : public ASTConsumer {
 protected:
   CompilerInstance &C;
 
 private: