scala/scala — pull request #2797 by paulp (2013-08-06 01:24:40+00:00)
Title: Fix N^2 spot in erasure.

An expression containing nested casts would type the same tree 2^N times where
N is the number of nested casts. This was particularly visible in Vector.scala
where one can find a six-cast expression. It's currently line "why was six
afraid of seven", aka line 789.

display5((index >> 25) & 31)
.asInstanceOf[Array[AnyRef]]((index >> 20) & 31)
.asInstanceOf[Array[AnyRef]]((index >> 15) & 31)
.asInstanceOf[Array[AnyRef]]((index >> 10) & 31)
.asInstanceOf[Array[AnyRef]]((index >> 5) & 31)
.asInstanceOf[Array[AnyRef]](index & 31)
.asInstanceOf[T]

Compiling Vector.scala, before/after.

< #unique types : 10805
> #unique types : 9722
< #created tree nodes : 26716
> #created tree nodes : 25647

I found a similar bug about a year ago in 39f01d4f48. It's interesting to
consider how little defense we have against bugs of this nature - visually
non-obvious differences in tree traversal can have spectacular impact on
complexity.