pattern matching encore

8 files changed, 1593 insertions, 1 deletions

diff --git a/sources/scalac/transformer/matching/BindingBerrySethi.java b/sources/scalac/transformer/matching/BindingBerrySethi.java
new file mode 100644
index 0000000000..ede37647c4
--- /dev/null
+++ b/sources/scalac/transformer/matching/BindingBerrySethi.java
@@ -0,0 +1,169 @@
+package scalac.transformer.matching ;
+
+import scalac.ApplicationError ;
+import scalac.ast.Tree ;
+import scalac.util.Name ;
+import Tree.* ;
+
+import java.util.* ;
+
+import scalac.ast.printer.TextTreePrinter ;
+//import scala.compiler.printer.XMLTreePrinter ;
+//import scala.compiler.printer.XMLAutomPrinter ;
+
+/** a Berry-Sethi style construction for nfas.
+ *  this class plays is the "Builder" for the "Director" class
+ *  WordRecognizer.
+ */
+
+public class BindingBerrySethi extends BerrySethi {
+
+      HashMap deltaqRev[];    // delta of Rev
+      Vector  defaultqRev[];  // default transitions of Rev
+      Vector qbinders[];  // transitions <-> variables
+
+      protected void makeTransition( Integer srcI, Integer destI, Label label ) {
+            int src  = srcI.intValue() ;
+            int dest = destI.intValue() ;
+            Vector arrows, revArrows;
+            Label revLabel = new Label.Pair( srcI, label  );
+            switch( label ) {
+            case DefaultLabel:
+                  arrows = defaultq[ src ];
+                  revArrows = defaultqRev[ dest ];
+                  break;
+            default:
+                  arrows = (Vector) deltaq[ src ].get( label );
+                  if( arrows == null )
+                        deltaq[ src ].put( label,
+                                           arrows = new Vector() );
+                  revArrows = (Vector) deltaqRev[ dest ].get( revLabel );
+                  if( revArrows == null )
+                        deltaqRev[ dest ].put( revLabel,
+                                               revArrows = new Vector() );
+            }
+            arrows.add( destI );
+            revArrows.add( srcI );
+      }
+
+      NondetWordAutom revnfa ;
+
+      void seenLabel( Tree pat, Label label ) {
+            Integer i = new Integer( ++pos );
+            seenLabel( pat, i, label );
+            switch( pat ) {
+            case Apply(_, _):
+            case Literal( _ ):
+                  this.varAt.put( i, activeBinders.clone() ); // below @ ?
+                  break;
+            case Ident( Name name ):
+                  assert ( name == Name.fromString("_"));
+
+                  Vector binders = (Vector) activeBinders.clone();
+
+                  if( name != Name.fromString("_")) {
+                        binders.add( pat.symbol() );
+                  }
+
+                  this.varAt.put( i, binders );
+
+            }
+      }
+
+      HashMap varAt;   // chi:    Positions -> Vars (Symbol)
+
+      protected void initialize( Tree[] pats ) {
+            this.varAt = new HashMap(); // Xperiment
+            super.initialize( pats );
+      }
+
+      protected void initializeAutom() {
+            super.initializeAutom();
+            deltaqRev = new HashMap[ pos ];   // deltaRev
+            defaultqRev = new Vector[ pos ];  // default transitions
+            qbinders = new Vector[ pos ];    // transitions <-> variables
+
+            for( int j = 0; j < pos; j++ ) {
+                  deltaqRev[ j ] = new HashMap();
+                  defaultqRev[ j ] = new Vector();
+                  qbinders[ j ] = (Vector) varAt.get( new Integer( j ) );
+            }
+            varAt.clear(); // clean up
+
+      }
+
+
+
+      public NondetWordAutom automatonFrom( Tree pat, Integer finalTag ) {
+
+            this.finalTag = finalTag ;
+            //System.out.println( "enter automatonFrom("+TextTreePrinter.toString(pat)+")");
+            switch( pat ) {
+            case Sequence( Tree[] subexpr ):
+
+                  initialize( subexpr );
+
+                  // (1) compute first + follow;
+                  ++pos;
+
+                  globalFirst = compFollow( subexpr );
+
+
+
+                  initializeAutom();   // explicit representation
+
+                  collectTransitions();
+
+                  NondetWordAutom result =
+                        new NondetWordAutom(pos, // = nstates
+                                            labels,
+                                            initials,
+                                            finals,
+                                            (Object) deltaq,
+                                            (Object) defaultq,
+                                            (Object) qbinders);
+
+                  result.leftTrans = true;
+
+                  TreeSet revInitials = new TreeSet( finals.keySet() );
+                  /*
+                  pos++; // adding a state
+                  HashSet deltaqRev2[]   = new HashSet[ deltaqRev.length + 1];
+                  HashSet defaultqRev2[] = new HashSet[ deltaqRev.length + 1];
+                  HashSet qbinders[]     = new HashSet[ deltaqRev.length + 1];
+                  for(Iterator it = finals.keySet().iterator(); it.hasNext(); ) {
+
+                  }
+                  */
+                  TreeMap revFinals = new TreeMap();
+                  for(Iterator it = initials.iterator(); it.hasNext(); ) {
+                        revFinals.put( it.next(), finalTag);
+                  }
+                  revnfa = new NondetWordAutom(pos,
+                                               labels,
+                                               revInitials,
+                                               revFinals,
+                                               (Object) deltaqRev,
+                                               (Object) defaultqRev,
+                                               (Object) qbinders);
+
+                  revnfa.rightTrans = true;
+
+                  /*
+                  System.out.println("inBerrySethi");
+                  XMLAutomPrinter pr = new XMLAutomPrinter( System.out );
+                  pr.begin();
+                  pr.print( result );
+                  pr.print( revnfa );
+                  pr.end();
+                  System.out.println("initialsRev = "+initialsRev);
+                  System.out.println("outBerrySethi");
+                  */
+                  //System.exit(0);
+                  return result;                  //print();
+            }
+
+            throw new ApplicationError("expected a sequence pattern");
+      }
+
+}
diff --git a/sources/scalac/transformer/matching/CodeFactory.java b/sources/scalac/transformer/matching/CodeFactory.java
index b91007401c..77797ca9c0 100644
--- a/sources/scalac/transformer/matching/CodeFactory.java
+++ b/sources/scalac/transformer/matching/CodeFactory.java
@@ -20,6 +20,26 @@ import Tree.*;
 
 class CodeFactory extends PatternTool {
 
+    private int pos = Position.NOPOS ;
+
+      static final Name HEAD_N       = Name.fromString("head");
+
+      static final Name TAIL_N       = Name.fromString("tail");
+
+      static final Name SEQ_TRACE_N      = Name.fromString("scala.SeqTrace");
+
+      static final Name HEADSTATE_N       = Name.fromString("headState");
+
+      static final Name HEADELEM_N        = Name.fromString("headElem");
+
+      static final Name ISEMPTY_N        = Name.fromString("isEmpty");
+
+
+
+    Symbol seqListSym() {
+	return defs.getType( Name.fromString("scala.List") ).symbol() ;
+    }
+
     Symbol seqConsSym() {
 	return defs.getType( Name.fromString("scala.::") ).symbol() ;
     }
@@ -28,6 +48,14 @@ class CodeFactory extends PatternTool {
 	return defs.getType( Name.fromString( "scala.Nil" ) ).symbol(); // no need for TypeApply anymore!x
     }
 
+    Symbol seqIterSym() {
+	return defs.getType( Name.fromString( "scala.Iterator" ) ).symbol();
+    }
+
+    Symbol seqTraceSym() {
+	return defs.getType( Name.fromString( "scala.SeqTrace" ) ).symbol();
+    }
+
     Symbol seqTraceConsSym() {
 	return defs.getType( Name.fromString( "scala.SeqTraceCons" ) ).symbol();
     }
@@ -77,13 +105,27 @@ class CodeFactory extends PatternTool {
 	return result ;
     }
 
+      //                       `SeqList[ elemType ]'
+      Type SeqListType( Type elemType ) {
+            return Type.TypeRef( defs.SCALA_TYPE,
+                                 seqListSym(),
+                                 new Type[] { elemType });
+      }
+
+      //                       `SeqTrace[ elemType ]'
+      Type SeqTraceType( Type elemType ) {
+            return Type.TypeRef( defs.SCALA_TYPE,
+                                 seqTraceSym(),
+                                 new Type[] { elemType });
+      }
+
     /**                       `SequenceIterator[ elemType ]' // TODO: Move to TypeFactory
      */
     Type _seqIterType( Type elemType ) {
 	Symbol seqIterSym = defs.getType( Names.scala_Iterator ).symbol();
 
 	return Type.TypeRef( defs.SCALA_TYPE/*PREFIX*/,
-			     seqIterSym,
+			     seqIterSym(),
 			     new Type[] { elemType });
     }
 
@@ -268,6 +310,53 @@ class CodeFactory extends PatternTool {
 	    .setType( defs.BOOLEAN_TYPE );
     }
 
+      /** `trace.isEmpty'
+       */
+      public Tree isEmpty( Tree iter ) {
+            Scope scp = seqTraceSym().members();
+            Symbol isEmptySym = scp.lookup ( ISEMPTY_N );
+            return _applyNone( gen.Select( iter, isEmptySym ))
+                  .setType( defs.BOOLEAN_TYPE );
+      }
+
+      Tree SeqTrace_headElem( Tree arg ) {
+            Scope scp = seqTraceSym().members();
+            Symbol headSym = scp.lookup ( HEADELEM_N );
+            assert headSym != Symbol.NONE;
+            return gen.Apply( gen.Select( pos, arg, headSym ),
+                              Tree.EMPTY_ARRAY );
+      }
+
+      Tree SeqTrace_headState( Tree arg ) {
+            Scope scp = seqTraceSym().members();
+            Symbol headSym = scp.lookup ( HEADSTATE_N );
+            assert headSym != Symbol.NONE;
+            return gen.Apply( gen.Select( pos, arg, headSym ),
+                              Tree.EMPTY_ARRAY );
+      }
+
+      Tree SeqTrace_tail( Tree arg ) {
+            Scope scp = seqTraceSym().members();
+            Symbol tailSym = scp.lookup ( TAIL_N );
+            assert tailSym != Symbol.NONE;
+            return gen.Apply( gen.Select( pos, arg, tailSym ),
+                              Tree.EMPTY_ARRAY );
+      }
+
+      /** `<seqlist>.head()'
+       */
+      Tree SeqList_head( Tree arg ) {
+            Scope scp = seqListSym().members();
+            Symbol headSym = scp.lookup ( HEAD_N );
+            assert headSym != Symbol.NONE;
+            return gen.Apply( make.Select( pos,
+                                           arg,
+                                           HEAD_N )
+                              .setType( headSym.type() )
+                              .setSymbol( headSym ),
+                              Tree.EMPTY_ARRAY);
+      }
+
     /** return the analyzed type
      */
     public Type typeOf(Symbol sym) {
diff --git a/sources/scalac/transformer/matching/FreshVariableTraverser.java b/sources/scalac/transformer/matching/FreshVariableTraverser.java
new file mode 100644
index 0000000000..7010aae5da
--- /dev/null
+++ b/sources/scalac/transformer/matching/FreshVariableTraverser.java
@@ -0,0 +1,46 @@
+package scalac.transformer.matching ;
+
+import scalac.ast.Traverser ;
+
+import scalac.ast.Tree;
+import Tree.Ident;
+import Tree.Bind;
+
+import scalac.util.Name;
+import scalac.util.FreshNameCreator ;
+
+import scalac.symtab.* ;
+
+import java.util.HashMap;
+import java.util.Vector;
+
+class FreshVariableTraverser extends VariableTraverser {
+
+      int    pos;
+      Symbol owner;
+      FreshNameCreator fresh;
+
+      public HashMap helpMap ;
+
+      public FreshVariableTraverser( int pos,
+                                     Symbol owner,
+                                     FreshNameCreator fresh) {
+            this.pos   = pos;
+            this.owner = owner;
+            this.fresh = fresh;
+
+            helpMap  =  new HashMap();
+      }
+
+      void handleVariableSymbol( Symbol sym ) {
+            Symbol helpVar = new TermSymbol( pos,
+                                             fresh.newName( sym.name
+                                                            .toString() ),
+                                             owner,
+                                             0)
+                  .setType( sym.type() );
+
+            helpMap.put( sym, helpVar );
+      }
+
+}
diff --git a/sources/scalac/transformer/matching/LeftTracerInScala.java b/sources/scalac/transformer/matching/LeftTracerInScala.java
new file mode 100644
index 0000000000..c56eeee368
--- /dev/null
+++ b/sources/scalac/transformer/matching/LeftTracerInScala.java
@@ -0,0 +1,373 @@
+package scalac.transformer.matching ;
+
+import scalac.*;
+import scalac.ast.*;
+import scalac.symtab.*;
+import Tree.*;
+import scalac.util.Name;
+
+import scalac.transformer.TransMatch.Matcher ;
+
+import java.util.* ;
+
+import ch.epfl.lamp.util.Position;
+
+public class LeftTracerInScala extends Autom2Scala {
+
+      Tree selector;
+
+      /** symbol of the accumulator ( scala.SequenceList )
+       */
+      Symbol accumSym;
+
+
+      Type _accumType( Type elemType ) {
+            return new Type.TypeRef( defs.SCALA_TYPE,
+                                     cf.seqTraceSym(),
+                                     new Type[] { elemType });
+      }
+
+
+      Matcher _m ;
+      public LeftTracerInScala( DetWordAutom dfa,
+                                Type elementType,
+                                Matcher m,
+                                CodeFactory cf ) {
+            // ignore clazzOwner!
+            super( dfa, elementType, m.owner, cf );
+            this._m = m;
+            this.selector = m.selector;
+            helpMap = new HashMap();
+            helpVarDefs = new Vector();
+
+      }
+
+
+      // SAME AS IN RightTracerInScala,
+      // todo create common abstract superclass Tracer/TransducerInScala,
+      // move WordAutom down.
+      HashMap helpMap ;
+      Vector  helpVarDefs;
+
+      Symbol makeHelpVar( Symbol realVar ) {
+	  Symbol helpVar = new TermSymbol( //Kinds.VAR,
+                                             pos,
+                                             cf.fresh.newName( realVar.name
+                                                               .toString() ),
+                                             owner,
+                                             0)
+                  .setType( cf.SeqListType( elementType ) ) ;
+
+            helpMap.put( realVar, helpVar );
+
+            Tree varDef = gen.ValDef(helpVar, cf.newSeqNil( elementType ));
+            //((ValDef) varDef).kind = Kinds.VAR;
+            helpVarDefs.add( varDef );
+            return helpVar;
+      }
+
+      Symbol makeHelpVarSEQ( Tree pat ) {
+            String  helpName = String.valueOf( pat.hashCode() ); //wicked, in'it ?
+            Symbol helpVar =
+		new TermSymbol( /*Kinds.VAR, */pos,
+                                  cf.fresh.newName(Name.fromString( helpName )),
+                                  owner,
+                                  0)
+                  .setType( pat.type() ) ;
+
+            ValDef varDef = (ValDef) gen.ValDef( helpVar,
+                                                 cf.ignoreValue( pat.type() ));
+            //varDef.kind = Kinds.VAR;
+            helpVarDefs.add( varDef );
+            return helpVar;
+      }
+
+      // SAME AS RIGHT
+      Tree refHelpVar( Symbol realVar ) {
+            Symbol hv = (Symbol)helpMap.get( realVar );
+            assert hv != null : realVar;
+            return gen.Ident( Position.NOPOS, hv );
+      }
+
+      // SAME AS RIGHT
+      Tree assignToHelpVar( Symbol realVar, Tree rhs ) {
+            Tree hv = refHelpVar( realVar );
+            return gen.Assign( hv, rhs );
+      }
+
+      void handleVars( Vector freeVars ) {
+            for(Iterator it = freeVars.iterator(); it.hasNext(); ) {
+                  makeHelpVar( (Symbol) it.next() );
+            }
+      }
+
+      Tree bindVar(Symbol realVar) {
+            Tree hv = refHelpVar( realVar );
+            System.out.println("realVar.name "+realVar.name+" type:"+realVar.type());
+            if( realVar.type().isSameAs( elementType ))
+                  return gen.ValDef( realVar, cf.SeqList_head( hv ));
+            else
+                  return gen.ValDef( realVar, hv);
+
+      }
+
+
+      /** returns a Tree whose type is boolean.
+       *  now we care about free vars
+       */
+      /*
+      Tree handleBody( HashMap helpMap ) {
+            Tree res[] = new Tree[ helpMap.keySet().size() + 1 ];
+            int j = 0;
+            for( Iterator it = helpMap.keySet().iterator(); it.hasNext(); ) {
+                  Symbol vsym = (Symbol) it.next();
+                  Symbol hv   = (Symbol) helpMap.get( vsym );
+                  hv.type( cf.SeqListType( elementType ) ) ;
+                  Tree refv   = gen.Ident(Position.NOPOS, vsym);
+                  Tree refhv  = gen.Ident(Position.NOPOS, hv);
+                  res[ j++ ] = gen.Assign( refhv, refv );
+            }
+
+            res[ j ] = super.handleBody( freeVars ); // just `true'
+
+            return cf.Block(Position.NOPOS, res, res[j].type() );
+      }
+*/
+      protected void initializeSyms() {
+            funSymName = "leftTracer";
+
+            nestedMap = new HashMap();
+
+            super.initializeSyms();
+
+            this.accumSym = newParam("accum")                    // accumulator
+                  .setType( _accumType( elementType ));
+
+            this.funSym
+                  .setType( new Type.MethodType( new Symbol[] {
+                        accumSym, iterSym, stateSym},
+                                              _accumType( elementType )));
+
+            // 2 do: rename switchresultsym to something else...
+
+            this.resultSym = new TermSymbol( //Kinds.VAR,
+                                                   pos,
+                                                   cf.fresh.newName("trace"),
+                                                   owner,
+                                                   0 )
+                  .setType( _accumType( elementType ) ) ;
+
+      }
+
+      /** do the translation
+      public void translate() {
+            initializeSyms();
+            Tree tb = code_body();
+            theDefDef = gen.DefDef( this.funSym,
+                                    tb );
+      }
+       */
+
+      // should throw an exception here really, e.g. MatchError
+      Tree code_fail() {
+
+            return gen.Ident( accumSym.pos, accumSym );
+
+      }
+
+
+
+      /** returns translation of transition with label from i.
+       *  returns null if there is no such transition(no translation needed)
+       */
+      Tree code_delta( int i, Label label ) {
+            Integer target = dfa.delta( i, label );
+            /*
+            System.out.println("LeftTracer:calling dfa.delta("+i+","+label+")");
+            System.out.println("result: "+target);
+            */
+            if( target == null )
+                  return null;
+
+            // (optimization) that one is a dead state (does not make sense for tracer)
+            /*
+              if( target == dfa.nstates - 1 )
+            return code_fail();
+            */
+            Tree newAcc = cf.newSeqTraceCons(new Integer(i),
+                                             currentElem(),
+                                             _ref( accumSym ));
+
+            return callFun( new Tree[] { newAcc , _iter(), cf.Int( target )} );
+      }
+
+
+      /** return code for state i of the dfa SAME AS IN SUPER, ONLY SINK IS GONE
+       */
+      Tree code_state( int i, Tree elseBody ) {
+
+            Tree runFinished; // holds result of the run
+            int  finalSwRes;
+
+            runFinished = run_finished( i );
+
+            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();
+            // transitions of state i
+
+            HashMap trans = ((HashMap[])dfa.deltaq)[ i ];
+
+            for( Iterator labs = ((HashMap)dfa.deltaq( i )).keySet().iterator();
+                 labs.hasNext() ; ) {
+                  Object label = labs.next();
+                  Integer next = (Integer) trans.get( label );
+
+
+                  Tree action = code_delta( i, (Label) label );
+
+                  if( action != null ) {
+
+                        stateBody = cf.If( _cur_eq( _iter(), (Label) label ),
+                                         action,
+                                         stateBody);
+                  }
+            }
+
+            return wrapStateBody( stateBody,
+                                  elseBody,
+                                  runFinished,
+                                  i );
+
+      }
+
+      Tree[] getTrace() {
+
+            initializeSyms();
+            Tree tb = code_body();
+            theDefDef = gen.DefDef( this.funSym,
+                                    tb );
+
+            Vector v = new Vector();
+
+            v.addAll( helpVarDefs );
+
+            //
+            // `def leftTracer(...) = ...'                 the function definition
+            v.add( theDefDef );
+
+            Tree emptyAcc    = cf._seqTraceNil( elementType );
+
+            // the valdef is needed, because passing emptyAcc as a parameter
+            //   results in a ClassCastException at runtime (?!)
+
+            Symbol emptyAccSym = new TermSymbol( //Kinds.VAR,
+                                                 pos,
+                                                 cf.fresh.newName("acc"),
+                                                 owner,
+                                                 0 )
+                  .setType( _accumType( elementType ) ) ;
+
+            // `val acc = SeqNil[ elementType ]'                 init accumulator
+            v.add( gen.ValDef( pos, emptyAccSym, emptyAcc) );
+
+            Tree run = callFun( new Tree[] {
+                  gen.Ident( pos, emptyAccSym ),
+                  cf.newIterator( selector ),
+                  cf.Int( 0 )  });
+
+            run = gen.ValDef( Position.NOPOS, resultSym, run );
+
+            v.add( run );
+
+            // vars...
+            for( Iterator it = helpMap.keySet().iterator(); it.hasNext(); ) {
+                  v.add( bindVar( (Symbol) it.next()) );
+            }
+
+            /* IF YOU NEED DEBUG OUTPUT AT RUNTIME
+            v.add( cf.debugPrintRuntime( "the trace is" ) );
+            v.add( cf.debugPrintRuntime( gen.Ident( pos, resultSym ) ) );
+            v.add( cf.debugPrintNewlineRuntime( "" ) );
+            */
+
+            Tree res[] = new Tree[ v.size() ];
+            int j = 0;
+            for( Iterator it = v.iterator(); it.hasNext(); )
+                  res[ j++ ] = (Tree) it.next();
+
+            _m.varMap = nestedMap;
+
+            return res;
+
+      }
+
+      public HashMap nestedMap;
+
+      // calling the AlgebraicMatcher here
+      Tree _cur_match( Tree pat ) {
+            //System.out.println("calling algebraic matcher on type:"+pat.type);
+
+            Matcher m = new Matcher( funSym,
+                                     currentElem(),
+                                     defs.BOOLEAN_TYPE );
+
+            if( CollectVariableTraverser.containsBinding( pat )) {
+                  switch( pat ) {
+                  case Sequence(Tree[] pats):
+                        //System.out.println("ouch! v Left");
+                        Symbol hv = makeHelpVarSEQ( pat );
+                        nestedMap.put( pat, hv );
+                        Tree stm  = gen.Assign( gen.Ident(0, hv), currentElem() );
+                        m.stms = new Tree[2];
+                        m.stms[0] = stm;
+                        m.stms[1] = gen.mkBooleanLit(Position.NOPOS, true);
+                        return cf.Block( 0, m.stms, m.stms[1].type() );
+                  }
+            }
+
+            FreshVariableTraverser fv = new FreshVariableTraverser(pos,
+                                                                   owner,
+                                                                   cf.fresh);
+            fv.traverse( pat );
+            HashMap helpMap = fv.helpMap;
+            //System.out.println("varMap: "+helpMap );
+
+            m.varMap = fv.helpMap;
+
+            //replaceVars( pat );
+
+            am.construct( m, new CaseDef[] {
+                  (CaseDef) cf.make.CaseDef( pat.pos,
+                                             pat,
+                                             Tree.Empty,
+                                             handleBody( fv.helpMap )),
+                        (CaseDef) cf.make.CaseDef( pat.pos,
+                                                   cf.make.Ident(pat.pos, WILDCARD_N)
+                                                   .setSymbol( Symbol.NONE )
+                                                   .setType(pat.type()),
+                                                   Tree.Empty,
+                                                   gen.mkBooleanLit(Position.NOPOS, false)) }/*,
+											       false */
+                          );
+            Tree res = am.toTree().setType( defs.BOOLEAN_TYPE );
+            //System.out.println("freeVars: "+freeVars);
+
+            return res;
+      }
+
+
+      /** return the accumulator + last state
+       */
+      Tree run_finished( int state ) {
+            return cf.newSeqTraceCons(new Integer( state ),
+                                      cf.ignoreValue( elementType ),
+                                      _ref( accumSym ));
+      }
+
+}
diff --git a/sources/scalac/transformer/matching/NoSeqVariableTraverser.java b/sources/scalac/transformer/matching/NoSeqVariableTraverser.java
new file mode 100644
index 0000000000..50a3ec55f3
--- /dev/null
+++ b/sources/scalac/transformer/matching/NoSeqVariableTraverser.java
@@ -0,0 +1,43 @@
+package scalac.transformer.matching ;
+
+import scalac.util.Name ;
+import scalac.ast.Tree ;
+import scalac.ast.Traverser ;
+import scalac.symtab.Symbol ;
+
+import java.util.Vector;
+
+class NoSeqVariableTraverser extends CollectVariableTraverser {
+
+      public void traverse(Tree tree) {
+            switch (tree) {
+            case Sequence(_):
+                  return ;
+            default:
+                  super.traverse( tree );
+            }
+      }
+
+
+      public NoSeqVariableTraverser() {
+            super();
+      }
+
+      static Vector varsNoSeq( Tree  pat ) {
+
+            NoSeqVariableTraverser nvt = new NoSeqVariableTraverser();
+            nvt.traverse( pat );
+            return nvt.vars;
+
+      }
+
+      static Vector varsNoSeq( Tree[]  pats ) {
+
+            NoSeqVariableTraverser nvt = new NoSeqVariableTraverser();
+            for(int i = 0; i < pats.length; i++)
+                  nvt.traverse( pats[ i ] );
+            return nvt.vars;
+
+      }
+
+}
diff --git a/sources/scalac/transformer/matching/RightTracerInScala.java b/sources/scalac/transformer/matching/RightTracerInScala.java
new file mode 100644
index 0000000000..f41370708c
--- /dev/null
+++ b/sources/scalac/transformer/matching/RightTracerInScala.java
@@ -0,0 +1,500 @@
+package scalac.transformer.matching ;
+
+import scalac.*;
+import scalac.ast.*;
+import scalac.symtab.*;
+import Tree.*;
+
+import scalac.transformer.TransMatch.Matcher ;
+
+import java.util.* ;
+import Scope.SymbolIterator;
+
+import scalac.ast.printer.TextTreePrinter ;
+
+import ch.epfl.lamp.util.Position;
+
+public class RightTracerInScala extends Autom2Scala  {
+
+      //Scope  scp;
+      //Symbol vars[];
+
+      Vector seqVars;
+      Vector allVars;
+
+      Matcher _m;
+
+      /** translate right tracer to code
+       * @param dfa determinized left tracer
+       * @param left nondeterm. left tracer
+       * @param cf   ...
+       * @param pat  ?
+       * @param elementType ...
+       */
+      public RightTracerInScala( DetWordAutom dfa,
+                                 NondetWordAutom left,
+                                 Matcher m,
+                                 CodeFactory cf,
+                                 Tree pat,
+                                 Type elementType ) {
+            super( dfa, elementType, m.owner, cf );
+            this._m = m;
+
+
+            Vector seqVars = new Vector();
+
+            for( int j = 0; j < left.nstates; j++ ) {
+                  if( left.qbinders[ j ] != null )
+                        for( Iterator it = left.qbinders[ j ].iterator();
+                             it.hasNext() ; ) {
+                              Symbol varSym = (Symbol) it.next();
+
+                              if( !seqVars.contains( varSym ) )
+                                    seqVars.add( varSym );
+                        }
+            }
+
+            this.seqVars = seqVars;
+
+            //System.out.println("seqVars:" +seqVars);
+            //Vector varsToExport = NoSeqVariableTraverser.varsNoSeq( pat );
+            //System.out.println("var2expo:" +varsToExport);
+
+
+            CollectVariableTraverser cv = new CollectVariableTraverser();
+            cv.traverse( pat );
+
+            //System.out.println("allVars:" +allVars);
+            this.allVars = cv.vars;
+
+            helpMap = new HashMap();
+            helpMap2 = new HashMap();
+            helpVarDefs = new Vector();
+
+            for( Iterator it = seqVars.iterator(); it.hasNext(); ) {
+                  makeHelpVar( (Symbol) it.next() );
+            }
+
+            for( Iterator it = allVars.iterator(); it.hasNext(); ) {
+                  Symbol varSym = (Symbol) it.next();
+                  if( !seqVars.contains( varSym )) {
+                        makeHelpVar( varSym, true );
+                  }
+            }
+
+            initializeSyms();
+      }
+
+      //      Symbol funSym;
+
+      Symbol elemSym;
+      Symbol targetSym;
+
+      HashMap helpMap ;
+      HashMap helpMap2 ;
+      Vector  helpVarDefs;
+
+      void makeHelpVar( Symbol realVar ) {
+            makeHelpVar( realVar, false );
+      }
+
+      void makeHelpVar( Symbol realVar, boolean keepType ) {
+	  Symbol helpVar = new TermSymbol( //Kinds.VAR,
+                                             pos,
+                                             cf.fresh.newName( realVar.name
+                                                               .toString() ),
+                                             owner,
+                                             0);
+
+            //System.out.println("making helpvar : "+realVar+" -> "+helpVar);
+
+            if( keepType )
+                  helpVar.setType( realVar.type() );
+            else
+                  helpVar.setType( cf.SeqListType( elementType ) );
+
+
+            helpMap.put( realVar, helpVar );
+
+            Tree rhs;
+            if( keepType )
+                  rhs = cf.ignoreValue( realVar.type() );
+            else
+                  rhs = cf.newSeqNil( elementType );
+
+            Tree varDef = gen.ValDef(helpVar, rhs);
+            //((ValDef) varDef).kind = Kinds.VAR;
+            helpVarDefs.add( varDef );
+
+      }
+
+      Tree refHelpVar( Symbol realVar ) {
+            Symbol hv = (Symbol)helpMap.get( realVar );
+            assert hv != null : realVar;
+            return gen.Ident(Position.NOPOS, hv);
+      }
+
+      Tree prependToHelpVar( Symbol realVar, Tree elem ) {
+            Tree hv = refHelpVar( realVar );
+            return gen.Assign( hv, cf.newSeqCons( elem, hv ));
+            /*
+            return cf.Block(pos,
+                            new Tree [] {
+                  cf.debugPrintRuntime( "ASSIGN" ),
+                  gen.Assign( hv, cf.newSeqCons( elem, hv ))
+                        }, defs.UNIT_TYPE);
+            */
+      }
+
+      Tree bindVar(Symbol realVar) {
+            Tree hv = refHelpVar( realVar );
+            //System.out.println("binding realVar.name "+realVar.name+" type:"+realVar.type()+" to smth");
+            realVar.setOwner( owner );
+            if( realVar.type().isSameAs( elementType ))
+                  return gen.ValDef( realVar, cf.SeqList_head( hv ));
+            else
+                  return gen.ValDef( realVar, hv);
+
+      }
+
+      protected void initializeSyms() {
+
+            this.funSym = newFunSym( "binder" );
+
+            this.iterSym = new TermSymbol( //Kinds.VAL,
+                                           pos,
+                                           cf.fresh.newName("iter"),
+                                           funSym,
+                                           0)
+                  .setType( cf.SeqTraceType( elementType ));
+
+            this.stateSym = new TermSymbol( //Kinds.VAL,
+                                            pos,
+                                            cf.fresh.newName("q"),
+                                            funSym,
+                                            0 )
+                  .setType( defs.INT_TYPE ) ;
+
+            this.elemSym = new TermSymbol( //Kinds.VAL,
+                                           pos,
+                                           cf.fresh.newName("elem"),
+                                           funSym,
+                                           0)
+                  .setType( elementType ) ;
+
+            this.targetSym = new TermSymbol( //Kinds.VAL,
+                                             pos,
+                                             cf.fresh.newName("trgt"),
+                                             funSym,
+                                             0)
+                  .setType( defs.INT_TYPE ) ;
+
+
+            funSym.setType( new Type.MethodType( new Symbol[] {
+                  iterSym, stateSym },  defs.UNIT_TYPE ));
+
+      }
+
+      // same as in LeftTracer
+      Tree code_fail() {
+
+            return cf.ThrowMatchError( Position.NOPOS, defs.UNIT_TYPE );
+
+      }
+
+      public Tree code_body() {
+
+            Tree body = code_fail(); // never reached at runtime.
+
+            // state [ nstates-1 ] is the dead state, so we skip it
+
+            //`if( state == q ) <code_state> else {...}'
+            for( int i = dfa.nstates-1; i >= 0; i-- ) {
+                  body = code_state( i, body );
+            }
+
+
+            Tree t3 = cf.If( cf.isEmpty( _iter() ),
+                               run_finished( 0 ),
+                               gen.Block( new Tree[] {
+                                     gen.ValDef( targetSym,
+                                                 cf.SeqTrace_headState( gen.Ident( pos, iterSym))),
+                                     gen.ValDef( elemSym,
+                                                 cf.SeqTrace_headElem( gen.Ident( pos, iterSym))),
+
+                                     body }));
+
+            /*
+            t3 = gen.Block( new Tree[] {
+                  cf.debugPrintRuntime("enter binderFun"),
+                  cf.debugPrintRuntime(" state:"),
+                  cf.debugPrintRuntime( gen.Ident( pos, stateSym )),
+                  cf.debugPrintRuntime(" iter:"),
+                  cf.debugPrintRuntime(_iter()),
+                  cf.debugPrintNewlineRuntime(""),
+                  t3 });
+            */
+
+            //System.out.println("enter RightTracerInScala:code_body()");// DEBUG
+            //System.out.println("dfa.nstates"+dfa.nstates);// DEBUG
+            return t3;
+      }
+
+      /** 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
+
+            HashMap hmap    = (HashMap) dfa.deltaq( 0 ); // all the initial states
+
+            Tree stateBody = code_fail(); // never happens
+
+            for( Iterator it = hmap.keySet().iterator(); it.hasNext(); ) {
+                  Integer targetL  = (Integer) it.next();
+                  Integer targetR  = (Integer) hmap.get( targetL );
+
+                  stateBody = cf.If( cf.Equals( gen.Ident( pos, targetSym ),
+                                                cf.Int( targetL )),
+                                     callFun( new Tree[] {
+                                           cf.SeqTrace_tail( _iter() ),
+                                           cf.Int( targetR ) }),
+                                     stateBody );
+            }
+
+            return cf.If( cf.Equals( _state(), cf.Int( 0 )),
+                          stateBody ,
+                          elseBody );
+
+      }
+
+      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();
+
+            // transitions of state i
+
+            HashMap trans = ((HashMap[])dfa.deltaq)[ i ];
+
+            for( Iterator labs = dfa.labels.iterator(); labs.hasNext() ; ) {
+                  Object label = labs.next();
+                  Integer next = (Integer) trans.get( label );
+
+                  Tree action = code_delta( i, (Label) label );
+
+                  if( action != null ) {
+
+                        stateBody = cf.If( _cur_eq( _iter(), (Label) label ),
+                                           action,
+                                           stateBody);
+                  }
+            }
+
+            return wrapStateBody0( stateBody,
+                                   elseBody,
+                                   i );
+      }
+
+      /** returns a Tree whose type is boolean.
+       *  now we care about free vars
+       */
+
+      Tree handleBody( Object o ) {
+            HashMap helpMap = (HashMap) o;
+            Tree res[] = new Tree[ helpMap.keySet().size() + 1 ];
+            int j = 0;
+            for( Iterator it = helpMap.keySet().iterator(); it.hasNext(); ) {
+                  Symbol vsym = (Symbol) it.next();
+                  Symbol hv   = (Symbol) helpMap.get( vsym );
+                  hv.setType( cf.SeqListType( elementType ) ) ;
+                  Tree refv   = gen.Ident(Position.NOPOS, vsym);
+                  Tree refhv  = gen.Ident(Position.NOPOS, hv);
+                  res[ j++ ] = gen.Assign( refhv, refv );
+            }
+
+            res[ j ] = super.handleBody( freeVars ); // just `true'
+
+            return cf.Block(Position.NOPOS, res, res[j].type() );
+      }
+
+      // calling the AlgebraicMatcher here
+      Tree _cur_match( Tree pat ) {
+
+            //System.out.println("RTiS._cur_match("+TextTreePrinter.toString(pat)+")");
+
+            //System.out.println("calling algebraic matcher on type:"+pat.type);
+
+            Matcher m = new Matcher( funSym,//this.funSym,
+                                     currentElem(),
+                                     defs.BOOLEAN_TYPE );
+
+            Vector varsToExport = NoSeqVariableTraverser.varsNoSeq( pat );
+
+            //System.out.println("RightTracerInScala::varsToExport :"+varsToExport);
+
+            for( Iterator it = varsToExport.iterator(); it.hasNext(); ) {
+                  Symbol key = (Symbol) it.next();
+                  this.helpMap2.put( key, helpMap.get( key ));
+            }
+
+            am.construct( m, new CaseDef[] {
+                  (CaseDef) cf.make.CaseDef( pat.pos,
+                                             pat,
+                                             Tree.Empty,
+                                             handleBody( helpMap2 )),
+                        (CaseDef) cf.make.CaseDef( pat.pos,
+                                                   cf.make.Ident(pat.pos, WILDCARD_N)
+                                                   .setSymbol( Symbol.NONE )
+                                                   .setType(pat.type()),
+                                                   Tree.Empty,
+                                                   gen.mkBooleanLit( pat.pos, false )) }/*,
+                          true // do binding please */
+                          );
+            Tree res = am.toTree().setType( defs.BOOLEAN_TYPE );
+            //System.out.println("freeVars: "+freeVars);
+            return res;
+      }
+
+
+      /** returns translation of transition with label from i.
+       *  returns null if there is no such transition(no translation needed)
+       */
+      Tree code_delta( int i, Label label ) {
+            HashMap hmap    = (HashMap) dfa.deltaq( i );
+            Integer ntarget = (Integer) hmap.get( label );
+            Tree    algMatchTree = null;
+            if( ntarget == null )
+                  return null;
+            //System.out.println("delta("+i+","+label+")" );
+            Label theLab = null;
+            switch(label) {
+            case Label.Pair( Integer state, Label lab2 ):
+                  //assert ntarget == state;
+                  theLab = lab2;
+                  switch( lab2 ) {
+                  case TreeLabel( Tree pat ):
+                        algMatchTree = _cur_match( pat );
+                        break;
+                  }
+                  break;
+            case DefaultLabel:
+                  throw new ApplicationError(); // should not happen
+            }
+            assert dfa.qbinders != null : "qbinders ?";
+
+            Vector vars = dfa.qbinders[ i ];
+
+            if( vars == null ) vars = new Vector(); // TODO: make this more consistent
+            assert vars != null;
+
+            //System.out.println("delta: theLab: " + theLab + " vars in current ="+ vars );
+
+            if( ntarget == null )
+                  return code_fail();
+
+            Tree stms[] = new Tree[ vars.size()
+                                    + ((algMatchTree != null )? 1 : 0 )
+                                    + 1 ];
+            int j = 0;
+            for( Iterator it = vars.iterator(); it.hasNext(); ) {
+                  Symbol var = (Symbol) it.next();
+
+                  /*Tree field = gen.Select( gen.Ident( pos, accumSym ),
+                                           var.name ).setSymbol( var );
+                  */
+                  //Tree field = gen.Ident( pos, var );
+                  Tree rhs = gen.Ident( pos, elemSym ); //cf._cur( _iter() );
+
+                  stms[ j++ ] = prependToHelpVar( var , rhs);
+            }
+
+            if( algMatchTree != null )
+                  stms[ j++ ] = algMatchTree ;
+
+            stms[ j ] = callFun( new Tree[] { cf.SeqTrace_tail( _iter() ),
+                                              cf.Int( ntarget ) } );
+
+            return cf.Block( pos, stms, funRetType() );
+      }
+
+      /* 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, cf.Int( 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 the accumulator. (same as in LeftTracerInScala)
+       */
+      Tree run_finished( int state ) {
+            //return gen.Ident( accumSym.pos, accumSym );
+            return gen.New( pos, defs.SCALA_TYPE, defs.UNIT_CLASS,
+                            Type.EMPTY_ARRAY,
+                            Tree.EMPTY_ARRAY);
+
+
+      }
+
+      Tree current() {
+            return gen.Ident( pos, targetSym );
+      }
+
+      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( cf.Int( target ),
+                                    current() );
+            }
+            throw new ApplicationError("expected Pair label");
+      }
+
+
+}
diff --git a/sources/scalac/transformer/matching/SequenceMatcher.java b/sources/scalac/transformer/matching/SequenceMatcher.java
new file mode 100644
index 0000000000..ef68b8a909
--- /dev/null
+++ b/sources/scalac/transformer/matching/SequenceMatcher.java
@@ -0,0 +1,285 @@
+package scalac.transformer.matching ;
+
+import scalac.*;
+import scalac.ast.Tree;
+import scalac.typechecker.*;
+import Tree.*;
+
+//import scala.compiler.printer.TextTreePrinter ; // DEBUGGING\
+    //import scala.compiler.printer.XMLAutomPrinter ; // DEBUGGING\
+
+import scalac.transformer.TransMatch.Matcher ;
+import scalac.ast.* ;
+import scalac.symtab.* ;
+
+import java.util.* ;
+
+import ch.epfl.lamp.util.Position;
+
+/** constructs a matcher for a sequence pattern. plays two roles in
+ *  described in design pattern Builder.
+ *  is the "Director" for "Builder" class BerrySethi.
+ *  is the "Builder" for "Director" class TransMatch.
+ */
+
+public class SequenceMatcher extends PatternTool {
+
+      CodeFactory cf;
+
+      Matcher _m;
+
+      Tree pat[];
+      Tree body[];
+
+    /*
+      public Tree[] getNested( HashMap varMap ) {
+            Tree[][] stmsNest = new Tree[varMap.size()][];
+            int i = 0;
+            int k = 0;
+            for( Iterator it = varMap.keySet().iterator() ; it.hasNext(); ) {
+                  Tree pat = (Tree) it.next(); // contains variables
+                  Symbol v = (Symbol) varMap.get( pat );
+
+                  BindingBerrySethi build = new BindingBerrySethi();
+                  NondetWordAutom leftNest = build.automatonFrom( pat,
+                                                                  new Integer( 0 ));
+
+                  DetWordAutom dLeftNest  = new DetWordAutom( leftNest );
+
+                  NondetWordAutom rightNest = build.revnfa;
+
+                  Matcher mNest = new Matcher( _m.owner, _m.selector, null );
+
+                  LeftTracerInScala ltisNest =
+                        new LeftTracerInScala( dLeftNest,
+                                               cf.getElemType( pat.type() ),
+                                               mNest,
+                                               cf );
+                  Tree stmsLeftNest[] = ltisNest.getTrace();
+
+                  Tree selNest = gen.Ident( 0, ltisNest.resultSym );
+
+                  DetWordAutom dRightNest =
+                        new DetWordAutom( rightNest, leftNest, dLeftNest);
+
+                  RightTracerInScala rtisNest =
+                        new RightTracerInScala( dRightNest, leftNest, mNest,
+                                                cf, pat, cf.getElemType(pat.type()));
+
+                  Tree stmsRightNest[] = rtisNest.getStms( gen.Ident( 0, v ) );
+                  stmsNest[ i ] = new Tree[ stmsLeftNest.length
+                                            + stmsRightNest.length ];
+
+                  System.arraycopy( stmsLeftNest, 0,
+                                    stmsNest[ i ], 0, stmsLeftNest.length );
+                  System.arraycopy( stmsRightNest, 0, stmsNest[ i ],
+                                    stmsLeftNest.length, stmsRightNest.length );
+                  k += stmsNest[ i ].length;
+                  i++;
+            }
+            // flatten
+            Tree[] res = new Tree[ k ];
+            k = 0;
+            for( i = 0; i < varMap.size(); i++ ) {
+                  System.arraycopy( stmsNest[ i ], 0, res, k, stmsNest[ i ].length );
+                  k += stmsNest[ i ].length;
+            }
+            return res;
+      }
+    */
+
+      // translates the det/switching automaton to scala code
+
+      Tree addBinderToBody( Tree pat, Tree body ) {
+
+            SplitNested spn = new SplitNested( pat, _m.owner, cf );
+
+
+            pat = spn.flatPat; // flat pattern - no nested sequences present
+
+            for( Iterator it = spn.nestedVarToPats.keySet().iterator();
+                 it.hasNext(); ){
+                  Symbol v = (Symbol) it.next();
+                  Tree nestPat = (Tree) spn.nestedVarToPats.get( v );
+                  Matcher mNest = new Matcher( _m.owner, gen.Ident(0, v), null );
+
+                  Matcher saveM = _m; _m = mNest;
+
+                  Tree nbody = addBinderToBody( nestPat, body );
+                  _m = saveM;
+                  body = nbody;
+            }
+
+            Type elementType = cf.getElemType( pat.type() );
+
+            BindingBerrySethi build = new BindingBerrySethi();
+            NondetWordAutom left =  build.automatonFrom( pat, new Integer(0) );
+            NondetWordAutom right = build.revnfa;
+
+            //  - - -> left
+
+            DetWordAutom dLeft  =
+                  new DetWordAutom( left );
+
+            Matcher mL = new Matcher( _m.owner, _m.selector, null );
+
+            LeftTracerInScala ltis =
+                  new LeftTracerInScala( dLeft, elementType, mL, cf);
+
+            Tree stms[] = ltis.getTrace();
+
+            Tree sel = gen.Ident( 0, ltis.resultSym );
+
+            // <- - - right
+
+            DetWordAutom dRight =
+                  new DetWordAutom( right, left, dLeft);
+
+            //System.out.println( "vars: "+vars );
+            int j;
+
+            RightTracerInScala rtis =
+                  new RightTracerInScala( dRight, left, mL,
+                                          cf, pat, elementType );
+
+            Tree stms2[] = rtis.getStms( sel );             // to scala
+
+            // run them, bind
+
+            Tree items[] = new Tree[ stms.length
+                                     + stms2.length
+                                     + 1 ];
+
+            System.arraycopy( stms, 0, items, 0, stms.length );
+            System.arraycopy( stms2, 0, items, stms.length, stms2.length );
+
+            j = stms.length + stms2.length ;
+            items[ stms.length + stms2.length ] = body;
+
+            AttributedTreeCopier treeCopier = new AttributedTreeCopier(unit.global,
+							     cf.make) ;
+		    /* EXPERIMENT, might not work
+            TreeCopier treeCopier = new TreeCopier(unit.global,
+                                                   unit.global.currentPhase,
+                                                   cf.make) {
+                        // Substitute symbols
+                        public boolean mustSubstituteSymbol(Tree tree) {
+                              switch (tree) {
+                                    //                              case Select(_,_):
+                                      //                              return false;
+                              case Ident(Name n):
+
+                                    //System.out.println("tree.symbol:"+tree.symbol());
+                                    //return true;
+                                    return n.isVariable();
+
+                              default:
+                                    return mustCopySymbol(tree);
+                              }
+                        }
+                  };
+		    */
+
+            //System.out.println("helpmap");
+            //System.out.println( rtis.helpMap2 );
+            treeCopier.pushSymbolSubst( rtis.helpMap2 );
+
+            items[ stms.length + stms2.length ] = treeCopier.copy( body );
+
+            return cf.Block( body.pos, items, body.type );
+      }
+
+      /** turns body `case pat(x,y,z) => body' into
+       **  `{ <runLeft>;<runRight>;body }' if
+       *  necessary.
+       *  @param body the array containing the bodies of the visitor
+       */
+      Tree[] addBindersToBodies( Tree body[] ) {
+            //System.out.println("addBindersToBodies");
+            Tree nbody[] = new Tree[ body.length ];
+            for( int i = 0; i < body.length; i++ ) {
+                  Integer iI = new Integer( i );
+
+                  if( !CollectVariableTraverser.containsBinding( pat[ i ] ) )
+                        {
+                              nbody[ i ] = body[ i ]; // no need for binding
+                        }
+                  else
+                        {
+                              nbody[ i ] =
+                                    addBinderToBody( pat[ i ], body[ i ] );
+                        }
+            }
+            return nbody;
+      }
+      Type elementType ;
+
+      /** constructs a word recognizer from an array of patterns which
+       *  should all be SequencePatterns ( no wildcard * )
+       *  @param _m          Matcher object, holds the result
+       *  @param pat         the (Sequence) patterns
+       *  @param body        the bodies
+       *  @param defaultCase code that is run when nothing matches. may be null, it
+       *                     becomes a ThrowMatchError then
+
+       */
+      public void construct( Matcher _m,
+                             Tree[] pat,
+                             Tree[] body,
+                             Tree defaultCase,
+                             boolean doBinding ) {
+
+            this.pat  = pat;
+            this.body = body;
+            assert body.length == pat.length;
+            this._m = _m;
+
+            this.cf = new CodeFactory( unit, infer /*, _m.pos*/ );
+
+            Type seqType = pat[ 0 ].type();
+
+            elementType = cf.getElemType( seqType );
+
+            NondetWordAutom manyNfa[] = new NondetWordAutom[ pat.length ];
+
+            BerrySethi build = new BerrySethi();
+
+            for( int i = 0; i < pat.length; i++ )
+                  {
+                        manyNfa[ i ] = build.automatonFrom( pat[ i ],
+                                                            new Integer( i ));
+                  }
+
+            // merge nfas into one if necessary
+
+            NondetWordAutom nfa =
+                  (pat.length > 1) ? new NondetWordAutom( manyNfa )
+                  : manyNfa[ 0 ];
+
+            DetWordAutom dfa = new DetWordAutom( nfa );
+
+            WordAutomInScala scalaAut = new WordAutomInScala( dfa,
+                                                              elementType,
+                                                              _m.owner,
+                                                              cf);
+            scalaAut.translate();
+
+            if( defaultCase == null )
+                  defaultCase = cf.ThrowMatchError( Position.NOPOS, _m.resultType );
+
+            Tree newbody[] = doBinding ? addBindersToBodies( body ): body;
+
+            _m.tree = scalaAut.getMatcherSwitch( _m.selector,
+                                                 defaultCase,
+                                                 newbody,
+                                                 _m.resultType );
+      } // construct (Matcher, Tree[], Tree[], Tree, boolean )
+
+      /** constructor, invoked  by AlgebraicMatcher
+       */
+      SequenceMatcher( Unit unit, Infer infer ) {
+            super( unit, infer );
+            //Symbol predefSym = defs.getModule( defs.SCALA, Names.Predef );
+            //Scope predefScope = predefSym.members();
+      }
+} // class SequenceMatcher
diff --git a/sources/scalac/transformer/matching/SplitNested.java b/sources/scalac/transformer/matching/SplitNested.java
new file mode 100644
index 0000000000..39e6225eb9
--- /dev/null
+++ b/sources/scalac/transformer/matching/SplitNested.java
@@ -0,0 +1,87 @@
+package scalac.transformer.matching ;
+
+import scalac.ast.Tree ;
+import scalac.symtab.Symbol ;
+import scalac.symtab.TermSymbol ;
+import scalac.* ;
+import scalac.util.Name ;
+import java.util.* ;
+import scalac.ast.printer.TextTreePrinter ;
+
+/** given Sequence pattern pat, create flatpatterns flatPat and
+ *  extract the nested (not necessarily flat) patterns pat_1,...,pat_n */
+public class SplitNested {
+
+      CodeFactory cf;
+      Symbol owner;
+
+      Tree origPat ;
+      Tree flatPat ;
+
+      HashMap nestedVarToPats ;
+
+      Tree split( Tree pat ) {
+            //System.out.println("SplitNested::split("+
+            //                   TextTreePrinter.toString(pat)+")");
+            switch( pat ) {
+            case Apply(Tree fun, Tree[] trees):
+                  return new Tree.Apply( fun, split( trees ))
+                        .setType( pat.type() );
+
+            case Sequence(_):  // remove nested sequences, make vars
+                  Name n = cf.fresh.newName("nestseq");
+                  Symbol v = new TermSymbol( 0,
+                                             n,
+                                             owner,
+                                             0)
+                        .setType( pat.type() );
+                  nestedVarToPats.put( v, pat );
+                  return new Tree.ExtBind( n,
+                                           cf.make.Ident( 0, Name.fromString("_"))
+                                           .setType( v.type() ))
+                        .setSymbol( v )
+                        .setType( v.type() );
+
+            case Bind(Name name, Tree subtree):  // remove nested sequences, make vars
+                  return new Tree.ExtBind(name, split( subtree ))
+                        .setType( pat.type() )
+                        .setSymbol( pat.symbol() );
+
+            case Alternative(Tree[] trees):
+                  return new Tree.Alternative( split( trees )) ;
+
+
+            case Subsequence(Tree[] trees):
+                  return new Tree.Subsequence( split( trees )) ;
+
+            default:
+                  return pat;
+            }
+      }
+
+      Tree[] split( Tree pats[] ) {
+            Tree npats[] = new Tree[ pats.length ];
+            for( int i = 0; i < pats.length ; i++ ) {
+                  npats[ i ] = split( pats[ i ] );
+            }
+            return npats;
+      }
+
+      Tree split1( Tree pat ) {
+            switch( pat ) {
+            case Sequence( Tree[] trees ):
+                  return cf.make.Sequence( pat.pos, split( trees ) )
+                        .setType( pat.type() );
+            default:
+                  throw new ApplicationError("SequencePattern expected");
+            }
+      }
+
+      SplitNested(Tree pat, Symbol owner, CodeFactory cf) {
+            origPat = pat;
+            this.cf = cf;
+            this.owner = owner;
+            nestedVarToPats = new HashMap();
+            this.flatPat = split1( pat );
+      }
+}