Pattern matching breaks @tailrec

[Atry]

Welcome to Scala 2.12.3 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_131).
Type in expressions for evaluation. Or try :help.

scala> trait Cons[A] {
     |   def next(): Any
     | 
     |   @scala.annotation.tailrec
     |   final private def last(): Any = {
     |     next() match {
     |       case cons: Cons[_] =>
     |         cons.last()
     |       case notCons =>
     |         notCons
     |     }
     |   }
     | }
<console>:20: error: could not optimize @tailrec annotated method last: it contains a recursive call not in tail position
               notCons
               ^

[viktorklang]

@Atry Your last method is not tail recursive. (Hint: cons.last() is not the same as last())

[jvican]

I guess the error here is in the error message. Should be:

<console>:18: error: could not optimize @tailrec annotated method last: it contains a recursive call not in tail position
               cons.last()
               ^

instead of:

<console>:20: error: could not optimize @tailrec annotated method last: it contains a recursive call not in tail position
               notCons
               ^

[viktorklang]

@jvican That's an assessment I'd second.

[martijnhoekstra]

Shouldn't the error rather be

@tailrec annotated method contains no recursive calls

when aiming low, or something like

@tailrec annotated method contains no recursive calls
  because
  `last` on `cons` is not the same function as `last` on `this`

when aiming high?

[sjrd]

scalac is in general perfectly capable of tailrec-transforming methods that call themselves on a different receiver than this. However, it cannot do so if the polymorphic type of this changes. The compile error I would expect in this case should be similar to what we get with an if instead of the match:

scala> trait Cons[A] {
     |   def next(): Any
     |
     |   @scala.annotation.tailrec
     |   final def last(): Any = {
     |     val n = next()
     |     if (n.isInstanceOf[Cons[_]])
     |       n.asInstanceOf[Cons[_]].last()
     |     else
     |       n
     |   }
     | }
<console>:14: error: could not optimize @tailrec annotated method last: it changes type of 'this' on a polymorphic recursive call
             n.asInstanceOf[Cons[_]].last()
                                     ^

If we cheat and cast to Cons[A] (because we can), it works:

scala> trait Cons[A] {
     |   def next(): Any
     |
     |   @scala.annotation.tailrec
     |   final def last(): Any = {
     |     val n = next()
     |     if (n.isInstanceOf[Cons[_]])
     |       n.asInstanceOf[Cons[A]].last()
     |     else
     |       n
     |   }
     | }
defined trait Cons

[viktorklang]

@sjrd 👍

[Atry]

@sjrd I think it's a different problem.

In the example that I provided, the error position is notCons. The error position suggests there is a type unification inserted at the end of the match, which prevents tail-call optimization.

[sjrd]

The position of the error is definitely off, but it is the problem I describe. You can also "fix" the problem with a .asInstanceOf[Cons[A]] in your original example:

scala> :paste
// Entering paste mode (ctrl-D to finish)

trait Cons[A] {
  def next(): Any

  @scala.annotation.tailrec
  final private def last(): Any = {
    next() match {
      case cons: Cons[_] =>
        cons.asInstanceOf[Cons[A]].last()
      case notCons =>
        notCons
    }
  }
}

// Exiting paste mode, now interpreting.

defined trait Cons

[TomasMikula]

scala/scala#6065 would allow a workaround:

trait Cons[A] {
  def next(): Any

  def last(): Any = {
    @scala.annotation.tailrec
    def go[T](c: Cons[T]): Any = 
      c.next() match {
        case cons: Cons[_] =>
          go(cons)
        case notCons =>
          notCons
      }

    go(this)
  }
}