UnCurry forgets to liftTree, causing java.lang.VerifyError down the road

[scabug]

I'm trying to use a modified version of https://github.com/romix/akka-kryo-serialization with Scala 2.10.0-RC5. It compiles fine (without -optimise, with the flag it crashes, but that's a different issue), but then at class load-time I get the following error:

Could not run test org.hyflow.KryoTest: java.lang.VerifyError: (class: com/romix/scala/serialization/kryo/ScalaSetSerializer, method: create signature: (Lcom/esotericsoftware/kryo/Kryo;Lcom/esotericsoftware/kryo/io/Input;Ljava/lang/Class; )Lscala/collection/Set; ) Inconsistent stack height 1 != 3

Even Soot refuses to load the class properly, and gives the following:

Considering 111: invokenonvirtual[111]
Exception in thread "main" java.lang.RuntimeException: TypeStack merging failed; unequal stack lengths: 1 and 3
	at soot.coffi.TypeStack.merge(TypeStack.java:137)
	at soot.coffi.CFG.jimplify(CFG.java:1196)
	at soot.coffi.CFG.jimplify(CFG.java:955)
	...

The code that causes the problem appears to be at the end of this block, as the three branches are collected into the final result (line labeled 111 in the 2.10 bytecode file):

var coll: Map[Any, Any] = 
if(classOf[SortedMap[_,_]].isAssignableFrom(typ)) {
// Read ordering and set it for this collection 
implicit val mapOrdering = kryo.readClassAndObject(input).asInstanceOf[scala.math.Ordering[Any]]
	try typ.getDeclaredConstructor(classOf[scala.math.Ordering[_]]).newInstance(mapOrdering).asInstanceOf[Map[Any,Any]].empty 
	catch { case _ => kryo.newInstance(typ).asInstanceOf[Map[Any,Any]].empty }
} else {
	kryo.newInstance(typ).asInstanceOf[Map[Any,Any]].empty
}

This code worked on 2.9.1, and it appears the generated bytecode is indeed different. I've attached the source code excerpt and disassembled bytecode for 2.9.1 and 2.10.0-RC5, and highlighted the line with the problem in the 2.10 bytecode.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-6863?orig=1
Reporter: Alex Turcu (talex)
Assignee: @JamesIry
Affected Versions: 2.10.0-RC5, 2.10.0, 2.11.0
Attachments:

• scala-2.10.txt (created on Dec 22, 2012 11:00:29 PM UTC, 6723 bytes)
• scala-2.9.scala (created on Dec 22, 2012 11:00:29 PM UTC, 1213 bytes)
• scala-2.9.shimp (created on Dec 22, 2012 11:00:29 PM UTC, 20734 bytes)
• scala-2.9.txt (created on Dec 22, 2012 11:00:29 PM UTC, 5566 bytes)

[scabug]

Alex Turcu (talex) said:
The minimal test case that generates the error seems to be:

def test(kryo: Kryo, input:Input, typ: Class[Map[_,_]]): Map[_,_] = {
	val len = 7
	var coll: Map[Any, Any] = {
		try { 
			val someVar = null;
			Map[Any,Any]().empty 
		} catch { 
			case _ => Map[Any,Any]().empty 
		}
	}
	0 until len foreach {_ => coll += Tuple2( 0, 0) }
	coll
}

Looks similar to #5380 , and seems to be related to the wrapping of "coll" into a scala.runtime.ObjectRef . someVar is required but probably just prevents some other optimization.

[scabug]

@magarciaEPFL said:
The snippet in [#comment-61645] doesn't cause a VerifyError as of v2.10.0 (after removing the method params to make the snippet self-contained). Some of the differences with the snippet in the Description must explain why the VerifyError appears there. It would be great if you could minimize into a self-contained program.

[scabug]

Alex Turcu (talex) said:
How about this?

object Main extends App {
	def test(): Map[_,_] = {
		//val typ = classOf[Map[Int,Int]]
		var coll: Map[Int, Int] = {
			val key = 4
			try {
				Map[Int,Int](key -> 5).empty 
			} catch { case _ => Map[Int,Int](2 -> 3).empty }
		}
		0 until 7 foreach {_ => coll += Tuple2( 0, 0) }
		coll
	}
}

It fails for me using 2.10.0-RC5 and:

#!/bin/bash
rm ./*.class
scalac  bug.scala
scala -classpath . Main

[scabug]

@magarciaEPFL said:
Further minimization:

object Test {

  def main(args: Array[String]) {

    var coll = {
      val key = 4
      try   { null }
      catch { case _ => null }
    }

    { () => coll } // the purpose of this is making `coll` an ObjectRef

  }
}

After compiling with v2.10.0 and master we get:

java.lang.VerifyError: (class: Test$, method: main signature: ([Ljava/lang/String;)V) Inconsistent stack height 1 != 3

[scabug]

@magarciaEPFL said:
As a sidenote, removing val key = 4 also removes the VerifyError: the emitted bytecode contains two code sections, one for the try-clause and another for the catch-clause (both doing the same, ie building an ObjectRef with null as payload). In this case, there's no VerifyError because on control-flow merge those stacks have same height.

[scabug]

@magarciaEPFL said:
Back to the example in [#comment-61651]. Here's the javap:

public void main(java.lang.String[]);
  Code:
   0:   new     #16; //class scala/runtime/ObjectRef
   3:   dup
   4:   iconst_4
   5:   istore_3
   6:   aconst_null
   7:   goto    12
   10:  pop
   11:  aconst_null
   12:  pop
   13:  aconst_null
   14:  invokespecial   #19; //Method scala/runtime/ObjectRef."<init>":(Ljava/lang/Object;)V
   17:  astore_2
   18:  new     #21; //class Test$$anonfun$main$1
   21:  dup
   22:  aload_2
   23:  invokespecial   #24; //Method Test$$anonfun$main$1."<init>":(Lscala/runtime/ObjectRef;)V
   26:  pop
   27:  return
  Exception table:
   from   to  target type
     6    10    10   any

Two blocks (B1 and B2) get merged at instruction 12. B1 comprises instructions [0 to 7] and B2 (an exception handler) [10 to 11].

On exit from B1, the stack is [ObjectRef ObjectRef null]
On exit from B2, the stack is [null]
Therefore the VerifyError Inconsistent stack height 1 != 3

Usually liftTree() in UnCurry avoids the situation above, by creating a local method for the try expression:

 *  - convert try-catch expressions in contexts where there might be values on the stack to
 *      a local method and a call to it (since an exception empties the evaluation stack):
 *
 *      meth(x_1,..., try { x_i } catch { ..}, .. x_b0) ==>
 *        {
 *          def liftedTry$1 = try { x_i } catch { .. }
 *          meth(x_1, .., liftedTry$1(), .. )
 *        }

That would have saved the day.

[scabug]

@JamesIry said (edited on Jan 8, 2013 6:19:35 PM UTC):
Appears to be related to scala/scala@b2f3fb2

[scabug]

@JamesIry said:
Here's the story.

Remove some redundant code
scala/scala@b2f3fb2

Remove the code that it was redundant to, so now it
can't work
scala/scala@beb8751

Then destroy the evidence that it ever existed
scala/scala@ffc2389

Moral of the story: tests are good.

[scabug]

@JamesIry said:
scala/scala#1870

[scabug]

@magarciaEPFL said:
There is a (way) simpler solution. The bug results from UnCurry not anticipating that the location of a try-catch will become non-statement after LambdaLift. That's because LambdaLift turns a statement-position try-catch into non-statement-position (by giving the enclosing RHS as argument to new OBjectRef(initialValue). The only way to lower such New() is:

NEW ObjectRef
DUP
... instructions loading initialValue
INVOKESPECIAL scala.runtime.ObjectRef.<init>(initialValue)

Alternatively, if the above were lowered into:

... instructions loading initialValue
INVOKESTATIC scala.runtime.ObjectRef.create(initialValue)

then UnCurry wouldn't need to anticipate anything (no code resurrection, no code duplication, more compact code). For bonus points, it would be great to have:

INVOKESTATIC scala.runtime.ObjectRef.zero()

which returns an ObjectRef initialized to null. Similarly for the zeroes of IntRef and others.

About binary compatibility, what if ObjectRef et al. had been designed from the start with the above in mind? It's never too late.

[scabug]

@JamesIry said:
I totally agree that that's a cleaner solution. But it would have to wait until 2.11 when we can break forward binary compatibility by adding the factory methods to ObjectRef.

[scabug]

@JamesIry said (edited on Jan 18, 2013 4:49:17 PM UTC):
An alternative that doesn't break binary compatibility is

var x = try{...}catch{...}

transforms to

val temp$ = try {...}catch{...}
var x = temp$

which, when x is captured, turns turns into

... instructions loading initialValue
STORE temp$
NEW ObjectRef
DUP
LOAD temp$
INVOKESPECIAL scala.runtime.ObjectRef.<init>(initialValue)

It wastes a variable slot in cases when var is not captured, though (unless we're smarter about optimizing away variables than I think we are), so we'd want to replace it with the cleaner static factory version in 2.11.

[scabug]

@adriaanm said:
Based on a meatspace discussion with James, I agree we should pursue Miguel's factory approach for 2.11 and try to implement James's extra-variable fix for 2.10.1-RC1.

[scabug]

@magarciaEPFL said:
The extra-variable is actually lightweight, and apparently LambdaLift isn't too late to apply it (I'm guessing here). Perhaps detecting new Foo(try{...}catch{...}) during LambdaLift is also amenable to a local rewriting

var temp = try {} catch {}
new Foo(temp)

I agree getting this fixed first in a binary-compatible way is the best for now.