From 238b1fba3d5085457d05817c646d436542def5ea Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Thu, 29 Oct 2015 13:01:07 +1000 Subject: 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 --- test/files/pos/existental-slow-compile2.scala | 7 +++++++ test/files/pos/existential-slow-compile1.flags | 1 + test/files/pos/existential-slow-compile1.scala | 7 +++++++ 3 files changed, 15 insertions(+) create mode 100644 test/files/pos/existental-slow-compile2.scala create mode 100644 test/files/pos/existential-slow-compile1.flags create mode 100644 test/files/pos/existential-slow-compile1.scala (limited to 'test') 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[_]]]]]]]]]]]]]]]]]]]]]]]] + = ??? } } + -- cgit v1.2.3