OLD | NEW |
| (Empty) |
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 | |
3 // BSD-style license that can be found in the LICENSE file. | |
4 | |
5 part of dart2js; | |
6 | |
7 abstract class ClassWorld { | |
8 // TODO(johnniwinther): Refine this into a `BackendClasses` interface. | |
9 Backend get backend; | |
10 | |
11 // TODO(johnniwinther): Remove the need for this getter. | |
12 @deprecated | |
13 Compiler get compiler; | |
14 | |
15 /// The [ClassElement] for the [Object] class defined in 'dart:core'. | |
16 ClassElement get objectClass; | |
17 | |
18 /// The [ClassElement] for the [Function] class defined in 'dart:core'. | |
19 ClassElement get functionClass; | |
20 | |
21 /// The [ClassElement] for the [bool] class defined in 'dart:core'. | |
22 ClassElement get boolClass; | |
23 | |
24 /// The [ClassElement] for the [num] class defined in 'dart:core'. | |
25 ClassElement get numClass; | |
26 | |
27 /// The [ClassElement] for the [int] class defined in 'dart:core'. | |
28 ClassElement get intClass; | |
29 | |
30 /// The [ClassElement] for the [double] class defined in 'dart:core'. | |
31 ClassElement get doubleClass; | |
32 | |
33 /// The [ClassElement] for the [String] class defined in 'dart:core'. | |
34 ClassElement get stringClass; | |
35 | |
36 /// Returns `true` if [cls] is instantiated. | |
37 bool isInstantiated(ClassElement cls); | |
38 | |
39 /// Returns `true` if the class world is closed. | |
40 bool get isClosed; | |
41 | |
42 /// Return `true` if [x] is a subclass of [y]. | |
43 bool isSubclassOf(ClassElement x, ClassElement y); | |
44 | |
45 /// Returns `true` if [x] is a subtype of [y], that is, if [x] implements an | |
46 /// instance of [y]. | |
47 bool isSubtypeOf(ClassElement x, ClassElement y); | |
48 | |
49 /// Returns an iterable over the live classes that extend [cls] including | |
50 /// [cls] itself. | |
51 Iterable<ClassElement> subclassesOf(ClassElement cls); | |
52 | |
53 /// Returns an iterable over the live classes that extend [cls] _not_ | |
54 /// including [cls] itself. | |
55 Iterable<ClassElement> strictSubclassesOf(ClassElement cls); | |
56 | |
57 /// Returns an iterable over the live classes that implement [cls] including | |
58 /// [cls] if it is live. | |
59 Iterable<ClassElement> subtypesOf(ClassElement cls); | |
60 | |
61 /// Returns an iterable over the live classes that implement [cls] _not_ | |
62 /// including [cls] if it is live. | |
63 Iterable<ClassElement> strictSubtypesOf(ClassElement cls); | |
64 | |
65 /// Returns `true` if any live class extends [cls]. | |
66 bool hasAnySubclass(ClassElement cls); | |
67 | |
68 /// Returns `true` if any live class other than [cls] extends [cls]. | |
69 bool hasAnyStrictSubclass(ClassElement cls); | |
70 | |
71 /// Returns `true` if any live class implements [cls]. | |
72 bool hasAnySubtype(ClassElement cls); | |
73 | |
74 /// Returns `true` if any live class other than [cls] implements [cls]. | |
75 bool hasAnyStrictSubtype(ClassElement cls); | |
76 | |
77 /// Returns `true` if all live classes that implement [cls] extend it. | |
78 bool hasOnlySubclasses(ClassElement cls); | |
79 | |
80 /// Returns an iterable over the common supertypes of the [classes]. | |
81 Iterable<ClassElement> commonSupertypesOf(Iterable<ClassElement> classes); | |
82 | |
83 /// Returns an iterable over the live mixin applications that mixin [cls]. | |
84 Iterable<MixinApplicationElement> mixinUsesOf(ClassElement cls); | |
85 | |
86 /// Returns `true` if [cls] is mixed into a live class. | |
87 bool isUsedAsMixin(ClassElement cls); | |
88 | |
89 /// Returns `true` if any live class that mixes in [cls] implements [type]. | |
90 bool hasAnySubclassOfMixinUseThatImplements(ClassElement cls, | |
91 ClassElement type); | |
92 | |
93 /// Returns `true` if any live class that mixes in [mixin] is also a subclass | |
94 /// of [superclass]. | |
95 bool hasAnySubclassThatMixes(ClassElement superclass, ClassElement mixin); | |
96 | |
97 /// Returns `true` if any subclass of [superclass] implements [type]. | |
98 bool hasAnySubclassThatImplements(ClassElement superclass, ClassElement type); | |
99 } | |
100 | |
101 class World implements ClassWorld { | |
102 ClassElement get objectClass => compiler.objectClass; | |
103 ClassElement get functionClass => compiler.functionClass; | |
104 ClassElement get boolClass => compiler.boolClass; | |
105 ClassElement get numClass => compiler.numClass; | |
106 ClassElement get intClass => compiler.intClass; | |
107 ClassElement get doubleClass => compiler.doubleClass; | |
108 ClassElement get stringClass => compiler.stringClass; | |
109 | |
110 bool checkInvariants(ClassElement cls, {bool mustBeInstantiated: true}) { | |
111 return | |
112 invariant(cls, cls.isDeclaration, | |
113 message: '$cls must be the declaration.') && | |
114 invariant(cls, cls.isResolved, | |
115 message: '$cls must be resolved.') && | |
116 (!mustBeInstantiated || | |
117 invariant(cls, isInstantiated(cls), | |
118 message: '$cls is not instantiated.')); | |
119 } | |
120 | |
121 /// Returns `true` if [x] is a subtype of [y], that is, if [x] implements an | |
122 /// instance of [y]. | |
123 bool isSubtypeOf(ClassElement x, ClassElement y) { | |
124 assert(checkInvariants(x)); | |
125 assert(checkInvariants(y, mustBeInstantiated: false)); | |
126 | |
127 if (y == objectClass) return true; | |
128 if (x == objectClass) return false; | |
129 if (x.asInstanceOf(y) != null) return true; | |
130 if (y != functionClass) return false; | |
131 return x.callType != null; | |
132 } | |
133 | |
134 /// Return `true` if [x] is a (non-strict) subclass of [y]. | |
135 bool isSubclassOf(ClassElement x, ClassElement y) { | |
136 assert(checkInvariants(x)); | |
137 assert(checkInvariants(y)); | |
138 | |
139 if (y == objectClass) return true; | |
140 if (x == objectClass) return false; | |
141 while (x != null && x.hierarchyDepth >= y.hierarchyDepth) { | |
142 if (x == y) return true; | |
143 x = x.superclass; | |
144 } | |
145 return false; | |
146 } | |
147 | |
148 /// Returns `true` if [cls] is instantiated. | |
149 bool isInstantiated(ClassElement cls) { | |
150 return compiler.resolverWorld.isInstantiated(cls); | |
151 } | |
152 | |
153 /// Returns an iterable over the live classes that extend [cls] including | |
154 /// [cls] itself. | |
155 Iterable<ClassElement> subclassesOf(ClassElement cls) { | |
156 Set<ClassElement> subclasses = _subclasses[cls.declaration]; | |
157 if (subclasses == null) return const <ClassElement>[]; | |
158 assert(invariant(cls, isInstantiated(cls.declaration), | |
159 message: 'Class $cls has not been instantiated.')); | |
160 return subclasses; | |
161 } | |
162 | |
163 /// Returns an iterable over the live classes that extend [cls] _not_ | |
164 /// including [cls] itself. | |
165 Iterable<ClassElement> strictSubclassesOf(ClassElement cls) { | |
166 return subclassesOf(cls).where((c) => c != cls); | |
167 } | |
168 | |
169 /// Returns an iterable over the live classes that implement [cls] including | |
170 /// [cls] if it is live. | |
171 Iterable<ClassElement> subtypesOf(ClassElement cls) { | |
172 Set<ClassElement> subtypes = _subtypes[cls.declaration]; | |
173 return subtypes != null ? subtypes : const <ClassElement>[]; | |
174 } | |
175 | |
176 /// Returns an iterable over the live classes that implement [cls] _not_ | |
177 /// including [cls] if it is live. | |
178 Iterable<ClassElement> strictSubtypesOf(ClassElement cls) { | |
179 return subtypesOf(cls).where((c) => c != cls); | |
180 } | |
181 | |
182 /// Returns `true` if any live class extends [cls]. | |
183 bool hasAnySubclass(ClassElement cls) { | |
184 return !subclassesOf(cls).isEmpty; | |
185 } | |
186 | |
187 /// Returns `true` if any live class other than [cls] extends [cls]. | |
188 bool hasAnyStrictSubclass(ClassElement cls) { | |
189 return !strictSubclassesOf(cls).isEmpty; | |
190 } | |
191 | |
192 /// Returns `true` if any live class implements [cls]. | |
193 bool hasAnySubtype(ClassElement cls) { | |
194 return !subtypesOf(cls).isEmpty; | |
195 } | |
196 | |
197 /// Returns `true` if any live class other than [cls] implements [cls]. | |
198 bool hasAnyStrictSubtype(ClassElement cls) { | |
199 return !strictSubtypesOf(cls).isEmpty; | |
200 } | |
201 | |
202 /// Returns `true` if all live classes that implement [cls] extend it. | |
203 bool hasOnlySubclasses(ClassElement cls) { | |
204 Iterable<ClassElement> subtypes = subtypesOf(cls); | |
205 if (subtypes == null) return true; | |
206 Iterable<ClassElement> subclasses = subclassesOf(cls); | |
207 return subclasses != null && (subclasses.length == subtypes.length); | |
208 } | |
209 | |
210 /// Returns an iterable over the common supertypes of the [classes]. | |
211 Iterable<ClassElement> commonSupertypesOf(Iterable<ClassElement> classes) { | |
212 Iterator<ClassElement> iterator = classes.iterator; | |
213 if (!iterator.moveNext()) return const <ClassElement>[]; | |
214 | |
215 ClassElement cls = iterator.current; | |
216 assert(checkInvariants(cls)); | |
217 OrderedTypeSet typeSet = cls.allSupertypesAndSelf; | |
218 if (!iterator.moveNext()) return typeSet.types.map((type) => type.element); | |
219 | |
220 int depth = typeSet.maxDepth; | |
221 Link<OrderedTypeSet> otherTypeSets = const Link<OrderedTypeSet>(); | |
222 do { | |
223 ClassElement otherClass = iterator.current; | |
224 assert(checkInvariants(otherClass)); | |
225 OrderedTypeSet otherTypeSet = otherClass.allSupertypesAndSelf; | |
226 otherTypeSets = otherTypeSets.prepend(otherTypeSet); | |
227 if (otherTypeSet.maxDepth < depth) { | |
228 depth = otherTypeSet.maxDepth; | |
229 } | |
230 } while (iterator.moveNext()); | |
231 | |
232 List<ClassElement> commonSupertypes = <ClassElement>[]; | |
233 OUTER: for (Link<DartType> link = typeSet[depth]; | |
234 link.head.element != objectClass; | |
235 link = link.tail) { | |
236 ClassElement cls = link.head.element; | |
237 for (Link<OrderedTypeSet> link = otherTypeSets; | |
238 !link.isEmpty; | |
239 link = link.tail) { | |
240 if (link.head.asInstanceOf(cls) == null) { | |
241 continue OUTER; | |
242 } | |
243 } | |
244 commonSupertypes.add(cls); | |
245 } | |
246 commonSupertypes.add(objectClass); | |
247 return commonSupertypes; | |
248 } | |
249 | |
250 /// Returns an iterable over all mixin applications that mixin [cls]. | |
251 Iterable<MixinApplicationElement> allMixinUsesOf(ClassElement cls) { | |
252 Iterable<MixinApplicationElement> uses = _mixinUses[cls]; | |
253 return uses != null ? uses : const <MixinApplicationElement>[]; | |
254 } | |
255 | |
256 /// Returns an iterable over the live mixin applications that mixin [cls]. | |
257 Iterable<MixinApplicationElement> mixinUsesOf(ClassElement cls) { | |
258 assert(isClosed); | |
259 if (_liveMixinUses == null) { | |
260 _liveMixinUses = new Map<ClassElement, List<MixinApplicationElement>>(); | |
261 for (ClassElement mixin in _mixinUses.keys) { | |
262 Iterable<MixinApplicationElement> uses = | |
263 _mixinUses[mixin].where(isInstantiated); | |
264 if (uses.isNotEmpty) _liveMixinUses[mixin] = uses.toList(); | |
265 } | |
266 } | |
267 Iterable<MixinApplicationElement> uses = _liveMixinUses[cls]; | |
268 return uses != null ? uses : const <MixinApplicationElement>[]; | |
269 } | |
270 | |
271 /// Returns `true` if [cls] is mixed into a live class. | |
272 bool isUsedAsMixin(ClassElement cls) { | |
273 return !mixinUsesOf(cls).isEmpty; | |
274 } | |
275 | |
276 /// Returns `true` if any live class that mixes in [cls] implements [type]. | |
277 bool hasAnySubclassOfMixinUseThatImplements(ClassElement cls, | |
278 ClassElement type) { | |
279 return mixinUsesOf(cls).any( | |
280 (use) => hasAnySubclassThatImplements(use, type)); | |
281 } | |
282 | |
283 /// Returns `true` if any live class that mixes in [mixin] is also a subclass | |
284 /// of [superclass]. | |
285 bool hasAnySubclassThatMixes(ClassElement superclass, ClassElement mixin) { | |
286 return mixinUsesOf(mixin).any((each) => each.isSubclassOf(superclass)); | |
287 } | |
288 | |
289 /// Returns `true` if any subclass of [superclass] implements [type]. | |
290 bool hasAnySubclassThatImplements(ClassElement superclass, | |
291 ClassElement type) { | |
292 Set<ClassElement> subclasses = typesImplementedBySubclassesOf(superclass); | |
293 if (subclasses == null) return false; | |
294 return subclasses.contains(type); | |
295 } | |
296 | |
297 final Compiler compiler; | |
298 Backend get backend => compiler.backend; | |
299 final FunctionSet allFunctions; | |
300 final Set<Element> functionsCalledInLoop = new Set<Element>(); | |
301 final Map<Element, SideEffects> sideEffects = new Map<Element, SideEffects>(); | |
302 | |
303 final Set<TypedefElement> allTypedefs = new Set<TypedefElement>(); | |
304 | |
305 final Map<ClassElement, List<MixinApplicationElement>> _mixinUses = | |
306 new Map<ClassElement, List<MixinApplicationElement>>(); | |
307 Map<ClassElement, List<MixinApplicationElement>> _liveMixinUses; | |
308 | |
309 final Map<ClassElement, Set<ClassElement>> _typesImplementedBySubclasses = | |
310 new Map<ClassElement, Set<ClassElement>>(); | |
311 | |
312 // We keep track of subtype and subclass relationships in four | |
313 // distinct sets to make class hierarchy analysis faster. | |
314 final Map<ClassElement, Set<ClassElement>> _subclasses = | |
315 new Map<ClassElement, Set<ClassElement>>(); | |
316 final Map<ClassElement, Set<ClassElement>> _subtypes = | |
317 new Map<ClassElement, Set<ClassElement>>(); | |
318 | |
319 final Set<Element> sideEffectsFreeElements = new Set<Element>(); | |
320 | |
321 final Set<Element> elementsThatCannotThrow = new Set<Element>(); | |
322 | |
323 final Set<Element> functionsThatMightBePassedToApply = | |
324 new Set<FunctionElement>(); | |
325 | |
326 final Set<Element> alreadyPopulated; | |
327 | |
328 bool get isClosed => compiler.phase > Compiler.PHASE_RESOLVING; | |
329 | |
330 // Used by selectors. | |
331 bool isAssertMethod(Element element) { | |
332 return compiler.backend.isAssertMethod(element); | |
333 } | |
334 | |
335 // Used by selectors. | |
336 bool isForeign(Element element) { | |
337 return element.isForeign(compiler.backend); | |
338 } | |
339 | |
340 Set<ClassElement> typesImplementedBySubclassesOf(ClassElement cls) { | |
341 return _typesImplementedBySubclasses[cls.declaration]; | |
342 } | |
343 | |
344 World(Compiler compiler) | |
345 : allFunctions = new FunctionSet(compiler), | |
346 this.compiler = compiler, | |
347 alreadyPopulated = compiler.cacheStrategy.newSet(); | |
348 | |
349 void populate() { | |
350 void addSubtypes(ClassElement cls) { | |
351 if (compiler.hasIncrementalSupport && !alreadyPopulated.add(cls)) { | |
352 return; | |
353 } | |
354 assert(cls.isDeclaration); | |
355 if (!cls.isResolved) { | |
356 compiler.internalError(cls, 'Class "${cls.name}" is not resolved.'); | |
357 } | |
358 | |
359 for (DartType type in cls.allSupertypes) { | |
360 Set<Element> subtypesOfSupertype = | |
361 _subtypes.putIfAbsent(type.element, () => new Set<ClassElement>()); | |
362 subtypesOfSupertype.add(cls); | |
363 } | |
364 | |
365 // Walk through the superclasses, and record the types | |
366 // implemented by that type on the superclasses. | |
367 ClassElement superclass = cls.superclass; | |
368 while (superclass != null) { | |
369 Set<Element> subclassesOfSuperclass = | |
370 _subclasses.putIfAbsent(superclass, () => new Set<ClassElement>()); | |
371 subclassesOfSuperclass.add(cls); | |
372 | |
373 Set<Element> typesImplementedBySubclassesOfCls = | |
374 _typesImplementedBySubclasses.putIfAbsent( | |
375 superclass, () => new Set<ClassElement>()); | |
376 for (DartType current in cls.allSupertypes) { | |
377 typesImplementedBySubclassesOfCls.add(current.element); | |
378 } | |
379 superclass = superclass.superclass; | |
380 } | |
381 } | |
382 | |
383 // Use the [:seenClasses:] set to include non-instantiated | |
384 // classes: if the superclass of these classes require RTI, then | |
385 // they also need RTI, so that a constructor passes the type | |
386 // variables to the super constructor. | |
387 compiler.resolverWorld.directlyInstantiatedClasses.forEach(addSubtypes); | |
388 } | |
389 | |
390 void registerMixinUse(MixinApplicationElement mixinApplication, | |
391 ClassElement mixin) { | |
392 // TODO(johnniwinther): Add map restricted to live classes. | |
393 // We don't support patch classes as mixin. | |
394 assert(mixin.isDeclaration); | |
395 List<MixinApplicationElement> users = | |
396 _mixinUses.putIfAbsent(mixin, () => | |
397 new List<MixinApplicationElement>()); | |
398 users.add(mixinApplication); | |
399 } | |
400 | |
401 bool hasAnyUserDefinedGetter(Selector selector) { | |
402 return allFunctions.filter(selector).any((each) => each.isGetter); | |
403 } | |
404 | |
405 void registerUsedElement(Element element) { | |
406 if (element.isInstanceMember && !element.isAbstract) { | |
407 allFunctions.add(element); | |
408 } | |
409 } | |
410 | |
411 VariableElement locateSingleField(Selector selector) { | |
412 Element result = locateSingleElement(selector); | |
413 return (result != null && result.isField) ? result : null; | |
414 } | |
415 | |
416 Element locateSingleElement(Selector selector) { | |
417 ti.TypeMask mask = selector.mask == null | |
418 ? compiler.typesTask.dynamicType | |
419 : selector.mask; | |
420 return mask.locateSingleElement(selector, compiler); | |
421 } | |
422 | |
423 void addFunctionCalledInLoop(Element element) { | |
424 functionsCalledInLoop.add(element.declaration); | |
425 } | |
426 | |
427 bool isCalledInLoop(Element element) { | |
428 return functionsCalledInLoop.contains(element.declaration); | |
429 } | |
430 | |
431 bool fieldNeverChanges(Element element) { | |
432 if (!element.isField) return false; | |
433 if (element.isNative) { | |
434 // Some native fields are views of data that may be changed by operations. | |
435 // E.g. node.firstChild depends on parentNode.removeBefore(n1, n2). | |
436 // TODO(sra): Refine the effect classification so that native effects are | |
437 // distinct from ordinary Dart effects. | |
438 return false; | |
439 } | |
440 | |
441 return element.isFinal | |
442 || element.isConst | |
443 || (element.isInstanceMember | |
444 && !compiler.resolverWorld.hasInvokedSetter(element, this)); | |
445 } | |
446 | |
447 SideEffects getSideEffectsOfElement(Element element) { | |
448 // The type inferrer (where the side effects are being computed), | |
449 // does not see generative constructor bodies because they are | |
450 // created by the backend. Also, it does not make any distinction | |
451 // between a constructor and its body for side effects. This | |
452 // implies that currently, the side effects of a constructor body | |
453 // contain the side effects of the initializers. | |
454 assert(!element.isGenerativeConstructorBody); | |
455 assert(!element.isField); | |
456 return sideEffects.putIfAbsent(element.declaration, () { | |
457 return new SideEffects(); | |
458 }); | |
459 } | |
460 | |
461 void registerSideEffects(Element element, SideEffects effects) { | |
462 if (sideEffectsFreeElements.contains(element)) return; | |
463 sideEffects[element.declaration] = effects; | |
464 } | |
465 | |
466 void registerSideEffectsFree(Element element) { | |
467 sideEffects[element.declaration] = new SideEffects.empty(); | |
468 sideEffectsFreeElements.add(element); | |
469 } | |
470 | |
471 SideEffects getSideEffectsOfSelector(Selector selector) { | |
472 // We're not tracking side effects of closures. | |
473 if (selector.isClosureCall) return new SideEffects(); | |
474 SideEffects sideEffects = new SideEffects.empty(); | |
475 for (Element e in allFunctions.filter(selector)) { | |
476 if (e.isField) { | |
477 if (selector.isGetter) { | |
478 if (!fieldNeverChanges(e)) { | |
479 sideEffects.setDependsOnInstancePropertyStore(); | |
480 } | |
481 } else if (selector.isSetter) { | |
482 sideEffects.setChangesInstanceProperty(); | |
483 } else { | |
484 assert(selector.isCall); | |
485 sideEffects.setAllSideEffects(); | |
486 sideEffects.setDependsOnSomething(); | |
487 } | |
488 } else { | |
489 sideEffects.add(getSideEffectsOfElement(e)); | |
490 } | |
491 } | |
492 return sideEffects; | |
493 } | |
494 | |
495 void registerCannotThrow(Element element) { | |
496 elementsThatCannotThrow.add(element); | |
497 } | |
498 | |
499 bool getCannotThrow(Element element) { | |
500 return elementsThatCannotThrow.contains(element); | |
501 } | |
502 | |
503 void registerImplicitSuperCall(Registry registry, | |
504 FunctionElement superConstructor) { | |
505 registry.registerDependency(superConstructor); | |
506 } | |
507 | |
508 void registerMightBePassedToApply(Element element) { | |
509 functionsThatMightBePassedToApply.add(element); | |
510 } | |
511 | |
512 bool getMightBePassedToApply(Element element) { | |
513 // We have to check whether the element we look at was created after | |
514 // type inference ran. This is currently only the case for the call | |
515 // method of function classes that were generated for function | |
516 // expressions. In such a case, we have to look at the original | |
517 // function expressions's element. | |
518 // TODO(herhut): Generate classes for function expressions earlier. | |
519 if (element is closureMapping.SynthesizedCallMethodElementX) { | |
520 return getMightBePassedToApply(element.expression); | |
521 } | |
522 return functionsThatMightBePassedToApply.contains(element); | |
523 } | |
524 } | |
OLD | NEW |