Iterators in the std library should implement Eq where possible

[Valloric]

[Per discussion with @huonw on #rust.]

I've written a function apply like so:

type ParseState<'a> = Enumerate< Chars<'a> >;

struct ParseResult<'a> {
  value: Option< uint >,  // something more complicated in actual code
  parse_state: ParseState<'a>
}

fn apply<'a>( &self, parse_state: ParseState<'a> ) -> Option< ParseResult<'a> >

The idea is to parse the input and also return an iterator that's correctly advanced. I'm writing a test for this and Iterators not implementing Eq is making this more difficult than it needs to be.

[pongad]

How would you define two iterators to be equal?

[thestinger]

It's not actually going to be able to increment the iterators, because Eq uses &self.

[huonw]

@thestinger this is meant to be comparing the iterator state (where that makes sense), not the contents of the iterator. e.g. vec::Items would compare the two pointers, Zip would defer to the Eq of its two captured iterators, etc.

[thestinger]

That makes sense, but it may be a bit surprising. The only other place using identity-based equality is the raw pointer implementation of Eq.

[pongad]

@huonw Is it possible to compare two vec::Items? For two iterators to have to same state, it needs to come from the same vector right? You can't take out two iterators from the same vector at the same time. Am I missing something?

[huonw]

You can have two immutable iterators from one vector.

@thestinger true enough that it might be confusing.

[huonw]

(To be clear, by "immutable iterator" I mean the one yielding immutable references (&) as opposed to the one yielding &muts.)

[thestinger]

I don't think it makes sense to do this. The only real way to find out if two iterators are truly equal is to iterate through them. That's true even for the iterator returned by range, because different parameters can be used to create an iterator yielding the same values. Using address-based equality would be inconsistent with how things are done everywhere else. It's a subjective feature request to the core libraries so it really needs to go through the RFC process.

[aturon]

I disagree that adding an Eq instance would require an RFC, but this issue is basically a dupe of #15294

(That said, I agree that pointer-based equality does not seem like the right road to take here.)

[thestinger]

I suggested an RFC because I don't think people will agree with using shallow equality, but I can't speak for others. It can't really do anything but shallow equality since deep equality implies moving the iterator forwards.