Returning Proxies from Index/IndexMut

[matthieum]

Looking at the signature of Index and IndexMut, we note that the signature enforces that the returned type be &'a [mut] Return where only Result is customizable.

Given such a signature:

pub trait IndexMut<Index, Result> {
    fn index_mut(&'a mut self, index: &Index) -> &'a mut Result;
}

It seems infeasible to actually return proxies (and thus, to implement views).

For example, a silly example:

struct Matrix<T> {
    nb_lines: uint,
    nb_columns: uint,
    data: Vec<T>,
}

impl Matrix<T> {
    fn get<'a>(&'a self, line: uint, col: uint) -> &'a {
        self.data.get(line * self.nb_columns + col)
    }
}

struct LazilyTransposedMatrix<'a, T> {
    base: &'a Matrix<T>,
}

impl LazilyTransposedMatrix<'a, T> {
    fn get(&self, line: uint, col: uint) -> &'a T {
        self.base.get(col, line)
    }
}

Now, if I’d like to implement [] on my lazily transposed matrix, I cannot just return a reference, what I need is a proxy:

struct LazilyTransposedRow<'a, T> {
    base: &'a Matrix<T>,
    row_index: uint,
}

impl <'a, T> Index<uint, LazilyTransposedRow<'a, T>> for LazilyTransposedMatrix<T> {
    fn index(&'a self, index: uint) -> LazilyTransposedRow<'a, T> {
        LazilyTransposedRow { base: self, row_index: index }
    }
}

impl <'a, T> Index<uint, &'a T> for LazilyTransposedRow<'a, T> {
    fn index(&'a self, index: uint) -> &'a T {
        self.base.get(row_index, index)
    }
}

This looks (to me) like a typical example of views, however this will fail to compile because the signature of index will not match that of the trait. I looked for, but could not find, any rationalization for specifying the trait as it is, and thus was wondering whether I was missing something obvious or had just stumbled on an oversight.

Is there any reason not to make the trait more general ?

Note: this seems opposed to the design of iterators which were specifically made so that returning a view is possible.

[japaric]

@matthieum

Is there any reason not to make the trait more general ?

Is possible to implement a more general Index trait for, say, Vec<T>? I tried a few things but none of them worked:

// Attempt 1
trait Index2<I, R> {
    fn index2(&self, index: &I) -> R;
}

// error: cannot infer an appropriate lifetime for autoref due to
// conflicting requirements
impl<'a, T> Index2<uint, &'a T> for Vec<T> {
    fn index2(&self, index: &uint) -> &'a T {
        self.index(index)
    }
    // The fully typed signature is
    //     fn index2(self: &'s Self, index: &'i I) -> &'a T
    // The compiler doesn't know how 's and 'a are related
}

// Attempt 2
trait Index2<I, R> {
    fn index2<'a>(&'a self, index: &I) -> R;
    // This function declaration is equivalent to
    //     index2(&self, index: &I) -> R;
}

// error: method `index2` has an incompatible type for trait: expected
// concrete lifetime, but found bound lifetime parameter 'a
impl<'a, T> Index2<uint, &'a T> for Vec<T> {
    fn index2<'a>(&'a self, index: &uint) -> &'a T {
        unimplemented!()
    }
}

// Attempt 3 (RFC #192 a.k.a lifetime bounds)
trait Index2<I, R: 'a> {
    // R: 'a means that all the references contained in R must *outlive*
    // 'a, this is the *opposite* of what's required for the Vec case
    // For the Vec case, the lifetimes of the references in R must be equal
    // or *shorter* than 'a
    fn index2(&'a self, index: &I) -> R;
}

// Attempt 4 (Higher Kinder Type constructors?)
// R is a type constructor that takes a lifetime parameter as argument
trait Index2<I, R> {
    // This may work, but we don't have HKT (yet?)
    fn index2<'a>(&'a self, index: &I) -> R<'a>;
    // With this method, I think index2 *can't* return a Copy type like int
}

// Attempt 5 (Vec auto-slicing)
// Is not possible to implement the Index2 trait for Vec
trait Index2<I, R> {
    fn index2(&self, index: &I) -> R;
}

// Implement Index2 for a slice, and just use vec.as_slice().index2(i) everywhere
// If &Vec was automatically coerced to &'a [T], then we could also use vec.index2(i)
impl<'a, T> Index2<uint, &'a T> for &'a [T] {
    fn index2(&self, &index: &uint) -> &'a T {
        &self[index]
    }
}

It can't be done? Or am I overlooking something simple?

[shadowmint]

You can do some hacky things like:

struct Foo {
  x:Vec<u8>
}

struct FooView {
  foo:u8;
}

impl Index<uint, FooView> for Foo {
  fn index(&self, index:&uint) -> &FooView {
    unsafe {
      return transmute(&self.x[*index]);
    }
  }
}

(there may be some safe way of doing the same I’m not aware of? Not sure).

Anyway, this lets you return a ‘view’ with a specific offset, but since it can only contain a single pointer value you’re limited in what you can do with it depending on the parent structure.

Particularly for Vec like objects this doesn’t meaningfully help because it doesn’t provide a len. However, for c string buffers it works because any sub sequence of the data is terminated by a 0 byte.

Having a better index trait (index(&self, &index) -> Result) would be great; you could still implement Index of I, &T for existing behavior, but it would allow more complex Index operations (eg. allowing String to be indexable for a Grapheme instead of a pointer).

[matthieum]

I think that the most interesting is #3:

// Attempt 3 (RFC #192 a.k.a lifetime bounds)
trait Index2<I, R: 'a> {
    // R: 'a means that all the references contained in R must *outlive*
    // 'a, this is the *opposite* of what's required for the Vec case
    // For the Vec case, the lifetimes of the references in R must be equal
    // or *shorter* than 'a
    fn index2(&'a self, index: &I) -> R;
}

However indeed there is an issue with the specification of bounds on the type parameters; it seems that:

• for arguments, you want a “longer than” relationship
• for results, you want a “shorter than” relationship

but maybe an explicit syntax might be better. R: <'a and R: >'a ? Neither seems too satisfactory.

Is there no other place where we need to specify, generically, that the result’s lifetime should not exceed one of the parameters without assuming it is a reference ?

I tried to look at the Iterator interface but it circumvents the issue either by:

• passing self by value, thus having the result taking ownership (does not seem quite what I would want here)
• using a concrete type that is bound, circumventing the HKT issue

[japaric]

@matthieum

I think that the most interesting is #3:

Yeah, when I saw the RFC I thought it was going to solve some issues I encountered with lifetimes. But it seems my issues need a syntax that express the opposite of the R: 'a R outlives 'a relationship.

@matthieum

but maybe an explicit syntax might be better. R: <'a and R: >'a ? Neither seems too satisfactory.

The first thing that ocurred to me was: 'a: R as a syntax for the opposite relationship of R: 'a, but I'm not sure if that's parseable, and it looks odd because it reads as a lifetime parameter bounded by a type.

@matthieum

passing self by value

This is very useful, because you can use a reference like &'a Vec<T> as the Self parameter. In fact, that makes the Index2 trait implementable for Vec<T>:

trait Index2<I, R> {
    // Take `Self` by value
    fn index2(self, index: &I) -> R;
}

impl<'a, T> Index2<uint, &'a T> for &'a Vec<T> {
    // It works!
    fn index2(self, index: &uint) -> &'a T {
        self.index(index)
    }
}

The problem is that for sugary traits you get ambiguity. For example, if you implement Index2 for &'a Vec<T> and also for &'a mut Vec<T>, what is the expansion of vec[0]? Is it (&vec).index2(0) or (&mut vec).index2(0)? If the compiler can't disambiguate the sugar, then the user would have to explictly call (&mut vec)[0], which beats the purpose of having sugar at all!

Of course, is not a good idea to implement Index2 for both the reference and the mutable reference. But nothing stops the trait user from doing so. I think the type system should allow us to design traits that avoid these problems.

[rkjnsn]

Out of curiosity, if we were to go the route of using trait type parameters for input types only, and using associated type for output types, would that make devising a solution for this issue any easier?

[matthieum]

@japaric

This is very useful, because you can use a reference like &'a Vec<T> as the Self parameter. In fact, that makes the Index2 trait implementable for Vec<T>;

Bingo!

Using your approach for Index2 I can indeed get my Matrix off the ground:

struct Matrix<T> {
    lines: uint,
    columns: uint,
    data: Vec<T>,
}

struct Row<'a, T> {
    base: &'a Matrix<T>,
    index: uint,
}

impl<T: Copy> Matrix<T> {
    fn new(lines: uint, cols: uint, data: T) -> Matrix<T> {
        let cloner = |_: uint| -> T { data };
        Matrix{lines: lines, columns: cols, data: Vec::<T>::from_fn(lines * cols, cloner) }
    }
}

impl<T> Matrix<T> {
    fn get<'a>(&'a self, line: uint, col: uint) -> &'a T { return self.data.get(line * self.columns + col) }
}

trait Index2<I, R> {
    // Take `Self` by value
    fn index(self, index: I) -> R;
}

impl<'a, T> Index2<uint, Row<'a, T>> for &'a Matrix<T> {
    fn index(self, index: uint) -> Row<'a, T> { Row{ base: self, index: index } }
}

impl<'a, 'b, T> Index2<uint, &'b T> for &'a Row<'b, T> {
    fn index(self, index: uint) -> &'b T { self.base.get(self.index, index) }
}

fn main() {
    let matrix = Matrix::<int>::new(2, 4, 0);
    let row = matrix.index(1);
    println!("{}", row.index(2));
}

Using the playpen, it prints 0.

Note that Index2 is slightly modified:

trait Index2<I, R> {
    fn index(self, index: I) -> R;
}

I do not impose a reference on either parameters, letting the user choosing whether self and index should be passed by value or reference, which seems to be the more generic fashion.

However I am not sure of the usefulness of such a definition when it comes to using it as a generic (ie, using a T having Index2<I, R> as a bound).

[ahmedcharles]

I just bumped into this limitation of the standard Index and IndexMut traits and I guess I’m still not sure of why this restriction exists. It would be really nice to be able to support proxy types when using the [] syntax.

[withoutboats]

Perhaps if we had had associated type constructors, we would have defined Index like this:

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

But we didn’t have that feature then (and still don’t right now).

[declanvk]

@withoutboats Is it possible to revive this? I like your idea of associated type constructors, but could it also be achieved through some sort of lifetime bounds on the associated type?

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

I suppose it’s nearly the same thing. Any thoughts?

[declanvk]

I checked out the recent effort towards DerefMove/IndexMove which doesn’t quite cover this use case.

[DDOtten]

I would like to see something like this

trait Index<Idx: ?Sized> {
    type Output: ?Sized;
    type OutputRef<'a>: Deref<Target = Self::Output> = &'a Self::Output;
    fn index<'a>(&'a self, idx: Idx) -> Self::OutputRef<'a>;
}

trait IndexMut<Idx: Sized?>: Index<Idx> {
    type OutputMut<'a>: DerefMut<Target = Self::Output> = &'a mut Self::Output;
    fn index_mut<'a>(&'a self, idx: Idx) -> Self::OutputMut<'a>;
}

when we have associated type constructors but this would not be strictly backwards compatible because you can no longer rely on OutputRef to be a simple reference. However implementations of the trait and most uses of it would still work.

[kornel]

Custom DSTs could also help, where the extra data would be hidden in the fat pointer:

Custom DST Discussion

We recently postponed the custom DST RFC. But I wanted to continue the conversation both about its design and potential applications. If you’d like to catch up, read my most recent summary comment. Anyone, when we left it, @AtheMathmo and I were discussing trying to mock up how their library would look if implemented with this feature. I’m eager to hear the results. =)