Roadmap for a Concepts implementation P0734R0, currently merged into C++20 draft

Hi all,

As I’ve read and seen in Clang’s code, a Concepts implementation in Clang hasn’t really been pushed forward in the past year, with only very, very little code in place right now regarding Concepts, placed by Hubert Tong, CC’d, back in February, and very little to non-existent discussions in the mailing lists.

As of the Toronto meeting back in July, a subset of the original Concepts TS was merged into draft C++20, which omits some shorthand notations for concepts but keeps the core parts of the language feature. Most notably - function concepts were removed, as well as the ‘bool’ keyword after the ‘concept’ keyword, and the ‘introducer’ and “terse/natural syntax” were omitted.

I believe we should go ahead and implement P0734R0 now for the following reasons:

  • P0734R0 hasn’t yet been implemented in any compiler (excluding GCC which implements a different proposal), and furthermore no Concepts implementation was made from specification - Andrew Sutton who worked on the GCC implementation also wrote the proposal. Doing a concepts implementation now would, I believe, help the committee discover defects and in general be more confident in the proposal.
  • to be honest, it is really not that hard to implement, and can, I believe, be done in a month or two.
  • Concepts will be present in C++2a unless something extraordinary happens - if not in their current form, then in a very similar form with maybe a few more terse syntaxes introduced which would not break existing code but just allow for nicer code - in any case, I believe it is a good time to lay a foundation for the core of the language feature which seems pretty stable already and were agreed upon by the committee.

I took a look at the relevant code and the proposal and hereby propose a roadmap for implementing Concepts in clang as it stands today: https://github.com/saarraz/clang-concepts-roadmap
I broke it up into commit-sized chunks, which should take us to a working implementation of the proposal. I’m of course willing to implement all of this if needed.

Please tell me what you think and post issues/pull requests to the roadmap repo or post here.
I’d really like to see this get going.

Thanks!

Saar

Hi all,

As I've read and seen in Clang's code, a Concepts implementation in Clang
hasn't really been pushed forward in the past year, with only very, very
little code in place right now regarding Concepts, placed by Hubert Tong,
CC'd, back in February, and very little to non-existent discussions in the
mailing lists.

As of the Toronto meeting back in July, a subset of the original Concepts
TS was merged into draft C++20, which omits some shorthand notations for
concepts but keeps the core parts of the language feature. Most notably -
function concepts were removed, as well as the 'bool' keyword after the
'concept' keyword, and the 'introducer' and "terse/natural syntax" were
omitted.

I believe we should *go ahead and implement P0734R0 now *for the
following reasons:
- P0734R0
<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0734r0.pdf&gt; hasn't
yet been implemented in any compiler (excluding GCC which implements a
different proposal), and furthermore *no Concepts implementation was made
from specification* - Andrew Sutton who worked on the GCC implementation
also wrote the proposal. Doing a concepts implementation now would, I
believe, help the committee discover defects and in general be more
confident in the proposal.
- to be honest, it is* really not that hard *to implement, and can, I
believe, be done in a month or two.
- Concepts will be present in C++2a unless something extraordinary happens
- if not in their current form, then in a very similar form with maybe a
few more terse syntaxes introduced* which would not break existing code*
but just allow for nicer code - in any case, I believe it is a good time to
lay a foundation for the core of the language feature which seems pretty
stable already and were agreed upon by the committee.

I took a look at the relevant code and the proposal and hereby propose* a
roadmap for implementing *Concepts in clang as it stands today:
https://github.com/saarraz/clang-concepts-roadmap
I broke it up into commit-sized chunks, which should take us to a working
implementation of the proposal. I'm of course willing to implement all of
this if needed.

Thank you for your analysis and the offer to help out!

We are very much open to adding support for P0734R0 to Clang, along with
all other features voted into the working draft for C++20. The only reason
this has not already been implemented is a lack of volunteers such as
yourself with the time to devote to the task.

Your roadmap looks to be in good shape. I have a few suggestions:

* For point 4, consider modeling an id-expression that names a concept
specialization as a DeclRefExpr rather than introducing a new AST node.
That's our general way of representing "an expression denoting a name
associated with some declaration by name lookup", and is currently used for
things like variables, functions and enumerators. This will likely be
significantly simpler if you do in fact make a ConceptSpecialization be a
declaration. (You'll need a templated declaration to live within the
ConceptTemplateDecl anyway, if you're going to follow the usual AST model
where a template declaration is a wrapper around some other declaration.)
However, there may be a reason why this is infeasible -- particularly, the
result of evaluating a concept with a set of arguments may validly change
throughout the compilation of a program, so any notion of tracking /
caching concept specializations might not be workable. This needs more
analysis.

* Consider how constraint normalization and subsumption checking will fit
into the system. These are probably the two biggest pieces to design and
implement.

* Decouple the implementation of requires-expressions from everything else.
I would be inclined to implement them first rather than last, but that's up
to whoever actually does the implementation work.

Hi Saar,

As Richard mentioned, the only reason for the delay has been an issue with finding people with available time to work on the project. I’m adding Changyu and Nathan to the CC because they’ve also been active in this area.

– HT

Great to hear that you’re willing to get this going too :slight_smile:

Can the value of a concept really change throughout the compilation of a program? Doesn’t two phase lookup and the guarantee that templates cannot be further specialized after they’ve been instantiated guarantee this not to happen? ([temp.spec]p5.3)

Well yes, I see a few challenges with normalization and subsumption - please give your input:

  1. The paper introduces “conjunction” and “disjunction” as their own ‘operators’ that act on constraints. I guess the goal there was to avoid people overloading operator&& and operator||. A possible implementation we could do is take the expression as parsed, and replace BinaryOperator nodes with either the same BinaryOperator with its arguments wrapped with casts to bool, or create a new operator opcode and substituting that in. The former has the problem that those bool casts weren’t really written by the user and will be confusing in diagnostics, and frankly do not conform to the paper as they would allow ‘atomic constraints’ to have a type other than bool that has a conversion to bool. The latter is probably the more correct solution but IDK how much work introducing a new operator is gonna be - any input on that?
  2. Regarding normalization - my roadmap already incorporates caching a ‘complete’ version of the constraint-expression, we might as well calculate a normalized version right there and then.
  3. Normalization requires we break up ConceptSpecializationExprs into their constituents, which would circumvent our proposed caching of concept specializations if we were to then calculate the satisfaction of the normalized referencing concept. How about using the non-normalized version of the constraints to calculate the satisfaction and using the normalized version only for subsumption checking? Can you think of any non-conformance issues we get from this approach?
  4. If we’re using the normalized version for subsumption checking only, we might as well delay the normalization to when we need to calculate subsumption.
  5. Should we or should we not cache the result of subsumptions? I tend to think that we should, what do you thing?

They are decoupled except for their required support of partial-concept-ids like so:
requires (T t) {
{ t.foo() }-> Same
}
So I’d rather implement them last after we have concept-ids.

Great to hear that you're willing to get this going too :slight_smile:

the result of evaluating a concept with a set of arguments may validly
change throughout the compilation of a program, so any notion of tracking /
caching concept specializations might not be workable. This needs more
analysis.

Can the value of a concept really change throughout the compilation of a
program? Doesn't two phase lookup and the guarantee that templates cannot
be further specialized after they've been instantiated guarantee this not
to happen? ([temp.spec]p5.3)

Concepts are not instantiated. They are evaluated for satisfaction. Much of
the wording to allow "global" knowledge to be used for instantiating
templates relies on point-of-instantiation.

void foo(int, int);

template <typename T>
concept C = requires (T t) { ::foo(t); };

constexpr bool a = C<int>;

void foo(int, int = 0);
constexpr bool b = C<int>;

static_assert(a != b);

* Consider how constraint normalization and subsumption checking will fit
into the system. These are probably the two biggest pieces to design and
implement.

Well yes, I see a few challenges with normalization and subsumption -
please give your input:
1. The paper introduces "conjunction" and "disjunction" as their own
'operators' that act on constraints. I guess the goal there was to avoid
people overloading operator&& and operator||. A possible implementation we
could do is take the expression as parsed, and replace BinaryOperator nodes
with either the same BinaryOperator with its arguments wrapped with casts
to bool, or create a new operator opcode and substituting that in. The
former has the problem that those bool casts weren't really written by the
user and will be confusing in diagnostics, and frankly do not conform to
the paper as they would allow 'atomic constraints' to have a type other
than bool that has a conversion to bool. The latter is probably the more
correct solution but IDK how much work introducing a new operator is gonna
be - any input on that?

My understanding is that it is viable for conjunction and disjunction to be
represented by && and || for satisfaction checking; it would be
context-dependent during the evaluation whether the node is within an
atomic constraint (and thus not representative of a conjunction or
disjunction). When checking for subsumption, the ordering ceases to matter
and likewise the contents of atomic constraints: a non-AST representation
would like be what is cached.

2. Regarding normalization - my roadmap already incorporates caching a
'complete' version of the constraint-expression, we might as well calculate
a normalized version right there and then.
3. Normalization requires we break up ConceptSpecializationExprs into
their constituents, which would circumvent our proposed caching of concept
specializations if we were to then calculate the satisfaction of the
normalized referencing concept. How about using the non-normalized version
of the constraints to calculate the satisfaction and using the normalized
version only for subsumption checking? Can you think of any non-conformance
issues we get from this approach?

Normalizing only for subsumption checking sounds good.

4. If we're using the normalized version for subsumption checking only, we
might as well delay the normalization to when we need to calculate
subsumption.

Yes.

5. Should we or should we not cache the result of subsumptions? I tend to
think that we should, what do you thing?

I think we should on the basis of candidate pairs. Of course, some
associated constraints may manifestly be such that they cannot be subsumed
except by themselves, and it would make sense to keep that as the first
thing to check.

* Decouple the implementation of requires-expressions from everything
else. I would be inclined to implement them first rather than last, but
that's up to whoever actually does the implementation work.

They are decoupled except for their required support of
partial-concept-ids like so:
requires (T t) {
    { t.foo() }-> Same<bool>
}
So I'd rather implement them last after we have concept-ids.

That's also my inclination; just my 2 cents.

Mmm, good example. So does that mean we cannot hope to cache results of concept evaluations? That sounds like quite the performance hit for highly conceptized code (e.g. ranges), is it not?

Maybe we can form some sort of condition under which a concept evaluation result may be cached? There are, I think, at least some expression classes that cannot change once the concept has been instantiated with a type (e.g. expressions that do not involve namespace lookup).
I’d say that’s premature optimization but it impacts the design quite substantially - do we model concepts specializations as Decls or not?

What worries me about checking for satisfaction with && and || is the following:
[temp.constr.atomic]: "[Example:
template
concept C = sizeof(T) == 4 && !true; // requires atomic constraints
// sizeof(T) == 4 and !true
template
struct S {
constexpr operator bool() const { return true; }
};

template
requires (S{})
void f(T); // #1

void f(int); // #2

void g() {
f(0); // error: expression S{} does not have type bool
// while checking satisfaction of deduced arguments of #1,
// even though #2 is a better match
}
— end example ]"
By using regular Exprs we cannot enforce the bool-ness of operands.

Mmm, good example. So does that mean we cannot hope to cache results of concept evaluations? That sounds like quite the performance hit for highly conceptized code (e.g. ranges), is it not?

Maybe we can form some sort of condition under which a concept evaluation result may be cached? There are, I think, at least some expression classes that cannot change once the concept has been instantiated with a type (e.g. expressions that do not involve namespace lookup).
I’d say that’s premature optimization but it impacts the design quite substantially - do we model concepts specializations as Decls or not?

What worries me about checking for satisfaction with && and || is the following:
[temp.constr.atomic]: "[Example:
template
concept C = sizeof(T) == 4 && !true; // requires atomic constraints
// sizeof(T) == 4 and !true
template
struct S {
constexpr operator bool() const { return true; }
};

template
requires (S{})
void f(T); // #1

void f(int); // #2

void g() {
f(0); // error: expression S{} does not have type bool
// while checking satisfaction of deduced arguments of #1,
// even though #2 is a better match
}
— end example ]"
By using regular Exprs we cannot enforce the bool-ness of operands.

Concepts are not instantiated. They are evaluated for satisfaction. Much
of the wording to allow "global" knowledge to be used for instantiating
templates relies on point-of-instantiation.

void foo(int, int);

template <typename T>
concept C = requires (T t) { ::foo(t); };

constexpr bool a = C<int>;

void foo(int, int = 0);
constexpr bool b = C<int>;

static_assert(a != b);

Mmm, good example. So does that mean we cannot hope to cache results of
concept evaluations? That sounds like quite the performance hit for highly
conceptized code (e.g. ranges), is it not?

Maybe we can form some sort of condition under which a concept evaluation
result may be cached? There are, I think, at least some expression classes
that cannot change once the concept has been instantiated with a type (e.g.
expressions that do not involve namespace lookup).

There are indeed things that can be cached (like an atomic constraint of
::std::is_union_v<T>). Even if the constraint expressed by the concept
specialization cannot be entirely cached, the constraint can be rewritten
when cacheable portions are evaluated.

I'd say that's premature optimization but it impacts the design quite
substantially - do we model concepts specializations as Decls or not?

If I understand you correctly, you are saying that the trade-off is
uncertain on whether using Decls would buy us enough for the cost of having
them.
Using Decls or not affects how we should refer to the concept
specializations from expression nodes that name fully resolved concept
specializations.
If we do not use the Decls to keep enough information around, then they
only form an extra layer of indirection.

Other than that, the purist in me says that concept specializations are
merely a pair of concept template and a set of template arguments. There is
not even an AST with the arguments substituted in.

My understanding is that it is viable for conjunction and disjunction to
be represented by && and || for satisfaction checking; it would be
context-dependent during the evaluation whether the node is within an
atomic constraint (and thus not representative of a conjunction or
disjunction).

What worries me about checking for satisfaction with && and || is the
following:
[temp.constr.atomic]: "[Example:
  template<typename T>
  concept C = sizeof(T) == 4 && !true; // requires atomic constraints
                                     // sizeof(T) == 4 and !true
  template<typename T>
  struct S {
    constexpr operator bool() const { return true; }
  };

  template<typename T>
    requires (S<T>{})
      void f(T); // #1

  void f(int); // #2

  void g() {
  f(0); // error: expression S<int>{} does not have type bool
        // while checking satisfaction of deduced arguments of #1,
        // even though #2 is a better match
  }
— end example ]"
By using regular Exprs we cannot enforce the bool-ness of operands.

I think this depends on timing. I am not sure how eager Clang is in
performing semantic analysis that would trigger implicit conversions. We
probably need to hamper resolution of the && and || operators somehow while
we are in a constraint, but not atomic constraint, context. I believe that
would be sufficient to prevent the type of atomic constraints from being
coerced early.

Hi Saar,

I’d like to help you implement your road map. I’ve finished point 1 and am working on points 2 and 3. I may have some questions in the future, not right now though.

Hi Changyu - did you submit a patch for #1?
Anyways, it’d be great if you could work on requires expressions (25-27) and the diagnostic functions instead, as I already have much of the code figured out for the other steps and it would be a waste if you had to figure it out again yourself

Hi Changyu - did you submit a patch for #1?
Anyways, it’d be great if you could work on requires expressions (25-27) and the diagnostic functions instead, as I already have much of the code figured out for the other steps and it would be a waste if you had to figure it out again yourself

Attached is a patch file that implements point 1 with some comments as to what should be done next.
Changyu - you didn’t answer my question - could you work on requires-expressions and not the other parts for now?

stage_1_remove_existing.patch (27.8 KB)

Sure.

Saar, I believe cfe-commits is the mailing list for patch reviews. I also
find Phabricator to be helpful (but it is not mandatory).

Some comments:
The patch would obviously break tests, so test updates are needed. I would
prefer to see if some tests are salvageable by modifying them to use the
new syntax (and then leaving them disabled for now).
The error message at line 132 of the patch still refers to "concept" as a
specifier.
This particular error message is also more likely to be orphaned than not
depending on how the parsing is implemented.

template <typename T>
inline concept C = true;
// ^
// error: expected unqualified-id

template <typename T>
concept constexpr C = true;
// ^
// error: expected unqualified-id

Agreed, I’ll post a patch with fixed tests and the diagnostic removed soon.

Richard - I heard from Andrew Sutton that constrained non-template functions had been cut out of the working draft when concepts was voted in because of name mangling issues - are they still left out? If so, was the trailing requires-clause cut out as well?
Anyway I’ve noticed another problem/defect with constrained non-template functions as described in P0734R0, discussed here: https://groups.google.com/a/isocpp.org/forum/#!topic/std-discussion/CJAmcnFI86o (Andrew also agreed that this probably should be fixed in the way I suggested)

Agreed, I'll post a patch with fixed tests and the diagnostic removed soon.

Richard - I heard from Andrew Sutton that constrained non-template
functions had been cut out of the working draft when concepts was voted in
because of name mangling issues - are they still left out? If so, was the
trailing requires-clause cut out as well?
Anyway I've noticed another problem/defect with constrained non-template
functions as described in P0734R0, discussed here: https://groups.google.
com/a/isocpp.org/forum/#!topic/std-discussion/CJAmcnFI86o (Andrew also
agreed that this probably should be fixed in the way I suggested)

Yes, previous discussions on the issue you describe led to the same
conclusion. There are still questions over what exactly is used to
distinguish requires-clauses that are "different" without template
dependent constructs. The constraint expression really just evaluates to a
bool value, and all cases evaluating to "true" could be considered
equivalent. [basic.link]/9 in N4700 is silent to the point of being wrong
here, but I do not think we have an agreement on what the right words
should look like.

Hi Saar,

I submitted the work I did for review.
https://reviews.llvm.org/D40381https://reviews.llvm.org/D40381

Hi Saar,

I submitted the work I did for review.

https://reviews.llvm.org/D40380

https://reviews.llvm.org/D40381

I broke it into two parts. The removing old code part is pretty much the same as yours.

Hi guys,

I just wanted to say thanks for taking this on. I really just haven’t had time to get back to this work. Appreciate it!

Awesome! I’ll check it out later today