clang-tools  15.0.0git
Dex.h
Go to the documentation of this file.
1 //===--- Dex.h - Dex Symbol Index Implementation ----------------*- 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 /// \file
10 /// This defines Dex - a symbol index implementation based on query iterators
11 /// over symbol tokens, such as fuzzy matching trigrams, scopes, types, etc.
12 /// While consuming more memory and having longer build stage due to
13 /// preprocessing, Dex will have substantially lower latency. It will also allow
14 /// efficient symbol searching which is crucial for operations like code
15 /// completion, and can be very important for a number of different code
16 /// transformations which will be eventually supported by Clangd.
17 ///
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_DEX_H
21 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_DEX_H
22 
23 #include "index/dex/Iterator.h"
24 #include "index/Index.h"
25 #include "index/Relation.h"
26 #include "index/dex/PostingList.h"
27 #include "index/dex/Token.h"
28 #include "llvm/ADT/StringSet.h"
29 
30 namespace clang {
31 namespace clangd {
32 namespace dex {
33 
34 /// In-memory Dex trigram-based index implementation.
35 class Dex : public SymbolIndex {
36 public:
37  // All data must outlive this index.
38  template <typename SymbolRange, typename RefsRange, typename RelationsRange>
39  Dex(SymbolRange &&Symbols, RefsRange &&Refs, RelationsRange &&Relations)
40  : Corpus(0) {
41  for (auto &&Sym : Symbols)
42  this->Symbols.push_back(&Sym);
43  for (auto &&Ref : Refs)
44  this->Refs.try_emplace(Ref.first, Ref.second);
45  for (auto &&Rel : Relations)
46  this->Relations[std::make_pair(Rel.Subject,
47  static_cast<uint8_t>(Rel.Predicate))]
48  .push_back(Rel.Object);
49  buildIndex();
50  }
51  // Symbols and Refs are owned by BackingData, Index takes ownership.
52  template <typename SymbolRange, typename RefsRange, typename RelationsRange,
53  typename Payload>
54  Dex(SymbolRange &&Symbols, RefsRange &&Refs, RelationsRange &&Relations,
55  Payload &&BackingData, size_t BackingDataSize)
56  : Dex(std::forward<SymbolRange>(Symbols), std::forward<RefsRange>(Refs),
57  std::forward<RelationsRange>(Relations)) {
58  KeepAlive = std::shared_ptr<void>(
59  std::make_shared<Payload>(std::move(BackingData)), nullptr);
60  this->BackingDataSize = BackingDataSize;
61  }
62 
63  template <typename SymbolRange, typename RefsRange, typename RelationsRange,
64  typename FileRange, typename Payload>
65  Dex(SymbolRange &&Symbols, RefsRange &&Refs, RelationsRange &&Relations,
66  FileRange &&Files, IndexContents IdxContents, Payload &&BackingData,
67  size_t BackingDataSize)
68  : Dex(std::forward<SymbolRange>(Symbols), std::forward<RefsRange>(Refs),
69  std::forward<RelationsRange>(Relations),
70  std::forward<Payload>(BackingData), BackingDataSize) {
71  this->Files = std::forward<FileRange>(Files);
72  this->IdxContents = IdxContents;
73  }
74 
75  /// Builds an index from slabs. The index takes ownership of the slab.
76  static std::unique_ptr<SymbolIndex> build(SymbolSlab, RefSlab, RelationSlab);
77 
78  bool
79  fuzzyFind(const FuzzyFindRequest &Req,
80  llvm::function_ref<void(const Symbol &)> Callback) const override;
81 
82  void lookup(const LookupRequest &Req,
83  llvm::function_ref<void(const Symbol &)> Callback) const override;
84 
85  bool refs(const RefsRequest &Req,
86  llvm::function_ref<void(const Ref &)> Callback) const override;
87 
88  void relations(const RelationsRequest &Req,
89  llvm::function_ref<void(const SymbolID &, const Symbol &)>
90  Callback) const override;
91 
92  llvm::unique_function<IndexContents(llvm::StringRef) const>
93  indexedFiles() const override;
94 
95  size_t estimateMemoryUsage() const override;
96 
97 private:
98  void buildIndex();
99  std::unique_ptr<Iterator> iterator(const Token &Tok) const;
100  std::unique_ptr<Iterator>
101  createFileProximityIterator(llvm::ArrayRef<std::string> ProximityPaths) const;
102  std::unique_ptr<Iterator>
103  createTypeBoostingIterator(llvm::ArrayRef<std::string> Types) const;
104 
105  /// Stores symbols sorted in the descending order of symbol quality..
106  std::vector<const Symbol *> Symbols;
107  /// SymbolQuality[I] is the quality of Symbols[I].
108  std::vector<float> SymbolQuality;
109  llvm::DenseMap<SymbolID, const Symbol *> LookupTable;
110  /// Inverted index is a mapping from the search token to the posting list,
111  /// which contains all items which can be characterized by such search token.
112  /// For example, if the search token is scope "std::", the corresponding
113  /// posting list would contain all indices of symbols defined in namespace
114  /// std. Inverted index is used to retrieve posting lists which are processed
115  /// during the fuzzyFind process.
116  llvm::DenseMap<Token, PostingList> InvertedIndex;
118  llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> Refs;
119  static_assert(sizeof(RelationKind) == sizeof(uint8_t),
120  "RelationKind should be of same size as a uint8_t");
121  llvm::DenseMap<std::pair<SymbolID, uint8_t>, std::vector<SymbolID>> Relations;
122  std::shared_ptr<void> KeepAlive; // poor man's move-only std::any
123  // Set of files which were used during this index build.
124  llvm::StringSet<> Files;
125  // Contents of the index (symbols, references, etc.)
126  IndexContents IdxContents;
127  // Size of memory retained by KeepAlive.
128  size_t BackingDataSize = 0;
129 };
130 
131 /// Returns Search Token for a number of parent directories of given Path.
132 /// Should be used within the index build process.
133 ///
134 /// This function is exposed for testing only.
135 std::vector<std::string> generateProximityURIs(llvm::StringRef URIPath);
136 
137 } // namespace dex
138 } // namespace clangd
139 } // namespace clang
140 
141 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_DEX_H
clang::clangd::dex::Dex::Dex
Dex(SymbolRange &&Symbols, RefsRange &&Refs, RelationsRange &&Relations, FileRange &&Files, IndexContents IdxContents, Payload &&BackingData, size_t BackingDataSize)
Definition: Dex.h:65
clang::clangd::dex::Dex::lookup
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: Dex.cpp:290
clang::clangd::dex::Dex::relations
void relations(const RelationsRequest &Req, llvm::function_ref< void(const SymbolID &, const Symbol &)> Callback) const override
Definition: Dex.cpp:317
clang::clangd::dex::Dex::Dex
Dex(SymbolRange &&Symbols, RefsRange &&Refs, RelationsRange &&Relations, Payload &&BackingData, size_t BackingDataSize)
Definition: Dex.h:54
Index.h
clang::clangd::dex::Dex::build
static std::unique_ptr< SymbolIndex > build(SymbolSlab, RefSlab, RelationSlab)
Builds an index from slabs. The index takes ownership of the slab.
Definition: Dex.cpp:34
clang::clangd::RefSlab
An efficient structure of storing large set of symbol references in memory.
Definition: Ref.h:108
clang::clangd::FuzzyFindRequest
Definition: Index.h:26
clang::clangd::dex::Dex::estimateMemoryUsage
size_t estimateMemoryUsage() const override
Returns estimated size of index (in bytes).
Definition: Dex.cpp:346
clang::clangd::dex::Corpus
Definition: Iterator.h:133
Relation.h
clang::clangd::dex::Dex
In-memory Dex trigram-based index implementation.
Definition: Dex.h:35
clang::clangd::RelationSlab
Definition: Relation.h:50
PostingList.h
clang::clangd::dex::generateProximityURIs
std::vector< std::string > generateProximityURIs(llvm::StringRef URIPath)
Returns Search Token for a number of parent directories of given Path.
Definition: Dex.cpp:358
clang::clangd::Symbol
The class presents a C++ symbol, e.g.
Definition: Symbol.h:36
clang::clangd::IndexContents
IndexContents
Describes what data is covered by an index.
Definition: Index.h:93
Payload
std::string Payload
Definition: SourceCode.cpp:653
clang::clangd::dex::Dex::indexedFiles
llvm::unique_function< IndexContents(llvm::StringRef) const > indexedFiles() const override
Definition: Dex.cpp:340
clang::clangd::dex::Token
A Token represents an attribute of a symbol, such as a particular trigram present in the name (used f...
Definition: Token.h:38
Iterator.h
clang::clangd::dex::Dex::refs
bool refs(const RefsRequest &Req, llvm::function_ref< void(const Ref &)> Callback) const override
Finds all occurrences (e.g.
Definition: Dex.cpp:300
clang::clangd::SymbolIndex
Interface for symbol indexes that can be used for searching or matching symbols among a set of symbol...
Definition: Index.h:113
clang::clangd::LookupRequest
Definition: Index.h:64
clang::clangd::Ref
Represents a symbol occurrence in the source file.
Definition: Ref.h:85
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::clangd::dex::Dex::fuzzyFind
bool fuzzyFind(const FuzzyFindRequest &Req, llvm::function_ref< void(const Symbol &)> Callback) const override
Constructs iterators over tokens extracted from the query and exhausts it while applying Callback to ...
Definition: Dex.cpp:211
clang::clangd::Callback
llvm::unique_function< void(llvm::Expected< T >)> Callback
A Callback<T> is a void function that accepts Expected<T>.
Definition: Function.h:28
clang::clangd::RelationsRequest
Definition: Index.h:80
clang::clangd::SymbolSlab
An immutable symbol container that stores a set of symbols.
Definition: Symbol.h:177
clang::clangd::dex::Dex::Dex
Dex(SymbolRange &&Symbols, RefsRange &&Refs, RelationsRange &&Relations)
Definition: Dex.h:39
clang::clangd::SymbolID
Definition: SymbolID.h:32
Token.h
clang::clangd::RefsRequest
Definition: Index.h:68
clang::clangd::RelationKind
RelationKind
Definition: Relation.h:20