← 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-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
39
39
        return None
40
40
 
41
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
 
42
52
class Merge3(object):
43
53
    """3-way merge of texts.
44
54
 
49
59
        self.base = base
50
60
        self.a = a
51
61
        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()
 
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
        """
57
81
 
58
82
        
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].
 
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)). 
66
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
 
67
131
 
68
132
 
69
133
    def find_unconflicted(self):