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 "Logger.h" 11 #include "Trace.h" 12 #include "index/Symbol.h" 13 #include "index/SymbolLocation.h" 14 #include "index/SymbolOrigin.h" 15 #include "llvm/ADT/STLExtras.h" 16 #include "llvm/ADT/StringRef.h" 17 #include "llvm/ADT/StringSet.h" 18 #include "llvm/Support/raw_ostream.h" 19 #include <algorithm> 20 #include <iterator> 21 22 namespace clang { 23 namespace clangd { 24 25 // FIXME: Deleted symbols in dirty files are still returned (from Static). 26 // To identify these eliminate these, we should: 27 // - find the generating file from each Symbol which is Static-only 28 // - ask Dynamic if it has that file (needs new SymbolIndex method) 29 // - if so, drop the Symbol. 30 bool MergedIndex::fuzzyFind( 31 const FuzzyFindRequest &Req, 32 llvm::function_ref<void(const Symbol &)> Callback) const { 33 // We can't step through both sources in parallel. So: 34 // 1) query all dynamic symbols, slurping results into a slab 35 // 2) query the static symbols, for each one: 36 // a) if it's not in the dynamic slab, yield it directly 37 // b) if it's in the dynamic slab, merge it and yield the result 38 // 3) now yield all the dynamic symbols we haven't processed. 39 trace::Span Tracer("MergedIndex fuzzyFind"); 40 bool More = false; // We'll be incomplete if either source was. 41 SymbolSlab::Builder DynB; 42 unsigned DynamicCount = 0; 43 unsigned StaticCount = 0; 44 unsigned MergedCount = 0; 45 More |= Dynamic->fuzzyFind(Req, [&](const Symbol &S) { 46 ++DynamicCount; 47 DynB.insert(S); 48 }); 49 SymbolSlab Dyn = std::move(DynB).build(); 50 51 llvm::DenseSet<SymbolID> SeenDynamicSymbols; 52 More |= Static->fuzzyFind(Req, [&](const Symbol &S) { 53 auto DynS = Dyn.find(S.ID); 54 ++StaticCount; 55 if (DynS == Dyn.end()) 56 return Callback(S); 57 ++MergedCount; 58 SeenDynamicSymbols.insert(S.ID); 59 Callback(mergeSymbol(*DynS, S)); 60 }); 61 SPAN_ATTACH(Tracer, "dynamic", DynamicCount); 62 SPAN_ATTACH(Tracer, "static", StaticCount); 63 SPAN_ATTACH(Tracer, "merged", MergedCount); 64 for (const Symbol &S : Dyn) 65 if (!SeenDynamicSymbols.count(S.ID)) 66 Callback(S); 67 return More; 68 } 69 70 void MergedIndex::lookup( 71 const LookupRequest &Req, 72 llvm::function_ref<void(const Symbol &)> Callback) const { 73 trace::Span Tracer("MergedIndex lookup"); 74 SymbolSlab::Builder B; 75 76 Dynamic->lookup(Req, [&](const Symbol &S) { B.insert(S); }); 77 78 auto RemainingIDs = Req.IDs; 79 Static->lookup(Req, [&](const Symbol &S) { 80 const Symbol *Sym = B.find(S.ID); 81 RemainingIDs.erase(S.ID); 82 if (!Sym) 83 Callback(S); 84 else 85 Callback(mergeSymbol(*Sym, S)); 86 }); 87 for (const auto &ID : RemainingIDs) 88 if (const Symbol *Sym = B.find(ID)) 89 Callback(*Sym); 90 } 91 92 void MergedIndex::refs(const RefsRequest &Req, 93 llvm::function_ref<void(const Ref &)> Callback) const { 94 trace::Span Tracer("MergedIndex refs"); 95 uint32_t Remaining = 96 Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max()); 97 // We don't want duplicated refs from the static/dynamic indexes, 98 // and we can't reliably duplicate them because offsets may differ slightly. 99 // We consider the dynamic index authoritative and report all its refs, 100 // and only report static index refs from other files. 101 // 102 // FIXME: The heuristic fails if the dynamic index contains a file, but all 103 // refs were removed (we will report stale ones from the static index). 104 // Ultimately we should explicit check which index has the file instead. 105 llvm::StringSet<> DynamicIndexFileURIs; 106 Dynamic->refs(Req, [&](const Ref &O) { 107 DynamicIndexFileURIs.insert(O.Location.FileURI); 108 Callback(O); 109 --Remaining; 110 }); 111 if (Remaining == 0) 112 return; 113 // We return less than Req.Limit if static index returns more refs for dirty 114 // files. 115 Static->refs(Req, [&](const Ref &O) { 116 if (Remaining > 0 && !DynamicIndexFileURIs.count(O.Location.FileURI)) { 117 --Remaining; 118 Callback(O); 119 } 120 }); 121 } 122 123 // Returns true if \p L is (strictly) preferred to \p R (e.g. by file paths). If 124 // neither is preferred, this returns false. 125 bool prefer(const SymbolLocation &L, const SymbolLocation &R) { 126 if (!L) 127 return false; 128 if (!R) 129 return true; 130 auto HasCodeGenSuffix = [](const SymbolLocation &Loc) { 131 constexpr static const char *CodegenSuffixes[] = {".proto"}; 132 return std::any_of(std::begin(CodegenSuffixes), std::end(CodegenSuffixes), 133 [&](llvm::StringRef Suffix) { 134 return llvm::StringRef(Loc.FileURI).endswith(Suffix); 135 }); 136 }; 137 return HasCodeGenSuffix(L) && !HasCodeGenSuffix(R); 138 } 139 140 Symbol mergeSymbol(const Symbol &L, const Symbol &R) { 141 assert(L.ID == R.ID); 142 // We prefer information from TUs that saw the definition. 143 // Classes: this is the def itself. Functions: hopefully the header decl. 144 // If both did (or both didn't), continue to prefer L over R. 145 bool PreferR = R.Definition && !L.Definition; 146 // Merge include headers only if both have definitions or both have no 147 // definition; otherwise, only accumulate references of common includes. 148 assert(L.Definition.FileURI && R.Definition.FileURI); 149 bool MergeIncludes = 150 bool(*L.Definition.FileURI) == bool(*R.Definition.FileURI); 151 Symbol S = PreferR ? R : L; // The target symbol we're merging into. 152 const Symbol &O = PreferR ? L : R; // The "other" less-preferred symbol. 153 154 // Only use locations in \p O if it's (strictly) preferred. 155 if (prefer(O.CanonicalDeclaration, S.CanonicalDeclaration)) 156 S.CanonicalDeclaration = O.CanonicalDeclaration; 157 if (prefer(O.Definition, S.Definition)) 158 S.Definition = O.Definition; 159 S.References += O.References; 160 if (S.Signature == "") 161 S.Signature = O.Signature; 162 if (S.CompletionSnippetSuffix == "") 163 S.CompletionSnippetSuffix = O.CompletionSnippetSuffix; 164 if (S.Documentation == "") 165 S.Documentation = O.Documentation; 166 if (S.ReturnType == "") 167 S.ReturnType = O.ReturnType; 168 if (S.Type == "") 169 S.Type = O.Type; 170 for (const auto &OI : O.IncludeHeaders) { 171 bool Found = false; 172 for (auto &SI : S.IncludeHeaders) { 173 if (SI.IncludeHeader == OI.IncludeHeader) { 174 Found = true; 175 SI.References += OI.References; 176 break; 177 } 178 } 179 if (!Found && MergeIncludes) 180 S.IncludeHeaders.emplace_back(OI.IncludeHeader, OI.References); 181 } 182 183 S.Origin |= O.Origin | SymbolOrigin::Merge; 184 S.Flags |= O.Flags; 185 return S; 186 } 187 188 } // namespace clangd 189 } // namespace clang 190