Re: [PATCH v3] rust: alloc: implement `extend` for `Vec`

[Danilo Krummrich <dakr@kernel.org>]

On Wed, Apr 23, 2025 at 10:02:58AM +0900, Alexandre Courbot wrote:
> On Wed Apr 23, 2025 at 2:03 AM JST, Danilo Krummrich wrote:
> >> Well, that turned out to be an interesting rabbit hole.
> >> 
> >> Leveraging the existing traits seems a bit difficult:
> >> 
> >> - `ExactSizeIterator` cannot be implemented for adapters that increase the
> >>   length of their iterators, because if one of them is already `usize::MAX` long
> >>   then the size wouldn't be exact anymore. [1]
> >> 
> >> - And `TrustedLen` cannot be implemented for adapters that make an iterator
> >>   shorter, because if the iterator returns more than `usize::MAX` items (i.e.
> >>   has an upper bound set to `None`) then the adapter can't predict the actual
> >>   length. [2]
> >
> > Why is this a problem for the above implementation of Vec::extend()?
> >
> > I just looked it up and it seems that std [1] does the same thing. Do I miss
> > anything?
> >
> > [1] https://github.com/rust-lang/rust/blob/master/library/alloc/src/vec/spec_extend.rs#L25
> 
> The problem I see is that if you try and do something like:
> 
>   vec.extend((0..10).into_iter().skip(2));
> 
> with the standard library, then the use of `skip` will remove the
> `TrustedLen` implementation from the resulting iterator

Skip implements TrustedLen, no?

> and
> `extend_desugared` will be called instead of `extend_trusted`, which
> could add some unwanted (and unexpected) overhead.
> 
> If we want an implementation of `extend` as simple as "confidently
> increase the length of the vector and copy the new items into it, once",
> then we need a trait that can be implemented on both shrinking and
> extending adapters. Anything else and we might trick the caller into a
> code path less efficient than expected (i.e. my original version, which
> generates more core even for the obvious cases that are `extend_with`
> and `extend_from_slice`). Or if we rely on `TrustedLen` solely in the
> kernel, then `extend` could not be called at all with this particular
> iterator.

I think you can't solve all problems within this single function, since other
than std we don't have spcialization.

So, if we need both the fastpath and the slowpath it needs to be separate
methods unfortunately. I'd rather stick to the fastpath for now. Unless you have
a specific use-case for something else?

> There is also the fact that `TrustedLen` is behind a nightly feature,
> which I guess is another obstacle for using it.

Yeah, I think we have to implement our own TrustedLen trait for this reason and
add the corresponding impls. However, if we can come up with a marker trait that
deviates in requirements and guarantees from std, but is a better fit for the
kernel, I'm fine exploring this direction too.