Why is this tail-call optimized method not recognized as such by the Scala compiler?

Question

This simple regex implementation (scastie here) does not compile, where I expected it to. The error is at line 14, where an intermediate recursive call is interpreted as to break the @tailrec requirement. While this intermediate recursive call is indeed not in tail-call position, the actual last call of the expression is, making the complete expression tail-call optimized.

This line of reasoning can be illustrated by aliasing the intermediate recursive call, turning it into an 'arbitrary' call. When the this call is aliased by aliasMatches, the code compiles and executes as expected.

Why doesn't the compiler accepts the non-aliased implementation? Is this a practical limitation, or is there something wrong with the reasoning above? Is there a way to coax the compiler in accepting the first version (other than a complete accumulator-rewrite) that I'm missing?

(using Scala 2.13.5)

import scala.annotation.tailrec

def matches(input: String, pattern: String): Boolean = {

    @tailrec
    def matchesRemainder(remainder: Seq[Char], remainingPattern: Seq[Char]): Boolean =
        (remainder, remainingPattern) match {
            case (Seq(), Seq()) => true
            case (Seq(_@_*), Seq()) => false

            case (Seq(), Seq(_, '*', _@_*)) => true
            case (Seq(), Seq(_@_*)) => false
                                                        \\ vvvv error vvvv
            case (Seq(_, rs@_*), Seq('.', '*', xs@_*)) => matchesRemainder(rs, remainingPattern) ||
                matchesRemainder(remainder, xs)
            case (Seq(r, rs@_*), Seq(p, '*', xs@_*)) => (r == p && aliasMatches(rs, remainingPattern)) ||
                matchesRemainder(remainder, xs)

            case (Seq(_, rs@_*), Seq('.', ps@_*)) => matchesRemainder(rs, ps)
            case (Seq(r, rs@_*), Seq(p, ps@_*)) => r == p && matchesRemainder(rs, ps)
        }

    def aliasMatches(remainder: Seq[Char], p: Seq[Char]): Boolean =
        matchesRemainder(remainder, p)

    matchesRemainder(input, pattern)
}

Answer 1

Let's simplify it a little bit, to see the problem more clearly.

    @tailrec
    def foo(x: Int): Boolean = x == 0 || foo(x-1) || foo(x-2)

This does not compile, because it cannot eliminate recursion completely: foo(x-1) has to return control back to the caller, so in can evaluate the result and either return it, or call foo(x-2). Tail recursion can only happen when the result of the recursive call is directly returned right away, without the control returning to the caller.

Now why does this compile?

   def bar(x: Int) = foo(x) 
   @tailrec
   def foo(x: Int): Boolean = x == 0 || bar(x-1) || foo(x-2)

Well, that's just cheating :) The compiler doesn't expect you to be that cunning, it has no way of knowing that bar is just going to call foo, so it has to trust you on that.

Basically @tailrec can only detect the immediate recursion if you try to mask it ... well, you will succeed :)

Remove || foo(x-2) from the above – it'll stop compiling, and tell you there is no recursion. Even though it is now a perfectly tail-recursive function, it will not be able to optimize it.

It's not a golden bullet. Here's another quirk:

    @tailrec
    def foo(x: => Future[Int]): Future[Int] = {
       x.recoverWith { case _ => foo(x) }
       foo(Future(1))
    }

This is tail-recursive, but it will refuse to compile, because it does not realize that the first call to foo doesn't actually happen inside the outer foo.