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

19 files changed, 0 insertions, 352 deletions

diff --git a/tests/untried/neg/t1672b.check b/tests/untried/neg/t1672b.check
deleted file mode 100644
index 60ccf7717..000000000
--- a/tests/untried/neg/t1672b.check
+++ /dev/null
@@ -1,16 +0,0 @@
-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/untried/neg/t1672b.scala b/tests/untried/neg/t1672b.scala
deleted file mode 100644
index 0ccdd0363..000000000
--- a/tests/untried/neg/t1672b.scala
+++ /dev/null
@@ -1,52 +0,0 @@
-object Test {
-  @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/untried/neg/t3275.check b/tests/untried/neg/t3275.check
deleted file mode 100644
index 117c79232..000000000
--- a/tests/untried/neg/t3275.check
+++ /dev/null
@@ -1,4 +0,0 @@
-t3275.scala:2: error: @tailrec annotated method contains no recursive calls
-  @annotation.tailrec def foo() = 5
-                          ^
-one error found
diff --git a/tests/untried/neg/t3275.scala b/tests/untried/neg/t3275.scala
deleted file mode 100644
index 18e38a1a9..000000000
--- a/tests/untried/neg/t3275.scala
+++ /dev/null
@@ -1,3 +0,0 @@
-object Test {
-  @annotation.tailrec def foo() = 5
-}
diff --git a/tests/untried/neg/t6574.check b/tests/untried/neg/t6574.check
deleted file mode 100644
index c67b4ed80..000000000
--- a/tests/untried/neg/t6574.check
+++ /dev/null
@@ -1,7 +0,0 @@
-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/untried/neg/t6574.scala b/tests/untried/neg/t6574.scala
deleted file mode 100644
index 9e1d624e5..000000000
--- a/tests/untried/neg/t6574.scala
+++ /dev/null
@@ -1,10 +0,0 @@
-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/untried/neg/tailrec-2.check b/tests/untried/neg/tailrec-2.check
deleted file mode 100644
index 1daad6922..000000000
--- a/tests/untried/neg/tailrec-2.check
+++ /dev/null
@@ -1,7 +0,0 @@
-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/untried/neg/tailrec-2.scala b/tests/untried/neg/tailrec-2.scala
deleted file mode 100644
index d6b8b1355..000000000
--- a/tests/untried/neg/tailrec-2.scala
+++ /dev/null
@@ -1,29 +0,0 @@
-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/untried/neg/tailrec-3.check b/tests/untried/neg/tailrec-3.check
deleted file mode 100644
index a3542fb56..000000000
--- a/tests/untried/neg/tailrec-3.check
+++ /dev/null
@@ -1,10 +0,0 @@
-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/untried/neg/tailrec-3.scala b/tests/untried/neg/tailrec-3.scala
deleted file mode 100644
index 20361658e..000000000
--- a/tests/untried/neg/tailrec-3.scala
+++ /dev/null
@@ -1,14 +0,0 @@
-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/untried/neg/tailrec.check b/tests/untried/neg/tailrec.check
deleted file mode 100644
index 946d3421e..000000000
--- a/tests/untried/neg/tailrec.check
+++ /dev/null
@@ -1,16 +0,0 @@
-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/untried/neg/tailrec.scala b/tests/untried/neg/tailrec.scala
deleted file mode 100644
index 83a0c1a9e..000000000
--- a/tests/untried/neg/tailrec.scala
+++ /dev/null
@@ -1,65 +0,0 @@
-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)
-  }
-}
diff --git a/tests/untried/pos/t1672.scala b/tests/untried/pos/t1672.scala
deleted file mode 100644
index 5ee6bb175..000000000
--- a/tests/untried/pos/t1672.scala
+++ /dev/null
@@ -1,10 +0,0 @@
-object Test {
-  @annotation.tailrec
-  def bar : Nothing = {
-    try {
-      throw new RuntimeException
-    } catch {
-      case _: Throwable => bar
-    }
-  }
-}
diff --git a/tests/untried/pos/t4649.flags b/tests/untried/pos/t4649.flags
deleted file mode 100644
index e8fb65d50..000000000
--- a/tests/untried/pos/t4649.flags
+++ /dev/null
@@ -1 +0,0 @@
--Xfatal-warnings
\ No newline at end of file
diff --git a/tests/untried/pos/t4649.scala b/tests/untried/pos/t4649.scala
deleted file mode 100644
index 0d6caa8d7..000000000
--- a/tests/untried/pos/t4649.scala
+++ /dev/null
@@ -1,6 +0,0 @@
-object Test {
-  // @annotation.tailrec
-  def lazyFilter[E](s: Stream[E], p: E => Boolean): Stream[E] = s match {
-    case h #:: t => if (p(h)) h #:: lazyFilter(t, p) else lazyFilter(t, p)
-  }
-}
diff --git a/tests/untried/pos/t6479.scala b/tests/untried/pos/t6479.scala
deleted file mode 100644
index e4a4ff601..000000000
--- a/tests/untried/pos/t6479.scala
+++ /dev/null
@@ -1,56 +0,0 @@
-object TailrecAfterTryCatch {
-
-  @annotation.tailrec
-  final def good1(): Unit = {
-    1 match {
-      case 2 => {
-        try {
-        //  return
-        } catch {
-          case e: ClassNotFoundException =>
-        }
-        good1()
-      }
-    }
-  }
-
-  @annotation.tailrec
-  final def good2(): Unit = {
-    //1 match {
-    //  case 2 => {
-        try {
-          return
-        } catch {
-          case e: ClassNotFoundException =>
-        }
-        good2()
-    //  }
-    //}
-  }
-
-  @annotation.tailrec
-  final def good3(): Unit = {
-    val 1 = 2
-    try {
-      return
-    } catch {
-      case e: ClassNotFoundException =>
-    }
-    good3()
-  }
-
-  @annotation.tailrec
-  final def bad(): Unit = {
-    1 match {
-      case 2 => {
-        try {
-          return
-        } catch {
-          case e: ClassNotFoundException =>
-        }
-        bad()
-      }
-    }
-  }
-
-}
diff --git a/tests/untried/pos/t6574.scala b/tests/untried/pos/t6574.scala
deleted file mode 100644
index 6bb0042c6..000000000
--- a/tests/untried/pos/t6574.scala
+++ /dev/null
@@ -1,19 +0,0 @@
-class Bad[X, Y](val v: Int) extends AnyVal {
-  def vv = v
-  @annotation.tailrec final def foo[Z](a: Int)(b: String): Unit = {
-    this.foo[Z](a)(b)
-  }
-
-  @annotation.tailrec final def differentReceiver {: Unit = 
-    {(); new Bad[X, Y](0)}.differentReceiver
-  }
-
-  @annotation.tailrec final def dependent[Z](a: Int)(b: String): b.type = {
-    this.dependent[Z](a)(b)
-  }
-}
-
-class HK[M[_]](val v: Int) extends AnyVal {
-  def hk[N[_]]: Unit = if (false) hk[M] else ()
-}
-
diff --git a/tests/untried/pos/t6891.flags b/tests/untried/pos/t6891.flags
deleted file mode 100644
index fe048006a..000000000
--- a/tests/untried/pos/t6891.flags
+++ /dev/null
@@ -1 +0,0 @@
--Ycheck:extmethods -Xfatal-warnings
\ No newline at end of file
diff --git a/tests/untried/pos/t6891.scala b/tests/untried/pos/t6891.scala
deleted file mode 100644
index bed2d0d77..000000000
--- a/tests/untried/pos/t6891.scala
+++ /dev/null
@@ -1,26 +0,0 @@
-object O {
-  implicit class Foo[A](val value: String) extends AnyVal {
-    def bippy() = {
-      @annotation.tailrec def loop(x: A): Unit = loop(x)
-      ()
-    }
-
-    def boppy() = {
-      @annotation.tailrec def loop(x: value.type): Unit = loop(x)
-      ()
-    }
-
-    def beppy[C](c: => C) = {
-      () => c
-      @annotation.tailrec def loop(x: value.type): Unit = loop(x)
-        () => c
-      ()
-    }
-  }
-  // uncaught exception during compilation: Types$TypeError("type mismatch;
-  //  found   : A(in method bippy$extension)
-  //  required: A(in class Foo)") @ scala.tools.nsc.typechecker.Contexts$Context.issueCommon(Contexts.scala:396)
-  // error: scala.reflect.internal.Types$TypeError: type mismatch;
-  //  found   : A(in method bippy$extension)
-  //  required: A(in class Foo)
-}