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 "ClangdUnit.h"
11 #include "Logger.h"
12 #include "SymbolCollector.h"
13 #include "index/CanonicalIncludes.h"
14 #include "index/Index.h"
15 #include "index/MemIndex.h"
16 #include "index/Merge.h"
17 #include "index/SymbolOrigin.h"
18 #include "index/dex/Dex.h"
19 #include "clang/Index/IndexingAction.h"
20 #include "clang/Lex/MacroInfo.h"
21 #include "clang/Lex/Preprocessor.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/DenseSet.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/ADT/StringRef.h"
26 #include <memory>
27 
28 namespace clang {
29 namespace clangd {
30 
31 static std::pair<SymbolSlab, RefSlab>
32 indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
33              llvm::ArrayRef<Decl *> DeclsToIndex,
34              const CanonicalIncludes &Includes, bool IsIndexMainAST) {
35   SymbolCollector::Options CollectorOpts;
36   CollectorOpts.CollectIncludePath = true;
37   CollectorOpts.Includes = &Includes;
38   CollectorOpts.CountReferences = false;
39   CollectorOpts.Origin = SymbolOrigin::Dynamic;
40 
41   index::IndexingOptions IndexOpts;
42   // We only need declarations, because we don't count references.
43   IndexOpts.SystemSymbolFilter =
44       index::IndexingOptions::SystemSymbolFilterKind::DeclarationsOnly;
45   IndexOpts.IndexFunctionLocals = false;
46   if (IsIndexMainAST) {
47     // We only collect refs when indexing main AST.
48     CollectorOpts.RefFilter = RefKind::All;
49     // Comments for main file can always be obtained from sema, do not store
50     // them in the index.
51     CollectorOpts.StoreAllDocumentation = false;
52   } else {
53     IndexOpts.IndexMacrosInPreprocessor = true;
54     CollectorOpts.CollectMacro = true;
55     CollectorOpts.StoreAllDocumentation = true;
56   }
57 
58   SymbolCollector Collector(std::move(CollectorOpts));
59   Collector.setPreprocessor(PP);
60   index::indexTopLevelDecls(AST, *PP, DeclsToIndex, Collector, IndexOpts);
61 
62   const auto &SM = AST.getSourceManager();
63   const auto *MainFileEntry = SM.getFileEntryForID(SM.getMainFileID());
64   std::string FileName = MainFileEntry ? MainFileEntry->getName() : "";
65 
66   auto Syms = Collector.takeSymbols();
67   auto Refs = Collector.takeRefs();
68   vlog("index AST for {0} (main={1}): \n"
69        "  symbol slab: {2} symbols, {3} bytes\n"
70        "  ref slab: {4} symbols, {5} refs, {6} bytes",
71        FileName, IsIndexMainAST, Syms.size(), Syms.bytes(), Refs.size(),
72        Refs.numRefs(), Refs.bytes());
73   return {std::move(Syms), std::move(Refs)};
74 }
75 
76 std::pair<SymbolSlab, RefSlab> indexMainDecls(ParsedAST &AST) {
77   return indexSymbols(AST.getASTContext(), AST.getPreprocessorPtr(),
78                       AST.getLocalTopLevelDecls(), AST.getCanonicalIncludes(),
79                       /*IsIndexMainAST=*/true);
80 }
81 
82 SymbolSlab indexHeaderSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
83                               const CanonicalIncludes &Includes) {
84   std::vector<Decl *> DeclsToIndex(
85       AST.getTranslationUnitDecl()->decls().begin(),
86       AST.getTranslationUnitDecl()->decls().end());
87   return indexSymbols(AST, std::move(PP), DeclsToIndex, Includes,
88                       /*IsIndexMainAST=*/false)
89       .first;
90 }
91 
92 void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Symbols,
93                          std::unique_ptr<RefSlab> Refs) {
94   std::lock_guard<std::mutex> Lock(Mutex);
95   if (!Symbols)
96     FileToSymbols.erase(Path);
97   else
98     FileToSymbols[Path] = std::move(Symbols);
99   if (!Refs)
100     FileToRefs.erase(Path);
101   else
102     FileToRefs[Path] = std::move(Refs);
103 }
104 
105 std::unique_ptr<SymbolIndex>
106 FileSymbols::buildIndex(IndexType Type, DuplicateHandling DuplicateHandle) {
107   std::vector<std::shared_ptr<SymbolSlab>> SymbolSlabs;
108   std::vector<std::shared_ptr<RefSlab>> RefSlabs;
109   {
110     std::lock_guard<std::mutex> Lock(Mutex);
111     for (const auto &FileAndSymbols : FileToSymbols)
112       SymbolSlabs.push_back(FileAndSymbols.second);
113     for (const auto &FileAndRefs : FileToRefs)
114       RefSlabs.push_back(FileAndRefs.second);
115   }
116   std::vector<const Symbol *> AllSymbols;
117   std::vector<Symbol> SymsStorage;
118   switch (DuplicateHandle) {
119   case DuplicateHandling::Merge: {
120     llvm::DenseMap<SymbolID, Symbol> Merged;
121     for (const auto &Slab : SymbolSlabs) {
122       for (const auto &Sym : *Slab) {
123         auto I = Merged.try_emplace(Sym.ID, Sym);
124         if (!I.second)
125           I.first->second = mergeSymbol(I.first->second, Sym);
126       }
127     }
128     SymsStorage.reserve(Merged.size());
129     for (auto &Sym : Merged) {
130       SymsStorage.push_back(std::move(Sym.second));
131       AllSymbols.push_back(&SymsStorage.back());
132     }
133     // FIXME: aggregate symbol reference count based on references.
134     break;
135   }
136   case DuplicateHandling::PickOne: {
137     llvm::DenseSet<SymbolID> AddedSymbols;
138     for (const auto &Slab : SymbolSlabs)
139       for (const auto &Sym : *Slab)
140         if (AddedSymbols.insert(Sym.ID).second)
141           AllSymbols.push_back(&Sym);
142     break;
143   }
144   }
145 
146   std::vector<Ref> RefsStorage; // Contiguous ranges for each SymbolID.
147   llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> AllRefs;
148   {
149     llvm::DenseMap<SymbolID, llvm::SmallVector<Ref, 4>> MergedRefs;
150     size_t Count = 0;
151     for (const auto &RefSlab : RefSlabs)
152       for (const auto &Sym : *RefSlab) {
153         MergedRefs[Sym.first].append(Sym.second.begin(), Sym.second.end());
154         Count += Sym.second.size();
155       }
156     RefsStorage.reserve(Count);
157     AllRefs.reserve(MergedRefs.size());
158     for (auto &Sym : MergedRefs) {
159       auto &SymRefs = Sym.second;
160       // Sorting isn't required, but yields more stable results over rebuilds.
161       llvm::sort(SymRefs);
162       llvm::copy(SymRefs, back_inserter(RefsStorage));
163       AllRefs.try_emplace(
164           Sym.first,
165           llvm::ArrayRef<Ref>(&RefsStorage[RefsStorage.size() - SymRefs.size()],
166                               SymRefs.size()));
167     }
168   }
169 
170   size_t StorageSize =
171       RefsStorage.size() * sizeof(Ref) + SymsStorage.size() * sizeof(Symbol);
172   for (const auto &Slab : SymbolSlabs)
173     StorageSize += Slab->bytes();
174   for (const auto &RefSlab : RefSlabs)
175     StorageSize += RefSlab->bytes();
176 
177   // Index must keep the slabs and contiguous ranges alive.
178   switch (Type) {
179   case IndexType::Light:
180     return llvm::make_unique<MemIndex>(
181         llvm::make_pointee_range(AllSymbols), std::move(AllRefs),
182         std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
183                         std::move(RefsStorage), std::move(SymsStorage)),
184         StorageSize);
185   case IndexType::Heavy:
186     return llvm::make_unique<dex::Dex>(
187         llvm::make_pointee_range(AllSymbols), std::move(AllRefs),
188         std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
189                         std::move(RefsStorage), std::move(SymsStorage)),
190         StorageSize);
191   }
192   llvm_unreachable("Unknown clangd::IndexType");
193 }
194 
195 FileIndex::FileIndex(bool UseDex)
196     : MergedIndex(&MainFileIndex, &PreambleIndex), UseDex(UseDex),
197       PreambleIndex(llvm::make_unique<MemIndex>()),
198       MainFileIndex(llvm::make_unique<MemIndex>()) {}
199 
200 void FileIndex::updatePreamble(PathRef Path, ASTContext &AST,
201                                std::shared_ptr<Preprocessor> PP,
202                                const CanonicalIncludes &Includes) {
203   auto Symbols = indexHeaderSymbols(AST, std::move(PP), Includes);
204   PreambleSymbols.update(Path,
205                          llvm::make_unique<SymbolSlab>(std::move(Symbols)),
206                          llvm::make_unique<RefSlab>());
207   PreambleIndex.reset(
208       PreambleSymbols.buildIndex(UseDex ? IndexType::Heavy : IndexType::Light,
209                                  DuplicateHandling::PickOne));
210 }
211 
212 void FileIndex::updateMain(PathRef Path, ParsedAST &AST) {
213   auto Contents = indexMainDecls(AST);
214   MainFileSymbols.update(
215       Path, llvm::make_unique<SymbolSlab>(std::move(Contents.first)),
216       llvm::make_unique<RefSlab>(std::move(Contents.second)));
217   MainFileIndex.reset(
218       MainFileSymbols.buildIndex(IndexType::Light, DuplicateHandling::PickOne));
219 }
220 
221 } // namespace clangd
222 } // namespace clang
223