// 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 resolution.ordered_typeset_builder; | |
import 'dart2jslib.dart' show Compiler, MessageKind; | |
import 'dart_types.dart'; | |
import 'elements/elements.dart' show ClassElement; | |
import 'util/util.dart' show Link, LinkBuilder; | |
import 'util/util_implementation.dart' show LinkEntry; | |
/** | |
* An ordered set of the supertypes of a class. The supertypes of a class are | |
* ordered by decreasing hierarchy depth and by the order they are extended, | |
* mixed in, or implemented. | |
* | |
* For these classes | |
* | |
* class A {} // Depth = 1. | |
* class B {} // Depth = 1. | |
* class C extends B implements A {} // Depth 2. | |
* | |
* the ordered supertypes are | |
* | |
* A: [A, Object] | |
* B: [B, Object] | |
* C: [C, B, A, Object] | |
*/ | |
class OrderedTypeSet { | |
final List<Link<DartType>> _levels; | |
final Link<DartType> types; | |
final Link<DartType> _supertypes; | |
OrderedTypeSet._internal(List<Link<DartType>> this._levels, | |
Link<DartType> this.types, | |
Link<DartType> this._supertypes); | |
factory OrderedTypeSet.singleton(DartType type) { | |
Link<DartType> types = | |
new LinkEntry<DartType>(type, const Link<DartType>()); | |
List<Link<DartType>> list = new List<Link<DartType>>(1); | |
list[0] = types; | |
return new OrderedTypeSet._internal(list, types, const Link<DartType>()); | |
} | |
/// Creates a new [OrderedTypeSet] for [type] when it directly extends the | |
/// class which this set represents. This is for instance used to create the | |
/// type set for [ClosureClassElement] which extends [Closure]. | |
OrderedTypeSet extendClass(InterfaceType type) { | |
assert(type.treatAsRaw); | |
Link<DartType> extendedTypes = | |
new LinkEntry<DartType>(type, types); | |
List<Link<DartType>> list = new List<Link<DartType>>(levels + 1); | |
for (int i = 0; i < levels; i++) { | |
list[i] = _levels[i]; | |
} | |
list[levels] = extendedTypes; | |
return new OrderedTypeSet._internal( | |
list, extendedTypes, _supertypes.prepend(types.head)); | |
} | |
Link<DartType> get supertypes => _supertypes; | |
int get levels => _levels.length; | |
int get maxDepth => levels - 1; | |
Link<DartType> operator [](int index) { | |
if (index < levels) { | |
return _levels[index]; | |
} | |
return const Link<DartType>(); | |
} | |
void forEach(int level, void f(DartType type)) { | |
if (level < levels) { | |
Link<DartType> pointer = _levels[level]; | |
Link<DartType> end = | |
level > 0 ? _levels[level - 1] : const Link<DartType>(); | |
while (!identical(pointer, end)) { | |
f(pointer.head); | |
pointer = pointer.tail; | |
} | |
} | |
} | |
String toString() => types.toString(); | |
} | |
/** | |
* Builder for creation an ordered set of the supertypes of a class. The | |
* supertypes are ordered by decreasing hierarchy depth and by the order they | |
* are extended, mixed in, or implemented. | |
* | |
* For these classes | |
* | |
* class A {} // Depth = 1. | |
* class B {} // Depth = 1. | |
* class C extends B implements A {} // Depth 2. | |
* | |
* the ordered supertypes are | |
* | |
* A: [A, Object] | |
* B: [B, Object] | |
* C: [C, B, A, Object] | |
*/ | |
class OrderedTypeSetBuilder { | |
Map<int, LinkEntry<DartType>> map = new Map<int, LinkEntry<DartType>>(); | |
// TODO(15296): Avoid computing this order on the side when member | |
// lookup handles multiply inherited members correctly. | |
LinkBuilder<DartType> allSupertypes = new LinkBuilder<DartType>(); | |
int maxDepth = -1; | |
final ClassElement cls; | |
OrderedTypeSetBuilder(this.cls); | |
void add(Compiler compiler, InterfaceType type) { | |
if (type.element == cls) { | |
if (type.element != compiler.objectClass) { | |
allSupertypes.addLast(compiler.objectClass.computeType(compiler)); | |
} | |
_addAtDepth(compiler, type, maxDepth + 1); | |
} else { | |
if (type.element != compiler.objectClass) { | |
allSupertypes.addLast(type); | |
} | |
_addAtDepth(compiler, type, type.element.hierarchyDepth); | |
} | |
} | |
void _addAtDepth(Compiler compiler, InterfaceType type, int depth) { | |
LinkEntry<DartType> prev = null; | |
LinkEntry<DartType> link = map[depth]; | |
while (link != null) { | |
DartType existingType = link.head; | |
if (existingType == type) return; | |
if (existingType.element == type.element) { | |
compiler.reportError(cls, | |
MessageKind.MULTI_INHERITANCE, | |
{'thisType': cls.computeType(compiler), | |
'firstType': existingType, | |
'secondType': type}); | |
return; | |
} | |
prev = link; | |
link = link.tail; | |
} | |
LinkEntry<DartType> next = new LinkEntry<DartType>(type); | |
next.tail = null; | |
if (prev == null) { | |
map[depth] = next; | |
} else { | |
prev.tail = next; | |
} | |
if (depth > maxDepth) { | |
maxDepth = depth; | |
} | |
} | |
OrderedTypeSet toTypeSet() { | |
List<Link<DartType>> levels = new List<Link<DartType>>(maxDepth + 1); | |
if (maxDepth < 0) { | |
return new OrderedTypeSet._internal( | |
levels, const Link<DartType>(), const Link<DartType>()); | |
} | |
Link<DartType> next = const Link<DartType>(); | |
for (int depth = 0; depth <= maxDepth; depth++) { | |
LinkEntry<DartType> first = map[depth]; | |
if (first == null) { | |
levels[depth] = next; | |
} else { | |
levels[depth] = first; | |
LinkEntry<DartType> last = first; | |
while (last.tail != null) { | |
last = last.tail; | |
} | |
last.tail = next; | |
next = first; | |
} | |
} | |
return new OrderedTypeSet._internal( | |
levels, levels.last, allSupertypes.toLink()); | |
} | |
String toString() { | |
StringBuffer sb = new StringBuffer(); | |
for (int depth = 0; depth <= maxDepth; depth++) { | |
sb.write('$depth: '); | |
LinkEntry<DartType> first = map[depth]; | |
if (first != null) { | |
sb.write('${first.head}'); | |
while (first.tail != null) { | |
sb.write(', ${first.tail.head}'); | |
first = first.tail; | |
} | |
} | |
sb.write('\n'); | |
} | |
return sb.toString(); | |
} | |
} |