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

import '../common_elements.dart' show CommonElements;
import '../constants/values.dart';
import '../elements/entities.dart';
import '../js_backend/interceptor_data.dart';
import '../types/abstract_value_domain.dart';
import '../universe/selector.dart' show Selector;
import '../world.dart' show JClosedWorld;
import 'nodes.dart';
import 'optimize.dart';

/**
 * This phase simplifies interceptors in multiple ways:
 *
 * 1) If the interceptor is for an object whose type is known, it
 * tries to use a constant interceptor instead.
 *
 * 2) Interceptors are specialized based on the selector it is used with.
 *
 * 3) If we know the object is not intercepted, we just use the object
 * instead.
 *
 * 4) Single use interceptors at dynamic invoke sites are replaced with 'one
 * shot interceptors' which are synthesized static helper functions that fetch
 * the interceptor and then call the method.  This saves code size and makes the
 * receiver of an intercepted call a candidate for being generated at use site.
 *
 * 5) Some HIs operations on an interceptor are replaced with a HIs version that
 * uses 'instanceof' rather than testing a type flag.
 *
 */
class SsaSimplifyInterceptors extends HBaseVisitor
    implements OptimizationPhase {
  final String name = "SsaSimplifyInterceptors";
  final JClosedWorld _closedWorld;
  final ClassEntity _enclosingClass;
  HGraph _graph;

  SsaSimplifyInterceptors(this._closedWorld, this._enclosingClass);

  CommonElements get _commonElements => _closedWorld.commonElements;

  InterceptorData get _interceptorData => _closedWorld.interceptorData;

  AbstractValueDomain get _abstractValueDomain =>
      _closedWorld.abstractValueDomain;

  void visitGraph(HGraph graph) {
    this._graph = graph;
    visitDominatorTree(graph);
  }

  void visitBasicBlock(HBasicBlock node) {
    currentBlock = node;

    HInstruction instruction = node.first;
    while (instruction != null) {
      bool shouldRemove = instruction.accept(this);
      HInstruction next = instruction.next;
      if (shouldRemove) {
        instruction.block.remove(instruction);
      }
      instruction = next;
    }
  }

  bool visitInstruction(HInstruction instruction) => false;

  bool visitInvoke(HInvoke invoke) {
    if (!invoke.isInterceptedCall) return false;
    dynamic interceptor = invoke.inputs[0];
    if (interceptor is! HInterceptor) return false;

    // TODO(sra): Move this per-call code to visitInterceptor.
    //
    // The interceptor is visited first, so we get here only when the
    // interceptor was not rewritten to a single shared replacement.  I'm not
    // sure we should substitute a constant interceptor on a per-call basis if
    // the interceptor is already available in a local variable, but it is
    // possible that all uses can be rewritten to use different constants.

    HInstruction constant = tryComputeConstantInterceptor(
        invoke.inputs[1], interceptor.interceptedClasses);
    if (constant != null) {
      invoke.changeUse(interceptor, constant);
    }
    return false;
  }

  bool canUseSelfForInterceptor(HInstruction receiver,
      {Set<ClassEntity> interceptedClasses}) {
    if (receiver.canBePrimitive(_abstractValueDomain)) {
      // Primitives always need interceptors.
      return false;
    }
    if (receiver.canBeNull(_abstractValueDomain)) {
      if (interceptedClasses == null ||
          interceptedClasses.contains(_commonElements.jsNullClass)) {
        // Need the JSNull interceptor.
        return false;
      }
    }

    // All intercepted classes extend `Interceptor`, so if the receiver can't be
    // a class extending `Interceptor` then it can be called directly.
    return !_abstractValueDomain.canBeInterceptor(receiver.instructionType);
  }

  HInstruction tryComputeConstantInterceptor(
      HInstruction input, Set<ClassEntity> interceptedClasses) {
    ClassEntity constantInterceptor = tryComputeConstantInterceptorFromType(
        input.instructionType, interceptedClasses);

    if (constantInterceptor == null) return null;

    // If we just happen to be in an instance method of the constant
    // interceptor, `this` is a shorter alias.
    if (constantInterceptor == _enclosingClass &&
        _graph.thisInstruction != null) {
      return _graph.thisInstruction;
    }

    ConstantValue constant = new InterceptorConstantValue(constantInterceptor);
    return _graph.addConstant(constant, _closedWorld);
  }

  ClassEntity tryComputeConstantInterceptorFromType(
      AbstractValue type, Set<ClassEntity> interceptedClasses) {
    if (_abstractValueDomain.canBeNull(type)) {
      if (_abstractValueDomain.isNull(type)) {
        return _commonElements.jsNullClass;
      }
    } else if (_abstractValueDomain.isIntegerOrNull(type)) {
      return _commonElements.jsIntClass;
    } else if (_abstractValueDomain.isDoubleOrNull(type)) {
      return _commonElements.jsDoubleClass;
    } else if (_abstractValueDomain.isBooleanOrNull(type)) {
      return _commonElements.jsBoolClass;
    } else if (_abstractValueDomain.isStringOrNull(type)) {
      return _commonElements.jsStringClass;
    } else if (_abstractValueDomain.isArray(type)) {
      return _commonElements.jsArrayClass;
    } else if (_abstractValueDomain.isNumberOrNull(type) &&
        !interceptedClasses.contains(_commonElements.jsIntClass) &&
        !interceptedClasses.contains(_commonElements.jsDoubleClass)) {
      // If the method being intercepted is not defined in [int] or [double] we
      // can safely use the number interceptor.  This is because none of the
      // [int] or [double] methods are called from a method defined on [num].
      return _commonElements.jsNumberClass;
    } else {
      // Try to find constant interceptor for a native class.  If the receiver
      // is constrained to a leaf native class, we can use the class's
      // interceptor directly.

      // TODO(sra): Key DOM classes like Node, Element and Event are not leaf
      // classes.  When the receiver type is not a leaf class, we might still be
      // able to use the receiver class as a constant interceptor.  It is
      // usually the case that methods defined on a non-leaf class don't test
      // for a subclass or call methods defined on a subclass.  Provided the
      // code is completely insensitive to the specific instance subclasses, we
      // can use the non-leaf class directly.
      ClassEntity element = _abstractValueDomain.getExactClass(type);
      if (element != null && _closedWorld.nativeData.isNativeClass(element)) {
        return element;
      }
    }

    return null;
  }

  HInstruction findDominator(Iterable<HInstruction> instructions) {
    HInstruction result;
    L1:
    for (HInstruction candidate in instructions) {
      for (HInstruction current in instructions) {
        if (current != candidate && !candidate.dominates(current)) continue L1;
      }
      result = candidate;
      break;
    }
    return result;
  }

  static int useCount(HInstruction user, HInstruction used) =>
      user.inputs.where((input) => input == used).length;

  bool visitInterceptor(HInterceptor node) {
    if (node.receiver.nonCheck() == _graph.explicitReceiverParameter) {
      // If `explicitReceiverParameter` is set it means the current method is an
      // interceptor method, and `this` is the interceptor.  The caller just did
      // `getInterceptor(foo).currentMethod(foo)` to enter the current method.
      node.block.rewrite(node, _graph.thisInstruction);
      return true;
    }

    rewriteSelfInterceptorUses(node);

    if (node.usedBy.isEmpty) return true;

    // Specialize the interceptor with set of classes it intercepts, considering
    // all uses.  (The specialized interceptor has a shorter dispatch chain).
    // This operation applies only where the interceptor is used to dispatch a
    // method.  Other uses, e.g. as an ordinary argument or a HIs check use the
    // most general interceptor.
    //
    // TODO(sra): Take into account the receiver type at each call.  e.g:
    //
    //     (a) => a.length + a.hashCode
    //
    // Currently we use the most general interceptor since all intercepted types
    // implement `hashCode`. But in this example, `a.hashCode` is only reached
    // if `a.length` succeeds, which is indicated by the hashCode receiver being
    // a HTypeKnown instruction.

    Set<ClassEntity> interceptedClasses;
    HInstruction dominator = findDominator(node.usedBy);
    // If there is a call that dominates all other uses, we can use just the
    // selector of that instruction.
    if (dominator is HInvokeDynamic &&
        dominator.isCallOnInterceptor(_closedWorld) &&
        node == dominator.receiver &&
        useCount(dominator, node) == 1) {
      interceptedClasses = _interceptorData.getInterceptedClassesOn(
          dominator.selector.name, _closedWorld);

      // If we found that we need number, we must still go through all
      // uses to check if they require int, or double.
      if (interceptedClasses.contains(_commonElements.jsNumberClass) &&
          !(interceptedClasses.contains(_commonElements.jsDoubleClass) ||
              interceptedClasses.contains(_commonElements.jsIntClass))) {
        Set<ClassEntity> required;
        for (HInstruction user in node.usedBy) {
          if (user is! HInvoke) continue;
          Set<ClassEntity> intercepted = _interceptorData
              .getInterceptedClassesOn(user.selector.name, _closedWorld);
          if (intercepted.contains(_commonElements.jsIntClass)) {
            // TODO(johnniwinther): Use type argument when all uses of
            // intercepted classes expect entities instead of elements.
            required ??= new Set<ClassEntity>();
            required.add(_commonElements.jsIntClass);
          }
          if (intercepted.contains(_commonElements.jsDoubleClass)) {
            // TODO(johnniwinther): Use type argument when all uses of
            // intercepted classes expect entities instead of elements.
            required ??= new Set<ClassEntity>();
            required.add(_commonElements.jsDoubleClass);
          }
        }
        // Don't modify the result of
        // [_interceptorData.getInterceptedClassesOn].
        if (required != null) {
          interceptedClasses = interceptedClasses.union(required);
        }
      }
    } else {
      // TODO(johnniwinther): Use type argument when all uses of intercepted
      // classes expect entities instead of elements.
      interceptedClasses = new Set<ClassEntity>();
      for (HInstruction user in node.usedBy) {
        if (user is HInvokeDynamic &&
            user.isCallOnInterceptor(_closedWorld) &&
            node == user.receiver &&
            useCount(user, node) == 1) {
          interceptedClasses.addAll(_interceptorData.getInterceptedClassesOn(
              user.selector.name, _closedWorld));
        } else if (user is HInvokeSuper &&
            user.isCallOnInterceptor(_closedWorld) &&
            node == user.receiver &&
            useCount(user, node) == 1) {
          interceptedClasses.addAll(_interceptorData.getInterceptedClassesOn(
              user.selector.name, _closedWorld));
        } else {
          // Use a most general interceptor for other instructions, example,
          // is-checks and escaping interceptors.
          interceptedClasses.addAll(_interceptorData.interceptedClasses);
          break;
        }
      }
    }

    node.interceptedClasses = interceptedClasses;

    HInstruction receiver = node.receiver;

    // Try computing a constant interceptor.
    HInstruction constantInterceptor =
        tryComputeConstantInterceptor(receiver, interceptedClasses);
    if (constantInterceptor != null) {
      node.block.rewrite(node, constantInterceptor);
      return false;
    }

    // If it is a conditional constant interceptor and was not strengthened to a
    // constant interceptor then there is nothing more we can do.
    if (node.isConditionalConstantInterceptor) return false;

    // Do we have an 'almost constant' interceptor?  The receiver could be
    // `null` but not any other JavaScript falsy value, `null` values cause
    // `NoSuchMethodError`s, and if the receiver was not null we would have a
    // constant interceptor `C`.  Then we can use `(receiver && C)` for the
    // interceptor.
    if (receiver.canBeNull(_abstractValueDomain)) {
      if (!interceptedClasses.contains(_commonElements.jsNullClass)) {
        // Can use `(receiver && C)` only if receiver is either null or truthy.
        if (!(receiver.canBePrimitiveNumber(_abstractValueDomain) ||
            receiver.canBePrimitiveBoolean(_abstractValueDomain) ||
            receiver.canBePrimitiveString(_abstractValueDomain))) {
          ClassEntity interceptorClass = tryComputeConstantInterceptorFromType(
              _abstractValueDomain.excludeNull(receiver.instructionType),
              interceptedClasses);
          if (interceptorClass != null) {
            HInstruction constantInstruction = _graph.addConstant(
                new InterceptorConstantValue(interceptorClass), _closedWorld);
            node.conditionalConstantInterceptor = constantInstruction;
            constantInstruction.usedBy.add(node);
            return false;
          }
        }
      }
    }

    // Try creating a one-shot interceptor or optimized is-check
    if (node.usedBy.length != 1) return false;
    HInstruction user = node.usedBy.single;

    // If the interceptor [node] was loop hoisted, we keep the interceptor.
    if (!user.hasSameLoopHeaderAs(node)) return false;

    bool replaceUserWith(HInstruction replacement) {
      HBasicBlock block = user.block;
      block.addAfter(user, replacement);
      block.rewrite(user, replacement);
      block.remove(user);
      return false;
    }

    if (user is HIs) {
      // See if we can rewrite the is-check to use 'instanceof', i.e. rewrite
      // "getInterceptor(x).$isT" to "x instanceof T".
      if (node == user.interceptor) {
        if (_interceptorData.mayGenerateInstanceofCheck(
            user.typeExpression, _closedWorld)) {
          HInstruction instanceofCheck = new HIs.instanceOf(user.typeExpression,
              user.expression, user.instructionType, user.sourceInformation);
          instanceofCheck.sourceElement = user.sourceElement;
          return replaceUserWith(instanceofCheck);
        }
      }
    } else if (user is HInvokeDynamic) {
      if (node == user.inputs[0]) {
        // Replace the user with a [HOneShotInterceptor].
        HConstant nullConstant = _graph.addConstantNull(_closedWorld);
        List<HInstruction> inputs = new List<HInstruction>.from(user.inputs);
        inputs[0] = nullConstant;
        HOneShotInterceptor oneShotInterceptor = new HOneShotInterceptor(
            _abstractValueDomain,
            user.selector,
            user.mask,
            inputs,
            user.instructionType,
            user.typeArguments,
            interceptedClasses);
        oneShotInterceptor.sourceInformation = user.sourceInformation;
        oneShotInterceptor.sourceElement = user.sourceElement;
        return replaceUserWith(oneShotInterceptor);
      }
    }

    return false;
  }

  void rewriteSelfInterceptorUses(HInterceptor node) {
    HInstruction receiver = node.receiver;

    // At instructions that use the interceptor and its receiver, the receiver
    // might be refined at the use site.

    //     dynamic x = ...
    //     if (x is Mumble) {
    //       print(x.length);  // Self-interceptor here.
    //     } else {
    //       print(x.length);  //
    //     }

    finishInvoke(HInvoke invoke, Selector selector) {
      HInstruction callReceiver = invoke.getDartReceiver(_closedWorld);
      if (receiver.nonCheck() == callReceiver.nonCheck()) {
        Set<ClassEntity> interceptedClasses = _interceptorData
            .getInterceptedClassesOn(selector.name, _closedWorld);

        if (canUseSelfForInterceptor(callReceiver,
            interceptedClasses: interceptedClasses)) {
          invoke.changeUse(node, callReceiver);
        }
      }
    }

    for (HInstruction user in node.usedBy.toList()) {
      if (user is HIs) {
        if (user.interceptor == node) {
          HInstruction expression = user.expression;
          if (canUseSelfForInterceptor(expression)) {
            user.changeUse(node, expression);
          }
        }
      } else if (user is HInvokeDynamic) {
        if (user.isCallOnInterceptor(_closedWorld) &&
            node == user.inputs[0] &&
            useCount(user, node) == 1) {
          finishInvoke(user, user.selector);
        }
      } else if (user is HInvokeSuper) {
        if (user.isCallOnInterceptor(_closedWorld) &&
            node == user.inputs[0] &&
            useCount(user, node) == 1) {
          finishInvoke(user, user.selector);
        }
      } else {
        // TODO(sra): Are there other paired uses of the receiver and
        // interceptor where we can make use of a strengthened receiver?
      }
    }
  }

  bool visitOneShotInterceptor(HOneShotInterceptor node) {
    // 'Undo' the one-shot transformation if the receiver has a constant
    // interceptor.
    HInstruction constant =
        tryComputeConstantInterceptor(node.inputs[1], node.interceptedClasses);

    if (constant == null) return false;

    Selector selector = node.selector;
    AbstractValue mask = node.mask;
    HInstruction instruction;
    if (selector.isGetter) {
      instruction = new HInvokeDynamicGetter(
          selector,
          mask,
          node.element,
          <HInstruction>[constant, node.inputs[1]],
          true,
          node.instructionType,
          node.sourceInformation);
    } else if (selector.isSetter) {
      instruction = new HInvokeDynamicSetter(
          selector,
          mask,
          node.element,
          <HInstruction>[constant, node.inputs[1], node.inputs[2]],
          true,
          node.instructionType,
          node.sourceInformation);
    } else {
      List<HInstruction> inputs = new List<HInstruction>.from(node.inputs);
      inputs[0] = constant;
      instruction = new HInvokeDynamicMethod(selector, mask, inputs,
          node.instructionType, node.typeArguments, node.sourceInformation,
          isIntercepted: true);
    }

    HBasicBlock block = node.block;
    block.addAfter(node, instruction);
    block.rewrite(node, instruction);
    return true;
  }
}