I have two traits which are basically equivalent, but one provides a lower level interface than the other. Given the higher level trait, one can easily implement the lower level trait. I want to write a library which accepts an implementation of either trait.
My specific case is a trait for traversing a tree:
// "Lower level" version of the trait
pub trait RawState {
type Cost: std::cmp::Ord + std::ops::Add<Output = Self::Cost> + std::marker::Copy;
type CulledChildrenIterator: Iterator<Item = (Self, Self::Cost)>;
fn cull(&self) -> Option<Self::Cost>;
fn children_with_cull(&self) -> Self::CulledChildrenIterator;
}
// "Higher level" version of the trait
pub trait State: RawState {
type ChildrenIterator: Iterator<Item = (Self, Self::Cost)>;
fn children(&self) -> Self::ChildrenIterator;
}
// Example of how RawState could be implemented using State
fn state_children_with_cull<S: State> (s: S)
-> impl Iterator<Item = (S, S::Cost)>
{
s.children()
.filter_map(move |(state, transition_cost)|
state.cull().map(move |emission_cost|
(state, transition_cost + emission_cost)
)
)
}
Here, State trait provides an interface where you define the .children() function to list the children, and the .cull() function to potentially cull a state.
The RawState trait provides an interface where you define a function .children_with_cull() instead, which iterates through the children and culls them in a single function call. This allows an implementation of RawState to never even generate children that it knows will be culled.
I would like to allow most users to only implement the State trait, and have the RawState implementation be automatically generated based on their State implementation. However, when implementing State, some parts of the trait are still a part of RawState, e.g.
#[derive(Clone, Eq, PartialEq, Hash, Debug)]
struct DummyState {}
impl State for DummyState {
type Cost = u32;
type ChildrenIterator = DummyIt;
fn emission(&self) -> Option<Self::Cost> {
Some(0u32)
}
fn children(&self) -> DummyIt {
return DummyIt {};
}
}
Will give errors, because the type "Cost" is defined in RawState, not in State. On potential workaround, to redefine all the relevant parts of the RawState inside State, i.e. define State as
pub trait State: RawState {
type Cost: std::cmp::Ord + std::ops::Add<Output = Self::Cost> + std::marker::Copy;
type ChildrenIterator: Iterator<Item = (Self, Self::Cost)>;
fn cull(&self) -> Option<Self::Cost>;
fn children(&self) -> Self::ChildrenIterator;
}
But then the compiler will complain about the ambiguous duplicate definitions. For example in the DummyState implementation for State, it will complain that Self::Cost is ambiguous, since it can't tell whether you are referring to <Self as State>::Cost, or <Self as RawState>::Cost.
Considering that both RawState and State are not object-safe (because they use Self in return types), I'll assume that you don't intend to create trait objects for these traits (i.e. no &RawState).
The supertrait bound State: RawState is mostly important when dealing with trait objects, because trait objects can only specify one trait (plus a select few whitelisted traits from the standard library that have no methods, like Copy, Send and Sync). The vtable that the trait object refers to only contains pointers to the methods defined in that trait. But if the trait has supertrait bounds, then the methods from those traits are also included in the vtable. Thus, a &State (if it was legal) would give you access to children_with_cull.
Another situation where the supertrait bound is important is when the subtrait provides default implementations for some methods. The default implementation can make use of the supertrait bound to access methods from another trait.
Since you can't use trait objects, and since you don't have default implementations for the methods in State, I think that you should simply not declare the supertrait bound State: RawState, because it adds nothing (and indeed, causes issues).
With this approach, it becomes necessary to copy the members from RawState that we need to implement State, as you suggested. State would thus be defined like this:
pub trait State: Sized {
type Cost: std::cmp::Ord + std::ops::Add<Output = Self::Cost> + std::marker::Copy;
type ChildrenIterator: Iterator<Item = (Self, Self::Cost)>;
fn cull(&self) -> Option<Self::Cost>;
fn children(&self) -> Self::ChildrenIterator;
}
(Note that the bound State: Sized is required because we use Self in ChildrenIterator. RawState also need the bound RawState: Sized.)
Finally, we can provide a blanket impl of RawState for all types that implement State. With this impl, any type that implements State will automatically implement RawState.
impl<T> RawState for T
where
T: State
{
type Cost = <Self as State>::Cost;
type CulledChildrenIterator = std::iter::Empty<(Self, Self::Cost)>; // placeholder
fn cull(&self) -> Option<Self::Cost> { <Self as State>::cull(self) }
fn children_with_cull(&self) -> Self::CulledChildrenIterator {
unimplemented!()
}
}
Note the syntax to disambiguate the conflicting names: <Self as State>. It's used on the two members we duplicated so that RawState defers to State.