Argument deduction constraints are specified incorrectly

[ericniebler]

See #155 for detailed discussion, but basically we've been operating under the faulty assumption that the following:

requires(const T& t) {  {t} -> Same<const T&>; }

was trivially satisfied. It is not. Argument deduction constraints are handled as if the placeholder were made the argument type of an invented function f, like void f(Same<const T&>), and then a call were made like f(t). That causes the type of t to decay.

This should instead be written as:

requires(const T& t) {  {t} -> Same<const T&>&&; }

That prevents argument decay from happening, which recovers the value category information.

We need to review and amend all the definitions and uses of concepts in the ranges ts.

(In our defense, this slipped through because early concepts implementations didn't do argument deduction constraints, so we invented a workaround, and the workaround was buggy because we didn't understand the model.)

Proposed Resolution:

Update section "Concept Assignable" ([concepts.lib.corelang.assignable]) and "Concept Destructible" ([concepts.lib.object.destructible]) as specified in P0547R1.

Update sections "Concept Boolean" [concepts.lib.compare.boolean]), "Concept EqualityComparable" ([concepts.lib.compare.equalitycomparable]), "Concept StrictTotallyOrdered" ([concepts.lib.compare.stricttotallyordered]) as specified in #155.

Update section "Concept Readable" ([iterators.readable]) as follows (also fixes #339):

template <class I>
concept bool Readable() {
- return Movable<I>() && DefaultConstructible<I>() &&
-   requires(const I& i) {
+ return requires {
    typename value_type_t<I>;
    typename reference_t<I>;
    typename rvalue_reference_t<I>;
-   { *i } -> Same<reference_t<I>>;
-   { ranges::iter_move(i) } -> Same<rvalue_reference_t<I>>;
  } &&
  CommonReference<reference_t<I>, value_type_t<I>&>() &&
  CommonReference<reference_t<I>, rvalue_reference_t<I>>() &&
  CommonReference<rvalue_reference_t<I>, const value_type_t<I>&>();
}

Change section "Concept WeaklyIncrementable" ([iterators.weaklyincrementable]) as follows:

template <class I>
concept bool WeaklyIncrementable() {
  return Semiregular<I>() &&
  requires(I i) {
    typename difference_type_t<I>;
    requires SignedIntegral<difference_type_t<I>>();
-   { ++i } -> Same<I&>; // not required to be equality preserving
+   { ++i } -> Same<I>&; // not required to be equality preserving
    i++; // not required to be equality preserving
  };
}

Change section "Concept Incrementable" ([iterators.incrementable]) as follows:

template <class I>
concept bool Incrementable() {
  return Regular<I>() &&
    WeaklyIncrementable<I>() &&
    requires(I i) {
-     { i++ } -> Same<I>; // not required to be equality preserving
+     { i++ } -> Same<I>&&; // not required to be equality preserving
    };
}

Change section "Concept SizedSentinel" ([iterators.sizedsentinel]) as follows:

template <class S, class I>
concept bool SizedSentinel() {
  return Sentinel<S, I>() &&
    !disable_sized_sentinel<remove_cv_t<S>, remove_cv_t<I>> &&
    requires(const I& i, const S& s) {
-     { s - i } -> Same<difference_type_t<I>>;
-     { i - s } -> Same<difference_type_t<I>>;
+     { s - i } -> Same<difference_type_t<I>>&&;
+     { i - s } -> Same<difference_type_t<I>>&&;
    };
}

Take the definition of concept InputIterator ([iterators.input]) from P0541.

Change section "Concept BidirectionalIterator" ([iterators.bidirectional]) as follows:

template <class I>
concept bool BidirectionalIterator() {
  return ForwardIterator<I>() &&
    DerivedFrom<iterator_category_t<I>, bidirectional_iterator_tag>() &&
    requires(I i) {
-     { --i } -> Same<I&>;
-     { i-- } -> Same<I>;
+     { --i } -> Same<I>&;
+     { i-- } -> Same<I>&&;
    };
}

Change section "Concept RandomAccessIterator" ([iterators.random.access]) as follows:

template <class I>
concept bool RandomAccessIterator() {
  return BidirectionalIterator<I>() &&
    DerivedFrom<iterator_category_t<I>, random_access_iterator_tag>() &&
    StrictTotallyOrdered<I>() &&
    SizedSentinel<I, I>() &&
    requires(I i, const I j, const difference_type_t<I> n) {
-     { i += n } -> Same<I&>;
-     { j + n } -> Same<I>;
-     { n + j } -> Same<I>;
-     { i -= n } -> Same<I&>;
-     { j - n } -> Same<I>;
-     { j[n] } -> Same<reference_t<I>>;
+     { i += n } -> Same<I>&;
+     { j + n } -> Same<I>&&;
+     { n + j } -> Same<I>&&;
+     { i -= n } -> Same<I>&;
+     { j - n } -> Same<I>&&;
+     j[n];
+     requires Same<decltype(j[n]), reference_t<I>>();
    };
}

Change section "Concept UniformRandomNumberGenerator" ([rand.req.urng]) as follows:

template <class G>
concept bool UniformRandomNumberGenerator() {
- return requires(G g) {
-   { g() } -> UnsignedIntegral; // not required to be equality preserving
-   { G::min() } -> Same<result_of_t<G&()>>;
-   { G::max() } -> Same<result_of_t<G&()>>;
+ return Invocable<G&>() &&
+   UnsignedIntegral<result_of_t<G&()>>() &&
+   requires {
+     { G::min() } -> Same<result_of_t<G&()>>&&;
+     { G::max() } -> Same<result_of_t<G&()>>&&;
    };
}

[ericniebler]

This proposed resolution is ready for its close-up, @CaseyCarter.

[timsong-cpp]

Unless I missed something, { ranges::size(t) } -> Integral&&; allows ranges::size(t) to return int&& but not int&. I'm not sure why we are doing that. Surely these should be both disallowed or both allowed?

[ericniebler]

That's not wrong, but does generic code care? I consider this better than size(r); requires Integral<decltype(size(r))>();

[timsong-cpp]

If generic code doesn't care about int&&, why do we want to ban int&? That is, what harm does the decay do here?

[CaseyCarter]

Generic code cares about the rvalue vs. lvalue distinction, but we haven't yet found an example usage where reasonable code cares about prvalue vs. xvalue. That said, I'm nervous that this is something that requires thought and investigation when we are honestly doing this to paper over the fact that Concepts has no good syntax for constraining the type and value category of an expression.

I think it may be safer in the short run to replace { E } -> C; with requires C<decltype(E)>(); when we want a true type-and-value-category constraint. It's ugly, but it's obviously correct even to those that don't know Concepts syntax backwards and forwards.

EDIT: And if its ugliness encourages the development of a prettier syntax for type-and-value-category constraints, so much the better.

EDIT 2: We cannot blindly replace { E } -> C; with requires C<decltype(E)>();; since the second is not an expression constraint, it doesn't trigger the "implicit expression variant" wording in [concepts.lib.general.equality]/6. We need to either blindly replace with E; requires C<decltype(E)>(); or update the implicit expression variant wording.

[timsong-cpp]

Generic code cares about the rvalue vs. lvalue distinction, but we haven't yet found an example usage where reasonable code cares about prvalue vs. xvalue.

I have little doubt that there are cases where generic code cares about rvalue vs. lvalue. I'm just somewhat doubtful that size (or URNG, for that matter) is one of such cases.

[CaseyCarter]

For size, at least, the question is moot: the result of calling (|c|r|cr)begin, (|c|r|cr)end, size, empty, and (|c)data is always a prvalue.

Edit: and the result of calling size always satisfies Integral. I would simply remove all changes to SizedRange from the PR.

[CaseyCarter]

The proposed changes to Readable are wrong. The affected requirements are there to ensure that reference_t<const I> (resp. rvalue_reference_t<const I>) is valid and has the same type as reference_t<I> (resp rvalue_reference_t<const I>). (Note that reference_t<T> and rvalue_reference_t<T> already require { *t } -> auto&& and { iter_move(t) } -> auto&&.) I suggest instead:

 template <class I>
 concept bool Readable() {
   return Movable<I>() && DefaultConstructible<I>() &&
-    requires(const I& i) {
-      typename value_type_t<I>;
-      typename reference_t<I>;
-      typename rvalue_reference_t<I>;
-      { *i } -> Same<reference_t<I>>;
-      { ranges::iter_move(i) } -> Same<rvalue_reference_t<I>>;
-    } &&
+    Same<reference_t<const I>, reference_t<I>>() &&
+    Same<rvalue_reference_t<const I>, rvalue_reference_t<I>>() &&
     CommonReference<reference_t<I>, value_type_t<I>&>() &&
     CommonReference<reference_t<I>, rvalue_reference_t<I>>() &&
     CommonReference<rvalue_reference_t<I>, const value_type_t<I>&>();
}

Edit: Broken type-and-value-category constraints or not, I think this is an improvement to Readable.

Edit again: Oh, and remove the editorial note "(The Same constraints above were unnecessary because they are trivially true if the associated types are well-formed.)" since it's wrong ;)

[CaseyCarter]

I agree with @timsong-cpp about URNG, as well: If we don't care whether these functions return a prvalue or xvalue, we shouldn't care if they return an lvalue. The type is required to be an unsigned integral type, so object semantics are of no consequence here.

(This is not the same as the pointer case we argued earlier, there are no types with stupid decay conversions to unsigned integer types.)