Type "inference" for generics

[HosseinYousefi]

Simple example

Let's take this add method:

// In class Test
static public <T> T transfer(ArrayList<T> l, Stack<T> s) {
  while (!s.empty()) {
    l.add(s.pop());
  }
  return l.get(0); // just so it's not void
}

Right now, calling this in Dart is like this:

Test.transfer(Integer.type, intList, intStack);

Even though in Java, we're able to do

Test.transfer(intList, intStack);

and have it automatically infer the type parameter T.

We could try doing the same in Dart. Instead of passing T as the first ordered argument, we can pass it as an (in this case) optional type parameter.

static T transfer<T>(
  ArrayList<T> l,
  Stack<T> s, {
  JObjType<T>? $T,
}) {
  // ...
}

In the body of the function, we will have to have something like:

$T ??= (l.$type as $ArrayListType<T>).$T;
return $T.fromRef(...);

Also it's useful to have assertions making sure l.$type.$T and s.$type.$T are the exact same. This is because in Dart we could pass ArrayList<Integer> and Stack<Number>. T will be Number but we know that a Number cannot be added to an ArrayList<Integer>!

assert((l.$type as $ArrayListType<T>).$T == (s.$type as $StackType<T>).$T, '...');

The type parameter in this case looks like so:

graph TD;
  ArrayList--$T-->T;
  Stack--$T-->T;

Higher depths!

But they can be arbitrarily deep, for example if instead of ArrayList<T> we have ArrayList<HashMap<String, T>>:

graph TD;
  ArrayList--$T-->HashMap;
  HashMap--$K-->String;
  HashMap--$V-->T;
  Stack--$T-->T;

The generated code also gets more complicated:

assert((l.$type as $ArrayListType<HashMap<JString, T>>).$T.$V == (s.$type as $StackType<T>).$T, '...');

We'd also need k - 1 equality assertions for k arguments that have T type parameter. Of course, this gets more complicated when we have multiple type parameters.

Different variants

transfer method in the example above can only transfer elements of Stack<T> to an ArrayList<T>. We want to make this method more generic, so that we can transfer any Stack<U> to an ArrayList<T> where U <: T. Let's change the signature to allow this:

// In class Test
static public <T> T transfer(ArrayList<T> l, Stack<? extends T> s) {
  while (!s.empty()) {
    l.add(s.pop());
  }
  return l.get(0);
}

Now the assertion in Dart would have to be changed as well:

assert((l.$type as $ArrayListType<T>).$T.isSuperOf((s.$type as $StackType<T>).$T), '...');

? super T would be similar to ? extends T.

Lowest common ancestor type

Now let's say that we don't have any type T directly.

static public <T> T randomFirst(ArrayList<? extends T> l, Stack<? extends T> s) {
  if (random() % 2 == 0) {
    return l.get(0);
  }
  return s.get(0);
}

In this case $T should be the lowest common ancesstor of s.$type.$T and t.$type.$T. Take these classes:

graph TD;
  java.lang.Object--subclass-->A
  A--subclass-->B
  B--subclass-->C
  A--subclass-->D
  D--subclass-->E

Here Test.randomFirst(listOfC, listOfE) should have a type of A.

Supers and extends

What about a combination of super and extends?

static public <T> T setFirst(ArrayList<? super T> l, Stack<? extends T> s) {
  l.set(0, s.get(0));
  return s.get(0);
}

This should only work when l.$type.$T is a supertype of s.$type.$T.

Conclusion

As you can see, there are many cases that need to be thoroughly tested.

Performance

The type graph is not going to be super deep. So naive implementation does the job in most cases.

We're using the operations of type is_ancestor? and lowest_common_ancestor a lot. So keeping not only the supertypes but also jumps with powers of two (parent, grandparent, grandparent of grandparent, ...) can improve the performance in cases where we have many layers of subclass/superclasses.