~bzr-pqm/bzr/bzr.dev

1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
1
# Copyright (C) 2005, 2006 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
4183.7.1 by Sabin Iacob
update FSF mailing address
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
16
#
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
17
# Author: Martin Pool <mbp@canonical.com>
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
18
#         Aaron Bentley <aaron.bentley@utoronto.ca>
19
1551.6.13 by Aaron Bentley
Cleanup
20
1711.2.24 by John Arbash Meinel
Late bind to PatienceSequenceMatcher to allow plugin to override.
21
import bzrlib.patiencediff
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
22
23
24
class TextMerge(object):
1551.6.8 by Aaron Bentley
Implemented reprocess for weave
25
    """Base class for text-mergers
26
    Subclasses must implement _merge_struct.
1551.6.13 by Aaron Bentley
Cleanup
27
28
    Many methods produce or consume structured merge information.
29
    This is an iterable of tuples of lists of lines.
30
    Each tuple may have a length of 1 - 3, depending on whether the region it
31
    represents is conflicted.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
32
1551.6.13 by Aaron Bentley
Cleanup
33
    Unconflicted region tuples have length 1.
34
    Conflicted region tuples have length 2 or 3.  Index 1 is text_a, e.g. THIS.
35
    Index 1 is text_b, e.g. OTHER.  Index 2 is optional.  If present, it
36
    represents BASE.
1551.6.8 by Aaron Bentley
Implemented reprocess for weave
37
    """
1551.6.13 by Aaron Bentley
Cleanup
38
    # TODO: Show some version information (e.g. author, date) on conflicted
39
    # regions.
1551.6.14 by Aaron Bentley
Tweaks from merge review
40
    A_MARKER = '<<<<<<< \n'
41
    B_MARKER = '>>>>>>> \n'
42
    SPLIT_MARKER = '=======\n'
43
    def __init__(self, a_marker=A_MARKER, b_marker=B_MARKER,
44
                 split_marker=SPLIT_MARKER):
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
45
        self.a_marker = a_marker
46
        self.b_marker = b_marker
47
        self.split_marker = split_marker
48
1551.6.14 by Aaron Bentley
Tweaks from merge review
49
    def _merge_struct(self):
50
        """Return structured merge info.  Must be implemented by subclasses.
51
        See TextMerge docstring for details on the format.
52
        """
53
        raise NotImplementedError('_merge_struct is abstract')
54
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
55
    def struct_to_lines(self, struct_iter):
1551.6.8 by Aaron Bentley
Implemented reprocess for weave
56
        """Convert merge result tuples to lines"""
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
57
        for lines in struct_iter:
58
            if len(lines) == 1:
59
                for line in lines[0]:
60
                    yield line
61
            else:
62
                yield self.a_marker
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
63
                for line in lines[0]:
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
64
                    yield line
65
                yield self.split_marker
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
66
                for line in lines[1]:
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
67
                    yield line
68
                yield self.b_marker
69
70
    def iter_useful(self, struct_iter):
1551.6.8 by Aaron Bentley
Implemented reprocess for weave
71
        """Iterate through input tuples, skipping empty ones."""
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
72
        for group in struct_iter:
73
            if len(group[0]) > 0:
74
                yield group
75
            elif len(group) > 1 and len(group[1]) > 0:
76
                yield group
77
1551.6.8 by Aaron Bentley
Implemented reprocess for weave
78
    def merge_lines(self, reprocess=False):
1551.6.14 by Aaron Bentley
Tweaks from merge review
79
        """Produce an iterable of lines, suitable for writing to a file
1551.6.13 by Aaron Bentley
Cleanup
80
        Returns a tuple of (line iterable, conflict indicator)
81
        If reprocess is True, a two-way merge will be performed on the
82
        intermediate structure, to reduce conflict regions.
83
        """
1551.6.11 by Aaron Bentley
Switched TextMerge_lines to work on a list
84
        struct = []
1551.6.12 by Aaron Bentley
Indicate conflicts from merge_lines, insead of guessing
85
        conflicts = False
1551.6.11 by Aaron Bentley
Switched TextMerge_lines to work on a list
86
        for group in self.merge_struct(reprocess):
87
            struct.append(group)
1551.6.12 by Aaron Bentley
Indicate conflicts from merge_lines, insead of guessing
88
            if len(group) > 1:
89
                conflicts = True
90
        return self.struct_to_lines(struct), conflicts
1551.6.8 by Aaron Bentley
Implemented reprocess for weave
91
92
    def merge_struct(self, reprocess=False):
1551.6.13 by Aaron Bentley
Cleanup
93
        """Produce structured merge info"""
1551.6.8 by Aaron Bentley
Implemented reprocess for weave
94
        struct_iter = self.iter_useful(self._merge_struct())
95
        if reprocess is True:
96
            return self.reprocess_struct(struct_iter)
97
        else:
98
            return struct_iter
99
100
    @staticmethod
101
    def reprocess_struct(struct_iter):
1551.6.14 by Aaron Bentley
Tweaks from merge review
102
        """ Perform a two-way merge on structural merge info.
1551.6.13 by Aaron Bentley
Cleanup
103
        This reduces the size of conflict regions, but breaks the connection
1551.6.14 by Aaron Bentley
Tweaks from merge review
104
        between the BASE text and the conflict region.
1551.6.13 by Aaron Bentley
Cleanup
105
106
        This process may split a single conflict region into several smaller
107
        ones, but will not introduce new conflicts.
108
        """
1551.6.8 by Aaron Bentley
Implemented reprocess for weave
109
        for group in struct_iter:
110
            if len(group) == 1:
111
                yield group
112
            else:
113
                for newgroup in Merge2(group[0], group[1]).merge_struct():
114
                    yield newgroup
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
115
116
117
class Merge2(TextMerge):
1551.6.14 by Aaron Bentley
Tweaks from merge review
118
    """ Two-way merge.
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
119
    In a two way merge, common regions are shown as unconflicting, and uncommon
120
    regions produce conflicts.
121
    """
1551.6.13 by Aaron Bentley
Cleanup
122
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
123
    def __init__(self, lines_a, lines_b, a_marker=TextMerge.A_MARKER,
124
                 b_marker=TextMerge.B_MARKER,
1551.6.14 by Aaron Bentley
Tweaks from merge review
125
                 split_marker=TextMerge.SPLIT_MARKER):
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
126
        TextMerge.__init__(self, a_marker, b_marker, split_marker)
127
        self.lines_a = lines_a
128
        self.lines_b = lines_b
129
130
    def _merge_struct(self):
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
131
        """Return structured merge info.
1551.6.13 by Aaron Bentley
Cleanup
132
        See TextMerge docstring.
133
        """
1711.2.24 by John Arbash Meinel
Late bind to PatienceSequenceMatcher to allow plugin to override.
134
        sm = bzrlib.patiencediff.PatienceSequenceMatcher(None, self.lines_a, self.lines_b)
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
135
        pos_a = 0
136
        pos_b = 0
137
        for ai, bi, l in sm.get_matching_blocks():
138
            # non-matching lines
139
            yield(self.lines_a[pos_a:ai], self.lines_b[pos_b:bi])
140
            # matching lines
141
            yield(self.lines_a[ai:ai+l],)
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
142
            pos_a = ai + l
1551.6.7 by Aaron Bentley
Implemented two-way merge, refactored weave merge
143
            pos_b = bi + l
144
        # final non-matching lines
145
        yield(self.lines_a[pos_a:-1], self.lines_b[pos_b:-1])