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(x: std::move(Slab), y: std::move(Refs));
22 return std::make_unique<MemIndex>(args&: Data.first, args&: Data.second, args&: Relations,
23 args: std::move(Data), args: BackingDataSize);
24}
25
26bool MemIndex::fuzzyFind(
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
33 TopN<std::pair<float, const Symbol *>> Top(
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(Range: Req.Scopes, Element: Sym->Scope))
42 continue;
43 if (Req.RestrictForCodeCompletion &&
44 !(Sym->Flags & Symbol::IndexedForCodeCompletion))
45 continue;
46
47 if (auto Score = Filter.match(Word: Sym->Name))
48 if (Top.push(V: {*Score * quality(S: *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
58void MemIndex::lookup(const LookupRequest &Req,
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(Val: ID);
63 if (I != Index.end())
64 Callback(*I->second);
65 }
66}
67
68bool 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(u: std::numeric_limits<uint32_t>::max());
72 for (const auto &ReqID : Req.IDs) {
73 auto SymRefs = Refs.find(Val: 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
88void MemIndex::relations(
89 const RelationsRequest &Req,
90 llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
91 uint32_t Remaining = Req.Limit.value_or(u: std::numeric_limits<uint32_t>::max());
92 for (const SymbolID &Subject : Req.Subjects) {
93 LookupRequest LookupReq;
94 auto It = Relations.find(
95 Val: std::make_pair(x: Subject, y: 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(V: Obj);
101 }
102 }
103 }
104 lookup(Req: LookupReq, Callback: [&](const Symbol &Object) { Callback(Subject, Object); });
105 }
106}
107
108llvm::unique_function<IndexContents(llvm::StringRef) const>
109MemIndex::indexedFiles() const {
110 return [this](llvm::StringRef FileURI) {
111 return Files.contains(key: FileURI) ? IdxContents : IndexContents::None;
112 };
113}
114
115size_t MemIndex::estimateMemoryUsage() const {
116 return Index.getMemorySize() + Refs.getMemorySize() +
117 Relations.getMemorySize() + BackingDataSize;
118}
119
120} // namespace clangd
121} // namespace clang
122

source code of clang-tools-extra/clangd/index/MemIndex.cpp