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

Jump to bottom

BitSet.last raises exception on non-empty set #10164

Closed
scabug opened this issue Jan 24, 2017 · 3 comments
Closed

BitSet.last raises exception on non-empty set #10164

scabug opened this issue Jan 24, 2017 · 3 comments
Assignees
@som-snytt
Labels
help wanted library:collections
Milestone
2.12.2

Comments

@scabug
Copy link

scabug commented Jan 24, 2017 •
edited by adriaanm

A non-empty bitset incorrectly raises an "Empty BitSet" exception. The exception occurs several seconds after invoking the method.

scala> scala.collection.mutable.BitSet() ++ (0 to 128)
res9: scala.collection.mutable.BitSet = BitSet(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128)

scala> res9.last
java.util.NoSuchElementException: Empty BitSet
  at scala.collection.BitSetLike.last(BitSetLike.scala:225)
  at scala.collection.BitSetLike.last$(BitSetLike.scala:218)
  at scala.collection.mutable.BitSet.last(BitSet.scala:40)
  ... 30 elided

I think that the cause is this line from the source code (link to line 223 of BitSetLike.scala).
Based on the loop termination condition, the loop looks like it is meant to walk backwards through the array of words. And this is what you would expect for "last"
But the index variable "i" is being incremented.

I believe that what is happening in the example above is that "i" is being incremented until it overflows to MIN_INT (this takes several seconds on my machine) - and then the loop terminates and the exception is thrown.

(0 to 128) seems to be the smallest example on which this fails. (0 to 127) is fine.
@scabug
Copy link
Author

scabug commented Jan 24, 2017

Imported From: https://issues.scala-lang.org/browse/SI-10164?orig=1
Reporter: Alastair Reid (areid)
Affected Versions: 2.12.1

@scabug
Copy link
Author

scabug commented Feb 11, 2017

@SethTisue said:
good catch! want to attempt a PR with a fix...?

@scabug
Copy link
Author

scabug commented Feb 19, 2017

@som-snytt said (edited on Feb 19, 2017 4:41:32 AM UTC):
OK, yes I do. Fix as suggested by reporter: scala/scala#5697

@scabug scabug closed this as completed Feb 19, 2017
@scabug scabug added this to the 2.12.2 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@som-snytt som-snytt

Labels
help wanted library:collections
Projects
None yet
Milestone
2.12.2
Development

No branches or pull requests
2 participants
@som-snytt @scabug