Add is_empty function to ExactSizeIterator

[frewsxcv]

Tracking issue for functionality introduced in #34357

[frewsxcv]

Added reference to this issue in #35429

[SimonSapin]

I wanted to use this today until I realized that it’s unstable. (I could use .len() == 0 in the mean time.) Seems straightforward enough. FCP to stabilize?

[alexcrichton]

@rfcbot fcp merge

Seems good to have consistency!

[rfcbot]

Team member @alexcrichton has proposed to merge this. The next step is review by the rest of the tagged teams:

• @BurntSushi
• @Kimundi
• @alexcrichton
• @aturon
• @brson
• @sfackler

No concerns currently listed.

Once these reviewers reach consensus, this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[bluss]

@SimonSapin I'm curious, when do you use ExactSizeIterator and have the opportunity to use this?

[SimonSapin]

When using a slice or vec iterator as input for a parser, .is_empty() is a way to tell "have I reach the end of the input yet?" https://github.com/servo/html5ever/blob/b5c4552fab/macros/match_token.rs#L175

[bluss]

Aha, that explains it for me: using a specific iterator type, not using ESI generically. This method is good, reinforces existing conventions.

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

psst @alexcrichton, I wasn't able to add the final-comment-period label, please do so.

[rfcbot]

The final comment period is now complete.

[bluss]

used in PR #37943

[bluss]

Here's a thought: Some iterators can implement a good is_empty() even if they can't do ESI or .len(). One example is .chars(). Does it matter?

[aturon]

@bluss Sorry I missed your comment when prepping the stabilization PR.

My feeling is that these iterators can/should provide an inherent is_empty method if we think that's useful. The addition of the method to ExactSizeIterator is more about convenience than generic programming, IMO.

FWIW, it's also a longstanding desire on the lang side to have an API evolution path for splitting a trait into supertraits without breaking existing code. It's not guaranteed to happen, but that would allow us to split out is_empty into its own trait if we wanted to program generically with it in std in the future. (Of course, we can always add a separate trait with a blanket impl, worst case.)

[aturon]

I'm removing is_empty from the current stabilization PR, to give more time for discussion here.

[bluss]

• I think emptiness should be a trait, so that it can pass through adapters
• Iterators as lazy sequences have a different relationship to emptiness than collections, and the common chars() can already tell emptiness but not length; it's a common case in for example parsers (maybe not the most common, since byte-level parsing seems to be the most popular).

[aturon]

@bluss

Both points make sense. However, without further language improvements, it will be tricky to meet those goals and the original ergonomic goal at the same time.

Ideally, ExactSizeIterator would be a subtrait of IsEmpty and provide a default implementation of the is_empty method. To make this work, we'll need both specialization and the ability to implicitly impl supertraits when impl'ing a subtrait (an idea we've been kicking around on the lang team precisely to allow for this kind of API evolution).

Alternatively, we could add the IsEmpty trait to the prelude, along with a blanket impl from ExactSizeIterator. That comes with its own backwards-compatibility risks, though.

[bluss]

don't we have a backdoor for adding methods like this? trait Iterator has the method .rposition() where Self: DoubleEndedIterator

[aturon]

@bluss I may be missing something, but I don't see how that helps here. To clarify, the competing goals I see are:

• A separate IsEmpty trait that can be properly forwarded along adapters, and programmed over generically.
• Ergonomic access to is_empty for any ExactSizeIterator.

I don't offhand see how the trick you mention helps here; maybe you can spell it out?

It's worth noting that we could provide an is_empty method both in ExactSizeIterator and in a separate IsEmpty trait, with a blanket impl as well. But of course if you have both traits in scope at the same time, you'll have to explicitly disambiguate.

[bluss]

It's easier said than done, apparently. trait Iterator can get a new method, something like:

fn is_empty(&self) -> bool
    where Self: IsEmptyIterator;

which fixes the issue with having the method in the prelude.

But to arrange the right blanket implementations for IsEmptyIterator does not seem to be possible, even with the specialization features that are in nightly now.

[SimonSapin]

Did the IsEmpty trait preempt the stabilization FCP?

[aturon]

@SimonSapin Yes, this ended up getting pulled from the stabilization PR and has been sitting idle since then. Needs someone to drive it to a conclusion.

[SimonSapin]

I can’t reproduce this: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=cec84e30d1eedd6e5fa6933b4e1f8631 Did you mean something else?

[nox]

Ouch, it fails when the receiver of the call is a &mut.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=ed565c343e2fc196ea1e3dc4f2e54ad1

[nox]

I assume it ends up calling <&mut Oops as ExactSizeIterator>::is_empty rather than Oops::is_empty or <Oops as ExactSizeIterator>::is_empty.

[SimonSapin]

Ah that’s a good point, presumably through impl<I: Iterator + ?Sized> Iterator for &mut I.

[nox]

@scottmcm

Thoughts?

Can you imagine a scenario where you would want to have a trait bound on KnowsEmptyIterator but not ExactSizeIterator, and where you wouldn't be able to just call Iterator::next until a None is returned?

[gin-ahirsch]

@nox

Can you imagine a scenario where you would want to have a trait bound on KnowsEmptyIterator but not ExactSizeIterator, and where you wouldn't be able to just call Iterator::next until a None is returned?

In general, when an iterator is processed, but the last element needs to be handled differently. You can always get around this by buffering one element, e.g. using a Peekable<Iterator> instead of a plain Iterator, where is_empty() == peek().is_none().

In an application of mine for instance, I have a parser that scans log-files for various events and groups them into "runs" (i.e. events delimited by a start- and end-event). It is capable of detecting some instances of missing start- or end-events.
Usually logs are cut off at the start and the end, so there will virtually always be an initial missing start and a final missing end event. I have decided to make the parser emit a "complete" event chain, so it will output those "missing start/end" events for the first/last run.
I filter them out when e.g. writing the detected events to a file though, for which some tools exist to visualize the events. Since the user knows that the first and last runs are incomplete, having these is just noise.
To filter the last "missing stop"-event I need to know if I am processing the last run. I have implemented the function by accepting an Iterator<&Event>, so currently I wrap it in a Peekable as mentioned above. I don't really need to peek, it is just to check if it is the last run.
The fact that the parser emits only "complete" event chains is currently not used anywhere, so it's essentially an arbitrary decision which triggers the use-case, but I think it stands as an example. I'll concede that it may be too specific of a use-case, also because I have a functioning workaround.

[behnam]

Hi there,

Looks like it hasn't been mentioned on this issue (afaict), so sharing a tiny problem I noticed with the current non-stabilized is_empty() from ExactSizeIterator, in case it needs any action before stabilization.

For a simple type, such as:

pub type SomeRange = Range<usize>;

When std::iter::ExactSizeIterator is in scope, the following compile error happens when is_empty() used on a SomeRange value:

error[E0034]: multiple applicable items in scope
   |
   |         assert!(!some_range.is_empty());
   |                  ----^^^^^^^^--
   |                  |   |
   |                  |   multiple `is_empty` found
   |                  help: disambiguate the associated function for candidate #2: `std::iter::ExactSizeIterator::is_empty(&some_range)`
   |
   = note: candidate #1 is defined in an impl for the type `std::ops::Range<Idx>`
   = note: candidate #2 is defined in an impl of the trait `std::iter::ExactSizeIterator` for the type `std::ops::Range<usize>`

[scottmcm]

Good news: Range::is_empty() is stable in beta (#75132), so this no longer happens there, and will be fixed in stable on Oct 8th with 1.47.

[Walther]

Hello hi 👋 Kindest little boop & status check - what is the status of this? The docs seem to still say this is nightly-only, experimental https://doc.rust-lang.org/std/iter/trait.ExactSizeIterator.html#method.is_empty

[scottmcm]

@Walther I think the same "people want this on non-ExactSizedIterators" contention still applies, and thus I expect it to stay unstable until someone has a solution for that.

For now, .len() == 0 is often just as fast, so may suffice.

[clarfonthey]

An alternative for the not fast case would be to just use peekable, but that does use up space and most people would prefer it to be usable without taking up extra space.

Maybe a version like FusedIterator that makes Peekable fast might help?

EDIT: I actually really like this and might offer up a PR.

[clarfonthey]

So, I did the thing and offered up a PeekableIterator trait in #95195 as a potential path to an alternative. Feel free to put your thoughts there and whether you think this is a reasonable alternative or not.