Move Selector and CallStructure into parts.

pkg/compiler/lib/src/universe/selector.dart

-// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// Copyright (c) 2015, 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 'dart:collection';
-
-import '../common/names.dart' show
-    Identifiers,
-    Names,
-    Selectors;
-import '../compiler.dart' show
-    Compiler;
-import '../diagnostics/invariant.dart' show
-    invariant;
-import '../diagnostics/spannable.dart' show
-    SpannableAssertionFailure;
-import '../elements/elements.dart';
-import '../dart_types.dart';
-import '../tree/tree.dart';
-import '../types/types.dart';
-import '../util/util.dart';
-import '../world.dart' show
-    ClassWorld,
-    World;
-
-part 'function_set.dart';
-part 'side_effects.dart';
-
-class UniverseSelector {
-  final Selector selector;
-  final ReceiverMask mask;
-
-  UniverseSelector(this.selector, this.mask);
-
-  bool appliesUnnamed(Element element, ClassWorld world) {
-    return selector.appliesUnnamed(element, world) &&
-        (mask == null || mask.canHit(element, selector, world));
-  }
-
-  String toString() => '$selector,$mask';
-}
-
-/// A potential receiver for a dynamic call site.
-abstract class ReceiverMask {
-  /// Returns whether [element] is a potential target when being
-  /// invoked on this receiver mask. [selector] is used to ensure library
-  /// privacy is taken into account.
-  bool canHit(Element element, Selector selector, ClassWorld classWorld);
-}
-
-/// A set of potential receivers for the dynamic call sites of the same
-/// selector.
-///
-/// For instance for these calls
-///
-///     new A().foo(a, b);
-///     new B().foo(0, 42);
-///
-/// the receiver mask set for dynamic calls to 'foo' with to positional
-/// arguments will contain receiver masks abstracting `new A()` and `new B()`.
-abstract class ReceiverMaskSet {
-  /// Returns `true` if [selector] applies to any of the potential receivers
-  /// in this set given the closed [world].
-  bool applies(Element element, Selector selector, ClassWorld world);
-
-  /// Returns `true` if any potential receivers in this set given the closed
-  /// [world] have no implementation matching [selector].
-  ///
-  /// For instance for this code snippet
-  ///
-  ///     class A {}
-  ///     class B { foo() {} }
-  ///     m(b) => (b ? new A() : new B()).foo();
-  ///
-  /// the potential receiver `new A()` have no implementation of `foo` and thus
-  /// needs to handle the call though its `noSuchMethod` handler.
-  bool needsNoSuchMethodHandling(Selector selector, ClassWorld world);
-}
-
-/// A mutable [ReceiverMaskSet] used in [Universe].
-abstract class UniverseReceiverMaskSet extends ReceiverMaskSet {
-  /// Adds [mask] to this set of potential receivers. Return `true` if the
-  /// set expanded due to the new mask.
-  bool addReceiverMask(ReceiverMask mask);
-}
-
-/// Strategy for computing potential receivers of dynamic call sites.
-abstract class ReceiverMaskStrategy {
-  /// Create a [UniverseReceiverMaskSet] to represent the potential receiver for
-  /// a dynamic call site with [selector].
-  UniverseReceiverMaskSet createReceiverMaskSet(Selector selector);
-}
-
-class Universe {
-  /// The set of all directly instantiated classes, that is, classes with a
-  /// generative constructor that has been called directly and not only through
-  /// a super-call.
-  ///
-  /// Invariant: Elements are declaration elements.
-  // TODO(johnniwinther): [_directlyInstantiatedClasses] and
-  // [_instantiatedTypes] sets should be merged.
-  final Set<ClassElement> _directlyInstantiatedClasses =
-      new Set<ClassElement>();
-
-  /// The set of all directly instantiated types, that is, the types of the
-  /// directly instantiated classes.
-  ///
-  /// See [_directlyInstantiatedClasses].
-  final Set<DartType> _instantiatedTypes = new Set<DartType>();
-
-  /// The set of all instantiated classes, either directly, as superclasses or
-  /// as supertypes.
-  ///
-  /// Invariant: Elements are declaration elements.
-  final Set<ClassElement> _allInstantiatedClasses = new Set<ClassElement>();
-
-  /// The set of all referenced static fields.
-  ///
-  /// Invariant: Elements are declaration elements.
-  final Set<FieldElement> allReferencedStaticFields = new Set<FieldElement>();
-
-  /**
-   * Documentation wanted -- johnniwinther
-   *
-   * Invariant: Elements are declaration elements.
-   */
-  final Set<FunctionElement> staticFunctionsNeedingGetter =
-      new Set<FunctionElement>();
-  final Set<FunctionElement> methodsNeedingSuperGetter =
-      new Set<FunctionElement>();
-  final Map<String, Map<Selector, ReceiverMaskSet>> _invokedNames =
-      <String, Map<Selector, ReceiverMaskSet>>{};
-  final Map<String, Map<Selector, ReceiverMaskSet>> _invokedGetters =
-      <String, Map<Selector, ReceiverMaskSet>>{};
-  final Map<String, Map<Selector, ReceiverMaskSet>> _invokedSetters =
-      <String, Map<Selector, ReceiverMaskSet>>{};
-
-  /**
-   * 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 (live) [:call:] methods whose signatures reference type variables.
-   *
-   * A live [:call:] method is one whose enclosing class has been instantiated.
-   */
-  final Set<Element> callMethodsWithFreeTypeVariables = new Set<Element>();
-
-  /**
-   * Set of (live) local functions (closures) whose signatures reference type
-   * variables.
-   *
-   * A live function is one whose enclosing member function has been enqueued.
-   */
-  final Set<Element> closuresWithFreeTypeVariables = new Set<Element>();
-
-  /**
-   * Set of all closures in the program. Used by the mirror tracking system
-   * to find all live closure instances.
-   */
-  final Set<LocalFunctionElement> allClosures = new Set<LocalFunctionElement>();
-
-  /**
-   * Set of methods in instantiated classes that are potentially
-   * closurized.
-   */
-  final Set<Element> closurizedMembers = new Set<Element>();
-
-  final ReceiverMaskStrategy receiverMaskStrategy;
-
-  Universe(this.receiverMaskStrategy);
-
-  /// All directly instantiated classes, that is, classes with a generative
-  /// constructor that has been called directly and not only through a
-  /// super-call.
-  // TODO(johnniwinther): Improve semantic precision.
-  Iterable<ClassElement> get directlyInstantiatedClasses {
-    return _directlyInstantiatedClasses;
-  }
-
-  /// All instantiated classes, either directly, as superclasses or as
-  /// supertypes.
-  // TODO(johnniwinther): Improve semantic precision.
-  Iterable<ClassElement> get allInstantiatedClasses {
-    return _allInstantiatedClasses;
-  }
-
-  /// All directly instantiated types, that is, the types of the directly
-  /// instantiated classes.
-  ///
-  /// See [directlyInstantiatedClasses].
-  // TODO(johnniwinther): Improve semantic precision.
-  Iterable<DartType> get instantiatedTypes => _instantiatedTypes;
-
-  /// Returns `true` if [cls] is considered to be instantiated, either directly,
-  /// through subclasses or through subtypes. The latter case only contains
-  /// spurious information from instatiations through factory constructors and
-  /// mixins.
-  // TODO(johnniwinther): Improve semantic precision.
-  bool isInstantiated(ClassElement cls) {
-    return _allInstantiatedClasses.contains(cls);
-  }
-
-  /// Register [type] as (directly) instantiated.
-  ///
-  /// If [byMirrors] is `true`, the instantiation is through mirrors.
-  // TODO(johnniwinther): Fully enforce the separation between exact, through
-  // subclass and through subtype instantiated types/classes.
-  // TODO(johnniwinther): Support unknown type arguments for generic types.
-  void registerTypeInstantiation(InterfaceType type,
-                                 {bool byMirrors: false}) {
-    _instantiatedTypes.add(type);
-    ClassElement cls = type.element;
-    if (!cls.isAbstract
-        // We can't use the closed-world assumption with native abstract
-        // classes; a native abstract class may have non-abstract subclasses
-        // not declared to the program.  Instances of these classes are
-        // indistinguishable from the abstract class.
-        || cls.isNative
-        // Likewise, if this registration comes from the mirror system,
-        // all bets are off.
-        // TODO(herhut): Track classes required by mirrors seperately.
-        || byMirrors) {
-      _directlyInstantiatedClasses.add(cls);
-    }
-
-    // TODO(johnniwinther): Replace this by separate more specific mappings.
-    if (!_allInstantiatedClasses.add(cls)) return;
-    cls.allSupertypes.forEach((InterfaceType supertype) {
-      _allInstantiatedClasses.add(supertype.element);
-    });
-  }
-
-  bool _hasMatchingSelector(Map<Selector, ReceiverMaskSet> selectors,
-                            Element member,
-                            World world) {
-    if (selectors == null) return false;
-    for (Selector selector in selectors.keys) {
-      if (selector.appliesUnnamed(member, world)) {
-        ReceiverMaskSet masks = selectors[selector];
-        if (masks.applies(member, selector, world)) {
-          return true;
-        }
-      }
-    }
-    return false;
-  }
-
-  bool hasInvocation(Element member, World world) {
-    return _hasMatchingSelector(_invokedNames[member.name], member, world);
-  }
-
-  bool hasInvokedGetter(Element member, World world) {
-    return _hasMatchingSelector(_invokedGetters[member.name], member, world);
-  }
-
-  bool hasInvokedSetter(Element member, World world) {
-    return _hasMatchingSelector(_invokedSetters[member.name], member, world);
-  }
-
-  bool registerInvocation(UniverseSelector selector) {
-    return _registerNewSelector(selector, _invokedNames);
-  }
-
-  bool registerInvokedGetter(UniverseSelector selector) {
-    return _registerNewSelector(selector, _invokedGetters);
-  }
-
-  bool registerInvokedSetter(UniverseSelector selector) {
-    return _registerNewSelector(selector, _invokedSetters);
-  }
-
-  bool _registerNewSelector(
-      UniverseSelector universeSelector,
-      Map<String, Map<Selector, ReceiverMaskSet>> selectorMap) {
-    Selector selector = universeSelector.selector;
-    String name = selector.name;
-    ReceiverMask mask = universeSelector.mask;
-    Map<Selector, ReceiverMaskSet> selectors = selectorMap.putIfAbsent(
-        name, () => new Maplet<Selector, ReceiverMaskSet>());
-    UniverseReceiverMaskSet masks = selectors.putIfAbsent(
-        selector, () => receiverMaskStrategy.createReceiverMaskSet(selector));
-    return masks.addReceiverMask(mask);
-  }
-
-  Map<Selector, ReceiverMaskSet> _asUnmodifiable(
-      Map<Selector, ReceiverMaskSet> map) {
-    if (map == null) return null;
-    return new UnmodifiableMapView(map);
-  }
-
-  Map<Selector, ReceiverMaskSet> invocationsByName(String name) {
-    return _asUnmodifiable(_invokedNames[name]);
-  }
-
-  Map<Selector, ReceiverMaskSet> getterInvocationsByName(String name) {
-    return _asUnmodifiable(_invokedGetters[name]);
-  }
-
-  Map<Selector, ReceiverMaskSet> setterInvocationsByName(String name) {
-    return _asUnmodifiable(_invokedSetters[name]);
-  }
-
-  void forEachInvokedName(
-      f(String name, Map<Selector, ReceiverMaskSet> selectors)) {
-    _invokedNames.forEach(f);
-  }
-
-  void forEachInvokedGetter(
-      f(String name, Map<Selector, ReceiverMaskSet> selectors)) {
-    _invokedGetters.forEach(f);
-  }
-
-  void forEachInvokedSetter(
-      f(String name, Map<Selector, ReceiverMaskSet> selectors)) {
-    _invokedSetters.forEach(f);
-  }
-
-  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;
-  }
-
-  void registerStaticFieldUse(FieldElement staticField) {
-    assert(Elements.isStaticOrTopLevel(staticField) && staticField.isField);
-    assert(staticField.isDeclaration);
-
-    allReferencedStaticFields.add(staticField);
-  }
-
-  void forgetElement(Element element, Compiler compiler) {
-    allClosures.remove(element);
-    slowDirectlyNestedClosures(element).forEach(compiler.forgetElement);
-    closurizedMembers.remove(element);
-    fieldSetters.remove(element);
-    fieldGetters.remove(element);
-    _directlyInstantiatedClasses.remove(element);
-    _allInstantiatedClasses.remove(element);
-    if (element is ClassElement) {
-      assert(invariant(
-          element, element.thisType.isRaw,
-          message: 'Generic classes not supported (${element.thisType}).'));
-      _instantiatedTypes
-          ..remove(element.rawType)
-          ..remove(element.thisType);
-    }
-  }
-
-  // TODO(ahe): Replace this method with something that is O(1), for example,
-  // by using a map.
-  List<LocalFunctionElement> slowDirectlyNestedClosures(Element element) {
-    // Return new list to guard against concurrent modifications.
-    return new List<LocalFunctionElement>.from(
-        allClosures.where((LocalFunctionElement closure) {
-          return closure.executableContext == element;
-        }));
-  }
-}
+part of universe;
 
 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;
 }
 
-/// The structure of the arguments at a call-site.
-// TODO(johnniwinther): Should these be cached?
-// TODO(johnniwinther): Should isGetter/isSetter be part of the call structure
-// instead of the selector?
-class CallStructure {
-  static const CallStructure NO_ARGS = const CallStructure.unnamed(0);
-  static const CallStructure ONE_ARG = const CallStructure.unnamed(1);
-  static const CallStructure TWO_ARGS = const CallStructure.unnamed(2);
-
-  /// The numbers of arguments of the call. Includes named arguments.
-  final int argumentCount;
-
-  /// The number of named arguments of the call.
-  int get namedArgumentCount => 0;
-
-  /// The number of positional argument of the call.
-  int get positionalArgumentCount => argumentCount;
-
-  const CallStructure.unnamed(this.argumentCount);
-
-  factory CallStructure(int argumentCount, [List<String> namedArguments]) {
-    if (namedArguments == null || namedArguments.isEmpty) {
-      return new CallStructure.unnamed(argumentCount);
-    }
-    return new NamedCallStructure(argumentCount, namedArguments);
-  }
-
-  /// `true` if this call has named arguments.
-  bool get isNamed => false;
-
-  /// `true` if this call has no named arguments.
-  bool get isUnnamed => true;
-
-  /// The names of the named arguments in call-site order.
-  List<String> get namedArguments => const <String>[];
-
-  /// The names of the named arguments in canonicalized order.
-  List<String> getOrderedNamedArguments() => const <String>[];
-
-  /// A description of the argument structure.
-  String structureToString() => 'arity=$argumentCount';
-
-  String toString() => 'CallStructure(${structureToString()})';
-
-  Selector get callSelector {
-    return new Selector(SelectorKind.CALL, Selector.CALL_NAME, this);
-  }
-
-  bool match(CallStructure other) {
-    if (identical(this, other)) return true;
-    return this.argumentCount == other.argumentCount
-        && this.namedArgumentCount == other.namedArgumentCount
-        && sameNames(this.namedArguments, other.namedArguments);
-  }
-
-  // TODO(johnniwinther): Cache hash code?
-  int get hashCode {
-    return Hashing.listHash(namedArguments,
-        Hashing.objectHash(argumentCount, namedArguments.length));
-  }
-
-  bool operator ==(other) {
-    if (other is! CallStructure) return false;
-    return match(other);
-  }
-
-  bool signatureApplies(FunctionSignature parameters) {
-    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;
-    }
-  }
-
-  /**
-   * Returns a `List` with the evaluated arguments in the normalized order.
-   *
-   * [compileDefaultValue] is a function that returns a compiled constant
-   * of an optional argument that is not in [compiledArguments].
-   *
-   * Precondition: `this.applies(element, world)`.
-   *
-   * Invariant: [element] must be the implementation element.
-   */
-  /*<T>*/ List/*<T>*/ makeArgumentsList(
-      Link<Node> arguments,
-      FunctionElement element,
-      /*T*/ compileArgument(Node argument),
-      /*T*/ compileDefaultValue(ParameterElement element)) {
-    assert(invariant(element, element.isImplementation));
-    List/*<T>*/ result = new List();
-
-    FunctionSignature parameters = element.functionSignature;
-    parameters.forEachRequiredParameter((ParameterElement element) {
-      result.add(compileArgument(arguments.head));
-      arguments = arguments.tail;
-    });
-
-    if (!parameters.optionalParametersAreNamed) {
-      parameters.forEachOptionalParameter((ParameterElement element) {
-        if (!arguments.isEmpty) {
-          result.add(compileArgument(arguments.head));
-          arguments = arguments.tail;
-        } else {
-          result.add(compileDefaultValue(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((ParameterElement element) {
-        int foundIndex = namedArguments.indexOf(element.name);
-        if (foundIndex != -1) {
-          result.add(compiledNamedArguments[foundIndex]);
-        } else {
-          result.add(compileDefaultValue(element));
-        }
-      });
-    }
-    return result;
-  }
-
-  /**
-   * 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 /*<T>*/ bool addForwardingElementArgumentsToList(
-      ConstructorElement caller,
-      List/*<T>*/ list,
-      ConstructorElement callee,
-      /*T*/ compileArgument(ParameterElement element),
-      /*T*/ compileConstant(ParameterElement element)) {
-    assert(invariant(caller, !callee.isErroneous,
-        message: "Cannot compute arguments to erroneous constructor: "
-                 "$caller calling $callee."));
-
-    FunctionSignature signature = caller.functionSignature;
-    Map<Node, ParameterElement> mapping = <Node, ParameterElement>{};
-
-    // TODO(ngeoffray): This is a hack that fakes up AST nodes, so
-    // that we can call [addArgumentsToList].
-    Link<Node> computeCallNodesFromParameters() {
-      LinkBuilder<Node> builder = new LinkBuilder<Node>();
-      signature.forEachRequiredParameter((ParameterElement element) {
-        Node node = element.node;
-        mapping[node] = element;
-        builder.addLast(node);
-      });
-      if (signature.optionalParametersAreNamed) {
-        signature.forEachOptionalParameter((ParameterElement element) {
-          mapping[element.initializer] = element;
-          builder.addLast(new NamedArgument(null, null, element.initializer));
-        });
-      } else {
-        signature.forEachOptionalParameter((ParameterElement element) {
-          Node node = element.node;
-          mapping[node] = element;
-          builder.addLast(node);
-        });
-      }
-      return builder.toLink();
-    }
-
-    /*T*/ internalCompileArgument(Node node) {
-      return compileArgument(mapping[node]);
-    }
-
-    Link<Node> nodes = computeCallNodesFromParameters();
-
-    // Synthesize a structure for the call.
-    // TODO(ngeoffray): Should the resolver do it instead?
-    List<String> namedParameters;
-    if (signature.optionalParametersAreNamed) {
-      namedParameters =
-          signature.optionalParameters.map((e) => e.name).toList();
-    }
-    CallStructure callStructure =
-        new CallStructure(signature.parameterCount, namedParameters);
-    if (!callStructure.signatureApplies(signature)) {
-      return false;
-    }
-    list.addAll(callStructure.makeArgumentsList(
-        nodes,
-        callee,
-        internalCompileArgument,
-        compileConstant));
-
-    return true;
-  }
-
-  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;
-  }
-}
-
-///
-class NamedCallStructure extends CallStructure {
-  final List<String> namedArguments;
-  final List<String> _orderedNamedArguments = <String>[];
-
-  NamedCallStructure(int argumentCount, this.namedArguments)
-      : super.unnamed(argumentCount) {
-    assert(namedArguments.isNotEmpty);
-  }
-
-  @override
-  bool get isNamed => true;
-
-  @override
-  bool get isUnnamed => false;
-
-  @override
-  int get namedArgumentCount => namedArguments.length;
-
-  @override
-  int get positionalArgumentCount => argumentCount - namedArgumentCount;
-
-  @override
-  List<String> getOrderedNamedArguments() {
-    if (!_orderedNamedArguments.isEmpty) return _orderedNamedArguments;
-
-    _orderedNamedArguments.addAll(namedArguments);
-    _orderedNamedArguments.sort((String first, String second) {
-      return first.compareTo(second);
-    });
-    return _orderedNamedArguments;
-  }
-
-  @override
-  String structureToString() {
-    return 'arity=$argumentCount, named=[${namedArguments.join(', ')}]';
-  }
-}
-
 class Selector {
   final SelectorKind kind;
   final Name memberName;
   final CallStructure callStructure;
 
   final int hashCode;
 
   int get argumentCount => callStructure.argumentCount;
   int get namedArgumentCount => callStructure.namedArgumentCount;
   int get positionalArgumentCount => callStructure.positionalArgumentCount;
@@ skipping 231 matching lines @@
     // Add bits from the call structure.
     return Hashing.mixHashCodeBits(hash, callStructure.hashCode);
   }
 
   String toString() {
     return 'Selector($kind, $name, ${callStructure.structureToString()})';
   }
 
   Selector toCallSelector() => new Selector.callClosureFrom(this);
 }