clang-tools  10.0.0svn
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 "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.
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.
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 
71  const LookupRequest &Req,
72  llvm::function_ref<void(const Symbol &)> Callback) const {
73  trace::Span Tracer("MergedIndex lookup");
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 
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 deduplicate 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 
124  const RelationsRequest &Req,
125  llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
126  uint32_t Remaining =
127  Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
128  // Return results from both indexes but avoid duplicates.
129  // We might return stale relations from the static index;
130  // we don't currently have a good way of identifying them.
131  llvm::DenseSet<std::pair<SymbolID, SymbolID>> SeenRelations;
132  Dynamic->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
133  Callback(Subject, Object);
134  SeenRelations.insert(std::make_pair(Subject, Object.ID));
135  --Remaining;
136  });
137  if (Remaining == 0)
138  return;
139  Static->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
140  if (Remaining > 0 &&
141  !SeenRelations.count(std::make_pair(Subject, Object.ID))) {
142  --Remaining;
143  Callback(Subject, Object);
144  }
145  });
146 }
147 
148 // Returns true if \p L is (strictly) preferred to \p R (e.g. by file paths). If
149 // neither is preferred, this returns false.
150 bool prefer(const SymbolLocation &L, const SymbolLocation &R) {
151  if (!L)
152  return false;
153  if (!R)
154  return true;
155  auto HasCodeGenSuffix = [](const SymbolLocation &Loc) {
156  constexpr static const char *CodegenSuffixes[] = {".proto"};
157  return std::any_of(std::begin(CodegenSuffixes), std::end(CodegenSuffixes),
158  [&](llvm::StringRef Suffix) {
159  return llvm::StringRef(Loc.FileURI).endswith(Suffix);
160  });
161  };
162  return HasCodeGenSuffix(L) && !HasCodeGenSuffix(R);
163 }
164 
165 Symbol mergeSymbol(const Symbol &L, const Symbol &R) {
166  assert(L.ID == R.ID);
167  // We prefer information from TUs that saw the definition.
168  // Classes: this is the def itself. Functions: hopefully the header decl.
169  // If both did (or both didn't), continue to prefer L over R.
170  bool PreferR = R.Definition && !L.Definition;
171  // Merge include headers only if both have definitions or both have no
172  // definition; otherwise, only accumulate references of common includes.
173  assert(L.Definition.FileURI && R.Definition.FileURI);
174  bool MergeIncludes =
175  bool(*L.Definition.FileURI) == bool(*R.Definition.FileURI);
176  Symbol S = PreferR ? R : L; // The target symbol we're merging into.
177  const Symbol &O = PreferR ? L : R; // The "other" less-preferred symbol.
178 
179  // Only use locations in \p O if it's (strictly) preferred.
182  if (prefer(O.Definition, S.Definition))
183  S.Definition = O.Definition;
184  S.References += O.References;
185  if (S.Signature == "")
186  S.Signature = O.Signature;
187  if (S.CompletionSnippetSuffix == "")
189  // Don't accept documentation from bare forward declarations, if there is a
190  // definition and it didn't provide one. S is often an undocumented class,
191  // and O is a non-canonical forward decl preceded by an irrelevant comment.
192  if (S.Documentation == "" && !S.Definition)
194  if (S.ReturnType == "")
195  S.ReturnType = O.ReturnType;
196  if (S.Type == "")
197  S.Type = O.Type;
198  for (const auto &OI : O.IncludeHeaders) {
199  bool Found = false;
200  for (auto &SI : S.IncludeHeaders) {
201  if (SI.IncludeHeader == OI.IncludeHeader) {
202  Found = true;
203  SI.References += OI.References;
204  break;
205  }
206  }
207  if (!Found && MergeIncludes)
208  S.IncludeHeaders.emplace_back(OI.IncludeHeader, OI.References);
209  }
210 
212  S.Flags |= O.Flags;
213  return S;
214 }
215 
216 } // namespace clangd
217 } // namespace clang
SourceLocation Loc
&#39;#&#39; location in the include directive
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...
An immutable symbol container that stores a set of symbols.
Definition: Symbol.h:177
const Symbol * find(const SymbolID &ID)
Returns the symbol with an ID, if it exists. Valid until insert/remove.
Definition: Symbol.h:211
llvm::Optional< uint32_t > Limit
If set, limit the number of relations returned from the index.
Definition: Index.h:80
const_iterator find(const SymbolID &SymID) const
Definition: Symbol.cpp:37
llvm::DenseSet< SymbolID > IDs
Definition: Index.h:64
Represents a symbol occurrence in the source file.
Definition: Ref.h:52
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...
void insert(const Symbol &S)
Adds a symbol, overwriting any existing one with the same ID.
Definition: Symbol.cpp:50
llvm::unique_function< void(llvm::Expected< T >)> Callback
A Callback<T> is a void function that accepts Expected<T>.
Definition: Function.h:28
unsigned References
The number of translation units that reference this symbol from their main file.
Definition: Symbol.h:59
SymbolSlab::Builder is a mutable container that can &#39;freeze&#39; to SymbolSlab.
Definition: Symbol.h:199
SymbolID ID
The ID of the symbol.
Definition: Symbol.h:38
SymbolLocation Definition
The location of the symbol&#39;s definition, if one was found.
Definition: Symbol.h:47
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:70
bool prefer(const SymbolLocation &L, const SymbolLocation &R)
Definition: Merge.cpp:150
llvm::SmallVector< IncludeHeaderWithReferences, 1 > IncludeHeaders
One Symbol can potentially be incuded via different headers.
Definition: Symbol.h:111
SymbolFlag Flags
Definition: Symbol.h:128
llvm::StringRef Signature
A brief description of the symbol that can be appended in the completion candidate list...
Definition: Symbol.h:65
SymbolLocation Location
The source location where the symbol is named.
Definition: Ref.h:54
llvm::StringRef Documentation
Documentation including comment for the symbol declaration.
Definition: Symbol.h:76
SymbolLocation CanonicalDeclaration
The location of the preferred declaration of the symbol.
Definition: Symbol.h:56
Symbol mergeSymbol(const Symbol &L, const Symbol &R)
Definition: Merge.cpp:165
virtual void refs(const RefsRequest &Req, llvm::function_ref< void(const Ref &)> Callback) const =0
Finds all occurrences (e.g.
void relations(const RelationsRequest &, llvm::function_ref< void(const SymbolID &, const Symbol &)>) const override
Definition: Merge.cpp:123
The class presents a C++ symbol, e.g.
Definition: Symbol.h:36
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
llvm::Optional< uint32_t > Limit
If set, limit the number of refers returned from the index.
Definition: Index.h:73
void refs(const RefsRequest &, llvm::function_ref< void(const Ref &)>) const override
Finds all occurrences (e.g.
Definition: Merge.cpp:92
llvm::StringRef CompletionSnippetSuffix
What to insert when completing this symbol, after the symbol name.
Definition: Symbol.h:74
const_iterator end() const
Definition: Symbol.h:186
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:30
llvm::StringRef Type
Raw representation of the OpaqueType of the symbol, used for scoring purposes.
Definition: Symbol.h:85
SymbolOrigin Origin
Where this symbol came from. Usually an index provides a constant value.
Definition: Symbol.h:61
Records an event whose duration is the lifetime of the Span object.
Definition: Trace.h:81
llvm::StringRef ReturnType
Type when this symbol is used in an expression.
Definition: Symbol.h:80
#define SPAN_ATTACH(S, Name, Expr)
Attach a key-value pair to a Span event.
Definition: Trace.h:97
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...