Generic programming with traits


#1

Hi folks!

I develop a generic constraint library and have some difficulties to achieve a truly generic library. Basically, I have a potentially infinite number of constraints that must implement several traits: Propagator, DeepClone,… In my solver, I store these constraints in a vector which has type: Vec<Box<Propagator+DeepClone+...>>, since this syntax is not possible, I use a trait erasure, let’s call it ErasurePropagator. If I decomposed operations into several traits, it’s because they are independents. The problem is that DeepClone has a clone method returning a boxed type, but what should be that type?

  • Box<Self> doesn’t work because it makes DeepClone object-unsafe.
  • Box<DeepClone> doesn’t work because we can not cast it to Box<ErasurePropagator> (non-scalar cast).
  • Box<PropagatorErasure> works but it adds unnecessary coupling between all these traits and DeepClone would not be re-usable in others contexts.

I don’t understand why the first solution prevents DeepClone to be object-safe (Self is boxed), is there any conflicting requirements? Is it just not implemented yet? Do you have any suggestions to make it work?

A toy example to test things is available here, it implements the first solution.


#2

I found a “workaround” that is acceptable. First DeepClone just returns Self unboxed. Then, I define a BoxedDeepClone trait and an implementation for each types implementing DeepClone+Propagator+.... Thus, the traits DeepClone, Propagator, … stay uncoupled and the machinery for storing multi-traits types is just two traits: BoxedDeepClone and PropagatorErasure. The code below is taken from my library and simplified, it should give you the main idea:

// The initial problem was to store types implementing several traits.
pub struct Solver<Dom> {
  propagators: Vec<Box<PropagatorErasure<Dom> + 'static>>
}

// The traits we want to polymorphically store.
pub trait Propagator
{
  fn propagate(&mut self) -> bool;
}

pub trait PropagatorDependencies
{
  fn dependencies(&self) -> Vec<(usize)>;
}

pub trait DeepClone<State>
{
  fn deep_clone(&self, state: &State) -> Self;
}

// A kind of "hack" for cloning values while being sure they implement all the traits above.
pub trait BoxedDeepClone<D>
{
  fn boxed_deep_clone(&self, state: &Vec<SharedVar<D>>) -> Box<PropagatorErasure<D>>;
}

impl<R, D> BoxedDeepClone<D> for R where
  R: DeepClone<Vec<SharedVar<D>>>,
  R: Propagator,
  R: PropagatorDependencies,
  R: 'static
{
  fn boxed_deep_clone(&self, state: &Vec<SharedVar<D>>) -> Box<PropagatorErasure<D>> {
    Box::new(self.deep_clone(state))
  }
}

// The trait erasure, because only one trait is accepted in `Box<Trait>`.
pub trait PropagatorErasure<D>:
    Propagator
  + PropagatorDependencies
  + BoxedDeepClone<D>
{}

impl<
  D,
  R: Propagator
   + PropagatorDependencies
   + BoxedDeepClone<D>
> PropagatorErasure<D> for R {}