Resolve typedefs.

lib/compiler/implementation/typechecker.dart

Index: lib/compiler/implementation/typechecker.dart
diff --git a/lib/compiler/implementation/typechecker.dart b/lib/compiler/implementation/typechecker.dart
index f5a600fa3e08f04b40f497efe977c7630b43dbe0..41750c9bb50e95d63a9261f4dc4635208c0fe900 100644
--- a/lib/compiler/implementation/typechecker.dart
+++ b/lib/compiler/implementation/typechecker.dart
@@ -27,14 +27,92 @@ class TypeCheckerTask extends CompilerTask {
 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(Compiler compiler,
+             Link<Type> arguments, Link<TypeVariableType> parameters);
+
+  /**
+   * Returns the defining type for this type. For non-typedef types, the
+   * defining type is the type itself, whereas for typedef types the defining
+   * type is the defining type of its definition. For example the defining type
+   * for `typedef A Func<A,B>(B b)` is the function type `(B) -> A` and the
+   * defining type for `Func<int,String>` is the function type
+   * `(String) -> int`.
+   */
+  Type unalias(Compiler compiler);
 }
 
+/**
+ * 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(Compiler compiler,
+             Link<Type> arguments, Link<TypeVariableType> parameters) {
+    if (parameters.isEmpty()) {
+      // Return fast on empty substitutions.
+      return this;
+    }
+    Link<TypeVariableType> parameterLink = parameters;
+    if (arguments.isEmpty()) {
+      // Raw substitution: Dynamic replaces parameters.
+      while (!parameterLink.isEmpty()) {
+        TypeVariableType parameter = parameterLink.head;
+        if (parameter == this) {
+          return compiler.types.dynamicType;
+        }
+        parameterLink = parameterLink.tail;
+      }
+    } else {
+      // Normal substitution.
+      Link<Type> argumentLink = arguments;
+      while (!argumentLink.isEmpty() && !parameterLink.isEmpty()) {
+        TypeVariableType parameter = parameterLink.head;
+        Type argument = argumentLink.head;
+        if (parameter == this) {
+          return argument;
+        }
+        parameterLink = parameterLink.tail;
+        argumentLink = argumentLink.tail;
+      }
+    }
+    // The type variable was not substituted.
+    return this;
+  }
+
+  Type unalias(Compiler compiler) => this;
+
+  String toString() => name.slowToString();
 }
 
 /**
@@ -57,6 +135,14 @@ class StatementType implements Type {
     return (this === other) ? this : MAYBE_RETURNING;
   }
 
+  Type subst(Compiler compiler,
+             Link<Type> arguments, Link<TypeVariableType> parameters) {
+    // Statement types are not substitutable.
+    return this;
+  }
+
+  Type unalias(Compiler compiler) => this;
+
   String toString() => stringName;
 }
 
@@ -65,24 +151,96 @@ class VoidType implements Type {
   SourceString get name() => element.name;
   final VoidElement element;
 
-  toString() => name.slowToString();
+  Type subst(Compiler compiler,
+             Link<Type> arguments, Link<TypeVariableType> parameters) {
+    // Void cannot be substituted.
+    return this;
+  }
+
+  Type unalias(Compiler compiler) => this;
+
+  String toString() => name.slowToString();
 }
 
 class InterfaceType implements Type {
-  final Element element;
-  final Link<Type> arguments;
+  final ClassElement element;
+  final Link<Type> typeArguments;
 
   const InterfaceType(this.element,
-                      [this.arguments = const EmptyLink<Type>()]);
+                      [this.typeArguments = const EmptyLink<Type>()]);
 
   SourceString get name() => element.name;
 
-  toString() {
+  Type subst(Compiler compiler,
+             Link<Type> arguments, Link<TypeVariableType> parameters) {
+    if (typeArguments.isEmpty()) {
+      // Return fast on non-generic types.
+      return this;
+    }
+    if (parameters.isEmpty()) {
+      // Return fast on empty substitutions.
+      return this;
+    }
+    if (arguments.isEmpty()) {
+      // Return the 'raw' type on raw substitutions.
+      return new InterfaceType(element);
+    }
+    bool changed = false;
+    var argumentsBuilder = new LinkBuilder<Type>();
+    Link<Type> typeArgument = typeArguments;
+    while (!typeArgument.isEmpty()) {
+      var argument =
+          typeArgument.head.subst(compiler, arguments, parameters);
+      if (!changed && argument !== typeArgument.head) {
+        changed = true;
+      }
+      argumentsBuilder.addLast(argument);
+      typeArgument = typeArgument.tail;
+    }
+    if (changed) {
+      // Create a new type only if necessary.
+      return new InterfaceType(element, argumentsBuilder.toLink());
+    }
+    return this;
+  }
+
+  Type unalias(Compiler compiler) => this;
+
+  /**
+   * Finds the method, field or property on this interface type named [name].
+   */
+  Member lookupMember(Compiler compiler, SourceString name) {
+    ClassElement classElement = element;
+    InterfaceType receiver = this;
+    InterfaceType declarer = receiver;
+    Element member = classElement.lookupLocalMember(name);
+    if (member === null) {
+      classElement.ensureResolved(compiler);
+      for (Link<InterfaceType> supertypes = classElement.allSupertypes;
+           !supertypes.isEmpty() && member === null;
+           supertypes = supertypes.tail) {
+        declarer = supertypes.head;
+        ClassElement lookupTarget = declarer.element;
+        member = lookupTarget.lookupLocalMember(name);
+      }
+    }
+    if (member == null) {
+      return null;
+    }
+    if (member.kind == ElementKind.FUNCTION ||
+        member.kind == ElementKind.ABSTRACT_FIELD ||
+        member.kind == ElementKind.FIELD) {
+      return new Member(receiver, declarer, member);
+    }
+    return null;
+  }
+
+  String toString() {
     StringBuffer sb = new StringBuffer();
     sb.add(name.slowToString());
-    if (!arguments.isEmpty()) {
+    if (!typeArguments.isEmpty()) {
       sb.add('<');
-      arguments.printOn(sb, ', ');
+      typeArguments.printOn(sb, ', ');
       sb.add('>');
     }
     return sb.toString();
@@ -92,12 +250,41 @@ class InterfaceType implements Type {
 class FunctionType implements Type {
   final Element element;
   final Type returnType;
-  final Link<Type> parameterTypes;
+  Link<Type> parameterTypes;
 
-  const FunctionType(Type this.returnType, Link<Type> this.parameterTypes,
-                     Element this.element);
+  FunctionType(Type this.returnType, Link<Type> this.parameterTypes,
+               Element this.element);
 
-  toString() {
+  Type subst(Compiler compiler,
+             Link<Type> arguments, Link<TypeVariableType> parameters) {
+    if (parameters.isEmpty()) {
+      // Return fast on empty substitutions.
+      return this;
+    }
+    var newReturnType = returnType.subst(compiler, arguments, parameters);
+    bool changed = newReturnType !== returnType;
+    var newParameterTypesBuilder = new LinkBuilder<Type>();
+    Link<Type> parameterType = parameterTypes;
+    while (!parameterType.isEmpty()) {
+      var newParameterType =
+          parameterType.head.subst(compiler, arguments, parameters);
+      if (!changed && newParameterType !== parameterType.head) {
+        changed = true;
+      }
+      newParameterTypesBuilder.addLast(newParameterType);
+      parameterType = parameterType.tail;
+    }
+    if (changed) {
+      // Create a new type only if necessary.
+      return new FunctionType(newReturnType, newParameterTypesBuilder.toLink(),
+                              element);
+    }
+    return this;
+  }
+
+  Type unalias(Compiler compiler) => this;
+
+  String toString() {
     StringBuffer sb = new StringBuffer();
     bool first = true;
     sb.add('(');
@@ -115,23 +302,151 @@ class FunctionType implements Type {
   }
 }
 
+class TypedefType implements Type {
+  final TypedefElement element;
+  final Link<Type> typeArguments;
+
+  const TypedefType(this.element,
+      [this.typeArguments = const EmptyLink<Type>()]);
+
+  SourceString get name() => element.name;
+
+  Type subst(Compiler compiler,
+             Link<Type> arguments, Link<TypeVariableType> parameters) {
+    if (typeArguments.isEmpty()) {
+      // Return fast on non-generic typedefs.
+      return this;
+    }
+    if (parameters.isEmpty()) {
+      // Return fast on empty substitutions.
+      return this;
+    }
+    if (arguments.isEmpty()) {
+      // Return the 'raw' type on raw substitutions.
+      return new TypedefType(element);
+    }
+    bool changed = false;
+    var argumentsBuilder = new LinkBuilder<Type>();
+    Link<Type> typeArgument = typeArguments;
+    while (!typeArgument.isEmpty()) {
+      var argument =
+          typeArgument.head.subst(compiler, arguments, parameters);
+      if (!changed && argument !== typeArgument.head) {
+        changed = true;
+      }
+      argumentsBuilder.addLast(argument);
+      typeArgument = typeArgument.tail;
+    }
+    if (changed) {
+      // Create a new type only if necessary.
+      return new TypedefType(element, argumentsBuilder.toLink());
+    }
+    return this;
+  }
+
+  Type unalias(Compiler compiler) {
+    compiler.resolveTypedef(element);
+    Type definition = element.alias.unalias(compiler);
+    TypedefType declaration = element.computeType(compiler);
+    return definition.subst(compiler, typeArguments, declaration.typeArguments);
+  }
+
+  String toString() {
+    StringBuffer sb = new StringBuffer();
+    sb.add(name.slowToString());
+    if (!typeArguments.isEmpty()) {
+      sb.add('<');
+      typeArguments.printOn(sb, ', ');
+      sb.add('>');
+    }
+    return sb.toString();
+  }
+}
+
+/**
+ * Member encapsulates a member (constructor, method, field, property, getter,
+ * or setter) with the types of the declarer and receiver in order to do
+ * substitution on the member type.
+ *
+ * Consider for instance these classes and the variable `B<String> b`:
+ *
+ *     class A<E> {
+ *         E field;
+ *     }
+ *     class B<F> extends A<F> {}
+ *
+ * In a [Member] for `b.field` the [receiver] is `B<String>` and the declarer
+ * is `A<F>`, which is the supertype of `B<F>` from which `field` has been
+ * inherited. To compute the type of `b.field` we must first substitute `E`
+ * by `F` using the relation between `A<E>` and `A<F>`, and then `F` by `String`
+ * using the relation between `B<F>` and `B<String>`.
+ */
+class Member {
+  final InterfaceType receiver;
+  final InterfaceType declarer;
+  final Element element;
+
+  Member(this.receiver, this.declarer, this.element);
+
+  Type computeType(Compiler compiler) {
+    Type type;
+    if (element.kind == ElementKind.ABSTRACT_FIELD) {
+      AbstractFieldElement abstractFieldElement = element;
+      if (abstractFieldElement.getter != null) {
+        type = abstractFieldElement.getter.computeType(compiler).returnType;
+      } else {
+        type = abstractFieldElement.setter.computeType(
+            compiler).parameterTypes.head;
+        if (type == null) {
+          type = compiler.types.dynamicType;
+        }
+      }
+    } else {
+      type = element.computeType(compiler);
+    }
+    if (!declarer.element.typeVariables.isEmpty()) {
+      type = type.subst(compiler,
+          declarer.typeArguments,
+          declarer.element.computeType(compiler).typeArguments);
+      type = type.subst(compiler,
+          receiver.typeArguments,
+          receiver.element.computeType(compiler).typeArguments);
+    }
+    return type;
+  }
+
+  String toString() {
+    return '$receiver.$element';
+  }
+}
+
 class Types {
+  final Compiler compiler;
   final VoidType voidType;
   final InterfaceType dynamicType;
 
-  Types(Element dynamicElement)
-    : this.with(dynamicElement, new LibraryElement(new Script(null, null)));
+  Types(Compiler compiler, Element dynamicElement)
+    : this.with(compiler, dynamicElement,
+                new LibraryElement(new Script(null, null)));
 
   // TODO(karlklose): should we have a class Void?
-  Types.with(Element dynamicElement, LibraryElement library)
+  Types.with(Compiler this.compiler,
+             Element dynamicElement,
+             LibraryElement library)
     : voidType = new VoidType(new VoidElement(library)),
       dynamicType = new InterfaceType(dynamicElement);
 
   /** Returns true if t is a subtype of s */
   bool isSubtype(Type t, Type s) {
-    if (t === s || t === dynamicType || s === dynamicType ||
-        // TODO(karlklose): Test for s.element === compiler.objectClass.
-        s.name == const SourceString('Object')) return true;
+    if (t === s ||
+        t === dynamicType ||
+        s === dynamicType ||
+        s.element === compiler.objectClass) {
+      return true;
+    }
+    t = t.unalias(compiler);
+    s = s.unalias(compiler);
+
     if (t is VoidType) {
       return false;
     } else if (t is InterfaceType) {
@@ -146,6 +461,7 @@ class Types {
       }
       return false;
     } else if (t is FunctionType) {
+      if (s.element == compiler.functionClass) return true;
       if (s is !FunctionType) return false;
       FunctionType tf = t;
       FunctionType sf = s;
@@ -206,9 +522,12 @@ class TypeCheckerVisitor implements Visitor<Type> {
     listType = compiler.listClass.computeType(compiler);
   }
 
-  Type fail(node, [reason]) {
+  Type fail(Node node, [reason]) {
     String message = 'cannot type-check';
-    if (reason !== null) {
+    if (node != null) {
+      message = '$message ${node.getObjectDescription()} `$node`';
+    }
+    if (reason != null) {
       message = '$message: $reason';
     }
     throw new CancelTypeCheckException(node, message);
@@ -394,6 +713,37 @@ class TypeCheckerVisitor implements Visitor<Type> {
     return types.dynamicType;
   }
 
+  /**
+   * Returns the interface type on which to lookup members. If [type] is the
+   * function of a getter, the return type is returned. If [type] is a type
+   * variable the bound is returned.
+   */
+  InterfaceType findReceiverType(Node receiver, Type receiverType) {
+    if (receiverType === null) {
+      fail(receiver, 'receivertype is null');
+    }
+    if (receiverType.element == compiler.dynamicClass) {
+      return receiverType;
+    }
+    ElementKind receiverKind = receiverType.element.kind;
+    if (receiverKind === ElementKind.GETTER) {
+      FunctionType getterType  = receiverType;
+      return findReceiverType(receiver, getterType.returnType);
+    }
+    if (receiverKind === ElementKind.TYPEDEF) {
+      // TODO(karlklose): handle typedefs.
+      return null;
+    }
+    if (receiverKind === ElementKind.TYPE_VARIABLE) {
+      TypeVariableElement typeVariableElement = receiverType.element;
+      return findReceiverType(receiver, typeVariableElement.bound);
+    }
+    if (receiverKind !== ElementKind.CLASS) {
+      fail(receiver, 'unexpected receiver kind: ${receiverKind}');
+    }
+    return receiverType;
+  }
+
   void analyzeArguments(Send send, FunctionType funType) {
     Link<Node> arguments = send.arguments;
     if (funType === null || funType === types.dynamicType) {
@@ -459,56 +809,87 @@ class TypeCheckerVisitor implements Visitor<Type> {
 
     } else if (node.isPropertyAccess) {
       if (node.receiver !== null) {
-        // TODO(karlklose): we cannot handle fields.
-        return unhandledExpression();
-      }
-      Element element = elements[node];
-      if (element === null) return types.dynamicType;
-      return computeType(element);
+        InterfaceType receiverType =
+            findReceiverType(node.receiver, analyze(node.receiver));
+        if (receiverType === null) return null;
+        if (receiverType.element === compiler.dynamicClass) {
+          return types.dynamicType;
+        }
 
+        Member member = receiverType.lookupMember(compiler, selector.source);
+        if (member === null ||
+            !(member.element.kind === ElementKind.FIELD ||
+              member.element.kind === ElementKind.ABSTRACT_FIELD)) {
+          reportTypeWarning(selector, MessageKind.PROPERTY_NOT_FOUND,
+                            [receiverType, selector.source]);
+        } else {
+          return member.computeType(compiler);
+        }
+        return types.dynamicType;
+      } else {
+        Element element = elements[node];
+        if (element === null) {
+          return types.dynamicType;
+        }
+        if ((element.kind == ElementKind.FIELD ||
+             element.kind == ElementKind.GETTER) &&
+            element.isInstanceMember()) {
+          // Ensure substitution of declared type variables with inherited type
+          // variables.
+          InterfaceType thisType = currentClass.computeType(compiler);
+          Member member = thisType.lookupMember(compiler, selector.source);
+          if (member != null) {
+            // Should always work!
+            return member.computeType(compiler);
+          }
+          compiler.internalError('Could not lookup resolved member '
+            '${selector.source} on ${thisType}.');
+        }
+        return computeType(element);
+      }
     } else if (node.isFunctionObjectInvocation) {
       fail(node.receiver, 'function object invocation unimplemented');
 
     } else {
       FunctionType computeFunType() {
         if (node.receiver !== null) {
-          Type receiverType = analyze(node.receiver);
-          if (receiverType.element == compiler.dynamicClass) return null;
-          if (receiverType === null) {
-            fail(node.receiver, 'receivertype is null');
-          }
-          if (receiverType.element.kind === ElementKind.GETTER) {
-            FunctionType getterType  = receiverType;
-            receiverType = getterType.returnType;
-          }
-          ElementKind receiverKind = receiverType.element.kind;
-          if (receiverKind === ElementKind.TYPEDEF) {
-            // TODO(karlklose): handle typedefs.
+          InterfaceType receiverType =
+              findReceiverType(node.receiver, analyze(node.receiver));
+          if (receiverType === null) return null;
+          if (receiverType.element === compiler.dynamicClass) return null;
+
+          Member member = receiverType.lookupMember(compiler, selector.source);
+          if (member === null || member.element.kind !== ElementKind.FUNCTION) {
+            reportTypeWarning(selector, MessageKind.METHOD_NOT_FOUND,
+                              [receiverType, name]);
             return null;
           }
-          if (receiverKind === ElementKind.TYPE_VARIABLE) {
-            // TODO(karlklose): handle type variables.
-            return null;
-          }
-          if (receiverKind !== ElementKind.CLASS) {
-            fail(node.receiver, 'unexpected receiver kind: ${receiverKind}');
-          }
-          ClassElement classElement = receiverType.element;
-          // TODO(karlklose): substitute type arguments.
-          Type memberType =
-            lookupMethodType(selector, classElement, selector.source);
-          if (memberType.element === compiler.dynamicClass) return null;
+          Type memberType = member.computeType(compiler);
+          if (memberType.element == compiler.dynamicClass) return null;
+          if (memberType.element == compiler.functionClass) return null;
           return memberType;
         } else {
           Element element = elements[node];
           if (element === null) {
             fail(node, 'unresolved ${node.selector}');
           } else if (element.kind === ElementKind.FUNCTION) {
+            if (element.isInstanceMember()) {
+              // Ensure substitution of declared type variables with inherited
+              // type variables.
+              InterfaceType thisType = currentClass.computeType(compiler);
+              Member member = thisType.lookupMember(compiler, selector.source);
+              if (member != null) {
+                // Should always work!
+                return member.computeType(compiler);
+              }
+              compiler.internalError('Could not lookup resolved member '
+                                     '${selector.source} on ${thisType}.');
+            }
             return computeType(element);
           } else if (element.kind === ElementKind.FOREIGN) {
             return null;
-          } else if (element.kind === ElementKind.VARIABLE
-                     || element.kind === ElementKind.FIELD) {
+          } else if (element.kind === ElementKind.VARIABLE ||
+                     element.kind === ElementKind.FIELD) {
             // TODO(karlklose): handle object invocations.
             return null;
           } else {
@@ -565,13 +946,22 @@ class TypeCheckerVisitor implements Visitor<Type> {
   }
 
   Type visitNewExpression(NewExpression node) {
+    InterfaceType type = elements.getType(node.getTypeAnnotation());
     Element element = elements[node.send];
-    analyzeArguments(node.send, computeType(element));
-    return analyze(node.send.selector);
+    var member = new Member(type,
+                            element.enclosingElement.computeType(compiler),
+                            element);
+    analyzeArguments(node.send, member.computeType(compiler));
+    return type;
   }
 
   Type visitLiteralList(LiteralList node) {
-    return listType;
+    Type elementType = node.type != null
+        ? elements[node.type]
+        : compiler.types.dynamicType;
+    var linkBuilder = new LinkBuilder<Type>();
+    linkBuilder.addLast(elementType);
+    return new InterfaceType(listType.element, linkBuilder.toLink());
   }
 
   Type visitNodeList(NodeList node) {