Use GLB for function parameters when doing LUB in strong mode.

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 84f2eb7c2168c68532b02a388a9061296c734233..ff1f682757f96391fc33e0c779e828a718f7fedc 100644
--- a/pkg/analyzer/lib/src/generated/type_system.dart
+++ b/pkg/analyzer/lib/src/generated/type_system.dart
@@ -22,8 +22,6 @@ typedef bool _GuardedSubtypeChecker<T>(T t1, T t2, Set<Element> visited);
  * https://github.com/dart-lang/dev_compiler/blob/master/STRONG_MODE.md
  */
 class StrongTypeSystemImpl extends TypeSystem {
-  final _specTypeSystem = new TypeSystemImpl();
-
   bool anyParameterType(FunctionType ft, bool predicate(DartType t)) {
     return ft.parameters.any((p) => predicate(p.type));
   }
@@ -43,13 +41,6 @@ class StrongTypeSystemImpl extends TypeSystem {
     return null;
   }
 
-  @override
-  DartType getLeastUpperBound(
-      TypeProvider typeProvider, DartType type1, DartType type2) {
-    // TODO(leafp): Implement a strong mode version of this.
-    return _specTypeSystem.getLeastUpperBound(typeProvider, type1, type2);
-  }
-
   /**
    * Given a generic function type `F<T0, T1, ... Tn>` and a context type C,
    * infer an instantiation of F, such that `F<S0, S1, ..., Sn>` <: C.
@@ -222,8 +213,7 @@ class StrongTypeSystemImpl extends TypeSystem {
     // TODO(leafp): Emit warnings and hints for these in some way.
     // TODO(leafp): Consider adding a flag to disable these?  Or just rely on
     //   --warnings-as-errors?
-    if (isSubtypeOf(toType, fromType) ||
-        _specTypeSystem.isAssignableTo(toType, fromType)) {
+    if (isSubtypeOf(toType, fromType) || toType.isAssignableTo(fromType)) {
       // TODO(leafp): error if type is known to be exact (literal,
       //  instance creation).
       // TODO(leafp): Warn on composite downcast.
@@ -448,6 +438,175 @@ class StrongTypeSystemImpl extends TypeSystem {
   bool _isTop(DartType t, {bool dynamicIsBottom: false}) {
     return (t.isDynamic && !dynamicIsBottom) || t.isObject;
   }
+
+  /// Computes the greatest lower bound of [type1] and [type2].
+  @override
+  DartType getGreatestLowerBound(
+      TypeProvider provider, DartType type1, DartType type2) {
+    // The greatest lower bound relation is reflexive.
+    if (identical(type1, type2)) {
+      return type1;
+    }
+
+    // Treat dynamic as top. The GLB of dynamic and any type is just that type
+    // since dynamic permits all values.
+    if (type1.isDynamic) {
+      return type2;
+    }
+    if (type2.isDynamic) {
+      return type1;
+    }
+
+    // You can't get any lower than bottom.
+    if (type1.isBottom || type2.isBottom) {
+      return provider.bottomType;
+    }
+
+    // Void only permits one value, null, which is also a value of all other
+    // types, so treat it as bottom-ish.
+    if (type1.isVoid || type2.isVoid) {

[Leaf, 2016/03/22 00:02:20]

This seems wrong.  void isn't really in the same category of types as the rest,
but I don't *think* it hurts to have it here.  In the subtype code, we really
only allow it in function subtying.  However, it should presumably only arise
(in well-formed code at least) via taking the GLB of two function return types. 


In any case, while we only allow returns of null values from void functions,
we've defined subtyping to allow non-void functions to be a subtype of void
functions.  If I recall correctly this was to support the common idiom of
passing functions returning dynamic where functions returning void were
expected.  This means the that GLB of a function returning void and a function
returning T should be a function returning T.

The dual will be true for LUB, of course.  

[Bob Nystrom, 2016/03/22 21:35:00]

Yeah, I think that's right.
So treat void like a top type for GLB? If I do that, then I think that implies
type errors on the marked lines here:

takeVoidFn(void fn()) { print(fn()); }
takeIntFn(int fn()) { print(fn()); }

void returnVoid() => null;
int returnInt() => 123;

main(bool b) {
  takeIntFn(returnVoid); // <--
  takeVoidFn(returnInt);

  (b ? takeVoidFn : takeIntFn)(returnVoid); // <--
  (b ? takeVoidFn : takeIntFn)(returnInt);
}

The first one isn't GLB, of course, and seems reasonable if a little
pessimistic.

But it seems a little strange to me to have the type error on the second marked
line. Is that what you had in mind? If so, I'm OK with it, I guess. We are way
off in the weeds of code that no sane person would likely write anyway.

[Leaf, 2016/03/23 05:33:39]

Yes, that's right.  The issue is that subtyping defines what GLB and LUB need to
be.   The most basic correctness condition for GLB and LUB is that what they
compute should be at least lower bounds and upper bounds respectively.  We're
being loosey-goosey about the G and L part, but we should at least get the LB
and UB part right.  So:
If you consider this example, you'll see why it has to be this way:

takeVoidFn(void fn()) { takeIntFn(fn); }
takeIntFn(int fn()) { print(fn() + 1); }

void returnVoid() => null;
int returnInt() => 123;
bool returnBool() => true;

takeVoidFn(returnBool);

We allow () -> something to subtype () -> void.  If we allow you to go the other
way as well, then you break the type system entirely.

We could consider only allowing () -> dynamic to subtype () -> void.  This would
probably allow most of the cases that we were trying to support, and induce a
different LUB/GLB.  But it kind of makes sense to me that you can pass any
function returning something into a context expecting a function that returns
nothing, since you can count on the context to ignore the result (and on all of
our current platforms at least the calling conventions are compatible).

Once you accept this though (if you do accept it), then the GLB just falls out. 
In order to satisfy the basic correctness condition I describe above, the LUB of
the types of takeVoidFn and takeIntFn must be a supertype of each of their
types, which means that GLB(() -> void, () -> int) <: () -> void and () -> int
must be true.  That means that GLB(void, int) <: void and int must be true. 
Bottom would work here, but it's not greatest.  Choosing int gives you a greater
lower bound (in fact, in this case, it gives you the actual greatest lower bound
as induced by this subtyping relation.).

[Bob Nystrom, 2016/03/23 20:51:37]

Ah, got it. Took me a while to work through it (so many nested function types!)
but I think it makes sense.

+      return VoidTypeImpl.instance;
+    }
+
+    // Substitute type parameters for their bounds.
+    type1 = type1.resolveToBound(provider.objectType);
+    type2 = type2.resolveToBound(provider.objectType);

[Leaf, 2016/03/22 00:02:20]

These look wrong.  I think these methods are wrong even in the spec mode
implementation of LUB, actually.  But here, I think this gives GLB(S, T) ==
Object (when S and T are type variables with no bounds), and GLB(S, T) == T when
S is a type variable with no bound and T is not.  In neither case is the result
even a lower bound.  In the case that the variables have bounds it's slightly
more complicated, but still wrong.

We could try to do something here to take into account parameter bounds into
account - we're basically in a closed world with respect to the sub-typing
hierarchy induced by parameter bounds.  For now though, I'd suggest just letting
this fall through to the subtyping cases below.  This will, I think, catch the
common cases (e.g. S, T extends S) without pulling you down the rabbit hole.

[Bob Nystrom, 2016/03/22 21:35:00]

Honestly, I didn't understand exactly what it accomplished there either.
Done. Took me a while to think through it, but it makes sense.

+
+    // Function types have structural GLB.
+    if (type1 is FunctionType && type2 is FunctionType) {
+      return _functionGreatestLowerBound(provider, type1, type2);
+    }
+
+    // Otherwise, the GLB of two types is one of them it if it is a subtype of
+    // the other.
+    if (isSubtypeOf(type1, type2)) {
+      return type1;
+    }
+
+    if (isSubtypeOf(type2, type1)) {
+      return type2;
+    }
+
+    // No subtype relation, so no known GLB.
+    return provider.bottomType;
+  }
+
+  /**
+   * Compute the greatest lower bound of function types [f] and [g].
+   *
+   * The spec rules for GLB on function types, informally, are pretty simple:
+   *
+   * - If a parameter is required in both, it stays required.
+   *
+   * - If a positional parameter is optional or missing in one, it becomes
+   *   optional.
+   *
+   * - Named parameters are unioned together.
+   *
+   * - For any parameter that exists in both functions, use the LUB of them as
+   *   the resulting parameter type.
+   *
+   * - Use the GLB of their return types.
+   */
+  DartType _functionGreatestLowerBound(
+      TypeProvider provider, FunctionType f, FunctionType g) {
+    // Calculate the LUB of each corresponding pair of parameters.
+    List<ParameterElement> parameters = [];
+
+    bool hasPositional = false;
+    bool hasNamed = false;
+    addParameter(
+        String name, DartType fType, DartType gType, ParameterKind kind) {
+      DartType paramType;
+      if (fType != null && gType != null) {
+        // If both functions have this parameter, include both of their types.
+        paramType = getLeastUpperBound(provider, fType, gType);
+      } else {
+        paramType = fType ?? gType;
+      }
+
+      parameters.add(new ParameterElementImpl.synthetic(name, paramType, kind));
+    }
+
+    // TODO(rnystrom): Right now, this assumes f and g do not have any type
+    // parameters. Revisit that in the presence of generic methods.
+    List<DartType> fRequired = f.normalParameterTypes;
+    List<DartType> gRequired = g.normalParameterTypes;
+
+    // We need some parameter names for in the synthesized function type.
+    List<String> fRequiredNames = f.normalParameterNames;
+    List<String> gRequiredNames = g.normalParameterNames;
+
+    // Parameters that are required in both functions are required in the
+    // result.
+    int requiredCount = math.min(fRequired.length, gRequired.length);
+    for (int i = 0; i < requiredCount; i++) {
+      parameters.add(new ParameterElementImpl.synthetic(

[Leaf, 2016/03/22 00:02:20]

Why not re-use addParameter here?

[Bob Nystrom, 2016/03/22 21:35:00]

Oops. Done.

+          fRequiredNames[i],
+          getLeastUpperBound(provider, fRequired[i], gRequired[i]),
+          ParameterKind.REQUIRED));
+    }
+
+    // Parameters that are optional or missing in either end up optional.
+    List<DartType> fPositional = f.optionalParameterTypes;
+    List<DartType> gPositional = g.optionalParameterTypes;
+    List<String> fPositionalNames = f.optionalParameterNames;
+    List<String> gPositionalNames = g.optionalParameterNames;
+
+    int totalPositional = math.max(fRequired.length + fPositional.length,
+        gRequired.length + gPositional.length);
+    for (int i = requiredCount; i < totalPositional; i++) {
+      // Find the corresponding positional parameters (required or optional) at
+      // this index, if there is one.
+      DartType fType;
+      String fName;
+      if (i < fRequired.length) {
+        fType = fRequired[i];
+        fName = fRequiredNames[i];
+      } else if (i < fRequired.length + fPositional.length) {
+        fType = fPositional[i - fRequired.length];
+        fName = fPositionalNames[i - fRequired.length];
+      }
+
+      DartType gType;
+      String gName;
+      if (i < gRequired.length) {
+        gType = gRequired[i];
+        gName = gRequiredNames[i];
+      } else if (i < gRequired.length + gPositional.length) {
+        gType = gPositional[i - gRequired.length];
+        gName = gPositionalNames[i - gRequired.length];
+      }
+
+      // The loop should not let us go past both f and g's positional params.
+      assert(fType != null || gType != null);
+
+      addParameter(fName ?? gName, fType, gType, ParameterKind.POSITIONAL);
+      hasPositional = true;
+    }
+
+    // Union the named parameters together.
+    Map<String, DartType> fNamed = f.namedParameterTypes;
+    Map<String, DartType> gNamed = g.namedParameterTypes;
+    for (String name in fNamed.keys.toSet()..addAll(gNamed.keys)) {
+      addParameter(name, fNamed[name], gNamed[name], ParameterKind.NAMED);
+      hasNamed = true;
+    }
+
+    // Edge case. Dart does not support functions with both optional positional
+    // and named parameters. If we would synthesize that, give up.
+    if (hasPositional && hasNamed) return provider.bottomType;
+
+    // Calculate the GLB of the return type.
+    DartType returnType =
+        getGreatestLowerBound(provider, f.returnType, g.returnType);
+    return new FunctionElementImpl.synthetic(parameters, returnType).type;
+  }
+
+  @override
+  DartType _functionParameterBound(
+          TypeProvider provider, DartType f, DartType g) =>
+      getGreatestLowerBound(provider, f, g);
 }
 
 /**
@@ -473,7 +632,66 @@ abstract class TypeSystem {
    * Compute the least upper bound of two types.
    */
   DartType getLeastUpperBound(
-      TypeProvider typeProvider, DartType type1, DartType type2);
+      TypeProvider typeProvider, DartType type1, DartType type2) {
+    // The least upper bound relation is reflexive.
+    if (identical(type1, type2)) {
+      return type1;
+    }
+    // The least upper bound of dynamic and any type T is dynamic.
+    if (type1.isDynamic) {
+      return type1;
+    }
+    if (type2.isDynamic) {
+      return type2;
+    }

[Leaf, 2016/03/22 00:02:20]

Might be worth checking for object here, just to cut out the long search below
in the case that one of the types is object.

[Bob Nystrom, 2016/03/23 20:51:37]

I'm trying to get out of the habit of speculative optimization because I think
analyzer is rife with it (so many cached list lengths!), and it's not clear to
me that it adds performance value. Definitely up for optimizing this case if we
see it show up in a profile. :)

+    // The least upper bound of void and any type T != dynamic is void.
+    if (type1.isVoid) {
+      return type1;
+    }
+    if (type2.isVoid) {
+      return type2;
+    }
+    // The least upper bound of bottom and any type T is T.
+    if (type1.isBottom) {
+      return type2;
+    }
+    if (type2.isBottom) {
+      return type1;
+    }
+
+    // Let U be a type variable with upper bound B.  The least upper bound of U
+    // and a type T is the least upper bound of B and T.
+    type1 = type1.resolveToBound(typeProvider.objectType);
+    type2 = type2.resolveToBound(typeProvider.objectType);

[Leaf, 2016/03/22 00:02:20]

This is kind of weird, and not right even for spec mode in the case that both
are type variables.  I filed a bug here:

https://github.com/dart-lang/sdk/issues/26054

It does at least give *an* upper bound, but it won't be the least, and in many
common cases won't be the useful one (e.g. T, S extends T).

The spec definition is pretty unhelpful.

I suspect that a reasonable algorithm is to expand the innermost type variable
first.  Alternatively, you could probably choose to treat it as just an instance
of the interface type upper bound problem, with the "inheritance" chain extended
by the bounds placed on the variables.

In the short term, in the case that both are type variables you could check if
either is a subtype of the other, and if so use the supertype, and otherwise
fall back to expanding both.  This should catch many of the interesting cases
without getting too involved.  

[Bob Nystrom, 2016/03/22 21:35:00]

For what it's worth, this code is unchanged. I just moved it up from
TypeSystemImpl into here so it's accessible to StrongModeTypeSystem too. Is it
OK if I just add TODO mentioning the bug and leave it alone for now?

[Leaf, 2016/03/23 05:33:39]

Sure, but I'd like it to be one of those TODOs that actually gets TODONE at some
point. :)

Can you summarize (or just copy) my suggestions above into the TODO (or into a
bug) so that the context doesn't get lost - I did put a certain amount of
thought into it, and will have forgotten it all by the time we come back to
this.

[Bob Nystrom, 2016/03/23 20:51:37]

Done!

+
+    // The least upper bound of a function type and an interface type T is the
+    // least upper bound of Function and T.
+    if (type1 is FunctionType && type2 is InterfaceType) {
+      type1 = typeProvider.functionType;
+    }
+    if (type2 is FunctionType && type1 is InterfaceType) {
+      type2 = typeProvider.functionType;
+    }
+
+    // At this point type1 and type2 should both either be interface types or
+    // function types.
+    if (type1 is InterfaceType && type2 is InterfaceType) {
+      InterfaceType result =
+          InterfaceTypeImpl.computeLeastUpperBound(type1, type2);
+      if (result == null) {
+        return typeProvider.dynamicType;
+      }
+      return result;
+    }
+
+    if (type1 is FunctionType && type2 is FunctionType) {
+      return _functionLeastUpperBound(typeProvider, type1, type2);
+    }
+
+    // Should never happen. As a defensive measure, return the dynamic type.
+    assert(false);
+    return typeProvider.dynamicType;
+  }
 
   /**
    * Given a [DartType] [type], instantiate it with its bounds.
@@ -594,111 +812,6 @@ abstract class TypeSystem {
         ? new StrongTypeSystemImpl()
         : new TypeSystemImpl();
   }
-}
-
-/**
- * Implementation of [TypeSystem] using the rules in the Dart specification.
- */
-class TypeSystemImpl extends TypeSystem {
-  TypeSystemImpl();
-
-  @override
-  bool canPromoteToType(DartType to, DartType from) {
-    // Declared type should not be "dynamic".
-    // Promoted type should not be "dynamic".
-    // Promoted type should be more specific than declared.
-    return !from.isDynamic && !to.isDynamic && to.isMoreSpecificThan(from);
-  }
-
-  @override
-  DartType getLeastUpperBound(
-      TypeProvider typeProvider, DartType type1, DartType type2) {
-    // The least upper bound relation is reflexive.
-    if (identical(type1, type2)) {
-      return type1;
-    }
-    // The least upper bound of dynamic and any type T is dynamic.
-    if (type1.isDynamic) {
-      return type1;
-    }
-    if (type2.isDynamic) {
-      return type2;
-    }
-    // The least upper bound of void and any type T != dynamic is void.
-    if (type1.isVoid) {
-      return type1;
-    }
-    if (type2.isVoid) {
-      return type2;
-    }
-    // The least upper bound of bottom and any type T is T.
-    if (type1.isBottom) {
-      return type2;
-    }
-    if (type2.isBottom) {
-      return type1;
-    }
-
-    // Let U be a type variable with upper bound B.  The least upper bound of U
-    // and a type T is the least upper bound of B and T.
-    type1 = type1.resolveToBound(typeProvider.objectType);
-    type2 = type2.resolveToBound(typeProvider.objectType);
-
-    // The least upper bound of a function type and an interface type T is the
-    // least upper bound of Function and T.
-    if (type1 is FunctionType && type2 is InterfaceType) {
-      type1 = typeProvider.functionType;
-    }
-    if (type2 is FunctionType && type1 is InterfaceType) {
-      type2 = typeProvider.functionType;
-    }
-
-    // At this point type1 and type2 should both either be interface types or
-    // function types.
-    if (type1 is InterfaceType && type2 is InterfaceType) {
-      InterfaceType result =
-          InterfaceTypeImpl.computeLeastUpperBound(type1, type2);
-      if (result == null) {
-        return typeProvider.dynamicType;
-      }
-      return result;
-    } else if (type1 is FunctionType && type2 is FunctionType) {
-      return _functionLeastUpperBound(typeProvider, type1, type2);
-    } else {
-      // Should never happen.  As a defensive measure, return the dynamic type.
-      assert(false);
-      return typeProvider.dynamicType;
-    }
-  }
-
-  /**
-   * Instantiate a parameterized type using `dynamic` for all generic
-   * parameters.  Returns the type unchanged if there are no parameters.
-   */
-  DartType instantiateToBounds(DartType type) {
-    List<DartType> typeFormals = typeFormalsAsTypes(type);
-    int count = typeFormals.length;
-    if (count > 0) {
-      List<DartType> typeArguments =
-          new List<DartType>.filled(count, DynamicTypeImpl.instance);
-      return instantiateType(type, typeArguments);
-    }
-    return type;
-  }
-
-  @override
-  bool isAssignableTo(DartType leftType, DartType rightType) {
-    return leftType.isAssignableTo(rightType);
-  }
-
-  @override
-  bool isMoreSpecificThan(DartType t1, DartType t2) =>
-      t1.isMoreSpecificThan(t2);
-
-  @override
-  bool isSubtypeOf(DartType leftType, DartType rightType) {
-    return leftType.isSubtypeOf(rightType);
-  }
 
   /**
    * Compute the least upper bound of function types [f] and [g].
@@ -739,7 +852,7 @@ class TypeSystemImpl extends TypeSystem {
     for (int i = 0; i < fRequired.length; i++) {
       parameters.add(new ParameterElementImpl.synthetic(
           fRequiredNames[i],
-          getLeastUpperBound(provider, fRequired[i], gRequired[i]),
+          _functionParameterBound(provider, fRequired[i], gRequired[i]),
           ParameterKind.REQUIRED));
     }
 
@@ -752,7 +865,7 @@ class TypeSystemImpl extends TypeSystem {
     for (int i = 0; i < length; i++) {
       parameters.add(new ParameterElementImpl.synthetic(
           fPositionalNames[i],
-          getLeastUpperBound(provider, fPositional[i], gPositional[i]),
+          _functionParameterBound(provider, fPositional[i], gPositional[i]),
           ParameterKind.POSITIONAL));
     }
 
@@ -761,21 +874,69 @@ class TypeSystemImpl extends TypeSystem {
     for (String name in fNamed.keys.toSet()..retainAll(gNamed.keys)) {
       parameters.add(new ParameterElementImpl.synthetic(
           name,
-          getLeastUpperBound(provider, fNamed[name], gNamed[name]),
+          _functionParameterBound(provider, fNamed[name], gNamed[name]),
           ParameterKind.NAMED));
     }
 
     // Calculate the LUB of the return type.
     DartType returnType =
         getLeastUpperBound(provider, f.returnType, g.returnType);
+    return new FunctionElementImpl.synthetic(parameters, returnType).type;
+  }
+
+  /**
+   * Calculates the appropriate upper or lower bound of a pair of parameters
+   * for two function types whose least upper bound is being calculated.
+   *
+   * In spec mode, this uses least upper bound, which... doesn't really make
+   * much sense. Strong mode overrides this to use greatest lower bound.
+   */
+  DartType _functionParameterBound(
+          TypeProvider provider, DartType f, DartType g) =>
+      getLeastUpperBound(provider, f, g);
+}
 
-    FunctionElementImpl function = new FunctionElementImpl("", -1);
-    function.synthetic = true;
-    function.returnType = returnType;
-    function.parameters = parameters;
+/**
+ * Implementation of [TypeSystem] using the rules in the Dart specification.
+ */
+class TypeSystemImpl extends TypeSystem {
+  TypeSystemImpl();
 
-    function.type = new FunctionTypeImpl(function);
-    return function.type;
+  @override
+  bool canPromoteToType(DartType to, DartType from) {
+    // Declared type should not be "dynamic".
+    // Promoted type should not be "dynamic".
+    // Promoted type should be more specific than declared.
+    return !from.isDynamic && !to.isDynamic && to.isMoreSpecificThan(from);
+  }
+
+  /**
+   * Instantiate a parameterized type using `dynamic` for all generic
+   * parameters.  Returns the type unchanged if there are no parameters.
+   */
+  DartType instantiateToBounds(DartType type) {
+    List<DartType> typeFormals = typeFormalsAsTypes(type);
+    int count = typeFormals.length;
+    if (count > 0) {
+      List<DartType> typeArguments =
+          new List<DartType>.filled(count, DynamicTypeImpl.instance);
+      return instantiateType(type, typeArguments);
+    }
+    return type;
+  }
+
+  @override
+  bool isAssignableTo(DartType leftType, DartType rightType) {
+    return leftType.isAssignableTo(rightType);
+  }
+
+  @override
+  bool isMoreSpecificThan(DartType t1, DartType t2) =>
+      t1.isMoreSpecificThan(t2);
+
+  @override
+  bool isSubtypeOf(DartType leftType, DartType rightType) {
+    return leftType.isSubtypeOf(rightType);
   }
 }