On jump removal once again

2011/6/13 Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com>

Hi,
Miguel created a plugin for goto elimination. Something very valuable to Scala+GWT project. I finally had a spare evening to sync our one-year-old nsc fork with current I could give that plug-in a whirl.
I found a problem with that plug-in that can be shown using very simple example:

 [...] 

Anyway, I'm wondering if exact semantics for LabelDefs are defined somewhere. What kind of constructs are legal and what not? Specifically, is situation above considered only suboptimal or plain broken and instead of fixing the plug-in I should be fixing logic that emits equals method for case classes?

Only now I realized that equals is implemented using pattern matching so whatever I see in equals for case classes I can see in any other place. In other words: I'd need to fix (assuming that such trees as above are invalid) pattern matching. Having heard so many scary stories about pattern matching I'll assume that this problem is not fixable by me and I need to defend myself from it down compiler pipeline. I'll try to fix gotoelim plug-in.
--
Grzegorz Kossakowski

If I'm interpreting that error message correctly, the plugin is choking because there's no Apply corresponding to the LabelDef?  It seems to me that the plugin could either ignore such labels or optimize them away.  Collecting and checking the parameters that are used in the label body seems like unnecessary overhead.
In general, if there's no jump to a label, can't the label be removed from the tree?  In this example, it's pretty clear that it could be rewritten
    if (A.this.gd1$1(a$1, b$1)) x$1.$asInstanceOf[A]().canEqual(A.this)    else ...
Generally, if the label *did* use those parameters, they would get their values from the lexical scope of the Label when arrived at along a normal execution path (as opposed to a jump).

2011/6/13 Aaron Novstrup <aaron.novstrup@gmail.com>

If I'm interpreting that error message correctly, the plugin is choking because there's no Apply corresponding to the LabelDef?  It seems to me that the plugin could either ignore such labels or optimize them away.  Collecting and checking the parameters that are used in the label body seems like unnecessary overhead.

Actually, plug-in already does it for parameterless LabelDefs. What I'm proposing is to calculate real list of parameters that are actually used. 

In general, if there's no jump to a label, can't the label be removed from the tree?  In this example, it's pretty clear that it could be rewritten
    if (A.this.gd1$1(a$1, b$1)) x$1.$asInstanceOf[A]().canEqual(A.this)     else ...
Generally, if the label *did* use those parameters, they would get their values from the lexical scope of the Label when arrived at along a normal execution path (as opposed to a jump).

Yes, you are right. However, if we are dropping some trees we should be very confident that it's a correct thing to do. Dropping LabelDefs silently might turn out to obscure some bug in pattern matcher. I prefer to fail fast especially because jvm backend deals with LabelDefs differently and might be forgiving to some trees we cannot. One example is here:
https://groups.google.com/d/topic/scala-internals/pN5pu7ljxoE/discussion

--
Grzegorz Kossakowski

What about the option of just ignoring those LabelDefs, then, rather
than issuing an error? The jribble backend should be able to handle
labels -- it's just Apply that's the hard part, right?

On Mon, Jun 13, 2011 at 3:08 PM, Grzegorz Kossakowski
wrote:
> 2011/6/13 Aaron Novstrup
>>
>> If I'm interpreting that error message correctly, the plugin is choking
>> because there's no Apply corresponding to the LabelDef?  It seems to me that
>> the plugin could either ignore such labels or optimize them away.
>>  Collecting and checking the parameters that are used in the label body
>> seems like unnecessary overhead.
>
> Actually, plug-in already does it for parameterless LabelDefs. What I'm
> proposing is to calculate real list of parameters that are actually used.
>
>>
>> In general, if there's no jump to a label, can't the label be removed from
>> the tree?  In this example, it's pretty clear that it could be rewritten
>>     if (A.this.gd1$1(a$1, b$1)) x$1.$asInstanceOf[A]().canEqual(A.this)
>>     else ...
>> Generally, if the label *did* use those parameters, they would get their
>> values from the lexical scope of the Label when arrived at along a normal
>> execution path (as opposed to a jump).
>
> Yes, you are right. However, if we are dropping some trees we should be very
> confident that it's a correct thing to do. Dropping LabelDefs silently might
> turn out to obscure some bug in pattern matcher. I prefer to fail fast
> especially because jvm backend deals with LabelDefs differently and might be
> forgiving to some trees we cannot. One example is here:
> https://groups.google.com/d/topic/scala-internals/pN5pu7ljxoE/discussion
>
> --
> Grzegorz Kossakowski
>
>

On 6/13/11 2:08 PM, Grzegorz Kossakowski wrote:
> Only now I realized that equals is implemented using pattern matching so
> whatever I see in equals for case classes I can see in any other place.
> In other words: I'd need to fix (assuming that such trees as above are
> invalid) pattern matching. Having heard so many scary stories about
> pattern matching I'll assume that this problem is not fixable by me and
> I need to defend myself from it down compiler pipeline. I'll try to fix
> gotoelim plug-in.

-1!

Despite all the scary stories you may have heard, it has been years
since anyone besides me has looked at the pattern matcher, other than
perhaps from a speeding vehicle of some kind. So I'm the only one who
can spin scary stories firsthand, and it's not that scary anymore. Why
not listen to the little creature on your other shoulder, the one not
equipped with horns and a red suit, I think that's a halo there, and go
after the problem where it arises.

2011/6/14 Aaron Novstrup <aaron.novstrup@gmail.com>

What about the option of just ignoring those LabelDefs, then, rather
than issuing an error?  The jribble backend should be able to handle
labels -- it's just Apply that's the hard part, right?

What do you mean by ignoring? Completely dropping the tree, including right hand side of LabelDef?
--
Grzegorz Kossakowski

2011/6/14 Paul Phillips <paulp@improving.org>

-1!
Despite all the scary stories you may have heard, it has been years
since anyone besides me has looked at the pattern matcher, other than
perhaps from a speeding vehicle of some kind.  So I'm the only one who
can spin scary stories firsthand, and it's not that scary anymore.  

:-)Actually, there was another person that advised me against trying to fix pattern matcher so you don't take all the credit ;-)  

Why
not listen to the little creature on your other shoulder, the one not
equipped with horns and a red suit, I think that's a halo there, and go
after the problem where it arises.

Those problems I encounter feel like should be fixed where they arise. That's right. I promise to have a look into pattern matcher once I'll be surrounded by people knowing nsc so I can prepare a list of question for a lunch, everyday. In short: I'll try to have a look once I move to Lausanne (in three weeks).

--
Grzegorz Kossakowski

Hi, 
Great to see this lively discussion on LabelDefs, so late at night. 

----- (1) ----- 
The LabelDef emitted in method equals of the example: 
  case class A(a: Int, b: String)
is fine. Why does the gotoelim plugin report as an error those LabelDef without accompanying goto? Just to call our attention. Not an error really. 


----- (2) ----- 
What about replacing that LabelDef with its rhs? To answer that, more than -Xprint:cleanup is needed, because that doesn't show symbols. Additionally, -Yshow-trees -uniqid. 
The semantics of LabelDef are covered in the write-up at   http://lamp.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/2011Q1/JumpsRemover.pdf
Depending on what you're after, you may want to dig deeper. Like so: 
// GenICode
        case LabelDef(name, params, rhs) =>          val ctx1 = ctx.newBlock
          if (nme.isLoopHeaderLabel(name))
            ctx1.bb.loopHeader = true

          ctx1.labels.get(tree.symbol) match {
            case Some(label) =>
              log("Found existing label for " + tree.symbol)
              label.anchor(ctx1.bb)
              label.patch(ctx.method.code)

            case None =>
              val pair = (tree.symbol -> (new Label(tree.symbol) anchor ctx1.bb setParams (params map (_.symbol))))
              log("Adding label " + tree.symbol + " in genLoad.")
              ctx1.labels += pair
              ctx.method.addLocals(params map (p => new Local(p.symbol, toTypeKind(p.symbol.info), false)));
          }

          ctx.bb.closeWith(JUMP(ctx1.bb), tree.pos)
          genLoad(rhs, ctx1, expectedType /*toTypeKind(tree.symbol.info.resultType)*/)


----- (3) ----- 

BTW, the gotoelim plugin and its documentation are "work in progress". The plugin classifies the trees to transform as per the algorithm by Erosa and Hendren, but it does not fully implement that algorithm. 


Cheers, 
Miguel http://lamp.epfl.ch/~magarcia/ScalaNET/

2011/6/14 Miguel Garcia <mgarcia512@yahoo.com>

Hi, 
Great to see this lively discussion on LabelDefs, so late at night. 

Great to see you joining it so late at night!
 

----- (1) ----- 
The LabelDef emitted in method equals of the example: 
  case class A(a: Int, b: String)
is fine. Why does the gotoelim plugin report as an error those LabelDef without accompanying goto? Just to call our attention. Not an error really.

Ok. So pattern matcher shouldn't be blamed for emitting LabelDefs with parameters that are never used, right?
 

----- (2) ----- 
What about replacing that LabelDef with its rhs? To answer that, more than -Xprint:cleanup is needed, because that doesn't show symbols. Additionally, -Yshow-trees -uniqid. 

Not sure why because:  body%01(a$1,b$1){                x$1.$asInstanceOf[A]().canEqual(A.this)              }
Looks quite clear to me. Anyway, at the end of my e-mail you'll find that LabelDef printed using -Yshow-trees -uniqid.  

The semantics of LabelDef are covered in the write-up at   http://lamp.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/2011Q1/JumpsRemover.pdf

Does it address the question about unused parameters? I fail to find relevant fragment.
 

Depending on what you're after, you may want to dig deeper. Like so: 
// GenICode
        case LabelDef(name, params, rhs) =>          val ctx1 = ctx.newBlock
          if (nme.isLoopHeaderLabel(name))
            ctx1.bb.loopHeader = true

          ctx1.labels.get(tree.symbol) match {
            case Some(label) =>
              log("Found existing label for " + tree.symbol)
              label.anchor(ctx1.bb)
              label.patch(ctx.method.code)

            case None =>
              val pair = (tree.symbol -> (new Label(tree.symbol) anchor ctx1.bb setParams (params map (_.symbol))))
              log("Adding label " + tree.symbol + " in genLoad.")
              ctx1.labels += pair
              ctx.method.addLocals(params map (p => new Local(p.symbol, toTypeKind(p.symbol.info), false)));
          }

          ctx.bb.closeWith(JUMP(ctx1.bb), tree.pos)
          genLoad(rhs, ctx1, expectedType /*toTypeKind(tree.symbol.info.resultType)*/)


----- (3) ----- 

BTW, the gotoelim plugin and its documentation are "work in progress". The plugin classifies the trees to transform as per the algorithm by Erosa and Hendren, but it does not fully implement that algorithm. 

Miguel,
Is there any chance for you to finish it any time soon? I've reached a point in scalagwt project where my simple heuristics for dealing with forward jumps fall short and I need a real solution.
--
Grzegorz Kossakowski

Grzegorz, 
Looks like I won't be able to improve gotoelim for a while. The option of replacing Match trees with Blocks, Ifs, and temp vars before explicitouter can get its hands at it seems in fact like a shourter route. Not necessarily by patching the compiler, a compiler plugin can do that. 
A good example on creating temp vars and such can be found in cleanup: 
      /* rewrite all try blocks with a result != {Unit, All} such that they       * store their result in a local variable. The catch blocks are adjusted as well.
       * The try tree is subsituted by a block whose result expression is read of that variable. */

      case theTry @ Try(block, catches, finalizer)         if theTry.tpe.typeSymbol != definitions.UnitClass && theTry.tpe.typeSymbol != definitions.NothingClass =>
        val tpe = theTry.tpe.widen
        val tempVar = currentOwner.newVariable(theTry.pos, mkTerm(nme.EXCEPTION_RESULT_PREFIX)).setInfo(tpe)
        def assignBlock(rhs: Tree) = super.transform(BLOCK(Ident(tempVar) === transform(rhs)))
        
        val newBlock    = assignBlock(block)
        val newCatches  = for (CaseDef(pattern, guard, body) <- catches) yield
          (CASE(super.transform(pattern)) IF (super.transform(guard))) ==> assignBlock(body)
        val newTry      = Try(newBlock, newCatches, super.transform(finalizer))
                
        typedWithPos(theTry.pos)(BLOCK(VAL(tempVar) === EmptyTree, newTry, Ident(tempVar)))



Miguel http://lamp.epfl.ch/~magarcia/ScalaNET/

2011/6/14 Miguel Garcia <mgarcia512@yahoo.com>

Grzegorz, 
Looks like I won't be able to improve gotoelim for a while. The option of replacing Match trees with Blocks, Ifs, and temp vars before explicitouter can get its hands at it seems in fact like a shourter route. Not necessarily by patching the compiler, a compiler plugin can do that. 

Not sure if I follow you here. Do you propose to reimplemented pattern matching logic with Blocks, Ifs and temp vars as a simple replacement for sophisticated logic of current pattern matching? This doesn't sound very simple to me but I don't know that much about this area.
--
Grzegorz Kossakowski

I know that the rewriting of Match expressions is not easy, however I can't say that the gotoelim approach would be significantly easier either. The original formulation of the Erosa-Herden algorithm is based on three-address code, and the ASTs after CleanUp are more complex than that. 
Regarding rewriting Match expressions, there are two aspects to it: 
  (a) determining what kind of patterns its contains (that's Secs. 8.1.1 to 8.1.14 in SLS);  (b) the optimization of patterns eval. 
When I said, "rewriting Match into Ifs, Blocks, and temp vars", yes, I should have added that (a) is a pre-requisite for that. Even then, that rewriting will be way less efficient than the optimized one. 
Summing up. No clue where (a) happens in the compiler, but gotoelim doesn't seem that easy either. 
Miguelhttp://lamp.epfl.ch/~magarcia/ScalaNET/

On 6/13/11 5:56 PM, Miguel Garcia wrote:
> (a) determining what kind of patterns its contains (that's Secs. 8.1.1
> to 8.1.14 in SLS);
> Summing up. No clue where (a) happens in the compiler, but gotoelim
> doesn't seem that easy either.

Patterns.scala:

val p = tree match {
case x: Bind => apply(unbind(tree)) withBoundTree x
case EmptyTree => WildcardPattern()
case Ident(nme.WILDCARD) => WildcardPattern()
case x @ Alternative(ps) => AlternativePattern(x)
case x: Apply => ApplyPattern(x)
case x: Typed => TypedPattern(x)
case x: Literal => LiteralPattern(x)
case x: UnApply => UnapplyPattern(x)
case x: Ident => if (isVarPattern(x)) VariablePattern(x) else SimpleIdPattern(x)
case x: ArrayValue => SequencePattern(x)
case x: Select => StableIdPattern(x)
case x: Star => StarPattern(x)
case x: This => ThisPattern(x) // XXX ?
case _ => abortUnknownTree(tree)
}

2011/6/14 Paul Phillips <paulp@improving.org>

On 6/13/11 5:56 PM, Miguel Garcia wrote:
>   (a) determining what kind of patterns its contains (that's Secs. 8.1.1
> to 8.1.14 in SLS);
> Summing up. No clue where (a) happens in the compiler, but gotoelim
> doesn't seem that easy either.

Patterns.scala:

     val p = tree match {
       case x: Bind              => apply(unbind(tree)) withBoundTree x
       case EmptyTree            => WildcardPattern()
       case Ident(nme.WILDCARD)  => WildcardPattern()
       case x @ Alternative(ps)  => AlternativePattern(x)
       case x: Apply             => ApplyPattern(x)
       case x: Typed             => TypedPattern(x)
       case x: Literal           => LiteralPattern(x)
       case x: UnApply           => UnapplyPattern(x)
       case x: Ident             => if (isVarPattern(x)) VariablePattern(x) else SimpleIdPattern(x)
       case x: ArrayValue        => SequencePattern(x)
       case x: Select            => StableIdPattern(x)
       case x: Star              => StarPattern(x)
       case x: This              => ThisPattern(x) // XXX ?
       case _                    => abortUnknownTree(tree)
     }

Thanks a lot for your suggestions. I'll try to have a look into that once I have some more free time.

--
Grzegorz Kossakowski

Grzegorz, 

Perhaps the AST transformation described next can prevent jumps from being generated in the first place (thus, it's totally unrelated to my previous attempt [1]). 
Briefly, the transform relies on the  assumption that `matchTranslation` won't emit jumps for ASTs of the form: 
  <selector> match {    case <pattern1> if <guard1> => <body1>    case _ => ()  }
So far I haven't found a counterexample, to know for sure someone should dive into `matchTranslation`. Not today. 
The usual remarks apply: the goal is to preserve semantics but not performance (in the resulting AST the pattern-matching-optimizer can't optimize across case clauses, and thus can't insert GOTOs). Code size will increase in general. On the plus side, no restrictions are placed on patterns, guards, or case-clause bodies, we just copy them verbatim, and let `matchTranslation` handle them afterwards. 
Let me know if it works. It would be a useful building block for "source-code backends" in general (not just when translating into JavaScript but also into C# 3.0, Objective-C, and a long etc). 

Miguelhttp://lamp.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

Original program
I'm using as running example the code you posted a while ago ("YouBadPatternMatcher"). 

class YouBadPatternMatcher {  def problematicPattern = {    try {      0    } catch {      case x: Exception if x.getMessage == "test" => println("first case " + x)      case x => println("second case " + x)    }  }}

First transform

Rephrase mutliple catch clauses in terms of an explicit match expression (that's ok with SLS 6.22). This way, the second and last transform has to deal with match expressions only. 
class YouBadPatternMatcher {  def problematicPattern = {    try {      0    } catch {      case exc =>         exc match {          case x: Exception if x.getMessage == "test" => println("first case " + x)          case x => println("second case " + x)        }        throw exc // this might be dead code, depending on the cases above. But in any case it's not wrong, and leaving it out might well be wrong.     }  }}
Second transform
Break up a multi-case match expression dedicating a match expression for each case-clause. This requires: 
  a) evaluating the selector once and storing it in a temp var   b) if the match expression evals to some value,      ie. if (!isVoid(expr) where 
       def isVoid(tree: Tree): Boolean = {         val ts  = tree.tpe.typeSymbol         (ts == definitions.UnitClass) || (ts == definitions.NothingClass)       }      then we need a temp var for the result. 
  Say we have case-clauses 1 to N:
       <originalSelector> match {          case p1 if cond1 => body1          . . .            case pN if condN => bodyN        }
  This AST transformation replaces the above with a Block expression, as follows: 
     { // start of Block 
       val selector  = <originalSelector>       var matchDone = false        var result : <tpe of original match expression>   = _  // if original match not void
       selector match {          case p1 if cond1 =>             matchDone = true             result = body1 // or just `body1` if the original match evaluates to Nothing or Unit, as explained above.            case _ => () // emitted to avoid a MatchError       }
       if(!matchDone) {          selector match {            case p2 if cond2 =>               matchDone = true               result = body2 // or just `body2`, see above.              case _ => () // emitted to avoid a MatchError         }      } 
      . . . 
       if(!matchDone) {          selector match {            case pN if condN =>               matchDone = true               result = bodyN // or just `bodyN`, see above.              // don't emit case _ => ()         }      } 
      result // in case a `result` temp var was emitted, EmptyTree otherwise. 
    } // end of Block 

In terms of the original example: 
class YouBadPatternMatcher {  def problematicPattern = {    try {      0    } catch {      case exc => 
      {        val selector  = exc         var matchDone = false 
        selector match {          case x: Exception if x.getMessage == "test" =>             matchDone = true            println("first case " + x)          case _ =>             ()        }
        if(!matchDone) {          selector match {            case x if x.toString.length > 2 =>               matchDone = true              println("second case " + x)          }        }
      }
      throw exc
    }  }}

Comments

1. Some LabelDefs are emitted. But they are targeted from no GOTO. Each such LabelDef can be replaced by its rhs
   
   
2. The transformation above takes care of try expressions and match expressions that are present in source (i.e., non-synthetic). CleanUp lowers an ApplyDynamic into a try expression, but in a manner that does not introduce jumps. I guess no other phase introduces jumps. 
   
   
3. As to the implementation, running right before explicitouter should do it. Given that the transformation has two steps, a multi-component compiler plugin could be used, alternatively a single Transformer that invokes others (example: the plugin to convert into a C-like language [2] has the DoAllWork transformer invoke the Blockify and Stmtify helper transformers).  

References 

[1] http://lamp.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/2011Q1/JumpsRemover.pdf 
[2] http://lampsvn.epfl.ch/trac/scala/browser/scala-experimental/trunk/imp/src/Imperating.scala

And here goes the first patch. For the first transform, "throw exc" shouldn't be unconditional but only if not case-clause matched. How to emit code to check that? Initial thoughts: either by checking the last case-clause for irrefutability, or by keeping a `matchDone' temp var as in the second transform. 
One more thing. Starting with 2.9 there's "Generalized try-catch-finally". I guess the transform as described can handle it but I hadn't thought initially about those AST shapes. Quoting from http://www.scala-lang.org/node/9483 
---- begin quote ---- 
try bodycatch handlerfinally cleanup
Here, body and cleanup can be arbitrary expressions, and handler can be any expression which evaluates to a valid exception handler (which is: PartialFunction[Throwable, T]).
---- end quote ---- 

It looks like preserving performance and code size characteristics would be a worthy goal. I would like to propose the following pattern once more. I think it should work well for most cases but I haven't thought through all possible details of course. So I'd be interested in learning about cases where you think it won't work ...
Say you have the following code (with jumps):
l0: foobar     barfoo     goto l2l1:...    goto l3l2:....    gotol1l3:...    // fall through and exit
Translate to (JavaScript syntax):
var pc = 0var keepgoing = truewhile (keepgoing) {  switch (pc) {    case 0:      // code for l0      pc = 2 // goto l2      break    case 1:      // code for l1      pc = 3 // goto l3      break    case 2:      // code for l2      pc = 1 // goto l1      break    case 3:      // code for l3      keepgoing = false      break  }}
You will need to hoist some variable declarations outside the loop to make sure the code is well-scoped.
Cheers,- Tiark

On Jul 6, 2011, at 11:26 PM, Miguel Garcia wrote:

And here goes the first patch. For the first transform, "throw exc" shouldn't be unconditional but only if not case-clause matched. How to emit code to check that? Initial thoughts: either by checking the last case-clause for irrefutability, or by keeping a `matchDone' temp var as in the second transform. 
One more thing. Starting with 2.9 there's "Generalized try-catch-finally". I guess the transform as described can handle it but I hadn't thought initially about those AST shapes. Quoting from http://www.scala-lang.org/node/9483 
---- begin quote ---- 
try bodycatch handlerfinally cleanup
Here, body and cleanup can be arbitrary expressions, and handler can be any expression which evaluates to a valid exception handler (which is: PartialFunction[Throwable, T]).
---- end quote ---- 

Hi, 
Just to see it in a larger example, I'm pasting below the -Xprint:cleanup output for the YouBadPatternMatcher example. 
I see no problem w.r.t. functional correctness once the whole method is converted into a big switch (I guess after turning structured control flow into gotos, to avoid special casing them). 
If we want to keep the exception handling semantics (in a Scala to Scala transform that's an issue) then "which instruction ranges are covered by which handlers" should also be part of the deal. 
And readability suffers under all approaches, so I guess it doesn't count. 
One of the good things about flexible problem statements is the large number of solutions they can motivate! :-) 

Miguel http://lamp.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/


[[syntax trees at end of cleanup]]// Scala source: YouBadPatternMatcher.scalapackage <empty> {  class YouBadPatternMatcher extends java.lang.Object with ScalaObject {    def problematicPattern(): java.lang.Object = {      var exceptionResult1: java.lang.Object = _;      try {        exceptionResult1 = scala.Int.box(0)      } catch {        case (ex$1 @ _) => {          exceptionResult1 = {            {              <synthetic> val temp1: java.lang.Throwable = ex$1;              if (temp1.$isInstanceOf[java.lang.Exception]())                {                  <synthetic> val temp2: java.lang.Exception = temp1.$asInstanceOf[java.lang.Exception]();                  val x: java.lang.Exception = temp2;                  if (YouBadPatternMatcher.this.gd1$1(x))                    {                      {                        scala.this.Predef.println("first case ".+(temp2));                        scala.runtime.BoxedUnit.UNIT                      }                    }                  else                    {                      val x: java.lang.Throwable = temp2;                      body%1(x){                        scala.this.Predef.println("second case ".+(x));                        scala.runtime.BoxedUnit.UNIT                      }                    }                }              else                {                  body%1(temp1);                  scala.runtime.BoxedUnit.UNIT                }            }          }        }      };      exceptionResult1    };    final <synthetic> private[this] def gd1$1(x$1: java.lang.Exception): Boolean = x$1.getMessage().==("test");    def this(): YouBadPatternMatcher = {      YouBadPatternMatcher.super.this();      ()    }  }}

On 6 July 2011 20:59, Miguel Garcia <mgarcia512@yahoo.com> wrote:

Grzegorz, 

Perhaps the AST transformation described next can prevent jumps from being generated in the first place (thus, it's totally unrelated to my previous attempt [1]). 
Briefly, the transform relies on the  assumption that `matchTranslation` won't emit jumps for ASTs of the form: 
  <selector> match {     case <pattern1> if <guard1> => <body1>    case _ => ()  }
So far I haven't found a counterexample, to know for sure someone should dive into `matchTranslation`. Not today. 

Miguel,
I found a counterexample, see:
mac-grek:scalapatterns grek$ cat patterns.scala class X {    def p2(xs: List[Int]) = xs match {    case a :: (1 :: Nil | 2 :: Nil) => println(a)     case _ => ()  }  }mac-grek:scalapatterns grek$ scalac -Xprint:cleanup patterns.scala [[syntax trees at end of cleanup]]// Scala source: patterns.scala package <empty> {  class X extends java.lang.Object with ScalaObject {    def p2(xs: List): Unit = {      <synthetic> val temp1: List = xs;      if (temp1.$isInstanceOf[scala.collection.immutable.::]())         {          <synthetic> val temp2: scala.collection.immutable.:: = temp1.$asInstanceOf[scala.collection.immutable.::]();          <synthetic> val temp3: Int = scala.Int.unbox(temp2.hd$1());           <synthetic> val temp4: List = temp2.tl$1();          if (temp4.$isInstanceOf[scala.collection.immutable.::]())            {              <synthetic> val temp5: scala.collection.immutable.:: = temp4.$asInstanceOf[scala.collection.immutable.::]();               <synthetic> val temp7: List = temp5.tl$1();              (scala.Int.unbox(temp5.hd$1()): Int) match {                case 1 => if (immutable.this.Nil.==(temp7))                   {                    val a: Int = temp3;                    body%01(a){                      scala.this.Predef.println(scala.Int.box(a))                    }                   }                else                  {                    ()                  }                case 2 => if (immutable.this.Nil.==(temp7))                   {                    body%01(temp3)                  }                else                  {                    ()                  }                 case _ => {                  ()                }              }            }          else            {              ()             }        }      else        {          ()        }    };    def this(): X = {      X.super.this();      ()     }  }} By playing around with pattern alternative in parenthesis you can make it arbitrarily complex causing pattern matching logic to emit forward jumps deeply nested in ASTs.
I think it's clear that general solution dealing with forward jumps is the only way to go. I'll be investigating FSM (AKA "big switch") route proposed by others. I'll start with gathering info about all shapes of ASTs containing forward jumps.

--
Grzegorz Kossakowski

Hey,
i think one would not need to translate all control flow to gotos, just the smallest enclosing tree which contains the jump labels and targets. Below is a possible translation of the example, leaving the try/catch as it is.
- Tiark
[[syntax trees at end of cleanup]]// Scala source: YouBadPatternMatcher.scalapackage <empty> {  class YouBadPatternMatcher extends java.lang.Object with ScalaObject {    def problematicPattern(): java.lang.Object = {      var exceptionResult1: java.lang.Object = _;      try {        exceptionResult1 = scala.Int.box(0)      } catch {        case (ex$1 @ _) => {          exceptionResult1 = {            {              <synthetic> val temp1: java.lang.Throwable = ex$1;              <synthetic> var temp2: java.lang.Exception = null; // moved out of conditional and turned into a var              var x1: java.lang.Exception = null;              var x2: java.lang.Throwable = null;              if (temp1.$isInstanceOf[java.lang.Exception]())                goto %A              else                goto %B
              %A: {                  temp2 = temp1.$asInstanceOf[java.lang.Exception]();                  x1 = temp2;                  if (YouBadPatternMatcher.this.gd1$1(x1))                    goto %C                  else                    goto %D              }                  %C: {                        scala.this.Predef.println("first case ".+(temp2));                        scala.runtime.BoxedUnit.UNIT                      }                  %D: {                      x2 = temp2;                      goto %E                    }                  %E: {                      scala.this.Predef.println("second case ".+(x2));                      scala.runtime.BoxedUnit.UNIT                    }              %B: {                  x2 = temp1                  goto %E                }          }        }      };      exceptionResult1    };    final <synthetic> private[this] def gd1$1(x$1: java.lang.Exception): Boolean = x$1.getMessage().==("test");    def this(): YouBadPatternMatcher = {      YouBadPatternMatcher.super.this();      ()    }  }}


On Jul 7, 2011, at 6:36 PM, Miguel Garcia wrote:

Hi, 
Just to see it in a larger example, I'm pasting below the -Xprint:cleanup output for the YouBadPatternMatcher example. 
I see no problem w.r.t. functional correctness once the whole method is converted into a big switch (I guess after turning structured control flow into gotos, to avoid special casing them). 
If we want to keep the exception handling semantics (in a Scala to Scala transform that's an issue) then "which instruction ranges are covered by which handlers" should also be part of the deal. 
And readability suffers under all approaches, so I guess it doesn't count. 
One of the good things about flexible problem statements is the large number of solutions they can motivate! :-) 

Miguel http://lamp.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/


[[syntax trees at end of cleanup]]// Scala source: YouBadPatternMatcher.scalapackage <empty> {  class YouBadPatternMatcher extends java.lang.Object with ScalaObject {    def problematicPattern(): java.lang.Object = {      var exceptionResult1: java.lang.Object = _;      try {        exceptionResult1 = scala.Int.box(0)      } catch {        case (ex$1 @ _) => {          exceptionResult1 = {            {              <synthetic> val temp1: java.lang.Throwable = ex$1;              if (temp1.$isInstanceOf[java.lang.Exception]())                {                  <synthetic> val temp2: java.lang.Exception = temp1.$asInstanceOf[java.lang.Exception]();                  val x: java.lang.Exception = temp2;                  if (YouBadPatternMatcher.this.gd1$1(x))                    {                      {                        scala.this.Predef.println("first case ".+(temp2));                        scala.runtime.BoxedUnit.UNIT                      }                    }                  else                    {                      val x: java.lang.Throwable = temp2;                      body%1(x){                        scala.this.Predef.println("second case ".+(x));                        scala.runtime.BoxedUnit.UNIT                      }                    }                }              else                {                  body%1(temp1);                  scala.runtime.BoxedUnit.UNIT                }            }          }        }      };      exceptionResult1    };    final <synthetic> private[this] def gd1$1(x$1: java.lang.Exception): Boolean = x$1.getMessage().==("test");    def this(): YouBadPatternMatcher = {      YouBadPatternMatcher.super.this();      ()    }  }}

On 6/13/11 9:09 AM, Grzegorz Kossakowski wrote:
> mac-grek:gotoelim grek$ cat A.scala
> case class A(a: Int, b: String)

OK, here's what that looks like after cleanup as of now.

override def equals(x$1: java.lang.Object): Boolean = A.this.eq(x$1).||(x$1.$isInstanceOf[A]().&&({
val A$1: A = x$1.$asInstanceOf[A]();
A.this.a().==(A$1.a()).&&(A.this.b().==(A$1.b())).&&(A$1.canEqual(A.this))
}));

I trust that is more to your liking.

> [[syntax trees at end of cleanup]]// Scala source: A.scala
> override def equals(x$1: java.lang.Object): Boolean = A.this.eq(x$1).||({
> {
> val temp1: java.lang.Object = x$1;
> if (temp1.$isInstanceOf[A]())
> {
> val temp2: A = temp1.$asInstanceOf[A]();
> val temp3: Int = temp2.a();
> val temp4: java.lang.String = temp2.b();
> val a$1: Int = temp3;
> val b$1: java.lang.String = temp4;
> if (A.this.gd1$1(a$1, b$1))
> body%01(a$1,b$1){
> x$1.$asInstanceOf[A]().canEqual(A.this)
> }
> else
> {
> false
> }
> }
> else
> {
> false
> }
> }
> });
>