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
Appending a large collection to a ListSet causes a StackOverflowError #3822
Comments
Imported From: https://issues.scala-lang.org/browse/SI-3822?orig=1 |
@paulp said: |
Sean Parsons (seanparsons) said: I stumbled on it while trying to come up with a nice implementation of the Sieve of Eratosthenes technique where I planned to filter immutable collections by replacing them repeatedly. Is there any scope for me adding some more unit tests around the collections framework to detect issues like this in the future? |
@paulp said:
Not that low. More importantly, it's unnecessary. Post-patch: scala> import scala.collection.immutable._
import scala.collection.immutable._
scala> new ListSet[Int] ++ (2 to 1999999)
res0: scala.collection.immutable.ListSet[Int] = Set(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, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 1...
scala> res0 filter (x => x > 1000000 && x < 1000005)
res1: scala.collection.immutable.ListSet[Int] = Set(1000004, 1000003, 1000002, 1000001)
I say a prayer along those lines most nights. There is always talk about such things but so far everyone who shows much interest is derailed by the realities. |
@paulp said: // with this patch: 2.250s elapsed, assertions pass. Closes #3822, review by community. |
I wanted to create a large ListSet, which goes quite wrong when using the ++ operator as the following code would demonstrate:
The stack trace looks like the following:
java.lang.StackOverflowError
at scala.collection.immutable.ListSet$$Node.contains(ListSet.scala:117)
at scala.collection.immutable.ListSet$$Node.contains(ListSet.scala:117)
at scala.collection.immutable.ListSet$$Node.contains(ListSet.scala:117)
(about 1,000 more of the above)
The text was updated successfully, but these errors were encountered: