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

32–33

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

44

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

lib/AST/ExternalASTMerger.cpp

21

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.

35–36

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

69

Why is it best to rely on the Origins map?

82–121

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.

96

Please add a comment explaining what this method does.

98

This doesn't seem to be clang-formatted.

103

Same here!

106

Same here! And all the other places.

123

Odd identation here.

138

merger -> Merger

167

auto SourceDC -> auto *SourceDC

228

auto T1 -> auto *T1

229

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

249

What's the deal with this commented out snippet?

260

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

283

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

169

Can you conditionalize the logging?

179

Same here.

187

Same here.

258

Same here.

287

Ditto

293

Ditto

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

232

Can you also add a brief documentation for this one?

242

No need for the else here.

256

No need for curly braces here.

326

No need for the else here.

333

No need for curly braces here.

343

No need for the else here.

354–361

No need for braces in this entire block

365

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

 
 #include "clang/AST/ASTImporter.h"
 #include "clang/AST/ExternalASTSource.h"
 
 namespace clang {
 
 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;
+  typedef std::vector<std::unique_ptr<ASTImporter>> ImporterVector;
 private:
-  std::vector<ImporterPair> Importers;
+  ImporterVector Importers;
+  OriginMap Origins;
 
 public:
-  struct ImporterEndpoint {
+  struct ImporterTarget {
     ASTContext &AST;
     FileManager &FM;
   };
-  ExternalASTMerger(const ImporterEndpoint &Target,
-                    llvm::ArrayRef<ImporterEndpoint> Sources);
+  struct ImporterSource {
+    ASTContext &AST;
+    FileManager &FM;
+    const OriginMap &OM;
+  };
+  ExternalASTMerger(const ImporterTarget &Target,
+                    llvm::ArrayRef<ImporterSource> 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;
+
+  void CompleteType(clang::TagDecl *Tag) override;
+  void CompleteType(clang::ObjCInterfaceDecl *Interface) override;
+
+  void MaybeRecordOrigin(DeclContext *ToDC, DCOrigin Origin);
+  void ForceRecordOrigin(DeclContext *ToDC, DCOrigin Origin);
+  const OriginMap &GetOrigins() { return Origins; }
+
+  bool HasImporterForOrigin(ASTContext &OriginContext);
+  ASTImporter &ImporterForOrigin(ASTContext &OriginContext);
+private:
+  void RecordOriginImpl(DeclContext *ToDC, DCOrigin Origin,
+                                  ASTImporter &importer);
+  template <typename CallbackType>
+  void ForEachMatchingDC(const DeclContext *DC, CallbackType Callback);
 };
 
 } // end namespace clang
 
 #endif

lib/AST/ExternalASTMerger.cpp

 //===- ExternalASTMerger.cpp - Merging External AST Interface ---*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file implements the ExternalASTMerger, which vends a combination of
 //  ASTs from several different ASTContext/FileManager pairs
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
+#include "clang/AST/DeclCXX.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);
-  }
-};
+const DeclContext *CanonicalizeDC(const DeclContext *DC) {
+  if (isa<LinkageSpecDecl>(DC))
+    return DC->getRedeclContext();
+  return DC;
 
 Source<const DeclContext *>
 LookupSameContext(Source<TranslationUnitDecl *> SourceTU, const DeclContext *DC,
                   ASTImporter &ReverseImporter) {
+  DC = CanonicalizeDC(DC);
   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 template 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
+    // versions elsewhere.
     return nullptr;
   } else {
     NamedDecl *SearchResultDecl = SearchResult[0];
-    return dyn_cast<DeclContext>(SearchResultDecl);
+    if (isa<DeclContext>(SearchResultDecl) &&
+        SearchResultDecl->getKind() == DC->getDeclKind())
+      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 {
+class LazyASTImporter : public ASTImporter {
+private:
+  ExternalASTMerger &Parent;
+  ASTImporter Reverse;
+  const ExternalASTMerger::OriginMap &FromOrigins;
+public:
+  LazyASTImporter(ExternalASTMerger &_Parent, ASTContext &ToContext,
+                  FileManager &ToFileManager, ASTContext &FromContext,
+                  FileManager &FromFileManager,
+                  const ExternalASTMerger::OriginMap &_FromOrigins)
+      : ASTImporter(ToContext, ToFileManager, FromContext, FromFileManager,
+                    /*MinimalImport=*/true),
+        Parent(_Parent), Reverse(FromContext, FromFileManager, ToContext,
+                                 ToFileManager, /*MinimalImport=*/true), FromOrigins(_FromOrigins) {}
+  Decl *Imported(Decl *From, Decl *To) override {
+    if (auto *ToDC = dyn_cast<DeclContext>(To)) {
+      Source<DeclContext *> FromDC(
+          cast<DeclContext>(From)->getPrimaryContext());
+      if (FromOrigins.count(FromDC) &&
+          Parent.HasImporterForOrigin(*FromOrigins.lookup(FromDC).AST))
+        Parent.ForceRecordOrigin(ToDC, FromOrigins.lookup(FromDC));
+      else
+        Parent.MaybeRecordOrigin(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);
+  }
+  ASTImporter &GetReverse() { return Reverse; }
+};
+
+bool HasDeclOfSameType(llvm::ArrayRef<Candidate> Decls, const Candidate &C) {
+  if (isa<FunctionDecl>(C.first.get()))
     return false;
-  }
+  return llvm::any_of(Decls, [&](const Candidate &D) {    return C.first.get()->getKind() == D.first.get()->getKind();
+  });
+
+} // end namespace
+
+ASTImporter &ExternalASTMerger::ImporterForOrigin(ASTContext &OriginContext) {
+  for (const std::unique_ptr<ASTImporter> &I : Importers) {
+    if (&I->getFromContext() == &OriginContext)
+      return *I;
+  }
+  llvm_unreachable("We should have an importer for this origin!");
+}
+
+namespace {
+LazyASTImporter &LazyImporterForOrigin(ExternalASTMerger &merger,
+                                   ASTContext &OriginContext) {
+  return static_cast<LazyASTImporter &>(
+      merger.ImporterForOrigin(OriginContext));
+}
+}
+
+bool ExternalASTMerger::HasImporterForOrigin(ASTContext &OriginContext) {
+  for (const std::unique_ptr<ASTImporter> &I : Importers) {
+    if (&I->getFromContext() == &OriginContext)
+      return true;
+  }
+  return false;
 }
 
 template <typename CallbackType>
-void ForEachMatchingDC(
-    const DeclContext *DC,
-    llvm::ArrayRef<ExternalASTMerger::ImporterPair> Importers,
+void ExternalASTMerger::ForEachMatchingDC(const DeclContext *DC,
                                           CallbackType Callback) {
-  for (const ExternalASTMerger::ImporterPair &IP : Importers) {
+  if (Origins.count(DC)) {
+    ExternalASTMerger::DCOrigin Origin = Origins[DC];
+    LazyASTImporter &Importer = LazyImporterForOrigin(*this, *Origin.AST);
+    Callback(Importer, Importer.GetReverse(), Origin.DC);
+  } else {
+    bool DidCallback = false;
+    for (const std::unique_ptr<ASTImporter> &Importer : Importers) {
       Source<TranslationUnitDecl *> SourceTU =
-        IP.Forward->getFromContext().getTranslationUnitDecl();
-    if (auto SourceDC = LookupSameContext(SourceTU, DC, *IP.Reverse))
-      Callback(IP, SourceDC);
+          Importer->getFromContext().getTranslationUnitDecl();
+      ASTImporter &Reverse =
+          static_cast<LazyASTImporter *>(Importer.get())->GetReverse();
+      if (auto SourceDC = LookupSameContext(SourceTU, DC, Reverse)) {
+        DidCallback = true;
+        if (Callback(*Importer, Reverse, SourceDC))
+          break;
+      }
+    }
+    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();
+void ExternalASTMerger::CompleteType(clang::TagDecl *Tag) {
+  assert(Tag->hasExternalLexicalStorage());
+  ForEachMatchingDC(Tag, [&](ASTImporter &Forward, ASTImporter &Reverse,
+                             Source<const DeclContext *> SourceDC) -> bool {
+    auto *SourceTag = const_cast<TagDecl *>(cast<TagDecl>(SourceDC.get()));
+    if (SourceTag->hasExternalLexicalStorage())
+      SourceTag->getASTContext().getExternalSource()->CompleteType(SourceTag);
+    if (!SourceTag->getDefinition())
+      return false;
+    Forward.Imported(SourceTag, Tag);
+    Forward.ImportDefinition(SourceTag);
+    Tag->setCompleteDefinition(SourceTag->isCompleteDefinition());
+    return true;
   });
 }
-} // 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<ASTImporter>(S.AST, S.FM, Target.AST, Target.FM,
-                                        /*MinimalImport=*/true)});
+void ExternalASTMerger::CompleteType(clang::ObjCInterfaceDecl *Interface) {
+  assert(Interface->hasExternalLexicalStorage());
+  ForEachMatchingDC(Interface, [&](ASTImporter &Forward, ASTImporter &Reverse,
+                            Source<const DeclContext *> SourceDC) -> bool {
+    auto *SourceInterface = const_cast<ObjCInterfaceDecl *>(cast<ObjCInterfaceDecl>(SourceDC.get()));
+    if (SourceInterface->hasExternalLexicalStorage())
+      SourceInterface->getASTContext().getExternalSource()->CompleteType(SourceInterface);
+    if (!SourceInterface->getDefinition())
+      return false;
+    Forward.Imported(SourceInterface, Interface);
+    Forward.ImportDefinition(SourceInterface);
+    return true;
+  });
+}
+
+namespace {
+bool IsSameDC(const DeclContext *D1, const DeclContext *D2) {
+  if (isa<ObjCContainerDecl>(D1) && isa<ObjCContainerDecl>(D2))
+    return true; // There are many cases where Objective-C is ambiguous.
+  if (auto T1 = dyn_cast<TagDecl>(D1))
+    if (auto T2 = dyn_cast<TagDecl>(D2))
+      if (T1->getFirstDecl() == T2->getFirstDecl())
+        return true;
+  return D1 == D2 || D1 == CanonicalizeDC(D2);
+}
+}
+
+void ExternalASTMerger::MaybeRecordOrigin(DeclContext *ToDC, DCOrigin Origin) {
+  LazyASTImporter &Importer = LazyImporterForOrigin(*this, *Origin.AST);
+  ASTImporter &Reverse = Importer.GetReverse();
+  Source<const DeclContext *> FoundFromDC =
+      LookupSameContext(Origin.AST->getTranslationUnitDecl(), ToDC, Reverse);
+  if (!FoundFromDC || !IsSameDC(FoundFromDC.get(), Origin.DC)) {
+    RecordOriginImpl(ToDC, Origin, Importer);
+  }
+}
+
+void ExternalASTMerger::ForceRecordOrigin(DeclContext *ToDC,
+                                          DCOrigin Origin) {
+  RecordOriginImpl(ToDC, Origin, ImporterForOrigin(*Origin.AST));
+}
+
+void ExternalASTMerger::RecordOriginImpl(DeclContext *ToDC, DCOrigin Origin,
+                                         ASTImporter &Importer) {
+  Origins[ToDC] = Origin;
+  Importer.ASTImporter::Imported(cast<Decl>(Origin.DC), cast<Decl>(ToDC));
+}
+
+ExternalASTMerger::ExternalASTMerger(const ImporterTarget &Target,
+                                     llvm::ArrayRef<ImporterSource> Sources) {
+  for (const ImporterSource &S : Sources) {
+    Importers.push_back(llvm::make_unique<LazyASTImporter>(
+        *this, Target.AST, Target.FM, S.AST, S.FM, S.OM));
   }
 }
 
 bool ExternalASTMerger::FindExternalVisibleDeclsByName(const DeclContext *DC,
                                                        DeclarationName Name) {
   llvm::SmallVector<NamedDecl *, 1> Decls;
-  llvm::SmallVector<Candidate, 4> CompleteDecls;
-  llvm::SmallVector<Candidate, 4> ForwardDecls;
+  llvm::SmallVector<Candidate, 4> Candidates;
 
-  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);
-    }
+  auto FilterFoundDecl = [&Candidates](const Candidate &C) {
+   if (!HasDeclOfSameType(Candidates, C))
+     Candidates.push_back(C);
   };
 
-  ForEachMatchingDC(
-      DC, Importers,
-      [&](const ImporterPair &IP, Source<const DeclContext *> SourceDC) {
-        DeclarationName FromName = IP.Reverse->Import(Name);
-        DeclContextLookupResult Result = SourceDC.get()->lookup(FromName);
-        for (NamedDecl *FromD : Result) {
-          FilterFoundDecl(std::make_pair(FromD, IP.Forward.get()));
-        }
-      });
+  ForEachMatchingDC(DC, [&](ASTImporter &Forward, ASTImporter &Reverse,
+                            Source<const DeclContext *> SourceDC) -> bool {
+    DeclarationName FromName = Reverse.Import(Name);
+      FilterFoundDecl(std::make_pair(FromD, &Forward));
+    return false;
 
-  llvm::ArrayRef<Candidate> DeclsToReport =
-      CompleteDecls.empty() ? ForwardDecls : CompleteDecls;
-
-  if (DeclsToReport.empty()) {
+  if (Candidates.empty()) {
     return false;
   }
 
-  Decls.reserve(DeclsToReport.size());
-  for (const Candidate &C : DeclsToReport) {
+  Decls.reserve(Candidates.size());
+  for (const Candidate &C : Candidates) {
     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) {
-        for (const Decl *SourceDecl : SourceDC.get()->decls()) {
-          if (IsKindWeWant(SourceDecl->getKind())) {
-            Decl *ImportedDecl =
-                IP.Forward->Import(const_cast<Decl *>(SourceDecl));
-            assert(ImportedDecl->getDeclContext() == DC);
-            (void)ImportedDecl;
-          }
-        }
-      });
+  ForEachMatchingDC(DC, [&](ASTImporter &Forward, ASTImporter &Reverse,
+                            Source<const DeclContext *> SourceDC) -> bool {
+        Decl *ImportedDecl = Forward.Import(const_cast<Decl *>(SourceDecl));
+        assert(!ImportedDecl || IsSameDC(ImportedDecl->getDeclContext(), DC));
+    return false;
 }
-

lib/Sema/SemaType.cpp

         Tag ? static_cast<NamedDecl *>(Tag->getDecl()) : IFace->getDecl();
 
     // Avoid diagnosing invalid decls as incomplete.
     if (D->isInvalidDecl())
       return true;
 
     // Give the external AST source a chance to complete the type.
     if (auto *Source = Context.getExternalSource()) {
-      if (Tag)
-        Source->CompleteType(Tag->getDecl());
-      else
-        Source->CompleteType(IFace->getDecl());
-
+      if (Tag) {
+        TagDecl *TagD = Tag->getDecl();
+        if (TagD->hasExternalLexicalStorage())
+          Source->CompleteType(TagD);
+      } else {
+        ObjCInterfaceDecl *IFaceD = IFace->getDecl();
+        if (IFaceD->hasExternalLexicalStorage())
+          Source->CompleteType(IFace->getDecl());
+      }
       // If the external source completed the type, go through the motions
       // again to ensure we're allowed to use the completed type.
       if (!T->isIncompleteType())
         return RequireCompleteTypeImpl(Loc, T, Diagnoser);
     }
   }
 
   // If we have a class template specialization or a class member of a

test/Import/extern-c-function/Inputs/F.cpp

-void f(int arg) { }
+extern "C" {
+  void f(int arg);
+}

test/Import/extern-c-function/test.cpp

-// RUN: clang-import-test -import %S/Inputs/F1.c -import %S/Inputs/F2.c -expression %s
+// RUN: clang-import-test -import %S/Inputs/F.cpp -expression %s
 void expr() {
   f(2);
-  f("world");
-  S s;
-  f(s);
-}
+}

test/Import/forward-declared-objc-class/Inputs/S1.m

-struct S;
+@class MyClass;
 No newline at end of file

test/Import/forward-declared-objc-class/Inputs/S2.m

-struct S {
-  int a;
+@interface MyClass {
+  int j;
 };
++(MyClass*)fromInteger:(int)_j;
+-(int)getInteger;
+@end
 No newline at end of file

test/Import/forward-declared-objc-class/Inputs/S3.m

-struct S;
+@class MyClass;
 No newline at end of file

test/Import/forward-declared-objc-class/test.m

-// RUN: clang-import-test -import %S/Inputs/S1.c --import %S/Inputs/S2.c -expression %s
+// RUN: clang-import-test -x objective-c++ -import %S/Inputs/S1.m --import %S/Inputs/S2.m --import %S/Inputs/S3.m -expression %s
 void expr() {
-  struct S MyS;
-  MyS.a = 3;
+  MyClass *c = [MyClass fromInteger:3];
+  const int i = [c getInteger];
+  const int j = c->j;
 }

test/Import/forward-declared-struct/test.c

-// RUN: clang-import-test -import %S/Inputs/S1.c --import %S/Inputs/S2.c -expression %s
+// RUN: clang-import-test -import %S/Inputs/S1.c --import %S/Inputs/S2.c --import %S/Inputs/S3.c -expression %s
 void expr() {
   struct S MyS;
   MyS.a = 3;
 }

test/Import/local-struct-use-origins/test.cpp

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

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);
 }

test/Import/objc-definitions-in-expression/test.m

 // RUN: clang-import-test -x objective-c++ -import %S/Inputs/S.m -expression %s
+@class D;
+
+@interface B {
+  int x;
+  int y;
+}
+@end
+
+@interface D : B {
+  int z;
+}
+-(int)n;
+@end
+
 void expr() {
   C *c;
   int i = [c m];
+  D *d;
+  int j = [d n] + d->x;
 }

test/Import/struct-and-var/Inputs/S1.cpp

-class T;
-
-class S {
-  T *t;
-  int a;
-};
+int F;

test/Import/struct-and-var/Inputs/S2.cpp

-class U {
-  int b;
-};
-
-class T {
-  U u;
+struct F {
+  int a;
 };

test/Import/struct-and-var/test.cpp

 // RUN: clang-import-test --import %S/Inputs/S1.cpp --import %S/Inputs/S2.cpp -expression %s
 void expr() {
-  S MyS;
-  T MyT;
-  MyS.a = 3;
-  MyT.u.b = 2;
+  struct F f;
+  int x = f.a;
 }

test/Import/template/Inputs/T.cpp

 template <typename T> struct A {
-};
-
-template <> struct A<int> {
-  struct B {
-    int f;
-  };
-};
-
-template <> struct A<bool> {
   struct B {
-    int g;
+    T f;
   };
 };

test/Import/template/test.cpp

 // RUN: clang-import-test -import %S/Inputs/T.cpp -expression %s
-// XFAIL: *
 void expr() {
-  A<int>::B b1;
-  A<bool>::B b2;
-  b1.f + b2.g;
+  A<int>::B b;
 }

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::opt<bool>
+    UseOrigins("use-origins", llvm::cl::Optional,
+           llvm::cl::desc("Use DeclContext origin information for more accurate lookups"));  
+
 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()});
-  llvm::SmallVector<ExternalASTMerger::ImporterEndpoint, 3> Sources;
-  for (const std::unique_ptr<CompilerInstance> &CI : Imports) {
-    Sources.push_back({CI->getASTContext(), CI->getFileManager()});
+struct CIAndOrigins {
+  using OriginMap = clang::ExternalASTMerger::OriginMap;
+  std::unique_ptr<CompilerInstance> CI;
+
+  ASTContext &getASTContext() { return CI->getASTContext(); }
+  FileManager &getFileManager() { return CI->getFileManager(); }
+  const OriginMap &getOriginMap() {
+    static const OriginMap EmptyOriginMap;
+    if (ExternalASTSource *Source = CI->getASTContext().getExternalSource())
+      return static_cast<ExternalASTMerger *>(Source)->GetOrigins();
+    else
+      return EmptyOriginMap;
+  }
+  DiagnosticConsumer &getDiagnosticClient() {
+    return CI->getDiagnosticClient();
+  }
+  CompilerInstance &getCompilerInstance() { return *CI; }
+};
+
+void AddExternalSource(CIAndOrigins &CI,
+                       llvm::MutableArrayRef<CIAndOrigins> Imports) {
+  ExternalASTMerger::ImporterTarget Target(
+      {CI.getASTContext(), CI.getFileManager()});
+  llvm::SmallVector<ExternalASTMerger::ImporterSource, 3> Sources;
+  for (CIAndOrigins &Import : Imports) {
+    Sources.push_back(
+        {Import.getASTContext(), Import.getFileManager(), Import.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()};
   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()};
   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;
-  if (!Direct) {
+  std::vector<CIAndOrigins> IndirectCIs;
+  if (!Direct || UseOrigins) {
     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 =
-      Parse(Expression, Direct ? ImportCIs : IndirectCIs, DumpAST, DumpIR);
+  if (UseOrigins) {
+    for (auto &ImportCI : ImportCIs) {
+      IndirectCIs.push_back(std::move(ImportCI));
+    }
+  }
+  llvm::Expected<CIAndOrigins> ExpressionCI =
+      Parse(Expression, (Direct && !UseOrigins) ? ImportCIs : IndirectCIs,
+            DumpAST, DumpIR);
   if (auto E = ExpressionCI.takeError()) {
     llvm::errs() << llvm::toString(std::move(E));
     exit(-1);
   } else {
     return 0;
   }
 }
-