Scala Programming Language
  1. Scala Programming Language
  2. SI-4370

Range bug: Wrong result for Long.MinValue to Long.MaxValue by Int.MaxValue

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: Scala 2.11.0-M8
    • Component/s: Misc Library
    • Labels:
    • Environment:

      range yetanotherbuginrange long maxvalue minvalue

      Description

      === What steps will reproduce the problem? ===

      Long.MinValue to Long.MaxValue by Int.MaxValue
      

      === What is the expected behavior? ===
      (2*9223372036854775807)/2147483647 = 8589934596
      and 8589934596 > Int.MaxValue.

      It should be rejected, because it has more than Int.MaxValue elements.

      === What do you see instead? ===

      scala.collection.immutable.NumericRange[Long] = NumericRange(-9223372036854775808)
      

      === Additional information ===
      I think Paul is the expert here, see SI-4308 and SI-4321.

      === What versions of the following are you using? ===

      • Scala: 2.10.0.r24516-b20110320020044

        Activity

        Hide
        Simon Ochsenreither added a comment -

        I hope Paul doesn't hate me too much, but I fear it will get assigned to him anyways ... so forgive me, I'm just doing the inevitable here. :-/

        Is there some information on how to write tests? I would at least sit down and try to catch all the tricky stuff on the boundaries.

        Show
        Simon Ochsenreither added a comment - I hope Paul doesn't hate me too much, but I fear it will get assigned to him anyways ... so forgive me, I'm just doing the inevitable here. :-/ Is there some information on how to write tests? I would at least sit down and try to catch all the tricky stuff on the boundaries.
        Hide
        Paul Phillips added a comment -

        Replying to [comment:1 soc]:
        > Is there some information on how to write tests? I would at least sit down and try to catch all the tricky stuff on the boundaries.

        It's not difficult. Writing tests is by far the most useful thing you could do. Just look at the existing tests. Here are the ones which mention Range somehow.

        % ./partest --grep Range
        
        Testing individual files
        testing: [...]/files/pos/spec-cyclic.scala                            [  OK  ]
        
        Testing individual files
        testing: [...]/files/run/colltest.scala                               [  OK  ]
        testing: [...]/files/run/range.scala                                  [  OK  ]
        testing: [...]/files/run/concurrent-stream.scala                      [  OK  ]
        testing: [...]/files/run/pc-conversions.scala                         [  OK  ]
        testing: [...]/files/run/colltest1.scala                              [  OK  ]
        
        Testing individual files
        testing: [...]/files/jvm/serialization.scala                          [  OK  ]
        
        Testing individual files
        testing: [...]/files/scalacheck/range.scala                           [  OK  ]
        
        Show
        Paul Phillips added a comment - Replying to [comment:1 soc] : > Is there some information on how to write tests? I would at least sit down and try to catch all the tricky stuff on the boundaries. It's not difficult. Writing tests is by far the most useful thing you could do. Just look at the existing tests. Here are the ones which mention Range somehow. % ./partest --grep Range Testing individual files testing: [...]/files/pos/spec-cyclic.scala [ OK ] Testing individual files testing: [...]/files/run/colltest.scala [ OK ] testing: [...]/files/run/range.scala [ OK ] testing: [...]/files/run/concurrent-stream.scala [ OK ] testing: [...]/files/run/pc-conversions.scala [ OK ] testing: [...]/files/run/colltest1.scala [ OK ] Testing individual files testing: [...]/files/jvm/serialization.scala [ OK ] Testing individual files testing: [...]/files/scalacheck/range.scala [ OK ]
        Hide
        Simon Ochsenreither added a comment -

        Hi Paul.

        Some smaller additions to files/run/range.scala, new file is:

        import scala.collection.immutable.{ Range, NumericRange }
        
        object Test {
          def rangeForeach(range : Range) = {
            val buffer = new scala.collection.mutable.ListBuffer[Int];
            range.foreach(buffer += _);
            assert(buffer.toList == range.iterator.toList, buffer.toList+"/"+range.iterator.toList)
          }
          
          def boundaryTests() = {
            // SI-4321
            assert((Int.MinValue to Int.MaxValue by Int.MaxValue).size == 3)
            
            //Some "boundary" tests for BigInt.
            assert((BigInt(Long.MinValue) to BigInt(Long.MaxValue) by BigInt(Long.MaxValue)).size == 3)
            assert((BigInt(Long.MinValue) to BigInt(Long.MaxValue-1) by BigInt(Long.MaxValue)).size == 3)
            assert((BigInt(Long.MinValue) to BigInt(Long.MaxValue-2) by BigInt(Long.MaxValue)).size == 2)
            
            val biIntMinUpRanges = for(i <- -3 to 3) yield (BigInt(Int.MinValue)-i to BigInt(Int.MinValue))
            assert(biIntMinUpRanges.map(_.size).sum == 10)
            val biIntMaxUpRanges = for(i <- -3 to 3) yield (BigInt(Int.MaxValue)-i to BigInt(Int.MaxValue))
            assert(biIntMaxUpRanges.map(_.size).sum == 10)
            val biIntMinDownRanges = for(i <- -3 to 3) yield (BigInt(Int.MinValue) to BigInt(Int.MinValue)-i by -1)
            assert(biIntMinUpRanges.map(_.size).sum == 10)
            val biIntMaxDownRanges = for(i <- -3 to 3) yield (BigInt(Int.MaxValue) to BigInt(Int.MaxValue)-i by -1)
            assert(biIntMaxDownRanges.map(_.size).sum == 10)
        
            val biLongMinUpRanges = for(i <- -3 to 3) yield (BigInt(Long.MinValue)-i to BigInt(Long.MinValue))
            assert(biLongMinUpRanges.map(_.size).sum == 10)
            val biLongMaxUpRanges = for(i <- -3 to 3) yield (BigInt(Long.MaxValue)-i to BigInt(Long.MaxValue))
            assert(biLongMaxUpRanges.map(_.size).sum == 10)
            val biLongMinDownRanges = for(i <- -3 to 3) yield (BigInt(Long.MinValue) to BigInt(Long.MinValue)-i by -1)
            assert(biLongMinUpRanges.map(_.size).sum == 10)
            val biLongMaxDownRanges = for(i <- -3 to 3) yield (BigInt(Long.MaxValue) to BigInt(Long.MaxValue)-i by -1)
            assert(biLongMaxDownRanges.map(_.size).sum == 10)
        
            //Overflows. Source of errors.
            val intOverflowRange = (Int.MaxValue+1 to Int.MinValue)
            assert(intOverflowRange.size == 1)
            assert(intOverflowRange.head == Int.MinValue)
            val longOverflowRange = (Long.MaxValue+1 to Long.MinValue)
            assert(longOverflowRange.size == 1)
            assert(longOverflowRange.head == Long.MinValue)
        
            assert(((-7:Byte) to (7:Byte) by 2).size == 8)
        
            //The following ranges should fail.
            // SI-4308
            val range0 = Long.MinValue to Long.MaxValue
            // SI-4370
            val range1 = Long.MinValue to Long.MaxValue by Int.MaxValue
            val range2 = Long.MaxValue to Long.MinValue by -Int.MaxValue
            val range3 = BigInt(Int.MinValue) to BigInt(Int.MaxValue)
            val range4 = BigInt(Long.MinValue) to BigInt(Long.MaxValue)
        
            val failRanges = List(range0, range1, range2, range3, range4)
            failRanges.foreach(range => assert(exceptionThrown(range)))
        
            def exceptionThrown(range: IndexedSeq[_]) =
              try   { range.length; false }
              catch { case _: IllegalArgumentException => true }
          }
          
          case class GR[T](val x: T)(implicit val num: Integral[T]) {
            import num._
            
            def negated = GR[T](-x)
            
            def gr1 = NumericRange(x, x, x)
            def gr2 = NumericRange.inclusive(x, x, x)
            def gr3 = NumericRange(x, x * fromInt(10), x)
            def gr4 = NumericRange.inclusive(x, x * fromInt(10), x)
            def gr5 = gr3.toList ::: negated.gr3.toList
            
            def check = {
              assert(gr1.isEmpty && !gr2.isEmpty)
              assert(gr3.size == 9 && gr4.size == 10)      
              assert(gr5.sum == num.zero, gr5.toString)
              assert(!(gr3 contains (x * fromInt(10))))
              assert((gr4 contains (x * fromInt(10))))
            }
          }
          
          def main(args: Array[String]): Unit = {
            implicit val imp1 = Numeric.BigDecimalAsIfIntegral
            implicit val imp2 = Numeric.DoubleAsIfIntegral
            
            val _grs = List[GR[_]](
              GR(BigDecimal(5.0)),
              GR(BigInt(5)),
              GR(5L),
              GR(5.0d),
              GR(2.toByte)
            )
            val grs = _grs ::: (_grs map (_.negated))
            grs foreach (_.check)
            
            assert(NumericRange(1, 10, 1) sameElements (1 until 10))
            assert(NumericRange.inclusive(1, 10, 1) sameElements (1 to 10))
            assert(NumericRange.inclusive(1, 100, 3) sameElements (1 to 100 by 3))
            
            // SI-2518
            assert((3L to 7 by 2) sameElements List(3L, 5L, 7L))
            
            rangeForeach(1 to 10);
            rangeForeach(1 until 10);
            rangeForeach(10 to 1 by -1);
            rangeForeach(10 until 1 by -1);
            rangeForeach(10 to 1 by -3);
            rangeForeach(10 until 1 by -3);
            
            // living on the edges
            boundaryTests()
          }
        }
        

        (Two of them (range1, range2) will fail currently.)

        Show
        Simon Ochsenreither added a comment - Hi Paul. Some smaller additions to files/run/range.scala, new file is: import scala.collection.immutable.{ Range, NumericRange } object Test { def rangeForeach(range : Range) = { val buffer = new scala.collection.mutable.ListBuffer[Int]; range.foreach(buffer += _); assert(buffer.toList == range.iterator.toList, buffer.toList+"/"+range.iterator.toList) } def boundaryTests() = { // SI-4321 assert((Int.MinValue to Int.MaxValue by Int.MaxValue).size == 3) //Some "boundary" tests for BigInt. assert((BigInt(Long.MinValue) to BigInt(Long.MaxValue) by BigInt(Long.MaxValue)).size == 3) assert((BigInt(Long.MinValue) to BigInt(Long.MaxValue-1) by BigInt(Long.MaxValue)).size == 3) assert((BigInt(Long.MinValue) to BigInt(Long.MaxValue-2) by BigInt(Long.MaxValue)).size == 2) val biIntMinUpRanges = for(i <- -3 to 3) yield (BigInt(Int.MinValue)-i to BigInt(Int.MinValue)) assert(biIntMinUpRanges.map(_.size).sum == 10) val biIntMaxUpRanges = for(i <- -3 to 3) yield (BigInt(Int.MaxValue)-i to BigInt(Int.MaxValue)) assert(biIntMaxUpRanges.map(_.size).sum == 10) val biIntMinDownRanges = for(i <- -3 to 3) yield (BigInt(Int.MinValue) to BigInt(Int.MinValue)-i by -1) assert(biIntMinUpRanges.map(_.size).sum == 10) val biIntMaxDownRanges = for(i <- -3 to 3) yield (BigInt(Int.MaxValue) to BigInt(Int.MaxValue)-i by -1) assert(biIntMaxDownRanges.map(_.size).sum == 10) val biLongMinUpRanges = for(i <- -3 to 3) yield (BigInt(Long.MinValue)-i to BigInt(Long.MinValue)) assert(biLongMinUpRanges.map(_.size).sum == 10) val biLongMaxUpRanges = for(i <- -3 to 3) yield (BigInt(Long.MaxValue)-i to BigInt(Long.MaxValue)) assert(biLongMaxUpRanges.map(_.size).sum == 10) val biLongMinDownRanges = for(i <- -3 to 3) yield (BigInt(Long.MinValue) to BigInt(Long.MinValue)-i by -1) assert(biLongMinUpRanges.map(_.size).sum == 10) val biLongMaxDownRanges = for(i <- -3 to 3) yield (BigInt(Long.MaxValue) to BigInt(Long.MaxValue)-i by -1) assert(biLongMaxDownRanges.map(_.size).sum == 10) //Overflows. Source of errors. val intOverflowRange = (Int.MaxValue+1 to Int.MinValue) assert(intOverflowRange.size == 1) assert(intOverflowRange.head == Int.MinValue) val longOverflowRange = (Long.MaxValue+1 to Long.MinValue) assert(longOverflowRange.size == 1) assert(longOverflowRange.head == Long.MinValue) assert(((-7:Byte) to (7:Byte) by 2).size == 8) //The following ranges should fail. // SI-4308 val range0 = Long.MinValue to Long.MaxValue // SI-4370 val range1 = Long.MinValue to Long.MaxValue by Int.MaxValue val range2 = Long.MaxValue to Long.MinValue by -Int.MaxValue val range3 = BigInt(Int.MinValue) to BigInt(Int.MaxValue) val range4 = BigInt(Long.MinValue) to BigInt(Long.MaxValue) val failRanges = List(range0, range1, range2, range3, range4) failRanges.foreach(range => assert(exceptionThrown(range))) def exceptionThrown(range: IndexedSeq[_]) = try { range.length; false } catch { case _: IllegalArgumentException => true } } case class GR[T](val x: T)(implicit val num: Integral[T]) { import num._ def negated = GR[T](-x) def gr1 = NumericRange(x, x, x) def gr2 = NumericRange.inclusive(x, x, x) def gr3 = NumericRange(x, x * fromInt(10), x) def gr4 = NumericRange.inclusive(x, x * fromInt(10), x) def gr5 = gr3.toList ::: negated.gr3.toList def check = { assert(gr1.isEmpty && !gr2.isEmpty) assert(gr3.size == 9 && gr4.size == 10) assert(gr5.sum == num.zero, gr5.toString) assert(!(gr3 contains (x * fromInt(10)))) assert((gr4 contains (x * fromInt(10)))) } } def main(args: Array[String]): Unit = { implicit val imp1 = Numeric.BigDecimalAsIfIntegral implicit val imp2 = Numeric.DoubleAsIfIntegral val _grs = List[GR[_]]( GR(BigDecimal(5.0)), GR(BigInt(5)), GR(5L), GR(5.0d), GR(2.toByte) ) val grs = _grs ::: (_grs map (_.negated)) grs foreach (_.check) assert(NumericRange(1, 10, 1) sameElements (1 until 10)) assert(NumericRange.inclusive(1, 10, 1) sameElements (1 to 10)) assert(NumericRange.inclusive(1, 100, 3) sameElements (1 to 100 by 3)) // SI-2518 assert((3L to 7 by 2) sameElements List(3L, 5L, 7L)) rangeForeach(1 to 10); rangeForeach(1 until 10); rangeForeach(10 to 1 by -1); rangeForeach(10 until 1 by -1); rangeForeach(10 to 1 by -3); rangeForeach(10 until 1 by -3); // living on the edges boundaryTests() } } (Two of them (range1, range2) will fail currently.)
        Hide
        Adriaan Moors added a comment -

        Please submit a pull request.

        Show
        Adriaan Moors added a comment - Please submit a pull request.
        Show
        Adriaan Moors added a comment - https://github.com/scala/scala/pull/3319

          People

          • Assignee:
            Rex Kerr
            Reporter:
            Simon Ochsenreither
            TracCC:
            Simon Ochsenreither
          • Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development