diff options
author | Iulian Dragos <jaguarul@gmail.com> | 2005-04-26 14:38:45 +0000 |
---|---|---|
committer | Iulian Dragos <jaguarul@gmail.com> | 2005-04-26 14:38:45 +0000 |
commit | 8e8f1558934ffe8600625cffd730d0126a4ede7c (patch) | |
tree | eb26696eb3f002c05a6b704a6d32d669fd719b96 /sources/scalac/transformer/TailCallPhase.java | |
parent | b630d0e2d9df946ea30eb67223e29084d25ddf8e (diff) | |
download | scala-8e8f1558934ffe8600625cffd730d0126a4ede7c.tar.gz scala-8e8f1558934ffe8600625cffd730d0126a4ede7c.tar.bz2 scala-8e8f1558934ffe8600625cffd730d0126a4ede7c.zip |
Moved tail call phase before transmatch.
Diffstat (limited to 'sources/scalac/transformer/TailCallPhase.java')
-rw-r--r-- | sources/scalac/transformer/TailCallPhase.java | 170 |
1 files changed, 141 insertions, 29 deletions
diff --git a/sources/scalac/transformer/TailCallPhase.java b/sources/scalac/transformer/TailCallPhase.java index 2487a7d436..4798e22c1a 100644 --- a/sources/scalac/transformer/TailCallPhase.java +++ b/sources/scalac/transformer/TailCallPhase.java @@ -30,7 +30,8 @@ import scalac.util.Debug; * A call is in a tail-position if it is the last instruction to be * executed in the body of a method. This is done by recursing over * the trees that may contain calls in tail-position (trees that can't - * contain such calls are not transformed). + * contain such calls are not transformed). However, they are not that + * many. * * Self-recursive calls in tail-position are replaced by jumps to a * label at the beginning of the method. As the JVM provides no way to @@ -43,12 +44,48 @@ import scalac.util.Debug; * the method has type parameters, the call must contain these * parameters as type arguments. * + * Nested functions can be tail recursive (if this phase runs before + * lambda lift) and they are transformed as well. + * * If a method contains self-recursive calls, a label is added to at * the beginning of its body and the calls are replaced by jumps to * that label. */ public class TailCallPhase extends Phase { + private static class Context { + /** The current method */ + public Symbol method = Symbol.NONE; + + /** The current tail-call label */ + public Symbol label = Symbol.NONE; + + /** The expected type arguments of self-recursive calls */ + public Type[] types; + + /** Tells whether we are in a tail position. */ + public boolean tailPosition; + + public Context() { + this.tailPosition = false; + } + + /** + * The Context of this transformation. It contains the current enclosing method, + * the label and the type parameters of the enclosing method, together with a + * flag which says whether our position in the tree allows tail calls. This is + * modified only in <code>Block</code>, where stats cannot possibly contain tail + * calls, but the value can. + */ + public Context(Symbol method, Symbol label, Type[] types, boolean tailPosition) { + this.method = method; + this.label = label; + this.types = types; + this.tailPosition = tailPosition; + } + } + + //######################################################################## // Public Constructors @@ -71,51 +108,78 @@ public class TailCallPhase extends Phase { /** The tree transformer */ private final GenTransformer treeTransformer = new GenTransformer(global) { - /** The current method */ - private Symbol method; - /** The current tail-call label */ - private Symbol label; + /** The context of this call */ + private Context ctx = new Context(); - /** The expected type arguments of self-recursive calls */ - private Type[] types; + /** Transform the given tree, which is (or not) in tail position */ + public Tree transform(Tree tree, boolean tailPos) { + boolean oldTP = ctx.tailPosition; + ctx.tailPosition = tailPos; + tree = transform(tree); + ctx.tailPosition = oldTP; + return tree; + } + + public Tree[] transform(Tree[] trees, boolean tailPos) { + boolean oldTP = ctx.tailPosition; + ctx.tailPosition = tailPos; + trees = transform(trees); + ctx.tailPosition = oldTP; + return trees; + } /** Transforms the given tree. */ public Tree transform(Tree tree) { switch (tree) { case DefDef(_, _, _, _, _, Tree rhs): - assert method == null: Debug.show(method) + " -- " + tree; - method = tree.symbol(); - if (method.isMethodFinal()) { - label = method.newLabel(method.pos, method.name); - types = Type.EMPTY_ARRAY; - Type type = method.type(); + Context oldCtx = ctx; + + ctx = new Context(); + + //assert method == null: Debug.show(method) + " -- " + tree; + ctx.method = tree.symbol(); + ctx.tailPosition = true; + + if (ctx.method.isMethodFinal() || ctx.method.owner().isMethod()) { + ctx.label = ctx.method.newLabel(ctx.method.pos, ctx.method.name); + ctx.types = Type.EMPTY_ARRAY; + Type type = ctx.method.type(); switch (type) { case PolyType(Symbol[] tparams, Type result): - types = Symbol.type(tparams); + ctx.types = Symbol.type(tparams); type = result; } - label.setInfo(type.cloneType(method, label)); + ctx.label.setInfo(type.cloneType(ctx.method, ctx.label)); rhs = transform(rhs); - if (label.isAccessed()) { - rhs = gen.LabelDef(label, method.valueParams(), rhs); - tree = gen.DefDef(method, rhs); + if (ctx.label.isAccessed()) { + global.log("Rewriting def " + ctx.method.simpleName()); + rhs = gen.LabelDef(ctx.label, ctx.method.valueParams(), rhs); } - types = null; - label = null; + tree = gen.DefDef(ctx.method, rhs); + } else { + assert !ctx.method.isMethodFinal() + : "Final method: " + ctx.method.simpleName(); + // non-final method + ctx.tailPosition = false; + tree = gen.DefDef(tree.symbol(), transform(rhs)); } - method = null; + ctx = oldCtx; return tree; case Block(Tree[] stats, Tree value): + boolean oldPosition = ctx.tailPosition; + ctx.tailPosition = false; stats = transform(stats); + ctx.tailPosition = oldPosition; return gen.Block(tree.pos, stats, transform(value)); + case If(Tree cond, Tree thenp, Tree elsep): Type type = tree.type(); thenp = transform(thenp); elsep = transform(elsep); - return gen.If(tree.pos, cond, thenp, elsep, type); + return gen.If(tree.pos, cond, thenp, elsep); case Switch(Tree test, int[] tags, Tree[] bodies, Tree otherwise): Type type = tree.type(); @@ -123,18 +187,52 @@ public class TailCallPhase extends Phase { otherwise = transform(otherwise); return gen.Switch(tree.pos, test, tags, bodies,otherwise,type); + // handle pattern matches explicitly + case Apply(Select(_, scalac.util.Names._match), Tree[] args): + Tree newTree = global.make.Apply(tree.pos, ((Tree.Apply)tree).fun, transform(args)); + newTree.setType(tree.getType()); + return newTree; + case Apply(TypeApply(Tree fun, Tree[] targs), Tree[] vargs): - if (!Type.isSameAs(Tree.typeOf(targs), types)) return tree; - return transform(tree, fun, vargs); + if (ctx.method != Symbol.NONE && ctx.tailPosition) { + assert targs != null : "Null type arguments " + tree; + assert ctx.types != null : "Null types " + tree; + + if (!Type.isSameAs(Tree.typeOf(targs), ctx.types) | + !ctx.tailPosition) + return tree; + return transform(tree, fun, transform(vargs, false)); + } else + return tree; + case Apply(Tree fun, Tree[] vargs): - return transform(tree, fun, vargs); + if (ctx.tailPosition) + return transform(tree, fun, transform(vargs, false)); + else + return gen.mkApply_V(fun, transform(vargs, false)); + + case Visitor(Tree.CaseDef[] cases): + Tree newTree = global.make.Visitor(tree.pos, super.transform(cases)); + newTree.setType(tree.getType()); + return newTree; + + case CaseDef(Tree pattern, Tree guard, Tree body): + return gen.CaseDef(pattern, guard, transform(body)); + + case Typed(Tree expr, Tree type): + return gen.Typed(transform(expr), type); + + case ClassDef(_, _, _, _, _, Tree.Template impl): + Symbol impl_symbol = getSymbolFor(impl); + Tree[] body = transform(impl.body); + return gen.ClassDef(getSymbolFor(tree), impl.parents, impl_symbol, body); - case ClassDef(_, _, _, _, _, _): case PackageDef(_, _): case LabelDef(_, _, _): case Return(_): return super.transform(tree); + case Empty: case ValDef(_, _, _, _): case Assign(_, _): @@ -145,6 +243,10 @@ public class TailCallPhase extends Phase { case Ident(_): case Literal(_): case TypeTerm(): + case AbsTypeDef(_, _, _, _): + case AliasTypeDef(_, _, _, _): + case Import(_, _): + case Function(_, _): return tree; default: @@ -154,11 +256,21 @@ public class TailCallPhase extends Phase { /** Transforms the given function call. */ private Tree transform(Tree tree, Tree fun, Tree[] vargs) { - if (fun.symbol() != method) return tree; + if (fun.symbol() != ctx.method) + return tree; switch (fun) { case Select(Tree qual, _): - if (!isReferenceToThis(qual, method.owner())) return tree; - return gen.Apply(tree.pos, gen.Ident(qual.pos, label), vargs); + if (!isReferenceToThis(qual, ctx.method.owner())) + return tree; + global.log("Applying tail call recursion elimination for " + + ctx.method.enclClass().simpleName() + "." + ctx.method.simpleName()); + return gen.Apply(tree.pos, gen.Ident(qual.pos, ctx.label), vargs); + + case Ident(_): + global.log("Applying tail call recursion elimination for function " + + ctx.method.enclClass().simpleName() + "." + ctx.method.simpleName()); + return gen.Apply(tree.pos, gen.Ident(fun.pos, ctx.label), vargs); + default: throw Debug.abort("illegal case", fun); } |