Substitution implemented for the class hierarchy.

lib/compiler/implementation/typechecker.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.
 
 class TypeCheckerTask extends CompilerTask {
   TypeCheckerTask(Compiler compiler) : super(compiler);
   String get name() => "Type checker";
 
   static final bool LOG_FAILURES = false;
 
   void check(Node tree, TreeElements elements) {
     measure(() {
       Visitor visitor =
           new TypeCheckerVisitor(compiler, elements, compiler.types);
       try {
         tree.accept(visitor);
       } catch (CancelTypeCheckException e) {
         if (LOG_FAILURES) {
           // Do not warn about unimplemented features; log message instead.
           compiler.log("'${e.node}': ${e.reason}");
         }
       }
     });
   }
 }
 
 interface Type {
   SourceString get name();
   Element get element();
+
+  /**
+   * Performs the substitution [arguments[i]/parameters[i]]this.
+   * The notation is known from this lambda calculus rule:
+   * (lambda x.e0)e1 -> [e1/x]e0.
+   *
+   * See [TypeVariableType] for a motivation for this method.
+   */
+  Type subst(Link<Type> arguments, List<Type> parameters);
 }
 
+/**
+ * Represents a type variable, that is the type parameters of a class
+ * or interface type. For example, in class Array<E> { ... }`,
+ * E is a type variable.
+ *
+ * Each class/interface should have its own unique type variables,
+ * one for each type parameter. A class/interface with type parameters
+ * is said to be parameterized or generic.
+ *
+ * Non-static members, constructors, and factories of generic
+ * class/interface can refer to type variables of the current class
+ * (not of supertypes).
+ *
+ * When using a generic type, also known as an application or
+ * instantiation of the type, the actual type arguments should be
+ * substituted for the type variables in the class declaration.
+ *
+ * For example, given a box, `class Box<T> { T value; }`, the
+ * type of the expression `new Box<String>().value` is
+ * [String] because we must substitute `String` for the
+ * the type variable `T`.
+ */
 class TypeVariableType implements Type {
   final SourceString name;
   TypeVariableElement element;
   TypeVariableType(this.name, [this.element]);
 
-  toString() => name.slowToString();
+  Type subst(Link<Type> arguments, List<Type> parameters) {
+    if (arguments.isEmpty()) {
+      // Return fast on empty substitutions.
+      return this;
+    }
+    Link<Type> argumentLink = arguments;
+    Iterator<Type> parameterIterator = parameters.iterator();
+    while (!argumentLink.isEmpty() && parameterIterator.hasNext()) {
+      Type parameter = parameterIterator.next();
+      Type argument = argumentLink.head;
+      if (parameter === this) {
+        return argument;
+      }
+      argumentLink = argumentLink.tail;
+    }
+    // The type variable was not substituted.
+    return this;
+  }
+
+  String toString() => name.slowToString();
 }
 
 /**
  * A statement type tracks whether a statement returns or may return.
  */
 class StatementType implements Type {
   final String stringName;
   Element get element() => null;
 
   SourceString get name() => new SourceString(stringName);
 
   const StatementType(this.stringName);
 
   static final RETURNING = const StatementType('<returning>');
   static final NOT_RETURNING = const StatementType('<not returning>');
   static final MAYBE_RETURNING = const StatementType('<maybe returning>');
 
   /** Combine the information about two control-flow edges that are joined. */
   StatementType join(StatementType other) {
     return (this === other) ? this : MAYBE_RETURNING;
   }
 
+  Type subst(Link<Type> arguments, List<Type> parameters) {
+    // Statement types are not substitutable.
+    return this;
+  }
+
   String toString() => stringName;
 }
 
 class VoidType implements Type {
   const VoidType(this.element);
   SourceString get name() => element.name;
   final VoidElement element;
 
-  toString() => name.slowToString();
+  Type subst(Link<Type> arguments, List<Type> parameters) {
+    // Void cannot be substituted.
+    return this;
+  }
+
+  String toString() => name.slowToString();
 }
 
 class InterfaceType implements Type {
   final Element element;
   final Link<Type> arguments;
 
   const InterfaceType(this.element,
                       [this.arguments = const EmptyLink<Type>()]);
 
   SourceString get name() => element.name;
 
-  toString() {
+  Type subst(Link<Type> replacements, List<Type> parameters) {
+    if (arguments.isEmpty()) {
+      // Return fast on non-generic types.
+      return this;
+    }
+    if (replacements.isEmpty()) {
+      // Return fast on empty substitutions.
+      return this;
+    }
+    bool changed = false;
+    var argumentsBuilder = new LinkBuilder<Type>();
+    Link<Type> argument = arguments;
+    while (!argument.isEmpty()) {
+      var replacement = argument.head.subst(replacements, parameters);
+      if (!changed && replacement !== argument.head) {
+        changed = true;
+      }
+      argumentsBuilder.addLast(replacement);
+      argument = argument.tail;
+    }
+    if (changed) {
+      // Create a new type only if necessary.
+      return new InterfaceType(element, argumentsBuilder.toLink());
+    }
+    return this;
+  }
+
+  String toString() {
     StringBuffer sb = new StringBuffer();
     sb.add(name.slowToString());
     if (!arguments.isEmpty()) {
       sb.add('<');
       arguments.printOn(sb, ', ');
       sb.add('>');
     }
     return sb.toString();
   }
 }
 
 class FunctionType implements Type {
   final Element element;
   final Type returnType;
   final Link<Type> parameterTypes;
 
   const FunctionType(Type this.returnType, Link<Type> this.parameterTypes,
                      Element this.element);
 
-  toString() {
+  Type subst(Link<Type> arguments, List<Type> parameters) {
+    if (arguments.isEmpty()) {
+      // Return fast on empty substitutions.
+      return this;
+    }
+    var newReturnType = returnType.subst(arguments, parameters);
+    bool changed = newReturnType !== returnType;
+    var parameterBuilder = new LinkBuilder<Type>();
+    Link<Type> parameterType = parameterTypes;
+    while (!parameterType.isEmpty()) {
+      var replacement = parameterType.head.subst(arguments, parameters);
+      if (!changed && replacement !== parameterType.head) {
+        changed = true;
+      }
+      parameterBuilder.addLast(replacement);
+      parameterType = parameterType.tail;
+    }
+    if (changed) {
+      // Create a new type only if necessary.
+      return new FunctionType(newReturnType, parameterBuilder.toLink(),
+                              element);
+    }
+    return this;
+  }
+
+  String toString() {
     StringBuffer sb = new StringBuffer();
     bool first = true;
     sb.add('(');
     parameterTypes.printOn(sb, ', ');
     sb.add(') -> ${returnType}');
     return sb.toString();
   }
 
   SourceString get name() => const SourceString('Function');
 
@@ skipping 661 matching lines @@
   }
 
   visitCatchBlock(CatchBlock node) {
     return unhandledStatement();
   }
 
   visitTypedef(Typedef node) {
     return unhandledStatement();
   }
 }