diff options
Diffstat (limited to 'src/compiler/scala/tools/nsc/matching')
17 files changed, 5918 insertions, 0 deletions
diff --git a/src/compiler/scala/tools/nsc/matching/AlgebraicMatchers.scala b/src/compiler/scala/tools/nsc/matching/AlgebraicMatchers.scala new file mode 100644 index 0000000000..4137b128eb --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/AlgebraicMatchers.scala @@ -0,0 +1,172 @@ +/* NSC -- new scala compiler + * Copyright 2005 LAMP/EPFL + * @author buraq + */ +// $Id$ + +package scala.tools.nsc.matching; + +/** the pattern matcher, tweaked to work with regular patterns + * @author Burak Emir + */ +trait AlgebraicMatchers : TransMatcher { + + import global._; + + class AlgebraicMatcher extends PatternMatcher { + + import java.util.Vector ; + import java.util.Iterator ; + + var _m: PartialMatcher = _; + + override protected var delegateSequenceMatching = true; + override protected var optimize = false; + + /** constructs an algebraic pattern matcher from cases */ + def construct(m: PartialMatcher, cases: List[CaseDef]): Unit = + construct(m, cases, true); + + /** constructs an algebraic pattern matcher from cases */ + def construct(m: PartialMatcher, cases: List[CaseDef], doBinding: Boolean): Unit = { + this._m = m; + super.initialize( _m.selector, _m.owner, doBinding ); + + val it = cases.elements; + while (it.hasNext) { + val cdef = it.next; + /* + if(cdef != null) + Console.println("algebraic matcher: "+cdef.toString()); // DEBUG + else + scala.Predef.error("got CaseDef null in alg matcher!"); + */ + enter(cdef); + } + + //if (unit.global.log()) { + // unit.global.log("internal pattern matching structure"); + // print(); + // } + _m.tree = toTree(); + } + + + /** initializes this AlgebraicMatcher, see Matcher.initialize + void initialize() {} + */ + /* + def isStarApply(tree: Tree.Apply): Boolean = { + val params:Array[Symbol] = tree.fun.getType().valueParams(); + //System.err.println( tree.fun.type.resultType().symbol() ); + (tree.args.length == 1) + && (tree.getType().symbol().flags & Modifiers.CASE) != 0 + && params.length > 0 + && (params(params.length-1).flags & Modifiers.REPEATED) != 0; + } + */ + //////////// generator methods + + override def toTree(): Tree = { + + this.exit = currentOwner.newLabel(root.pos, "exitA") + .setInfo(new MethodType(List(resultType), resultType)); + + val result = exit.newValueParameter(root.pos, "resultA").setInfo( resultType ); + + Block( + List ( + ValDef(root.symbol, _m.selector) + ), + If( super.toTree(root.and), + LabelDef(exit, List(result), Ident(result)), + ThrowMatchError( _m.pos, resultType )) + ); + } + + protected override def toTree(node: PatternNode, selector: Tree): Tree = { + //System.err.println("AM.toTree called"+node); + if (node == null) + Literal(false); + else node match { + case SeqContainerPat( _, _ ) => + callSequenceMatcher( node, + selector ); + case _ => + super.toTree( node, selector ); + } + } + + /** collects all sequence patterns and returns the default + */ + def collectSeqPats(node1: PatternNode, seqPatNodes: Vector, bodies: Vector): PatternNode = { + var node = node1; + var defaultNode: PatternNode = null; + var exit = false; + do { + if( node == null ) + exit=true; //defaultNode = node; // break + else + node match { + case SeqContainerPat( _, _ ) => + seqPatNodes.add( node ); + bodies.add( super.toTree( node.and ) ); + node = node.or; + exit//defaultNode = node; // break; + + case _ => + defaultNode = node; + } + } while (!exit && (null == defaultNode)) ; + + defaultNode; + } + + def callSequenceMatcher(node: PatternNode, selector1: Tree): Tree = { + + //Console.println("calling sequent matcher for"+node); + /* ???????????????????????? necessary to test whether is a Seq? + gen.If(selector.pos, maybe And( Is(selector, seqpat.type()) )???) + */ + + // translate the _.and subtree of this SeqContainerPat + + val seqPatNodes = new Vector(); + val bodies = new Vector(); + + var defaultNode = collectSeqPats(node, seqPatNodes, bodies); + + val defaultCase = toTree(defaultNode, selector1); + + val wordRec = new SequenceMatcher(); + + val m = new PartialMatcher { + val owner = _m.owner; + val selector = selector1; + } + + var pats: scala.List[Tree] = Nil; + var body: scala.List[Tree] = Nil; + + val tmp = bodies.toArray(); + var j = 0; + val it = seqPatNodes.iterator(); + while (it.hasNext()) { + //pats(j) = it.next().asInstanceOf[SeqContainerPat].seqpat; + pats = it.next().asInstanceOf[SeqContainerPat].seqpat :: pats; + //body(j) = tmp(j).asInstanceOf[Tree]; + body = tmp(j).asInstanceOf[Tree] :: body; + j = j + 1; + } + //Tree defaultTree = toTree(node.or, selector); // cdef.body ; + + wordRec.construct(m, pats.reverse, body.reverse, defaultCase, doBinding); + + //_m.defs.addAll(m.defs); + + m.tree; + } + +} // class AlgebraicMatcher + +} diff --git a/src/compiler/scala/tools/nsc/matching/Autom2.scala b/src/compiler/scala/tools/nsc/matching/Autom2.scala new file mode 100644 index 0000000000..b99db700b4 --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/Autom2.scala @@ -0,0 +1,196 @@ +package scala.tools.nsc.matching ; + +//import java.util._ ; + +import scala.tools.nsc.util.Position; + +trait Autom2: TransMatcher { + + import global._; + + /** @param owner owner of the pattern matching expression + */ + abstract class Autom2Scala { + + val dfa: DetWordAutom; + val owner: Symbol; + + protected var optimize = true; + + final val FAIL = -1; + + /** symbol of the matcher DefDef or Label */ + var funSym:Symbol = _; + + /** symbol of the iterator ( scala.SequenceIterator ) */ + var iterSym: Symbol = _; + + /** symbol of the switching result ( scala.Int ) */ + var resultSym: Symbol = _; + + /** symbol of the state variable ( scala.Int ) */ + var stateSym: Symbol = _; + + /** symbol of variable holding current label */ + var curSym: Symbol = _; + + /** symbol of boolean variable that indicates we have not reached end of sequence */ + var hasnSym: Symbol = _; + + val am = new AlgebraicMatcher(); + + var pos: Int = Position.FIRSTPOS; + + val elementType: Type; + + def funRetType(): Type = { + funSym.tpe match { + case MethodType( _, retType )=> retType; + case _ => scala.Predef.error("quoi?"); + } + } + + def callFun(args: List[Tree]): Tree = Apply(Ident(funSym),args); + + // overridden in RightTracerInScala + def loadCurrentElem(body: Tree): Tree = { + Block( + List( + ValDef(this.hasnSym, _hasNext( _iter() ) ), + ValDef(this.curSym, If(Ident( hasnSym ), + _next( _iter() ), + EmptyTree)) + ), + body + ); + } + + /** bug ?? */ + def currentElem() = { Ident( curSym ) } + + def currentMatches(label: Label): Tree = { + label match { + case TreeLabel( pat ) => + _cur_match( pat ); + case SimpleLabel(lit: Literal) => + Equals( currentElem(), lit ); + case _ => // cannot happen + scala.Predef.error("expected either algebraic or simple label:"+label); + } + } + + // + // translation of automata to scala code + // + + + /** `[switchResult]' */ + def _swres(): Tree = { Ident( resultSym );} + + /** `<state>' param */ + def _state(): Tree = { Ident( stateSym ); } + + /** `<iterator>' param */ + def _iter(): Tree = { Ident( iterSym ); } + + /** simple optimization: if we are in a sink state, stop traversing sequence + */ + def stateWrap(i: Int): Tree = { + if( dfa.isSink( i )) + run_finished( i ); // state won't change! optimization + else + If( Negate( Ident( hasnSym )), + run_finished( i ), + code_state_NEW( i )); + } + + /** body of the matcherDefFun + */ + def code_body_NEW(): Tree = { + var cases: List[CaseDef] = Nil; + + //val tags = new Array[Int](dfa.nstates()); + //val bodies = new Array[Tree](dfa.nstates()); + var i = 0; while (i < dfa.nstates()) { + cases = CaseDef( Literal(i), stateWrap(i)) :: cases; + i = i + 1; + } + //if( optimize ) + loadCurrentElem( Match( _state(), cases )); + + /* + Tree res = code_error(); + for( int i = dfa.nstates-2; i>= 0; i-- ) + res = gen.If( Equals( _state(), gen.mkIntLit( pos, i )), + bodies[ i ] , + res ); + + return loadCurrentElem( res ); + */ + } + + /* calling the (AlgebraicMatcher)PatternMatcher here */ + def _cur_match(pat: Tree): Tree = { + val m: PartialMatcher = new PartialMatcher { + val owner = Autom2Scala.this.funSym; /* owner*/ + val selector = currentElem(); /* root */ + /* defs.boolean_TYPE() restype */ + }; + + am.construct( m, List ( + CaseDef( pat, Literal(true)), + CaseDef( Ident(nme.WILDCARD), Literal(false)) + ), + false); + am.toTree(); + } + + // @todo should be abstract + def code_delta( i:Int, label: Label): Tree = { + scala.Predef.error("should not happen"); + } + + /** some error happened which is due to bug in translation/automaton + */ + final def code_error(): Tree = { + ThrowMatchError( pos , funRetType() ); + } + + def code_fail(): Tree = { + Literal( FAIL ); //gen.mkIntLit(Position.FIRSTPOS, FAIL ); + } + + /** code for the return value of the automaton translation + */ + def run_finished(state: Int): Tree = { + if( dfa.isFinal( state )) + Literal( + dfa.finals.get( new Integer( state ) ).asInstanceOf[Integer] + .intValue() + ) + else + Literal( FAIL ); + } + + def code_state_NEW(i: Int): Tree = { + var stateBody = code_delta( i, DefaultLabel() ); + if( stateBody == null ) + stateBody = code_fail(); + val trans = dfa.deltaq( i ); + + val labs = dfa.labels().iterator(); + while(labs.hasNext()) { + val label = labs.next(); + val next = trans.get( label ).asInstanceOf[Integer]; + val action = code_delta( i, label.asInstanceOf[Label] ); + if( action != null ) { + /*assert*/ //stateBody != null : "stateBody is null"; + stateBody = If( currentMatches(label.asInstanceOf[Label] ), + action, + stateBody); + } + } + stateBody; + } + } +} diff --git a/src/compiler/scala/tools/nsc/matching/BerrySethis.scala b/src/compiler/scala/tools/nsc/matching/BerrySethis.scala new file mode 100644 index 0000000000..85638903b0 --- /dev/null +++ b/src/compiler/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("<nullable>"); + //DEBUG.print( pat ); + //System.out.println("</nullable>"); + pat match { + case Apply(_, _) => false; + case Sequence( trees ) => trees.isEmpty || (trees forall {nullable}); + case Star(t) => true; // ? new + case Bind(n, t) => nullable( t ); + case Alternative(choices) => choices exists {nullable} + case _ => false; + } + + + + /** returns true if a Sequence pattern matches the empty sequence + * @param pat the sequence pattern. + def nullableSequence(pat: Tree): Boolean = + pat match { + case Sequence(pats) => pats forall {nullable}; + } + } + */ + + /** returns true if a sequence of patterns (usually children of a + * sequence or subsequence node) is nullable. + * @param pats the sequence of patterns + def nullable(pats: Array[Tree]): Boolean = { + var result = true; + var i = 0; + while(i < pats.length && result){ + result = result && nullable( pats( i ) ); + i = i + 1 + } + return result; + } + */ + + /** computes first( alpha ) where alpha is a word regexp + */ + + def compFirst( pat:Tree ): TreeSet = { + //System.out.print("<compFirst>"); + //DEBUG.print( pat ); + //System.out.println("</compFirst>"); + pat match { + case Sequence( trees ) => + return compFirst( trees ); + case Typed(_,_) | Select(_,_) | Apply(_, _) => + val tmp = new TreeSet(); + tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set + return tmp; + + case Literal( _ ) => + val tmp = new TreeSet(); + tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set + return tmp; + //case Subsequence( Tree[] trees ) => + //return compFirst( trees ); + case Alternative( trees ) => + val tmp = new TreeSet(); + var i = 0; + while(i < trees.length) { + tmp.addAll( compFirst( trees( i ) )); + i = i + 1 + } + return tmp; + + case Bind(_, tree) => + return compFirst(tree); + + case Ident( name ) => + //if (name != Name.fromString("_")) + // error("unexpected pattern"); + val tmp = new TreeSet(); + tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set + return tmp; + + case _ => + scala.Predef.error("unexpected pattern"); + } + } + + + + /** computes last( alpha ) where alpha is a word regexp + */ + def compLast(pat: Tree): TreeSet = { + //System.out.print("<last>"); + //DEBUG.print( pat ); + //System.out.println("</compLast>"); + pat match { + case Sequence( _ ) | Apply(_, _) => + val tmp = new TreeSet(); + tmp.add(posMap.get( pat ).asInstanceOf[Integer]); // singleton set + return tmp; + + case Literal( _ ) => + val tmp = new TreeSet(); + tmp.add( posMap.get( pat ).asInstanceOf[Integer]); // singleton set + return tmp; + + case Alternative( trees ) => + val tmp = new TreeSet(); + var i = 0; + while(i < trees.length) { + tmp.addAll( compLast( trees )); + i = i + 1 + } + return tmp; + + case Bind( _, tree ) => + return compLast( tree ); + + case _ => + scala.Predef.error("unexpected pattern"); + } + } + + + /** computes first(w) where w=alpha_1...alpha_n are successors of a + * sequence node + * @todo make tail recursive + */ + def compFirst( pats:scala.List[Tree] ): TreeSet = pats match { + case List() => new TreeSet(); + case x::xs => + val res = compFirst(x); + if(nullable(x)) + res.addAll(compFirst(xs)); + res + } + + // Unit test ? + + /** computes last(w) where w are successors of a sequence node + */ + def compLast(pats: scala.List[Tree]): TreeSet = pats match { + case List() => new TreeSet(); + + case _ => + /* + System.out.print("<last>"); + for( int k = 0; k<pats.length; k++) { + DEBUG.print( pats[k] ); + System.out.print(" "); + } + System.out.println(); + */ + + var i = pats.length - 1; + var tmp = pats( i ); + val result = compLast( tmp ); + i = i - 1; + while( nullable(tmp) && (i >= 0 )) { + tmp = pats( i ); + result.addAll( compLast( tmp )); + i = i + 1; + } + return result; + } + + // starts from the right-to-left + // precondition: pos is final + // pats are successor patterns of a Sequence node + // returns first-set (== follow set of initial state) + def compFollow(pats: scala.List[Tree]): TreeSet = { + var first:TreeSet = null; + this.recVars = new HashMap(); + var fol = new TreeSet(); + if( pats.length > 0 ) {//non-empty expr + var i = pats.length; + fol.add( new Integer( pos )); // don't modify pos ! + do { + i = i - 1; + first = compFollow1( fol, pats( i ) ); + if( nullable( pats( i ) )) + fol.addAll( first ); + else + fol = first; + //System.out.println("in compFollow: first"+first); + //System.out.println("in compFollow: fol"+fol); + + } while( i > 0 ); + } + this.follow.put(new Integer( 0 ), fol); + return fol; + } + + var recVars: HashMap = _; + + /** returns the first set of an expression, setting the follow set along + * the way + */ + def compFollow1( fol1:TreeSet , pat:Tree ): TreeSet = { + var fol = fol1; + //System.out.println("compFollow1("+fol+","+pat+")"); + pat match { + case Sequence( trees ) => + var first: TreeSet = null; + var i = trees.length; + if( i > 0 ) { // is nonempty + do { + i = i - 1; + first = compFollow1(fol, trees( i )); + if( nullable( trees( i ) )) + fol.addAll( first ); + else + fol = first; + } while( i > 0 ) ; + } + if( null == first ) first = new TreeSet(); + return first; + + case Alternative( choices ) => + val first = new TreeSet(); + var i = choices.length - 1; + while(i >= 0) { + first.addAll( compFollow1( fol, choices( i ) )); + i = i - 1; + } + return first; + + case Star(t) => + + val first = compFirst( t ); + fol.addAll(first); + compFollow1(fol,t); + + case Bind( n, t ) => // == can also be star + + val first = compFirst( t ); + //System.out.print("BIND" + first); + //recVars.put( pat.symbol, first ); + + // if( appearsRightmost( n, t )) + // follow = oldfollw + ownfirst + + //if( isStar( n ) ) + // fol.addAll( first ); // an iterated pattern + + // continue to compute follow sets with adjusted fol + return compFollow1( fol, t ); + + case Ident( n ) => + if ((pat.symbol != null ) + && pat.symbol.isPrimaryConstructor) { + // same as Apply + val pos = this.posMap.get( pat ).asInstanceOf[Integer]; + val tset = fol.clone().asInstanceOf[TreeSet]; + this.follow.put( pos, tset ); + val first = new TreeSet(); + first.add( pos ); + return first; + } + /* + if ( recVars.keySet().contains( pat.symbol )) { // grammar + val first = recVars.get( pat.symbol ).asInstanceOf[TreeSet]; + val follow = fol.clone().asInstanceOf[TreeSet]; + first.addAll( follow ); + //recVars.put//this.follow.put( pat.symbol, follow ); + return first; + } + */ + // --- --- only happens when called from BindingBerrySethi + // [... x ...] changed to [... x@_ ...] + + // non-generated, non-recursive variable should not appear, + // so this is a wildcard pattern _ + + val pos = this.posMap.get( pat ).asInstanceOf[Integer]; + val tset = fol.clone().asInstanceOf[TreeSet]; + this.follow.put( pos, tset ); + val first = new TreeSet(); + first.add( pos ); + //System.out.println("Ident("+n+",...) first:"+first); + //System.out.println("Ident("+n+",...) follow:"+tset); + return first; + + case Apply(_, _) | Literal( _ ) | Typed(_,_) | Select(_,_) => + val pos = this.posMap.get( pat ).asInstanceOf[Integer]; + val tset = fol.clone().asInstanceOf[TreeSet]; + this.follow.put( pos, tset ); + val first = new TreeSet(); + first.add( pos ); + return first; + + case _ => + scala.Predef.error("unexpected pattern: "+pat.getClass()); + } + } + + /** called at the leaves of the regexp + */ + def seenLabel( pat:Tree , i:Integer , label:Label ): Unit = { + this.posMap.put( pat, i ); + this.labelAt.put( i, label ); + if( label != DefaultLabel() ) { + /* + if( this.labels.contains( label ) ) { + switch(label) { + case TreeLabel(Apply(_, Tree[] args)) => + if( args.length > 0 ) { + unit.warning(pat.pos, "if this pattern in nondeterminism, it will not compile correctly"); + } + } + } + */ + this.labels.add( label ); + } + + } + + /** overriden in BindingBerrySethi + */ + def seenLabel( pat:Tree , label:Label ): Unit = { + seenLabel( pat, new Integer( {pos = pos + 1; pos} ), label ); + } + + /** returns "Sethi-length" of a pattern, creating the set of position + * along the way + */ + + var activeBinders:Vector = _; + + // todo: replace global variable pos with acc + def traverse( pat:Tree ): Unit = { + pat match { + + // (is tree automaton stuff, more than Berry-Sethi) + case Apply( _, _ ) | Typed( _, _ )| Select( _, _ ) => + val label = new TreeLabel( pat ); + seenLabel( pat, label ) ; + return ; + + case p @ Literal( _ ) => + val label = new SimpleLabel( p ); + seenLabel( pat, label ) ; + + return ; + + case Sequence( trees ) => + var i = 0; + while(i < trees.length) { + traverse( trees( i ) ); + i = i + 1 + } + return ; + + case Alternative( trees ) => + var i = 0; + while(i < trees.length) { + traverse( trees( i ) ); + i = i + 1 + } + return ; + + case Bind( name, body) => + //recVars.put( pat.symbol, java.lang.Boolean.TRUE ); + //if( !isStar( name ) ) { + activeBinders.add( pat.symbol ); + traverse( body ); + activeBinders.remove( pat.symbol ); + //} + //else + // + case Star(body) => traverse( body ); + + case Ident(name) => + if ((pat.symbol != null ) + && pat.symbol.isPrimaryConstructor) { + // same as Apply + val label = new TreeLabel( pat ); + seenLabel( pat, label ) ; + + return ; + } + + scala.Predef.error("should not get here"); // removed idents? + //if( null != recVars.get( pat.symbol ) ) { + // return ; + //} + // _ and variable x ( == x @ _ ) + val label = DefaultLabel(); + seenLabel( pat, label ); + + return ; + + } + } + + + var finals: TreeMap = _; // final states + + //TreeSet initialsRev; // final states + + var deltaq:Array[HashMap] = _; // delta + + + + var defaultq: Array[Vector] = _; // default transitions + + + //HashMap deltaqRev[]; // delta of Rev + //Vector defaultqRev[]; // default transitions of Rev + + + def makeTransition(srcI:Integer, destI:Integer, label: Label): Unit = { + var src = srcI.intValue() ; + var dest = destI.intValue() ; + var arrows: Vector = null; //, 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 = null; + var revArrows: Vector = null; + 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/src/compiler/scala/tools/nsc/matching/CodeFactory.scala b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala new file mode 100644 index 0000000000..1d6882a0fa --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala @@ -0,0 +1,260 @@ +/* +** $Id$ +*/ +package scala.tools.nsc.matching ; + +import scala.tools.nsc.util.Position; + +[_trait_] abstract class CodeFactory: TransMatcher { + + import global._ ; + + import definitions._; // standard classes and methods + import typer.typed; // methods to type trees + import posAssigner.atPos; // for filling in tree positions + + + /** returns `List[ Tuple2[ scala.Int, <elemType> ] ]' */ + def SeqTraceType( elemType: Type ): Type = { + appliedType(definitions.ListClass.typeConstructor, + List(pairType(definitions.IntClass.info, + elemType))) + } + + + + def pairType(left: Type, right: Type) = { + appliedType( definitions.TupleClass(2).typeConstructor, + List(left,right)) + } + + /** returns `Iterator[ elemType ]' */ + def _seqIterType( elemType: Type ): Type = { + appliedType( definitions.IteratorClass.typeConstructor, + List(elemType)) + } + + /** returns A for T <: Sequence[ A ] + */ + def getElemType_Sequence(tpe: Type): Type = { + //System.err.println("getElemType_Sequence("+tpe.widen()+")"); + val tpe1 = tpe.widen.baseType( definitions.SeqClass ); + + if( tpe1 == NoType ) + Predef.error("arg "+tpe+" not subtype of Seq[ A ]"); + + return tpe1.typeArgs( 0 ); + } + + + // --------- these are new + + /** a faked switch statement + */ + def Switch(condition: Array[Tree], body: Array[Tree], defaultBody: Tree): Tree = { + //assert condition != null:"cond is null"; + //assert body != null:"body is null"; + //assert defaultBody != null:"defaultBody is null"; + var result = defaultBody; + + var i = condition.length-1; + while (i >= 0) { + result = If(condition(i), body(i), result); + i = i - 1 + } + + return result ; + } + + /** returns code `<seqObj>.elements' */ + def newIterator( seqObj:Tree ): Tree = + Apply(Select(seqObj, newTermName("elements")), List()); + + + /** `it.next()' */ + def _next(iter: Tree) = + Apply(Select(iter, definitions.Iterator_next), List()); + + + /** `it.hasNext()' */ + def _hasNext(iter: Tree) = + Apply(Select(iter, definitions.Iterator_hasNext), List()); + + + /** `!it.hasCur()' */ + def _not_hasNext( iter:Tree ) = + Apply(Select(_hasNext(iter), definitions.Boolean_not), List()); + + + /** `trace.isEmpty' */ + def isEmpty( iter: Tree ): Tree = + Apply(Select(iter, definitions.List_isEmpty), List()); + + + /** `arg.head' */ + def SeqList_head( arg: Tree ) = + Apply(Select(arg, definitions.List_head), List()); + + + def Negate(tree: Tree) = tree match { + case Literal(Constant(value:Boolean))=> + Literal(Constant(!value)) + case _ => + Apply(Select(tree, definitions.Boolean_not), List()); + } + + /*protected*/ def And(left: Tree, right: Tree): Tree = left match { + case Literal(Constant(value:Boolean)) => + if(value) right else left; + case _ => + right match { + case Literal(Constant(true)) => + left; + case _ => + Apply(Select(left, definitions.Boolean_and), List(right)); + } + } + + /*protected*/ def Or(left: Tree, right: Tree): Tree = { + left match { +/* + case If(cond: Tree, thenp: Tree, Literal(Constant(false))) => // little opt, frequent special case + If(cond, thenp, right) +*/ + case Literal(Constant(value: Boolean))=> + if(value) left else right; + case _ => + right match { + case Literal(Constant(false)) => + left; + case _ => + Apply(Select(left, definitions.Boolean_or), List(right)); + } + } + } + + // used by Equals + private def getCoerceToInt(left: Type): Symbol = { + val sym = left.nonPrivateMember( nme.coerce ); + //assert sym != Symbol.NONE : Debug.show(left); + + sym.alternatives.find { + x => x.info match { + case MethodType(vparams, restpe) => + vparams.length == 0 && isSameType(restpe,definitions.IntClass.info) + } + }.get + } + + // used by Equals +/* + private def getEqEq(left: Type, right: Type): Symbol = { + //Console.println("getEqeq of left == "+left); + val sym = left.nonPrivateMember( nme.EQEQ ); + + + //if (sym == NoSymbol) + // error("no eqeq for "+left); + // : Debug.show(left) + "::" + Debug.show(left.members()); + + var fun: Symbol = null; + var ftype:Type = null; // faster than `definitions.AnyClass.tpe' + sym.alternatives.foreach { + x => + //Console.println("getEqEq: "+x); + val vparams = x.info.paramTypes; + //Console.println("vparams.length == "+vparams.length); + + if (vparams.length == 1) { + val vptype = vparams(0); + //Console.println("vptype == "+vptype); + //Console.println(" ftype == "+ftype); + //Console.println(" cond1 == "+isSubType(right, vptype)); + //Console.println(" cond2("+vptype+","+ftype+") == "+(ftype == null || isSubType(vptype, ftype))); + //Console.println("vptype.getClass "+vptype.getClass()); + if (isSubType(right, vptype) && (ftype == null || isSubType(vptype, ftype)) ) { + fun = x; + ftype = vptype; + //Console.println("fun now: "+fun+" ftype now "+ftype); + } + } + } + //if (fun == null) scala.Predef.error("couldn't find eqeq for left"+left); + fun; + } +*/ + def Equals(left: Tree , right: Tree ): Tree = Apply(Select(left, nme.EQEQ), List(right)); +/* { var left = left1; + var right = right1; +*/ +/* + //Console.println("CodeFactory:: left.tpe =" + left.tpe + " right.tpe "+right.tpe+")"); + val ltype = left.tpe.widen; + var rtype = right.tpe.widen; + if (isSameType(ltype, rtype) + && (isSameType(ltype, definitions.CharClass.info) + || isSameType(ltype,definitions.ByteClass.info) + || isSameType(ltype,definitions.ShortClass.info))) + { + //Console.println("getcoerce"+getCoerceToInt(rtype)); + //Console.println("getcoerce.tpe"+getCoerceToInt(rtype).tpe); + right = Apply(Select(right, getCoerceToInt(rtype)), List()); + rtype = definitions.IntClass.info; + } + val eqsym = getEqEq(ltype, rtype); +*/ + //Console.println("eqsym "+eqsym); + //Console.println("eqsym.tpe "+eqsym.tpe); +// Apply(Select(left1, nme.EQEQ/*eqsym*/), List(right1)); +// } + + def ThrowMatchError(pos: Int, tpe: Type ) = + atPos(pos) { + Throw( + New( + TypeTree(definitions.MatchErrorClass.tpe), + List(List( + Literal(cunit.toString()), + Literal(Position.line(cunit.source, pos)))))) + } + +/* + Apply( + TypeApply( + gen.mkRef(definitions.MatchError_fail), + List(TypeTree(tpe)) + ), + List( + Literal(cunit.toString()), + Literal(Position.line(cunit.source, pos)) + ) + ); +*/ + + /* // ?! + def ThrowMatchError(pos:int , tree:Tree ) = + Apply( + gen.mkRef(definitions.MatchError_report), + List( + Literal(cunit.toString()), + Literal(Position.line(cunit.source, pos)), + tree + ) + ); + */ + +// def Error(pos: Int) = +// ThrowMatchError(pos); + + + /* + def newPair(left: Tree, right: Tree) = + New( + Apply( + gen.mkRef(definitions.TupleClass(2)), + List(left,right) + ) + ); + */ +} + diff --git a/src/compiler/scala/tools/nsc/matching/DetWordAutoms.scala b/src/compiler/scala/tools/nsc/matching/DetWordAutoms.scala new file mode 100644 index 0000000000..8e4d2943be --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/DetWordAutoms.scala @@ -0,0 +1,884 @@ +/* NSC -- new scala compiler + * Copyright 2005 LAMP/EPFL + * @author buraq + */ +// $Id$ +package scala.tools.nsc.matching ; + +import java.util._ ; + +trait DetWordAutoms: TransMatcher { + +import global._; +class DetWordAutom { + + /** determinization -- standard algorithm considering only + * reachable states + */ + def this(nfa: NondetWordAutom) = { + this(); + //Console.println("DWA:this(.)"); + //Console.println(nfa.nstates); + //nfa.print(); + determinize( nfa ); + //Console.println(_nstates); + } + + //final static Integer FINTAG = new Integer(0); + + /** number of states */ + var _nstates:int =0; + + /** the 'alphabet' */ + var _labels:HashSet = _; + + /** the set of final states, here as a TreeMap */ + /*protected*/ var finals:TreeMap = _; + + /** dfa: HashMap trans: Object -> Integer + * nfa: HashMap trans: Object -> Vector [ Integer ] + * + * nfa: Integer ->(Object -> Vector [ Int ]) + * [q] |->( a |-> { q' | (q,a,q') in \deltaright } ) + * + * dfa: Integer ->(Object -> Int) + * [q] |->( a |-> q' | \deltaright(q,a) = q' } ) + */ + + var _deltaq: Array[HashMap] = _; + + var _defaultq: Array[Integer] = _; // this gives the default transitions + + //protected HashMap deltaq[]; + + // --- accessor methods + + /** returns number of states + */ + def nstates(): Int = _nstates; + + /** returns the labels + */ + def labels(): HashSet = _labels; + + /** returns the transitions + */ + def deltaq( state:int ): HashMap = _deltaq( state ); + + /** returns the transitions + */ + def deltaq( state:Integer ): HashMap = _deltaq( state.intValue() ); + + /** for a set of nfa states (that must exist), returns its transitions + */ + def deltaq(nset: TreeSet): HashMap = + deltaq( indexMap.get( nset ).asInstanceOf[Integer] ); + + /** for a set of nfa states (that must exist), returns its transitions + */ + def defaultq( nset:TreeSet ): Integer = + defaultq( indexMap.get( nset ).asInstanceOf[Integer] ); + + /** returns the transitions + */ + def defaultq( state: int ): Integer = + _defaultq( state ); + + /** returns the transitions + */ + def defaultq( state: Integer ): Integer = + _defaultq( state.intValue() ); + + /** returns true if the state is final + */ + def isFinal(state: int): boolean = + ((finals != null) + && (finals.get( new Integer( state )) != null)); + + /** returns true if the state is final + */ + def isFinal(state: Integer): boolean = { + return ((finals != null) && finals.containsKey( state )); + } + + /** returns true if the state is final + */ + def finalTag( state:Integer ): Integer = { + return finals.get( state ).asInstanceOf[Integer]; + } + + + def finalTag( state: int ): Integer = { + return finals.get( new Integer (state )).asInstanceOf[Integer]; + } + + /** returns true if the set of states contains at least one final state + */ + def containsFinal( Q: TreeSet ): boolean = { + val it = Q.iterator(); + while(it.hasNext()) { + if( isFinal(it.next().asInstanceOf[Integer])) + return true; + } + return false; + } + + + /** returns true if there are no finite states + */ + def isEmpty(): boolean = { + return finals.isEmpty(); + } + + // END stuff from FiniteAutom + + final val FIRST: int = 0; + final val LAST: int = FIRST + 1; + + //static final int WHICH_LONGEST_MATCH = FIRST ; + final val WHICH_LONGEST_MATCH:int = LAST ; + + // inherited from FiniteAutom: + + // int nstates; // number of states + // HashSet labels;// the alphabet + // TreeMap finals; + + // HashMap deltaq[]; + //Integer defaultq[]; + + + // TEMPORARY VAR used only during determinization and debug printing + // Q -> (Label -> Q ) + var delta/*Map*/ : 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 = null; // temp: Set[Set[Integer]] + var deftrans:HashMap = null; // Set[Integer] -> Int + + var trans: HashMap = null; // always points to a mapping ( Label -> Q ) + var ix = 0; // state index + + this._labels = nfa.labels; + ////System.out.println("Labels: "+labels); + this.delta/*Map*/ = 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/*Map*/.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 = null; + 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/*Map*/.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 = null; + 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/*Map*/.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 = null; + label match { + case DefaultLabel() => + if (! hasDefault(i)) + return null; + return _defaultq( i ).asInstanceOf[Integer] ; + case SimpleLabel( _ ) | TreeLabel( _ ) => + return _deltaq( i ).get( label ).asInstanceOf[Integer] ; + /*case LPair( Integer state, Label lab ): + return state; + */ + case _ => + scala.Predef.error("whut's this: label="+label+", class "+label.getClass()); + } + } + + def delta(i: Integer, label: Label): Integer = + delta(i.intValue(), label); + + /** should maybe in nfa, not here + */ + /*static */ + protected def smallestFinal( nfa: NondetWordAutom, states:TreeSet ): Integer = { + + var min = Integer.MAX_VALUE ; + val it = states.iterator(); + while (it.hasNext()) { + val state = it.next().asInstanceOf[Integer]; + if( nfa.isFinal( state ) && (state.intValue() < min )) + min = state.intValue(); + } + if (min == Integer.MAX_VALUE) + scala.Predef.error("I expected a final set of states"); + return new Integer( min ); + } + + protected def allSetsThatContain( ndstate: Integer ): Vector = { + val v = new Vector(); + val it = indexMap.keySet().iterator(); + while(it.hasNext()) { + val ndstateSet = it.next().asInstanceOf[TreeSet]; + if( ndstateSet.contains( ndstate )) + v.add( ndstateSet ); + } + return v; + } + + + protected def filterItOutQuoi( dLeft: DetWordAutom, npTarget: Npair,lab:LPair , nsrc:TreeMap ):Unit = { + val theLabel = lab.lab; + val ntarget = lab.state; + + // e.g.[2,(3),4] --> 7 + val dstate = dLeft.indexMap.get( npTarget.nset ).asInstanceOf[Integer]; + + // eg. 3 -> [3] [2,3] + val targets:Vector = dLeft.allSetsThatContain( ntarget ); + + ////System.out.println( targets+", of these " ) ; + + // filter out those source states which arrive here... + val su = targets.iterator(); + while(su.hasNext()) { + val nset = su.next().asInstanceOf[TreeSet]; + val ddelta = dLeft.deltaq( nset ).asInstanceOf[HashMap]; + + // ... at THIS dstate + if(ddelta.get( theLabel ).asInstanceOf[Integer] == dstate ) { + + val np1 = new Npair( ntarget, nset ); + + ////System.out.print( np1.toString( dLeft.indexMap )); + + if( WHICH_LONGEST_MATCH == FIRST ) + addTransitionFLM( nsrc, np1 ); + else + addTransitionLLM( nsrc, np1 ); + } + + } + } + + /** all default transitions from sets that contain nq to npTarget + */ + protected def filterItOutQuoiDefault( dLeft: DetWordAutom ,npTarget:Npair , nq:Integer , nsrc:TreeMap ): Unit = { + + + ////System.out.println( "npTarget = " + npTarget ) ; + + val allSources = dLeft.allSetsThatContain( npTarget.nstate ); + val it = allSources.iterator(); + while(it.hasNext()) { + + // e.g.[2,(3),4] --> 7 + //Integer dstate = (Integer) dLeft.indexMap.get( npTarget.nset ); + + val dstate = dLeft.indexMap.get( it.next() ).asInstanceOf[Integer]; + + //System.out.println( "dstate = " + dstate ) ; + + //assert dstate != null; + + // eg. 3 -> [3] [2,3] + val targets = dLeft.allSetsThatContain( nq ); + + //System.out.println( "targets: " + targets ) ; + + // filter out those source states which arrive here... + val su = targets.iterator(); + while(su.hasNext()) { + val nset = su.next().asInstanceOf[TreeSet]; + val ddef = dLeft.defaultq( nset ); + + //System.out.println( "ddef ="+ddef ); + + // ... at THIS dstate + if( ddef == dstate ) { + + val np1 = new Npair( nq, nset ); + + // print target + //System.out.print( np1.toString( dLeft.indexMap )); + + if( WHICH_LONGEST_MATCH == FIRST ) + addTransitionFLM( nsrc, np1 ); + else + addTransitionLLM( nsrc, np1 ); + + } + + } + } + } + + /** this implements the first longest match policy + */ + protected def addTransitionFLM( nsrc:TreeMap , np:Npair ): Unit= { + val np2 = nsrc.get( np.nset ).asInstanceOf[Npair ]; + + // (policy) first longest match + if(( np2 == null ) + ||( np2.nstate.intValue() > np.nstate.intValue())) { + nsrc.put( np.nset, np ); + } + + } + + /** this implements the last longest match policy (!) + */ + protected def addTransitionLLM(nsrc: TreeMap, np: Npair ): Unit = { + val np2 = nsrc.get( np.nset ).asInstanceOf[Npair]; + + // (policy) first longest match + if(( np2 == null ) + ||( np2.nstate.intValue() < np.nstate.intValue())) { + nsrc.put( np.nset, np ); + } + + } + + + /** build a deterministic right to left transducer from the args + */ + def this(right: NondetWordAutom, left:NondetWordAutom, dLeft: DetWordAutom ) = { + this(); + + /* System.out.println("DetWordAutom.<init>(nfa,nfa,dfa)"); + System.out.println("nfa-left:");left.print(); + System.out.println("nfa-right:");right.print(); + System.out.println("dLeft:"+dLeft.print()); + System.out.println("dLeft.finals"+dLeft.finals); + */ + this.indexMap = dLeft.indexMap; + this.invIndexMap = dLeft.invIndexMap; + // fix indexMap + /* // unnecessary + TreeSet q0 = new TreeSet(); + q0.add( new Integer( 0 )); + indexMap.put( q0, new Integer( 0 )); + //System.out.println("check out the indexMap!" + indexMap); + */ + + val visited_n = new TreeSet( new NpairComparator() ); + val rest = new Stack(); + + // right is "nearly deterministic" + // we can follow reverse traces paths by using dLeft.indexMap + + // start with right.initials, left.final, dLeft.final + val it = dLeft.finals.keySet().iterator(); + while(it.hasNext()) { + val fstate = it.next().asInstanceOf[Integer]; + val nfstate = invIndexMap.get( fstate ).asInstanceOf[TreeSet]; + //System.out.print( "final state:"+fstate); + //System.out.print( " correspond to set of states:"+ nfstate ); + + val min_ndstate: Integer = smallestFinal( left, nfstate ); + + val npair:Npair = new Npair( min_ndstate, nfstate ); + + //System.out.println( " smallest final of these: "+ min_ndstate ); + + + //System.out.println( "push final nfa state "+npair.toString( dLeft.indexMap )); + + if( !visited_n.contains( npair )) { + visited_n.add( npair ); + rest.push( npair ); + } + } + + val ratLab = new HashMap(); // maps nset to label,HashMap + val ratDelta = new HashMap(); // maps nset to Vector[ NP ]targets + + val ratDefault = new HashMap(); // maps nset to NP (one target) + + var ix = 1; + val ix_initial = rest.clone().asInstanceOf[Stack]; + var ix_final = new TreeSet( new NpairComparator() );; + + val newIndexMap = new TreeMap( new NpairComparator() ); + + while( !rest.isEmpty() ) { + + val npair = rest.pop().asInstanceOf[Npair]; + newIndexMap.put( npair, new Integer(ix)); + + ratDelta.put( npair, new Vector() ); + + if( npair.nset.contains( new Integer( 0 )) ) { + ix_final.add( npair ); + } + ix = ix + 1; + + //System.out.println(" popped "+npair.toString( dLeft.indexMap )); + + ////System.out.print(" binders: "); + ////System.out.print( right.qbinders[ npair.nstate.intValue() ] ); + + val delta = right.deltaq( npair.nstate ); + + ////System.out.print(" we could have arrived : "); + //search the delta for target invIndexMap + + val labelToNset = new HashMap(); + val labelToFrom = new HashMap(); + + // maps nsets to the active nstates + var nsrc = new TreeMap( new StateSetComparator() ); + + // berry-sethi construction assures that + // there is only one label for outgoing transitions + var theLabel:Label = null; + + // collect all transition possible in the DFA + val jt = delta.keySet().iterator(); + while(jt.hasNext()) { + val lab = jt.next().asInstanceOf[LPair]; + + // lab.state is the target in the NFA + + if( null == theLabel ) { + ratLab.put( npair, lab.lab ); + ////System.out.print(" with \""+lab.lab+"\" "); + } + theLabel = lab.lab ; + + ////System.out.print("\nfrom n" + lab.state +" ... "); + + // these are too many, filter out those that exist in DFA + + filterItOutQuoi( dLeft, npair, lab, nsrc ); + + } + + + ////System.out.println( "---" ); + + ////System.out.println("all sources: "); + + // !! first longest match + val ut = nsrc.keySet().iterator(); + while(ut.hasNext()) { + val nset = ut.next().asInstanceOf[TreeSet]; + val np2: Npair = nsrc.get( nset ).asInstanceOf[Npair] ; + + //assert( np2 != null ); + ////System.out.println("target: n"+npair.nstate+" via: "+theLabel+" from "+ np2.toString( dLeft.indexMap ));// nset:"+nset+ " namely state n"+ dest); + + val v = ratDelta.get( npair ).asInstanceOf[Vector]; + + v.add( np2 ); + + if( !visited_n.contains( np2 ) ) { + + visited_n.add( np2 ); + rest.push( np2 ); + } + + } + + //System.out.println("default sources: "); + + // maps nsets to the active nstates + nsrc = new TreeMap( new StateSetComparator() ); + + // now for all default transitions that arrive at this nfa state + val defqs = right.defaultq( npair.nstate ); + val kt = defqs.iterator(); + while( kt.hasNext() ) { + val nq = kt.next().asInstanceOf[Integer]; + //System.out.println("checking nq="+nq); + filterItOutQuoiDefault( dLeft, npair, nq, nsrc ); + //System.out.println( "nsrc after "+nq+" is "+nsrc ); + } + + //System.out.println( "defqs :"+defqs ); + //System.out.println( "nsrc :"+nsrc ); + var nut = nsrc.keySet().iterator(); + while(nut.hasNext()) { + + val np2 = nsrc.get( nut.next() ).asInstanceOf[Npair]; + + var v = ratDefault.get( npair ).asInstanceOf[Vector] ; + if( v == null ) + ratDefault.put( npair, {v = new Vector(); v} ); + v.add( np2 ); + + if( !visited_n.contains( np2 ) ) { + + visited_n.add( np2 ); + rest.push( np2 ); + } + + } + + ////System.out.println("zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"); + + } + + // Renumbering + + ////System.out.println( "output: a dfa with "+ix+"states"); + + // FIX: empty regular expression (as in "List()") is valid + //assert ( !ix_final.isEmpty() ) : "no final states found"; + + ////System.out.println( "final state:"+ix_final); + + //System.out.println( "indexMap: " +indexMap); + //System.out.println( "newIndexMap: " +newIndexMap); + this.finals = new TreeMap(); + this._nstates = ix; + val dratDelta = new Array[HashMap]( ix ); + qbinders = new Array[Vector]( ix ); + _labels = new HashSet(); + val kit = ratDelta.keySet().iterator(); + while(kit.hasNext()) { + val np = kit.next().asInstanceOf[Npair]; + + //System.out.print( "\nstate: "+np); + val ndset = np.nset; + val dstate = newIndexMap.get( np ).asInstanceOf[Integer]; + //assert dstate != null : "no dstate for "+np.toString(dLeft.indexMap); + + //System.out.print(" binders:"); + + qbinders( dstate.intValue() ) = left.qbinders( np.nstate.intValue() ); + + //System.out.print( qbinders[dstate.intValue() ]); + + //System.out.println(" transitions:"); + if( ix_final.contains( np ) ) { + val fin_ix = newIndexMap.get( np ).asInstanceOf[Integer]; + finals.put( fin_ix, new Integer( 0 )); + } + + val lab = ratLab.get( np ).asInstanceOf[Label]; + val v = ratDelta.get( np ).asInstanceOf[Vector]; + + val ddelta = new HashMap(); + + // v might be null if there are only default transitions + if( v != null ) { + val it2 = v.iterator(); + while(it2.hasNext()) { + + val np2= it2.next().asInstanceOf[Npair]; + //System.out.print( "("+lab+","+np2+") " ); + val ddestR = newIndexMap.get( np2 ).asInstanceOf[Integer]; + val ddest = indexMap.get( np2.nset ).asInstanceOf[Integer]; + //assert ddest != null : + //"no ddest for " + //+np2.toString(dLeft.indexMap); + + val newLab = new LPair(ddest, lab); + ddelta.put( newLab, ddestR ); + _labels.add( newLab ); + + } + dratDelta( dstate.intValue() ) = ddelta; + + } + } + var itt = ratDefault.keySet().iterator(); + while(itt.hasNext()) { + val np = itt.next().asInstanceOf[Npair]; + val dstate = newIndexMap.get( np ).asInstanceOf[Integer]; + + //System.out.print("\nstate: "+np+" default trans: "); + + val v = ratDefault.get( np ).asInstanceOf[Vector]; + val ut = v.iterator(); + while(ut.hasNext()) { + val np2 = ut.next().asInstanceOf[Npair]; + val targetL = indexMap.get( np2.nset ).asInstanceOf[Integer];; + val targetR = newIndexMap.get( np2 ).asInstanceOf[Integer];; + + val defLab = new LPair( targetL, DefaultLabel() ); + + _labels.add( defLab ); + //System.out.print( "("+defLab+","+np2+") " ); + + var d = dratDelta( dstate.intValue() ); + if( d == null ) + dratDelta( dstate.intValue() ) = {d = new HashMap(); d}; + + d.put( defLab, targetR ); + } + } + + _deltaq = dratDelta; + + val hmap = new HashMap(); + + // final states of left are initial states of right + // problem: still need to choose the one + + while( !ix_initial.isEmpty() ) { + val np = ix_initial.pop().asInstanceOf[Npair]; + + val i = newIndexMap.get( np ).asInstanceOf[Integer]; //R-state + val dtarget = indexMap.get( np.nset ).asInstanceOf[Integer];// left-d-state + + hmap.put( dtarget, i ); + } + _deltaq( 0 ) = hmap; // careful, this maps Int to Int + + qbinders( 0 ) = new Vector(); + //((Vector[])defaultq)[ 0 ] = new Vector(); is null + //printBeforeRAT( dratDelta ); + + } + + def printBeforeRAT1(str: String): Unit = { + val tmp = new StringBuffer( str ); + var j = tmp.length(); + while(j < 20) { + tmp.append(" "); + j = j + 1; + } + Console.println( tmp.toString() ); + } + + def printBeforeRAT( dratDelta: Array[HashMap] ): Unit = { + //System.out.println(); + printBeforeRAT1( "dratDelta" ); + printBeforeRAT1( "[index]" ); + //System.out.println(); + var i = 0; + while(i < dratDelta.length) { + if( isFinal( i )) + printBeforeRAT1( "*"+i ); + else + printBeforeRAT1( " "+i ); + + //System.out.println( dratDelta[ i ] ); + i = i + 1 + } + } + + /** you may only call this before the set[set[...]] representation + * gets flattened. + */ + def printBefore(states: TreeSet, deftrans: HashMap): Unit = { + var trans: HashMap = null; + Console.println(states); + val it = states.iterator(); + while (it.hasNext()) { + val state = it.next().asInstanceOf[TreeSet]; + Console.print("state:" + state.toString() + " transitions "); + trans = delta/*Map*/.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/src/compiler/scala/tools/nsc/matching/LeftTracers.scala b/src/compiler/scala/tools/nsc/matching/LeftTracers.scala new file mode 100644 index 0000000000..b58e11b4cb --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/LeftTracers.scala @@ -0,0 +1,232 @@ +/* NSC -- new scala compiler + * Copyright 2005 LAMP/EPFL + * @author buraq + */ +// $Id$ + +package scala.tools.nsc.matching; + +import java.util._ ; + +import scala.tools.nsc.util.Position; + +trait LeftTracers: TransMatcher { + +import global._; + +abstract class LeftTracerInScala extends Autom2Scala { + + val selector: Tree; + val elementType: Type; + + /** symbol of the accumulator ( scala.SequenceList ) + */ + var accumSym: Symbol = _; + var accumType: Type = _; + var accumTypeArg: Type =_ ; + + def _accumType(elemType: Type): Type = { + SeqTraceType( elemType ); + } + + protected def initializeSyms(): Unit = { + this.funSym = owner.newLabel( pos, fresh.newName( "left" )); + + this.iterSym = owner.newVariable( pos, fresh.newName( "iter" )) + .setInfo( _seqIterType( elementType ) ) ; + + this.stateSym = owner.newVariable( pos, fresh.newName( "q" )) + .setInfo( definitions.IntClass.info ) ; + + this.accumType = _accumType( elementType ); + this.accumTypeArg = accumType.typeArgs( 0 ); + this.accumSym = owner.newVariable( pos, // accumulator + fresh.newName( "acc" )) + .setInfo( accumType ); + + //this.funSym + // .setInfo( new MethodType( new Symbol[] { + // accumSym, iterSym, stateSym}, + // accumType)); + + this.funSym.setInfo( + MethodType( + scala.List ( // dummy symbol MethodType + definitions.IntClass.info, + accumType + ), + accumType) + ); + + //funSym.newValueParameter( pos, fresh.newName( "q" )) + //.setInfo(definitions.IntClass.info), + //funSym.newValueParameter( pos, fresh.newName( "acc" )) + //.setInfo( accumType ) ), + // accumType)); // result type = List[T] + + this.resultSym = owner.newVariable(pos, fresh.newName("trace")) + .setInfo( accumType ) ; + + this.curSym = owner.newVariable( pos, "cur" ) + .setInfo( elementType ); + + this.hasnSym = owner.newVariable( pos, nme.hasNext ) + .setInfo( definitions.BooleanClass.info ); + + } + + /* should throw an exception here really, e.g. MatchError + */ + override def code_fail() = Ident( accumSym ); + + /** returns translation of transition with label from i. + * returns null if there is no such transition(no translation needed) + */ + override def code_delta(i: Int, label: Label): Tree = { + val target = dfa.delta( i, label ); + + /* + System.out.println("LeftTracer:calling dfa.delta("+i+","+label+")"); + System.out.println("result: "+target); + */ + if( target == null ) + null; + else { + // (optimization) that one is a dead state (does not make sense for tracer) + /* + if( target == dfa.nstates - 1 ) + return code_fail(); + */ + + /* + Tree newAcc = newSeqTraceCons(new Integer(i), + currentElem(), + _ref( accumSym )); + */ + val hd = gen.mkNewPair( Literal(i), currentElem() ); + + val newAcc = gen.mkNewCons(hd, Ident(accumSym )); + + //return callFun( new Tree[] { newAcc , _iter(), mkIntLit( pos, target )} ); + callFun( scala.List( Literal(target.intValue() ), newAcc ) ); + } + } + + + def code_body(): Tree = { + + var body = code_error(); // never reached at runtime. + + // state [ nstates-1 ] is the dead state, so we skip it + + //`if( state == q ) <code_state> else {...}' + var i = dfa.nstates() - 2; + while (i >= 0) { + body = code_state(i, body); + i = i - 1; + } + loadCurrentElem(body); + } + + /** return code for state i of the dfa SAME AS IN SUPER, ONLY SINK IS GONE + */ + def code_state(i: Int, elseBody: Tree): Tree = { + + var runFinished: Tree = null; // holds result of the run + var finalSwRes: Int = 0; + + runFinished = run_finished(i); + + var stateBody: Tree = null ; // action(delta) for one particular label/test + + // default action (fail if there is none) + + stateBody = code_delta( i, DefaultLabel()); + + if( stateBody == null ) + stateBody = code_fail(); + // transitions of state i + + val trans = dfa.deltaq( i ); + val labs = dfa.deltaq( i ).keySet().iterator(); + while(labs.hasNext()) { + val label = labs.next(); + val next = trans.get( label ).asInstanceOf[Integer]; + + val action = code_delta( i, label.asInstanceOf[Label] ); + + if( action != null ) { + stateBody = If( currentMatches(label.asInstanceOf[Label]), + action, + stateBody); + } + } + stateBody = If(Negate(Ident(hasnSym)), + runFinished, + stateBody ); + If( Equals( _state(), Literal( i )), + stateBody , + elseBody ); + } + + def getTrace(): Tree = { + + initializeSyms(); + + Block(scala.List( + ValDef( iterSym, newIterator( selector )), + ValDef( stateSym, Literal( 0 ) ), + ValDef( accumSym, gen.mkNil /*mkNil( pos )*/), + ValDef( resultSym, + LabelDef( this.funSym, + scala.List ( + stateSym, + accumSym + ), code_body() /* code_body_new ? */ )) + ), + Ident( resultSym )); + } + + // calling the AlgebraicMatcher here + override def _cur_match(pat: Tree): Tree = { + //return mkBooleanLit(pos, true); + + //System.out.println("calling algebraic matcher on type:" + pat.type); + + val m = new PartialMatcher { + val owner = LeftTracerInScala.this.owner; + val selector = currentElem(); + + // result type definitions.BooleanClass.info ); + } + + pat match { + case Sequence(pats) if containsBinding(pat) => + //scala.Predef.error("should not happen?!"); + null; // Literal(true); ?! + case _ => + am.construct(m, scala.List ( + CaseDef( pat, Literal( true )), + CaseDef( Ident( nme.WILDCARD ), Literal(false)) ), + false); + am.toTree(); + } + } + + + /** return the accumulator + last state + */ + override def run_finished(state: Int): Tree = { + val hd = gen.mkNewPair( Literal(state), EmptyTree); + //System.err.println(hd.type); + gen.mkNewCons(hd, Ident( accumSym )); +/* + mkNewCons(pos, + accumTypeArg, + hd, + Ident( accumSym )); +*/ + } + +} // TracerInScala +} // LeftTracers diff --git a/src/compiler/scala/tools/nsc/matching/MatcherLabels.scala b/src/compiler/scala/tools/nsc/matching/MatcherLabels.scala new file mode 100644 index 0000000000..06c8cd2baa --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/MatcherLabels.scala @@ -0,0 +1,126 @@ +package scala.tools.nsc.matching ; + +[_trait_] abstract class MatcherLabels: TransMatcher { + + import global._ ; + + /** + * This class represents the label that a transition in an automaton + * may carry. These get translated to specific (boolean) tests + */ + + class Label { + + //case class RLabel(Object rstate, Label lab, Symbol vars[]); + + override def hashCode(): Int = this match { + case DefaultLabel() => + return 0; + case SimpleLabel(lit) => + return lit.value.hashCode(); + case TreeLabel(pat) => + // if pat is an Apply, than this case can only be correctly + // handled there are no other similar Applys (nondeterminism) + return pat.tpe.hashCode(); + case TypeLabel(tpe) => + return tpe.hashCode(); + case _ => + return super.hashCode(); + } + + override def equals( o: Any ): Boolean = { + if( !(o.isInstanceOf[Label] )) + return false; + val oL = o.asInstanceOf[Label]; + //System.out.print(this + " equals " + oL); + this match { + case DefaultLabel()=> + oL match { + case DefaultLabel() => + return true; + case _ => false; + } // + case SimpleLabel( lit ) => + oL match { + case SimpleLabel( lit2 ) => + return (/*(lit.kind == lit2.kind) + && */lit.value.equals( lit2.value )); + case _ => false; + } + + case TreeLabel( pat ) => + oL match { + case TreeLabel( pat2 ) => + pat match { + case Apply( _, _ ) => + pat2 match { + case Apply( _, _ ) => + return (treeInfo.methPart/*methSymbol?*/( pat ) + == treeInfo.methPart/*methSymbol*/( pat2 )); + } + case _ => false; + } + case _ => false + } + + case TypeLabel(tpe) => + oL match { + case TypeLabel( tpe2) => + return tpe.equals(tpe2); + case _ => false; + } + case LPair(state, lab) => + oL match { + case LPair(state2, lab2) => + return state.equals(state2) && lab.equals(lab2); + case _ => false; + } + case _ => return false; + } + } + + + def toString2(): String = { + val ext = System.getProperty("extendedMatching"); + if ((ext != null) && ext.equals("true")) { + this match { + case DefaultLabel() => + return "<>:p"+p; + case SimpleLabel( lit ) => + return lit.toString()+":p"+p; + case TreeLabel( pat ) => + return pat.tpe.toString()+":p"+p; + + case _ => scala.Predef.error("this never happens"); + } + } + scala.Predef.error("this never happens"); + } + + override def toString(): String = this match { + case DefaultLabel() => + "<>"; + case SimpleLabel( lit) => + lit.toString(); + case TreeLabel(pat) => + pat.toString(); + case TypeLabel(tpe) => + tpe.toString(); + case LPair(state, lab) => + "(" + state.toString() + "," + lab.toString() + ")"; + case _ => + scala.Predef.error("this never happens"); + } + + val p = -1; // tree state - only needed for extended matching + +} + + case class DefaultLabel() extends Label; + case class SimpleLabel(lit: Literal) extends Label; + case class TreeLabel(pat: Tree) extends Label; // Apply, Sequence + case class TypeLabel(tpe: Type) extends Label; // Apply, Sequence + case class LPair(state: Integer, lab: Label) extends Label; + +} + diff --git a/src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala b/src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala new file mode 100644 index 0000000000..cd1d8b576e --- /dev/null +++ b/src/compiler/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; + } + } + + +} + +} diff --git a/src/compiler/scala/tools/nsc/matching/Npair.scala b/src/compiler/scala/tools/nsc/matching/Npair.scala new file mode 100644 index 0000000000..8cb050de2e --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/Npair.scala @@ -0,0 +1,64 @@ +/* NSC -- new scala compiler + * Copyright 2005 LAMP/EPFL + * @author buraq + */ +// $Id$ +package scala.tools.nsc.matching ; + +import java.util.{ HashMap, TreeSet }; +/** cartesian + */ + +/** Int x TreeSet[ Int ] + */ +case class Npair(nstate: Integer, nset: TreeSet) { + + override def equals(that: Any): Boolean = { + this match { + case Npair(nstate, nset) => + that match { + case Npair(_nstate, _nset) => + return ((nstate == _nstate) + && (nset == _nset)); + case _ => return false + } + case _ => return false + } + } + + override def toString(): String = this match { + case Npair(nstate, nset) => + //Integer dstate = (Integer) indexMap.get(nset); + "<n" + nstate.toString() + " in " + nset /*+" = d"+dstate*/ + ">"; + case _ => null + } + + def toString(indexMap: HashMap): String = { + //assert indexMap != null; + this match { + case Npair(nstate, nset) => + //assert nstate != null; + val dstate = indexMap.get( nset ).asInstanceOf[Integer]; + return "<n" + nstate.toString() + " in " + nset + " = d" + dstate + ">"; + case _ => + return null; + } + } + + +} + +class NpairComparator extends StateSetComparator { + override def compare(o1: Any, o2: Any): Int = { + o1 match { + case Npair(nstate, nset) => o2 match { + case Npair(_nstate, _nset) => + val res = nstate.compareTo(_nstate); + if (res != 0) + return res; + else + return super.compare(nset, _nset); + } + } + } +} diff --git a/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala b/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala new file mode 100644 index 0000000000..7d4292e3ff --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala @@ -0,0 +1,992 @@ +/* NSC -- new scala compiler + * Copyright 2005 LAMP/EPFL + * @author buraq + */ +// $Id$ + +package scala.tools.nsc.matching ; + +import scala.tools.nsc.util.Position; + +trait PatternMatchers: (TransMatcher with PatternNodes) extends AnyRef with PatternNodeCreator { + + + import global._; + import typer.typed ; + import symtab.Flags; + + class PatternMatcher { + + + + protected var optimize = true; + protected var delegateSequenceMatching = false; + protected var doBinding = true; + + /** the owner of the pattern matching expression + */ + var owner:Symbol = _ ; + + /** the selector expression + */ + protected var selector: Tree = _; + + /** the root of the pattern node structure + */ + protected var root: PatternNode = _; + + /** the symbol of the result variable + */ +// protected var resultVar: Symbol = _; + + def defs = definitions; + /** init method, also needed in subclass AlgebraicMatcher + */ + def initialize(selector: Tree, owner: Symbol, doBinding: Boolean): Unit = { + + //Console.println("pm.initialize selector.tpe = "+selector.tpe); + + /* + this.mk = new PatternNodeCreator { + val global = PatternMatcher.this.global; + val unit = PatternMatcher.this.unit; + val owner = PatternMatcher.this.owner; + } + */ + /* + this.cf = new CodeFactory { + val global = PatternMatcher.this.global; + val unit = PatternMatcher.this.unit; + val owner = PatternMatcher.this.owner; + } + */ + this.root = pConstrPat(selector.pos, selector.tpe.widen); + //Console.println("selector.tpe "+selector.tpe); + //Console.println("selector.tpe.widen "+selector.tpe.widen); + //Console.println("root.symbol "+root.symbol); + //Console.println("root.symbol.tpe "+root.symbol.tpe); + this.root.and = pHeader(selector.pos, + selector.tpe.widen, + Ident(root.symbol).setType(root.tpe)); + //Console.println("resultType = "+resultType); + this.owner = owner; + this.selector = selector; + + this.optimize = this.optimize && (settings.target.value == "jvm"); + this.doBinding = doBinding; + } + + /** pretty printer + */ + def print(): Unit = { Console.println ( + root.and.print("", new StringBuffer()).toString() + )} + + /** enters a sequence of cases into the pattern matcher + */ + def construct(cases: List[Tree]): Unit = { + cases foreach enter; + } + + /** enter a single case into the pattern matcher + */ + protected def enter(caseDef: Tree): Unit = { + caseDef match { + case CaseDef(pat, guard, body) => + val env = new CaseEnv; + // PatternNode matched = match(pat, root); + val target = enter1(pat, -1, root, root.symbol, env); + // if (target.and != null) + // unit.error(pat.pos, "duplicate case"); + if (null == target.and) + target.and = pBody(caseDef.pos, env.getBoundVars(), guard, body); + else if (target.and.isInstanceOf[Body]) + updateBody(target.and.asInstanceOf[Body], env.getBoundVars(), guard, body); + else + cunit.error(pat.pos, "duplicate case"); + } + } + + protected def updateBody(tree: Body, bound: Array[ValDef], guard: Tree , body: Tree): Unit = { + if (tree.guard(tree.guard.length - 1) == EmptyTree) { + //unit.error(body.pos, "unreachable code"); + } else { + val bd = new Array[Array[ValDef]](tree.bound.length + 1); + val ng = new Array[Tree](tree.guard.length + 1); + val nb = new Array[Tree](tree.body.length + 1); + System.arraycopy(tree.bound, 0, bd, 0, tree.bound.length); + System.arraycopy(tree.guard, 0, ng, 0, tree.guard.length); + System.arraycopy(tree.body, 0, nb, 0, tree.body.length); + bd(bd.length - 1) = bound; + ng(ng.length - 1) = guard; + nb(nb.length - 1) = body; + tree.bound = bd ; + tree.guard = ng ; + tree.body = nb ; + } + } + + protected def patternArgs(tree: Tree):List[Tree] = { + tree match { + case Bind(_, pat) => + patternArgs(pat); + case Apply(_, args) => + if ( isSeqApply(tree.asInstanceOf[Apply]) && !delegateSequenceMatching) + args(0) match { + case ArrayValue(_, ts) => // test array values + ts; + //case Sequence(ts) => + // ts; + case _ => + args; + } + else args + case Sequence(ts) if (!delegateSequenceMatching) => + ts; + case ArrayValue(_, ts) => // test array values + ts; + case _ => + List(); + } + } + + /** returns true if apply is a "sequence apply". analyzer inserts Sequence nodes if something is a + * + * - last update: discussion with Martin 2005-02-18 + * + * - if true, tree.fn must be ignored. The analyzer ensures that the selector will be a subtype + * of fn; it thus assigns the expected type from the context (which is surely a subtype, + * but may have different flags etc. + * + * - so should be + * (( tree.args.length == 1 ) && tree.args(0).isInstanceOf[Sequence]) + * but fails + */ + protected def isSeqApply( tree: Apply ): Boolean = { + // Console.print("isSeqApply? "+tree.toString()); + // val res = + tree match { + case Apply(_, List(ArrayValue(_,_))) => (tree.tpe.symbol.flags & Flags.CASE) == 0 + case _ => false; + } + //Console.println(res); + //res; + } + + protected def patternNode(tree:Tree , header:Header , env: CaseEnv ): PatternNode = { + //if(tree!=null) Console.println("patternNode("+tree+","+header+")"); + //else scala.Predef.error("got null tree in patternNode"); + //Console.println("tree.tpe "+tree.tpe); + //Console.println("tree.getClass() "+tree.getClass()); + tree match { + case Bind(name, Typed(Ident( nme.WILDCARD ), tpe)) => // x@_:Type + if (isSubType(header.getTpe(),tpe.tpe)) { + //Console.println("U"); + val node = pDefaultPat(tree.pos, tpe.tpe); + env.newBoundVar( tree.symbol, tree.tpe, header.selector ); + node; + } else { + //Console.println("X"); + val node = pConstrPat(tree.pos, tpe.tpe); + env.newBoundVar( tree.symbol, + tpe.tpe /*scalac: tree.tpe */, + typed(Ident( node.casted ))); + node; + } + + case Bind(name, Ident(nme.WILDCARD)) => // x @ _ + val node = pDefaultPat(tree.pos, header.getTpe()); + if ((env != null) && (tree.symbol != defs.PatternWildcard)) + env.newBoundVar( tree.symbol, tree.tpe, header.selector); + node; + + case Bind(name, pat) => + val node = patternNode(pat, header, env); + if ((env != null) && (tree.symbol != defs.PatternWildcard)) { + val casted = node.symbol; + val theValue = if (casted == NoSymbol) header.selector else Ident( casted).setType(casted.tpe); + env.newBoundVar(tree.symbol, tree.tpe, theValue); + } + node; + + case t @ Apply(fn, args) => // pattern with args + //Console.println("Apply!"); + //Console.println("isSeqApply "+isSeqApply(t)); + //Console.println("delegateSequenceMatching "+delegateSequenceMatching); + if (isSeqApply(t)) { + if (!delegateSequenceMatching) { + args(0) match { + // case Sequence(ts)=> + case ArrayValue(_, ts)=> + //Console.println("doing pSeqpat "); + val res = pSequencePat(tree.pos, tree.tpe, ts.length); + //Console.println("pSeqpat.casted = "+res.casted); + //Console.println("pSeqpat.casted.pos = "+res.casted.pos); + res + } + } else { + //Console.println("delegating ... "); + val res = pConstrPat(tree.pos, tree.tpe); + res.and = pHeader(tree.pos, header.getTpe(), header.selector); + //res.and.and = pSeqContainerPat(tree.pos, tree.tpe, args(0)); + res.and.and = pSeqContainerPat(tree.pos, tree.tpe, Sequence(args(0).asInstanceOf[ArrayValue].elems)); + res; + } + } else if ((fn.symbol != null) && + fn.symbol.isStable && + !(fn.symbol.isModule && + ((fn.symbol.flags & Flags.CASE) != 0))) { + pVariablePat(tree.pos, tree); + } + else { + /* + Console.println("apply but not seqApply"); + Console.println("tree.tpe="+tree.tpe); + Console.println("tree.symbol="+tree.symbol); + */ + pConstrPat(tree.pos, tree.tpe); + } + case Typed(Ident( nme.WILDCARD ), tpe) => // x@_:Type + val doTest = isSubType(header.getTpe(),tpe.tpe); + if(doTest) + pDefaultPat(tree.pos, tpe.tpe) + else + pConstrPat(tree.pos, tpe.tpe); + + case t @ Typed(ident, tpe) => // variable pattern + //Console.println("Z"); + val doTest = isSubType(header.getTpe(),tpe.tpe); + val node = { + if(doTest) + pDefaultPat(tree.pos, tpe.tpe) + else + pConstrPat(tree.pos, tpe.tpe); + } + //if(t.expr.symbol == NoSymbol) { + // Console.println(t.toString()); + // scala.Predef.error("go typed pattern with no symbol in "+cunit.toString()); + // } + if ((null != env) /* && (ident.symbol != defs.PatternWildcard) */) + node match { + case ConstrPat(casted) => + env.newBoundVar(t.expr.symbol, + tpe.tpe, + Ident( casted ).setType(casted.tpe)); + case _ => + env.newBoundVar(t.expr.symbol, + tpe.tpe, + {if(doTest) + header.selector + else + typed(Ident(node + .asInstanceOf[ConstrPat] + .casted))}); + } + node; + + case Ident(nme.WILDCARD) => + pDefaultPat(tree.pos, header.getTpe()); + + case Ident(name) => // pattern without args or variable + + // nsc: wildcard's don't have symbols anymore! + //if (tree.symbol == defs.PatternWildcard) + // pDefaultPat(tree.pos, header.getTpe()); + //else + + if (tree.symbol.isPrimaryConstructor) { + scala.Predef.error("error may not happen: ident is primary constructor"+tree.symbol); // Burak + + } else if (treeInfo.isVariableName(name)) {// Burak + //old scalac + scala.Predef.error("this may not happen"); // Burak + + //nsc: desugarize (in case nsc does not do it) + /* + Console.println("Ident("+name+") in unit"+cunit); + Console.println("tree.symbol = "+tree.symbol); + // = treat the same as Bind(name, _) + val node = pDefaultPat(tree.pos, header.getTpe()); + if ((env != null) && (tree.symbol != defs.PatternWildcard)) + env.newBoundVar( tree.symbol, tree.tpe, header.selector); + node; + */ + } else + pVariablePat(tree.pos, tree); // a named constant Foo + + case Select(_, name) => // variable + if (tree.symbol.isPrimaryConstructor) + pConstrPat(tree.pos, tree.tpe); + else + pVariablePat(tree.pos, tree); + + case Literal(Constant(value)) => + pConstantPat(tree.pos, tree.tpe, value); + + //case Sequence(ts) => + case ArrayValue(_, ts) => + if ( !delegateSequenceMatching ) { + pSequencePat(tree.pos, tree.tpe, ts.length); + } else { + pSeqContainerPat(tree.pos, tree.tpe, tree); + } + case Alternative(ts) => + if(ts.length < 2) + scala.Predef.error("ill-formed Alternative"); + val subroot = pConstrPat(header.pos, header.getTpe()); + subroot.and = pHeader(header.pos, header.getTpe(), header.selector.duplicate); + val subenv = new CaseEnv; + var i = 0; while(i < ts.length) { + val target = enter1(ts(i), -1, subroot, subroot.symbol, subenv); + target.and = pBody(tree.pos); + i = i + 1 + } + pAltPat(tree.pos, subroot.and.asInstanceOf[Header]); + + case _ => + if(tree == null) + scala.Predef.error("unit = " + cunit + "; tree = null"); + else + scala.Predef.error("unit = " + cunit + "; tree = "+tree); + } + } + + protected def enter(pat: Tree, index: Int, target: PatternNode, casted: Symbol, env: CaseEnv ): PatternNode = { + target match { + case ConstrPat(newCasted) => + enter1(pat, index, target, newCasted, env); + case SequencePat(newCasted, len) => + enter1(pat, index, target, newCasted, env); + case _ => + enter1(pat, index, target, casted, env); + } + } + + private def newHeader(pos: Int, casted: Symbol, index: Int): Header = { + //Console.println("newHeader(pos,"+casted+","+index+")"); + //Console.println(" casted.tpe"+casted.tpe); + //Console.println(" casted.pos "+casted.pos+" equals firstpos?"+(casted.pos == Position.FIRSTPOS)); + val ident = typed(Ident(casted)); + if (casted.pos == Position.FIRSTPOS) { + //Console.println("FIRSTPOS"); + + //Console.println("DEBUG"); + //Console.println(); + + val t = typed( + Apply(Select( ident, ident.tpe.member(nme.apply)/* scalac: defs.functionApply( 1 )*/), + List( Literal( Constant(index) ) ))); + val seqType = t.tpe; + pHeader( pos, seqType, t ); + } else { + //Console.println("NOT FIRSTPOS"); + // Console.println("newHeader :: casted="+casted); + // Console.println("newHeader :: casted.tpe="+casted.tpe); + //Console.println("newHeader :: "); + val caseAccs = casted.tpe.symbol.caseFieldAccessors; + if (caseAccs.length <= index) System.out.println("selecting " + index + " in case fields of " + casted.tpe.symbol + "=" + casted.tpe.symbol.caseFieldAccessors);//debug + val ts = caseAccs(index); + //Console.println("newHeader :: ts="+ts); + //val accType = casted.tpe.memberType(ts); // old scalac + //val accTree = global.typer.typed(Select(ident, ts)); // ! + + val accTree = typed(Apply(Select(ident, ts), List())); // nsc ! + val accType = accTree.tpe; + //Console.println("newHeader :: accType="+accType); + //Console.println("newHeader :: accType.resultType ="+accType.resultType); + //Console.println("accTree.tpe =="+accTree.tpe); + + accType match { + // scala case accessor + case MethodType(_, _) => + //Console.println("Hello?!"); + pHeader(pos, accType.resultType, Apply(accTree, List())); + // jaco case accessor + case _ => + //Console.println("Hola?!"); + pHeader(pos, accType, accTree); + } + } + } + + /** main enter function + * + * invariant: ( curHeader == (Header)target.and ) holds + */ + protected def enter1(pat: Tree, index: Int, target: PatternNode, casted: Symbol, env: CaseEnv): PatternNode = { + //System.err.println("enter(" + pat + ", " + index + ", " + target + ", " + casted + ")"); + val patArgs = patternArgs(pat); // get pattern arguments + var curHeader = target.and.asInstanceOf[Header]; // advance one step in intermediate representation + if (curHeader == null) { // check if we have to add a new header + //assert index >= 0 : casted; + if (index < 0) { scala.Predef.error("error entering:" + casted); return null } + target.and = {curHeader = newHeader(pat.pos, casted, index); curHeader}; + curHeader.or = patternNode(pat, curHeader, env); + enter(patArgs, curHeader.or, casted, env); + } + else { + // find most recent header + while (curHeader.next != null) + curHeader = curHeader.next; + // create node + var patNode = patternNode(pat, curHeader, env); + var next: PatternNode = curHeader; + // add branch to curHeader, but reuse tests if possible + while (true) { + if (next.isSameAs(patNode)) { // test for patNode already present --> reuse + // substitute... !!! + patNode match { + case ConstrPat(ocasted) => + env.substitute(ocasted, typed(Ident(next.asInstanceOf[ConstrPat].casted))); + case _ => + } + return enter(patArgs, next, casted, env); + } else if (next.isDefaultPat() || // default case reached, or + ((next.or == null) && // no more alternatives and + (patNode.isDefaultPat() || next.subsumes(patNode)))) { + // new node is default or subsumed + var header = pHeader(patNode.pos, + curHeader.getTpe(), + curHeader.selector); + {curHeader.next = header; header}; + header.or = patNode; + return enter(patArgs, + patNode, + casted, + env); + } + else if (next.or == null) { + return enter(patArgs, {next.or = patNode; patNode}, casted, env); // add new branch + } else + next = next.or; + } + error("must not happen"); + null + } + } + + /** calls enter for an array of patterns, see enter + */ + protected def enter(pats:List[Tree], target1: PatternNode , casted1: Symbol , env: CaseEnv): PatternNode = { + var target = target1; + var casted = casted1; + target match { + case ConstrPat(newCasted) => + casted = newCasted; + case SequencePat(newCasted, len) => + casted = newCasted; + case _ => + } + var i = 0; while(i < pats.length) { + target = enter1(pats(i), i, target, casted, env); + i = i + 1 + } + target; + } + + protected def nCaseComponents(tree: Tree): int = { + tree match { + case Apply(fn, _) => + val tpe = tree.tpe.symbol.primaryConstructor.tpe; + //Console.println("~~~ " + tree.type() + ", " + tree.type().symbol.primaryConstructor()); + tpe match { + // I'm not sure if this is a good idea, but obviously, currently all case classes + // without constructor arguments have type NoType + case NoType => + error("this cannot happen"); + 0 + case MethodType(args, _) => + args.length; + case PolyType(tvars, MethodType(args, _)) => + args.length; + case PolyType(tvars, _) => + 0; + case _ => + error("not yet implemented;" + + "pattern matching for " + tree + ": " + tpe); + } + } + return 0; + } + + + //////////// generator methods + + def toTree(): Tree = { + if (optimize && isSimpleIntSwitch()) + intSwitchToTree(); + + else /* if (false && optimize && isSimpleSwitch()) + switchToTree(); + else */ { + //print(); + generalSwitchToTree(); + } + } + + case class Break(res:Boolean) extends java.lang.Throwable; + case class Break2() extends java.lang.Throwable; + + // TODO disentangle this + protected def isSimpleSwitch(): Boolean = { + print(); + var patNode = root.and; + while (patNode != null) { + var node = patNode; + while (({node = node.or; node}) != null) { + node match { + case VariablePat(tree) => + Console.println(((tree.symbol.flags & Flags.CASE) != 0)); + case ConstrPat(_) => + Console.println(node.getTpe().toString() + " / " + ((node.getTpe().symbol.flags & Flags.CASE) != 0)); + var inner = node.and; + def funct(inner: PatternNode): Boolean = { + //outer: while (true) { + inner match { + case _h:Header => + if (_h.next != null) + throw Break(false); + funct(inner.or) + + case DefaultPat() => + funct(inner.and); + + case b:Body => + if ((b.guard.length > 1) || + (b.guard(0) != EmptyTree)) + throw Break(false); + + throw Break2() // break outer + case _ => + Console.println(inner); + throw Break(false); + } + } + var res = false; + var set = false; + try { + funct(inner) + } catch { + case ex: Break => + res = ex.res; + set = true; + case ex: Break2 => + } + if(set) return res; + case _ => + return false; + } + } + patNode = patNode.nextH(); + } + return true; + } + + protected def isSimpleIntSwitch(): Boolean = { + if (isSameType(selector.tpe.widen, defs.IntClass.tpe)) { + var patNode = root.and; + while (patNode != null) { + var node = patNode; + while (({node = node.or; node}) != null) { + node match { + case ConstantPat(_) => ; + case _ => + return false; + } + node.and match { + case _b:Body => + if ((_b.guard.length > 1) || + (_b.guard(0) != EmptyTree) || + (_b.bound(0).length > 0)) + return false; + case _ => + return false; + } + } + patNode = patNode.nextH(); + } + return true; + } else + return false; + } + + class TagBodyPair(tag1: Int, body1: Tree, next1:TagBodyPair ) { + + var tag: int = tag1; + var body: Tree = body1; + var next: TagBodyPair = next1; + + def length(): Int = { + if (null == next) 1 else (next.length() + 1); + } + } + + protected def numCases(patNode1: PatternNode): Int = { + var patNode = patNode1; + var n = 0; + while (({patNode = patNode.or; patNode}) != null) + patNode match { + case DefaultPat() => ; + case _ => + n = n + 1; + } + n; + } + + protected def defaultBody(patNode1: PatternNode, otherwise: Tree ): Tree = { + var patNode = patNode1; + while (patNode != null) { + var node = patNode; + while (({node = node.or; node}) != null) + node match { + case DefaultPat() => + return node.and.bodyToTree(); + case _ => + } + patNode = patNode.nextH(); + } + otherwise; + } + + /** This method translates pattern matching expressions that match + * on integers on the top level. + */ + def intSwitchToTree(): Tree = { + def insert1(tag: Int, body: Tree, current: TagBodyPair): TagBodyPair = { + if (current == null) + return new TagBodyPair(tag, body, null); + else if (tag > current.tag) + return new TagBodyPair(current.tag, current.body, insert1(tag, body, current.next)); + else + return new TagBodyPair(tag, body, current); + } + + //print(); + val ncases = numCases(root.and); + val matchError = ThrowMatchError(selector.pos, resultType); + // without a case, we return a match error if there is no default case + if (ncases == 0) + return defaultBody(root.and, matchError); + // for one case we use a normal if-then-else instruction + else if (ncases == 1) { + root.and.or match { + case ConstantPat(value) => + return If(Equals(selector, Literal(value)), + (root.and.or.and).bodyToTree(), + defaultBody(root.and, matchError)); + case _ => + return generalSwitchToTree(); + } + } + // + // if we have more than 2 cases than use a switch statement + val _h:Header = root.and.asInstanceOf[Header]; + + val next = _h.next; + var mappings: TagBodyPair = null; + var defaultBody1: Tree = matchError; + var patNode = root.and; + while (patNode != null) { + var node = patNode.or; + while (node != null) { + node match { + case DefaultPat() => + if (defaultBody1 != null) + scala.Predef.error("not your day today"); + defaultBody1 = node.and.bodyToTree(); + node = node.or; + + case ConstantPat( value: Int )=> + mappings = insert1( + value, + node.and.bodyToTree(), + mappings); + node = node.or; + } + } + patNode = patNode.nextH(); + } + + var n = mappings.length(); + var nCases: List[CaseDef] = Nil; + while (mappings != null) { + nCases = CaseDef(Literal(mappings.tag), + mappings.body) :: nCases; + mappings = mappings.next; + } + /* + val tags = new Array[Int](n); + val bodies = new Array[Tree](n); + n = 0; + while (mappings != null) { + tags(n) = mappings.tag; + bodies(n) = mappings.body; + n = n + 1; + mappings = mappings.next; + } + return Switch(selector, tags, bodies, defaultBody1, resultType); + */ + nCases = CaseDef(Ident(nme.WILDCARD), defaultBody1) :: nCases; + return Match(selector, nCases) + } + + + var exit:Symbol = null; + /** simple optimization: if the last pattern is `case _' (no guards), we won't generate the ThrowMatchError + */ + def generalSwitchToTree(): Tree = { + this.exit = currentOwner.newLabel(root.pos, "exit") + .setInfo(new MethodType(List(resultType), resultType)); + //Console.println("resultType:"+resultType.toString()); + val result = exit.newValueParameter(root.pos, "result").setInfo( resultType ); + + //Console.println("generalSwitchToTree: "+root.or); + /* + val ts = List(ValDef(root.symbol, selector)); + val res = If(toTree(root.and), + LabelDef(exit, List(result), Ident(result)), + ThrowMatchError(selector.pos, resultType // , Ident(root.symbol) + )); + return Block(ts, res); + */ + return Block( + List( + ValDef(root.symbol, selector), + toTree(root.and), + ThrowMatchError(selector.pos, resultType)), + LabelDef(exit, List(result), Ident(result))) + } + + /*protected*/ def toTree(node1: PatternNode): Tree = { + def optimize1(selType:Type, alternatives1: PatternNode ): Boolean = { + var alts = alternatives1; + if (!optimize || !isSubType(selType, defs.ScalaObjectClass.tpe)) + return false; + var cases = 0; + while (alts != null) { + alts match { + case ConstrPat(_) => + if (alts.getTpe().symbol.hasFlag(Flags.CASE)) + cases = cases +1; + else + return false; + + case DefaultPat() => + ; + case _ => + return false; + } + alts = alts.or; + } + return cases > 2; + } // def optimize + + var node = node1; + + var res: Tree = typed(Literal(Constant(false))); //.setInfo(defs.BooleanClass); + //Console.println("pm.toTree res.tpe "+res.tpe); + while (node != null) + node match { + case _h:Header => + val selector = _h.selector; + val next = _h.next; + //res = And(mkNegate(res), toTree(node.or, selector)); + //Console.println("HEADER TYPE = " + selector.type); + if (optimize1(node.getTpe(), node.or)) + res = Or(res, toOptTree(node.or, selector)); + else + res = Or(res, toTree(node.or, selector)); + node = next; + + case _b:Body => + var bound = _b.bound; + val guard = _b.guard; + val body = _b.body; + if ((bound.length == 0) && + (guard.length == 0) && + (body.length == 0)) { + return Literal(Constant(true)); + } else if (!doBinding) + bound = Predef.Array[Array[ValDef]]( Predef.Array[ValDef]() ); + var i = guard.length - 1; while(i >= 0) { + val ts:Seq[Tree] = bound(i).asInstanceOf[Array[Tree]]; + val temp = currentOwner.newValue(body(i).pos, cunit.fresh.newName("r$")) + .setFlag(Flags.SYNTHETIC).setInfo(resultType); + var res0: Tree = + //Block( + // List(Assign(Ident(resultVar), body(i))), + // Literal(Constant(true))); + Block( + List( + ValDef(temp, body(i)), + Apply(Ident(exit), List(Ident(temp)))), + Literal(Constant(true)) + ); // forward jump + if (guard(i) != EmptyTree) + res0 = And(guard(i), res0); + res = Or(Block(ts.toList, res0), res); + i = i - 1 + } + return res; + case _ => + scala.Predef.error("I am tired"); + } + return res; + } + + + class TagNodePair(tag1: int, node1: PatternNode, next1: TagNodePair) { + var tag: int = tag1; + var node: PatternNode = node1; + var next: TagNodePair = next1; + + def length(): Int = { + return if (null == next) 1 else (next.length() + 1); + } + } + + protected def toOptTree(node1: PatternNode, selector: Tree): Tree = { + def insert2(tag: Int, node: PatternNode, current: TagNodePair): TagNodePair = { + if (current == null) + return new TagNodePair(tag, node, null); + else if (tag > current.tag) + return new TagNodePair(current.tag, current.node, insert2(tag, node, current.next)); + else if (tag == current.tag) { + val old = current.node; + ({current.node = node; node}).or = old; + return current; + } else + return new TagNodePair(tag, node, current); + } + + def insertNode(tag:int , node:PatternNode , current:TagNodePair ): TagNodePair = { + val newnode = node.dup(); + newnode.or = null; + return insert2(tag, newnode, current); + } + var node = node1; + //System.err.println("pm.toOptTree called"+node); + var cases: TagNodePair = null; + var defaultCase: PatternNode = null; + while (node != null) + node match { + case ConstrPat(casted) => + cases = insertNode(node.getTpe().symbol.tag, node, cases); + node = node.or; + + case DefaultPat() => + defaultCase = node; + node = node.or; + + case _ => + scala.Predef.error("errare humanum est"); + } + var n = cases.length(); + /* + val tags = new Array[int](n); + val bodies = new Array[Tree](n); + n = 0; + while (null != cases) { + tags(n) = cases.tag; + bodies(n) = toTree(cases.node, selector); + n = n + 1; + cases = cases.next; + } + */ + + + /* + return + Switch( + Apply( + Select(selector.duplicate, defs.ScalaObjectClass_tag), + List()), + tags, + bodies, + { if (defaultCase == null) Literal(false) else toTree(defaultCase.and) }, + defs.boolean_TYPE()); + */ + var nCases: List[CaseDef] = Nil; + while (cases != null) { + nCases = CaseDef(Literal(Constant(cases.tag)), + toTree(cases.node, selector)) :: nCases; + cases = cases.next; + } + + val defBody = if (defaultCase == null) + Literal(Constant(false)) + else + toTree(defaultCase.and); + + nCases = CaseDef(Ident(nme.WILDCARD), defBody) :: nCases; + return Match(Apply(Select(selector.duplicate, defs.ScalaObjectClass_tag), + List()), + nCases); + } + + protected def toTree(node:PatternNode , selector:Tree ): Tree = { + //Console.println("pm.toTree("+node+","+selector+")"); + //Console.println("pm.toTree selector.tpe = "+selector.tpe+")"); + if(selector.tpe == null) + scala.Predef.error("cannot go on"); + if (node == null) + return Literal(Constant(false)); + else + node match { + case DefaultPat() => + return toTree(node.and); + + case ConstrPat(casted) => + return If(gen.mkIsInstanceOf(selector.duplicate, node.getTpe()), + Block( + List(ValDef(casted, + gen.mkAsInstanceOf(selector.duplicate, node.getTpe(), true))), + toTree(node.and)), + toTree(node.or, selector.duplicate)); + case SequencePat(casted, len) => + return ( + Or( + And( + And(gen.mkIsInstanceOf(selector.duplicate, node.getTpe()), + Equals( + typed( + Apply( + Select( + gen.mkAsInstanceOf(selector.duplicate, + node.getTpe(), + true), + node.getTpe().member(nme.length) /*defs.Seq_length*/), + List()) + ), + typed( + Literal(Constant(len)) + ))), + Block( + List( + ValDef(casted, + gen.mkAsInstanceOf(selector.duplicate, node.getTpe(), true))), + toTree(node.and))), + toTree(node.or, selector.duplicate))); + case ConstantPat(value) => + //Console.println("selector = "+selector); + //Console.println("selector.tpe = "+selector.tpe); + return If(Equals(selector.duplicate, + typed(Literal(Constant(value))).setType(node.tpe)), + toTree(node.and), + toTree(node.or, selector.duplicate)); + case VariablePat(tree) => + return If(Equals(selector.duplicate, tree), + toTree(node.and), + toTree(node.or, selector.duplicate)); + case AltPat(header) => + return If(toTree(header), + toTree(node.and), + toTree(node.or, selector.duplicate)); + case _ => + scala.Predef.error("can't plant this tree"); + } + } +} + + +} diff --git a/src/compiler/scala/tools/nsc/matching/PatternNodeCreator.scala b/src/compiler/scala/tools/nsc/matching/PatternNodeCreator.scala new file mode 100644 index 0000000000..79ba780469 --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/PatternNodeCreator.scala @@ -0,0 +1,108 @@ +package scala.tools.nsc.matching; + +import scala.tools.nsc.util.Position; + +/** PatternNode factory. + * we inherit the globals from PatternTool. + */ + +trait PatternNodeCreator: (TransMatcher with PatternNodes) { + + import global._; + + def pSequencePat(pos: Int , tpe:Type , len:int) = { + //assert (tpe != null); + val sym = newVar(Position.FIRSTPOS, tpe); + //Console.println("pncrea::sequencePat sym.pos = "+sym.pos); + val node = new SequencePat(sym, len); + node.pos = pos; + node.tpe = tpe; + //Console.println("pncrea::sequencePat sym.pos = "+sym.pos); + node; + } + + def pSeqContainerPat(pos: int, tpe: Type, seqpat:Tree ) = { + //assert (tpe != null); + val sym = newVar(Position.NOPOS, tpe); + val node = new SeqContainerPat(sym, seqpat); + node.pos = pos; + node.setType(tpe); + node; + } + + def pDefaultPat(pos: int, tpe: Type) = { + //assert (tpe != null); + val node = new DefaultPat(); + node.pos = pos; + node.setType(tpe); + node; + } + + def pConstrPat(pos: int, tpe: Type) = { + //assert (tpe != null); + val node = new ConstrPat(newVar(pos, tpe)); + node.pos = pos; + node.setType(tpe); + node; + } + + def pConstantPat(pos: int, tpe: Type, value: Any /*AConstant*/ ) = { + //assert (tpe != null); + val node = new ConstantPat( value ); + node.pos = pos; + node.setType(tpe); + node; + } + + def pVariablePat(pos: int, tree:Tree) = { + //assert (tree.tpe != null); + val node = new VariablePat( tree ); + node.pos = pos; + node.setType(tree.tpe); + node; + } + + def pAltPat(pos: int, header:Header ) = { + val node = new AltPat(header); + node.pos = pos; + node.setType(header.getTpe()); + node; + } + + // factories + + def pHeader(pos: int, tpe: Type, selector:Tree) = { + //assert (tpe != null); + val node = new Header(selector, null); + node.pos = pos; + node.setType(tpe); + node; + } + + def pBody(pos: int) = { + val node = new Body(new Array[Array[ValDef]](0), new Array[Tree](0), new Array[Tree](0)); + node.pos = pos; + node; + } + + def pBody(pos: int, bound:Array[ValDef] , guard:Tree, body:Tree) = { + val node = new Body(Predef.Array[Array[ValDef]](bound), Predef.Array[Tree](guard), Predef.Array[Tree](body)); + node.pos = pos; + node; + } + + def newVar(pos: int, name: Name, tpe: Type): Symbol= { + /** hack: pos has special meaning*/ + val sym = currentOwner.newVariable(pos, name); + //Console.println("patnodcre::newVar sym = "+sym+ "tpe = "+tpe); + sym.setInfo(tpe); + //System.out.println("PatternNodeCreator::newVar creates symbol "+sym); + //System.out.println("owner: "+sym.owner()); + sym; + } + + def newVar(pos: int, tpe: Type): Symbol = { + newVar(pos, cunit.fresh.newName("temp"), tpe); + } +} + diff --git a/src/compiler/scala/tools/nsc/matching/PatternNodes.scala b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala new file mode 100644 index 0000000000..551d964c39 --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala @@ -0,0 +1,371 @@ +/* ____ ____ ____ ____ ______ *\ +** / __// __ \/ __// __ \/ ____/ SOcos COmpiles Scala ** +** __\_ \/ /_/ / /__/ /_/ /\_ \ (c) 2002, LAMP/EPFL ** +** /_____/\____/\___/\____/____/ ** +** ** +** $Id$ +\* */ + +package scala.tools.nsc.matching ; + +import scala.tools.nsc.util.Position; + +trait PatternNodes: TransMatcher { + + import global._; + + /** Intermediate data structure for algebraic + pattern matcher + */ + class PatternNode { + var pos = Position.FIRSTPOS; + var tpe: Type = _; + var or: PatternNode = _; + var and: PatternNode = _; + + def bodyToTree(): Tree = this match { + case _b:Body => + return _b.body(0); + } + + def getTpe(): Type = { + tpe; + } + def setType(tpe: Type): Unit = { + this.tpe = tpe; + } + + def dup(): PatternNode = { + var res: PatternNode = null; + this match { + case h:Header => + res = new Header(h.selector, h.next); + + case b:Body=> + res = new Body(b.bound, b.guard, b.body); + + case DefaultPat() => + res = DefaultPat(); + + case ConstrPat(casted) => + res = ConstrPat(casted); + + case SequencePat(casted, len) => + res = SequencePat(casted, len); + + case SeqContainerPat(casted, seqpat) => + res = SeqContainerPat(casted, seqpat); + + case ConstantPat(value) => + res = ConstantPat(value); + + case VariablePat(tree) => + res = VariablePat(tree); + + case AltPat(subheader) => + res = AltPat(subheader); + + case _ => + error("") + } + res.pos = pos; + res.tpe = tpe; + res.or = or; + res.and = and; + res; + } + + def symbol: Symbol = { + this match { + case ConstrPat(casted) => + return casted; + case SequencePat(casted, _) => + return casted; + case SeqContainerPat(casted, _) => + return casted; + case _ => + return NoSymbol; //.NONE; + } + } + + def nextH(): PatternNode = { + this match { + case _h:Header => + return _h.next; + case _ => + return null; + } + } + + def isDefaultPat(): boolean = { + this match { + case DefaultPat() => + return true; + case _ => + return false; + } + } + + /** returns true if + * p and q are equal (constructor | sequence) type tests, or + * "q matches" => "p matches" + */ + def isSameAs(q: PatternNode): boolean = { + this match { + case ConstrPat(_) => + q match { + case ConstrPat(_) => + isSameType(q.getTpe(), this.getTpe()); + case _ => + false + } + case SequencePat(_, plen) => + q match { + case SequencePat(_, qlen) => + return (plen == qlen) && isSameType(q.getTpe(), this.getTpe()); + case _ => + false + } + case _ => + subsumes(q); + } + } + + /** returns true if "q matches" => "p matches" + */ + def subsumes(q:PatternNode): Boolean = { + this match { + case DefaultPat() => + q match { + case DefaultPat() => + true; + case _ => + false; + } + case ConstrPat(_) => + q match { + case ConstrPat(_) => + isSubType(q.getTpe(), this.getTpe()); + case _ => + false; + } + case SequencePat(_, plen) => + q match { + case SequencePat(_, qlen) => + (plen == qlen) && isSubType(q.getTpe(), this.getTpe()); + case _ => + false; + } + case ConstantPat(pval) => + q match { + case ConstantPat(qval) => + pval == qval; + case _ => + false; + } + case VariablePat(tree) => + q match { + case VariablePat(other) => + ((tree.symbol != null) && + (tree.symbol != NoSymbol) && + (!tree.symbol.isError) && + (tree.symbol == other.symbol)) + case _ => + false; + } + case _ => + false; + } + } + + override def toString(): String = { + this match { + case _h:Header => + return "Header(" + _h.selector + ")"; + case _b:Body => + return "Body"; + case DefaultPat() => + return "DefaultPat"; + case ConstrPat(casted) => + return "ConstrPat(" + casted + ")"; + case SequencePat(casted, len) => + return "SequencePat(" + casted + ", " + len + "...)"; + case SeqContainerPat(casted, seqpat) => + return "SeqContainerPat(" + casted + ", " + seqpat + ")"; + case ConstantPat(value) => + return "ConstantPat(" + value + ")"; + case VariablePat(tree) => + return "VariablePat"; + case _ => + return "<unknown pat>"; + } + } + + def print(indent: String, sb: StringBuffer): StringBuffer = { + + val patNode = this; + + def cont = if (patNode.or != null) patNode.or.print(indent, sb); else sb; + + def newIndent(s: String) = { + val removeBar: Boolean = (null == patNode.or); + val sb = new StringBuffer(); + sb.append(indent); + if (removeBar) + sb.setCharAt(indent.length() - 1, ' '); + var i = 0; while (i < s.length()) { + sb.append(' '); + i = i + 1 + } + sb.toString() + } + + if (patNode == null) + sb.append(indent).append("NULL"); + else + patNode match { + + case _h: Header => + val selector = _h.selector; + val next = _h.next; + sb.append(indent + "HEADER(" + patNode.getTpe() + + ", " + selector + ")").append('\n'); + patNode.or.print(indent + "|", sb); + if (next != null) + next.print(indent, sb); + else + sb + case ConstrPat(casted) => + val s = ("-- " + patNode.getTpe().symbol.name + + "(" + patNode.getTpe() + ", " + casted + ") -> "); + val nindent = newIndent(s); + sb.append(nindent + s).append('\n'); + patNode.and.print(nindent, sb); + cont; + + case SequencePat( casted, plen ) => + val s = ("-- " + patNode.getTpe().symbol.name + "(" + + patNode.getTpe() + + ", " + casted + ", " + plen + ") -> "); + val nindent = newIndent(s); + sb.append(indent + s).append('\n'); + patNode.and.print(nindent, sb); + cont; + + case DefaultPat() => + sb.append(indent + "-- _ -> ").append('\n'); + patNode.and.print(indent.substring(0, indent.length() - 1) + + " ", sb); + cont; + + case ConstantPat(value) => + val s = "-- CONST(" + value + ") -> "; + val nindent = newIndent(s); + sb.append(indent + s).append('\n'); + patNode.and.print( nindent, sb); + cont; + + case VariablePat(tree) => + val s = "-- STABLEID(" + tree + ": " + patNode.getTpe() + ") -> "; + val nindent = newIndent(s); + sb.append(indent + s).append('\n'); + patNode.and.print(nindent, sb); + cont; + + case AltPat(header) => + sb.append(indent + "-- ALTERNATIVES:").append('\n'); + header.print(indent + " * ", sb); + patNode.and.print(indent + " * -> ", sb); + cont; + + case _b:Body => + if ((_b.guard.length == 0) && (_b.body.length == 0)) + sb.append(indent + "true").append('\n') ; + else + sb.append(indent + "BODY(" + _b.body.length + ")").append('\n'); + + } + } // def print + + } + + class Header(sel1: Tree, next1: Header ) extends PatternNode { + var selector: Tree = sel1; + var next: Header = next1; + } + + class Body(bound1: Array[Array[ValDef]] , guard1:Array[Tree] , body1:Array[Tree] ) extends PatternNode { + var bound = bound1; + var guard = guard1; + var body = body1; + } + + case class DefaultPat()extends PatternNode; + case class ConstrPat(casted:Symbol ) extends PatternNode; + case class ConstantPat(value: Any /*AConstant*/ ) extends PatternNode; + case class VariablePat(tree: Tree ) extends PatternNode; + case class AltPat(subheader: Header ) extends PatternNode; + case class SequencePat( casted: Symbol, len:int) extends PatternNode; // only used in PatternMatcher + case class SeqContainerPat(casted: Symbol , seqpat: Tree ) extends PatternNode; // in AlgebraicMatcher + + /** the environment for a body of a case + * @param owner the owner of the variables created here + */ + class CaseEnv { +// (val owner:Symbol, unit:CompilationUnit) + private var boundVars:scala.Array[ValDef] = new Array[ValDef](4); + private var numVars = 0; + + /** substitutes a symbol on the right hand side of a ValDef + */ + def substitute(oldSym: Symbol, newInit: Tree): Unit = { + var i = 0; while( i < numVars) { + if( boundVars(i).rhs.symbol == oldSym ) { + boundVars(i) = ValDef(boundVars(i).symbol, newInit); + return; + } + i = i + 1; + } + } + + def newBoundVar(sym:Symbol, tpe: Type, init:Tree ): Unit = { + //if(sym == Symbol.NoSymbol ) { +// scala.Predef.Error("can't add variable with NoSymbol"); +// } + // sym.setOwner( owner ); // FIXME should be corrected earlier + // @maybe is corrected now? bq + if (numVars == boundVars.length) { + val newVars = new Array[ValDef](numVars * 2); + System.arraycopy(boundVars, 0, newVars, 0, numVars); + this.boundVars = newVars; + } + sym.setInfo(tpe); + this.boundVars(numVars) = ValDef(sym, init.duplicate); + numVars = numVars + 1; + } + + def getBoundVars(): Array[ValDef] = { + val newVars = new Array[ValDef](numVars); + System.arraycopy(boundVars, 0, newVars, 0, numVars); + return newVars; + } + + override def equals(obj: Any): Boolean = { + if (!(obj.isInstanceOf[CaseEnv])) + return false; + val env = obj.asInstanceOf[CaseEnv]; + if (env.numVars != numVars) + return false; + var i = 0; while(i < numVars) { + if ((boundVars(i).name != env.boundVars(i).name) || + !isSameType(boundVars(i).tpe, env.boundVars(i).tpe) || + (boundVars(i).rhs != env.boundVars(i).rhs)) + return false; + i = i + 1; + } + return true; + } + + } // class CaseEnv + + +} diff --git a/src/compiler/scala/tools/nsc/matching/RightTracers.scala b/src/compiler/scala/tools/nsc/matching/RightTracers.scala new file mode 100644 index 0000000000..f0daf20fed --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/RightTracers.scala @@ -0,0 +1,537 @@ +/* NSC -- new scala compiler + * Copyright 2005 LAMP/EPFL + * @author buraq + */ +// $Id$ + +package scala.tools.nsc.matching; + +import java.util._ ; + +import scala.tools.nsc.util.Position; +import scala.tools.nsc.symtab.Flags; + +trait RightTracers: TransMatcher { + + import global._ ; + import java.util._ ; + +//import Scope.SymbolIterator; + +//import scalac.util.Name ; +//import scalac.util.Names ; + +//import scala.tools.util.Position; + + /** translate right tracer to code + * @param dfa determinized left tracer + * @param left nondeterm. left tracer (only needed for variables!) + * @param pat ? + * @param elementType ... + */ +abstract class RightTracerInScala extends Autom2Scala { + + val seqVars: Set; + val pat:Tree; + val elementType: Type; + + + def SeqTrace_headElem( arg: Tree ) = { // REMOVE SeqTrace + val t = Apply(Select(arg, definitions.List_head), Nil); + Apply(Select(t, definitions.tupleField(2,2)),Nil) + } + + def SeqTrace_headState( arg: Tree ) = { // REMOVE SeqTrace + val t = Apply(Select(arg, definitions.List_head), Nil); + Apply(Select(t, definitions.tupleField(2,1)), Nil) + } + + def SeqTrace_tail( arg: Tree ): Tree = // REMOVE SeqTrace + Apply(Select(arg, definitions.List_tail), Nil); + + final def collectVars(pat: Tree): HashSet = { + var vars = new HashSet(); + + def handleVariableSymbol(sym: Symbol): Unit = { + vars.add( sym ); + } + def isVariableName(name: Name): Boolean = + ( name != nme.WILDCARD ) && ( treeInfo.isVariableName( name ) ) ; + + def isVariableSymbol(sym: Symbol): Boolean = { + ( sym != null )&&( !sym.isPrimaryConstructor ); + } + + def traverse(tree: Tree): Unit = { + tree match { + case x @ Ident(name)=> + if(x.symbol != definitions.PatternWildcard) + scala.Predef.error("shouldn't happen?!"); + + case Star(t) => + traverse(t); + case Bind(name, subtree) => + var sym: Symbol = null; + if( isVariableName( name ) + && isVariableSymbol( {sym = tree.symbol; tree.symbol} )) + handleVariableSymbol( sym ); + + traverse( subtree ); + + // congruence cases + case Apply(fun, args) => args foreach {traverse}; + case Sequence(trees) => trees foreach {traverse}; + case Typed(expr, tpe) => traverse(expr); // needed?? + case _ : Alternative | _ : Select | _ : Literal => ; // no variables + case _ => Predef.error("unknown node:"+tree+" = "+tree.getClass()); + } + } + traverse( pat ); + return vars; + } + + //final def defs = cf.defs; + + val allVars: Set = collectVars( pat ); + + var varsToExport: Set = new HashSet(); // @todo HANDLE seqVars THESE GLOBALLY INSTEAD OF LOCALLY + + varsToExport.addAll( allVars ); + varsToExport.removeAll( seqVars ); + + var targetSym:Symbol = _; + + var helpMap = new HashMap(); + var helpMap2 = new HashMap(); + var helpVarDefs:scala.List[Tree] = Nil; + + val it = seqVars.iterator(); + while(it.hasNext()) { + makeHelpVar( it.next().asInstanceOf[Symbol] ); + } + + val jt = allVars.iterator(); + while(jt.hasNext()) { + val varSym = jt.next().asInstanceOf[Symbol]; + if(( varSym.name.toString().indexOf("$") == -1 ) + && ( !seqVars.contains( varSym ))) { + makeHelpVar( varSym, true ); + } + } + + //System.out.println("allVars: "+allVars); + //System.out.println("seqVars: "+seqVars); + //System.out.println("helpVarDefs now: "+helpVarDefs); + + initializeSyms(); + + def makeHelpVar(realVar: Symbol): Unit = { + makeHelpVar( realVar, false ); + } + + /** makes a helpvar and puts mapping into helpMap, ValDef into helpVarDefs + */ + + def makeHelpVar(realVar: Symbol, keepType: Boolean): Unit = { + val helpVar = owner.newVariable( pos, + fresh.newName( realVar.name + .toString()+"RTIS" )); + var rhs: Tree = null; + + //System.out.println("RTiS making helpvar : "+realVar+" -> "+helpVar); + + if( keepType ) { + helpVar.setInfo( realVar.tpe ); + rhs = EmptyTree; + } else { + helpVar.setInfo( definitions.ListClass.info /* LIST_TYPE(elementType)*/ ); + rhs = gen.mkNil; + } + + helpMap.put( realVar, helpVar ); + helpVar.setFlag(Flags.MUTABLE); + val varDef = ValDef( helpVar, rhs ); + //((ValDef) varDef).kind = Kinds.VAR; + helpVarDefs= varDef :: helpVarDefs; + + } + + def prependToHelpVar(realVar: Symbol, elem:Tree): Tree = { + val hv = refHelpVar( realVar ); + Assign( hv, gen.mkNewCons( /*elementType, */elem, hv )); + /* + return cf.Block(pos, + new Tree [] { + cf.debugPrintRuntime( "ASSIGN" ), + gen.Assign( hv, cf.newSeqCons( elem, hv )) + }, defs.UNIT_TYPE()); + */ + } + + protected def initializeSyms(): Unit = { + + this.funSym = owner.newLabel( pos, fresh.newName( "right" )); + + this.iterSym = owner.newVariable( pos, fresh.newName("iter")) + .setInfo( SeqTraceType( elementType )); + + this.stateSym = owner.newVariable ( pos, fresh.newName("q")) + .setInfo( definitions.IntClass.info ) ; + + this.curSym = owner.newVariable( pos, fresh.newName("cur")) + .setInfo( elementType ) ; + + this.targetSym = owner.newVariable( pos, fresh.newName("p")) + .setInfo( definitions.IntClass.info ) ; + + funSym.setInfo( + MethodType( scala.List ( // dummy symbol MethodType + SeqTraceType(elementType), + //funSym.newValueParameter( pos, fresh.newName("iter") /*, SeqTraceType elementType */), + definitions.IntClass.info), + //funSym.newValueParameter( pos, fresh.newName( "q" ) /*, definitions.IntClass.info */), + definitions.UnitClass.info)) // result + + } + + // load current elem and trace + override def loadCurrentElem(body: Tree): Tree = { + If( isEmpty( _iter() ), + run_finished( 0 ), // we are done + Block( scala.List ( + ValDef( this.targetSym, + SeqTrace_headState( Ident( iterSym))), + ValDef( this.curSym, + SeqTrace_headElem( Ident( iterSym )))), + body ) + ); + } + + /** see code_state0_NEW + */ + def code_state0(elseBody: Tree) = { // careful, map Int to Int + + If( Equals( _state(), Literal(0)), + code_state0_NEW(), + elseBody ); + + } + + /** this one is special, we check the first element of the trace + * and choose the next state depending only on the state part + */ + def code_state0_NEW(): Tree = { // careful, map Int to Int + + val hmap = dfa.deltaq( 0 ); // all the initial states + + var i = 0; + val n = hmap.keySet().size(); // all transitions defined + + val tmapTag = new TreeMap(); + val tmapBody = new TreeMap(); + var it = hmap.keySet().iterator(); + while(it.hasNext()) { + val targetL = it.next().asInstanceOf[Integer]; + val targetR = hmap.get( targetL ).asInstanceOf[Integer]; + + val I = new Integer( i ); + tmapTag.put( targetL, I ); + tmapBody.put( I, callFun( scala.List ( + SeqTrace_tail( _iter() ), + Literal( targetR.intValue() ) ))); + i = i + 1; + } + //i = 0; + + var ncases: scala.List[CaseDef] = Nil; + //val tags = new Array[Int]( n ); + //val targets = new Array[Tree]( n ); + var jt = tmapTag.keySet().iterator(); + while(jt.hasNext()) { + val tagI = jt.next().asInstanceOf[Integer]; + //tags( i ) = tagI.intValue(); + val I = tmapTag.get( tagI ).asInstanceOf[Integer]; + //targets( i ) = tmapBody.get( I ).asInstanceOf[Tree];; + ncases = CaseDef( Literal(tagI.intValue()), + tmapBody.get(I).asInstanceOf[Tree] ) :: ncases; + //i = i + 1 + } + //gen.Switch( gen.Ident( pos, targetSym ), + // tags, + // targets, + // code_error()/*cannot happen*/ ); + + Match(Ident(targetSym), ncases); + } + + override def currentMatches(label: Label): Tree = label match { + case LPair( target, theLab ) => + Equals( Literal(target.intValue() ), current() ); + case _ => + scala.Predef.error("expected Pair label"); + } + + + override def code_state_NEW(i: Int): Tree = { // precondition i != 0 + var stateBody = code_delta( i, DefaultLabel() ); + if( stateBody == null ) { + stateBody = code_error(); + } + val trans = dfa.deltaq( i ); + val tmapTag = new TreeMap(); + val tmapBody = new TreeMap(); + var j = 0; + var labs = dfa.labels().iterator(); + while(labs.hasNext()) { + val label = labs.next(); + val next = trans.get( label ).asInstanceOf[Integer]; + val action = code_delta( i, label.asInstanceOf[Label] ); + + if( action != null ) { + val J = new Integer( j ); + tmapTag.put( label.asInstanceOf[LPair].state, J ); + tmapBody.put( J, action ); + + stateBody = If( currentMatches( label.asInstanceOf[Label] ), + action, + stateBody); + } + j = j + 1; + } + val n = tmapTag.keySet().size(); + //j = 0; + //val tags = new Array[int]( n ); + //val targets = new Array[Tree]( n ); + var ncases: scala.List[CaseDef] = Nil; + val it = tmapTag.keySet().iterator(); + while(it.hasNext()) { + val tagI = it.next().asInstanceOf[Integer]; + //tags( j ) = tagI.intValue(); + val J = tmapTag.get( tagI ).asInstanceOf[Integer]; + //targets( j ) = tmapBody.get( J ).asInstanceOf[Tree]; + ncases = CaseDef(Literal(tagI.intValue()), + tmapBody.get( J ).asInstanceOf[Tree]) :: ncases; + //j = j + 1; + } + if( n > 0 ) + //gen.Switch( gen.Ident( pos, targetSym ), tags, targets, code_error() ); + Match(Ident( targetSym ), ncases); + else + code_error(); + } + + // calling the AlgebraicMatcher here + override def _cur_match(pat1: Tree): Tree = { + var pat = pat1; + //System.out.println("RTiS._cur_match("+pat.toString()+")"); + //System.out.println("calling algebraic matcher on type:"+pat.type); + + //System.err.println( "curT"+currentElem().type().widen() ); + val m = new PartialMatcher { + val owner = RightTracerInScala.this.owner; // , //funSym,//this.funSym, + val selector = currentElem(); //, + // result type defs.boolean_TYPE() ); + } + val freshenMap = new HashMap(); // sym2exp -> new sym + val helpMap3 = new HashMap(); // new sym -> original sym + + // "freshening": never use the same symbol more than once + // (in later invocations of _cur_match) + + var it = varsToExport.iterator(); + while(it.hasNext() ) { + val key = it.next().asInstanceOf[Symbol]; + if( key.name.toString().indexOf("$") == -1 ) { + this.helpMap2.put( key, helpMap.get( key )); + // "freshening" by appending string ( a bit dangerous ) + val newSym = key.cloneSymbol( owner /*funSym*/ ); + newSym.name = newTermName(key.name.toString() + "%") ; // erm + freshenMap.put( key, newSym ); + helpMap3.put( newSym, helpMap.get( key )); + //System.out.println( "key: "+ key + " key.owner:"+key.owner()); + //System.out.println( "newsym owner:"+newSym.owner()); + } else { + freshenMap.put( key, key ); + } + } + + //System.out.println("RightTracerInScala:: -pat :"+pat.toString()); + /* + System.out.println("RightTracerInScala - the seqVars"+seqVars); + System.out.println("RightTracerInScala - the varsToExport"+varsToExport); + */ + //System.out.println("RightTracerInScala::freshenMap :"+freshenMap); + + // "freshening" + + //@nsc @todo @todo @todo @todo + + //val tc = new TreeCloner( global, freshenMap, Type.IdMap ); + //pat = tc.transform( pat ); + //@nsc this commented out, is broken anyway. + + // val match case <pat> => <do binding>; true + // case _ => false + + + var ts: scala.List[Tree] = scala.List(); //new Array[Tree]( helpMap3.keySet().size() ); + //var j = 0; + var jt = helpMap3.keySet().iterator(); + while(jt.hasNext()) { + val vsym = jt.next().asInstanceOf[Symbol]; + val hv = helpMap3.get( vsym ).asInstanceOf[Symbol]; + //hv.setInfo( defs.LIST_TYPE( elementType ) ) ; DEBUG ALARM ? + ts = Assign( Ident(hv), Ident(vsym) ) :: ts; + //ts( j ) = gen.; + //j = j + 1; + // System.out.println( "the assign" + res[ j - 1 ] ); + } + + val theBody = Block(ts, Literal( true )); // just `true' + + am.construct( m, scala.List( + CaseDef( pat, theBody), // freshening + // if tree val matches pat -> update vars, return true + CaseDef(Ident(definitions.PatternWildcard), Literal(false))), + // else return false + true // do binding please + ); + + am.toTree(); + } + + /** returns translation of transition with label from i. + * returns null if there is no such transition(no translation needed) + */ + override def code_delta(i: Int , label: Label ): Tree = { + val hmap = dfa.deltaq( i ); + val ntarget = hmap.get( label ).asInstanceOf[Integer]; + var algMatchTree: Tree = null; + if( ntarget == null ) + return null; + + //System.out.println("delta("+i+","+label+")" ); + var theLab: Label = null; + label match { + case LPair ( state, lab2 )=> + //assert ntarget == state; + theLab = lab2; + lab2 match { + case TreeLabel( pat ) => + algMatchTree = _cur_match( pat ); + case _ => + } + case DefaultLabel() => + scala.Predef.error("bla"); // should not happen + } + //assert dfa.qbinders != null : "qbinders ?"; + + var vars = dfa.qbinders(i); + + //System.out.println("dfa.qbinders[ i ]"+vars); + + if (null == vars) vars = new Vector(); // TODO: make this more consistent + //assert vars != null; + + var stms = if (algMatchTree != null ) algMatchTree::Nil else Nil; + + var it = vars.iterator(); + while(it.hasNext()) { + val vble = it.next().asInstanceOf[Symbol]; + val rhs = gen.Ident( curSym ); + stms = prependToHelpVar( vble , rhs) :: stms; + } + + val value = callFun( scala.List( SeqTrace_tail( _iter() ), + Literal(ntarget.intValue()))); + + Block(stms, value ); + } + + override def stateWrap(i: Int): Tree = { + if (i == 0) + code_state0_NEW(); + else + code_state_NEW(i); + } + + /* returns statements that do the work of the right-transducer + */ + def getStms(trace: Tree, unit: CompilationUnit, body: Tree): Tree = { + + var stms: scala.List[Tree] = scala.List(); + val loopbody = code_body_NEW(); + + stms = ( + scala.List( + ValDef( iterSym, trace ), + ValDef( stateSym, Literal( 0 )) + ) ::: helpVarDefs + ::: scala.List( + LabelDef( + this.funSym, + scala.List ( + iterSym, + stateSym + ), + loopbody ) + )); + + // bind variables handled by this righttracer + var it = seqVars.iterator(); + while(it.hasNext()) + stms = stms ::: bindVar( it.next().asInstanceOf[Symbol] ) :: Nil; + + val treeCloner = new Transformer { + override def transform(tree1: Tree): Tree = { + val tree = super.transform(tree1); + if (tree.hasSymbol) { + val symbol = helpMap2.get(tree.symbol); + if (symbol != null) tree.setSymbol(symbol.asInstanceOf[Symbol]); + } + tree; + } + }; + + Block(stms, treeCloner.transform( body )); + } + + + /** return the accumulator. (same as in LeftTracerInScala) + * todo: move tree generation of Unit somewhere else + */ + override def run_finished(state: Int): Tree = Literal(()); + + def current() = Ident( targetSym ); + + def refHelpVar(realVar: Symbol) = { + val hv = helpMap.get( realVar ).asInstanceOf[Symbol]; + //assert hv != null : realVar; + Ident(hv); + } + + def assignToHelpVar(realVar: Symbol, rhs: Tree): Tree = { + val hv = refHelpVar(realVar); + Assign(hv, rhs); + } + + def bindVar(realVar: Symbol): Tree = { + val hv = refHelpVar(realVar); + /* + System.out.println("binding realVar.name "+realVar.name+" type:"+realVar.type()+" to hv type:"+hv.type()); + realVar.setOwner( owner ); + System.out.println("is same as realVar"+realVar.type().isSameAs( elementType )); + System.out.println("is same as hv"+realVar.type().isSameAs( hv.type() )); + if( realVar.type().isSameAs( elementType )) + return gen.ValDef( realVar, SeqList_head( hv )); + else + return gen.ValDef( realVar, hv ); + */ + if( isSameType(realVar.tpe, hv.tpe)) + ValDef( realVar, hv ); // e.g. x @ _* + else { + ValDef( realVar, SeqList_head( hv )); + } + } +} +} diff --git a/src/compiler/scala/tools/nsc/matching/SequenceMatchers.scala b/src/compiler/scala/tools/nsc/matching/SequenceMatchers.scala new file mode 100644 index 0000000000..d2d8aa7414 --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/SequenceMatchers.scala @@ -0,0 +1,173 @@ +/* NSC -- new scala compiler + * Copyright 2005 LAMP/EPFL + * @author buraq + */ +// $Id$ + +package scala.tools.nsc.matching; + +import java.util._ ; + +/** constructs a matcher for a sequence pattern. plays two roles in + * described in design pattern Builder. + * is the "Director" for "Builder" class BerrySethi. + * is the "Builder" for "Director" class TransMatch. + */ + +trait SequenceMatchers: TransMatcher { + + import global._; + + class SequenceMatcher { + + // Console.println("CONSTR SEQUENCEMATCHER"); + final val IGNORED = new Integer(42); + + var _m: PartialMatcher = _; + + var bbuild: BindingBerrySethi = null; + + /** collects variables + * @return all variables bound by this binding nfa + */ + def collectNfaVariables(nfa: NondetWordAutom): Set = { + val seqVars = new HashSet(); + var j = 0; + while(j < nfa.nstates) { + if( nfa.qbinders( j ) != null ) + seqVars.addAll( nfa.qbinders( j ) ); + j = j + 1 + } + seqVars; + } + + + /** translates the det/switching automaton to scala code + * precondition: pat.type() corresponds to element type + */ + def addBinderToBody( pat1:Tree , body:Tree ): Tree = { + if( bbuild == null ) + bbuild = new BindingBerrySethi; + + val elementType1 = getElemType_Sequence( pat1.tpe ); + + // (a) build *binding* nfa (sequential machine) + val left = bbuild.automatonFrom( pat1, IGNORED ); + val right = bbuild.revnfa; + + // (b) determinize + translate L + + val dLeft = new DetWordAutom( left ); + + val ltis = new LeftTracerInScala { + val dfa = dLeft; + val owner = _m.owner; + val selector = _m.selector; + val elementType = elementType1; + } + + val trace = ltis.getTrace(); + + // (c) determinize + translate R + + val dRight = new DetWordAutom( right, left, dLeft ); + + val seqVars1 = collectNfaVariables( left ); + //System.out.println("seqVars here are:"+seqVars); + val rtis = new RightTracerInScala { + val dfa = dRight; + val owner = _m.owner; + val pat = pat1; + val seqVars = seqVars1; + val elementType = elementType1; + } + + // !!! Tree stms2 = rtis.getStms( theTrace, cunit, body ); + // !!! gen.mkBlock_( body.pos, trace, stms2 ); + val stms2 = rtis.getStms( trace, cunit, body ); + stms2; + } + + private def buildNfas( pat:scala.List[Tree] ): Array[NondetWordAutom] = { + val build = new BerrySethi; + val manyNfa = new Array[NondetWordAutom]( pat.length ); + var i = 0; + val it = pat.elements; + while( i < pat.length ) { + manyNfa( i ) = build.automatonFrom( it.next, new Integer( i )); + i = i + 1; + //manyNfa[ i ].print(); + } + manyNfa; + } + + /** constructs a word recognizer from an array of patterns which + * should all be SequencePatterns ( no wildcard * ) + * precondition: pat.type corresponds to element type + * @param _m Matcher object, holds the result + * @param pat the (Sequence) patterns + * @param body the bodies + * @param defaultCase code that is run when nothing matches. may be null, it + * becomes a ThrowMatchError then + * @param doBinding flasg that indicates whether variables should be bound + */ + def construct(_m: PartialMatcher, pat: scala.List[Tree] , body: scala.List[Tree] , defcase1: Tree, doBinding: Boolean ): Unit = { + var defaultCase = defcase1; + this._m = _m; + //assert body.length == pat.length; + if( defaultCase == null ) + defaultCase = ThrowMatchError( _m.pos, resultType ); + + val seqType = pat( 0 ).tpe; + val elementType1 = getElemType_Sequence( seqType ); + + // STEP 1 - build nfas for each pattern + + val manyNfa = buildNfas( pat ); + + // STEP 2 - recognizing + + // (a) merge nfas into one if necessary + val nfa = if(pat.length > 1) + new NondetWordAutom( manyNfa ) + else + manyNfa( 0 ); + + //nfa.print(); + + // (b) determinize + val dfa1 = new DetWordAutom( nfa ); + + // (c) translate to scala code + val scalaAut = + new WordAutomInScala{ + val dfa = dfa1; + val owner = _m.owner; + val optim = settings.target == "jvm"; + val elementType = elementType1; + } + scalaAut.translate(); + + // STEP 3 - binding + + var newbody: scala.List[Tree] = Nil; + if( !doBinding ) + newbody = body; + else { // this is done in the body of the matching case + var i = 0; + while(i < body.length) { + if( !containsBinding( pat( i ) ) ) + newbody = body( i ) :: newbody; // no need for binding + else + newbody = addBinderToBody( pat( i ), body( i ) ) :: newbody; + i = i + 1; + } + newbody = newbody.reverse; + } + _m.tree = scalaAut.getMatcherSwitch( _m.selector, + defaultCase, + newbody ); + } // construct (PartialMatcher, Tree[], Tree[], Tree, boolean ) + + } // class SequenceMatcher +} diff --git a/src/compiler/scala/tools/nsc/matching/StateSetComparator.scala b/src/compiler/scala/tools/nsc/matching/StateSetComparator.scala new file mode 100644 index 0000000000..99942f38d5 --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/StateSetComparator.scala @@ -0,0 +1,34 @@ +package scala.tools.nsc.matching ; + +import java.util.{Comparator, TreeSet} ; + +class StateSetComparator extends Comparator { + // use lexicographic order + def compare(o1: Any , o2: Any ): Int = { + /* + System.out.print("lexi" ); + System.out.print( o1 +" "); + System.out.println( o2 ); + */ + val it1 = o1.asInstanceOf[TreeSet].iterator(); + val it2 = o2.asInstanceOf[TreeSet].iterator(); + while( it1.hasNext() ) { + while( it2.hasNext() ) { + if( !it1.hasNext() ) + return -1; + + val i1 = it1.next().asInstanceOf[Integer].intValue(); + val i2 = it2.next().asInstanceOf[Integer].intValue(); + if( i1 < i2 ) + return -1; + else if ( i1 > i2 ) + return 1; + } + if( it1.hasNext() ) + return 1; + } + if( it2.hasNext() ) + return -1; + return 0; + } +} diff --git a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala new file mode 100644 index 0000000000..bca478b0dc --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala @@ -0,0 +1,301 @@ +/* NSC -- new scala compiler + * Copyright 2005 LAMP/EPFL + * @author buraq + */ +// $Id$ +package scala.tools.nsc.matching; + +/** Translation of pattern matching + */ +abstract class TransMatcher extends transform.Transform +with PatternNodes +with CodeFactory +with PatternMatchers +with SequenceMatchers +with AlgebraicMatchers +with MatcherLabels +with BerrySethis +with DetWordAutoms +with NondetWordAutoms +with Autom2 +with WordAutoms +with LeftTracers +with RightTracers { + + import global._; + import definitions._; + import posAssigner.atPos; + import typer.typed; + + val phaseName = "transmatcher"; + + protected def newTransformer(unit: global.CompilationUnit): global.Transformer = { + cunit = unit; + new TransMatch + } + + /** container. classes AlgebraicMatcher and SequenceMatcher get input and + * store their results in here. resembles the 'Memento' design pattern, + * could also be named 'Liaison' + */ + abstract class PartialMatcher { + + /** owner of the code we create (input) + */ + val owner: Symbol; + + /** the selector value (input) + */ + val selector:Tree; + + /** tree representing the matcher (output) + */ + var tree: Tree = _ ; + + def pos: int = selector.pos; + + //assert( owner != null ) : "owner is null"; + //assert owner != Symbol.NONE ; + //this.owner = owner; + + //assert root != null; + //assert root.type != null; + //this.selector = root; + + //assert this.resultType != Type.NoType; + //this.resultType = resultType; + + //this.pos = root.pos; // for convenience only + + } + + var cunit: CompilationUnit = _; + + def fresh = cunit.fresh ; + + var currentOwner: Symbol = _; + + var resultType: Type = _; + + def containsBinding(pat: Tree): Boolean = { + var generatedVars = false; + + def handleVariableSymbol(sym: Symbol): Unit = + if (sym.name.toString().indexOf("$") == -1) { + generatedVars = true; // .add(sym); + } + + def isVariableName(name: Name): Boolean = + ( treeInfo.isVariableName(name) ) && ( name != nme.USCOREkw ) ; + + def isVariableSymbol(sym: Symbol): Boolean = + ( sym != null )&&( !sym.isPrimaryConstructor ); + + def traverse(tree: Tree): Unit = { + + tree match { + case x @ Ident(name) => + if(x.symbol != definitions.PatternWildcard) + error("shouldn't happen?!"); + + case Bind(name, subtree) => + var sym: Symbol = null; + + if (isVariableName(name) + && isVariableSymbol( {sym = tree.symbol; tree.symbol} )) + handleVariableSymbol(sym); + + traverse( subtree ); + + // congruence + + case Apply(fun, args) => args foreach traverse; + case Sequence(trees) => trees foreach traverse + case Star(arg) => traverse(arg) + case Typed(expr, tpe) => traverse(expr); // needed?? + + case _ : Select | + _ : Alternative | + _ : Select | + _ : Literal => ; // no variables + + case _ => + error("unknown pattern node:" + tree + " = " + tree.getClass()); + } + } + traverse(pat); + generatedVars; + } + + class TransMatch extends Transformer { + + /** a casedef with sequence subpatterns like + * + * case ..x @ ().. => body + * + * should be replaced straight away with + * + * case .. () .. => val x = Nil; body + */ + def isRegular(pats:List[CaseDef]): Pair[List[CaseDef],Boolean] = { + var existsReg = false; + var isReg = false; + var nilVars:List[Symbol] = null; + + def isRegular1(pat: Tree): Tree = pat match { + case Alternative(trees) => + copy.Alternative(pat, trees map { isRegular1 }); + + case Star(t) => isReg = true; copy.Star(pat, isRegular1(t) ); + + case Ident(_) => pat; + + case Bind( id, empt @ Sequence(List())) => + nilVars = pat.symbol /*id.symbol()*/ :: nilVars; + empt; + case Bind( n, pat1 ) => copy.Bind(pat, n, isRegular1( pat1 )); + + case Sequence( trees ) => + //isReg = isReg || ( trees.length == 0 ); + isReg = true; // cause there are ArrayValues now + copy.Sequence(pat, trees map { isRegular1 }); + + case ArrayValue( tt, List(b @ Bind(id, Star(wc @ Ident(nme.WILDCARD))))) => + //Console.println("OPTIMIZING"); + //Console.println(pat); + //Console.println(pat.tpe); + //Console.println(b.tpe); + b.symbol.setInfo(pat.tpe); + b.setType(pat.tpe); + val res = copy.Bind(b, id, wc); + //Console.println("====>"); + //Console.println(res); + res + + case ArrayValue( s, trees ) => + //Console.println("XXX ArrayValue, trees="+trees); + copy.ArrayValue( pat, s, (trees map { isRegular1 })); + + case Apply( fn, List(Sequence(List()))) => + pat; + + case Apply( fn, trees ) => + //Console.println(" IN isRegular, apply node "+pat.toString()); + //Console.println(" trees are:"+(trees map {x => x.getClass().toString()})); + copy.Apply( pat, fn, ( trees map { isRegular1 }) ) + + case Literal(_) => pat + case Select(_,_) => pat + case Typed(_,_) => pat + + //case _ => + // Console.println(pat); + // Console.println(pat.getClass()); + // scala.Predef.error(" what is this ? ") + } + + var res:List[CaseDef] = Nil; + val it = pats.elements; while(it.hasNext) { + nilVars = Nil; + val cdef = it.next; + val newt = isRegular1(cdef.pat); + existsReg = existsReg || isReg; + + val nbody = if(nilVars.isEmpty) cdef.body else + atPos(cdef.body.pos)( + Block(nilVars map { + x => ValDef(x, Ident(definitions.NilModule)) + }, cdef.body) + ); + + res = copy.CaseDef(cdef, newt, cdef.guard, nbody) :: res; + } + Pair(res.reverse, existsReg); + } + + + + def handle(sel:Tree, ocases:List[CaseDef]): Tree = { + + + // 1. is there a regular pattern? + + val Pair(cases, containsReg) = isRegular(ocases); + + // @todo: remove unused variables + + if(containsReg) { + // 2. replace nilVariables + //@todo: bring over AlgebraicMatcher + /* + val matcher = new PartialMatcher { + val global: TransMatcher.this.global.type = TransMatcher.this.global; + val owner = currentOwner; + val selector = sel ; + } + new AlgebraicMatcher() { + val tm: TransMatcher.this.type = TransMatcher.this; + }.construct( matcher, cases ); + matcher.tree + */ + System.out.println("" + sel + " match " + ocases); + scala.Predef.error("regular expressions not yet implemented"); + } else { + val pm = new PatternMatcher(); + pm.initialize(sel, currentOwner, true ); + pm.construct( cases ); + //if (global.log()) { + // global.log("internal pattern matching structure"); + // pm.print(); + //} + pm.toTree() + } + } + override def transform(tree: Tree): Tree = tree match { + /* // test code to generate forward jumps + case Match(selector, CaseDef(Ident(nme.WILDCARD), EmptyTree, exp)::Nil) => // inserting test-code + + val target1 = currentOwner.newLabel(tree.pos, "target1") + .setInfo(new MethodType(List(definitions.IntClass.tpe), definitions.IntClass.tpe)); + + val a = currentOwner.newValue(tree.pos, "a").setInfo(definitions.IntClass.tpe); + val x = currentOwner.newValueParameter(tree.pos, "x").setInfo(definitions.IntClass.tpe); + val y = currentOwner.newValueParameter(tree.pos, "y").setInfo(definitions.IntClass.tpe); + val target2 = currentOwner.newLabel(tree.pos, "target2") + .setInfo(new MethodType(List(definitions.IntClass.tpe, definitions.IntClass.tpe), definitions.IntClass.tpe)); + + val z = currentOwner.newValueParameter(tree.pos, "z").setInfo(definitions.IntClass.tpe); + typed { atPos(tree.pos) { Block( + List( + Apply(Ident(target2), List(Literal(Constant(1)),Literal(Constant(2)))), + LabelDef(target1, List(x), exp)), + LabelDef(target2, List(y,z), Apply(Select(Ident(y), nme.PLUS), List(Ident(z)))) + )}}; +*/ + + case Match(selector, cases) => + val nselector = transform(selector).setType(selector.tpe); + val ncases = cases map { transform }; +/* + Console.println("TransMatch translating cases: "); + for(val t <- cases) { + Console.println(t.pat.toString()); + Console.println("BODY "+t.body.toString()); + } +*/ + // @todo: remove from partial matcher + TransMatcher.this.currentOwner = currentOwner; + TransMatcher.this.resultType = tree.tpe; + //Console.println("TransMatcher currentOwner ="+currentOwner+")"); + //Console.println("TransMatcher selector.tpe ="+selector.tpe+")"); + //Console.println("TransMatcher resultType ="+resultType+")"); + val t_untyped = handle(nselector, ncases.asInstanceOf[List[CaseDef]]); + //Console.println("t_untyped "+t_untyped.toString()); + val t = typed { atPos(tree.pos) (t_untyped) }; + //Console.println("t typed "+t.toString()); + t + case _ => + super.transform(tree); + } + } +} diff --git a/src/compiler/scala/tools/nsc/matching/WordAutoms.scala b/src/compiler/scala/tools/nsc/matching/WordAutoms.scala new file mode 100644 index 0000000000..de17fc6445 --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/WordAutoms.scala @@ -0,0 +1,146 @@ +/* NSC -- new scala compiler + * Copyright 2005 LAMP/EPFL + * @author buraq + */ +// $Id$ + +package scala.tools.nsc.matching; + +import java.util._ ; + +import scala.tools.nsc.util.Position; + +trait WordAutoms: TransMatcher { + + import global._ ; + /** translates a recognizer to scala code + */ + + /** constructor + * @param dfa the dfa that is to be translated + * @param elementType type of the objects in the sequence + * @param owner the owner of the pattern match + * @param cf code factory + * @param optim flag that indicates whether to optimize + * @return an object that translates the dfa + */ +abstract class WordAutomInScala extends Autom2Scala { + + val optim: Boolean; + + this.optimize = this.optimize && optim; + + var theLabelDef: Tree = _ ; + + def getMatcherSwitch(selector: Tree, failTree: Tree, body: scala.List[Tree] /*, resultType: Type*/ ): Tree = { + + var result: Tree = null; + var ncases: scala.List[CaseDef] = Nil; + val it = body.reverse.elements; + //val tags = new Array[int](body.length); + var i = body.length - 1; + while( i >= 0 ) { + //tags(i) = i; + ncases = CaseDef(Literal(i), it.next) :: ncases; + i = i - 1 + } + + ncases= ncases::: CaseDef(Ident(nme.WILDCARD),failTree) :: Nil; + result = Match( _swres(), ncases ); + + //} + + result = + Block( + scala.List ( + ValDef( iterSym, newIterator( selector.duplicate )), + ValDef( stateSym, Literal(0) ), + ValDef( resultSym, theLabelDef )), + result + ); + //unit.global.debugPrinter.print( result ); + result; + } + + protected def initializeSyms(): Unit = { // TEST + + this.funSym = owner.newLabel( pos, fresh.newName( "matcher" )); + + this.iterSym = owner.newVariable( pos, fresh.newName("iter")) + .setInfo( _seqIterType( elementType ) ) ; + + this.stateSym = owner.newVariable( pos, fresh.newName("q")) + .setInfo( definitions.IntClass.info ) ; + + this.resultSym = owner.newVariable( pos, fresh.newName("swRes")) + .setInfo( definitions.IntClass.info ) ; + + this.funSym.setInfo( MethodType(scala.List (definitions.IntClass.info), + definitions.IntClass.info )); + + this.curSym = owner.newVariable( pos, "cur" /*Names.cur*/ ) + .setInfo( elementType ); + + this.hasnSym = owner.newVariable( pos, nme.hasNext ) + .setInfo( definitions.BooleanClass.info ); + + } + + /** code for the return value of the automaton translation + */ + override def run_finished(state: Int): Tree = { // T E S T + if( dfa.isFinal(state)) + Literal(dfa.finals.get(new Integer(state)).asInstanceOf[Integer].intValue()); + else + Literal(FAIL); + } + + + // calling the /*AlgebraicMatcher*/PatternMatcher here + override def _cur_match(pat: Tree): Tree = { // TE ST + val m = new PartialMatcher { + val owner = WordAutomInScala.this.owner; /* owner*/ + val selector = currentElem(); /* root */ + // restyp definitions.BooleanClass.info /* restype */); + } + + am.construct( m, scala.List ( + CaseDef( pat, Literal( true )), + CaseDef( Ident(definitions.PatternWildcard), Literal( false )) ), + false); + am.toTree(); + } + + /** do the translation + */ + def translate(): Unit = { + initializeSyms(); + val tb = code_body_NEW(); + //theLabelDef = gen.DefDef(this.funSym, tb); + theLabelDef = LabelDef(this.funSym, scala.List( stateSym ), tb); + } + + /** ... + * @return returns translation of transition with label from i. + * returns null if there is no such transition + * (no translation needed) + */ + override def code_delta(i: Int, label: Label): Tree = { + val target = dfa.delta(i, label); + + if (target == null) + label match { + case DefaultLabel() => + code_error(); // this may not happen ! + case _ => + null; // not good + } + else if (target.intValue() == dfa.nstates() - 1) // that one is a dead state + code_fail(); + else + callFun(scala.List( Literal(target.intValue() ))); + } + +} +} + |