Implement type variable 'more specific than' and 'subtype'.

editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/type/TypeParameterTypeImpl.java

Index: editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/type/TypeParameterTypeImpl.java
diff --git a/editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/type/TypeParameterTypeImpl.java b/editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/type/TypeParameterTypeImpl.java
index fbfd4dcc40ae23ea9a4d75aad60b1faad286a915..00548d9b07e0158c88119fca890d101ea7b33d21 100644
--- a/editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/type/TypeParameterTypeImpl.java
+++ b/editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/type/TypeParameterTypeImpl.java
@@ -13,11 +13,17 @@
  */
 package com.google.dart.engine.internal.type;
 
+import com.google.common.base.Objects;
+import com.google.dart.engine.element.ClassElement;
 import com.google.dart.engine.element.TypeParameterElement;
+import com.google.dart.engine.type.InterfaceType;
 import com.google.dart.engine.type.Type;
 import com.google.dart.engine.type.TypeParameterType;
 import com.google.dart.engine.utilities.general.ObjectUtilities;
 
+import java.util.HashSet;
+import java.util.Set;
+
 /**
  * Instances of the class {@code TypeParameterTypeImpl} defines the behavior of objects representing
  * the type introduced by a type parameter.
@@ -77,18 +83,35 @@ public class TypeParameterTypeImpl extends TypeImpl implements TypeParameterType
   }
 
   @Override
-  public boolean isMoreSpecificThan(Type type) {
+  public boolean isMoreSpecificThan(Type s) {
     //
-    // T is a type parameter and S is the upper bound of T.
+    // A type T is more specific than a type S, written T << S,  if one of the following conditions
+    // is met:
     //
-    Type upperBound = getElement().getBound();
-    return type.equals(upperBound);
+    // Reflexivity: T is S.
+    //
+    if (this.equals(s)) {
+      return true;
+    }
+
+    // S is bottom.
+    //
+    if (s == BottomTypeImpl.getInstance()) {
+      return true;
+    }
+
+    // S is dynamic.
+    //
+    if (s == DynamicTypeImpl.getInstance()) {

[Brian Wilkerson, 2013/10/10 13:31:35]

Can we use .isBottom() and .isDynamic() here instead of identity tests?

+      return true;
+    }
+
+    return isMoreSpecificThan(s, new HashSet<Type>());
   }
 
   @Override
-  public boolean isSubtypeOf(Type type) {
-    // TODO(scheglov) really? without checking if this is another type parameter and bound?
-    return true;
+  public boolean isSubtypeOf(Type s) {
+    return isMoreSpecificThan(s);
   }
 
   @Override
@@ -101,4 +124,72 @@ public class TypeParameterTypeImpl extends TypeImpl implements TypeParameterType
     }
     return this;
   }
+
+  /**
+   * Returns <i>Base</i> if given class is <i>Base&lt;T></i> where <i>T extends Base&lt;T></i>, or
+   * {@code null} otherwise.
+   */
+  private ClassElement getSelfBoundTypeParameterClass(InterfaceType interfaceType) {
+    Type[] typeArguments = interfaceType.getTypeArguments();
+    if (typeArguments.length == 1) {
+      Type typeArgument = typeArguments[0];
+      if (typeArgument instanceof TypeParameterType) {
+        TypeParameterType typeParameter = (TypeParameterType) typeArgument;
+        if (Objects.equal(typeParameter.getElement().getBound(), interfaceType)) {
+          return interfaceType.getElement();
+        }
+      }
+    }
+    return null;
+  }
+
+  private boolean isMoreSpecificThan(Type s, Set<Type> visitedTypes) {
+    // T is a type parameter and S is the upper bound of T.
+    //
+    Type upperBound = getElement().getBound();
+    if (s.equals(upperBound)) {
+      return true;
+    }
+
+    // T is a type parameter and S is Object.
+    //
+    if (s.isObject()) {
+      return true;
+    }
+
+    // We need upper bound to continue.
+    if (upperBound == null) {
+      return false;
+    }
+
+    //
+    // Transitivity: T << U and U << S.
+    //
+    if (upperBound instanceof TypeParameterTypeImpl) {
+      TypeParameterTypeImpl upperBoundTypeParameter = (TypeParameterTypeImpl) upperBound;
+      // First check for infinite loops
+      if (visitedTypes.contains(upperBound)) {
+        return false;
+      }
+      visitedTypes.add(upperBound);
+      // Then check upper bound.
+      return upperBoundTypeParameter.isMoreSpecificThan(s, visitedTypes);
+    }
+
+    // <W extends Base<W>>  is the same as <U extends Base<U>>
+    if (upperBound instanceof InterfaceType && s instanceof InterfaceType) {
+      InterfaceType upperBoundInterfaceType = (InterfaceType) upperBound;
+      InterfaceType sInterfaceType = (InterfaceType) s;
+      ClassElement sSelfClass = getSelfBoundTypeParameterClass(sInterfaceType);
+      if (sSelfClass != null) {
+        ClassElement boundSelfClass = getSelfBoundTypeParameterClass(upperBoundInterfaceType);
+        if (sSelfClass.equals(boundSelfClass)) {
+          return true;
+        }
+      }
+    }
+
+    // Check interface type.
+    return upperBound.isMoreSpecificThan(s);

[jwren, 2013/10/10 17:34:57]

Shouldn't it be s.isMoreSpecificThan(upperBound)?

[scheglov, 2013/10/10 22:24:23]

Hm... No.

<T extends B>, so T << B.
So, if B << S then also T << S.

But S << B  =>  T << S does not looks true for me.

For example B = num, T = int, S = double, but int << double is not correct.

+  }
 }