1 //===--- CrossTranslationUnit.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 //
9 //  This file implements the CrossTranslationUnit interface.
10 //
11 //===----------------------------------------------------------------------===//
12 #include "clang/CrossTU/CrossTranslationUnit.h"
13 #include "clang/AST/ASTImporter.h"
14 #include "clang/AST/Decl.h"
15 #include "clang/AST/ParentMapContext.h"
16 #include "clang/Basic/TargetInfo.h"
17 #include "clang/CrossTU/CrossTUDiagnostic.h"
18 #include "clang/Frontend/ASTUnit.h"
19 #include "clang/Frontend/CompilerInstance.h"
20 #include "clang/Frontend/TextDiagnosticPrinter.h"
21 #include "clang/Index/USRGeneration.h"
22 #include "llvm/ADT/Optional.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/ADT/Triple.h"
25 #include "llvm/Option/ArgList.h"
26 #include "llvm/Support/ErrorHandling.h"
27 #include "llvm/Support/ManagedStatic.h"
28 #include "llvm/Support/Path.h"
29 #include "llvm/Support/YAMLParser.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include <algorithm>
32 #include <fstream>
33 #include <sstream>
34 #include <tuple>
35 
36 namespace clang {
37 namespace cross_tu {
38 
39 namespace {
40 
41 #define DEBUG_TYPE "CrossTranslationUnit"
42 STATISTIC(NumGetCTUCalled, "The # of getCTUDefinition function called");
43 STATISTIC(
44     NumNotInOtherTU,
45     "The # of getCTUDefinition called but the function is not in any other TU");
46 STATISTIC(NumGetCTUSuccess,
47           "The # of getCTUDefinition successfully returned the "
48           "requested function's body");
49 STATISTIC(NumUnsupportedNodeFound, "The # of imports when the ASTImporter "
50                                    "encountered an unsupported AST Node");
51 STATISTIC(NumNameConflicts, "The # of imports when the ASTImporter "
52                             "encountered an ODR error");
53 STATISTIC(NumTripleMismatch, "The # of triple mismatches");
54 STATISTIC(NumLangMismatch, "The # of language mismatches");
55 STATISTIC(NumLangDialectMismatch, "The # of language dialect mismatches");
56 STATISTIC(NumASTLoadThresholdReached,
57           "The # of ASTs not loaded because of threshold");
58 
59 // Same as Triple's equality operator, but we check a field only if that is
60 // known in both instances.
61 bool hasEqualKnownFields(const llvm::Triple &Lhs, const llvm::Triple &Rhs) {
62   using llvm::Triple;
63   if (Lhs.getArch() != Triple::UnknownArch &&
64       Rhs.getArch() != Triple::UnknownArch && Lhs.getArch() != Rhs.getArch())
65     return false;
66   if (Lhs.getSubArch() != Triple::NoSubArch &&
67       Rhs.getSubArch() != Triple::NoSubArch &&
68       Lhs.getSubArch() != Rhs.getSubArch())
69     return false;
70   if (Lhs.getVendor() != Triple::UnknownVendor &&
71       Rhs.getVendor() != Triple::UnknownVendor &&
72       Lhs.getVendor() != Rhs.getVendor())
73     return false;
74   if (!Lhs.isOSUnknown() && !Rhs.isOSUnknown() &&
75       Lhs.getOS() != Rhs.getOS())
76     return false;
77   if (Lhs.getEnvironment() != Triple::UnknownEnvironment &&
78       Rhs.getEnvironment() != Triple::UnknownEnvironment &&
79       Lhs.getEnvironment() != Rhs.getEnvironment())
80     return false;
81   if (Lhs.getObjectFormat() != Triple::UnknownObjectFormat &&
82       Rhs.getObjectFormat() != Triple::UnknownObjectFormat &&
83       Lhs.getObjectFormat() != Rhs.getObjectFormat())
84     return false;
85   return true;
86 }
87 
88 // FIXME: This class is will be removed after the transition to llvm::Error.
89 class IndexErrorCategory : public std::error_category {
90 public:
91   const char *name() const noexcept override { return "clang.index"; }
92 
93   std::string message(int Condition) const override {
94     switch (static_cast<index_error_code>(Condition)) {
95     case index_error_code::unspecified:
96       return "An unknown error has occurred.";
97     case index_error_code::missing_index_file:
98       return "The index file is missing.";
99     case index_error_code::invalid_index_format:
100       return "Invalid index file format.";
101     case index_error_code::multiple_definitions:
102       return "Multiple definitions in the index file.";
103     case index_error_code::missing_definition:
104       return "Missing definition from the index file.";
105     case index_error_code::failed_import:
106       return "Failed to import the definition.";
107     case index_error_code::failed_to_get_external_ast:
108       return "Failed to load external AST source.";
109     case index_error_code::failed_to_generate_usr:
110       return "Failed to generate USR.";
111     case index_error_code::triple_mismatch:
112       return "Triple mismatch";
113     case index_error_code::lang_mismatch:
114       return "Language mismatch";
115     case index_error_code::lang_dialect_mismatch:
116       return "Language dialect mismatch";
117     case index_error_code::load_threshold_reached:
118       return "Load threshold reached";
119     case index_error_code::invocation_list_ambiguous:
120       return "Invocation list file contains multiple references to the same "
121              "source file.";
122     case index_error_code::invocation_list_file_not_found:
123       return "Invocation list file is not found.";
124     case index_error_code::invocation_list_empty:
125       return "Invocation list file is empty.";
126     case index_error_code::invocation_list_wrong_format:
127       return "Invocation list file is in wrong format.";
128     case index_error_code::invocation_list_lookup_unsuccessful:
129       return "Invocation list file does not contain the requested source file.";
130     }
131     llvm_unreachable("Unrecognized index_error_code.");
132   }
133 };
134 
135 static llvm::ManagedStatic<IndexErrorCategory> Category;
136 } // end anonymous namespace
137 
138 char IndexError::ID;
139 
140 void IndexError::log(raw_ostream &OS) const {
141   OS << Category->message(static_cast<int>(Code)) << '\n';
142 }
143 
144 std::error_code IndexError::convertToErrorCode() const {
145   return std::error_code(static_cast<int>(Code), *Category);
146 }
147 
148 llvm::Expected<llvm::StringMap<std::string>>
149 parseCrossTUIndex(StringRef IndexPath) {
150   std::ifstream ExternalMapFile{std::string(IndexPath)};
151   if (!ExternalMapFile)
152     return llvm::make_error<IndexError>(index_error_code::missing_index_file,
153                                         IndexPath.str());
154 
155   llvm::StringMap<std::string> Result;
156   std::string Line;
157   unsigned LineNo = 1;
158   while (std::getline(ExternalMapFile, Line)) {
159     StringRef LineRef{Line};
160     const size_t Delimiter = LineRef.find(" ");
161     if (Delimiter > 0 && Delimiter != std::string::npos) {
162       StringRef LookupName = LineRef.substr(0, Delimiter);
163 
164       // Store paths with posix-style directory separator.
165       SmallVector<char, 32> FilePath;
166       llvm::Twine{LineRef.substr(Delimiter + 1)}.toVector(FilePath);
167       llvm::sys::path::native(FilePath, llvm::sys::path::Style::posix);
168 
169       bool InsertionOccured;
170       std::tie(std::ignore, InsertionOccured) =
171           Result.try_emplace(LookupName, FilePath.begin(), FilePath.end());
172       if (!InsertionOccured)
173         return llvm::make_error<IndexError>(
174             index_error_code::multiple_definitions, IndexPath.str(), LineNo);
175     } else
176       return llvm::make_error<IndexError>(
177           index_error_code::invalid_index_format, IndexPath.str(), LineNo);
178     ++LineNo;
179   }
180   return Result;
181 }
182 
183 std::string
184 createCrossTUIndexString(const llvm::StringMap<std::string> &Index) {
185   std::ostringstream Result;
186   for (const auto &E : Index)
187     Result << E.getKey().str() << " " << E.getValue() << '\n';
188   return Result.str();
189 }
190 
191 bool containsConst(const VarDecl *VD, const ASTContext &ACtx) {
192   CanQualType CT = ACtx.getCanonicalType(VD->getType());
193   if (!CT.isConstQualified()) {
194     const RecordType *RTy = CT->getAs<RecordType>();
195     if (!RTy || !RTy->hasConstFields())
196       return false;
197   }
198   return true;
199 }
200 
201 static bool hasBodyOrInit(const FunctionDecl *D, const FunctionDecl *&DefD) {
202   return D->hasBody(DefD);
203 }
204 static bool hasBodyOrInit(const VarDecl *D, const VarDecl *&DefD) {
205   return D->getAnyInitializer(DefD);
206 }
207 template <typename T> static bool hasBodyOrInit(const T *D) {
208   const T *Unused;
209   return hasBodyOrInit(D, Unused);
210 }
211 
212 CrossTranslationUnitContext::CrossTranslationUnitContext(CompilerInstance &CI)
213     : Context(CI.getASTContext()), ASTStorage(CI) {}
214 
215 CrossTranslationUnitContext::~CrossTranslationUnitContext() {}
216 
217 llvm::Optional<std::string>
218 CrossTranslationUnitContext::getLookupName(const NamedDecl *ND) {
219   SmallString<128> DeclUSR;
220   bool Ret = index::generateUSRForDecl(ND, DeclUSR);
221   if (Ret)
222     return {};
223   return std::string(DeclUSR.str());
224 }
225 
226 /// Recursively visits the decls of a DeclContext, and returns one with the
227 /// given USR.
228 template <typename T>
229 const T *
230 CrossTranslationUnitContext::findDefInDeclContext(const DeclContext *DC,
231                                                   StringRef LookupName) {
232   assert(DC && "Declaration Context must not be null");
233   for (const Decl *D : DC->decls()) {
234     const auto *SubDC = dyn_cast<DeclContext>(D);
235     if (SubDC)
236       if (const auto *ND = findDefInDeclContext<T>(SubDC, LookupName))
237         return ND;
238 
239     const auto *ND = dyn_cast<T>(D);
240     const T *ResultDecl;
241     if (!ND || !hasBodyOrInit(ND, ResultDecl))
242       continue;
243     llvm::Optional<std::string> ResultLookupName = getLookupName(ResultDecl);
244     if (!ResultLookupName || *ResultLookupName != LookupName)
245       continue;
246     return ResultDecl;
247   }
248   return nullptr;
249 }
250 
251 template <typename T>
252 llvm::Expected<const T *> CrossTranslationUnitContext::getCrossTUDefinitionImpl(
253     const T *D, StringRef CrossTUDir, StringRef IndexName,
254     bool DisplayCTUProgress) {
255   assert(D && "D is missing, bad call to this function!");
256   assert(!hasBodyOrInit(D) &&
257          "D has a body or init in current translation unit!");
258   ++NumGetCTUCalled;
259   const llvm::Optional<std::string> LookupName = getLookupName(D);
260   if (!LookupName)
261     return llvm::make_error<IndexError>(
262         index_error_code::failed_to_generate_usr);
263   llvm::Expected<ASTUnit *> ASTUnitOrError =
264       loadExternalAST(*LookupName, CrossTUDir, IndexName, DisplayCTUProgress);
265   if (!ASTUnitOrError)
266     return ASTUnitOrError.takeError();
267   ASTUnit *Unit = *ASTUnitOrError;
268   assert(&Unit->getFileManager() ==
269          &Unit->getASTContext().getSourceManager().getFileManager());
270 
271   const llvm::Triple &TripleTo = Context.getTargetInfo().getTriple();
272   const llvm::Triple &TripleFrom =
273       Unit->getASTContext().getTargetInfo().getTriple();
274   // The imported AST had been generated for a different target.
275   // Some parts of the triple in the loaded ASTContext can be unknown while the
276   // very same parts in the target ASTContext are known. Thus we check for the
277   // known parts only.
278   if (!hasEqualKnownFields(TripleTo, TripleFrom)) {
279     // TODO: Pass the SourceLocation of the CallExpression for more precise
280     // diagnostics.
281     ++NumTripleMismatch;
282     return llvm::make_error<IndexError>(index_error_code::triple_mismatch,
283                                         std::string(Unit->getMainFileName()),
284                                         TripleTo.str(), TripleFrom.str());
285   }
286 
287   const auto &LangTo = Context.getLangOpts();
288   const auto &LangFrom = Unit->getASTContext().getLangOpts();
289 
290   // FIXME: Currenty we do not support CTU across C++ and C and across
291   // different dialects of C++.
292   if (LangTo.CPlusPlus != LangFrom.CPlusPlus) {
293     ++NumLangMismatch;
294     return llvm::make_error<IndexError>(index_error_code::lang_mismatch);
295   }
296 
297   // If CPP dialects are different then return with error.
298   //
299   // Consider this STL code:
300   //   template<typename _Alloc>
301   //     struct __alloc_traits
302   //   #if __cplusplus >= 201103L
303   //     : std::allocator_traits<_Alloc>
304   //   #endif
305   //     { // ...
306   //     };
307   // This class template would create ODR errors during merging the two units,
308   // since in one translation unit the class template has a base class, however
309   // in the other unit it has none.
310   if (LangTo.CPlusPlus11 != LangFrom.CPlusPlus11 ||
311       LangTo.CPlusPlus14 != LangFrom.CPlusPlus14 ||
312       LangTo.CPlusPlus17 != LangFrom.CPlusPlus17 ||
313       LangTo.CPlusPlus20 != LangFrom.CPlusPlus20) {
314     ++NumLangDialectMismatch;
315     return llvm::make_error<IndexError>(
316         index_error_code::lang_dialect_mismatch);
317   }
318 
319   TranslationUnitDecl *TU = Unit->getASTContext().getTranslationUnitDecl();
320   if (const T *ResultDecl = findDefInDeclContext<T>(TU, *LookupName))
321     return importDefinition(ResultDecl, Unit);
322   return llvm::make_error<IndexError>(index_error_code::failed_import);
323 }
324 
325 llvm::Expected<const FunctionDecl *>
326 CrossTranslationUnitContext::getCrossTUDefinition(const FunctionDecl *FD,
327                                                   StringRef CrossTUDir,
328                                                   StringRef IndexName,
329                                                   bool DisplayCTUProgress) {
330   return getCrossTUDefinitionImpl(FD, CrossTUDir, IndexName,
331                                   DisplayCTUProgress);
332 }
333 
334 llvm::Expected<const VarDecl *>
335 CrossTranslationUnitContext::getCrossTUDefinition(const VarDecl *VD,
336                                                   StringRef CrossTUDir,
337                                                   StringRef IndexName,
338                                                   bool DisplayCTUProgress) {
339   return getCrossTUDefinitionImpl(VD, CrossTUDir, IndexName,
340                                   DisplayCTUProgress);
341 }
342 
343 void CrossTranslationUnitContext::emitCrossTUDiagnostics(const IndexError &IE) {
344   switch (IE.getCode()) {
345   case index_error_code::missing_index_file:
346     Context.getDiagnostics().Report(diag::err_ctu_error_opening)
347         << IE.getFileName();
348     break;
349   case index_error_code::invalid_index_format:
350     Context.getDiagnostics().Report(diag::err_extdefmap_parsing)
351         << IE.getFileName() << IE.getLineNum();
352     break;
353   case index_error_code::multiple_definitions:
354     Context.getDiagnostics().Report(diag::err_multiple_def_index)
355         << IE.getLineNum();
356     break;
357   case index_error_code::triple_mismatch:
358     Context.getDiagnostics().Report(diag::warn_ctu_incompat_triple)
359         << IE.getFileName() << IE.getTripleToName() << IE.getTripleFromName();
360     break;
361   default:
362     break;
363   }
364 }
365 
366 CrossTranslationUnitContext::ASTUnitStorage::ASTUnitStorage(
367     CompilerInstance &CI)
368     : Loader(CI, CI.getAnalyzerOpts()->CTUDir,
369              CI.getAnalyzerOpts()->CTUInvocationList),
370       LoadGuard(CI.getASTContext().getLangOpts().CPlusPlus
371                     ? CI.getAnalyzerOpts()->CTUImportCppThreshold
372                     : CI.getAnalyzerOpts()->CTUImportThreshold) {}
373 
374 llvm::Expected<ASTUnit *>
375 CrossTranslationUnitContext::ASTUnitStorage::getASTUnitForFile(
376     StringRef FileName, bool DisplayCTUProgress) {
377   // Try the cache first.
378   auto ASTCacheEntry = FileASTUnitMap.find(FileName);
379   if (ASTCacheEntry == FileASTUnitMap.end()) {
380 
381     // Do not load if the limit is reached.
382     if (!LoadGuard) {
383       ++NumASTLoadThresholdReached;
384       return llvm::make_error<IndexError>(
385           index_error_code::load_threshold_reached);
386     }
387 
388     auto LoadAttempt = Loader.load(FileName);
389 
390     if (!LoadAttempt)
391       return LoadAttempt.takeError();
392 
393     std::unique_ptr<ASTUnit> LoadedUnit = std::move(LoadAttempt.get());
394 
395     // Need the raw pointer and the unique_ptr as well.
396     ASTUnit *Unit = LoadedUnit.get();
397 
398     // Update the cache.
399     FileASTUnitMap[FileName] = std::move(LoadedUnit);
400 
401     LoadGuard.indicateLoadSuccess();
402 
403     if (DisplayCTUProgress)
404       llvm::errs() << "CTU loaded AST file: " << FileName << "\n";
405 
406     return Unit;
407 
408   } else {
409     // Found in the cache.
410     return ASTCacheEntry->second.get();
411   }
412 }
413 
414 llvm::Expected<ASTUnit *>
415 CrossTranslationUnitContext::ASTUnitStorage::getASTUnitForFunction(
416     StringRef FunctionName, StringRef CrossTUDir, StringRef IndexName,
417     bool DisplayCTUProgress) {
418   // Try the cache first.
419   auto ASTCacheEntry = NameASTUnitMap.find(FunctionName);
420   if (ASTCacheEntry == NameASTUnitMap.end()) {
421     // Load the ASTUnit from the pre-dumped AST file specified by ASTFileName.
422 
423     // Ensure that the Index is loaded, as we need to search in it.
424     if (llvm::Error IndexLoadError =
425             ensureCTUIndexLoaded(CrossTUDir, IndexName))
426       return std::move(IndexLoadError);
427 
428     // Check if there is and entry in the index for the function.
429     if (!NameFileMap.count(FunctionName)) {
430       ++NumNotInOtherTU;
431       return llvm::make_error<IndexError>(index_error_code::missing_definition);
432     }
433 
434     // Search in the index for the filename where the definition of FuncitonName
435     // resides.
436     if (llvm::Expected<ASTUnit *> FoundForFile =
437             getASTUnitForFile(NameFileMap[FunctionName], DisplayCTUProgress)) {
438 
439       // Update the cache.
440       NameASTUnitMap[FunctionName] = *FoundForFile;
441       return *FoundForFile;
442 
443     } else {
444       return FoundForFile.takeError();
445     }
446   } else {
447     // Found in the cache.
448     return ASTCacheEntry->second;
449   }
450 }
451 
452 llvm::Expected<std::string>
453 CrossTranslationUnitContext::ASTUnitStorage::getFileForFunction(
454     StringRef FunctionName, StringRef CrossTUDir, StringRef IndexName) {
455   if (llvm::Error IndexLoadError = ensureCTUIndexLoaded(CrossTUDir, IndexName))
456     return std::move(IndexLoadError);
457   return NameFileMap[FunctionName];
458 }
459 
460 llvm::Error CrossTranslationUnitContext::ASTUnitStorage::ensureCTUIndexLoaded(
461     StringRef CrossTUDir, StringRef IndexName) {
462   // Dont initialize if the map is filled.
463   if (!NameFileMap.empty())
464     return llvm::Error::success();
465 
466   // Get the absolute path to the index file.
467   SmallString<256> IndexFile = CrossTUDir;
468   if (llvm::sys::path::is_absolute(IndexName))
469     IndexFile = IndexName;
470   else
471     llvm::sys::path::append(IndexFile, IndexName);
472 
473   if (auto IndexMapping = parseCrossTUIndex(IndexFile)) {
474     // Initialize member map.
475     NameFileMap = *IndexMapping;
476     return llvm::Error::success();
477   } else {
478     // Error while parsing CrossTU index file.
479     return IndexMapping.takeError();
480   };
481 }
482 
483 llvm::Expected<ASTUnit *> CrossTranslationUnitContext::loadExternalAST(
484     StringRef LookupName, StringRef CrossTUDir, StringRef IndexName,
485     bool DisplayCTUProgress) {
486   // FIXME: The current implementation only supports loading decls with
487   //        a lookup name from a single translation unit. If multiple
488   //        translation units contains decls with the same lookup name an
489   //        error will be returned.
490 
491   // Try to get the value from the heavily cached storage.
492   llvm::Expected<ASTUnit *> Unit = ASTStorage.getASTUnitForFunction(
493       LookupName, CrossTUDir, IndexName, DisplayCTUProgress);
494 
495   if (!Unit)
496     return Unit.takeError();
497 
498   // Check whether the backing pointer of the Expected is a nullptr.
499   if (!*Unit)
500     return llvm::make_error<IndexError>(
501         index_error_code::failed_to_get_external_ast);
502 
503   return Unit;
504 }
505 
506 CrossTranslationUnitContext::ASTLoader::ASTLoader(
507     CompilerInstance &CI, StringRef CTUDir, StringRef InvocationListFilePath)
508     : CI(CI), CTUDir(CTUDir), InvocationListFilePath(InvocationListFilePath) {}
509 
510 CrossTranslationUnitContext::LoadResultTy
511 CrossTranslationUnitContext::ASTLoader::load(StringRef Identifier) {
512   llvm::SmallString<256> Path;
513   if (llvm::sys::path::is_absolute(Identifier, PathStyle)) {
514     Path = Identifier;
515   } else {
516     Path = CTUDir;
517     llvm::sys::path::append(Path, PathStyle, Identifier);
518   }
519 
520   // The path is stored in the InvocationList member in posix style. To
521   // successfully lookup an entry based on filepath, it must be converted.
522   llvm::sys::path::native(Path, PathStyle);
523 
524   // Normalize by removing relative path components.
525   llvm::sys::path::remove_dots(Path, /*remove_dot_dot*/ true, PathStyle);
526 
527   if (Path.endswith(".ast"))
528     return loadFromDump(Path);
529   else
530     return loadFromSource(Path);
531 }
532 
533 CrossTranslationUnitContext::LoadResultTy
534 CrossTranslationUnitContext::ASTLoader::loadFromDump(StringRef ASTDumpPath) {
535   IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts = new DiagnosticOptions();
536   TextDiagnosticPrinter *DiagClient =
537       new TextDiagnosticPrinter(llvm::errs(), &*DiagOpts);
538   IntrusiveRefCntPtr<DiagnosticIDs> DiagID(new DiagnosticIDs());
539   IntrusiveRefCntPtr<DiagnosticsEngine> Diags(
540       new DiagnosticsEngine(DiagID, &*DiagOpts, DiagClient));
541   return ASTUnit::LoadFromASTFile(
542       std::string(ASTDumpPath.str()),
543       CI.getPCHContainerOperations()->getRawReader(), ASTUnit::LoadEverything,
544       Diags, CI.getFileSystemOpts());
545 }
546 
547 /// Load the AST from a source-file, which is supposed to be located inside the
548 /// YAML formatted invocation list file under the filesystem path specified by
549 /// \p InvocationList. The invocation list should contain absolute paths.
550 /// \p SourceFilePath is the absolute path of the source file that contains the
551 /// function definition the analysis is looking for. The Index is built by the
552 /// \p clang-extdef-mapping tool, which is also supposed to be generating
553 /// absolute paths.
554 ///
555 /// Proper diagnostic emission requires absolute paths, so even if a future
556 /// change introduces the handling of relative paths, this must be taken into
557 /// consideration.
558 CrossTranslationUnitContext::LoadResultTy
559 CrossTranslationUnitContext::ASTLoader::loadFromSource(
560     StringRef SourceFilePath) {
561 
562   if (llvm::Error InitError = lazyInitInvocationList())
563     return std::move(InitError);
564   assert(InvocationList);
565 
566   auto Invocation = InvocationList->find(SourceFilePath);
567   if (Invocation == InvocationList->end())
568     return llvm::make_error<IndexError>(
569         index_error_code::invocation_list_lookup_unsuccessful);
570 
571   const InvocationListTy::mapped_type &InvocationCommand = Invocation->second;
572 
573   SmallVector<const char *, 32> CommandLineArgs(InvocationCommand.size());
574   std::transform(InvocationCommand.begin(), InvocationCommand.end(),
575                  CommandLineArgs.begin(),
576                  [](auto &&CmdPart) { return CmdPart.c_str(); });
577 
578   IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts{&CI.getDiagnosticOpts()};
579   auto *DiagClient = new ForwardingDiagnosticConsumer{CI.getDiagnosticClient()};
580   IntrusiveRefCntPtr<DiagnosticIDs> DiagID{
581       CI.getDiagnostics().getDiagnosticIDs()};
582   IntrusiveRefCntPtr<DiagnosticsEngine> Diags(
583       new DiagnosticsEngine{DiagID, &*DiagOpts, DiagClient});
584 
585   return std::unique_ptr<ASTUnit>(ASTUnit::LoadFromCommandLine(
586       CommandLineArgs.begin(), (CommandLineArgs.end()),
587       CI.getPCHContainerOperations(), Diags,
588       CI.getHeaderSearchOpts().ResourceDir));
589 }
590 
591 llvm::Expected<InvocationListTy>
592 parseInvocationList(StringRef FileContent, llvm::sys::path::Style PathStyle) {
593   InvocationListTy InvocationList;
594 
595   /// LLVM YAML parser is used to extract information from invocation list file.
596   llvm::SourceMgr SM;
597   llvm::yaml::Stream InvocationFile(FileContent, SM);
598 
599   /// Only the first document is processed.
600   llvm::yaml::document_iterator FirstInvocationFile = InvocationFile.begin();
601 
602   /// There has to be at least one document available.
603   if (FirstInvocationFile == InvocationFile.end())
604     return llvm::make_error<IndexError>(
605         index_error_code::invocation_list_empty);
606 
607   llvm::yaml::Node *DocumentRoot = FirstInvocationFile->getRoot();
608   if (!DocumentRoot)
609     return llvm::make_error<IndexError>(
610         index_error_code::invocation_list_wrong_format);
611 
612   /// According to the format specified the document must be a mapping, where
613   /// the keys are paths to source files, and values are sequences of invocation
614   /// parts.
615   auto *Mappings = dyn_cast<llvm::yaml::MappingNode>(DocumentRoot);
616   if (!Mappings)
617     return llvm::make_error<IndexError>(
618         index_error_code::invocation_list_wrong_format);
619 
620   for (auto &NextMapping : *Mappings) {
621     /// The keys should be strings, which represent a source-file path.
622     auto *Key = dyn_cast<llvm::yaml::ScalarNode>(NextMapping.getKey());
623     if (!Key)
624       return llvm::make_error<IndexError>(
625           index_error_code::invocation_list_wrong_format);
626 
627     SmallVector<char, 32> ValueStorage;
628     StringRef SourcePath = Key->getValue(ValueStorage);
629 
630     // Store paths with PathStyle directory separator.
631     SmallVector<char, 32> NativeSourcePath;
632     llvm::Twine{SourcePath}.toVector(NativeSourcePath);
633     llvm::sys::path::native(NativeSourcePath, PathStyle);
634 
635     StringRef InvocationKey{NativeSourcePath.begin(), NativeSourcePath.size()};
636 
637     if (InvocationList.find(InvocationKey) != InvocationList.end())
638       return llvm::make_error<IndexError>(
639           index_error_code::invocation_list_ambiguous);
640 
641     /// The values should be sequences of strings, each representing a part of
642     /// the invocation.
643     auto *Args = dyn_cast<llvm::yaml::SequenceNode>(NextMapping.getValue());
644     if (!Args)
645       return llvm::make_error<IndexError>(
646           index_error_code::invocation_list_wrong_format);
647 
648     for (auto &Arg : *Args) {
649       auto *CmdString = dyn_cast<llvm::yaml::ScalarNode>(&Arg);
650       if (!CmdString)
651         return llvm::make_error<IndexError>(
652             index_error_code::invocation_list_wrong_format);
653       /// Every conversion starts with an empty working storage, as it is not
654       /// clear if this is a requirement of the YAML parser.
655       ValueStorage.clear();
656       InvocationList[InvocationKey].emplace_back(
657           CmdString->getValue(ValueStorage));
658     }
659 
660     if (InvocationList[InvocationKey].empty())
661       return llvm::make_error<IndexError>(
662           index_error_code::invocation_list_wrong_format);
663   }
664 
665   return InvocationList;
666 }
667 
668 llvm::Error CrossTranslationUnitContext::ASTLoader::lazyInitInvocationList() {
669   /// Lazily initialize the invocation list member used for on-demand parsing.
670   if (InvocationList)
671     return llvm::Error::success();
672 
673   llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> FileContent =
674       llvm::MemoryBuffer::getFile(InvocationListFilePath);
675   if (!FileContent)
676     return llvm::make_error<IndexError>(
677         index_error_code::invocation_list_file_not_found);
678   std::unique_ptr<llvm::MemoryBuffer> ContentBuffer = std::move(*FileContent);
679   assert(ContentBuffer && "If no error was produced after loading, the pointer "
680                           "should not be nullptr.");
681 
682   llvm::Expected<InvocationListTy> ExpectedInvocationList =
683       parseInvocationList(ContentBuffer->getBuffer(), PathStyle);
684 
685   if (!ExpectedInvocationList)
686     return ExpectedInvocationList.takeError();
687 
688   InvocationList = *ExpectedInvocationList;
689 
690   return llvm::Error::success();
691 }
692 
693 template <typename T>
694 llvm::Expected<const T *>
695 CrossTranslationUnitContext::importDefinitionImpl(const T *D, ASTUnit *Unit) {
696   assert(hasBodyOrInit(D) && "Decls to be imported should have body or init.");
697 
698   assert(&D->getASTContext() == &Unit->getASTContext() &&
699          "ASTContext of Decl and the unit should match.");
700   ASTImporter &Importer = getOrCreateASTImporter(Unit);
701 
702   auto ToDeclOrError = Importer.Import(D);
703   if (!ToDeclOrError) {
704     handleAllErrors(ToDeclOrError.takeError(),
705                     [&](const ImportError &IE) {
706                       switch (IE.Error) {
707                       case ImportError::NameConflict:
708                         ++NumNameConflicts;
709                          break;
710                       case ImportError::UnsupportedConstruct:
711                         ++NumUnsupportedNodeFound;
712                         break;
713                       case ImportError::Unknown:
714                         llvm_unreachable("Unknown import error happened.");
715                         break;
716                       }
717                     });
718     return llvm::make_error<IndexError>(index_error_code::failed_import);
719   }
720   auto *ToDecl = cast<T>(*ToDeclOrError);
721   assert(hasBodyOrInit(ToDecl) && "Imported Decl should have body or init.");
722   ++NumGetCTUSuccess;
723 
724   // Parent map is invalidated after changing the AST.
725   ToDecl->getASTContext().getParentMapContext().clear();
726 
727   return ToDecl;
728 }
729 
730 llvm::Expected<const FunctionDecl *>
731 CrossTranslationUnitContext::importDefinition(const FunctionDecl *FD,
732                                               ASTUnit *Unit) {
733   return importDefinitionImpl(FD, Unit);
734 }
735 
736 llvm::Expected<const VarDecl *>
737 CrossTranslationUnitContext::importDefinition(const VarDecl *VD,
738                                               ASTUnit *Unit) {
739   return importDefinitionImpl(VD, Unit);
740 }
741 
742 void CrossTranslationUnitContext::lazyInitImporterSharedSt(
743     TranslationUnitDecl *ToTU) {
744   if (!ImporterSharedSt)
745     ImporterSharedSt = std::make_shared<ASTImporterSharedState>(*ToTU);
746 }
747 
748 ASTImporter &
749 CrossTranslationUnitContext::getOrCreateASTImporter(ASTUnit *Unit) {
750   ASTContext &From = Unit->getASTContext();
751 
752   auto I = ASTUnitImporterMap.find(From.getTranslationUnitDecl());
753   if (I != ASTUnitImporterMap.end())
754     return *I->second;
755   lazyInitImporterSharedSt(Context.getTranslationUnitDecl());
756   ASTImporter *NewImporter = new ASTImporter(
757       Context, Context.getSourceManager().getFileManager(), From,
758       From.getSourceManager().getFileManager(), false, ImporterSharedSt);
759   NewImporter->setFileIDImportHandler([this, Unit](FileID ToID, FileID FromID) {
760     assert(ImportedFileIDs.find(ToID) == ImportedFileIDs.end() &&
761            "FileID already imported, should not happen.");
762     ImportedFileIDs[ToID] = std::make_pair(FromID, Unit);
763   });
764   ASTUnitImporterMap[From.getTranslationUnitDecl()].reset(NewImporter);
765   return *NewImporter;
766 }
767 
768 llvm::Optional<std::pair<SourceLocation, ASTUnit *>>
769 CrossTranslationUnitContext::getImportedFromSourceLocation(
770     const clang::SourceLocation &ToLoc) const {
771   const SourceManager &SM = Context.getSourceManager();
772   auto DecToLoc = SM.getDecomposedLoc(ToLoc);
773 
774   auto I = ImportedFileIDs.find(DecToLoc.first);
775   if (I == ImportedFileIDs.end())
776     return {};
777 
778   FileID FromID = I->second.first;
779   clang::ASTUnit *Unit = I->second.second;
780   SourceLocation FromLoc =
781       Unit->getSourceManager().getComposedLoc(FromID, DecToLoc.second);
782 
783   return std::make_pair(FromLoc, Unit);
784 }
785 
786 } // namespace cross_tu
787 } // namespace clang
788