// Copyright (c) 2013, 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 locals_handler;

import 'dart:collection' show IterableMixin;
import 'package:kernel/ast.dart' as ir;
import '../elements/entities.dart';
import '../elements/types.dart';
import '../util/util.dart';
import 'inferrer_engine.dart';
import 'type_graph_nodes.dart';

/**
 * A variable scope holds types for variables. It has a link to a
 * parent scope, but never changes the types in that parent. Instead,
 * updates to locals of a parent scope are put in the current scope.
 * The inferrer makes sure updates get merged into the parent scope,
 * once the control flow block has been visited.
 */
class VariableScope {
  Map<Local, TypeInformation> variables;

  /// The parent of this scope. Null for the root scope.
  final VariableScope parent;

  /// The [ir.Node] that created this scope.
  final ir.Node block;

  /// `true` if this scope is for a try block.
  final bool isTry;

  VariableScope(this.block, {VariableScope parent, this.isTry})
      : this.variables = null,
        this.parent = parent {
    assert(isTry == (block is ir.TryCatch || block is ir.TryFinally),
        "Unexpected block $block for isTry=$isTry");
  }

  VariableScope.deepCopyOf(VariableScope other)
      : variables = other.variables == null
            ? null
            : new Map<Local, TypeInformation>.from(other.variables),
        block = other.block,
        isTry = other.isTry,
        parent = other.parent == null
            ? null
            : new VariableScope.deepCopyOf(other.parent);

  VariableScope.topLevelCopyOf(VariableScope other)
      : variables = other.variables == null
            ? null
            : new Map<Local, TypeInformation>.from(other.variables),
        block = other.block,
        isTry = other.isTry,
        parent = other.parent;

  TypeInformation operator [](Local variable) {
    TypeInformation result;
    if (variables == null || (result = variables[variable]) == null) {
      return parent == null ? null : parent[variable];
    }
    return result;
  }

  void operator []=(Local variable, TypeInformation mask) {
    assert(mask != null);
    if (variables == null) {
      variables = new Map<Local, TypeInformation>();
    }
    variables[variable] = mask;
  }

  void forEachOwnLocal(void f(Local variable, TypeInformation type)) {
    if (variables == null) return;
    variables.forEach(f);
  }

  void forEachLocalUntilNode(
      ir.Node node, void f(Local variable, TypeInformation type),
      [Setlet<Local> seenLocals]) {
    if (seenLocals == null) seenLocals = new Setlet<Local>();
    if (variables != null) {
      variables.forEach((variable, type) {
        if (seenLocals.contains(variable)) return;
        seenLocals.add(variable);
        f(variable, type);
      });
    }
    if (node != null && block == node) return;
    if (parent != null) parent.forEachLocalUntilNode(node, f, seenLocals);
  }

  void forEachLocal(void f(Local variable, TypeInformation type)) {
    forEachLocalUntilNode(null, f);
  }

  bool updates(Local variable) {
    if (variables == null) return false;
    return variables.containsKey(variable);
  }

  String toStructuredText(String indent) {
    StringBuffer sb = new StringBuffer();
    _toStructuredText(sb, indent);
    return sb.toString();
  }

  void _toStructuredText(StringBuffer sb, String indent) {
    sb.write('VariableScope($hashCode) [');
    String blockText = block.toString().replaceAll('\n', ' ');
    if (blockText.length > 20) {
      blockText = blockText.substring(0, 17) + '...';
    }
    sb.write('\n${indent}  block: '
        '(${block.runtimeType}:${block.hashCode})${blockText}');
    if (variables != null) {
      sb.write('\n${indent}  variables:');
      variables.forEach((Local local, TypeInformation type) {
        sb.write('\n${indent}    $local: ');
        sb.write(type.toStructuredText('${indent}      '));
      });
    }
    if (parent != null) {
      sb.write('\n${indent}  parent:');
      parent._toStructuredText(sb, '${indent}     ');
    }
    sb.write(']');
  }

  String toString() {
    String rest = parent == null ? "null" : parent.toString();
    return '{$variables} $rest';
  }
}

/// Tracks initializers via initializations and assignments.
class FieldInitializationScope {
  Map<FieldEntity, TypeInformation> fields;
  bool isThisExposed;

  /// `true` when control flow prevents accumulating definite assignments,
  /// e.g. an early return or caught exception.
  bool isIndefinite;

  FieldInitializationScope()
      : isThisExposed = false,
        isIndefinite = false;

  FieldInitializationScope.internalFrom(FieldInitializationScope other)
      : isThisExposed = other.isThisExposed,
        isIndefinite = other.isIndefinite;

  factory FieldInitializationScope.from(FieldInitializationScope other) {
    if (other == null) return null;
    return new FieldInitializationScope.internalFrom(other);
  }

  void updateField(FieldEntity field, TypeInformation type) {
    if (isThisExposed) return;
    if (isIndefinite) return;
    fields ??= new Map<FieldEntity, TypeInformation>();
    fields[field] = type;
  }

  TypeInformation readField(FieldEntity field) {
    return fields == null ? null : fields[field];
  }

  void forEach(void f(FieldEntity element, TypeInformation type)) {
    fields?.forEach(f);
  }

  /// Returns the join between [thenScope] and [elseScope] which models the
  /// flow through either [thenScope] or [elseScope].
  FieldInitializationScope mergeDiamondFlow(InferrerEngine inferrer,
      FieldInitializationScope thenScope, FieldInitializationScope elseScope) {
    assert(elseScope != null);

    // Quick bailout check. If [isThisExposed] or [isIndefinite] is true, we
    // know the code following won'TypeInformation do anything.
    if (isThisExposed) return this;
    if (isIndefinite) return this;

    FieldInitializationScope otherScope =
        elseScope.fields == null ? this : elseScope;

    thenScope.forEach((FieldEntity field, TypeInformation type) {
      TypeInformation otherType = otherScope.readField(field);
      if (otherType == null) return;
      updateField(field, inferrer.types.allocateDiamondPhi(type, otherType));
    });

    isThisExposed = thenScope.isThisExposed || elseScope.isThisExposed;
    isIndefinite = thenScope.isIndefinite || elseScope.isIndefinite;
    return this;
  }
}

/**
 * Placeholder for inferred arguments types on sends.
 */
class ArgumentsTypes extends IterableMixin<TypeInformation> {
  final List<TypeInformation> positional;
  final Map<String, TypeInformation> named;
  ArgumentsTypes(this.positional, named)
      : this.named = (named == null || named.isEmpty) ? const {} : named {
    assert(this.positional.every((TypeInformation type) => type != null));
    assert(this.named.values.every((TypeInformation type) => type != null));
  }

  ArgumentsTypes.empty()
      : positional = const [],
        named = const {};

  int get length => positional.length + named.length;

  Iterator<TypeInformation> get iterator => new ArgumentsTypesIterator(this);

  String toString() => "{ positional = $positional, named = $named }";

  bool operator ==(other) {
    if (positional.length != other.positional.length) return false;
    if (named.length != other.named.length) return false;
    for (int i = 0; i < positional.length; i++) {
      if (positional[i] != other.positional[i]) return false;
    }
    var result = true;
    named.forEach((name, type) {
      if (other.named[name] != type) result = false;
    });
    return result;
  }

  int get hashCode => throw new UnsupportedError('ArgumentsTypes.hashCode');

  bool hasNoArguments() => positional.isEmpty && named.isEmpty;

  void forEach(void f(TypeInformation type)) {
    positional.forEach(f);
    named.values.forEach(f);
  }

  bool every(bool f(TypeInformation type)) {
    return positional.every(f) && named.values.every(f);
  }

  bool contains(Object type) {
    return positional.contains(type) || named.containsValue(type);
  }
}

class ArgumentsTypesIterator implements Iterator<TypeInformation> {
  final Iterator<TypeInformation> positional;
  final Iterator<TypeInformation> named;
  bool _iteratePositional = true;

  ArgumentsTypesIterator(ArgumentsTypes iteratee)
      : positional = iteratee.positional.iterator,
        named = iteratee.named.values.iterator;

  Iterator<TypeInformation> get _currentIterator =>
      _iteratePositional ? positional : named;

  TypeInformation get current => _currentIterator.current;

  bool moveNext() {
    if (_iteratePositional && positional.moveNext()) {
      return true;
    }
    _iteratePositional = false;
    return named.moveNext();
  }
}

/**
 * Placeholder for inferred types of local variables.
 */
class LocalsHandler {
  final VariableScope _locals;

  LocalsHandler(ir.Node block)
      : _locals = new VariableScope(block, isTry: false);

  LocalsHandler.from(LocalsHandler other, ir.Node block, {bool isTry: false})
      : _locals = new VariableScope(block, isTry: isTry, parent: other._locals);

  LocalsHandler.deepCopyOf(LocalsHandler other)
      : _locals = new VariableScope.deepCopyOf(other._locals);

  TypeInformation use(InferrerEngine inferrer, Local local) {
    return _locals[local];
  }

  void update(InferrerEngine inferrer, Local local, TypeInformation type,
      ir.Node node, DartType staticType, LocalsHandler tryBlock) {
    if (tryBlock != null) {
      // We don't know if an assignment in a try block
      // will be executed, so all assignments in that block are
      // potential types after we have left it. We update the parent
      // of the try block so that, at exit of the try block, we get
      // the right phi for it.
      TypeInformation existing = tryBlock._locals.parent[local];
      if (existing != null) {
        TypeInformation phiType = inferrer.types.allocatePhi(
            tryBlock._locals.block, local, existing,
            isTry: tryBlock._locals.isTry);
        TypeInformation inputType =
            inferrer.types.addPhiInput(local, phiType, type);
        tryBlock._locals.parent[local] = inputType;
      }
      // Update the current handler unconditionally with the new
      // type.
      _locals[local] = type;
    } else {
      _locals[local] = type;
    }
  }

  /// Returns the join between this locals handler and [other] which models the
  /// flow through either this or [other].
  ///
  /// If [inPlace] is `true`, the variable types in this locals handler are
  /// replaced by the variables types in [other]. Otherwise the variable types
  /// from both are merged with a phi type.
  LocalsHandler mergeFlow(InferrerEngine inferrer, LocalsHandler other,
      {bool inPlace: false}) {
    other._locals.forEachLocalUntilNode(_locals.block,
        (Local local, TypeInformation type) {
      TypeInformation myType = _locals[local];
      if (myType == null) return; // Variable is only defined in [other].
      if (type == myType) return;
      _locals[local] =
          inPlace ? type : inferrer.types.allocateDiamondPhi(myType, type);
    });
    return this;
  }

  /// Returns the join between [thenBranch] and [elseBranch] which models the
  /// flow through either [thenBranch] or [elseBranch].
  LocalsHandler mergeDiamondFlow(InferrerEngine inferrer,
      LocalsHandler thenBranch, LocalsHandler elseBranch) {
    assert(elseBranch != null);

    void mergeLocal(Local local) {
      TypeInformation myType = _locals[local];
      if (myType == null) return;
      TypeInformation elseType = elseBranch._locals[local];
      TypeInformation thenType = thenBranch._locals[local];
      if (thenType == elseType) {
        _locals[local] = thenType;
      } else {
        _locals[local] = inferrer.types.allocateDiamondPhi(thenType, elseType);
      }
    }

    thenBranch._locals.forEachLocalUntilNode(_locals.block, (Local local, _) {
      mergeLocal(local);
    });
    elseBranch._locals.forEachLocalUntilNode(_locals.block, (Local local, _) {
      // Discard locals we already processed when iterating over
      // [thenBranch]'s locals.
      if (!thenBranch._locals.updates(local)) mergeLocal(local);
    });
    return this;
  }

  /**
   * Merge all [LocalsHandler] in [handlers] into [:this:].
   *
   * If [keepOwnLocals] is true, the types of locals in this
   * [LocalsHandler] are being used in the merge. [keepOwnLocals]
   * should be true if this [LocalsHandler], the dominator of
   * all [handlers], also directly flows into the join point,
   * that is the code after all [handlers]. For example, consider:
   *
   * [: switch (...) {
   *      case 1: ...; break;
   *    }
   * :]
   *
   * The [LocalsHandler] at entry of the switch also flows into the
   * exit of the switch, because there is no default case. So the
   * types of locals at entry of the switch have to take part to the
   * merge.
   *
   * The above situation is also true for labeled statements like
   *
   * [: L: {
   *      if (...) break;
   *      ...
   *    }
   * :]
   *
   * where [:this:] is the [LocalsHandler] for the paths through the
   * labeled statement that do not break out.
   */
  LocalsHandler mergeAfterBreaks(
      InferrerEngine inferrer, Iterable<LocalsHandler> handlers,
      {bool keepOwnLocals: true}) {
    ir.Node level = _locals.block;
    // Use a separate locals handler to perform the merge in, so that Phi
    // creation does not invalidate previous type knowledge while we might
    // still look it up.
    LocalsHandler merged =
        new LocalsHandler.from(this, level, isTry: _locals.isTry);
    Set<Local> seenLocals = new Setlet<Local>();
    // Merge all other handlers.
    for (LocalsHandler handler in handlers) {
      merged._mergeHandler(inferrer, handler, seenLocals);
    }
    // If we want to keep own locals, we merge [seenLocals] from [this] into
    // [merged] to update the Phi nodes with original values.
    if (keepOwnLocals) {
      for (Local variable in seenLocals) {
        TypeInformation originalType = _locals[variable];
        if (originalType != null) {
          merged._locals[variable] = inferrer.types
              .addPhiInput(variable, merged._locals[variable], originalType);
        }
      }
    }
    // Clean up Phi nodes with single input and store back result into
    // actual locals handler.
    merged._locals.forEachLocalUntilNode(_locals.block,
        (Local variable, TypeInformation type) {
      _locals[variable] = inferrer.types.simplifyPhi(level, variable, type);
    });
    return this;
  }

  /**
   * Merge [other] into this handler. Returns whether a local in this
   * has changed. If [seen] is not null, we allocate new Phi nodes
   * unless the local is already present in the set [seen]. This effectively
   * overwrites the current type knowledge in this handler.
   */
  bool _mergeHandler(InferrerEngine inferrer, LocalsHandler other,
      [Set<Local> seen]) {
    bool changed = false;
    other._locals.forEachLocalUntilNode(_locals.block, (local, otherType) {
      TypeInformation myType = _locals[local];
      if (myType == null) return;
      TypeInformation newType;
      if (seen != null && !seen.contains(local)) {
        newType = inferrer.types
            .allocatePhi(_locals.block, local, otherType, isTry: _locals.isTry);
        seen.add(local);
      } else {
        newType = inferrer.types.addPhiInput(local, myType, otherType);
      }
      if (newType != myType) {
        changed = true;
        _locals[local] = newType;
      }
    });
    return changed;
  }

  /**
   * Merge all [LocalsHandler] in [handlers] into this handler.
   * Returns whether a local in this handler has changed.
   */
  bool mergeAll(InferrerEngine inferrer, Iterable<LocalsHandler> handlers) {
    bool changed = false;
    handlers.forEach((other) {
      changed = _mergeHandler(inferrer, other) || changed;
    });
    return changed;
  }

  void startLoop(InferrerEngine inferrer, ir.Node loop) {
    _locals.forEachLocal((Local variable, TypeInformation type) {
      TypeInformation newType =
          inferrer.types.allocateLoopPhi(loop, variable, type, isTry: false);
      if (newType != type) {
        _locals[variable] = newType;
      }
    });
  }

  void endLoop(InferrerEngine inferrer, ir.Node loop) {
    _locals.forEachLocal((Local variable, TypeInformation type) {
      TypeInformation newType =
          inferrer.types.simplifyPhi(loop, variable, type);
      if (newType != type) {
        _locals[variable] = newType;
      }
    });
  }

  String toStructuredText(String indent) {
    StringBuffer sb = new StringBuffer();
    _toStructuredText(sb, indent);
    return sb.toString();
  }

  void _toStructuredText(StringBuffer sb, String indent) {
    sb.write('LocalsHandler($hashCode) [');
    sb.write('\n${indent}  locals:');
    _locals._toStructuredText(sb, '${indent}    ');
    sb.write('\n]');
  }

  String toString() {
    StringBuffer sb = new StringBuffer();
    sb.write('LocalsHandler(');
    sb.write('locals=$_locals');
    sb.write(')');
    return sb.toString();
  }
}