Unsound static type in kernel AST when function type is returned

[alexmarkov]

Consider the following code:

abstract class A<T> {
  void Function(T) get foo;
}

class B implements A<int> {
  void Function(int) get foo => (int x) => print(x);
}

void main() {
  A<num> a = B();
  final f = a.foo;
  f(3.14);
}

Kernel:

  static method main() → void {
    foo::A<core::num> a = new foo::B::•();
    final (core::num) → void f = a.{foo::A::foo}{(core::num) → void} as{TypeError,CovarianceCheck} (core::num) → void;
    f(3.14){(core::num) → void};
  }

CFE inserts as check to ensure soundness at run time. However, InstanceGet node a.{foo::A::foo}{(core::num) → void} is typed incorrectly - it has (core::num) → void static type already, but at run time it can actually return (core::int) → void. This typing is causing problems as TFA currently trusts static types.

@johnniwinther Is it possible to correct this static type, or somehow distinguish AST nodes which getStaticType() cannot be trusted?

[johnniwinther]

This is an (unfortunate) unsoundness inherent in Dart and the reason for why we have the CovarianceCheck AsExpression. Currently there is no way to distinguish nodes that produces this unsound static type, other than that they are the operand of such a CovarianceCheck AsExpression.

Would it be helpful for you if we marked these nodes directly, as well as having the CovarianceCheck AsExpression?

[eernstg]

@alexmarkov, here's another perspective on the same topic. I understand that this issue may be mostly about the Kernel code which is emitted for the given example, but I can't help commenting on the language perspective.

You might want to keep an eye on sound variance support and possibly also on "non-covariant members".

The point is that the declaration of A.foo is inherently dangerous because it is a non-covariant member as defined in that issue: It has a declared type (for a method or a getter that's: return type) where a type variable of the enclosing class/mixin occurs in a position which isn't covariant. In this case it is T which is used as a parameter type of a function type, and that is a contravariant position.

I've been pushing for feedback on this situation: #59050. This is a proposal for a lint which would flag declarations like A.foo. That should make it safe and convenient to adopt a policy that we don't have non-covariant members in the first place.

Alternatively, if you really want to use a return type like void Function(T) for a getter, you can define the class differently such that there is no need for run-time type checks. In particular, the class would usually be invariant in T (that's where sound variance comes up).

// `--enable-experiment=variance`

abstract class A<inout T> { // `in` would actually suffice in this case.
  void Function(T) get foo;
}

class B implements A<int> {
  void Function(int) get foo => (int x) => print(x);
}

void main() {
  A<int> a = B(); // Must be `A<int>`, it's a compile-time error with `A<num>`.
  final f = a.foo;
  // f(3.14); // Compile-time error.
  f(314); // OK.
}

With this, A<int> is no longer a subtype of A<num>, and hence we never get into the situation where a variable of type A<num> refers to an object of type B or A<int>. This also implies that f(3.14) is a compile-time error. But an invocation like f(314) is fine (accepted at compile time, and safe at run time).

Dart doesn't yet support sound variance, but we can emulate invariance using a type alias. So we'll make A an alias that extends the list of type arguments (such that we can know for sure which type arguments are passed to the "real" class which is now called _A).

References (such as implements A<int> in the declaration of B, and the declared type of a variable in main, and instance creations like A(), if any) will now use the type alias.

typedef Inv<X> = X Function(X);
typedef A<X> = _A<X, Inv<X>>;

abstract class _A<T, Invariance extends Inv<T>> {
  void Function(T) get foo;
}

class B implements A<int> {
  void Function(int) get foo => (int x) => print(x);
}

void main() {
  A<int> a = B();
  final f = a.foo;
  // f(3.14); // Compile-time error.
  f(314); // OK.
}

[alexmarkov]

@johnniwinther In my pending CL I added a workaround to test if return type of an interface target is FunctionType and ignore static type in such a case. It seems like a temporary patch and I'm not sure it covers all cases where static type is incorrect (and also probably too conservative in cases where it is correct).

Currently there is no way to distinguish nodes that produces this unsound static type, other than that they are the operand of such a CovarianceCheck AsExpression.

I can probably test parent node if it is a reliable / accurate / recommended approach. Maybe something like

  final parent = node.parent;
  if (parent is AsExpression && parent.isCovarianceCheck) {
    // Do not trust node.getStaticType()
  }

But something more explicit in the AST would be more robust (and would not rely on parent pointers which may be removed in future).

Would it be helpful for you if we marked these nodes directly, as well as having the CovarianceCheck AsExpression?

Yes, an additional flag on all invocation nodes which can have unsound static type would help. Alternatively, maybe CFE could just replace return type of an invocation node (InstanceGet / InstanceInvocation) with Function / dynamic when inserting a CovarianceCheck AsExpression? That would make static types sound and would not require additional flags.

[alexmarkov]

@eernstg Unfortunately sound variance is not there yet. The code above is a correct Dart code which should be supported by Dart implementations. Hopefully such code would trigger a compile-time error when sound variance arrives and eventually we will be able to remove CovarianceCheck AsExpression and any code added to fix this soundness issue. But for now (and maybe as long as we support current and older language versions) Dart implementations should still support this case.

[eernstg]

Right, @alexmarkov, you're considering how to deal with a caller-side check (that is, a CovarianceCheck AsExpression) which is given. So you don't have the option to consider programs that are written differently (such that the caller-side check isn't generated in the first place), you need to deal with the program exactly as written. So my comments were basically irrelevant. ;-)

However, we could still consider going one step in the direction of sound variance without adding it to the language: In the situation where a caller-side check has been performed and didn't throw, you will basically be able to conclude that the given object has an invariant type rather than the dynamically-checked-covariant type that it has according to the surface language.

For example, a successful caller-side check could be used to promote an instance of type A<num> to the type A<exactly num>. This kind of promotion could take place without disturbing the surface language at all (nobody would see it, or need to know), but for a variable v of type A<exactly num> there would not be a need to perform a caller-side check when v.foo is evaluated, not even in the situation where it is possible that v.foo has been modified after the caller-side check, or it's a getter that could return different results on each invocation.

abstract class A<T> {
  void Function(T) get foo;
  void Function(T, T) get bar;
}

class B implements A<int> {
  void Function(int) get foo => (int x) => print(x);
  void Function(int, int) get bar => (int x, int y) => print(x + y);
}

void main() {
  A<num> a = B();
  a.foo(3.14); // Promote `a` to `A<exactly num>`, or throw.
  while (true) {
    a.bar(14, 18); // No dynamic checks needed, `a` still has type `A<exactly num>`.
  }
}

Unfortunately, the test that the run-time type of o is A<exactly num> (more precisely, it is a type R such that R <: A<num> and R <: A<S> implies that num <: S) is a tiny bit too strict: We can actually have a situation where the caller-side check succeeds, but the holder does have a type that involves covariance (so a cast to A<exactly num> would fail).

class A<X> {
  void Function(X) foo;
  A(this.foo);
}

void main() {
  A<num> a = A<int>((num n) {});
  a.foo; // Succeeds, in spite of covariance `A<int> <: A<num>`.
}

This means that we can't just rush ahead and use the check like is A<exactly num>, but we can at least do something like the following:

void main() {
  A<num> a = B();
  // Compiler-generated local variable; only the compiler can test for `A<exactly num>`.
  var aIsCovariant = a is! A<exactly num>;
  a.foo(3.14); // Dynamic check performed if and only if `aIsCovariant`.
  while (true) {
    a.bar(14, 18); // Dynamic check performed if and only if `aIsCovariant`.
  }
}

PS: Doesn't the VM already keep track of invariance in some cases? Do we already have much of the machinery needed to do these things?

[johnniwinther]

I'll update the nodes that provide the unsound static type to use the sound static type (approximation) suggested in dart-lang/language#297. This should hopefully make Expression.getStaticType return sound static types in all cases.