[clang][dataflow] Generalise match switch utility to other AST types and add a `CFGMatchSwitch` which currently handles `CFGStmt` and `CFGInitializer`.

[wyt]

Summary

MatchSwitch currently takes in matchers and functions for the Stmt class.

This patch generalises the match switch utility (renamed to ASTMatchSwitch) to work for different AST node types by introducing a template argument which is the base type for the AST nodes that the match switch will handle.

A CFGMatchSwitch is introduced as a wrapper around multiple ASTMatchSwitchs for different base types. It works by unwrapping CFGElements into their contained AST nodes and passing the nodes to the relevant ASTMatchSwitch. The CFGMatchSwitch currently only handles CFGStmt and CFGInitializer.

Depends On D131614

[gribozavr2]

LGTM so far, please finish the patch and tests.

[wyt]

Move implementation to CFGMatchSwitch.h, add tests.

[wyt]

Propagate change from parent patch.

[wyt]

Fix incorrect change.

[gribozavr2]

clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h

54–55

68–69

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

97–98

Can we keep doing this?

109

Ditto.

clang/unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.cpp

35–36

[wyt]

Address comments.

[wyt]

Rebase.

[sgatev]

clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h

25–26

These seem unnecessary.

29

This seems unnecessary.

31

This seems unnecessary.

33

This seems unnecessary.

56

Is the outer move necessary? Also, aren't we supposed to assign the result back to StmtBuilder? Same comment for InitBuilder below.

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

1

Let's add a FIXME to rename the file to ASTMatchSwitch.h and update the comment below.

51–64

What do you think about calling these MatchSwitchMatcher and MatchSwitchAction?

69

95–100

Let's add a static assert.

95–100

clang/unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.cpp

13

This seems unnecessary.

15–16

These seem unnecessary.

21–25

These seem unnecessary.

[wyt]

Address comments.

clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h

56

Is the outer move necessary? Also, aren't we supposed to assign the result back to StmtBuilder? Same comment for InitBuilder below.

Yeap the outer move was unnecessary.
The self-assignment wasn't necessary since the CaseOf modifies the object it is called on, in fact the self-assignment led to the destroyal of contents inside the builder.

[wyt]

Fix comments for consistency.

[wyt]

Use u suffix to declare constants as unsigned in CFGMatchSwitchTest.cpp.

clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h

+//===---- CFGMatchSwitch.h --------------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the `CFGMatchSwitch` abstraction for building a "switch"
+//  statement for control flow graph elements. Each case of the switch is
+//  defined by an ASTMatcher which is applied on the AST node contained in the
+//  input `CFGElement`.
+//
+//  Currently, the `CFGMatchSwitch` only handles `CFGElement`s of
+//  `Kind::Statement` and `Kind::Initializer`.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CFGMATCHSWITCH_H_
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CFGMATCHSWITCH_H_
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/MatchSwitch.h"
+#include <functional>
+#include <utility>
+
+namespace clang {
+namespace dataflow {
+
+template <typename State, typename Result = void>
+using CFGMatchSwitch =
+    std::function<Result(const CFGElement &, ASTContext &, State &)>;
+
+/// Collects cases of a "match switch": a collection of matchers paired with
+/// callbacks, which together define a switch that can be applied to an AST node
+/// contained in a CFG element.
+template <typename State, typename Result = void> class CFGMatchSwitchBuilder {
+public:
+  /// Registers an action `A` for `CFGStmt`s that will be triggered by the match
+  /// of the pattern `M` against the `Stmt` contained in the input `CFGStmt`.
+  ///
+  /// Requirements:
+  ///
+  ///  `NodeT` should be derived from `Stmt`.
+  template <typename NodeT>
+  CFGMatchSwitchBuilder &&
+  CaseOfCFGStmt(MatchSwitchMatcher<Stmt> M,
+                MatchSwitchAction<NodeT, State, Result> A) && {
+    std::move(StmtBuilder).template CaseOf<NodeT>(M, A);
+    return std::move(*this);
+  }
+
+  /// Registers an action `A` for `CFGInitializer`s that will be triggered by
+  /// the match of the pattern `M` against the `CXXCtorInitializer` contained in
+  /// the input `CFGInitializer`.
+  ///
+  /// Requirements:
+  ///
+  ///  `NodeT` should be derived from `CXXCtorInitializer`.
+  template <typename NodeT>
+  CFGMatchSwitchBuilder &&
+  CaseOfCFGInit(MatchSwitchMatcher<CXXCtorInitializer> M,
+                MatchSwitchAction<NodeT, State, Result> A) && {
+    std::move(InitBuilder).template CaseOf<NodeT>(M, A);
+    return std::move(*this);
+  }
+
+  CFGMatchSwitch<State, Result> Build() && {
+    return [StmtMS = std::move(StmtBuilder).Build(),
+            InitMS = std::move(InitBuilder).Build()](const CFGElement &Element,
+                                                     ASTContext &Context,
+                                                     State &S) -> Result {
+      switch (Element.getKind()) {
+      case CFGElement::Initializer:
+        return InitMS(*Element.castAs<CFGInitializer>().getInitializer(),
+                      Context, S);
+      case CFGElement::Statement:
+      case CFGElement::Constructor:
+      case CFGElement::CXXRecordTypedCall:
+        return StmtMS(*Element.castAs<CFGStmt>().getStmt(), Context, S);
+      default:
+        // FIXME: Handle other kinds of CFGElement.
+        return Result();
+      }
+    };
+  }
+
+private:
+  ASTMatchSwitchBuilder<Stmt, State, Result> StmtBuilder;
+  ASTMatchSwitchBuilder<CXXCtorInitializer, State, Result> InitBuilder;
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CFGMATCHSWITCH_H_

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

 //===---- MatchSwitch.h -----------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines the `MatchSwitch` abstraction for building a "switch"
 //  statement, where each case of the switch is defined by an AST matcher. The
 //  cases are considered in order, like pattern matching in functional
 //  languages.
 //
 //  Currently, the design is catered towards simplifying the implementation of
 //  `DataflowAnalysis` transfer functions. Based on experience here, this
 //  library may be generalized and moved to ASTMatchers.
 //
 //===----------------------------------------------------------------------===//
+//
+// FIXME: Rename to ASTMatchSwitch.h and update documentation when all usages of
+// `MatchSwitch` are updated to `ASTMatchSwitch<Stmt>`
 
 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_
 
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Stmt.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "llvm/ADT/StringRef.h"
 #include <functional>
 #include <string>
+#include <type_traits>
 #include <utility>
 #include <vector>
 
 namespace clang {
 namespace dataflow {
 
 /// A common form of state shared between the cases of a transfer function.
 template <typename LatticeT> struct TransferState {
   TransferState(LatticeT &Lattice, Environment &Env)
       : Lattice(Lattice), Env(Env) {}
 
   /// Current lattice element.
   LatticeT &Lattice;
   Environment &Env;
 };
 
-/// Matches against `Stmt` and, based on its structure, dispatches to an
-/// appropriate handler.
+template <typename T>
+using MatchSwitchMatcher = ast_matchers::internal::Matcher<T>;
+
+template <typename T, typename State, typename Result = void>
+using MatchSwitchAction = std::function<Result(
+    const T *, const ast_matchers::MatchFinder::MatchResult &, State &)>;
+
+template <typename BaseT, typename State, typename Result = void>
+using ASTMatchSwitch =
+    std::function<Result(const BaseT &, ASTContext &, State &)>;
+
+// FIXME: Remove this alias when all usages of `MatchSwitch` are updated to
+// `ASTMatchSwitch<Stmt>`.
 template <typename State, typename Result = void>
-using MatchSwitch = std::function<Result(const Stmt &, ASTContext &, State &)>;
+using MatchSwitch = ASTMatchSwitch<Stmt, State, Result>;
 
 /// Collects cases of a "match switch": a collection of matchers paired with
-/// callbacks, which together define a switch that can be applied to a
-/// `Stmt`. This structure can simplify the definition of `transfer` functions
-/// that rely on pattern-matching.
+/// callbacks, which together define a switch that can be applied to a node
+/// whose type derives from `BaseT`. This structure can simplify the definition
+/// of `transfer` functions that rely on pattern-matching.
 ///
 /// For example, consider an analysis that handles particular function calls. It
-/// can define the `MatchSwitch` once, in the constructor of the analysis, and
-/// then reuse it each time that `transfer` is called, with a fresh state value.
+/// can define the `ASTMatchSwitch` once, in the constructor of the analysis,
+/// and then reuse it each time that `transfer` is called, with a fresh state
+/// value.
 ///
 /// \code
-/// MatchSwitch<TransferState<MyLattice> BuildSwitch() {
-///   return MatchSwitchBuilder<TransferState<MyLattice>>()
+/// ASTMatchSwitch<Stmt, TransferState<MyLattice> BuildSwitch() {
+///   return ASTMatchSwitchBuilder<TransferState<MyLattice>>()
 ///     .CaseOf(callExpr(callee(functionDecl(hasName("foo")))), TransferFooCall)
 ///     .CaseOf(callExpr(argumentCountIs(2),
 ///                      callee(functionDecl(hasName("bar")))),
 ///             TransferBarCall)
 ///     .Build();
 /// }
 /// \endcode
-template <typename State, typename Result = void> class MatchSwitchBuilder {
+template <typename BaseT, typename State, typename Result = void>
+class ASTMatchSwitchBuilder {
 public:
   /// Registers an action that will be triggered by the match of a pattern
   /// against the input statement.
   ///
   /// Requirements:
   ///
-  ///  `Node` should be a subclass of `Stmt`.
-  template <typename Node>
-  MatchSwitchBuilder &&
-  CaseOf(ast_matchers::internal::Matcher<Stmt> M,
-         std::function<Result(const Node *,
-                              const ast_matchers::MatchFinder::MatchResult &,
-                              State &)>
-             A) && {
+  ///  `NodeT` should be derived from `BaseT`.
+  template <typename NodeT>
+  ASTMatchSwitchBuilder &&CaseOf(MatchSwitchMatcher<BaseT> M,
+                                 MatchSwitchAction<NodeT, State, Result> A) && {
+    static_assert(std::is_base_of<BaseT, NodeT>::value,
+                  "NodeT must be derived from BaseT.");
     Matchers.push_back(std::move(M));
     Actions.push_back(
-        [A = std::move(A)](const Stmt *Stmt,
+        [A = std::move(A)](const BaseT *Node,
                            const ast_matchers::MatchFinder::MatchResult &R,
-                           State &S) { return A(cast<Node>(Stmt), R, S); });
+                           State &S) { return A(cast<NodeT>(Node), R, S); });
     return std::move(*this);
   }
 
-  MatchSwitch<State, Result> Build() && {
+  ASTMatchSwitch<BaseT, State, Result> Build() && {
     return [Matcher = BuildMatcher(), Actions = std::move(Actions)](
-               const Stmt &Stmt, ASTContext &Context, State &S) -> Result {
-      auto Results = ast_matchers::matchDynamic(Matcher, Stmt, Context);
-      if (Results.empty())
+               const BaseT &Node, ASTContext &Context, State &S) -> Result {
+      auto Results = ast_matchers::matchDynamic(Matcher, Node, Context);
+      if (Results.empty()) {
         return Result();
+      }
       // Look through the map for the first binding of the form "TagN..." use
       // that to select the action.
       for (const auto &Element : Results[0].getMap()) {
         llvm::StringRef ID(Element.first);
         size_t Index = 0;
         if (ID.consume_front("Tag") && !ID.getAsInteger(10, Index) &&
             Index < Actions.size()) {
           return Actions[Index](
-              &Stmt,
+              &Node,
               ast_matchers::MatchFinder::MatchResult(Results[0], &Context), S);
         }
       }
       return Result();
     };
   }
 
 private:
for (int I = 0, N = Matchers.size(); I < N; ++I) {
       // the kind is already set, or explicitly set to `TK_AsIs`. We choose this
       // setting because it is the default interpretation of matchers.
       Matchers[I] =
           !M.getTraversalKind() ? M.withTraversalKind(TK_AsIs) : std::move(M);
     }
     // The matcher type on the cases ensures that `Expr` kind is compatible with
     // all of the matchers.
     return DynTypedMatcher::constructVariadic(
-        DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind<Stmt>(),
+        DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind<BaseT>(),
         std::move(Matchers));
   }
 
   std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
-  std::vector<std::function<Result(
-      const Stmt *, const ast_matchers::MatchFinder::MatchResult &, State &)>>
-      Actions;
+  std::vector<MatchSwitchAction<BaseT, State, Result>> Actions;
 };
+
+// FIXME: Remove this alias when all usages of `MatchSwitchBuilder` are updated
+// to `ASTMatchSwitchBuilder<Stmt>`.
+template <typename State, typename Result = void>
+using MatchSwitchBuilder = ASTMatchSwitchBuilder<Stmt, State, Result>;
+
 } // namespace dataflow
 } // namespace clang
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_

clang/unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.cpp

+//===- unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.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 "clang/Analysis/FlowSensitive/CFGMatchSwitch.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/StringRef.h"
+#include "gtest/gtest.h"
+
+using namespace clang;
+using namespace dataflow;
+using namespace ast_matchers;
+
+namespace {
+// State for tracking the number of matches on each kind of CFGElement by the
+// CFGMatchSwitch. Currently only tracks CFGStmt and CFGInitializer.
+struct CFGElementMatches {
+  unsigned StmtMatches = 0;
+  unsigned InitializerMatches = 0;
+};
+
+// Returns a match switch that counts the number of local variables
+// (singly-declared) and fields initialized to the integer literal 42.
+auto buildCFGMatchSwitch() {
+  return CFGMatchSwitchBuilder<CFGElementMatches>()
+      .CaseOfCFGStmt<DeclStmt>(
+          declStmt(hasSingleDecl(
+              varDecl(hasInitializer(integerLiteral(equals(42)))))),
+          [](const DeclStmt *, const MatchFinder::MatchResult &,
+             CFGElementMatches &Counter) { Counter.StmtMatches++; })
+      .CaseOfCFGInit<CXXCtorInitializer>(
+          cxxCtorInitializer(withInitializer(integerLiteral(equals(42)))),
+          [](const CXXCtorInitializer *, const MatchFinder::MatchResult &,
+             CFGElementMatches &Counter) { Counter.InitializerMatches++; })
+      .Build();
+}
+
+// Runs the match switch `MS` on the control flow graph generated from `Code`,
+// tracking information in state `S`. For simplicity, this test utility is
+// restricted to CFGs with a single control flow block (excluding entry and
+// exit blocks) - generated by `Code` with sequential flow (i.e. no branching).
+//
+// Requirements:
+//
+//  `Code` must contain a function named `f`, the body of this function will be
+//  used to generate the CFG.
+template <typename State>
+void applySwitchToCode(CFGMatchSwitch<State> &MS, State &S,
+                       llvm::StringRef Code) {
+  auto Unit = tooling::buildASTFromCodeWithArgs(Code, {"-Wno-unused-value"});
+  auto &Ctx = Unit->getASTContext();
+  const auto *F = selectFirst<FunctionDecl>(
+      "f", match(functionDecl(isDefinition(), hasName("f")).bind("f"), Ctx));
+
+  CFG::BuildOptions BO;
+  BO.AddInitializers = true;
+
+  auto CFG = CFG::buildCFG(F, F->getBody(), &Ctx, BO);
+  auto CFGBlock = *CFG->getEntry().succ_begin();
+  for (auto &Elt : CFGBlock->Elements) {
+    MS(Elt, Ctx, S);
+  }
+}
+
+TEST(CFGMatchSwitchTest, NoInitializationTo42) {
+  CFGMatchSwitch<CFGElementMatches> Switch = buildCFGMatchSwitch();
+  CFGElementMatches Counter;
+  applySwitchToCode(Switch, Counter, R"(
+    void f() {
+      42;
+    }
+  )");
+  EXPECT_EQ(Counter.StmtMatches, 0u);
+  EXPECT_EQ(Counter.InitializerMatches, 0u);
+}
+
+TEST(CFGMatchSwitchTest, SingleLocalVarInitializationTo42) {
+  CFGMatchSwitch<CFGElementMatches> Switch = buildCFGMatchSwitch();
+  CFGElementMatches Counter;
+  applySwitchToCode(Switch, Counter, R"(
+    void f() {
+      int i = 42;
+    }
+  )");
+  EXPECT_EQ(Counter.StmtMatches, 1u);
+  EXPECT_EQ(Counter.InitializerMatches, 0u);
+}
+
+TEST(CFGMatchSwitchTest, SingleFieldInitializationTo42) {
+  CFGMatchSwitch<CFGElementMatches> Switch = buildCFGMatchSwitch();
+  CFGElementMatches Counter;
+  applySwitchToCode(Switch, Counter, R"(
+    struct f {
+      int i;
+      f(): i(42) {}
+    };
+  )");
+  EXPECT_EQ(Counter.StmtMatches, 0u);
+  EXPECT_EQ(Counter.InitializerMatches, 1u);
+}
+
+TEST(CFGMatchSwitchTest, LocalVarAndFieldInitializationTo42) {
+  CFGMatchSwitch<CFGElementMatches> Switch = buildCFGMatchSwitch();
+  CFGElementMatches Counter;
+  applySwitchToCode(Switch, Counter, R"(
+    struct f {
+      int i;
+      f(): i(42) {
+        int j = 42;
+      }
+    };
+  )");
+  EXPECT_EQ(Counter.StmtMatches, 1u);
+  EXPECT_EQ(Counter.InitializerMatches, 1u);
+}
+} // namespace

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(ClangAnalysisFlowSensitiveTests
+  CFGMatchSwitchTest.cpp
   ChromiumCheckModelTest.cpp
   DataflowAnalysisContextTest.cpp
   DataflowEnvironmentTest.cpp
   DebugSupportTest.cpp
   MapLatticeTest.cpp
   MatchSwitchTest.cpp
   MultiVarConstantPropagationTest.cpp
   SingleVarConstantPropagationTest.cpp

clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp

 //===- unittests/Analysis/FlowSensitive/MatchSwitchTest.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
 //
 //===----------------------------------------------------------------------===//
-//
-//  This file defines a simplistic version of Constant Propagation as an example
-//  of a forward, monotonic dataflow analysis. The analysis tracks all
-//  variables in the scope, but lacks escape analysis.
-//
-//===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/FlowSensitive/MatchSwitch.h"
 #include "TestingSupport.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/Stmt.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"