diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2015-10-29 13:01:07 +1000 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2015-11-13 14:24:35 +1000 |
commit | 238b1fba3d5085457d05817c646d436542def5ea (patch) | |
tree | 3a828a30eaa286ba8c28fc918f9dc15cd6602232 | |
parent | a24ca7fa617cabada82c43d2d6ac354db698d181 (diff) | |
download | scala-238b1fba3d5085457d05817c646d436542def5ea.tar.gz scala-238b1fba3d5085457d05817c646d436542def5ea.tar.bz2 scala-238b1fba3d5085457d05817c646d436542def5ea.zip |
Attacking exponential complexity in TypeMaps
- Don't normalize existentials during the `contain`-s type map;
`ExistentialType#normalize' calls contains internally and
an exponential blowup ensues.
- Ensure that the type map used in variance validation never
returns modified types in order to avoid needless cloning of
symbols.
The enclosed test case still gets stuck in Uncurry, thanks to
the way that `TypeMap#mapOver(List[Symbol])` recurses through the
type first to check whether the type map would be an no-op or not.
If not, it repeats the type map with cloned symbols. Doing the work
twice at each level of recursion blows up the complexity.
Removing that "fast path" allows the enclosed test to compile
completely. As at this commit, it gets stuck in uncurry, which
dealiases `s.List` to `s.c.i.List` within the type.
Some more background on the troublesome part of `TypeMap`:
http://lrytz.github.io/scala-aladdin-bugtracker/displayItem.do%3Fid=1210.html
https://github.com/scala/scala/commit/f8b2b21050e7a2ca0f537ef70e3e0c8eead43abc
-rw-r--r-- | src/reflect/scala/reflect/internal/Variances.scala | 24 | ||||
-rw-r--r-- | src/reflect/scala/reflect/internal/tpe/TypeMaps.scala | 18 | ||||
-rw-r--r-- | test/files/pos/existental-slow-compile2.scala | 7 | ||||
-rw-r--r-- | test/files/pos/existential-slow-compile1.flags | 1 | ||||
-rw-r--r-- | test/files/pos/existential-slow-compile1.scala | 7 |
5 files changed, 44 insertions, 13 deletions
diff --git a/src/reflect/scala/reflect/internal/Variances.scala b/src/reflect/scala/reflect/internal/Variances.scala index ef22df3f2e..af04f47e0e 100644 --- a/src/reflect/scala/reflect/internal/Variances.scala +++ b/src/reflect/scala/reflect/internal/Variances.scala @@ -122,15 +122,21 @@ trait Variances { * same is true of the parameters (ValDefs) unless we are inside a * refinement, in which case they are checked from here. */ - def apply(tp: Type): Type = tp match { - case _ if isUncheckedVariance(tp) => tp - case _ if resultTypeOnly(tp) => this(tp.resultType) - case TypeRef(_, sym, _) if sym.isAliasType => this(tp.normalize) - case TypeRef(_, sym, _) if !sym.variance.isInvariant => checkVarianceOfSymbol(sym) ; mapOver(tp) - case RefinedType(_, _) => withinRefinement(mapOver(tp)) - case ClassInfoType(parents, _, _) => parents foreach this ; tp - case mt @ MethodType(_, result) => flipped(mt.paramTypes foreach this) ; this(result) - case _ => mapOver(tp) + def apply(tp: Type): Type = { + tp match { + case _ if isUncheckedVariance(tp) => + case _ if resultTypeOnly(tp) => this(tp.resultType) + case TypeRef(_, sym, _) if sym.isAliasType => this(tp.normalize) + case TypeRef(_, sym, _) if !sym.variance.isInvariant => checkVarianceOfSymbol(sym) ; mapOver(tp) + case RefinedType(_, _) => withinRefinement(mapOver(tp)) + case ClassInfoType(parents, _, _) => parents foreach this + case mt @ MethodType(_, result) => flipped(mt.paramTypes foreach this) ; this(result) + case _ => mapOver(tp) + } + // We're using TypeMap here for type traversal only. To avoid wasteful symbol + // cloning during the recursion, it is important to return the input `tp`, rather + // than the result of the pattern match above, which normalizes types. + tp } def validateDefinition(base: Symbol) { val saved = this.base diff --git a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala index b8d4050d7d..804360b677 100644 --- a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala +++ b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala @@ -998,10 +998,20 @@ private[internal] trait TypeMaps { class ContainsCollector(sym: Symbol) extends TypeCollector(false) { def traverse(tp: Type) { if (!result) { - tp.normalize match { - case TypeRef(_, sym1, _) if (sym == sym1) => result = true - case SingleType(_, sym1) if (sym == sym1) => result = true - case _ => mapOver(tp) + tp match { + case _: ExistentialType => + // ExistentialType#normalize internally calls contains, which leads to exponential performance + // for types like: `A[_ <: B[_ <: ... ]]`. Example: pos/existential-contains.scala. + // + // We can just map over the components and wait until we see the underlying type before we call + // normalize. + mapOver(tp) + case _ => + tp.normalize match { + case TypeRef(_, sym1, _) if (sym == sym1) => result = true + case SingleType(_, sym1) if (sym == sym1) => result = true + case _ => mapOver(tp) + } } } } diff --git a/test/files/pos/existental-slow-compile2.scala b/test/files/pos/existental-slow-compile2.scala new file mode 100644 index 0000000000..907344982c --- /dev/null +++ b/test/files/pos/existental-slow-compile2.scala @@ -0,0 +1,7 @@ +class C { + class L[+A] + def test = { + val foo: + L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: _ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: _ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_]]]]]]]]]]]]]]]]]]]]]]]] + = ??? } } + diff --git a/test/files/pos/existential-slow-compile1.flags b/test/files/pos/existential-slow-compile1.flags new file mode 100644 index 0000000000..7f7581974d --- /dev/null +++ b/test/files/pos/existential-slow-compile1.flags @@ -0,0 +1 @@ +-Ystop-after:refchecks diff --git a/test/files/pos/existential-slow-compile1.scala b/test/files/pos/existential-slow-compile1.scala new file mode 100644 index 0000000000..8602afd9db --- /dev/null +++ b/test/files/pos/existential-slow-compile1.scala @@ -0,0 +1,7 @@ +class C { + type L[+A] = scala.collection.immutable.List[A] + def test = { + val foo: + L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: _ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: _ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_]]]]]]]]]]]]]]]]]]]]]]]] + = ??? } } + |