Do we prepare to change `type Output` in the standard library to GAT?

Currently, we cannot return an immutable reference from a field of mutable reference type. For example, MyIntoIterator resembles to IntoIterator

	type T = form_arr_type!(i32 [1][2][3]);
	struct A<'a>(&'a mut i32);
	trait MyIntoIterator{
		type Item;
		fn next<'b>(&'b self)->Self::Item;
	}
	impl<'a> MyIntoIter for A<'a>{
		type Item = &'a i32;
		fn next<'b>(&'b self)->Self::Item{
			& *(*self).0  // #1
		}
	}

Assume the lifetime in #1 has lifetime 'l, there is a constraint that 'a : 'b : 'l, so we cannot return a reference &'l i32 to &'a i32. This is because we didn't have GAT priorly.

If we rewrite MyIntoIterator with GAT, we can do that this way:

	struct A<'a>(&'a mut i32);
	trait MyIntoIter{
		type Item<'b> where Self: 'b;
		fn next<'b>(&'b self)->Self::Item<'b>;
	}
	impl<'a> MyIntoIter for A<'a>{
		type Item<'b> = &'b i32 where Self: 'b;
		fn next<'b>(&'b self)->Self::Item<'b>{
			& *(*self).0
		}
	}

This is more powerful and flexible. Do we prepare to rewrite all these similar traits with GAT to make them more ergonomic?

3 Likes

This is commonly LendingIterator. AFAIK there are a few blocking issues for this to be added to the standard library though, mainly with regard to backward compatibility due to impl Iterator/impl/dyn Iterator<Item = T> being allowed with the assumption that the items won't borrow from the iterator. Moreover due to some borrow checker limitations (at least until we get Polonius) you can't write some basic iterator adapters with safe code, for example filter.

This kind of change as also been considered for other traits, mainly Deref/DerefMut and Index/IndexMut, but in those cases it's even more complicated due to method selection and the double trait versions (shared/exclusive)

2 Likes

"Rewriting" Iterator/Deref/Index/etc. is not in the cards and should not be. These traits represent interesting categories of behavior that you can do with things and changing Iterator to LendingIterator, although more general, makes it less useful. You can't collect a LendingIterator, for instance. Even if GATs had been in the language from the beginning, you would still want LendingIterator and Iterator to be different traits.

Future movement wrt GATs in the standard library (if any) will be more in the vein of "add LendingIterator and features that make it convenient to work with lending iterators" rather than "change Iterator so it can be lending".

3 Likes

I don't see why that would be the case. Would you mind explaining this point?

1 Like

A lending iterator's items may borrow from the iterator. Advancing the iterator mutates it. Therefore, you cannot keep an item and also advance the iterator (because that would be trying to take a mutable borrow while an immutable borrow exists), which is what collect() does repeatedly.

Of course, items could be transformed in a way which un-borrows them, e.g. .map(Clone::clone), to solve this problem in specific cases. Ideally the types are arranged so that if you do that, you can .collect(), but I don't know if that will be possible without further language extensions.

3 Likes

I think it's possible to have a middle ground, where Iterator keeps the same meaning it has always had, but code written to be compatible with any LendingIterator can also accept any Iterator with no extra work. I have an open RFC that goes partway toward making this possible.

2 Likes

I think if we ever get partial borrows, a bunch of lending iterator patterns would be compatible with yielding multiple items.

How would that work? In order to yield multiple items you would have to call next multiple time, but next will always be the same method and thus borrow the same values, doesn't matter if partially or fully they will still be the same and thus will conflict.

1 Like

IMO it is frustratingly close to working in current Rust.

fn main() {
    let mut it = ArrayLendingIterator {
        inner: vec![1, 2, 3],
        slice_start: 0,
    };

    // error[E0499]: cannot borrow `it` as mutable more than once at a time
    let first = it.next();
    //          --------- first mutable borrow occurs here
    let second = it.next();
    //           ^^^^^^^^^ second mutable borrow occurs here
    println!("{first:?}, {second:?}")
    //        --------- first borrow later used here
}

struct ArrayLendingIterator<T> {
    inner: Vec<T>,
    slice_start: usize,
}

impl<T> ArrayLendingIterator<T> {
    // It is impossible to express `'partial` in contemporary Rust
    fn next(&mut self) -> Option<&'partial T> {
        let Self {
            ref inner,
            ref mut slice_start,
        } = self;
        Self::next_impl(inner, slice_start)
    }

    fn next_impl<'c, 'n>(inner: &'n Vec<T>, slice_start: &'c mut usize) -> Option<&'n T> {
        let slice = &inner[*slice_start..];
        let next = slice.first();
        *slice_start += 1;
        next
    }
}

Within one function, current borrowchecker can understand what , to human eye, is the exact same pattern:

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