matching

8 files changed, 443 insertions, 125 deletions

diff --git a/sources/scala/tools/nsc/ast/TreeGen.scala b/sources/scala/tools/nsc/ast/TreeGen.scala
index fc31aeff4c..fa0c7ab2e8 100755
--- a/sources/scala/tools/nsc/ast/TreeGen.scala
+++ b/sources/scala/tools/nsc/ast/TreeGen.scala
@@ -115,4 +115,17 @@ abstract class TreeGen {
     mkAsInstanceOf(value, tpe, global.phase.erasedTypes);
   }
 
+
+  /** Builds a list with given head and tail. */
+  def mkNewCons(head: Tree, tail: Tree):  Tree =
+    New(Apply(mkRef(definitions.ConsClass), List(head,tail)));
+
+  /** Builds a list with given head and tail. */
+  def mkNil: Tree =
+    mkRef(definitions.NilModule);
+
+  /** Builds a pair */
+  def mkNewPair(left: Tree, right: Tree) =
+    New(Apply(mkRef(definitions.TupleClass(2)), List(left,right)));
+
 }
diff --git a/sources/scala/tools/nsc/ast/Trees.scala b/sources/scala/tools/nsc/ast/Trees.scala
index e3230fe19e..7ee1a44d8a 100644
--- a/sources/scala/tools/nsc/ast/Trees.scala
+++ b/sources/scala/tools/nsc/ast/Trees.scala
@@ -246,10 +246,15 @@ abstract class Trees: Global {
   case class Block(stats: List[Tree], expr: Tree)
        extends TermTree;
 
-  /** Case clause in a pattern match, eliminated by TransMatch */
+  /** Case clause in a pattern match, eliminated by TransMatch
+   *  (except for occurences in switch statements)
+   */
   case class CaseDef(pat: Tree, guard: Tree, body: Tree)
        extends Tree;
 
+  /** casedef shorthand */
+  def CaseDef(pat: Tree, body: Tree): CaseDef = CaseDef(pat, EmptyTree, body);
+
   /** Sequence of expression/patterns (comma separated expressions),
    *  eliminated by TransMatch */
   case class Sequence(trees: List[Tree])
@@ -368,7 +373,6 @@ abstract class Trees: Global {
     Ident(sym.name) setSymbol sym
   }
 
-
   /** Literal */
   case class Literal(value: Any)
        extends TermTree {
diff --git a/sources/scala/tools/nsc/matching/CodeFactory.scala b/sources/scala/tools/nsc/matching/CodeFactory.scala
index fa2d2dfe95..0e81abdcaf 100644
--- a/sources/scala/tools/nsc/matching/CodeFactory.scala
+++ b/sources/scala/tools/nsc/matching/CodeFactory.scala
@@ -5,7 +5,7 @@ package scala.tools.nsc.matching ;
 
 import scala.tools.util.Position;
 
-abstract class CodeFactory extends PatternUtil {
+abstract class CodeFactory: TransMatcher  {
 
   import global._ ;
 
@@ -13,6 +13,40 @@ abstract class CodeFactory extends PatternUtil {
   import typer.typed;               // methods to type trees
   import posAssigner.atPos;         // for filling in tree positions
 
+
+  /** returns  `List[ Tuple2[ scala.Int, <elemType> ] ]' */
+  def SeqTraceType( elemType: Type  ):  Type = {
+    appliedType(definitions.ListClass.typeConstructor,
+                List(pairType(definitions.IntClass.info,
+                              elemType)))
+  }
+
+
+
+  def pairType(left: Type, right: Type) = {
+    appliedType( definitions.TupleClass(2).typeConstructor,
+                List(left,right))
+  }
+
+  /**  returns `Iterator[ elemType ]' */
+  def _seqIterType( elemType: Type  ):  Type = {
+    appliedType( definitions.IteratorClass.typeConstructor,
+                List(elemType))
+  }
+
+  /** returns A for T <: Sequence[ A ]
+   */
+  def getElemType_Sequence(tpe: Type):  Type = {
+    //System.err.println("getElemType_Sequence("+tpe.widen()+")");
+    val tpe1 = tpe.widen.baseType( definitions.SeqClass );
+
+    if( tpe1 == NoType )
+      Predef.error("arg "+tpe+" not subtype of Seq[ A ]");
+
+    return tpe1.typeArgs( 0 );
+  }
+
+
   // --------- these are new
 
   /** a faked switch statement
@@ -57,19 +91,6 @@ abstract class CodeFactory extends PatternUtil {
     Apply(Select(iter, definitions.List_isEmpty), List());
 
 
-  def SeqTrace_headElem( arg: Tree  ) = { // REMOVE SeqTrace
-    val t = Apply(Select(arg, definitions.List_head), List());
-    Apply(Select(t, definitions.tupleField(2,2)),List())
-  }
-
-  def SeqTrace_headState( arg: Tree  ) = { // REMOVE SeqTrace
-    val t = Apply(Select(arg, definitions.List_head), List());
-    Apply(Select(t, definitions.tupleField(2,1)),List())
-  }
-
-  def SeqTrace_tail( arg: Tree ): Tree =  // REMOVE SeqTrace
-    Apply(Select(arg, definitions.List_tail), List());
-
   /** `arg.head' */
   def SeqList_head( arg: Tree ) =
     Apply(Select(arg, definitions.List_head), List());
@@ -161,28 +182,30 @@ abstract class CodeFactory extends PatternUtil {
     Apply(Select(left, eqsym), List(right));
   }
 
-  def ThrowMatchError(pos: Int, tpe: Type ) =
+  def ThrowMatchError(pos: Int ) =
     Apply(
       gen.mkRef(definitions.MatchError_fail),
       List(
-        Literal(unit.toString()),
+        Literal(cunit.toString()),
         Literal(Position.line(pos))
       )
     );
 
-  def ThrowMatchError(pos:int , tpe:Type , tree:Tree ) =
+  /* // ?!
+  def ThrowMatchError(pos:int , tree:Tree ) =
    Apply(
      gen.mkRef(definitions.MatchError_report),
      List(
-       Literal(unit.toString()),
+       Literal(cunit.toString()),
        Literal(Position.line(pos)),
        tree
      )
    );
+  */
+  def Error(pos: Int) =
+    ThrowMatchError(pos);
 
-  def Error(pos: Int, tpe: Type) =
-    ThrowMatchError(pos: Int, tpe: Type );
-
+  /*
   def newPair(left: Tree, right: Tree) =
     New(
       Apply(
@@ -190,6 +213,6 @@ abstract class CodeFactory extends PatternUtil {
         List(left,right)
       )
     );
-
+  */
 }
 
diff --git a/sources/scala/tools/nsc/matching/PatternMatcher.scala b/sources/scala/tools/nsc/matching/PatternMatcher.scala
index e96fa008e6..d087131480 100644
--- a/sources/scala/tools/nsc/matching/PatternMatcher.scala
+++ b/sources/scala/tools/nsc/matching/PatternMatcher.scala
@@ -8,19 +8,22 @@ package scala.tools.nsc.matching ;
 
 import scala.tools.util.Position;
 
-abstract class PatternMatcher extends PatternUtil with PatternNodes with PatternNodeCreator with CodeFactory  {
+trait PatternMatchers: (TransMatcher with PatternNodes) with PatternNodeCreator {
 
   import global._;
-
   import symtab.Flags;
 
+ class PatternMatcher  {
+
+
+
   protected var optimize = true;
   protected var delegateSequenceMatching = false;
   protected var doBinding = true;
 
   /** the owner of the pattern matching expression
    */
-  protected var owner:Symbol = _ ;
+  var owner:Symbol = _ ;
 
   /** the selector expression
    */
@@ -34,18 +37,10 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
    */
   protected var resultVar: Symbol = _;
 
-  /** methods to generate scala code
-   */
-  protected val cf: this.type = this;
-
-  /** methods to create pattern nodes
-   */
-  protected val mk: this.type = this;
-
   def defs = definitions;
   /** init method, also needed in subclass AlgebraicMatcher
    */
-  def initialize(selector: Tree, owner: Symbol, resultType: Type, doBinding: Boolean): Unit = {
+  def initialize(selector: Tree, owner: Symbol, doBinding: Boolean): Unit = {
 
     /*
     this.mk = new PatternNodeCreator {
@@ -61,13 +56,12 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
       val owner = PatternMatcher.this.owner;
     }
     */
-    this.root = mk.ConstrPat(selector.pos, selector.tpe.widen);
-    this.root.and = mk.Header(selector.pos,
+    this.root = pConstrPat(selector.pos, selector.tpe.widen);
+    this.root.and = pHeader(selector.pos,
                               selector.tpe.widen,
                               Ident(root.symbol));
     this.resultVar = owner.newVariable(Flags.MUTABLE,
                                        "result");
-    this.resultVar.setInfo(resultType);
     this.owner = owner;
     this.selector = selector;
     this.optimize = this.optimize & (settings.target == "jvm");
@@ -97,11 +91,11 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
         // if (target.and != null)
         //     unit.error(pat.pos, "duplicate case");
       if (null == target.and)
-        target.and = mk.Body(caseDef.pos, env.getBoundVars(), guard, body);
+        target.and = pBody(caseDef.pos, env.getBoundVars(), guard, body);
       else if (target.and.isInstanceOf[Body])
         updateBody(target.and.asInstanceOf[Body], env.getBoundVars(), guard, body);
       else
-        unit.error(pat.pos, "duplicate case");
+        cunit.error(pat.pos, "duplicate case");
     }
   }
 
@@ -166,17 +160,17 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
     tree match {
       case Bind(name, Typed(Ident( nme.WILDCARD ), tpe)) => // x@_:Type
         if (isSubType(header.getTpe(),tpe.tpe)) {
-          val node = mk.DefaultPat(tree.pos, tpe.tpe);
+          val node = pDefaultPat(tree.pos, tpe.tpe);
           env.newBoundVar( tree.symbol, tree.tpe, header.selector );
           node;
         } else {
-          val node = mk.ConstrPat(tree.pos, tpe.tpe);
+          val node = pConstrPat(tree.pos, tpe.tpe);
           env.newBoundVar( tree.symbol, tree.tpe, Ident( node.casted ));
           node;
         }
 
       case Bind(name, Ident(nme.WILDCARD)) => // x @ _
-        val node = mk.DefaultPat(tree.pos, header.getTpe());
+        val node = pDefaultPat(tree.pos, header.getTpe());
         if ((env != null) && (tree.symbol != defs.PatternWildcard))
           env.newBoundVar( tree.symbol, tree.tpe, header.selector);
         node;
@@ -195,19 +189,19 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
           if (!delegateSequenceMatching) {
             args(0) match {
               case Sequence(ts)=>
-                mk.SequencePat(tree.pos, tree.tpe, ts.length);
+                pSequencePat(tree.pos, tree.tpe, ts.length);
             }
           } else {
-            val res = mk.ConstrPat(tree.pos, tree.tpe);
-            res.and = mk.Header(tree.pos, header.getTpe(), header.selector);
-            res.and.and = mk.SeqContainerPat(tree.pos, tree.tpe, args(0));
+            val res = pConstrPat(tree.pos, tree.tpe);
+            res.and = pHeader(tree.pos, header.getTpe(), header.selector);
+            res.and.and = pSeqContainerPat(tree.pos, tree.tpe, args(0));
             res;
           }
         } else if ((fn.symbol != null) &&
                    fn.symbol.isStable &&
                    !(fn.symbol.isModule &&
                      ((fn.symbol.flags & Flags.CASE) != 0))) {
-                       mk.VariablePat(tree.pos, tree);
+                       pVariablePat(tree.pos, tree);
                      }
            else {
              /*
@@ -215,15 +209,15 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
             Console.println("tree.tpe="+tree.tpe);
             Console.println("tree.symbol="+tree.symbol);
              */
-             mk.ConstrPat(tree.pos, tree.tpe);
+             pConstrPat(tree.pos, tree.tpe);
            }
         case t @ Typed(ident, tpe) =>       // variable pattern
           val doTest = isSubType(header.getTpe(),tpe.tpe);
           val node = {
             if(doTest)
-              mk.DefaultPat(tree.pos, tpe.tpe)
+              pDefaultPat(tree.pos, tpe.tpe)
             else
-              mk.ConstrPat(tree.pos, tpe.tpe);
+              pConstrPat(tree.pos, tpe.tpe);
           }
           if ((null != env) && (ident.symbol != defs.PatternWildcard))
             node match {
@@ -240,45 +234,45 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
 
         case Ident(name) =>               // pattern without args or variable
             if (tree.symbol == defs.PatternWildcard)
-              mk.DefaultPat(tree.pos, header.getTpe());
+              pDefaultPat(tree.pos, header.getTpe());
             else if (tree.symbol.isPrimaryConstructor) {
               scala.Predef.error("error may not happen"); // Burak
 
             } else if (treeInfo.isVariableName(name)) {//  Burak
               scala.Predef.error("this may not happen"); // Burak
             } else
-              mk.VariablePat(tree.pos, tree);
+              pVariablePat(tree.pos, tree);
 
         case Select(_, name) =>                                  // variable
             if (tree.symbol.isPrimaryConstructor)
-                mk.ConstrPat(tree.pos, tree.tpe);
+                pConstrPat(tree.pos, tree.tpe);
             else
-                mk.VariablePat(tree.pos, tree);
+                pVariablePat(tree.pos, tree);
 
         case Literal(value) =>
-            mk.ConstantPat(tree.pos, tree.tpe, value);
+            pConstantPat(tree.pos, tree.tpe, value);
 
         case Sequence(ts) =>
             if ( !delegateSequenceMatching ) {
-                mk.SequencePat(tree.pos, tree.tpe, ts.length);
+                pSequencePat(tree.pos, tree.tpe, ts.length);
             } else {
-                mk.SeqContainerPat(tree.pos, tree.tpe, tree);
+                pSeqContainerPat(tree.pos, tree.tpe, tree);
             }
         case Alternative(ts) =>
           if(ts.length < 2)
             scala.Predef.error("ill-formed Alternative");
-          val subroot = mk.ConstrPat(header.pos, header.getTpe());
-          subroot.and = mk.Header(header.pos, header.getTpe(), header.selector.duplicate);
+          val subroot = pConstrPat(header.pos, header.getTpe());
+          subroot.and = pHeader(header.pos, header.getTpe(), header.selector.duplicate);
             val subenv = new CaseEnv;
           var i = 0; while(i < ts.length) {
             val target = enter1(ts(i), -1, subroot, subroot.symbol, subenv);
-            target.and = mk.Body(tree.pos);
+            target.and = pBody(tree.pos);
             i = i + 1
           }
-          mk.AltPat(tree.pos, subroot.and.asInstanceOf[Header]);
+          pAltPat(tree.pos, subroot.and.asInstanceOf[Header]);
 
         case _ =>
-          scala.Predef.error("unit = " + unit + "; tree = "+tree);
+          scala.Predef.error("unit = " + cunit + "; tree = "+tree);
     }
   }
 
@@ -302,7 +296,7 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
       val t = Apply(Select( ident, defs.functionApply( 1 )),
                     List( Literal( index ) ));
       val seqType = t.tpe;
-      mk.Header( pos, seqType, t );
+      pHeader( pos, seqType, t );
     } else {
       //Console.println("NOT FIRSTPOS");
       val ts = casted.tpe.symbol.asInstanceOf[ClassSymbol]
@@ -313,10 +307,10 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
       accType match {
         // scala case accessor
         case MethodType(_, _) =>
-          mk.Header(pos, accType.resultType, Apply(accTree, List()));
+          pHeader(pos, accType.resultType, Apply(accTree, List()));
         // jaco case accessor
         case _ =>
-          mk.Header(pos, accType, accTree);
+          pHeader(pos, accType, accTree);
       }
     }
   }
@@ -357,7 +351,7 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
                    ((next.or == null) &&            //  no more alternatives and
                     (patNode.isDefaultPat() || next.subsumes(patNode)))) {
                       // new node is default or subsumed
-                      var header = mk.Header(patNode.pos,
+                      var header = pHeader(patNode.pos,
                                              curHeader.getTpe(),
                                              curHeader.selector);
                       {curHeader.next = header; header};
@@ -574,7 +568,7 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
 
     //print();
     val ncases = numCases(root.and);
-    val matchError = cf.ThrowMatchError(selector.pos, resultVar.tpe);
+    val matchError = ThrowMatchError(selector.pos);
     // without a case, we return a match error if there is no default case
     if (ncases == 0)
       return defaultBody(root.and, matchError);
@@ -582,7 +576,7 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
     else if (ncases == 1) {
       root.and.or match {
         case ConstantPat(value) =>
-          return If(cf.Equals(selector, Literal(value)),
+          return If(Equals(selector, Literal(value)),
                     (root.and.or.and).bodyToTree(),
                     defaultBody(root.and, matchError));
         case _ =>
@@ -619,6 +613,13 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
     }
 
     var n = mappings.length();
+    var nCases: List[CaseDef] = Nil;
+    while (mappings != null) {
+      nCases = CaseDef(Literal(mappings.tag),
+                       mappings.body) :: nCases;
+      mappings = mappings.next;
+    }
+    /*
     val tags = new Array[Int](n);
     val bodies = new Array[Tree](n);
     n = 0;
@@ -629,6 +630,9 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
       mappings = mappings.next;
     }
     return Switch(selector, tags, bodies, defaultBody1, resultVar.tpe);
+    */
+    nCases = CaseDef(Ident(nme.WILDCARD), defaultBody1) :: nCases;
+    return Match(selector, nCases)
   }
 
   def generalSwitchToTree(): Tree = {
@@ -637,9 +641,8 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
       ValDef(resultVar, EmptyTree /* DefaultValue */));
     val res = If(toTree(root.and),
                  Ident(resultVar),
-                 cf.ThrowMatchError(selector.pos,
-                                    resultVar.tpe,
-                                    Ident(root.symbol)));
+                 ThrowMatchError(selector.pos /* ,
+                                    Ident(root.symbol) */));
     return Block(ts, res);
   }
 
@@ -674,12 +677,12 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
       case _h:Header =>
         val selector = _h.selector;
       val next = _h.next;
-      //res = cf.And(mkNegate(res), toTree(node.or, selector));
+      //res = And(mkNegate(res), toTree(node.or, selector));
       //Console.println("HEADER TYPE = " + selector.type);
       if (optimize1(node.getTpe(), node.or))
-        res = cf.Or(res, toOptTree(node.or, selector));
+        res = Or(res, toOptTree(node.or, selector));
       else
-            res = cf.Or(res, toTree(node.or, selector));
+            res = Or(res, toTree(node.or, selector));
           node = next;
 
         case _b:Body =>
@@ -699,8 +702,8 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
                       List(Assign(Ident(resultVar), body(i))),
                       Literal(true));
                   if (guard(i) != EmptyTree)
-                    res0 = cf.And(guard(i), res0);
-                  res = cf.Or(Block(ts.toList, res0), res);
+                    res0 = And(guard(i), res0);
+                  res = Or(Block(ts.toList, res0), res);
                   i = i - 1
                 }
         return res;
@@ -758,6 +761,7 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
           scala.Predef.error("errare humanum est");
       }
       var n = cases.length();
+      /*
       val tags = new Array[int](n);
       val bodies = new Array[Tree](n);
       n = 0;
@@ -767,6 +771,10 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
         n = n + 1;
         cases = cases.next;
       }
+      */
+
+
+      /*
       return
       Switch(
         Apply(
@@ -776,6 +784,23 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
         bodies,
         { if (defaultCase == null) Literal(false) else toTree(defaultCase.and) },
                         defs.boolean_TYPE());
+                        */
+      var nCases: List[CaseDef] = Nil;
+      while (cases != null) {
+        nCases = CaseDef(Literal(cases.tag),
+                         toTree(cases.node, selector)) :: nCases;
+        cases = cases.next;
+      }
+
+      val defBody = if (defaultCase == null)
+                      Literal(false)
+                    else
+                      toTree(defaultCase.and);
+
+      nCases = CaseDef(Ident(nme.WILDCARD), defBody) :: nCases;
+      return Match(Apply(Select(selector.duplicate, defs.ScalaObjectClass_tag),
+                         List()),
+                   nCases);
     }
 
     protected def toTree(node:PatternNode , selector:Tree ): Tree = {
@@ -796,10 +821,10 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
                       toTree(node.or, selector.duplicate));
           case SequencePat(casted, len) =>
             return
-          cf.Or(
-            cf.And(
-              cf.And(gen.mkIsInstanceOf(selector.duplicate, node.getTpe()),
-                     cf.Equals(
+          Or(
+            And(
+              And(gen.mkIsInstanceOf(selector.duplicate, node.getTpe()),
+                     Equals(
                        Apply(
                          Select(
                            gen.mkAsInstanceOf(selector.duplicate,
@@ -815,12 +840,12 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
                   toTree(node.and))),
             toTree(node.or, selector.duplicate));
           case ConstantPat(value) =>
-            return If(cf.Equals(selector.duplicate,
+            return If(Equals(selector.duplicate,
                                 Literal(value)),
                       toTree(node.and),
                       toTree(node.or, selector.duplicate));
           case VariablePat(tree) =>
-            return If(cf.Equals(selector.duplicate, tree),
+            return If(Equals(selector.duplicate, tree),
                       toTree(node.and),
                       toTree(node.or, selector.duplicate));
           case AltPat(header) =>
@@ -834,3 +859,4 @@ abstract class PatternMatcher extends PatternUtil with PatternNodes with Pattern
 }
 
 
+}
diff --git a/sources/scala/tools/nsc/matching/PatternNodeCreator.scala b/sources/scala/tools/nsc/matching/PatternNodeCreator.scala
index 60eab3d92e..9646225869 100644
--- a/sources/scala/tools/nsc/matching/PatternNodeCreator.scala
+++ b/sources/scala/tools/nsc/matching/PatternNodeCreator.scala
@@ -6,15 +6,15 @@ import scala.tools.util.Position;
  *  we inherit the globals from PatternTool.
  */
 
-abstract class PatternNodeCreator extends PatternUtil with PatternNodes {
+trait PatternNodeCreator: (TransMatcher with PatternNodes) {
 
   import global._;
 
-  var owner:Symbol = _;
+  def owner:Symbol;
   /** the owner of the variable symbols that might be created */
   //Symbol owner;
 
-  def SequencePat(pos: Int , tpe:Type ,  len:int) = {
+  def pSequencePat(pos: Int , tpe:Type ,  len:int) = {
     val sym = newVar(Position.FIRSTPOS, tpe);
     val node = new SequencePat(sym, len);
     node.pos = pos;
@@ -22,7 +22,7 @@ abstract class PatternNodeCreator extends PatternUtil with PatternNodes {
     node;
   }
 
-  def SeqContainerPat(pos: int, tpe: Type, seqpat:Tree ) = {
+  def pSeqContainerPat(pos: int, tpe: Type, seqpat:Tree ) = {
     val sym = newVar(Position.NOPOS, tpe);
     val node = new SeqContainerPat(sym, seqpat);
     node.pos = pos;
@@ -30,35 +30,35 @@ abstract class PatternNodeCreator extends PatternUtil with PatternNodes {
     node;
   }
 
-  def DefaultPat(pos: int, tpe: Type) = {
+  def pDefaultPat(pos: int, tpe: Type) = {
     val node = new DefaultPat();
     node.pos = pos;
     node.setType(tpe);
     node;
   }
 
-  def ConstrPat(pos: int, tpe: Type) = {
+  def pConstrPat(pos: int, tpe: Type) = {
     val node = new ConstrPat(newVar(pos, tpe));
     node.pos = pos;
     node.setType(tpe);
     node;
   }
 
-  def ConstantPat(pos: int, tpe: Type, value: Any /*AConstant*/ ) = {
+  def pConstantPat(pos: int, tpe: Type, value: Any /*AConstant*/ ) = {
     val node = new ConstantPat( value );
     node.pos = pos;
     node.setType(tpe);
     node;
   }
 
-  def VariablePat(pos: int,  tree:Tree) = {
+  def pVariablePat(pos: int,  tree:Tree) = {
     val node = new VariablePat( tree );
     node.pos = pos;
     node.setType(tree.tpe);
     node;
   }
 
-  def AltPat(pos: int, header:Header ) = {
+  def pAltPat(pos: int, header:Header ) = {
     val node = new AltPat(header);
     node.pos = pos;
     node.setType(header.getTpe());
@@ -67,20 +67,20 @@ abstract class PatternNodeCreator extends PatternUtil with PatternNodes {
 
   // factories
 
-  def Header(pos: int, tpe: Type,  selector:Tree) = {
+  def pHeader(pos: int, tpe: Type,  selector:Tree) = {
     val node = new Header(selector, null);
     node.pos = pos;
     node.setType(tpe);
     node;
   }
 
-  def Body(pos: int) = {
+  def pBody(pos: int) = {
     val node = new Body(new Array[Array[ValDef]](0), new Array[Tree](0), new Array[Tree](0));
     node.pos = pos;
     node;
   }
 
-  def Body(pos: int, bound:Array[ValDef] ,  guard:Tree,  body:Tree) = {
+  def pBody(pos: int, bound:Array[ValDef] ,  guard:Tree,  body:Tree) = {
     val node = new Body(Predef.Array[Array[ValDef]](bound), Predef.Array[Tree](guard), Predef.Array[Tree](body));
     node.pos = pos;
     node;
@@ -95,7 +95,7 @@ abstract class PatternNodeCreator extends PatternUtil with PatternNodes {
   }
 
   def newVar(pos: int, tpe: Type): Symbol = {
-    newVar(pos, unit.fresh.newName("temp"), tpe);
+    newVar(pos, cunit.fresh.newName("temp"), tpe);
   }
 }
 
diff --git a/sources/scala/tools/nsc/matching/PatternNodes.scala b/sources/scala/tools/nsc/matching/PatternNodes.scala
index e93b20f47c..4e4e0970b2 100644
--- a/sources/scala/tools/nsc/matching/PatternNodes.scala
+++ b/sources/scala/tools/nsc/matching/PatternNodes.scala
@@ -10,9 +10,7 @@ package scala.tools.nsc.matching ;
 
 import scala.tools.util.Position;
 
-abstract class PatternNodes {
-
-  val global: Global;
+trait PatternNodes: TransMatcher {
 
   import global._;
 
diff --git a/sources/scala/tools/nsc/matching/TransMatcher.scala b/sources/scala/tools/nsc/matching/TransMatcher.scala
index 7cb1a3ccd3..2f74cb7315 100644
--- a/sources/scala/tools/nsc/matching/TransMatcher.scala
+++ b/sources/scala/tools/nsc/matching/TransMatcher.scala
@@ -7,7 +7,20 @@ package scala.tools.nsc.matching;
 
 /** Translation of pattern matching
  */
-abstract class TransMatcher {
+abstract class TransMatcher
+with PatternNodes
+with CodeFactory
+with PatternMatchers
+with SequenceMatchers
+with AlgebraicMatchers
+with MatcherLabels
+with BerrySethis
+with DetWordAutoms
+with NondetWordAutoms
+with Autom2
+with WordAutoms
+with LeftTracers
+with RightTracers {
 
   val global: Global;
 
@@ -15,13 +28,100 @@ abstract class TransMatcher {
   import definitions._;
   import posAssigner.atPos;
 
-  private var unit: CompilationUnit;
+  /** container. classes AlgebraicMatcher and SequenceMatcher get input and
+   *  store their results in here. resembles the 'Memento' design pattern,
+   *  could also be named 'Liaison'
+   */
+  abstract class PartialMatcher {
+
+    /** owner of the code we create (input)
+     */
+    val owner: Symbol;
+
+    /** the selector value (input)
+     */
+    val selector:Tree;
+
+    /** tree representing the matcher (output)
+     */
+    var tree: Tree  = _ ;
+
+    def pos: int = selector.pos;
+
+    //assert( owner != null ) : "owner is null";
+    //assert owner != Symbol.NONE ;
+    //this.owner      = owner;
+
+    //assert root != null;
+    //assert root.type != null;
+    //this.selector   = root;
+
+    //assert this.resultType != Type.NoType;
+    //this.resultType = resultType;
+
+    //this.pos        = root.pos; // for convenience only
+
+  }
+
+  var cunit: CompilationUnit;
+
+  def fresh = cunit.fresh ;
+
+  def containsBinding(pat: Tree): Boolean = {
+    var generatedVars = false;
+
+    def handleVariableSymbol(sym: Symbol): Unit  =
+      if (sym.name.toString().indexOf("$") == -1) {
+        generatedVars = true; // .add(sym);
+      }
+
+    def isVariableName(name: Name): Boolean =
+      ( treeInfo.isVariableName(name) ) && ( name != nme.USCOREkw ) ;
+
+    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)
+            error("shouldn't happen?!");
+
+        case Bind(name, subtree) =>
+          var sym: Symbol = _;
+
+        if (isVariableName(name)
+            && isVariableSymbol( {sym = tree.symbol; tree.symbol} ))
+          handleVariableSymbol(sym);
+
+        traverse( subtree );
+
+        // congruence
+
+        case Apply(fun, args) => args foreach traverse;
+        case Sequence(trees)  => trees foreach traverse
+        case Star(arg)        => traverse(arg)
+        case Typed(expr, tpe) => traverse(expr); // needed??
+
+        case  _ : Select |
+               _ : Alternative |
+               _ : Select |
+               _ : Literal =>  ; // no variables
+
+        case _ =>
+          error("unknown pattern node:" + tree + " = " + tree.getClass());
+      }
+    }
+    traverse(pat);
+    generatedVars;
+  }
 
   class TransMatchPhase(prev: Phase) extends StdPhase(prev) {
     def name = "transmatcher";
     val global: TransMatcher.this.global.type = TransMatcher.this.global;
     def apply(unit: CompilationUnit): unit = {
-      TransMatcher.this.unit = unit;
+      TransMatcher.this.cunit = unit;
       unit.body = newTransMatcher.transform(unit.body);
     }
   }
@@ -38,16 +138,18 @@ abstract class TransMatcher {
 
       case Bind( n, pat1 )         =>  isRegular( pat1 )
       case Sequence( trees )       =>
-        ( trees.length == 0 ) || isRegular( trees );
+        ( trees.length == 0 ) || (trees exists { isRegular });
+
+      case Apply( fn, List(Sequence(List())))      =>
+        false;
 
       case Apply( fn, trees )      =>
-        isRegular( trees ) &&
-      !((trees.length == 1) && TreeInfo.isEmptySequence( trees( 0 )))
+        ( trees exists { isRegular })
+//      && !((trees.length == 1) && TreeInfo.isEmptySequence( trees( 0 )))
 
       case Literal(_)              => false;
       case Select(_,_)             => false;
       case Typed(_,_)              => false;
-      case _ => error("in TransMatch.isRegular phase: unknown node"+pat.getClass());
     }
 
 
@@ -64,8 +166,8 @@ abstract class TransMatcher {
       def remove(pat: Tree): Tree = pat.match {
         case Alternative( _ )          => pat /* no bind/var allowed! */
         case Star( _ )                 => pat /* no bind/var allowed! */
-        case Bind( id, empt @ Sequence()) =>
-          nilVars = id.symbol() :: nilVars;
+        case Bind( id, empt @ Sequence(List())) =>
+          nilVars = pat.symbol /*id.symbol()*/ :: nilVars;
           empt
         case Bind( id, pat )           =>
           copy.Bind( pat, id, remove(pat) );
@@ -81,7 +183,7 @@ abstract class TransMatcher {
         case Select(_,_)       => pat
         case Typed(_,_)        => pat
 
-        case _ => error("unknown node"+pat.getClass());
+        case _ => scala.Predef.error("unknown node"+pat.getClass());
       }
 
       cd.match {
@@ -92,7 +194,9 @@ abstract class TransMatcher {
               body
             else
               atPos(body.pos)(
-                Block(nilVars map { x => ValDef(s, gen.mkNil) }, body)
+                Block(nilVars map {
+                  x => ValDef(x, Ident(definitions.NilModule))
+                }, body)
               )
           }
         copy.CaseDef(cd, npat, guard, nbody)
@@ -110,29 +214,33 @@ abstract class TransMatcher {
       if(containsReg) {
         // 2. replace nilVariables
         //@todo: bring over AlgebraicMatcher
-        //val ncases  = cases.map { removeNilVariables };
-        //val matcher = new PartialMatcher( currentOwner, root, restpe );
-        //new AlgebraicMatcher().construct( matcher, ncases );
-
+        val ncases  = cases.map { removeNilVariables };
+        val matcher = new PartialMatcher {
+          val global: TransMatcher.this.global.type = TransMatcher.this.global;
+          val owner = currentOwner;
+          val selector = sel ;
+        }
+        //new AlgebraicMatcher() {
+        //  val tm: TransMatcher.this.type = TransMatcher.this;
+        //}.construct( matcher, ncases );
         //matcher.tree
         null
       } else {
-        val pm = new matching.PatternMatcher() {
-          val global = TransMatcher.this.global;
-        }
-        pm.initialize(root, currentOwner, restpe, true );
+        val pm = new PatternMatcher();
+        pm.initialize(sel, currentOwner, true );
         pm.construct( cases );
-        if (global.log()) {
-          global.log("internal pattern matching structure");
-          pm.print();
-        }
+        //if (global.log()) {
+        //  global.log("internal pattern matching structure");
+        //  pm.print();
+        //}
         pm.toTree();
       }
     }
 
-    override def transform(tree: Tree) = tree match {
+    override def transform(tree: Tree): Tree = tree match {
       case Match(selector, cases) =>
-        handle(transform(selector), transform1(cases));
+        val ts = cases map { transform };
+        handle(transform(selector), ts.asInstanceOf[List[CaseDef]]);
       case _ =>
         super.transform(tree);
     }
diff --git a/sources/scala/tools/nsc/matching/WordAutoms.scala b/sources/scala/tools/nsc/matching/WordAutoms.scala
new file mode 100644
index 0000000000..2a9dc26596
--- /dev/null
+++ b/sources/scala/tools/nsc/matching/WordAutoms.scala
@@ -0,0 +1,146 @@
+/* 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 WordAutoms: TransMatcher {
+
+  import global._ ;
+  /** translates a recognizer to scala code
+   */
+
+    /** constructor
+     * @param dfa         the dfa that is to be translated
+     * @param elementType type of the objects in the sequence
+     * @param owner       the owner of the pattern match
+     * @param cf          code factory
+     * @param optim       flag that indicates whether to optimize
+     * @return            an object that translates the dfa
+     */
+abstract class WordAutomInScala extends Autom2Scala {
+
+  val optim: Boolean;
+
+  this.optimize = this.optimize && optim;
+
+  var theLabelDef: Tree = _ ;
+
+  def getMatcherSwitch(selector: Tree, failTree: Tree, body: scala.List[Tree] /*, resultType: Type*/ ): Tree = {
+
+    var result: Tree = _;
+    var ncases: scala.List[CaseDef] = Nil;
+    val it = body.reverse.elements;
+    //val tags = new Array[int](body.length);
+    var i = body.length - 1;
+    while( i >= 0 ) {
+      //tags(i) = i;
+      ncases = CaseDef(Literal(i), it.next) :: ncases;
+      i = i - 1
+      }
+
+      ncases= ncases::: CaseDef(Ident(nme.WILDCARD),failTree) :: Nil;
+      result = Match( _swres(), ncases );
+
+      //}
+
+      result =
+        Block(
+          scala.List (
+            ValDef( iterSym, newIterator( selector.duplicate )),
+            ValDef( stateSym, Literal(0) ),
+            ValDef( resultSym, theLabelDef )),
+          result
+        );
+      //unit.global.debugPrinter.print( result );
+      result;
+    }
+
+    protected def initializeSyms(): Unit =  { // TEST
+
+      this.funSym = owner.newLabel( pos, fresh.newName( "matcher" ));
+
+      this.iterSym = owner.newVariable( pos, fresh.newName("iter"))
+      .setInfo( _seqIterType( elementType ) ) ;
+
+      this.stateSym = owner.newVariable( pos, fresh.newName("q"))
+      .setInfo( definitions.IntClass.info ) ;
+
+      this.resultSym = owner.newVariable( pos, fresh.newName("swRes"))
+      .setInfo( definitions.IntClass.info ) ;
+
+      this.funSym.setInfo( new MethodType(scala.List (definitions.IntClass.info),
+                                          definitions.IntClass.info ));
+
+      this.curSym = owner.newVariable( pos, "cur" /*Names.cur*/ )
+      .setInfo( elementType );
+
+      this.hasnSym = owner.newVariable( pos, nme.hasNext )
+      .setInfo( definitions.BooleanClass.info );
+
+    }
+
+    /** code for the return value of the automaton translation
+     */
+    override def run_finished(state: Int): Tree = { // T E S T
+      if( dfa.isFinal(state))
+        Literal(dfa.finals.get(new Integer(state)).asInstanceOf[Integer].intValue());
+      else
+        Literal(FAIL);
+    }
+
+
+  // calling the /*AlgebraicMatcher*/PatternMatcher here
+  override def _cur_match(pat: Tree): Tree = { // TE ST
+    val m = new PartialMatcher {
+      val owner = WordAutomInScala.this.owner;   /* owner*/
+      val selector = currentElem(); /* root */
+      // restyp definitions.BooleanClass.info /* restype */);
+    }
+
+    am.construct( m, scala.List (
+      CaseDef( pat, Literal( true )),
+      CaseDef( Ident(definitions.PatternWildcard), Literal( false )) ),
+                 false);
+    am.toTree();
+  }
+
+  /** do the translation
+   */
+  def translate(): Unit = {
+    initializeSyms();
+    val tb = code_body_NEW();
+    //theLabelDef = gen.DefDef(this.funSym, tb);
+    theLabelDef = LabelDef(this.funSym, scala.List( stateSym ), tb);
+  }
+
+  /** ...
+   * @return 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);
+
+    if (target == null)
+      label match {
+        case DefaultLabel() =>
+          code_error(); // this may not happen !
+        case _ =>
+          null; // not good
+      }
+    else if (target.intValue() == dfa.nstates() - 1) // that one is a dead state
+      code_fail();
+    else
+      callFun(scala.List( Literal(target.intValue() )));
+  }
+
+}
+}
+