Trusted length trait for use in `Vec`

The problem

https://github.com/oxc-project/oxc/pull/9881#pullrequestreview-2699838278 revealed an annoyance we have with Vec.

Due to the lack of specialization in stable Rust, we can't make Vec::extend as optimal as it is in the standard library.

Std lib has an unsafe TrustedLen trait, which is implemented on Iterators which are guaranteed to report their length correctly via size_hint.

Vec::extend has a specialized implementation for Iterators which implement TrustedLen.

We can optimize common cases by using Vec::extend_from_slice, Vec::extend_from_array and Vec::append instead of Vec::extend, but there's some use cases not covered by these methods, where an iterator does have a guaranteed exact length, but we can't utilize that guarantee for optimization e.g.:

fn increment_and_extend<'a>(src: &[u64], dst: &mut Vec<'a, u64>) {
    let iter = src.into_iter().copied().map(|n| n + 1);
    dst.extend(iter);
}

That's a fairly common pattern (except the map closure would transform one AST node to another).

Vec::from_iter_in

The same problem also occurs with Vec::from_iter_in - it also cannot be optimized for some common cases, hence why we introduced Vec::from_array_in.

What we can't do

We cannot:

1. Make Vec::extend divert to a specialized implementation for trusted length iterators.
2. Make Vec::extend throw an error at compile time if called with a trusted length iterator, telling user to use a more optimized method.

What we can do: TrustedExactSizeIterator trait

We could define an additional unsafe trait:

/// Implementing this trait on an `Iterator` guarantees
/// that `ExactSizeIterator::len` reports the length accurately.
unsafe trait TrustedExactSizeIterator: std::iter::ExactSizeIterator {
    /// This default method can be overridden where the `Iterator` uses default implementation
    /// of `ExactSizeIterator::len` (which contains an assertion that's unnecessary in many cases)
    fn trusted_len(&self) -> usize {
        ExactSizeIterator::len(self)
    }
}

and a method on Vec which utilizes that trait:

impl<T> Vec<T> {
    pub fn extend_exact_len<I>(&mut self, iter: I)
    where:
        I: IntoIterator<Item = T>,
        I::IntoIter: TrustedExactSizeIterator,
    {
        let mut iter = iter.into_iter();

        // We can rely on `iter_len` being accurate
        let iter_len = iter.trusted_len();

        // After this, the `Vec` definitely has sufficient capacity for all the iterator's items
        self.reserve(iter_len);

        // No further bounds checks are required
        let mut ptr = unsafe { self.as_mut_ptr().add(self.len()) };
        while let Some(item) = iter.next() {
            ptr.write(item);
            ptr = unsafe { ptr.add(1) };
            // Because `Vec` guarantees `T` is not `Drop`, no need to increment `self.len`
            // on each turn of the loop to avoid memory leaks. Everything is "leaked" into the arena anyway.
        }

        // `self.len() + iter_len` cannot exceed `isize::MAX` or `self.reserve(iter_len)` would have panicked
        unsafe { self.set_len(self.len() + iter_len) }
    }
}

We implement TrustedExactSizeIterator on Iterators which have an exact length e.g.:

/// `Vec`'s `IntoIter` iterator always reports its length correctly
unsafe impl TrustedExactSizeIterator for oxc_allocator::vec::IntoIter {}

/// Slice iterators always report their length correctly
unsafe impl TrustedExactSizeIterator for std::slice::Iter {}

/// Array iterators always report their length correctly
unsafe impl TrustedExactSizeIterator for std::array::IntoIter {}

/// Map iterators maintain same length as their inner iterator
unsafe impl<I, F, B> TrustedExactSizeIterator for std::iter::Map<I, F>
where
    I: TrustedExactSizeIterator,
    F: FnMut(I::Item) -> B,
{}

/// ... etc ...

Other traits

It may also be useful to define other traits representing other guarantees:

• Length is minimum n.
• Length is maximum n.
• Length does not exceed isize::MAX.
• Iterator describes a slice (e.g. slice, but also slice.skip(1)).

What we can do: Macro

As mentioned above, we cannot make Vec::extend or Vec::from_iter_in specialize for the most efficient implementation, depending on the type of the iterator.

But we can do it in a macro using auto-ref specialization or auto-deref specialization tricks.

APIs would be:

extend!(vec, slice.map(map_fn));
vec_from_iter!(slice.map(map_fn), &allocator);

I'm not sure if we'd want to do this, as macros might increase compile times.

But, on positive side, it would make it possible for user to just write extend! or vec_from_iter!, and not worry about what the most efficient implementation is - the macro would select it automatically, and make sure the generated code is optimal.

What we can maybe do: Lint rule

Maybe there's a way to produce lint warnings where user uses Vec::extend where Vec::extend_exact_len would be more efficient (because the iterator implements TrustedExactSizeIterator). That would remove the need for a macro.

Start by reviewing the proposed TrustedExactSizeIterator API, the Vec::extend and Vec::from_iter_in use cases, and the existing oxc_allocator::vec::IntoIter implementation. Compare the trait, macro, and lint alternatives, then clarify which approach and supported iterator guarantees should be adopted; the issue currently does not define a single finished outcome.