Skip to content

Iterator::fuse is not guaranteed to fuse a generic iterator. #83969

Closed
@lcnr

Description

@lcnr
Contributor
struct S(bool);

impl Iterator for S {
    type Item = ();
    fn next(&mut self) -> Option<()> {
        self.0 = !self.0;
        if self.0 {
            Some(())
        } else {
            None
        }
    }
}

impl std::iter::FusedIterator for S {}

fn main() {
    let mut x = S(false).fuse();
    for _i in &mut x {}
    // x is fused, so it must be empty.
    assert_eq!(x.next(), None);
}

playground

This means unsafe code may not rely on iter.fuse() to actually fuse the iterator if iter is generic, which is unexpected to me.
I personally would like us to either add a note to Iterator::fuse mentioning this or to remove the specialization for std::iter::Fused.

Activity

changed the title [-]`Iterator::fuse` is not guaranteed to actually fuse the given iterator.[/-] [+]`Iterator::fuse` is not guaranteed to fuse a generic iterator.[/+] on Apr 7, 2021
added
T-libs-apiRelevant to the library API team, which will review and decide on the PR/issue.
on Apr 7, 2021
amorison

amorison commented on Apr 7, 2021

@amorison
Contributor

Well, by implementing std::iter::FusedIterator, you declare that S is already fused even though it isn't. You should remove the line impl std::iter::FusedIterator for S {} to get the expected behaviour. The only thing implementing FusedIterator on T does is tell Iterator::fuse that there is nothing to do because the type T is already fused. It doesn't fuse the iterator.

(As a side note, unsafe code should not blindly rely on safe code, especially traits implementation, precisely because it is impossible to automatically check that implementations are logically correct.)


EDIT : maybe I misunderstood your request, are you suggesting FusedIterator be deprecated and ignored by fuse because it can lead to fuse not working properly when wrongly implemented? That doesn't seem like a good idea to me, correct implementation of any trait is necessarily the burden of the user of that trait. Maybe the documentation could be more clear but it seems good to me as is to be honest.

ExpHP

ExpHP commented on Apr 9, 2021

@ExpHP
Contributor

Of course, the option of making the trait unsafe was discussed as part of the RFC, but it seems that the use case for the guarantees of Fuse in unsafe code were unclear at the time.

That said, I do kind of see how somebody might look of the signature of fuse:

pub fn fuse(self) -> Fuse<Self>

and think, "ah, this returns a standard library type, so I should be able to trust this on an arbitrary iterator," without considering that Fuse<I> uses specialization on a safe trait. Perhaps this merits a warning in the documentation. (Edit: Ah, this is precisely as you suggested!)

workingjubilee

workingjubilee commented on Apr 22, 2021

@workingjubilee
Member

I honestly imagine there is also a lot of unsafe code that relies on Eq implementations being correct for generic types, no? Is this different?

ExpHP

ExpHP commented on Apr 22, 2021

@ExpHP
Contributor

I honestly imagine there is also a lot of unsafe code that relies on Eq implementations being correct for generic types, no? Is this different?

I feel that there is a difference, due to way that specialization impacts this. The danger of reliance on safe traits in unsafe code is so omnipresent that I would hope that most people who audit unsafe code already look for things like bad Eq impls. I know that when I see T: Eq in an unsafe function, things that immediately come to mind are:

  • equality comparisons may violate the properties of Eq
  • equality comparisons may panic

On the other hand, if I were auditing unsafe code and saw a function take T: Iterator and call Iterator::fuse, I might think:

  • somebody could override the fuse method and use a different/modified instance of Self that returns different items.
  • somebody could override the fuse method and make it panic.
  • ...but since it returns std::iter::Fuse, I can see myself easily mistakenly thinking that, at the very least, the result is properly fused. I might not think of false FusedIterator implementations since that trait is not mentioned anywhere in the code or even in the docs of Iterator::fuse
amorison

amorison commented on Apr 23, 2021

@amorison
Contributor

I guess adding something along the line of

This method is a no-op on iterators that implement the FusedIterator trait. It may therefore behave incorrectly if this trait is improperly implemented.

in the doc of Iterator::fuse would be enough of a warning? Maybe a similar sentence in the doc of FusedIterator itself, but I feel like the current documentation is clear on the expected contract. If this sounds like a good idea, I could make a PR.

workingjubilee

workingjubilee commented on Apr 23, 2021

@workingjubilee
Member

Sounds good to me!

added a commit that references this issue on Apr 24, 2021

Rollup merge of rust-lang#84489 - amorison:issue-83969-fix, r=yaahc

ed991a3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    C-bugCategory: This is a bug.T-libs-apiRelevant to the library API team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      Participants

      @ExpHP@amorison@lcnr@workingjubilee

      Issue actions

        `Iterator::fuse` is not guaranteed to fuse a generic iterator. · Issue #83969 · rust-lang/rust