Dotty: Wrong pat mat exhaustivity / reachability warnings involving F-bounds

[Sciss]

Minimized code

This is a data structure with a "rectangular" type matrix, e.g. traits for Left versus Right, Branch versus Leaf, Empty versus NonEmpty. I believe the warnings emitted by Scala 3.0.0-M1 (none of them emitted by Scala 2.13) are wrong:

https://github.com/Sciss/DottyLucrePatMat

(class DetSkipOctree).

Output

The warnings look like this:

[warn] -- [E029] Pattern Match Exhaustivity Warning: /data/temp/DottyLucreBreaks/src/main/scala/de/sciss/lucre/data/DetSkipOctree.scala:261:71 
[warn] 261 |    final def nextOption(implicit tx: T): Option[Branch[T, P, H, A]] = thisBranch.next match {
[warn]     |                                                                       ^^^^^^^^^^^^^^^
[warn]     |match may not be exhaustive.
[warn]     |
[warn]     |It would fail on pattern case: _: DetSkipOctree.RightTopBranchImpl[<? <: de.sciss.lucre.Exec[LazyRef(T)] & de.sciss.lucre.Exec[LazyRef(T)] & 
[warn]     |  de.sciss.lucre.Exec[LazyRef(T)]
[warn]     | & T>,<? <: P>,<? <: H>,<? <: A>], _: DetSkipOctree.RightChildBranchImpl[<? <: de.sciss.lucre.Exec[LazyRef(T)] & de.sciss.lucre.Exec[LazyRef(T)] & 
[warn]     |  de.sciss.lucre.Exec[LazyRef(T)]
[warn]     | & T>,<? <: P>,<? <: H>,<? <: A>]
[warn] -- [E030] Match case Unreachable Warning: /data/temp/DottyLucreBreaks/src/main/scala/de/sciss/lucre/data/DetSkipOctree.scala:263:11 
[warn] 263 |      case b: Branch[T, P, H, A]  => Some(b)
[warn]     |           ^^^^^^^^^^^^^^^^^^^^^
[warn]     |           Unreachable case

[liufengyun]

@Sciss Thanks for reporting. It would be nice to have a minimized version so that we can provide a quick fix.

[smarter]

My best attempt at minimizing:

trait Exec[T <: Exec[T]]
sealed trait Child[+T]
sealed trait Next[+T] extends Child[T] 
sealed trait Branch[T <: Exec[T]] extends Child[T] {
  def foo(x: Next[T]): Unit = x match {
    case x: Branch[T] =>
  }
}
final class RightBranch[T <: Exec[T]] extends Next[T] with Branch[T]

-- [E029] Pattern Match Exhaustivity Warning: try/i10254.scala:5:30 ------------
5 |  def foo(x: Next[T]): Unit = x match {
  |                              ^
  |match may not be exhaustive.
  |
  |It would fail on pattern case: _: RightBranch[<? <: Exec[LazyRef(T)] & T>]

longer explanation available when compiling with `-explain`
-- Warning: try/i10254.scala:6:9 -----------------------------------------------
6 |    case x: Branch[T] =>
  |         ^^^^^^^^^^^^
  |         the type test for Branch[T] cannot be checked at runtime
2 warnings found

[smarter]

In that minimization, the warnings goes away if I replace case x: Branch[T] by case x: Branch[_], but in the original code doing so leads to more errors. This can be reproduced by tweaking the minimization a bit to add a result type to foo:

  def foo(x: Next[T]): Branch[T] = x match {
    case x: Branch[T] => x // same warning as before
  }

// no warning, error instead:
  def foo(x: Next[T]): Branch[T] = x match {
    case x: Branch[_] => x // error: Found:    (x : Next[T] & Branch[_])
                           // Required: Branch[T]
                           // where:    _ is a type in method foo with bounds <: Exec[LazyRef(Branch[?]#T)]
  }

Same conclusion as usual: F-bounds are bad.

[Sciss]

Thanks for the minimization. I'm a bit tired of hearing "f-bounds are bad", though. They are not bad, they are an essential feature of the language, and I understand reimplementing them in the new compiler is a lot of work, but please don't put the blame on people using this well-defined and battle-proven construct. Cheers.

[smarter]

Not blaming you, Java is the one at fault here for introducing them, which means we're forced to support them, but we're not necessarily happy about it :p. But I would still advise people to avoid them if possible (and in fact they're rarely used in Scala as far as I can see, the standard library being a notable exception).

[Sciss]

Well, they are the piece that holds my system still together after extensively refactoring to do without type projections :shrug: I have not seen a convincing argument why they are bad, except from the compiler authors' perspective. In the end Scala is an OOP with sub-typing and not just a syntactic variant of Haskell....

[liufengyun]

If we make the type parameters for Branch covariant, it will work:

trait Exec[T <: Exec[T]]
sealed trait Child[+T]
sealed trait Next[+T] extends Child[T]
sealed trait Branch[+T <: Exec[T]] extends Child[T]
final class RightBranch[+T <: Exec[T]] extends Next[T] with Branch[T]

def foo[T <: Exec[T]](x: Next[T]): Unit = x match {
  case x: Branch[T] =>
}

[smarter]

class RightBranch[+T <: Exec[T]]

Huh, I'm surprised this isn't a variance error given that T appears in an invariant position here (and in fact the same code fails in Scala 2 with a variance error so this might be a missing check in dotty)

[odersky]

Thanks for the minimization. I'm a bit tired of hearing "f-bounds are bad", though. They are not bad, they are an essential feature of the language, and I understand reimplementing them in the new compiler is a lot of work, but please don't put the blame on people using this well-defined and battle-proven construct. Cheers.

I am afraid there's not much we can do about F-bounds. My preference would be to get rid of them. My preferred strategy to deal with them until that point is to restrict their usage as much as possible.

F-bounds are not battle proven. it's just that people got used to nsc's behavior for them, which also has its share of problems. The problem with F-Bounds is essentially that when you try to find out anything about them you go into an infinite cycle. Scala 2 has quite different typing rules which do not require coalescing information as much. In Scala 3, we have to intersect types more often, and that's what often causes the problems.

To sum it up: F-bounds are by far the feature that causes most complexity in the compiler. Complexity is bad, it leads to bugs and fragility. Hence, I am afraid, F-bounds _are_ bad. We should not have to contort the language to accommodate them. By now there are usually better ways to do things. E.g. context bounds, higher-kinded types.

[smarter]

Setting aside the F-bounds related issue, I believe that at least some of the pattern matches in https://github.com/Sciss/DottyLucrePatMat are unsafe (or at least, they're not safe in a way that can be statically determined by the exhaustiveness checker), for example consider https://github.com/Sciss/DottyLucrePatMat/blob/08c77b08b9a3c642f5018becaed13ea9194a02a9/src/main/scala/de/sciss/lucre/data/DetSkipOctree.scala#L261-L264, here's an F-bounds-free reduction:

sealed trait Next[+T]
sealed trait Branch[T] extends Next[T]
final class RightBranch[T] extends Next[T] with Branch[T]

object Test {
  def foo[T](x: Next[T]): Branch[T] = x match {
    case b: Branch[T] => b
  }
}

Scala 2 doesn't say anything here, but Scala 3 will rightfully warn:

17 |    case b: Branch[T] => b
   |         ^^^^^^^^^^^^
   |         the type test for Branch[T] cannot be checked at runtime

The problem comes from matching on a type with a covariant type parameter where the same type parameter is invariant in the subclass. If I have an instance of Branch[Int] I can safely upcast it to Next[Int], and then upcast that to Next[Any], but if I then pattern match on the Next[Any], I can't safely get a Branch[Any] out of it because Branch is invariant in its type parameter! So the best I can do is say that I have a Branch[_ <: Any], or in other words I can avoid the unchecked warning by writing:

  def foo[T](x: Next[T]): Branch[_ <: T] = x match {
    case b: Branch[_ <: T] => b
  }

Alternatively, I can make the whole hierarchy invariant or covariant in its type parameter (but in your case to make everything covariant I believe you'd need Exec to be covariant as well even though Dotty doesn't require it as I mentioned in https://github.com/lampepfl/dotty/issues/10254#issuecomment-724349624)

[Sciss]

The variance in that example is merely used to include Empty. To view Next[+T] without the constraints on T changes the situation of course. I can assure you that the type grid is sound. I was about to make a .dot file, but it took longer than you came up with the minimised case. Your example does not match with the actual usage. I believe you were departing from

trait Branch[T <: Exec[T]] {
  def next(implicit tx: T): Next[T]

  def nextOption(implicit tx: T): Option[Branch[T]] = next match {
      case Empty         => None
      case b: Branch[T]  => Some(b)
    } 
}

So clearly T cannot be Any. Whether the pat mat is right in being more constrained than in Scala 2, I cannot judge. I was indeed more worried about the reachability warnings, because clearly my class runs correctly and all the cases are indeed reached.

[smarter]

So clearly T cannot be Any

In the original code there's four type parameters, only one of them has an (f-)bounds, the three other don't but are also covariant in Next and invariant in Branch, so my point still stands.

[Sciss]

So clearly T cannot be Any

In the original code there's four type parameters, only one of them has an (f-)bounds, the three other don't but are also covariant in Next and invariant in Branch, so my point still stands.

the submitted example is a simplified case. "original" code has three type parameters, two of them F-bounded. The number of type parameters grew after refactoring to do without type projections removed by Dotty. The last parameter A indeed is unconstrained. The alternative I can see is to axe Empty and move to Option everywhere. Kind of sad, as this is a data structure at the performance heart of the system, so I would like to avoid overhead here. The whole situation is complicated by cross-building Scala 2 / 3. If I only targetted Dotty, I could probably use union types instead.

[smarter]

Maybe this won't help especially since it's a Scala 3 only thing, but from the code snippet you wrote my first instinct would be to try to take advantage of the fact that implicit parameter blocks can come before explicit parameter blocks now, e.g.:

trait ConfluentTxn extends Txn {
  type Id <: ConfluentIdent
}

class InMemoryIdMap[T <: ConfluentTxn, A] {
  def get(implicit tx: T)(id: tx.Id): Option[A] = {
    getCache[A](id.base, tx)(id.path)
  }
}

Indeed I wouldn't even know how to submit this project to a community build, as it depends itself on a dozen other libraries I developed, so I would have to submit them all.

Unlike the Scala 2 community build, we allow projects in our community build even if they depend on other Scala 2 projects because we maintain binary compatibility with Scala 2, so you can submit individual projects if you're interested, https://github.com/lampepfl/dotty/tree/master/community-build#dotty-community-build has instructions. We try to keep projects in the community build compiling when making changes, but do note that this isn't a guarantee, especially if the project is complex we might just disable it if we can't figure out how to keep it working.

I am not a professional software engineer, but an artist and researcher; most of the software I develop comes from research context and artistic practice.

And I think it's awesome you developed and open source all these things, ScalaCollider by itself is a really cool piece of work, so thanks for that!

But F-bounded types were never ever on the table of being axed.

F-bounds are required for Java compat and heavily used by the standard library, so there's no way we can drop them. But we've already invested a lot of time and effort in implementing them as Martin said, and given that this issue tracker has ~600 issues and that only a few people work on the compiler internals, realistically we need to focus on the issues that people are most likely to hit, so we can't promise perfect support for the more obscure combinations of features. I understand that this is frustrating and if I could I would fix every bug, but my time is limited too!

[LPTK]

@Sciss

I believe you were departing from

trait Branch[T <: Exec[T]] {
  def next(implicit tx: T): Next[T]

  def nextOption(implicit tx: T): Option[Branch[T]] = next match {
      case Empty         => None
      case b: Branch[T]  => Some(b)
    } 
}

So clearly T cannot be Any.

I haven't looked at your codebase, but couldn't the next method return a Branch[Nothing]? This would work because of the variance of Next, but it would make nextOption lie by saying it returns an Option[Branch[T]] whereas it actually returns an Option[Branch[Nothing]].

[Sciss]

I think that's a moot argument. You could as well say there is a Some[Nothing] <: Some[X]. You cannot construct that because you cannot submit or return a value of Nothing.

[LPTK]

Nothing is just an example; it's not the only type that would work in this position. Any more specific subtype of Branch will do.

(Also, in the example at hand, there is no actual value of T being held by Branch, unlike Some, but that's beside the point anyways.)

[Sciss]

Any more specific subtype of Branch will do.

Yes but that's how covariance is supposed to work... If I hold Some(Branch()) it can always contain something more specific than Branch. And Empty is not a Branch. I don't see the point...

[abgruszecki]

@Sciss I believe LPTK is trying to convey that nextOption doesn't return an Option[Branch[T]], but an Option[Branch[_ <: T]].

[odersky]

If we refactor the code with my proposed algebraic subtyping encoding, the problem also goes away:

trait Exec[T]
sealed trait Child[+T]
sealed trait Next[+T] extends Child[T]
sealed trait Branch[T] extends Child[T] {
  def foo(x: Next[T & Exec[T]]): Unit = x match {
    case x: Branch[T] =>
  }
}
final class RightBranch[T] extends Next[T] with Branch[T]