/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/merge3.py

  • Committer: Martin Pool
  • Date: 2005-07-05 07:19:12 UTC
  • Revision ID: mbp@sourcefrog.net-20050705071911-6a116ea7c5379658
- Renamed merge3 test suite for easier access.

- New merge approach based on finding triple-matching regions, and comparing
  the regions between them; add find_sync_regions() and some tests for it.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge3.py
 
1
# Copyright (C) 2004, 2005 by 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
 
 
18
 
 
19
def intersect(ra, rb):
 
20
    """Given two ranges return the range where they intersect or None.
 
21
 
 
22
    >>> intersect((0, 10), (0, 6))
 
23
    (0, 6)
 
24
    >>> intersect((0, 10), (5, 15))
 
25
    (5, 10)
 
26
    >>> intersect((0, 10), (10, 15))
 
27
    >>> intersect((0, 9), (10, 15))
 
28
    >>> intersect((0, 9), (7, 15))
 
29
    (7, 9)
 
30
    """
 
31
    assert ra[0] <= ra[1]
 
32
    assert rb[0] <= rb[1]
 
33
    
 
34
    sa = max(ra[0], rb[0])
 
35
    sb = min(ra[1], rb[1])
 
36
    if sa < sb:
 
37
        return sa, sb
 
38
    else:
 
39
        return None
 
40
 
 
41
 
 
42
def threeway(baseline, aline, bline):
 
43
    if baseline == aline:
 
44
        return bline
 
45
    elif baseline == bline:
 
46
        return aline
 
47
    else:
 
48
        return [aline, bline]
 
49
 
 
50
 
 
51
 
 
52
class Merge3(object):
 
53
    """3-way merge of texts.
 
54
 
 
55
    Given BASE, OTHER, THIS, tries to produce a combined text
 
56
    incorporating the changes from both BASE->OTHER and BASE->THIS.
 
57
    All three will typically be sequences of lines."""
 
58
    def __init__(self, base, a, b):
 
59
        self.base = base
 
60
        self.a = a
 
61
        self.b = b
 
62
        from difflib import SequenceMatcher
 
63
        self.a_ops = SequenceMatcher(None, base, a).get_opcodes()
 
64
        self.b_ops = SequenceMatcher(None, base, b).get_opcodes()
 
65
 
 
66
 
 
67
    def merge(self):
 
68
        """Return sequences of matching and conflicting regions.
 
69
 
 
70
        Method is as follows:
 
71
 
 
72
        The two sequences align only on regions which match the base
 
73
        and both descendents.  These are found by doing a two-way diff
 
74
        of each one against the base, and then finding the
 
75
        intersections between those regions.  These "sync regions"
 
76
        are by definition unchanged in both and easily dealt with.
 
77
 
 
78
        The regions in between can be in any of three cases:
 
79
        conflicted, or changed on only one side.
 
80
        """
 
81
 
 
82
        
 
83
    def find_sync_regions(self):
 
84
        """Return a list of sync regions, where both descendents match the base.
 
85
 
 
86
        Generates a list of ((base1, base2), (a1, a2), (b1, b2)). 
 
87
        """
 
88
        from difflib import SequenceMatcher
 
89
        aiter = iter(SequenceMatcher(None, self.base, self.a).get_matching_blocks())
 
90
        biter = iter(SequenceMatcher(None, self.base, self.b).get_matching_blocks())
 
91
 
 
92
        abase, amatch, alen = aiter.next()
 
93
        bbase, bmatch, blen = biter.next()
 
94
 
 
95
        while aiter and biter:
 
96
            # there is an unconflicted block at i; how long does it
 
97
            # extend?  until whichever one ends earlier.
 
98
            i = intersect((abase, abase+alen), (bbase, bbase+blen))
 
99
            if i:
 
100
                intbase = i[0]
 
101
                intend = i[1]
 
102
                intlen = intend - intbase
 
103
 
 
104
                # found a match of base[i[0], i[1]]; this may be less than
 
105
                # the region that matches in either one
 
106
                assert intlen <= alen
 
107
                assert intlen <= blen
 
108
                assert abase <= intbase
 
109
                assert bbase <= intbase
 
110
 
 
111
                asub = amatch + (intbase - abase)
 
112
                bsub = bmatch + (intbase - bbase)
 
113
                aend = asub + intlen
 
114
                bend = bsub + intlen
 
115
 
 
116
                assert self.base[intbase:intend] == self.a[asub:aend], \
 
117
                       (self.base[intbase:intend], self.a[asub:aend])
 
118
                
 
119
                assert self.base[intbase:intend] == self.b[bsub:bend]
 
120
 
 
121
                yield ((intbase, intend),
 
122
                       (asub, aend),
 
123
                       (bsub, bend))
 
124
 
 
125
            # advance whichever one ends first in the base text
 
126
            if (abase + alen) < (bbase + blen):
 
127
                abase, amatch, alen = aiter.next()
 
128
            else:
 
129
                bbase, bmatch, blen = biter.next()
 
130
 
 
131
 
 
132
 
 
133
    def find_unconflicted(self):
 
134
        """Return a list of ranges in base that are not conflicted."""
 
135
        from difflib import SequenceMatcher
 
136
        am = SequenceMatcher(None, self.base, self.a).get_matching_blocks()
 
137
        bm = SequenceMatcher(None, self.base, self.b).get_matching_blocks()
 
138
 
 
139
        unc = []
 
140
 
 
141
        while am and bm:
 
142
            # there is an unconflicted block at i; how long does it
 
143
            # extend?  until whichever one ends earlier.
 
144
            a1 = am[0][0]
 
145
            a2 = a1 + am[0][2]
 
146
            b1 = bm[0][0]
 
147
            b2 = b1 + bm[0][2]
 
148
            i = intersect((a1, a2), (b1, b2))
 
149
            if i:
 
150
                unc.append(i)
 
151
 
 
152
            if a2 < b2:
 
153
                del am[0]
 
154
            else:
 
155
                del bm[0]
 
156
                
 
157
        return unc