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/Support/JSON.h" 19 #include <mutex> 20 #include <optional> 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 std::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 std::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 ContainedRefsRequest { 81 /// Note that RefKind::Call just restricts the matched SymbolKind to 82 /// functions, not the form of the reference (e.g. address-of-function, 83 /// which can indicate an indirect call, should still be caught). 84 static const RefKind SupportedRefKinds = RefKind::Call; 85 86 SymbolID ID; 87 /// If set, limit the number of refers returned from the index. The index may 88 /// choose to return less than this, e.g. it tries to avoid returning stale 89 /// results. 90 std::optional<uint32_t> Limit; 91 }; 92 93 struct RelationsRequest { 94 llvm::DenseSet<SymbolID> Subjects; 95 RelationKind Predicate; 96 /// If set, limit the number of relations returned from the index. 97 std::optional<uint32_t> Limit; 98 }; 99 100 struct ContainedRefsResult { 101 /// The source location where the symbol is named. 102 SymbolLocation Location; 103 RefKind Kind = RefKind::Unknown; 104 /// The ID of the symbol which is referred to 105 SymbolID Symbol; 106 }; 107 108 /// Describes what data is covered by an index. 109 /// 110 /// Indexes may contain symbols but not references from a file, etc. 111 /// This affects merging: if a staler index contains a reference but a fresher 112 /// one does not, we want to trust the fresher index *only* if it actually 113 /// includes references in general. 114 enum class IndexContents : uint8_t { 115 None = 0, 116 Symbols = 1 << 1, 117 References = 1 << 2, 118 Relations = 1 << 3, 119 All = Symbols | References | Relations 120 }; 121 122 inline constexpr IndexContents operator&(IndexContents L, IndexContents R) { 123 return static_cast<IndexContents>(static_cast<uint8_t>(L) & 124 static_cast<uint8_t>(R)); 125 } 126 127 inline constexpr IndexContents operator|(IndexContents L, IndexContents R) { 128 return static_cast<IndexContents>(static_cast<uint8_t>(L) | 129 static_cast<uint8_t>(R)); 130 } 131 132 /// Interface for symbol indexes that can be used for searching or 133 /// matching symbols among a set of symbols based on names or unique IDs. 134 class SymbolIndex { 135 public: 136 virtual ~SymbolIndex() = default; 137 138 /// Matches symbols in the index fuzzily and applies \p Callback on 139 /// each matched symbol before returning. 140 /// If returned Symbols are used outside Callback, they must be deep-copied! 141 /// 142 /// Returns true if there may be more results (limited by Req.Limit). 143 virtual bool 144 fuzzyFind(const FuzzyFindRequest &Req, 145 llvm::function_ref<void(const Symbol &)> Callback) const = 0; 146 147 /// Looks up symbols with any of the given symbol IDs and applies \p Callback 148 /// on each matched symbol. 149 /// The returned symbol must be deep-copied if it's used outside Callback. 150 virtual void 151 lookup(const LookupRequest &Req, 152 llvm::function_ref<void(const Symbol &)> Callback) const = 0; 153 154 /// Finds all occurrences (e.g. references, declarations, definitions) of 155 /// symbols and applies \p Callback on each result. 156 /// 157 /// Results should be returned in arbitrary order. 158 /// The returned result must be deep-copied if it's used outside Callback. 159 /// FIXME: there's no indication which result references which symbol. 160 /// 161 /// Returns true if there will be more results (limited by Req.Limit); 162 virtual bool refs(const RefsRequest &Req, 163 llvm::function_ref<void(const Ref &)> Callback) const = 0; 164 165 /// Find all symbols that are referenced by a symbol and apply 166 /// \p Callback on each result. 167 /// 168 /// Results should be returned in arbitrary order. 169 /// The returned result must be deep-copied if it's used outside Callback. 170 /// 171 /// Returns true if there will be more results (limited by Req.Limit); 172 virtual bool containedRefs( 173 const ContainedRefsRequest &Req, 174 llvm::function_ref<void(const ContainedRefsResult &)> Callback) const = 0; 175 176 /// Finds all relations (S, P, O) stored in the index such that S is among 177 /// Req.Subjects and P is Req.Predicate, and invokes \p Callback for (S, O) in 178 /// each. 179 virtual void relations( 180 const RelationsRequest &Req, 181 llvm::function_ref<void(const SymbolID &Subject, const Symbol &Object)> 182 Callback) const = 0; 183 184 /// Returns function which checks if the specified file was used to build this 185 /// index or not. The function must only be called while the index is alive. 186 using IndexedFiles = 187 llvm::unique_function<IndexContents(llvm::StringRef) const>; 188 virtual IndexedFiles indexedFiles() const = 0; 189 190 /// Returns estimated size of index (in bytes). 191 virtual size_t estimateMemoryUsage() const = 0; 192 }; 193 194 // Delegating implementation of SymbolIndex whose delegate can be swapped out. 195 class SwapIndex : public SymbolIndex { 196 public: 197 // If an index is not provided, reset() must be called. 198 SwapIndex(std::unique_ptr<SymbolIndex> Index = nullptr) 199 : Index(std::move(Index)) {} 200 void reset(std::unique_ptr<SymbolIndex>); 201 202 // SymbolIndex methods delegate to the current index, which is kept alive 203 // until the call returns (even if reset() is called). 204 bool fuzzyFind(const FuzzyFindRequest &, 205 llvm::function_ref<void(const Symbol &)>) const override; 206 void lookup(const LookupRequest &, 207 llvm::function_ref<void(const Symbol &)>) const override; 208 bool refs(const RefsRequest &, 209 llvm::function_ref<void(const Ref &)>) const override; 210 bool containedRefs( 211 const ContainedRefsRequest &, 212 llvm::function_ref<void(const ContainedRefsResult &)>) const override; 213 void relations(const RelationsRequest &, 214 llvm::function_ref<void(const SymbolID &, const Symbol &)>) 215 const override; 216 217 llvm::unique_function<IndexContents(llvm::StringRef) const> 218 indexedFiles() const override; 219 220 size_t estimateMemoryUsage() const override; 221 222 private: 223 std::shared_ptr<SymbolIndex> snapshot() const; 224 mutable std::mutex Mutex; 225 std::shared_ptr<SymbolIndex> Index; 226 }; 227 228 } // namespace clangd 229 } // namespace clang 230 231 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H 232