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