Should inference take variance into account to resolve under-constrained inference problems?

[leafpetersen]

During type inference for covariant classes (currently all classes), we may be solving for a type variable X, and end up with a constraint of the form S <: X <: T where S is a subtype of T, but S is not equal to T. For example, we might have int <: X <: Object, which indicates that any of int, num, or Object are valid solutions to the inference problem (since X must lie in the range between int and Object).

Currently, we heuristically choose the lower bound, when present. That is, given the above constraints, we will choose int. An intuition behind this is that if class C has properly covariant type parameter X, then choosing C<int> will work in all cases that choosing C<Object> would, but not vice versa.

This intuition suggests that it might be appropriate to reverse this heuristic for contravariant type parameters, since if class C has properly contravariant type parameter X, then choosing C<Object> will work in all cases that choosing C<int> would work, but not vice versa.

As a concrete example, consider the following:

class Render<in T> {
  String Function() _default;
  String Function(T) _render;
  Render(T x, String Function(T) f){
    _default = () => f(x);
    _render = f;
  }
  void test() {
    print(T);
  }
  String render([T argument]) {
    if (argument == null) {
      return _default();
    }
    return _render(argument);
  }
}

void main() {
  // Is this an Object renderer or an int renderer?
  var a = Render(3, (Object x) {}); // -> int <: T, T <: Object
  // Is this a num renderer or an int renderer?
  var b = Render(3, (num x) {}); // -> int <: T, T <: num

  a.test(); // prints "int" currently
  b.test(); // prints "int" currently

  //  Render<String> s = a; // Rejected if we infer Render<int>, but would work fine if we infer Render<Object>
  //  Render<num> n = b; // Rejected if we infer Render<int>, but would work fine if we infer Render<num>
}

As a data point, Kotlin does not seem to change the direction of the heuristic. The program below emits an error indicating that CheckInference<Int> is the inferred type of ci. I haven't checked what Scala does. I'm not sure this comes up in C#, since only interfaces have variance there.

class CheckInference<in T> {
    constructor(x : T, f : (a : T) -> String) {
    }
    fun foo(x : T) {}
}
fun main(args: Array<String>) {
    val integer : Int = 3;
    val number : Number = 3.7;
    val ci = CheckInference(integer, {x : Number -> "hello" })
    ci.foo(number);
}

cc @eernstg @munificent @lrhn @kallentu