Implement ExactSizeIterator for `Zip<A, Repeat<B>> where A: ExactSizeIterator, B: Clone`

libs
1

This is a proposal to add two instances:

impl<A, B> ExactSizeIterator for Zip<A, Repeat<B>>
where
    A: ExactSizeIterator,
    B: Clone,
{
}

impl<A, B> ExactSizeIterator for Zip<Repeat<A>, B>
where
    A: Clone,
    B: ExactSizeIterator,
{
}

This would appear to be completely safe. .size_hint() will take the minimum of usize::MAX (from Repeat), and the other lower bound.

I've added these instances to core, and added this coretest:

#[test]
fn zip_repeat_bounds() {
    let iter = [1, 2, 3].into_iter().zip(repeat(2));
    let (lower, upper) = iter.size_hint();
    assert_eq!(lower, 3);
    assert_eq!(upper, Some(3));
    assert_eq!(iter.len(), 3);

    let iter = repeat(2).zip([1, 2, 3].into_iter());
    let (lower, upper) = iter.size_hint();
    assert_eq!(lower, 3);
    assert_eq!(upper, Some(3));
    assert_eq!(iter.len(), 3);
}

Which passes.

There is currently only one implementation of ExactSizeIterator for Zip:

impl<A, B> ExactSizeIterator for Zip<A, B>
where
    A: ExactSizeIterator,
    B: ExactSizeIterator {}

Which doesn't overlap with the proposed instances, as Repeat does not implement ExactSizeIterator.

If this seems sensible, I'll add a tracking issue, and PR the changes upstream.

2

You don't need a tracking issue for adding a new trait impl, as they are insta-stable. Just PR it

1 Like
3

Thanks, I was hoping that was the case.

4

Why can't Repeat be exact size? It is known to always be infinite after all.

5

What usize would you have .len() return for Repeat?

6

PR is up: Implement ExactSizeIterator for `Zip<A, Repeat<B>>` by 414owen · Pull Request #146642 · rust-lang/rust · GitHub

7

Ah, that is indeed a fair point. I only thought about size hint.

Edit: would adding a ExactInfinite trait make sense? Because the same logic could apply to other infinite iterators. Such as RepeatWith and probably several in the itertools crate.

8

Could yo remove “[Pre-RFC]” from the title since this thread does not (and should not) contain an RFC draft?

1 Like
9

Trait impls can be unstable now, actually! I haven't tried it out but I'm almost positive that was merged.

2 Likes
10

Yes. But this would require a language feature that allows marking InfiniteIterator and ExactSizeIterator as mutually exclusive traits.

4 Likes
11

For those interested in getting instances of ExactSizeIterator for exactly-limited infinite iterator sources, I have an ACP out, and would appreciate feedback (or just a :+1:, if you think this problem is worth solving): Generalize ExactSizeIterator to QuantifiedIterator · Issue #659 · rust-lang/libs-team · GitHub

tldr; in order to express the mutually exclusive traits, you can simply subsume both traits with one which can mark iterators as either infinite or exact (but not both, because it's an associated type, so can only be instantiated once per implementation).

2 Likes