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