Add the core classification infrastructure to memory_inspector.

tools/memory_inspector/memory_inspector/classification/results.py

Index: tools/memory_inspector/memory_inspector/classification/results.py
diff --git a/tools/memory_inspector/memory_inspector/classification/results.py b/tools/memory_inspector/memory_inspector/classification/results.py
new file mode 100644
index 0000000000000000000000000000000000000000..24091485459110a13c9cc922687f79fce53a4de9
--- /dev/null
+++ b/tools/memory_inspector/memory_inspector/classification/results.py
@@ -0,0 +1,115 @@
+# Copyright 2014 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+"""This module owns the logic for classifying and aggregating data in buckets.
+
+This complements the structure defined in the rules module. Symmetrically, the
+aggregated results are organized in a bucket tree, which structure is identical
+to the one of the corresponding rule tree.
+The logic for aggregation is the following:
+- The client loads a "rule tree" defined by the end-user (e.g., in a file) which
+  defines the final "shape" of the results.
+- The rules define how to "match" a trace_record (e.g., a mmap line or a native
+  allocation) given some of its properties (e.g. the mapped file or the prot.
+  flags).
+- The concrete classifier (which will use this module) knows how to count the
+  values for each trace_record (e.g. [Dirty KB, Clean KB, RSS KB] for mmaps).
+  Hence it decides the cardinality of the result nodes.
+- The responsibility of this module is simply doing the math.
+
+In the very essence this module adds up the counters of each node whereas the
+trace_record being pushed in the tree (through the AddToMatchingNodes method)
+matches a rule.
+It just does this math in a hierarchical fashion following the shape the tree.
+
+A typical result tree looks like this (each node has two values in the example):
+                          +----------------------+
+                          |        Total         |
+                          |----------------------|
+       +------------------+     (100, 1000)      +--------------------+
+       |                  +----------+-----------+                    |
+       |                             |                                |
+ +-----v-----+                 +-----v-----+                   +------v----+
+ |    Foo    |                 |    Bar    |                   |Total-other|
+ |-----------|                 |-----------|                   |-----------|
+ | (15, 100) |             +---+ (80, 200) +-----+             | (5, 700)  |
+ +-----------+             |   +-----------+     |             +-----------+
+                           |                     |
+                    +------v------+       +------v-----+
+                    | Bar::Coffee |       | Bar-other  |
+                    |-------------|       |------------|
+                    |  (30, 120)  |       |  (50, 80)  |
+                    +-------------+       +------------+
+"""
+
+from memory_inspector.classification import rules
+
+
+class AggreatedResults(object):
+  """A tree of results, where each node is a bucket (root: 'Total' bucket)."""
+
+  def __init__(self, rule_tree, keys):
+    """Initializes the bucket tree using the structure of the rules tree.
+
+    Each node of the bucket tree is initialized with a list of len(keys) zeros.
+    """
+    assert(isinstance(rule_tree, rules.Rule))
+    assert(isinstance(keys, list))
+    self.keys = keys
+    self.total = AggreatedResults._MakeBucketNodeFromRule(rule_tree, len(keys))
+
+  def AddToMatchingNodes(self, trace_record, values):
+    """Adds the provided |values| to the nodes that match the |trace_record|.
+
+    Tree traversal logic: at any level, one and only one node will match the
+    |trace_record| (in the worst case it will be the catchall *-other rule).
+    When a node is matched, the traversal continues in its children and no
+    further siblings in the upper levels are visited anymore.
+    This is to guarantee that at any level the values of one node are equal to
+    the sum of the values of all its children.
+
+    Args:
+      trace_record: any kind of object which can be matched by the Match method
+          of the Rule object.
+      values: a list of int(s) which represent the value associated to the
+          matched trace_record. The cardinality of the list must be equal to the
+          cardinality of the initial keys.
+    """
+    assert(len(values) == len(self.keys))
+    AggreatedResults._AddToMatchingNodes(
+        trace_record, values, self.total, len(self.keys))
+
+  @staticmethod
+  def _AddToMatchingNodes(trace_record, values, bucket, num_keys):
+    if not bucket.rule.Match(trace_record):
+      return False
+    for i in xrange(num_keys):
+      bucket.values[i] += values[i]
+    for child_bucket in bucket.children:
+      if AggreatedResults._AddToMatchingNodes(
+          trace_record, values, child_bucket, num_keys):
+        break
+    return True
+
+  @staticmethod
+  def _MakeBucketNodeFromRule(rule, num_keys):
+    assert(isinstance(rule, rules.Rule))
+    bucket = Bucket(rule, num_keys)
+    for child_rule in rule.children:
+      bucket.children.append(
+          AggreatedResults._MakeBucketNodeFromRule(child_rule, num_keys))
+    return bucket
+
+
+class Bucket(object):
+  """A bucket is a node in the results tree. """
+  def __init__(self, rule, num_keys):
+    self.rule = rule
+    self.values = [0] * num_keys
+    self.children = []
+
+
+  @property
+  def name(self):
+    return self.rule.name