Avoid overly conservative warnings about type testability in exhaustive matches

Scala Improvement Process
1

Greetings fellow Scala enthusiasts.

I came across a situation in which the compiler complains about the inability to perform a type test due to erasure, despite said erasure being actually inconsequential AFAICT. Consider the following:

sealed trait Tree[+T]:
  def map[U](f: T => U): Tree[U] = this match
    case n: Tree.Node[T] => Tree.Node(f(n.value), n.lhs.map(f), n.rhs.map(f))
    case _ => Tree.Leaf

object Tree:
  object Leaf extends Tree[Nothing]
  class Node[T](var value: T, var lhs: Tree[T], var rhs: Tree[T]) extends Tree[T]

The code presents a straightforward implementation of binary trees equipped with a map function intended to transform a Tree[A] to a Tree[B]. Unfortunately, the compiler will complain (with a warning) in the implementation of Tree.map because:

the type test for Tree.Node[T] cannot be checked at runtime because its type arguments can’t be determined from Tree[T]

I believe that in this situation the warning is not justified because I would expect that Tree.Node[T] is an upper bound for any value that is not Tree.Leaf.

Emitting a warning is a way to discourage users from doing something. Sadly, alternative solutions to my code are not necessarily desirable. To state the obvious, I am aware that I can get the above code to work by defining Tree.Node as a case class but I claim that there are valid use cases for using a good old class as in the above. For instance, I may want to define my class with the ability to be mutated in-place, or I’d like to avoid generating all the additional methods that come with a case class.

As a result, I think it would be useful if the compiler did not emit the warning, or if we had another way to match against the node case without exacting the contents of the node.

2

You could get this to compile without the warning by using @unchecked for the type parameter T:

sealed trait Tree[+T]:
  def map[U](f: T => U): Tree[U] = this match
    case n: Tree.Node[T@unchecked] => Tree.Node(f(n.value), n.lhs.map(f), n.rhs.map(f))
    case _ => Tree.Leaf

object Tree:
  object Leaf extends Tree[Nothing]
  class Node[T](var value: T, var lhs: Tree[T], var rhs: Tree[T]) extends Tree[T]

In this case it is safe to do so, because we know that a Tree[T] is either a Tree.Node[T] or a Tree.Leaf.

3

@unchecked on such a type parameter is basically an asInstanceOf. That doesn’t count as a real solution. :wink:

4

Is it sound though? With Node being invariant, and tree being covariant, the pattern match would allow casting a Node[String] as a Node[Object] which is not a supertype.
Not sure if anything else prevents incorrect use afterwards … ?

2 Likes
5

Actually, thinking about this again, don’t you just want:

case n: Tree.Node[_ <: T] => ...
1 Like
6

That is a good point! With Node invariant and Tree covariant, it is definitely unsound. On a first reading I had assumed Node was covariant, like Tree.

The original test does compile without issue if both are invariant (but the Tree.Leaf is not a valid result, then).

Edit:

If they are both covariant, then the pattern matching works, but of course the vars in the class Node are not allowed.

So I think the compiler is doing everything it can already.

2 Likes
7

Indeed, the compiler is doing its best actually. Good catch @ragnar!

2 Likes