VerifyError: unsorted lookupswitch

[scabug]

The following macro throws a VerifyError when run. Variations on the error are possible. There need to be enough cases to cause a lookupswitch to be generated.

import scala.reflect.makro.Context
import language.experimental.macros

object Macros {
  def m(): Unit = macro m_impl
  def m_impl(c: Context)(): c.Expr[Unit] = {
    import c.universe._
    def f(ch: Char): Any = ch match {
      case 'b' | 'B'                               => 1
      case 'c' | 'C'                               => 2
      case 'd' | 'u' | 'i' | 'o' | 'x' | 'X' | 'c' => 3
      case 'f' | 'e' | 'E' | 'g' | 'G'             => 4
      case 'h' | 'H'                               => 5
      case 's'                                     => 6
      case _                                       => 7
    }
    List('a') foreach f
    c.Expr[Unit](Block(Literal(Constant(()))))
  }
}

object Test extends App { Macros.m() }


uncaught exception during compilation: java.lang.VerifyError
error: java.lang.VerifyError: (class: Macros$, method: Macros$$f$1 signature: (C)Ljava/lang/Object;) Unsorted lookup switch
	at java.lang.Class.forName0(Native Method)
	at java.lang.Class.forName(Class.java:264)
	at scala.tools.nsc.typechecker.Macros$$anonfun$scala$tools$nsc$typechecker$Macros$$macroRuntime$2.loadMacroImpl$1(Macros.scala:702)
	at scala.tools.nsc.typechecker.Macros$$anonfun$scala$tools$nsc$typechecker$Macros$$macroRuntime$2.apply(Macros.scala:745)
	at scala.tools.nsc.typechecker.Macros$$anonfun$scala$tools$nsc$typechecker$Macros$$macroRuntime$2.apply(Macros.scala:653)
	at scala.collection.mutable.MapLike$class.getOrElseUpdate(MapLike.scala:189)
	at scala.collection.mutable.AbstractMap.getOrElseUpdate(Map.scala:91)
	at scala.tools.nsc.typechecker.Macros$class.scala$tools$nsc$typechecker$Macros$$macroRuntime(Macros.scala:653)

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-6011?orig=1
Reporter: @paulp
See #5830, #6902

[scabug]

@paulp said:
Ha ha ha, classic. Macros have nothing to do with anything, it's just when you're writing your first macro you tend to blame macros for the verify errors.

This is more than sufficient:

object Test {
  def f(ch: Char): Any = ch match {
    case 'b' | 'B'                               => 1
    case 'c' | 'C'                               => 2
    case 'd' | 'u' | 'i' | 'o' | 'x' | 'X' | 'c' => 3
    case 'f' | 'e' | 'E' | 'g' | 'G'             => 4
    case 'h' | 'H'                               => 5
    case 's'                                     => 6
    case _                                       => 7
  }
  
  def main(args: Array[String]): Unit = {
    f('a')
  }
}

[scabug]

@paulp said:
A-ha. Minimized.

object Test {
  def f(ch: Char): Any = ch match {
    case 'a' | 'b' => 1
    case 'z' | 'a' => 1
  }
  def main(args: Array[String]): Unit = f('a')
}

[scabug]

@magarciaEPFL said:
The offending bytecode instruction is:

   3:	lookupswitch{ //4
		97: 63;
		97: 56;
		98: 63;
		122: 56;
		default: 44 }

The list of int pair (match, offset) as per the JVMS "must be sorted in increasing numerical order by match."

The problem above is the duplicate match value (97) which results from 'a' matching two different case clauses (the second is unreachable for that value).

The backend can silently swallow duplicate match values but given they're constants, the error could be signalled earlier.

[scabug]

@paulp said:
The error must be signalled earlier, it's definitively unreachable code. But the backend should - not silently, emitting a warning - eliminate duplicates in the name of robustness.

[scabug]

@magarciaEPFL said:
What GenASM can do (all it can do) about this is showcased in the third commit of scala/scala#841 , ie in 4cca17da5c5236c23e32c0a3298e4a097e335a0c

[scabug]

@dragos said:
I don't know if I should file a separate ticket, but the same happens with the following correct code:

object Test {
  var cond = false
  
  def f(ch: Char): Any = ch match {
    case 'a' if cond => 1
    case 'z' | 'a' => 2
  }
  def main(args: Array[String]): Unit = f('a')
}

[scabug]

@adriaanm said:
I'm looking into fixing this, but it's a bit involved...

Technically, it depends on the granularity of the reachable entities you're considering.
The current implementation considers reachability per case, and f('z') will reach the case we think of as unreachable.

I'm trying to figure out how to consider reachability per alternative, but that's tricky to describe in general. What if you have several nested alternatives (inside other patterns) in one case?

[scabug]

@dragos said:
Adriaan, do you want me to open a separate ticket? In my example there is no unreachable code, so let me know if you want to keep this ticket for unreachability analysis and have another one for incorrect code.

For the record, you could fall back to if-then-elses if there are duplicate entries with different guards (like the old one did).

[scabug]

@paulp said:
I also just opened an unreachability ticket this morning. #6048

[scabug]

@adriaanm said:
I've looking at all of these unreachability tickets today and will continue tomorrow.
No need for a separate ticket, Iulian, I'll take care of it.

Yes, we shouldn't emit switches like this, and fall back.
I wasn't dealing with alternatives properly in the code that collapses guarded cases in switches.

[scabug]

@paulp said:

I'm trying to figure out how to consider reachability per alternative, but that's tricky to describe in general. What if you have several nested alternatives (inside other patterns) in one case?

What deters you from expanding all the alternatives up front? This was something the old matcher did which I thought was approximately correct: copy patterns around until alternatives are gone.

[scabug]

@adriaanm said:
it's an option I'm considering, at least for the sake of analyzing a match
I currently didn't need to do that, since I could just Or the corresponding propositions together

[scabug]

@adriaanm said:
scala/scala#876