Add a strong mode implementation of LUB to fasta; use it to infer ?:

pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart

Index: pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart
diff --git a/pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart b/pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart
new file mode 100644
index 0000000000000000000000000000000000000000..6d6ac86bff2feca6d44839dffd2dd8061fb788b0
--- /dev/null
+++ b/pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart
@@ -0,0 +1,402 @@
+// Copyright (c) 2017, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE.md file.
+
+import 'dart:math' as math;
+
+import 'package:front_end/src/fasta/type_inference/type_schema.dart';
+import 'package:kernel/ast.dart';
+import 'package:kernel/class_hierarchy.dart';
+import 'package:kernel/core_types.dart';
+import 'package:kernel/type_algebra.dart';
+import 'package:kernel/type_environment.dart';
+
+class TypeSchemaEnvironment extends TypeEnvironment {
+  TypeSchemaEnvironment(CoreTypes coreTypes, ClassHierarchy hierarchy)
+      : super(coreTypes, hierarchy);
+
+  /// Computes the greatest lower bound of [type1] and [type2].
+  DartType getGreatestLowerBound(DartType type1, DartType type2) {
+    // The greatest lower bound relation is reflexive.
+    if (identical(type1, type2)) {

[ahe, 2017/05/02 18:32:56]

Should this be == ?

[Leaf, 2017/05/02 23:28:46]

There could be a separate entry point that first tested for full equality, but
since this is a recursive algorithm, testing for equality on every recursive
call (O(n)) makes it quadratic.  The identity check isn't needed for
correctness, it just cuts off fast if the types are the same.

[Paul Berry, 2017/05/03 17:31:25]

I've added a comment explaining this.

+      return type1;
+    }
+
+    // For any type T, GLB(?, T) == T.
+    if (type1 is UnknownType) {
+      return type2;
+    }
+    if (type2 is UnknownType) {
+      return type1;
+    }
+
+    // The GLB of top and any type is just that type.
+    // Also GLB of bottom and any type is bottom.
+    if (isTop(type1) || isBottom(type2)) {
+      return type2;
+    }
+    if (isTop(type2) || isBottom(type1)) {
+      return type1;
+    }
+
+    // Function types have structural GLB.
+    if (type1 is FunctionType && type2 is FunctionType) {
+      return _functionGreatestLowerBound(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 const BottomType();
+  }
+
+  /// Compute the least upper bound of two types.
+  DartType getLeastUpperBound(DartType type1, DartType type2) {
+    // The least upper bound relation is reflexive.
+    if (identical(type1, type2)) {

[ahe, 2017/05/02 18:32:56]

== ?

[Paul Berry, 2017/05/03 17:31:24]

Ditto

+      return type1;
+    }
+
+    // For any type T, LUB(?, T) == T.
+    if (type1 is UnknownType) {
+      return type2;
+    }
+    if (type2 is UnknownType) {
+      return type1;
+    }
+
+    // The least upper bound of void and any type T != dynamic is void.
+    if (type1 is VoidType) {
+      return type2 is DynamicType ? type2 : type1;
+    }
+    if (type2 is VoidType) {
+      return type1 is DynamicType ? type1 : type2;
+    }
+
+    // The least upper bound of top and any type T is top.
+    // The least upper bound of bottom and any type T is T.
+    if (isTop(type1) || isBottom(type2)) {
+      return type1;
+    }
+    if (isTop(type2) || isBottom(type1)) {
+      return type2;
+    }
+
+    if (type1 is TypeParameterType || type2 is TypeParameterType) {
+      return _typeParameterLeastUpperBound(type1, type2);
+    }
+
+    // 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 = rawFunctionType;
+    }
+    if (type2 is FunctionType && type1 is InterfaceType) {
+      type2 = rawFunctionType;
+    }
+
+    // At this point type1 and type2 should both either be interface types or
+    // function types.
+    if (type1 is InterfaceType && type2 is InterfaceType) {
+      return _interfaceLeastUpperBound(type1, type2);
+    }
+
+    if (type1 is FunctionType && type2 is FunctionType) {
+      return _functionLeastUpperBound(type1, type2);
+    }
+
+    // Should never happen. As a defensive measure, return the dynamic type.
+    assert(false);

[ahe, 2017/05/02 18:32:56]

internalError.

[Paul Berry, 2017/05/03 17:31:24]

internalError has the disadvantage of causing a crash even in unchecked mode (we
wouldn't be able to fall back to dynamic as a defensive measure).

I'm going to keep it as is for defensiveness.  If you feel strongly about it,
let me know and we can discuss further.

+    return const DynamicType();
+  }
+
+  @override
+  bool isBottom(DartType t) {
+    if (t is UnknownType) {
+      return true;
+    } else {
+      return super.isBottom(t);
+    }
+  }
+
+  @override
+  bool isTop(DartType t) {
+    if (t is UnknownType) {
+      return true;
+    } else {
+      return super.isTop(t);
+    }
+  }
+
+  /// 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

[ahe, 2017/05/02 18:32:56]

I don't understand why a missing parameter would become optional.

[Bob Nystrom, 2017/05/02 23:22:18]

Consider:

a(callback(i)) => callback(1);
b(callback()) => callback();

var fn = cond ? a : b;
fn((???) {});

What is the parameter signature at "???" that would create a function that both
a and b can successfully call? The answer is:

([i]) {}

where it takes a single optional parameter.

[Leaf, 2017/05/02 23:28:46]

We're looking for a function type that can be used anywhere either of the two
input function types can be used.   So for example, if we have 
DOWN((int, int) -> int, (int) -> int)), then ([int, int]) -> int is the correct
choice, because it is a subtype of the one with two required parameters, and
also of the one with only one required parameter.   And similarly for when one
of the input arguments has optional parameters.

[Paul Berry, 2017/05/03 17:31:25]

Thanks for the explanations.  I've updated the comment to make this clearer.

+  ///   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(FunctionType f, FunctionType g) {
+    // TODO(rnystrom): Right now, this assumes f and g do not have any type

[ahe, 2017/05/02 18:32:56]

Is this copied from somewhere?

[Bob Nystrom, 2017/05/02 23:22:18]

Yes:
https://github.com/dart-lang/sdk/blob/3b790e5311ce3877b1f63a9a0d2beecd11cd6d0...

+    // parameters. Revisit that in the presence of generic methods.

[Leaf, 2017/05/02 23:28:46]

Ouch.  This should be fixed.  I'll write up spec verbiage, but basically they
need to have the same number of type parameters, and the bounds need to be
equal.

[Paul Berry, 2017/05/03 17:31:25]

Thanks.  I've added my name to the TODO comment as well.

+
+    // Calculate the LUB of each corresponding pair of parameters.
+    int totalPositional =
+        math.max(f.positionalParameters.length, g.positionalParameters.length);
+    var positionalParameters = new List<DartType>(totalPositional);
+    for (int i = 0; i < totalPositional; i++) {
+      if (i < f.positionalParameters.length) {
+        var fType = f.positionalParameters[i];
+        if (i < g.positionalParameters.length) {
+          var gType = g.positionalParameters[i];
+          positionalParameters[i] = getLeastUpperBound(fType, gType);
+        } else {
+          positionalParameters[i] = fType;
+        }
+      } else {
+        positionalParameters[i] = g.positionalParameters[i];
+      }
+    }
+
+    // Parameters that are required in both functions are required in the
+    // result.  Parameters that are optional or missing in either end up
+    // optional.
+    int requiredParameterCount =
+        math.min(f.requiredParameterCount, g.requiredParameterCount);
+    bool hasPositional = requiredParameterCount < totalPositional;
+
+    // Union the named parameters together.
+    List<NamedType> namedParameters = [];
+    {
+      int i = 0;
+      int j = 0;
+      while (true) {
+        if (i < f.namedParameters.length) {
+          if (j < g.namedParameters.length) {
+            var fName = f.namedParameters[i].name;
+            var gName = g.namedParameters[j].name;
+            int order = fName.compareTo(gName);
+            if (order < 0) {
+              namedParameters.add(f.namedParameters[i++]);
+            } else if (order > 0) {
+              namedParameters.add(g.namedParameters[j++]);
+            } else {
+              namedParameters.add(new NamedType(
+                  fName,
+                  getLeastUpperBound(f.namedParameters[i++].type,
+                      g.namedParameters[j++].type)));
+            }
+          } else {
+            namedParameters.addAll(f.namedParameters.skip(i));
+            break;
+          }
+        } else {
+          namedParameters.addAll(g.namedParameters.skip(j));
+          break;
+        }
+      }
+    }
+    bool hasNamed = namedParameters.isNotEmpty;
+
+    // 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 const BottomType();
+
+    // Calculate the GLB of the return type.
+    DartType returnType = getGreatestLowerBound(f.returnType, g.returnType);
+    return new FunctionType(positionalParameters, returnType,
+        namedParameters: namedParameters,
+        requiredParameterCount: requiredParameterCount);
+  }
+
+  /// Compute the least upper bound of function types [f] and [g].
+  ///
+  /// The rules for LUB on function types, informally, are pretty simple:
+  ///
+  /// - If the functions don't have the same number of required parameters,
+  ///   always return `Function`.
+  ///
+  /// - Discard any optional named or positional parameters the two types do not
+  ///   have in common.
+  ///
+  /// - Compute the GLB of each corresponding pair of parameter types, and the
+  ///   LUB of the return types.  Return a function type with those types.
+  DartType _functionLeastUpperBound(FunctionType f, FunctionType g) {
+    // TODO(rnystrom): Right now, this assumes f and g do not have any type
+    // parameters. Revisit that in the presence of generic methods.
+
+    // If F and G differ in their number of required parameters, then the
+    // least upper bound of F and G is Function.
+    // TODO(paulberry): We could do better here, e.g.:
+    //   LUB(([int]) -> void, (int) -> void) = (int) -> void
+    if (f.requiredParameterCount != g.requiredParameterCount) {
+      return coreTypes.functionClass.rawType;
+    }
+    int requiredParameterCount = f.requiredParameterCount;
+
+    // Calculate the GLB of each corresponding pair of parameters.
+    // Ignore any extra optional positional parameters if one has more than the
+    // other.
+    int totalPositional =
+        math.min(f.positionalParameters.length, g.positionalParameters.length);
+    var positionalParameters = new List<DartType>(totalPositional);
+    for (int i = 0; i < totalPositional; i++) {
+      positionalParameters[i] = getGreatestLowerBound(
+          f.positionalParameters[i], g.positionalParameters[i]);
+    }
+
+    // Intersect the named parameters.
+    List<NamedType> namedParameters = [];
+    {
+      int i = 0;
+      int j = 0;
+      while (true) {
+        if (i < f.namedParameters.length) {
+          if (j < g.namedParameters.length) {
+            var fName = f.namedParameters[i].name;
+            var gName = g.namedParameters[j].name;
+            int order = fName.compareTo(gName);
+            if (order < 0) {
+              i++;
+            } else if (order > 0) {
+              j++;
+            } else {
+              namedParameters.add(new NamedType(
+                  fName,
+                  getGreatestLowerBound(f.namedParameters[i++].type,
+                      g.namedParameters[j++].type)));
+            }
+          } else {
+            break;
+          }
+        } else {
+          break;
+        }
+      }
+    }
+
+    // Calculate the LUB of the return type.
+    DartType returnType = getLeastUpperBound(f.returnType, g.returnType);
+    return new FunctionType(positionalParameters, returnType,
+        namedParameters: namedParameters,
+        requiredParameterCount: requiredParameterCount);
+  }
+
+  DartType _interfaceLeastUpperBound(InterfaceType type1, InterfaceType type2) {
+    // This currently does not implement a very complete least upper bound
+    // algorithm, but handles a couple of the very common cases that are
+    // causing pain in real code.  The current algorithm is:
+    // 1. If either of the types is a supertype of the other, return it.
+    //    This is in fact the best result in this case.
+    // 2. If the two types have the same class element, then take the
+    //    pointwise least upper bound of the type arguments.  This is again
+    //    the best result, except that the recursive calls may not return
+    //    the true least upper bounds.  The result is guaranteed to be a
+    //    well-formed type under the assumption that the input types were
+    //    well-formed (and assuming that the recursive calls return
+    //    well-formed types).
+    // 3. Otherwise return the spec-defined least upper bound.  This will
+    //    be an upper bound, might (or might not) be least, and might
+    //    (or might not) be a well-formed type.
+    //
+    // TODO(leafp): Use matchTypes or something similar here to handle the

[Leaf, 2017/05/02 23:28:46]

Remove this todo.  it's tracked elsewhere as a language issue.

[Paul Berry, 2017/05/03 17:31:24]

Done.

+    //  case where one of the types is a superclass (but not supertype) of
+    //  the other, e.g. LUB(Iterable<double>, List<int>) = Iterable<num>
+    // TODO(leafp): Figure out the right final algorithm and implement it.

[Leaf, 2017/05/02 23:28:45]

likewise.

[Paul Berry, 2017/05/03 17:31:24]

Done.

+    if (isSubtypeOf(type1, type2)) {
+      return type2;
+    }
+    if (isSubtypeOf(type2, type1)) {
+      return type1;
+    }
+    if (type1 is InterfaceType &&
+        type2 is InterfaceType &&
+        identical(type1.classNode, type2.classNode)) {
+      List<DartType> tArgs1 = type1.typeArguments;
+      List<DartType> tArgs2 = type2.typeArguments;
+
+      assert(tArgs1.length == tArgs2.length);
+      List<DartType> tArgs = new List(tArgs1.length);
+      for (int i = 0; i < tArgs1.length; i++) {
+        tArgs[i] = getLeastUpperBound(tArgs1[i], tArgs2[i]);
+      }
+      return new InterfaceType(type1.classNode, tArgs);
+    }
+    return hierarchy.getClassicLeastUpperBound(type1, type2);
+  }
+
+  DartType _typeParameterLeastUpperBound(DartType type1, DartType type2) {
+    // This currently just implements a simple least upper bound to
+    // handle some common cases.  It also avoids some termination issues
+    // with the naive spec algorithm.  The least upper bound of two types
+    // (at least one of which is a type parameter) is computed here as:
+    // 1. If either type is a supertype of the other, return it.
+    // 2. If the first type is a type parameter, replace it with its bound,
+    //    with recursive occurrences of itself replaced with Object.
+    //    The second part of this should ensure termination.  Informally,
+    //    each type variable instantiation in one of the arguments to the
+    //    least upper bound algorithm now strictly reduces the number
+    //    of bound variables in scope in that argument position.
+    // 3. If the second type is a type parameter, do the symmetric operation
+    //    to #2.
+    //
+    // It's not immediately obvious why this is symmetric in the case that both
+    // of them are type parameters.  For #1, symmetry holds since subtype
+    // is antisymmetric.  For #2, it's clearly not symmetric if upper bounds of
+    // bottom are allowed.  Ignoring this (for various reasons, not least
+    // of which that there's no way to write it), there's an informal
+    // argument (that might even be right) that you will always either
+    // end up expanding both of them or else returning the same result no matter
+    // which order you expand them in.  A key observation is that
+    // identical(expand(type1), type2) => subtype(type1, type2)
+    // and hence the contra-positive.
+    //
+    // TODO(leafp): Think this through and figure out what's the right
+    // definition.  Be careful about termination.
+    //
+    // I suspect in general 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.
+    if (isSubtypeOf(type1, type2)) {
+      return type2;
+    }
+    if (isSubtypeOf(type2, type1)) {
+      return type1;
+    }
+    if (type1 is TypeParameterType) {
+      // TODO(paulberry): Analyzer collapses simple bounds in one step, i.e. for
+      // C<T extends U, U extends List>, T gets resolved directly to List.  Do
+      // we need to replicate that behavior?
+      return getLeastUpperBound(
+          Substitution.fromMap({type1.parameter: objectType}).substituteType(
+              type1.parameter.bound),
+          type2);
+    } else if (type2 is TypeParameterType) {
+      return getLeastUpperBound(
+          type1,
+          Substitution.fromMap({type2.parameter: objectType}).substituteType(
+              type2.parameter.bound));
+    } else {
+      // We should only be called when at least one of the types is a
+      // TypeParameterType
+      assert(false);
+      return const DynamicType();
+    }
+  }
+}