1 //===- ExternalASTMerger.cpp - Merging External AST Interface ---*- 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 ExternalASTMerger, which vends a combination of
10 //  ASTs from several different ASTContext/FileManager pairs
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/AST/ASTContext.h"
15 #include "clang/AST/Decl.h"
16 #include "clang/AST/DeclCXX.h"
17 #include "clang/AST/DeclObjC.h"
18 #include "clang/AST/DeclTemplate.h"
19 #include "clang/AST/ExternalASTMerger.h"
20 
21 using namespace clang;
22 
23 namespace {
24 
25 template <typename T> struct Source {
26   T t;
27   Source(T t) : t(t) {}
28   operator T() { return t; }
29   template <typename U = T> U &get() { return t; }
30   template <typename U = T> const U &get() const { return t; }
31   template <typename U> operator Source<U>() { return Source<U>(t); }
32 };
33 
34 typedef std::pair<Source<NamedDecl *>, ASTImporter *> Candidate;
35 
36 /// For the given DC, return the DC that is safe to perform lookups on.  This is
37 /// the DC we actually want to work with most of the time.
38 const DeclContext *CanonicalizeDC(const DeclContext *DC) {
39   if (isa<LinkageSpecDecl>(DC))
40     return DC->getRedeclContext();
41   return DC;
42 }
43 
44 Source<const DeclContext *>
45 LookupSameContext(Source<TranslationUnitDecl *> SourceTU, const DeclContext *DC,
46                   ASTImporter &ReverseImporter) {
47   DC = CanonicalizeDC(DC);
48   if (DC->isTranslationUnit()) {
49     return SourceTU;
50   }
51   Source<const DeclContext *> SourceParentDC =
52       LookupSameContext(SourceTU, DC->getParent(), ReverseImporter);
53   if (!SourceParentDC) {
54     // If we couldn't find the parent DC in this TranslationUnit, give up.
55     return nullptr;
56   }
57   auto *ND = cast<NamedDecl>(DC);
58   DeclarationName Name = ND->getDeclName();
59   Source<DeclarationName> SourceName = ReverseImporter.Import(Name);
60   DeclContext::lookup_result SearchResult =
61       SourceParentDC.get()->lookup(SourceName.get());
62   size_t SearchResultSize = SearchResult.size();
63   if (SearchResultSize == 0 || SearchResultSize > 1) {
64     // There are two cases here.  First, we might not find the name.
65     // We might also find multiple copies, in which case we have no
66     // guarantee that the one we wanted is the one we pick.  (E.g.,
67     // if we have two specializations of the same template it is
68     // very hard to determine which is the one you want.)
69     //
70     // The Origins map fixes this problem by allowing the origin to be
71     // explicitly recorded, so we trigger that recording by returning
72     // nothing (rather than a possibly-inaccurate guess) here.
73     return nullptr;
74   } else {
75     NamedDecl *SearchResultDecl = SearchResult[0];
76     if (isa<DeclContext>(SearchResultDecl) &&
77         SearchResultDecl->getKind() == DC->getDeclKind())
78       return cast<DeclContext>(SearchResultDecl)->getPrimaryContext();
79     return nullptr; // This type of lookup is unsupported
80   }
81 }
82 
83 /// A custom implementation of ASTImporter, for ExternalASTMerger's purposes.
84 ///
85 /// There are several modifications:
86 ///
87 /// - It enables lazy lookup (via the HasExternalLexicalStorage flag and a few
88 ///   others), which instructs Clang to refer to ExternalASTMerger.  Also, it
89 ///   forces MinimalImport to true, which is necessary to make this work.
90 /// - It maintains a reverse importer for use with names.  This allows lookup of
91 ///   arbitrary names in the source context.
92 /// - It updates the ExternalASTMerger's origin map as needed whenever a
93 ///   it sees a DeclContext.
94 class LazyASTImporter : public ASTImporter {
95 private:
96   ExternalASTMerger &Parent;
97   ASTImporter Reverse;
98   const ExternalASTMerger::OriginMap &FromOrigins;
99 
100   llvm::raw_ostream &logs() { return Parent.logs(); }
101 public:
102   LazyASTImporter(ExternalASTMerger &_Parent, ASTContext &ToContext,
103                   FileManager &ToFileManager, ASTContext &FromContext,
104                   FileManager &FromFileManager,
105                   const ExternalASTMerger::OriginMap &_FromOrigins)
106       : ASTImporter(ToContext, ToFileManager, FromContext, FromFileManager,
107                     /*MinimalImport=*/true),
108         Parent(_Parent), Reverse(FromContext, FromFileManager, ToContext,
109                                  ToFileManager, /*MinimalImport=*/true), FromOrigins(_FromOrigins) {}
110 
111   /// Whenever a DeclContext is imported, ensure that ExternalASTSource's origin
112   /// map is kept up to date.  Also set the appropriate flags.
113   Decl *Imported(Decl *From, Decl *To) override {
114     if (auto *ToDC = dyn_cast<DeclContext>(To)) {
115       const bool LoggingEnabled = Parent.LoggingEnabled();
116       if (LoggingEnabled)
117         logs() << "(ExternalASTMerger*)" << (void*)&Parent
118                << " imported (DeclContext*)" << (void*)ToDC
119                << ", (ASTContext*)" << (void*)&getToContext()
120                << " from (DeclContext*)" << (void*)llvm::cast<DeclContext>(From)
121                << ", (ASTContext*)" << (void*)&getFromContext()
122                << "\n";
123       Source<DeclContext *> FromDC(
124           cast<DeclContext>(From)->getPrimaryContext());
125       if (FromOrigins.count(FromDC) &&
126           Parent.HasImporterForOrigin(*FromOrigins.at(FromDC).AST)) {
127         if (LoggingEnabled)
128           logs() << "(ExternalASTMerger*)" << (void*)&Parent
129                  << " forced origin (DeclContext*)"
130                  << (void*)FromOrigins.at(FromDC).DC
131                  << ", (ASTContext*)"
132                  << (void*)FromOrigins.at(FromDC).AST
133                  << "\n";
134         Parent.ForceRecordOrigin(ToDC, FromOrigins.at(FromDC));
135       } else {
136         if (LoggingEnabled)
137           logs() << "(ExternalASTMerger*)" << (void*)&Parent
138                  << " maybe recording origin (DeclContext*)" << (void*)FromDC
139                  << ", (ASTContext*)" << (void*)&getFromContext()
140                  << "\n";
141         Parent.MaybeRecordOrigin(ToDC, {FromDC, &getFromContext()});
142       }
143     }
144     if (auto *ToTag = dyn_cast<TagDecl>(To)) {
145       ToTag->setHasExternalLexicalStorage();
146       ToTag->getPrimaryContext()->setMustBuildLookupTable();
147       assert(Parent.CanComplete(ToTag));
148     } else if (auto *ToNamespace = dyn_cast<NamespaceDecl>(To)) {
149       ToNamespace->setHasExternalVisibleStorage();
150       assert(Parent.CanComplete(ToNamespace));
151     } else if (auto *ToContainer = dyn_cast<ObjCContainerDecl>(To)) {
152       ToContainer->setHasExternalLexicalStorage();
153       ToContainer->getPrimaryContext()->setMustBuildLookupTable();
154       assert(Parent.CanComplete(ToContainer));
155     }
156     return To;
157   }
158   ASTImporter &GetReverse() { return Reverse; }
159 };
160 
161 bool HasDeclOfSameType(llvm::ArrayRef<Candidate> Decls, const Candidate &C) {
162   if (isa<FunctionDecl>(C.first.get()))
163     return false;
164   return llvm::any_of(Decls, [&](const Candidate &D) {
165     return C.first.get()->getKind() == D.first.get()->getKind();
166   });
167 }
168 
169 } // end namespace
170 
171 ASTImporter &ExternalASTMerger::ImporterForOrigin(ASTContext &OriginContext) {
172   for (const std::unique_ptr<ASTImporter> &I : Importers)
173     if (&I->getFromContext() == &OriginContext)
174       return *I;
175   llvm_unreachable("We should have an importer for this origin!");
176 }
177 
178 namespace {
179 LazyASTImporter &LazyImporterForOrigin(ExternalASTMerger &Merger,
180                                    ASTContext &OriginContext) {
181   return static_cast<LazyASTImporter &>(
182       Merger.ImporterForOrigin(OriginContext));
183 }
184 }
185 
186 bool ExternalASTMerger::HasImporterForOrigin(ASTContext &OriginContext) {
187   for (const std::unique_ptr<ASTImporter> &I : Importers)
188     if (&I->getFromContext() == &OriginContext)
189       return true;
190   return false;
191 }
192 
193 template <typename CallbackType>
194 void ExternalASTMerger::ForEachMatchingDC(const DeclContext *DC,
195                                           CallbackType Callback) {
196   if (Origins.count(DC)) {
197     ExternalASTMerger::DCOrigin Origin = Origins[DC];
198     LazyASTImporter &Importer = LazyImporterForOrigin(*this, *Origin.AST);
199     Callback(Importer, Importer.GetReverse(), Origin.DC);
200   } else {
201     bool DidCallback = false;
202     for (const std::unique_ptr<ASTImporter> &Importer : Importers) {
203       Source<TranslationUnitDecl *> SourceTU =
204           Importer->getFromContext().getTranslationUnitDecl();
205       ASTImporter &Reverse =
206           static_cast<LazyASTImporter *>(Importer.get())->GetReverse();
207       if (auto SourceDC = LookupSameContext(SourceTU, DC, Reverse)) {
208         DidCallback = true;
209         if (Callback(*Importer, Reverse, SourceDC))
210           break;
211       }
212     }
213     if (!DidCallback && LoggingEnabled())
214       logs() << "(ExternalASTMerger*)" << (void*)this
215              << " asserting for (DeclContext*)" << (const void*)DC
216              << ", (ASTContext*)" << (void*)&Target.AST
217              << "\n";
218     assert(DidCallback && "Couldn't find a source context matching our DC");
219   }
220 }
221 
222 void ExternalASTMerger::CompleteType(TagDecl *Tag) {
223   assert(Tag->hasExternalLexicalStorage());
224   ForEachMatchingDC(Tag, [&](ASTImporter &Forward, ASTImporter &Reverse,
225                              Source<const DeclContext *> SourceDC) -> bool {
226     auto *SourceTag = const_cast<TagDecl *>(cast<TagDecl>(SourceDC.get()));
227     if (SourceTag->hasExternalLexicalStorage())
228       SourceTag->getASTContext().getExternalSource()->CompleteType(SourceTag);
229     if (!SourceTag->getDefinition())
230       return false;
231     Forward.MapImported(SourceTag, Tag);
232     if (llvm::Error Err = Forward.ImportDefinition_New(SourceTag))
233       llvm::consumeError(std::move(Err));
234     Tag->setCompleteDefinition(SourceTag->isCompleteDefinition());
235     return true;
236   });
237 }
238 
239 void ExternalASTMerger::CompleteType(ObjCInterfaceDecl *Interface) {
240   assert(Interface->hasExternalLexicalStorage());
241   ForEachMatchingDC(
242       Interface, [&](ASTImporter &Forward, ASTImporter &Reverse,
243                      Source<const DeclContext *> SourceDC) -> bool {
244         auto *SourceInterface = const_cast<ObjCInterfaceDecl *>(
245             cast<ObjCInterfaceDecl>(SourceDC.get()));
246         if (SourceInterface->hasExternalLexicalStorage())
247           SourceInterface->getASTContext().getExternalSource()->CompleteType(
248               SourceInterface);
249         if (!SourceInterface->getDefinition())
250           return false;
251         Forward.MapImported(SourceInterface, Interface);
252         if (llvm::Error Err = Forward.ImportDefinition_New(SourceInterface))
253           llvm::consumeError(std::move(Err));
254         return true;
255       });
256 }
257 
258 bool ExternalASTMerger::CanComplete(DeclContext *Interface) {
259   assert(Interface->hasExternalLexicalStorage() ||
260          Interface->hasExternalVisibleStorage());
261   bool FoundMatchingDC = false;
262   ForEachMatchingDC(Interface,
263                     [&](ASTImporter &Forward, ASTImporter &Reverse,
264                         Source<const DeclContext *> SourceDC) -> bool {
265                       FoundMatchingDC = true;
266                       return true;
267                     });
268   return FoundMatchingDC;
269 }
270 
271 namespace {
272 bool IsSameDC(const DeclContext *D1, const DeclContext *D2) {
273   if (isa<ObjCContainerDecl>(D1) && isa<ObjCContainerDecl>(D2))
274     return true; // There are many cases where Objective-C is ambiguous.
275   if (auto *T1 = dyn_cast<TagDecl>(D1))
276     if (auto *T2 = dyn_cast<TagDecl>(D2))
277       if (T1->getFirstDecl() == T2->getFirstDecl())
278         return true;
279   return D1 == D2 || D1 == CanonicalizeDC(D2);
280 }
281 }
282 
283 void ExternalASTMerger::MaybeRecordOrigin(const DeclContext *ToDC,
284                                           DCOrigin Origin) {
285   LazyASTImporter &Importer = LazyImporterForOrigin(*this, *Origin.AST);
286   ASTImporter &Reverse = Importer.GetReverse();
287   Source<const DeclContext *> FoundFromDC =
288       LookupSameContext(Origin.AST->getTranslationUnitDecl(), ToDC, Reverse);
289   const bool DoRecord = !FoundFromDC || !IsSameDC(FoundFromDC.get(), Origin.DC);
290   if (DoRecord)
291     RecordOriginImpl(ToDC, Origin, Importer);
292   if (LoggingEnabled())
293     logs() << "(ExternalASTMerger*)" << (void*)this
294              << (DoRecord ? " decided " : " decided NOT")
295              << " to record origin (DeclContext*)" << (void*)Origin.DC
296              << ", (ASTContext*)" << (void*)&Origin.AST
297              << "\n";
298 }
299 
300 void ExternalASTMerger::ForceRecordOrigin(const DeclContext *ToDC,
301                                           DCOrigin Origin) {
302   RecordOriginImpl(ToDC, Origin, ImporterForOrigin(*Origin.AST));
303 }
304 
305 void ExternalASTMerger::RecordOriginImpl(const DeclContext *ToDC, DCOrigin Origin,
306                                          ASTImporter &Importer) {
307   Origins[ToDC] = Origin;
308   Importer.ASTImporter::MapImported(cast<Decl>(Origin.DC), const_cast<Decl*>(cast<Decl>(ToDC)));
309 }
310 
311 ExternalASTMerger::ExternalASTMerger(const ImporterTarget &Target,
312                                      llvm::ArrayRef<ImporterSource> Sources) : LogStream(&llvm::nulls()), Target(Target) {
313   AddSources(Sources);
314 }
315 
316 void ExternalASTMerger::AddSources(llvm::ArrayRef<ImporterSource> Sources) {
317   for (const ImporterSource &S : Sources) {
318     assert(&S.AST != &Target.AST);
319     Importers.push_back(llvm::make_unique<LazyASTImporter>(
320         *this, Target.AST, Target.FM, S.AST, S.FM, S.OM));
321   }
322 }
323 
324 void ExternalASTMerger::RemoveSources(llvm::ArrayRef<ImporterSource> Sources) {
325   if (LoggingEnabled())
326     for (const ImporterSource &S : Sources)
327       logs() << "(ExternalASTMerger*)" << (void*)this
328              << " removing source (ASTContext*)" << (void*)&S.AST
329              << "\n";
330   Importers.erase(
331       std::remove_if(Importers.begin(), Importers.end(),
332                      [&Sources](std::unique_ptr<ASTImporter> &Importer) -> bool {
333                        for (const ImporterSource &S : Sources) {
334                          if (&Importer->getFromContext() == &S.AST)
335                            return true;
336                        }
337                        return false;
338                      }),
339       Importers.end());
340   for (OriginMap::iterator OI = Origins.begin(), OE = Origins.end(); OI != OE; ) {
341     std::pair<const DeclContext *, DCOrigin> Origin = *OI;
342     bool Erase = false;
343     for (const ImporterSource &S : Sources) {
344       if (&S.AST == Origin.second.AST) {
345         Erase = true;
346         break;
347       }
348     }
349     if (Erase)
350       OI = Origins.erase(OI);
351     else
352       ++OI;
353   }
354 }
355 
356 template <typename DeclTy>
357 static bool importSpecializations(DeclTy *D, ASTImporter *Importer) {
358   for (auto *Spec : D->specializations())
359     if (!Importer->Import(Spec))
360       return true;
361   return false;
362 }
363 
364 /// Imports specializations from template declarations that can be specialized.
365 static bool importSpecializationsIfNeeded(Decl *D, ASTImporter *Importer) {
366   if (!isa<TemplateDecl>(D))
367     return false;
368   if (auto *FunctionTD = dyn_cast<FunctionTemplateDecl>(D))
369     return importSpecializations(FunctionTD, Importer);
370   else if (auto *ClassTD = dyn_cast<ClassTemplateDecl>(D))
371     return importSpecializations(ClassTD, Importer);
372   else if (auto *VarTD = dyn_cast<VarTemplateDecl>(D))
373     return importSpecializations(VarTD, Importer);
374   return false;
375 }
376 
377 bool ExternalASTMerger::FindExternalVisibleDeclsByName(const DeclContext *DC,
378                                                        DeclarationName Name) {
379   llvm::SmallVector<NamedDecl *, 1> Decls;
380   llvm::SmallVector<Candidate, 4> Candidates;
381 
382   auto FilterFoundDecl = [&Candidates](const Candidate &C) {
383    if (!HasDeclOfSameType(Candidates, C))
384      Candidates.push_back(C);
385   };
386 
387   ForEachMatchingDC(DC, [&](ASTImporter &Forward, ASTImporter &Reverse,
388                             Source<const DeclContext *> SourceDC) -> bool {
389     DeclarationName FromName = Reverse.Import(Name);
390     DeclContextLookupResult Result = SourceDC.get()->lookup(FromName);
391     for (NamedDecl *FromD : Result) {
392       FilterFoundDecl(std::make_pair(FromD, &Forward));
393     }
394     return false;
395   });
396 
397   if (Candidates.empty())
398     return false;
399 
400   Decls.reserve(Candidates.size());
401   for (const Candidate &C : Candidates) {
402     Decl *LookupRes = C.first.get();
403     ASTImporter *Importer = C.second;
404     NamedDecl *ND = cast_or_null<NamedDecl>(Importer->Import(LookupRes));
405     assert(ND);
406     // If we don't import specialization, they are not available via lookup
407     // because the lookup result is imported TemplateDecl and it does not
408     // reference its specializations until they are imported explicitly.
409     bool IsSpecImportFailed =
410         importSpecializationsIfNeeded(LookupRes, Importer);
411     assert(!IsSpecImportFailed);
412     (void)IsSpecImportFailed;
413     Decls.push_back(ND);
414   }
415   SetExternalVisibleDeclsForName(DC, Name, Decls);
416   return true;
417 }
418 
419 void ExternalASTMerger::FindExternalLexicalDecls(
420     const DeclContext *DC, llvm::function_ref<bool(Decl::Kind)> IsKindWeWant,
421     SmallVectorImpl<Decl *> &Result) {
422   ForEachMatchingDC(DC, [&](ASTImporter &Forward, ASTImporter &Reverse,
423                             Source<const DeclContext *> SourceDC) -> bool {
424     for (const Decl *SourceDecl : SourceDC.get()->decls()) {
425       if (IsKindWeWant(SourceDecl->getKind())) {
426         Decl *ImportedDecl = Forward.Import(const_cast<Decl *>(SourceDecl));
427         assert(!ImportedDecl || IsSameDC(ImportedDecl->getDeclContext(), DC));
428         (void)ImportedDecl;
429       }
430     }
431     return false;
432   });
433 }
434 
435