Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Bounds on generic methods should be treated invariantly in subtyping #29014

Closed
leafpetersen opened this issue Mar 9, 2017 · 13 comments

Comments

@leafpetersen
Copy link
Member

commented Mar 9, 2017

Currently, the analyzer treats generic method bounds contra-variantly for sub-typing purposes. For example, the following is allowed:

class A {
  void foo<T extends num>() {}
}

class B extends A {
  void foo<T extends Object>() {}
}

Per language team decision, this should be changed to require that bounds be equal.

@leafpetersen leafpetersen added this to the 1.23 milestone Mar 9, 2017

@leafpetersen leafpetersen self-assigned this Mar 9, 2017

@leafpetersen leafpetersen removed this from the 1.23 milestone Mar 9, 2017

@leafpetersen leafpetersen added this to Language implementation in 2.0 language Mar 2, 2018

@leafpetersen leafpetersen added this to the Dart2Stable milestone May 18, 2018

@leafpetersen leafpetersen removed their assignment May 18, 2018

@MichaelRFairhurst MichaelRFairhurst self-assigned this May 21, 2018

@MichaelRFairhurst

This comment has been minimized.

Copy link
Contributor

commented May 21, 2018

Clarification, does this affect function subtyping in general?

Function<T extends num>() fn = <T extends int>(){};

It seems like this is already an error, so I'm assuming this is truly limited to method overrides.

@MichaelRFairhurst

This comment has been minimized.

Copy link
Contributor

commented May 21, 2018

this is also currently not an error:

class C extends A {                                                              
  void foo<T>() {                                                                
    return foo<String>();                                                        
  }                                                                              
}

Would the error be at override, or would it infer the type parameter to have a bound, in which case the error would be at the type application site of foo?

@leafpetersen for these questions

@MichaelRFairhurst

This comment has been minimized.

Copy link
Contributor

commented May 21, 2018

Oops, had tested contravariance before. Function type's type parameters are currently covariant inside the type system, should that change too?

Function<T extends num>() fn = <T extends int>(){}; // OK
@leafpetersen

This comment has been minimized.

Copy link
Member Author

commented May 21, 2018

@MichaelRFairhurst I'm confused about the results you claim to see above. Just tested with bleeding edge analyzer and I see covariance as an error, contra-variance currently ok:

void main() {
  Function<T extends num>() fn = <T extends int>(){}; // Error
  Function<T extends int>() fn2 = <T extends num>(){}; // Currently OK, should be error.
}

The contra-variant case should also be an error.

This applies to all places that subtype checking is done (override, assignment, etc).

This example:

class C extends A {                                                              
  void foo<T>() {                                                                
    return foo<String>();                                                        
  }                                                                              
}

I don't understand. There is no subtype checking involved here? In any case, this is valid code: Dart has polymorphic recursion.

@MichaelRFairhurst

This comment has been minimized.

Copy link
Contributor

commented May 21, 2018

I was confused at the results I claimed to see! And I figured out why. I had a copy/paste error. The code I said 'is already an error" and the code I implied wasn't an error, are the same code. Then I based my question on the wrong code snippet. Anyways, I am seeing the same behavior as you. And also, that answers my question. Easy to solve for all cases.

The question on the last example refers to class A in the original issue description. The question mostly whether the bound of T in C.foo should be inferred. It could be considered unbounded/dynamic, in which case its an invalid override of A.foo. Or it could (and I'm assuming it doesn't!) infer the bound to be num as it is declared on A.foo.

@MichaelRFairhurst

This comment has been minimized.

Copy link
Contributor

commented May 22, 2018

I had a prototype in an hour or so, but this may be another one of those rabbit hole bugs.

there was an issue in function type equality not present in function type subtype code. The == operator checks that the typeArguments of two functions are equal, where the subtype code just checks that their typeFormals match as well as their parameters & return type.

I could be mistaken, but it seems that the typeArguments should not be checked since those include values bound to outer contexts. (unless the goal is to say, "these are the same type in the same context". That said, == is used in a number of places in TypeSystem that makes me think that is NOT the case).

The problem is that having equality be too strict means that switching from co to invariance creates bugs, unless I can fix that equality.

Its easy to fix, but I'm getting at least one very strange failure where code seems to depend upon the "broken" (if it is) equality behavior. Its in code that I've worked on before, where a robust solution was not easy and I had to sort of create some compromises.

I don't think any of these failures will be permissible to leave in. So I'm puzzling over what an "incremental" rollout would be, and in the meantime will try to solve that test failure without creating others.

Its worth noting that the test failure is in summary linking, so my understanding is that language tests don't really provide coverage there. If I can't solve that test case, I'll mark it @failingTest and do a test roll.

@leafpetersen

This comment has been minimized.

Copy link
Member Author

commented May 22, 2018

Or it could (and I'm assuming it doesn't!) infer the bound to be num as it is declared on A.foo.

Right, no override inference for bounds, so this is rejected.

@leafpetersen

This comment has been minimized.

Copy link
Member Author

commented May 22, 2018

there was an issue in function type equality not present in function type subtype code.

Function type equality is way sketchy in the analyzer and probably needs some revisiting.

I could be mistaken, but it seems that the typeArguments should not be checked since those include values bound to outer contexts.

I think you're referring to the analyzer's lazy substitutions? You definitely need to distinguish between the same syntactic type with different replacements for free variables. For example, this program needs to be rejected:

class A<T> {
  void foo<S extends T>() {}
}

class B<T> {
  void foo<S extends T>() {}
}
 void main() {
   var f = A<int>().foo;
   var g = B<String>().foo;
   f = g;
 }
@MichaelRFairhurst

This comment has been minimized.

Copy link
Contributor

commented May 22, 2018

maybe @jmesserly can give some insight into the equality stuff.

In the following example,

class A<T> {
  void foo<R extends void Function(T)>() {}
}
class B extends A<Num> {
  void foo<R2 extends void Function(Num)>() {}
}

if I check that the bounds are equal, I get "false." The reason why is that A.foo.R.bound.typeArguments has a length of 2: [R, T], and B.foo.R2.bound.typeArguments has a length of 1: [R2]. Neither of these values are related to the equality of the two Function types though.

It already checks that typeFormals are of equal length, and uses relateTypeFormals to get parameters with which to instantiate the functions and then ensure that those instantiated functions are equal. I believe that means that at that point, you only need to check that their parameters & return types are compatible. Reading through the docs on typeFormals (and the code) kind of bounces around in my brain, its explanations are a mix of theory an practice that I haven't quite grokked yet, but it seems like typeFormals eagerly finds the free variables specific to the type in question, so that is what I think I want to be using.

I suppose I may need to alter the code of relateTypeFormals to ensure that it doesn't try to do GLB on the parameters. Hopefully if so it results in simpler logic.

@jmesserly

This comment has been minimized.

Copy link
Contributor

commented May 22, 2018

I think the fix is something like this. Warning, untested code :)

Note that I'm not using operator == on the types. operator == does not implement equality for Dart 2 correctly. Also we want Object vs dynamic to be allowed. So we just do t1 <: t2 && t2 <: t1 to implement invariance. Not the most efficient way, but it should get the job done. Maybe we need a fast path for when all the bounds are emitted (the most common case).

diff --git a/pkg/analyzer/lib/src/dart/element/type.dart b/pkg/analyzer/lib/src/dart/element/type.dart
index 5d91528495..f752be1ad7 100644
--- a/pkg/analyzer/lib/src/dart/element/type.dart
+++ b/pkg/analyzer/lib/src/dart/element/type.dart
@@ -1175,8 +1175,8 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
 
   /**
    * Compares two function types [t] and [s] to see if their corresponding
-   * parameter types match [parameterRelation] and their return types match
-   * [returnRelation].
+   * parameter types match [parameterRelation], return types match
+   * [returnRelation], and type parameter bounds match [boundsRelation].
    *
    * Used for the various relations on function types which have the same
    * structural rules for handling optional parameters and arity, but use their
@@ -1184,14 +1184,20 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
    *
    * If [parameterRelation] is omitted, uses [returnRelation] for both. This
    * is convenient for Dart 1 type system methods.
+   *
+   * If [boundsRelation] is omitted, uses [returnRelation]. This is for
+   * backwards compatibility, and convenience for Dart 1 type system methods.
    */
   static bool relate(
       FunctionType t,
       DartType other,
       bool returnRelation(DartType t, DartType s),
       DartType instantiateToBounds(DartType t),
-      {bool parameterRelation(ParameterElement t, ParameterElement s)}) {
+      {bool parameterRelation(ParameterElement t, ParameterElement s),
+      bool boundsRelation(DartType bound2, DartType bound1,
+          TypeParameterElement formal2, TypeParameterElement formal1)}) {
     parameterRelation ??= (t, s) => returnRelation(t.type, s.type);
+    boundsRelation ??= (t, s, _, __) => returnRelation(t, s);
 
     // Trivial base cases.
     if (other == null) {
@@ -1209,7 +1215,7 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
     FunctionType s = other as FunctionType;
     if (t.typeFormals.isNotEmpty) {
       List<DartType> freshVariables =
-          relateTypeFormals(t, s, (s, t, _, __) => returnRelation(s, t));
+          relateTypeFormals(t, s, boundsRelation);
       if (freshVariables == null) {
         return false;
       }
diff --git a/pkg/analyzer/lib/src/generated/resolver.dart b/pkg/analyzer/lib/src/generated/resolver.dart
index 185d6d3489..84e7e4627c 100644
--- a/pkg/analyzer/lib/src/generated/resolver.dart
+++ b/pkg/analyzer/lib/src/generated/resolver.dart
@@ -6748,6 +6748,9 @@ class ResolverVisitor extends ScopedVisitor {
    */
   void _inferFunctionExpressionParametersTypes(
       Expression mayBeClosure, DartType mayByFunctionType) {
+    // TODO(jmesserly): remove this code and callers. It's doing
+    // "propagated type" inference for the Dart 1 type system.
+    assert(!strongMode);
     // prepare closure
     if (mayBeClosure is! FunctionExpression) {
       return;
diff --git a/pkg/analyzer/lib/src/generated/type_system.dart b/pkg/analyzer/lib/src/generated/type_system.dart
index d178f25039..ab376a17a8 100644
--- a/pkg/analyzer/lib/src/generated/type_system.dart
+++ b/pkg/analyzer/lib/src/generated/type_system.dart
@@ -646,18 +646,14 @@ class GenericInferrer {
 
     if (t1 is FunctionType && t2 is FunctionType) {
       return FunctionTypeImpl.relate(
-          t1,
-          t2,
-          (t1, t2) {
-            // TODO(jmesserly): should we flip covariance when we're relating
-            // type formal bounds? They're more like parameters.
-            return matchSubtype(t1, t2);
-          },
-          _typeSystem.instantiateToBounds,
+          t1, t2, matchSubtype, _typeSystem.instantiateToBounds,
           parameterRelation: (p1, p2) {
             return _matchSubtypeOf(p2.type, p1.type, null, origin,
                 covariant: !covariant);
-          });
+          },
+          // Type parameter bounds are invariant.
+          boundsRelation: (t1, t2, p1, p2) =>
+              matchSubtype(t1, t2) && matchSubtype(t2, t1));
     }
 
     if (t1 is FunctionType && t2 == typeProvider.functionType) {
@@ -1181,7 +1177,10 @@ class StrongTypeSystemImpl extends TypeSystem {
   /// - it allows opt-in covariant parameters.
   bool isOverrideSubtypeOf(FunctionType f1, FunctionType f2) {
     return FunctionTypeImpl.relate(f1, f2, isSubtypeOf, instantiateToBounds,
-        parameterRelation: isOverrideSubtypeOfParameter);
+        parameterRelation: isOverrideSubtypeOfParameter,
+        // Type parameter bounds are invariant.
+        boundsRelation: (t1, t2, p1, p2) =>
+            isSubtypeOf(t1, t2) && isSubtypeOf(t2, t1));
   }
 
   /// Check that parameter [p2] is a subtype of [p1], given that we are
@@ -1522,7 +1521,10 @@ class StrongTypeSystemImpl extends TypeSystem {
   /// Check that [f1] is a subtype of [f2].
   bool _isFunctionSubtypeOf(FunctionType f1, FunctionType f2) {
     return FunctionTypeImpl.relate(f1, f2, isSubtypeOf, instantiateToBounds,
-        parameterRelation: (p1, p2) => isSubtypeOf(p2.type, p1.type));
+        parameterRelation: (p1, p2) => isSubtypeOf(p2.type, p1.type),
+        // Type parameter bounds are invariant.
+        boundsRelation: (t1, t2, p1, p2) =>
+            isSubtypeOf(t1, t2) && isSubtypeOf(t2, t1));
   }
 
   bool _isInterfaceSubtypeOf(
@jmesserly

This comment has been minimized.

Copy link
Contributor

commented May 22, 2018

I made that diff by searching for all uses of FunctionTypeImpl.relate.

I also looked at FunctionTypeImpl.relateTypeFormals ... there's one use in checker.dart, but I think that use is correct. It's for figuring out runtime covariance checks. I think this example is still supported, so we still need that code in checker.dart:

  class C<T> {
    g<S extends T>() => <S>[];
  }
  class D extends C<num> {
    g<R extends num>() => <R>[];
  }
  main() {
     C<Object> c = new C<int>();
     c.g<String>(); // must throw for soundness
     c = new D();
     c.g<String>(); // must throw for soundness
  }
@MichaelRFairhurst

This comment has been minimized.

Copy link
Contributor

commented May 22, 2018

Ah, I like "isSubtypeOf(t1, t2) && isSubtypeOf(t2, t1)"! And great edge case with object/dynamic.

With this I can leave equality untouched which hopefully fixes that linking error if it depends upon equality being...what it is! Awesome response & response time @jmesserly!

@MichaelRFairhurst

This comment has been minimized.

Copy link
Contributor

commented May 22, 2018

Your code is awesome @jmesserly and passed all my tests locally. Up for review here, running trybots: https://dart-review.googlesource.com/c/sdk/+/56029

@dart-bot dart-bot closed this in 1d59ab2 May 24, 2018

2.0 language automation moved this from Language implementation to Done May 24, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
4 participants
You can’t perform that action at this time.