From 466b7d29f1c70018aea965961e830f50cf0facd4 Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Mon, 5 Aug 2013 16:41:54 -0700 Subject: 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. --- .../scala/tools/nsc/transform/Erasure.scala | 3 +- test/files/pos/erasure-nsquared.scala | 35 ++++++++++++++++++++++ 2 files changed, 37 insertions(+), 1 deletion(-) create mode 100644 test/files/pos/erasure-nsquared.scala diff --git a/src/compiler/scala/tools/nsc/transform/Erasure.scala b/src/compiler/scala/tools/nsc/transform/Erasure.scala index 0f65b11e9b..ee687e56b0 100644 --- a/src/compiler/scala/tools/nsc/transform/Erasure.scala +++ b/src/compiler/scala/tools/nsc/transform/Erasure.scala @@ -706,7 +706,8 @@ abstract class Erasure extends AddInterfaces // } typed(untyped) } - } else tree + } else qual1 + case Apply(TypeApply(sel @ Select(qual, name), List(targ)), List()) if tree.symbol == Any_isInstanceOf => targ.tpe match { diff --git a/test/files/pos/erasure-nsquared.scala b/test/files/pos/erasure-nsquared.scala new file mode 100644 index 0000000000..b0e30ade58 --- /dev/null +++ b/test/files/pos/erasure-nsquared.scala @@ -0,0 +1,35 @@ +trait BigCast { + def bar(x: Int): AnyRef = ( + null + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + .asInstanceOf[List[AnyRef]].head + ) +} -- cgit v1.2.3