← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/textmerge.py

  • Committer: Aaron Bentley
  • Date: 2007-06-21 01:58:29 UTC
  • mto: This revision was merged to the branch mainline in revision 2542.
  • Revision ID: aaron.bentley@utoronto.ca-20070621015829-b62l2d1ehuvgnr3x
Fix iter_topo_order to permit un-included parents

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/textmerge.py
 
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
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
#
 
17
# Author: Martin Pool <mbp@canonical.com> 
 
18
#         Aaron Bentley <aaron.bentley@utoronto.ca>
 
19
 
 
20
 
 
21
import bzrlib.patiencediff
 
22
 
 
23
 
 
24
class TextMerge(object):
 
25
    """Base class for text-mergers
 
26
    Subclasses must implement _merge_struct.
 
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.
 
32
    
 
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.
 
37
    """
 
38
    # TODO: Show some version information (e.g. author, date) on conflicted
 
39
    # regions.
 
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):
 
45
        self.a_marker = a_marker
 
46
        self.b_marker = b_marker
 
47
        self.split_marker = split_marker
 
48
 
 
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
 
 
55
    def struct_to_lines(self, struct_iter):
 
56
        """Convert merge result tuples to lines"""
 
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
 
63
                for line in lines[0]: 
 
64
                    yield line
 
65
                yield self.split_marker
 
66
                for line in lines[1]: 
 
67
                    yield line
 
68
                yield self.b_marker
 
69
 
 
70
    def iter_useful(self, struct_iter):
 
71
        """Iterate through input tuples, skipping empty ones."""
 
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
 
 
78
    def merge_lines(self, reprocess=False):
 
79
        """Produce an iterable of lines, suitable for writing to a file
 
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
        """
 
84
        struct = []
 
85
        conflicts = False
 
86
        for group in self.merge_struct(reprocess):
 
87
            struct.append(group)
 
88
            if len(group) > 1:
 
89
                conflicts = True
 
90
        return self.struct_to_lines(struct), conflicts
 
91
 
 
92
    def merge_struct(self, reprocess=False):
 
93
        """Produce structured merge info"""
 
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):
 
102
        """ Perform a two-way merge on structural merge info.
 
103
        This reduces the size of conflict regions, but breaks the connection
 
104
        between the BASE text and the conflict region.
 
105
 
 
106
        This process may split a single conflict region into several smaller
 
107
        ones, but will not introduce new conflicts.
 
108
        """
 
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
 
115
 
 
116
 
 
117
class Merge2(TextMerge):
 
118
    """ Two-way merge.
 
119
    In a two way merge, common regions are shown as unconflicting, and uncommon
 
120
    regions produce conflicts.
 
121
    """
 
122
 
 
123
    def __init__(self, lines_a, lines_b, a_marker=TextMerge.A_MARKER, 
 
124
                 b_marker=TextMerge.B_MARKER, 
 
125
                 split_marker=TextMerge.SPLIT_MARKER):
 
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):
 
131
        """Return structured merge info.  
 
132
        See TextMerge docstring.
 
133
        """
 
134
        sm = bzrlib.patiencediff.PatienceSequenceMatcher(None, self.lines_a, self.lines_b)
 
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],)
 
142
            pos_a = ai + l 
 
143
            pos_b = bi + l
 
144
        # final non-matching lines
 
145
        yield(self.lines_a[pos_a:-1], self.lines_b[pos_b:-1])