Spurious Match Exhaustivity Warning

[adamgfraser]

I'm getting what appears to be a spurious pattern matching exhaustivity warning. I'm trying to define a function Either[X, A] => Int using pattern matching. My first match clause is for Left(Y), where Y is an object that is a subtype of X. My second match clause is a wildcard that should catch anything else. But I'm getting a warning that the match would fail for Left(_). Note that this compiles with Scala 2.12.7. Relatively minimized case below.

import scala.language.higherKinds

object Test {

  trait X
  case object Y extends X

  trait Foo[F[_], O] {
    def bar: Foo[F, O] = this match {
      case Qux(fa, f) => qux(fa) {
        case Left(Y) => ???
        case x => ???
      }
    }
  }

  case class Qux[F[_], A, O](fa: F[A], f: Either[X, A] => Int) extends Foo[F, O]

  def qux[F[_], A, O](fa: F[A])(f: Either[X, A] => Int): Foo[F, O] =
    Qux(fa, f)
}

[error] 11 |        case Left(Y) => ???
[error]    |        ^
[error]    |        match may not be exhaustive.
[error]    |
[error]    |        It would fail on pattern case: Left(_)

[adamgfraser]

Here is another pattern matching issue. Sorry if this has already been reported somewhere else.

  def test[A](s: Stream[A]) = s match {
    case h #:: t => ???
    case Stream.Empty => ???
  }

[warn] 17 |  def test[A](s: Stream[A]) = s match {
[warn]    |                              ^
[warn]    |                              match may not be exhaustive.
[warn]    |
[warn]    |                              It would fail on pattern case: _: Cons

[liufengyun]

@adamgfraser Thanks for reporting.

For the first example, adding sealed to trait X will pass the check.

For the second example, it's a problem with the extractor #::. The following program passes the check without any problem:

sealed abstract class Stream[+A] {
  def isEmpty: Boolean = ???
  def head: A = ???
  def tail: Stream[A] = ???
}

final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A]

object Empty extends Stream[Nothing]

object #:: {
  def unapply[A](xs: Cons[A]): Some[(A, Stream[A])] = //  <-------  Use `Some` for irrefutable pattern
    Some((xs.head, xs.tail))
}


class Test {
  def test[A](s: Stream[A]) = s match {
    case h #:: t => ???
    case Empty => ???
  }
}

Note that the extractor should return Some to indicate that it's irrefutable.

[smarter]

def unapply[A](xs: Cons[A]): Some[(A, Stream[A])] = // <------- Use Some for irrefutable pattern

This could work for Stream, but not for LazyList which replaces Stream in 2.13 and does not use subclasses to distinguish empty and non-empty lists: https://github.com/scala/scala/blob/2.13.x/src/library/scala/collection/immutable/LazyList.scala

[smarter]

Oh but I guess that doesn't matter since you can't match on anything more precise than _: LazyList for the other case then

[liufengyun]

It's possible to define extractors for LazyList as follows:

sealed class LazyList[A] {
  def nonEmpty: Boolean = ???
  def head: A = ???
  def tail: LazyList[A] = ???
}

object LazyList {
  def unapply[A](s: LazyList[A]): Some[(A, LazyList[A]) | Unit] =  // pity: Nil.type disallowed in union type!
    if (s.nonEmpty) Some(s.head -> s.tail) else Some(())
}

object #:: {
  def unapply[A](pair: (A, LazyList[A])): Some[(A, LazyList[A])] = Some(pair._1 -> pair._2)
}

object Test {
  def f(s: LazyList[Int]) = s match { // It would fail on pattern case: LazyList(())
    case LazyList(x #:: xs) =>
    // case LazyList(()) =>
  }
}

[liufengyun]

The extractor LazyList looks redundant. One possible way to make it nicer is to define a spliter:

sealed class LazyList[A] {
  def split: (A, LazyList[A]) | Unit = if (s.nonEmpty) s.head -> s.tail else ()
}

object #:: {
  def unapply[A](pair: (A, LazyList[A])): Some[(A, LazyList[A])] = Some(pair._1 -> pair._2)
}

object Test {
  def f(s: LazyList[Int]) = s.split match { // It would fail on pattern case: ()
    case x #:: xs =>
    // case() =>
  }
}

[adamgfraser]

@liufengyun Thanks! Unfortunately in the first example X is not under my control so I can't make it sealed. Definitely not the end of the world but it seems wrong that if I do match { case x => ??? } I have an exhaustive match but if I do match { case Left(Y) => ???; case x => ??? }, just adding a more specific possibility before the same catch all, the match is now deemed not exhaustive.

[liufengyun]

@adamgfraser I see now, indeed the warning is an error.