From d638dde279142824ddfcca40cb5b9fa7637daff5 Mon Sep 17 00:00:00 2001 From: michelou Date: Wed, 21 Mar 2007 14:27:15 +0000 Subject: synchronized with trunk for 2.4.0-final --- src/compiler/scala/tools/nsc/symtab/Types.scala | 9 +- .../scala/tools/nsc/transform/TailCalls.scala | 134 ++++++++++++--------- .../scala/tools/nsc/typechecker/Typers.scala | 3 + test/files/pos/bug1006.scala | 15 +++ test/files/run/tailcalls.check | 1 + test/files/run/tailcalls.scala | 22 ++++ 6 files changed, 123 insertions(+), 61 deletions(-) create mode 100644 test/files/pos/bug1006.scala diff --git a/src/compiler/scala/tools/nsc/symtab/Types.scala b/src/compiler/scala/tools/nsc/symtab/Types.scala index d368ff37f5..66bdf9dfd1 100644 --- a/src/compiler/scala/tools/nsc/symtab/Types.scala +++ b/src/compiler/scala/tools/nsc/symtab/Types.scala @@ -1042,7 +1042,10 @@ trait Types requires SymbolTable { def transform(cl: Array[Type]): Array[Type] = { val cl1 = new Array[Type](cl.length) var i = 0 - while (i < cl.length) { cl1(i) = transform(cl(i)); i = i + 1 } + while (i < cl.length) { + cl1(i) = transform(cl(i)) + i = i + 1 + } cl1 } @@ -1789,7 +1792,9 @@ trait Types requires SymbolTable { else subst(sym, from.tail, to.tail) tp match { case TypeRef(NoPrefix, sym, _) => - subst(sym, from, to) + val tp1 = subst(sym, from, to) + if (tp1 ne tp) tp1 + else mapOver(tp) case SingleType(NoPrefix, sym) => subst(sym, from, to) case PolyType(tparams, restp) => diff --git a/src/compiler/scala/tools/nsc/transform/TailCalls.scala b/src/compiler/scala/tools/nsc/transform/TailCalls.scala index 1fc2f43e3e..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. + *

+ * 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. + *

*/ 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,19 +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) -// throw new RuntimeException("Lonely TypeApply found -- we can only handle them inside Apply(TypeApply()): " + tree + " at: " + unit); + + case Apply(fun, args) if fun.symbol == definitions.Boolean_or => + 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 @@ -268,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 = { @@ -281,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 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. + * + * @param fun ... + * @return true ... + */ private def isRecursiveCall(fun: Tree): Boolean = if (fun.symbol eq ctx.currentMethod) fun match { @@ -296,8 +312,8 @@ abstract class TailCalls extends Transform case Ident(_) => true case _ => false } - else - false; + else + false } } diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala index ab4cf811fa..3ffb1e10bf 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala @@ -1426,7 +1426,10 @@ trait Typers requires Analyzer { } fun.tpe match { case OverloadedType(pre, alts) => + val undetparams = context.undetparams + context.undetparams = List() val args1 = typedArgs(args, mode) + context.undetparams = undetparams inferMethodAlternative(fun, context.undetparams, args1 map (.tpe.deconst), pt) typedApply(tree, adapt(fun, funMode(mode), WildcardType), args1, mode, pt) case MethodType(formals0, restpe) => diff --git a/test/files/pos/bug1006.scala b/test/files/pos/bug1006.scala new file mode 100644 index 0000000000..91eb2d9b7d --- /dev/null +++ b/test/files/pos/bug1006.scala @@ -0,0 +1,15 @@ +object Test extends Application { + +def test() { + + abstract class A[T] { + def myVal: T + } + + class B[T1](value: T1) extends A[T1] { + def myVal: T1 = value + } + + Console.println(new B[int](23).myVal) +} +} diff --git a/test/files/run/tailcalls.check b/test/files/run/tailcalls.check index 83ea0b3760..49af1207a0 100644 --- a/test/files/run/tailcalls.check +++ b/test/files/run/tailcalls.check @@ -48,3 +48,4 @@ test TailCall.h1 was successful test NonTailCall.f1 0 1 2 was successful test NonTailCall.f2 was successful +test TailCall.b1 was successful diff --git a/test/files/run/tailcalls.scala b/test/files/run/tailcalls.scala index b20fbb20f4..87a14b3f53 100644 --- a/test/files/run/tailcalls.scala +++ b/test/files/run/tailcalls.scala @@ -180,6 +180,9 @@ class TailCall[S](s: S) { aux(x, y, Nil); } + final def b1(x: Int): Boolean = + (x == 1) || b1(x - 1) + def h1(n: Int, v: Int): Int = hP(n, v); private def hP(n: Int, v: Int): Int = if (n == 0) v else hP(n - 1, v - 1); @@ -226,6 +229,23 @@ object Test { Console.println; } + def check_success_b(name: String, closure: => Boolean, expected: Boolean): Unit = { + Console.print("test " + name); + try { + val actual: Boolean = closure; + if (actual == expected) { + Console.print(" was successful"); + } else { + Console.print(" failed: expected "+ expected +", found "+ actual); + } + } catch { + case exception: Throwable => { + Console.print(" raised exception " + exception); + } + } + Console.println; + } + def check_overflow(name: String, closure: => Int): Unit = { Console.print("test " + name); try { @@ -323,6 +343,8 @@ object Test { val NonTailCall = new NonTailCall; check_success("NonTailCall.f1", NonTailCall.f1(2), 0) check_overflow("NonTailCall.f2", NonTailCall.f2(max)) + + check_success_b("TailCall.b1", TailCall.b1(max), true); } } -- cgit v1.2.3