CPU profile displayed in three tables with a tree

runtime/observatory/lib/src/cpu_profile/cpu_profile.dart

Index: runtime/observatory/lib/src/cpu_profile/cpu_profile.dart
diff --git a/runtime/observatory/lib/src/cpu_profile/cpu_profile.dart b/runtime/observatory/lib/src/cpu_profile/cpu_profile.dart
index 359117128c674a4ef626cfa580dd5d2fa0209996..4393b1299c6ae19f045fc74ef8a3e6b55679612f 100644
--- a/runtime/observatory/lib/src/cpu_profile/cpu_profile.dart
+++ b/runtime/observatory/lib/src/cpu_profile/cpu_profile.dart
@@ -41,6 +41,24 @@ class CodeCallTree {
       _setCodePercentage(node, child);
     }
   }
+
+  _markCodeCallsInner(CodeCallTreeNode caller,
+                      CodeCallTreeNode callee) {
+    if (caller != null) {
+      caller.profileCode._noteCallee(callee.profileCode, callee.count);
+      callee.profileCode._noteCaller(caller.profileCode, callee.count);
+    }
+
+    for (var child in callee.children) {
+      _markCodeCallsInner(callee, child);
+    }
+  }
+
+  _markCodeCalls() {

[turnidge, 2015/04/07 21:24:31]

What does "marking" mean here?  Is there another name for this?  Maybe
"SetCallCounts" or maybe "RecordCalls".

BTW, What do you think of this class being named "CallTree" instead of
"CodeCallTree"?

[Cutch, 2015/04/14 21:45:15]

Went with _recordCallerAndCallees.

The class is named CodeCallTree because there is also a FunctionCallTree (Code
vs. Function).

+    for (var child in root.children) {
+      _markCodeCallsInner(null, child);
+    }
+  }
 }
 
 class FunctionCallTreeNodeCode {
@@ -129,6 +147,108 @@ class FunctionCallTreeNode {
   }
 }
 
+typedef bool FunctionCallTreeNodeFilter(FunctionCallTreeNode node);
+
+class _FilteredTreeBuilder {

[turnidge, 2015/04/07 21:24:31]

Can you make some of the functions in this class private so I can tell which
ones are external entry points?  Maybe add some one-line comments on the
functions too.

[Cutch, 2015/04/14 21:45:15]

Done.

+  final FunctionCallTreeNodeFilter filter;
+  final FunctionCallTree tree;
+  final FunctionCallTree filtered;
+  final List currentPath = [];
+
+  _FilteredTreeBuilder(this.filter, FunctionCallTree tree)
+      : tree = tree,
+        filtered =
+          new FunctionCallTree(
+              tree.inclusive,
+              new FunctionCallTreeNode(
+                  tree.root.profileFunction,
+                  tree.root.count));
+
+  FunctionCallTreeNode findFunctionInChildren(FunctionCallTreeNode current,
+                                              FunctionCallTreeNode needle) {
+    for (var child in current.children) {
+      if (child.profileFunction == needle.profileFunction) {
+        return child;
+      }
+    }
+    return null;
+  }
+
+  FunctionCallTreeNode addCurrentPath() {
+    FunctionCallTreeNode current = filtered.root;
+    // Tree root is always the first element of the current path.
+    assert(tree.root == currentPath[0]);
+    // Assert that tree and filtered are different.
+    assert(tree.root != current);
+    for (var i = 1; i < currentPath.length; i++) {
+      var toAdd = currentPath[i];
+      var child = findFunctionInChildren(current, toAdd);
+      if (child == null) {
+        child = new FunctionCallTreeNode(toAdd.profileFunction, toAdd.count);
+        current.children.add(child);
+      }
+      current = child;
+      assert(current.count == toAdd.count);
+    }
+    return current;
+  }
+
+  appendTree(FunctionCallTreeNode current, FunctionCallTreeNode next) {
+    if (next == null) {
+      return;
+    }
+    var child = findFunctionInChildren(current, next);
+    if (child == null) {
+      child = new FunctionCallTreeNode(next.profileFunction, next.count);
+      current.children.add(child);
+    }
+    current = child;
+    for (var nextChild in next.children) {
+      appendTree(current, nextChild);
+    }
+  }
+
+  addTree(FunctionCallTreeNode child) {
+    var current = addCurrentPath();
+    appendTree(current, child);
+  }
+
+  descend(FunctionCallTreeNode current) {
+    if (current == null) {
+      return;
+    }
+    currentPath.add(current);
+
+    if (filter(current)) {
+      // Filter matched.
+      if (current.children.length == 0) {
+        // Have no children. Add this path.
+        addTree(null);
+      } else {
+        // Add all child trees.
+        for (var child in current.children) {
+          addTree(child);
+        }
+      }
+    } else {
+      // Did not match, descend to each child.
+      for (var child in current.children) {
+        descend(child);
+      }
+    }
+
+    var last = currentPath.removeLast();
+    assert(current == last);
+  }
+
+  build() {
+    assert(filtered != null);
+    assert(filter != null);
+    assert(tree != null);
+    descend(tree.root);
+  }
+}
+
 class FunctionCallTree {
   final bool inclusive;
   final FunctionCallTreeNode root;
@@ -136,6 +256,13 @@ class FunctionCallTree {
     _setFunctionPercentage(null, root);
   }
 
+  FunctionCallTree filtered(FunctionCallTreeNodeFilter filter) {
+    var treeFilter = new _FilteredTreeBuilder(filter, this);
+    treeFilter.build();
+    _setFunctionPercentage(null, treeFilter.filtered.root);
+    return treeFilter.filtered;
+  }
+
   void _setFunctionPercentage(FunctionCallTreeNode parent,
                               FunctionCallTreeNode node) {
     assert(node != null);
@@ -154,6 +281,23 @@ class FunctionCallTree {
       _setFunctionPercentage(node, child);
     }
   }
+
+  _markFunctionCallsInner(FunctionCallTreeNode caller,
+                     FunctionCallTreeNode callee) {
+    if (caller != null) {
+      caller.profileFunction._noteCallee(callee.profileFunction, callee.count);
+      callee.profileFunction._noteCaller(caller.profileFunction, callee.count);
+    }
+    for (var child in callee.children) {
+      _markFunctionCallsInner(callee, child);
+    }
+  }
+
+  _markFunctionCalls() {
+    for (var child in root.children) {
+      _markFunctionCallsInner(null, child);
+    }
+  }
 }
 
 class CodeTick {
@@ -186,6 +330,8 @@ class ProfileCode {
   String formattedCpuTime = '';
   String formattedOnStackTime = '';
   final Set<String> attributes = new Set<String>();
+  final Map<ProfileCode, int> callers = new Map<ProfileCode, int>();
+  final Map<ProfileCode, int> callees = new Map<ProfileCode, int>();
 
   void _processTicks(List<String> profileTicks) {
     assert(profileTicks != null);
@@ -262,6 +408,22 @@ class ProfileCode {
       '${Utils.formatPercent(exclusiveTicks, profile.sampleCount)} '
       '($exclusiveTicks)';
   }
+
+  _noteCaller(ProfileCode caller, int count) {

[turnidge, 2015/04/07 21:24:31]

Maybe _addCaller and _addCallee?

[Cutch, 2015/04/14 21:45:15]

Done.

+    var r = callers[caller];
+    if (r == null) {
+      r = 0;
+    }
+    callers[caller] = r + count;
+  }
+
+  _noteCallee(ProfileCode callee, int count) {
+    var r = callees[callee];
+    if (r == null) {
+      r = 0;
+    }
+    callees[callee] = r + count;
+  }
 }
 
 class ProfileFunction {
@@ -269,6 +431,9 @@ class ProfileFunction {
   final ServiceFunction function;
   // List of compiled code objects containing this function.
   final List<ProfileCode> profileCodes = new List<ProfileCode>();
+  final Map<ProfileFunction, int> callers = new Map<ProfileFunction, int>();
+  final Map<ProfileFunction, int> callees = new Map<ProfileFunction, int>();
+
   // Absolute ticks:
   int exclusiveTicks = 0;
   int inclusiveTicks = 0;
@@ -356,6 +521,7 @@ class ProfileFunction {
   }
 
   ProfileFunction.fromMap(this.profile, this.function, Map data) {
+    function.profile = this;
     for (var codeIndex in data['codes']) {
       var profileCode = profile.codes[codeIndex];
       profileCodes.add(profileCode);
@@ -397,6 +563,22 @@ class ProfileFunction {
         '${Utils.formatPercent(exclusiveTicks, profile.sampleCount)} '
         '($exclusiveTicks)';
   }
+
+  _noteCaller(ProfileFunction caller, int count) {
+    var r = callers[caller];
+    if (r == null) {
+      r = 0;
+    }
+    callers[caller] = r + count;
+  }
+
+  _noteCallee(ProfileFunction callee, int count) {
+    var r = callees[callee];
+    if (r == null) {
+      r = 0;
+    }
+    callees[callee] = r + count;
+  }
 }
 
 
@@ -416,7 +598,9 @@ class CpuProfile {
 
   final Map<String, List> tries = <String, List>{};
   final List<ProfileCode> codes = new List<ProfileCode>();
+  bool _markedCodeCalls = false;
   final List<ProfileFunction> functions = new List<ProfileFunction>();
+  bool _markedFunctionCalls = false;
 
   CodeCallTree loadCodeTree(String name) {
     if (name == 'inclusive') {
@@ -434,7 +618,25 @@ class CpuProfile {
     }
   }
 
-  void clear() {
+  markCodeCalls() {
+    if (_markedCodeCalls) {
+      return;
+    }
+    _markedCodeCalls = true;
+    var tree = loadCodeTree('inclusive');
+    tree._markCodeCalls();
+  }
+
+  markFunctionCalls() {
+    if (_markedFunctionCalls) {
+      return;
+    }
+    _markedFunctionCalls = true;
+    var tree = loadFunctionTree('inclusive');
+    tree._markFunctionCalls();
+  }
+
+  clear() {
     sampleCount = 0;
     samplePeriod = 0;
     sampleRate = 0.0;
@@ -443,9 +645,11 @@ class CpuProfile {
     codes.clear();
     functions.clear();
     tries.clear();
+    _markedCodeCalls = false;
+    _markedFunctionCalls = false;
   }
 
-  void load(Isolate isolate, ServiceMap profile) {
+  load(Isolate isolate, ServiceMap profile) {
     clear();
     if ((isolate == null) || (profile == null)) {
       return;