Returning Proxies from Index/IndexMut

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.

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?

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).

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

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.

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.

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.

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?

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).

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.

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).

1 Like

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

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

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.

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

2 Likes

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.