clang-tools  14.0.0git
FileIndex.h
Go to the documentation of this file.
1 //===--- FileIndex.h - Index for files. ---------------------------- 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 // FileIndex implements SymbolIndex for symbols from a set of files. Symbols are
10 // maintained at source-file granularity (e.g. with ASTs), and files can be
11 // updated dynamically.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H
16 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H
17 
18 #include "Headers.h"
19 #include "Index.h"
20 #include "MemIndex.h"
21 #include "Merge.h"
23 #include "index/Ref.h"
24 #include "index/Relation.h"
25 #include "index/Serialization.h"
26 #include "index/Symbol.h"
27 #include "support/MemoryTree.h"
28 #include "support/Path.h"
29 #include "clang/Lex/Preprocessor.h"
30 #include "clang/Tooling/CompilationDatabase.h"
31 #include "llvm/ADT/DenseSet.h"
32 #include "llvm/ADT/Optional.h"
33 #include "llvm/ADT/StringMap.h"
34 #include "llvm/ADT/StringRef.h"
35 #include <memory>
36 #include <vector>
37 
38 namespace clang {
39 class ASTContext;
40 namespace clangd {
41 class ParsedAST;
42 
43 /// Select between in-memory index implementations, which have tradeoffs.
44 enum class IndexType {
45  // MemIndex is trivially cheap to build, but has poor query performance.
46  Light,
47  // Dex is relatively expensive to build and uses more memory, but is fast.
48  Heavy,
49 };
50 
51 /// How to handle duplicated symbols across multiple files.
52 enum class DuplicateHandling {
53  // Pick a random symbol. Less accurate but faster.
54  PickOne,
55  // Merge symbols. More accurate but slower.
56  Merge,
57 };
58 
59 /// A container of slabs associated with a key. It can be updated at key
60 /// granularity, replacing all slabs belonging to a key with a new set. Keys are
61 /// usually file paths/uris.
62 ///
63 /// This implements snapshot semantics. Each update will create a new snapshot
64 /// for all slabs of the Key. Snapshots are managed with shared pointers that
65 /// are shared between this class and the users. For each key, this class only
66 /// stores a pointer pointing to the newest snapshot, and an outdated snapshot
67 /// is deleted by the last owner of the snapshot, either this class or the
68 /// symbol index.
69 ///
70 /// The snapshot semantics keeps critical sections minimal since we only need
71 /// locking when we swap or obtain references to snapshots.
72 class FileSymbols {
73 public:
74  FileSymbols(IndexContents IdxContents);
75  /// Updates all slabs associated with the \p Key.
76  /// If either is nullptr, corresponding data for \p Key will be removed.
77  /// If CountReferences is true, \p Refs will be used for counting references
78  /// during merging.
79  void update(llvm::StringRef Key, std::unique_ptr<SymbolSlab> Symbols,
80  std::unique_ptr<RefSlab> Refs,
81  std::unique_ptr<RelationSlab> Relations, bool CountReferences);
82 
83  /// The index keeps the slabs alive.
84  /// Will count Symbol::References based on number of references in the main
85  /// files, while building the index with DuplicateHandling::Merge option.
86  /// Version is populated with an increasing sequence counter.
87  std::unique_ptr<SymbolIndex>
90  size_t *Version = nullptr);
91 
92  void profile(MemoryTree &MT) const;
93 
94 private:
95  IndexContents IdxContents;
96 
97  struct RefSlabAndCountReferences {
98  std::shared_ptr<RefSlab> Slab;
99  bool CountReferences = false;
100  };
101  mutable std::mutex Mutex;
102 
103  size_t Version = 0;
104  llvm::StringMap<std::shared_ptr<SymbolSlab>> SymbolsSnapshot;
105  llvm::StringMap<RefSlabAndCountReferences> RefsSnapshot;
106  llvm::StringMap<std::shared_ptr<RelationSlab>> RelationsSnapshot;
107 };
108 
109 /// This manages symbols from files and an in-memory index on all symbols.
110 /// FIXME: Expose an interface to remove files that are closed.
111 class FileIndex : public MergedIndex {
112 public:
113  FileIndex();
114 
115  /// Update preamble symbols of file \p Path with all declarations in \p AST
116  /// and macros in \p PP.
117  void updatePreamble(PathRef Path, llvm::StringRef Version, ASTContext &AST,
118  std::shared_ptr<Preprocessor> PP,
119  const CanonicalIncludes &Includes);
120 
121  /// Update symbols and references from main file \p Path with
122  /// `indexMainDecls`.
123  void updateMain(PathRef Path, ParsedAST &AST);
124 
125  void profile(MemoryTree &MT) const;
126 
127 private:
128  // Contains information from each file's preamble only. Symbols and relations
129  // are sharded per declaration file to deduplicate multiple symbols and reduce
130  // memory usage.
131  // Missing information:
132  // - symbol refs (these are always "from the main file")
133  // - definition locations in the main file
134  //
135  // Note that we store only one version of a header, hence symbols appearing in
136  // different PP states will be missing.
137  FileSymbols PreambleSymbols;
138  SwapIndex PreambleIndex;
139 
140  // Contains information from each file's main AST.
141  // These are updated frequently (on file change), but are relatively small.
142  // Mostly contains:
143  // - refs to symbols declared in the preamble and referenced from main
144  // - symbols declared both in the main file and the preamble
145  // (Note that symbols *only* in the main file are not indexed).
146  FileSymbols MainFileSymbols;
147  SwapIndex MainFileIndex;
148 
149  // While both the FileIndex and SwapIndex are threadsafe, we need to track
150  // versions to ensure that we don't overwrite newer indexes with older ones.
151  std::mutex UpdateIndexMu;
152  unsigned MainIndexVersion = 0;
153  unsigned PreambleIndexVersion = 0;
154 };
155 
156 using SlabTuple = std::tuple<SymbolSlab, RefSlab, RelationSlab>;
157 
158 /// Retrieves symbols and refs of local top level decls in \p AST (i.e.
159 /// `AST.getLocalTopLevelDecls()`).
160 /// Exposed to assist in unit tests.
162 
163 /// Index declarations from \p AST and macros from \p PP that are declared in
164 /// included headers.
165 SlabTuple indexHeaderSymbols(llvm::StringRef Version, ASTContext &AST,
166  std::shared_ptr<Preprocessor> PP,
167  const CanonicalIncludes &Includes);
168 
169 /// Takes slabs coming from a TU (multiple files) and shards them per
170 /// declaration location.
172  /// \p HintPath is used to convert file URIs stored in symbols into absolute
173  /// paths.
174  explicit FileShardedIndex(IndexFileIn Input);
175 
176  /// Returns uris for all files that has a shard.
177  std::vector<llvm::StringRef> getAllSources() const;
178 
179  /// Generates index shard for the \p Uri. Note that this function results in
180  /// a copy of all the relevant data.
181  /// Returned index will always have Symbol/Refs/Relation Slabs set, even if
182  /// they are empty.
183  llvm::Optional<IndexFileIn> getShard(llvm::StringRef Uri) const;
184 
185 private:
186  // Contains all the information that belongs to a single file.
187  struct FileShard {
188  // Either declared or defined in the file.
189  llvm::DenseSet<const Symbol *> Symbols;
190  // Reference occurs in the file.
191  llvm::DenseSet<const Ref *> Refs;
192  // Subject is declared in the file.
193  llvm::DenseSet<const Relation *> Relations;
194  // Contains edges for only the direct includes.
195  IncludeGraph IG;
196  };
197 
198  // Keeps all the information alive.
199  const IndexFileIn Index;
200  // Mapping from URIs to slab information.
201  llvm::StringMap<FileShard> Shards;
202  // Used to build RefSlabs.
203  llvm::DenseMap<const Ref *, SymbolID> RefToSymID;
204 };
205 
206 } // namespace clangd
207 } // namespace clang
208 
209 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H
clang::clangd::IndexType
IndexType
Select between in-memory index implementations, which have tradeoffs.
Definition: FileIndex.h:44
clang::clangd::FileIndex::FileIndex
FileIndex()
Definition: FileIndex.cpp:419
Headers.h
Refs
RefSlab Refs
Definition: SymbolCollectorTests.cpp:311
clang::clangd::Path
std::string Path
A typedef to represent a file path.
Definition: Path.h:26
clang::clangd::IndexFileIn
Definition: Serialization.h:42
Path.h
clang::clangd::SwapIndex
Definition: Index.h:161
Index.h
clang::clangd::FileShardedIndex::FileShardedIndex
FileShardedIndex(IndexFileIn Input)
HintPath is used to convert file URIs stored in symbols into absolute paths.
Definition: FileIndex.cpp:124
clang::clangd::FileIndex
This manages symbols from files and an in-memory index on all symbols.
Definition: FileIndex.h:111
clang::clangd::FileSymbols
A container of slabs associated with a key.
Definition: FileIndex.h:72
clang::clangd::DuplicateHandling
DuplicateHandling
How to handle duplicated symbols across multiple files.
Definition: FileIndex.h:52
clang::clangd::FileShardedIndex::getShard
llvm::Optional< IndexFileIn > getShard(llvm::StringRef Uri) const
Generates index shard for the Uri.
Definition: FileIndex.cpp:190
Relation.h
clang::clangd::MergedIndex
Definition: Merge.h:26
MemIndex.h
CanonicalIncludes.h
clang::clangd::MemoryTree
A tree that can be used to represent memory usage of nested components while preserving the hierarchy...
Definition: MemoryTree.h:32
clang::clangd::CanonicalIncludes
Maps a definition location onto an #include file, based on a set of filename rules.
Definition: CanonicalIncludes.h:36
clang::clangd::IndexContents
IndexContents
Describes what data is covered by an index.
Definition: Index.h:91
clang::clangd::FileSymbols::update
void update(llvm::StringRef Key, std::unique_ptr< SymbolSlab > Symbols, std::unique_ptr< RefSlab > Refs, std::unique_ptr< RelationSlab > Relations, bool CountReferences)
Updates all slabs associated with the Key.
Definition: FileIndex.cpp:242
clang::clangd::DuplicateHandling::PickOne
@ PickOne
clang::clangd::FileIndex::profile
void profile(MemoryTree &MT) const
Definition: FileIndex.cpp:489
clang::clangd::SlabTuple
std::tuple< SymbolSlab, RefSlab, RelationSlab > SlabTuple
Definition: FileIndex.h:156
Serialization.h
clang::clangd::indexHeaderSymbols
SlabTuple indexHeaderSymbols(llvm::StringRef Version, ASTContext &AST, std::shared_ptr< Preprocessor > PP, const CanonicalIncludes &Includes)
Index declarations from AST and macros from PP that are declared in included headers.
Definition: FileIndex.cpp:227
clang::clangd::Key
Values in a Context are indexed by typed keys.
Definition: Context.h:40
clang::clangd::FileSymbols::profile
void profile(MemoryTree &MT) const
Definition: FileIndex.cpp:400
clang::clangd::DuplicateHandling::Merge
@ Merge
Symbol.h
clang::tidy::bugprone::PP
static Preprocessor * PP
Definition: BadSignalToKillThreadCheck.cpp:29
clang::clangd::FileIndex::updateMain
void updateMain(PathRef Path, ParsedAST &AST)
Update symbols and references from main file Path with indexMainDecls.
Definition: FileIndex.cpp:463
clang::clangd::FileShardedIndex::getAllSources
std::vector< llvm::StringRef > getAllSources() const
Returns uris for all files that has a shard.
Definition: FileIndex.cpp:179
clang::clangd::PathRef
llvm::StringRef PathRef
A typedef to represent a ref to file path.
Definition: Path.h:29
clang::clangd::FileShardedIndex
Takes slabs coming from a TU (multiple files) and shards them per declaration location.
Definition: FileIndex.h:171
Ref.h
MemoryTree.h
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::clangd::IncludeGraph
llvm::StringMap< IncludeGraphNode > IncludeGraph
Definition: Headers.h:86
clang::clangd::FileSymbols::buildIndex
std::unique_ptr< SymbolIndex > buildIndex(IndexType, DuplicateHandling DuplicateHandle=DuplicateHandling::PickOne, size_t *Version=nullptr)
The index keeps the slabs alive.
Definition: FileIndex.cpp:268
clang::clangd::ParsedAST
Stores and provides access to parsed AST.
Definition: ParsedAST.h:49
clang::clangd::FileIndex::updatePreamble
void updatePreamble(PathRef Path, llvm::StringRef Version, ASTContext &AST, std::shared_ptr< Preprocessor > PP, const CanonicalIncludes &Includes)
Update preamble symbols of file Path with all declarations in AST and macros in PP.
Definition: FileIndex.cpp:426
Merge.h
clang::clangd::IndexType::Heavy
@ Heavy
clang::clangd::FileSymbols::FileSymbols
FileSymbols(IndexContents IdxContents)
Definition: FileIndex.cpp:239
clang::clangd::IndexType::Light
@ Light
clang::clangd::indexMainDecls
SlabTuple indexMainDecls(ParsedAST &AST)
Retrieves symbols and refs of local top level decls in AST (i.e.
Definition: FileIndex.cpp:220