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