← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge3.py

  • Committer: Robert Collins
  • Date: 2007-07-15 15:40:37 UTC
  • mto: (2592.3.33 repository)
  • mto: This revision was merged to the branch mainline in revision 2624.
  • Revision ID: robertc@robertcollins.net-20070715154037-3ar8g89decddc9su
Make GraphIndex accept nodes as key, value, references, so that the method
signature is closer to what a simple key->value index delivers. Also
change the behaviour when the reference list count is zero to accept
key, value as nodes, and emit key, value to make it identical in that case
to a simple key->value index. This may not be a good idea, but for now it
seems ok.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge3.py
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
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
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
 
18
18
# mbp: "you know that thing where cvs gives you conflict markers?"
36
36
    >>> intersect((0, 9), (7, 15))
37
37
    (7, 9)
38
38
    """
39
 
    # preconditions: (ra[0] <= ra[1]) and (rb[0] <= rb[1])
40
 
 
 
39
    assert ra[0] <= ra[1]
 
40
    assert rb[0] <= rb[1]
 
41
    
41
42
    sa = max(ra[0], rb[0])
42
43
    sb = min(ra[1], rb[1])
43
44
    if sa < sb:
56
57
            return False
57
58
    else:
58
59
        return True
59
 
 
 
60
        
60
61
 
61
62
 
62
63
 
66
67
    Given BASE, OTHER, THIS, tries to produce a combined text
67
68
    incorporating the changes from both BASE->OTHER and BASE->THIS.
68
69
    All three will typically be sequences of lines."""
69
 
    def __init__(self, base, a, b, is_cherrypick=False):
 
70
    def __init__(self, base, a, b):
70
71
        check_text_lines(base)
71
72
        check_text_lines(a)
72
73
        check_text_lines(b)
73
74
        self.base = base
74
75
        self.a = a
75
76
        self.b = b
76
 
        self.is_cherrypick = is_cherrypick
 
77
 
 
78
 
77
79
 
78
80
    def merge_lines(self,
79
81
                    name_a=None,
128
130
                yield end_marker + newline
129
131
            else:
130
132
                raise ValueError(what)
 
133
        
 
134
        
 
135
 
 
136
 
131
137
 
132
138
    def merge_annotated(self):
133
139
        """Return merge with conflicts, showing origin of lines.
134
140
 
135
 
        Most useful for debugging merge.
 
141
        Most useful for debugging merge.        
136
142
        """
137
143
        for t in self.merge_regions():
138
144
            what = t[0]
155
161
                yield '>>>>\n'
156
162
            else:
157
163
                raise ValueError(what)
 
164
        
 
165
        
 
166
 
 
167
 
158
168
 
159
169
    def merge_groups(self):
160
170
        """Yield sequence of line groups.  Each one is a tuple:
190
200
            else:
191
201
                raise ValueError(what)
192
202
 
 
203
 
193
204
    def merge_regions(self):
194
205
        """Return sequences of matching and conflicting regions.
195
206
 
219
230
 
220
231
        # section a[0:ia] has been disposed of, etc
221
232
        iz = ia = ib = 0
222
 
 
 
233
        
223
234
        for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
 
235
            #print 'match base [%d:%d]' % (zmatch, zend)
 
236
            
224
237
            matchlen = zend - zmatch
225
 
            # invariants:
226
 
            #   matchlen >= 0
227
 
            #   matchlen == (aend - amatch)
228
 
            #   matchlen == (bend - bmatch)
 
238
            assert matchlen >= 0
 
239
            assert matchlen == (aend - amatch)
 
240
            assert matchlen == (bend - bmatch)
 
241
            
229
242
            len_a = amatch - ia
230
243
            len_b = bmatch - ib
231
244
            len_base = zmatch - iz
232
 
            # invariants:
233
 
            # assert len_a >= 0
234
 
            # assert len_b >= 0
235
 
            # assert len_base >= 0
 
245
            assert len_a >= 0
 
246
            assert len_b >= 0
 
247
            assert len_base >= 0
236
248
 
237
249
            #print 'unmatched a=%d, b=%d' % (len_a, len_b)
238
250
 
239
251
            if len_a or len_b:
240
252
                # try to avoid actually slicing the lists
 
253
                equal_a = compare_range(self.a, ia, amatch,
 
254
                                        self.base, iz, zmatch)
 
255
                equal_b = compare_range(self.b, ib, bmatch,
 
256
                                        self.base, iz, zmatch)
241
257
                same = compare_range(self.a, ia, amatch,
242
258
                                     self.b, ib, bmatch)
243
259
 
244
260
                if same:
245
261
                    yield 'same', ia, amatch
 
262
                elif equal_a and not equal_b:
 
263
                    yield 'b', ib, bmatch
 
264
                elif equal_b and not equal_a:
 
265
                    yield 'a', ia, amatch
 
266
                elif not equal_a and not equal_b:
 
267
                    yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
246
268
                else:
247
 
                    equal_a = compare_range(self.a, ia, amatch,
248
 
                                            self.base, iz, zmatch)
249
 
                    equal_b = compare_range(self.b, ib, bmatch,
250
 
                                            self.base, iz, zmatch)
251
 
                    if equal_a and not equal_b:
252
 
                        yield 'b', ib, bmatch
253
 
                    elif equal_b and not equal_a:
254
 
                        yield 'a', ia, amatch
255
 
                    elif not equal_a and not equal_b:
256
 
                        if self.is_cherrypick:
257
 
                            for node in self._refine_cherrypick_conflict(
258
 
                                                    iz, zmatch, ia, amatch,
259
 
                                                    ib, bmatch):
260
 
                                yield node
261
 
                        else:
262
 
                            yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
263
 
                    else:
264
 
                        raise AssertionError("can't handle a=b=base but unmatched")
 
269
                    raise AssertionError("can't handle a=b=base but unmatched")
265
270
 
266
271
                ia = amatch
267
272
                ib = bmatch
270
275
            # if the same part of the base was deleted on both sides
271
276
            # that's OK, we can just skip it.
272
277
 
 
278
                
273
279
            if matchlen > 0:
274
 
                # invariants:
275
 
                # assert ia == amatch
276
 
                # assert ib == bmatch
277
 
                # assert iz == zmatch
278
 
 
 
280
                assert ia == amatch
 
281
                assert ib == bmatch
 
282
                assert iz == zmatch
 
283
                
279
284
                yield 'unchanged', zmatch, zend
280
285
                iz = zend
281
286
                ia = aend
282
287
                ib = bend
283
 
 
284
 
    def _refine_cherrypick_conflict(self, zstart, zend, astart, aend, bstart, bend):
285
 
        """When cherrypicking b => a, ignore matches with b and base."""
286
 
        # Do not emit regions which match, only regions which do not match
287
 
        matches = bzrlib.patiencediff.PatienceSequenceMatcher(None,
288
 
            self.base[zstart:zend], self.b[bstart:bend]).get_matching_blocks()
289
 
        last_base_idx = 0
290
 
        last_b_idx = 0
291
 
        last_b_idx = 0
292
 
        yielded_a = False
293
 
        for base_idx, b_idx, match_len in matches:
294
 
            conflict_z_len = base_idx - last_base_idx
295
 
            conflict_b_len = b_idx - last_b_idx
296
 
            if conflict_b_len == 0: # There are no lines in b which conflict,
297
 
                                    # so skip it
298
 
                pass
299
 
            else:
300
 
                if yielded_a:
301
 
                    yield ('conflict',
302
 
                           zstart + last_base_idx, zstart + base_idx,
303
 
                           aend, aend, bstart + last_b_idx, bstart + b_idx)
304
 
                else:
305
 
                    # The first conflict gets the a-range
306
 
                    yielded_a = True
307
 
                    yield ('conflict', zstart + last_base_idx, zstart +
308
 
                    base_idx,
309
 
                           astart, aend, bstart + last_b_idx, bstart + b_idx)
310
 
            last_base_idx = base_idx + match_len
311
 
            last_b_idx = b_idx + match_len
312
 
        if last_base_idx != zend - zstart or last_b_idx != bend - bstart:
313
 
            if yielded_a:
314
 
                yield ('conflict', zstart + last_base_idx, zstart + base_idx,
315
 
                       aend, aend, bstart + last_b_idx, bstart + b_idx)
316
 
            else:
317
 
                # The first conflict gets the a-range
318
 
                yielded_a = True
319
 
                yield ('conflict', zstart + last_base_idx, zstart + base_idx,
320
 
                       astart, aend, bstart + last_b_idx, bstart + b_idx)
321
 
        if not yielded_a:
322
 
            yield ('conflict', zstart, zend, astart, aend, bstart, bend)
 
288
    
323
289
 
324
290
    def reprocess_merge_regions(self, merge_regions):
325
291
        """Where there are conflict regions, remove the agreed lines.
326
292
 
327
 
        Lines where both A and B have made the same changes are
 
293
        Lines where both A and B have made the same changes are 
328
294
        eliminated.
329
295
        """
330
296
        for region in merge_regions:
352
318
            if reg is not None:
353
319
                yield reg
354
320
 
 
321
 
355
322
    @staticmethod
356
323
    def mismatch_region(next_a, region_ia,  next_b, region_ib):
357
324
        if next_a < region_ia or next_b < region_ib:
358
325
            return 'conflict', None, None, next_a, region_ia, next_b, region_ib
 
326
            
359
327
 
360
328
    def find_sync_regions(self):
361
329
        """Return a list of sync regions, where both descendents match the base.
388
356
 
389
357
                # found a match of base[i[0], i[1]]; this may be less than
390
358
                # the region that matches in either one
391
 
                # assert intlen <= alen
392
 
                # assert intlen <= blen
393
 
                # assert abase <= intbase
394
 
                # assert bbase <= intbase
 
359
                assert intlen <= alen
 
360
                assert intlen <= blen
 
361
                assert abase <= intbase
 
362
                assert bbase <= intbase
395
363
 
396
364
                asub = amatch + (intbase - abase)
397
365
                bsub = bmatch + (intbase - bbase)
398
366
                aend = asub + intlen
399
367
                bend = bsub + intlen
400
368
 
401
 
                # assert self.base[intbase:intend] == self.a[asub:aend], \
402
 
                #       (self.base[intbase:intend], self.a[asub:aend])
403
 
                # assert self.base[intbase:intend] == self.b[bsub:bend]
 
369
                assert self.base[intbase:intend] == self.a[asub:aend], \
 
370
                       (self.base[intbase:intend], self.a[asub:aend])
 
371
 
 
372
                assert self.base[intbase:intend] == self.b[bsub:bend]
404
373
 
405
374
                sl.append((intbase, intend,
406
375
                           asub, aend,
407
376
                           bsub, bend))
 
377
 
408
378
            # advance whichever one ends first in the base text
409
379
            if (abase + alen) < (bbase + blen):
410
380
                ia += 1
411
381
            else:
412
382
                ib += 1
413
 
 
 
383
            
414
384
        intbase = len(self.base)
415
385
        abase = len(self.a)
416
386
        bbase = len(self.b)
418
388
 
419
389
        return sl
420
390
 
 
391
 
 
392
 
421
393
    def find_unconflicted(self):
422
394
        """Return a list of ranges in base that are not conflicted."""
423
395
        am = bzrlib.patiencediff.PatienceSequenceMatcher(
442
414
                del am[0]
443
415
            else:
444
416
                del bm[0]
445
 
 
 
417
                
446
418
        return unc
447
419
 
448
420