Nil and List as case expressions in Scala

Question

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?

Answer 1

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"  
  }  
}  

Answer 2

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).