Refactor tree type parameters

[odersky]

Compiler version

All 3.x versions

Minimized example

The modelling of ASTs can be improved by exploiting the -Yexplicit-nulls setting, which is enabled in the dotc build.
There are the following major design criteria for AST trees, which should be kept:

• There are untyped trees and typed trees.
• The kind of a tree is represented by a type parameter or abstract type T.
• For typed trees T = Type and for untyped trees T = Untyped where Untyped is either Null or Nothing.
• Typed trees can be used where untyped trees are required, forgetting the type annotations.
• The typeOpt method on trees returns a T, i.e. either bottom type or a Type.
• The tpe method on trees returns a Type and will fail (ideally at compile time, but currently at runtime) if the tree is untyped.

When dotc was first designed, we fulfilled the criteria by defining type Tree like this:

  abstract class Tree[-T >: Null] ...

That made sure that typed trees Tree[Type] are a subtype of untyped trees Tree[Null], since Null was a subtype of Type. But with explicit nulls, that's no longer true. So we changed the bottom type from Null to Nothing.

Nevertheless, there's some awkwardness:

First, the tpe method on trees is variance incorrect. It is defined like this:

    final def tpe: T @uncheckedVariance = ...

Second, we can write

    val t: Type = tree.tpe

without problem even if tree is an untyped tree, since its tpe method returns Nothing, which conforms to Type.

It looks like we can get a sound system with better static checking if we model Tree instead like this:

   abstract class Tree[+T <: Type | Null]
   object untpd:
     type Tree = Tree[Type | Null]
   object tpe:
     type Tree = Tree[Type]

It's going to be a big change in the sense of number of lines changed, but it would make things clearer. So I think we should do it before going into an LTS.

[dwijnand]

I have a patch that does most of this (which I worked on as a good outcome from banning "an Old Paradox", #14820).

[odersky]

Is #14820 correct? I don't see a connection.

I have done the necessary changes now. It was surprisingly easy. PR forthcoming.

[dwijnand]

The connection is that if that enforcement is in place you can trust that if a tree: Tree[T] is an instance of class Select, so Select[T2], then T2 is subtype/supertype of T (depending on which variance Tree has on T). Today we can't depend on that, and we should be getting unchecked warnings on those, because of the remote possibility of a paradoxical subclass, as described in #11834.

[odersky]

@dwijnand Ah yes, that makes sense.