Add SubclassNode to prepare for optimized queries on ClassWorld.

pkg/compiler/lib/src/universe/class_set.dart

Index: pkg/compiler/lib/src/universe/class_set.dart
diff --git a/pkg/compiler/lib/src/universe/class_set.dart b/pkg/compiler/lib/src/universe/class_set.dart
new file mode 100644
index 0000000000000000000000000000000000000000..1f90c9c7140cb3f9ba2b5862ff5d24620aafd972
--- /dev/null
+++ b/pkg/compiler/lib/src/universe/class_set.dart
@@ -0,0 +1,177 @@
+// Copyright (c) 2015, 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 dart2js.world.class_set;
+
+import 'dart:collection' show IterableBase;
+import '../elements/elements.dart' show ClassElement;
+import '../util/util.dart' show Link;
+
+/// Node for [cls] in a tree forming the subclass relation of [ClassElement]s.
+///
+/// This is used by the [ClassWorld] to perform queries on subclass and subtype
+/// relations.
+// TODO(johnniwinther): Use this for `ClassWorld.subtypesOf`.
+class SubclassNode {

[Siggi Cherem (dart-lang), 2015/07/14 23:51:07]

This is a hard one name :) - Somehow SubclassNode sounds to me a bit like this
is a node representing a subclass.

A possible idea is to use the term "class hierarchy tree" to refer to the
subclass relation, so we could use: ClassHierarchyNode or
ClassHierarchyTreeNode. thoughts?

Similarly - maybe rename the file and library name from class_set to
class_hierarchy?

[Johnni Winther, 2015/07/15 08:55:08]

ClassHierarchyNode or ClassHierarchyTreeNode it is. The filename is in
anticipation that it'll contains Set-like classes for subclass and subtype
relations build upon ClassHierarchy(Tree)Node.

[Johnni Winther, 2015/07/21 12:11:01]

Done.

+  final ClassElement cls;
+
+  /// `true` if [cls] has been directly instantiated.
+  ///
+  /// For instance `C` but _not_ `B` in:
+  ///   class B {}
+  ///   class C extends B {}
+  ///   main() => new C();
+  ///
+  bool isDirectlyInstantiated = false;
+
+  /// `true` if [cls] has been instantiated through subclasses.
+  ///
+  /// For instance `B` and `C` but _not_ `A` in:

[Siggi Cherem (dart-lang), 2015/07/14 23:51:07]

I was expecting `A` would be true in this case (since B & C extend from it)?

Or did you mean to have the following code instead?

  class A {}
  class B {} // no extends A
  class C extends B {}
  main() => new C();

[Johnni Winther, 2015/07/15 08:55:08]

It should have been: `A` and `B` but _not_ `C`

[Johnni Winther, 2015/07/21 12:11:00]

Done.

+  ///   class A {}
+  ///   class B extends A {}
+  ///   class C extends B {}
+  ///   main() => [new B(), new C()];
+  ///
+  bool isIndirectlyInstantiated = false;
+
+  /// The node for the direct subclasses of [cls].
+  Link<SubclassNode> _directSubclasses = const Link<SubclassNode>();
+
+  SubclassNode(this.cls);
+
+  /// Adds [subclass] as a direct subclass of [cls].
+  void addDirectSubclass(SubclassNode subclass) {
+    assert(subclass.cls.superclass == cls);
+    assert(!_directSubclasses.contains(subclass));
+    _directSubclasses = _directSubclasses.prepend(subclass);
+  }
+
+  /// The nodes for the direct subclasses of [cls].
+  Link<SubclassNode> get directSubclasses => _directSubclasses;
+
+  /// `true` if [cls] has any direct subclasses.
+  bool get hasDirectSubclasses => !_directSubclasses.isEmpty;
+
+  /// `true` if [cls] has been directly or indirectly instantiated.
+  bool get isInstantiated => isDirectlyInstantiated || isIndirectlyInstantiated;
+
+  /// Returns an [Iterable] of the subclasses of [cls] possibly including [cls].
+  /// If [directlyInstantiated] is `true`, the iterable only returns the
+  /// directly instantiated subclasses of [cls].
+  Iterable<ClassElement> subclasses({bool directlyInstantiated: true}) {
+    return new SubclassNodeIterable(
+        this, directlyInstantiatedOnly: directlyInstantiated);
+  }
+
+  /// Returns an [Iterable] of the strict subclasses of [cls] _not_ including
+  /// [cls] itself. If [directlyInstantiated] is `true`, the iterable only
+  /// returns the directly instantiated subclasses of [cls].
+  Iterable<ClassElement> strictSubclasses(
+      {bool directlyInstantiated: true}) {
+    return new SubclassNodeIterable(this,
+        includeRoot: false, directlyInstantiatedOnly: directlyInstantiated);
+  }
+
+  String toString() => cls.toString();
+}
+
+/// Iterable for subclasses of a [SubclassNode].
+class SubclassNodeIterable extends IterableBase<ClassElement> {
+  final SubclassNode root;
+  final bool includeRoot;
+  final bool directlyInstantiatedOnly;
+
+  SubclassNodeIterable(
+      this.root,
+      {this.includeRoot: true,
+       this.directlyInstantiatedOnly: false});
+
+  @override
+  Iterator<ClassElement> get iterator {
+    return new SubclassNodeIterator(this);
+  }
+}
+
+/// Iterator for subclasses of a [SubclassNode].

[Siggi Cherem (dart-lang), 2015/07/14 23:51:07]

it might be worth mentioning here or in the sublasses functions above that the
iterable will return the classes in a DFS fashion in pre-order (top-down
depth-first).

BTW - I wonder if there is an order that makes more sense for our algorithms, or
if we want to introduce more than one order? (would some order let us stop
iterating earlier?)

[Johnni Winther, 2015/07/15 08:55:08]

The iterator is an intermediate step towards the intended solution: Currently we
use strictSubclassesOf and strictSubtypesOf which return Iterable. 

This class for providing such functionality. Long-term users of ClassWorld
should not have access to such brute-force iteration through classes but more
high level function that choose the order and terminate based on the intention
of the query. 

For instance, for computing whether a  noSuchMethod stub is needed for a method
on a type-mask we run through all classes (using strictSubclassesOf or
strictSubtypesOf, depending on the maks) and for each run up the superclass
chain to determinate if that class need a stub for the method. This means that
we for instance test Object once for each class in the iterable. What we should
do instead is to run through superclasses first and skip subtrees when a method
is found. For instance checking the need for a noSuchMethod stub for 'toString'
will then only require a check on Object and nothing more.

+class SubclassNodeIterator implements Iterator<ClassElement> {
+  final SubclassNodeIterable iterable;
+
+  /// The class node holding the [current] class.
+  ///
+  /// This is `null` before the first call to [moveNext] and at the end of
+  /// iteration, i.e. after [moveNext] has returned `false`.
+  SubclassNode currentNode;
+
+  /// Stack of list of pending class nodes.
+  ///
+  /// This is `null` before the first call to [moveNext].
+  Link<Link<SubclassNode>> stack;
+
+  SubclassNodeIterator(this.iterable);
+
+  SubclassNode get root => iterable.root;
+
+  bool get includeRoot => iterable.includeRoot;
+
+  bool get directlyInstantiatedOnly => iterable.directlyInstantiatedOnly;
+
+  @override
+  ClassElement get current {
+    return currentNode != null ? currentNode.cls : null;
+  }
+
+  @override
+  bool moveNext() {
+    if (stack == null) {
+      // Uninitialized state.
+      stack = const Link<Link<SubclassNode>>();
+      currentNode = root;
+      if (currentNode.hasDirectSubclasses) {

[Siggi Cherem (dart-lang), 2015/07/14 23:51:07]

it would be nice to only have this part of the logic that uses
`directSubclasses` in a single place. How about making moveNext only initialize
the stack with `root` and let _findNext add the rest?

For example:

bool moveNext() {
  if (stack == null) {
    // first call to moveNext
    if (root == null) return false;
    var pending = const Link<SubclassNode>().prepend(root);
    stack = (const Link<...>()).prepend(pending);
  }
  return _findNext();
}

[Johnni Winther, 2015/07/15 08:55:09]

Good idea!

[Johnni Winther, 2015/07/21 12:11:00]

Done.

+        stack = stack.prepend(currentNode.directSubclasses);
+      }
+      if (isValid(currentNode)) {
+        return true;
+      }
+      return findNext();
+    } else {
+      // Initialized state.
+      if (currentNode == null) return false;
+      return findNext();
+    }
+  }
+
+  /// Find the next class using the [stack].
+  bool findNext() {

[Siggi Cherem (dart-lang), 2015/07/14 23:51:07]

make private?

[Johnni Winther, 2015/07/21 12:11:00]

Done.

+    while (true) {
+      if (stack.isEmpty) {
+        // No more classes. Set [currentNode] to `null` to signal the end of
+        // iteration.
+        currentNode = null;
+        return false;
+      }
+      Link<SubclassNode> pending = stack.head;
+      stack = stack.tail;
+      currentNode = pending.head;
+      pending = pending.tail;
+      if (!pending.isEmpty) {
+        stack = stack.prepend(pending);
+      }
+      if (currentNode.hasDirectSubclasses) {
+        stack = stack.prepend(currentNode.directSubclasses);

[Siggi Cherem (dart-lang), 2015/07/14 23:51:07]

What do you think about flattening the list here (keep a stack of nodes, rather
than a stack with lists of nodes)?

It would probably make the iterator invariant a bit simpler, and it seems the
cost is very similar to the current algorithm:

- current algorithm: 1 operation to append children, 2 * n operations later (1
to pop the a child, and 1 push back the pending children)

- w/flattening: n operations upfront to append children, n operations later (1
to pop each child)

where `n` is just the number of directSubclasses on a node (not the total number
of descendants)

[Johnni Winther, 2015/07/15 08:55:08]

I'll give it a try.

[Johnni Winther, 2015/07/21 12:11:00]

Done.

+      }
+      if (isValid(currentNode)) {
+        return true;
+      }
+    }
+  }
+
+  /// Returns `true` if the class of [node] is a valid result for this iterator.
+  bool isValid(SubclassNode node) {

[Siggi Cherem (dart-lang), 2015/07/14 23:51:07]

make private too?

[Johnni Winther, 2015/07/15 08:55:08]

Will do.

[Johnni Winther, 2015/07/21 12:11:00]

Done.

+    if (!includeRoot && node == root) return false;
+    if (directlyInstantiatedOnly && !node.isDirectlyInstantiated) return false;
+    return true;
+  }
+}
+
+