Page MenuHomePhabricator

[P0857R0 Part B] Resubmit an implemention for constrained template template parameters
ClosedPublic

Authored by lime on Sep 18 2022, 1:54 AM.

Details

Summary

This function had been submitted by @erichkeane long time ago. However, he has not been working on it. So I submit a new patch with some minor differences.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
lime added a comment.EditedOct 5 2022, 9:30 PM

Thanks for the advice. I used AdjustConstraintDepth before subsume. The adjusted constraints are assigned to new addresses, but I think MutableArrayRef could be used here.

what do you mean by 'tailing' here?

I wanted to express the require clauses, as they are stored in TrailingObject.

What exactly is going on here? I would expect the 'AdjustConstraintDepth' work to have already made these basically equal.

AdjustConstraintDepth works here, but I missed it before you mentioned it.

I'm sorry that this update is broken. Some cases are crashed, and s11 in p3-2a.cpp is rejected. Perhaps, I should place AdjustConstraintDepth in another place rather than IsAtLeastAsConstrained, as the depths in Exprs already equal to each other, but the calculations from NamedDecls do not when it comes to s11.

erichkeane accepted this revision.Oct 6 2022, 6:06 AM
erichkeane added inline comments.
clang/lib/Sema/SemaConcept.cpp
625

SemaRef or S is our common nomenclature.

This revision is now accepted and ready to land.Oct 6 2022, 6:06 AM
lime updated this revision to Diff 465750.EditedOct 6 2022, 8:29 AM

I updated the patch to fix the previous problem about failing to pass unit tests. And, isn't this patch accepted a little quickly? BTW, NormalizationCache becomes heavier than before.

erichkeane requested changes to this revision.Oct 6 2022, 8:34 AM

I updated patch to fix the previous problem that failed to pass unit tests. And, isn't this patch accepted a little quickly? BTW, NormalizationCache becomes heavier than before.

Huh, woah, Phab didn't show me 1/2 this patch the last time. The changes in Sema.h and the changes of CalculateTemplateDepthForConstraints just weren't there...

So yeah, I guess, spend more time on this?

This revision now requires changes to proceed.Oct 6 2022, 8:34 AM
lime updated this revision to Diff 466056.EditedOct 7 2022, 6:22 AM

The changes in Sema.h and the changes of CalculateTemplateDepthForConstraints

I think it might be fine now. The above changes are related to NormalizationCache. This cache used to take NamedDecl as its key. However, constraints need to be adjusted to different depths, and p3-2a.cpp can reproduce the case. Thus, NameDecl is not enough, and a heavier key is used. But the needs to adjust the depth seem unique to template-template parameter, so I'm not sure whether there is a better solution. Another performance issue is about IsAtLeastAsConstrained. This function takes ArrayRef as its argument, which leads to new spaces for potentially adjusted constraints. I think MutableArryRef could be used here. At last, CalculateTemplateDepthForConstraints may be incomplete, as I don't know all the possibilities about getting depths from constraint expressions. The constraint in template<template <C T> class> has a depth equal to 0. Thus, calculating from NamedDecl is unreliable here.

BTW, this comment includes an update that involves git clang-format.

lime updated this revision to Diff 467039.Oct 12 2022, 1:08 AM

I updated the patch as I said, while kept the key of NormalizationCache relatively heavy. That means I:

  • changed the parameter of IsAtLeastAsConstrained to MutableArrayRef,
  • and let the new CalculateTemplateDepthForConstraints handle BinaryOperator and ParenExpr.
erichkeane added inline comments.Oct 12 2022, 6:58 AM
clang/lib/Sema/SemaConcept.cpp
599

I'd like some sort of assert in the case where you don't know what to do here. We need to collect all of these cases best we can in advance.

I'd suggest ALSO running libcxx tests against this once you have the assert in place, which should help.

668

Unless I'm missing something, I don't think this idea of 'unify constraint depth' is correct. We should be able, from the decl itself, to determine the depths? What is the difference here that I'm not getting?

1283

Can you explain why this is a MutableArrayRef now? I believe this means it'll now modify the arrays that are passed into it, which we don't necessarily want, right? A new

lime added a comment.EditedOct 12 2022, 8:11 AM

Unless I'm missing something, I don't think this idea of 'unify constraint depth' is correct. We should be able, from the decl itself, to determine the depths? What is the difference here that I'm not getting?

It is explained by the inline comments in sequence.

Can you explain why this is a MutableArrayRef now? I believe this means it'll now modify the arrays that are passed into it, which we don't necessarily want, right?

In the previous update, I mentioned using ArrayRef is not as efficient as MutableArrayRef. And there was no feedback on my comment for several days, so I changed it as I said. Additionally, I found some code once called IsAtLeastAsConstrained for two constraints, and then call IsAtLeastAsConstrained again with the sequence of the two constraints swapped. So using MutableArrayRef also saves a potential adjustment.
Any way, adjusting depths here might be unique to template template parameters. If so, parsing the require clause in the unit test with depth equal to 0 should be a better solution, and things about CalculateTemplateDepthForConstraints and ArrayRef could remain unchanged.

clang/lib/Sema/SemaConcept.cpp
589
  1. The orignal CalculateTemplateDepthForConstraints calculates the depth from NamedDecl.
631
  1. And it was only called in AreConstraintExpressionsEqual.
668
  1. I extracted the calls to the original CalculateTemplateDepthForConstraints as UnifyConstraintDepthFromDecl. Calculating from a declaration is indeed not accurate, as it returns 1 for template<template <C T> class>, but the depth in the constraint is actually 0. This is one reason why a previous version of patch breaks some unit tests. But I leaves it to keep the code unchanged functionally.
erichkeane added inline comments.Oct 12 2022, 8:52 AM
clang/lib/Sema/SemaConcept.cpp
668

Hmm... SO it seems based on debugging that the issue is exclusive with template template parameters. It DOES make sense that the inner-template is 'deeper', but I think the problem is that getTemplateInstantiationArgs isn't correctly handling a ClassTemplateDecl, so the "D2" in IsAtLeastAsConstrainedAs is returning 0, instead of 1.

The "Depth" of something is the 'number of layers of template arguments'. So for: 'template<template <C T> class>', the answer SHOULD be 1.

So I think the problem is basically that for X, the answer should ALSO be 1 (since it has template parameters), but we aren't handling it. So I think we just need to correctly just call the ClassTemplateDecl::getTemplatedDecl at one point on that one.

1283

I see your response... I am a bit concerned about the use of this in SemaTemplate, which re-uses the generated array after this however (though for diagnostics?).

Everywhere else doesn't seem to be using the underlying array after the fact.

lime added inline comments.Oct 12 2022, 8:12 PM
clang/lib/Sema/SemaConcept.cpp
668

I guess there could be another patch improving the calculation about depth. In this patch, I just adjust the calculation to pass unit tests about template template parameters.

1283

The function MaybeEmitAmbiguousAtomicConstraintDiagnostic calls subsume on AtomicConstraint without adjusting depths. So, I guess it is fine to reuse the unified arrays.

lime added inline comments.Oct 12 2022, 9:57 PM
clang/lib/Sema/SemaConcept.cpp
599

I'm afraid that assertions would abort Clang on many code. This function serves as a check for AdjustConstraintDepth, and this class looks like just handling TemplateTypeParmType. The function has already handled TemplateTypeParmType. And determining cases that should trigger the assertions also involves the subsumption of atomic constraints. It is needed to check the depth according to TemplateTypeParmType, because the identity of QualType involves the depth, and then effects the subsumption. There will be some works to determine which cases are the same, and leave assertions for the cases. This kind of works is highly related to the depth and the subsumption, while I think it is less related to template template parameters.

erichkeane added inline comments.Oct 13 2022, 6:31 AM
clang/lib/Sema/SemaConcept.cpp
599

The point of an assertion would be to do just that! We WANT to make sure we get all those assertions. That said, I'm unconvinced that this code here is necessary.

668

Right, but I'm saying how you're doing it is incorrect and will likely result in incorrect compilations

lime added a comment.EditedOct 16 2022, 7:31 AM

I think I located the problem. In the line 4014 of the file SemaTemplateInstantiateDecl.cpp, the requires clause is not instantiated as the parameters of the template parameter list, and these parameters have been instantiated with a shallower depth. So that's the reason why the depths are not confirm between the T in template <template <C T> class> and the constraints on the instantiated parameters. I guess adjusting depths should be unnecessary in IsAtLeastAsConstrained, if the requires clause was correctly instantiated, so should changes related to SemaConcept.cpp. I will work on this later.

I think I located the problem. In the line 4014 of the file SemaTemplateInstantiateDecl.cpp, the requires clause is not instantiated as the parameters of the template parameter list, and these parameters have been instantiated with a shallower depth. So that's the reason why the depths are not confirm between the T in template <template <C T> class> and the constraints on the instantiated parameters. I guess adjusting depths should be unnecessary in IsAtLeastAsConstrained, if the requires clause was correctly instantiated, so should changes related to SemaConcept.cpp. I will work on this later.

I wouldn't expect the requires clause (nor any other concept related AST node) to be instantiated at all until it is going through 'checking', which is the purpose of the deferred concepts patch. That said, SemaTemplateInstantiateDecl.cpp:4014 is in the middle of adjustForRewrite, which isn't clear to me what you mean.

That said, I'm not sure what the

lime added a comment.EditedOct 18 2022, 6:33 AM

which isn't clear to me what you mean

  • In the function Sema::CheckTemplateArgument at line 5725, Params has been substituted in a way all TemplateTypeParmDecls are instantiated with a smaller depth, and so are constraints of them at SemaTemplateInstantiateDecl.cpp:2769, while the requires clause remains the same.
  • Then CheckTemplateArgument calls CheckTemplateTemplateArgument which calls IsAtLeastAsConstrained with the original declaration and the constraint collected from Params. Thus, in IsAtLeastAsConstrained, the depth calculated from the declaration will not reflect the depth in the constraint.
  • It should be fine to not adjust the depths between two constraints passed to IsAtLeastAsConstrained if the requires clause is not parsed, as they are already the same. But it is not the case when the constraint is from a requires clause, as requires clauses are not substituted. However, calculating from declarations will break the original case.

I wouldn't expect the requires clause (nor any other concept related AST node) to be instantiated at all until it is going through 'checking'

The function TemplateDeclInstantiator::SubstTemplateParams instantiates constraints like the one template <template <C T> class>, as I mentioned above. So it is already happened.

which isn't clear to me what you mean

  • In the function Sema::CheckTemplateArgument at line 5725, Params has been substituted in a way all TemplateTypeParmDecls are instantiated with a smaller depth, and so are constraints of them at SemaTemplateInstantiateDecl.cpp:2769, while the requires clause remains the same.
  • Then CheckTemplateArgument calls CheckTemplateTemplateArgument which calls IsAtLeastAsConstrained with the original declaration and the constraints collected from Params. Thus, in IsAtLeastAsConstrained, a depth calculated from the declaration will not reflect the depth in the constraint.
  • It should be fine to not adjust the depths between two constraints passed to IsAtLeastAsConstrained if the requires clause is not parsed, as they are already the same. But it is not the case when the constraint is from a requires clause, as requires clauses are not substituted. However, calculating from declarations will break the original case.

It sounds like perhaps we've instantiated constraints we shouldn't have in the case of template-template parameters. Based on what you're saying, I'm concerned then that perhaps the deferred concept instantiation didn't work right for template-template constraints? That might require more work on that then before anything could happen here.

Otherwise, I would expect calculating from the Template Template Decl to work, (though its likely it doesn't actually 'add' a layer yet, since I don't think we've needed that yet, so an extra bit of work there would need to be done).

I wouldn't expect the requires clause (nor any other concept related AST node) to be instantiated at all until it is going through 'checking'

The function TemplateDeclInstantiator::SubstTemplateParams instantiates constraints like template <template <C T> class>, so it is already happened.

If that is happening outside of a constraint evaluation, that is likely incorrect, and perhaps part of the problem.

So I've been messing around with this a bit, and am somewhat confident that IsAtLeastAsConstrainedAs should just contain:

unsigned Depth1 = CalculateTemplateDepthForConstraints(*this, D1);
unsigned Depth2 = CalculateTemplateDepthForConstraints(*this, D2);
  
for (size_t I = 0; I != AC1.size() && I != AC2.size(); ++I) {
  if (Depth2 > Depth1) {
    AC1[I] = AdjustConstraintDepth(*this, Depth2 - Depth1).
      TransformExpr(const_cast<Expr*>(AC1[I])).
      get();
  } else if (Depth1 > Depth2) {
    AC2[I] = AdjustConstraintDepth(*this, Depth1 - Depth2).
      TransformExpr(const_cast<Expr*>(AC2[I])).
      get();
  }
}

However, I see in the example:

template<typename T> concept C = T::f();
template<C> struct X{};

template<template<C> class P> struct S1 { }; // #S1
S1<X> s11;

That this fails because the type-constraint has already been instantiated during the SubstTemplateParams call ~5735 in SemaTemplate.cpp. I believe that to be an error, and the type-constraint on the TemplateTypeParmDecl should NOT be instantiated.

That line seems to change:

TemplateTypeParmDecl 0x149b2d20 <partb.cpp:4:19> col:20 Concept 0x149b2740 'C' depth 1 index 0
`-ConceptSpecializationExpr 0x149b2e58 <col:19> 'bool' Concept 0x149b2740 'C'
  `-TemplateArgument <col:20> type 'type-parameter-1-0'
    `-TemplateTypeParmType 0x149b2df0 'type-parameter-1-0' dependent depth 1 index 0
      `-TemplateTypeParm 0x149b2d20 ''

To

TemplateTypeParmDecl 0x149d1550 <partb.cpp:4:19> col:20 Concept 0x149b2740 'C' depth 0 index 0
`-ConceptSpecializationExpr 0x149d1668 <col:19> 'bool' Concept 0x149b2740 'C'
  `-TemplateArgument <col:20> type 'type-parameter-0-0'
    `-TemplateTypeParmType 0x149d15f0 'type-parameter-0-0' dependent depth 0 index 0
      `-TemplateTypeParm 0x149d1550 ''

While the TemplateTypeParmDecl is CORRECT to be changed like this, the ConceptSpecializationExpr should NOT have its arguments changed, thats the whole point of the deferred concepts implementation.

IN LOOKING, it seems that the problem is that the instantiator set up by SubstTemplateParams doesn't set the "EvaluateConstraints" to false, as it should be.

I did a test-patch here: https://reviews.llvm.org/D136468 (for you to look at, not for review!). However, I am getting 4 test failures that I suspect are a result of needing to stop evaluating constraints early elsewhere as well. I'm about done with being able to look at this today, so if you get a chance, you might find that useful to look into.

lime updated this revision to Diff 469976.Oct 23 2022, 4:20 AM

I updated the patch based on D136468. I added a change which I think could be a fix to the specialization problem. It is just skipping the addition of the level where the specialization specialized from, as it seems to effect the calculation of the depth but not the depth in the constraint.

Denote that I got a linking error during ninja check-all, so I try to upload directly and see if it passes all the cases. And the require clauses seem not to be instantiated even if EvaluateConstraints is true.

lime updated this revision to Diff 469982.Oct 23 2022, 6:08 AM

Update for the format check.

I'm reasonably OK with this, I'm disappointed the 'skip for specialization' is what was required, but I don't think I know of a better way. I'll hold off approving this until I've confirmed that libcxx tests + libcxx-modules-tests are properly passing as a result of this.

ALSO; this is missing the cxx_status.html and release-notes, so please re-add those!

I'm reasonably OK with this, I'm disappointed the 'skip for specialization' is what was required, but I don't think I know of a better way. I'll hold off approving this until I've confirmed that libcxx tests + libcxx-modules-tests are properly passing as a result of this.

I wnated to test this config locally, but it doesnt seem to be working for me? But you can modify this patch modify the DELETEME file in libcxx (see how he did it here: https://reviews.llvm.org/D127695 put it in the review but didnt commit it), it will cause libcxx pre-commit, which I think we shoudl do. Just don't commit the DELETEME file obviously.

lime updated this revision to Diff 470679.Oct 25 2022, 7:01 PM

Update as required. Also, I need the following modification to complete ninja check-all. Maybe, I should submit another patch.

diff --git a/clang/unittests/Support/CMakeLists.txt b/clang/unittests/Support/CMakeLists.txt
index 956b3a7561..2413088a2b 100644
--- a/clang/unittests/Support/CMakeLists.txt
+++ b/clang/unittests/Support/CMakeLists.txt
@@ -9,4 +9,7 @@ add_clang_unittest(ClangSupportTests
 clang_target_link_libraries(ClangSupportTests
   PRIVATE
   clangFrontend
+  clangAST
+  clangSerialization
+  clangBasic
   )
Herald added a project: Restricted Project. · View Herald TranscriptOct 25 2022, 7:01 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
lime updated this revision to Diff 470686.Oct 25 2022, 8:13 PM

Solve the conflicts, and the issue about CMakeLists.txt had been solved by upstream.

lime updated this revision to Diff 470702.Oct 25 2022, 9:45 PM

Update for the format check.

lime updated this revision to Diff 470739.Oct 26 2022, 1:23 AM

Solve the format issue further.

lime updated this revision to Diff 470746.Oct 26 2022, 2:02 AM

Solve the conflicts.

lime updated this revision to Diff 470779.Oct 26 2022, 4:40 AM

The previous update for conflicts lacks a comma, and the comma was added.

Still need release notes!

lime updated this revision to Diff 470800.Oct 26 2022, 6:21 AM
lime retitled this revision from Resubmit an implemention for constrained template template parameters [P0857R0 Part B] to [P0857R0 Part B] Resubmit an implemention for constrained template template parameters.

Update release notes as required.

erichkeane accepted this revision.Oct 26 2022, 6:23 AM

I'm happy with this once the release-note is clarified and all libcxx pre-commit works with it.

clang/docs/ReleaseNotes.rst
562

I'm not sure what you're trying to say here? Is there just a typo that I'm missing that makes this perfectly clear?

ALSO: When you commit this: please try to use a more descriptive commit message, more similar to what I posted in Phab originally.

lime updated this revision to Diff 470816.Oct 26 2022, 7:48 AM

Update commit message, and remove the "for" in release notes, which should make the phrase correct in grammar.

erichkeane added inline comments.Oct 26 2022, 10:29 AM
clang/docs/ReleaseNotes.rst
562

Sorry, I'm still getting caught up on what 'which words' means here?

h-vetinari added inline comments.Oct 26 2022, 6:03 PM
clang/docs/ReleaseNotes.rst
562

Maybe the intention was something along the lines of: words -> specifies

clang/test/SemaTemplate/concepts.cpp
61–62

That FIXME should be removed

lime updated this revision to Diff 471046.EditedOct 27 2022, 12:56 AM

Update as suggested. Could you please help me apply this patch? It seems unsuitable to grant a fresh account the accessibility.

Update as suggested. Could you please help me apply this patch? It seems unsuitable to grant a fresh account the accessibility.

Sure, I just need an email address and name in the form of "Name ToAppear <Email.Name@Domain.whatever>".

lime added a comment.Oct 27 2022, 6:19 AM

Liming Liu <gangliugangliu.ml@outlook.com>

It is also included in the patch file.

Liming Liu <gangliugangliu.ml@outlook.com>

It is also included in the patch file.

Ok, I'll use that. Typically we don't use a separately attached patch-file, we just use the phabricator 'download patch', so I didn't think to look for it there.

This revision was not accepted when it landed; it landed in state Needs Review.Oct 27 2022, 6:42 AM
This revision was automatically updated to reflect the committed changes.

Congratulations for landing this!

How far do you (both) think we're away from completing concepts? Are the issues (aside from CWG1496 & CWG1734) mentioned on https://clang.llvm.org/cxx_status.html tracked anywhere else? I see that https://github.com/orgs/llvm/projects/14 has 45 concept-related issues, but presumably not all of those are necessary to set the feature macro?

Congratulations for landing this!

How far do you (both) think we're away from completing concepts? Are the issues (aside from CWG1496 & CWG1734) mentioned on https://clang.llvm.org/cxx_status.html tracked anywhere else? I see that https://github.com/orgs/llvm/projects/14 has 45 concept-related issues, but presumably not all of those are necessary to set the feature macro?

There is enough on that list of failures that I'm not quite comfortable updating the macro. I think this is a question we should evaluate right before the release.