Boundary issue in Range

[scabug]

The script

  def sum(xs: Iterable[Int]): Long = {
    var sum = 0L
    xs.foreach((x) => sum = sum + x)
    sum
  }

  println(sum(Integer.MAX_VALUE - 1 to Integer.MAX_VALUE))

returns 0 where as

  println(sum(List(Integer.MAX_VALUE - 1, Integer.MAX_VALUE)))

returns 4294967293. A helpful community member looked in Range and identified this

  val until = if (inInterval(end)) end + 1 else end

as the defect. We've reproduced it on Scala 2.7 and 2.8. Additional commentary is available at http://stackoverflow.com/questions/1635094

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-2535?orig=1
Reporter: Trenton Lipscomb (trenton)
Attachments:

• range.scala (created on Mar 2, 2010 11:11:36 PM UTC, 5321 bytes)
• Range.scala.2.diff (created on Feb 10, 2010 9:58:50 PM UTC, 5336 bytes)
• Range.scala.diff (created on Jan 30, 2010 2:40:25 AM UTC, 5277 bytes)

[scabug]

Trenton Lipscomb (trenton) said:
I should point out the bug is in the foreach method of Range.

[scabug]

@dcsobral said:
On the face of it it seems trivial to fix. If "end" is positive, substract one for the open range, leave the closed range alone, and use <= in the loop; if "end" is negative, add one for the open range, leave the closed range alone, and use >= in the loop.

Since we are subtracting from a positive or adding to a negative, we know there won't be an overflow.

[scabug]

@dcsobral said:
There are rather more problems than simply Int boundaries. The present implementation is very susceptible to int overflow and underflow, given arbitrary step values. I'm attaching both a test suit based on scalacheck, and a patch.

The patch is based on the idea of computing and keeping an Option of last. This means going through or testing for Option, which may introduce a small overhead on a few methods.

On the other hand, it removes an "if" statement from foreach (byOne ranges not-affected) which might well make them faster.

A possible optimization that was not pursued here might see the Range factory checking whether a Range has a "last" or not, and overriding the few methods affected by this with versions that make no checking at all.

I'll do some benchmarking later, and update this ticket with the results, unless some kind soul beat me to it. :-)

[scabug]

@dcsobral said:
Patch

[scabug]

@dcsobral said:
Alternate patch -- faster

[scabug]

@dcsobral said:
Ok, I did a mini-benchmark with this code:

def testRange(i: Int, j: Int, k: Int) = {
  var count = 0
  for {
    vi <- 0 to i
    vj <- 0 to j
    vk <- 0 to k
  } { count += 1 }
}

Then timed it with the following two settings:

testRange(10, 1000, 10000)
testRange(10000, 1000, 10)

Naturally, the former stresses foreach speed, while the latter stresses Range creation. I decided my original patch was too slow, so I have submitted another patch. This patch manages to be slightly faster than the original Range, by virtue of turning length from a lazy val into a def. I tried val too, but that was slower than either of the the other options.

[scabug]

@dcsobral said:
ScalaCheck tests for Range -- long running

[scabug]

@SethTisue said:
as dcsobral wrote on scala-internals, "at the very least there should be an exception when ranges are created with broken parameters"

[scabug]

@odersky said:
Since Eugene is gone, we need to reassign. Miguel maybe?

[scabug]

@axel22 said:
(In r21349) Fixes #2535. Review by community.

[scabug]

@dcsobral said:
I don't remember what's the review site, but I'm concerned about this:

final override def reverse: Range = if (length > 0) new Range.Inclusive(last, start, -step) else this 

I don't think there's any performance gain to be had by not creating the reverse of a zero-length range, so why change it from the original code that inverted end, start and negated step?

[scabug]

@axel22 said:
This is the reason:

scala> import collection.immutable.Range
import collection.immutable.Range

scala> import collection.immutable.Range._
import collection.immutable.Range._

scala> new Range(0, 0, 5)
res0: scala.collection.immutable.Range = Range()

scala> new Range.Inclusive(0, 0, -5)
res1: Range.Inclusive = Range(0)

[scabug]

@paulp said:
(In r22160) Discovered and disproved this unlikely truth:

scala> (1 to 1 drop 1) == (1 to 1)
res0: Boolean = true

It was introduced in r21349 which was to fix #2535, but led to #3529.
I humbly suggest we can't afford to introduce bugs of this severity
in the pursuit of corner cases such as Ranges which use Int.MaxValue
as a boundary. And looking at the patch I find the "after" code
a lot harder to follow. Closes #3529. Review by prokopec.

[scabug]

@dcsobral said:
It seems to me that locationAfterN should become locationAtN, thus preventing the integer wrap problems, and drop should use locationAtN + step -- if it wraps here, the result is still fine.

I'm disgusted (with myself) to find I did not test "drop" in the scalacheck tests. It was my intention to test all methods that were directly affected by the change, but somehow I missed drop.