/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/ASTMatchers/ASTMatchersInternal.h

Source (jump to first uncovered line)
//===- 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/None.h"
#include "llvm/ADT/Optional.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 <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(None); }

  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 llvm::Optional<clang::TraversalKind> TraversalKind() const {
    return llvm::None;
  }
};

/// 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 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 Optional<>.
  llvm::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 llvm::None is returned.
  llvm::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) {}

Coverage Report

Created: 2022-07-16 07:03