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

["Alexandre Courbot" <acourbot@nvidia.com>]

On Wed Apr 23, 2025 at 6:47 PM JST, Danilo Krummrich wrote:
> 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?

According to TrustedLen's documentation it doesn't:

> This is why Skip<I> isn’t TrustedLen, even when I implements TrustedLen.

(https://doc.rust-lang.org/std/iter/trait.TrustedLen.html#when-shouldnt-an-adapter-be-trustedlen)

But if I look at the code for `Skip`, well sure enough it's there:

https://doc.rust-lang.org/src/core/iter/adapters/skip.rs.html#289

... with the caveat that `TrustedRandomAccess` must also be implemented.
Now that makes sense!

>
>> 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?

No, and that's also basically what I was suggesting with the
`ExactSizeCollectible` trait, something that works only for the fast
path. I don't think there is much use (if any) for the slow path in the
kernel anyway.

So I think the idea will be to introduce that `ExactSizeCollectible`
unsafe trait that would be a mix of `TrustedLen` and
`TrustedRandomAccess`. Then we can hand-pick all the iterator types and
adapters that should implement it.

Thanks for the fruitful discussion - I didn't know about the use of
specialization in the standard library.

Cheers,
Alex.