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

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

import '../common/names.dart' show Identifiers, Selectors;
import '../elements/entities.dart';
import '../inferrer/abstract_value_domain.dart';
import '../util/util.dart' show Hashing, Setlet;
import 'selector.dart' show Selector;

// TODO(kasperl): This actually holds getters and setters just fine
// too and stricly they aren't functions. Maybe this needs a better
// name -- something like ElementSet seems a bit too generic.
class FunctionSet {
  final Map<String, FunctionSetNode> _nodes;

  factory FunctionSet(Iterable<MemberEntity> liveInstanceMembers) {
    Map<String, FunctionSetNode> nodes = new Map<String, FunctionSetNode>();
    for (MemberEntity member in liveInstanceMembers) {
      String name = member.name;
      (nodes[name] ??= new FunctionSetNode(name)).add(member);
    }
    return new FunctionSet.internal(nodes);
  }

  FunctionSet.internal(this._nodes);

  bool contains(MemberEntity element) {
    assert(element.isInstanceMember);
    assert(!element.isAbstract);
    String name = element.name;
    FunctionSetNode node = _nodes[name];
    return (node != null) ? node.contains(element) : false;
  }

  /// Returns all the functions that may be invoked with the [selector] on a
  /// receiver with the given [constraint]. The returned elements may include
  /// noSuchMethod handlers that are potential targets indirectly through the
  /// noSuchMethod mechanism.
  Iterable<MemberEntity> filter(
      Selector selector, AbstractValue receiver, AbstractValueDomain domain) {
    return query(selector, receiver, domain).functions;
  }

  /// Returns the mask for the potential receivers of a dynamic call to
  /// [selector] on [constraint].
  ///
  /// This will narrow the constraints of [constraint] to a [TypeMask] of the
  /// set of classes that actually implement the selected member or implement
  /// the handling 'noSuchMethod' where the selected member is unimplemented.
  AbstractValue receiverType(
      Selector selector, AbstractValue receiver, AbstractValueDomain domain) {
    return query(selector, receiver, domain).computeMask(domain);
  }

  SelectorMask _createSelectorMask(
      Selector selector, AbstractValue receiver, AbstractValueDomain domain) {
    return receiver != null
        ? new SelectorMask(selector, receiver)
        : new SelectorMask(selector, domain.dynamicType);
  }

  /// Returns the set of functions that can be the target of a call to
  /// [selector] on a receiver constrained by [constraint] including
  /// 'noSuchMethod' methods where applicable.
  FunctionSetQuery query(
      Selector selector, AbstractValue receiver, AbstractValueDomain domain) {
    String name = selector.name;
    SelectorMask selectorMask = _createSelectorMask(selector, receiver, domain);
    SelectorMask noSuchMethodMask =
        new SelectorMask(Selectors.noSuchMethod_, selectorMask.receiver);
    FunctionSetNode node = _nodes[name];
    FunctionSetNode noSuchMethods = _nodes[Identifiers.noSuchMethod_];
    if (node != null) {
      return node.query(selectorMask, domain, noSuchMethods, noSuchMethodMask);
    }
    // If there is no method that matches [selector] we know we can
    // only hit [:noSuchMethod:].
    if (noSuchMethods == null) {
      return const EmptyFunctionSetQuery();
    }
    return noSuchMethods.query(noSuchMethodMask, domain);
  }

  void forEach(void action(MemberEntity member)) {
    _nodes.forEach((String name, FunctionSetNode node) {
      node.forEach(action);
    });
  }
}

/// A selector/constraint pair representing the dynamic invocation of [selector]
/// on a receiver constrained by [constraint].
class SelectorMask {
  final Selector selector;
  final AbstractValue receiver;
  @override
  final int hashCode;

  SelectorMask(this.selector, this.receiver)
      : this.hashCode =
            Hashing.mixHashCodeBits(selector.hashCode, receiver.hashCode) {
    assert(receiver != null);
  }

  String get name => selector.name;

  bool applies(MemberEntity element, AbstractValueDomain domain) {
    if (!selector.appliesUnnamed(element)) return false;
    return domain
        .isTargetingMember(receiver, element, selector.memberName)
        .isPotentiallyTrue;
  }

  bool needsNoSuchMethodHandling(AbstractValueDomain domain) {
    return domain
        .needsNoSuchMethodHandling(receiver, selector)
        .isPotentiallyTrue;
  }

  @override
  bool operator ==(other) {
    if (identical(this, other)) return true;
    return selector == other.selector && receiver == other.receiver;
  }

  @override
  String toString() => '($selector,$receiver)';
}

/// A node in the [FunctionSet] caching all [FunctionSetQuery] object for
/// selectors with the same [name].
class FunctionSetNode {
  final String name;
  final Map<SelectorMask, FunctionSetQuery> cache =
      <SelectorMask, FunctionSetQuery>{};

  // Initially, we keep the elements in a list because it is more
  // compact than a hash set. Once we get enough elements, we change
  // the representation to be a set to get faster contains checks.
  static const int MAX_ELEMENTS_IN_LIST = 8;
  Iterable<MemberEntity> elements = <MemberEntity>[];
  bool isList = true;

  FunctionSetNode(this.name);

  void add(MemberEntity element) {
    assert(element.name == name);
    // We try to avoid clearing the cache unless we have to. For that
    // reason we keep the explicit contains check even though the add
    // method ends up doing the work again (for sets).
    if (!elements.contains(element)) {
      if (isList && elements.length >= MAX_ELEMENTS_IN_LIST) {
        elements = elements.toSet();
        isList = false;
      }
      if (isList) {
        List<MemberEntity> list = elements;
        list.add(element);
      } else {
        Set<MemberEntity> set = elements;
        set.add(element);
      }
      if (!cache.isEmpty) cache.clear();
    }
  }

  void remove(MemberEntity element) {
    assert(element.name == name);
    if (isList) {
      List<MemberEntity> list = elements;
      int index = list.indexOf(element);
      if (index < 0) return;
      MemberEntity last = list.removeLast();
      if (index != list.length) {
        list[index] = last;
      }
      if (!cache.isEmpty) cache.clear();
    } else {
      Set<MemberEntity> set = elements;
      if (set.remove(element)) {
        // To avoid wobbling between the two representations, we do
        // not transition back to the list representation even if we
        // end up with few enough elements at this point.
        if (!cache.isEmpty) cache.clear();
      }
    }
  }

  bool contains(MemberEntity element) {
    assert(element.name == name);
    return elements.contains(element);
  }

  void forEach(void action(MemberEntity member)) {
    elements.forEach(action);
  }

  /// Returns the set of functions that can be the target of [selectorMask]
  /// including no such method handling where applicable.
  FunctionSetQuery query(SelectorMask selectorMask, AbstractValueDomain domain,
      [FunctionSetNode noSuchMethods, SelectorMask noSuchMethodMask]) {
    assert(selectorMask.name == name);
    FunctionSetQuery result = cache[selectorMask];
    if (result != null) return result;

    Setlet<MemberEntity> functions;
    for (MemberEntity element in elements) {
      if (selectorMask.applies(element, domain)) {
        if (functions == null) {
          // Defer the allocation of the functions set until we are
          // sure we need it. This allows us to return immutable empty
          // lists when the filtering produced no results.
          functions = new Setlet<MemberEntity>();
        }
        functions.add(element);
      }
    }

    // If we cannot ensure a method will be found at runtime, we also
    // add [noSuchMethod] implementations that apply to [mask] as
    // potential targets.
    if (noSuchMethods != null &&
        selectorMask.needsNoSuchMethodHandling(domain)) {
      FunctionSetQuery noSuchMethodQuery =
          noSuchMethods.query(noSuchMethodMask, domain);
      if (!noSuchMethodQuery.functions.isEmpty) {
        if (functions == null) {
          functions =
              new Setlet<MemberEntity>.from(noSuchMethodQuery.functions);
        } else {
          functions.addAll(noSuchMethodQuery.functions);
        }
      }
    }
    cache[selectorMask] = result = (functions != null)
        ? new FullFunctionSetQuery(functions)
        : const EmptyFunctionSetQuery();
    return result;
  }

  @override
  String toString() {
    StringBuffer sb = new StringBuffer();
    sb.write('FunctionSetNode(');
    String comma = '';
    cache.forEach((mask, query) {
      sb.write(comma);
      sb.write('$mask=$query');
      comma = ',';
    });
    sb.write(')');
    return sb.toString();
  }
}

/// A set of functions that are the potential targets of all call sites sharing
/// the same receiver mask and selector.
abstract class FunctionSetQuery {
  const FunctionSetQuery();

  /// Compute the type of all potential receivers of this function set.
  AbstractValue computeMask(AbstractValueDomain domain);

  /// Returns all potential targets of this function set.
  Iterable<MemberEntity> get functions;
}

class EmptyFunctionSetQuery implements FunctionSetQuery {
  const EmptyFunctionSetQuery();

  @override
  AbstractValue computeMask(AbstractValueDomain domain) => domain.emptyType;

  @override
  Iterable<MemberEntity> get functions => const <MemberEntity>[];

  @override
  String toString() => '<empty>';
}

class FullFunctionSetQuery implements FunctionSetQuery {
  @override
  final Iterable<MemberEntity> functions;

  AbstractValue _receiver;

  FullFunctionSetQuery(this.functions);

  @override
  AbstractValue computeMask(AbstractValueDomain domain) {
    return _receiver ??= domain.computeReceiver(functions);
  }

  @override
  String toString() => '$_receiver:$functions';
}