From 5bb967a3de039830dcc453bb92d3b6a0b794684f Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Sat, 19 Mar 2011 15:27:19 +0000 Subject: Some boundary conditions in range. infix implicits to Integral and Fractional. As a bonus this patch knocked 10,000 long boxings off a specialized test. Who knew. Closes #4308, #4321, review by community. --- .../scala/collection/immutable/NumericRange.scala | 49 ++++++++++++++-------- src/library/scala/collection/immutable/Range.scala | 12 ++++-- src/library/scala/math/Fractional.scala | 7 ++++ src/library/scala/math/Integral.scala | 11 +++++ test/files/pos/implicit-infix-ops.scala | 16 +++++++ test/files/run/range.scala | 14 +++++++ test/files/specialized/fft.check | 2 +- 7 files changed, 88 insertions(+), 23 deletions(-) diff --git a/src/library/scala/collection/immutable/NumericRange.scala b/src/library/scala/collection/immutable/NumericRange.scala index 4db7d81fa8..e4b539f962 100644 --- a/src/library/scala/collection/immutable/NumericRange.scala +++ b/src/library/scala/collection/immutable/NumericRange.scala @@ -48,7 +48,8 @@ extends IndexedSeq[T] with Serializable { */ import num._ - private val numRangeElements: Int = + // See comment in Range for why this must be lazy. + private lazy val numRangeElements: Int = NumericRange.count(start, end, step, isInclusive) override def length = numRangeElements @@ -191,32 +192,44 @@ extends IndexedSeq[T] with Serializable { /** A companion object for numeric ranges. */ object NumericRange { + import Ordering.Implicits._ + import math.Integral.Implicits._ + /** Calculates the number of elements in a range given start, end, step, and * whether or not it is inclusive. Throws an exception if step == 0 or * the number of elements exceeds the maximum Int. */ def count[T: Integral](start: T, end: T, step: T, isInclusive: Boolean): Int = { - val num = implicitly[Integral[T]] - import num._ + val zero = implicitly[Integral[T]].zero + val upward = start < end + val posStep = step > zero + + if (step == zero) throw new IllegalArgumentException("step cannot be 0.") + else if (start == end) if (isInclusive) 1 else 0 + else if (upward != posStep) 0 + else { + val jumps = ((end - start) / step).toLong + val remainder = ((end - start) % step).toLong + val longCount = jumps + ( + if (!isInclusive && zero == remainder) 0 else 1 + ) - if (step == zero) - throw new IllegalArgumentException("step cannot be 0.") + /** The edge cases keep coming. Since e.g. + * Long.MaxValue + 1 == Long.MinValue + * we do some more improbable seeming checks lest + * overflow turn up as an empty range. + */ + // The second condition contradicts an empty result. + val isOverflow = longCount == 0 && (start + step < end) == upward - val longCount: Long = - if (start == end) { if (isInclusive) 1 else 0 } - else if (end > start != step > zero) 0 - else { - val jumps = toLong((end - start) / step) - val remainder = toLong((end - start) % step) + if (longCount > scala.Int.MaxValue || longCount < 0L || isOverflow) { + val word = if (isInclusive) "to" else "until" + val descr = List(start, word, end, "by", step) mkString " " - if (!isInclusive && zero == remainder) jumps - else jumps + 1L + throw new IllegalArgumentException(descr + ": seqs cannot contain more than Int.MaxValue elements.") } - - if (longCount > scala.Int.MaxValue || longCount < 0L) - throw new IllegalArgumentException("Seqs cannot contain more than Int.MaxValue elements.") - - longCount.toInt + longCount.toInt + } } class Inclusive[T](start: T, end: T, step: T)(implicit num: Integral[T]) diff --git a/src/library/scala/collection/immutable/Range.scala b/src/library/scala/collection/immutable/Range.scala index 90a1383353..435959a645 100644 --- a/src/library/scala/collection/immutable/Range.scala +++ b/src/library/scala/collection/immutable/Range.scala @@ -46,10 +46,14 @@ extends IndexedSeq[Int] { override def par = new ParRange(this) - // Note that this value is calculated eagerly intentionally: it also - // serves to enforce conditions (step != 0) && (length <= Int.MaxValue) - private val numRangeElements: Int = - Range.count(start, end, step, isInclusive) + // This member is designed to enforce conditions: + // (step != 0) && (length <= Int.MaxValue), + // but cannot be evaluated eagerly because we have a pattern where ranges + // are constructed like: "x to y by z" + // The "x to y" piece should not trigger an exception. So the calculation + // is delayed, which means it will not fail fast for those cases where failing + // was correct. + private lazy val numRangeElements: Int = Range.count(start, end, step, isInclusive) protected def copy(start: Int, end: Int, step: Int): Range = new Range(start, end, step) diff --git a/src/library/scala/math/Fractional.scala b/src/library/scala/math/Fractional.scala index c6a80d3ee6..de09b184e0 100644 --- a/src/library/scala/math/Fractional.scala +++ b/src/library/scala/math/Fractional.scala @@ -20,3 +20,10 @@ trait Fractional[T] extends Numeric[T] { override implicit def mkNumericOps(lhs: T): FractionalOps = new FractionalOps(lhs) } + +object Fractional { + trait ExtraImplicits { + implicit def infixFractionalOps[T](x: T)(implicit num: Fractional[T]): Fractional[T]#FractionalOps = new num.FractionalOps(x) + } + object Implicits extends ExtraImplicits +} \ No newline at end of file diff --git a/src/library/scala/math/Integral.scala b/src/library/scala/math/Integral.scala index 9c1deaea33..bb364a79b4 100644 --- a/src/library/scala/math/Integral.scala +++ b/src/library/scala/math/Integral.scala @@ -24,3 +24,14 @@ trait Integral[T] extends Numeric[T] { } override implicit def mkNumericOps(lhs: T): IntegralOps = new IntegralOps(lhs) } + +object Integral { + trait ExtraImplicits { + /** The regrettable design of Numeric/Integral/Fractional has them all + * bumping into one another when searching for this implicit, so they + * are exiled into their own companions. + */ + implicit def infixIntegralOps[T](x: T)(implicit num: Integral[T]): Integral[T]#IntegralOps = new num.IntegralOps(x) + } + object Implicits extends ExtraImplicits +} \ No newline at end of file diff --git a/test/files/pos/implicit-infix-ops.scala b/test/files/pos/implicit-infix-ops.scala index ef4512fa6b..66f3718e86 100644 --- a/test/files/pos/implicit-infix-ops.scala +++ b/test/files/pos/implicit-infix-ops.scala @@ -5,3 +5,19 @@ object Test { def f1[T: Numeric](x: T, y: T, z: T) = x + y + z def f2[T: Ordering](x: T, y: T, z: T) = if (x < y) (z > y) else (x < z) } + +object Int { + import Ordering.Implicits._ + import math.Integral.Implicits._ + + def f1[T: Integral](x: T, y: T, z: T) = (x + y + z) / z + def f2[T: Ordering](x: T, y: T, z: T) = if (x < y) (z > y) else (x < z) +} + +object Frac { + import Ordering.Implicits._ + import math.Fractional.Implicits._ + + def f1[T: Fractional](x: T, y: T, z: T) = (x + y + z) / z + def f2[T: Ordering](x: T, y: T, z: T) = if (x < y) (z > y) else (x < z) +} \ No newline at end of file diff --git a/test/files/run/range.scala b/test/files/run/range.scala index 31d90f2d6d..2dc0bae330 100644 --- a/test/files/run/range.scala +++ b/test/files/run/range.scala @@ -7,6 +7,17 @@ object Test { assert(buffer.toList == range.iterator.toList, buffer.toList+"/"+range.iterator.toList) } + def boundaryTests() = { + // #4321 + assert((Int.MinValue to Int.MaxValue by Int.MaxValue).size == 3) + // #4308 + val caught = ( + try { (Long.MinValue to Long.MaxValue).sum ; false } + catch { case _: IllegalArgumentException => true } + ) + assert(caught) + } + case class GR[T](val x: T)(implicit val num: Integral[T]) { import num._ @@ -54,5 +65,8 @@ object Test { rangeForeach(10 until 1 by -1); rangeForeach(10 to 1 by -3); rangeForeach(10 until 1 by -3); + + // living on the edges + boundaryTests() } } diff --git a/test/files/specialized/fft.check b/test/files/specialized/fft.check index eb56a2a879..69a3a61f36 100644 --- a/test/files/specialized/fft.check +++ b/test/files/specialized/fft.check @@ -1,4 +1,4 @@ Processing 65536 items Boxed doubles: 0 Boxed ints: 2 -Boxed longs: 1442031 +Boxed longs: 1310921 -- cgit v1.2.3