WIP for non-eager lambda instantiation

[erichkeane]

Summary

See https://github.com/llvm/llvm-project/issues/58872 and https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0588r1.html

Just an our or so trying to figure out the issue. Since this is a 'DR', this likely means we will have a lot of tests to update. @aaron.ballman : is this something we need to hide behind the clang-abi flag?

ALSO, there are quite a few crashes on top of those, but at least the example code 'works'. The implementation here was mostly "remove this special cutout for generic lambdas", so I wonder if the crashes are all something like that?

[erichkeane]

Failure list of the 1st patch:

---

Failed Tests (54):

Clang :: ASTMerge/exprs-cpp/test.cpp
Clang :: CXX/expr/expr.prim/expr.prim.lambda/expr.prim.lambda.capture/p17.cpp
Clang :: CXX/expr/expr.prim/expr.prim.lambda/p11-1y.cpp
Clang :: CXX/expr/expr.prim/expr.prim.lambda/p23.cpp
Clang :: CXX/expr/expr.prim/expr.prim.lambda/templates.cpp
Clang :: CXX/stmt.stmt/stmt.select/stmt.if/p2.cpp
Clang :: CXX/temp/temp.decls/temp.variadic/init-capture.cpp
Clang :: CXX/temp/temp.param/p15-cxx0x.cpp
Clang :: CodeGenCXX/captured-statements.cpp
Clang :: CodeGenCXX/crash.cpp
Clang :: CodeGenCXX/cxx2b-static-call-operator.cpp
Clang :: CodeGenCXX/lambda-expressions-inside-auto-functions.cpp
Clang :: CodeGenCXX/lambda-expressions-nested-linkage.cpp
Clang :: CodeGenCXX/mangle-lambdas-cxx14.cpp
Clang :: CodeGenCXX/mangle-lambdas-cxx20.cpp
Clang :: CodeGenCXX/mangle-lambdas.cpp
Clang :: CodeGenCXX/mangle-ms-cxx14.cpp
Clang :: CodeGenCXX/predefined-expr.cpp
Clang :: CodeGenCXX/vla-lambda-capturing.cpp
Clang :: CodeGenCoroutines/coro-lambda-exp-namespace.cpp
Clang :: CodeGenCoroutines/coro-lambda.cpp
Clang :: CodeGenObjCXX/lambda-expressions.mm
Clang :: OpenMP/default_firstprivate_ast_print.cpp
Clang :: OpenMP/nvptx_lambda_pointer_capturing.cpp
Clang :: OpenMP/single_codegen.cpp
Clang :: OpenMP/target_map_codegen_24.cpp
Clang :: PCH/cxx11-lambdas.mm
Clang :: PCH/cxx1y-init-captures.cpp
Clang :: PCH/cxx20-unevaluated-lambda.cpp
Clang :: SemaCXX/constant-expression-cxx2b.cpp
Clang :: SemaCXX/cxx1y-generic-lambdas-capturing.cpp
Clang :: SemaCXX/cxx1y-generic-lambdas-variadics.cpp
Clang :: SemaCXX/cxx1y-generic-lambdas.cpp
Clang :: SemaCXX/cxx1y-init-captures.cpp
Clang :: SemaCXX/cxx1z-constexpr-lambdas.cpp
Clang :: SemaCXX/cxx1z-lambda-star-this.cpp
Clang :: SemaCXX/lambda-expressions.cpp
Clang :: SemaCXX/lambda-unevaluated.cpp
Clang :: SemaCXX/lambdas-implicit-explicit-template.cpp
Clang :: SemaCXX/recursive-lambda.cpp
Clang :: SemaCXX/vartemplate-lambda.cpp
Clang :: SemaCXX/warn-unused-lambda-capture.cpp
Clang :: SemaSYCL/zero-length-arrays.cpp
Clang :: SemaTemplate/concepts.cpp
Clang :: SemaTemplate/constexpr-instantiate.cpp
Clang :: SemaTemplate/cxx1z-using-declaration.cpp
Clang :: SemaTemplate/default-arguments-cxx0x.cpp
Clang :: SemaTemplate/default-expr-arguments-3.cpp
Clang :: SemaTemplate/explicit-instantiation.cpp
Clang :: SemaTemplate/instantiate-exception-spec-cxx11.cpp
Clang :: SemaTemplate/instantiate-local-class.cpp
Clang :: SemaTemplate/lambda-capture-pack.cpp
Clang :: SemaTemplate/ms-lookup-template-base-classes.cpp
Clang :: SemaTemplate/sizeof-pack.cpp

[cschreib]

I used the code below as a test:

template <typename T> int foo() {
  int i = 2;
  auto bar = [&]<typename U>(U) {
    if constexpr (sizeof(U) > 1) {
      return sizeof(U) + i;
    } else {
      return sizeof(T);
    }
  };

  return bar(1);
}

int main() {
  return foo<void>();
}

Expected output: no diagnostic, output of main is 6. When instantiating foo<void>, the else branch of the if constexpr in bar would generate an invalid sizeof(void) (current clang releases do emit this diagnostic, and won't compile). However, bar.operator<U>() is only instantiated with template parameter int, such that the if constexpr(sizeof(U) > 1) is true, therefore the else statement should be discarded and no diagnostic produced.

My understanding of the clang code base is rather shallow, but I'll share some observations from poking around at the code and proposed changes:

1. Prior to the changes, the commented-out lines in Decl.cpp and SemaTemplateInstantiate.cpp were not hit when compiling the test code above. The diagnostic was emitted first. They also were not hit if I only applied the change to TreeTransform.h (which does get rid of the diagnostic, see below).
2. The lines in Decl.cpp seem to me like they should stay; this looks like a shortcut we can take since the lambda call operator cannot be specialized, forward-declared, friended, etc.. There is no need for an exhaustive search for the right prototype, as one would do for a classic function template.
3. Commenting-out the lines in SemaTemplateInstantiate.cpp looks sensible.
4. The change to TreeTransform.h does get rid of the diagnostic, but it is probably too much. It appears the lambda body never gets instantiated (see below); this is probably what is causing all the crashes and failures.

Applying all proposed changes (or just the change to TreeTransform.h) and compiling the above with clang test.cpp -std=c++20 -o test, I get:

clang-16: /home/cschreib/programming/llvm-project/clang/lib/Sema/SemaTemplateInstantiate.cpp:4048: llvm::PointerUnion<clang::Decl*, llvm::SmallVector<clang::VarDecl*, 4>*>* clang::LocalInstantiationScope::findInstantiationOf(const clang::Decl*): Assertion `isa<LabelDecl>(D) && "declaration not instantiated in this scope"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: /home/cschreib/programming/llvm-project/build/bin/clang-16 -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -mrelax-all --mrelax-relocations -disable-free -clear-ast-before-backend -main-file-name test.cpp -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -mllvm -treat-scalable-fixed-error-as-warning -debugger-tuning=gdb -fcoverage-compilation-dir=/home/cschreib/programming/llvm-project/build/bin -resource-dir /home/cschreib/programming/llvm-project/build/lib/clang/16 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /home/cschreib/programming/llvm-project/build/lib/clang/16/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -std=c++20 -fdeprecated-macro -fdebug-compilation-dir=/home/cschreib/programming/llvm-project/build/bin -ferror-limit 19 -fgnuc-version=4.2.1 -fno-implicit-modules -fcxx-exceptions -fexceptions -fcolor-diagnostics -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/test-d0a799.o -x c++ test.cpp
1.	<eof> parser at end of file
2.	test.cpp:1:27: instantiating function definition 'foo<void>'
3.	test.cpp:3:14: instantiating function definition 'foo()::(anonymous class)::operator()<int>'

[erichkeane]

In D138148#3933197, @cschreib wrote:

I used the code below as a test:

template <typename T> int foo() {
  int i = 2;
  auto bar = [&]<typename U>(U) {
    if constexpr (sizeof(U) > 1) {
      return sizeof(U) + i;
    } else {
      return sizeof(T);
    }
  };

  return bar(1);
}

int main() {
  return foo<void>();
}

Expected output: no diagnostic, output of main is 6. When instantiating foo<void>, the else branch of the if constexpr in bar would generate an invalid sizeof(void) (current clang releases do emit this diagnostic, and won't compile). However, bar.operator<U>() is only instantiated with template parameter int, such that the if constexpr(sizeof(U) > 1) is true, therefore the else statement should be discarded and no diagnostic produced.

My understanding of the clang code base is rather shallow, but I'll share some observations from poking around at the code and proposed changes:

1. Prior to the changes, the commented-out lines in Decl.cpp and SemaTemplateInstantiate.cpp were not hit when compiling the test code above. The diagnostic was emitted first. They also were not hit if I only applied the change to TreeTransform.h (which does get rid of the diagnostic, see below).
2. The lines in Decl.cpp seem to me like they should stay; this looks like a shortcut we can take since the lambda call operator cannot be specialized, forward-declared, friended, etc.. There is no need for an exhaustive search for the right prototype, as one would do for a classic function template.

These are necessary, they are there because otherwise we end up adding the wrong parameters list, we need to add the parameters list relative to the primary template. The code in Decl.cpp was there to make sure we are actually installing the correct list of 'parameters' and template arguments, else you'll not get the parameters from teh parent template, nor the declarations from the signature of the lambda.

3. Commenting-out the lines in SemaTemplateInstantiate.cpp looks sensible.
4. The change to TreeTransform.h does get rid of the diagnostic, but it is probably too much. It appears the lambda body never gets instantiated (see below); this is probably what is causing all the crashes and failures.

This isn't what is causing the crashes/failures as far as I can tell. The body IS still being instantiated (in fact, the crash is happening DURING instantiation, look at the last line of your post), the problem I suspect with below is the things being captured not being properly added to the scope.

Applying all proposed changes (or just the change to TreeTransform.h) and compiling the above with clang test.cpp -std=c++20 -o test, I get:

clang-16: /home/cschreib/programming/llvm-project/clang/lib/Sema/SemaTemplateInstantiate.cpp:4048: llvm::PointerUnion<clang::Decl*, llvm::SmallVector<clang::VarDecl*, 4>*>* clang::LocalInstantiationScope::findInstantiationOf(const clang::Decl*): Assertion `isa<LabelDecl>(D) && "declaration not instantiated in this scope"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: /home/cschreib/programming/llvm-project/build/bin/clang-16 -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -mrelax-all --mrelax-relocations -disable-free -clear-ast-before-backend -main-file-name test.cpp -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -mllvm -treat-scalable-fixed-error-as-warning -debugger-tuning=gdb -fcoverage-compilation-dir=/home/cschreib/programming/llvm-project/build/bin -resource-dir /home/cschreib/programming/llvm-project/build/lib/clang/16 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /home/cschreib/programming/llvm-project/build/lib/clang/16/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -std=c++20 -fdeprecated-macro -fdebug-compilation-dir=/home/cschreib/programming/llvm-project/build/bin -ferror-limit 19 -fgnuc-version=4.2.1 -fno-implicit-modules -fcxx-exceptions -fexceptions -fcolor-diagnostics -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/test-d0a799.o -x c++ test.cpp
1.	<eof> parser at end of file
2.	test.cpp:1:27: instantiating function definition 'foo<void>'
3.	test.cpp:3:14: instantiating function definition 'foo()::(anonymous class)::operator()<int>'

Yeah that crash is consistent with a bunch of the test failures I'm seeing. I have a suspicion that the problem is the lambda's captures. A simplified version of your test works perfectly (that is, one without captures):

template<typename T, typename U>
struct is_same {
  static constexpr bool value = false;
};
template<typename T>
struct is_same<T,T> {
  static constexpr bool value = true;
};


template<typename T>
auto foo() {
  return [](auto X) {
  //return []<typename U>(U X) {
  //  if constexpr (is_same<U, int>::value){
    if constexpr (is_same<decltype(X), double>::value){
    return 5 + X /*+ T{}*/; // commented out, because constructing a void is still an  error.
    } else {
      return (int)sizeof(T);
    }
  }(1.1);
}

auto bar() {
  return foo<void>();
}

So I suspect the problem left with the crashes at least is 2 fold:
1- Now that we're doing this, we have nothing causing non-generic lambdas to be instantiated. I believe the paper makes us delay these as well, so we can't just skip generic lambdas in tree-transform.
2- We're not setting the scope up properly: instantiating lambdas 'later' is a fairly novel concept here, so there is no code currently to set up the rest of the 'inner function' correctly, such that we end up with the correct list things we can capture.

clang/lib/Sema/TreeTransform.h

13393

I thought about this further, and I think the paper requires we do this for EVERY lambda, not just generic lambdas.

[aaron.ballman]

Just an our or so trying to figure out the issue. Since this is a 'DR', this likely means we will have a lot of tests to update. @aaron.ballman : is this something we need to hide behind the clang-abi flag?

It depends. Hopefully this isn't disruptive in practice and the question is moot. But if this turns out to be mildly disruptive, then I think we'd want an ABI compat flag for users to opt into the old ABI. If this turns out to be more than mildly disruptive, we'll have to figure out whether we want to implement it as a DR or not (or not at all, I suppose, but hopefully we can avoid that outcome).

[erichkeane]

clang/lib/Sema/TreeTransform.h

13393

So I re-considered this and discussed it... I suspect we can get rid of at least 1 class of the failures (the T->isDependent crashes) if we just make this for generic lambdas, so our only problem would be #2 above I believe.

I can't think of any situation where this would matter. However P0588 is a little tough to parse for me.

[erichkeane]

Limiting this to just generic lambdas by changing TransformLambdaBody to:

if (E->isGenericLambda())
  return SkipLambdaBody(E, S);
return TransformStmt(S);

changed the errors to:

********************
Failed Tests (13):
  Clang :: CXX/stmt.stmt/stmt.select/stmt.if/p2.cpp
  Clang :: CXX/temp/temp.decls/temp.variadic/init-capture.cpp
  Clang :: SemaCXX/cxx1y-generic-lambdas-capturing.cpp
  Clang :: SemaCXX/cxx1y-generic-lambdas-variadics.cpp
  Clang :: SemaCXX/cxx1y-generic-lambdas.cpp
  Clang :: SemaCXX/cxx1y-init-captures.cpp
  Clang :: SemaCXX/cxx1z-lambda-star-this.cpp
  Clang :: SemaCXX/lambdas-implicit-explicit-template.cpp
  Clang :: SemaCXX/recursive-lambda.cpp
  Clang :: SemaCXX/warn-unused-lambda-capture.cpp
  Clang :: SemaTemplate/cxx1z-using-declaration.cpp
  Clang :: SemaTemplate/default-arguments-cxx0x.cpp
  Clang :: SemaTemplate/lambda-capture-pack.cpp

AND confirms my thoughts that the T->isDependent crashes would go away, and leave us with just the capture issues (the LabelDecl asserts), and some other diagnostic changes which MIGHT just be fallout from this change.

I'm STILL a little suspicious of what SkipLambdaBody does here though, and wonder if it is messing up our captures in some way anyway.

[erichkeane]

In D138148#3934059, @erichkeane wrote:

Limiting this to just generic lambdas by changing TransformLambdaBody to:

if (E->isGenericLambda())
  return SkipLambdaBody(E, S);
return TransformStmt(S);

changed the errors to:

********************
Failed Tests (13):
  Clang :: CXX/stmt.stmt/stmt.select/stmt.if/p2.cpp
  Clang :: CXX/temp/temp.decls/temp.variadic/init-capture.cpp
  Clang :: SemaCXX/cxx1y-generic-lambdas-capturing.cpp
  Clang :: SemaCXX/cxx1y-generic-lambdas-variadics.cpp
  Clang :: SemaCXX/cxx1y-generic-lambdas.cpp
  Clang :: SemaCXX/cxx1y-init-captures.cpp
  Clang :: SemaCXX/cxx1z-lambda-star-this.cpp
  Clang :: SemaCXX/lambdas-implicit-explicit-template.cpp
  Clang :: SemaCXX/recursive-lambda.cpp
  Clang :: SemaCXX/warn-unused-lambda-capture.cpp
  Clang :: SemaTemplate/cxx1z-using-declaration.cpp
  Clang :: SemaTemplate/default-arguments-cxx0x.cpp
  Clang :: SemaTemplate/lambda-capture-pack.cpp

AND confirms my thoughts that the T->isDependent crashes would go away, and leave us with just the capture issues (the LabelDecl asserts), and some other diagnostic changes which MIGHT just be fallout from this change.

I'm STILL a little suspicious of what SkipLambdaBody does here though, and wonder if it is messing up our captures in some way anyway.

I spent a while workign on the weekend, and I think we have 2 problems with this (with the suggested change to only modify transform lambda body when it is generic).

1- We need to teach FindInstantiatedDecl to work with this case. Currently it assumes that any declaration with a parent of type FunctionDecl should be able to find the declaration inside of the CurrentInstantiationScope. This isn't true anymore, since it can come from a different function now, in a different scope. I'm not sure how to go about this, and holidays are likely going to interfere with my ability to look into this short-term.

2- There is some funny-business happening with default arguments. I know that a few people have messed with these in the past, and I'm sure there is a good amount of hackery to make them work, so I'm a touch concerned about the fallout of that.

[cor3ntin]

Note that https://reviews.llvm.org/D137244 touches at different parts of P0588

clang/lib/AST/Decl.cpp

   // (i.e. instantiated-from-member-template) to use as an instantiation
   // pattern.
 
-  if (isGenericLambdaCallOperatorSpecialization(
-          dyn_cast<CXXMethodDecl>(this))) {
-    assert(getPrimaryTemplate() && "not a generic lambda call operator?");
-    return getDefinitionOrSelf(getPrimaryTemplate()->getTemplatedDecl());
-  }
+  //if (isGenericLambdaCallOperatorSpecialization(
+  //        dyn_cast<CXXMethodDecl>(this))) {
+  //  assert(getPrimaryTemplate() && "not a generic lambda call operator?");
+  //  return getDefinitionOrSelf(getPrimaryTemplate()->getTemplatedDecl());
+  //}
 
   // Check for a declaration of this function that was instantiated from a
   // friend definition.

clang/lib/Sema/SemaTemplateInstantiate.cpp

       return Response::Done();
 
     // If this function is a generic lambda specialization, we are done.
-    if (!ForConstraintInstantiation &&
-        isGenericLambdaCallOperatorOrStaticInvokerSpecialization(Function))
-      return Response::Done();
+    //if (!ForConstraintInstantiation &&
+    //    isGenericLambdaCallOperatorOrStaticInvokerSpecialization(Function))
+    //  return Response::Done();
 
   } else if (Function->getDescribedFunctionTemplate()) {
     assert(

clang/lib/Sema/TreeTransform.h

 template<typename Derived>
 StmtResult
 TreeTransform<Derived>::TransformLambdaBody(LambdaExpr *E, Stmt *S) {
-  return TransformStmt(S);
+  //return TransformStmt(S);
+  return SkipLambdaBody(E, S);
 }
 
 template<typename Derived>