← 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-07-04 13:08:55 UTC
  • Revision ID: mbp@sourcefrog.net-20050704130854-7fbef398256b8cab
- start code for built-in diff3-style resolve

- test cases for this

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
class Merge3(object):
 
43
    """3-way merge of texts.
 
44
 
 
45
    Given BASE, OTHER, THIS, tries to produce a combined text
 
46
    incorporating the changes from both BASE->OTHER and BASE->THIS.
 
47
    All three will typically be sequences of lines."""
 
48
    def __init__(self, base, a, b):
 
49
        self.base = base
 
50
        self.a = a
 
51
        self.b = b
 
52
 
 
53
        #from difflib import SequenceMatcher
 
54
 
 
55
        #self.a_ops = SequenceMatcher(None, self.base, self.a).get_opcodes()
 
56
        #self.b_ops = SequenceMatcher(None, self.base, self.b).get_opcodes()
 
57
 
 
58
        
 
59
    def find_conflicts(self):
 
60
        """Return a list of conflict regions.
 
61
 
 
62
        Each entry is given as (base1, base2, a1, a2, b1, b2).
 
63
 
 
64
        This indicates that the range [base1,base2] can be replaced by either
 
65
        [a1,a2] or [b1,b2].
 
66
        """
 
67
 
 
68
 
 
69
    def find_unconflicted(self):
 
70
        """Return a list of ranges in base that are not conflicted."""
 
71
        from difflib import SequenceMatcher
 
72
        am = SequenceMatcher(None, self.base, self.a).get_matching_blocks()
 
73
        bm = SequenceMatcher(None, self.base, self.b).get_matching_blocks()
 
74
 
 
75
        unc = []
 
76
 
 
77
        while am and bm:
 
78
            # there is an unconflicted block at i; how long does it
 
79
            # extend?  until whichever one ends earlier.
 
80
            a1 = am[0][0]
 
81
            a2 = a1 + am[0][2]
 
82
            b1 = bm[0][0]
 
83
            b2 = b1 + bm[0][2]
 
84
            i = intersect((a1, a2), (b1, b2))
 
85
            if i:
 
86
                unc.append(i)
 
87
 
 
88
            if a2 < b2:
 
89
                del am[0]
 
90
            else:
 
91
                del bm[0]
 
92
                
 
93
        return unc