"match may not be exhaustive" warning for LazyList (but not for List)

[flomebul]

reproduction steps

using Scala 2.13.4,

  def diff(one: LazyList[Int], two: LazyList[Int]): LazyList[Int] =
    (one, two) match {
      case (LazyList(), _) => two
      case (_, LazyList()) => one
      case (onh #:: ont, twh #:: twt) =>
        (onh - twh).sign match {
          case -1 => onh #:: diff(ont, two)
          case  1 => twh #:: diff(one, twt)
          case  0 => diff(ont, twt)
        }
    }

problem

Compiling this code result in a warning

ABug.scala:30: warning: match may not be exhaustive.
It would fail on the following input: (_, _)
    (one, two) match {
    ^

While the same code with List replacing LazyList and "::" replacing "#::" compile without error.

[dwijnand]

I think we need to fix this by adding the same kind of rewrite that is used for List.

[dwijnand]

During the pattern matcher's analysis, it rewrites List(), which is an invocation of List.unapply, to Nil, which is a subclass/object, so that analysis works nicely when combined with usages of its other subclass ::.

Which is why at first I thought this was because it was using LazyList(). Turns out because of another change I did, that rewrite was applying to LazyList already. The problem is that LazyList isn't a sealed hierarchy (Stream was/is, btw) - it's a final class. Which first of all means it doesn't even get any exhaustivity warnings unless you opt-in. But then it means that #:: isn't one of its subclasses. So I think this is stuck in the "how do you define complementary custom extractors" bucket, like for :+ and other, non-stdlib, custom extractors.

[martijnhoekstra]

Side note, to workaround the immediate issue, if you don't want to add an @unchecked annotation, the following version of the example is exhaustive:

def diff(one: LazyList[Int], two: LazyList[Int]): LazyList[Int] =
  (one, two) match {
    case (onh #:: ont, twh #:: twt) =>
      (onh - twh).sign match {
        case -1 => onh #:: diff(ont, two)
        case 1  => twh #:: diff(one, twt)
        case 0  => diff(ont, twt)
      }
    case (LazyList(), _) => two
    case (_, _)          => one
  }

Another exhaustive variation available now is

def diff(one: LazyList[Int], two: LazyList[Int]): LazyList[Int] =
  (#::.unapply(one), #::.unapply(two)) match {
    case (None, _) => two
    case (_, None) => one
    case (Some(onh -> ont), Some(twh -> twt)) =>
      (onh - twh).sign match {
        case -1 => onh #:: diff(ont, two)
        case 1  => twh #:: diff(one, twt)
        case 0  => diff(ont, twt)
      }
  }

Though I'll give you that explicitly calling unapply on the symbolic extractor is really ugly. This would become a bit less ugly if LazyList had that unapply method as an instance method, maybe called uncons. Maybe that's a candidate for library-next. Then you'd have:

def diff(one: LazyList[Int], two: LazyList[Int]): LazyList[Int] =
  (one.uncons, two.uncons) match {
    case (None, _) => two
    case (_, None) => one
    case (Some(onh -> ont), Some(twh -> twt)) =>
      (onh - twh).sign match {
        case -1 => onh #:: diff(ont, two)
        case 1  => twh #:: diff(one, twt)
        case 0  => diff(ont, twt)
      }
  }

[martijnhoekstra]

Is the now the "match exhaustiveness of unapplySeq is not tracked over arities of irrefutably extracted seqs, or is that (or should it be) a separate one?

[dwijnand]

Something's wrong with your sentence, but it sounds like you're describing your #12252. No? To me this ticket is now "why doesn't this linked list have the same exhaustivity properties that I get with List?"

[martijnhoekstra]

Yes, I am describing my own #12252, but that was like several days ago. If this isn't a duplicate of that, then I don't think this is a bug per your analysis: the expectation that the compiler should know SomeCollection() should be complementary with some head -> tail destructuring, the only thing actionable here, I think, is finding (and correcting) what causes that false expectation -- which may actually be the rewrite of List() to Nil itself

[dwijnand]

Maybe I can teach the analysis that #::.unapply usage is complementary with Nil... but I think it's too hard and maybe still a bad idea.

I still think it's a legit issue because it's not just SomeCollection, it's in the standard library... 😦

[martijnhoekstra]

My thinking is, for the general case, we should get varargs exhaustiveness to work per #12252 -- conceptually it's clear: a set of "irrefutable" varargs extractors is actually exhaustive if all arities are covered. Then the user could write this case in terms of varargs extractors to be exhaustive. I intend to work on that, but can't make any promises I'll succeed in that.

If you don't want to call it good just yet then, because you also kind of want a #:: b #:: c #:: tail to work, we could then re-write that to LazyList(a, b, c, tail @ _*) and rely on the underlying varargs exhaustiveness to check that. I personally don't like baking ergonomics for specific types into the compiler, because it can lead to frustration too, when it's unclear why a users own code doesn't do what LazyList does and then finding out that that works because the compiler "cheats".