Moved tail call phase before transmatch.

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);
             }