From b0142d0b0bea1c67cdaeb7b569b38210976cc296 Mon Sep 17 00:00:00 2001 From: buraq Date: Tue, 28 Jun 2005 11:06:00 +0000 Subject: renamed file --- sources/scala/tools/nsc/matching/BerrySethi.scala | 800 --------------------- sources/scala/tools/nsc/matching/BerrySethis.scala | 800 +++++++++++++++++++++ .../scala/tools/nsc/matching/NondetWordAutom.scala | 522 -------------- .../tools/nsc/matching/NondetWordAutoms.scala | 522 ++++++++++++++ 4 files changed, 1322 insertions(+), 1322 deletions(-) delete mode 100644 sources/scala/tools/nsc/matching/BerrySethi.scala create mode 100644 sources/scala/tools/nsc/matching/BerrySethis.scala delete mode 100644 sources/scala/tools/nsc/matching/NondetWordAutom.scala create mode 100644 sources/scala/tools/nsc/matching/NondetWordAutoms.scala diff --git a/sources/scala/tools/nsc/matching/BerrySethi.scala b/sources/scala/tools/nsc/matching/BerrySethi.scala deleted file mode 100644 index 4e774ad94e..0000000000 --- a/sources/scala/tools/nsc/matching/BerrySethi.scala +++ /dev/null @@ -1,800 +0,0 @@ -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(""); - //DEBUG.print( pat ); - //System.out.println(""); - 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(""); - //DEBUG.print( pat ); - //System.out.println(""); - 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(""); - //DEBUG.print( pat ); - //System.out.println(""); - 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(""); - for( int k = 0; k= 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/BerrySethis.scala b/sources/scala/tools/nsc/matching/BerrySethis.scala new file mode 100644 index 0000000000..4e774ad94e --- /dev/null +++ b/sources/scala/tools/nsc/matching/BerrySethis.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(""); + //DEBUG.print( pat ); + //System.out.println(""); + 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(""); + //DEBUG.print( pat ); + //System.out.println(""); + 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(""); + //DEBUG.print( pat ); + //System.out.println(""); + 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(""); + for( int k = 0; k= 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/NondetWordAutom.scala b/sources/scala/tools/nsc/matching/NondetWordAutom.scala deleted file mode 100644 index cd1d8b576e..0000000000 --- a/sources/scala/tools/nsc/matching/NondetWordAutom.scala +++ /dev/null @@ -1,522 +0,0 @@ -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/NondetWordAutoms.scala b/sources/scala/tools/nsc/matching/NondetWordAutoms.scala new file mode 100644 index 0000000000..cd1d8b576e --- /dev/null +++ b/sources/scala/tools/nsc/matching/NondetWordAutoms.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; + } + } + + +} + +} -- cgit v1.2.3