fix part of #25200, reject non-generic function subtype of generic function

pkg/analyzer/lib/src/generated/type_system.dart

Index: pkg/analyzer/lib/src/generated/type_system.dart
diff --git a/pkg/analyzer/lib/src/generated/type_system.dart b/pkg/analyzer/lib/src/generated/type_system.dart
index 16e0817f8943c8acd93f69453fda4f14d9367f7f..0bf7227cd044bd3add59015902b80ed1699327da 100644
--- a/pkg/analyzer/lib/src/generated/type_system.dart
+++ b/pkg/analyzer/lib/src/generated/type_system.dart
@@ -91,7 +91,11 @@ class StrongTypeSystemImpl implements TypeSystem {
           argumentTypes[i], correspondingParameterTypes[i]);
     }
 
-    return inferringTypeSystem._infer(fnType);
+    // We are okay inferring some type variables and not others.
+    //
+    // This lets our return type be as precise as possible, which will help
+    // make any type information resulting from it more precise.

[Leaf, 2016/02/09 21:29:25]

This is purely to make error messages better, right?  Presumably if we couldn't
find a solution, then the solution we get here is invalid, and we will get an
error somewhere else?  But by allowing the partial instantiation, we reduce the
errors to a fairly minimal set?  Will it be confusing to see errors in terms of
the partially instantiated types?  I'm feeling a little wobbly about what's
going on with this - maybe clarifying in comments, possibly with some examples
would be worthwhile.

[Jennifer Messerly, 2016/02/10 22:42:08]

Yes to all. :)
Let's say our function returns `Map<T, U>` and we inferred T := int but not U.

For example, you might see an error about `Map<int, dynamic>` instead of
`Map<dynamic, dynamic>`.

the `int` might be helpful, for example, if you did `map.keys` you'd get
`Iterable<int>`, which might avoid further errors.

I'm trying to avoid an error in one parameter causing more downstream errors
than it needs to.

This is definitely different from how we handle:

    foo(<T, U>(...) => ...);

if we fail to infer only T but not U, we leave it as a generic type.
I added a little bit, but it's definitely a heuristic we should get more user
experience/feedback with.

+    return inferringTypeSystem._infer(fnType, allowPartialSolution: true);
   }
 
   /**
@@ -118,61 +122,23 @@ class StrongTypeSystemImpl implements TypeSystem {
     var inferringTypeSystem =
         new _StrongInferenceTypeSystem(typeProvider, fnType.typeFormals);
 
-    // Add constraints for each corresponding pair of parameters.
-    var fRequired = fnType.normalParameterTypes;
-    var cRequired = contextType.normalParameterTypes;
-    if (cRequired.length != fRequired.length) {
-      // If the number of required parameters differs, we can't infer from this
-      // type (this will be a static type error).
+    // Since we're trying to infer the instantiation, we want to ignore type
+    // formals as we check the parameters and return type.

[Leaf, 2016/02/09 21:29:25]

I would suggest phrasing this comment differently.  I think what's going in is
that notionally what we are doing is instantiating fnType with fresh type
variables (or re-using it's existing type variables) to produce an instantiated
function type, and then unifying with the contextType to solve for the type
variables.  As an optimization, we can avoid allocating a new function type
simply by calling a version of the subtype function which ignores the type
formals and solving for the free type parameters of the body of the universal.

[Jennifer Messerly, 2016/02/10 22:42:07]

Hah, yes, indeed. :) It now works like that. More clear?

+    if (!inferringTypeSystem._isFunctionSubtypeOfRaw(fnType, contextType)) {
       return fnType;
     }
-    for (int i = 0; i < fRequired.length; i++) {
-      inferringTypeSystem.isSubtypeOf(cRequired[i], fRequired[i]);
-    }
 
-    var fOptional = fnType.optionalParameterTypes;
-    var cOptional = contextType.optionalParameterTypes;
-    if (cOptional.length > fOptional.length) {
-      // If we have more optional parameters that can be passed, we can't infer
-      // from this type (this will be a static type error).
-      return fnType;
-    }
-    // Ignore any extra optional arguments in F. We only need to pass arguments
-    // that could be passed to C.
-    for (int i = 0; i < cOptional.length; i++) {
-      inferringTypeSystem.isSubtypeOf(cOptional[i], fOptional[i]);
-    }
+    // Try to infer and instantiate the resulting type.
+    var resultType =
+        inferringTypeSystem._infer(fnType, allowPartialSolution: false);
 
-    var fNamed = fnType.namedParameterTypes;
-    var cNamed = contextType.namedParameterTypes;
-    for (var name in cNamed.keys) {
-      DartType fNamedType = fNamed[name];
-      if (fNamedType == null) {
-        // If F does not have a named parameter needed for C, then we can't
-        // infer from this type (this will be a static type error).
-        return fnType;
-      }
-      DartType cNamedType = cNamed[name];
-      inferringTypeSystem.isSubtypeOf(cNamedType, fNamedType);
-    }
-
-    // Infer from the return type. F must return a subtype of what C returns.
-    inferringTypeSystem.isSubtypeOf(fnType.returnType, contextType.returnType);
-
-    // Instantiate the resulting type.
-    var resultType = inferringTypeSystem._infer(fnType);
-
-    // If the instantiation is not a subtype of our context (because some
-    // constraints could not be solved), return the original type, so the error
-    // is in terms of it.
+    // If the instantiation failed (because some type variable constraints
+    // could not be solved, in other words, we could not find a valid subtype),
+    // then return the original type, so the error is in terms of it.
     //
-    // TODO(jmesserly): for performance, we could refactor this so the _infer

[Jennifer Messerly, 2016/02/08 21:54:27]

I went ahead and addressed this TODO. That's what `allowPartialSolution` is for.

-    // call above bails out sooner, and then we can avoid this extra check.
-    if (isSubtypeOf(resultType, contextType)) {
-      return resultType;
-    } else {
-      return fnType;
-    }
+    // It would be safe to return a partial solution here, but the user
+    // experience may be better if we simply do not infer in this case.
+    return resultType ?? fnType;
   }
 
   /**
@@ -319,15 +285,27 @@ class StrongTypeSystemImpl implements TypeSystem {
    */
   bool _isFunctionSubtypeOf(FunctionType f1, FunctionType f2,
       {bool fuzzyArrows: true}) {
-    if (!f1.typeFormals.isEmpty) {
+    if (f1.typeFormals.isNotEmpty) {
       if (f2.typeFormals.isEmpty) {
         f1 = instantiateToBounds(f1);
-        return _isFunctionSubtypeOf(f1, f2);
+        return _isFunctionSubtypeOfRaw(f1, f2, fuzzyArrows: fuzzyArrows);

[Jennifer Messerly, 2016/02/08 21:54:27]

I feel like we don't want to drop the fuzzyArrows flag here, but I might be
missing something.

(Also we can skip checking typeFormals again -- both will be empty at this point
-- that's why it calls straight into the "raw type" version)

[Leaf, 2016/02/09 21:29:25]

I really think this code would be better of being clearer and slightly
efficient.  e.g. something like:

if (f1.typeFormals.length != f2.typeFormals.length) {
  if (f1.typeFormals.isNotEmpty) {
    f1 = instantiateToBounds(f1);
 } else {
   return false;
}
return _isGenericFunctionSubtypeOf(f1, f2, fuzzyArrows: fuzzyArrows);

Yes, _isGenericFunctionSubtypeOf will have to recheck for type formals, but... I
think it's worth it for clarity.

[Jennifer Messerly, 2016/02/10 22:42:08]

Done as part of the Grand Refactoring :)

       } else {
         return _isGenericFunctionSubtypeOf(f1, f2, fuzzyArrows: fuzzyArrows);
       }
+    } else if (f2.typeFormals.isNotEmpty) {

[Jennifer Messerly, 2016/02/08 21:54:27]

this was the else case that I believe was missing

[Leaf, 2016/02/09 21:29:25]

Can you add a test for this in type_system_test.dart, probably in
test_genericFunction_generic_monomorphic ?

[Jennifer Messerly, 2016/02/10 22:42:08]

I believe this is covered by the tests I added to checker tests.

+      // A function without type formals cannot subtype one that has them.
+      return false;
     }
+    return _isFunctionSubtypeOfRaw(f1, f2, fuzzyArrows: fuzzyArrows);
+  }
 
+  /**
+   * Checks if f1 <: f2, ignoring type formals. This should generally not be
+   * used directly, instead call [_isFunctionSubtypeOf]. Its main use is for
+   * [_StrongInferenceTypeSystem].
+   */
+  bool _isFunctionSubtypeOfRaw(FunctionType f1, FunctionType f2,

[Leaf, 2016/02/09 21:29:25]

I don't really like the name of this - Raw doesn't really mean anything to me. 
Consider being more verbose, since this is not intended to be used much?
_isFunctionSubtypeOfIgnoringTypeFormals?  _isUniversalTypeBodySubtypeOf?

[Jennifer Messerly, 2016/02/10 22:42:08]

It's gone :D

+      {bool fuzzyArrows: true}) {
     return FunctionTypeImpl.structuralCompare(
         f1,
         f2,
@@ -345,43 +323,10 @@ class StrongTypeSystemImpl implements TypeSystem {
    */
   bool _isGenericFunctionSubtypeOf(FunctionType f1, FunctionType f2,
       {bool fuzzyArrows: true}) {
-    List<TypeParameterElement> params1 = f1.typeFormals;
-    List<TypeParameterElement> params2 = f2.typeFormals;
-    int count = params1.length;
-    if (params2.length != count) {
-      return false;
-    }
-    // We build up a substitution matching up the type parameters
-    // from the two types, {variablesFresh/variables1} and
-    // {variablesFresh/variables2}
-    List<DartType> variables1 = new List<DartType>();
-    List<DartType> variables2 = new List<DartType>();
-    List<DartType> variablesFresh = new List<DartType>();
-    for (int i = 0; i < count; i++) {
-      TypeParameterElement p1 = params1[i];
-      TypeParameterElement p2 = params2[i];
-      TypeParameterElementImpl pFresh =
-          new TypeParameterElementImpl(p2.name, -1);
-
-      DartType variable1 = p1.type;
-      DartType variable2 = p2.type;
-      DartType variableFresh = new TypeParameterTypeImpl(pFresh);
-
-      variables1.add(variable1);
-      variables2.add(variable2);
-      variablesFresh.add(variableFresh);
-      DartType bound1 = p1.bound ?? DynamicTypeImpl.instance;
-      DartType bound2 = p2.bound ?? DynamicTypeImpl.instance;
-      bound1 = bound1.substitute2(variablesFresh, variables1);
-      bound2 = bound2.substitute2(variablesFresh, variables2);
-      pFresh.bound = bound2;
-      if (!isSubtypeOf(bound2, bound1)) {
-        return false;
-      }
-    }
-    return _isFunctionSubtypeOf(
-        f1.instantiate(variablesFresh), f2.instantiate(variablesFresh),
-        fuzzyArrows: fuzzyArrows);
+
+    return FunctionTypeImpl.structuralCompareGeneric(f1, f2,
+        (t, s) => t.isSubtypeOf(s),
+        (f, g) => _isFunctionSubtypeOf(f, g, fuzzyArrows: fuzzyArrows));
   }
 
   bool _isInterfaceSubtypeOf(
@@ -790,7 +735,7 @@ class _StrongInferenceTypeSystem extends StrongTypeSystemImpl {
 
   /// Given the constraints that were given by calling [isSubtypeOf], find the
   /// instantiation of the generic function that satisfies these constraints.
-  FunctionType _infer(FunctionType fnType) {
+  FunctionType _infer(FunctionType fnType, {bool allowPartialSolution: false}) {
     List<TypeParameterType> fnTypeParams =
         TypeParameterTypeImpl.getTypes(fnType.typeFormals);
 
@@ -832,13 +777,22 @@ class _StrongInferenceTypeSystem extends StrongTypeSystemImpl {
       inferredTypes[i] =
           inferredTypes[i].substitute2(inferredTypes, fnTypeParams);
 
-      // See if this actually worked.
-      // If not, fall back to the known upper bound (if any) or `dynamic`.
+      // See if the constraints on the type variable are satisfied.
+      //
+      // If not, bail out of the analysis, unless a partial solution was
+      // requested. If we are willing to accept a partial solution, fall back to
+      // the known upper bound (if any) or `dynamic` for this unsolvable type
+      // variable.
       if (inferredTypes[i].isBottom ||
           !isSubtypeOf(inferredTypes[i],
               bound.upper.substitute2(inferredTypes, fnTypeParams)) ||
           !isSubtypeOf(bound.lower.substitute2(inferredTypes, fnTypeParams),
               inferredTypes[i])) {
+        // Unless a partial solution was requested, bail.
+        if (!allowPartialSolution) {
+          return null;
+        }
+
         inferredTypes[i] = DynamicTypeImpl.instance;
         if (typeParam.element.bound != null) {
           inferredTypes[i] =