How to avoid needing `std::marker::Sized` when an associated type does not have a size?

Question

Background

I have a situation where I want to abstract over two different operation modes Sparse and Dense. Which one I pick is a compile time decision.

Orthogonal to these modes I have a number of Kernels. The implementation details and signatures of kernels differs between the two modes, but each mode has the same kernels. The kernel will be determined during runtime, based on a model file.

I now want to create a BlackBox that handles both modes and kernels.

Simplified Code

I removed additional kernels and the sparse mode.

pub struct XKernel;

pub trait KernelDense {
    fn compute_dense(&self, vectors: &[f32]);
}

impl KernelDense for XKernel {
    fn compute_dense(&self, vectors: &[f32]) {}
}

pub trait KernelCompute<V> {
    fn just_compute_it(&self, vectors: &[V]);
}

impl KernelCompute<f32> for (dyn KernelDense + 'static) {
    fn just_compute_it(&self, v: &[f32]) {
        self.compute_dense(v);
    }
}

pub trait Generalization {
    type V: 'static;

    type OperatorType: KernelCompute<Self::V>;

    fn set_kernel(&self, x: Box<Self::OperatorType>);

    fn compute(&self, v: &[Self::V]);
}

pub struct DenseVariant {
    x: Box<KernelDense>,
}

impl Generalization for DenseVariant {
    type V = f32;
    type OperatorType = KernelDense;

    fn set_kernel(&self, x: Box<KernelDense>) {}

    fn compute(&self, v: &[Self::V]) {
        self.x.compute_dense(v);
    }
}

struct BlackBox<'a, T>
where
    T: Generalization,
{
    computer: T,
    elements: &'a [T::V],
}

impl<'a, T> BlackBox<'a, T>
where
    T: Generalization,
{
    fn runtime_pick_operator_and_compute(&mut self) {
        self.computer.set_kernel(Box::new(XKernel));
        let s = self.elements.as_ref();
        self.computer.compute(s);
    }
}

fn main() {
    // What I eventually want to do:
    // let black_box = BlackBox::<DenseVariant>::new();
    // black_box.runtime_pick_operator_and_compute();
}

Playground

The code above produces the error

error[E0277]: the size for values of type `(dyn KernelDense + 'static)` cannot be known at compilation time
  --> src/main.rs:35:6
   |
35 | impl Generalization for DenseVariant {
   |      ^^^^^^^^^^^^^^ doesn't have a size known at compile-time
   |
   = help: the trait `std::marker::Sized` is not implemented for `(dyn KernelDense + 'static)`
   = note: to learn more, visit <https://doc.rust-lang.org/book/second-edition/ch19-04-advanced-types.html#dynamically-sized-types-and-sized>

I tried adding copious amounts of : Sized (e.g., giving BlackBox a where T: Generalization + Sized, which eventually just produced different errors.

Questions

1. How can I implement std::marker::Sized for (dyn KernelDense + 'static) / make this program compile addressing the intention above?
2. Why does the compiler even care about Generalization being Sized (even when I add T: Generalization + Sized to BlackBox)? Isn't BlackBox (the only one using Generalization) being monomorphized into something that is Generalization (such as DenseVariant) which then clearly has a size of Box)?

Answer 1

The error message is confusing. The ^^^s are (misleadingly) pointing at Generalization, but the actual error says dyn KernelDense, which is OperatorType. Since at least Rust 1.50, you get a much better error message:

error[E0277]: the size for values of type `(dyn KernelDense + 'static)` cannot be known at compilation time
  --> src/main.rs:42:9
   |
24 |         type OperatorType: KernelCompute<Self::V>;
   |         ------------------------------------------ required by this bound in `Generalization::OperatorType`
...
42 |         type OperatorType = KernelDense;
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ doesn't have a size known at compile-time
   |
   = help: the trait `Sized` is not implemented for `(dyn KernelDense + 'static)`

Therefore, OperatorType is what really needs to be Sized. Associated types, like generic type parameters, have an implicit Sized bound unless you specify otherwise by adding ?Sized instead:

pub trait Generalization {
    ...
    type OperatorType: ?Sized + KernelCompute<Self::V>;
    ...
}

But you'll immediately run into another problem (playground):

error[E0308]: mismatched types
  --> src/main.rs:59:47
   |
59 |         self.computer.set_kernel(Box::new(XKernel));
   |                                           ^^^^^^^ expected associated type, found struct `XKernel`
   |
   = note: expected type `<T as Generalization>::OperatorType`
              found type `XKernel`

Which, if you read between the lines a little, is basically the compiler saying "What do I do with a Box<XKernel>? I need a Box<T::OperatorType> and I don't even know what T is yet!"

And that should make sense. Because there's no rule that forbids adding a new kind of variant where OperatorType is, let's say, str:

struct StringyVariant;

impl Generalization for StringyVariant {
    type V = f32;
    type OperatorType = str;
    
    fn set_kernel(&self, x: Box<str>) {}
    
    fn compute(&self, v: &[f32]) {}
}

impl KernelCompute<f32> for str {
    fn just_compute_it(&self, vectors: &[f32]) {}
}

No rules forbid these impls, and yet it's impossible to coerce Box<XKernel> into Box<str>, so the blanket impl on BlackBox must be erroneous. It's missing a requirement: the requirement that Box<XKernel> can be coerced into Box<T::OperatorType>.

In stable Rust (as of 1.50) there is no way to write this requirement as a trait bound, so you must write two impls (i.e., one for BlackBox<DenseVariant> and one for BlackBox<SparseVariant>), or perhaps find some other way around (like using From instead of coercion).

However, in nightly Rust, you can solve the original problem with a CoerceUnsized bound and an extra as _ to hint to the compiler that it should coerce to something that makes sense:

// at top of file
#![feature(coerce_unsized)]

use std::ops::CoerceUnsized;

impl<'a, T> BlackBox<'a, T>
where
    T: Generalization,
    Box<XKernel>: CoerceUnsized<Box<T::OperatorType>>,
{
    fn runtime_pick_operator_and_compute(&mut self) {
        self.computer.set_kernel(Box::new(XKernel) as _);
        let s = self.elements.as_ref();
        self.computer.compute(s);
    }
}

Here it is in the playground.