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 15 namespace clang { 16 namespace clangd { 17 18 std::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 27 bool 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 59 void 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 69 bool 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 89 bool 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 108 void 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 128 llvm::unique_function<IndexContents(llvm::StringRef) const> 129 MemIndex::indexedFiles() const { 130 return [this](llvm::StringRef FileURI) { 131 return Files.contains(FileURI) ? IdxContents : IndexContents::None; 132 }; 133 } 134 135 size_t MemIndex::estimateMemoryUsage() const { 136 return Index.getMemorySize() + Refs.getMemorySize() + 137 Relations.getMemorySize() + BackingDataSize; 138 } 139 140 } // namespace clangd 141 } // namespace clang 142