Add strong mode type checking pass.

lib/type_algebra.dart

 // Copyright (c) 2016, 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 file.
 library kernel.type_algebra;
 
 import 'ast.dart';
 
 /// Returns a type where all occurrences of the given type parameters have been
 /// replaced with the corresponding types.
 ///
@@ skipping 101 matching lines @@
   Supertype substituteSuper(Supertype type) {
     return substitution.substituteSupertype(type);
   }
 }
 
 // ------------------------------------------------------------------------
 //                              IMPLEMENTATION
 // ------------------------------------------------------------------------
 
 abstract class Substitution {
+  const Substitution();
+
+  static const Substitution empty = _NullSubstitution.instance;
+
   /// Substitutes each parameter to the type it maps to in [map].
   static Substitution fromMap(Map<TypeParameter, DartType> map) {
     if (map.isEmpty) return _NullSubstitution.instance;
     return new _MapSubstitution(map, map);
   }
 
   /// Substitutes all occurrences of the given type parameters with the
   /// corresponding upper or lower bound, depending on the variance of the
   /// context where it occurs.
   ///
@@ skipping 30 matching lines @@
   static Substitution fromPairs(
       List<TypeParameter> parameters, List<DartType> types) {
     // TODO(asgerf): Investigate if it is more efficient to implement
     // substitution based on parallel pairwise lists instead of Maps.
     assert(parameters.length == types.length);
     if (parameters.isEmpty) return _NullSubstitution.instance;
     return fromMap(
         new Map<TypeParameter, DartType>.fromIterables(parameters, types));
   }
 
+  /// Substitutes the type parameters on the class with bottom or dynamic,
+  /// depending on the covariance of its use.
+  static Substitution bottomForClass(Class class_) {
+    if (class_.typeParameters.isEmpty) return _NullSubstitution.instance;
+    return new _ClassBottomSubstitution(class_);
+  }
+
+  /// Substitutes both variables from [first] and [second], favoring those from
+  /// [first] if they overlap.
+  ///
+  /// Neither substitution is applied to the results of the other, so this does
+  /// *not* correspond to a sequence of two subsitutions. For example, combining
+  /// `{T -> List<G>}` with `{G -> String}` does not correspond to
+  /// `{T -> List<String>}` because the result from substituting `T` is not
+  /// searched for occurences of `G`.
+  static Substitution combine(Substitution first, Substitution second) {
+    if (first == _NullSubstitution.instance) return second;
+    if (second == _NullSubstitution.instance) return first;
+    return new _CombinedSubstitution(first, second);
+  }
+
   DartType getSubstitute(TypeParameter parameter, bool upperBound);
 
-  DartType substituteType(DartType node) {
-    return new _TopSubstitutor(this).visit(node);
+  DartType substituteType(DartType node, {bool contravariant: false}) {
+    return new _TopSubstitutor(this, contravariant).visit(node);
   }
 
   Supertype substituteSupertype(Supertype node) {
-    return new _TopSubstitutor(this).visitSupertype(node);
+    return new _TopSubstitutor(this, false).visitSupertype(node);
   }
 }
 
 class _NullSubstitution extends Substitution {
-  static final _NullSubstitution instance = new _NullSubstitution();
+  static const _NullSubstitution instance = const _NullSubstitution();
+
+  const _NullSubstitution();
 
   DartType getSubstitute(TypeParameter parameter, bool upperBound) {
     return new TypeParameterType(parameter);
   }
 
   @override
-  DartType substituteType(DartType node) => node;
+  DartType substituteType(DartType node, {bool contravariant: false}) => node;
 
   @override
   Supertype substituteSupertype(Supertype node) => node;
 }
 
 class _MapSubstitution extends Substitution {
   final Map<TypeParameter, DartType> upper;
   final Map<TypeParameter, DartType> lower;
 
   _MapSubstitution(this.upper, this.lower);
 
   DartType getSubstitute(TypeParameter parameter, bool upperBound) {
     return upperBound ? upper[parameter] : lower[parameter];
   }
 }
 
 class _TopSubstitutor extends _TypeSubstitutor {
   final Substitution substitution;
 
-  _TopSubstitutor(this.substitution) : super(null);
+  _TopSubstitutor(this.substitution, bool contravariant) : super(null) {
+    if (contravariant) {
+      invertVariance();
+    }
+  }
 
   DartType lookup(TypeParameter parameter, bool upperBound) {
     return substitution.getSubstitute(parameter, upperBound);
   }
 
   TypeParameter freshTypeParameter(TypeParameter node) {
     throw 'Create a fresh environment first';
   }
 }
 
+class _ClassBottomSubstitution extends Substitution {
+  final Class class_;
+
+  _ClassBottomSubstitution(this.class_);
+
+  DartType getSubstitute(TypeParameter parameter, bool upperBound) {
+    if (parameter.parent == class_) {
+      return upperBound ? const BottomType() : const DynamicType();
+    }
+    return null;
+  }
+}
+
+class _CombinedSubstitution extends Substitution {
+  final Substitution first, second;
+
+  _CombinedSubstitution(this.first, this.second);
+
+  DartType getSubstitute(TypeParameter parameter, bool upperBound) {
+    return first.getSubstitute(parameter, upperBound) ??
+        second.getSubstitute(parameter, upperBound);
+  }
+}
+
 class _InnerTypeSubstitutor extends _TypeSubstitutor {
   final Map<TypeParameter, DartType> substitution = <TypeParameter, DartType>{};
 
   _InnerTypeSubstitutor(_TypeSubstitutor outer) : super(outer);
 
   DartType lookup(TypeParameter parameter, bool upperBound) {
     return substitution[parameter];
   }
 
   TypeParameter freshTypeParameter(TypeParameter node) {
@@ skipping 344 matching lines @@
 }
 
 Map<dynamic/*=K*/, dynamic/*=W*/ > _mapValues/*<K,V,W>*/(
     Map<dynamic/*=K*/, dynamic/*=V*/ > map, dynamic/*=W*/ fn(dynamic/*=V*/)) {
   Map<dynamic/*=K*/, dynamic/*=W*/ > result = {};
   map.forEach((key, value) {
     result[key] = fn(value);
   });
   return result;
 }