supersize: Add symbol.template_name, and strip <>s from symbol.name

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).
   * size: The number of bytes this symbol takes up, including padding that comes
-       before |address|.
+        before |address|.
   * num_aliases: The number of symbols with the same address (including self).
   * pss: size / num_aliases.
   * padding: The number of bytes of padding before |address| due to this symbol.
-  * name: Symbol names with parameter list removed.
+  * name: Names with templates and parameter list removed.
         Never None, but will be '' for anonymous symbols.
-  * full_name: Symbols names with parameter list left in.
-       Never None, but will be '' for anonymous symbols, and for symbols that do
-       not contain a parameter list.
+  * template_name: Name with parameter list removed (but templates left in).
+        Never None, but will be '' for anonymous symbols.
+  * full_name: Name with template and parameter list left in.
+        Never None, but will be '' for anonymous symbols.
   * is_anonymous: True when the symbol exists in an anonymous namespace (which
-       are removed from both full_name and name during normalization).
+        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
@@ skipping 23 matching lines @@
 FLAG_REL = 8
 FLAG_REL_LOCAL = 16
 FLAG_GENERATED_SOURCE = 32
 
 
 class SizeInfo(object):
   """Represents all size information for a single binary.
 
   Fields:
     section_sizes: A dict of section_name -> size.
-    symbols: A SymbolGroup containing all symbols, sorted by address.
+    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.
     metadata: A dict.
   """
   __slots__ = (
       'section_sizes',
+      'raw_symbols',
       'symbols',
       'metadata',
   )
 
   """Root size information."""
-  def __init__(self, section_sizes, symbols, metadata=None):
+  def __init__(self, section_sizes, raw_symbols, metadata=None, symbols=None):
     self.section_sizes = section_sizes  # E.g. {'.text': 0}
-    self.symbols = symbols
+    self.raw_symbols = raw_symbols
+    self.symbols = symbols or SymbolGroup(raw_symbols)
     self.metadata = metadata or {}
 
-  def Cluster(self):
+  def Clustered(self):
     """Returns a new SizeInfo with some symbols moved into subgroups.
 
-    See SymbolGroup.Cluster() for more details.
+    See SymbolGroup.Clustered() for more details.
     """
-    return SizeInfo(self.section_sizes, self.symbols.Cluster(), self.metadata)
+    return SizeInfo(self.section_sizes, self.raw_symbols, self.metadata,
+                    symbols=self.symbols.Clustered())
 
 
 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.
     before_metadata: metadata of the "before" SizeInfo.
     after_metadata: metadata of the "after" SizeInfo.
@@ skipping 90 matching lines @@
 
 class Symbol(BaseSymbol):
   """Represents a single symbol within a binary.
 
   Refer to module docs for field descriptions.
   """
 
   __slots__ = (
       'address',
       'full_name',
+      'template_name',
+      'name',
       'flags',
       'object_path',
-      'name',
       'aliases',
       'padding',
       'section_name',
       'source_path',
       'size',
   )
 
   def __init__(self, section_name, size_without_padding, address=None,
-               name=None, source_path=None, object_path=None, full_name=None,
-               flags=0, aliases=None):
+               full_name=None, template_name=None, name=None, source_path=None,
+               object_path=None, flags=0, aliases=None):
     self.section_name = section_name
     self.address = address or 0
+    self.full_name = full_name or ''
+    self.template_name = template_name or ''
     self.name = name or ''
-    self.full_name = full_name or ''
     self.source_path = source_path or ''
     self.object_path = object_path or ''
     self.size = size_without_padding
     self.flags = flags
     self.aliases = aliases
     self.padding = 0
 
   def __repr__(self):
     template = ('{}@{:x}(size_without_padding={},padding={},name={},'
                 'object_path={},source_path={},flags={})')
@@ skipping 26 matching lines @@
   * unioned = group1 + group2
   """
 
   __slots__ = (
       '_padding',
       '_size',
       '_pss',
       '_symbols',
       '_filtered_symbols',
       'full_name',
+      'template_name',
       'name',
       'section_name',
       'is_sorted',
   )
 
-  def __init__(self, symbols, filtered_symbols=None, name=None,
-               full_name=None, section_name=None, is_sorted=False):
+  # template_name and full_name are useful when clustering symbol clones.
+  def __init__(self, symbols, filtered_symbols=None, full_name=None,
+               template_name=None, name='', section_name=None, is_sorted=False):
     self._padding = None
     self._size = None
     self._pss = None
     self._symbols = symbols
     self._filtered_symbols = filtered_symbols or []
+    self.full_name = full_name if full_name is not None else name
+    self.template_name = template_name if template_name is not None else name
     self.name = name or ''
-    self.full_name = full_name
     self.section_name = section_name or '.*'
     self.is_sorted = is_sorted
 
   def __repr__(self):
     return 'Group(name=%s,count=%d,size=%d)' % (
         self.name, len(self), self.size)
 
   def __iter__(self):
     return iter(self._symbols)
 
@@ skipping 95 matching lines @@
     for s in self:
       if s.IsGroup():
         for x in s.IterLeafSymbols():
           yield x
       else:
         yield s
 
   def CountUniqueSymbols(self):
     return sum(1 for s in self.IterUniqueSymbols())
 
-  def _CreateTransformed(self, symbols, filtered_symbols=None, name=None,
-                         full_name=None, section_name=None, is_sorted=None):
+  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, name=name,
-                       full_name=full_name, section_name=section_name,
+    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 Cluster(self):
+  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))
@@ skipping 38 matching lines @@
 
   def WhereInSection(self, section):
     if len(section) == 1:
       ret = self.Filter(lambda s: s.section == section)
       ret.section_name = SECTION_TO_SECTION_NAME[section]
     else:
       ret = self.Filter(lambda s: s.section_name == section)
       ret.section_name = section
     return ret
 
+  def WhereIsTemplate(self):
+    return self.Filter(lambda s: s.template_name is not s.name)
+
   def WhereSourceIsGenerated(self):
     return self.Filter(lambda s: s.generated_source)
 
   def WhereGeneratedByToolchain(self):
     return self.Filter(lambda s: s.IsGeneratedByToolchain())
 
+  def WhereFullNameMatches(self, pattern):
+    regex = re.compile(match_util.ExpandRegexIdentifierPlaceholder(pattern))
+    return self.Filter(lambda s: regex.search(s.full_name))
+
+  def WhereTemplateNameMatches(self, pattern):
+    regex = re.compile(match_util.ExpandRegexIdentifierPlaceholder(pattern))
+    return self.Filter(lambda s: regex.search(s.template_name))
+
   def WhereNameMatches(self, pattern):
     regex = re.compile(match_util.ExpandRegexIdentifierPlaceholder(pattern))
     return self.Filter(lambda s: regex.search(s.name))
 
-  def WhereFullNameMatches(self, pattern):
-    regex = re.compile(match_util.ExpandRegexIdentifierPlaceholder(pattern))
-    return self.Filter(lambda s: regex.search(s.full_name or s.name))
-
   def WhereObjectPathMatches(self, pattern):
     regex = re.compile(match_util.ExpandRegexIdentifierPlaceholder(pattern))
     return self.Filter(lambda s: regex.search(s.object_path))
 
   def WhereSourcePathMatches(self, pattern):
     regex = re.compile(match_util.ExpandRegexIdentifierPlaceholder(pattern))
     return self.Filter(lambda s: regex.search(s.source_path))
 
   def WherePathMatches(self, pattern):
     regex = re.compile(match_util.ExpandRegexIdentifierPlaceholder(pattern))
     return self.Filter(lambda s: (regex.search(s.source_path) or
                                   regex.search(s.object_path)))
 
   def WhereMatches(self, pattern):
     """Looks for |pattern| within all paths & names."""
     regex = re.compile(match_util.ExpandRegexIdentifierPlaceholder(pattern))
-    return self.Filter(lambda s: (regex.search(s.source_path) or
-                                  regex.search(s.object_path) or
-                                  regex.search(s.full_name or '') or
-                                  regex.search(s.name)))
+    return self.Filter(lambda s: (
+        regex.search(s.source_path) or
+        regex.search(s.object_path) or
+        regex.search(s.full_name) or
+        s.full_name is not s.template_name and regex.search(s.template_name) or
+        s.full_name is not s.name and regex.search(s.name)))
 
   def WhereAddressInRange(self, start, end=None):
     """Searches for addesses within [start, end).
 
     Args may be ints or hex strings. Default value for |end| is |start| + 1.
     """
     if isinstance(start, basestring):
       start = int(start, 16)
     if end is None:
       end = start + 1
     return self.Filter(lambda s: s.address >= start and s.address < end)
 
   def WhereHasPath(self):
     return self.Filter(lambda s: s.source_path or s.object_path)
 
   def WhereHasAnyAttribution(self):
-    return self.Filter(lambda s: s.name or s.source_path or s.object_path)
+    return self.Filter(lambda s: s.full_name or s.source_path or s.object_path)
 
   def Inverted(self):
     """Returns the symbols that were filtered out by the previous filter.
 
     Applies only when the previous call was a filter.
 
     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 GroupBy(self, func, min_count=0):
+  def GroupedBy(self, func, min_count=0):
     """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.
       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.
@@ skipping 19 matching lines @@
             is_sorted=False))
       elif include_singles:
         after_syms.extend(symbols)
       else:
         filtered_symbols.extend(symbols)
     grouped = self._CreateTransformed(
         after_syms, filtered_symbols=filtered_symbols,
         section_name=self.section_name, is_sorted=False)
     return grouped
 
-  def GroupBySectionName(self):
-    return self.GroupBy(lambda s: s.section_name)
+  def GroupedBySectionName(self):
+    return self.GroupedBy(lambda s: s.section_name)
 
-  def GroupByNamespace(self, depth=0, fallback='{global}', min_count=0):
-    """Groups by symbol namespace (as denoted by ::s).
+  def GroupedByName(self, depth=0, min_count=0):
+    """Groups by symbol name, where |depth| controls how many ::s to include.
 
-    Does not differentiate between C++ namespaces and C++ classes.
+    Does not differentiate between namespaces/classes/functions.
 
     Args:
-      depth: When 0 (default), groups by entire namespace. When 1, groups by
-             top-level name, when 2, groups by top 2 names, etc.
-      fallback: Use this value when no namespace exists.
+      depth: 0 (default): Groups by entire name. Useful for grouping templates.
+             >0: Groups by this many name parts.
+                 Example: 1 -> std::, 2 -> std::map
+             <0: Groups by entire name minus this many name parts
+                 Example: -1 -> std::map, -2 -> std::
       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.
     """
-    def extract_namespace(symbol):
-      # Remove template params.
-      name = symbol.name
-      template_idx = name.find('<')
-      if template_idx:
-        name = name[:template_idx]
+    if depth >= 0:
+      extract_namespace = (
+          lambda s: _ExtractPrefixBeforeSeparator(s.name, '::', depth))
+    else:
+      depth = -depth
+      extract_namespace = (
+          lambda s: _ExtractSuffixAfterSeparator(s.name, '::', depth))
+    return self.GroupedBy(extract_namespace, min_count=min_count)
 
-      # Remove after the final :: (not part of the namespace).
-      colon_idx = name.rfind('::')
-      if colon_idx == -1:
-        return fallback
-      name = name[:colon_idx]
-
-      return _ExtractPrefixBeforeSeparator(name, '::', depth)
-    return self.GroupBy(extract_namespace, min_count=min_count)
-
-  def GroupByPath(self, depth=0, fallback='{no path}',
+  def GroupedByPath(self, depth=0, fallback='{no path}',
                   fallback_to_object_path=True, min_count=0):
     """Groups by source_path.
 
     Args:
       depth: When 0 (default), groups by entire path. When 1, groups by
              top-level directory, when 2, groups by top 2 directories, etc.
       fallback: Use this value when no namespace exists.
       fallback_to_object_path: When True (default), uses object_path when
              source_path is missing.
       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.
     """
     def extract_path(symbol):
       path = symbol.source_path
       if fallback_to_object_path and not path:
         path = symbol.object_path
       path = path or fallback
       return _ExtractPrefixBeforeSeparator(path, os.path.sep, depth)
-    return self.GroupBy(extract_path, min_count=min_count)
+    return self.GroupedBy(extract_path, min_count=min_count)
 
 
 class SymbolDiff(SymbolGroup):
   """A SymbolGroup subclass representing a diff of two other SymbolGroups.
 
   All Symbols contained within have a |size| which is actually the size delta.
   Additionally, metadata is kept about which symbols were added / removed /
   changed.
   """
   __slots__ = (
       '_added_ids',
       '_removed_ids',
   )
 
-  def __init__(self, added, removed, similar, name=None, full_name=None,
-               section_name=None):
+  def __init__(self, added, removed, similar):
     self._added_ids = set(id(s) for s in added)
     self._removed_ids = set(id(s) for s in removed)
     symbols = []
     symbols.extend(added)
     symbols.extend(removed)
     symbols.extend(similar)
-    super(SymbolDiff, self).__init__(symbols, name=name, full_name=full_name,
-                                     section_name=section_name)
+    super(SymbolDiff, self).__init__(symbols)
 
   def __repr__(self):
     return '%s(%d added, %d removed, %d changed, %d unchanged, size=%d)' % (
         'SymbolGroup', self.added_count, self.removed_count, self.changed_count,
         self.unchanged_count, self.size)
 
-  def _CreateTransformed(self, symbols, filtered_symbols=None, name=None,
-                         full_name=None, section_name=None, is_sorted=None):
+  def _CreateTransformed(self, symbols, filtered_symbols=None, full_name=None,
+                         template_name=None, name=None, section_name=None,
+                         is_sorted=None):
     # Printing sorts, so short-circuit the same symbols case.
     if len(symbols) == len(self._symbols):
       new_added_ids = self._added_ids
       new_removed_ids = self._removed_ids
     else:
       old_added_ids = self._added_ids
       old_removed_ids = self._removed_ids
 
       def get_status(sym):
         obj_id = id(sym)
@@ skipping 13 matching lines @@
         status = get_status(sym)
         if status == 0:
           new_added_ids.add(id(sym))
         elif status == 1:
           new_removed_ids.add(id(sym))
 
     ret = SymbolDiff.__new__(SymbolDiff)
     ret._added_ids = new_added_ids
     ret._removed_ids = new_removed_ids
     super(SymbolDiff, ret).__init__(
-        symbols, filtered_symbols=filtered_symbols, name=name,
-        full_name=full_name, section_name=section_name, is_sorted=is_sorted)
+        symbols, filtered_symbols=filtered_symbols, full_name=full_name,
+        template_name=template_name, name=name, section_name=section_name,
+        is_sorted=is_sorted)
     return ret
 
   @property
   def added_count(self):
     return len(self._added_ids)
 
   @property
   def removed_count(self):
     return len(self._removed_ids)
 
@@ skipping 13 matching lines @@
     key = id(sym)
     return key not in self._added_ids and key not in self._removed_ids
 
   def IsRemoved(self, sym):
     return id(sym) in self._removed_ids
 
   def WhereNotUnchanged(self):
     return self.Filter(lambda s: not self.IsSimilar(s) or s.size)
 
 
-def _ExtractPrefixBeforeSeparator(string, separator, count=1):
+def _ExtractPrefixBeforeSeparator(string, separator, count):
   idx = -len(separator)
   prev_idx = None
   for _ in xrange(count):
     idx = string.find(separator, idx + len(separator))
     if idx < 0:
       break
     prev_idx = idx
   return string[:prev_idx]
+
+
+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]