Contracts of the Clone trait?

I want to ask the contracts of the Clone trait. It could be used for deep copies, but sometimes not, say the Rc struct.

Therefore I wonder contracts for the Clone trait. I mean, ideally, what properties should the implementations of this trait should guarantee?

No contract is listed in https://doc.rust-lang.org/std/clone/trait.Clone.html

A common trait for the ability to explicitly duplicate an object.

Differs from Copy in that Copy is implicit and extremely inexpensive, while Clone is always explicit and may or may not be expensive.

The doc seems pretty explicit, does it answer your question?

The contract is: &T-> T. Ideally it should not be too expensive and avoid panic!king.

Regarding shallow versus deep, I would say that it goes for a shallow copy whenever it can (shared pointers, such as & _, Rc<_> and Arc<_>), but since it rarely can (contrary to most languages, shared pointers are not that common), it usually needs to recurse.

Anyway, the only case where the difference matters is with interior mutability, e.g., with something like T = Rc<RefCell<Inner>>. Then T::clone = Rc::clone, i.e., a shallow “copy” (incrementing the refcounts):

let x = Rc::new(RefCell::new(42));
let y = x.clone(); // Rc::clone
*x.borrow() += 27;
assert_ne!(*y.borrow(), 42);

In that case, when you need a “deep” clone (you don’t want a mutation on x to mutate y), you have to create a new Rc:

let x = Rc::new(RefCell::new(42));
let y = Rc::new(RefCell::new(x.borrow().clone()));
*x.borrow() += 27;
assert_eq!(*y.borrow(), 42);

but then usually this means that interior mutability shouldn’t have been used to begin with:

let mut x = Rc::new(42);
let y = x.clone(); // Rc::clone
*x.make_mut() += 27; // clones the pointee to avoid mutating a shared value
assert_eq!(*y, 42);
2 Likes

I would say that the convention is for Clone to be as shallow as possible.

Thanks to the borrow checker, you can’t generally tell the difference between shallow and deep copies in rust unless the type happens to have interior mutability. This makes shallow copies the clear winner for the majority of use cases in rust, and so it’s simply not something the average rust author thinks about every day.

6 Likes

By contract, I meant something essentially equivalent to a set of class invariants. With some efforts, it could be formalized.

If I understand correctly what this link is explaining, it can’t exist on trait because these constrains are on the data and Rust’s trait can’t have any.

If we look at the data, it says in std::rc's doc:

Invoking clone on Rc produces a new pointer to the same value in the heap.

But you can’t make any promise on the trait itself. For example if a String would do the same, you’d have two owners.
You can’t even say clones will be “equals”, that’s a Copy promise. For example these two types have the same data but behave very differently.
The only thing you can be 100% sure is that for any &T you will get a T.

1 Like

This, basically. Clone itself has no supertraits or other methods besides clone, so there’s nothing for us to talk about!


Now, there are some rules that are generally taken for granted when you look at Clone in combination with other traits. The vast majority of rust code assumes that:

If A: Clone + Hash:
      hash(&a) == hash(&a.clone())

If A: Clone + Display:
      a.to_string() == a.clone().to_string()

If A: Clone + PartialOrd<B>:
      a.partial_cmp(&b) == a.clone().partial_cmp(&b)
                        == a.partial_cmp(&b.clone())`

Notice the awkward way I wrote the last one; you can’t say a == a.clone() because of floats. And surely, as you try to specify things further and further, you’ll just run into mountains of caveats like refcounts, vector capacity, and +0.0 == -0.0.

2 Likes

With Eq instead of PartialEq we could add the following informal assumption:

If A : Clone + Eq:
    a == a.clone()

Another thing that seems reasonable to ask would be that if A: Clone + Copy, then Clone just does a cheap copy.

AFAIK Vec<T>::clone might actually copy the data if T: Copy thanks to specialization. So if A: Clone + Copy, you can not rely on your Clone being called when you put A into a container and then clone that container.

2 Likes

Wow, I didn’t even realize that you can implement Copy manually. Up until now I thought it had to be derived, thereby preventing a custom Clone impl.

Now I have to reconsider why none of the array vec implementations I’ve looked at impl Copy… (1 2)

You can implement Copy, but there are no methods. It’s basically just a marker trait for the compiler. An array-vec might wish not to copy unused entries, but there’s no way to control that.

Doesn’t really explain why they don’t impl Copy for T: Copy though. I mean, a move already requires just as much work. Might as well make lemonade from those lemons.

That’s because ArrayVec has to implement Drop, and you can’t implement both Drop and Copy, so you would need to duplicate all of the functionality across two types to make it work. At best, you could make a thin wrapper around the Copy version that implements Drop, and the Copy version will have a public constructor function only for Copy types. This gets cumbersome to maintain.

3 Likes

First, I want to clarify that I was asking a contract as a set of properties by design that an implementation should comply. If an implementation does not comply, maybe the compiler cannot check, it should be considered as an incorrect implementation.

The properties you have listed seem okay, but I am more concerned about the properties with regards to mutabilities.

By the way, I roughly grasped the idea of interior mutability, but I failed to see a formalism (not necessarily written in formal language, but could be) to make this precise.

By the way, for traits, contracts could also talk about their elements (that is to say, about a general proposition about elements in all implementations), but not necessarily expressible in Rust. In the wiki page, it only talks about constraints of 0th-order (namely, in the language of propositional logic). We also accept constraints in first order language, or even higher, just like:

For all elements x of (implementations of) a trait T, the type of x should be an implementation of Eq.

One can also include generic propositions similar to axiom schema in logic.

Interior mutability isn’t the best name, a better name would be shared mutability. In Rust, we have two primitive pointer types that make the distinction of shared or unique.

The shared borrow (&T) and the unique borrow (&mut T). Because shared mutation is extremely hard to reason about, shared borrows are immutable by default, and unique borrows are mutable. But what if we absolutely have to share and mutate something something? For example across threads.

This is where we need to recover the idea of shared mutability as a separate primitive, UnsafeCell<T>. Everything that can mutate behind a shared borrow must go through an UnsafeCell somewhere down the line. Every other way of going from a shared borrow to a unique borrow is instant UB. Everything from Cell<T> and Mutex<T> to atomics and mpsc depend on UnsafeCell to get shared mutability.

This is already documented:

Types that are Copy should have a trivial implementation of Clone. More formally: if T: Copy, x: T, and y: &T, then let x = y.clone(); is equivalent to let x = *y;. Manual implementations should be careful to uphold this invariant; however, unsafe code must not rely on it to ensure memory safety.

3 Likes

I forgot about Drop – I guess we would need negative trait bounds like impl<T: !Copy> Drop ... to make impl<T: Copy> Copy ... possible.

Yes, but that form of negative trait bounds would make adding a trait implementation a breaking change. Also Drop is not allowed to have different bounds than the type definition, so

struct Foo<T>(T);

impl<T: std::fmt::Display> Drop for Foo {
    fn drop(&mut self) {}
}

Doesn’t work (although it would be nice if it did work)

impl<T: Drop> Drop for ArrayVec<T> would suffice for arrayvec’s use case, except it’s forbidden as mentioned by @KrishnaSannasi just now. [update: This is incorrect; see replies.]