[RFC] Full Tuple and NamedTuple covariance

[HertzDevil]

This RFC is essentially the opposite of #10036.

A Tuple instance can be upcast to a larger Tuple, but not downcast to a smaller one:

{1}.as({Int32 | String}).as({Int32}) # Error: can't cast Tuple(Int32 | String) to Tuple(Int32)

Likewise, runtime type checks also fail:

{1}.as({Int32 | String}).is_a?({Int32}) # false

This ultimately comes from the fact that type filtering of Tuple instances is non-commutative, i.e. #2404 (comment).

I suggest that we make these examples work, because they are compatible with Tuple's built-in covariance rules. The same goes for NamedTuple instances up to equivalence. One consequence is the family of Tuple(T) instances have exactly the same subtyping relationships as the family of T, so the following example should also compile:

# neither overload is more specialized than the other, so
# their overload order is as written
def foo(x : {Int32 | Char}); end
def foo(x : {Int32 | String}); end

# dynamic dispatch occurs here
# argument's static type is {Char | String}, dynamic type is {String}
# first overload fails because {Int32 | Char} & {Char | String} == {Char}
# second overload succeeds because {Int32 | String} & {Char | String} == {String}
# there are no missing overloads because {Char} and {String} fully cover {Char | String}
foo({"" || 'a'})

Another consequence is two Tuple instances may have a common subtype even if neither is a subtype of the other:

class Foo; end
class Bar < Foo; end

x = {Foo.new, Bar.new}
y = x.is_a?({Bar, Foo}) ? x : nil # nil
typeof(y)                         # => (Tuple(Bar, Bar) | Nil)

[HertzDevil]

To be precise, there are at least 5 parts to implementing full Tuple covariance: (the rules for NamedTuples with the same sets of keys are defined analogously)

• Given the types Tuple(T1, T2, ..., Tn) and Tuple(U1, U2, ..., Un) with the same arity, their intersection is the Tuple instance whose generic type arguments are the pairwise intersections between the Tns and Uns; if the intersection doesn't exist for some pair of element types, the whole Tuple intersection is NoReturn. This is simply the dual of the union operator.
• Element-wise downcasts should be allowed. If U1, U2, ..., Un are subtypes of T1, T2, ..., Tn and at least one is a proper subtype, then given x : Tuple(*T), the expression x.as(Tuple(*U)) should compile and perform a downcast during runtime. (There is already some support for it because assignments to the same variable can trigger a tuple downcast.)
• Parameter restrictions should respect the intersection between Tuple instance types. This is fine if the restriction is already a supertype of the argument's type, but full covariance will enable downcasting or sidecasting scenarios such as def foo in the OP. The cover for Tuple(*T) is, roughly speaking, the cartesian product of the covers for each element type.
• Flow typing on the else-branches of if-expressions should work for Tuple types. Consider the case of subtracting one Tuple from another:

  # `!(Ti <= Ui)` for at least one `i`
  x = uninitialized Tuple(T1, T2, ..., Tn)
  typeof(x.is_a?(Tuple(U1, U2, ..., Un)) ? raise("") : x) # => Tuple(V1, V2, ..., Vn)

  Since the else-branch performs union reduction, most result types will simply be the original tuple again. The only exception is when Tuple(*T) and Tuple(*U) differ in exactly one element, and all others are equivalent. Then we have:

  # `!(Ti <= Ui)`, so `typeof(v)` is not `NoReturn`
  t = uninitialized Ti
  v = t.is_a?(Ui) ? raise("") : t
  
  x = uninitialized Tuple(T1, T2, ..., Ti, ..., Tn)
  typeof(x.is_a?(Tuple(T1, T2, ..., Ui, ..., Tn)) ? raise("") : x) # => Tuple(T1, T2, ..., typeof(v)..., Tn)

  The then-branch doesn't perform union reduction, so some extra work is probably needed to make the following pass:

  x = uninitialized Tuple(Int32 | String, Int32 | String)
  typeof(x.is_a?(Tuple(Int32, Int32)) || x.is_a?(Tuple(Int32, String)) ? raise("") : x) # => Tuple(String, Int32 | String)

  but at the same time, not produce NoReturn in the following:

  typeof(x.is_a?(Tuple(Int32, Int32)) || x.is_a?(Tuple(String, String)) ? raise("") : x) # => Tuple(Int32 | String, Int32 | String)

• Tuple instances should be supported in exhaustive case-expressions, where the exhaustive branches are defined similarly to the type cover (carterian product of the branches for each element). This would allow one to write:

  x = {1 || "", 1 || ""}
  case x # regular variable, not `TupleLiteral`
  in Tuple(Int32, Int32) # type name (literal form might not work if it invokes `Tuple#===(Tuple)`)
  in Tuple(Int32, String)
  in Tuple(String, Int32)
  in Tuple(String, String)
  end

Above all, the compiler should never instantiate all subtypes of a Tuple instance unless they are indeed used. This is so that we don't get 79 extra types generated from a 4-tuple of 3-element union types.

At the time of writing this I got the first 3 parts working.

[HertzDevil]

Bathroom thought: #10519 works because subtyping never compares generic arguments recursively, but they could manifest in fully covariant Tuples. (It is also never fixed for restrictions.)