Regression in getkyo/kyo for type comparer

[WojciechMazur]

Based on OpenCB failure in getkyo/kyo - build logs

Compiler version

Last good release: 3.5.0-RC1-bin-20240327-c251f36-NIGHTLY
First bad release: 3.5.0-RC1-bin-20240329-c8c3bde-NIGHTLY
Bisect points to 9c80a7c

Minimized code

sealed abstract class Kyo[+T, -S]
opaque type <[+T, -S] >: T = T | Kyo[T, S]

abstract class Effect[+E]:
    type Command[_]

case class Recurse[Command[_], Result[_], E <: Effect[E], T, S, S2](
    h: ResultHandler[Command, Result, E, S],
    v: T < (E & S & S2)
)

abstract class ResultHandler[Command[_], Result[_], E <: Effect[E], S]:
  opaque type Handle[T, S2] >: (Result[T] < (S & S2)) = Result[T] < (S & S2) | Recurse[Command, Result, E, T, S, S2]

  def handle[T, S2](h: ResultHandler[Command, Result, E, S], v: T < (E & S & S2)): Handle[T, S2] = Recurse(h, v)

Output

Compiling project (Scala 3.5.0-RC1-bin-20240409-2148c8d-NIGHTLY, JVM (17))
[error] ./bisect/test.scala:15:111
[error] Found:    (v : T < (E & S & S2))
[error] Required: T < (E & S & S2)
[error] 
[error] where:    E is a type in class ResultHandler with bounds <: Effect[E]
[error]   def handle[T, S2](h: ResultHandler[Command, Result, E, S], v: T < (E & S & S2)): Handle[T, S2] = Recurse(h, v)
[error]        

Expectation

Should compile without significant compilation time penalties to optimizations done in #20034

[Gedochao]

cc @odersky

[odersky]

How i fixed it: There was a nice minimization and bisect which made it clear that the problem was in the new optimized implementation of lub. But for a long time I could not find anything wrong with that implementation. I turned on -explain and -Ydebug to get the full subtyping trace. The curious thing is that it decided that glb(E & S & S2)= S2 even though the three types should be unrelated. Further investigation gave that dropIfSuper returned NoType, which should mean one of the types is redundant with respect to the others, except that in this case it wasn't. I then turned on printing for the exact statement where a type was dropped. It never happened. So the NoType must have come from elsewhere. I added some ensuring(_.exists) to some of the other branches, and found it in the end: The case

  case tp: TypeVar if tp.isInstantiated =>
    dropIfSuper(tp.inst, sub)

triggered the assertion. Then it became clear. tp was instantiated in this case, but the instance was in a retractable constraint so the inst method of TypeVar still returned NoType. That meant that the logic in lub decided that the case could be dropped! It's clearly a trap waiting to happen, so I went further and made sure that it will be hard to make the same mistake again.