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

tools/binary_size/libsupersize/cluster_symbols.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.
-
-"""Logic for clustering similar symbols."""
-
-import collections
-import logging
-import re
-
-import function_signature
-
-
-def _StripCloneSuffix(name):
-  # Multiple attributes could exist, so search from left-to-right.
-  idx = name.find(' [clone ')
-  if idx != -1:
-    return name[:idx]
-  return name
-
-
-# Refer to models.SymbolGroup.Clustered() for pydoc
-# TODO(agrieve): This logic should likely be combined with
-#    SymbolGroup.GroupedBy(), as it conceptually does the same thing.
-#    One could also thing of this as GroupedByFullName().
-def ClusterSymbols(symbols):
-  # http://unix.stackexchange.com/questions/223013/function-symbol-gets-part-suffix-after-compilation
-  # Example name suffixes:
-  #     [clone .part.322]  # GCC
-  #     [clone .isra.322]  # GCC
-  #     [clone .constprop.1064]  # GCC
-  #     [clone .11064]  # clang
-
-  # Step 1: Create name map, find clones, collect star syms into replacements.
-  logging.debug('Creating name -> symbol map')
-  clone_indices = []
-  indices_by_full_name = {}
-  # (section_name, full_name_no_attr) -> [(index, sym),...]
-  replacements_by_tup = collections.defaultdict(list)
-  for i, symbol in enumerate(symbols):
-    name = symbol.full_name
-    if not name:
-      continue
-    if name.startswith('*'):
-      # "symbol gap 3" -> "symbol gaps"
-      name = re.sub(r'\s+\d+( \(.*\))?$', 's', name)
-      replacements_by_tup[(symbol.section_name, name)].append((i, symbol))
-    elif name.endswith(']') and ' [clone ' in name:
-      clone_indices.append(i)
-    else:
-      indices_by_full_name[name] = i
-
-  # Step 2: Collect same-named clone symbols.
-  logging.debug('Grouping all clones')
-  group_names_by_index = {}
-  for i in clone_indices:
-    symbol = symbols[i]
-    stripped_full_name = _StripCloneSuffix(symbol.full_name)
-    name_tup = (symbol.section_name, stripped_full_name)
-    replacement_list = replacements_by_tup[name_tup]
-
-    if not replacement_list:
-      # First occurance, check for non-clone symbol.
-      non_clone_idx = indices_by_full_name.get(stripped_full_name)
-      if non_clone_idx is not None:
-        non_clone_symbol = symbols[non_clone_idx]
-        replacement_list.append((non_clone_idx, non_clone_symbol))
-        group_names_by_index[non_clone_idx] = stripped_full_name
-
-    replacement_list.append((i, symbol))
-    group_names_by_index[i] = stripped_full_name
-
-  # Step 3: Undo clustering when length=1.
-  # Removing these groups means Diff() logic must know about [clone] suffix.
-  to_clear = []
-  for name_tup, replacement_list in replacements_by_tup.iteritems():
-    if len(replacement_list) == 1:
-      to_clear.append(name_tup)
-  for name_tup in to_clear:
-    del replacements_by_tup[name_tup]
-
-  # Step 4: Replace first symbol from each cluster with a SymbolGroup.
-  before_symbol_count = sum(len(x) for x in replacements_by_tup.itervalues())
-  logging.debug('Creating %d symbol groups from %d symbols. %d clones had only '
-                'one symbol.', len(replacements_by_tup), before_symbol_count,
-                len(to_clear))
-
-  len_delta = len(replacements_by_tup) - before_symbol_count
-  grouped_symbols = [None] * (len(symbols) + len_delta)
-  dest_index = 0
-  src_index = 0
-  seen_tups = set()
-  index_and_name_tups = []
-  for name_tup, replacement_list in replacements_by_tup.iteritems():
-    for symbol_tup in replacement_list:
-      index_and_name_tups.append((symbol_tup[0], name_tup))
-
-  index_and_name_tups.sort(key=lambda tup: tup[0])
-  for index, name_tup in index_and_name_tups:
-    count = index - src_index
-    grouped_symbols[dest_index:dest_index + count] = (
-        symbols[src_index:src_index + count])
-    src_index = index + 1
-    dest_index += count
-    if name_tup not in seen_tups:
-      seen_tups.add(name_tup)
-      group_symbols = [tup[1] for tup in replacements_by_tup[name_tup]]
-      section_name, stripped_full_name = name_tup
-      if stripped_full_name.startswith('*'):
-        stripped_template_name = stripped_full_name
-        stripped_name = stripped_full_name
-      else:
-        stripped_template_name = _StripCloneSuffix(
-            group_symbols[0].template_name)
-        stripped_name = _StripCloneSuffix(group_symbols[0].name)
-      cluster = symbols._CreateTransformed(
-          group_symbols, full_name=stripped_full_name,
-          template_name=stripped_template_name, name=stripped_name,
-          section_name=section_name)
-      function_signature.InternSameNames(cluster)
-      grouped_symbols[dest_index] = cluster
-      dest_index += 1
-
-  assert len(grouped_symbols[dest_index:None]) == len(symbols[src_index:None])
-  grouped_symbols[dest_index:None] = symbols[src_index:None]
-  logging.debug('Finished clustering symbols.')
-  return grouped_symbols