// Copyright (c) 2017, 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.

import '../common.dart';
import '../elements/elements.dart';
import '../elements/resolution_types.dart'
    show ResolutionDartType, ResolutionInterfaceType;
import '../tree/dartstring.dart';
import '../tree/nodes.dart' as ast;
import '../types/masks.dart';
import '../universe/selector.dart';
import '../world.dart';
import 'type_graph_nodes.dart';

/**
 * The class [SimpleInferrerVisitor] will use when working on types.
 */
class TypeSystem {
  final ClosedWorld closedWorld;

  /// [ElementTypeInformation]s for elements.
  final Map<Element, TypeInformation> typeInformations =
      new Map<Element, TypeInformation>();

  /// [ListTypeInformation] for allocated lists.
  final Map<ast.Node, TypeInformation> allocatedLists =
      new Map<ast.Node, TypeInformation>();

  /// [MapTypeInformation] for allocated Maps.
  final Map<ast.Node, TypeInformation> allocatedMaps =
      new Map<ast.Node, TypeInformation>();

  /// Closures found during the analysis.
  final Set<TypeInformation> allocatedClosures = new Set<TypeInformation>();

  /// Cache of [ConcreteTypeInformation].
  final Map<TypeMask, TypeInformation> concreteTypes =
      new Map<TypeMask, TypeInformation>();

  /// List of [TypeInformation]s allocated inside method bodies (calls,
  /// narrowing, phis, and containers).
  final List<TypeInformation> allocatedTypes = <TypeInformation>[];

  Iterable<TypeInformation> get allTypes => [
        typeInformations.values,
        allocatedLists.values,
        allocatedMaps.values,
        allocatedClosures,
        concreteTypes.values,
        allocatedTypes
      ].expand((x) => x);

  TypeSystem(this.closedWorld) {
    nonNullEmptyType = getConcreteTypeFor(commonMasks.emptyType);
  }

  CommonMasks get commonMasks => closedWorld.commonMasks;

  /// Used to group [TypeInformation] nodes by the element that triggered their
  /// creation.
  MemberTypeInformation _currentMember = null;
  MemberTypeInformation get currentMember => _currentMember;

  void withMember(MemberElement element, action) {
    assert(invariant(element, _currentMember == null,
        message: "Already constructing graph for $_currentMember."));
    _currentMember = getInferredTypeOf(element);
    action();
    _currentMember = null;
  }

  TypeInformation nullTypeCache;
  TypeInformation get nullType {
    if (nullTypeCache != null) return nullTypeCache;
    return nullTypeCache = getConcreteTypeFor(commonMasks.nullType);
  }

  TypeInformation intTypeCache;
  TypeInformation get intType {
    if (intTypeCache != null) return intTypeCache;
    return intTypeCache = getConcreteTypeFor(commonMasks.intType);
  }

  TypeInformation uint32TypeCache;
  TypeInformation get uint32Type {
    if (uint32TypeCache != null) return uint32TypeCache;
    return uint32TypeCache = getConcreteTypeFor(commonMasks.uint32Type);
  }

  TypeInformation uint31TypeCache;
  TypeInformation get uint31Type {
    if (uint31TypeCache != null) return uint31TypeCache;
    return uint31TypeCache = getConcreteTypeFor(commonMasks.uint31Type);
  }

  TypeInformation positiveIntTypeCache;
  TypeInformation get positiveIntType {
    if (positiveIntTypeCache != null) return positiveIntTypeCache;
    return positiveIntTypeCache =
        getConcreteTypeFor(commonMasks.positiveIntType);
  }

  TypeInformation doubleTypeCache;
  TypeInformation get doubleType {
    if (doubleTypeCache != null) return doubleTypeCache;
    return doubleTypeCache = getConcreteTypeFor(commonMasks.doubleType);
  }

  TypeInformation numTypeCache;
  TypeInformation get numType {
    if (numTypeCache != null) return numTypeCache;
    return numTypeCache = getConcreteTypeFor(commonMasks.numType);
  }

  TypeInformation boolTypeCache;
  TypeInformation get boolType {
    if (boolTypeCache != null) return boolTypeCache;
    return boolTypeCache = getConcreteTypeFor(commonMasks.boolType);
  }

  TypeInformation functionTypeCache;
  TypeInformation get functionType {
    if (functionTypeCache != null) return functionTypeCache;
    return functionTypeCache = getConcreteTypeFor(commonMasks.functionType);
  }

  TypeInformation listTypeCache;
  TypeInformation get listType {
    if (listTypeCache != null) return listTypeCache;
    return listTypeCache = getConcreteTypeFor(commonMasks.listType);
  }

  TypeInformation constListTypeCache;
  TypeInformation get constListType {
    if (constListTypeCache != null) return constListTypeCache;
    return constListTypeCache = getConcreteTypeFor(commonMasks.constListType);
  }

  TypeInformation fixedListTypeCache;
  TypeInformation get fixedListType {
    if (fixedListTypeCache != null) return fixedListTypeCache;
    return fixedListTypeCache = getConcreteTypeFor(commonMasks.fixedListType);
  }

  TypeInformation growableListTypeCache;
  TypeInformation get growableListType {
    if (growableListTypeCache != null) return growableListTypeCache;
    return growableListTypeCache =
        getConcreteTypeFor(commonMasks.growableListType);
  }

  TypeInformation mapTypeCache;
  TypeInformation get mapType {
    if (mapTypeCache != null) return mapTypeCache;
    return mapTypeCache = getConcreteTypeFor(commonMasks.mapType);
  }

  TypeInformation constMapTypeCache;
  TypeInformation get constMapType {
    if (constMapTypeCache != null) return constMapTypeCache;
    return constMapTypeCache = getConcreteTypeFor(commonMasks.constMapType);
  }

  TypeInformation stringTypeCache;
  TypeInformation get stringType {
    if (stringTypeCache != null) return stringTypeCache;
    return stringTypeCache = getConcreteTypeFor(commonMasks.stringType);
  }

  TypeInformation typeTypeCache;
  TypeInformation get typeType {
    if (typeTypeCache != null) return typeTypeCache;
    return typeTypeCache = getConcreteTypeFor(commonMasks.typeType);
  }

  TypeInformation dynamicTypeCache;
  TypeInformation get dynamicType {
    if (dynamicTypeCache != null) return dynamicTypeCache;
    return dynamicTypeCache = getConcreteTypeFor(commonMasks.dynamicType);
  }

  TypeInformation asyncFutureTypeCache;
  // Subtype of Future returned by async methods.
  TypeInformation get asyncFutureType {
    if (asyncFutureTypeCache != null) return asyncFutureTypeCache;
    return asyncFutureTypeCache =
        getConcreteTypeFor(commonMasks.asyncFutureType);
  }

  TypeInformation syncStarIterableTypeCache;
  TypeInformation get syncStarIterableType {
    if (syncStarIterableTypeCache != null) return syncStarIterableTypeCache;
    return syncStarIterableTypeCache =
        getConcreteTypeFor(commonMasks.syncStarIterableType);
  }

  TypeInformation asyncStarStreamTypeCache;
  TypeInformation get asyncStarStreamType {
    if (asyncStarStreamTypeCache != null) return asyncStarStreamTypeCache;
    return asyncStarStreamTypeCache =
        getConcreteTypeFor(commonMasks.asyncStarStreamType);
  }

  TypeInformation nonNullEmptyType;

  TypeInformation stringLiteralType(DartString value) {
    return new StringLiteralTypeInformation(value, commonMasks.stringType);
  }

  TypeInformation boolLiteralType(ast.LiteralBool value) {
    return new BoolLiteralTypeInformation(value, commonMasks.boolType);
  }

  /**
   * Returns the least upper bound between [firstType] and
   * [secondType].
   */
  TypeInformation computeLUB(
      TypeInformation firstType, TypeInformation secondType) {
    if (firstType == null) return secondType;
    if (firstType == secondType) return firstType;
    if (firstType == nonNullEmptyType) return secondType;
    if (secondType == nonNullEmptyType) return firstType;
    if (firstType == dynamicType || secondType == dynamicType) {
      return dynamicType;
    }
    return getConcreteTypeFor(
        firstType.type.union(secondType.type, closedWorld));
  }

  /**
   * Returns `true` if `selector` should be updated to reflect the new
   * `receiverType`.
   */
  bool selectorNeedsUpdate(TypeInformation info, TypeMask mask) {
    return info.type != mask;
  }

  /**
   * Returns a new receiver type for this [selector] applied to
   * [receiverType].
   *
   * The option [isConditional] is true when [selector] was seen in a
   * conditional send (e.g.  `a?.selector`), in which case the returned type may
   * be null.
   */
  TypeInformation refineReceiver(Selector selector, TypeMask mask,
      TypeInformation receiver, bool isConditional) {
    if (receiver.type.isExact) return receiver;
    TypeMask otherType = closedWorld.allFunctions.receiverType(selector, mask);
    // Conditional sends (a?.b) can still narrow the possible types of `a`,
    // however, we still need to consider that `a` may be null.
    if (isConditional) {
      // Note: we don't check that receiver.type.isNullable here because this is
      // called during the graph construction.
      otherType = otherType.nullable();
    }
    // If this is refining to nullable subtype of `Object` just return
    // the receiver. We know the narrowing is useless.
    if (otherType.isNullable && otherType.containsAll(closedWorld)) {
      return receiver;
    }
    assert(TypeMask.assertIsNormalized(otherType, closedWorld));
    TypeInformation newType = new NarrowTypeInformation(receiver, otherType);
    allocatedTypes.add(newType);
    return newType;
  }

  /**
   * Returns the intersection between [type] and [annotation].
   * [isNullable] indicates whether the annotation implies a null
   * type.
   */
  TypeInformation narrowType(
      TypeInformation type, ResolutionDartType annotation,
      {bool isNullable: true}) {
    if (annotation.treatAsDynamic) return type;
    if (annotation.isVoid) return nullType;
    if (annotation.element == closedWorld.commonElements.objectClass &&
        isNullable) {
      return type;
    }
    TypeMask otherType;
    if (annotation.isTypedef || annotation.isFunctionType) {
      otherType = functionType.type;
    } else if (annotation.isTypeVariable) {
      // TODO(ngeoffray): Narrow to bound.
      return type;
    } else {
      ResolutionInterfaceType interface = annotation;
      otherType = annotation.element == closedWorld.commonElements.objectClass
          ? dynamicType.type.nonNullable()
          : new TypeMask.nonNullSubtype(interface.element, closedWorld);
    }
    if (isNullable) otherType = otherType.nullable();
    if (type.type.isExact) {
      return type;
    } else {
      assert(TypeMask.assertIsNormalized(otherType, closedWorld));
      TypeInformation newType = new NarrowTypeInformation(type, otherType);
      allocatedTypes.add(newType);
      return newType;
    }
  }

  /**
   * Returns the non-nullable type of [type].
   */
  TypeInformation narrowNotNull(TypeInformation type) {
    if (type.type.isExact && !type.type.isNullable) {
      return type;
    }
    TypeInformation newType =
        new NarrowTypeInformation(type, dynamicType.type.nonNullable());
    allocatedTypes.add(newType);
    return newType;
  }

  ElementTypeInformation getInferredTypeOf(Element element) {
    element = element.implementation;
    return typeInformations.putIfAbsent(element, () {
      return new ElementTypeInformation(element, this);
    });
  }

  /**
   * Returns the internal inferrer representation for [mask].
   */
  ConcreteTypeInformation getConcreteTypeFor(TypeMask mask) {
    assert(mask != null);
    return concreteTypes.putIfAbsent(mask, () {
      return new ConcreteTypeInformation(mask);
    });
  }

  String getInferredSignatureOf(FunctionElement function) {
    ElementTypeInformation info = getInferredTypeOf(function);
    FunctionElement impl = function.implementation;
    FunctionSignature signature = impl.functionSignature;
    var res = "";
    signature.forEachParameter((Element parameter) {
      TypeInformation type = getInferredTypeOf(parameter);
      res += "${res.isEmpty ? '(' : ', '}${type.type} ${parameter.name}";
    });
    res += ") -> ${info.type}";
    return res;
  }

  TypeInformation nonNullSubtype(ClassElement type) {
    return getConcreteTypeFor(
        new TypeMask.nonNullSubtype(type.declaration, closedWorld));
  }

  TypeInformation nonNullSubclass(ClassElement type) {
    return getConcreteTypeFor(
        new TypeMask.nonNullSubclass(type.declaration, closedWorld));
  }

  TypeInformation nonNullExact(ClassElement type) {
    return getConcreteTypeFor(
        new TypeMask.nonNullExact(type.declaration, closedWorld));
  }

  TypeInformation nonNullEmpty() {
    return nonNullEmptyType;
  }

  bool isNull(TypeInformation type) {
    return type == nullType;
  }

  TypeInformation allocateList(
      TypeInformation type, ast.Node node, Element enclosing,
      [TypeInformation elementType, int length]) {
    ClassElement typedDataClass = closedWorld.commonElements.typedDataClass;
    bool isTypedArray = typedDataClass != null &&
        closedWorld.isInstantiated(typedDataClass) &&
        type.type.satisfies(typedDataClass, closedWorld);
    bool isConst = (type.type == commonMasks.constListType);
    bool isFixed =
        (type.type == commonMasks.fixedListType) || isConst || isTypedArray;
    bool isElementInferred = isConst || isTypedArray;

    int inferredLength = isFixed ? length : null;
    TypeMask elementTypeMask =
        isElementInferred ? elementType.type : dynamicType.type;
    ContainerTypeMask mask = new ContainerTypeMask(
        type.type, node, enclosing, elementTypeMask, inferredLength);
    ElementInContainerTypeInformation element =
        new ElementInContainerTypeInformation(currentMember, elementType);
    element.inferred = isElementInferred;

    allocatedTypes.add(element);
    return allocatedLists[node] =
        new ListTypeInformation(currentMember, mask, element, length);
  }

  TypeInformation allocateClosure(ast.Node node, Element element) {
    TypeInformation result =
        new ClosureTypeInformation(currentMember, node, element);
    allocatedClosures.add(result);
    return result;
  }

  TypeInformation allocateMap(
      ConcreteTypeInformation type, ast.Node node, Element element,
      [List<TypeInformation> keyTypes, List<TypeInformation> valueTypes]) {
    assert(keyTypes.length == valueTypes.length);
    bool isFixed = (type.type == commonMasks.constMapType);

    TypeMask keyType, valueType;
    if (isFixed) {
      keyType = keyTypes.fold(nonNullEmptyType.type,
          (type, info) => type.union(info.type, closedWorld));
      valueType = valueTypes.fold(nonNullEmptyType.type,
          (type, info) => type.union(info.type, closedWorld));
    } else {
      keyType = valueType = dynamicType.type;
    }
    MapTypeMask mask =
        new MapTypeMask(type.type, node, element, keyType, valueType);

    TypeInformation keyTypeInfo =
        new KeyInMapTypeInformation(currentMember, null);
    TypeInformation valueTypeInfo =
        new ValueInMapTypeInformation(currentMember, null);
    allocatedTypes.add(keyTypeInfo);
    allocatedTypes.add(valueTypeInfo);

    MapTypeInformation map =
        new MapTypeInformation(currentMember, mask, keyTypeInfo, valueTypeInfo);

    for (int i = 0; i < keyTypes.length; ++i) {
      TypeInformation newType =
          map.addEntryAssignment(keyTypes[i], valueTypes[i], true);
      if (newType != null) allocatedTypes.add(newType);
    }

    // Shortcut: If we already have a first approximation of the key/value type,
    // start propagating it early.
    if (isFixed) map.markAsInferred();

    allocatedMaps[node] = map;
    return map;
  }

  TypeMask newTypedSelector(TypeInformation info, TypeMask mask) {
    // Only type the selector if [info] is concrete, because the other
    // kinds of [TypeInformation] have the empty type at this point of
    // analysis.
    return info.isConcrete ? info.type : mask;
  }

  /**
   * Returns a new type that unions [firstInput] and [secondInput].
   */
  TypeInformation allocateDiamondPhi(
      TypeInformation firstInput, TypeInformation secondInput) {
    PhiElementTypeInformation result =
        new PhiElementTypeInformation(currentMember, null, false, null);
    result.addAssignment(firstInput);
    result.addAssignment(secondInput);
    allocatedTypes.add(result);
    return result;
  }

  PhiElementTypeInformation _addPhi(
      ast.Node node, Local variable, inputType, bool isLoop) {
    PhiElementTypeInformation result =
        new PhiElementTypeInformation(currentMember, node, isLoop, variable);
    allocatedTypes.add(result);
    result.addAssignment(inputType);
    return result;
  }

  /**
   * Returns a new type for holding the potential types of [element].
   * [inputType] is the first incoming type of the phi.
   */
  PhiElementTypeInformation allocatePhi(
      ast.Node node, Local variable, inputType) {
    // Check if [inputType] is a phi for a local updated in
    // the try/catch block [node]. If it is, no need to allocate a new
    // phi.
    if (inputType is PhiElementTypeInformation &&
        inputType.branchNode == node &&
        inputType.branchNode is ast.TryStatement) {
      return inputType;
    }
    return _addPhi(node, variable, inputType, false);
  }

  /**
   * Returns a new type for holding the potential types of [element].
   * [inputType] is the first incoming type of the phi. [allocateLoopPhi]
   * only differs from [allocatePhi] in that it allows the underlying
   * implementation of [TypeSystem] to differentiate Phi nodes due to loops
   * from other merging uses.
   */
  PhiElementTypeInformation allocateLoopPhi(
      ast.Node node, Local variable, inputType) {
    return _addPhi(node, variable, inputType, true);
  }

  /**
   * Simplies the phi representing [element] and of the type
   * [phiType]. For example, if this phi has one incoming input, an
   * implementation of this method could just return that incoming
   * input type.
   */
  TypeInformation simplifyPhi(
      ast.Node node, Local variable, PhiElementTypeInformation phiType) {
    assert(phiType.branchNode == node);
    if (phiType.assignments.length == 1) return phiType.assignments.first;
    return phiType;
  }

  /**
   * Adds [newType] as an input of [phiType].
   */
  PhiElementTypeInformation addPhiInput(Local variable,
      PhiElementTypeInformation phiType, TypeInformation newType) {
    phiType.addAssignment(newType);
    return phiType;
  }

  TypeMask computeTypeMask(Iterable<TypeInformation> assignments) {
    return joinTypeMasks(assignments.map((e) => e.type));
  }

  TypeMask joinTypeMasks(Iterable<TypeMask> masks) {
    var dynamicType = commonMasks.dynamicType;
    // Optimization: we are iterating over masks twice, but because `masks` is a
    // mapped iterable, we save the intermediate results to avoid computing them
    // again.
    var list = [];
    for (TypeMask mask in masks) {
      // Don't do any work on computing unions if we know that after all that
      // work the result will be `dynamic`.
      // TODO(sigmund): change to `mask == dynamicType` so we can continue to
      // track the non-nullable bit.
      if (mask.containsAll(closedWorld)) return dynamicType;
      list.add(mask);
    }

    TypeMask newType = null;
    for (TypeMask mask in list) {
      newType = newType == null ? mask : newType.union(mask, closedWorld);
      // Likewise - stop early if we already reach dynamic.
      if (newType.containsAll(closedWorld)) return dynamicType;
    }

    return newType ?? const TypeMask.nonNullEmpty();
  }
}