clang-tools-extra/clangd/index/MemIndex.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-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