[Solved] Dynamic dispatch: Trait object not object-save, alternatives?


#1

Hi everyone,

I’m currently writing a library and do have a question about the design.

The user will create objects of a specific type using the builder pattern to supply various options.
One of these options is the type of algorithm that is going to be used later on.

Currently I’m using enums and nested matches to choose the appropriate algorithm.
This works but is somehow cumbersome for me to maintain (macros may help a bit) and inefficient, since it has to be evaluated multiple times.

    enum Algorithm {
        algo1,
        algo2,
        algo2
    }

    ...

    // inside impl:

    match self.some_option {
        option1 => {
            match self.algorithm {
                algo1 => {...}
                algo2 => {...}
                algo3 => {...}
            }
        }

        option2 => {
            match self.algorithm {
                algo1 => {...}
                algo2 => {...}
                algo3 => {...}
            }
        }
        ...
        // and so on
    }

Now I do have the following options to make this better:

  • Use a trait object and dynamics dispatch.
    Unfortunately this is not possible since the function that implements the specific algorithm is generic and thus not object-save.

    trait Algorithm {
        fn run<T: SomeOtherTrait>(val: T, ...) {...}
    }

    struct Algo1;
    struct Algo2;
    struct Algo3;

    impl Algorithm for Algo1 {
        fn run<T: SomeOtherTrait>(val: T, ...) {...}
    }

    impl Algorithm for Algo2 {
        fn run<T: SomeOtherTrait>(val: T, ...) {...}
    }

    // and so on

    struct Configuration<T: SomeOtherTrait> {
        item: T,
        ...
        algorithm: Algorithm
    }

    // BuilderPattern not shown here
    let config = Configuration<Type1> {// other fields...
                                algorithm: &Algo1 as &Algorithm} // does not compile, not object-save

  • Put the functions into a Box and use that boxed type as a field of the builder pattern struct.
    This would work but seems to be a bit “unrusty”, or not ?

    fn run_algo1<T: SomeOtherTrait>(val: T, ...) {...}
    fn run_algo2<T: SomeOtherTrait>(val: T, ...) {...}
    fn run_algo3<T: SomeOtherTrait>(val: T, ...) {...}

    struct Configuration<T: SomeOtherTrait> {
        item: T,
        ...
        algorithm: Box<Fn(T, ...)>
    }

    // BuilderPattern not shown here
    let config = Configuration<Type1>{// other fields...
                                algorithm: Box::new(run_algo1)}

  • I’ve read about a language change that would allow to define impls for enum variants
    (that is treat them as real type ?) and if I understood it correctly this would solve my problem, right ?
    (IIRC it was a blog post, unfortunately I don’t find it anymore. Should have bookmarked it…)

    trait Algorithm {
        fn run<T: SomeOtherTrait>(val: T, ...) {...}
    }

    enum AlgorithmStrategy {
        algo1,
        algo2,
        algo2
    }

    impl Algorithm for algo1 { // <- not possible right now, but maybe in the future ?
        fn run<T: SomeOtherTrait>(val: T, ...) {...}
    }

    impl Algorithm for algo2 { // <- not possible right now, but maybe in the future ?
        fn run<T: SomeOtherTrait>(val: T, ...) {...}
    }

    // and so on

    struct Configuration<T: SomeOtherTrait> {
        item: T,
        ...
        algorithm: AlgorithmStrategy
    }

    // BuilderPattern not shown here
    let config = Configuration<Type1>{// other fields...
                                algorithm: algo1}



  • Use another trait (static dispatch), but then the user has to specify two (and later more) type parameters
    and additionally call the builder pattern method. It would be much nicer if the user just had to call the
    builder pattern method and set all options there.

trait Algorithm {
    fn run<T: SomeOtherTrait>(val: T, ...) {...}
}

struct Algo1;
struct Algo2;
struct Algo3;

impl Algorithm for Algo1 {
    fn run<T: SomeOtherTrait>(val: T, ...) {...}
}

impl Algorithm for Algo2 {
    fn run<T: SomeOtherTrait>(val: T, ...) {...}
}

// and so on

struct Configuration<T: SomeOtherTrait, U: Algorithm> {
    item: T,
    ...
    algorithm: U
}

// BuilderPattern not shown here
let config = Configuration<Type1, Algo1>{...}

// Later versions in the future may add more options:
let config = Configuration<Type1, Algo1, Option1, AnotherOption2, MoreOptions5>{...}


  • (just for explanation) In c++ or Java there would be a base class / interface providing a “run” method and each algorithm would inherit from that
    and implement the algorithm in the “run” method. In the builder pattern struct there would then be a field of the type of the base class. (See StrategyPattern)

Are there any other options ? Did I miss s.th. or are some of the above assumptions wrong ?
Maybe there also is an obvious and simple solution and I just don’t see it :wink:

Sorry for the long post, but I hope that if s.o. else has this problem he / she will see all the possibilities and be pointed to the right direction(s).

Thanks a lot!


#2

The syntax highlighting doesn’t work for the first code block, but it works in the preview when I edit this post. Looks like a bug ?


#3

Couldn’t this be done through static dispatch(you don’t need to box a function)?
Btw, the pattern you are describing also sounds somewhat like the Command pattern.
Also, this might be helpful to understand more about object safety.


#5

I think you want this instead:

trait Algorithm<T: SomeOtherTrait> {
    fn run(val: T, ...);
}
impl<T: SomeOtherTrait> Algorithm<T> for Algo1 {
    fn run(val: T, ...) {...}
}
struct Configuration<T: SomeOtherTrait> {
        ...
    algorithm: Box<Algorithm<T>>
}

This is the same as in C++ where you can’t have a template virtual method, but can have virtual methods in a template class, and for the same reason - limits of monomorphization-based generics.


#6

Hi LilianMoraru,

Couldn’t this be done through static dispatch(you don’t need to box a function)?

The only way I can see static dispatch is through another generic type parameter (like above), or not ?

Btw, the pattern you are describing also sounds somewhat like the Command pattern.

Thanks for the link. Since I want to encapsulate an algorithm, the Strategy Pattern seems to be more suitable.
See this discussions on StackOverflow:

Funny that you link to a game dev. site. Do you have a background in game developing ?
One of the next things I want to do with Rust is to write a game using Piston.
(Probably I’ll port my SnowBall game from Python to Rust: https://github.com/willi-kappler/Snowball_Python)

Also, this might be helpful to understand more about object safety.

Oh yes, I remember I’ve read this but I’m not sure if it helps in my actual case.

If I understood it correctly the “where” clause is used to make a trait generally more open but restrict the type parameter for some specific methods.
This allows one to use the more open methods for (nearly) all types and one doesn’t have to care about the specific methods if these are not used.
But if these specific methods are needed, only those types are allowed that obey the bound in the where clause.
(Please correct me if I’m wrong)


#7

Hi comex,

thanks, this looks like what I need but I can’t make it run:
Here is the PlayPen, if I enable the lines

    val.do_sth();

The compiler complains:

<anon>:24:13: 24:21 error: no method named `do_sth` found for type `&T` in the current scope
<anon>:24         val.do_sth();
                      ^~~~~~~~
<anon>:24:13: 24:21 note: found defined static methods, maybe a `self` is missing?
<anon>:2:5: 2:17 note: candidate #1 is defined in the trait `SomeOtherTrait`
<anon>:2     fn do_sth();
             ^~~~~~~~~~~~
<anon>:24:13: 24:21 help: items from traits can only be used if the trait is implemented and in scope; the following trait defines an item `do_sth`, perhaps you need to implement it:
<anon>:24:13: 24:21 help: candidate #1: `SomeOtherTrait`
error: aborting due to previous error

But the trait is implemented and in scope, or not ? And self refers to “Algo1”.
Any ideas ?


#8

Ok, so you want to say something like: here is a generic sort function, plug in your algorithm and it will sort using your algorithm(by “your” - it would mean that you can also get it from other library). Command pattern is definitely not the one…

Nope. But in 2014, after seeing Mike Acton’s CppCon 2014 epic talk, I got more interested in game dev material.
When I have the chance, I prefer to read game dev material(over the other material on the same topic) because it is oriented more on performance, which is an area I was always interested in.


#9

Yes exactly.

That’s true, nice catch! Looks like I’ll have to listen more carefully what the game devs are saying… :slightly_smiling:


#10

The solution is described here. Thanks to /r/cdbfoster and /r/phil-n, who both pointed out that I 've missed self and thus created a static method.

Adding &self to the Trait and the implementation solves the problem: PlayPen.