Implement least upper bound.

sdk/lib/_internal/compiler/implementation/ordered_typeset.dart

+// 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 {

[karlklose, 2013/11/21 13:29:10]

Where do you enforce that this really is a set? Is that guaranteed by using the
builder?

[Johnni Winther, 2013/11/25 13:58:27]

Yes. Made the default constructor private to further enforce this.

+  final List<Link<DartType>> _levels;
+  final Link<DartType> _head;

[karlklose, 2013/11/21 13:29:10]

What is this used for? Can you find a better name?

[Johnni Winther, 2013/11/25 13:58:27]

It holds the list of the types. Renamed to types (replacing the getter).

+  final Link<DartType> _supertypes;
+
+  OrderedTypeSet(List<Link<DartType>> this._levels,
+                 Link<DartType> this._head,
+                 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(list, types, const Link<DartType>());
+  }
+
+  OrderedTypeSet extendClass(InterfaceType type) {

[karlklose, 2013/11/21 13:29:10]

Please add a comment explaining what this method does.

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+    assert(type.treatAsRaw);
+    Link<DartType> types =
+        new LinkEntry<DartType>(type, _head);
+    List<Link<DartType>> list = new List<Link<DartType>>(levels+1);

[karlklose, 2013/11/21 13:29:10]

Missing spaces around operator 'levels_+_1'.

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+    for (int i = 0 ; i < levels ; i++) {

[karlklose, 2013/11/21 13:29:10]

No space before ';'.

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+      list[i] = _levels[i];
+    }
+    list[levels] = types;
+    return new OrderedTypeSet(list, types, _supertypes.prepend(_head.head));
+  }
+
+

[karlklose, 2013/11/21 13:29:10]

Remove empty line.

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+  Link<DartType> get types => _head;
+
+  Link<DartType> get supertypes => _supertypes;
+
+  int get levels => _levels.length;
+
+  int get maxDepth => levels-1;

[karlklose, 2013/11/21 13:29:10]

Missing spaces around operator.

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+
+  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>();

[karlklose, 2013/11/21 13:29:10]

Ditto.

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+      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(johnniwinther): 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);

[karlklose, 2013/11/21 13:29:10]

Spaces around operator.

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+    } 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> head = map[depth];

[karlklose, 2013/11/21 13:29:10]

Is [head] used somewhere else than in l. 135?  If not, inline it at use site.

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+    LinkEntry<DartType> prev = null;
+    LinkEntry<DartType> link = head;
+    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 toSet() {

[karlklose, 2013/11/21 13:29:10]

toSet -> toTypeSet?

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+    List<Link<DartType>> levels = new List<Link<DartType>>(maxDepth+1);

[karlklose, 2013/11/21 13:29:10]

Spaces.

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+    if (maxDepth < 0) {
+      return new OrderedTypeSet(
+          levels, const Link<DartType>(), const Link<DartType>());
+    }
+    Link<DartType> next = const Link<DartType>();
+    for (int depth = 0 ; depth <= maxDepth ; depth++) {

[karlklose, 2013/11/21 13:29:10]

No spaces before ';'.

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+      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(levels, levels.last, allSupertypes.toLink());
+  }
+
+  String toString() {
+    StringBuffer sb = new StringBuffer();
+    for (int depth = 0 ; depth <= maxDepth ; depth++) {

[karlklose, 2013/11/21 13:29:10]

Ditto.

[Johnni Winther, 2013/11/25 13:58:27]

Done.

+      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();
+  }
+}