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