211 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// FileIndex implements SymbolIndex for symbols from a set of files. Symbols are10// maintained at source-file granularity (e.g. with ASTs), and files can be11// updated dynamically.12//13//===----------------------------------------------------------------------===//14 15#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H16#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H17 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 36namespace clang {37class ASTContext;38namespace clangd {39class ParsedAST;40 41/// Select between in-memory index implementations, which have tradeoffs.42enum 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.50enum 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 key58/// granularity, replacing all slabs belonging to a key with a new set. Keys are59/// usually file paths/uris.60///61/// This implements snapshot semantics. Each update will create a new snapshot62/// for all slabs of the Key. Snapshots are managed with shared pointers that63/// are shared between this class and the users. For each key, this class only64/// stores a pointer pointing to the newest snapshot, and an outdated snapshot65/// is deleted by the last owner of the snapshot, either this class or the66/// symbol index.67///68/// The snapshot semantics keeps critical sections minimal since we only need69/// locking when we swap or obtain references to snapshots.70class FileSymbols {71public:72 FileSymbols(IndexContents IdxContents, bool SupportContainedRefs);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 references76 /// 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 main83 /// 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 92private:93 IndexContents IdxContents;94 bool SupportContainedRefs;95 96 struct RefSlabAndCountReferences {97 std::shared_ptr<RefSlab> Slab;98 bool CountReferences = false;99 };100 mutable std::mutex Mutex;101 102 size_t Version = 0;103 llvm::StringMap<std::shared_ptr<SymbolSlab>> SymbolsSnapshot;104 llvm::StringMap<RefSlabAndCountReferences> RefsSnapshot;105 llvm::StringMap<std::shared_ptr<RelationSlab>> RelationsSnapshot;106};107 108/// This manages symbols from files and an in-memory index on all symbols.109/// FIXME: Expose an interface to remove files that are closed.110class FileIndex : public MergedIndex {111public:112 FileIndex(bool SupportContainedRefs);113 114 /// Update preamble symbols of file \p Path with all declarations in \p AST115 /// and macros in \p PP.116 void updatePreamble(PathRef Path, llvm::StringRef Version, ASTContext &AST,117 Preprocessor &PP,118 const include_cleaner::PragmaIncludes &PI);119 void updatePreamble(IndexFileIn);120 121 /// Update symbols and references from main file \p Path with122 /// `indexMainDecls`.123 void updateMain(PathRef Path, ParsedAST &AST);124 125 void profile(MemoryTree &MT) const;126 127private:128 // Contains information from each file's preamble only. Symbols and relations129 // are sharded per declaration file to deduplicate multiple symbols and reduce130 // memory usage.131 // Missing information:132 // - symbol refs (these are always "from the main file")133 // - definition locations in the main file134 //135 // Note that we store only one version of a header, hence symbols appearing in136 // 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 main144 // - symbols declared both in the main file and the preamble145 // (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 track150 // 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 156using 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.161SlabTuple indexMainDecls(ParsedAST &AST);162 163/// Index declarations from \p AST and macros from \p PP that are declared in164/// included headers.165SlabTuple indexHeaderSymbols(llvm::StringRef Version, ASTContext &AST,166 Preprocessor &PP,167 const include_cleaner::PragmaIncludes &PI,168 SymbolOrigin Origin);169 170/// Takes slabs coming from a TU (multiple files) and shards them per171/// declaration location.172struct FileShardedIndex {173 /// \p HintPath is used to convert file URIs stored in symbols into absolute174 /// paths.175 explicit FileShardedIndex(IndexFileIn Input);176 177 /// Returns uris for all files that has a shard.178 std::vector<llvm::StringRef> getAllSources() const;179 180 /// Generates index shard for the \p Uri. Note that this function results in181 /// a copy of all the relevant data.182 /// Returned index will always have Symbol/Refs/Relation Slabs set, even if183 /// they are empty.184 std::optional<IndexFileIn> getShard(llvm::StringRef Uri) const;185 186private:187 // Contains all the information that belongs to a single file.188 struct FileShard {189 // Either declared or defined in the file.190 llvm::DenseSet<const Symbol *> Symbols;191 // Reference occurs in the file.192 llvm::DenseSet<const Ref *> Refs;193 // Subject is declared in the file.194 llvm::DenseSet<const Relation *> Relations;195 // Contains edges for only the direct includes.196 IncludeGraph IG;197 };198 199 // Keeps all the information alive.200 const IndexFileIn Index;201 // Mapping from URIs to slab information.202 llvm::StringMap<FileShard> Shards;203 // Used to build RefSlabs.204 llvm::DenseMap<const Ref *, SymbolID> RefToSymID;205};206 207} // namespace clangd208} // namespace clang209 210#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H211