| // 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 '../types/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; | |
| 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.canHit(receiver, element, selector); | |
| } | |
| bool needsNoSuchMethodHandling(AbstractValueDomain domain) { | |
| return domain.needsNoSuchMethodHandling(receiver, selector); | |
| } | |
| bool operator ==(other) { | |
| if (identical(this, other)) return true; | |
| return selector == other.selector && receiver == other.receiver; | |
| } | |
| 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; | |
| } | |
| 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>[]; | |
| 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); | |
| } | |
| String toString() => '$_receiver:$functions'; | |
| } |