more 4 matching

11 files changed, 3729 insertions, 0 deletions

diff --git a/sources/scala/tools/nsc/matching/AlgebraicMatcher.scala b/sources/scala/tools/nsc/matching/AlgebraicMatcher.scala
new file mode 100644
index 0000000000..1d32485fcc
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/AlgebraicMatcher.scala
@@ -0,0 +1,159 @@
+/* NSC -- new scala compiler
+ * Copyright 2005 LAMP/EPFL
+ * @author buraq
+ */
+// $Id$
+
+package scala.tools.nsc.matching;
+
+/** the pattern matcher, tweaked to work with regular patterns
+ *  @author Burak Emir
+ */
+trait AlgebraicMatchers : TransMatcher {
+
+  import global._;
+
+ class AlgebraicMatcher extends PatternMatcher {
+
+  import java.util.Vector ;
+  import java.util.Iterator ;
+
+  var _m: PartialMatcher = _;
+
+  override protected var delegateSequenceMatching = true;
+  override protected var optimize = false;
+
+  /** constructs an algebraic pattern matcher from cases */
+  def construct(m: PartialMatcher, cases: List[CaseDef]): Unit =
+    construct(m, cases, true);
+
+  /** constructs an algebraic pattern matcher from cases */
+  def construct(m: PartialMatcher, cases: List[CaseDef], doBinding: Boolean): Unit = {
+    this._m = m;
+    super.initialize( _m.selector, _m.owner, doBinding );
+
+    val it = cases.elements;
+    while (it.hasNext)
+    enter(it.next);
+
+    //if (unit.global.log()) {
+    //  unit.global.log("internal pattern matching structure");
+    //  print();
+    // }
+    _m.tree = toTree();
+  }
+
+
+  /** initializes this AlgebraicMatcher, see Matcher.initialize
+   void initialize() {}
+   */
+  /*
+   def isStarApply(tree: Tree.Apply): Boolean = {
+   val params:Array[Symbol] = tree.fun.getType().valueParams();
+   //System.err.println( tree.fun.type.resultType().symbol() );
+   (tree.args.length == 1)
+   && (tree.getType().symbol().flags & Modifiers.CASE) != 0
+   && params.length > 0
+   && (params(params.length-1).flags & Modifiers.REPEATED) != 0;
+   }
+   */
+  //////////// generator methods
+
+  override def toTree(): Tree = {
+    Block(
+      List (
+        ValDef(root.symbol, _m.selector),
+        ValDef(resultVar, EmptyTree)
+      ),
+      If( super.toTree(root.and),
+         Ident(resultVar ),
+         ThrowMatchError( _m.pos ))
+    );
+  }
+
+  protected override def toTree(node: PatternNode, selector: Tree): Tree = {
+    //System.err.println("AM.toTree called"+node);
+    if (node == null)
+      Literal(false);
+    else node match {
+      case SeqContainerPat( _, _ ) =>
+	callSequenceMatcher( node,
+			    selector );
+      case _ =>
+	super.toTree( node, selector );
+    }
+  }
+
+  /** collects all sequence patterns and returns the default
+   */
+  def collectSeqPats(node1: PatternNode, seqPatNodes: Vector, bodies: Vector): PatternNode = {
+    var node = node1;
+    var defaultNode: PatternNode = null;
+    var exit = false;
+      do {
+        if( node == null )
+          exit=true; //defaultNode = node; // break
+        else
+          node match {
+            case SeqContainerPat( _, _ ) =>
+              seqPatNodes.add( node );
+              bodies.add( super.toTree( node.and ) );
+              node = node.or;
+              exit//defaultNode = node; //               break;
+
+            case _ =>
+              defaultNode = node;
+          }
+      } while (!exit && (null == defaultNode)) ;
+
+    defaultNode;
+  }
+
+  def callSequenceMatcher(node: PatternNode, selector1: Tree):  Tree = {
+
+    //Console.println("calling sequent matcher for"+node);
+    /*    ???????????????????????? necessary to test whether is a Seq?
+     gen.If(selector.pos, maybe And( Is(selector, seqpat.type()) )???)
+     */
+
+    // translate the _.and subtree of this SeqContainerPat
+
+    val seqPatNodes = new Vector();
+    val bodies      = new Vector();
+
+    var defaultNode = collectSeqPats(node, seqPatNodes, bodies);
+
+    val defaultCase = toTree(defaultNode, selector1);
+
+    val wordRec = new SequenceMatcher();
+
+    val m = new PartialMatcher {
+      val owner = _m.owner;
+      val selector = selector1;
+    }
+
+    var pats: scala.List[Tree] = Nil;
+    var body: scala.List[Tree] = Nil;
+
+    val tmp = bodies.toArray();
+    var j = 0;
+    val it = seqPatNodes.iterator();
+    while (it.hasNext()) {
+      //pats(j) = it.next().asInstanceOf[SeqContainerPat].seqpat;
+      pats = it.next().asInstanceOf[SeqContainerPat].seqpat :: pats;
+      //body(j) = tmp(j).asInstanceOf[Tree];
+      body = tmp(j).asInstanceOf[Tree] :: body;
+      j = j + 1;
+    }
+    //Tree defaultTree = toTree(node.or, selector); // cdef.body ;
+
+    wordRec.construct(m, pats.reverse, body.reverse, defaultCase, doBinding);
+
+    //_m.defs.addAll(m.defs);
+
+    m.tree;
+  }
+
+} // class AlgebraicMatcher
+
+}
diff --git a/sources/scala/tools/nsc/matching/Autom2.scala b/sources/scala/tools/nsc/matching/Autom2.scala
new file mode 100644
index 0000000000..0d67f0c419
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/Autom2.scala
@@ -0,0 +1,196 @@
+package scala.tools.nsc.matching ;
+
+//import java.util._ ;
+
+import scala.tools.util.Position;
+
+trait Autom2: TransMatcher {
+
+  import global._;
+
+  /**  @param owner owner of the pattern matching expression
+   */
+  abstract class Autom2Scala {
+
+    val dfa: DetWordAutom;
+    val owner: Symbol;
+
+    protected var optimize = true;
+
+    final val FAIL = -1;
+
+    /** symbol of the matcher DefDef or Label */
+    var funSym:Symbol = _;
+
+    /** symbol of the iterator ( scala.SequenceIterator ) */
+    var iterSym: Symbol = _;
+
+    /** symbol of the switching result ( scala.Int ) */
+    var resultSym: Symbol = _;
+
+    /** symbol of the state variable ( scala.Int ) */
+    var stateSym: Symbol = _;
+
+    /** symbol of variable holding current label */
+    var curSym: Symbol = _;
+
+    /** symbol of boolean variable that indicates we have not reached end of sequence */
+    var hasnSym: Symbol = _;
+
+    val am = new AlgebraicMatcher();
+
+    var pos: Int = Position.FIRSTPOS;
+
+    val elementType: Type;
+
+    def funRetType(): Type = {
+      funSym.tpe match {
+        case MethodType( _, retType )=> retType;
+        case _ => scala.Predef.error("quoi?");
+      }
+    }
+
+    def callFun(args: List[Tree]): Tree = Apply(Ident(funSym),args);
+
+    // overridden in RightTracerInScala
+    def loadCurrentElem(body: Tree): Tree = {
+      Block(
+        List(
+          ValDef(this.hasnSym, _hasNext( _iter() ) ),
+          ValDef(this.curSym, If(Ident( hasnSym ),
+                                 _next( _iter() ),
+                                 EmptyTree))
+        ),
+        body
+      );
+    }
+
+    /** bug ?? */
+    def currentElem() = { Ident( curSym ) }
+
+    def currentMatches(label: Label): Tree = {
+      label match {
+        case TreeLabel( pat ) =>
+          _cur_match( pat );
+        case SimpleLabel(lit: Literal) =>
+          Equals( currentElem(), lit );
+        case _ => // cannot happen
+          scala.Predef.error("expected either algebraic or simple label:"+label);
+      }
+    }
+
+    //
+    // translation of automata to scala code
+    //
+
+
+    /** `[switchResult]' */
+    def _swres(): Tree = { Ident( resultSym );}
+
+    /** `<state>' param */
+    def _state(): Tree = { Ident( stateSym ); }
+
+    /** `<iterator>' param */
+    def  _iter(): Tree = { Ident( iterSym );  }
+
+    /** simple optimization: if we are in a sink state, stop traversing sequence
+     */
+    def stateWrap(i: Int): Tree = {
+      if( dfa.isSink( i ))
+        run_finished( i ); // state won't change! optimization
+      else
+        If( Negate( Ident( hasnSym )),
+           run_finished( i ),
+           code_state_NEW( i ));
+    }
+
+    /** body of the matcherDefFun
+     */
+    def code_body_NEW(): Tree  = {
+      var cases: List[CaseDef] = Nil;
+
+      //val tags   = new Array[Int](dfa.nstates());
+      //val bodies = new Array[Tree](dfa.nstates());
+      var i = 0; while (i < dfa.nstates()) {
+        cases = CaseDef( Literal(i), stateWrap(i)) :: cases;
+        i = i + 1;
+      }
+      //if( optimize )
+      loadCurrentElem( Match( _state(), cases ));
+
+      /*
+       Tree res = code_error();
+       for( int i = dfa.nstates-2; i>= 0; i-- )
+       res = gen.If( Equals( _state(), gen.mkIntLit( pos, i )),
+       bodies[ i ] ,
+       res );
+
+       return loadCurrentElem( res );
+       */
+    }
+
+    /* calling the (AlgebraicMatcher)PatternMatcher here */
+    def _cur_match(pat: Tree): Tree  = {
+      val m:  PartialMatcher = new PartialMatcher {
+        val owner = Autom2Scala.this.funSym;   /* owner*/
+        val selector = currentElem(); /* root */
+                                 /* defs.boolean_TYPE() restype */
+      };
+
+      am.construct( m, List (
+        CaseDef(                 pat, Literal(true)),
+        CaseDef( Ident(nme.WILDCARD), Literal(false))
+      ),
+                   false);
+      am.toTree();
+    }
+
+    // @todo should be abstract
+    def code_delta( i:Int, label: Label): Tree = {
+        scala.Predef.error("should not happen");
+    }
+
+    /** some error happened which is due to bug in translation/automaton
+     */
+    final def code_error(): Tree = {
+        ThrowMatchError( pos /*, funRetType() */);
+    }
+
+    def code_fail(): Tree = {
+      Literal( FAIL ); //gen.mkIntLit(Position.FIRSTPOS, FAIL );
+    }
+
+    /** code for the return value of the automaton translation
+     */
+    def run_finished(state: Int): Tree = {
+      if( dfa.isFinal( state ))
+        Literal(
+          dfa.finals.get( new Integer( state ) ).asInstanceOf[Integer]
+          .intValue()
+        )
+      else
+        Literal( FAIL );
+    }
+
+    def code_state_NEW(i: Int): Tree = {
+      var stateBody = code_delta( i, DefaultLabel() );
+      if( stateBody == null )
+        stateBody = code_fail();
+      val trans = dfa.deltaq( i );
+
+      val  labs = dfa.labels().iterator();
+      while(labs.hasNext()) {
+        val label  = labs.next();
+        val next   = trans.get( label ).asInstanceOf[Integer];
+        val action = code_delta( i, label.asInstanceOf[Label] );
+        if( action != null ) {
+          /*assert*/ //stateBody != null : "stateBody is null";
+          stateBody = If( currentMatches(label.asInstanceOf[Label] ),
+                         action,
+                         stateBody);
+        }
+      }
+      stateBody;
+    }
+  }
+}
diff --git a/sources/scala/tools/nsc/matching/BerrySethi.scala b/sources/scala/tools/nsc/matching/BerrySethi.scala
new file mode 100644
index 0000000000..4e774ad94e
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/BerrySethi.scala
@@ -0,0 +1,800 @@
+package scala.tools.nsc.matching ;
+
+import java.util.{ HashSet, HashMap, TreeSet, TreeMap, Vector };
+
+//import scala.compiler.printer.XMLAutomPrinter;
+
+trait BerrySethis: TransMatcher {
+
+import global._;
+/** a Berry-Sethi style construction for nfas.
+ *  this class plays is the "Builder" for the "Director" class WordRecognizer.
+ */
+
+class BerrySethi {
+
+  /*
+  def isStar(n: Name): boolean = {
+    TreeInfo.isNameOfStarPattern(n);
+  }
+  */
+    /*
+
+            String s = n.toString();
+            return (s.indexOf("$") != -1)
+                  &&(!s.startsWith("nest"));
+      }
+    */
+
+  var labels: HashSet = _;
+
+  var pos: int = _;
+  // maps a literal pattern to an Integer ( the position )
+  // is not *really* needed (postfix order determines position!)
+  var posMap: HashMap = _;    // pos:    Patterns   -> Positions
+  // don't let this fool you, only labelAt is a real, surjective mapping
+  var labelAt: HashMap= _; // chi:    Positions -> Obj
+
+  var globalFirst: TreeSet= _;
+
+  // results which hold all info for the NondetWordAutomaton
+
+  var follow: HashMap= _;    // follow: Positions -> Set[Positions]
+
+
+  // Unit test ?
+  def nullable(pat: Tree): Boolean =
+    //System.out.print("<nullable>");
+    //DEBUG.print( pat );
+    //System.out.println("</nullable>");
+    pat match {
+      case Apply(_, _)          => false;
+      case Sequence( trees )    => trees.isEmpty || (trees forall {nullable});
+      case Star(t)              => true; // ? new
+      case Bind(n, t)           => nullable( t );
+      case Alternative(choices) => choices exists {nullable}
+      case _                    => false;
+    }
+
+
+
+  /** returns true if a Sequence pattern matches the empty sequence
+   *  @param pat the sequence pattern.
+  def nullableSequence(pat: Tree): Boolean =
+    pat match {
+      case Sequence(pats) => pats forall {nullable};
+    }
+    }
+   */
+
+  /** returns true if a sequence of patterns (usually children of a
+   *  sequence or subsequence node) is nullable.
+   *  @param pats the sequence of patterns
+  def nullable(pats: Array[Tree]): Boolean = {
+    var result = true;
+    var i = 0;
+    while(i < pats.length && result){
+      result = result && nullable( pats( i ) );
+      i = i + 1
+    }
+    return result;
+  }
+   */
+
+  /** computes first( alpha ) where alpha is a word regexp
+   */
+
+  def compFirst( pat:Tree  ): TreeSet = {
+    //System.out.print("<compFirst>");
+    //DEBUG.print( pat );
+            //System.out.println("</compFirst>");
+    pat match {
+      case Sequence( trees ) =>
+        return compFirst( trees );
+      case Typed(_,_) |  Select(_,_) | Apply(_, _) =>
+        val tmp = new TreeSet();
+        tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set
+        return tmp;
+
+      case Literal( _ ) =>
+        val tmp = new TreeSet();
+        tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set
+        return tmp;
+		  //case Subsequence( Tree[] trees ) =>
+                  //return compFirst( trees );
+      case Alternative( trees ) =>
+        val tmp = new TreeSet();
+        var i = 0;
+        while(i < trees.length) {
+          tmp.addAll( compFirst( trees( i ) ));
+          i = i + 1
+        }
+        return tmp;
+
+      case Bind(_, tree) =>
+        return compFirst(tree);
+
+      case Ident(  name ) =>
+        //if (name != Name.fromString("_"))
+        //    error("unexpected pattern");
+        val tmp = new TreeSet();
+        tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set
+        return tmp;
+
+      case _ =>
+        scala.Predef.error("unexpected pattern");
+    }
+  }
+
+
+
+  /** computes last( alpha ) where alpha is a word regexp
+   */
+  def compLast(pat: Tree): TreeSet = {
+    //System.out.print("<last>");
+    //DEBUG.print( pat );
+    //System.out.println("</compLast>");
+    pat match {
+      case Sequence( _ ) | Apply(_, _) =>
+        val tmp = new TreeSet();
+        tmp.add(posMap.get( pat ).asInstanceOf[Integer]); // singleton set
+        return tmp;
+
+      case Literal( _ ) =>
+        val tmp = new TreeSet();
+        tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set
+        return tmp;
+
+      case Alternative( trees ) =>
+        val tmp = new TreeSet();
+        var i = 0;
+        while(i < trees.length) {
+          tmp.addAll( compLast( trees ));
+          i = i + 1
+        }
+        return tmp;
+
+      case Bind( _, tree ) =>
+        return compLast( tree );
+
+      case _ =>
+        scala.Predef.error("unexpected pattern");
+    }
+  }
+
+
+  /** computes first(w) where w=alpha_1...alpha_n  are successors of a
+   *  sequence node
+   * @todo make tail recursive
+   */
+  def compFirst( pats:scala.List[Tree]  ): TreeSet = pats match {
+    case List() => new TreeSet();
+    case x::xs  =>
+      val res = compFirst(x);
+      if(nullable(x))
+        res.addAll(compFirst(xs));
+      res
+  }
+
+  // Unit test ?
+
+  /** computes last(w) where w are successors of a sequence node
+   */
+  def compLast(pats: scala.List[Tree]): TreeSet = pats match {
+    case List() => new TreeSet();
+
+    case _ =>
+    /*
+     System.out.print("<last>");
+     for( int k = 0; k<pats.length; k++) {
+     DEBUG.print( pats[k] );
+     System.out.print("  ");
+     }
+     System.out.println();
+     */
+
+      var i = pats.length - 1;
+      var tmp = pats( i );
+      val result = compLast( tmp );
+      i = i - 1;
+      while( nullable(tmp) && (i >= 0 )) {
+        tmp = pats( i );
+        result.addAll( compLast( tmp ));
+        i = i + 1;
+      }
+    return result;
+  }
+
+  // starts from the right-to-left
+  // precondition: pos is final
+  //               pats are successor patterns of a Sequence node
+  // returns first-set (== follow set of initial state)
+  def compFollow(pats: scala.List[Tree]): TreeSet = {
+    var first:TreeSet  = null;
+    this.recVars = new HashMap();
+    var fol = new TreeSet();
+    if( pats.length > 0 ) {//non-empty expr
+      var i = pats.length;
+      fol.add( new Integer( pos )); // don't modify pos !
+      do {
+        i = i - 1;
+        first = compFollow1( fol, pats( i ) );
+        if( nullable( pats( i ) ))
+          fol.addAll( first );
+        else
+          fol = first;
+        //System.out.println("in compFollow: first"+first);
+        //System.out.println("in compFollow: fol"+fol);
+
+      } while( i > 0 );
+    }
+    this.follow.put(new Integer( 0 ), fol);
+    return fol;
+  }
+
+  var recVars: HashMap = _;
+
+  /** returns the first set of an expression, setting the follow set along
+   *  the way
+   */
+  def compFollow1( fol1:TreeSet , pat:Tree  ): TreeSet = {
+    var fol = fol1;
+    //System.out.println("compFollow1("+fol+","+pat+")");
+    pat match {
+      case Sequence( trees ) =>
+        var first: TreeSet = null;
+        var i = trees.length;
+        if( i > 0 ) { // is nonempty
+          do {
+            i = i - 1;
+            first = compFollow1(fol, trees( i ));
+            if( nullable( trees( i ) ))
+              fol.addAll( first );
+            else
+              fol = first;
+          } while( i > 0 ) ;
+        }
+      if( null == first ) first = new TreeSet();
+      return first;
+
+      case Alternative( choices ) =>
+        val first = new TreeSet();
+      var  i = choices.length - 1;
+      while(i >= 0) {
+        first.addAll( compFollow1( fol, choices( i ) ));
+        i = i - 1;
+      }
+      return first;
+
+      case Star(t) =>
+
+        val first = compFirst( t );
+        fol.addAll(first);
+        compFollow1(fol,t);
+
+      case Bind( n, t ) =>  // == can also be star
+
+        val first = compFirst( t );
+                  //System.out.print("BIND" + first);
+      //recVars.put( pat.symbol, first );
+
+      // if( appearsRightmost( n, t ))
+      // follow = oldfollw + ownfirst
+
+      //if( isStar( n ) )
+      //  fol.addAll( first ); // an iterated pattern
+
+      // continue to compute follow sets with adjusted fol
+      return compFollow1( fol, t );
+
+      case Ident(  n ) =>
+        if ((pat.symbol != null )
+            && pat.symbol.isPrimaryConstructor) {
+              // same as Apply
+              val pos = this.posMap.get( pat ).asInstanceOf[Integer];
+              val tset = fol.clone().asInstanceOf[TreeSet];
+              this.follow.put( pos, tset );
+              val first = new TreeSet();
+              first.add( pos );
+              return first;
+            }
+      /*
+      if ( recVars.keySet().contains( pat.symbol )) { // grammar
+        val first = recVars.get( pat.symbol ).asInstanceOf[TreeSet];
+        val follow = fol.clone().asInstanceOf[TreeSet];
+        first.addAll( follow );
+        //recVars.put//this.follow.put( pat.symbol, follow );
+        return first;
+      }
+      */
+      // --- --- only happens when called from BindingBerrySethi
+      // [... x ...] changed to [... x@_ ...]
+
+      // non-generated, non-recursive variable should not appear,
+      // so this is a wildcard pattern _
+
+      val pos = this.posMap.get( pat ).asInstanceOf[Integer];
+      val tset = fol.clone().asInstanceOf[TreeSet];
+      this.follow.put( pos, tset );
+      val first = new TreeSet();
+      first.add( pos );
+      //System.out.println("Ident("+n+",...) first:"+first);
+      //System.out.println("Ident("+n+",...) follow:"+tset);
+      return first;
+
+      case Apply(_, _) | Literal( _ ) | Typed(_,_) | Select(_,_) =>
+        val pos = this.posMap.get( pat ).asInstanceOf[Integer];
+        val tset = fol.clone().asInstanceOf[TreeSet];
+        this.follow.put( pos, tset );
+        val first = new TreeSet();
+        first.add( pos );
+        return first;
+
+      case _ =>
+        scala.Predef.error("unexpected pattern: "+pat.getClass());
+    }
+  }
+
+  /** called at the leaves of the regexp
+   */
+  def seenLabel( pat:Tree , i:Integer , label:Label  ): Unit = {
+    this.posMap.put( pat, i );
+    this.labelAt.put( i, label );
+    if( label != DefaultLabel() ) {
+      /*
+       if( this.labels.contains( label ) ) {
+       switch(label) {
+       case TreeLabel(Apply(_, Tree[] args)) =>
+       if( args.length > 0 ) {
+       unit.warning(pat.pos, "if this pattern in nondeterminism, it will not compile correctly");
+       }
+       }
+       }
+       */
+      this.labels.add( label );
+    }
+
+  }
+
+  /** overriden in BindingBerrySethi
+   */
+  def seenLabel( pat:Tree ,  label:Label ): Unit = {
+    seenLabel( pat, new Integer( {pos = pos + 1; pos} ), label );
+  }
+
+  /** returns "Sethi-length" of a pattern, creating the set of position
+   *  along the way
+   */
+
+  var activeBinders:Vector = _;
+
+  // todo: replace global variable pos with acc
+  def traverse( pat:Tree  ): Unit = {
+    pat match {
+
+      // (is tree automaton stuff, more than Berry-Sethi)
+      case Apply( _, _ ) | Typed( _, _ )| Select( _, _ ) =>
+        val label = new TreeLabel( pat );
+        seenLabel( pat, label ) ;
+        return ;
+
+      case p @ Literal( _ ) =>
+        val label = new SimpleLabel( p );
+        seenLabel( pat, label ) ;
+
+        return ;
+
+      case Sequence( trees ) =>
+        var i = 0;
+        while(i < trees.length) {
+          traverse( trees( i ) );
+          i = i + 1
+        }
+      return ;
+
+      case Alternative( trees ) =>
+        var i = 0;
+        while(i < trees.length) {
+          traverse( trees( i ) );
+          i = i + 1
+        }
+        return ;
+
+      case Bind( name,  body) =>
+        //recVars.put( pat.symbol, java.lang.Boolean.TRUE );
+        //if( !isStar( name ) ) {
+          activeBinders.add( pat.symbol );
+          traverse( body );
+          activeBinders.remove( pat.symbol );
+        //}
+        //else
+        //
+      case Star(body) => traverse( body );
+
+      case Ident(name) =>
+        if ((pat.symbol != null )
+            && pat.symbol.isPrimaryConstructor) {
+              // same as Apply
+              val label = new TreeLabel( pat );
+              seenLabel( pat, label ) ;
+
+              return ;
+            }
+
+      scala.Predef.error("should not get here"); //  removed idents?
+      //if( null != recVars.get( pat.symbol ) ) {
+      //  return ;
+      //}
+      // _ and variable x ( == x @ _ )
+      val label = DefaultLabel();
+      seenLabel( pat, label );
+
+      return ;
+
+    }
+  }
+
+
+  var finals: TreeMap  = _;      // final states
+
+  //TreeSet initialsRev;      // final states
+
+  var deltaq:Array[HashMap] = _;    // delta
+
+
+
+  var  defaultq: Array[Vector] = _;  // default transitions
+
+
+  //HashMap deltaqRev[];    // delta of Rev
+  //Vector  defaultqRev[];  // default transitions of Rev
+
+
+   def makeTransition(srcI:Integer, destI:Integer, label: Label): Unit = {
+    var src  = srcI.intValue() ;
+    var dest = destI.intValue() ;
+    var  arrows: Vector = _; //, revArrows;
+    //Label revLabel = new Pair( srcI, label );
+    label match {
+      case DefaultLabel() =>
+        arrows = defaultq( src );
+      //revArrows = defaultqRev[ dest ];
+      case _ =>
+        arrows = deltaq( src ).get( label ).asInstanceOf[Vector];
+        if( arrows == null )
+          deltaq( src ).put( label,
+                            {arrows = new Vector(); arrows} );
+      /*
+       revArrows = (Vector) deltaqRev[ dest ].get( revLabel );
+       if( revArrows == null )
+       deltaqRev[ dest ].put( revLabel,
+       revArrows = new Vector() );
+       */
+    }
+    arrows.add( destI );
+    //revArrows.add( srcI );
+  }
+
+
+  var         initials: TreeSet = _;
+  //NondetWordAutom revNfa ;
+
+  def initialize( subexpr:List[Tree]  ): Unit = {
+    this.posMap = new HashMap();
+    this.labelAt = new HashMap();
+
+
+    this.follow = new HashMap();
+    this.labels = new HashSet();
+    this.recVars = new HashMap();
+    this.pos = 0;
+    // determine "Sethi-length" of the regexp
+    activeBinders = new Vector();
+    val  it = subexpr.elements;
+    while(it.hasNext )
+      traverse( it.next );
+
+
+    this.initials = new TreeSet();
+    initials.add( new Integer( 0 ));
+
+  }
+
+   def initializeAutom(): Unit = {
+
+    finals   = new TreeMap();        // final states
+    deltaq   = new Array[HashMap]( pos );   // delta
+    defaultq = new Array[Vector]( pos );    // default transitions
+
+    var  j = 0;
+    while(j < pos) {
+      deltaq( j ) = new HashMap();
+      defaultq( j ) = new Vector();
+      j = j + 1;
+    }
+  }
+
+  def collectTransitions(): Unit = {                 // make transitions
+    var  j = 0;
+    while(j < pos) {
+      val q = new Integer( j );
+
+      //System.out.print( "--q="+q );
+      //System.out.println(" labelAt:"+labelAt.get( q ));
+
+      val fol = this.follow.get( q ).asInstanceOf[TreeSet];
+      //assert fol != null;
+      val it = fol.iterator();
+      while(it.hasNext()) {
+        val p = it.next().asInstanceOf[Integer];
+        //System.out.println( "--  -- p="+p );
+        if( p.intValue() == pos ) {
+          finals.put( q, finalTag );
+        } else {
+          makeTransition( new Integer(j), p,
+                         labelAt.get( p ).asInstanceOf[Label]);
+        }
+      }
+      j = j + 1
+    }
+  }
+
+  var finalTag: Integer = _;
+
+  def automatonFrom(pat: Tree , finalTag: Integer):  NondetWordAutom = {
+
+    this.finalTag = finalTag;
+
+    //System.out.println( "enter automatonFrom("+pat+","+finalTag+")"); // UNIT TEST
+    //System.out.println( pat );
+    //System.out.println( nullableSequence( pat )); // UNIT TEST
+    pat match {
+      case Sequence( subexpr ) =>
+        initialize( subexpr );
+
+
+      // (1) compute first
+
+      //globalFirst = compFirst( subexpr );
+      //System.out.println(globalFirst);
+
+      // (2) compute follow;
+     pos = pos + 1;
+      //Set ignore = compFollow( subexpr );
+      //System.out.println(ignore);
+      //System.exit(0);
+      //assert (ignore.equals( globalFirst ));
+
+      globalFirst = compFollow( subexpr );
+
+      //System.out.print("someFirst:");debugPrint(someFirst);
+
+      // construct the automaton's explicit representation
+
+      initializeAutom();
+
+
+      // defaultqRev = new Vector[pos];  // default transitions
+
+      collectTransitions();
+
+      if (subexpr forall {nullable}) // initial state is final
+	finals.put(new Integer(0), finalTag);
+
+      //TreeSet initials = new TreeSet();
+      //initials.add(new Integer(0));
+
+      val result =
+        new NondetWordAutom(pos, // = nstates
+                            labels,
+                            initials,
+                            finals,
+                            deltaq,
+                            defaultq,
+                            null/*(Object) qbinders*/);
+
+      /*
+       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);
+      //result.print();
+      return result;
+    }
+
+    scala.Predef.error("expected a sequence pattern");
+  }
+
+  def print1(): Unit = {
+    Console.println("after sethi-style processing");
+    Console.println("#positions:" + pos);
+    Console.println("posMap:");
+
+    var it = this.posMap.keySet().iterator();
+    while(it.hasNext()) {
+      val t = it.next().asInstanceOf[Tree];
+      t match {
+        case Literal( _ ) =>
+          Console.print( "(" + t.toString() + " -> ");
+          val s2 = (posMap.get(t).asInstanceOf[Integer]).toString();
+          Console.print( s2 +") ");
+        }
+      }
+      Console.println("\nfollow: ");
+    var  j = 1;
+    while(j < pos ) {
+      val fol = this.follow.get(new Integer(j)).asInstanceOf[TreeSet];
+      Console.print("("+j+" -> "+fol.toString()+") ");
+      //debugPrint( fol );
+      Console.println;
+      j = j + 1;
+    }
+
+  }
+} // class BerrySethi
+
+//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.
+ */
+
+class BindingBerrySethi extends BerrySethi {
+
+  // variables
+
+  var deltaqRev  : Array[HashMap] = _; // delta of Rev
+  var defaultqRev: Array[Vector] = _;  // default transitions of Rev
+  var qbinders   : Array[Vector] = _;  // transitions <-> variables
+  var revnfa     : NondetWordAutom = _ ;
+  var varAt      : HashMap = _;   // chi:    Positions -> Vars (Symbol)
+
+  override def makeTransition(srcI: Integer, destI: Integer, label: Label): Unit = {
+    val src  = srcI.intValue() ;
+    val dest = destI.intValue() ;
+    var arrows: Vector = _;
+    var revArrows: Vector = _;
+    val revLabel = new LPair(srcI, label);
+    label match {
+      case DefaultLabel() =>
+        arrows = defaultq(src);
+        revArrows = defaultqRev(dest);
+
+      case _ =>
+        arrows = deltaq(src).get(label).asInstanceOf[Vector];
+        if (arrows == null)
+          deltaq(src).put(label,
+                            {arrows = new Vector(); arrows} );
+        revArrows = deltaqRev(dest).get(revLabel).asInstanceOf[Vector];
+      if (revArrows == null)
+        deltaqRev(dest).put(revLabel, {revArrows = new Vector(); revArrows} );
+    }
+    arrows.add(destI);
+    revArrows.add(srcI);
+  }
+
+  override def seenLabel(pat: Tree, label: Label): Unit = {
+    var i = new Integer({pos = pos + 1; pos} );
+    seenLabel( pat, i, label );
+    pat match {
+      case Apply(_, _) | Literal( _ ) | Select(_, _) | Typed(_,_) =>
+        this.varAt.put( i, activeBinders.clone() ); // below @ ?
+
+      case Ident( name ) =>
+        //assert ( pat.symbol() == Global.instance.definitions.PATTERN_WILDCARD )||( name.toString().indexOf("$") > -1 ) : "found variable label "+name;
+
+        val binders = activeBinders.clone().asInstanceOf[Vector];
+      /*
+       if( pat.symbol() != Global.instance.definitions.PATTERN_WILDCARD) {
+       binders.add( pat.symbol() );
+       }
+       */
+        this.varAt.put( i, binders );
+    }
+  }
+
+   override def initialize( pats:List[Tree]  ): Unit = {
+    this.varAt = new HashMap(); // Xperiment
+    super.initialize( pats );
+  }
+
+   override def initializeAutom(): Unit = {
+    super.initializeAutom();
+    deltaqRev = new Array[HashMap](pos);   // deltaRev
+    defaultqRev = new Array[Vector](pos);  // default transitions
+    qbinders = new Array[Vector](pos);    // transitions <-> variables
+
+    var  j = 0;
+    while (j < pos) {
+      deltaqRev(j) = new HashMap();
+      defaultqRev(j) = new Vector();
+      qbinders(j) = varAt.get(new Integer(j)).asInstanceOf[Vector];
+      j = j + 1;
+    }
+    varAt.clear(); // clean up
+  }
+
+
+  override def automatonFrom(pat: Tree, finalTag: Integer): NondetWordAutom = {
+    this.finalTag = finalTag ;
+    //System.out.println("enter automatonFrom("+ pat +")");
+    pat match {
+      case Sequence(subexpr) =>
+
+        initialize(subexpr);
+
+        // (1) compute first + follow;
+       pos = pos + 1;
+
+        globalFirst = compFollow( subexpr );
+
+
+
+      initializeAutom();   // explicit representation
+
+      collectTransitions();
+
+      val result =
+        new NondetWordAutom(pos, // = nstates
+                            labels,
+                            initials,
+                            finals,
+                            deltaq,
+                            defaultq,
+                            qbinders);
+
+      result.leftTrans = true;
+
+      val 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(); ) {
+
+       }
+       */
+      val revFinals = new TreeMap();
+      var it = initials.iterator();
+      while(it.hasNext()) {
+        revFinals.put(it.next(), finalTag);
+      }
+      revnfa = new NondetWordAutom(pos,
+                                   labels,
+                                   revInitials,
+                                   revFinals,
+				   deltaqRev,
+				   defaultqRev,
+                                   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();
+    }
+  }
+
+} // class BindingBerrySethi
+
+
+
+}
diff --git a/sources/scala/tools/nsc/matching/DetWordAutoms.scala b/sources/scala/tools/nsc/matching/DetWordAutoms.scala
new file mode 100644
index 0000000000..7870458a44
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/DetWordAutoms.scala
@@ -0,0 +1,884 @@
+/* NSC -- new scala compiler
+ * Copyright 2005 LAMP/EPFL
+ * @author buraq
+ */
+// $Id$
+package scala.tools.nsc.matching ;
+
+import java.util._ ;
+
+trait DetWordAutoms: TransMatcher  {
+
+import global._;
+class DetWordAutom  {
+
+    /** determinization -- standard algorithm considering only
+     *                    reachable states
+     */
+    def this(nfa: NondetWordAutom) = {
+      this();
+      //Console.println("DWA:this(.)");
+      //Console.println(nfa.nstates);
+      //nfa.print();
+      determinize( nfa );
+      //Console.println(_nstates);
+    }
+
+  //final static Integer FINTAG = new Integer(0);
+
+  /** number of states */
+  var _nstates:int =0;
+
+  /** the 'alphabet' */
+  var _labels:HashSet = _;
+
+  /** the set of final states, here as a TreeMap */
+  /*protected*/ var finals:TreeMap = _;
+
+  /** dfa: HashMap trans: Object -> Integer
+   *  nfa: HashMap trans: Object -> Vector [ Integer ]
+   *
+   *  nfa: Integer  ->(Object -> Vector [ Int ])
+   *       [q]     |->( a |-> { q' | (q,a,q') in \deltaright } )
+   *
+   *  dfa: Integer  ->(Object -> Int)
+   *       [q]     |->( a |-> q' | \deltaright(q,a) = q' } )
+   */
+
+  var _deltaq: Array[HashMap] = _;
+
+  var _defaultq: Array[Integer] = _; // this gives the default transitions
+
+  //protected HashMap deltaq[];
+
+  // --- accessor methods
+
+  /** returns number of states
+   */
+  def nstates(): Int = _nstates;
+
+  /** returns the labels
+   */
+  def labels():  HashSet = _labels;
+
+  /** returns the transitions
+   */
+  def deltaq( state:int  ): HashMap =  _deltaq( state );
+
+  /** returns the transitions
+   */
+  def deltaq( state:Integer  ): HashMap =  _deltaq( state.intValue() );
+
+  /** for a set of nfa states (that must exist), returns its transitions
+   */
+  def deltaq(nset: TreeSet):  HashMap =
+    deltaq( indexMap.get( nset ).asInstanceOf[Integer] );
+
+  /** for a set of nfa states (that must exist), returns its transitions
+   */
+   def defaultq( nset:TreeSet  ):  Integer =
+     defaultq( indexMap.get( nset ).asInstanceOf[Integer] );
+
+  /** returns the transitions
+   */
+  def  defaultq( state: int  ): Integer =
+    _defaultq( state );
+
+  /** returns the transitions
+   */
+  def defaultq( state: Integer  ): Integer =
+    _defaultq( state.intValue() );
+
+  /** returns true if the state is final
+   */
+  def isFinal(state: int): boolean =
+    ((finals != null)
+     && (finals.get( new Integer( state )) != null));
+
+  /** returns true if the state is final
+   */
+  def  isFinal(state: Integer):  boolean = {
+    return ((finals != null) && finals.containsKey( state ));
+  }
+
+  /** returns true if the state is final
+   */
+  def finalTag( state:Integer  ):  Integer = {
+    return finals.get( state ).asInstanceOf[Integer];
+  }
+
+
+  def  finalTag( state: int  ): Integer = {
+    return finals.get( new Integer (state )).asInstanceOf[Integer];
+  }
+
+  /** returns true if the set of states contains at least one final state
+   */
+  def containsFinal( Q: TreeSet  ): boolean = {
+    val it = Q.iterator();
+    while(it.hasNext()) {
+      if( isFinal(it.next().asInstanceOf[Integer]))
+	return true;
+    }
+    return false;
+  }
+
+
+  /** returns true if there are no finite states
+   */
+  def isEmpty():  boolean = {
+    return finals.isEmpty();
+  }
+
+  // END stuff from FiniteAutom
+
+   final val FIRST: int  = 0;
+   final val LAST: int   = FIRST + 1;
+
+  //static final int WHICH_LONGEST_MATCH = FIRST ;
+   final val WHICH_LONGEST_MATCH:int  = LAST ;
+
+  // inherited from FiniteAutom:
+
+  // int nstates;   // number of states
+  // HashSet labels;// the alphabet
+  // TreeMap finals;
+
+  // HashMap deltaq[];
+  //Integer defaultq[];
+
+
+  // TEMPORARY VAR used only during determinization and debug printing
+  // Q -> (Label -> Q )
+  var  delta: HashMap = _;
+  // Q -> Integer;
+  var indexMap: HashMap = _;
+
+  // Integer -> Q
+  var invIndexMap: HashMap = _;
+
+    // only not null if this is a right-transducer
+  var qbinders: Array[Vector] = _;
+
+  final val NODEFAULT:  Integer = new Integer( -1 );
+
+  def isSink( i:int ):  boolean = {
+    return  ( _deltaq( i ).keySet().isEmpty()
+	     && (_defaultq != null )
+	     && (_defaultq( i ).intValue() == i) );
+  }
+
+  def hasDefault( i:int  ):  boolean = {
+    return _defaultq( i ) != NODEFAULT;
+  }
+
+  def determinize( nfa: NondetWordAutom  ): Unit = {
+    //Console.println("DetWordAutom:determinize");
+    //System.out.println("nfa:");nfa.print();
+    var states:TreeSet = _; // temp: Set[Set[Integer]]
+    var deftrans:HashMap = _; // Set[Integer] -> Int
+
+    var trans: HashMap = _; // always points to a mapping ( Label -> Q )
+    var ix = 0;    // state index
+
+    this._labels = nfa.labels;
+    ////System.out.println("Labels: "+labels);
+    this.delta = new HashMap();
+    //this.dead = -1;
+
+    states = new TreeSet( new StateSetComparator() );
+    deftrans = new HashMap();
+    // temporarily: Map[Set[Integer]] later: Map[Integer]
+    this.finals = new TreeMap( new StateSetComparator() );
+    this.invIndexMap = new HashMap();
+    this.indexMap = new HashMap();
+
+    // new initial state (singleton set { q0 } by construction)
+    val q0 = new TreeSet();
+    q0.addAll( nfa.initials ); /*new Integer( 0 )); */
+    states.add( q0 );
+
+    val empty = new TreeSet();
+    deftrans.put( q0, empty );
+    states.add( empty );
+    deftrans.put( empty, empty );
+
+    val rest = new Stack();
+    if( nfa.isFinal( 0 ) )
+      this.finals.put( q0, nfa.finalTag( 0 ) );
+
+    //Console.println("...beginning");
+
+    rest.push( empty );
+    rest.push( q0 );
+    //Console.println("...beginning 2" );
+    while( !rest.empty() ) {
+      //Console.println("...beginning 3" );
+      val P1 = rest.pop().asInstanceOf[TreeSet];
+
+      //System.out.println("states:"+ states);
+      //System.out.println("P1:"+ P1);
+
+      invIndexMap.put( new Integer( ix ), P1 );
+      indexMap.put( P1, new Integer( ix ));
+      ix = ix + 1;
+      delta.put( P1, {trans = new HashMap(); trans});
+
+      //Console.println("...beginning 4" );
+      // labelled transitions
+      val  it = _labels.iterator();
+      //Console.println("it = "+it );
+      //Console.println(it.hasNext());
+
+      while( it.hasNext() ) {
+        //Console.println("...beginning 5" );
+        //Console.flush;
+	val label = it.next();
+	//Console.print( "Label: " + label +" ");
+	// Qdest will contain all states reachable via `label'
+	// from some nfa state in P1;
+	val Qdest = nfa.getSide( P1, label );
+	//Console.println("Qdest:"+Qdest);
+	if( !states.contains( Qdest ) ) {
+	  states.add( Qdest );
+	  ////System.out.print(" (added)" );
+	  rest.push( Qdest );
+	  ////System.out.print(" (pushed)");
+
+        //Console.println("nfa.containsFinal("+Qdest+") =="+nfa.containsFinal( Qdest ));
+
+	  if( nfa.containsFinal( Qdest ) )
+	    this.finals.put( Qdest, nfa.finalTag( Qdest ));
+	  ////System.out.print(" (added final)");
+
+	}
+	////System.out.println(".Qdest");
+
+	trans.put( label, Qdest );
+	// //System.out.println( "Qdest: " + Qdest);
+        //Console.println("Y marks");
+      }
+
+      // default transitions
+
+      val defTarget: TreeSet = nfa.defaultq( P1 ).asInstanceOf[TreeSet];
+      //System.out.println("defTarget:"+defTarget);
+      deftrans.put( P1, defTarget );
+
+      //Console.println("X marks 0");
+
+      if( !states.contains( defTarget ) ) {
+        //Console.println("X marks 1");
+
+	states.add( defTarget );
+	rest.push( defTarget );
+        //Console.println("nfa.containsFinal("+defTarget+")"+nfa.containsFinal( defTarget ));
+	if( nfa.containsFinal( defTarget ) )
+	  this.finals.put( defTarget, nfa.finalTag( defTarget ));
+      }
+
+      //Console.println("X marks");
+    }
+
+    //Console.println("...continuing");
+
+    // <DEBUG>
+    //printBefore( states, deftrans );
+
+    // </DEBUG> do not call printBefore after this point
+    // //System.out.println("indexMap: "+indexMap);
+
+    this._nstates = states.size();
+    _deltaq = new Array[HashMap]( _nstates );
+    _defaultq = new Array[Integer]( _nstates );
+
+    // we replace Set[Set[Integer]] by its index and clean up
+
+    val jt = states.iterator();
+    while(jt.hasNext()) {
+      val state   = jt.next().asInstanceOf[TreeSet];
+      val state_x = indexMap.get( state ).asInstanceOf[Integer];
+
+      val defTarget  = deftrans.get( state ).asInstanceOf[TreeSet];
+      var defTarget_x: Integer  = _;
+      if(  null != defTarget) {
+	defTarget_x = indexMap.get( defTarget ).asInstanceOf[Integer];
+	////System.out.println("deftarget" + defTarget);
+      } else
+	defTarget_x = NODEFAULT;
+
+      ////System.out.print(state.toString() + " --> " + state_x);
+      //System.out.println(" deftarget " + defTarget + " --> "+defTarget_x);
+
+      trans = delta.get( state ).asInstanceOf[HashMap];
+      val newTrans = new HashMap();
+      val labs = _labels.iterator();
+      while(labs.hasNext()) {
+	val label = labs.next();
+	val target   = trans.get( label ).asInstanceOf[TreeSet];
+	var target_x: Integer = _;
+	if( null != target  ) {
+	  // //System.out.println("target :"+target);
+	  target_x = indexMap.get( target ).asInstanceOf[Integer];
+
+	  if( target_x.intValue() != defTarget_x.intValue() ) {
+	    // replace target by target_x
+	    // (use type-unawareness)
+	    newTrans.put( label, target_x );
+	  }
+	  trans.remove( label );
+	}
+
+      }
+      _deltaq( state_x.intValue() ) = newTrans;
+      _defaultq( state_x.intValue() ) = defTarget_x;
+
+      delta.remove( state );
+      deftrans.remove( state );
+
+    }
+    //Console.println("determinize::: finals"+finals);
+    val oldfin: TreeMap = finals;
+    this.finals = new TreeMap();
+    var kt = oldfin.keySet().iterator();
+    while(kt.hasNext()) {
+      val state = kt.next().asInstanceOf[TreeSet];
+      val state_x = indexMap.get( state ).asInstanceOf[Integer];;
+      this.finals.put( state_x, oldfin.get( state ) ); // conserve tags
+    }
+
+    // clean up, delete temporary stuff
+    /*
+     // we cannot clean up, indexmap is needed later
+     for( Iterator it = states.iterator(); it.hasNext(); ) {
+     ((TreeSet) it.next()).clear();
+     }
+     */
+    states.clear();
+
+      //Console.println("...done");
+    //minimize();
+  }
+
+
+
+  def isDead(state: Int): Boolean = {
+    return state == _nstates - 1; // by construction
+  }
+
+  def isDead(state: Integer): Boolean = {
+    return state.intValue() == _nstates - 1; // by construction
+  }
+
+
+  /** returns target of the transition from state i with label label.
+   *  null if no such transition exists.
+   */
+  def delta(i: Int, label: Label): Integer = {
+    var target:Integer =_;
+    label match {
+    case DefaultLabel() =>
+      if (! hasDefault(i))
+        return null;
+        return _defaultq( i ).asInstanceOf[Integer] ;
+    case SimpleLabel( _ ) | TreeLabel( _ ) =>
+      return _deltaq( i ).get( label ).asInstanceOf[Integer] ;
+    /*case LPair( Integer state, Label lab ):
+      return state;
+     */
+    case _ =>
+      scala.Predef.error("whut's this: label="+label+", class "+label.getClass());
+    }
+  }
+
+  def delta(i: Integer, label: Label): Integer =
+    delta(i.intValue(), label);
+
+  /** should maybe in nfa, not here
+   */
+  /*static  */
+  protected def smallestFinal( nfa: NondetWordAutom, states:TreeSet  ): Integer = {
+
+    var min = Integer.MAX_VALUE ;
+    val it = states.iterator();
+    while (it.hasNext()) {
+      val state = it.next().asInstanceOf[Integer];
+      if( nfa.isFinal( state ) && (state.intValue() < min ))
+	min = state.intValue();
+    }
+    if (min == Integer.MAX_VALUE)
+      scala.Predef.error("I expected a final set of states");
+    return new Integer( min );
+  }
+
+  protected def allSetsThatContain( ndstate: Integer  ): Vector = {
+    val v = new Vector();
+    val it = indexMap.keySet().iterator();
+    while(it.hasNext()) {
+      val ndstateSet = it.next().asInstanceOf[TreeSet];
+      if( ndstateSet.contains( ndstate ))
+	v.add( ndstateSet );
+    }
+    return v;
+  }
+
+
+  protected def filterItOutQuoi( dLeft: DetWordAutom, npTarget: Npair,lab:LPair , nsrc:TreeMap ):Unit = {
+    val theLabel  = lab.lab;
+    val ntarget = lab.state;
+
+    // e.g.[2,(3),4] --> 7
+    val dstate = dLeft.indexMap.get( npTarget.nset ).asInstanceOf[Integer];
+
+    // eg. 3 -> [3] [2,3]
+    val targets:Vector = dLeft.allSetsThatContain( ntarget );
+
+    ////System.out.println( targets+", of these " ) ;
+
+    // filter out those source states which arrive here...
+    val su = targets.iterator();
+    while(su.hasNext()) {
+      val nset   = su.next().asInstanceOf[TreeSet];
+      val ddelta = dLeft.deltaq( nset ).asInstanceOf[HashMap];
+
+      // ...  at THIS dstate
+      if(ddelta.get( theLabel ).asInstanceOf[Integer] == dstate ) {
+
+	val np1 = new Npair( ntarget, nset );
+
+	////System.out.print( np1.toString( dLeft.indexMap ));
+
+	if( WHICH_LONGEST_MATCH == FIRST )
+	  addTransitionFLM( nsrc, np1 );
+	else
+	  addTransitionLLM( nsrc, np1 );
+      }
+
+    }
+  }
+
+  /** all default transitions from sets that contain nq to npTarget
+   */
+  protected def filterItOutQuoiDefault( dLeft: DetWordAutom ,npTarget:Npair , nq:Integer , nsrc:TreeMap  ): Unit = {
+
+
+    ////System.out.println( "npTarget = " + npTarget ) ;
+
+    val allSources = dLeft.allSetsThatContain( npTarget.nstate );
+    val it = allSources.iterator();
+    while(it.hasNext()) {
+
+      // e.g.[2,(3),4] --> 7
+      //Integer dstate = (Integer) dLeft.indexMap.get( npTarget.nset );
+
+      val dstate = dLeft.indexMap.get( it.next() ).asInstanceOf[Integer];
+
+      //System.out.println( "dstate = " + dstate ) ;
+
+      //assert dstate != null;
+
+      // eg. 3 -> [3] [2,3]
+      val targets = dLeft.allSetsThatContain( nq );
+
+      //System.out.println( "targets: " + targets ) ;
+
+      // filter out those source states which arrive here...
+      val su = targets.iterator();
+      while(su.hasNext()) {
+	val nset = su.next().asInstanceOf[TreeSet];
+	val ddef = dLeft.defaultq( nset );
+
+	//System.out.println( "ddef ="+ddef );
+
+	// ...  at THIS dstate
+	if( ddef == dstate ) {
+
+	  val np1 = new Npair( nq, nset );
+
+	  // print target
+	  //System.out.print( np1.toString( dLeft.indexMap ));
+
+	  if( WHICH_LONGEST_MATCH == FIRST )
+	    addTransitionFLM( nsrc, np1 );
+	  else
+	    addTransitionLLM( nsrc, np1 );
+
+	}
+
+      }
+    }
+  }
+
+  /** this implements the first longest match policy
+   */
+  protected def addTransitionFLM( nsrc:TreeMap , np:Npair  ): Unit= {
+    val np2 = nsrc.get( np.nset ).asInstanceOf[Npair ];
+
+    // (policy) first longest match
+    if(( np2 == null )
+       ||( np2.nstate.intValue() > np.nstate.intValue())) {
+	 nsrc.put( np.nset, np  );
+       }
+
+  }
+
+  /** this implements the last longest match policy (!)
+   */
+  protected def addTransitionLLM(nsrc: TreeMap,  np: Npair ): Unit = {
+    val np2 = nsrc.get( np.nset ).asInstanceOf[Npair];
+
+    // (policy) first longest match
+    if(( np2 == null )
+       ||( np2.nstate.intValue() < np.nstate.intValue())) {
+	 nsrc.put( np.nset, np  );
+       }
+
+  }
+
+
+  /** build a deterministic right to left transducer from the args
+   */
+  def this(right: NondetWordAutom, left:NondetWordAutom, dLeft: DetWordAutom ) = {
+    this();
+
+    /* System.out.println("DetWordAutom.<init>(nfa,nfa,dfa)");
+     System.out.println("nfa-left:");left.print();
+     System.out.println("nfa-right:");right.print();
+     System.out.println("dLeft:"+dLeft.print());
+     System.out.println("dLeft.finals"+dLeft.finals);
+     */
+    this.indexMap = dLeft.indexMap;
+    this.invIndexMap = dLeft.invIndexMap;
+    // fix indexMap
+    /* // unnecessary
+     TreeSet q0 = new TreeSet();
+     q0.add( new Integer( 0 ));
+     indexMap.put( q0, new Integer( 0 ));
+     //System.out.println("check out the indexMap!" + indexMap);
+     */
+
+    val visited_n = new TreeSet( new NpairComparator() );
+    val rest    = new Stack();
+
+    // right is "nearly deterministic"
+    // we can follow reverse traces paths by using dLeft.indexMap
+
+    // start with right.initials, left.final, dLeft.final
+    val it = dLeft.finals.keySet().iterator();
+    while(it.hasNext()) {
+      val fstate = it.next().asInstanceOf[Integer];
+      val nfstate = invIndexMap.get( fstate ).asInstanceOf[TreeSet];
+      //System.out.print( "final state:"+fstate);
+      //System.out.print( " correspond to set of states:"+ nfstate );
+
+      val min_ndstate: Integer = smallestFinal( left, nfstate );
+
+      val npair:Npair = new Npair( min_ndstate, nfstate );
+
+      //System.out.println( "  smallest final of these: "+ min_ndstate );
+
+
+      //System.out.println( "push final nfa state "+npair.toString( dLeft.indexMap ));
+
+      if( !visited_n.contains( npair )) {
+	visited_n.add( npair );
+	rest.push( npair );
+      }
+    }
+
+    val ratLab     = new HashMap(); // maps nset to label,HashMap
+    val ratDelta   = new HashMap(); // maps nset to Vector[ NP ]targets
+
+    val ratDefault = new HashMap(); // maps nset to NP (one target)
+
+    var ix = 1;
+    val ix_initial = rest.clone().asInstanceOf[Stack];
+    var ix_final = new TreeSet( new NpairComparator() );;
+
+    val newIndexMap = new TreeMap( new NpairComparator() );
+
+    while( !rest.isEmpty() ) {
+
+      val npair = rest.pop().asInstanceOf[Npair];
+      newIndexMap.put( npair, new Integer(ix));
+
+      ratDelta.put( npair, new Vector() );
+
+      if( npair.nset.contains( new Integer( 0 )) ) {
+	ix_final.add( npair );
+      }
+      ix = ix + 1;
+
+      //System.out.println(" popped "+npair.toString( dLeft.indexMap ));
+
+      ////System.out.print(" binders: ");
+      ////System.out.print( right.qbinders[ npair.nstate.intValue() ] );
+
+      val delta = right.deltaq( npair.nstate );
+
+      ////System.out.print(" we could have arrived : ");
+      //search the delta for target invIndexMap
+
+      val labelToNset = new HashMap();
+      val labelToFrom = new HashMap();
+
+      // maps nsets to the active nstates
+      var nsrc = new TreeMap( new StateSetComparator() );
+
+      // berry-sethi construction assures that
+      //   there is only one label for outgoing transitions
+      var theLabel:Label = null;
+
+      // collect all transition possible in the DFA
+      val jt = delta.keySet().iterator();
+      while(jt.hasNext()) {
+	val lab = jt.next().asInstanceOf[LPair];
+
+	// lab.state is the target in the NFA
+
+	if( null == theLabel ) {
+	  ratLab.put( npair, lab.lab );
+	  ////System.out.print(" with \""+lab.lab+"\" ");
+	}
+	theLabel = lab.lab ;
+
+	////System.out.print("\nfrom n" + lab.state +"  ... ");
+
+	// these are too many, filter out those that exist in DFA
+
+	filterItOutQuoi( dLeft, npair, lab, nsrc );
+
+      }
+
+
+      ////System.out.println( "---" );
+
+      ////System.out.println("all sources: ");
+
+      // !!  first longest match
+      val ut = nsrc.keySet().iterator();
+      while(ut.hasNext()) {
+	val nset  = ut.next().asInstanceOf[TreeSet];
+	val np2: Npair = nsrc.get( nset ).asInstanceOf[Npair] ;
+
+	//assert( np2 != null );
+	////System.out.println("target: n"+npair.nstate+" via: "+theLabel+" from "+ np2.toString( dLeft.indexMap ));// nset:"+nset+ " namely state n"+ dest);
+
+	val v = ratDelta.get( npair ).asInstanceOf[Vector];
+
+	v.add( np2 );
+
+	if( !visited_n.contains( np2 ) ) {
+
+	  visited_n.add( np2 );
+	  rest.push( np2 );
+	}
+
+      }
+
+      //System.out.println("default sources: ");
+
+      // maps nsets to the active nstates
+      nsrc = new TreeMap( new StateSetComparator() );
+
+      // now for all default transitions that arrive at this nfa state
+      val defqs = right.defaultq( npair.nstate );
+      val kt = defqs.iterator();
+      while( kt.hasNext() ) {
+	val nq = kt.next().asInstanceOf[Integer];
+	//System.out.println("checking nq="+nq);
+	filterItOutQuoiDefault( dLeft, npair, nq, nsrc );
+	//System.out.println( "nsrc after "+nq+" is "+nsrc );
+      }
+
+      //System.out.println( "defqs :"+defqs );
+      //System.out.println( "nsrc :"+nsrc );
+      var nut = nsrc.keySet().iterator();
+      while(nut.hasNext()) {
+
+	val np2 = nsrc.get( nut.next() ).asInstanceOf[Npair];
+
+	var v = ratDefault.get( npair ).asInstanceOf[Vector] ;
+	if( v == null )
+	  ratDefault.put( npair, {v = new Vector(); v} );
+	v.add( np2 );
+
+	if( !visited_n.contains( np2 ) ) {
+
+	  visited_n.add( np2 );
+	  rest.push( np2 );
+	}
+
+      }
+
+      ////System.out.println("zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz");
+
+    }
+
+    // Renumbering
+
+    ////System.out.println( "output: a dfa with "+ix+"states");
+
+    // FIX: empty regular expression (as in "List()") is valid
+    //assert ( !ix_final.isEmpty() ) : "no final states found";
+
+    ////System.out.println( "final state:"+ix_final);
+
+    //System.out.println( "indexMap: " +indexMap);
+      //System.out.println( "newIndexMap: " +newIndexMap);
+    this.finals = new TreeMap();
+    this._nstates = ix;
+    val dratDelta = new Array[HashMap]( ix );
+    qbinders  = new Array[Vector]( ix );
+    _labels = new HashSet();
+    val kit = ratDelta.keySet().iterator();
+    while(kit.hasNext()) {
+      val np = kit.next().asInstanceOf[Npair];
+
+      //System.out.print( "\nstate: "+np);
+      val ndset = np.nset;
+      val dstate = newIndexMap.get( np ).asInstanceOf[Integer];
+      //assert dstate != null : "no dstate for "+np.toString(dLeft.indexMap);
+
+      //System.out.print(" binders:");
+
+      qbinders( dstate.intValue() ) = left.qbinders( np.nstate.intValue() );
+
+      //System.out.print( qbinders[dstate.intValue() ]);
+
+      //System.out.println(" transitions:");
+      if( ix_final.contains( np ) ) {
+	val fin_ix = newIndexMap.get( np ).asInstanceOf[Integer];
+	finals.put( fin_ix, new Integer( 0 ));
+      }
+
+      val lab = ratLab.get( np ).asInstanceOf[Label];
+      val v   = ratDelta.get( np ).asInstanceOf[Vector];
+
+      val ddelta = new HashMap();
+
+      // v might be null if there are only default transitions
+      if( v != null ) {
+        val it2 = v.iterator();
+        while(it2.hasNext()) {
+
+	  val np2= it2.next().asInstanceOf[Npair];
+	  //System.out.print( "("+lab+","+np2+") " );
+	  val ddestR = newIndexMap.get( np2 ).asInstanceOf[Integer];
+	  val ddest = indexMap.get( np2.nset ).asInstanceOf[Integer];
+	  //assert ddest != null :
+	  //"no ddest for "
+	  //+np2.toString(dLeft.indexMap);
+
+	  val newLab = new LPair(ddest, lab);
+	  ddelta.put( newLab, ddestR );
+	  _labels.add( newLab );
+
+	}
+	dratDelta( dstate.intValue() ) = ddelta;
+
+      }
+    }
+    var itt = ratDefault.keySet().iterator();
+    while(itt.hasNext()) {
+      val np  = itt.next().asInstanceOf[Npair];
+      val dstate = newIndexMap.get( np ).asInstanceOf[Integer];
+
+      //System.out.print("\nstate: "+np+" default trans: ");
+
+      val v = ratDefault.get( np ).asInstanceOf[Vector];
+      val ut = v.iterator();
+      while(ut.hasNext()) {
+	val np2  = ut.next().asInstanceOf[Npair];
+	val targetL      = indexMap.get( np2.nset ).asInstanceOf[Integer];;
+	val targetR      = newIndexMap.get( np2 ).asInstanceOf[Integer];;
+
+	val defLab = new LPair( targetL, DefaultLabel() );
+
+	_labels.add( defLab );
+	//System.out.print( "("+defLab+","+np2+") " );
+
+	var d = dratDelta( dstate.intValue() );
+	if( d == null )
+	  dratDelta( dstate.intValue() ) = {d = new HashMap(); d};
+
+	d.put( defLab, targetR );
+      }
+    }
+
+    _deltaq = dratDelta;
+
+    val hmap = new HashMap();
+
+    // final states of left are initial states of right
+    // problem: still need to choose the one
+
+    while( !ix_initial.isEmpty() ) {
+      val np = ix_initial.pop().asInstanceOf[Npair];
+
+      val i          = newIndexMap.get( np ).asInstanceOf[Integer]; //R-state
+      val dtarget    = indexMap.get( np.nset ).asInstanceOf[Integer];// left-d-state
+
+      hmap.put( dtarget, i );
+    }
+    _deltaq( 0 )  = hmap; // careful, this maps Int to Int
+
+    qbinders( 0 ) = new Vector();
+    //((Vector[])defaultq)[ 0 ] = new Vector(); is null
+    //printBeforeRAT( dratDelta );
+
+  }
+
+  def printBeforeRAT1(str: String): Unit = {
+    val tmp = new StringBuffer( str );
+    var j = tmp.length();
+    while(j < 20) {
+      tmp.append(" ");
+      j = j + 1;
+    }
+    Console.println( tmp.toString() );
+  }
+
+  def printBeforeRAT( dratDelta: Array[HashMap] ): Unit = {
+    //System.out.println();
+    printBeforeRAT1( "dratDelta" );
+    printBeforeRAT1( "[index]" );
+    //System.out.println();
+    var  i = 0;
+    while(i < dratDelta.length) {
+      if( isFinal( i ))
+	printBeforeRAT1( "*"+i );
+      else
+	printBeforeRAT1( " "+i );
+
+      //System.out.println( dratDelta[ i ] );
+    i = i + 1
+    }
+  }
+
+  /** you may only call this before the set[set[...]] representation
+   *  gets flattened.
+   */
+  def printBefore(states: TreeSet, deftrans: HashMap): Unit = {
+    var  trans: HashMap = _;
+    Console.println(states);
+    val  it = states.iterator();
+    while (it.hasNext()) {
+      val state = it.next().asInstanceOf[TreeSet];
+      Console.print("state:" + state.toString() + " transitions ");
+      trans = delta.get( state ).asInstanceOf[HashMap];
+      val labs = _labels.iterator();
+      while(labs.hasNext()) {
+	val label = labs.next();
+	val target = trans.get( label ).asInstanceOf[TreeSet];
+	Console.print( "  (" + label.toString()
+		      + "," + target.toString()+")");
+      }
+      Console.print("default trans"+deftrans.get(state));
+      Console.println;
+    }
+    Console.println("final states:" + finals);
+  }
+}
+
+}
diff --git a/sources/scala/tools/nsc/matching/LeftTracers.scala b/sources/scala/tools/nsc/matching/LeftTracers.scala
new file mode 100644
index 0000000000..6d1639952a
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/LeftTracers.scala
@@ -0,0 +1,232 @@
+/* NSC -- new scala compiler
+ * Copyright 2005 LAMP/EPFL
+ * @author buraq
+ */
+// $Id$
+
+package scala.tools.nsc.matching;
+
+import java.util._ ;
+
+import scala.tools.util.Position;
+
+trait LeftTracers: TransMatcher {
+
+import global._;
+
+abstract class LeftTracerInScala extends Autom2Scala {
+
+  val selector: Tree;
+  val elementType: Type;
+
+    /** symbol of the accumulator ( scala.SequenceList )
+     */
+    var accumSym: Symbol   = _;
+    var accumType: Type    = _;
+    var accumTypeArg: Type =_ ;
+
+    def _accumType(elemType: Type): Type =  {
+        SeqTraceType( elemType );
+    }
+
+    protected def initializeSyms(): Unit = {
+      this.funSym =  owner.newLabel( pos, fresh.newName( "left" ));
+
+      this.iterSym = owner.newVariable( pos, fresh.newName( "iter" ))
+      .setInfo( _seqIterType( elementType ) ) ;
+
+      this.stateSym = owner.newVariable( pos, fresh.newName( "q" ))
+      .setInfo( definitions.IntClass.info ) ;
+
+      this.accumType = _accumType( elementType );
+      this.accumTypeArg = accumType.typeArgs( 0 );
+      this.accumSym = owner.newVariable( pos,                  // accumulator
+                                        fresh.newName( "acc" ))
+      .setInfo( accumType );
+
+      //this.funSym
+      //    .setInfo( new MethodType( new Symbol[] {
+      //        accumSym, iterSym, stateSym},
+      //                                   accumType));
+
+      this.funSym.setInfo(
+        new MethodType(
+          scala.List (  // dummy symbol MethodType
+            definitions.IntClass.info,
+            accumType
+          ),
+          accumType)
+      );
+
+      //funSym.newValueParameter( pos, fresh.newName( "q" ))
+      //.setInfo(definitions.IntClass.info),
+      //funSym.newValueParameter( pos, fresh.newName( "acc" ))
+      //.setInfo( accumType ) ),
+      // accumType)); // result type = List[T]
+
+      this.resultSym = owner.newVariable(pos, fresh.newName("trace"))
+      .setInfo( accumType ) ;
+
+      this.curSym = owner.newVariable( pos, "cur" )
+      .setInfo( elementType );
+
+      this.hasnSym = owner.newVariable( pos, nme.hasNext )
+      .setInfo( definitions.BooleanClass.info );
+
+    }
+
+  /* should throw an exception here really, e.g. MatchError
+   */
+  override def code_fail() = Ident( accumSym );
+
+  /** returns translation of transition with label from i.
+     *  returns null if there is no such transition(no translation needed)
+     */
+    override def code_delta(i: Int, label: Label): Tree = {
+      val target = dfa.delta( i, label );
+
+      /*
+       System.out.println("LeftTracer:calling dfa.delta("+i+","+label+")");
+       System.out.println("result: "+target);
+       */
+      if( target == null )
+        null;
+      else {
+        // (optimization) that one is a dead state (does not make sense for tracer)
+        /*
+          if( target == dfa.nstates - 1 )
+          return code_fail();
+        */
+
+        /*
+          Tree newAcc = newSeqTraceCons(new Integer(i),
+          currentElem(),
+          _ref( accumSym ));
+        */
+        val hd = gen.mkNewPair( Literal(i), currentElem() );
+
+        val newAcc = gen.mkNewCons(hd, Ident(accumSym ));
+
+        //return callFun( new Tree[] { newAcc , _iter(), mkIntLit( pos, target )} );
+        callFun( scala.List( Literal(target.intValue() ), newAcc ) );
+      }
+    }
+
+
+  def code_body(): Tree = {
+
+    var body = code_error(); // never reached at runtime.
+
+    // state [ nstates-1 ] is the dead state, so we skip it
+
+    //`if( state == q ) <code_state> else {...}'
+    var i = dfa.nstates() - 2;
+    while (i >= 0) {
+      body = code_state(i, body);
+      i = i - 1;
+    }
+    loadCurrentElem(body);
+  }
+
+    /** return code for state i of the dfa SAME AS IN SUPER, ONLY SINK IS GONE
+     */
+  def code_state(i: Int, elseBody: Tree): Tree = {
+
+    var runFinished: Tree = _; // holds result of the run
+    var finalSwRes: Int = 0;
+
+    runFinished = run_finished(i);
+
+    var stateBody: Tree = _ ; // action(delta) for one particular label/test
+
+    // default action (fail if there is none)
+
+    stateBody = code_delta( i, DefaultLabel());
+
+    if( stateBody == null )
+      stateBody = code_fail();
+    // transitions of state i
+
+    val trans = dfa.deltaq( i );
+    val labs  = dfa.deltaq( i ).keySet().iterator();
+    while(labs.hasNext()) {
+      val label = labs.next();
+      val next = trans.get( label ).asInstanceOf[Integer];
+
+      val  action = code_delta( i, label.asInstanceOf[Label] );
+
+      if( action != null ) {
+        stateBody = If( currentMatches(label.asInstanceOf[Label]),
+                       action,
+                       stateBody);
+      }
+    }
+    stateBody = If(Negate(Ident(hasnSym)),
+                   runFinished,
+                   stateBody );
+    If( Equals( _state(), Literal( i )),
+       stateBody ,
+       elseBody );
+  }
+
+  def  getTrace(): Tree = {
+
+    initializeSyms();
+
+   Block(scala.List(
+      ValDef( iterSym, newIterator( selector )),
+      ValDef( stateSym, Literal( 0 ) ),
+      ValDef( accumSym, gen.mkNil /*mkNil( pos )*/),
+      ValDef( resultSym,
+                 LabelDef( this.funSym,
+                              scala.List (
+                                stateSym,
+                                accumSym
+                              ), code_body() /* code_body_new ? */ ))
+   ),
+         Ident( resultSym ));
+  }
+
+  // calling the AlgebraicMatcher here
+  override def _cur_match(pat: Tree): Tree  = {
+    //return mkBooleanLit(pos, true);
+
+    //System.out.println("calling algebraic matcher on type:" + pat.type);
+
+    val m = new PartialMatcher {
+      val owner = LeftTracerInScala.this.owner;
+      val selector = currentElem();
+
+      // result type definitions.BooleanClass.info );
+    }
+
+    pat match {
+        case Sequence(pats) if containsBinding(pat) =>
+          //scala.Predef.error("should not happen?!");
+          null; // Literal(true); ?!
+      case _ =>
+        am.construct(m, scala.List (
+          CaseDef( pat, Literal( true )),
+          CaseDef( Ident( nme.WILDCARD ), Literal(false)) ),
+                     false);
+      am.toTree();
+    }
+  }
+
+
+  /** return the accumulator + last state
+   */
+  override def run_finished(state: Int): Tree = {
+    val hd = gen.mkNewPair( Literal(state), EmptyTree);
+    //System.err.println(hd.type);
+    gen.mkNewCons(hd, Ident( accumSym ));
+/*
+    mkNewCons(pos,
+                  accumTypeArg,
+                  hd,
+                  Ident( accumSym ));
+*/
+  }
+
+} // TracerInScala
+} // LeftTracers
diff --git a/sources/scala/tools/nsc/matching/MatcherLabels.scala b/sources/scala/tools/nsc/matching/MatcherLabels.scala
new file mode 100644
index 0000000000..55529e61e2
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/MatcherLabels.scala
@@ -0,0 +1,126 @@
+package scala.tools.nsc.matching ;
+
+class MatcherLabels: TransMatcher {
+
+  import global._ ;
+
+  /**
+   * This class represents the label that a transition in an automaton
+   * may carry. These get translated to specific (boolean) tests
+   */
+
+  class Label {
+
+      //case class RLabel(Object rstate, Label lab, Symbol vars[]);
+
+      override def hashCode(): Int = this match {
+        case DefaultLabel() =>
+          return 0;
+        case SimpleLabel(lit) =>
+          return lit.value.hashCode();
+        case TreeLabel(pat) =>
+          // if pat is an  Apply, than this case can only be correctly
+          // handled there are no other similar Applys (nondeterminism)
+          return pat.tpe.hashCode();
+        case TypeLabel(tpe) =>
+          return tpe.hashCode();
+        case _ =>
+          return super.hashCode();
+      }
+
+      override def  equals( o: Any ): Boolean = {
+            if( !(o.isInstanceOf[Label] ))
+              return false;
+        val oL = o.asInstanceOf[Label];
+        //System.out.print(this + " equals " + oL);
+         this match {
+           case DefaultLabel()=>
+           oL match {
+             case DefaultLabel() =>
+               return true;
+             case _ => false;
+           } //
+           case SimpleLabel( lit ) =>
+           oL match {
+             case SimpleLabel( lit2 ) =>
+             return /*(lit.kind == lit2.kind)
+	     && */lit.value.equals( lit2.value );
+             case _ => false;
+           }
+
+           case TreeLabel( pat ) =>
+             oL match {
+               case TreeLabel( pat2 ) =>
+	       pat match {
+		 case Apply( _, _ ) =>
+		   pat2 match {
+		     case Apply( _, _ ) =>
+		       return treeInfo.methPart/*methSymbol?*/( pat )
+                     == treeInfo.methPart/*methSymbol*/( pat2 );
+		   }
+                 case _ => false;
+	       }
+               case _ => false
+             }
+
+           case TypeLabel(tpe) =>
+             oL match {
+               case TypeLabel( tpe2) =>
+                 return tpe.equals(tpe2);
+               case _ => false;
+             }
+           case LPair(state, lab) =>
+             oL match {
+               case LPair(state2, lab2) =>
+                 return  state.equals(state2) && lab.equals(lab2);
+               case _ => false;
+             }
+           case _ => return false;
+         }
+      }
+
+
+  def toString2(): String = {
+    val ext = System.getProperty("extendedMatching");
+    if ((ext != null) && ext.equals("true")) {
+      this match {
+        case DefaultLabel() =>
+          return "<>:p"+p;
+        case SimpleLabel( lit ) =>
+          return lit.toString()+":p"+p;
+        case TreeLabel( pat ) =>
+          return pat.tpe.toString()+":p"+p;
+
+        case _ => scala.Predef.error("this never happens");
+      }
+    }
+    scala.Predef.error("this never happens");
+  }
+
+  override def toString(): String = this match {
+    case DefaultLabel() =>
+      "<>";
+    case SimpleLabel(  lit) =>
+      lit.toString();
+    case TreeLabel(pat) =>
+      pat.toString();
+    case TypeLabel(tpe) =>
+      tpe.toString();
+    case LPair(state, lab) =>
+      "(" + state.toString() + "," + lab.toString() + ")";
+    case _ =>
+      scala.Predef.error("this never happens");
+  }
+
+  val p = -1; // tree state - only needed for extended matching
+
+}
+
+  case class DefaultLabel()                    extends Label;
+  case class SimpleLabel(lit: Literal)         extends Label;
+  case class TreeLabel(pat: Tree)              extends Label; // Apply, Sequence
+  case class TypeLabel(tpe: Type)              extends Label; // Apply, Sequence
+  case class LPair(state: Integer, lab: Label) extends Label;
+
+}
+
diff --git a/sources/scala/tools/nsc/matching/NondetWordAutom.scala b/sources/scala/tools/nsc/matching/NondetWordAutom.scala
new file mode 100644
index 0000000000..cd1d8b576e
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/NondetWordAutom.scala
@@ -0,0 +1,522 @@
+package scala.tools.nsc.matching ;
+import java.util._ ;
+
+trait NondetWordAutoms {
+/** a nondeterministic word automaton.
+ *  states are represented (implicitly) as Integer objects.
+ */
+class NondetWordAutom  {
+  // BEGIN stuff from FiniteAutom
+
+  //final static Integer FINTAG = new Integer(0);
+
+  /** number of states */
+  var nstates: int =_;
+
+  /** the 'alphabet' */
+  var labels:  HashSet = _;
+
+  /** the set of final states, here as a TreeMap */
+  var finals: TreeMap = _;
+
+  /** dfa: HashMap trans: Object -> Integer
+   *  nfa: HashMap trans: Object -> Vector [ Integer ]
+   *
+   *  nfa: Integer  ->(Object -> Vector [ Int ])
+   *       [q]     |->( a |-> { q' | (q,a,q') in \deltaright } )
+   *
+   *  dfa: Integer  ->(Object -> Int)
+   *       [q]     |->( a |-> q' | \deltaright(q,a) = q' } )
+   */
+
+  var _deltaq:Array[HashMap] = _;
+
+  var _defaultq:Array[Vector] = _; // this gives the default transitions
+
+  //public HashMap deltaq[];
+
+  // --- accessor methods
+
+  /** returns number of states
+   def nstates():  int = {
+   return nstates;
+   }
+   */
+
+  /** returns the labels
+   def labels():  HashSet = {
+   return _labels;
+   }
+   */
+
+  /** returns the transitions
+   */
+  def deltaq(  state: int ):HashMap = {
+    return _deltaq( state );
+  }
+
+  /** returns the transitions
+   */
+  def deltaq(  state: Integer ): HashMap = {
+    return _deltaq( state.intValue() );
+  }
+
+  /** returns the transitions
+   */
+  def defaultq( state: int  ): Vector = {
+    return _defaultq( state );
+  }
+
+  /** returns the transitions
+   */
+   def defaultq( state:Integer  ): Vector = {
+     return _defaultq( state.intValue() );
+   }
+
+
+  /** returns true if the state is final
+   */
+  def isFinal( state:int  ): boolean = {
+    return ((finals != null)
+            && (finals.get( new Integer( state )) != null));
+  }
+
+  /** returns true if the state is final
+   */
+  def isFinal( state:Integer  ): boolean = {
+    return ((finals != null) && finals.containsKey( state ));
+  }
+
+  /** returns true if the state is final
+   */
+  def finalTag(  state: Integer ):     Integer = {
+    return finals.get( state ).asInstanceOf[Integer];
+  }
+
+
+  def finalTag( state:int  ): Integer = {
+    return finals.get( new Integer (state )).asInstanceOf[Integer];
+  }
+
+  /** returns true if the set of states contains at least one final state
+   */
+  def containsFinal( Q:TreeSet  ): boolean = {
+    var  it = Q.iterator();
+    while(it.hasNext()) {
+      if( isFinal( it.next().asInstanceOf[Integer]))
+        return true;
+    }
+    return false;
+  }
+
+
+  /** returns true if there are no finite states
+   */
+  def isEmpty(): boolean = finals.isEmpty();
+
+  // END stuff from FiniteAutom
+
+
+  // inherited from FiniteAutom
+
+  // set of *distinct* objects that may label transitions
+  // see Object.hashCode() to see why this works
+
+  //HashSet labels;
+  //TreeMap finals;
+
+  var initials: TreeSet = _; // ? need this ?
+  // ---
+
+  // Object deltaq -->
+  // HashMap deltaq[]; // this gives the transitions of q;
+
+  var leftTrans: boolean = _;
+  var rightTrans:    boolean = _;
+
+  /** if true, this automaton behaves as a special left transducer.
+   *  if a run succeeds, the result is not "true" but the entire
+   *  run of the automaton as a sequence of (label,state) - pairs.
+   *  used for binding variables.
+   */
+   def producesRun(): boolean = {
+     return leftTrans;
+   }
+
+    def consumesRun():    boolean = {
+      return rightTrans;
+    }
+
+  def initial( i: Integer  ):      boolean  = {
+    return initials.contains( i );
+  }
+  var qbinders: Array[Vector] = _;
+
+  /** returns all states accessible from Qsrc via label.
+   *  used by class DetWordAutomaton.
+   */
+  def getSide ( Qsrc:TreeSet , label:Object  ): TreeSet = {
+    //Console.println("NWA::getSide(Qsrc="+Qsrc);
+    val Qdest = new TreeSet();
+    var it = Qsrc.iterator();
+    while(it.hasNext())  {// state
+      val q = it.next().asInstanceOf[Integer].intValue();
+      val ps = deltaq( q ).get( label ).asInstanceOf[Vector];
+      //Console.println("deltaq(q) = "+deltaq(q));
+      //Console.println("_deltaq(q) = "+_deltaq(q));
+      //Console.println("ps = "+ps);
+      if( null != ps ) {
+	Qdest.addAll( ps );
+      }
+      //Console.println("defq = "+_defaultq( q ));
+      Qdest.addAll( _defaultq( q ) );
+    }
+    //Console.println("DONE-NWA::getSide");
+    return Qdest;
+  }
+
+  /** returns the transitions
+   */
+  def defaultq( P1: Set  ): Object  = {
+      val defTarget = new TreeSet();
+    var p1 = P1.iterator();
+    while(p1.hasNext()) {
+      val q1 = p1.next().asInstanceOf[Integer].intValue();
+      //System.out.println("   q1:"+q1+ " defa: "+defaultq( q1 ));
+      defTarget.addAll( _defaultq( q1 ) );
+    }
+    return defTarget;
+  }
+
+
+  /** first match policy: among several final states, the smallest one is
+   *   chosen. used by class DetWordAutomaton
+   */
+  def finalTag( Q:Set  ): Integer = {
+
+    var min = Integer.MAX_VALUE ;
+    var it = Q.iterator();
+    while(it.hasNext()) {
+      val state = it.next().asInstanceOf[Integer];
+      val tag = finals.get( state ).asInstanceOf[Integer];
+      if( tag != null ) {
+        if( tag.intValue() < min )
+          min = tag.intValue();
+      }
+    }
+
+    if ( min == Integer.MAX_VALUE )
+      scala.Predef.error( "there should be a final state ");
+
+    return new Integer( min );
+  }
+
+  /*
+   void tmap(int offs, TreeMap t) = {
+   TreeMap nt = new TreeMap();
+   for(Iterator it = t.keySet().iterator(); it.hasNext(); ) = {
+   Integer key = (Integer) it.next();
+   Integer newkey = new Integer( key.intValue() + offs );
+   Integer val = (Integer) t.get( key );
+   Integer newval = new Integer( val.intValue() + offs );
+
+   nt.put( newkey, newval );
+   }
+   return nt;
+   }
+   */
+  // hashmaps, treemaps
+  def mapmap(src:Map, offset:int , dest:Map , mapkeys:boolean , mapvals:boolean ): Map = {
+    var it = src.keySet().iterator();
+    while(it.hasNext()) {
+      var key = it.next();
+      var value = src.get( key );
+      if( mapkeys ) key = new Integer( key.asInstanceOf[Integer].intValue()
+                                      + offset );
+      if( mapvals ) value = vmap( offset, value.asInstanceOf[Vector] ) ;
+      /* new Integer( ((Integer)val).intValue()
+       + offset );
+       */
+      dest.put( key, value );
+    }
+    return dest;
+  }
+
+  def vmap(offs:int , v:Vector  ):  Vector = {
+    if( v == null )
+      return null;
+    var res = new Vector( v.size() );
+    var it = v.iterator();
+    while(it.hasNext()) {
+      val item = it.next().asInstanceOf[Integer];
+      res.add( new Integer( item.intValue() + offs ));
+    }
+    return res;
+
+  }
+
+  /*
+   void relocate_defaultq( int offs, Vector   _defaultq[] ) = {
+   for( int i = 0; i < this.nstates; i++ ) = {
+   _defaultq[ i + offset ] = vmap( offset, ((Vector[])defaultq)[ i ]);
+   }
+   }
+   */
+
+  /** copies the values in the fields of this object into the
+   *  arguments, possibly adding an offset.
+   */
+  def relocate( offset:int, _finals:TreeMap, _deltaq1:Array[HashMap], _defaultq1:Array[Vector], _qbinders1:Array[Vector] ): Unit = {
+
+    mapmap( finals, offset, _finals, true, false);
+    var i = 0;
+    while(i < this.nstates) {
+
+      _deltaq1  ( i + offset ) =
+        mapmap( deltaq( i ), offset, new HashMap(), false, true).asInstanceOf[HashMap];
+
+      _defaultq1( i + offset ) = vmap( offset, this.defaultq( i ) );
+      i = i + 1;
+    }
+    if ((_qbinders1 != null) &&( qbinders != null )) {
+      i = 0;
+      while(i < this.nstates ) {
+        //System.out.println("hallo"+qbinders);
+        //System.out.println("qbinders[ i ] :"+qbinders[ i ]);
+        //assert _qbinders != null;
+        //System.out.println("_qbinders :"+_qbinders);
+
+        _qbinders1( i + offset ) = qbinders( i );
+        i = i + 1
+      }
+    }
+  }
+
+
+  /** if there is more than one initial state, a new initial state
+   *  is created, with index 0
+   */
+  def normalize( initials:TreeSet , reloc:boolean  ): Unit = {
+    //if( initials.size() == 1 )
+    //      return;
+
+    var idelta   = new HashMap();
+    var idefault = new TreeSet();
+
+    var q0 = new Integer( 0 );
+
+    var it = initials.iterator();
+    while(it.hasNext()) {
+
+      val ostate = it.next().asInstanceOf[Integer];
+
+      val finTag = finals.get( ostate ).asInstanceOf[Integer] ;
+      if(( finTag != null ) && ( finals.get( q0 )  == null))
+        finals.put( q0, finTag );
+
+
+      var tmp = deltaq( ostate );
+
+      if( reloc )
+        tmp = mapmap( tmp, 1, new HashMap(), false, true ).asInstanceOf[HashMap];
+
+      val labs = tmp.keySet().iterator();
+      while(labs.hasNext()) {
+        val lab     = labs.next();
+        var itarget = idelta.get( lab ).asInstanceOf[Vector];
+        if( null == itarget )
+          idelta.put( lab, {itarget = new Vector(); itarget});
+        val otarget = tmp.get( lab ).asInstanceOf[Vector];
+        itarget.addAll( otarget );
+      }
+      //System.out.println( "normalize:defaultq[ "+ostate+" ] "+((Vector[]) defaultq) [ ostate.intValue() ]);
+      if( defaultq( ostate ) != null )
+        idefault.addAll( defaultq( ostate )  );
+    }
+
+    if( reloc ) {
+      val m = 1 + this.nstates;
+      val _finals    = new TreeMap();
+      val _deltaq    = new Array[HashMap]( m );
+      val _defaultq = new Array[Vector]( m );
+      var _qbinders: Array[Vector] = null;
+
+      if( qbinders != null )
+        _qbinders = new Array[Vector]( m );
+
+      relocate( 1, _finals, _deltaq, _defaultq, _qbinders );
+
+      this.nstates  = m;
+      this.finals   = _finals;
+      this._deltaq   = _deltaq;
+      this._defaultq = _defaultq;
+      this.qbinders = _qbinders;
+    }
+
+    this._deltaq  ( 0 ) = idelta;
+    //System.out.println("normalize:deltaq[ 0 ]"+ idelta );
+    this._defaultq( 0 ) = new Vector( idefault );
+
+    //System.out.println("normalize:defaultq[ 0 ]"+ idefault );
+
+    this.initials = new TreeSet();
+    this.initials.add( q0 );
+  }
+
+
+      /** called from Berry-Sethi construction.
+       */
+
+       def this(nstates:int, _labels:HashSet, initials: TreeSet, finals:TreeMap, deltaq:Array[HashMap], defaultq:Array[Vector], qbinders:Object ) = {
+         this();
+         //Console.println("NWA::this(. . . . )");
+         this.nstates = nstates;
+         this.labels = _labels;
+         this.initials = initials;
+         this.finals = finals;
+         this._deltaq = deltaq;
+         this._defaultq = defaultq;
+         this.qbinders = qbinders.asInstanceOf[Array[Vector]];
+         //print();
+         //System.exit(0);
+       }
+
+
+
+  var offset:Array[int] = _; // only used if constructed from multiple
+
+  def collectLabels( nfa:Array[NondetWordAutom ] ): Unit = {
+    this.labels = new HashSet();
+    var i = 0;
+    while(i < nfa.length) {
+      this.labels.addAll( nfa( i ).labels );
+      i = i + 1
+    }
+  }
+
+  def collectOffsets( nfa:Array[NondetWordAutom] ): Unit = {
+    this.offset = new Array[int]( nfa.length + 1 );
+    offset( 0 ) = 1; // we have a new initial state
+    var i = 0;
+    while(i < nfa.length ) {
+      offset( i + 1 ) = nfa( i ).nstates + offset( i );
+      i = i + 1
+    }
+  }
+
+  /** collapses several normalized NondetWordAutom objects into one.
+   */
+
+  def this( nfa: Array[NondetWordAutom] ) = {
+    this();
+    //Console.println("NWA::this(.)");
+
+    //this.m
+    val m = nfa.length;
+    //System.out.println("enter NondetWordSwitch, "
+    //                   +"combining " + m + " automata");
+
+    collectLabels( nfa );
+    collectOffsets( nfa );
+
+    //Console.println(" X 1");
+
+
+    this.nstates = offset( nfa.length ); //m - 1 ] + nfa[ m - 1 ].nstates;
+
+
+    this.finals = new TreeMap();
+
+    this.qbinders = new Array[Vector]( nstates );
+
+    // new initial state gets all transitions from all initial states
+
+    this._deltaq        = new Array[HashMap]( nstates );
+    this._defaultq      = new Array[Vector]( nstates );
+    //Console.println(" X 2");
+
+    //TreeSet defaultqSet = new TreeSet();
+    _deltaq( 0 ) = new HashMap(); // 0 = our new initial state
+
+    val initials = new TreeSet();
+
+    var i = 0;
+    while(i < m) {
+      //System.out.println("i (current NFA):"+i);
+
+      val n = nfa( i );
+
+      val offs = offset( i );
+
+      initials.add( new Integer( offs ));
+
+      n.relocate( offs,
+                 this.finals,
+                 this._deltaq,
+                 this._defaultq,
+                 this.qbinders );
+      i = i + 1;
+    }
+
+    normalize( initials, false );
+    //Console.println("Leave-NWA::this(.)");
+  }
+
+
+
+
+  def print(): Unit = {
+
+    Console.print("NFA on labels "+ this.labels);
+
+    if( offset != null ) {
+      Console.print("offset");
+      var k = 0;
+      while(k < offset.length) {
+        if( k > 0)
+          Console.print(", ");
+        Console.print(offset(k));
+        k = k + 1;
+      }
+    }
+    Console.println;
+
+    Console.print("max state number :" + (nstates - 1)  );
+
+    Console.println("initials" + initials);
+
+    Console.println("finals" + finals);
+
+    var i = 0;
+    while(i < nstates) {
+      Console.print("state: " + i);
+      if( finals.containsKey( new Integer( i )) ){
+        Console.print("*"); //final
+      }
+      Console.print("  transitions: {");
+      var arrows:HashMap  = deltaq( i );
+
+      var it = arrows.keySet().iterator();
+      while(it.hasNext()) {
+        val label = it.next();
+        val targets = arrows.get( label ).asInstanceOf[Vector];
+        val jt = targets.iterator();
+        while(jt.hasNext()) {
+          val p = jt.next().asInstanceOf[Integer];
+          Console.print("("+label+","+p+")");
+        }
+      }
+
+      Console.print("} ");
+      Console.print(" default transitions: "+_defaultq( i ));
+      if( null != qbinders )
+        Console.println(" binders "+qbinders( i ));
+      Console.println;
+      i = i + 1;
+    }
+  }
+
+
+}
+
+}
diff --git a/sources/scala/tools/nsc/matching/Npair.scala b/sources/scala/tools/nsc/matching/Npair.scala
new file mode 100644
index 0000000000..8cb050de2e
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/Npair.scala
@@ -0,0 +1,64 @@
+/* NSC -- new scala compiler
+ * Copyright 2005 LAMP/EPFL
+ * @author buraq
+ */
+// $Id$
+package scala.tools.nsc.matching ;
+
+import java.util.{ HashMap, TreeSet };
+/** cartesian
+ */
+
+/** Int x TreeSet[ Int ]
+ */
+case class Npair(nstate: Integer, nset: TreeSet) {
+
+  override def equals(that: Any): Boolean = {
+    this match {
+      case Npair(nstate, nset) =>
+	that match {
+	  case Npair(_nstate, _nset) =>
+	    return ((nstate == _nstate)
+		    && (nset == _nset));
+          case _ => return false
+	}
+      case _ => return false
+    }
+  }
+
+  override def toString(): String = this match {
+    case Npair(nstate, nset) =>
+      //Integer dstate = (Integer) indexMap.get(nset);
+      "<n" + nstate.toString() + " in " + nset /*+" = d"+dstate*/ + ">";
+    case _ => null
+  }
+
+ def toString(indexMap: HashMap):  String = {
+    //assert indexMap != null;
+    this match {
+      case Npair(nstate, nset) =>
+      //assert nstate != null;
+      val dstate = indexMap.get( nset ).asInstanceOf[Integer];
+      return "<n" + nstate.toString() + " in " + nset + " = d" + dstate + ">";
+      case _ =>
+        return null;
+    }
+  }
+
+
+}
+
+class NpairComparator extends StateSetComparator {
+  override def compare(o1: Any, o2: Any): Int = {
+    o1 match {
+      case Npair(nstate, nset) => o2 match {
+	case Npair(_nstate, _nset) =>
+	  val res = nstate.compareTo(_nstate);
+          if (res != 0)
+	    return res;
+	  else
+	    return super.compare(nset, _nset);
+      }
+    }
+  }
+}
diff --git a/sources/scala/tools/nsc/matching/RightTracers.scala b/sources/scala/tools/nsc/matching/RightTracers.scala
new file mode 100644
index 0000000000..cc3285d282
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/RightTracers.scala
@@ -0,0 +1,539 @@
+/* NSC -- new scala compiler
+ * Copyright 2005 LAMP/EPFL
+ * @author buraq
+ */
+// $Id$
+
+package scala.tools.nsc.matching;
+
+import java.util._ ;
+
+import scala.tools.util.Position;
+import scala.tools.nsc.symtab.Flags;
+
+trait RightTracers: TransMatcher {
+
+  import global._ ;
+  import java.util._ ;
+
+//import Scope.SymbolIterator;
+
+//import scalac.util.Name ;
+//import scalac.util.Names ;
+
+//import scala.tools.util.Position;
+
+  /** translate right tracer to code
+     * @param dfa determinized left tracer
+     * @param left nondeterm. left tracer (only needed for variables!)
+     * @param pat  ?
+     * @param elementType ...
+     */
+abstract class RightTracerInScala  extends Autom2Scala {
+
+  val seqVars: Set;
+  val pat:Tree;
+  val elementType: Type;
+
+
+  def SeqTrace_headElem( arg: Tree  ) = { // REMOVE SeqTrace
+    val t = Apply(Select(arg, definitions.List_head), Nil);
+    Apply(Select(t, definitions.tupleField(2,2)),Nil)
+  }
+
+  def SeqTrace_headState( arg: Tree  ) = { // REMOVE SeqTrace
+    val t = Apply(Select(arg, definitions.List_head), Nil);
+    Apply(Select(t, definitions.tupleField(2,1)), Nil)
+  }
+
+  def SeqTrace_tail( arg: Tree ): Tree =  // REMOVE SeqTrace
+    Apply(Select(arg, definitions.List_tail), Nil);
+
+  final def collectVars(pat: Tree): HashSet = {
+    var vars = new HashSet();
+
+    def handleVariableSymbol(sym: Symbol): Unit  = {
+      vars.add( sym );
+    }
+    def isVariableName(name: Name): Boolean =
+      ( name != nme.WILDCARD ) && ( treeInfo.isVariableName( name ) ) ;
+
+    def isVariableSymbol(sym: Symbol): Boolean = {
+      ( sym != null )&&( !sym.isPrimaryConstructor );
+    }
+
+    def traverse(tree: Tree): Unit = {
+      tree match {
+        case x @ Ident(name)=>
+          if(x.symbol != definitions.PatternWildcard)
+            scala.Predef.error("shouldn't happen?!");
+
+        case Star(t) =>
+          traverse(t);
+        case Bind(name, subtree) =>
+          var sym: Symbol = _;
+          if( isVariableName( name )
+             && isVariableSymbol( {sym = tree.symbol; tree.symbol} ))
+            handleVariableSymbol( sym );
+
+          traverse( subtree );
+
+        case Select(_,_) => ;
+
+        // congruence cases
+        case Apply(fun, args) => args foreach {traverse};
+        case Sequence(trees)  => trees foreach {traverse};
+        case Typed(expr, tpe) => traverse(expr); // needed??
+        case _ : Alternative | _ : Select | _ : Literal =>  ; // no variables
+        case _ => Predef.error("unknown node:"+tree+" = "+tree.getClass());
+      }
+    }
+    traverse( pat );
+    return vars;
+  }
+
+  //final def defs = cf.defs;
+
+  val allVars: Set = collectVars( pat );
+
+  var varsToExport: Set = new HashSet(); // @todo HANDLE seqVars THESE GLOBALLY INSTEAD OF LOCALLY
+
+  varsToExport.addAll( allVars );
+  varsToExport.removeAll( seqVars );
+
+  var targetSym:Symbol = _;
+
+  var helpMap  = new HashMap();
+  var helpMap2 = new HashMap();
+  var helpVarDefs:scala.List[Tree] = Nil;
+
+  val it = seqVars.iterator();
+  while(it.hasNext()) {
+    makeHelpVar( it.next().asInstanceOf[Symbol] );
+  }
+
+  val jt = allVars.iterator();
+  while(jt.hasNext()) {
+    val varSym = jt.next().asInstanceOf[Symbol];
+    if(( varSym.name.toString().indexOf("$") == -1 )
+       && ( !seqVars.contains( varSym ))) {
+         makeHelpVar( varSym, true );
+       }
+  }
+
+  //System.out.println("allVars: "+allVars);
+  //System.out.println("seqVars: "+seqVars);
+  //System.out.println("helpVarDefs now: "+helpVarDefs);
+
+  initializeSyms();
+
+  def makeHelpVar(realVar: Symbol): Unit = {
+    makeHelpVar( realVar, false );
+  }
+
+  /** makes a helpvar and puts mapping into helpMap, ValDef into helpVarDefs
+   */
+
+  def makeHelpVar(realVar: Symbol, keepType: Boolean): Unit = {
+    val helpVar = owner.newVariable( pos,
+                                    fresh.newName( realVar.name
+                                                  .toString()+"RTIS" ));
+    var rhs: Tree = _;
+
+    //System.out.println("RTiS making helpvar : "+realVar+" -> "+helpVar);
+
+    if( keepType ) {
+      helpVar.setInfo( realVar.tpe );
+      rhs = EmptyTree;
+    } else {
+      helpVar.setInfo( definitions.ListClass.info /* LIST_TYPE(elementType)*/ );
+      rhs = gen.mkNil;
+    }
+
+    helpMap.put( realVar, helpVar );
+    helpVar.setFlag(Flags.MUTABLE);
+    val varDef = ValDef( helpVar, rhs );
+    //((ValDef) varDef).kind = Kinds.VAR;
+    helpVarDefs= varDef :: helpVarDefs;
+
+  }
+
+  def prependToHelpVar(realVar: Symbol, elem:Tree): Tree = {
+    val hv = refHelpVar( realVar );
+    Assign( hv, gen.mkNewCons( /*elementType, */elem, hv ));
+    /*
+     return cf.Block(pos,
+     new Tree [] {
+     cf.debugPrintRuntime( "ASSIGN" ),
+     gen.Assign( hv, cf.newSeqCons( elem, hv ))
+     }, defs.UNIT_TYPE());
+     */
+  }
+
+  protected def initializeSyms(): Unit = {
+
+    this.funSym = owner.newLabel( pos, fresh.newName( "right" ));
+
+    this.iterSym = owner.newVariable( pos, fresh.newName("iter"))
+    .setInfo( SeqTraceType( elementType ));
+
+    this.stateSym = owner.newVariable ( pos, fresh.newName("q"))
+    .setInfo( definitions.IntClass.info ) ;
+
+    this.curSym = owner.newVariable( pos, fresh.newName("cur"))
+    .setInfo( elementType ) ;
+
+    this.targetSym = owner.newVariable( pos, fresh.newName("p"))
+    .setInfo( definitions.IntClass.info ) ;
+
+    funSym.setInfo(
+      new MethodType( scala.List (  // dummy symbol MethodType
+        SeqTraceType(elementType),
+        //funSym.newValueParameter( pos, fresh.newName("iter") /*, SeqTraceType elementType */),
+        definitions.IntClass.info),
+      //funSym.newValueParameter( pos, fresh.newName( "q" ) /*, definitions.IntClass.info */),
+                     definitions.UnitClass.info)) // result
+
+  }
+
+  // load current elem and trace
+  override def loadCurrentElem(body: Tree): Tree = {
+    If( isEmpty( _iter() ),
+       run_finished( 0 ),            // we are done
+       Block( scala.List (
+         ValDef( this.targetSym,
+                SeqTrace_headState( Ident( iterSym))),
+         ValDef( this.curSym,
+                SeqTrace_headElem( Ident( iterSym )))),
+             body )
+     );
+  }
+
+  /** see code_state0_NEW
+   */
+  def code_state0(elseBody: Tree) = { // careful, map Int to Int
+
+    If( Equals( _state(), Literal(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
+   */
+  def code_state0_NEW(): Tree =  { // careful, map Int to Int
+
+    val hmap = dfa.deltaq( 0 ); // all the initial states
+
+    var i = 0;
+    val n = hmap.keySet().size(); // all transitions defined
+
+    val tmapTag = new TreeMap();
+    val  tmapBody = new TreeMap();
+    var  it = hmap.keySet().iterator();
+    while(it.hasNext()) {
+      val  targetL = it.next().asInstanceOf[Integer];
+      val targetR  = hmap.get( targetL ).asInstanceOf[Integer];
+
+      val I = new Integer( i );
+      tmapTag.put( targetL, I );
+      tmapBody.put( I, callFun( scala.List (
+        SeqTrace_tail( _iter() ),
+        Literal( targetR.intValue() ) )));
+      i = i + 1;
+    }
+    //i = 0;
+
+    var ncases: scala.List[CaseDef] = Nil;
+    //val tags    = new Array[Int]( n );
+    //val targets = new Array[Tree]( n );
+    var jt = tmapTag.keySet().iterator();
+    while(jt.hasNext()) {
+      val tagI = jt.next().asInstanceOf[Integer];
+      //tags( i )    = tagI.intValue();
+      val I    = tmapTag.get( tagI ).asInstanceOf[Integer];
+      //targets( i ) = tmapBody.get( I ).asInstanceOf[Tree];;
+      ncases = CaseDef( Literal(tagI.intValue()),
+                       tmapBody.get(I).asInstanceOf[Tree] ) :: ncases;
+      //i = i + 1
+    }
+    //gen.Switch( gen.Ident( pos, targetSym ),
+    //           tags,
+    //           targets,
+    //           code_error()/*cannot happen*/ );
+
+    Match(Ident(targetSym), ncases);
+  }
+
+  override def currentMatches(label: Label): Tree = label match {
+    case LPair( target, theLab ) =>
+      Equals( Literal(target.intValue() ), current() );
+    case _ =>
+      scala.Predef.error("expected Pair label");
+  }
+
+
+  override def code_state_NEW(i: Int): Tree = { // precondition i != 0
+    var stateBody = code_delta( i, DefaultLabel() );
+    if( stateBody == null ) {
+      stateBody = code_error();
+    }
+    val trans = dfa.deltaq( i );
+    val tmapTag = new TreeMap();
+    val tmapBody = new TreeMap();
+    var  j = 0;
+    var  labs = dfa.labels().iterator();
+    while(labs.hasNext())  {
+      val label  = labs.next();
+      val next   = trans.get( label ).asInstanceOf[Integer];
+      val action = code_delta( i, label.asInstanceOf[Label] );
+
+      if( action != null ) {
+        val J = new Integer( j );
+        tmapTag.put( label.asInstanceOf[LPair].state, J );
+        tmapBody.put( J, action );
+
+        stateBody = If( currentMatches( label.asInstanceOf[Label] ),
+                       action,
+                       stateBody);
+      }
+      j = j + 1;
+    }
+    val n = tmapTag.keySet().size();
+    //j = 0;
+    //val tags    = new Array[int]( n );
+    //val targets = new Array[Tree]( n );
+    var ncases: scala.List[CaseDef] = Nil;
+    val it = tmapTag.keySet().iterator();
+    while(it.hasNext()) {
+      val tagI     = it.next().asInstanceOf[Integer];
+      //tags( j )    = tagI.intValue();
+      val J        = tmapTag.get( tagI ).asInstanceOf[Integer];
+      //targets( j ) = tmapBody.get( J ).asInstanceOf[Tree];
+      ncases = CaseDef(Literal(tagI.intValue()),
+                       tmapBody.get( J ).asInstanceOf[Tree]) :: ncases;
+      //j = j + 1;
+    }
+    if( n > 0 )
+      //gen.Switch( gen.Ident( pos, targetSym ), tags, targets, code_error() );
+      Match(Ident( targetSym ), ncases);
+    else
+      code_error();
+  }
+
+    // calling the AlgebraicMatcher here
+  override def _cur_match(pat1: Tree): Tree = {
+    var pat = pat1;
+    //System.out.println("RTiS._cur_match("+pat.toString()+")");
+    //System.out.println("calling algebraic matcher on type:"+pat.type);
+
+    //System.err.println( "curT"+currentElem().type().widen() );
+    val m = new PartialMatcher {
+      val owner = RightTracerInScala.this.owner; // , //funSym,//this.funSym,
+      val selector = currentElem(); //,
+      // result type defs.boolean_TYPE() );
+    }
+    val freshenMap = new HashMap(); // sym2exp -> new sym
+    val helpMap3 = new HashMap();         // new sym -> original sym
+
+    // "freshening": never use the same symbol more than once
+    // (in later invocations of _cur_match)
+
+    var it = varsToExport.iterator();
+    while(it.hasNext() ) {
+      val key = it.next().asInstanceOf[Symbol];
+      if( key.name.toString().indexOf("$") == -1 ) {
+        this.helpMap2.put( key, helpMap.get( key ));
+        // "freshening" by appending string ( a bit dangerous )
+        val newSym = key.cloneSymbol( owner /*funSym*/ );
+        newSym.name = newTermName(key.name.toString() + "%") ; // erm
+        freshenMap.put( key, newSym );
+        helpMap3.put( newSym, helpMap.get( key ));
+        //System.out.println( "key: "+ key + " key.owner:"+key.owner());
+        //System.out.println( "newsym owner:"+newSym.owner());
+      } else {
+        freshenMap.put( key, key );
+      }
+    }
+
+    //System.out.println("RightTracerInScala:: -pat :"+pat.toString());
+    /*
+     System.out.println("RightTracerInScala - the seqVars"+seqVars);
+     System.out.println("RightTracerInScala - the varsToExport"+varsToExport);
+     */
+    //System.out.println("RightTracerInScala::freshenMap :"+freshenMap);
+
+    // "freshening"
+
+    //@nsc @todo @todo @todo @todo
+
+    //val tc = new TreeCloner( global, freshenMap, Type.IdMap );
+    //pat = tc.transform( pat );
+    //@nsc   this commented out, is broken anyway.
+
+    // val match  case <pat> =>  <do binding>; true
+    //             case _     => false
+
+
+    var ts: scala.List[Tree] = scala.List(); //new Array[Tree]( helpMap3.keySet().size() );
+    //var j = 0;
+    var jt = helpMap3.keySet().iterator();
+    while(jt.hasNext()) {
+      val vsym = jt.next().asInstanceOf[Symbol];
+      val hv   = helpMap3.get( vsym ).asInstanceOf[Symbol];
+      //hv.setInfo( defs.LIST_TYPE( elementType ) ) ; DEBUG ALARM ?
+      ts = Assign( Ident(hv), Ident(vsym) ) :: ts;
+      //ts( j ) = gen.;
+      //j = j + 1;
+      // System.out.println( "the assign" + res[ j - 1 ] );
+    }
+
+    val theBody =  Block(ts, Literal( true )); // just `true'
+
+    am.construct( m, scala.List(
+      CaseDef( pat, theBody), // freshening
+      // if tree val matches pat -> update vars, return true
+      CaseDef(Ident(definitions.PatternWildcard), Literal(false))),
+                 // else return false
+                 true // do binding please
+               );
+
+    am.toTree();
+  }
+
+  /** returns translation of transition with label from i.
+   *  returns null if there is no such transition(no translation needed)
+   */
+  override def code_delta(i: Int , label: Label  ): Tree = {
+    val hmap    = dfa.deltaq( i );
+    val ntarget =  hmap.get( label ).asInstanceOf[Integer];
+    var algMatchTree: Tree = null;
+    if( ntarget == null )
+      return null;
+
+    //System.out.println("delta("+i+","+label+")" );
+    var  theLab: Label = null;
+    label match {
+      case LPair ( state, lab2 )=>
+        //assert ntarget == state;
+        theLab = lab2;
+      lab2 match {
+        case TreeLabel( pat ) =>
+          algMatchTree = _cur_match( pat );
+        case _ =>
+      }
+      case DefaultLabel() =>
+        scala.Predef.error("bla"); // should not happen
+    }
+    //assert dfa.qbinders != null : "qbinders ?";
+
+    var vars = dfa.qbinders(i);
+
+    //System.out.println("dfa.qbinders[ i ]"+vars);
+
+    if (null == vars) vars = new Vector(); // TODO: make this more consistent
+    //assert vars != null;
+
+    var stms = if (algMatchTree != null ) algMatchTree::Nil else Nil;
+
+    var it = vars.iterator();
+    while(it.hasNext()) {
+      val vble = it.next().asInstanceOf[Symbol];
+      val rhs = gen.Ident( curSym );
+      stms = prependToHelpVar( vble , rhs) :: stms;
+    }
+
+    val value = callFun( scala.List( SeqTrace_tail( _iter() ),
+                                    Literal(ntarget.intValue())));
+
+    Block(stms, value );
+  }
+
+  override def stateWrap(i: Int): Tree = {
+    if (i == 0)
+      code_state0_NEW();
+    else
+      code_state_NEW(i);
+  }
+
+  /* returns statements that do the work of the right-transducer
+   */
+  def getStms(trace: Tree, unit: CompilationUnit, body: Tree): Tree =  {
+
+    var stms: scala.List[Tree] = scala.List();
+    val loopbody = code_body_NEW();
+
+    stms =
+      scala.List(
+        ValDef( iterSym, trace ),
+        ValDef( stateSym, Literal( 0 ))
+      ) ::: helpVarDefs
+        ::: scala.List(
+          LabelDef(
+            this.funSym,
+            scala.List (
+              iterSym,
+              stateSym
+            ),
+            loopbody )
+        );
+
+    // bind variables handled by this righttracer
+    var it = seqVars.iterator();
+    while(it.hasNext())
+      stms = stms ::: bindVar( it.next().asInstanceOf[Symbol] ) :: Nil;
+
+    val treeCloner = new Transformer {
+      override def transform(tree1: Tree): Tree = {
+        val tree = super.transform(tree1);
+        if (tree.hasSymbol) {
+          val symbol = helpMap2.get(tree.symbol);
+          if (symbol != null) tree.setSymbol(symbol.asInstanceOf[Symbol]);
+        }
+        tree;
+      }
+    };
+
+    Block(stms, treeCloner.transform( body ));
+  }
+
+
+  /** return the accumulator. (same as in LeftTracerInScala)
+   *  todo: move tree generation of Unit somewhere else
+   */
+  override def run_finished(state: Int):  Tree = Literal(());
+
+  def   current() = Ident( targetSym );
+
+  def refHelpVar(realVar: Symbol) = {
+    val hv = helpMap.get( realVar ).asInstanceOf[Symbol];
+    //assert hv != null : realVar;
+    Ident(hv);
+  }
+
+  def assignToHelpVar(realVar: Symbol, rhs: Tree): Tree = {
+    val hv = refHelpVar(realVar);
+    Assign(hv, rhs);
+  }
+
+  def bindVar(realVar: Symbol): Tree = {
+    val hv = refHelpVar(realVar);
+    /*
+     System.out.println("binding realVar.name "+realVar.name+" type:"+realVar.type()+" to hv type:"+hv.type());
+     realVar.setOwner( owner );
+     System.out.println("is same as realVar"+realVar.type().isSameAs( elementType ));
+     System.out.println("is same as hv"+realVar.type().isSameAs( hv.type() ));
+     if( realVar.type().isSameAs( elementType ))
+     return gen.ValDef( realVar, SeqList_head( hv ));
+     else
+     return gen.ValDef( realVar, hv );
+     */
+    if( isSameType(realVar.tpe, hv.tpe))
+      ValDef( realVar, hv ); // e.g. x @ _*
+    else {
+      ValDef( realVar, SeqList_head( hv ));
+    }
+  }
+}
+}
diff --git a/sources/scala/tools/nsc/matching/SequenceMatcher.scala b/sources/scala/tools/nsc/matching/SequenceMatcher.scala
new file mode 100644
index 0000000000..dcbd9bc1a5
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/SequenceMatcher.scala
@@ -0,0 +1,173 @@
+/* NSC -- new scala compiler
+ * Copyright 2005 LAMP/EPFL
+ * @author buraq
+ */
+// $Id$
+
+package scala.tools.nsc.matching;
+
+import java.util._ ;
+
+/** 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.
+ */
+
+trait SequenceMatchers: TransMatcher  {
+
+  import global._;
+
+  class SequenceMatcher {
+
+  //  Console.println("CONSTR SEQUENCEMATCHER");
+  final val IGNORED = new Integer(42);
+
+  var _m: PartialMatcher = _;
+
+  var bbuild: BindingBerrySethi  = null;
+
+  /** collects variables
+   * @return all variables bound by this binding nfa
+   */
+  def collectNfaVariables(nfa: NondetWordAutom): Set = {
+    val seqVars = new HashSet();
+    var j = 0;
+    while(j < nfa.nstates) {
+      if( nfa.qbinders( j ) != null )
+        seqVars.addAll( nfa.qbinders( j ) );
+      j = j + 1
+    }
+    seqVars;
+  }
+
+
+  /** translates the det/switching automaton to scala code
+   *  precondition: pat.type() corresponds to element type
+   */
+  def addBinderToBody( pat1:Tree , body:Tree  ): Tree = {
+    if( bbuild == null )
+      bbuild = new BindingBerrySethi;
+
+    val elementType1 = getElemType_Sequence( pat1.tpe );
+
+    // (a) build *binding* nfa (sequential machine)
+    val left =  bbuild.automatonFrom( pat1, IGNORED );
+    val right = bbuild.revnfa;
+
+    //  (b) determinize + translate L
+
+    val dLeft  = new DetWordAutom( left );
+
+    val ltis = new LeftTracerInScala {
+      val dfa =  dLeft;
+      val owner =  _m.owner;
+      val selector = _m.selector;
+      val elementType = elementType1;
+    }
+
+    val trace = ltis.getTrace();
+
+    //  (c) determinize + translate R
+
+    val dRight = new DetWordAutom( right, left, dLeft );
+
+    val seqVars1 = collectNfaVariables( left );
+    //System.out.println("seqVars here are:"+seqVars);
+    val rtis = new RightTracerInScala {
+      val dfa = dRight;
+      val owner = _m.owner;
+      val pat = pat1;
+      val seqVars = seqVars1;
+      val elementType = elementType1;
+    }
+
+    // !!! Tree stms2 = rtis.getStms( theTrace, cunit, body );
+    // !!! gen.mkBlock_( body.pos, trace, stms2 );
+    val stms2 = rtis.getStms( trace, cunit, body );
+    stms2;
+  }
+
+    private def buildNfas( pat:scala.List[Tree]  ): Array[NondetWordAutom] = {
+      val build   = new BerrySethi;
+      val manyNfa = new Array[NondetWordAutom]( pat.length );
+      var i = 0;
+      val it = pat.elements;
+      while( i < pat.length ) {
+        manyNfa( i ) = build.automatonFrom( it.next, new Integer( i ));
+        i = i + 1;
+        //manyNfa[ i ].print();
+      }
+      manyNfa;
+    }
+
+    /** constructs a word recognizer from an array of patterns which
+     *  should all be SequencePatterns ( no wildcard * )
+     *  precondition: pat.type corresponds to element type
+     *  @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
+     *  @param doBinding   flasg that indicates whether variables should be bound
+    */
+  def construct(_m: PartialMatcher,  pat: scala.List[Tree] , body: scala.List[Tree] , defcase1: Tree, doBinding: Boolean  ): Unit = {
+    var defaultCase = defcase1;
+    this._m = _m;
+    //assert body.length == pat.length;
+    if( defaultCase == null )
+      defaultCase = ThrowMatchError( _m.pos );
+
+    val seqType = pat( 0 ).tpe;
+    val elementType1 = getElemType_Sequence( seqType );
+
+    // STEP 1 - build nfas for each pattern
+
+    val manyNfa = buildNfas( pat );
+
+    // STEP 2 - recognizing
+
+    // (a) merge nfas into one if necessary
+    val nfa = if(pat.length > 1)
+      new NondetWordAutom( manyNfa )
+              else
+                manyNfa( 0 );
+
+    //nfa.print();
+
+    // (b) determinize
+    val dfa1 = new DetWordAutom( nfa );
+
+    // (c) translate to scala code
+    val scalaAut =
+      new WordAutomInScala{
+        val dfa = dfa1;
+        val owner = _m.owner;
+        val optim = settings.target == "jvm";
+        val elementType = elementType1;
+      }
+    scalaAut.translate();
+
+    // STEP 3 - binding
+
+    var newbody: scala.List[Tree] = Nil;
+    if( !doBinding )
+      newbody = body;
+    else {  // this is done in the body of the matching case
+      var i = 0;
+      while(i < body.length) {
+        if( !containsBinding( pat( i ) ) )
+          newbody = body( i ) :: newbody; // no need for binding
+        else
+          newbody = addBinderToBody( pat( i ), body( i ) ) :: newbody;
+        i = i + 1;
+      }
+      newbody = newbody.reverse;
+    }
+    _m.tree = scalaAut.getMatcherSwitch( _m.selector,
+                                        defaultCase,
+                                        newbody );
+  } // construct (PartialMatcher, Tree[], Tree[], Tree, boolean )
+
+  } // class SequenceMatcher
+}
diff --git a/sources/scala/tools/nsc/matching/StateSetComparator.scala b/sources/scala/tools/nsc/matching/StateSetComparator.scala
new file mode 100644
index 0000000000..99942f38d5
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/StateSetComparator.scala
@@ -0,0 +1,34 @@
+package scala.tools.nsc.matching ;
+
+import java.util.{Comparator, TreeSet} ;
+
+class StateSetComparator extends Comparator {
+  // use lexicographic order
+  def compare(o1: Any , o2: Any ): Int = {
+    /*
+     System.out.print("lexi" );
+     System.out.print( o1 +" ");
+     System.out.println( o2 );
+     */
+    val it1 = o1.asInstanceOf[TreeSet].iterator();
+    val it2 = o2.asInstanceOf[TreeSet].iterator();
+    while( it1.hasNext() ) {
+      while( it2.hasNext() ) {
+        if( !it1.hasNext() )
+          return -1;
+
+        val i1 = it1.next().asInstanceOf[Integer].intValue();
+        val i2 = it2.next().asInstanceOf[Integer].intValue();
+        if( i1 < i2 )
+          return -1;
+        else if ( i1 > i2 )
+          return 1;
+      }
+      if( it1.hasNext() )
+        return 1;
+    }
+    if( it2.hasNext() )
+      return -1;
+    return 0;
+  }
+}