24 #include "clang/AST/ASTContext.h"
25 #include "clang/AST/ASTTypeTraits.h"
26 #include "clang/AST/Attr.h"
27 #include "clang/AST/Attrs.inc"
28 #include "clang/AST/Decl.h"
29 #include "clang/AST/DeclCXX.h"
30 #include "clang/AST/DeclObjC.h"
31 #include "clang/AST/DeclTemplate.h"
32 #include "clang/AST/DeclVisitor.h"
33 #include "clang/AST/ExprCXX.h"
34 #include "clang/AST/RecursiveASTVisitor.h"
35 #include "clang/AST/Stmt.h"
36 #include "clang/AST/StmtCXX.h"
37 #include "clang/AST/StmtVisitor.h"
38 #include "clang/AST/Type.h"
39 #include "clang/Basic/LLVM.h"
40 #include "clang/Basic/LangOptions.h"
41 #include "clang/Basic/SourceLocation.h"
42 #include "clang/Basic/SourceManager.h"
43 #include "clang/Basic/TokenKinds.h"
44 #include "clang/Index/IndexDataConsumer.h"
45 #include "clang/Index/IndexSymbol.h"
46 #include "clang/Index/IndexingAction.h"
47 #include "clang/Index/IndexingOptions.h"
48 #include "clang/Index/USRGeneration.h"
49 #include "clang/Tooling/Syntax/Tokens.h"
50 #include "llvm/ADT/ArrayRef.h"
51 #include "llvm/ADT/DenseMap.h"
52 #include "llvm/ADT/None.h"
53 #include "llvm/ADT/STLExtras.h"
54 #include "llvm/ADT/ScopeExit.h"
55 #include "llvm/ADT/SmallSet.h"
56 #include "llvm/ADT/SmallVector.h"
57 #include "llvm/ADT/StringRef.h"
58 #include "llvm/Support/Casting.h"
59 #include "llvm/Support/Error.h"
60 #include "llvm/Support/Path.h"
61 #include "llvm/Support/raw_ostream.h"
73 const NamedDecl *getDefinition(
const NamedDecl *
D) {
76 if (
const auto *TD = dyn_cast<TagDecl>(
D))
77 return TD->getDefinition();
78 if (
const auto *VD = dyn_cast<VarDecl>(
D))
79 return VD->getDefinition();
80 if (
const auto *FD = dyn_cast<FunctionDecl>(
D))
81 return FD->getDefinition();
82 if (
const auto *CTD = dyn_cast<ClassTemplateDecl>(
D))
83 if (
const auto *RD = CTD->getTemplatedDecl())
84 return RD->getDefinition();
101 if (
const auto *
ID = dyn_cast<ObjCInterfaceDecl>(
D))
102 return ID->getImplementation();
103 if (
const auto *CD = dyn_cast<ObjCCategoryDecl>(
D)) {
104 if (CD->IsClassExtension()) {
105 if (
const auto *
ID = CD->getClassInterface())
106 return ID->getImplementation();
109 return CD->getImplementation();
112 if (isa<ValueDecl>(
D) || isa<TemplateTypeParmDecl>(
D) ||
113 isa<TemplateTemplateParmDecl>(
D))
119 void logIfOverflow(
const SymbolLocation &
Loc) {
120 if (
Loc.Start.hasOverflow() ||
Loc.End.hasOverflow())
121 log(
"Possible overflow in symbol location: {0}",
Loc);
128 llvm::Optional<Location> toLSPLocation(
const SymbolLocation &
Loc,
129 llvm::StringRef TUPath) {
134 elog(
"Could not parse URI {0}: {1}",
Loc.FileURI, Uri.takeError());
139 elog(
"Could not resolve URI {0}: {1}",
Loc.FileURI, U.takeError());
144 LSPLoc.uri = std::move(*U);
145 LSPLoc.range.start.line =
Loc.Start.line();
146 LSPLoc.range.start.character =
Loc.Start.column();
147 LSPLoc.range.end.line =
Loc.End.line();
148 LSPLoc.range.end.character =
Loc.End.column();
153 SymbolLocation toIndexLocation(
const Location &
Loc, std::string &URIStorage) {
154 SymbolLocation SymLoc;
155 URIStorage =
Loc.uri.uri();
156 SymLoc.FileURI = URIStorage.c_str();
157 SymLoc.Start.setLine(
Loc.range.start.line);
158 SymLoc.Start.setColumn(
Loc.range.start.character);
159 SymLoc.End.setLine(
Loc.range.end.line);
160 SymLoc.End.setColumn(
Loc.range.end.character);
165 SymbolLocation getPreferredLocation(
const Location &ASTLoc,
166 const SymbolLocation &IdxLoc,
167 std::string &Scratch) {
170 Symbol ASTSym, IdxSym;
171 ASTSym.ID = IdxSym.ID =
SymbolID(
"mock_symbol_id");
172 ASTSym.CanonicalDeclaration = toIndexLocation(ASTLoc, Scratch);
173 IdxSym.CanonicalDeclaration = IdxLoc;
175 return Merged.CanonicalDeclaration;
178 std::vector<std::pair<const NamedDecl *, DeclRelationSet>>
179 getDeclAtPositionWithRelations(ParsedAST &AST, SourceLocation
Pos,
180 DeclRelationSet Relations,
181 ASTNodeKind *NodeKind =
nullptr) {
183 std::vector<std::pair<const NamedDecl *, DeclRelationSet>> Result;
184 auto ResultFromTree = [&](SelectionTree ST) {
185 if (
const SelectionTree::Node *N = ST.commonAncestor()) {
187 *NodeKind = N->ASTNode.getNodeKind();
192 if (N->ASTNode.get<Attr>() && N->Parent)
195 std::back_inserter(Result),
196 [&](
auto &
Entry) {
return !(
Entry.second & ~Relations); });
198 return !Result.empty();
205 std::vector<const NamedDecl *>
206 getDeclAtPosition(ParsedAST &AST, SourceLocation
Pos, DeclRelationSet Relations,
207 ASTNodeKind *NodeKind =
nullptr) {
208 std::vector<const NamedDecl *> Result;
210 getDeclAtPositionWithRelations(AST,
Pos, Relations, NodeKind))
211 Result.push_back(
Entry.first);
217 llvm::Optional<Location> makeLocation(
const ASTContext &AST, SourceLocation
Loc,
218 llvm::StringRef TUPath) {
220 const FileEntry *F = SM.getFileEntryForID(SM.getFileID(
Loc));
225 log(
"failed to get path!");
232 auto TokLen = Lexer::MeasureTokenLength(
Loc, SM, AST.
getLangOpts());
234 SM, CharSourceRange::getCharRange(
Loc,
Loc.getLocWithOffset(TokLen)));
239 llvm::Optional<LocatedSymbol> locateFileReferent(
const Position &
Pos,
241 llvm::StringRef MainFilePath) {
243 if (!Inc.Resolved.empty() && Inc.HashLine ==
Pos.line) {
245 File.Name = std::string(llvm::sys::path::filename(Inc.Resolved));
246 File.PreferredDeclaration = {
248 File.Definition = File.PreferredDeclaration;
258 llvm::Optional<LocatedSymbol>
259 locateMacroReferent(
const syntax::Token &TouchedIdentifier, ParsedAST &AST,
260 llvm::StringRef MainFilePath) {
265 Macro.Name = std::string(
M->Name);
288 const NamedDecl *getPreferredDecl(
const NamedDecl *
D) {
293 D = llvm::cast<NamedDecl>(
D->getCanonicalDecl());
296 if (
const auto *
ID = dyn_cast<ObjCInterfaceDecl>(
D))
297 if (
const auto *DefinitionID =
ID->getDefinition())
299 if (
const auto *PD = dyn_cast<ObjCProtocolDecl>(
D))
300 if (
const auto *DefinitionID = PD->getDefinition())
306 std::vector<LocatedSymbol> findImplementors(llvm::DenseSet<SymbolID> IDs,
308 const SymbolIndex *
Index,
309 llvm::StringRef MainFilePath) {
310 if (IDs.empty() || !
Index)
312 static constexpr trace::Metric FindImplementorsMetric(
316 FindImplementorsMetric.record(1,
"find-base");
319 FindImplementorsMetric.record(1,
"find-override");
323 RelationsRequest Req;
324 Req.Predicate = Predicate;
325 Req.Subjects = std::move(IDs);
326 std::vector<LocatedSymbol>
Results;
331 elog(
"Find overrides: {0}", DeclLoc.takeError());
336 Results.back().PreferredDeclaration = *DeclLoc;
339 elog(
"Failed to convert location: {0}", DefLoc.takeError());
342 Results.back().Definition = *DefLoc;
351 std::vector<LocatedSymbol>
352 locateASTReferent(SourceLocation CurLoc,
const syntax::Token *TouchedIdentifier,
353 ParsedAST &AST, llvm::StringRef MainFilePath,
354 const SymbolIndex *
Index, ASTNodeKind &NodeKind) {
357 std::vector<LocatedSymbol> Result;
359 llvm::DenseMap<SymbolID, size_t> ResultIndex;
361 static constexpr trace::Metric LocateASTReferentMetric(
363 auto AddResultDecl = [&](
const NamedDecl *
D) {
364 D = getPreferredDecl(
D);
370 Result.emplace_back();
372 Result.back().PreferredDeclaration = *
Loc;
374 if (
const NamedDecl *Def = getDefinition(
D))
375 Result.back().Definition = makeLocation(
380 ResultIndex[
ID] = Result.size() - 1;
384 DeclRelationSet Relations =
387 getDeclAtPositionWithRelations(AST, CurLoc, Relations, &NodeKind);
388 llvm::DenseSet<SymbolID> VirtualMethods;
389 for (
const auto &
E : Candidates) {
390 const NamedDecl *
D =
E.first;
391 if (
const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(
D)) {
396 if (TouchedIdentifier && SM.getSpellingLoc(CMD->getLocation()) ==
397 TouchedIdentifier->location()) {
399 LocateASTReferentMetric.record(1,
"method-to-override");
403 if (NodeKind.isSame(ASTNodeKind::getFromNodeKind<OverrideAttr>()) ||
404 NodeKind.isSame(ASTNodeKind::getFromNodeKind<FinalAttr>())) {
406 for (
const NamedDecl *ND : CMD->overridden_methods())
419 SM.isPointWithin(TouchedIdentifier ? TouchedIdentifier->location()
421 D->getBeginLoc(),
D->getEndLoc()))
426 if (
auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(
D)) {
427 if (TouchedIdentifier &&
428 D->getLocation() == TouchedIdentifier->location()) {
429 LocateASTReferentMetric.record(1,
"template-specialization-to-primary");
430 AddResultDecl(CTSD->getSpecializedTemplate());
441 if (
const auto *CD = dyn_cast<ObjCCategoryDecl>(
D))
442 if (
const auto *
ID = CD->getClassInterface())
443 if (TouchedIdentifier &&
444 (CD->getLocation() == TouchedIdentifier->location() ||
445 ID->getName() == TouchedIdentifier->text(SM))) {
446 LocateASTReferentMetric.record(1,
"objc-category-to-class");
450 LocateASTReferentMetric.record(1,
"regular");
456 if (
Index && !ResultIndex.empty()) {
457 LookupRequest QueryRequest;
458 for (
auto It : ResultIndex)
459 QueryRequest.IDs.insert(It.first);
461 Index->
lookup(QueryRequest, [&](
const Symbol &Sym) {
462 auto &R = Result[ResultIndex.lookup(Sym.ID)];
467 if (auto Loc = toLSPLocation(Sym.CanonicalDeclaration, MainFilePath))
468 R.PreferredDeclaration = *Loc;
472 if (auto Loc = toLSPLocation(
473 getPreferredLocation(*R.Definition, Sym.Definition, Scratch),
477 R.Definition = toLSPLocation(Sym.Definition, MainFilePath);
480 if (auto Loc = toLSPLocation(
481 getPreferredLocation(R.PreferredDeclaration,
482 Sym.CanonicalDeclaration, Scratch),
484 R.PreferredDeclaration = *Loc;
490 Index, MainFilePath);
491 Result.insert(Result.end(), Overrides.begin(), Overrides.end());
495 std::vector<LocatedSymbol> locateSymbolForType(
const ParsedAST &AST,
496 const QualType &Type) {
501 elog(
"Failed to get a path for the main file, so no symbol.");
507 auto Decls =
targetDecl(DynTypedNode::create(
Type.getNonReferenceType()),
513 std::vector<LocatedSymbol>
Results;
516 for (
const NamedDecl *
D : Decls) {
517 D = getPreferredDecl(
D);
527 if (
const NamedDecl *Def = getDefinition(
D))
529 makeLocation(ASTContext,
nameLocation(*Def, SM), *MainFilePath);
535 bool tokenSpelledAt(SourceLocation SpellingLoc,
const syntax::TokenBuffer &TB) {
536 auto ExpandedTokens = TB.expandedTokens(
537 TB.sourceManager().getMacroArgExpandedLocation(SpellingLoc));
538 return !ExpandedTokens.empty();
541 llvm::StringRef sourcePrefix(SourceLocation
Loc,
const SourceManager &SM) {
542 auto D = SM.getDecomposedLoc(
Loc);
544 llvm::StringRef Buf = SM.getBufferData(
D.first, &Invalid);
545 if (Invalid ||
D.second > Buf.size())
547 return Buf.substr(0,
D.second);
550 bool isDependentName(ASTNodeKind NodeKind) {
551 return NodeKind.isSame(ASTNodeKind::getFromNodeKind<OverloadExpr>()) ||
553 ASTNodeKind::getFromNodeKind<CXXDependentScopeMemberExpr>()) ||
555 ASTNodeKind::getFromNodeKind<DependentScopeDeclRefExpr>());
560 std::vector<LocatedSymbol>
563 ASTNodeKind NodeKind) {
568 if ((
Word.ExpandedToken && !isDependentName(NodeKind)) ||
573 if (
Word.PartOfSpelledToken &&
574 isStringLiteral(
Word.PartOfSpelledToken->kind()))
591 bool TooMany =
false;
592 using ScoredLocatedSymbol = std::pair<float, LocatedSymbol>;
593 std::vector<ScoredLocatedSymbol> ScoredResults;
604 if (Sym.
SymInfo.Kind == index::SymbolKind::Constructor)
610 log(
"locateSymbolNamedTextuallyAt: {0}", MaybeDeclLoc.takeError());
620 log(
"locateSymbolNamedTextuallyAt: {0}", MaybeDefLoc.takeError());
627 if (ScoredResults.size() >= 5) {
640 Relevance.
merge(Sym);
643 dlog(
"locateSymbolNamedTextuallyAt: {0}{1} = {2}\n{3}{4}\n", Sym.
Scope,
646 ScoredResults.push_back({
Score, std::move(Located)});
650 vlog(
"Heuristic index lookup for {0} returned too many candidates, ignored",
655 llvm::sort(ScoredResults,
656 [](
const ScoredLocatedSymbol &
A,
const ScoredLocatedSymbol &
B) {
657 return A.first >
B.first;
659 std::vector<LocatedSymbol>
Results;
660 for (
auto &Res : std::move(ScoredResults))
661 Results.push_back(std::move(Res.second));
663 vlog(
"No heuristic index definition for {0}",
Word.Text);
665 log(
"Found definition heuristically in index for {0}",
Word.Text);
670 const syntax::TokenBuffer &TB) {
673 if (
Word.ExpandedToken)
677 if (
Word.PartOfSpelledToken &&
678 isStringLiteral(
Word.PartOfSpelledToken->kind()))
681 const SourceManager &SM = TB.sourceManager();
684 auto File = SM.getFileID(
Word.Location);
685 unsigned WordLine = SM.getSpellingLineNumber(
Word.Location);
686 auto Cost = [&](SourceLocation
Loc) ->
unsigned {
687 assert(SM.getFileID(
Loc) == File &&
"spelled token in wrong file?");
688 unsigned Line = SM.getSpellingLineNumber(
Loc);
689 return Line >= WordLine ?
Line - WordLine : 2 * (WordLine -
Line);
691 const syntax::Token *BestTok =
nullptr;
692 unsigned BestCost = -1;
696 unsigned MaxDistance =
697 1U << std::min<unsigned>(
Word.Text.size(),
698 std::numeric_limits<unsigned>::digits - 1);
705 WordLine + 1 <= MaxDistance / 2 ? 1 : WordLine + 1 - MaxDistance / 2;
706 unsigned LineMax = WordLine + 1 + MaxDistance;
707 SourceLocation LocMin = SM.translateLineCol(File, LineMin, 1);
708 assert(LocMin.isValid());
709 SourceLocation LocMax = SM.translateLineCol(File, LineMax, 1);
710 assert(LocMax.isValid());
714 auto Consider = [&](
const syntax::Token &Tok) {
715 if (Tok.location() < LocMin || Tok.location() > LocMax)
717 if (!(Tok.kind() == tok::identifier && Tok.text(SM) ==
Word.Text))
720 if (Tok.location() ==
Word.Location)
723 unsigned TokCost = Cost(Tok.location());
724 if (TokCost >= BestCost)
728 if (!(tokenSpelledAt(Tok.location(), TB) || TB.expansionStartingAt(&Tok)))
735 auto SpelledTokens = TB.spelledTokens(File);
737 auto *I = llvm::partition_point(SpelledTokens, [&](
const syntax::Token &T) {
738 assert(SM.getFileID(T.location()) == SM.getFileID(
Word.Location));
739 return T.location() <
Word.Location;
742 for (
const syntax::Token &Tok : llvm::makeArrayRef(I, SpelledTokens.end()))
746 for (
const syntax::Token &Tok :
747 llvm::reverse(llvm::makeArrayRef(SpelledTokens.begin(), I)))
753 "Word {0} under cursor {1} isn't a token (after PP), trying nearby {2}",
754 Word.Text,
Word.Location.printToString(SM),
755 BestTok->location().printToString(SM));
766 elog(
"Failed to get a path for the main file, so no references");
770 if (
auto File = locateFileReferent(
Pos, AST, *MainFilePath))
771 return {std::move(*File)};
775 elog(
"locateSymbolAt failed to convert position to source location: {0}",
780 const syntax::Token *TouchedIdentifier =
nullptr;
781 auto TokensTouchingCursor =
782 syntax::spelledTokensTouching(*CurLoc, AST.
getTokens());
783 for (
const syntax::Token &Tok : TokensTouchingCursor) {
784 if (Tok.kind() == tok::identifier) {
785 if (
auto Macro = locateMacroReferent(Tok, AST, *MainFilePath))
789 return {*std::move(
Macro)};
791 TouchedIdentifier = &Tok;
795 if (Tok.kind() == tok::kw_auto || Tok.kind() == tok::kw_decltype) {
799 auto LocSym = locateSymbolForType(AST, *
Deduced);
806 ASTNodeKind NodeKind;
807 auto ASTResults = locateASTReferent(*CurLoc, TouchedIdentifier, AST,
808 *MainFilePath,
Index, NodeKind);
809 if (!ASTResults.empty())
817 if (
const syntax::Token *NearbyIdent =
819 if (
auto Macro = locateMacroReferent(*NearbyIdent, AST, *MainFilePath)) {
820 log(
"Found macro definition heuristically using nearby identifier {0}",
822 return {*std::move(
Macro)};
824 ASTResults = locateASTReferent(NearbyIdent->location(), NearbyIdent, AST,
825 *MainFilePath,
Index, NodeKind);
826 if (!ASTResults.empty()) {
827 log(
"Found definition heuristically using nearby identifier {0}",
828 NearbyIdent->text(SM));
831 vlog(
"No definition found using nearby identifier {0} at {1}",
Word->Text,
832 Word->Location.printToString(SM));
835 auto TextualResults =
837 if (!TextualResults.empty())
838 return TextualResults;
849 elog(
"Failed to get a path for the main file, so no links");
853 std::vector<DocumentLink> Result;
855 if (Inc.Resolved.empty())
857 auto HashLoc = SM.getComposedLoc(SM.getMainFileID(), Inc.HashOffset);
858 const auto *HashTok = AST.
getTokens().spelledTokenAt(HashLoc);
859 assert(HashTok &&
"got inclusion at wrong offset");
860 const auto *IncludeTok = std::next(HashTok);
861 const auto *FileTok = std::next(IncludeTok);
866 syntax::FileRange(SM, FileTok->location(), Inc.Written.length())
880 class ReferenceFinder :
public index::IndexDataConsumer {
887 Range range(
const SourceManager &SM)
const {
892 ReferenceFinder(
const ParsedAST &AST,
893 const llvm::ArrayRef<const NamedDecl *> Targets,
bool PerToken)
894 : PerToken(PerToken), AST(AST) {
895 for (
const NamedDecl *ND : Targets) {
896 const Decl *CD = ND->getCanonicalDecl();
901 std::vector<Reference> take() && {
902 llvm::sort(References, [](
const Reference &L,
const Reference &R) {
903 auto LTok = L.SpelledTok.location();
904 auto RTok = R.SpelledTok.location();
905 return std::tie(LTok, L.Role) < std::tie(RTok, R.Role);
909 [](
const Reference &L,
const Reference &R) {
910 auto LTok = L.SpelledTok.location();
911 auto RTok = R.SpelledTok.location();
912 return std::tie(LTok, L.Role) ==
913 std::tie(RTok, R.Role);
916 return std::move(References);
920 handleDeclOccurrence(
const Decl *
D, index::SymbolRoleSet Roles,
921 llvm::ArrayRef<index::SymbolRelation> Relations,
923 index::IndexDataConsumer::ASTNodeInfo ASTNode)
override {
924 auto DeclID = TargetDeclToID.find(
D->getCanonicalDecl());
925 if (DeclID == TargetDeclToID.end())
927 const SourceManager &SM = AST.getSourceManager();
930 const auto &TB = AST.getTokens();
932 llvm::SmallVector<SourceLocation, 1> Locs;
936 if (
auto *OME = llvm::dyn_cast_or_null<ObjCMessageExpr>(ASTNode.OrigE)) {
937 OME->getSelectorLocs(Locs);
938 }
else if (
auto *OMD =
939 llvm::dyn_cast_or_null<ObjCMethodDecl>(ASTNode.OrigD)) {
940 OMD->getSelectorLocs(Locs);
944 if (!Locs.empty() && Locs.front() !=
Loc)
950 for (SourceLocation L : Locs) {
951 L = SM.getFileLoc(L);
952 if (
const auto *Tok = TB.spelledTokenAt(L))
953 References.push_back({*Tok, Roles, DeclID->getSecond()});
961 const ParsedAST &AST;
962 llvm::DenseMap<const Decl *, SymbolID> TargetDeclToID;
965 std::vector<ReferenceFinder::Reference>
966 findRefs(
const llvm::ArrayRef<const NamedDecl*> TargetDecls, ParsedAST &AST,
968 ReferenceFinder RefFinder(AST, TargetDecls, PerToken);
969 index::IndexingOptions IndexOpts;
970 IndexOpts.SystemSymbolFilter =
971 index::IndexingOptions::SystemSymbolFilterKind::All;
972 IndexOpts.IndexFunctionLocals =
true;
973 IndexOpts.IndexParametersInDeclarations =
true;
974 IndexOpts.IndexTemplateParameters =
true;
977 return std::move(RefFinder).take();
980 const Stmt *getFunctionBody(DynTypedNode N) {
981 if (
const auto *FD = N.get<FunctionDecl>())
982 return FD->getBody();
983 if (
const auto *FD = N.get<BlockDecl>())
984 return FD->getBody();
985 if (
const auto *FD = N.get<LambdaExpr>())
986 return FD->getBody();
987 if (
const auto *FD = N.get<ObjCMethodDecl>())
988 return FD->getBody();
992 const Stmt *getLoopBody(DynTypedNode N) {
993 if (
const auto *LS = N.get<ForStmt>())
994 return LS->getBody();
995 if (
const auto *LS = N.get<CXXForRangeStmt>())
996 return LS->getBody();
997 if (
const auto *LS = N.get<WhileStmt>())
998 return LS->getBody();
999 if (
const auto *LS = N.get<DoStmt>())
1000 return LS->getBody();
1016 All = Break | Continue | Return | Case | Throw | Goto,
1020 std::vector<SourceLocation> &Result;
1021 const SourceManager &SM;
1025 template <
typename Func>
1026 bool filterAndTraverse(DynTypedNode
D,
const Func &Delegate) {
1027 auto RestoreIgnore = llvm::make_scope_exit(
1028 [OldIgnore(Ignore),
this] { Ignore = OldIgnore; });
1029 if (getFunctionBody(
D))
1031 else if (getLoopBody(
D))
1032 Ignore |= Continue | Break;
1033 else if (
D.get<SwitchStmt>())
1034 Ignore |= Break | Case;
1036 return (Ignore == All) ? true : Delegate();
1039 void found(
Target T, SourceLocation
Loc) {
1042 if (SM.isBeforeInTranslationUnit(
Loc,
Bounds.getBegin()) ||
1043 SM.isBeforeInTranslationUnit(
Bounds.getEnd(),
Loc))
1045 Result.push_back(
Loc);
1049 FindControlFlow(SourceRange
Bounds, std::vector<SourceLocation> &Result,
1050 const SourceManager &SM)
1055 bool TraverseDecl(
Decl *
D) {
1056 return !
D || filterAndTraverse(DynTypedNode::create(*
D), [&] {
1057 return RecursiveASTVisitor::TraverseDecl(
D);
1060 bool TraverseStmt(Stmt *S) {
1061 return !S || filterAndTraverse(DynTypedNode::create(*S), [&] {
1062 return RecursiveASTVisitor::TraverseStmt(S);
1067 bool VisitReturnStmt(ReturnStmt *R) {
1068 found(Return, R->getReturnLoc());
1071 bool VisitBreakStmt(BreakStmt *
B) {
1072 found(Break,
B->getBreakLoc());
1075 bool VisitContinueStmt(ContinueStmt *
C) {
1076 found(Continue,
C->getContinueLoc());
1079 bool VisitSwitchCase(SwitchCase *
C) {
1080 found(Case,
C->getKeywordLoc());
1083 bool VisitCXXThrowExpr(CXXThrowExpr *T) {
1084 found(Throw, T->getThrowLoc());
1087 bool VisitGotoStmt(GotoStmt *G) {
1089 if (
const auto *LD = G->getLabel()) {
1090 if (SM.isBeforeInTranslationUnit(LD->getLocation(),
Bounds.getBegin()) ||
1091 SM.isBeforeInTranslationUnit(
Bounds.getEnd(), LD->getLocation()))
1092 found(Goto, G->getGotoLoc());
1101 SourceRange findCaseBounds(
const SwitchStmt &Switch, SourceLocation
Loc,
1102 const SourceManager &SM) {
1105 std::vector<const SwitchCase *> Cases;
1106 for (
const SwitchCase *Case = Switch.getSwitchCaseList(); Case;
1107 Case = Case->getNextSwitchCase())
1108 Cases.push_back(Case);
1109 llvm::sort(Cases, [&](
const SwitchCase *L,
const SwitchCase *R) {
1110 return SM.isBeforeInTranslationUnit(L->getKeywordLoc(), R->getKeywordLoc());
1114 auto CaseAfter = llvm::partition_point(Cases, [&](
const SwitchCase *
C) {
1115 return !SM.isBeforeInTranslationUnit(
Loc,
C->getKeywordLoc());
1117 SourceLocation End = CaseAfter == Cases.end() ? Switch.getEndLoc()
1118 : (*CaseAfter)->getKeywordLoc();
1121 if (CaseAfter == Cases.begin())
1122 return SourceRange(Switch.getBeginLoc(), End);
1124 auto CaseBefore = std::prev(CaseAfter);
1126 while (CaseBefore != Cases.begin() &&
1127 (*std::prev(CaseBefore))->getSubStmt() == *CaseBefore)
1129 return SourceRange((*CaseBefore)->getKeywordLoc(), End);
1139 std::vector<SourceLocation> relatedControlFlow(
const SelectionTree::Node &N) {
1140 const SourceManager &SM =
1141 N.getDeclContext().getParentASTContext().getSourceManager();
1142 std::vector<SourceLocation> Result;
1145 enum class Cur {
None, Break, Continue, Return, Case, Throw } Cursor;
1146 if (N.ASTNode.get<BreakStmt>()) {
1147 Cursor = Cur::Break;
1148 }
else if (N.ASTNode.get<ContinueStmt>()) {
1149 Cursor = Cur::Continue;
1150 }
else if (N.ASTNode.get<ReturnStmt>()) {
1151 Cursor = Cur::Return;
1152 }
else if (N.ASTNode.get<CXXThrowExpr>()) {
1153 Cursor = Cur::Throw;
1154 }
else if (N.ASTNode.get<SwitchCase>()) {
1156 }
else if (
const GotoStmt *GS = N.ASTNode.get<GotoStmt>()) {
1158 Result.push_back(GS->getGotoLoc());
1159 if (
const auto *LD = GS->getLabel())
1160 Result.push_back(LD->getLocation());
1166 const Stmt *
Root =
nullptr;
1169 for (
const auto *P = &N; P; P = P->Parent) {
1171 if (
const Stmt *FunctionBody = getFunctionBody(P->ASTNode)) {
1172 if (Cursor == Cur::Return || Cursor == Cur::Throw) {
1173 Root = FunctionBody;
1178 if (
const Stmt *LoopBody = getLoopBody(P->ASTNode)) {
1179 if (Cursor == Cur::None || Cursor == Cur::Break ||
1180 Cursor == Cur::Continue) {
1184 Result.push_back(P->ASTNode.getSourceRange().getBegin());
1191 if (
const auto *SS = P->ASTNode.get<SwitchStmt>()) {
1192 if (Cursor == Cur::Break || Cursor == Cur::Case) {
1193 Result.push_back(SS->getSwitchLoc());
1194 Root = SS->getBody();
1196 Bounds = findCaseBounds(*SS, N.ASTNode.getSourceRange().getBegin(), SM);
1201 if (Cursor == Cur::None)
1207 FindControlFlow(
Bounds, Result, SM).TraverseStmt(
const_cast<Stmt *
>(
Root));
1212 DocumentHighlight toHighlight(
const ReferenceFinder::Reference &Ref,
1213 const SourceManager &SM) {
1214 DocumentHighlight DH;
1215 DH.range = Ref.range(SM);
1216 if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Write))
1218 else if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Read))
1225 llvm::Optional<DocumentHighlight> toHighlight(SourceLocation
Loc,
1226 const syntax::TokenBuffer &TB) {
1227 Loc = TB.sourceManager().getFileLoc(
Loc);
1228 if (
const auto *Tok = TB.spelledTokenAt(
Loc)) {
1229 DocumentHighlight Result;
1232 CharSourceRange::getCharRange(Tok->location(), Tok->endLocation()));
1246 llvm::consumeError(CurLoc.takeError());
1249 std::vector<DocumentHighlight> Result;
1256 if (!TargetDecls.empty()) {
1259 for (
const auto &
Ref : findRefs(TargetDecls, AST,
true))
1260 Result.push_back(toHighlight(
Ref, SM));
1263 auto ControlFlow = relatedControlFlow(*N);
1264 if (!ControlFlow.empty()) {
1265 for (SourceLocation
Loc : ControlFlow)
1266 if (
auto Highlight = toHighlight(
Loc, AST.
getTokens()))
1267 Result.push_back(std::move(*Highlight));
1291 if (!MainFilePath) {
1292 elog(
"Failed to get a path for the main file, so no implementations.");
1297 elog(
"Failed to convert position to source location: {0}",
1298 CurLoc.takeError());
1303 llvm::DenseSet<SymbolID> IDs;
1305 for (
const NamedDecl *ND : getDeclAtPosition(AST, *CurLoc, Relations)) {
1306 if (
const auto *CXXMD = llvm::dyn_cast<CXXMethodDecl>(ND)) {
1307 if (CXXMD->isVirtual()) {
1311 }
else if (
const auto *RD = dyn_cast<CXXRecordDecl>(ND)) {
1316 return findImplementors(std::move(IDs),
QueryKind,
Index, *MainFilePath);
1322 void getOverriddenMethods(
const CXXMethodDecl *CMD,
1323 llvm::DenseSet<SymbolID> &OverriddenMethods) {
1326 for (
const CXXMethodDecl *
Base : CMD->overridden_methods()) {
1328 OverriddenMethods.insert(
ID);
1329 getOverriddenMethods(
Base, OverriddenMethods);
1340 if (!MainFilePath) {
1341 elog(
"Failed to get a path for the main file, so no references");
1347 llvm::consumeError(CurLoc.takeError());
1351 llvm::DenseSet<SymbolID> IDsToQuery, OverriddenMethods;
1353 const auto *IdentifierAtCursor =
1354 syntax::spelledIdentifierTouching(*CurLoc, AST.
getTokens());
1355 llvm::Optional<DefinedMacro>
Macro;
1356 if (IdentifierAtCursor)
1363 auto Refs = IDToRefs.find(MacroSID);
1365 for (
const auto &
Ref :
Refs->second) {
1367 Result.Loc.range =
Ref.Rng;
1368 Result.Loc.uri = URIMainFile;
1369 if (
Ref.IsDefinition) {
1373 Results.References.push_back(std::move(Result));
1376 IDsToQuery.insert(MacroSID);
1383 std::vector<const NamedDecl *> Decls =
1384 getDeclAtPosition(AST, *CurLoc, Relations);
1385 llvm::SmallVector<const NamedDecl *> TargetsInMainFile;
1386 for (
const NamedDecl *
D : Decls) {
1390 TargetsInMainFile.push_back(
D);
1394 if (
D->getParentFunctionOrMethod())
1396 IDsToQuery.insert(
ID);
1402 for (
const NamedDecl *ND : Decls) {
1405 if (
const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(ND)) {
1406 if (CMD->isVirtual()) {
1409 getOverriddenMethods(CMD, OverriddenMethods);
1416 auto MainFileRefs = findRefs(TargetsInMainFile, AST,
false);
1420 MainFileRefs.erase(std::unique(MainFileRefs.begin(), MainFileRefs.end(),
1421 [](
const ReferenceFinder::Reference &L,
1422 const ReferenceFinder::Reference &R) {
1423 return L.SpelledTok.location() ==
1424 R.SpelledTok.location();
1426 MainFileRefs.end());
1427 for (
const auto &
Ref : MainFileRefs) {
1429 Result.Loc.range =
Ref.range(SM);
1430 Result.Loc.uri = URIMainFile;
1431 if (
Ref.Role &
static_cast<unsigned>(index::SymbolRole::Declaration))
1434 if (
Ref.Role &
static_cast<unsigned>(index::SymbolRole::Definition))
1435 Result.Attributes |=
1437 Results.References.push_back(std::move(Result));
1443 if (Limit &&
Results.References.size() >= Limit) {
1444 Results.HasMore = true;
1447 const auto LSPLocDecl =
1448 toLSPLocation(
Object.CanonicalDeclaration, *MainFilePath);
1449 const auto LSPLocDef = toLSPLocation(
Object.Definition, *MainFilePath);
1450 if (LSPLocDecl && LSPLocDecl != LSPLocDef) {
1452 Result.Loc = std::move(*LSPLocDecl);
1455 Results.References.push_back(std::move(Result));
1459 Result.Loc = std::move(*LSPLocDef);
1463 Results.References.push_back(std::move(Result));
1469 auto QueryIndex = [&](llvm::DenseSet<SymbolID> IDs,
bool AllowAttributes,
1470 bool AllowMainFileSymbols) {
1474 Req.
IDs = std::move(IDs);
1476 if (Limit <
Results.References.size()) {
1486 auto LSPLoc = toLSPLocation(R.
Location, *MainFilePath);
1489 (!AllowMainFileSymbols && LSPLoc->uri.file() == *MainFilePath))
1492 Result.Loc = std::move(*LSPLoc);
1493 if (AllowAttributes) {
1498 Result.Attributes |=
1501 Results.References.push_back(std::move(Result));
1504 QueryIndex(std::move(IDsToQuery),
true,
1509 QueryIndex(std::move(OverriddenMethods),
false,
1518 llvm::consumeError(CurLoc.takeError());
1522 std::vector<SymbolDetails>
Results;
1528 for (
const NamedDecl *
D : getDeclAtPosition(AST, *CurLoc, Relations)) {
1533 NewSymbol.
name = std::string(SplitQName.second);
1536 if (
const auto *ParentND =
1537 dyn_cast_or_null<NamedDecl>(
D->getDeclContext()))
1540 llvm::SmallString<32> USR;
1541 if (!index::generateUSRForDecl(
D, USR)) {
1542 NewSymbol.
USR = std::string(USR.str());
1545 Results.push_back(std::move(NewSymbol));
1548 const auto *IdentifierAtCursor =
1549 syntax::spelledIdentifierTouching(*CurLoc, AST.
getTokens());
1550 if (!IdentifierAtCursor)
1555 NewMacro.
name = std::string(
M->Name);
1556 llvm::SmallString<32> USR;
1557 if (!index::generateUSRForMacro(NewMacro.
name,
M->Info->getDefinitionLoc(),
1559 NewMacro.
USR = std::string(USR.str());
1562 Results.push_back(std::move(NewMacro));
1583 OS <<
" [override]";
1587 template <
typename HierarchyItem>
1589 ASTContext &
Ctx = ND.getASTContext();
1590 auto &SM =
Ctx.getSourceManager();
1592 SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc()));
1593 SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc()));
1594 const auto DeclRange =
1600 auto TUPath =
getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
1601 if (!FilePath || !TUPath)
1606 SM, Lexer::getLocForEndOfToken(NameLoc, 0, SM,
Ctx.getLangOpts()));
1618 HI.selectionRange =
Range{NameBegin, NameEnd};
1619 if (!HI.range.contains(HI.selectionRange)) {
1622 HI.range = HI.selectionRange;
1637 static llvm::Optional<TypeHierarchyItem>
1639 auto Result = declToHierarchyItem<TypeHierarchyItem>(ND);
1641 Result->deprecated = ND.isDeprecated();
1645 static llvm::Optional<CallHierarchyItem>
1647 auto Result = declToHierarchyItem<CallHierarchyItem>(ND);
1648 if (Result && ND.isDeprecated())
1653 template <
typename HierarchyItem>
1658 elog(
"Failed to convert symbol to hierarchy item: {0}",
Loc.takeError());
1662 HI.name = std::string(S.
Name);
1664 HI.selectionRange =
Loc->range;
1667 HI.range = HI.selectionRange;
1672 HI.data = S.
ID.
str();
1677 static llvm::Optional<TypeHierarchyItem>
1679 auto Result = symbolToHierarchyItem<TypeHierarchyItem>(S, TUPath);
1685 static llvm::Optional<CallHierarchyItem>
1687 auto Result = symbolToHierarchyItem<CallHierarchyItem>(S, TUPath);
1694 std::vector<TypeHierarchyItem> &SubTypes,
1700 if (Optional<TypeHierarchyItem> ChildSym =
1703 ChildSym->children.emplace();
1706 SubTypes.emplace_back(std::move(*ChildSym));
1714 std::vector<TypeHierarchyItem> &SuperTypes,
1721 auto *Pattern = CXXRD.getDescribedTemplate() ? &CXXRD :
nullptr;
1723 if (!RPSet.insert(Pattern).second) {
1728 for (
const CXXRecordDecl *ParentDecl :
typeParents(&CXXRD)) {
1729 if (Optional<TypeHierarchyItem> ParentSym =
1731 ParentSym->parents.emplace();
1733 SuperTypes.emplace_back(std::move(*ParentSym));
1738 RPSet.erase(Pattern);
1743 auto RecordFromNode =
1757 const NamedDecl *
D = Decls[0];
1759 if (
const VarDecl *VD = dyn_cast<VarDecl>(
D)) {
1761 return VD->getType().getTypePtr()->getAsCXXRecordDecl();
1764 if (
const CXXMethodDecl *
Method = dyn_cast<CXXMethodDecl>(
D)) {
1766 return Method->getParent();
1773 return dyn_cast<CXXRecordDecl>(
D);
1777 const CXXRecordDecl *Result =
nullptr;
1780 llvm::consumeError(
Offset.takeError());
1785 Result = RecordFromNode(ST.commonAncestor());
1786 return Result != nullptr;
1796 while (N && N->
ASTNode.get<NestedNameSpecifierLoc>())
1802 if (
const TypeLoc *TL = N->
ASTNode.get<TypeLoc>()) {
1803 if (llvm::isa<DeducedType>(TL->getTypePtr()))
1808 if (llvm::isa<TypedefType>(TL->getTypePtr()))
1809 return TL->getTypePtr()->getLocallyUnqualifiedSingleStepDesugaredType();
1810 return TL->getType();
1814 if (
const auto *CCI = N->
ASTNode.get<CXXCtorInitializer>()) {
1815 if (
const FieldDecl *FD = CCI->getAnyMember())
1816 return FD->getType();
1817 if (
const Type *
Base = CCI->getBaseClass())
1818 return QualType(
Base, 0);
1822 if (
const auto *CBS = N->
ASTNode.get<CXXBaseSpecifier>())
1823 return CBS->getType();
1826 struct Visitor : ConstDeclVisitor<Visitor, QualType> {
1827 QualType VisitValueDecl(
const ValueDecl *
D) {
return D->getType(); }
1829 QualType VisitTypeDecl(
const TypeDecl *
D) {
1830 return QualType(
D->getTypeForDecl(), 0);
1833 QualType VisitTypedefNameDecl(
const TypedefNameDecl *
D) {
1834 return D->getUnderlyingType();
1837 QualType VisitTemplateDecl(
const TemplateDecl *
D) {
1838 return Visit(
D->getTemplatedDecl());
1844 if (
const Stmt *S = N->
ASTNode.get<Stmt>()) {
1845 struct Visitor : ConstStmtVisitor<Visitor, QualType> {
1847 QualType type(
const Stmt *S) {
return S ? Visit(S) : QualType(); }
1850 QualType VisitExpr(
const Expr *S) {
1851 return S->IgnoreImplicitAsWritten()->getType();
1854 QualType VisitCXXDeleteExpr(
const CXXDeleteExpr *S) {
1855 return S->getDestroyedType();
1857 QualType VisitCXXPseudoDestructorExpr(
const CXXPseudoDestructorExpr *S) {
1858 return S->getDestroyedType();
1860 QualType VisitCXXThrowExpr(
const CXXThrowExpr *S) {
1861 return S->getSubExpr()->getType();
1863 QualType VisitCoyieldExpr(
const CoyieldExpr *S) {
1864 return type(S->getOperand());
1867 QualType VisitDesignatedInitExpr(
const DesignatedInitExpr *S) {
1869 for (
auto &
D : llvm::reverse(S->designators()))
1870 if (
D.isFieldDesignator())
1871 if (
const auto *FD =
D.getField())
1872 return FD->getType();
1877 QualType VisitSwitchStmt(
const SwitchStmt *S) {
1878 return type(S->getCond());
1880 QualType VisitWhileStmt(
const WhileStmt *S) {
return type(S->getCond()); }
1881 QualType VisitDoStmt(
const DoStmt *S) {
return type(S->getCond()); }
1882 QualType VisitIfStmt(
const IfStmt *S) {
return type(S->getCond()); }
1883 QualType VisitCaseStmt(
const CaseStmt *S) {
return type(S->getLHS()); }
1884 QualType VisitCXXForRangeStmt(
const CXXForRangeStmt *S) {
1885 return S->getLoopVariable()->getType();
1887 QualType VisitReturnStmt(
const ReturnStmt *S) {
1888 return type(S->getRetValue());
1890 QualType VisitCoreturnStmt(
const CoreturnStmt *S) {
1891 return type(S->getOperand());
1893 QualType VisitCXXCatchStmt(
const CXXCatchStmt *S) {
1894 return S->getCaughtType();
1896 QualType VisitObjCAtThrowStmt(
const ObjCAtThrowStmt *S) {
1897 return type(S->getThrowExpr());
1899 QualType VisitObjCAtCatchStmt(
const ObjCAtCatchStmt *S) {
1900 return S->getCatchParamDecl() ? S->getCatchParamDecl()->getType()
1917 if (
const auto* TDT = T->getAs<TypedefType>())
1918 return QualType(TDT, 0);
1921 if (
const auto *PT = T->getAs<PointerType>())
1923 if (
const auto *RT = T->getAs<ReferenceType>())
1925 if (
const auto *AT = T->getAsArrayTypeUnsafe())
1930 if (
auto *FT = T->getAs<FunctionType>())
1932 if (
auto *CRD = T->getAsCXXRecordDecl()) {
1933 if (CRD->isLambda())
1934 return unwrapFindType(CRD->getLambdaCallOperator()->getReturnType());
1945 std::vector<LocatedSymbol> Result;
1947 elog(
"failed to convert position {0} for findTypes: {1}",
Pos,
1952 auto SymbolsFromNode =
1957 return locateSymbolForType(AST,
Type);
1961 Result = SymbolsFromNode(ST.commonAncestor());
1962 return !Result.empty();
1967 std::vector<const CXXRecordDecl *>
typeParents(
const CXXRecordDecl *CXXRD) {
1968 std::vector<const CXXRecordDecl *> Result;
1972 if (
auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD)) {
1973 if (CTSD->isInvalidDecl())
1974 CXXRD = CTSD->getSpecializedTemplate()->getTemplatedDecl();
1978 if (!CXXRD->hasDefinition())
1981 for (
auto Base : CXXRD->bases()) {
1982 const CXXRecordDecl *ParentDecl =
nullptr;
1985 if (
const RecordType *RT =
Type->getAs<RecordType>()) {
1986 ParentDecl = RT->getAsCXXRecordDecl();
1992 if (
const TemplateSpecializationType *TS =
1993 Type->getAs<TemplateSpecializationType>()) {
1994 TemplateName TN = TS->getTemplateName();
1995 if (TemplateDecl *TD = TN.getAsTemplateDecl()) {
1996 ParentDecl = dyn_cast<CXXRecordDecl>(TD->getTemplatedDecl());
2002 Result.push_back(ParentDecl);
2008 llvm::Optional<TypeHierarchyItem>
2029 if (
auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD))
2030 CXXRD = CTSD->getTemplateInstantiationPattern();
2038 Result->parents.emplace();
2044 if (WantChildren && ResolveLevels > 0) {
2045 Result->children.emplace();
2075 std::vector<CallHierarchyItem>
2077 std::vector<CallHierarchyItem> Result;
2081 elog(
"prepareCallHierarchy failed to convert position to source location: "
2086 for (
const NamedDecl *
Decl : getDeclAtPosition(AST, *
Loc, {})) {
2087 if (!(isa<DeclContext>(
Decl) &&
2088 cast<DeclContext>(
Decl)->isFunctionOrMethod()) &&
2089 Decl->getKind() != Decl::Kind::FunctionTemplate)
2092 Result.emplace_back(std::move(*CHI));
2097 std::vector<CallHierarchyIncomingCall>
2099 std::vector<CallHierarchyIncomingCall>
Results;
2104 elog(
"incomingCalls failed to find symbol: {0}",
ID.takeError());
2114 Request.
IDs.insert(*
ID);
2123 llvm::DenseMap<SymbolID, std::vector<Range>> CallsIn;
2130 elog(
"incomingCalls failed to convert location: {0}",
Loc.takeError());
2133 auto It = CallsIn.try_emplace(R.
Container, std::vector<Range>{}).first;
2134 It->second.push_back(
Loc->range);
2141 auto It = CallsIn.find(Caller.
ID);
2142 assert(It != CallsIn.end());
2150 return A.from.name <
B.from.name;
2156 const FunctionDecl *FD) {
2159 llvm::DenseSet<const Decl *> DeclRefs;
2163 for (
const Decl *
D :
Ref.Targets) {
2164 if (!index::isFunctionLocalSymbol(D) && !D->isTemplateParameter() &&