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

8 files changed, 124 insertions, 0 deletions

diff --git a/tests/pos/tailcall/t1672.scala b/tests/pos/tailcall/t1672.scala
new file mode 100644
index 000000000..9be5c6066
--- /dev/null
+++ b/tests/pos/tailcall/t1672.scala
@@ -0,0 +1,10 @@
+object Test1672 {
+  @annotation.tailrec
+  def bar(x: Int)(y: Int) : Nothing = {
+    try {
+      throw new RuntimeException
+    } catch {
+      case _: Throwable => bar(x)(y)
+    }
+  }
+}
diff --git a/tests/pos/tailcall/t4649.flags b/tests/pos/tailcall/t4649.flags
new file mode 100644
index 000000000..e8fb65d50
--- /dev/null
+++ b/tests/pos/tailcall/t4649.flags
@@ -0,0 +1 @@
+-Xfatal-warnings
\ No newline at end of file
diff --git a/tests/pos/tailcall/t4649.scala b/tests/pos/tailcall/t4649.scala
new file mode 100644
index 000000000..5f009b7a4
--- /dev/null
+++ b/tests/pos/tailcall/t4649.scala
@@ -0,0 +1,6 @@
+object Test4649 {
+  // @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/pos/tailcall/t6479.scala b/tests/pos/tailcall/t6479.scala
new file mode 100644
index 000000000..e4a4ff601
--- /dev/null
+++ b/tests/pos/tailcall/t6479.scala
@@ -0,0 +1,56 @@
+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/pos/tailcall/t6574.scala b/tests/pos/tailcall/t6574.scala
new file mode 100644
index 000000000..cd0fdbb8d
--- /dev/null
+++ b/tests/pos/tailcall/t6574.scala
@@ -0,0 +1,19 @@
+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/pos/tailcall/t6891.flags b/tests/pos/tailcall/t6891.flags
new file mode 100644
index 000000000..fe048006a
--- /dev/null
+++ b/tests/pos/tailcall/t6891.flags
@@ -0,0 +1 @@
+-Ycheck:extmethods -Xfatal-warnings
\ No newline at end of file
diff --git a/tests/pos/tailcall/t6891.scala b/tests/pos/tailcall/t6891.scala
new file mode 100644
index 000000000..edbe6f097
--- /dev/null
+++ b/tests/pos/tailcall/t6891.scala
@@ -0,0 +1,26 @@
+object O6891 {
+  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)
+}
diff --git a/tests/pos/tailcall/tailcall.scala b/tests/pos/tailcall/tailcall.scala
new file mode 100644
index 000000000..9cf373cf0
--- /dev/null
+++ b/tests/pos/tailcall/tailcall.scala
@@ -0,0 +1,5 @@
+class tailcall {
+  val shift = 1
+  final def fact(x: Int, acc: Int = 1): Int = if (x == 0) acc else fact(x - shift, acc * x)
+  def id[T <: AnyRef](x: T): T = if (x eq null) x else id(x)
+}