Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Zip's __iterator_get_unchecked doesn't preserve side-effects #82303

Closed
SkiFire13 opened this issue Feb 19, 2021 · 6 comments
Closed

Zip's __iterator_get_unchecked doesn't preserve side-effects #82303

SkiFire13 opened this issue Feb 19, 2021 · 6 comments
Labels
C-bug Category: This is a bug.

Comments

@SkiFire13
Copy link
Contributor

I tried this code:

fn main() {
    let a = vec![String::new(), String::new()];
    let b = [()];
    
    let mut counter = 0;
    
    a.into_iter() 
        .map(|i| {
            counter += 1;
            i
        })
        .zip(&b)
        .zip(&b)
        .for_each(drop);
        
    assert_eq!(counter, 2);
    
    let a = vec![String::new(), String::new()];
    let b = [()];
    
    let mut counter = 0;
    
    a.iter()
        .map(|i| {
            counter += 1;
            i
        })
        .zip(&b)
        .zip(&b)
        .for_each(drop);
        
    assert_eq!(counter, 2); // this fails, even though it succeed in the non-specialized version
}

Playground link

I would expect the two iterators to behave the same, so either both asserts fail (actually the first should stop the program) or neither of them. Instead, the second iterator doesn't preserve side-effects. causing the second assert (and only that one) to fail.

I don't think there's a way to solve this without completly changing the TrustedRandomAccess trait to use some type level trickery to replace may_have_side_effect. I wonder if there's even a point to keep the simulated side effects in the specialized ZipImpl::next if it doesn't cover all cases.

@SkiFire13 SkiFire13 added the C-bug Category: This is a bug. label Feb 19, 2021
@the8472
Copy link
Member

the8472 commented Feb 21, 2021

I would expect the two iterators to behave the same

We could also update the documentation to clarify that next() might not always be called on empty iterators.

For example a valid implementation would be checking size_hint() before iterating and bailing out early in case the upper bound is 0. It should be permissible for safe code to make these kinds of checks, size_hint only can't be relied on to uphold unsafe contracts. Whether side-effects happen would then depend on the tightness of the hint bounds.

Note that this isn't specific to Zip. Another adapter wrapping zip could introduce this kind of behavior.

@the8472
Copy link
Member

the8472 commented Apr 2, 2021

In the meantime I have introduced some additional specializations relying on TrustedRandomAccess and I just realized that they all suffer from similar problems when a zip exists somewhere earlier in the iterator pipeline. I think that is fixable for those cases, but...

I wonder if there's even a point to keep the simulated side effects in the specialized ZipImpl::next if it doesn't cover all cases.

Indeed, I would be in favor of getting rid of it and rewording the documentation instead.

@the8472
Copy link
Member

the8472 commented Apr 2, 2021

Original discussion about side-effects: #33090 (comment)
And the PR implementing it for the first time: #37230

I don't find those to be particularly strong arguments, primarily concerns about consistency between default and specialized code.
As far as side-effects are concerned this consistency arguably does not exist in the first place given the the different ways iterators can be driven: counted loops vs. checking for next() == None. Only the latter triggers the side-effect behavior.

@steffahn
Copy link
Member

steffahn commented Jun 1, 2021

The documentation of Zip says

If either iterator returns None , next from the zipped iterator will return None . If the first iterator returns None , zip will short-circuit and next will not be called on the second iterator.

Which pretty clearly describes the behavior of Zip. Following this description one would not necessarily expect the first iterator not to be advanced just because the second iterator has size 0.

Edit: I suppose that’s exactly what #83791 tries to address.

matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Nov 27, 2021
…ntee, r=dtolnay

Weaken guarantee around advancing underlying iterators in zip

The current guarantee (introduced in rust-lang#52279) is too strong as it prevents adapters from exploiting knowledge about the iterator length and using counted loops for example because they would stop calling `next()` before it ever returned `None`. Additionally several nested zip iterators already fail to uphold this.

This does not yet remove any of the specialization code that tries (and sometimes fails) to uphold the guarantee for `next()`
because removing it would also affect `next_back()` in more surprising ways.

The intent is to be able to remove for example this branch

https://github.com/rust-lang/rust/blob/36bcf4069717b9dff90270d13b53a3b130329960/library/core/src/iter/adapters/zip.rs#L234-L243

or this test

https://github.com/rust-lang/rust/blob/36bcf4069717b9dff90270d13b53a3b130329960/library/core/tests/iter/adapters/zip.rs#L177-L188

Solves rust-lang#82303 by declaring it a non-issue.
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Nov 27, 2021
…ntee, r=dtolnay

Weaken guarantee around advancing underlying iterators in zip

The current guarantee (introduced in rust-lang#52279) is too strong as it prevents adapters from exploiting knowledge about the iterator length and using counted loops for example because they would stop calling `next()` before it ever returned `None`. Additionally several nested zip iterators already fail to uphold this.

This does not yet remove any of the specialization code that tries (and sometimes fails) to uphold the guarantee for `next()`
because removing it would also affect `next_back()` in more surprising ways.

The intent is to be able to remove for example this branch

https://github.com/rust-lang/rust/blob/36bcf4069717b9dff90270d13b53a3b130329960/library/core/src/iter/adapters/zip.rs#L234-L243

or this test

https://github.com/rust-lang/rust/blob/36bcf4069717b9dff90270d13b53a3b130329960/library/core/tests/iter/adapters/zip.rs#L177-L188

Solves rust-lang#82303 by declaring it a non-issue.
@the8472
Copy link
Member

the8472 commented Feb 21, 2022

I believe with #83791 merged this can be closed since it turns it into a non-promise

@Dylan-DPC
Copy link
Member

Closing this as this isn't promised.

@Dylan-DPC Dylan-DPC closed this as not planned Won't fix, can't repro, duplicate, stale May 9, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C-bug Category: This is a bug.
Projects
None yet
Development

No branches or pull requests

4 participants