Does filterKey cause a stack overflow?

Question

As I understand it, the filterKeys of MapLike creates a wrapper on top of the original map. So, if I executed the code below m , there will be a chain of 10K wrappers and the source map.

  var m = Map (1 -> "one", 2 -> "two")
 for (1 <- 0 until 10000) {m = m.filterKeys (_% 2 == 0)}

Now I thought that calling m.contains caused a stack overflow, but this does not happen. Could you explain what happens in this case?

Answer 1

Your loop runs only once if I copy the shorthand. Because of this, you only create one shell, so what was supposed to be a chain of 10,000 wrappers is just a chain of 1. It could be a typo, but a loop,

 for(1 <- 0 until 10000) {m = m.filterKeys(_%2 == 0)} 

it should be

 for(i <- 0 until 10000) {m = m.filterKeys(_%2 == 0)} 

In addition, Daniel is right; fitlerKeys really creates what is essentially a wrapper. It took me more than 10,000 iterations, but I managed to create a StackOverflowError.

Answer 2

I could not reproduce the stack overflow, but here is what happens:

 override def filterKeys(p: A => Boolean): Map[A, B] = new DefaultMap[A, B] { override def foreach[C](f: ((A, B)) => C): Unit = for (kv <- self) if (p(kv._1)) f(kv) def iterator = self.iterator.filter(kv => p(kv._1)) override def contains(key: A) = self.contains(key) && p(key) def get(key: A) = if (!p(key)) None else self.get(key) } 

Note that copying the values ​​does not occur: the new class simply adds rules to the four methods that will change the way they work to reflect the added filter. Since you reapply filterKeys (10,000 times), this means that you have 10,000 classes, each of which points to the previous one, and the first points to the original map.

When you call one of the above methods (directly or indirectly) in the final class, 10,000 nested methods will be called, which can lead to a stack overflow if your stack is small enough.

Answer 3

I managed to cause it to overflow the stack (Scala 2.9.1)

 scala> var m = Map(1 -> "one", 2 -> "two") scala> for (_ <- 0 until 1000000) { m = m.filterKeys(_ % 2 == 0) } scala> m.contains(1) huge stack trace 

Of course, you can avoid stack tracing by forcing filterKeys to do its job at every step:

 scala> var m = Map(1 -> "one", 2 -> "two") scala> for (_ <- 0 until 1000000) { m = Map() ++ m.filterKeys(_ % 2 == 0) } scala> m.contains(1) res1: Boolean = false