pattern matcher - lost in translation

14 files changed, 2508 insertions, 56 deletions

diff --git a/config/list/scalac.lst b/config/list/scalac.lst
index 2cb91953b0..5ab90fcf75 100644
--- a/config/list/scalac.lst
+++ b/config/list/scalac.lst
@@ -114,17 +114,17 @@
 
 #../../../scalac/transformer/matching/AlgebraicMatcher.java
 #../../../scalac/transformer/matching/Autom2Scala.java
-../../../scalac/transformer/matching/BindingBerrySethi.java
-../../../scalac/transformer/matching/BerrySethi.java
+#../../../scalac/transformer/matching/BindingBerrySethi.java
+#../../../scalac/transformer/matching/BerrySethi.java
 #../../../scalac/transformer/matching/CaseEnv.java
 #../../../scalac/transformer/matching/CodeFactory.java
 #../../../scalac/transformer/matching/CollectVariableTraverser.java
-../../../scalac/transformer/matching/DetWordAutom.java
+#../../../scalac/transformer/matching/DetWordAutom.java
 #../../../scalac/transformer/matching/FreshVariableTraverser.java
-../../../scalac/transformer/matching/Label.java
+#../../../scalac/transformer/matching/Label.java
 #../../../scalac/transformer/matching/TracerInScala.java
 #../../../scalac/transformer/matching/LeftTracerInScala.java
-../../../scalac/transformer/matching/NondetWordAutom.java
+#../../../scalac/transformer/matching/NondetWordAutom.java
 #../../../scalac/transformer/matching/NoSeqVariableTraverser.java
 #../../../scalac/transformer/matching/PartialMatcher.java
 #../../../scalac/transformer/matching/PatternMatcher.java
@@ -133,7 +133,7 @@
 #../../../scalac/transformer/matching/PatternTool.java
 #../../../scalac/transformer/matching/RightTracerInScala.java
 #../../../scalac/transformer/matching/SequenceMatcher.java
-../../../scalac/transformer/matching/StateSetComparator.java
+#../../../scalac/transformer/matching/StateSetComparator.java
 #../../../scalac/transformer/matching/VariableTraverser.java
 #../../../scalac/transformer/matching/WordAutomInScala.java
 
@@ -184,11 +184,16 @@ transformer/UnCurry.scala
 transformer/UnCurryPhase.scala
 transformer/matching/AlgebraicMatcher.scala
 transformer/matching/Autom2Scala.scala
+transformer/matching/BindingBerrySethi.scala
+transformer/matching/BerrySethi.scala
 transformer/matching/CaseEnv.scala
 transformer/matching/CodeFactory.scala
 transformer/matching/CollectVariableTraverser.scala
+transformer/matching/DetWordAutom.scala
 transformer/matching/FreshVariableTraverser.scala
+transformer/matching/Label.scala
 transformer/matching/LeftTracerInScala.scala
+transformer/matching/NondetWordAutom.scala
 transformer/matching/PartialMatcher.scala
 transformer/matching/NoSeqVariableTraverser.scala
 transformer/matching/PatternMatcher.scala
@@ -197,6 +202,8 @@ transformer/matching/PatternNodeCreator.scala
 transformer/matching/PatternTool.scala
 transformer/matching/RightTracerInScala.scala
 transformer/matching/TracerInScala.scala
+transformer/matching/StateSetComparator.scala
+transformer/matching/Npair.scala
 transformer/matching/VariableTraverser.scala
 transformer/matching/WordAutomInScala.scala
 transformer/matching/SequenceMatcher.scala
diff --git a/sources/scala/tools/scalac/transformer/matching/Autom2Scala.scala b/sources/scala/tools/scalac/transformer/matching/Autom2Scala.scala
index 32018a870b..f091982f9b 100644
--- a/sources/scala/tools/scalac/transformer/matching/Autom2Scala.scala
+++ b/sources/scala/tools/scalac/transformer/matching/Autom2Scala.scala
@@ -12,18 +12,8 @@ import scalac.ast._;
 import scalac.symtab._;
 import scalac.util._;       // Names
 
-import scala.tools.scalac.util.NewArray;
-import scalac.transformer.{ OwnerTransformer => scalac_transformer_OwnerTransformer };
-
-//import scalac.transformer.matching.CodeFactory ;
-import scalac.transformer.matching.DetWordAutom ;
-//import scalac.transformer.matching.PatternNode ;
-import scalac.transformer.matching.Label ;
-
-//import PatternNode._ ;
-import Label._ ;
-
-
+import scalac.transformer.{ OwnerTransformer
+                           => scalac_transformer_OwnerTransformer };
 
 import Tree._;
 
@@ -78,7 +68,7 @@ package scala.tools.scalac.transformer.matching {
 
     // overridden in RightTracerInScala
     def loadCurrentElem(body: Tree): Tree = {
-      gen.mkBlock( NewArray.Tree (
+      gen.mkBlock( Predef.Array[Tree] (
         cf.gen.ValDef(this.hasnSym,
                       cf._hasNext( _iter() ) ),
         cf.gen.ValDef(this.curSym,
@@ -195,10 +185,10 @@ package scala.tools.scalac.transformer.matching {
     }
 
     def code_state_NEW(i: Int): Tree = {
-      var stateBody = code_delta( i, Label.DefaultLabel );
+      var stateBody = code_delta( i, DefaultLabel() );
       if( stateBody == null )
         stateBody = code_fail();
-      val trans = dfa.deltaq.asInstanceOf[Array[HashMap]]( i );
+      val trans = dfa.deltaq( i );
 
       val  labs = dfa.labels().iterator();
       while(labs.hasNext()) {
diff --git a/sources/scala/tools/scalac/transformer/matching/BerrySethi.scala b/sources/scala/tools/scalac/transformer/matching/BerrySethi.scala
new file mode 100644
index 0000000000..7bc5b32be1
--- /dev/null
+++ b/sources/scala/tools/scalac/transformer/matching/BerrySethi.scala
@@ -0,0 +1,666 @@
+/** $Id */
+import scalac.CompilationUnit ;
+import scalac.ApplicationError ;
+import scalac.ast.Tree ;
+import scalac.ast.TreeInfo ;
+import scalac.util.Name ;
+import Tree._ ;
+
+import java.util._ ;
+
+//import scala.compiler.printer.XMLAutomPrinter ;
+
+/** a Berry-Sethi style construction for nfas.
+ *  this class plays is the "Builder" for the "Director" class WordRecognizer.
+ */
+package scala.tools.scalac.transformer.matching {
+
+class BerrySethi(val unit: CompilationUnit ) {
+
+  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(_, _) =>
+        return false;
+
+      case Sequence( trees ) =>
+        return (trees.length == 0) || nullable( trees );
+      //case Subsequence( Tree[] trees ):
+      //return
+      case Bind(n, t) =>
+        /*
+         if( isStar( n ) ) // generated for star/plus(?)
+         return true;
+         */
+        return nullable( t );
+      case Alternative( choices) =>
+        var result = false;
+      var i = 0;
+      while(i < choices.length && !result) {
+        result = result || nullable( choices( i ) );
+        i = i + 1
+      }
+      return result;
+      case _ =>
+        return 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 ) =>
+        return nullable( pats );
+    }
+    return false;
+  }
+
+  /** 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("_") )
+        //    throw new ApplicationError("unexpected pattern");
+        val tmp = new TreeSet();
+        tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set
+        return tmp;
+
+      case _ =>
+        throw new ApplicationError("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 _ =>
+        throw new ApplicationError("unexpected pattern");
+    }
+  }
+
+
+  /** computes first(w) where w=alpha_1...alpha_n  are successors of a
+   *  sequence node
+   */
+  def compFirst( pats:Array[Tree]  ): TreeSet = {
+    if( pats.length == 0 )
+      return new TreeSet();
+
+    var i = 0;
+    var tmp = pats( i );
+    val result = compFirst( tmp );
+    i = i + 1;
+    while( nullable(tmp) && (i < pats.length )) {
+      tmp = pats( i );
+      result.addAll( compFirst( tmp ));
+      i = i + 1;
+    }
+    return result;
+  }
+
+  // Unit test ?
+
+  /** computes last(w) where w are successors of a sequence node
+   */
+  def compLast(pats: Array[Tree]): TreeSet = {
+    /*
+     System.out.print("<last>");
+     for( int k = 0; k<pats.length; k++) {
+     DEBUG.print( pats[k] );
+     System.out.print("  ");
+     }
+     System.out.println();
+     */
+    if( pats.length == 0 )
+      return new TreeSet();
+
+    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
+  def compFollow(pats: Array[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 );
+    }
+    if( null == first )
+      first = new TreeSet();
+    else {
+      first = fol;
+    }
+    this.follow.put(new Integer( 0 ), first);
+    return first;
+  }
+
+  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 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 _ =>
+        throw new ApplicationError("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
+          traverse( body );
+      return ;
+
+      case Ident(name) =>
+        if ((pat.symbol() != null )
+            && pat.symbol().isPrimaryConstructor()) {
+              // same as Apply
+              val label = new TreeLabel( pat );
+              seenLabel( pat, label ) ;
+
+              return ;
+            }
+
+
+      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:Array[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();
+    var  i = 0;
+    while(i < subexpr.length ) {
+      traverse( subexpr( i ));
+      //assert ( activeBinders.isEmpty() )
+      i = i + 1;
+    }
+
+    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( nullable( subexpr )) // 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;
+    }
+
+    throw new ApplicationError("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;
+    }
+
+  }
+}
+}
diff --git a/sources/scala/tools/scalac/transformer/matching/BindingBerrySethi.scala b/sources/scala/tools/scalac/transformer/matching/BindingBerrySethi.scala
new file mode 100644
index 0000000000..8c9a49f06d
--- /dev/null
+++ b/sources/scala/tools/scalac/transformer/matching/BindingBerrySethi.scala
@@ -0,0 +1,171 @@
+
+
+import scalac.CompilationUnit;
+import scalac.Global ;
+import scalac.ApplicationError ;
+import scalac.ast.Tree ;
+import scalac.util.Name ;
+import scalac.util.Names ;
+import Tree._ ;
+
+import java.util._ ;
+
+//import scala.compiler.printer.XMLTreePrinter ;
+//import scala.compiler.printer.XMLAutomPrinter ;
+
+package scala.tools.scalac.transformer.matching {
+/** a Berry-Sethi style construction for nfas.
+ *  this class plays is the "Builder" for the "Director" class
+ *  WordRecognizer.
+ */
+
+class BindingBerrySethi(unit:CompilationUnit)  extends BerrySethi(unit) {
+
+
+  var deltaqRev: Array[HashMap ] = _;    // delta of Rev
+  var defaultqRev:Array[Vector] = _;  // default transitions of Rev
+  var qbinders:Array[Vector] = _;  // transitions <-> variables
+
+  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 );
+  }
+
+  var  revnfa:  NondetWordAutom = _ ;
+
+  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 );
+    }
+  }
+
+  var varAt: HashMap = _;   // chi:    Positions -> Vars (Symbol)
+
+   override def initialize( pats:Array[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();
+    }
+  }
+}
+}
+
diff --git a/sources/scala/tools/scalac/transformer/matching/DetWordAutom.scala b/sources/scala/tools/scalac/transformer/matching/DetWordAutom.scala
new file mode 100644
index 0000000000..357b6fe652
--- /dev/null
+++ b/sources/scala/tools/scalac/transformer/matching/DetWordAutom.scala
@@ -0,0 +1,882 @@
+import scalac.ast.Tree ;
+import Tree._ ;
+
+import java.util._ ;
+
+import scalac.ApplicationError ;
+
+package scala.tools.scalac.transformer.matching {
+
+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 _ =>
+	   throw new ApplicationError("whut's this: label="+label+", class "+label.getClass());
+	}
+  }
+
+  def delta( i:Integer , label:Label  ):  Integer  = {
+    return 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 )
+      throw new ApplicationError("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/scalac/transformer/matching/Label.scala b/sources/scala/tools/scalac/transformer/matching/Label.scala
new file mode 100644
index 0000000000..3935ffc631
--- /dev/null
+++ b/sources/scala/tools/scalac/transformer/matching/Label.scala
@@ -0,0 +1,133 @@
+import scalac.ApplicationError;
+import scalac.ast.Tree ;
+import scalac.ast.TreeInfo ;
+import scalac.symtab.Symbol ;
+import scalac.symtab.Type ;
+import Tree.Literal ;
+
+/** this class represents the label that a transition in an automaton may carry.
+ *  these get translated to specific (boolean) tests
+ */
+package scala.tools.scalac.transformer.matching {
+
+class Label {
+
+
+      //case class RLabel( Object rstate, Label lab, Symbol vars[] );
+
+      override def hashCode(): Int = 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.getType().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 Tree.Apply( _, _ ) =>
+		   pat2.match {
+		     case Tree.Apply( _, _ ) =>
+		       return TreeInfo.methSymbol( pat ) == TreeInfo.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.getType().toString()+":p"+p;
+
+        case _ => throw new ApplicationError("this never happens");
+      }
+    }
+    throw new ApplicationError("this never happens");
+  }
+
+  override def toString():  String = {
+
+    this.match {
+      case DefaultLabel() =>
+        return "<>";
+      case SimpleLabel(  lit) =>
+        return lit.toString();
+      case TreeLabel(pat) =>
+        return pat.toString();
+      case TypeLabel( tpe ) =>
+        return tpe.toString();
+      case LPair( state, lab  ) =>
+        return "("+state.toString()+","+lab.toString()+")";
+      case _ =>
+        throw new ApplicationError("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/scalac/transformer/matching/LeftTracerInScala.scala b/sources/scala/tools/scalac/transformer/matching/LeftTracerInScala.scala
index 34fd084d7c..b13c7680b5 100644
--- a/sources/scala/tools/scalac/transformer/matching/LeftTracerInScala.scala
+++ b/sources/scala/tools/scalac/transformer/matching/LeftTracerInScala.scala
@@ -7,10 +7,7 @@ import scalac.util.Names;
 import java.util._ ;
 
 import scala.tools.util.Position;
-//import scalac.transformer.matching._ ;
-//import scalac.transformer.matching.CodeFactory ;
-import scalac.transformer.matching.DetWordAutom ;
-import scalac.transformer.matching.Label ;
+
 package scala.tools.scalac.transformer.matching {
 
 class LeftTracerInScala(dfa: DetWordAutom, elementType: Type, owner: Symbol, cf: CodeFactory, val selector: Tree )
@@ -144,14 +141,14 @@ extends TracerInScala( dfa, elementType, owner, cf ) {
 
     // default action (fail if there is none)
 
-    stateBody = code_delta( i, Label.DefaultLabel);
+    stateBody = code_delta( i, DefaultLabel());
 
     if( stateBody == null )
       stateBody = code_fail();
     // transitions of state i
 
-    val trans = (dfa.deltaq.asInstanceOf[Array[HashMap]])( i );
-    val labs = (dfa.deltaq( i ).asInstanceOf[HashMap]).keySet().iterator();
+    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];
diff --git a/sources/scala/tools/scalac/transformer/matching/NondetWordAutom.scala b/sources/scala/tools/scalac/transformer/matching/NondetWordAutom.scala
new file mode 100644
index 0000000000..d87cee40f2
--- /dev/null
+++ b/sources/scala/tools/scalac/transformer/matching/NondetWordAutom.scala
@@ -0,0 +1,527 @@
+
+
+import scalac.ApplicationError ;
+import scalac.ast.Tree ;
+import scalac.util.Name ;
+import Tree._ ;
+
+import java.util._ ;
+package scala.tools.scalac.transformer.matching {
+/** 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 )
+      throw new ApplicationError( "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/scalac/transformer/matching/Npair.scala b/sources/scala/tools/scalac/transformer/matching/Npair.scala
new file mode 100644
index 0000000000..41d09fa510
--- /dev/null
+++ b/sources/scala/tools/scalac/transformer/matching/Npair.scala
@@ -0,0 +1,61 @@
+package scala.tools.scalac.transformer.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 );
+	return "<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/scalac/transformer/matching/RightTracerInScala.scala b/sources/scala/tools/scalac/transformer/matching/RightTracerInScala.scala
index 74d804db12..08a395225d 100644
--- a/sources/scala/tools/scalac/transformer/matching/RightTracerInScala.scala
+++ b/sources/scala/tools/scalac/transformer/matching/RightTracerInScala.scala
@@ -15,10 +15,6 @@ import scalac.util.Names ;
 
 import scala.tools.util.Position;
 
-//import scalac.transformer.matching.CodeFactory ;
-import scalac.transformer.matching.DetWordAutom ;
-import scalac.transformer.matching.Label ;
-
 package scala.tools.scalac.transformer.matching {
 
   /** translate right tracer to code
@@ -170,7 +166,7 @@ extends TracerInScala( dfa, elementType, owner, cf )  {
      */
   def code_state0_NEW(): Tree =  { // careful, map Int to Int
 
-    val hmap = dfa.deltaq( 0 ).asInstanceOf[HashMap]; // all the initial states
+    val hmap = dfa.deltaq( 0 ); // all the initial states
 
     var i = 0;
     val n = hmap.keySet().size(); // all transitions defined
@@ -209,7 +205,7 @@ extends TracerInScala( dfa, elementType, owner, cf )  {
 
   override def currentMatches(label: Label): Tree = {
     label.match {
-      case Label.Pair( target, theLab ) =>
+      case LPair( target, theLab ) =>
         cf.Equals( gen.mkIntLit( cf.pos, target.intValue() ),
                          current() );
       case _ => throw new ApplicationError("expected Pair label");
@@ -218,11 +214,11 @@ extends TracerInScala( dfa, elementType, owner, cf )  {
 
 
   override def code_state_NEW(i: Int): Tree = { // precondition i != 0
-    var stateBody = code_delta( i, Label.DefaultLabel );
+    var stateBody = code_delta( i, DefaultLabel() );
     if( stateBody == null ) {
       stateBody = code_error();
     }
-    val trans = dfa.deltaq.asInstanceOf[Array[HashMap]]( i );
+    val trans = dfa.deltaq( i );
     val tmapTag = new TreeMap();
     val tmapBody = new TreeMap();
     var  j = 0;
@@ -234,7 +230,7 @@ extends TracerInScala( dfa, elementType, owner, cf )  {
 
       if( action != null ) {
         val J = new Integer( j );
-        tmapTag.put( label.asInstanceOf[Label.Pair].state, J );
+        tmapTag.put( label.asInstanceOf[LPair].state, J );
         tmapBody.put( J, action );
 
         stateBody = gen.If( currentMatches( label.asInstanceOf[Label] ),
@@ -363,7 +359,7 @@ extends TracerInScala( dfa, elementType, owner, cf )  {
    *  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 ).asInstanceOf[HashMap];
+    val hmap    = dfa.deltaq( i );
     val ntarget =  hmap.get( label ).asInstanceOf[Integer];
     var algMatchTree: Tree = null;
     if( ntarget == null )
@@ -372,15 +368,15 @@ extends TracerInScala( dfa, elementType, owner, cf )  {
     //System.out.println("delta("+i+","+label+")" );
     var  theLab: Label = null;
     label.match {
-      case Label.Pair( state, lab2 )=>
+      case LPair ( state, lab2 )=>
         //assert ntarget == state;
         theLab = lab2;
       lab2.match {
-        case Label.TreeLabel( pat ) =>
+        case TreeLabel( pat ) =>
           algMatchTree = _cur_match( pat );
         case _ =>
       }
-      case Label.DefaultLabel =>
+      case DefaultLabel() =>
         throw new ApplicationError(); // should not happen
     }
     //assert dfa.qbinders != null : "qbinders ?";
diff --git a/sources/scala/tools/scalac/transformer/matching/SequenceMatcher.scala b/sources/scala/tools/scalac/transformer/matching/SequenceMatcher.scala
index a9e43e211b..fbce115eea 100644
--- a/sources/scala/tools/scalac/transformer/matching/SequenceMatcher.scala
+++ b/sources/scala/tools/scalac/transformer/matching/SequenceMatcher.scala
@@ -12,13 +12,6 @@ import scalac.symtab._ ;
 import java.util._ ;
 
 import scala.tools.util.Position;
-//import scalac.transformer.matching.PatternTool;
-
-import scalac.transformer.matching.{BerrySethi, BindingBerrySethi};
-//import scalac.transformer.matching.CodeFactory;
-import scalac.transformer.matching.DetWordAutom;
-import scalac.transformer.matching.Label;
-import scalac.transformer.matching.NondetWordAutom;
 
 package scala.tools.scalac.transformer.matching {
 /** constructs a matcher for a sequence pattern. plays two roles in
@@ -29,6 +22,7 @@ package scala.tools.scalac.transformer.matching {
 
 class SequenceMatcher(unit: CompilationUnit) extends PatternTool(unit) {
 
+//  Console.println("CONSTR SEQUENCEMATCHER");
     final val IGNORED = new Integer(42);
 
     var cf: CodeFactory = _;
@@ -42,7 +36,7 @@ class SequenceMatcher(unit: CompilationUnit) extends PatternTool(unit) {
     def collectNfaVariables(nfa: NondetWordAutom): Set = {
       val seqVars = new HashSet();
       var j = 0;
-      while(j < nfa.nstates()) {
+      while(j < nfa.nstates) {
         if( nfa.qbinders( j ) != null )
           seqVars.addAll( nfa.qbinders( j ) );
         j = j + 1
diff --git a/sources/scala/tools/scalac/transformer/matching/StateSetComparator.scala b/sources/scala/tools/scalac/transformer/matching/StateSetComparator.scala
new file mode 100644
index 0000000000..c57e9c8f74
--- /dev/null
+++ b/sources/scala/tools/scalac/transformer/matching/StateSetComparator.scala
@@ -0,0 +1,34 @@
+package scala.tools.scalac.transformer.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;
+  }
+}
diff --git a/sources/scala/tools/scalac/transformer/matching/TracerInScala.scala b/sources/scala/tools/scalac/transformer/matching/TracerInScala.scala
index 79a573c62a..5838ed7991 100644
--- a/sources/scala/tools/scalac/transformer/matching/TracerInScala.scala
+++ b/sources/scala/tools/scalac/transformer/matching/TracerInScala.scala
@@ -1,8 +1,6 @@
 import scalac.ast.Tree;
 import scalac.symtab.Symbol;
 import scalac.symtab.Type;
-//import scalac.transformer.matching.CodeFactory ;
-import scalac.transformer.matching.DetWordAutom ;
 
 package scala.tools.scalac.transformer.matching {
 /** @todo: factor common things of LeftTracerInScala and RightTracerInScala
diff --git a/sources/scala/tools/scalac/transformer/matching/WordAutomInScala.scala b/sources/scala/tools/scalac/transformer/matching/WordAutomInScala.scala
index 2ce7ddb3f1..c04972af37 100644
--- a/sources/scala/tools/scalac/transformer/matching/WordAutomInScala.scala
+++ b/sources/scala/tools/scalac/transformer/matching/WordAutomInScala.scala
@@ -16,15 +16,11 @@ import scalac.ast.TreeGen;
 import scalac.symtab.Type;
 import scalac.symtab.Symbol;
 import scalac.symtab.Modifiers; // test
-//import scalac.typechecker.*;
 import Tree._;
 
 import java.util._;
 import scala.tools.scalac.util.NewArray;
 
-//import scalac.transformer.matching.CodeFactory;
-import scalac.transformer.matching.DetWordAutom;
-import scalac.transformer.matching.Label;
 import scalac.util.Names;
 
 package scala.tools.scalac.transformer.matching {
@@ -160,7 +156,7 @@ package scala.tools.scalac.transformer.matching {
 
       if (target == null)
         label.match  {
-          case Label.DefaultLabel =>
+          case DefaultLabel() =>
             code_error(); // this may not happen !
           case _ =>
             null; // not good