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 "index/Index.h"
13#include "support/Trace.h"
14
15namespace clang {
16namespace clangd {
17
18std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs,
19 RelationSlab Relations) {
20 // Store Slab size before it is moved.
21 const auto BackingDataSize = Slab.bytes() + Refs.bytes();
22 auto Data = std::make_pair(x: std::move(Slab), y: std::move(Refs));
23 return std::make_unique<MemIndex>(args&: Data.first, args&: Data.second, args&: Relations,
24 args: std::move(Data), args: BackingDataSize);
25}
26
27bool MemIndex::fuzzyFind(
28 const FuzzyFindRequest &Req,
29 llvm::function_ref<void(const Symbol &)> Callback) const {
30 assert(!StringRef(Req.Query).contains("::") &&
31 "There must be no :: in query.");
32 trace::Span Tracer("MemIndex fuzzyFind");
33
34 TopN<std::pair<float, const Symbol *>> Top(
35 Req.Limit.value_or(u: std::numeric_limits<size_t>::max()));
36 FuzzyMatcher Filter(Req.Query);
37 bool More = false;
38 for (const auto &Pair : Index) {
39 const Symbol *Sym = Pair.second;
40
41 // Exact match against all possible scopes.
42 if (!Req.AnyScope && !llvm::is_contained(Range: Req.Scopes, Element: Sym->Scope))
43 continue;
44 if (Req.RestrictForCodeCompletion &&
45 !(Sym->Flags & Symbol::IndexedForCodeCompletion))
46 continue;
47
48 if (auto Score = Filter.match(Word: Sym->Name))
49 if (Top.push(V: {*Score * quality(S: *Sym), Sym}))
50 More = true; // An element with smallest score was discarded.
51 }
52 auto Results = std::move(Top).items();
53 SPAN_ATTACH(Tracer, "results", static_cast<int>(Results.size()));
54 for (const auto &Item : Results)
55 Callback(*Item.second);
56 return More;
57}
58
59void MemIndex::lookup(const LookupRequest &Req,
60 llvm::function_ref<void(const Symbol &)> Callback) const {
61 trace::Span Tracer("MemIndex lookup");
62 for (const auto &ID : Req.IDs) {
63 auto I = Index.find(Val: ID);
64 if (I != Index.end())
65 Callback(*I->second);
66 }
67}
68
69bool MemIndex::refs(const RefsRequest &Req,
70 llvm::function_ref<void(const Ref &)> Callback) const {
71 trace::Span Tracer("MemIndex refs");
72 uint32_t Remaining = Req.Limit.value_or(u: std::numeric_limits<uint32_t>::max());
73 for (const auto &ReqID : Req.IDs) {
74 auto SymRefs = Refs.find(Val: ReqID);
75 if (SymRefs == Refs.end())
76 continue;
77 for (const auto &O : SymRefs->second) {
78 if (!static_cast<int>(Req.Filter & O.Kind))
79 continue;
80 if (Remaining == 0)
81 return true; // More refs were available.
82 --Remaining;
83 Callback(O);
84 }
85 }
86 return false; // We reported all refs.
87}
88
89bool MemIndex::containedRefs(
90 const ContainedRefsRequest &Req,
91 llvm::function_ref<void(const ContainedRefsResult &)> Callback) const {
92 trace::Span Tracer("MemIndex refersTo");
93 uint32_t Remaining = Req.Limit.value_or(u: std::numeric_limits<uint32_t>::max());
94 for (const auto &Pair : Refs) {
95 for (const auto &R : Pair.second) {
96 if (!static_cast<int>(ContainedRefsRequest::SupportedRefKinds & R.Kind) ||
97 Req.ID != R.Container)
98 continue;
99 if (Remaining == 0)
100 return true; // More refs were available.
101 --Remaining;
102 Callback({.Location: R.Location, .Kind: R.Kind, .Symbol: Pair.first});
103 }
104 }
105 return false; // We reported all refs.
106}
107
108void MemIndex::relations(
109 const RelationsRequest &Req,
110 llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
111 uint32_t Remaining = Req.Limit.value_or(u: std::numeric_limits<uint32_t>::max());
112 for (const SymbolID &Subject : Req.Subjects) {
113 LookupRequest LookupReq;
114 auto It = Relations.find(
115 Val: std::make_pair(x: Subject, y: static_cast<uint8_t>(Req.Predicate)));
116 if (It != Relations.end()) {
117 for (const auto &Obj : It->second) {
118 if (Remaining > 0) {
119 --Remaining;
120 LookupReq.IDs.insert(V: Obj);
121 }
122 }
123 }
124 lookup(Req: LookupReq, Callback: [&](const Symbol &Object) { Callback(Subject, Object); });
125 }
126}
127
128llvm::unique_function<IndexContents(llvm::StringRef) const>
129MemIndex::indexedFiles() const {
130 return [this](llvm::StringRef FileURI) {
131 return Files.contains(key: FileURI) ? IdxContents : IndexContents::None;
132 };
133}
134
135size_t MemIndex::estimateMemoryUsage() const {
136 return Index.getMemorySize() + Refs.getMemorySize() +
137 Relations.getMemorySize() + BackingDataSize;
138}
139
140} // namespace clangd
141} // namespace clang
142

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