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

   1 //===--- Index.h -------------------------------------------------*- 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 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
  10 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
  11
  12 #include "index/Ref.h"
  13 #include "index/Relation.h"
  14 #include "index/Symbol.h"
  15 #include "index/SymbolID.h"
  16 #include "llvm/ADT/DenseSet.h"
  17 #include "llvm/ADT/FunctionExtras.h"
  18 #include "llvm/ADT/Optional.h"
  19 #include "llvm/Support/JSON.h"
  20 #include <mutex>
  21 #include <string>
  22
  23 namespace clang {
  24 namespace clangd {
  25
  26 struct FuzzyFindRequest {
  27   /// A query string for the fuzzy find. This is matched against symbols'
  28   /// un-qualified identifiers and should not contain qualifiers like "::".
  29   std::string Query;
  30   /// If this is non-empty, symbols must be in at least one of the scopes
  31   /// (e.g. namespaces) excluding nested scopes. For example, if a scope "xyz::"
  32   /// is provided, the matched symbols must be defined in namespace xyz but not
  33   /// namespace xyz::abc.
  34   ///
  35   /// The global scope is "", a top level scope is "foo::", etc.
  36   std::vector<std::string> Scopes;
  37   /// If set to true, allow symbols from any scope. Scopes explicitly listed
  38   /// above will be ranked higher.
  39   bool AnyScope = false;
  40   /// The number of top candidates to return. The index may choose to
  41   /// return more than this, e.g. if it doesn't know which candidates are best.
  42   llvm::Optional<uint32_t> Limit;
  43   /// If set to true, only symbols for completion support will be considered.
  44   bool RestrictForCodeCompletion = false;
  45   /// Contextually relevant files (e.g. the file we're code-completing in).
  46   /// Paths should be absolute.
  47   std::vector<std::string> ProximityPaths;
  48   /// Preferred types of symbols. These are raw representation of `OpaqueType`.
  49   std::vector<std::string> PreferredTypes;
  50
  51   bool operator==(const FuzzyFindRequest &Req) const {
  52     return std::tie(Query, Scopes, Limit, RestrictForCodeCompletion,
  53                     ProximityPaths, PreferredTypes) ==
  54            std::tie(Req.Query, Req.Scopes, Req.Limit,
  55                     Req.RestrictForCodeCompletion, Req.ProximityPaths,
  56                     Req.PreferredTypes);
  57   }
  58   bool operator!=(const FuzzyFindRequest &Req) const { return !(*this == Req); }
  59 };
  60 bool fromJSON(const llvm::json::Value &Value, FuzzyFindRequest &Request,
  61               llvm::json::Path);
  62 llvm::json::Value toJSON(const FuzzyFindRequest &Request);
  63
  64 struct LookupRequest {
  65   llvm::DenseSet<SymbolID> IDs;
  66 };
  67
  68 struct RefsRequest {
  69   llvm::DenseSet<SymbolID> IDs;
  70   RefKind Filter = RefKind::All;
  71   /// If set, limit the number of refers returned from the index. The index may
  72   /// choose to return less than this, e.g. it tries to avoid returning stale
  73   /// results.
  74   llvm::Optional<uint32_t> Limit;
  75   /// If set, populates the container of the reference.
  76   /// Index implementations may chose to populate containers no matter what.
  77   bool WantContainer = false;
  78 };
  79
  80 struct RelationsRequest {
  81   llvm::DenseSet<SymbolID> Subjects;
  82   RelationKind Predicate;
  83   /// If set, limit the number of relations returned from the index.
  84   llvm::Optional<uint32_t> Limit;
  85 };
  86
  87 /// Describes what data is covered by an index.
  88 ///
  89 /// Indexes may contain symbols but not references from a file, etc.
  90 /// This affects merging: if a staler index contains a reference but a fresher
  91 /// one does not, we want to trust the fresher index *only* if it actually
  92 /// includes references in general.
  93 enum class IndexContents : uint8_t {
  94   None = 0,
  95   Symbols = 1 << 1,
  96   References = 1 << 2,
  97   Relations = 1 << 3,
  98   All = Symbols | References | Relations
  99 };
 100
 101 inline constexpr IndexContents operator&(IndexContents L, IndexContents R) {
 102   return static_cast<IndexContents>(static_cast<uint8_t>(L) &
 103                                     static_cast<uint8_t>(R));
 104 }
 105
 106 inline constexpr IndexContents operator|(IndexContents L, IndexContents R) {
 107   return static_cast<IndexContents>(static_cast<uint8_t>(L) |
 108                                     static_cast<uint8_t>(R));
 109 }
 110
 111 /// Interface for symbol indexes that can be used for searching or
 112 /// matching symbols among a set of symbols based on names or unique IDs.
 113 class SymbolIndex {
 114 public:
 115   virtual ~SymbolIndex() = default;
 116
 117   /// Matches symbols in the index fuzzily and applies \p Callback on
 118   /// each matched symbol before returning.
 119   /// If returned Symbols are used outside Callback, they must be deep-copied!
 120   ///
 121   /// Returns true if there may be more results (limited by Req.Limit).
 122   virtual bool
 123   fuzzyFind(const FuzzyFindRequest &Req,
 124             llvm::function_ref<void(const Symbol &)> Callback) const = 0;
 125
 126   /// Looks up symbols with any of the given symbol IDs and applies \p Callback
 127   /// on each matched symbol.
 128   /// The returned symbol must be deep-copied if it's used outside Callback.
 129   virtual void
 130   lookup(const LookupRequest &Req,
 131          llvm::function_ref<void(const Symbol &)> Callback) const = 0;
 132
 133   /// Finds all occurrences (e.g. references, declarations, definitions) of
 134   /// symbols and applies \p Callback on each result.
 135   ///
 136   /// Results should be returned in arbitrary order.
 137   /// The returned result must be deep-copied if it's used outside Callback.
 138   /// FIXME: there's no indication which result references which symbol.
 139   ///
 140   /// Returns true if there will be more results (limited by Req.Limit);
 141   virtual bool refs(const RefsRequest &Req,
 142                     llvm::function_ref<void(const Ref &)> Callback) const = 0;
 143
 144   /// Finds all relations (S, P, O) stored in the index such that S is among
 145   /// Req.Subjects and P is Req.Predicate, and invokes \p Callback for (S, O) in
 146   /// each.
 147   virtual void relations(
 148       const RelationsRequest &Req,
 149       llvm::function_ref<void(const SymbolID &Subject, const Symbol &Object)>
 150           Callback) const = 0;
 151
 152   /// Returns function which checks if the specified file was used to build this
 153   /// index or not. The function must only be called while the index is alive.
 154   using IndexedFiles =
 155       llvm::unique_function<IndexContents(llvm::StringRef) const>;
 156   virtual IndexedFiles indexedFiles() const = 0;
 157
 158   /// Returns estimated size of index (in bytes).
 159   virtual size_t estimateMemoryUsage() const = 0;
 160 };
 161
 162 // Delegating implementation of SymbolIndex whose delegate can be swapped out.
 163 class SwapIndex : public SymbolIndex {
 164 public:
 165   // If an index is not provided, reset() must be called.
 166   SwapIndex(std::unique_ptr<SymbolIndex> Index = nullptr)
 167       : Index(std::move(Index)) {}
 168   void reset(std::unique_ptr<SymbolIndex>);
 169
 170   // SymbolIndex methods delegate to the current index, which is kept alive
 171   // until the call returns (even if reset() is called).
 172   bool fuzzyFind(const FuzzyFindRequest &,
 173                  llvm::function_ref<void(const Symbol &)>) const override;
 174   void lookup(const LookupRequest &,
 175               llvm::function_ref<void(const Symbol &)>) const override;
 176   bool refs(const RefsRequest &,
 177             llvm::function_ref<void(const Ref &)>) const override;
 178   void relations(const RelationsRequest &,
 179                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
 180       const override;
 181
 182   llvm::unique_function<IndexContents(llvm::StringRef) const>
 183   indexedFiles() const override;
 184
 185   size_t estimateMemoryUsage() const override;
 186
 187 private:
 188   std::shared_ptr<SymbolIndex> snapshot() const;
 189   mutable std::mutex Mutex;
 190   std::shared_ptr<SymbolIndex> Index;
 191 };
 192
 193 } // namespace clangd
 194 } // namespace clang
 195
 196 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H