← 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: 2005-07-26 14:06:11 UTC
  • mto: (1092.1.41) (1185.3.4) (974.1.47)
  • mto: This revision was merged to the branch mainline in revision 982.
  • Revision ID: abentley@panoramicfeedback.com-20050726140611-403e366f3c79c1f1
Fixed python invocation

Show diffs side-by-side

added added

removed removed

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