Index: sdk/lib/_internal/compiler/implementation/ordered_typeset.dart |
diff --git a/sdk/lib/_internal/compiler/implementation/ordered_typeset.dart b/sdk/lib/_internal/compiler/implementation/ordered_typeset.dart |
new file mode 100644 |
index 0000000000000000000000000000000000000000..6a68357336bf3a31f4d586e38d4f642a0e1f68ef |
--- /dev/null |
+++ b/sdk/lib/_internal/compiler/implementation/ordered_typeset.dart |
@@ -0,0 +1,203 @@ |
+// 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(); |
+ } |
+} |