clang-tools  15.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/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 
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.
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 
92  const LookupRequest &Req,
93  llvm::function_ref<void(const Symbol &)> Callback) const {
94  trace::Span Tracer("MergedIndex lookup");
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 
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) !=
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>
160  return [DynamicContainsFile{Dynamic->indexedFiles()},
161  StaticContainsFile{Static->indexedFiles()}](llvm::StringRef FileURI) {
162  return DynamicContainsFile(FileURI) | StaticContainsFile(FileURI);
163  };
164 }
165 
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 std::any_of(std::begin(CodegenSuffixes), std::end(CodegenSuffixes),
200  [&](llvm::StringRef Suffix) {
201  return llvm::StringRef(Loc.FileURI).endswith(Suffix);
202  });
203  };
204  return HasCodeGenSuffix(L) && !HasCodeGenSuffix(R);
205 }
206 
207 Symbol mergeSymbol(const Symbol &L, const Symbol &R) {
208  assert(L.ID == R.ID);
209  // We prefer information from TUs that saw the definition.
210  // Classes: this is the def itself. Functions: hopefully the header decl.
211  // If both did (or both didn't), continue to prefer L over R.
212  bool PreferR = R.Definition && !L.Definition;
213  // Merge include headers only if both have definitions or both have no
214  // definition; otherwise, only accumulate references of common includes.
215  assert(L.Definition.FileURI && R.Definition.FileURI);
216  bool MergeIncludes =
217  bool(*L.Definition.FileURI) == bool(*R.Definition.FileURI);
218  Symbol S = PreferR ? R : L; // The target symbol we're merging into.
219  const Symbol &O = PreferR ? L : R; // The "other" less-preferred symbol.
220 
221  // Only use locations in \p O if it's (strictly) preferred.
224  if (prefer(O.Definition, S.Definition))
225  S.Definition = O.Definition;
226  S.References += O.References;
227  if (S.Signature == "")
228  S.Signature = O.Signature;
229  if (S.CompletionSnippetSuffix == "")
231  if (S.Documentation == "") {
232  // Don't accept documentation from bare forward class declarations, if there
233  // is a definition and it didn't provide one. S is often an undocumented
234  // class, and O is a non-canonical forward decl preceded by an irrelevant
235  // comment.
236  bool IsClass = S.SymInfo.Kind == index::SymbolKind::Class ||
237  S.SymInfo.Kind == index::SymbolKind::Struct ||
238  S.SymInfo.Kind == index::SymbolKind::Union;
239  if (!IsClass || !S.Definition)
241  }
242  if (S.ReturnType == "")
243  S.ReturnType = O.ReturnType;
244  if (S.Type == "")
245  S.Type = O.Type;
246  for (const auto &OI : O.IncludeHeaders) {
247  bool Found = false;
248  for (auto &SI : S.IncludeHeaders) {
249  if (SI.IncludeHeader == OI.IncludeHeader) {
250  Found = true;
251  SI.References += OI.References;
252  break;
253  }
254  }
255  if (!Found && MergeIncludes)
256  S.IncludeHeaders.emplace_back(OI.IncludeHeader, OI.References);
257  }
258 
260  S.Flags |= O.Flags;
261  return S;
262 }
263 
264 } // namespace clangd
265 } // namespace clang
Loc
SourceLocation Loc
Definition: KernelNameRestrictionCheck.cpp:45
clang::clangd::SymbolLocation
Definition: SymbolLocation.h:19
Suffix
std::string Suffix
Definition: AddUsing.cpp:113
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:161
clang::clangd::RelationsRequest::Limit
llvm::Optional< uint32_t > Limit
If set, limit the number of relations returned from the index.
Definition: Index.h:84
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:26
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:155
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:166
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:34
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::SymbolOrigin::Merge
@ Merge
clang::clangd::Ref::Location
SymbolLocation Location
The source location where the symbol is named.
Definition: Ref.h:87
clang::clangd::MergedIndex::refs
bool refs(const RefsRequest &, llvm::function_ref< void(const Ref &)>) const override
Finds all occurrences (e.g.
Definition: Merge.cpp:125
clang::clangd::Symbol::Origin
SymbolOrigin Origin
Where this symbol came from. Usually an index provides a constant value.
Definition: Symbol.h:61
clang::clangd::Symbol
The class presents a C++ symbol, e.g.
Definition: Symbol.h:36
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:93
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:207
clang::clangd::prefer
static bool prefer(const SymbolLocation &L, const SymbolLocation &R)
Definition: Merge.cpp:192
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:65
Index
const SymbolIndex * Index
Definition: Dexp.cpp:98
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:64
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:85
clang::clangd::MergedIndex::indexedFiles
llvm::unique_function< IndexContents(llvm::StringRef) const > indexedFiles() const override
Definition: Merge.cpp:159
if
if(CLANG_PLUGIN_SUPPORT) export_executable_symbols_for_plugins(clang-tidy) endif() install(PROGRAMS clang-tidy-diff.py DESTINATION "$
Definition: clang-tidy/tool/CMakeLists.txt:59
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:74
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:80
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:68
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:91
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