Add `is_empty` function to `ExactSizeIterator`

Opened by Corey Farwell at 2022-03-22 02:30:03

Tracking issue for functionality introduced in https://github.com/rust-lang/rust/pull/34357

Added reference to this issue in https://github.com/rust-lang/rust/pull/35429
Corey Farwell at 2016-08-06 19:17:28
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?
Simon Sapin at 2016-10-17 16:30:14
@rfcbot fcp merge

Seems good to have consistency!
Alex Crichton at 2016-11-01 23:16:17
Team member @alexcrichton has proposed to merge this. The next step is review by the rest of the tagged teams:
- [x] @BurntSushi
- [x] @Kimundi
- [x] @alexcrichton
- [x] @aturon
- [x] @brson
- [x] @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.
Rust RFC bot at 2016-11-01 23:48:55
@SimonSapin I'm curious, when do you use ExactSizeIterator and have the opportunity to use this?
bluss at 2016-11-04 22:18:34
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
Simon Sapin at 2016-11-05 09:41:49
Aha, that explains it for me: using a specific iterator type, not using ESI generically. This method is good, reinforces existing conventions.
bluss at 2016-11-05 09:49:11
:bell: This is now entering its final comment period, as per the review above. :bell:

psst @alexcrichton, I wasn't able to add the final-comment-period label, please do so.
Rust RFC bot at 2016-11-12 01:11:25
The final comment period is now complete.
Rust RFC bot at 2016-11-22 01:38:49
used in PR #37943
bluss at 2016-11-22 22:40:53
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?
bluss at 2016-11-23 10:54:25
@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.)
Aaron Turon at 2016-12-15 18:12:29
I'm removing is_empty from the current stabilization PR, to give more time for discussion here.
Aaron Turon at 2016-12-15 18:18:22
- 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).
bluss at 2016-12-15 18:20:33
@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.
Aaron Turon at 2016-12-15 18:23:36
don't we have a backdoor for adding methods like this? trait Iterator has the method .rposition() where Self: DoubleEndedIterator
bluss at 2016-12-15 18:23:56
@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.
Aaron Turon at 2016-12-15 18:27:32
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.
bluss at 2016-12-15 19:12:06
Did the IsEmpty trait preempt the stabilization FCP?
Simon Sapin at 2017-03-09 09:50:58
@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.
Aaron Turon at 2017-03-13 20:07:16

I'd like to modify ESI to be something like this:

trait ExactSizeIterator : IsEmpty {
    fn len(&self) -> usize;
}

trait IsEmpty {
    fn is_empty(&self) -> bool;
}

impl<T> IsEmpty for T where T: ExactSizeIterator {
    default fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

specialization seems to implement this correctly, so I don't immediately see any problems with it. It doesn't resolve having the method in the prelude.

Iterator could get a new method:

pub trait Iterator {
    ...
    fn is_empty(&self) -> bool
        where Self: IsEmpty
    {
        IsEmpty::is_empty(self)
    }
}

which puts it in the prelude.

bluss at 2017-03-13 20:30:25

cc @rust-lang/libs, thoughts on @bluss's proposed change?

The overall motivation here is to allow for greater customization of is_empty, and to pass it through iterator adapters and the like.

Note that customization would currently only be allowed on nightly via specialization.
Aaron Turon at 2017-03-13 20:35:08
And so that chars() has the same is_empty even though it's not an ESI.
bluss at 2017-03-13 20:54:00
Given that is_empty was basically purely added for our len convention (where if you have len you have is_empty) I feel like blowing that up into an entire trait with specialization and new methods is way overkill.

If we can't stabilize it as is I would prefer to remove it as it doesn't seem to have strong enough motivation for a new trait and combinator.
Alex Crichton at 2017-03-14 21:41:50
Right, I don't think it's right to add an is_empty only for ESI, when it makes sense for a much larger class of iterators. I could see is_empty coming back in a new trait with an RFC, though.

@SimonSapin Thoughts? I thought you might weigh in on chars() and related iterators, if they should have is_empty() too.
bluss at 2017-03-14 21:50:54
An IsEmpty trait also seems slightly overkill to me, but I’m ok with it if other people want it.

I think it’s also fine to not have a dedicated trait but only a default method on ExactSizeIterator and an inherent method on str::Chars (and others as appropriate). Note that the latter is already possible through .as_str().is_empty().
Simon Sapin at 2017-03-14 23:01:34
Personally I think that is_empty as a convenience method here is useful; I've found myself directly checking is_empty on iterators sometimes and removing this method would be a bit of a pain.

Also, on the note of generic traits for is_empty, I've been slowly working on my len-trait crate and that may be of use to you, @bluss. In the future it may be worth having some sort of generalisation over these things in stdlib, but atm I'd honestly rather just have is_empty on ExactSizeIterator and deal with having the method duplicated over multiple traits if it comes down to it.
Clar Fon at 2017-04-09 04:40:14
I'm very much in favor of a separate IsEmpty trait as described by @bluss.

One solid use case of is_empty() is in a chess engine. They commonly use a Bitboard type that can be implemented as an exact size iterator of 64 bits that map to squares. len() would be implemented via count_ones() on a u64. However, is_empty() can be made faster by simply checking if the internal u64 is zero rather than checking if len() returns zero.
Nikolai Vazquez at 2017-05-04 19:49:06
@nvzqz Is this chess board type used in a generic context? If not you can make an inherent is_empty method, no need for a standard library trait.
Simon Sapin at 2017-05-11 18:13:45
IMHO is_empty cases are much better covered by peek than any generic trait. I'd rather just have this trait have an is_empty method.

If people want to have more generality they can use the len-trait crate I mentioned earlier. Based upon this discussion I did split out Empty and Len in that crate because it's for more niche cases.
Clar Fon at 2017-05-11 18:17:53
@SimonSapin While it currently isn't used internally in a generic context, I would like it so that an outside user can use the Bitboard as a generic iterator with an is_empty() method.
Nikolai Vazquez at 2017-05-11 23:20:16
As I said, you can easily implement is_empty for any iterator with peekable().peek().is_none()
Clar Fon at 2017-05-12 00:18:57
@clarcharr peek can cause side-effects (as suggested by mut), while len and is_empty are pure.
Andrea Canciani at 2017-05-12 11:00:10
@ranma42 huh, I never realised. that seems like a bug to me
Clar Fon at 2017-05-12 17:01:28
Does peek depend on next? If so, it makes sense to me for it to require mut.
Nikolai Vazquez at 2017-05-12 23:13:16
peek is a method of Peekable, an iterator wrapper that holds an Option<Self::Item> buffer. It does call next to fill that buffer if not filled already.
Simon Sapin at 2017-05-12 23:47:48
I mean, you could easily make peek immutable:
```
fn peekable(self) -> Peekable<Self> {
    Peekable {
        buffer: self.next(),
        iter: self,
    }
}
```
and
```
fn peek(&self) -> Option<&Self::Item> {
    self.buffer.as_ref()
}
fn next(&mut self) -> Option<Self::Item> {
    mem::replace(self.buffer, self.next())
}
```
Although I guess that this is a bit out of the scope of the general discussion.

My main point is that it's almost trivial to determine if an iterator is empty, and doesn't need a generic trait. We can deal with ExactSizeIterator just having an is_empty convenience method.
Clar Fon at 2017-05-13 17:07:34
While the Peekable solution can serve as a trivial default, I still think that any default should be able to be overridden with a possibly faster form like with my previous example where the internal u64 is 0.
Nikolai Vazquez at 2017-05-13 17:57:52
One thing that's unfortunate about is_empty being on ExactSizeIterator is that it would also make sense on TrustedLen. And their slightly-different requirements mean that either choice leaves out things that could have it easily -- Chain xor Skip can have it, if it's on only one of those two traits. And if it's on both, it'll be ambiguous on a whole bunch of common iterators...
scottmcm at 2017-05-24 07:16:46
Range::is_empty (https://github.com/rust-lang/rust/issues/48111) is another example of wanting the method on non-ESI.
scottmcm at 2018-02-20 02:26:35
The libs team discussed this and the consensus was to stabilize ExactSizeIterator as-is.

Iterator types that are not ExactSizeIterator but are still able to implement a meaningful is_empty method can do so in an inherent method. Code that needs to be generic over such types can define a non-standard-library trait.

@rfcbot fcp merge
Simon Sapin at 2018-03-28 12:22:41
Oops, it looks like rfcbot is not responding because a FCP was already completed in 2016. Anyone please make a stabilization PR, we’ll FCP there.
Simon Sapin at 2018-03-28 12:43:56
(is the rfcbot code in a repo somewhere? because I'd be willing to take a look at that)
Clar Fon at 2018-03-28 16:13:09
As far as a proper method goes, I think that perhaps an is_empty method could also be added to FusedIterator, and is_empty could be added to Fuse. Although I think the former is already stable, so, I'm not sure if we can do that...
Clar Fon at 2018-03-28 16:15:05
(rfcbot is at https://github.com/anp/rfcbot-rs/)
Simon Sapin at 2018-03-28 18:17:01
It still seems weird to have is_empty only for things that meet the "here to make rposition work" rules of ExactSizeIterator. There are so many things for which it's obvious that it could exist, like chain, but it won't. Having it here gets literally nothing over .len() == 0, which isn't even shorter than .is_empty(). And making a third-party trait for it would be painful at best, since ExactSizeIterator is in the prelude and thus trying to call it would be ambiguous with no nice workaround.
scottmcm at 2018-03-29 06:14:04
I can’t tell whether you’re arguing that is_empty is so important that it should have a dedicated trait, or that it’s unimportant enough that it doesn’t need to exist at all. We’re not adding a dedicated trait right now, but it or inherent methods on other iterators can still be proposed in a separate RFC or PR. As to .len() == 0, I think it’s less about character count than about clarifying intent. Collections (slices, maps) already have an is_empty method.
Simon Sapin at 2018-03-31 07:36:10
On top of being able to express intent with is_empty, it may be more optimal to call than .len() == 0. One case that comes to mind is a linked list iterator where is_empty is a constant time operation whereas len may take linear time.

I don't think is_empty should go on ExactSizeIterator, however. There may be iterators where the remaining number of elements is unknown, but it is known whether or not there are more elements left.
Nikolai Vazquez at 2018-03-31 15:18:36
@SimonSapin I'm arguing that is_empty is too useful to be restricted to only things (particularly adapters) that are ExactSizedIterator. (I agree that the clearer intent is valuable.) And I don't think "a dedicated trait" can be usefully added after this is stabilized, since it'd cause name conflicts with this one. I'd rather live with inherent methods and only-a-tiny-bit-worse .len() == 0 for now to keep from closing off a straight-forward path to having .is_empty() on things like Chain.

I don't think inherent methods are a great option for is_empty() either, since they disappear as soon as you .map() them. And there's no reason Map<RangeInclusive<usize>, _>, say, shouldn't have is_empty.
scottmcm at 2018-04-01 04:47:51
I think that putting it on FusedIterator would be best but that would require un-stabilising it after it's been in beta, when a release is around the corner.
Clar Fon at 2018-04-01 21:41:27
Triage: What's barring this from stabilization? It's been on nightly for... 6 months now, I think?
Phlosioneer at 2019-02-01 02:21:22
@Phlosioneer I don't think the situation has changed in the ~18 months since I wrote https://github.com/rust-lang/rust/issues/35428#issuecomment-303639055

(More than that, since the "this should be on things that are not ESI" predates that, like https://github.com/rust-lang/rust/issues/35428#issuecomment-286240343)

If you're looking at the labels, the finished-FCP is not for is_empty: https://github.com/rust-lang/rust/issues/35428#issuecomment-267400996
scottmcm at 2019-02-01 03:52:32
So we're not doing anything here because we haven't decided what to do about TrustedLen. And we haven't decided what to do about TrustedLen because no one has commented on it in 6 months.

Cross-referencing #37572

To your earlier comment: TrustedLen defines no methods. ExactSizeIterator defines len(). Everything else with a len() has a way to avoid len() == 0 by using is_empty() instead. TrustedLen will never have a len() or any similar method, because it can't be reduced to a usize by definition. I feel like there's no conflict of interest here between the two traits.
Phlosioneer at 2019-02-01 06:22:13
Also, we should fix the labels on this issue if they are incorrect. However, this issue is solely about stabilizing the is_empty function. The original call for RFC was specifically for is_empty. If we leave them as-is, this issue can easily be looked at as "If no one disagrees, is_empty will be merged." Particularly with the disposition-merge tag.
Phlosioneer at 2019-02-01 06:29:46
A thought: if is_empty() can always be defined as size_hint().1 == Some(0), then one could potentially do #[marker] trait IsEmpty: Iterator { fn is_empty(&self) -> bool { size_hint().1 == Some(0) } } and have blanket implementations for both ExactSizeIterators and TrustedLens.
scottmcm at 2019-05-31 07:48:30
I personally wish that is_empty were added to FusedItearator...
Clar Fon at 2019-05-31 13:44:26
@clarfon I don’t understand how these two things are related. For example std::iter::Filter<I, P> implements FusedIterator if I does, but cannot non-destructively determine whether the next call to next will return None.
Simon Sapin at 2019-05-31 15:11:09
What other functionality could a new trait have (related to is_empty) that would make it worth creating a dedicated trait that goes beyond the scope of just iterators? I feel that is_empty goes beyond just iterators, into types such as collections. And I've seen some discussion before about adding collection-related traits once GATs become a thing.
Nikolai Vazquez at 2019-06-03 19:06:28
@SimonSapin After rethinking it my original reasoning was flawed anyway. I was thinking that "emptiness" was mostly intrinsic to fused iterators only, but then realised that something like an I/O queue would not be fused, but could be empty. So, basically, ignore what I said.
Clar Fon at 2019-06-04 05:37:25
Over in https://github.com/rust-lang/rust/pull/61366#issuecomment-497671528, @SimonSapin asked for other possibilities, so here's something I tried out today: https://github.com/rust-lang/rust/compare/master...scottmcm:is_empty-alternative?expand=1

It moves is_empty to a new trait that depends on a size_hint being lower > 0 || upper == Some(0), which it implements automatically for ExactSizeIterator and TrustedLen. So one path forward here could be to stabilize the method but not the trait, which would allow people to start using the method (I put the trait in the prelude because its previous position on ESI was there). Then we could stabilize the trait once specialization stabilizes and other implementations wouldn't be blocked by coherence.

Thoughts?
scottmcm at 2019-07-08 06:00:26
Note that users can't make their own inherent is_empty method on their own types if they also want to implement ExactSizeIterator on them, any use triggers an "use of unstable library feature 'exact_size_is_empty'" error.
Anthony Ramine at 2019-07-23 08:16:54
I can’t reproduce this: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=cec84e30d1eedd6e5fa6933b4e1f8631 Did you mean something else?
Simon Sapin at 2019-07-23 08:41:20
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
Anthony Ramine at 2019-07-23 09:35:27
I assume it ends up calling <&mut Oops as ExactSizeIterator>::is_empty rather than Oops::is_empty or <Oops as ExactSizeIterator>::is_empty.
Anthony Ramine at 2019-07-23 09:38:37
Ah that’s a good point, presumably through impl<I: Iterator + ?Sized> Iterator for &mut I.
Simon Sapin at 2019-07-23 11:59:42
@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?
Anthony Ramine at 2019-07-30 13:44:43
@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.
gin-ahirsch at 2020-01-16 12:05:45

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>`

Behnam Esfahbod at 2020-09-27 23:06:23

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.
scottmcm at 2020-09-28 05:21:59
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
Veeti Haapsamo at 2022-03-21 18:27:51
@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.
scottmcm at 2022-03-21 18:41:14
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.
Clar Fon at 2022-03-21 19:08:19
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.
Clar Fon at 2022-03-22 02:29:55