[Sema] Lambdas are not part of immediate context for deduction

[ilya-biryukov]

Summary

This commit implements [temp.deduct]p9.
Test updates include:

• New notes in cxx1y-init-captures.cpp, lambda-expressions.cpp and 'warn-unused-lambda-capture.cpp'. This seems to be caused by diagnosing errors earlier (during deduction) that were previously surfaced later (during instantiation).
• New error lambda-unevaluated.cpp is in line with [temp.deduct]p9.

[erichkeane]

My one concern is that this is going to expose our incorrect instantiation of lambdas further and more painfully (see https://github.com/llvm/llvm-project/issues/58872). Else, I don't see anything to be concerned about here.

I think the FIXME of adding a note diagnostic here should be fixed before committing however.

clang/lib/Sema/SemaTemplateInstantiate.cpp

965

Would really like this note here, it shouldn't be too difficult, right?

[ilya-biryukov]

clang/lib/Sema/SemaTemplateInstantiate.cpp

965

Ah, sorry, I added a comment here that I forgot to submit. The question is: could it be that we want to skip this note?

I wanted to double-check if folks find this note useful.
On one hand, this probably creates some noise as there will always be other notes that point into the location of a corresponding substitution location that contains the lambda.
On the other hand, since the lambda is not an immediate context, this may give hints to users on why SFINAE does not apply.

If you feel like the note is useful, I will follow up with an implementation.

[erichkeane]

clang/lib/Sema/SemaTemplateInstantiate.cpp

965

I think it is useful for exactly the reason you mentioned: this is going to be somewhat shocking behavior to most people, so explaining it better will be helpful.

[shafik]

clang/test/CXX/temp/temp.deduct/p9.cpp

2

Maybe helpful to quote p9?

36

I know the note in the standard does not explain why this is ok but a comment would be helpful to future readers.

39

I think the comment from the draft is helpful here "deduction fails on #1, calls #2"

clang/test/SemaCXX/warn-unused-lambda-capture.cpp

192

Why the 12 extra notes here, I feel I am missing something but not sure what. I see the increase in notes in other cases as well.

[ilya-biryukov]

• Add a note when substituting into a lambda
• Quote the standard and add explanation for the test

[ilya-biryukov]

In D148802#4283566, @erichkeane wrote:

My one concern is that this is going to expose our incorrect instantiation of lambdas further and more painfully (see https://github.com/llvm/llvm-project/issues/58872). Else, I don't see anything to be concerned about here.

That's true, but it seems that as a result of this patch, Clang will start rejecting some valid C++ programs when lambdas are used in unevaluated contexts, but will stop (incorrectly) accepting a class of programs that are invalid according to C++ standard.
I would err on the side of false negatives (correct program not compiled) instead of false positives (incorrect program complied). Otherwise, future changes that make Clang compliant can potentially require rewriting the code that relied on incorrect behavior.
It's still unfortunate that we don't accept valid programs, but at least existing code will not need to be changed after GH58872 is fixed.
My perspective is based on the need to support a large codebase, in which codebase-wide refactorings are expensive, other might have a different opinion here.

clang/lib/Sema/SemaTemplateInstantiate.cpp

965

Makes sense. Added a corresponding note.

clang/test/SemaCXX/warn-unused-lambda-capture.cpp

192

I'm not entirely sure, but it seems there is some deduplication of notes that's happening when the stacks of code-synthesis-contexts for subsequent errors are the same.
However, this patch introduces a different code synthesis context for lambda substitutions, forcing the notes to be added.
In the new version of the patch, the added context actually shows up in the notes as well.

[ilya-biryukov]

Friendly ping for another round of review.

[ilya-biryukov]

Another friendly ping for review.
@erichkeane let me know if you feel that exposing the incorrect lambda instantiation behavior is a blocker here.

[erichkeane]

In D148802#4326268, @ilya-biryukov wrote:

Another friendly ping for review.
@erichkeane let me know if you feel that exposing the incorrect lambda instantiation behavior is a blocker here.

I don't... we're up to ~4 active bugs on that, so its not like it is 'unexposed' now. I think this looks good enough to accept;

clang/test/SemaCXX/warn-unused-lambda-capture.cpp

192

Note that this test is organized poorly, and the 12 additions are likely the levels added above, and it is 1 per error, so its just 1 more level of 'in instantiation...' in each of those cases above.

[ilya-biryukov]

• Moved the relase note to 'C++20 feature support', fixed typos

[ilya-biryukov]

• Fix a typo (forgot to commit last time)

clang/docs/ReleaseNotes.rst

 - Clang now supports ``__builtin_assume_separate_storage`` that indicates that
   its arguments point to objects in separate storage allocations.
 - Clang now supports expressions in ``#pragma clang __debug dump``.
 - Clang now supports declaration of multi-dimensional arrays with
   ``__declspec(property)``.
 - A new builtin type trait ``__is_trivially_equaltiy_comparable`` has been added,
   which checks whether comparing two instances of a type is equivalent to
   ``memcmp(&lhs, &rhs, sizeof(T)) == 0``.
+- Clang now implements `[temp.deduct]p9`, subsitution failures inside lambdas from
+  unevaluated contexts will be surfaced as errors. They were previously handled as
+  SFINAE.
+
 
 New Compiler Flags
 ------------------
 
 Deprecated Compiler Flags
 -------------------------
 
 Modified Compiler Flags

clang/include/clang/Sema/Sema.h

enum SynthesisKind {
 
       /// We are substituting template argument determined as part of
       /// template argument deduction for either a class template
       /// partial specialization or a function template. The
       /// Entity is either a {Class|Var}TemplatePartialSpecializationDecl or
       /// a TemplateDecl.
       DeducedTemplateArgumentSubstitution,
 
+      /// We are substituting into a lambda expression.
+      LambdaExpressionSubstitution,
+
       /// We are substituting prior template arguments into a new
       /// template parameter. The template parameter itself is either a
       /// NonTypeTemplateParmDecl or a TemplateTemplateParmDecl.
       PriorTemplateArgumentSubstitution,
 
       /// We are checking the validity of a default template argument that
       /// has been used when naming a template-id.
       DefaultTemplateArgumentChecking,

clang/lib/Frontend/FrontendActions.cpp

static std::string toString(CodeSynthesisContext::SynthesisKind Kind) {
     case CodeSynthesisContext::DefaultTemplateArgumentInstantiation:
       return "DefaultTemplateArgumentInstantiation";
     case CodeSynthesisContext::DefaultFunctionArgumentInstantiation:
       return "DefaultFunctionArgumentInstantiation";
     case CodeSynthesisContext::ExplicitTemplateArgumentSubstitution:
       return "ExplicitTemplateArgumentSubstitution";
     case CodeSynthesisContext::DeducedTemplateArgumentSubstitution:
       return "DeducedTemplateArgumentSubstitution";
+    case CodeSynthesisContext::LambdaExpressionSubstitution:
+      return "LambdaExpressionSubstitution";
     case CodeSynthesisContext::PriorTemplateArgumentSubstitution:
       return "PriorTemplateArgumentSubstitution";
     case CodeSynthesisContext::DefaultTemplateArgumentChecking:
       return "DefaultTemplateArgumentChecking";
     case CodeSynthesisContext::ExceptionSpecEvaluation:
       return "ExceptionSpecEvaluation";
     case CodeSynthesisContext::ExceptionSpecInstantiation:
       return "ExceptionSpecInstantiation";

clang/lib/Sema/SemaTemplateInstantiate.cpp

 #include "clang/Sema/Initialization.h"
 #include "clang/Sema/Lookup.h"
 #include "clang/Sema/Sema.h"
 #include "clang/Sema/SemaConcept.h"
 #include "clang/Sema/SemaInternal.h"
 #include "clang/Sema/Template.h"
 #include "clang/Sema/TemplateDeduction.h"
 #include "clang/Sema/TemplateInstCallback.h"
+#include "llvm/ADT/ScopeExit.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/TimeProfiler.h"
 #include <optional>
 
 using namespace clang;
 using namespace sema;
 
 //===----------------------------------------------------------------------===/
bool Sema::CodeSynthesisContext::isInstantiationRecord() const {
   case ExceptionSpecEvaluation:
   case ConstraintSubstitution:
   case ParameterMappingSubstitution:
   case ConstraintNormalization:
   case RewritingOperatorAsSpaceship:
   case InitializingStructuredBinding:
   case MarkingClassDllexported:
   case BuildingBuiltinDumpStructCall:
+  case LambdaExpressionSubstitution:
     return false;
 
   // This function should never be called when Kind's value is Memoization.
   case Memoization:
     break;
   }
 
   llvm_unreachable("Invalid SynthesisKind!");
for (SmallVectorImpl<CodeSynthesisContext>::reverse_iterator
     case CodeSynthesisContext::BuildingBuiltinDumpStructCall:
       Diags.Report(Active->PointOfInstantiation,
                    diag::note_building_builtin_dump_struct_call)
           << convertCallArgsToString(
                  *this, llvm::ArrayRef(Active->CallArgs, Active->NumCallArgs));
       break;
 
     case CodeSynthesisContext::Memoization:
+    case CodeSynthesisContext::LambdaExpressionSubstitution:
+      // FIXME: add a note for lambdas.
       break;
 
     case CodeSynthesisContext::ConstraintsCheck: {
       unsigned DiagID = 0;
       if (!Active->Entity) {
         Diags.Report(Active->PointOfInstantiation,
                      diag::note_nested_requirement_here)
           << Active->InstantiationRange;
for (SmallVectorImpl<CodeSynthesisContext>::reverse_iterator
     }
   }
 }
 
 std::optional<TemplateDeductionInfo *> Sema::isSFINAEContext() const {
   if (InNonInstantiationSFINAEContext)
     return std::optional<TemplateDeductionInfo *>(nullptr);
 
+  bool SawLambdaSubstitution = false;
   for (SmallVectorImpl<CodeSynthesisContext>::const_reverse_iterator
          Active = CodeSynthesisContexts.rbegin(),
          ActiveEnd = CodeSynthesisContexts.rend();
        Active != ActiveEnd;
        ++Active)
   {
     switch (Active->Kind) {
     case CodeSynthesisContext::TemplateInstantiation:
       // An instantiation of an alias template may or may not be a SFINAE
       // context, depending on what else is on the stack.
       if (isa<TypeAliasTemplateDecl>(Active->Entity))
         break;
       [[fallthrough]];
     case CodeSynthesisContext::DefaultFunctionArgumentInstantiation:
     case CodeSynthesisContext::ExceptionSpecInstantiation:
     case CodeSynthesisContext::ConstraintsCheck:
     case CodeSynthesisContext::ParameterMappingSubstitution:
     case CodeSynthesisContext::ConstraintNormalization:
     case CodeSynthesisContext::NestedRequirementConstraintsCheck:
       // This is a template instantiation, so there is no SFINAE.
       return std::nullopt;
+    case CodeSynthesisContext::LambdaExpressionSubstitution:
+      // [temp.deduct]p9
+      // A lambda-expression appearing in a function type or a template
+      // parameter is not considered part of the immediate context for the
+      // purposes of template argument deduction.
+
+      // We need to check parents.
+      SawLambdaSubstitution = true;
+      break;
 
     case CodeSynthesisContext::DefaultTemplateArgumentInstantiation:
     case CodeSynthesisContext::PriorTemplateArgumentSubstitution:
     case CodeSynthesisContext::DefaultTemplateArgumentChecking:
     case CodeSynthesisContext::RewritingOperatorAsSpaceship:
       // A default template argument instantiation and substitution into
       // template parameters with arguments for prior parameters may or may
       // not be a SFINAE context; look further up the stack.
       break;
 
     case CodeSynthesisContext::ExplicitTemplateArgumentSubstitution:
     case CodeSynthesisContext::DeducedTemplateArgumentSubstitution:
+      // We're either substituting explicitly-specified template arguments,
+      // deduced template arguments. SFINAE applies unless we are in a lambda
+      // expression, see [temp.deduct]p9.
+      if (SawLambdaSubstitution)
+        return std::nullopt;
+      [[fallthrough]];
     case CodeSynthesisContext::ConstraintSubstitution:
     case CodeSynthesisContext::RequirementInstantiation:
     case CodeSynthesisContext::RequirementParameterInstantiation:
-      // We're either substituting explicitly-specified template arguments,
-      // deduced template arguments, a constraint expression or a requirement
-      // in a requires expression, so SFINAE applies.
+      // SFINAE always applies in a constraint expression or a requirement
+      // in a requires expression.
       assert(Active->DeductionInfo && "Missing deduction info pointer");
       return Active->DeductionInfo;
 
     case CodeSynthesisContext::DeclaringSpecialMember:
     case CodeSynthesisContext::DeclaringImplicitEqualityComparison:
     case CodeSynthesisContext::DefiningSynthesizedFunction:
     case CodeSynthesisContext::InitializingStructuredBinding:
     case CodeSynthesisContext::MarkingClassDllexported:
public:
     QualType
     TransformSubstTemplateTypeParmPackType(TypeLocBuilder &TLB,
                                            SubstTemplateTypeParmPackTypeLoc TL,
                                            bool SuppressObjCLifetime);
 
     ExprResult TransformLambdaExpr(LambdaExpr *E) {
       LocalInstantiationScope Scope(SemaRef, /*CombineWithOuterScope=*/true);
       Sema::ConstraintEvalRAII<TemplateInstantiator> RAII(*this);
+
+      Sema::CodeSynthesisContext C;
+      C.Kind = clang::Sema::CodeSynthesisContext::LambdaExpressionSubstitution;
+      C.PointOfInstantiation = E->getBeginLoc();
+      SemaRef.pushCodeSynthesisContext(C);
+      auto PopCtx =
+          llvm::make_scope_exit([this] { SemaRef.popCodeSynthesisContext(); });
+
       ExprResult Result = inherited::TransformLambdaExpr(E);
       if (Result.isInvalid())
         return Result;
 
       CXXMethodDecl *MD = Result.getAs<LambdaExpr>()->getCallOperator();
       for (ParmVarDecl *PVD : MD->parameters()) {
         assert(PVD && "null in a parameter list");
         if (!PVD->hasDefaultArg())

clang/test/CXX/temp/temp.deduct/p9.cpp

+// RUN:  %clang_cc1 -std=c++20 -verify %s
+template <class T>
+auto f(T) -> decltype([]() { T::invalid; } ());
+void f(...);
+void test_f() {
+  f(0); // expected-error@-3 {{type 'int' cannot be used prior to '::'}}
+        // expected-note@-1 {{while substituting deduced template arguments}}
+}
+
+template <class T, unsigned = sizeof([]() { T::invalid; })>
+void g(T);
+void g(...);
+void test_g() {
+  g(0); // expected-error@-4 {{type 'int' cannot be used prior to '::'}}
+        // expected-note@-4 {{in instantiation of default argument}}
+        // expected-note@-2 {{while substituting deduced template arguments}}
+}
+
+template <class T>
+auto h(T) -> decltype([x = T::invalid]() { });
+void h(...);
+void test_h() {
+  h(0); // expected-error@-3 {{type 'int' cannot be used prior to '::'}}
+        // expected-note@-1 {{while substituting deduced template arguments}}
+}
+
+template <class T>
+auto i(T) -> decltype([]() -> typename T::invalid { });
+void i(...);
+void test_i() {
+  i(0); // expected-error@-3 {{type 'int' cannot be used prior to '::'}}
+        // expected-note@-1 {{while substituting deduced template arguments}}
+}
+
+template <class T>
+auto j(T t) -> decltype([](auto x) -> decltype(x.invalid) { } (t));   // #1
+void j(...);                                                            // #2
+void test_j() {
+  j(0);
+}

clang/test/SemaCXX/cxx1y-init-captures.cpp

auto N2 = [x = y, //expected-note3{{begins here}} expected-note 6 {{default capture by}}
                 o = f([&a(t)](T& ... t)->decltype(auto) { return a; }(t...)...)](T& ... s) { // expected-note 6 {{capture 't' by}}
                 fv([&a(t)]()->decltype(auto) { //expected-error 3{{captured}}
                     return a;
                   }() ...);
                 };                 
 
   }
 
-  void h(int i, char c) { g(i, c); } //expected-note{{in instantiation}}
+  void h(int i, char c) { g(i, c); } //expected-note 2{{in instantiation}}
 }
 
 namespace odr_use_within_init_capture {
 
 int test() {
   
   { // no captures
     const int x = 10;
auto L = [z =
                   [z = x, &y = x](char a) { return z + y; }('a')](char a) 
       { return z; };
   
   }
   
   return 0;
 }
 
-int run = test(); //expected-note {{instantiation}}
+int run = test(); //expected-note 2 {{instantiation}}
 
 }
 
 namespace classification_of_captures_of_init_captures {
 
 template <typename T>
 void f() {
   [a = 24] () mutable {

clang/test/SemaCXX/lambda-expressions.cpp

template<typename...Ts> void nested2(Ts ...ts) { // expected-note 2{{here}}
     // also say which slice of the pack expansion is being performed in the
     // instantiation backtrace.
     f([&ts] { return (int)f(ts...); } ()...); // \
     // expected-error 2{{'ts' cannot be implicitly captured}} \
     // expected-note 2{{lambda expression begins here}} \
     // expected-note 4 {{capture 'ts' by}}
   }
   template void nested2(int); // ok
-  template void nested2(int, int); // expected-note {{in instantiation of}}
+  template void nested2(int, int); // expected-note 2 {{in instantiation of}}
 }
 
 namespace PR13860 {
   void foo() {
     auto x = PR13860UndeclaredIdentifier(); // expected-error {{use of undeclared identifier 'PR13860UndeclaredIdentifier'}}
     auto y = [x]() { };
     static_assert(sizeof(y), "");
   }

clang/test/SemaCXX/lambda-unevaluated.cpp

 using d = decltype(sizeof([] { return 0; }));
 
 template <auto T>
 int unique_test1();
 static_assert(&unique_test1<[](){}> != &unique_test1<[](){}>);
 
 template <class T>
 auto g(T) -> decltype([]() { T::invalid; } ());
-auto e = g(0); // expected-error{{no matching function for call}}
-// expected-note@-2 {{substitution failure}}
+auto e = g(0); // expected-error@-1{{type 'int' cannot be used prior to '::'}}
+               // expected-note@-1{{while substituting deduced template}}
+               // expected-error@-2 {{no matching function for call to 'g'}}
+               // expected-note@-4 {{substitution failure}}
 
 template <typename T>
 auto foo(decltype([] {
   return [] { return T(); }();
 })) {}
 
 void test() {
   foo<int>({});

 using c = decltype([]() static noexcept(noexcept([] { return 0; }())) { return 0; });
 using d = decltype(sizeof([] static { return 0; }));
 
 }
 
 namespace lambda_in_trailing_decltype {
 auto x = ([](auto) -> decltype([] {}()) {}(0), 2);
 }
+
+namespace lambda_in_constraints {
+struct WithFoo { static void foo(); };
+
+template <class T>
+concept lambda_works = requires {
+    []() { T::foo(); };
+};
+
+static_assert(!lambda_works<int>);
+static_assert(lambda_works<WithFoo>);
+
+template <class T>
+int* func(T) requires requires { []() { T::foo(); }; };
+double* func(...);
+
+static_assert(__is_same(decltype(func(0)), double*));
+static_assert(__is_same(decltype(func(WithFoo())), int*));
+
+template <class T>
+auto direct_lambda(T) -> decltype([] { T::foo(); }) {}
+void direct_lambda(...) {}
+
+void recursive() {
+    direct_lambda(0); // expected-error@-4 {{type 'int' cannot be used prior to '::'}}
+                      // expected-note@-1 {{while substituting deduced template arguments}}
+    bool x = requires { direct_lambda(0); }; // expected-error@-6 {{type 'int' cannot be used prior to '::'}}
+                                             // expected-note@-1 {{while substituting deduced template arguments}}
+
+}
+}

clang/test/SemaCXX/warn-unused-lambda-capture.cpp

void test_templated() {
   NonTrivialDestructor dest;
   auto explicit_by_value_non_trivial_destructor = [dest] {};
 
   volatile int v;
   auto explicit_by_value_volatile = [v] {};
 }
 
 void test_use_template() {
-  test_templated<int>(); // expected-note{{in instantiation of function template specialization 'test_templated<int>' requested here}}
+  test_templated<int>(); // expected-note 13{{in instantiation of function template specialization 'test_templated<int>' requested here}}
 }
 
 namespace pr35555 {
 int a;
 void b() {
   int c[a];
   auto vla_used = [&c] { return c[0]; };
   auto vla_unused = [&c] {}; // expected-warning{{lambda capture 'c' is not used}}
 }
 } // namespace pr35555

clang/www/cxx_status.html

</tr>
     <tr>
       <td>Default constructible and assignable stateless lambdas</td>
       <td><a href="https://wg21.link/p0624r2">P0624R2</a></td>
       <td class="full" align="center">Clang 8</td>
     </tr>
     <tr>
       <td>Lambdas in unevaluated contexts</td>
       <td><a href="https://wg21.link/p0315r4">P0315R4</a></td>
-      <td class="partial" align="center">
-        <details><summary>Partial</summary>
-          temp.deduct/9 is not implemented yet.
-        </details>
-      </td>
+      <td class="full" align="center">Clang 17</td>
     </tr>
     <!-- Jacksonville papers -->
     <tr>
       <td><tt>[[no_unique_address]]</tt> attribute</td>
       <td><a href="https://wg21.link/p0840r2">P0840R2</a></td>
       <td class="full" align="center">Clang 9</td>
     </tr>
     <tr>