clang-tools  15.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/Trace.h"
13 
14 namespace clang {
15 namespace clangd {
16 
17 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs,
18  RelationSlab Relations) {
19  // Store Slab size before it is moved.
20  const auto BackingDataSize = Slab.bytes() + Refs.bytes();
21  auto Data = std::make_pair(std::move(Slab), std::move(Refs));
22  return std::make_unique<MemIndex>(Data.first, Data.second, Relations,
23  std::move(Data), BackingDataSize);
24 }
25 
27  const FuzzyFindRequest &Req,
28  llvm::function_ref<void(const Symbol &)> Callback) const {
29  assert(!StringRef(Req.Query).contains("::") &&
30  "There must be no :: in query.");
31  trace::Span Tracer("MemIndex fuzzyFind");
32 
34  Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
35  FuzzyMatcher Filter(Req.Query);
36  bool More = false;
37  for (const auto &Pair : Index) {
38  const Symbol *Sym = Pair.second;
39 
40  // Exact match against all possible scopes.
41  if (!Req.AnyScope && !llvm::is_contained(Req.Scopes, Sym->Scope))
42  continue;
43  if (Req.RestrictForCodeCompletion &&
45  continue;
46 
47  if (auto Score = Filter.match(Sym->Name))
48  if (Top.push({*Score * quality(*Sym), Sym}))
49  More = true; // An element with smallest score was discarded.
50  }
51  auto Results = std::move(Top).items();
52  SPAN_ATTACH(Tracer, "results", static_cast<int>(Results.size()));
53  for (const auto &Item : Results)
54  Callback(*Item.second);
55  return More;
56 }
57 
59  llvm::function_ref<void(const Symbol &)> Callback) const {
60  trace::Span Tracer("MemIndex lookup");
61  for (const auto &ID : Req.IDs) {
62  auto I = Index.find(ID);
63  if (I != Index.end())
64  Callback(*I->second);
65  }
66 }
67 
68 bool MemIndex::refs(const RefsRequest &Req,
69  llvm::function_ref<void(const Ref &)> Callback) const {
70  trace::Span Tracer("MemIndex refs");
71  uint32_t Remaining = Req.Limit.value_or(std::numeric_limits<uint32_t>::max());
72  for (const auto &ReqID : Req.IDs) {
73  auto SymRefs = Refs.find(ReqID);
74  if (SymRefs == Refs.end())
75  continue;
76  for (const auto &O : SymRefs->second) {
77  if (!static_cast<int>(Req.Filter & O.Kind))
78  continue;
79  if (Remaining == 0)
80  return true; // More refs were available.
81  --Remaining;
82  Callback(O);
83  }
84  }
85  return false; // We reported all refs.
86 }
87 
89  const RelationsRequest &Req,
90  llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
91  uint32_t Remaining = Req.Limit.value_or(std::numeric_limits<uint32_t>::max());
92  for (const SymbolID &Subject : Req.Subjects) {
93  LookupRequest LookupReq;
94  auto It = Relations.find(
95  std::make_pair(Subject, static_cast<uint8_t>(Req.Predicate)));
96  if (It != Relations.end()) {
97  for (const auto &Obj : It->second) {
98  if (Remaining > 0) {
99  --Remaining;
100  LookupReq.IDs.insert(Obj);
101  }
102  }
103  }
104  lookup(LookupReq, [&](const Symbol &Object) { Callback(Subject, Object); });
105  }
106 }
107 
108 llvm::unique_function<IndexContents(llvm::StringRef) const>
110  return [this](llvm::StringRef FileURI) {
111  return Files.contains(FileURI) ? IdxContents : IndexContents::None;
112  };
113 }
114 
116  return Index.getMemorySize() + Refs.getMemorySize() +
117  Relations.getMemorySize() + BackingDataSize;
118 }
119 
120 } // namespace clangd
121 } // namespace clang
clang::clangd::MemIndex::indexedFiles
llvm::unique_function< IndexContents(llvm::StringRef) const > indexedFiles() const override
Definition: MemIndex.cpp:109
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:172
Refs
RefSlab Refs
Definition: SymbolCollectorTests.cpp:312
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::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:26
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:36
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:88
clang::clangd::RelationsRequest::Predicate
RelationKind Predicate
Definition: Index.h:82
clang::clangd::RefSlab
An efficient structure of storing large set of symbol references in memory.
Definition: Ref.h:108
clang::clangd::FuzzyFindRequest
Definition: Index.h:26
clang::clangd::FuzzyFindRequest::Query
std::string Query
A query string for the fuzzy find.
Definition: Index.h:29
clang::clangd::TopN::push
bool push(value_type &&V)
Definition: Quality.h:196
MemIndex.h
FuzzyMatch.h
clang::clangd::TopN
TopN<T> is a lossy container that preserves only the "best" N elements.
Definition: Quality.h:188
clang::clangd::RelationsRequest::Subjects
llvm::DenseSet< SymbolID > Subjects
Definition: Index.h:81
clang::clangd::RelationSlab
Definition: Relation.h:50
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:93
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:784
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:17
clang::clangd::RefsRequest::IDs
llvm::DenseSet< SymbolID > IDs
Definition: Index.h:69
clang::clangd::FuzzyFindRequest::Limit
llvm::Optional< uint32_t > Limit
The number of top candidates to return.
Definition: Index.h:42
clang::clangd::LookupRequest::IDs
llvm::DenseSet< SymbolID > IDs
Definition: Index.h:65
clang::clangd::RefsRequest::Filter
RefKind Filter
Definition: Index.h:70
clang::clangd::LookupRequest
Definition: Index.h:64
clang::clangd::MemIndex::estimateMemoryUsage
size_t estimateMemoryUsage() const override
Returns estimated size of index (in bytes).
Definition: MemIndex.cpp:115
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:58
clang::clangd::IndexContents::None
@ None
ID
static char ID
Definition: Logger.cpp:74
Score
llvm::Optional< float > Score
Definition: FuzzyMatchTests.cpp:47
clang::clangd::Ref
Represents a symbol occurrence in the source file.
Definition: Ref.h:85
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:68
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::FuzzyFindRequest::AnyScope
bool AnyScope
If set to true, allow symbols from any scope.
Definition: Index.h:39
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
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:44
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:68
clang::clangd::trace::Span
Records an event whose duration is the lifetime of the Span object.
Definition: Trace.h:143