Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

3.0.2 typing incompatible with 3.0.1 #13491

Closed
jrudolph opened this issue Sep 9, 2021 · 18 comments
Closed

3.0.2 typing incompatible with 3.0.1 #13491

jrudolph opened this issue Sep 9, 2021 · 18 comments
Assignees
Labels
area:match-types area:typer itype:bug regression This worked in a previous version but doesn't anymore

Comments

@jrudolph
Copy link
Contributor

jrudolph commented Sep 9, 2021

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 Kordyjan added area:typer regression This worked in a previous version but doesn't anymore labels Sep 9, 2021
@nicolasstucki nicolasstucki added the stat:needs minimization Needs a self contained minimization label Sep 9, 2021
@Kordyjan
Copy link
Contributor

Kordyjan commented Sep 9, 2021

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
Copy link
Member

smarter commented Sep 9, 2021

@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
Copy link
Contributor Author

jrudolph commented Sep 9, 2021

@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
Copy link
Contributor Author

jrudolph commented Sep 9, 2021

It happened in this range: fb6b453...ecbe3d2. From the description, most likely it might be this change: fb6b453...ecbe3d2 a023600

@jrudolph
Copy link
Contributor Author

jrudolph commented Sep 9, 2021

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
Copy link
Member

smarter commented Sep 9, 2021

Can you turn this example into something self-contained?

@dwijnand

This comment has been minimized.

@jrudolph
Copy link
Contributor Author

Oops, I meant a023600 which seems to be the only significant typing change in that time span.

@jrudolph
Copy link
Contributor Author

jrudolph commented Sep 13, 2021

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
Copy link
Member

bishabosha commented Sep 13, 2021

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
-- [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
Copy link
Member

smarter commented Sep 13, 2021

The code does compile if we revert the fix to TypeOps#simplify in a023600 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
Copy link
Contributor Author

Great, thanks for the analysis, that sounds reasonable.

@dwijnand
Copy link
Member

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

The use of @uncheckedVariance is perhaps worth investigating too.

@dwijnand
Copy link
Member

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.

@OlivierBlanvillain OlivierBlanvillain removed the stat:needs minimization Needs a self contained minimization label Sep 22, 2021
OlivierBlanvillain added a commit to dotty-staging/dotty that referenced this issue Sep 22, 2021
@smarter
Copy link
Member

smarter commented Sep 23, 2021

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

OlivierBlanvillain added a commit that referenced this issue Sep 27, 2021
@dwijnand
Copy link
Member

somehow fixed itself in recent nightlies

Perhaps #13483

@smarter
Copy link
Member

smarter commented Sep 27, 2021

Nope, Olivier bisected it in #13585 (comment), it was fixed in #13253

@jrudolph
Copy link
Contributor Author

jrudolph commented Oct 4, 2021

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

sirthias/parboiled2#313

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area:match-types area:typer itype:bug regression This worked in a previous version but doesn't anymore
Projects
None yet
Development

No branches or pull requests

7 participants