Extract DartTypeVisitor and subclasses from resolution_types.

pkg/compiler/lib/src/elements/types.dart

Index: pkg/compiler/lib/src/elements/types.dart
diff --git a/pkg/compiler/lib/src/elements/types.dart b/pkg/compiler/lib/src/elements/types.dart
index 946a03590ed907810a83c7cab589a6e6c23d143a..f8a4a4e899b65e03b60981dd1aea3d218742c431 100644
--- a/pkg/compiler/lib/src/elements/types.dart
+++ b/pkg/compiler/lib/src/elements/types.dart
@@ -2,8 +2,9 @@
 // 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.
 
-import 'entities.dart';
+import '../common_elements.dart';
 import '../util/util.dart' show equalElements;
+import 'entities.dart';
 
 /// Hierarchy to describe types in Dart.
 ///
@@ -77,6 +78,9 @@ abstract class DartType {
   ///
   /// Invariant: There must be the same number of [arguments] and [parameters].
   DartType subst(List<DartType> arguments, List<DartType> parameters);
+
+  /// Calls the visit method on [visitor] corresponding to this type.
+  R accept<R, A>(DartTypeVisitor<R, A> visitor, A argument);
 }
 
 class InterfaceType extends DartType {
@@ -111,6 +115,10 @@ class InterfaceType extends DartType {
     return this;
   }
 
+  @override
+  R accept<R, A>(DartTypeVisitor visitor, A argument) =>
+      visitor.visitInterfaceType(this, argument);
+
   int get hashCode {
     int hash = element.hashCode;
     for (DartType argument in typeArguments) {
@@ -172,6 +180,10 @@ class TypeVariableType extends DartType {
     return this;
   }
 
+  @override
+  R accept<R, A>(DartTypeVisitor visitor, A argument) =>
+      visitor.visitTypeVariableType(this, argument);
+
   int get hashCode => 17 * element.hashCode;
 
   bool operator ==(other) {
@@ -192,6 +204,10 @@ class VoidType extends DartType {
     return this;
   }
 
+  @override
+  R accept<R, A>(DartTypeVisitor visitor, A argument) =>
+      visitor.visitVoidType(this, argument);
+
   int get hashCode => 6007;
 
   String toString() => 'void';
@@ -211,6 +227,10 @@ class DynamicType extends DartType {
     return this;
   }
 
+  @override
+  R accept<R, A>(DartTypeVisitor visitor, A argument) =>
+      visitor.visitDynamicType(this, argument);
+
   int get hashCode => 91;
 
   String toString() => 'dynamic';
@@ -279,6 +299,10 @@ class FunctionType extends DartType {
     return this;
   }
 
+  @override
+  R accept<R, A>(DartTypeVisitor visitor, A argument) =>
+      visitor.visitFunctionType(this, argument);
+
   int get hashCode {
     int hash = 3 * returnType.hashCode;
     for (DartType parameter in parameterTypes) {
@@ -373,3 +397,327 @@ List<DartType> _substTypes(
   // Use the new List only if necessary.
   return changed ? result : types;
 }
+
+abstract class DartTypeVisitor<R, A> {
+  const DartTypeVisitor();
+
+  R visit(DartType type, A argument) => type.accept(this, argument);
+
+  R visitVoidType(VoidType type, A argument) => null;
+
+  R visitTypeVariableType(TypeVariableType type, A argument) => null;
+
+  R visitFunctionType(FunctionType type, A argument) => null;
+
+  R visitInterfaceType(InterfaceType type, A argument) => null;
+
+  R visitDynamicType(DynamicType type, A argument) => null;
+}
+
+abstract class BaseDartTypeVisitor<R, A> extends DartTypeVisitor<R, A> {
+  const BaseDartTypeVisitor();
+
+  R visitType(DartType type, A argument);
+
+  @override
+  R visitVoidType(VoidType type, A argument) => visitType(type, argument);
+
+  @override
+  R visitTypeVariableType(TypeVariableType type, A argument) =>
+      visitType(type, argument);
+
+  @override
+  R visitFunctionType(FunctionType type, A argument) =>
+      visitType(type, argument);
+
+  @override
+  R visitInterfaceType(InterfaceType type, A argument) =>
+      visitType(type, argument);
+
+  @override
+  R visitDynamicType(DynamicType type, A argument) => visitType(type, argument);
+}
+
+/// Abstract visitor for determining relations between types.
+abstract class AbstractTypeRelation
+    extends BaseDartTypeVisitor<bool, DartType> {
+  CommonElements get commonElements;
+
+  /// Ensures that the super hierarchy of [type] is computed.
+  void ensureResolved(InterfaceType type) {}
+
+  /// Returns the unaliased version of [type].
+  DartType getUnaliased(DartType type) => type.unaliased;
+
+  /// Returns [type] as an instance of [cls], or `null` if [type] is not subtype
+  /// if [cls].
+  InterfaceType asInstanceOf(InterfaceType type, ClassEntity cls);
+
+  /// Returns the type of the `call` method on [type], or `null` if the class
+  /// of [type] does not have a `call` method.
+  FunctionType getCallType(InterfaceType type);
+
+  /// Returns the declared bound of [element].
+  DartType getTypeVariableBound(TypeVariableEntity element);
+
+  bool visitType(DartType t, DartType s) {
+    throw 'internal error: unknown type ${t}';
+  }
+
+  bool visitVoidType(VoidType t, DartType s) {
+    assert(s is! VoidType);
+    return false;
+  }
+
+  bool invalidTypeArguments(DartType t, DartType s);
+
+  bool invalidFunctionReturnTypes(DartType t, DartType s);
+
+  bool invalidFunctionParameterTypes(DartType t, DartType s);
+
+  bool invalidTypeVariableBounds(DartType bound, DartType s);
+
+  bool invalidCallableType(DartType callType, DartType s);
+
+  bool visitInterfaceType(InterfaceType t, DartType s) {
+    ensureResolved(t);
+
+    bool checkTypeArguments(InterfaceType instance, InterfaceType other) {
+      List<DartType> tTypeArgs = instance.typeArguments;
+      List<DartType> sTypeArgs = other.typeArguments;
+      assert(tTypeArgs.length == sTypeArgs.length);
+      for (int i = 0; i < tTypeArgs.length; i++) {
+        if (invalidTypeArguments(tTypeArgs[i], sTypeArgs[i])) {
+          return false;
+        }
+      }
+      return true;
+    }
+
+    if (s is InterfaceType) {
+      InterfaceType instance = asInstanceOf(t, s.element);
+      if (instance != null && checkTypeArguments(instance, s)) {
+        return true;
+      }
+    }
+
+    FunctionType callType = getCallType(t);
+    if (s == commonElements.functionType && callType != null) {
+      return true;
+    } else if (s is FunctionType) {
+      return callType != null && !invalidCallableType(callType, s);
+    }
+
+    return false;
+  }
+
+  bool visitFunctionType(FunctionType t, DartType s) {
+    if (s == commonElements.functionType) {
+      return true;
+    }
+    if (s is! FunctionType) return false;
+    FunctionType tf = t;
+    FunctionType sf = s;
+    if (invalidFunctionReturnTypes(tf.returnType, sf.returnType)) {
+      return false;
+    }
+
+    // TODO(johnniwinther): Rewrite the function subtyping to be more readable
+    // but still as efficient.
+
+    // For the comments we use the following abbreviations:
+    //  x.p     : parameterTypes on [:x:],
+    //  x.o     : optionalParameterTypes on [:x:], and
+    //  len(xs) : length of list [:xs:].
+
+    Iterator<DartType> tps = tf.parameterTypes.iterator;
+    Iterator<DartType> sps = sf.parameterTypes.iterator;
+    bool sNotEmpty = sps.moveNext();
+    bool tNotEmpty = tps.moveNext();
+    tNext() => (tNotEmpty = tps.moveNext());
+    sNext() => (sNotEmpty = sps.moveNext());
+
+    bool incompatibleParameters() {
+      while (tNotEmpty && sNotEmpty) {
+        if (invalidFunctionParameterTypes(tps.current, sps.current)) {
+          return true;
+        }
+        tNext();
+        sNext();
+      }
+      return false;
+    }
+
+    if (incompatibleParameters()) return false;
+    if (tNotEmpty) {
+      // We must have [: len(t.p) <= len(s.p) :].
+      return false;
+    }
+    if (!sf.namedParameters.isEmpty) {
+      // We must have [: len(t.p) == len(s.p) :].
+      if (sNotEmpty) {
+        return false;
+      }
+      // Since named parameters are globally ordered we can determine the
+      // subset relation with a linear search for [:sf.namedParameters:]
+      // within [:tf.namedParameters:].
+      List<String> tNames = tf.namedParameters;
+      List<DartType> tTypes = tf.namedParameterTypes;
+      List<String> sNames = sf.namedParameters;
+      List<DartType> sTypes = sf.namedParameterTypes;
+      int tIndex = 0;
+      int sIndex = 0;
+      while (tIndex < tNames.length && sIndex < sNames.length) {
+        if (tNames[tIndex] == sNames[sIndex]) {
+          if (invalidFunctionParameterTypes(tTypes[tIndex], sTypes[sIndex])) {
+            return false;
+          }
+          sIndex++;
+        }
+        tIndex++;
+      }
+      if (sIndex < sNames.length) {
+        // We didn't find all names.
+        return false;
+      }
+    } else {
+      // Check the remaining [: s.p :] against [: t.o :].
+      tps = tf.optionalParameterTypes.iterator;
+      tNext();
+      if (incompatibleParameters()) return false;
+      if (sNotEmpty) {
+        // We must have [: len(t.p) + len(t.o) >= len(s.p) :].
+        return false;
+      }
+      if (!sf.optionalParameterTypes.isEmpty) {
+        // Check the remaining [: s.o :] against the remaining [: t.o :].
+        sps = sf.optionalParameterTypes.iterator;
+        sNext();
+        if (incompatibleParameters()) return false;
+        if (sNotEmpty) {
+          // We didn't find enough parameters:
+          // We must have [: len(t.p) + len(t.o) <= len(s.p) + len(s.o) :].
+          return false;
+        }
+      } else {
+        if (sNotEmpty) {
+          // We must have [: len(t.p) + len(t.o) >= len(s.p) :].
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+
+  bool visitTypeVariableType(TypeVariableType t, DartType s) {
+    // Identity check is handled in [isSubtype].
+    DartType bound = getTypeVariableBound(t.element);
+    if (bound.isTypeVariable) {
+      // The bound is potentially cyclic so we need to be extra careful.
+      Set<TypeVariableEntity> seenTypeVariables = new Set<TypeVariableEntity>();
+      seenTypeVariables.add(t.element);
+      while (bound.isTypeVariable) {
+        TypeVariableType typeVariable = bound;
+        if (bound == s) {
+          // [t] extends [s].
+          return true;
+        }
+        if (seenTypeVariables.contains(typeVariable.element)) {
+          // We have a cycle and have already checked all bounds in the cycle
+          // against [s] and can therefore conclude that [t] is not a subtype
+          // of [s].
+          return false;
+        }
+        seenTypeVariables.add(typeVariable.element);
+        bound = getTypeVariableBound(typeVariable.element);
+      }
+    }
+    if (invalidTypeVariableBounds(bound, s)) return false;
+    return true;
+  }
+}
+
+abstract class MoreSpecificVisitor extends AbstractTypeRelation {
+  bool isMoreSpecific(DartType t, DartType s) {
+    if (identical(t, s) || s.treatAsDynamic || t == commonElements.nullType) {
+      return true;
+    }
+    if (t.isVoid || s.isVoid) {
+      return false;
+    }
+    if (t.treatAsDynamic) {
+      return false;
+    }
+    if (s == commonElements.objectType) {
+      return true;
+    }
+    t = getUnaliased(t);
+    s = getUnaliased(s);
+
+    return t.accept(this, s);
+  }
+
+  bool invalidTypeArguments(DartType t, DartType s) {
+    return !isMoreSpecific(t, s);
+  }
+
+  bool invalidFunctionReturnTypes(DartType t, DartType s) {
+    if (s.treatAsDynamic && t.isVoid) return true;
+    return !s.isVoid && !isMoreSpecific(t, s);
+  }
+
+  bool invalidFunctionParameterTypes(DartType t, DartType s) {
+    return !isMoreSpecific(t, s);
+  }
+
+  bool invalidTypeVariableBounds(DartType bound, DartType s) {
+    return !isMoreSpecific(bound, s);
+  }
+
+  bool invalidCallableType(DartType callType, DartType s) {
+    return !isMoreSpecific(callType, s);
+  }
+}
+
+/// Type visitor that determines the subtype relation two types.
+abstract class SubtypeVisitor extends MoreSpecificVisitor {
+  bool isSubtype(DartType t, DartType s) {
+    return t.treatAsDynamic || isMoreSpecific(t, s);
+  }
+
+  bool isAssignable(DartType t, DartType s) {
+    return isSubtype(t, s) || isSubtype(s, t);
+  }
+
+  bool invalidTypeArguments(DartType t, DartType s) {
+    return !isSubtype(t, s);
+  }
+
+  bool invalidFunctionReturnTypes(DartType t, DartType s) {
+    return !s.isVoid && !isAssignable(t, s);
+  }
+
+  bool invalidFunctionParameterTypes(DartType t, DartType s) {
+    return !isAssignable(t, s);
+  }
+
+  bool invalidTypeVariableBounds(DartType bound, DartType s) {
+    return !isSubtype(bound, s);
+  }
+
+  bool invalidCallableType(DartType callType, DartType s) {
+    return !isSubtype(callType, s);
+  }
+}
+
+/// Type visitor that determines one type could a subtype of another given the
+/// right type variable substitution. The computation is approximate and returns
+/// `false` only if we are sure no such substitution exists.
+abstract class PotentialSubtypeVisitor extends SubtypeVisitor {
+  bool isSubtype(DartType t, DartType s) {
+    if (t is TypeVariableType || s is TypeVariableType) {
+      return true;
+    }
+    return super.isSubtype(t, s);
+  }
+}