← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

Moved the merge stuff into merge.py

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge.py
18
18
 
19
19
import os
20
20
import errno
 
21
from tempfile import mkdtemp
 
22
from shutil import rmtree
21
23
 
22
24
import bzrlib
23
25
from bzrlib.branch import Branch
27
29
                           NoCommonAncestor,
28
30
                           NoCommits,
29
31
                           NoSuchRevision,
 
32
                           NoSuchFile,
30
33
                           NotBranchError,
31
34
                           NotVersionedError,
32
35
                           UnrelatedBranches,
34
37
                           )
35
38
from bzrlib.fetch import greedy_fetch, fetch
36
39
import bzrlib.osutils
 
40
from bzrlib.merge3 import Merge3
37
41
from bzrlib.osutils import rename, pathjoin
38
42
from bzrlib.revision import common_ancestor, is_ancestor, NULL_REVISION
39
 
from bzrlib.transform import (Merge3Merger, WeaveMerger, Diff3Merger)
 
43
from bzrlib.transform import TreeTransform, resolve_conflicts, FinalPaths, create_by_entry, unique_add
40
44
from bzrlib.trace import mutter, warning, note
41
45
from bzrlib.workingtree import WorkingTree
42
46
 
97
101
                interesting_ids=interesting_ids)
98
102
 
99
103
 
100
 
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
101
 
                backup_files=False, 
102
 
                merge_type=Merge3Merger, 
103
 
                interesting_ids=None, 
104
 
                show_base=False, 
105
 
                reprocess=False, 
106
 
                other_rev_id=None,
107
 
                interesting_files=None,
108
 
                this_tree=None):
109
 
    """Primary interface for merging. 
110
 
 
111
 
        typical use is probably 
112
 
        'merge_inner(branch, branch.get_revision_tree(other_revision),
113
 
                     branch.get_revision_tree(base_revision))'
114
 
        """
115
 
    if this_tree is None:
116
 
        this_tree = this_branch.working_tree()
117
 
    merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree)
118
 
    merger.backup_files = backup_files
119
 
    merger.merge_type = merge_type
120
 
    merger.interesting_ids = interesting_ids
121
 
    if interesting_files:
122
 
        assert not interesting_ids, ('Only supply interesting_ids'
123
 
                                     ' or interesting_files')
124
 
        merger._set_interesting_files(interesting_files)
125
 
    merger.show_base = show_base 
126
 
    merger.reprocess = reprocess
127
 
    merger.other_rev_id = other_rev_id
128
 
    merger.other_basis = other_rev_id
129
 
    return merger.do_merge()
130
 
 
131
 
 
132
104
class Merger(object):
133
105
    def __init__(self, this_branch, other_tree=None, base_tree=None, this_tree=None):
134
106
        object.__init__(self)
352
324
        return new_inventory_list
353
325
 
354
326
 
 
327
class Merge3Merger(object):
 
328
    requires_base = True
 
329
    supports_reprocess = True
 
330
    supports_show_base = True
 
331
    history_based = False
 
332
    def __init__(self, working_tree, this_tree, base_tree, other_tree, 
 
333
                 reprocess=False, show_base=False):
 
334
        object.__init__(self)
 
335
        self.this_tree = working_tree
 
336
        self.base_tree = base_tree
 
337
        self.other_tree = other_tree
 
338
        self._raw_conflicts = []
 
339
        self.cooked_conflicts = []
 
340
        self.reprocess = reprocess
 
341
        self.show_base = show_base
 
342
 
 
343
        all_ids = set(base_tree)
 
344
        all_ids.update(other_tree)
 
345
        self.tt = TreeTransform(working_tree)
 
346
        try:
 
347
            for file_id in all_ids:
 
348
                self.merge_names(file_id)
 
349
                file_status = self.merge_contents(file_id)
 
350
                self.merge_executable(file_id, file_status)
 
351
                
 
352
            resolve_conflicts(self.tt)
 
353
            self.cook_conflicts()
 
354
            self.tt.apply()
 
355
        finally:
 
356
            try:
 
357
                self.tt.finalize()
 
358
            except:
 
359
                pass
 
360
       
 
361
    @staticmethod
 
362
    def parent(entry, file_id):
 
363
        if entry is None:
 
364
            return None
 
365
        return entry.parent_id
 
366
 
 
367
    @staticmethod
 
368
    def name(entry, file_id):
 
369
        if entry is None:
 
370
            return None
 
371
        return entry.name
 
372
    
 
373
    @staticmethod
 
374
    def contents_sha1(tree, file_id):
 
375
        if file_id not in tree:
 
376
            return None
 
377
        return tree.get_file_sha1(file_id)
 
378
 
 
379
    @staticmethod
 
380
    def executable(tree, file_id):
 
381
        if file_id not in tree:
 
382
            return None
 
383
        if tree.kind(file_id) != "file":
 
384
            return False
 
385
        return tree.is_executable(file_id)
 
386
 
 
387
    @staticmethod
 
388
    def kind(tree, file_id):
 
389
        if file_id not in tree:
 
390
            return None
 
391
        return tree.kind(file_id)
 
392
 
 
393
    @staticmethod
 
394
    def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
 
395
        """Do a three-way test on a scalar.
 
396
        Return "this", "other" or "conflict", depending whether a value wins.
 
397
        """
 
398
        key_base = key(base_tree, file_id)
 
399
        key_other = key(other_tree, file_id)
 
400
        #if base == other, either they all agree, or only THIS has changed.
 
401
        if key_base == key_other:
 
402
            return "this"
 
403
        key_this = key(this_tree, file_id)
 
404
        if key_this not in (key_base, key_other):
 
405
            return "conflict"
 
406
        # "Ambiguous clean merge"
 
407
        elif key_this == key_other:
 
408
            return "this"
 
409
        else:
 
410
            assert key_this == key_base
 
411
            return "other"
 
412
 
 
413
    def merge_names(self, file_id):
 
414
        def get_entry(tree):
 
415
            if file_id in tree.inventory:
 
416
                return tree.inventory[file_id]
 
417
            else:
 
418
                return None
 
419
        this_entry = get_entry(self.this_tree)
 
420
        other_entry = get_entry(self.other_tree)
 
421
        base_entry = get_entry(self.base_tree)
 
422
        name_winner = self.scalar_three_way(this_entry, base_entry, 
 
423
                                            other_entry, file_id, self.name)
 
424
        parent_id_winner = self.scalar_three_way(this_entry, base_entry, 
 
425
                                                 other_entry, file_id, 
 
426
                                                 self.parent)
 
427
        if this_entry is None:
 
428
            if name_winner == "this":
 
429
                name_winner = "other"
 
430
            if parent_id_winner == "this":
 
431
                parent_id_winner = "other"
 
432
        if name_winner == "this" and parent_id_winner == "this":
 
433
            return
 
434
        if name_winner == "conflict":
 
435
            trans_id = self.tt.get_trans_id(file_id)
 
436
            self._raw_conflicts.append(('name conflict', trans_id, 
 
437
                                        self.name(this_entry, file_id), 
 
438
                                        self.name(other_entry, file_id)))
 
439
        if parent_id_winner == "conflict":
 
440
            trans_id = self.tt.get_trans_id(file_id)
 
441
            self._raw_conflicts.append(('parent conflict', trans_id, 
 
442
                                        self.parent(this_entry, file_id), 
 
443
                                        self.parent(other_entry, file_id)))
 
444
        if other_entry is None:
 
445
            # it doesn't matter whether the result was 'other' or 
 
446
            # 'conflict'-- if there's no 'other', we leave it alone.
 
447
            return
 
448
        # if we get here, name_winner and parent_winner are set to safe values.
 
449
        winner_entry = {"this": this_entry, "other": other_entry, 
 
450
                        "conflict": other_entry}
 
451
        trans_id = self.tt.get_trans_id(file_id)
 
452
        parent_id = winner_entry[parent_id_winner].parent_id
 
453
        parent_trans_id = self.tt.get_trans_id(parent_id)
 
454
        self.tt.adjust_path(winner_entry[name_winner].name, parent_trans_id,
 
455
                            trans_id)
 
456
 
 
457
 
 
458
    def merge_contents(self, file_id):
 
459
        def contents_pair(tree):
 
460
            if file_id not in tree:
 
461
                return (None, None)
 
462
            kind = tree.kind(file_id)
 
463
            if kind == "file":
 
464
                contents = tree.get_file_sha1(file_id)
 
465
            elif kind == "symlink":
 
466
                contents = tree.get_symlink_target(file_id)
 
467
            else:
 
468
                contents = None
 
469
            return kind, contents
 
470
        # See SPOT run.  run, SPOT, run.
 
471
        # So we're not QUITE repeating ourselves; we do tricky things with
 
472
        # file kind...
 
473
        base_pair = contents_pair(self.base_tree)
 
474
        other_pair = contents_pair(self.other_tree)
 
475
        if base_pair == other_pair:
 
476
            return "unmodified"
 
477
        this_pair = contents_pair(self.this_tree)
 
478
        if this_pair == other_pair:
 
479
            return "unmodified"
 
480
        else:
 
481
            trans_id = self.tt.get_trans_id(file_id)
 
482
            if this_pair == base_pair:
 
483
                if file_id in self.this_tree:
 
484
                    self.tt.delete_contents(trans_id)
 
485
                if file_id in self.other_tree.inventory:
 
486
                    create_by_entry(self.tt, 
 
487
                                    self.other_tree.inventory[file_id], 
 
488
                                    self.other_tree, trans_id)
 
489
                    return "modified"
 
490
                if file_id in self.this_tree:
 
491
                    self.tt.unversion_file(trans_id)
 
492
                    return "deleted"
 
493
            elif this_pair[0] == "file" and other_pair[0] == "file":
 
494
                # If this and other are both files, either base is a file, or
 
495
                # both converted to files, so at least we have agreement that
 
496
                # output should be a file.
 
497
                self.text_merge(file_id, trans_id)
 
498
                return "modified"
 
499
            else:
 
500
                trans_id = self.tt.get_trans_id(file_id)
 
501
                name = self.tt.final_name(trans_id)
 
502
                parent_id = self.tt.final_parent(trans_id)
 
503
                if file_id in self.this_tree.inventory:
 
504
                    self.tt.unversion_file(trans_id)
 
505
                    self.tt.delete_contents(trans_id)
 
506
                else:
 
507
                    self.tt.cancel_versioning(trans_id)
 
508
                file_group = self._dump_conflicts(name, parent_id, file_id, 
 
509
                                                  set_version=True)
 
510
                self._raw_conflicts.append(('contents conflict', file_group))
 
511
 
 
512
    def get_lines(self, tree, file_id):
 
513
        if file_id in tree:
 
514
            return tree.get_file(file_id).readlines()
 
515
        else:
 
516
            return []
 
517
 
 
518
    def text_merge(self, file_id, trans_id):
 
519
        """Perform a three-way text merge on a file_id"""
 
520
        # it's possible that we got here with base as a different type.
 
521
        # if so, we just want two-way text conflicts.
 
522
        if file_id in self.base_tree and \
 
523
            self.base_tree.kind(file_id) == "file":
 
524
            base_lines = self.get_lines(self.base_tree, file_id)
 
525
        else:
 
526
            base_lines = []
 
527
        other_lines = self.get_lines(self.other_tree, file_id)
 
528
        this_lines = self.get_lines(self.this_tree, file_id)
 
529
        m3 = Merge3(base_lines, this_lines, other_lines)
 
530
        start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
 
531
        if self.show_base is True:
 
532
            base_marker = '|' * 7
 
533
        else:
 
534
            base_marker = None
 
535
 
 
536
        def iter_merge3(retval):
 
537
            retval["text_conflicts"] = False
 
538
            for line in m3.merge_lines(name_a = "TREE", 
 
539
                                       name_b = "MERGE-SOURCE", 
 
540
                                       name_base = "BASE-REVISION",
 
541
                                       start_marker=start_marker, 
 
542
                                       base_marker=base_marker,
 
543
                                       reprocess=self.reprocess):
 
544
                if line.startswith(start_marker):
 
545
                    retval["text_conflicts"] = True
 
546
                    yield line.replace(start_marker, '<' * 7)
 
547
                else:
 
548
                    yield line
 
549
        retval = {}
 
550
        merge3_iterator = iter_merge3(retval)
 
551
        self.tt.create_file(merge3_iterator, trans_id)
 
552
        if retval["text_conflicts"] is True:
 
553
            self._raw_conflicts.append(('text conflict', trans_id))
 
554
            name = self.tt.final_name(trans_id)
 
555
            parent_id = self.tt.final_parent(trans_id)
 
556
            file_group = self._dump_conflicts(name, parent_id, file_id, 
 
557
                                              this_lines, base_lines,
 
558
                                              other_lines)
 
559
            file_group.append(trans_id)
 
560
 
 
561
    def _dump_conflicts(self, name, parent_id, file_id, this_lines=None, 
 
562
                        base_lines=None, other_lines=None, set_version=False,
 
563
                        no_base=False):
 
564
        data = [('OTHER', self.other_tree, other_lines), 
 
565
                ('THIS', self.this_tree, this_lines)]
 
566
        if not no_base:
 
567
            data.append(('BASE', self.base_tree, base_lines))
 
568
        versioned = False
 
569
        file_group = []
 
570
        for suffix, tree, lines in data:
 
571
            if file_id in tree:
 
572
                trans_id = self._conflict_file(name, parent_id, tree, file_id,
 
573
                                               suffix, lines)
 
574
                file_group.append(trans_id)
 
575
                if set_version and not versioned:
 
576
                    self.tt.version_file(file_id, trans_id)
 
577
                    versioned = True
 
578
        return file_group
 
579
           
 
580
    def _conflict_file(self, name, parent_id, tree, file_id, suffix, 
 
581
                       lines=None):
 
582
        name = name + '.' + suffix
 
583
        trans_id = self.tt.create_path(name, parent_id)
 
584
        entry = tree.inventory[file_id]
 
585
        create_by_entry(self.tt, entry, tree, trans_id, lines)
 
586
        return trans_id
 
587
 
 
588
    def merge_executable(self, file_id, file_status):
 
589
        if file_status == "deleted":
 
590
            return
 
591
        trans_id = self.tt.get_trans_id(file_id)
 
592
        try:
 
593
            if self.tt.final_kind(trans_id) != "file":
 
594
                return
 
595
        except NoSuchFile:
 
596
            return
 
597
        winner = self.scalar_three_way(self.this_tree, self.base_tree, 
 
598
                                       self.other_tree, file_id, 
 
599
                                       self.executable)
 
600
        if winner == "conflict":
 
601
        # There must be a None in here, if we have a conflict, but we
 
602
        # need executability since file status was not deleted.
 
603
            if self.other_tree.is_executable(file_id) is None:
 
604
                winner == "this"
 
605
            else:
 
606
                winner == "other"
 
607
        if winner == "this":
 
608
            if file_status == "modified":
 
609
                executability = self.this_tree.is_executable(file_id)
 
610
                if executability is not None:
 
611
                    trans_id = self.tt.get_trans_id(file_id)
 
612
                    self.tt.set_executability(executability, trans_id)
 
613
        else:
 
614
            assert winner == "other"
 
615
            if file_id in self.other_tree:
 
616
                executability = self.other_tree.is_executable(file_id)
 
617
            elif file_id in self.this_tree:
 
618
                executability = self.this_tree.is_executable(file_id)
 
619
            elif file_id in self.base_tree:
 
620
                executability = self.base_tree.is_executable(file_id)
 
621
            if executability is not None:
 
622
                trans_id = self.tt.get_trans_id(file_id)
 
623
                self.tt.set_executability(executability, trans_id)
 
624
 
 
625
    def cook_conflicts(self):
 
626
        """Convert all conflicts into a form that doesn't depend on trans_id"""
 
627
        name_conflicts = {}
 
628
        fp = FinalPaths(self.tt)
 
629
        for conflict in self._raw_conflicts:
 
630
            conflict_type = conflict[0]
 
631
            if conflict_type in ('name conflict', 'parent conflict'):
 
632
                trans_id = conflict[1]
 
633
                conflict_args = conflict[2:]
 
634
                if trans_id not in name_conflicts:
 
635
                    name_conflicts[trans_id] = {}
 
636
                unique_add(name_conflicts[trans_id], conflict_type, 
 
637
                           conflict_args)
 
638
            if conflict_type == 'contents conflict':
 
639
                for trans_id in conflict[1]:
 
640
                    file_id = self.tt.final_file_id(trans_id)
 
641
                    if file_id is not None:
 
642
                        break
 
643
                path = fp.get_path(trans_id)
 
644
                for suffix in ('.BASE', '.THIS', '.OTHER'):
 
645
                    if path.endswith(suffix):
 
646
                        path = path[:-len(suffix)]
 
647
                        break
 
648
                self.cooked_conflicts.append((conflict_type, file_id, path))
 
649
            if conflict_type == 'text conflict':
 
650
                trans_id = conflict[1]
 
651
                path = fp.get_path(trans_id)
 
652
                file_id = self.tt.final_file_id(trans_id)
 
653
                self.cooked_conflicts.append((conflict_type, file_id, path))
 
654
 
 
655
        for trans_id, conflicts in name_conflicts.iteritems():
 
656
            try:
 
657
                this_parent, other_parent = conflicts['parent conflict']
 
658
                assert this_parent != other_parent
 
659
            except KeyError:
 
660
                this_parent = other_parent = \
 
661
                    self.tt.final_file_id(self.tt.final_parent(trans_id))
 
662
            try:
 
663
                this_name, other_name = conflicts['name conflict']
 
664
                assert this_name != other_name
 
665
            except KeyError:
 
666
                this_name = other_name = self.tt.final_name(trans_id)
 
667
            other_path = fp.get_path(trans_id)
 
668
            if this_parent is not None:
 
669
                this_parent_path = \
 
670
                    fp.get_path(self.tt.get_trans_id(this_parent))
 
671
                this_path = os.path.join(this_parent_path, this_name)
 
672
            else:
 
673
                this_path = "<deleted>"
 
674
            file_id = self.tt.final_file_id(trans_id)
 
675
            self.cooked_conflicts.append(('path conflict', file_id, this_path, 
 
676
                                         other_path))
 
677
            
 
678
 
 
679
class WeaveMerger(Merge3Merger):
 
680
    supports_reprocess = False
 
681
    supports_show_base = False
 
682
 
 
683
    def __init__(self, working_tree, this_tree, base_tree, other_tree):
 
684
        self.this_revision_tree = self._get_revision_tree(this_tree)
 
685
        self.other_revision_tree = self._get_revision_tree(other_tree)
 
686
        super(WeaveMerger, self).__init__(working_tree, this_tree, 
 
687
                                          base_tree, other_tree)
 
688
 
 
689
    def _get_revision_tree(self, tree):
 
690
        if getattr(tree, 'get_weave', False) is False:
 
691
            # If we have a WorkingTree, try using the basis
 
692
            return tree.branch.basis_tree()
 
693
        else:
 
694
            return tree
 
695
 
 
696
    def _check_file(self, file_id):
 
697
        """Check that the revision tree's version of the file matches."""
 
698
        for tree, rt in ((self.this_tree, self.this_revision_tree), 
 
699
                         (self.other_tree, self.other_revision_tree)):
 
700
            if rt is tree:
 
701
                continue
 
702
            if tree.get_file_sha1(file_id) != rt.get_file_sha1(file_id):
 
703
                raise WorkingTreeNotRevision(self.this_tree)
 
704
 
 
705
    def _merged_lines(self, file_id):
 
706
        """Generate the merged lines.
 
707
        There is no distinction between lines that are meant to contain <<<<<<<
 
708
        and conflicts.
 
709
        """
 
710
        weave = self.this_revision_tree.get_weave(file_id)
 
711
        this_revision_id = self.this_revision_tree.inventory[file_id].revision
 
712
        other_revision_id = \
 
713
            self.other_revision_tree.inventory[file_id].revision
 
714
        this_i = weave.lookup(this_revision_id)
 
715
        other_i = weave.lookup(other_revision_id)
 
716
        plan =  weave.plan_merge(this_i, other_i)
 
717
        return weave.weave_merge(plan)
 
718
 
 
719
    def text_merge(self, file_id, trans_id):
 
720
        self._check_file(file_id)
 
721
        lines = self._merged_lines(file_id)
 
722
        conflicts = '<<<<<<<\n' in lines
 
723
        self.tt.create_file(lines, trans_id)
 
724
        if conflicts:
 
725
            self._raw_conflicts.append(('text conflict', trans_id))
 
726
            name = self.tt.final_name(trans_id)
 
727
            parent_id = self.tt.final_parent(trans_id)
 
728
            file_group = self._dump_conflicts(name, parent_id, file_id, 
 
729
                                              no_base=True)
 
730
            file_group.append(trans_id)
 
731
 
 
732
 
 
733
class Diff3Merger(Merge3Merger):
 
734
    """Use good ol' diff3 to do text merges"""
 
735
    def dump_file(self, temp_dir, name, tree, file_id):
 
736
        out_path = pathjoin(temp_dir, name)
 
737
        out_file = file(out_path, "wb")
 
738
        in_file = tree.get_file(file_id)
 
739
        for line in in_file:
 
740
            out_file.write(line)
 
741
        return out_path
 
742
 
 
743
    def text_merge(self, file_id, trans_id):
 
744
        import bzrlib.patch
 
745
        temp_dir = mkdtemp(prefix="bzr-")
 
746
        try:
 
747
            new_file = os.path.join(temp_dir, "new")
 
748
            this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
 
749
            base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
 
750
            other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
 
751
            status = bzrlib.patch.diff3(new_file, this, base, other)
 
752
            if status not in (0, 1):
 
753
                raise BzrError("Unhandled diff3 exit code")
 
754
            self.tt.create_file(file(new_file, "rb"), trans_id)
 
755
            if status == 1:
 
756
                name = self.tt.final_name(trans_id)
 
757
                parent_id = self.tt.final_parent(trans_id)
 
758
                self._dump_conflicts(name, parent_id, file_id)
 
759
            self._raw_conflicts.append(('text conflict', trans_id))
 
760
        finally:
 
761
            rmtree(temp_dir)
 
762
 
 
763
 
 
764
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
 
765
                backup_files=False, 
 
766
                merge_type=Merge3Merger, 
 
767
                interesting_ids=None, 
 
768
                show_base=False, 
 
769
                reprocess=False, 
 
770
                other_rev_id=None,
 
771
                interesting_files=None,
 
772
                this_tree=None):
 
773
    """Primary interface for merging. 
 
774
 
 
775
        typical use is probably 
 
776
        'merge_inner(branch, branch.get_revision_tree(other_revision),
 
777
                     branch.get_revision_tree(base_revision))'
 
778
        """
 
779
    if this_tree is None:
 
780
        this_tree = this_branch.working_tree()
 
781
    merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree)
 
782
    merger.backup_files = backup_files
 
783
    merger.merge_type = merge_type
 
784
    merger.interesting_ids = interesting_ids
 
785
    if interesting_files:
 
786
        assert not interesting_ids, ('Only supply interesting_ids'
 
787
                                     ' or interesting_files')
 
788
        merger._set_interesting_files(interesting_files)
 
789
    merger.show_base = show_base 
 
790
    merger.reprocess = reprocess
 
791
    merger.other_rev_id = other_rev_id
 
792
    merger.other_basis = other_rev_id
 
793
    return merger.do_merge()
 
794
 
 
795
 
355
796
merge_types = {     "merge3": (Merge3Merger, "Native diff3-style merge"), 
356
797
                     "diff3": (Diff3Merger,  "Merge using external diff3"),
357
798
                     'weave': (WeaveMerger, "Weave-based merge")