StackOverflowError in the compiler if a subclass provides an abstract type projection from a higher type as a type parameter to its base class

[noresttherein]

Reproduction steps

Scala version: 2.13.10

	trait F[O] { type Value }
	trait B[V]
	trait E[M[O] <: F[O], V] extends B[V]
	trait G[M[O] <: F[O]] extends E[M, M[Unit]#Value]

	type TE = E[M, _] forSome { type M[O] <: F[O] }
	type TG = G[M] forSome { type M[O] <: F[O] }

	def test[M[O] <: F[O], V](e :E[M, V]) :Unit = (e :TE) match {
		case _ :TG =>
	}

Problem

scalac: Error: java.lang.StackOverflowError
java.lang.StackOverflowError
	at scala.reflect.internal.tpe.TypeConstraints$UndoLog.scala$reflect$internal$tpe$TypeConstraints$UndoLog$$$outer(TypeConstraints.scala:33)
	at scala.reflect.internal.tpe.TypeConstraints$UndoLog.undoTo(TypeConstraints.scala:48)
	at scala.reflect.internal.tpe.TypeComparers.isSameType(TypeComparers.scala:119)
	at scala.reflect.internal.tpe.TypeComparers.isSameType$(TypeComparers.scala:105)
	at scala.reflect.internal.SymbolTable.isSameType(SymbolTable.scala:28)
	at scala.reflect.internal.Types$Type.$eq$colon$eq(Types.scala:864)
	at scala.reflect.internal.Types$TypeVar.checkIsSameType$1(Types.scala:3697)
	at scala.reflect.internal.Types$TypeVar.registerTypeEquality(Types.scala:3702)
	at scala.reflect.internal.tpe.TypeComparers.mutateNonTypeConstructs$1(TypeComparers.scala:217)
	at scala.reflect.internal.tpe.TypeComparers.isSameType2(TypeComparers.scala:261)
	at scala.reflect.internal.tpe.TypeComparers.isSameType2$(TypeComparers.scala:198)
	at scala.reflect.internal.SymbolTable.isSameType2(SymbolTable.scala:28)
	at scala.reflect.internal.tpe.TypeComparers.isSameType1(TypeComparers.scala:142)
	at scala.reflect.internal.tpe.TypeComparers.isSameType(TypeComparers.scala:117)
	at scala.reflect.internal.tpe.TypeComparers.isSameType$(TypeComparers.scala:105)
	at scala.reflect.internal.SymbolTable.isSameType(SymbolTable.scala:28)
	at scala.reflect.internal.Types$Type.$eq$colon$eq(Types.scala:864)
	at scala.reflect.internal.Types$TypeVar.checkIsSameType$1(Types.scala:3697)
	at scala.reflect.internal.Types$TypeVar.registerTypeEquality(Types.scala:3702)
	at scala.reflect.internal.tpe.TypeComparers.mutateNonTypeConstructs$1(TypeComparers.scala:217)
	at scala.reflect.internal.tpe.TypeComparers.isSameType2(TypeComparers.scala:261)
	at scala.reflect.internal.tpe.TypeComparers.isSameType2$(TypeComparers.scala:198)
	at scala.reflect.internal.SymbolTable.isSameType2(SymbolTable.scala:28)
	at scala.reflect.internal.tpe.TypeComparers.isSameType1(TypeComparers.scala:142)
	at scala.reflect.internal.tpe.TypeComparers.isSameType(TypeComparers.scala:117)
	at scala.reflect.internal.tpe.TypeComparers.isSameType$(TypeComparers.scala:105)
	at scala.reflect.internal.SymbolTable.isSameType(SymbolTable.scala:28)
	at scala.reflect.internal.Types$Type.$eq$colon$eq(Types.scala:864)
	at scala.reflect.internal.Types$TypeVar.checkIsSameType$1(Types.scala:3697)
	at scala.reflect.internal.Types$TypeVar.registerTypeEquality(Types.scala:3702)
	at scala.reflect.internal.tpe.TypeComparers.mutateNonTypeConstructs$1(TypeComparers.scala:217)
	at scala.reflect.internal.tpe.TypeComparers.isSameType2(TypeComparers.scala:261)
	at scala.reflect.internal.tpe.TypeComparers.isSameType2$(TypeComparers.scala:198)
	at scala.reflect.internal.SymbolTable.isSameType2(SymbolTable.scala:28)
	at scala.reflect.internal.tpe.TypeComparers.isSameType1(TypeComparers.scala:142)
	at scala.reflect.internal.tpe.TypeComparers.isSameType(TypeComparers.scala:117)
	at scala.reflect.internal.tpe.TypeComparers.isSameType$(TypeComparers.scala:105)
	at scala.reflect.internal.SymbolTable.isSameType(SymbolTable.scala:28)

[SethTisue]

can it be encoded without forSome? not sure whether to label it "fixed in Scala 3", since Scala 3 doesn't have forSome

[Jasper-M]

Apart from the fact that I have no idea how to write a higher kinded wildcard, M[Unit]#Value is also illegal in Scala 3.

[noresttherein]

Yeah, I know Scala 3 has no abstract type projection, but Scala 2 has a much worse typer and I can't use F[_] as a type parameter, because it will not unify the wildcard member type.

AFAIK, it can't be encoded without forSome. This is the only way in which a type with a type constructor type parameter can be used as a pattern. Sadly, even if I forgo abstract type projection, I don't think a type pattern with a type constructor type parameter can be written at all in Scala 3 without resolving to:

def test[M[O] <: F[O], V](e :E[M, V]) :Unit = e match {
	case _ :G[ F @unchecked] =>
}

FWIW, this is how it could be written in Scala 3:

trait F[O] { type Value }
trait B { type Value }
type TB[V] = B { type Value = V }

trait E extends B { val f :Cons[Unit]; type Cons[O] <: F[O] } 
type TE[M[O] <: F[O], V] = E { type Cons[O] = M[O]; type Value = V }

trait G extends E { val f :Cons[Unit]; type Value = f.Value; def get :Value } 
type TG[M[O] <: F[O]] = G { type Cons[O] = M[O] }

def test[M[O] <: F[O], V](e :TE[M, V]) :Unit = (e :E) match {
	case _ :G =>
}

Edit: it used to be that this did not compile in Scala 2 a couple of years back, so I was forced to use type projections:

trait F[O] { type Value }
trait B { type Value }
type TB[V] = B { type Value = V }

trait E extends B { val f :Cons[Unit]; type Cons[O] <: F[O] } 
type TE[M[O] <: F[O], V] = E { type Cons[O] = M[O]; type Value = V }

trait G extends E { val f :Cons[Unit]; type Value = f.Value; def get :Value } 
type TG[M[O] <: F[O]] = G { type Cons[O] = M[O] }

trait FF[O] extends F[O] { type Value = Int } 
val g :TG[FF] = new G { type Cons[O] = FF[O]; val f = new FF[Unit] {}; def get = 0 }

def test2[M[O] <: F[O]](g :TG[M]) :g.Value = g.get
val notAnInt = test2(g)
notAnInt :Int

Now it seems it is fixed, or I misremember the problem. If it's the former, then great, my migration to Scala 3 will be much easier if I first rewrite everything in Scala 2 to the above.

[joroKr21]

Unification in Scala 2.13 did get better over the years so it sounds plausible to me that it got fixed (I mean the unification issue you mentioned)