[Sema] Fix assertion failure when instantiating requires expression

[ilya-biryukov]

Summary

Fixes #54629.
The crash is is caused by the double template instantiation.
See the added test. Here is what happens:

• Template arguments for the partial specialization get instantiated.
• This causes instantitation into the corrensponding requires expression.
• TemplateInsantiator correctly handles instantiation of parameters inside RequiresExprBody and instantiates the constraint expression inside the NestedRequirement.
• To build the substituted NestedRequirement, TemplateInsantiator calls Sema::BuildNestedRequirement calls CheckConstraintSatisfaction, which results in another template instantiation (with empty template arguments). This seem to be an implementation detail to handle constraint satisfaction and is not required by the standard.
• The recursive template instantiation tries to find the parameter inside RequiresExprBody and fails with the corresponding assertion.

Note that this only happens as both instantiations happen with the class
partial template specialization set as Sema.CurContext, which is
considered a dependent DeclContext.

To fix the assertion, avoid doing the recursive template instantiation
and instead evaluate resulting expressions in-place.

[ilya-biryukov]

@saar.raz @erichkeane please let me know if you are the right people to review this.
The change might need a little more refactoring, e.g. placement new should probably move to a helper in Sema to align with what clang usually does.

I wanted to align early on the approach taken. Let me know if you have better ideas on how to fix this.

[ilya-biryukov]

Fixed issue is: 54629

[erichkeane]

I'm not quite understanding this yet, so I'll have to take another look early next week. However, I AM intending to get https://reviews.llvm.org/D126907 committed in the next week or so. Could you perhaps see how it interacts with that? Its a sizable, multi-month project that I'd like to make sure doesn't get stuck in a rebase-loop again.

clang/lib/Sema/SemaConcept.cpp

352

Can you explain this more? How does this work, and why don't we do that directly instead?

clang/lib/Sema/SemaTemplateInstantiate.cpp

2041

This branch ends up being empty if asserts are off. Also, it results in CheckConstraintExpression happening 2x, which ends up being more expensive after https://reviews.llvm.org/D126907

clang/test/SemaTemplate/concepts-PR54629.cpp

11

Simply 'doesn't crash' isn't quite enough for a test here, I would like to see some level of confirmation which of the versions of "A" get selected here. So perhaps A<double>{}.some_func(); call that wouldn't be valid/etc. And perhaps a situation where both instances have a constraint and and we diagnose why it doesn't fit?

[ilya-biryukov]

• Do not introduce empty branches on asserts
• Test whether specialization or primary template gets picked

[ilya-biryukov]

In D127487#3573180, @erichkeane wrote:

I'm not quite understanding this yet, so I'll have to take another look early next week. However, I AM intending to get https://reviews.llvm.org/D126907 committed in the next week or so. Could you perhaps see how it interacts with that? Its a sizable, multi-month project that I'd like to make sure doesn't get stuck in a rebase-loop again.

Sure, I will try to rebase my patch on top of your work and report what happens.

clang/lib/Sema/SemaConcept.cpp

352

That's entangled with calculateConstraintSatisfaction. I actually tried to do it directly, but before passing expressions to this function calculateConstraintSatisfaction calls IgnoreParenImpCasts(), which strips away the lvalue-to-rvalue conversion.
And we need this conversion so that the evaluation that runs after this callback returns actually produces an r-value.

Note that the other call to calculateConstraintSatisfaction also calls PerformContextuallyConvertToBool after doing template substitution into the constraint expression.

I don't have full context on why it's the way it is, maybe there is a more fundamental change that helps with both cases.

clang/lib/Sema/SemaTemplateInstantiate.cpp

2041

This branch ends up being empty if asserts are off. Also, it results in CheckConstraintExpression happening 2x, which ends up being more expensive after https://reviews.llvm.org/D126907

Yeah, good point, I have update it.

I am not sure why would CheckConstraintExpression be called twice, could you elaborate? Note that we do not call BuildNestedRequirement anymore and use placement new directly to avoid extra template instantiations. Instead we call CheckConstraintExpression directly to account for any errors.

clang/test/SemaTemplate/concepts-PR54629.cpp

11

I have added the test for primary template vs specialization.
Keeping a comment open to add a test for two specializations too, I will do this a bit later.

[erichkeane]

clang/lib/Sema/SemaConcept.cpp

352

Hmm... my understanding is we DO need these to be a boolean expression eventually, since we have to test them as a bool, so that is why the other attempts the converesion. If you think of any generalizations of this, it would be appreciated, I'll think it through as well.

clang/lib/Sema/SemaTemplateInstantiate.cpp

2041

This check does not seem to cause a 'return' to the function, but then falls through to the version on 2052, right?

CheckConstraintExpression/CheckConstraintSatisfaction(i think?) ends up now having to re-instantiate every time it is called, so any ability to cache results ends up being beneficial here.

[royjacobson]

clang/lib/Sema/SemaConcept.cpp

352

Note we already have a related bug about this https://github.com/llvm/llvm-project/issues/54524

[ilya-biryukov]

I've checked that the change works fine on top of D126907. The bug is still there after D126907 and gets fixed by this.
Also, the merge conflict is actually minimal, no code changes intersect.

clang/lib/Sema/SemaConcept.cpp

352

Yeah, they have to be bool and we actually check for that in CheckConstraintExpression. The standard explicitly mentions only the lvalue-to-rvalue conversion should be performed.

[temp.constr.atomic]p3 If substitution results in an invalid type or expression, the constraint is
not satisfied. Otherwise, the lvalue-to-rvalue conversion (7.3.1) is performed if necessary, and E shall be a constant expression of type bool.

However, in the calls to calculateConstraintSatisfaction we do a more generic boolean conversion, but the comment in the other call site suggests this probably accidental and we actually want a less generic conversion:

// Substitution might have stripped off a contextual conversion to
// bool if this is the operand of an '&&' or '||'. For example, we
// might lose an lvalue-to-rvalue conversion here. If so, put it back
// before we try to evaluate.
if (!SubstitutedExpression.isInvalid())
  SubstitutedExpression =
      S.PerformContextuallyConvertToBool(SubstitutedExpression.get());

I am happy to take a look at fixing the mentioned bug.

clang/lib/Sema/SemaTemplateInstantiate.cpp

2041

The number of calls to these functions is actually the same.

CheckConstraintExpression used to be called during CheckConstraintSatisfaction (that does instantiations) for every atomic constraint after the substitution. It merely checks that each constraint have a bool type and does not do any substitutions, so it's pretty cheap anyway.

CheckConstraintSatisfaction was called inside BuildNestedRequirement, we now call a different overload here directly that does not do any extra template instantiations directly.

That way we end up doing the same checks without running recursive template instantiations.

[erichkeane]

In D127487#3573667, @ilya-biryukov wrote:

I've checked that the change works fine on top of D126907. The bug is still there after D126907 and gets fixed by this.
Also, the merge conflict is actually minimal, no code changes intersect.

Thanks for looking into this! I DID see it was still in place after the fact, but wanted to make sure this wouldn't break any more of the tests.

clang/lib/Sema/SemaConcept.cpp

352

Hmm... yeah, I find myself wondering if there is a better lval/rval conversion function here, and I'm guessing the contextually convert to bool is the wrong one.

clang/lib/Sema/SemaTemplateInstantiate.cpp

2041

Hmm... I guess what I'm saying is: I would like it if we could minimize/reduce the calls to calcuateConstraintSatisfaction (in SemaConcept.cpp) that does the call to SubstConstraintExpr (or substExpr).

That ends up being more expensive thanks to my other patch.

[ilya-biryukov]

clang/lib/Sema/SemaConcept.cpp

352

Yep, it's definitely the wrong function. I could not find a better one, but I only briefly looked through the options.

I will have to find one or implement it while fixing https://github.com/llvm/llvm-project/issues/54524.

clang/lib/Sema/SemaTemplateInstantiate.cpp

2041

Ah, yes, that makes sense. Note that CheckConstraintSatisfaction call on 2052 does not do any substitutions, it merely evaluates the expressions if they are not dependent.

I will have to look more closely into your patch to get a sense of why substituting to the constraint expressions is more expensive after it.

BTW, I was wondering if there is any reason to substitute empty template arguments to evaluate non-dependent constraints? (This is what CalculateConstraintSatisfaction does)
I feels like merely evaluating those should be enough.

[erichkeane]

clang/lib/Sema/SemaTemplateInstantiate.cpp

2041

ah, I see! Constraint expressions get 'more expensive' because now we actually have to do substitution EVERY time we evaluate, rather than just having an already non-dependent expression stored. This is because the deferred constraint instantiation requires that we re-evaluate it just about every time we check a constraint.

Which version of CalculateConstraintSatisfaction are you referring to? it DOES actually appear that the one you modify above doesn't actually DO any substitution. it DOES looklike it does some checking to make sure we specifically are a boolean expr ([temp.constr.atompic]p1 ~ line 210), but it isn't clear to me what the logic there is either.

[ilya-biryukov]

clang/lib/Sema/SemaTemplateInstantiate.cpp

2041

This is because the deferred constraint instantiation requires that we re-evaluate it just about every time we check a constraint.

That makes sense. And this is to meet the requirements of the standard, right? Reading through it, we should keep "template parameter mappings" and original expressions for atomic constraint and only do the substitution once we actually need to check the constraint.

PS I should really read the code first to understand what it's doing, but hopefully I'm on the right track.

Which version of CalculateConstraintSatisfaction are you referring to?

Sorry, got confused here. I meant the overload of CheckConstraintSatisfaction that does empty template argument substitution. I was wondering whether we need template instantiations there in the first place. It looks like it might be there for code reuse and we can instead just evaluate the expressions directly. But maybe I'm missing something.

As for the overload of CheckConstraintSatisfaction that does no substitutions.

looklike it does some checking to make sure we specifically are a boolean expr.

The check for boolean type is done by CheckConstraintExpression during instantiation. However, there is a change in the body of the function to add lvalue-to-rvalue conversion. This is necessary to make sure the code inside calculateConstraintSatisfaction gets correct evaluation results. This overload of CheckConstraintExpression happened to be broken in that regard, but it was not widely used (as all constraints normally get evaluated by the other overload), so this was never caught this.

[ilya-biryukov]

• Update test, check error messages

[ilya-biryukov]

@erichkeane could you take another look at this?

clang/test/SemaTemplate/concepts-PR54629.cpp

11

Added a check for error messages in case of ambiguous specializations and no matching specialization (in terms of function overloads).
For classes there is no way to cause no matching specialization AFAICT.
Either a primary template will be picked and no error message will be shown or its requirements will fail and the error message will not mention the specializations at all.

[erichkeane]

clang/lib/Sema/SemaTemplateInstantiate.cpp

2039

I think I'd rather collapse this into SOMETHING like:

assert((TransConstraint.isInvalid() || (SemaRef.CheckConstraintExpr(TransConstraint.get() || Trap.hasErrorOccurred()) && "...");

I think thats right?

2048

Same sorta thing here, if our check is only used for an assert, we should call it in the assert.

[ilya-biryukov]

clang/lib/Sema/SemaTemplateInstantiate.cpp

2039

CheckConstraintExpression has to always run, even when assertions are disabled. It does checks for C++ semantics, e.g. checks that the type is bool.

The assertion is only there to check that whenever the function fails, Trap captures the actual diagnostic so the code below that relies on hasErrorOccurred ends up in a valid state.

2048

See the comment above, the call to CheckConstraintSatisfaction is also to implement semantic C++ checks, not solely for assertion.

[erichkeane]

Ah, i see! Thanks for the explanation!

clang/lib/Sema/SemaConcept.cpp

bool Sema::CheckConstraintSatisfaction(
   SatisfactionCache.InsertNode(Satisfaction.release());
   return false;
 }
 
 bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
                                        ConstraintSatisfaction &Satisfaction) {
   return calculateConstraintSatisfaction(
       *this, ConstraintExpr, Satisfaction,
-      [](const Expr *AtomicExpr) -> ExprResult {
-        return ExprResult(const_cast<Expr *>(AtomicExpr));
+      [this](const Expr *AtomicExpr) -> ExprResult {
+        // We only do this to immitate lvalue-to-rvalue conversion.
+        return PerformContextuallyConvertToBool(const_cast<Expr *>(AtomicExpr));
       });
 }
 
 bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,
                                     ConstraintSatisfaction &Satisfaction,
                                     SourceLocation UsageLoc) {
   const Expr *RC = FD->getTrailingRequiresClause();
   if (RC->isInstantiationDependent()) {

clang/lib/Sema/SemaTemplateInstantiate.cpp

 //===------- SemaTemplateInstantiate.cpp - C++ Template Instantiation ------===/
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //===----------------------------------------------------------------------===/
 //
 //  This file implements C++ template instantiation.
 //
 //===----------------------------------------------------------------------===/
 
 #include "TreeTransform.h"
+#include "clang/AST/ASTConcept.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTLambda.h"
 #include "clang/AST/ASTMutationListener.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/Expr.h"
+#include "clang/AST/ExprConcepts.h"
 #include "clang/AST/PrettyDeclStackTrace.h"
 #include "clang/AST/TypeVisitor.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/Stack.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Sema/DeclSpec.h"
 #include "clang/Sema/Initialization.h"
 #include "clang/Sema/Lookup.h"
if (Req->isSubstitutionFailure()) {
     return Req;
   }
   Sema::InstantiatingTemplate ReqInst(SemaRef,
       Req->getConstraintExpr()->getBeginLoc(), Req,
       Sema::InstantiatingTemplate::ConstraintsCheck{},
       Req->getConstraintExpr()->getSourceRange());
 
   ExprResult TransConstraint;
+  ConstraintSatisfaction Satisfaction;
   TemplateDeductionInfo Info(Req->getConstraintExpr()->getBeginLoc());
   {
     EnterExpressionEvaluationContext ContextRAII(
         SemaRef, Sema::ExpressionEvaluationContext::ConstantEvaluated);
     Sema::SFINAETrap Trap(SemaRef);
     Sema::InstantiatingTemplate ConstrInst(SemaRef,
         Req->getConstraintExpr()->getBeginLoc(), Req, Info,
         Req->getConstraintExpr()->getSourceRange());
     if (ConstrInst.isInvalid())
       return nullptr;
     TransConstraint = TransformExpr(Req->getConstraintExpr());
+    if (!TransConstraint.isInvalid()) {
+      bool CheckSucceeded =
+          SemaRef.CheckConstraintExpression(TransConstraint.get());
+      (void)CheckSucceeded;
+      assert(CheckSucceeded || Trap.hasErrorOccurred() &&
+                                   "CheckConstraintExpression failed, but "
+                                   "did not produce a SFINAE error");
+    }
+    // Use version of CheckConstraintSatisfaction that does no substitutions.
+    if (!TransConstraint.isInvalid() &&
+        !TransConstraint.get()->isInstantiationDependent() &&
+        !Trap.hasErrorOccurred()) {
+      bool CheckFailed = SemaRef.CheckConstraintSatisfaction(
+          TransConstraint.get(), Satisfaction);
+      (void)CheckFailed;
+      assert(!CheckFailed || Trap.hasErrorOccurred() &&
+                                 "CheckConstraintSatisfaction failed, "
+                                 "but did not produce a SFINAE error");
+    }
     if (TransConstraint.isInvalid() || Trap.hasErrorOccurred())
       return RebuildNestedRequirement(createSubstDiag(SemaRef, Info,
           [&] (llvm::raw_ostream& OS) {
               Req->getConstraintExpr()->printPretty(OS, nullptr,
                                                     SemaRef.getPrintingPolicy());
           }));
   }
-  return RebuildNestedRequirement(TransConstraint.get());
+  if (TransConstraint.get()->isInstantiationDependent())
+    return new (SemaRef.Context)
+        concepts::NestedRequirement(TransConstraint.get());
+  return new (SemaRef.Context) concepts::NestedRequirement(
+      SemaRef.Context, TransConstraint.get(), Satisfaction);
 }
 
 
 /// Perform substitution on the type T with a given set of template
 /// arguments.
 ///
 /// This routine substitutes the given template arguments into the
 /// type T and produces the instantiated type.

clang/test/SemaTemplate/concepts-PR54629.cpp

+// RUN: %clang_cc1 -std=c++20 -verify %s
+
+template <class T>
+struct A {
+  void primary();
+};
+
+template <class T>
+  requires requires(T &t) { requires sizeof(t) > 4; }
+struct A<T> {
+  void specialization1();
+};
+
+template <class T>
+  requires requires(T &t) { requires sizeof(t) > 8; }
+struct A<T> {
+  void specialization2();
+};
+
+int main() {
+  A<char>().primary();
+  A<char[5]>().specialization1();
+  A<char[16]>(); // expected-error {{ambiguous partial specialization}}
+                 // expected-note@10 {{partial specialization matches [with T = char[16]}}
+                 // expected-note@16 {{partial specialization matches [with T = char[16]}}
+}
+
+// Check error messages when no overload with constraints matches.
+template <class T>
+void foo()
+  requires requires(T &t) { requires sizeof(t) < 4; }
+{}
+
+template <class T>
+void foo()
+  requires requires(T &t) { requires sizeof(t) > 4; }
+{}
+
+template <class T>
+void foo()
+  requires requires(T &t) { requires sizeof(t) > 8; }
+{}
+
+void test() {
+  foo<char[4]>();
+  // expected-error@-1 {{no matching function for call to 'foo'}}
+  // expected-note@30 {{candidate template ignored: constraints not satisfied}}
+  // expected-note@31 {{because 'sizeof (t) < 4' (4 < 4) evaluated to false}}
+  // expected-note@35 {{candidate template ignored: constraints not satisfied}}
+  // expected-note@36 {{because 'sizeof (t) > 4' (4 > 4) evaluated to false}}
+  // expected-note@40 {{candidate template ignored: constraints not satisfied}}
+  // expected-note@41 {{because 'sizeof (t) > 8' (4 > 8) evaluated to false}}
+
+  foo<char[16]>();
+  // expected-error@-1 {{call to 'foo' is ambiguous}}
+  // expected-note@35 {{candidate function}}
+  // expected-note@40 {{candidate function}}
+}