pkg/kernel/lib/type_environment.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_environment;

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

import 'src/hierarchy_based_type_environment.dart'
    show HierarchyBasedTypeEnvironment;

typedef void ErrorHandler(TreeNode node, String message);

abstract class TypeEnvironment extends SubtypeTester {
  final CoreTypes coreTypes;

  InterfaceType thisType;

  DartType returnType;
  DartType yieldType;
  AsyncMarker currentAsyncMarker = AsyncMarker.Sync;

  /// An error handler for use in debugging, or `null` if type errors should not
  /// be tolerated.  See [typeError].
  ErrorHandler errorHandler;

  TypeEnvironment.fromSubclass(this.coreTypes);

  factory TypeEnvironment(CoreTypes coreTypes, ClassHierarchy hierarchy) {
    return new HierarchyBasedTypeEnvironment(coreTypes, hierarchy);
  }

  Class get intClass => coreTypes.intClass;
  Class get numClass => coreTypes.numClass;
  Class get futureOrClass => coreTypes.futureOrClass;

  InterfaceType get objectLegacyRawType => coreTypes.objectLegacyRawType;
  InterfaceType get nullType => coreTypes.nullType;
  InterfaceType get functionLegacyRawType => coreTypes.functionLegacyRawType;

  InterfaceType literalListType(DartType elementType) {
    return new InterfaceType(coreTypes.listClass, <DartType>[elementType]);
  }

  InterfaceType literalSetType(DartType elementType) {
    return new InterfaceType(coreTypes.setClass, <DartType>[elementType]);
  }

  InterfaceType literalMapType(DartType key, DartType value) {
    return new InterfaceType(coreTypes.mapClass, <DartType>[key, value]);
  }

  InterfaceType iterableType(DartType type) {
    return new InterfaceType(coreTypes.iterableClass, <DartType>[type]);
  }

  InterfaceType streamType(DartType type) {
    return new InterfaceType(coreTypes.streamClass, <DartType>[type]);
  }

  InterfaceType futureType(DartType type) {
    return new InterfaceType(coreTypes.futureClass, <DartType>[type]);
  }

  /// Removes a level of `Future<>` types wrapping a type.
  ///
  /// This implements the function `flatten` from the spec, which unwraps a
  /// layer of Future or FutureOr from a type.
  DartType unfutureType(DartType type) {
    if (type is InterfaceType) {
      if (type.classNode == coreTypes.futureOrClass ||
          type.classNode == coreTypes.futureClass) {
        return type.typeArguments[0];
      }
      // It is a compile-time error to implement, extend, or mixin FutureOr so
      // we aren't concerned with it.  If a class implements multiple
      // instantiations of Future, getTypeAsInstanceOf is responsible for
      // picking the least one in the sense required by the spec.
      InterfaceType future = getTypeAsInstanceOf(type, coreTypes.futureClass);
      if (future != null) {
        return future.typeArguments[0];
      }
    }
    return type;
  }

  /// Called if the computation of a static type failed due to a type error.
  ///
  /// This should never happen in production.  The frontend should report type
  /// errors, and either recover from the error during translation or abort
  /// compilation if unable to recover.
  ///
  /// By default, this throws an exception, since programs in kernel are assumed
  /// to be correctly typed.
  ///
  /// An [errorHandler] may be provided in order to override the default
  /// behavior and tolerate the presence of type errors.  This can be useful for
  /// debugging IR producers which are required to produce a strongly typed IR.
  void typeError(TreeNode node, String message) {
    if (errorHandler != null) {
      errorHandler(node, message);
    } else {
      throw '$message in $node';
    }
  }

  /// True if [member] is a binary operator that returns an `int` if both
  /// operands are `int`, and otherwise returns `double`.
  ///
  /// This is a case of type-based overloading, which in Dart is only supported
  /// by giving special treatment to certain arithmetic operators.
  bool isOverloadedArithmeticOperator(Procedure member) {
    Class class_ = member.enclosingClass;
    if (class_ == coreTypes.intClass || class_ == coreTypes.numClass) {
      String name = member.name.name;
      return name == '+' ||
          name == '-' ||
          name == '*' ||
          name == 'remainder' ||
          name == '%';
    }
    return false;
  }

  /// Returns the static return type of an overloaded arithmetic operator
  /// (see [isOverloadedArithmeticOperator]) given the static type of the
  /// operands.
  ///
  /// If both types are `int`, the returned type is `int`.
  /// If either type is `double`, the returned type is `double`.
  /// If both types refer to the same type variable (typically with `num` as
  /// the upper bound), then that type variable is returned.
  /// Otherwise `num` is returned.
  DartType getTypeOfOverloadedArithmetic(DartType type1, DartType type2) {
    if (type1 == type2) return type1;
    if (type1 == coreTypes.doubleLegacyRawType ||
        type2 == coreTypes.doubleLegacyRawType)
      return coreTypes.doubleLegacyRawType;
    return coreTypes.numLegacyRawType;
  }
}

/// The value enum for internal states of [IsSubtypeOf].
enum _IsSubtypeOfValues {
  always,
  onlyIfIgnoringNullabilities,
  never,
}

/// Result of a nullability-aware subtype check.
///
/// It is assumed that if a subtype check succeeds for two types in full-NNBD
/// mode, it also succeeds for those two types if the nullability markers on the
/// types and all of their sub-terms are ignored (that is, in the pre-NNBD
/// mode).  By contraposition, if a subtype check fails for two types when the
/// nullability markers are ignored, it should also fail for those types in
/// full-NNBD mode.
class IsSubtypeOf {
  final _IsSubtypeOfValues _value;

  /// Subtype check succeeds in both modes.
  const IsSubtypeOf.always() : _value = _IsSubtypeOfValues.always;

  /// Subtype check succeeds only if the nullability markers are ignored.
  ///
  /// This implies that if the nullability markers aren't ignored, the subtype
  /// check fails.
  const IsSubtypeOf.onlyIfIgnoringNullabilities()
      : _value = _IsSubtypeOfValues.onlyIfIgnoringNullabilities;

  /// Subtype check fails in both modes.
  const IsSubtypeOf.never() : _value = _IsSubtypeOfValues.never;

  bool isSubtypeWhenIgnoringNullabilities() {
    return _value != _IsSubtypeOfValues.never;
  }

  bool isSubtypeWhenUsingNullabilities() {
    return _value == _IsSubtypeOfValues.always;
  }
}

enum SubtypeCheckMode {
  withNullabilities,
  ignoringNullabilities,
}

/// The part of [TypeEnvironment] that deals with subtype tests.
///
/// This lives in a separate class so it can be tested independently of the SDK.
abstract class SubtypeTester {
  InterfaceType get objectLegacyRawType;
  InterfaceType get nullType;
  InterfaceType get functionLegacyRawType;
  Class get futureOrClass;
  InterfaceType futureType(DartType type);

  static List<Object> typeChecks;

  InterfaceType getTypeAsInstanceOf(InterfaceType type, Class superclass);

  /// Determines if the given type is at the top of the type hierarchy.  May be
  /// overridden in subclasses.
  bool isTop(DartType type) {
    return type is DynamicType ||
        type is VoidType ||
        type == objectLegacyRawType;
  }

  /// Can be use to collect type checks. To use:
  /// 1. Rename `isSubtypeOf` to `_isSubtypeOf`.
  /// 2. Rename `_collect_isSubtypeOf` to `isSubtypeOf`.
  /// 3. Comment out the call to `_isSubtypeOf` below.
  // ignore:unused_element
  bool _collect_isSubtypeOf(DartType subtype, DartType supertype) {
    bool result = true;
    // result = _isSubtypeOf(subtype, supertype);
    typeChecks ??= <Object>[];
    typeChecks.add([subtype, supertype, result]);
    return result;
  }

  /// Returns true if [subtype] is a subtype of [supertype].
  bool isSubtypeOf(
      DartType subtype, DartType supertype, SubtypeCheckMode mode) {
    IsSubtypeOf result =
        performNullabilityAwareSubtypeCheck(subtype, supertype);
    switch (mode) {
      case SubtypeCheckMode.ignoringNullabilities:
        return result.isSubtypeWhenIgnoringNullabilities();
      case SubtypeCheckMode.withNullabilities:
        return result.isSubtypeWhenUsingNullabilities();
      default:
        throw new StateError("Unhandled subtype checking mode '$mode'");
    }
  }

  /// Performs a nullability-aware subtype check.
  ///
  /// The outcome is described in the comments to [IsSubtypeOf].
  IsSubtypeOf performNullabilityAwareSubtypeCheck(
      DartType subtype, DartType supertype) {
    subtype = subtype.unalias;
    supertype = supertype.unalias;
    if (identical(subtype, supertype)) return const IsSubtypeOf.always();
    if (subtype is BottomType) return const IsSubtypeOf.always();
    if (subtype == nullType) {
      // See rule 4 of the subtype rules from the Dart Language Specification.
      return supertype is BottomType
          ? const IsSubtypeOf.never()
          : const IsSubtypeOf.always();
    }
    if (isTop(supertype)) return const IsSubtypeOf.always();

    // Handle FutureOr<T> union type.
    if (subtype is InterfaceType &&
        identical(subtype.classNode, futureOrClass)) {
      var subtypeArg = subtype.typeArguments[0];
      if (supertype is InterfaceType &&
          identical(supertype.classNode, futureOrClass)) {
        var supertypeArg = supertype.typeArguments[0];
        // FutureOr<A> <: FutureOr<B> iff A <: B
        return performNullabilityAwareSubtypeCheck(subtypeArg, supertypeArg);
      }

      // given t1 is Future<A> | A, then:
      // (Future<A> | A) <: t2 iff Future<A> <: t2 and A <: t2.
      var subtypeFuture = futureType(subtypeArg);
      return performNullabilityAwareSubtypeCheck(subtypeFuture, supertype)
                  .isSubtypeWhenIgnoringNullabilities() &&
              performNullabilityAwareSubtypeCheck(subtypeArg, supertype)
                  .isSubtypeWhenIgnoringNullabilities()
          ? const IsSubtypeOf.always()
          : const IsSubtypeOf.never();
    }

    if (supertype is InterfaceType &&
        identical(supertype.classNode, futureOrClass)) {
      // given t2 is Future<A> | A, then:
      // t1 <: (Future<A> | A) iff t1 <: Future<A> or t1 <: A
      var supertypeArg = supertype.typeArguments[0];
      var supertypeFuture = futureType(supertypeArg);
      return performNullabilityAwareSubtypeCheck(subtype, supertypeFuture)
                  .isSubtypeWhenIgnoringNullabilities() ||
              performNullabilityAwareSubtypeCheck(subtype, supertypeArg)
                  .isSubtypeWhenIgnoringNullabilities()
          ? const IsSubtypeOf.always()
          : const IsSubtypeOf.never();
    }

    if (subtype is InterfaceType && supertype is InterfaceType) {
      var upcastType = getTypeAsInstanceOf(subtype, supertype.classNode);
      if (upcastType == null) return const IsSubtypeOf.never();
      for (int i = 0; i < upcastType.typeArguments.length; ++i) {
        // Termination: the 'supertype' parameter decreases in size.
        int variance = upcastType.classNode.typeParameters[i].variance;
        DartType leftType = upcastType.typeArguments[i];
        DartType rightType = supertype.typeArguments[i];
        if (variance == Variance.contravariant) {
          if (!performNullabilityAwareSubtypeCheck(rightType, leftType)
              .isSubtypeWhenIgnoringNullabilities()) {
            return const IsSubtypeOf.never();
          }
        } else if (variance == Variance.invariant) {
          if (!performNullabilityAwareSubtypeCheck(rightType, leftType)
                  .isSubtypeWhenIgnoringNullabilities() ||
              !performNullabilityAwareSubtypeCheck(leftType, rightType)
                  .isSubtypeWhenIgnoringNullabilities()) {
            return const IsSubtypeOf.never();
          }
        } else {
          if (!performNullabilityAwareSubtypeCheck(leftType, rightType)
              .isSubtypeWhenIgnoringNullabilities()) {
            return const IsSubtypeOf.never();
          }
        }
      }
      return const IsSubtypeOf.always();
    }
    if (subtype is TypeParameterType) {
      if (supertype is TypeParameterType &&
          subtype.parameter == supertype.parameter) {
        if (supertype.promotedBound != null) {
          return performNullabilityAwareSubtypeCheck(
              subtype.bound, supertype.bound);
        } else {
          // Promoted bound should always be a subtype of the declared bound.
          assert(subtype.promotedBound == null ||
              performNullabilityAwareSubtypeCheck(
                      subtype.bound, supertype.bound)
                  .isSubtypeWhenIgnoringNullabilities());
          return const IsSubtypeOf.always();
        }
      }
      // Termination: if there are no cyclically bound type parameters, this
      // recursive call can only occur a finite number of times, before reaching
      // a shrinking recursive call (or terminating).
      return performNullabilityAwareSubtypeCheck(subtype.bound, supertype);
    }
    if (subtype is FunctionType) {
      if (supertype == functionLegacyRawType) return const IsSubtypeOf.always();
      if (supertype is FunctionType) {
        return _performNullabilityAwareFunctionSubtypeCheck(subtype, supertype);
      }
    }
    return const IsSubtypeOf.never();
  }

  IsSubtypeOf _performNullabilityAwareFunctionSubtypeCheck(
      FunctionType subtype, FunctionType supertype) {
    if (subtype.requiredParameterCount > supertype.requiredParameterCount) {
      return const IsSubtypeOf.never();
    }
    if (subtype.positionalParameters.length <
        supertype.positionalParameters.length) {
      return const IsSubtypeOf.never();
    }
    if (subtype.typeParameters.length != supertype.typeParameters.length) {
      return const IsSubtypeOf.never();
    }
    if (subtype.typeParameters.isNotEmpty) {
      var substitution = <TypeParameter, DartType>{};
      for (int i = 0; i < subtype.typeParameters.length; ++i) {
        var subParameter = subtype.typeParameters[i];
        var superParameter = supertype.typeParameters[i];
        substitution[subParameter] = new TypeParameterType(superParameter);
      }
      for (int i = 0; i < subtype.typeParameters.length; ++i) {
        var subParameter = subtype.typeParameters[i];
        var superParameter = supertype.typeParameters[i];
        var subBound = substitute(subParameter.bound, substitution);
        // Termination: if there are no cyclically bound type parameters, this
        // recursive call can only occur a finite number of times before
        // reaching a shrinking recursive call (or terminating).
        // TODO(dmitryas): Replace it with one recursive descent instead of two.
        if (!performNullabilityAwareSubtypeCheck(superParameter.bound, subBound)
                .isSubtypeWhenIgnoringNullabilities() ||
            !performNullabilityAwareSubtypeCheck(subBound, superParameter.bound)
                .isSubtypeWhenIgnoringNullabilities()) {
          return const IsSubtypeOf.never();
        }
      }
      subtype = substitute(subtype.withoutTypeParameters, substitution);
    }
    if (!performNullabilityAwareSubtypeCheck(
            subtype.returnType, supertype.returnType)
        .isSubtypeWhenIgnoringNullabilities()) {
      return const IsSubtypeOf.never();
    }
    for (int i = 0; i < supertype.positionalParameters.length; ++i) {
      var supertypeParameter = supertype.positionalParameters[i];
      var subtypeParameter = subtype.positionalParameters[i];
      // Termination: Both types shrink in size.
      if (!performNullabilityAwareSubtypeCheck(
              supertypeParameter, subtypeParameter)
          .isSubtypeWhenIgnoringNullabilities()) {
        return const IsSubtypeOf.never();
      }
    }
    int subtypeNameIndex = 0;
    for (NamedType supertypeParameter in supertype.namedParameters) {
      while (subtypeNameIndex < subtype.namedParameters.length &&
          subtype.namedParameters[subtypeNameIndex].name !=
              supertypeParameter.name) {
        ++subtypeNameIndex;
      }
      if (subtypeNameIndex == subtype.namedParameters.length) {
        return const IsSubtypeOf.never();
      }
      NamedType subtypeParameter = subtype.namedParameters[subtypeNameIndex];
      // Termination: Both types shrink in size.
      if (!performNullabilityAwareSubtypeCheck(
              supertypeParameter.type, subtypeParameter.type)
          .isSubtypeWhenIgnoringNullabilities()) {
        return const IsSubtypeOf.never();
      }
    }
    return const IsSubtypeOf.always();
  }
}