Why does the Index trait require returning a reference?

1

This question popped up in my mind as I was getting ready to write an index operator for something where I can't return a reference, and now it seems that I can't do so cleanly. (I just noticed that bit-vec used the workaround of returning pointers to private static variables which is hardly ideal.)
I read/skimmed through the following:

  • the reddit thread on the same question, and none of the comments seem to have answered my question satisfactorily;
  • the bug and the corresponding the RFC on splitting Index into multiple traits;

and I don't understand the rationale for making the output always a reference. For completeness, here's the Index trait:

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

(Also confusing is the fact that Idx can be unsized -- if so, how do you pass it in?)

As stated in one of the reddit comments, the trait could have been

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

and if a reference needed to be returned, the impl could be, eg:

impl<'a> Index<'a, usize> for Vec<u8> {
    type Output = &'a u8;
    fn index(&'a self, index: usize) -> Self::Output {
        // blah
    }
}

So what am I missing?

1 Like
2

I think there's a bug filed on this.

Such a trait works. It doesn't really have the semantics we want for the builtin Index trait, though. a[i] is translated to roughly *a.index(i), and that doesn't work unless indexing returns a reference.

3

Could you possibly elaborate on the desired semantics? Is the automatic dereferencing just for ergonomics in the case that we would want to return a reference (which is the common case for containers of non-Copy types)? Or is there a more fundamental limitation that I missed?

4

The idea is that array indexing should work the same way it does in C/C++: let x = a[i];, let x = &a[i];, let x = &mut a[i];, and a[i].x = 10; should have the obvious meanings.

5

Your impl is incorrect. You want:

impl Index<usize> for Vec<u8> {
    type Output<'x> = &'x u8;  // Not real syntax, doesn't work
    fn index for<'a>(&'a self, index: usize) -> Self::Output<'a> {
        // blah
    }
}

But this is inexpressible in Rust today, and then precludes being able to return values again! Actually, I don't think it will ever be possible to be generic over returns value, borrows self shared, and borrows self mutably. Generic code needs to know which of these will happen in order to correctly perform borrow-checking. If the trait doesn't expose these, it simply can't.

Further, this would expose no way for a single to type to have both a mutable and shared indexing (as eefriedman notes is desirable). Your usecase is handled by the IndexGet proposal: Extending deref/index with ownership transfer: DerefMove, IndexMove, IndexSet · Issue #997 · rust-lang/rfcs · GitHub

6

Is this different than having Index and IndexMut be different things? Seems like this is ultimately the desire for HKTs.