Debian Codegraph @

llvm-project/clang-tools-extra/clangd/index/StdLib.cpp

raw
1 //===-- StdLib.cpp ----------------------------------------------*- 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 #include "StdLib.h"
9 #include <fstream>
10 #include <memory>
11 #include <optional>
12 #include <string>
13 #include <vector>
14
15 #include "Compiler.h"
16 #include "Config.h"
17 #include "SymbolCollector.h"
18 #include "index/IndexAction.h"
19 #include "support/Logger.h"
20 #include "support/ThreadsafeFS.h"
21 #include "support/Trace.h"
22 #include "clang/Basic/LangOptions.h"
23 #include "clang/Frontend/CompilerInvocation.h"
24 #include "clang/Lex/PreprocessorOptions.h"
25 #include "llvm/ADT/IntrusiveRefCntPtr.h"
26 #include "llvm/ADT/StringRef.h"
27 #include "llvm/Support/MemoryBuffer.h"
28 #include "llvm/Support/Path.h"
29
30 namespace clang {
31 namespace clangd {
32 namespace {
33
34 enum Lang { C, CXX };
35
36 Lang langFromOpts(const LangOptions &LO) { return LO.CPlusPlus ? CXX : C; }
37 llvm::StringLiteral mandatoryHeader(Lang L) {
38 switch (L) {
39 case C:
40 return "stdio.h";
41 case CXX:
42 return "vector";
43 }
44 llvm_unreachable("unhandled Lang");
45 }
46
47 LangStandard::Kind standardFromOpts(const LangOptions &LO) {
48 if (LO.CPlusPlus) {
49 if (LO.CPlusPlus2b)
50 return LangStandard::lang_cxx2b;
51 if (LO.CPlusPlus20)
52 return LangStandard::lang_cxx20;
53 if (LO.CPlusPlus17)
54 return LangStandard::lang_cxx17;
55 if (LO.CPlusPlus14)
56 return LangStandard::lang_cxx14;
57 if (LO.CPlusPlus11)
58 return LangStandard::lang_cxx11;
59 return LangStandard::lang_cxx98;
60 }
61 if (LO.C2x)
62 return LangStandard::lang_c2x;
63 // C17 has no new features, so treat {C11,C17} as C17.
64 if (LO.C11)
65 return LangStandard::lang_c17;
66 return LangStandard::lang_c99;
67 }
68
69 std::string buildUmbrella(llvm::StringLiteral Mandatory,
70 std::vector<llvm::StringLiteral> Headers) {
71 std::string Result;
72 llvm::raw_string_ostream OS(Result);
73
74 // We __has_include guard all our #includes to avoid errors when using older
75 // stdlib version that don't have headers for the newest language standards.
76 // But make sure we get *some* error if things are totally broken.
77 OS << llvm::formatv(
78 "#if !__has_include(<{0}>)\n"
79 "#error Mandatory header <{0}> not found in standard library!\n"
80 "#endif\n",
81 Mandatory);
82
83 llvm::sort(Headers);
84 auto Last = std::unique(Headers.begin(), Headers.end());
85 for (auto Header = Headers.begin(); Header != Last; ++Header) {
86 OS << llvm::formatv("#if __has_include({0})\n"
87 "#include {0}\n"
88 "#endif\n",
89 *Header);
90 }
91 OS.flush();
92 return Result;
93 }
94
95 } // namespace
96
97 llvm::StringRef getStdlibUmbrellaHeader(const LangOptions &LO) {
98 // The umbrella header is the same for all versions of each language.
99 // Headers that are unsupported in old lang versions are usually guarded by
100 // #if. Some headers may be not present in old stdlib versions, the umbrella
101 // header guards with __has_include for this purpose.
102 Lang L = langFromOpts(LO);
103 switch (L) {
104 case CXX:
105 static std::string *UmbrellaCXX =
106 new std::string(buildUmbrella(mandatoryHeader(L), {
107 #define SYMBOL(Name, NameSpace, Header) #Header,
108 #include "clang/Tooling/Inclusions/StdSymbolMap.inc"
109 #undef SYMBOL
110 }));
111 return *UmbrellaCXX;
112 case C:
113 static std::string *UmbrellaC =
114 new std::string(buildUmbrella(mandatoryHeader(L), {
115 #define SYMBOL(Name, NameSpace, Header) #Header,
116 #include "clang/Tooling/Inclusions/CSymbolMap.inc"
117 #undef SYMBOL
118 }));
119 return *UmbrellaC;
120 }
121 llvm_unreachable("invalid Lang in langFromOpts");
122 }
123
124 namespace {
125
126 // Including the standard library leaks unwanted transitively included symbols.
127 //
128 // We want to drop these, they're a bit tricky to identify:
129 // - we don't want to limit to symbols on our list, as our list has only
130 // top-level symbols (and there may be legitimate stdlib extensions).
131 // - we can't limit to only symbols defined in known stdlib headers, as stdlib
132 // internal structure is murky
133 // - we can't strictly require symbols to come from a particular path, e.g.
134 // libstdc++ is mostly under /usr/include/c++/10/...
135 // but std::ctype_base is under /usr/include/<platform>/c++/10/...
136 // We require the symbol to come from a header that is *either* from
137 // the standard library path (as identified by the location of <vector>), or
138 // another header that defines a symbol from our stdlib list.
139 SymbolSlab filter(SymbolSlab Slab, const StdLibLocation &Loc) {
140 SymbolSlab::Builder Result;
141
142 static auto &StandardHeaders = *[] {
143 auto *Set = new llvm::DenseSet<llvm::StringRef>();
144 for (llvm::StringRef Header : {
145 #define SYMBOL(Name, NameSpace, Header) #Header,
146 #include "clang/Tooling/Inclusions/CSymbolMap.inc"
147 #include "clang/Tooling/Inclusions/StdSymbolMap.inc"
148 #undef SYMBOL
149 })
150 Set->insert(Header);
151 return Set;
152 }();
153
154 // Form prefixes like file:///usr/include/c++/10/
155 // These can be trivially prefix-compared with URIs in the indexed symbols.
156 llvm::SmallVector<std::string> StdLibURIPrefixes;
157 for (const auto &Path : Loc.Paths) {
158 StdLibURIPrefixes.push_back(URI::create(Path).toString());
159 if (StdLibURIPrefixes.back().back() != '/')
160 StdLibURIPrefixes.back().push_back('/');
161 }
162 // For each header URI, is it *either* prefixed by StdLibURIPrefixes *or*
163 // owner of a symbol whose insertable header is in StandardHeaders?
164 // Pointer key because strings in a SymbolSlab are interned.
165 llvm::DenseMap<const char *, bool> GoodHeader;
166 for (const Symbol &S : Slab) {
167 if (!S.IncludeHeaders.empty() &&
168 StandardHeaders.contains(S.IncludeHeaders.front().IncludeHeader)) {
169 GoodHeader[S.CanonicalDeclaration.FileURI] = true;
170 GoodHeader[S.Definition.FileURI] = true;
171 continue;
172 }
173 for (const char *URI :
174 {S.CanonicalDeclaration.FileURI, S.Definition.FileURI}) {
175 auto R = GoodHeader.try_emplace(URI, false);
176 if (R.second) {
177 R.first->second = llvm::any_of(
178 StdLibURIPrefixes,
179 [&, URIStr(llvm::StringRef(URI))](const std::string &Prefix) {
180 return URIStr.startswith(Prefix);
181 });
182 }
183 }
184 }
185 #ifndef NDEBUG
186 for (const auto &Good : GoodHeader)
187 if (Good.second && *Good.first)
188 dlog("Stdlib header: {0}", Good.first);
189 #endif
190 // Empty URIs aren't considered good. (Definition can be blank).
191 auto IsGoodHeader = [&](const char *C) { return *C && GoodHeader.lookup(C); };
192
193 for (const Symbol &S : Slab) {
194 if (!(IsGoodHeader(S.CanonicalDeclaration.FileURI) ||
195 IsGoodHeader(S.Definition.FileURI))) {
196 dlog("Ignoring wrong-header symbol {0}{1} in {2}", S.Scope, S.Name,
197 S.CanonicalDeclaration.FileURI);
198 continue;
199 }
200 Result.insert(S);
201 }
202
203 return std::move(Result).build();
204 }
205
206 } // namespace
207
208 SymbolSlab indexStandardLibrary(llvm::StringRef HeaderSources,
209 std::unique_ptr<CompilerInvocation> CI,
210 const StdLibLocation &Loc,
211 const ThreadsafeFS &TFS) {
212 if (CI->getFrontendOpts().Inputs.size() != 1 ||
213 !CI->getPreprocessorOpts().ImplicitPCHInclude.empty()) {
214 elog("Indexing standard library failed: bad CompilerInvocation");
215 assert(false && "indexing stdlib with a dubious CompilerInvocation!");
216 return SymbolSlab();
217 }
218 const FrontendInputFile &Input = CI->getFrontendOpts().Inputs.front();
219 trace::Span Tracer("StandardLibraryIndex");
220 LangStandard::Kind LangStd = standardFromOpts(*CI->getLangOpts());
221 log("Indexing {0} standard library in the context of {1}",
222 LangStandard::getLangStandardForKind(LangStd).getName(), Input.getFile());
223
224 SymbolSlab Symbols;
225 IgnoreDiagnostics IgnoreDiags;
226 // CompilerInvocation is taken from elsewhere, and may map a dirty buffer.
227 CI->getPreprocessorOpts().clearRemappedFiles();
228 auto Clang = prepareCompilerInstance(
229 std::move(CI), /*Preamble=*/nullptr,
230 llvm::MemoryBuffer::getMemBuffer(HeaderSources, Input.getFile()),
231 TFS.view(/*CWD=*/std::nullopt), IgnoreDiags);
232 if (!Clang) {
233 elog("Standard Library Index: Couldn't build compiler instance");
234 return Symbols;
235 }
236
237 SymbolCollector::Options IndexOpts;
238 IndexOpts.Origin = SymbolOrigin::StdLib;
239 IndexOpts.CollectMainFileSymbols = false;
240 IndexOpts.CollectMainFileRefs = false;
241 IndexOpts.CollectMacro = true;
242 IndexOpts.StoreAllDocumentation = true;
243 // Sadly we can't use IndexOpts.FileFilter to restrict indexing scope.
244 // Files from outside the StdLibLocation may define true std symbols anyway.
245 // We end up "blessing" such headers, and can only do that by indexing
246 // everything first.
247
248 // Refs, relations, include graph in the stdlib mostly aren't useful.
249 auto Action = createStaticIndexingAction(
250 IndexOpts, [&](SymbolSlab S) { Symbols = std::move(S); }, nullptr,
251 nullptr, nullptr);
252
253 if (!Action->BeginSourceFile(*Clang, Input)) {
254 elog("Standard Library Index: BeginSourceFile() failed");
255 return Symbols;
256 }
257
258 if (llvm::Error Err = Action->Execute()) {
259 elog("Standard Library Index: Execute failed: {0}", std::move(Err));
260 return Symbols;
261 }
262
263 Action->EndSourceFile();
264
265 unsigned SymbolsBeforeFilter = Symbols.size();
266 Symbols = filter(std::move(Symbols), Loc);
267 bool Errors = Clang->hasDiagnostics() &&
268 Clang->getDiagnostics().hasUncompilableErrorOccurred();
269 log("Indexed {0} standard library{3}: {1} symbols, {2} filtered",
270 LangStandard::getLangStandardForKind(LangStd).getName(), Symbols.size(),
271 SymbolsBeforeFilter - Symbols.size(),
272 Errors ? " (incomplete due to errors)" : "");
273 SPAN_ATTACH(Tracer, "symbols", int(Symbols.size()));
274 return Symbols;
275 }
276
277 SymbolSlab indexStandardLibrary(std::unique_ptr<CompilerInvocation> Invocation,
278 const StdLibLocation &Loc,
279 const ThreadsafeFS &TFS) {
280 llvm::StringRef Header = getStdlibUmbrellaHeader(*Invocation->getLangOpts());
281 return indexStandardLibrary(Header, std::move(Invocation), Loc, TFS);
282 }
283
284 bool StdLibSet::isBest(const LangOptions &LO) const {
285 return standardFromOpts(LO) >=
286 Best[langFromOpts(LO)].load(std::memory_order_acquire);
287 }
288
289 std::optional<StdLibLocation> StdLibSet::add(const LangOptions &LO,
290 const HeaderSearch &HS) {
291 Lang L = langFromOpts(LO);
292 int OldVersion = Best[L].load(std::memory_order_acquire);
293 int NewVersion = standardFromOpts(LO);
294 dlog("Index stdlib? {0}",
295 LangStandard::getLangStandardForKind(standardFromOpts(LO)).getName());
296
297 if (!Config::current().Index.StandardLibrary) {
298 dlog("No: disabled in config");
299 return std::nullopt;
300 }
301
302 if (NewVersion <= OldVersion) {
303 dlog("No: have {0}, {1}>={2}",
304 LangStandard::getLangStandardForKind(
305 static_cast<LangStandard::Kind>(NewVersion))
306 .getName(),
307 OldVersion, NewVersion);
308 return std::nullopt;
309 }
310
311 // We'd like to index a standard library here if there is one.
312 // Check for the existence of <vector> on the search path.
313 // We could cache this, but we only get here repeatedly when there's no
314 // stdlib, and even then only once per preamble build.
315 llvm::StringLiteral ProbeHeader = mandatoryHeader(L);
316 llvm::SmallString<256> Path; // Scratch space.
317 llvm::SmallVector<std::string> SearchPaths;
318 auto RecordHeaderPath = [&](llvm::StringRef HeaderPath) {
319 llvm::StringRef DirPath = llvm::sys::path::parent_path(HeaderPath);
320 if (!HS.getFileMgr().getVirtualFileSystem().getRealPath(DirPath, Path))
321 SearchPaths.emplace_back(Path);
322 };
323 for (const auto &DL :
324 llvm::make_range(HS.search_dir_begin(), HS.search_dir_end())) {
325 switch (DL.getLookupType()) {
326 case DirectoryLookup::LT_NormalDir: {
327 Path = DL.getDir()->getName();
328 llvm::sys::path::append(Path, ProbeHeader);
329 llvm::vfs::Status Stat;
330 if (!HS.getFileMgr().getNoncachedStatValue(Path, Stat) &&
331 Stat.isRegularFile())
332 RecordHeaderPath(Path);
333 break;
334 }
335 case DirectoryLookup::LT_Framework:
336 // stdlib can't be a framework (framework includes must have a slash)
337 continue;
338 case DirectoryLookup::LT_HeaderMap:
339 llvm::StringRef Target =
340 DL.getHeaderMap()->lookupFilename(ProbeHeader, Path);
341 if (!Target.empty())
342 RecordHeaderPath(Target);
343 break;
344 }
345 }
346 if (SearchPaths.empty())
347 return std::nullopt;
348
349 dlog("Found standard library in {0}", llvm::join(SearchPaths, ", "));
350
351 while (!Best[L].compare_exchange_weak(OldVersion, NewVersion,
352 std::memory_order_acq_rel))
353 if (OldVersion >= NewVersion) {
354 dlog("No: lost the race");
355 return std::nullopt; // Another thread won the race while we were
356 // checking.
357 }
358
359 dlog("Yes, index stdlib!");
360 return StdLibLocation{std::move(SearchPaths)};
361 }
362
363 } // namespace clangd
364 } // namespace clang