| 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 |
llvm::unique_function<IndexContents(llvm::StringRef) const> |
| 159 |
MergedIndex::indexedFiles() const { |
| 160 |
return [DynamicContainsFile{Dynamic->indexedFiles()}, |
| 161 |
StaticContainsFile{Static->indexedFiles()}](llvm::StringRef FileURI) { |
| 162 |
return DynamicContainsFile(FileURI) | StaticContainsFile(FileURI); |
| 163 |
}; |
| 164 |
} |
| 165 |
|
| 166 |
void MergedIndex::relations( |
| 167 |
const RelationsRequest &Req, |
| 168 |
llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const { |
| 169 |
uint32_t Remaining = Req.Limit.value_or(std::numeric_limits<uint32_t>::max()); |
| 170 |
// Return results from both indexes but avoid duplicates. |
| 171 |
// We might return stale relations from the static index; |
| 172 |
// we don't currently have a good way of identifying them. |
| 173 |
llvm::DenseSet<std::pair<SymbolID, SymbolID>> SeenRelations; |
| 174 |
Dynamic->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) { |
| 175 |
Callback(Subject, Object); |
| 176 |
SeenRelations.insert(std::make_pair(Subject, Object.ID)); |
| 177 |
--Remaining; |
| 178 |
}); |
| 179 |
if (Remaining == 0) |
| 180 |
return; |
| 181 |
Static->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) { |
| 182 |
if (Remaining > 0 && |
| 183 |
!SeenRelations.count(std::make_pair(Subject, Object.ID))) { |
| 184 |
--Remaining; |
| 185 |
Callback(Subject, Object); |
| 186 |
} |
| 187 |
}); |
| 188 |
} |
| 189 |
|
| 190 |
// Returns true if \p L is (strictly) preferred to \p R (e.g. by file paths). If |
| 191 |
// neither is preferred, this returns false. |
| 192 |
static bool prefer(const SymbolLocation &L, const SymbolLocation &R) { |
| 193 |
if (!L) |
| 194 |
return false; |
| 195 |
if (!R) |
| 196 |
return true; |
| 197 |
auto HasCodeGenSuffix = [](const SymbolLocation &Loc) { |
| 198 |
constexpr static const char *CodegenSuffixes[] = {".proto"}; |
| 199 |
return llvm::any_of(CodegenSuffixes, [&](llvm::StringRef Suffix) { |
| 200 |
return llvm::StringRef(Loc.FileURI).ends_with(Suffix); |
| 201 |
}); |
| 202 |
}; |
| 203 |
return HasCodeGenSuffix(L) && !HasCodeGenSuffix(R); |
| 204 |
} |
| 205 |
|
| 206 |
Symbol mergeSymbol(const Symbol &L, const Symbol &R) { |
| 207 |
assert(L.ID == R.ID); |
| 208 |
// We prefer information from TUs that saw the definition. |
| 209 |
// Classes: this is the def itself. Functions: hopefully the header decl. |
| 210 |
// If both did (or both didn't), continue to prefer L over R. |
| 211 |
bool PreferR = R.Definition && !L.Definition; |
| 212 |
// Merge include headers only if both have definitions or both have no |
| 213 |
// definition; otherwise, only accumulate references of common includes. |
| 214 |
assert(L.Definition.FileURI && R.Definition.FileURI); |
| 215 |
bool MergeIncludes = |
| 216 |
bool(*L.Definition.FileURI) == bool(*R.Definition.FileURI); |
| 217 |
Symbol S = PreferR ? R : L; // The target symbol we're merging into. |
| 218 |
const Symbol &O = PreferR ? L : R; // The "other" less-preferred symbol. |
| 219 |
|
| 220 |
// Only use locations in \p O if it's (strictly) preferred. |
| 221 |
if (prefer(O.CanonicalDeclaration, S.CanonicalDeclaration)) |
| 222 |
S.CanonicalDeclaration = O.CanonicalDeclaration; |
| 223 |
if (prefer(O.Definition, S.Definition)) |
| 224 |
S.Definition = O.Definition; |
| 225 |
S.References += O.References; |
| 226 |
if (S.Signature == "") |
| 227 |
S.Signature = O.Signature; |
| 228 |
if (S.CompletionSnippetSuffix == "") |
| 229 |
S.CompletionSnippetSuffix = O.CompletionSnippetSuffix; |
| 230 |
if (S.Documentation == "") { |
| 231 |
// Don't accept documentation from bare forward class declarations, if there |
| 232 |
// is a definition and it didn't provide one. S is often an undocumented |
| 233 |
// class, and O is a non-canonical forward decl preceded by an irrelevant |
| 234 |
// comment. |
| 235 |
bool IsClass = S.SymInfo.Kind == index::SymbolKind::Class || |
| 236 |
S.SymInfo.Kind == index::SymbolKind::Struct || |
| 237 |
S.SymInfo.Kind == index::SymbolKind::Union; |
| 238 |
if (!IsClass || !S.Definition) |
| 239 |
S.Documentation = O.Documentation; |
| 240 |
} |
| 241 |
if (S.ReturnType == "") |
| 242 |
S.ReturnType = O.ReturnType; |
| 243 |
if (S.Type == "") |
| 244 |
S.Type = O.Type; |
| 245 |
for (const auto &OI : O.IncludeHeaders) { |
| 246 |
bool Found = false; |
| 247 |
for (auto &SI : S.IncludeHeaders) { |
| 248 |
if (SI.IncludeHeader == OI.IncludeHeader) { |
| 249 |
Found = true; |
| 250 |
SI.References += OI.References; |
| 251 |
SI.SupportedDirectives |= OI.SupportedDirectives; |
| 252 |
break; |
| 253 |
} |
| 254 |
} |
| 255 |
if (!Found && MergeIncludes) |
| 256 |
S.IncludeHeaders.emplace_back(OI.IncludeHeader, OI.References, |
| 257 |
OI.supportedDirectives()); |
| 258 |
} |
| 259 |
|
| 260 |
S.Origin |= O.Origin | SymbolOrigin::Merge; |
| 261 |
S.Flags |= O.Flags; |
| 262 |
return S; |
| 263 |
} |
| 264 |
|
| 265 |
} // namespace clangd |
| 266 |
} // namespace clang |