Type inference fails for collection of trait objects

help
1

Recently I found a case where rust's type inference fails for collections of trait objects. Here an example:

use std::fmt::Debug;

#[derive(Debug)]
struct D1;

#[derive(Debug)]
struct D2;

fn debug_vec() -> Vec<Box<dyn Debug>> {
    // compiler: hmm, I don't know what type this is. Let's see how this one 
    //           unfolds.
    let mut v = Vec::new();
    
    // compiler: got it, v must be Vec<Box<D1>>!
    v.push(Box::new(D1));
    
    // compiler: gosh darn it, this is no Box<D1> added to v! That's the wrong 
    //           type! Let's raise error E0308!
    v.push(Box::new(D2));
    
    // compiler: gosh darn it, v is Vec<Box<D1>>, not Vec<Box<dyn Debug>>!
    //           Let's raise error E0308!
    v
}

fn main() {
    println!("{:?}", debug_vec());
}

Playground.

When I give a type hint in line 12

let mut v: Vec<Box<dyn Debug>> = Vec::new();

the program compiles and runs as expected.

I'm way out of my depth here, but to me it feels like type inference should be able to figure out v's type without explicit typing. My questions, before I start chasing down the rabbit hole and learn about the HM type system, rust's type inference and chalk:

  1. Is there already an RFC or even an unstable feature for enabling type inference for this kind of situations? I can't find any in the RFC book, but I'm unfamiliar with the vocabulary of type systems and inference

  2. Maybe I'm completely wrong about the difficulty of inferring the right type in the example above. If so, does anyone have any complementary literature I can read to understand the difficulties involved?

Thanks a lot!

2

I imagine there's a tradeoff here, as we don't want this to stop compiling due to the compiler never being sure if it should coerce or not:

fn foo() {
    let mut v = Vec::new();
    v.push(Box::new(D1));
    println!("{v:?}");
}

...but I'm not familiar enough with the compiler to do more than speculate.

By the way, signaling that things may not be what they seem (i.e. where a coercion is required) also results in a successful compilation.

3 Likes
3

Using as _ for explicit type coercion is a neat trick I was not aware of. Thanks!

Concerning your example, I was thinking that it could be possible to use the return type of the function to infer the type of v. We return v from a block that is expected to return Vec<Box<dyn Debug>>. I assumed that this information could be somehow leveraged to do type inference for the variable we return, v in this case.

4

Note that before coercions are ruled out, this isn’t as clear cut either. The last line

v

does actually allow v to be any type that coerces to Vec<Box<dyn Debug>>. The reasoning would need to be more smart and reason that Vec<Box<dyn Debug>> itself is, ignoring lifetimes, the only type that coerces to the type Vec<Box<dyn Debug>>. And in general, this kind of reasoning must be introduced carefully in order to minimize the potential for breakage if semver-compatible upstream changes add new possible coercions. Library changes or compiler changes. And on that note, there is a case to be made that eventually, supertraits subtraits of Debug that are inferred or perhaps explicitly marked to make sure to have a dyn Debug vtable be a prefix of their own vtable, could facilitate an implicit Vec<Box<dyn TheSubTrait>> to Vec<Box<dyn Debug>> coercion, so even in this – initially seemingly clear cut – case, there’s questions about how desirable changing the compiler behavior is.

7 Likes
5

Thanks for the explanation! Implicit conversion of return types is something I completely missed in my assessment of the difficulty of the problem.

Again, way out of my depth here, but would you mind expanding on this argument? Isn't what you are describing only possible if we'd have a cycle between subtrait Debug and its supertrait TheSuperTrait?

6

I mixed up sub- and super- in case that was causing confusion.

The following is already possible on nightly

#![feature(trait_upcasting)]

use std::fmt::Debug;

trait TheSubTrait: Debug {}

fn demo_coercion(x: Box<dyn TheSubTrait>) -> Box<dyn Debug> {
    x
}

Extending to Vec<Box<dyn _>> coercion can only ever be possible in more restricted cases that I explained above, i.e. cases

E.g. in my imagination, something like

trait TheSubTrait: #[extend] Debug {}

could be used to mark a (single) supertrait bound to influence the vtable layout such that converting pointers to dyn TheSubTrait into pointers to dyn Debug becomes a no-op, and merely involves re-interpreting the vtable by reading less far into it. If it’s a no-op, it could be allowed to implicitly happen behind Vec, too (via covariance), similar to how coercions like

trait Foo<'a> {}

fn demo_coercion(x: Vec<Box<dyn for<'a> Foo<'a>>>) -> Vec<Box<dyn Foo<'static>>> {
    x
}

work today, even though, the two trait objects are technically speaking entirely different types.

use std::any::TypeId;

trait Foo<'a> {}

fn main() {
    dbg!(
        TypeId::of::<dyn for<'a> Foo<'a>>(),
        TypeId::of::<dyn Foo<'static>>(),
    );
}

/*

[src/main.rs:6] TypeId::of::<dyn for<'a> Foo<'a>>() = TypeId {
    t: 1642206956481714344,
}
[src/main.rs:6] TypeId::of::<dyn Foo<'static>>() = TypeId {
    t: 6917648195226195345,
}

*/
1 Like
7

Yes, sorry, I got confused about how a supertrait can be cast to a subtrait.

Thanks, that is very insightful!

8

Right, I agree it could, but the compiler has to decide it has enough information at some point, even with a lack of an explicit return type (or whatever) to go on (like in my example). Currently, AFAICT, [1]

  • A call to Box::new(_) with a known type results in the type of the returned Box<_> being known
  • A call a Vec::push(_) with a known type results in the type of the Vec<_> being known

The compiler would have to stop doing that initially and instead act like it did with my as _ addition -- leave more things unknown and do the work to solve them later. But it would still have to backtrack and make the same conclusions it does in my example if there is no further information. And even in your example, as @steffahn pointed out, it would have to decide the return type without coercion was both enough information and the most relevant information (versus the types of the boxes as above).

And I think that's all possible and reasonable [2] in this case! But it's definitely more work and more complicated.

(The latter is a consideration not only for humans to reason about, but because we want multiple compilers to agree on the meaning of a program, so precedence of inference sources is relevant when more than one result is possible; it should be part of the spec of the language.)

  1. for example trying putting as _ on the D1 case only ↩︎

  2. from a high-level standpoint -- I don't know what the compilation speed hit or technical challenges would be ↩︎

9

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.