diff options
Diffstat (limited to 'bzrlib/plugins/changelog_merge/changelog_merge.py')
| -rw-r--r-- | bzrlib/plugins/changelog_merge/changelog_merge.py | 199 |
1 files changed, 199 insertions, 0 deletions
diff --git a/bzrlib/plugins/changelog_merge/changelog_merge.py b/bzrlib/plugins/changelog_merge/changelog_merge.py new file mode 100644 index 0000000..2b3ce8a --- /dev/null +++ b/bzrlib/plugins/changelog_merge/changelog_merge.py @@ -0,0 +1,199 @@ +# Copyright (C) 2010 Canonical Ltd +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + +"""Merge logic for changelog_merge plugin.""" + +from __future__ import absolute_import + +import difflib + +from bzrlib import ( + debug, + merge, + urlutils, + ) +from bzrlib.merge3 import Merge3 +from bzrlib.trace import mutter + + +def changelog_entries(lines): + """Return a list of changelog entries. + + :param lines: lines of a changelog file. + :returns: list of entries. Each entry is a tuple of lines. + """ + entries = [] + for line in lines: + if line[0] not in (' ', '\t', '\n'): + # new entry + entries.append([line]) + else: + try: + entry = entries[-1] + except IndexError: + # Cope with leading blank lines. + entries.append([]) + entry = entries[-1] + entry.append(line) + return map(tuple, entries) + + +def entries_to_lines(entries): + """Turn a list of entries into a flat iterable of lines.""" + for entry in entries: + for line in entry: + yield line + + +class ChangeLogMerger(merge.ConfigurableFileMerger): + """Merge GNU-format ChangeLog files.""" + + name_prefix = "changelog" + + def get_filepath(self, params, tree): + """Calculate the path to the file in a tree. + + This is overridden to return just the basename, rather than full path, + so that e.g. if the config says ``changelog_merge_files = ChangeLog``, + then all ChangeLog files in the tree will match (not just one in the + root of the tree). + + :param params: A MergeHookParams describing the file to merge + :param tree: a Tree, e.g. self.merger.this_tree. + """ + return urlutils.basename(tree.id2path(params.file_id)) + + def merge_text(self, params): + """Merge changelog changes. + + * new entries from other will float to the top + * edits to older entries are preserved + """ + # Transform files into lists of changelog entries + this_entries = changelog_entries(params.this_lines) + other_entries = changelog_entries(params.other_lines) + base_entries = changelog_entries(params.base_lines) + try: + result_entries = merge_entries( + base_entries, this_entries, other_entries) + except EntryConflict: + # XXX: generating a nice conflict file would be better + return 'not_applicable', None + # Transform the merged elements back into real blocks of lines. + return 'success', entries_to_lines(result_entries) + + +class EntryConflict(Exception): + pass + + +def default_guess_edits(new_entries, deleted_entries, entry_as_str=''.join): + """Default implementation of guess_edits param of merge_entries. + + This algorithm does O(N^2 * logN) SequenceMatcher.ratio() calls, which is + pretty bad, but it shouldn't be used very often. + """ + deleted_entries_as_strs = map(entry_as_str, deleted_entries) + new_entries_as_strs = map(entry_as_str, new_entries) + result_new = list(new_entries) + result_deleted = list(deleted_entries) + result_edits = [] + sm = difflib.SequenceMatcher() + CUTOFF = 0.8 + while True: + best = None + best_score = CUTOFF + # Compare each new entry with each old entry to find the best match + for new_entry_as_str in new_entries_as_strs: + sm.set_seq1(new_entry_as_str) + for old_entry_as_str in deleted_entries_as_strs: + sm.set_seq2(old_entry_as_str) + score = sm.ratio() + if score > best_score: + best = new_entry_as_str, old_entry_as_str + best_score = score + if best is not None: + # Add the best match to the list of edits, and remove it from the + # the list of new/old entries. Also remove it from the new/old + # lists for the next round. + del_index = deleted_entries_as_strs.index(best[1]) + new_index = new_entries_as_strs.index(best[0]) + result_edits.append( + (result_deleted[del_index], result_new[new_index])) + del deleted_entries_as_strs[del_index], result_deleted[del_index] + del new_entries_as_strs[new_index], result_new[new_index] + else: + # No match better than CUTOFF exists in the remaining new and old + # entries. + break + return result_new, result_deleted, result_edits + + +def merge_entries(base_entries, this_entries, other_entries, + guess_edits=default_guess_edits): + """Merge changelog given base, this, and other versions.""" + m3 = Merge3(base_entries, this_entries, other_entries, allow_objects=True) + result_entries = [] + at_top = True + for group in m3.merge_groups(): + if 'changelog_merge' in debug.debug_flags: + mutter('merge group:\n%r', group) + group_kind = group[0] + if group_kind == 'conflict': + _, base, this, other = group + # Find additions + new_in_other = [ + entry for entry in other if entry not in base] + # Find deletions + deleted_in_other = [ + entry for entry in base if entry not in other] + if at_top and deleted_in_other: + # Magic! Compare deletions and additions to try spot edits + new_in_other, deleted_in_other, edits_in_other = guess_edits( + new_in_other, deleted_in_other) + else: + # Changes not made at the top are always preserved as is, no + # need to try distinguish edits from adds and deletes. + edits_in_other = [] + if 'changelog_merge' in debug.debug_flags: + mutter('at_top: %r', at_top) + mutter('new_in_other: %r', new_in_other) + mutter('deleted_in_other: %r', deleted_in_other) + mutter('edits_in_other: %r', edits_in_other) + # Apply deletes and edits + updated_this = [ + entry for entry in this if entry not in deleted_in_other] + for old_entry, new_entry in edits_in_other: + try: + index = updated_this.index(old_entry) + except ValueError: + # edited entry no longer present in this! Just give up and + # declare a conflict. + raise EntryConflict() + updated_this[index] = new_entry + if 'changelog_merge' in debug.debug_flags: + mutter('updated_this: %r', updated_this) + if at_top: + # Float new entries from other to the top + result_entries = new_in_other + result_entries + else: + result_entries.extend(new_in_other) + result_entries.extend(updated_this) + else: # unchanged, same, a, or b. + lines = group[1] + result_entries.extend(lines) + at_top = False + return result_entries |