Substitution handled for most Send nodes.

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;
 
@@ skipping 11 matching lines @@
       }
     });
   }
 }
 
 interface Type {
   SourceString get name();
   Element get element();
 
   /**
-   * Performs the substitution [arguments[i]/parameters[i]]this.
+   * Performs the substitution `[arguments[i]/parameters[i]]this`, where
+   * `parameters[i]` denotes the i'th type variable in [typeParameters].
    * The notation is known from this lambda calculus rule:
-   * (lambda x.e0)e1 -> [e1/x]e0.
+   *
+   *     (lambda x.e0)e1 -> [e1/x]e0.
    *
    * See [TypeVariableType] for a motivation for this method.
    */
-  Type subst(Link<Type> arguments, List<Type> parameters);
+  Type subst(Compiler compiler, Link<Type> arguments,
+             LinkedHashMap<SourceString, TypeVariableElement> typeParameters);
 }
 
 /**
  * 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]);
 
-  Type subst(Link<Type> arguments, List<Type> parameters) {
-    if (arguments.isEmpty()) {
+  Type subst(Compiler compiler, Link<Type> arguments,
+             LinkedHashMap<SourceString, TypeVariableElement> typeParameters) {
+    if (typeParameters.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;
+    Iterator<TypeVariableElement> parameterIterator =
+        typeParameters.getValues().iterator();
+    if (arguments.isEmpty()) {
+      // Raw substitution: Dynamic replaces parameters.
+      while (parameterIterator.hasNext()) {
+        TypeVariableType parameter = parameterIterator.next().type;
+        if (parameter == this) {
+          return compiler.types.dynamicType;
+        }
       }
-      argumentLink = argumentLink.tail;
+    } else {
+      // Normal substitution.
+      Link<Type> argumentLink = arguments;
+      while (!argumentLink.isEmpty() && parameterIterator.hasNext()) {
+        TypeVariableType parameter = parameterIterator.next().type;
+        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) {
+  Type subst(Compiler compiler, Link<Type> arguments,
+             LinkedHashMap<SourceString, TypeVariableElement> typeParameters) {
     // 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;
 
-  Type subst(Link<Type> arguments, List<Type> parameters) {
+  Type subst(Compiler compiler, Link<Type> arguments,
+             LinkedHashMap<SourceString, TypeVariableElement> typeParameters) {
     // Void cannot be substituted.
     return 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;
 
-  Type subst(Link<Type> replacements, List<Type> parameters) {
-    if (arguments.isEmpty()) {
+  Type subst(Compiler compiler, Link<Type> arguments,
+             LinkedHashMap<SourceString, TypeVariableElement> typeParameters) {
+    if (typeArguments.isEmpty()) {
       // Return fast on non-generic types.
       return this;
     }
-    if (replacements.isEmpty()) {
+    if (typeParameters.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> argument = arguments;
-    while (!argument.isEmpty()) {
-      var replacement = argument.head.subst(replacements, parameters);
-      if (!changed && replacement !== argument.head) {
+    Link<Type> typeArgument = typeArguments;
+    while (!typeArgument.isEmpty()) {
+      var argument =
+          typeArgument.head.subst(compiler, arguments, typeParameters);
+      if (!changed && argument !== typeArgument.head) {
         changed = true;
       }
-      argumentsBuilder.addLast(replacement);
-      argument = argument.tail;
+      argumentsBuilder.addLast(argument);
+      typeArgument = typeArgument.tail;
     }
     if (changed) {
       // Create a new type only if necessary.
       return new InterfaceType(element, argumentsBuilder.toLink());
     }
     return 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();
   }
 }
 
 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);
 
-  Type subst(Link<Type> arguments, List<Type> parameters) {
-    if (arguments.isEmpty()) {
+  Type subst(Compiler compiler, Link<Type> arguments,
+             LinkedHashMap<SourceString, TypeVariableElement> typeParameters) {
+    if (typeParameters.isEmpty()) {
       // Return fast on empty substitutions.
       return this;
     }
-    var newReturnType = returnType.subst(arguments, parameters);
+    var newReturnType = returnType.subst(compiler, arguments, typeParameters);
     bool changed = newReturnType !== returnType;
-    var parameterBuilder = new LinkBuilder<Type>();
+    var newParameterTypesBuilder = new LinkBuilder<Type>();
     Link<Type> parameterType = parameterTypes;
     while (!parameterType.isEmpty()) {
-      var replacement = parameterType.head.subst(arguments, parameters);
-      if (!changed && replacement !== parameterType.head) {
+      var newParameterType =
+          parameterType.head.subst(compiler, arguments, typeParameters);
+      if (!changed && newParameterType !== parameterType.head) {
         changed = true;
       }
-      parameterBuilder.addLast(replacement);
+      newParameterTypesBuilder.addLast(newParameterType);
       parameterType = parameterType.tail;
     }
     if (changed) {
       // Create a new type only if necessary.
-      return new FunctionType(newReturnType, parameterBuilder.toLink(),
+      return new FunctionType(newReturnType, newParameterTypesBuilder.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');
 
   int computeArity() {
     int arity = 0;
     parameterTypes.forEach((_) { arity++; });
     return arity;
   }
 }
 
+/**
+ * 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.typeParameters.isEmpty()) {
+      type = type.subst(compiler,
+          declarer.typeArguments, declarer.element.typeParameters);
+      type = type.subst(compiler,
+          receiver.typeArguments, receiver.element.typeParameters);
+    }
+    return type;
+  }
+
+  String toString() {
+    return '$receiver.$element';
+  }
+}
+
 class Types {
   final VoidType voidType;
   final InterfaceType dynamicType;
+  final Element functionElement;
 
-  Types(Element dynamicElement)
-    : this.with(dynamicElement, new LibraryElement(new Script(null, null)));
+  Types(Element dynamicElement, Element functionElement)
+    : this.with(dynamicElement, functionElement,
+                new LibraryElement(new Script(null, null)));
 
   // TODO(karlklose): should we have a class Void?
-  Types.with(Element dynamicElement, LibraryElement library)
+  Types.with(Element dynamicElement,
+             Element this.functionElement,
+             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 is VoidType) {
       return false;
     } else if (t is InterfaceType) {
       if (s is !InterfaceType) return false;
       ClassElement tc = t.element;
       if (tc === s.element) return true;
       for (Link<Type> supertypes = tc.allSupertypes;
            supertypes != null && !supertypes.isEmpty();
            supertypes = supertypes.tail) {
         Type supertype = supertypes.head;
         if (supertype.element === s.element) return true;
       }
       return false;
     } else if (t is FunctionType) {
+      if (s.element == functionElement) return true;
       if (s is !FunctionType) return false;
       FunctionType tf = t;
       FunctionType sf = s;
       Link<Type> tps = tf.parameterTypes;
       Link<Type> sps = sf.parameterTypes;
       while (!tps.isEmpty() && !sps.isEmpty()) {
         if (!isAssignable(tps.head, sps.head)) return false;
         tps = tps.tail;
         sps = sps.tail;
       }
@@ skipping 40 matching lines @@
 
   TypeCheckerVisitor(this.compiler, this.elements, this.types) {
     intType = compiler.intClass.computeType(compiler);
     doubleType = compiler.doubleClass.computeType(compiler);
     boolType = compiler.boolClass.computeType(compiler);
     stringType = compiler.stringClass.computeType(compiler);
     objectType = compiler.objectClass.computeType(compiler);
     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);
   }
 
   reportTypeWarning(Node node, MessageKind kind, [List arguments = const []]) {
     compiler.reportWarning(node, new TypeWarning(kind, arguments));
   }
 
   // TODO(karlklose): remove these functions.
@@ skipping 165 matching lines @@
       }
     }
     if (member !== null && member.kind == ElementKind.FUNCTION) {
       return computeType(member);
     }
     reportTypeWarning(node, MessageKind.METHOD_NOT_FOUND,
                       [classElement.name, name]);
     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) {
       while(!arguments.isEmpty()) {
         analyze(arguments.head);
         arguments = arguments.tail;
       }
     } else {
       Link<Type> parameterTypes = funType.parameterTypes;
       while (!arguments.isEmpty() && !parameterTypes.isEmpty()) {
@@ skipping 45 matching lines @@
         if (!arguments.isEmpty()) {
           // TODO(karlklose): check number of arguments in validator.
           checkAssignable(secondArgument, boolType, secondArgumentType);
         }
         return boolType;
       }
       fail(selector, 'unexpected operator ${name}');
 
     } else if (node.isPropertyAccess) {
       if (node.receiver !== null) {
-        // TODO(karlklose): we cannot handle fields.
-        return unhandledExpression();
+        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);
       }
-      Element element = elements[node];
-      if (element === null) return types.dynamicType;
-      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 {
             fail(node, 'unexpected element kind ${element.kind}');
           }
         }
       }
       FunctionType funType = computeFunType();
       analyzeArguments(node, funType);
       return (funType !== null) ? funType.returnType : types.dynamicType;
@@ skipping 36 matching lines @@
     analyze(node.first);
     analyze(node.second);
     return stringType;
   }
 
   Type visitLiteralNull(LiteralNull node) {
     return types.dynamicType;
   }
 
   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) {
     Type type = StatementType.NOT_RETURNING;
     bool reportedDeadCode = false;
     for (Link<Node> link = node.nodes; !link.isEmpty(); link = link.tail) {
       Type nextType = analyze(link.head);
       if (type == StatementType.RETURNING) {
         if (!reportedDeadCode) {
           reportTypeWarning(link.head, MessageKind.UNREACHABLE_CODE);
@@ skipping 187 matching lines @@
   }
 
   visitCatchBlock(CatchBlock node) {
     return unhandledStatement();
   }
 
   visitTypedef(Typedef node) {
     return unhandledStatement();
   }
 }