TailRec phase and tests for it.

Ported tailcall phase from scalac with such changes:
  - all transformation is done in the phase itself
     (previously half of the work was done in backend)
  - it is now able to run before uncurry
  - it is now a treeTransform
  - renamed to tailrec to make it more obvious that
     this phase transforms only recursive calls.

For now this is a single phase which speculatively
transforms DefDefs.
Speculation can be potentially removed by
splitting into 2 phases:
  one detecting which methods should be transformed
  second performing transformation.

But, as transformation requires as same amount of work
as detection, I believe it will be simpler to maintain
it as a single phase.

Conflicts:
	tests/pos/typers.scala

12 files changed, 233 insertions, 0 deletions

diff --git a/tests/neg/tailcall/t1672b.check b/tests/neg/tailcall/t1672b.check
new file mode 100644
index 000000000..60ccf7717
--- /dev/null
+++ b/tests/neg/tailcall/t1672b.check
@@ -0,0 +1,16 @@
+t1672b.scala:3: error: could not optimize @tailrec annotated method bar: it contains a recursive call not in tail position
+  def bar : Nothing = {
+      ^
+t1672b.scala:14: error: could not optimize @tailrec annotated method baz: it contains a recursive call not in tail position
+  def baz : Nothing = {
+      ^
+t1672b.scala:29: error: could not optimize @tailrec annotated method boz: it contains a recursive call not in tail position
+      case _: Throwable => boz; ???
+                                ^
+t1672b.scala:34: error: could not optimize @tailrec annotated method bez: it contains a recursive call not in tail position
+  def bez : Nothing = {
+      ^
+t1672b.scala:46: error: could not optimize @tailrec annotated method bar: it contains a recursive call not in tail position
+    else 1 + (try {
+           ^
+5 errors found
diff --git a/tests/neg/tailcall/t1672b.scala b/tests/neg/tailcall/t1672b.scala
new file mode 100644
index 000000000..f05d05c34
--- /dev/null
+++ b/tests/neg/tailcall/t1672b.scala
@@ -0,0 +1,52 @@
+object Test1772B {
+  @annotation.tailrec
+  def bar : Nothing = {
+    try {
+      throw new RuntimeException
+    } catch {
+      case _: Throwable => bar
+    } finally {
+      bar
+    }
+  }
+
+  @annotation.tailrec
+  def baz : Nothing = {
+    try {
+      throw new RuntimeException
+    } catch {
+      case _: Throwable => baz
+    } finally {
+      ???
+    }
+  }
+
+  @annotation.tailrec
+  def boz : Nothing = {
+    try {
+      throw new RuntimeException
+    } catch {
+      case _: Throwable => boz; ???
+    }
+  }
+
+  @annotation.tailrec
+  def bez : Nothing = {
+    try {
+      bez
+    } finally {
+      ???
+    }
+  }
+
+  // the `liftedTree` local method will prevent a tail call here.
+  @annotation.tailrec
+  def bar(i : Int) : Int = {
+    if (i == 0) 0
+    else 1 + (try {
+      throw new RuntimeException
+    } catch {
+      case _: Throwable => bar(i - 1)
+    })
+  }
+}
diff --git a/tests/neg/tailcall/t3275.check b/tests/neg/tailcall/t3275.check
new file mode 100644
index 000000000..117c79232
--- /dev/null
+++ b/tests/neg/tailcall/t3275.check
@@ -0,0 +1,4 @@
+t3275.scala:2: error: @tailrec annotated method contains no recursive calls
+  @annotation.tailrec def foo() = 5
+                          ^
+one error found
diff --git a/tests/neg/tailcall/t3275.scala b/tests/neg/tailcall/t3275.scala
new file mode 100644
index 000000000..18e38a1a9
--- /dev/null
+++ b/tests/neg/tailcall/t3275.scala
@@ -0,0 +1,3 @@
+object Test {
+  @annotation.tailrec def foo() = 5
+}
diff --git a/tests/neg/tailcall/t6574.check b/tests/neg/tailcall/t6574.check
new file mode 100644
index 000000000..c67b4ed80
--- /dev/null
+++ b/tests/neg/tailcall/t6574.check
@@ -0,0 +1,7 @@
+t6574.scala:4: error: could not optimize @tailrec annotated method notTailPos$extension: it contains a recursive call not in tail position
+    println("tail")
+    ^
+t6574.scala:8: error: could not optimize @tailrec annotated method differentTypeArgs$extension: it is called recursively with different type arguments
+    {(); new Bad[String, Unit](0)}.differentTypeArgs
+                                   ^
+two errors found
diff --git a/tests/neg/tailcall/t6574.scala b/tests/neg/tailcall/t6574.scala
new file mode 100644
index 000000000..59f3108ad
--- /dev/null
+++ b/tests/neg/tailcall/t6574.scala
@@ -0,0 +1,10 @@
+class Bad[X, Y](val v: Int) extends AnyVal {
+  @annotation.tailrec final def notTailPos[Z](a: Int)(b: String): Unit = {
+    this.notTailPos[Z](a)(b)
+    println("tail")
+  }
+
+  @annotation.tailrec final def differentTypeArgs : Unit = { 
+    {(); new Bad[String, Unit](0)}.differentTypeArgs
+  }
+}
diff --git a/tests/neg/tailcall/tailrec-2.check b/tests/neg/tailcall/tailrec-2.check
new file mode 100644
index 000000000..1daad6922
--- /dev/null
+++ b/tests/neg/tailcall/tailrec-2.check
@@ -0,0 +1,7 @@
+tailrec-2.scala:8: error: could not optimize @tailrec annotated method f: it contains a recursive call targeting a supertype
+  @annotation.tailrec final def f[B >: A](mem: List[B]): List[B] = (null: Super[A]).f(mem)
+                                                                                    ^
+tailrec-2.scala:9: error: @tailrec annotated method contains no recursive calls
+  @annotation.tailrec final def f1[B >: A](mem: List[B]): List[B] = this.g(mem)
+                                ^
+two errors found
diff --git a/tests/neg/tailcall/tailrec-2.scala b/tests/neg/tailcall/tailrec-2.scala
new file mode 100644
index 000000000..d6b8b1355
--- /dev/null
+++ b/tests/neg/tailcall/tailrec-2.scala
@@ -0,0 +1,29 @@
+sealed abstract class Super[+A] {
+  def f[B >: A](mem: List[B]) : List[B]
+  def g(mem: List[_]) = ???
+}
+// This one should fail, target is a supertype
+class Bop1[+A](val element: A) extends Super[A] {
+
+  @annotation.tailrec final def f[B >: A](mem: List[B]): List[B] = (null: Super[A]).f(mem)
+  @annotation.tailrec final def f1[B >: A](mem: List[B]): List[B] = this.g(mem)
+}
+// These succeed
+class Bop2[+A](val element: A) extends Super[A] {
+  @annotation.tailrec final def f[B >: A](mem: List[B]): List[B] = (null: Bop2[A]).f(mem)
+}
+object Bop3 extends Super[Nothing] {
+  @annotation.tailrec final def f[B](mem: List[B]): List[B] = (null: Bop3.type).f(mem)
+}
+class Bop4[+A](val element: A) extends Super[A] {
+  @annotation.tailrec final def f[B >: A](mem: List[B]): List[B] = Other.f[A].f(mem)
+}
+
+object Other {
+  def f[T] : Bop4[T] = sys.error("")
+}
+
+object Bop {
+  def m1[A] : Super[A] = sys.error("")
+  def m2[A] : Bop2[A] = sys.error("")
+}
diff --git a/tests/neg/tailcall/tailrec-3.check b/tests/neg/tailcall/tailrec-3.check
new file mode 100644
index 000000000..a3542fb56
--- /dev/null
+++ b/tests/neg/tailcall/tailrec-3.check
@@ -0,0 +1,10 @@
+tailrec-3.scala:4: error: could not optimize @tailrec annotated method quux: it contains a recursive call not in tail position
+  @tailrec private def quux(xs: List[String]): List[String] = quux(quux(xs))
+                                                                       ^
+tailrec-3.scala:6: error: could not optimize @tailrec annotated method quux2: it contains a recursive call not in tail position
+    case x1 :: x2 :: rest => quux2(x1 :: quux2(rest))
+                                              ^
+tailrec-3.scala:10: error: could not optimize @tailrec annotated method quux3: it contains a recursive call not in tail position
+    case x :: xs if quux3(List("abc"))  => quux3(xs)
+                         ^
+three errors found
diff --git a/tests/neg/tailcall/tailrec-3.scala b/tests/neg/tailcall/tailrec-3.scala
new file mode 100644
index 000000000..20361658e
--- /dev/null
+++ b/tests/neg/tailcall/tailrec-3.scala
@@ -0,0 +1,14 @@
+import annotation.tailrec
+
+object Test {
+  @tailrec private def quux(xs: List[String]): List[String] = quux(quux(xs))
+  @tailrec private def quux2(xs: List[String]): List[String] = xs match {
+    case x1 :: x2 :: rest => quux2(x1 :: quux2(rest))
+    case _                => Nil
+  }
+  @tailrec private def quux3(xs: List[String]): Boolean = xs match {
+    case x :: xs if quux3(List("abc"))  => quux3(xs)
+    case _                              => false
+  }
+}
+
diff --git a/tests/neg/tailcall/tailrec.check b/tests/neg/tailcall/tailrec.check
new file mode 100644
index 000000000..946d3421e
--- /dev/null
+++ b/tests/neg/tailcall/tailrec.check
@@ -0,0 +1,16 @@
+tailrec.scala:45: error: could not optimize @tailrec annotated method facfail: it contains a recursive call not in tail position
+    else n * facfail(n - 1)
+           ^
+tailrec.scala:50: error: could not optimize @tailrec annotated method fail1: it is neither private nor final so can be overridden
+  @tailrec def fail1(x: Int): Int = fail1(x)
+               ^
+tailrec.scala:53: error: could not optimize @tailrec annotated method fail2: 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 fail3: 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 fail4: 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/tests/neg/tailcall/tailrec.scala b/tests/neg/tailcall/tailrec.scala
new file mode 100644
index 000000000..83a0c1a9e
--- /dev/null
+++ b/tests/neg/tailcall/tailrec.scala
@@ -0,0 +1,65 @@
+import scala.annotation.tailrec
+
+// putting @tailrec through the paces
+object Winners {
+  @tailrec
+  def facsucc(n: Int, acc: Int): Int =
+    if (n == 0) acc
+    else facsucc(n - 1, n * acc)
+
+  @tailrec def loopsucc1(x: Int): Int = loopsucc1(x - 1)
+  @tailrec def loopsucc2[T](x: Int): Int = loopsucc2[T](x - 1)
+
+  def ding(): Unit = {
+    object dong {
+      @tailrec def loopsucc3(x: Int): Int = loopsucc3(x)
+    }
+    ()
+  }
+
+  def inner(q: Int) = {
+    @tailrec
+    def loopsucc4(x: Int): Int = loopsucc4(x + 1)
+
+    loopsucc4(q)
+  }
+
+  object innerBob {
+    @tailrec def loopsucc5(x: Int): Int = loopsucc5(x)
+  }
+}
+
+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 final def fail2[T](xs: List[T]): List[T] = xs match {
+    case Nil      => Nil
+    case x :: xs  => x :: fail2[T](xs)
+  }
+
+  // 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)
+  }
+}