automata stuff for pattern matching

6 files changed, 2217 insertions, 0 deletions

diff --git a/sources/scalac/transformer/matching/BerrySethi.java b/sources/scalac/transformer/matching/BerrySethi.java
new file mode 100644
index 0000000000..e502c75c7c
--- /dev/null
+++ b/sources/scalac/transformer/matching/BerrySethi.java
@@ -0,0 +1,642 @@
+package scalac.transformer.matching ;
+
+import scalac.ApplicationError ;
+import scalac.ast.Tree ;
+import scalac.util.Name ;
+import Tree.* ;
+
+import java.util.* ;
+
+//import scala.compiler.printer.TextTreePrinter ;
+//import scala.compiler.printer.XMLAutomPrinter ;
+
+/** a Berry-Sethi style construction for nfas.
+ *  this class plays is the "Builder" for the "Director" class WordRecognizer.
+ */
+
+class BerrySethi {
+
+      boolean isStar( Name n ) {
+            String s = n.toString();
+            return (s.indexOf("$") != -1)
+                  &&(!s.startsWith("nest"));
+      }
+
+
+      HashSet labels;
+
+      int pos;
+      // maps a literal pattern to an Integer ( the position )
+      // is not *really* needed (postfix order determines position!)
+      HashMap posMap;    // pos:    Patterns   -> Positions
+      // don't let this fool you, only labelAt is a real, surjective mapping
+      HashMap labelAt; // chi:    Positions -> Obj
+
+      TreeSet globalFirst;
+
+      // results which hold all info for the NondetWordAutomaton
+
+      HashMap follow;    // follow: Positions -> Set[Positions]
+
+
+      // Unit test ?
+      boolean nullable( Tree pat ) {
+            //System.out.print("<nullable>");
+            //DEBUG.print( pat );
+            //System.out.println("</nullable>");
+            switch( pat ) {
+            case Apply(_, _):
+                  return false;
+            case Sequence( Tree[] trees ):
+                  return trees.length == 0;
+            case Subsequence( Tree[] trees ):
+                  return nullable( trees );
+            case Bind(Name n, Tree t):
+                  /*
+                     if( isStar( n ) ) // generated for star/plus(?)
+                     return true;
+                  */
+                  return nullable( t );
+            case Alternative(Tree[] choices):
+                  boolean result = false;
+                  for( int i = 0; i < choices.length && !result; i++ )
+                        result = result || nullable( choices[ i ] );
+                  return result;
+            default:
+                  return false;
+
+            }
+      }
+
+
+      /** returns true if a Sequence pattern matches the empty sequence
+       *  @param pat the sequence pattern.
+       */
+      boolean nullableSequence( Tree pat ) {
+            switch( pat ) {
+            case Sequence( Tree[] 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
+       */
+      boolean nullable( Tree[] pats ) {
+            boolean result = true;
+            for( int i = 0; i < pats.length && result; i++ )
+                  result = result && nullable( pats[ i ] );
+            return result;
+      }
+
+      /** computes first( alpha ) where alpha is a word regexp
+       */
+
+      TreeSet compFirst( Tree pat ) {
+            //System.out.print("<compFirst>");
+            //DEBUG.print( pat );
+            //System.out.println("</compFirst>");
+            switch( pat ) {
+            case Sequence( _ ):
+            case Typed(_,_):
+            case Select(_,_):
+            case Apply(_, _):
+                  TreeSet tmp = new TreeSet();
+                  tmp.add( (Integer) posMap.get( pat )); // singleton set
+                  return tmp;
+            case Literal( _ ):
+                  TreeSet tmp = new TreeSet();
+                  tmp.add( (Integer) posMap.get( pat )); // singleton set
+                  return tmp;
+            case Subsequence( Tree[] trees ):
+                  return compFirst( trees );
+            case Alternative( Tree[] trees ):
+                  TreeSet tmp = new TreeSet();
+                  for( int i = 0; i < trees.length; i++ ) {
+                        tmp.addAll( compFirst( trees[ i ] ));
+                  }
+                  return tmp;
+            case Bind( _, Tree tree ):
+                  return compFirst( tree );
+            case Ident( Name name ):
+                  //if( name != Name.fromString("_") )
+                  //    throw new ApplicationError("unexpected pattern");
+                  TreeSet tmp = new TreeSet();
+                  tmp.add( (Integer) posMap.get( pat )); // singleton set
+                  return tmp;
+            default:
+                  throw new ApplicationError("unexpected pattern");
+            }
+      }
+
+
+
+      /** computes last( alpha ) where alpha is a word regexp
+       */
+      TreeSet compLast( Tree pat ) {
+            //System.out.print("<last>");
+            //DEBUG.print( pat );
+            //System.out.println("</compLast>");
+            switch( pat ) {
+            case Sequence( _ ):
+            case Apply(_, _):
+                  TreeSet tmp = new TreeSet();
+                  tmp.add( (Integer) posMap.get( pat )); // singleton set
+                  return tmp;
+            case Literal( _ ):
+                  TreeSet tmp = new TreeSet();
+                  tmp.add( (Integer) posMap.get( pat )); // singleton set
+                  return tmp;
+            case Subsequence( Tree[] trees ):
+                  return compLast( trees );
+            case Alternative( Tree[] trees ):
+                  TreeSet tmp = new TreeSet();
+                  for( int i = 0; i < trees.length; i++ ) {
+                        tmp.addAll( compLast( trees ));
+                  }
+                  return tmp;
+            case Bind( _, Tree tree ):
+                  return compLast( tree );
+            default:
+                  throw new ApplicationError("unexpected pattern");
+            }
+      }
+
+
+      /** computes first(w) where w=alpha_1...alpha_n  are successors of a
+       *  sequence node
+       */
+      TreeSet compFirst( Tree[] pats ) {
+            if( pats.length == 0 )
+                  return new TreeSet();
+
+            int i = 0;
+            Tree tmp = pats[ i ];
+            TreeSet result = compFirst( tmp );
+            i++;
+            while( nullable(tmp) && (i < pats.length )) {
+                  tmp = pats[ i ];
+                  result.addAll( compFirst( tmp ));
+                  i++;
+            }
+            return result;
+      }
+
+      // Unit test ?
+
+      /** computes last(w) where w are successors of a sequence node
+       */
+      TreeSet compLast( Tree[] pats ) {
+            /*
+              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();
+
+            int i = pats.length - 1;
+            Tree tmp = pats[ i ];
+            TreeSet result = compLast( tmp );
+            i--;
+            while( nullable(tmp) && (i >= 0 )) {
+                  tmp = pats[ i ];
+                  result.addAll( compLast( tmp ));
+                  i++;
+            }
+            return result;
+      }
+
+      // starts from the right-to-left
+      // precondition: pos is final
+      //               pats are successor patterns of a Sequence node
+      TreeSet compFollow(Tree[] pats) {
+            TreeSet first = null;
+            this.recVars = new HashMap();
+            TreeSet fol = new TreeSet();
+            if( pats.length > 0 ) {//non-empty expr
+                  int i = pats.length;
+                  fol.add( new Integer( pos )); // don't modify pos !
+                  do {
+                        --i;
+                        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;
+      }
+
+      HashMap recVars;
+
+      /** returns the first set of an expression, setting the follow set along
+       *  the way
+       */
+      TreeSet compFollow1( TreeSet fol, Tree pat ) {
+            switch( pat ) {
+            case Subsequence(Tree[] trees):
+                  TreeSet first = null;
+                  int i = trees.length;
+                  if( i > 0 ) { // is nonempty
+                        do {
+                              --i;
+                              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(Tree[] choices):
+                  TreeSet first = new TreeSet();
+                  for( int i = choices.length - 1; i >= 0; --i ) {
+                        first.addAll( compFollow1( fol, choices[ i ] ));
+                  }
+                  return first;
+
+            case Bind( Name n, Tree t ):
+
+                  Integer p = (Integer) this.posMap.get( pat );
+
+                  TreeSet 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
+
+                  this.follow.put( p, fol.clone() );
+                  //System.out.println("Bind("+n+",...) first:"+first);
+                  //System.out.println("Bind("+n+",...) follow:"+fol);
+
+                  // continue to compute follow sets with adjusted fol
+                  return compFollow1( fol, t );
+
+            case Ident( Name n ):
+                  if ((pat.symbol() != null )
+                      && pat.symbol().isPrimaryConstructor()) {
+                        // same as Apply
+                        Integer pos = (Integer) this.posMap.get( pat );
+                        TreeSet tset = (TreeSet) fol.clone();
+                        this.follow.put( pos, tset );
+                        TreeSet first = new TreeSet();
+                        first.add( pos );
+                        return first;
+                  }
+
+                  if ( recVars.keySet().contains( pat.symbol() )) { // grammar
+                        TreeSet first = (TreeSet) recVars.get( pat.symbol() );
+                        TreeSet follow = ((TreeSet) fol.clone());
+                        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 _
+
+                  Integer pos = (Integer) this.posMap.get( pat );
+                  TreeSet tset = (TreeSet) fol.clone();
+                  this.follow.put( pos, tset );
+                  TreeSet first = new TreeSet();
+                  first.add( pos );
+                  //System.out.println("Ident("+n+",...) first:"+first);
+                  //System.out.println("Ident("+n+",...) follow:"+tset);
+                  return first;
+
+            case Sequence( _ ):
+            case Apply(_, _):
+            case Literal( _ ):
+            case Typed(_,_):
+            case Select(_,_):
+                  Integer pos = (Integer) this.posMap.get( pat );
+                  TreeSet tset = (TreeSet) fol.clone();
+                  this.follow.put( pos, tset );
+                  TreeSet first = new TreeSet();
+                  first.add( pos );
+                  return first;
+            default:
+                  throw new ApplicationError("unexpected pattern: "+pat.getClass());
+            }
+      }
+
+      /** called at the leaves of the regexp
+       */
+      void seenLabel( Tree pat, Integer i, Label label ) {
+            this.posMap.put( pat, i );
+            this.labelAt.put( i, label );
+            if( label != Label.DefaultLabel )
+                  this.labels.add( label );
+      }
+
+      /** overriden in BindingBerrySethi
+       */
+      void seenLabel( Tree pat, Label label ) {
+            seenLabel( pat, new Integer( ++pos ), label );
+      }
+
+      /** returns "Sethi-length" of a pattern, creating the set of position
+       *  along the way
+       */
+
+      Vector activeBinders;
+
+      // todo: replace global variable pos with acc
+      void traverse( Tree pat ) {
+            switch( pat ) {
+
+                  // (is tree automaton stuff, more than Berry-Sethi)
+            case Sequence( _ ):
+            case Apply( _, _ ):
+            case Typed( _, _ ):
+            case Select( _, _ ):
+                  Label label = new Label.TreeLabel( pat );
+                  seenLabel( pat, label ) ;
+
+                  return ;
+
+            case Literal( Object val ):
+                  Label label = new Label.SimpleLabel( (Literal) pat );
+                  seenLabel( pat, label ) ;
+
+                  return ;
+
+            case Subsequence( Tree[] trees ):
+                  for( int i = 0; i < trees.length; i++ ) {
+                        traverse( trees[ i ] );
+                  }
+                  return ;
+            case Alternative(Tree[] choices):
+                  for( int i = 0; i < choices.length; i++ ) {
+                        traverse( choices[ i ] );
+                  }
+                  return ;
+            case Bind(Name name, Tree body):
+                  recVars.put( pat.symbol(), Boolean.TRUE );
+                  if( !isStar( name ) )
+                        {
+                              activeBinders.add( pat.symbol() );
+                              traverse( body );
+                              activeBinders.remove( pat.symbol() );
+                        }
+                  else
+                        traverse( body );
+                  return ;
+
+            case Ident(Name name):
+                  if ((pat.symbol() != null )
+                      && pat.symbol().isPrimaryConstructor()) {
+                        // same as Apply
+                        Label label = new Label.TreeLabel( pat );
+                        seenLabel( pat, label ) ;
+
+                        return ;
+                  }
+
+
+                  if( recVars.get( pat.symbol() ) != null ) {
+                        return ;
+                  }
+                  // _ and variable x ( == x @ _ )
+                  Label label = Label.DefaultLabel;
+                  seenLabel( pat, label );
+
+                  return ;
+
+                  //else throw new ApplicationError("cannot handle this: "+name);
+                  //            case Apply( _, _ ):
+                  //throw new ApplicationError("cannot handle this");
+            default:
+                  throw new ApplicationError("this is not a pattern");
+            }
+      }
+
+
+      TreeMap finals;      // final states
+
+      //TreeSet initialsRev;      // final states
+
+      HashMap deltaq[];    // delta
+
+
+
+      Vector  defaultq[];  // default transitions
+
+
+      //HashMap deltaqRev[];    // delta of Rev
+      //Vector  defaultqRev[];  // default transitions of Rev
+
+
+ protected void makeTransition( Integer srcI, Integer destI, Label label ) {
+            int src  = srcI.intValue() ;
+            int dest = destI.intValue() ;
+            Vector arrows; //, revArrows;
+            //Label revLabel = new Label.Pair( srcI, label );
+            switch( label ) {
+            case DefaultLabel:
+                  arrows = defaultq[ src ];
+                  //revArrows = defaultqRev[ dest ];
+                  break;
+            default:
+                  arrows = (Vector) deltaq[ src ].get( label );
+                  if( arrows == null )
+                        deltaq[ src ].put( label,
+                                           arrows = new Vector() );
+                  /*
+                  revArrows = (Vector) deltaqRev[ dest ].get( revLabel );
+                  if( revArrows == null )
+                        deltaqRev[ dest ].put( revLabel,
+                                               revArrows = new Vector() );
+                  */
+            }
+            arrows.add( destI );
+            //revArrows.add( srcI );
+      }
+
+
+      TreeSet         initials;
+      //NondetWordAutom revNfa ;
+
+      protected void initialize( Tree[] subexpr ) {
+            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();
+            for( int i = 0; i < subexpr.length; i++ ) {
+                  traverse( subexpr[ i ] );
+                  assert ( activeBinders.isEmpty() );
+            }
+
+            this.initials = new TreeSet();
+            initials.add( new Integer( 0 ));
+
+      }
+
+      protected void initializeAutom() {
+
+            finals   = new TreeMap();        // final states
+            deltaq   = new HashMap[ pos ];   // delta
+            defaultq = new Vector[ pos ];    // default transitions
+
+            for( int j = 0; j < pos; j++ ) {
+                  deltaq[ j ] = new HashMap();
+                  defaultq[ j ] = new Vector();
+            }
+      }
+
+      void collectTransitions() {                 // make transitions
+
+            for( int j = 0; j < pos; j++ ) {
+
+                  Integer q = new Integer( j );
+
+                  //System.out.print( "--q="+q );
+                  //System.out.println(" labelAt:"+labelAt.get( q ));
+
+                  TreeSet fol = (TreeSet) this.follow.get( q );
+                  //assert fol != null;
+                  for( Iterator it = fol.iterator(); it.hasNext(); ) {
+                        Integer p = (Integer) it.next();
+                        //System.out.println( "--  -- p="+p );
+                        if( p.intValue() == pos ) {
+                              finals.put( q, finalTag );
+                        } else {
+                              makeTransition( new Integer(j), p,
+                                              (Label) labelAt.get( p ));
+                        }
+                  }
+            }
+
+      }
+
+      Integer finalTag;
+
+      public NondetWordAutom automatonFrom( Tree pat, Integer finalTag ) {
+
+            this.finalTag = finalTag;
+
+            //System.out.println( "enter automatonFrom(...)"); // UNIT TEST
+            //System.out.println( TextTreePrinter.toString(pat) );
+            /*DEBUG = new TextTreePrinter( System.out );
+            DEBUG.begin();
+            DEBUG.print( pat );
+            DEBUG.end();
+            */
+            //System.out.println( nullableSequence( pat )); // UNIT TEST
+            switch( pat ) {
+            case Sequence( Tree[] subexpr ):
+                  initialize( subexpr );
+
+
+                  // (1) compute first
+
+                  //globalFirst = compFirst( subexpr );
+                  //System.out.println(globalFirst);
+
+                  // (2) compute follow;
+                  ++pos;
+                  //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();
+
+
+                  //TreeSet initials = new TreeSet();
+                  //initials.add( new Integer( 0 ) );
+
+                  NondetWordAutom result =
+                        new NondetWordAutom(pos, // = nstates
+                                            labels,
+                                            initials,
+                                            finals,
+                                            (Object) deltaq,
+                                            (Object) 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);
+                  return result;                  //print();
+            }
+
+            throw new ApplicationError("expected a sequence pattern");
+      }
+
+      void print1() {
+            System.out.println("after sethi-style processing");
+            System.out.println("#positions:" + pos);
+            System.out.println("posMap:");
+
+            for( Iterator it = this.posMap.keySet().iterator();
+                 it.hasNext(); ) {
+                  Tree t = (Tree) it.next();
+                  switch(t) {
+                  case Literal( Object value ):
+                        System.out.print( "(" + t.toString() + " -> ");
+                        String s2 = ((Integer) posMap.get(t)).toString();
+                        System.out.print( s2 +") ");
+                  }
+            }
+            System.out.println("\nfollow: ");
+            for( int j = 1; j < pos; j++ ) {
+                  TreeSet fol = (TreeSet) this.follow.get(new Integer(j));
+                  System.out.print("("+j+" -> "+fol.toString()+") ");
+                  //debugPrint( fol );
+                  System.out.println();
+            }
+
+      }
+
+
+
+}
diff --git a/sources/scalac/transformer/matching/DetWordAutom.java b/sources/scalac/transformer/matching/DetWordAutom.java
new file mode 100644
index 0000000000..1f81e8c04d
--- /dev/null
+++ b/sources/scalac/transformer/matching/DetWordAutom.java
@@ -0,0 +1,892 @@
+package scalac.transformer.matching ;
+
+import scalac.ast.Tree ;
+import Tree.* ;
+
+import java.util.* ;
+
+import scalac.ApplicationError ;
+
+public class DetWordAutom extends FiniteAutom {
+
+      static final int FIRST = 0;
+      static final int LAST  = FIRST + 1;
+
+      static final int WHICH_LONGEST_MATCH = FIRST ;
+
+      // inherited from FiniteAutom:
+
+      // int nstates;   // number of states
+      // HashSet labels;// the alphabet
+      // TreeMap finals;
+
+      // HashMap deltaq[];
+      //Integer defaultq[];
+
+
+      // used only during determinization and debug printing
+      // Q -> (Label -> Q )
+      HashMap delta;
+      // Q -> Integer;
+      HashMap indexMap;
+
+      // Integer -> Q
+      HashMap invIndexMap;
+
+      // only not null if this is a right-transducer
+      public Vector qbinders[];
+
+      final static Integer NODEFAULT = new Integer( -1 );
+
+      public boolean isSink( int i ) {
+            return  (((HashMap[])deltaq)[ i ].keySet().isEmpty()
+                     && (defaultq != null )
+                     && (((Integer)defaultq( i )).intValue() == i));
+      }
+
+      public boolean hasDefault( int i ) {
+            return (Integer) defaultq( i ) != NODEFAULT;
+      }
+
+      void determinize( NondetWordAutom nfa ) {
+            //System.out.println("DetWordAutom:determinize");
+            //System.out.println("nfa:");nfa.print();
+            TreeSet states;// temp: Set[Set[Integer]]
+            HashMap deftrans; // Set[Integer] -> Int
+
+            HashMap trans; // always points to a mapping ( Label -> Q )
+            int 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)
+
+            TreeSet q0 = new TreeSet();
+            q0.addAll( nfa.initials ); /*new Integer( 0 )); */
+            states.add( q0 );
+
+            TreeSet empty = new TreeSet();
+            deftrans.put( q0, empty );
+            states.add( empty );
+            deftrans.put( empty, empty );
+
+            Stack rest = new Stack();
+            if( nfa.isFinal( 0 ) )
+                  this.finals.put( q0, nfa.finalTag( 0 ) );
+
+
+            rest.push( empty );
+            rest.push( q0 );
+            while( !rest.empty() ) {
+                  TreeSet P1 = (TreeSet) rest.pop();
+
+                  //System.out.println("states:"+ states);
+                  //System.out.println("P1:"+ P1);
+
+                  invIndexMap.put( new Integer( ix ), P1 );
+                  indexMap.put( P1, new Integer( ix++ ));
+                  delta.put( P1, trans = new HashMap());
+
+                  // labelled transitions
+
+                  for( Iterator it = labels.iterator(); it.hasNext(); ) {
+                        Object label = it.next();
+                        ////System.out.print( "Label: " + label +" ");
+                        // Qdest will contain all states reachable via `label'
+                        // from some nfa state in P1;
+                        TreeSet Qdest = nfa.getSide( P1, label );
+                        //System.out.println("Qdest:"+Qdest);
+                        if( !states.contains( Qdest ) ) {
+                              states.add( Qdest );
+                              ////System.out.print(" (added)" );
+                              rest.push( Qdest );
+                              ////System.out.print(" (pushed)");
+
+                              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);
+
+                  }
+
+                  // default transitions
+
+                  TreeSet defTarget = (TreeSet) nfa.defaultq( P1 );
+                  //System.out.println("defTarget:"+defTarget);
+                  deftrans.put( P1, defTarget );
+
+                  if( !states.contains( defTarget ) ) {
+                        states.add( defTarget );
+                        rest.push( defTarget );
+                        if( nfa.containsFinal( defTarget ) )
+                              this.finals.put( defTarget, nfa.finalTag( defTarget ));
+                  }
+            }
+
+            // <DEBUG>
+            // printBefore( states, deftrans );
+
+            // </DEBUG> do not call printBefore after this point
+            // //System.out.println("indexMap: "+indexMap);
+
+            this.nstates = states.size();
+            deltaq = new HashMap[ nstates ];
+            defaultq = new Integer[ nstates ];
+
+            // we replace Set[Set[Integer]] by its index and clean up
+
+            for( Iterator it = states.iterator(); it.hasNext(); ) {
+                  TreeSet state   = (TreeSet) it.next();
+                  Integer state_x = (Integer) indexMap.get( state );
+
+                  TreeSet defTarget  = (TreeSet) deftrans.get( state );
+                  Integer defTarget_x;
+                  if( defTarget != null ) {
+                        defTarget_x = (Integer) indexMap.get( defTarget );
+                        ////System.out.println("deftarget" + defTarget);
+                  } else
+                        defTarget_x = NODEFAULT;
+
+                  ////System.out.print(state.toString() + " --> " + state_x);
+                  //System.out.println(" deftarget " + defTarget + " --> "+defTarget_x);
+
+                  trans = (HashMap) delta.get( state );
+                  HashMap newTrans = new HashMap();
+                  for( Iterator labs = labels.iterator(); labs.hasNext() ;) {
+                        Object label = labs.next();
+                        TreeSet target   = (TreeSet) trans.get( label );
+                        Integer target_x;
+                        if( target != null ) {
+                              // //System.out.println("target :"+target);
+                              target_x = (Integer) indexMap.get( target );
+
+                              if( target_x.intValue() != defTarget_x.intValue() ) {
+                                    // replace target by target_x
+                                    // (use type-unawareness)
+                                    newTrans.put( label, target_x );
+                              }
+                              trans.remove( label );
+                        }
+
+                  }
+                  ((HashMap[])deltaq)[ state_x.intValue() ] = newTrans;
+                  ((Integer[])defaultq)[ state_x.intValue() ] = defTarget_x;
+
+                  delta.remove( state );
+                  deftrans.remove( state );
+
+            }
+
+            TreeMap oldfin = finals;
+            this.finals = new TreeMap();
+            for( Iterator it = oldfin.keySet().iterator(); it.hasNext(); ) {
+                  TreeSet state = (TreeSet) it.next();
+                  Integer state_x = (Integer) indexMap.get( state );
+                  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();
+
+            //minimize();
+      }
+
+      public DetWordAutom() {}
+
+      public boolean isDead( int state ) {
+            return state == nstates - 1; // by construction
+      }
+
+      public boolean isDead( Integer state ) {
+            return state.intValue() == nstates - 1; // by construction
+      }
+
+      /** determinization -- standard algorithm considering only
+       *                    reachable states
+       */
+      public DetWordAutom( NondetWordAutom nfa ) {
+            determinize( nfa );
+      }
+
+      /** for a set of nfa states (that must exist), returns its transitions
+       */
+      HashMap deltaq( TreeSet nset ) {
+            return (HashMap) deltaq( (Integer) indexMap.get( nset ) );
+      }
+
+
+      /** for a set of nfa states (that must exist), returns its transitions
+       */
+      Integer defaultq( TreeSet nset ) {
+            return (Integer) defaultq( (Integer) indexMap.get( nset ) );
+      }
+
+      /** returns target of the transition from state i with label label.
+       *  null if no such transition exists.
+       */
+      Integer delta( int i, Label label ) {
+            Integer target;
+            switch( label ) {
+            case DefaultLabel:
+                  if( !hasDefault( i ) )
+                        return null;
+                  return (Integer) defaultq( i ) ;
+            case SimpleLabel( _ ):
+            case TreeLabel( _ ):
+                  return (Integer) ((HashMap[])deltaq)[ i ].get( label ) ;
+                  /*case Pair( Integer state, Label lab ):
+                  return state;
+                  */
+            default:
+                  throw new ApplicationError("whut's this: label="+label+", class "+label.getClass());
+            }
+      }
+
+      Integer delta( Integer i, Label label ) {
+            return delta( i.intValue(), label );
+      }
+
+      /** should maybe in nfa, not here
+       */
+      protected static Integer smallestFinal( NondetWordAutom nfa,
+                                              TreeSet states ) {
+
+            int min = Integer.MAX_VALUE ;
+            for( Iterator it = states.iterator(); it.hasNext(); ) {
+                  Integer state = (Integer) it.next();
+                  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 Vector allSetsThatContain( Integer ndstate ) {
+            Vector v = new Vector();
+            for( Iterator it = indexMap.keySet().iterator(); it.hasNext(); ) {
+                  TreeSet ndstateSet = (TreeSet) it.next();
+                  if( ndstateSet.contains( ndstate ))
+                        v.add( ndstateSet );
+            }
+            return v;
+      }
+
+
+      protected void filterItOutQuoi( DetWordAutom dLeft,
+                                      Cartesian.Npair npTarget,
+                                      Label.Pair lab,
+                                      TreeMap nsrc ) {
+            Label theLabel  = lab.lab;
+            Integer ntarget = lab.state;
+
+            // e.g.[2,(3),4] --> 7
+            Integer dstate = (Integer) dLeft.indexMap.get( npTarget.nset );
+
+            // eg. 3 -> [3] [2,3]
+            Vector targets = dLeft.allSetsThatContain( ntarget );
+
+            ////System.out.println( targets+", of these " ) ;
+
+            // filter out those source states which arrive here...
+
+            for( Iterator su = targets.iterator(); su.hasNext(); ) {
+                  TreeSet nset   = (TreeSet) su.next();
+
+                  HashMap ddelta = (HashMap) dLeft.deltaq( nset );
+
+                  // ...  at THIS dstate
+                  if( (Integer) ddelta.get( theLabel ) == dstate ) {
+
+                        Cartesian.Npair np1 = new Cartesian.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 void filterItOutQuoiDefault( DetWordAutom dLeft,
+                                             Cartesian.Npair npTarget,
+                                             Integer nq,
+                                             TreeMap nsrc ) {
+
+
+            ////System.out.println( "npTarget = " + npTarget ) ;
+
+            Vector allSources = dLeft.allSetsThatContain( npTarget.nstate );
+
+            for( Iterator it = allSources.iterator(); it.hasNext(); ) {
+
+                  // e.g.[2,(3),4] --> 7
+                  //Integer dstate = (Integer) dLeft.indexMap.get( npTarget.nset );
+
+                  Integer dstate = (Integer) dLeft.indexMap.get( it.next() );
+
+                  //System.out.println( "dstate = " + dstate ) ;
+
+                  assert dstate != null;
+
+                  // eg. 3 -> [3] [2,3]
+                  Vector targets = dLeft.allSetsThatContain( nq );
+
+                  //System.out.println( "targets: " + targets ) ;
+
+                  // filter out those source states which arrive here...
+
+                  for( Iterator su = targets.iterator(); su.hasNext(); ) {
+                        TreeSet nset   = (TreeSet) su.next();
+
+                        Integer ddef = (Integer) dLeft.defaultq( nset );
+
+                        //System.out.println( "ddef ="+ddef );
+
+                        // ...  at THIS dstate
+                        if( ddef == dstate ) {
+
+                              Cartesian.Npair np1 = new Cartesian.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 static void addTransitionFLM( TreeMap nsrc, Cartesian.Npair np ) {
+            Cartesian.Npair np2 = (Cartesian.Npair) nsrc.get( np.nset );
+
+            // (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 static void addTransitionLLM( TreeMap nsrc, Cartesian.Npair np ) {
+            Cartesian.Npair np2 = (Cartesian.Npair) nsrc.get( np.nset );
+
+            // (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
+       */
+      public DetWordAutom( NondetWordAutom right,
+                           NondetWordAutom left,
+                           DetWordAutom    dLeft ) {
+
+            /* 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);
+            */
+
+            TreeSet visited_n = new TreeSet( new NpairComparator() );
+            Stack 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
+            for( Iterator it = dLeft.finals.keySet().iterator(); it.hasNext(); ) {
+                  Integer fstate  = (Integer) it.next();
+                  TreeSet nfstate = (TreeSet) invIndexMap.get( fstate );
+                  //System.out.print( "final state:"+fstate);
+                  //System.out.print( " correspond to set of states:"+ nfstate );
+
+                  Integer min_ndstate = smallestFinal( left, nfstate );
+
+                  Cartesian.Npair npair = new Cartesian.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 );
+                  }
+            }
+
+            HashMap ratLab     = new HashMap(); // maps nset to label,HashMap
+            HashMap ratDelta   = new HashMap(); // maps nset to Vector[ NP ]targets
+
+            HashMap ratDefault = new HashMap(); // maps nset to NP (one target)
+
+            int ix = 1;
+            Stack ix_initial = (Stack) rest.clone();
+            TreeSet ix_final = new TreeSet( new NpairComparator() );;
+
+            TreeMap newIndexMap = new TreeMap( new NpairComparator() );
+
+            while( !rest.isEmpty() ) {
+
+                  Cartesian.Npair npair = (Cartesian.Npair) rest.pop();
+                  newIndexMap.put( npair, new Integer(ix));
+
+                  ratDelta.put( npair, new Vector() );
+
+                  if( npair.nset.contains( new Integer( 0 )) ) {
+                        ix_final.add( npair );
+                  }
+                  ix++;
+
+                  //System.out.println(" popped "+npair.toString( dLeft.indexMap ));
+
+                  ////System.out.print(" binders: ");
+                  ////System.out.print( right.qbinders[ npair.nstate.intValue() ] );
+
+                  HashMap delta = (HashMap) right.deltaq( npair.nstate );
+
+                  ////System.out.print(" we could have arrived : ");
+                  //search the delta for target invIndexMap
+
+                  HashMap labelToNset = new HashMap();
+                  HashMap labelToFrom = new HashMap();
+
+                  // maps nsets to the active nstates
+                  TreeMap nsrc = new TreeMap( new StateSetComparator() );
+
+                  // berry-sethi construction assures that
+                  //   there is only one label for outgoing transitions
+                  Label theLabel = null;
+
+                  // collect all transition possible in the DFA
+
+                  for( Iterator it = delta.keySet().iterator(); it.hasNext(); ) {
+
+                        Label.Pair   lab = (Label.Pair) it.next();
+
+                        // lab.state is the target in the NFA
+
+                        if( theLabel == null ) {
+                              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
+
+                  for( Iterator ut = nsrc.keySet().iterator(); ut.hasNext(); ) {
+                        TreeSet nset  = (TreeSet) ut.next();
+
+                        Cartesian.Npair np2 = (Cartesian.Npair) nsrc.get( nset );
+
+                        assert( np2 != null );
+                        ////System.out.println("target: n"+npair.nstate+" via: "+theLabel+" from "+ np2.toString( dLeft.indexMap ));// nset:"+nset+ " namely state n"+ dest);
+
+                        Vector v = (Vector) ratDelta.get( npair );
+
+                        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
+                  Vector defqs = (Vector) right.defaultq( npair.nstate );
+                  for( Iterator it = defqs.iterator(); it.hasNext(); ) {
+                        Integer nq = (Integer) it.next();
+                        //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 );
+
+                  for( Iterator ut = nsrc.keySet().iterator(); ut.hasNext(); ) {
+
+                        Cartesian.Npair np2 = (Cartesian.Npair) nsrc.get( ut.next() );
+
+                        Vector v = (Vector) ratDefault.get( npair );
+                        if( v == null )
+                              ratDefault.put( npair, v = new Vector() );
+                        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");
+            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;
+            HashMap dratDelta[] = new HashMap[ ix ];
+            qbinders  = new Vector[ ix ];
+            labels = new HashSet();
+            for( Iterator it = ratDelta.keySet().iterator(); it.hasNext(); ) {
+                  Cartesian.Npair np = (Cartesian.Npair) it.next();
+
+                  //System.out.print( "\nstate: "+np);
+                  TreeSet ndset = np.nset;
+                  Integer dstate = (Integer) newIndexMap.get( np );
+                  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 ) ) {
+                        Integer fin_ix = (Integer) newIndexMap.get( np );
+                        finals.put( fin_ix, new Integer( 0 ));
+                  }
+
+                  Label   lab   = (Label)  ratLab.get( np );
+                  Vector  v     = (Vector) ratDelta.get( np );
+
+                  HashMap ddelta = new HashMap();
+
+                  // v might be null if there are only default transitions
+                  if( v != null )
+                        for( Iterator it2 = v.iterator(); it2.hasNext() ; ) {
+
+                              Cartesian.Npair np2= (Cartesian.Npair) it2.next();
+                              //System.out.print( "("+lab+","+np2+") " );
+                              Integer ddestR = (Integer) newIndexMap.get( np2 );
+                              Integer ddest = (Integer) indexMap.get( np2.nset );
+                              assert ddest != null :
+                                    "no ddest for "
+                                    +np2.toString(dLeft.indexMap);
+
+                              Label.Pair newLab = new Label.Pair(ddest, lab);
+                              ddelta.put( newLab, ddestR );
+                              labels.add( newLab );
+
+                        }
+                  dratDelta[ dstate.intValue() ] = ddelta;
+
+            }
+
+            for( Iterator it = ratDefault.keySet().iterator(); it.hasNext(); ) {
+                  Cartesian.Npair np  = (Cartesian.Npair) it.next();
+                  Integer         dstate = (Integer) newIndexMap.get( np );
+
+                  //System.out.print("\nstate: "+np+" default trans: ");
+
+                  Vector v = (Vector) ratDefault.get( np );
+                  for( Iterator ut = v.iterator(); ut.hasNext(); ) {
+                        Cartesian.Npair np2  = (Cartesian.Npair) ut.next();
+                        Integer targetL      = (Integer) indexMap.get( np2.nset );
+                        Integer targetR      = (Integer) newIndexMap.get( np2 );
+
+                        Label defLab = new Label.Pair( targetL,
+                                                       Label.DefaultLabel );
+
+                        labels.add( defLab );
+                        //System.out.print( "("+defLab+","+np2+") " );
+
+                        HashMap d = dratDelta[ dstate.intValue() ];
+                        if( d == null )
+                              dratDelta[ dstate.intValue() ] = d = new HashMap();
+
+                        d.put( defLab, targetR );
+                  }
+            }
+
+            deltaq = dratDelta;
+
+            HashMap hmap = new HashMap();
+
+            // final states of left are initial states of right
+            // problem: still need to choose the one
+
+            while( !ix_initial.isEmpty() ) {
+                  Cartesian.Npair np = (Cartesian.Npair) ix_initial.pop();
+
+                  Integer i          = (Integer) newIndexMap.get( np ); //R-state
+                  Integer dtarget    = (Integer) indexMap.get( np.nset );// left-d-state
+
+                  hmap.put( dtarget, i );
+            }
+            ((HashMap[])deltaq)[ 0 ]  = hmap; // careful, this maps Int to Int
+
+            qbinders[ 0 ] = new Vector();
+            //((Vector[])defaultq)[ 0 ] = new Vector(); is null
+            printBeforeRAT( dratDelta );
+
+      }
+
+      void printBeforeRAT1( String str ) {
+            StringBuffer tmp = new StringBuffer( str );
+            for( int j = tmp.length(); j < 20; j++ ) {
+                  tmp.append(" ");
+            }
+            //System.out.print( tmp.toString() );
+      }
+
+      void printBeforeRAT( HashMap dratDelta[] ) {
+            //System.out.println();
+            printBeforeRAT1( "dratDelta" );
+            printBeforeRAT1( "[index]" );
+            //System.out.println();
+
+            for( int i = 0; i < dratDelta.length; i++ ) {
+                  if( isFinal( i ))
+                        printBeforeRAT1( "*"+i );
+                  else
+                        printBeforeRAT1( " "+i );
+
+                  //System.out.println( dratDelta[ i ] );
+            }
+      }
+
+      /** you may only call this before the set[set[...]] representation
+       *  gets flattened.
+       */
+      public void printBefore( TreeSet states, HashMap deftrans ) {
+            HashMap trans;
+            //System.out.println( states );
+            for( Iterator it = states.iterator(); it.hasNext(); ) {
+                  TreeSet state = (TreeSet) it.next();
+                  //System.out.print("state:"+state.toString()+" transitions ");
+                  trans = (HashMap) delta.get( state );
+                  for( Iterator labs = labels.iterator(); labs.hasNext() ;) {
+                        Object label = labs.next();
+                        TreeSet target = (TreeSet) trans.get( label );
+                        //System.out.print( "  (" + label.toString()
+                        //            + "," + target.toString()+")");
+                  }
+                  //System.out.print("default trans"+deftrans.get( state ));
+                  //System.out.println();
+            }
+            //System.out.println("final states:" + finals );
+      }
+
+
+      /*
+      public void minimize() { // TO DO
+            //System.out.println("minimization");
+            boolean mark[][] = new boolean[nstates][];
+            for( int i = 0; i < nstates; i++ ) {
+                  mark[i] = new boolean[nstates - i];
+                  for( int j = 0; j < (nstates - i); j++ )
+                        mark[i][j] = false;
+            }
+            debugPrint( mark );
+      }
+
+      protected void debugPrint( boolean mark[][] ) {
+            for( int i = 0; i < nstates; i++ ) {
+                  //System.out.print("[");
+                  for( int j = 0; j < nstates - i; j++ ) {
+                        //System.out.print(" "+mark[i][j]);
+                        if( mark[i][j] )
+                              //System.out.print(" ");
+                  }
+                  //System.out.println(" ]");
+            }
+      }
+
+      */
+
+      /*
+
+      public void createDeadState() {
+            assert dead == -1;
+            this.dead = this.nstates++;
+            Integer deadI = new Integer( dead );
+
+            HashMap odelta[] = ((HashMap[])deltaq);
+            deltaq = new HashMap[ this.nstates ];
+            System.arraycopy(odelta, 0, ((HashMap[])deltaq), 0, odelta.length);
+            HashMap trans = new HashMap();
+            ((HashMap[])deltaq)[ this.dead ] = trans;
+            for( Iterator labs = labels.iterator(); labs.hasNext(); ) {
+                  trans.put( labels, deadI );
+            }
+            //System.out.println("createDeadState, new dead state:"+dead);
+      }
+
+
+
+      // adjusts the alphabet of this automaton
+
+      public void addLabels( HashSet labels ) {
+
+            for(Iterator it = labels.iterator(); it.hasNext(); ) {
+                  Object label = it.next();
+                  if( this.labels.add( label )) { // new
+                        // adjust all transitions
+
+                        if( this.dead == -1 )
+                              createDeadState();
+
+                        Integer deadI = new Integer( this.dead );
+
+                        for( int i = 0; i < this.nstates; i++ ) {
+                              ((HashMap[])deltaq)[ i ].put( label, deadI );
+                        }
+                  }
+            }
+      }
+      */
+
+      // wishlist for jaco: why does Cartesian have to be static ?
+      // if not, error "inner classes must not have static members"
+
+      /** cartesian
+       */
+
+      static class Cartesian {
+            /** Int x TreeSet[ Int ]
+             */
+            case Npair(Integer nstate, TreeSet nset);
+
+            public boolean equals( Object that ) {
+                  if( !(that instanceof Cartesian ))
+                        return false;
+                  switch( this ) {
+                  case Npair( Integer nstate, TreeSet nset ):
+                        switch((Cartesian) that) {
+                        case Npair( Integer _nstate, TreeSet _nset ):
+                              return ((nstate == _nstate)
+                                      &&( nset == _nset ));
+                        }
+                  }
+                  return false;
+            }
+
+            public String toString() {
+                  switch( this ) {
+                  case Npair( Integer nstate, TreeSet nset ):
+                        //Integer dstate = (Integer) indexMap.get( nset );
+                        return "<n"+nstate.toString()+" in "+nset /*+" = d"+dstate*/+">";
+                  }
+                  return null;
+            }
+
+            public String toString( HashMap indexMap ) {
+                  //assert indexMap != null;
+                  switch( this ) {
+                  case Npair( Integer nstate, TreeSet nset ):
+                        assert nstate!=null;
+                        Integer dstate = (Integer) indexMap.get( nset );
+                        return "<n"+nstate.toString()+" in "+nset +" = d"+dstate +">";
+                  }
+                  return null;
+            }
+
+
+      }
+
+      static class NpairComparator extends StateSetComparator {
+            public int compare( Object o1, Object o2 ) {
+                  if(( o1 instanceof Cartesian.Npair )&&
+                     ( o2 instanceof Cartesian.Npair ))
+                        switch((Cartesian) o1) {
+                        case Npair( Integer nstate, TreeSet nset ):
+                              switch( (Cartesian) o2 ) {
+                              case Npair( Integer _nstate, TreeSet _nset ):
+                                    int res = nstate.compareTo( _nstate );
+
+                                    ////System.out.println("nstate"+nstate+" <> _nstate "+ _nstate+" res"+res);
+                                    if( res != 0 )
+                                          return res;
+                                    else
+                                          return super.compare( nset, _nset );
+                              }
+                        }
+                  throw new ApplicationError( "illegal arg. to compare. "
+                                              +o1.getClass()+" "+o2.getClass());
+            }
+      }
+
+}
diff --git a/sources/scalac/transformer/matching/FiniteAutom.java b/sources/scalac/transformer/matching/FiniteAutom.java
new file mode 100644
index 0000000000..f075e4aa93
--- /dev/null
+++ b/sources/scalac/transformer/matching/FiniteAutom.java
@@ -0,0 +1,120 @@
+package scalac.transformer.matching ;
+
+import java.util.Iterator ;
+import java.util.HashSet ;
+import java.util.HashMap ;
+import java.util.TreeSet ;
+import java.util.TreeMap ;
+
+public abstract class FiniteAutom {
+
+      //final static Integer FINTAG = new Integer(0);
+
+      /** number of states */
+      protected int nstates;
+
+      /** the 'alphabet' */
+      protected HashSet labels;
+
+      /** the set of final states, here as a TreeMap */
+      protected TreeMap finals;
+
+      /** 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' } )
+       */
+
+      public Object deltaq;
+
+      public Object defaultq; // this gives the default transitions
+
+      //protected HashMap deltaq[];
+
+      // --- accessor methods
+
+      /** returns number of states
+       */
+      public int nstates() {
+            return nstates;
+      }
+
+      /** returns the labels
+       */
+      public HashSet labels() {
+            return labels;
+      }
+
+      /** returns the transitions
+       */
+      public Object deltaq( int state ) {
+            return ((Object []) deltaq)[ state ];
+      }
+
+      /** returns the transitions
+       */
+      public Object deltaq( Integer state ) {
+            return ((Object []) deltaq)[ state.intValue() ];
+      }
+
+
+      /** returns the transitions
+       */
+      public Object defaultq( int state ) {
+            return ((Object []) defaultq)[ state ];
+      }
+
+      /** returns the transitions
+       */
+      public Object defaultq( Integer state ) {
+            return ((Object []) defaultq)[ state.intValue() ];
+      }
+
+
+      /** returns true if the state is final
+       */
+      public boolean isFinal( int state ) {
+            return ((finals != null)
+                    && (finals.get( new Integer( state )) != null));
+      }
+
+      /** returns true if the state is final
+       */
+      public boolean isFinal( Integer state ) {
+            return ((finals != null) && finals.containsKey( state ));
+      }
+
+      /** returns true if the state is final
+       */
+      public Integer finalTag( Integer state ) {
+            return (Integer) finals.get( state );
+      }
+
+
+      public Integer finalTag( int state ) {
+            return (Integer) finals.get( new Integer (state ));
+      }
+
+      /** returns true if the set of states contains at least one final state
+       */
+      boolean containsFinal( TreeSet Q ) {
+            for( Iterator it = Q.iterator(); it.hasNext(); ) {
+                  if( isFinal( (Integer) it.next()))
+                        return true;
+            }
+            return false;
+      }
+
+
+      /** returns true if there are no finite states
+       */
+      public boolean isEmpty() {
+            return finals.isEmpty();
+      }
+
+
+}
diff --git a/sources/scalac/transformer/matching/Label.java b/sources/scalac/transformer/matching/Label.java
new file mode 100644
index 0000000000..389139da0a
--- /dev/null
+++ b/sources/scalac/transformer/matching/Label.java
@@ -0,0 +1,120 @@
+package scalac.transformer.matching ;
+
+import scalac.ast.Tree ;
+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
+ */
+
+public class Label {
+
+
+      public case DefaultLabel;
+      public case SimpleLabel( Literal lit );
+      public case TreeLabel( Tree pat ); // Apply, Sequence
+
+      public case TypeLabel( Type tpe ); // Apply, Sequence
+
+      public case Pair( Integer state, Label lab );
+
+      //public case RLabel( Object rstate, Label lab, Symbol vars[] );
+
+      public int hashCode() {
+            switch( this ) {
+            case DefaultLabel:
+                  return 0;
+            case SimpleLabel( Literal lit ):
+                  return lit.value.hashCode();
+            case TreeLabel( Tree pat ):
+                  return pat.hashCode();
+            case TypeLabel( Type type ):
+                  return type.hashCode();
+            default:
+                  return super.hashCode();
+            }
+      }
+
+      public boolean equals( Object o ) {
+            if( !(o instanceof Label ))
+                  return false;
+            Label oL = (Label) o;
+            //System.out.print(this + " equals " + oL);
+            switch( this ) {
+            case DefaultLabel:
+                  switch( oL ) {
+                  case DefaultLabel:
+                        return true;
+                  } //
+                  break;
+            case SimpleLabel( Literal lit ):
+                  switch( oL ) {
+                  case SimpleLabel( Literal lit2 ):
+                        return /*(lit.kind == lit2.kind)
+				 && */lit.value.equals( lit2.value );
+                  }
+                  break;
+            case TreeLabel( Tree pat ):
+                  switch( oL ) {
+                  case TreeLabel( Tree pat2):
+                        return pat == pat2;
+                  }
+                  break ;
+            case TypeLabel( Type tpe ):
+                  switch( oL ) {
+                  case TypeLabel( Type tpe2):
+                        return tpe.equals( tpe2 );
+                  }
+                  break ;
+            case Pair( Integer state, Label lab ):
+                  switch( oL ) {
+                  case Pair(  Integer state2, Label lab2 ):
+                        return  state.equals( state2 )
+                                 && lab.equals( lab2 ) ;
+                  }
+                  break;
+            }
+            return false;
+      }
+
+
+      public String toString2() {
+            String ext = System.getProperty("extendedMatching");
+            if(( ext != null )
+               && ext.equals( "true" )) {
+                  switch( this ) {
+                  case DefaultLabel:
+                        return "<>:p"+p;
+                  case SimpleLabel( Literal lit ):
+                        return lit.toString()+":p"+p;
+                  case TreeLabel( Tree pat ):
+                        return pat.type()+":p"+p;
+
+                  }
+            }
+            throw new scalac.ApplicationError
+                  ("this never happens");
+      }
+
+      public String toString() {
+
+            switch( this ) {
+            case DefaultLabel:
+                  return "<>";
+            case SimpleLabel( Literal lit):
+                  return lit.toString();
+            case TreeLabel( Tree pat):
+                  return pat.toString();
+            case TypeLabel( Type tpe ):
+                  return tpe.toString();
+            case Pair( Integer state, Label lab  ):
+                  return "("+state.toString()+","+lab.toString()+")";
+            }
+            throw new scalac.ApplicationError("this never happens");
+      }
+
+      int p = -1; // tree state - only needed for extended matching
+
+
+}
diff --git a/sources/scalac/transformer/matching/NondetWordAutom.java b/sources/scalac/transformer/matching/NondetWordAutom.java
new file mode 100644
index 0000000000..f4a7458f52
--- /dev/null
+++ b/sources/scalac/transformer/matching/NondetWordAutom.java
@@ -0,0 +1,409 @@
+package scalac.transformer.matching ;
+
+import scalac.ApplicationError ;
+import scalac.ast.Tree ;
+import scalac.util.Name ;
+import Tree.* ;
+
+import java.util.* ;
+
+//import scala.compiler.printer.TextTreePrinter ;
+
+/** a nondeterministic word automaton.
+ *  states are represented (implicitly) as Integer objects.
+ */
+
+public class NondetWordAutom extends FiniteAutom {
+
+      // inherited from FiniteAutom
+
+      // set of *distinct* objects that may label transitions
+      // see Object.hashCode() to see why this works
+
+      //HashSet labels;
+      //TreeMap finals;
+
+      TreeSet initials; // ? need this ?
+      // ---
+
+      // Object deltaq -->
+      // HashMap deltaq[]; // this gives the transitions of q;
+
+      boolean leftTrans;
+      boolean rightTrans;
+
+      /** 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.
+       */
+      public boolean producesRun() {
+            return leftTrans;
+      }
+
+      public boolean consumesRun() {
+            return rightTrans;
+      }
+
+      public boolean initial( Integer i ) {
+            return initials.contains( i );
+      }
+      public Vector qbinders[];
+
+      /** returns all states accessible from Qsrc via label.
+       *  used by class DetWordAutomaton.
+       */
+      TreeSet getSide ( TreeSet Qsrc, Object label ) {
+            TreeSet Qdest = new TreeSet();
+            for( Iterator it = Qsrc.iterator(); it.hasNext(); ) {
+                  // state
+                  int q1 = ((Integer) it.next()).intValue();
+                  Vector ps = (Vector) ((HashMap[])deltaq)[ q1 ].get( label );
+
+                  //System.out.println( "q1 "+q1+" targ:"+ps.toString() );
+                  if( ps!=null )
+                        Qdest.addAll( ps );
+
+                  Qdest.addAll((Vector) defaultq( q1 ));
+            }
+            return Qdest;
+      }
+
+      /** returns the transitions
+       */
+      public Object defaultq( Set P1 ) {
+            TreeSet defTarget = new TreeSet();
+            for( Iterator p1 = P1.iterator(); p1.hasNext(); ) {
+                  int q1 = ((Integer) p1.next()).intValue();
+                  //System.out.println("   q1:"+q1+ " defa: "+defaultq( q1 ));
+                  defTarget.addAll( (Vector) defaultq( q1 ));
+            }
+            return defTarget;
+      }
+
+
+      /** first match policy: among several final states, the smallest one is
+       *   chosen. used by class DetWordAutomaton
+       */
+      Integer finalTag( Set Q ) {
+
+            int min = Integer.MAX_VALUE ;
+
+            for( Iterator it = Q.iterator(); it.hasNext(); ) {
+                  Integer state = (Integer) it.next();
+                  Integer tag = (Integer) finals.get( state );
+                  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 );
+      }
+
+      /*
+      protected 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
+      protected Map mapmap(Map src,
+                             int offset,
+                             Map dest,
+                             boolean mapkeys,
+                             boolean mapvals) {
+            for(Iterator it = src.keySet().iterator(); it.hasNext(); ) {
+                  Object key = it.next();
+                  Object val = src.get( key );
+                  if( mapkeys ) key = new Integer( ((Integer)key).intValue()
+                                                   + offset );
+                  if( mapvals ) val = vmap( offset, (Vector) val ) ;
+                                      /* new Integer( ((Integer)val).intValue()
+                                                   + offset );
+                                      */
+                  dest.put( key, val );
+            }
+            return dest;
+      }
+
+      protected static Vector vmap(int offs, Vector v ) {
+            if( v == null )
+                  return null;
+            Vector res = new Vector( v.size() );
+
+            for(Iterator it = v.iterator(); it.hasNext(); ) {
+                  Integer item = (Integer) it.next();
+                  res.add( new Integer( item.intValue() + offs ));
+            }
+            return res;
+
+      }
+
+      /*
+      protected 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.
+       */
+      protected void relocate( int      offset,
+                               TreeMap  _finals,
+                               HashMap  _deltaq[],
+                               Vector   _defaultq[],
+                               Vector   _qbinders[] ) {
+
+            mapmap( finals, offset, _finals, true, false);
+
+            for( int i = 0; i < this.nstates; i++ ) {
+
+                  _deltaq  [ i + offset ] = (HashMap) mapmap( ((HashMap[])deltaq)[ i ],
+                                                    offset, new HashMap(), false, true);
+
+                  _defaultq[ i + offset ] = vmap( offset, ((Vector[])defaultq)[ i ]);
+
+            }
+            if ((_qbinders != null) &&( qbinders != null ))
+                  for( int i = 0; i < this.nstates; i++ ) {
+                        //System.out.println("hallo"+qbinders);
+                        //System.out.println("qbinders[ i ] :"+qbinders[ i ]);
+                        assert _qbinders != null;
+                        //System.out.println("_qbinders :"+_qbinders);
+
+                        _qbinders[ i + offset ] = qbinders[ i ];
+                  }
+      }
+
+      /** if there is more than one initial state, a new initial state
+       *  is created, with index 0
+       */
+      protected void normalize( TreeSet initials, boolean reloc ) {
+            //if( initials.size() == 1 )
+            //      return;
+
+            HashMap idelta   = new HashMap();
+            TreeSet idefault = new TreeSet();
+
+            Integer q0 = new Integer( 0 );
+
+            for( Iterator it = initials.iterator(); it.hasNext(); ) {
+
+                  Integer ostate = (Integer) it.next();
+
+                  Integer finTag = (Integer) finals.get( ostate ) ;
+                  if(( finTag != null ) && ( finals.get( q0 )  == null))
+                        finals.put( q0, finTag );
+
+
+                  HashMap tmp = (HashMap) deltaq( ostate );
+
+                  if( reloc )
+                        tmp = (HashMap) mapmap( tmp, 1, new HashMap(), false, true );
+
+                  for( Iterator labs = tmp.keySet().iterator(); labs.hasNext(); ) {
+                        Label  lab    = (Label) labs.next();
+                        Vector itarget = (Vector) idelta.get( lab );
+                        if( itarget == null )
+                              idelta.put( lab, itarget = new Vector());
+                        Vector otarget = (Vector) tmp.get( lab );
+                        itarget.addAll( otarget );
+                  }
+                  //System.out.println( "normalize:defaultq[ "+ostate+" ] "+((Vector[]) defaultq) [ ostate.intValue() ]);
+                  if( defaultq( ostate ) != null )
+                        idefault.addAll( (Vector) defaultq( ostate )  );
+            }
+
+            if( reloc ) {
+                  int m = 1 + this.nstates;
+                  TreeMap _finals     = new TreeMap();
+                  HashMap _deltaq[]   = new HashMap[ m ];
+                  Vector  _defaultq[] = new Vector[ m ];
+                  Vector  _qbinders[] = null;
+
+                  if( qbinders != null )
+                        _qbinders = new Vector[ m ];
+
+                  relocate( 1, _finals, _deltaq, _defaultq, _qbinders );
+
+                  this.nstates  = m;
+                  this.finals   = _finals;
+                  this.deltaq   = _deltaq;
+                  this.defaultq = _defaultq;
+                  this.qbinders = _qbinders;
+            }
+
+            ((HashMap[])this.deltaq)  [ 0 ] = idelta;
+            //System.out.println("normalize:deltaq[ 0 ]"+ idelta );
+            ((Vector[])this.defaultq) [ 0 ] = new Vector( idefault );
+
+            //System.out.println("normalize:defaultq[ 0 ]"+ idefault );
+
+            this.initials = new TreeSet();
+            this.initials.add( q0 );
+      }
+
+
+      /** needed for NondetWordSwitch
+       */
+      NondetWordAutom() {}
+
+      /** called from Berry-Sethi construction.
+       */
+
+      public NondetWordAutom(int nstates,
+                             HashSet labels,
+                             TreeSet initials,
+                             TreeMap finals,
+                             Object deltaq,
+                             Object defaultq,
+                             Object qbinders) {
+            this.nstates = nstates;
+            this.labels = labels;
+            this.initials = initials;
+            this.finals = finals;
+            this.deltaq = deltaq;
+            this.defaultq = defaultq;
+            this.qbinders = (Vector[])qbinders;
+            //print();
+            //System.exit(0);
+      }
+
+
+
+      int offset[]; // only used if constructed from multiple
+
+      protected void collectLabels( NondetWordAutom nfa[] ) {
+            this.labels = new HashSet();
+            for( int i = 0; i < nfa.length; i++ ) {
+                  this.labels.addAll( nfa[ i ].labels );
+            }
+      }
+
+      protected void collectOffsets( NondetWordAutom nfa[] ) {
+            this.offset = new int[ nfa.length + 1 ];
+            offset[ 0 ] = 1; // we have a new initial state
+            for( int i = 0; i < nfa.length ; i++ )
+                  offset[ i + 1 ] = nfa[ i ].nstates + offset[ i ];
+
+      }
+
+      /** collapses several normalized NondetWordAutom objects into one.
+       */
+
+      public NondetWordAutom( NondetWordAutom nfa[] ) {
+
+
+            //this.m
+            int m = nfa.length;
+            //System.out.println("enter NondetWordSwitch, "
+            //                   +"combining " + m + " automata");
+
+            collectLabels( nfa );
+            collectOffsets( nfa );
+
+            this.nstates = offset[ nfa.length ]; //m - 1 ] + nfa[ m - 1 ].nstates;
+
+
+            this.finals = new TreeMap();
+
+            this.qbinders = new Vector[ nstates ];
+
+            // new initial state gets all transitions from all initial states
+
+            this.deltaq        = new HashMap[ nstates ];
+            this.defaultq      = new Vector [ nstates ];
+
+            //TreeSet defaultqSet = new TreeSet();
+            ((HashMap [])deltaq)[ 0 ] = new HashMap(); // 0 = our new initial state
+
+            TreeSet initials = new TreeSet();
+
+
+            for( int i = 0; i < m; i++ ) {
+                  //System.out.println("i (current NFA):"+i);
+
+                  NondetWordAutom n = nfa[ i ];
+
+                  int offs = offset[ i ];
+
+                  initials.add( new Integer( offs ));
+
+                  n.relocate( offs,
+                              this.finals,
+                              (HashMap[]) this.deltaq,
+                              (Vector[])  this.defaultq,
+                              (Vector[])  this.qbinders );
+            }
+
+            normalize( initials, false );
+
+      }
+
+
+
+
+      public void print() {
+
+            System.out.print("NFA on labels "+ this.labels);
+
+            if( offset != null ) {
+                  System.out.print("offset");
+                  for( int k = 0; k < offset.length; k++ ) {
+                        if( k > 0)
+                              System.out.print(", ");
+                        System.out.print(offset[k]);
+                  }
+            }
+            System.out.println();
+
+            System.out.print("max state number :" + (nstates - 1)  );
+
+            System.out.println("initials" + initials);
+
+            System.out.println("finals" + finals);
+
+            for( int i = 0; i < nstates; i++ ) {
+                  System.out.print("state: " + i);
+                  if( finals.containsKey( new Integer( i )) ){
+                        System.out.print("*"); //final
+                  }
+                  System.out.print("  transitions: {");
+                  HashMap arrows = ((HashMap[])deltaq)[ i ];
+
+                  for( Iterator it = arrows.keySet().iterator();
+                       it.hasNext(); ) {
+                        Object label = it.next();
+                        Vector targets = (Vector) arrows.get( label );
+                        for( Iterator jt = targets.iterator();
+                             jt.hasNext(); ) {
+                              Integer p = (Integer) jt.next();
+                              System.out.print("("+label+","+p+")");
+                        }
+                  }
+
+                  System.out.print("} ");
+                  System.out.print(" default transitions: "+defaultq( i ));
+                  if( qbinders != null )
+                        System.out.println(" binders "+qbinders[ i ]);
+                  System.out.println();
+
+            }
+
+      }
+
+}
diff --git a/sources/scalac/transformer/matching/StateSetComparator.java b/sources/scalac/transformer/matching/StateSetComparator.java
new file mode 100644
index 0000000000..71c43b2374
--- /dev/null
+++ b/sources/scalac/transformer/matching/StateSetComparator.java
@@ -0,0 +1,34 @@
+package scalac.transformer.matching ;
+
+import java.util.* ;
+
+class StateSetComparator implements Comparator {
+            // use lexicographic order
+            public int compare( Object o1, Object o2 ) {
+                  /*
+                  System.out.print("lexi" );
+                  System.out.print( o1 +" ");
+                  System.out.println( o2 );
+                  */
+                  Iterator it1 = ((TreeSet) o1).iterator();
+                  Iterator it2 = ((TreeSet) o2).iterator();
+                  while( it1.hasNext() ) {
+                        while( it2.hasNext() ) {
+                              if( !it1.hasNext() )
+                                    return -1;
+
+                              int i1 = ((Integer) it1.next()).intValue();
+                              int i2 = ((Integer) it2.next()).intValue();
+                              if( i1 < i2 )
+                                    return -1;
+                              else if ( i1 > i2 )
+                                    return 1;
+                        }
+                        if( it1.hasNext() )
+                              return 1;
+                  }
+                  if( it2.hasNext() )
+                        return -1;
+                  return 0;
+            }
+      }