From 64cbdf370984783911bb6d3bc25ec35a8b59e998 Mon Sep 17 00:00:00 2001 From: Manuel Klimek Date: Tue, 31 May 2011 23:49:32 +0000 Subject: [PATCH] This patch implements an AST matching framework that allows to write tools that match on the C++ ASTs. The main interface is in ASTMatchers.h, an example implementation of a tool that removes redundant .c_str() calls is in the example RemoveCStrCalls.cpp. Various contributions: Zhanyong Wan, Chandler Carruth, Marcin Kowalczyk, Wei Xu, James Dennett. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@132374 91177308-0d34-0410-b5e6-96231b3b80d8 --- examples/Tooling/CMakeLists.txt | 1 + .../Tooling/RemoveCStrCalls/CMakeLists.txt | 5 + .../RemoveCStrCalls/RemoveCStrCalls.cpp | 229 +++ examples/Tooling/replace.py | 50 + include/clang/Tooling/ASTMatchers.h | 1736 +++++++++++++++++ include/clang/Tooling/Tooling.h | 4 +- include/clang/Tooling/VariadicFunction.h | 1398 +++++++++++++ lib/Tooling/ASTMatchers.cpp | 564 ++++++ lib/Tooling/CMakeLists.txt | 1 + lib/Tooling/Tooling.cpp | 60 +- test/Tooling/remove-cstr-calls.cpp | 20 + unittests/CMakeLists.txt | 5 + unittests/Tooling/ASTMatchersTest.cpp | 1602 +++++++++++++++ 13 files changed, 5643 insertions(+), 32 deletions(-) create mode 100644 examples/Tooling/RemoveCStrCalls/CMakeLists.txt create mode 100644 examples/Tooling/RemoveCStrCalls/RemoveCStrCalls.cpp create mode 100755 examples/Tooling/replace.py create mode 100644 include/clang/Tooling/ASTMatchers.h create mode 100644 include/clang/Tooling/VariadicFunction.h create mode 100644 lib/Tooling/ASTMatchers.cpp create mode 100644 test/Tooling/remove-cstr-calls.cpp create mode 100644 unittests/Tooling/ASTMatchersTest.cpp diff --git a/examples/Tooling/CMakeLists.txt b/examples/Tooling/CMakeLists.txt index 257d3ea8ea..01132b858a 100644 --- a/examples/Tooling/CMakeLists.txt +++ b/examples/Tooling/CMakeLists.txt @@ -4,3 +4,4 @@ add_clang_executable(clang-check ClangCheck.cpp ) +add_subdirectory(RemoveCStrCalls) diff --git a/examples/Tooling/RemoveCStrCalls/CMakeLists.txt b/examples/Tooling/RemoveCStrCalls/CMakeLists.txt new file mode 100644 index 0000000000..66debc9288 --- /dev/null +++ b/examples/Tooling/RemoveCStrCalls/CMakeLists.txt @@ -0,0 +1,5 @@ +set(LLVM_USED_LIBS clangTooling clangBasic clangAST) + +add_clang_executable(remove-cstr-calls + RemoveCStrCalls.cpp + ) diff --git a/examples/Tooling/RemoveCStrCalls/RemoveCStrCalls.cpp b/examples/Tooling/RemoveCStrCalls/RemoveCStrCalls.cpp new file mode 100644 index 0000000000..6de9dd986a --- /dev/null +++ b/examples/Tooling/RemoveCStrCalls/RemoveCStrCalls.cpp @@ -0,0 +1,229 @@ +//===- examples/Tooling/RemoveCStrCalls.cpp - Redundant c_str call removal ===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a tool that prints replacements that remove redundant +// calls of c_str() on strings. +// +// Usage: +// remove-cstr-calls ... +// +// Where is a CMake build directory in which a file named +// compile_commands.json exists (enable -DCMAKE_EXPORT_COMPILE_COMMANDS in +// CMake to get this output). +// +// ... specify the paths of files in the CMake source tree. This path +// is looked up in the compile command database. If the path of a file is +// absolute, it needs to point into CMake's source tree. If the path is +// relative, the current working directory needs to be in the CMake source +// tree and the file must be in a subdirectory of the current working +// directory. "./" prefixes in the relative files will be automatically +// removed, but the rest of a relative path must be a suffix of a path in +// the compile command line database. +// +// For example, to use remove-cstr-calls on all files in a subtree of the +// source tree, use: +// +// /path/in/subtree $ find . -name '*.cpp'| +// xargs remove-cstr-calls /path/to/source +// +//===----------------------------------------------------------------------===// + +#include "clang/Basic/SourceManager.h" +#include "clang/Frontend/FrontendActions.h" +#include "clang/Lex/Lexer.h" +#include "clang/Tooling/ASTMatchers.h" +#include "clang/Tooling/Tooling.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/ADT/Twine.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/Path.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/system_error.h" + +using namespace clang::tooling::match; + +// FIXME: Pull out helper methods in here into more fitting places. + +// Returns the text that makes up 'node' in the source. +// Returns an empty string if the text cannot be found. +template +std::string GetText(const clang::SourceManager &SourceManager, const T &Node) { + clang::SourceLocation StartSpellingLocatino = + SourceManager.getSpellingLoc(Node.getLocStart()); + clang::SourceLocation EndSpellingLocation = + SourceManager.getSpellingLoc(Node.getLocEnd()); + if (!StartSpellingLocatino.isValid() || !EndSpellingLocation.isValid()) { + return std::string(); + } + bool Invalid = true; + const char *Text = + SourceManager.getCharacterData(StartSpellingLocatino, &Invalid); + if (Invalid) { + return std::string(); + } + std::pair Start = + SourceManager.getDecomposedLoc(StartSpellingLocatino); + std::pair End = + SourceManager.getDecomposedLoc(clang::Lexer::getLocForEndOfToken( + EndSpellingLocation, 0, SourceManager, clang::LangOptions())); + if (Start.first != End.first) { + // Start and end are in different files. + return std::string(); + } + if (End.second < Start.second) { + // Shuffling text with macros may cause this. + return std::string(); + } + return std::string(Text, End.second - Start.second); +} + +// Returns the position of the spelling location of a node inside a file. +// The format is: +// ":::" +template +void PrintPosition( + llvm::raw_ostream &OS, + const clang::SourceManager &SourceManager, const T1 &Node) { + clang::SourceLocation StartSpellingLocation = + SourceManager.getSpellingLoc(Node.getLocStart()); + clang::SourceLocation EndSpellingLocation = + SourceManager.getSpellingLoc(Node.getLocEnd()); + clang::PresumedLoc Start = + SourceManager.getPresumedLoc(StartSpellingLocation); + clang::SourceLocation EndToken = clang::Lexer::getLocForEndOfToken( + EndSpellingLocation, 1, SourceManager, clang::LangOptions()); + clang::PresumedLoc End = SourceManager.getPresumedLoc(EndToken); + OS << Start.getLine() << ":" << Start.getColumn() << ":" + << End.getLine() << ":" << End.getColumn(); +} + +class ReportPosition : public clang::tooling::MatchFinder::MatchCallback { + public: + virtual void Run(const clang::tooling::MatchFinder::MatchResult &Result) { + llvm::outs() << "Found!\n"; + } +}; + +// Return true if expr needs to be put in parens when it is an +// argument of a prefix unary operator, e.g. when it is a binary or +// ternary operator syntactically. +bool NeedParensAfterUnaryOperator(const clang::Expr &ExprNode) { + if (llvm::dyn_cast(&ExprNode) || + llvm::dyn_cast(&ExprNode)) { + return true; + } + if (const clang::CXXOperatorCallExpr *op = + llvm::dyn_cast(&ExprNode)) { + return op->getNumArgs() == 2 && + op->getOperator() != clang::OO_PlusPlus && + op->getOperator() != clang::OO_MinusMinus && + op->getOperator() != clang::OO_Call && + op->getOperator() != clang::OO_Subscript; + } + return false; +} + +// Format a pointer to an expression: prefix with '*' but simplify +// when it already begins with '&'. Return empty string on failure. +std::string FormatDereference(const clang::SourceManager &SourceManager, + const clang::Expr &ExprNode) { + if (const clang::UnaryOperator *Op = + llvm::dyn_cast(&ExprNode)) { + if (Op->getOpcode() == clang::UO_AddrOf) { + // Strip leading '&'. + return GetText(SourceManager, *Op->getSubExpr()->IgnoreParens()); + } + } + const std::string Text = GetText(SourceManager, ExprNode); + if (Text.empty()) return std::string(); + // Add leading '*'. + if (NeedParensAfterUnaryOperator(ExprNode)) { + return std::string("*(") + Text + ")"; + } + return std::string("*") + Text; +} + +class FixCStrCall : public clang::tooling::MatchFinder::MatchCallback { + public: + virtual void Run(const clang::tooling::MatchFinder::MatchResult &Result) { + const clang::CallExpr *Call = + Result.Nodes.GetStmtAs("call"); + const clang::Expr *Arg = + Result.Nodes.GetStmtAs("arg"); + const bool Arrow = + Result.Nodes.GetStmtAs("member")->isArrow(); + // Replace the "call" node with the "arg" node, prefixed with '*' + // if the call was using '->' rather than '.'. + const std::string ArgText = Arrow ? + FormatDereference(*Result.SourceManager, *Arg) : + GetText(*Result.SourceManager, *Arg); + if (ArgText.empty()) return; + + llvm::outs() << + Result.SourceManager->getBufferName(Call->getLocStart(), NULL) << ":"; + PrintPosition(llvm::outs(), *Result.SourceManager, *Call); + llvm::outs() << ":" << ArgText << "\n"; + } +}; + +const char *StringConstructor = + "::std::basic_string, std::allocator >" + "::basic_string"; + +const char *StringCStrMethod = + "::std::basic_string, std::allocator >" + "::c_str"; + +int main(int argc, char **argv) { + clang::tooling::ClangTool Tool(argc, argv); + clang::tooling::MatchFinder finder; + finder.AddMatcher( + ConstructorCall( + HasDeclaration(Method(HasName(StringConstructor))), + ArgumentCountIs(2), + // The first argument must have the form x.c_str() or p->c_str() + // where the method is string::c_str(). We can use the copy + // constructor of string instead (or the compiler might share + // the string object). + HasArgument( + 0, + Id("call", Call( + Callee(Id("member", MemberExpression())), + Callee(Method(HasName(StringCStrMethod))), + On(Id("arg", Expression()))))), + // The second argument is the alloc object which must not be + // present explicitly. + HasArgument( + 1, + DefaultArgument())), new FixCStrCall); + finder.AddMatcher( + ConstructorCall( + // Implicit constructors of these classes are overloaded + // wrt. string types and they internally make a StringRef + // referring to the argument. Passing a string directly to + // them is preferred to passing a char pointer. + HasDeclaration(Method(AnyOf( + HasName("::llvm::StringRef::StringRef"), + HasName("::llvm::Twine::Twine")))), + ArgumentCountIs(1), + // The only argument must have the form x.c_str() or p->c_str() + // where the method is string::c_str(). StringRef also has + // a constructor from string which is more efficient (avoids + // strlen), so we can construct StringRef from the string + // directly. + HasArgument( + 0, + Id("call", Call( + Callee(Id("member", MemberExpression())), + Callee(Method(HasName(StringCStrMethod))), + On(Id("arg", Expression())))))), + new FixCStrCall); + return Tool.Run(finder.NewFrontendActionFactory()); +} + diff --git a/examples/Tooling/replace.py b/examples/Tooling/replace.py new file mode 100755 index 0000000000..a738dea70c --- /dev/null +++ b/examples/Tooling/replace.py @@ -0,0 +1,50 @@ +#!/usr/bin/env python + +#===- replace.py - Applying code rewrites --------------------*- python -*--===# +# +# The LLVM Compiler Infrastructure +# +# This file is distributed under the University of Illinois Open Source +# License. See LICENSE.TXT for details. +# +#===------------------------------------------------------------------------===# +# +# This script applies the rewrites generated by replace-cstr-calls on a source +# tree. +# +# Usage: +# ./replace.py < /path/to/replace-cstr-calls-output +# +#===------------------------------------------------------------------------===# + +import fileinput +import re +import sys + +for line in sys.stdin.readlines(): + # The format is: + # ::::: + # FIXME: This currently does not support files with colons, we'll need to + # figure out a format when we implement more refactoring support. + match = re.match(r'(.*):(\d+):(\d+):(\d+):(\d+):(.*)$', line) + if match is not None: + file_name = match.group(1) + start_line, start_column = int(match.group(2)), int(match.group(3)) + end_line, end_column = int(match.group(4)), int(match.group(5)) + replacement = match.group(6) + if start_line != end_line: + print ('Skipping match "%s": only single line ' + + 'replacements are supported') % line.strip() + continue + try: + replace_file = fileinput.input(file_name, inplace=1) + for replace_line in replace_file: + # FIXME: Looping over the file for each replacement is both inefficient + # and incorrect if replacements add or remove lines. + if replace_file.lineno() == start_line: + sys.stdout.write(replace_line[:start_column-1] + replacement + + replace_line[end_column:]) + else: + sys.stdout.write(replace_line) + except OSError, e: + print 'Cannot open %s for editing' % file_name diff --git a/include/clang/Tooling/ASTMatchers.h b/include/clang/Tooling/ASTMatchers.h new file mode 100644 index 0000000000..08b687dfe9 --- /dev/null +++ b/include/clang/Tooling/ASTMatchers.h @@ -0,0 +1,1736 @@ +//===--- 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 a framework of AST matchers that can be used to express +// structural queries on the AST representing C++ code. +// +// The general idea is to construct a matcher expression that describes a +// subtree match on the AST. Next, a callback that is executed every time the +// expression matches is registered, and the matcher is run over the AST of +// some code. Matched subexpressions can be bound to string IDs and easily +// be accessed from the registered callback. The callback can than use the +// AST nodes that the subexpressions matched on to output information about +// the match or construct changes that can be applied to the code. +// +// Example: +// class HandleMatch : public clang::tooling::MatchFinder::MatchCallback { +// public: +// virtual void Run(const clang::tooling::MatchFinder::MatchResult &Result) { +// const clang::CXXRecordDecl *Class = +// Result.Nodes.GetDeclAs("id"); +// ... +// } +// }; +// +// int main(int argc, char **argv) { +// ClangTool Tool(argc, argv); +// MatchFinder finder; +// finder.AddMatcher(Id("id", Class(HasName("::a_namespace::AClass"))), +// new HandleMatch); +// return Tool.Run(finder.NewFrontendActionFactory()); +// } +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_TOOLING_AST_MATCHERS_H +#define LLVM_CLANG_TOOLING_AST_MATCHERS_H + +#include "clang/AST/Decl.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/ExprCXX.h" +#include "clang/AST/Stmt.h" +#include "clang/Tooling/VariadicFunction.h" +#include "llvm/ADT/Twine.h" +#include "llvm/Support/type_traits.h" +#include +#include +#include +#include +#include +#include + +/// FIXME: Move into the llvm support library. +template struct CompileAssert {}; +#define COMPILE_ASSERT(Expr, Msg) \ + typedef CompileAssert<(bool(Expr))> Msg[bool(Expr) ? 1 : -1] + +namespace clang { + +class FrontendAction; +class SourceManager; + +namespace tooling { + +class FrontendActionFactory; +class BoundNodesBuilder; + +/// Contains a mapping from IDs to nodes bound to those IDs and provides +/// convenient access to those nodes. +class BoundNodes { + public: + BoundNodes() {} + + /// Create BoundNodes from a pre-filled map of bindings. + BoundNodes(const std::map &DeclBindings, + const std::map &StmtBindings) + : DeclBindings(DeclBindings), StmtBindings(StmtBindings) {} + + /// Returns the node bound to the specified id if the id was bound to a node + /// and that node can be converted into the specified type. Returns NULL + /// otherwise. + /// FIXME: We'll need one of those for every base type. + template + const T *GetDeclAs(const std::string &ID) const { + return GetNodeAs(DeclBindings, ID); + } + template + const T *GetStmtAs(const std::string &ID) const { + return GetNodeAs(StmtBindings, ID); + } + + /// Adds all bound nodes to bound_nodes_builder. + void CopyTo(BoundNodesBuilder *CopyToBuilder) const; + + private: + template + const T *GetNodeAs(const MapT &Bindings, const std::string &ID) const { + typename MapT::const_iterator It = Bindings.find(ID); + if (It == Bindings.end()) { + return NULL; + } + return llvm::dyn_cast(It->second); + } + + std::map DeclBindings; + std::map StmtBindings; +}; // class BoundNodes + +/// Creates BoundNodes objects. +class BoundNodesBuilder { + public: + BoundNodesBuilder() {} + + /// Add a binding from 'ID' to 'Node'. + /// FIXME: Add overloads for all AST base types. + void SetBinding(const std::string &ID, const clang::Decl *Node) { + DeclBindings[ID] = Node; + } + void SetBinding(const std::string &ID, const clang::Stmt *Node) { + StmtBindings[ID] = Node; + } + + /// Returns a BoundNodes object containing all current bindings. + BoundNodes Build() const { + return BoundNodes(DeclBindings, StmtBindings); + } + + private: + BoundNodesBuilder(const BoundNodesBuilder&); // DO NOT IMPLEMENT + void operator=(const BoundNodesBuilder&); // DO NOT IMPLEMENT + + std::map DeclBindings; + std::map StmtBindings; +}; + +inline void BoundNodes::CopyTo(BoundNodesBuilder *CopyToBuilder) const { + for (std::map::const_iterator + It = DeclBindings.begin(), End = DeclBindings.end(); + It != End; ++It) { + CopyToBuilder->SetBinding(It->first, It->second); + } + /// FIXME: Pull out method. + for (std::map::const_iterator + It = StmtBindings.begin(), End = StmtBindings.end(); + It != End; ++It) { + CopyToBuilder->SetBinding(It->first, It->second); + } +} + +class ASTMatchFinder; + +/// Generic interface for matchers on an AST node of type T. Implement +/// this if your matcher may need to inspect the children or +/// descendants of the node or bind matched nodes to names. If you are +/// writing a simple matcher that only inspects properties of the +/// current node and doesn't care about its children or descendants, +/// implement SingleNodeMatcherInterface instead. +template +class MatcherInterface : public llvm::RefCountedBaseVPTR { + public: + virtual ~MatcherInterface() {} + + /// Returns true if 'Node' can be matched. + /// May bind 'Node' to an ID via 'Builder', or recurse into + /// the AST via 'Finder'. + virtual bool Matches( + const T &Node, + ASTMatchFinder *Finder, + BoundNodesBuilder *Builder) const = 0; +}; + +/// Interface for matchers that only evaluate properties on a single node. +template +class SingleNodeMatcherInterface : public MatcherInterface { + public: + /// Returns true if the matcher matches the provided node. A subclass + /// must implement this instead of Matches(). + virtual bool MatchesNode(const T &Node) const = 0; + + private: + /// Implements MatcherInterface::Matches. + virtual bool Matches(const T &Node, + ASTMatchFinder * /* Finder */, + BoundNodesBuilder * /* Builder */) const { + return MatchesNode(Node); + } +}; + +/// Wrapper of a MatcherInterface *that allows copying. +/// +/// A Matcher can be used anywhere a Matcher is +/// required. This establishes an is-a relationship which is reverse +/// to the AST hierarchy. In other words, Matcher is contravariant +/// with respect to T. The relationship is built via a type conversion +/// operator rather than a type hierarchy to be able to templatize the +/// type hierarchy instead of spelling it out. +template +class Matcher { + public: + /// Takes ownership of the provided implementation pointer. + explicit Matcher(MatcherInterface *Implementation) + : Implementation(Implementation) {} + + /// Forwards the call to the underlying MatcherInterface pointer. + bool Matches( + const T &Node, + ASTMatchFinder *Finder, + BoundNodesBuilder *Builder) const { + return Implementation->Matches(Node, Finder, Builder); + } + + /// Implicitly converts this object to a Matcher; requires + /// Derived to be derived from T. + template + operator Matcher() const { + return Matcher(new ImplicitCastMatcher(*this)); + } + + /// Returns an ID that uniquely identifies the matcher. + uint64_t GetID() const { + /// FIXME: Document the requirements this imposes on matcher + /// implementations (no new() implementation_ during a Matches()). + return reinterpret_cast(Implementation.getPtr()); + } + + private: + /// Allows conversion from Matcher to Matcher if Derived + /// is derived from T. + template + class ImplicitCastMatcher : public MatcherInterface { + public: + explicit ImplicitCastMatcher(const Matcher &From) + : From(From) {} + + virtual bool Matches( + const Derived &Node, + ASTMatchFinder *Finder, + BoundNodesBuilder *Builder) const { + return From.Matches(Node, Finder, Builder); + } + + private: + const Matcher From; + }; + + llvm::IntrusiveRefCntPtr< MatcherInterface > Implementation; +}; // class Matcher + +/// A convenient helper for creating a Matcher without specifying +/// the template type argument. +template +inline Matcher MakeMatcher(MatcherInterface *Implementation) { + return Matcher(Implementation); +} + +/// Matches declarations for QualType and CallExpr. Type argument +/// DeclMatcherT is required by PolymorphicMatcherWithParam1 but not +/// actually used. +template +class HasDeclarationMatcher : public MatcherInterface { + COMPILE_ASSERT((llvm::is_same< DeclMatcherT, Matcher >::value), + instantiated_with_wrong_types); + public: + explicit HasDeclarationMatcher(const Matcher &InnerMatcher) + : InnerMatcher(InnerMatcher) {} + + virtual bool Matches( + const T &Node, + ASTMatchFinder *Finder, + BoundNodesBuilder *Builder) const { + return MatchesSpecialized(Node, Finder, Builder); + } + + private: + /// Extracts the CXXRecordDecl of a QualType and returns whether the inner + /// matcher matches on it. + bool MatchesSpecialized( + const clang::QualType &Node, ASTMatchFinder *Finder, + BoundNodesBuilder *Builder) const { + /// FIXME: Add other ways to convert... + clang::CXXRecordDecl *NodeAsRecordDecl = Node->getAsCXXRecordDecl(); + return NodeAsRecordDecl != NULL && + InnerMatcher.Matches(*NodeAsRecordDecl, Finder, Builder); + } + + /// Extracts the Decl of the callee of a CallExpr and returns whether the + /// inner matcher matches on it. + bool MatchesSpecialized( + const clang::CallExpr &Node, ASTMatchFinder *Finder, + BoundNodesBuilder *Builder) const { + const clang::Decl *NodeAsDecl = Node.getCalleeDecl(); + return NodeAsDecl != NULL && + InnerMatcher.Matches(*NodeAsDecl, Finder, Builder); + } + + /// Extracts the Decl of the constructor call and returns whether the inner + /// matcher matches on it. + bool MatchesSpecialized( + const clang::CXXConstructExpr &Node, ASTMatchFinder *Finder, + BoundNodesBuilder *Builder) const { + const clang::Decl *NodeAsDecl = Node.getConstructor(); + return NodeAsDecl != NULL && + InnerMatcher.Matches(*NodeAsDecl, Finder, Builder); + } + + const Matcher InnerMatcher; +}; + +/// IsBaseType::value is true if T is a "base" type in the AST +/// node class hierarchies (i.e. if T is Decl, Stmt, or QualType). +template +struct IsBaseType { + static const bool value = (llvm::is_same::value || + llvm::is_same::value || + llvm::is_same::value); +}; +template +const bool IsBaseType::value; + +/// Interface that can match any AST base node type and contains default +/// implementations returning false. +class UntypedBaseMatcher { + public: + virtual ~UntypedBaseMatcher() {} + + virtual bool Matches( + const clang::Decl &DeclNode, ASTMatchFinder *Finder, + BoundNodesBuilder *Builder) const { + return false; + } + virtual bool Matches( + const clang::QualType &TypeNode, ASTMatchFinder *Finder, + BoundNodesBuilder *Builder) const { + return false; + } + virtual bool Matches( + const clang::Stmt &StmtNode, ASTMatchFinder *Finder, + BoundNodesBuilder *Builder) const { + return false; + } + + /// Returns a unique ID for the matcher. + virtual uint64_t GetID() const = 0; +}; + +/// An UntypedBaseMatcher that overwrites the Matches(...) method for node +/// type T. T must be an AST base type. +template +class TypedBaseMatcher : public UntypedBaseMatcher { + COMPILE_ASSERT(IsBaseType::value, + typed_base_matcher_can_only_be_used_with_base_type); + public: + explicit TypedBaseMatcher(const Matcher &InnerMatcher) + : InnerMatcher(InnerMatcher) {} + + using UntypedBaseMatcher::Matches; + /// Implements UntypedBaseMatcher::Matches. Since T is guaranteed to + /// be a "base" AST node type, this method is guaranteed to override + /// one of the Matches() methods from UntypedBaseMatcher. + virtual bool Matches(const T &Node, + ASTMatchFinder *Finder, + BoundNodesBuilder *Builder) const { + return InnerMatcher.Matches(Node, Finder, Builder); + } + + /// Implements UntypedBaseMatcher::GetID. + virtual uint64_t GetID() const { + return InnerMatcher.GetID(); + } + + private: + Matcher InnerMatcher; +}; + +/// Interface that allows matchers to traverse the AST. +/// This provides two entry methods for each base node type in the AST: +/// - MatchesChildOf: +/// Matches a matcher on every child node of the given node. Returns true +/// if at least one child node could be matched. +/// - MatchesDescendantOf: +/// Matches a matcher on all descendant nodes of the given node. Returns true +/// if at least one descendant matched. +class ASTMatchFinder { + public: + /// Defines how we descend a level in the AST when we pass + /// through expressions. + enum TraversalMethod { + /// Will traverse any child nodes. + kAsIs, + /// Will not traverse implicit casts and parentheses. + kIgnoreImplicitCastsAndParentheses + }; + + virtual ~ASTMatchFinder() {} + + /// Returns true if the given class is directly or indirectly derived + /// from a base type with the given name. A class is considered to + /// be also derived from itself. + virtual bool ClassIsDerivedFrom(const clang::CXXRecordDecl *Declaration, + const std::string &BaseName) const = 0; + + // FIXME: Implement for other base nodes. + virtual bool MatchesChildOf(const clang::Decl &DeclNode, + const UntypedBaseMatcher &BaseMatcher, + BoundNodesBuilder *Builder, + TraversalMethod Traverse) = 0; + virtual bool MatchesChildOf(const clang::Stmt &StmtNode, + const UntypedBaseMatcher &BaseMatcher, + BoundNodesBuilder *Builder, + TraversalMethod Traverse) = 0; + + virtual bool MatchesDescendantOf(const clang::Decl &DeclNode, + const UntypedBaseMatcher &BaseMatcher, + BoundNodesBuilder *Builder) = 0; + virtual bool MatchesDescendantOf(const clang::Stmt &StmtNode, + const UntypedBaseMatcher &BaseMatcher, + BoundNodesBuilder *Builder) = 0; +}; + +/// Converts a Matcher to a matcher of desired type To by "adapting" +/// a To into a T. The ArgumentAdapterT argument specifies how the +/// adaptation is done. For example: +/// +/// ArgumentAdaptingMatcher(InnerMatcher); +/// returns a matcher that can be used where a Matcher is required, if +/// To and T are in the same type hierarchy, and thus dyn_cast can be +/// called to convert a To to a T. +/// +/// FIXME: Make sure all our applications of this class actually require +/// knowledge about the inner type. DynCastMatcher obviously does, but the +/// Has *matchers require the inner type solely for COMPILE_ASSERT purposes. +template