diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/compiler/scala/tools/nsc/transform/TailCalls.scala | 132 |
1 files changed, 73 insertions, 59 deletions
diff --git a/src/compiler/scala/tools/nsc/transform/TailCalls.scala b/src/compiler/scala/tools/nsc/transform/TailCalls.scala index 02735d0609..a6add103cf 100644 --- a/src/compiler/scala/tools/nsc/transform/TailCalls.scala +++ b/src/compiler/scala/tools/nsc/transform/TailCalls.scala @@ -1,12 +1,12 @@ /* NSC -- new scala compiler - * Copyright 2005 LAMP/EPFL + * Copyright 2005-2007 LAMP/EPFL * @author Iulian Dragos */ // $Id$ -package scala.tools.nsc.transform; +package scala.tools.nsc.transform -import scala.tools.nsc.symtab.Flags; +import scala.tools.nsc.symtab.Flags /** Perform tail recursive call elimination. * @@ -46,36 +46,42 @@ abstract class TailCalls extends Transform * @version 1.1 * * What it does: - * - * Finds method calls in tail-position and replaces them with jumps. - * 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). 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 - * jump from a method to another one, non-recursive calls in - * tail-position are not optimized. - * - * A method call is self-recursive if it calls the current method on - * the current instance and the method is final (otherwise, it could - * be a call to an overridden method in a subclass). Furthermore, If - * the method has type parameters, the call must contain these - * parameters as type arguments. - * - * This phase has been moved before pattern matching to catch more - * of the common cases of tail recursive functions. This means that - * more cases should be taken into account (like nested function, and - * pattern cases). - * - * 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. - * - * Assumes: Uncurry has been run already, and no multiple parameter - * lists exit. + * <p> + * Finds method calls in tail-position and replaces them with jumps. + * 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). However, they are not that + * many. + * </p> + * <p> + * 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 + * jump from a method to another one, non-recursive calls in + * tail-position are not optimized. + * </p> + * <p> + * A method call is self-recursive if it calls the current method on + * the current instance and the method is final (otherwise, it could + * be a call to an overridden method in a subclass). Furthermore, If + * the method has type parameters, the call must contain these + * parameters as type arguments. + * </p> + * <p> + * This phase has been moved before pattern matching to catch more + * of the common cases of tail recursive functions. This means that + * more cases should be taken into account (like nested function, and + * pattern cases). + * </p> + * <p> + * 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. + * </p> + * <p> + * Assumes: <code>Uncurry</code> has been run already, and no multiple + * parameter lists exit. + * </p> */ class TailCallElimination(unit: CompilationUnit) extends Transformer { @@ -129,10 +135,10 @@ abstract class TailCalls extends Transform /** Rewrite this tree to contain no tail recursive calls */ def transform(tree: Tree, nctx: Context): Tree = { - val oldCtx = ctx; - ctx = nctx; - val t = transform(tree); - this.ctx = oldCtx; + val oldCtx = ctx + ctx = nctx + val t = transform(tree) + this.ctx = oldCtx t } @@ -161,7 +167,7 @@ abstract class TailCalls extends Transform var newRHS = transform(rhs, newCtx); if (newCtx.accessed) { - log("Rewrote def " + newCtx.currentMethod); + log("Rewrote def " + newCtx.currentMethod) newRHS = typed(atPos(tree.pos)( @@ -174,12 +180,14 @@ abstract class TailCalls extends Transform } else { copy.DefDef(tree, mods, name, tparams, vparams, tpt, transform(rhs, newCtx)) } - log("Leaving DefDef: " + name); - t1; + log("Leaving DefDef: " + name) + t1 case EmptyTree => tree - case PackageDef(name, stats) => super.transform(tree) + case PackageDef(name, stats) => + super.transform(tree) + case ClassDef(_, name, _, _, _) => log("Entering class " + name) val res = super.transform(tree) @@ -191,7 +199,8 @@ abstract class TailCalls extends Transform case AliasTypeDef(mods, name, tparams, rhs) => tree // (eliminated by erasure) case LabelDef(name, params, rhs) => super.transform(tree) - case Template(parents, body) => super.transform(tree) + case Template(parents, body) => + super.transform(tree) case Block(stats, expr) => copy.Block(tree, @@ -203,18 +212,20 @@ abstract class TailCalls extends Transform case Sequence(_) | Alternative(_) | Star(_) | Bind(_, _) => - throw new RuntimeException("We should've never gotten inside a pattern"); + throw new RuntimeException("We should've never gotten inside a pattern") case Function(vparams, body) => tree //throw new RuntimeException("Anonymous function should not exist at this point. at: " + unit.position(tree.pos)); - case Assign(lhs, rhs) => super.transform(tree); + case Assign(lhs, rhs) => + super.transform(tree) + case If(cond, thenp, elsep) => - copy.If(tree, cond, transform(thenp), transform(elsep)); + copy.If(tree, cond, transform(thenp), transform(elsep)) case Match(selector, cases) => //super.transform(tree); - copy.Match(tree, transform(selector, mkContext(ctx, false)), transformTrees(cases).asInstanceOf[List[CaseDef]]); + copy.Match(tree, transform(selector, mkContext(ctx, false)), transformTrees(cases).asInstanceOf[List[CaseDef]]) case Return(expr) => super.transform(tree) case Try(block, catches, finalizer) => @@ -232,21 +243,21 @@ abstract class TailCalls extends Transform isRecursiveCall(fun)) rewriteTailCall(fun, transformTrees(vargs, mkContext(ctx, false))) else - copy.Apply(tree, tapply, transformTrees(vargs, mkContext(ctx, false))); + copy.Apply(tree, tapply, transformTrees(vargs, mkContext(ctx, false))) case TypeApply(fun, args) => super.transform(tree) case Apply(fun, args) if fun.symbol == definitions.Boolean_or => - copy.Apply(tree, fun, transformTrees(args)); + copy.Apply(tree, fun, transformTrees(args)) case Apply(fun, args) => if (ctx.currentMethod.isFinal && ctx.tailPos && isRecursiveCall(fun)) - rewriteTailCall(fun, transformTrees(args, mkContext(ctx, false))); + rewriteTailCall(fun, transformTrees(args, mkContext(ctx, false))) else - copy.Apply(tree, fun, transformTrees(args, mkContext(ctx, false))); + copy.Apply(tree, fun, transformTrees(args, mkContext(ctx, false))) case Super(qual, mix) => tree @@ -270,10 +281,10 @@ abstract class TailCalls extends Transform private def rewriteTailCall(fun: Tree, args: List[Tree]): Tree = { log("Rewriting tail recursive method call at: " + - unit.position(fun.pos)); - ctx.accessed = true; + unit.position(fun.pos)) + ctx.accessed = true typed(atPos(fun.pos)( - Apply(Ident(ctx.label), args))); + Apply(Ident(ctx.label), args))) } private def isSameTypes(ts1: List[Symbol], ts2: List[Symbol]): Boolean = { @@ -283,10 +294,13 @@ abstract class TailCalls extends Transform List.forall2(ts1, ts2)(isSameType) } - /** Return true if the fun tree refers to the same method as the one - * saved in ctx. If it is a method call, we check that it is applied to - * "this" - */ + /** Returns <code>true</code> if the fun tree refers to the same method as + * the one saved in <code>ctx</code>. If it is a method call, we check + * that it is applied to <code>this</code>. + * + * @param fun ... + * @return <code>true</code> ... + */ private def isRecursiveCall(fun: Tree): Boolean = if (fun.symbol eq ctx.currentMethod) fun match { @@ -298,8 +312,8 @@ abstract class TailCalls extends Transform case Ident(_) => true case _ => false } - else - false; + else + false } } |