contrib/llvm/tools/clang/lib/AST/ExternalASTMerger.cpp

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