How to implement Sized trait for another trait?

help
#1

Hi, I'm working on a Sudoku solver, where I want to have a list of strategies which will be applied one after another.

I don't know how to put them into a Vector, so that I can later iterate over it and call each of them. My code is:

pub struct SolvingStep {
}

pub trait Strategy {
    fn find_step(&self) -> Option<SolvingStep>;
}

pub struct S01SimpleNaked {
}

impl S01SimpleNaked {
    pub fn new() -> Self {
        Self{}
    }
}

impl Strategy for S01SimpleNaked  {
    fn find_step(&self) -> Option<SolvingStep> {
        todo!()
    }
}

pub struct S02HiddenSingle {

}

impl S02HiddenSingle {

}

impl Strategy for S02HiddenSingle {
    fn find_step(&self) -> Option<SolvingStep> {
        todo!()
    }
}

pub struct SudokuSolver {
    strategies: Vec<dyn Strategy>
}

impl SudokuSolver {
    pub fn new() -> Self {
        Self {
            strategies: vec![S01SimpleNaked{}, S02HiddenSingle{}]
        }
    }
}

fn main() {

}

and I'm getting following compilation error:

   Compiling playground v0.0.1 (/playground)
error[E0277]: the size for values of type `(dyn Strategy + 'static)` cannot be known at compilation time
   --> src/main.rs:38:17
    |
38  |     strategies: Vec<dyn Strategy>
    |                 ^^^^^^^^^^^^^^^^^ doesn't have a size known at compile-time
    |
    = help: the trait `Sized` is not implemented for `(dyn Strategy + 'static)`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0277`.
error: could not compile `playground`

To learn more, run the command again with --verbose.

Code is here:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8bb5ed960ecdd1fd15e0aad552d0ed74

How can I put "trait instances" into one vector? Or do I simply need to provide Sized as compiler is suggesting? How can that be done? Many thanks!

#2

Trait objects (dyn Trait) are never Sized: They need to be behind some kind of indirection. The easiest way here is to put them in a Box. (Playground)

pub struct SudokuSolver {
    strategies: Vec<Box<dyn Strategy>>
}
7 Likes
#3

Note that the compiler is not suggesting that you need to implement Sized. It merely states that Sized isn’t implemented for/by dyn Strategy.

Of course if any ordinary trait is not implemented by a type, there’s multiple options of how to resolve the issue, one of them being to implement the trait for the type, but another very common option is that you just chose the wrong type — the compiler usually can’t know this, hence even in the general case it isn’t necessarily suggesting that you should implement a trait when it says that “xyz is not implemented for …”. In this case the error message is actually trying to explain that this isn’t about any traits per se, the main message being “the size for values of type (dyn Strategy + 'static) cannot be known at compilation time”. Maybe it’s still a bit hard to make the connection for people unfamiliar with the Sized trait and unsized types.

You can think of trait object types like dyn Strategy of a way to do dynamic typing without introducing implicit indirection. This doesn’t mean that you don’t need the indirection, but Rust likes to be explicit about this kind of stuff unlike many other programming languages in many of which values/objects are always behind a pointer, also there’s different kinds of pointers in Rust regarding ownership anyways, so there’s Box<dyn Strategy>, &dyn Strategy, &mut dyn Strategy, or Rc<dyn Strategy or Arc<dyn Strategy> to choose from. That’s probably all the trait object types you commonly need. Unless you want to go into the details of what works and what doesn’t work with so-called “unsized” types like dyn Trait or slices, “[T]”, it’s best to think of these types to not exist in isolation at all, you can’t use them as type parameters in most cases anyways and won’t be able to directly put them into variables or fields either; only resorting to familiar combinations like Box<dyn Trait> or &[Type] is what you mostly need.

So whenever you see dyn Trait or [Type] in unfamiliar combinations like Option<dyn Strategy> or Vec<[i32]>, you should be wary of such constructs and need to double-check if the generic types involved (Option or Vec in this case) have the same “power” that Box or Arc or &/&mut have. In case of e.g. Box, you look at its documentation, expand the [+] Show declaration and look for the T: ?Sized bound, that’s the indication that it’s supporting types such as dyn Strategy. For Vec or Option, you won’t find this bound, that’s the technical reason for why the types Option<dyn Strategy> or Vec<[i32]> are wrong and will give compilation errors, and that’s also the reason why the error message is talking about a “Sized” trait in the first place.

4 Likes