[clang][dataflow] Add `MatchSwitch` utility library.

[ymandel]

Summary

Adds MatchSwitch, a library for simplifying implementation of transfer
functions. MatchSwitch supports constructing 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.

[ymandel]

Adjust tests to use two different handlers.

[xazax.hun]

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

52

When we instantiate this with TransferState we have ASTContext both as an argument and as a member of State. Is this intentional?

111

This does not need to be addressed here but it looks like it could be a useful feature to be able to tag nodes with integer identifiers.

[ymandel]

Thanks for the fast review!

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

52

Yes, but...
The ASTContext is needed for the match itself, but the State type is not guaranteed to be TransferState, so won't necessarily hold the context.

But, we could reorganize a bit. Either:
a) pass MatchFinder::MatchResult, instead of BoundNodes. That would bundle the nodes, context and source manager, which seems like a good idea.
b) bake TransferState into MatchSwitch, and make the parameter genericy named rather than "lattice".

I'm inclined towards the first option, since it seems "right" to give full access to the MatchResult. WDYT?

111

Great point. I'm not sure that would work here, fwiw, because we prefix with "Tag" here to protect against interfering with any IDs in the matcher. I suppose we could "reserve" a portion of the ID space.

But, in general, integers would make more sense in other situations that deal w/ matchers. The problem is that, unless we encode them as strings, the implementation inside the matchers could be kind of messy.

[ymandel]

moved to MatchFinder::MatchResult.

[xazax.hun]

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

52

Option a) sounds good to me, thanks!

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.
+//
+//===----------------------------------------------------------------------===//
+
+#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 <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 State>
+using MatchSwitch = std::function<void(const Stmt &, 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 a
+/// `Stmt`. 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.
+///
+/// \code
+/// MatchSwitch<TransferState<MyLattice> BuildSwitch() {
+///   return MatchSwitchBuilder<TransferState<MyLattice>>()
+///     .CaseOf(callExpr(callee(functionDecl(hasName("foo")))), TransferFooCall)
+///     .CaseOf(callExpr(argumentCountIs(2),
+///                      callee(functionDecl(hasName("bar")))),
+///             TransferBarCall)
+///     .Build();
+/// }
+/// \endcode
+template <typename State> class MatchSwitchBuilder {
+public:
+  // An action is triggered by the match of a pattern against the input
+  // statement. For generality, actions take both the matched statement and the
+  // set of bindings produced by the match.
+  using Action = std::function<void(
+      const Stmt *, const ast_matchers::MatchFinder::MatchResult &, State &)>;
+
+  MatchSwitchBuilder &&CaseOf(ast_matchers::internal::Matcher<Stmt> M,
+                              Action A) && {
+    Matchers.push_back(std::move(M));
+    Actions.push_back(std::move(A));
+    return std::move(*this);
+  }
+
+  // Convenience function for the common case, where bound nodes are not
+  // needed. `Node` should be a subclass of `Stmt`.
+  template <typename Node>
+  MatchSwitchBuilder &&CaseOf(ast_matchers::internal::Matcher<Stmt> M,
+                              void (*Action)(const Node *, State &)) && {
+    Matchers.push_back(std::move(M));
+    Actions.push_back([Action](const Stmt *Stmt,
+                               const ast_matchers::MatchFinder::MatchResult &,
+                               State &S) { Action(cast<Node>(Stmt), S); });
+    return std::move(*this);
+  }
+
+  MatchSwitch<State> Build() && {
+    return [Matcher = BuildMatcher(), Actions = std::move(Actions)](
+               const Stmt &Stmt, ASTContext &Context, State &S) {
+      auto Results = ast_matchers::matchDynamic(Matcher, Stmt, Context);
+      if (Results.empty())
+        return;
+      // 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()) {
+          Actions[Index](
+              &Stmt,
+              ast_matchers::MatchFinder::MatchResult(Results[0], &Context), S);
+          return;
+        }
+      }
+    };
+  }
+
+private:
+  ast_matchers::internal::DynTypedMatcher BuildMatcher() {
+    using ast_matchers::anything;
+    using ast_matchers::stmt;
+    using ast_matchers::unless;
+    using ast_matchers::internal::DynTypedMatcher;
+    if (Matchers.empty())
+      return stmt(unless(anything()));
+    for (int I = 0, N = Matchers.size(); I < N; ++I) {
+      std::string Tag = ("Tag" + llvm::Twine(I)).str();
+      // Many matchers are not bindable, so ensure that tryBind will work.
+      Matchers[I].setAllowBind(true);
+      auto M = *Matchers[I].tryBind(Tag);
+      // Each anyOf explicitly controls the traversal kind. The anyOf itself is
+      // set to `TK_AsIs` to ensure no nodes are skipped, thereby deferring to
+      // the kind of the branches. Then, each branch is either left as is, if
+      // 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>(),
+        std::move(Matchers));
+  }
+
+  std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
+  std::vector<Action> Actions;
+};
+} // namespace dataflow
+} // namespace clang
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(ClangAnalysisFlowSensitiveTests
   DataflowAnalysisContextTest.cpp
   DataflowEnvironmentTest.cpp
   MapLatticeTest.cpp
+  MatchSwitchTest.cpp
   MultiVarConstantPropagationTest.cpp
   SingleVarConstantPropagationTest.cpp
   SourceLocationsLatticeTest.cpp
   TestingSupport.cpp
   TestingSupportTest.cpp
   TransferTest.cpp
   TypeErasedDataflowAnalysisTest.cpp
   SolverTest.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"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "clang/Analysis/FlowSensitive/MapLattice.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Testing/Support/Annotations.h"
+#include "llvm/Testing/Support/Error.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <cstdint>
+#include <memory>
+#include <ostream>
+#include <string>
+#include <utility>
+
+using namespace clang;
+using namespace dataflow;
+
+namespace {
+using ::testing::Pair;
+using ::testing::UnorderedElementsAre;
+
+class BooleanLattice {
+public:
+  BooleanLattice() : Value(false) {}
+  explicit BooleanLattice(bool B) : Value(B) {}
+
+  static BooleanLattice bottom() { return BooleanLattice(false); }
+
+  static BooleanLattice top() { return BooleanLattice(true); }
+
+  LatticeJoinEffect join(BooleanLattice Other) {
+    auto Prev = Value;
+    Value = Value || Other.Value;
+    return Prev == Value ? LatticeJoinEffect::Unchanged
+                         : LatticeJoinEffect::Changed;
+  }
+
+  friend bool operator==(BooleanLattice LHS, BooleanLattice RHS) {
+    return LHS.Value == RHS.Value;
+  }
+
+  friend std::ostream &operator<<(std::ostream &Os, const BooleanLattice &B) {
+    Os << B.Value;
+    return Os;
+  }
+
+  bool value() const { return Value; }
+
+private:
+  bool Value;
+};
+} // namespace
+
+MATCHER_P(Holds, m,
+          ((negation ? "doesn't hold" : "holds") +
+           llvm::StringRef(" a lattice element that ") +
+           ::testing::DescribeMatcher<BooleanLattice>(m, negation))
+              .str()) {
+  return ExplainMatchResult(m, arg.Lattice, result_listener);
+}
+
+void TransferSetTrue(const DeclRefExpr *,
+                     TransferState<BooleanLattice> &State) {
+  State.Lattice = BooleanLattice(true);
+}
+
+void TransferSetFalse(const Stmt *,
+                      const ast_matchers::MatchFinder::MatchResult &,
+                      TransferState<BooleanLattice> &State) {
+  State.Lattice = BooleanLattice(false);
+}
+
+class TestAnalysis : public DataflowAnalysis<TestAnalysis, BooleanLattice> {
+  MatchSwitch<TransferState<BooleanLattice>> TransferSwitch;
+
+public:
+  explicit TestAnalysis(ASTContext &Context)
+      : DataflowAnalysis<TestAnalysis, BooleanLattice>(Context) {
+    using namespace ast_matchers;
+    TransferSwitch =
+        MatchSwitchBuilder<TransferState<BooleanLattice>>()
+            .CaseOf(declRefExpr(to(varDecl(hasName("X")))), TransferSetTrue)
+            .CaseOf(callExpr(callee(functionDecl(hasName("Foo")))),
+                    TransferSetFalse)
+            .Build();
+  }
+
+  static BooleanLattice initialElement() { return BooleanLattice::bottom(); }
+
+  void transfer(const Stmt *S, BooleanLattice &L, Environment &Env) {
+    TransferState<BooleanLattice> State(L, Env);
+    TransferSwitch(*S, getASTContext(), State);
+  }
+};
+
+class MatchSwitchTest : public ::testing::Test {
+protected:
+  template <typename Matcher>
+  void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
+    ASSERT_THAT_ERROR(
+        test::checkDataflow<TestAnalysis>(
+            Code, "fun",
+            [](ASTContext &C, Environment &) { return TestAnalysis(C); },
+            [&Expectations](
+                llvm::ArrayRef<std::pair<
+                    std::string, DataflowAnalysisState<TestAnalysis::Lattice>>>
+                    Results,
+                ASTContext &) { EXPECT_THAT(Results, Expectations); },
+            {"-fsyntax-only", "-std=c++17"}),
+        llvm::Succeeded());
+  }
+};
+
+TEST_F(MatchSwitchTest, JustX) {
+  std::string Code = R"(
+    void fun() {
+      int X = 1;
+      (void)X;
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code,
+              UnorderedElementsAre(Pair("p", Holds(BooleanLattice(true)))));
+}
+
+TEST_F(MatchSwitchTest, JustFoo) {
+  std::string Code = R"(
+    void Foo();
+    void fun() {
+      Foo();
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code,
+              UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false)))));
+}
+
+TEST_F(MatchSwitchTest, XThenFoo) {
+  std::string Code = R"(
+    void Foo();
+    void fun() {
+      int X = 1;
+      (void)X;
+      Foo();
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code,
+              UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false)))));
+}
+
+TEST_F(MatchSwitchTest, FooThenX) {
+  std::string Code = R"(
+    void Foo();
+    void fun() {
+      Foo();
+      int X = 1;
+      (void)X;
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code,
+              UnorderedElementsAre(Pair("p", Holds(BooleanLattice(true)))));
+}
+
+TEST_F(MatchSwitchTest, Neither) {
+  std::string Code = R"(
+    void Bar();
+    void fun(bool b) {
+      Bar();
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code,
+              UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false)))));
+}