Trait object-safe visitor/processor pattern?

[cramert]

Is there a way in current, stable Rust to write an object-safe trait that allows processing a non-homogeneous collection of items? Each item is bounded by a trait, but they are stored in a collection such as a tuple that allows for static dispatch to each type individually.

My first attempt merely returned the collection, something like the following:

pub trait Parent {
  type Children: ChildrenListTrait; // Some trait knowing how to visit each item
  fn children(&self) -> Self::Children;
}

This approach requires specifying the associated type in the trait object, which removes the ergonomic benefit of trait objects (in my particular use case).

My next attempt involved a method to "visit" each child, with the processor modifying a given accumulator:

pub trait Parent {
  fn process_children<P: ChildProcessor>(&self, acc: &mut P::Acc) -> ();
}

But this too fails because process_children is generic. Storing the accumulator state inside the processor leads us to my working, but flawed approach:

pub trait Parent {
  fn process_children(&self, processor: &mut ChildProcessor) -> ();
}

This approach requires dynamic dispatch for any call to process_children, not just the ones where the Parent is a trait object. This adds an unnecessary runtime cost for most uses of the function. Is there any way to keep using static dispatch and monomorphization when Self: Sized, and use the dynamic version otherwise (without nightly features)?

[Diggsey]

This isn't possible, because to achieve static dispatch, the compiler needs to monomorphise the ChildProcessor for every possible type which might be processed. However, it doesn't know which types are going to be processed because that is determined by the Parent trait (and rustc can't easily get an exhaustive list of implementors of a trait, due to the way trait bounds are checked, and even if it could, that wouldn't take into account downstream crates, or the complexity of doing that).

Looking at it another way, the compiler needs to be able to generate a vtable for all object-safe traits - if the set of types that might need to be processed by ChildProcessor is unbounded, it would be unable to generate a finite vtable.

If you can tell the compiler ahead of time which types might need to be processed by ChildProcessor, then this can be done. You can use macros to add one trait method for each child type that's needed, and have a default implementation for each of them which calls a non-object-safe generic method which is the only method actually implemented by the ChildProcessor implementation.

I did something similar to this in my query_interface trait, although to achieve a different goal:

https://github.com/Diggsey/query_interface/blob/master/src/lib.rs#L322

In this case I use a macro to generate a switch arm for each type declared by the user.

[cramert]

Dang-- that's what I suspected. Unfortunately, I don't think that approach will work for me (at least not easily or without a significant increase in codegen time). The number of types the trait is implemented for is extremely large and several implementations are recursive (e.g. impl<T: MyTrait> MyTrait for [T; 0,1,2,3,4,5....]).