path: root/sources/scalac/transformer/TailCallPhase.java

/*     ____ ____  ____ ____  ______                                     *\
**    / __// __ \/ __// __ \/ ____/    SOcos COmpiles Scala             **
**  __\_ \/ /_/ / /__/ /_/ /\_ \       (c) 2002, LAMP/EPFL              **
** /_____/\____/\___/\____/____/                                        **
\*                                                                      */

// $Id$

package scalac.transformer;

import scalac.Global;
import scalac.Phase;
import scalac.PhaseDescriptor;
import scalac.CompilationUnit;
import scalac.ast.Tree;
import scalac.ast.GenTransformer;
import scalac.symtab.Symbol;
import scalac.symtab.Type;
import scalac.util.Debug;

/**
 * A Tail Call Transformer
 *
 * @author     Erik Stenman
 * @version    1.0
 *
 * 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.
 *
 * 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

    /** Initializes this instance. */
    public TailCallPhase(Global global, PhaseDescriptor descriptor) {
        super(global, descriptor);
    }

   //########################################################################
    // Public Methods

    /** Applies this phase to the given compilation unit. */
    public void apply(CompilationUnit unit) {
        treeTransformer.apply(unit);
    }

   //########################################################################
    // Private Classes

    /** The tree transformer */
    private final GenTransformer treeTransformer = new GenTransformer(global) {


        /** The context of this call */
        private Context ctx = new Context();

        /** 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):
                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):
                        ctx.types = Symbol.type(tparams);
                        type = result;
                    }
                    ctx.label.setInfo(type.cloneType(ctx.method, ctx.label));
                    rhs = transform(rhs);
                    if (ctx.label.isAccessed()) {
                        global.log("Rewriting def " + ctx.method.simpleName());
                        rhs = gen.LabelDef(ctx.label, ctx.method.valueParams(), rhs);
                    }
                    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));
                }
                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);

            case Switch(Tree test, int[] tags, Tree[] bodies, Tree otherwise):
                Type type = tree.type();
                bodies = transform(bodies);
                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 (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):
                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 PackageDef(_, _):
            case LabelDef(_, _, _):
            case Return(_):
                return super.transform(tree);


            case Empty:
            case ValDef(_, _, _, _):
            case Assign(_, _):
            case New(_):
            case Super(_, _):
            case This(_):
            case Select(_, _):
            case Ident(_):
            case Literal(_):
            case TypeTerm():
	    case AbsTypeDef(_, _, _, _):
	    case AliasTypeDef(_, _, _, _):
	    case Import(_, _):
	    case Function(_, _):
                return tree;

            default:
                throw Debug.abort("illegal case", tree);
            }
        }

        /** Transforms the given function call. */
        private Tree transform(Tree tree, Tree fun, Tree[] vargs) {
            if (fun.symbol() != ctx.method)
		return tree;
            switch (fun) {
            case Select(Tree qual, _):
                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);
            }
        }

        /**
         * Returns true if the tree represents the current instance of
         * given class.
         */
        private boolean isReferenceToThis(Tree tree, Symbol clasz) {
            switch (tree) {
            case This(_):
                assert tree.symbol() == clasz: tree +" -- "+ Debug.show(clasz);
                return true;
            default:
                return false;
            }
        }

    };

    //########################################################################
}