ExactSizeIterator for Range<char>

libs
1

Should we have it?

The obvious answer is yes. After all, Range<u32> is ExactSizeIterator and Range<char> is strictly smaller, so it should fit into ExactSizeIterator, right?

The reality is, as always, more complicated.

Strictly, Range<u32> should not be ExactSizeIterator, because (0..=u32::MAX).len() will overflow on 16 bit systems where usize = u16. The same argument applies to Range<char>, so, strictly, Range<char> should not be ExactSizeIterator.

The difference with Range<u32> is that it's been ExactSizeIterator since 1.0.0, so removing it would be breaking. With Range<char>, we can choose to do the "correct" thing, or the convenient thing pointing to the precident of u32.

(Note that this also applies to RangeInclusive<u16> and RangeInclusive<char>!)

Here's the relevant impl lines on docs (or permalinked on GitHub).

2

I don’t have a 16bit system at hand to check but judging by the source code in the standard library (AFAICT) it would actually panic and not overflow.

3

Does it use #[rustc_inherit_overflow_checks], Add::add, or neither of those and just +?

Because the standard library is always compiled in release mode, unless special effort is given to opt in to the "inherit overflow checks" hacks, arithmetic in the standard library is going to use the release profile of wrapping on overflow.

It'd be nice if someone could confirm the behavior here, though, as I don't really understand how these hacks work :upside_down_face:

The code comment explaining why the ExactSizeIterator impls are wrong and give the wrong result are originally @SimonSapin's, though they have my name on git blame IIRC.

4

It ultimately uses TryFrom<u32> for usize.

5

To elaborate: the ExactSizeIterator for Range<u32> comes from the range_exact_iter_impl macro which does

impl ExactSizeIterator for ops::Range<$t> { }

so it uses

    fn len(&self) -> usize {
        let (lower, upper) = self.size_hint();
        // Note: This assertion is overly defensive, but it checks the invariant
        // guaranteed by the trait. If this trait were rust-internal,
        // we could use debug_assert!; assert_eq! will check all Rust user
        // implementations too.
        assert_eq!(upper, Some(lower));
        lower
    }

The assert is what will cause the panic IMO. The size_hint comes from here:

impl<A: Step> Iterator for ops::Range<A> {
    type Item = A;
    // ...
    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        if self.start < self.end {
            let hint = Step::steps_between(&self.start, &self.end);
            (hint.unwrap_or(usize::MAX), hint)
        } else {
            (0, Some(0))
        }
    }
    // ...
}

Which uses the Step impl for u32:

#[cfg(target_pointer_width = "16")]
step_integer_impls! {
    narrower than or same width as usize: [u8 i8], [u16 i16], [usize isize];
    wider than usize: [u32 i32], [u64 i64], [u128 i128];
}

And this macro does (for the unsigned wider types like u32 on 16 bit):

                #[inline]
                fn steps_between(start: &Self, end: &Self) -> Option<usize> {
                    if *start <= *end {
                        usize::try_from(*end - *start).ok()
                    } else {
                        None
                    }
                }

So all-in-all for (0..u32::MAX).len() [you mistakenly used ..= which I just noticed] you need to calculate usize::try_from(u32::MAX-0) which is None and then assert that this None equals u32::MAX which it doesn’t.

6

I guess a panic is considered a wrong result for an ExactSizeIterator impl.

7

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.