Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
scabug opened this issue Mar 20, 2011 · 21 comments
Closed

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

scabug opened this issue Mar 20, 2011 · 21 comments
Assignees
Milestone

Comments

@scabug
Copy link

@scabug scabug commented Mar 20, 2011

=== 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 #4308 and #4321.

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

  • Scala: 2.10.0.r24516-b20110320020044
@scabug
Copy link
Author

@scabug scabug commented Mar 20, 2011

@scabug
Copy link
Author

@scabug scabug commented Mar 20, 2011

@soc said:
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.

@scabug
Copy link
Author

@scabug scabug commented Mar 20, 2011

@paulp said:
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  ]

@scabug
Copy link
Author

@scabug scabug commented Mar 22, 2011

@soc said:
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.)

@scabug
Copy link
Author

@scabug scabug commented Jun 11, 2012

@adriaanm said:
Please submit a pull request.

@scabug
Copy link
Author

@scabug scabug commented Jan 16, 2014

@scabug
Copy link
Author

@scabug scabug commented Apr 21, 2014

Daniel Darabos (darabos) said:
In Scala 2.10.3:

scala> 0.0 until 5.0 by 10.0
res0: scala.collection.immutable.NumericRange[Double] = NumericRange(0.0)
scala> 0.0 until 0.5 by 1.0
res1: scala.collection.immutable.NumericRange[Double] = NumericRange(0.0)

In Scala 2.11.0:

scala> 0.0 until 5.0 by 10.0
res0: scala.collection.immutable.NumericRange[Double] = NumericRange(0.0)
scala> 0.0 until 0.5 by 1.0
res1: scala.collection.immutable.NumericRange[Double] = NumericRange()

Is this change in behavior intended? It is due to the above pull request, and looks like a bug to me.

@scabug
Copy link
Author

@scabug scabug commented Apr 21, 2014

@Ichoran said:
The change in behavior is not intended.

Another one: 0.0 until 0.3 by 0.1 does not give the expected result.

@scabug
Copy link
Author

@scabug scabug commented Apr 21, 2014

Daniel Darabos (darabos) said:
I may have a fix for "0.0 until 0.3 by 0.1".

I'm trying to fix #8518. I've added a test for it, and have a fix. It also fixes "0.0 until 0.3 by 0.1". Perhaps someone can help me sort out the binary incompatibility warnings? The changes are in:
https://github.com/darabos/scala/commits/SI-8518

Should I send this as a pull request even if it is unfinished?

@scabug
Copy link
Author

@scabug scabug commented Apr 21, 2014

@Ichoran said:
It looks like the changes you are making can't go in 2.11 because they rely upon things that are not binary compatible (e.g. abstract class to private class), so this would be a fix for 2.12 at the earliest. I'd hold off submitting a PR against 2.11 until I have a go at fixing it in a binary-compatible way. I don't think we want range broken for the whole 2.11 series. I'll give it a try tomorrow.

@scabug
Copy link
Author

@scabug scabug commented Apr 21, 2014

Daniel Darabos (darabos) said:
It doesn't exactly rely on such changes, it's just me being clumsy. I've got a version now which only adds two new private methods. Still it is rejected by the forward binary compatibility check. I'm fairly new to all this — is there a common way to add some internal code in a way that passes the compatibility check?

I appreciate you jumping on the problem right away! It's just that #8518 was broken in 2.10 too, so even if you fix this tomorrow, I still have to figure it out for my change. Thanks!

@scabug
Copy link
Author

@scabug scabug commented Apr 23, 2014

@Ichoran said:
[~darabos] I don't see how an anchor point is really going to solve the issues. The key is the comment "XXX This may be incomplete". This is a classic design bug pattern: inheritance that doesn't override enough to do what it needs to do. To solve the issue, we need to add overrides in mapRange's overridden NumericRange (and make sure it gets used).

@scabug
Copy link
Author

@scabug scabug commented Apr 24, 2014

Daniel Darabos (darabos) said:
The anchor point is meant to only solve #8518. In that case the problem is that we suffer from floating point inaccuracies each time we pick a new start and end point, so take() and drop() end up silly.

After struggling with binary compatibility a bit longer, I'm of the opinion as well to submit it against 2.12. But how do I do that? Is it on a separate branch, or do I tell test.bc somehow which version to test against?

Sorry for polluting your ticket. Let me know if I should take my questions elsewhere. Thanks!

@scabug
Copy link
Author

@scabug scabug commented Apr 24, 2014

@Ichoran said:
My point is that once the floating point inaccuracies are fixed, #8518 will magically work also; and an anchor point is not really the best way to solve them anyway, since you still have inaccuracies in our output (you just cope with them internally).

I don't think the 2.12 branch has been created yet. Just hang on until it is, I guess, and then rebase and submit against that branch. But I think I'm going to have to fix the inaccuracy problem anyway. I haven't quite figured out yet what is possible without breaking compatibility.

@scabug
Copy link
Author

@scabug scabug commented Apr 24, 2014

Daniel Darabos (darabos) said:
Sounds good, thanks. I do not yet understand what you mean by fixing floating point inaccuracies, but I will see in time. (My worry is that there will always be numbers that you cannot accurately represent.)

@scabug
Copy link
Author

@scabug scabug commented Apr 24, 2014

@Ichoran said:
In previous versions, Double and Float ranges would actually defer to BigDecimal to avoid inaccuracies. My intent is to do that again. The performance will likely suffer, but it is difficult otherwise to avoid e.g. (0.1 to 0.5 by 0.1) contains 0.3 == false.

@scabug
Copy link
Author

@scabug scabug commented Apr 24, 2014

Daniel Darabos (darabos) said:
I have a pretty vague understanding of BigDecimal... Are its operations always associative? Will it avoid inaccuracies with a step size of, say, 1.0/3.0?

@scabug
Copy link
Author

@scabug scabug commented Apr 24, 2014

@paulp said:
It still does defer to BigDecimal depending on how you construct it. I guess this is my doing via the de-duplication of the to/until code for numerics.

scala> 0.0 until 0.3 by 0.1
res5: scala.collection.immutable.NumericRange[Double] = NumericRange(0.0, 0.1, 0.2, 0.30000000000000004)

scala> Range.Double(0.0, 0.3, 0.1)
res6: scala.collection.immutable.NumericRange[Double] = NumericRange(0.0, 0.1, 0.2)

@scabug
Copy link
Author

@scabug scabug commented Apr 24, 2014

@Ichoran said:
@paulp 'fraid so. Patching it back in is nontrivial, because as usual there's an incomplete proxy involved that needs to be fixed as well--but in this case it may not be fixable without breaking binary compatibility in at least one direction.

@scabug
Copy link
Author

@scabug scabug commented Apr 25, 2014

@Ichoran said:
Not sure I succeeded at preserving binary compatibility, but

scala/scala#3699

@scabug scabug closed this May 26, 2014
@scabug
Copy link
Author

@scabug scabug commented May 26, 2014

@Ichoran said:
Original bug is fixed. New bug opened for different issues (floating point ranges).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants