Make cloned values indistinguishable

[Stebalien]

Define "Returns a copy of the value" to mean a == b -> a == b.clone().

---

Original unworkable proposal (see discussion below):

Currently, clone explicitly doesn't guarantee that the following are always indistinguishable:

let a = f();
let b = g();
let c = b.clone();
h(a, b);

let a = f();
let b = g();
let c = b.clone();
h(a, c);

This is unfortunate. However, the trait does say that Clone::clone() "Returns a copy of the value." which could imply indistinguishably (i.e., a copy of a value is indistinguishable from the original). It would be nice to make this explicit (so that, e.g., a == b implies a == b.clone()).

/cc #1203

[arielb1]

That's because it does not. For example, it is totally fine to put an interior address into some data structure.

[Stebalien]

That's because it does not. For example, it is totally fine to put an interior address into some data structure.

Yes but it shouldn't be exposed. That's why I said indistinguishable, not identical. That is, if I flip a fair coin and give you either a or a.clone(), you shouldn't be able to guess which one I gave you (ignoring timing, power, unsafe, etc.).

[durka]

cc #1521

[oli-obk]

in case of Rc, equality stands, because it is forwarded to the inner type, but cloning is exposed, because try_unwrap will fail after a clone.

So you can only guarantee that it's not exposed which one is the original and which one is the clone, but only if you always clone before you try to figure out if a value is a clone.

[Stebalien]

@oli-obk that's why I did it that way in the example (I wasn't thinking about Rc but Clone side effects in general). However, I somehow didn't notice that this would make this restriction useless in solving the linked issue. Regardless, I still think a restriction like this would be useful.

[oli-obk]

It's very hard to enforce this rule. You'd need to ensure that clone doesn't modify any fields that are accessible outside the module. I'll evaluate if it's possible to write a lint for that.

[ticki]

@oli-obk, I don't think @Stebalien propose to enforce it, but rather add a "rule", like the hash rule:

If you are also implementing Eq, there is an additional property that is important:

k1 == k2 -> hash(k1) == hash(k2)

In other words, if two keys are equal, their hashes should also be equal. HashMap and HashSet both rely on this behavior.

So just state that this is the expected behavior of clone.

[Stebalien]

@oli-obk exactly what @ticki said. Basically, precisely define that "returns a copy" means that, after cloning, the clone and the original are indistinguishable (for some reasonable definition of indistinguishable that doesn't involve the physical world).

[ticki]

I think a rule like:

a == b → a == b.clone()

[durka]

@ticki in other words, tying Clone to PartialEq?

[Stebalien]

@ticki that would also be nice but is slightly different and neither implies nor is implied by my rule. However, it would solve my problem with #1203 because a == b.clone() → hash(a) == hash(b.clone()) which means that hash(b) == hash(b.clone()).

[durka]

@Stebalien what is your rule? The "reasonable definition of indistinguishable" needs to be decided.

[Stebalien]

@durka My original thinking was "indistinguishable using the provided API". That is, you can't time things, read raw memory, use unsafe shenanigans, etc. However, you'd also have to ban looking at locations of objects in memory (casting pointers to ints) so I'm no longer sure this proposal is workable.

[ticki]

They aren't indistiguishable in the current API. See Rc for example.

[Stebalien]

@ticki see #1544 (comment). That's why my rule doesn't imply your rule.

[bluss]

Vec, String, VecDeque are examples of collections that are distinguishable after cloning (the new clone picks a capacity that fits exactly). A HashMap interestingly enough seems to have identical clones.

Using this rule can only increase the cost of cloning a Vec.

The cloned vec is indistinguishable in terms of equality, hash, iteration. But differs in .capacity() (and of course in .as_ptr()).

[withoutboats]

I think a == b → a == b.clone() is a reasonable way to define making a copy of a value.

[ticki]

I cannot think of any counter-examples to a == b → a == b.clone().

[glaebhoerl]

Why not just a == a.clone()...?

[ticki]

@glaebhoerl, I guess you mean ∀x.x=clone(x).

[petrochenkov]

Stepanov (the C++ STL author) used several concepts to describe types which are "well-behaved" and can be reasoned about, when used in algorithms and collections. His terminology is also adopted for the current C++ concepts proposals.
a == a.clone() in particular looks like a part of the Regular concept.
Links:
http://www.amazon.com/Elements-Programming-Alexander-A-Stepanov/dp/032163537X
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3351.pdf

[petrochenkov]

I don't think clone should be special, we just need to come up with some form of saying in the docs "all the code can assume that implementations of a trait Tr behave as recommended in the docs of the trait Tr, unless memory safety is at stake".
It would cover a == a.clone(), clone for T: Copy vs memcmp, a == b vs !(a != b), and everything else.

[petrochenkov]

@glaebhoerl

Why not just a == a.clone()...?

f32 satisfies a == b → a == b.clone(), but not a == a.clone() :P

[glaebhoerl]

I should have guessed.