1 #pragma once
2
3 #include "indexer.h"
4 #include "serializer.h"
5
6 #include <sparsepp/spp.h>
7
8 #include <forward_list>
9 #include <functional>
10
11 struct QueryFile;
12 struct QueryType;
13 struct QueryFunc;
14 struct QueryVar;
15 struct QueryDatabase;
16
17 struct IdMap;
18
19 // |id|,|kind| refer to the referenced entity.
20 struct QuerySymbolRef : Reference {
21 QuerySymbolRef() = default;
QuerySymbolRefQuerySymbolRef22 QuerySymbolRef(Range range, AnyId id, SymbolKind kind, Role role)
23 : Reference{range, id, kind, role} {}
24 };
25
26 // |id|,|kind| refer to the lexical parent.
27 struct QueryLexicalRef : Reference {
28 Id<QueryFile> file;
29 QueryLexicalRef() = default;
QueryLexicalRefQueryLexicalRef30 QueryLexicalRef(Range range,
31 AnyId id,
32 SymbolKind kind,
33 Role role,
34 Id<QueryFile> file)
35 : Reference{range, id, kind, role}, file(file) {}
36 };
37 // Used by |HANDLE_MERGEABLE| so only |range| is needed.
38 MAKE_HASHABLE(QueryLexicalRef, t.range);
39
40 struct QueryId {
41 using File = Id<QueryFile>;
42 using Func = Id<QueryFunc>;
43 using Type = Id<QueryType>;
44 using Var = Id<QueryVar>;
45 using SymbolRef = QuerySymbolRef;
46 using LexicalRef = QueryLexicalRef;
47 };
48
49 // There are two sources of reindex updates: the (single) definition of a
50 // symbol has changed, or one of many users of the symbol has changed.
51 //
52 // For simplicitly, if the single definition has changed, we update all of the
53 // associated single-owner definition data. See |Update*DefId|.
54 //
55 // If one of the many symbol users submits an update, we store the update such
56 // that it can be merged with other updates before actually being applied to
57 // the main database. See |MergeableUpdate|.
58
59 template <typename TId, typename TValue>
60 struct MergeableUpdate {
61 // The type/func/var which is getting new usages.
62 TId id;
63 // Entries to add and remove.
64 std::vector<TValue> to_add;
65 std::vector<TValue> to_remove;
66
MergeableUpdateMergeableUpdate67 MergeableUpdate(TId id, std::vector<TValue>&& to_add)
68 : id(id), to_add(std::move(to_add)) {}
MergeableUpdateMergeableUpdate69 MergeableUpdate(TId id,
70 std::vector<TValue>&& to_add,
71 std::vector<TValue>&& to_remove)
72 : id(id), to_add(std::move(to_add)), to_remove(std::move(to_remove)) {}
73 };
74 template <typename TVisitor, typename TId, typename TValue>
Reflect(TVisitor & visitor,MergeableUpdate<TId,TValue> & value)75 void Reflect(TVisitor& visitor, MergeableUpdate<TId, TValue>& value) {
76 REFLECT_MEMBER_START();
77 REFLECT_MEMBER(id);
78 REFLECT_MEMBER(to_add);
79 REFLECT_MEMBER(to_remove);
80 REFLECT_MEMBER_END();
81 }
82
83 template <typename T>
84 struct WithUsr {
85 Usr usr;
86 T value;
87
WithUsrWithUsr88 WithUsr(Usr usr, const T& value) : usr(usr), value(value) {}
WithUsrWithUsr89 WithUsr(Usr usr, T&& value) : usr(usr), value(std::move(value)) {}
90 };
91 template <typename TVisitor, typename T>
Reflect(TVisitor & visitor,WithUsr<T> & value)92 void Reflect(TVisitor& visitor, WithUsr<T>& value) {
93 REFLECT_MEMBER_START();
94 REFLECT_MEMBER(usr);
95 REFLECT_MEMBER(value);
96 REFLECT_MEMBER_END();
97 }
98
99 template <typename T>
100 struct WithFileContent {
101 T value;
102 std::string file_content;
103
WithFileContentWithFileContent104 WithFileContent(const T& value, const std::string& file_content)
105 : value(value), file_content(file_content) {}
106 };
107 template <typename TVisitor, typename T>
Reflect(TVisitor & visitor,WithFileContent<T> & value)108 void Reflect(TVisitor& visitor, WithFileContent<T>& value) {
109 REFLECT_MEMBER_START();
110 REFLECT_MEMBER(value);
111 REFLECT_MEMBER(file_content);
112 REFLECT_MEMBER_END();
113 }
114
115 struct QueryFile {
116 struct Def {
117 QueryId::File file;
118 AbsolutePath path;
119 std::vector<std::string> args;
120 // Language identifier
121 std::string language;
122 // Includes in the file.
123 std::vector<IndexInclude> includes;
124 // Outline of the file (ie, for code lens).
125 std::vector<QueryId::SymbolRef> outline;
126 // Every symbol found in the file (ie, for goto definition)
127 std::vector<QueryId::SymbolRef> all_symbols;
128 // Parts of the file which are disabled.
129 std::vector<Range> inactive_regions;
130 // Used by |$cquery/freshenIndex|.
131 std::vector<AbsolutePath> dependencies;
132 };
133
134 using DefUpdate = WithFileContent<Def>;
135
136 optional<Def> def;
137 Maybe<AnyId> symbol_idx;
138
QueryFileQueryFile139 explicit QueryFile(const AbsolutePath& path) {
140 def = Def();
141 def->path = path;
142 }
143 };
144 MAKE_REFLECT_STRUCT(QueryFile::Def,
145 file,
146 path,
147 args,
148 language,
149 outline,
150 all_symbols,
151 inactive_regions,
152 dependencies);
153
154 template <typename Q, typename QDef>
155 struct QueryEntity {
156 using Def = QDef;
157 using DefUpdate = WithUsr<Def>;
158 using DeclarationsUpdate = MergeableUpdate<Id<Q>, QueryId::LexicalRef>;
159 using UsesUpdate = MergeableUpdate<Id<Q>, QueryId::LexicalRef>;
AnyDefQueryEntity160 Def* AnyDef() {
161 Def* ret = nullptr;
162 for (auto& i : static_cast<Q*>(this)->def) {
163 ret = &i;
164 if (i.spell)
165 break;
166 }
167 return ret;
168 }
AnyDefQueryEntity169 const Def* AnyDef() const { return const_cast<QueryEntity*>(this)->AnyDef(); }
170 };
171
172 struct QueryType : QueryEntity<QueryType, TypeDefDefinitionData<QueryId>> {
173 using DerivedUpdate = MergeableUpdate<QueryId::Type, QueryId::Type>;
174 using InstancesUpdate = MergeableUpdate<QueryId::Type, QueryId::Var>;
175
176 Usr usr;
177 Maybe<AnyId> symbol_idx;
178 std::forward_list<Def> def;
179 std::vector<QueryId::LexicalRef> declarations;
180 std::vector<QueryId::Type> derived;
181 std::vector<QueryId::Var> instances;
182 std::vector<QueryId::LexicalRef> uses;
183
QueryTypeQueryType184 explicit QueryType(const Usr& usr) : usr(usr) {}
185 };
186
187 struct QueryFunc : QueryEntity<QueryFunc, FuncDefDefinitionData<QueryId>> {
188 using DerivedUpdate = MergeableUpdate<QueryId::Func, QueryId::Func>;
189
190 Usr usr;
191 Maybe<AnyId> symbol_idx;
192 std::forward_list<Def> def;
193 std::vector<QueryId::LexicalRef> declarations;
194 std::vector<QueryId::Func> derived;
195 std::vector<QueryId::LexicalRef> uses;
196
QueryFuncQueryFunc197 explicit QueryFunc(const Usr& usr) : usr(usr) {}
198 };
199
200 struct QueryVar : QueryEntity<QueryVar, VarDefDefinitionData<QueryId>> {
201 Usr usr;
202 Maybe<AnyId> symbol_idx;
203 std::forward_list<Def> def;
204 std::vector<QueryId::LexicalRef> declarations;
205 std::vector<QueryId::LexicalRef> uses;
206
QueryVarQueryVar207 explicit QueryVar(const Usr& usr) : usr(usr) {}
208 };
209
210 struct IndexUpdate {
211 // Creates a new IndexUpdate based on the delta from previous to current. If
212 // no delta computation should be done just pass null for previous.
213 static IndexUpdate CreateDelta(const IdMap* previous_id_map,
214 const IdMap* current_id_map,
215 IndexFile* previous,
216 IndexFile* current);
217
218 // Merge |update| into this update; this can reduce overhead / index update
219 // work can be parallelized.
220 void Merge(IndexUpdate&& update);
221
222 // Dump the update to a string.
223 std::string ToString();
224
225 // File updates.
226 std::vector<AbsolutePath> files_removed;
227 std::vector<QueryFile::DefUpdate> files_def_update;
228
229 // Type updates.
230 std::vector<Usr> types_removed;
231 std::vector<QueryType::DefUpdate> types_def_update;
232 std::vector<QueryType::DeclarationsUpdate> types_declarations;
233 std::vector<QueryType::DerivedUpdate> types_derived;
234 std::vector<QueryType::InstancesUpdate> types_instances;
235 std::vector<QueryType::UsesUpdate> types_uses;
236
237 // Function updates.
238 std::vector<WithUsr<QueryId::File>> funcs_removed;
239 std::vector<QueryFunc::DefUpdate> funcs_def_update;
240 std::vector<QueryFunc::DeclarationsUpdate> funcs_declarations;
241 std::vector<QueryFunc::DerivedUpdate> funcs_derived;
242 std::vector<QueryFunc::UsesUpdate> funcs_uses;
243
244 // Variable updates.
245 std::vector<WithUsr<QueryId::File>> vars_removed;
246 std::vector<QueryVar::DefUpdate> vars_def_update;
247 std::vector<QueryVar::DeclarationsUpdate> vars_declarations;
248 std::vector<QueryVar::UsesUpdate> vars_uses;
249
250 private:
251 // Creates an index update assuming that |previous| is already
252 // in the index, so only the delta between |previous| and |current|
253 // will be applied.
254 IndexUpdate(const IdMap& previous_id_map,
255 const IdMap& current_id_map,
256 IndexFile& previous,
257 IndexFile& current);
258 };
259 // NOTICE: We're not reflecting on files_removed or files_def_update, it is too
260 // much output when logging
261 MAKE_REFLECT_STRUCT(IndexUpdate,
262 types_removed,
263 types_def_update,
264 types_derived,
265 types_instances,
266 types_uses,
267 funcs_removed,
268 funcs_def_update,
269 funcs_declarations,
270 funcs_derived,
271 funcs_uses,
272 vars_removed,
273 vars_def_update,
274 vars_declarations,
275 vars_uses);
276
277 // The query database is heavily optimized for fast queries. It is stored
278 // in-memory.
279 struct QueryDatabase {
280 // All File/Func/Type/Var symbols.
281 std::vector<SymbolIdx> symbols;
282
283 // Raw data storage. Accessible via SymbolIdx instances.
284 std::vector<QueryFile> files;
285 std::vector<QueryType> types;
286 std::vector<QueryFunc> funcs;
287 std::vector<QueryVar> vars;
288
289 // Lookup symbol based on a usr.
290 spp::sparse_hash_map<AbsolutePath, QueryId::File> usr_to_file;
291 spp::sparse_hash_map<Usr, QueryId::Type> usr_to_type;
292 spp::sparse_hash_map<Usr, QueryId::Func> usr_to_func;
293 spp::sparse_hash_map<Usr, QueryId::Var> usr_to_var;
294
295 // Marks the given Usrs as invalid.
296 void RemoveUsrs(SymbolKind usr_kind, const std::vector<Usr>& to_remove);
297 void RemoveUsrs(SymbolKind usr_kind,
298 const std::vector<WithUsr<QueryId::File>>& to_remove);
299 // Insert the contents of |update| into |db|.
300 void ApplyIndexUpdate(IndexUpdate* update);
301 void ImportOrUpdate(const std::vector<QueryFile::DefUpdate>& updates);
302 void ImportOrUpdate(std::vector<QueryType::DefUpdate>&& updates);
303 void ImportOrUpdate(std::vector<QueryFunc::DefUpdate>&& updates);
304 void ImportOrUpdate(std::vector<QueryVar::DefUpdate>&& updates);
305 void UpdateSymbols(Maybe<AnyId>* symbol_idx, SymbolKind kind, AnyId idx);
306 std::string_view GetSymbolDetailedName(RawId symbol_idx) const;
307 std::string_view GetSymbolShortName(RawId symbol_idx) const;
308
309 // Query the indexing structure to look up symbol id for given Usr.
310 Maybe<QueryId::File> GetQueryFileIdFromPath(const std::string& path);
311 Maybe<QueryId::Type> GetQueryTypeIdFromUsr(Usr usr);
312 Maybe<QueryId::Func> GetQueryFuncIdFromUsr(Usr usr);
313 Maybe<QueryId::Var> GetQueryVarIdFromUsr(Usr usr);
314
GetFileQueryDatabase315 QueryFile& GetFile(SymbolIdx ref) { return files[ref.id.id]; }
GetFuncQueryDatabase316 QueryFunc& GetFunc(SymbolIdx ref) { return funcs[ref.id.id]; }
GetTypeQueryDatabase317 QueryType& GetType(SymbolIdx ref) { return types[ref.id.id]; }
GetVarQueryDatabase318 QueryVar& GetVar(SymbolIdx ref) { return vars[ref.id.id]; }
319 };
320
321 template <typename I>
322 struct IndexToQuery;
323
324 // clang-format off
325 template <> struct IndexToQuery<IndexId::File> { using type = QueryId::File; };
326 template <> struct IndexToQuery<IndexId::Func> { using type = QueryId::Func; };
327 template <> struct IndexToQuery<IndexId::Type> { using type = QueryId::Type; };
328 template <> struct IndexToQuery<IndexId::Var> { using type = QueryId::Var; };
329 template <> struct IndexToQuery<IndexId::SymbolRef> { using type = QueryId::SymbolRef; };
330 template <> struct IndexToQuery<IndexId::LexicalRef> { using type = QueryId::LexicalRef; };
331 template <> struct IndexToQuery<IndexFunc::Declaration> { using type = QueryId::LexicalRef; };
332 template <typename I> struct IndexToQuery<optional<I>> {
333 using type = optional<typename IndexToQuery<I>::type>;
334 };
335 template <typename I> struct IndexToQuery<std::vector<I>> {
336 using type = std::vector<typename IndexToQuery<I>::type>;
337 };
338 // clang-format on
339
340 struct IdMap {
341 const IdCache& local_ids;
342 QueryId::File primary_file;
343
344 IdMap(QueryDatabase* query_db, const IdCache& local_ids);
345
346 // clang-format off
347 Id<void> ToQuery(SymbolKind kind, Id<void> id) const;
348 QueryId::Type ToQuery(IndexId::Type id) const;
349 QueryId::Func ToQuery(IndexId::Func id) const;
350 QueryId::Var ToQuery(IndexId::Var id) const;
351 QueryId::SymbolRef ToQuery(IndexId::SymbolRef ref) const;
352 QueryId::LexicalRef ToQuery(IndexId::LexicalRef ref) const;
353 QueryId::LexicalRef ToQuery(IndexFunc::Declaration decl) const;
354 template <typename I>
355 Maybe<typename IndexToQuery<I>::type> ToQuery(Maybe<I> id) const {
356 if (!id)
357 return nullopt;
358 return ToQuery(*id);
359 }
360 template <typename I>
361 std::vector<typename IndexToQuery<I>::type> ToQuery(const std::vector<I>& a) const {
362 std::vector<typename IndexToQuery<I>::type> ret;
363 ret.reserve(a.size());
364 for (auto& x : a)
365 ret.push_back(ToQuery(x));
366 return ret;
367 }
368 // clang-format on
369
370 private:
371 spp::sparse_hash_map<IndexId::Type, QueryId::Type> cached_type_ids_;
372 spp::sparse_hash_map<IndexId::Func, QueryId::Func> cached_func_ids_;
373 spp::sparse_hash_map<IndexId::Var, QueryId::Var> cached_var_ids_;
374 };
375