1 //===- ExternalASTMerger.cpp - Merging External AST Interface ---*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file implements the ExternalASTMerger, which vends a combination of
11 //  ASTs from several different ASTContext/FileManager pairs
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/Decl.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/DeclObjC.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->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->setMustBuildLookupTable();
154       assert(Parent.CanComplete(ToContainer));
155     }
156     return ASTImporter::Imported(From, 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.Imported(SourceTag, Tag);
232     Forward.ImportDefinition(SourceTag);
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.Imported(SourceInterface, Interface);
251         Forward.ImportDefinition(SourceInterface);
252         return true;
253       });
254 }
255 
256 bool ExternalASTMerger::CanComplete(DeclContext *Interface) {
257   assert(Interface->hasExternalLexicalStorage() ||
258          Interface->hasExternalVisibleStorage());
259   bool FoundMatchingDC = false;
260   ForEachMatchingDC(Interface,
261                     [&](ASTImporter &Forward, ASTImporter &Reverse,
262                         Source<const DeclContext *> SourceDC) -> bool {
263                       FoundMatchingDC = true;
264                       return true;
265                     });
266   return FoundMatchingDC;
267 }
268 
269 namespace {
270 bool IsSameDC(const DeclContext *D1, const DeclContext *D2) {
271   if (isa<ObjCContainerDecl>(D1) && isa<ObjCContainerDecl>(D2))
272     return true; // There are many cases where Objective-C is ambiguous.
273   if (auto *T1 = dyn_cast<TagDecl>(D1))
274     if (auto *T2 = dyn_cast<TagDecl>(D2))
275       if (T1->getFirstDecl() == T2->getFirstDecl())
276         return true;
277   return D1 == D2 || D1 == CanonicalizeDC(D2);
278 }
279 }
280 
281 void ExternalASTMerger::MaybeRecordOrigin(const DeclContext *ToDC,
282                                           DCOrigin Origin) {
283   LazyASTImporter &Importer = LazyImporterForOrigin(*this, *Origin.AST);
284   ASTImporter &Reverse = Importer.GetReverse();
285   Source<const DeclContext *> FoundFromDC =
286       LookupSameContext(Origin.AST->getTranslationUnitDecl(), ToDC, Reverse);
287   const bool DoRecord = !FoundFromDC || !IsSameDC(FoundFromDC.get(), Origin.DC);
288   if (DoRecord)
289     RecordOriginImpl(ToDC, Origin, Importer);
290   if (LoggingEnabled())
291     logs() << "(ExternalASTMerger*)" << (void*)this
292              << (DoRecord ? " decided " : " decided NOT")
293              << " to record origin (DeclContext*)" << (void*)Origin.DC
294              << ", (ASTContext*)" << (void*)&Origin.AST
295              << "\n";
296 }
297 
298 void ExternalASTMerger::ForceRecordOrigin(const DeclContext *ToDC,
299                                           DCOrigin Origin) {
300   RecordOriginImpl(ToDC, Origin, ImporterForOrigin(*Origin.AST));
301 }
302 
303 void ExternalASTMerger::RecordOriginImpl(const DeclContext *ToDC, DCOrigin Origin,
304                                          ASTImporter &Importer) {
305   Origins[ToDC] = Origin;
306   Importer.ASTImporter::Imported(cast<Decl>(Origin.DC), const_cast<Decl*>(cast<Decl>(ToDC)));
307 }
308 
309 ExternalASTMerger::ExternalASTMerger(const ImporterTarget &Target,
310                                      llvm::ArrayRef<ImporterSource> Sources) : LogStream(&llvm::nulls()), Target(Target) {
311   AddSources(Sources);
312 }
313 
314 void ExternalASTMerger::AddSources(llvm::ArrayRef<ImporterSource> Sources) {
315   for (const ImporterSource &S : Sources) {
316     assert(&S.AST != &Target.AST);
317     Importers.push_back(llvm::make_unique<LazyASTImporter>(
318         *this, Target.AST, Target.FM, S.AST, S.FM, S.OM));
319   }
320 }
321 
322 void ExternalASTMerger::RemoveSources(llvm::ArrayRef<ImporterSource> Sources) {
323   if (LoggingEnabled())
324     for (const ImporterSource &S : Sources)
325       logs() << "(ExternalASTMerger*)" << (void*)this
326              << " removing source (ASTContext*)" << (void*)&S.AST
327              << "\n";
328   Importers.erase(
329       std::remove_if(Importers.begin(), Importers.end(),
330                      [&Sources](std::unique_ptr<ASTImporter> &Importer) -> bool {
331                        for (const ImporterSource &S : Sources) {
332                          if (&Importer->getFromContext() == &S.AST)
333                            return true;
334                        }
335                        return false;
336                      }),
337       Importers.end());
338   for (OriginMap::iterator OI = Origins.begin(), OE = Origins.end(); OI != OE; ) {
339     std::pair<const DeclContext *, DCOrigin> Origin = *OI;
340     bool Erase = false;
341     for (const ImporterSource &S : Sources) {
342       if (&S.AST == Origin.second.AST) {
343         Erase = true;
344         break;
345       }
346     }
347     if (Erase)
348       OI = Origins.erase(OI);
349     else
350       ++OI;
351   }
352 }
353 
354 bool ExternalASTMerger::FindExternalVisibleDeclsByName(const DeclContext *DC,
355                                                        DeclarationName Name) {
356   llvm::SmallVector<NamedDecl *, 1> Decls;
357   llvm::SmallVector<Candidate, 4> Candidates;
358 
359   auto FilterFoundDecl = [&Candidates](const Candidate &C) {
360    if (!HasDeclOfSameType(Candidates, C))
361      Candidates.push_back(C);
362   };
363 
364   ForEachMatchingDC(DC, [&](ASTImporter &Forward, ASTImporter &Reverse,
365                             Source<const DeclContext *> SourceDC) -> bool {
366     DeclarationName FromName = Reverse.Import(Name);
367     DeclContextLookupResult Result = SourceDC.get()->lookup(FromName);
368     for (NamedDecl *FromD : Result) {
369       FilterFoundDecl(std::make_pair(FromD, &Forward));
370     }
371     return false;
372   });
373 
374   if (Candidates.empty())
375     return false;
376 
377   Decls.reserve(Candidates.size());
378   for (const Candidate &C : Candidates) {
379     NamedDecl *d = cast<NamedDecl>(C.second->Import(C.first.get()));
380     assert(d);
381     Decls.push_back(d);
382   }
383   SetExternalVisibleDeclsForName(DC, Name, Decls);
384   return true;
385 }
386 
387 void ExternalASTMerger::FindExternalLexicalDecls(
388     const DeclContext *DC, llvm::function_ref<bool(Decl::Kind)> IsKindWeWant,
389     SmallVectorImpl<Decl *> &Result) {
390   ForEachMatchingDC(DC, [&](ASTImporter &Forward, ASTImporter &Reverse,
391                             Source<const DeclContext *> SourceDC) -> bool {
392     for (const Decl *SourceDecl : SourceDC.get()->decls()) {
393       if (IsKindWeWant(SourceDecl->getKind())) {
394         Decl *ImportedDecl = Forward.Import(const_cast<Decl *>(SourceDecl));
395         assert(!ImportedDecl || IsSameDC(ImportedDecl->getDeclContext(), DC));
396         (void)ImportedDecl;
397       }
398     }
399     return false;
400   });
401 }
402 
403