finish covariance checks for generic types

[vsmenon]

From @jmesserly on May 1, 2015 20:9

we need to add covariance checks for parameters, e.g. List<E>.add ... given

class Foo<T> {
  T _t;
  add(T t) {
    _t = t;
  }

  forEach(void fn(T t)) {
    // No check needed for `fn`
    fn(_t);
  }
}

class Bar extends Foo<int> {
  add(int x) {
    print('Bar.add got $x');
    super.add(x);
  }
}
main() {
  Foo<Object> foo = new Bar();
  foo.add('hi'); // should throw
}

currently I'm adding something simple to JS codegen, but it adds extra checks (Foo.forEach) and it misses checks (Bar.add). Also ideally we'd compute this earlier, in checker/coercion reifier.

Copied from original issue: dart-archive/dev_compiler#161

[vsmenon]

From @jmesserly on February 11, 2016 20:7

So, thinking about this again, now that I understand better how types work in Analyzer:

What we want to do is instantiate Foo<T> to its upper bound (edit: meant upper, not lower :) ), look up our base method type Mb and our own method type Md, then for each parameter type Pb_i and Pd_i, see if Pb_i <: Pd_i. If that is not the case, we need a check for parameter i.

(Incidentally: that's the same logic we'd use for covariant overrides, if we allow opt-in to that feature. The extra step here is we need to instantiate our base generics as their lower bounds. I'm assuming that strong mode will already disallow instantiation where it does not match the lower bound, e.g. given Rectangle< T extends num > it will not be allowed to instantiate that with dynamic.)

[vsmenon]

From @leafpetersen on February 11, 2016 21:21

I'm not sure I follow this. What lower bound do you mean, when you say "instantiate Foo<T> to it's lower bound"?

[vsmenon]

From @jmesserly on February 11, 2016 21:31

Haha, oops, I meant upper bound :)

[vsmenon]

From @jmesserly on February 11, 2016 21:37

In other words: Foo<Object>. The covariance problem happens because Foo<int> <: Foo<Object>, which means the static type system will implicitly allow call sites like: Foo<int>.add <: Foo<Object>.add, or in other words, int -> void <: Object -> void, which is not what we want. Replacing the type parameter with its upper bound would be an easy way to find those soundness violations.

(We could certainly look at each parameter and see if the type parameter T occurs in certain positions in the base method's parameters. I thought subtype might be an easy way to get the same effect.)

[vsmenon]

From @jmesserly on February 11, 2016 21:40

Another example:

class C<T extends num> {
  add(T t) {}
}
class D extends C<int> {
  add(Object obj) {}
}

Here we wouldn't need a check on D.add, because: {num/T}T <: Object.

[vsmenon]

From @leafpetersen on February 11, 2016 22:3

Ah, I see. Yes, I think that makes sense, and could be a nice way to do it. You may need to think about what exactly the base method you compare to should be. For example:

class C<T> {
  add(T t) {}
}
class D extends C<int> {
  add(int i) {}
}
class E extends D {
  add(num obj) {}

Here both overrides need a check, but if you only compare the type of E.add against D.add I don't think you'll see it. It's possible it's always sufficient to check against the root definitions in the hierarchy (presumably there can be multiple roots). Might be worth thinking through the corner cases though.

[vsmenon]

From @jmesserly on February 11, 2016 22:35

Chatted with Leaf, another thing we should consider:

It would be nice if Analyzer knows about these implicit downcasts, so we can go through our normal warning logic. For example Iterable<E> or E fn() are downcasts that are likely to fail (warning:DOWN_CAST_COMPOSITE).

[vsmenon]

From @jmesserly on May 9, 2016 23:15

@rakudrama noticed another bug with the currently implemented logic -- it adds checks inside inner lambda, so for example:

class C<T> {
  Iterable<T> iter;
  m() {
    return iter.any((i) => i != null);
  }
}

there's a check added inside the lambda to assert that i is a T which is not necessary.

[vsmenon]

From @leafpetersen on May 17, 2016 17:48

https://codereview.chromium.org/1988613006/ addresses the unnecessary checks inside of lambdas, and also eliminates checks when the type parameter is only used covariantly.

[jmesserly]

#27269 has another example that we should add as a test case.

[jmesserly]

edited subject; the issue here is for covariance in generic types & making sure we have the right checks in place for soundness. These checks are inside the method, on the parameter, when the parameter type needs a check for soundness.

[jmesserly]

This also includes fields, e.g.

class C<T> { T x; }
main() {
  C<Object> c = new C<int>();
  c.x = 'hello'; // should throw
}

[leafpetersen]

See also test/language_strong/covariant_subtyping* . We're currently failing several of these.

[jmesserly]

I split one of these out based on our discussion: #29295

[jmesserly]

Note in addition to parameters, there's also returning function types:

typedef F<T> = Function(T);

class C<T> {
  T _t;
  T getT() => _t;
  F<T> setterForT() {
    return (T t) { _t = t; };
  }
}

main() {
  C<int> cInt = new C<int>();
  C<Object> cObj = cInt;
  cObj.setterForT()('hello');
  print(cInt.getT().isEven);
}

VM catches this in checked mode (and throws nSM in prod mode). DDC incorrectly prints null due to the unsoundness. Chatting with @leafpetersen it sounds like the check should be placed at the call site. So desugared it is something like:

main() {
  C<int> cInt = new C<int>();
  C<Object> cObj = cInt;
  (cObj.setterForT() as F<Object>) ('hello'); // cast fails
  print(cInt.getT().isEven);
  // this would work:
  (cInt.setterForT() as F<int>)(42); // cast succeeds, set succeeds
}

EDIT: also I believe we only need to look at the declared interface type we're calling through at the caller side, because the unsafety is a property of the interface we access it through. Need to prove that, though.

EDIT2: here's another example: #29912 (comment)

[jmesserly]

Another fun one: when the covariant check is needed for a superclass or mixin method.

e.g.

class B {
  int _t = 0;
  add(int t) {
    _t += t;
    print(_t);
  }
}

abstract class I<T> {
  add(T t);
}

class C extends Object with B implements I<int> {}

class D extends B implements I<int> {}

main() {
  I<Object> i = new C();
  I<Object> j = new D();
  i.add('hi');
  j.add('there');
}

results

$ ddc test3.dart
0hi
0there
$ dart -c  test3.dart
Unhandled exception:
type 'String' is not a subtype of type 'int' of 't' where
  String is from dart:core
  int is from dart:core

[jmesserly]

More fun: generic method bounds!

abstract class I<T> {
  add<S extends T>(S t);
}
class C implements I<num> {
  num _t = 0;
  add<T extends num>(T t) {
    _t += t;
    print(_t);
  }
}
main() {
  I<Object> i = new C();
  i.add('hi');
}

edit: DDC prints 0hi again, illustrating the lack of soundness

[jmesserly]

Making good progress on this. I'm now looking into if we can do caller side checks for private fields -- or at least, eliminate the callee side checks if they aren't needed. There's some SDK fields that could benefit (a bunch of Iterator classes have a _current, HashMap related classes have K/V typed fields, stream subscriptions and controllers, etc)

[jmesserly]

we should also add a test for the example in #29915