Do not merge LocalInstantiationScope for template specialization

[yaxunl]

Summary

A lambda in a function template may be recursively instantiated as the following example:

template <unsigned v>
struct Number
{
   static constexpr unsigned value = v;
};

template <unsigned IBegin = 0,
          unsigned IEnd = 1>
constexpr auto fun1(Number<IBegin> = Number<0>{}, Number<IEnd>  = Number<1>{})
{
  auto f = [&](auto fs, auto i) {
    if constexpr(i.value > 0)
    {
      return fs(fs, Number<IBegin>{});
    }
  };

  return f(f, Number<IEnd>{});
}


void fun2() {
  fun1();
}

The recursive lambda will cause a lambda function instantiated twice, one inside another.
The inner LocalInstantiationScope should not be marked as MergeWithParentScope
since it already has references to locals properly substituted, otherwise it causes
assertion due to the check for duplicate locals in merged LocalInstantiationScope.

[tra]

Godbolt appears to be OK with the code for both gcc and clang: https://godbolt.org/z/enec44

Debug build does assert here:

clang++: /work/llvm/repo/clang/lib/Sema/SemaTemplateInstantiate.cpp:3630: void clang::LocalInstantiationScope::InstantiatedLocal(const clang::Decl *, clang::Decl *): Assertion `Current->LocalDecls.find(D) == Current->LocalDecls.end() && "Instantiated local in inner and outer scopes"' failed.
...
 #12 0x00007f8aa3941b9f clang::LocalInstantiationScope::InstantiatedLocal(clang::Decl const*, clang::Decl*) /work/llvm/repo/clang/lib/Sema/SemaTemplateInstantiate.cpp:3627:5
 #13 0x00007f8aa39bd090 addInstantiatedParametersToScope(clang::Sema&, clang::FunctionDecl*, clang::FunctionDecl const*, clang::LocalInstantiationScope&, clang::MultiLevelTemplateArgumentList const&) /work/llvm/repo/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp:4293:7
 #14 0x00007f8aa39be985 clang::Sema::InstantiateFunctionDefinition(clang::SourceLocation, clang::FunctionDecl*, bool, bool, bool) /work/llvm/repo/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp:4869:9
 #15 0x00007f8aa3929378 clang::Sema::DeduceReturnType(clang::FunctionDecl*, clang::SourceLocation, bool)::$_10::operator()() const /work/llvm/repo/clang/lib/Sema/SemaTemplateDeduction.cpp:5025:5
 #16 0x00007f8aa3929335 void llvm::function_ref<void ()>::callback_fn<clang::Sema::DeduceReturnType(clang::FunctionDecl*, clang::SourceLocation, bool)::$_10>(long) /work/llvm/repo/llvm/include/llvm/ADT/STLExtras.h:185:5
 #17 0x00007f8aa28d9ff9 llvm::function_ref<void ()>::operator()() const /work/llvm/repo/llvm/include/llvm/ADT/STLExtras.h:209:5
 #18 0x00007f8aa28c4b0d clang::runWithSufficientStackSpace(llvm::function_ref<void ()>, llvm::function_ref<void ()>) /work/llvm/repo/clang/include/clang/Basic/Stack.h:52:3
 #19 0x00007f8aa28b1de4 clang::Sema::runWithSufficientStackSpace(clang::SourceLocation, llvm::function_ref<void ()>) //work/llvm/repo/clang/lib/Sema/Sema.cpp:458:1
 #20 0x00007f8aa3851a7f clang::Sema::DeduceReturnType(clang::FunctionDecl*, clang::SourceLocation, bool) /work/llvm/repo/clang/lib/Sema/SemaTemplateDeduction.cpp:5028:25
 #21 0x00007f8aa2fe10a4 clang::Sema::DiagnoseUseOfDecl(clang::NamedDecl*, llvm::ArrayRef<clang::SourceLocation>, clang::ObjCInterfaceDecl const*, bool, bool, clang::ObjCInterfaceDecl*) /llvm/repo/clang/lib/Sema/SemaExpr.cpp:291:9
 #22 0x00007f8aa35e47eb CreateFunctionRefExpr(clang::Sema&, clang::FunctionDecl*, clang::NamedDecl*, clang::Expr const*, bool, clang::SourceLocation, clang::DeclarationNameLoc const&) /work/llvm/repo/clang/lib/Sema/SemaOverload.cpp:65:28
 #23 0x00007f8aa35ecba0 clang::Sema::BuildCallToObjectOfClassType(clang::Scope*, clang::Expr*, clang::SourceLocation, llvm::MutableArrayRef<clang::Expr*>, clang::SourceLocation) /work/llvm/repo/clang/lib/Sema/SemaOverload.cpp:14630:22
 #24 0x00007f8aa2fe7574 clang::Sema::BuildCallExpr(clang::Scope*, clang::Expr*, clang::SourceLocation, llvm::MutableArrayRef<clang::Expr*>, clang::SourceLocation, clang::Expr*, bool, bool) /work/llvm/repo/clang/lib/Sema/SemaExpr.cpp:6396:
...

[yaxunl]

ping

I will provide a detailed description of the issue:

What happen are:

First, fun1 is instantiated as fun1<0,1>, which calls lambda function f(f, Number<1>).

This causes lambda function f instantiated as f(f, Number<1>). clang uses LocalInstantiationScope to track local variable instantiations, i.e., map var decls in the template to the corresponding var decls in the instantiation. In this case, clang adds two decls to the map: fs -> f, and i -> instantiation of i with type Number<1>.

This further causes instantiation of lambda function f as f(f, Number<0>) since f contains call of fs(fs, Number<0>). clang adds two decls to its LocalInstantiationScope: fs -> f, and i -> instantiation of i with Number<0>.

Since f is lambda function, clang assumes its instantiation sees the decls in the LocalInstantiationScope of its enclosing template function instantiation, i.e. f(f,Number<1>). However, clang assumes each decl can only show up in LocalInstantiationScope and any enclosing LocalInstantiationScope once, and clang checks and asserts that. In this case, since f shows up in LocalInstantiationScope of f(f, Number<0>) and f(f, Number<1>) twice. This causes assertion.

LocalInstantiationScope has a data member CombineWithOuterScope, which determines whether a template function instantiation sees the var decls instantiated in its enclosing function template instantiation. For non-lambda functions, this is false, therefore non-lambda functions will not have such an issue. For non-recursive lambda function instantiation, such an issue will not happen since the var decls will not show up twice.

Functionally, it seems to be OK to have var decls show up twice in LocalInstantiationScope for recursive lambda instantiations. For the inner level lambda instantiation, when looking up the var decls, the local var instantiation will be found first. The var instantiation in the outer LocalInstantiationScope will not be found. This is like the inner instantiation hides the outer instantiation. To me, it seems we only need to disable the assertion for the specific case of recursive lambda instantiation.

Any thoughts? Thanks.

[yaxunl]

re-enable the assert but with exception for recursive lambda functions

[rsmith]

I think this is the wrong solution; I think the assertion is correct and is observing a problem elsewhere. Imagine if we had something like:

template<typename T>
void f() {
  auto a = [] (auto recurse, auto x) {
    auto b = [] (auto) {
      refer to local decl in a
    };
    if constexpr (recurse)
      a(false_type(), b)
    else
      x(0)
  }
  a(true_type(), a)
}

We would then have a local instantiation scope stack that looks like:

f<int>
f<int>::a::operator()<true_type, f<int>::a>
f<int>::a::operator()<false_type, f<int>::a::operator()<true_type, f<int>::a>::b>
f<int>::a::operator()<true_type, f<int>::a>::operator()::b::operator()<int>

... so the reference from the true_type version of b to the local decl in a would find the local from the enclosing false_type class, which is wrong. That's the kind of bug that I think this assertion is defending against, and it looks like we have that bug here. (As it happens, this will never actually cause problems, because all references from b to enclosing locals already got substituted when instantiating the operator() function template, but that's actually kind of the point -- the local instantiation scope stack is wrong.)

I think the real problem is that the local instantiation scope for the instantiation of a generic lambda's call operator from the instantiated call operator template should never be merged with its parent. Merging the contexts cannot be necessary -- we can have left the parent instantiation before we instantiate a specialization of the call operator template, so there cannot be any references from the call operator template to enclosing locals that require substitution. I think the bug is in InstantiateFunctionDefinition, somewhere around line 4863:

// Introduce a new scope where local variable instantiations will be
// recorded, unless we're actually a member function within a local
// class, in which case we need to merge our results with the parent
// scope (of the enclosing function).
bool MergeWithParentScope = false;
if (CXXRecordDecl *Rec = dyn_cast<CXXRecordDecl>(Function->getDeclContext()))
  MergeWithParentScope = Rec->isLocalClass();

LocalInstantiationScope Scope(*this, MergeWithParentScope);

While we do need the enclosing local instantiation scope when we're instantiating a non-template member of a local class, or when we're instantiating the definition of a member function template as a member function template (that is, when instantiating a generic lambda to form a generic lambda), we do not need the enclosing local instantiation scope when re-substituting into the result of such a local substitution. That is, we do not want a local instantiation scope if we're instantiating a function template specialization, because the template we're instantiating already had references to locals properly substituted. I'd try a change like this to the above code:

-    MergeWithParentScope = Rec->isLocalClass();
+    MergeWithParentScope = Rec->isLocalClass() && !Function->isFunctionTemplateSpecialization();

[yaxunl]

Revised by Richard's comments.

clang/lib/Sema/SemaTemplateInstantiate.cpp

LocalInstantiationScope::findInstantiationOf(const Decl *D) {
   assert(isa<LabelDecl>(D) && "declaration not instantiated in this scope");
   return nullptr;
 }
 
 void LocalInstantiationScope::InstantiatedLocal(const Decl *D, Decl *Inst) {
   D = getCanonicalParmVarDecl(D);
   llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored = LocalDecls[D];
   if (Stored.isNull()) {
-#ifndef NDEBUG
-    // It should not be present in any surrounding scope either.
-    LocalInstantiationScope *Current = this;
-    while (Current->CombineWithOuterScope && Current->Outer) {
-      Current = Current->Outer;
-      assert(Current->LocalDecls.find(D) == Current->LocalDecls.end() &&
-             "Instantiated local in inner and outer scopes");
-    }
-#endif
     Stored = Inst;
   } else if (DeclArgumentPack *Pack = Stored.dyn_cast<DeclArgumentPack *>()) {
     Pack->push_back(cast<VarDecl>(Inst));
   } else {
     assert(Stored.get<Decl *>() == Inst && "Already instantiated this local");
   }
 }
 
 void LocalInstantiationScope::InstantiatedLocalPackArg(const Decl *D,
                                                        VarDecl *Inst) {
   D = getCanonicalParmVarDecl(D);
   DeclArgumentPack *Pack = LocalDecls[D].get<DeclArgumentPack *>();
   Pack->push_back(Inst);
 }
 
 void LocalInstantiationScope::MakeInstantiatedLocalArgPack(const Decl *D) {
-#ifndef NDEBUG
-  // This should be the first time we've been told about this decl.
-  for (LocalInstantiationScope *Current = this;
-       Current && Current->CombineWithOuterScope; Current = Current->Outer)
-    assert(Current->LocalDecls.find(D) == Current->LocalDecls.end() &&
-           "Creating local pack after instantiation of local");
-#endif
-
   D = getCanonicalParmVarDecl(D);
   llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored = LocalDecls[D];
   DeclArgumentPack *Pack = new DeclArgumentPack;
   Stored = Pack;
   ArgumentPacks.push_back(Pack);
 }
 
 bool LocalInstantiationScope::isLocalPackExpansion(const Decl *D) {

clang/test/SemaCXX/recursive-lambda.cpp

+// RUN: %clang_cc1 -std=c++17 -fsyntax-only -verify %s
+
+// expected-no-diagnostics
+
+// Check recursive instantiation of lambda does not cause assertion.
+
+template <unsigned v>
+struct Number
+{
+   static constexpr unsigned value = v;
+};
+
+template <unsigned IBegin = 0,
+          unsigned IEnd = 1>
+constexpr auto fun1(Number<IBegin> = Number<0>{}, Number<IEnd>  = Number<1>{})
+{
+  auto f = [&](auto fs, auto i) {
+    if constexpr(i.value > 0)
+    {
+      return fs(fs, Number<IBegin>{});
+    }
+  };
+
+  return f(f, Number<IEnd>{});
+}
+
+
+void fun2() {
+  fun1();
+}