Nil and List as case expressions in Scala

This code compiles:

def wtf(arg: Any) = {  
  arg match {  
    case Nil => "Nil was passed to arg"  
    case List() => "List() was passed to arg"  
    case _ =>"otherwise"  
  }  
}

But this one does not:

def wtf(arg: Any) = {  
  arg match {  
开发者_运维技巧    case List() => "List() was passed to arg"  
    case Nil => "Nil was passed to arg"  
    case _ =>"otherwise"  
  }  
}  

The line case Nil => ... is marked as unreachable code. Why, in the first case, the line case List() => ... is not marked with the same error?

The actual answer requires understanding an unfortunate implementation detail which cost me a lot of time to discover.

1) case List() invokes an extractor, for which no exhaustivity/unreachability checking is possible in the general case because extractors invoke arbitrary functions. So far so good, we can't be expected to overturn the halting problem.

2) Way back in the more "wild west" days of the compiler, it was determined that pattern matching could be sped up rather a lot (and not lose exhaustivity checking) if "case List()" were just translated to "case Nil" during an early compiler phase so it would avoid the extractor. This is still the case and although it could be undone, apparently lots of people have been told that "case List() => " is perfectly fine and we don't want to pessimize all their code all of a sudden. So I just have to figure out a road out.

You can see empirically that List is privileged by trying it with some other class. No unreachability errors.

import scala.collection.immutable.IndexedSeq
val Empty: IndexedSeq[Nothing] = IndexedSeq()
def wtf1(arg: Any) = {  
  arg match {  
    case Empty => "Nil was passed to arg"  
    case IndexedSeq() => "IndexedSeq() was passed to arg"  
    case _ =>"otherwise"  
  }  
}

def wtf2(arg: Any) = {  
  arg match {  
    case IndexedSeq() => "IndexedSeq() was passed to arg"  
    case Empty => "Nil was passed to arg"  
    case _ =>"otherwise"  
  }  
}  

The discrepancy is particularly weird since the code for the Nil case in the second version is definitely not unreachable, as we can see if we hide things from the compiler a bit:

def wtf(arg: Any) = {
  arg match {
    case List() => "List() was passed to arg"  
    case x => x match {
      case Nil => "Nil was passed to arg"
      case _ =>"otherwise"
    }
  }
}

Now wtf(Vector()) will return "Nil was passed to arg". This may also seem counterintuitive, but it's because literal patterns match values that are equal in terms of ==, and Vector() == Nil, but Vector() doesn't match the extractor pattern List().

More concisely:

scala> (Vector(): Seq[_]) match { case List() => true; case Nil => false }
<console>:8: error: unreachable code

scala> (Vector(): Seq[_]) match { case List() => true; case x => x match { case Nil => false } }
res0: Boolean = false

So the compiler's response is completely reversed: in the "good" version the second case is unreachable, and in the "bad" version the second case is perfectly fine. I've reported this as a bug (SI-5029).

Nil is an object extending List[Nothing]. Being more specific than List(), it isn't reached if it appears after List() in the case expression.

While I think the above is more or less true, it's likely not the whole story.

There are hints in the article Matching Objects with Patterns, though I don't see a definitive answer there.

I suspect that detection of unreachability is simply more completely implemented for named constants and literals than for constructor patterns, and that List() is being interpreted as a constructor pattern (even though it's a trivial one), while Nil is a named constant.

I cannot find anything in the language specification with respect to unreachable match clauses. Somebody correct me if I'm wrong.

So I assume that unreachable compilation errors are on a best effort basis, which may explain why the first case does not complain.

scala -Xprint:typer suggests that Nil is a literal pattern using immutable.this.Nil.== to check for a match, while List() is an extractor pattern. Looking at the implementation of the extractor in it seems to be doing something like this:

def unapplySeq[A](x: CC[A]): Some[CC[A]] = Some(x)

So I got curious and rolled out an alternate implementation:

object ListAlt {
  def unapplySeq[A](l: List[A]): Some[List[A]] = Some(l)
}

It matches like List():

scala> Nil match { case ListAlt() => 1 }
res0: Int = 1

But if I implement your function with it, it compiles fine (except for unchecked warning):

def f(a: Any) = a match { case ListAlt() => 1 case Nil => 2 case _ => 0 }

scala> f(List())
res2: Int = 1

scala> f(Nil)
res3: Int = 1

scala> f(4)
res4: Int = 0

So I am wondering if the pattern matcher implementation has some special casing for Nil and List(). May be it treats List() as a literal...