Page MenuHomePhabricator

Do not merge LocalInstantiationScope for template specialization
ClosedPublic

Authored by yaxunl on Mar 5 2021, 12:17 PM.

Details

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.

Diff Detail

Event Timeline

yaxunl requested review of this revision.Mar 5 2021, 12:17 PM
yaxunl created this revision.
tra added a comment.Mar 8 2021, 10:43 AM

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 added a comment.EditedJun 14 2021, 7:07 AM

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 updated this revision to Diff 351934.Jun 14 2021, 11:09 AM
yaxunl retitled this revision from Remove asserts for LocalInstantiationScope to Exampt asserts for recursive lambdas about LocalInstantiationScope.
yaxunl edited the summary of this revision. (Show Details)

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

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 updated this revision to Diff 351990.Jun 14 2021, 1:56 PM
yaxunl edited the summary of this revision. (Show Details)

Revised by Richard's comments.

yaxunl retitled this revision from Exampt asserts for recursive lambdas about LocalInstantiationScope to Do not merge LocalInstantiationScope for template specialization.Jun 14 2021, 1:58 PM
rsmith accepted this revision.Jun 14 2021, 3:45 PM
This revision is now accepted and ready to land.Jun 14 2021, 3:45 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 14 2021, 8:39 PM