Problem with pattern matcher logic

I'm not sure if I fully understand the problem but is this related to the issue that forward jumps are permitted in bytecode but not in source level Java? Maybe this can be solved with the following pattern (sort of defunctionalizing the jump targets and building an explicit state machine):

// at the method's top-level

int next = 0
do {
switch(next) {
case 0:
// begin of 'real' method body
...
// now 'forward jump' to label #7
next = 7
continue
case 1: // other code
...
case 7: // jump target, continue here
...
}
} while (false)

You would need to move the label definitions out of the nested if/else branches and insert a 'jump' there. That means some local val defs will need to become method-level variables as well.

- Tiark

On Aug 25, 2010, at 9:30 PM, Grzegorz Kossakowski wrote:

> Hi,
>
> While working ScalaGWT project I finally ran into a problem with
> pattern matching that everyone (including me) was aware of. I was only
> hoping that you need complicated pattern to trigger pattern matching
> logic to emit dangerous output. By dangerous output I mean LabelDefs
> along with references to them outside the block that the label is
> attached to.
>
> Let me give you an example of what I'm talking about:
> class YouBadPatternMatcher {
>
> def problematicPattern = {
> try {
> 0
> } catch {
> case x: Exception if x.getMessage == "test" => println("first case " + x)
> case x => println("second case " + x)
> }
> }
> }
>
> and I get following for -Xprint:cleanup:
>
> [[syntax trees at end of cleanup]]// Scala source: hello.scala
> package {
> 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 = {
> {
> val temp1: java.lang.Throwable = ex$1;
> if (temp1.$isInstanceOf[java.lang.Exception]())
> {
> 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){ //THIS IS LABEL DEF
> scala.this.Predef.println("second case ".+(x));
> scala.runtime.BoxedUnit.UNIT
> }
> }
> }
> else
> {
> body%1(temp1); //THIS is Apply referring to the
> label defined above
> scala.runtime.BoxedUnit.UNIT
> }
> }
> }
> }
> };
> exceptionResult1
> };
> final private[this] def gd1$1(x$1:
> java.lang.Exception): Boolean = x$1.getMessage().==("test");
> def this(): YouBadPatternMatcher = {
> YouBadPatternMatcher.super.this();
> ()
> }
> }
> }
>
> As you can see we've got a label definition 'body%1' (which is
> translated to while (true) {...; break; }) and we've got label apply
> which means we should jump to that label def. If this apply was inside
> of the block Label is attached to then jumping would be easy as
> emitting 'continue body%1;' but since apply is outside of that block
> we've got no way to jump to it in Java (or in language I'm working on
> which is very, very similar to Java).
>
> I talked briefly to Lex about this and we agreed that solving this
> problem is beyond the scope of my internship and this should be
> addressed by people with better understanding of the big picture of
> the compiler. I'd like to know your opinion about options on how to
> proceed. From my very own perspective the best solution would be if
> pattern matching logic didn't emit that kind of trees at all. I don't
> know how feasible is this.
>
> I should explain how much does this affects my project. I think it
> does affect it quite a lot because it's so easy to trigger the logic
> in pattern matcher that will emit output I cannot translate in
> meaningful way without very serious code transformations. The fact
> that it's so easy (see code above) to trigger this behaviour means
> that people willing to write any kind of Scala application for GWT
> will run into this. I believe that this is the only blocker or
> semi-blocker for ScalaGWT effort.
>
> Thoughts?
>

On Wed, Aug 25, 2010 at 4:47 PM, Tiark Rompf wrote:
> I'm not sure if I fully understand the problem but is this related to the issue that forward jumps are permitted in bytecode but not in source level Java?

Essentially, yes it's manifestation of the same problem as forward
jumps introduce.

> Maybe this can be solved with the following pattern (sort of defunctionalizing the jump targets and building an explicit state machine):
>
> // at the method's top-level
>
> int next = 0
> do {
>  switch(next) {
>    case 0:
>        // begin of 'real' method body
>        ...
>        // now 'forward jump' to label #7
>        next = 7
>        continue
>    case 1: // other code
>      ...
>    case 7: // jump target, continue here
>       ...
>  }
> } while (false)
>
>
> You would need to move the label definitions out of the nested if/else branches and insert a 'jump' there. That means some local val defs will need to become method-level variables as well.

I believe this would work but you would need to put a label for
top-level do { ... } while loop so you could actually jump back to
top-level switch statement.

Any chance you could get tree transformation like that implemented as
separate compiler phase that I could use in my code?

On Wed, Aug 25, 2010 at 4:47 PM, Tiark Rompf wrote:
> I'm not sure if I fully understand the problem but is this related to the issue that forward jumps are permitted in bytecode but not in source level Java? Maybe this can be solved with the following pattern (sort of defunctionalizing the jump targets and building an explicit state machine):
>
> // at the method's top-level
>
> int next = 0
> do {
>  switch(next) {
>    case 0:
>        // begin of 'real' method body
>        ...
>        // now 'forward jump' to label #7
>        next = 7
>        continue
>    case 1: // other code
>      ...
>    case 7: // jump target, continue here
>       ...
>  }
> } while (false)
>
>
> You would need to move the label definitions out of the nested if/else branches and insert a 'jump' there. That means some local val defs will need to become method-level variables as well.

Hi Tiark,

I decided to try different idea (proposed by Martin during Scala Days
AFAIR). The ides is to replace LabelDefs with method def and an
immediate call to that method, and to replace jumps by method calls
too.

I was about to ask you to have a look what I've got here:

http://review.source.gogoego.com/#change,621

but I found a problem with that code myself. The problem is that it
seems that nested LabelDefs with the same name are allowed to exist
(??!). Have a look at this tree:

body%2(ms){
val temp1: List = ms.filter({
(new scala.testing.Show$$anonfun$test$2($this, args$1): Function1)
}).$asInstanceOf[List]();
if (temp1.$isInstanceOf[object Nil]())
{
scala.testing.Show$class.testMethod$1($this,
ms.head().$asInstanceOf[java.lang.reflect.Method](), f$1, args$1,
args1$1)
}
else
if (temp1.$isInstanceOf[scala.collection.immutable.::]())
{
val temp3: scala.collection.immutable.:: =
temp1.$asInstanceOf[scala.collection.immutable.::]();
val temp4: java.lang.reflect.Method =
temp3.hd$1().$asInstanceOf[java.lang.reflect.Method]();
if (immutable.this.Nil.==(temp3.tl$1()))
{
scala.testing.Show$class.testMethod$1($this, temp4, f$1,
args$1, args1$1)
}
else
{
val ms: List = temp3;
body%2(ms){
"cannot disambiguate between multiple implementations of
".+(f$1.name())
}
}
}
else
body%2(temp1)
}

(this is fragment of -Xprint:clenaup
src/library/scala/testing/Show.scala output)

You can see that there is LabelDef 'body%2' mentioned second time:
body%2(ms){
"cannot disambiguate between multiple implementations of
".+(f$1.name())
}

What are semantics of such defintion? Does it override previous one in
some sense? I was trying to find an answer in GenJVM/GenIcode but
without a much of luck.

In general, use Symbols whenever you deal with definitions. Names are ambiguous, as you have noticed. Symbols are guaranteed to be unique per definition. I assume the two LabelDefs have different symbols, if they don't then it's a bug.
iulian

On Sun, Sep 5, 2010 at 7:42 AM, Grzegorz Kossakowski <grek@google.com> wrote:

On Wed, Aug 25, 2010 at 4:47 PM, Tiark Rompf <tiark.rompf@epfl.ch> wrote:
> I'm not sure if I fully understand the problem but is this related to the issue that forward jumps are permitted in bytecode but not in source level Java? Maybe this can be solved with the following pattern (sort of defunctionalizing the jump targets and building an explicit state machine):
>
> // at the method's top-level
>
> int next = 0
> do {
>  switch(next) {
>    case 0:
>        // begin of 'real' method body
>        ...
>        // now 'forward jump' to label #7
>        next = 7
>        continue
>    case 1: // other code
>      ...
>    case 7: // jump target, continue here
>       ...
>  }
> } while (false)
>
>
> You would need to move the label definitions out of the nested if/else branches and insert a 'jump' there. That means some local val defs will need to become method-level variables as well.

Hi Tiark,

I decided to try different idea (proposed by Martin during Scala Days
AFAIR). The ides is to replace LabelDefs with method def and an
immediate call to that method, and to replace jumps by method calls
too.

I was about to ask you to have a look what I've got here:

http://review.source.gogoego.com/#change,621

but I found a problem with that code myself. The problem is that it
seems that nested LabelDefs with the same name are allowed to exist
(??!). Have a look at this tree:

body%2(ms){
 <synthetic> val temp1: List = ms.filter({
   (new scala.testing.Show$$anonfun$test$2($this, args$1): Function1)
 }).$asInstanceOf[List]();
 if (temp1.$isInstanceOf[object Nil]())
   {
     scala.testing.Show$class.testMethod$1($this,
ms.head().$asInstanceOf[java.lang.reflect.Method](), f$1, args$1,
args1$1)
   }
 else
   if (temp1.$isInstanceOf[scala.collection.immutable.::]())
     {
       <synthetic> val temp3: scala.collection.immutable.:: =
temp1.$asInstanceOf[scala.collection.immutable.::]();
       <synthetic> val temp4: java.lang.reflect.Method =
temp3.hd$1().$asInstanceOf[java.lang.reflect.Method]();
       if (immutable.this.Nil.==(temp3.tl$1()))
         {
           scala.testing.Show$class.testMethod$1($this, temp4, f$1,
args$1, args1$1)
         }
       else
         {
           val ms: List = temp3;
           body%2(ms){
             "cannot disambiguate between multiple implementations of
".+(f$1.name())
           }
         }
     }
   else
     body%2(temp1)
}

(this is fragment of -Xprint:clenaup
src/library/scala/testing/Show.scala output)

You can see that there is LabelDef 'body%2' mentioned second time:
body%2(ms){
             "cannot disambiguate between multiple implementations of
".+(f$1.name())
           }

What are semantics of such defintion? Does it override previous one in
some sense? I was trying to find an answer in GenJVM/GenIcode but
without a much of luck.

--
Grzegorz

--
« Je déteste la montagne, ça cache le paysage »
Alphonse Allais

On Sun, Sep 05, 2010 at 01:23:25PM +0200, iulian dragos wrote:
> In general, use Symbols whenever you deal with definitions. Names are
> ambiguous, as you have noticed. Symbols are guaranteed to be unique
> per definition. I assume the two LabelDefs have different symbols, if
> they don't then it's a bug.

I bet it is a bug. I know there are pattern matcher bugs tied up in
that. It's one of those things I couldn't figure out.

https://lampsvn.epfl.ch/trac/scala/ticket/2756
"pattern matcher creates multiple local variables with the same symbol"

Reported by a certain Mr. I. Dragos.

On Sun, Sep 5, 2010 at 10:43 AM, Paul Phillips wrote:
> On Sun, Sep 05, 2010 at 01:23:25PM +0200, iulian dragos wrote:
>> In general, use Symbols whenever you deal with definitions. Names are
>> ambiguous, as you have noticed. Symbols are guaranteed to be unique
>> per definition. I assume the two LabelDefs have different symbols, if
>> they don't then it's a bug.
>
> I bet it is a bug.  I know there are pattern matcher bugs tied up in
> that.  It's one of those things I couldn't figure out.
>
> https://lampsvn.epfl.ch/trac/scala/ticket/2756
> "pattern matcher creates multiple local variables with the same symbol"
>
> Reported by a certain Mr. I. Dragos.

I checked it today and it turns out that it's not a bug in scalac.
Symbols are different, only names are the same. I had a bug in my code
which was making me to believe that problem is with the same symbols.

In any case, it would be good if names were different too. Otherwise
printing trees gives you really confusing results.

On Tue, Sep 7, 2010 at 4:24 PM, Grzegorz Kossakowski wrote:
> On Sun, Sep 5, 2010 at 10:43 AM, Paul Phillips wrote:
>> On Sun, Sep 05, 2010 at 01:23:25PM +0200, iulian dragos wrote:
>>> In general, use Symbols whenever you deal with definitions. Names are
>>> ambiguous, as you have noticed. Symbols are guaranteed to be unique
>>> per definition. I assume the two LabelDefs have different symbols, if
>>> they don't then it's a bug.
>>
>> I bet it is a bug.  I know there are pattern matcher bugs tied up in
>> that.  It's one of those things I couldn't figure out.
>>
>> https://lampsvn.epfl.ch/trac/scala/ticket/2756
>> "pattern matcher creates multiple local variables with the same symbol"
>>
>> Reported by a certain Mr. I. Dragos.
>
> I checked it today and it turns out that it's not a bug in scalac.
> Symbols are different, only names are the same. I had a bug in my code
> which was making me to believe that problem is with the same symbols.
>
> In any case, it would be good if names were different too. Otherwise
> printing trees gives you really confusing results.
>
-uniqid is your friend here