From 11398dd393fe3eff544bfbafafb584d3acd66e05 Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Thu, 15 Apr 2010 22:18:15 +0000 Subject: Improved @tailrec error messages to specify the... Improved @tailrec error messages to specify the reason. In the process fixed old bug involving tail call transformation. Closes #3275, #2018. Review by dragos. --- .../scala/tools/nsc/transform/TailCalls.scala | 130 +++++++++------------ test/files/neg/tailrec.check | 18 ++- test/files/neg/tailrec.scala | 44 ++++--- test/files/pos/bug2018.scala | 15 +++ 4 files changed, 112 insertions(+), 95 deletions(-) create mode 100644 test/files/pos/bug2018.scala diff --git a/src/compiler/scala/tools/nsc/transform/TailCalls.scala b/src/compiler/scala/tools/nsc/transform/TailCalls.scala index effc75486d..0ec90f142b 100644 --- a/src/compiler/scala/tools/nsc/transform/TailCalls.scala +++ b/src/compiler/scala/tools/nsc/transform/TailCalls.scala @@ -39,9 +39,6 @@ abstract class TailCalls extends Transform } } - /** The @tailrec annotation indicates TCO is mandatory */ - private def tailrecRequired(defdef: DefDef) = defdef.symbol hasAnnotation TailrecClass - /** * A Tail Call Transformer * @@ -105,6 +102,9 @@ abstract class TailCalls extends Transform /** Tells whether we are in a (possible) tail position */ var tailPos = false + /** The reason this method could not be optimized. */ + var tailrecFailReason = "it contains a recursive call not in tail position" + /** Is the label accessed? */ var accessed = false @@ -138,7 +138,8 @@ abstract class TailCalls extends Transform t } - private var ctx: Context = new Context() + private var ctx: Context = new Context() + private def enclosingType = ctx.currentMethod.enclClass.typeOfThis /** Rewrite this tree to contain no tail recursive calls */ def transform(tree: Tree, nctx: Context): Tree = { @@ -150,11 +151,50 @@ abstract class TailCalls extends Transform } override def transform(tree: Tree): Tree = { + /** A possibly polymorphic apply to be considered for tail call transformation. + */ + def rewriteApply(target: Tree, fun: Tree, targs: List[Tree], args: List[Tree]) = { + def isRecursiveCall = ctx.currentMethod eq fun.symbol + def isMandatory = ctx.currentMethod hasAnnotation TailrecClass + def isEligible = ctx.currentMethod.isEffectivelyFinal + def transformArgs = transformTrees(args, mkContext(ctx, false)) + def matchesTypeArgs = ctx.tparams sameElements (targs map (_.tpe.typeSymbol)) + def defaultTree = treeCopy.Apply(tree, target, transformArgs) + + def sameTypeOfThis(receiver: Tree) = + receiver.tpe.widen =:= enclosingType.widen + + /** Records failure reason in Context for reporting. + */ + def cannotRewrite(reason: String) = { + if (isMandatory) + ctx.tailrecFailReason = reason + + defaultTree + } + def rewriteTailCall(receiver: Tree, otherArgs: List[Tree]): Tree = { + log("Rewriting tail recursive method call at: " + fun.pos) + + ctx.accessed = true + typed { atPos(fun.pos)(Apply(Ident(ctx.label), receiver :: otherArgs)) } + } + + if (!isRecursiveCall) defaultTree + else if (!isEligible) cannotRewrite("it is neither private nor final so can be overridden") + else if (!ctx.tailPos) cannotRewrite("it contains a recursive call not in tail position") + else if (!matchesTypeArgs) cannotRewrite("it is called recursively with different type arguments") + else fun match { + case Select(_, _) if forMSIL => cannotRewrite("it cannot be optimized on MSIL") + case Select(qual, _) if !sameTypeOfThis(qual) => cannotRewrite("it changes type of 'this' on a polymorphic recursive call") + case Select(qual, _) => rewriteTailCall(qual, transformArgs) + case _ => rewriteTailCall(This(currentClass), transformArgs) + } + } + tree match { case dd @ DefDef(mods, name, tparams, vparams, tpt, rhs) => log("Entering DefDef: " + name) - var isTransformed = false val newCtx = mkContext(ctx) newCtx.currentMethod = tree.symbol newCtx.makeLabel() @@ -162,7 +202,8 @@ abstract class TailCalls extends Transform newCtx.label.setInfo(MethodType(currentClassParam :: tree.symbol.tpe.params, tree.symbol.tpe.finalResultType)) newCtx.tailPos = true - val isEligible = newCtx.currentMethod.isEffectivelyFinal || (newCtx.currentMethod.enclClass hasFlag Flags.MODULE) + val isEligible = newCtx.currentMethod.isEffectivelyFinal + val isMandatory = dd.symbol hasAnnotation TailrecClass // @tailrec annotation indicates mandatory transformation if (isEligible) { newCtx.tparams = Nil @@ -182,7 +223,6 @@ abstract class TailCalls extends Transform transformed match { case newRHS if isEligible && newCtx.accessed => log("Rewrote def " + newCtx.currentMethod) - isTransformed = true val newThis = newCtx.currentMethod . newValue (tree.pos, nme.THIS) . setInfo (currentClass.typeOfThis) @@ -192,13 +232,14 @@ abstract class TailCalls extends Transform List(ValDef(newThis, This(currentClass))), LabelDef(newCtx.label, newThis :: (vparams.flatten map (_.symbol)), newRHS) ))) - case rhs => rhs + case rhs => + if (isMandatory) + unit.error(dd.pos, "could not optimize @tailrec annotated method: " + newCtx.tailrecFailReason) + + rhs } }) - if (!forMSIL && !isTransformed && tailrecRequired(dd)) - unit.error(dd.pos, "could not optimize @tailrec annotated method") - log("Leaving DefDef: " + name) t1 @@ -255,50 +296,16 @@ abstract class TailCalls extends Transform case Typed(expr, tpt) => super.transform(tree) case Apply(tapply @ TypeApply(fun, targs), vargs) => - lazy val defaultTree = treeCopy.Apply(tree, tapply, transformTrees(vargs, mkContext(ctx, false))) - if ( ctx.currentMethod.isEffectivelyFinal && - ctx.tailPos && - isSameTypes(ctx.tparams, targs map (_.tpe.typeSymbol)) && - isRecursiveCall(fun)) { - fun match { - case Select(receiver, _) => - val recTpe = receiver.tpe.widen - val enclTpe = ctx.currentMethod.enclClass.typeOfThis - // make sure the type of 'this' doesn't change through this polymorphic recursive call - if (!forMSIL && - (receiver.tpe.typeParams.isEmpty || - (receiver.tpe.widen == ctx.currentMethod.enclClass.typeOfThis))) - rewriteTailCall(fun, receiver :: transformTrees(vargs, mkContext(ctx, false))) - else - defaultTree - case _ => rewriteTailCall(fun, This(currentClass) :: transformTrees(vargs, mkContext(ctx, false))) - } - } else - defaultTree + rewriteApply(tapply, fun, targs, vargs) case TypeApply(fun, args) => super.transform(tree) - case Apply(fun, args) if (fun.symbol == definitions.Boolean_or || - fun.symbol == definitions.Boolean_and) => - treeCopy.Apply(tree, fun, transformTrees(args)) - case Apply(fun, args) => - lazy val defaultTree = treeCopy.Apply(tree, fun, transformTrees(args, mkContext(ctx, false))) - if (ctx.currentMethod.isEffectivelyFinal && - ctx.tailPos && - isRecursiveCall(fun)) { - fun match { - case Select(receiver, _) => - if (!forMSIL) - rewriteTailCall(fun, receiver :: transformTrees(args, mkContext(ctx, false))) - else - defaultTree - case _ => rewriteTailCall(fun, This(currentClass) :: transformTrees(args, mkContext(ctx, false))) - } - } else - defaultTree - + if (fun.symbol == Boolean_or || fun.symbol == Boolean_and) + treeCopy.Apply(tree, fun, transformTrees(args)) + else + rewriteApply(fun, fun, Nil, args) case Super(qual, mix) => tree @@ -319,28 +326,5 @@ abstract class TailCalls extends Transform def transformTrees(trees: List[Tree], nctx: Context): List[Tree] = trees map ((tree) => transform(tree, nctx)) - - private def rewriteTailCall(fun: Tree, args: List[Tree]): Tree = { - log("Rewriting tail recursive method call at: " + - (fun.pos)) - ctx.accessed = true - //println("fun: " + fun + " args: " + args) - val t = atPos(fun.pos)(Apply(Ident(ctx.label), args)) - // println("TAIL: "+t) - typed(t) - } - - private def isSameTypes(ts1: List[Symbol], ts2: List[Symbol]) = ts1 sameElements ts2 - - /** Returns true if the fun tree refers to the same method as - * the one saved in ctx. - * - * @param fun the expression that is applied - * @return true if the tree symbol refers to the innermost - * enclosing method - */ - private def isRecursiveCall(fun: Tree): Boolean = - (fun.symbol eq ctx.currentMethod) } - } diff --git a/test/files/neg/tailrec.check b/test/files/neg/tailrec.check index 22d70e82a0..27d99f632e 100644 --- a/test/files/neg/tailrec.check +++ b/test/files/neg/tailrec.check @@ -1,10 +1,16 @@ -tailrec.scala:6: error: could not optimize @tailrec annotated method +tailrec.scala:43: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position def facfail(n: Int): Int = ^ -tailrec.scala:42: error: could not optimize @tailrec annotated method +tailrec.scala:50: error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden @tailrec def fail1(x: Int): Int = fail1(x) ^ -tailrec.scala:45: error: could not optimize @tailrec annotated method - @tailrec def fail2[T](xs: List[T]): List[T] = xs match { - ^ -three errors found +tailrec.scala:53: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position + @tailrec final def fail2[T](xs: List[T]): List[T] = xs match { + ^ +tailrec.scala:59: error: could not optimize @tailrec annotated method: it is called recursively with different type arguments + @tailrec final def fail3[T](x: Int): Int = fail3(x - 1) + ^ +tailrec.scala:63: error: could not optimize @tailrec annotated method: it changes type of 'this' on a polymorphic recursive call + @tailrec final def fail4[U](other: Tom[U], x: Int): Int = other.fail4[U](other, x - 1) + ^ +5 errors found diff --git a/test/files/neg/tailrec.scala b/test/files/neg/tailrec.scala index 4c45672f93..a77f439cfe 100644 --- a/test/files/neg/tailrec.scala +++ b/test/files/neg/tailrec.scala @@ -1,53 +1,65 @@ import scala.annotation.tailrec // putting @tailrec through the paces -object Main { - @tailrec - def facfail(n: Int): Int = - if (n == 0) 1 - else n * facfail(n - 1) - +object Winners { @tailrec def facsucc(n: Int, acc: Int): Int = if (n == 0) acc else facsucc(n - 1, n * acc) - @tailrec def loopy1(x: Int): Int = loopy1(x - 1) + @tailrec def loopsucc1(x: Int): Int = loopsucc1(x - 1) + @tailrec def loopsucc2[T](x: Int): Int = loopsucc2[T](x - 1) def ding { object dong { - @tailrec def loopy2(x: Int): Int = loopy2(x) + @tailrec def loopsucc3(x: Int): Int = loopsucc3(x) } () } def inner(q: Int) = { @tailrec - def loopy3(x: Int): Int = loopy3(x + 1) + def loopsucc4(x: Int): Int = loopsucc4(x + 1) - loopy3(q) + loopsucc4(q) + } + + object innerBob { + @tailrec def loopsucc5(x: Int): Int = loopsucc5(x) } } -class Bob { - // these should work +class Winners { @tailrec private def succ1(x: Int): Int = succ1(x) @tailrec final def succ2(x: Int): Int = succ2(x) @tailrec final def succ3[T](in: List[T], acc: List[T]): List[T] = in match { case Nil => Nil case x :: xs => succ3(xs, x :: acc) } +} +object Failures { + @tailrec + def facfail(n: Int): Int = + if (n == 0) 1 + else n * facfail(n - 1) +} + +class Failures { // not private, not final @tailrec def fail1(x: Int): Int = fail1(x) // a typical between-chair-and-keyboard error - @tailrec def fail2[T](xs: List[T]): List[T] = xs match { + @tailrec final def fail2[T](xs: List[T]): List[T] = xs match { case Nil => Nil - case x :: xs => x :: fail2(xs) + case x :: xs => x :: fail2[T](xs) } - object innerBob { - @tailrec def succ4(x: Int): Int = succ4(x) + // unsafe + @tailrec final def fail3[T](x: Int): Int = fail3(x - 1) + + // unsafe + class Tom[T](x: Int) { + @tailrec final def fail4[U](other: Tom[U], x: Int): Int = other.fail4[U](other, x - 1) } } diff --git a/test/files/pos/bug2018.scala b/test/files/pos/bug2018.scala new file mode 100644 index 0000000000..1736c394c9 --- /dev/null +++ b/test/files/pos/bug2018.scala @@ -0,0 +1,15 @@ +class A { + val b = new B + + def getChildren = List(new A).iterator + + class B { + private def check = true + + private def getAncestor(p: A): A = { + val c = (p.getChildren.find(_.b.check)) match {case Some(d) => d case None => p} + + if (c == p) p else c.b.getAncestor(c) + } + } +} \ No newline at end of file -- cgit v1.2.3