164 lines · cpp
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-exception6//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(std::move(Slab), std::move(Refs));23 return std::make_unique<MemIndex>(Data.first, Data.second, Relations,24 std::move(Data), 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(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(Req.Scopes, Sym->Scope))43 continue;44 if (Req.RestrictForCodeCompletion &&45 !(Sym->Flags & Symbol::IndexedForCodeCompletion))46 continue;47 48 if (auto Score = Filter.match(Sym->Name))49 if (Top.push({*Score * quality(*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(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(std::numeric_limits<uint32_t>::max());73 for (const auto &ReqID : Req.IDs) {74 auto SymRefs = Refs.find(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(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({R.Location, R.Kind, 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(std::numeric_limits<uint32_t>::max());112 for (const SymbolID &Subject : Req.Subjects) {113 LookupRequest LookupReq;114 auto It = Relations.find(115 std::make_pair(Subject, 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(Obj);121 }122 }123 }124 lookup(LookupReq, [&](const Symbol &Object) { Callback(Subject, Object); });125 }126}127 128void MemIndex::reverseRelations(129 const RelationsRequest &Req,130 llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {131 assert(Req.Predicate == RelationKind::OverriddenBy);132 uint32_t Remaining = Req.Limit.value_or(std::numeric_limits<uint32_t>::max());133 for (const SymbolID &Subject : Req.Subjects) {134 LookupRequest LookupReq;135 auto It = ReverseRelations.find(136 std::make_pair(Subject, static_cast<uint8_t>(Req.Predicate)));137 if (It != ReverseRelations.end()) {138 for (const auto &Obj : It->second) {139 if (Remaining > 0) {140 --Remaining;141 LookupReq.IDs.insert(Obj);142 }143 }144 }145 lookup(LookupReq, [&](const Symbol &Object) { Callback(Subject, Object); });146 }147}148 149llvm::unique_function<IndexContents(llvm::StringRef) const>150MemIndex::indexedFiles() const {151 return [this](llvm::StringRef FileURI) {152 return Files.contains(FileURI) ? IdxContents : IndexContents::None;153 };154}155 156size_t MemIndex::estimateMemoryUsage() const {157 return Index.getMemorySize() + Refs.getMemorySize() +158 Relations.getMemorySize() + ReverseRelations.getMemorySize() +159 BackingDataSize;160}161 162} // namespace clangd163} // namespace clang164