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

   1 //===--- Merge.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 "Merge.h"
  10 #include "index/Symbol.h"
  11 #include "index/SymbolLocation.h"
  12 #include "index/SymbolOrigin.h"
  13 #include "support/Trace.h"
  14 #include "llvm/ADT/StringRef.h"
  15 #include <algorithm>
  16 #include <iterator>
  17
  18 namespace clang {
  19 namespace clangd {
  20
  21 namespace {
  22
  23 // Returns true if file defining/declaring \p S is covered by \p Index.
  24 bool isIndexAuthoritative(const SymbolIndex::IndexedFiles &Index,
  25                           const Symbol &S) {
  26   // We expect the definition to see the canonical declaration, so it seems to
  27   // be enough to check only the definition if it exists.
  28   const char *OwningFile =
  29       S.Definition ? S.Definition.FileURI : S.CanonicalDeclaration.FileURI;
  30   return (Index(OwningFile) & IndexContents::Symbols) != IndexContents::None;
  31 }
  32 } // namespace
  33
  34 bool MergedIndex::fuzzyFind(
  35     const FuzzyFindRequest &Req,
  36     llvm::function_ref<void(const Symbol &)> Callback) const {
  37   // We can't step through both sources in parallel. So:
  38   //  1) query all dynamic symbols, slurping results into a slab
  39   //  2) query the static symbols, for each one:
  40   //    a) if it's not in the dynamic slab, yield it directly
  41   //    b) if it's in the dynamic slab, merge it and yield the result
  42   //  3) now yield all the dynamic symbols we haven't processed.
  43   trace::Span Tracer("MergedIndex fuzzyFind");
  44   bool More = false; // We'll be incomplete if either source was.
  45   SymbolSlab::Builder DynB;
  46   unsigned DynamicCount = 0;
  47   unsigned StaticCount = 0;
  48   unsigned MergedCount = 0;
  49   // Number of results ignored due to staleness.
  50   unsigned StaticDropped = 0;
  51   More |= Dynamic->fuzzyFind(Req, [&](const Symbol &S) {
  52     ++DynamicCount;
  53     DynB.insert(S);
  54   });
  55   SymbolSlab Dyn = std::move(DynB).build();
  56
  57   llvm::DenseSet<SymbolID> ReportedDynSymbols;
  58   {
  59     auto DynamicContainsFile = Dynamic->indexedFiles();
  60     More |= Static->fuzzyFind(Req, [&](const Symbol &S) {
  61       ++StaticCount;
  62       auto DynS = Dyn.find(S.ID);
  63       // If symbol also exist in the dynamic index, just merge and report.
  64       if (DynS != Dyn.end()) {
  65         ++MergedCount;
  66         ReportedDynSymbols.insert(S.ID);
  67         return Callback(mergeSymbol(*DynS, S));
  68       }
  69
  70       // Otherwise, if the dynamic index owns the symbol's file, it means static
  71       // index is stale just drop the symbol.
  72       if (isIndexAuthoritative(DynamicContainsFile, S)) {
  73         ++StaticDropped;
  74         return;
  75       }
  76
  77       // If not just report the symbol from static index as is.
  78       return Callback(S);
  79     });
  80   }
  81   SPAN_ATTACH(Tracer, "dynamic", DynamicCount);
  82   SPAN_ATTACH(Tracer, "static", StaticCount);
  83   SPAN_ATTACH(Tracer, "static_dropped", StaticDropped);
  84   SPAN_ATTACH(Tracer, "merged", MergedCount);
  85   for (const Symbol &S : Dyn)
  86     if (!ReportedDynSymbols.count(S.ID))
  87       Callback(S);
  88   return More;
  89 }
  90
  91 void MergedIndex::lookup(
  92     const LookupRequest &Req,
  93     llvm::function_ref<void(const Symbol &)> Callback) const {
  94   trace::Span Tracer("MergedIndex lookup");
  95   SymbolSlab::Builder B;
  96
  97   Dynamic->lookup(Req, [&](const Symbol &S) { B.insert(S); });
  98
  99   auto RemainingIDs = Req.IDs;
 100   {
 101     auto DynamicContainsFile = Dynamic->indexedFiles();
 102     Static->lookup(Req, [&](const Symbol &S) {
 103       // If we've seen the symbol before, just merge.
 104       if (const Symbol *Sym = B.find(S.ID)) {
 105         RemainingIDs.erase(S.ID);
 106         return Callback(mergeSymbol(*Sym, S));
 107       }
 108
 109       // If symbol is missing in dynamic index, and dynamic index owns the
 110       // symbol's file. Static index is stale, just drop the symbol.
 111       if (isIndexAuthoritative(DynamicContainsFile, S))
 112         return;
 113
 114       // Dynamic index doesn't know about this file, just use the symbol from
 115       // static index.
 116       RemainingIDs.erase(S.ID);
 117       Callback(S);
 118     });
 119   }
 120   for (const auto &ID : RemainingIDs)
 121     if (const Symbol *Sym = B.find(ID))
 122       Callback(*Sym);
 123 }
 124
 125 bool MergedIndex::refs(const RefsRequest &Req,
 126                        llvm::function_ref<void(const Ref &)> Callback) const {
 127   trace::Span Tracer("MergedIndex refs");
 128   bool More = false;
 129   uint32_t Remaining = Req.Limit.value_or(std::numeric_limits<uint32_t>::max());
 130   // We don't want duplicated refs from the static/dynamic indexes,
 131   // and we can't reliably deduplicate them because offsets may differ slightly.
 132   // We consider the dynamic index authoritative and report all its refs,
 133   // and only report static index refs from other files.
 134   More |= Dynamic->refs(Req, [&](const Ref &O) {
 135     Callback(O);
 136     assert(Remaining != 0);
 137     --Remaining;
 138   });
 139   if (Remaining == 0 && More)
 140     return More;
 141   auto DynamicContainsFile = Dynamic->indexedFiles();
 142   // We return less than Req.Limit if static index returns more refs for dirty
 143   // files.
 144   bool StaticHadMore = Static->refs(Req, [&](const Ref &O) {
 145     if ((DynamicContainsFile(O.Location.FileURI) & IndexContents::References) !=
 146         IndexContents::None)
 147       return; // ignore refs that have been seen from dynamic index.
 148     if (Remaining == 0) {
 149       More = true;
 150       return;
 151     }
 152     --Remaining;
 153     Callback(O);
 154   });
 155   return More || StaticHadMore;
 156 }
 157
 158 bool MergedIndex::containedRefs(
 159     const ContainedRefsRequest &Req,
 160     llvm::function_ref<void(const ContainedRefsResult &)> Callback) const {
 161   trace::Span Tracer("MergedIndex refersTo");
 162   bool More = false;
 163   uint32_t Remaining = Req.Limit.value_or(std::numeric_limits<uint32_t>::max());
 164   // We don't want duplicated refs from the static/dynamic indexes,
 165   // and we can't reliably deduplicate them because offsets may differ slightly.
 166   // We consider the dynamic index authoritative and report all its refs,
 167   // and only report static index refs from other files.
 168   More |= Dynamic->containedRefs(Req, [&](const auto &O) {
 169     Callback(O);
 170     assert(Remaining != 0);
 171     --Remaining;
 172   });
 173   if (Remaining == 0 && More)
 174     return More;
 175   auto DynamicContainsFile = Dynamic->indexedFiles();
 176   // We return less than Req.Limit if static index returns more refs for dirty
 177   // files.
 178   bool StaticHadMore = Static->containedRefs(Req, [&](const auto &O) {
 179     if ((DynamicContainsFile(O.Location.FileURI) & IndexContents::References) !=
 180         IndexContents::None)
 181       return; // ignore refs that have been seen from dynamic index.
 182     if (Remaining == 0) {
 183       More = true;
 184       return;
 185     }
 186     --Remaining;
 187     Callback(O);
 188   });
 189   return More || StaticHadMore;
 190 }
 191
 192 llvm::unique_function<IndexContents(llvm::StringRef) const>
 193 MergedIndex::indexedFiles() const {
 194   return [DynamicContainsFile{Dynamic->indexedFiles()},
 195           StaticContainsFile{Static->indexedFiles()}](llvm::StringRef FileURI) {
 196     return DynamicContainsFile(FileURI) | StaticContainsFile(FileURI);
 197   };
 198 }
 199
 200 void MergedIndex::relations(
 201     const RelationsRequest &Req,
 202     llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
 203   uint32_t Remaining = Req.Limit.value_or(std::numeric_limits<uint32_t>::max());
 204   // Return results from both indexes but avoid duplicates.
 205   // We might return stale relations from the static index;
 206   // we don't currently have a good way of identifying them.
 207   llvm::DenseSet<std::pair<SymbolID, SymbolID>> SeenRelations;
 208   Dynamic->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
 209     Callback(Subject, Object);
 210     SeenRelations.insert(std::make_pair(Subject, Object.ID));
 211     --Remaining;
 212   });
 213   if (Remaining == 0)
 214     return;
 215   Static->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
 216     if (Remaining > 0 &&
 217         !SeenRelations.count(std::make_pair(Subject, Object.ID))) {
 218       --Remaining;
 219       Callback(Subject, Object);
 220     }
 221   });
 222 }
 223
 224 // Returns true if \p L is (strictly) preferred to \p R (e.g. by file paths). If
 225 // neither is preferred, this returns false.
 226 static bool prefer(const SymbolLocation &L, const SymbolLocation &R) {
 227   if (!L)
 228     return false;
 229   if (!R)
 230     return true;
 231   auto HasCodeGenSuffix = [](const SymbolLocation &Loc) {
 232     constexpr static const char *CodegenSuffixes[] = {".proto"};
 233     return llvm::any_of(CodegenSuffixes, [&](llvm::StringRef Suffix) {
 234       return llvm::StringRef(Loc.FileURI).ends_with(Suffix);
 235     });
 236   };
 237   return HasCodeGenSuffix(L) && !HasCodeGenSuffix(R);
 238 }
 239
 240 Symbol mergeSymbol(const Symbol &L, const Symbol &R) {
 241   assert(L.ID == R.ID);
 242   // We prefer information from TUs that saw the definition.
 243   // Classes: this is the def itself. Functions: hopefully the header decl.
 244   // If both did (or both didn't), continue to prefer L over R.
 245   bool PreferR = R.Definition && !L.Definition;
 246   // Merge include headers only if both have definitions or both have no
 247   // definition; otherwise, only accumulate references of common includes.
 248   assert(L.Definition.FileURI && R.Definition.FileURI);
 249   bool MergeIncludes =
 250       bool(*L.Definition.FileURI) == bool(*R.Definition.FileURI);
 251   Symbol S = PreferR ? R : L;        // The target symbol we're merging into.
 252   const Symbol &O = PreferR ? L : R; // The "other" less-preferred symbol.
 253
 254   // Only use locations in \p O if it's (strictly) preferred.
 255   if (prefer(O.CanonicalDeclaration, S.CanonicalDeclaration))
 256     S.CanonicalDeclaration = O.CanonicalDeclaration;
 257   if (prefer(O.Definition, S.Definition))
 258     S.Definition = O.Definition;
 259   S.References += O.References;
 260   if (S.Signature == "")
 261     S.Signature = O.Signature;
 262   if (S.CompletionSnippetSuffix == "")
 263     S.CompletionSnippetSuffix = O.CompletionSnippetSuffix;
 264   if (S.Documentation == "") {
 265     // Don't accept documentation from bare forward class declarations, if there
 266     // is a definition and it didn't provide one. S is often an undocumented
 267     // class, and O is a non-canonical forward decl preceded by an irrelevant
 268     // comment.
 269     bool IsClass = S.SymInfo.Kind == index::SymbolKind::Class ||
 270                    S.SymInfo.Kind == index::SymbolKind::Struct ||
 271                    S.SymInfo.Kind == index::SymbolKind::Union;
 272     if (!IsClass || !S.Definition)
 273       S.Documentation = O.Documentation;
 274   }
 275   if (S.ReturnType == "")
 276     S.ReturnType = O.ReturnType;
 277   if (S.Type == "")
 278     S.Type = O.Type;
 279   for (const auto &OI : O.IncludeHeaders) {
 280     bool Found = false;
 281     for (auto &SI : S.IncludeHeaders) {
 282       if (SI.IncludeHeader == OI.IncludeHeader) {
 283         Found = true;
 284         SI.References += OI.References;
 285         SI.SupportedDirectives |= OI.SupportedDirectives;
 286         break;
 287       }
 288     }
 289     if (!Found && MergeIncludes)
 290       S.IncludeHeaders.emplace_back(OI.IncludeHeader, OI.References,
 291                                     OI.supportedDirectives());
 292   }
 293
 294   S.Origin |= O.Origin | SymbolOrigin::Merge;
 295   S.Flags |= O.Flags;
 296   return S;
 297 }
 298
 299 } // namespace clangd
 300 } // namespace clang