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..08ab0c07578abb1c3bd5b10d0a657ec31bf1db93 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,27 @@ 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() {
-    Set<ClassElement> instantiatedArguments = new Set<ClassElement>();
-    for (DartType type in compiler.codegenWorld.instantiatedTypes) {
-      addAllInterfaceTypeArguments(type, instantiatedArguments);
-    }
+  TypeChecks cachedRequiredChecks;
 
-    Set<ClassElement> checkedArguments = new Set<ClassElement>();
-    for (DartType type in compiler.enqueuer.codegen.universe.isChecks) {
-      addAllInterfaceTypeArguments(type, checkedArguments);
-    }
+  TypeChecks getRequiredChecks() {
+    if (cachedRequiredChecks != null) return cachedRequiredChecks;
+
+    // Get all types used in type arguments of instantiated types.
+    Set<ClassElement> instantiatedArguments = getInstantiatedArguments();
+
+    // Collect all type arguments used in is-checks.
+    Set<ClassElement> checkedArguments = getCheckedArguments();
 
+    // 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 +62,48 @@ class RuntimeTypeInformation {
         }
       }
     }
+    return cachedRequiredChecks = requiredChecks;
+  }
+
+  /**
+   * Collects all types used in type arguments of instantiated types.
+   *
+   * 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> getInstantiatedArguments() {
+    Set<ClassElement> instantiatedArguments = new Set<ClassElement>();
+    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);
+      }
+    }
+    return instantiatedArguments;
+  }
 
-    return requiredChecks;
+  /// Collects all type arguments used in is-checks.
+  Set<ClassElement> getCheckedArguments() {
+    Set<ClassElement> checkedArguments = new Set<ClassElement>();
+    for (DartType type in isChecks) {
+      addAllInterfaceTypeArguments(type, checkedArguments);
+    }
+    return checkedArguments;
+  }
+
+  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 +111,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 +148,108 @@ 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.
+      return true;
+    }
+    InterfaceType type = cls.computeType(compiler);
+    type = type.asInstanceOf(check);
+
+    // [type] is not a subtype of [check]. we do not generate a check and do not
+    // need a substitution.
+    if (type == null) return true;
+
+    // If there are no type variables or the type is the same, we do not need
+    // a substitution.
+    if (check.typeVariables.isEmpty || cls == check) {
+      return true;
+    }
+
+    // Run through both lists of type variables and check if the type variables
+    // are identical at each position. If they are not, we need to calculate a
+    // substitution function.
+    Link<DartType> variables = cls.typeVariables;
+    Link<DartType> arguments = type.typeArguments;
+    while (!variables.isEmpty && !arguments.isEmpty) {
+      assert(variables.head.kind == TypeKind.TYPE_VARIABLE);
+      if (variables.head.element != arguments.head.element) {
+        return false;
+      }
+      variables = variables.tail;
+      arguments = arguments.tail;
+    }
+    if (variables.isEmpty != arguments.isEmpty) {
+      return false;
+    }
+    return true;
+  }
+
+  // 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 type = cls.computeType(compiler);
+    InterfaceType target = type.asInstanceOf(check);
+    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 {
+          String name = getJsName(element);
+          if (!hasArguments) {
+            builder.add(name);
+          } else {
+            builder.add('[');
+            builder.add(name);
+            InterfaceType interface = part;
+            for (DartType argument in interface.typeArguments) {
+              builder.add(', ');
+              build(argument);
+            }
+            builder.add(']');
+          }
         }
-        builder.add(']');
       }
     }
     build(type);