//===--- ASTMatchers.h - Structural query framework -------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This file implements matchers to be used together with the MatchFinder to
//  match AST nodes.
//
//  Matchers are created by generator functions, which can be combined in
//  a functional in-language DSL to express queries over the C++ AST.
//
//  For example, to match a class with a certain name, one would call:
//    recordDecl(hasName("MyClass"))
//  which returns a matcher that can be used to find all AST nodes that declare
//  a class named 'MyClass'.
//
//  For more complicated match expressions we're often interested in accessing
//  multiple parts of the matched AST nodes once a match is found. In that case,
//  use the id(...) matcher around the match expressions that match the nodes
//  you want to access.
//
//  For example, when we're interested in child classes of a certain class, we
//  would write:
//    recordDecl(hasName("MyClass"), hasChild(id("child", recordDecl())))
//  When the match is found via the MatchFinder, a user provided callback will
//  be called with a BoundNodes instance that contains a mapping from the
//  strings that we provided for the id(...) calls to the nodes that were
//  matched.
//  In the given example, each time our matcher finds a match we get a callback
//  where "child" is bound to the CXXRecordDecl node of the matching child
//  class declaration.
//
//  See ASTMatchersInternal.h for a more in-depth explanation of the
//  implementation details of the matcher framework.
//
//  See ASTMatchFinder.h for how to use the generated matchers to run over
//  an AST.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_AST_MATCHERS_AST_MATCHERS_H
#define LLVM_CLANG_AST_MATCHERS_AST_MATCHERS_H

#include "clang/AST/DeclFriend.h"
#include "clang/AST/DeclTemplate.h"
#include "clang/ASTMatchers/ASTMatchersInternal.h"
#include "clang/ASTMatchers/ASTMatchersMacros.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Support/Regex.h"
#include <iterator>

namespace clang {
namespace ast_matchers {

/// \brief Maps string IDs to AST nodes matched by parts of a matcher.
///
/// The bound nodes are generated by calling \c bind("id") on the node matchers
/// of the nodes we want to access later.
///
/// The instances of BoundNodes are created by \c MatchFinder when the user's
/// callbacks are executed every time a match is found.
class BoundNodes {
public:
  /// \brief 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 {
    return MyBoundNodes.getNodeAs<T>(ID);
  }

  /// \brief Deprecated. Please use \c getNodeAs instead.
  /// @{
  template <typename T>
  const T *getDeclAs(StringRef ID) const {
    return getNodeAs<T>(ID);
  }
  template <typename T>
  const T *getStmtAs(StringRef ID) const {
    return getNodeAs<T>(ID);
  }
  /// @}

  /// \brief Type of mapping from binding identifiers to bound nodes. This type
  /// is an associative container with a key type of \c std::string and a value
  /// type of \c clang::ast_type_traits::DynTypedNode
  typedef internal::BoundNodesMap::IDToNodeMap IDToNodeMap;

  /// \brief Retrieve mapping from binding identifiers to bound nodes.
  const IDToNodeMap &getMap() const {
    return MyBoundNodes.getMap();
  }

private:
  /// \brief Create BoundNodes from a pre-filled map of bindings.
  BoundNodes(internal::BoundNodesMap &MyBoundNodes)
      : MyBoundNodes(MyBoundNodes) {}

  internal::BoundNodesMap MyBoundNodes;

  friend class internal::BoundNodesTreeBuilder;
};

/// \brief If the provided matcher matches a node, binds the node to \c ID.
///
/// FIXME: Do we want to support this now that we have bind()?
template <typename T>
internal::Matcher<T> id(const std::string &ID,
                        const internal::BindableMatcher<T> &InnerMatcher) {
  return InnerMatcher.bind(ID);
}

/// \brief Types of matchers for the top-level classes in the AST class
/// hierarchy.
/// @{
typedef internal::Matcher<Decl> DeclarationMatcher;
typedef internal::Matcher<Stmt> StatementMatcher;
typedef internal::Matcher<QualType> TypeMatcher;
typedef internal::Matcher<TypeLoc> TypeLocMatcher;
typedef internal::Matcher<NestedNameSpecifier> NestedNameSpecifierMatcher;
typedef internal::Matcher<NestedNameSpecifierLoc> NestedNameSpecifierLocMatcher;
/// @}

/// \brief Matches any node.
///
/// Useful when another matcher requires a child matcher, but there's no
/// additional constraint. This will often be used with an explicit conversion
/// to an \c internal::Matcher<> type such as \c TypeMatcher.
///
/// Example: \c DeclarationMatcher(anything()) matches all declarations, e.g.,
/// \code
/// "int* p" and "void f()" in
///   int* p;
///   void f();
/// \endcode
///
/// Usable as: Any Matcher
inline internal::PolymorphicMatcherWithParam0<internal::TrueMatcher>
anything() {
  return internal::PolymorphicMatcherWithParam0<internal::TrueMatcher>();
}

/// \brief Matches declarations.
///
/// Examples matches \c X, \c C, and the friend declaration inside \c C;
/// \code
///   void X();
///   class C {
///     friend X;
///   };
/// \endcode
const internal::VariadicAllOfMatcher<Decl> decl;

/// \brief Matches a declaration of anything that could have a name.
///
/// Example matches \c X, \c S, the anonymous union type, \c i, and \c U;
/// \code
///   typedef int X;
///   struct S {
///     union {
///       int i;
///     } U;
///   };
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Decl, NamedDecl> namedDecl;

/// \brief Matches a declaration of a namespace.
///
/// Given
/// \code
///   namespace {}
///   namespace test {}
/// \endcode
/// namespaceDecl()
///   matches "namespace {}" and "namespace test {}"
const internal::VariadicDynCastAllOfMatcher<Decl, NamespaceDecl> namespaceDecl;

/// \brief Matches C++ class declarations.
///
/// Example matches \c X, \c Z
/// \code
///   class X;
///   template<class T> class Z {};
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Decl,
  CXXRecordDecl> recordDecl;

/// \brief Matches C++ class template declarations.
///
/// Example matches \c Z
/// \code
///   template<class T> class Z {};
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Decl,
  ClassTemplateDecl> classTemplateDecl;

/// \brief Matches C++ class template specializations.
///
/// Given
/// \code
///   template<typename T> class A {};
///   template<> class A<double> {};
///   A<int> a;
/// \endcode
/// classTemplateSpecializationDecl()
///   matches the specializations \c A<int> and \c A<double>
const internal::VariadicDynCastAllOfMatcher<
  Decl,
  ClassTemplateSpecializationDecl> classTemplateSpecializationDecl;

/// \brief Matches declarator declarations (field, variable, function
/// and non-type template parameter declarations).
///
/// Given
/// \code
///   class X { int y; };
/// \endcode
/// declaratorDecl()
///   matches \c int y.
const internal::VariadicDynCastAllOfMatcher<Decl, DeclaratorDecl>
    declaratorDecl;

/// \brief Matches parameter variable declarations.
///
/// Given
/// \code
///   void f(int x);
/// \endcode
/// parmVarDecl()
///   matches \c int x.
const internal::VariadicDynCastAllOfMatcher<Decl, ParmVarDecl> parmVarDecl;

/// \brief Matches C++ access specifier declarations.
///
/// Given
/// \code
///   class C {
///   public:
///     int a;
///   };
/// \endcode
/// accessSpecDecl()
///   matches 'public:'
const internal::VariadicDynCastAllOfMatcher<
  Decl,
  AccessSpecDecl> accessSpecDecl;

/// \brief Matches constructor initializers.
///
/// Examples matches \c i(42).
/// \code
///   class C {
///     C() : i(42) {}
///     int i;
///   };
/// \endcode
const internal::VariadicAllOfMatcher<CXXCtorInitializer> ctorInitializer;

/// \brief Matches public C++ declarations.
///
/// Given
/// \code
///   class C {
///   public:    int a;
///   protected: int b;
///   private:   int c;
///   };
/// \endcode
/// fieldDecl(isPublic())
///   matches 'int a;' 
AST_MATCHER(Decl, isPublic) {
  return Node.getAccess() == AS_public;
}

/// \brief Matches protected C++ declarations.
///
/// Given
/// \code
///   class C {
///   public:    int a;
///   protected: int b;
///   private:   int c;
///   };
/// \endcode
/// fieldDecl(isProtected())
///   matches 'int b;' 
AST_MATCHER(Decl, isProtected) {
  return Node.getAccess() == AS_protected;
}

/// \brief Matches private C++ declarations.
///
/// Given
/// \code
///   class C {
///   public:    int a;
///   protected: int b;
///   private:   int c;
///   };
/// \endcode
/// fieldDecl(isPrivate())
///   matches 'int c;' 
AST_MATCHER(Decl, isPrivate) {
  return Node.getAccess() == AS_private;
}

/// \brief Matches classTemplateSpecializations that have at least one
/// TemplateArgument matching the given InnerMatcher.
///
/// Given
/// \code
///   template<typename T> class A {};
///   template<> class A<double> {};
///   A<int> a;
/// \endcode
/// classTemplateSpecializationDecl(hasAnyTemplateArgument(
///     refersToType(asString("int"))))
///   matches the specialization \c A<int>
AST_MATCHER_P(ClassTemplateSpecializationDecl, hasAnyTemplateArgument,
              internal::Matcher<TemplateArgument>, InnerMatcher) {
  llvm::ArrayRef<TemplateArgument> List = Node.getTemplateArgs().asArray();
  return matchesFirstInRange(InnerMatcher, List.begin(), List.end(), Finder,
                             Builder);
}

/// \brief Matches expressions that match InnerMatcher after any implicit casts
/// are stripped off.
///
/// Parentheses and explicit casts are not discarded.
/// Given
/// \code
///   int arr[5];
///   int a = 0;
///   char b = 0;
///   const int c = a;
///   int *d = arr;
///   long e = (long) 0l;
/// \endcode
/// The matchers
/// \code
///    varDecl(hasInitializer(ignoringImpCasts(integerLiteral())))
///    varDecl(hasInitializer(ignoringImpCasts(declRefExpr())))
/// \endcode
/// would match the declarations for a, b, c, and d, but not e.
/// While
/// \code
///    varDecl(hasInitializer(integerLiteral()))
///    varDecl(hasInitializer(declRefExpr()))
/// \endcode
/// only match the declarations for b, c, and d.
AST_MATCHER_P(Expr, ignoringImpCasts,
              internal::Matcher<Expr>, InnerMatcher) {
  return InnerMatcher.matches(*Node.IgnoreImpCasts(), Finder, Builder);
}

/// \brief Matches expressions that match InnerMatcher after parentheses and
/// casts are stripped off.
///
/// Implicit and non-C Style casts are also discarded.
/// Given
/// \code
///   int a = 0;
///   char b = (0);
///   void* c = reinterpret_cast<char*>(0);
///   char d = char(0);
/// \endcode
/// The matcher
///    varDecl(hasInitializer(ignoringParenCasts(integerLiteral())))
/// would match the declarations for a, b, c, and d.
/// while
///    varDecl(hasInitializer(integerLiteral()))
/// only match the declaration for a.
AST_MATCHER_P(Expr, ignoringParenCasts, internal::Matcher<Expr>, InnerMatcher) {
  return InnerMatcher.matches(*Node.IgnoreParenCasts(), Finder, Builder);
}

/// \brief Matches expressions that match InnerMatcher after implicit casts and
/// parentheses are stripped off.
///
/// Explicit casts are not discarded.
/// Given
/// \code
///   int arr[5];
///   int a = 0;
///   char b = (0);
///   const int c = a;
///   int *d = (arr);
///   long e = ((long) 0l);
/// \endcode
/// The matchers
///    varDecl(hasInitializer(ignoringParenImpCasts(integerLiteral())))
///    varDecl(hasInitializer(ignoringParenImpCasts(declRefExpr())))
/// would match the declarations for a, b, c, and d, but not e.
/// while
///    varDecl(hasInitializer(integerLiteral()))
///    varDecl(hasInitializer(declRefExpr()))
/// would only match the declaration for a.
AST_MATCHER_P(Expr, ignoringParenImpCasts,
              internal::Matcher<Expr>, InnerMatcher) {
  return InnerMatcher.matches(*Node.IgnoreParenImpCasts(), Finder, Builder);
}

/// \brief Matches classTemplateSpecializations where the n'th TemplateArgument
/// matches the given InnerMatcher.
///
/// Given
/// \code
///   template<typename T, typename U> class A {};
///   A<bool, int> b;
///   A<int, bool> c;
/// \endcode
/// classTemplateSpecializationDecl(hasTemplateArgument(
///     1, refersToType(asString("int"))))
///   matches the specialization \c A<bool, int>
AST_MATCHER_P2(ClassTemplateSpecializationDecl, hasTemplateArgument,
               unsigned, N, internal::Matcher<TemplateArgument>, InnerMatcher) {
  const TemplateArgumentList &List = Node.getTemplateArgs();
  if (List.size() <= N)
    return false;
  return InnerMatcher.matches(List.get(N), Finder, Builder);
}

/// \brief Matches a TemplateArgument that refers to a certain type.
///
/// Given
/// \code
///   struct X {};
///   template<typename T> struct A {};
///   A<X> a;
/// \endcode
/// classTemplateSpecializationDecl(hasAnyTemplateArgument(
///     refersToType(class(hasName("X")))))
///   matches the specialization \c A<X>
AST_MATCHER_P(TemplateArgument, refersToType,
              internal::Matcher<QualType>, InnerMatcher) {
  if (Node.getKind() != TemplateArgument::Type)
    return false;
  return InnerMatcher.matches(Node.getAsType(), Finder, Builder);
}

/// \brief Matches a TemplateArgument that refers to a certain declaration.
///
/// Given
/// \code
///   template<typename T> struct A {};
///   struct B { B* next; };
///   A<&B::next> a;
/// \endcode
/// classTemplateSpecializationDecl(hasAnyTemplateArgument(
///     refersToDeclaration(fieldDecl(hasName("next"))))
///   matches the specialization \c A<&B::next> with \c fieldDecl(...) matching
///     \c B::next
AST_MATCHER_P(TemplateArgument, refersToDeclaration,
              internal::Matcher<Decl>, InnerMatcher) {
  if (Node.getKind() == TemplateArgument::Declaration)
    return InnerMatcher.matches(*Node.getAsDecl(), Finder, Builder);
  return false;
}

/// \brief Matches C++ constructor declarations.
///
/// Example matches Foo::Foo() and Foo::Foo(int)
/// \code
///   class Foo {
///    public:
///     Foo();
///     Foo(int);
///     int DoSomething();
///   };
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Decl,
  CXXConstructorDecl> constructorDecl;

/// \brief Matches explicit C++ destructor declarations.
///
/// Example matches Foo::~Foo()
/// \code
///   class Foo {
///    public:
///     virtual ~Foo();
///   };
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Decl,
  CXXDestructorDecl> destructorDecl;

/// \brief Matches enum declarations.
///
/// Example matches X
/// \code
///   enum X {
///     A, B, C
///   };
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Decl, EnumDecl> enumDecl;

/// \brief Matches enum constants.
///
/// Example matches A, B, C
/// \code
///   enum X {
///     A, B, C
///   };
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Decl,
  EnumConstantDecl> enumConstantDecl;

/// \brief Matches method declarations.
///
/// Example matches y
/// \code
///   class X { void y() };
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Decl, CXXMethodDecl> methodDecl;

/// \brief Matches variable declarations.
///
/// Note: this does not match declarations of member variables, which are
/// "field" declarations in Clang parlance.
///
/// Example matches a
/// \code
///   int a;
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Decl, VarDecl> varDecl;

/// \brief Matches field declarations.
///
/// Given
/// \code
///   class X { int m; };
/// \endcode
/// fieldDecl()
///   matches 'm'.
const internal::VariadicDynCastAllOfMatcher<Decl, FieldDecl> fieldDecl;

/// \brief Matches function declarations.
///
/// Example matches f
/// \code
///   void f();
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Decl, FunctionDecl> functionDecl;

/// \brief Matches C++ function template declarations.
///
/// Example matches f
/// \code
///   template<class T> void f(T t) {}
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Decl,
  FunctionTemplateDecl> functionTemplateDecl;

/// \brief Matches friend declarations.
///
/// Given
/// \code
///   class X { friend void foo(); };
/// \endcode
/// friendDecl()
///   matches 'friend void foo()'.
const internal::VariadicDynCastAllOfMatcher<Decl, FriendDecl> friendDecl;

/// \brief Matches statements.
///
/// Given
/// \code
///   { ++a; }
/// \endcode
/// stmt()
///   matches both the compound statement '{ ++a; }' and '++a'.
const internal::VariadicAllOfMatcher<Stmt> stmt;

/// \brief Matches declaration statements.
///
/// Given
/// \code
///   int a;
/// \endcode
/// declStmt()
///   matches 'int a'.
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  DeclStmt> declStmt;

/// \brief Matches member expressions.
///
/// Given
/// \code
///   class Y {
///     void x() { this->x(); x(); Y y; y.x(); a; this->b; Y::b; }
///     int a; static int b;
///   };
/// \endcode
/// memberExpr()
///   matches this->x, x, y.x, a, this->b
const internal::VariadicDynCastAllOfMatcher<Stmt, MemberExpr> memberExpr;

/// \brief Matches call expressions.
///
/// Example matches x.y() and y()
/// \code
///   X x;
///   x.y();
///   y();
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Stmt, CallExpr> callExpr;

/// \brief Matches lambda expressions.
///
/// Example matches [&](){return 5;}
/// \code
///   [&](){return 5;}
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Stmt, LambdaExpr> lambdaExpr;

/// \brief Matches member call expressions.
///
/// Example matches x.y()
/// \code
///   X x;
///   x.y();
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXMemberCallExpr> memberCallExpr;

/// \brief Matches init list expressions.
///
/// Given
/// \code
///   int a[] = { 1, 2 };
///   struct B { int x, y; };
///   B b = { 5, 6 };
/// \endcode
/// initList()
///   matches "{ 1, 2 }" and "{ 5, 6 }"
const internal::VariadicDynCastAllOfMatcher<Stmt, InitListExpr> initListExpr;

/// \brief Matches using declarations.
///
/// Given
/// \code
///   namespace X { int x; }
///   using X::x;
/// \endcode
/// usingDecl()
///   matches \code using X::x \endcode
const internal::VariadicDynCastAllOfMatcher<Decl, UsingDecl> usingDecl;

/// \brief Matches unresolved using value declarations.
///
/// Given
/// \code
///   template<typename X>
///   class C : private X {
///     using X::x;
///   };
/// \endcode
/// unresolvedUsingValueDecl()
///   matches \code using X::x \endcode
const internal::VariadicDynCastAllOfMatcher<
  Decl,
  UnresolvedUsingValueDecl> unresolvedUsingValueDecl;

/// \brief Matches constructor call expressions (including implicit ones).
///
/// Example matches string(ptr, n) and ptr within arguments of f
///     (matcher = constructExpr())
/// \code
///   void f(const string &a, const string &b);
///   char *ptr;
///   int n;
///   f(string(ptr, n), ptr);
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXConstructExpr> constructExpr;

/// \brief Matches unresolved constructor call expressions.
///
/// Example matches T(t) in return statement of f
///     (matcher = unresolvedConstructExpr())
/// \code
///   template <typename T>
///   void f(const T& t) { return T(t); }
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXUnresolvedConstructExpr> unresolvedConstructExpr;

/// \brief Matches implicit and explicit this expressions.
///
/// Example matches the implicit this expression in "return i".
///     (matcher = thisExpr())
/// \code
/// struct foo {
///   int i;
///   int f() { return i; }
/// };
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Stmt, CXXThisExpr> thisExpr;

/// \brief Matches nodes where temporaries are created.
///
/// Example matches FunctionTakesString(GetStringByValue())
///     (matcher = bindTemporaryExpr())
/// \code
///   FunctionTakesString(GetStringByValue());
///   FunctionTakesStringByPointer(GetStringPointer());
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXBindTemporaryExpr> bindTemporaryExpr;

/// \brief Matches nodes where temporaries are materialized.
///
/// Example: Given
/// \code
///   struct T {void func()};
///   T f();
///   void g(T);
/// \endcode
/// materializeTemporaryExpr() matches 'f()' in these statements
/// \code
///   T u(f());
///   g(f());
/// \endcode
/// but does not match
/// \code
///   f();
///   f().func();
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  MaterializeTemporaryExpr> materializeTemporaryExpr;

/// \brief Matches new expressions.
///
/// Given
/// \code
///   new X;
/// \endcode
/// newExpr()
///   matches 'new X'.
const internal::VariadicDynCastAllOfMatcher<Stmt, CXXNewExpr> newExpr;

/// \brief Matches delete expressions.
///
/// Given
/// \code
///   delete X;
/// \endcode
/// deleteExpr()
///   matches 'delete X'.
const internal::VariadicDynCastAllOfMatcher<Stmt, CXXDeleteExpr> deleteExpr;

/// \brief Matches array subscript expressions.
///
/// Given
/// \code
///   int i = a[1];
/// \endcode
/// arraySubscriptExpr()
///   matches "a[1]"
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  ArraySubscriptExpr> arraySubscriptExpr;

/// \brief Matches the value of a default argument at the call site.
///
/// Example matches the CXXDefaultArgExpr placeholder inserted for the
///     default value of the second parameter in the call expression f(42)
///     (matcher = defaultArgExpr())
/// \code
///   void f(int x, int y = 0);
///   f(42);
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXDefaultArgExpr> defaultArgExpr;

/// \brief Matches overloaded operator calls.
///
/// Note that if an operator isn't overloaded, it won't match. Instead, use
/// binaryOperator matcher.
/// Currently it does not match operators such as new delete.
/// FIXME: figure out why these do not match?
///
/// Example matches both operator<<((o << b), c) and operator<<(o, b)
///     (matcher = operatorCallExpr())
/// \code
///   ostream &operator<< (ostream &out, int i) { };
///   ostream &o; int b = 1, c = 1;
///   o << b << c;
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXOperatorCallExpr> operatorCallExpr;

/// \brief Matches expressions.
///
/// Example matches x()
/// \code
///   void f() { x(); }
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Stmt, Expr> expr;

/// \brief Matches expressions that refer to declarations.
///
/// Example matches x in if (x)
/// \code
///   bool x;
///   if (x) {}
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Stmt, DeclRefExpr> declRefExpr;

/// \brief Matches if statements.
///
/// Example matches 'if (x) {}'
/// \code
///   if (x) {}
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Stmt, IfStmt> ifStmt;

/// \brief Matches for statements.
///
/// Example matches 'for (;;) {}'
/// \code
///   for (;;) {}
///   int i[] =  {1, 2, 3}; for (auto a : i);
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Stmt, ForStmt> forStmt;

/// \brief Matches range-based for statements.
///
/// forRangeStmt() matches 'for (auto a : i)'
/// \code
///   int i[] =  {1, 2, 3}; for (auto a : i);
///   for(int j = 0; j < 5; ++j);
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Stmt, CXXForRangeStmt> forRangeStmt;

/// \brief Matches the increment statement of a for loop.
///
/// Example:
///     forStmt(hasIncrement(unaryOperator(hasOperatorName("++"))))
/// matches '++x' in
/// \code
///     for (x; x < N; ++x) { }
/// \endcode
AST_MATCHER_P(ForStmt, hasIncrement, internal::Matcher<Stmt>,
              InnerMatcher) {
  const Stmt *const Increment = Node.getInc();
  return (Increment != NULL &&
          InnerMatcher.matches(*Increment, Finder, Builder));
}

/// \brief Matches the initialization statement of a for loop.
///
/// Example:
///     forStmt(hasLoopInit(declStmt()))
/// matches 'int x = 0' in
/// \code
///     for (int x = 0; x < N; ++x) { }
/// \endcode
AST_MATCHER_P(ForStmt, hasLoopInit, internal::Matcher<Stmt>,
              InnerMatcher) {
  const Stmt *const Init = Node.getInit();
  return (Init != NULL && InnerMatcher.matches(*Init, Finder, Builder));
}

/// \brief Matches while statements.
///
/// Given
/// \code
///   while (true) {}
/// \endcode
/// whileStmt()
///   matches 'while (true) {}'.
const internal::VariadicDynCastAllOfMatcher<Stmt, WhileStmt> whileStmt;

/// \brief Matches do statements.
///
/// Given
/// \code
///   do {} while (true);
/// \endcode
/// doStmt()
///   matches 'do {} while(true)'
const internal::VariadicDynCastAllOfMatcher<Stmt, DoStmt> doStmt;

/// \brief Matches break statements.
///
/// Given
/// \code
///   while (true) { break; }
/// \endcode
/// breakStmt()
///   matches 'break'
const internal::VariadicDynCastAllOfMatcher<Stmt, BreakStmt> breakStmt;

/// \brief Matches continue statements.
///
/// Given
/// \code
///   while (true) { continue; }
/// \endcode
/// continueStmt()
///   matches 'continue'
const internal::VariadicDynCastAllOfMatcher<Stmt, ContinueStmt> continueStmt;

/// \brief Matches return statements.
///
/// Given
/// \code
///   return 1;
/// \endcode
/// returnStmt()
///   matches 'return 1'
const internal::VariadicDynCastAllOfMatcher<Stmt, ReturnStmt> returnStmt;

/// \brief Matches goto statements.
///
/// Given
/// \code
///   goto FOO;
///   FOO: bar();
/// \endcode
/// gotoStmt()
///   matches 'goto FOO'
const internal::VariadicDynCastAllOfMatcher<Stmt, GotoStmt> gotoStmt;

/// \brief Matches label statements.
///
/// Given
/// \code
///   goto FOO;
///   FOO: bar();
/// \endcode
/// labelStmt()
///   matches 'FOO:'
const internal::VariadicDynCastAllOfMatcher<Stmt, LabelStmt> labelStmt;

/// \brief Matches switch statements.
///
/// Given
/// \code
///   switch(a) { case 42: break; default: break; }
/// \endcode
/// switchStmt()
///   matches 'switch(a)'.
const internal::VariadicDynCastAllOfMatcher<Stmt, SwitchStmt> switchStmt;

/// \brief Matches case and default statements inside switch statements.
///
/// Given
/// \code
///   switch(a) { case 42: break; default: break; }
/// \endcode
/// switchCase()
///   matches 'case 42: break;' and 'default: break;'.
const internal::VariadicDynCastAllOfMatcher<Stmt, SwitchCase> switchCase;

/// \brief Matches case statements inside switch statements.
///
/// Given
/// \code
///   switch(a) { case 42: break; default: break; }
/// \endcode
/// caseStmt()
///   matches 'case 42: break;'.
const internal::VariadicDynCastAllOfMatcher<Stmt, CaseStmt> caseStmt;

/// \brief Matches default statements inside switch statements.
///
/// Given
/// \code
///   switch(a) { case 42: break; default: break; }
/// \endcode
/// defaultStmt()
///   matches 'default: break;'.
const internal::VariadicDynCastAllOfMatcher<Stmt, DefaultStmt> defaultStmt;

/// \brief Matches compound statements.
///
/// Example matches '{}' and '{{}}'in 'for (;;) {{}}'
/// \code
///   for (;;) {{}}
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Stmt, CompoundStmt> compoundStmt;

/// \brief Matches catch statements.
///
/// \code
///   try {} catch(int i) {}
/// \endcode
/// catchStmt()
///   matches 'catch(int i)'
const internal::VariadicDynCastAllOfMatcher<Stmt, CXXCatchStmt> catchStmt;

/// \brief Matches try statements.
///
/// \code
///   try {} catch(int i) {}
/// \endcode
/// tryStmt()
///   matches 'try {}'
const internal::VariadicDynCastAllOfMatcher<Stmt, CXXTryStmt> tryStmt;

/// \brief Matches throw expressions.
///
/// \code
///   try { throw 5; } catch(int i) {}
/// \endcode
/// throwExpr()
///   matches 'throw 5'
const internal::VariadicDynCastAllOfMatcher<Stmt, CXXThrowExpr> throwExpr;

/// \brief Matches null statements.
///
/// \code
///   foo();;
/// \endcode
/// nullStmt()
///   matches the second ';'
const internal::VariadicDynCastAllOfMatcher<Stmt, NullStmt> nullStmt;

/// \brief Matches asm statements.
///
/// \code
///  int i = 100;
///   __asm("mov al, 2");
/// \endcode
/// asmStmt()
///   matches '__asm("mov al, 2")'
const internal::VariadicDynCastAllOfMatcher<Stmt, AsmStmt> asmStmt;

/// \brief Matches bool literals.
///
/// Example matches true
/// \code
///   true
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXBoolLiteralExpr> boolLiteral;

/// \brief Matches string literals (also matches wide string literals).
///
/// Example matches "abcd", L"abcd"
/// \code
///   char *s = "abcd"; wchar_t *ws = L"abcd"
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  StringLiteral> stringLiteral;

/// \brief Matches character literals (also matches wchar_t).
///
/// Not matching Hex-encoded chars (e.g. 0x1234, which is a IntegerLiteral),
/// though.
///
/// Example matches 'a', L'a'
/// \code
///   char ch = 'a'; wchar_t chw = L'a';
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CharacterLiteral> characterLiteral;

/// \brief Matches integer literals of all sizes / encodings, e.g.
/// 1, 1L, 0x1 and 1U.
///
/// Does not match character-encoded integers such as L'a'.
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  IntegerLiteral> integerLiteral;

/// \brief Matches float literals of all sizes / encodings, e.g.
/// 1.0, 1.0f, 1.0L and 1e10.
///
/// Does not match implicit conversions such as
/// \code
///   float a = 10;
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  FloatingLiteral> floatLiteral;

/// \brief Matches user defined literal operator call.
///
/// Example match: "foo"_suffix
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  UserDefinedLiteral> userDefinedLiteral;

/// \brief Matches compound (i.e. non-scalar) literals
///
/// Example match: {1}, (1, 2)
/// \code
///   int array[4] = {1}; vector int myvec = (vector int)(1, 2);
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CompoundLiteralExpr> compoundLiteralExpr;

/// \brief Matches nullptr literal.
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXNullPtrLiteralExpr> nullPtrLiteralExpr;

/// \brief Matches binary operator expressions.
///
/// Example matches a || b
/// \code
///   !(a || b)
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  BinaryOperator> binaryOperator;

/// \brief Matches unary operator expressions.
///
/// Example matches !a
/// \code
///   !a || b
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  UnaryOperator> unaryOperator;

/// \brief Matches conditional operator expressions.
///
/// Example matches a ? b : c
/// \code
///   (a ? b : c) + 42
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  ConditionalOperator> conditionalOperator;

/// \brief Matches a reinterpret_cast expression.
///
/// Either the source expression or the destination type can be matched
/// using has(), but hasDestinationType() is more specific and can be
/// more readable.
///
/// Example matches reinterpret_cast<char*>(&p) in
/// \code
///   void* p = reinterpret_cast<char*>(&p);
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXReinterpretCastExpr> reinterpretCastExpr;

/// \brief Matches a C++ static_cast expression.
///
/// \see hasDestinationType
/// \see reinterpretCast
///
/// Example:
///   staticCastExpr()
/// matches
///   static_cast<long>(8)
/// in
/// \code
///   long eight(static_cast<long>(8));
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXStaticCastExpr> staticCastExpr;

/// \brief Matches a dynamic_cast expression.
///
/// Example:
///   dynamicCastExpr()
/// matches
///   dynamic_cast<D*>(&b);
/// in
/// \code
///   struct B { virtual ~B() {} }; struct D : B {};
///   B b;
///   D* p = dynamic_cast<D*>(&b);
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXDynamicCastExpr> dynamicCastExpr;

/// \brief Matches a const_cast expression.
///
/// Example: Matches const_cast<int*>(&r) in
/// \code
///   int n = 42;
///   const int &r(n);
///   int* p = const_cast<int*>(&r);
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXConstCastExpr> constCastExpr;

/// \brief Matches a C-style cast expression.
///
/// Example: Matches (int*) 2.2f in
/// \code
///   int i = (int) 2.2f;
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CStyleCastExpr> cStyleCastExpr;

/// \brief Matches explicit cast expressions.
///
/// Matches any cast expression written in user code, whether it be a
/// C-style cast, a functional-style cast, or a keyword cast.
///
/// Does not match implicit conversions.
///
/// Note: the name "explicitCast" is chosen to match Clang's terminology, as
/// Clang uses the term "cast" to apply to implicit conversions as well as to
/// actual cast expressions.
///
/// \see hasDestinationType.
///
/// Example: matches all five of the casts in
/// \code
///   int((int)(reinterpret_cast<int>(static_cast<int>(const_cast<int>(42)))))
/// \endcode
/// but does not match the implicit conversion in
/// \code
///   long ell = 42;
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  ExplicitCastExpr> explicitCastExpr;

/// \brief Matches the implicit cast nodes of Clang's AST.
///
/// This matches many different places, including function call return value
/// eliding, as well as any type conversions.
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  ImplicitCastExpr> implicitCastExpr;

/// \brief Matches any cast nodes of Clang's AST.
///
/// Example: castExpr() matches each of the following:
/// \code
///   (int) 3;
///   const_cast<Expr *>(SubExpr);
///   char c = 0;
/// \endcode
/// but does not match
/// \code
///   int i = (0);
///   int k = 0;
/// \endcode
const internal::VariadicDynCastAllOfMatcher<Stmt, CastExpr> castExpr;

/// \brief Matches functional cast expressions
///
/// Example: Matches Foo(bar);
/// \code
///   Foo f = bar;
///   Foo g = (Foo) bar;
///   Foo h = Foo(bar);
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXFunctionalCastExpr> functionalCastExpr;

/// \brief Matches functional cast expressions having N != 1 arguments
///
/// Example: Matches Foo(bar, bar)
/// \code
///   Foo h = Foo(bar, bar);
/// \endcode
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  CXXTemporaryObjectExpr> temporaryObjectExpr;

/// \brief Matches \c QualTypes in the clang AST.
const internal::VariadicAllOfMatcher<QualType> qualType;

/// \brief Matches \c Types in the clang AST.
const internal::VariadicAllOfMatcher<Type> type;

/// \brief Matches \c TypeLocs in the clang AST.
const internal::VariadicAllOfMatcher<TypeLoc> typeLoc;

/// \brief Matches if any of the given matchers matches.
///
/// Unlike \c anyOf, \c eachOf will generate a match result for each
/// matching submatcher.
///
/// For example, in:
/// \code
///   class A { int a; int b; };
/// \endcode
/// The matcher:
/// \code
///   recordDecl(eachOf(has(fieldDecl(hasName("a")).bind("v")),
///                     has(fieldDecl(hasName("b")).bind("v"))))
/// \endcode
/// will generate two results binding "v", the first of which binds
/// the field declaration of \c a, the second the field declaration of
/// \c b.
///
/// Usable as: Any Matcher
const internal::VariadicOperatorMatcherFunc eachOf = {
  internal::EachOfVariadicOperator
};

/// \brief Matches if any of the given matchers matches.
///
/// Usable as: Any Matcher
const internal::VariadicOperatorMatcherFunc anyOf = {
  internal::AnyOfVariadicOperator
};

/// \brief Matches if all given matchers match.
///
/// Usable as: Any Matcher
const internal::VariadicOperatorMatcherFunc allOf = {
  internal::AllOfVariadicOperator
};

/// \brief Matches sizeof (C99), alignof (C++11) and vec_step (OpenCL)
///
/// Given
/// \code
///   Foo x = bar;
///   int y = sizeof(x) + alignof(x);
/// \endcode
/// unaryExprOrTypeTraitExpr()
///   matches \c sizeof(x) and \c alignof(x)
const internal::VariadicDynCastAllOfMatcher<
  Stmt,
  UnaryExprOrTypeTraitExpr> unaryExprOrTypeTraitExpr;

/// \brief Matches unary expressions that have a specific type of argument.
///
/// Given
/// \code
///   int a, c; float b; int s = sizeof(a) + sizeof(b) + alignof(c);
/// \endcode
/// unaryExprOrTypeTraitExpr(hasArgumentOfType(asString("int"))
///   matches \c sizeof(a) and \c alignof(c)
AST_MATCHER_P(UnaryExprOrTypeTraitExpr, hasArgumentOfType,
              internal::Matcher<QualType>, InnerMatcher) {
  const QualType ArgumentType = Node.getTypeOfArgument();
  return InnerMatcher.matches(ArgumentType, Finder, Builder);
}

/// \brief Matches unary expressions of a certain kind.
///
/// Given
/// \code
///   int x;
///   int s = sizeof(x) + alignof(x)
/// \endcode
/// unaryExprOrTypeTraitExpr(ofKind(UETT_SizeOf))
///   matches \c sizeof(x)
AST_MATCHER_P(UnaryExprOrTypeTraitExpr, ofKind, UnaryExprOrTypeTrait, Kind) {
  return Node.getKind() == Kind;
}

/// \brief Same as unaryExprOrTypeTraitExpr, but only matching
/// alignof.
inline internal::Matcher<Stmt> alignOfExpr(
    const internal::Matcher<UnaryExprOrTypeTraitExpr> &InnerMatcher) {
  return stmt(unaryExprOrTypeTraitExpr(allOf(
      ofKind(UETT_AlignOf), InnerMatcher)));
}

/// \brief Same as unaryExprOrTypeTraitExpr, but only matching
/// sizeof.
inline internal::Matcher<Stmt> sizeOfExpr(
    const internal::Matcher<UnaryExprOrTypeTraitExpr> &InnerMatcher) {
  return stmt(unaryExprOrTypeTraitExpr(
      allOf(ofKind(UETT_SizeOf), InnerMatcher)));
}

/// \brief Matches NamedDecl nodes that have the specified name.
///
/// Supports specifying enclosing namespaces or classes by prefixing the name
/// with '<enclosing>::'.
/// Does not match typedefs of an underlying type with the given name.
///
/// Example matches X (Name == "X")
/// \code
///   class X;
/// \endcode
///
/// Example matches X (Name is one of "::a::b::X", "a::b::X", "b::X", "X")
/// \code
///   namespace a { namespace b { class X; } }
/// \endcode
AST_MATCHER_P(NamedDecl, hasName, std::string, Name) {
  assert(!Name.empty());
  const std::string FullNameString = "::" + Node.getQualifiedNameAsString();
  const StringRef FullName = FullNameString;
  const StringRef Pattern = Name;
  if (Pattern.startswith("::")) {
    return FullName == Pattern;
  } else {
    return FullName.endswith(("::" + Pattern).str());
  }
}

/// \brief Matches NamedDecl nodes whose fully qualified names contain
/// a substring matched by the given RegExp.
///
/// Supports specifying enclosing namespaces or classes by
/// prefixing the name with '<enclosing>::'.  Does not match typedefs
/// of an underlying type with the given name.
///
/// Example matches X (regexp == "::X")
/// \code
///   class X;
/// \endcode
///
/// Example matches X (regexp is one of "::X", "^foo::.*X", among others)
/// \code
///   namespace foo { namespace bar { class X; } }
/// \endcode
AST_MATCHER_P(NamedDecl, matchesName, std::string, RegExp) {
  assert(!RegExp.empty());
  std::string FullNameString = "::" + Node.getQualifiedNameAsString();
  llvm::Regex RE(RegExp);
  return RE.match(FullNameString);
}

/// \brief Matches overloaded operator names.
///
/// Matches overloaded operator names specified in strings without the
/// "operator" prefix: e.g. "<<".
///
/// Given:
/// \code
///   class A { int operator*(); };
///   const A &operator<<(const A &a, const A &b);
///   A a;
///   a << a;   // <-- This matches
/// \endcode
///
/// \c operatorCallExpr(hasOverloadedOperatorName("<<"))) matches the specified
/// line and \c recordDecl(hasMethod(hasOverloadedOperatorName("*"))) matches
/// the declaration of \c A.
///
/// Usable as: Matcher<CXXOperatorCallExpr>, Matcher<CXXMethodDecl>
inline internal::PolymorphicMatcherWithParam1<
    internal::HasOverloadedOperatorNameMatcher, StringRef,
    AST_POLYMORPHIC_SUPPORTED_TYPES_2(CXXOperatorCallExpr, CXXMethodDecl)>
hasOverloadedOperatorName(const StringRef Name) {
  return internal::PolymorphicMatcherWithParam1<
      internal::HasOverloadedOperatorNameMatcher, StringRef,
      AST_POLYMORPHIC_SUPPORTED_TYPES_2(CXXOperatorCallExpr, CXXMethodDecl)>(
      Name);
}

/// \brief Matches C++ classes that are directly or indirectly derived from
/// a class matching \c Base.
///
/// Note that a class is not considered to be derived from itself.
///
/// Example matches Y, Z, C (Base == hasName("X"))
/// \code
///   class X;
///   class Y : public X {};  // directly derived
///   class Z : public Y {};  // indirectly derived
///   typedef X A;
///   typedef A B;
///   class C : public B {};  // derived from a typedef of X
/// \endcode
///
/// In the following example, Bar matches isDerivedFrom(hasName("X")):
/// \code
///   class Foo;
///   typedef Foo X;
///   class Bar : public Foo {};  // derived from a type that X is a typedef of
/// \endcode
AST_MATCHER_P(CXXRecordDecl, isDerivedFrom,
              internal::Matcher<NamedDecl>, Base) {
  return Finder->classIsDerivedFrom(&Node, Base, Builder);
}

/// \brief Overloaded method as shortcut for \c isDerivedFrom(hasName(...)).
AST_MATCHER_P_OVERLOAD(CXXRecordDecl, isDerivedFrom, StringRef, BaseName, 1) {
  assert(!BaseName.empty());
  return isDerivedFrom(hasName(BaseName)).matches(Node, Finder, Builder);
}

/// \brief Similar to \c isDerivedFrom(), but also matches classes that directly
/// match \c Base.
AST_MATCHER_P_OVERLOAD(CXXRecordDecl, isSameOrDerivedFrom,
                       internal::Matcher<NamedDecl>, Base, 0) {
  return Matcher<CXXRecordDecl>(anyOf(Base, isDerivedFrom(Base)))
      .matches(Node, Finder, Builder);
}

/// \brief Overloaded method as shortcut for
/// \c isSameOrDerivedFrom(hasName(...)).
AST_MATCHER_P_OVERLOAD(CXXRecordDecl, isSameOrDerivedFrom, StringRef, BaseName,
                       1) {
  assert(!BaseName.empty());
  return isSameOrDerivedFrom(hasName(BaseName)).matches(Node, Finder, Builder);
}

/// \brief Matches the first method of a class or struct that satisfies \c
/// InnerMatcher.
///
/// Given:
/// \code
///   class A { void func(); };
///   class B { void member(); };
/// \code
///
/// \c recordDecl(hasMethod(hasName("func"))) matches the declaration of \c A
/// but not \c B.
AST_MATCHER_P(CXXRecordDecl, hasMethod, internal::Matcher<CXXMethodDecl>,
              InnerMatcher) {
  return matchesFirstInPointerRange(InnerMatcher, Node.method_begin(),
                                    Node.method_end(), Finder, Builder);
}

/// \brief Matches AST nodes that have child AST nodes that match the
/// provided matcher.
///
/// Example matches X, Y (matcher = recordDecl(has(recordDecl(hasName("X")))
/// \code
///   class X {};  // Matches X, because X::X is a class of name X inside X.
///   class Y { class X {}; };
///   class Z { class Y { class X {}; }; };  // Does not match Z.
/// \endcode
///
/// ChildT must be an AST base type.
///
/// Usable as: Any Matcher
const internal::ArgumentAdaptingMatcherFunc<internal::HasMatcher>
LLVM_ATTRIBUTE_UNUSED has = {};

/// \brief Matches AST nodes that have descendant AST nodes that match the
/// provided matcher.
///
/// Example matches X, Y, Z
///     (matcher = recordDecl(hasDescendant(recordDecl(hasName("X")))))
/// \code
///   class X {};  // Matches X, because X::X is a class of name X inside X.
///   class Y { class X {}; };
///   class Z { class Y { class X {}; }; };
/// \endcode
///
/// DescendantT must be an AST base type.
///
/// Usable as: Any Matcher
const internal::ArgumentAdaptingMatcherFunc<internal::HasDescendantMatcher>
LLVM_ATTRIBUTE_UNUSED hasDescendant = {};

/// \brief Matches AST nodes that have child AST nodes that match the
/// provided matcher.
///
/// Example matches X, Y (matcher = recordDecl(forEach(recordDecl(hasName("X")))
/// \code
///   class X {};  // Matches X, because X::X is a class of name X inside X.
///   class Y { class X {}; };
///   class Z { class Y { class X {}; }; };  // Does not match Z.
/// \endcode
///
/// ChildT must be an AST base type.
///
/// As opposed to 'has', 'forEach' will cause a match for each result that
/// matches instead of only on the first one.
///
/// Usable as: Any Matcher
const internal::ArgumentAdaptingMatcherFunc<internal::ForEachMatcher>
LLVM_ATTRIBUTE_UNUSED forEach = {};

/// \brief Matches AST nodes that have descendant AST nodes that match the
/// provided matcher.
///
/// Example matches X, A, B, C
///     (matcher = recordDecl(forEachDescendant(recordDecl(hasName("X")))))
/// \code
///   class X {};  // Matches X, because X::X is a class of name X inside X.
///   class A { class X {}; };
///   class B { class C { class X {}; }; };
/// \endcode
///
/// DescendantT must be an AST base type.
///
/// As opposed to 'hasDescendant', 'forEachDescendant' will cause a match for
/// each result that matches instead of only on the first one.
///
/// Note: Recursively combined ForEachDescendant can cause many matches:
///   recordDecl(forEachDescendant(recordDecl(forEachDescendant(recordDecl()))))
/// will match 10 times (plus injected class name matches) on:
/// \code
///   class A { class B { class C { class D { class E {}; }; }; }; };
/// \endcode
///
/// Usable as: Any Matcher
const internal::ArgumentAdaptingMatcherFunc<internal::ForEachDescendantMatcher>
LLVM_ATTRIBUTE_UNUSED forEachDescendant = {};

/// \brief Matches if the node or any descendant matches.
///
/// Generates results for each match.
///
/// For example, in:
/// \code
///   class A { class B {}; class C {}; };
/// \endcode
/// The matcher:
/// \code
///   recordDecl(hasName("::A"), findAll(recordDecl(isDefinition()).bind("m")))
/// \endcode
/// will generate results for \c A, \c B and \c C.
///
/// Usable as: Any Matcher
template <typename T>
internal::Matcher<T> findAll(const internal::Matcher<T> &Matcher) {
  return eachOf(Matcher, forEachDescendant(Matcher));
}

/// \brief Matches AST nodes that have a parent that matches the provided
/// matcher.
///
/// Given
/// \code
/// void f() { for (;;) { int x = 42; if (true) { int x = 43; } } }
/// \endcode
/// \c compoundStmt(hasParent(ifStmt())) matches "{ int x = 43; }".
///
/// Usable as: Any Matcher
const internal::ArgumentAdaptingMatcherFunc<
    internal::HasParentMatcher, internal::TypeList<Decl, Stmt>,
    internal::TypeList<Decl, Stmt> > LLVM_ATTRIBUTE_UNUSED hasParent = {};

/// \brief Matches AST nodes that have an ancestor that matches the provided
/// matcher.
///
/// Given
/// \code
/// void f() { if (true) { int x = 42; } }
/// void g() { for (;;) { int x = 43; } }
/// \endcode
/// \c expr(integerLiteral(hasAncestor(ifStmt()))) matches \c 42, but not 43.
///
/// Usable as: Any Matcher
const internal::ArgumentAdaptingMatcherFunc<
    internal::HasAncestorMatcher, internal::TypeList<Decl, Stmt>,
    internal::TypeList<Decl, Stmt> > LLVM_ATTRIBUTE_UNUSED hasAncestor = {};

/// \brief Matches if the provided matcher does not match.
///
/// Example matches Y (matcher = recordDecl(unless(hasName("X"))))
/// \code
///   class X {};
///   class Y {};
/// \endcode
///
/// Usable as: Any Matcher
template <typename M>
internal::PolymorphicMatcherWithParam1<internal::NotMatcher, M>
unless(const M &InnerMatcher) {
  return internal::PolymorphicMatcherWithParam1<
    internal::NotMatcher, M>(InnerMatcher);
}

/// \brief Matches a node if the declaration associated with that node
/// matches the given matcher.
///
/// The associated declaration is:
/// - for type nodes, the declaration of the underlying type
/// - for CallExpr, the declaration of the callee
/// - for MemberExpr, the declaration of the referenced member
/// - for CXXConstructExpr, the declaration of the constructor
///
/// Also usable as Matcher<T> for any T supporting the getDecl() member
/// function. e.g. various subtypes of clang::Type and various expressions.
///
/// Usable as: Matcher<CallExpr>, Matcher<CXXConstructExpr>,
///   Matcher<DeclRefExpr>, Matcher<EnumType>, Matcher<InjectedClassNameType>,
///   Matcher<LabelStmt>, Matcher<MemberExpr>, Matcher<QualType>,
///   Matcher<RecordType>, Matcher<TagType>,
///   Matcher<TemplateSpecializationType>, Matcher<TemplateTypeParmType>,
///   Matcher<TypedefType>, Matcher<UnresolvedUsingType>
inline internal::PolymorphicMatcherWithParam1<
    internal::HasDeclarationMatcher, internal::Matcher<Decl>,
    void(internal::HasDeclarationSupportedTypes)>
hasDeclaration(const internal::Matcher<Decl> &InnerMatcher) {
  return internal::PolymorphicMatcherWithParam1<
      internal::HasDeclarationMatcher, internal::Matcher<Decl>,
      void(internal::HasDeclarationSupportedTypes)>(InnerMatcher);
}

/// \brief Matches on the implicit object argument of a member call expression.
///
/// Example matches y.x() (matcher = callExpr(on(hasType(recordDecl(hasName("Y"))))))
/// \code
///   class Y { public: void x(); };
///   void z() { Y y; y.x(); }",
/// \endcode
///
/// FIXME: Overload to allow directly matching types?
AST_MATCHER_P(CXXMemberCallExpr, on, internal::Matcher<Expr>,
              InnerMatcher) {
  const Expr *ExprNode = Node.getImplicitObjectArgument()
                            ->IgnoreParenImpCasts();
  return (ExprNode != NULL &&
          InnerMatcher.matches(*ExprNode, Finder, Builder));
}

/// \brief Matches if the call expression's callee expression matches.
///
/// Given
/// \code
///   class Y { void x() { this->x(); x(); Y y; y.x(); } };
///   void f() { f(); }
/// \endcode
/// callExpr(callee(expr()))
///   matches this->x(), x(), y.x(), f()
/// with callee(...)
///   matching this->x, x, y.x, f respectively
///
/// Note: Callee cannot take the more general internal::Matcher<Expr>
/// because this introduces ambiguous overloads with calls to Callee taking a
/// internal::Matcher<Decl>, as the matcher hierarchy is purely
/// implemented in terms of implicit casts.
AST_MATCHER_P(CallExpr, callee, internal::Matcher<Stmt>,
              InnerMatcher) {
  const Expr *ExprNode = Node.getCallee();
  return (ExprNode != NULL &&
          InnerMatcher.matches(*ExprNode, Finder, Builder));
}

/// \brief Matches if the call expression's callee's declaration matches the
/// given matcher.
///
/// Example matches y.x() (matcher = callExpr(callee(methodDecl(hasName("x")))))
/// \code
///   class Y { public: void x(); };
///   void z() { Y y; y.x();
/// \endcode
AST_MATCHER_P_OVERLOAD(CallExpr, callee, internal::Matcher<Decl>, InnerMatcher,
                       1) {
  return callExpr(hasDeclaration(InnerMatcher)).matches(Node, Finder, Builder);
}

/// \brief Matches if the expression's or declaration's type matches a type
/// matcher.
///
/// Example matches x (matcher = expr(hasType(recordDecl(hasName("X")))))
///             and z (matcher = varDecl(hasType(recordDecl(hasName("X")))))
/// \code
///  class X {};
///  void y(X &x) { x; X z; }
/// \endcode
AST_POLYMORPHIC_MATCHER_P_OVERLOAD(
    hasType, AST_POLYMORPHIC_SUPPORTED_TYPES_2(Expr, ValueDecl),
    internal::Matcher<QualType>, InnerMatcher, 0) {
  return InnerMatcher.matches(Node.getType(), Finder, Builder);
}

/// \brief Overloaded to match the declaration of the expression's or value
/// declaration's type.
///
/// In case of a value declaration (for example a variable declaration),
/// this resolves one layer of indirection. For example, in the value
/// declaration "X x;", recordDecl(hasName("X")) matches the declaration of X,
/// while varDecl(hasType(recordDecl(hasName("X")))) matches the declaration
/// of x."
///
/// Example matches x (matcher = expr(hasType(recordDecl(hasName("X")))))
///             and z (matcher = varDecl(hasType(recordDecl(hasName("X")))))
/// \code
///  class X {};
///  void y(X &x) { x; X z; }
/// \endcode
///
/// Usable as: Matcher<Expr>, Matcher<ValueDecl>
AST_POLYMORPHIC_MATCHER_P_OVERLOAD(
    hasType, AST_POLYMORPHIC_SUPPORTED_TYPES_2(Expr, ValueDecl),
    internal::Matcher<Decl>, InnerMatcher, 1) {
  return qualType(hasDeclaration(InnerMatcher))
      .matches(Node.getType(), Finder, Builder);
}

/// \brief Matches if the type location of the declarator decl's type matches
/// the inner matcher.
///
/// Given
/// \code
///   int x;
/// \endcode
/// declaratorDecl(hasTypeLoc(loc(asString("int"))))
///   matches int x
AST_MATCHER_P(DeclaratorDecl, hasTypeLoc, internal::Matcher<TypeLoc>, Inner) {
  if (!Node.getTypeSourceInfo())
    // This happens for example for implicit destructors.
    return false;
  return Inner.matches(Node.getTypeSourceInfo()->getTypeLoc(), Finder, Builder);
}

/// \brief Matches if the matched type is represented by the given string.
///
/// Given
/// \code
///   class Y { public: void x(); };
///   void z() { Y* y; y->x(); }
/// \endcode
/// callExpr(on(hasType(asString("class Y *"))))
///   matches y->x()
AST_MATCHER_P(QualType, asString, std::string, Name) {
  return Name == Node.getAsString();
}

/// \brief Matches if the matched type is a pointer type and the pointee type
/// matches the specified matcher.
///
/// Example matches y->x()
///     (matcher = callExpr(on(hasType(pointsTo(recordDecl(hasName("Y")))))))
/// \code
///   class Y { public: void x(); };
///   void z() { Y *y; y->x(); }
/// \endcode
AST_MATCHER_P(
    QualType, pointsTo, internal::Matcher<QualType>,
    InnerMatcher) {
  return (!Node.isNull() && Node->isPointerType() &&
          InnerMatcher.matches(Node->getPointeeType(), Finder, Builder));
}

/// \brief Overloaded to match the pointee type's declaration.
AST_MATCHER_P_OVERLOAD(QualType, pointsTo, internal::Matcher<Decl>,
                       InnerMatcher, 1) {
  return pointsTo(qualType(hasDeclaration(InnerMatcher)))
      .matches(Node, Finder, Builder);
}

/// \brief Matches if the matched type is a reference type and the referenced
/// type matches the specified matcher.
///
/// Example matches X &x and const X &y
///     (matcher = varDecl(hasType(references(recordDecl(hasName("X"))))))
/// \code
///   class X {
///     void a(X b) {
///       X &x = b;
///       const X &y = b;
///   };
/// \endcode
AST_MATCHER_P(QualType, references, internal::Matcher<QualType>,
              InnerMatcher) {
  return (!Node.isNull() && Node->isReferenceType() &&
          InnerMatcher.matches(Node->getPointeeType(), Finder, Builder));
}

/// \brief Matches QualTypes whose canonical type matches InnerMatcher.
///
/// Given:
/// \code
///   typedef int &int_ref;
///   int a;
///   int_ref b = a;
/// \code
///
/// \c varDecl(hasType(qualType(referenceType()))))) will not match the
/// declaration of b but \c
/// varDecl(hasType(qualType(hasCanonicalType(referenceType())))))) does.
AST_MATCHER_P(QualType, hasCanonicalType, internal::Matcher<QualType>,
              InnerMatcher) {
  if (Node.isNull())
    return false;
  return InnerMatcher.matches(Node.getCanonicalType(), Finder, Builder);
}

/// \brief Overloaded to match the referenced type's declaration.
AST_MATCHER_P_OVERLOAD(QualType, references, internal::Matcher<Decl>,
                       InnerMatcher, 1) {
  return references(qualType(hasDeclaration(InnerMatcher)))
      .matches(Node, Finder, Builder);
}

AST_MATCHER_P(CXXMemberCallExpr, onImplicitObjectArgument,
              internal::Matcher<Expr>, InnerMatcher) {
  const Expr *ExprNode = Node.getImplicitObjectArgument();
  return (ExprNode != NULL &&
          InnerMatcher.matches(*ExprNode, Finder, Builder));
}

/// \brief Matches if the expression's type either matches the specified
/// matcher, or is a pointer to a type that matches the InnerMatcher.
AST_MATCHER_P_OVERLOAD(CXXMemberCallExpr, thisPointerType,
                       internal::Matcher<QualType>, InnerMatcher, 0) {
  return onImplicitObjectArgument(
      anyOf(hasType(InnerMatcher), hasType(pointsTo(InnerMatcher))))
      .matches(Node, Finder, Builder);
}

/// \brief Overloaded to match the type's declaration.
AST_MATCHER_P_OVERLOAD(CXXMemberCallExpr, thisPointerType,
                       internal::Matcher<Decl>, InnerMatcher, 1) {
  return onImplicitObjectArgument(
      anyOf(hasType(InnerMatcher), hasType(pointsTo(InnerMatcher))))
      .matches(Node, Finder, Builder);
}

/// \brief Matches a DeclRefExpr that refers to a declaration that matches the
/// specified matcher.
///
/// Example matches x in if(x)
///     (matcher = declRefExpr(to(varDecl(hasName("x")))))
/// \code
///   bool x;
///   if (x) {}
/// \endcode
AST_MATCHER_P(DeclRefExpr, to, internal::Matcher<Decl>,
              InnerMatcher) {
  const Decl *DeclNode = Node.getDecl();
  return (DeclNode != NULL &&
          InnerMatcher.matches(*DeclNode, Finder, Builder));
}

/// \brief Matches a \c DeclRefExpr that refers to a declaration through a
/// specific using shadow declaration.
///
/// FIXME: This currently only works for functions. Fix.
///
/// Given
/// \code
///   namespace a { void f() {} }
///   using a::f;
///   void g() {
///     f();     // Matches this ..
///     a::f();  // .. but not this.
///   }
/// \endcode
/// declRefExpr(throughUsingDeclaration(anything()))
///   matches \c f()
AST_MATCHER_P(DeclRefExpr, throughUsingDecl,
              internal::Matcher<UsingShadowDecl>, InnerMatcher) {
  const NamedDecl *FoundDecl = Node.getFoundDecl();
  if (const UsingShadowDecl *UsingDecl = dyn_cast<UsingShadowDecl>(FoundDecl))
    return InnerMatcher.matches(*UsingDecl, Finder, Builder);
  return false;
}

/// \brief Matches the Decl of a DeclStmt which has a single declaration.
///
/// Given
/// \code
///   int a, b;
///   int c;
/// \endcode
/// declStmt(hasSingleDecl(anything()))
///   matches 'int c;' but not 'int a, b;'.
AST_MATCHER_P(DeclStmt, hasSingleDecl, internal::Matcher<Decl>, InnerMatcher) {
  if (Node.isSingleDecl()) {
    const Decl *FoundDecl = Node.getSingleDecl();
    return InnerMatcher.matches(*FoundDecl, Finder, Builder);
  }
  return false;
}

/// \brief Matches a variable declaration that has an initializer expression
/// that matches the given matcher.
///
/// Example matches x (matcher = varDecl(hasInitializer(callExpr())))
/// \code
///   bool y() { return true; }
///   bool x = y();
/// \endcode
AST_MATCHER_P(
    VarDecl, hasInitializer, internal::Matcher<Expr>,
    InnerMatcher) {
  const Expr *Initializer = Node.getAnyInitializer();
  return (Initializer != NULL &&
          InnerMatcher.matches(*Initializer, Finder, Builder));
}

/// \brief Checks that a call expression or a constructor call expression has
/// a specific number of arguments (including absent default arguments).
///
/// Example matches f(0, 0) (matcher = callExpr(argumentCountIs(2)))
/// \code
///   void f(int x, int y);
///   f(0, 0);
/// \endcode
AST_POLYMORPHIC_MATCHER_P(argumentCountIs, AST_POLYMORPHIC_SUPPORTED_TYPES_2(
                                               CallExpr, CXXConstructExpr),
                          unsigned, N) {
  return Node.getNumArgs() == N;
}

/// \brief Matches the n'th argument of a call expression or a constructor
/// call expression.
///
/// Example matches y in x(y)
///     (matcher = callExpr(hasArgument(0, declRefExpr())))
/// \code
///   void x(int) { int y; x(y); }
/// \endcode
AST_POLYMORPHIC_MATCHER_P2(
    hasArgument,
    AST_POLYMORPHIC_SUPPORTED_TYPES_2(CallExpr, CXXConstructExpr),
    unsigned, N, internal::Matcher<Expr>, InnerMatcher) {
  return (N < Node.getNumArgs() &&
          InnerMatcher.matches(
              *Node.getArg(N)->IgnoreParenImpCasts(), Finder, Builder));
}

/// \brief Matches declaration statements that contain a specific number of
/// declarations.
///
/// Example: Given
/// \code
///   int a, b;
///   int c;
///   int d = 2, e;
/// \endcode
/// declCountIs(2)
///   matches 'int a, b;' and 'int d = 2, e;', but not 'int c;'.
AST_MATCHER_P(DeclStmt, declCountIs, unsigned, N) {
  return std::distance(Node.decl_begin(), Node.decl_end()) == (ptrdiff_t)N;
}

/// \brief Matches the n'th declaration of a declaration statement.
///
/// Note that this does not work for global declarations because the AST
/// breaks up multiple-declaration DeclStmt's into multiple single-declaration
/// DeclStmt's.
/// Example: Given non-global declarations
/// \code
///   int a, b = 0;
///   int c;
///   int d = 2, e;
/// \endcode
/// declStmt(containsDeclaration(
///       0, varDecl(hasInitializer(anything()))))
///   matches only 'int d = 2, e;', and
/// declStmt(containsDeclaration(1, varDecl()))
/// \code
///   matches 'int a, b = 0' as well as 'int d = 2, e;'
///   but 'int c;' is not matched.
/// \endcode
AST_MATCHER_P2(DeclStmt, containsDeclaration, unsigned, N,
               internal::Matcher<Decl>, InnerMatcher) {
  const unsigned NumDecls = std::distance(Node.decl_begin(), Node.decl_end());
  if (N >= NumDecls)
    return false;
  DeclStmt::const_decl_iterator Iterator = Node.decl_begin();
  std::advance(Iterator, N);
  return InnerMatcher.matches(**Iterator, Finder, Builder);
}

/// \brief Matches a constructor initializer.
///
/// Given
/// \code
///   struct Foo {
///     Foo() : foo_(1) { }
///     int foo_;
///   };
/// \endcode
/// recordDecl(has(constructorDecl(hasAnyConstructorInitializer(anything()))))
///   record matches Foo, hasAnyConstructorInitializer matches foo_(1)
AST_MATCHER_P(CXXConstructorDecl, hasAnyConstructorInitializer,
              internal::Matcher<CXXCtorInitializer>, InnerMatcher) {
  return matchesFirstInPointerRange(InnerMatcher, Node.init_begin(),
                                    Node.init_end(), Finder, Builder);
}

/// \brief Matches the field declaration of a constructor initializer.
///
/// Given
/// \code
///   struct Foo {
///     Foo() : foo_(1) { }
///     int foo_;
///   };
/// \endcode
/// recordDecl(has(constructorDecl(hasAnyConstructorInitializer(
///     forField(hasName("foo_"))))))
///   matches Foo
/// with forField matching foo_
AST_MATCHER_P(CXXCtorInitializer, forField,
              internal::Matcher<FieldDecl>, InnerMatcher) {
  const FieldDecl *NodeAsDecl = Node.getMember();
  return (NodeAsDecl != NULL &&
      InnerMatcher.matches(*NodeAsDecl, Finder, Builder));
}

/// \brief Matches the initializer expression of a constructor initializer.
///
/// Given
/// \code
///   struct Foo {
///     Foo() : foo_(1) { }
///     int foo_;
///   };
/// \endcode
/// recordDecl(has(constructorDecl(hasAnyConstructorInitializer(
///     withInitializer(integerLiteral(equals(1)))))))
///   matches Foo
/// with withInitializer matching (1)
AST_MATCHER_P(CXXCtorInitializer, withInitializer,
              internal::Matcher<Expr>, InnerMatcher) {
  const Expr* NodeAsExpr = Node.getInit();
  return (NodeAsExpr != NULL &&
      InnerMatcher.matches(*NodeAsExpr, Finder, Builder));
}

/// \brief Matches a constructor initializer if it is explicitly written in
/// code (as opposed to implicitly added by the compiler).
///
/// Given
/// \code
///   struct Foo {
///     Foo() { }
///     Foo(int) : foo_("A") { }
///     string foo_;
///   };
/// \endcode
/// constructorDecl(hasAnyConstructorInitializer(isWritten()))
///   will match Foo(int), but not Foo()
AST_MATCHER(CXXCtorInitializer, isWritten) {
  return Node.isWritten();
}

/// \brief Matches a constructor declaration that has been implicitly added
/// by the compiler (eg. implicit default/copy constructors).
AST_MATCHER(CXXConstructorDecl, isImplicit) {
  return Node.isImplicit();
}

/// \brief Matches any argument of a call expression or a constructor call
/// expression.
///
/// Given
/// \code
///   void x(int, int, int) { int y; x(1, y, 42); }
/// \endcode
/// callExpr(hasAnyArgument(declRefExpr()))
///   matches x(1, y, 42)
/// with hasAnyArgument(...)
///   matching y
///
/// FIXME: Currently this will ignore parentheses and implicit casts on
/// the argument before applying the inner matcher. We'll want to remove
/// this to allow for greater control by the user once \c ignoreImplicit()
/// has been implemented.
AST_POLYMORPHIC_MATCHER_P(hasAnyArgument, AST_POLYMORPHIC_SUPPORTED_TYPES_2(
                                              CallExpr, CXXConstructExpr),
                          internal::Matcher<Expr>, InnerMatcher) {
  for (unsigned I = 0; I < Node.getNumArgs(); ++I) {
    BoundNodesTreeBuilder Result(*Builder);
    if (InnerMatcher.matches(*Node.getArg(I)->IgnoreParenImpCasts(), Finder,
                             &Result)) {
      *Builder = Result;
      return true;
    }
  }
  return false;
}

/// \brief Matches the n'th parameter of a function declaration.
///
/// Given
/// \code
///   class X { void f(int x) {} };
/// \endcode
/// methodDecl(hasParameter(0, hasType(varDecl())))
///   matches f(int x) {}
/// with hasParameter(...)
///   matching int x
AST_MATCHER_P2(FunctionDecl, hasParameter,
               unsigned, N, internal::Matcher<ParmVarDecl>,
               InnerMatcher) {
  return (N < Node.getNumParams() &&
          InnerMatcher.matches(
              *Node.getParamDecl(N), Finder, Builder));
}

/// \brief Matches any parameter of a function declaration.
///
/// Does not match the 'this' parameter of a method.
///
/// Given
/// \code
///   class X { void f(int x, int y, int z) {} };
/// \endcode
/// methodDecl(hasAnyParameter(hasName("y")))
///   matches f(int x, int y, int z) {}
/// with hasAnyParameter(...)
///   matching int y
AST_MATCHER_P(FunctionDecl, hasAnyParameter,
              internal::Matcher<ParmVarDecl>, InnerMatcher) {
  return matchesFirstInPointerRange(InnerMatcher, Node.param_begin(),
                                    Node.param_end(), Finder, Builder);
}

/// \brief Matches \c FunctionDecls that have a specific parameter count.
///
/// Given
/// \code
///   void f(int i) {}
///   void g(int i, int j) {}
/// \endcode
/// functionDecl(parameterCountIs(2))
///   matches g(int i, int j) {}
AST_MATCHER_P(FunctionDecl, parameterCountIs, unsigned, N) {
  return Node.getNumParams() == N;
}

/// \brief Matches the return type of a function declaration.
///
/// Given:
/// \code
///   class X { int f() { return 1; } };
/// \endcode
/// methodDecl(returns(asString("int")))
///   matches int f() { return 1; }
AST_MATCHER_P(FunctionDecl, returns,
              internal::Matcher<QualType>, InnerMatcher) {
  return InnerMatcher.matches(Node.getResultType(), Finder, Builder);
}

/// \brief Matches extern "C" function declarations.
///
/// Given:
/// \code
///   extern "C" void f() {}
///   extern "C" { void g() {} }
///   void h() {}
/// \endcode
/// functionDecl(isExternC())
///   matches the declaration of f and g, but not the declaration h
AST_MATCHER(FunctionDecl, isExternC) {
  return Node.isExternC();
}

/// \brief Matches the condition expression of an if statement, for loop,
/// or conditional operator.
///
/// Example matches true (matcher = hasCondition(boolLiteral(equals(true))))
/// \code
///   if (true) {}
/// \endcode
AST_POLYMORPHIC_MATCHER_P(
    hasCondition, AST_POLYMORPHIC_SUPPORTED_TYPES_5(
                      IfStmt, ForStmt, WhileStmt, DoStmt, ConditionalOperator),
    internal::Matcher<Expr>, InnerMatcher) {
  const Expr *const Condition = Node.getCond();
  return (Condition != NULL &&
          InnerMatcher.matches(*Condition, Finder, Builder));
}

namespace internal {
struct NotEqualsBoundNodePredicate {
  bool operator()(const internal::BoundNodesMap &Nodes) const {
    return Nodes.getNode(ID) != Node;
  }
  std::string ID;
  ast_type_traits::DynTypedNode Node;
};
} // namespace internal

/// \brief Matches if a node equals a previously bound node.
///
/// Matches a node if it equals the node previously bound to \p ID.
///
/// Given
/// \code
///   class X { int a; int b; };
/// \endcode
/// recordDecl(
///     has(fieldDecl(hasName("a"), hasType(type().bind("t")))),
///     has(fieldDecl(hasName("b"), hasType(type(equalsBoundNode("t"))))))
///   matches the class \c X, as \c a and \c b have the same type.
///
/// Note that when multiple matches are involved via \c forEach* matchers,
/// \c equalsBoundNodes acts as a filter.
/// For example:
/// compoundStmt(
///     forEachDescendant(varDecl().bind("d")),
///     forEachDescendant(declRefExpr(to(decl(equalsBoundNode("d"))))))
/// will trigger a match for each combination of variable declaration
/// and reference to that variable declaration within a compound statement.
AST_POLYMORPHIC_MATCHER_P(equalsBoundNode, AST_POLYMORPHIC_SUPPORTED_TYPES_4(
                                               Stmt, Decl, Type, QualType),
                          std::string, ID) {
  // FIXME: Figure out whether it makes sense to allow this
  // on any other node types.
  // For *Loc it probably does not make sense, as those seem
  // unique. For NestedNameSepcifier it might make sense, as
  // those also have pointer identity, but I'm not sure whether
  // they're ever reused.
  internal::NotEqualsBoundNodePredicate Predicate;
  Predicate.ID = ID;
  Predicate.Node = ast_type_traits::DynTypedNode::create(Node);
  return Builder->removeBindings(Predicate);
}

/// \brief Matches the condition variable statement in an if statement.
///
/// Given
/// \code
///   if (A* a = GetAPointer()) {}
/// \endcode
/// hasConditionVariableStatement(...)
///   matches 'A* a = GetAPointer()'.
AST_MATCHER_P(IfStmt, hasConditionVariableStatement,
              internal::Matcher<DeclStmt>, InnerMatcher) {
  const DeclStmt* const DeclarationStatement =
    Node.getConditionVariableDeclStmt();
  return DeclarationStatement != NULL &&
         InnerMatcher.matches(*DeclarationStatement, Finder, Builder);
}

/// \brief Matches the index expression of an array subscript expression.
///
/// Given
/// \code
///   int i[5];
///   void f() { i[1] = 42; }
/// \endcode
/// arraySubscriptExpression(hasIndex(integerLiteral()))
///   matches \c i[1] with the \c integerLiteral() matching \c 1
AST_MATCHER_P(ArraySubscriptExpr, hasIndex,
              internal::Matcher<Expr>, InnerMatcher) {
  if (const Expr* Expression = Node.getIdx())
    return InnerMatcher.matches(*Expression, Finder, Builder);
  return false;
}

/// \brief Matches the base expression of an array subscript expression.
///
/// Given
/// \code
///   int i[5];
///   void f() { i[1] = 42; }
/// \endcode
/// arraySubscriptExpression(hasBase(implicitCastExpr(
///     hasSourceExpression(declRefExpr()))))
///   matches \c i[1] with the \c declRefExpr() matching \c i
AST_MATCHER_P(ArraySubscriptExpr, hasBase,
              internal::Matcher<Expr>, InnerMatcher) {
  if (const Expr* Expression = Node.getBase())
    return InnerMatcher.matches(*Expression, Finder, Builder);
  return false;
}

/// \brief Matches a 'for', 'while', or 'do while' statement that has
/// a given body.
///
/// Given
/// \code
///   for (;;) {}
/// \endcode
/// hasBody(compoundStmt())
///   matches 'for (;;) {}'
/// with compoundStmt()
///   matching '{}'
AST_POLYMORPHIC_MATCHER_P(
    hasBody, AST_POLYMORPHIC_SUPPORTED_TYPES_3(DoStmt, ForStmt, WhileStmt),
    internal::Matcher<Stmt>, InnerMatcher) {
  const Stmt *const Statement = Node.getBody();
  return (Statement != NULL &&
          InnerMatcher.matches(*Statement, Finder, Builder));
}

/// \brief Matches compound statements where at least one substatement matches
/// a given matcher.
///
/// Given
/// \code
///   { {}; 1+2; }
/// \endcode
/// hasAnySubstatement(compoundStmt())
///   matches '{ {}; 1+2; }'
/// with compoundStmt()
///   matching '{}'
AST_MATCHER_P(CompoundStmt, hasAnySubstatement,
              internal::Matcher<Stmt>, InnerMatcher) {
  return matchesFirstInPointerRange(InnerMatcher, Node.body_begin(),
                                    Node.body_end(), Finder, Builder);
}

/// \brief Checks that a compound statement contains a specific number of
/// child statements.
///
/// Example: Given
/// \code
///   { for (;;) {} }
/// \endcode
/// compoundStmt(statementCountIs(0)))
///   matches '{}'
///   but does not match the outer compound statement.
AST_MATCHER_P(CompoundStmt, statementCountIs, unsigned, N) {
  return Node.size() == N;
}

/// \brief Matches literals that are equal to the given value.
///
/// Example matches true (matcher = boolLiteral(equals(true)))
/// \code
///   true
/// \endcode
///
/// Usable as: Matcher<CharacterLiteral>, Matcher<CXXBoolLiteral>,
///            Matcher<FloatingLiteral>, Matcher<IntegerLiteral>
template <typename ValueT>
internal::PolymorphicMatcherWithParam1<internal::ValueEqualsMatcher, ValueT>
equals(const ValueT &Value) {
  return internal::PolymorphicMatcherWithParam1<
    internal::ValueEqualsMatcher,
    ValueT>(Value);
}

/// \brief Matches the operator Name of operator expressions (binary or
/// unary).
///
/// Example matches a || b (matcher = binaryOperator(hasOperatorName("||")))
/// \code
///   !(a || b)
/// \endcode
AST_POLYMORPHIC_MATCHER_P(hasOperatorName, AST_POLYMORPHIC_SUPPORTED_TYPES_2(
                                               BinaryOperator, UnaryOperator),
                          std::string, Name) {
  return Name == Node.getOpcodeStr(Node.getOpcode());
}

/// \brief Matches the left hand side of binary operator expressions.
///
/// Example matches a (matcher = binaryOperator(hasLHS()))
/// \code
///   a || b
/// \endcode
AST_MATCHER_P(BinaryOperator, hasLHS,
              internal::Matcher<Expr>, InnerMatcher) {
  Expr *LeftHandSide = Node.getLHS();
  return (LeftHandSide != NULL &&
          InnerMatcher.matches(*LeftHandSide, Finder, Builder));
}

/// \brief Matches the right hand side of binary operator expressions.
///
/// Example matches b (matcher = binaryOperator(hasRHS()))
/// \code
///   a || b
/// \endcode
AST_MATCHER_P(BinaryOperator, hasRHS,
              internal::Matcher<Expr>, InnerMatcher) {
  Expr *RightHandSide = Node.getRHS();
  return (RightHandSide != NULL &&
          InnerMatcher.matches(*RightHandSide, Finder, Builder));
}

/// \brief Matches if either the left hand side or the right hand side of a
/// binary operator matches.
inline internal::Matcher<BinaryOperator> hasEitherOperand(
    const internal::Matcher<Expr> &InnerMatcher) {
  return anyOf(hasLHS(InnerMatcher), hasRHS(InnerMatcher));
}

/// \brief Matches if the operand of a unary operator matches.
///
/// Example matches true (matcher = hasUnaryOperand(boolLiteral(equals(true))))
/// \code
///   !true
/// \endcode
AST_MATCHER_P(UnaryOperator, hasUnaryOperand,
              internal::Matcher<Expr>, InnerMatcher) {
  const Expr * const Operand = Node.getSubExpr();
  return (Operand != NULL &&
          InnerMatcher.matches(*Operand, Finder, Builder));
}

/// \brief Matches if the cast's source expression matches the given matcher.
///
/// Example: matches "a string" (matcher =
///                                  hasSourceExpression(constructExpr()))
/// \code
/// class URL { URL(string); };
/// URL url = "a string";
AST_MATCHER_P(CastExpr, hasSourceExpression,
              internal::Matcher<Expr>, InnerMatcher) {
  const Expr* const SubExpression = Node.getSubExpr();
  return (SubExpression != NULL &&
          InnerMatcher.matches(*SubExpression, Finder, Builder));
}

/// \brief Matches casts whose destination type matches a given matcher.
///
/// (Note: Clang's AST refers to other conversions as "casts" too, and calls
/// actual casts "explicit" casts.)
AST_MATCHER_P(ExplicitCastExpr, hasDestinationType,
              internal::Matcher<QualType>, InnerMatcher) {
  const QualType NodeType = Node.getTypeAsWritten();
  return InnerMatcher.matches(NodeType, Finder, Builder);
}

/// \brief Matches implicit casts whose destination type matches a given
/// matcher.
///
/// FIXME: Unit test this matcher
AST_MATCHER_P(ImplicitCastExpr, hasImplicitDestinationType,
              internal::Matcher<QualType>, InnerMatcher) {
  return InnerMatcher.matches(Node.getType(), Finder, Builder);
}

/// \brief Matches the true branch expression of a conditional operator.
///
/// Example matches a
/// \code
///   condition ? a : b
/// \endcode
AST_MATCHER_P(ConditionalOperator, hasTrueExpression,
              internal::Matcher<Expr>, InnerMatcher) {
  Expr *Expression = Node.getTrueExpr();
  return (Expression != NULL &&
          InnerMatcher.matches(*Expression, Finder, Builder));
}

/// \brief Matches the false branch expression of a conditional operator.
///
/// Example matches b
/// \code
///   condition ? a : b
/// \endcode
AST_MATCHER_P(ConditionalOperator, hasFalseExpression,
              internal::Matcher<Expr>, InnerMatcher) {
  Expr *Expression = Node.getFalseExpr();
  return (Expression != NULL &&
          InnerMatcher.matches(*Expression, Finder, Builder));
}

/// \brief Matches if a declaration has a body attached.
///
/// Example matches A, va, fa
/// \code
///   class A {};
///   class B;  // Doesn't match, as it has no body.
///   int va;
///   extern int vb;  // Doesn't match, as it doesn't define the variable.
///   void fa() {}
///   void fb();  // Doesn't match, as it has no body.
/// \endcode
///
/// Usable as: Matcher<TagDecl>, Matcher<VarDecl>, Matcher<FunctionDecl>
AST_POLYMORPHIC_MATCHER(isDefinition, AST_POLYMORPHIC_SUPPORTED_TYPES_3(
                                          TagDecl, VarDecl, FunctionDecl)) {
  return Node.isThisDeclarationADefinition();
}

/// \brief Matches the class declaration that the given method declaration
/// belongs to.
///
/// FIXME: Generalize this for other kinds of declarations.
/// FIXME: What other kind of declarations would we need to generalize
/// this to?
///
/// Example matches A() in the last line
///     (matcher = constructExpr(hasDeclaration(methodDecl(
///         ofClass(hasName("A"))))))
/// \code
///   class A {
///    public:
///     A();
///   };
///   A a = A();
/// \endcode
AST_MATCHER_P(CXXMethodDecl, ofClass,
              internal::Matcher<CXXRecordDecl>, InnerMatcher) {
  const CXXRecordDecl *Parent = Node.getParent();
  return (Parent != NULL &&
          InnerMatcher.matches(*Parent, Finder, Builder));
}

/// \brief Matches if the given method declaration is virtual.
///
/// Given
/// \code
///   class A {
///    public:
///     virtual void x();
///   };
/// \endcode
///   matches A::x
AST_MATCHER(CXXMethodDecl, isVirtual) {
  return Node.isVirtual();
}

/// \brief Matches if the given method declaration is const.
///
/// Given
/// \code
/// struct A {
///   void foo() const;
///   void bar();
/// };
/// \endcode
///
/// methodDecl(isConst()) matches A::foo() but not A::bar()
AST_MATCHER(CXXMethodDecl, isConst) {
  return Node.isConst();
}

/// \brief Matches if the given method declaration overrides another method.
///
/// Given
/// \code
///   class A {
///    public:
///     virtual void x();
///   };
///   class B : public A {
///    public:
///     virtual void x();
///   };
/// \endcode
///   matches B::x
AST_MATCHER(CXXMethodDecl, isOverride) {
  return Node.size_overridden_methods() > 0;
}

/// \brief Matches member expressions that are called with '->' as opposed
/// to '.'.
///
/// Member calls on the implicit this pointer match as called with '->'.
///
/// Given
/// \code
///   class Y {
///     void x() { this->x(); x(); Y y; y.x(); a; this->b; Y::b; }
///     int a;
///     static int b;
///   };
/// \endcode
/// memberExpr(isArrow())
///   matches this->x, x, y.x, a, this->b
AST_MATCHER(MemberExpr, isArrow) {
  return Node.isArrow();
}

/// \brief Matches QualType nodes that are of integer type.
///
/// Given
/// \code
///   void a(int);
///   void b(long);
///   void c(double);
/// \endcode
/// functionDecl(hasAnyParameter(hasType(isInteger())))
/// matches "a(int)", "b(long)", but not "c(double)".
AST_MATCHER(QualType, isInteger) {
    return Node->isIntegerType();
}

/// \brief Matches QualType nodes that are const-qualified, i.e., that
/// include "top-level" const.
///
/// Given
/// \code
///   void a(int);
///   void b(int const);
///   void c(const int);
///   void d(const int*);
///   void e(int const) {};
/// \endcode
/// functionDecl(hasAnyParameter(hasType(isConstQualified())))
///   matches "void b(int const)", "void c(const int)" and
///   "void e(int const) {}". It does not match d as there
///   is no top-level const on the parameter type "const int *".
AST_MATCHER(QualType, isConstQualified) {
  return Node.isConstQualified();
}

/// \brief Matches QualType nodes that have local CV-qualifiers attached to
/// the node, not hidden within a typedef.
///
/// Given
/// \code
///   typedef const int const_int;
///   const_int i;
///   int *const j;
///   int *volatile k;
///   int m;
/// \endcode
/// \c varDecl(hasType(hasLocalQualifiers())) matches only \c j and \c k.
/// \c i is const-qualified but the qualifier is not local.
AST_MATCHER(QualType, hasLocalQualifiers) {
  return Node.hasLocalQualifiers();
}

/// \brief Matches a member expression where the member is matched by a
/// given matcher.
///
/// Given
/// \code
///   struct { int first, second; } first, second;
///   int i(second.first);
///   int j(first.second);
/// \endcode
/// memberExpr(member(hasName("first")))
///   matches second.first
///   but not first.second (because the member name there is "second").
AST_MATCHER_P(MemberExpr, member,
              internal::Matcher<ValueDecl>, InnerMatcher) {
  return InnerMatcher.matches(*Node.getMemberDecl(), Finder, Builder);
}

/// \brief Matches a member expression where the object expression is
/// matched by a given matcher.
///
/// Given
/// \code
///   struct X { int m; };
///   void f(X x) { x.m; m; }
/// \endcode
/// memberExpr(hasObjectExpression(hasType(recordDecl(hasName("X")))))))
///   matches "x.m" and "m"
/// with hasObjectExpression(...)
///   matching "x" and the implicit object expression of "m" which has type X*.
AST_MATCHER_P(MemberExpr, hasObjectExpression,
              internal::Matcher<Expr>, InnerMatcher) {
  return InnerMatcher.matches(*Node.getBase(), Finder, Builder);
}

/// \brief Matches any using shadow declaration.
///
/// Given
/// \code
///   namespace X { void b(); }
///   using X::b;
/// \endcode
/// usingDecl(hasAnyUsingShadowDecl(hasName("b"))))
///   matches \code using X::b \endcode
AST_MATCHER_P(UsingDecl, hasAnyUsingShadowDecl,
              internal::Matcher<UsingShadowDecl>, InnerMatcher) {
  return matchesFirstInPointerRange(InnerMatcher, Node.shadow_begin(),
                                    Node.shadow_end(), Finder, Builder);
}

/// \brief Matches a using shadow declaration where the target declaration is
/// matched by the given matcher.
///
/// Given
/// \code
///   namespace X { int a; void b(); }
///   using X::a;
///   using X::b;
/// \endcode
/// usingDecl(hasAnyUsingShadowDecl(hasTargetDecl(functionDecl())))
///   matches \code using X::b \endcode
///   but not \code using X::a \endcode
AST_MATCHER_P(UsingShadowDecl, hasTargetDecl,
              internal::Matcher<NamedDecl>, InnerMatcher) {
  return InnerMatcher.matches(*Node.getTargetDecl(), Finder, Builder);
}

/// \brief Matches template instantiations of function, class, or static
/// member variable template instantiations.
///
/// Given
/// \code
///   template <typename T> class X {}; class A {}; X<A> x;
/// \endcode
/// or
/// \code
///   template <typename T> class X {}; class A {}; template class X<A>;
/// \endcode
/// recordDecl(hasName("::X"), isTemplateInstantiation())
///   matches the template instantiation of X<A>.
///
/// But given
/// \code
///   template <typename T>  class X {}; class A {};
///   template <> class X<A> {}; X<A> x;
/// \endcode
/// recordDecl(hasName("::X"), isTemplateInstantiation())
///   does not match, as X<A> is an explicit template specialization.
///
/// Usable as: Matcher<FunctionDecl>, Matcher<VarDecl>, Matcher<CXXRecordDecl>
AST_POLYMORPHIC_MATCHER(
    isTemplateInstantiation,
    AST_POLYMORPHIC_SUPPORTED_TYPES_3(FunctionDecl, VarDecl, CXXRecordDecl)) {
  return (Node.getTemplateSpecializationKind() == TSK_ImplicitInstantiation ||
          Node.getTemplateSpecializationKind() ==
          TSK_ExplicitInstantiationDefinition);
}

/// \brief Matches explicit template specializations of function, class, or
/// static member variable template instantiations.
///
/// Given
/// \code
///   template<typename T> void A(T t) { }
///   template<> void A(int N) { }
/// \endcode
/// functionDecl(isExplicitTemplateSpecialization())
///   matches the specialization A<int>().
///
/// Usable as: Matcher<FunctionDecl>, Matcher<VarDecl>, Matcher<CXXRecordDecl>
AST_POLYMORPHIC_MATCHER(
    isExplicitTemplateSpecialization,
    AST_POLYMORPHIC_SUPPORTED_TYPES_3(FunctionDecl, VarDecl, CXXRecordDecl)) {
  return (Node.getTemplateSpecializationKind() == TSK_ExplicitSpecialization);
}

/// \brief Matches \c TypeLocs for which the given inner
/// QualType-matcher matches.
inline internal::BindableMatcher<TypeLoc> loc(
    const internal::Matcher<QualType> &InnerMatcher) {
  return internal::BindableMatcher<TypeLoc>(
      new internal::TypeLocTypeMatcher(InnerMatcher));
}

/// \brief Matches builtin Types.
///
/// Given
/// \code
///   struct A {};
///   A a;
///   int b;
///   float c;
///   bool d;
/// \endcode
/// builtinType()
///   matches "int b", "float c" and "bool d"
AST_TYPE_MATCHER(BuiltinType, builtinType);

/// \brief Matches all kinds of arrays.
///
/// Given
/// \code
///   int a[] = { 2, 3 };
///   int b[4];
///   void f() { int c[a[0]]; }
/// \endcode
/// arrayType()
///   matches "int a[]", "int b[4]" and "int c[a[0]]";
AST_TYPE_MATCHER(ArrayType, arrayType);

/// \brief Matches C99 complex types.
///
/// Given
/// \code
///   _Complex float f;
/// \endcode
/// complexType()
///   matches "_Complex float f"
AST_TYPE_MATCHER(ComplexType, complexType);

/// \brief Matches arrays and C99 complex types that have a specific element
/// type.
///
/// Given
/// \code
///   struct A {};
///   A a[7];
///   int b[7];
/// \endcode
/// arrayType(hasElementType(builtinType()))
///   matches "int b[7]"
///
/// Usable as: Matcher<ArrayType>, Matcher<ComplexType>
AST_TYPELOC_TRAVERSE_MATCHER(
    hasElementType, getElement,
    AST_POLYMORPHIC_SUPPORTED_TYPES_2(ArrayType, ComplexType));

/// \brief Matches C arrays with a specified constant size.
///
/// Given
/// \code
///   void() {
///     int a[2];
///     int b[] = { 2, 3 };
///     int c[b[0]];
///   }
/// \endcode
/// constantArrayType()
///   matches "int a[2]"
AST_TYPE_MATCHER(ConstantArrayType, constantArrayType);

/// \brief Matches \c ConstantArrayType nodes that have the specified size.
///
/// Given
/// \code
///   int a[42];
///   int b[2 * 21];
///   int c[41], d[43];
/// \endcode
/// constantArrayType(hasSize(42))
///   matches "int a[42]" and "int b[2 * 21]"
AST_MATCHER_P(ConstantArrayType, hasSize, unsigned, N) {
  return Node.getSize() == N;
}

/// \brief Matches C++ arrays whose size is a value-dependent expression.
///
/// Given
/// \code
///   template<typename T, int Size>
///   class array {
///     T data[Size];
///   };
/// \endcode
/// dependentSizedArrayType
///   matches "T data[Size]"
AST_TYPE_MATCHER(DependentSizedArrayType, dependentSizedArrayType);

/// \brief Matches C arrays with unspecified size.
///
/// Given
/// \code
///   int a[] = { 2, 3 };
///   int b[42];
///   void f(int c[]) { int d[a[0]]; };
/// \endcode
/// incompleteArrayType()
///   matches "int a[]" and "int c[]"
AST_TYPE_MATCHER(IncompleteArrayType, incompleteArrayType);

/// \brief Matches C arrays with a specified size that is not an
/// integer-constant-expression.
///
/// Given
/// \code
///   void f() {
///     int a[] = { 2, 3 }
///     int b[42];
///     int c[a[0]];
/// \endcode
/// variableArrayType()
///   matches "int c[a[0]]"
AST_TYPE_MATCHER(VariableArrayType, variableArrayType);

/// \brief Matches \c VariableArrayType nodes that have a specific size
/// expression.
///
/// Given
/// \code
///   void f(int b) {
///     int a[b];
///   }
/// \endcode
/// variableArrayType(hasSizeExpr(ignoringImpCasts(declRefExpr(to(
///   varDecl(hasName("b")))))))
///   matches "int a[b]"
AST_MATCHER_P(VariableArrayType, hasSizeExpr,
              internal::Matcher<Expr>, InnerMatcher) {
  return InnerMatcher.matches(*Node.getSizeExpr(), Finder, Builder);
}

/// \brief Matches atomic types.
///
/// Given
/// \code
///   _Atomic(int) i;
/// \endcode
/// atomicType()
///   matches "_Atomic(int) i"
AST_TYPE_MATCHER(AtomicType, atomicType);

/// \brief Matches atomic types with a specific value type.
///
/// Given
/// \code
///   _Atomic(int) i;
///   _Atomic(float) f;
/// \endcode
/// atomicType(hasValueType(isInteger()))
///  matches "_Atomic(int) i"
///
/// Usable as: Matcher<AtomicType>
AST_TYPELOC_TRAVERSE_MATCHER(hasValueType, getValue,
                             AST_POLYMORPHIC_SUPPORTED_TYPES_1(AtomicType));

/// \brief Matches types nodes representing C++11 auto types.
///
/// Given:
/// \code
///   auto n = 4;
///   int v[] = { 2, 3 }
///   for (auto i : v) { }
/// \endcode
/// autoType()
///   matches "auto n" and "auto i"
AST_TYPE_MATCHER(AutoType, autoType);

/// \brief Matches \c AutoType nodes where the deduced type is a specific type.
///
/// Note: There is no \c TypeLoc for the deduced type and thus no
/// \c getDeducedLoc() matcher.
///
/// Given
/// \code
///   auto a = 1;
///   auto b = 2.0;
/// \endcode
/// autoType(hasDeducedType(isInteger()))
///   matches "auto a"
///
/// Usable as: Matcher<AutoType>
AST_TYPE_TRAVERSE_MATCHER(hasDeducedType, getDeducedType,
                          AST_POLYMORPHIC_SUPPORTED_TYPES_1(AutoType));

/// \brief Matches \c FunctionType nodes.
///
/// Given
/// \code
///   int (*f)(int);
///   void g();
/// \endcode
/// functionType()
///   matches "int (*f)(int)" and the type of "g".
AST_TYPE_MATCHER(FunctionType, functionType);

/// \brief Matches \c ParenType nodes.
///
/// Given
/// \code
///   int (*ptr_to_array)[4];
///   int *array_of_ptrs[4];
/// \endcode
///
/// \c varDecl(hasType(pointsTo(parenType()))) matches \c ptr_to_array but not
/// \c array_of_ptrs.
AST_TYPE_MATCHER(ParenType, parenType);

/// \brief Matches \c ParenType nodes where the inner type is a specific type.
///
/// Given
/// \code
///   int (*ptr_to_array)[4];
///   int (*ptr_to_func)(int);
/// \endcode
///
/// \c varDecl(hasType(pointsTo(parenType(innerType(functionType()))))) matches
/// \c ptr_to_func but not \c ptr_to_array.
///
/// Usable as: Matcher<ParenType>
AST_TYPE_TRAVERSE_MATCHER(innerType, getInnerType,
                          AST_POLYMORPHIC_SUPPORTED_TYPES_1(ParenType));

/// \brief Matches block pointer types, i.e. types syntactically represented as
/// "void (^)(int)".
///
/// The \c pointee is always required to be a \c FunctionType.
AST_TYPE_MATCHER(BlockPointerType, blockPointerType);

/// \brief Matches member pointer types.
/// Given
/// \code
///   struct A { int i; }
///   A::* ptr = A::i;
/// \endcode
/// memberPointerType()
///   matches "A::* ptr"
AST_TYPE_MATCHER(MemberPointerType, memberPointerType);

/// \brief Matches pointer types.
///
/// Given
/// \code
///   int *a;
///   int &b = *a;
///   int c = 5;
/// \endcode
/// pointerType()
///   matches "int *a"
AST_TYPE_MATCHER(PointerType, pointerType);

/// \brief Matches both lvalue and rvalue reference types.
///
/// Given
/// \code
///   int *a;
///   int &b = *a;
///   int &&c = 1;
///   auto &d = b;
///   auto &&e = c;
///   auto &&f = 2;
///   int g = 5;
/// \endcode
///
/// \c referenceType() matches the types of \c b, \c c, \c d, \c e, and \c f.
AST_TYPE_MATCHER(ReferenceType, referenceType);

/// \brief Matches lvalue reference types.
///
/// Given:
/// \code
///   int *a;
///   int &b = *a;
///   int &&c = 1;
///   auto &d = b;
///   auto &&e = c;
///   auto &&f = 2;
///   int g = 5;
/// \endcode
///
/// \c lValueReferenceType() matches the types of \c b, \c d, and \c e. \c e is
/// matched since the type is deduced as int& by reference collapsing rules.
AST_TYPE_MATCHER(LValueReferenceType, lValueReferenceType);

/// \brief Matches rvalue reference types.
///
/// Given:
/// \code
///   int *a;
///   int &b = *a;
///   int &&c = 1;
///   auto &d = b;
///   auto &&e = c;
///   auto &&f = 2;
///   int g = 5;
/// \endcode
///
/// \c rValueReferenceType() matches the types of \c c and \c f. \c e is not
/// matched as it is deduced to int& by reference collapsing rules.
AST_TYPE_MATCHER(RValueReferenceType, rValueReferenceType);

/// \brief Narrows PointerType (and similar) matchers to those where the
/// \c pointee matches a given matcher.
///
/// Given
/// \code
///   int *a;
///   int const *b;
///   float const *f;
/// \endcode
/// pointerType(pointee(isConstQualified(), isInteger()))
///   matches "int const *b"
///
/// Usable as: Matcher<BlockPointerType>, Matcher<MemberPointerType>,
///   Matcher<PointerType>, Matcher<ReferenceType>
AST_TYPELOC_TRAVERSE_MATCHER(
    pointee, getPointee,
    AST_POLYMORPHIC_SUPPORTED_TYPES_4(BlockPointerType, MemberPointerType,
                                      PointerType, ReferenceType));

/// \brief Matches typedef types.
///
/// Given
/// \code
///   typedef int X;
/// \endcode
/// typedefType()
///   matches "typedef int X"
AST_TYPE_MATCHER(TypedefType, typedefType);

/// \brief Matches template specialization types.
///
/// Given
/// \code
///   template <typename T>
///   class C { };
///
///   template class C<int>;  // A
///   C<char> var;            // B
/// \code
///
/// \c templateSpecializationType() matches the type of the explicit
/// instantiation in \c A and the type of the variable declaration in \c B.
AST_TYPE_MATCHER(TemplateSpecializationType, templateSpecializationType);

/// \brief Matches types nodes representing unary type transformations.
///
/// Given:
/// \code
///   typedef __underlying_type(T) type;
/// \endcode
/// unaryTransformType()
///   matches "__underlying_type(T)"
AST_TYPE_MATCHER(UnaryTransformType, unaryTransformType);

/// \brief Matches record types (e.g. structs, classes).
///
/// Given
/// \code
///   class C {};
///   struct S {};
///
///   C c;
///   S s;
/// \code
///
/// \c recordType() matches the type of the variable declarations of both \c c
/// and \c s.
AST_TYPE_MATCHER(RecordType, recordType);

/// \brief Matches types specified with an elaborated type keyword or with a
/// qualified name.
///
/// Given
/// \code
///   namespace N {
///     namespace M {
///       class D {};
///     }
///   }
///   class C {};
///
///   class C c;
///   N::M::D d;
/// \code
///
/// \c elaboratedType() matches the type of the variable declarations of both
/// \c c and \c d.
AST_TYPE_MATCHER(ElaboratedType, elaboratedType);

/// \brief Matches ElaboratedTypes whose qualifier, a NestedNameSpecifier,
/// matches \c InnerMatcher if the qualifier exists.
///
/// Given
/// \code
///   namespace N {
///     namespace M {
///       class D {};
///     }
///   }
///   N::M::D d;
/// \code
///
/// \c elaboratedType(hasQualifier(hasPrefix(specifiesNamespace(hasName("N"))))
/// matches the type of the variable declaration of \c d.
AST_MATCHER_P(ElaboratedType, hasQualifier,
              internal::Matcher<NestedNameSpecifier>, InnerMatcher) {
  if (const NestedNameSpecifier *Qualifier = Node.getQualifier())
    return InnerMatcher.matches(*Qualifier, Finder, Builder);

  return false;
}

/// \brief Matches ElaboratedTypes whose named type matches \c InnerMatcher.
///
/// Given
/// \code
///   namespace N {
///     namespace M {
///       class D {};
///     }
///   }
///   N::M::D d;
/// \code
///
/// \c elaboratedType(namesType(recordType(
/// hasDeclaration(namedDecl(hasName("D")))))) matches the type of the variable
/// declaration of \c d.
AST_MATCHER_P(ElaboratedType, namesType, internal::Matcher<QualType>,
              InnerMatcher) {
  return InnerMatcher.matches(Node.getNamedType(), Finder, Builder);
}

/// \brief Matches declarations whose declaration context, interpreted as a
/// Decl, matches \c InnerMatcher.
///
/// Given
/// \code
///   namespace N {
///     namespace M {
///       class D {};
///     }
///   }
/// \code
///
/// \c recordDecl(hasDeclContext(namedDecl(hasName("M")))) matches the
/// declaration of \c class \c D.
AST_MATCHER_P(Decl, hasDeclContext, internal::Matcher<Decl>, InnerMatcher) {
  return InnerMatcher.matches(*Decl::castFromDeclContext(Node.getDeclContext()),
                              Finder, Builder);
}

/// \brief Matches nested name specifiers.
///
/// Given
/// \code
///   namespace ns {
///     struct A { static void f(); };
///     void A::f() {}
///     void g() { A::f(); }
///   }
///   ns::A a;
/// \endcode
/// nestedNameSpecifier()
///   matches "ns::" and both "A::"
const internal::VariadicAllOfMatcher<NestedNameSpecifier> nestedNameSpecifier;

/// \brief Same as \c nestedNameSpecifier but matches \c NestedNameSpecifierLoc.
const internal::VariadicAllOfMatcher<
  NestedNameSpecifierLoc> nestedNameSpecifierLoc;

/// \brief Matches \c NestedNameSpecifierLocs for which the given inner
/// NestedNameSpecifier-matcher matches.
inline internal::BindableMatcher<NestedNameSpecifierLoc> loc(
    const internal::Matcher<NestedNameSpecifier> &InnerMatcher) {
  return internal::BindableMatcher<NestedNameSpecifierLoc>(
      new internal::LocMatcher<NestedNameSpecifierLoc, NestedNameSpecifier>(
          InnerMatcher));
}

/// \brief Matches nested name specifiers that specify a type matching the
/// given \c QualType matcher without qualifiers.
///
/// Given
/// \code
///   struct A { struct B { struct C {}; }; };
///   A::B::C c;
/// \endcode
/// nestedNameSpecifier(specifiesType(hasDeclaration(recordDecl(hasName("A")))))
///   matches "A::"
AST_MATCHER_P(NestedNameSpecifier, specifiesType,
              internal::Matcher<QualType>, InnerMatcher) {
  if (Node.getAsType() == NULL)
    return false;
  return InnerMatcher.matches(QualType(Node.getAsType(), 0), Finder, Builder);
}

/// \brief Matches nested name specifier locs that specify a type matching the
/// given \c TypeLoc.
///
/// Given
/// \code
///   struct A { struct B { struct C {}; }; };
///   A::B::C c;
/// \endcode
/// nestedNameSpecifierLoc(specifiesTypeLoc(loc(type(
///   hasDeclaration(recordDecl(hasName("A")))))))
///   matches "A::"
AST_MATCHER_P(NestedNameSpecifierLoc, specifiesTypeLoc,
              internal::Matcher<TypeLoc>, InnerMatcher) {
  return InnerMatcher.matches(Node.getTypeLoc(), Finder, Builder);
}

/// \brief Matches on the prefix of a \c NestedNameSpecifier.
///
/// Given
/// \code
///   struct A { struct B { struct C {}; }; };
///   A::B::C c;
/// \endcode
/// nestedNameSpecifier(hasPrefix(specifiesType(asString("struct A")))) and
///   matches "A::"
AST_MATCHER_P_OVERLOAD(NestedNameSpecifier, hasPrefix,
                       internal::Matcher<NestedNameSpecifier>, InnerMatcher,
                       0) {
  NestedNameSpecifier *NextNode = Node.getPrefix();
  if (NextNode == NULL)
    return false;
  return InnerMatcher.matches(*NextNode, Finder, Builder);
}

/// \brief Matches on the prefix of a \c NestedNameSpecifierLoc.
///
/// Given
/// \code
///   struct A { struct B { struct C {}; }; };
///   A::B::C c;
/// \endcode
/// nestedNameSpecifierLoc(hasPrefix(loc(specifiesType(asString("struct A")))))
///   matches "A::"
AST_MATCHER_P_OVERLOAD(NestedNameSpecifierLoc, hasPrefix,
                       internal::Matcher<NestedNameSpecifierLoc>, InnerMatcher,
                       1) {
  NestedNameSpecifierLoc NextNode = Node.getPrefix();
  if (!NextNode)
    return false;
  return InnerMatcher.matches(NextNode, Finder, Builder);
}

/// \brief Matches nested name specifiers that specify a namespace matching the
/// given namespace matcher.
///
/// Given
/// \code
///   namespace ns { struct A {}; }
///   ns::A a;
/// \endcode
/// nestedNameSpecifier(specifiesNamespace(hasName("ns")))
///   matches "ns::"
AST_MATCHER_P(NestedNameSpecifier, specifiesNamespace,
              internal::Matcher<NamespaceDecl>, InnerMatcher) {
  if (Node.getAsNamespace() == NULL)
    return false;
  return InnerMatcher.matches(*Node.getAsNamespace(), Finder, Builder);
}

/// \brief Overloads for the \c equalsNode matcher.
/// FIXME: Implement for other node types.
/// @{

/// \brief Matches if a node equals another node.
///
/// \c Decl has pointer identity in the AST.
AST_MATCHER_P_OVERLOAD(Decl, equalsNode, Decl*, Other, 0) {
  return &Node == Other;
}
/// \brief Matches if a node equals another node.
///
/// \c Stmt has pointer identity in the AST.
///
AST_MATCHER_P_OVERLOAD(Stmt, equalsNode, Stmt*, Other, 1) {
  return &Node == Other;
}

/// @}

/// \brief Matches each case or default statement belonging to the given switch
/// statement. This matcher may produce multiple matches.
///
/// Given
/// \code
///   switch (1) { case 1: case 2: default: switch (2) { case 3: case 4: ; } }
/// \endcode
/// switchStmt(forEachSwitchCase(caseStmt().bind("c"))).bind("s")
///   matches four times, with "c" binding each of "case 1:", "case 2:",
/// "case 3:" and "case 4:", and "s" respectively binding "switch (1)",
/// "switch (1)", "switch (2)" and "switch (2)".
AST_MATCHER_P(SwitchStmt, forEachSwitchCase, internal::Matcher<SwitchCase>,
              InnerMatcher) {
  BoundNodesTreeBuilder Result;
  // FIXME: getSwitchCaseList() does not necessarily guarantee a stable
  // iteration order. We should use the more general iterating matchers once
  // they are capable of expressing this matcher (for example, it should ignore
  // case statements belonging to nested switch statements).
  bool Matched = false;
  for (const SwitchCase *SC = Node.getSwitchCaseList(); SC;
       SC = SC->getNextSwitchCase()) {
    BoundNodesTreeBuilder CaseBuilder(*Builder);
    bool CaseMatched = InnerMatcher.matches(*SC, Finder, &CaseBuilder);
    if (CaseMatched) {
      Matched = true;
      Result.addMatch(CaseBuilder);
    }
  }
  *Builder = Result;
  return Matched;
}

/// \brief Matches each constructor initializer in a constructor definition.
///
/// Given
/// \code
///   class A { A() : i(42), j(42) {} int i; int j; };
/// \endcode
/// constructorDecl(forEachConstructorInitializer(forField(decl().bind("x"))))
///   will trigger two matches, binding for 'i' and 'j' respectively.
AST_MATCHER_P(CXXConstructorDecl, forEachConstructorInitializer,
              internal::Matcher<CXXCtorInitializer>, InnerMatcher) {
  BoundNodesTreeBuilder Result;
  bool Matched = false;
  for (CXXConstructorDecl::init_const_iterator I = Node.init_begin(),
                                               E = Node.init_end();
       I != E; ++I) {
    BoundNodesTreeBuilder InitBuilder(*Builder);
    if (InnerMatcher.matches(**I, Finder, &InitBuilder)) {
      Matched = true;
      Result.addMatch(InitBuilder);
    }
  }
  *Builder = Result;
  return Matched;
}

/// \brief If the given case statement does not use the GNU case range
/// extension, matches the constant given in the statement.
///
/// Given
/// \code
///   switch (1) { case 1: case 1+1: case 3 ... 4: ; }
/// \endcode
/// caseStmt(hasCaseConstant(integerLiteral()))
///   matches "case 1:"
AST_MATCHER_P(CaseStmt, hasCaseConstant, internal::Matcher<Expr>,
              InnerMatcher) {
  if (Node.getRHS())
    return false;

  return InnerMatcher.matches(*Node.getLHS(), Finder, Builder);
}

} // end namespace ast_matchers
} // end namespace clang

#endif // LLVM_CLANG_AST_MATCHERS_AST_MATCHERS_H
