nth_back() for Zip returns wrong values

[JohnTitor]

Assertions are successful in this code (playground):

let mut a = Vec::new();
let mut b = Vec::new();
let value = [1, 2, 3, 4, 5, 6]
    .iter()
    .cloned()
    .map(|n| {
        a.push(n);
        n * 10
    })
    .zip([2, 3, 4, 5, 6, 7, 8].iter().cloned().map(|n| {
        b.push(n * 100);
        n * 1000
    }))
    .nth_back(3);
assert_eq!(value, Some((30, 4000)));
assert_eq!(a, vec![6, 6, 5, 5, 4, 4, 3]);
assert_eq!(b, vec![800, 700, 700, 600, 600, 500, 500, 400]);

But later assertions are actually wrong (the second and third ones shouldn't double-count).
@matthewjasper pointed out it's a bug that exists in the current next_back implementation.

[timvermeulen]

a and b are obviously wrong, but value seems correct to me? The zip produces

[(10, 2000), (20, 3000), (30, 4000), (40, 5000), (50, 6000), (60, 7000)]

so nth_back(3) correctly produces (30, 4000).

[JohnTitor]

@timvermeulen Ah, my bad. Thanks for pointing out!

[timvermeulen]

The problem seems to be that the specialized version of Zip::next_back calls TrustedRandomAccess::get_unchecked(i) on both inner iterators here, which doesn't affect the len() of the inner iterators in any way. As a result, the next time next_back is called, next_back is called on both inner iterators here because their length now exceeds self.len by 1. So I think we probably need to call next_back on the inner iterators instead of get_unchecked. I'll check if this negatively affects benchmarks in any way.

To be honest, it's not really clear to me why Zip needs get_unchecked anyway (or why Zip has the index and len fields for that matter). From quickly reading the code, it seems like its main purpose is to make Zip::nth O(1) in case both inner iterators are known to not have side-effects, but in that case I think we could just call nth on the inner iterators instead? Maybe I'm missing something.

[spastorino]

This is really a libs-impl thing, fixing labels accordingly.

[nikomatsakis]

@timvermeulen did you ever experiment with the fix that it sounds like you had in mind here:

I'll check if this negatively affects benchmarks in any way.

[spastorino]

Removing nomination as it was discussed during today's weekly meeting.

[Dylan-DPC-zz]

Marking this as p-high as per the prioritization discussion

[timvermeulen]

@nikomatsakis Thanks for pinging me, I had completely forgotten about this. I remember going down a rabbit hole that eventually spawned #69187 — in a world where that compiled better, we might very well not need the index and len fields on Zip anymore (or, for that matter, a get_unchecked method that doesn't advance the iterator). But for now it looks like this issue is being taken care of.