OLD | NEW |
| (Empty) |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | |
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. | |
4 | |
5 library ordered_typeset; | |
6 | |
7 import 'dart2jslib.dart' show Compiler, MessageKind, invariant; | |
8 import 'dart_types.dart'; | |
9 import 'elements/elements.dart' show ClassElement; | |
10 import 'util/util.dart' show Link, LinkBuilder; | |
11 import 'util/util_implementation.dart' show LinkEntry; | |
12 | |
13 /** | |
14 * An ordered set of the supertypes of a class. The supertypes of a class are | |
15 * ordered by decreasing hierarchy depth and by the order they are extended, | |
16 * mixed in, or implemented. | |
17 * | |
18 * For these classes | |
19 * | |
20 * class A {} // Depth = 1. | |
21 * class B {} // Depth = 1. | |
22 * class C extends B implements A {} // Depth 2. | |
23 * | |
24 * the ordered supertypes are | |
25 * | |
26 * A: [A, Object] | |
27 * B: [B, Object] | |
28 * C: [C, B, A, Object] | |
29 */ | |
30 class OrderedTypeSet { | |
31 final List<Link<DartType>> _levels; | |
32 final Link<DartType> types; | |
33 final Link<DartType> _supertypes; | |
34 | |
35 OrderedTypeSet._internal(List<Link<DartType>> this._levels, | |
36 Link<DartType> this.types, | |
37 Link<DartType> this._supertypes); | |
38 | |
39 factory OrderedTypeSet.singleton(DartType type) { | |
40 Link<DartType> types = | |
41 new LinkEntry<DartType>(type, const Link<DartType>()); | |
42 List<Link<DartType>> list = new List<Link<DartType>>(1); | |
43 list[0] = types; | |
44 return new OrderedTypeSet._internal(list, types, const Link<DartType>()); | |
45 } | |
46 | |
47 /// Creates a new [OrderedTypeSet] for [type] when it directly extends the | |
48 /// class which this set represents. This is for instance used to create the | |
49 /// type set for [ClosureClassElement] which extends [Closure]. | |
50 OrderedTypeSet extendClass(InterfaceType type) { | |
51 assert(invariant(type.element, types.head.treatAsRaw, | |
52 message: 'Cannot extend generic class ${types.head} using ' | |
53 'OrderedTypeSet.extendClass')); | |
54 Link<DartType> extendedTypes = | |
55 new LinkEntry<DartType>(type, types); | |
56 List<Link<DartType>> list = new List<Link<DartType>>(levels + 1); | |
57 for (int i = 0; i < levels; i++) { | |
58 list[i] = _levels[i]; | |
59 } | |
60 list[levels] = extendedTypes; | |
61 return new OrderedTypeSet._internal( | |
62 list, extendedTypes, _supertypes.prepend(types.head)); | |
63 } | |
64 | |
65 Link<DartType> get supertypes => _supertypes; | |
66 | |
67 int get levels => _levels.length; | |
68 | |
69 int get maxDepth => levels - 1; | |
70 | |
71 Link<DartType> operator [](int index) { | |
72 if (index < levels) { | |
73 return _levels[index]; | |
74 } | |
75 return const Link<DartType>(); | |
76 } | |
77 | |
78 void forEach(int level, void f(DartType type)) { | |
79 if (level < levels) { | |
80 Link<DartType> pointer = _levels[level]; | |
81 Link<DartType> end = | |
82 level > 0 ? _levels[level - 1] : const Link<DartType>(); | |
83 while (!identical(pointer, end)) { | |
84 f(pointer.head); | |
85 pointer = pointer.tail; | |
86 } | |
87 } | |
88 } | |
89 | |
90 InterfaceType asInstanceOf(ClassElement cls) { | |
91 int level = cls.hierarchyDepth; | |
92 if (level < levels) { | |
93 Link<DartType> pointer = _levels[level]; | |
94 Link<DartType> end = | |
95 level > 0 ? _levels[level - 1] : const Link<DartType>(); | |
96 while (!identical(pointer, end)) { | |
97 if (cls == pointer.head.element) { | |
98 return pointer.head; | |
99 } | |
100 pointer = pointer.tail; | |
101 } | |
102 } | |
103 return null; | |
104 } | |
105 | |
106 String toString() => types.toString(); | |
107 } | |
108 | |
109 /** | |
110 * Builder for creation an ordered set of the supertypes of a class. The | |
111 * supertypes are ordered by decreasing hierarchy depth and by the order they | |
112 * are extended, mixed in, or implemented. | |
113 * | |
114 * For these classes | |
115 * | |
116 * class A {} // Depth = 1. | |
117 * class B {} // Depth = 1. | |
118 * class C extends B implements A {} // Depth 2. | |
119 * | |
120 * the ordered supertypes are | |
121 * | |
122 * A: [A, Object] | |
123 * B: [B, Object] | |
124 * C: [C, B, A, Object] | |
125 */ | |
126 class OrderedTypeSetBuilder { | |
127 Map<int, LinkEntry<DartType>> map = new Map<int, LinkEntry<DartType>>(); | |
128 // TODO(15296): Avoid computing this order on the side when member | |
129 // lookup handles multiply inherited members correctly. | |
130 LinkBuilder<DartType> allSupertypes = new LinkBuilder<DartType>(); | |
131 int maxDepth = -1; | |
132 | |
133 final ClassElement cls; | |
134 | |
135 OrderedTypeSetBuilder(this.cls); | |
136 | |
137 void add(Compiler compiler, InterfaceType type) { | |
138 if (type.element == cls) { | |
139 if (type.element != compiler.objectClass) { | |
140 allSupertypes.addLast(compiler.objectClass.rawType); | |
141 } | |
142 _addAtDepth(compiler, type, maxDepth + 1); | |
143 } else { | |
144 if (type.element != compiler.objectClass) { | |
145 allSupertypes.addLast(type); | |
146 } | |
147 _addAtDepth(compiler, type, type.element.hierarchyDepth); | |
148 } | |
149 } | |
150 | |
151 void _addAtDepth(Compiler compiler, InterfaceType type, int depth) { | |
152 LinkEntry<DartType> prev = null; | |
153 LinkEntry<DartType> link = map[depth]; | |
154 while (link != null) { | |
155 DartType existingType = link.head; | |
156 if (existingType == type) return; | |
157 if (existingType.element == type.element) { | |
158 compiler.reportError(cls, | |
159 MessageKind.MULTI_INHERITANCE, | |
160 {'thisType': cls.thisType, | |
161 'firstType': existingType, | |
162 'secondType': type}); | |
163 return; | |
164 } | |
165 prev = link; | |
166 link = link.tail; | |
167 } | |
168 LinkEntry<DartType> next = new LinkEntry<DartType>(type); | |
169 next.tail = null; | |
170 if (prev == null) { | |
171 map[depth] = next; | |
172 } else { | |
173 prev.tail = next; | |
174 } | |
175 if (depth > maxDepth) { | |
176 maxDepth = depth; | |
177 } | |
178 } | |
179 | |
180 OrderedTypeSet toTypeSet() { | |
181 List<Link<DartType>> levels = new List<Link<DartType>>(maxDepth + 1); | |
182 if (maxDepth < 0) { | |
183 return new OrderedTypeSet._internal( | |
184 levels, const Link<DartType>(), const Link<DartType>()); | |
185 } | |
186 Link<DartType> next = const Link<DartType>(); | |
187 for (int depth = 0; depth <= maxDepth; depth++) { | |
188 LinkEntry<DartType> first = map[depth]; | |
189 if (first == null) { | |
190 levels[depth] = next; | |
191 } else { | |
192 levels[depth] = first; | |
193 LinkEntry<DartType> last = first; | |
194 while (last.tail != null) { | |
195 last = last.tail; | |
196 } | |
197 last.tail = next; | |
198 next = first; | |
199 } | |
200 } | |
201 return new OrderedTypeSet._internal( | |
202 levels, levels.last, allSupertypes.toLink()); | |
203 } | |
204 | |
205 String toString() { | |
206 StringBuffer sb = new StringBuffer(); | |
207 for (int depth = 0; depth <= maxDepth; depth++) { | |
208 sb.write('$depth: '); | |
209 LinkEntry<DartType> first = map[depth]; | |
210 if (first != null) { | |
211 sb.write('${first.head}'); | |
212 while (first.tail != null) { | |
213 sb.write(', ${first.tail.head}'); | |
214 first = first.tail; | |
215 } | |
216 } | |
217 sb.write('\n'); | |
218 } | |
219 return sb.toString(); | |
220 } | |
221 } | |
OLD | NEW |