Extending `core::ops::Index` to return non-references #2

shepmaster · 2022-01-25T20:31:30Z

Motivation

There are times where "indexing" is desired but returning a literal reference is suboptimal or impossible.

@cuviper said (lightly edited by me):

For example, ndarray would want to return ArrayView<'_, ..>. For mutable indexing, it would want ArrayViewMut<'_, ..>. GAT indexing would need a distinct type Output<'_> [for each mutability]. Currently, without GAT, they use slice and slice_mut methods.

We recognize that this requires GATs and something else to be able to truly supplant core::ops::Index and the [] syntax.

Details

A concrete example of the problem:

#![feature(generic_associated_types)]

fn main() {
    let c = Container(42);
    // Nightly
    let w = c.index(());
    // Desired, strawman syntax
    let w = &c[()];
    w.hello();
}

struct Wrapper<'a>(&'a u8);

impl Wrapper<'_> {
    fn hello(&self) {
        eprintln!("Hello, {}", self.0);
    }
}

struct Container(u8);

impl Index<()> for Container {
    type Output<'a> = Wrapper<'a>;

    fn index(&self, index: ()) -> Self::Output<'_> {
        Wrapper(&self.0)
    }
}

pub trait Index<Idx>
where
    Idx: ?Sized,
{
    type Output<'a>: ?Sized
    where
        Self: 'a;

    fn index(&self, index: Idx) -> Self::Output<'_>;
}

References in the wild

Related traits

These traits might also conceptually benefit from similar ability:

Deref
Borrow

The text was updated successfully, but these errors were encountered:

danielhenrymantilla · 2022-01-25T20:51:50Z

"Moved" from #3:

Based on the "GAT motivation" discussion over Zulip, and more precisely, around this question (archive link for those not on Zulip); people have started pondering about the idea that traits representing some of our sugary operations, such as […]-indexing, or deref-coercions, could maybe be GAT-ified in some retro-compatible fashion, so that they not be required to necessarily yield & or &mut references respectively.

Motivation

Plenty of examples in that Zulip thread; but people can also provide some to this very GH "issue".

But to summarize the main ones:

custom (re-)borrowing (e.g., Pin<&mut _>) could be featured with a GAT-ified Deref{,Mut}), and more general borrowing (e.g., &mut pinned_box being able to coerce to pinned_box.as_mut());
custom indexing/slicing.
- without involving unsafe or other RefCast-like approaches;
- when the reference type does not necessarily have the layout of a Rust reference (e.g., more embedded data (could be solved by ptr_metadata), or FFI requirements).
- when other GAT APIs become widespread, and thus types such as <Ty as Trait>::Gat<'lt> become more common.

Questions:

What would exactly be the semantics of a GAT-ified operator such as Index{,Mut} (I suspect the same concerns apply to Deref{,Mut})?
```
indexable[idx]
```
is actually sugar for a *-dereference (to a place expression) of the &Index::Output or &mut Index::Output (depending on the kind of usage of the place), so the starting point of these traits is &indexable[idx] or &mut indexable[idx].

Wouldn't GAT-ifying this result in either:
- reversing the relationship;
- and/or having &indexable[idx] not yield a &T (and same for &mut).
  This last idea seems like the most likely solution? Maybe?
How could the change be made in a retro-compatible fashion? I suspect we'll need new traits, to be the really sugared ones, and have the current ones be subsets which blanketly implement the new ones.

SkiFire13 · 2022-01-25T21:09:59Z

and/or having &indexable[idx] not yield a &T (and same for &mut).

To be backward compatible indexable[idx] should still yield T though.

Also, currently indexable[idx].foo() desugars to either indexable.index(idx).foo() or indexable.index_mut(idx).foo() depending whether foo takes &self or &mut self. How would this work if the GATified Index and IndexMut allowed different associated types?

danielhenrymantilla · 2022-01-25T21:26:05Z

Yeah, that's a problem: even though one could add a "let's try both paths" heuristic there, it means that multiply-chained indexing operations ([][][][].method()) would end up exploring an exponentially big set of candidates 😬

cuviper · 2022-01-25T23:07:25Z

Ugh, that ambiguity is unfortunate. I fear that will affect all possible uses of GAT indexing, not just my example, because the type mutability is hidden. That is, if we had fn index(&self, ..) -> Self::Output<'_>, there's no mechanism to write the "same" return type in a mutable form for index_mut. (compared to the current &Output and &mut Output)

TennyZhuang · 2022-01-26T16:20:43Z

Another similar example may be BitVec.

nikomatsakis · 2022-01-31T15:01:44Z

Thanks for opening this. @jackh726 and I were discussing similar questions around lending iterator and thinking that, before stabilizing, it would be good for us to spell out our plans here (whatever they are).

…, r=Mark-Simulacrum Add `Iterator::map_windows` Tracking issue: rust-lang#87155. This is inherited from the old PR rust-lang#82413. Unlike rust-lang#82413, this PR implements the `MapWindows` to be lazy: only when pulling from the outer iterator, `.next()` of the inner iterator will be called. ## Implementaion Steps - [x] Implement `MapWindows` to keep the iterators' [*Laziness*](https://doc.rust-lang.org/std/iter/index.html#laziness) contract. - [x] Fix the known bug of memory access error. - [ ] Full specialization of iterator-related traits for `MapWindows`. - [x] `Iterator::size_hint`, - [x] ~`Iterator::count`~, - [x] `ExactSizeIterator` (when `I: ExactSizeIterator`), - [x] ~`TrustedLen` (when `I: TrustedLen`)~, - [x] `FusedIterator`, - [x] ~`Iterator::advance_by`~, - [x] ~`Iterator::nth`~, - [ ] ... - [ ] More tests and docs. ## Unresolved Questions: - [ ] Is there any more iterator-related traits should be specialized? - [ ] Is the double-space buffer worth? - [ ] Should there be `rmap_windows` or something else? - [ ] Taking GAT for consideration, should the mapper function be `FnMut(&[I::Item; N]) -> R` or something like `FnMut(ArrayView<'_, I::Item, N>) -> R`? Where `ArrayView` is mentioned in rust-lang/generic-associated-types-initiative#2. - It can save memory, only the same size as the array window is needed, - It is more efficient, which requires less data copies, - It is possibly compatible with the GATified version of `LendingIterator::windows`. - But it prevents the array pattern matching like `iter.map_windows(|_arr: [_; N]| ())`, unless we extend the array pattern to allow matching the `ArrayView`.

…Simulacrum Add `Iterator::map_windows` Tracking issue: #87155. This is inherited from the old PR #82413. Unlike #82413, this PR implements the `MapWindows` to be lazy: only when pulling from the outer iterator, `.next()` of the inner iterator will be called. ## Implementaion Steps - [x] Implement `MapWindows` to keep the iterators' [*Laziness*](https://doc.rust-lang.org/std/iter/index.html#laziness) contract. - [x] Fix the known bug of memory access error. - [ ] Full specialization of iterator-related traits for `MapWindows`. - [x] `Iterator::size_hint`, - [x] ~`Iterator::count`~, - [x] `ExactSizeIterator` (when `I: ExactSizeIterator`), - [x] ~`TrustedLen` (when `I: TrustedLen`)~, - [x] `FusedIterator`, - [x] ~`Iterator::advance_by`~, - [x] ~`Iterator::nth`~, - [ ] ... - [ ] More tests and docs. ## Unresolved Questions: - [ ] Is there any more iterator-related traits should be specialized? - [ ] Is the double-space buffer worth? - [ ] Should there be `rmap_windows` or something else? - [ ] Taking GAT for consideration, should the mapper function be `FnMut(&[I::Item; N]) -> R` or something like `FnMut(ArrayView<'_, I::Item, N>) -> R`? Where `ArrayView` is mentioned in rust-lang/generic-associated-types-initiative#2. - It can save memory, only the same size as the array window is needed, - It is more efficient, which requires less data copies, - It is possibly compatible with the GATified version of `LendingIterator::windows`. - But it prevents the array pattern matching like `iter.map_windows(|_arr: [_; N]| ())`, unless we extend the array pattern to allow matching the `ArrayView`.

danielhenrymantilla mentioned this issue Jan 25, 2022

Quid of sugared ops:: traits and GAT-ifying them #3

Closed

frank-king mentioned this issue Mar 7, 2022

Add Iterator::map_windows rust-lang/rust#94667

Merged

16 tasks

kirawi mentioned this issue Mar 15, 2022

Show git diff signs in gutter helix-editor/helix#1623

Closed

dtolnay mentioned this issue Feb 28, 2023

Tracking Issue for Iterator::map_windows (feature iter_map_windows) rust-lang/rust#87155

Open

10 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Extending `core::ops::Index` to return non-references #2

Extending `core::ops::Index` to return non-references #2

shepmaster commented Jan 25, 2022

danielhenrymantilla commented Jan 25, 2022

SkiFire13 commented Jan 25, 2022

danielhenrymantilla commented Jan 25, 2022

cuviper commented Jan 25, 2022

TennyZhuang commented Jan 26, 2022

nikomatsakis commented Jan 31, 2022

Extending core::ops::Index to return non-references #2

Extending core::ops::Index to return non-references #2

Comments

shepmaster commented Jan 25, 2022

Motivation

Details

References in the wild

Related traits

danielhenrymantilla commented Jan 25, 2022

Motivation

Questions:

SkiFire13 commented Jan 25, 2022

danielhenrymantilla commented Jan 25, 2022

cuviper commented Jan 25, 2022

TennyZhuang commented Jan 26, 2022

nikomatsakis commented Jan 31, 2022

Extending `core::ops::Index` to return non-references #2

Extending `core::ops::Index` to return non-references #2