XRefs.cpp | Explore in Territory

//===--- XRefs.cpp -----------------------------------------------*- C++-*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "XRefs.h"
#include "AST.h"
#include "FindSymbols.h"
#include "FindTarget.h"
#include "Headers.h"
#include "HeuristicResolver.h"
#include "IncludeCleaner.h"
#include "ParsedAST.h"
#include "Protocol.h"
#include "Quality.h"
#include "Selection.h"
#include "SourceCode.h"
#include "URI.h"
#include "clang-include-cleaner/Analysis.h"
#include "clang-include-cleaner/Types.h"
#include "index/Index.h"
#include "index/Merge.h"
#include "index/Relation.h"
#include "index/SymbolCollector.h"
#include "index/SymbolID.h"
#include "index/SymbolLocation.h"
#include "support/Logger.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/ASTTypeTraits.h"
#include "clang/AST/Attr.h"
#include "clang/AST/Attrs.inc"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/DeclObjC.h"
#include "clang/AST/DeclTemplate.h"
#include "clang/AST/DeclVisitor.h"
#include "clang/AST/ExprCXX.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/AST/Stmt.h"
#include "clang/AST/StmtCXX.h"
#include "clang/AST/StmtVisitor.h"
#include "clang/AST/Type.h"
#include "clang/Basic/LLVM.h"
#include "clang/Basic/LangOptions.h"
#include "clang/Basic/SourceLocation.h"
#include "clang/Basic/SourceManager.h"
#include "clang/Basic/TokenKinds.h"
#include "clang/Index/IndexDataConsumer.h"
#include "clang/Index/IndexSymbol.h"
#include "clang/Index/IndexingAction.h"
#include "clang/Index/IndexingOptions.h"
#include "clang/Index/USRGeneration.h"
#include "clang/Lex/Lexer.h"
#include "clang/Tooling/Syntax/Tokens.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Error.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/raw_ostream.h"
#include <optional>
#include <string>
#include <vector>

namespace clang {
namespace clangd {
namespace {

// Returns the single definition of the entity declared by D, if visible.
// In particular:
// - for non-redeclarable kinds (e.g. local vars), return D
// - for kinds that allow multiple definitions (e.g. namespaces), return nullptr
// Kinds of nodes that always return nullptr here will not have definitions
// reported by locateSymbolAt().
const NamedDecl *getDefinition(const NamedDecl *D) { … }

void logIfOverflow(const SymbolLocation &Loc) { … }

// Convert a SymbolLocation to LSP's Location.
// TUPath is used to resolve the path of URI.
// FIXME: figure out a good home for it, and share the implementation with
// FindSymbols.
std::optional<Location> toLSPLocation(const SymbolLocation &Loc,
                                      llvm::StringRef TUPath) { … }

SymbolLocation toIndexLocation(const Location &Loc, std::string &URIStorage) { … }

// Returns the preferred location between an AST location and an index location.
SymbolLocation getPreferredLocation(const Location &ASTLoc,
                                    const SymbolLocation &IdxLoc,
                                    std::string &Scratch) { … }

std::vector<std::pair<const NamedDecl *, DeclRelationSet>>
getDeclAtPositionWithRelations(ParsedAST &AST, SourceLocation Pos,
                               DeclRelationSet Relations,
                               ASTNodeKind *NodeKind = nullptr) { … }

std::vector<const NamedDecl *>
getDeclAtPosition(ParsedAST &AST, SourceLocation Pos, DeclRelationSet Relations,
                  ASTNodeKind *NodeKind = nullptr) { … }

// Expects Loc to be a SpellingLocation, will bail out otherwise as it can't
// figure out a filename.
std::optional<Location> makeLocation(const ASTContext &AST, SourceLocation Loc,
                                     llvm::StringRef TUPath) { … }

// Treat #included files as symbols, to enable go-to-definition on them.
std::optional<LocatedSymbol> locateFileReferent(const Position &Pos,
                                                ParsedAST &AST,
                                                llvm::StringRef MainFilePath) { … }

// Macros are simple: there's no declaration/definition distinction.
// As a consequence, there's no need to look them up in the index either.
std::optional<LocatedSymbol>
locateMacroReferent(const syntax::Token &TouchedIdentifier, ParsedAST &AST,
                    llvm::StringRef MainFilePath) { … }

// A wrapper around `Decl::getCanonicalDecl` to support cases where Clang's
// definition of a canonical declaration doesn't match up to what a programmer
// would expect. For example, Objective-C classes can have three types of
// declarations:
//
// - forward declaration(s): @class MyClass;
// - true declaration (interface definition): @interface MyClass ... @end
// - true definition (implementation): @implementation MyClass ... @end
//
// Clang will consider the forward declaration to be the canonical declaration
// because it is first. We actually want the class definition if it is
// available since that is what a programmer would consider the primary
// declaration to be.
const NamedDecl *getPreferredDecl(const NamedDecl *D) { … }

std::vector<LocatedSymbol> findImplementors(llvm::DenseSet<SymbolID> IDs,
                                            RelationKind Predicate,
                                            const SymbolIndex *Index,
                                            llvm::StringRef MainFilePath) { … }

// Given LocatedSymbol results derived from the AST, query the index to obtain
// definitions and preferred declarations.
void enhanceLocatedSymbolsFromIndex(llvm::MutableArrayRef<LocatedSymbol> Result,
                                    const SymbolIndex *Index,
                                    llvm::StringRef MainFilePath) { … }

// Decls are more complicated.
// The AST contains at least a declaration, maybe a definition.
// These are up-to-date, and so generally preferred over index results.
// We perform a single batch index lookup to find additional definitions.
std::vector<LocatedSymbol>
locateASTReferent(SourceLocation CurLoc, const syntax::Token *TouchedIdentifier,
                  ParsedAST &AST, llvm::StringRef MainFilePath,
                  const SymbolIndex *Index, ASTNodeKind &NodeKind) { … }

std::vector<LocatedSymbol> locateSymbolForType(const ParsedAST &AST,
                                               const QualType &Type,
                                               const SymbolIndex *Index) { … }

bool tokenSpelledAt(SourceLocation SpellingLoc, const syntax::TokenBuffer &TB) { … }

llvm::StringRef sourcePrefix(SourceLocation Loc, const SourceManager &SM) { … }

bool isDependentName(ASTNodeKind NodeKind) { … }

} // namespace

std::vector<LocatedSymbol> locateSymbolTextually(const SpelledWord &Word,
                                                 ParsedAST &AST,
                                                 const SymbolIndex *Index,
                                                 llvm::StringRef MainFilePath,
                                                 ASTNodeKind NodeKind) { … }

const syntax::Token *findNearbyIdentifier(const SpelledWord &Word,
                                          const syntax::TokenBuffer &TB) { … }

std::vector<LocatedSymbol> locateSymbolAt(ParsedAST &AST, Position Pos,
                                          const SymbolIndex *Index) { … }

std::vector<DocumentLink> getDocumentLinks(ParsedAST &AST) { … }

namespace {

/// Collects references to symbols within the main file.
class ReferenceFinder : public index::IndexDataConsumer { … };

std::vector<ReferenceFinder::Reference>
findRefs(const llvm::ArrayRef<const NamedDecl *> TargetDecls, ParsedAST &AST,
         bool PerToken) { … }

const Stmt *getFunctionBody(DynTypedNode N) { … }

const Stmt *getLoopBody(DynTypedNode N) { … }

// AST traversal to highlight control flow statements under some root.
// Once we hit further control flow we prune the tree (or at least restrict
// what we highlight) so we capture e.g. breaks from the outer loop only.
class FindControlFlow : public RecursiveASTVisitor<FindControlFlow> { … };

// Given a location within a switch statement, return the half-open range that
// covers the case it's contained in.
// We treat `case X: case Y: ...` as one case, and assume no other fallthrough.
SourceRange findCaseBounds(const SwitchStmt &Switch, SourceLocation Loc,
                           const SourceManager &SM) { … }

// Returns the locations of control flow statements related to N. e.g.:
//   for    => branches: break/continue/return/throw
//   break  => controlling loop (forwhile/do), and its related control flow
//   return => all returns/throws from the same function
// When an inner block is selected, we include branches bound to outer blocks
// as these are exits from the inner block. e.g. return in a for loop.
// FIXME: We don't analyze catch blocks, throw is treated the same as return.
std::vector<SourceLocation> relatedControlFlow(const SelectionTree::Node &N) { … }

DocumentHighlight toHighlight(const ReferenceFinder::Reference &Ref,
                              const SourceManager &SM) { … }

std::optional<DocumentHighlight> toHighlight(SourceLocation Loc,
                                             const syntax::TokenBuffer &TB) { … }

} // namespace

std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
                                                      Position Pos) { … }

std::vector<LocatedSymbol> findImplementations(ParsedAST &AST, Position Pos,
                                               const SymbolIndex *Index) { … }

namespace {
// Recursively finds all the overridden methods of `CMD` in complete type
// hierarchy.
void getOverriddenMethods(const CXXMethodDecl *CMD,
                          llvm::DenseSet<SymbolID> &OverriddenMethods) { … }

std::optional<std::string>
stringifyContainerForMainFileRef(const Decl *Container) { … }

std::optional<ReferencesResult>
maybeFindIncludeReferences(ParsedAST &AST, Position Pos,
                           URIForFile URIMainFile) { … }
} // namespace

ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit,
                                const SymbolIndex *Index, bool AddContext) { … }

std::vector<SymbolDetails> getSymbolInfo(ParsedAST &AST, Position Pos) { … }

llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LocatedSymbol &S) { … }

llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                              const ReferencesResult::Reference &R) { … }

template <typename HierarchyItem>
static std::optional<HierarchyItem>
declToHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) { … }

static std::optional<TypeHierarchyItem>
declToTypeHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) { … }

static std::optional<CallHierarchyItem>
declToCallHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) { … }

template <typename HierarchyItem>
static std::optional<HierarchyItem> symbolToHierarchyItem(const Symbol &S,
                                                          PathRef TUPath) { … }

static std::optional<TypeHierarchyItem>
symbolToTypeHierarchyItem(const Symbol &S, PathRef TUPath) { … }

static std::optional<CallHierarchyItem>
symbolToCallHierarchyItem(const Symbol &S, PathRef TUPath) { … }

static void fillSubTypes(const SymbolID &ID,
                         std::vector<TypeHierarchyItem> &SubTypes,
                         const SymbolIndex *Index, int Levels, PathRef TUPath) { … }

RecursionProtectionSet;

// Extracts parents from AST and populates the type hierarchy item.
static void fillSuperTypes(const CXXRecordDecl &CXXRD, llvm::StringRef TUPath,
                           TypeHierarchyItem &Item,
                           RecursionProtectionSet &RPSet) { … }

std::vector<const CXXRecordDecl *> findRecordTypeAt(ParsedAST &AST,
                                                    Position Pos) { … }

// Return the type most associated with an AST node.
// This isn't precisely defined: we want "go to type" to do something useful.
static QualType typeForNode(const SelectionTree::Node *N) { … }

// Given a type targeted by the cursor, return one or more types that are more interesting
// to target.
static void unwrapFindType(
    QualType T, const HeuristicResolver* H, llvm::SmallVector<QualType>& Out) { … }

// Convenience overload, to allow calling this without the out-parameter
static llvm::SmallVector<QualType> unwrapFindType(
    QualType T, const HeuristicResolver* H) { … }

std::vector<LocatedSymbol> findType(ParsedAST &AST, Position Pos,
                                    const SymbolIndex *Index) { … }

std::vector<const CXXRecordDecl *> typeParents(const CXXRecordDecl *CXXRD) { … }

std::vector<TypeHierarchyItem>
getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
                 TypeHierarchyDirection Direction, const SymbolIndex *Index,
                 PathRef TUPath) { … }

std::optional<std::vector<TypeHierarchyItem>>
superTypes(const TypeHierarchyItem &Item, const SymbolIndex *Index) { … }

std::vector<TypeHierarchyItem> subTypes(const TypeHierarchyItem &Item,
                                        const SymbolIndex *Index) { … }

void resolveTypeHierarchy(TypeHierarchyItem &Item, int ResolveLevels,
                          TypeHierarchyDirection Direction,
                          const SymbolIndex *Index) { … }

std::vector<CallHierarchyItem>
prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath) { … }

std::vector<CallHierarchyIncomingCall>
incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) { … }

llvm::DenseSet<const Decl *> getNonLocalDeclRefs(ParsedAST &AST,
                                                 const FunctionDecl *FD) { … }

} // namespace clangd
} // namespace clang
llvm/clang-tools-extra/clangd/XRefs.cpp
