Represent runtime type information as nested lists.

sdk/lib/_internal/compiler/implementation/ssa/builder.dart

 // Copyright (c) 2012, 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.
 
 part of ssa;
 
 /**
  * A special element for the extra parameter taken by intercepted
  * methods. We need to override [Element.computeType] because our
  * optimizers may look at its declared type.
@@ skipping 2615 matching lines @@
 
   void pushInvokeHelper4(Element helper, HInstruction a0, HInstruction a1,
                          HInstruction a2, HInstruction a3) {
     HInstruction reference = new HStatic(helper);
     add(reference);
     List<HInstruction> inputs = <HInstruction>[reference, a0, a1, a2, a3];
     HInstruction result = new HInvokeStatic(inputs);
     push(result);
   }
 
+  createForeign(String code, String type, List<HInstruction> inputs) {

[ngeoffray, 2012/12/06 23:21:45]

HForeign createForeign

[karlklose, 2012/12/07 07:46:35]

Done.

+    return new HForeign(new LiteralDartString(code),
+                        new LiteralDartString(type),
+                        inputs);
+  }
+
+  HInstruction getRuntimeTypeInfo(HInstruction target) {
+    pushInvokeHelper1(interceptors.getGetRuntimeTypeInfo(), target);
+    return pop();
+  }
+
+  // TODO(karlklose): change construction of the representations to be GVN'able.

[ngeoffray, 2012/12/06 23:21:45]

You can also reference the bug number.

[karlklose, 2012/12/07 07:46:35]

Done.

+  List<HInstruction> buildTypeArgumentRepresentations(DartType type) {
+    HInstruction createForeignArray(String code, inputs) {
+      return createForeign(code, 'JSArray', inputs);

[ngeoffray, 2012/12/06 23:21:45]

Should be '=List' but i plan on fixing that.

[karlklose, 2012/12/07 07:46:35]

I changed it to '=List'.

+    }
+    HInstruction typeInfo;
+
+    /// Helper to create an instruction that contains the runtime value of
+    /// the type variable [variable].
+    HInstruction getTypeArgument(TypeVariableType variable) {
+      if (typeInfo == null) {
+        typeInfo = getRuntimeTypeInfo(localsHandler.readThis());
+      }
+      int intIndex = RuntimeTypeInformation.getTypeVariableIndex(variable);
+      HInstruction index = graph.addConstantInt(intIndex, constantSystem);
+      return createForeignArray('#[#]', <HInstruction>[typeInfo, index]);
+    }
+
+    // Compute the representation of the type arguments, including access
+    // to the runtime type information for type variables as instructions.
+    HInstruction representations;
+    if (type.element.isTypeVariable()) {
+      return <HInstruction>[getTypeArgument(type)];
+    } else {
+      assert(type.element.isClass());
+      List<HInstruction> arguments = <HInstruction>[];
+      InterfaceType interface = type;
+      for (DartType argument in interface.typeArguments) {
+        List<HInstruction> inputs = <HInstruction>[];
+        String template = rti.getTypeRepresentation(argument, (variable) {
+          HInstruction runtimeType = getTypeArgument(variable);
+          add(runtimeType);
+          inputs.add(runtimeType);
+        });
+        HInstruction representation = createForeignArray(template, inputs);
+        add(representation);
+        arguments.add(representation);
+      }
+      return arguments;
+    }
+  }
+
   visitOperatorSend(node) {
     assert(node.selector is Operator);
     if (!methodInterceptionEnabled) {
       visitDynamicSend(node);
       return;
     }
 
     Operator op = node.selector;
     if (const SourceString("[]") == op.source) {
       HStatic target = new HStatic(interceptors.getIndexInterceptor());
@@ skipping 15 matching lines @@
       HInstruction expression = pop();
       Node argument = node.arguments.head;
       TypeAnnotation typeAnnotation = argument.asTypeAnnotation();
       bool isNot = false;
       // TODO(ngeoffray): Duplicating pattern in resolver. We should
       // add a new kind of node.
       if (typeAnnotation == null) {
         typeAnnotation = argument.asSend().receiver;
         isNot = true;
       }
-
       DartType type = elements.getType(typeAnnotation);
       if (type.isMalformed) {
         String reasons = fetchReasonsFromMalformedType(type);
         if (compiler.enableTypeAssertions) {
           generateMalformedSubtypeError(node, expression, type, reasons);
         } else {
           generateRuntimeError(node, '$type is malformed: $reasons');
         }
         return;
       }
-      HInstruction typeInfo = null;
-      if (RuntimeTypeInformation.hasTypeArguments(type)) {
-        pushInvokeHelper1(interceptors.getGetRuntimeTypeInfo(), expression);
-        typeInfo = pop();
+      if (type.element.isTypeVariable()) {
+        // TODO(karlklose): remove this check when the backend can deal with
+        // checks of the form [:o is T:] where [:T:] is a type variable.
+        stack.add(graph.addConstantBool(true, constantSystem));
+        return;
       }
-      if (type.element.isTypeVariable()) {
-        // TODO(karlklose): We currently answer true to any is check
-        // involving a type variable -- both is T and is !T -- until
-        // we have a proper implementation of reified generics.
-        stack.add(graph.addConstantBool(true, constantSystem));
+
+      HInstruction instruction;
+      if (RuntimeTypeInformation.hasTypeArguments(type) ||
+          type.element.isTypeVariable()) {

[ngeoffray, 2012/12/06 23:21:45]

I don't think this can happen (see line 2734 and 2738).

[karlklose, 2012/12/07 07:46:35]

You are right, this is a left-over from trying to handle both in this CL.
Removed.

+        HInstruction typeInfo = getRuntimeTypeInfo(expression);
+        // TODO(karlklose): make isSubtype a HInstruction to enable
+        // optimizations?

[ngeoffray, 2012/12/06 23:21:45]

No, I think we need to put compiler flags on the method.

[karlklose, 2012/12/07 07:46:35]

I will remove the comment. Let's chat about dartbug.com/7182 next week.

+        Element helper = compiler.findHelper(const SourceString('isSubtype'));
+        HInstruction isSubtype = new HStatic(helper);
+        add(isSubtype);
+        // Build a list of representations for the type arguments.
+        List<HInstruction> representations =
+            buildTypeArgumentRepresentations(type);
+        // For each type argument, build a call to isSubtype, with the type
+        // argument as first and the representation of the tested type as
+        // second argument.
+        List<HInstruction> checks = <HInstruction>[];
+        int index = 0;
+        representations.forEach((HInstruction representation) {
+          HInstruction position = graph.addConstantInt(index, constantSystem);
+          // Get the index'th type argument from the runtime type information.
+          HInstruction typeArgument =
+              createForeign('#[#]', 'Object', [typeInfo, position]);
+          add(typeArgument);
+          // Create the call to isSubtype.
+          List<HInstruction> inputs =
+              <HInstruction>[isSubtype, typeArgument, representation];
+          HInstruction call = new HInvokeStatic(inputs);
+          add(call);
+          checks.add(call);
+          index++;
+        });
+        instruction = new HIs.withArgumentChecks(type, expression, checks);
       } else {
-        HInstruction instruction;
-        if (typeInfo != null) {
-          instruction = new HIs.withTypeInfoCall(type, expression, typeInfo);
-        } else {
-          instruction = new HIs(type, expression);
-        }
-        if (isNot) {
-          add(instruction);
-          instruction = new HNot(instruction);
-        }
-        push(instruction);
+        instruction = new HIs(type, expression);
       }
+      if (isNot) {
+        add(instruction);
+        instruction = new HNot(instruction);
+      }
+      push(instruction);
     } else if (const SourceString("as") == op.source) {
       visit(node.receiver);
       HInstruction expression = pop();
       Node argument = node.arguments.head;
       TypeAnnotation typeAnnotation = argument.asTypeAnnotation();
       DartType type = elements.getType(typeAnnotation);
       HInstruction converted = expression.convertType(
           compiler, type, HTypeConversion.CAST_TYPE_CHECK);
       if (converted != expression) add(converted);
       stack.add(converted);
@@ skipping 382 matching lines @@
    */
   HInstruction analyzeTypeArgument(DartType argument, Node currentNode) {
     assert(invariant(currentNode,
                      !compiler.enableTypeAssertions || !argument.isMalformed,
                      message: '$argument is malformed in checked mode'));
     if (argument == compiler.types.dynamicType || argument.isMalformed) {
       // Represent [dynamic] as [null].
       return graph.addConstantNull(constantSystem);
     }
 
-    // These variables are shared between invocations of the helper methods.
+    // These variables are shared between invocations of the helper.
     HInstruction typeInfo;
-    StringBuffer template = new StringBuffer();
     List<HInstruction> inputs = <HInstruction>[];
 
     /**
      * Helper to create an instruction that gets the value of a type variable.
      */
     void addTypeVariableReference(TypeVariableType type) {
       Element member = work.element;
       if (member.enclosingElement.isClosure()) {
         ClosureClassElement closureClass = member.enclosingElement;
         member = closureClass.methodElement;
         member = member.getOutermostEnclosingMemberOrTopLevel();
       }
       if (member.isFactoryConstructor()) {
         // The type variable is stored in a parameter of the factory.
         inputs.add(localsHandler.readLocal(type.element));
       } else if (member.isInstanceMember()
                  || member.isGenerativeConstructor()) {
         // The type variable is stored in [this].
         if (typeInfo == null) {
           pushInvokeHelper1(interceptors.getGetRuntimeTypeInfo(),
                             localsHandler.readThis());
           typeInfo = pop();
         }
         int index = RuntimeTypeInformation.getTypeVariableIndex(type);
-        HInstruction foreign = new HForeign(
-            new LiteralDartString('#[$index]'),
-            new LiteralDartString('String'),
-            <HInstruction>[typeInfo]);
+        HInstruction foreign = createForeign('#[$index]', 'String',
+                                             <HInstruction>[typeInfo]);
         add(foreign);
         inputs.add(foreign);
       } else {
         // TODO(ngeoffray): Match the VM behavior and throw an
         // exception at runtime.
         compiler.cancel('Unimplemented unresolved type variable',
                         node: currentNode);
       }
     }
 
-    /**
-     * Helper to build an instruction that builds the string representation for
-     * this type, where type variables are substituted by their runtime value.
-     *
-     * Examples:
-     *   Type            Template                Inputs
-     *   int             'int'                   []
-     *   C<int, int>     'C<int, int>'           []
-     *   Var             #                       [getRuntimeType(this).Var]
-     *   C<int, D<Var>>  'C<int, D<' + # + '>>'  [getRuntimeType(this).Var]
-     */
-    void buildTypeString(DartType type, {isInQuotes: false}) {
-      if (type is TypeVariableType) {
-        addTypeVariableReference(type);
-        template.add(isInQuotes ? "' + # +'" : "#");
-      } else if (type is InterfaceType) {
-        bool isFirstVariable = true;
-        InterfaceType interfaceType = type;
-        bool hasTypeArguments = !interfaceType.isRaw;
-        if (!isInQuotes) template.add("'");
-        template.add(backend.namer.getName(type.element));
-        if (hasTypeArguments) {
-          template.add("<");
-          for (DartType argument in interfaceType.typeArguments) {
-            if (!isFirstVariable) {
-              template.add(", ");
-            } else {
-              isFirstVariable = false;
-            }
-            buildTypeString(argument, isInQuotes: true);
-          }
-          template.add(">");
-        }
-        if (!isInQuotes) template.add("'");
-      } else {
-        assert(type is TypedefType);
-        if (!isInQuotes) template.add("'");
-        template.add(backend.namer.getName(argument.element));
-        if (!isInQuotes) template.add("'");
-      }
-    }
-
-    buildTypeString(argument, isInQuotes: false);
-    HInstruction result =
-        new HForeign(new LiteralDartString("$template"),
-            new LiteralDartString('String'),
-            inputs);
+    String template = rti.getTypeRepresentation(argument,
+                                                addTypeVariableReference);
+    HInstruction result = createForeign(template, 'String', inputs);
     add(result);
     return result;
   }
 
   void handleListConstructor(InterfaceType type,
                              Node currentNode,
                              HInstruction newObject) {
     if (!compiler.world.needsRti(type.element)) return;
     List<HInstruction> inputs = <HInstruction>[];
     if (!type.isRaw) {
@@ skipping 1756 matching lines @@
           new HSubGraphBlockInformation(elseBranch.graph));
 
     HBasicBlock conditionStartBlock = conditionBranch.block;
     conditionStartBlock.setBlockFlow(info, joinBlock);
     SubGraph conditionGraph = conditionBranch.graph;
     HIf branch = conditionGraph.end.last;
     assert(branch is HIf);
     branch.blockInformation = conditionStartBlock.blockFlow;
   }
 }