llvm-project

1
//===--- FileIndex.cpp - Indexes 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
#include "FileIndex.h"
10
#include "CollectMacros.h"
11
#include "ParsedAST.h"
12
#include "clang-include-cleaner/Record.h"
13
#include "index/Index.h"
14
#include "index/MemIndex.h"
15
#include "index/Merge.h"
16
#include "index/Ref.h"
17
#include "index/Relation.h"
18
#include "index/Serialization.h"
19
#include "index/Symbol.h"
20
#include "index/SymbolCollector.h"
21
#include "index/SymbolID.h"
22
#include "index/SymbolOrigin.h"
23
#include "index/dex/Dex.h"
24
#include "support/Logger.h"
25
#include "support/MemoryTree.h"
26
#include "support/Path.h"
27
#include "clang/AST/ASTContext.h"
28
#include "clang/Index/IndexingAction.h"
29
#include "clang/Index/IndexingOptions.h"
30
#include "clang/Lex/Preprocessor.h"
31
#include "llvm/ADT/DenseMap.h"
32
#include "llvm/ADT/STLExtras.h"
33
#include "llvm/ADT/StringMap.h"
34
#include "llvm/ADT/StringRef.h"
35
#include <algorithm>
36
#include <memory>
37
#include <optional>
38
#include <tuple>
39
#include <utility>
40
#include <vector>
41

42
namespace clang {
43
namespace clangd {
44
namespace {
45

46
SlabTuple indexSymbols(ASTContext &AST, Preprocessor &PP,
47
                       llvm::ArrayRef<Decl *> DeclsToIndex,
48
                       const MainFileMacros *MacroRefsToIndex,
49
                       const include_cleaner::PragmaIncludes &PI,
50
                       bool IsIndexMainAST, llvm::StringRef Version,
51
                       bool CollectMainFileRefs) {
52
  SymbolCollector::Options CollectorOpts;
53
  CollectorOpts.CollectIncludePath = true;
54
  CollectorOpts.PragmaIncludes = &PI;
55
  CollectorOpts.CountReferences = false;
56
  CollectorOpts.Origin =
57
      IsIndexMainAST ? SymbolOrigin::Open : SymbolOrigin::Preamble;
58
  CollectorOpts.CollectMainFileRefs = CollectMainFileRefs;
59
  // We want stdlib implementation details in the index only if we've opened the
60
  // file in question. This does means xrefs won't work, though.
61
  CollectorOpts.CollectReserved = IsIndexMainAST;
62

63
  index::IndexingOptions IndexOpts;
64
  // We only need declarations, because we don't count references.
65
  IndexOpts.SystemSymbolFilter =
66
      index::IndexingOptions::SystemSymbolFilterKind::DeclarationsOnly;
67
  // We index function-local classes and its member functions only.
68
  IndexOpts.IndexFunctionLocals = true;
69
  if (IsIndexMainAST) {
70
    // We only collect refs when indexing main AST.
71
    CollectorOpts.RefFilter = RefKind::All;
72
    // Comments for main file can always be obtained from sema, do not store
73
    // them in the index.
74
    CollectorOpts.StoreAllDocumentation = false;
75
  } else {
76
    IndexOpts.IndexMacrosInPreprocessor = true;
77
    CollectorOpts.CollectMacro = true;
78
    CollectorOpts.StoreAllDocumentation = true;
79
  }
80

81
  SymbolCollector Collector(std::move(CollectorOpts));
82
  Collector.setPreprocessor(PP);
83
  index::indexTopLevelDecls(AST, PP, DeclsToIndex, Collector, IndexOpts);
84
  if (MacroRefsToIndex)
85
    Collector.handleMacros(*MacroRefsToIndex);
86

87
  const auto &SM = AST.getSourceManager();
88
  const auto MainFileEntry = SM.getFileEntryRefForID(SM.getMainFileID());
89
  std::string FileName =
90
      std::string(MainFileEntry ? MainFileEntry->getName() : "");
91

92
  auto Syms = Collector.takeSymbols();
93
  auto Refs = Collector.takeRefs();
94
  auto Relations = Collector.takeRelations();
95

96
  vlog("indexed {0} AST for {1} version {2}:\n"
97
       "  symbol slab: {3} symbols, {4} bytes\n"
98
       "  ref slab: {5} symbols, {6} refs, {7} bytes\n"
99
       "  relations slab: {8} relations, {9} bytes",
100
       IsIndexMainAST ? "file" : "preamble", FileName, Version, Syms.size(),
101
       Syms.bytes(), Refs.size(), Refs.numRefs(), Refs.bytes(),
102
       Relations.size(), Relations.bytes());
103
  return std::make_tuple(std::move(Syms), std::move(Refs),
104
                         std::move(Relations));
105
}
106

107
// We keep only the node "U" and its edges. Any node other than "U" will be
108
// empty in the resultant graph.
109
IncludeGraph getSubGraph(llvm::StringRef URI, const IncludeGraph &FullGraph) {
110
  IncludeGraph IG;
111

112
  auto Entry = IG.try_emplace(URI).first;
113
  auto &Node = Entry->getValue();
114
  Node = FullGraph.lookup(Entry->getKey());
115
  Node.URI = Entry->getKey();
116

117
  // URIs inside nodes must point into the keys of the same IncludeGraph.
118
  for (auto &Include : Node.DirectIncludes) {
119
    auto I = IG.try_emplace(Include).first;
120
    I->getValue().URI = I->getKey();
121
    Include = I->getKey();
122
  }
123
  return IG;
124
}
125
} // namespace
126

127
FileShardedIndex::FileShardedIndex(IndexFileIn Input)
128
    : Index(std::move(Input)) {
129
  // Used to build RelationSlabs.
130
  llvm::DenseMap<SymbolID, FileShard *> SymbolIDToFile;
131

132
  // Attribute each Symbol to both their declaration and definition locations.
133
  if (Index.Symbols) {
134
    for (const auto &S : *Index.Symbols) {
135
      auto It = Shards.try_emplace(S.CanonicalDeclaration.FileURI);
136
      It.first->getValue().Symbols.insert(&S);
137
      SymbolIDToFile[S.ID] = &It.first->getValue();
138
      // Only bother if definition file is different than declaration file.
139
      if (S.Definition &&
140
          S.Definition.FileURI != S.CanonicalDeclaration.FileURI) {
141
        auto It = Shards.try_emplace(S.Definition.FileURI);
142
        It.first->getValue().Symbols.insert(&S);
143
      }
144
    }
145
  }
146
  // Attribute references into each file they occured in.
147
  if (Index.Refs) {
148
    for (const auto &SymRefs : *Index.Refs) {
149
      for (const auto &R : SymRefs.second) {
150
        const auto It = Shards.try_emplace(R.Location.FileURI);
151
        It.first->getValue().Refs.insert(&R);
152
        RefToSymID[&R] = SymRefs.first;
153
      }
154
    }
155
  }
156
  // The Subject and/or Object shards might be part of multiple TUs. In
157
  // such cases there will be a race and the last TU to write the shard
158
  // will win and all the other relations will be lost. To avoid this,
159
  // we store relations in both shards. A race might still happen if the
160
  // same translation unit produces different relations under different
161
  // configurations, but that's something clangd doesn't handle in general.
162
  if (Index.Relations) {
163
    for (const auto &R : *Index.Relations) {
164
      // FIXME: RelationSlab shouldn't contain dangling relations.
165
      FileShard *SubjectFile = SymbolIDToFile.lookup(R.Subject);
166
      FileShard *ObjectFile = SymbolIDToFile.lookup(R.Object);
167
      if (SubjectFile)
168
        SubjectFile->Relations.insert(&R);
169
      if (ObjectFile && ObjectFile != SubjectFile)
170
        ObjectFile->Relations.insert(&R);
171
    }
172
  }
173
  // Store only the direct includes of a file in a shard.
174
  if (Index.Sources) {
175
    const auto &FullGraph = *Index.Sources;
176
    for (const auto &It : FullGraph) {
177
      auto ShardIt = Shards.try_emplace(It.first());
178
      ShardIt.first->getValue().IG = getSubGraph(It.first(), FullGraph);
179
    }
180
  }
181
}
182
std::vector<llvm::StringRef> FileShardedIndex::getAllSources() const {
183
  // It should be enough to construct a vector with {Shards.keys().begin(),
184
  // Shards.keys().end()} but MSVC fails to compile that.
185
  std::vector<PathRef> Result;
186
  Result.reserve(Shards.size());
187
  for (auto Key : Shards.keys())
188
    Result.push_back(Key);
189
  return Result;
190
}
191

192
std::optional<IndexFileIn>
193
FileShardedIndex::getShard(llvm::StringRef Uri) const {
194
  auto It = Shards.find(Uri);
195
  if (It == Shards.end())
196
    return std::nullopt;
197

198
  IndexFileIn IF;
199
  IF.Sources = It->getValue().IG;
200
  IF.Cmd = Index.Cmd;
201

202
  SymbolSlab::Builder SymB;
203
  for (const auto *S : It->getValue().Symbols)
204
    SymB.insert(*S);
205
  IF.Symbols = std::move(SymB).build();
206

207
  RefSlab::Builder RefB;
208
  for (const auto *Ref : It->getValue().Refs) {
209
    auto SID = RefToSymID.lookup(Ref);
210
    RefB.insert(SID, *Ref);
211
  }
212
  IF.Refs = std::move(RefB).build();
213

214
  RelationSlab::Builder RelB;
215
  for (const auto *Rel : It->getValue().Relations) {
216
    RelB.insert(*Rel);
217
  }
218
  IF.Relations = std::move(RelB).build();
219
  // Explicit move here is needed by some compilers.
220
  return std::move(IF);
221
}
222

223
SlabTuple indexMainDecls(ParsedAST &AST) {
224
  return indexSymbols(
225
      AST.getASTContext(), AST.getPreprocessor(), AST.getLocalTopLevelDecls(),
226
      &AST.getMacros(), AST.getPragmaIncludes(),
227
      /*IsIndexMainAST=*/true, AST.version(), /*CollectMainFileRefs=*/true);
228
}
229

230
SlabTuple indexHeaderSymbols(llvm::StringRef Version, ASTContext &AST,
231
                             Preprocessor &PP,
232
                             const include_cleaner::PragmaIncludes &PI) {
233
  std::vector<Decl *> DeclsToIndex(
234
      AST.getTranslationUnitDecl()->decls().begin(),
235
      AST.getTranslationUnitDecl()->decls().end());
236
  return indexSymbols(AST, PP, DeclsToIndex,
237
                      /*MainFileMacros=*/nullptr, PI,
238
                      /*IsIndexMainAST=*/false, Version,
239
                      /*CollectMainFileRefs=*/false);
240
}
241

242
FileSymbols::FileSymbols(IndexContents IdxContents)
243
    : IdxContents(IdxContents) {}
244

245
void FileSymbols::update(llvm::StringRef Key,
246
                         std::unique_ptr<SymbolSlab> Symbols,
247
                         std::unique_ptr<RefSlab> Refs,
248
                         std::unique_ptr<RelationSlab> Relations,
249
                         bool CountReferences) {
250
  std::lock_guard<std::mutex> Lock(Mutex);
251
  ++Version;
252
  if (!Symbols)
253
    SymbolsSnapshot.erase(Key);
254
  else
255
    SymbolsSnapshot[Key] = std::move(Symbols);
256
  if (!Refs) {
257
    RefsSnapshot.erase(Key);
258
  } else {
259
    RefSlabAndCountReferences Item;
260
    Item.CountReferences = CountReferences;
261
    Item.Slab = std::move(Refs);
262
    RefsSnapshot[Key] = std::move(Item);
263
  }
264
  if (!Relations)
265
    RelationsSnapshot.erase(Key);
266
  else
267
    RelationsSnapshot[Key] = std::move(Relations);
268
}
269

270
std::unique_ptr<SymbolIndex>
271
FileSymbols::buildIndex(IndexType Type, DuplicateHandling DuplicateHandle,
272
                        size_t *Version) {
273
  std::vector<std::shared_ptr<SymbolSlab>> SymbolSlabs;
274
  std::vector<std::shared_ptr<RefSlab>> RefSlabs;
275
  std::vector<std::shared_ptr<RelationSlab>> RelationSlabs;
276
  llvm::StringSet<> Files;
277
  std::vector<RefSlab *> MainFileRefs;
278
  {
279
    std::lock_guard<std::mutex> Lock(Mutex);
280
    for (const auto &FileAndSymbols : SymbolsSnapshot) {
281
      SymbolSlabs.push_back(FileAndSymbols.second);
282
      Files.insert(FileAndSymbols.first());
283
    }
284
    for (const auto &FileAndRefs : RefsSnapshot) {
285
      RefSlabs.push_back(FileAndRefs.second.Slab);
286
      Files.insert(FileAndRefs.first());
287
      if (FileAndRefs.second.CountReferences)
288
        MainFileRefs.push_back(RefSlabs.back().get());
289
    }
290
    for (const auto &FileAndRelations : RelationsSnapshot) {
291
      Files.insert(FileAndRelations.first());
292
      RelationSlabs.push_back(FileAndRelations.second);
293
    }
294

295
    if (Version)
296
      *Version = this->Version;
297
  }
298
  std::vector<const Symbol *> AllSymbols;
299
  std::vector<Symbol> SymsStorage;
300
  switch (DuplicateHandle) {
301
  case DuplicateHandling::Merge: {
302
    llvm::DenseMap<SymbolID, Symbol> Merged;
303
    for (const auto &Slab : SymbolSlabs) {
304
      for (const auto &Sym : *Slab) {
305
        assert(Sym.References == 0 &&
306
               "Symbol with non-zero references sent to FileSymbols");
307
        auto I = Merged.try_emplace(Sym.ID, Sym);
308
        if (!I.second)
309
          I.first->second = mergeSymbol(I.first->second, Sym);
310
      }
311
    }
312
    for (const RefSlab *Refs : MainFileRefs)
313
      for (const auto &Sym : *Refs) {
314
        auto It = Merged.find(Sym.first);
315
        // This might happen while background-index is still running.
316
        if (It == Merged.end())
317
          continue;
318
        It->getSecond().References += Sym.second.size();
319
      }
320
    SymsStorage.reserve(Merged.size());
321
    for (auto &Sym : Merged) {
322
      SymsStorage.push_back(std::move(Sym.second));
323
      AllSymbols.push_back(&SymsStorage.back());
324
    }
325
    break;
326
  }
327
  case DuplicateHandling::PickOne: {
328
    llvm::DenseSet<SymbolID> AddedSymbols;
329
    for (const auto &Slab : SymbolSlabs)
330
      for (const auto &Sym : *Slab) {
331
        assert(Sym.References == 0 &&
332
               "Symbol with non-zero references sent to FileSymbols");
333
        if (AddedSymbols.insert(Sym.ID).second)
334
          AllSymbols.push_back(&Sym);
335
      }
336
    break;
337
  }
338
  }
339

340
  std::vector<Ref> RefsStorage; // Contiguous ranges for each SymbolID.
341
  llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> AllRefs;
342
  {
343
    llvm::DenseMap<SymbolID, llvm::SmallVector<Ref, 4>> MergedRefs;
344
    size_t Count = 0;
345
    for (const auto &RefSlab : RefSlabs)
346
      for (const auto &Sym : *RefSlab) {
347
        MergedRefs[Sym.first].append(Sym.second.begin(), Sym.second.end());
348
        Count += Sym.second.size();
349
      }
350
    RefsStorage.reserve(Count);
351
    AllRefs.reserve(MergedRefs.size());
352
    for (auto &Sym : MergedRefs) {
353
      auto &SymRefs = Sym.second;
354
      // Sorting isn't required, but yields more stable results over rebuilds.
355
      llvm::sort(SymRefs);
356
      llvm::copy(SymRefs, back_inserter(RefsStorage));
357
      AllRefs.try_emplace(
358
          Sym.first,
359
          llvm::ArrayRef<Ref>(&RefsStorage[RefsStorage.size() - SymRefs.size()],
360
                              SymRefs.size()));
361
    }
362
  }
363

364
  std::vector<Relation> AllRelations;
365
  for (const auto &RelationSlab : RelationSlabs) {
366
    for (const auto &R : *RelationSlab)
367
      AllRelations.push_back(R);
368
  }
369
  // Sort relations and remove duplicates that could arise due to
370
  // relations being stored in both the shards containing their
371
  // subject and object.
372
  llvm::sort(AllRelations);
373
  AllRelations.erase(std::unique(AllRelations.begin(), AllRelations.end()),
374
                     AllRelations.end());
375

376
  size_t StorageSize =
377
      RefsStorage.size() * sizeof(Ref) + SymsStorage.size() * sizeof(Symbol);
378
  for (const auto &Slab : SymbolSlabs)
379
    StorageSize += Slab->bytes();
380
  for (const auto &RefSlab : RefSlabs)
381
    StorageSize += RefSlab->bytes();
382

383
  // Index must keep the slabs and contiguous ranges alive.
384
  switch (Type) {
385
  case IndexType::Light:
386
    return std::make_unique<MemIndex>(
387
        llvm::make_pointee_range(AllSymbols), std::move(AllRefs),
388
        std::move(AllRelations), std::move(Files), IdxContents,
389
        std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
390
                        std::move(RefsStorage), std::move(SymsStorage)),
391
        StorageSize);
392
  case IndexType::Heavy:
393
    return std::make_unique<dex::Dex>(
394
        llvm::make_pointee_range(AllSymbols), std::move(AllRefs),
395
        std::move(AllRelations), std::move(Files), IdxContents,
396
        std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
397
                        std::move(RefsStorage), std::move(SymsStorage)),
398
        StorageSize);
399
  }
400
  llvm_unreachable("Unknown clangd::IndexType");
401
}
402

403
void FileSymbols::profile(MemoryTree &MT) const {
404
  std::lock_guard<std::mutex> Lock(Mutex);
405
  for (const auto &SymSlab : SymbolsSnapshot) {
406
    MT.detail(SymSlab.first())
407
        .child("symbols")
408
        .addUsage(SymSlab.second->bytes());
409
  }
410
  for (const auto &RefSlab : RefsSnapshot) {
411
    MT.detail(RefSlab.first())
412
        .child("references")
413
        .addUsage(RefSlab.second.Slab->bytes());
414
  }
415
  for (const auto &RelSlab : RelationsSnapshot) {
416
    MT.detail(RelSlab.first())
417
        .child("relations")
418
        .addUsage(RelSlab.second->bytes());
419
  }
420
}
421

422
FileIndex::FileIndex()
423
    : MergedIndex(&MainFileIndex, &PreambleIndex),
424
      PreambleSymbols(IndexContents::Symbols | IndexContents::Relations),
425
      PreambleIndex(std::make_unique<MemIndex>()),
426
      MainFileSymbols(IndexContents::All),
427
      MainFileIndex(std::make_unique<MemIndex>()) {}
428

429
void FileIndex::updatePreamble(IndexFileIn IF) {
430
  FileShardedIndex ShardedIndex(std::move(IF));
431
  for (auto Uri : ShardedIndex.getAllSources()) {
432
    auto IF = ShardedIndex.getShard(Uri);
433
    // We are using the key received from ShardedIndex, so it should always
434
    // exist.
435
    assert(IF);
436
    PreambleSymbols.update(
437
        Uri, std::make_unique<SymbolSlab>(std::move(*IF->Symbols)),
438
        std::make_unique<RefSlab>(),
439
        std::make_unique<RelationSlab>(std::move(*IF->Relations)),
440
        /*CountReferences=*/false);
441
  }
442
  size_t IndexVersion = 0;
443
  auto NewIndex = PreambleSymbols.buildIndex(
444
      IndexType::Heavy, DuplicateHandling::PickOne, &IndexVersion);
445
  {
446
    std::lock_guard<std::mutex> Lock(UpdateIndexMu);
447
    if (IndexVersion <= PreambleIndexVersion) {
448
      // We lost the race, some other thread built a later version.
449
      return;
450
    }
451
    PreambleIndexVersion = IndexVersion;
452
    PreambleIndex.reset(std::move(NewIndex));
453
    vlog(
454
        "Build dynamic index for header symbols with estimated memory usage of "
455
        "{0} bytes",
456
        PreambleIndex.estimateMemoryUsage());
457
  }
458
}
459

460
void FileIndex::updatePreamble(PathRef Path, llvm::StringRef Version,
461
                               ASTContext &AST, Preprocessor &PP,
462
                               const include_cleaner::PragmaIncludes &PI) {
463
  IndexFileIn IF;
464
  std::tie(IF.Symbols, std::ignore, IF.Relations) =
465
      indexHeaderSymbols(Version, AST, PP, PI);
466
  updatePreamble(std::move(IF));
467
}
468

469
void FileIndex::updateMain(PathRef Path, ParsedAST &AST) {
470
  auto Contents = indexMainDecls(AST);
471
  MainFileSymbols.update(
472
      URI::create(Path).toString(),
473
      std::make_unique<SymbolSlab>(std::move(std::get<0>(Contents))),
474
      std::make_unique<RefSlab>(std::move(std::get<1>(Contents))),
475
      std::make_unique<RelationSlab>(std::move(std::get<2>(Contents))),
476
      /*CountReferences=*/true);
477
  size_t IndexVersion = 0;
478
  auto NewIndex = MainFileSymbols.buildIndex(
479
      IndexType::Light, DuplicateHandling::Merge, &IndexVersion);
480
  {
481
    std::lock_guard<std::mutex> Lock(UpdateIndexMu);
482
    if (IndexVersion <= MainIndexVersion) {
483
      // We lost the race, some other thread built a later version.
484
      return;
485
    }
486
    MainIndexVersion = IndexVersion;
487
    MainFileIndex.reset(std::move(NewIndex));
488
    vlog(
489
        "Build dynamic index for main-file symbols with estimated memory usage "
490
        "of {0} bytes",
491
        MainFileIndex.estimateMemoryUsage());
492
  }
493
}
494

495
void FileIndex::profile(MemoryTree &MT) const {
496
  PreambleSymbols.profile(MT.child("preamble").child("slabs"));
497
  MT.child("preamble")
498
      .child("index")
499
      .addUsage(PreambleIndex.estimateMemoryUsage());
500
  MainFileSymbols.profile(MT.child("main_file").child("slabs"));
501
  MT.child("main_file")
502
      .child("index")
503
      .addUsage(MainFileIndex.estimateMemoryUsage());
504
}
505
} // namespace clangd
506
} // namespace clang
507