This is an archive of the discontinued LLVM Phabricator instance.

[Sema] Fix assertion failure when instantiating requires expression
ClosedPublic

Authored by ilya-biryukov on Jun 10 2022, 4:28 AM.

Details

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.

Diff Detail

Event Timeline

ilya-biryukov created this revision.Jun 10 2022, 4:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 10 2022, 4:28 AM
ilya-biryukov requested review of this revision.Jun 10 2022, 4:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 10 2022, 4:28 AM

@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.

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?

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

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 added inline comments.Jun 10 2022, 7:29 AM
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 added inline comments.
clang/lib/Sema/SemaConcept.cpp
352

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

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.

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 added inline comments.Jun 10 2022, 9:10 AM
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 added inline comments.Jun 10 2022, 9:49 AM
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 added inline comments.Jun 10 2022, 10:35 AM
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.

  • Update test, check error messages
ilya-biryukov marked an inline comment as done.Jun 22 2022, 4:56 AM

@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 added inline comments.Jun 22 2022, 6:27 AM
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 added inline comments.Jun 22 2022, 8:59 AM
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 accepted this revision.Jun 22 2022, 9:03 AM

Ah, i see! Thanks for the explanation!

This revision is now accepted and ready to land.Jun 22 2022, 9:03 AM
This revision was landed with ongoing or failed builds.Jun 23 2022, 7:20 AM
This revision was automatically updated to reflect the committed changes.