Does the +: extractor break exhaustive match checking?

Hello! I have a problem with exhaustiveness check: it seems like the collection extractors +: and :+ breaks the exhaustiveness check, for instance in the following example:

  sealed trait Tr
  final case class A(list: List[Int]) extends Tr
  final case class B(list: List[Int]) extends Tr
  val tr: Tr = A(List.empty)
  tr match {
      case A(_ +: list) => list
   // case B(_) should be required...
  }

In this example I get no warning, even though the case for B should be defined to be complete (at the very least).
If you instead of using the +: replace it with ::, you do the get expected warning:

match may not be exhaustive.
It would fail on the following input: B(_)
tr match {

In fact, these extractors break the exhaustiveness check when you match on a List directly:

def matchTest(list: List[String]): String = {
  list match {
    case head +: Nil => head
//    case _ => "empty"   -- no warning for missing this!
  }
}

I’ve googled and haven’t found why this is, or how I can work around it.
This goes for Scala 2.12 as well as 2.13.3 (the two I have tried this with).
Does anyone know about this?

Summary

This text will be hidden

My advice would be never use +:
If you use it on something that is not a List or a LazyList it will have a very bad performance. And if you know you have a List then what is the point of using +: over ::?

Anyways, the reason is that all extractors (as well as if guards) break exhaustive checks.

Isn’t :: an extractor?

As for the need, if I know the List is not too large, I’d like to be able to pattern match on the last element (without having to reverse the list first…) with case list :+ last .

No, it isn’t. It is a case class and one that is a member of an ADT (a sealed trait).
The compiler treats those different to custom extractors (even tho both use the unapply method under the hood).

Well, if you want to preserve exhaustivity you can do this:
(which is quite ugly, I know)

list match {
  case Nil =>
    ???

  case nonEmptyList =>
    val (init, last) = nonEmptyList.init -> onEmptyList.last
}

However, note that if you need both init and last is more efficient to reverse first.
And if you only need the last element then using :+ will still call both init and last, so another reason to avoid it.

On latest 2.13.x nightly,

Welcome to Scala 2.13.4-bin-7e9fd55 (OpenJDK 64-Bit Server VM, Java 1.8.0_272).
Type in expressions for evaluation. Or try :help.

scala 2.13.4-bin-7e9fd55> sealed trait Tr
                        |   final case class A(list: List[Int]) extends Tr
                        |   final case class B(list: List[Int]) extends Tr
                        |   val tr: Tr = A(List.empty)
                        |   tr match {
                        |       case A(_ +: list) => list
                        | }
                            tr match {
                            ^
On line 5: warning: match may not be exhaustive.
                          It would fail on the following inputs: A(List(_)), A(Nil), B(_)

see https://github.com/scala/scala/pull/9140

1 Like

Great news @SethTisue !
So was this planned or did it make in in there because of this post? :stuck_out_tongue:
And does it also cover the :+ extractor?
Edit: ah sorry missed the PR-link, which answered these questions.

So from a Scala user point of view, is it clear that :: differs from +: and :+ in terms of match checking?
I think at least it should warn in the docs…?

But A(List(_)) is a false positive. It’s because the exhaustiveness checker doesn’t know what +: does of course. But when you’re working with Seq instead of List it becomes an actual problem:

scala> sealed trait Tr
     | final case class A(seq: Seq[Int]) extends Tr
     | final case class B(seq: Seq[Int]) extends Tr
     | val tr: Tr = A(List.empty)
     | tr match {
     |   case A(_ +: tail) => tail // really unsafe to use :: here
     |   case A(Seq()) => Seq()
     |   case B(seq) => seq
     | }
       tr match {
       ^
On line 5: warning: match may not be exhaustive.
       It would fail on the following input: A((x: Seq[?] forSome x not in Nil))

Maybe you can argue ‘ok but +: is not “performance safe” in general’ but then why does it exist if you can’t use it.

1 Like

To be honest A(List(_)) is the one that’s misrepresenting itself and A(Nil) is making it more confusing. A(List(_)) is trying to say "as a counter-example, any value of List, of unknown variadic size, for which +: returns None". Perhaps it should be A(List(_: _*)) (or is it A(List(_ @ _*))? and in Scala 3 A(List(_ as _*)), now?).

The reason A(Nil) is there is because there’s little fudging going on for List to make case List(..) give nice results even though List.unapply is a custom extractor.

Still not sure I get it. So in this example:

List("") match {
  case Nil => "Nil"
  case head +: tail => head
}

I will get the warning. If I instead use head :: tail there’s no warning. Why can’t the compiler know how the built in extractors +: and :+ work, and use them in exhaustiveness checking?

You are basically asking for the compiler to solve the halting problem.

Is it because :: is a concrete implementation, whereas +: is abstract (it could be implemented for any type of collection?

:: is a case class whose default unapply methods have well known (to the compiler) semantics. +: and :+ are just objects with custom unapply methods that—as far as the compiler knows—can do anything. That knowledge could be built into the compiler though, but then that would be a special case for these specific unapply methods in the std library, which would then be treated differently if you defined them yourself.

2 Likes

No, is because as I said before :: is not a (custom extractor) but rather a member of an ADT.

Thus, the compiler can know that if you have three cases you have to check for those three cases.
But, with a custom extractor the compiler can not simply understand the logic behind the extractor and then understand what would be missing. Because again, this is reducible to the halting problem.

I don’t know, but I’ve been assuming that :: works because :: is a class with an unapply method, and I’m not sure how :+ even works as an extractor.

Huh, never noticed that, and probably never even used it in code:image

No, :: works because it’s a case class. Just like case class Foo(x: Int) and case Foo(x) => work because its a case class. :+ works because it’s an object with an unapply, aka it’s a custom extractor.

It’s a 2.13 addition.
The documentation is a bit off though. The B in the doc refers to the A in the method signature and the A refers to the Int in the method signature. But I guess that’s a scaladoc feature request (i.e. interpolate the correct names into inherited docs).