As I read the documentation for rust Vec, I want to understand how index operator [] works. For example, v[0] is a syntax sugar for *v.index(0) and how index is implemented? This leads me to Index trait implementation.

impl<T, I: SliceIndex<[T]>> Index<I> for Vec<T> {
    type Output = I::Output;

    #[inline]
    fn index(&self, index: I) -> &Self::Output {
        Index::index(&**self, index)
    }
}

There are many things happening in above code snippet. Let me elaborate.

Index Trait

pub trait Index<Idx>
where
    Idx: ?Sized,
{
    type Output: ?Sized;
    fn index(&self, index: Idx) -> &Self::Output;
}

Idx can potentially be an unsized type and being passed by value in above declaration. After discussion in rust forum, Rust compiler won’t check the declaration only until it sees definition.

  • declaration time: declaring generics and trait.
  • definition time: instantiating generics, define a function with body, non-generic struct/enum and trait/method implementation.
  • both: declaring and defining variables

Even though we know Idx type must be sized in order to be passed by value, the compiler doesn’t care it at generic declaration time. That’s reasonable, why force the compiler to think that far? The Idx type might not be any unsized type forever.

During a definition or implementation, if a trait-typed value is passed in, compiler will error out since unsized type can’t be passed by value. Check the comparison between trait type, trait object in my previous post.

The reason to declare this as ?Sized instead of strictly Sized is that it serves as a forward-compatible for unsized local. You can turn this feature on by adding #![feature(unsized_locals)]. See an example in playground.

Under this context, Idx: ?Sized is interpreted as any type is acceptable for this generic but no guarantee it can be instantiated without any errors.

Index::index: Universal Function Call Syntax

Universal Function Call Syntax, UFCS, is a desugared form of function call. The sugared form is (&**self).index(index), which is less readable since it doesn’t tell that this index is from Index<T> trait.

// *self -> Vec<T>
// **self -> [T]
// &**self -> &[T]

Thus, this index method is also from Index trait and it is defined in [T]:

impl<T, I> ops::Index<I> for [T]
where
    I: SliceIndex<[T]>,
{
    type Output = I::Output;

    #[inline]
    fn index(&self, index: I) -> &I::Output {
        index.index(self)
    }
}

Therefore, syntax Index::index means that it uses the index method from Index trait implementation for [T]. In this way, there may be other index methods for [T] but this unambiguously designates that the index method is from the implementation for Index trait and makes it more readable.

In the function body, it uses sugared form index.index(self) to refer to the method of an instance that implements SliceIndex<[T]>.

SliceIndex Trait

Let’s take vector indexing with usize index for example.

impl<T> SliceIndex<[T]> for usize {
    type Output = T;
    #[inline]
    fn index(self, slice: &[T]) -> &T {
        // N.B., use intrinsic indexing
        &(*slice)[self]
    }

As we can see, vec[8] is equivalent to *8usize.index(&vec).

#![feature(slice_index_methods)]

use std::slice::SliceIndex;
pub fn main() {
    let v = vec![1;10];
    println!("{}", *8usize.index(&v));
}

Run above code in playground.

Summary

Vec<T> indexing will redirect into indexing on [T], which also implements Index trait. Then [T] will delegate the indexing job to an instance that implements the SliceIndex<T> trait in order to index on slice type.

The chain is quite long and involves a lot of function calls. Fortunately, the whole chain is inlined (#[inline]) so that the overhead of extra storage for fat pointer &[T] can be negligible. Check more from my previous fat pointer blog.

Reference