`ExactSizeIterator` and combinators

I'm looking at whether it's possible to implement ExactSizeIterator for more std::iter combinators. For an example of the problems with this, take the Chain<A, B> combinator returned by Iterator::chain. If A::len and B::len both return values of usize::MAX / 2 + 1, then despite each of them being bounded, their sum will overflow and return (usize::MAX, None) for the size_hint. TrustedLen makes this situation well-defined by relaxing the guarantees once the upper limit >= usize::MAX (we no longer can assume the exact length of the iterator). Does ExactSizeIterator have the same semantics?

It does not make any allowance for overflow. The default implementation of len will panic if the size_hint upper bound is None.

No. ExactSizeIterator can't be used on adaptors that make things longer (like Chain) and TrustedLen can't be used on adaptors that make things shorter (like Skip).

Why not?

Suppose iter1 has length usize::MAX + 1, and iter2 is infinite. Since TrustedLen requires an exact size_hint instead of a range, it would require iter1.skip(1).size_hint() == (usize::MAX, Some(usize::MAX)) and iter2.skip(1).size_hint() == (usize::MAX, None). But since iter1.size_hint() and iter2.size_hint() are both (usize::MAX, None), the Skip adapter has no way of distinguishing the two. Therefore, I: TrustedLen cannot imply Skip<I>: TrustedLen.

4 Likes