Overflow/panic problem in Step and ExactSizeIterator for Range<BigInt>

[sellibitze]

In the trait Step we have the method

fn steps_between(start: &Self, end: &Self) -> Option<usize>;

which is supposed to handle the integer overflow case with None.

Range<Idx> comes with the following size_hint function in its Iterator<Idx> implementation:

fn size_hint(&self) -> (uint, Option<uint>) {
    if let Some(hint) = Step::steps_between(&self.start, &self.end) {
        (hint, Some(hint))
    } else {
        (0, None)
    }
}

which simply forwards a possible None. Range<Idx> also implements ExactSizeIterator. But consider what the default implementation of len in ExactSizeIterator will do if it has to deal with such a None:

fn len(&self) -> uint {
    let (lower, upper) = self.size_hint();
    assert_eq!(upper, Some(lower));
    lower
}

Clearly, this function does not expect an integer overflow. It will panic in such a case which will probably surprize some users that try to wrap things like BigInts into the Range.

I don't know how this should be handled. Perhaps using algebraic types a bit differently here would help (replacing None with Overflowed). Or perhaps we should only provide an ExactSizeIterator implementation if we can be sure that there won't be any integer overflows. This would imply an additional constraint for the Idx parameter in

impl<Idx: Clone + Step> ExactSizeIterator for Range<Idx> {}

cc @aturon @nick29581

[aturon]

Note: this will be resolved in #21258, which removes Step (in favor of direct, custom iterator implementations for e.g. bignums).