optimization, switch instead of if-the-else for...

optimization, switch instead of if-the-else for left and right tracer

5 files changed, 192 insertions, 120 deletions

diff --git a/sources/scalac/transformer/matching/Autom2Scala.java b/sources/scalac/transformer/matching/Autom2Scala.java
index 4452a38bd8..8cbdb664fa 100644
--- a/sources/scalac/transformer/matching/Autom2Scala.java
+++ b/sources/scalac/transformer/matching/Autom2Scala.java
@@ -59,7 +59,7 @@ public class Autom2Scala  {
 	  return new TermSymbol( pos,
 				 cf.fresh.newName( prefix ),
 				 owner,
-				 0);
+				 scalac.symtab.Modifiers.FINAL );
       }
 
       Symbol newParam( String prefix ) {
@@ -148,7 +148,7 @@ public class Autom2Scala  {
       Symbol curSym;
       Symbol hasnSym;
 
-    // overridden in TracerInScala
+    // overridden in XXTracerInScala
     Tree loadCurrentElem( Tree body ) {
 	return gen.mkBlock( new Tree[] {
 	    cf.gen.ValDef( this.hasnSym,
@@ -166,9 +166,9 @@ public class Autom2Scala  {
 	return gen.Ident(Position.FIRSTPOS, curSym);
     }
 
-      Tree currentMatches( Label label ) {
-            return _cur_eq( _iter(), label );
-      }
+    Tree currentMatches( Label label ) {
+        return _cur_eq( _iter(), label );
+    }
 
       //
       // translation of automata to scala code
@@ -191,29 +191,35 @@ public class Autom2Scala  {
 
       /** code to reference the iterator
        */
-      Tree _iter() {         return gen.Ident( pos, iterSym );  }
+      Tree _iter() {
+          return gen.Ident( pos, iterSym );
+      }
 
-      /** body of the matcherDefFun
-       */
+    Tree stateWrap(int i) {
+        if( dfa.isSink( i ))
+            return run_finished( i ); // state won't change! optimization
+        else
+            return gen.If( cf.Negate( gen.Ident( pos, hasnSym )),//cf._not_hasNext( _iter() ),
+                           run_finished( i ),
+                           code_state_NEW( i ));
+    }
+
+    /** body of the matcherDefFun
+     */
 
     public Tree code_body_NEW() {
 	int[] tags = new int[dfa.nstates];
 	Tree[] bodies = new Tree[dfa.nstates];
 	for( int i = 0; i<dfa.nstates; i++ ) {
 	    tags[ i ]   = i;
-	    if( dfa.isSink( i ))
-		bodies[ i ] = run_finished( i ); // state won't change!
-	    else
-		bodies[ i ] = gen.If( cf.Negate( gen.Ident( pos, hasnSym )),//cf._not_hasNext( _iter() ),
-				      run_finished( i ),
-				      code_state_NEW( i ));
+            bodies[ i ] = stateWrap( i );
 	}
 	if( optimize )
 	    return loadCurrentElem( gen.Switch( _state(),
-					       tags,
-					       bodies,
-					       gen.mkIntLit(cf.pos, -1 ),
-                                               funRetType()));
+                                                tags,
+                                                bodies,
+                                                code_fail(), // cannot happen
+                                                funRetType()));
 
 	Tree res = code_fail();
 	for( int i = dfa.nstates-2; i>= 0; i-- )
@@ -225,15 +231,15 @@ public class Autom2Scala  {
 
     }
 
-      Tree _cur_eq( Tree iter, Label label ) {
-            switch( label ) {
-            case TreeLabel( Tree pat ):
-                  return _cur_match( pat );
-            case SimpleLabel( Tree.Literal lit ):
-                  return cf.Equals( currentElem(), lit );
-            }
-            throw new ApplicationError("expected either algebraic or simple label:"+label);
-      }
+    private Tree _cur_eq( Tree iter, Label label ) {
+        switch( label ) {
+        case TreeLabel( Tree pat ):
+            return _cur_match( pat );
+        case SimpleLabel( Tree.Literal lit ):
+            return cf.Equals( currentElem(), lit );
+        }
+        throw new ApplicationError("expected either algebraic or simple label:"+label);
+    }
 
       AlgebraicMatcher am;
 
@@ -285,7 +291,9 @@ public class Autom2Scala  {
     */
 
     Tree code_state_NEW( int i ) {
-	Tree stateBody = code_delta(i, Label.DefaultLabel );
+	Tree stateBody = code_delta( i, Label.DefaultLabel );
+        if( stateBody == null )
+            stateBody = code_fail();
 	HashMap trans = ((HashMap[])dfa.deltaq)[ i ];
 
 	for( Iterator labs = dfa.labels.iterator(); labs.hasNext() ; ) {
@@ -296,7 +304,7 @@ public class Autom2Scala  {
 	    Tree action = code_delta( i, (Label) label );
 
 	    if( action != null ) {
-
+		assert stateBody != null : "stateBody is null";
 		stateBody = gen.If( currentMatches((Label) label ),
 				    action,
 				    stateBody);
diff --git a/sources/scalac/transformer/matching/CodeFactory.java b/sources/scalac/transformer/matching/CodeFactory.java
index b42354e430..ff874aec5c 100644
--- a/sources/scalac/transformer/matching/CodeFactory.java
+++ b/sources/scalac/transformer/matching/CodeFactory.java
@@ -197,6 +197,16 @@ class CodeFactory extends PatternTool {
                              });
     }
 
+    protected Tree Error(int pos, Type type) {
+        return gen.mkApplyTV(
+			     gen.mkRef(pos, defs.MATCHERROR_FAIL()),
+                             new Tree[]{gen.mkType(pos, type)},
+                             new Tree[]{
+                                 gen.mkStringLit(pos, unit.toString()),
+                                 gen.mkIntLit(pos, Position.line(pos))
+                             });
+    }
+
 
     Type pairType( Type left, Type right ) {
 	return defs.TUPLE_TYPE(new Type[] { left, right } );
diff --git a/sources/scalac/transformer/matching/LeftTracerInScala.java b/sources/scalac/transformer/matching/LeftTracerInScala.java
index ad10599f15..c4f5c3ff74 100644
--- a/sources/scalac/transformer/matching/LeftTracerInScala.java
+++ b/sources/scalac/transformer/matching/LeftTracerInScala.java
@@ -143,6 +143,10 @@ public class LeftTracerInScala extends TracerInScala {
     }
 
 
+    Tree switchDefaultCase() {
+        return gen.Nil( cf.pos );
+    }
+
     public Tree code_body() {
 
         Tree body = code_fail(); // never reached at runtime.
@@ -203,7 +207,8 @@ public class LeftTracerInScala extends TracerInScala {
     Tree[] getTrace() {
 
         initializeSyms();
-        Tree tb = code_body();
+        //Tree tb = code_body();
+        Tree tb = code_body_NEW();
         theDefDef = gen.DefDef( this.funSym,
                                 tb );
 
diff --git a/sources/scalac/transformer/matching/RightTracerInScala.java b/sources/scalac/transformer/matching/RightTracerInScala.java
index b3ee33b8d7..654845c6b9 100644
--- a/sources/scalac/transformer/matching/RightTracerInScala.java
+++ b/sources/scalac/transformer/matching/RightTracerInScala.java
@@ -31,9 +31,6 @@ public class RightTracerInScala extends TracerInScala  {
 
     Matcher _m;
 
-    //      Symbol funSym;
-
-    Symbol elemSym;
     Symbol targetSym;
 
     HashMap helpMap2 ;
@@ -153,7 +150,7 @@ public class RightTracerInScala extends TracerInScala  {
 					0 )
 	    .setType( defs.INT_TYPE() ) ;
 
-	this.elemSym = new TermSymbol( pos,
+	this.curSym = new TermSymbol( pos,
 				       cf.fresh.newName("elem"),
 				       funSym,
 				       0)
@@ -165,17 +162,34 @@ public class RightTracerInScala extends TracerInScala  {
 					 0)
 	    .setType( defs.INT_TYPE() ) ;
 
-
 	funSym.setType( new Type.MethodType( new Symbol[] {
 	    iterSym, stateSym },  defs.UNIT_TYPE() ));
 
     }
 
+    // load current elem and trace
+    Tree loadCurrentElem( Tree body ) {
+        return gen.mkBlock( new Tree[] {
+            gen.If( cf.isEmpty( _iter() ),
+                    run_finished( 0 ),
+                    gen.mkBlock( new Tree[] {
+                        gen.ValDef( this.targetSym,
+                                    cf.SeqTrace_headState( gen.Ident( pos, iterSym))),
+                        gen.ValDef( this.curSym,
+                                    cf.SeqTrace_headElem( gen.Ident( pos, iterSym ))),
+                        body })
+                    )});
+    }
+
     // same as in LeftTracer
     Tree code_fail() {
-	return cf.ThrowMatchError( _m.pos, defs.UNIT_TYPE() );
+	return gen.Block( new Tree[] {
+            gen.Console_print( pos, "System error during pattern matching. Please file bug report\n"),
+            cf.ThrowMatchError( _m.pos, defs.UNIT_TYPE() )
+        });
     }
 
+    /*
     public Tree code_body() {
 
 	Tree body = code_fail(); // never reached at runtime.
@@ -192,13 +206,12 @@ public class RightTracerInScala extends TracerInScala  {
 			  gen.mkBlock( new Tree[] {
 			      gen.ValDef( targetSym,
 					  cf.SeqTrace_headState( gen.Ident( pos, iterSym))),
-			      gen.ValDef( elemSym,
+			      gen.ValDef( curSym,
 					  cf.SeqTrace_headElem( gen.Ident( pos, iterSym))),
 
 			      body }));
 
-	/*
-	  t3 = gen.mkBlock( new Tree[] {
+		  t3 = gen.mkBlock( new Tree[] {
 	  cf.debugPrintRuntime("enter binderFun"),
 	  cf.debugPrintRuntime(" state:"),
 	  cf.debugPrintRuntime( gen.Ident( pos, stateSym )),
@@ -206,76 +219,110 @@ public class RightTracerInScala extends TracerInScala  {
 	  cf.debugPrintRuntime(_iter()),
 	  cf.debugPrintNewlineRuntime(""),
 	  t3 });
-	*/
+
 
 	//System.out.println("enter RightTracerInScala:code_body()");// DEBUG
 	//System.out.println("dfa.nstates"+dfa.nstates);// DEBUG
 	return t3;
     }
+*/
+    /** see code_state0_NEW
+     */
+    Tree code_state0( Tree elseBody ) { // careful, map Int to Int
+
+	return gen.If( cf.Equals( _state(), gen.mkIntLit( cf.pos, 0 )),
+		       code_state0_NEW(),
+		       elseBody );
+
+    }
 
     /** this one is special, we check the first element of the trace
      *  and choose the next state depending only on the state part
      */
-    Tree code_state0( Tree elseBody ) { // careful, map Int to Int
+    Tree code_state0_NEW() { // careful, map Int to Int
 
 	HashMap hmap    = (HashMap) dfa.deltaq( 0 ); // all the initial states
 
-	Tree stateBody = code_fail(); // never happens
+        int i = 0;
+        final int n = hmap.keySet().size(); // all transitions defined
+
+        TreeMap tmapTag = new TreeMap();
+        TreeMap tmapBody = new TreeMap();
+	for( Iterator it = hmap.keySet().iterator(); it.hasNext(); i++) {
 
-	for( Iterator it = hmap.keySet().iterator(); it.hasNext(); ) {
 	    Integer targetL  = (Integer) it.next();
 	    Integer targetR  = (Integer) hmap.get( targetL );
 
-	    stateBody = gen.If( cf.Equals( gen.Ident( pos, targetSym ),
-					   gen.mkIntLit( cf.pos, targetL )),
-			        callFun( new Tree[] {
-				    cf.SeqTrace_tail( _iter() ),
-				    gen.mkIntLit( cf.pos, targetR ) }),
-			        stateBody );
-	}
+            Integer I = new Integer( i );
+            tmapTag.put( targetL, I );
+            tmapBody.put( I, callFun( new Tree[] {
+                cf.SeqTrace_tail( _iter() ),
+                gen.mkIntLit( cf.pos, targetR ) }));
 
-	return gen.If( cf.Equals( _state(), gen.mkIntLit( cf.pos, 0 )),
-		       stateBody ,
-		       elseBody );
+	}
+        i = 0;
+        int[]  tags    = new int[ n ];
+        Tree[] targets = new Tree[ n ];
+        for( Iterator it = tmapTag.keySet().iterator(); it.hasNext(); i++) {
+            Integer tagI = (Integer) it.next();
+            tags[ i ] = tagI.intValue();
+            Integer I = (Integer) tmapTag.get( tagI );
+            targets[ i ] = (Tree) tmapBody.get( I );
+        }
+        return gen.Switch( gen.Ident( pos, targetSym ), tags, targets, code_fail()/*cannot happen*/ );
 
     }
 
-    Tree code_state( int i, Tree elseBody ) {
-
-	if( i == 0 )
-	    return code_state0( elseBody );
-
-	int  finalSwRes;
-	Tree stateBody ; // action(delta) for one particular label/test
-
-	// default action (fail if there is none)
-
-	stateBody = code_delta( i, Label.DefaultLabel);
-
-	if( stateBody == null )
-	    stateBody = code_fail();
+    Tree currentMatches( Label label ) {
+	switch( label ) {
+	case Pair( Integer target, Label theLab ):
+	    return cf.Equals( gen.mkIntLit( cf.pos, target ),
+			      current() );
+	}
+	throw new ApplicationError("expected Pair label");
+    }
 
-	// transitions of state i
 
+    Tree code_state_NEW( int i ) { // precondition i != 0
+	Tree stateBody = code_delta( i, Label.DefaultLabel );
+        if( stateBody == null )
+            stateBody = code_fail();
 	HashMap trans = ((HashMap[])dfa.deltaq)[ i ];
 
-	for( Iterator labs = dfa.labels.iterator(); labs.hasNext() ; ) {
+        TreeMap tmapTag = new TreeMap();
+        TreeMap tmapBody = new TreeMap();
+	int j = 0;
+	for( Iterator labs = dfa.labels.iterator(); labs.hasNext(); j++) {
 	    Object label = labs.next();
 	    Integer next = (Integer) trans.get( label );
 
 	    Tree action = code_delta( i, (Label) label );
 
 	    if( action != null ) {
+                Integer J = new Integer( j );
+                tmapTag.put( ((Label.Pair) label).state, J );
+                tmapBody.put( J, action );
 
-		stateBody = gen.If( _cur_eq( _iter(), (Label) label ),
+		stateBody = gen.If( currentMatches((Label) label ),
 				    action,
 				    stateBody);
 	    }
 	}
-
-	return gen.If( cf.Equals( _state(), gen.mkIntLit( cf.pos, i )),
-		       stateBody ,
-		       elseBody );
+        final int n = tmapTag.keySet().size();
+        j = 0;
+        int[]  tags    = new int[ n ];
+        Tree[] targets = new Tree[ n ];
+        for( Iterator it = tmapTag.keySet().iterator(); it.hasNext(); j++) {
+            Integer tagI = (Integer) it.next();
+            tags[ j ] = tagI.intValue();
+            Integer J = (Integer) tmapTag.get( tagI );
+            targets[ j ] = (Tree) tmapBody.get( J );
+        }
+        if( n > 0 ) {
+            actionsPresent = true;
+            return gen.Switch( gen.Ident( pos, targetSym ), tags, targets, code_fail()/*cannot happen*/ );
+        } else
+            return code_fail();
     }
 
     /** returns a Tree whose type is boolean.
@@ -357,7 +404,6 @@ public class RightTracerInScala extends TracerInScala  {
 	return  am.toTree();
     }
 
-
     /** returns translation of transition with label from i.
      *  returns null if there is no such transition(no translation needed)
      */
@@ -367,6 +413,7 @@ public class RightTracerInScala extends TracerInScala  {
 	Tree    algMatchTree = null;
 	if( ntarget == null )
 	    return null;
+
 	//System.out.println("delta("+i+","+label+")" );
 	Label theLab = null;
 	switch(label) {
@@ -401,7 +448,7 @@ public class RightTracerInScala extends TracerInScala  {
 	for( Iterator it = vars.iterator(); it.hasNext(); ) {
 	    Symbol var = (Symbol) it.next();
 
-	    Tree rhs = gen.Ident( pos, elemSym );
+	    Tree rhs = gen.Ident( pos, curSym );
 
 	    stms[ j++ ] = prependToHelpVar( var , rhs);
 	}
@@ -415,44 +462,56 @@ public class RightTracerInScala extends TracerInScala  {
 	return gen.mkBlock( pos, stms );
     }
 
+    Tree stateWrap(int i) {
+        if( i == 0 )
+            return code_state0_NEW();
+        return code_state_NEW( i );
+    }
+
+    boolean actionsPresent = false;
+
     /* returns statements that do the work of the right-transducer
      */
     Tree[] getStms( Tree trace ) {
 
-	//System.out.println( "!!getStms.helpVarDefs: "+helpVarDefs);
-
-	Vector v = new Vector();
-
-	for( Iterator it = helpVarDefs.iterator(); it.hasNext(); )
-	    v.add( (Tree) it.next() );
-
-	v.add( gen.DefDef( this.funSym, code_body() )  );
-	v.add( callFun( new Tree[] {  trace, gen.mkIntLit( cf.pos, 0 )  }  )  );
-
-	/*
-	  for(Iterator it = helpMap.keySet().iterator(); it.hasNext(); ) {
-	  // DEBUG
-	  Symbol var = (Symbol)it.next();
-	  v.add( cf.debugPrintRuntime( var.name.toString() ));
-	  v.add( cf.debugPrintRuntime( refHelpVar( var )) );
-	  }
-	*/
-
-	for( Iterator it = seqVars.iterator(); it.hasNext(); ) {
-	    v.add( bindVar( (Symbol) it.next() ) );
-	}
-
-	Tree result[] = new Tree[ v.size() ];
-	int j = 0;
-	for( Iterator it = v.iterator(); it.hasNext(); ) {
-	    result[ j++ ] = (Tree) it.next();
-	}
-
-	// helpvarSEQ via _m.varMap
+        //System.out.println( "!!getStms.helpVarDefs: "+helpVarDefs);
+
+        Vector v = new Vector();
+
+        for( Iterator it = helpVarDefs.iterator(); it.hasNext(); ) {
+            v.add( (Tree) it.next() );
+        }
+        Tree binderFunDef = gen.DefDef( this.funSym, code_body_NEW() );
+        if( actionsPresent ) {
+            //v.add( gen.DefDef( this.funSym, code_body() )  );
+            v.add( binderFunDef );
+            v.add( callFun( new Tree[] {  trace, gen.mkIntLit( cf.pos, 0 )  }  )  );
+        };
+        /*
+          for(Iterator it = helpMap.keySet().iterator(); it.hasNext(); ) {
+          // DEBUG
+          Symbol var = (Symbol)it.next();
+          v.add( cf.debugPrintRuntime( var.name.toString() ));
+          v.add( cf.debugPrintRuntime( refHelpVar( var )) );
+          }
+        */
+
+        for( Iterator it = seqVars.iterator(); it.hasNext(); ) {
+            v.add( bindVar( (Symbol) it.next() ) );
+        }
+
+        Tree result[] = new Tree[ v.size() ];
+        int j = 0;
+        for( Iterator it = v.iterator(); it.hasNext(); ) {
+            result[ j++ ] = (Tree) it.next();
+        }
+
+        // helpvarSEQ via _m.varMap
+
+        return result;
+    }
 
-	return result;
 
-    }
 
     /** return the accumulator. (same as in LeftTracerInScala)
      *  todo: move tree generation of Unit somewhere else
@@ -466,18 +525,7 @@ public class RightTracerInScala extends TracerInScala  {
     }
 
     Tree currentElem() {
-	return gen.Ident( pos, elemSym );
-    }
-
-    Tree _cur_eq( Tree iter, Label label ) {
-	//System.out.println("_cur_eq, thelab: "+label);
-	switch( label ) {
-	case Pair( Integer target, Label theLab ):
-	    return cf.Equals( gen.mkIntLit( cf.pos, target ),
-			      current() );
-	}
-	throw new ApplicationError("expected Pair label");
+	return gen.Ident( pos, curSym );
     }
 
-
 }
diff --git a/sources/scalac/transformer/matching/TracerInScala.java b/sources/scalac/transformer/matching/TracerInScala.java
index 61a51fa809..d3315bf5df 100644
--- a/sources/scalac/transformer/matching/TracerInScala.java
+++ b/sources/scalac/transformer/matching/TracerInScala.java
@@ -18,6 +18,7 @@ import ch.epfl.lamp.util.Position;
  */
 public class TracerInScala extends Autom2Scala {
 
+    protected boolean optimize = true;
 
     HashMap helpMap;