[ASTImporter] Add importer specific lookup

[martong]

Summary

There are certain cases when normal C/C++ lookup (localUncachedLookup)
does not find AST nodes. E.g.:

Example 1:

template <class T>
struct X {
  friend void foo(); // this is never found in the DC of the TU.
};

Example 2:

// The fwd decl to Foo is not found in the lookupPtr of the DC of the
// translation unit decl.
struct A { struct Foo *p; };

In these cases we create a new node instead of returning with the old one.
To fix it we create a new lookup table which holds every node and we are
not interested in any C++ specific visibility considerations.
Simply, we must know if there is an existing Decl in a given DC.

[martong]

Gentle Ping.

[martong]

Constructs like struct A { struct Foo *p; }; are very common in C projects. Since Foo as a forward decl cannot be found by normal lookup we need this patch in order to properly CTU analyze even a simple C project like tmux.

[a_sidorin]

Hi Gabor,

I think it is a good patch with a nice test set. There are some mine comments inline. I'd also like to have LLDB guys opinion on it.

lib/AST/ASTImporter.cpp

7605 ↗

(On Diff #171114)

It's better to make LookupTable an optional parameter of the previous ctor and remove this one.

7657 ↗

(On Diff #171114)

@shafik @jingham Could you please address this question?

lib/AST/ASTImporterLookupTable.cpp

52 ↗

(On Diff #171114)

// anonymous namespace or just // namespace.

84 ↗

(On Diff #171114)

Should we remove DC-related entry if it is empty after deletion?

95 ↗

(On Diff #171114)

Could you please add newlines after ifs?

121 ↗

(On Diff #171114)

1. StringRef
2. Do we need a space before newline?

122 ↗

(On Diff #171114)

Two spaces before "\n".

lib/CrossTU/CrossTranslationUnit.cpp

258 ↗

(On Diff #171114)

if (!LookupTable)
  LookupTable = llvm::make_unique<ASTImporterLookupTable>(*ToTU);

?

unittests/AST/ASTImporterTest.cpp

346 ↗

(On Diff #171114)

if (!LookupTablePtr) ...

3843 ↗

(On Diff #171114)

Redundant space after paren.

3845 ↗

(On Diff #171114)

Could you please explain what does this test do?

3889 ↗

(On Diff #171114)

Do we need break/early return here?

3930 ↗

(On Diff #171114)

This lambda is the same as in previous func so it's better to extract it into a helper.

4020 ↗

(On Diff #171114)

This line exceeds 80 chars.

[martong]

lib/AST/ASTImporter.cpp

7605 ↗

(On Diff #171114)

Okay, I have changed it to be a default initalized to nullptr parameter.

lib/AST/ASTImporterLookupTable.cpp

84 ↗

(On Diff #171114)

I don't think so.
The only place where we are going to use remove is in case we had an error during import (upcoming patch). Even if we had an error before, subsequent successfully imported Decls could be part of the same DC (so, chances are we would superfluously do a ping-pong of delete/create).

unittests/AST/ASTImporterTest.cpp

3845 ↗

(On Diff #171114)

Well, it makes sure that we can build a lookup table for an empty file without any *assertion*. We may have an assertion in the ctor during traversing the AST. I consider this the most basic use case as it tests only the constructor.
However, if you find it weird I can remove it.

3889 ↗

(On Diff #171114)

Yes, that's better to have.

3930 ↗

(On Diff #171114)

Good catch, thanks.

[martong]

• Address Alexei's comments

[a_sidorin]

Hi Gabor,
Here are some new comments.

lib/AST/ASTImporter.cpp

7658 ↗

(On Diff #175495)

Naming conventions require method names to start with a small letter.

lib/AST/ASTImporterLookupTable.cpp

121 ↗

(On Diff #171114)

Point 2 is still not addressed. We print a string ending with a space and then print a newline. I think we can remove the trailing space from both string literals.

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

12 ↗

(On Diff #175495)

It looks like the only change done to this file is including a header. Are there any related changes that should be added?

unittests/AST/ASTImporterTest.cpp

3933 ↗

(On Diff #175495)

return nullptr, Found is actually unused.

3845 ↗

(On Diff #171114)

Yes, I think it's better to remove it or check some invariants of an empty lookup table.

[martong]

lib/AST/ASTImporter.cpp

7658 ↗

(On Diff #175495)

Okay, I changed it. Unfortunately ASTImporter does not really follow the conventions. Most of the functions start with a capital letter, and some with a small case.
E.g.:

/// Retrieve the file manager that AST nodes are being imported from.
FileManager &getFromFileManager() const { return FromFileManager; }

/// Report a diagnostic in the "to" context.
DiagnosticBuilder ToDiag(SourceLocation Loc, unsigned DiagID);

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

12 ↗

(On Diff #175495)

Thank you, this is a good catch, I removed it.

unittests/AST/ASTImporterTest.cpp

3845 ↗

(On Diff #171114)

Ok, I removed it.

[martong]

• Address Alexei's comments
• Rename FindDeclsInToCtx to findDeclsInToCtx
• Remove superfluous spaces from stringliterals
• Remove unused header
• Remove empty test
• Return nullptr and FindInDeclListOfDC -> findInDeclListOfDC
• Use SmallSetVector instead of SmallPtrSet

[martong]

Hey Alexei,

Thank you again for your comments. I changed the code accordingly.

Also, I recognized that we should use a SmallSetVector instead of a SmallPtrSet, because the latter results unpredictable iteration (pointers may have different values with each run). Though SmallPtrSet is more powerful than SmallSetVector it makes it really hard to debug false positive ODR warnings from the ASTImporter, because the warning may appear in one run but may not appear in the subsequent run. We need an iteration order in the order of insertions and that is produced by SmallSetVector.

[a_sidorin]

Hi Gabor,
I think the code looks good. Thank you!

[martong]

• Rebase to master (trunk)

[riccibruno]

This is a perhaps a naive comment, but why is localUncachedLookup used
instead of noload_lookup ? There is a fixme dating from 2013 stating
that noload_lookup should be used instead.

[martong]

This is a perhaps a naive comment, but why is localUncachedLookup used
instead of noload_lookup ? There is a fixme dating from 2013 stating
that noload_lookup should be used instead.

This is not a naive question. I was wondering myself on the very same thing when I started working on the ASTImporter at 2017.
I think when noload_lookup was introduced the author of that function tried to replace localUncachedLookup in ASTImporter, but that broke some tests. The major difference between the two functions is that the latter can find declarations even if they are not stored in the LookupPtr. This is rather unusual from the C/C++ point of view of lookup, and not working in all cases (see the introduction of this patch). Ironically, I can't just get rid of localUncachedLookup because it would break some LLDB test cases.

[riccibruno]

In D53708#1332868, @martong wrote:

This is a perhaps a naive comment, but why is localUncachedLookup used
instead of noload_lookup ? There is a fixme dating from 2013 stating
that noload_lookup should be used instead.

This is not a naive question. I was wondering myself on the very same thing when I started working on the ASTImporter at 2017.
I think when noload_lookup was introduced the author of that function tried to replace localUncachedLookup in ASTImporter, but that broke some tests. The major difference between the two functions is that the latter can find declarations even if they are not stored in the LookupPtr. This is rather unusual from the C/C++ point of view of lookup, and not working in all cases (see the introduction of this patch). Ironically, I can't just get rid of localUncachedLookup because it would break some LLDB test cases.

Ah I think I understand. For my understanding (and please correct me if I am wrong here):

localUncachedLookup will first try to do a normal lookup, and if that fails it will try to look in the declarations in the declaration context.
Now some declarations (including declarations which are not NamedDecl and declarations which matches shouldBeHidden)
will not be added to the LookupPtr (via makeDeclVisibleInContextWithFlags) and so will not be found though the normal lookup mechanism. You therefore need to use localUncachedLookup to find these.

Does this make sense ?

[martong]

In D53708#1332922, @riccibruno wrote:

In D53708#1332868, @martong wrote:

This is a perhaps a naive comment, but why is localUncachedLookup used
instead of noload_lookup ? There is a fixme dating from 2013 stating
that noload_lookup should be used instead.

This is not a naive question. I was wondering myself on the very same thing when I started working on the ASTImporter at 2017.
I think when noload_lookup was introduced the author of that function tried to replace localUncachedLookup in ASTImporter, but that broke some tests. The major difference between the two functions is that the latter can find declarations even if they are not stored in the LookupPtr. This is rather unusual from the C/C++ point of view of lookup, and not working in all cases (see the introduction of this patch). Ironically, I can't just get rid of localUncachedLookup because it would break some LLDB test cases.

Ah I think I understand. For my understanding (and please correct me if I am wrong here):

localUncachedLookup will first try to do a normal lookup, and if that fails it will try to look in the declarations in the declaration context.
Now some declarations (including declarations which are not NamedDecl and declarations which matches shouldBeHidden)
will not be added to the LookupPtr (via makeDeclVisibleInContextWithFlags) and so will not be found though the normal lookup mechanism. You therefore need to use localUncachedLookup to find these.

Does this make sense ?

Exactly. And this seems to be an important feature in ASTImporter, because this makes it possible that we can chain into the redecl chain a newly imported AST node to existing and structurally equivalent nodes. (The existing nodes are found by the lookup and then we iterate over the lookup results searching for structurally equivalent ones.)

[riccibruno]

Exactly. And this seems to be an important feature in ASTImporter, because this makes it possible that we can chain into the redecl chain a newly imported AST node to existing and structurally equivalent > nodes. (The existing nodes are found by the lookup and then we iterate over the lookup results searching for structurally equivalent ones.)

I see. I am unfortunately not familiar at all with the ASTImporter, but thanks for clearing this up.

cfe/trunk/include/clang/AST/ASTImporter.h

 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Error.h"
 #include <utility>
 
 namespace clang {
 
 class ASTContext;
+class ASTImporterLookupTable;
 class CXXBaseSpecifier;
 class CXXCtorInitializer;
 class Decl;
 class DeclContext;
 class Expr;
 class FileManager;
 class NamedDecl;
 class Stmt;
class Attr;
   // previous decl and the next item is actually the previous item in the order
   // of source locations.  Thus, `Decl::redecls()` gives different lists for
   // the different entries in a given redecl chain.
   llvm::SmallVector<Decl*, 2> getCanonicalForwardRedeclChain(Decl* D);
 
   /// Imports selected nodes from one AST context into another context,
   /// merging AST nodes where appropriate.
   class ASTImporter {
+    friend class ASTNodeImporter;
   public:
     using NonEquivalentDeclSet = llvm::DenseSet<std::pair<Decl *, Decl *>>;
     using ImportedCXXBaseSpecifierMap =
         llvm::DenseMap<const CXXBaseSpecifier *, CXXBaseSpecifier *>;
 
   private:
+
+    /// Pointer to the import specific lookup table, which may be shared
+    /// amongst several ASTImporter objects.
+    /// This is an externally managed resource (and should exist during the
+    /// lifetime of the ASTImporter object)
+    /// If not set then the original C/C++ lookup is used.
+    ASTImporterLookupTable *LookupTable = nullptr;
+
     /// The contexts we're importing to and from.
     ASTContext &ToContext, &FromContext;
 
     /// The file managers we're importing to and from.
     FileManager &ToFileManager, &FromFileManager;
 
     /// Whether to perform a minimal import.
     bool Minimal;
private:
     ///  the "from" source manager to the corresponding CXXBasesSpecifier
     ///  in the "to" source manager.
     ImportedCXXBaseSpecifierMap ImportedCXXBaseSpecifiers;
 
     /// Declaration (from, to) pairs that are known not to be equivalent
     /// (which we have already complained about).
     NonEquivalentDeclSet NonEquivalentDecls;
 
+    using FoundDeclsTy = SmallVector<NamedDecl *, 2>;
+    FoundDeclsTy findDeclsInToCtx(DeclContext *DC, DeclarationName Name);
+
+    void AddToLookupTable(Decl *ToD);
+
   public:
-    /// Create a new AST importer.
-    ///
+
     /// \param ToContext The context we'll be importing into.
     ///
     /// \param ToFileManager The file manager we'll be importing into.
     ///
     /// \param FromContext The context we'll be importing from.
     ///
     /// \param FromFileManager The file manager we'll be importing into.
     ///
     /// \param MinimalImport If true, the importer will attempt to import
     /// as little as it can, e.g., by importing declarations as forward
     /// declarations that can be completed at a later point.
+    ///
+    /// \param LookupTable The importer specific lookup table which may be
+    /// shared amongst several ASTImporter objects.
+    /// If not set then the original C/C++ lookup is used.
     ASTImporter(ASTContext &ToContext, FileManager &ToFileManager,
                 ASTContext &FromContext, FileManager &FromFileManager,
-                bool MinimalImport);
+                bool MinimalImport,
+                ASTImporterLookupTable *LookupTable = nullptr);
 
     virtual ~ASTImporter();
 
     /// Whether the importer will perform a minimal import, creating
     /// to-be-completed forward declarations when possible.
     bool isMinimalImport() const { return Minimal; }
 
     /// \brief Import the given object, returns the result.

cfe/trunk/include/clang/AST/ASTImporterLookupTable.h

+//===- ASTImporterLookupTable.h - ASTImporter specific lookup--*- C++ -*---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the ASTImporterLookupTable class which implements a
+//  lookup procedure for the import mechanism.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_ASTIMPORTERLOOKUPTABLE_H
+#define LLVM_CLANG_AST_ASTIMPORTERLOOKUPTABLE_H
+
+#include "clang/AST/DeclBase.h" // lookup_result
+#include "clang/AST/DeclarationName.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SetVector.h"
+
+namespace clang {
+
+class ASTContext;
+class NamedDecl;
+class DeclContext;
+
+// There are certain cases when normal C/C++ lookup (localUncachedLookup)
+// does not find AST nodes. E.g.:
+// Example 1:
+//   template <class T>
+//   struct X {
+//     friend void foo(); // this is never found in the DC of the TU.
+//   };
+// Example 2:
+//   // The fwd decl to Foo is not found in the lookupPtr of the DC of the
+//   // translation unit decl.
+//   // Here we could find the node by doing a traverse throught the list of
+//   // the Decls in the DC, but that would not scale.
+//   struct A { struct Foo *p; };
+// This is a severe problem because the importer decides if it has to create a
+// new Decl or not based on the lookup results.
+// To overcome these cases we need an importer specific lookup table which
+// holds every node and we are not interested in any C/C++ specific visibility
+// considerations. Simply, we must know if there is an existing Decl in a
+// given DC. Once we found it then we can handle any visibility related tasks.
+class ASTImporterLookupTable {
+
+  // We store a list of declarations for each name.
+  // And we collect these lists for each DeclContext.
+  // We could have a flat map with (DeclContext, Name) tuple as key, but a two
+  // level map seems easier to handle.
+  using DeclList = llvm::SmallSetVector<NamedDecl *, 2>;
+  using NameMap = llvm::SmallDenseMap<DeclarationName, DeclList, 4>;
+  using DCMap = llvm::DenseMap<DeclContext *, NameMap>;
+
+  void add(DeclContext *DC, NamedDecl *ND);
+  void remove(DeclContext *DC, NamedDecl *ND);
+
+  DCMap LookupTable;
+
+public:
+  ASTImporterLookupTable(TranslationUnitDecl &TU);
+  void add(NamedDecl *ND);
+  void remove(NamedDecl *ND);
+  using LookupResult = DeclList;
+  LookupResult lookup(DeclContext *DC, DeclarationName Name) const;
+  void dump(DeclContext *DC) const;
+  void dump() const;
+};
+
+} // namespace clang
+
+#endif // LLVM_CLANG_AST_ASTIMPORTERLOOKUPTABLE_H

cfe/trunk/include/clang/CrossTU/CrossTranslationUnit.h

 //  This file provides an interface to load binary AST dumps on demand. This
 //  feature can be utilized for tools that require cross translation unit
 //  support.
 //
 //===----------------------------------------------------------------------===//
 #ifndef LLVM_CLANG_CROSSTU_CROSSTRANSLATIONUNIT_H
 #define LLVM_CLANG_CROSSTU_CROSSTRANSLATIONUNIT_H
 
+#include "clang/AST/ASTImporterLookupTable.h"
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/Error.h"
 
 namespace clang {
 class CompilerInstance;
public:
 
   /// Get a name to identify a function.
   static std::string getLookupName(const NamedDecl *ND);
 
   /// Emit diagnostics for the user for potential configuration errors.
   void emitCrossTUDiagnostics(const IndexError &IE);
 
 private:
+  void lazyInitLookupTable(TranslationUnitDecl *ToTU);
   ASTImporter &getOrCreateASTImporter(ASTContext &From);
   const FunctionDecl *findFunctionInDeclContext(const DeclContext *DC,
                                                 StringRef LookupFnName);
 
   llvm::StringMap<std::unique_ptr<clang::ASTUnit>> FileASTUnitMap;
   llvm::StringMap<clang::ASTUnit *> FunctionASTUnitMap;
   llvm::StringMap<std::string> FunctionFileMap;
   llvm::DenseMap<TranslationUnitDecl *, std::unique_ptr<ASTImporter>>
       ASTUnitImporterMap;
   CompilerInstance &CI;
   ASTContext &Context;
+  std::unique_ptr<ASTImporterLookupTable> LookupTable;
 };
 
 } // namespace cross_tu
 } // namespace clang
 
 #endif // LLVM_CLANG_CROSSTU_CROSSTRANSLATIONUNIT_H

cfe/trunk/lib/AST/ASTImporter.cpp

 //===- ASTImporter.cpp - Importing ASTs from other Contexts ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines the ASTImporter class which imports AST nodes from one
 //  context into another context.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ASTImporter.h"
+#include "clang/AST/ASTImporterLookupTable.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/ASTStructuralEquivalence.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclAccessPair.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclCXX.h"
namespace clang {
 
   void updateFlags(const Decl *From, Decl *To) {
     // Check if some flags or attrs are new in 'From' and copy into 'To'.
     // FIXME: Other flags or attrs?
     if (From->isUsed(false) && !To->isUsed(false))
       To->setIsUsed();
   }
 
-  Optional<unsigned> ASTImporter::getFieldIndex(Decl *F) {
-    assert(F && (isa<FieldDecl>(*F) || isa<IndirectFieldDecl>(*F)) &&
-        "Try to get field index for non-field.");
-
-    auto *Owner = dyn_cast<RecordDecl>(F->getDeclContext());
-    if (!Owner)
-      return None;
-
-    unsigned Index = 0;
-    for (const auto *D : Owner->decls()) {
-      if (D == F)
-        return Index;
-
-      if (isa<FieldDecl>(*D) || isa<IndirectFieldDecl>(*D))
-        ++Index;
-    }
-
-    llvm_unreachable("Field was not found in its parent context.");
-
-    return None;
-  }
-
   // FIXME: Temporary until every import returns Expected.
   template <>
   LLVM_NODISCARD Error
   ASTImporter::importInto(SourceLocation &To, const SourceLocation &From) {
     To = Import(From);
     if (From.isValid() && To.isInvalid())
         return llvm::make_error<ImportError>();
     return Error::success();
GetImportedOrCreateSpecialDecl(ToDeclT *&ToD, CreateFunT CreateFun,
       //if (Importer.getImportDeclErrorIfAny(FromD)) {
       //  ToD = nullptr;
       //  return true; // Already imported but with error.
       //}
       ToD = cast_or_null<ToDeclT>(Importer.GetAlreadyImportedOrNull(FromD));
       if (ToD)
         return true; // Already imported.
       ToD = CreateFun(std::forward<Args>(args)...);
+      // Keep track of imported Decls.
+      Importer.MapImported(FromD, ToD);
+      Importer.AddToLookupTable(ToD);
       InitializeImportedDecl(FromD, ToD);
       return false; // A new Decl is created.
     }
 
     void InitializeImportedDecl(Decl *FromD, Decl *ToD) {
-      Importer.MapImported(FromD, ToD);
       ToD->IdentifierNamespace = FromD->IdentifierNamespace;
       if (FromD->hasAttrs())
         for (const Attr *FromAttr : FromD->getAttrs())
           ToD->addAttr(Importer.Import(FromAttr));
       if (FromD->isUsed())
         ToD->setIsUsed();
       if (FromD->isImplicit())
         ToD->setImplicit();
if (!Name) {
     // namespace if we can.
     // FIXME: Not testable.
     if (auto *TU = dyn_cast<TranslationUnitDecl>(DC))
       MergeWithNamespace = TU->getAnonymousNamespace();
     else
       MergeWithNamespace = cast<NamespaceDecl>(DC)->getAnonymousNamespace();
   } else {
     SmallVector<NamedDecl *, 4> ConflictingDecls;
-    SmallVector<NamedDecl *, 2> FoundDecls;
-    DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+    auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
     for (auto *FoundDecl : FoundDecls) {
       if (!FoundDecl->isInIdentifierNamespace(Decl::IDNS_Namespace))
         continue;
 
       if (auto *FoundNS = dyn_cast<NamespaceDecl>(FoundDecl)) {
         MergeWithNamespace = FoundNS;
         ConflictingDecls.clear();
         break;
if (ToD)
     return ToD;
 
   // If this typedef is not in block scope, determine whether we've
   // seen a typedef with the same name (that we can merge with) or any
   // other entity by that name (which name lookup could conflict with).
   if (!DC->isFunctionOrMethod()) {
     SmallVector<NamedDecl *, 4> ConflictingDecls;
     unsigned IDNS = Decl::IDNS_Ordinary;
-    SmallVector<NamedDecl *, 2> FoundDecls;
-    DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+    auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
     for (auto *FoundDecl : FoundDecls) {
       if (!FoundDecl->isInIdentifierNamespace(IDNS))
         continue;
       if (auto *FoundTypedef = dyn_cast<TypedefNameDecl>(FoundDecl)) {
         QualType FromUT = D->getUnderlyingType();
         QualType FoundUT = FoundTypedef->getUnderlyingType();
         if (Importer.IsStructurallyEquivalent(FromUT, FoundUT)) {
           // If the "From" context has a complete underlying type but we
if (FoundD)
     return FoundD;
 
   // If this typedef is not in block scope, determine whether we've
   // seen a typedef with the same name (that we can merge with) or any
   // other entity by that name (which name lookup could conflict with).
   if (!DC->isFunctionOrMethod()) {
     SmallVector<NamedDecl *, 4> ConflictingDecls;
     unsigned IDNS = Decl::IDNS_Ordinary;
-    SmallVector<NamedDecl *, 2> FoundDecls;
-    DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+    auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
     for (auto *FoundDecl : FoundDecls) {
       if (!FoundDecl->isInIdentifierNamespace(IDNS))
         continue;
       if (auto *FoundAlias = dyn_cast<TypeAliasTemplateDecl>(FoundDecl))
         return Importer.MapImported(D, FoundAlias);
       ConflictingDecls.push_back(FoundDecl);
     }
 
if (Error Err = importInto(
       return std::move(Err);
     IDNS = Decl::IDNS_Ordinary;
   } else if (Importer.getToContext().getLangOpts().CPlusPlus)
     IDNS |= Decl::IDNS_Ordinary;
 
   // We may already have an enum of the same name; try to find and match it.
   if (!DC->isFunctionOrMethod() && SearchName) {
     SmallVector<NamedDecl *, 4> ConflictingDecls;
-    SmallVector<NamedDecl *, 2> FoundDecls;
-    DC->getRedeclContext()->localUncachedLookup(SearchName, FoundDecls);
+    auto FoundDecls =
+        Importer.findDeclsInToCtx(DC, SearchName);
     for (auto *FoundDecl : FoundDecls) {
       if (!FoundDecl->isInIdentifierNamespace(IDNS))
         continue;
 
       if (auto *Typedef = dyn_cast<TypedefNameDecl>(FoundDecl)) {
         if (const auto *Tag = Typedef->getUnderlyingType()->getAs<TagType>())
           FoundDecl = Tag->getDecl();
       }
if (!SearchName && D->getTypedefNameForAnonDecl()) {
     IDNS = Decl::IDNS_Ordinary;
   } else if (Importer.getToContext().getLangOpts().CPlusPlus)
     IDNS |= Decl::IDNS_Ordinary | Decl::IDNS_TagFriend;
 
   // We may already have a record of the same name; try to find and match it.
   RecordDecl *PrevDecl = nullptr;
   if (!DC->isFunctionOrMethod()) {
     SmallVector<NamedDecl *, 4> ConflictingDecls;
-    SmallVector<NamedDecl *, 2> FoundDecls;
-    DC->getRedeclContext()->localUncachedLookup(SearchName, FoundDecls);
-
+    auto FoundDecls =
+        Importer.findDeclsInToCtx(DC, SearchName);
     if (!FoundDecls.empty()) {
       // We're going to have to compare D against potentially conflicting Decls, so complete it.
       if (D->hasExternalLexicalStorage() && !D->isCompleteDefinition())
         D->getASTContext().getExternalSource()->CompleteType(D);
     }
 
     for (auto *FoundDecl : FoundDecls) {
       if (!FoundDecl->isInIdentifierNamespace(IDNS))
         continue;
 
       Decl *Found = FoundDecl;
       if (auto *Typedef = dyn_cast<TypedefNameDecl>(Found)) {
         if (const auto *Tag = Typedef->getUnderlyingType()->getAs<TagType>())
           Found = Tag->getDecl();
       }
 
-      if (D->getDescribedTemplate()) {
-        if (auto *Template = dyn_cast<ClassTemplateDecl>(Found)) {
-          Found = Template->getTemplatedDecl();
-        } else {
-          ConflictingDecls.push_back(FoundDecl);
-          continue;
-        }
-      }
-
       if (auto *FoundRecord = dyn_cast<RecordDecl>(Found)) {
         // Do not emit false positive diagnostic in case of unnamed
         // struct/union and in case of anonymous structs.  Would be false
         // because there may be several anonymous/unnamed structs in a class.
         // E.g. these are both valid:
         //  struct A { // unnamed structs
         //    struct { struct A *next; } entry0;
         //    struct { struct A *next; } entry1;
ExpectedDecl ASTNodeImporter::VisitEnumConstantDecl(EnumConstantDecl *D) {
   if (ToD)
     return ToD;
 
   // Determine whether there are any other declarations with the same name and
   // in the same context.
   if (!LexicalDC->isFunctionOrMethod()) {
     SmallVector<NamedDecl *, 4> ConflictingDecls;
     unsigned IDNS = Decl::IDNS_Ordinary;
-    SmallVector<NamedDecl *, 2> FoundDecls;
-    DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+    auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
     for (auto *FoundDecl : FoundDecls) {
       if (!FoundDecl->isInIdentifierNamespace(IDNS))
         continue;
 
       if (auto *FoundEnumConstant = dyn_cast<EnumConstantDecl>(FoundDecl)) {
         if (IsStructuralMatch(D, FoundEnumConstant))
           return Importer.MapImported(D, FoundEnumConstant);
       }
if (Error Err = ImportDeclParts(D, DC, LexicalDC, Name, ToD, Loc))
     return std::move(Err);
   if (ToD)
     return ToD;
 
   const FunctionDecl *FoundByLookup = nullptr;
   FunctionTemplateDecl *FromFT = D->getDescribedFunctionTemplate();
 
   // If this is a function template specialization, then try to find the same
-  // existing specialization in the "to" context. The localUncachedLookup
-  // below will not find any specialization, but would find the primary
-  // template; thus, we have to skip normal lookup in case of specializations.
+  // existing specialization in the "to" context. The lookup below will not
+  // find any specialization, but would find the primary template; thus, we
+  // have to skip normal lookup in case of specializations.
   // FIXME handle member function templates (TK_MemberSpecialization) similarly?
   if (D->getTemplatedKind() ==
       FunctionDecl::TK_FunctionTemplateSpecialization) {
     auto FoundFunctionOrErr = FindFunctionTemplateSpecialization(D);
     if (!FoundFunctionOrErr)
       return FoundFunctionOrErr.takeError();
     if (FunctionDecl *FoundFunction = *FoundFunctionOrErr) {
       if (D->doesThisDeclarationHaveABody() && FoundFunction->hasBody())
         return Importer.MapImported(D, FoundFunction);
       FoundByLookup = FoundFunction;
     }
   }
   // Try to find a function in our own ("to") context with the same name, same
   // type, and in the same context as the function we're importing.
   else if (!LexicalDC->isFunctionOrMethod()) {
     SmallVector<NamedDecl *, 4> ConflictingDecls;
     unsigned IDNS = Decl::IDNS_Ordinary | Decl::IDNS_OrdinaryFriend;
-    SmallVector<NamedDecl *, 2> FoundDecls;
-    DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+    auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
     for (auto *FoundDecl : FoundDecls) {
       if (!FoundDecl->isInIdentifierNamespace(IDNS))
         continue;
 
-      // If template was found, look at the templated function.
-      if (FromFT) {
-        if (auto *Template = dyn_cast<FunctionTemplateDecl>(FoundDecl))
-          FoundDecl = Template->getTemplatedDecl();
-        else
-          continue;
-      }
-
       if (auto *FoundFunction = dyn_cast<FunctionDecl>(FoundDecl)) {
         if (FoundFunction->hasExternalFormalLinkage() &&
             D->hasExternalFormalLinkage()) {
           if (IsStructuralMatch(D, FoundFunction)) {
             const FunctionDecl *Definition = nullptr;
             if (D->doesThisDeclarationHaveABody() &&
                 FoundFunction->hasBody(Definition)) {
               return Importer.MapImported(
ExpectedDecl ASTNodeImporter::VisitFieldDecl(FieldDecl *D) {
   SourceLocation Loc;
   NamedDecl *ToD;
   if (Error Err = ImportDeclParts(D, DC, LexicalDC, Name, ToD, Loc))
     return std::move(Err);
   if (ToD)
     return ToD;
 
   // Determine whether we've already imported this field.
-  SmallVector<NamedDecl *, 2> FoundDecls;
-  DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+  auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
   for (auto *FoundDecl : FoundDecls) {
     if (FieldDecl *FoundField = dyn_cast<FieldDecl>(FoundDecl)) {
       // For anonymous fields, match up by index.
       if (!Name &&
           ASTImporter::getFieldIndex(D) !=
           ASTImporter::getFieldIndex(FoundField))
         continue;
 
ExpectedDecl ASTNodeImporter::VisitIndirectFieldDecl(IndirectFieldDecl *D) {
   SourceLocation Loc;
   NamedDecl *ToD;
   if (Error Err = ImportDeclParts(D, DC, LexicalDC, Name, ToD, Loc))
     return std::move(Err);
   if (ToD)
     return ToD;
 
   // Determine whether we've already imported this field.
-  SmallVector<NamedDecl *, 2> FoundDecls;
-  DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+  auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
   for (unsigned I = 0, N = FoundDecls.size(); I != N; ++I) {
     if (auto *FoundField = dyn_cast<IndirectFieldDecl>(FoundDecls[I])) {
       // For anonymous indirect fields, match up by index.
       if (!Name &&
           ASTImporter::getFieldIndex(D) !=
           ASTImporter::getFieldIndex(FoundField))
         continue;
 

 
 ExpectedDecl ASTNodeImporter::VisitFriendDecl(FriendDecl *D) {
   // Import the major distinguishing characteristics of a declaration.
   DeclContext *DC, *LexicalDC;
   if (Error Err = ImportDeclContext(D, DC, LexicalDC))
     return std::move(Err);
 
   // Determine whether we've already imported this decl.
-  // FriendDecl is not a NamedDecl so we cannot use localUncachedLookup.
+  // FriendDecl is not a NamedDecl so we cannot use lookup.
   auto *RD = cast<CXXRecordDecl>(DC);
   FriendDecl *ImportedFriend = RD->getFirstFriend();
 
   while (ImportedFriend) {
     if (D->getFriendDecl() && ImportedFriend->getFriendDecl()) {
       if (IsStructuralMatch(D->getFriendDecl(), ImportedFriend->getFriendDecl(),
                             /*Complain=*/false))
         return Importer.MapImported(D, ImportedFriend);
ExpectedDecl ASTNodeImporter::VisitObjCIvarDecl(ObjCIvarDecl *D) {
   SourceLocation Loc;
   NamedDecl *ToD;
   if (Error Err = ImportDeclParts(D, DC, LexicalDC, Name, ToD, Loc))
     return std::move(Err);
   if (ToD)
     return ToD;
 
   // Determine whether we've already imported this ivar
-  SmallVector<NamedDecl *, 2> FoundDecls;
-  DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+  auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
   for (auto *FoundDecl : FoundDecls) {
     if (ObjCIvarDecl *FoundIvar = dyn_cast<ObjCIvarDecl>(FoundDecl)) {
       if (Importer.IsStructurallyEquivalent(D->getType(),
                                             FoundIvar->getType())) {
         Importer.MapImported(D, FoundIvar);
         return FoundIvar;
       }
 
if (ToD)
     return ToD;
 
   // Try to find a variable in our own ("to") context with the same name and
   // in the same context as the variable we're importing.
   VarDecl *FoundByLookup = nullptr;
   if (D->isFileVarDecl()) {
     SmallVector<NamedDecl *, 4> ConflictingDecls;
     unsigned IDNS = Decl::IDNS_Ordinary;
-    SmallVector<NamedDecl *, 2> FoundDecls;
-    DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+    auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
     for (auto *FoundDecl : FoundDecls) {
       if (!FoundDecl->isInIdentifierNamespace(IDNS))
         continue;
 
       if (auto *FoundVar = dyn_cast<VarDecl>(FoundDecl)) {
         // We have found a variable that we may need to merge with. Check it.
         if (FoundVar->hasExternalFormalLinkage() &&
             D->hasExternalFormalLinkage()) {
ExpectedDecl ASTNodeImporter::VisitObjCMethodDecl(ObjCMethodDecl *D) {
   DeclarationName Name;
   SourceLocation Loc;
   NamedDecl *ToD;
   if (Error Err = ImportDeclParts(D, DC, LexicalDC, Name, ToD, Loc))
     return std::move(Err);
   if (ToD)
     return ToD;
 
-  SmallVector<NamedDecl *, 2> FoundDecls;
-  DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+  auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
   for (auto *FoundDecl : FoundDecls) {
     if (auto *FoundMethod = dyn_cast<ObjCMethodDecl>(FoundDecl)) {
       if (FoundMethod->isInstanceMethod() != D->isInstanceMethod())
         continue;
 
       // Check return types.
       if (!Importer.IsStructurallyEquivalent(D->getReturnType(),
                                              FoundMethod->getReturnType())) {
ExpectedDecl ASTNodeImporter::VisitObjCProtocolDecl(ObjCProtocolDecl *D) {
   SourceLocation Loc;
   NamedDecl *ToD;
   if (Error Err = ImportDeclParts(D, DC, LexicalDC, Name, ToD, Loc))
     return std::move(Err);
   if (ToD)
     return ToD;
 
   ObjCProtocolDecl *MergeWithProtocol = nullptr;
-  SmallVector<NamedDecl *, 2> FoundDecls;
-  DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+  auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
   for (auto *FoundDecl : FoundDecls) {
     if (!FoundDecl->isInIdentifierNamespace(Decl::IDNS_ObjCProtocol))
       continue;
 
     if ((MergeWithProtocol = dyn_cast<ObjCProtocolDecl>(FoundDecl)))
       break;
   }
 
ExpectedDecl ASTNodeImporter::VisitObjCInterfaceDecl(ObjCInterfaceDecl *D) {
   NamedDecl *ToD;
   if (Error Err = ImportDeclParts(D, DC, LexicalDC, Name, ToD, Loc))
     return std::move(Err);
   if (ToD)
     return ToD;
 
   // Look for an existing interface with the same name.
   ObjCInterfaceDecl *MergeWithIface = nullptr;
-  SmallVector<NamedDecl *, 2> FoundDecls;
-  DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+  auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
   for (auto *FoundDecl : FoundDecls) {
     if (!FoundDecl->isInIdentifierNamespace(Decl::IDNS_Ordinary))
       continue;
 
     if ((MergeWithIface = dyn_cast<ObjCInterfaceDecl>(FoundDecl)))
       break;
   }
 
ExpectedDecl ASTNodeImporter::VisitObjCPropertyDecl(ObjCPropertyDecl *D) {
   SourceLocation Loc;
   NamedDecl *ToD;
   if (Error Err = ImportDeclParts(D, DC, LexicalDC, Name, ToD, Loc))
     return std::move(Err);
   if (ToD)
     return ToD;
 
   // Check whether we have already imported this property.
-  SmallVector<NamedDecl *, 2> FoundDecls;
-  DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+  auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
   for (auto *FoundDecl : FoundDecls) {
     if (auto *FoundProp = dyn_cast<ObjCPropertyDecl>(FoundDecl)) {
       // Check property types.
       if (!Importer.IsStructurallyEquivalent(D->getType(),
                                              FoundProp->getType())) {
         Importer.ToDiag(Loc, diag::err_odr_objc_property_type_inconsistent)
           << Name << D->getType() << FoundProp->getType();
         Importer.ToDiag(FoundProp->getLocation(), diag::note_odr_value_here)
ExpectedDecl ASTNodeImporter::VisitClassTemplateDecl(ClassTemplateDecl *D) {
   if (ToD)
     return ToD;
 
   ClassTemplateDecl *FoundByLookup = nullptr;
 
   // We may already have a template of the same name; try to find and match it.
   if (!DC->isFunctionOrMethod()) {
     SmallVector<NamedDecl *, 4> ConflictingDecls;
-    SmallVector<NamedDecl *, 2> FoundDecls;
-    DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+    auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
     for (auto *FoundDecl : FoundDecls) {
       if (!FoundDecl->isInIdentifierNamespace(Decl::IDNS_Ordinary |
                                               Decl::IDNS_TagFriend))
         continue;
 
       Decl *Found = FoundDecl;
       auto *FoundTemplate = dyn_cast<ClassTemplateDecl>(Found);
       if (FoundTemplate) {
if (Error Err = ImportDeclParts(D, DC, LexicalDC, Name, ToD, Loc))
     return std::move(Err);
   if (ToD)
     return ToD;
 
   // We may already have a template of the same name; try to find and match it.
   assert(!DC->isFunctionOrMethod() &&
          "Variable templates cannot be declared at function scope");
   SmallVector<NamedDecl *, 4> ConflictingDecls;
-  SmallVector<NamedDecl *, 2> FoundDecls;
-  DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+  auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
   for (auto *FoundDecl : FoundDecls) {
     if (!FoundDecl->isInIdentifierNamespace(Decl::IDNS_Ordinary))
       continue;
 
     Decl *Found = FoundDecl;
     if (VarTemplateDecl *FoundTemplate = dyn_cast<VarTemplateDecl>(Found)) {
       if (IsStructuralMatch(D, FoundTemplate)) {
         // The variable templates structurally match; call it the same template.
ASTNodeImporter::VisitFunctionTemplateDecl(FunctionTemplateDecl *D) {
 
   if (ToD)
     return ToD;
 
   // Try to find a function in our own ("to") context with the same name, same
   // type, and in the same context as the function we're importing.
   if (!LexicalDC->isFunctionOrMethod()) {
     unsigned IDNS = Decl::IDNS_Ordinary;
-    SmallVector<NamedDecl *, 2> FoundDecls;
-    DC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+    auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
     for (auto *FoundDecl : FoundDecls) {
       if (!FoundDecl->isInIdentifierNamespace(IDNS))
         continue;
 
       if (auto *FoundFunction =
           dyn_cast<FunctionTemplateDecl>(FoundDecl)) {
         if (FoundFunction->hasExternalFormalLinkage() &&
             D->hasExternalFormalLinkage()) {
if (auto ImportedOrErr = import(FromOverriddenMethod))
           (*ImportedOrErr)->getCanonicalDecl()));
     else
       consumeError(ImportedOrErr.takeError());
   }
 }
 
 ASTImporter::ASTImporter(ASTContext &ToContext, FileManager &ToFileManager,
                          ASTContext &FromContext, FileManager &FromFileManager,
-                         bool MinimalImport)
-    : ToContext(ToContext), FromContext(FromContext),
+                         bool MinimalImport,
+                         ASTImporterLookupTable *LookupTable)
+    : LookupTable(LookupTable), ToContext(ToContext), FromContext(FromContext),
       ToFileManager(ToFileManager), FromFileManager(FromFileManager),
       Minimal(MinimalImport) {
-  ImportedDecls[FromContext.getTranslationUnitDecl()]
-    = ToContext.getTranslationUnitDecl();
+
+  ImportedDecls[FromContext.getTranslationUnitDecl()] =
+      ToContext.getTranslationUnitDecl();
 }
 
 ASTImporter::~ASTImporter() = default;
 
 Expected<QualType> ASTImporter::Import_New(QualType FromT) {
   QualType ToT = Import(FromT);
   if (ToT.isNull() && !FromT.isNull())
     return make_error<ImportError>();
   return ToT;
 }
+
+Optional<unsigned> ASTImporter::getFieldIndex(Decl *F) {
+  assert(F && (isa<FieldDecl>(*F) || isa<IndirectFieldDecl>(*F)) &&
+      "Try to get field index for non-field.");
+
+  auto *Owner = dyn_cast<RecordDecl>(F->getDeclContext());
+  if (!Owner)
+    return None;
+
+  unsigned Index = 0;
+  for (const auto *D : Owner->decls()) {
+    if (D == F)
+      return Index;
+
+    if (isa<FieldDecl>(*D) || isa<IndirectFieldDecl>(*D))
+      ++Index;
+  }
+
+  llvm_unreachable("Field was not found in its parent context.");
+
+  return None;
+}
+
+ASTImporter::FoundDeclsTy
+ASTImporter::findDeclsInToCtx(DeclContext *DC, DeclarationName Name) {
+  // We search in the redecl context because of transparent contexts.
+  // E.g. a simple C language enum is a transparent context:
+  //   enum E { A, B };
+  // Now if we had a global variable in the TU
+  //   int A;
+  // then the enum constant 'A' and the variable 'A' violates ODR.
+  // We can diagnose this only if we search in the redecl context.
+  DeclContext *ReDC = DC->getRedeclContext();
+  if (LookupTable) {
+    ASTImporterLookupTable::LookupResult LookupResult =
+        LookupTable->lookup(ReDC, Name);
+    return FoundDeclsTy(LookupResult.begin(), LookupResult.end());
+  } else {
+    // FIXME Can we remove this kind of lookup?
+    // Or lldb really needs this C/C++ lookup?
+    FoundDeclsTy Result;
+    ReDC->localUncachedLookup(Name, Result);
+    return Result;
+  }
+}
+
+void ASTImporter::AddToLookupTable(Decl *ToD) {
+  if (LookupTable)
+    if (auto *ToND = dyn_cast<NamedDecl>(ToD))
+      LookupTable->add(ToND);
+}
+
 QualType ASTImporter::Import(QualType FromT) {
   if (FromT.isNull())
     return {};
 
   const Type *FromTy = FromT.getTypePtr();
 
   // Check whether we've already imported this type.
   llvm::DenseMap<const Type *, const Type *>::iterator Pos
Decl *ASTImporter::Import(Decl *FromD) {
   // Import the type.
   ExpectedDecl ToDOrErr = Importer.Visit(FromD);
   if (!ToDOrErr) {
     llvm::consumeError(ToDOrErr.takeError());
     return nullptr;
   }
   ToD = *ToDOrErr;
 
+  // Once the decl is connected to the existing declarations, i.e. when the
+  // redecl chain is properly set then we populate the lookup again.
+  // This way the primary context will be able to find all decls.
+  AddToLookupTable(ToD);
+
   // Notify subclasses.
   Imported(FromD, ToD);
 
   updateFlags(FromD, ToD);
   return ToD;
 }
 
 Expected<DeclContext *> ASTImporter::ImportContext(DeclContext *FromDC) {

cfe/trunk/lib/AST/ASTImporterLookupTable.cpp

+//===- ASTImporterLookupTable.cpp - ASTImporter specific lookup -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the ASTImporterLookupTable class which implements a
+//  lookup procedure for the import mechanism.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/ASTImporterLookupTable.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+
+namespace clang {
+
+namespace {
+
+struct Builder : RecursiveASTVisitor<Builder> {
+  ASTImporterLookupTable &LT;
+  Builder(ASTImporterLookupTable &LT) : LT(LT) {}
+  bool VisitNamedDecl(NamedDecl *D) {
+    LT.add(D);
+    return true;
+  }
+  bool VisitFriendDecl(FriendDecl *D) {
+    if (D->getFriendType()) {
+      QualType Ty = D->getFriendType()->getType();
+      // FIXME Can this be other than elaborated?
+      QualType NamedTy = cast<ElaboratedType>(Ty)->getNamedType();
+      if (!NamedTy->isDependentType()) {
+        if (const auto *RTy = dyn_cast<RecordType>(NamedTy))
+          LT.add(RTy->getAsCXXRecordDecl());
+        else if (const auto *SpecTy =
+                     dyn_cast<TemplateSpecializationType>(NamedTy)) {
+          LT.add(SpecTy->getAsCXXRecordDecl());
+        }
+      }
+    }
+    return true;
+  }
+
+  // Override default settings of base.
+  bool shouldVisitTemplateInstantiations() const { return true; }
+  bool shouldVisitImplicitCode() const { return true; }
+};
+
+} // anonymous namespace
+
+ASTImporterLookupTable::ASTImporterLookupTable(TranslationUnitDecl &TU) {
+  Builder B(*this);
+  B.TraverseDecl(&TU);
+}
+
+void ASTImporterLookupTable::add(DeclContext *DC, NamedDecl *ND) {
+  DeclList &Decls = LookupTable[DC][ND->getDeclName()];
+  // Inserts if and only if there is no element in the container equal to it.
+  Decls.insert(ND);
+}
+
+void ASTImporterLookupTable::remove(DeclContext *DC, NamedDecl *ND) {
+  DeclList &Decls = LookupTable[DC][ND->getDeclName()];
+  bool EraseResult = Decls.remove(ND);
+  (void)EraseResult;
+  assert(EraseResult == true && "Trying to remove not contained Decl");
+}
+
+void ASTImporterLookupTable::add(NamedDecl *ND) {
+  assert(ND);
+  DeclContext *DC = ND->getDeclContext()->getPrimaryContext();
+  add(DC, ND);
+  DeclContext *ReDC = DC->getRedeclContext()->getPrimaryContext();
+  if (DC != ReDC)
+    add(ReDC, ND);
+}
+
+void ASTImporterLookupTable::remove(NamedDecl *ND) {
+  assert(ND);
+  DeclContext *DC = ND->getDeclContext()->getPrimaryContext();
+  remove(DC, ND);
+  DeclContext *ReDC = DC->getRedeclContext()->getPrimaryContext();
+  if (DC != ReDC)
+    remove(ReDC, ND);
+}
+
+ASTImporterLookupTable::LookupResult
+ASTImporterLookupTable::lookup(DeclContext *DC, DeclarationName Name) const {
+  auto DCI = LookupTable.find(DC->getPrimaryContext());
+  if (DCI == LookupTable.end())
+    return {};
+
+  const auto &FoundNameMap = DCI->second;
+  auto NamesI = FoundNameMap.find(Name);
+  if (NamesI == FoundNameMap.end())
+    return {};
+
+  return NamesI->second;
+}
+
+void ASTImporterLookupTable::dump(DeclContext *DC) const {
+  auto DCI = LookupTable.find(DC->getPrimaryContext());
+  if (DCI == LookupTable.end())
+    llvm::errs() << "empty\n";
+  const auto &FoundNameMap = DCI->second;
+  for (const auto &Entry : FoundNameMap) {
+    DeclarationName Name = Entry.first;
+    llvm::errs() << "==== Name: ";
+    Name.dump();
+    const DeclList& List = Entry.second;
+    for (NamedDecl *ND : List) {
+      ND->dump();
+    }
+  }
+}
+
+void ASTImporterLookupTable::dump() const {
+  for (const auto &Entry : LookupTable) {
+    DeclContext *DC = Entry.first;
+    StringRef Primary = DC->getPrimaryContext() ? " primary" : "";
+    llvm::errs() << "== DC:" << cast<Decl>(DC) << Primary << "\n";
+    dump(DC);
+  }
+}
+
+} // namespace clang

cfe/trunk/lib/AST/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   BinaryFormat
   Support
   )
 
 add_clang_library(clangAST
   APValue.cpp
   ASTConsumer.cpp
   ASTContext.cpp
   ASTDiagnostic.cpp
   ASTDumper.cpp
   ASTImporter.cpp
+  ASTImporterLookupTable.cpp
   ASTStructuralEquivalence.cpp
   ASTTypeTraits.cpp
   AttrImpl.cpp
   CXXInheritance.cpp
   Comment.cpp
   CommentBriefParser.cpp
   CommentCommandTraits.cpp
   CommentLexer.cpp

cfe/trunk/lib/CrossTU/CrossTranslationUnit.cpp

CrossTranslationUnitContext::importDefinition(const FunctionDecl *FD) {
   if (!ToDecl)
     return llvm::make_error<IndexError>(index_error_code::failed_import);
   assert(ToDecl->hasBody());
   assert(FD->hasBody() && "Functions already imported should have body.");
   ++NumGetCTUSuccess;
   return ToDecl;
 }
 
+void CrossTranslationUnitContext::lazyInitLookupTable(
+    TranslationUnitDecl *ToTU) {
+  if (!LookupTable)
+    LookupTable = llvm::make_unique<ASTImporterLookupTable>(*ToTU);
+}
+
 ASTImporter &
 CrossTranslationUnitContext::getOrCreateASTImporter(ASTContext &From) {
   auto I = ASTUnitImporterMap.find(From.getTranslationUnitDecl());
   if (I != ASTUnitImporterMap.end())
     return *I->second;
-  ASTImporter *NewImporter =
-      new ASTImporter(Context, Context.getSourceManager().getFileManager(),
-                      From, From.getSourceManager().getFileManager(), false);
+  lazyInitLookupTable(Context.getTranslationUnitDecl());
+  ASTImporter *NewImporter = new ASTImporter(
+      Context, Context.getSourceManager().getFileManager(), From,
+      From.getSourceManager().getFileManager(), false, LookupTable.get());
   ASTUnitImporterMap[From.getTranslationUnitDecl()].reset(NewImporter);
   return *NewImporter;
 }
 
 } // namespace cross_tu
 } // namespace clang

cfe/trunk/lib/Frontend/ASTMerge.cpp

 //===-- ASTMerge.cpp - AST Merging Frontend Action --------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #include "clang/Frontend/ASTUnit.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/ASTImporter.h"
+#include "clang/AST/ASTImporterLookupTable.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendActions.h"
 
 using namespace clang;
 
 std::unique_ptr<ASTConsumer>
 ASTMergeAction::CreateASTConsumer(CompilerInstance &CI, StringRef InFile) {

 void ASTMergeAction::ExecuteAction() {
   CompilerInstance &CI = getCompilerInstance();
   CI.getDiagnostics().getClient()->BeginSourceFile(
                                              CI.getASTContext().getLangOpts());
   CI.getDiagnostics().SetArgToStringFn(&FormatASTNodeDiagnosticArgument,
                                        &CI.getASTContext());
   IntrusiveRefCntPtr<DiagnosticIDs>
       DiagIDs(CI.getDiagnostics().getDiagnosticIDs());
+  ASTImporterLookupTable LookupTable(
+      *CI.getASTContext().getTranslationUnitDecl());
   for (unsigned I = 0, N = ASTFiles.size(); I != N; ++I) {
     IntrusiveRefCntPtr<DiagnosticsEngine>
         Diags(new DiagnosticsEngine(DiagIDs, &CI.getDiagnosticOpts(),
                                     new ForwardingDiagnosticConsumer(
                                           *CI.getDiagnostics().getClient()),
                                     /*ShouldOwnClient=*/true));
     std::unique_ptr<ASTUnit> Unit = ASTUnit::LoadFromASTFile(
         ASTFiles[I], CI.getPCHContainerReader(), ASTUnit::LoadEverything, Diags,
         CI.getFileSystemOpts(), false);
 
     if (!Unit)
       continue;
 
-    ASTImporter Importer(CI.getASTContext(),
-                         CI.getFileManager(),
-                         Unit->getASTContext(),
-                         Unit->getFileManager(),
-                         /*MinimalImport=*/false);
+    ASTImporter Importer(CI.getASTContext(), CI.getFileManager(),
+                         Unit->getASTContext(), Unit->getFileManager(),
+                         /*MinimalImport=*/false, &LookupTable);
 
     TranslationUnitDecl *TU = Unit->getASTContext().getTranslationUnitDecl();
     for (auto *D : TU->decls()) {
       // Don't re-import __va_list_tag, __builtin_va_list.
       if (const auto *ND = dyn_cast<NamedDecl>(D))
         if (IdentifierInfo *II = ND->getIdentifier())
           if (II->isStr("__va_list_tag") || II->isStr("__builtin_va_list"))
             continue;

cfe/trunk/unittests/AST/ASTImporterTest.cpp

 // Tests for the correct import of AST nodes from one AST context to another.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ASTImporter.h"
 #include "MatchVerifier.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclContextInternals.h"
+#include "clang/AST/ASTImporter.h"
+#include "clang/AST/ASTImporterLookupTable.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Tooling/Tooling.h"
 
 #include "DeclMatcher.h"
 #include "Language.h"
 #include "gmock/gmock.h"
 #include "llvm/ADT/StringMap.h"
struct TU {
     TU(StringRef Code, StringRef FileName, ArgVector Args)
         : Code(Code), FileName(FileName),
           Unit(tooling::buildASTFromCodeWithArgs(this->Code, Args,
                                                  this->FileName)),
           TUDecl(Unit->getASTContext().getTranslationUnitDecl()) {
       Unit->enableSourceFileDiagnostics();
     }
 
-    void lazyInitImporter(ASTUnit *ToAST) {
+    void lazyInitImporter(ASTImporterLookupTable &LookupTable, ASTUnit *ToAST) {
       assert(ToAST);
       if (!Importer) {
-        Importer.reset(new ASTImporter(
-            ToAST->getASTContext(), ToAST->getFileManager(),
-            Unit->getASTContext(), Unit->getFileManager(), false));
+        Importer.reset(
+            new ASTImporter(ToAST->getASTContext(), ToAST->getFileManager(),
+                            Unit->getASTContext(), Unit->getFileManager(),
+                            false, &LookupTable));
       }
       assert(&ToAST->getASTContext() == &Importer->getToContext());
       createVirtualFileIfNeeded(ToAST, FileName, Code);
     }
 
-    Decl *import(ASTUnit *ToAST, Decl *FromDecl) {
-      lazyInitImporter(ToAST);
+    Decl *import(ASTImporterLookupTable &LookupTable, ASTUnit *ToAST,
+                 Decl *FromDecl) {
+      lazyInitImporter(LookupTable, ToAST);
       return Importer->Import(FromDecl);
-     }
 
-    QualType import(ASTUnit *ToAST, QualType FromType) {
-      lazyInitImporter(ToAST);
+    QualType import(ASTImporterLookupTable &LookupTable, ASTUnit *ToAST,
+                    QualType FromType) {
+      lazyInitImporter(LookupTable, ToAST);
       return Importer->Import(FromType);
     }
   };
 
   // We may have several From contexts and related translation units. In each
   // AST, the buffers for the source are handled via references and are set
   // during the creation of the AST. These references must point to a valid
   // buffer until the AST is alive. Thus, we must use a list in order to avoid
   // moving of the stored objects because that would mean breaking the
   // references in the AST. By using a vector a move could happen when the
   // vector is expanding, with the list we won't have these issues.
   std::list<TU> FromTUs;
 
-  void lazyInitToAST(Language ToLang) {
+  // Initialize the lookup table if not initialized already.
+  void lazyInitLookupTable(TranslationUnitDecl *ToTU) {
+    assert(ToTU);
+    if (!LookupTablePtr)
+      LookupTablePtr = llvm::make_unique<ASTImporterLookupTable>(*ToTU);
+  }
+
+  void lazyInitToAST(Language ToLang, StringRef ToSrcCode, StringRef FileName) {
     if (ToAST)
       return;
     ArgVector ToArgs = getArgVectorForLanguage(ToLang);
+    // Source code must be a valid live buffer through the tests lifetime.
+    ToCode = ToSrcCode;
     // Build the AST from an empty file.
-    ToAST = tooling::buildASTFromCodeWithArgs(/*Code=*/"", ToArgs, "empty.cc");
+    ToAST = tooling::buildASTFromCodeWithArgs(ToCode, ToArgs, FileName);
     ToAST->enableSourceFileDiagnostics();
+    lazyInitLookupTable(ToAST->getASTContext().getTranslationUnitDecl());
   }
 
   TU *findFromTU(Decl *From) {
     // Create a virtual file in the To Ctx which corresponds to the file from
     // which we want to import the `From` Decl. Without this source locations
     // will be invalid in the ToCtx.
     auto It = std::find_if(FromTUs.begin(), FromTUs.end(), [From](const TU &E) {
       return E.TUDecl == From->getTranslationUnitDecl();
     });
     assert(It != FromTUs.end());
     return &*It;
   }
 
+protected:
+
+  std::unique_ptr<ASTImporterLookupTable> LookupTablePtr;
+
 public:
   // We may have several From context but only one To context.
   std::unique_ptr<ASTUnit> ToAST;
 
   // Creates an AST both for the From and To source code and imports the Decl
   // of the identifier into the To context.
   // Must not be called more than once within the same test.
   std::tuple<Decl *, Decl *>
   getImportedDecl(StringRef FromSrcCode, Language FromLang, StringRef ToSrcCode,
                   Language ToLang, StringRef Identifier = DeclToImportID) {
     ArgVector FromArgs = getArgVectorForLanguage(FromLang),
               ToArgs = getArgVectorForLanguage(ToLang);
 
     FromTUs.emplace_back(FromSrcCode, InputFileName, FromArgs);
     TU &FromTU = FromTUs.back();
 
-    ToCode = ToSrcCode;
     assert(!ToAST);
-    ToAST = tooling::buildASTFromCodeWithArgs(ToCode, ToArgs, OutputFileName);
-    ToAST->enableSourceFileDiagnostics();
+    lazyInitToAST(ToLang, ToSrcCode, OutputFileName);
 
     ASTContext &FromCtx = FromTU.Unit->getASTContext();
 
-    createVirtualFileIfNeeded(ToAST.get(), InputFileName, FromTU.Code);
-
     IdentifierInfo *ImportedII = &FromCtx.Idents.get(Identifier);
     assert(ImportedII && "Declaration with the given identifier "
                          "should be specified in test!");
     DeclarationName ImportDeclName(ImportedII);
-    SmallVector<NamedDecl *, 4> FoundDecls;
+    SmallVector<NamedDecl *, 1> FoundDecls;
     FromCtx.getTranslationUnitDecl()->localUncachedLookup(ImportDeclName,
                                                           FoundDecls);
 
     assert(FoundDecls.size() == 1);
 
-    Decl *Imported = FromTU.import(ToAST.get(), FoundDecls.front());
+    Decl *Imported =
+        FromTU.import(*LookupTablePtr, ToAST.get(), FoundDecls.front());
 
     assert(Imported);
     return std::make_tuple(*FoundDecls.begin(), Imported);
   }
 
   // Creates a TU decl for the given source code which can be used as a From
   // context.  May be called several times in a given test (with different file
   // name).
TranslationUnitDecl *getTuDecl(StringRef SrcCode, Language Lang,
     TU &Tu = FromTUs.back();
 
     return Tu.TUDecl;
   }
 
   // Creates the To context with the given source code and returns the TU decl.
   TranslationUnitDecl *getToTuDecl(StringRef ToSrcCode, Language ToLang) {
     ArgVector ToArgs = getArgVectorForLanguage(ToLang);
-    ToCode = ToSrcCode;
     assert(!ToAST);
-    ToAST = tooling::buildASTFromCodeWithArgs(ToCode, ToArgs, OutputFileName);
-    ToAST->enableSourceFileDiagnostics();
-
+    lazyInitToAST(ToLang, ToSrcCode, OutputFileName);
     return ToAST->getASTContext().getTranslationUnitDecl();
   }
 
   // Import the given Decl into the ToCtx.
   // May be called several times in a given test.
   // The different instances of the param From may have different ASTContext.
   Decl *Import(Decl *From, Language ToLang) {
-    lazyInitToAST(ToLang);
+    lazyInitToAST(ToLang, "", OutputFileName);
     TU *FromTU = findFromTU(From);
-    return FromTU->import(ToAST.get(), From);
+    assert(LookupTablePtr);
+    return FromTU->import(*LookupTablePtr, ToAST.get(), From);
   }
 
   QualType ImportType(QualType FromType, Decl *TUDecl, Language ToLang) {
-    lazyInitToAST(ToLang);
+    lazyInitToAST(ToLang, "", OutputFileName);
     TU *FromTU = findFromTU(TUDecl);
-    return FromTU->import(ToAST.get(), FromType);
+    assert(LookupTablePtr);
+    return FromTU->import(*LookupTablePtr, ToAST.get(), FromType);
    }
 
   ~ASTImporterTestBase() {
     if (!::testing::Test::HasFailure()) return;
 
     for (auto &Tu : FromTUs) {
       assert(Tu.Unit);
       llvm::errs() << "FromAST:\n";
auto *ToClass = FirstDeclMatcher<CXXRecordDecl>().match(
         ToTU, ClassMatcher);
 
     ASSERT_EQ(DeclCounter<CXXMethodDecl>().match(ToClass, MethodMatcher), 1u);
 
     {
       CXXMethodDecl *Method =
           FirstDeclMatcher<CXXMethodDecl>().match(ToClass, MethodMatcher);
       ToClass->removeDecl(Method);
+      LookupTablePtr->remove(Method);
     }
 
     ASSERT_EQ(DeclCounter<CXXMethodDecl>().match(ToClass, MethodMatcher), 0u);
 
     Decl *ImportedClass = nullptr;
     {
       Decl *FromTU = getTuDecl(Code, Lang_CXX11, "input1.cc");
       auto *FromClass = FirstDeclMatcher<CXXRecordDecl>().match(
TEST_P(ImportClasses, ImportPrototypeThenDefinition) {
   auto ToDef = LastDeclMatcher<CXXRecordDecl>().match(ToTU, Pattern);
   EXPECT_TRUE(ImportedDef == ToDef);
   EXPECT_TRUE(ImportedProto == ToProto);
   EXPECT_TRUE(ToDef->isThisDeclarationADefinition());
   EXPECT_FALSE(ToProto->isThisDeclarationADefinition());
   EXPECT_EQ(ToDef->getPreviousDecl(), ToProto);
 }
 
+TEST_P(ImportClasses, ImportDefinitionWhenProtoIsInToContext) {
+  Decl *ToTU = getToTuDecl("struct X;", Lang_C);
+  Decl *FromTU1 = getTuDecl("struct X {};", Lang_C, "input1.cc");
+  auto Pattern = recordDecl(hasName("X"), unless(isImplicit()));
+  auto ToProto = FirstDeclMatcher<RecordDecl>().match(ToTU, Pattern);
+  auto FromDef = FirstDeclMatcher<RecordDecl>().match(FromTU1, Pattern);
+
+  Decl *ImportedDef = Import(FromDef, Lang_C);
+
+  EXPECT_NE(ImportedDef, ToProto);
+  EXPECT_EQ(DeclCounter<RecordDecl>().match(ToTU, Pattern), 2u);
+  auto ToDef = LastDeclMatcher<RecordDecl>().match(ToTU, Pattern);
+  EXPECT_TRUE(ImportedDef == ToDef);
+  EXPECT_TRUE(ToDef->isThisDeclarationADefinition());
+  EXPECT_FALSE(ToProto->isThisDeclarationADefinition());
+  EXPECT_EQ(ToDef->getPreviousDecl(), ToProto);
+}
+
+TEST_P(ImportClasses, ImportDefinitionWhenProtoIsInNestedToContext) {
+  Decl *ToTU = getToTuDecl("struct A { struct X *Xp; };", Lang_C);
+  Decl *FromTU1 = getTuDecl("struct X {};", Lang_C, "input1.cc");
+  auto Pattern = recordDecl(hasName("X"), unless(isImplicit()));
+  auto ToProto = FirstDeclMatcher<RecordDecl>().match(ToTU, Pattern);
+  auto FromDef = FirstDeclMatcher<RecordDecl>().match(FromTU1, Pattern);
+
+  Decl *ImportedDef = Import(FromDef, Lang_C);
+
+  EXPECT_NE(ImportedDef, ToProto);
+  EXPECT_EQ(DeclCounter<RecordDecl>().match(ToTU, Pattern), 2u);
+  auto ToDef = LastDeclMatcher<RecordDecl>().match(ToTU, Pattern);
+  EXPECT_TRUE(ImportedDef == ToDef);
+  EXPECT_TRUE(ToDef->isThisDeclarationADefinition());
+  EXPECT_FALSE(ToProto->isThisDeclarationADefinition());
+  EXPECT_EQ(ToDef->getPreviousDecl(), ToProto);
+}
+
+TEST_P(ImportClasses, ImportDefinitionWhenProtoIsInNestedToContextCXX) {
+  Decl *ToTU = getToTuDecl("struct A { struct X *Xp; };", Lang_CXX);
+  Decl *FromTU1 = getTuDecl("struct X {};", Lang_CXX, "input1.cc");
+  auto Pattern = recordDecl(hasName("X"), unless(isImplicit()));
+  auto ToProto = FirstDeclMatcher<RecordDecl>().match(ToTU, Pattern);
+  auto FromDef = FirstDeclMatcher<RecordDecl>().match(FromTU1, Pattern);
+
+  Decl *ImportedDef = Import(FromDef, Lang_CXX);
+
+  EXPECT_NE(ImportedDef, ToProto);
+  EXPECT_EQ(DeclCounter<RecordDecl>().match(ToTU, Pattern), 2u);
+  auto ToDef = LastDeclMatcher<RecordDecl>().match(ToTU, Pattern);
+  EXPECT_TRUE(ImportedDef == ToDef);
+  EXPECT_TRUE(ToDef->isThisDeclarationADefinition());
+  EXPECT_FALSE(ToProto->isThisDeclarationADefinition());
+  EXPECT_EQ(ToDef->getPreviousDecl(), ToProto);
+}
+
+TEST_P(ImportClasses, ImportNestedPrototypeThenDefinition) {
+  Decl *FromTU0 = getTuDecl("struct A { struct X *Xp; };", Lang_C, "input0.cc");
+  Decl *FromTU1 = getTuDecl("struct X {};", Lang_C, "input1.cc");
+  auto Pattern = recordDecl(hasName("X"), unless(isImplicit()));
+  auto FromProto = FirstDeclMatcher<RecordDecl>().match(FromTU0, Pattern);
+  auto FromDef = FirstDeclMatcher<RecordDecl>().match(FromTU1, Pattern);
+
+  Decl *ImportedProto = Import(FromProto, Lang_C);
+  Decl *ImportedDef = Import(FromDef, Lang_C);
+  Decl *ToTU = ImportedDef->getTranslationUnitDecl();
+
+  EXPECT_NE(ImportedDef, ImportedProto);
+  EXPECT_EQ(DeclCounter<RecordDecl>().match(ToTU, Pattern), 2u);
+  auto ToProto = FirstDeclMatcher<RecordDecl>().match(ToTU, Pattern);
+  auto ToDef = LastDeclMatcher<RecordDecl>().match(ToTU, Pattern);
+  EXPECT_TRUE(ImportedDef == ToDef);
+  EXPECT_TRUE(ImportedProto == ToProto);
+  EXPECT_TRUE(ToDef->isThisDeclarationADefinition());
+  EXPECT_FALSE(ToProto->isThisDeclarationADefinition());
+  EXPECT_EQ(ToDef->getPreviousDecl(), ToProto);
+}
+
 struct ImportClassTemplates : ASTImporterTestBase {};
 
 TEST_P(ImportClassTemplates,
        PrototypeShouldBeImportedAsAPrototypeWhenThereIsNoDefinition) {
   Decl *FromTU = getTuDecl("template <class T> class X;", Lang_CXX);
   auto Pattern = classTemplateDecl(hasName("X"), unless(isImplicit()));
   auto FromD = FirstDeclMatcher<ClassTemplateDecl>().match(FromTU, Pattern);
 
Decl *FromTU1 = getTuDecl(
       Lang_CXX, "input1.cc");
   auto *Definition = FirstDeclMatcher<CXXRecordDecl>().match(
       FromTU1, cxxRecordDecl(hasName("F")));
   auto *ImportedDef = Import(Definition, Lang_CXX);
   EXPECT_TRUE(ImportedDef->getPreviousDecl());
   EXPECT_EQ(ImportedFwd, ImportedDef->getPreviousDecl());
 }
 
+TEST_P(ASTImporterTestBase, FriendFunInClassTemplate) {
+  auto *Code = R"(
+  template <class T>
+  struct X {
+    friend void foo(){}
+  };
+      )";
+  TranslationUnitDecl *ToTU = getToTuDecl(Code, Lang_CXX);
+  auto *ToFoo = FirstDeclMatcher<FunctionDecl>().match(
+      ToTU, functionDecl(hasName("foo")));
+
+  TranslationUnitDecl *FromTU = getTuDecl(Code, Lang_CXX, "input.cc");
+  auto *FromFoo = FirstDeclMatcher<FunctionDecl>().match(
+      FromTU, functionDecl(hasName("foo")));
+  auto *ImportedFoo = Import(FromFoo, Lang_CXX);
+  EXPECT_EQ(ImportedFoo, ToFoo);
+}
+
 struct DeclContextTest : ASTImporterTestBase {};
 
 TEST_P(DeclContextTest, removeDeclOfClassTemplateSpecialization) {
   Decl *TU = getTuDecl(
       R"(
       namespace NS {
 
       template <typename T>
auto *FromD = FirstDeclMatcher<TypedefNameDecl>().match(FromTU,
       typedefNameDecl(hasName("U")));
   ASSERT_FALSE(FromD->getUnderlyingType()->isIncompleteType());
 
   // The imported type should be complete.
   auto *ImportedD = cast<TypedefNameDecl>(Import(FromD, Lang_CXX11));
   EXPECT_FALSE(ImportedD->getUnderlyingType()->isIncompleteType());
 }
 
+struct ASTImporterLookupTableTest : ASTImporterTestBase {};
+
+TEST_P(ASTImporterLookupTableTest, OneDecl) {
+  auto *ToTU = getToTuDecl("int a;", Lang_CXX);
+  auto *D = FirstDeclMatcher<VarDecl>().match(ToTU, varDecl(hasName("a")));
+  ASTImporterLookupTable LT(*ToTU);
+  auto Res = LT.lookup(ToTU, D->getDeclName());
+  ASSERT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), D);
+}
+
+static Decl *findInDeclListOfDC(DeclContext *DC, DeclarationName Name) {
+  for (Decl *D : DC->decls()) {
+    if (auto *ND = dyn_cast<NamedDecl>(D))
+      if (ND->getDeclName() == Name)
+        return ND;
+  }
+  return nullptr;
+};
+
+TEST_P(ASTImporterLookupTableTest,
+    FriendWhichIsnotFoundByNormalLookupShouldBeFoundByImporterSpecificLookup) {
+  auto *Code = R"(
+  template <class T>
+  struct X {
+    friend void foo(){}
+  };
+      )";
+  TranslationUnitDecl *ToTU = getToTuDecl(Code, Lang_CXX);
+  auto *X = FirstDeclMatcher<ClassTemplateDecl>().match(
+      ToTU, classTemplateDecl(hasName("X")));
+  auto *Foo = FirstDeclMatcher<FunctionDecl>().match(
+      ToTU, functionDecl(hasName("foo")));
+  DeclContext *FooDC = Foo->getDeclContext();
+  DeclContext *FooLexicalDC = Foo->getLexicalDeclContext();
+  ASSERT_EQ(cast<Decl>(FooLexicalDC), X->getTemplatedDecl());
+  ASSERT_EQ(cast<Decl>(FooDC), ToTU);
+  DeclarationName FooName = Foo->getDeclName();
+
+  // Cannot find in the LookupTable of its DC (TUDecl)
+  SmallVector<NamedDecl *, 2> FoundDecls;
+  FooDC->getRedeclContext()->localUncachedLookup(FooName, FoundDecls);
+  EXPECT_EQ(FoundDecls.size(), 0u);
+
+  // Cannot find in the LookupTable of its LexicalDC (X)
+  FooLexicalDC->getRedeclContext()->localUncachedLookup(FooName, FoundDecls);
+  EXPECT_EQ(FoundDecls.size(), 0u);
+
+  // Can't find in the list of Decls of the DC.
+  EXPECT_EQ(findInDeclListOfDC(FooDC, FooName), nullptr);
+
+  // Can't find in the list of Decls of the LexicalDC
+  EXPECT_EQ(findInDeclListOfDC(FooLexicalDC, FooName), nullptr);
+
+  // ASTImporter specific lookup finds it.
+  ASTImporterLookupTable LT(*ToTU);
+  auto Res = LT.lookup(FooDC, Foo->getDeclName());
+  ASSERT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), Foo);
+}
+
+TEST_P(ASTImporterLookupTableTest,
+       FwdDeclStructShouldBeFoundByImporterSpecificLookup) {
+  TranslationUnitDecl *ToTU =
+      getToTuDecl("struct A { struct Foo *p; };", Lang_C);
+  auto *Foo =
+      FirstDeclMatcher<RecordDecl>().match(ToTU, recordDecl(hasName("Foo")));
+  auto *A =
+      FirstDeclMatcher<RecordDecl>().match(ToTU, recordDecl(hasName("A")));
+  DeclContext *FooDC = Foo->getDeclContext();
+  DeclContext *FooLexicalDC = Foo->getLexicalDeclContext();
+  ASSERT_EQ(cast<Decl>(FooLexicalDC), A);
+  ASSERT_EQ(cast<Decl>(FooDC), ToTU);
+  DeclarationName FooName = Foo->getDeclName();
+
+  // Cannot find in the LookupTable of its DC (TUDecl).
+  SmallVector<NamedDecl *, 2> FoundDecls;
+  FooDC->getRedeclContext()->localUncachedLookup(FooName, FoundDecls);
+  EXPECT_EQ(FoundDecls.size(), 0u);
+
+  // Cannot find in the LookupTable of its LexicalDC (A).
+  FooLexicalDC->getRedeclContext()->localUncachedLookup(FooName, FoundDecls);
+  EXPECT_EQ(FoundDecls.size(), 0u);
+
+  // Can't find in the list of Decls of the DC.
+  EXPECT_EQ(findInDeclListOfDC(FooDC, FooName), nullptr);
+
+  // Can find in the list of Decls of the LexicalDC.
+  EXPECT_EQ(findInDeclListOfDC(FooLexicalDC, FooName), Foo);
+
+  // ASTImporter specific lookup finds it.
+  ASTImporterLookupTable LT(*ToTU);
+  auto Res = LT.lookup(FooDC, Foo->getDeclName());
+  ASSERT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), Foo);
+}
+
+TEST_P(ASTImporterLookupTableTest, LookupFindsNamesInDifferentDC) {
+  TranslationUnitDecl *ToTU =
+      getToTuDecl("int V; struct A { int V; }; struct B { int V; };", Lang_C);
+  DeclarationName VName = FirstDeclMatcher<VarDecl>()
+                              .match(ToTU, varDecl(hasName("V")))
+                              ->getDeclName();
+  auto *A =
+      FirstDeclMatcher<RecordDecl>().match(ToTU, recordDecl(hasName("A")));
+  auto *B =
+      FirstDeclMatcher<RecordDecl>().match(ToTU, recordDecl(hasName("B")));
+
+  ASTImporterLookupTable LT(*ToTU);
+
+  auto Res = LT.lookup(cast<DeclContext>(A), VName);
+  ASSERT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), FirstDeclMatcher<FieldDecl>().match(
+                        ToTU, fieldDecl(hasName("V"),
+                                        hasParent(recordDecl(hasName("A"))))));
+  Res = LT.lookup(cast<DeclContext>(B), VName);
+  ASSERT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), FirstDeclMatcher<FieldDecl>().match(
+                        ToTU, fieldDecl(hasName("V"),
+                                        hasParent(recordDecl(hasName("B"))))));
+  Res = LT.lookup(ToTU, VName);
+  ASSERT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), FirstDeclMatcher<VarDecl>().match(
+                        ToTU, varDecl(hasName("V"),
+                                        hasParent(translationUnitDecl()))));
+}
+
+TEST_P(ASTImporterLookupTableTest, LookupFindsOverloadedNames) {
+  TranslationUnitDecl *ToTU = getToTuDecl(
+      R"(
+      void foo();
+      void foo(int);
+      void foo(int, int);
+      )",
+      Lang_CXX);
+
+  ASTImporterLookupTable LT(*ToTU);
+  auto *F0 = FirstDeclMatcher<FunctionDecl>().match(ToTU, functionDecl());
+  auto *F2 = LastDeclMatcher<FunctionDecl>().match(ToTU, functionDecl());
+  DeclarationName Name = F0->getDeclName();
+  auto Res = LT.lookup(ToTU, Name);
+  EXPECT_EQ(Res.size(), 3u);
+  EXPECT_EQ(Res.count(F0), 1u);
+  EXPECT_EQ(Res.count(F2), 1u);
+}
+
+static const RecordDecl * getRecordDeclOfFriend(FriendDecl *FD) {
+  QualType Ty = FD->getFriendType()->getType();
+  QualType NamedTy = cast<ElaboratedType>(Ty)->getNamedType();
+  return cast<RecordType>(NamedTy)->getDecl();
+}
+
+TEST_P(ASTImporterLookupTableTest, LookupFindsFwdFriendClassDecl) {
+  TranslationUnitDecl *ToTU = getToTuDecl(
+      R"(
+      class Y { friend class F; };
+      )",
+      Lang_CXX);
+
+  // In this case, the CXXRecordDecl is hidden, the FriendDecl is not a parent.
+  // So we must dig up the underlying CXXRecordDecl.
+  ASTImporterLookupTable LT(*ToTU);
+  auto *FriendD = FirstDeclMatcher<FriendDecl>().match(ToTU, friendDecl());
+  const RecordDecl *RD = getRecordDeclOfFriend(FriendD);
+  auto *Y = FirstDeclMatcher<CXXRecordDecl>().match(
+      ToTU, cxxRecordDecl(hasName("Y")));
+
+  DeclarationName Name = RD->getDeclName();
+  auto Res = LT.lookup(ToTU, Name);
+  EXPECT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), RD);
+
+  Res = LT.lookup(Y, Name);
+  EXPECT_EQ(Res.size(), 0u);
+}
+
+TEST_P(ASTImporterLookupTableTest, LookupFindsFwdFriendClassTemplateDecl) {
+  TranslationUnitDecl *ToTU = getToTuDecl(
+      R"(
+      class Y { template <class T> friend class F; };
+      )",
+      Lang_CXX);
+
+  ASTImporterLookupTable LT(*ToTU);
+  auto *F = FirstDeclMatcher<ClassTemplateDecl>().match(
+      ToTU, classTemplateDecl(hasName("F")));
+  DeclarationName Name = F->getDeclName();
+  auto Res = LT.lookup(ToTU, Name);
+  EXPECT_EQ(Res.size(), 2u);
+  EXPECT_EQ(Res.count(F), 1u);
+  EXPECT_EQ(Res.count(F->getTemplatedDecl()), 1u);
+}
+
+TEST_P(ASTImporterLookupTableTest, DependentFriendClass) {
+  TranslationUnitDecl *ToTU = getToTuDecl(
+      R"(
+      template <typename T>
+      class F;
+
+      template <typename T>
+      class Y {
+        friend class F<T>;
+      };
+      )",
+      Lang_CXX);
+
+  ASTImporterLookupTable LT(*ToTU);
+  auto *F = FirstDeclMatcher<ClassTemplateDecl>().match(
+      ToTU, classTemplateDecl(hasName("F")));
+  DeclarationName Name = F->getDeclName();
+  auto Res = LT.lookup(ToTU, Name);
+  EXPECT_EQ(Res.size(), 2u);
+  EXPECT_EQ(Res.count(F), 1u);
+  EXPECT_EQ(Res.count(F->getTemplatedDecl()), 1u);
+}
+
+TEST_P(ASTImporterLookupTableTest, FriendClassTemplateSpecialization) {
+  TranslationUnitDecl *ToTU = getToTuDecl(
+      R"(
+      template <typename T>
+      class F;
+
+      class Y {
+        friend class F<int>;
+      };
+      )",
+      Lang_CXX);
+
+  ASTImporterLookupTable LT(*ToTU);
+  auto *F = FirstDeclMatcher<ClassTemplateDecl>().match(
+      ToTU, classTemplateDecl(hasName("F")));
+  DeclarationName Name = F->getDeclName();
+  auto Res = LT.lookup(ToTU, Name);
+  ASSERT_EQ(Res.size(), 3u);
+  EXPECT_EQ(Res.count(F), 1u);
+  EXPECT_EQ(Res.count(F->getTemplatedDecl()), 1u);
+  EXPECT_EQ(Res.count(*F->spec_begin()), 1u);
+}
+
+TEST_P(ASTImporterLookupTableTest, LookupFindsFwdFriendFunctionDecl) {
+  TranslationUnitDecl *ToTU = getToTuDecl(
+      R"(
+      class Y { friend void F(); };
+      )",
+      Lang_CXX);
+
+  ASTImporterLookupTable LT(*ToTU);
+  auto *F =
+      FirstDeclMatcher<FunctionDecl>().match(ToTU, functionDecl(hasName("F")));
+  DeclarationName Name = F->getDeclName();
+  auto Res = LT.lookup(ToTU, Name);
+  EXPECT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), F);
+}
+
+TEST_P(ASTImporterLookupTableTest,
+       LookupFindsDeclsInClassTemplateSpecialization) {
+  TranslationUnitDecl *ToTU = getToTuDecl(
+      R"(
+      template <typename T>
+      struct X {
+        int F;
+      };
+      void foo() {
+        X<char> xc;
+      }
+      )",
+      Lang_CXX);
+
+  ASTImporterLookupTable LT(*ToTU);
+
+  auto *Template = FirstDeclMatcher<ClassTemplateDecl>().match(
+      ToTU, classTemplateDecl(hasName("X")));
+  auto *FieldInTemplate = FirstDeclMatcher<FieldDecl>().match(
+      ToTU,
+      fieldDecl(hasParent(cxxRecordDecl(hasParent(classTemplateDecl())))));
+
+  auto *Spec = FirstDeclMatcher<ClassTemplateSpecializationDecl>().match(
+      ToTU, classTemplateSpecializationDecl(hasName("X")));
+  FieldDecl *FieldInSpec = *Spec->field_begin();
+  ASSERT_TRUE(FieldInSpec);
+
+  DeclarationName Name = FieldInSpec->getDeclName();
+  auto TemplateDC = cast<DeclContext>(Template->getTemplatedDecl());
+
+  SmallVector<NamedDecl *, 2> FoundDecls;
+  TemplateDC->getRedeclContext()->localUncachedLookup(Name, FoundDecls);
+  EXPECT_EQ(FoundDecls.size(), 1u);
+  EXPECT_EQ(FoundDecls[0], FieldInTemplate);
+
+  auto Res = LT.lookup(TemplateDC, Name);
+  ASSERT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), FieldInTemplate);
+
+  cast<DeclContext>(Spec)->getRedeclContext()->localUncachedLookup(Name,
+                                                                   FoundDecls);
+  EXPECT_EQ(FoundDecls.size(), 1u);
+  EXPECT_EQ(FoundDecls[0], FieldInSpec);
+
+  Res = LT.lookup(cast<DeclContext>(Spec), Name);
+  ASSERT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), FieldInSpec);
+}
+
+TEST_P(ASTImporterLookupTableTest, LookupFindsFwdFriendFunctionTemplateDecl) {
+  TranslationUnitDecl *ToTU = getToTuDecl(
+      R"(
+      class Y { template <class T> friend void F(); };
+      )",
+      Lang_CXX);
+
+  ASTImporterLookupTable LT(*ToTU);
+  auto *F = FirstDeclMatcher<FunctionTemplateDecl>().match(
+      ToTU, functionTemplateDecl(hasName("F")));
+  DeclarationName Name = F->getDeclName();
+  auto Res = LT.lookup(ToTU, Name);
+  EXPECT_EQ(Res.size(), 2u);
+  EXPECT_EQ(Res.count(F), 1u);
+  EXPECT_EQ(Res.count(F->getTemplatedDecl()), 1u);
+}
+
+TEST_P(ASTImporterLookupTableTest, MultipleBefriendingClasses) {
+  TranslationUnitDecl *ToTU = getToTuDecl(
+      R"(
+      struct X;
+      struct A {
+        friend struct X;
+      };
+      struct B {
+        friend struct X;
+      };
+      )",
+      Lang_CXX);
+
+  ASTImporterLookupTable LT(*ToTU);
+  auto *X = FirstDeclMatcher<CXXRecordDecl>().match(
+      ToTU, cxxRecordDecl(hasName("X")));
+  auto *FriendD0 = FirstDeclMatcher<FriendDecl>().match(ToTU, friendDecl());
+  auto *FriendD1 = LastDeclMatcher<FriendDecl>().match(ToTU, friendDecl());
+  const RecordDecl *RD0 = getRecordDeclOfFriend(FriendD0);
+  const RecordDecl *RD1 = getRecordDeclOfFriend(FriendD1);
+  ASSERT_EQ(RD0, RD1);
+  ASSERT_EQ(RD1, X);
+
+  DeclarationName Name = X->getDeclName();
+  auto Res = LT.lookup(ToTU, Name);
+  EXPECT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), X);
+}
+
+TEST_P(ASTImporterLookupTableTest, EnumConstantDecl) {
+  TranslationUnitDecl *ToTU = getToTuDecl(
+      R"(
+      enum E {
+        A,
+        B
+      };
+      )",
+      Lang_C);
+
+  ASTImporterLookupTable LT(*ToTU);
+  auto *E = FirstDeclMatcher<EnumDecl>().match(ToTU, enumDecl(hasName("E")));
+  auto *A = FirstDeclMatcher<EnumConstantDecl>().match(
+      ToTU, enumConstantDecl(hasName("A")));
+
+  DeclarationName Name = A->getDeclName();
+  // Redecl context is the TU.
+  ASSERT_EQ(E->getRedeclContext(), ToTU);
+
+  SmallVector<NamedDecl *, 2> FoundDecls;
+  // Normal lookup finds in the DC.
+  E->localUncachedLookup(Name, FoundDecls);
+  EXPECT_EQ(FoundDecls.size(), 1u);
+
+  // Normal lookup finds in the Redecl context.
+  ToTU->localUncachedLookup(Name, FoundDecls);
+  EXPECT_EQ(FoundDecls.size(), 1u);
+
+  // Import specific lookup finds in the DC.
+  auto Res = LT.lookup(E, Name);
+  ASSERT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), A);
+
+  // Import specific lookup finds in the Redecl context.
+  Res = LT.lookup(ToTU, Name);
+  ASSERT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), A);
+}
+
+TEST_P(ASTImporterLookupTableTest, LookupSearchesInTheWholeRedeclChain) {
+  TranslationUnitDecl *ToTU = getToTuDecl(
+      R"(
+      namespace N {
+        int A;
+      }
+      namespace N {
+      }
+      )",
+      Lang_CXX);
+  auto *N1 =
+      LastDeclMatcher<NamespaceDecl>().match(ToTU, namespaceDecl(hasName("N")));
+  auto *A = FirstDeclMatcher<VarDecl>().match(ToTU, varDecl(hasName("A")));
+  DeclarationName Name = A->getDeclName();
+
+  ASTImporterLookupTable LT(*ToTU);
+  auto Res = LT.lookup(N1, Name);
+  ASSERT_EQ(Res.size(), 1u);
+  EXPECT_EQ(*Res.begin(), A);
+}
+
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, DeclContextTest,
                         ::testing::Values(ArgVector()), );
 
 INSTANTIATE_TEST_CASE_P(
     ParameterizedTests, CanonicalRedeclChain,
     ::testing::Values(ArgVector()),);
 
 auto DefaultTestValuesForRunOptions = ::testing::Values(
     ArgVector(),
     ArgVector{"-fdelayed-template-parsing"},
     ArgVector{"-fms-compatibility"},
     ArgVector{"-fdelayed-template-parsing", "-fms-compatibility"});
 
+INSTANTIATE_TEST_CASE_P(ParameterizedTests, ASTImporterLookupTableTest,
+                        DefaultTestValuesForRunOptions, );
+
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportExpr,
                         DefaultTestValuesForRunOptions, );
 
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportType,
                         DefaultTestValuesForRunOptions, );
 
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportDecl,
                         DefaultTestValuesForRunOptions, );
 
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, ASTImporterTestBase,
                         DefaultTestValuesForRunOptions, );
 
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportFunctions,
                         DefaultTestValuesForRunOptions, );
 
-INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportFriendFunctions,
+INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportClasses,
                         DefaultTestValuesForRunOptions, );
 
-INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportClasses,
+INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportFriendFunctions,
                         DefaultTestValuesForRunOptions, );
 
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportClassTemplates,
                         DefaultTestValuesForRunOptions, );
 
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportFriendClasses,
                         DefaultTestValuesForRunOptions, );