brintos / llvm-project-archived public Read only

1//===--- XRefs.cpp -----------------------------------------------*- C++-*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8#include "XRefs.h"9#include "AST.h"10#include "FindSymbols.h"11#include "FindTarget.h"12#include "Headers.h"13#include "IncludeCleaner.h"14#include "ParsedAST.h"15#include "Protocol.h"16#include "Quality.h"17#include "Selection.h"18#include "SourceCode.h"19#include "URI.h"20#include "clang-include-cleaner/Analysis.h"21#include "clang-include-cleaner/Types.h"22#include "index/Index.h"23#include "index/Merge.h"24#include "index/Ref.h"25#include "index/Relation.h"26#include "index/SymbolCollector.h"27#include "index/SymbolID.h"28#include "index/SymbolLocation.h"29#include "support/Logger.h"30#include "clang/AST/ASTContext.h"31#include "clang/AST/ASTTypeTraits.h"32#include "clang/AST/Attr.h"33#include "clang/AST/Attrs.inc"34#include "clang/AST/Decl.h"35#include "clang/AST/DeclCXX.h"36#include "clang/AST/DeclObjC.h"37#include "clang/AST/DeclTemplate.h"38#include "clang/AST/DeclVisitor.h"39#include "clang/AST/ExprCXX.h"40#include "clang/AST/RecursiveASTVisitor.h"41#include "clang/AST/Stmt.h"42#include "clang/AST/StmtCXX.h"43#include "clang/AST/StmtVisitor.h"44#include "clang/AST/Type.h"45#include "clang/Basic/LLVM.h"46#include "clang/Basic/LangOptions.h"47#include "clang/Basic/SourceLocation.h"48#include "clang/Basic/SourceManager.h"49#include "clang/Basic/TokenKinds.h"50#include "clang/Index/IndexDataConsumer.h"51#include "clang/Index/IndexSymbol.h"52#include "clang/Index/IndexingAction.h"53#include "clang/Index/IndexingOptions.h"54#include "clang/Index/USRGeneration.h"55#include "clang/Lex/Lexer.h"56#include "clang/Sema/HeuristicResolver.h"57#include "clang/Tooling/Syntax/Tokens.h"58#include "llvm/ADT/ArrayRef.h"59#include "llvm/ADT/DenseMap.h"60#include "llvm/ADT/DenseSet.h"61#include "llvm/ADT/STLExtras.h"62#include "llvm/ADT/ScopeExit.h"63#include "llvm/ADT/SmallSet.h"64#include "llvm/ADT/SmallVector.h"65#include "llvm/ADT/StringRef.h"66#include "llvm/Support/Casting.h"67#include "llvm/Support/Error.h"68#include "llvm/Support/ErrorHandling.h"69#include "llvm/Support/Path.h"70#include "llvm/Support/raw_ostream.h"71#include <algorithm>72#include <optional>73#include <string>74#include <vector>75 76namespace clang {77namespace clangd {78namespace {79 80// Returns the single definition of the entity declared by D, if visible.81// In particular:82// - for non-redeclarable kinds (e.g. local vars), return D83// - for kinds that allow multiple definitions (e.g. namespaces), return nullptr84// Kinds of nodes that always return nullptr here will not have definitions85// reported by locateSymbolAt().86const NamedDecl *getDefinition(const NamedDecl *D) {87  assert(D);88  // Decl has one definition that we can find.89  if (const auto *TD = dyn_cast<TagDecl>(D))90    return TD->getDefinition();91  if (const auto *VD = dyn_cast<VarDecl>(D))92    return VD->getDefinition();93  if (const auto *FD = dyn_cast<FunctionDecl>(D))94    return FD->getDefinition();95  if (const auto *CTD = dyn_cast<ClassTemplateDecl>(D))96    if (const auto *RD = CTD->getTemplatedDecl())97      return RD->getDefinition();98  if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {99    if (MD->isThisDeclarationADefinition())100      return MD;101    // Look for the method definition inside the implementation decl.102    auto *DeclCtx = cast<Decl>(MD->getDeclContext());103    if (DeclCtx->isInvalidDecl())104      return nullptr;105 106    if (const auto *CD = dyn_cast<ObjCContainerDecl>(DeclCtx))107      if (const auto *Impl = getCorrespondingObjCImpl(CD))108        return Impl->getMethod(MD->getSelector(), MD->isInstanceMethod());109  }110  if (const auto *CD = dyn_cast<ObjCContainerDecl>(D))111    return getCorrespondingObjCImpl(CD);112  // Only a single declaration is allowed.113  if (isa<ValueDecl>(D) || isa<TemplateTypeParmDecl>(D) ||114      isa<TemplateTemplateParmDecl>(D)) // except cases above115    return D;116  // Multiple definitions are allowed.117  return nullptr; // except cases above118}119 120void logIfOverflow(const SymbolLocation &Loc) {121  if (Loc.Start.hasOverflow() || Loc.End.hasOverflow())122    log("Possible overflow in symbol location: {0}", Loc);123}124 125// Convert a SymbolLocation to LSP's Location.126// TUPath is used to resolve the path of URI.127std::optional<Location> toLSPLocation(const SymbolLocation &Loc,128                                      llvm::StringRef TUPath) {129  if (!Loc)130    return std::nullopt;131  auto LSPLoc = indexToLSPLocation(Loc, TUPath);132  if (!LSPLoc) {133    elog("{0}", LSPLoc.takeError());134    return std::nullopt;135  }136  logIfOverflow(Loc);137  return *LSPLoc;138}139 140SymbolLocation toIndexLocation(const Location &Loc, std::string &URIStorage) {141  SymbolLocation SymLoc;142  URIStorage = Loc.uri.uri();143  SymLoc.FileURI = URIStorage.c_str();144  SymLoc.Start.setLine(Loc.range.start.line);145  SymLoc.Start.setColumn(Loc.range.start.character);146  SymLoc.End.setLine(Loc.range.end.line);147  SymLoc.End.setColumn(Loc.range.end.character);148  return SymLoc;149}150 151// Returns the preferred location between an AST location and an index location.152SymbolLocation getPreferredLocation(const Location &ASTLoc,153                                    const SymbolLocation &IdxLoc,154                                    std::string &Scratch) {155  // Also use a mock symbol for the index location so that other fields (e.g.156  // definition) are not factored into the preference.157  Symbol ASTSym, IdxSym;158  ASTSym.ID = IdxSym.ID = SymbolID("mock_symbol_id");159  ASTSym.CanonicalDeclaration = toIndexLocation(ASTLoc, Scratch);160  IdxSym.CanonicalDeclaration = IdxLoc;161  auto Merged = mergeSymbol(ASTSym, IdxSym);162  return Merged.CanonicalDeclaration;163}164 165std::vector<std::pair<const NamedDecl *, DeclRelationSet>>166getDeclAtPositionWithRelations(ParsedAST &AST, SourceLocation Pos,167                               DeclRelationSet Relations,168                               ASTNodeKind *NodeKind = nullptr) {169  unsigned Offset = AST.getSourceManager().getDecomposedSpellingLoc(Pos).second;170  std::vector<std::pair<const NamedDecl *, DeclRelationSet>> Result;171  auto ResultFromTree = [&](SelectionTree ST) {172    if (const SelectionTree::Node *N = ST.commonAncestor()) {173      if (NodeKind)174        *NodeKind = N->ASTNode.getNodeKind();175      // Attributes don't target decls, look at the176      // thing it's attached to.177      // We still report the original NodeKind!178      // This makes the `override` hack work.179      if (N->ASTNode.get<Attr>() && N->Parent)180        N = N->Parent;181      llvm::copy_if(allTargetDecls(N->ASTNode, AST.getHeuristicResolver()),182                    std::back_inserter(Result),183                    [&](auto &Entry) { return !(Entry.second & ~Relations); });184    }185    return !Result.empty();186  };187  SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset,188                            Offset, ResultFromTree);189  return Result;190}191 192std::vector<const NamedDecl *>193getDeclAtPosition(ParsedAST &AST, SourceLocation Pos, DeclRelationSet Relations,194                  ASTNodeKind *NodeKind = nullptr) {195  std::vector<const NamedDecl *> Result;196  for (auto &Entry :197       getDeclAtPositionWithRelations(AST, Pos, Relations, NodeKind))198    Result.push_back(Entry.first);199  return Result;200}201 202// Expects Loc to be a SpellingLocation, will bail out otherwise as it can't203// figure out a filename.204std::optional<Location> makeLocation(const ASTContext &AST, SourceLocation Loc,205                                     llvm::StringRef TUPath) {206  const auto &SM = AST.getSourceManager();207  const auto F = SM.getFileEntryRefForID(SM.getFileID(Loc));208  if (!F)209    return std::nullopt;210  auto FilePath = getCanonicalPath(*F, SM.getFileManager());211  if (!FilePath) {212    log("failed to get path!");213    return std::nullopt;214  }215  Location L;216  L.uri = URIForFile::canonicalize(*FilePath, TUPath);217  // We call MeasureTokenLength here as TokenBuffer doesn't store spelled tokens218  // outside the main file.219  auto TokLen = Lexer::MeasureTokenLength(Loc, SM, AST.getLangOpts());220  L.range = halfOpenToRange(221      SM, CharSourceRange::getCharRange(Loc, Loc.getLocWithOffset(TokLen)));222  return L;223}224 225// Treat #included files as symbols, to enable go-to-definition on them.226std::optional<LocatedSymbol> locateFileReferent(const Position &Pos,227                                                ParsedAST &AST,228                                                llvm::StringRef MainFilePath) {229  for (auto &Inc : AST.getIncludeStructure().MainFileIncludes) {230    if (!Inc.Resolved.empty() && Inc.HashLine == Pos.line) {231      LocatedSymbol File;232      File.Name = std::string(llvm::sys::path::filename(Inc.Resolved));233      File.PreferredDeclaration = {234          URIForFile::canonicalize(Inc.Resolved, MainFilePath), Range{}};235      File.Definition = File.PreferredDeclaration;236      // We're not going to find any further symbols on #include lines.237      return File;238    }239  }240  return std::nullopt;241}242 243// Macros are simple: there's no declaration/definition distinction.244// As a consequence, there's no need to look them up in the index either.245std::optional<LocatedSymbol>246locateMacroReferent(const syntax::Token &TouchedIdentifier, ParsedAST &AST,247                    llvm::StringRef MainFilePath) {248  if (auto M = locateMacroAt(TouchedIdentifier, AST.getPreprocessor())) {249    if (auto Loc =250            makeLocation(AST.getASTContext(), M->NameLoc, MainFilePath)) {251      LocatedSymbol Macro;252      Macro.Name = std::string(M->Name);253      Macro.PreferredDeclaration = *Loc;254      Macro.Definition = Loc;255      Macro.ID = getSymbolID(M->Name, M->Info, AST.getSourceManager());256      return Macro;257    }258  }259  return std::nullopt;260}261 262// A wrapper around `Decl::getCanonicalDecl` to support cases where Clang's263// definition of a canonical declaration doesn't match up to what a programmer264// would expect. For example, Objective-C classes can have three types of265// declarations:266//267// - forward declaration(s): @class MyClass;268// - true declaration (interface definition): @interface MyClass ... @end269// - true definition (implementation): @implementation MyClass ... @end270//271// Clang will consider the forward declaration to be the canonical declaration272// because it is first. We actually want the class definition if it is273// available since that is what a programmer would consider the primary274// declaration to be.275const NamedDecl *getPreferredDecl(const NamedDecl *D) {276  // FIXME: Canonical declarations of some symbols might refer to built-in277  // decls with possibly-invalid source locations (e.g. global new operator).278  // In such cases we should pick up a redecl with valid source location279  // instead of failing.280  D = llvm::cast<NamedDecl>(D->getCanonicalDecl());281 282  // Prefer Objective-C class/protocol definitions over the forward declaration.283  if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(D))284    if (const auto *DefinitionID = ID->getDefinition())285      return DefinitionID;286  if (const auto *PD = dyn_cast<ObjCProtocolDecl>(D))287    if (const auto *DefinitionID = PD->getDefinition())288      return DefinitionID;289 290  return D;291}292 293std::vector<LocatedSymbol> findImplementors(llvm::DenseSet<SymbolID> IDs,294                                            RelationKind Predicate,295                                            const SymbolIndex *Index,296                                            llvm::StringRef MainFilePath) {297  if (IDs.empty() || !Index)298    return {};299  static constexpr trace::Metric FindImplementorsMetric(300      "find_implementors", trace::Metric::Counter, "case");301  switch (Predicate) {302  case RelationKind::BaseOf:303    FindImplementorsMetric.record(1, "find-base");304    break;305  case RelationKind::OverriddenBy:306    FindImplementorsMetric.record(1, "find-override");307    break;308  }309 310  RelationsRequest Req;311  Req.Predicate = Predicate;312  Req.Subjects = std::move(IDs);313  std::vector<LocatedSymbol> Results;314  Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {315    auto DeclLoc =316        indexToLSPLocation(Object.CanonicalDeclaration, MainFilePath);317    if (!DeclLoc) {318      elog("Find overrides: {0}", DeclLoc.takeError());319      return;320    }321    Results.emplace_back();322    Results.back().Name = Object.Name.str();323    Results.back().PreferredDeclaration = *DeclLoc;324    auto DefLoc = indexToLSPLocation(Object.Definition, MainFilePath);325    if (!DefLoc) {326      elog("Failed to convert location: {0}", DefLoc.takeError());327      return;328    }329    Results.back().Definition = *DefLoc;330  });331  return Results;332}333 334// Given LocatedSymbol results derived from the AST, query the index to obtain335// definitions and preferred declarations.336void enhanceLocatedSymbolsFromIndex(llvm::MutableArrayRef<LocatedSymbol> Result,337                                    const SymbolIndex *Index,338                                    llvm::StringRef MainFilePath) {339  LookupRequest QueryRequest;340  llvm::DenseMap<SymbolID, unsigned> ResultIndex;341  for (unsigned I = 0; I < Result.size(); ++I) {342    if (auto ID = Result[I].ID) {343      ResultIndex.try_emplace(ID, I);344      QueryRequest.IDs.insert(ID);345    }346  }347  if (!Index || QueryRequest.IDs.empty())348    return;349  std::string Scratch;350  Index->lookup(QueryRequest, [&](const Symbol &Sym) {351    auto &R = Result[ResultIndex.lookup(Sym.ID)];352 353    if (R.Definition) { // from AST354      // Special case: if the AST yielded a definition, then it may not be355      // the right *declaration*. Prefer the one from the index.356      if (auto Loc = toLSPLocation(Sym.CanonicalDeclaration, MainFilePath))357        R.PreferredDeclaration = *Loc;358 359      // We might still prefer the definition from the index, e.g. for360      // generated symbols.361      if (auto Loc = toLSPLocation(362              getPreferredLocation(*R.Definition, Sym.Definition, Scratch),363              MainFilePath))364        R.Definition = *Loc;365    } else {366      R.Definition = toLSPLocation(Sym.Definition, MainFilePath);367 368      // Use merge logic to choose AST or index declaration.369      if (auto Loc = toLSPLocation(370              getPreferredLocation(R.PreferredDeclaration,371                                   Sym.CanonicalDeclaration, Scratch),372              MainFilePath))373        R.PreferredDeclaration = *Loc;374    }375  });376}377 378bool objcMethodIsTouched(const SourceManager &SM, const ObjCMethodDecl *OMD,379                         SourceLocation Loc) {380  unsigned NumSels = OMD->getNumSelectorLocs();381  for (unsigned I = 0; I < NumSels; ++I)382    if (SM.getSpellingLoc(OMD->getSelectorLoc(I)) == Loc)383      return true;384  return false;385}386 387// Decls are more complicated.388// The AST contains at least a declaration, maybe a definition.389// These are up-to-date, and so generally preferred over index results.390// We perform a single batch index lookup to find additional definitions.391std::vector<LocatedSymbol>392locateASTReferent(SourceLocation CurLoc, const syntax::Token *TouchedIdentifier,393                  ParsedAST &AST, llvm::StringRef MainFilePath,394                  const SymbolIndex *Index, ASTNodeKind &NodeKind) {395  const SourceManager &SM = AST.getSourceManager();396  // Results follow the order of Symbols.Decls.397  std::vector<LocatedSymbol> Result;398 399  static constexpr trace::Metric LocateASTReferentMetric(400      "locate_ast_referent", trace::Metric::Counter, "case");401  auto AddResultDecl = [&](const NamedDecl *D) {402    D = getPreferredDecl(D);403    auto Loc =404        makeLocation(AST.getASTContext(), nameLocation(*D, SM), MainFilePath);405    if (!Loc)406      return;407 408    Result.emplace_back();409    Result.back().Name = printName(AST.getASTContext(), *D);410    Result.back().PreferredDeclaration = *Loc;411    Result.back().ID = getSymbolID(D);412    if (const NamedDecl *Def = getDefinition(D))413      Result.back().Definition = makeLocation(414          AST.getASTContext(), nameLocation(*Def, SM), MainFilePath);415  };416 417  // Emit all symbol locations (declaration or definition) from AST.418  DeclRelationSet Relations =419      DeclRelation::TemplatePattern | DeclRelation::Alias;420  auto Candidates =421      getDeclAtPositionWithRelations(AST, CurLoc, Relations, &NodeKind);422  llvm::DenseSet<SymbolID> VirtualMethods;423  for (const auto &E : Candidates) {424    const NamedDecl *D = E.first;425    if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D)) {426      // Special case: virtual void ^method() = 0: jump to all overrides.427      // FIXME: extend it to ^virtual, unfortunately, virtual location is not428      // saved in the AST.429      if (CMD->isPureVirtual()) {430        if (TouchedIdentifier && SM.getSpellingLoc(CMD->getLocation()) ==431                                     TouchedIdentifier->location()) {432          VirtualMethods.insert(getSymbolID(CMD));433          LocateASTReferentMetric.record(1, "method-to-override");434        }435      }436      // Special case: void foo() ^override: jump to the overridden method.437      if (NodeKind.isSame(ASTNodeKind::getFromNodeKind<OverrideAttr>()) ||438          NodeKind.isSame(ASTNodeKind::getFromNodeKind<FinalAttr>())) {439        // We may be overridding multiple methods - offer them all.440        for (const NamedDecl *ND : CMD->overridden_methods())441          AddResultDecl(ND);442        continue;443      }444    }445    // Special case: - (void)^method {} should jump to overrides, but the decl446    // shouldn't, only the definition. Note that an Objective-C method can447    // override a parent class or protocol.448    //449    // FIXME: Support jumping from a protocol decl to overrides on go-to450    // definition.451    if (const auto *OMD = llvm::dyn_cast<ObjCMethodDecl>(D)) {452      if (OMD->isThisDeclarationADefinition() && TouchedIdentifier &&453          objcMethodIsTouched(SM, OMD, TouchedIdentifier->location())) {454        llvm::SmallVector<const ObjCMethodDecl *, 4> Overrides;455        OMD->getOverriddenMethods(Overrides);456        if (!Overrides.empty()) {457          for (const auto *Override : Overrides)458            AddResultDecl(Override);459          LocateASTReferentMetric.record(1, "objc-overriden-method");460        }461        AddResultDecl(OMD);462        continue;463      }464    }465 466    // Special case: the cursor is on an alias, prefer other results.467    // This targets "using ns::^Foo", where the target is more interesting.468    // This does not trigger on renaming aliases:469    //   `using Foo = ^Bar` already targets Bar via a TypeLoc470    //   `using ^Foo = Bar` has no other results, as Underlying is filtered.471    if (E.second & DeclRelation::Alias && Candidates.size() > 1 &&472        // beginLoc/endLoc are a token range, so rewind the identifier we're in.473        SM.isPointWithin(TouchedIdentifier ? TouchedIdentifier->location()474                                           : CurLoc,475                         D->getBeginLoc(), D->getEndLoc()))476      continue;477 478    // Special case: the point of declaration of a template specialization,479    // it's more useful to navigate to the template declaration.480    if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(D)) {481      if (TouchedIdentifier &&482          D->getLocation() == TouchedIdentifier->location()) {483        LocateASTReferentMetric.record(1, "template-specialization-to-primary");484        AddResultDecl(CTSD->getSpecializedTemplate());485        continue;486      }487    }488 489    // Special case: if the class name is selected, also map Objective-C490    // categories and category implementations back to their class interface.491    //492    // Since `TouchedIdentifier` might refer to the `ObjCCategoryImplDecl`493    // instead of the `ObjCCategoryDecl` we intentionally check the contents494    // of the locs when checking for class name equivalence.495    if (const auto *CD = dyn_cast<ObjCCategoryDecl>(D))496      if (const auto *ID = CD->getClassInterface())497        if (TouchedIdentifier &&498            (CD->getLocation() == TouchedIdentifier->location() ||499             ID->getName() == TouchedIdentifier->text(SM))) {500          LocateASTReferentMetric.record(1, "objc-category-to-class");501          AddResultDecl(ID);502        }503 504    LocateASTReferentMetric.record(1, "regular");505    // Otherwise the target declaration is the right one.506    AddResultDecl(D);507  }508  enhanceLocatedSymbolsFromIndex(Result, Index, MainFilePath);509 510  auto Overrides = findImplementors(VirtualMethods, RelationKind::OverriddenBy,511                                    Index, MainFilePath);512  Result.insert(Result.end(), Overrides.begin(), Overrides.end());513  return Result;514}515 516std::vector<LocatedSymbol> locateSymbolForType(const ParsedAST &AST,517                                               const QualType &Type,518                                               const SymbolIndex *Index) {519  const auto &SM = AST.getSourceManager();520  auto MainFilePath = AST.tuPath();521 522  // FIXME: this sends unique_ptr<Foo> to unique_ptr<T>.523  // Likely it would be better to send it to Foo (heuristically) or to both.524  auto Decls = targetDecl(DynTypedNode::create(Type.getNonReferenceType()),525                          DeclRelation::TemplatePattern | DeclRelation::Alias,526                          AST.getHeuristicResolver());527  if (Decls.empty())528    return {};529 530  std::vector<LocatedSymbol> Results;531  const auto &ASTContext = AST.getASTContext();532 533  for (const NamedDecl *D : Decls) {534    D = getPreferredDecl(D);535 536    auto Loc = makeLocation(ASTContext, nameLocation(*D, SM), MainFilePath);537    if (!Loc)538      continue;539 540    Results.emplace_back();541    Results.back().Name = printName(ASTContext, *D);542    Results.back().PreferredDeclaration = *Loc;543    Results.back().ID = getSymbolID(D);544    if (const NamedDecl *Def = getDefinition(D))545      Results.back().Definition =546          makeLocation(ASTContext, nameLocation(*Def, SM), MainFilePath);547  }548  enhanceLocatedSymbolsFromIndex(Results, Index, MainFilePath);549 550  return Results;551}552 553bool tokenSpelledAt(SourceLocation SpellingLoc, const syntax::TokenBuffer &TB) {554  auto ExpandedTokens = TB.expandedTokens(555      TB.sourceManager().getMacroArgExpandedLocation(SpellingLoc));556  return !ExpandedTokens.empty();557}558 559llvm::StringRef sourcePrefix(SourceLocation Loc, const SourceManager &SM) {560  auto D = SM.getDecomposedLoc(Loc);561  bool Invalid = false;562  llvm::StringRef Buf = SM.getBufferData(D.first, &Invalid);563  if (Invalid || D.second > Buf.size())564    return "";565  return Buf.substr(0, D.second);566}567 568bool isDependentName(ASTNodeKind NodeKind) {569  return NodeKind.isSame(ASTNodeKind::getFromNodeKind<OverloadExpr>()) ||570         NodeKind.isSame(571             ASTNodeKind::getFromNodeKind<CXXDependentScopeMemberExpr>()) ||572         NodeKind.isSame(573             ASTNodeKind::getFromNodeKind<DependentScopeDeclRefExpr>());574}575 576} // namespace577 578std::vector<LocatedSymbol> locateSymbolTextually(const SpelledWord &Word,579                                                 ParsedAST &AST,580                                                 const SymbolIndex *Index,581                                                 llvm::StringRef MainFilePath,582                                                 ASTNodeKind NodeKind) {583  // Don't use heuristics if this is a real identifier, or not an584  // identifier.585  // Exception: dependent names, because those may have useful textual586  // matches that AST-based heuristics cannot find.587  if ((Word.ExpandedToken && !isDependentName(NodeKind)) ||588      !Word.LikelyIdentifier || !Index)589    return {};590  // We don't want to handle words in string literals. (It'd be nice to list591  // *allowed* token kinds explicitly, but comment Tokens aren't retained).592  if (Word.PartOfSpelledToken &&593      isStringLiteral(Word.PartOfSpelledToken->kind()))594    return {};595 596  const auto &SM = AST.getSourceManager();597  // Look up the selected word in the index.598  FuzzyFindRequest Req;599  Req.Query = Word.Text.str();600  Req.ProximityPaths = {MainFilePath.str()};601  // Find the namespaces to query by lexing the file.602  Req.Scopes =603      visibleNamespaces(sourcePrefix(Word.Location, SM), AST.getLangOpts());604  // FIXME: For extra strictness, consider AnyScope=false.605  Req.AnyScope = true;606  // We limit the results to 3 further below. This limit is to avoid fetching607  // too much data, while still likely having enough for 3 results to remain608  // after additional filtering.609  Req.Limit = 10;610  bool TooMany = false;611  using ScoredLocatedSymbol = std::pair<float, LocatedSymbol>;612  std::vector<ScoredLocatedSymbol> ScoredResults;613  Index->fuzzyFind(Req, [&](const Symbol &Sym) {614    // Only consider exact name matches, including case.615    // This is to avoid too many false positives.616    // We could relax this in the future (e.g. to allow for typos) if we make617    // the query more accurate by other means.618    if (Sym.Name != Word.Text)619      return;620 621    // Exclude constructor results. They have the same name as the class,622    // but we don't have enough context to prefer them over the class.623    if (Sym.SymInfo.Kind == index::SymbolKind::Constructor)624      return;625 626    auto MaybeDeclLoc =627        indexToLSPLocation(Sym.CanonicalDeclaration, MainFilePath);628    if (!MaybeDeclLoc) {629      log("locateSymbolNamedTextuallyAt: {0}", MaybeDeclLoc.takeError());630      return;631    }632    LocatedSymbol Located;633    Located.PreferredDeclaration = *MaybeDeclLoc;634    Located.Name = (Sym.Name + Sym.TemplateSpecializationArgs).str();635    Located.ID = Sym.ID;636    if (Sym.Definition) {637      auto MaybeDefLoc = indexToLSPLocation(Sym.Definition, MainFilePath);638      if (!MaybeDefLoc) {639        log("locateSymbolNamedTextuallyAt: {0}", MaybeDefLoc.takeError());640        return;641      }642      Located.PreferredDeclaration = *MaybeDefLoc;643      Located.Definition = *MaybeDefLoc;644    }645 646    if (ScoredResults.size() >= 5) {647      // If we have more than 5 results, don't return anything,648      // as confidence is too low.649      // FIXME: Alternatively, try a stricter query?650      TooMany = true;651      return;652    }653 654    SymbolQualitySignals Quality;655    Quality.merge(Sym);656    SymbolRelevanceSignals Relevance;657    Relevance.Name = Sym.Name;658    Relevance.Query = SymbolRelevanceSignals::Generic;659    Relevance.merge(Sym);660    auto Score = evaluateSymbolAndRelevance(Quality.evaluateHeuristics(),661                                            Relevance.evaluateHeuristics());662    dlog("locateSymbolNamedTextuallyAt: {0}{1} = {2}\n{3}{4}\n", Sym.Scope,663         Sym.Name, Score, Quality, Relevance);664 665    ScoredResults.push_back({Score, std::move(Located)});666  });667 668  if (TooMany) {669    vlog("Heuristic index lookup for {0} returned too many candidates, ignored",670         Word.Text);671    return {};672  }673 674  llvm::sort(ScoredResults,675             [](const ScoredLocatedSymbol &A, const ScoredLocatedSymbol &B) {676               return A.first > B.first;677             });678  std::vector<LocatedSymbol> Results;679  for (auto &Res : std::move(ScoredResults))680    Results.push_back(std::move(Res.second));681  if (Results.empty())682    vlog("No heuristic index definition for {0}", Word.Text);683  else684    log("Found definition heuristically in index for {0}", Word.Text);685  return Results;686}687 688const syntax::Token *findNearbyIdentifier(const SpelledWord &Word,689                                          const syntax::TokenBuffer &TB) {690  // Don't use heuristics if this is a real identifier.691  // Unlikely identifiers are OK if they were used as identifiers nearby.692  if (Word.ExpandedToken)693    return nullptr;694  // We don't want to handle words in string literals. (It'd be nice to list695  // *allowed* token kinds explicitly, but comment Tokens aren't retained).696  if (Word.PartOfSpelledToken &&697      isStringLiteral(Word.PartOfSpelledToken->kind()))698    return {};699 700  const SourceManager &SM = TB.sourceManager();701  // We prefer the closest possible token, line-wise. Backwards is penalized.702  // Ties are implicitly broken by traversal order (first-one-wins).703  auto File = SM.getFileID(Word.Location);704  unsigned WordLine = SM.getSpellingLineNumber(Word.Location);705  auto Cost = [&](SourceLocation Loc) -> unsigned {706    assert(SM.getFileID(Loc) == File && "spelled token in wrong file?");707    unsigned Line = SM.getSpellingLineNumber(Loc);708    return Line >= WordLine ? Line - WordLine : 2 * (WordLine - Line);709  };710  const syntax::Token *BestTok = nullptr;711  unsigned BestCost = -1;712  // Search bounds are based on word length:713  // - forward: 2^N lines714  // - backward: 2^(N-1) lines.715  unsigned MaxDistance =716      1U << std::min<unsigned>(Word.Text.size(),717                               std::numeric_limits<unsigned>::digits - 1);718  // Line number for SM.translateLineCol() should be one-based, also719  // SM.translateLineCol() can handle line number greater than720  // number of lines in the file.721  // - LineMin = max(1, WordLine + 1 - 2^(N-1))722  // - LineMax = WordLine + 1 + 2^N723  unsigned LineMin =724      WordLine + 1 <= MaxDistance / 2 ? 1 : WordLine + 1 - MaxDistance / 2;725  unsigned LineMax = WordLine + 1 + MaxDistance;726  SourceLocation LocMin = SM.translateLineCol(File, LineMin, 1);727  assert(LocMin.isValid());728  SourceLocation LocMax = SM.translateLineCol(File, LineMax, 1);729  assert(LocMax.isValid());730 731  // Updates BestTok and BestCost if Tok is a good candidate.732  // May return true if the cost is too high for this token.733  auto Consider = [&](const syntax::Token &Tok) {734    if (Tok.location() < LocMin || Tok.location() > LocMax)735      return true; // we are too far from the word, break the outer loop.736    if (!(Tok.kind() == tok::identifier && Tok.text(SM) == Word.Text))737      return false;738    // No point guessing the same location we started with.739    if (Tok.location() == Word.Location)740      return false;741    // We've done cheap checks, compute cost so we can break the caller's loop.742    unsigned TokCost = Cost(Tok.location());743    if (TokCost >= BestCost)744      return true; // causes the outer loop to break.745    // Allow locations that might be part of the AST, and macros (even if empty)746    // but not things like disabled preprocessor sections.747    if (!(tokenSpelledAt(Tok.location(), TB) || TB.expansionStartingAt(&Tok)))748      return false;749    // We already verified this token is an improvement.750    BestCost = TokCost;751    BestTok = &Tok;752    return false;753  };754  auto SpelledTokens = TB.spelledTokens(File);755  // Find where the word occurred in the token stream, to search forward & back.756  auto *I = llvm::partition_point(SpelledTokens, [&](const syntax::Token &T) {757    assert(SM.getFileID(T.location()) == SM.getFileID(Word.Location));758    return T.location() < Word.Location; // Comparison OK: same file.759  });760  // Search for matches after the cursor.761  for (const syntax::Token &Tok : llvm::ArrayRef(I, SpelledTokens.end()))762    if (Consider(Tok))763      break; // costs of later tokens are greater...764  // Search for matches before the cursor.765  for (const syntax::Token &Tok :766       llvm::reverse(llvm::ArrayRef(SpelledTokens.begin(), I)))767    if (Consider(Tok))768      break;769 770  if (BestTok)771    vlog(772        "Word {0} under cursor {1} isn't a token (after PP), trying nearby {2}",773        Word.Text, Word.Location.printToString(SM),774        BestTok->location().printToString(SM));775 776  return BestTok;777}778 779std::vector<LocatedSymbol> locateSymbolAt(ParsedAST &AST, Position Pos,780                                          const SymbolIndex *Index) {781  const auto &SM = AST.getSourceManager();782  auto MainFilePath = AST.tuPath();783 784  if (auto File = locateFileReferent(Pos, AST, MainFilePath))785    return {std::move(*File)};786 787  auto CurLoc = sourceLocationInMainFile(SM, Pos);788  if (!CurLoc) {789    elog("locateSymbolAt failed to convert position to source location: {0}",790         CurLoc.takeError());791    return {};792  }793 794  const syntax::Token *TouchedIdentifier = nullptr;795  auto TokensTouchingCursor =796      syntax::spelledTokensTouching(*CurLoc, AST.getTokens());797  for (const syntax::Token &Tok : TokensTouchingCursor) {798    if (Tok.kind() == tok::identifier) {799      if (auto Macro = locateMacroReferent(Tok, AST, MainFilePath))800        // Don't look at the AST or index if we have a macro result.801        // (We'd just return declarations referenced from the macro's802        // expansion.)803        return {*std::move(Macro)};804 805      TouchedIdentifier = &Tok;806      break;807    }808 809    if (Tok.kind() == tok::kw_auto || Tok.kind() == tok::kw_decltype) {810      // go-to-definition on auto should find the definition of the deduced811      // type, if possible812      if (auto Deduced =813              getDeducedType(AST.getASTContext(), AST.getHeuristicResolver(),814                             Tok.location())) {815        auto LocSym = locateSymbolForType(AST, *Deduced, Index);816        if (!LocSym.empty())817          return LocSym;818      }819    }820  }821 822  ASTNodeKind NodeKind;823  auto ASTResults = locateASTReferent(*CurLoc, TouchedIdentifier, AST,824                                      MainFilePath, Index, NodeKind);825  if (!ASTResults.empty())826    return ASTResults;827 828  // If the cursor can't be resolved directly, try fallback strategies.829  auto Word =830      SpelledWord::touching(*CurLoc, AST.getTokens(), AST.getLangOpts());831  if (Word) {832    // Is the same word nearby a real identifier that might refer to something?833    if (const syntax::Token *NearbyIdent =834            findNearbyIdentifier(*Word, AST.getTokens())) {835      if (auto Macro = locateMacroReferent(*NearbyIdent, AST, MainFilePath)) {836        log("Found macro definition heuristically using nearby identifier {0}",837            Word->Text);838        return {*std::move(Macro)};839      }840      ASTResults = locateASTReferent(NearbyIdent->location(), NearbyIdent, AST,841                                     MainFilePath, Index, NodeKind);842      if (!ASTResults.empty()) {843        log("Found definition heuristically using nearby identifier {0}",844            NearbyIdent->text(SM));845        return ASTResults;846      }847      vlog("No definition found using nearby identifier {0} at {1}", Word->Text,848           Word->Location.printToString(SM));849    }850    // No nearby word, or it didn't refer to anything either. Try the index.851    auto TextualResults =852        locateSymbolTextually(*Word, AST, Index, MainFilePath, NodeKind);853    if (!TextualResults.empty())854      return TextualResults;855  }856 857  return {};858}859 860std::vector<DocumentLink> getDocumentLinks(ParsedAST &AST) {861  const auto &SM = AST.getSourceManager();862 863  std::vector<DocumentLink> Result;864  for (auto &Inc : AST.getIncludeStructure().MainFileIncludes) {865    if (Inc.Resolved.empty())866      continue;867 868    // Get the location of the # symbole of the "#include ..." statement869    auto HashLoc = SM.getComposedLoc(SM.getMainFileID(), Inc.HashOffset);870 871    // get the # Token itself, std::next to get the "include" token and the872    // first token after (aka "File Token")873    const auto *HashTok = AST.getTokens().spelledTokenContaining(HashLoc);874    assert(HashTok && "got inclusion at wrong offset");875    const auto *IncludeTok = std::next(HashTok);876    const auto *FileTok = std::next(IncludeTok);877 878    // The File Token can either be of kind :879    // "less" if using the "#include <h-char-sequence> new-line" syntax880    // "string_literal" if using the "#include "q-char-sequence" new-line"881    // syntax something else (most likely "identifier") if using the "#include882    // pp-tokens new-line" syntax (#include with macro argument)883 884    CharSourceRange FileRange;885 886    if (FileTok->kind() == tok::TokenKind::less) {887      // FileTok->range would only include the '<' char. Hence we explicitly use888      // Inc.Written's length.889      FileRange =890          syntax::FileRange(SM, FileTok->location(), Inc.Written.length())891              .toCharRange(SM);892    } else if (FileTok->kind() == tok::TokenKind::string_literal) {893      // FileTok->range includes the quotes for string literals so just return894      // it.895      FileRange = FileTok->range(SM).toCharRange(SM);896    } else {897      // FileTok is the first Token of a macro spelling898 899      // Report the range of the first token (as it should be the macro900      // identifier)901      // We could use the AST to find the last spelled token of the macro and902      // report a range spanning the full macro expression, but it would require903      // using token-buffers that are deemed too unstable and crash-prone904      // due to optimizations in cland905 906      FileRange = FileTok->range(SM).toCharRange(SM);907    }908 909    Result.push_back(910        DocumentLink({halfOpenToRange(SM, FileRange),911                      URIForFile::canonicalize(Inc.Resolved, AST.tuPath())}));912  }913 914  return Result;915}916 917namespace {918 919/// Collects references to symbols within the main file.920class ReferenceFinder : public index::IndexDataConsumer {921public:922  struct Reference {923    syntax::Token SpelledTok;924    index::SymbolRoleSet Role;925    const Decl *Container;926 927    Range range(const SourceManager &SM) const {928      return halfOpenToRange(SM, SpelledTok.range(SM).toCharRange(SM));929    }930  };931 932  ReferenceFinder(const ParsedAST &AST,933                  const llvm::ArrayRef<const NamedDecl *> Targets,934                  bool PerToken)935      : PerToken(PerToken), AST(AST) {936    for (const NamedDecl *ND : Targets)937      TargetDecls.insert(ND->getCanonicalDecl());938  }939 940  std::vector<Reference> take() && {941    llvm::sort(References, [](const Reference &L, const Reference &R) {942      auto LTok = L.SpelledTok.location();943      auto RTok = R.SpelledTok.location();944      return std::tie(LTok, L.Role) < std::tie(RTok, R.Role);945    });946    // We sometimes see duplicates when parts of the AST get traversed twice.947    References.erase(llvm::unique(References,948                                  [](const Reference &L, const Reference &R) {949                                    auto LTok = L.SpelledTok.location();950                                    auto RTok = R.SpelledTok.location();951                                    return std::tie(LTok, L.Role) ==952                                           std::tie(RTok, R.Role);953                                  }),954                     References.end());955    return std::move(References);956  }957 958  bool959  handleDeclOccurrence(const Decl *D, index::SymbolRoleSet Roles,960                       llvm::ArrayRef<index::SymbolRelation> Relations,961                       SourceLocation Loc,962                       index::IndexDataConsumer::ASTNodeInfo ASTNode) override {963    if (!TargetDecls.contains(D->getCanonicalDecl()))964      return true;965    const SourceManager &SM = AST.getSourceManager();966    if (!isInsideMainFile(Loc, SM))967      return true;968    const auto &TB = AST.getTokens();969 970    llvm::SmallVector<SourceLocation, 1> Locs;971    if (PerToken) {972      // Check whether this is one of the few constructs where the reference973      // can be split over several tokens.974      if (auto *OME = llvm::dyn_cast_or_null<ObjCMessageExpr>(ASTNode.OrigE)) {975        OME->getSelectorLocs(Locs);976      } else if (auto *OMD =977                     llvm::dyn_cast_or_null<ObjCMethodDecl>(ASTNode.OrigD)) {978        OMD->getSelectorLocs(Locs);979      }980      // Sanity check: we expect the *first* token to match the reported loc.981      // Otherwise, maybe it was e.g. some other kind of reference to a Decl.982      if (!Locs.empty() && Locs.front() != Loc)983        Locs.clear(); // First token doesn't match, assume our guess was wrong.984    }985    if (Locs.empty())986      Locs.push_back(Loc);987 988    SymbolCollector::Options CollectorOpts;989    CollectorOpts.CollectMainFileSymbols = true;990    for (SourceLocation L : Locs) {991      L = SM.getFileLoc(L);992      if (const auto *Tok = TB.spelledTokenContaining(L))993        References.push_back(994            {*Tok, Roles,995             SymbolCollector::getRefContainer(ASTNode.Parent, CollectorOpts)});996    }997    return true;998  }999 1000private:1001  bool PerToken; // If true, report 3 references for split ObjC selector names.1002  std::vector<Reference> References;1003  const ParsedAST &AST;1004  llvm::DenseSet<const Decl *> TargetDecls;1005};1006 1007std::vector<ReferenceFinder::Reference>1008findRefs(const llvm::ArrayRef<const NamedDecl *> TargetDecls, ParsedAST &AST,1009         bool PerToken) {1010  ReferenceFinder RefFinder(AST, TargetDecls, PerToken);1011  index::IndexingOptions IndexOpts;1012  IndexOpts.SystemSymbolFilter =1013      index::IndexingOptions::SystemSymbolFilterKind::All;1014  IndexOpts.IndexFunctionLocals = true;1015  IndexOpts.IndexParametersInDeclarations = true;1016  IndexOpts.IndexTemplateParameters = true;1017  indexTopLevelDecls(AST.getASTContext(), AST.getPreprocessor(),1018                     AST.getLocalTopLevelDecls(), RefFinder, IndexOpts);1019  return std::move(RefFinder).take();1020}1021 1022const Stmt *getFunctionBody(DynTypedNode N) {1023  if (const auto *FD = N.get<FunctionDecl>())1024    return FD->getBody();1025  if (const auto *FD = N.get<BlockDecl>())1026    return FD->getBody();1027  if (const auto *FD = N.get<LambdaExpr>())1028    return FD->getBody();1029  if (const auto *FD = N.get<ObjCMethodDecl>())1030    return FD->getBody();1031  return nullptr;1032}1033 1034const Stmt *getLoopBody(DynTypedNode N) {1035  if (const auto *LS = N.get<ForStmt>())1036    return LS->getBody();1037  if (const auto *LS = N.get<CXXForRangeStmt>())1038    return LS->getBody();1039  if (const auto *LS = N.get<WhileStmt>())1040    return LS->getBody();1041  if (const auto *LS = N.get<DoStmt>())1042    return LS->getBody();1043  return nullptr;1044}1045 1046// AST traversal to highlight control flow statements under some root.1047// Once we hit further control flow we prune the tree (or at least restrict1048// what we highlight) so we capture e.g. breaks from the outer loop only.1049class FindControlFlow : public RecursiveASTVisitor<FindControlFlow> {1050  // Types of control-flow statements we might highlight.1051  enum Target {1052    Break = 1,1053    Continue = 2,1054    Return = 4,1055    Case = 8,1056    Throw = 16,1057    Goto = 32,1058    All = Break | Continue | Return | Case | Throw | Goto,1059  };1060  int Ignore = 0;     // bitmask of Target - what are we *not* highlighting?1061  SourceRange Bounds; // Half-open, restricts reported targets.1062  std::vector<SourceLocation> &Result;1063  const SourceManager &SM;1064 1065  // Masks out targets for a traversal into D.1066  // Traverses the subtree using Delegate() if any targets remain.1067  template <typename Func>1068  bool filterAndTraverse(DynTypedNode D, const Func &Delegate) {1069    auto RestoreIgnore = llvm::make_scope_exit(1070        [OldIgnore(Ignore), this] { Ignore = OldIgnore; });1071    if (getFunctionBody(D))1072      Ignore = All;1073    else if (getLoopBody(D))1074      Ignore |= Continue | Break;1075    else if (D.get<SwitchStmt>())1076      Ignore |= Break | Case;1077    // Prune tree if we're not looking for anything.1078    return (Ignore == All) ? true : Delegate();1079  }1080 1081  void found(Target T, SourceLocation Loc) {1082    if (T & Ignore)1083      return;1084    if (SM.isBeforeInTranslationUnit(Loc, Bounds.getBegin()) ||1085        SM.isBeforeInTranslationUnit(Bounds.getEnd(), Loc))1086      return;1087    Result.push_back(Loc);1088  }1089 1090public:1091  FindControlFlow(SourceRange Bounds, std::vector<SourceLocation> &Result,1092                  const SourceManager &SM)1093      : Bounds(Bounds), Result(Result), SM(SM) {}1094 1095  // When traversing function or loops, limit targets to those that still1096  // refer to the original root.1097  bool TraverseDecl(Decl *D) {1098    return !D || filterAndTraverse(DynTypedNode::create(*D), [&] {1099      return RecursiveASTVisitor::TraverseDecl(D);1100    });1101  }1102  bool TraverseStmt(Stmt *S) {1103    return !S || filterAndTraverse(DynTypedNode::create(*S), [&] {1104      return RecursiveASTVisitor::TraverseStmt(S);1105    });1106  }1107 1108  // Add leaves that we found and want.1109  bool VisitReturnStmt(ReturnStmt *R) {1110    found(Return, R->getReturnLoc());1111    return true;1112  }1113  bool VisitBreakStmt(BreakStmt *B) {1114    found(Break, B->getKwLoc());1115    return true;1116  }1117  bool VisitContinueStmt(ContinueStmt *C) {1118    found(Continue, C->getKwLoc());1119    return true;1120  }1121  bool VisitSwitchCase(SwitchCase *C) {1122    found(Case, C->getKeywordLoc());1123    return true;1124  }1125  bool VisitCXXThrowExpr(CXXThrowExpr *T) {1126    found(Throw, T->getThrowLoc());1127    return true;1128  }1129  bool VisitGotoStmt(GotoStmt *G) {1130    // Goto is interesting if its target is outside the root.1131    if (const auto *LD = G->getLabel()) {1132      if (SM.isBeforeInTranslationUnit(LD->getLocation(), Bounds.getBegin()) ||1133          SM.isBeforeInTranslationUnit(Bounds.getEnd(), LD->getLocation()))1134        found(Goto, G->getGotoLoc());1135    }1136    return true;1137  }1138};1139 1140// Given a location within a switch statement, return the half-open range that1141// covers the case it's contained in.1142// We treat `case X: case Y: ...` as one case, and assume no other fallthrough.1143SourceRange findCaseBounds(const SwitchStmt &Switch, SourceLocation Loc,1144                           const SourceManager &SM) {1145  // Cases are not stored in order, sort them first.1146  // (In fact they seem to be stored in reverse order, don't rely on this)1147  std::vector<const SwitchCase *> Cases;1148  for (const SwitchCase *Case = Switch.getSwitchCaseList(); Case;1149       Case = Case->getNextSwitchCase())1150    Cases.push_back(Case);1151  llvm::sort(Cases, [&](const SwitchCase *L, const SwitchCase *R) {1152    return SM.isBeforeInTranslationUnit(L->getKeywordLoc(), R->getKeywordLoc());1153  });1154 1155  // Find the first case after the target location, the end of our range.1156  auto CaseAfter = llvm::partition_point(Cases, [&](const SwitchCase *C) {1157    return !SM.isBeforeInTranslationUnit(Loc, C->getKeywordLoc());1158  });1159  SourceLocation End = CaseAfter == Cases.end() ? Switch.getEndLoc()1160                                                : (*CaseAfter)->getKeywordLoc();1161 1162  // Our target can be before the first case - cases are optional!1163  if (CaseAfter == Cases.begin())1164    return SourceRange(Switch.getBeginLoc(), End);1165  // The start of our range is usually the previous case, but...1166  auto CaseBefore = std::prev(CaseAfter);1167  // ... rewind CaseBefore to the first in a `case A: case B: ...` sequence.1168  while (CaseBefore != Cases.begin() &&1169         (*std::prev(CaseBefore))->getSubStmt() == *CaseBefore)1170    --CaseBefore;1171  return SourceRange((*CaseBefore)->getKeywordLoc(), End);1172}1173 1174// Returns the locations of control flow statements related to N. e.g.:1175//   for    => branches: break/continue/return/throw1176//   break  => controlling loop (forwhile/do), and its related control flow1177//   return => all returns/throws from the same function1178// When an inner block is selected, we include branches bound to outer blocks1179// as these are exits from the inner block. e.g. return in a for loop.1180// FIXME: We don't analyze catch blocks, throw is treated the same as return.1181std::vector<SourceLocation> relatedControlFlow(const SelectionTree::Node &N) {1182  const SourceManager &SM =1183      N.getDeclContext().getParentASTContext().getSourceManager();1184  std::vector<SourceLocation> Result;1185 1186  // First, check if we're at a node that can resolve to a root.1187  enum class Cur { None, Break, Continue, Return, Case, Throw } Cursor;1188  if (N.ASTNode.get<BreakStmt>()) {1189    Cursor = Cur::Break;1190  } else if (N.ASTNode.get<ContinueStmt>()) {1191    Cursor = Cur::Continue;1192  } else if (N.ASTNode.get<ReturnStmt>()) {1193    Cursor = Cur::Return;1194  } else if (N.ASTNode.get<CXXThrowExpr>()) {1195    Cursor = Cur::Throw;1196  } else if (N.ASTNode.get<SwitchCase>()) {1197    Cursor = Cur::Case;1198  } else if (const GotoStmt *GS = N.ASTNode.get<GotoStmt>()) {1199    // We don't know what root to associate with, but highlight the goto/label.1200    Result.push_back(GS->getGotoLoc());1201    if (const auto *LD = GS->getLabel())1202      Result.push_back(LD->getLocation());1203    Cursor = Cur::None;1204  } else {1205    Cursor = Cur::None;1206  }1207 1208  const Stmt *Root = nullptr; // Loop or function body to traverse.1209  SourceRange Bounds;1210  // Look up the tree for a root (or just at this node if we didn't find a leaf)1211  for (const auto *P = &N; P; P = P->Parent) {1212    // return associates with enclosing function1213    if (const Stmt *FunctionBody = getFunctionBody(P->ASTNode)) {1214      if (Cursor == Cur::Return || Cursor == Cur::Throw) {1215        Root = FunctionBody;1216      }1217      break; // other leaves don't cross functions.1218    }1219    // break/continue associate with enclosing loop.1220    if (const Stmt *LoopBody = getLoopBody(P->ASTNode)) {1221      if (Cursor == Cur::None || Cursor == Cur::Break ||1222          Cursor == Cur::Continue) {1223        Root = LoopBody;1224        // Highlight the loop keyword itself.1225        // FIXME: for do-while, this only covers the `do`..1226        Result.push_back(P->ASTNode.getSourceRange().getBegin());1227        break;1228      }1229    }1230    // For switches, users think of case statements as control flow blocks.1231    // We highlight only occurrences surrounded by the same case.1232    // We don't detect fallthrough (other than 'case X, case Y').1233    if (const auto *SS = P->ASTNode.get<SwitchStmt>()) {1234      if (Cursor == Cur::Break || Cursor == Cur::Case) {1235        Result.push_back(SS->getSwitchLoc()); // Highlight the switch.1236        Root = SS->getBody();1237        // Limit to enclosing case, if there is one.1238        Bounds = findCaseBounds(*SS, N.ASTNode.getSourceRange().getBegin(), SM);1239        break;1240      }1241    }1242    // If we didn't start at some interesting node, we're done.1243    if (Cursor == Cur::None)1244      break;1245  }1246  if (Root) {1247    if (!Bounds.isValid())1248      Bounds = Root->getSourceRange();1249    FindControlFlow(Bounds, Result, SM).TraverseStmt(const_cast<Stmt *>(Root));1250  }1251  return Result;1252}1253 1254DocumentHighlight toHighlight(const ReferenceFinder::Reference &Ref,1255                              const SourceManager &SM) {1256  DocumentHighlight DH;1257  DH.range = Ref.range(SM);1258  if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Write))1259    DH.kind = DocumentHighlightKind::Write;1260  else if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Read))1261    DH.kind = DocumentHighlightKind::Read;1262  else1263    DH.kind = DocumentHighlightKind::Text;1264  return DH;1265}1266 1267std::optional<DocumentHighlight> toHighlight(SourceLocation Loc,1268                                             const syntax::TokenBuffer &TB) {1269  Loc = TB.sourceManager().getFileLoc(Loc);1270  if (const auto *Tok = TB.spelledTokenContaining(Loc)) {1271    DocumentHighlight Result;1272    Result.range = halfOpenToRange(1273        TB.sourceManager(),1274        CharSourceRange::getCharRange(Tok->location(), Tok->endLocation()));1275    return Result;1276  }1277  return std::nullopt;1278}1279 1280} // namespace1281 1282std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,1283                                                      Position Pos) {1284  const SourceManager &SM = AST.getSourceManager();1285  // FIXME: show references to macro within file?1286  auto CurLoc = sourceLocationInMainFile(SM, Pos);1287  if (!CurLoc) {1288    llvm::consumeError(CurLoc.takeError());1289    return {};1290  }1291  std::vector<DocumentHighlight> Result;1292  auto TryTree = [&](SelectionTree ST) {1293    if (const SelectionTree::Node *N = ST.commonAncestor()) {1294      DeclRelationSet Relations =1295          DeclRelation::TemplatePattern | DeclRelation::Alias;1296      auto TargetDecls =1297          targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver());1298      if (!TargetDecls.empty()) {1299        // FIXME: we may get multiple DocumentHighlights with the same location1300        // and different kinds, deduplicate them.1301        for (const auto &Ref : findRefs(TargetDecls, AST, /*PerToken=*/true))1302          Result.push_back(toHighlight(Ref, SM));1303        return true;1304      }1305      auto ControlFlow = relatedControlFlow(*N);1306      if (!ControlFlow.empty()) {1307        for (SourceLocation Loc : ControlFlow)1308          if (auto Highlight = toHighlight(Loc, AST.getTokens()))1309            Result.push_back(std::move(*Highlight));1310        return true;1311      }1312    }1313    return false;1314  };1315 1316  unsigned Offset =1317      AST.getSourceManager().getDecomposedSpellingLoc(*CurLoc).second;1318  SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset,1319                            Offset, TryTree);1320  return Result;1321}1322 1323std::vector<LocatedSymbol> findImplementations(ParsedAST &AST, Position Pos,1324                                               const SymbolIndex *Index) {1325  // We rely on index to find the implementations in subclasses.1326  // FIXME: Index can be stale, so we may loose some latest results from the1327  // main file.1328  if (!Index)1329    return {};1330  const SourceManager &SM = AST.getSourceManager();1331  auto CurLoc = sourceLocationInMainFile(SM, Pos);1332  if (!CurLoc) {1333    elog("Failed to convert position to source location: {0}",1334         CurLoc.takeError());1335    return {};1336  }1337  DeclRelationSet Relations =1338      DeclRelation::TemplatePattern | DeclRelation::Alias;1339  llvm::DenseSet<SymbolID> IDs;1340  RelationKind QueryKind = RelationKind::OverriddenBy;1341  for (const NamedDecl *ND : getDeclAtPosition(AST, *CurLoc, Relations)) {1342    if (const auto *CXXMD = llvm::dyn_cast<CXXMethodDecl>(ND)) {1343      if (CXXMD->isVirtual()) {1344        IDs.insert(getSymbolID(ND));1345        QueryKind = RelationKind::OverriddenBy;1346      }1347    } else if (const auto *RD = dyn_cast<CXXRecordDecl>(ND)) {1348      IDs.insert(getSymbolID(RD));1349      QueryKind = RelationKind::BaseOf;1350    } else if (const auto *OMD = dyn_cast<ObjCMethodDecl>(ND)) {1351      IDs.insert(getSymbolID(OMD));1352      QueryKind = RelationKind::OverriddenBy;1353    } else if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(ND)) {1354      IDs.insert(getSymbolID(ID));1355      QueryKind = RelationKind::BaseOf;1356    }1357  }1358  return findImplementors(std::move(IDs), QueryKind, Index, AST.tuPath());1359}1360 1361namespace {1362// Recursively finds all the overridden methods of `CMD` in complete type1363// hierarchy.1364void getOverriddenMethods(const CXXMethodDecl *CMD,1365                          llvm::DenseSet<SymbolID> &OverriddenMethods) {1366  if (!CMD)1367    return;1368  for (const CXXMethodDecl *Base : CMD->overridden_methods()) {1369    if (auto ID = getSymbolID(Base))1370      OverriddenMethods.insert(ID);1371    getOverriddenMethods(Base, OverriddenMethods);1372  }1373}1374 1375// Recursively finds all the overridden methods of `OMD` in complete type1376// hierarchy.1377void getOverriddenMethods(const ObjCMethodDecl *OMD,1378                          llvm::DenseSet<SymbolID> &OverriddenMethods) {1379  if (!OMD)1380    return;1381  llvm::SmallVector<const ObjCMethodDecl *, 4> Overrides;1382  OMD->getOverriddenMethods(Overrides);1383  for (const ObjCMethodDecl *Base : Overrides) {1384    if (auto ID = getSymbolID(Base))1385      OverriddenMethods.insert(ID);1386    getOverriddenMethods(Base, OverriddenMethods);1387  }1388}1389 1390std::optional<std::string>1391stringifyContainerForMainFileRef(const Decl *Container) {1392  // FIXME We might also want to display the signature here1393  // When doing so, remember to also add the Signature to index results!1394  if (auto *ND = llvm::dyn_cast_if_present<NamedDecl>(Container))1395    return printQualifiedName(*ND);1396  return {};1397}1398 1399std::optional<ReferencesResult>1400maybeFindIncludeReferences(ParsedAST &AST, Position Pos,1401                           URIForFile URIMainFile) {1402  const auto &Includes = AST.getIncludeStructure().MainFileIncludes;1403  auto IncludeOnLine = llvm::find_if(Includes, [&Pos](const Inclusion &Inc) {1404    return Inc.HashLine == Pos.line;1405  });1406  if (IncludeOnLine == Includes.end())1407    return std::nullopt;1408 1409  const SourceManager &SM = AST.getSourceManager();1410  ReferencesResult Results;1411  auto Converted = convertIncludes(AST);1412  include_cleaner::walkUsed(1413      AST.getLocalTopLevelDecls(), collectMacroReferences(AST),1414      &AST.getPragmaIncludes(), AST.getPreprocessor(),1415      [&](const include_cleaner::SymbolReference &Ref,1416          llvm::ArrayRef<include_cleaner::Header> Providers) {1417        if (Ref.RT != include_cleaner::RefType::Explicit ||1418            !isPreferredProvider(*IncludeOnLine, Converted, Providers))1419          return;1420 1421        auto Loc = SM.getFileLoc(Ref.RefLocation);1422        // File locations can be outside of the main file if macro is1423        // expanded through an #include.1424        while (SM.getFileID(Loc) != SM.getMainFileID())1425          Loc = SM.getIncludeLoc(SM.getFileID(Loc));1426 1427        ReferencesResult::Reference Result;1428        const auto *Token = AST.getTokens().spelledTokenContaining(Loc);1429        assert(Token && "references expected token here");1430        Result.Loc.range = Range{sourceLocToPosition(SM, Token->location()),1431                                 sourceLocToPosition(SM, Token->endLocation())};1432        Result.Loc.uri = URIMainFile;1433        Results.References.push_back(std::move(Result));1434      });1435  if (Results.References.empty())1436    return std::nullopt;1437 1438  // Add the #include line to the references list.1439  ReferencesResult::Reference Result;1440  Result.Loc.range = rangeTillEOL(SM.getBufferData(SM.getMainFileID()),1441                                  IncludeOnLine->HashOffset);1442  Result.Loc.uri = URIMainFile;1443  Results.References.push_back(std::move(Result));1444  return Results;1445}1446} // namespace1447 1448ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit,1449                                const SymbolIndex *Index, bool AddContext) {1450  ReferencesResult Results;1451  const SourceManager &SM = AST.getSourceManager();1452  auto MainFilePath = AST.tuPath();1453  auto URIMainFile = URIForFile::canonicalize(MainFilePath, MainFilePath);1454  auto CurLoc = sourceLocationInMainFile(SM, Pos);1455  if (!CurLoc) {1456    llvm::consumeError(CurLoc.takeError());1457    return {};1458  }1459 1460  const auto IncludeReferences =1461      maybeFindIncludeReferences(AST, Pos, URIMainFile);1462  if (IncludeReferences)1463    return *IncludeReferences;1464 1465  llvm::DenseSet<SymbolID> IDsToQuery, OverriddenMethods;1466 1467  const auto *IdentifierAtCursor =1468      syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens());1469  std::optional<DefinedMacro> Macro;1470  if (IdentifierAtCursor)1471    Macro = locateMacroAt(*IdentifierAtCursor, AST.getPreprocessor());1472  if (Macro) {1473    // Handle references to macro.1474    if (auto MacroSID = getSymbolID(Macro->Name, Macro->Info, SM)) {1475      // Collect macro references from main file.1476      const auto &IDToRefs = AST.getMacros().MacroRefs;1477      auto Refs = IDToRefs.find(MacroSID);1478      if (Refs != IDToRefs.end()) {1479        for (const auto &Ref : Refs->second) {1480          ReferencesResult::Reference Result;1481          Result.Loc.range = Ref.toRange(SM);1482          Result.Loc.uri = URIMainFile;1483          if (Ref.IsDefinition) {1484            Result.Attributes |= ReferencesResult::Declaration;1485            Result.Attributes |= ReferencesResult::Definition;1486          }1487          Results.References.push_back(std::move(Result));1488        }1489      }1490      IDsToQuery.insert(MacroSID);1491    }1492  } else {1493    // Handle references to Decls.1494 1495    DeclRelationSet Relations =1496        DeclRelation::TemplatePattern | DeclRelation::Alias;1497    std::vector<const NamedDecl *> Decls =1498        getDeclAtPosition(AST, *CurLoc, Relations);1499    llvm::SmallVector<const NamedDecl *> TargetsInMainFile;1500    for (const NamedDecl *D : Decls) {1501      auto ID = getSymbolID(D);1502      if (!ID)1503        continue;1504      TargetsInMainFile.push_back(D);1505      // Not all symbols can be referenced from outside (e.g. function-locals).1506      // TODO: we could skip TU-scoped symbols here (e.g. static functions) if1507      // we know this file isn't a header. The details might be tricky.1508      if (D->getParentFunctionOrMethod())1509        continue;1510      IDsToQuery.insert(ID);1511    }1512 1513    RelationsRequest OverriddenBy;1514    if (Index) {1515      OverriddenBy.Predicate = RelationKind::OverriddenBy;1516      for (const NamedDecl *ND : Decls) {1517        // Special case: For virtual methods, report decl/def of overrides and1518        // references to all overridden methods in complete type hierarchy.1519        if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(ND)) {1520          if (CMD->isVirtual()) {1521            if (auto ID = getSymbolID(CMD))1522              OverriddenBy.Subjects.insert(ID);1523            getOverriddenMethods(CMD, OverriddenMethods);1524          }1525        }1526        // Special case: Objective-C methods can override a parent class or1527        // protocol, we should be sure to report references to those.1528        if (const auto *OMD = llvm::dyn_cast<ObjCMethodDecl>(ND)) {1529          OverriddenBy.Subjects.insert(getSymbolID(OMD));1530          getOverriddenMethods(OMD, OverriddenMethods);1531        }1532      }1533    }1534 1535    // We traverse the AST to find references in the main file.1536    auto MainFileRefs = findRefs(TargetsInMainFile, AST, /*PerToken=*/false);1537    // We may get multiple refs with the same location and different Roles, as1538    // cross-reference is only interested in locations, we deduplicate them1539    // by the location to avoid emitting duplicated locations.1540    MainFileRefs.erase(llvm::unique(MainFileRefs,1541                                    [](const ReferenceFinder::Reference &L,1542                                       const ReferenceFinder::Reference &R) {1543                                      return L.SpelledTok.location() ==1544                                             R.SpelledTok.location();1545                                    }),1546                       MainFileRefs.end());1547    for (const auto &Ref : MainFileRefs) {1548      ReferencesResult::Reference Result;1549      Result.Loc.range = Ref.range(SM);1550      Result.Loc.uri = URIMainFile;1551      if (AddContext)1552        Result.Loc.containerName =1553            stringifyContainerForMainFileRef(Ref.Container);1554      if (Ref.Role & static_cast<unsigned>(index::SymbolRole::Declaration))1555        Result.Attributes |= ReferencesResult::Declaration;1556      // clang-index doesn't report definitions as declarations, but they are.1557      if (Ref.Role & static_cast<unsigned>(index::SymbolRole::Definition))1558        Result.Attributes |=1559            ReferencesResult::Definition | ReferencesResult::Declaration;1560      Results.References.push_back(std::move(Result));1561    }1562    // Add decl/def of overridding methods.1563    if (Index && !OverriddenBy.Subjects.empty()) {1564      LookupRequest ContainerLookup;1565      // Different overrides will always be contained in different classes, so1566      // we have a one-to-one mapping between SymbolID and index here, thus we1567      // don't need to use std::vector as the map's value type.1568      llvm::DenseMap<SymbolID, size_t> RefIndexForContainer;1569      Index->relations(OverriddenBy, [&](const SymbolID &Subject,1570                                         const Symbol &Object) {1571        if (Limit && Results.References.size() >= Limit) {1572          Results.HasMore = true;1573          return;1574        }1575        const auto LSPLocDecl =1576            toLSPLocation(Object.CanonicalDeclaration, MainFilePath);1577        const auto LSPLocDef = toLSPLocation(Object.Definition, MainFilePath);1578        if (LSPLocDecl && LSPLocDecl != LSPLocDef) {1579          ReferencesResult::Reference Result;1580          Result.Loc = {std::move(*LSPLocDecl), std::nullopt};1581          Result.Attributes =1582              ReferencesResult::Declaration | ReferencesResult::Override;1583          RefIndexForContainer.insert({Object.ID, Results.References.size()});1584          ContainerLookup.IDs.insert(Object.ID);1585          Results.References.push_back(std::move(Result));1586        }1587        if (LSPLocDef) {1588          ReferencesResult::Reference Result;1589          Result.Loc = {std::move(*LSPLocDef), std::nullopt};1590          Result.Attributes = ReferencesResult::Declaration |1591                              ReferencesResult::Definition |1592                              ReferencesResult::Override;1593          RefIndexForContainer.insert({Object.ID, Results.References.size()});1594          ContainerLookup.IDs.insert(Object.ID);1595          Results.References.push_back(std::move(Result));1596        }1597      });1598 1599      if (!ContainerLookup.IDs.empty() && AddContext)1600        Index->lookup(ContainerLookup, [&](const Symbol &Container) {1601          auto Ref = RefIndexForContainer.find(Container.ID);1602          assert(Ref != RefIndexForContainer.end());1603          Results.References[Ref->getSecond()].Loc.containerName =1604              Container.Scope.str() + Container.Name.str();1605        });1606    }1607  }1608  // Now query the index for references from other files.1609  auto QueryIndex = [&](llvm::DenseSet<SymbolID> IDs, bool AllowAttributes,1610                        bool AllowMainFileSymbols) {1611    if (IDs.empty() || !Index || Results.HasMore)1612      return;1613    RefsRequest Req;1614    Req.IDs = std::move(IDs);1615    if (Limit) {1616      if (Limit < Results.References.size()) {1617        // We've already filled our quota, still check the index to correctly1618        // return the `HasMore` info.1619        Req.Limit = 0;1620      } else {1621        // Query index only for the remaining size.1622        Req.Limit = Limit - Results.References.size();1623      }1624    }1625    LookupRequest ContainerLookup;1626    llvm::DenseMap<SymbolID, std::vector<size_t>> RefIndicesForContainer;1627    Results.HasMore |= Index->refs(Req, [&](const Ref &R) {1628      auto LSPLoc = toLSPLocation(R.Location, MainFilePath);1629      // Avoid indexed results for the main file - the AST is authoritative.1630      if (!LSPLoc ||1631          (!AllowMainFileSymbols && LSPLoc->uri.file() == MainFilePath))1632        return;1633      ReferencesResult::Reference Result;1634      Result.Loc = {std::move(*LSPLoc), std::nullopt};1635      if (AllowAttributes) {1636        if ((R.Kind & RefKind::Declaration) == RefKind::Declaration)1637          Result.Attributes |= ReferencesResult::Declaration;1638        // FIXME: our index should definitely store def | decl separately!1639        if ((R.Kind & RefKind::Definition) == RefKind::Definition)1640          Result.Attributes |=1641              ReferencesResult::Declaration | ReferencesResult::Definition;1642      }1643      if (AddContext) {1644        SymbolID Container = R.Container;1645        ContainerLookup.IDs.insert(Container);1646        RefIndicesForContainer[Container].push_back(Results.References.size());1647      }1648      Results.References.push_back(std::move(Result));1649    });1650 1651    if (!ContainerLookup.IDs.empty() && AddContext)1652      Index->lookup(ContainerLookup, [&](const Symbol &Container) {1653        auto Ref = RefIndicesForContainer.find(Container.ID);1654        assert(Ref != RefIndicesForContainer.end());1655        auto ContainerName = Container.Scope.str() + Container.Name.str();1656        for (auto I : Ref->getSecond()) {1657          Results.References[I].Loc.containerName = ContainerName;1658        }1659      });1660  };1661  QueryIndex(std::move(IDsToQuery), /*AllowAttributes=*/true,1662             /*AllowMainFileSymbols=*/false);1663  // For a virtual method: Occurrences of BaseMethod should be treated as refs1664  // and not as decl/def. Allow symbols from main file since AST does not report1665  // these.1666  QueryIndex(std::move(OverriddenMethods), /*AllowAttributes=*/false,1667             /*AllowMainFileSymbols=*/true);1668  return Results;1669}1670 1671std::vector<SymbolDetails> getSymbolInfo(ParsedAST &AST, Position Pos) {1672  const SourceManager &SM = AST.getSourceManager();1673  auto CurLoc = sourceLocationInMainFile(SM, Pos);1674  if (!CurLoc) {1675    llvm::consumeError(CurLoc.takeError());1676    return {};1677  }1678  auto MainFilePath = AST.tuPath();1679  std::vector<SymbolDetails> Results;1680 1681  // We also want the targets of using-decls, so we include1682  // DeclRelation::Underlying.1683  DeclRelationSet Relations = DeclRelation::TemplatePattern |1684                              DeclRelation::Alias | DeclRelation::Underlying;1685  for (const NamedDecl *D : getDeclAtPosition(AST, *CurLoc, Relations)) {1686    D = getPreferredDecl(D);1687 1688    SymbolDetails NewSymbol;1689    std::string QName = printQualifiedName(*D);1690    auto SplitQName = splitQualifiedName(QName);1691    NewSymbol.containerName = std::string(SplitQName.first);1692    NewSymbol.name = std::string(SplitQName.second);1693 1694    if (NewSymbol.containerName.empty()) {1695      if (const auto *ParentND =1696              dyn_cast_or_null<NamedDecl>(D->getDeclContext()))1697        NewSymbol.containerName = printQualifiedName(*ParentND);1698    }1699    llvm::SmallString<32> USR;1700    if (!index::generateUSRForDecl(D, USR)) {1701      NewSymbol.USR = std::string(USR);1702      NewSymbol.ID = SymbolID(NewSymbol.USR);1703    }1704    if (const NamedDecl *Def = getDefinition(D))1705      NewSymbol.definitionRange = makeLocation(1706          AST.getASTContext(), nameLocation(*Def, SM), MainFilePath);1707    NewSymbol.declarationRange =1708        makeLocation(AST.getASTContext(), nameLocation(*D, SM), MainFilePath);1709 1710    Results.push_back(std::move(NewSymbol));1711  }1712 1713  const auto *IdentifierAtCursor =1714      syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens());1715  if (!IdentifierAtCursor)1716    return Results;1717 1718  if (auto M = locateMacroAt(*IdentifierAtCursor, AST.getPreprocessor())) {1719    SymbolDetails NewMacro;1720    NewMacro.name = std::string(M->Name);1721    llvm::SmallString<32> USR;1722    if (!index::generateUSRForMacro(NewMacro.name, M->Info->getDefinitionLoc(),1723                                    SM, USR)) {1724      NewMacro.USR = std::string(USR);1725      NewMacro.ID = SymbolID(NewMacro.USR);1726    }1727    Results.push_back(std::move(NewMacro));1728  }1729 1730  return Results;1731}1732 1733llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LocatedSymbol &S) {1734  OS << S.Name << ": " << S.PreferredDeclaration;1735  if (S.Definition)1736    OS << " def=" << *S.Definition;1737  return OS;1738}1739 1740llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,1741                              const ReferencesResult::Reference &R) {1742  OS << R.Loc;1743  if (R.Attributes & ReferencesResult::Declaration)1744    OS << " [decl]";1745  if (R.Attributes & ReferencesResult::Definition)1746    OS << " [def]";1747  if (R.Attributes & ReferencesResult::Override)1748    OS << " [override]";1749  return OS;1750}1751 1752template <typename HierarchyItem>1753static std::optional<HierarchyItem>1754declToHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) {1755  ASTContext &Ctx = ND.getASTContext();1756  auto &SM = Ctx.getSourceManager();1757  SourceLocation NameLoc = nameLocation(ND, Ctx.getSourceManager());1758  SourceLocation BeginLoc = SM.getFileLoc(ND.getBeginLoc());1759  SourceLocation EndLoc = SM.getFileLoc(ND.getEndLoc());1760  const auto DeclRange =1761      toHalfOpenFileRange(SM, Ctx.getLangOpts(), {BeginLoc, EndLoc});1762  if (!DeclRange)1763    return std::nullopt;1764  const auto FE = SM.getFileEntryRefForID(SM.getFileID(NameLoc));1765  if (!FE)1766    return std::nullopt;1767  auto FilePath = getCanonicalPath(*FE, SM.getFileManager());1768  if (!FilePath)1769    return std::nullopt; // Not useful without a uri.1770 1771  Position NameBegin = sourceLocToPosition(SM, NameLoc);1772  Position NameEnd = sourceLocToPosition(1773      SM, Lexer::getLocForEndOfToken(NameLoc, 0, SM, Ctx.getLangOpts()));1774 1775  index::SymbolInfo SymInfo = index::getSymbolInfo(&ND);1776  // FIXME: This is not classifying constructors, destructors and operators1777  // correctly.1778  SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind);1779 1780  HierarchyItem HI;1781  HI.name = printName(Ctx, ND);1782  // FIXME: Populate HI.detail the way we do in symbolToHierarchyItem?1783  HI.kind = SK;1784  HI.range = Range{sourceLocToPosition(SM, DeclRange->getBegin()),1785                   sourceLocToPosition(SM, DeclRange->getEnd())};1786  HI.selectionRange = Range{NameBegin, NameEnd};1787  if (!HI.range.contains(HI.selectionRange)) {1788    // 'selectionRange' must be contained in 'range', so in cases where clang1789    // reports unrelated ranges we need to reconcile somehow.1790    HI.range = HI.selectionRange;1791  }1792 1793  HI.uri = URIForFile::canonicalize(*FilePath, TUPath);1794 1795  return HI;1796}1797 1798static std::optional<TypeHierarchyItem>1799declToTypeHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) {1800  auto Result = declToHierarchyItem<TypeHierarchyItem>(ND, TUPath);1801  if (Result) {1802    Result->deprecated = ND.isDeprecated();1803    // Compute the SymbolID and store it in the 'data' field.1804    // This allows typeHierarchy/resolve to be used to1805    // resolve children of items returned in a previous request1806    // for parents.1807    Result->data.symbolID = getSymbolID(&ND);1808  }1809  return Result;1810}1811 1812static std::optional<CallHierarchyItem>1813declToCallHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) {1814  auto Result = declToHierarchyItem<CallHierarchyItem>(ND, TUPath);1815  if (!Result)1816    return Result;1817  if (ND.isDeprecated())1818    Result->tags.push_back(SymbolTag::Deprecated);1819  if (auto ID = getSymbolID(&ND))1820    Result->data = ID.str();1821  return Result;1822}1823 1824template <typename HierarchyItem>1825static std::optional<HierarchyItem> symbolToHierarchyItem(const Symbol &S,1826                                                          PathRef TUPath) {1827  auto Loc = symbolToLocation(S, TUPath);1828  if (!Loc) {1829    elog("Failed to convert symbol to hierarchy item: {0}", Loc.takeError());1830    return std::nullopt;1831  }1832  HierarchyItem HI;1833  HI.name = std::string(S.Name);1834  HI.detail = (S.Scope + S.Name).str();1835  HI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);1836  HI.selectionRange = Loc->range;1837  // FIXME: Populate 'range' correctly1838  // (https://github.com/clangd/clangd/issues/59).1839  HI.range = HI.selectionRange;1840  HI.uri = Loc->uri;1841 1842  return HI;1843}1844 1845static std::optional<TypeHierarchyItem>1846symbolToTypeHierarchyItem(const Symbol &S, PathRef TUPath) {1847  auto Result = symbolToHierarchyItem<TypeHierarchyItem>(S, TUPath);1848  if (Result) {1849    Result->deprecated = (S.Flags & Symbol::Deprecated);1850    Result->data.symbolID = S.ID;1851  }1852  return Result;1853}1854 1855static std::optional<CallHierarchyItem>1856symbolToCallHierarchyItem(const Symbol &S, PathRef TUPath) {1857  auto Result = symbolToHierarchyItem<CallHierarchyItem>(S, TUPath);1858  if (!Result)1859    return Result;1860  Result->data = S.ID.str();1861  if (S.Flags & Symbol::Deprecated)1862    Result->tags.push_back(SymbolTag::Deprecated);1863  return Result;1864}1865 1866static void fillSubTypes(const SymbolID &ID,1867                         std::vector<TypeHierarchyItem> &SubTypes,1868                         const SymbolIndex *Index, int Levels, PathRef TUPath) {1869  RelationsRequest Req;1870  Req.Subjects.insert(ID);1871  Req.Predicate = RelationKind::BaseOf;1872  Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {1873    if (std::optional<TypeHierarchyItem> ChildSym =1874            symbolToTypeHierarchyItem(Object, TUPath)) {1875      if (Levels > 1) {1876        ChildSym->children.emplace();1877        fillSubTypes(Object.ID, *ChildSym->children, Index, Levels - 1, TUPath);1878      }1879      SubTypes.emplace_back(std::move(*ChildSym));1880    }1881  });1882}1883 1884using RecursionProtectionSet = llvm::SmallPtrSet<const CXXRecordDecl *, 4>;1885 1886// Extracts parents from AST and populates the type hierarchy item.1887static void fillSuperTypes(const CXXRecordDecl &CXXRD, llvm::StringRef TUPath,1888                           TypeHierarchyItem &Item,1889                           RecursionProtectionSet &RPSet) {1890  Item.parents.emplace();1891  Item.data.parents.emplace();1892  // typeParents() will replace dependent template specializations1893  // with their class template, so to avoid infinite recursion for1894  // certain types of hierarchies, keep the templates encountered1895  // along the parent chain in a set, and stop the recursion if one1896  // starts to repeat.1897  auto *Pattern = CXXRD.getDescribedTemplate() ? &CXXRD : nullptr;1898  if (Pattern) {1899    if (!RPSet.insert(Pattern).second) {1900      return;1901    }1902  }1903 1904  for (const CXXRecordDecl *ParentDecl : typeParents(&CXXRD)) {1905    if (std::optional<TypeHierarchyItem> ParentSym =1906            declToTypeHierarchyItem(*ParentDecl, TUPath)) {1907      fillSuperTypes(*ParentDecl, TUPath, *ParentSym, RPSet);1908      Item.data.parents->emplace_back(ParentSym->data);1909      Item.parents->emplace_back(std::move(*ParentSym));1910    }1911  }1912 1913  if (Pattern) {1914    RPSet.erase(Pattern);1915  }1916}1917 1918std::vector<const CXXRecordDecl *> findRecordTypeAt(ParsedAST &AST,1919                                                    Position Pos) {1920  auto RecordFromNode = [&AST](const SelectionTree::Node *N) {1921    std::vector<const CXXRecordDecl *> Records;1922    if (!N)1923      return Records;1924 1925    // Note: explicitReferenceTargets() will search for both template1926    // instantiations and template patterns, and prefer the former if available1927    // (generally, one will be available for non-dependent specializations of a1928    // class template).1929    auto Decls = explicitReferenceTargets(N->ASTNode, DeclRelation::Underlying,1930                                          AST.getHeuristicResolver());1931    for (const NamedDecl *D : Decls) {1932 1933      if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {1934        // If this is a variable, use the type of the variable.1935        if (const auto *RD = VD->getType().getTypePtr()->getAsCXXRecordDecl())1936          Records.push_back(RD);1937        continue;1938      }1939 1940      if (const CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(D)) {1941        // If this is a method, use the type of the class.1942        Records.push_back(Method->getParent());1943        continue;1944      }1945 1946      // We don't handle FieldDecl because it's not clear what behaviour1947      // the user would expect: the enclosing class type (as with a1948      // method), or the field's type (as with a variable).1949 1950      if (auto *RD = dyn_cast<CXXRecordDecl>(D))1951        Records.push_back(RD);1952    }1953    return Records;1954  };1955 1956  const SourceManager &SM = AST.getSourceManager();1957  std::vector<const CXXRecordDecl *> Result;1958  auto Offset = positionToOffset(SM.getBufferData(SM.getMainFileID()), Pos);1959  if (!Offset) {1960    llvm::consumeError(Offset.takeError());1961    return Result;1962  }1963  SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), *Offset,1964                            *Offset, [&](SelectionTree ST) {1965                              Result = RecordFromNode(ST.commonAncestor());1966                              return !Result.empty();1967                            });1968  return Result;1969}1970 1971// Return the type most associated with an AST node.1972// This isn't precisely defined: we want "go to type" to do something useful.1973static QualType typeForNode(const ASTContext &Ctx, const HeuristicResolver *H,1974                            const SelectionTree::Node *N) {1975  // If we're looking at a namespace qualifier, walk up to what it's qualifying.1976  // (If we're pointing at a *class* inside a NNS, N will be a TypeLoc).1977  while (N && N->ASTNode.get<NestedNameSpecifierLoc>())1978    N = N->Parent;1979  if (!N)1980    return QualType();1981 1982  // If we're pointing at a type => return it.1983  if (const TypeLoc *TL = N->ASTNode.get<TypeLoc>()) {1984    if (llvm::isa<DeducedType>(TL->getTypePtr()))1985      if (auto Deduced = getDeducedType(1986              N->getDeclContext().getParentASTContext(), H, TL->getBeginLoc()))1987        return *Deduced;1988    // Exception: an alias => underlying type.1989    if (llvm::isa<TypedefType>(TL->getTypePtr()))1990      return TL->getTypePtr()->getLocallyUnqualifiedSingleStepDesugaredType();1991    return TL->getType();1992  }1993 1994  // Constructor initializers => the type of thing being initialized.1995  if (const auto *CCI = N->ASTNode.get<CXXCtorInitializer>()) {1996    if (const FieldDecl *FD = CCI->getAnyMember())1997      return FD->getType();1998    if (const Type *Base = CCI->getBaseClass())1999      return QualType(Base, 0);2000  }2001 2002  // Base specifier => the base type.2003  if (const auto *CBS = N->ASTNode.get<CXXBaseSpecifier>())2004    return CBS->getType();2005 2006  if (const Decl *D = N->ASTNode.get<Decl>()) {2007    struct Visitor : ConstDeclVisitor<Visitor, QualType> {2008      const ASTContext &Ctx;2009      Visitor(const ASTContext &Ctx) : Ctx(Ctx) {}2010 2011      QualType VisitValueDecl(const ValueDecl *D) { return D->getType(); }2012      // Declaration of a type => that type.2013      QualType VisitTypeDecl(const TypeDecl *D) {2014        return Ctx.getTypeDeclType(D);2015      }2016      // Exception: alias declaration => the underlying type, not the alias.2017      QualType VisitTypedefNameDecl(const TypedefNameDecl *D) {2018        return D->getUnderlyingType();2019      }2020      // Look inside templates.2021      QualType VisitTemplateDecl(const TemplateDecl *D) {2022        return Visit(D->getTemplatedDecl());2023      }2024    } V(Ctx);2025    return V.Visit(D);2026  }2027 2028  if (const Stmt *S = N->ASTNode.get<Stmt>()) {2029    struct Visitor : ConstStmtVisitor<Visitor, QualType> {2030      // Null-safe version of visit simplifies recursive calls below.2031      QualType type(const Stmt *S) { return S ? Visit(S) : QualType(); }2032 2033      // In general, expressions => type of expression.2034      QualType VisitExpr(const Expr *S) {2035        return S->IgnoreImplicitAsWritten()->getType();2036      }2037      QualType VisitMemberExpr(const MemberExpr *S) {2038        // The `foo` in `s.foo()` pretends not to have a real type!2039        if (S->getType()->isSpecificBuiltinType(BuiltinType::BoundMember))2040          return Expr::findBoundMemberType(S);2041        return VisitExpr(S);2042      }2043      // Exceptions for void expressions that operate on a type in some way.2044      QualType VisitCXXDeleteExpr(const CXXDeleteExpr *S) {2045        return S->getDestroyedType();2046      }2047      QualType VisitCXXPseudoDestructorExpr(const CXXPseudoDestructorExpr *S) {2048        return S->getDestroyedType();2049      }2050      QualType VisitCXXThrowExpr(const CXXThrowExpr *S) {2051        return S->getSubExpr()->getType();2052      }2053      QualType VisitCoyieldExpr(const CoyieldExpr *S) {2054        return type(S->getOperand());2055      }2056      // Treat a designated initializer like a reference to the field.2057      QualType VisitDesignatedInitExpr(const DesignatedInitExpr *S) {2058        // In .foo.bar we want to jump to bar's type, so find *last* field.2059        for (auto &D : llvm::reverse(S->designators()))2060          if (D.isFieldDesignator())2061            if (const auto *FD = D.getFieldDecl())2062              return FD->getType();2063        return QualType();2064      }2065 2066      // Control flow statements that operate on data: use the data type.2067      QualType VisitSwitchStmt(const SwitchStmt *S) {2068        return type(S->getCond());2069      }2070      QualType VisitWhileStmt(const WhileStmt *S) { return type(S->getCond()); }2071      QualType VisitDoStmt(const DoStmt *S) { return type(S->getCond()); }2072      QualType VisitIfStmt(const IfStmt *S) { return type(S->getCond()); }2073      QualType VisitCaseStmt(const CaseStmt *S) { return type(S->getLHS()); }2074      QualType VisitCXXForRangeStmt(const CXXForRangeStmt *S) {2075        return S->getLoopVariable()->getType();2076      }2077      QualType VisitReturnStmt(const ReturnStmt *S) {2078        return type(S->getRetValue());2079      }2080      QualType VisitCoreturnStmt(const CoreturnStmt *S) {2081        return type(S->getOperand());2082      }2083      QualType VisitCXXCatchStmt(const CXXCatchStmt *S) {2084        return S->getCaughtType();2085      }2086      QualType VisitObjCAtThrowStmt(const ObjCAtThrowStmt *S) {2087        return type(S->getThrowExpr());2088      }2089      QualType VisitObjCAtCatchStmt(const ObjCAtCatchStmt *S) {2090        return S->getCatchParamDecl() ? S->getCatchParamDecl()->getType()2091                                      : QualType();2092      }2093    } V;2094    return V.Visit(S);2095  }2096 2097  return QualType();2098}2099 2100// Given a type targeted by the cursor, return one or more types that are more interesting2101// to target.2102static void unwrapFindType(2103    QualType T, const HeuristicResolver* H, llvm::SmallVector<QualType>& Out) {2104  if (T.isNull())2105    return;2106 2107  // If there's a specific type alias, point at that rather than unwrapping.2108  if (const auto* TDT = T->getAs<TypedefType>())2109    return Out.push_back(QualType(TDT, 0));2110 2111  // Pointers etc => pointee type.2112  if (const auto *PT = T->getAs<PointerType>())2113    return unwrapFindType(PT->getPointeeType(), H, Out);2114  if (const auto *RT = T->getAs<ReferenceType>())2115    return unwrapFindType(RT->getPointeeType(), H, Out);2116  if (const auto *AT = T->getAsArrayTypeUnsafe())2117    return unwrapFindType(AT->getElementType(), H, Out);2118 2119  // Function type => return type.2120  if (auto *FT = T->getAs<FunctionType>())2121    return unwrapFindType(FT->getReturnType(), H, Out);2122  if (auto *CRD = T->getAsCXXRecordDecl()) {2123    if (CRD->isLambda())2124      return unwrapFindType(CRD->getLambdaCallOperator()->getReturnType(), H,2125                            Out);2126    // FIXME: more cases we'd prefer the return type of the call operator?2127    //        std::function etc?2128  }2129 2130  // For smart pointer types, add the underlying type2131  if (H)2132    if (auto PointeeType = H->getPointeeType(T.getNonReferenceType());2133        !PointeeType.isNull()) {2134      unwrapFindType(PointeeType, H, Out);2135      return Out.push_back(T);2136    }2137 2138  return Out.push_back(T);2139}2140 2141// Convenience overload, to allow calling this without the out-parameter2142static llvm::SmallVector<QualType> unwrapFindType(2143    QualType T, const HeuristicResolver* H) {2144  llvm::SmallVector<QualType> Result;2145  unwrapFindType(T, H, Result);2146  return Result;2147}2148 2149std::vector<LocatedSymbol> findType(ParsedAST &AST, Position Pos,2150                                    const SymbolIndex *Index) {2151  const SourceManager &SM = AST.getSourceManager();2152  auto Offset = positionToOffset(SM.getBufferData(SM.getMainFileID()), Pos);2153  std::vector<LocatedSymbol> Result;2154  if (!Offset) {2155    elog("failed to convert position {0} for findTypes: {1}", Pos,2156         Offset.takeError());2157    return Result;2158  }2159  // The general scheme is: position -> AST node -> type -> declaration.2160  auto SymbolsFromNode =2161      [&](const SelectionTree::Node *N) -> std::vector<LocatedSymbol> {2162    std::vector<LocatedSymbol> LocatedSymbols;2163 2164    // NOTE: unwrapFindType might return duplicates for something like2165    // unique_ptr<unique_ptr<T>>. Let's *not* remove them, because it gives you some2166    // information about the type you may have not known before2167    // (since unique_ptr<unique_ptr<T>> != unique_ptr<T>).2168    for (const QualType &Type : unwrapFindType(2169             typeForNode(AST.getASTContext(), AST.getHeuristicResolver(), N),2170             AST.getHeuristicResolver()))2171      llvm::copy(locateSymbolForType(AST, Type, Index),2172                 std::back_inserter(LocatedSymbols));2173 2174    return LocatedSymbols;2175  };2176  SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), *Offset,2177                            *Offset, [&](SelectionTree ST) {2178                              Result = SymbolsFromNode(ST.commonAncestor());2179                              return !Result.empty();2180                            });2181  return Result;2182}2183 2184std::vector<const CXXRecordDecl *> typeParents(const CXXRecordDecl *CXXRD) {2185  std::vector<const CXXRecordDecl *> Result;2186 2187  // If this is an invalid instantiation, instantiation of the bases2188  // may not have succeeded, so fall back to the template pattern.2189  if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD)) {2190    if (CTSD->isInvalidDecl())2191      CXXRD = CTSD->getSpecializedTemplate()->getTemplatedDecl();2192  }2193 2194  // Can't query bases without a definition.2195  if (!CXXRD->hasDefinition())2196    return Result;2197 2198  for (auto Base : CXXRD->bases()) {2199    const CXXRecordDecl *ParentDecl = nullptr;2200 2201    const Type *Type = Base.getType().getTypePtr();2202    if (const RecordType *RT = Type->getAs<RecordType>()) {2203      ParentDecl = RT->getAsCXXRecordDecl();2204    }2205 2206    if (!ParentDecl) {2207      // Handle a dependent base such as "Base<T>" by using the primary2208      // template.2209      if (const TemplateSpecializationType *TS =2210              Type->getAs<TemplateSpecializationType>()) {2211        TemplateName TN = TS->getTemplateName();2212        if (TemplateDecl *TD = TN.getAsTemplateDecl()) {2213          ParentDecl = dyn_cast<CXXRecordDecl>(TD->getTemplatedDecl());2214        }2215      }2216    }2217 2218    if (ParentDecl)2219      Result.push_back(ParentDecl);2220  }2221 2222  return Result;2223}2224 2225std::vector<TypeHierarchyItem>2226getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,2227                 TypeHierarchyDirection Direction, const SymbolIndex *Index,2228                 PathRef TUPath) {2229  std::vector<TypeHierarchyItem> Results;2230  for (const auto *CXXRD : findRecordTypeAt(AST, Pos)) {2231 2232    bool WantChildren = Direction == TypeHierarchyDirection::Children ||2233                        Direction == TypeHierarchyDirection::Both;2234 2235    // If we're looking for children, we're doing the lookup in the index.2236    // The index does not store relationships between implicit2237    // specializations, so if we have one, use the template pattern instead.2238    // Note that this needs to be done before the declToTypeHierarchyItem(),2239    // otherwise the type hierarchy item would misleadingly contain the2240    // specialization parameters, while the children would involve classes2241    // that derive from other specializations of the template.2242    if (WantChildren) {2243      if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD))2244        CXXRD = CTSD->getTemplateInstantiationPattern();2245    }2246 2247    std::optional<TypeHierarchyItem> Result =2248        declToTypeHierarchyItem(*CXXRD, AST.tuPath());2249    if (!Result)2250      continue;2251 2252    RecursionProtectionSet RPSet;2253    fillSuperTypes(*CXXRD, AST.tuPath(), *Result, RPSet);2254 2255    if (WantChildren && ResolveLevels > 0) {2256      Result->children.emplace();2257 2258      if (Index) {2259        if (auto ID = getSymbolID(CXXRD))2260          fillSubTypes(ID, *Result->children, Index, ResolveLevels, TUPath);2261      }2262    }2263    Results.emplace_back(std::move(*Result));2264  }2265 2266  return Results;2267}2268 2269std::optional<std::vector<TypeHierarchyItem>>2270superTypes(const TypeHierarchyItem &Item, const SymbolIndex *Index) {2271  std::vector<TypeHierarchyItem> Results;2272  if (!Item.data.parents)2273    return std::nullopt;2274  if (Item.data.parents->empty())2275    return Results;2276  LookupRequest Req;2277  llvm::DenseMap<SymbolID, const TypeHierarchyItem::ResolveParams *> IDToData;2278  for (const auto &Parent : *Item.data.parents) {2279    Req.IDs.insert(Parent.symbolID);2280    IDToData[Parent.symbolID] = &Parent;2281  }2282  Index->lookup(Req, [&Item, &Results, &IDToData](const Symbol &S) {2283    if (auto THI = symbolToTypeHierarchyItem(S, Item.uri.file())) {2284      THI->data = *IDToData.lookup(S.ID);2285      Results.emplace_back(std::move(*THI));2286    }2287  });2288  return Results;2289}2290 2291std::vector<TypeHierarchyItem> subTypes(const TypeHierarchyItem &Item,2292                                        const SymbolIndex *Index) {2293  std::vector<TypeHierarchyItem> Results;2294  fillSubTypes(Item.data.symbolID, Results, Index, 1, Item.uri.file());2295  for (auto &ChildSym : Results)2296    ChildSym.data.parents = {Item.data};2297  return Results;2298}2299 2300void resolveTypeHierarchy(TypeHierarchyItem &Item, int ResolveLevels,2301                          TypeHierarchyDirection Direction,2302                          const SymbolIndex *Index) {2303  // We only support typeHierarchy/resolve for children, because for parents2304  // we ignore ResolveLevels and return all levels of parents eagerly.2305  if (!Index || Direction == TypeHierarchyDirection::Parents ||2306      ResolveLevels == 0)2307    return;2308 2309  Item.children.emplace();2310  fillSubTypes(Item.data.symbolID, *Item.children, Index, ResolveLevels,2311               Item.uri.file());2312}2313 2314std::vector<CallHierarchyItem>2315prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath) {2316  std::vector<CallHierarchyItem> Result;2317  const auto &SM = AST.getSourceManager();2318  auto Loc = sourceLocationInMainFile(SM, Pos);2319  if (!Loc) {2320    elog("prepareCallHierarchy failed to convert position to source location: "2321         "{0}",2322         Loc.takeError());2323    return Result;2324  }2325  for (const NamedDecl *Decl : getDeclAtPosition(AST, *Loc, {})) {2326    if (!(isa<DeclContext>(Decl) &&2327          cast<DeclContext>(Decl)->isFunctionOrMethod()) &&2328        Decl->getKind() != Decl::Kind::FunctionTemplate &&2329        !(Decl->getKind() == Decl::Kind::Var &&2330          !cast<VarDecl>(Decl)->isLocalVarDecl()) &&2331        Decl->getKind() != Decl::Kind::Field &&2332        Decl->getKind() != Decl::Kind::EnumConstant)2333      continue;2334    if (auto CHI = declToCallHierarchyItem(*Decl, AST.tuPath()))2335      Result.emplace_back(std::move(*CHI));2336  }2337  return Result;2338}2339 2340std::vector<CallHierarchyIncomingCall>2341incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {2342  std::vector<CallHierarchyIncomingCall> Results;2343  if (!Index || Item.data.empty())2344    return Results;2345  auto ID = SymbolID::fromStr(Item.data);2346  if (!ID) {2347    elog("incomingCalls failed to find symbol: {0}", ID.takeError());2348    return Results;2349  }2350  // In this function, we find incoming calls based on the index only.2351  // In principle, the AST could have more up-to-date information about2352  // occurrences within the current file. However, going from a SymbolID2353  // to an AST node isn't cheap, particularly when the declaration isn't2354  // in the main file.2355  // FIXME: Consider also using AST information when feasible.2356  auto QueryIndex = [&](llvm::DenseSet<SymbolID> IDs, bool MightNeverCall) {2357    RefsRequest Request;2358    Request.IDs = std::move(IDs);2359    Request.WantContainer = true;2360    // We could restrict more specifically to calls by introducing a new2361    // RefKind, but non-call references (such as address-of-function) can still2362    // be interesting as they can indicate indirect calls.2363    Request.Filter = RefKind::Reference;2364    // Initially store the ranges in a map keyed by SymbolID of the caller.2365    // This allows us to group different calls with the same caller2366    // into the same CallHierarchyIncomingCall.2367    llvm::DenseMap<SymbolID, std::vector<Location>> CallsIn;2368    // We can populate the ranges based on a refs request only. As we do so, we2369    // also accumulate the container IDs into a lookup request.2370    LookupRequest ContainerLookup;2371    Index->refs(Request, [&](const Ref &R) {2372      auto Loc = indexToLSPLocation(R.Location, Item.uri.file());2373      if (!Loc) {2374        elog("incomingCalls failed to convert location: {0}", Loc.takeError());2375        return;2376      }2377      CallsIn[R.Container].push_back(*Loc);2378 2379      ContainerLookup.IDs.insert(R.Container);2380    });2381    // Perform the lookup request and combine its results with CallsIn to2382    // get complete CallHierarchyIncomingCall objects.2383    Index->lookup(ContainerLookup, [&](const Symbol &Caller) {2384      auto It = CallsIn.find(Caller.ID);2385      assert(It != CallsIn.end());2386      if (auto CHI = symbolToCallHierarchyItem(Caller, Item.uri.file())) {2387        std::vector<Range> FromRanges;2388        for (const Location &L : It->second) {2389          if (L.uri != CHI->uri) {2390            // Call location not in same file as caller.2391            // This can happen in some edge cases. There's not much we can do,2392            // since the protocol only allows returning ranges interpreted as2393            // being in the caller's file.2394            continue;2395          }2396          FromRanges.push_back(L.range);2397        }2398        Results.push_back(CallHierarchyIncomingCall{2399            std::move(*CHI), std::move(FromRanges), MightNeverCall});2400      }2401    });2402  };2403  QueryIndex({ID.get()}, false);2404  // In the case of being a virtual function we also want to return2405  // potential calls through the base function.2406  if (Item.kind == SymbolKind::Method) {2407    llvm::DenseSet<SymbolID> IDs;2408    RelationsRequest Req{{ID.get()}, RelationKind::OverriddenBy, std::nullopt};2409    Index->reverseRelations(Req, [&](const SymbolID &, const Symbol &Caller) {2410      IDs.insert(Caller.ID);2411    });2412    QueryIndex(std::move(IDs), true);2413  }2414  // Sort results by name of container.2415  llvm::sort(Results, [](const CallHierarchyIncomingCall &A,2416                         const CallHierarchyIncomingCall &B) {2417    return A.from.name < B.from.name;2418  });2419  return Results;2420}2421 2422std::vector<CallHierarchyOutgoingCall>2423outgoingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {2424  std::vector<CallHierarchyOutgoingCall> Results;2425  if (!Index || Item.data.empty())2426    return Results;2427  auto ID = SymbolID::fromStr(Item.data);2428  if (!ID) {2429    elog("outgoingCalls failed to find symbol: {0}", ID.takeError());2430    return Results;2431  }2432  // In this function, we find outgoing calls based on the index only.2433  ContainedRefsRequest Request;2434  Request.ID = *ID;2435  // Initially store the ranges in a map keyed by SymbolID of the callee.2436  // This allows us to group different calls to the same function2437  // into the same CallHierarchyOutgoingCall.2438  llvm::DenseMap<SymbolID, std::vector<Location>> CallsOut;2439  // We can populate the ranges based on a refs request only. As we do so, we2440  // also accumulate the callee IDs into a lookup request.2441  LookupRequest CallsOutLookup;2442  Index->containedRefs(Request, [&](const auto &R) {2443    auto Loc = indexToLSPLocation(R.Location, Item.uri.file());2444    if (!Loc) {2445      elog("outgoingCalls failed to convert location: {0}", Loc.takeError());2446      return;2447    }2448    auto It = CallsOut.try_emplace(R.Symbol, std::vector<Location>{}).first;2449    It->second.push_back(*Loc);2450 2451    CallsOutLookup.IDs.insert(R.Symbol);2452  });2453  // Perform the lookup request and combine its results with CallsOut to2454  // get complete CallHierarchyOutgoingCall objects.2455  Index->lookup(CallsOutLookup, [&](const Symbol &Callee) {2456    // The containedRefs request should only return symbols which are2457    // function-like, i.e. symbols for which references to them can be "calls".2458    using SK = index::SymbolKind;2459    auto Kind = Callee.SymInfo.Kind;2460    assert(Kind == SK::Function || Kind == SK::InstanceMethod ||2461           Kind == SK::ClassMethod || Kind == SK::StaticMethod ||2462           Kind == SK::Constructor || Kind == SK::Destructor ||2463           Kind == SK::ConversionFunction);2464    (void)Kind;2465    (void)SK::Function;2466 2467    auto It = CallsOut.find(Callee.ID);2468    assert(It != CallsOut.end());2469    if (auto CHI = symbolToCallHierarchyItem(Callee, Item.uri.file())) {2470      std::vector<Range> FromRanges;2471      for (const Location &L : It->second) {2472        if (L.uri != Item.uri) {2473          // Call location not in same file as the item that outgoingCalls was2474          // requested for. This can happen when Item is a declaration separate2475          // from the implementation. There's not much we can do, since the2476          // protocol only allows returning ranges interpreted as being in2477          // Item's file.2478          continue;2479        }2480        FromRanges.push_back(L.range);2481      }2482      Results.push_back(2483          CallHierarchyOutgoingCall{std::move(*CHI), std::move(FromRanges)});2484    }2485  });2486  // Sort results by name of the callee.2487  llvm::sort(Results, [](const CallHierarchyOutgoingCall &A,2488                         const CallHierarchyOutgoingCall &B) {2489    return A.to.name < B.to.name;2490  });2491  return Results;2492}2493 2494llvm::DenseSet<const Decl *> getNonLocalDeclRefs(ParsedAST &AST,2495                                                 const FunctionDecl *FD) {2496  if (!FD->hasBody())2497    return {};2498  llvm::DenseSet<const Decl *> DeclRefs;2499  findExplicitReferences(2500      FD,2501      [&](ReferenceLoc Ref) {2502        for (const Decl *D : Ref.Targets) {2503          if (!index::isFunctionLocalSymbol(D) && !D->isTemplateParameter() &&2504              !Ref.IsDecl)2505            DeclRefs.insert(D);2506        }2507      },2508      AST.getHeuristicResolver());2509  return DeclRefs;2510}2511 2512} // namespace clangd2513} // namespace clang2514