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

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