Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- ASTMatchersInternal.h - Structural query framework -------*- 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

//

//===----------------------------------------------------------------------===//

//

//  Implements the base layer of the matcher framework.

//

//  Matchers are methods that return a Matcher<T> which provides a method

//  Matches(...) which is a predicate on an AST node. The Matches method's

//  parameters define the context of the match, which allows matchers to recurse

//  or store the current node as bound to a specific string, so that it can be

//  retrieved later.

//

//  In general, matchers have two parts:

//  1. A function Matcher<T> MatcherName(<arguments>) which returns a Matcher<T>

//     based on the arguments and optionally on template type deduction based

//     on the arguments. Matcher<T>s form an implicit reverse hierarchy

//     to clang's AST class hierarchy, meaning that you can use a Matcher<Base>

//     everywhere a Matcher<Derived> is required.

//  2. An implementation of a class derived from MatcherInterface<T>.

//

//  The matcher functions are defined in ASTMatchers.h. To make it possible

//  to implement both the matcher function and the implementation of the matcher

//  interface in one place, ASTMatcherMacros.h defines macros that allow

//  implementing a matcher in a single place.

//

//  This file contains the base classes needed to construct the actual matchers.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H

#define LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H

#include "clang/AST/ASTTypeTraits.h"

#include "clang/AST/Decl.h"

#include "clang/AST/DeclCXX.h"

#include "clang/AST/DeclFriend.h"

#include "clang/AST/DeclTemplate.h"

#include "clang/AST/Expr.h"

#include "clang/AST/ExprCXX.h"

#include "clang/AST/ExprObjC.h"

#include "clang/AST/NestedNameSpecifier.h"

#include "clang/AST/Stmt.h"

#include "clang/AST/TemplateName.h"

#include "clang/AST/Type.h"

#include "clang/AST/TypeLoc.h"

#include "clang/Basic/LLVM.h"

#include "clang/Basic/OperatorKinds.h"

#include "llvm/ADT/APFloat.h"

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/IntrusiveRefCntPtr.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/ADT/iterator.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/ManagedStatic.h"

#include "llvm/Support/Regex.h"

#include <algorithm>

#include <cassert>

#include <cstddef>

#include <cstdint>

#include <map>

#include <memory>

#include <optional>

#include <string>

#include <tuple>

#include <type_traits>

#include <utility>

#include <vector>

namespace clang {

class ASTContext;

namespace ast_matchers {

class BoundNodes;

namespace internal {

/// A type-list implementation.

///

/// A "linked list" of types, accessible by using the ::head and ::tail

/// typedefs.

template <typename... Ts> struct TypeList {}; // Empty sentinel type list.

template <typename T1, typename... Ts> struct TypeList<T1, Ts...> {

  /// The first type on the list.

  using head = T1;

  /// A sublist with the tail. ie everything but the head.

  ///

  /// This type is used to do recursion. TypeList<>/EmptyTypeList indicates the

  /// end of the list.

  using tail = TypeList<Ts...>;

};

/// The empty type list.

using EmptyTypeList = TypeList<>;

/// Helper meta-function to determine if some type \c T is present or

///   a parent type in the list.

template <typename AnyTypeList, typename T> struct TypeListContainsSuperOf {

  static const bool value =

      std::is_base_of<typename AnyTypeList::head, T>::value ||

      TypeListContainsSuperOf<typename AnyTypeList::tail, T>::value;

};

template <typename T> struct TypeListContainsSuperOf<EmptyTypeList, T> {

  static const bool value = false;

};

/// Variadic function object.

///

/// Most of the functions below that use VariadicFunction could be implemented

/// using plain C++11 variadic functions, but the function object allows us to

/// capture it on the dynamic matcher registry.

template <typename ResultT, typename ArgT,

          ResultT (*Func)(ArrayRef<const ArgT *>)>

struct VariadicFunction {

  ResultT operator()() const { return Func(std::nullopt); }

  template <typename... ArgsT>

  ResultT operator()(const ArgT &Arg1, const ArgsT &... Args) const {

    return Execute(Arg1, static_cast<const ArgT &>(Args)...);

  }

  // We also allow calls with an already created array, in case the caller

  // already had it.

  ResultT operator()(ArrayRef<ArgT> Args) const {

    return Func(llvm::to_vector<8>(llvm::make_pointer_range(Args)));

  }

private:

  // Trampoline function to allow for implicit conversions to take place

  // before we make the array.

  template <typename... ArgsT> ResultT Execute(const ArgsT &... Args) const {

    const ArgT *const ArgsArray[] = {&Args...};

    return Func(ArrayRef<const ArgT *>(ArgsArray, sizeof...(ArgsT)));

  }

};

/// Unifies obtaining the underlying type of a regular node through

/// `getType` and a TypedefNameDecl node through `getUnderlyingType`.

inline QualType getUnderlyingType(const Expr &Node) { return Node.getType(); }

inline QualType getUnderlyingType(const ValueDecl &Node) {

  return Node.getType();

}

inline QualType getUnderlyingType(const TypedefNameDecl &Node) {

  return Node.getUnderlyingType();

}

inline QualType getUnderlyingType(const FriendDecl &Node) {

  if (const TypeSourceInfo *TSI = Node.getFriendType())

    return TSI->getType();

  return QualType();

}

inline QualType getUnderlyingType(const CXXBaseSpecifier &Node) {

  return Node.getType();

}

/// Unifies obtaining a `TypeSourceInfo` from different node types.

template <typename T,

          std::enable_if_t<TypeListContainsSuperOf<

              TypeList<CXXBaseSpecifier, CXXCtorInitializer,

                       CXXTemporaryObjectExpr, CXXUnresolvedConstructExpr,

                       CompoundLiteralExpr, DeclaratorDecl, ObjCPropertyDecl,

                       TemplateArgumentLoc, TypedefNameDecl>,

              T>::value> * = nullptr>

inline TypeSourceInfo *GetTypeSourceInfo(const T &Node) {

  return Node.getTypeSourceInfo();

}

template <typename T,

          std::enable_if_t<TypeListContainsSuperOf<

              TypeList<CXXFunctionalCastExpr, ExplicitCastExpr>, T>::value> * =

              nullptr>

inline TypeSourceInfo *GetTypeSourceInfo(const T &Node) {

  return Node.getTypeInfoAsWritten();

}

inline TypeSourceInfo *GetTypeSourceInfo(const BlockDecl &Node) {

  return Node.getSignatureAsWritten();

}

inline TypeSourceInfo *GetTypeSourceInfo(const CXXNewExpr &Node) {

  return Node.getAllocatedTypeSourceInfo();

}

inline TypeSourceInfo *

GetTypeSourceInfo(const ClassTemplateSpecializationDecl &Node) {

  return Node.getTypeAsWritten();

}

/// Unifies obtaining the FunctionProtoType pointer from both

/// FunctionProtoType and FunctionDecl nodes..

inline const FunctionProtoType *

getFunctionProtoType(const FunctionProtoType &Node) {

  return &Node;

}

inline const FunctionProtoType *getFunctionProtoType(const FunctionDecl &Node) {

  return Node.getType()->getAs<FunctionProtoType>();

}

/// Unifies obtaining the access specifier from Decl and CXXBaseSpecifier nodes.

inline clang::AccessSpecifier getAccessSpecifier(const Decl &Node) {

  return Node.getAccess();

}

inline clang::AccessSpecifier getAccessSpecifier(const CXXBaseSpecifier &Node) {

  return Node.getAccessSpecifier();

}

/// Internal version of BoundNodes. Holds all the bound nodes.

class BoundNodesMap {

public:

  /// Adds \c Node to the map with key \c ID.

  ///

  /// The node's base type should be in NodeBaseType or it will be unaccessible.

  void addNode(StringRef ID, const DynTypedNode &DynNode) {

    NodeMap[std::string(ID)] = DynNode;

  }

  /// Returns the AST node bound to \c ID.

  ///

  /// Returns NULL if there was no node bound to \c ID or if there is a node but

  /// it cannot be converted to the specified type.

  template <typename T>

  const T *getNodeAs(StringRef ID) const {

    IDToNodeMap::const_iterator It = NodeMap.find(ID);

    if (It == NodeMap.end()) {

      return nullptr;

    }

    return It->second.get<T>();

  }

  DynTypedNode getNode(StringRef ID) const {

    IDToNodeMap::const_iterator It = NodeMap.find(ID);

    if (It == NodeMap.end()) {

      return DynTypedNode();

    }

    return It->second;

  }

  /// Imposes an order on BoundNodesMaps.

  bool operator<(const BoundNodesMap &Other) const {

    return NodeMap < Other.NodeMap;

  }

  /// A map from IDs to the bound nodes.

  ///

  /// Note that we're using std::map here, as for memoization:

  /// - we need a comparison operator

  /// - we need an assignment operator

  using IDToNodeMap = std::map<std::string, DynTypedNode, std::less<>>;

  const IDToNodeMap &getMap() const {

    return NodeMap;

  }

  /// Returns \c true if this \c BoundNodesMap can be compared, i.e. all

  /// stored nodes have memoization data.

  bool isComparable() const {

    for (const auto &IDAndNode : NodeMap) {

      if (!IDAndNode.second.getMemoizationData())

        return false;

    }

    return true;

  }

private:

  IDToNodeMap NodeMap;

};

/// Creates BoundNodesTree objects.

///

/// The tree builder is used during the matching process to insert the bound

/// nodes from the Id matcher.

class BoundNodesTreeBuilder {

public:

  /// A visitor interface to visit all BoundNodes results for a

  /// BoundNodesTree.

  class Visitor {

  public:

    virtual ~Visitor() = default;

    /// Called multiple times during a single call to VisitMatches(...).

    ///

    /// 'BoundNodesView' contains the bound nodes for a single match.

    virtual void visitMatch(const BoundNodes& BoundNodesView) = 0;

  };

  /// Add a binding from an id to a node.

  void setBinding(StringRef Id, const DynTypedNode &DynNode) {

    if (Bindings.empty())

      Bindings.emplace_back();

    for (BoundNodesMap &Binding : Bindings)

      Binding.addNode(Id, DynNode);

  }

  /// Adds a branch in the tree.

  void addMatch(const BoundNodesTreeBuilder &Bindings);

  /// Visits all matches that this BoundNodesTree represents.

  ///

  /// The ownership of 'ResultVisitor' remains at the caller.

  void visitMatches(Visitor* ResultVisitor);

  template <typename ExcludePredicate>

  bool removeBindings(const ExcludePredicate &Predicate) {

    llvm::erase_if(Bindings, Predicate);

    return !Bindings.empty();

  }

  /// Imposes an order on BoundNodesTreeBuilders.

  bool operator<(const BoundNodesTreeBuilder &Other) const {

    return Bindings < Other.Bindings;

  }

  /// Returns \c true if this \c BoundNodesTreeBuilder can be compared,

  /// i.e. all stored node maps have memoization data.

  bool isComparable() const {

    for (const BoundNodesMap &NodesMap : Bindings) {

      if (!NodesMap.isComparable())

        return false;

    }

    return true;

  }

private:

  SmallVector<BoundNodesMap, 1> Bindings;

};

class ASTMatchFinder;

/// Generic interface for all matchers.

///

/// Used by the implementation of Matcher<T> and DynTypedMatcher.

/// In general, implement MatcherInterface<T> or SingleNodeMatcherInterface<T>

/// instead.

class DynMatcherInterface

    : public llvm::ThreadSafeRefCountedBase<DynMatcherInterface> {

public:

  virtual ~DynMatcherInterface() = default;

  /// Returns true if \p DynNode can be matched.

  ///

  /// May bind \p DynNode to an ID via \p Builder, or recurse into

  /// the AST via \p Finder.

  virtual bool dynMatches(const DynTypedNode &DynNode, ASTMatchFinder *Finder,

                          BoundNodesTreeBuilder *Builder) const = 0;

  virtual std::optional<clang::TraversalKind> TraversalKind() const {

    return std::nullopt;

  }

};

/// Generic interface for matchers on an AST node of type T.

///

/// Implement this if your matcher may need to inspect the children or

/// descendants of the node or bind matched nodes to names. If you are

/// writing a simple matcher that only inspects properties of the

/// current node and doesn't care about its children or descendants,

/// implement SingleNodeMatcherInterface instead.

template <typename T>

class MatcherInterface : public DynMatcherInterface {

public:

  /// Returns true if 'Node' can be matched.

  ///

  /// May bind 'Node' to an ID via 'Builder', or recurse into

  /// the AST via 'Finder'.

  virtual bool matches(const T &Node,

                       ASTMatchFinder *Finder,

                       BoundNodesTreeBuilder *Builder) const = 0;

  bool dynMatches(const DynTypedNode &DynNode, ASTMatchFinder *Finder,

                  BoundNodesTreeBuilder *Builder) const override {

    return matches(DynNode.getUnchecked<T>(), Finder, Builder);

  }

};

/// Interface for matchers that only evaluate properties on a single

/// node.

template <typename T>

class SingleNodeMatcherInterface : public MatcherInterface<T> {

public:

  /// Returns true if the matcher matches the provided node.

  ///

  /// A subclass must implement this instead of Matches().

  virtual bool matchesNode(const T &Node) const = 0;

private:

  /// Implements MatcherInterface::Matches.

  bool matches(const T &Node,

               ASTMatchFinder * /* Finder */,

               BoundNodesTreeBuilder * /*  Builder */) const override {

    return matchesNode(Node);

  }

};

template <typename> class Matcher;

/// Matcher that works on a \c DynTypedNode.

///

/// It is constructed from a \c Matcher<T> object and redirects most calls to

/// underlying matcher.

/// It checks whether the \c DynTypedNode is convertible into the type of the

/// underlying matcher and then do the actual match on the actual node, or

/// return false if it is not convertible.

class DynTypedMatcher {

public:

  /// Takes ownership of the provided implementation pointer.

  template <typename T>

  DynTypedMatcher(MatcherInterface<T> *Implementation)

      : SupportedKind(ASTNodeKind::getFromNodeKind<T>()),

        RestrictKind(SupportedKind), Implementation(Implementation) {}

  /// Construct from a variadic function.

  enum VariadicOperator {

    /// Matches nodes for which all provided matchers match.

    VO_AllOf,

    /// Matches nodes for which at least one of the provided matchers

    /// matches.

    VO_AnyOf,

    /// Matches nodes for which at least one of the provided matchers

    /// matches, but doesn't stop at the first match.

    VO_EachOf,

    /// Matches any node but executes all inner matchers to find result

    /// bindings.

    VO_Optionally,

    /// Matches nodes that do not match the provided matcher.

    ///

    /// Uses the variadic matcher interface, but fails if

    /// InnerMatchers.size() != 1.

    VO_UnaryNot

  };

  static DynTypedMatcher

  constructVariadic(VariadicOperator Op, ASTNodeKind SupportedKind,

                    std::vector<DynTypedMatcher> InnerMatchers);

  static DynTypedMatcher

  constructRestrictedWrapper(const DynTypedMatcher &InnerMatcher,

                             ASTNodeKind RestrictKind);

  /// Get a "true" matcher for \p NodeKind.

  ///

  /// It only checks that the node is of the right kind.

  static DynTypedMatcher trueMatcher(ASTNodeKind NodeKind);

  void setAllowBind(bool AB) { AllowBind = AB; }

  /// Check whether this matcher could ever match a node of kind \p Kind.

  /// \return \c false if this matcher will never match such a node. Otherwise,

  /// return \c true.

  bool canMatchNodesOfKind(ASTNodeKind Kind) const;

  /// Return a matcher that points to the same implementation, but

  ///   restricts the node types for \p Kind.

  DynTypedMatcher dynCastTo(const ASTNodeKind Kind) const;

  /// Return a matcher that points to the same implementation, but sets the

  ///   traversal kind.

  ///

  /// If the traversal kind is already set, then \c TK overrides it.

  DynTypedMatcher withTraversalKind(TraversalKind TK);

  /// Returns true if the matcher matches the given \c DynNode.

  bool matches(const DynTypedNode &DynNode, ASTMatchFinder *Finder,

               BoundNodesTreeBuilder *Builder) const;

  /// Same as matches(), but skips the kind check.

  ///

  /// It is faster, but the caller must ensure the node is valid for the

  /// kind of this matcher.

  bool matchesNoKindCheck(const DynTypedNode &DynNode, ASTMatchFinder *Finder,

                          BoundNodesTreeBuilder *Builder) const;

  /// Bind the specified \p ID to the matcher.

  /// \return A new matcher with the \p ID bound to it if this matcher supports

  ///   binding. Otherwise, returns an empty \c std::optional<>.

  std::optional<DynTypedMatcher> tryBind(StringRef ID) const;

  /// Returns a unique \p ID for the matcher.

  ///

  /// Casting a Matcher<T> to Matcher<U> creates a matcher that has the

  /// same \c Implementation pointer, but different \c RestrictKind. We need to

  /// include both in the ID to make it unique.

  ///

  /// \c MatcherIDType supports operator< and provides strict weak ordering.

  using MatcherIDType = std::pair<ASTNodeKind, uint64_t>;

  MatcherIDType getID() const {

    /// FIXME: Document the requirements this imposes on matcher

    /// implementations (no new() implementation_ during a Matches()).

    return std::make_pair(RestrictKind,

                          reinterpret_cast<uint64_t>(Implementation.get()));

  }

  /// Returns the type this matcher works on.

  ///

  /// \c matches() will always return false unless the node passed is of this

  /// or a derived type.

  ASTNodeKind getSupportedKind() const { return SupportedKind; }

  /// Returns \c true if the passed \c DynTypedMatcher can be converted

  ///   to a \c Matcher<T>.

  ///

  /// This method verifies that the underlying matcher in \c Other can process

  /// nodes of types T.

  template <typename T> bool canConvertTo() const {

    return canConvertTo(ASTNodeKind::getFromNodeKind<T>());

  }

  bool canConvertTo(ASTNodeKind To) const;

  /// Construct a \c Matcher<T> interface around the dynamic matcher.

  ///

  /// This method asserts that \c canConvertTo() is \c true. Callers

  /// should call \c canConvertTo() first to make sure that \c this is

  /// compatible with T.

  template <typename T> Matcher<T> convertTo() const {

    assert(canConvertTo<T>());

    return unconditionalConvertTo<T>();

  }

  /// Same as \c convertTo(), but does not check that the underlying

  ///   matcher can handle a value of T.

  ///

  /// If it is not compatible, then this matcher will never match anything.

  template <typename T> Matcher<T> unconditionalConvertTo() const;

  /// Returns the \c TraversalKind respected by calls to `match()`, if any.

  ///

  /// Most matchers will not have a traversal kind set, instead relying on the

  /// surrounding context. For those, \c std::nullopt is returned.

  std::optional<clang::TraversalKind> getTraversalKind() const {

    return Implementation->TraversalKind();

  }

private:

  DynTypedMatcher(ASTNodeKind SupportedKind, ASTNodeKind RestrictKind,

                  IntrusiveRefCntPtr<DynMatcherInterface> Implementation)

      : SupportedKind(SupportedKind), RestrictKind(RestrictKind),

        Implementation(std::move(Implementation)) {}

  bool AllowBind = false;

  ASTNodeKind SupportedKind;

  /// A potentially stricter node kind.

  ///

  /// It allows to perform implicit and dynamic cast of matchers without

  /// needing to change \c Implementation.

  ASTNodeKind RestrictKind;

  IntrusiveRefCntPtr<DynMatcherInterface> Implementation;

};

/// Wrapper of a MatcherInterface<T> *that allows copying.

///

/// A Matcher<Base> can be used anywhere a Matcher<Derived> is

/// required. This establishes an is-a relationship which is reverse

/// to the AST hierarchy. In other words, Matcher<T> is contravariant

/// with respect to T. The relationship is built via a type conversion

/// operator rather than a type hierarchy to be able to templatize the

/// type hierarchy instead of spelling it out.

template <typename T>

class Matcher {

public:

  /// Takes ownership of the provided implementation pointer.

  explicit Matcher(MatcherInterface<T> *Implementation)

      : Implementation(Implementation) {}

  /// Implicitly converts \c Other to a Matcher<T>.

  ///

  /// Requires \c T to be derived from \c From.

  template <typename From>

  Matcher(const Matcher<From> &Other,

          std::enable_if_t<std::is_base_of<From, T>::value &&

                           !std::is_same<From, T>::value> * = nullptr)

      : Implementation(restrictMatcher(Other.Implementation)) {

    assert(Implementation.getSupportedKind().isSame(

        ASTNodeKind::getFromNodeKind<T>()));

  }

  /// Implicitly converts \c Matcher<Type> to \c Matcher<QualType>.

  ///

  /// The resulting matcher is not strict, i.e. ignores qualifiers.

  template <typename TypeT>

  Matcher(const Matcher<TypeT> &Other,

          std::enable_if_t<std::is_same<T, QualType>::value &&

                           std::is_same<TypeT, Type>::value> * = nullptr)

      : Implementation(new TypeToQualType<TypeT>(Other)) {}

  /// Convert \c this into a \c Matcher<T> by applying dyn_cast<> to the

  /// argument.

  /// \c To must be a base class of \c T.

  template <typename To> Matcher<To> dynCastTo() const & {

    static_assert(std::is_base_of<To, T>::value, "Invalid dynCast call.");

    return Matcher<To>(Implementation);

  }

  template <typename To> Matcher<To> dynCastTo() && {

    static_assert(std::is_base_of<To, T>::value, "Invalid dynCast call.");

    return Matcher<To>(std::move(Implementation));

  }

  /// Forwards the call to the underlying MatcherInterface<T> pointer.

  bool matches(const T &Node,

               ASTMatchFinder *Finder,

               BoundNodesTreeBuilder *Builder) const {

    return Implementation.matches(DynTypedNode::create(Node), Finder, Builder);

  }

  /// Returns an ID that uniquely identifies the matcher.

  DynTypedMatcher::MatcherIDType getID() const {

    return Implementation.getID();

  }

  /// Extract the dynamic matcher.

  ///

  /// The returned matcher keeps the same restrictions as \c this and remembers

  /// that it is meant to support nodes of type \c T.

  operator DynTypedMatcher() const & { return Implementation; }

  operator DynTypedMatcher() && { return std::move(Implementation); }

  /// Allows the conversion of a \c Matcher<Type> to a \c

  /// Matcher<QualType>.

  ///

  /// Depending on the constructor argument, the matcher is either strict, i.e.

  /// does only matches in the absence of qualifiers, or not, i.e. simply

  /// ignores any qualifiers.

  template <typename TypeT>

  class TypeToQualType : public MatcherInterface<QualType> {

    const DynTypedMatcher InnerMatcher;

  public:

    TypeToQualType(const Matcher<TypeT> &InnerMatcher)

        : InnerMatcher(InnerMatcher) {}

    bool matches(const QualType &Node, ASTMatchFinder *Finder,

                 BoundNodesTreeBuilder *Builder) const override {

      if (Node.isNull())

        return false;

      return this->InnerMatcher.matches(DynTypedNode::create(*Node), Finder,

                                        Builder);

    }

    std::optional<clang::TraversalKind> TraversalKind() const override {

      return this->InnerMatcher.getTraversalKind();

    }

  };

private:

  // For Matcher<T> <=> Matcher<U> conversions.

  template <typename U> friend class Matcher;

  // For DynTypedMatcher::unconditionalConvertTo<T>.

  friend class DynTypedMatcher;

  static DynTypedMatcher restrictMatcher(const DynTypedMatcher &Other) {

    return Other.dynCastTo(ASTNodeKind::getFromNodeKind<T>());

  }

  explicit Matcher(const DynTypedMatcher &Implementation)

      : Implementation(restrictMatcher(Implementation)) {

    assert(this->Implementation.getSupportedKind().isSame(

        ASTNodeKind::getFromNodeKind<T>()));

  }

  DynTypedMatcher Implementation;

};  // class Matcher

/// A convenient helper for creating a Matcher<T> without specifying

/// the template type argument.

template <typename T>

inline Matcher<T> makeMatcher(MatcherInterface<T> *Implementation) {

  return Matcher<T>(Implementation);

}

/// Interface that allows matchers to traverse the AST.

/// FIXME: Find a better name.

///

/// This provides three entry methods for each base node type in the AST:

/// - \c matchesChildOf:

///   Matches a matcher on every child node of the given node. Returns true

///   if at least one child node could be matched.

/// - \c matchesDescendantOf:

///   Matches a matcher on all descendant nodes of the given node. Returns true

///   if at least one descendant matched.

/// - \c matchesAncestorOf:

///   Matches a matcher on all ancestors of the given node. Returns true if

///   at least one ancestor matched.

///

/// FIXME: Currently we only allow Stmt and Decl nodes to start a traversal.

/// In the future, we want to implement this for all nodes for which it makes

/// sense. In the case of matchesAncestorOf, we'll want to implement it for

/// all nodes, as all nodes have ancestors.

class ASTMatchFinder {

public:

  /// Defines how bindings are processed on recursive matches.

  enum BindKind {

    /// Stop at the first match and only bind the first match.

    BK_First,

    /// Create results for all combinations of bindings that match.

    BK_All

  };

  /// Defines which ancestors are considered for a match.

  enum AncestorMatchMode {

    /// All ancestors.

    AMM_All,

    /// Direct parent only.

    AMM_ParentOnly

  };

  virtual ~ASTMatchFinder() = default;

  /// Returns true if the given C++ class is directly or indirectly derived

  /// from a base type matching \c base.

  ///

  /// A class is not considered to be derived from itself.

  virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,

                                  const Matcher<NamedDecl> &Base,

                                  BoundNodesTreeBuilder *Builder,

                                  bool Directly) = 0;

  /// Returns true if the given Objective-C class is directly or indirectly

  /// derived from a base class matching \c base.

  ///

  /// A class is not considered to be derived from itself.

  virtual bool objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration,

                                      const Matcher<NamedDecl> &Base,

                                      BoundNodesTreeBuilder *Builder,

                                      bool Directly) = 0;

  template <typename T>

  bool matchesChildOf(const T &Node, const DynTypedMatcher &Matcher,

                      BoundNodesTreeBuilder *Builder, BindKind Bind) {

    static_assert(std::is_base_of<Decl, T>::value ||

                      std::is_base_of<Stmt, T>::value ||

                      std::is_base_of<NestedNameSpecifier, T>::value ||

                      std::is_base_of<NestedNameSpecifierLoc, T>::value ||

                      std::is_base_of<TypeLoc, T>::value ||

                      std::is_base_of<QualType, T>::value ||

                      std::is_base_of<Attr, T>::value,

                  "unsupported type for recursive matching");

    return matchesChildOf(DynTypedNode::create(Node), getASTContext(), Matcher,

                          Builder, Bind);

  }

  template <typename T>

  bool matchesDescendantOf(const T &Node, const DynTypedMatcher &Matcher,

                           BoundNodesTreeBuilder *Builder, BindKind Bind) {

    static_assert(std::is_base_of<Decl, T>::value ||

                      std::is_base_of<Stmt, T>::value ||

                      std::is_base_of<NestedNameSpecifier, T>::value ||

                      std::is_base_of<NestedNameSpecifierLoc, T>::value ||

                      std::is_base_of<TypeLoc, T>::value ||

                      std::is_base_of<QualType, T>::value ||

                      std::is_base_of<Attr, T>::value,

                  "unsupported type for recursive matching");

    return matchesDescendantOf(DynTypedNode::create(Node), getASTContext(),

                               Matcher, Builder, Bind);

  }

  // FIXME: Implement support for BindKind.

  template <typename T>

  bool matchesAncestorOf(const T &Node, const DynTypedMatcher &Matcher,

                         BoundNodesTreeBuilder *Builder,

                         AncestorMatchMode MatchMode) {

    static_assert(std::is_base_of<Decl, T>::value ||

                      std::is_base_of<NestedNameSpecifierLoc, T>::value ||

                      std::is_base_of<Stmt, T>::value ||

                      std::is_base_of<TypeLoc, T>::value ||

                      std::is_base_of<Attr, T>::value,

                  "type not allowed for recursive matching");

    return matchesAncestorOf(DynTypedNode::create(Node), getASTContext(),

                             Matcher, Builder, MatchMode);

  }

  virtual ASTContext &getASTContext() const = 0;

  virtual bool IsMatchingInASTNodeNotSpelledInSource() const = 0;

  virtual bool IsMatchingInASTNodeNotAsIs() const = 0;

  bool isTraversalIgnoringImplicitNodes() const;

protected:

  virtual bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx,

                              const DynTypedMatcher &Matcher,

                              BoundNodesTreeBuilder *Builder,

                              BindKind Bind) = 0;

  virtual bool matchesDescendantOf(const DynTypedNode &Node, ASTContext &Ctx,

                                   const DynTypedMatcher &Matcher,

                                   BoundNodesTreeBuilder *Builder,

                                   BindKind Bind) = 0;

  virtual bool matchesAncestorOf(const DynTypedNode &Node, ASTContext &Ctx,

                                 const DynTypedMatcher &Matcher,

                                 BoundNodesTreeBuilder *Builder,

                                 AncestorMatchMode MatchMode) = 0;

private:

  friend struct ASTChildrenNotSpelledInSourceScope;

  virtual bool isMatchingChildrenNotSpelledInSource() const = 0;

  virtual void setMatchingChildrenNotSpelledInSource(bool Set) = 0;

};

struct ASTChildrenNotSpelledInSourceScope {

  ASTChildrenNotSpelledInSourceScope(ASTMatchFinder *V, bool B)

      : MV(V), MB(V->isMatchingChildrenNotSpelledInSource()) {

    V->setMatchingChildrenNotSpelledInSource(B);

  }

  ~ASTChildrenNotSpelledInSourceScope() {