OLD | NEW |
1 # Copyright 2017 The Chromium Authors. All rights reserved. | 1 # Copyright 2017 The Chromium Authors. All rights reserved. |
2 # Use of this source code is governed by a BSD-style license that can be | 2 # Use of this source code is governed by a BSD-style license that can be |
3 # found in the LICENSE file. | 3 # found in the LICENSE file. |
4 | 4 |
5 """Logic for clustering similar symbols.""" | 5 """Logic for clustering similar symbols.""" |
6 | 6 |
7 import collections | 7 import collections |
8 import logging | 8 import logging |
9 import re | 9 import re |
10 | 10 |
11 | 11 |
12 # Refer to models.SymbolGroup.Cluster() for pydoc | 12 # Refer to models.SymbolGroup.Cluster() for pydoc |
13 def ClusterSymbols(symbols): | 13 def ClusterSymbols(symbols): |
14 # http://unix.stackexchange.com/questions/223013/function-symbol-gets-part-suf
fix-after-compilation | 14 # http://unix.stackexchange.com/questions/223013/function-symbol-gets-part-suf
fix-after-compilation |
15 # Example name suffixes: | 15 # Example name suffixes: |
16 # [clone .part.322] # GCC | 16 # [clone .part.322] # GCC |
17 # [clone .isra.322] # GCC | 17 # [clone .isra.322] # GCC |
18 # [clone .constprop.1064] # GCC | 18 # [clone .constprop.1064] # GCC |
19 # [clone .11064] # clang | 19 # [clone .11064] # clang |
20 | 20 |
21 # Step 1: Create name map, find clones, collect star syms into replacements. | 21 # Step 1: Create name map, find clones, collect star syms into replacements. |
22 logging.debug('Creating name -> symbol map') | 22 logging.debug('Creating name -> symbol map') |
23 clone_indices = [] | 23 clone_indices = [] |
24 indices_by_full_name = {} | 24 indices_by_full_name = {} |
25 # (name, full_name) -> [(index, sym),...] | 25 # (section_name, name, full_name) -> [(index, sym),...] |
26 replacements_by_name = collections.defaultdict(list) | 26 replacements_by_tup = collections.defaultdict(list) |
27 for i, symbol in enumerate(symbols): | 27 for i, symbol in enumerate(symbols): |
28 if symbol.name.startswith('**'): | 28 if symbol.name.startswith('**'): |
29 # "symbol gap 3" -> "symbol gaps" | 29 # "symbol gap 3" -> "symbol gaps" |
30 name = re.sub(r'\s+\d+$', 's', symbol.name) | 30 name = re.sub(r'\s+\d+( \(.*\))?$', 's', symbol.name) |
31 replacements_by_name[(name, None)].append((i, symbol)) | 31 replacements_by_tup[(symbol.section_name, name, None)].append((i, symbol)) |
32 elif symbol.full_name: | 32 elif symbol.full_name: |
33 if symbol.full_name.endswith(']') and ' [clone ' in symbol.full_name: | 33 if symbol.full_name.endswith(']') and ' [clone ' in symbol.full_name: |
34 clone_indices.append(i) | 34 clone_indices.append(i) |
35 else: | 35 else: |
36 indices_by_full_name[symbol.full_name] = i | 36 indices_by_full_name[symbol.full_name] = i |
37 | 37 |
38 # Step 2: Collect same-named clone symbols. | 38 # Step 2: Collect same-named clone symbols. |
39 logging.debug('Grouping all clones') | 39 logging.debug('Grouping all clones') |
40 group_names_by_index = {} | 40 group_names_by_index = {} |
41 for i in clone_indices: | 41 for i in clone_indices: |
42 symbol = symbols[i] | 42 symbol = symbols[i] |
43 # Multiple attributes could exist, so search from left-to-right. | 43 # Multiple attributes could exist, so search from left-to-right. |
44 stripped_name = symbol.name[:symbol.name.index(' [clone ')] | 44 stripped_name = symbol.name[:symbol.name.index(' [clone ')] |
45 stripped_full_name = symbol.full_name[:symbol.full_name.index(' [clone ')] | 45 stripped_full_name = symbol.full_name[:symbol.full_name.index(' [clone ')] |
46 name_tup = (stripped_name, stripped_full_name) | 46 name_tup = (symbol.section_name, stripped_name, stripped_full_name) |
47 replacement_list = replacements_by_name[name_tup] | 47 replacement_list = replacements_by_tup[name_tup] |
48 | 48 |
49 if not replacement_list: | 49 if not replacement_list: |
50 # First occurance, check for non-clone symbol. | 50 # First occurance, check for non-clone symbol. |
51 non_clone_idx = indices_by_full_name.get(stripped_name) | 51 non_clone_idx = indices_by_full_name.get(stripped_name) |
52 if non_clone_idx is not None: | 52 if non_clone_idx is not None: |
53 non_clone_symbol = symbols[non_clone_idx] | 53 non_clone_symbol = symbols[non_clone_idx] |
54 replacement_list.append((non_clone_idx, non_clone_symbol)) | 54 replacement_list.append((non_clone_idx, non_clone_symbol)) |
55 group_names_by_index[non_clone_idx] = stripped_name | 55 group_names_by_index[non_clone_idx] = stripped_name |
56 | 56 |
57 replacement_list.append((i, symbol)) | 57 replacement_list.append((i, symbol)) |
58 group_names_by_index[i] = stripped_name | 58 group_names_by_index[i] = stripped_name |
59 | 59 |
60 # Step 3: Undo clustering when length=1. | 60 # Step 3: Undo clustering when length=1. |
61 # Removing these groups means Diff() logic must know about [clone] suffix. | 61 # Removing these groups means Diff() logic must know about [clone] suffix. |
62 to_clear = [] | 62 to_clear = [] |
63 for name_tup, replacement_list in replacements_by_name.iteritems(): | 63 for name_tup, replacement_list in replacements_by_tup.iteritems(): |
64 if len(replacement_list) == 1: | 64 if len(replacement_list) == 1: |
65 to_clear.append(name_tup) | 65 to_clear.append(name_tup) |
66 for name_tup in to_clear: | 66 for name_tup in to_clear: |
67 del replacements_by_name[name_tup] | 67 del replacements_by_tup[name_tup] |
68 | 68 |
69 # Step 4: Replace first symbol from each cluster with a SymbolGroup. | 69 # Step 4: Replace first symbol from each cluster with a SymbolGroup. |
70 before_symbol_count = sum(len(x) for x in replacements_by_name.itervalues()) | 70 before_symbol_count = sum(len(x) for x in replacements_by_tup.itervalues()) |
71 logging.debug('Creating %d symbol groups from %d symbols. %d clones had only ' | 71 logging.debug('Creating %d symbol groups from %d symbols. %d clones had only ' |
72 'one symbol.', len(replacements_by_name), before_symbol_count, | 72 'one symbol.', len(replacements_by_tup), before_symbol_count, |
73 len(to_clear)) | 73 len(to_clear)) |
74 | 74 |
75 len_delta = len(replacements_by_name) - before_symbol_count | 75 len_delta = len(replacements_by_tup) - before_symbol_count |
76 grouped_symbols = [None] * (len(symbols) + len_delta) | 76 grouped_symbols = [None] * (len(symbols) + len_delta) |
77 dest_index = 0 | 77 dest_index = 0 |
78 src_index = 0 | 78 src_index = 0 |
79 seen_names = set() | 79 seen_tups = set() |
80 replacement_names_by_index = {} | 80 replacement_tup_by_index = {} |
81 for name_tup, replacement_list in replacements_by_name.iteritems(): | 81 for name_tup, replacement_list in replacements_by_tup.iteritems(): |
82 for tup in replacement_list: | 82 for tup in replacement_list: |
83 replacement_names_by_index[tup[0]] = name_tup | 83 replacement_tup_by_index[tup[0]] = name_tup |
84 | 84 |
85 sorted_items = replacement_names_by_index.items() | 85 sorted_items = replacement_tup_by_index.items() |
86 sorted_items.sort(key=lambda tup: tup[0]) | 86 sorted_items.sort(key=lambda tup: tup[0]) |
87 for index, name_tup in sorted_items: | 87 for index, name_tup in sorted_items: |
88 count = index - src_index | 88 count = index - src_index |
89 grouped_symbols[dest_index:dest_index + count] = ( | 89 grouped_symbols[dest_index:dest_index + count] = ( |
90 symbols[src_index:src_index + count]) | 90 symbols[src_index:src_index + count]) |
91 src_index = index + 1 | 91 src_index = index + 1 |
92 dest_index += count | 92 dest_index += count |
93 if name_tup not in seen_names: | 93 if name_tup not in seen_tups: |
94 seen_names.add(name_tup) | 94 seen_tups.add(name_tup) |
95 group_symbols = [tup[1] for tup in replacements_by_name[name_tup]] | 95 group_symbols = [tup[1] for tup in replacements_by_tup[name_tup]] |
96 grouped_symbols[dest_index] = symbols._CreateTransformed( | 96 grouped_symbols[dest_index] = symbols._CreateTransformed( |
97 group_symbols, name=name_tup[0], full_name=name_tup[1], | 97 group_symbols, name=name_tup[1], full_name=name_tup[2], |
98 section_name=group_symbols[0].section_name) | 98 section_name=name_tup[0]) |
99 dest_index += 1 | 99 dest_index += 1 |
100 | 100 |
101 assert len(grouped_symbols[dest_index:None]) == len(symbols[src_index:None]) | 101 assert len(grouped_symbols[dest_index:None]) == len(symbols[src_index:None]) |
102 grouped_symbols[dest_index:None] = symbols[src_index:None] | 102 grouped_symbols[dest_index:None] = symbols[src_index:None] |
103 logging.debug('Finished clustering symbols.') | 103 logging.debug('Finished clustering symbols.') |
104 return grouped_symbols | 104 return grouped_symbols |
OLD | NEW |