Add support for remembering origins to ExternalASTMerger

[spyffe]

Summary

ExternalASTMerger has hitherto relied on being able to look up any Decl through its named DeclContext chain. This works for many cases, but causes problems for function-local structs, which cannot be looked up in their containing FunctionDecl. An example case is

void f() {
  { struct S { int a; }; }
  { struct S { bool b; }; }
}

It is not possible to lookup either of the two Ses individually (or even to provide enough information to disambiguate) after parsing is over; and there is typically no need to, since they are invisible to the outside world.

However, ExternalASTMerger needs to be able to complete either S on demand. This led to an XFAIL on test/Import/local-struct, which this patch removes. The way the patch works is:

• It defines a new data structure, ExternalASTMerger::OriginMap, which clients are expected to maintain (default-constructing if the origin does not have an ExternalASTMerger servicing it)
• As DeclContexts are imported, if they cannot be looked up by name they are placed in the OriginMap. This allows ExternalASTMerger to complete them later if necessary.
• As DeclContexts are imported from an origin that already has its own OriginMap, the origins are forwarded – but only for those DeclContexts that are actually used. This keeps the amount of stored data minimal.

[spyffe]

Updated the patch to eliminate the need to pass in an OriginMap for the target. The OriginMap can be extracted afterward, and merged by other algorithms if necessary.

[spyffe]

Updated the patch to make it possible for external clients to record the origins of types manually, a requirement for LLDB.

[spyffe]

Added more tests, and added an option to clang-import-test to actually use the origin-forwarding code. Also fixed some errors in CompleteType that were caught by these new tests.

[spyffe]

Removed unnecessary code and improved code coverage. Also made a few operational changes:

• In initial lookup, accept forward declarations. They can be completed later.
• When doing lookup in a DeclContext, only look at source DeclContexts of the same type.
• Assume that only Decls with hasExternalLexicalStorage are actually completed, saving runtime and simplifying the code. Fixed one case in Sema where this rule was violated.

[spyffe]

Added DEBUG_PRINTF code to enable introspection into what's happening.

[bruno]

Hi Sean,

Thanks for making this functionality available in clang. Comments below.

Can you please add cfe-commits to the review for the next round?

include/clang/AST/ExternalASTMerger.h

36–37

Please add a comment explaining what Origins means and what it's used for.

50

Cool, I like these abstraction more than ImporterEndpoint. Please add comments explaining what ImporterTarget and ImporterSource represent in this context.

lib/AST/ExternalASTMerger.cpp

20

This seems brittle. Maybe hide this logic behind a variable that can be setup through clang-importer-test invocation by passing down a flag? Another solution is to hide users on dump functions, along the line of AST dumpers, etc.

34–35

Please add a comment explaining what do you mean by canonicalization here.

61

Why is it best to rely on the Origins map?

80

Add some comments on why you need a LazyASTImporter, so users know what to expect. Is LazyASTImporter expected to have other users outside this in the future? I wonder if it's worth to have this in ExternalASTMerger.h or any other place.

82

Odd identation here.

86

merger -> Merger

94

Please add a comment explaining what this method does.

96

This doesn't seem to be clang-formatted.

101

Same here!

104

Same here! And all the other places.

124

auto SourceDC -> auto *SourceDC

214

What's the deal with this commented out snippet?

224

auto T1 -> auto *T1

225

auto T2 -> auto *T2, please also fix other places with * or & where appropriate.

225

This is an example of where having a variable for conditionally printing extra information becomes handy.

248

No need for curly braces here.

[spyffe]

Updated to reflect Bruno's suggestions.

• Commented ExternalASTMerger.h extensively.
• Refactored the log into a pluggable raw_ostream that defaults to llvm::nulls().
• Added comments per Bruno's requests
• Fixed some indentation
• Fixed some variable names and auto [*&] s
• Removed some commented-out code
• Cleaned up some curly braces

[bruno]

Thanks for the additional docs! More comments below.

lib/AST/ExternalASTMerger.cpp

126

Can you conditionalize the logging?

136

Same here.

144

Same here.

210

Same here.

242

Ditto

248

Ditto

tools/clang-import-test/clang-import-test.cpp

247

Can you also add a brief documentation for this one?

257

No need for the else here.

261

No need for curly braces here.

318

No need for the else here.

325

No need for curly braces here.

335

No need for the else here.

347

No need for braces in this entire block

351

No need for the else here.

[spyffe]

At @bruno 's request, abandoning this revision in favor of the updated https://reviews.llvm.org/D38208.
That revision has all the changes requested.

include/clang/AST/ExternalASTMerger.h

 
 class ExternalASTMerger : public ExternalASTSource {
 public:
   struct ImporterPair {
     std::unique_ptr<ASTImporter> Forward;
     std::unique_ptr<ASTImporter> Reverse;
   };
 
+  struct DCOrigin {
+    DeclContext *DC;
+    ASTContext *AST;
+  };
+
+  typedef llvm::DenseMap<const DeclContext *, DCOrigin> OriginMap;
 private:
   std::vector<ImporterPair> Importers;
+  OriginMap Origins;
 
 public:
   struct ImporterEndpoint {
     ASTContext &AST;
     FileManager &FM;
+    OriginMap &OM;
   };
   ExternalASTMerger(const ImporterEndpoint &Target,
                     llvm::ArrayRef<ImporterEndpoint> Sources);
 
   bool FindExternalVisibleDeclsByName(const DeclContext *DC,
                                       DeclarationName Name) override;
 
   void
   FindExternalLexicalDecls(const DeclContext *DC,
                            llvm::function_ref<bool(Decl::Kind)> IsKindWeWant,
                            SmallVectorImpl<Decl *> &Result) override;
+
+  const OriginMap &GetOrigins() { return Origins; }
 };
 
 } // end namespace clang
 
 #endif

lib/AST/ExternalASTMerger.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/ExternalASTMerger.h"
 
 using namespace clang;
 
 namespace {
 
 template <typename T> struct Source {
   T t;
   Source(T t) : t(t) {}
   operator T() { return t; }
   template <typename U = T> U &get() { return t; }
   template <typename U = T> const U &get() const { return t; }
   template <typename U> operator Source<U>() { return Source<U>(t); }
 };
 
 typedef std::pair<Source<NamedDecl *>, ASTImporter *> Candidate;
 
-class LazyASTImporter : public ASTImporter {
-public:
-  LazyASTImporter(ASTContext &ToContext, FileManager &ToFileManager,
-                  ASTContext &FromContext, FileManager &FromFileManager)
-      : ASTImporter(ToContext, ToFileManager, FromContext, FromFileManager,
-                    /*MinimalImport=*/true) {}
-  Decl *Imported(Decl *From, Decl *To) override {
-    if (auto ToTag = dyn_cast<TagDecl>(To)) {
-      ToTag->setHasExternalLexicalStorage();
-      ToTag->setMustBuildLookupTable();
-    } else if (auto ToNamespace = dyn_cast<NamespaceDecl>(To)) {
-      ToNamespace->setHasExternalVisibleStorage();
-    } else if (auto ToContainer = dyn_cast<ObjCContainerDecl>(To)) {
-      ToContainer->setHasExternalLexicalStorage();
-      ToContainer->setMustBuildLookupTable();
-    }
-    return ASTImporter::Imported(From, To);
-  }
-};
-
 Source<const DeclContext *>
 LookupSameContext(Source<TranslationUnitDecl *> SourceTU, const DeclContext *DC,
                   ASTImporter &ReverseImporter) {
   if (DC->isTranslationUnit()) {
     return SourceTU;
   }
   Source<const DeclContext *> SourceParentDC =
       LookupSameContext(SourceTU, DC->getParent(), ReverseImporter);
   if (!SourceParentDC) {
     // If we couldn't find the parent DC in this TranslationUnit, give up.
     return nullptr;
   }
   auto ND = cast<NamedDecl>(DC);
   DeclarationName Name = ND->getDeclName();
   Source<DeclarationName> SourceName = ReverseImporter.Import(Name);
   DeclContext::lookup_result SearchResult =
       SourceParentDC.get()->lookup(SourceName.get());
   size_t SearchResultSize = SearchResult.size();
-  // Handle multiple candidates once we have a test for it.
-  // This may turn up when we import template specializations correctly.
-  assert(SearchResultSize < 2);
-  if (SearchResultSize == 0) {
-    // couldn't find the name, so we have to give up
+  if (SearchResultSize == 0 || SearchResultSize > 1) {
+    // There are two cases here.  First, we might not find the name.
+    // We might also find multiple copies, in which case we have no
+    // guarantee that the one we wanted is the one we pick.  (E.g.,
+    // if we have two specializations of the same templae it is
+    // very hard to determine which is the one you want.)
+    //
+    // Since we have the Origins map, the most reliable solution here
+    // is to rely on that and give up on being able to find better
+    // versios elsewhere.
     return nullptr;
   } else {
     NamedDecl *SearchResultDecl = SearchResult[0];
-    return dyn_cast<DeclContext>(SearchResultDecl);
+    if (isa<DeclContext>(SearchResultDecl))
+      return cast<DeclContext>(SearchResultDecl)->getPrimaryContext();
+    else
+      return nullptr; // This type of lookup is unsupported
   }
 }
 
 bool IsForwardDeclaration(Decl *D) {
   if (auto TD = dyn_cast<TagDecl>(D)) {
     return !TD->isThisDeclarationADefinition();
   } else if (auto FD = dyn_cast<FunctionDecl>(D)) {
     return !FD->isThisDeclarationADefinition();
   } else if (auto OID = dyn_cast<ObjCInterfaceDecl>(D)) {
-     return OID->isThisDeclarationADefinition();
   } else {
     return false;
   }
 }
 
+struct UnownedImporterPair {
+  ASTImporter *Forward = nullptr;
+  ASTImporter *Reverse = nullptr;
+
+  UnownedImporterPair(const ExternalASTMerger::ImporterPair &Pair)
+      : Forward(Pair.Forward.get()), Reverse(Pair.Reverse.get()) {}
+  UnownedImporterPair() {}
+
+  bool IsValid() { return Forward && Reverse; }
+};
+
+UnownedImporterPair
+ImportersForOrigin(llvm::ArrayRef<ExternalASTMerger::ImporterPair> Importers,
+                   ASTContext &OriginContext) {
+  for (const ExternalASTMerger::ImporterPair &IP : Importers) {
+    if (&IP.Forward->getFromContext() == &OriginContext)
+      return UnownedImporterPair(IP);
+  }
+  return {};
+}
+
 template <typename CallbackType>
 void ForEachMatchingDC(
-    const DeclContext *DC,
+    const DeclContext *DC, ExternalASTMerger::OriginMap &Origins,
     llvm::ArrayRef<ExternalASTMerger::ImporterPair> Importers,
     CallbackType Callback) {
+  if (Origins.count(DC)) {
+    ExternalASTMerger::DCOrigin Origin = Origins[DC];
+    UnownedImporterPair IP = ImportersForOrigin(Importers, *Origin.AST);
+    assert(IP.IsValid() && "We shoud have an importer for this origin!");
+    Callback(*IP.Forward, *IP.Reverse, Origin.DC);
+  } else {
+    bool DidCallback = false;
     for (const ExternalASTMerger::ImporterPair &IP : Importers) {
       Source<TranslationUnitDecl *> SourceTU =
           IP.Forward->getFromContext().getTranslationUnitDecl();
-    if (auto SourceDC = LookupSameContext(SourceTU, DC, *IP.Reverse))
-      Callback(IP, SourceDC);
+      if (auto SourceDC = LookupSameContext(SourceTU, DC, *IP.Reverse)) {
+        DidCallback = true;
+        Callback(*IP.Forward, *IP.Reverse, SourceDC);
+      }
+    }
+    assert(DidCallback && "Couldn't find a source context matching our DC");
   }
 }
 
 bool HasDeclOfSameType(llvm::ArrayRef<Candidate> Decls, const Candidate &C) {
   return llvm::any_of(Decls, [&](const Candidate &D) {
     return C.first.get()->getKind() == D.first.get()->getKind();
   });
 }
+
+class LazyASTImporter : public ASTImporter {
+private:
+  ExternalASTMerger::OriginMap *Origins;
+  ExternalASTMerger::OriginMap *FromOrigins;
+  ASTImporter *Reverse;
+
+public:
+  LazyASTImporter(ASTContext &ToContext, FileManager &ToFileManager,
+                  ASTContext &FromContext, FileManager &FromFileManager,
+                  ExternalASTMerger::OriginMap &_Origins,
+                  ExternalASTMerger::OriginMap &_FromOrigins)
+      : ASTImporter(ToContext, ToFileManager, FromContext, FromFileManager,
+                    /*MinimalImport=*/true),
+        Origins(&_Origins), FromOrigins(&_FromOrigins) {}
+  Decl *Imported(Decl *From, Decl *To) override {
+    assert(Origins && Reverse && "Must initialize Origins and Reverse!");
+    if (auto *ToDC = dyn_cast<DeclContext>(To)) {
+      Source<DeclContext *> FromDC(
+          cast<DeclContext>(From)->getPrimaryContext());
+      if (FromOrigins->count(FromDC)) {
+        (*Origins)[ToDC] = (*FromOrigins)[FromDC];
+      }
+      Source<const DeclContext *> FoundFromDC = LookupSameContext(
+          getFromContext().getTranslationUnitDecl(), ToDC, *Reverse);
+      if (FoundFromDC) {
+        assert(FoundFromDC == FromDC && "Found a different FromDC!");
+      } else {
+        (*Origins)[ToDC] = {FromDC, &getFromContext()};
+      }
+    }
+    if (auto ToTag = dyn_cast<TagDecl>(To)) {
+      ToTag->setHasExternalLexicalStorage();
+      ToTag->setMustBuildLookupTable();
+    } else if (auto ToNamespace = dyn_cast<NamespaceDecl>(To)) {
+      ToNamespace->setHasExternalVisibleStorage();
+    } else if (auto ToContainer = dyn_cast<ObjCContainerDecl>(To)) {
+      ToContainer->setHasExternalLexicalStorage();
+      ToContainer->setMustBuildLookupTable();
+    }
+    return ASTImporter::Imported(From, To);
+  }
+  void InstallReverse(ASTImporter *_Reverse) { Reverse = _Reverse; }
+};
+
 } // end namespace
 
 ExternalASTMerger::ExternalASTMerger(const ImporterEndpoint &Target,
                                      llvm::ArrayRef<ImporterEndpoint> Sources) {
   for (const ImporterEndpoint &S : Sources) {
     Importers.push_back(
-        {llvm::make_unique<LazyASTImporter>(Target.AST, Target.FM, S.AST, S.FM),
+        {llvm::make_unique<LazyASTImporter>(Target.AST, Target.FM, S.AST, S.FM,
+                                            Origins, S.OM),
          llvm::make_unique<ASTImporter>(S.AST, S.FM, Target.AST, Target.FM,
                                         /*MinimalImport=*/true)});
+    static_cast<LazyASTImporter *>(Importers.back().Forward.get())
+        ->InstallReverse(Importers.back().Reverse.get());
   }
 }
 
 bool ExternalASTMerger::FindExternalVisibleDeclsByName(const DeclContext *DC,
                                                        DeclarationName Name) {
   llvm::SmallVector<NamedDecl *, 1> Decls;
   llvm::SmallVector<Candidate, 4> CompleteDecls;
   llvm::SmallVector<Candidate, 4> ForwardDecls;
 
   auto FilterFoundDecl = [&CompleteDecls, &ForwardDecls](const Candidate &C) {
     if (IsForwardDeclaration(C.first.get())) {
       if (!HasDeclOfSameType(ForwardDecls, C)) {
         ForwardDecls.push_back(C);
       }
     } else {
       CompleteDecls.push_back(C);
     }
   };
 
   ForEachMatchingDC(
-      DC, Importers,
-      [&](const ImporterPair &IP, Source<const DeclContext *> SourceDC) {
-        DeclarationName FromName = IP.Reverse->Import(Name);
+      DC, Origins, Importers, [&](ASTImporter &Forward, ASTImporter &Reverse,
+                                  Source<const DeclContext *> SourceDC) {
+        DeclarationName FromName = Reverse.Import(Name);
         DeclContextLookupResult Result = SourceDC.get()->lookup(FromName);
         for (NamedDecl *FromD : Result) {
-          FilterFoundDecl(std::make_pair(FromD, IP.Forward.get()));
+          FilterFoundDecl(std::make_pair(FromD, &Forward));
         }
       });
 
   llvm::ArrayRef<Candidate> DeclsToReport =
       CompleteDecls.empty() ? ForwardDecls : CompleteDecls;
 
   if (DeclsToReport.empty()) {
     return false;
   }
 
   Decls.reserve(DeclsToReport.size());
   for (const Candidate &C : DeclsToReport) {
     NamedDecl *d = cast<NamedDecl>(C.second->Import(C.first.get()));
     assert(d);
     Decls.push_back(d);
   }
   SetExternalVisibleDeclsForName(DC, Name, Decls);
   return true;
 }
 
 void ExternalASTMerger::FindExternalLexicalDecls(
     const DeclContext *DC, llvm::function_ref<bool(Decl::Kind)> IsKindWeWant,
     SmallVectorImpl<Decl *> &Result) {
   ForEachMatchingDC(
-      DC, Importers,
-      [&](const ImporterPair &IP, Source<const DeclContext *> SourceDC) {
+      DC, Origins, Importers, [&](ASTImporter &Forward, ASTImporter &Reverse,
+                                  Source<const DeclContext *> SourceDC) {
         for (const Decl *SourceDecl : SourceDC.get()->decls()) {
           if (IsKindWeWant(SourceDecl->getKind())) {
-            Decl *ImportedDecl =
-                IP.Forward->Import(const_cast<Decl *>(SourceDecl));
+            Decl *ImportedDecl = Forward.Import(const_cast<Decl *>(SourceDecl));
             assert(ImportedDecl->getDeclContext() == DC);
             (void)ImportedDecl;
           }
         }
       });
 }
-

test/Import/local-struct/test.cpp

 // RUN: clang-import-test -dump-ir -import %S/Inputs/Callee.cpp -expression %s | FileCheck %s
-// XFAIL: *
 // CHECK: %struct.S = type { i
-// CHECK: %struct.S.0 = type { i1 }
+// CHECK: %struct.S.0 = type { i
 
 void foo() {
   return Bar().bar(3, true);
 }

tools/clang-import-test/clang-import-test.cpp

static llvm::cl::opt<std::string> Expression(
     llvm::cl::desc("Path to a file containing the expression to parse"));
 
 static llvm::cl::list<std::string>
     Imports("import", llvm::cl::ZeroOrMore,
             llvm::cl::desc("Path to a file containing declarations to import"));
 
 static llvm::cl::opt<bool>
     Direct("direct", llvm::cl::Optional,
-             llvm::cl::desc("Use the parsed declarations without indirection"));
 
 static llvm::cl::list<std::string>
     ClangArgs("Xcc", llvm::cl::ZeroOrMore,
               llvm::cl::desc("Argument to pass to the CompilerInvocation"),
               llvm::cl::CommaSeparated);
 
 static llvm::cl::opt<std::string>
     Input("x", llvm::cl::Optional,
           llvm::cl::desc("The language to parse (default: c++)"),
           llvm::cl::init("c++"));
 
-static llvm::cl::opt<bool>
-DumpAST("dump-ast", llvm::cl::init(false),
+static llvm::cl::opt<bool> DumpAST("dump-ast", llvm::cl::init(false),
                                    llvm::cl::desc("Dump combined AST"));
 
-static llvm::cl::opt<bool>
-DumpIR("dump-ir", llvm::cl::init(false),
+static llvm::cl::opt<bool> DumpIR("dump-ir", llvm::cl::init(false),
                                   llvm::cl::desc("Dump IR from final parse"));
 
 namespace init_convenience {
 class TestDiagnosticConsumer : public DiagnosticConsumer {
 private:
   std::unique_ptr<TextDiagnosticBuffer> Passthrough;
   const LangOptions *LangOpts = nullptr;
 
 public:
if (Info.hasSourceManager() && LangOpts) {
           llvm::errs() << Ref << '\n';
         }
       }
     }
     DiagnosticConsumer::HandleDiagnostic(DiagLevel, Info);
   }
 };
 
-std::unique_ptr<CompilerInstance>
-BuildCompilerInstance() {
+std::unique_ptr<CompilerInstance> BuildCompilerInstance() {
   auto Ins = llvm::make_unique<CompilerInstance>();
   auto DC = llvm::make_unique<TestDiagnosticConsumer>();
   const bool ShouldOwnClient = true;
   Ins->createDiagnostics(DC.release(), ShouldOwnClient);
 
   auto Inv = llvm::make_unique<CompilerInvocation>();
 
   std::vector<const char *> ClangArgv(ClangArgs.size());
std::unique_ptr<CodeGenerator> BuildCodeGen(CompilerInstance &CI,
   StringRef ModuleName("$__module");
   return std::unique_ptr<CodeGenerator>(CreateLLVMCodeGen(
       CI.getDiagnostics(), ModuleName, CI.getHeaderSearchOpts(),
       CI.getPreprocessorOpts(), CI.getCodeGenOpts(), LLVMCtx));
 }
 } // end namespace
 
 namespace {
- 
-void AddExternalSource(
-    CompilerInstance &CI,
-    llvm::ArrayRef<std::unique_ptr<CompilerInstance>> Imports) {
-  ExternalASTMerger::ImporterEndpoint Target({CI.getASTContext(), CI.getFileManager()});
+struct CIAndOrigins {
+  using OriginMap = clang::ExternalASTMerger::OriginMap;
+  std::unique_ptr<CompilerInstance> CI;
+  OriginMap OM;
+  ASTContext &getASTContext() { return CI->getASTContext(); }
+  FileManager &getFileManager() { return CI->getFileManager(); }
+  OriginMap &getOriginMap() { return OM; }
+  DiagnosticConsumer &getDiagnosticClient() {
+    return CI->getDiagnosticClient();
+  }
+  CompilerInstance &getCompilerInstance() { return *CI; }
+};
+
+void AddExternalSource(CIAndOrigins &CI,
+                       llvm::MutableArrayRef<CIAndOrigins> Imports) {
+  ExternalASTMerger::ImporterEndpoint Target(
+      {CI.getASTContext(), CI.getFileManager(), CI.getOriginMap()});
   llvm::SmallVector<ExternalASTMerger::ImporterEndpoint, 3> Sources;
-  for (const std::unique_ptr<CompilerInstance> &CI : Imports) {
-    Sources.push_back({CI->getASTContext(), CI->getFileManager()});
+  for (CIAndOrigins &CI : Imports) {
+    Sources.push_back(
+        {CI.getASTContext(), CI.getFileManager(), CI.getOriginMap()});
   }
   auto ES = llvm::make_unique<ExternalASTMerger>(Target, Sources);
   CI.getASTContext().setExternalSource(ES.release());
   CI.getASTContext().getTranslationUnitDecl()->setHasExternalVisibleStorage();
 }
 
-std::unique_ptr<CompilerInstance> BuildIndirect(std::unique_ptr<CompilerInstance> &CI) {
-  std::unique_ptr<CompilerInstance> IndirectCI =
-      init_convenience::BuildCompilerInstance();
+CIAndOrigins BuildIndirect(CIAndOrigins &CI) {
+  CIAndOrigins IndirectCI{init_convenience::BuildCompilerInstance(),
+                          ExternalASTMerger::OriginMap()};
   auto ST = llvm::make_unique<SelectorTable>();
   auto BC = llvm::make_unique<Builtin::Context>();
-  std::unique_ptr<ASTContext> AST =
-      init_convenience::BuildASTContext(*IndirectCI, *ST, *BC);
-  IndirectCI->setASTContext(AST.release());
-  AddExternalSource(*IndirectCI, CI);
+  std::unique_ptr<ASTContext> AST = init_convenience::BuildASTContext(
+      IndirectCI.getCompilerInstance(), *ST, *BC);
+  IndirectCI.getCompilerInstance().setASTContext(AST.release());
+  AddExternalSource(IndirectCI, CI);
   return IndirectCI;
 }
 
 llvm::Error ParseSource(const std::string &Path, CompilerInstance &CI,
                         ASTConsumer &Consumer) {
   SourceManager &SM = CI.getSourceManager();
   const FileEntry *FE = CI.getFileManager().getFile(Path);
   if (!FE) {
     return llvm::make_error<llvm::StringError>(
         llvm::Twine("Couldn't open ", Path), std::error_code());
   }
   SM.setMainFileID(SM.createFileID(FE, SourceLocation(), SrcMgr::C_User));
   ParseAST(CI.getPreprocessor(), &Consumer, CI.getASTContext());
   return llvm::Error::success();
 }
 
-llvm::Expected<std::unique_ptr<CompilerInstance>>
-Parse(const std::string &Path,
-      llvm::ArrayRef<std::unique_ptr<CompilerInstance>> Imports,
+llvm::Expected<CIAndOrigins> Parse(const std::string &Path,
+                                   llvm::MutableArrayRef<CIAndOrigins> Imports,
                                    bool ShouldDumpAST, bool ShouldDumpIR) {
-  std::unique_ptr<CompilerInstance> CI =
-      init_convenience::BuildCompilerInstance();
+  CIAndOrigins CI{init_convenience::BuildCompilerInstance(),
+                  ExternalASTMerger::OriginMap()};
   auto ST = llvm::make_unique<SelectorTable>();
   auto BC = llvm::make_unique<Builtin::Context>();
   std::unique_ptr<ASTContext> AST =
-      init_convenience::BuildASTContext(*CI, *ST, *BC);
-  CI->setASTContext(AST.release());
+      init_convenience::BuildASTContext(CI.getCompilerInstance(), *ST, *BC);
+  CI.getCompilerInstance().setASTContext(AST.release());
   if (Imports.size())
-    AddExternalSource(*CI, Imports);
+    AddExternalSource(CI, Imports);
 
   std::vector<std::unique_ptr<ASTConsumer>> ASTConsumers;
 
   auto LLVMCtx = llvm::make_unique<llvm::LLVMContext>();
-  ASTConsumers.push_back(init_convenience::BuildCodeGen(*CI, *LLVMCtx));
-  auto &CG = *static_cast<CodeGenerator*>(ASTConsumers.back().get());
+  ASTConsumers.push_back(
+      init_convenience::BuildCodeGen(CI.getCompilerInstance(), *LLVMCtx));
+  auto &CG = *static_cast<CodeGenerator *>(ASTConsumers.back().get());
 
   if (ShouldDumpAST)
     ASTConsumers.push_back(CreateASTDumper("", true, false, false));
 
-  CI->getDiagnosticClient().BeginSourceFile(CI->getLangOpts(),
-                                            &CI->getPreprocessor());
+  CI.getDiagnosticClient().BeginSourceFile(
+      CI.getCompilerInstance().getLangOpts(),
+      &CI.getCompilerInstance().getPreprocessor());
   MultiplexConsumer Consumers(std::move(ASTConsumers));
-  Consumers.Initialize(CI->getASTContext());
+  Consumers.Initialize(CI.getASTContext());
 
-  if (llvm::Error PE = ParseSource(Path, *CI, Consumers)) {
+  if (llvm::Error PE = ParseSource(Path, CI.getCompilerInstance(), Consumers)) {
     return std::move(PE);
   }
-  CI->getDiagnosticClient().EndSourceFile();
+  CI.getDiagnosticClient().EndSourceFile();
   if (ShouldDumpIR)
     CG.GetModule()->print(llvm::outs(), nullptr);
-  if (CI->getDiagnosticClient().getNumErrors()) {
+  if (CI.getDiagnosticClient().getNumErrors()) {
     return llvm::make_error<llvm::StringError>(
         "Errors occured while parsing the expression.", std::error_code());
   } else {
     return std::move(CI);
   }
 }
 
 } // end namespace
 
 int main(int argc, const char **argv) {
   const bool DisableCrashReporting = true;
   llvm::sys::PrintStackTraceOnErrorSignal(argv[0], DisableCrashReporting);
   llvm::cl::ParseCommandLineOptions(argc, argv);
-  std::vector<std::unique_ptr<CompilerInstance>> ImportCIs;
+  std::vector<CIAndOrigins> ImportCIs;
   for (auto I : Imports) {
-    llvm::Expected<std::unique_ptr<CompilerInstance>> ImportCI =
-      Parse(I, {}, false, false);
+    llvm::Expected<CIAndOrigins> ImportCI = Parse(I, {}, false, false);
     if (auto E = ImportCI.takeError()) {
       llvm::errs() << llvm::toString(std::move(E));
       exit(-1);
     } else {
       ImportCIs.push_back(std::move(*ImportCI));
     }
   }
-  std::vector<std::unique_ptr<CompilerInstance>> IndirectCIs;
+  std::vector<CIAndOrigins> IndirectCIs;
   if (!Direct) {
     for (auto &ImportCI : ImportCIs) {
-      std::unique_ptr<CompilerInstance> IndirectCI = BuildIndirect(ImportCI);
+      CIAndOrigins IndirectCI = BuildIndirect(ImportCI);
       IndirectCIs.push_back(std::move(IndirectCI));
     }
   }
-  llvm::Expected<std::unique_ptr<CompilerInstance>> ExpressionCI =
+  llvm::Expected<CIAndOrigins> ExpressionCI =
       Parse(Expression, Direct ? ImportCIs : IndirectCIs, DumpAST, DumpIR);
   if (auto E = ExpressionCI.takeError()) {
     llvm::errs() << llvm::toString(std::move(E));
     exit(-1);
   } else {
     return 0;
   }
 }
-