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 sirthias/parboiled2#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: fb6b453...ecbe3d2. From the description, most likely it might be this change: fb6b453...ecbe3d2 a023600

[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 a023600 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)
}