Fix name lookup within modules during template instantiation

[rsmith]

Summary

When we perform dependent name lookup during template instantiation, it's not sufficient to only consider names visible at the point of instantiation, because that may not include names that were visible when the template was defined. More generally, if the instantiation backtrace goes through a module M, then every declaration visible within M should be available to the instantiation. Any of those declarations might be part of the interface that M intended to export to a template that it instantiates.

The fix here has two parts:

1. If we find a non-visible declaration during name lookup during template instantiation, check whether the declaration was visible from the defining module of all entities on the active template instantiation stack. The defining module is not the owning module in all cases: we look at the module in which a template was defined, not the module in which it was first instantiated.
2. Perform pending instantiations at the end of a module, not at the end of the translation unit. This is general goodness, since it significantly cuts down the amount of redundant work that is performed in every TU importing a module, and also implicitly adds the module containing the point of instantiation to the set of modules checked for declarations in a lookup within a template instantiation.

With this change, a simple "Hello world" program now compiles with a modularized libc++ (with only one top-level module, for now -- cross-top-level-module merging of template specializations doesn't work yet).

[rsmith]

Cache computation of defining module for a template for the duration of its instantiation.

[doug.gregor]

This looks *great*. It's simpler than I was expecting.

One concern about the caching, though: we might be forced to perform instantiation before we've seen all of the imports (say, due to a constexpr function template definition getting instantiated), which means the cache could be incomplete. I suggest invalidating based on the ASTReader's current generation.

[rsmith]

Names visible in the current translation unit are always considered to be visible, so I don't think it's possible to observe the change in visible modules for the currently-being-built module. (We also never query it, since it's not an owning module for any declaration.)

[rsmith]

This was committed way back in r187167. I added a FIXME for the out-of-date cache issue in r209915.

include/clang/AST/DeclBase.h

void setTopLevelDeclInObjCContainer(bool V = true) {
     unsigned Bits = NextInContextAndBits.getInt();
     if (V)
       Bits |= TopLevelDeclInObjCContainerFlag;
     else
       Bits &= ~TopLevelDeclInObjCContainerFlag;
     NextInContextAndBits.setInt(Bits);
   }
 
-protected:
   /// \brief Whether this declaration was marked as being private to the
   /// module in which it was defined.
-  bool isModulePrivate() const { 
+  bool isModulePrivate() const {
     return NextInContextAndBits.getInt() & ModulePrivateFlag;
   }
-  
+protected:
   /// \brief Specify whether this declaration was marked as being private
   /// to the module in which it was defined.
   void setModulePrivate(bool MP = true) {
     unsigned Bits = NextInContextAndBits.getInt();
     if (MP)
       Bits |= ModulePrivateFlag;
     else
       Bits &= ~ModulePrivateFlag;

include/clang/Basic/Module.h

 /// \brief Defines the clang::Module class, which describes a module in the
 /// source code.
 ///
 //===----------------------------------------------------------------------===//
 #ifndef LLVM_CLANG_BASIC_MODULE_H
 #define LLVM_CLANG_BASIC_MODULE_H
 
 #include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include <string>
 #include <utility>
private:
   const FileEntry *ASTFile;
 
   /// \brief The top-level headers associated with this module.
   llvm::SmallSetVector<const FileEntry *, 2> TopHeaders;
 
   /// \brief top-level header filenames that aren't resolved to FileEntries yet.
   std::vector<std::string> TopHeaderNames;
 
+  /// \brief Cache of modules visible to lookup in this module.
+  mutable llvm::DenseSet<const Module*> VisibleModulesCache;
+
 public:
   /// \brief The headers that are part of this module.
   SmallVector<const FileEntry *, 2> NormalHeaders;
 
   /// \brief The headers that are explicitly excluded from this module.
   SmallVector<const FileEntry *, 2> ExcludedHeaders;
 
   /// \brief The headers that are private to this module.
public:
   void addRequirement(StringRef Feature, const LangOptions &LangOpts,
                       const TargetInfo &Target);
 
   /// \brief Find the submodule with the given name.
   ///
   /// \returns The submodule if found, or NULL otherwise.
   Module *findSubmodule(StringRef Name) const;
 
+  /// \brief Determine whether the specified module would be visible to
+  /// a lookup at the end of this module.
+  bool isModuleVisible(const Module *M) const {
+    if (VisibleModulesCache.empty())
+      buildVisibleModulesCache();
+    return VisibleModulesCache.count(M);
+  }
+
   typedef std::vector<Module *>::iterator submodule_iterator;
   typedef std::vector<Module *>::const_iterator submodule_const_iterator;
   
   submodule_iterator submodule_begin() { return SubModules.begin(); }
   submodule_const_iterator submodule_begin() const {return SubModules.begin();}
   submodule_iterator submodule_end()   { return SubModules.end(); }
   submodule_const_iterator submodule_end() const { return SubModules.end(); }
 
   /// \brief Returns the exported modules based on the wildcard restrictions.
   void getExportedModules(SmallVectorImpl<Module *> &Exported) const;
 
   static StringRef getModuleInputBufferName() {
     return "<module-includes>";
   }
 
   /// \brief Print the module map for this module to the given stream. 
   ///
   void print(raw_ostream &OS, unsigned Indent = 0) const;
   
   /// \brief Dump the contents of this module to the given output stream.
   void dump() const;
+
+private:
+  void buildVisibleModulesCache() const;
 };
 
 } // end namespace clang
 
 
 #endif // LLVM_CLANG_BASIC_MODULE_H

include/clang/Sema/Lookup.h

public:
   /// \brief Return the base paths structure that's associated with
   /// these results, or null if none is.
   CXXBasePaths *getBasePaths() const {
     return Paths;
   }
 
   /// \brief Determine whether the given declaration is visible to the
   /// program.
-  static bool isVisible(NamedDecl *D) {
+  static bool isVisible(Sema &SemaRef, NamedDecl *D) {
     // If this declaration is not hidden, it's visible.
     if (!D->isHidden())
       return true;
-    
-    // FIXME: We should be allowed to refer to a module-private name from 
-    // within the same module, e.g., during template instantiation.
-    // This requires us know which module a particular declaration came from.
+    if (SemaRef.ActiveTemplateInstantiations.empty())
       return false;
+
+    // During template instantiation, we can refer to hidden declarations, if
+    // they were visible in any module along the path of instantiation.
+    return isVisibleSlow(SemaRef, D);
   }
-  
   /// \brief Retrieve the accepted (re)declaration of the given declaration,
   /// if there is one.
   NamedDecl *getAcceptableDecl(NamedDecl *D) const {
     if (!D->isInIdentifierNamespace(IDNS))
       return 0;
-    
-    if (isHiddenDeclarationVisible() || isVisible(D))
+    if (isHiddenDeclarationVisible() || isVisible(SemaRef, D))
       return D;
-    
     return getAcceptableDeclSlow(D);
   }
-  
 private:
+  static bool isVisibleSlow(Sema &SemaRef, NamedDecl *D);
   NamedDecl *getAcceptableDeclSlow(NamedDecl *D) const;
-public:
-  
+public:
   /// \brief Returns the identifier namespace mask for this lookup.
   unsigned getIdentifierNamespace() const {
     return IDNS;
   }
 
   /// \brief Returns whether these results arose from performing a
   /// lookup into a class.
   bool isClassLookup() const {

include/clang/Sema/Sema.h

   ///
   /// This vector is treated as a stack. As one template instantiation
   /// requires another template instantiation, additional
   /// instantiations are pushed onto the stack up to a
   /// user-configurable limit LangOptions::InstantiationDepth.
   SmallVector<ActiveTemplateInstantiation, 16>
     ActiveTemplateInstantiations;
 
+  /// \brief Extra modules inspected when performing a lookup during a template
+  /// instantiation. Computed lazily.
+  SmallVector<Module*, 16> ActiveTemplateInstantiationLookupModules;
+
+  /// \brief Cache of additional modules that should be used for name lookup
+  /// within the current template instantiation. Computed lazily; use
+  /// getLookupModules() to get a complete set.
+  llvm::DenseSet<Module*> LookupModulesCache;
+
+  /// \brief Get the set of additional modules that should be checked during
+  /// name lookup. A module and its imports become visible when instanting a
+  /// template defined within it.
+  llvm::DenseSet<Module*> &getLookupModules();
+
   /// \brief Whether we are in a SFINAE context that is not associated with
   /// template instantiation.
   ///
   /// This is used when setting up a SFINAE trap (\c see SFINAETrap) outside
   /// of a template instantiation or template argument deduction.
   bool InNonInstantiationSFINAEContext;
 
   /// \brief The number of ActiveTemplateInstantiation entries in

lib/Basic/Module.cpp

for (unsigned I = 0, N = Imports.size(); I != N; ++I) {
 
     if (!Acceptable)
       continue;
 
     Exported.push_back(Mod);
   }
 }
 
+void Module::buildVisibleModulesCache() const {
+  assert(VisibleModulesCache.empty() && "cache does not need building");
+
+  // This module is visible to itself.
+  VisibleModulesCache.insert(this);
+
+  llvm::SmallVector<Module*, 4> Exported;
+  for (unsigned I = 0, N = Imports.size(); I != N; ++I) {
+    // Every imported module is visible.
+    VisibleModulesCache.insert(Imports[I]);
+
+    // Every module exported by an imported module is visible.
+    Imports[I]->getExportedModules(Exported);
+    VisibleModulesCache.insert(Exported.begin(), Exported.end());
+    Exported.clear();
+  }
+}
+
 void Module::print(raw_ostream &OS, unsigned Indent) const {
   OS.indent(Indent);
   if (IsFramework)
     OS << "framework ";
   if (IsExplicit)
     OS << "explicit ";
   OS << "module " << Name;
 

lib/Sema/Sema.cpp

void Sema::ActOnEndOfTranslationUnit() {
   assert(DelayedDiagnostics.getCurrentPool() == NULL
          && "reached end of translation unit with a pool attached?");
 
   // If code completion is enabled, don't perform any end-of-translation-unit
   // work.
   if (PP.isCodeCompletionEnabled())
     return;
 
-  // Only complete translation units define vtables and perform implicit
-  // instantiations.
-  if (TUKind == TU_Complete) {
+  // Complete translation units and modules define vtables and perform implicit
+  // instantiations. PCH files do not.
+  if (TUKind != TU_Prefix) {
     DiagnoseUseOfUnimplementedSelectors();
 
     // If any dynamic classes have their key function defined within
     // this translation unit, then those vtables are considered "used" and must
     // be emitted.
     for (DynamicClassesType::iterator I = DynamicClasses.begin(ExternalSource),
                                       E = DynamicClasses.end();
          I != E; ++I) {
if (TUKind != TU_Prefix) {
     DefineUsedVTables();
 
     // C++: Perform implicit template instantiations.
     //
     // FIXME: When we perform these implicit instantiations, we do not
     // carefully keep track of the point of instantiation (C++ [temp.point]).
     // This means that name lookup that occurs within the template
     // instantiation will always happen at the end of the translation unit,
-    // so it will find some names that should not be found. Although this is
-    // common behavior for C++ compilers, it is technically wrong. In the
-    // future, we either need to be able to filter the results of name lookup
-    // or we need to perform template instantiations earlier.
+    // so it will find some names that are not required to be found. This is
+    // valid, but we could do better by diagnosing if an instantiation uses a
+    // name that was not visible at its first point of instantiation.
     PerformPendingInstantiations();
   }
 
   // Remove file scoped decls that turned out to be used.
   UnusedFileScopedDecls.erase(
       std::remove_if(UnusedFileScopedDecls.begin(0, true),
                      UnusedFileScopedDecls.end(),
                      std::bind1st(std::ptr_fun(ShouldRemoveFromUnused), this)),

lib/Sema/SemaLookup.cpp

assert((Paths != NULL) == (ResultKind == Ambiguous &&
                               Ambiguity == AmbiguousBaseSubobjects)));
 }
 
 // Necessary because CXXBasePaths is not complete in Sema.h
 void LookupResult::deletePaths(CXXBasePaths *Paths) {
   delete Paths;
 }
 
-static NamedDecl *getVisibleDecl(NamedDecl *D);
-
-NamedDecl *LookupResult::getAcceptableDeclSlow(NamedDecl *D) const {
-  return getVisibleDecl(D);
-}
-
 /// Resolves the result kind of this lookup.
 void LookupResult::resolveKind() {
   unsigned N = Decls.size();
 
   // Fast case: no possible ambiguity.
   if (N == 0) {
     assert(ResultKind == NotFound || ResultKind == NotFoundInCurrentInstantiation);
     return;
for (; S; S = S->getParent()) {
 
     if (R.isForRedeclaration() && Ctx && !Ctx->isTransparentContext())
       return false;
   }
 
   return !R.empty();
 }
 
+/// \brief Find the declaration that a class temploid member specialization was
+/// instantiated from, or the member itself if it is an explicit specialization.
+static Decl *getInstantiatedFrom(Decl *D, MemberSpecializationInfo *MSInfo) {
+  return MSInfo->isExplicitSpecialization() ? D : MSInfo->getInstantiatedFrom();
+}
+
+/// \brief Find the module in which the given declaration was defined.
+static Module *getDefiningModule(Decl *Entity) {
+  if (FunctionDecl *FD = dyn_cast<FunctionDecl>(Entity)) {
+    // If this function was instantiated from a template, the defining module is
+    // the module containing the pattern.
+    if (FunctionDecl *Pattern = FD->getTemplateInstantiationPattern())
+      Entity = Pattern;
+  } else if (CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(Entity)) {
+    // If it's a class template specialization, find the template or partial
+    // specialization from which it was instantiated.
+    if (ClassTemplateSpecializationDecl *SpecRD =
+            dyn_cast<ClassTemplateSpecializationDecl>(RD)) {
+      llvm::PointerUnion<ClassTemplateDecl*,
+                         ClassTemplatePartialSpecializationDecl*> From =
+          SpecRD->getInstantiatedFrom();
+      if (ClassTemplateDecl *FromTemplate = From.dyn_cast<ClassTemplateDecl*>())
+        Entity = FromTemplate->getTemplatedDecl();
+      else if (From)
+        Entity = From.get<ClassTemplatePartialSpecializationDecl*>();
+      // Otherwise, it's an explicit specialization.
+    } else if (MemberSpecializationInfo *MSInfo =
+                   RD->getMemberSpecializationInfo())
+      Entity = getInstantiatedFrom(RD, MSInfo);
+  } else if (EnumDecl *ED = dyn_cast<EnumDecl>(Entity)) {
+    if (MemberSpecializationInfo *MSInfo = ED->getMemberSpecializationInfo())
+      Entity = getInstantiatedFrom(ED, MSInfo);
+  } else if (VarDecl *VD = dyn_cast<VarDecl>(Entity)) {
+    // FIXME: Map from variable template specializations back to the template.
+    if (MemberSpecializationInfo *MSInfo = VD->getMemberSpecializationInfo())
+      Entity = getInstantiatedFrom(VD, MSInfo);
+  }
+
+  // Walk up to the containing context. That might also have been instantiated
+  // from a template.
+  DeclContext *Context = Entity->getDeclContext();
+  if (Context->isFileContext())
+    return Entity->getOwningModule();
+  return getDefiningModule(cast<Decl>(Context));
+}
+
+llvm::DenseSet<Module*> &Sema::getLookupModules() {
+  unsigned N = ActiveTemplateInstantiations.size();
+  for (unsigned I = ActiveTemplateInstantiationLookupModules.size();
+       I != N; ++I) {
+    Module *M = getDefiningModule(ActiveTemplateInstantiations[I].Entity);
+    if (M && !LookupModulesCache.insert(M).second)
+      M = 0;
+    ActiveTemplateInstantiationLookupModules.push_back(M);
+  }
+  return LookupModulesCache;
+}
+
+/// \brief Determine whether a declaration is visible to name lookup.
+///
+/// This routine determines whether the declaration D is visible in the current
+/// lookup context, taking into account the current template instantiation
+/// stack. During template instantiation, a declaration is visible if it is
+/// visible from a module containing any entity on the template instantiation
+/// path (by instantiating a template, you allow it to see the declarations that
+/// your module can see, including those later on in your module).
+bool LookupResult::isVisibleSlow(Sema &SemaRef, NamedDecl *D) {
+  assert(D->isHidden() && !SemaRef.ActiveTemplateInstantiations.empty() &&
+         "should not call this: not in slow case");
+  Module *DeclModule = D->getOwningModule();
+  assert(DeclModule && "hidden decl not from a module");
+
+  // Find the extra places where we need to look.
+  llvm::DenseSet<Module*> &LookupModules = SemaRef.getLookupModules();
+  if (LookupModules.empty())
+    return false;
+
+  // If our lookup set contains the decl's module, it's visible.
+  if (LookupModules.count(DeclModule))
+    return true;
+
+  // If the declaration isn't exported, it's not visible in any other module.
+  if (D->isModulePrivate())
+    return false;
+
+  // Check whether DeclModule is transitively exported to an import of
+  // the lookup set.
+  for (llvm::DenseSet<Module *>::iterator I = LookupModules.begin(),
+                                          E = LookupModules.end();
+       I != E; ++I)
+    if ((*I)->isModuleVisible(DeclModule))
+      return true;
+  return false;
+}
+
 /// \brief Retrieve the visible declaration corresponding to D, if any.
 ///
 /// This routine determines whether the declaration D is visible in the current
 /// module, with the current imports. If not, it checks whether any
 /// redeclaration of D is visible, and if so, returns that declaration.
-/// 
+///
 /// \returns D, or a visible previous declaration of D, whichever is more recent
 /// and visible. If no declaration of D is visible, returns null.
-static NamedDecl *getVisibleDecl(NamedDecl *D) {
-  if (LookupResult::isVisible(D))
-    return D;
-  
+NamedDecl *LookupResult::getAcceptableDeclSlow(NamedDecl *D) const {
+  assert(!isVisible(SemaRef, D) && "not in slow case");
   for (Decl::redecl_iterator RD = D->redecls_begin(), RDEnd = D->redecls_end();
        RD != RDEnd; ++RD) {
     if (NamedDecl *ND = dyn_cast<NamedDecl>(*RD)) {
-      if (LookupResult::isVisible(ND))
+      if (isVisible(SemaRef, ND))
         return ND;
     }
   }
-  
   return 0;
 }
 
 /// @brief Perform unqualified name lookup starting from a given
 /// scope.
 ///
 /// Unqualified name lookup (C++ [basic.lookup.unqual], C99 6.2.1) is
 /// used to find names within the current scope. For example, 'x' in
if (NameKind == Sema::LookupRedeclarationWithLinkage) {
       // Find the nearest non-transparent declaration scope.
       while (!(S->getFlags() & Scope::DeclScope) ||
              (S->getEntity() &&
               static_cast<DeclContext *>(S->getEntity())
                 ->isTransparentContext()))
         S = S->getParent();
     }
 
-    unsigned IDNS = R.getIdentifierNamespace();
-
     // Scan up the scope chain looking for a decl that matches this
     // identifier that is in the appropriate namespace.  This search
     // should not take long, as shadowing of names is uncommon, and
     // deep shadowing is extremely uncommon.
     bool LeftStartingScope = false;
 
     for (IdentifierResolver::iterator I = IdResolver.begin(Name),
                                    IEnd = IdResolver.end();
          I != IEnd; ++I)
-      if ((*I)->isInIdentifierNamespace(IDNS)) {
+      if (NamedDecl *D = R.getAcceptableDecl(*I)) {
         if (NameKind == LookupRedeclarationWithLinkage) {
           // Determine whether this (or a previous) declaration is
           // out-of-scope.
           if (!LeftStartingScope && !S->isDeclScope(*I))
             LeftStartingScope = true;
 
           // If we found something outside of our starting scope that
           // does not have linkage, skip it.
           if (LeftStartingScope && !((*I)->hasLinkage()))
             continue;
         }
         else if (NameKind == LookupObjCImplicitSelfParam &&
                  !isa<ImplicitParamDecl>(*I))
           continue;
-        
-        // If this declaration is module-private and it came from an AST
-        // file, we can't see it.
-        NamedDecl *D = R.isHiddenDeclarationVisible()? *I : getVisibleDecl(*I);
-        if (!D)
-          continue;
-                
         R.addDecl(D);
 
         // Check whether there are any other declarations with the same name
         // and in the same scope.
         if (I != IEnd) {
           // Find the scope in which this declaration was declared (if it
           // actually exists in a Scope).
           while (S && !S->isDeclScope(D))
for (IdentifierResolver::iterator I = IdResolver.begin(Name),
                 break;
             } else {
               // Match based on DeclContext.
               DeclContext *LastDC 
                 = (*LastI)->getDeclContext()->getRedeclContext();
               if (!LastDC->Equals(DC))
                 break;
             }
-            
-            // If the declaration isn't in the right namespace, skip it.
-            if (!(*LastI)->isInIdentifierNamespace(IDNS))
-              continue;
-                        
-            D = R.isHiddenDeclarationVisible()? *LastI : getVisibleDecl(*LastI);
-            if (D)
-              R.addDecl(D);
+            // If the declaration is in the right namespace and visible, add it.
+            if (NamedDecl *LastD = R.getAcceptableDecl(*LastI))
+              R.addDecl(LastD);
           }
 
           R.resolveKind();
         }
         return true;
       }
   } else {
     // Perform C++ unqualified name lookup.

lib/Sema/SemaTemplateInstantiate.cpp

 void Sema::InstantiatingTemplate::Clear() {
   if (!Invalid) {
     if (!SemaRef.ActiveTemplateInstantiations.back().isInstantiationRecord()) {
       assert(SemaRef.NonInstantiationEntries > 0);
       --SemaRef.NonInstantiationEntries;
     }
     SemaRef.InNonInstantiationSFINAEContext
       = SavedInNonInstantiationSFINAEContext;
+
+    // Name lookup no longer looks in this template's defining module.
+    assert(SemaRef.ActiveTemplateInstantiations.size() >=
+           SemaRef.ActiveTemplateInstantiationLookupModules.size() &&
+           "forgot to remove a lookup module for a template instantiation");
+    if (SemaRef.ActiveTemplateInstantiations.size() ==
+        SemaRef.ActiveTemplateInstantiationLookupModules.size()) {
+      if (Module *M = SemaRef.ActiveTemplateInstantiationLookupModules.back())
+        SemaRef.LookupModulesCache.erase(M);
+      SemaRef.ActiveTemplateInstantiationLookupModules.pop_back();
+    }
+
     SemaRef.ActiveTemplateInstantiations.pop_back();
     Invalid = true;
   }
 }
 
 bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
                                         SourceLocation PointOfInstantiation,
                                            SourceRange InstantiationRange) {

lib/Sema/SemaType.cpp

bool Sema::RequireCompleteTypeImpl(SourceLocation Loc, QualType T,
   //
   //  assert(!T->isDependentType() &&
   //         "Can't ask whether a dependent type is complete");
 
   // If we have a complete type, we're done.
   NamedDecl *Def = 0;
   if (!T->isIncompleteType(&Def)) {
     // If we know about the definition but it is not visible, complain.
-    if (!Diagnoser.Suppressed && Def && !LookupResult::isVisible(Def)) {
+    if (!Diagnoser.Suppressed && Def && !LookupResult::isVisible(*this, Def)) {
       // Suppress this error outside of a SFINAE context if we've already
       // emitted the error once for this type. There's no usefulness in
       // repeating the diagnostic.
       // FIXME: Add a Fix-It that imports the corresponding module or includes
       // the header.
       Module *Owner = Def->getOwningModule();
       Diag(Loc, diag::err_module_private_definition)
         << T << Owner->getFullModuleName();

test/Modules/Inputs/cxx-templates-a.h

 @import cxx_templates_common;
 
 template<typename T> T f() { return T(); }
 template<typename T> T f(T);
 namespace N {
   template<typename T> T f() { return T(); }
   template<typename T> T f(T);
 }
 
 template<int N> int template_param_kinds_1();
 template<template<typename T, int, int> class> int template_param_kinds_2();
 template<template<typename T, typename U, T> class> int template_param_kinds_3();
 
 template<typename T> struct SomeTemplate<T*>;
 template<typename T> struct SomeTemplate<T*> {};
 typedef SomeTemplate<int*> SomeTemplateIntPtr;
+
+template<typename T> void PerformDelayedLookup(T &t) {
+  t.f();
+  typename T::Inner inner;
+  FoundByADL(t);
+}

test/Modules/Inputs/cxx-templates-b-impl.h

+struct DefinedInBImpl {
+  void f();
+  struct Inner {};
+  friend void FoundByADL(DefinedInBImpl);
+};

test/Modules/Inputs/cxx-templates-b.h

 @import cxx_templates_common;
 
 template<typename T> T f();
 template<typename T> T f(T t) { return t; }
 namespace N {
   template<typename T> T f();
   template<typename T> T f(T t) { return t; }
 }
 
 template<typename> int template_param_kinds_1();
 template<template<typename, int, int...> class> int template_param_kinds_2();
 template<template<typename T, typename U, U> class> int template_param_kinds_3();
 
 template<typename T> struct SomeTemplate<T&> {};
 template<typename T> struct SomeTemplate<T&>;
 typedef SomeTemplate<int&> SomeTemplateIntRef;
+
+extern DefinedInCommon &defined_in_common;
+
+@import cxx_templates_b_impl;
+
+template<typename T, typename> struct Identity { typedef T type; };
+template<typename T> void UseDefinedInBImpl() {
+  typename Identity<DefinedInBImpl, T>::type dependent;
+  FoundByADL(dependent);
+  typename Identity<DefinedInBImpl, T>::type::Inner inner;
+  dependent.f();
+}
+
+extern DefinedInBImpl &defined_in_b_impl;
+
+@import cxx_templates_a;
+template<typename T> void UseDefinedInBImplIndirectly(T &v) {
+  PerformDelayedLookup(v);
+}
+
+void TriggerInstantiation() {
+  UseDefinedInBImpl<void>();
+}

test/Modules/Inputs/cxx-templates-common.h

 template<typename T> struct SomeTemplate {};
+
+struct DefinedInCommon {
+  void f();
+  struct Inner {};
+  friend void FoundByADL(DefinedInCommon);
+};

test/Modules/Inputs/module.map

 module cxx_templates_common {
   header "cxx-templates-common.h"
 }
 
 module cxx_templates_a {
   header "cxx-templates-a.h"
 }
 
+module cxx_templates_b_impl {
+  header "cxx-templates-b-impl.h"
+}
+
 module cxx_templates_b {
   header "cxx-templates-b.h"
 }
 
 module cxx_decls {
   module unimported {
     header "cxx-decls-unimported.h"
   }

test/Modules/cxx-templates.cpp

void g() {
   f(); // expected-error {{no matching function}}
   // expected-note@Inputs/cxx-templates-b.h:3 {{couldn't infer template argument}}
   // expected-note@Inputs/cxx-templates-b.h:4 {{requires single argument}}
 
   N::f(0);
   N::f<double>(1.0);
   N::f<int>();
   N::f(); // expected-error {{no matching function}}
-  // expected-note@Inputs/cxx-templates-a.h:6 {{couldn't infer template argument}}
-  // expected-note@Inputs/cxx-templates-a.h:7 {{requires 1 argument, but 0 were provided}}
+  // expected-note@Inputs/cxx-templates-b.h:6 {{couldn't infer template argument}}
+  // expected-note@Inputs/cxx-templates-b.h:7 {{requires single argument 't'}}
 
   template_param_kinds_1<0>(); // ok, from cxx-templates-a.h
   template_param_kinds_1<int>(); // ok, from cxx-templates-b.h
 
   template_param_kinds_2<Tmpl_T_C>(); // expected-error {{no matching function}}
   // expected-note@Inputs/cxx-templates-a.h:11 {{invalid explicitly-specified argument}}
   // expected-note@Inputs/cxx-templates-b.h:11 {{invalid explicitly-specified argument}}
 
   template_param_kinds_2<Tmpl_T_I_I>(); // expected-error {{ambiguous}}
   // expected-note@Inputs/cxx-templates-a.h:11 {{candidate}}
   // expected-note@Inputs/cxx-templates-b.h:11 {{candidate}}
 
   // FIXME: This should be valid, but we incorrectly match the template template
   // argument against both template template parameters.
   template_param_kinds_3<Tmpl_T_T_A>(); // expected-error {{ambiguous}}
   // expected-note@Inputs/cxx-templates-a.h:12 {{candidate}}
   // expected-note@Inputs/cxx-templates-b.h:12 {{candidate}}
   template_param_kinds_3<Tmpl_T_T_B>(); // expected-error {{ambiguous}}
   // expected-note@Inputs/cxx-templates-a.h:12 {{candidate}}
   // expected-note@Inputs/cxx-templates-b.h:12 {{candidate}}
+
+  // Trigger the instantiation of a template in 'a' that uses a type defined in
+  // 'common'. That type is not visible here.
+  PerformDelayedLookup(defined_in_common);
+
+  // Trigger the instantiation of a template in 'b' that uses a type defined in
+  // 'b_impl'. That type is not visible here.
+  UseDefinedInBImpl<int>();
+
+  // Trigger the instantiation of a template in 'a' that uses a type defined in
+  // 'b_impl', via a template defined in 'b'. Since the type is visible from
+  // within 'b', the instantiation succeeds.
+  UseDefinedInBImplIndirectly(defined_in_b_impl);
+
+  // Trigger the instantiation of a template in 'a' that uses a type defined in
+  // 'b_impl'. That type is not visible here, nor in 'a'. This fails; there is
+  // no reason why DefinedInBImpl should be visible here.
+  // expected-error@Inputs/cxx-templates-a.h:19 {{definition of 'DefinedInBImpl' must be imported}}
+  // expected-note@Inputs/cxx-templates-b-impl.h:1 {{definition is here}}
+  PerformDelayedLookup(defined_in_b_impl); // expected-note {{in instantiation of}}
 }
 
 @import cxx_templates_common;
 
 typedef SomeTemplate<int*> SomeTemplateIntPtr;
 typedef SomeTemplate<int&> SomeTemplateIntRef;
 SomeTemplate<char*> some_template_char_ptr;
 SomeTemplate<char&> some_template_char_ref;
 
 // FIXME: There should only be two 'f's here.
 // CHECK-GLOBAL:      DeclarationName 'f'
 // CHECK-GLOBAL-NEXT: |-FunctionTemplate {{.*}} 'f'
 // CHECK-GLOBAL-NEXT: |-FunctionTemplate {{.*}} 'f'
 // CHECK-GLOBAL-NEXT: |-FunctionTemplate {{.*}} 'f'
 // CHECK-GLOBAL-NEXT: `-FunctionTemplate {{.*}} 'f'
 
-// FIXME: There should only be two 'f's here.
 // CHECK-NAMESPACE-N:      DeclarationName 'f'
 // CHECK-NAMESPACE-N-NEXT: |-FunctionTemplate {{.*}} 'f'
-// CHECK-NAMESPACE-N-NEXT: |-FunctionTemplate {{.*}} 'f'
-// CHECK-NAMESPACE-N-NEXT: |-FunctionTemplate {{.*}} 'f'
 // CHECK-NAMESPACE-N-NEXT: `-FunctionTemplate {{.*}} 'f'