3.0.2 typing incompatible with 3.0.1

[jrudolph]

Compiler version

Our ongoing effort to port parboiled2 (and maybe more importantly akka-http and depending projects) to Scala 3, is hindered by the fact that code that compiled with 3.0.1, does not type correctly any more with 3.0.2.

Admittedly, the typing code is sophisticated, so we didn't expect that it would work unchanged from Scala 2 before. We rewrote some of the heavy implicit machinery using type matches which seemed to work somewhat with 3.0.1 (aside from some typing errors, stack overflows in the typer, and typing termination problems that we ignored or worked around for now).

Reproducer

See https://github.com/sirthias/parboiled2/pull/280, and use Scala 3.0.2 instead.

Output

Lots of type errors.

Expectation

Typing correctly.

[Kordyjan]

I've tried to investigate that and indeed code that was compiling in 3.0.1 is failing now.

The error is:

Click to see

``` [error] -- [E007] Type Mismatch Error: /Users/pmarks/Documents/parboiled2/parboiled/src/main/scala/org/parboiled2/Base64Parsing.scala:65:6 [error] 65 | oneOrMore(alphabet) ~ zeroOrMore(ch(fillChar)) ~ run[Rule1[Array[Byte]]] { [error] | ^ [error] |Found: org.parboiled2.Rule[?1.Out, ?2.Out] [error] |Required: org.parboiled2.Rule[org.parboiled2.support.hlist.HNil, Array[Byte] :: [error] | org.parboiled2.support.hlist.HNil [error] |] [error] | [error] |where: ?1 is an unknown value of type org.parboiled2.support.TailSwitch[org.parboiled2.support.hlist.HNil, ?3.Out, [error] | ?4.Out [error] |]{ [error] | Out = [error] | org.parboiled2.support.TailSwitch.TailSwitch0[ [error] | org.parboiled2.support.hlist.HNil [error] | , org.parboiled2.support.hlist.HNil, ?3.Out, ?3.Out, ?4.Out, [error] | org.parboiled2.support.hlist.HNil [error] | ] [error] |} [error] | ?2 is an unknown value of type org.parboiled2.support.TailSwitch[?5.Out, org.parboiled2.support.hlist.HNil, [error] | org.parboiled2.support.hlist.HNil [error] |]{ [error] | Out = [error] | org.parboiled2.support.TailSwitch.TailSwitch0[?5.Out, ?5.Out, [error] | org.parboiled2.support.hlist.HNil [error] | , org.parboiled2.support.hlist.HNil, org.parboiled2.support.hlist.HNil, [error] | org.parboiled2.support.hlist.HNil [error] | ] [error] |} [error] | [error] | [error] |Note: a match type could not be fully reduced: [error] | [error] | trying to reduce org.parboiled2.support.TailSwitch.TailSwitch0[org.parboiled2.support.hlist.HNil [error] | , [error] |org.parboiled2.support.hlist.HNil, ?3.Out, ?3.Out, ?4.Out, [error] | org.parboiled2.support.hlist.HNil [error] |] [error] | failed since selector ?3.Out [error] | does not match case org.parboiled2.support.hlist.HNil => ?4.Out [error] | and cannot be shown to be disjoint from it either. [error] | Therefore, reduction cannot advance to the remaining case [error] | [error] | case _ => org.parboiled2.support.hlist.HNil match { [error] | case ?3.Out => [error] | org.parboiled2.support.TailSwitch.Prepend0[ [error] | org.parboiled2.support.TailSwitch.Reverse1[ [error] | org.parboiled2.support.hlist.HNil [error] | ] [error] | , ?4.Out] [error] | case org.parboiled2.support.hlist.HNil => [error] | ?3.Out match { [error] | case _ :: t => [error] | org.parboiled2.support.TailSwitch.TailSwitch0[ [error] | org.parboiled2.support.hlist.HNil [error] | , org.parboiled2.support.hlist.HNil, ?3.Out, t, ?4.Out, [error] | org.parboiled2.support.hlist.HNil [error] | ] [error] | } <: org.parboiled2.support.hlist.HList [error] | case h :: t => [error] | ?3.Out match { [error] | case org.parboiled2.support.hlist.HNil => [error] | org.parboiled2.support.TailSwitch.TailSwitch0[ [error] | org.parboiled2.support.hlist.HNil [error] | , t, ?3.Out, org.parboiled2.support.hlist.HNil, ?4.Out, h :: [error] | org.parboiled2.support.hlist.HNil [error] | ] [error] | case _ :: tt => [error] | org.parboiled2.support.TailSwitch.TailSwitch0[ [error] | org.parboiled2.support.hlist.HNil [error] | , t, ?3.Out, tt, ?4.Out, h :: org.parboiled2.support.hlist.HNil] [error] | } <: org.parboiled2.support.hlist.HList [error] |} <: org.parboiled2.support.hlist.HList [error] 66 | decoder(input.sliceCharArray(start, cursor)) match { [error] 67 | case null => MISMATCH [error] 68 | case bytes => push(bytes) [error] 69 | } [error] 70 | } ~ EOI ```

The offending snippet:

rule {
  oneOrMore(alphabet) ~ zeroOrMore(ch(fillChar)) ~ run[Rule1[Array[Byte]]] {
    decoder(input.sliceCharArray(start, cursor)) match {
      case null  => MISMATCH
      case bytes => push(bytes)
    }
  } ~ EOI
}

It involves HLists and match types. It will be really hard to tell if this is indeed a regression or the compiler erroneously was accepting the code that shouldn't compile, without a smaller self-contained example.

[smarter]

@jrudolph First step here would be to find the first nightly where this is failing via bisection, to use a nightly simply set scalaVersion to a version number from https://repo1.maven.org/maven2/org/scala-lang/scala3-compiler_3/ (the nightlies of 3.0.2 all start with 3.0.2-RC1-bin-)

[jrudolph]

@jrudolph First step here would be to find the first nightly where this is failing via bisection, to use a nightly simply set scalaVersion to a version number from repo1.maven.org/maven2/org/scala-lang/scala3-compiler_3 (the nightlies of 3.0.2 all start with 3.0.2-RC1-bin-)

Thanks, I'll try this.

[jrudolph]

It happened in this range: https://github.com/lampepfl/dotty/compare/fb6b453...ecbe3d2. From the description, most likely it might be this change: ~https://github.com/lampepfl/dotty/compare/fb6b453...ecbe3d2~ https://github.com/lampepfl/dotty/commit/a0236000d3f9500dff58f9c6ef89b1c00073c7b3

[jrudolph]

Here's a relatively simple example:

      "Map[String, T]" - new TestParser1[Int] {
        val colors = Map("red" -> 1, "green" -> 2, "blue" -> 3)

        // does not work
        //def targetRule = rule(colors ~ EOI)    

        // works
        val colorRule = rule(colors)
        def targetRule = rule(colorRule ~ EOI)

        "red" must beMatchedWith(1)
        "green" must beMatchedWith(2)
        "blue" must beMatchedWith(3)
        "black" must beMismatched
      }

One problem with the error messages is that not all place holder are explained, so it's hard to see what might be wrong.

[smarter]

Can you turn this example into something self-contained?

[dwijnand]

most likely it might be this change: fb6b453...ecbe3d2

Which change?

[jrudolph]

Oops, I meant https://github.com/lampepfl/dotty/commit/a0236000d3f9500dff58f9c6ef89b1c00073c7b3 which seems to be the only significant typing change in that time span.

[jrudolph]

Here's a completely self-contained example:

import scala.annotation.unchecked.uncheckedVariance

import scala.language.implicitConversions

sealed trait HList extends Product with Serializable
final case class ::[+H, +T <: HList](head: H, tail: T) extends HList

sealed trait HNil extends HList
case object HNil extends HNil

trait HListable[T] {
  type Out <: HList
}

object HListable {
  type HL0[T] <: HList = T match {
    case Unit     => HNil
    case HNil     => HNil
    case ::[a, b] => ::[a, b]
    case _        => T :: HNil
  }

  implicit def calc[T]: HListable[T] { type Out = HL0[T] } = ???
}

sealed trait TailSwitch[L <: HList, T <: HList, R <: HList] {
  type Out <: HList
}
object TailSwitch {
  type Reverse0[Acc <: HList, L <: HList] <: HList = L match {
    case HNil     => Acc
    case ::[h, t] => Reverse0[h :: Acc, t]
  }

  type Reverse1[L <: HList] <: HList = L match {
    case HNil     => HNil
    case ::[h, t] => Reverse0[h :: HNil, t]
  }

  type Prepend0[A <: HList, B <: HList] <: HList = A match {
    case HNil     => B
    case ::[h, t] => ::[h, Prepend0[t, B]]
  }

  // type-level implementation of this algorithm:
  //   @tailrec def rec(L, LI, T, TI, R, RI) =
  //     if (TI <: L) R
  //     else if (LI <: T) RI.reverse ::: R
  //     else if (LI <: HNil) rec(L, HNil, T, TI.tail, R, RI)
  //     else if (TI <: HNil) rec(L, LI.tail, T, HNil, R, LI.head :: RI)
  //     else rec(L, LI.tail, T, TI.tail, R, LI.head :: RI)
  //   rec(L, L, T, T, R, HNil)
  type TailSwitch0[L <: HList, LI <: HList, T <: HList, TI <: HList, R <: HList, RI <: HList] <: HList = TI match {
    case L => R
    case _ =>
    LI match {
      case T => Prepend0[Reverse1[RI], R]
      case HNil =>
      TI match {
        case ::[_, t] => TailSwitch0[L, HNil, T, t, R, RI]
      }
      case ::[h, t] =>
      TI match {
        case HNil      => TailSwitch0[L, t, T, HNil, R, h :: RI]
        case ::[_, tt] => TailSwitch0[L, t, T, tt, R, h :: RI]
      }
    }
  }

  type Aux[L <: HList, LI <: HList, T <: HList, TI <: HList, R <: HList, RI <: HList, Out <: HList] =
    TailSwitch[L, T, R] { type Out = TailSwitch0[L, L, T, T, R, HNil] }

  implicit def tailSwitch[L <: HList, T <: HList, R <: HList]
  : TailSwitch[L, T, R] { type Out = TailSwitch0[L, L, T, T, R, HNil] } = ???
}

sealed class Rule[-I <: HList, +O <: HList] {
  def ~[I2 <: HList, O2 <: HList](that: Rule[I2, O2])(implicit
                                                      i: TailSwitch[I2, O@uncheckedVariance, I@uncheckedVariance],
                                                      o: TailSwitch[O@uncheckedVariance, I2, O2]
  ): Rule[i.Out, o.Out] = ???

}
object Rule {
  type Rule0 = Rule[HNil, HNil]
  type RuleN[+L <: HList]   = Rule[HNil, L]

  def rule[I <: HList, O <: HList](r: Rule[I, O]): Rule[I, O] = ???
  implicit def valueMap[T](m: Map[String, T])(implicit h: HListable[T]): RuleN[h.Out] = ???
}

object Test {
  import Rule._
  val colors: Map[String, Int] = Map("red" -> 1, "green" -> 2, "blue" -> 3)
  def EOI: Rule0= ???
  val r = rule(colors ~ EOI)
}

[bishabosha]

Here's a completely self-contained example:

here is the error I get with 3.0.2, with no errors for 3.0.1:

Error summary

```scala -- [E007] Type Mismatch Error: i13491.scala:96:14 -------------------------- 96 | val r = rule(colors ~ EOI) | ^^^^^^^^^^^^^^^^^^ |Found: Rule[?1.Out, ?2.Out] |Required: Rule[HNil, | TailSwitch[Int :: HNil, HNil, HNil]{ | Out = | TailSwitch.TailSwitch0[Int :: HNil, Int :: HNil, HNil, HNil, HNil, HNil] | }#Out |] | |where: ?1 is an unknown value of type TailSwitch[HNil, ?3.Out, HNil]{ | Out = TailSwitch.TailSwitch0[HNil, HNil, ?3.Out, ?3.Out, HNil, HNil] |} | ?2 is an unknown value of type TailSwitch[?4.Out, HNil, HNil]{ | Out = TailSwitch.TailSwitch0[?4.Out, ?4.Out, HNil, HNil, HNil, HNil] |} | | |Note: a match type could not be fully reduced: | | trying to reduce TailSwitch.TailSwitch0[HNil, HNil, ?3.Out, ?3.Out, HNil, HNil] | failed since selector ?3.Out | does not match case HNil => HNil | and cannot be shown to be disjoint from it either. | Therefore, reduction cannot advance to the remaining case | | case _ => HNil match { | case ?3.Out => TailSwitch.Prepend0[TailSwitch.Reverse1[HNil], HNil] | case HNil => | ?3.Out match { | case _ :: t => TailSwitch.TailSwitch0[HNil, HNil, ?3.Out, t, HNil, HNil] | } <: HList | case h :: t => | ?3.Out match { | case HNil => | TailSwitch.TailSwitch0[HNil, t, ?3.Out, HNil, HNil, h :: HNil] | case _ :: tt => | TailSwitch.TailSwitch0[HNil, t, ?3.Out, tt, HNil, h :: HNil] | } <: HList |} <: HList Explanation =========== I tried to show that Rule[?1.Out, ?2.Out] conforms to Rule[HNil, TailSwitch[Int :: HNil, HNil, HNil]{ Out = TailSwitch.TailSwitch0[Int :: HNil, Int :: HNil, HNil, HNil, HNil, HNil] }#Out ] but the comparison trace ended with `false`: ==> Rule[?1.Out, ?2.Out] <: Rule[HNil, TailSwitch[Int :: HNil, HNil, HNil]{ Out = TailSwitch.TailSwitch0[Int :: HNil, Int :: HNil, HNil, HNil, HNil, HNil] }#Out ] ==> Rule[?1.Out, ?2.Out] <: Rule[HNil, TailSwitch[Int :: HNil, HNil, HNil]{ Out = TailSwitch.TailSwitch0[Int :: HNil, Int :: HNil, HNil, HNil, HNil, HNil] }#Out ] (recurring) ==> HNil <: ?1.Out ==> HNil <: ?1.Out (recurring) ==> HNil <: TailSwitch.TailSwitch0[HNil, HNil, ?3.Out, ?3.Out, HNil, HNil] (right is approximated) ==> HNil <: TailSwitch.TailSwitch0[HNil, HNil, ?3.Out, ?3.Out, HNil, HNil] (recurring) ==> HNil <: ?3.Out match { case HNil => HNil case _ => HNil match { case ?3.Out => TailSwitch.Prepend0[TailSwitch.Reverse1[HNil], HNil] case HNil => ?3.Out match { case _ :: t => TailSwitch.TailSwitch0[HNil, HNil, ?3.Out, t, HNil, HNil] } <: HList case h :: t => ?3.Out match { case HNil => TailSwitch.TailSwitch0[HNil, t, ?3.Out, HNil, HNil, h :: HNil] case _ :: tt => TailSwitch.TailSwitch0[HNil, t, ?3.Out, tt, HNil, h :: HNil] } <: HList } <: HList } <: HList (right is approximated) ==> HNil <: ?3.Out match { case HNil => HNil case _ => HNil match { case ?3.Out => TailSwitch.Prepend0[TailSwitch.Reverse1[HNil], HNil] case HNil => ?3.Out match { case _ :: t => TailSwitch.TailSwitch0[HNil, HNil, ?3.Out, t, HNil, HNil] } <: HList case h :: t => ?3.Out match { case HNil => TailSwitch.TailSwitch0[HNil, t, ?3.Out, HNil, HNil, h :: HNil] case _ :: tt => TailSwitch.TailSwitch0[HNil, t, ?3.Out, tt, HNil, h :: HNil] } <: HList } <: HList } <: HList (recurring) <== HNil <: ?3.Out match { case HNil => HNil case _ => HNil match { case ?3.Out => TailSwitch.Prepend0[TailSwitch.Reverse1[HNil], HNil] case HNil => ?3.Out match { case _ :: t => TailSwitch.TailSwitch0[HNil, HNil, ?3.Out, t, HNil, HNil] } <: HList case h :: t => ?3.Out match { case HNil => TailSwitch.TailSwitch0[HNil, t, ?3.Out, HNil, HNil, h :: HNil] case _ :: tt => TailSwitch.TailSwitch0[HNil, t, ?3.Out, tt, HNil, h :: HNil] } <: HList } <: HList } <: HList (recurring) = false <== HNil <: ?3.Out match { case HNil => HNil case _ => HNil match { case ?3.Out => TailSwitch.Prepend0[TailSwitch.Reverse1[HNil], HNil] case HNil => ?3.Out match { case _ :: t => TailSwitch.TailSwitch0[HNil, HNil, ?3.Out, t, HNil, HNil] } <: HList case h :: t => ?3.Out match { case HNil => TailSwitch.TailSwitch0[HNil, t, ?3.Out, HNil, HNil, h :: HNil] case _ :: tt => TailSwitch.TailSwitch0[HNil, t, ?3.Out, tt, HNil, h :: HNil] } <: HList } <: HList } <: HList (right is approximated) = false <== HNil <: TailSwitch.TailSwitch0[HNil, HNil, ?3.Out, ?3.Out, HNil, HNil] (recurring) = false <== HNil <: TailSwitch.TailSwitch0[HNil, HNil, ?3.Out, ?3.Out, HNil, HNil] (right is approximated) = false <== HNil <: ?1.Out (recurring) = false <== HNil <: ?1.Out = false <== Rule[?1.Out, ?2.Out] <: Rule[HNil, TailSwitch[Int :: HNil, HNil, HNil]{ Out = TailSwitch.TailSwitch0[Int :: HNil, Int :: HNil, HNil, HNil, HNil, HNil] }#Out ] (recurring) = false <== Rule[?1.Out, ?2.Out] <: Rule[HNil, TailSwitch[Int :: HNil, HNil, HNil]{ Out = TailSwitch.TailSwitch0[Int :: HNil, Int :: HNil, HNil, HNil, HNil, HNil] }#Out ] = false The tests were made under the empty constraint 1 error found ```

[smarter]

The code does compile if we revert the fix to TypeOps#simplify in https://github.com/lampepfl/dotty/commit/a0236000d3f9500dff58f9c6ef89b1c00073c7b3 but the previous behavior was unsound, so either the code is broken or the match type reduction logic does not handle skolems properly. The error we get is:

   |  failed since selector  ?3.Out
   |  does not match  case HNil => HNil
   |  and cannot be shown to be disjoint from it either.

Replacing i" by ex" in the errors printed in MatchTypeTrace#explainEntry, we can get more information:

where:    ?3 is an unknown value of type HListable[Int]{Out = HListable.HL0[Int]}

And if I'm reading the definition of HL0 correctly, then ?3.Out should reduce to Int :: HNil which the compiler should be able to figure out is disjoint from HNil, so this looks like a bug in the match type reduction logic.

[jrudolph]

Great, thanks for the analysis, that sounds reasonable.

[dwijnand]

but the previous behavior was unsound, so either the code is broken

The use of @uncheckedVariance is perhaps worth investigating too.

[dwijnand]

And if I'm reading the definition of HL0 correctly, then ?3.Out should reduce to Int :: HNil which the compiler should be able to figure out is disjoint from HNil, so this looks like a bug in the match type reduction logic.

I wonder if the fact that HListable isn't sealed is relevant. Int :: HNil is probably an upper bound, but :: is also final so I'm not sure why that wouldn't still compute as disjoint from the sealed HNil.

[smarter]

This somehow fixed itself in recent nightlies, I've verified that it also fixes the original problem in the parboiled2 scala3 branch by setting scalaVersion := "3.1.1-RC1-bin-20210922-b13f37a-NIGHTLY" and fixing the pattern match on scalacOptions in the build to work with 3.1

[dwijnand]

somehow fixed itself in recent nightlies

Perhaps #13483

[smarter]

Nope, Olivier bisected it in https://github.com/lampepfl/dotty/pull/13585#issuecomment-927773627, it was fixed in https://github.com/lampepfl/dotty/pull/13253

[jrudolph]

Thanks for the fix(es). Seems the latest nightly works as well as 3.0.1 worked before!

https://github.com/sirthias/parboiled2/pull/313