supersize: Move [clone] from name -> flags & rewrite Cluster()

tools/binary_size/libsupersize/models.py

 # Copyright 2017 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.
 """Classes that comprise the data model for binary size analysis.
 
 The primary classes are Symbol, and SymbolGroup.
 
 Description of common properties:
   * address: The start address of the symbol.
         May be 0 (e.g. for .bss or for SymbolGroups).
@@ skipping 12 matching lines @@
         are removed from both full_name and name during normalization).
   * section_name: E.g. ".text", ".rodata", ".data.rel.local"
   * section: The second character of |section_name|. E.g. "t", "r", "d".
 """
 
 import collections
 import logging
 import os
 import re
 
-import cluster_symbols
 import match_util
 
 
 METADATA_GIT_REVISION = 'git_revision'
 METADATA_APK_FILENAME = 'apk_file_name'  # Path relative to output_directory.
 METADATA_MAP_FILENAME = 'map_file_name'  # Path relative to output_directory.
 METADATA_ELF_ARCHITECTURE = 'elf_arch'  # "Machine" field from readelf -h
 METADATA_ELF_FILENAME = 'elf_file_name'  # Path relative to output_directory.
 METADATA_ELF_MTIME = 'elf_mtime'  # int timestamp in utc.
 METADATA_ELF_BUILD_ID = 'elf_build_id'
 METADATA_GN_ARGS = 'gn_args'
 METADATA_TOOL_PREFIX = 'tool_prefix'  # Path relative to SRC_ROOT.
 
 
 SECTION_TO_SECTION_NAME = {
     'b': '.bss',
     'd': '.data',
     'r': '.rodata',
     't': '.text',
 }
 
 FLAG_ANONYMOUS = 1
 FLAG_STARTUP = 2
 FLAG_UNLIKELY = 4
 FLAG_REL = 8
 FLAG_REL_LOCAL = 16
 FLAG_GENERATED_SOURCE = 32
+FLAG_CLONE = 64
 
 DIFF_STATUS_UNCHANGED = 0
 DIFF_STATUS_CHANGED = 1
 DIFF_STATUS_ADDED = 2
 DIFF_STATUS_REMOVED = 3
 
 
 class SizeInfo(object):
   """Represents all size information for a single binary.
 
   Fields:
     section_sizes: A dict of section_name -> size.
-    raw_symbols: A list of all symbols, sorted by address.
-    symbols: A SymbolGroup containing all symbols. By default, these are the
-        same as raw_symbols, but may contain custom groupings when it is
-        desirable to convey the result of a query along with section_sizes and
-        metadata.
+    raw_symbols: A SymbolGroup containing all top-level symbols (no groups).
+    symbols: A SymbolGroup where symbols have been grouped by full_name (where
+        applicable). May be re-assigned when it is desirable to show custom
+        groupings while still printing metadata and section_sizes.
     metadata: A dict.
   """
   __slots__ = (
       'section_sizes',
       'raw_symbols',
-      'symbols',
+      '_symbols',
       'metadata',
   )
 
   """Root size information."""
   def __init__(self, section_sizes, raw_symbols, metadata=None, symbols=None):
+    if isinstance(raw_symbols, list):
+      raw_symbols = SymbolGroup(raw_symbols)
     self.section_sizes = section_sizes  # E.g. {'.text': 0}
     self.raw_symbols = raw_symbols
-    self.symbols = symbols or SymbolGroup(raw_symbols)
+    self._symbols = symbols
     self.metadata = metadata or {}
 
-  def Clustered(self):
-    """Returns a new SizeInfo with some symbols moved into subgroups.
+  @property
+  def symbols(self):
+    if self._symbols is None:
+      self._symbols = self.raw_symbols._Clustered()
+    return self._symbols
 
-    See SymbolGroup.Clustered() for more details.
-    """
-    return SizeInfo(self.section_sizes, self.raw_symbols, self.metadata,
-                    symbols=self.symbols.Clustered())
+  @symbols.setter
+  def symbols(self, value):
+    self._symbols = value
 
 
 class SizeInfoDiff(object):
   """What you get when you Diff() two SizeInfo objects.
 
   Fields:
     section_sizes: A dict of section_name -> size delta.
-    symbols: A SymbolDiff with all symbols in it.
+    raw_symbols: A SymbolDiff with all top-level symbols in it (no groups).
+    symbols: A SymbolDiff where symbols have been grouped by full_name (where
+        applicable). May be re-assigned when it is desirable to show custom
+        groupings while still printing metadata and section_sizes.
     before_metadata: metadata of the "before" SizeInfo.
     after_metadata: metadata of the "after" SizeInfo.
   """
   __slots__ = (
       'section_sizes',
-      'symbols',
+      'raw_symbols',
+      '_symbols',
       'before_metadata',
       'after_metadata',
   )
 
-  def __init__(self, section_sizes, symbols, before_metadata, after_metadata):
+  def __init__(self, section_sizes, raw_symbols, before_metadata,
+               after_metadata):
     self.section_sizes = section_sizes
-    self.symbols = symbols
+    self.raw_symbols = raw_symbols
     self.before_metadata = before_metadata
     self.after_metadata = after_metadata
+    self._symbols = None
+
+  @property
+  def symbols(self):
+    if self._symbols is None:
+      self._symbols = self.raw_symbols._Clustered()
+    return self._symbols
+
+  @symbols.setter
+  def symbols(self, value):
+    self._symbols = value
 
 
 class BaseSymbol(object):
   """Base class for Symbol and SymbolGroup.
 
   Refer to module docs for field descriptions.
   """
   __slots__ = ()
 
   @property
@@ skipping 42 matching lines @@
     if flags & FLAG_STARTUP:
       parts.append('startup')
     if flags & FLAG_UNLIKELY:
       parts.append('unlikely')
     if flags & FLAG_REL:
       parts.append('rel')
     if flags & FLAG_REL_LOCAL:
       parts.append('rel.loc')
     if flags & FLAG_GENERATED_SOURCE:
       parts.append('gen')
+    if flags & FLAG_CLONE:
+      parts.append('clone')
     # Not actually a part of flags, but useful to show it here.
     if self.aliases:
       parts.append('{} aliases'.format(self.num_aliases))
     return '{%s}' % ','.join(parts)
 
   def IsBss(self):
     return self.section_name == '.bss'
 
   def IsGroup(self):
     return False
@@ skipping 212 matching lines @@
   def _CreateTransformed(self, symbols, filtered_symbols=None, full_name=None,
                          template_name=None, name=None, section_name=None,
                          is_sorted=None):
     if is_sorted is None:
       is_sorted = self.is_sorted
     return SymbolGroup(symbols, filtered_symbols=filtered_symbols,
                        full_name=full_name, template_name=template_name,
                        name=name, section_name=section_name,
                        is_sorted=is_sorted)
 
-  def Clustered(self):
-    """Returns a new SymbolGroup with some symbols moved into subgroups.
-
-    Subgroups include:
-     * Symbols that have [clone] in their name (created during inlining).
-     * Star symbols (such as "** merge strings", and "** symbol gap")
-
-    To view created groups:
-      Print(clustered.Filter(lambda s: s.IsGroup()), recursive=True)
-    """
-    return self._CreateTransformed(cluster_symbols.ClusterSymbols(self))
-
   def Sorted(self, cmp_func=None, key=None, reverse=False):
     if cmp_func is None and key is None:
       cmp_func = lambda a, b: cmp((a.IsBss(), abs(b.pss), a.name),
                                   (b.IsBss(), abs(a.pss), b.name))
 
     after_symbols = sorted(self._symbols, cmp_func, key, reverse)
     return self._CreateTransformed(
         after_symbols, filtered_symbols=self._filtered_symbols,
         section_name=self.section_name, is_sorted=True)
 
@@ skipping 15 matching lines @@
       for symbol in self:
         filtered_and_kept[int(bool(func(symbol)))].append(symbol)
     except:
       logging.warning('Filter failed on symbol %r', symbol)
       raise
 
     return self._CreateTransformed(filtered_and_kept[1],
                                    filtered_symbols=filtered_and_kept[0],
                                    section_name=self.section_name)
 
+  def WhereIsGroup(self):
+    return self.Filter(lambda s: s.IsGroup())
+
   def WhereSizeBiggerThan(self, min_size):
     return self.Filter(lambda s: s.size >= min_size)
 
   def WherePssBiggerThan(self, min_pss):
     return self.Filter(lambda s: s.pss >= min_pss)
 
   def WhereInSection(self, section):
     if len(section) == 1:
       ret = self.Filter(lambda s: s.section == section)
       ret.section_name = SECTION_TO_SECTION_NAME[section]
@@ skipping 70 matching lines @@
 
     Example:
         # Symbols that do not have "third_party" in their path.
         symbols.WherePathMatches(r'third_party').Inverted()
         # Symbols within third_party that do not contain the string "foo".
         symbols.WherePathMatches(r'third_party').WhereMatches('foo').Inverted()
     """
     return self._CreateTransformed(
         self._filtered_symbols, filtered_symbols=self._symbols, is_sorted=False)
 
-  def GroupedBy(self, func, min_count=0):
+  def GroupedBy(self, func, min_count=0, group_factory=None):
     """Returns a SymbolGroup of SymbolGroups, indexed by |func|.
 
     Symbols within each subgroup maintain their relative ordering.
 
     Args:
       func: Grouping function. Passed a symbol and returns a string for the
-            name of the subgroup to put the symbol in. If None is returned, the
-            symbol is omitted.
+          name of the subgroup to put the symbol in. If None is returned, the
+          symbol is omitted.
       min_count: Miniumum number of symbols for a group. If fewer than this many
-                 symbols end up in a group, they will not be put within a group.
-                 Use a negative value to omit symbols entirely rather than
-                 include them outside of a group.
+          symbols end up in a group, they will not be put within a group.
+          Use a negative value to omit symbols entirely rather than
+          include them outside of a group.
+      group_factory: Function to create SymbolGroup from a list of Symbols.
     """
+    if group_factory is None:
+      group_factory = lambda token, symbols: self._CreateTransformed(
+            symbols, full_name=token, template_name=token, name=token,
+            section_name=self.section_name)
+
     after_syms = []
     filtered_symbols = []
-    symbols_by_token = collections.defaultdict(list)
+    symbols_by_token = collections.OrderedDict()
     # Index symbols by |func|.
     for symbol in self:
       token = func(symbol)
       if token is None:
         filtered_symbols.append(symbol)
-      symbols_by_token[token].append(symbol)
+      else:
+        # Optimization: Store a list only when >1 symbol.
+        # Saves 200-300ms for _Clustered().
+        prev = symbols_by_token.setdefault(token, symbol)
+        if prev is not symbol:
+          if prev.__class__ == list:
+            prev.append(symbol)
+          else:
+            symbols_by_token[token] = [prev, symbol]
     # Create the subgroups.
     include_singles = min_count >= 0
     min_count = abs(min_count)
-    for token, symbols in symbols_by_token.iteritems():
-      if len(symbols) >= min_count:
-        after_syms.append(self._CreateTransformed(
-            symbols, name=token, section_name=self.section_name,
-            is_sorted=False))
-      elif include_singles:
-        after_syms.extend(symbols)
+    for token, symbol_or_list in symbols_by_token.iteritems():
+      count = 1
+      if symbol_or_list.__class__ == list:
+        count = len(symbol_or_list)
+
+      if count >= min_count:
+        if count == 1:
+          symbol_or_list = [symbol_or_list]
+        after_syms.append(group_factory(token, symbol_or_list))
       else:
-        filtered_symbols.extend(symbols)
-    grouped = self._CreateTransformed(
+        target_list = after_syms if include_singles else filtered_symbols
+        if count == 1:
+          target_list.append(symbol_or_list)
+        else:
+          target_list.extend(symbol_or_list)
+
+    return self._CreateTransformed(
         after_syms, filtered_symbols=filtered_symbols,
-        section_name=self.section_name, is_sorted=False)
-    return grouped
+        section_name=self.section_name)
+
+  def _Clustered(self):
+    """Returns a new SymbolGroup with some symbols moved into subgroups.
+
+    Method is private since it only ever makes sense to call it from
+    SizeInfo.symbols.
+
+    The main function of clustering is to put symbols that were broken into
+    multiple parts under a group so that they once again look like a single
+    symbol. It also groups together symbols like "** merge strings".
+
+    To view created groups:
+      Print(size_info.symbols.WhereIsGroup())
+    """
+    def cluster_func(symbol):
+      name = symbol.full_name
+      if not name:
+        # min_count=2 will ensure order is maintained while not being grouped.
+        # "&" to distinguish from real symbol names, id() to ensure uniqueness.
+        return '&' + hex(id(symbol))
+      if name.startswith('*'):
+        # "symbol gap 3" -> "symbol gaps"
+        name = re.sub(r'\s+\d+( \(.*\))?$', 's', name)
+      return name
+
+    # Use a custom factory to fill in name & template_name.
+    def group_factory(full_name, symbols):
+      sym = symbols[0]
+      if full_name.startswith('*'):
+        return self._CreateTransformed(
+            symbols, full_name=full_name, template_name=full_name,
+            name=full_name, section_name=sym.section_name)
+      return self._CreateTransformed(
+          symbols, full_name=full_name, template_name=sym.template_name,
+          name=sym.name, section_name=sym.section_name)
+
+    # A full second faster to cluster per-section. Plus, don't need create
+    # (section_name, name) tuples in cluster_func.
+    ret = []
+    for section in self.GroupedBySectionName():
+      ret.extend(section.GroupedBy(
+          cluster_func, min_count=2, group_factory=group_factory))
+
+    return self._CreateTransformed(ret)
 
   def GroupedBySectionName(self):
     return self.GroupedBy(lambda s: s.section_name)
 
   def GroupedByName(self, depth=0, min_count=0):
     """Groups by symbol name, where |depth| controls how many ::s to include.
 
     Does not differentiate between namespaces/classes/functions.
 
     Args:
@@ skipping 161 matching lines @@
 
 
 def _ExtractSuffixAfterSeparator(string, separator, count):
   prev_idx = len(string) + 1
   for _ in xrange(count):
     idx = string.rfind(separator, 0, prev_idx - 1)
     if idx < 0:
       break
     prev_idx = idx
   return string[:prev_idx]