Pre-RFC: Returning Proxies from Index/IndexMut

libs
1

There's a thread (now closed) about generalizing Index and IndexMut to return "view" types that aren't references. There's also a prior RFC which was declined for accidentally proposing a solution that breaks backwards compatibility.

Here, I'd like to discuss a potential non-breaking solution: adding new indexing trait which supersedes the old ones, while providing covering implementations for types that implement the old types. More concretely:

trait CoolIndex<'a, Idx: ?Sized> {
    type Output: ?Sized;
    fn cool_index(&'a self, index: Idx) -> Self::Output;
}

impl<'a, T> CoolIndex<'a, usize> for TypeWithView<T>
    where T: 'a
{
    type Output = View<'a, T>;
    
    fn cool_index(&'a self, index: usize) -> View<'a, T> {
        magic!()
    }
}

This is essentially copied from @CAD97's solution from the RFC, which is similar to @japaric's attempt #3 from 2014. Heres's a playground with a more complete definition plus examples.

For me, I have the following unanswered questions:

  • If we're parametrizing the trait with the lifetime 'a, are there any issues letting cool_index take ownership of self and instead implement CoolIndex<'a, _> for &'a Whatever?

    Update: I tried out something like this in the playground. Benefit: the one trait can be implemented for both &'a T and &'a mut T. Problem: we lose syntactic disambiguation via &_[_] vs &mut _[_] (and people would probably be surprised if something with & in the calling syntax could somehow take ownership of the referent).

  • Could someone give a more concrete example of how lifetime contravaiance in the returned "view" type causes problems? To me it looks like CoolIndex has a straightforward translation to Index, which would have the same lifetime issues if any.

1 Like
2

Note: Lifting the lifetime parameter to the trait level makes CoolIndex much harder to use esp. in generic code.

3

Given that we'd need to shim to a new Index trait anyway, I think this is worth waiting to get it right with GAT. Specifically,

#![feature(generic_associated_types)]

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

While raising the lifetime parameter to the trait level and even reusing the same trait for both shared and unique indexing is an interesting concept theoretically, the practical issues make just going with GAT a much more reasonable target.

6 Likes
4

If a new Index-like trait is being designed anyway, can we quickly mention what happens when indexing fails?

That is, I think the index method should return a Result<Self::Output<'_>, Self::Error> for some associated type Error. It is in fact the only thing that keeps me from using the current Index trait because it directly implies that a failed index operation leads to instant program death by panic.

5

That would require indexing to be fallible, which does not seem like a good choice (indeed its exactly the sort of overly narrow contract this proposal is trying to get away from). But you could define types which define output as (for example) Result<&'a T, Error>.

3 Likes
6

Would that really prevent a panic when doing something like my_indexable[my_indexable.len()]? Because a little inside voice tells me that that isn't the case simply by defining output to be Result<_, Error>. Instead, the Result element at that index won't be found, triggering an out of bounds panic.

So in that sense I don't see how it is better than the current Index trait?

7

If you use my NewIndex trait, you can have the current behavior for std slices:

impl<T> NewIndex<usize> for [T] {
    type Output<'a> = &'a T;
    fn index(&'_ self, idx: usize) -> &'_ T {
        self.get(idx).unwrap()
    }
}

And you can have fallible indexing:

impl<T> NewIndex<usize> for Checked([T]) {
    type Output<'a> = Option<&'a T>;
    fn index(&'_ self, idx: usize) -> Option<&'_ T> {
        self.get(idx)
    }
}

You choose between them with what type you use.

The problem, of course, is the magicalness of the Index trait. &var[idx] is translated into Index::index(&var, idx), &mut var[idx] is translated into IndexMut::index_mut(&mut var, idx), and var[idx] is translated to (IIUC, the rough equivalent of) *&var[idx].

When you have an index trait that returns a value that isn't a plain reference, this specific sugar doesn't work anymore. var[idx] "looks like" a move, &var[idx] "looks like" a reference to the place calculated by the indexing operation.

When &var[idx] returns a value that isn't a plain reference to the indexed place, the affordance offered by the syntax breaks down.

It's for this reason that while I think that the GAT Index is a cool idea and one that works in the type system, it doesn't work so well for indexing syntax.

Now, what about @jjpe's always fallible indexing?

trait NewIndex<Idx> {
    type Output; type Error;
    fn index(&'_ self, idx: Idx) -> Result<&'_ Output, Error>;
}

This retains the ability of current Index to "fudge" around with the output type. But... it would require lifting all of Result's possible operations into the syntax to determine how exactly to interpret the indexing.

// Simple case
&var[idx]?; // &((var[idx])?)
// Simple case
&var[idx].unwrap();
// Annoying case
var[idx].as_ref(); // Result<&Output, &Error> (?)
// Uh oh
&var[idx].unwrap_or_else(arbitrary_code);

Index[Mut] is super special because of their calling syntax and how it (doesn't directly) correlate to the function return types. The even more fun bit is that it even depends on typeck, not just syntax: var[idx].method_by_ref() is T::method_by_ref(Index::index(&var, idx)), var[idx].method_by_mut() is T::method_by_mut(IndexMut::index_mut(&mut var, idx)), and var[idx].method_by_move() is (IIUC, the rough equivalent of) T::method_by_move(*&var[idx]).

Because of this, I think any other type for Index will ruin the current affordance and nonproblematic usage. I'd love to be proven wrong, but I think any "NewIndex" will instead have to be a Get trait rather than reuse indexing syntax. I know this is suboptimal for no-panic development, but I can't think of any other signature that can be abused by the sugar the same way that the simple current one can.

4 Likes
8

I think we'd want a TryIndex trait if you want to generalize over get methods.

3 Likes
9

How about translating &var[idx] not to &(var.index(idx)), but to var.index_by_ref(idx)? It wouldn't be weirder than non-moving of &var[idx] is today.

With two different methods one could return Wrapper<T> or Wrapper<&T> as appropriate.

10

&var[idx] isn't translated to &(Index::index(&var, idx)). It's translated to Index::index(&var, idx). The introduced reference is "lost", and effectively it is your var.index_by_ref(idx), as var.index(idx)/Index::index(&var, idx).

The point I'm trying to convey is that &var[idx] evaluating to a type that isn't &_ is going to be surprising, and lose the affordance that the current syntax has.

On top of this, if [] doesn't always return T, &T, or &mut T, but instead, for example, returns Result<T, E>, Result<&T, E>, or Result<&mut T, E> based on usage, how do we actually define when what type is made available? How does this interact with method resolution?

Autoref works on var[idx] because it's a "place" computation; I think a purely syntactical expansion of indexing (if you ignore IndexMut for a moment) would work as *Index::index(&var, idx). That way, auto-ref or a literal take-ref operator just "re-establish" the reference to the place being indexed. A change to indexing to not just work with plain references, though convenient, would require deep changes to how indexing is lowered (beyond just changing the method called) and auto-ref/typeck/inference around any and all indexing operations.

As a final bit, the syntax for indexing isn't &var[idx] and &mut var[idx]; it's var[idx]. Whether indexing is done via Index::index or Index::index_mut is decided (by typeck?) by whether the indexing place is used by-move, by-shared-reference, or by-unique-reference. But crucially, the place itself is of a known type.

Because of the loose-binding of the reference-of operator &, I don't think anyone would like it if to use indexing the reference-of operator needed to be present rather than autoref magic just doing its thing. Then we'd have to have a lot of (&var[idx]).method() rather than just var[idx].method().

IMHO, wrapper types for indexing is a great idea/concept that falls apart once you try to stick it onto indexing syntax rather than method syntax. (In fact, this discussion has sent me back a good ways in language design for my toy language, as the previous concept of making indexing "just" a function call falls apart in the face of this same issue, just with different syntax (since I have the same shared/unique split).)

Disclaimer: all further discussion of affordances is theoretical and backed up by nothing but annecdotal evidence of my interactions with other developers, and my own intuition.

Sure, the affordance of indexing is basically based on how it works in other C-styled languages. But today, &var[idx] translates roughly to "take a reference of the place found by indexing var by idx". There's no affordance for a move involved; the intuition is that var[idx] is a "place" computation. (In fact, IIUC, this is (basically) true for current Rust.)

3 Likes
11

To state this differently: Index wants to pretend that lvalues have distinct types, like in C++. In C++, vec[5] produces a T&, while &vec[5] simply converts the lvalue of type T& into an rvalue representing its address (a T*). I mostly think that the C++ style of references is utterly insane, but it does result in a fairly straightforward meaning of operator&.

Rust's indexing operator is really C++'s operator-> (in terms of actual behavior) with an extra dynamic index paramter mixed in.

1 Like
12

I assume you actually mean with bounds checking on slices. No new API can change the behavior of indexing on slices, but you can define a new type which implements index and never panics if you want.

13

I mean, we shouldn't and definitely can't rationalize the change within the "small impact" rule, but purely technically, we probably would be able to change the desugaring of index syntax in an edition. (It's a language change, not a library one.)

(Transparency: I'm stealing this from @josh:

but my reaction to the idea of using editions to change syntax desugaring remains the same:

)

14

Let me clarify: we could maybe change the desugaring to use a different interface if we have a good transition story etc (it would be very challenging). What we can't do (because the impact would be far too large) is change the concrete signature of the index operator on std types (that is, indexing a slice must return T and panic on out of bound).

3 Likes
15

I still think Custom DST is the proper backward-compatible solution here rather than GATs, due to the problems pointed out by @CAD97. You place the view information into the metadata part of the DST.

Referring to the linked thread, we can define the output type as this collapsed block. 
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct ColumnMeta {
   stride: usize,
   len: usize,
}

// "treat `&Column<T>` like `(*const T, ColumnMeta)` ≈ `(*const T, usize, usize)`"
pub dyn type Column<T>(regular: ColumnMeta) = [T];

impl<T> dst::Regular for Column<T> {
    fn reduce_with_metadata(meta: ColumnMeta) -> usize {
        meta.len
    }
}

impl<T> Index<usize> for LazyTransposedMatrix<T> {
    type Output = Column<T>;
    fn index(&self, col_index: usize) -> &Self::Output {
        assert!(col_index < self.width);
        // urgh.
        unsafe {
            &*<*const Row<T>>::from_raw_parts(
                self.base.as_ptr().add(col_index),
                ColumnMeta {
                    stride: self.width,
                    len: self.width * (self.height - 1) + 1,
                },
            )
        }
    }
}

impl<T> Index<usize> for Column<T> {
    type Output = T;
    fn index(&self, row_index: usize) -> &Self::Output {
        let meta = ptr::metadata(self);
        let slice = dst::reduce(self);
        &slice[row_index * meta.stride]
    }
}
1 Like
16

We have std::ops::Deref exactly for this: trait Index<'a> { type Output: 'a + Deref<Output=_>; fn index(&' a self, arg: usize) -> Self::Output; }

1 Like
17

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