Assignable concept looks wrong

[ericniebler]

Looks like it's half-way between an old-style object concept and a less semantically meaningful Swappable-like concept. Which should it be? (I'll flesh this issue out later.)

For Assignable we have:

template <class T, class U>
concept bool Assignable() {
  return Common<T, U>() && requires(T&& t, U&& u) {
    { std::forward<T>(t) = std::forward<U>(u) } -> Same<T&>;
  };
}

1. Let t be an lvalue of type T,

The "Let t be an lvalue of type T" is at odds with the concept definition. It needs the lvalue/rvalue dance.

Also, the application of == to entities whose types aren't constrained to satisfy EqualityComparable is meaningless; uu == v and t == uu should use "is equal to."

Proposed Resolution:

Adopt P0547R1.

[ericniebler]

OK, coming back to this. For Assignable we have:

template <class T, class U>
concept bool Assignable() {
  return Common<T, U>() && requires(T&& t, U&& u) {
    { std::forward<T>(t) = std::forward<U>(u) } -> Same<T&>;
  };
}

1. Let t be an lvalue of type T,

The "Let t be an lvalue of type T" is at odds with the concept definition. It needs the lvalue/rvalue dance.

[CaseyCarter]

Also, the application of == to entities whose types aren't constrained to satisfy EqualityComparable is meaningless; uu == v and t == uu should use "is equal to."

The poor wording for R, U, and v could likely be improved with the "Let E be an expression such that decltype(E) is T" idiom from Writable.

[CaseyCarter]

Proposed Resolution: SUPERSEDED

Replace the [concepts.lib.corelang.assignable]/1 with:

1 Let t be a glvalue which refers to an object o such that decltype(t) is T, and u an expression such that decltype(u) is U. Let u2 be a distinct object that is equal to u. Then Assignable<T, U>() is satisfied if and only if

(1.1) — std::addressof(t = u) == std::addressof(o).

(1.2) — After evaluating t = u:

(1.2.1) — t is equal to u2.

(1.2.2) — If u is a non-const xvalue, the resulting state of the object to which it refers is unspecified. [Note: the object must still meet the requirements of the library component that is using it. The operations listed in those requirements must work as specified. —end note ]

(1.2.3) — Otherwise, if u is a glvalue, the object to which it refers is not modified.

[ericniebler]

What does "an object o" mean here? std::addressof(o) only compiles if o is an lvalue.

[ericniebler]

What if T is a non-reference type? Then t cannot be a glvalue such that decltype(t) is T.

[CaseyCarter]

What does "an object o" mean here? std::addressof(o) only compiles if o is an lvalue.

The intent is that o is an lvalue that refers to the same object as t. (Since we can't take the address of t.)

What if T is a non-reference type?

decltype(t) for a glvalue t is always a reference type; Assignable does not admit non-reference types for T. This obviously needs to be made more explicit.

[ericniebler]

If u is a non-const xvalue, the resulting state of the object to which it refers is unspecified.

What if u is a prvalue? Same thing, right? Or does it not matter to say what the resulting state of a prvalue is since there is no way to observe it?

Assignable does not admit non-reference types for T

So proxy references cannot satisfy Assignable? That seems problematic.

[CaseyCarter]

So proxy references cannot satisfy Assignable? That seems problematic.

#150 (comment)

We've avoided characterizing proxy references in the design by placing requirements on expressions involving proxy iterators instead. We have iter_swap(i, j) so we need not make swap(*i, *j) work properly. We have IndirectlyCopyable<In, Out> to place requirements on *o = *i so that Assignable<reference_t<Out>, reference_t<In>> need not do so. Assigning to the reference vs. assigning to the referent is a giant can of worms that we do not want to open if we can help it.

[ericniebler]

... and Writable is not defined in terms of Assignable. <nod>

[CaseyCarter]

... and Writable is not defined in terms of Assignable.

Almost necessarily so: if we could define Writable in terms of Assignable, I don't think we would need both.

[ericniebler]

What about this from above?

If u is a non-const xvalue, the resulting state of the object to which it refers is unspecified.

What if u is a prvalue? Same thing, right? Or does it not matter to say what the resulting state of a prvalue is since there is no way to observe it?

[CaseyCarter]

What if u is a prvalue? Same thing, right? Or does it not matter to say what the resulting state of a prvalue is since there is no way to observe it?

If it's a prvalue, it doesn't refer to an object, and we can't reasonably talk about mutation of a non-object.
(Yes, a = b could hypothetically modify some other object somewhere but either (1) that object is subject to the value stability requirements in [concepts.lib.general.equality]/3 and we'll notice if we observe it later, or (2) it isn't and we don't care what happens to it.)

[CaseyCarter]

If it's a prvalue

But the fact that you asked for clarification tells me that we need a note.

[ericniebler]

Assigning to the reference vs. assigning to the referent is a giant can of worms that we do not want to open if we can help it.

Tell me more. Because the more I think about #226, the more it seems to me that we need some sort of characterization of "reference-like" types. What problems do you see?

[ericniebler]

Characterizing reference-like types:

Strawman Approach 1:

"A techterm{reference-like} type is a class type such that objects of that type have values that are comprised, in whole or in part, from parts outside the object's storage [or a reference to such?]."

Strawman Approach 2:

"A techterm{reference-like} type is a class type whose copy constructor is not equality preserving because (copies do not have independent values|values may not be stable) [, or a reference to such class type?]."

Or something. We may also need to say something about an object's "value", since it doesn't seem to be characterized anywhere. Loosely in this context it should mean any property of the object that may be observed, either directly or indirectly.

We would want to give examples of reference-like types, such as reference_wrapper, the tuple returned by std::tie, and vector<bool>::reference.

OK, rip it apart.

[ericniebler]

OK, rip it apart.

Ping. @CaseyCarter?

[CaseyCarter]

Recall that the original problem we're trying to solve here is how to characterize when the assignment expression in Writable<I, T> may modify the value denoted by its RHS. The current formulation of Writable implicitly assumes that the "value denoted by" the RHS is a value of type uncvref_t<T>, and explicitly states that the "value" may only be modified when T is an rvalue reference type, i.e., when the RHS of the assignment expression is an xvalue of type uncvref_t<T>.

Proxy references actually break that definition in two ways:

1. A proxy reference may be "xvalue-like" in that the denoted value may be changed when it appears on the RHS of an assignment without actually being an actual xvalue,
2. The mapping from T (the decltype of the RHS expression) to the type of the "denoted value" is not so simple as uncvref_t<T>. I suspect this will require explicit specification just as does value type for iterators.

The proposal I made in the other thread (add an is_xvalue_ish trait) seems to be the simplest/weakest solution to only #1; it doesn't even admit the existence of the second problem.

The problem this thread seems to be about is how to devise a complete characterization of proxy references so we can describe their behavior in equality preserving expressions. Notably, a solution to this problem will almost trivially provide a solution to the Writable issues. I suspect this is not an easy problem to solve and would be surprised if we could do so before moving P0022 in plenary.

I don't see how either of the two "Strawman approaches" presented herein get us closer to solutions to any of the above problems. I don't see how approach #1 differs from a non-reference-like type: we don't care where things are stored, the only "values" we care about are the results of evaluating equality-preserving expressions. Approach #2 seems to say "reference-like types are class types that don't participate in the semantics of equality-preserving expressions." which is fine, but doesn't tell me how I can reason about these things.

My intuition is that the way to break these problems open is to somehow hijack the mapping from "names" to "values" in equality preserving expressions. Given the definitions:

int i = 42;
int &j = i;

i + i, 2 * i, and i = 13 are equivalent expressions to j + j, 2 * j and j = 13. Subexpression j is a proxy for subexpression i in those expressions: replacing i with j changes neither the value of the expression, nor the resulting value of any objects involved.

Similarly:

int i = 42;
reference_wrapper<int> k = i;

i + i and 2 * i are equivalent expressions to k + k and 2 * k. Subexpression k is a proxy for subexpression i in those expressions: replacing i with k changes neither the value of the expression, nor the resulting value of any objects involved. (Notably k is a proxy for i in far fewer expressions than is j; i = 13 and &i are obvious examples.)

We've never really locked down what the "operands" of an expression are. I propose that we should do so, and in such way that in:

int i = 42;
reference_wrapper<int> k = i;
k + k;
k.get() + k.get();

both expressions k + k and k.get() + k.get() make sense, despite that fact that the mapping from names to "values" is different in the two expressions. And despite the fact that the mapping itself can change:

k + k;      // #1
int j = 11;
k = j;
k + k;      // #2

#1 and #2 appear to be equivalent expressions, but we cannot expect them to preserve equality since the name k denotes a different value in #1 than in #2. Not different because the value was mutated, but different because the mapping from name to value has changed.

[ericniebler]

There is a related issue wrt proxy references in that none of the transformation metafunctions (add/remove reference, add/remove const) works for them. If we had a generic way to "reach in" to a proxy reference and do these kinds of transformations, then we have a powerful mechanism that would be generally useful. It could also solve the problems you note above: we reach in and strip top-level cv and ref qualifiers to get the "value type", and then require that the proxy reference is convertible to the value.

[ericniebler]

And to finish the thought, I propose:

template <class T, template <class> class F>
struct transform_proxy
 : transform_proxy<remove_cv_t<T>, F>
{};

template <class T, template <class> class F>
  requires Same<T, remove_cv_t<T>>()
struct transform_proxy<T, F>
{
  using not_specialized = unspecified;
};

template <class T, template <class> class F>
using transform_proxy_t = typename transform_proxy<T,F>::type;

template <class T>
struct is_proxy : true_type {};
template <class T>
  requires requires {typename transform_proxy_t<T, remove_reference_t>::not_specialized;}
struct is_proxy : false_type {};

template <class T>
struct is_reference_like : disjunction<is_reference<T>, is_proxy<T>>
{};

By default, it is specialized for types such as reference_wrapper, pairs and tuples of references as follows:

template <class T, template <class> class F>
struct transform_proxy< reference_wrapper<T>, F>
{
  using type = reference_wrapper< F<T> >;
};
template <class T>
struct transform_proxy< reference_wrapper<T>, remove_reference_t >
{
  using type = T;
};

Then we can infer the value type with remove_cv<transform_proxy_t<T, remove_reference_t>>.

We can handle the mapping of name to value by coercing a proxy to the value type. But can we do this without forcing a copy?

EDIT: It's not hard to poke holes in this, but perhaps there is the germ of an idea here.

EDIT 2: All this garbage is what I hoped to avoid with iter_move and iter_swap. Ugh. Still hoping to find a better way.

[ericniebler]

Proxies aside, can we get to some suggested wording that is better than what we have? Is this comment good enough?

[CaseyCarter]

From the Issaquah review: "Assignable should require a non-const lvalue LHS." Sentiment in the room was that if we are not yet ready to define semantics for assigning to something that isn't a modifiable lvalue we should restrict the domain of the concept instead of only applying semantics to the restricted domain.

#229 (comment) is better than what we have, but still needs more work.

[CaseyCarter]

Proxies aside, can we get to some suggested wording that is better than what we have?

And FWIW, I agree that we should fix the wording to support the current intended design, close this, and move discussion about making Assignable work with proxies to #226. (I haven't given up on solving the problem, but I think we should fix Assignable for the PDTS and #226 is not going to happen in time.)

[ericniebler]

It's too late for PDTS. We can't make changes without LWG review. Sorry, I missed the comment about LWG requesting changes. OK great.

[CaseyCarter]

Proposed Resolution:

Change [concepts.lib.corelang.assignable] as follows:

template <class T, class U>
concept bool Assignable() {
- return CommonReference<const T&, const U&>() && requires(T&& t, U&& u) {
-   { std::forward<T>(t) = std::forward<U>(u) } -> Same<T&>;
- };
+ return std::is_lvalue_reference<T>::value &&
+   Same<std::remove_reference_t<T>, std::remove_cv_t<std::remove_reference_t<T>>>() &&
+   CommonReference<T, const U&>() &&
+   requires(T t, U&& u) {
+     { t = std::forward<U>(u); } -> Same<T>;
+   };
}

-1 Let t be an lvalue of type T, and R be the type remove_reference_t<U>. If U is an
-  lvalue reference type, let v be an lvalue of type R; otherwise, let v be an rvalue
-  of type R. Let uu be a distinct object of type R such that uu is equal to v.
+1 Let `t` be an lvalue which refers to an object `o` such that `decltype((t))` is `T`,
+  and `u` an expression such that `decltype((u))` is `U`. Let `u2` be a distinct object that is
+  equal to `u`.
   Then Assignable<T, U>() is satisfied if and only if

-(1.1) — std::addressof(t = v) == std::addressof(t).
+(1.1) — std::addressof(t = u) == std::addressof(o).

-(1.2) — After evaluating t = v:
+(1.2) — After evaluating t = u:

-(1.2.1) — t is equal to uu.
+(1.2.1) — t is equal to u2.

-(1.2.2) — If v is a non-const rvalue, its resulting state is unspecified. [Note: v must still
-          meet the requirements of the library component that is using it. The operations listed
-          in those requirements must work as specified. —end note ]
+(1.2.2) — If u is a non-const xvalue, the resulting state of the object to which it refers is
+          unspecified. [ Note: the object must still meet the requirements of the library
+          component that is using it. The operations listed in those requirements must work as
+          specified. —end note ]

-(1.2.3) — Otherwise, v is not modified.
+(1.2.3) — Otherwise, if u is a glvalue, the object to which it refers is not modified.

[cjdb]

Should this program be ill-formed (it currently is as of CaseyCarter/cmcstl2@6ec9162)?

template <class T, class U>
requires
   std::experimental::ranges::Assignable<T, U>()
void foo(T, U) {}

int main()
{
   foo(std::pair<int, int>{}, std::pair<int, double>{});
}

[ericniebler]

Should this program be ill-formed

Yes. It's testing rvalues for assignment. You probably want to change this to:

template <class T, class U>
requires
   std::experimental::ranges::Assignable<T&, U>()
void foo(T t, U u) { }

[cjdb]

std::experimental::ranges::Assignable<T&, U>()

Whoops, that's exactly what I meant! Even so, it's not assignable on account of CommonReference being ill-formed:

cmcstl2/include/stl2/type_traits.hpp:187:15: note: within ‘template<class T, class U> concept bool std::experimental::ranges::v1::CommonReference() [with T = std::pair<int, int>&; U = const std::pair<int, double>&]’
  concept bool CommonReference() {
               ^~~~~~~~~~~~~~~
cmcstl2/include/stl2/type_traits.hpp:187:15: note: ‘std::experimental::ranges::v1::models::CommonReference’ evaluated to false

[ericniebler]

The CommonReference constraint isn't new. But we should probably propose specializing common_type and basic_common_reference for the std:: utilities like pair, tuple, optional, and possibly others.

[CaseyCarter]

Assignable<std::pair<int, int>&, std::pair<int, double>>() is not satisfied for the same reason that Assignable<int&, double>() is not satisfied: the assignment invokes a lossy conversion, and can't satisfy the "after the assignment, the two things are equal" post-condition.

[CaseyCarter]

the assignment invokes a lossy conversion

Unless restricted to the common domain of values representable by both types, of course.

[ericniebler]

I'm beginning to question whether the CommonReference requirement on Assignable is correct. We don't enforce CommonReference<const T&, const U&> from Constructible<T, U>, so is Assignable right to do that? If the answer is "equational reasoning", then why does that argument not apply to construction?

[CaseyCarter]

If the answer is "equational reasoning", then why does that argument not apply to construction?

For Assignable, given a equal to b, the postcondition of c = a is that c is equal to b. Recall that we deliberately chose that strong semantic to support the needs of the default swap implementation.

For Constructible, we only require that T{u} somehow produces a T. The expression isn't required to be equality preserving, so each evaluation of T{u} might be different from every other T{u}. It's a very weak, general sort of semantic.

[CaseyCarter]

Recall that we deliberately chose that strong semantic to support the needs of the default swap implementation.

...and the assignment operations of Copyable and Movable, which need the result of assignment to be "equal to" the original value, just as is the case for Copy/MoveConstructible.

[ericniebler]

My point is that this:

Case 1

T t(a);

should be the same as:

Case 2

T t;
t = a;

The concept we have to constrain case 2 enforces equational reasoning, but we don't have any such guarantee for case 1. I think it's fishy.

[CaseyCarter]

I think it's fishy.

There are too many types in C++ for which the value of the constructed object is not a function of the values of the constructor parameters. Timers are the first and most obvious example. We could not specify the standard library without a "weak" Constructible concept of some kind. On the opposite side of the coin, the components specified in the TS only need a "strong" Constructible concept for the copy and move cases. For now, we have the concepts to describe the semantics we need and not the semantics we don't.