clang-tools 20.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
14namespace clang {
15namespace clangd {
16
17std::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;
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
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
108llvm::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
std::vector< CodeCompletionResult > Results
std::optional< float > Score
#define SPAN_ATTACH(S, Name, Expr)
Attach a key-value pair to a Span event.
Definition: Trace.h:164
size_t estimateMemoryUsage() const override
Returns estimated size of index (in bytes).
Definition: MemIndex.cpp:115
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
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
void relations(const RelationsRequest &Req, llvm::function_ref< void(const SymbolID &, const Symbol &)> Callback) const override
Definition: MemIndex.cpp:88
llvm::unique_function< IndexContents(llvm::StringRef) const > indexedFiles() const override
Definition: MemIndex.cpp:109
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
bool refs(const RefsRequest &Req, llvm::function_ref< void(const Ref &)> Callback) const override
Finds all occurrences (e.g.
Definition: MemIndex.cpp:68
An efficient structure of storing large set of symbol references in memory.
Definition: Ref.h:108
An immutable symbol container that stores a set of symbols.
Definition: Symbol.h:199
size_t bytes() const
Definition: Symbol.h:215
TopN<T> is a lossy container that preserves only the "best" N elements.
Definition: Quality.h:189
bool push(value_type &&V)
Definition: Quality.h:197
Records an event whose duration is the lifetime of the Span object.
Definition: Trace.h:143
IndexContents
Describes what data is covered by an index.
Definition: Index.h:93
llvm::json::Object Obj
Definition: LSPClient.cpp:217
llvm::unique_function< void(llvm::Expected< T >)> Callback
A Callback<T> is a void function that accepts Expected<T>.
Definition: Function.h:28
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
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
bool RestrictForCodeCompletion
If set to true, only symbols for completion support will be considered.
Definition: Index.h:44
std::string Query
A query string for the fuzzy find.
Definition: Index.h:29
bool AnyScope
If set to true, allow symbols from any scope.
Definition: Index.h:39
std::optional< uint32_t > Limit
The number of top candidates to return.
Definition: Index.h:42
llvm::DenseSet< SymbolID > IDs
Definition: Index.h:65
Represents a symbol occurrence in the source file.
Definition: Ref.h:85
llvm::DenseSet< SymbolID > IDs
Definition: Index.h:69
std::optional< uint32_t > Limit
If set, limit the number of refers returned from the index.
Definition: Index.h:74
std::optional< uint32_t > Limit
If set, limit the number of relations returned from the index.
Definition: Index.h:84
llvm::DenseSet< SymbolID > Subjects
Definition: Index.h:81
The class presents a C++ symbol, e.g.
Definition: Symbol.h:39
SymbolFlag Flags
Definition: Symbol.h:150
@ IndexedForCodeCompletion
Whether or not this symbol is meant to be used for the code completion.
Definition: Symbol.h:141
llvm::StringRef Name
The unqualified name of the symbol, e.g. "bar" (for ns::bar).
Definition: Symbol.h:45
llvm::StringRef Scope
The containing namespace. e.g. "" (global), "ns::" (top-level namespace).
Definition: Symbol.h:47