// Copyright (c) 2012, 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 universe;

import '../elements/elements.dart';
import '../dart2jslib.dart';
import '../dart_types.dart';
import '../types/types.dart';
import '../tree/tree.dart';
import '../util/util.dart';

part 'function_set.dart';
part 'side_effects.dart';

class Universe {
  /**
   * Documentation wanted -- johnniwinther
   *
   * Invariant: Elements are declaration elements.
   */
  // TODO(karlklose): these sets should be merged.
  final Set<ClassElement> instantiatedClasses = new Set<ClassElement>();
  final Set<DartType> instantiatedTypes = new Set<DartType>();

  /**
   * Documentation wanted -- johnniwinther
   *
   * Invariant: Elements are declaration elements.
   */
  final Set<FunctionElement> staticFunctionsNeedingGetter =
      new Set<FunctionElement>();
  final Map<String, Set<Selector>> invokedNames =
      new Map<String, Set<Selector>>();
  final Map<String, Set<Selector>> invokedGetters =
      new Map<String, Set<Selector>>();
  final Map<String, Set<Selector>> invokedSetters =
      new Map<String, Set<Selector>>();

  /**
   * Fields accessed. Currently only the codegen knows this
   * information. The resolver is too conservative when seeing a
   * getter and only registers an invoked getter.
   */
  final Set<Element> fieldGetters = new Set<Element>();

  /**
   * Fields set. See comment in [fieldGetters].
   */
  final Set<Element> fieldSetters = new Set<Element>();
  final Set<DartType> isChecks = new Set<DartType>();

  /**
   * Set of [:call:] methods in instantiated classes that use type variables
   * in their signature.
   */
  final Set<Element> genericCallMethods = new Set<Element>();

  /**
   * Set of closures that use type variables in their signature.
   */
  final Set<Element> genericClosures = new Set<Element>();

  /**
   * Set of methods in instantiated classes that are potentially
   * closurized.
   */
  final Set<Element> closurizedMembers = new Set<Element>();

  bool usingFactoryWithTypeArguments = false;

  bool hasMatchingSelector(Set<Selector> selectors,
                           Element member,
                           Compiler compiler) {
    if (selectors == null) return false;
    for (Selector selector in selectors) {
      if (selector.appliesUnnamed(member, compiler)) return true;
    }
    return false;
  }

  bool hasInvocation(Element member, Compiler compiler) {
    return hasMatchingSelector(invokedNames[member.name], member, compiler);
  }

  bool hasInvokedGetter(Element member, Compiler compiler) {
    return hasMatchingSelector(invokedGetters[member.name], member, compiler);
  }

  bool hasInvokedSetter(Element member, Compiler compiler) {
    return hasMatchingSelector(invokedSetters[member.name], member, compiler);
  }

  bool hasFieldGetter(Element member, Compiler compiler) {
    return fieldGetters.contains(member);
  }

  bool hasFieldSetter(Element member, Compiler compiler) {
    return fieldSetters.contains(member);
  }

  DartType registerIsCheck(DartType type, Compiler compiler) {
    type = type.unalias(compiler);
    // Even in checked mode, type annotations for return type and argument
    // types do not imply type checks, so there should never be a check
    // against the type variable of a typedef.
    isChecks.add(type);
    return type;
  }
}

class SelectorKind {
  final String name;
  final int hashCode;
  const SelectorKind(this.name, this.hashCode);

  static const SelectorKind GETTER = const SelectorKind('getter', 0);
  static const SelectorKind SETTER = const SelectorKind('setter', 1);
  static const SelectorKind CALL = const SelectorKind('call', 2);
  static const SelectorKind OPERATOR = const SelectorKind('operator', 3);
  static const SelectorKind INDEX = const SelectorKind('index', 4);

  String toString() => name;
}

class Selector {
  final SelectorKind kind;
  final String name;
  final LibraryElement library; // Library is null for non-private selectors.

  // The numbers of arguments of the selector. Includes named arguments.
  final int argumentCount;
  final List<String> namedArguments;
  final List<String> orderedNamedArguments;
  final int hashCode;

  static const String INDEX_NAME ="[]";
  static const String INDEX_SET_NAME = "[]=";
  static const String CALL_NAME = Compiler.CALL_OPERATOR_NAME;

  Selector.internal(this.kind,
                    this.name,
                    this.library,
                    this.argumentCount,
                    this.namedArguments,
                    this.orderedNamedArguments,
                    this.hashCode) {
    assert(kind == SelectorKind.INDEX
           || (name != INDEX_NAME && name != INDEX_SET_NAME));
    assert(kind == SelectorKind.OPERATOR
           || kind == SelectorKind.INDEX
           || Elements.operatorNameToIdentifier(name) == name);
    assert(kind == SelectorKind.CALL
           || kind == SelectorKind.GETTER
           || kind == SelectorKind.SETTER
           || Elements.operatorNameToIdentifier(name) != name);
    assert(!isPrivateName(name) || library != null);
  }

  static Map<int, List<Selector>> canonicalizedValues =
      new Map<int, List<Selector>>();

  factory Selector(SelectorKind kind,
                   String name,
                   LibraryElement library,
                   int argumentCount,
                   [List<String> namedArguments]) {
    if (!isPrivateName(name)) library = null;
    if (namedArguments == null) namedArguments = const <String>[];
    int hashCode = computeHashCode(
        kind, name, library, argumentCount, namedArguments);
    List<Selector> list = canonicalizedValues.putIfAbsent(hashCode,
        () => <Selector>[]);
    for (int i = 0; i < list.length; i++) {
      Selector existing = list[i];
      if (existing.match(kind, name, library, argumentCount, namedArguments)) {
        assert(existing.hashCode == hashCode);
        assert(existing.mask == null);
        return existing;
      }
    }
    List<String> orderedNamedArguments = namedArguments.isEmpty
        ? const <String>[]
        : <String>[];
    Selector result = new Selector.internal(
        kind, name, library, argumentCount,
        namedArguments, orderedNamedArguments,
        hashCode);
    list.add(result);
    return result;
  }

  factory Selector.fromElement(Element element, Compiler compiler) {
    String name = element.name;
    if (element.isFunction()) {
      int arity = element.asFunctionElement().requiredParameterCount(compiler);
      if (name == '[]') {
        return new Selector.index();
      } else if (name == '[]=') {
        return new Selector.indexSet();
      } else if (Elements.operatorNameToIdentifier(name) != name) {
        return new Selector(SelectorKind.OPERATOR, name, null, arity);
      } else {
        return new Selector.call(name, element.getLibrary(), arity);
      }
    } else if (element.isSetter()) {
      return new Selector.setter(name, element.getLibrary());
    } else if (element.isGetter()) {
      return new Selector.getter(name, element.getLibrary());
    } else if (element.isField()) {
      return new Selector.getter(name, element.getLibrary());
    }
  }

  factory Selector.getter(String name, LibraryElement library)
      => new Selector(SelectorKind.GETTER, name, library, 0);

  factory Selector.getterFrom(Selector selector)
      => new Selector(SelectorKind.GETTER, selector.name, selector.library, 0);

  factory Selector.setter(String name, LibraryElement library)
      => new Selector(SelectorKind.SETTER, name, library, 1);

  factory Selector.unaryOperator(String name)
      => new Selector(SelectorKind.OPERATOR,
                      Elements.constructOperatorName(name, true),
                      null, 0);

  factory Selector.binaryOperator(String name)
      => new Selector(SelectorKind.OPERATOR,
                      Elements.constructOperatorName(name, false),
                      null, 1);

  factory Selector.index()
      => new Selector(SelectorKind.INDEX,
                      Elements.constructOperatorName(INDEX_NAME, false),
                      null, 1);

  factory Selector.indexSet()
      => new Selector(SelectorKind.INDEX,
                      Elements.constructOperatorName(INDEX_SET_NAME, false),
                      null, 2);

  factory Selector.call(String name,
                        LibraryElement library,
                        int arity,
                        [List<String> namedArguments])
      => new Selector(SelectorKind.CALL, name, library, arity, namedArguments);

  factory Selector.callClosure(int arity, [List<String> namedArguments])
      => new Selector(SelectorKind.CALL, CALL_NAME, null,
                      arity, namedArguments);

  factory Selector.callClosureFrom(Selector selector)
      => new Selector(SelectorKind.CALL, CALL_NAME, null,
                      selector.argumentCount, selector.namedArguments);

  factory Selector.callConstructor(String name, LibraryElement library,
                                   [int arity = 0,
                                    List<String> namedArguments])
      => new Selector(SelectorKind.CALL, name, library,
                      arity, namedArguments);

  factory Selector.callDefaultConstructor(LibraryElement library)
      => new Selector(SelectorKind.CALL, "", library, 0);

  bool isGetter() => identical(kind, SelectorKind.GETTER);
  bool isSetter() => identical(kind, SelectorKind.SETTER);
  bool isCall() => identical(kind, SelectorKind.CALL);
  bool isClosureCall() {
    String callName = Compiler.CALL_OPERATOR_NAME;
    return isCall() && name == callName;
  }

  bool isIndex() => identical(kind, SelectorKind.INDEX) && argumentCount == 1;
  bool isIndexSet() => identical(kind, SelectorKind.INDEX) && argumentCount == 2;

  bool isOperator() => identical(kind, SelectorKind.OPERATOR);
  bool isUnaryOperator() => isOperator() && argumentCount == 0;
  bool isBinaryOperator() => isOperator() && argumentCount == 1;

  /** Check whether this is a call to 'assert'. */
  bool isAssert() => isCall() && identical(name, "assert");

  int get namedArgumentCount => namedArguments.length;
  int get positionalArgumentCount => argumentCount - namedArgumentCount;

  bool get hasExactMask => false;
  TypeMask get mask => null;
  Selector get asUntyped => this;

  /**
   * The member name for invocation mirrors created from this selector.
   */
  String get invocationMirrorMemberName =>
      isSetter() ? '$name=' : name;

  int get invocationMirrorKind {
    const int METHOD = 0;
    const int GETTER = 1;
    const int SETTER = 2;
    int kind = METHOD;
    if (isGetter()) {
      kind = GETTER;
    } else if (isSetter()) {
      kind = SETTER;
    }
    return kind;
  }

  bool appliesUnnamed(Element element, Compiler compiler) {
    assert(sameNameHack(element, compiler));
    return appliesUntyped(element, compiler);
  }

  bool appliesUntyped(Element element, Compiler compiler) {
    assert(sameNameHack(element, compiler));
    if (Elements.isUnresolved(element)) return false;
    if (isPrivateName(name) && library != element.getLibrary()) return false;
    if (element.isForeign(compiler)) return true;
    if (element.isSetter()) return isSetter();
    if (element.isGetter()) return isGetter() || isCall();
    if (element.isField()) {
      return isSetter()
          ? !element.modifiers.isFinalOrConst()
          : isGetter() || isCall();
    }
    if (isGetter()) return true;
    if (isSetter()) return false;

    FunctionElement function = element;
    FunctionSignature parameters = function.computeSignature(compiler);
    if (argumentCount > parameters.parameterCount) return false;
    int requiredParameterCount = parameters.requiredParameterCount;
    int optionalParameterCount = parameters.optionalParameterCount;
    if (positionalArgumentCount < requiredParameterCount) return false;

    if (!parameters.optionalParametersAreNamed) {
      // We have already checked that the number of arguments are
      // not greater than the number of parameters. Therefore the
      // number of positional arguments are not greater than the
      // number of parameters.
      assert(positionalArgumentCount <= parameters.parameterCount);
      return namedArguments.isEmpty;
    } else {
      if (positionalArgumentCount > requiredParameterCount) return false;
      assert(positionalArgumentCount == requiredParameterCount);
      if (namedArgumentCount > optionalParameterCount) return false;
      Set<String> nameSet = new Set<String>();
      parameters.optionalParameters.forEach((Element element) {
        nameSet.add(element.name);
      });
      for (String name in namedArguments) {
        if (!nameSet.contains(name)) return false;
        // TODO(5213): By removing from the set we are checking
        // that we are not passing the name twice. We should have this
        // check in the resolver also.
        nameSet.remove(name);
      }
      return true;
    }
  }

  bool sameNameHack(Element element, Compiler compiler) {
    // TODO(ngeoffray): Remove workaround checks.
    return element == compiler.assertMethod
        || element.isConstructor()
        || name == element.name;
  }

  bool applies(Element element, Compiler compiler) {
    if (!sameNameHack(element, compiler)) return false;
    return appliesUnnamed(element, compiler);
  }

  /**
   * Fills [list] with the arguments in a defined order.
   *
   * [compileArgument] is a function that returns a compiled version
   * of an argument located in [arguments].
   *
   * [compileConstant] is a function that returns a compiled constant
   * of an optional argument that is not in [arguments].
   *
   * Returns [:true:] if the selector and the [element] match; [:false:]
   * otherwise.
   *
   * Invariant: [element] must be the implementation element.
   */
  bool addArgumentsToList(Link<Node> arguments,
                          List list,
                          FunctionElement element,
                          compileArgument(Node argument),
                          compileConstant(Element element),
                          Compiler compiler) {
    assert(invariant(element, element.isImplementation));
    if (!this.applies(element, compiler)) return false;

    FunctionSignature parameters = element.computeSignature(compiler);
    parameters.forEachRequiredParameter((element) {
      list.add(compileArgument(arguments.head));
      arguments = arguments.tail;
    });

    if (!parameters.optionalParametersAreNamed) {
      parameters.forEachOptionalParameter((element) {
        if (!arguments.isEmpty) {
          list.add(compileArgument(arguments.head));
          arguments = arguments.tail;
        } else {
          list.add(compileConstant(element));
        }
      });
    } else {
      // Visit named arguments and add them into a temporary list.
      List compiledNamedArguments = [];
      for (; !arguments.isEmpty; arguments = arguments.tail) {
        NamedArgument namedArgument = arguments.head;
        compiledNamedArguments.add(compileArgument(namedArgument.expression));
      }
      // Iterate over the optional parameters of the signature, and try to
      // find them in [compiledNamedArguments]. If found, we use the
      // value in the temporary list, otherwise the default value.
      parameters.orderedOptionalParameters.forEach((element) {
        int foundIndex = namedArguments.indexOf(element.name);
        if (foundIndex != -1) {
          list.add(compiledNamedArguments[foundIndex]);
        } else {
          list.add(compileConstant(element));
        }
      });
    }
    return true;
  }

  /**
   * Fills [list] with the arguments in the order expected by
   * [callee], and where [caller] is a synthesized element
   *
   * [compileArgument] is a function that returns a compiled version
   * of a parameter of [callee].
   *
   * [compileConstant] is a function that returns a compiled constant
   * of an optional argument that is not in the parameters of [callee].
   *
   * Returns [:true:] if the signature of the [caller] matches the
   * signature of the [callee], [:false:] otherwise.
   */
  static bool addForwardingElementArgumentsToList(
      FunctionElement caller,
      List list,
      FunctionElement callee,
      compileArgument(Element element),
      compileConstant(Element element),
      Compiler compiler) {

    FunctionSignature signature = caller.computeSignature(compiler);
    Map mapping = new Map();

    // TODO(ngeoffray): This is a hack that fakes up AST nodes, so
    // that we can call [addArgumentsToList].
    Link computeCallNodesFromParameters() {
      LinkBuilder builder = new LinkBuilder();
      signature.forEachRequiredParameter((Element element) {
        Node node = element.parseNode(compiler);
        mapping[node] = element;
        builder.addLast(node);
      });
      if (signature.optionalParametersAreNamed) {
        signature.forEachOptionalParameter((Element element) {
          Node node = element.parseNode(compiler);
          mapping[node] = element;
          builder.addLast(new NamedArgument(null, null, node));
        });
      } else {
        signature.forEachOptionalParameter((Element element) {
          Node node = element.parseNode(compiler);
          mapping[node] = element;
          builder.addLast(node);
        });
      }
      return builder.toLink();
    }

    internalCompileArgument(Node node) => compileArgument(mapping[node]);

    Link<Node> nodes = computeCallNodesFromParameters();

    // Synthesize a selector for the call.
    // TODO(ngeoffray): Should the resolver do it instead?
    List<String> namedParameters;
    if (signature.optionalParametersAreNamed) {
      namedParameters =
          signature.optionalParameters.toList().map((e) => e.name).toList();
    }
    Selector selector = new Selector.call(callee.name,
                                          caller.getLibrary(),
                                          signature.parameterCount,
                                          namedParameters);

    return selector.addArgumentsToList(nodes,
                                       list,
                                       callee,
                                       internalCompileArgument,
                                       compileConstant,
                                       compiler);
  }

  static bool sameNames(List<String> first, List<String> second) {
    for (int i = 0; i < first.length; i++) {
      if (first[i] != second[i]) return false;
    }
    return true;
  }

  bool match(SelectorKind kind,
             String name,
             LibraryElement library,
             int argumentCount,
             List<String> namedArguments) {
    return this.kind == kind
        && this.name == name
        && identical(this.library, library)
        && this.argumentCount == argumentCount
        && this.namedArguments.length == namedArguments.length
        && sameNames(this.namedArguments, namedArguments);
  }

  static int computeHashCode(SelectorKind kind,
                             String name,
                             LibraryElement library,
                             int argumentCount,
                             List<String> namedArguments) {
    // Add bits from name and kind.
    int hash = mixHashCodeBits(name.hashCode, kind.hashCode);
    // Add bits from the library.
    if (library != null) hash = mixHashCodeBits(hash, library.hashCode);
    // Add bits from the unnamed arguments.
    hash = mixHashCodeBits(hash, argumentCount);
    // Add bits from the named arguments.
    int named = namedArguments.length;
    hash = mixHashCodeBits(hash, named);
    for (int i = 0; i < named; i++) {
      hash = mixHashCodeBits(hash, namedArguments[i].hashCode);
    }
    return hash;
  }

  // TODO(kasperl): Move this out so it becomes useful in other places too?
  static int mixHashCodeBits(int existing, int value) {
    // Spread the bits of value. Try to stay in the 30-bit range to
    // avoid overflowing into a more expensive integer representation.
    int h = value & 0x1fffffff;
    h += ((h & 0x3fff) << 15) ^ 0x1fffcd7d;
    h ^= (h >> 10);
    h += ((h & 0x3ffffff) << 3);
    h ^= (h >> 6);
    h += ((h & 0x7ffffff) << 2) + ((h & 0x7fff) << 14);
    h ^= (h >> 16);
    // Combine the two hash values.
    int high = existing >> 15;
    int low = existing & 0x7fff;
    return (high * 13) ^ (low * 997) ^ h;
  }

  List<String> getOrderedNamedArguments() {
    if (namedArguments.isEmpty) return namedArguments;
    if (!orderedNamedArguments.isEmpty) return orderedNamedArguments;

    orderedNamedArguments.addAll(namedArguments);
    orderedNamedArguments.sort((String first, String second) {
      return first.compareTo(second);
    });
    return orderedNamedArguments;
  }

  String namedArgumentsToString() {
    if (namedArgumentCount > 0) {
      StringBuffer result = new StringBuffer();
      for (int i = 0; i < namedArgumentCount; i++) {
        if (i != 0) result.write(', ');
        result.write(namedArguments[i]);
      }
      return "[$result]";
    }
    return '';
  }

  String toString() {
    String named = '';
    String type = '';
    if (namedArgumentCount > 0) named = ', named=${namedArgumentsToString()}';
    if (mask != null) type = ', mask=$mask';
    return 'Selector($kind, $name, '
           'arity=$argumentCount$named$type)';
  }

  Selector extendIfReachesAll(Compiler compiler) {
    return new TypedSelector(compiler.typesTask.dynamicType, this);
  }
}

class TypedSelector extends Selector {
  final Selector asUntyped;
  final TypeMask mask;

  TypedSelector.internal(this.mask, Selector selector, int hashCode)
      : asUntyped = selector,
        super.internal(selector.kind,
                       selector.name,
                       selector.library,
                       selector.argumentCount,
                       selector.namedArguments,
                       selector.orderedNamedArguments,
                       hashCode) {
    assert(mask != null);
    assert(asUntyped.mask == null);
  }

  static Map<Selector, Map<TypeMask, TypedSelector>> canonicalizedValues =
      new Map<Selector, Map<TypeMask, TypedSelector>>();

  factory TypedSelector(TypeMask mask, Selector selector) {
    if (selector.mask == mask) return selector;
    Selector untyped = selector.asUntyped;
    Map<TypeMask, TypedSelector> map = canonicalizedValues.putIfAbsent(untyped,
        () => new Map<TypeMask, TypedSelector>());
    TypedSelector result = map[mask];
    if (result == null) {
      int hashCode = Selector.mixHashCodeBits(untyped.hashCode, mask.hashCode);
      result = map[mask] = new TypedSelector.internal(mask, untyped, hashCode);
    }
    return result;
  }

  factory TypedSelector.exact(ClassElement base, Selector selector)
      => new TypedSelector(new TypeMask.exact(base), selector);

  factory TypedSelector.subclass(ClassElement base, Selector selector)
      => new TypedSelector(new TypeMask.subclass(base), selector);

  factory TypedSelector.subtype(ClassElement base, Selector selector)
      => new TypedSelector(new TypeMask.subtype(base), selector);

  bool appliesUnnamed(Element element, Compiler compiler) {
    assert(sameNameHack(element, compiler));
    // [TypedSelector] are only used after resolution.
    assert(compiler.phase > Compiler.PHASE_RESOLVING);
    if (!element.isMember()) return false;

    // A closure can be called through any typed selector:
    // class A {
    //   get foo => () => 42;
    //   bar() => foo(); // The call to 'foo' is a typed selector.
    // }
    if (element.getEnclosingClass().isClosure()) {
      return appliesUntyped(element, compiler);
    }

    if (!mask.canHit(element, this, compiler)) return false;
    return appliesUntyped(element, compiler);
  }

  Selector extendIfReachesAll(Compiler compiler) {
    bool canReachAll = compiler.enabledInvokeOn
        && mask.needsNoSuchMethodHandling(this, compiler);
    return canReachAll
        ? new TypedSelector(compiler.typesTask.dynamicType, this)
        : this;
  }
}