~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/plugins/changelog_merge/changelog_merge.py

  • Committer: Vincent Ladeuil
  • Date: 2011-07-06 09:22:00 UTC
  • mfrom: (6008 +trunk)
  • mto: (6012.1.1 trunk)
  • mto: This revision was merged to the branch mainline in revision 6013.
  • Revision ID: v.ladeuil+lp@free.fr-20110706092200-7iai2mwzc0sqdsvf
MergingĀ inĀ trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
# Copyright (C) 2010 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
"""Merge logic for changelog_merge plugin."""
 
18
 
 
19
import difflib
 
20
 
 
21
from bzrlib import merge
 
22
from bzrlib import debug
 
23
from bzrlib.merge3 import Merge3
 
24
from bzrlib.trace import mutter
 
25
 
 
26
 
 
27
def changelog_entries(lines):
 
28
    """Return a list of changelog entries.
 
29
 
 
30
    :param lines: lines of a changelog file.
 
31
    :returns: list of entries.  Each entry is a tuple of lines.
 
32
    """
 
33
    entries = []
 
34
    for line in lines:
 
35
        if line[0] not in (' ', '\t', '\n'):
 
36
            # new entry
 
37
            entries.append([line])
 
38
        else:
 
39
            try:
 
40
                entry = entries[-1]
 
41
            except IndexError:
 
42
                # Cope with leading blank lines.
 
43
                entries.append([])
 
44
                entry = entries[-1]
 
45
            entry.append(line)
 
46
    return map(tuple, entries)
 
47
 
 
48
 
 
49
def entries_to_lines(entries):
 
50
    """Turn a list of entries into a flat iterable of lines."""
 
51
    for entry in entries:
 
52
        for line in entry:
 
53
            yield line
 
54
 
 
55
 
 
56
class ChangeLogMerger(merge.ConfigurableFileMerger):
 
57
    """Merge GNU-format ChangeLog files."""
 
58
 
 
59
    name_prefix = "changelog"
 
60
 
 
61
    def get_filepath(self, params, tree):
 
62
        """Calculate the path to the file in a tree.
 
63
 
 
64
        This is overridden to return just the basename, rather than full path,
 
65
        so that e.g. if the config says ``changelog_merge_files = ChangeLog``,
 
66
        then all ChangeLog files in the tree will match (not just one in the
 
67
        root of the tree).
 
68
        
 
69
        :param params: A MergeHookParams describing the file to merge
 
70
        :param tree: a Tree, e.g. self.merger.this_tree.
 
71
        """
 
72
        return tree.inventory[params.file_id].name
 
73
 
 
74
    def merge_text(self, params):
 
75
        """Merge changelog changes.
 
76
 
 
77
         * new entries from other will float to the top
 
78
         * edits to older entries are preserved
 
79
        """
 
80
        # Transform files into lists of changelog entries
 
81
        this_entries = changelog_entries(params.this_lines)
 
82
        other_entries = changelog_entries(params.other_lines)
 
83
        base_entries = changelog_entries(params.base_lines)
 
84
        try:
 
85
            result_entries = merge_entries(
 
86
                base_entries, this_entries, other_entries)
 
87
        except EntryConflict:
 
88
            # XXX: generating a nice conflict file would be better
 
89
            return 'not_applicable', None
 
90
        # Transform the merged elements back into real blocks of lines.
 
91
        return 'success', entries_to_lines(result_entries)
 
92
 
 
93
 
 
94
class EntryConflict(Exception):
 
95
    pass
 
96
 
 
97
 
 
98
def default_guess_edits(new_entries, deleted_entries, entry_as_str=''.join):
 
99
    """Default implementation of guess_edits param of merge_entries.
 
100
 
 
101
    This algorithm does O(N^2 * logN) SequenceMatcher.ratio() calls, which is
 
102
    pretty bad, but it shouldn't be used very often.
 
103
    """
 
104
    deleted_entries_as_strs = map(entry_as_str, deleted_entries)
 
105
    new_entries_as_strs = map(entry_as_str, new_entries)
 
106
    result_new = list(new_entries)
 
107
    result_deleted = list(deleted_entries)
 
108
    result_edits = []
 
109
    sm = difflib.SequenceMatcher()
 
110
    CUTOFF = 0.8
 
111
    while True:
 
112
        best = None
 
113
        best_score = CUTOFF
 
114
        # Compare each new entry with each old entry to find the best match
 
115
        for new_entry_as_str in new_entries_as_strs:
 
116
            sm.set_seq1(new_entry_as_str)
 
117
            for old_entry_as_str in deleted_entries_as_strs:
 
118
                sm.set_seq2(old_entry_as_str)
 
119
                score = sm.ratio()
 
120
                if score > best_score:
 
121
                    best = new_entry_as_str, old_entry_as_str
 
122
                    best_score = score
 
123
        if best is not None:
 
124
            # Add the best match to the list of edits, and remove it from the
 
125
            # the list of new/old entries.  Also remove it from the new/old
 
126
            # lists for the next round.
 
127
            del_index = deleted_entries_as_strs.index(best[1])
 
128
            new_index = new_entries_as_strs.index(best[0])
 
129
            result_edits.append(
 
130
                (result_deleted[del_index], result_new[new_index]))
 
131
            del deleted_entries_as_strs[del_index], result_deleted[del_index]
 
132
            del new_entries_as_strs[new_index], result_new[new_index]
 
133
        else:
 
134
            # No match better than CUTOFF exists in the remaining new and old
 
135
            # entries.
 
136
            break
 
137
    return result_new, result_deleted, result_edits
 
138
 
 
139
 
 
140
def merge_entries(base_entries, this_entries, other_entries,
 
141
        guess_edits=default_guess_edits):
 
142
    """Merge changelog given base, this, and other versions."""
 
143
    m3 = Merge3(base_entries, this_entries, other_entries, allow_objects=True)
 
144
    result_entries = []
 
145
    at_top = True
 
146
    for group in m3.merge_groups():
 
147
        if 'changelog_merge' in debug.debug_flags:
 
148
            mutter('merge group:\n%r', group)
 
149
        group_kind = group[0]
 
150
        if group_kind == 'conflict':
 
151
            _, base, this, other = group
 
152
            # Find additions
 
153
            new_in_other = [
 
154
                entry for entry in other if entry not in base]
 
155
            # Find deletions
 
156
            deleted_in_other = [
 
157
                entry for entry in base if entry not in other]
 
158
            if at_top and deleted_in_other:
 
159
                # Magic!  Compare deletions and additions to try spot edits
 
160
                new_in_other, deleted_in_other, edits_in_other = guess_edits(
 
161
                    new_in_other, deleted_in_other)
 
162
            else:
 
163
                # Changes not made at the top are always preserved as is, no
 
164
                # need to try distinguish edits from adds and deletes.
 
165
                edits_in_other = []
 
166
            if 'changelog_merge' in debug.debug_flags:
 
167
                mutter('at_top: %r', at_top)
 
168
                mutter('new_in_other: %r', new_in_other)
 
169
                mutter('deleted_in_other: %r', deleted_in_other)
 
170
                mutter('edits_in_other: %r', edits_in_other)
 
171
            # Apply deletes and edits
 
172
            updated_this = [
 
173
                entry for entry in this if entry not in deleted_in_other]
 
174
            for old_entry, new_entry in edits_in_other:
 
175
                try:
 
176
                    index = updated_this.index(old_entry)
 
177
                except ValueError:
 
178
                    # edited entry no longer present in this!  Just give up and
 
179
                    # declare a conflict.
 
180
                    raise EntryConflict()
 
181
                updated_this[index] = new_entry
 
182
            if 'changelog_merge' in debug.debug_flags:
 
183
                mutter('updated_this: %r', updated_this)
 
184
            if at_top:
 
185
                # Float new entries from other to the top
 
186
                result_entries = new_in_other + result_entries
 
187
            else:
 
188
                result_entries.extend(new_in_other)
 
189
            result_entries.extend(updated_this)
 
190
        else: # unchanged, same, a, or b.
 
191
            lines = group[1]
 
192
            result_entries.extend(lines)
 
193
        at_top = False
 
194
    return result_entries