SOE in TypeSizeAccumulator.apply

[sir-wabbit]

minimized code

trait F[x]
implicit def foo[f[_], y, x <: f[y]](implicit ev: F[y]): F[x] = ???
val test = implicitly

Stack trace

java.lang.StackOverflowError while compiling testing/Test.scala
Exception in thread "main" java.lang.StackOverflowError
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5125)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5122)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:4976)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5128)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5122)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:5004)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5136)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5134)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5122)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldArgs$1(Types.scala:4972)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:4976)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5128)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5122)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:5004)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5136)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5134)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5122)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldArgs$1(Types.scala:4972)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:4976)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5128)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5122)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:5004)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5136)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5134)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5122)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldArgs$1(Types.scala:4972)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:4976)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5128)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5122)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:5004)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5136)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5134)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5122)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldArgs$1(Types.scala:4972)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:4976)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5128)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5122)
	at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:5004)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5136)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5134)
	at dotty.tools.dotc.core.Types$TypeSizeAccumulator.apply(Types.scala:5122)

Possibly related to #7744 ?

[odersky]

The problem is that the TypeSize and ConveringSet accumulators infinitely recurse through the F-bound. The seen sets in the accumulators do not work since the higher-kinded type lambda f[_] is not hash-consed, so we get new types on each recursive call. I tried to not recurse into bounds in TypeSizeAccumulator and CoveringSetAccumulator, with this diff:

@@ -5175,7 +5174,7 @@ object Types {
           case tp: TypeRef if tp.info.isTypeAlias =>
             apply(n, tp.superType)
           case tp: TypeParamRef =>
-            apply(n, ctx.typeComparer.bounds(tp))
+            n//apply(n, ctx.typeComparer.bounds(tp))
           case _ =>
             foldOver(n, tp)
         }
@@ -5203,7 +5202,7 @@ object Types {
             val tsym = if (tp.termSymbol.is(Param)) tp.underlying.typeSymbol else tp.termSymbol
             foldOver(cs + tsym, tp)
           case tp: TypeParamRef =>
-            apply(cs, ctx.typeComparer.bounds(tp))
+            cs//apply(cs, ctx.typeComparer.bounds(tp))
           case other =>
             foldOver(cs, tp)
         }

That fixed #7745 but broke #6058 again. It seems we need a more refined approach to type size and covering sets.

@milessabin Do you have an idea how to fix this?

[milessabin]

Is it possible to reproduce this in cases where there are actually some constraints on the type variables?