Merge the work on Generic Types Reification from 'dart-lang/reify' repo

pkg/kernel/lib/transformations/reify/transformation/transformer.dart

Index: pkg/kernel/lib/transformations/reify/transformation/transformer.dart
diff --git a/pkg/kernel/lib/transformations/reify/transformation/transformer.dart b/pkg/kernel/lib/transformations/reify/transformation/transformer.dart
new file mode 100644
index 0000000000000000000000000000000000000000..867248510fc833bc62779501b704cf075f34d517
--- /dev/null
+++ b/pkg/kernel/lib/transformations/reify/transformation/transformer.dart
@@ -0,0 +1,575 @@
+// Copyright (c) 2016, 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.
+
+library kernel.transformations.reify.transformation.transformer;
+
+import '../analysis/program_analysis.dart';
+import 'package:kernel/ast.dart';
+import 'binding.dart' show RuntimeLibrary;
+import 'builder.dart' show RuntimeTypeSupportBuilder;
+import 'dart:collection' show LinkedHashMap;
+import '../asts.dart';
+
+export 'binding.dart' show RuntimeLibrary;
+export 'builder.dart' show RuntimeTypeSupportBuilder;
+
+enum RuntimeTypeStorage {
+  none,
+  inheritedField,
+  field,
+  getter,
+}
+
+class TransformationContext {
+  /// Describes how the runtime type is stored on the object.
+  RuntimeTypeStorage runtimeTypeStorage;
+
+  /// Field added to store the runtime type if [runtimeType] is
+  /// [RuntimeTypeStorage.field].
+  Field runtimeTypeField;
+
+  /// The parameter for the type information introduced to the constructor or
+  /// to static initializers.
+  VariableDeclaration parameter;
+
+  /// A ordered collection of fields together with their initializers rewritten
+  /// to static initializer functions that can be used in the constructor's
+  /// initializer list.
+  /// The order is important because of possible side-effects in the
+  /// initializers.
+  LinkedHashMap<Field, Procedure> initializers;
+
+  // `true` if the visitor currently is in a field initializer, a initializer
+  // list of a constructor, or the body of a factory method. In these cases,
+  // type argument access is different than in an instance context, since `this`
+  // is not available.
+  bool inInitializer = false;
+
+  String toString() => "s: ${runtimeTypeStorage} f: $runtimeTypeField,"
+      " p: $parameter, i: $inInitializer";
+}
+
+abstract class DebugTrace {
+  static const bool debugTrace = false;
+
+  static const int lineLength = 80;
+
+  TransformationContext get context;
+
+  String getNodeLevel(TreeNode node) {
+    String level = "";
+    while (node != null && node is! Library) {
+      level = " $level";
+      node = node.parent;
+    }
+    return level;
+  }
+
+  String shorten(String s) {
+    return s.length > lineLength ? s.substring(0, lineLength) : s;
+  }
+
+  void trace(TreeNode node) {
+    if (debugTrace) {
+      String nodeText = node.toString().replaceAll("\n", " ");
+      print(shorten("trace:${getNodeLevel(node)}$context"
+          " [${node.runtimeType}] $nodeText"));
+    }
+  }
+}
+
+/// Rewrites a tree to remove generic types and runtime type checks and replace
+/// them with Dart objects.
+///
+/// Runtime types are stored in a field/getter called [runtimeTypeName] on the
+/// object, which for parameterized classes is initialized in the constructor.
+//  TODO(karlklose):
+//  - add a scoped namer
+//  - rewrite types (supertypes, implemented types)
+//  - rewrite as
+class ReifyVisitor extends Transformer with DebugTrace {
+  final RuntimeLibrary rtiLibrary;
+  final RuntimeTypeSupportBuilder builder;
+  final ProgramKnowledge knowledge;
+
+  ReifyVisitor(this.rtiLibrary, this.builder, this.knowledge,
+      [this.libraryToTransform]);
+
+  /// If not null, the transformation will only be applied to classes declared
+  /// in this library.
+  final Library libraryToTransform;
+
+  // TODO(karlklose): find a way to get rid of this state in the visitor.
+  TransformationContext context;
+
+  bool libraryShouldBeTransformed(Library library) {
+    return libraryToTransform == null || libraryToTransform == library;
+  }
+
+  bool needsTypeInformation(Class cls) {
+    return !isObject(cls) &&
+        !rtiLibrary.contains(cls) &&
+        libraryShouldBeTransformed(cls.enclosingLibrary);
+  }
+
+  bool usesTypeGetter(Class cls) {
+    return cls.typeParameters.isEmpty;
+  }
+
+  bool isObject(Class cls) {
+    // TODO(karlklose): use [CoreTypes].
+    return "$cls" == 'dart.core::Object';
+  }
+
+  Initializer addTypeAsArgument(initializer) {
+    assert(initializer is SuperInitializer ||
+        initializer is RedirectingInitializer);
+    Class cls = getEnclosingClass(initializer.target);
+    if (needsTypeInformation(cls) && !usesTypeGetter(cls)) {
+      // If the current class uses a getter for type information, we did not add
+      // a parameter to the constructor, but we can pass `null` as the value to
+      // initialize the type field, since it will be shadowed by the getter.
+      Expression type = (context.parameter != null)
+          ? new VariableGet(context.parameter)
+          : new NullLiteral();
+      builder.insertAsFirstArgument(initializer.arguments, type);
+    }
+    return initializer;
+  }
+
+  Expression interceptInstantiation(
+      InvocationExpression invocation, Member target) {
+    Class targetClass = target.parent;
+    Library targetLibrary = targetClass.parent;
+    Library currentLibrary = getEnclosingLibrary(invocation);
+    if (libraryShouldBeTransformed(currentLibrary) &&
+        !libraryShouldBeTransformed(targetLibrary) &&
+        !rtiLibrary.contains(target)) {
+      return builder.attachTypeToConstructorInvocation(invocation, target);
+    }
+    return invocation;
+  }
+
+  Expression createRuntimeType(DartType type) {
+    if (context?.inInitializer == true) {
+      // In initializer context, the instance type is provided in
+      // `context.parameter` as there is no `this`.
+      return builder.createRuntimeType(type, typeContext: context.parameter);
+    } else {
+      return builder.createRuntimeType(type);
+    }
+  }
+
+  TreeNode defaultTreeNode(TreeNode node) {
+    trace(node);
+    return super.defaultTreeNode(node);
+  }
+
+  Expression visitStaticInvocation(StaticInvocation invocation) {
+    trace(invocation);
+
+    invocation.transformChildren(this);
+
+    Procedure target = invocation.target;
+    if (target == rtiLibrary.reifyFunction) {
+      /// Rewrite calls to reify(TypeLiteral) to a reified type.
+      TypeLiteral literal = invocation.arguments.positional.single;
+      return createRuntimeType(literal.type);
+    } else if (target.kind == ProcedureKind.Factory) {
+      // Intercept calls to factories of classes we do not transform
+      return interceptInstantiation(invocation, target);
+    }
+    return invocation;
+  }
+
+  Library visitLibrary(Library library) {
+    trace(library);
+
+    if (libraryShouldBeTransformed(library)) {
+      library.transformChildren(this);
+    }
+    return library;
+  }
+
+  Expression visitConstructorInvocation(ConstructorInvocation invocation) {
+    invocation.transformChildren(this);
+    return interceptInstantiation(invocation, invocation.target);
+  }
+
+  Member getStaticInvocationTarget(InvocationExpression invocation) {
+    if (invocation is ConstructorInvocation) {
+      return invocation.target;
+    } else if (invocation is StaticInvocation) {
+      return invocation.target;
+    } else {
+      throw "Unexpected InvocationExpression $invocation.";
+    }
+  }
+
+  bool isInstantiation(TreeNode invocation) {
+    return invocation is ConstructorInvocation ||
+        invocation is StaticInvocation &&
+            invocation.target.kind == ProcedureKind.Factory;
+  }
+
+  bool isTypeVariable(DartType type) => type is TypeParameterType;
+
+  /// Add the runtime type as an extra argument to constructor invocations.
+  Arguments visitArguments(Arguments arguments) {
+    trace(arguments);
+
+    arguments.transformChildren(this);
+    TreeNode parent = arguments.parent;
+    if (isInstantiation(parent)) {
+      Class targetClass = getEnclosingClass(getStaticInvocationTarget(parent));
+      // Do not add the extra argument if the class does not need a type member
+      // or if it can be implemented as a getter.
+      if (!needsTypeInformation(targetClass) || usesTypeGetter(targetClass)) {
+        return arguments;
+      }
+
+      List<DartType> typeArguments = arguments.types;
+
+      Expression type =
+          createRuntimeType(new InterfaceType(targetClass, typeArguments));
+
+      builder.insertAsFirstArgument(arguments, type);
+    }
+    return arguments;
+  }
+
+  Field visitField(Field field) {
+    trace(field);
+
+    visitDartType(field.type);
+    for (Expression annotation in field.annotations) {
+      annotation.accept(this);
+    }
+    // Do not visit initializers, they have already been transformed when the
+    // class was handled.
+    return field;
+  }
+
+  /// Go through all initializers of fields and record a static initializer
+  /// function, if necessary.
+  void rewriteFieldInitializers(Class cls) {
+    assert(context != null);
+    context.initializers = new LinkedHashMap<Field, Procedure>();
+    List<Field> fields = cls.fields;
+    bool initializerRewritten = false;
+    for (Field field in fields) {
+      if (!initializerRewritten && knowledge.usedParameters(field).isEmpty) {
+        // This field needs no static initializer.
+        continue;
+      }
+
+      Expression initializer = field.initializer;
+      if (initializer == null || field.isStatic) continue;
+      // Declare a new variable that holds the type information and can be
+      // used to access type variables in initializer context.
+      // TODO(karlklose): some fields do not need the parameter.
+      VariableDeclaration typeObject = new VariableDeclaration(r"$type");
+      context.parameter = typeObject;
+      context.inInitializer = true;
+      // Translate the initializer while keeping track of whether there was
+      // already an initializers that required type information in
+      // [typeVariableUsedInInitializer].
+      initializer = initializer.accept(this);
+      context.parameter = null;
+      context.inInitializer = false;
+      // Create a static initializer function from the translated initializer
+      // expression and record it.
+      Name name = new Name("\$init\$${field.name.name}");
+      Statement body = new ReturnStatement(initializer);
+      Procedure staticInitializer = new Procedure(
+          name,
+          ProcedureKind.Method,
+          new FunctionNode(body,
+              positionalParameters: <VariableDeclaration>[typeObject]),
+          isStatic: true,
+          fileUri: cls.fileUri);
+      context.initializers[field] = staticInitializer;
+      // Finally, remove the initializer from the field.
+      field.initializer = null;
+    }
+  }
+
+  bool inheritsTypeProperty(Class cls) {
+    assert(needsTypeInformation(cls));
+    Class superclass = cls.superclass;
+    return needsTypeInformation(superclass);
+  }
+
+  Class visitClass(Class cls) {
+    trace(cls);
+
+    if (needsTypeInformation(cls)) {
+      context = new TransformationContext();
+      List<TypeParameter> typeParameters = cls.typeParameters;
+      if (usesTypeGetter(cls)) {
+        assert(typeParameters.isEmpty);
+        context.runtimeTypeStorage = RuntimeTypeStorage.getter;
+        Member getter = builder.createGetter(rtiLibrary.runtimeTypeName,
+            createRuntimeType(cls.rawType), cls, rtiLibrary.typeType);
+        cls.addMember(getter);
+      } else if (!inheritsTypeProperty(cls)) {
+        context.runtimeTypeStorage = RuntimeTypeStorage.field;
+        // TODO(karlklose): should we add the field to [Object]?
+        context.runtimeTypeField = new Field(rtiLibrary.runtimeTypeName,
+            fileUri: cls.fileUri, isFinal: true, type: rtiLibrary.typeType);
+        cls.addMember(context.runtimeTypeField);
+      } else {
+        context.runtimeTypeStorage = RuntimeTypeStorage.inheritedField;
+      }
+
+      for (int i = 0; i < typeParameters.length; ++i) {
+        TypeParameter variable = typeParameters[i];
+        cls.addMember(builder.createTypeVariableGetter(cls, variable, i));
+      }
+
+      // Tag the class as supporting the runtime type getter.
+      InterfaceType interfaceTypeForSupertype =
+          new InterfaceType(rtiLibrary.markerClass);
+      cls.implementedTypes.add(new Supertype(
+          interfaceTypeForSupertype.classNode,
+          interfaceTypeForSupertype.typeArguments));
+
+      // Before transforming the parts of the class declaration, rewrite field
+      // initializers that use type variables (or that would be called after one
+      // that does) to static functions that can be used from constructors.
+      rewriteFieldInitializers(cls);
+
+      // Add properties for declaration tests.
+      for (Class test in knowledge.classTests) {
+        if (test == rtiLibrary.markerClass) continue;
+
+        Procedure tag = builder.createGetter(
+            builder.getTypeTestTagName(test),
+            new BoolLiteral(isSuperClass(test, cls)),
+            cls,
+            builder.coreTypes.boolClass.rawType);
+        cls.addMember(tag);
+      }
+
+      // Add a runtimeType getter.
+      if (!usesTypeGetter(cls) && !inheritsTypeProperty(cls)) {
+        cls.addMember(new Procedure(
+            new Name("runtimeType"),
+            ProcedureKind.Getter,
+            new FunctionNode(
+                new ReturnStatement(new DirectPropertyGet(
+                    new ThisExpression(), context.runtimeTypeField)),
+                returnType: builder.coreTypes.typeClass.rawType),
+            fileUri: cls.fileUri));
+      }
+    }
+
+    cls.transformChildren(this);
+
+    // Add the static initializer functions. They have already been transformed.
+    if (context?.initializers != null) {
+      context.initializers.forEach((_, Procedure initializer) {
+        cls.addMember(initializer);
+      });
+    }
+
+    // TODO(karlklose): clear type arguments later, the order of class
+    // transformations otherwise influences the result.
+    // cls.typeParameters.clear();
+    context = null;
+    return cls;
+  }
+
+  // TODO(karlklose): replace with a structure that can answer also the question
+  // which tags must be overriden due to different values.
+  /// Returns `true` if [a] is a declaration used in a supertype of [b].
+  bool isSuperClass(Class a, Class b) {
+    if (b == null) return false;
+    if (a == b) return true;
+
+    if (isSuperClass(a, b.superclass)) {
+      return true;
+    }
+
+    Iterable<Class> interfaceClasses = b.implementedTypes
+        .map((Supertype type) => type.classNode)
+        .where((Class cls) => cls != rtiLibrary.markerClass);
+    return interfaceClasses
+        .any((Class declaration) => isSuperClass(a, declaration));
+  }
+
+  bool isConstructorOrFactory(TreeNode node) {
+    return isFactory(node) || node is Constructor;
+  }
+
+  bool isFactory(TreeNode node) {
+    return node is Procedure && node.kind == ProcedureKind.Factory;
+  }
+
+  bool needsParameterForRuntimeType(TreeNode node) {
+    if (!isConstructorOrFactory(node)) return false;
+
+    RuntimeTypeStorage access = context.runtimeTypeStorage;
+    assert(access != RuntimeTypeStorage.none);
+    return access == RuntimeTypeStorage.field ||
+        access == RuntimeTypeStorage.inheritedField;
+  }
+
+  FunctionNode visitFunctionNode(FunctionNode node) {
+    trace(node);
+
+    // If we have a [TransformationContext] with a runtime type field and we
+    // translate a constructor or factory, we need a parameter that the code of
+    // initializers or the factory body can use to access type arguments.
+    // The parameter field in the context will be reset in the visit-method of
+    // the parent.
+    if (context != null && needsParameterForRuntimeType(node.parent)) {
+      assert(context.parameter == null);
+      // Create the parameter and insert it as the function's first parameter.
+      context.parameter = new VariableDeclaration(
+          rtiLibrary.runtimeTypeName.name,
+          type: rtiLibrary.typeType);
+      context.parameter.parent = node;
+      node.positionalParameters.insert(0, context.parameter);
+      node.requiredParameterCount++;
+    }
+    node.transformChildren(this);
+    return node;
+  }
+
+  SuperInitializer visitSuperInitializer(SuperInitializer initializer) {
+    initializer.transformChildren(this);
+    return addTypeAsArgument(initializer);
+  }
+
+  RedirectingInitializer visitRedirectingInitializer(
+      RedirectingInitializer initializer) {
+    initializer.transformChildren(this);
+    return addTypeAsArgument(initializer);
+  }
+
+  Procedure visitProcedure(Procedure procedure) {
+    trace(procedure);
+
+    transformList(procedure.annotations, this, procedure.parent);
+    // Visit the function body in a initializing context, if it is a factory.
+    context?.inInitializer = isFactory(procedure);
+    procedure.function?.accept(this);
+    context?.inInitializer = false;
+
+    context?.parameter = null;
+    return procedure;
+  }
+
+  Constructor visitConstructor(Constructor constructor) {
+    trace(constructor);
+
+    transformList(constructor.annotations, this, constructor);
+    if (constructor.function != null) {
+      constructor.function = constructor.function.accept(this);
+      constructor.function?.parent = constructor;
+    }
+
+    context?.inInitializer = true;
+    transformList(constructor.initializers, this, constructor);
+    context?.inInitializer = false;
+
+    if (context != null) {
+      if (context.runtimeTypeStorage == RuntimeTypeStorage.field) {
+        // Initialize the runtime type field with value given in the additional
+        // constructor parameter.
+        assert(context.parameter != null);
+        Initializer initializer = new FieldInitializer(
+            context.runtimeTypeField, new VariableGet(context.parameter));
+        initializer.parent = constructor;
+        constructor.initializers.insert(0, initializer);
+      }
+      if (context.initializers != null) {
+        // For each field that needed a static initializer function, initialize
+        // the field by calling the function.
+        List<Initializer> fieldInitializers = <Initializer>[];
+        context.initializers.forEach((Field field, Procedure initializer) {
+          assert(context.parameter != null);
+          Arguments argument =
+              new Arguments(<Expression>[new VariableGet(context.parameter)]);
+          fieldInitializers.add(new FieldInitializer(
+              field, new StaticInvocation(initializer, argument)));
+        });
+        constructor.initializers.insertAll(0, fieldInitializers);
+      }
+      context.parameter = null;
+    }
+
+    return constructor;
+  }
+
+  /// Returns `true` if the given type can be tested using type test tags.
+  ///
+  /// This implies that there are no subtypes of the [type] that are not
+  /// transformed.
+  bool typeSupportsTagTest(InterfaceType type) {
+    return needsTypeInformation(type.classNode);
+  }
+
+  Expression visitIsExpression(IsExpression expression) {
+    trace(expression);
+
+    expression.transformChildren(this);
+
+    if (getEnclosingLibrary(expression) == rtiLibrary.interceptorsLibrary) {
+      // In the interceptor library we need actual is-checks at the moment.
+      return expression;
+    }
+
+    Expression target = expression.operand;
+    DartType type = expression.type;
+
+    if (type is InterfaceType && typeSupportsTagTest(type)) {
+      assert(knowledge.classTests.contains(type.classNode));
+      bool checkArguments =
+          type.typeArguments.any((DartType type) => type is! DynamicType);
+      Class declaration = type.classNode;
+      VariableDeclaration typeExpression =
+          new VariableDeclaration(null, initializer: createRuntimeType(type));
+      VariableDeclaration targetValue =
+          new VariableDeclaration(null, initializer: target);
+      Expression markerClassTest = new IsExpression(
+          new VariableGet(targetValue), rtiLibrary.markerClass.rawType);
+      Expression tagCheck = new PropertyGet(new VariableGet(targetValue),
+          builder.getTypeTestTagName(declaration));
+      Expression check = new LogicalExpression(markerClassTest, "&&", tagCheck);
+      if (checkArguments) {
+        // TODO(karlklose): support a direct argument check, we already checked
+        // the declaration.
+        Expression uninterceptedCheck = new Let(
+            typeExpression,
+            builder.createIsSubtypeOf(
+                new VariableGet(targetValue), new VariableGet(typeExpression),
+                targetHasTypeProperty: true));
+        check = new LogicalExpression(check, "&&", uninterceptedCheck);
+      }
+      return new Let(targetValue, check);
+    } else {
+      return builder.createIsSubtypeOf(target, createRuntimeType(type));
+    }
+  }
+
+  Expression visitListLiteral(ListLiteral node) {
+    trace(node);
+    node.transformChildren(this);
+    return builder.callAttachType(
+        node,
+        new InterfaceType(
+            builder.coreTypes.listClass, <DartType>[node.typeArgument]));
+  }
+
+  Expression visitMapLiteral(MapLiteral node) {
+    trace(node);
+    node.transformChildren(this);
+    return builder.callAttachType(
+        node,
+        new InterfaceType(builder.coreTypes.mapClass,
+            <DartType>[node.keyType, node.valueType]));
+  }
+}