Analysis/FlowSensitive/MatchSwitch.h

0001 //===---- MatchSwitch.h -----------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 //  This file defines the `ASTMatchSwitch` abstraction for building a "switch"
0010 //  statement, where each case of the switch is defined by an AST matcher. The
0011 //  cases are considered in order, like pattern matching in functional
0012 //  languages.
0013 //
0014 //  Currently, the design is catered towards simplifying the implementation of
0015 //  `DataflowAnalysis` transfer functions. Based on experience here, this
0016 //  library may be generalized and moved to ASTMatchers.
0017 //
0018 //===----------------------------------------------------------------------===//
0019 //
0020 // FIXME: Rename to ASTMatchSwitch.h
0021
0022 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_
0023 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_
0024
0025 #include "clang/AST/ASTContext.h"
0026 #include "clang/AST/Stmt.h"
0027 #include "clang/ASTMatchers/ASTMatchFinder.h"
0028 #include "clang/ASTMatchers/ASTMatchers.h"
0029 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
0030 #include "llvm/ADT/StringRef.h"
0031 #include <functional>
0032 #include <string>
0033 #include <type_traits>
0034 #include <utility>
0035 #include <vector>
0036
0037 namespace clang {
0038 namespace dataflow {
0039
0040 /// A common form of state shared between the cases of a transfer function.
0041 template <typename LatticeT> struct TransferState {
0042   TransferState(LatticeT &Lattice, Environment &Env)
0043       : Lattice(Lattice), Env(Env) {}
0044
0045   /// Current lattice element.
0046   LatticeT &Lattice;
0047   Environment &Env;
0048 };
0049
0050 /// A read-only version of TransferState.
0051 ///
0052 /// FIXME: this type is being used as a general (typed) view type for untyped
0053 /// dataflow analysis state, rather than strictly for transfer-function
0054 /// purposes. Move it (and rename it) to DataflowAnalysis.h.
0055 template <typename LatticeT> struct TransferStateForDiagnostics {
0056   TransferStateForDiagnostics(const LatticeT &Lattice, const Environment &Env)
0057       : Lattice(Lattice), Env(Env) {}
0058
0059   /// Current lattice element.
0060   const LatticeT &Lattice;
0061   const Environment &Env;
0062 };
0063
0064 template <typename T>
0065 using MatchSwitchMatcher = ast_matchers::internal::Matcher<T>;
0066
0067 template <typename T, typename State, typename Result = void>
0068 using MatchSwitchAction = std::function<Result(
0069     const T *, const ast_matchers::MatchFinder::MatchResult &, State &)>;
0070
0071 template <typename BaseT, typename State, typename Result = void>
0072 using ASTMatchSwitch =
0073     std::function<Result(const BaseT &, ASTContext &, State &)>;
0074
0075 /// Collects cases of a "match switch": a collection of matchers paired with
0076 /// callbacks, which together define a switch that can be applied to a node
0077 /// whose type derives from `BaseT`. This structure can simplify the definition
0078 /// of `transfer` functions that rely on pattern-matching.
0079 ///
0080 /// For example, consider an analysis that handles particular function calls. It
0081 /// can define the `ASTMatchSwitch` once, in the constructor of the analysis,
0082 /// and then reuse it each time that `transfer` is called, with a fresh state
0083 /// value.
0084 ///
0085 /// \code
0086 /// ASTMatchSwitch<Stmt, TransferState<MyLattice> BuildSwitch() {
0087 ///   return ASTMatchSwitchBuilder<TransferState<MyLattice>>()
0088 ///     .CaseOf(callExpr(callee(functionDecl(hasName("foo")))), TransferFooCall)
0089 ///     .CaseOf(callExpr(argumentCountIs(2),
0090 ///                      callee(functionDecl(hasName("bar")))),
0091 ///             TransferBarCall)
0092 ///     .Build();
0093 /// }
0094 /// \endcode
0095 template <typename BaseT, typename State, typename Result = void>
0096 class ASTMatchSwitchBuilder {
0097 public:
0098   /// Registers an action that will be triggered by the match of a pattern
0099   /// against the input statement.
0100   ///
0101   /// Requirements:
0102   ///
0103   ///  `NodeT` should be derived from `BaseT`.
0104   template <typename NodeT>
0105   ASTMatchSwitchBuilder &&CaseOf(MatchSwitchMatcher<BaseT> M,
0106                                  MatchSwitchAction<NodeT, State, Result> A) && {
0107     static_assert(std::is_base_of<BaseT, NodeT>::value,
0108                   "NodeT must be derived from BaseT.");
0109     Matchers.push_back(std::move(M));
0110     Actions.push_back(
0111         [A = std::move(A)](const BaseT *Node,
0112                            const ast_matchers::MatchFinder::MatchResult &R,
0113                            State &S) { return A(cast<NodeT>(Node), R, S); });
0114     return std::move(*this);
0115   }
0116
0117   ASTMatchSwitch<BaseT, State, Result> Build() && {
0118     return [Matcher = BuildMatcher(), Actions = std::move(Actions)](
0119                const BaseT &Node, ASTContext &Context, State &S) -> Result {
0120       auto Results = ast_matchers::matchDynamic(Matcher, Node, Context);
0121       if (Results.empty()) {
0122         return Result();
0123       }
0124       // Look through the map for the first binding of the form "TagN..." use
0125       // that to select the action.
0126       for (const auto &Element : Results[0].getMap()) {
0127         llvm::StringRef ID(Element.first);
0128         size_t Index = 0;
0129         if (ID.consume_front("Tag") && !ID.getAsInteger(10, Index) &&
0130             Index < Actions.size()) {
0131           return Actions[Index](
0132               &Node,
0133               ast_matchers::MatchFinder::MatchResult(Results[0], &Context), S);
0134         }
0135       }
0136       return Result();
0137     };
0138   }
0139
0140 private:
0141   ast_matchers::internal::DynTypedMatcher BuildMatcher() {
0142     using ast_matchers::anything;
0143     using ast_matchers::stmt;
0144     using ast_matchers::unless;
0145     using ast_matchers::internal::DynTypedMatcher;
0146     if (Matchers.empty())
0147       return stmt(unless(anything()));
0148     for (int I = 0, N = Matchers.size(); I < N; ++I) {
0149       std::string Tag = ("Tag" + llvm::Twine(I)).str();
0150       // Many matchers are not bindable, so ensure that tryBind will work.
0151       Matchers[I].setAllowBind(true);
0152       auto M = *Matchers[I].tryBind(Tag);
0153       // Each anyOf explicitly controls the traversal kind. The anyOf itself is
0154       // set to `TK_AsIs` to ensure no nodes are skipped, thereby deferring to
0155       // the kind of the branches. Then, each branch is either left as is, if
0156       // the kind is already set, or explicitly set to `TK_AsIs`. We choose this
0157       // setting because it is the default interpretation of matchers.
0158       Matchers[I] =
0159           !M.getTraversalKind() ? M.withTraversalKind(TK_AsIs) : std::move(M);
0160     }
0161     // The matcher type on the cases ensures that `Expr` kind is compatible with
0162     // all of the matchers.
0163     return DynTypedMatcher::constructVariadic(
0164         DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind<BaseT>(),
0165         std::move(Matchers));
0166   }
0167
0168   std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
0169   std::vector<MatchSwitchAction<BaseT, State, Result>> Actions;
0170 };
0171
0172 } // namespace dataflow
0173 } // namespace clang
0174 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_