pkg/kernel/lib/type_checker.dart

// 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.type_checker;

import 'ast.dart';
import 'class_hierarchy.dart';
import 'core_types.dart';
import 'type_algebra.dart';
import 'type_environment.dart';
import 'clone.dart';

enum TypeKind { Reference, Integer, Double }

class Instantiation {
  final Class klass;
  final List<TypeKind> types;

  Class node;

  Instantiation(this.klass, this.types);

  bool operator == (other) {
    return other is Instantiation &&
           this.klass == other.klass &&
           _listEquals(this.types, other.types);
  }

  int get hashCode => klass.hashCode ^ _listHash(types);

  static bool _listEquals(List<TypeKind> a, List<TypeKind> b) {
    if (a.length != b.length) return false;
    for (var i = 0; i < a.length; i++) {
      if (a[i] != b[i]) return false;
    }
    return true;
  }

  static int _listHash(List<TypeKind> a) {
    int result = a.length;
    for (var i = 0; i < a.length; i++) {
      result |= a[i].hashCode;
    }
    return result;
  }

}

/// Performs strong-mode type checking on the kernel IR.
///
/// A concrete subclass of [TypeChecker] must implement [checkAssignable] and
/// [fail] in order to deal with subtyping requirements and error handling.
abstract class TypeChecker {
  final CoreTypes coreTypes;
  final ClassHierarchy hierarchy;
  TypeEnvironment environment;

  TypeChecker(this.coreTypes, this.hierarchy) {
    environment = new TypeEnvironment(coreTypes, hierarchy);
  }

  DartType ensureNoDynamic(DartType type) {
    if (type == const DynamicType()) {
      return environment.objectType;
    } else if (type is InterfaceType && type.typeArguments.isNotEmpty) {
      return new InterfaceType(type.classNode, type.typeArguments.map(ensureNoDynamic).toList());
    } else if (type is FunctionType) {
      return new FunctionType(type.positionalParameters.map(ensureNoDynamic).toList(), ensureNoDynamic(type.returnType),
          namedParameters: type.namedParameters, typeParameters: type.typeParameters, requiredParameterCount: type.requiredParameterCount);
    } else {
      return type;
    }
  }

  void checkSignature(FunctionNode node) {
    for (VariableDeclaration v in node.positionalParameters) {
      v.type = ensureNoDynamic(v.type);
    }

    for (VariableDeclaration v in node.namedParameters) {
      v.type = ensureNoDynamic(v.type);
    }

    node.returnType = ensureNoDynamic(node.returnType);
  }

  List<Field> checkSignatures(Program program) {
    final List<Field> dynamicFields = <Field>[];

    handleField(Field field) {
      if (field.type == const DynamicType()) {
        if ((field.initializer == null || field.initializer is NullLiteral)) {
          field.type = environment.objectType;
        } else {
          dynamicFields.add(field);
        }
      }
    }

    int processed = 0;
    for (var library in program.libraries) {
      processed++;
      print(
          'Processing ${library.importUri} (${processed} of ${program.libraries.length})');
      int nclass = 0;
      for (var class_ in library.classes) {
        nclass++;
        print('${nclass}/${library.classes.length}: ${class_}');
        for (var constructor in class_.constructors) {
          checkSignature(constructor.function);
        }
        for (var procedure in class_.procedures) {
          checkSignature(procedure.function);
        }

        class_.fields.forEach(handleField);
      }

      for (var procedure in library.procedures) {
        checkSignature(procedure.function);
      }

      library.fields.forEach(handleField);
    }

    return dynamicFields;
  }

  void checkClass(TypeCheckingVisitor visitor, Class klass) {
    environment.thisType = klass.thisType;
    for (var field in klass.fields) {
      visitor.visitField(field);
    }
    for (var constructor in klass.constructors) {
      visitor.visitConstructor(constructor);
    }
    for (var procedure in klass.procedures) {
      if (procedure.function.typeParameters.isNotEmpty) {
        print('Skipping ${procedure}');
        continue;
      }
      visitor.visitProcedure(procedure);
    }
  }

  void checkProgram(Program program) {
    final dynamicFields = checkSignatures(program);

    for (var library in program.libraries) {
      if (library.importUri.scheme == 'dart') continue;
      for (var class_ in library.classes) {
        hierarchy.forEachOverridePair(class_,
            (Member ownMember, Member superMember, bool isSetter) {
          checkOverride(class_, ownMember, superMember, isSetter);
        });
      }
    }

    var visitor = new TypeCheckingVisitor(this, environment);
    var worklist = dynamicFields;

    var changed;
    do {
      var current = worklist;
      worklist = <Field>[];
      changed = false;
      for (var field in current) {
        final parent = field.parent;
        if (parent is Class) {
          environment.thisType = parent.thisType;
        } else {
          environment.thisType = null;
        }
        try {
          visitor.visitField(field);
          changed = true;
        } catch (e) {
          worklist.add(field);
        }
      }

      if (!changed && worklist.isNotEmpty) {
        throw "Haha";
      }
    } while (worklist.isNotEmpty);

    for (var field in dynamicFields) {
      if (field.type == const DynamicType()) {
        fail(field, "Field has type dynamic");
      }
    }

    var processed = 0;
    for (var library in program.libraries) {
      processed++;
      print(
          'Processing ${library.importUri} (${processed} of ${program.libraries.length})');
      int nclass = 0;
      for (var klass in library.classes) {
        nclass++;
        if (klass.typeParameters.isNotEmpty) {
          print('Skipping ${klass}');
          continue;
        }
        print('${nclass}/${library.classes.length}: ${klass}');
        checkClass(visitor, klass);
      }
      environment.thisType = null;
      for (var procedure in library.procedures) {
        if (procedure.function.typeParameters.isNotEmpty) {
          print('Skipping ${procedure}');
          continue;
        }
        visitor.visitProcedure(procedure);
      }
      for (var field in library.fields) {
        visitor.visitField(field);
      }
    }
  }

  DartType getterType(Class host, Member member) {
    var hostType = hierarchy.getClassAsInstanceOf(host, member.enclosingClass);
    var substitution = Substitution.fromSupertype(hostType);
    return substitution.substituteType(member.getterType);
  }

  DartType setterType(Class host, Member member) {
    var hostType = hierarchy.getClassAsInstanceOf(host, member.enclosingClass);
    var substitution = Substitution.fromSupertype(hostType);
    return substitution.substituteType(member.setterType, contravariant: true);
  }

  void checkOverride(
      Class host, Member ownMember, Member superMember, bool isSetter) {
    if (isSetter) {
      checkAssignable(ownMember, setterType(host, superMember),
          setterType(host, ownMember));
    } else {
      checkAssignable(ownMember, getterType(host, ownMember),
          getterType(host, superMember));
    }
  }

  /// Check that [from] is a subtype of [to].
  ///
  /// [where] is an AST node indicating roughly where the check is required.
  void checkAssignable(TreeNode where, DartType from, DartType to);

  /// Checks that [expression], which has type [from], can be assigned to [to].
  ///
  /// Should return a downcast if necessary, or [expression] if no cast is
  /// needed.
  Expression checkAndDowncastExpression(
      Expression expression, DartType from, DartType to) {
    checkAssignable(expression, from, to);
    return expression;
  }

  /// Indicates that type checking failed.
  void fail(TreeNode where, String message);

  bool isNumeric(DartType type);

  bool isInteger(DartType type);

  bool isDouble(DartType type);

  TypeKind toTypeKind(TreeNode where, DartType type);

  DartType leastUpperBound(TreeNode where, DartType a, DartType b);
}

enum SelectorKind {
  Method,
  Getter,
  Setter,
}

class Selector {
  final SelectorKind kind;
  final Name name;

  Selector(this.kind, this.name);

  factory Selector.fromProcedure(Procedure procedure) {
    SelectorKind kind;
    switch (procedure.kind) {
      case ProcedureKind.Getter:
        kind = SelectorKind.Getter;
        break;
      case ProcedureKind.Setter:
        kind = SelectorKind.Setter;
        break;
      case ProcedureKind.Operator:
      case ProcedureKind.Method:
      case ProcedureKind.Factory:
        kind = SelectorKind.Method;
        break;
    }
    return new Selector(kind, procedure.name);
  }

  Selector get asGetter => new Selector(SelectorKind.Getter, name);

  Selector get asMethod => new Selector(SelectorKind.Method, name);

  Selector modifyKindToAccess(Member target) {
    if (target is Procedure) {
      if (kind == SelectorKind.Method && target.kind == ProcedureKind.Getter) {
        return asGetter; // This is a call-though-getter.
      } else if (kind == SelectorKind.Getter &&
          target.kind == ProcedureKind.Method) {
        return asMethod; // This is a tear-off.
      }
    } else if (target is Field) {
      if (kind == SelectorKind.Method) {
        return asGetter; // This is a call-though-field.
      }
    }
    return this;
  }

  int get hashCode => kind.hashCode ^ name.hashCode;

  bool operator ==(other) =>
      other is Selector && other.kind == kind && other.name == name;

  String toString() {
    if (kind == SelectorKind.Getter) return 'get:${name}';
    if (kind == SelectorKind.Setter) return 'set:${name}';
    assert(kind == SelectorKind.Method);
    return '$name';
  }
}

class LookupCache {
  final Map<Class, Map<Selector, Member>> lookupCache =
      <Class, Map<Selector, Member>>{};

  final Map<Class, Map<Selector, Member>> interfaceLookupCache =
      <Class, Map<Selector, Member>>{};

  Member lookupSelector(Class klass, Selector selector) {
    return lookupCache
        .putIfAbsent(klass, () => <Selector, Member>{})
        .putIfAbsent(selector, () {
      while (klass != null) {
        for (final Member member in klass.members) {
          if (member.name == selector.name) {
            if (member is Field) {
              // A field shadows getter/call and setter iff non-final/non-const.
              if (selector.kind == SelectorKind.Method) {
                ensureIsFunctionType(member.type, 'call-through-field usage');
                return member;
              }
              if (selector.kind == SelectorKind.Getter) {
                return member;
              }
              if (selector.kind == SelectorKind.Setter &&
                  (!member.isFinal && !member.isConst)) {
                return member;
              }
            } else if (member is Procedure) {
              // A procedure shadows getter/call but not setter.
              if (selector.kind == SelectorKind.Getter &&
                  member.kind == ProcedureKind.Method) {
                ensureProcedureCanBeTornOff(member);
                return member;
              }
              if (selector.kind == SelectorKind.Getter &&
                  member.kind == ProcedureKind.Getter) {
                return member;
              }
              if (selector.kind == SelectorKind.Setter &&
                  member.kind == ProcedureKind.Setter) {
                return member;
              }
              if (selector.kind == SelectorKind.Method &&
                  (member.kind == ProcedureKind.Method ||
                      member.kind == ProcedureKind.Operator ||
                      member.kind == ProcedureKind.Factory)) {
                return member;
              }
              if (selector.kind == SelectorKind.Method &&
                  (member.kind == ProcedureKind.Getter)) {
                ensureIsFunctionType(
                    member.function.returnType, 'call-through-field usage');
                return member;
              }
            } else {
              throw "UNREACHABLE";
            }
          }
        }
        klass = klass.superclass;
      }
      return null;
    });
  }

  Member lookupInterfaceSelector(Class klass, Selector selector) {
    return interfaceLookupCache
        .putIfAbsent(klass, () => <Selector, Member>{})
        .putIfAbsent(selector, () {
      Member member = lookupSelector(klass, selector);
      if (member != null) return member;

      for (final Supertype superType in klass.implementedTypes) {
        member = lookupInterfaceSelector(superType.classNode, selector);
        if (member != null) return member;
      }
      return null;
    });
  }

  void ensureProcedureCanBeTornOff(Procedure procedure) {
    final FunctionNode function = procedure.function;
    if (function.requiredParameterCount !=
            function.positionalParameters.length ||
        function.namedParameters.isNotEmpty) {
      throw 'No tear-off support for functions with optional parameters!';
    }
  }

  void ensureIsFunctionType(DartType type, String msg) {
    if (type is! FunctionType) {
      throw 'Expected a [FunctionType] for $msg but got "$type".';
    }
  }
}

class AssignmentFinder extends RecursiveVisitor {
  final VariableDeclaration decl;

  AssignmentFinder(this.decl);

  bool found = false;

  @override
  void visitVariableSet(VariableSet node) {
    if (node.variable == decl) {
      found = true;
    } else {
      super.visitVariableSet(node);
    }
  }

  static bool hasAssignmentsTo(VariableDeclaration decl, TreeNode node) {
    final finder = new AssignmentFinder(decl);
    node.accept(finder);
    return finder.found;
  }
}



class TypeCheckingVisitor
    implements
        ExpressionVisitor<DartType>,
        StatementVisitor<Null>,
        MemberVisitor<Null>,
        InitializerVisitor<Null> {
  final TypeChecker checker;
  final TypeEnvironment environment;

  CoreTypes get coreTypes => environment.coreTypes;
  ClassHierarchy get hierarchy => environment.hierarchy;
  Class get currentClass => environment.thisType.classNode;

  TypeCheckingVisitor(this.checker, this.environment);

  void checkAssignable(TreeNode where, DartType from, DartType to) {
    checker.checkAssignable(where, from, to);
  }

  Expression checkAndDowncastExpression(Expression from, DartType to) {
    if (isUntypedLambda(from)) {
      handleUntypedLambda(from, to, new Set<TypeParameter>());
    }

    var parent = from.parent;
    var type = visitExpression(from);
    var result = checker.checkAndDowncastExpression(from, type, to);
    result.parent = parent;
    return result;
  }

  Expression checkAndDowncastExpressionFrom(
      Expression from, DartType fromType, DartType to) {
    var parent = from.parent;
    var result = checker.checkAndDowncastExpression(from, fromType, to);
    result.parent = parent;
    return result;
  }

  void checkExpressionNoDowncast(Expression expression, DartType to) {
    checkAssignable(expression, visitExpression(expression), to);
  }

  void fail(TreeNode node, String message) {
    checker.fail(node, message);
  }

  DartType visitExpression(Expression node) => node.accept(this);

  void visitStatement(Statement node) {
    node.accept(this);
  }

  void visitInitializer(Initializer node) {
    node.accept(this);
  }

  defaultMember(Member node) => throw 'Unused';

  DartType defaultBasicLiteral(BasicLiteral node) {
    return defaultExpression(node);
  }

  DartType defaultExpression(Expression node) {
    throw 'Unexpected expression ${node.runtimeType}';
  }

  defaultStatement(Statement node) {
    throw 'Unexpected statement ${node.runtimeType}';
  }

  defaultInitializer(Initializer node) {
    throw 'Unexpected initializer ${node.runtimeType}';
  }

  visitField(Field node) {
    if (node.type == const DynamicType() && node.initializer == null) {
      fail(node, "Field ${node} has dynamic type and no initializer");
      return;
    }

    if (node.type == const DynamicType()) {
      node.type = visitExpression(node.initializer);
    }

    if (node.initializer != null) {
      node.initializer =
          checkAndDowncastExpression(node.initializer, node.type);
    }
  }

  visitConstructor(Constructor node) {
    environment.returnType = null;
    environment.yieldType = null;
    node.initializers.forEach(visitInitializer);
    handleFunctionNode(node.function);
  }

  visitProcedure(Procedure node) {
    environment.returnType = _getInternalReturnType(node.function);
    environment.yieldType = _getYieldType(node.function);
    handleFunctionNode(node.function);
  }

  void handleFunctionNode(FunctionNode node) {
    var oldAsyncMarker = environment.currentAsyncMarker;
    environment.currentAsyncMarker = node.asyncMarker;
    node.positionalParameters
        .skip(node.requiredParameterCount)
        .forEach(handleOptionalParameter);
    node.namedParameters.forEach(handleOptionalParameter);
    if (node.body != null) {
      visitStatement(node.body);
    }
    environment.currentAsyncMarker = oldAsyncMarker;
  }

  void handleNestedFunctionNode(FunctionNode node) {
    var oldReturn = environment.returnType;
    var oldYield = environment.yieldType;
    var oldCanInferReturnType = environment.canInferReturnType;
    environment.returnType = _getInternalReturnType(node);
    environment.yieldType = _getYieldType(node);
    environment.canInferReturnType = node.parent is FunctionExpression &&
        environment.returnType == const DynamicType();
    handleFunctionNode(node);
    if (environment.canInferReturnType) {
      if (environment.returnType != const DynamicType()) {
        node.returnType = environment.returnType;
      }
    }
    environment.returnType = oldReturn;
    environment.yieldType = oldYield;
    environment.canInferReturnType = oldCanInferReturnType;
  }

  void fixupInitializer(VariableDeclaration node) {
    if (node.initializer is NullLiteral) {
      switch (checker.toTypeKind(node, node.type)) {
        case TypeKind.Integer:
          node.initializer = new IntLiteral(0);
          break;
        case TypeKind.Double:
          node.initializer = new DoubleLiteral(0.0);
          break;
        case TypeKind.Reference:
          return;
      }
      node.initializer.parent = node;
    }
  }

  void handleOptionalParameter(VariableDeclaration parameter) {
    fixupInitializer(parameter);

    if (parameter.initializer != null) {
      // Default parameter values cannot be downcast.
      checkExpressionNoDowncast(parameter.initializer, parameter.type);
    }
  }

  Substitution getReceiverType(
      TreeNode access, Expression receiver, Member member) {
    return getReceiverTypeImpl(
        visitExpression(receiver), access, receiver, member);
  }

  Substitution getReceiverTypeImpl(
      DartType type, TreeNode access, Expression receiver, Member member) {
    Class superclass = member.enclosingClass;
    if (superclass.supertype == null) {
      return Substitution.empty; // Members on Object are always accessible.
    }
    while (type is TypeParameterType) {
      type = (type as TypeParameterType).parameter.bound;
    }
    if (type is BottomType) {
      // The bottom type is a subtype of all types, so it should be allowed.
      return Substitution.bottomForClass(superclass);
    }
    if (type is InterfaceType) {
      // The receiver type should implement the interface declaring the member.
      var upcastType = hierarchy.getTypeAsInstanceOf(type, superclass);
      if (upcastType != null) {
        return Substitution.fromInterfaceType(upcastType);
      }
    }
    if (type is FunctionType && superclass == coreTypes.functionClass) {
      assert(type.typeParameters.isEmpty);
      return Substitution.empty;
    }
    // Note that we do not allow 'dynamic' here.  Dynamic calls should not
    // have a declared interface target.
    fail(access, '$member is not accessible on a receiver of type $type');
    return Substitution.bottomForClass(superclass); // Continue type checking.
  }

  Substitution getSuperReceiverType(Member member) {
    return Substitution.fromSupertype(
        hierarchy.getClassAsInstanceOf(currentClass, member.enclosingClass));
  }

  static bool isUntypedLambda(TreeNode node) {
    return node is FunctionExpression &&
        node.function.functionType.positionalParameters
            .any((t) => t == const DynamicType());
  }

  // If function expression has untyped parameters then it infers their type
  // based on the expectedType which is expected to be a FunctionType.
  handleUntypedLambda(FunctionExpression arg, DartType expectedType,
      Set<TypeParameter> typeParameters) {
    if (!(expectedType is FunctionType &&
        expectedType.positionalParameters.length ==
            arg.function.positionalParameters.length)) {
      fail(arg,
          'Expected ${expectedType}, got function expression with untyped parameters.');
    }

    for (var i = 0; i < arg.function.positionalParameters.length; i++) {
      final param_ = arg.function.positionalParameters[i];
      if (param_.type != const DynamicType()) continue;

      final paramType_ = (expectedType as FunctionType).positionalParameters[i];

      if (containsTypeVariable(paramType_, typeParameters)) {
        fail(arg,
            'Expected ${expectedType}, got function expression with untyped parameters.');
      }

      arg.function.positionalParameters[i].type = paramType_;
      if (paramType_ == const DynamicType()) {
        fail(arg, 'Failed to infer type for the parameter');
      }
    }
  }

  void tryInferTypeArguments(
      FunctionNode function,
      Substitution receiver,
      Arguments arguments,
      List<TypeParameter> typeParameters) {
    // We need to infer type parameters.
    final quantifiedVariables = new Set<TypeParameter>.from(typeParameters);
    var foundMapping = <TypeParameter, DartType>{};
    for (var i = 0; i < arguments.positional.length; i++) {
      final param = function.positionalParameters[i];
      final arg = arguments.positional[i];

      final expectedType =
          receiver.substituteType(param.type, contravariant: true);

      if (isUntypedLambda(arg)) {
        handleUntypedLambda(arg, expectedType, quantifiedVariables);
      }

      final gotType = visitExpression(arg);
      DartType candidate = gotType;
      if (expectedType is InterfaceType && candidate is InterfaceType) {
        findInstanceOf(Class klass, InterfaceType type) {
          while (type.classNode != klass) {
            final sup = type.classNode.supertype;
            if (sup == null) {
              return null;
            }

            final sub = Substitution.fromInterfaceType(type);
            if (sup.classNode != klass) {
              for (var supi in type.classNode.implementedTypes) {
                if (supi.classNode == klass) {
                  return sub.substituteType(supi.asInterfaceType);
                }
              }

              for (var supi in type.classNode.implementedTypes) {
                final res = findInstanceOf(klass, supi.asInterfaceType);
                if (res != null) {
                  return res;
                }
              }
            }

            type = sub.substituteType(sup.asInterfaceType);
          }
          return type;
        }

        candidate = findInstanceOf(expectedType.classNode, candidate as InterfaceType) ?? candidate;
      }

      var mapping = unifyTypes(expectedType, candidate, quantifiedVariables);
      if (mapping != null) {
        mapping.forEach((p, t1) {
          final t2 = foundMapping[p];
          if (t2 == null) {
            foundMapping[p] = t1;
          } else if (t2 != t1) {
            // TODO(vegorov) !!!
            fail(arguments.positional[i], "Inferred T to be ${t1} and ${t2}.");
          }
        });
      }
    }

    if (foundMapping.length != quantifiedVariables.length) {
      fail(arguments,
          "Failed to infer some type arguments: "
          "${quantifiedVariables.where((p) => !foundMapping.containsKey(p))}");
    }

    arguments.types.length = typeParameters.length;
    arguments.types.setRange(
        0, arguments.types.length, typeParameters.map((p) => foundMapping[p]));
  }

  DartType handleCall(Arguments arguments, FunctionNode function,
      {Substitution receiver: Substitution.empty,
      List<TypeParameter> typeParameters}) {
    final parent = arguments.parent;
    if (parent is StaticInvocation &&
        parent.name.name == 'identical') {
      if (arguments.named.length == 0 && arguments.positional.length == 2) {
        var lhs = arguments.positional[0];
        var rhs = arguments.positional[1];

        if (checker.toTypeKind(lhs, visitExpression(lhs)) ==
            checker.toTypeKind(rhs, visitExpression(rhs))) {
          return environment.boolType;
        }
      }
    }

    typeParameters ??= function.typeParameters;
    if (arguments.positional.length < function.requiredParameterCount) {
      fail(arguments, 'Too few positional arguments');
      return const BottomType();
    }
    if (arguments.positional.length > function.positionalParameters.length) {
      fail(arguments, 'Too many positional arguments');
      return const BottomType();
    }
    if (arguments.types.length != typeParameters.length) {
      if (arguments.types.isEmpty && typeParameters.isNotEmpty) {
        tryInferTypeArguments(function, receiver, arguments, typeParameters);
      } else {
        fail(arguments, '''
Wrong number of type arguments:
    expected ${function.functionType}
    found    ${arguments}
''');
        return const BottomType();
      }
    } else if (arguments.types.isNotEmpty &&
        arguments.types.every((t) => t == const DynamicType())) {
      tryInferTypeArguments(function, receiver, arguments, typeParameters);
    }

    var instantiation = Substitution.fromPairs(typeParameters, arguments.types);
    var substitution = Substitution.combine(receiver, instantiation);
    for (int i = 0; i < typeParameters.length; ++i) {
      var argument = arguments.types[i];
      InterfaceType bound = substitution.substituteType(typeParameters[i].bound);
      if (bound.classNode.supertype == null) {
        // Ignore Object bound.
        continue;
      }
      checkAssignable(arguments, argument, bound);
    }
    for (int i = 0; i < arguments.positional.length; ++i) {
      var expectedType = substitution.substituteType(
          function.positionalParameters[i].type,
          contravariant: true);
      arguments.positional[i] =
          checkAndDowncastExpression(arguments.positional[i], expectedType);
    }
    for (int i = 0; i < arguments.named.length; ++i) {
      var argument = arguments.named[i];
      bool found = false;
      for (int j = 0; j < function.namedParameters.length; ++j) {
        if (argument.name == function.namedParameters[j].name) {
          var expectedType = substitution.substituteType(
              function.namedParameters[j].type,
              contravariant: true);
          argument.value =
              checkAndDowncastExpression(argument.value, expectedType);
          found = true;
          break;
        }
      }
      if (!found) {
        fail(argument.value, 'Unexpected named parameter: ${argument.name}');
        return const BottomType();
      }
    }
    return substitution.substituteType(function.returnType);
  }

  DartType _getInternalReturnType(FunctionNode function) {
    switch (function.asyncMarker) {
      case AsyncMarker.Sync:
        return function.returnType;

      case AsyncMarker.Async:
        Class container = coreTypes.futureClass;
        DartType returnType = function.returnType;
        if (returnType is InterfaceType && returnType.classNode == container) {
          return returnType.typeArguments.single;
        }
        return const DynamicType();

      case AsyncMarker.SyncStar:
      case AsyncMarker.AsyncStar:
      case AsyncMarker.SyncYielding:
        return null;

      default:
        throw 'Unexpected async marker: ${function.asyncMarker}';
    }
  }

  DartType _getYieldType(FunctionNode function) {
    switch (function.asyncMarker) {
      case AsyncMarker.Sync:
      case AsyncMarker.Async:
        return null;

      case AsyncMarker.SyncStar:
      case AsyncMarker.AsyncStar:
        Class container = function.asyncMarker == AsyncMarker.SyncStar
            ? coreTypes.iterableClass
            : coreTypes.streamClass;
        DartType returnType = function.returnType;
        if (returnType is InterfaceType && returnType.classNode == container) {
          return returnType.typeArguments.single;
        }
        return const DynamicType();

      case AsyncMarker.SyncYielding:
        return function.returnType;

      default:
        throw 'Unexpected async marker: ${function.asyncMarker}';
    }
  }

  @override
  DartType visitAsExpression(AsExpression node) {
    if (node.type == const DynamicType()) {
      fail(node, 'dynamic is not allowed in this context');
    }
    node.type = ensureNoDynamic(node.type);
    visitExpression(node.operand);
    return node.type;
  }

  @override
  DartType visitAwaitExpression(AwaitExpression node) {
    return environment.unfutureType(visitExpression(node.operand));
  }

  @override
  DartType visitBoolLiteral(BoolLiteral node) {
    return environment.boolType;
  }

  @override
  DartType visitConditionalExpression(ConditionalExpression node) {
    node.condition =
        checkAndDowncastExpression(node.condition, environment.boolType);

    var thenType = visitExpression(node.then);
    var otherwiseType = visitExpression(node.otherwise);

    node.staticType = checker.leastUpperBound(node, thenType, otherwiseType);
    node.then =
        checkAndDowncastExpressionFrom(node.then, thenType, node.staticType);
    node.otherwise = checkAndDowncastExpressionFrom(
        node.otherwise, otherwiseType, node.staticType);
    return node.staticType;
  }

  @override
  DartType visitConstructorInvocation(ConstructorInvocation node) {
    Constructor target = node.target;
    Arguments arguments = node.arguments;
    Class class_ = target.enclosingClass;
    handleCall(arguments, target.function,
        typeParameters: class_.typeParameters);
    return new InterfaceType(target.enclosingClass, arguments.types);
  }

  @override
  DartType visitDirectMethodInvocation(DirectMethodInvocation node) {
    return handleCall(node.arguments, node.target.function,
        receiver: getReceiverType(node, node.receiver, node.target));
  }

  @override
  DartType visitDirectPropertyGet(DirectPropertyGet node) {
    var receiver = getReceiverType(node, node.receiver, node.target);
    return receiver.substituteType(node.target.getterType);
  }

  @override
  DartType visitDirectPropertySet(DirectPropertySet node) {
    var receiver = getReceiverType(node, node.receiver, node.target);
    var value = visitExpression(node.value);
    checkAssignable(node, value,
        receiver.substituteType(node.target.setterType, contravariant: true));
    return value;
  }

  @override
  DartType visitDoubleLiteral(DoubleLiteral node) {
    return environment.doubleType;
  }

  @override
  DartType visitFunctionExpression(FunctionExpression node) {
    handleNestedFunctionNode(node.function);
    return node.function.functionType;
  }

  @override
  DartType visitIntLiteral(IntLiteral node) {
    return environment.intType;
  }

  @override
  DartType visitInvalidExpression(InvalidExpression node) {
    return const BottomType();
  }

  DartType ensureNoDynamic(DartType type) {
    if (type == const DynamicType()) {
      return environment.objectType;
    } else if (type is InterfaceType && type.typeArguments.isNotEmpty) {
      return new InterfaceType(type.classNode, type.typeArguments.map(ensureNoDynamic).toList());
    } else if (type is FunctionType) {
      return new FunctionType(type.positionalParameters.map(ensureNoDynamic).toList(), ensureNoDynamic(type.returnType),
          namedParameters: type.namedParameters, typeParameters: type.typeParameters, requiredParameterCount: type.requiredParameterCount);
    } else {
      return type;
    }
  }

  @override
  DartType visitIsExpression(IsExpression node) {
    if (node.type == const DynamicType()) {
      fail(node, 'dynamic is not allowed in this context');
    }
    node.type = ensureNoDynamic(node.type);
    visitExpression(node.operand);
    return environment.boolType;
  }

  @override
  DartType visitLet(Let node) {
    var value = visitExpression(node.variable.initializer);
    if (node.variable.type is DynamicType) {
      node.variable.type = value;
    }
    return visitExpression(node.body);
  }

  @override
  DartType visitListLiteral(ListLiteral node) {
    if (node.typeArgument == const DynamicType()) {
      if (node.expressions.isEmpty) {
        fail(node,
            'Empty array literals must have an explicitly specified type argument');
      }

      // We don't permit <dynamic>[...] lists.
      DartType typeArg = null;
      for (var expr in node.expressions) {
        final DartType elemType = visitExpression(expr);
        if (typeArg == null) {
          typeArg = elemType;
        } else if (typeArg != elemType) {
          typeArg = checker.leastUpperBound(expr, typeArg, elemType);
        }
      }
      node.typeArgument = typeArg;
    } else {
      for (int i = 0; i < node.expressions.length; ++i) {
        node.expressions[i] =
            checkAndDowncastExpression(node.expressions[i], node.typeArgument);
      }
    }

    return environment.literalListType(node.typeArgument);
  }

  @override
  DartType visitLogicalExpression(LogicalExpression node) {
    node.left = checkAndDowncastExpression(node.left, environment.boolType);

    final cond = node.left;
    VariableDeclaration promoted;
    DartType outerPromotion;

    if (node.operator == '&&') {
      if (cond is IsExpression) {
        final val = cond.operand;
        if (val is VariableGet &&
            (val.variable.isFinal || !AssignmentFinder.hasAssignmentsTo(val.variable, node.right))) {
          outerPromotion = promotions[val.variable];
          promotions[val.variable] = cond.type;
          promoted = val.variable;
        }
      }
    }
    node.right = checkAndDowncastExpression(node.right, environment.boolType);
    if (promoted != null) {
      promotions[promoted] = outerPromotion;
    }
    return environment.boolType;
  }

  @override
  DartType visitMapLiteral(MapLiteral node) {
    final inferKey = node.keyType == const DynamicType();
    final inferValue = node.valueType == const DynamicType();

    for (var entry in node.entries) {
      if (inferKey) {
        final type = visitExpression(entry.key);
        if (node.keyType == const DynamicType()) {
          node.keyType = type;
        } else {
          node.keyType = checker.leastUpperBound(entry, node.keyType, type);
        }
      } else {
        entry.key = checkAndDowncastExpression(entry.key, node.keyType);
      }

      if (inferValue) {
        final type = visitExpression(entry.value);
        if (node.valueType == const DynamicType()) {
          node.valueType = type;
        } else {
          node.valueType = checker.leastUpperBound(entry, node.valueType, type);
        }
      } else {
        entry.value = checkAndDowncastExpression(entry.value, node.valueType);
      }
    }
    return environment.literalMapType(node.keyType, node.valueType);
  }

  DartType handleDynamicCall(DartType receiver, Arguments arguments) {
    arguments.positional.forEach(visitExpression);
    arguments.named.forEach((NamedExpression n) => visitExpression(n.value));
    return const DynamicType();
  }

  DartType handleFunctionCall(
      TreeNode access, FunctionType function, Arguments arguments) {
    if (function.requiredParameterCount > arguments.positional.length) {
      fail(access, 'Too few positional arguments');
      return const BottomType();
    }
    if (function.positionalParameters.length < arguments.positional.length) {
      fail(access, 'Too many positional arguments');
      return const BottomType();
    }
    if (function.typeParameters.length != arguments.types.length) {
      fail(access, 'Wrong number of type arguments: expected ${function}, found ${arguments}');
      return const BottomType();
    }
    var instantiation =
        Substitution.fromPairs(function.typeParameters, arguments.types);
    for (int i = 0; i < arguments.positional.length; ++i) {
      var expectedType = instantiation.substituteType(
          function.positionalParameters[i],
          contravariant: true);
      arguments.positional[i] =
          checkAndDowncastExpression(arguments.positional[i], expectedType);
    }
    for (int i = 0; i < arguments.named.length; ++i) {
      var argument = arguments.named[i];
      bool found = false;
      for (int j = 0; j < function.namedParameters.length; ++j) {
        if (argument.name == function.namedParameters[j].name) {
          var expectedType = instantiation.substituteType(
              function.namedParameters[j].type,
              contravariant: true);
          argument.value =
              checkAndDowncastExpression(argument.value, expectedType);
          found = true;
          break;
        }
      }
      if (!found) {
        fail(argument.value, 'Unexpected named parameter: ${argument.name}');
        return const BottomType();
      }
    }
    return instantiation.substituteType(function.returnType);
  }

  final LookupCache lookupCache = new LookupCache();

  static bool isBinaryArithmeticOperator(String name) {
    return name == '+' ||
        name == '-' ||
        name == '*' ||
        name == 'remainder' ||
        name == '%' ||
        name == '/' ||
        name == '~/';
  }

  static bool isBinaryComparisonOperator(String name) {
    return name == '==' ||
        name == '!=' ||
        name == '<' ||
        name == '>' ||
        name == '<=' ||
        name == '>=';
  }

  void checkArguments(Arguments args, int expected) {
    if (args.types.isNotEmpty) {
      fail(args.parent, "Expected no type arguments");
    }

    if (args.named.isNotEmpty) {
      fail(args.parent, "Expected no named arguments");
    }

    if (args.positional.length != expected) {
      fail(args.parent,
          "Expected ${expected} arguments, got ${args.positional.length}");
    }
  }

  Member resolveInvocation(DartType receiver, MethodInvocation node) {
    if (receiver is InterfaceType) {
      return lookupCache.lookupInterfaceSelector(
          receiver.classNode, new Selector(SelectorKind.Method, node.name));
    } else if (receiver is FunctionType) {
      if (node.name.name == 'call') {
        return environment.invokeClosure;
      } else if (node.name.name == '==') {
        return coreTypes.getMember('dart:core', 'Object', '==');
      }
    } else if (receiver is TypeParameterType) {
      return resolveInvocation(receiver.parameter.bound, node);
    }

    return null;
  }

  @override
  DartType visitMethodInvocation(MethodInvocation node) {
    if (isUntypedLambda(node.receiver) && node.name.name == 'call') {
      assert(node.arguments.named.isEmpty);
      handleUntypedLambda(
          node.receiver,
          new FunctionType(
              node.arguments.positional.map(visitExpression).toList(),
              const DynamicType()),
          new Set<TypeParameter>());
    }

    final receiver = visitExpression(node.receiver);

    var target = node.interfaceTarget;
    if (target == null) {
      target = resolveInvocation(receiver, node);
      if (target == null) {
        fail(node, "Failed to resolve ${node.name} for ${receiver}");
      }
      node.interfaceTarget = target;
    }

    if (target == environment.invokeClosure) {
      return handleFunctionCall(node, receiver, node.arguments);
    }

    final receiverKind = checker.toTypeKind(node.receiver, receiver);

    if (receiverKind != TypeKind.Reference &&
        target.enclosingClass == coreTypes.numClass) {
      final isArithmetic = isBinaryArithmeticOperator(node.name.name);
      final isComparison = isBinaryComparisonOperator(node.name.name);
      if (isArithmetic || isComparison) {
        checkArguments(node.arguments, 1);
        final rhs = node.arguments.positional[0];
        final argument = visitExpression(rhs);
        final argumentKind = checker.toTypeKind(rhs, argument);

        if (argumentKind == TypeKind.Reference) {
          fail(node,
              "Second argument must be numeric: ${receiver} ${node.name.name} ${argument}");
        }

        var resultKind = receiverKind;
        if (receiverKind != argumentKind) {
          // Argument conversion is necessary.
          final toDouble = coreTypes.getMember('dart:core', 'num', 'toDouble');
          if (receiverKind == TypeKind.Double) {
            node.arguments.positional[0] =
                new DirectMethodInvocation(rhs, toDouble, new Arguments.empty())
                  ..parent = node.arguments;
          } else {
            node.receiver = new DirectMethodInvocation(
                node.receiver, toDouble, new Arguments.empty())
              ..parent = node;
          }
          resultKind = TypeKind.Double;
        }

        if (node.name.name == '/') {
          resultKind = TypeKind.Double;
        }

        return isComparison
            ? environment.boolType
            : (resultKind == TypeKind.Integer
                ? environment.intType
                : environment.doubleType);
      }

      // fail(node, 'Numeric expression requires special rules. ${target}');
    }

    if (target is Procedure) {
      if (environment.isOverloadedArithmeticOperator(target)) {
        assert(node.arguments.positional.length == 1);
        var argument = visitExpression(node.arguments.positional[0]);
        return environment.getTypeOfOverloadedArithmetic(receiver, argument);
      } else {
        return handleCall(node.arguments, target.function,
            receiver: getReceiverTypeImpl(
              receiver, node, node.receiver, node.interfaceTarget));
      }
    } else if (target is Field) {
      if (target.type is! FunctionType) {
        fail(node, 'Expression does not evaluate to function');
      }

      return handleFunctionCall(node, target.type, node.arguments);
    } else {
      fail(node, 'Unexpected target: ${target}');
    }
  }

  @override
  DartType visitPropertyGet(PropertyGet node) {
    var target = node.interfaceTarget;
    if (target == null) {
      final receiver = visitExpression(node.receiver);

      if (receiver is InterfaceType) {
        target = lookupCache.lookupInterfaceSelector(
            receiver.classNode, new Selector(SelectorKind.Getter, node.name));
        if (target == null) {
          fail(node, 'Failed to lookup ${node.name} on ${receiver}');
          return const BottomType();
        }
        node.interfaceTarget = target;
      } else if (receiver is FunctionType) {
        fail(node, "Can't dispatch on FunctionType");
        return const BottomType();
      } else {
        fail(node, "Can't dispatch on ${receiver}.");
        return const BottomType();
      }
    }

    var receiver = getReceiverType(node, node.receiver, node.interfaceTarget);
    return receiver.substituteType(node.interfaceTarget.getterType);
  }

  @override
  DartType visitPropertySet(PropertySet node) {
    var target = node.interfaceTarget;
    if (target == null) {
      final receiver = visitExpression(node.receiver);

      if (receiver is InterfaceType) {
        target = lookupCache.lookupInterfaceSelector(
            receiver.classNode, new Selector(SelectorKind.Setter, node.name));
        if (target == null) {
          fail(node, 'Failed to lookup ${node.name} on ${receiver}');
          return const BottomType();
        }
        node.interfaceTarget = target;
      } else if (receiver is FunctionType) {
        fail(node, "Can't dispatch on FunctionType");
        return const BottomType();
      } else {
        fail(node, "Can't dispatch on ${receiver}.");
        return const BottomType();
      }
    }

    var value = visitExpression(node.value);
    var receiver = getReceiverType(node, node.receiver, node.interfaceTarget);

    node.value = checkAndDowncastExpressionFrom(
        node.value,
        value,
        receiver.substituteType(node.interfaceTarget.setterType,
            contravariant: true));

    return value;
  }

  @override
  DartType visitNot(Not node) {
    visitExpression(node.operand);
    return environment.boolType;
  }

  @override
  DartType visitNullLiteral(NullLiteral node) {
    return const BottomType();
  }

  @override
  DartType visitRethrow(Rethrow node) {
    return const BottomType();
  }

  @override
  DartType visitStaticGet(StaticGet node) {
    return node.target.getterType;
  }

  @override
  DartType visitStaticInvocation(StaticInvocation node) {
    return handleCall(node.arguments, node.target.function);
  }

  @override
  DartType visitStaticSet(StaticSet node) {
    var value = visitExpression(node.value);
    checkAssignable(node.value, value, node.target.setterType);
    return value;
  }

  @override
  DartType visitStringConcatenation(StringConcatenation node) {
    node.expressions.forEach(visitExpression);
    return environment.stringType;
  }

  @override
  DartType visitStringLiteral(StringLiteral node) {
    return environment.stringType;
  }

  @override
  DartType visitSuperMethodInvocation(SuperMethodInvocation node) {
    if (node.interfaceTarget == null) {
      return handleDynamicCall(environment.thisType, node.arguments);
    } else {
      return handleCall(node.arguments, node.interfaceTarget.function,
          receiver: getSuperReceiverType(node.interfaceTarget));
    }
  }

  @override
  DartType visitSuperPropertyGet(SuperPropertyGet node) {
    if (node.interfaceTarget == null) {
      return const DynamicType();
    } else {
      var receiver = getSuperReceiverType(node.interfaceTarget);
      return receiver.substituteType(node.interfaceTarget.getterType);
    }
  }

  @override
  DartType visitSuperPropertySet(SuperPropertySet node) {
    var value = visitExpression(node.value);
    if (node.interfaceTarget != null) {
      var receiver = getSuperReceiverType(node.interfaceTarget);
      checkAssignable(
          node.value,
          value,
          receiver.substituteType(node.interfaceTarget.setterType,
              contravariant: true));
    }
    return value;
  }

  @override
  DartType visitSymbolLiteral(SymbolLiteral node) {
    return environment.symbolType;
  }

  @override
  DartType visitThisExpression(ThisExpression node) {
    return environment.thisType;
  }

  @override
  DartType visitThrow(Throw node) {
    visitExpression(node.expression);
    return const BottomType();
  }

  @override
  DartType visitTypeLiteral(TypeLiteral node) {
    return environment.typeType;
  }

  @override
  DartType visitVariableGet(VariableGet node) {
    node.promotedType ??= promotions[node.variable];
    return node.promotedType ?? node.variable.type;
  }

  @override
  DartType visitVariableSet(VariableSet node) {
    var value = visitExpression(node.value);
    checkAssignable(node.value, value, node.variable.type);
    return value;
  }

  @override
  DartType visitLoadLibrary(LoadLibrary node) {
    return environment.futureType(const DynamicType());
  }

  @override
  DartType visitCheckLibraryIsLoaded(CheckLibraryIsLoaded node) {
    return environment.objectType;
  }

  @override
  DartType visitVectorCreation(VectorCreation node) {
    return const VectorType();
  }

  @override
  DartType visitVectorGet(VectorGet node) {
    var type = visitExpression(node.vectorExpression);
    if (type is! VectorType) {
      fail(
          node.vectorExpression,
          'The type of vector-expression in vector-get node is expected to be '
          'VectorType, but $type found');
    }
    return const DynamicType();
  }

  @override
  visitVectorSet(VectorSet node) {
    var type = visitExpression(node.vectorExpression);
    if (type is! VectorType) {
      fail(
          node.vectorExpression,
          'The type of vector-expression in vector-set node is expected to be '
          'VectorType, but $type found');
    }
    return visitExpression(node.value);
  }

  @override
  visitVectorCopy(VectorCopy node) {
    var type = visitExpression(node.vectorExpression);
    if (type is! VectorType) {
      fail(
          node.vectorExpression,
          'The type of vector-expression in vector-copy node is exected to be '
          'VectorType, but $type found');
    }
    return const VectorType();
  }

  @override
  visitClosureCreation(ClosureCreation node) {
    var contextType = visitExpression(node.contextVector);
    if (contextType is! VectorType) {
      fail(
          node.contextVector,
          "The second child of 'ClosureConversion' node is supposed to be a "
          "Vector, but $contextType found.");
    }
    return node.functionType;
  }

  final List<Object> rollback = [];

  @override
  visitAssertStatement(AssertStatement node) {
    visitExpression(node.condition);

    if (node.parent is Block) {
      final cond = node.condition;
      if (cond is IsExpression) {
        final val = cond.operand;
        if (val is VariableGet &&
            (val.variable.isFinal || !AssignmentFinder.hasAssignmentsTo(val.variable, node.parent))) {
          final outerPromotion = promotions[val.variable];
          promotions[val.variable] = cond.type;
          if (rollback.isEmpty ||
              rollback[rollback.length - 1] != node.parent) {
            rollback.add(new Map<VariableDeclaration, DartType>());
            rollback.add(node.parent);
          }

          Map<VariableDeclaration, DartType> m = rollback[rollback.length - 2];
          m[val.variable] = outerPromotion;
        }
      }
    }

    if (node.message != null) {
      visitExpression(node.message);
    }
  }

  @override
  visitBlock(Block node) {
    node.statements.forEach(visitStatement);
    if (rollback.isNotEmpty && rollback.last == node) {
      Map<VariableDeclaration, DartType> m = rollback[rollback.length - 2];
      m.forEach((v, t) => promotions[v] = t);
      rollback.length -= 2;
    }
  }

  @override
  visitBreakStatement(BreakStatement node) {}

  @override
  visitContinueSwitchStatement(ContinueSwitchStatement node) {}

  @override
  visitDoStatement(DoStatement node) {
    visitStatement(node.body);
    node.condition =
        checkAndDowncastExpression(node.condition, environment.boolType);
  }

  @override
  visitEmptyStatement(EmptyStatement node) {}

  @override
  visitExpressionStatement(ExpressionStatement node) {
    visitExpression(node.expression);
  }

  @override
  visitForInStatement(ForInStatement node) {
    var iterable = visitExpression(node.iterable);
    // TODO(asgerf): Store interface targets on for-in loops or desugar them,
    // instead of doing the ad-hoc resolution here.
    if (node.isAsync) {
      checkAssignable(node, getStreamElementType(iterable), node.variable.type);
    } else {
      checkAssignable(
          node, getIterableElementType(iterable), node.variable.type);
    }
    visitStatement(node.body);
  }

  static final Name iteratorName = new Name('iterator');
  static final Name currentName = new Name('current');

  DartType getIterableElementType(DartType iterable) {
    if (iterable is InterfaceType) {
      var iteratorGetter =
          hierarchy.getInterfaceMember(iterable.classNode, iteratorName);
      if (iteratorGetter == null) return const DynamicType();
      var castedIterable = hierarchy.getTypeAsInstanceOf(
          iterable, iteratorGetter.enclosingClass);
      var iteratorType = Substitution
          .fromInterfaceType(castedIterable)
          .substituteType(iteratorGetter.getterType);
      if (iteratorType is InterfaceType) {
        var currentGetter =
            hierarchy.getInterfaceMember(iteratorType.classNode, currentName);
        if (currentGetter == null) return const DynamicType();
        var castedIteratorType = hierarchy.getTypeAsInstanceOf(
            iteratorType, currentGetter.enclosingClass);
        return Substitution
            .fromInterfaceType(castedIteratorType)
            .substituteType(currentGetter.getterType);
      }
    }
    return const DynamicType();
  }

  DartType getStreamElementType(DartType stream) {
    if (stream is InterfaceType) {
      var asStream =
          hierarchy.getTypeAsInstanceOf(stream, coreTypes.streamClass);
      if (asStream == null) return const DynamicType();
      return asStream.typeArguments.single;
    }
    return const DynamicType();
  }

  @override
  visitForStatement(ForStatement node) {
    node.variables.forEach(visitVariableDeclaration);
    if (node.condition != null) {
      node.condition =
          checkAndDowncastExpression(node.condition, environment.boolType);
    }
    node.updates.forEach(visitExpression);
    visitStatement(node.body);
  }

  @override
  visitFunctionDeclaration(FunctionDeclaration node) {
    handleNestedFunctionNode(node.function);
    node.variable.type = node.function.functionType;
  }

  final Map<VariableDeclaration, DartType> promotions =
      <VariableDeclaration, DartType>{};

  @override
  visitIfStatement(IfStatement node) {
    node.condition =
        checkAndDowncastExpression(node.condition, environment.boolType);
    final cond = node.condition;
    VariableDeclaration promoted;
    DartType outerPromotion;
    if (cond is IsExpression) {
      final val = cond.operand;
      if (val is VariableGet &&
          (val.variable.isFinal || !AssignmentFinder.hasAssignmentsTo(val.variable, node.then))) {
        outerPromotion = promotions[val.variable];
        promotions[val.variable] = cond.type;
        promoted = val.variable;
      }
    }
    visitStatement(node.then);
    if (promoted != null) {
      promotions[promoted] = outerPromotion;
    }
    if (node.otherwise != null) {
      visitStatement(node.otherwise);
    }
  }

  @override
  visitInvalidStatement(InvalidStatement node) {}

  @override
  visitLabeledStatement(LabeledStatement node) {
    visitStatement(node.body);
  }

  @override
  visitReturnStatement(ReturnStatement node) {
    if (node.expression != null) {
      if (environment.returnType == null) {
        fail(node, 'Return of a value from void method');
      } else {
        if (environment.returnType != const DynamicType()) {
          if (isUntypedLambda(node.expression)) {
            handleUntypedLambda(node.expression, environment.returnType,
                new Set<TypeParameter>());
          }
        }

        var type = visitExpression(node.expression);
        if (environment.currentAsyncMarker == AsyncMarker.Async) {
          type = environment.unfutureType(type);
        }
        if (environment.returnType == const DynamicType()) {
          if (!environment.canInferReturnType) {
            fail(node, 'Functions can not have dynamic return type');
          }

          environment.returnType = type;
        }

        checkAssignable(node.expression, type, environment.returnType);
      }
    }
  }

  @override
  visitSwitchStatement(SwitchStatement node) {
    visitExpression(node.expression);
    for (var switchCase in node.cases) {
      switchCase.expressions.forEach(visitExpression);
      visitStatement(switchCase.body);
    }
  }

  @override
  visitTryCatch(TryCatch node) {
    visitStatement(node.body);
    for (var catchClause in node.catches) {
      if (catchClause.exception?.type == const DynamicType()) {
        catchClause.exception.type = environment.objectType;
      }
      if (catchClause.stackTrace?.type == const DynamicType()) {
        catchClause.stackTrace.type = environment.objectType;
      }
      visitStatement(catchClause.body);
    }
  }

  @override
  visitTryFinally(TryFinally node) {
    visitStatement(node.body);
    visitStatement(node.finalizer);
  }

  @override
  visitVariableDeclaration(VariableDeclaration node) {
    if (node.type == const DynamicType()) {
      if (node.initializer == null) {
        fail(
            node, 'Local variables declarated with var must have initializers');
      }
      node.type = visitExpression(node.initializer);
    } else if (node.initializer != null) {
      node.type = ensureNoDynamic(node.type);
      fixupInitializer(node);
      node.initializer =
          checkAndDowncastExpression(node.initializer, node.type);
    }
  }

  @override
  visitWhileStatement(WhileStatement node) {
    node.condition =
        checkAndDowncastExpression(node.condition, environment.boolType);
    visitStatement(node.body);
  }

  @override
  visitYieldStatement(YieldStatement node) {
    if (node.isYieldStar) {
      Class container = environment.currentAsyncMarker == AsyncMarker.AsyncStar
          ? coreTypes.streamClass
          : coreTypes.iterableClass;
      var type = visitExpression(node.expression);
      var asContainer = type is InterfaceType
          ? hierarchy.getTypeAsInstanceOf(type, container)
          : null;
      if (asContainer != null) {
        checkAssignable(node.expression, asContainer.typeArguments[0],
            environment.yieldType);
      } else {
        fail(node.expression, '$type is not an instance of $container');
      }
    } else {
      node.expression =
          checkAndDowncastExpression(node.expression, environment.yieldType);
    }
  }

  @override
  visitFieldInitializer(FieldInitializer node) {
    node.value = checkAndDowncastExpression(node.value, node.field.type);
  }

  @override
  visitRedirectingInitializer(RedirectingInitializer node) {
    handleCall(node.arguments, node.target.function,
        typeParameters: const <TypeParameter>[]);
  }

  @override
  visitSuperInitializer(SuperInitializer node) {
    handleCall(node.arguments, node.target.function,
        typeParameters: const <TypeParameter>[],
        receiver: getSuperReceiverType(node.target));
  }

  @override
  visitLocalInitializer(LocalInitializer node) {
    visitVariableDeclaration(node.variable);
  }

  @override
  visitInvalidInitializer(InvalidInitializer node) {}
}