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; |
ngeoffray
2013/02/13 14:14:09
Fits in one line?
| |
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>[]; | |
140 | 75 |
141 FunctionSetNode(ClassElement type) : super(type), | 76 FunctionSetNode(this.name); |
142 membersByName = new Map<SourceString, Element>(); | |
143 | 77 |
78 void add(Element element) { | |
79 assert(element.name == name); | |
80 // Even when the representation of the elements has changed to a | |
81 // set we try to avoid clearing the cache unless we have to. For | |
ngeoffray
2013/02/13 14:14:09
I had a hard time understanding this sentence. May
| |
82 // that reason we keep the explicit contains check even though the | |
83 // add method ends up doing the work again (for sets). | |
84 if (!elements.contains(element)) { | |
85 if (elements is List && elements.length >= MAX_ELEMENTS_IN_LIST) { | |
86 elements = elements.toSet(); | |
87 } | |
88 elements.add(element); | |
89 cache.clear(); | |
90 } | |
91 } | |
92 | |
93 void remove(Element element) { | |
94 assert(element.name == name); | |
95 if (elements is Set) { | |
96 if (elements.remove(element)) { | |
97 cache.clear(); | |
98 } | |
99 } else { | |
100 assert(elements is List); | |
101 int index = elements.indexOf(element); | |
102 if (index < 0) return; | |
103 Element last = elements.removeLast(); | |
104 if (index != elements.length) { | |
105 elements[index] = last; | |
106 } | |
107 cache.clear(); | |
108 } | |
109 } | |
110 | |
111 bool contains(Element element) { | |
112 assert(element.name == name); | |
113 return elements.contains(element); | |
114 } | |
115 | |
116 void forEach(Function action) { | |
117 elements.forEach(action); | |
118 } | |
119 | |
120 Iterable<Element> filter(Selector selector, Compiler compiler) { | |
121 assert(selector.name == name); | |
122 List<Element> result = cache[selector]; | |
123 if (result != null) return result; | |
124 for (Element element in elements) { | |
125 if (selector.appliesUnnamed(element, compiler)) { | |
126 if (result == null) { | |
127 result = <Element>[]; | |
128 } | |
129 result.add(element); | |
130 } | |
131 } | |
132 if (result == null) result = const <Element>[]; | |
133 cache[selector] = result; | |
134 return result; | |
135 } | |
144 } | 136 } |
OLD | NEW |