dart-lang / dart-lang/language
Should inference take variance into account to resolve under-constrained inference problems?
- 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
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