clang-tools  14.0.0git
Merge.cpp
Go to the documentation of this file.
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/Logger.h"
14 #include "support/Trace.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 namespace {
26 
27 // Returns true if file defining/declaring \p S is covered by \p Index.
28 bool isIndexAuthoritative(const SymbolIndex::IndexedFiles &Index,
29  const Symbol &S) {
30  // We expect the definition to see the canonical declaration, so it seems to
31  // be enough to check only the definition if it exists.
32  const char *OwningFile =
33  S.Definition ? S.Definition.FileURI : S.CanonicalDeclaration.FileURI;
34  return (Index(OwningFile) & IndexContents::Symbols) != IndexContents::None;
35 }
36 } // namespace
37 
39  const FuzzyFindRequest &Req,
40  llvm::function_ref<void(const Symbol &)> Callback) const {
41  // We can't step through both sources in parallel. So:
42  // 1) query all dynamic symbols, slurping results into a slab
43  // 2) query the static symbols, for each one:
44  // a) if it's not in the dynamic slab, yield it directly
45  // b) if it's in the dynamic slab, merge it and yield the result
46  // 3) now yield all the dynamic symbols we haven't processed.
47  trace::Span Tracer("MergedIndex fuzzyFind");
48  bool More = false; // We'll be incomplete if either source was.
50  unsigned DynamicCount = 0;
51  unsigned StaticCount = 0;
52  unsigned MergedCount = 0;
53  // Number of results ignored due to staleness.
54  unsigned StaticDropped = 0;
55  More |= Dynamic->fuzzyFind(Req, [&](const Symbol &S) {
56  ++DynamicCount;
57  DynB.insert(S);
58  });
59  SymbolSlab Dyn = std::move(DynB).build();
60 
61  llvm::DenseSet<SymbolID> ReportedDynSymbols;
62  {
63  auto DynamicContainsFile = Dynamic->indexedFiles();
64  More |= Static->fuzzyFind(Req, [&](const Symbol &S) {
65  ++StaticCount;
66  auto DynS = Dyn.find(S.ID);
67  // If symbol also exist in the dynamic index, just merge and report.
68  if (DynS != Dyn.end()) {
69  ++MergedCount;
70  ReportedDynSymbols.insert(S.ID);
71  return Callback(mergeSymbol(*DynS, S));
72  }
73 
74  // Otherwise, if the dynamic index owns the symbol's file, it means static
75  // index is stale just drop the symbol.
76  if (isIndexAuthoritative(DynamicContainsFile, S)) {
77  ++StaticDropped;
78  return;
79  }
80 
81  // If not just report the symbol from static index as is.
82  return Callback(S);
83  });
84  }
85  SPAN_ATTACH(Tracer, "dynamic", DynamicCount);
86  SPAN_ATTACH(Tracer, "static", StaticCount);
87  SPAN_ATTACH(Tracer, "static_dropped", StaticDropped);
88  SPAN_ATTACH(Tracer, "merged", MergedCount);
89  for (const Symbol &S : Dyn)
90  if (!ReportedDynSymbols.count(S.ID))
91  Callback(S);
92  return More;
93 }
94 
96  const LookupRequest &Req,
97  llvm::function_ref<void(const Symbol &)> Callback) const {
98  trace::Span Tracer("MergedIndex lookup");
100 
101  Dynamic->lookup(Req, [&](const Symbol &S) { B.insert(S); });
102 
103  auto RemainingIDs = Req.IDs;
104  {
105  auto DynamicContainsFile = Dynamic->indexedFiles();
106  Static->lookup(Req, [&](const Symbol &S) {
107  // If we've seen the symbol before, just merge.
108  if (const Symbol *Sym = B.find(S.ID)) {
109  RemainingIDs.erase(S.ID);
110  return Callback(mergeSymbol(*Sym, S));
111  }
112 
113  // If symbol is missing in dynamic index, and dynamic index owns the
114  // symbol's file. Static index is stale, just drop the symbol.
115  if (isIndexAuthoritative(DynamicContainsFile, S))
116  return;
117 
118  // Dynamic index doesn't know about this file, just use the symbol from
119  // static index.
120  RemainingIDs.erase(S.ID);
121  Callback(S);
122  });
123  }
124  for (const auto &ID : RemainingIDs)
125  if (const Symbol *Sym = B.find(ID))
126  Callback(*Sym);
127 }
128 
130  llvm::function_ref<void(const Ref &)> Callback) const {
131  trace::Span Tracer("MergedIndex refs");
132  bool More = false;
133  uint32_t Remaining =
134  Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
135  // We don't want duplicated refs from the static/dynamic indexes,
136  // and we can't reliably deduplicate them because offsets may differ slightly.
137  // We consider the dynamic index authoritative and report all its refs,
138  // and only report static index refs from other files.
139  More |= Dynamic->refs(Req, [&](const Ref &O) {
140  Callback(O);
141  assert(Remaining != 0);
142  --Remaining;
143  });
144  if (Remaining == 0 && More)
145  return More;
146  auto DynamicContainsFile = Dynamic->indexedFiles();
147  // We return less than Req.Limit if static index returns more refs for dirty
148  // files.
149  bool StaticHadMore = Static->refs(Req, [&](const Ref &O) {
150  if ((DynamicContainsFile(O.Location.FileURI) & IndexContents::References) !=
152  return; // ignore refs that have been seen from dynamic index.
153  if (Remaining == 0) {
154  More = true;
155  return;
156  }
157  --Remaining;
158  Callback(O);
159  });
160  return More || StaticHadMore;
161 }
162 
163 llvm::unique_function<IndexContents(llvm::StringRef) const>
165  return [DynamicContainsFile{Dynamic->indexedFiles()},
166  StaticContainsFile{Static->indexedFiles()}](llvm::StringRef FileURI) {
167  return DynamicContainsFile(FileURI) | StaticContainsFile(FileURI);
168  };
169 }
170 
172  const RelationsRequest &Req,
173  llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
174  uint32_t Remaining =
175  Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
176  // Return results from both indexes but avoid duplicates.
177  // We might return stale relations from the static index;
178  // we don't currently have a good way of identifying them.
179  llvm::DenseSet<std::pair<SymbolID, SymbolID>> SeenRelations;
180  Dynamic->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
181  Callback(Subject, Object);
182  SeenRelations.insert(std::make_pair(Subject, Object.ID));
183  --Remaining;
184  });
185  if (Remaining == 0)
186  return;
187  Static->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
188  if (Remaining > 0 &&
189  !SeenRelations.count(std::make_pair(Subject, Object.ID))) {
190  --Remaining;
191  Callback(Subject, Object);
192  }
193  });
194 }
195 
196 // Returns true if \p L is (strictly) preferred to \p R (e.g. by file paths). If
197 // neither is preferred, this returns false.
198 static bool prefer(const SymbolLocation &L, const SymbolLocation &R) {
199  if (!L)
200  return false;
201  if (!R)
202  return true;
203  auto HasCodeGenSuffix = [](const SymbolLocation &Loc) {
204  constexpr static const char *CodegenSuffixes[] = {".proto"};
205  return std::any_of(std::begin(CodegenSuffixes), std::end(CodegenSuffixes),
206  [&](llvm::StringRef Suffix) {
207  return llvm::StringRef(Loc.FileURI).endswith(Suffix);
208  });
209  };
210  return HasCodeGenSuffix(L) && !HasCodeGenSuffix(R);
211 }
212 
213 Symbol mergeSymbol(const Symbol &L, const Symbol &R) {
214  assert(L.ID == R.ID);
215  // We prefer information from TUs that saw the definition.
216  // Classes: this is the def itself. Functions: hopefully the header decl.
217  // If both did (or both didn't), continue to prefer L over R.
218  bool PreferR = R.Definition && !L.Definition;
219  // Merge include headers only if both have definitions or both have no
220  // definition; otherwise, only accumulate references of common includes.
221  assert(L.Definition.FileURI && R.Definition.FileURI);
222  bool MergeIncludes =
223  bool(*L.Definition.FileURI) == bool(*R.Definition.FileURI);
224  Symbol S = PreferR ? R : L; // The target symbol we're merging into.
225  const Symbol &O = PreferR ? L : R; // The "other" less-preferred symbol.
226 
227  // Only use locations in \p O if it's (strictly) preferred.
230  if (prefer(O.Definition, S.Definition))
231  S.Definition = O.Definition;
232  S.References += O.References;
233  if (S.Signature == "")
234  S.Signature = O.Signature;
235  if (S.CompletionSnippetSuffix == "")
237  if (S.Documentation == "") {
238  // Don't accept documentation from bare forward class declarations, if there
239  // is a definition and it didn't provide one. S is often an undocumented
240  // class, and O is a non-canonical forward decl preceded by an irrelevant
241  // comment.
242  bool IsClass = S.SymInfo.Kind == index::SymbolKind::Class ||
243  S.SymInfo.Kind == index::SymbolKind::Struct ||
244  S.SymInfo.Kind == index::SymbolKind::Union;
245  if (!IsClass || !S.Definition)
247  }
248  if (S.ReturnType == "")
249  S.ReturnType = O.ReturnType;
250  if (S.Type == "")
251  S.Type = O.Type;
252  for (const auto &OI : O.IncludeHeaders) {
253  bool Found = false;
254  for (auto &SI : S.IncludeHeaders) {
255  if (SI.IncludeHeader == OI.IncludeHeader) {
256  Found = true;
257  SI.References += OI.References;
258  break;
259  }
260  }
261  if (!Found && MergeIncludes)
262  S.IncludeHeaders.emplace_back(OI.IncludeHeader, OI.References);
263  }
264 
266  S.Flags |= O.Flags;
267  return S;
268 }
269 
270 } // namespace clangd
271 } // namespace clang
Loc
SourceLocation Loc
Definition: KernelNameRestrictionCheck.cpp:45
clang::clangd::SymbolLocation
Definition: SymbolLocation.h:19
Suffix
std::string Suffix
Definition: AddUsing.cpp:112
clang::clangd::SymbolSlab::end
const_iterator end() const
Definition: Symbol.h:186
SymbolOrigin.h
clang::clangd::Symbol::ID
SymbolID ID
The ID of the symbol.
Definition: Symbol.h:38
SymbolLocation.h
Tracer
std::unique_ptr< trace::EventTracer > Tracer
Definition: TraceTests.cpp:164
clang::clangd::RelationsRequest::Limit
llvm::Optional< uint32_t > Limit
If set, limit the number of relations returned from the index.
Definition: Index.h:82
clang::clangd::SymbolIndex::indexedFiles
virtual IndexedFiles indexedFiles() const =0
clang::clangd::SymbolKind::Object
@ Object
Trace.h
clang::clangd::IndexContents::Symbols
@ Symbols
clang::clangd::FuzzyFindRequest
Definition: Index.h:27
clang::clangd::SymbolIndex::IndexedFiles
llvm::unique_function< IndexContents(llvm::StringRef) const > IndexedFiles
Returns function which checks if the specified file was used to build this index or not.
Definition: Index.h:153
clang::clangd::Symbol::References
unsigned References
The number of translation units that reference this symbol from their main file.
Definition: Symbol.h:59
clang::clangd::MergedIndex::relations
void relations(const RelationsRequest &, llvm::function_ref< void(const SymbolID &, const Symbol &)>) const override
Definition: Merge.cpp:171
clang::clangd::Symbol::ReturnType
llvm::StringRef ReturnType
Type when this symbol is used in an expression.
Definition: Symbol.h:80
clang::clangd::MergedIndex::fuzzyFind
bool fuzzyFind(const FuzzyFindRequest &, llvm::function_ref< void(const Symbol &)>) const override
Matches symbols in the index fuzzily and applies Callback on each matched symbol before returning.
Definition: Merge.cpp:38
clang::clangd::SymbolIndex::lookup
virtual void lookup(const LookupRequest &Req, llvm::function_ref< void(const Symbol &)> Callback) const =0
Looks up symbols with any of the given symbol IDs and applies Callback on each matched symbol.
clang::clangd::SymbolIndex::relations
virtual void relations(const RelationsRequest &Req, llvm::function_ref< void(const SymbolID &Subject, const Symbol &Object)> Callback) const =0
Finds all relations (S, P, O) stored in the index such that S is among Req.Subjects and P is Req....
clang::clangd::Ref::Location
SymbolLocation Location
The source location where the symbol is named.
Definition: Ref.h:89
clang::clangd::MergedIndex::refs
bool refs(const RefsRequest &, llvm::function_ref< void(const Ref &)>) const override
Finds all occurrences (e.g.
Definition: Merge.cpp:129
clang::clangd::Symbol::Origin
SymbolOrigin Origin
Where this symbol came from. Usually an index provides a constant value.
Definition: Symbol.h:61
Logger.h
clang::clangd::Symbol
The class presents a C++ symbol, e.g.
Definition: Symbol.h:36
if
if(CLANGD_ENABLE_REMOTE) generate_protos(RemoteIndexProto "Index.proto") generate_protos(MonitoringServiceProto "MonitoringService.proto" GRPC) generate_protos(RemoteIndexServiceProto "Service.proto" DEPENDS "Index.proto" GRPC) target_link_libraries(RemoteIndexServiceProto PRIVATE RemoteIndexProto MonitoringServiceProto) include_directories($
Definition: clangd/index/remote/CMakeLists.txt:1
clang::clangd::SymbolSlab::find
const_iterator find(const SymbolID &SymID) const
Definition: Symbol.cpp:37
clang::clangd::Symbol::Flags
SymbolFlag Flags
Definition: Symbol.h:128
clang::clangd::IndexContents
IndexContents
Describes what data is covered by an index.
Definition: Index.h:91
clang::clangd::Symbol::SymInfo
index::SymbolInfo SymInfo
The symbol information, like symbol kind.
Definition: Symbol.h:40
clang::clangd::SymbolLocation::FileURI
const char * FileURI
Definition: SymbolLocation.h:64
SPAN_ATTACH
#define SPAN_ATTACH(S, Name, Expr)
Attach a key-value pair to a Span event.
Definition: Trace.h:164
clang::clangd::mergeSymbol
Symbol mergeSymbol(const Symbol &L, const Symbol &R)
Definition: Merge.cpp:213
clang::clangd::prefer
static bool prefer(const SymbolLocation &L, const SymbolLocation &R)
Definition: Merge.cpp:198
Symbol.h
clang::clangd::Symbol::CanonicalDeclaration
SymbolLocation CanonicalDeclaration
The location of the preferred declaration of the symbol.
Definition: Symbol.h:56
clang::clangd::LookupRequest::IDs
llvm::DenseSet< SymbolID > IDs
Definition: Index.h:66
clang::clangd::SymbolOrigin::Merge
@ Merge
Index
const SymbolIndex * Index
Definition: Dexp.cpp:99
clang::clangd::SymbolIndex::refs
virtual bool refs(const RefsRequest &Req, llvm::function_ref< void(const Ref &)> Callback) const =0
Finds all occurrences (e.g.
clang::clangd::Symbol::CompletionSnippetSuffix
llvm::StringRef CompletionSnippetSuffix
What to insert when completing this symbol, after the symbol name.
Definition: Symbol.h:74
clang::clangd::LookupRequest
Definition: Index.h:65
clang::clangd::IndexContents::References
@ References
clang::clangd::IndexContents::None
@ None
ID
static char ID
Definition: Logger.cpp:74
clang::clangd::Ref
Represents a symbol occurrence in the source file.
Definition: Ref.h:87
clang::clangd::MergedIndex::indexedFiles
llvm::unique_function< IndexContents(llvm::StringRef) const > indexedFiles() const override
Definition: Merge.cpp:164
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::clangd::RefsRequest::Limit
llvm::Optional< uint32_t > Limit
If set, limit the number of refers returned from the index.
Definition: Index.h:75
clang::clangd::Symbol::Definition
SymbolLocation Definition
The location of the symbol's definition, if one was found.
Definition: Symbol.h:47
clang::clangd::Callback
llvm::unique_function< void(llvm::Expected< T >)> Callback
A Callback<T> is a void function that accepts Expected<T>.
Definition: Function.h:28
clang::clangd::RelationsRequest
Definition: Index.h:78
Merge.h
clang::clangd::SymbolSlab::Builder
SymbolSlab::Builder is a mutable container that can 'freeze' to SymbolSlab.
Definition: Symbol.h:200
ns1::ns2::B
@ B
Definition: CategoricalFeature.h:3
clang::clangd::SymbolSlab
An immutable symbol container that stores a set of symbols.
Definition: Symbol.h:177
clang::clangd::SymbolID
Definition: SymbolID.h:32
clang::clangd::Symbol::Signature
llvm::StringRef Signature
A brief description of the symbol that can be appended in the completion candidate list.
Definition: Symbol.h:65
clang::clangd::Symbol::Type
llvm::StringRef Type
Raw representation of the OpaqueType of the symbol, used for scoring purposes.
Definition: Symbol.h:85
clang::clangd::RefsRequest
Definition: Index.h:69
clang::clangd::Symbol::IncludeHeaders
llvm::SmallVector< IncludeHeaderWithReferences, 1 > IncludeHeaders
One Symbol can potentially be included via different headers.
Definition: Symbol.h:111
clang::clangd::MergedIndex::lookup
void lookup(const LookupRequest &, llvm::function_ref< void(const Symbol &)>) const override
Looks up symbols with any of the given symbol IDs and applies Callback on each matched symbol.
Definition: Merge.cpp:95
clang::clangd::Symbol::Documentation
llvm::StringRef Documentation
Documentation including comment for the symbol declaration.
Definition: Symbol.h:76
clang::clangd::SymbolIndex::fuzzyFind
virtual bool fuzzyFind(const FuzzyFindRequest &Req, llvm::function_ref< void(const Symbol &)> Callback) const =0
Matches symbols in the index fuzzily and applies Callback on each matched symbol before returning.
clang::clangd::SymbolSlab::Builder::insert
void insert(const Symbol &S)
Adds a symbol, overwriting any existing one with the same ID.
Definition: Symbol.cpp:50
clang::clangd::trace::Span
Records an event whose duration is the lifetime of the Span object.
Definition: Trace.h:143