Readable types with prvalue reference types erroneously model Writable

[ericniebler]

Consider:

struct MakeString
{
	using value_type = std::string;
	std::string operator*() const
	{
		return std::string();
	}
};

static_assert(!Writable<MakeString, std::string>()); // FAILS

This is a huge usability problem, since it permits users to, e.g., pass a range to sort that is not, in fact, sortable. The Ranges TS inherited this problem from the Palo Alto Report (N3351), which also has this bug. Fixing this will be tricky easy :-) without messing up proxy iterators.

EDIT: See ericniebler/range-v3#573

Resolution Discussion:

One fix would be to require that *o return a true reference, but that breaks when *o returns a proxy reference. The trick is in distinguishing between a prvalue that is a proxy from a prvalue that is just a value. The trick lies in recognizing that a proxy always represents a (logical, if not physical) indirection. As such, adding a const to the proxy should not effect the mutability of the thing being proxied. Further, if decltype(*o) is a true reference, then adding const to it has no effect, which also does not effect the mutability. So the fix is to add const to decltype(*o), const_cast *o to that, and then test for writability.

Proposed Resolution

Accept the wording in P0547R1 (duplicated below).

(Includes the resolution for #387.)

Change the definition of Writable ([iterators.writable]) as follows:

 template <class Out, class T>
 concept bool Writable() {
-  return requires(Out& o, T&& t) {
+  return requires(Out&& o, T&& t) {
     *o = std::forward<T>(t); // not required to be equality preserving
+    *std::forward<Out>(o) = std::forward<T>(t); // not required to be equality preserving
+   const_cast<const reference_t<Out>&&>(*o) =
+      std::forward<T>(t); // not required to be equality preserving
+   const_cast<const reference_t<Out>&&>(*std::forward<Out>(o)) =
+      std::forward<T>(t); // not required to be equality preserving
   };
 }

In [iterators.writable] paragraphs 2.1 and 3, replace "the assignment" with "either above assignment":

 (2.1) — If Readable<Out>() && Same<value_type_t<Out>, decay_t<T>>() is satisfied, then *o after
-        the
+        any above
         assignment is equal to the value of E before the assignment.
    3    After evaluating
-        the
+        any above
         assignment expression, o is not required to be dereferenceable.

[ericniebler]

Solution 1

A partial fix is to change iter_swap to require real references when the reference types are not themselves swappable, as follows:

 (1.3) - Otherwise, if the types T1 and T2 of E1 and E2
       satisfy IndirectlyMovableStorable<T1, T2>() &&
       IndirectlyMovableStorable<T2, T1>(),
+      and if reference_t<T1> and reference_t<T2>
+      are lvalue reference types,
       (void)(*E1 = ranges::iter_exchange(E2, E1)), except
       that E1 is evaluated only once.

That makes iterators that return things by value not satisfy IndirectlySwappable by default, which causes them to no longer satisfy Permutable.

One could argue that with the suggested change, (1.3) above is no longer particularly useful, so an alternative approach would be to simply delete that para.

Either way, it would no longer be enough to hook iter_move for proxy iterators; users would have to hook both iter_move and iter_swap. That's a small price to pay, IMO.

However IndirectlyMovable<MakeString, MakeString> and IndirectlyCopyable<MakeString, MakeString> is still satisfied, so "fixing" IndirectlySwappable this way is only a partial fix.

Solution 2

Change Writable as follows:

template <class Out, class T>
concept bool Writable() {
  return requires(Out& o, T&& t) {
    *o = std::forward<T>(t); // not required to be equality preserving
+   const_cast<const reference_t<Out>&&>(*o) =
+      std::forward<T>(t); // not required to be equality preserving
  };
}

The reasoning here is that when *o is a glvalue, adding const has no effect. When *o is a proxy prvalue, adding a const shouldn't matter since you're const-ifying the proxy. We lose writability of types like optional, but frankly I don't care.

This would also lose the ability to use std::pairs of references as a proxy reference type, since it doesn't have a const-qualified assignment operator. But pairs of references have always seemed like a hack, and we could add a better type to use as a collection of references. Maybe a generalization of reference_wrapper.

Obviously, we would require that the two valid expressions of Writable have the same effect.

[ericniebler]

Solution 3

Push for a language change where the compiler-generated copy/move assignment operator is (lvalue) reference qualified, changed all std:: library types to similarly qualify their copy/move assignment operators, and get the entire industry to follow suit. Obviously a non-starter, but including it here for the sake of completeness.

[CaseyCarter]

I think you're emphasizing the symptom over the actual problem, which is that prvalues of non-class types often lie about being mutable. We can paper over the symptoms of that problem we've noticed in the Ranges TS, but that won't make the problem go away.

As such, I'm not certain this is the right answer, but I agree it is the right now answer. It addresses the usability problem for users of the TS.

[ericniebler]

I think you're emphasizing the symptom over the actual problem, which is that prvalues of non-class types often lie about being mutable.

Prvalues of class types often lie about being mutable, yes. And I agree that that is the root cause of the problem. I can make that point more strenuously if you think it would help. I don't. STL2 has N decades of legacy code to contend with, where N >= 3. It simply must play well in that world.

As such, I'm not certain this is the right answer, but I agree it is the right now answer.

For extremely large values of right now. ;-)

[CaseyCarter]

Prvalues of class types

Way to go, me - write the exact opposite of the point you're trying to make.

For extremely large values of right now. ;-)

Agreed, but 20 or 25 years from now it would be nice if assignment operators were properly &-constrained and our children's children didn't have this problem. We need both the short-term fix to get working code and the long term plan to fix the root problem. (Albeit not in the TS.)

[timsong-cpp]

Data point: neither std::vector<bool>::reference nor std::bitset::reference has a const-qualified assignment operator.

[ericniebler]

Data point: neither std::vector<bool>::reference nor std::bitset::reference has a const-qualified assignment operator.

But not for any valid technical reason. They too represent an indirection. Assigning through these types doesn't change the bits of the proxy.

Besides, I suspect these containers have iterators that fail to model Writable for other reasons besides. They need tweaks to be brought in to STL2.

[ericniebler]

I think you're emphasizing the symptom over the actual problem

... and c'mon. You have to admit that this is a very nice hack. :-)

[timsong-cpp]

Also worth considering, I think, is the interaction between a const-qualified assignment operator and [res.on.data.races]/3. With the current direction, that wording will need to be weakened somehow sooner or later.

[CaseyCarter]

[res.on.data.races]/3

The standard needs to properly define what "non-const" arguments means. E.g., can these functions:

namespace std {
  void f1(int* p);
  void f2(int* const p);
}

modify p's referent? The argument is the same for proxy references or - the most recent example I recall from LWG - coroutine handles. Operations that are explicitly specified to modify the target of a handle/iterator/pointer but do not modify the handle/iterator/pointer should operate on const handle/iterator/pointers.

[CaseyCarter]

Incorporating the PR of #387, and correcting for the fact that "equivalent" in "The second expression in the above requires clause is equivalent to the first" has no well-defined meaning:

Change the definition of Writable ([iterators.writable]) as follows:

 template <class Out, class T>
 concept bool Writable() {
-  return requires(Out& o, T&& t) {
+  return requires(Out&& o, T&& t) {
     *o = std::forward<T>(t); // not required to be equality preserving
+    *std::forward<Out>(o) = std::forward<T>(t); // not required to be equality preserving
+   const_cast<const reference_t<Out>&&>(*o) =
+      std::forward<T>(t); // not required to be equality preserving
+   const_cast<const reference_t<Out>&&>(*std::forward<Out>(o)) =
+      std::forward<T>(t); // not required to be equality preserving
   };
 }

In [iterators.writable] paragraphs 2.1 and 3, replace "the assignment" with "either above assignment":

 (2.1) — If Readable<Out>() && Same<value_type_t<Out>, decay_t<T>>() is satisfied, then *o after
-        the
+        either above
         assignment is equal to the value of E before the assignment.
    3    After evaluating
-        the
+        either above
         assignment expression, o is not required to be dereferenceable.

[ericniebler]

"Either" is for denoting one of two alternatives. There are four assignments in the proposed resolution, so "either above assignment expression" is wrong. Maybe "after any of the above assignment expressions..."?