OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 part of universe; | 5 part of universe; |
6 | 6 |
7 // TODO(kasperl): This actually holds getters and setters just fine | 7 // TODO(kasperl): This actually holds getters and setters just fine |
8 // too and stricly they aren't functions. Maybe this needs a better | 8 // too and stricly they aren't functions. Maybe this needs a better |
9 // name -- something like ElementSet seems a bit too generic. | 9 // name -- something like ElementSet seems a bit too generic. |
10 class FunctionSet extends PartialTypeTree { | 10 class FunctionSet { |
| 11 final Compiler compiler; |
| 12 final Map<SourceString, FunctionSetNode> nodes = |
| 13 new Map<SourceString, FunctionSetNode>(); |
| 14 FunctionSet(this.compiler); |
11 | 15 |
12 FunctionSet(Compiler compiler) : super(compiler); | |
13 | |
14 FunctionSetNode newSpecializedNode(ClassElement type) | |
15 => new FunctionSetNode(type); | |
16 | |
17 // TODO(kasperl): Allow static members too? | |
18 void add(Element element) { | 16 void add(Element element) { |
19 assert(element.isMember()); | 17 assert(element.isMember()); |
20 FunctionSetNode node = findNode(element.getEnclosingClass(), true); | 18 SourceString name = element.name; |
21 node.membersByName[element.name] = element; | 19 FunctionSetNode node = nodes.putIfAbsent( |
| 20 name, () => new FunctionSetNode(name)); |
| 21 node.add(element); |
22 } | 22 } |
23 | 23 |
24 // TODO(kasperl): Allow static members too? | |
25 void remove(Element element) { | 24 void remove(Element element) { |
26 assert(element.isMember()); | 25 assert(element.isMember()); |
27 FunctionSetNode node = findNode(element.getEnclosingClass(), false); | 26 SourceString name = element.name; |
28 if (node != null) node.membersByName.remove(element.name); | 27 FunctionSetNode node = nodes[name]; |
| 28 if (node != null) node.remove(element); |
29 } | 29 } |
30 | 30 |
31 // TODO(kasperl): Allow static members too? | |
32 bool contains(Element element) { | 31 bool contains(Element element) { |
33 assert(element.isMember()); | 32 assert(element.isMember()); |
34 FunctionSetNode node = findNode(element.getEnclosingClass(), false); | 33 SourceString name = element.name; |
| 34 FunctionSetNode node = nodes[name]; |
35 return (node != null) | 35 return (node != null) |
36 ? node.membersByName.containsKey(element.name) | 36 ? node.contains(element) |
37 : false; | 37 : false; |
38 } | 38 } |
39 | 39 |
40 bool shouldVisitAll(Selector selector) { | |
41 // TODO(kasperl): For now, we use a different implementation for | |
42 // filtering if the tree contains interface subtypes. | |
43 return containsInterfaceSubtypes | |
44 && (selector.typeKind == TypedSelectorKind.INTERFACE | |
45 || selector.typeKind == TypedSelectorKind.UNKNOWN); | |
46 } | |
47 | |
48 /** | 40 /** |
49 * Returns all elements that may be invoked with the given [selector]. | 41 * Returns all elements that may be invoked with the given [selector]. |
50 */ | 42 */ |
51 Set<Element> filterBySelector(Selector selector) { | 43 Iterable<Element> filterBySelector(Selector selector) { |
52 return shouldVisitAll(selector) | 44 SourceString name = selector.name; |
53 ? filterAllBySelector(selector) | 45 FunctionSetNode node = nodes[name]; |
54 : filterHierarchyBySelector(selector); | 46 return (node != null) |
| 47 ? node.filter(selector, compiler) |
| 48 : const <Element>[]; |
55 } | 49 } |
56 | 50 |
57 /** | 51 /** |
58 * Returns whether the set has any element matching the given | 52 * Returns whether the set has any element matching the given |
59 * [selector]. | 53 * [selector]. |
60 */ | 54 */ |
61 bool hasAnyElementMatchingSelector(Selector selector) { | 55 bool hasAnyElementMatchingSelector(Selector selector) { |
62 return shouldVisitAll(selector) | 56 return !filterBySelector(selector).isEmpty; |
63 ? hasAnyInAll(selector) | |
64 : hasAnyInHierarchy(selector); | |
65 } | 57 } |
66 | 58 |
67 Set<Element> filterAllBySelector(Selector selector) { | 59 void forEach(Function action) { |
68 Set<Element> result = new Set<Element>(); | 60 nodes.forEach((SourceString name, FunctionSetNode node) { |
69 if (root == null) return result; | 61 node.forEach(action); |
70 root.visitRecursively((FunctionSetNode node) { | |
71 Element member = node.membersByName[selector.name]; | |
72 // Since we're running through the entire tree we have to use | |
73 // the applies method that takes types into account. | |
74 if (member != null && selector.appliesUnnamed(member, compiler)) { | |
75 result.add(member); | |
76 } | |
77 return true; | |
78 }); | |
79 return result; | |
80 } | |
81 | |
82 Set<Element> filterHierarchyBySelector(Selector selector) { | |
83 Set<Element> result = new Set<Element>(); | |
84 if (root == null) return result; | |
85 visitHierarchy(selectorType(selector), (FunctionSetNode node) { | |
86 Element member = node.membersByName[selector.name]; | |
87 if (member != null && selector.appliesUntyped(member, compiler)) { | |
88 result.add(member); | |
89 } | |
90 return true; | |
91 }); | |
92 return result; | |
93 } | |
94 | |
95 bool hasAnyInAll(Selector selector) { | |
96 bool result = false; | |
97 if (root == null) return result; | |
98 root.visitRecursively((FunctionSetNode node) { | |
99 Element member = node.membersByName[selector.name]; | |
100 // Since we're running through the entire tree we have to use | |
101 // the applies method that takes types into account. | |
102 if (member != null && selector.appliesUnnamed(member, compiler)) { | |
103 result = true; | |
104 // End the traversal. | |
105 return false; | |
106 } | |
107 return true; | |
108 }); | |
109 return result; | |
110 } | |
111 | |
112 bool hasAnyInHierarchy(Selector selector) { | |
113 bool result = false; | |
114 if (root == null) return result; | |
115 visitHierarchy(selectorType(selector), (FunctionSetNode node) { | |
116 Element member = node.membersByName[selector.name]; | |
117 if (member != null && selector.appliesUntyped(member, compiler)) { | |
118 result = true; | |
119 // End the traversal. | |
120 return false; | |
121 } | |
122 return true; | |
123 }); | |
124 return result; | |
125 } | |
126 | |
127 void forEach(Function f) { | |
128 if (root == null) return; | |
129 root.visitRecursively((FunctionSetNode node) { | |
130 node.membersByName.forEach( | |
131 (SourceString _, Element element) => f(element)); | |
132 return true; | |
133 }); | 62 }); |
134 } | 63 } |
135 } | 64 } |
136 | 65 |
137 class FunctionSetNode extends PartialTypeTreeNode { | 66 class FunctionSetNode { |
| 67 final SourceString name; |
| 68 final Map<Selector, List<Element>> cache = new Map<Selector, List<Element>>(); |
138 | 69 |
139 final Map<SourceString, Element> membersByName; | 70 // Initially, we keep the elements in a list because it is more |
| 71 // compact than a hash set. Once we get enough elements, we change |
| 72 // the representation to be a set to get faster contains checks. |
| 73 static const int MAX_ELEMENTS_IN_LIST = 8; |
| 74 Collection<Element> elements = <Element>[]; |
| 75 bool isList = true; |
140 | 76 |
141 FunctionSetNode(ClassElement type) : super(type), | 77 FunctionSetNode(this.name); |
142 membersByName = new Map<SourceString, Element>(); | |
143 | 78 |
| 79 void add(Element element) { |
| 80 assert(element.name == name); |
| 81 // Even when the representation of the elements has changed to a |
| 82 // set we try to avoid clearing the cache unless we have to. For |
| 83 // that reason we keep the explicit contains check even though the |
| 84 // add method ends up doing the work again (for sets). |
| 85 if (!elements.contains(element)) { |
| 86 if (isList && elements.length >= MAX_ELEMENTS_IN_LIST) { |
| 87 elements = elements.toSet(); |
| 88 isList = false; |
| 89 } |
| 90 elements.add(element); |
| 91 cache.clear(); |
| 92 } |
| 93 } |
| 94 |
| 95 void remove(Element element) { |
| 96 assert(element.name == name); |
| 97 if (isList) { |
| 98 List list = elements; |
| 99 int index = list.indexOf(element); |
| 100 if (index < 0) return; |
| 101 Element last = list.removeLast(); |
| 102 if (index != list.length) { |
| 103 list[index] = last; |
| 104 } |
| 105 cache.clear(); |
| 106 } else { |
| 107 Set set = elements; |
| 108 if (set.remove(element)) { |
| 109 // To avoid wobbling between the two representations, we do |
| 110 // not transition back to the list representation even if we |
| 111 // end up with few enough elements at this point. |
| 112 cache.clear(); |
| 113 } |
| 114 } |
| 115 } |
| 116 |
| 117 bool contains(Element element) { |
| 118 assert(element.name == name); |
| 119 return elements.contains(element); |
| 120 } |
| 121 |
| 122 void forEach(Function action) { |
| 123 elements.forEach(action); |
| 124 } |
| 125 |
| 126 Iterable<Element> filter(Selector selector, Compiler compiler) { |
| 127 assert(selector.name == name); |
| 128 List<Element> result = cache[selector]; |
| 129 if (result != null) return result; |
| 130 for (Element element in elements) { |
| 131 if (selector.appliesUnnamed(element, compiler)) { |
| 132 if (result == null) { |
| 133 // Defer the allocation of the resulting list until we are |
| 134 // sure we need it. This allows us to return immutable empty |
| 135 // lists when the filtering produced no results. |
| 136 result = <Element>[]; |
| 137 } |
| 138 result.add(element); |
| 139 } |
| 140 } |
| 141 if (result == null) result = const <Element>[]; |
| 142 cache[selector] = result; |
| 143 return result; |
| 144 } |
144 } | 145 } |
OLD | NEW |