Iterator.drop susceptible to arithmetic overflow

[noresttherein]

Reproduction steps

Scala version: 2.13.11

println(List(1).iterator.drop(1).drop(Int.MaxValue).toList)

Problem

prints

List(1)

[SethTisue]

@scala/collections

[yzia2000]

Yeah can see the arithmetic overflow happening with the Iterator. The drop function in Iterator is implemented using the SliceIterator which maintains a variable called dropping of type Int. So if we add 1 to it and then Int.MaxValue, it will overflow and cause no dropping to actually be done as highlighted.

  private[scala] final class SliceIterator[A](val underlying: Iterator[A], start: Int, limit: Int) extends AbstractIterator[A] {
    private[this] var remaining = limit
    private[this] var dropping  = start
...

    override protected def sliceIterator(from: Int, until: Int): Iterator[A] = {
      val lo = from max 0
      def adjustedBound =
        if (unbounded) -1
        else 0 max (remaining - lo)
      val rest =
        if (until < 0) adjustedBound          // respect current bound, if any
        else if (until <= lo) 0               // empty
        else if (unbounded) until - lo        // now finite
        else adjustedBound min (until - lo)   // keep lesser bound
      if (rest == 0) empty
      else {
        dropping += lo
        remaining = rest
        this
      }
    }
  }

If Iterators are only supposed to carry a maximum of Int.MaxValue elements (notice that variables like knownSize is of type Int). We can simply max the dropping variable:

dropping = max(Long.MaxValue, dropping + offset)

Another solution that I am not too keen on is changing dropping to type BigInt.

[He-Pin]

Welcome to the Ammonite Repl 2.4.0 (Scala 2.12.13 Java 1.8.0_341)
@ println(List(1).iterator.drop(1).drop(Int.MaxValue).toList)
List()

@

This works fine in 2.12, maybe better to run the tests against both versions. @SethTisue