Observatory: Add view of dominator tree with siblings merged by class.

runtime/observatory/lib/object_graph.dart

Index: runtime/observatory/lib/object_graph.dart
diff --git a/runtime/observatory/lib/object_graph.dart b/runtime/observatory/lib/object_graph.dart
index c2b4169e7d8cbf6ba61e2647b57ec074b0eb8fdd..33a727aea258ff17d8db55190a2bf0fecf903620 100644
--- a/runtime/observatory/lib/object_graph.dart
+++ b/runtime/observatory/lib/object_graph.dart
@@ -282,6 +282,75 @@ class ObjectVertex {
   }
 }
 
+
+class MergedObjectVertex {

[Cutch, 2016/11/14 17:24:13]

Doc comment explaining what this represents at a high level, for example:

A dominator tree of objects where sibling nodes with the same class are
collapsed / merged.

This class needs to implement ObjectVertex.

[rmacnak, 2016/11/15 00:44:15]

Added comment. This class does *not* implement ObjectVertex.

+  // 0 represents invalid/uninitialized, 1 is the root.

[Cutch, 2016/11/14 17:24:13]

Let's use a constant for 0 where you mean the invalid node sentinel.

const int invalidNodeIndex = 0;
const int rootNodeIndex = 1;

(here and elsewhere)

+  final int _id;
+  final ObjectGraph _graph;
+
+  MergedObjectVertex._(this._id, this._graph);
+
+  bool get isRoot => _id == 1;
+
+  bool operator ==(other) => _id == other._id && _graph == other._graph;
+  int get hashCode => _id;
+
+  int get vmCid => _graph._cids[_id];
+
+  int get shallowSize {
+    var cids = _graph._cids;
+    var size = 0;
+    var sibling = _id;
+    while (sibling != 0 &&
+           cids[sibling] == cids[_id]) {
+      size += _graph._shallowSizes[sibling];
+      sibling = _graph._mergedDomNext[sibling];
+    }
+    return size;
+  }
+  int get retainedSize {
+    var cids = _graph._cids;
+    var size = 0;
+    var sibling = _id;
+    while (sibling != 0 &&

[Cutch, 2016/11/14 17:24:13]

here and elsewhere != invalidNodeIndex

+           cids[sibling] == cids[_id]) {
+      size += _graph._retainedSizes[sibling];
+      sibling = _graph._mergedDomNext[sibling];
+    }
+    return size;
+  }
+  int get instanceCount {
+    var cids = _graph._cids;
+    var count = 0;
+    var sibling = _id;
+    while (sibling != 0 &&
+           cids[sibling] == cids[_id]) {
+      count++;
+      sibling = _graph._mergedDomNext[sibling];
+    }
+    return count;
+  }
+
+  List<ObjectVertex> dominatorTreeChildren() {
+    var next = _graph._mergedDomNext;
+    var cids = _graph._cids;
+
+    var domChildren = [];
+    var prev = 0;
+    var child = _graph._mergedDomHead[_id];
+    while (child != 0) {

[Cutch, 2016/11/14 17:24:13]

Scan the list of siblings, creating MergedObjectVertex nodes whenever the class
id changes. 

This code ensures that the child index is the head of sibling list for that
given class id.

[rmacnak, 2016/11/15 00:44:15]

Done.

+      if (prev == 0 ||
+          cids[prev] != cids[child]) {
+        domChildren.add(new MergedObjectVertex._(child, _graph));
+      }
+      prev = child;
+      child = next[child];
+    }
+
+    return domChildren;
+  }
+}
+
 class _SuccessorsIterable extends IterableBase<ObjectVertex> {
   final ObjectGraph _graph;
   final int _id;
@@ -346,6 +415,7 @@ class ObjectGraph {
   int get edgeCount => _E;
 
   ObjectVertex get root => new ObjectVertex._(1, this);
+  MergedObjectVertex get mergedRoot => new MergedObjectVertex._(1, this);
   Iterable<ObjectVertex> get vertices => new _VerticesIterable(this);
 
   Iterable<ObjectVertex> getMostRetained({int classId, int limit}) {
@@ -381,10 +451,10 @@ class ObjectGraph {
       controller.add(["Finding depth-first order...", 30.0]);
       await new Future(() => _dfs());
 
-      controller.add(["Finding predecessors...", 45.0]);
+      controller.add(["Finding predecessors...", 40.0]);
       await new Future(() => _buildPredecessors());
 
-      controller.add(["Finding dominators...", 60.0]);
+      controller.add(["Finding dominators...", 50.0]);
       await new Future(() => _buildDominators());
 
       _firstPreds = null;
@@ -393,12 +463,21 @@ class ObjectGraph {
       _semi = null;
       _parent = null;
 
-      controller.add(["Finding retained sizes...", 75.0]);
+      controller.add(["Finding retained sizes...", 60.0]);
       await new Future(() => _calculateRetainedSizes());
 
       _vertex = null;
 
-      controller.add(["Loaded", 100.0]);
+      controller.add(["Linking dominator tree children...", 70.0]);
+      await new Future(() => _linkDominatorChildren());
+
+      controller.add(["Sorting dominator tree children...", 80.0]);
+      await new Future(() => _sortDominatorChildren());
+
+      controller.add(["Merging dominator tree siblings...", 90.0]);
+      await new Future(() => _mergeDominatorSiblings());
+
+      controller.add(["Processed", 100.0]);
       controller.close();
     }());
     return controller.stream;
@@ -431,6 +510,8 @@ class ObjectGraph {
   // Outputs.
   Uint32List _doms;
   Uint32List _retainedSizes;
+  Uint32List _mergedDomHead;
+  Uint32List _mergedDomNext;
 
   void _remapNodes() {
     var N = _N;
@@ -812,4 +893,150 @@ class ObjectGraph {
     _retainedSizes = retainedSizes;
     _size = size;
   }
+
+  void _linkDominatorChildren() {

[Cutch, 2016/11/14 17:24:13]

// Build a set of linked lists of children dominated by common parents.

+    var N = _N;

[Cutch, 2016/11/14 17:24:13]

Let's start typing local variables ....

[rmacnak, 2016/11/15 00:44:15]

Not while we can still write Dart.

+    var doms = _doms;
+    var head = new Uint32List(N + 1);

[Cutch, 2016/11/14 17:24:13]

We need to start commenting at a high level what is being computed. For example:

// The head of a linked list containing all nodes dominated by the same parent
node. Indexed by node id.

+    var next = new Uint32List(N + 1);
+
+    for (var child = 1; child <= N; child++) {
+      var parent = doms[child];
+      next[child] = head[parent];
+      head[parent] = child;
+    }
+
+    _mergedDomHead = head;
+    _mergedDomNext = next;
+  }
+
+  static int _mergeSorted(int head1, int head2,
+                          Uint32List next, Uint16List key) {
+    var head = head1;
+    var beforeInsert = 0;
+    var afterInsert = head1;
+    var startInsert = head2;
+
+    while (startInsert != 0) {
+      while ((afterInsert != 0) &&
+             (key[afterInsert] <= key[startInsert])) {
+        beforeInsert = afterInsert;
+        afterInsert = next[beforeInsert];
+      }
+
+      var endInsert = startInsert;
+      var peek = next[endInsert];
+
+      while ((peek != 0) && (key[peek] < key[afterInsert])) {
+        endInsert = peek;
+        peek = next[endInsert];
+      }
+      assert(endInsert != 0);
+
+      if (beforeInsert == 0) {
+        head = startInsert;
+      } else {
+        next[beforeInsert] = startInsert;
+      }
+      next[endInsert] = afterInsert;
+
+      startInsert = peek;
+      beforeInsert = endInsert;
+    }
+
+    return head;
+  }
+
+  void _sortDominatorChildren() {
+    var N = _N;
+    var cids = _cids;
+    var head = _mergedDomHead;
+    var next = _mergedDomNext;
+
+    int sort(int head) {

[Cutch, 2016/11/14 17:24:13]

/// Returns the first node index in the list after being sorted.

+      if (head == 0) return 0;

[Cutch, 2016/11/14 17:24:13]

... == invalidNodeIndex) {
  return invalidNodeIndex;
}

+      if (next[head] == 0) return head;
+

[Cutch, 2016/11/14 17:24:13]

// Determine the mid and end point of the list by walking two cursors down the
list in parallel. The first, 'slow', walks 1 node per iteration and 'fast' walks
2 nodes per iteration. When 'fast' hits the end of the list, 'slow' will be at
the middle.

+      int head1 = head;
+      int slow = head;
+      int fast = head;
+      while (next[fast] != 0 &&
+             next[next[fast]] != 0) {
+        slow = next[slow];
+        fast = next[next[fast]];
+      }
+
+      int head2 = next[slow];

[Cutch, 2016/11/14 17:24:13]

// Split the list in half.

+      next[slow] = 0;
+
+      assert(head1 != head2);
+      int newHead1 = sort(head1);

[Cutch, 2016/11/14 17:24:13]

Recursively sort each of the sublists

+      int newHead2 = sort(head2);
+      return _mergeSorted(newHead1, newHead2, next, cids);

[Cutch, 2016/11/14 17:24:13]

Merge them

+    }
+
+    for (var parent = 1; parent <= N; parent++) {

[Cutch, 2016/11/14 17:24:13]

Sort all of the merged dominator sibling lists so that siblings with a common
class id are next to each other.

+      head[parent] = sort(head[parent]);
+    }
+  }
+
+  void _mergeDominatorSiblings() {
+    var N = _N;
+    var cids = _cids;
+    var head = _mergedDomHead;
+    var next = _mergedDomNext;
+    var workStack = new Uint32List(N);
+    var workStackTop = 0;
+
+    mergeChildrenAndSort(var parent1, var end) {
+      assert(parent1 != 0);
+      if (next[parent1] == end) return;
+
+      int cid = cids[parent1];
+      int slow = parent1;
+      int fast = parent1;
+      while (next[fast] != end &&
+             next[next[fast]] != end) {

[Cutch, 2016/11/14 17:24:13]

this should be factored out and reused with the code above. maybe return a list
[mid, end]

+        slow = next[slow];
+        fast = next[next[fast]];
+      }
+
+      int parent2 = next[slow];
+
+      assert(parent2 != 0);
+      assert(parent1 != parent2);
+      assert(cids[parent1] == cids[parent2]);
+
+      mergeChildrenAndSort(parent1, parent2);
+      mergeChildrenAndSort(parent2, end);
+
+      head[parent1] = _mergeSorted(head[parent1], head[parent2], next, cids);
+      head[parent2] = 0;

[Cutch, 2016/11/14 17:24:12]

// We have merged the siblings of parent2 into parent1. Clear out the linked
list for parent 2.

+    }
+
+    // Push root.
+    workStack[workStackTop++] = 1;
+
+    while (workStackTop > 0) {
+      var parent = workStack[--workStackTop];
+
+      var prev = 0;
+      var child = head[parent];
+      while (child != 0) {
+        // Push child.
+        workStack[workStackTop++] = child;
+
+        // Next sibling with a different cid.
+        var after = child;
+        while (after != 0 &&
+               cids[after] == cids[child]) {
+          after = next[after];
+        }
+
+        mergeChildrenAndSort(child, after);

[Cutch, 2016/11/14 17:24:13]

// child is the first node with cid A and after is the node just 'after' the
last node with cid A.
// collapse / merge all the nodes between child and after into child.

+
+        child = after;
+      }
+    }
+  }
 }