clang-tools 22.0.0git
MemIndex.h
Go to the documentation of this file.
1//===--- MemIndex.h - 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#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MEMINDEX_H
10#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MEMINDEX_H
11
12#include "index/Index.h"
13#include "index/Relation.h"
14#include "llvm/ADT/StringSet.h"
15#include <mutex>
16
17namespace clang {
18namespace clangd {
19
20/// MemIndex is a naive in-memory index suitable for a small set of symbols.
21class MemIndex : public SymbolIndex {
22public:
23 MemIndex() = default;
24 // All symbols and refs must outlive this index.
25 template <typename SymbolRange, typename RefRange, typename RelationRange>
26 MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations) {
27 for (const Symbol &S : Symbols)
28 Index[S.ID] = &S;
29 for (const std::pair<SymbolID, llvm::ArrayRef<Ref>> &R : Refs)
30 this->Refs.try_emplace(R.first, R.second.begin(), R.second.end());
31 for (const Relation &R : Relations) {
32 this->Relations[std::make_pair(R.Subject,
33 static_cast<uint8_t>(R.Predicate))]
34 .push_back(R.Object);
35 if (R.Predicate == RelationKind::OverriddenBy) {
36 this->ReverseRelations[std::make_pair(
37 R.Object, static_cast<uint8_t>(R.Predicate))]
38 .push_back(R.Subject);
39 }
40 }
41 }
42 // Symbols are owned by BackingData, Index takes ownership.
43 template <typename SymbolRange, typename RefRange, typename RelationRange,
44 typename Payload>
45 MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations,
46 Payload &&BackingData, size_t BackingDataSize)
47 : MemIndex(std::forward<SymbolRange>(Symbols),
48 std::forward<RefRange>(Refs),
49 std::forward<RelationRange>(Relations)) {
50 KeepAlive = std::shared_ptr<void>(
51 std::make_shared<Payload>(std::move(BackingData)), nullptr);
52 this->BackingDataSize = BackingDataSize;
53 }
54
55 template <typename SymbolRange, typename RefRange, typename RelationRange,
56 typename FileRange, typename Payload>
57 MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations,
58 FileRange &&Files, IndexContents IdxContents, Payload &&BackingData,
59 size_t BackingDataSize)
60 : MemIndex(std::forward<SymbolRange>(Symbols),
61 std::forward<RefRange>(Refs),
62 std::forward<RelationRange>(Relations),
63 std::forward<Payload>(BackingData), BackingDataSize) {
64 this->Files = std::forward<FileRange>(Files);
65 this->IdxContents = IdxContents;
66 }
67
68 /// Builds an index from slabs. The index takes ownership of the data.
69 static std::unique_ptr<SymbolIndex> build(SymbolSlab Symbols, RefSlab Refs,
70 RelationSlab Relations);
71
72 bool
73 fuzzyFind(const FuzzyFindRequest &Req,
74 llvm::function_ref<void(const Symbol &)> Callback) const override;
75
76 void lookup(const LookupRequest &Req,
77 llvm::function_ref<void(const Symbol &)> Callback) const override;
78
79 bool refs(const RefsRequest &Req,
80 llvm::function_ref<void(const Ref &)> Callback) const override;
81
82 bool containedRefs(const ContainedRefsRequest &Req,
83 llvm::function_ref<void(const ContainedRefsResult &)>
84 Callback) const override;
85
86 void relations(const RelationsRequest &Req,
87 llvm::function_ref<void(const SymbolID &, const Symbol &)>
88 Callback) const override;
89
90 void
92 llvm::function_ref<void(const SymbolID &, const Symbol &)>
93 Callback) const override;
94
95 llvm::unique_function<IndexContents(llvm::StringRef) const>
96 indexedFiles() const override;
97
98 size_t estimateMemoryUsage() const override;
99
100private:
101 // Index is a set of symbols that are deduplicated by symbol IDs.
102 llvm::DenseMap<SymbolID, const Symbol *> Index;
103 // A map from symbol ID to symbol refs, support query by IDs.
104 llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> Refs;
105 // A map from (subject, predicate) pair to objects.
106 static_assert(sizeof(RelationKind) == sizeof(uint8_t),
107 "RelationKind should be of same size as a uint8_t");
108 llvm::DenseMap<std::pair<SymbolID, uint8_t>, std::vector<SymbolID>> Relations;
109 // Reverse relations, currently only for OverriddenBy
110 llvm::DenseMap<std::pair<SymbolID, uint8_t>, std::vector<SymbolID>>
111 ReverseRelations;
112 // Set of files which were used during this index build.
113 llvm::StringSet<> Files;
114 // Contents of the index (symbols, references, etc.)
116 std::shared_ptr<void> KeepAlive; // poor man's move-only std::any
117 // Size of memory retained by KeepAlive.
118 size_t BackingDataSize = 0;
119};
120
121} // namespace clangd
122} // namespace clang
123
124#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MEMINDEX_H
void reverseRelations(const RelationsRequest &Req, llvm::function_ref< void(const SymbolID &, const Symbol &)> Callback) const override
Definition MemIndex.cpp:128
size_t estimateMemoryUsage() const override
Returns estimated size of index (in bytes).
Definition MemIndex.cpp:156
void lookup(const LookupRequest &Req, llvm::function_ref< void(const Symbol &)> Callback) const override
Looks up symbols with any of the given symbol IDs and applies Callback on each matched symbol.
Definition MemIndex.cpp:59
bool fuzzyFind(const FuzzyFindRequest &Req, llvm::function_ref< void(const Symbol &)> Callback) const override
Matches symbols in the index fuzzily and applies Callback on each matched symbol before returning.
Definition MemIndex.cpp:27
MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations, Payload &&BackingData, size_t BackingDataSize)
Definition MemIndex.h:45
void relations(const RelationsRequest &Req, llvm::function_ref< void(const SymbolID &, const Symbol &)> Callback) const override
Definition MemIndex.cpp:108
llvm::unique_function< IndexContents(llvm::StringRef) const > indexedFiles() const override
Definition MemIndex.cpp:150
MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations, FileRange &&Files, IndexContents IdxContents, Payload &&BackingData, size_t BackingDataSize)
Definition MemIndex.h:57
MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations)
Definition MemIndex.h:26
static std::unique_ptr< SymbolIndex > build(SymbolSlab Symbols, RefSlab Refs, RelationSlab Relations)
Builds an index from slabs. The index takes ownership of the data.
Definition MemIndex.cpp:18
bool containedRefs(const ContainedRefsRequest &Req, llvm::function_ref< void(const ContainedRefsResult &)> Callback) const override
Find all symbols that are referenced by a symbol and apply Callback on each result.
Definition MemIndex.cpp:89
bool refs(const RefsRequest &Req, llvm::function_ref< void(const Ref &)> Callback) const override
Finds all occurrences (e.g.
Definition MemIndex.cpp:69
An efficient structure of storing large set of symbol references in memory.
Definition Ref.h:111
Interface for symbol indexes that can be used for searching or matching symbols among a set of symbol...
Definition Index.h:134
An immutable symbol container that stores a set of symbols.
Definition Symbol.h:201
FIXME: Skip testing on windows temporarily due to the different escaping code mode.
Definition AST.cpp:45
IndexContents
Describes what data is covered by an index.
Definition Index.h:114
llvm::unique_function< void(llvm::Expected< T >)> Callback
A Callback<T> is a void function that accepts Expected<T>.
Definition Function.h:28
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Represents a symbol occurrence in the source file.
Definition Ref.h:88
Represents a relation between two symbols.
Definition Relation.h:32
Represents a symbol range where the symbol can potentially have multiple tokens.
Definition Rename.h:112
The class presents a C++ symbol, e.g.
Definition Symbol.h:39