6 ms·
In this example: fn foo(x: i32) -> Box<Iterator<Item = i32>> { let iter = vec![1, 2, 3] .into_iter() .map(|x| x + 1); if x %
by squiguy7 8y ago
In this example:
fn foo(x: i32) -> Box<Iterator<Item = i32>> {
let iter = vec![1, 2, 3]
.into_iter()
.map(|x| x + 1);
if x % 2 == 0 {
Box::new(iter.filter(|x| x % 2 == 0))
} else {
Box::new(iter)
}
}
Why is it that I can't return `impl Iterator<Item = i32>`? Doesn't the `Filter` type implement `Iterator` for the same associated type?
- wcrichton 8y agoThe guarantee of `impl Trait` is that if I want to call a trait method on the returned object, e.g. for iterators if I want to call `foo(0).next()`, then the function pointer will always be in the same place on the object in memory (static dispatch). By contrast, if I returned a boxed trait, then calling the trait method requires a dynamic lookup to find the method on the boxed object, and then jumping to that function (dynamic dispatch). In this example, `iter.map(..)` and `iter.filter(..)` return two different implementations of the Iterator trait, so dynamic dispatch is required. In general, if your function returns multiple possible implementations of a given trait, then the compiler cannot know where the trait methods will be statically, so it is impossible to do static dispatch. Since impl Trait wants to guarantee static dispatch, it requires that only one possible implementation of the trait be returned.
- naasking 8y agoI think your explanation of static and dynamic dispatch is either wrong, or incredibly confusing. The offset of the function pointers is always statically known for a given trait/interface type, it's just the actual vtable instance that may not be known, ie. the concrete type implementing that trait/interface. A statically known vtable instance that can be inlined/monomorphized is static dispatch, and if it's not known at compile-time it must be dynamically dispatched.
- deleted 8y ago[deleted]
- burntsushi 8y agoI don't understand what's so confusing about it. GP says "calling the trait method requires a dynamic lookup to find the method on the boxed object" It sounds like all you want to say is "calling the trait method requires a dynamic lookup to find [the vtable instance, which is then used to find] the method on the boxed object"
- naasking 8y agoThat's not the clarification I was making. For instance, I simply can't interpret this line from the original post as anything but incorrect: > then the function pointer will always be in the same place on the object in memory (static dispatch) As I said, static vs. dynamic dispatch is about knowledge of the vtable instance, not about the offset into the object or the vtable. All of the offsets are always known statically, it's merely what you're indexing into that may or may not be known statically. Maybe I'm being pedantic, but I've found that there's a lot of misunderstanding surrounding static vs. dynamic dispatch.
- burntsushi 8y agoI see. Makes sense. It might help to show what the representation in memory of a trait object is. (I'm assuming there's a type for it somewhere in rustc, but I don't know where offhand.)
- steveklabnik 8y agohttps://doc.rust-lang.org/stable/std/raw/struct.TraitObject.html https://doc.rust-lang.org/stable/std/raw/struct.TraitObject....
- tylerhou 8y agoI think because returning two different types requires dynamic dispatch when using the returned objects, which requires Box; if the function only returns one type then that type can be determined at runtime and further function calls can be implemented with static dispatch instead.
- the_mitsuhiko 8y agoRust could generate a bespoke internal proxy type.
- Rusky 8y agoThat would still require dynamic dispatch of some kind.
- the_mitsuhiko 8y agoBut it wouldn’t require a heap allocation.
- lmm 8y agoWhere is the proxy implementation going to go if not the heap?
- GolDDranks 8y agoThe proxy object would have statically known size (maximum of the size of the types it dispatches between, plus some metadata such as a vtable pointer or an enum discriminant). Now, because you know the size statically, you can store it in the stack.
- shepmaster 8y agoUntil then, we use `Either` (https://stackoverflow.com/a/50204370/155423 https://stackoverflow.com/a/50204370/155423)
- steveklabnik 8y agoThe mismatch isn’t about the associated type, it’s about the actual, underlying type. One is a Map and one is a Filter. It’s not possible to determine which is returned, so you inherently need dynamic dispatch. There is some discussion about it possibly being sugar for an anonymous enum in the future, but that’s not what it is right now.
- khuey 8y agoIs there an RFC for the anonymous enum thing? I would gladly write the implementation ... :D
- steveklabnik 8y agoI don’t believe so? I feel like there’s several internals discussions but no RFC yet.
- the8472 8y agothere's some discussion, but no RFC yet. https://github.com/rust-lang/rfcs/issues/2414 https://github.com/rust-lang/rfcs/issues/2414
- deleted 8y ago[deleted]
- Soft 8y agoMy understanding is that impl Iterator<Item = i32> in return position means that there is some single concrete type that implements the Iterator trait that we are simply not going to name. This way, the compiler can do dispatching statically. If different paths returned values with different types there wouldn't be just a single type that is known at compilation time. That is why the extra indirection via trait objects is required in the example.
- bluejekyll 8y agoI'll take a stab at explaining this in the way that I finally started grokking the issue (coming from the land of Java). In Rust (most languages), by default the compiler needs to set aside space on the stack for each return value. So it needs a constantly known size (and shape) to create the slot on the stack. You need to flip to dynamic dispatch, ie a pointer to an object (Java's default), that will be placed on the stack as a reference to the unknown size/shape of the thing at the end of the pointer when the size/shape is unknown. A pointer always has a constant size on the stack. In this example, `impl Trait` is just saying I want the compiler to figure out the size/shape of the thing being returned for me, and allocate that to the stack at the call site of the function. What this means is that even with `impl Trait` you must return a thing that has the same size/shape. Steve's answer mentions a common pattern used to create constant size/shape by using an enum for the wrapper type to return two different types on the stack from the function. The only other option is to put something with unknown size behind a pointer, ie Box<Trait> or &Trait, and thus pay the expense of dynamic dispatch.