aboutsummaryrefslogtreecommitdiff
path: root/llvm/utils/UpdateTestChecks/common.py
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/utils/UpdateTestChecks/common.py')
-rw-r--r--llvm/utils/UpdateTestChecks/common.py130
1 files changed, 103 insertions, 27 deletions
diff --git a/llvm/utils/UpdateTestChecks/common.py b/llvm/utils/UpdateTestChecks/common.py
index b861bd0..759fc5d 100644
--- a/llvm/utils/UpdateTestChecks/common.py
+++ b/llvm/utils/UpdateTestChecks/common.py
@@ -1534,14 +1534,58 @@ def remap_metavar_names(
candidate_matches = find_diff_matching(lhs_lines, rhs_lines)
- # Apply commits greedily on a match-by-match basis
- matches = [(-1, -1)]
- committed_anything = False
+ candidate_matches = [
+ (old_begin + lhs_idx, new_begin + rhs_idx)
+ for lhs_idx, rhs_idx in candidate_matches
+ ]
+
+ # Candidate matches may conflict if they require conflicting mappings of
+ # names. We want to determine a large set of compatible candidates,
+ # because that leads to a small diff.
+ #
+ # We think of the candidates as vertices in a conflict graph. The
+ # conflict graph has edges between incompatible candidates. We want to
+ # find a large independent set in this graph.
+ #
+ # Greedily selecting candidates and removing incompatible ones has the
+ # disadvantage that making few bad decisions early on can have huge
+ # consequences.
+ #
+ # Instead, we implicitly compute multiple independent sets by greedily
+ # assigning a *coloring* to the conflict graph. Then, we select the
+ # largest color class (which is the largest independent set we found),
+ # commit to all candidates in it, and recurse.
+ #
+ # Note that we don't actually materialize the conflict graph. Instead,
+ # each color class tracks the information needed to decide implicitly
+ # whether a vertex conflicts (has an edge to) any of the vertices added
+ # to the color class so far.
+ class Color:
+ def __init__(self):
+ # (lhs_idx, rhs_idx) of matches in this color
+ self.matches = []
+
+ # rhs_name -> lhs_name mappings required by this color
+ self.mapping = {}
+
+ # lhs_names committed for this color
+ self.committed = set()
+
+ colors = []
+
for lhs_idx, rhs_idx in candidate_matches:
lhs_line = old_line_infos[lhs_idx]
rhs_line = new_line_infos[rhs_idx]
- local_commits = {}
+ # We scan through the uncommitted names in the candidate line and
+ # filter out the color classes to which the candidate could be
+ # assigned.
+ #
+ # Simultaneously, we prepare a new color class in case the candidate
+ # conflicts with all colors that have been established so far.
+ compatible_colors = colors[:]
+ new_color = Color()
+ new_color.matches.append((lhs_idx, rhs_idx))
for lhs_value, rhs_value in zip(lhs_line.values, rhs_line.values):
if new_mapping[rhs_value.name] in committed_names:
@@ -1554,39 +1598,71 @@ def remap_metavar_names(
else:
break
- if rhs_value.name in local_commits:
+ if rhs_value.name in new_color.mapping:
# Same, but for a possible commit happening on the same line
- if local_commits[rhs_value.name] == lhs_value.name:
+ if new_color.color[rhs_value.name] == lhs_value.name:
continue
else:
break
- if lhs_value.name in committed_names:
- # We can't map this value because the name we would map it to has already been
- # committed for something else. Give up on this line.
+ if (
+ lhs_value.name in committed_names
+ or lhs_value.name in new_color.committed
+ ):
+ # We can't map this value because the name we would map it
+ # to has already been committed for something else. Give up
+ # on this line.
break
- local_commits[rhs_value.name] = lhs_value.name
- else:
- # No reason not to add any commitments for this line
- for rhs_var, lhs_var in local_commits.items():
- new_mapping[rhs_var] = lhs_var
- committed_names.add(lhs_var)
- committed_anything = True
-
- if (
- lhs_var != rhs_var
- and lhs_var in new_mapping
- and new_mapping[lhs_var] == lhs_var
- ):
- new_mapping[lhs_var] = "conflict_" + lhs_var
+ new_color.mapping[rhs_value.name] = lhs_value.name
+ new_color.committed.add(lhs_value.name)
- matches.append((lhs_idx, rhs_idx))
+ color_idx = 0
+ while color_idx < len(compatible_colors):
+ color = compatible_colors[color_idx]
+ compatible = True
+ if rhs_value.name in color.mapping:
+ compatible = color.mapping[rhs_value.name] == lhs_value.name
+ else:
+ compatible = lhs_value.name not in color.committed
+ if compatible:
+ color_idx += 1
+ else:
+ del compatible_colors[color_idx]
+ else:
+ # We never broke out of the loop, which means that at a minimum,
+ # this line is viable standalone
+ if compatible_colors:
+ color = max(compatible_colors, key=lambda color: len(color.matches))
+ color.mapping.update(new_color.mapping)
+ color.committed.update(new_color.committed)
+ color.matches.append((lhs_idx, rhs_idx))
+ else:
+ colors.append(new_color)
+
+ if colors:
+ # Pick the largest color class. This gives us a large independent
+ # (non-conflicting) set of candidate matches. Assign all names
+ # required by the independent set and recurse.
+ max_color = max(colors, key=lambda color: len(color.matches))
+
+ for rhs_var, lhs_var in max_color.mapping.items():
+ new_mapping[rhs_var] = lhs_var
+ committed_names.add(lhs_var)
+
+ if (
+ lhs_var != rhs_var
+ and lhs_var in new_mapping
+ and new_mapping[lhs_var] == lhs_var
+ ):
+ new_mapping[lhs_var] = "conflict_" + lhs_var
- matches.append((old_end, new_end))
+ matches = (
+ [(old_begin - 1, new_begin - 1)]
+ + max_color.matches
+ + [(old_end, new_end)]
+ )
- # Recursively handle sequences between matches
- if committed_anything:
for (lhs_prev, rhs_prev), (lhs_next, rhs_next) in zip(matches, matches[1:]):
recurse(lhs_prev + 1, lhs_next, rhs_prev + 1, rhs_next)