| // Copyright (c) 2013, 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 ordered_typeset; |
| |
| import 'dart2jslib.dart' show Compiler, MessageKind, invariant; |
| 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(invariant(type.element, types.head.treatAsRaw, |
| message: 'Cannot extend generic class ${types.head} using ' |
| 'OrderedTypeSet.extendClass')); |
| 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; |
| } |
| } |
| } |
| |
| InterfaceType asInstanceOf(ClassElement cls) { |
| int level = cls.hierarchyDepth; |
| if (level < levels) { |
| Link<DartType> pointer = _levels[level]; |
| Link<DartType> end = |
| level > 0 ? _levels[level - 1] : const Link<DartType>(); |
| while (!identical(pointer, end)) { |
| if (cls == pointer.head.element) { |
| return pointer.head; |
| } |
| pointer = pointer.tail; |
| } |
| } |
| return null; |
| } |
| |
| 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.rawType); |
| } |
| _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.thisType, |
| '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(); |
| } |
| } |