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/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