clang-tools-extra/clangd/index/FileIndex.h

   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