← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge3.py

  • Committer: Martin Pool
  • Date: 2005-06-29 04:11:40 UTC
  • Revision ID: mbp@sourcefrog.net-20050629041140-6b17e65a23ffdf47
Merge John's log patch:

implements bzr log --forward --verbose
optimizes so that only logs to be printed are read (rather than reading
all and filtering out unwanted).

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