ASTMatchFinder.cpp | Explore in Territory

//===--- ASTMatchFinder.cpp - Structural query framework ------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
//  Implements an algorithm to efficiently search for matches on AST nodes.
//  Uses memoization to support recursive matches like HasDescendant.
//
//  The general idea is to visit all AST nodes with a RecursiveASTVisitor,
//  calling the Matches(...) method of each matcher we are running on each
//  AST node. The matcher can recurse via the ASTMatchFinder interface.
//
//===----------------------------------------------------------------------===//

#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/AST/ASTConsumer.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/Support/PrettyStackTrace.h"
#include "llvm/Support/Timer.h"
#include <deque>
#include <memory>
#include <set>

namespace clang {
namespace ast_matchers {
namespace internal {
namespace {

MatchCallback;

// The maximum number of memoization entries to store.
// 10k has been experimentally found to give a good trade-off
// of performance vs. memory consumption by running matcher
// that match on every statement over a very large codebase.
//
// FIXME: Do some performance optimization in general and
// revisit this number; also, put up micro-benchmarks that we can
// optimize this on.
static const unsigned MaxMemoizationEntries = …;

enum class MatchType { … };

// We use memoization to avoid running the same matcher on the same
// AST node twice.  This struct is the key for looking up match
// result.  It consists of an ID of the MatcherInterface (for
// identifying the matcher), a pointer to the AST node and the
// bound nodes before the matcher was executed.
//
// We currently only memoize on nodes whose pointers identify the
// nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
// For \c QualType and \c TypeLoc it is possible to implement
// generation of keys for each type.
// FIXME: Benchmark whether memoization of non-pointer typed nodes
// provides enough benefit for the additional amount of code.
struct MatchKey { … };

// Used to store the result of a match and possibly bound nodes.
struct MemoizedMatchResult { … };

// A RecursiveASTVisitor that traverses all children or all descendants of
// a node.
class MatchChildASTVisitor
    : public RecursiveASTVisitor<MatchChildASTVisitor> { … };

// Controls the outermost traversal of the AST and allows to match multiple
// matchers.
class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
                        public ASTMatchFinder { … };

static CXXRecordDecl *
getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) { … }

// Returns true if the given C++ class is directly or indirectly derived
// from a base type with the given name.  A class is not considered to be
// derived from itself.
bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
                                         const Matcher<NamedDecl> &Base,
                                         BoundNodesTreeBuilder *Builder,
                                         bool Directly) { … }

bool MatchASTVisitor::classIsDerivedFromImpl(
    const CXXRecordDecl *Declaration, const Matcher<NamedDecl> &Base,
    BoundNodesTreeBuilder *Builder, bool Directly,
    llvm::SmallPtrSetImpl<const CXXRecordDecl *> &Visited) { … }

// Returns true if the given Objective-C class is directly or indirectly
// derived from a matching base class. A class is not considered to be derived
// from itself.
bool MatchASTVisitor::objcClassIsDerivedFrom(
    const ObjCInterfaceDecl *Declaration, const Matcher<NamedDecl> &Base,
    BoundNodesTreeBuilder *Builder, bool Directly) { … }

bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) { … }

bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) { … }

bool MatchASTVisitor::TraverseType(QualType TypeNode) { … }

bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) { … }

bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) { … }

bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
    NestedNameSpecifierLoc NNS) { … }

bool MatchASTVisitor::TraverseConstructorInitializer(
    CXXCtorInitializer *CtorInit) { … }

bool MatchASTVisitor::TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc) { … }

bool MatchASTVisitor::TraverseAttr(Attr *AttrNode) { … }

class MatchASTConsumer : public ASTConsumer { … };

} // end namespace
} // end namespace internal

MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
                                      ASTContext *Context)
  : … { … }

MatchFinder::MatchCallback::~MatchCallback() { … }
MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() { … }

MatchFinder::MatchFinder(MatchFinderOptions Options)
    : … { … }

MatchFinder::~MatchFinder() { … }

void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
                             MatchCallback *Action) { … }

void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
                             MatchCallback *Action) { … }

void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
                             MatchCallback *Action) { … }

void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
                             MatchCallback *Action) { … }

void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
                             MatchCallback *Action) { … }

void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
                             MatchCallback *Action) { … }

void MatchFinder::addMatcher(const CXXCtorInitializerMatcher &NodeMatch,
                             MatchCallback *Action) { … }

void MatchFinder::addMatcher(const TemplateArgumentLocMatcher &NodeMatch,
                             MatchCallback *Action) { … }

void MatchFinder::addMatcher(const AttrMatcher &AttrMatch,
                             MatchCallback *Action) { … }

bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
                                    MatchCallback *Action) { … }

std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() { … }

void MatchFinder::match(const clang::DynTypedNode &Node, ASTContext &Context) { … }

void MatchFinder::matchAST(ASTContext &Context) { … }

void MatchFinder::registerTestCallbackAfterParsing(
    MatchFinder::ParsingDoneTestCallback *NewParsingDone) { … }

StringRef MatchFinder::MatchCallback::getID() const { … }

std::optional<TraversalKind>
MatchFinder::MatchCallback::getCheckTraversalKind() const { … }

} // end namespace ast_matchers
} // end namespace clang
llvm/clang/lib/ASTMatchers/ASTMatchFinder.cpp
