A trick for invariant generics in Sorbet

There’s a neat trick for using generic methods to get around some of the limitations that invariant type members in generic classes carry.

The problem I’m trying to solve:

The solution is to change the parameter type from Box[Numeric] to the more generic Box[T.all(T.type_parameter(:Elem), Numeric)].You’ll recognize this type (rather verbose) type as typical of a method which wants to place bounds on generic methods.

At this point, let’s just look at code.

Statement of the problem

Here’s our mutable, invariant Box class:

class Box
  extend T::Sig
  extend T::Generic

  # Needs to be invariant: this type supports reading
  # and writing the `val` field
  # (appears in both input and output positions)
  Elem = type_member

  sig { params(Elem).void }
  def initialize(val)
    @val = val

  sig { returns(Elem) }
  #             ^^^^ output position

  sig { params(Elem).returns(Elem) }
  #                 ^^^^ input position

A method which operates on Box[Numeric] is allowed to do things like this:

sig { params(Box[Numeric]).void }
def mutates_numeric_box(box)
  # Can call arbitrary Numeric methods:
  raise unless box.val.zero?

  # Can set the value of the box to any Numeric,
  # regardless of what was in it before.
  box.val = (1 / 2r)
  #         ^^^^^^^^ instance of Rational

Recall that because of invariance, Sorbet has to reject things like this:

complex_box = Box[Complex].new(3 + 4i)
#                   ^^^^^^^^^^^ ❌ Box[Complex] is not a subtype of Box[Numeric]
radius = complex_box.val.polar.fetch(0)
#                        ^^^^^ runtime: 💥 Method `polar` does not exist on `Rational`

Sorbet must report an error on the call to mutates_numeric_box: after the call, Sorbet still thinks that complex_box has type Box[Complex] but it actually holds a Rational value. Allowing the program to continue is disastrous, and the program crashes with an exception on the call to polar on the next line.

It’s frustrating because the only way to get from a Box[Complex] to a Box[Numeric] (so that we can call this method at all) is to make an entirely new box, with an explicitly wider type:

numeric_box = Box[Numeric].new(complex_box.val)

… which is annoying on its own (imagine having to do this for every call to mutates_numeric_box!) but having done this, there’s no way to safely recover the fact that this Box[Numeric] started with a Complex. That fact has been forgotten.

What we can do instead, and what we give up

We can define our method using type_parameters (with a pseudo bound), which allows being called with Box[Complex], but places more constraints on what we’re allowed to do inside the method itself.

sig do
      Box[T.all(T.type_parameter(), Numeric)],
      T.all(T.type_parameter(), Numeric)
def mutates_generic_numeric_box(box, elem)
  initial_value = box.val

  # Can still call arbitrary Numeric methods:
  raise unless box.val.zero?

  # CAN'T set val to an arbitrary Numeric value
  # (It might not have been a Box that holds strings!)
  box.val = (1 / 2r)
  #          ^^^^^^ ❌ Rational is not a subtype of
  #                    T.all(T.type_parameter(:Elem), Numeric)
  #                    (because Rational is not a subtype of
  #                    T.type_parameter(:Elem))

  # ... but we CAN set val to a user-provided value:
  box.val = elem

  # ... and we CAN set val to its original value:
  box.val = initial_value

Note the new constraints on this implementation. We’re no longer able to overwrite val with an arbitrary Numeric value, like we could before with Rational. It’s not like we can’t set this field at all: we just need something with the right type. As I discuss in Sorbet, Generics, and Parametricity, this limits us to only set val to something we’ve been given as an argument. In our case, we’ve been given box.val and elem—those are the only two things we’re allowed to assign to val.

This is… not all that limiting in practice? Especially considering that it means we’re now allowed to use subtyping at the call site:

complex_box = Box[Complex].new(3 + 4i)
mutates_generic_numeric_box(complex_box, 4 + 3i) # ✅
radius = complex_box.val.polar.fetch(0)          # ✅

The only real tradeoff with this approach is that the generic signature with type_parameters is quite verbose.I have some ideas for what the new syntax should be, it’s mostly just an open question of whether the feature should be more or less syntactic sugar for the current syntax with T.all and have bad error messages, or whether we should expand Sorbet’s type system to track bounds on type parameters, possibly introducing uncaught bugs.

Verbosity aside, the tradeoffs which limit what kinds of method implementations are allowed are not typically show-stopping limitations in real-world code.