diff options
14 files changed, 2508 insertions, 56 deletions
diff --git a/config/list/scalac.lst b/config/list/scalac.lst index 2cb91953b0..5ab90fcf75 100644 --- a/config/list/scalac.lst +++ b/config/list/scalac.lst @@ -114,17 +114,17 @@ #../../../scalac/transformer/matching/AlgebraicMatcher.java #../../../scalac/transformer/matching/Autom2Scala.java -../../../scalac/transformer/matching/BindingBerrySethi.java -../../../scalac/transformer/matching/BerrySethi.java +#../../../scalac/transformer/matching/BindingBerrySethi.java +#../../../scalac/transformer/matching/BerrySethi.java #../../../scalac/transformer/matching/CaseEnv.java #../../../scalac/transformer/matching/CodeFactory.java #../../../scalac/transformer/matching/CollectVariableTraverser.java -../../../scalac/transformer/matching/DetWordAutom.java +#../../../scalac/transformer/matching/DetWordAutom.java #../../../scalac/transformer/matching/FreshVariableTraverser.java -../../../scalac/transformer/matching/Label.java +#../../../scalac/transformer/matching/Label.java #../../../scalac/transformer/matching/TracerInScala.java #../../../scalac/transformer/matching/LeftTracerInScala.java -../../../scalac/transformer/matching/NondetWordAutom.java +#../../../scalac/transformer/matching/NondetWordAutom.java #../../../scalac/transformer/matching/NoSeqVariableTraverser.java #../../../scalac/transformer/matching/PartialMatcher.java #../../../scalac/transformer/matching/PatternMatcher.java @@ -133,7 +133,7 @@ #../../../scalac/transformer/matching/PatternTool.java #../../../scalac/transformer/matching/RightTracerInScala.java #../../../scalac/transformer/matching/SequenceMatcher.java -../../../scalac/transformer/matching/StateSetComparator.java +#../../../scalac/transformer/matching/StateSetComparator.java #../../../scalac/transformer/matching/VariableTraverser.java #../../../scalac/transformer/matching/WordAutomInScala.java @@ -184,11 +184,16 @@ transformer/UnCurry.scala transformer/UnCurryPhase.scala transformer/matching/AlgebraicMatcher.scala transformer/matching/Autom2Scala.scala +transformer/matching/BindingBerrySethi.scala +transformer/matching/BerrySethi.scala transformer/matching/CaseEnv.scala transformer/matching/CodeFactory.scala transformer/matching/CollectVariableTraverser.scala +transformer/matching/DetWordAutom.scala transformer/matching/FreshVariableTraverser.scala +transformer/matching/Label.scala transformer/matching/LeftTracerInScala.scala +transformer/matching/NondetWordAutom.scala transformer/matching/PartialMatcher.scala transformer/matching/NoSeqVariableTraverser.scala transformer/matching/PatternMatcher.scala @@ -197,6 +202,8 @@ transformer/matching/PatternNodeCreator.scala transformer/matching/PatternTool.scala transformer/matching/RightTracerInScala.scala transformer/matching/TracerInScala.scala +transformer/matching/StateSetComparator.scala +transformer/matching/Npair.scala transformer/matching/VariableTraverser.scala transformer/matching/WordAutomInScala.scala transformer/matching/SequenceMatcher.scala diff --git a/sources/scala/tools/scalac/transformer/matching/Autom2Scala.scala b/sources/scala/tools/scalac/transformer/matching/Autom2Scala.scala index 32018a870b..f091982f9b 100644 --- a/sources/scala/tools/scalac/transformer/matching/Autom2Scala.scala +++ b/sources/scala/tools/scalac/transformer/matching/Autom2Scala.scala @@ -12,18 +12,8 @@ import scalac.ast._; import scalac.symtab._; import scalac.util._; // Names -import scala.tools.scalac.util.NewArray; -import scalac.transformer.{ OwnerTransformer => scalac_transformer_OwnerTransformer }; - -//import scalac.transformer.matching.CodeFactory ; -import scalac.transformer.matching.DetWordAutom ; -//import scalac.transformer.matching.PatternNode ; -import scalac.transformer.matching.Label ; - -//import PatternNode._ ; -import Label._ ; - - +import scalac.transformer.{ OwnerTransformer + => scalac_transformer_OwnerTransformer }; import Tree._; @@ -78,7 +68,7 @@ package scala.tools.scalac.transformer.matching { // overridden in RightTracerInScala def loadCurrentElem(body: Tree): Tree = { - gen.mkBlock( NewArray.Tree ( + gen.mkBlock( Predef.Array[Tree] ( cf.gen.ValDef(this.hasnSym, cf._hasNext( _iter() ) ), cf.gen.ValDef(this.curSym, @@ -195,10 +185,10 @@ package scala.tools.scalac.transformer.matching { } def code_state_NEW(i: Int): Tree = { - var stateBody = code_delta( i, Label.DefaultLabel ); + var stateBody = code_delta( i, DefaultLabel() ); if( stateBody == null ) stateBody = code_fail(); - val trans = dfa.deltaq.asInstanceOf[Array[HashMap]]( i ); + val trans = dfa.deltaq( i ); val labs = dfa.labels().iterator(); while(labs.hasNext()) { diff --git a/sources/scala/tools/scalac/transformer/matching/BerrySethi.scala b/sources/scala/tools/scalac/transformer/matching/BerrySethi.scala new file mode 100644 index 0000000000..7bc5b32be1 --- /dev/null +++ b/sources/scala/tools/scalac/transformer/matching/BerrySethi.scala @@ -0,0 +1,666 @@ +/** $Id */ +import scalac.CompilationUnit ; +import scalac.ApplicationError ; +import scalac.ast.Tree ; +import scalac.ast.TreeInfo ; +import scalac.util.Name ; +import Tree._ ; + +import java.util._ ; + +//import scala.compiler.printer.XMLAutomPrinter ; + +/** a Berry-Sethi style construction for nfas. + * this class plays is the "Builder" for the "Director" class WordRecognizer. + */ +package scala.tools.scalac.transformer.matching { + +class BerrySethi(val unit: CompilationUnit ) { + + def isStar(n: Name): boolean = { + TreeInfo.isNameOfStarPattern( n ); + } + /* + + String s = n.toString(); + return (s.indexOf("$") != -1) + &&(!s.startsWith("nest")); + } + */ + + var labels: HashSet = _; + + var pos: int = _; + // maps a literal pattern to an Integer ( the position ) + // is not *really* needed (postfix order determines position!) + var posMap: HashMap = _; // pos: Patterns -> Positions + // don't let this fool you, only labelAt is a real, surjective mapping + var labelAt: HashMap= _; // chi: Positions -> Obj + + var globalFirst: TreeSet= _; + + // results which hold all info for the NondetWordAutomaton + + var follow: HashMap= _; // follow: Positions -> Set[Positions] + + + // Unit test ? + def nullable( pat: Tree ): boolean = { + //System.out.print("<nullable>"); + //DEBUG.print( pat ); + //System.out.println("</nullable>"); + pat.match { + case Apply(_, _) => + return false; + + case Sequence( trees ) => + return (trees.length == 0) || nullable( trees ); + //case Subsequence( Tree[] trees ): + //return + case Bind(n, t) => + /* + if( isStar( n ) ) // generated for star/plus(?) + return true; + */ + return nullable( t ); + case Alternative( choices) => + var result = false; + var i = 0; + while(i < choices.length && !result) { + result = result || nullable( choices( i ) ); + i = i + 1 + } + return result; + case _ => + return false; + } + } + + + /** returns true if a Sequence pattern matches the empty sequence + * @param pat the sequence pattern. + */ + def nullableSequence(pat: Tree): boolean = { + pat.match { + case Sequence( pats ) => + return nullable( pats ); + } + return false; + } + + /** returns true if a sequence of patterns (usually children of a + * sequence or subsequence node) is nullable. + * @param pats the sequence of patterns + */ + def nullable( pats:Array[Tree] ): boolean = { + var result = true; + var i = 0; + while(i < pats.length && result){ + result = result && nullable( pats( i ) ); + i = i + 1 + } + return result; + } + + /** computes first( alpha ) where alpha is a word regexp + */ + + def compFirst( pat:Tree ): TreeSet = { + //System.out.print("<compFirst>"); + //DEBUG.print( pat ); + //System.out.println("</compFirst>"); + pat.match { + case Sequence( trees ) => + return compFirst( trees ); + case Typed(_,_) | Select(_,_) | Apply(_, _) => + val tmp = new TreeSet(); + tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set + return tmp; + + case Literal( _ ) => + val tmp = new TreeSet(); + tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set + return tmp; + //case Subsequence( Tree[] trees ) => + //return compFirst( trees ); + case Alternative( trees ) => + val tmp = new TreeSet(); + var i = 0; + while(i < trees.length) { + tmp.addAll( compFirst( trees( i ) )); + i = i + 1 + } + return tmp; + + case Bind( _, tree ) => + return compFirst( tree ); + + case Ident( name ) => + //if( name != Name.fromString("_") ) + // throw new ApplicationError("unexpected pattern"); + val tmp = new TreeSet(); + tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set + return tmp; + + case _ => + throw new ApplicationError("unexpected pattern"); + } + } + + + + /** computes last( alpha ) where alpha is a word regexp + */ + def compLast( pat:Tree ): TreeSet = { + //System.out.print("<last>"); + //DEBUG.print( pat ); + //System.out.println("</compLast>"); + pat.match { + case Sequence( _ ) | Apply(_, _) => + val tmp = new TreeSet(); + tmp.add(posMap.get( pat ).asInstanceOf[Integer]); // singleton set + return tmp; + + case Literal( _ ) => + val tmp = new TreeSet(); + tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set + return tmp; + + case Alternative( trees ) => + val tmp = new TreeSet(); + var i = 0; + while(i < trees.length) { + tmp.addAll( compLast( trees )); + i = i + 1 + } + return tmp; + + case Bind( _, tree ) => + return compLast( tree ); + + case _ => + throw new ApplicationError("unexpected pattern"); + } + } + + + /** computes first(w) where w=alpha_1...alpha_n are successors of a + * sequence node + */ + def compFirst( pats:Array[Tree] ): TreeSet = { + if( pats.length == 0 ) + return new TreeSet(); + + var i = 0; + var tmp = pats( i ); + val result = compFirst( tmp ); + i = i + 1; + while( nullable(tmp) && (i < pats.length )) { + tmp = pats( i ); + result.addAll( compFirst( tmp )); + i = i + 1; + } + return result; + } + + // Unit test ? + + /** computes last(w) where w are successors of a sequence node + */ + def compLast(pats: Array[Tree]): TreeSet = { + /* + System.out.print("<last>"); + for( int k = 0; k<pats.length; k++) { + DEBUG.print( pats[k] ); + System.out.print(" "); + } + System.out.println(); + */ + if( pats.length == 0 ) + return new TreeSet(); + + var i = pats.length - 1; + var tmp = pats( i ); + val result = compLast( tmp ); + i = i - 1; + while( nullable(tmp) && (i >= 0 )) { + tmp = pats( i ); + result.addAll( compLast( tmp )); + i = i + 1; + } + return result; + } + + // starts from the right-to-left + // precondition: pos is final + // pats are successor patterns of a Sequence node + def compFollow(pats: Array[Tree]): TreeSet = { + var first:TreeSet = null; + this.recVars = new HashMap(); + var fol = new TreeSet(); + if( pats.length > 0 ) {//non-empty expr + var i = pats.length; + fol.add( new Integer( pos )); // don't modify pos ! + do { + i = i - 1; + first = compFollow1( fol, pats( i ) ); + if( nullable( pats( i ) )) + fol.addAll( first ); + else + fol = first; + //System.out.println("in compFollow: first"+first); + //System.out.println("in compFollow: fol"+fol); + + } while( i > 0 ); + } + if( null == first ) + first = new TreeSet(); + else { + first = fol; + } + this.follow.put(new Integer( 0 ), first); + return first; + } + + var recVars: HashMap = _; + + /** returns the first set of an expression, setting the follow set along + * the way + */ + def compFollow1( fol1:TreeSet , pat:Tree ): TreeSet = { + var fol = fol1; + //System.out.println("compFollow1("+fol+","+pat+")"); + pat.match { + case Sequence( trees ) => + var first: TreeSet = null; + var i = trees.length; + if( i > 0 ) { // is nonempty + do { + i = i - 1; + first = compFollow1(fol, trees( i )); + if( nullable( trees( i ) )) + fol.addAll( first ); + else + fol = first; + } while( i > 0 ) ; + } + if( null == first ) first = new TreeSet(); + return first; + + case Alternative( choices ) => + val first = new TreeSet(); + var i = choices.length - 1; + while(i >= 0) { + first.addAll( compFollow1( fol, choices( i ) )); + i = i - 1; + } + return first; + + case Bind( n, t ) => // == can also be star + + val first = compFirst( t ); + //System.out.print("BIND" + first); + recVars.put( pat.symbol(), first ); + + // if( appearsRightmost( n, t )) + // follow = oldfollw + ownfirst + if( isStar( n ) ) + fol.addAll( first ); // an iterated pattern + + // continue to compute follow sets with adjusted fol + return compFollow1( fol, t ); + + case Ident( n ) => + if ((pat.symbol() != null ) + && pat.symbol().isPrimaryConstructor()) { + // same as Apply + val pos = this.posMap.get( pat ).asInstanceOf[Integer]; + val tset = fol.clone().asInstanceOf[TreeSet]; + this.follow.put( pos, tset ); + val first = new TreeSet(); + first.add( pos ); + return first; + } + + if ( recVars.keySet().contains( pat.symbol() )) { // grammar + val first = recVars.get( pat.symbol() ).asInstanceOf[TreeSet]; + val follow = fol.clone().asInstanceOf[TreeSet]; + first.addAll( follow ); + //recVars.put//this.follow.put( pat.symbol(), follow ); + return first; + } + + // --- --- only happens when called from BindingBerrySethi + // [... x ...] changed to [... x@_ ...] + + // non-generated, non-recursive variable should not appear, + // so this is a wildcard pattern _ + + val pos = this.posMap.get( pat ).asInstanceOf[Integer]; + val tset = fol.clone().asInstanceOf[TreeSet]; + this.follow.put( pos, tset ); + val first = new TreeSet(); + first.add( pos ); + //System.out.println("Ident("+n+",...) first:"+first); + //System.out.println("Ident("+n+",...) follow:"+tset); + return first; + + case Apply(_, _) | Literal( _ ) | Typed(_,_) | Select(_,_) => + val pos = this.posMap.get( pat ).asInstanceOf[Integer]; + val tset = fol.clone().asInstanceOf[TreeSet]; + this.follow.put( pos, tset ); + val first = new TreeSet(); + first.add( pos ); + return first; + + case _ => + throw new ApplicationError("unexpected pattern: "+pat.getClass()); + } + } + + /** called at the leaves of the regexp + */ + def seenLabel( pat:Tree , i:Integer , label:Label ): Unit = { + this.posMap.put( pat, i ); + this.labelAt.put( i, label ); + if( label != DefaultLabel() ) { + /* + if( this.labels.contains( label ) ) { + switch(label) { + case TreeLabel(Apply(_, Tree[] args)) => + if( args.length > 0 ) { + unit.warning(pat.pos, "if this pattern in nondeterminism, it will not compile correctly"); + } + } + } + */ + this.labels.add( label ); + } + + } + + /** overriden in BindingBerrySethi + */ + def seenLabel( pat:Tree , label:Label ): Unit = { + seenLabel( pat, new Integer( {pos = pos + 1; pos} ), label ); + } + + /** returns "Sethi-length" of a pattern, creating the set of position + * along the way + */ + + var activeBinders:Vector = _; + + // todo: replace global variable pos with acc + def traverse( pat:Tree ): Unit = { + pat.match { + + // (is tree automaton stuff, more than Berry-Sethi) + case Apply( _, _ ) | Typed( _, _ )| Select( _, _ ) => + val label = new TreeLabel( pat ); + seenLabel( pat, label ) ; + return ; + + case p @ Literal( _ ) => + val label = new SimpleLabel( p ); + seenLabel( pat, label ) ; + + return ; + + case Sequence( trees ) => + var i = 0; + while(i < trees.length) { + traverse( trees( i ) ); + i = i + 1 + } + return ; + + case Alternative( trees ) => + var i = 0; + while(i < trees.length) { + traverse( trees( i ) ); + i = i + 1 + } + return ; + + case Bind( name, body) => + recVars.put( pat.symbol(), java.lang.Boolean.TRUE ); + if( !isStar( name ) ) { + activeBinders.add( pat.symbol() ); + traverse( body ); + activeBinders.remove( pat.symbol() ); + } + else + traverse( body ); + return ; + + case Ident(name) => + if ((pat.symbol() != null ) + && pat.symbol().isPrimaryConstructor()) { + // same as Apply + val label = new TreeLabel( pat ); + seenLabel( pat, label ) ; + + return ; + } + + + if( null != recVars.get( pat.symbol() ) ) { + return ; + } + // _ and variable x ( == x @ _ ) + val label = DefaultLabel(); + seenLabel( pat, label ); + + return ; + + } + } + + + var finals: TreeMap = _; // final states + + //TreeSet initialsRev; // final states + + var deltaq:Array[HashMap] = _; // delta + + + + var defaultq: Array[Vector] = _; // default transitions + + + //HashMap deltaqRev[]; // delta of Rev + //Vector defaultqRev[]; // default transitions of Rev + + + def makeTransition(srcI:Integer, destI:Integer, label: Label): Unit = { + var src = srcI.intValue() ; + var dest = destI.intValue() ; + var arrows: Vector = _; //, revArrows; + //Label revLabel = new Pair( srcI, label ); + label.match { + case DefaultLabel() => + arrows = defaultq( src ); + //revArrows = defaultqRev[ dest ]; + case _ => + arrows = deltaq( src ).get( label ).asInstanceOf[Vector]; + if( arrows == null ) + deltaq( src ).put( label, + {arrows = new Vector(); arrows} ); + /* + revArrows = (Vector) deltaqRev[ dest ].get( revLabel ); + if( revArrows == null ) + deltaqRev[ dest ].put( revLabel, + revArrows = new Vector() ); + */ + } + arrows.add( destI ); + //revArrows.add( srcI ); + } + + + var initials: TreeSet = _; + //NondetWordAutom revNfa ; + + def initialize( subexpr:Array[Tree] ): Unit = { + this.posMap = new HashMap(); + this.labelAt = new HashMap(); + + + this.follow = new HashMap(); + this.labels = new HashSet(); + this.recVars = new HashMap(); + this.pos = 0; + // determine "Sethi-length" of the regexp + activeBinders = new Vector(); + var i = 0; + while(i < subexpr.length ) { + traverse( subexpr( i )); + //assert ( activeBinders.isEmpty() ) + i = i + 1; + } + + this.initials = new TreeSet(); + initials.add( new Integer( 0 )); + + } + + def initializeAutom(): Unit = { + + finals = new TreeMap(); // final states + deltaq = new Array[HashMap]( pos ); // delta + defaultq = new Array[Vector]( pos ); // default transitions + + var j = 0; + while(j < pos) { + deltaq( j ) = new HashMap(); + defaultq( j ) = new Vector(); + j = j + 1; + } + } + + def collectTransitions(): Unit = { // make transitions + var j = 0; + while(j < pos) { + val q = new Integer( j ); + + //System.out.print( "--q="+q ); + //System.out.println(" labelAt:"+labelAt.get( q )); + + val fol = this.follow.get( q ).asInstanceOf[TreeSet]; + //assert fol != null; + val it = fol.iterator(); + while(it.hasNext()) { + val p = it.next().asInstanceOf[Integer]; + //System.out.println( "-- -- p="+p ); + if( p.intValue() == pos ) { + finals.put( q, finalTag ); + } else { + makeTransition( new Integer(j), p, + labelAt.get( p ).asInstanceOf[Label]); + } + } + j = j + 1 + } + } + + var finalTag: Integer = _; + + def automatonFrom(pat: Tree , finalTag: Integer): NondetWordAutom = { + + this.finalTag = finalTag; + + //System.out.println( "enter automatonFrom("+pat+","+finalTag+")"); // UNIT TEST + //System.out.println( pat ); + //System.out.println( nullableSequence( pat )); // UNIT TEST + pat.match { + case Sequence( subexpr ) => + initialize( subexpr ); + + + // (1) compute first + + //globalFirst = compFirst( subexpr ); + //System.out.println(globalFirst); + + // (2) compute follow; + pos = pos + 1; + //Set ignore = compFollow( subexpr ); + //System.out.println(ignore); + //System.exit(0); + //assert (ignore.equals( globalFirst )); + + globalFirst = compFollow( subexpr ); + + //System.out.print("someFirst:");debugPrint(someFirst); + + // construct the automaton's explicit representation + + initializeAutom(); + + + // defaultqRev = new Vector[ pos ]; // default transitions + + collectTransitions(); + + if( nullable( subexpr )) // initial state is final + finals.put( new Integer(0), finalTag ); + + //TreeSet initials = new TreeSet(); + //initials.add( new Integer( 0 ) ); + + val result = + new NondetWordAutom(pos, // = nstates + labels, + initials, + finals, + deltaq, + defaultq, + null/*(Object) qbinders*/); + + /* + System.out.println("inBerrySethi"); + XMLAutomPrinter pr = new XMLAutomPrinter( System.out ); + pr.begin(); + pr.print( result ); + pr.print( revNfa ); + pr.end(); + System.out.println("initialsRev = "+initialsRev); + System.out.println("outBerrySethi"); + */ + //System.exit(0); + //result.print(); + return result; + } + + throw new ApplicationError("expected a sequence pattern"); + } + + def print1(): Unit = { + Console.println("after sethi-style processing"); + Console.println("#positions:" + pos); + Console.println("posMap:"); + + var it = this.posMap.keySet().iterator(); + while(it.hasNext()) { + val t = it.next().asInstanceOf[Tree]; + t.match { + case Literal( _ ) => + Console.print( "(" + t.toString() + " -> "); + val s2 = (posMap.get(t).asInstanceOf[Integer]).toString(); + Console.print( s2 +") "); + } + } + Console.println("\nfollow: "); + var j = 1; + while(j < pos ) { + val fol = this.follow.get(new Integer(j)).asInstanceOf[TreeSet]; + Console.print("("+j+" -> "+fol.toString()+") "); + //debugPrint( fol ); + Console.println; + j = j + 1; + } + + } +} +} diff --git a/sources/scala/tools/scalac/transformer/matching/BindingBerrySethi.scala b/sources/scala/tools/scalac/transformer/matching/BindingBerrySethi.scala new file mode 100644 index 0000000000..8c9a49f06d --- /dev/null +++ b/sources/scala/tools/scalac/transformer/matching/BindingBerrySethi.scala @@ -0,0 +1,171 @@ + + +import scalac.CompilationUnit; +import scalac.Global ; +import scalac.ApplicationError ; +import scalac.ast.Tree ; +import scalac.util.Name ; +import scalac.util.Names ; +import Tree._ ; + +import java.util._ ; + +//import scala.compiler.printer.XMLTreePrinter ; +//import scala.compiler.printer.XMLAutomPrinter ; + +package scala.tools.scalac.transformer.matching { +/** a Berry-Sethi style construction for nfas. + * this class plays is the "Builder" for the "Director" class + * WordRecognizer. + */ + +class BindingBerrySethi(unit:CompilationUnit) extends BerrySethi(unit) { + + + var deltaqRev: Array[HashMap ] = _; // delta of Rev + var defaultqRev:Array[Vector] = _; // default transitions of Rev + var qbinders:Array[Vector] = _; // transitions <-> variables + + override def makeTransition(srcI: Integer, destI: Integer, label: Label): Unit = { + val src = srcI.intValue() ; + val dest = destI.intValue() ; + var arrows: Vector = _; + var revArrows: Vector = _; + val revLabel = new LPair( srcI, label ); + label.match { + case DefaultLabel() => + arrows = defaultq( src ); + revArrows = defaultqRev( dest ); + + case _ => + arrows = deltaq( src ).get( label ).asInstanceOf[Vector]; + if( arrows == null ) + deltaq( src ).put( label, + {arrows = new Vector(); arrows} ); + revArrows = deltaqRev( dest ).get( revLabel ).asInstanceOf[Vector]; + if( revArrows == null ) + deltaqRev( dest ).put(revLabel, {revArrows = new Vector(); revArrows} ); + } + arrows.add( destI ); + revArrows.add( srcI ); + } + + var revnfa: NondetWordAutom = _ ; + + override def seenLabel( pat:Tree , label:Label ): Unit = { + var i = new Integer({pos = pos + 1; pos} ); + seenLabel( pat, i, label ); + pat.match { + case Apply(_, _) | Literal( _ ) | Select(_, _) | Typed(_,_) => + this.varAt.put( i, activeBinders.clone() ); // below @ ? + + case Ident( name ) => + //assert ( pat.symbol() == Global.instance.definitions.PATTERN_WILDCARD )||( name.toString().indexOf("$") > -1 ) : "found variable label "+name; + + val binders = activeBinders.clone().asInstanceOf[Vector]; + /* + if( pat.symbol() != Global.instance.definitions.PATTERN_WILDCARD) { + binders.add( pat.symbol() ); + } + */ + this.varAt.put( i, binders ); + } + } + + var varAt: HashMap = _; // chi: Positions -> Vars (Symbol) + + override def initialize( pats:Array[Tree] ): Unit = { + this.varAt = new HashMap(); // Xperiment + super.initialize( pats ); + } + + override def initializeAutom(): Unit = { + super.initializeAutom(); + deltaqRev = new Array[HashMap]( pos ); // deltaRev + defaultqRev = new Array[Vector]( pos ); // default transitions + qbinders = new Array[Vector]( pos ); // transitions <-> variables + + var j = 0; + while(j < pos) { + deltaqRev( j ) = new HashMap(); + defaultqRev( j ) = new Vector(); + qbinders( j ) = varAt.get( new Integer( j ) ).asInstanceOf[Vector]; + j = j + 1; + } + varAt.clear(); // clean up + } + + + override def automatonFrom( pat:Tree , finalTag:Integer ): NondetWordAutom = { + + this.finalTag = finalTag ; + //System.out.println( "enter automatonFrom("+ pat +")"); + pat.match { + case Sequence( subexpr ) => + + initialize( subexpr ); + + // (1) compute first + follow; + pos = pos + 1; + + globalFirst = compFollow( subexpr ); + + + + initializeAutom(); // explicit representation + + collectTransitions(); + + val result = + new NondetWordAutom(pos, // = nstates + labels, + initials, + finals, + deltaq, + defaultq, + qbinders); + + result.leftTrans = true; + + val revInitials = new TreeSet( finals.keySet() ); + /* + pos++; // adding a state + HashSet deltaqRev2[] = new HashSet[ deltaqRev.length + 1]; + HashSet defaultqRev2[] = new HashSet[ deltaqRev.length + 1]; + HashSet qbinders[] = new HashSet[ deltaqRev.length + 1]; + for(Iterator it = finals.keySet().iterator(); it.hasNext(); ) { + + } + */ + val revFinals = new TreeMap(); + var it = initials.iterator(); + while(it.hasNext()) { + revFinals.put( it.next(), finalTag); + } + revnfa = new NondetWordAutom(pos, + labels, + revInitials, + revFinals, + deltaqRev, + defaultqRev, + qbinders); + + revnfa.rightTrans = true; + + /* + System.out.println("inBerrySethi"); + XMLAutomPrinter pr = new XMLAutomPrinter( System.out ); + pr.begin(); + pr.print( result ); + pr.print( revnfa ); + pr.end(); + System.out.println("initialsRev = "+initialsRev); + System.out.println("outBerrySethi"); + */ + //System.exit(0); + return result; //print(); + } + } +} +} + diff --git a/sources/scala/tools/scalac/transformer/matching/DetWordAutom.scala b/sources/scala/tools/scalac/transformer/matching/DetWordAutom.scala new file mode 100644 index 0000000000..357b6fe652 --- /dev/null +++ b/sources/scala/tools/scalac/transformer/matching/DetWordAutom.scala @@ -0,0 +1,882 @@ +import scalac.ast.Tree ; +import Tree._ ; + +import java.util._ ; + +import scalac.ApplicationError ; + +package scala.tools.scalac.transformer.matching { + +class DetWordAutom { + + /** determinization -- standard algorithm considering only + * reachable states + */ + def this(nfa: NondetWordAutom) = { + this(); + //Console.println("DWA:this(.)"); + //Console.println(nfa.nstates); + //nfa.print(); + determinize( nfa ); + //Console.println(_nstates); + } + + //final static Integer FINTAG = new Integer(0); + + /** number of states */ + var _nstates:int =0; + + /** the 'alphabet' */ + var _labels:HashSet = _; + + /** the set of final states, here as a TreeMap */ + /*protected*/ var finals:TreeMap = _; + + /** dfa: HashMap trans: Object -> Integer + * nfa: HashMap trans: Object -> Vector [ Integer ] + * + * nfa: Integer ->(Object -> Vector [ Int ]) + * [q] |->( a |-> { q' | (q,a,q') in \deltaright } ) + * + * dfa: Integer ->(Object -> Int) + * [q] |->( a |-> q' | \deltaright(q,a) = q' } ) + */ + + var _deltaq: Array[HashMap] = _; + + var _defaultq: Array[Integer] = _; // this gives the default transitions + + //protected HashMap deltaq[]; + + // --- accessor methods + + /** returns number of states + */ + def nstates(): Int = _nstates; + + /** returns the labels + */ + def labels(): HashSet = _labels; + + /** returns the transitions + */ + def deltaq( state:int ): HashMap = _deltaq( state ); + + /** returns the transitions + */ + def deltaq( state:Integer ): HashMap = _deltaq( state.intValue() ); + + + /** for a set of nfa states (that must exist), returns its transitions + */ + def deltaq(nset: TreeSet): HashMap = + deltaq( indexMap.get( nset ).asInstanceOf[Integer] ); + + /** for a set of nfa states (that must exist), returns its transitions + */ + def defaultq( nset:TreeSet ): Integer = + defaultq( indexMap.get( nset ).asInstanceOf[Integer] ); + + /** returns the transitions + */ + def defaultq( state: int ): Integer = + _defaultq( state ); + + /** returns the transitions + */ + def defaultq( state: Integer ): Integer = + _defaultq( state.intValue() ); + + /** returns true if the state is final + */ + def isFinal(state: int): boolean = + ((finals != null) + && (finals.get( new Integer( state )) != null)); + + /** returns true if the state is final + */ + def isFinal(state: Integer): boolean = { + return ((finals != null) && finals.containsKey( state )); + } + + /** returns true if the state is final + */ + def finalTag( state:Integer ): Integer = { + return finals.get( state ).asInstanceOf[Integer]; + } + + + def finalTag( state: int ): Integer = { + return finals.get( new Integer (state )).asInstanceOf[Integer]; + } + + /** returns true if the set of states contains at least one final state + */ + def containsFinal( Q: TreeSet ): boolean = { + val it = Q.iterator(); + while(it.hasNext()) { + if( isFinal(it.next().asInstanceOf[Integer])) + return true; + } + return false; + } + + + /** returns true if there are no finite states + */ + def isEmpty(): boolean = { + return finals.isEmpty(); + } + + // END stuff from FiniteAutom + + final val FIRST: int = 0; + final val LAST: int = FIRST + 1; + + //static final int WHICH_LONGEST_MATCH = FIRST ; + final val WHICH_LONGEST_MATCH:int = LAST ; + + // inherited from FiniteAutom: + + // int nstates; // number of states + // HashSet labels;// the alphabet + // TreeMap finals; + + // HashMap deltaq[]; + //Integer defaultq[]; + + + // TEMPORARY VAR used only during determinization and debug printing + // Q -> (Label -> Q ) + var delta: HashMap = _; + // Q -> Integer; + var indexMap: HashMap = _; + + // Integer -> Q + var invIndexMap: HashMap = _; + + // only not null if this is a right-transducer + var qbinders: Array[Vector] = _; + + final val NODEFAULT: Integer = new Integer( -1 ); + + def isSink( i:int ): boolean = { + return ( _deltaq( i ).keySet().isEmpty() + && (_defaultq != null ) + && (_defaultq( i ).intValue() == i) ); + } + + def hasDefault( i:int ): boolean = { + return _defaultq( i ) != NODEFAULT; + } + + def determinize( nfa: NondetWordAutom ): Unit = { + //Console.println("DetWordAutom:determinize"); + //System.out.println("nfa:");nfa.print(); + var states:TreeSet = _; // temp: Set[Set[Integer]] + var deftrans:HashMap = _; // Set[Integer] -> Int + + var trans: HashMap = _; // always points to a mapping ( Label -> Q ) + var ix = 0; // state index + + this._labels = nfa.labels; + ////System.out.println("Labels: "+labels); + this.delta = new HashMap(); + //this.dead = -1; + + states = new TreeSet( new StateSetComparator() ); + deftrans = new HashMap(); + // temporarily: Map[Set[Integer]] later: Map[Integer] + this.finals = new TreeMap( new StateSetComparator() ); + this.invIndexMap = new HashMap(); + this.indexMap = new HashMap(); + + // new initial state (singleton set { q0 } by construction) + val q0 = new TreeSet(); + q0.addAll( nfa.initials ); /*new Integer( 0 )); */ + states.add( q0 ); + + val empty = new TreeSet(); + deftrans.put( q0, empty ); + states.add( empty ); + deftrans.put( empty, empty ); + + val rest = new Stack(); + if( nfa.isFinal( 0 ) ) + this.finals.put( q0, nfa.finalTag( 0 ) ); + + //Console.println("...beginning"); + + rest.push( empty ); + rest.push( q0 ); + //Console.println("...beginning 2" ); + while( !rest.empty() ) { + //Console.println("...beginning 3" ); + val P1 = rest.pop().asInstanceOf[TreeSet]; + + //System.out.println("states:"+ states); + //System.out.println("P1:"+ P1); + + invIndexMap.put( new Integer( ix ), P1 ); + indexMap.put( P1, new Integer( ix )); + ix = ix + 1; + delta.put( P1, {trans = new HashMap(); trans}); + + //Console.println("...beginning 4" ); + // labelled transitions + val it = _labels.iterator(); + //Console.println("it = "+it ); + //Console.println(it.hasNext()); + + while( it.hasNext() ) { + //Console.println("...beginning 5" ); + //Console.flush; + val label = it.next(); + //Console.print( "Label: " + label +" "); + // Qdest will contain all states reachable via `label' + // from some nfa state in P1; + val Qdest = nfa.getSide( P1, label ); + //Console.println("Qdest:"+Qdest); + if( !states.contains( Qdest ) ) { + states.add( Qdest ); + ////System.out.print(" (added)" ); + rest.push( Qdest ); + ////System.out.print(" (pushed)"); + + //Console.println("nfa.containsFinal("+Qdest+") =="+nfa.containsFinal( Qdest )); + + if( nfa.containsFinal( Qdest ) ) + this.finals.put( Qdest, nfa.finalTag( Qdest )); + ////System.out.print(" (added final)"); + + } + ////System.out.println(".Qdest"); + + trans.put( label, Qdest ); + // //System.out.println( "Qdest: " + Qdest); + //Console.println("Y marks"); + } + + // default transitions + + val defTarget: TreeSet = nfa.defaultq( P1 ).asInstanceOf[TreeSet]; + //System.out.println("defTarget:"+defTarget); + deftrans.put( P1, defTarget ); + + //Console.println("X marks 0"); + + if( !states.contains( defTarget ) ) { + //Console.println("X marks 1"); + + states.add( defTarget ); + rest.push( defTarget ); + //Console.println("nfa.containsFinal("+defTarget+")"+nfa.containsFinal( defTarget )); + if( nfa.containsFinal( defTarget ) ) + this.finals.put( defTarget, nfa.finalTag( defTarget )); + } + + //Console.println("X marks"); + } + + //Console.println("...continuing"); + + // <DEBUG> + //printBefore( states, deftrans ); + + // </DEBUG> do not call printBefore after this point + // //System.out.println("indexMap: "+indexMap); + + this._nstates = states.size(); + _deltaq = new Array[HashMap]( _nstates ); + _defaultq = new Array[Integer]( _nstates ); + + // we replace Set[Set[Integer]] by its index and clean up + + val jt = states.iterator(); + while(jt.hasNext()) { + val state = jt.next().asInstanceOf[TreeSet]; + val state_x = indexMap.get( state ).asInstanceOf[Integer]; + + val defTarget = deftrans.get( state ).asInstanceOf[TreeSet]; + var defTarget_x: Integer = _; + if( null != defTarget) { + defTarget_x = indexMap.get( defTarget ).asInstanceOf[Integer]; + ////System.out.println("deftarget" + defTarget); + } else + defTarget_x = NODEFAULT; + + ////System.out.print(state.toString() + " --> " + state_x); + //System.out.println(" deftarget " + defTarget + " --> "+defTarget_x); + + trans = delta.get( state ).asInstanceOf[HashMap]; + val newTrans = new HashMap(); + val labs = _labels.iterator(); + while(labs.hasNext()) { + val label = labs.next(); + val target = trans.get( label ).asInstanceOf[TreeSet]; + var target_x: Integer = _; + if( null != target ) { + // //System.out.println("target :"+target); + target_x = indexMap.get( target ).asInstanceOf[Integer]; + + if( target_x.intValue() != defTarget_x.intValue() ) { + // replace target by target_x + // (use type-unawareness) + newTrans.put( label, target_x ); + } + trans.remove( label ); + } + + } + _deltaq( state_x.intValue() ) = newTrans; + _defaultq( state_x.intValue() ) = defTarget_x; + + delta.remove( state ); + deftrans.remove( state ); + + } + //Console.println("determinize::: finals"+finals); + val oldfin: TreeMap = finals; + this.finals = new TreeMap(); + var kt = oldfin.keySet().iterator(); + while(kt.hasNext()) { + val state = kt.next().asInstanceOf[TreeSet]; + val state_x = indexMap.get( state ).asInstanceOf[Integer];; + this.finals.put( state_x, oldfin.get( state ) ); // conserve tags + } + + // clean up, delete temporary stuff + /* + // we cannot clean up, indexmap is needed later + for( Iterator it = states.iterator(); it.hasNext(); ) { + ((TreeSet) it.next()).clear(); + } + */ + states.clear(); + + //Console.println("...done"); + //minimize(); + } + + + + def isDead( state: int ): boolean = { + return state == _nstates - 1; // by construction + } + + def isDead( state: Integer ): boolean = { + return state.intValue() == _nstates - 1; // by construction + } + + + /** returns target of the transition from state i with label label. + * null if no such transition exists. + */ + def delta( i:int , label:Label ): Integer = { + var target:Integer =_; + label.match { + case DefaultLabel() => + if( !hasDefault( i ) ) + return null; + return _defaultq( i ).asInstanceOf[Integer] ; + case SimpleLabel( _ ) | TreeLabel( _ ) => + return _deltaq( i ).get( label ).asInstanceOf[Integer] ; + /*case LPair( Integer state, Label lab ): + return state; + */ + case _ => + throw new ApplicationError("whut's this: label="+label+", class "+label.getClass()); + } + } + + def delta( i:Integer , label:Label ): Integer = { + return delta( i.intValue(), label ); + } + + /** should maybe in nfa, not here + */ + /*static */ + protected def smallestFinal( nfa: NondetWordAutom, states:TreeSet ): Integer = { + + var min = Integer.MAX_VALUE ; + val it = states.iterator(); + while(it.hasNext()) { + val state = it.next().asInstanceOf[Integer]; + if( nfa.isFinal( state ) && (state.intValue() < min )) + min = state.intValue(); + } + if( min == Integer.MAX_VALUE ) + throw new ApplicationError("I expected a final set of states"); + return new Integer( min ); + } + + protected def allSetsThatContain( ndstate: Integer ): Vector = { + val v = new Vector(); + val it = indexMap.keySet().iterator(); + while(it.hasNext()) { + val ndstateSet = it.next().asInstanceOf[TreeSet]; + if( ndstateSet.contains( ndstate )) + v.add( ndstateSet ); + } + return v; + } + + + protected def filterItOutQuoi( dLeft: DetWordAutom, npTarget: Npair,lab:LPair , nsrc:TreeMap ):Unit = { + val theLabel = lab.lab; + val ntarget = lab.state; + + // e.g.[2,(3),4] --> 7 + val dstate = dLeft.indexMap.get( npTarget.nset ).asInstanceOf[Integer]; + + // eg. 3 -> [3] [2,3] + val targets:Vector = dLeft.allSetsThatContain( ntarget ); + + ////System.out.println( targets+", of these " ) ; + + // filter out those source states which arrive here... + val su = targets.iterator(); + while(su.hasNext()) { + val nset = su.next().asInstanceOf[TreeSet]; + val ddelta = dLeft.deltaq( nset ).asInstanceOf[HashMap]; + + // ... at THIS dstate + if(ddelta.get( theLabel ).asInstanceOf[Integer] == dstate ) { + + val np1 = new Npair( ntarget, nset ); + + ////System.out.print( np1.toString( dLeft.indexMap )); + + if( WHICH_LONGEST_MATCH == FIRST ) + addTransitionFLM( nsrc, np1 ); + else + addTransitionLLM( nsrc, np1 ); + } + + } + } + + /** all default transitions from sets that contain nq to npTarget + */ + protected def filterItOutQuoiDefault( dLeft: DetWordAutom ,npTarget:Npair , nq:Integer , nsrc:TreeMap ): Unit = { + + + ////System.out.println( "npTarget = " + npTarget ) ; + + val allSources = dLeft.allSetsThatContain( npTarget.nstate ); + val it = allSources.iterator(); + while(it.hasNext()) { + + // e.g.[2,(3),4] --> 7 + //Integer dstate = (Integer) dLeft.indexMap.get( npTarget.nset ); + + val dstate = dLeft.indexMap.get( it.next() ).asInstanceOf[Integer]; + + //System.out.println( "dstate = " + dstate ) ; + + //assert dstate != null; + + // eg. 3 -> [3] [2,3] + val targets = dLeft.allSetsThatContain( nq ); + + //System.out.println( "targets: " + targets ) ; + + // filter out those source states which arrive here... + val su = targets.iterator(); + while(su.hasNext()) { + val nset = su.next().asInstanceOf[TreeSet]; + val ddef = dLeft.defaultq( nset ); + + //System.out.println( "ddef ="+ddef ); + + // ... at THIS dstate + if( ddef == dstate ) { + + val np1 = new Npair( nq, nset ); + + // print target + //System.out.print( np1.toString( dLeft.indexMap )); + + if( WHICH_LONGEST_MATCH == FIRST ) + addTransitionFLM( nsrc, np1 ); + else + addTransitionLLM( nsrc, np1 ); + + } + + } + } + } + + /** this implements the first longest match policy + */ + protected def addTransitionFLM( nsrc:TreeMap , np:Npair ): Unit= { + val np2 = nsrc.get( np.nset ).asInstanceOf[Npair ]; + + // (policy) first longest match + if(( np2 == null ) + ||( np2.nstate.intValue() > np.nstate.intValue())) { + nsrc.put( np.nset, np ); + } + + } + + /** this implements the last longest match policy (!) + */ + protected def addTransitionLLM(nsrc: TreeMap, np: Npair ): Unit = { + val np2 = nsrc.get( np.nset ).asInstanceOf[Npair]; + + // (policy) first longest match + if(( np2 == null ) + ||( np2.nstate.intValue() < np.nstate.intValue())) { + nsrc.put( np.nset, np ); + } + + } + + + /** build a deterministic right to left transducer from the args + */ + def this(right: NondetWordAutom, left:NondetWordAutom, dLeft: DetWordAutom ) = { + this(); + + /* System.out.println("DetWordAutom.<init>(nfa,nfa,dfa)"); + System.out.println("nfa-left:");left.print(); + System.out.println("nfa-right:");right.print(); + System.out.println("dLeft:"+dLeft.print()); + System.out.println("dLeft.finals"+dLeft.finals); + */ + this.indexMap = dLeft.indexMap; + this.invIndexMap = dLeft.invIndexMap; + // fix indexMap + /* // unnecessary + TreeSet q0 = new TreeSet(); + q0.add( new Integer( 0 )); + indexMap.put( q0, new Integer( 0 )); + //System.out.println("check out the indexMap!" + indexMap); + */ + + val visited_n = new TreeSet( new NpairComparator() ); + val rest = new Stack(); + + // right is "nearly deterministic" + // we can follow reverse traces paths by using dLeft.indexMap + + // start with right.initials, left.final, dLeft.final + val it = dLeft.finals.keySet().iterator(); + while(it.hasNext()) { + val fstate = it.next().asInstanceOf[Integer]; + val nfstate = invIndexMap.get( fstate ).asInstanceOf[TreeSet]; + //System.out.print( "final state:"+fstate); + //System.out.print( " correspond to set of states:"+ nfstate ); + + val min_ndstate: Integer = smallestFinal( left, nfstate ); + + val npair:Npair = new Npair( min_ndstate, nfstate ); + + //System.out.println( " smallest final of these: "+ min_ndstate ); + + + //System.out.println( "push final nfa state "+npair.toString( dLeft.indexMap )); + + if( !visited_n.contains( npair )) { + visited_n.add( npair ); + rest.push( npair ); + } + } + + val ratLab = new HashMap(); // maps nset to label,HashMap + val ratDelta = new HashMap(); // maps nset to Vector[ NP ]targets + + val ratDefault = new HashMap(); // maps nset to NP (one target) + + var ix = 1; + val ix_initial = rest.clone().asInstanceOf[Stack]; + var ix_final = new TreeSet( new NpairComparator() );; + + val newIndexMap = new TreeMap( new NpairComparator() ); + + while( !rest.isEmpty() ) { + + val npair = rest.pop().asInstanceOf[Npair]; + newIndexMap.put( npair, new Integer(ix)); + + ratDelta.put( npair, new Vector() ); + + if( npair.nset.contains( new Integer( 0 )) ) { + ix_final.add( npair ); + } + ix = ix + 1; + + //System.out.println(" popped "+npair.toString( dLeft.indexMap )); + + ////System.out.print(" binders: "); + ////System.out.print( right.qbinders[ npair.nstate.intValue() ] ); + + val delta = right.deltaq( npair.nstate ); + + ////System.out.print(" we could have arrived : "); + //search the delta for target invIndexMap + + val labelToNset = new HashMap(); + val labelToFrom = new HashMap(); + + // maps nsets to the active nstates + var nsrc = new TreeMap( new StateSetComparator() ); + + // berry-sethi construction assures that + // there is only one label for outgoing transitions + var theLabel:Label = null; + + // collect all transition possible in the DFA + val jt = delta.keySet().iterator(); + while(jt.hasNext()) { + val lab = jt.next().asInstanceOf[LPair]; + + // lab.state is the target in the NFA + + if( null == theLabel ) { + ratLab.put( npair, lab.lab ); + ////System.out.print(" with \""+lab.lab+"\" "); + } + theLabel = lab.lab ; + + ////System.out.print("\nfrom n" + lab.state +" ... "); + + // these are too many, filter out those that exist in DFA + + filterItOutQuoi( dLeft, npair, lab, nsrc ); + + } + + + ////System.out.println( "---" ); + + ////System.out.println("all sources: "); + + // !! first longest match + val ut = nsrc.keySet().iterator(); + while(ut.hasNext()) { + val nset = ut.next().asInstanceOf[TreeSet]; + val np2: Npair = nsrc.get( nset ).asInstanceOf[Npair] ; + + //assert( np2 != null ); + ////System.out.println("target: n"+npair.nstate+" via: "+theLabel+" from "+ np2.toString( dLeft.indexMap ));// nset:"+nset+ " namely state n"+ dest); + + val v = ratDelta.get( npair ).asInstanceOf[Vector]; + + v.add( np2 ); + + if( !visited_n.contains( np2 ) ) { + + visited_n.add( np2 ); + rest.push( np2 ); + } + + } + + //System.out.println("default sources: "); + + // maps nsets to the active nstates + nsrc = new TreeMap( new StateSetComparator() ); + + // now for all default transitions that arrive at this nfa state + val defqs = right.defaultq( npair.nstate ); + val kt = defqs.iterator(); + while( kt.hasNext() ) { + val nq = kt.next().asInstanceOf[Integer]; + //System.out.println("checking nq="+nq); + filterItOutQuoiDefault( dLeft, npair, nq, nsrc ); + //System.out.println( "nsrc after "+nq+" is "+nsrc ); + } + + //System.out.println( "defqs :"+defqs ); + //System.out.println( "nsrc :"+nsrc ); + var nut = nsrc.keySet().iterator(); + while(nut.hasNext()) { + + val np2 = nsrc.get( nut.next() ).asInstanceOf[Npair]; + + var v = ratDefault.get( npair ).asInstanceOf[Vector] ; + if( v == null ) + ratDefault.put( npair, {v = new Vector(); v} ); + v.add( np2 ); + + if( !visited_n.contains( np2 ) ) { + + visited_n.add( np2 ); + rest.push( np2 ); + } + + } + + ////System.out.println("zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"); + + } + + // Renumbering + + ////System.out.println( "output: a dfa with "+ix+"states"); + + // FIX: empty regular expression (as in "List()") is valid + //assert ( !ix_final.isEmpty() ) : "no final states found"; + + ////System.out.println( "final state:"+ix_final); + + //System.out.println( "indexMap: " +indexMap); + //System.out.println( "newIndexMap: " +newIndexMap); + this.finals = new TreeMap(); + this._nstates = ix; + val dratDelta = new Array[HashMap]( ix ); + qbinders = new Array[Vector]( ix ); + _labels = new HashSet(); + val kit = ratDelta.keySet().iterator(); + while(kit.hasNext()) { + val np = kit.next().asInstanceOf[Npair]; + + //System.out.print( "\nstate: "+np); + val ndset = np.nset; + val dstate = newIndexMap.get( np ).asInstanceOf[Integer]; + //assert dstate != null : "no dstate for "+np.toString(dLeft.indexMap); + + //System.out.print(" binders:"); + + qbinders( dstate.intValue() ) = left.qbinders( np.nstate.intValue() ); + + //System.out.print( qbinders[dstate.intValue() ]); + + //System.out.println(" transitions:"); + if( ix_final.contains( np ) ) { + val fin_ix = newIndexMap.get( np ).asInstanceOf[Integer]; + finals.put( fin_ix, new Integer( 0 )); + } + + val lab = ratLab.get( np ).asInstanceOf[Label]; + val v = ratDelta.get( np ).asInstanceOf[Vector]; + + val ddelta = new HashMap(); + + // v might be null if there are only default transitions + if( v != null ) { + val it2 = v.iterator(); + while(it2.hasNext()) { + + val np2= it2.next().asInstanceOf[Npair]; + //System.out.print( "("+lab+","+np2+") " ); + val ddestR = newIndexMap.get( np2 ).asInstanceOf[Integer]; + val ddest = indexMap.get( np2.nset ).asInstanceOf[Integer]; + //assert ddest != null : + //"no ddest for " + //+np2.toString(dLeft.indexMap); + + val newLab = new LPair(ddest, lab); + ddelta.put( newLab, ddestR ); + _labels.add( newLab ); + + } + dratDelta( dstate.intValue() ) = ddelta; + + } + } + var itt = ratDefault.keySet().iterator(); + while(itt.hasNext()) { + val np = itt.next().asInstanceOf[Npair]; + val dstate = newIndexMap.get( np ).asInstanceOf[Integer]; + + //System.out.print("\nstate: "+np+" default trans: "); + + val v = ratDefault.get( np ).asInstanceOf[Vector]; + val ut = v.iterator(); + while(ut.hasNext()) { + val np2 = ut.next().asInstanceOf[Npair]; + val targetL = indexMap.get( np2.nset ).asInstanceOf[Integer];; + val targetR = newIndexMap.get( np2 ).asInstanceOf[Integer];; + + val defLab = new LPair( targetL, DefaultLabel() ); + + _labels.add( defLab ); + //System.out.print( "("+defLab+","+np2+") " ); + + var d = dratDelta( dstate.intValue() ); + if( d == null ) + dratDelta( dstate.intValue() ) = {d = new HashMap(); d}; + + d.put( defLab, targetR ); + } + } + + _deltaq = dratDelta; + + val hmap = new HashMap(); + + // final states of left are initial states of right + // problem: still need to choose the one + + while( !ix_initial.isEmpty() ) { + val np = ix_initial.pop().asInstanceOf[Npair]; + + val i = newIndexMap.get( np ).asInstanceOf[Integer]; //R-state + val dtarget = indexMap.get( np.nset ).asInstanceOf[Integer];// left-d-state + + hmap.put( dtarget, i ); + } + _deltaq( 0 ) = hmap; // careful, this maps Int to Int + + qbinders( 0 ) = new Vector(); + //((Vector[])defaultq)[ 0 ] = new Vector(); is null + //printBeforeRAT( dratDelta ); + + } + + def printBeforeRAT1(str: String): Unit = { + val tmp = new StringBuffer( str ); + var j = tmp.length(); + while(j < 20) { + tmp.append(" "); + j = j + 1; + } + Console.println( tmp.toString() ); + } + + def printBeforeRAT( dratDelta: Array[HashMap] ): Unit = { + //System.out.println(); + printBeforeRAT1( "dratDelta" ); + printBeforeRAT1( "[index]" ); + //System.out.println(); + var i = 0; + while(i < dratDelta.length) { + if( isFinal( i )) + printBeforeRAT1( "*"+i ); + else + printBeforeRAT1( " "+i ); + + //System.out.println( dratDelta[ i ] ); + i = i + 1 + } + } + + /** you may only call this before the set[set[...]] representation + * gets flattened. + */ + def printBefore( states:TreeSet , deftrans:HashMap ): Unit = { + var trans: HashMap = _; + Console.println( states ); + val it = states.iterator(); + while(it.hasNext()) { + val state = it.next().asInstanceOf[TreeSet]; + Console.print("state:"+state.toString()+" transitions "); + trans = delta.get( state ).asInstanceOf[HashMap]; + val labs = _labels.iterator(); + while(labs.hasNext()) { + val label = labs.next(); + val target = trans.get( label ).asInstanceOf[TreeSet]; + Console.print( " (" + label.toString() + + "," + target.toString()+")"); + } + Console.print("default trans"+deftrans.get( state )); + Console.println; + } + Console.println("final states:" + finals ); + } +} +} diff --git a/sources/scala/tools/scalac/transformer/matching/Label.scala b/sources/scala/tools/scalac/transformer/matching/Label.scala new file mode 100644 index 0000000000..3935ffc631 --- /dev/null +++ b/sources/scala/tools/scalac/transformer/matching/Label.scala @@ -0,0 +1,133 @@ +import scalac.ApplicationError; +import scalac.ast.Tree ; +import scalac.ast.TreeInfo ; +import scalac.symtab.Symbol ; +import scalac.symtab.Type ; +import Tree.Literal ; + +/** this class represents the label that a transition in an automaton may carry. + * these get translated to specific (boolean) tests + */ +package scala.tools.scalac.transformer.matching { + +class Label { + + + //case class RLabel( Object rstate, Label lab, Symbol vars[] ); + + override def hashCode(): Int = match { + case DefaultLabel() => + return 0; + case SimpleLabel( lit )=> + return lit.value.hashCode(); + case TreeLabel( pat ) => + // if pat is an Apply, than this case can only be correctly + // handled there are no other similar Applys (nondeterminism) + return pat.getType().hashCode(); + case TypeLabel( tpe ) => + return tpe.hashCode(); + case _ => + return super.hashCode(); + } + + override def equals( o: Any ): Boolean = { + if( !(o.isInstanceOf[Label] )) + return false; + val oL = o.asInstanceOf[Label]; + //System.out.print(this + " equals " + oL); + this.match { + case DefaultLabel()=> + oL.match { + case DefaultLabel() => + return true; + case _ => false; + } // + case SimpleLabel( lit ) => + oL.match { + case SimpleLabel( lit2 ) => + return /*(lit.kind == lit2.kind) + && */lit.value.equals( lit2.value ); + case _ => false; + } + + case TreeLabel( pat ) => + oL.match { + case TreeLabel( pat2 ) => + pat.match { + case Tree.Apply( _, _ ) => + pat2.match { + case Tree.Apply( _, _ ) => + return TreeInfo.methSymbol( pat ) == TreeInfo.methSymbol( pat2 ); + } + case _ => false; + } + case _ => false + } + + case TypeLabel( tpe ) => + oL.match { + case TypeLabel( tpe2) => + return tpe.equals( tpe2 ); + case _ => false; + } + case LPair( state, lab ) => + oL.match { + case LPair( state2, lab2 ) => + return state.equals( state2 ) && lab.equals( lab2 ) ; + case _ => false; + } + case _ => return false; + } + } + + + def toString2(): String = { + val ext = System.getProperty("extendedMatching"); + if(( ext != null )&& ext.equals( "true" )) { + this.match { + case DefaultLabel() => + return "<>:p"+p; + case SimpleLabel( lit ) => + return lit.toString()+":p"+p; + case TreeLabel( pat ) => + return pat.getType().toString()+":p"+p; + + case _ => throw new ApplicationError("this never happens"); + } + } + throw new ApplicationError("this never happens"); + } + + override def toString(): String = { + + this.match { + case DefaultLabel() => + return "<>"; + case SimpleLabel( lit) => + return lit.toString(); + case TreeLabel(pat) => + return pat.toString(); + case TypeLabel( tpe ) => + return tpe.toString(); + case LPair( state, lab ) => + return "("+state.toString()+","+lab.toString()+")"; + case _ => + throw new ApplicationError("this never happens"); + } + } + + val p = -1; // tree state - only needed for extended matching + + +} + + + case class DefaultLabel() extends Label; + case class SimpleLabel( lit: Literal ) extends Label; + case class TreeLabel( pat: Tree ) extends Label; // Apply, Sequence + + case class TypeLabel( tpe: Type ) extends Label; // Apply, Sequence + + case class LPair( state: Integer, lab: Label ) extends Label; +} + diff --git a/sources/scala/tools/scalac/transformer/matching/LeftTracerInScala.scala b/sources/scala/tools/scalac/transformer/matching/LeftTracerInScala.scala index 34fd084d7c..b13c7680b5 100644 --- a/sources/scala/tools/scalac/transformer/matching/LeftTracerInScala.scala +++ b/sources/scala/tools/scalac/transformer/matching/LeftTracerInScala.scala @@ -7,10 +7,7 @@ import scalac.util.Names; import java.util._ ; import scala.tools.util.Position; -//import scalac.transformer.matching._ ; -//import scalac.transformer.matching.CodeFactory ; -import scalac.transformer.matching.DetWordAutom ; -import scalac.transformer.matching.Label ; + package scala.tools.scalac.transformer.matching { class LeftTracerInScala(dfa: DetWordAutom, elementType: Type, owner: Symbol, cf: CodeFactory, val selector: Tree ) @@ -144,14 +141,14 @@ extends TracerInScala( dfa, elementType, owner, cf ) { // default action (fail if there is none) - stateBody = code_delta( i, Label.DefaultLabel); + stateBody = code_delta( i, DefaultLabel()); if( stateBody == null ) stateBody = code_fail(); // transitions of state i - val trans = (dfa.deltaq.asInstanceOf[Array[HashMap]])( i ); - val labs = (dfa.deltaq( i ).asInstanceOf[HashMap]).keySet().iterator(); + val trans = dfa.deltaq( i ); + val labs = dfa.deltaq( i ).keySet().iterator(); while(labs.hasNext()) { val label = labs.next(); val next = trans.get( label ).asInstanceOf[Integer]; diff --git a/sources/scala/tools/scalac/transformer/matching/NondetWordAutom.scala b/sources/scala/tools/scalac/transformer/matching/NondetWordAutom.scala new file mode 100644 index 0000000000..d87cee40f2 --- /dev/null +++ b/sources/scala/tools/scalac/transformer/matching/NondetWordAutom.scala @@ -0,0 +1,527 @@ + + +import scalac.ApplicationError ; +import scalac.ast.Tree ; +import scalac.util.Name ; +import Tree._ ; + +import java.util._ ; +package scala.tools.scalac.transformer.matching { +/** a nondeterministic word automaton. + * states are represented (implicitly) as Integer objects. + */ + +class NondetWordAutom { + // BEGIN stuff from FiniteAutom + + //final static Integer FINTAG = new Integer(0); + + /** number of states */ + var nstates: int =_; + + /** the 'alphabet' */ + var labels: HashSet = _; + + /** the set of final states, here as a TreeMap */ + var finals: TreeMap = _; + + /** dfa: HashMap trans: Object -> Integer + * nfa: HashMap trans: Object -> Vector [ Integer ] + * + * nfa: Integer ->(Object -> Vector [ Int ]) + * [q] |->( a |-> { q' | (q,a,q') in \deltaright } ) + * + * dfa: Integer ->(Object -> Int) + * [q] |->( a |-> q' | \deltaright(q,a) = q' } ) + */ + + var _deltaq:Array[HashMap] = _; + + var _defaultq:Array[Vector] = _; // this gives the default transitions + + //public HashMap deltaq[]; + + // --- accessor methods + + /** returns number of states + def nstates(): int = { + return nstates; + } + */ + + /** returns the labels + def labels(): HashSet = { + return _labels; + } + */ + + /** returns the transitions + */ + def deltaq( state: int ):HashMap = { + return _deltaq( state ); + } + + /** returns the transitions + */ + def deltaq( state: Integer ): HashMap = { + return _deltaq( state.intValue() ); + } + + /** returns the transitions + */ + def defaultq( state: int ): Vector = { + return _defaultq( state ); + } + + /** returns the transitions + */ + def defaultq( state:Integer ): Vector = { + return _defaultq( state.intValue() ); + } + + + /** returns true if the state is final + */ + def isFinal( state:int ): boolean = { + return ((finals != null) + && (finals.get( new Integer( state )) != null)); + } + + /** returns true if the state is final + */ + def isFinal( state:Integer ): boolean = { + return ((finals != null) && finals.containsKey( state )); + } + + /** returns true if the state is final + */ + def finalTag( state: Integer ): Integer = { + return finals.get( state ).asInstanceOf[Integer]; + } + + + def finalTag( state:int ): Integer = { + return finals.get( new Integer (state )).asInstanceOf[Integer]; + } + + /** returns true if the set of states contains at least one final state + */ + def containsFinal( Q:TreeSet ): boolean = { + var it = Q.iterator(); + while(it.hasNext()) { + if( isFinal( it.next().asInstanceOf[Integer])) + return true; + } + return false; + } + + + /** returns true if there are no finite states + */ + def isEmpty(): boolean = finals.isEmpty(); + + // END stuff from FiniteAutom + + + // inherited from FiniteAutom + + // set of *distinct* objects that may label transitions + // see Object.hashCode() to see why this works + + //HashSet labels; + //TreeMap finals; + + var initials: TreeSet = _; // ? need this ? + // --- + + // Object deltaq --> + // HashMap deltaq[]; // this gives the transitions of q; + + var leftTrans: boolean = _; + var rightTrans: boolean = _; + + /** if true, this automaton behaves as a special left transducer. + * if a run succeeds, the result is not "true" but the entire + * run of the automaton as a sequence of (label,state) - pairs. + * used for binding variables. + */ + def producesRun(): boolean = { + return leftTrans; + } + + def consumesRun(): boolean = { + return rightTrans; + } + + def initial( i: Integer ): boolean = { + return initials.contains( i ); + } + var qbinders: Array[Vector] = _; + + /** returns all states accessible from Qsrc via label. + * used by class DetWordAutomaton. + */ + def getSide ( Qsrc:TreeSet , label:Object ): TreeSet = { + //Console.println("NWA::getSide(Qsrc="+Qsrc); + val Qdest = new TreeSet(); + var it = Qsrc.iterator(); + while(it.hasNext()) {// state + val q = it.next().asInstanceOf[Integer].intValue(); + val ps = deltaq( q ).get( label ).asInstanceOf[Vector]; + //Console.println("deltaq(q) = "+deltaq(q)); + //Console.println("_deltaq(q) = "+_deltaq(q)); + //Console.println("ps = "+ps); + if( null != ps ) { + Qdest.addAll( ps ); + } + //Console.println("defq = "+_defaultq( q )); + Qdest.addAll( _defaultq( q ) ); + } + //Console.println("DONE-NWA::getSide"); + return Qdest; + } + + /** returns the transitions + */ + def defaultq( P1: Set ): Object = { + val defTarget = new TreeSet(); + var p1 = P1.iterator(); + while(p1.hasNext()) { + val q1 = p1.next().asInstanceOf[Integer].intValue(); + //System.out.println(" q1:"+q1+ " defa: "+defaultq( q1 )); + defTarget.addAll( _defaultq( q1 ) ); + } + return defTarget; + } + + + /** first match policy: among several final states, the smallest one is + * chosen. used by class DetWordAutomaton + */ + def finalTag( Q:Set ): Integer = { + + var min = Integer.MAX_VALUE ; + var it = Q.iterator(); + while(it.hasNext()) { + val state = it.next().asInstanceOf[Integer]; + val tag = finals.get( state ).asInstanceOf[Integer]; + if( tag != null ) { + if( tag.intValue() < min ) + min = tag.intValue(); + } + } + + if ( min == Integer.MAX_VALUE ) + throw new ApplicationError( "there should be a final state "); + + return new Integer( min ); + } + + /* + void tmap(int offs, TreeMap t) = { + TreeMap nt = new TreeMap(); + for(Iterator it = t.keySet().iterator(); it.hasNext(); ) = { + Integer key = (Integer) it.next(); + Integer newkey = new Integer( key.intValue() + offs ); + Integer val = (Integer) t.get( key ); + Integer newval = new Integer( val.intValue() + offs ); + + nt.put( newkey, newval ); + } + return nt; + } + */ + // hashmaps, treemaps + def mapmap(src:Map, offset:int , dest:Map , mapkeys:boolean , mapvals:boolean ): Map = { + var it = src.keySet().iterator(); + while(it.hasNext()) { + var key = it.next(); + var value = src.get( key ); + if( mapkeys ) key = new Integer( key.asInstanceOf[Integer].intValue() + + offset ); + if( mapvals ) value = vmap( offset, value.asInstanceOf[Vector] ) ; + /* new Integer( ((Integer)val).intValue() + + offset ); + */ + dest.put( key, value ); + } + return dest; + } + + def vmap(offs:int , v:Vector ): Vector = { + if( v == null ) + return null; + var res = new Vector( v.size() ); + var it = v.iterator(); + while(it.hasNext()) { + val item = it.next().asInstanceOf[Integer]; + res.add( new Integer( item.intValue() + offs )); + } + return res; + + } + + /* + void relocate_defaultq( int offs, Vector _defaultq[] ) = { + for( int i = 0; i < this.nstates; i++ ) = { + _defaultq[ i + offset ] = vmap( offset, ((Vector[])defaultq)[ i ]); + } + } + */ + + /** copies the values in the fields of this object into the + * arguments, possibly adding an offset. + */ + def relocate( offset:int, _finals:TreeMap, _deltaq1:Array[HashMap], _defaultq1:Array[Vector], _qbinders1:Array[Vector] ): Unit = { + + mapmap( finals, offset, _finals, true, false); + var i = 0; + while(i < this.nstates) { + + _deltaq1 ( i + offset ) = + mapmap( deltaq( i ), offset, new HashMap(), false, true).asInstanceOf[HashMap]; + + _defaultq1( i + offset ) = vmap( offset, this.defaultq( i ) ); + i = i + 1; + } + if ((_qbinders1 != null) &&( qbinders != null )) { + i = 0; + while(i < this.nstates ) { + //System.out.println("hallo"+qbinders); + //System.out.println("qbinders[ i ] :"+qbinders[ i ]); + //assert _qbinders != null; + //System.out.println("_qbinders :"+_qbinders); + + _qbinders1( i + offset ) = qbinders( i ); + i = i + 1 + } + } + } + + + /** if there is more than one initial state, a new initial state + * is created, with index 0 + */ + def normalize( initials:TreeSet , reloc:boolean ): Unit = { + //if( initials.size() == 1 ) + // return; + + var idelta = new HashMap(); + var idefault = new TreeSet(); + + var q0 = new Integer( 0 ); + + var it = initials.iterator(); + while(it.hasNext()) { + + val ostate = it.next().asInstanceOf[Integer]; + + val finTag = finals.get( ostate ).asInstanceOf[Integer] ; + if(( finTag != null ) && ( finals.get( q0 ) == null)) + finals.put( q0, finTag ); + + + var tmp = deltaq( ostate ); + + if( reloc ) + tmp = mapmap( tmp, 1, new HashMap(), false, true ).asInstanceOf[HashMap]; + + val labs = tmp.keySet().iterator(); + while(labs.hasNext()) { + val lab = labs.next(); + var itarget = idelta.get( lab ).asInstanceOf[Vector]; + if( null == itarget ) + idelta.put( lab, {itarget = new Vector(); itarget}); + val otarget = tmp.get( lab ).asInstanceOf[Vector]; + itarget.addAll( otarget ); + } + //System.out.println( "normalize:defaultq[ "+ostate+" ] "+((Vector[]) defaultq) [ ostate.intValue() ]); + if( defaultq( ostate ) != null ) + idefault.addAll( defaultq( ostate ) ); + } + + if( reloc ) { + val m = 1 + this.nstates; + val _finals = new TreeMap(); + val _deltaq = new Array[HashMap]( m ); + val _defaultq = new Array[Vector]( m ); + var _qbinders: Array[Vector] = null; + + if( qbinders != null ) + _qbinders = new Array[Vector]( m ); + + relocate( 1, _finals, _deltaq, _defaultq, _qbinders ); + + this.nstates = m; + this.finals = _finals; + this._deltaq = _deltaq; + this._defaultq = _defaultq; + this.qbinders = _qbinders; + } + + this._deltaq ( 0 ) = idelta; + //System.out.println("normalize:deltaq[ 0 ]"+ idelta ); + this._defaultq( 0 ) = new Vector( idefault ); + + //System.out.println("normalize:defaultq[ 0 ]"+ idefault ); + + this.initials = new TreeSet(); + this.initials.add( q0 ); + } + + + /** called from Berry-Sethi construction. + */ + + def this(nstates:int, _labels:HashSet, initials: TreeSet, finals:TreeMap, deltaq:Array[HashMap], defaultq:Array[Vector], qbinders:Object ) = { + this(); + //Console.println("NWA::this(. . . . )"); + this.nstates = nstates; + this.labels = _labels; + this.initials = initials; + this.finals = finals; + this._deltaq = deltaq; + this._defaultq = defaultq; + this.qbinders = qbinders.asInstanceOf[Array[Vector]]; + //print(); + //System.exit(0); + } + + + + var offset:Array[int] = _; // only used if constructed from multiple + + def collectLabels( nfa:Array[NondetWordAutom ] ): Unit = { + this.labels = new HashSet(); + var i = 0; + while(i < nfa.length) { + this.labels.addAll( nfa( i ).labels ); + i = i + 1 + } + } + + def collectOffsets( nfa:Array[NondetWordAutom] ): Unit = { + this.offset = new Array[int]( nfa.length + 1 ); + offset( 0 ) = 1; // we have a new initial state + var i = 0; + while(i < nfa.length ) { + offset( i + 1 ) = nfa( i ).nstates + offset( i ); + i = i + 1 + } + } + + /** collapses several normalized NondetWordAutom objects into one. + */ + + def this( nfa: Array[NondetWordAutom] ) = { + this(); + //Console.println("NWA::this(.)"); + + //this.m + val m = nfa.length; + //System.out.println("enter NondetWordSwitch, " + // +"combining " + m + " automata"); + + collectLabels( nfa ); + collectOffsets( nfa ); + + //Console.println(" X 1"); + + + this.nstates = offset( nfa.length ); //m - 1 ] + nfa[ m - 1 ].nstates; + + + this.finals = new TreeMap(); + + this.qbinders = new Array[Vector]( nstates ); + + // new initial state gets all transitions from all initial states + + this._deltaq = new Array[HashMap]( nstates ); + this._defaultq = new Array[Vector]( nstates ); + //Console.println(" X 2"); + + //TreeSet defaultqSet = new TreeSet(); + _deltaq( 0 ) = new HashMap(); // 0 = our new initial state + + val initials = new TreeSet(); + + var i = 0; + while(i < m) { + //System.out.println("i (current NFA):"+i); + + val n = nfa( i ); + + val offs = offset( i ); + + initials.add( new Integer( offs )); + + n.relocate( offs, + this.finals, + this._deltaq, + this._defaultq, + this.qbinders ); + i = i + 1; + } + + normalize( initials, false ); + //Console.println("Leave-NWA::this(.)"); + } + + + + + def print(): Unit = { + + Console.print("NFA on labels "+ this.labels); + + if( offset != null ) { + Console.print("offset"); + var k = 0; + while(k < offset.length) { + if( k > 0) + Console.print(", "); + Console.print(offset(k)); + k = k + 1; + } + } + Console.println; + + Console.print("max state number :" + (nstates - 1) ); + + Console.println("initials" + initials); + + Console.println("finals" + finals); + + var i = 0; + while(i < nstates) { + Console.print("state: " + i); + if( finals.containsKey( new Integer( i )) ){ + Console.print("*"); //final + } + Console.print(" transitions: {"); + var arrows:HashMap = deltaq( i ); + + var it = arrows.keySet().iterator(); + while(it.hasNext()) { + val label = it.next(); + val targets = arrows.get( label ).asInstanceOf[Vector]; + val jt = targets.iterator(); + while(jt.hasNext()) { + val p = jt.next().asInstanceOf[Integer]; + Console.print("("+label+","+p+")"); + } + } + + Console.print("} "); + Console.print(" default transitions: "+_defaultq( i )); + if( null != qbinders ) + Console.println(" binders "+qbinders( i )); + Console.println; + i = i + 1; + } + } + + +} +} diff --git a/sources/scala/tools/scalac/transformer/matching/Npair.scala b/sources/scala/tools/scalac/transformer/matching/Npair.scala new file mode 100644 index 0000000000..41d09fa510 --- /dev/null +++ b/sources/scala/tools/scalac/transformer/matching/Npair.scala @@ -0,0 +1,61 @@ +package scala.tools.scalac.transformer.matching ; + +import java.util.{ HashMap, TreeSet }; +/** cartesian + */ + +/** Int x TreeSet[ Int ] + */ +case class Npair(nstate: Integer, nset: TreeSet) { + + override def equals(that: Any): Boolean = { + this.match { + case Npair( nstate, nset ) => + that.match { + case Npair( _nstate, _nset ) => + return ((nstate == _nstate) + &&( nset == _nset )); + case _ => return false + } + case _ => return false + } + } + + override def toString(): String = { + this.match { + case Npair( nstate, nset ) => + //Integer dstate = (Integer) indexMap.get( nset ); + return "<n"+nstate.toString()+" in "+nset /*+" = d"+dstate*/ +">"; + case _ => null + } + } + + def toString(indexMap: HashMap): String = { + //assert indexMap != null; + this.match { + case Npair( nstate, nset ) => + //assert nstate!=null; + val dstate = indexMap.get( nset ).asInstanceOf[Integer]; + return "<n"+nstate.toString()+" in "+nset +" = d"+dstate +">"; + case _ => + return null; + } + } + + +} + +class NpairComparator extends StateSetComparator { + override def compare( o1: Any, o2: Any ): Int = { + o1.match { + case Npair( nstate, nset ) => o2.match { + case Npair( _nstate, _nset ) => + val res = nstate.compareTo( _nstate ); + if( res != 0 ) + return res; + else + return super.compare( nset, _nset ); + } + } + } +} diff --git a/sources/scala/tools/scalac/transformer/matching/RightTracerInScala.scala b/sources/scala/tools/scalac/transformer/matching/RightTracerInScala.scala index 74d804db12..08a395225d 100644 --- a/sources/scala/tools/scalac/transformer/matching/RightTracerInScala.scala +++ b/sources/scala/tools/scalac/transformer/matching/RightTracerInScala.scala @@ -15,10 +15,6 @@ import scalac.util.Names ; import scala.tools.util.Position; -//import scalac.transformer.matching.CodeFactory ; -import scalac.transformer.matching.DetWordAutom ; -import scalac.transformer.matching.Label ; - package scala.tools.scalac.transformer.matching { /** translate right tracer to code @@ -170,7 +166,7 @@ extends TracerInScala( dfa, elementType, owner, cf ) { */ def code_state0_NEW(): Tree = { // careful, map Int to Int - val hmap = dfa.deltaq( 0 ).asInstanceOf[HashMap]; // all the initial states + val hmap = dfa.deltaq( 0 ); // all the initial states var i = 0; val n = hmap.keySet().size(); // all transitions defined @@ -209,7 +205,7 @@ extends TracerInScala( dfa, elementType, owner, cf ) { override def currentMatches(label: Label): Tree = { label.match { - case Label.Pair( target, theLab ) => + case LPair( target, theLab ) => cf.Equals( gen.mkIntLit( cf.pos, target.intValue() ), current() ); case _ => throw new ApplicationError("expected Pair label"); @@ -218,11 +214,11 @@ extends TracerInScala( dfa, elementType, owner, cf ) { override def code_state_NEW(i: Int): Tree = { // precondition i != 0 - var stateBody = code_delta( i, Label.DefaultLabel ); + var stateBody = code_delta( i, DefaultLabel() ); if( stateBody == null ) { stateBody = code_error(); } - val trans = dfa.deltaq.asInstanceOf[Array[HashMap]]( i ); + val trans = dfa.deltaq( i ); val tmapTag = new TreeMap(); val tmapBody = new TreeMap(); var j = 0; @@ -234,7 +230,7 @@ extends TracerInScala( dfa, elementType, owner, cf ) { if( action != null ) { val J = new Integer( j ); - tmapTag.put( label.asInstanceOf[Label.Pair].state, J ); + tmapTag.put( label.asInstanceOf[LPair].state, J ); tmapBody.put( J, action ); stateBody = gen.If( currentMatches( label.asInstanceOf[Label] ), @@ -363,7 +359,7 @@ extends TracerInScala( dfa, elementType, owner, cf ) { * returns null if there is no such transition(no translation needed) */ override def code_delta(i: Int , label: Label ): Tree = { - val hmap = dfa.deltaq( i ).asInstanceOf[HashMap]; + val hmap = dfa.deltaq( i ); val ntarget = hmap.get( label ).asInstanceOf[Integer]; var algMatchTree: Tree = null; if( ntarget == null ) @@ -372,15 +368,15 @@ extends TracerInScala( dfa, elementType, owner, cf ) { //System.out.println("delta("+i+","+label+")" ); var theLab: Label = null; label.match { - case Label.Pair( state, lab2 )=> + case LPair ( state, lab2 )=> //assert ntarget == state; theLab = lab2; lab2.match { - case Label.TreeLabel( pat ) => + case TreeLabel( pat ) => algMatchTree = _cur_match( pat ); case _ => } - case Label.DefaultLabel => + case DefaultLabel() => throw new ApplicationError(); // should not happen } //assert dfa.qbinders != null : "qbinders ?"; diff --git a/sources/scala/tools/scalac/transformer/matching/SequenceMatcher.scala b/sources/scala/tools/scalac/transformer/matching/SequenceMatcher.scala index a9e43e211b..fbce115eea 100644 --- a/sources/scala/tools/scalac/transformer/matching/SequenceMatcher.scala +++ b/sources/scala/tools/scalac/transformer/matching/SequenceMatcher.scala @@ -12,13 +12,6 @@ import scalac.symtab._ ; import java.util._ ; import scala.tools.util.Position; -//import scalac.transformer.matching.PatternTool; - -import scalac.transformer.matching.{BerrySethi, BindingBerrySethi}; -//import scalac.transformer.matching.CodeFactory; -import scalac.transformer.matching.DetWordAutom; -import scalac.transformer.matching.Label; -import scalac.transformer.matching.NondetWordAutom; package scala.tools.scalac.transformer.matching { /** constructs a matcher for a sequence pattern. plays two roles in @@ -29,6 +22,7 @@ package scala.tools.scalac.transformer.matching { class SequenceMatcher(unit: CompilationUnit) extends PatternTool(unit) { +// Console.println("CONSTR SEQUENCEMATCHER"); final val IGNORED = new Integer(42); var cf: CodeFactory = _; @@ -42,7 +36,7 @@ class SequenceMatcher(unit: CompilationUnit) extends PatternTool(unit) { def collectNfaVariables(nfa: NondetWordAutom): Set = { val seqVars = new HashSet(); var j = 0; - while(j < nfa.nstates()) { + while(j < nfa.nstates) { if( nfa.qbinders( j ) != null ) seqVars.addAll( nfa.qbinders( j ) ); j = j + 1 diff --git a/sources/scala/tools/scalac/transformer/matching/StateSetComparator.scala b/sources/scala/tools/scalac/transformer/matching/StateSetComparator.scala new file mode 100644 index 0000000000..c57e9c8f74 --- /dev/null +++ b/sources/scala/tools/scalac/transformer/matching/StateSetComparator.scala @@ -0,0 +1,34 @@ +package scala.tools.scalac.transformer.matching ; + +import java.util.{Comparator, TreeSet} ; + +class StateSetComparator extends Comparator { + // use lexicographic order + def compare(o1: Any , o2: Any ): Int = { + /* + System.out.print("lexi" ); + System.out.print( o1 +" "); + System.out.println( o2 ); + */ + val it1 = o1.asInstanceOf[TreeSet].iterator(); + val it2 = o2.asInstanceOf[TreeSet].iterator(); + while( it1.hasNext() ) { + while( it2.hasNext() ) { + if( !it1.hasNext() ) + return -1; + + val i1 = it1.next().asInstanceOf[Integer].intValue(); + val i2 = it2.next().asInstanceOf[Integer].intValue(); + if( i1 < i2 ) + return -1; + else if ( i1 > i2 ) + return 1; + } + if( it1.hasNext() ) + return 1; + } + if( it2.hasNext() ) + return -1; + return 0; + } +} diff --git a/sources/scala/tools/scalac/transformer/matching/TracerInScala.scala b/sources/scala/tools/scalac/transformer/matching/TracerInScala.scala index 79a573c62a..5838ed7991 100644 --- a/sources/scala/tools/scalac/transformer/matching/TracerInScala.scala +++ b/sources/scala/tools/scalac/transformer/matching/TracerInScala.scala @@ -1,8 +1,6 @@ import scalac.ast.Tree; import scalac.symtab.Symbol; import scalac.symtab.Type; -//import scalac.transformer.matching.CodeFactory ; -import scalac.transformer.matching.DetWordAutom ; package scala.tools.scalac.transformer.matching { /** @todo: factor common things of LeftTracerInScala and RightTracerInScala diff --git a/sources/scala/tools/scalac/transformer/matching/WordAutomInScala.scala b/sources/scala/tools/scalac/transformer/matching/WordAutomInScala.scala index 2ce7ddb3f1..c04972af37 100644 --- a/sources/scala/tools/scalac/transformer/matching/WordAutomInScala.scala +++ b/sources/scala/tools/scalac/transformer/matching/WordAutomInScala.scala @@ -16,15 +16,11 @@ import scalac.ast.TreeGen; import scalac.symtab.Type; import scalac.symtab.Symbol; import scalac.symtab.Modifiers; // test -//import scalac.typechecker.*; import Tree._; import java.util._; import scala.tools.scalac.util.NewArray; -//import scalac.transformer.matching.CodeFactory; -import scalac.transformer.matching.DetWordAutom; -import scalac.transformer.matching.Label; import scalac.util.Names; package scala.tools.scalac.transformer.matching { @@ -160,7 +156,7 @@ package scala.tools.scalac.transformer.matching { if (target == null) label.match { - case Label.DefaultLabel => + case DefaultLabel() => code_error(); // this may not happen ! case _ => null; // not good |