binary_size: Avoid creating nodes with many thousand children.

tools/binary_size/run_binary_size_analysis.py

 #!/usr/bin/env python
 # 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.
 
 """Generate a spatial analysis against an arbitrary library.
 
 To use, build the 'binary_size_tool' target. Then run this tool, passing
 in the location of the library to be analyzed along with any other options
 you desire.
@@ skipping 21 matching lines @@
     os.path.dirname(__file__),
     '..',
     '..',
     'build',
     'android',
     'pylib'))
 sys.path.append(elf_symbolizer_path)
 import symbols.elf_symbolizer as elf_symbolizer  # pylint: disable=F0401
 
 
+# Node dictionary keys. These are output in json read by the webapp so
+# keep them short to save file size.
+# Note: If these change, the webapp must also change.
+NODE_TYPE_KEY = 'k'
+NODE_NAME_KEY = 'n'
+NODE_CHILDREN_KEY = 'children'
+NODE_SYMBOL_TYPE_KEY = 't'
+NODE_SYMBOL_SIZE_KEY = 'value'
+NODE_MAX_DEPTH_KEY = 'maxDepth'
+NODE_LAST_PATH_ELEMENT_KEY = 'lastPathElement'
+
+# The display name of the bucket where we put symbols without path.
+NAME_NO_PATH_BUCKET = '(No Path)'
+
+# Try to keep data buckets smaller than this to avoid killing the
+# graphing lib.
+BIG_BUCKET_LIMIT = 3000
+
+
 # TODO(andrewhayden): Only used for legacy reports. Delete.
 def FormatBytes(byte_count):
   """Pretty-print a number of bytes."""
   if byte_count > 1e6:
     byte_count = byte_count / 1.0e6
     return '%.1fm' % byte_count
   if byte_count > 1e3:
     byte_count = byte_count / 1.0e3
     return '%.1fk' % byte_count
   return str(byte_count)
 
 
 # TODO(andrewhayden): Only used for legacy reports. Delete.
 def SymbolTypeToHuman(symbol_type):
   """Convert a symbol type as printed by nm into a human-readable name."""
   return {'b': 'bss',
           'd': 'data',
           'r': 'read-only data',
           't': 'code',
           'w': 'weak symbol',
           'v': 'weak symbol'}[symbol_type]
 
 
 def _MkChild(node, name):
-  child = node['children'].get(name)
+  child = node[NODE_CHILDREN_KEY].get(name)
   if child is None:
-    child = {'n': name, 'children': {}}
-    node['children'][name] = child
+    child = {NODE_NAME_KEY: name,
+             NODE_CHILDREN_KEY: {}}
+    node[NODE_CHILDREN_KEY][name] = child
   return child
 
 
+
+def SplitNoPathBucket(node):
+  """NAME_NO_PATH_BUCKET can be too large for the graphing lib to
+  handle. Split it into sub-buckets in that case."""
+  root_children = node[NODE_CHILDREN_KEY]
+  if NAME_NO_PATH_BUCKET in root_children:
+    no_path_bucket = root_children[NAME_NO_PATH_BUCKET]
+    old_children = no_path_bucket[NODE_CHILDREN_KEY]
+    count = 0
+    for symbol_type, symbol_bucket in old_children.iteritems():
+      count += len(symbol_bucket[NODE_CHILDREN_KEY])
+    if count > BIG_BUCKET_LIMIT:
+      new_children = {}
+      no_path_bucket[NODE_CHILDREN_KEY] = new_children
+      current_bucket = None
+      index = 0
+      for symbol_type, symbol_bucket in old_children.iteritems():
+        for symbol_name, value in symbol_bucket[NODE_CHILDREN_KEY].iteritems():
+          if index % BIG_BUCKET_LIMIT == 0:
+            group_no = (index / BIG_BUCKET_LIMIT) + 1
+            current_bucket = _MkChild(no_path_bucket,
+                                      '%s subgroup %d' % (NAME_NO_PATH_BUCKET,
+                                                          group_no))
+            assert not NODE_TYPE_KEY in node or node[NODE_TYPE_KEY] == 'p'
+            node[NODE_TYPE_KEY] = 'p'  # p for path
+          index += 1
+          symbol_size = value[NODE_SYMBOL_SIZE_KEY]
+          AddSymbolIntoFileNode(current_bucket, symbol_type,
+                                symbol_name, symbol_size)
+
+
 def MakeChildrenDictsIntoLists(node):
   largest_list_len = 0
-  if 'children' in node:
-    largest_list_len = len(node['children'])
+  if NODE_CHILDREN_KEY in node:
+    largest_list_len = len(node[NODE_CHILDREN_KEY])
     child_list = []
-    for child in node['children'].itervalues():
+    for child in node[NODE_CHILDREN_KEY].itervalues():
       child_largest_list_len = MakeChildrenDictsIntoLists(child)
       if child_largest_list_len > largest_list_len:
         largest_list_len = child_largest_list_len
       child_list.append(child)
-    node['children'] = child_list
+    node[NODE_CHILDREN_KEY] = child_list
 
   return largest_list_len
 
 
+def AddSymbolIntoFileNode(node, symbol_type, symbol_name, symbol_size):
+  """Puts symbol into the file path node |node|.
+  Returns the number of added levels in tree. I.e. returns 2."""
+
+  # 'node' is the file node and first step is to find its symbol-type bucket.
+  node[NODE_LAST_PATH_ELEMENT_KEY] = True
+  node = _MkChild(node, symbol_type)
+  assert not NODE_TYPE_KEY in node or node[NODE_TYPE_KEY] == 'b'
+  node[NODE_SYMBOL_TYPE_KEY] = symbol_type
+  node[NODE_TYPE_KEY] = 'b'  # b for bucket
+
+  # 'node' is now the symbol-type bucket. Make the child entry.
+  node = _MkChild(node, symbol_name)
+  if NODE_CHILDREN_KEY in node:
+    if node[NODE_CHILDREN_KEY]:
+      logging.warning('A container node used as symbol for %s.' % symbol_name)
+    # This is going to be used as a leaf so no use for child list.
+    del node[NODE_CHILDREN_KEY]
+  node[NODE_SYMBOL_SIZE_KEY] = symbol_size
+  node[NODE_SYMBOL_TYPE_KEY] = symbol_type
+  node[NODE_TYPE_KEY] = 's'  # s for symbol
+
+  return 2  # Depth of the added subtree.
+
+
 def MakeCompactTree(symbols):
-  result = {'n': '/', 'children': {}, 'k': 'p', 'maxDepth': 0}
+  result = {NODE_NAME_KEY: '/',
+            NODE_CHILDREN_KEY: {},
+            NODE_TYPE_KEY: 'p',
+            NODE_MAX_DEPTH_KEY: 0}
   seen_symbol_with_path = False
   for symbol_name, symbol_type, symbol_size, file_path in symbols:
 
     if 'vtable for ' in symbol_name:
-      symbol_type = '@' # hack to categorize these separately
+      symbol_type = '@'  # hack to categorize these separately
     # Take path like '/foo/bar/baz', convert to ['foo', 'bar', 'baz']
     if file_path:
       file_path = os.path.normpath(file_path)
       seen_symbol_with_path = True
     else:
-      file_path = '(No Path)'
+      file_path = NAME_NO_PATH_BUCKET
 
     if file_path.startswith('/'):
       file_path = file_path[1:]
     path_parts = file_path.split('/')
 
     # Find pre-existing node in tree, or update if it already exists
     node = result
     depth = 0
     while len(path_parts) > 0:
       path_part = path_parts.pop(0)
       if len(path_part) == 0:
         continue
       depth += 1
       node = _MkChild(node, path_part)
-      assert not 'k' in node or node['k'] == 'p'
-      node['k'] = 'p' # p for path
+      assert not NODE_TYPE_KEY in node or node[NODE_TYPE_KEY] == 'p'
+      node[NODE_TYPE_KEY] = 'p'  # p for path
 
-    # 'node' is now the file node. Find the symbol-type bucket.
-    node['lastPathElement'] = True
-    node = _MkChild(node, symbol_type)
-    assert not 'k' in node or node['k'] == 'b'
-    node['t'] = symbol_type
-    node['k'] = 'b' # b for bucket
-    depth += 1
-
-    # 'node' is now the symbol-type bucket. Make the child entry.
-    node = _MkChild(node, symbol_name)
-    if 'children' in node:
-      if node['children']:
-        logging.warning('A container node used as symbol for %s.' % symbol_name)
-      # This is going to be used as a leaf so no use for child list.
-      del node['children']
-    node['value'] = symbol_size
-    node['t'] = symbol_type
-    node['k'] = 's' # s for symbol
-    depth += 1
-    result['maxDepth'] = max(result['maxDepth'], depth)
+    depth += AddSymbolIntoFileNode(node, symbol_type, symbol_name, symbol_size)
+    result[NODE_MAX_DEPTH_KEY] = max(result[NODE_MAX_DEPTH_KEY], depth)
 
   if not seen_symbol_with_path:
     logging.warning('Symbols lack paths. Data will not be structured.')
 
+  # The (no path) bucket can be extremely large if we failed to get
+  # path information. Split it into subgroups if needed.
+  SplitNoPathBucket(result)
+
   largest_list_len = MakeChildrenDictsIntoLists(result)
 
-  if largest_list_len > 1000:
+  if largest_list_len > BIG_BUCKET_LIMIT:
     logging.warning('There are sections with %d nodes. '
                     'Results might be unusable.' % largest_list_len)
   return result
 
 
 # TODO(andrewhayden): Only used for legacy reports. Delete.
 def TreeifySymbols(symbols):
   """Convert symbols into a path-based tree, calculating size information
   along the way.
 
@@ skipping 572 matching lines @@
     shutil.copy(os.path.join(d3_src, 'LICENSE'), d3_out)
     shutil.copy(os.path.join(d3_src, 'd3.js'), d3_out)
     shutil.copy(os.path.join(template_src, 'index.html'), opts.destdir)
     shutil.copy(os.path.join(template_src, 'D3SymbolTreeMap.js'), opts.destdir)
 
   print 'Report saved to ' + opts.destdir + '/index.html'
 
 
 if __name__ == '__main__':
   sys.exit(main())