diff options
author | buraq <buraq@epfl.ch> | 2003-06-20 13:43:05 +0000 |
---|---|---|
committer | buraq <buraq@epfl.ch> | 2003-06-20 13:43:05 +0000 |
commit | 7454e3a00975ed23503e5db89647b013065df8f2 (patch) | |
tree | a895b2c7d5ef6a1a65f8ba0ad15feb6725f12e1b | |
parent | cefb352f0f5fb0280bc0dd7de7510744a11ec17c (diff) | |
download | scala-7454e3a00975ed23503e5db89647b013065df8f2.tar.gz scala-7454e3a00975ed23503e5db89647b013065df8f2.tar.bz2 scala-7454e3a00975ed23503e5db89647b013065df8f2.zip |
added Autom2Scala and related methods (pattern ...
added Autom2Scala and related methods (pattern matching)
-rw-r--r-- | sources/scalac/transformer/matching/Autom2Scala.java | 390 | ||||
-rw-r--r-- | sources/scalac/transformer/matching/CodeFactory.java | 286 | ||||
-rw-r--r-- | sources/scalac/transformer/matching/PatternTool.java | 41 |
3 files changed, 597 insertions, 120 deletions
diff --git a/sources/scalac/transformer/matching/Autom2Scala.java b/sources/scalac/transformer/matching/Autom2Scala.java new file mode 100644 index 0000000000..151e41f35e --- /dev/null +++ b/sources/scalac/transformer/matching/Autom2Scala.java @@ -0,0 +1,390 @@ +package scalac.transformer.matching ; + +import scalac.* ; +import scalac.typechecker.* ; +import scalac.symtab.Symbol ; +import scalac.symtab.Type ; +import scalac.symtab.TermSymbol ; +import scalac.symtab.Definitions ; +import scalac.ast.Tree; +import scalac.ast.TreeGen; +import scalac.util.Name; +import Tree.*; + +import scalac.transformer.TransMatch.Matcher ; +import java.util.* ; + +import ch.epfl.lamp.util.Position; + +public class Autom2Scala { + + static final Name WILDCARD_N = Name.fromString("_"); + static final Name CURRENT_ELEM = Name.fromString("cur"); + + final int FAIL = -1; + + DetWordAutom dfa; + protected CodeFactory cf; + + Vector freeVars; + Vector mdefs; + //Tree matcherDef; + //Tree matcherSwitch; + + Definitions defs; + TreeGen gen; + + /** owner of the pattern matching expression + */ + protected Symbol owner; + + /** symbol of the matcher fun + */ + Symbol funSym; + + /** symbol of the iterator ( scala.SequenceIterator ) + */ + Symbol iterSym; + + /** symbol of the switching result ( scala.Int ) + */ + Symbol resultSym; + + /** symbol of the state variable ( scala.Int ) + */ + Symbol stateSym; + + protected Type elementType; + + public int pos; + + String funSymName; + + Symbol newFunSym( String prefix ) { + return new TermSymbol( /*Kinds.FUN, */ + pos, + cf.fresh.newName( prefix ), + owner, + 0); + } + + Symbol newParam( String prefix ) { + return new TermSymbol( /*Kinds.VAL, */ + pos, + cf.fresh.newName( prefix ), + funSym, + 0); + } + + Type funRetType() { + switch( funSym.type() ) { + case MethodType( _, Type retType ): + return retType; + } + throw new RuntimeException(); + } + + + Tree callFun( Tree[] args ) { + return gen.Apply( pos, + gen.Ident( pos, funSym ), + args).setType( funRetType() ); + } + + + /** init funSym, iterSym, stateSym, resultSym + allocate mdefs. + * a subclass overriding initializeSyms may change these + * (esp. funSym) + */ + protected void initializeSyms() { + if( funSymName == null ) + funSymName = "matcher"; + // the function that does the matching + + this.funSym = newFunSym( funSymName ); + + this.iterSym = newParam("iter") + .setType( cf._seqIterType( elementType ) ) ; + + this.stateSym = newParam("q") + .setType( defs.INT_TYPE ) ; + + this.resultSym = new TermSymbol( /*Kinds.VAR,*/ + pos, + cf.fresh.newName("swRes"), + owner, + 0 ) + .setType( defs.INT_TYPE ) ; + + this.funSym + .setType( new Type.MethodType( new Symbol[] { + iterSym, stateSym }, defs.INT_TYPE )); + + this.curSym = new TermSymbol( /*Kinds.VAL, */ + pos, + CURRENT_ELEM, + funSym,//clazzOwner, + 0) + .setType( elementType ); + + } + + + public Autom2Scala( DetWordAutom dfa, + Type elementType, + Symbol owner, + CodeFactory cf ) { + this.dfa = dfa; + this.elementType = elementType; + this.defs = cf.defs; + this.gen = cf.gen; + this.owner = owner; + this.pos = 0; + this.cf = cf; + this.am = new /*AlgebraicMatcher*/PatternMatcher( cf.unit, cf.infer ); + this.mdefs = new Vector(); + + this.freeVars = new Vector(); + } + + public Tree theDefDef; + + Symbol curSym; + + Tree loadCurrentElem() { + return cf.gen.ValDef( 0, + this.curSym, + cf._cur( _iter() )); + } + + Tree currentElem() { + return gen.Ident(0, curSym); + } + + Tree currentMatches( Label label ) { + return _cur_eq( _iter(), label ); + } + + // + // translation of automata to scala code + // + + + /** creates an int variable + */ + Tree _intvar( Symbol sym, Tree init ) { + return gen.ValDef( pos, sym, init ); + /* + Kinds.VAR, + new ModifierSet(), + sym.name, + gen.mkType(pos, defs.INT_TYPE), + init) + .setType( defs.UNIT_TYPE ) + .symbol( sym );*/ + } + + /** `<sym> = val' + Tree code_assignInt( Symbol sym, Integer val ){ + return make.Assign(pos, + code_ref( sym ), + gen.mkIntLit(Position.NOPOS, val )) + .setType( defs.UNIT_TYPE ); + } + */ + + + + // the caller needs to set the type ! + Tree _applyNone( Tree arg ) { + return cf.make.Apply(pos, arg, Tree.EMPTY_ARRAY/*None*/ ); + } + + + + + + + + Tree _scala() { + // return gen.mkId( defs.SCALA ) // try this + return gen.Ident(pos, defs.SCALA ); /*make.Ident( pos, + SCALA_N ) + .setType( defs.SCALA.type() ).symbol( defs.SCALA );*/ + } + + + /** `<switchResult>' + */ + public Tree _swres() { return gen.Ident( pos, resultSym );} + + /** `<state>' + */ + public Tree _state() { return gen.Ident( pos, stateSym ); } + + /** code to reference the iterator + */ + Tree _iter() { return gen.Ident( pos, iterSym ); } + + /** body of the matcherDefFun + */ + public Tree code_body() { + + Tree body = code_fail(); // never reached at runtime. + + // state [ nstates-1 ] is the dead state, so we skip it + + //`if( state == q ) <code_state> else {...}' + for( int i = dfa.nstates-2; i >= 0; i-- ) { + body = code_state( i, body ); + } + return body; + + } + + Tree _cur_eq( Tree iter, Label label ) { + switch( label ) { + case TreeLabel( Tree pat ): + return _cur_match( pat ); + case SimpleLabel( Tree.Literal lit ): + return cf.Equals( currentElem(), lit ); + } + throw new ApplicationError("expected either algebraic or simple label:"+label); + } + + /*AlgebraicMatcher*/PatternMatcher am; + + void handleVars( ) { + } + + // returns a Tree whose type is boolean. + Tree handleBody( Object help ) { + // don't care about free vars + return gen.mkBooleanLit( Position.NOPOS, true ); + } + + // calling the /*AlgebraicMatcher*/PatternMatcher here + Tree _cur_match( Tree pat ) { + //System.out.println("calling algebraic matcher on type:"+pat.type); + + Matcher m = new Matcher( funSym,//this.funSym, + currentElem(), + defs.BOOLEAN_TYPE ); + + am.construct( m, new CaseDef[] { + (CaseDef) cf.make.CaseDef( pat.pos, + pat, + Tree.Empty, + handleBody( freeVars )), + (CaseDef) cf.make.CaseDef( pat.pos, + cf.make.Ident(pat.pos, WILDCARD_N) + .setSymbol( Symbol.NONE ) + .setType(pat.type()), + Tree.Empty, + gen.mkBooleanLit( pat.pos, false )) }/*, + false*/ + ); + Tree res = am.toTree().setType( defs.BOOLEAN_TYPE ); + return res; + } + + Tree code_delta( int i, Label label ) { + throw new RuntimeException(); + } + + Tree code_fail() { + return gen.mkIntLit(Position.NOPOS, FAIL ); + } + + /** code for the return value of the automaton translation + */ + Tree run_finished( int state ) { + if( dfa.isFinal( state )) { + return gen.mkIntLit(Position.NOPOS, ((Integer) dfa.finals.get( new Integer( state ) )).intValue() ); + } + return gen.mkIntLit(Position.NOPOS, FAIL ); + } + + Tree wrapStateBody0( Tree stateBody, + Tree elseBody, + int i ) { + return cf.If( cf.Equals( _state(), gen.mkIntLit(Position.NOPOS, i )), + stateBody , + elseBody ); + } + + // val cur := iter.cur() + + Tree wrapStateBody( Tree stateBody, + Tree elseBody, + Tree runFinished, int i ) { + stateBody = cf.If( cf._noMoreCur( _iter() ), + runFinished, + cf.Block( stateBody.pos, + new Tree[] { + loadCurrentElem(), + stateBody}, + stateBody.type()) ); + + return wrapStateBody0( stateBody , elseBody, i ); + } + + /** return code for state i of the dfa + */ + Tree code_state( int i, Tree elseBody ) { + + Tree runFinished; // holds result of the run + int finalSwRes; + + runFinished = run_finished( i ); + + + if( dfa.isSink( i ) ) // state won't change anymore (binding?) + return cf.If( cf.Equals( _state(), gen.mkIntLit(Position.NOPOS, i )), + runFinished, + elseBody ); + + + Tree stateBody ; // action(delta) for one particular label/test + + // default action (fail if there is none) + + stateBody = code_delta( i, Label.DefaultLabel); + + /* + if( stateBody == null ) + stateBody = code_fail(); + */ + + // transitions of state i + + HashMap trans = ((HashMap[])dfa.deltaq)[ i ]; + + for( Iterator labs = dfa.labels.iterator(); labs.hasNext() ; ) { + Object label = labs.next(); + Integer next = (Integer) trans.get( label ); + + + Tree action = code_delta( i, (Label) label ); + + if( action != null ) { + + stateBody = cf.If( currentMatches((Label) label ), + action, + stateBody); + } + } + return wrapStateBody( stateBody, + elseBody, + runFinished, + i ); + } + + /** code to reference a variable + */ + Tree _ref( Symbol sym ) { + return gen.Ident( pos, sym ); + } + + +} diff --git a/sources/scalac/transformer/matching/CodeFactory.java b/sources/scalac/transformer/matching/CodeFactory.java index 0c0b6e89e8..92a8d4ec8f 100644 --- a/sources/scalac/transformer/matching/CodeFactory.java +++ b/sources/scalac/transformer/matching/CodeFactory.java @@ -20,9 +20,89 @@ import Tree.*; class CodeFactory extends PatternTool { - public CodeFactory( Unit unit, Infer infer ) { - super( unit, infer ); - } + static final Name SEQ_ITER_N = Name.fromString("scala.SequenceIterator"); + static final Name HAS_CUR_N = Name.fromString("hasCur"); + static final Name CUR_N = Name.fromString("cur"); + static final Name NEXT_N = Name.fromString("next"); + + /** symbol of `scala.SequenceIterator' + */ + Symbol seqIterSym; + + Symbol curSym; + Symbol hasCurSym; + Symbol nextSym; + + public CodeFactory( Unit unit, Infer infer ) { + super( unit, infer ); + + this.seqIterSym = defs.getType( SEQ_ITER_N ).symbol(); + Scope scp = seqIterSym.members(); + curSym = scp.lookup/*Term*/ ( CUR_N ); + assert !( curSym == Symbol.NONE ) : "did not find cur"; + } + + // --------- these are new + + /** If ... pos, type is copied from thenBody + */ + Tree If( Tree cond, Tree thenBody, Tree elseBody ) { + //assert( thenBody.type().equals( elseBody.type() ) + // || thenBody.type().isSubType( elseBody.type() ) + // /*|| elseBody.type().isSubType( thenBody.type() BUG */) + // : "you try to construct a naughty if " + // + "thenBody: "+thenBody.type+" elseBody:"+elseBody.type; + assert cond != null:"cond is null"; + assert thenBody != null:"thenBody is null"; + assert elseBody != null:"elseBody is null"; + return make.If( thenBody.pos, + cond, + thenBody, + elseBody ).setType( elseBody.type() ); + } + + /** `SequenceIterator[ elemType ]' // TODO: Move to TypeFactory + */ + Type _seqIterType( Type elemType ) { + return Type.TypeRef( defs.SCALA_TYPE/*PREFIX*/, + seqIterSym, + new Type[] { elemType }); + } + + // the caller needs to set the type ! + Tree _applyNone( Tree arg ) { + return make.Apply(Position.NOPOS, arg, Tree.EMPTY_ARRAY ); + } + + // todo: more defensive checking + Type getElemType( Type seqType ) { + Type[] args = seqType.typeArgs(); /*use typeArgs instead of args*/ + assert (args.length==1); + return args[ 0 ]; + + } + + /** `it.cur()' + */ + Tree _cur( Tree iter ) { + Type elemType = getElemType( iter.type() ); + return _applyNone( gen.Select( iter, curSym ).setType( elemType )) + .setType( elemType ); + } + + /** `it.hasCur()' + */ + public Tree _hascur( Tree iter ) { + return _applyNone( gen.Select( iter, hasCurSym )) + .setType( defs.BOOLEAN_TYPE ); + } + + /** `!it.hasCur()' + */ + public Tree _noMoreCur( Tree iter ) { + return _applyNone( gen.Select( _hascur( iter ), notSym )) + .setType( defs.BOOLEAN_TYPE ); + } /** return the analyzed type */ @@ -43,152 +123,152 @@ class CodeFactory extends PatternTool { return ts[0]; else if (ts.length > 1) switch (ts[ts.length - 1]) { - case Block(Tree[] ts0): - Tree[] ts1 = new Tree[ts0.length + ts.length - 1]; - System.arraycopy(ts, 0, ts1, 0, ts.length - 1); - System.arraycopy(ts0, 0, ts1, ts.length - 1, ts0.length); - return Block(pos, ts1, tpe); + case Block(Tree[] ts0): + Tree[] ts1 = new Tree[ts0.length + ts.length - 1]; + System.arraycopy(ts, 0, ts1, 0, ts.length - 1); + System.arraycopy(ts0, 0, ts1, ts.length - 1, ts0.length); + return Block(pos, ts1, tpe); } return make.Block(pos, ts).setType(tpe); } /* // unused - protected Tree Negate(Tree tree) { - switch (tree) { - case Literal(Object value): - return gen.mkBooleanLit(tree.pos, !((Boolean)value).booleanValue()); - } - return make.Apply( - tree.pos, - gen.Select(tree, NOT_N), - Tree.EMPTY_ARRAY).setType(defs.BOOLEAN_TYPE); - } + protected Tree Negate(Tree tree) { + switch (tree) { + case Literal(Object value): + return gen.mkBooleanLit(tree.pos, !((Boolean)value).booleanValue()); + } + return make.Apply( + tree.pos, + gen.Select(tree, NOT_N), + Tree.EMPTY_ARRAY).setType(defs.BOOLEAN_TYPE); + } */ protected Tree And(Tree left, Tree right) { switch (left) { - case Literal(Object value): - return ((Boolean)value).booleanValue() ? right : left; + case Literal(Object value): + return ((Boolean)value).booleanValue() ? right : left; } switch (right) { - case Literal(Object value): - if (((Boolean)value).booleanValue()) return left; + case Literal(Object value): + if (((Boolean)value).booleanValue()) return left; } Symbol fun = left.type.lookup(AND_N); return make.Apply( - left.pos, - make.Select( - left.pos, - left, - AND_N).setType(typeOf(fun)).setSymbol(fun), - new Tree[]{right}).setType(defs.BOOLEAN_TYPE); + left.pos, + make.Select( + left.pos, + left, + AND_N).setType(typeOf(fun)).setSymbol(fun), + new Tree[]{right}).setType(defs.BOOLEAN_TYPE); } protected Tree Or(Tree left, Tree right) { switch (left) { - case Literal(Object value): - return ((Boolean)value).booleanValue() ? left : right; + case Literal(Object value): + return ((Boolean)value).booleanValue() ? left : right; } switch (right) { - case Literal(Object value): - if (!((Boolean)value).booleanValue()) return left; + case Literal(Object value): + if (!((Boolean)value).booleanValue()) return left; } Symbol fun = left.type.lookup(OR_N); return make.Apply( - left.pos, - make.Select( - left.pos, - left, - OR_N).setType(typeOf(fun)).setSymbol(fun), - new Tree[]{right}).setType(defs.BOOLEAN_TYPE); + left.pos, + make.Select( + left.pos, + left, + OR_N).setType(typeOf(fun)).setSymbol(fun), + new Tree[]{right}).setType(defs.BOOLEAN_TYPE); } protected Tree Is(Tree tree, Type type) { return make.Apply( - tree.pos, - make.TypeApply( - tree.pos, - make.Select( - tree.pos, - tree, - defs.IS.name).setType(typeOf(defs.IS)).setSymbol(defs.IS), - new Tree[]{gen.mkType(tree.pos, type)}) - .setType(Type.MethodType(Symbol.EMPTY_ARRAY, defs.BOOLEAN_TYPE)), - Tree.EMPTY_ARRAY).setType(defs.BOOLEAN_TYPE); + tree.pos, + make.TypeApply( + tree.pos, + make.Select( + tree.pos, + tree, + defs.IS.name).setType(typeOf(defs.IS)).setSymbol(defs.IS), + new Tree[]{gen.mkType(tree.pos, type)}) + .setType(Type.MethodType(Symbol.EMPTY_ARRAY, defs.BOOLEAN_TYPE)), + Tree.EMPTY_ARRAY).setType(defs.BOOLEAN_TYPE); } protected Tree As(Tree tree, Type type) { return make.Apply( - tree.pos, - make.TypeApply( - tree.pos, - make.Select( - tree.pos, - tree, - defs.AS.name).setType(typeOf(defs.AS)).setSymbol(defs.AS), - new Tree[]{gen.mkType(tree.pos, type)}) - .setType(Type.MethodType(Symbol.EMPTY_ARRAY, type)), - Tree.EMPTY_ARRAY).setType(type); + tree.pos, + make.TypeApply( + tree.pos, + make.Select( + tree.pos, + tree, + defs.AS.name).setType(typeOf(defs.AS)).setSymbol(defs.AS), + new Tree[]{gen.mkType(tree.pos, type)}) + .setType(Type.MethodType(Symbol.EMPTY_ARRAY, type)), + Tree.EMPTY_ARRAY).setType(type); } protected Tree Equals(Tree left, Tree right) { Symbol fun = left.type.lookup(EQUALS_N); switch (typeOf(fun)) { - case OverloadedType(Symbol[] alts, Type[] alttypes): - //System.out.println("**** " + left.type); - Tree t = make.Select(left.pos, left, EQUALS_N); - //for (int i = 0; i < alttypes.length; i++) - // System.out.println(alts[i] + ": " + alttypes[i]); - infer.methodAlternative(t, alts, alttypes, - new Type[]{right.type}, defs.BOOLEAN_TYPE); - return make.Apply(left.pos, t, new Tree[]{right}).setType(defs.BOOLEAN_TYPE); - default: - //System.out.println("#### " + left.type + ": " + fun); - return make.Apply( - left.pos, - make.Select( - left.pos, - left, - EQUALS_N).setType(typeOf(fun)).setSymbol(fun), - new Tree[]{right}).setType(defs.BOOLEAN_TYPE); + case OverloadedType(Symbol[] alts, Type[] alttypes): + //System.out.println("**** " + left.type); + Tree t = make.Select(left.pos, left, EQUALS_N); + //for (int i = 0; i < alttypes.length; i++) + // System.out.println(alts[i] + ": " + alttypes[i]); + infer.methodAlternative(t, alts, alttypes, + new Type[]{right.type}, defs.BOOLEAN_TYPE); + return make.Apply(left.pos, t, new Tree[]{right}).setType(defs.BOOLEAN_TYPE); + default: + //System.out.println("#### " + left.type + ": " + fun); + return make.Apply( + left.pos, + make.Select( + left.pos, + left, + EQUALS_N).setType(typeOf(fun)).setSymbol(fun), + new Tree[]{right}).setType(defs.BOOLEAN_TYPE); } } protected Tree ThrowMatchError(int pos, Type type) { Symbol matchErrorModule = defs.SCALA.members().lookup(MATCHERROR_N); outer: switch (typeOf(matchErrorModule)) { - case OverloadedType(Symbol[] alts, Type[] alttypes): - for (int i = 0; i < alts.length; i++) - switch (alttypes[i]) { - case TypeRef(_, _, _): - matchErrorModule = alts[i]; - break outer; - } + case OverloadedType(Symbol[] alts, Type[] alttypes): + for (int i = 0; i < alts.length; i++) + switch (alttypes[i]) { + case TypeRef(_, _, _): + matchErrorModule = alts[i]; + break outer; + } } Symbol failMethod = typeOf(matchErrorModule).lookup(FAIL_N); return - make.Apply( - pos, - make.TypeApply( - pos, - make.Select( - pos, - make.Select( - pos, - make.Ident(pos, Names.scala).setType(typeOf(defs.SCALA)).setSymbol(defs.SCALA), - MATCHERROR_N) - .setSymbol(matchErrorModule) - .setType(typeOf(matchErrorModule)), - FAIL_N).setType(typeOf(failMethod)).setSymbol(failMethod), - new Tree[]{gen.mkType(pos, type)}) - .setType(((Type.PolyType) typeOf(failMethod)).result.subst( - typeOf(failMethod).typeParams(), - new Type[]{type})), - new Tree[]{ - make.Literal(pos, unit.toString()).setType(defs.STRING_TYPE), - make.Literal(pos, new Integer(Position.line(pos))).setType(defs.INT_TYPE) - }).setType(type); + make.Apply( + pos, + make.TypeApply( + pos, + make.Select( + pos, + make.Select( + pos, + make.Ident(pos, Names.scala).setType(typeOf(defs.SCALA)).setSymbol(defs.SCALA), + MATCHERROR_N) + .setSymbol(matchErrorModule) + .setType(typeOf(matchErrorModule)), + FAIL_N).setType(typeOf(failMethod)).setSymbol(failMethod), + new Tree[]{gen.mkType(pos, type)}) + .setType(((Type.PolyType) typeOf(failMethod)).result.subst( + typeOf(failMethod).typeParams(), + new Type[]{type})), + new Tree[]{ + make.Literal(pos, unit.toString()).setType(defs.STRING_TYPE), + make.Literal(pos, new Integer(Position.line(pos))).setType(defs.INT_TYPE) + }).setType(type); } } diff --git a/sources/scalac/transformer/matching/PatternTool.java b/sources/scalac/transformer/matching/PatternTool.java index 25a70bf631..b16d2f461d 100644 --- a/sources/scalac/transformer/matching/PatternTool.java +++ b/sources/scalac/transformer/matching/PatternTool.java @@ -60,24 +60,31 @@ abstract class PatternTool { */ Infer infer; - /** the statics of class Boolean - */ + /** the statics of class Boolean + */ Symbol statics; // REMOVE - /** the eqeq symbol - */ - Symbol eqSymInt; // REMOVE - Symbol eqSymBool; // REMOVE - - - // constructor - public PatternTool( Unit unit, Infer infer ) { - this.unit = unit; - this.infer = infer; - this.fresh = unit.global.freshNameCreator; - this.make = unit.global.make; - this.gen = unit.global.treeGen; - this.defs = unit.global.definitions; - } // PatternTool( Unit unit, .... ) + /** the eqeq symbol + */ + Symbol eqSymInt; // REMOVE + Symbol eqSymBool; // REMOVE + + /** the eqeq symbol + */ + Symbol notSym; + + // constructor + public PatternTool( Unit unit, Infer infer ) { + this.unit = unit; + this.infer = infer; + this.fresh = unit.global.freshNameCreator; + this.make = unit.global.make; + this.gen = unit.global.treeGen; + this.defs = unit.global.definitions; + + this.notSym = defs.BOOLEAN_CLASS.lookup/*Term*/( NOT_N ); + assert !(notSym instanceof NoSymbol) : " Boolean.! not found "; + + } // PatternTool( Unit unit, .... ) } // class PatternTool |