Regression in `zio/zio-schema` for typer/implicit resolution

[WojciechMazur]

Based on OpenCB failure in zio/zio-schema - build logs

Compiler version

3.8.0-RC1 nightlies
Bisect points to c2ef180 / #20459

Minimized code

sealed trait Schema[A]
object Schema:
  def enumeration[A, C <: CaseSet.Aux[A]](caseSet: C): Schema[A] = ???

sealed trait Case[R, A]
sealed trait CaseSet:
  type EnumType

object CaseSet {
  def caseOf[A: Schema, Z >: A]: Cons[A, Empty[Z], Z] = ???
  type Aux[EnumType0] = CaseSet { type EnumType = EnumType0 }

  final class Empty[Z] extends CaseSet:
    type EnumType = Z
    // def ++[That](that: That)(implicit append: Append[Z, Empty[Z], That]): append.Out = ???
  object Empty:
    type Aux[Z] = CaseSet.Empty[Z] { type EnumType = Z }

  sealed trait :+:[A, +T <: CaseSet] extends CaseSet
  final class Cons[A, +T <: CaseSet.Aux[Z], Z](head: Case[Z, A], tail: T) extends :+:[A, T]:
    type EnumType = Z
    def ++[That](that: That)(implicit append: Append[Z, Cons[A, T, Z], That]): append.Out = ???
}

object Cons0:
  type Aux[A, T <: CaseSet.Aux[Z], Z] = CaseSet.Cons[A, T, Z] { type EnumType = Z }

sealed trait Append[EnumType, -Left, -Right]:
  type Out <: CaseSet.Aux[EnumType]

object Append extends AppendLowPriority:
  type WithOut[EnumType, Left, Right, Out0] = Append[EnumType, Left, Right] { type Out = Out0 }

  implicit def AppendCons[A, T <: CaseSet.Aux[Z], Z, That <: CaseSet.Aux[Z]](implicit
      append: Append[Z, T, That]
  ): Append.WithOut[Z, CaseSet.Cons[A, T, Z], That, CaseSet.Cons[A, append.Out, Z]] = ???

trait AppendLowPriority extends AppendLowPriority2:
  implicit def AppendEmptyRight[T <: CaseSet.Aux[Z], Z]: Append.WithOut[Z, T, CaseSet.Empty[Z], T] =
    ???

trait AppendLowPriority2:
  implicit def AppendEmptyLeft[T <: CaseSet.Aux[Z], Z]: Append.WithOut[Z, CaseSet.Empty[Z], T, T] =
    ???

object Test:
  given Schema[Int] = ???
  given Schema[Boolean] = ???
  given Schema[String] = ???

  type UnionValue = Int | Boolean | String
  given Schema[UnionValue] = Schema.enumeration[UnionValue, CaseSet.Aux[UnionValue]](
      CaseSet.caseOf[Int, UnionValue] ++
      CaseSet.caseOf[Boolean, UnionValue] ++
      CaseSet.caseOf[String, UnionValue]
  )

Output

error] No given instance of type Append[Int | Boolean | String, CaseSet.Cons[Int, ?1.Out, Int | Boolean | String], CaseSet.Cons[String, CaseSet.Empty[Test.UnionValue], Test.UnionValue]] was found for parameter append of method ++ in class Cons.
[error] I found:
[error] 
[error]     Append.AppendCons[Int, T, Int | Boolean | String, That](/* missing */summon[Append[Int | Boolean | String, T, That]])
[error] 
[error] But no implicit values were found that match type Append[Int | Boolean | String, T, That]
[error] 
[error] where:    ?1 is an unknown value of type Append.WithOut[Int | Boolean | String, CaseSet.Empty[Int | Boolean | String], T², T²]
[error] .
[error]       CaseSet.caseOf[String, UnionValue]
[error]                                         ^
Error compiling project (Scala 3.8.0-RC1-bin-20250921-834e8e9-NIGHTLY, JVM (21))

Expectation

Should compile

[Gedochao]

cc @eejbyfeldt

[eejbyfeldt]

Slightly more minimized:

sealed trait CaseSet:
  type EnumType

object CaseSet {
  def caseOf[A, Z >: A]: Cons[A, Empty[Z], Z] = ???
  type Aux[EnumType0] = CaseSet { type EnumType = EnumType0 }

  final class Empty[Z] extends CaseSet:
    type EnumType = Z

  final class Cons[A, +T <: CaseSet.Aux[Z], Z](head: A, tail: T) extends CaseSet:
    type EnumType = Z
    def ++[That](that: That)(implicit append: Append[Z, Cons[A, T, Z], That]): append.Out = ???
}

sealed trait Append[EnumType, -Left, -Right]:
  type Out <: CaseSet.Aux[EnumType]

object Append:
  type WithOut[EnumType, Left, Right, Out0] = Append[EnumType, Left, Right] { type Out = Out0 }

  implicit def AppendCons[A, Z, T <: CaseSet.Aux[Z], That <: CaseSet.Aux[Z]](implicit
      append: Append[Z, T, That]
  ): Append.WithOut[Z, CaseSet.Cons[A, T, Z], That, CaseSet.Cons[A, append.Out, Z]] = ???

  implicit def AppendEmptyLeft[T <: CaseSet.Aux[Z], Z]: Append.WithOut[Z, CaseSet.Empty[Z], T, T] =
    ???

object Test:
  type UnionValue = Int | Boolean | String
  val _ = CaseSet.caseOf[Int, UnionValue] ++
      CaseSet.caseOf[Boolean, UnionValue] ++
      CaseSet.caseOf[String, UnionValue]

It seems to trigger the divergence check when searching for AppendCons implicit. This seems to be at least partly due to how TypeBounds are treated in the TypeSizeAccumulator. Making Right invariant make the code compile.

It seems like in the first search of AppendCons that That is a fully specified but in the second search it a type parameter with bounds. Since both the upper bound and lower bound is add to the type size the second search type is considered bigger and we trigger the divergence check. I think #20459 only hid this issue and is not the root cause of it. Feels like it should be possible to come up with code hitting this issue even before that PR.