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) {
+    return new HForeign(new LiteralDartString(code),
+                        new LiteralDartString(type),
+                        inputs);
+  }
+
+  List<HInstruction> buildRepresentations(DartType type) {

[kasperl, 2012/12/06 09:51:04]

Maybe give this function a more telling name? Also consider if we could be
constructing the representations using instructions that are GVN'able. Whenever
you use foreign code we don't know anything about what it does (side-effects,
etc.) so using something simpler might be better. Calling "unknown" static
functions has the same problem.

[karlklose, 2012/12/06 13:30:03]

Renamed and added a comment for making the constructed representations GVN'able.

+    HInstruction createForeignArray(String code, inputs) {
+      return createForeign(code, 'JSArray', inputs);
+    }
+    HInstruction typeInfo;
+
+    /// Helper to create an instruction that contains the runtime value of
+    /// the type variable [variable].
+    HInstruction getTypeArgument(TypeVariableType variable) {
+      if (typeInfo == null) {
+        HInstruction context = localsHandler.readThis();
+        pushInvokeHelper1(interceptors.getGetRuntimeTypeInfo(), context);
+        typeInfo = pop();
+      }
+      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)) {
+      if (type.element.isTypeVariable()) {
+        // TODO(karlklose): remove this check when the backend can deal with it.

[kasperl, 2012/12/06 09:51:04]

Expand the comment to explain what you're waiting for. It's not clear to me what
situation the backend doesn't handle nicely.

[karlklose, 2012/12/06 13:30:03]

Done.

+        stack.add(graph.addConstantBool(true, constantSystem));
+        return;
+      }
+
+      HInstruction instruction;
+      if (RuntimeTypeInformation.hasTypeArguments(type) ||
+          type.element.isTypeVariable()) {
         pushInvokeHelper1(interceptors.getGetRuntimeTypeInfo(), expression);

[kasperl, 2012/12/06 09:51:04]

Could this code be put in a separate helper function? I think that would help
the readability and you wouldn't need to have an uninitialized instruction
variable.

[karlklose, 2012/12/06 13:30:03]

Done.

-        typeInfo = pop();
+        HInstruction typeInfo = pop();
+        Element helper = compiler.findHelper(const SourceString('isSubtype'));

[kasperl, 2012/12/06 09:51:04]

Would it make sense to have a separate HIsSubtype node that we could potentially
GVN, hoist and share?

[karlklose, 2012/12/06 13:30:03]

I am not sure how much work it is to do it, but I added a TODO and will
investigate making the builder output smaller.

+        HInstruction isSubtype = new HStatic(helper);
+        add(isSubtype);
+        List<HInstruction> representations = buildRepresentations(type);
+        List<HInstruction> checks = <HInstruction>[];
+        int index = 0;
+        representations.forEach((HInstruction representation) {

[kasperl, 2012/12/06 09:51:04]

Add a comment that explains the code you're building here.

[karlklose, 2012/12/06 13:30:03]

Done.

+          HInstruction position = graph.addConstantInt(index, constantSystem);
+          HInstruction typeArgument =

[kasperl, 2012/12/06 09:51:04]

I wonder if we should be creating something that we could GVN? Nicolas has been
toying with simplifying HIndex so maybe we should be able to use that in more
places?

[karlklose, 2012/12/06 13:30:03]

As said above, I'll look into better code generation in a later CL.

+              createForeign('#[#]', 'Object', [typeInfo, position]);
+          add(typeArgument);
+          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 {
+        instruction = new HIs(type, expression);
       }
-      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));
-      } 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);
+      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.
+    createForeignString(template, inputs) {

[kasperl, 2012/12/06 09:51:04]

Use createForeign?

[karlklose, 2012/12/06 13:30:03]

Done.

+      return new HForeign(new LiteralDartString(template),
+                          new LiteralDartString('String'),
+                          inputs);
+    }
+
+    // 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 = createForeignString('#[$index]',
+                                                   <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 = createForeignString(template, 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;
   }
 }