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   void 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   }
157   ASTImporter &GetReverse() { return Reverse; }
158 };
159 
160 bool HasDeclOfSameType(llvm::ArrayRef<Candidate> Decls, const Candidate &C) {
161   if (isa<FunctionDecl>(C.first.get()))
162     return false;
163   return llvm::any_of(Decls, [&](const Candidate &D) {
164     return C.first.get()->getKind() == D.first.get()->getKind();
165   });
166 }
167 
168 } // end namespace
169 
170 ASTImporter &ExternalASTMerger::ImporterForOrigin(ASTContext &OriginContext) {
171   for (const std::unique_ptr<ASTImporter> &I : Importers)
172     if (&I->getFromContext() == &OriginContext)
173       return *I;
174   llvm_unreachable("We should have an importer for this origin!");
175 }
176 
177 namespace {
178 LazyASTImporter &LazyImporterForOrigin(ExternalASTMerger &Merger,
179                                    ASTContext &OriginContext) {
180   return static_cast<LazyASTImporter &>(
181       Merger.ImporterForOrigin(OriginContext));
182 }
183 }
184 
185 bool ExternalASTMerger::HasImporterForOrigin(ASTContext &OriginContext) {
186   for (const std::unique_ptr<ASTImporter> &I : Importers)
187     if (&I->getFromContext() == &OriginContext)
188       return true;
189   return false;
190 }
191 
192 template <typename CallbackType>
193 void ExternalASTMerger::ForEachMatchingDC(const DeclContext *DC,
194                                           CallbackType Callback) {
195   if (Origins.count(DC)) {
196     ExternalASTMerger::DCOrigin Origin = Origins[DC];
197     LazyASTImporter &Importer = LazyImporterForOrigin(*this, *Origin.AST);
198     Callback(Importer, Importer.GetReverse(), Origin.DC);
199   } else {
200     bool DidCallback = false;
201     for (const std::unique_ptr<ASTImporter> &Importer : Importers) {
202       Source<TranslationUnitDecl *> SourceTU =
203           Importer->getFromContext().getTranslationUnitDecl();
204       ASTImporter &Reverse =
205           static_cast<LazyASTImporter *>(Importer.get())->GetReverse();
206       if (auto SourceDC = LookupSameContext(SourceTU, DC, Reverse)) {
207         DidCallback = true;
208         if (Callback(*Importer, Reverse, SourceDC))
209           break;
210       }
211     }
212     if (!DidCallback && LoggingEnabled())
213       logs() << "(ExternalASTMerger*)" << (void*)this
214              << " asserting for (DeclContext*)" << (const void*)DC
215              << ", (ASTContext*)" << (void*)&Target.AST
216              << "\n";
217     assert(DidCallback && "Couldn't find a source context matching our DC");
218   }
219 }
220 
221 void ExternalASTMerger::CompleteType(TagDecl *Tag) {
222   assert(Tag->hasExternalLexicalStorage());
223   ForEachMatchingDC(Tag, [&](ASTImporter &Forward, ASTImporter &Reverse,
224                              Source<const DeclContext *> SourceDC) -> bool {
225     auto *SourceTag = const_cast<TagDecl *>(cast<TagDecl>(SourceDC.get()));
226     if (SourceTag->hasExternalLexicalStorage())
227       SourceTag->getASTContext().getExternalSource()->CompleteType(SourceTag);
228     if (!SourceTag->getDefinition())
229       return false;
230     Forward.MapImported(SourceTag, Tag);
231     if (llvm::Error Err = Forward.ImportDefinition_New(SourceTag))
232       llvm::consumeError(std::move(Err));
233     Tag->setCompleteDefinition(SourceTag->isCompleteDefinition());
234     return true;
235   });
236 }
237 
238 void ExternalASTMerger::CompleteType(ObjCInterfaceDecl *Interface) {
239   assert(Interface->hasExternalLexicalStorage());
240   ForEachMatchingDC(
241       Interface, [&](ASTImporter &Forward, ASTImporter &Reverse,
242                      Source<const DeclContext *> SourceDC) -> bool {
243         auto *SourceInterface = const_cast<ObjCInterfaceDecl *>(
244             cast<ObjCInterfaceDecl>(SourceDC.get()));
245         if (SourceInterface->hasExternalLexicalStorage())
246           SourceInterface->getASTContext().getExternalSource()->CompleteType(
247               SourceInterface);
248         if (!SourceInterface->getDefinition())
249           return false;
250         Forward.MapImported(SourceInterface, Interface);
251         if (llvm::Error Err = Forward.ImportDefinition_New(SourceInterface))
252           llvm::consumeError(std::move(Err));
253         return true;
254       });
255 }
256 
257 bool ExternalASTMerger::CanComplete(DeclContext *Interface) {
258   assert(Interface->hasExternalLexicalStorage() ||
259          Interface->hasExternalVisibleStorage());
260   bool FoundMatchingDC = false;
261   ForEachMatchingDC(Interface,
262                     [&](ASTImporter &Forward, ASTImporter &Reverse,
263                         Source<const DeclContext *> SourceDC) -> bool {
264                       FoundMatchingDC = true;
265                       return true;
266                     });
267   return FoundMatchingDC;
268 }
269 
270 namespace {
271 bool IsSameDC(const DeclContext *D1, const DeclContext *D2) {
272   if (isa<ObjCContainerDecl>(D1) && isa<ObjCContainerDecl>(D2))
273     return true; // There are many cases where Objective-C is ambiguous.
274   if (auto *T1 = dyn_cast<TagDecl>(D1))
275     if (auto *T2 = dyn_cast<TagDecl>(D2))
276       if (T1->getFirstDecl() == T2->getFirstDecl())
277         return true;
278   return D1 == D2 || D1 == CanonicalizeDC(D2);
279 }
280 }
281 
282 void ExternalASTMerger::MaybeRecordOrigin(const DeclContext *ToDC,
283                                           DCOrigin Origin) {
284   LazyASTImporter &Importer = LazyImporterForOrigin(*this, *Origin.AST);
285   ASTImporter &Reverse = Importer.GetReverse();
286   Source<const DeclContext *> FoundFromDC =
287       LookupSameContext(Origin.AST->getTranslationUnitDecl(), ToDC, Reverse);
288   const bool DoRecord = !FoundFromDC || !IsSameDC(FoundFromDC.get(), Origin.DC);
289   if (DoRecord)
290     RecordOriginImpl(ToDC, Origin, Importer);
291   if (LoggingEnabled())
292     logs() << "(ExternalASTMerger*)" << (void*)this
293              << (DoRecord ? " decided " : " decided NOT")
294              << " to record origin (DeclContext*)" << (void*)Origin.DC
295              << ", (ASTContext*)" << (void*)&Origin.AST
296              << "\n";
297 }
298 
299 void ExternalASTMerger::ForceRecordOrigin(const DeclContext *ToDC,
300                                           DCOrigin Origin) {
301   RecordOriginImpl(ToDC, Origin, ImporterForOrigin(*Origin.AST));
302 }
303 
304 void ExternalASTMerger::RecordOriginImpl(const DeclContext *ToDC, DCOrigin Origin,
305                                          ASTImporter &Importer) {
306   Origins[ToDC] = Origin;
307   Importer.ASTImporter::MapImported(cast<Decl>(Origin.DC), const_cast<Decl*>(cast<Decl>(ToDC)));
308 }
309 
310 ExternalASTMerger::ExternalASTMerger(const ImporterTarget &Target,
311                                      llvm::ArrayRef<ImporterSource> Sources) : LogStream(&llvm::nulls()), Target(Target) {
312   AddSources(Sources);
313 }
314 
315 void ExternalASTMerger::AddSources(llvm::ArrayRef<ImporterSource> Sources) {
316   for (const ImporterSource &S : Sources) {
317     assert(&S.AST != &Target.AST);
318     Importers.push_back(llvm::make_unique<LazyASTImporter>(
319         *this, Target.AST, Target.FM, S.AST, S.FM, S.OM));
320   }
321 }
322 
323 void ExternalASTMerger::RemoveSources(llvm::ArrayRef<ImporterSource> Sources) {
324   if (LoggingEnabled())
325     for (const ImporterSource &S : Sources)
326       logs() << "(ExternalASTMerger*)" << (void*)this
327              << " removing source (ASTContext*)" << (void*)&S.AST
328              << "\n";
329   Importers.erase(
330       std::remove_if(Importers.begin(), Importers.end(),
331                      [&Sources](std::unique_ptr<ASTImporter> &Importer) -> bool {
332                        for (const ImporterSource &S : Sources) {
333                          if (&Importer->getFromContext() == &S.AST)
334                            return true;
335                        }
336                        return false;
337                      }),
338       Importers.end());
339   for (OriginMap::iterator OI = Origins.begin(), OE = Origins.end(); OI != OE; ) {
340     std::pair<const DeclContext *, DCOrigin> Origin = *OI;
341     bool Erase = false;
342     for (const ImporterSource &S : Sources) {
343       if (&S.AST == Origin.second.AST) {
344         Erase = true;
345         break;
346       }
347     }
348     if (Erase)
349       OI = Origins.erase(OI);
350     else
351       ++OI;
352   }
353 }
354 
355 template <typename DeclTy>
356 static bool importSpecializations(DeclTy *D, ASTImporter *Importer) {
357   for (auto *Spec : D->specializations())
358     if (!Importer->Import(Spec))
359       return true;
360   return false;
361 }
362 
363 /// Imports specializations from template declarations that can be specialized.
364 static bool importSpecializationsIfNeeded(Decl *D, ASTImporter *Importer) {
365   if (!isa<TemplateDecl>(D))
366     return false;
367   if (auto *FunctionTD = dyn_cast<FunctionTemplateDecl>(D))
368     return importSpecializations(FunctionTD, Importer);
369   else if (auto *ClassTD = dyn_cast<ClassTemplateDecl>(D))
370     return importSpecializations(ClassTD, Importer);
371   else if (auto *VarTD = dyn_cast<VarTemplateDecl>(D))
372     return importSpecializations(VarTD, Importer);
373   return false;
374 }
375 
376 bool ExternalASTMerger::FindExternalVisibleDeclsByName(const DeclContext *DC,
377                                                        DeclarationName Name) {
378   llvm::SmallVector<NamedDecl *, 1> Decls;
379   llvm::SmallVector<Candidate, 4> Candidates;
380 
381   auto FilterFoundDecl = [&Candidates](const Candidate &C) {
382    if (!HasDeclOfSameType(Candidates, C))
383      Candidates.push_back(C);
384   };
385 
386   ForEachMatchingDC(DC, [&](ASTImporter &Forward, ASTImporter &Reverse,
387                             Source<const DeclContext *> SourceDC) -> bool {
388     DeclarationName FromName = Reverse.Import(Name);
389     DeclContextLookupResult Result = SourceDC.get()->lookup(FromName);
390     for (NamedDecl *FromD : Result) {
391       FilterFoundDecl(std::make_pair(FromD, &Forward));
392     }
393     return false;
394   });
395 
396   if (Candidates.empty())
397     return false;
398 
399   Decls.reserve(Candidates.size());
400   for (const Candidate &C : Candidates) {
401     Decl *LookupRes = C.first.get();
402     ASTImporter *Importer = C.second;
403     NamedDecl *ND = cast_or_null<NamedDecl>(Importer->Import(LookupRes));
404     assert(ND);
405     // If we don't import specialization, they are not available via lookup
406     // because the lookup result is imported TemplateDecl and it does not
407     // reference its specializations until they are imported explicitly.
408     bool IsSpecImportFailed =
409         importSpecializationsIfNeeded(LookupRes, Importer);
410     assert(!IsSpecImportFailed);
411     (void)IsSpecImportFailed;
412     Decls.push_back(ND);
413   }
414   SetExternalVisibleDeclsForName(DC, Name, Decls);
415   return true;
416 }
417 
418 void ExternalASTMerger::FindExternalLexicalDecls(
419     const DeclContext *DC, llvm::function_ref<bool(Decl::Kind)> IsKindWeWant,
420     SmallVectorImpl<Decl *> &Result) {
421   ForEachMatchingDC(DC, [&](ASTImporter &Forward, ASTImporter &Reverse,
422                             Source<const DeclContext *> SourceDC) -> bool {
423     for (const Decl *SourceDecl : SourceDC.get()->decls()) {
424       if (IsKindWeWant(SourceDecl->getKind())) {
425         Decl *ImportedDecl = Forward.Import(const_cast<Decl *>(SourceDecl));
426         assert(!ImportedDecl || IsSameDC(ImportedDecl->getDeclContext(), DC));
427         (void)ImportedDecl;
428       }
429     }
430     return false;
431   });
432 }
433 
434