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
21using namespace clang;
22
23namespace {
24
25template <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
34typedef 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.
38const DeclContext *CanonicalizeDC(const DeclContext *DC) {
39  if (isa<LinkageSpecDecl>(DC))
40    return DC->getRedeclContext();
41  return DC;
42}
43
44Source<const DeclContext *>
45LookupSameContext(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  auto SourceNameOrErr = ReverseImporter.Import(Name);
60  if (!SourceNameOrErr) {
61    llvm::consumeError(SourceNameOrErr.takeError());
62    return nullptr;
63  }
64  Source<DeclarationName> SourceName = *SourceNameOrErr;
65  DeclContext::lookup_result SearchResult =
66      SourceParentDC.get()->lookup(SourceName.get());
67
68  // There are two cases here. First, we might not find the name.
69  // We might also find multiple copies, in which case we have no
70  // guarantee that the one we wanted is the one we pick.  (E.g.,
71  // if we have two specializations of the same template it is
72  // very hard to determine which is the one you want.)
73  //
74  // The Origins map fixes this problem by allowing the origin to be
75  // explicitly recorded, so we trigger that recording by returning
76  // nothing (rather than a possibly-inaccurate guess) here.
77  if (SearchResult.isSingleResult()) {
78    NamedDecl *SearchResultDecl = SearchResult.front();
79    if (isa<DeclContext>(SearchResultDecl) &&
80        SearchResultDecl->getKind() == DC->getDeclKind())
81      return cast<DeclContext>(SearchResultDecl)->getPrimaryContext();
82    return nullptr; // This type of lookup is unsupported
83  } else {
84    return nullptr;
85  }
86}
87
88/// A custom implementation of ASTImporter, for ExternalASTMerger's purposes.
89///
90/// There are several modifications:
91///
92/// - It enables lazy lookup (via the HasExternalLexicalStorage flag and a few
93///   others), which instructs Clang to refer to ExternalASTMerger.  Also, it
94///   forces MinimalImport to true, which is necessary to make this work.
95/// - It maintains a reverse importer for use with names.  This allows lookup of
96///   arbitrary names in the source context.
97/// - It updates the ExternalASTMerger's origin map as needed whenever a
98///   it sees a DeclContext.
99class LazyASTImporter : public ASTImporter {
100private:
101  ExternalASTMerger &Parent;
102  ASTImporter Reverse;
103  const ExternalASTMerger::OriginMap &FromOrigins;
104  /// @see ExternalASTMerger::ImporterSource::Temporary
105  bool TemporarySource;
106  /// Map of imported declarations back to the declarations they originated
107  /// from.
108  llvm::DenseMap<Decl *, Decl *> ToOrigin;
109  /// @see ExternalASTMerger::ImporterSource::Merger
110  ExternalASTMerger *SourceMerger;
111  llvm::raw_ostream &logs() { return Parent.logs(); }
112public:
113  LazyASTImporter(ExternalASTMerger &_Parent, ASTContext &ToContext,
114                  FileManager &ToFileManager,
115                  const ExternalASTMerger::ImporterSource &S,
116                  std::shared_ptr<ASTImporterSharedState> SharedState)
117      : ASTImporter(ToContext, ToFileManager, S.getASTContext(),
118                    S.getFileManager(),
119                    /*MinimalImport=*/true, SharedState),
120        Parent(_Parent),
121        Reverse(S.getASTContext(), S.getFileManager(), ToContext, ToFileManager,
122                /*MinimalImport=*/true),
123        FromOrigins(S.getOriginMap()), TemporarySource(S.isTemporary()),
124        SourceMerger(S.getMerger()) {}
125
126  llvm::Expected<Decl *> ImportImpl(Decl *FromD) override {
127    if (!TemporarySource || !SourceMerger)
128      return ASTImporter::ImportImpl(FromD);
129
130    // If we get here, then this source is importing from a temporary ASTContext
131    // that also has another ExternalASTMerger attached. It could be
132    // possible that the current ExternalASTMerger and the temporary ASTContext
133    // share a common ImporterSource, which means that the temporary
134    // AST could contain declarations that were imported from a source
135    // that this ExternalASTMerger can access directly. Instead of importing
136    // such declarations from the temporary ASTContext, they should instead
137    // be directly imported by this ExternalASTMerger from the original
138    // source. This way the ExternalASTMerger can safely do a minimal import
139    // without creating incomplete declarations originated from a temporary
140    // ASTContext. If we would try to complete such declarations later on, we
141    // would fail to do so as their temporary AST could be deleted (which means
142    // that the missing parts of the minimally imported declaration in that
143    // ASTContext were also deleted).
144    //
145    // The following code tracks back any declaration that needs to be
146    // imported from the temporary ASTContext to a persistent ASTContext.
147    // Then the ExternalASTMerger tries to import from the persistent
148    // ASTContext directly by using the associated ASTImporter. If that
149    // succeeds, this ASTImporter just maps the declarations imported by
150    // the other (persistent) ASTImporter to this (temporary) ASTImporter.
151    // The steps can be visualized like this:
152    //
153    //  Target AST <--- 3. Indirect import --- Persistent AST
154    //       ^            of persistent decl        ^
155    //       |                                      |
156    // 1. Current import           2. Tracking back to persistent decl
157    // 4. Map persistent decl                       |
158    //  & pretend we imported.                      |
159    //       |                                      |
160    // Temporary AST -------------------------------'
161
162    // First, ask the ExternalASTMerger of the source where the temporary
163    // declaration originated from.
164    Decl *Persistent = SourceMerger->FindOriginalDecl(FromD);
165    // FromD isn't from a persistent AST, so just do a normal import.
166    if (!Persistent)
167      return ASTImporter::ImportImpl(FromD);
168    // Now ask the current ExternalASTMerger to try import the persistent
169    // declaration into the target.
170    ASTContext &PersistentCtx = Persistent->getASTContext();
171    ASTImporter &OtherImporter = Parent.ImporterForOrigin(PersistentCtx);
172    // Check that we never end up in the current Importer again.
173    assert((&PersistentCtx != &getFromContext()) && (&OtherImporter != this) &&
174           "Delegated to same Importer?");
175    auto DeclOrErr = OtherImporter.Import(Persistent);
176    // Errors when importing the persistent decl are treated as if we
177    // had errors with importing the temporary decl.
178    if (!DeclOrErr)
179      return DeclOrErr.takeError();
180    Decl *D = *DeclOrErr;
181    // Tell the current ASTImporter that this has already been imported
182    // to prevent any further queries for the temporary decl.
183    MapImported(FromD, D);
184    return D;
185  }
186
187  /// Implements the ASTImporter interface for tracking back a declaration
188  /// to its original declaration it came from.
189  Decl *GetOriginalDecl(Decl *To) override {
190    auto It = ToOrigin.find(To);
191    if (It != ToOrigin.end())
192      return It->second;
193    return nullptr;
194  }
195
196  /// Whenever a DeclContext is imported, ensure that ExternalASTSource's origin
197  /// map is kept up to date.  Also set the appropriate flags.
198  void Imported(Decl *From, Decl *To) override {
199    ToOrigin[To] = From;
200
201    if (auto *ToDC = dyn_cast<DeclContext>(To)) {
202      const bool LoggingEnabled = Parent.LoggingEnabled();
203      if (LoggingEnabled)
204        logs() << "(ExternalASTMerger*)" << (void*)&Parent
205               << " imported (DeclContext*)" << (void*)ToDC
206               << ", (ASTContext*)" << (void*)&getToContext()
207               << " from (DeclContext*)" << (void*)llvm::cast<DeclContext>(From)
208               << ", (ASTContext*)" << (void*)&getFromContext()
209               << "\n";
210      Source<DeclContext *> FromDC(
211          cast<DeclContext>(From)->getPrimaryContext());
212      if (FromOrigins.count(FromDC) &&
213          Parent.HasImporterForOrigin(*FromOrigins.at(FromDC).AST)) {
214        if (LoggingEnabled)
215          logs() << "(ExternalASTMerger*)" << (void*)&Parent
216                 << " forced origin (DeclContext*)"
217                 << (void*)FromOrigins.at(FromDC).DC
218                 << ", (ASTContext*)"
219                 << (void*)FromOrigins.at(FromDC).AST
220                 << "\n";
221        Parent.ForceRecordOrigin(ToDC, FromOrigins.at(FromDC));
222      } else {
223        if (LoggingEnabled)
224          logs() << "(ExternalASTMerger*)" << (void*)&Parent
225                 << " maybe recording origin (DeclContext*)" << (void*)FromDC
226                 << ", (ASTContext*)" << (void*)&getFromContext()
227                 << "\n";
228        Parent.MaybeRecordOrigin(ToDC, {FromDC, &getFromContext()});
229      }
230    }
231    if (auto *ToTag = dyn_cast<TagDecl>(To)) {
232      ToTag->setHasExternalLexicalStorage();
233      ToTag->getPrimaryContext()->setMustBuildLookupTable();
234      assert(Parent.CanComplete(ToTag));
235    } else if (auto *ToNamespace = dyn_cast<NamespaceDecl>(To)) {
236      ToNamespace->setHasExternalVisibleStorage();
237      assert(Parent.CanComplete(ToNamespace));
238    } else if (auto *ToContainer = dyn_cast<ObjCContainerDecl>(To)) {
239      ToContainer->setHasExternalLexicalStorage();
240      ToContainer->getPrimaryContext()->setMustBuildLookupTable();
241      assert(Parent.CanComplete(ToContainer));
242    }
243  }
244  ASTImporter &GetReverse() { return Reverse; }
245};
246
247bool HasDeclOfSameType(llvm::ArrayRef<Candidate> Decls, const Candidate &C) {
248  if (isa<FunctionDecl>(C.first.get()))
249    return false;
250  return llvm::any_of(Decls, [&](const Candidate &D) {
251    return C.first.get()->getKind() == D.first.get()->getKind();
252  });
253}
254
255} // end namespace
256
257ASTImporter &ExternalASTMerger::ImporterForOrigin(ASTContext &OriginContext) {
258  for (const std::unique_ptr<ASTImporter> &I : Importers)
259    if (&I->getFromContext() == &OriginContext)
260      return *I;
261  llvm_unreachable("We should have an importer for this origin!");
262}
263
264namespace {
265LazyASTImporter &LazyImporterForOrigin(ExternalASTMerger &Merger,
266                                   ASTContext &OriginContext) {
267  return static_cast<LazyASTImporter &>(
268      Merger.ImporterForOrigin(OriginContext));
269}
270}
271
272bool ExternalASTMerger::HasImporterForOrigin(ASTContext &OriginContext) {
273  for (const std::unique_ptr<ASTImporter> &I : Importers)
274    if (&I->getFromContext() == &OriginContext)
275      return true;
276  return false;
277}
278
279template <typename CallbackType>
280void ExternalASTMerger::ForEachMatchingDC(const DeclContext *DC,
281                                          CallbackType Callback) {
282  if (Origins.count(DC)) {
283    ExternalASTMerger::DCOrigin Origin = Origins[DC];
284    LazyASTImporter &Importer = LazyImporterForOrigin(*this, *Origin.AST);
285    Callback(Importer, Importer.GetReverse(), Origin.DC);
286  } else {
287    bool DidCallback = false;
288    for (const std::unique_ptr<ASTImporter> &Importer : Importers) {
289      Source<TranslationUnitDecl *> SourceTU =
290          Importer->getFromContext().getTranslationUnitDecl();
291      ASTImporter &Reverse =
292          static_cast<LazyASTImporter *>(Importer.get())->GetReverse();
293      if (auto SourceDC = LookupSameContext(SourceTU, DC, Reverse)) {
294        DidCallback = true;
295        if (Callback(*Importer, Reverse, SourceDC))
296          break;
297      }
298    }
299    if (!DidCallback && LoggingEnabled())
300      logs() << "(ExternalASTMerger*)" << (void*)this
301             << " asserting for (DeclContext*)" << (const void*)DC
302             << ", (ASTContext*)" << (void*)&Target.AST
303             << "\n";
304    assert(DidCallback && "Couldn't find a source context matching our DC");
305  }
306}
307
308void ExternalASTMerger::CompleteType(TagDecl *Tag) {
309  assert(Tag->hasExternalLexicalStorage());
310  ForEachMatchingDC(Tag, [&](ASTImporter &Forward, ASTImporter &Reverse,
311                             Source<const DeclContext *> SourceDC) -> bool {
312    auto *SourceTag = const_cast<TagDecl *>(cast<TagDecl>(SourceDC.get()));
313    if (SourceTag->hasExternalLexicalStorage())
314      SourceTag->getASTContext().getExternalSource()->CompleteType(SourceTag);
315    if (!SourceTag->getDefinition())
316      return false;
317    Forward.MapImported(SourceTag, Tag);
318    if (llvm::Error Err = Forward.ImportDefinition(SourceTag))
319      llvm::consumeError(std::move(Err));
320    Tag->setCompleteDefinition(SourceTag->isCompleteDefinition());
321    return true;
322  });
323}
324
325void ExternalASTMerger::CompleteType(ObjCInterfaceDecl *Interface) {
326  assert(Interface->hasExternalLexicalStorage());
327  ForEachMatchingDC(
328      Interface, [&](ASTImporter &Forward, ASTImporter &Reverse,
329                     Source<const DeclContext *> SourceDC) -> bool {
330        auto *SourceInterface = const_cast<ObjCInterfaceDecl *>(
331            cast<ObjCInterfaceDecl>(SourceDC.get()));
332        if (SourceInterface->hasExternalLexicalStorage())
333          SourceInterface->getASTContext().getExternalSource()->CompleteType(
334              SourceInterface);
335        if (!SourceInterface->getDefinition())
336          return false;
337        Forward.MapImported(SourceInterface, Interface);
338        if (llvm::Error Err = Forward.ImportDefinition(SourceInterface))
339          llvm::consumeError(std::move(Err));
340        return true;
341      });
342}
343
344bool ExternalASTMerger::CanComplete(DeclContext *Interface) {
345  assert(Interface->hasExternalLexicalStorage() ||
346         Interface->hasExternalVisibleStorage());
347  bool FoundMatchingDC = false;
348  ForEachMatchingDC(Interface,
349                    [&](ASTImporter &Forward, ASTImporter &Reverse,
350                        Source<const DeclContext *> SourceDC) -> bool {
351                      FoundMatchingDC = true;
352                      return true;
353                    });
354  return FoundMatchingDC;
355}
356
357namespace {
358bool IsSameDC(const DeclContext *D1, const DeclContext *D2) {
359  if (isa<ObjCContainerDecl>(D1) && isa<ObjCContainerDecl>(D2))
360    return true; // There are many cases where Objective-C is ambiguous.
361  if (auto *T1 = dyn_cast<TagDecl>(D1))
362    if (auto *T2 = dyn_cast<TagDecl>(D2))
363      if (T1->getFirstDecl() == T2->getFirstDecl())
364        return true;
365  return D1 == D2 || D1 == CanonicalizeDC(D2);
366}
367}
368
369void ExternalASTMerger::MaybeRecordOrigin(const DeclContext *ToDC,
370                                          DCOrigin Origin) {
371  LazyASTImporter &Importer = LazyImporterForOrigin(*this, *Origin.AST);
372  ASTImporter &Reverse = Importer.GetReverse();
373  Source<const DeclContext *> FoundFromDC =
374      LookupSameContext(Origin.AST->getTranslationUnitDecl(), ToDC, Reverse);
375  const bool DoRecord = !FoundFromDC || !IsSameDC(FoundFromDC.get(), Origin.DC);
376  if (DoRecord)
377    RecordOriginImpl(ToDC, Origin, Importer);
378  if (LoggingEnabled())
379    logs() << "(ExternalASTMerger*)" << (void*)this
380             << (DoRecord ? " decided " : " decided NOT")
381             << " to record origin (DeclContext*)" << (void*)Origin.DC
382             << ", (ASTContext*)" << (void*)&Origin.AST
383             << "\n";
384}
385
386void ExternalASTMerger::ForceRecordOrigin(const DeclContext *ToDC,
387                                          DCOrigin Origin) {
388  RecordOriginImpl(ToDC, Origin, ImporterForOrigin(*Origin.AST));
389}
390
391void ExternalASTMerger::RecordOriginImpl(const DeclContext *ToDC, DCOrigin Origin,
392                                         ASTImporter &Importer) {
393  Origins[ToDC] = Origin;
394  Importer.ASTImporter::MapImported(cast<Decl>(Origin.DC), const_cast<Decl*>(cast<Decl>(ToDC)));
395}
396
397ExternalASTMerger::ExternalASTMerger(const ImporterTarget &Target,
398                                     llvm::ArrayRef<ImporterSource> Sources) : LogStream(&llvm::nulls()), Target(Target) {
399  SharedState = std::make_shared<ASTImporterSharedState>(
400      *Target.AST.getTranslationUnitDecl());
401  AddSources(Sources);
402}
403
404Decl *ExternalASTMerger::FindOriginalDecl(Decl *D) {
405  assert(&D->getASTContext() == &Target.AST);
406  for (const auto &I : Importers)
407    if (auto Result = I->GetOriginalDecl(D))
408      return Result;
409  return nullptr;
410}
411
412void ExternalASTMerger::AddSources(llvm::ArrayRef<ImporterSource> Sources) {
413  for (const ImporterSource &S : Sources) {
414    assert(&S.getASTContext() != &Target.AST);
415    // Check that the associated merger actually imports into the source AST.
416    assert(!S.getMerger() || &S.getMerger()->Target.AST == &S.getASTContext());
417    Importers.push_back(std::make_unique<LazyASTImporter>(
418        *this, Target.AST, Target.FM, S, SharedState));
419  }
420}
421
422void ExternalASTMerger::RemoveSources(llvm::ArrayRef<ImporterSource> Sources) {
423  if (LoggingEnabled())
424    for (const ImporterSource &S : Sources)
425      logs() << "(ExternalASTMerger*)" << (void *)this
426             << " removing source (ASTContext*)" << (void *)&S.getASTContext()
427             << "\n";
428  llvm::erase_if(Importers,
429                 [&Sources](std::unique_ptr<ASTImporter> &Importer) -> bool {
430                   for (const ImporterSource &S : Sources) {
431                     if (&Importer->getFromContext() == &S.getASTContext())
432                       return true;
433                   }
434                   return false;
435                 });
436  for (OriginMap::iterator OI = Origins.begin(), OE = Origins.end(); OI != OE; ) {
437    std::pair<const DeclContext *, DCOrigin> Origin = *OI;
438    bool Erase = false;
439    for (const ImporterSource &S : Sources) {
440      if (&S.getASTContext() == Origin.second.AST) {
441        Erase = true;
442        break;
443      }
444    }
445    if (Erase)
446      OI = Origins.erase(OI);
447    else
448      ++OI;
449  }
450}
451
452template <typename DeclTy>
453static bool importSpecializations(DeclTy *D, ASTImporter *Importer) {
454  for (auto *Spec : D->specializations()) {
455    auto ImportedSpecOrError = Importer->Import(Spec);
456    if (!ImportedSpecOrError) {
457      llvm::consumeError(ImportedSpecOrError.takeError());
458      return true;
459    }
460  }
461  return false;
462}
463
464/// Imports specializations from template declarations that can be specialized.
465static bool importSpecializationsIfNeeded(Decl *D, ASTImporter *Importer) {
466  if (!isa<TemplateDecl>(D))
467    return false;
468  if (auto *FunctionTD = dyn_cast<FunctionTemplateDecl>(D))
469    return importSpecializations(FunctionTD, Importer);
470  else if (auto *ClassTD = dyn_cast<ClassTemplateDecl>(D))
471    return importSpecializations(ClassTD, Importer);
472  else if (auto *VarTD = dyn_cast<VarTemplateDecl>(D))
473    return importSpecializations(VarTD, Importer);
474  return false;
475}
476
477bool ExternalASTMerger::FindExternalVisibleDeclsByName(const DeclContext *DC,
478                                                       DeclarationName Name) {
479  llvm::SmallVector<NamedDecl *, 1> Decls;
480  llvm::SmallVector<Candidate, 4> Candidates;
481
482  auto FilterFoundDecl = [&Candidates](const Candidate &C) {
483   if (!HasDeclOfSameType(Candidates, C))
484     Candidates.push_back(C);
485  };
486
487  ForEachMatchingDC(DC,
488                    [&](ASTImporter &Forward, ASTImporter &Reverse,
489                        Source<const DeclContext *> SourceDC) -> bool {
490                      auto FromNameOrErr = Reverse.Import(Name);
491                      if (!FromNameOrErr) {
492                        llvm::consumeError(FromNameOrErr.takeError());
493                        return false;
494                      }
495                      DeclContextLookupResult Result =
496                          SourceDC.get()->lookup(*FromNameOrErr);
497                      for (NamedDecl *FromD : Result) {
498                        FilterFoundDecl(std::make_pair(FromD, &Forward));
499                      }
500                      return false;
501                    });
502
503  if (Candidates.empty())
504    return false;
505
506  Decls.reserve(Candidates.size());
507  for (const Candidate &C : Candidates) {
508    Decl *LookupRes = C.first.get();
509    ASTImporter *Importer = C.second;
510    auto NDOrErr = Importer->Import(LookupRes);
511    NamedDecl *ND = cast<NamedDecl>(llvm::cantFail(std::move(NDOrErr)));
512    assert(ND);
513    // If we don't import specialization, they are not available via lookup
514    // because the lookup result is imported TemplateDecl and it does not
515    // reference its specializations until they are imported explicitly.
516    bool IsSpecImportFailed =
517        importSpecializationsIfNeeded(LookupRes, Importer);
518    assert(!IsSpecImportFailed);
519    (void)IsSpecImportFailed;
520    Decls.push_back(ND);
521  }
522  SetExternalVisibleDeclsForName(DC, Name, Decls);
523  return true;
524}
525
526void ExternalASTMerger::FindExternalLexicalDecls(
527    const DeclContext *DC, llvm::function_ref<bool(Decl::Kind)> IsKindWeWant,
528    SmallVectorImpl<Decl *> &Result) {
529  ForEachMatchingDC(DC, [&](ASTImporter &Forward, ASTImporter &Reverse,
530                            Source<const DeclContext *> SourceDC) -> bool {
531    for (const Decl *SourceDecl : SourceDC.get()->decls()) {
532      if (IsKindWeWant(SourceDecl->getKind())) {
533        auto ImportedDeclOrErr = Forward.Import(SourceDecl);
534        if (ImportedDeclOrErr)
535          assert(!(*ImportedDeclOrErr) ||
536                 IsSameDC((*ImportedDeclOrErr)->getDeclContext(), DC));
537        else
538          llvm::consumeError(ImportedDeclOrErr.takeError());
539      }
540    }
541    return false;
542  });
543}
544
545