dart-lang / dart-lang/language

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

Open
#658 0 comments 0 reactions 0 assignees View on GitHub
variance
Dominant language
TeX
Stars
2.9k
Forks
239
Avg merge
2d 18h
Merged PRs (30d)
14

Description

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` will work in all cases that choosing `C` 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` will work in all cases that choosing `C` would work, but not vice versa.

As a concrete example, consider the following:

```dart
class Render {
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 s = a; // Rejected if we infer Render, but would work fine if we infer Render
// Render n = b; // Rejected if we infer Render, but would work fine if we infer Render
}
```

As a data point, Kotlin does not seem to change the direction of the heuristic. The program below emits an error indicating that `CheckInference` 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.

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

cc @eernstg @munificent @lrhn @kallentu

Contributor guide

Open the contributing guide

Research direction

Start with the Dart and Kotlin inference examples in the issue, then review the language specification's rules for variance and under-constrained type inference. Done means reaching and documenting a decision on whether inference should account for variance, including the expected result for the provided Render examples.

Written by the indexing model from the issue text.

Assessment

Tech stack
dart, kotlin
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.