Mercurial > hg > CbC > CbC_llvm
diff clang-tools-extra/clangd/XRefs.cpp @ 221:79ff65ed7e25
LLVM12 Original
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 15 Jun 2021 19:15:29 +0900 |
| parents | 0572611fdcc8 |
| children | c4bab56944e8 |
line wrap: on
line diff
--- a/clang-tools-extra/clangd/XRefs.cpp Tue Jun 15 19:13:43 2021 +0900 +++ b/clang-tools-extra/clangd/XRefs.cpp Tue Jun 15 19:15:29 2021 +0900 @@ -27,8 +27,13 @@ #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/ExprCXX.h" +#include "clang/AST/ExternalASTSource.h" +#include "clang/AST/RecursiveASTVisitor.h" +#include "clang/AST/Stmt.h" +#include "clang/AST/StmtCXX.h" #include "clang/AST/Type.h" #include "clang/Basic/CharInfo.h" #include "clang/Basic/LLVM.h" @@ -43,8 +48,10 @@ #include "clang/Index/USRGeneration.h" #include "clang/Tooling/Syntax/Tokens.h" #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/MapVector.h" #include "llvm/ADT/None.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/ScopeExit.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringRef.h" @@ -73,6 +80,32 @@ return VD->getDefinition(); if (const auto *FD = dyn_cast<FunctionDecl>(D)) return FD->getDefinition(); + // Objective-C classes can have three types of declarations: + // + // - forward declaration: @class MyClass; + // - true declaration (interface definition): @interface MyClass ... @end + // - true definition (implementation): @implementation MyClass ... @end + // + // Objective-C categories are extensions are on classes: + // + // - declaration: @interface MyClass (Ext) ... @end + // - definition: @implementation MyClass (Ext) ... @end + // + // With one special case, a class extension, which is normally used to keep + // some declarations internal to a file without exposing them in a header. + // + // - class extension declaration: @interface MyClass () ... @end + // - which really links to class definition: @implementation MyClass ... @end + if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(D)) + return ID->getImplementation(); + if (const auto *CD = dyn_cast<ObjCCategoryDecl>(D)) { + if (CD->IsClassExtension()) { + if (const auto *ID = CD->getClassInterface()) + return ID->getImplementation(); + return nullptr; + } + return CD->getImplementation(); + } // Only a single declaration is allowed. if (isa<ValueDecl>(D) || isa<TemplateTypeParmDecl>(D) || isa<TemplateTemplateParmDecl>(D)) // except cases above @@ -130,32 +163,44 @@ SymbolLocation getPreferredLocation(const Location &ASTLoc, const SymbolLocation &IdxLoc, std::string &Scratch) { - // Also use a dummy symbol for the index location so that other fields (e.g. + // Also use a mock symbol for the index location so that other fields (e.g. // definition) are not factored into the preference. Symbol ASTSym, IdxSym; - ASTSym.ID = IdxSym.ID = SymbolID("dummy_id"); + ASTSym.ID = IdxSym.ID = SymbolID("mock_symbol_id"); ASTSym.CanonicalDeclaration = toIndexLocation(ASTLoc, Scratch); IdxSym.CanonicalDeclaration = IdxLoc; auto Merged = mergeSymbol(ASTSym, IdxSym); return Merged.CanonicalDeclaration; } +std::vector<std::pair<const NamedDecl *, DeclRelationSet>> +getDeclAtPositionWithRelations(ParsedAST &AST, SourceLocation Pos, + DeclRelationSet Relations, + ASTNodeKind *NodeKind = nullptr) { + unsigned Offset = AST.getSourceManager().getDecomposedSpellingLoc(Pos).second; + std::vector<std::pair<const NamedDecl *, DeclRelationSet>> Result; + auto ResultFromTree = [&](SelectionTree ST) { + if (const SelectionTree::Node *N = ST.commonAncestor()) { + if (NodeKind) + *NodeKind = N->ASTNode.getNodeKind(); + llvm::copy_if(allTargetDecls(N->ASTNode, AST.getHeuristicResolver()), + std::back_inserter(Result), + [&](auto &Entry) { return !(Entry.second & ~Relations); }); + } + return !Result.empty(); + }; + SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset, + Offset, ResultFromTree); + return Result; +} + std::vector<const NamedDecl *> getDeclAtPosition(ParsedAST &AST, SourceLocation Pos, DeclRelationSet Relations, ASTNodeKind *NodeKind = nullptr) { - unsigned Offset = AST.getSourceManager().getDecomposedSpellingLoc(Pos).second; std::vector<const NamedDecl *> Result; - SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset, - Offset, [&](SelectionTree ST) { - if (const SelectionTree::Node *N = - ST.commonAncestor()) { - if (NodeKind) - *NodeKind = N->ASTNode.getNodeKind(); - llvm::copy(targetDecl(N->ASTNode, Relations), - std::back_inserter(Result)); - } - return !Result.empty(); - }); + for (auto &Entry : + getDeclAtPositionWithRelations(AST, Pos, Relations, NodeKind)) + Result.push_back(Entry.first); return Result; } @@ -206,18 +251,91 @@ locateMacroReferent(const syntax::Token &TouchedIdentifier, ParsedAST &AST, llvm::StringRef MainFilePath) { if (auto M = locateMacroAt(TouchedIdentifier, AST.getPreprocessor())) { - if (auto Loc = makeLocation(AST.getASTContext(), - M->Info->getDefinitionLoc(), MainFilePath)) { + if (auto Loc = + makeLocation(AST.getASTContext(), M->NameLoc, MainFilePath)) { LocatedSymbol Macro; Macro.Name = std::string(M->Name); Macro.PreferredDeclaration = *Loc; Macro.Definition = Loc; + Macro.ID = getSymbolID(M->Name, M->Info, AST.getSourceManager()); return Macro; } } return llvm::None; } +// 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) { + // FIXME: Canonical declarations of some symbols might refer to built-in + // decls with possibly-invalid source locations (e.g. global new operator). + // In such cases we should pick up a redecl with valid source location + // instead of failing. + D = llvm::cast<NamedDecl>(D->getCanonicalDecl()); + + // Prefer Objective-C class/protocol definitions over the forward declaration. + if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(D)) + if (const auto *DefinitionID = ID->getDefinition()) + return DefinitionID; + if (const auto *PD = dyn_cast<ObjCProtocolDecl>(D)) + if (const auto *DefinitionID = PD->getDefinition()) + return DefinitionID; + + return D; +} + +std::vector<LocatedSymbol> findImplementors(llvm::DenseSet<SymbolID> IDs, + RelationKind Predicate, + const SymbolIndex *Index, + llvm::StringRef MainFilePath) { + if (IDs.empty() || !Index) + return {}; + static constexpr trace::Metric FindImplementorsMetric( + "find_implementors", trace::Metric::Counter, "case"); + switch (Predicate) { + case RelationKind::BaseOf: + FindImplementorsMetric.record(1, "find-base"); + break; + case RelationKind::OverriddenBy: + FindImplementorsMetric.record(1, "find-override"); + break; + } + + RelationsRequest Req; + Req.Predicate = Predicate; + Req.Subjects = std::move(IDs); + std::vector<LocatedSymbol> Results; + Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) { + auto DeclLoc = + indexToLSPLocation(Object.CanonicalDeclaration, MainFilePath); + if (!DeclLoc) { + elog("Find overrides: {0}", DeclLoc.takeError()); + return; + } + Results.emplace_back(); + Results.back().Name = Object.Name.str(); + Results.back().PreferredDeclaration = *DeclLoc; + auto DefLoc = indexToLSPLocation(Object.Definition, MainFilePath); + if (!DefLoc) { + elog("Failed to convert location: {0}", DefLoc.takeError()); + return; + } + Results.back().Definition = *DefLoc; + }); + return Results; +} + // 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. @@ -232,8 +350,10 @@ // Keep track of SymbolID -> index mapping, to fill in index data later. llvm::DenseMap<SymbolID, size_t> ResultIndex; + static constexpr trace::Metric LocateASTReferentMetric( + "locate_ast_referent", trace::Metric::Counter, "case"); auto AddResultDecl = [&](const NamedDecl *D) { - D = llvm::cast<NamedDecl>(D->getCanonicalDecl()); + D = getPreferredDecl(D); auto Loc = makeLocation(AST.getASTContext(), nameLocation(*D, SM), MainFilePath); if (!Loc) @@ -242,28 +362,43 @@ Result.emplace_back(); Result.back().Name = printName(AST.getASTContext(), *D); Result.back().PreferredDeclaration = *Loc; + Result.back().ID = getSymbolID(D); if (const NamedDecl *Def = getDefinition(D)) Result.back().Definition = makeLocation( AST.getASTContext(), nameLocation(*Def, SM), MainFilePath); // Record SymbolID for index lookup later. if (auto ID = getSymbolID(D)) - ResultIndex[*ID] = Result.size() - 1; + ResultIndex[ID] = Result.size() - 1; }; // Emit all symbol locations (declaration or definition) from AST. DeclRelationSet Relations = DeclRelation::TemplatePattern | DeclRelation::Alias; - for (const NamedDecl *D : - getDeclAtPosition(AST, CurLoc, Relations, NodeKind)) { - // Special case: void foo() ^override: jump to the overridden method. + auto Candidates = + getDeclAtPositionWithRelations(AST, CurLoc, Relations, NodeKind); + llvm::DenseSet<SymbolID> VirtualMethods; + for (const auto &E : Candidates) { + const NamedDecl *D = E.first; if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D)) { + // Special case: virtual void ^method() = 0: jump to all overrides. + // FIXME: extend it to ^virtual, unfortunately, virtual location is not + // saved in the AST. + if (CMD->isPure()) { + if (TouchedIdentifier && SM.getSpellingLoc(CMD->getLocation()) == + TouchedIdentifier->location()) { + VirtualMethods.insert(getSymbolID(CMD)); + LocateASTReferentMetric.record(1, "method-to-override"); + } + } + // Special case: void foo() ^override: jump to the overridden method. const InheritableAttr *Attr = D->getAttr<OverrideAttr>(); if (!Attr) Attr = D->getAttr<FinalAttr>(); if (Attr && TouchedIdentifier && SM.getSpellingLoc(Attr->getLocation()) == TouchedIdentifier->location()) { + LocateASTReferentMetric.record(1, "method-to-base"); // We may be overridding multiple methods - offer them all. for (const NamedDecl *ND : CMD->overridden_methods()) AddResultDecl(ND); @@ -271,16 +406,45 @@ } } + // Special case: the cursor is on an alias, prefer other results. + // This targets "using ns::^Foo", where the target is more interesting. + // This does not trigger on renaming aliases: + // `using Foo = ^Bar` already targets Bar via a TypeLoc + // `using ^Foo = Bar` has no other results, as Underlying is filtered. + if (E.second & DeclRelation::Alias && Candidates.size() > 1 && + // beginLoc/endLoc are a token range, so rewind the identifier we're in. + SM.isPointWithin(TouchedIdentifier ? TouchedIdentifier->location() + : CurLoc, + D->getBeginLoc(), D->getEndLoc())) + continue; + // Special case: the point of declaration of a template specialization, // it's more useful to navigate to the template declaration. if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(D)) { if (TouchedIdentifier && D->getLocation() == TouchedIdentifier->location()) { + LocateASTReferentMetric.record(1, "template-specialization-to-primary"); AddResultDecl(CTSD->getSpecializedTemplate()); continue; } } + // Special case: if the class name is selected, also map Objective-C + // categories and category implementations back to their class interface. + // + // Since `TouchedIdentifier` might refer to the `ObjCCategoryImplDecl` + // instead of the `ObjCCategoryDecl` we intentionally check the contents + // of the locs when checking for class name equivalence. + if (const auto *CD = dyn_cast<ObjCCategoryDecl>(D)) + if (const auto *ID = CD->getClassInterface()) + if (TouchedIdentifier && + (CD->getLocation() == TouchedIdentifier->location() || + ID->getName() == TouchedIdentifier->text(SM))) { + LocateASTReferentMetric.record(1, "objc-category-to-class"); + AddResultDecl(ID); + } + + LocateASTReferentMetric.record(1, "regular"); // Otherwise the target declaration is the right one. AddResultDecl(D); } @@ -319,9 +483,50 @@ }); } + auto Overrides = findImplementors(VirtualMethods, RelationKind::OverriddenBy, + Index, MainFilePath); + Result.insert(Result.end(), Overrides.begin(), Overrides.end()); return Result; } +std::vector<LocatedSymbol> locateSymbolForType(const ParsedAST &AST, + const QualType &Type) { + const auto &SM = AST.getSourceManager(); + auto MainFilePath = + getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM); + if (!MainFilePath) { + elog("Failed to get a path for the main file, so no symbol."); + return {}; + } + + auto Decls = targetDecl(DynTypedNode::create(Type.getNonReferenceType()), + DeclRelation::TemplatePattern | DeclRelation::Alias, + AST.getHeuristicResolver()); + if (Decls.empty()) + return {}; + + std::vector<LocatedSymbol> Results; + const auto &ASTContext = AST.getASTContext(); + + for (const NamedDecl *D : Decls) { + D = getPreferredDecl(D); + + auto Loc = makeLocation(ASTContext, nameLocation(*D, SM), *MainFilePath); + if (!Loc) + continue; + + Results.emplace_back(); + Results.back().Name = printName(ASTContext, *D); + Results.back().PreferredDeclaration = *Loc; + Results.back().ID = getSymbolID(D); + if (const NamedDecl *Def = getDefinition(D)) + Results.back().Definition = + makeLocation(ASTContext, nameLocation(*Def, SM), *MainFilePath); + } + + return Results; +} + bool tokenSpelledAt(SourceLocation SpellingLoc, const syntax::TokenBuffer &TB) { auto ExpandedTokens = TB.expandedTokens( TB.sourceManager().getMacroArgExpandedLocation(SpellingLoc)); @@ -358,8 +563,8 @@ if ((Word.ExpandedToken && !isDependentName(NodeKind)) || !Word.LikelyIdentifier || !Index) return {}; - // We don't want to handle words in string literals. It'd be nice to whitelist - // comments instead, but they're not retained in TokenBuffer. + // We don't want to handle words in string literals. (It'd be nice to list + // *allowed* token kinds explicitly, but comment Tokens aren't retained). if (Word.PartOfSpelledToken && isStringLiteral(Word.PartOfSpelledToken->kind())) return {}; @@ -400,46 +605,47 @@ log("locateSymbolNamedTextuallyAt: {0}", MaybeDeclLoc.takeError()); return; } - Location DeclLoc = *MaybeDeclLoc; - Location DefLoc; + LocatedSymbol Located; + Located.PreferredDeclaration = *MaybeDeclLoc; + Located.Name = (Sym.Name + Sym.TemplateSpecializationArgs).str(); + Located.ID = Sym.ID; if (Sym.Definition) { auto MaybeDefLoc = indexToLSPLocation(Sym.Definition, MainFilePath); if (!MaybeDefLoc) { log("locateSymbolNamedTextuallyAt: {0}", MaybeDefLoc.takeError()); return; } - DefLoc = *MaybeDefLoc; + Located.PreferredDeclaration = *MaybeDefLoc; + Located.Definition = *MaybeDefLoc; } - if (ScoredResults.size() >= 3) { - // If we have more than 3 results, don't return anything, + if (ScoredResults.size() >= 5) { + // If we have more than 5 results, don't return anything, // as confidence is too low. // FIXME: Alternatively, try a stricter query? TooMany = true; return; } - LocatedSymbol Located; - Located.Name = (Sym.Name + Sym.TemplateSpecializationArgs).str(); - Located.PreferredDeclaration = bool(Sym.Definition) ? DefLoc : DeclLoc; - Located.Definition = DefLoc; - SymbolQualitySignals Quality; Quality.merge(Sym); SymbolRelevanceSignals Relevance; Relevance.Name = Sym.Name; Relevance.Query = SymbolRelevanceSignals::Generic; Relevance.merge(Sym); - auto Score = - evaluateSymbolAndRelevance(Quality.evaluate(), Relevance.evaluate()); + auto Score = evaluateSymbolAndRelevance(Quality.evaluateHeuristics(), + Relevance.evaluateHeuristics()); dlog("locateSymbolNamedTextuallyAt: {0}{1} = {2}\n{3}{4}\n", Sym.Scope, Sym.Name, Score, Quality, Relevance); ScoredResults.push_back({Score, std::move(Located)}); }); - if (TooMany) + if (TooMany) { + vlog("Heuristic index lookup for {0} returned too many candidates, ignored", + Word.Text); return {}; + } llvm::sort(ScoredResults, [](const ScoredLocatedSymbol &A, const ScoredLocatedSymbol &B) { @@ -448,6 +654,10 @@ std::vector<LocatedSymbol> Results; for (auto &Res : std::move(ScoredResults)) Results.push_back(std::move(Res.second)); + if (Results.empty()) + vlog("No heuristic index definition for {0}", Word.Text); + else + log("Found definition heuristically in index for {0}", Word.Text); return Results; } @@ -457,8 +667,8 @@ // Unlikely identifiers are OK if they were used as identifiers nearby. if (Word.ExpandedToken) return nullptr; - // We don't want to handle words in string literals. It'd be nice to whitelist - // comments instead, but they're not retained in TokenBuffer. + // We don't want to handle words in string literals. (It'd be nice to list + // *allowed* token kinds explicitly, but comment Tokens aren't retained). if (Word.PartOfSpelledToken && isStringLiteral(Word.PartOfSpelledToken->kind())) return {}; @@ -471,19 +681,34 @@ auto Cost = [&](SourceLocation Loc) -> unsigned { assert(SM.getFileID(Loc) == File && "spelled token in wrong file?"); unsigned Line = SM.getSpellingLineNumber(Loc); - if (Line > WordLine) - return 1 + llvm::Log2_64(Line - WordLine); - if (Line < WordLine) - return 2 + llvm::Log2_64(WordLine - Line); - return 0; + return Line >= WordLine ? Line - WordLine : 2 * (WordLine - Line); }; const syntax::Token *BestTok = nullptr; - // Search bounds are based on word length: 2^N lines forward. - unsigned BestCost = Word.Text.size() + 1; + unsigned BestCost = -1; + // Search bounds are based on word length: + // - forward: 2^N lines + // - backward: 2^(N-1) lines. + unsigned MaxDistance = + 1U << std::min<unsigned>(Word.Text.size(), + std::numeric_limits<unsigned>::digits - 1); + // Line number for SM.translateLineCol() should be one-based, also + // SM.translateLineCol() can handle line number greater than + // number of lines in the file. + // - LineMin = max(1, WordLine + 1 - 2^(N-1)) + // - LineMax = WordLine + 1 + 2^N + unsigned LineMin = + WordLine + 1 <= MaxDistance / 2 ? 1 : WordLine + 1 - MaxDistance / 2; + unsigned LineMax = WordLine + 1 + MaxDistance; + SourceLocation LocMin = SM.translateLineCol(File, LineMin, 1); + assert(LocMin.isValid()); + SourceLocation LocMax = SM.translateLineCol(File, LineMax, 1); + assert(LocMax.isValid()); // Updates BestTok and BestCost if Tok is a good candidate. // May return true if the cost is too high for this token. auto Consider = [&](const syntax::Token &Tok) { + if (Tok.location() < LocMin || Tok.location() > LocMax) + return true; // we are too far from the word, break the outer loop. if (!(Tok.kind() == tok::identifier && Tok.text(SM) == Word.Text)) return false; // No point guessing the same location we started with. @@ -506,7 +731,7 @@ // Find where the word occurred in the token stream, to search forward & back. auto *I = llvm::partition_point(SpelledTokens, [&](const syntax::Token &T) { assert(SM.getFileID(T.location()) == SM.getFileID(Word.Location)); - return T.location() >= Word.Location; // Comparison OK: same file. + return T.location() < Word.Location; // Comparison OK: same file. }); // Search for matches after the cursor. for (const syntax::Token &Tok : llvm::makeArrayRef(I, SpelledTokens.end())) @@ -547,15 +772,31 @@ return {}; } - const syntax::Token *TouchedIdentifier = - syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens()); - if (TouchedIdentifier) - if (auto Macro = - locateMacroReferent(*TouchedIdentifier, AST, *MainFilePath)) - // Don't look at the AST or index if we have a macro result. - // (We'd just return declarations referenced from the macro's - // expansion.) - return {*std::move(Macro)}; + const syntax::Token *TouchedIdentifier = nullptr; + auto TokensTouchingCursor = + syntax::spelledTokensTouching(*CurLoc, AST.getTokens()); + for (const syntax::Token &Tok : TokensTouchingCursor) { + if (Tok.kind() == tok::identifier) { + if (auto Macro = locateMacroReferent(Tok, AST, *MainFilePath)) + // Don't look at the AST or index if we have a macro result. + // (We'd just return declarations referenced from the macro's + // expansion.) + return {*std::move(Macro)}; + + TouchedIdentifier = &Tok; + break; + } + + if (Tok.kind() == tok::kw_auto || Tok.kind() == tok::kw_decltype) { + // go-to-definition on auto should find the definition of the deduced + // type, if possible + if (auto Deduced = getDeducedType(AST.getASTContext(), Tok.location())) { + auto LocSym = locateSymbolForType(AST, *Deduced); + if (!LocSym.empty()) + return LocSym; + } + } + } ASTNodeKind NodeKind; auto ASTResults = locateASTReferent(*CurLoc, TouchedIdentifier, AST, @@ -570,13 +811,22 @@ // Is the same word nearby a real identifier that might refer to something? if (const syntax::Token *NearbyIdent = findNearbyIdentifier(*Word, AST.getTokens())) { - if (auto Macro = locateMacroReferent(*NearbyIdent, AST, *MainFilePath)) + if (auto Macro = locateMacroReferent(*NearbyIdent, AST, *MainFilePath)) { + log("Found macro definition heuristically using nearby identifier {0}", + Word->Text); return {*std::move(Macro)}; + } ASTResults = locateASTReferent(NearbyIdent->location(), NearbyIdent, AST, *MainFilePath, Index, /*NodeKind=*/nullptr); - if (!ASTResults.empty()) + if (!ASTResults.empty()) { + log("Found definition heuristically using nearby identifier {0}", + NearbyIdent->text(SM)); return ASTResults; + } else { + vlog("No definition found using nearby identifier {0} at {1}", + Word->Text, Word->Location.printToString(SM)); + } } // No nearby word, or it didn't refer to anything either. Try the index. auto TextualResults = @@ -629,6 +879,7 @@ struct Reference { syntax::Token SpelledTok; index::SymbolRoleSet Role; + SymbolID Target; Range range(const SourceManager &SM) const { return halfOpenToRange(SM, SpelledTok.range(SM).toCharRange(SM)); @@ -636,11 +887,8 @@ }; ReferenceFinder(const ParsedAST &AST, - const std::vector<const NamedDecl *> &TargetDecls) - : AST(AST) { - for (const NamedDecl *D : TargetDecls) - CanonicalTargets.insert(D->getCanonicalDecl()); - } + const llvm::DenseSet<SymbolID> &TargetIDs, bool PerToken) + : PerToken(PerToken), AST(AST), TargetIDs(TargetIDs) {} std::vector<Reference> take() && { llvm::sort(References, [](const Reference &L, const Reference &R) { @@ -665,26 +913,50 @@ llvm::ArrayRef<index::SymbolRelation> Relations, SourceLocation Loc, index::IndexDataConsumer::ASTNodeInfo ASTNode) override { - assert(D->isCanonicalDecl() && "expect D to be a canonical declaration"); const SourceManager &SM = AST.getSourceManager(); - if (!CanonicalTargets.count(D) || !isInsideMainFile(Loc, SM)) + if (!isInsideMainFile(Loc, SM)) + return true; + SymbolID ID = getSymbolID(D); + if (!TargetIDs.contains(ID)) return true; const auto &TB = AST.getTokens(); - Loc = SM.getFileLoc(Loc); - if (const auto *Tok = TB.spelledTokenAt(Loc)) - References.push_back({*Tok, Roles}); + + llvm::SmallVector<SourceLocation, 1> Locs; + if (PerToken) { + // Check whether this is one of the few constructs where the reference + // can be split over several tokens. + if (auto *OME = llvm::dyn_cast_or_null<ObjCMessageExpr>(ASTNode.OrigE)) { + OME->getSelectorLocs(Locs); + } else if (auto *OMD = + llvm::dyn_cast_or_null<ObjCMethodDecl>(ASTNode.OrigD)) { + OMD->getSelectorLocs(Locs); + } + // Sanity check: we expect the *first* token to match the reported loc. + // Otherwise, maybe it was e.g. some other kind of reference to a Decl. + if (!Locs.empty() && Locs.front() != Loc) + Locs.clear(); // First token doesn't match, assume our guess was wrong. + } + if (Locs.empty()) + Locs.push_back(Loc); + + for (SourceLocation L : Locs) { + L = SM.getFileLoc(L); + if (const auto *Tok = TB.spelledTokenAt(L)) + References.push_back({*Tok, Roles, ID}); + } return true; } private: - llvm::SmallSet<const Decl *, 4> CanonicalTargets; + bool PerToken; // If true, report 3 references for split ObjC selector names. std::vector<Reference> References; const ParsedAST &AST; + const llvm::DenseSet<SymbolID> &TargetIDs; }; std::vector<ReferenceFinder::Reference> -findRefs(const std::vector<const NamedDecl *> &Decls, ParsedAST &AST) { - ReferenceFinder RefFinder(AST, Decls); +findRefs(const llvm::DenseSet<SymbolID> &IDs, ParsedAST &AST, bool PerToken) { + ReferenceFinder RefFinder(AST, IDs, PerToken); index::IndexingOptions IndexOpts; IndexOpts.SystemSymbolFilter = index::IndexingOptions::SystemSymbolFilterKind::All; @@ -696,38 +968,364 @@ return std::move(RefFinder).take(); } +const Stmt *getFunctionBody(DynTypedNode N) { + if (const auto *FD = N.get<FunctionDecl>()) + return FD->getBody(); + if (const auto *FD = N.get<BlockDecl>()) + return FD->getBody(); + if (const auto *FD = N.get<LambdaExpr>()) + return FD->getBody(); + if (const auto *FD = N.get<ObjCMethodDecl>()) + return FD->getBody(); + return nullptr; +} + +const Stmt *getLoopBody(DynTypedNode N) { + if (const auto *LS = N.get<ForStmt>()) + return LS->getBody(); + if (const auto *LS = N.get<CXXForRangeStmt>()) + return LS->getBody(); + if (const auto *LS = N.get<WhileStmt>()) + return LS->getBody(); + if (const auto *LS = N.get<DoStmt>()) + return LS->getBody(); + return nullptr; +} + +// 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> { + // Types of control-flow statements we might highlight. + enum Target { + Break = 1, + Continue = 2, + Return = 4, + Case = 8, + Throw = 16, + Goto = 32, + All = Break | Continue | Return | Case | Throw | Goto, + }; + int Ignore = 0; // bitmask of Target - what are we *not* highlighting? + SourceRange Bounds; // Half-open, restricts reported targets. + std::vector<SourceLocation> &Result; + const SourceManager &SM; + + // Masks out targets for a traversal into D. + // Traverses the subtree using Delegate() if any targets remain. + template <typename Func> + bool filterAndTraverse(DynTypedNode D, const Func &Delegate) { + auto RestoreIgnore = llvm::make_scope_exit( + [OldIgnore(Ignore), this] { Ignore = OldIgnore; }); + if (getFunctionBody(D)) + Ignore = All; + else if (getLoopBody(D)) + Ignore |= Continue | Break; + else if (D.get<SwitchStmt>()) + Ignore |= Break | Case; + // Prune tree if we're not looking for anything. + return (Ignore == All) ? true : Delegate(); + } + + void found(Target T, SourceLocation Loc) { + if (T & Ignore) + return; + if (SM.isBeforeInTranslationUnit(Loc, Bounds.getBegin()) || + SM.isBeforeInTranslationUnit(Bounds.getEnd(), Loc)) + return; + Result.push_back(Loc); + } + +public: + FindControlFlow(SourceRange Bounds, std::vector<SourceLocation> &Result, + const SourceManager &SM) + : Bounds(Bounds), Result(Result), SM(SM) {} + + // When traversing function or loops, limit targets to those that still + // refer to the original root. + bool TraverseDecl(Decl *D) { + return !D || filterAndTraverse(DynTypedNode::create(*D), [&] { + return RecursiveASTVisitor::TraverseDecl(D); + }); + } + bool TraverseStmt(Stmt *S) { + return !S || filterAndTraverse(DynTypedNode::create(*S), [&] { + return RecursiveASTVisitor::TraverseStmt(S); + }); + } + + // Add leaves that we found and want. + bool VisitReturnStmt(ReturnStmt *R) { + found(Return, R->getReturnLoc()); + return true; + } + bool VisitBreakStmt(BreakStmt *B) { + found(Break, B->getBreakLoc()); + return true; + } + bool VisitContinueStmt(ContinueStmt *C) { + found(Continue, C->getContinueLoc()); + return true; + } + bool VisitSwitchCase(SwitchCase *C) { + found(Case, C->getKeywordLoc()); + return true; + } + bool VisitCXXThrowExpr(CXXThrowExpr *T) { + found(Throw, T->getThrowLoc()); + return true; + } + bool VisitGotoStmt(GotoStmt *G) { + // Goto is interesting if its target is outside the root. + if (const auto *LD = G->getLabel()) { + if (SM.isBeforeInTranslationUnit(LD->getLocation(), Bounds.getBegin()) || + SM.isBeforeInTranslationUnit(Bounds.getEnd(), LD->getLocation())) + found(Goto, G->getGotoLoc()); + } + return true; + } +}; + +// 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) { + // Cases are not stored in order, sort them first. + // (In fact they seem to be stored in reverse order, don't rely on this) + std::vector<const SwitchCase *> Cases; + for (const SwitchCase *Case = Switch.getSwitchCaseList(); Case; + Case = Case->getNextSwitchCase()) + Cases.push_back(Case); + llvm::sort(Cases, [&](const SwitchCase *L, const SwitchCase *R) { + return SM.isBeforeInTranslationUnit(L->getKeywordLoc(), R->getKeywordLoc()); + }); + + // Find the first case after the target location, the end of our range. + auto CaseAfter = llvm::partition_point(Cases, [&](const SwitchCase *C) { + return !SM.isBeforeInTranslationUnit(Loc, C->getKeywordLoc()); + }); + SourceLocation End = CaseAfter == Cases.end() ? Switch.getEndLoc() + : (*CaseAfter)->getKeywordLoc(); + + // Our target can be before the first case - cases are optional! + if (CaseAfter == Cases.begin()) + return SourceRange(Switch.getBeginLoc(), End); + // The start of our range is usually the previous case, but... + auto CaseBefore = std::prev(CaseAfter); + // ... rewind CaseBefore to the first in a `case A: case B: ...` sequence. + while (CaseBefore != Cases.begin() && + (*std::prev(CaseBefore))->getSubStmt() == *CaseBefore) + --CaseBefore; + return SourceRange((*CaseBefore)->getKeywordLoc(), End); +} + +// 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) { + const SourceManager &SM = + N.getDeclContext().getParentASTContext().getSourceManager(); + std::vector<SourceLocation> Result; + + // First, check if we're at a node that can resolve to a root. + enum class Cur { None, Break, Continue, Return, Case, Throw } Cursor; + if (N.ASTNode.get<BreakStmt>()) { + Cursor = Cur::Break; + } else if (N.ASTNode.get<ContinueStmt>()) { + Cursor = Cur::Continue; + } else if (N.ASTNode.get<ReturnStmt>()) { + Cursor = Cur::Return; + } else if (N.ASTNode.get<CXXThrowExpr>()) { + Cursor = Cur::Throw; + } else if (N.ASTNode.get<SwitchCase>()) { + Cursor = Cur::Case; + } else if (const GotoStmt *GS = N.ASTNode.get<GotoStmt>()) { + // We don't know what root to associate with, but highlight the goto/label. + Result.push_back(GS->getGotoLoc()); + if (const auto *LD = GS->getLabel()) + Result.push_back(LD->getLocation()); + Cursor = Cur::None; + } else { + Cursor = Cur::None; + } + + const Stmt *Root = nullptr; // Loop or function body to traverse. + SourceRange Bounds; + // Look up the tree for a root (or just at this node if we didn't find a leaf) + for (const auto *P = &N; P; P = P->Parent) { + // return associates with enclosing function + if (const Stmt *FunctionBody = getFunctionBody(P->ASTNode)) { + if (Cursor == Cur::Return || Cursor == Cur::Throw) { + Root = FunctionBody; + } + break; // other leaves don't cross functions. + } + // break/continue associate with enclosing loop. + if (const Stmt *LoopBody = getLoopBody(P->ASTNode)) { + if (Cursor == Cur::None || Cursor == Cur::Break || + Cursor == Cur::Continue) { + Root = LoopBody; + // Highlight the loop keyword itself. + // FIXME: for do-while, this only covers the `do`.. + Result.push_back(P->ASTNode.getSourceRange().getBegin()); + break; + } + } + // For switches, users think of case statements as control flow blocks. + // We highlight only occurrences surrounded by the same case. + // We don't detect fallthrough (other than 'case X, case Y'). + if (const auto *SS = P->ASTNode.get<SwitchStmt>()) { + if (Cursor == Cur::Break || Cursor == Cur::Case) { + Result.push_back(SS->getSwitchLoc()); // Highlight the switch. + Root = SS->getBody(); + // Limit to enclosing case, if there is one. + Bounds = findCaseBounds(*SS, N.ASTNode.getSourceRange().getBegin(), SM); + break; + } + } + // If we didn't start at some interesting node, we're done. + if (Cursor == Cur::None) + break; + } + if (Root) { + if (!Bounds.isValid()) + Bounds = Root->getSourceRange(); + FindControlFlow(Bounds, Result, SM).TraverseStmt(const_cast<Stmt *>(Root)); + } + return Result; +} + +DocumentHighlight toHighlight(const ReferenceFinder::Reference &Ref, + const SourceManager &SM) { + DocumentHighlight DH; + DH.range = Ref.range(SM); + if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Write)) + DH.kind = DocumentHighlightKind::Write; + else if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Read)) + DH.kind = DocumentHighlightKind::Read; + else + DH.kind = DocumentHighlightKind::Text; + return DH; +} + +llvm::Optional<DocumentHighlight> toHighlight(SourceLocation Loc, + const syntax::TokenBuffer &TB) { + Loc = TB.sourceManager().getFileLoc(Loc); + if (const auto *Tok = TB.spelledTokenAt(Loc)) { + DocumentHighlight Result; + Result.range = halfOpenToRange( + TB.sourceManager(), + CharSourceRange::getCharRange(Tok->location(), Tok->endLocation())); + return Result; + } + return llvm::None; +} + } // namespace std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST, Position Pos) { const SourceManager &SM = AST.getSourceManager(); // FIXME: show references to macro within file? - DeclRelationSet Relations = - DeclRelation::TemplatePattern | DeclRelation::Alias; auto CurLoc = sourceLocationInMainFile(SM, Pos); if (!CurLoc) { llvm::consumeError(CurLoc.takeError()); return {}; } - auto References = findRefs(getDeclAtPosition(AST, *CurLoc, Relations), AST); + std::vector<DocumentHighlight> Result; + auto TryTree = [&](SelectionTree ST) { + if (const SelectionTree::Node *N = ST.commonAncestor()) { + DeclRelationSet Relations = + DeclRelation::TemplatePattern | DeclRelation::Alias; + auto Decls = + targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver()); + if (!Decls.empty()) { + // FIXME: we may get multiple DocumentHighlights with the same location + // and different kinds, deduplicate them. + llvm::DenseSet<SymbolID> Targets; + for (const NamedDecl *ND : Decls) + if (auto ID = getSymbolID(ND)) + Targets.insert(ID); + for (const auto &Ref : findRefs(Targets, AST, /*PerToken=*/true)) + Result.push_back(toHighlight(Ref, SM)); + return true; + } + auto ControlFlow = relatedControlFlow(*N); + if (!ControlFlow.empty()) { + for (SourceLocation Loc : ControlFlow) + if (auto Highlight = toHighlight(Loc, AST.getTokens())) + Result.push_back(std::move(*Highlight)); + return true; + } + } + return false; + }; - // FIXME: we may get multiple DocumentHighlights with the same location and - // different kinds, deduplicate them. - std::vector<DocumentHighlight> Result; - for (const auto &Ref : References) { - DocumentHighlight DH; - DH.range = Ref.range(SM); - if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Write)) - DH.kind = DocumentHighlightKind::Write; - else if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Read)) - DH.kind = DocumentHighlightKind::Read; - else - DH.kind = DocumentHighlightKind::Text; - Result.push_back(std::move(DH)); - } + unsigned Offset = + AST.getSourceManager().getDecomposedSpellingLoc(*CurLoc).second; + SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset, + Offset, TryTree); return Result; } +std::vector<LocatedSymbol> findImplementations(ParsedAST &AST, Position Pos, + const SymbolIndex *Index) { + // We rely on index to find the implementations in subclasses. + // FIXME: Index can be stale, so we may loose some latest results from the + // main file. + if (!Index) + return {}; + const SourceManager &SM = AST.getSourceManager(); + auto MainFilePath = + getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM); + if (!MainFilePath) { + elog("Failed to get a path for the main file, so no implementations."); + return {}; + } + auto CurLoc = sourceLocationInMainFile(SM, Pos); + if (!CurLoc) { + elog("Failed to convert position to source location: {0}", + CurLoc.takeError()); + return {}; + } + DeclRelationSet Relations = + DeclRelation::TemplatePattern | DeclRelation::Alias; + llvm::DenseSet<SymbolID> IDs; + RelationKind QueryKind; + for (const NamedDecl *ND : getDeclAtPosition(AST, *CurLoc, Relations)) { + if (const auto *CXXMD = llvm::dyn_cast<CXXMethodDecl>(ND)) { + if (CXXMD->isVirtual()) { + IDs.insert(getSymbolID(ND)); + QueryKind = RelationKind::OverriddenBy; + } + } else if (const auto *RD = dyn_cast<CXXRecordDecl>(ND)) { + IDs.insert(getSymbolID(RD)); + QueryKind = RelationKind::BaseOf; + } + } + return findImplementors(std::move(IDs), QueryKind, Index, *MainFilePath); +} + +namespace { +// Recursively finds all the overridden methods of `CMD` in complete type +// hierarchy. +void getOverriddenMethods(const CXXMethodDecl *CMD, + llvm::DenseSet<SymbolID> &OverriddenMethods) { + if (!CMD) + return; + for (const CXXMethodDecl *Base : CMD->overridden_methods()) { + if (auto ID = getSymbolID(Base)) + OverriddenMethods.insert(ID); + getOverriddenMethods(Base, OverriddenMethods); + } +} +} // namespace + ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit, const SymbolIndex *Index) { if (!Limit) @@ -746,40 +1344,66 @@ llvm::consumeError(CurLoc.takeError()); return {}; } + + llvm::DenseSet<SymbolID> IDs, OverriddenMethods; + + const auto *IdentifierAtCursor = + syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens()); llvm::Optional<DefinedMacro> Macro; - if (const auto *IdentifierAtCursor = - syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens())) { + if (IdentifierAtCursor) Macro = locateMacroAt(*IdentifierAtCursor, AST.getPreprocessor()); - } - - RefsRequest Req; if (Macro) { // Handle references to macro. if (auto MacroSID = getSymbolID(Macro->Name, Macro->Info, SM)) { // Collect macro references from main file. const auto &IDToRefs = AST.getMacros().MacroRefs; - auto Refs = IDToRefs.find(*MacroSID); + auto Refs = IDToRefs.find(MacroSID); if (Refs != IDToRefs.end()) { - for (const auto Ref : Refs->second) { - Location Result; - Result.range = Ref; - Result.uri = URIMainFile; + for (const auto &Ref : Refs->second) { + ReferencesResult::Reference Result; + Result.Loc.range = Ref.Rng; + Result.Loc.uri = URIMainFile; + if (Ref.IsDefinition) { + Result.Attributes |= ReferencesResult::Declaration; + Result.Attributes |= ReferencesResult::Definition; + } Results.References.push_back(std::move(Result)); } } - Req.IDs.insert(*MacroSID); + IDs.insert(MacroSID); } } else { // Handle references to Decls. - // We also show references to the targets of using-decls, so we include - // DeclRelation::Underlying. - DeclRelationSet Relations = DeclRelation::TemplatePattern | - DeclRelation::Alias | DeclRelation::Underlying; - auto Decls = getDeclAtPosition(AST, *CurLoc, Relations); + DeclRelationSet Relations = + DeclRelation::TemplatePattern | DeclRelation::Alias; + std::vector<const NamedDecl *> Decls = + getDeclAtPosition(AST, *CurLoc, Relations); + llvm::DenseSet<SymbolID> Targets; + for (const NamedDecl *D : Decls) + if (auto ID = getSymbolID(D)) + Targets.insert(ID); + + RelationsRequest OverriddenBy; + if (Index) { + OverriddenBy.Predicate = RelationKind::OverriddenBy; + for (const NamedDecl *ND : Decls) { + // Special case: For virtual methods, report decl/def of overrides and + // references to all overridden methods in complete type hierarchy. + if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(ND)) { + if (CMD->isVirtual()) + if (IdentifierAtCursor && SM.getSpellingLoc(CMD->getLocation()) == + IdentifierAtCursor->location()) { + if (auto ID = getSymbolID(CMD)) + OverriddenBy.Subjects.insert(ID); + getOverriddenMethods(CMD, OverriddenMethods); + } + } + } + } // We traverse the AST to find references in the main file. - auto MainFileRefs = findRefs(Decls, AST); + auto MainFileRefs = findRefs(Targets, AST, /*PerToken=*/false); // We may get multiple refs with the same location and different Roles, as // cross-reference is only interested in locations, we deduplicate them // by the location to avoid emitting duplicated locations. @@ -791,11 +1415,40 @@ }), MainFileRefs.end()); for (const auto &Ref : MainFileRefs) { - Location Result; - Result.range = Ref.range(SM); - Result.uri = URIMainFile; + ReferencesResult::Reference Result; + Result.Loc.range = Ref.range(SM); + Result.Loc.uri = URIMainFile; + if (Ref.Role & static_cast<unsigned>(index::SymbolRole::Declaration)) + Result.Attributes |= ReferencesResult::Declaration; + // clang-index doesn't report definitions as declarations, but they are. + if (Ref.Role & static_cast<unsigned>(index::SymbolRole::Definition)) + Result.Attributes |= + ReferencesResult::Definition | ReferencesResult::Declaration; Results.References.push_back(std::move(Result)); } + // Add decl/def of overridding methods. + if (Index && Results.References.size() <= Limit && + !OverriddenBy.Subjects.empty()) + Index->relations( + OverriddenBy, [&](const SymbolID &Subject, const Symbol &Object) { + if (auto LSPLoc = + toLSPLocation(Object.CanonicalDeclaration, *MainFilePath)) { + ReferencesResult::Reference Result; + Result.Loc = std::move(*LSPLoc); + Result.Attributes = + ReferencesResult::Declaration | ReferencesResult::Override; + Results.References.push_back(std::move(Result)); + } + if (auto LSPLoc = toLSPLocation(Object.Definition, *MainFilePath)) { + ReferencesResult::Reference Result; + Result.Loc = std::move(*LSPLoc); + Result.Attributes = ReferencesResult::Declaration | + ReferencesResult::Definition | + ReferencesResult::Override; + Results.References.push_back(std::move(Result)); + } + }); + if (Index && Results.References.size() <= Limit) { for (const Decl *D : Decls) { // Not all symbols can be referenced from outside (e.g. @@ -805,25 +1458,47 @@ if (D->getParentFunctionOrMethod()) continue; if (auto ID = getSymbolID(D)) - Req.IDs.insert(*ID); + IDs.insert(ID); } } } // Now query the index for references from other files. - if (!Req.IDs.empty() && Index && Results.References.size() <= Limit) { + auto QueryIndex = [&](llvm::DenseSet<SymbolID> IDs, bool AllowAttributes, + bool AllowMainFileSymbols) { + RefsRequest Req; + Req.IDs = std::move(IDs); Req.Limit = Limit; + if (Req.IDs.empty() || !Index || Results.References.size() > Limit) + return; Results.HasMore |= Index->refs(Req, [&](const Ref &R) { // No need to continue process if we reach the limit. if (Results.References.size() > Limit) return; auto LSPLoc = toLSPLocation(R.Location, *MainFilePath); // Avoid indexed results for the main file - the AST is authoritative. - if (!LSPLoc || LSPLoc->uri.file() == *MainFilePath) + if (!LSPLoc || + (!AllowMainFileSymbols && LSPLoc->uri.file() == *MainFilePath)) return; - - Results.References.push_back(std::move(*LSPLoc)); + ReferencesResult::Reference Result; + Result.Loc = std::move(*LSPLoc); + if (AllowAttributes) { + if ((R.Kind & RefKind::Declaration) == RefKind::Declaration) + Result.Attributes |= ReferencesResult::Declaration; + // FIXME: our index should definitely store def | decl separately! + if ((R.Kind & RefKind::Definition) == RefKind::Definition) + Result.Attributes |= + ReferencesResult::Declaration | ReferencesResult::Definition; + } + Results.References.push_back(std::move(Result)); }); - } + }; + QueryIndex(std::move(IDs), /*AllowAttributes=*/true, + /*AllowMainFileSymbols=*/false); + // For a virtual method: Occurrences of BaseMethod should be treated as refs + // and not as decl/def. Allow symbols from main file since AST does not report + // these. + QueryIndex(std::move(OverriddenMethods), /*AllowAttributes=*/false, + /*AllowMainFileSymbols=*/true); if (Results.References.size() > Limit) { Results.HasMore = true; Results.References.resize(Limit); @@ -892,75 +1567,122 @@ return OS; } -// FIXME(nridge): Reduce duplication between this function and declToSym(). -static llvm::Optional<TypeHierarchyItem> -declToTypeHierarchyItem(ASTContext &Ctx, const NamedDecl &ND, - const syntax::TokenBuffer &TB) { +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, + const ReferencesResult::Reference &R) { + OS << R.Loc; + if (R.Attributes & ReferencesResult::Declaration) + OS << " [decl]"; + if (R.Attributes & ReferencesResult::Definition) + OS << " [def]"; + if (R.Attributes & ReferencesResult::Override) + OS << " [override]"; + return OS; +} + +template <typename HierarchyItem> +static llvm::Optional<HierarchyItem> declToHierarchyItem(const NamedDecl &ND) { + ASTContext &Ctx = ND.getASTContext(); auto &SM = Ctx.getSourceManager(); SourceLocation NameLoc = nameLocation(ND, Ctx.getSourceManager()); + SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc())); + SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc())); + const auto DeclRange = + toHalfOpenFileRange(SM, Ctx.getLangOpts(), {BeginLoc, EndLoc}); + if (!DeclRange) + return llvm::None; auto FilePath = getCanonicalPath(SM.getFileEntryForID(SM.getFileID(NameLoc)), SM); auto TUPath = getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM); if (!FilePath || !TUPath) return llvm::None; // Not useful without a uri. - auto DeclToks = TB.spelledForExpanded(TB.expandedTokens(ND.getSourceRange())); - if (!DeclToks || DeclToks->empty()) - return llvm::None; - - auto NameToks = TB.spelledForExpanded(TB.expandedTokens(NameLoc)); - if (!NameToks || NameToks->empty()) - return llvm::None; + Position NameBegin = sourceLocToPosition(SM, NameLoc); + Position NameEnd = sourceLocToPosition( + SM, Lexer::getLocForEndOfToken(NameLoc, 0, SM, Ctx.getLangOpts())); index::SymbolInfo SymInfo = index::getSymbolInfo(&ND); - // FIXME: this is not classifying constructors, destructors and operators - // correctly (they're all "methods"). + // FIXME: This is not classifying constructors, destructors and operators + // correctly. SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind); - TypeHierarchyItem THI; - THI.name = printName(Ctx, ND); - THI.kind = SK; - THI.deprecated = ND.isDeprecated(); - THI.range = halfOpenToRange( - SM, syntax::Token::range(SM, DeclToks->front(), DeclToks->back()) - .toCharRange(SM)); - THI.selectionRange = halfOpenToRange( - SM, syntax::Token::range(SM, NameToks->front(), NameToks->back()) - .toCharRange(SM)); - if (!THI.range.contains(THI.selectionRange)) { + HierarchyItem HI; + HI.name = printName(Ctx, ND); + HI.kind = SK; + HI.range = Range{sourceLocToPosition(SM, DeclRange->getBegin()), + sourceLocToPosition(SM, DeclRange->getEnd())}; + HI.selectionRange = Range{NameBegin, NameEnd}; + if (!HI.range.contains(HI.selectionRange)) { // 'selectionRange' must be contained in 'range', so in cases where clang // reports unrelated ranges we need to reconcile somehow. - THI.range = THI.selectionRange; + HI.range = HI.selectionRange; } - THI.uri = URIForFile::canonicalize(*FilePath, *TUPath); + HI.uri = URIForFile::canonicalize(*FilePath, *TUPath); - return THI; + // Compute the SymbolID and store it in the 'data' field. + // This allows typeHierarchy/resolve to be used to + // resolve children of items returned in a previous request + // for parents. + if (auto ID = getSymbolID(&ND)) + HI.data = ID.str(); + + return HI; } -static Optional<TypeHierarchyItem> -symbolToTypeHierarchyItem(const Symbol &S, const SymbolIndex *Index, - PathRef TUPath) { +static llvm::Optional<TypeHierarchyItem> +declToTypeHierarchyItem(const NamedDecl &ND) { + auto Result = declToHierarchyItem<TypeHierarchyItem>(ND); + if (Result) + Result->deprecated = ND.isDeprecated(); + return Result; +} + +static llvm::Optional<CallHierarchyItem> +declToCallHierarchyItem(const NamedDecl &ND) { + auto Result = declToHierarchyItem<CallHierarchyItem>(ND); + if (Result && ND.isDeprecated()) + Result->tags.push_back(SymbolTag::Deprecated); + return Result; +} + +template <typename HierarchyItem> +static llvm::Optional<HierarchyItem> symbolToHierarchyItem(const Symbol &S, + PathRef TUPath) { auto Loc = symbolToLocation(S, TUPath); if (!Loc) { - log("Type hierarchy: {0}", Loc.takeError()); + elog("Failed to convert symbol to hierarchy item: {0}", Loc.takeError()); return llvm::None; } - TypeHierarchyItem THI; - THI.name = std::string(S.Name); - THI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind); - THI.deprecated = (S.Flags & Symbol::Deprecated); - THI.selectionRange = Loc->range; + HierarchyItem HI; + HI.name = std::string(S.Name); + HI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind); + HI.selectionRange = Loc->range; // FIXME: Populate 'range' correctly // (https://github.com/clangd/clangd/issues/59). - THI.range = THI.selectionRange; - THI.uri = Loc->uri; + HI.range = HI.selectionRange; + HI.uri = Loc->uri; // Store the SymbolID in the 'data' field. The client will - // send this back in typeHierarchy/resolve, allowing us to - // continue resolving additional levels of the type hierarchy. - THI.data = S.ID.str(); + // send this back in requests to resolve additional levels + // of the hierarchy. + HI.data = S.ID.str(); + + return HI; +} - return std::move(THI); +static llvm::Optional<TypeHierarchyItem> +symbolToTypeHierarchyItem(const Symbol &S, PathRef TUPath) { + auto Result = symbolToHierarchyItem<TypeHierarchyItem>(S, TUPath); + if (Result) + Result->deprecated = (S.Flags & Symbol::Deprecated); + return Result; +} + +static llvm::Optional<CallHierarchyItem> +symbolToCallHierarchyItem(const Symbol &S, PathRef TUPath) { + auto Result = symbolToHierarchyItem<CallHierarchyItem>(S, TUPath); + if (Result && (S.Flags & Symbol::Deprecated)) + Result->tags.push_back(SymbolTag::Deprecated); + return Result; } static void fillSubTypes(const SymbolID &ID, @@ -971,7 +1693,7 @@ Req.Predicate = RelationKind::BaseOf; Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) { if (Optional<TypeHierarchyItem> ChildSym = - symbolToTypeHierarchyItem(Object, Index, TUPath)) { + symbolToTypeHierarchyItem(Object, TUPath)) { if (Levels > 1) { ChildSym->children.emplace(); fillSubTypes(Object.ID, *ChildSym->children, Index, Levels - 1, TUPath); @@ -985,8 +1707,7 @@ static void fillSuperTypes(const CXXRecordDecl &CXXRD, ASTContext &ASTCtx, std::vector<TypeHierarchyItem> &SuperTypes, - RecursionProtectionSet &RPSet, - const syntax::TokenBuffer &TB) { + RecursionProtectionSet &RPSet) { // typeParents() will replace dependent template specializations // with their class template, so to avoid infinite recursion for // certain types of hierarchies, keep the templates encountered @@ -1001,9 +1722,9 @@ for (const CXXRecordDecl *ParentDecl : typeParents(&CXXRD)) { if (Optional<TypeHierarchyItem> ParentSym = - declToTypeHierarchyItem(ASTCtx, *ParentDecl, TB)) { + declToTypeHierarchyItem(*ParentDecl)) { ParentSym->parents.emplace(); - fillSuperTypes(*ParentDecl, ASTCtx, *ParentSym->parents, RPSet, TB); + fillSuperTypes(*ParentDecl, ASTCtx, *ParentSym->parents, RPSet); SuperTypes.emplace_back(std::move(*ParentSym)); } } @@ -1015,7 +1736,7 @@ const CXXRecordDecl *findRecordTypeAt(ParsedAST &AST, Position Pos) { auto RecordFromNode = - [](const SelectionTree::Node *N) -> const CXXRecordDecl * { + [&AST](const SelectionTree::Node *N) -> const CXXRecordDecl * { if (!N) return nullptr; @@ -1023,7 +1744,8 @@ // instantiations and template patterns, and prefer the former if available // (generally, one will be available for non-dependent specializations of a // class template). - auto Decls = explicitReferenceTargets(N->ASTNode, DeclRelation::Underlying); + auto Decls = explicitReferenceTargets(N->ASTNode, DeclRelation::Underlying, + AST.getHeuristicResolver()); if (Decls.empty()) return nullptr; @@ -1071,6 +1793,10 @@ CXXRD = CTSD->getSpecializedTemplate()->getTemplatedDecl(); } + // Can't query bases without a definition. + if (!CXXRD->hasDefinition()) + return Result; + for (auto Base : CXXRD->bases()) { const CXXRecordDecl *ParentDecl = nullptr; @@ -1106,33 +1832,40 @@ if (!CXXRD) return llvm::None; - Optional<TypeHierarchyItem> Result = - declToTypeHierarchyItem(AST.getASTContext(), *CXXRD, AST.getTokens()); + bool WantParents = Direction == TypeHierarchyDirection::Parents || + Direction == TypeHierarchyDirection::Both; + bool WantChildren = Direction == TypeHierarchyDirection::Children || + Direction == TypeHierarchyDirection::Both; + + // If we're looking for children, we're doing the lookup in the index. + // The index does not store relationships between implicit + // specializations, so if we have one, use the template pattern instead. + // Note that this needs to be done before the declToTypeHierarchyItem(), + // otherwise the type hierarchy item would misleadingly contain the + // specialization parameters, while the children would involve classes + // that derive from other specializations of the template. + if (WantChildren) { + if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD)) + CXXRD = CTSD->getTemplateInstantiationPattern(); + } + + Optional<TypeHierarchyItem> Result = declToTypeHierarchyItem(*CXXRD); if (!Result) return Result; - if (Direction == TypeHierarchyDirection::Parents || - Direction == TypeHierarchyDirection::Both) { + if (WantParents) { Result->parents.emplace(); RecursionProtectionSet RPSet; - fillSuperTypes(*CXXRD, AST.getASTContext(), *Result->parents, RPSet, - AST.getTokens()); + fillSuperTypes(*CXXRD, AST.getASTContext(), *Result->parents, RPSet); } - if ((Direction == TypeHierarchyDirection::Children || - Direction == TypeHierarchyDirection::Both) && - ResolveLevels > 0) { + if (WantChildren && ResolveLevels > 0) { Result->children.emplace(); if (Index) { - // The index does not store relationships between implicit - // specializations, so if we have one, use the template pattern instead. - if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD)) - CXXRD = CTSD->getTemplateInstantiationPattern(); - - if (Optional<SymbolID> ID = getSymbolID(CXXRD)) - fillSubTypes(*ID, *Result->children, Index, ResolveLevels, TUPath); + if (auto ID = getSymbolID(CXXRD)) + fillSubTypes(ID, *Result->children, Index, ResolveLevels, TUPath); } } @@ -1158,19 +1891,100 @@ } } +std::vector<CallHierarchyItem> +prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath) { + std::vector<CallHierarchyItem> Result; + const auto &SM = AST.getSourceManager(); + auto Loc = sourceLocationInMainFile(SM, Pos); + if (!Loc) { + elog("prepareCallHierarchy failed to convert position to source location: " + "{0}", + Loc.takeError()); + return Result; + } + for (const NamedDecl *Decl : getDeclAtPosition(AST, *Loc, {})) { + if (!Decl->isFunctionOrFunctionTemplate()) + continue; + if (auto CHI = declToCallHierarchyItem(*Decl)) + Result.emplace_back(std::move(*CHI)); + } + return Result; +} + +std::vector<CallHierarchyIncomingCall> +incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) { + std::vector<CallHierarchyIncomingCall> Results; + if (!Index || Item.data.empty()) + return Results; + auto ID = SymbolID::fromStr(Item.data); + if (!ID) { + elog("incomingCalls failed to find symbol: {0}", ID.takeError()); + return Results; + } + // In this function, we find incoming calls based on the index only. + // In principle, the AST could have more up-to-date information about + // occurrences within the current file. However, going from a SymbolID + // to an AST node isn't cheap, particularly when the declaration isn't + // in the main file. + // FIXME: Consider also using AST information when feasible. + RefsRequest Request; + Request.IDs.insert(*ID); + // We could restrict more specifically to calls by introducing a new RefKind, + // but non-call references (such as address-of-function) can still be + // interesting as they can indicate indirect calls. + Request.Filter = RefKind::Reference; + // Initially store the ranges in a map keyed by SymbolID of the caller. + // This allows us to group different calls with the same caller + // into the same CallHierarchyIncomingCall. + llvm::DenseMap<SymbolID, std::vector<Range>> CallsIn; + // We can populate the ranges based on a refs request only. As we do so, we + // also accumulate the container IDs into a lookup request. + LookupRequest ContainerLookup; + Index->refs(Request, [&](const Ref &R) { + auto Loc = indexToLSPLocation(R.Location, Item.uri.file()); + if (!Loc) { + elog("incomingCalls failed to convert location: {0}", Loc.takeError()); + return; + } + auto It = CallsIn.try_emplace(R.Container, std::vector<Range>{}).first; + It->second.push_back(Loc->range); + + ContainerLookup.IDs.insert(R.Container); + }); + // Perform the lookup request and combine its results with CallsIn to + // get complete CallHierarchyIncomingCall objects. + Index->lookup(ContainerLookup, [&](const Symbol &Caller) { + auto It = CallsIn.find(Caller.ID); + assert(It != CallsIn.end()); + if (auto CHI = symbolToCallHierarchyItem(Caller, Item.uri.file())) + Results.push_back( + CallHierarchyIncomingCall{std::move(*CHI), std::move(It->second)}); + }); + // Sort results by name of container. + llvm::sort(Results, [](const CallHierarchyIncomingCall &A, + const CallHierarchyIncomingCall &B) { + return A.from.name < B.from.name; + }); + return Results; +} + llvm::DenseSet<const Decl *> getNonLocalDeclRefs(ParsedAST &AST, const FunctionDecl *FD) { if (!FD->hasBody()) return {}; llvm::DenseSet<const Decl *> DeclRefs; - findExplicitReferences(FD, [&](ReferenceLoc Ref) { - for (const Decl *D : Ref.Targets) { - if (!index::isFunctionLocalSymbol(D) && !D->isTemplateParameter() && - !Ref.IsDecl) - DeclRefs.insert(D); - } - }); + findExplicitReferences( + FD, + [&](ReferenceLoc Ref) { + for (const Decl *D : Ref.Targets) { + if (!index::isFunctionLocalSymbol(D) && !D->isTemplateParameter() && + !Ref.IsDecl) + DeclRefs.insert(D); + } + }, + AST.getHeuristicResolver()); return DeclRefs; } + } // namespace clangd -} // namespace clang +} // namespace clang \ No newline at end of file