Implement substitution for type variables.

sdk/lib/_internal/compiler/implementation/js_backend/runtime_types.dart

Index: sdk/lib/_internal/compiler/implementation/js_backend/runtime_types.dart
diff --git a/sdk/lib/_internal/compiler/implementation/js_backend/runtime_types.dart b/sdk/lib/_internal/compiler/implementation/js_backend/runtime_types.dart
index a3a0339b96e3c72661475c135989cb6a1caa81bb..19d592b73a24c81493c6fa0f0bd267f655671161 100644
--- a/sdk/lib/_internal/compiler/implementation/js_backend/runtime_types.dart
+++ b/sdk/lib/_internal/compiler/implementation/js_backend/runtime_types.dart
@@ -8,7 +8,7 @@ part of js_backend;
 abstract class TypeChecks {
   /// Get the set of checks required for class [element].
   Iterable<ClassElement> operator[](ClassElement element);
-  // Get the iterator for all classes that need type checks.
+  /// Get the iterator for all classes that need type checks.
   Iterator<ClassElement> get iterator;
 }
 
@@ -27,25 +27,45 @@ class RuntimeTypeInformation {
             element == compiler.numClass ||
             element == compiler.doubleClass ||
             element == compiler.stringClass ||
-            element == compiler.listClass ||
-            element == compiler.objectClass ||
-            element == compiler.dynamicClass);
+            element == compiler.listClass);
   }
 
-  TypeChecks computeRequiredChecks() {
+  TypeChecks cachedRequiredChecks;
+
+  TypeChecks getRequiredChecks() {
+    if (cachedRequiredChecks != null) return cachedRequiredChecks;
+
+    // Collect all types used in type arguments of instantiated types.

[kasperl, 2013/01/29 15:02:34]

You could factor out the computation of these two sets in two helper functions.

[karlklose, 2013/01/30 12:01:19]

Done.

+    // This includes type arguments used in supertype relations, because we may
+    // have a type check against this supertype that includes a check against
+    // the type arguments.
     Set<ClassElement> instantiatedArguments = new Set<ClassElement>();
-    for (DartType type in compiler.codegenWorld.instantiatedTypes) {
+    for (DartType type in instantiatedTypes) {
       addAllInterfaceTypeArguments(type, instantiatedArguments);
+      ClassElement cls = type.element;
+      for (DartType type in cls.allSupertypes) {
+        addAllInterfaceTypeArguments(type, instantiatedArguments);
+      }
+    }
+    for (ClassElement cls in instantiatedArguments) {
+      for (DartType type in cls.allSupertypes) {
+        addAllInterfaceTypeArguments(type, instantiatedArguments);
+      }
     }
 
+    // Collect all type arguments used in is-checks.
     Set<ClassElement> checkedArguments = new Set<ClassElement>();
-    for (DartType type in compiler.enqueuer.codegen.universe.isChecks) {
+    for (DartType type in isChecks) {
       addAllInterfaceTypeArguments(type, checkedArguments);
     }
 
+    // Precompute the set of all seen type arguments for use in the emitter.
     allArguments = new Set<ClassElement>.from(instantiatedArguments)
         ..addAll(checkedArguments);
 
+    // Finally, run through the combination of instantiated and checked
+    // arguments and record all combination where the element of a checked
+    // argument is a superclass of the element of an instantiated type.
     TypeCheckMapping requiredChecks = new TypeCheckMapping();
     for (ClassElement element in instantiatedArguments) {
       if (element == compiler.dynamicClass) continue;
@@ -60,8 +80,15 @@ class RuntimeTypeInformation {
         }
       }
     }
+    return cachedRequiredChecks = requiredChecks;
+  }
 
-    return requiredChecks;
+  Iterable<DartType> get isChecks {
+    return compiler.enqueuer.codegen.universe.isChecks;
+  }
+
+  Iterable<DartType> get instantiatedTypes {
+    return compiler.codegenWorld.instantiatedTypes;
   }
 
   void addAllInterfaceTypeArguments(DartType type, Set<ClassElement> classes) {
@@ -69,7 +96,7 @@ class RuntimeTypeInformation {
     for (DartType argument in type.typeArguments) {
       forEachInterfaceType(argument, (InterfaceType t) {
         ClassElement cls = t.element;
-        if (cls != compiler.dynamicClass && cls != compiler.objectClass) {
+        if (cls != compiler.dynamicClass) {
           classes.add(cls);
         }
       });
@@ -106,31 +133,99 @@ class RuntimeTypeInformation {
     InterfaceType interface = type;
     Link<DartType> variables = interface.element.typeVariables;
     if (variables.isEmpty) return name;
-    List<String> arguments = [];
-    variables.forEach((_) => arguments.add('dynamic'));
-    return '$name<${Strings.join(arguments, ', ')}>';
+    String arguments = variables.mappedBy((_) => 'dynamic').join(', ');
+    return '$name<$arguments>';
   }
 
-  String getTypeRepresentation(DartType type, void onVariable(variable)) {
+  // TODO(karlklose): maybe precompute this value and store it in typeChecks?
+  bool isTrivialSubstitution(ClassElement cls, ClassElement check) {
+    if (cls.isClosure()) {
+      // TODO(karlklose); handle closures.

[kasperl, 2013/01/29 15:02:34]

; -> :

[karlklose, 2013/01/30 12:01:19]

Done.

+      return true;
+    }
+    InterfaceType type = cls.computeType(compiler);
+    type = type.asInstanceOf(check);
+    if (type == null) return true;

[kasperl, 2013/01/29 15:02:34]

Add a comment that explains why it's correct to return true here and in the next
case. Feel free to keep it short.

[karlklose, 2013/01/30 12:01:19]

Done.

+
+    if (check.typeVariables.isEmpty || cls == check) {

[Johnni Winther, 2013/01/31 09:17:31]

Move this before the asInstanceOf check.

[karlklose, 2013/02/01 07:36:35]

Done.

+      return true;
+    }
+    Link<DartType> variables = cls.typeVariables;

[kasperl, 2013/01/29 15:02:34]

Explain what you're looking for in this loop in a few sentences in a comment.

[karlklose, 2013/01/30 12:01:19]

Done.

+    Link<DartType> arguments = type.typeArguments;
+    bool identicalOrEmptyVariables = true;
+    while (!variables.isEmpty && !arguments.isEmpty) {
+      assert(variables.head.kind == TypeKind.TYPE_VARIABLE);

[Johnni Winther, 2013/01/31 09:17:31]

Why this assertion? (It is true!)

[karlklose, 2013/02/01 07:36:35]

Removed.

+      if (variables.head.element != arguments.head.element) {
+        identicalOrEmptyVariables = false;

[kasperl, 2013/01/29 15:02:34]

Wouldn't it be cleaner just to return false here? I would try to get rid of the
identicalOrEmptyVariables variable.

[karlklose, 2013/01/30 12:01:19]

Done.

+        break;
+      }
+      variables = variables.tail;
+      arguments = arguments.tail;
+    }
+    if (variables.isEmpty != arguments.isEmpty) {

[Johnni Winther, 2013/01/31 09:17:31]

If this is not the case it is an invariant breach on InterfaceType.

[karlklose, 2013/02/01 07:36:35]

I am not comparing type arguments to the same class here, so it may happen that
the length is different:
I compare cls.thisType.asInstanceOf(check).typeArguments with cls.typeVariables.

[Johnni Winther, 2013/02/01 08:09:11]

Ahh!

+      identicalOrEmptyVariables = false;
+    }
+    return identicalOrEmptyVariables;
+  }
+
+  // TODO(karlklose): rewrite to use js.Expressions.
+  /**
+   * Compute a JavaScript expression that describes the necessary substitution
+   * for type arguments in a subtype test.
+   *
+   * The result can be:
+   *  1) [:null:], if no substituted check is necessary, because the
+   *     type variables are the same or there are no type variables in the class
+   *     that is checked for.
+   *  2) A list expression describing the type arguments to be used in the
+   *     subtype check, if the type arguments to be used in the check do not
+   *     depend on the type arguments of the object.
+   *  3) A function mapping the type variables of the object to be checked to
+   *     a list expression.
+   */
+  String getSupertypeSubstitution(ClassElement cls, ClassElement check,
+                                  {alwaysGenerateFunction: false}) {
+    if (isTrivialSubstitution(cls, check)) return null;
+
+    // TODO(karlklose): maybe precompute this value and store it in typeChecks?
+    InterfaceType target = cls.computeType(compiler);
+    target = target.asInstanceOf(check);

[kasperl, 2013/01/29 15:02:34]

Move the asInstanceOf call to the line where you initialize target?

[karlklose, 2013/01/30 12:01:19]

The problem here is that asInstanceOf is declared on InterfaceType, not on
DartType. So these are actually two type assertions, and I changed it to two
variables.

+    String substitution = target.typeArguments
+        .mappedBy((type) => getTypeRepresentation(type, (v) => v.toString()))
+        .join(', ');
+    substitution = '[$substitution]';
+    if (cls.typeVariables.isEmpty && !alwaysGenerateFunction) {
+      return substitution;
+    } else {
+      String parameters = cls.typeVariables.toList().join(', ');
+      return 'function ($parameters) { return $substitution; }';
+    }
+  }
+
+  // TODO(karlklose): rewrite to use js.Expressions.
+  String getTypeRepresentation(DartType type, String onVariable(variable)) {
     StringBuffer builder = new StringBuffer();
     void build(DartType part) {
       if (part is TypeVariableType) {
-        builder.add('#');
-        onVariable(part);
+        builder.add(onVariable(part));
       } else {
         bool hasArguments = part is InterfaceType && !part.isRaw;
         Element element = part.element;
-        if (hasArguments) {
-          builder.add('[');
-        }
-        builder.add(getJsName(element));
-        if (!hasArguments) return;
-        InterfaceType interface = part;
-        for (DartType argument in interface.typeArguments) {
-          builder.add(', ');
-          build(argument);
+        if (element == compiler.dynamicClass) {
+          builder.add('null');
+        } else {

[kasperl, 2013/01/29 15:02:34]

I would probably split the case that has arguments out to get a single test of
the hasArguments variable (instead of two). I know that requires you to
duplicate the builder.add(getJsName(element)) part, but you could cache the
getJsName(element) result in a local variable.

[karlklose, 2013/01/30 12:01:19]

Done.

+          if (hasArguments) {
+            builder.add('[');
+          }
+          builder.add(getJsName(element));
+          if (!hasArguments) return;
+          InterfaceType interface = part;
+          for (DartType argument in interface.typeArguments) {
+            builder.add(', ');
+            build(argument);
+          }
+          builder.add(']');
         }
-        builder.add(']');
       }
     }
     build(type);