Type inference with generic and opaque type

Hey, this is my first topic so in addition to being a request for help, see this as a greeting message.

I'm struggling with the some code that looks somewhat like this:

pub struct A<I: Iterator> {
    s: I,
}
  
impl<I: Iterator> A<I> {
    pub fn new(s: &str) -> A<impl Iterator<Item = char> + '_> {
        A {
            s: s.chars()
        }
    }
}
  
  
fn main() {
    drop(A::new("").s);
}

As you can see, what I'm trying to achieve is defining A to be a struct that contains an iterator (in this particular case it would have worked as well either by removing the bounds or by explicating the associated type Item too). Then I'd use A::new to instanciate it.

The point is, rustc complains that

error[E0282]: type annotations needed
  --> src/main.rs:15:10
   |
15 |     drop(A::new("").s);
   |          ^^^^^^ cannot infer type of the type parameter `I` declared on the struct `A`
   |
help: consider specifying the generic argument
   |
15 |     drop(A::<I>::new("").s);
   |           +++++

For more information about this error, try `rustc --explain E0282`.

Of course, if I were to do what it suggests, everything would work:

// preceding code unchanged

fn main() {
    drop(A::<Chars>::new("").s);
}

But my iterator is more complex than a mere Chars, and I was hoping to remove the need to make the type explicit (since it would be infeasable, or at least, extremely incovenient).
Doesn't the compiler have all it needs to infere the type? Am I doing something wrong? thanks for your help.

The type of I is completely irrelevant in your impl, so you can put any old iterator in there and it will work.

This compiles fine, for example

drop(A::<std::iter::Empty<()>>::new("").s);

Playground


The root issue here is that impl<I: Iterator> A<I> declares that the caller of the methods in the impl block will be choosing the type I, but new doesn't actually use I anywhere. That means the compiler has no way to connect the dots between the return type of new and I.

Ideally you'd be able to specify the same type for A on the impl block, but I don't think that's currently possible on stable. You can do it with the nightly type_alias_impl_trait feature though.

Playground

#![feature(type_alias_impl_trait)]

pub struct A<I: Iterator> {
    s: I,
}

type NewIter<'a> = impl Iterator<Item = char> + 'a;

impl<'a> A<NewIter<'a>> {
    pub fn new(s: &'a str) -> Self {
        A { s: s.chars() }
    }
}

fn main() {
    drop(A::new("").s);
}

There's a simple stable fix too though, which is just to specify some concrete type for the impl block instead of using a type parameter. Since you weren't using I in the methods anyway, I is essentially just functioning as a namespace for the methods.

Playground

pub struct A<I> {
    s: I,
}

impl A<()> {
    pub fn new(s: &str) -> A<impl Iterator<Item = char> + '_> {
        A { s: s.chars() }
    }
}

fn main() {
    drop(A::new("").s);
}

(Note I removed the Iterator bound on the struct definition to be able to use () as the type there, you could also use one of the std iterator types if you really wanted to keep that bound.)

Now there's no additional type the caller needs to specify so the compiler infers A<()> on the new call without any additional hinting.

1 Like

It may be useful to think of return-position impl Trait (RPIT) as an output type of the method signature. The output type may depend on the input types and lifetimes [1] of the method. But for any set of inputs, there is exactly one output type. The output type is mostly opaque, but there's still just one underlying type.

Indeed, as Rust is statically typed, this holds true more generally: Given the set of input parameters, every function has a single output type.

In your OP, the type happens to be nameable -- it doesn't include a closure type or some other unnameable thing -- so we can actually get rid of the RPIT without using the unstable type alias impl Trait (TAIT) feature:

// Same as what you have in your OP, but no longer opaque
impl<I: Iterator> A<I> {
    pub fn new(s: &str) -> A<Chars<'_>> {

As you can see, it still has the same problem. But now that we can see the concrete types, the root issue that @semicoleon explained is more evident: The output type depends on the input lifetime attached to s [2], but it doesn't depend on I. Any I: Iterator will do, you'll still get back a A<Chars<'_>>.

When you call A::<I>::new, the compiler refuses to pick an arbitrary I, and hence the error.


Since in this case it doesn't matter, you might wonder why it doesn't pick an arbitrary I. And the answer is that you could make it matter without changing the API, for all the compiler knows. Maybe Iterator has some side-effect inducing associated functions you could call in the body of new, say. Then the choice of I would matter. [3]

This is especially true with RPIT, because the in-scope I is considered captured by the opaque type, even if you don't use it. (This way it's a non-breaking change if you do start using it.)


I do wonder though, did you really want A to be generic over the iterator type? If the iterator type is always the same, you don't need the I type parameter. However, you may have also ran into having an unnameable iterator type, e.g. if there's a closure involved.

If that's the case, instead of the generic I, you could use s: Box<dyn Itererator<...> + 'a> and be generic over just the lifetime.

Outside of that or similar tricks, this is a case TAIT is designed to fix: having a way to name types that we can't name today, so we can avoid boxing and type erasure and dyn-safety restrictions. But it is, sadly, still unstable.


  1. and const parameters, etc. ↩︎

  2. OK, this is only evident if you already understand lifetime elision ↩︎

  3. And if you say "but Iterator doesn't have those", it would also be a non-breaking change to add some. Limits on what the compiler infers guard against future breakage from otherwise innocuous changes. ↩︎

2 Likes