Begin implementing subtype matching for type inference.

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
index 5310475ed06103ce34f5515c5919e3b1888ffeb9..ef01a9f19d18e7a76d8e3867ff4e8ed37f82adca 100644
--- 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
@@ -5,16 +5,41 @@
 import 'dart:math' as math;
 
 import 'package:front_end/src/fasta/type_inference/type_schema.dart';
+import 'package:front_end/src/fasta/type_inference/type_schema_elimination.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';
 
+/// A constraint on a type parameter that we're inferring.
+class TypeConstraint {
+  /// The lower bound of the type being constrained.  This bound must be a
+  /// subtype of the type being constrained.
+  DartType lower = const UnknownType();
+
+  /// The upper bound of the type being constrained.  The type being constrained
+  /// must be a subtype of this bound.
+  DartType upper = const UnknownType();
+
+  String toString() =>
+      '${typeSchemaToString(lower)} <: <type> <: ${typeSchemaToString(upper)}';
+}
+
 class TypeSchemaEnvironment extends TypeEnvironment {
   TypeSchemaEnvironment(CoreTypes coreTypes, ClassHierarchy hierarchy)
       : super(coreTypes, hierarchy);
 
+  /// Modify the given [constraint]'s lower bound to include [lower].
+  void addLowerBound(TypeConstraint constraint, DartType lower) {

[Jennifer Messerly, 2017/05/04 18:06:01]

this feels conceptually like it's an operation that might make more sense on
TypeConstraint?

since it's a mutation operation, putting it on the object can give the reader at
the call site bit more sense of what is being mutated. Otherwise I would wonder
if it's mutating the TypeSchemaEnvironment.

[Paul Berry, 2017/05/04 19:56:09]

Hmm, good point.  I'm not too thrilled with this API either.  I'll experiment
with this in a follow-up CL.

+    constraint.lower = getLeastUpperBound(constraint.lower, lower);

[Jennifer Messerly, 2017/05/04 18:06:01]

fyi ... we started with an implementation like this too in Analyzer ... we moved
to tracking individual constraints to be able to issue error messages with
better information about what went wrong.

[Paul Berry, 2017/05/04 19:56:08]

Thanks--I noticed that while reading through the analyzer code.  My current plan
is to have a derived version of TypeSchemaEnvironment that does additional
tracking for the purposes of better error reporting; if type inference fails,
we'll re-analyze the method using the derived class (that way we can avoid
paying the extra tracking penalty in the common case of analyzing code that is
error free).  I'm imagining that the derived TypeSchemaEnvironment would make
use of a derived version of TypeConstraint that stores the extra constraint
tracking information.

I'll play with this in the same follow-up CL.

+  }
+
+  /// Modify the given [constraint]'s upper bound to include [upper].
+  void addUpperBound(TypeConstraint constraint, DartType upper) {
+    constraint.upper = getGreatestLowerBound(constraint.upper, upper);
+  }
+
   /// Computes the greatest lower bound of [type1] and [type2].
   DartType getGreatestLowerBound(DartType type1, DartType type2) {
     // The greatest lower bound relation is reflexive.  Note that we don't test
@@ -142,6 +167,35 @@ class TypeSchemaEnvironment extends TypeEnvironment {
     }
   }
 
+  /// Computes the constraint solution for a type variable based on a given set
+  /// of constraints.
+  ///
+  /// If [grounded] is `true`, then the returned type is guaranteed to be a
+  /// known type (i.e. it will not contain any instances of `?`).
+  DartType solveTypeConstraint(TypeConstraint constraint,
+      {bool grounded: false}) {
+    // Prefer the known bound, if any.
+    if (isKnown(constraint.lower)) return constraint.lower;
+    if (isKnown(constraint.upper)) return constraint.upper;
+
+    // Otherwise take whatever bound has partial information, e.g. `Iterable<?>`
+    if (constraint.lower is! UnknownType) {
+      return grounded
+          ? greatestClosure(coreTypes, constraint.lower)
+          : constraint.lower;
+    } else {
+      return grounded
+          ? leastClosure(coreTypes, constraint.upper)
+          : constraint.upper;
+    }
+  }
+
+  /// Determine if the given [type] satisfies the given type [constraint].
+  bool typeSatisfiesConstraint(DartType type, TypeConstraint constraint) {
+    return isSubtypeOf(constraint.lower, type) &&
+        isSubtypeOf(type, constraint.upper);
+  }
+
   /// Compute the greatest lower bound of function types [f] and [g].
   ///
   /// The spec rules for GLB on function types, informally, are pretty simple: