clang-tools-extra/clangd/index/SymbolCollector.cpp

   1 //===--- SymbolCollector.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "SymbolCollector.h"
  10 #include "AST.h"
  11 #include "CodeComplete.h"
  12 #include "CodeCompletionStrings.h"
  13 #include "ExpectedTypes.h"
  14 #include "SourceCode.h"
  15 #include "URI.h"
  16 #include "index/CanonicalIncludes.h"
  17 #include "index/Relation.h"
  18 #include "index/SymbolID.h"
  19 #include "index/SymbolLocation.h"
  20 #include "clang/AST/Decl.h"
  21 #include "clang/AST/DeclBase.h"
  22 #include "clang/AST/DeclObjC.h"
  23 #include "clang/AST/DeclTemplate.h"
  24 #include "clang/AST/DeclarationName.h"
  25 #include "clang/Basic/LangOptions.h"
  26 #include "clang/Basic/SourceLocation.h"
  27 #include "clang/Basic/SourceManager.h"
  28 #include "clang/Index/IndexSymbol.h"
  29 #include "clang/Lex/Preprocessor.h"
  30 #include "clang/Lex/Token.h"
  31 #include "clang/Tooling/Inclusions/HeaderAnalysis.h"
  32 #include "llvm/ADT/ArrayRef.h"
  33 #include "llvm/Support/Casting.h"
  34 #include "llvm/Support/FileSystem.h"
  35 #include "llvm/Support/Path.h"
  36 #include <optional>
  37
  38 namespace clang {
  39 namespace clangd {
  40 namespace {
  41
  42 /// If \p ND is a template specialization, returns the described template.
  43 /// Otherwise, returns \p ND.
  44 const NamedDecl &getTemplateOrThis(const NamedDecl &ND) {
  45   if (auto *T = ND.getDescribedTemplate())
  46     return *T;
  47   return ND;
  48 }
  49
  50 // Checks whether the decl is a private symbol in a header generated by
  51 // protobuf compiler.
  52 // FIXME: make filtering extensible when there are more use cases for symbol
  53 // filters.
  54 bool isPrivateProtoDecl(const NamedDecl &ND) {
  55   const auto &SM = ND.getASTContext().getSourceManager();
  56   if (!isProtoFile(nameLocation(ND, SM), SM))
  57     return false;
  58
  59   // ND without identifier can be operators.
  60   if (ND.getIdentifier() == nullptr)
  61     return false;
  62   auto Name = ND.getIdentifier()->getName();
  63   if (!Name.contains('_'))
  64     return false;
  65   // Nested proto entities (e.g. Message::Nested) have top-level decls
  66   // that shouldn't be used (Message_Nested). Ignore them completely.
  67   // The nested entities are dangling type aliases, we may want to reconsider
  68   // including them in the future.
  69   // For enum constants, SOME_ENUM_CONSTANT is not private and should be
  70   // indexed. Outer_INNER is private. This heuristic relies on naming style, it
  71   // will include OUTER_INNER and exclude some_enum_constant.
  72   // FIXME: the heuristic relies on naming style (i.e. no underscore in
  73   // user-defined names) and can be improved.
  74   return (ND.getKind() != Decl::EnumConstant) || llvm::any_of(Name, islower);
  75 }
  76
  77 // We only collect #include paths for symbols that are suitable for global code
  78 // completion, except for namespaces since #include path for a namespace is hard
  79 // to define.
  80 Symbol::IncludeDirective shouldCollectIncludePath(index::SymbolKind Kind) {
  81   using SK = index::SymbolKind;
  82   switch (Kind) {
  83   case SK::Macro:
  84   case SK::Enum:
  85   case SK::Struct:
  86   case SK::Class:
  87   case SK::Union:
  88   case SK::TypeAlias:
  89   case SK::Using:
  90   case SK::Function:
  91   case SK::Variable:
  92   case SK::EnumConstant:
  93   case SK::Concept:
  94     return Symbol::Include | Symbol::Import;
  95   case SK::Protocol:
  96     return Symbol::Import;
  97   default:
  98     return Symbol::Invalid;
  99   }
 100 }
 101
 102 // Return the symbol range of the token at \p TokLoc.
 103 std::pair<SymbolLocation::Position, SymbolLocation::Position>
 104 getTokenRange(SourceLocation TokLoc, const SourceManager &SM,
 105               const LangOptions &LangOpts) {
 106   auto CreatePosition = [&SM](SourceLocation Loc) {
 107     auto LSPLoc = sourceLocToPosition(SM, Loc);
 108     SymbolLocation::Position Pos;
 109     Pos.setLine(LSPLoc.line);
 110     Pos.setColumn(LSPLoc.character);
 111     return Pos;
 112   };
 113
 114   auto TokenLength = clang::Lexer::MeasureTokenLength(TokLoc, SM, LangOpts);
 115   return {CreatePosition(TokLoc),
 116           CreatePosition(TokLoc.getLocWithOffset(TokenLength))};
 117 }
 118
 119 // Checks whether \p ND is a good candidate to be the *canonical* declaration of
 120 // its symbol (e.g. a go-to-declaration target). This overrides the default of
 121 // using Clang's canonical declaration, which is the first in the TU.
 122 //
 123 // Example: preferring a class declaration over its forward declaration.
 124 bool isPreferredDeclaration(const NamedDecl &ND, index::SymbolRoleSet Roles) {
 125   const auto &SM = ND.getASTContext().getSourceManager();
 126   if (isa<TagDecl>(ND))
 127     return (Roles & static_cast<unsigned>(index::SymbolRole::Definition)) &&
 128            !isInsideMainFile(ND.getLocation(), SM);
 129   if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(&ND))
 130     return ID->isThisDeclarationADefinition();
 131   if (const auto *PD = dyn_cast<ObjCProtocolDecl>(&ND))
 132     return PD->isThisDeclarationADefinition();
 133   return false;
 134 }
 135
 136 RefKind toRefKind(index::SymbolRoleSet Roles, bool Spelled = false) {
 137   RefKind Result = RefKind::Unknown;
 138   if (Roles & static_cast<unsigned>(index::SymbolRole::Declaration))
 139     Result |= RefKind::Declaration;
 140   if (Roles & static_cast<unsigned>(index::SymbolRole::Definition))
 141     Result |= RefKind::Definition;
 142   if (Roles & static_cast<unsigned>(index::SymbolRole::Reference))
 143     Result |= RefKind::Reference;
 144   if (Spelled)
 145     Result |= RefKind::Spelled;
 146   return Result;
 147 }
 148
 149 std::optional<RelationKind> indexableRelation(const index::SymbolRelation &R) {
 150   if (R.Roles & static_cast<unsigned>(index::SymbolRole::RelationBaseOf))
 151     return RelationKind::BaseOf;
 152   if (R.Roles & static_cast<unsigned>(index::SymbolRole::RelationOverrideOf))
 153     return RelationKind::OverriddenBy;
 154   return std::nullopt;
 155 }
 156
 157 // Check if there is an exact spelling of \p ND at \p Loc.
 158 bool isSpelled(SourceLocation Loc, const NamedDecl &ND) {
 159   auto Name = ND.getDeclName();
 160   const auto NameKind = Name.getNameKind();
 161   if (NameKind != DeclarationName::Identifier &&
 162       NameKind != DeclarationName::CXXConstructorName)
 163     return false;
 164   const auto &AST = ND.getASTContext();
 165   const auto &SM = AST.getSourceManager();
 166   const auto &LO = AST.getLangOpts();
 167   clang::Token Tok;
 168   if (clang::Lexer::getRawToken(Loc, Tok, SM, LO))
 169     return false;
 170   auto StrName = Name.getAsString();
 171   return clang::Lexer::getSpelling(Tok, SM, LO) == StrName;
 172 }
 173 } // namespace
 174
 175 // Encapsulates decisions about how to record header paths in the index,
 176 // including filename normalization, URI conversion etc.
 177 // Expensive checks are cached internally.
 178 class SymbolCollector::HeaderFileURICache {
 179   struct FrameworkUmbrellaSpelling {
 180     // Spelling for the public umbrella header, e.g. <Foundation/Foundation.h>
 181     std::optional<std::string> PublicHeader;
 182     // Spelling for the private umbrella header, e.g.
 183     // <Foundation/Foundation_Private.h>
 184     std::optional<std::string> PrivateHeader;
 185   };
 186   // Weird double-indirect access to PP, which might not be ready yet when
 187   // HeaderFiles is created but will be by the time it's used.
 188   // (IndexDataConsumer::setPreprocessor can happen before or after initialize)
 189   Preprocessor *&PP;
 190   const SourceManager &SM;
 191   const CanonicalIncludes *Includes;
 192   llvm::StringRef FallbackDir;
 193   llvm::DenseMap<const FileEntry *, const std::string *> CacheFEToURI;
 194   llvm::StringMap<std::string> CachePathToURI;
 195   llvm::DenseMap<FileID, llvm::StringRef> CacheFIDToInclude;
 196   llvm::StringMap<std::string> CachePathToFrameworkSpelling;
 197   llvm::StringMap<FrameworkUmbrellaSpelling>
 198       CacheFrameworkToUmbrellaHeaderSpelling;
 199
 200 public:
 201   HeaderFileURICache(Preprocessor *&PP, const SourceManager &SM,
 202                      const SymbolCollector::Options &Opts)
 203       : PP(PP), SM(SM), Includes(Opts.Includes), FallbackDir(Opts.FallbackDir) {
 204   }
 205
 206   // Returns a canonical URI for the file \p FE.
 207   // We attempt to make the path absolute first.
 208   const std::string &toURI(const FileEntryRef FE) {
 209     auto R = CacheFEToURI.try_emplace(FE);
 210     if (R.second) {
 211       auto CanonPath = getCanonicalPath(FE, SM);
 212       R.first->second = &toURIInternal(CanonPath ? *CanonPath : FE.getName());
 213     }
 214     return *R.first->second;
 215   }
 216
 217   // Returns a canonical URI for \p Path.
 218   // If the file is in the FileManager, use that to canonicalize the path.
 219   // We attempt to make the path absolute in any case.
 220   const std::string &toURI(llvm::StringRef Path) {
 221     if (auto File = SM.getFileManager().getFileRef(Path))
 222       return toURI(*File);
 223     return toURIInternal(Path);
 224   }
 225
 226   // Gets a canonical include (URI of the header or <header> or "header") for
 227   // header of \p FID (which should usually be the *expansion* file).
 228   // This does not account for any per-symbol overrides!
 229   // Returns "" if includes should not be inserted for this file.
 230   llvm::StringRef getIncludeHeader(FileID FID) {
 231     auto R = CacheFIDToInclude.try_emplace(FID);
 232     if (R.second)
 233       R.first->second = getIncludeHeaderUncached(FID);
 234     return R.first->second;
 235   }
 236
 237 private:
 238   // This takes care of making paths absolute and path->URI caching, but no
 239   // FileManager-based canonicalization.
 240   const std::string &toURIInternal(llvm::StringRef Path) {
 241     auto R = CachePathToURI.try_emplace(Path);
 242     if (R.second) {
 243       llvm::SmallString<256> AbsPath = Path;
 244       if (!llvm::sys::path::is_absolute(AbsPath) && !FallbackDir.empty())
 245         llvm::sys::fs::make_absolute(FallbackDir, AbsPath);
 246       assert(llvm::sys::path::is_absolute(AbsPath) &&
 247              "If the VFS can't make paths absolute, a FallbackDir must be "
 248              "provided");
 249       llvm::sys::path::remove_dots(AbsPath, /*remove_dot_dot=*/true);
 250       R.first->second = URI::create(AbsPath).toString();
 251     }
 252     return R.first->second;
 253   }
 254
 255   struct FrameworkHeaderPath {
 256     // Path to the framework directory containing the Headers/PrivateHeaders
 257     // directories  e.g. /Frameworks/Foundation.framework/
 258     llvm::StringRef HeadersParentDir;
 259     // Subpath relative to the Headers or PrivateHeaders dir, e.g. NSObject.h
 260     // Note: This is NOT relative to the `HeadersParentDir`.
 261     llvm::StringRef HeaderSubpath;
 262     // Whether this header is under the PrivateHeaders dir
 263     bool IsPrivateHeader;
 264   };
 265
 266   std::optional<FrameworkHeaderPath>
 267   splitFrameworkHeaderPath(llvm::StringRef Path) {
 268     using namespace llvm::sys;
 269     path::reverse_iterator I = path::rbegin(Path);
 270     path::reverse_iterator Prev = I;
 271     path::reverse_iterator E = path::rend(Path);
 272     while (I != E) {
 273       if (*I == "Headers") {
 274         FrameworkHeaderPath HeaderPath;
 275         HeaderPath.HeadersParentDir = Path.substr(0, I - E);
 276         HeaderPath.HeaderSubpath = Path.substr(Prev - E);
 277         HeaderPath.IsPrivateHeader = false;
 278         return HeaderPath;
 279       }
 280       if (*I == "PrivateHeaders") {
 281         FrameworkHeaderPath HeaderPath;
 282         HeaderPath.HeadersParentDir = Path.substr(0, I - E);
 283         HeaderPath.HeaderSubpath = Path.substr(Prev - E);
 284         HeaderPath.IsPrivateHeader = true;
 285         return HeaderPath;
 286       }
 287       Prev = I;
 288       ++I;
 289     }
 290     // Unexpected, must not be a framework header.
 291     return std::nullopt;
 292   }
 293
 294   // Frameworks typically have an umbrella header of the same name, e.g.
 295   // <Foundation/Foundation.h> instead of <Foundation/NSObject.h> or
 296   // <Foundation/Foundation_Private.h> instead of
 297   // <Foundation/NSObject_Private.h> which should be used instead of directly
 298   // importing the header.
 299   std::optional<std::string> getFrameworkUmbrellaSpelling(
 300       llvm::StringRef Framework, SrcMgr::CharacteristicKind HeadersDirKind,
 301       const HeaderSearch &HS, FrameworkHeaderPath &HeaderPath) {
 302     auto Res = CacheFrameworkToUmbrellaHeaderSpelling.try_emplace(Framework);
 303     auto *CachedSpelling = &Res.first->second;
 304     if (!Res.second) {
 305       return HeaderPath.IsPrivateHeader ? CachedSpelling->PrivateHeader
 306                                         : CachedSpelling->PublicHeader;
 307     }
 308     bool IsSystem = isSystem(HeadersDirKind);
 309     SmallString<256> UmbrellaPath(HeaderPath.HeadersParentDir);
 310     llvm::sys::path::append(UmbrellaPath, "Headers", Framework + ".h");
 311
 312     llvm::vfs::Status Status;
 313     auto StatErr = HS.getFileMgr().getNoncachedStatValue(UmbrellaPath, Status);
 314     if (!StatErr) {
 315       if (IsSystem)
 316         CachedSpelling->PublicHeader = llvm::formatv("<{0}/{0}.h>", Framework);
 317       else
 318         CachedSpelling->PublicHeader =
 319             llvm::formatv("\"{0}/{0}.h\"", Framework);
 320     }
 321
 322     UmbrellaPath = HeaderPath.HeadersParentDir;
 323     llvm::sys::path::append(UmbrellaPath, "PrivateHeaders",
 324                             Framework + "_Private.h");
 325
 326     StatErr = HS.getFileMgr().getNoncachedStatValue(UmbrellaPath, Status);
 327     if (!StatErr) {
 328       if (IsSystem)
 329         CachedSpelling->PrivateHeader =
 330             llvm::formatv("<{0}/{0}_Private.h>", Framework);
 331       else
 332         CachedSpelling->PrivateHeader =
 333             llvm::formatv("\"{0}/{0}_Private.h\"", Framework);
 334     }
 335     return HeaderPath.IsPrivateHeader ? CachedSpelling->PrivateHeader
 336                                       : CachedSpelling->PublicHeader;
 337   }
 338
 339   // Compute the framework include spelling for `FE` which is in a framework
 340   // named `Framework`, e.g. `NSObject.h` in framework `Foundation` would
 341   // give <Foundation/Foundation.h> if the umbrella header exists, otherwise
 342   // <Foundation/NSObject.h>.
 343   std::optional<llvm::StringRef> getFrameworkHeaderIncludeSpelling(
 344       const FileEntry *FE, llvm::StringRef Framework, HeaderSearch &HS) {
 345     auto Res = CachePathToFrameworkSpelling.try_emplace(FE->getName());
 346     auto *CachedHeaderSpelling = &Res.first->second;
 347     if (!Res.second)
 348       return llvm::StringRef(*CachedHeaderSpelling);
 349
 350     auto HeaderPath = splitFrameworkHeaderPath(FE->getName());
 351     if (!HeaderPath) {
 352       // Unexpected: must not be a proper framework header, don't cache the
 353       // failure.
 354       CachePathToFrameworkSpelling.erase(Res.first);
 355       return std::nullopt;
 356     }
 357     auto DirKind = HS.getFileDirFlavor(FE);
 358     if (auto UmbrellaSpelling =
 359             getFrameworkUmbrellaSpelling(Framework, DirKind, HS, *HeaderPath)) {
 360       *CachedHeaderSpelling = *UmbrellaSpelling;
 361       return llvm::StringRef(*CachedHeaderSpelling);
 362     }
 363
 364     if (isSystem(DirKind))
 365       *CachedHeaderSpelling =
 366           llvm::formatv("<{0}/{1}>", Framework, HeaderPath->HeaderSubpath)
 367               .str();
 368     else
 369       *CachedHeaderSpelling =
 370           llvm::formatv("\"{0}/{1}\"", Framework, HeaderPath->HeaderSubpath)
 371               .str();
 372     return llvm::StringRef(*CachedHeaderSpelling);
 373   }
 374
 375   llvm::StringRef getIncludeHeaderUncached(FileID FID) {
 376     const auto FE = SM.getFileEntryRefForID(FID);
 377     if (!FE || FE->getName().empty())
 378       return "";
 379     llvm::StringRef Filename = FE->getName();
 380     // If a file is mapped by canonical headers, use that mapping, regardless
 381     // of whether it's an otherwise-good header (header guards etc).
 382     if (Includes) {
 383       llvm::StringRef Canonical =
 384           Includes->mapHeader(*SM.getFileEntryRefForID(FID));
 385       if (!Canonical.empty()) {
 386         // If we had a mapping, always use it.
 387         if (Canonical.startswith("<") || Canonical.startswith("\""))
 388           return Canonical;
 389         return toURI(Canonical);
 390       }
 391     }
 392     // Framework headers are spelled as <FrameworkName/Foo.h>, not
 393     // "path/FrameworkName.framework/Headers/Foo.h".
 394     auto &HS = PP->getHeaderSearchInfo();
 395     if (const auto *HFI = HS.getExistingFileInfo(*FE, /*WantExternal*/ false))
 396       if (!HFI->Framework.empty())
 397         if (auto Spelling =
 398                 getFrameworkHeaderIncludeSpelling(*FE, HFI->Framework, HS))
 399           return *Spelling;
 400
 401     if (!tooling::isSelfContainedHeader(*FE, PP->getSourceManager(),
 402                                         PP->getHeaderSearchInfo())) {
 403       // A .inc or .def file is often included into a real header to define
 404       // symbols (e.g. LLVM tablegen files).
 405       if (Filename.endswith(".inc") || Filename.endswith(".def"))
 406         // Don't use cache reentrantly due to iterator invalidation.
 407         return getIncludeHeaderUncached(SM.getFileID(SM.getIncludeLoc(FID)));
 408       // Conservatively refuse to insert #includes to files without guards.
 409       return "";
 410     }
 411     // Standard case: just insert the file itself.
 412     return toURI(*FE);
 413   }
 414 };
 415
 416 // Return the symbol location of the token at \p TokLoc.
 417 std::optional<SymbolLocation>
 418 SymbolCollector::getTokenLocation(SourceLocation TokLoc) {
 419   const auto &SM = ASTCtx->getSourceManager();
 420   const auto FE = SM.getFileEntryRefForID(SM.getFileID(TokLoc));
 421   if (!FE)
 422     return std::nullopt;
 423
 424   SymbolLocation Result;
 425   Result.FileURI = HeaderFileURIs->toURI(*FE).c_str();
 426   auto Range = getTokenRange(TokLoc, SM, ASTCtx->getLangOpts());
 427   Result.Start = Range.first;
 428   Result.End = Range.second;
 429
 430   return Result;
 431 }
 432
 433 SymbolCollector::SymbolCollector(Options Opts) : Opts(std::move(Opts)) {}
 434 SymbolCollector::~SymbolCollector() = default;
 435
 436 void SymbolCollector::initialize(ASTContext &Ctx) {
 437   ASTCtx = &Ctx;
 438   HeaderFileURIs = std::make_unique<HeaderFileURICache>(
 439       this->PP, ASTCtx->getSourceManager(), Opts);
 440   CompletionAllocator = std::make_shared<GlobalCodeCompletionAllocator>();
 441   CompletionTUInfo =
 442       std::make_unique<CodeCompletionTUInfo>(CompletionAllocator);
 443 }
 444
 445 bool SymbolCollector::shouldCollectSymbol(const NamedDecl &ND,
 446                                           const ASTContext &ASTCtx,
 447                                           const Options &Opts,
 448                                           bool IsMainFileOnly) {
 449   // Skip anonymous declarations, e.g (anonymous enum/class/struct).
 450   if (ND.getDeclName().isEmpty())
 451     return false;
 452
 453   // Skip main-file symbols if we are not collecting them.
 454   if (IsMainFileOnly && !Opts.CollectMainFileSymbols)
 455     return false;
 456
 457   // Skip symbols in anonymous namespaces in header files.
 458   if (!IsMainFileOnly && ND.isInAnonymousNamespace())
 459     return false;
 460
 461   // For function local symbols, index only classes and its member functions.
 462   if (index::isFunctionLocalSymbol(&ND))
 463     return isa<RecordDecl>(ND) ||
 464            (ND.isCXXInstanceMember() && ND.isFunctionOrFunctionTemplate());
 465
 466   // We want most things but not "local" symbols such as symbols inside
 467   // FunctionDecl, BlockDecl, ObjCMethodDecl and OMPDeclareReductionDecl.
 468   // FIXME: Need a matcher for ExportDecl in order to include symbols declared
 469   // within an export.
 470   const auto *DeclCtx = ND.getDeclContext();
 471   switch (DeclCtx->getDeclKind()) {
 472   case Decl::TranslationUnit:
 473   case Decl::Namespace:
 474   case Decl::LinkageSpec:
 475   case Decl::Enum:
 476   case Decl::ObjCProtocol:
 477   case Decl::ObjCInterface:
 478   case Decl::ObjCCategory:
 479   case Decl::ObjCCategoryImpl:
 480   case Decl::ObjCImplementation:
 481     break;
 482   default:
 483     // Record has a few derivations (e.g. CXXRecord, Class specialization), it's
 484     // easier to cast.
 485     if (!isa<RecordDecl>(DeclCtx))
 486       return false;
 487   }
 488
 489   // Avoid indexing internal symbols in protobuf generated headers.
 490   if (isPrivateProtoDecl(ND))
 491     return false;
 492   if (!Opts.CollectReserved &&
 493       (hasReservedName(ND) || hasReservedScope(*ND.getDeclContext())))
 494     return false;
 495
 496   return true;
 497 }
 498
 499 const Decl *
 500 SymbolCollector::getRefContainer(const Decl *Enclosing,
 501                                  const SymbolCollector::Options &Opts) {
 502   while (Enclosing) {
 503     const auto *ND = dyn_cast<NamedDecl>(Enclosing);
 504     if (ND && shouldCollectSymbol(*ND, ND->getASTContext(), Opts, true)) {
 505       break;
 506     }
 507     Enclosing = dyn_cast_or_null<Decl>(Enclosing->getDeclContext());
 508   }
 509   return Enclosing;
 510 }
 511
 512 // Always return true to continue indexing.
 513 bool SymbolCollector::handleDeclOccurrence(
 514     const Decl *D, index::SymbolRoleSet Roles,
 515     llvm::ArrayRef<index::SymbolRelation> Relations, SourceLocation Loc,
 516     index::IndexDataConsumer::ASTNodeInfo ASTNode) {
 517   assert(ASTCtx && PP && HeaderFileURIs);
 518   assert(CompletionAllocator && CompletionTUInfo);
 519   assert(ASTNode.OrigD);
 520   // Indexing API puts canonical decl into D, which might not have a valid
 521   // source location for implicit/built-in decls. Fallback to original decl in
 522   // such cases.
 523   if (D->getLocation().isInvalid())
 524     D = ASTNode.OrigD;
 525   // If OrigD is an declaration associated with a friend declaration and it's
 526   // not a definition, skip it. Note that OrigD is the occurrence that the
 527   // collector is currently visiting.
 528   if ((ASTNode.OrigD->getFriendObjectKind() !=
 529        Decl::FriendObjectKind::FOK_None) &&
 530       !(Roles & static_cast<unsigned>(index::SymbolRole::Definition)))
 531     return true;
 532   // A declaration created for a friend declaration should not be used as the
 533   // canonical declaration in the index. Use OrigD instead, unless we've already
 534   // picked a replacement for D
 535   if (D->getFriendObjectKind() != Decl::FriendObjectKind::FOK_None)
 536     D = CanonicalDecls.try_emplace(D, ASTNode.OrigD).first->second;
 537   // Flag to mark that D should be considered canonical meaning its declaration
 538   // will override any previous declaration for the Symbol.
 539   bool DeclIsCanonical = false;
 540   // Avoid treating ObjCImplementationDecl as a canonical declaration if it has
 541   // a corresponding non-implicit and non-forward declared ObjcInterfaceDecl.
 542   if (const auto *IID = dyn_cast<ObjCImplementationDecl>(D)) {
 543     DeclIsCanonical = true;
 544     if (const auto *CID = IID->getClassInterface())
 545       if (const auto *DD = CID->getDefinition())
 546         if (!DD->isImplicitInterfaceDecl())
 547           D = DD;
 548   }
 549   // Avoid treating ObjCCategoryImplDecl as a canonical declaration in favor of
 550   // its ObjCCategoryDecl if it has one.
 551   if (const auto *CID = dyn_cast<ObjCCategoryImplDecl>(D)) {
 552     DeclIsCanonical = true;
 553     if (const auto *CD = CID->getCategoryDecl())
 554       D = CD;
 555   }
 556   const NamedDecl *ND = dyn_cast<NamedDecl>(D);
 557   if (!ND)
 558     return true;
 559
 560   auto ID = getSymbolIDCached(ND);
 561   if (!ID)
 562     return true;
 563
 564   // Mark D as referenced if this is a reference coming from the main file.
 565   // D may not be an interesting symbol, but it's cheaper to check at the end.
 566   auto &SM = ASTCtx->getSourceManager();
 567   if (Opts.CountReferences &&
 568       (Roles & static_cast<unsigned>(index::SymbolRole::Reference)) &&
 569       SM.getFileID(SM.getSpellingLoc(Loc)) == SM.getMainFileID())
 570     ReferencedSymbols.insert(ID);
 571
 572   // ND is the canonical (i.e. first) declaration. If it's in the main file
 573   // (which is not a header), then no public declaration was visible, so assume
 574   // it's main-file only.
 575   bool IsMainFileOnly =
 576       SM.isWrittenInMainFile(SM.getExpansionLoc(ND->getBeginLoc())) &&
 577       !isHeaderFile(SM.getFileEntryRefForID(SM.getMainFileID())->getName(),
 578                     ASTCtx->getLangOpts());
 579   // In C, printf is a redecl of an implicit builtin! So check OrigD instead.
 580   if (ASTNode.OrigD->isImplicit() ||
 581       !shouldCollectSymbol(*ND, *ASTCtx, Opts, IsMainFileOnly))
 582     return true;
 583
 584   // Note: we need to process relations for all decl occurrences, including
 585   // refs, because the indexing code only populates relations for specific
 586   // occurrences. For example, RelationBaseOf is only populated for the
 587   // occurrence inside the base-specifier.
 588   processRelations(*ND, ID, Relations);
 589
 590   bool CollectRef = static_cast<bool>(Opts.RefFilter & toRefKind(Roles));
 591   // Unlike other fields, e.g. Symbols (which use spelling locations), we use
 592   // file locations for references (as it aligns the behavior of clangd's
 593   // AST-based xref).
 594   // FIXME: we should try to use the file locations for other fields.
 595   if (CollectRef &&
 596       (!IsMainFileOnly || Opts.CollectMainFileRefs ||
 597        ND->isExternallyVisible()) &&
 598       !isa<NamespaceDecl>(ND)) {
 599     auto FileLoc = SM.getFileLoc(Loc);
 600     auto FID = SM.getFileID(FileLoc);
 601     if (Opts.RefsInHeaders || FID == SM.getMainFileID()) {
 602       addRef(ID, SymbolRef{FileLoc, FID, Roles,
 603                            getRefContainer(ASTNode.Parent, Opts),
 604                            isSpelled(FileLoc, *ND)});
 605     }
 606   }
 607   // Don't continue indexing if this is a mere reference.
 608   if (!(Roles & (static_cast<unsigned>(index::SymbolRole::Declaration) |
 609                  static_cast<unsigned>(index::SymbolRole::Definition))))
 610     return true;
 611
 612   // FIXME: ObjCPropertyDecl are not properly indexed here:
 613   // - ObjCPropertyDecl may have an OrigD of ObjCPropertyImplDecl, which is
 614   // not a NamedDecl.
 615   auto *OriginalDecl = dyn_cast<NamedDecl>(ASTNode.OrigD);
 616   if (!OriginalDecl)
 617     return true;
 618
 619   const Symbol *BasicSymbol = Symbols.find(ID);
 620   if (isPreferredDeclaration(*OriginalDecl, Roles))
 621     // If OriginalDecl is preferred, replace/create the existing canonical
 622     // declaration (e.g. a class forward declaration). There should be at most
 623     // one duplicate as we expect to see only one preferred declaration per
 624     // TU, because in practice they are definitions.
 625     BasicSymbol = addDeclaration(*OriginalDecl, std::move(ID), IsMainFileOnly);
 626   else if (!BasicSymbol || DeclIsCanonical)
 627     BasicSymbol = addDeclaration(*ND, std::move(ID), IsMainFileOnly);
 628
 629   if (Roles & static_cast<unsigned>(index::SymbolRole::Definition))
 630     addDefinition(*OriginalDecl, *BasicSymbol);
 631
 632   return true;
 633 }
 634
 635 void SymbolCollector::handleMacros(const MainFileMacros &MacroRefsToIndex) {
 636   assert(HeaderFileURIs && PP);
 637   const auto &SM = PP->getSourceManager();
 638   const auto MainFileEntryRef = SM.getFileEntryRefForID(SM.getMainFileID());
 639   assert(MainFileEntryRef);
 640
 641   const std::string &MainFileURI = HeaderFileURIs->toURI(*MainFileEntryRef);
 642   // Add macro references.
 643   for (const auto &IDToRefs : MacroRefsToIndex.MacroRefs) {
 644     for (const auto &MacroRef : IDToRefs.second) {
 645       const auto &Range = MacroRef.Rng;
 646       bool IsDefinition = MacroRef.IsDefinition;
 647       Ref R;
 648       R.Location.Start.setLine(Range.start.line);
 649       R.Location.Start.setColumn(Range.start.character);
 650       R.Location.End.setLine(Range.end.line);
 651       R.Location.End.setColumn(Range.end.character);
 652       R.Location.FileURI = MainFileURI.c_str();
 653       R.Kind = IsDefinition ? RefKind::Definition : RefKind::Reference;
 654       Refs.insert(IDToRefs.first, R);
 655       if (IsDefinition) {
 656         Symbol S;
 657         S.ID = IDToRefs.first;
 658         auto StartLoc = cantFail(sourceLocationInMainFile(SM, Range.start));
 659         auto EndLoc = cantFail(sourceLocationInMainFile(SM, Range.end));
 660         S.Name = toSourceCode(SM, SourceRange(StartLoc, EndLoc));
 661         S.SymInfo.Kind = index::SymbolKind::Macro;
 662         S.SymInfo.SubKind = index::SymbolSubKind::None;
 663         S.SymInfo.Properties = index::SymbolPropertySet();
 664         S.SymInfo.Lang = index::SymbolLanguage::C;
 665         S.Origin = Opts.Origin;
 666         S.CanonicalDeclaration = R.Location;
 667         // Make the macro visible for code completion if main file is an
 668         // include-able header.
 669         if (!HeaderFileURIs->getIncludeHeader(SM.getMainFileID()).empty()) {
 670           S.Flags |= Symbol::IndexedForCodeCompletion;
 671           S.Flags |= Symbol::VisibleOutsideFile;
 672         }
 673         Symbols.insert(S);
 674       }
 675     }
 676   }
 677 }
 678
 679 bool SymbolCollector::handleMacroOccurrence(const IdentifierInfo *Name,
 680                                             const MacroInfo *MI,
 681                                             index::SymbolRoleSet Roles,
 682                                             SourceLocation Loc) {
 683   assert(PP);
 684   // Builtin macros don't have useful locations and aren't needed in completion.
 685   if (MI->isBuiltinMacro())
 686     return true;
 687
 688   const auto &SM = PP->getSourceManager();
 689   auto DefLoc = MI->getDefinitionLoc();
 690   // Also avoid storing macros that aren't defined in any file, i.e. predefined
 691   // macros like __DBL_MIN__ and those defined on the command line.
 692   if (SM.isWrittenInBuiltinFile(DefLoc) ||
 693       SM.isWrittenInCommandLineFile(DefLoc) ||
 694       Name->getName() == "__GCC_HAVE_DWARF2_CFI_ASM")
 695     return true;
 696
 697   auto ID = getSymbolIDCached(Name->getName(), MI, SM);
 698   if (!ID)
 699     return true;
 700
 701   auto SpellingLoc = SM.getSpellingLoc(Loc);
 702   bool IsMainFileOnly =
 703       SM.isInMainFile(SM.getExpansionLoc(DefLoc)) &&
 704       !isHeaderFile(SM.getFileEntryRefForID(SM.getMainFileID())->getName(),
 705                     ASTCtx->getLangOpts());
 706   // Do not store references to main-file macros.
 707   if ((static_cast<unsigned>(Opts.RefFilter) & Roles) && !IsMainFileOnly &&
 708       (Opts.RefsInHeaders || SM.getFileID(SpellingLoc) == SM.getMainFileID())) {
 709     // FIXME: Populate container information for macro references.
 710     // FIXME: All MacroRefs are marked as Spelled now, but this should be
 711     // checked.
 712     addRef(ID, SymbolRef{Loc, SM.getFileID(Loc), Roles, /*Container=*/nullptr,
 713                          /*Spelled=*/true});
 714   }
 715
 716   // Collect symbols.
 717   if (!Opts.CollectMacro)
 718     return true;
 719
 720   // Skip main-file macros if we are not collecting them.
 721   if (IsMainFileOnly && !Opts.CollectMainFileSymbols)
 722     return false;
 723
 724   // Mark the macro as referenced if this is a reference coming from the main
 725   // file. The macro may not be an interesting symbol, but it's cheaper to check
 726   // at the end.
 727   if (Opts.CountReferences &&
 728       (Roles & static_cast<unsigned>(index::SymbolRole::Reference)) &&
 729       SM.getFileID(SpellingLoc) == SM.getMainFileID())
 730     ReferencedSymbols.insert(ID);
 731
 732   // Don't continue indexing if this is a mere reference.
 733   // FIXME: remove macro with ID if it is undefined.
 734   if (!(Roles & static_cast<unsigned>(index::SymbolRole::Declaration) ||
 735         Roles & static_cast<unsigned>(index::SymbolRole::Definition)))
 736     return true;
 737
 738   // Only collect one instance in case there are multiple.
 739   if (Symbols.find(ID) != nullptr)
 740     return true;
 741
 742   Symbol S;
 743   S.ID = std::move(ID);
 744   S.Name = Name->getName();
 745   if (!IsMainFileOnly) {
 746     S.Flags |= Symbol::IndexedForCodeCompletion;
 747     S.Flags |= Symbol::VisibleOutsideFile;
 748   }
 749   S.SymInfo = index::getSymbolInfoForMacro(*MI);
 750   S.Origin = Opts.Origin;
 751   // FIXME: use the result to filter out symbols.
 752   shouldIndexFile(SM.getFileID(Loc));
 753   if (auto DeclLoc = getTokenLocation(DefLoc))
 754     S.CanonicalDeclaration = *DeclLoc;
 755
 756   CodeCompletionResult SymbolCompletion(Name);
 757   const auto *CCS = SymbolCompletion.CreateCodeCompletionStringForMacro(
 758       *PP, *CompletionAllocator, *CompletionTUInfo);
 759   std::string Signature;
 760   std::string SnippetSuffix;
 761   getSignature(*CCS, &Signature, &SnippetSuffix, SymbolCompletion.Kind,
 762                SymbolCompletion.CursorKind);
 763   S.Signature = Signature;
 764   S.CompletionSnippetSuffix = SnippetSuffix;
 765
 766   IndexedMacros.insert(Name);
 767   setIncludeLocation(S, DefLoc);
 768   Symbols.insert(S);
 769   return true;
 770 }
 771
 772 void SymbolCollector::processRelations(
 773     const NamedDecl &ND, const SymbolID &ID,
 774     ArrayRef<index::SymbolRelation> Relations) {
 775   for (const auto &R : Relations) {
 776     auto RKind = indexableRelation(R);
 777     if (!RKind)
 778       continue;
 779     const Decl *Object = R.RelatedSymbol;
 780
 781     auto ObjectID = getSymbolIDCached(Object);
 782     if (!ObjectID)
 783       continue;
 784
 785     // Record the relation.
 786     // TODO: There may be cases where the object decl is not indexed for some
 787     // reason. Those cases should probably be removed in due course, but for
 788     // now there are two possible ways to handle it:
 789     //   (A) Avoid storing the relation in such cases.
 790     //   (B) Store it anyways. Clients will likely lookup() the SymbolID
 791     //       in the index and find nothing, but that's a situation they
 792     //       probably need to handle for other reasons anyways.
 793     // We currently do (B) because it's simpler.
 794     if (*RKind == RelationKind::BaseOf)
 795       this->Relations.insert({ID, *RKind, ObjectID});
 796     else if (*RKind == RelationKind::OverriddenBy)
 797       this->Relations.insert({ObjectID, *RKind, ID});
 798   }
 799 }
 800
 801 void SymbolCollector::setIncludeLocation(const Symbol &S, SourceLocation Loc) {
 802   if (Opts.CollectIncludePath &&
 803       shouldCollectIncludePath(S.SymInfo.Kind) != Symbol::Invalid)
 804     // Use the expansion location to get the #include header since this is
 805     // where the symbol is exposed.
 806     IncludeFiles[S.ID] =
 807         PP->getSourceManager().getDecomposedExpansionLoc(Loc).first;
 808 }
 809
 810 void SymbolCollector::finish() {
 811   // At the end of the TU, add 1 to the refcount of all referenced symbols.
 812   for (const auto &ID : ReferencedSymbols) {
 813     if (const auto *S = Symbols.find(ID)) {
 814       // SymbolSlab::Builder returns const symbols because strings are interned
 815       // and modifying returned symbols without inserting again wouldn't go
 816       // well. const_cast is safe here as we're modifying a data owned by the
 817       // Symbol. This reduces time spent in SymbolCollector by ~1%.
 818       ++const_cast<Symbol *>(S)->References;
 819     }
 820   }
 821   if (Opts.CollectMacro) {
 822     assert(PP);
 823     // First, drop header guards. We can't identify these until EOF.
 824     for (const IdentifierInfo *II : IndexedMacros) {
 825       if (const auto *MI = PP->getMacroDefinition(II).getMacroInfo())
 826         if (auto ID =
 827                 getSymbolIDCached(II->getName(), MI, PP->getSourceManager()))
 828           if (MI->isUsedForHeaderGuard())
 829             Symbols.erase(ID);
 830     }
 831   }
 832   llvm::DenseMap<FileID, bool> FileToContainsImportsOrObjC;
 833   // Fill in IncludeHeaders.
 834   // We delay this until end of TU so header guards are all resolved.
 835   for (const auto &[SID, FID] : IncludeFiles) {
 836     if (const Symbol *S = Symbols.find(SID)) {
 837       llvm::StringRef IncludeHeader;
 838       // Look for an overridden include header for this symbol specifically.
 839       if (Opts.Includes) {
 840         IncludeHeader =
 841             Opts.Includes->mapSymbol(S->Scope, S->Name, ASTCtx->getLangOpts());
 842         if (!IncludeHeader.empty()) {
 843           if (IncludeHeader.front() != '"' && IncludeHeader.front() != '<')
 844             IncludeHeader = HeaderFileURIs->toURI(IncludeHeader);
 845           else if (IncludeHeader == "<utility>" && S->Scope == "std::" &&
 846                    S->Name == "move" && S->Signature.contains(','))
 847             IncludeHeader = "<algorithm>";
 848         }
 849       }
 850       // Otherwise find the approprate include header for the defining file.
 851       if (IncludeHeader.empty())
 852         IncludeHeader = HeaderFileURIs->getIncludeHeader(FID);
 853
 854       // Symbols in slabs aren't mutable, insert() has to walk all the strings
 855       if (!IncludeHeader.empty()) {
 856         Symbol::IncludeDirective Directives = Symbol::Invalid;
 857         auto CollectDirectives = shouldCollectIncludePath(S->SymInfo.Kind);
 858         if ((CollectDirectives & Symbol::Include) != 0)
 859           Directives |= Symbol::Include;
 860         // Only allow #import for symbols from ObjC-like files.
 861         if ((CollectDirectives & Symbol::Import) != 0) {
 862           auto [It, Inserted] = FileToContainsImportsOrObjC.try_emplace(FID);
 863           if (Inserted)
 864             It->second = FilesWithObjCConstructs.contains(FID) ||
 865                          tooling::codeContainsImports(
 866                              ASTCtx->getSourceManager().getBufferData(FID));
 867           if (It->second)
 868             Directives |= Symbol::Import;
 869         }
 870         if (Directives != Symbol::Invalid) {
 871           Symbol NewSym = *S;
 872           NewSym.IncludeHeaders.push_back({IncludeHeader, 1, Directives});
 873           Symbols.insert(NewSym);
 874         }
 875       }
 876     }
 877   }
 878
 879   ReferencedSymbols.clear();
 880   IncludeFiles.clear();
 881   FilesWithObjCConstructs.clear();
 882 }
 883
 884 const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND, SymbolID ID,
 885                                               bool IsMainFileOnly) {
 886   auto &Ctx = ND.getASTContext();
 887   auto &SM = Ctx.getSourceManager();
 888
 889   Symbol S;
 890   S.ID = std::move(ID);
 891   std::string QName = printQualifiedName(ND);
 892   // FIXME: this returns foo:bar: for objective-C methods, we prefer only foo:
 893   // for consistency with CodeCompletionString and a clean name/signature split.
 894   std::tie(S.Scope, S.Name) = splitQualifiedName(QName);
 895   std::string TemplateSpecializationArgs = printTemplateSpecializationArgs(ND);
 896   S.TemplateSpecializationArgs = TemplateSpecializationArgs;
 897
 898   // We collect main-file symbols, but do not use them for code completion.
 899   if (!IsMainFileOnly && isIndexedForCodeCompletion(ND, Ctx))
 900     S.Flags |= Symbol::IndexedForCodeCompletion;
 901   if (isImplementationDetail(&ND))
 902     S.Flags |= Symbol::ImplementationDetail;
 903   if (!IsMainFileOnly)
 904     S.Flags |= Symbol::VisibleOutsideFile;
 905   S.SymInfo = index::getSymbolInfo(&ND);
 906   auto Loc = nameLocation(ND, SM);
 907   assert(Loc.isValid() && "Invalid source location for NamedDecl");
 908   // FIXME: use the result to filter out symbols.
 909   auto FID = SM.getFileID(Loc);
 910   shouldIndexFile(FID);
 911   if (auto DeclLoc = getTokenLocation(Loc))
 912     S.CanonicalDeclaration = *DeclLoc;
 913
 914   S.Origin = Opts.Origin;
 915   if (ND.getAvailability() == AR_Deprecated)
 916     S.Flags |= Symbol::Deprecated;
 917
 918   // Add completion info.
 919   // FIXME: we may want to choose a different redecl, or combine from several.
 920   assert(ASTCtx && PP && "ASTContext and Preprocessor must be set.");
 921   // We use the primary template, as clang does during code completion.
 922   CodeCompletionResult SymbolCompletion(&getTemplateOrThis(ND), 0);
 923   const auto *CCS = SymbolCompletion.CreateCodeCompletionString(
 924       *ASTCtx, *PP, CodeCompletionContext::CCC_Symbol, *CompletionAllocator,
 925       *CompletionTUInfo,
 926       /*IncludeBriefComments*/ false);
 927   std::string Documentation =
 928       formatDocumentation(*CCS, getDocComment(Ctx, SymbolCompletion,
 929                                               /*CommentsFromHeaders=*/true));
 930   if (!(S.Flags & Symbol::IndexedForCodeCompletion)) {
 931     if (Opts.StoreAllDocumentation)
 932       S.Documentation = Documentation;
 933     Symbols.insert(S);
 934     return Symbols.find(S.ID);
 935   }
 936   S.Documentation = Documentation;
 937   std::string Signature;
 938   std::string SnippetSuffix;
 939   getSignature(*CCS, &Signature, &SnippetSuffix, SymbolCompletion.Kind,
 940                SymbolCompletion.CursorKind);
 941   S.Signature = Signature;
 942   S.CompletionSnippetSuffix = SnippetSuffix;
 943   std::string ReturnType = getReturnType(*CCS);
 944   S.ReturnType = ReturnType;
 945
 946   std::optional<OpaqueType> TypeStorage;
 947   if (S.Flags & Symbol::IndexedForCodeCompletion) {
 948     TypeStorage = OpaqueType::fromCompletionResult(*ASTCtx, SymbolCompletion);
 949     if (TypeStorage)
 950       S.Type = TypeStorage->raw();
 951   }
 952
 953   Symbols.insert(S);
 954   setIncludeLocation(S, ND.getLocation());
 955   if (S.SymInfo.Lang == index::SymbolLanguage::ObjC)
 956     FilesWithObjCConstructs.insert(FID);
 957   return Symbols.find(S.ID);
 958 }
 959
 960 void SymbolCollector::addDefinition(const NamedDecl &ND,
 961                                     const Symbol &DeclSym) {
 962   if (DeclSym.Definition)
 963     return;
 964   const auto &SM = ND.getASTContext().getSourceManager();
 965   auto Loc = nameLocation(ND, SM);
 966   shouldIndexFile(SM.getFileID(Loc));
 967   auto DefLoc = getTokenLocation(Loc);
 968   // If we saw some forward declaration, we end up copying the symbol.
 969   // This is not ideal, but avoids duplicating the "is this a definition" check
 970   // in clang::index. We should only see one definition.
 971   if (!DefLoc)
 972     return;
 973   Symbol S = DeclSym;
 974   // FIXME: use the result to filter out symbols.
 975   S.Definition = *DefLoc;
 976   Symbols.insert(S);
 977 }
 978
 979 bool SymbolCollector::shouldIndexFile(FileID FID) {
 980   if (!Opts.FileFilter)
 981     return true;
 982   auto I = FilesToIndexCache.try_emplace(FID);
 983   if (I.second)
 984     I.first->second = Opts.FileFilter(ASTCtx->getSourceManager(), FID);
 985   return I.first->second;
 986 }
 987
 988 void SymbolCollector::addRef(SymbolID ID, const SymbolRef &SR) {
 989   const auto &SM = ASTCtx->getSourceManager();
 990   // FIXME: use the result to filter out references.
 991   shouldIndexFile(SR.FID);
 992   if (const auto FE = SM.getFileEntryRefForID(SR.FID)) {
 993     auto Range = getTokenRange(SR.Loc, SM, ASTCtx->getLangOpts());
 994     Ref R;
 995     R.Location.Start = Range.first;
 996     R.Location.End = Range.second;
 997     R.Location.FileURI = HeaderFileURIs->toURI(*FE).c_str();
 998     R.Kind = toRefKind(SR.Roles, SR.Spelled);
 999     R.Container = getSymbolIDCached(SR.Container);
1000     Refs.insert(ID, R);
1001   }
1002 }
1003
1004 SymbolID SymbolCollector::getSymbolIDCached(const Decl *D) {
1005   auto It = DeclToIDCache.try_emplace(D, SymbolID{});
1006   if (It.second)
1007     It.first->second = getSymbolID(D);
1008   return It.first->second;
1009 }
1010
1011 SymbolID SymbolCollector::getSymbolIDCached(const llvm::StringRef MacroName,
1012                                             const MacroInfo *MI,
1013                                             const SourceManager &SM) {
1014   auto It = MacroToIDCache.try_emplace(MI, SymbolID{});
1015   if (It.second)
1016     It.first->second = getSymbolID(MacroName, MI, SM);
1017   return It.first->second;
1018 }
1019 } // namespace clangd
1020 } // namespace clang