Iterating on implementations of given trait (generic processing)

Hi,

I'm writing some program accepting 2+ formats of input data and then doing some generic processing on it. Naturally, I've designed something resembling:

trait Processor {
  fn process(input: &str) -> Option<String>;
}

struct Horse {}
impl Processor for Horse { /* ... */ }

struct Dog {}
impl Processor for Dog { /* ... */ }

fn do_magic(input: &str) -> Option<String> {
  // Pseudo-code, this obviously does not compile.
  for dyn one_impl in [Horse, Dog] /* order is important */ {
    if let Some(out) = one_impl::process(input) {
      return Some(out);
    }
  }
  None
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=38be00e43037d1675c594858a4f29604

I'm trying to understand how I could write do_magic to do that kind of "iterate over implementations of Processor in that order and return the first output that succeeds".

I currently can only think of methods I find suboptimal/ugly:

  1. have a bunch of ifs for each implementation similar to
if let Some(out) = Horse::process(input) { return Some(out); }
if let Some(out) = Dog::process(input) { return Some(out); }
None
  1. do just that, but with some macro_rules! :sweat:

This example is minimal and has only 2 impls, so it does not look that bad, but IRL I have more impls and extra generic stuff going on for each, making for pretty terrible code using that method.

I feel like I'm missing something obvious, any idea? Thanks!

This is what I could come up with

#![allow(clippy::type_complexity)]

trait Processor {
    fn process(input: &str) -> Option<String>;
}

struct Horse {}
impl Processor for Horse {
    fn process(input: &str) -> Option<String> {
        Some("foo".into())
    }
}

struct Dog {}
impl Processor for Dog {
    fn process(input: &str) -> Option<String> {
        Some("bar".into())
    }
}

fn do_magic(input: &str) -> Option<String> {
    for process in processors::<tlist![Horse, Dog]>() {
        if let Some(out) = process(input) {
            return Some(out);
        }
    }
    None
}

// test
pub fn main() {
    for process in processors::<tlist![Horse, Dog]>() {
        println!("{:?}", process(""));
    }
}

/////////////////////////////////////////////////////////////////////////////////////////
// lists of types

use std::convert::Infallible;

// uninhabited marker types
pub struct Cons<Type, Types>(Infallible, Type, Types);
pub struct Nil(Infallible);

// macro turning tlist![A, B, C] into
// Cons<A, Cons<B, Cons<C, Nil>>>
#[macro_export]
macro_rules! tlist {
    ($T:ty $(, $Ts:ty)* $(,)?) => {
        $crate::Cons<$T, tlist![$($Ts),*]>
    };
    () => {
        $crate::Nil
    }
}

/////////////////////////////////////////////////////////////////////////////////////////
// creating an iterator of fn pointers for a list of types

trait ListOfProcessors {
    const STEP: Option<(fn(&str) -> Option<String>, Self::TailIter)>;
    type TailIter: Iterator<Item = fn(&str) -> Option<String>>;
    const SIZE: usize;
}

fn processors<Types: ListOfProcessors>() -> impl Iterator<Item = fn(&str) -> Option<String>> {
    Processors::<Types>::Head
}

enum Processors<Types: ListOfProcessors> {
    Head,
    Tail(Types::TailIter),
}
impl<Types: ListOfProcessors> Iterator for Processors<Types> {
    type Item = fn(&str) -> Option<String>;

    fn next(&mut self) -> Option<Self::Item> {
        match self {
            Processors::Head => match Types::STEP {
                Some((item, tail)) => {
                    *self = Processors::Tail(tail);
                    Some(item)
                }
                None => None,
            },
            Processors::Tail(tail) => tail.next(),
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        match self {
            Processors::Head => (Types::SIZE, Some(Types::SIZE)),
            Processors::Tail(tail) => tail.size_hint(),
        }
    }
}

enum NilIter {}
impl Iterator for NilIter {
    type Item = fn(&str) -> Option<String>;
    fn next(&mut self) -> Option<Self::Item> {
        match *self {}
    }
}
impl ListOfProcessors for Nil {
    const STEP: Option<(fn(&str) -> Option<String>, NilIter)> = None;

    type TailIter = NilIter;

    const SIZE: usize = 0;
}
impl<Type: Processor, Types: ListOfProcessors> ListOfProcessors for Cons<Type, Types> {
    const STEP: Option<(fn(&str) -> Option<String>, Processors<Types>)> =
        Some((<Type as Processor>::process, Processors::Head));

    type TailIter = Processors<Types>;

    const SIZE: usize = Types::SIZE + 1;
}

(in the playground)

Hm, admitted, I’ve probably over-engineered this. You could simply do

fn do_magic(input: &str) -> Option<String> {
    for process in [Horse::process, Dog::process] {
        if let Some(out) = process(input) {
            return Some(out);
        }
    }
    None
}

lol.

1 Like

I think we need talk about what kind of stuff this “extra generic stuff” is; in particular if your Processor trait has more than one method; possibly even associated types?


Edit:

As long as it’s just multiple methods, you could do something like

struct DynProcessor {
    process: fn(&str) -> Option<String>,
    other_method: fn(),
}
impl DynProcessor {
    fn process(&self, input: &str) -> Option<String> {
        (self.process)(input)
    }
    fn other_method(&self, ) {
        (self.other_method)()
    }
}

trait Processor {
    fn process(input: &str) -> Option<String>;
    fn other_method();
    const DYN: DynProcessor = DynProcessor {
        process: Self::process,
        other_method: Self::other_method,
    };
}

struct Horse {}
impl Processor for Horse {
    fn process(input: &str) -> Option<String> {
        Some("foo".into())
    }
    fn other_method() {
        todo!()
    }
}

struct Dog {}
impl Processor for Dog {
    fn process(input: &str) -> Option<String> {
        Some("bar".into())
    }
    fn other_method() {
        todo!()
    }
}

fn do_magic(input: &str) -> Option<String> {
    for one_impl in [Horse::DYN, Dog::DYN] {
        if let Some(out) = one_impl.process(input) {
            return Some(out);
        }
    }
    None
}

Is there a reason you couldn’t use regular dyn polymorphism here? You’d just need to give the process methods a self parameter and then have a plain old list of objects rather than a typelist or other exotics?

@steffahn, like you mentioned in your reply, indeed I don't have just a single method, otherwise I'd just have built a static slice of references to a generic method indeed. Sorry my original post was incomplete.

@jdahlstrom, this seems to be similar to what @steffahn ended up suggesting in post #4.

But maybe you're referring to something simpler like this (or using Box<dyn>)? Rust Playground – I could indeed get behind that, thanks for the suggestion, is there anything I could improve there?

I do find it sad that I need to carry around these physical instances, when I "just" wanted a way of having a compile-time (static) for-loop that refers to "types".

Yes, indeed I was, just the way you’d do it in a standard issue OOP language like Java. steffan’s array-of-function-pointers is also fine as long as you don’t need several related functions in one entity – which is of course what objects are. Note also that as long as the structs are stateless (ie. unit structs), you don’t really need to care about the instances because unit structs are necessarily singletons, and in Rust the sole value of a unit struct has the same name as the type. Hence:

    struct Foo;
    impl Foo {
        fn func1() {}
        fn func2(self) {}
    }

    Foo::func1();
    Foo.func2();

The major difference being that only func2 could be a trait method callable through dyn Trait because the self argument is needed to get to the correct vtable.

1 Like

Amazing, thanks for the explanation.