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 "index/CanonicalIncludes.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/Optional.h"
  31 #include "llvm/ADT/StringMap.h"
  32 #include "llvm/ADT/StringRef.h"
  33 #include <memory>
  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, const CanonicalIncludes &Includes);
 117   void updatePreamble(IndexFileIn);
 118
 119   /// Update symbols and references from main file \p Path with
 120   /// `indexMainDecls`.
 121   void updateMain(PathRef Path, ParsedAST &AST);
 122
 123   void profile(MemoryTree &MT) const;
 124
 125 private:
 126   // Contains information from each file's preamble only. Symbols and relations
 127   // are sharded per declaration file to deduplicate multiple symbols and reduce
 128   // memory usage.
 129   // Missing information:
 130   //  - symbol refs (these are always "from the main file")
 131   //  - definition locations in the main file
 132   //
 133   // Note that we store only one version of a header, hence symbols appearing in
 134   // different PP states will be missing.
 135   FileSymbols PreambleSymbols;
 136   SwapIndex PreambleIndex;
 137
 138   // Contains information from each file's main AST.
 139   // These are updated frequently (on file change), but are relatively small.
 140   // Mostly contains:
 141   //  - refs to symbols declared in the preamble and referenced from main
 142   //  - symbols declared both in the main file and the preamble
 143   // (Note that symbols *only* in the main file are not indexed).
 144   FileSymbols MainFileSymbols;
 145   SwapIndex MainFileIndex;
 146
 147   // While both the FileIndex and SwapIndex are threadsafe, we need to track
 148   // versions to ensure that we don't overwrite newer indexes with older ones.
 149   std::mutex UpdateIndexMu;
 150   unsigned MainIndexVersion = 0;
 151   unsigned PreambleIndexVersion = 0;
 152 };
 153
 154 using SlabTuple = std::tuple<SymbolSlab, RefSlab, RelationSlab>;
 155
 156 /// Retrieves symbols and refs of local top level decls in \p AST (i.e.
 157 /// `AST.getLocalTopLevelDecls()`).
 158 /// Exposed to assist in unit tests.
 159 SlabTuple indexMainDecls(ParsedAST &AST);
 160
 161 /// Index declarations from \p AST and macros from \p PP that are declared in
 162 /// included headers.
 163 SlabTuple indexHeaderSymbols(llvm::StringRef Version, ASTContext &AST,
 164                              Preprocessor &PP,
 165                              const CanonicalIncludes &Includes);
 166
 167 /// Takes slabs coming from a TU (multiple files) and shards them per
 168 /// declaration location.
 169 struct FileShardedIndex {
 170   /// \p HintPath is used to convert file URIs stored in symbols into absolute
 171   /// paths.
 172   explicit FileShardedIndex(IndexFileIn Input);
 173
 174   /// Returns uris for all files that has a shard.
 175   std::vector<llvm::StringRef> getAllSources() const;
 176
 177   /// Generates index shard for the \p Uri. Note that this function results in
 178   /// a copy of all the relevant data.
 179   /// Returned index will always have Symbol/Refs/Relation Slabs set, even if
 180   /// they are empty.
 181   llvm::Optional<IndexFileIn> getShard(llvm::StringRef Uri) const;
 182
 183 private:
 184   // Contains all the information that belongs to a single file.
 185   struct FileShard {
 186     // Either declared or defined in the file.
 187     llvm::DenseSet<const Symbol *> Symbols;
 188     // Reference occurs in the file.
 189     llvm::DenseSet<const Ref *> Refs;
 190     // Subject is declared in the file.
 191     llvm::DenseSet<const Relation *> Relations;
 192     // Contains edges for only the direct includes.
 193     IncludeGraph IG;
 194   };
 195
 196   // Keeps all the information alive.
 197   const IndexFileIn Index;
 198   // Mapping from URIs to slab information.
 199   llvm::StringMap<FileShard> Shards;
 200   // Used to build RefSlabs.
 201   llvm::DenseMap<const Ref *, SymbolID> RefToSymID;
 202 };
 203
 204 } // namespace clangd
 205 } // namespace clang
 206
 207 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H