clang-tools  14.0.0git
MemIndex.cpp
Go to the documentation of this file.
1 //===--- MemIndex.cpp - Dynamic in-memory symbol index. ----------*- 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 "MemIndex.h"
10 #include "FuzzyMatch.h"
11 #include "Quality.h"
12 #include "support/Logger.h"
13 #include "support/Trace.h"
14 #include "clang/Index/IndexSymbol.h"
15 
16 namespace clang {
17 namespace clangd {
18 
19 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs,
20  RelationSlab Relations) {
21  // Store Slab size before it is moved.
22  const auto BackingDataSize = Slab.bytes() + Refs.bytes();
23  auto Data = std::make_pair(std::move(Slab), std::move(Refs));
24  return std::make_unique<MemIndex>(Data.first, Data.second, Relations,
25  std::move(Data), BackingDataSize);
26 }
27 
29  const FuzzyFindRequest &Req,
30  llvm::function_ref<void(const Symbol &)> Callback) const {
31  assert(!StringRef(Req.Query).contains("::") &&
32  "There must be no :: in query.");
33  trace::Span Tracer("MemIndex fuzzyFind");
34 
36  Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
37  FuzzyMatcher Filter(Req.Query);
38  bool More = false;
39  for (const auto &Pair : Index) {
40  const Symbol *Sym = Pair.second;
41 
42  // Exact match against all possible scopes.
43  if (!Req.AnyScope && !llvm::is_contained(Req.Scopes, Sym->Scope))
44  continue;
45  if (Req.RestrictForCodeCompletion &&
47  continue;
48 
49  if (auto Score = Filter.match(Sym->Name))
50  if (Top.push({*Score * quality(*Sym), Sym}))
51  More = true; // An element with smallest score was discarded.
52  }
53  auto Results = std::move(Top).items();
54  SPAN_ATTACH(Tracer, "results", static_cast<int>(Results.size()));
55  for (const auto &Item : Results)
56  Callback(*Item.second);
57  return More;
58 }
59 
61  llvm::function_ref<void(const Symbol &)> Callback) const {
62  trace::Span Tracer("MemIndex lookup");
63  for (const auto &ID : Req.IDs) {
64  auto I = Index.find(ID);
65  if (I != Index.end())
66  Callback(*I->second);
67  }
68 }
69 
70 bool MemIndex::refs(const RefsRequest &Req,
71  llvm::function_ref<void(const Ref &)> Callback) const {
72  trace::Span Tracer("MemIndex refs");
73  uint32_t Remaining =
74  Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
75  for (const auto &ReqID : Req.IDs) {
76  auto SymRefs = Refs.find(ReqID);
77  if (SymRefs == Refs.end())
78  continue;
79  for (const auto &O : SymRefs->second) {
80  if (!static_cast<int>(Req.Filter & O.Kind))
81  continue;
82  if (Remaining == 0)
83  return true; // More refs were available.
84  --Remaining;
85  Callback(O);
86  }
87  }
88  return false; // We reported all refs.
89 }
90 
92  const RelationsRequest &Req,
93  llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
94  uint32_t Remaining =
95  Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
96  for (const SymbolID &Subject : Req.Subjects) {
97  LookupRequest LookupReq;
98  auto It = Relations.find(
99  std::make_pair(Subject, static_cast<uint8_t>(Req.Predicate)));
100  if (It != Relations.end()) {
101  for (const auto &Obj : It->second) {
102  if (Remaining > 0) {
103  --Remaining;
104  LookupReq.IDs.insert(Obj);
105  }
106  }
107  }
108  lookup(LookupReq, [&](const Symbol &Object) { Callback(Subject, Object); });
109  }
110 }
111 
112 llvm::unique_function<IndexContents(llvm::StringRef) const>
114  return [this](llvm::StringRef FileURI) {
115  return Files.contains(FileURI) ? IdxContents : IndexContents::None;
116  };
117 }
118 
120  return Index.getMemorySize() + Refs.getMemorySize() +
121  Relations.getMemorySize() + BackingDataSize;
122 }
123 
124 } // namespace clangd
125 } // namespace clang
clang::clangd::MemIndex::indexedFiles
llvm::unique_function< IndexContents(llvm::StringRef) const > indexedFiles() const override
Definition: MemIndex.cpp:113
clang::clangd::Symbol::IndexedForCodeCompletion
@ IndexedForCodeCompletion
Whether or not this symbol is meant to be used for the code completion.
Definition: Symbol.h:119
clang::clangd::Obj
llvm::json::Object Obj
Definition: LSPClient.cpp:164
Refs
RefSlab Refs
Definition: SymbolCollectorTests.cpp:311
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::SymbolKind::Object
@ Object
clang::clangd::MemIndex::fuzzyFind
bool fuzzyFind(const FuzzyFindRequest &Req, llvm::function_ref< void(const Symbol &)> Callback) const override
Matches symbols in the index fuzzily and applies Callback on each matched symbol before returning.
Definition: MemIndex.cpp:28
clang::clangd::FuzzyFindRequest::Scopes
std::vector< std::string > Scopes
If this is non-empty, symbols must be in at least one of the scopes (e.g.
Definition: Index.h:37
Trace.h
clang::clangd::MemIndex::relations
void relations(const RelationsRequest &Req, llvm::function_ref< void(const SymbolID &, const Symbol &)> Callback) const override
Definition: MemIndex.cpp:91
clang::clangd::RelationsRequest::Predicate
RelationKind Predicate
Definition: Index.h:80
clang::clangd::RefSlab
An efficient structure of storing large set of symbol references in memory.
Definition: Ref.h:110
clang::clangd::FuzzyFindRequest
Definition: Index.h:27
clang::clangd::FuzzyFindRequest::Query
std::string Query
A query string for the fuzzy find.
Definition: Index.h:30
clang::clangd::TopN::push
bool push(value_type &&V)
Definition: Quality.h:199
MemIndex.h
FuzzyMatch.h
clang::clangd::TopN
TopN<T> is a lossy container that preserves only the "best" N elements.
Definition: Quality.h:191
clang::clangd::RelationsRequest::Subjects
llvm::DenseSet< SymbolID > Subjects
Definition: Index.h:79
clang::clangd::RelationSlab
Definition: Relation.h:52
Logger.h
clang::clangd::Symbol
The class presents a C++ symbol, e.g.
Definition: Symbol.h:36
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
SPAN_ATTACH
#define SPAN_ATTACH(S, Name, Expr)
Attach a key-value pair to a Span event.
Definition: Trace.h:164
Results
std::vector< CodeCompletionResult > Results
Definition: CodeComplete.cpp:771
clang::clangd::Symbol::Name
llvm::StringRef Name
The unqualified name of the symbol, e.g. "bar" (for ns::bar).
Definition: Symbol.h:42
clang::clangd::MemIndex::build
static std::unique_ptr< SymbolIndex > build(SymbolSlab Symbols, RefSlab Refs, RelationSlab Relations)
Builds an index from slabs. The index takes ownership of the data.
Definition: MemIndex.cpp:19
clang::clangd::RefsRequest::IDs
llvm::DenseSet< SymbolID > IDs
Definition: Index.h:70
clang::clangd::FuzzyFindRequest::Limit
llvm::Optional< uint32_t > Limit
The number of top candidates to return.
Definition: Index.h:43
clang::clangd::LookupRequest::IDs
llvm::DenseSet< SymbolID > IDs
Definition: Index.h:66
clang::clangd::RefsRequest::Filter
RefKind Filter
Definition: Index.h:71
clang::clangd::LookupRequest
Definition: Index.h:65
clang::clangd::MemIndex::estimateMemoryUsage
size_t estimateMemoryUsage() const override
Returns estimated size of index (in bytes).
Definition: MemIndex.cpp:119
clang::clangd::MemIndex::lookup
void lookup(const LookupRequest &Req, llvm::function_ref< void(const Symbol &)> Callback) const override
Looks up symbols with any of the given symbol IDs and applies Callback on each matched symbol.
Definition: MemIndex.cpp:60
clang::clangd::IndexContents::None
@ None
ID
static char ID
Definition: Logger.cpp:74
Score
llvm::Optional< float > Score
Definition: FuzzyMatchTests.cpp:48
clang::clangd::Ref
Represents a symbol occurrence in the source file.
Definition: Ref.h:87
clang::clangd::FuzzyMatcher
Definition: FuzzyMatch.h:71
clang::clangd::Symbol::Scope
llvm::StringRef Scope
The containing namespace. e.g. "" (global), "ns::" (top-level namespace).
Definition: Symbol.h:44
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::clangd::MemIndex::refs
bool refs(const RefsRequest &Req, llvm::function_ref< void(const Ref &)> Callback) const override
Finds all occurrences (e.g.
Definition: MemIndex.cpp:70
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::FuzzyFindRequest::AnyScope
bool AnyScope
If set to true, allow symbols from any scope.
Definition: Index.h:40
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
clang::clangd::SymbolSlab::bytes
size_t bytes() const
Definition: Symbol.h:193
Quality.h
clang::clangd::FuzzyFindRequest::RestrictForCodeCompletion
bool RestrictForCodeCompletion
If set to true, only symbols for completion support will be considered.
Definition: Index.h:45
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::RefsRequest
Definition: Index.h:69
clang::clangd::trace::Span
Records an event whose duration is the lifetime of the Span object.
Definition: Trace.h:143