Surprising type inference on method call without explicit turbo-fish

[RSSchermer]

Please excuse the lack of specificity in the title, it reflects my lack of understanding what is going on here.

Here's a distilled example of what I'm going for:

trait FooMut {
    type Baz: 'static;

    fn bar<'a, I>(self, iterator: &'a I) where for <'b> &'b I: IntoIterator<Item= &'b &'a Self::Baz>;
}

struct DelegatingFooMut<T> where T: FooMut {
    delegate: T
}

impl<T> FooMut for DelegatingFooMut<T> where T: FooMut {
    type Baz = DelegatingBaz<T::Baz>;

    fn bar<'a, I>(self, collection: &'a I) where for <'b> &'b I: IntoIterator<Item= &'b &'a Self::Baz> {
        let collection = collection.into_iter().map(|b| &b.delegate);

        self.delegate.bar(&collection)
    }
}

struct DelegatingBaz<T> {
    delegate: T
}

(Play)

This fails to compile (on stable and nightly) with:

error[E0271]: type mismatch resolving `for<'b> <&'b I as std::iter::IntoIterator>::Item == &'b &<T as FooMut>::Baz`
  --> src/main.rs:17:23
   |
17 |         self.delegate.bar(&collection)
   |                       ^^^ expected struct `DelegatingBaz`, found associated type
   |
   = note: expected type `&&'a DelegatingBaz<<T as FooMut>::Baz>`
              found type `&&<T as FooMut>::Baz`

error[E0308]: mismatched types
  --> src/main.rs:17:27
   |
17 |         self.delegate.bar(&collection)
   |                           ^^^^^^^^^^^ expected type parameter, found struct `std::iter::Map`
   |
   = note: expected type `&I`
              found type `&std::iter::Map<<&I as std::iter::IntoIterator>::IntoIter, [closure@src/main.rs:15:53: 15:68]>`

I played around a bit and found that changing the bar implementation to the following does compile:

fn bar<'a, I>(self, collection: &'a I) where for <'b> &'b I: IntoIterator<Item= &'b &'a Self::Baz> {
    let collection: Vec<&<T as FooMut>::Baz> = collection.into_iter().map(|b| &b.delegate).collect();

    self.delegate.bar::<Vec<&<T as FooMut>::Baz>>(&collection)
}

(Play)

But only with the turbo-fish on the call to self.delegate.bar; if I remove the turbo-fish it once again fails to compile:

fn bar<'a, I>(self, collection: &'a I) where for <'b> &'b I: IntoIterator<Item= &'b &'a Self::Baz> {
    let collection: Vec<&<T as FooMut>::Baz> = collection.into_iter().map(|b| &b.delegate).collect();

    self.delegate.bar(&collection)
}

(Play)

This surprised me. From the error it seems like the compiler infers the type-parameter on the call to the delegate to be the same as the type parameter on the outer (delegating) method. I am not completely sure if this is a bug or intended behavior. If this isn't a bug I was hoping someone would perhaps be able to give me some insight into the what and why and a possible work-around.

While collecting into a Vec works as a workaround for now, I would really like to avoid having to allocate. I'm assuming that I might be able to make the original example work if I can work out a type for a turbo-fish there, but std::iter::Map seems to take the concrete type of its closure as a type parameter and I cannot figure out how to represent that in the turbo-fish type (if that's possible at all).

[csmoe]

It’s not a bug.

1. let collection = collection.into_iter().map(|b| &b.delegate);: If you want to create a collection for iterators, you need to collect them. map() is lazy, check out the documents about iter:;map for more info.
2. turbofish: https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.collect

[RSSchermer]

Thanks for the reply!

let collection = collection.into_iter().map(|b| &b.delegate);: If you want to create a collection for iterators, you need to collect them. map() is lazy, check out the documents about iter:;map for more info.

I don't necessarily want to create a collection. I don't understand why it should matter that map is lazy. It seems to me that the resulting Map value satifies the constraint I where for <'b> &'b I: IntoIterator<Item= &'b &'a Self::Baz> or does it not? In that case, why am I not able to pass it to the bar call on the delegate?

turbofish: https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.collect

I assume you're referring to the fact that collect needs a type hint, otherwise a concrete FromIterator type cannot be inferred. I am aware of this. However, I believe my problem is not with a turbofish on collect (the collect call works fine I think?), it's that I also need a turbofish on the bar call, otherwise it infers an incorrect(?) type.

I release I don't use turbofish notation to pass a type hint to the collect call in the examples above, instead I annotate the type on the variable declaration instead. If I change that to turbofish I get the same error:

fn bar<'a, I>(self, collection: &'a I) where for <'b> &'b I: IntoIterator<Item= &'b &'a Self::Baz> {
    let collection = collection.into_iter().map(|b| &b.delegate).collect::<Vec<&<T as FooMut>::Baz>>();

    self.delegate.bar(&collection)
}

(Play)

If I then also add the exact same turbofish to the bar call, it once again works:

fn bar<'a, I>(self, collection: &'a I) where for <'b> &'b I: IntoIterator<Item= &'b &'a Self::Baz> {
    let collection = collection.into_iter().map(|b| &b.delegate).collect::<Vec<&<T as FooMut>::Baz>>();

    self.delegate.bar::<Vec<&<T as FooMut>::Baz>>(&collection)
}

(Play)

I guess my question boils down to the following: why does that turbofish on the bar call matter? Should it matter or would this be a bug?

[ExpHP]

It seems to me that the resulting Map value satifies the constraint I where for <'b> &'b I: IntoIterator<Item= &'b &'a Self::Baz>

Well, the Map implements IntoIterator<Item=&'a Self::Baz> (if I'm reading it right).

&Map on the other hand doesn't implement IntoIterator, ever. Basically there's no way to turn an arbitrary iterator of values into an iterator of references without first collecting it into something that will outlive the full duration of iteration. At least, not currently, and not with Iterator.

(I do wonder if the "StreamingIterator" idea that would be enabled by generic associated types could support an adaptor that puts each value it receives from the wrapped iterator into an Option<T> field and loans out a temporary reference.)

&Vec does implement IntoIterator, because it can; all of the data is already backed by memory, and borrowing the vector guarantees that it outlives the entire process of iteration.

[RSSchermer]

Thanks @ExpHP, I understand now why my original approach does not work. I still don't quite understand why this version compiles:

fn bar<'a, I>(self, collection: &'a I) where for <'b> &'b I: IntoIterator<Item= &'b &'a Self::Baz> {
    let collection = collection.into_iter().map(|b| &b.delegate).collect::<Vec<&<T as FooMut>::Baz>>();

    self.delegate.bar::<Vec<&<T as FooMut>::Baz>>(&collection)
}

But this version does not:

fn bar<'a, I>(self, collection: &'a I) where for <'b> &'b I: IntoIterator<Item= &'b &'a Self::Baz> {
    let collection = collection.into_iter().map(|b| &b.delegate).collect::<Vec<&<T as FooMut>::Baz>>();

    self.delegate.bar(&collection)
}

However, this did allow me to work around my current problem.

[ExpHP]

Okay, that last example is super weird.

There is a known issue that type inference can be very aggressive with where bounds (which is more or less unfortunately by design), however I'm not sure if that's what's happening here.

What's really strange is that even just the following turbofish suffices:

fn bar<'a, I>(self, collection: &'a I) where for <'b> &'b I: IntoIterator<Item= &'b &'a Self::Baz> {
    // same as both examples in above post
    let collection = collection.into_iter().map(|b| &b.delegate).collect::<Vec<&<T as FooMut>::Baz>>();

    // shorter turbofish (infer the element type)
    self.delegate.bar::<Vec<_>>(&collection)
}

I guess just seeing Vec<_> makes the compiler kick some sense into itself and start considering things other than I.

[RSSchermer]

Should I reopen? I can also open a fresh issue that cuts out the intertwined &Map issue.

[ExpHP]

IMO nothing wrong with just reopening for now. I think the original post is fine.

[vitalyd]

It seems (I might be wrong) that type inference is using &Vec<...>: IntoIterator to determine the type. &Vec: IntoIterator adds another layer of references to the underlying type (ie &&T), and this appears to cause a failure. Telling it to use Vec: IntoIterator via turbofish sets it straight.

If possible, it might be easier to write bar as taking:

fn bar<'a, I>(self, collection: I) where I: IntoIterator<Item = &'a Self::Baz>

This would also let a Map (over a referenced Vec, say) through.

[vitalyd]

play for the above suggestion.

[RSSchermer]

Thanks a lot for the suggestion @vitalyd!

I ended up going with the following to solve my API's needs:

fn bar<'a, I, B>(self, collection: I) where I: IntoIterator<Item=B>, B: Borrow<&'a Self::Baz>

This seems to give me good range of valid values (the most notable for me: &[&T], Vec[&T], &Vec[&T] and a Map over any of these).

[vitalyd]

@RSSchermer, nice touch with Borrow for more flexibility!

I’d still love for someone to explain type inference’s behavior here.