Why are there "reverse" trait bounds?

Examples of "reverse" trait bounds:

// Copy doesn't depend on Clone, it's reversed: Clone actually depends on Copy
trait Copy: Clone {}

// Ord doesn't depend on PartialOrd, it's reversed: PartialOrd actually depends on Ord
trait Ord: Eq + PartialOrd {}

// FnMut doesn't depend on FnOnce, it's reversed: FnOnce actually depends on FnMut
trait FnMut<Args>: FnOnce<Args> {
    fn call_mut(&mut self, args: Args) -> Self::Output;
}

And then there are "totally independent" trait bounds:

// Fn doesn't actually depend on FnMut, but FnMut also doesn't depend on Fn
trait Fn<Args>: FnMut<Args> {
    fn call(&self, args: Args) -> Self::Output;
}

// DereftMut doesn't depend on Deref, well... it _kinda_ does, only to inherit Self::Target, but that's moreso to prevent people from creating surprising types which deref to different types depending on mutability, DerefMut's impl doesn't actually depend on Deref in any way, nor does Deref depend on DerefMut
trait DerefMut: Deref {
    fn deref_mut(&mut self) -> &mut Self::Target;
}

So I kinda understand why these traits exist in these forms and have the bounds that they have, but since in the above particular cases the traits themselves don't actually depend on their bounds at all it seems weird to call the trait bounds as "trait bounds" since their purpose in context has nothing to do with bounding a trait so... what do I call them? Maybe "dependent traits" or "requirement traits" because if you impl the base trait you're required to impl the dependent traits within its trait bounds?

This is usually called "inheritance" in OO settings, and it's not wrong to use the term here. Copy extends Clone, because a type that is Copy is required to also be Clone. Similarly, a type that is Ord must also be PartialOrd, and a type that is DerefMut must also be Deref. This means that if you have a bound X: Copy in a generic function, you can write x.clone() even though you didn't explicitly say that X: Clone, because X: Copy implies X: Clone.

I'm not sure what about these bounds is considered "reverse" though. It's true that the colon in trait Copy: Clone does not have the same meaning as the colon in X: Clone, since one of them is a subtyping relation on traits and the other asserts that a type implements a trait.

2 Likes

I'll allow "inheritance", although I think it's not the best word -- I like "requirement" better -- but I think it's probably harmful to think of trait bounds as being a subtype relationship. That term already has a meaning in Rust which pretty explicitly doesn't apply to traits, so if you mix them up you'll probably be easily confused.

3 Likes

I have to admit that I'm not really sure how Clone depends on Copy here. It is Copy that requires the Clone trait to also be implemented, not the other way around?

Am I missing something here?

8 Likes

I think it's backwards. If I have X: Copy bound in a generic function why would I ever want to call x.clone()? Nobody would ever write code like that because there's no point to it. I don't think that's the purpose of the reverse trait bounds.

I believe the purpose of the reverse trait bounds is if I have a X: Clone bound in a generic function I can pass either Clone or Copy types into it because Copy: Clone so I guess it saves me the trouble of writing X: Clone + Copy in the function signature because X: Clone includes both Clone and Copy.

Same! I think the Fn & FnMut example and the Deref & DerefMut example both show it's possible for traits to be related to each other without either type being dependent on the other. I like the word "requirement" so far the best as well.

I see reverse trait bounds as kind of a hacky stopgap solution until specialization lands in stable. There's no reason for Copy to depend on Clone and in fact it doesn't. Ideally the standard library would provide this generic blanket impl, which clearly shows it's actually Clone that depends on Copy (if Copy is already impl'd for the type):

impl<T: Copy> Clone for T {
    fn clone(&self) -> Self {
        *self
    }
}

However the standard library cannot do the above because of the trait coherence rules, as it would prevent users from ever impling Clone for their own non-Copy types. The above generic blanket impl only becomes possible once specialization lands in stable, and then the uselessness of Copy: Clone becomes obvious.

1 Like

It's not a subtype relationship, it's a subtrait relationship. If traits are viewed as sets of types, then this is the subset relation on those sets. A subtype relationship is when you have two types X and Y such that x: X implies x: Y; similarly a subtrait relationship between traits T and U is when X: T implies X: U.

3 Likes

I don't see it that way at all. Sure, for the specific example of Copy/Clone, you can make the argument, but the way it currently works is much more general and supports other important cases.

For instance, consider PartialEq vs Eq. When you implement the Eq trait, you are making a claim about your implementation of the PartialEq trait, but this doesn't mean that there is a unique way to implement PartialEq whenever you implement Eq, even though Eq has no functions in the same way Copy has no functions.

4 Likes

You might not want to do it yourself, but you might want to pass an x: X to a generic function that accepts any type T: Clone which in turn will call .clone() internally.


Ah, and you say it yourself...

when discussing these kinds of “inheritence”-like relations between different types, or in this case traits, it’s always very important to keep in mind that they’re always reversed when you start discussing function parameters. Functions are inherently contravariant [with respect to the input type], be it in terms of Rust lifetimes, in terms of OO-inheritance or in terms of category theory.

If you have two traits Trait: SuperTrait, and a type X: Trait and another type Y: SuperTrait, then the X: Trait bound makes the type X “more powerful” than the type Y in that you can e.g. call more kinds of trait methods on X. On the other hand for functions, a fn foo<T: SuperTrait>(... T ...) is “more powerful” than a fn bar<T: SuperTrait>(... T ...) [importantly, T is not in the return type!], since foo also allows you to pass values of type Y: Trait; it’s exactly reversed.


You’re talkind about “dependency” here in terms of trait implementations. There’s no prescribed way in which trait implementations depend on each other, the implementor can decide to introduce dependencies however they like it.

In terms of dependency between trait definitions, the subtrait depends on the supertrait. I can define a trait trait Foo: bar::Bar where Bar is a trait from a different crate bar. Clearly Bar depends in no way shape or form on Foo since from the crate bar does not even know about Foo.

7 Likes

to give an example

trait A {
    fn a(&self);
}
trait B: A {
    fn b(&self);
}

struct OneWay;
// “dependency” of `A` implementation on `B` implementation
impl A for OneWay {
    fn a(&self) {
        println!("hello");
    }
}
impl B for OneWay {
    fn b(&self) {
        self.a();
        println!("world");
    }
}

struct TheOtherWay;
// “dependency” of `B` implementation on `A` implementation
impl B for TheOtherWay {
    fn b(&self) {
        println!("hello");
    }
}
impl A for TheOtherWay {
    fn a(&self) {
        self.b();
        println!("world");
    }
}

Furthermore, these kinds of dependencies can even be circular

struct Circular(bool);
impl A for Circular {
    fn a(&self) {
        println!("a");
        if self.0 {
            Circular(false).b();
        }
    }
}
impl B for Circular {
    fn b(&self) {
        println!("b");
        if self.0 {
            Circular(false).a();
        }
    }
}

fn main() {
    Circular(true).a();
    Circular(true).b();
}
2 Likes

By the way, one extra point about the syntax: the two trait definitions

trait Foo: Bar {}

and

trait Foo where Self: Bar {}

are exactly the same.

2 Likes

Yes, I agree, and I would like to find words to distinguish all of these different cases, since these case can be mixed even within a single trait declaration, e.g.

trait Ord: Eq + PartialOrd {}

Ord has what I would call a "regular" trait bound on Eq and a "reverse" trait bound on PartialOrd.

Well Copy has no functions because its implementation is provided by the compiler, where Eq doesn't have any functions or implementations. And like you said, an argument can be made for Eq: PartialEq because for a type to be equal it should at least be partially equal, and we can view Eq as "refining" PartialEq on the type-level with additional guarantees. Although those arguments cannot be made for Copy: Clone, Fn: FnMut, or DerefMut: Deref.

Also, I don't have an issue with any of those traits or their bounds, I'm just trying to find a more intuitive mental model for understanding "trait bounds" on the trait level since it's confusing and the plain Rust syntax doesn't actually reveal all of the interesting and different ways it can be used.

I think that's what's confusing. Trait bounds in trait declarations can mean the the same thing they do when used within the context of a standalone generic function, e.g. T: Trait means T depends on Trait, but they can also mean other things like Copy: Clone means "If you impl Copy you really should also impl Clone" and not that Copy depends on Clone in any way.

  • A type is Clone if you can make a copy of a value from a shared reference to that value; the function for doing so is called clone(). A type is Copy if additionally that function is a memcpy, in which case the call to clone is given the syntax sugar *x.
  • A type is FnMut if there is a function that mutates the type and some arguments and returns a value; that function is called call_mut but the syntax sugar for this is (f)(x..) instead of f.call_mut(x..). A type is Fn if additionally the function can be called with a shared reference to the value, in which case it is also available as call. Importantly, the two functions are the same - one is a weakening of the other. Otherwise the notation (f)(x) would be ambiguous about which function is getting called.
  • A type is Deref if you can get a value of type &Target from a &X. It is DerefMut if additionally you can get a &mut Target from a &mut X, where again one function refines the other: if you call x.deref_mut() you should get the same value as x.deref(). Otherwise &*x would be ambiguous.

In all three cases, while there is no direct call dependency from one function to the other, there is a "coherence" requirement between the new function being added by the subtrait and the original function in the supertrait, and this requirement can't be expressed without having the subtrait relation. It looks useless only because Rust doesn't actually have proofs or dependent types or something to express the constraint directly.

2 Likes

I don't really see those as different. In both cases, implementing Ord is just a claim about how the implementations of other traits (PartialEq and PartialOrd) behave.

The fact that Ord also provides a cmp method is not as important. It's just a convenience method that it has because one of the claims that Ord makes is that the PartialOrd implementation is such that it never returns None, and it is convenient to be able to call it without having to unwrap it.

Really, Copy is the same. It's a claim about how the implementation of another trait behaves, and it has a (compiler-provided) convenience method of calling the method from that other trait.

(yes, yes, I know that you can implement Clone in weird ways even if Copy is implemented, but now you are just violating the contract of the Copy trait, and the same caveat also applies to cmp/partial_cmp)

It seems like what everyone is calling a reverse trait bound are the cases where the claims it makes about the implementation of that other trait are strong enough that you could implement the other trait entirely using the convenience methods I talk about above.

1 Like

But that is simply not the case. Ord requires both Eq and PartialOrd. However, neither Eq nor PartialOrd requires Ord, full stop.

Or to put it back in the language of inheritance: When we say that “Dog is a subtype of Animal,” we mean that every Dog is an Animal (but not all Animals are Dogs).

Similarly, Ord is a subtrait of PartialOrd, because every totally-ordered set is a partially-ordered set (but not all partially-ordered sets are totally-ordered sets).

The : notation also has a nice transitive property: (T: Foo) + (Foo: Bar) implies (T: Bar).

4 Likes

I don't really follow what's "reversed" here.

trait Copy: Clone {}

is sugar for

trait Copy where Self: Clone {}

so it's basically the same order as usual?

2 Likes

Okay, I think I'm coming around and starting to see things from your collective point of view. At first I thought the "refinement" idea was a novelty but after @digama0's and @alice's most recent explanations I'm starting to see how it can be universally applied to all of these different traits and their bounds.

I still think it's a little confusing that DerefMut refines Deref while Fn refines FnMut but maybe the explanation for that lies in what @steffahn said earlier about how types which are normally covariant become contravariant when used as function parameters. Please correct me if I am wrong.

I do think the "refinement" idea might be a stretch in some situations. Like if I wanted to implement a generic is_even function I'd write:

fn is_even<T>(num: T) -> bool
where
    T: Rem<Output = T> + PartialEq<T> + Sized,
    u8: TryInto<T>,
    <u8 as TryInto<T>>::Error: Debug
{
    num % 2.try_into().unwrap() == 0.try_into().unwrap()
}

In the above implementation it's easy to say the generic type parameter T depends on having implementations for the % and == operators and the ability of being converted to from a u8.

But if I wanted to make it a trait with a default implementation I'd write:

trait Even
where
    Self: Rem<Output = Self> + PartialEq<Self> + Sized,
    u8: TryInto<Self>,
    <u8 as TryInto<Self>>::Error: Debug
{
    fn is_even(self) -> bool {
        self % 2.try_into().unwrap() == 0.try_into().unwrap()
    }
}

In the above scenario would we still say that the idea of evenness is a refined concept of the combined ideas of modulo arithmetic, partial equality, and conversion from the u8 data type? I guess we can say that, so it still works, hmmm.

I think my experience with OO languages might be what is confusing me. A Dog is an Animal conceptually, but in the case of most OO languages, a Dog is also an Animal literally. A Dog class would literally inherit the data and methods from an Animal class and would be very tightly-coupled to the Animal class in a literal sense and not just in a vague conceptual sense. If we were to drop the Animal class from the codebase it would probably require significant refactors to Dog.

However, if we dropped Clone from the standard library it'd require no refactors or changes to Copy! Not only would Copy's implementation stay the same for all types which impl it (even if it wasn't provided by the compiler) but also the semantics of the trait and how it's used within user code would not change. Copy and Clone are conceptually related, a copy is just a cheap fast efficient clone, but they're otherwise completely independent and decoupled implementation-wise... BUT if some type T does impl Copy then this is the only Clone impl that makes sense:

impl<T: Copy> Clone for T {
    fn clone(&self) -> Self {
        *self
    }
}

This is where the "reverse" part comes in. However as @steffahn and @alice pointed out there's no way for the compiler to enforce this, and there's no way for the standard library to provide this impl (aside through documentation). There's nothing stopping a user from writing a totally nonsense impl for Clone which doesn't use Copy at all.

Okay, so in summary: a conceptual dependence does not require or imply an implementation dependence. Thanks everyone!

Huh, I had never thought about this particular issue in this way, but yes, that's exactly it. Something that can produce an immutable reference (Deref) can't necessarily also produce a mutable reference (DerefMut), but something that can be called with an immutable reference (Fn) can definitely also be called with a mutable reference (FnMut), since mutable references are trivially downgradeable to immutable ones.

2 Likes

Regarding your initial "reversed" qualifier, I think I see what you mean:

  • we all agree that when we have T : Copy, then, a fortiori, we should have T : Clone.

  • There are two ways to achieve this property in Rust:

    • Either we provide a blanket / fully generic implementation (a proof of this implication):

      impl<T : Copy> Clone for T { … }
      
    • Or we put Clone as a requirement to implement Copy: that way the problematic impl Copy for NotClone that would break the Copy => Clone implication is impossible to write: its author will get a compilation error demanding that they impl Clone for NotClone too.

And in the case of Copy and Clone, we currently have the latter, which looks "weird" / unnatural / reversed w.r.t. to the expected "trivial" impl of Clone for Copy types.

And that's true, I think everybody agrees with that; it is indeed a limitation regarding lack of specialization which doesn't let us write such a generic blanket impl while also have all the niceties of #[derive(Clone, Copy)] struct Wrapper<T>(T); (otherwise the impl<T : Clone> Clone for Wrapper<T> and the impl<W : Copy> Clone for W (where W = Wrapper<T>) would conflict)).

The other examples follow that rule: if something is Fni.e. &self-callable, then it is easy to make it &mut self-callable, by forwarding to the &self-based logic with a &* shared reborrow.

And if something is self: &mut Self callable, then one can make it mut self: Self callable by &mut borrowing it in the function body.

And same for PartialOrd and so on :slightly_smiling_face:

2 Likes

Adding to what @alice said, the subtrait/supertrait relationships Fn: FnMut and DerefMut: Deref don’t mean that it has to be the way that the methods of Fn alone refine the methods of FnMut, and methods of DerefMut alone refine the methods of Deref.

Although it turns out to be the case for Fn and FnMut (you can easily implement call_mut in terms of call). And it’s similar for Copy: Clone, Ord: PartialOrd, PartialOrd<Rhs>: PartialEq<Rhs>, and Ord: Eq. It doesn’t have to be this way though; honestly the fact that the new API of the subtrait makes the API of the supertrait entirely useless (like you said, “If I have X: Copy bound in a generic function why would I ever want to call x.clone() ?”) this is entirely coincidental and actually rather irrelevant. The actual API of a trait includes all of the API of all of its supertraits by definition. Think of Fn inheriting all the methods from FnMut, etc., so the Fn trait conceptually consists of three methods, call, call_mut, and call_once. Just that call_mut and call_once are pretty useless when you have call and the only reason they are still there is that you only actually have the supertrait bound here because you want to have compatibility with generic methods that accept FnMut.

In the DerefMut: Deref example this is not the case. DerefMut really offers deref(&self) -> &Target and deref_mut(&mut self) -> &mut Target; there’s no redundancy, both methods cannot (generically) be used to implement the other. One could have DerefMut and Deref completely separate then, and there’s precedent: the AsRef<T> and AsMut<T> traits are separate without supertrait relationships. The problem with Deref/DerefMut is that they are to be used for dereferencing (coercion of explicit *-operator) so they must share a Target type for type-checking to work. Well, okay, there could be a common supertrait without methods that just defines the associated Target type then—but then again, conceptually, dereferencing a smart (or dumb) pointer/reference is not supposed to “mutate” the pointer itself, so while deref_mut does get &mut self access it really shouldn’t need it for the dereferencing itself, so you ought to be able to provide a &self -> &Target conversion, too. So if Deref/DerefMut were separate, literally all the types with reasonable (i.e. side-effect free) DerefMut-implementations would also implement Deref anyways. I could also try to argue that if you write a generic function that accepts a DerefMut argument, you’d often need to write DerefMut+Deref because you’d tend to need both capabilities; but there’s an argument to be had about whether Deref-bounds are a good thing in the first place since these traits are so closely tied to Rust syntax (*) and mechanisms (coercion and method resolution). The bigger practical problem with the alternative DerefMut & Deref & CommonSupertraitForTarget is that the common supertrait could be implemented by a type that doesn’t offer either of DerefMut or Deref, which would be very weird and confusing, so the status quo enforces a much nicer situation (and it’s also simpler since it involves fewer traits).

For some better examples for traits that just add some methods, take DoubleEndedIterator: Iterator. For simplicity assume that they both would only contain their respective required method, that is: next and next_back. Then Iterator is a trait with the method next, and DoubleEndedIterator adds the method next_back, but also specifies the supertrait Iterator, so effectively DoubleEndedIterator means that your type has both methods next and next_back. There’s no redundancy here, unlike the examples listed in the second paragraph.

Eq: PartialEq is different, again. It’s similar to ExactSizeIterator: Iterator (ignoring the provided methods again). They don’t add any new methods, just new properties. There’s often properties attatched to traits, so that users of a trait can do sensible stuff when implementing generic functions that work with T: SomeTrait bounds; and these properties go beyond what can be expressed by the method’s type signature. These are a bit similar to marker traits such as Send or Sync; method-less traits just describing properties of a type. Of course these method-less “marker-subtraits” (just made up this term) usually just prescribe properties that relate to methods of their supertraits. And there’s also a distinction between how strongly these properties are enforced. Going from a suggestion, like AsRef stating that it’s a “cheap reference-to-reference conversion”, to requirements that can result in logic errors if violated, such as Hash or Borrow which can both lead to very broken hashmaps if implemented incorrectly. This second category includes Eq and ExactSizeIterator; Eq can also lead to broken hashmaps, Eq and even more so Ord has requirements that can lead to broken b-tree-maps, too. For ExactSizeIterator, e.g. I’ve recently looked into the DoubleEndedIterator implementation for Zip which will definitely misbehave (i.e. potentially panic here) if the ExactSizeIterator implementation is incorrect. And lastly there’s also marker-subtraits that are unsafe and whose extra properties must be upheld at all cost, otherwise you can get any kind of undefined behavior (memory unsafety, etc.). There’s the example of TrustedLen: Iterator in nightly rust.

5 Likes