/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: Lukáš Lalinský
  • Date: 2007-12-17 17:28:25 UTC
  • mfrom: (3120 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3123.
  • Revision ID: lalinsky@gmail.com-20071217172825-tr3pqm1mhvs3gwnn
Merge bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge.py
20
20
import warnings
21
21
 
22
22
from bzrlib import (
 
23
    debug,
23
24
    errors,
24
25
    osutils,
25
26
    patiencediff,
44
45
from bzrlib.merge3 import Merge3
45
46
from bzrlib.osutils import rename, pathjoin
46
47
from progress import DummyProgress, ProgressPhase
47
 
from bzrlib.revision import (is_ancestor, NULL_REVISION, ensure_null)
 
48
from bzrlib.revision import (NULL_REVISION, ensure_null)
48
49
from bzrlib.textfile import check_text_lines
49
50
from bzrlib.trace import mutter, warning, note
50
51
from bzrlib.transform import (TreeTransform, resolve_conflicts, cook_conflicts,
296
297
        self.base_branch = branch
297
298
        self._maybe_fetch(branch, self.this_branch, revision_id)
298
299
        self.base_tree = self.revision_tree(revision_id)
299
 
        self.base_is_ancestor = is_ancestor(self.this_basis,
300
 
                                            self.base_rev_id,
301
 
                                            self.this_branch)
302
 
        self.base_is_other_ancestor = is_ancestor(self.other_basis,
303
 
                                                  self.base_rev_id,
304
 
                                                  self.this_branch)
 
300
        graph = self.this_branch.repository.get_graph()
 
301
        self.base_is_ancestor = graph.is_ancestor(self.base_rev_id,
 
302
                                                  self.this_basis)
 
303
        self.base_is_other_ancestor = graph.is_ancestor(self.base_rev_id,
 
304
                                                        self.other_basis)
305
305
 
306
306
    def _maybe_fetch(self, source, target, revision_id):
307
307
        if not source.repository.has_same_location(target.repository):
315
315
        if NULL_REVISION in revisions:
316
316
            self.base_rev_id = NULL_REVISION
317
317
        else:
318
 
            self.base_rev_id = graph.find_unique_lca(*revisions)
 
318
            self.base_rev_id, steps = graph.find_unique_lca(revisions[0],
 
319
                revisions[1], count_steps=True)
319
320
            if self.base_rev_id == NULL_REVISION:
320
321
                raise UnrelatedBranches()
 
322
            if steps > 1:
 
323
                warning('Warning: criss-cross merge encountered.  See bzr'
 
324
                        ' help criss-cross.')
321
325
        self.base_tree = self.revision_tree(self.base_rev_id)
322
326
        self.base_is_ancestor = True
323
327
        self.base_is_other_ancestor = True
340
344
                self.base_rev_id = _mod_revision.ensure_null(
341
345
                    base_branch.get_rev_id(base_revision[1]))
342
346
            self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
343
 
            self.base_is_ancestor = is_ancestor(self.this_basis, 
344
 
                                                self.base_rev_id,
345
 
                                                self.this_branch)
346
 
            self.base_is_other_ancestor = is_ancestor(self.other_basis,
347
 
                                                      self.base_rev_id,
348
 
                                                      self.this_branch)
 
347
            graph = self.this_branch.repository.get_graph()
 
348
            self.base_is_ancestor = graph.is_ancestor(self.base_rev_id,
 
349
                                                      self.this_basis)
 
350
            self.base_is_other_ancestor = graph.is_ancestor(self.base_rev_id,
 
351
                                                            self.other_basis)
349
352
 
350
353
    def do_merge(self):
351
354
        kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
550
553
                                 self.tt.root)
551
554
        if self.other_tree.inventory.root is None:
552
555
            return
553
 
        other_root_file_id = self.other_tree.inventory.root.file_id
 
556
        other_root_file_id = self.other_tree.get_root_id()
554
557
        other_root = self.tt.trans_id_file_id(other_root_file_id)
555
558
        if other_root == self.tt.root:
556
559
            return
991
994
        and conflicts.
992
995
        """
993
996
        plan = self.this_tree.plan_file_merge(file_id, self.other_tree)
 
997
        if 'merge' in debug.debug_flags:
 
998
            plan = list(plan)
 
999
            trans_id = self.tt.trans_id_file_id(file_id)
 
1000
            name = self.tt.final_name(trans_id) + '.plan'
 
1001
            contents = ('%10s|%s' % l for l in plan)
 
1002
            self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
994
1003
        textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
995
1004
            '>>>>>>> MERGE-SOURCE\n')
996
1005
        return textmerge.merge_lines(self.reprocess)
1137
1146
        for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
1138
1147
            assert text_a == text_b
1139
1148
            yield "unchanged", text_a
 
1149
 
 
1150
 
 
1151
class _PlanMerge(object):
 
1152
    """Plan an annotate merge using on-the-fly annotation"""
 
1153
 
 
1154
    def __init__(self, a_rev, b_rev, vf):
 
1155
        """Contructor.
 
1156
 
 
1157
        :param a_rev: Revision-id of one revision to merge
 
1158
        :param b_rev: Revision-id of the other revision to merge
 
1159
        :param vf: A versionedfile containing both revisions
 
1160
        """
 
1161
        self.a_rev = a_rev
 
1162
        self.b_rev = b_rev
 
1163
        self.lines_a = vf.get_lines(a_rev)
 
1164
        self.lines_b = vf.get_lines(b_rev)
 
1165
        self.vf = vf
 
1166
        a_ancestry = set(vf.get_ancestry(a_rev, topo_sorted=False))
 
1167
        b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
 
1168
        self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
 
1169
        self._last_lines = None
 
1170
        self._last_lines_revision_id = None
 
1171
 
 
1172
    def plan_merge(self):
 
1173
        """Generate a 'plan' for merging the two revisions.
 
1174
 
 
1175
        This involves comparing their texts and determining the cause of
 
1176
        differences.  If text A has a line and text B does not, then either the
 
1177
        line was added to text A, or it was deleted from B.  Once the causes
 
1178
        are combined, they are written out in the format described in
 
1179
        VersionedFile.plan_merge
 
1180
        """
 
1181
        blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
 
1182
        new_a = self._find_new(self.a_rev)
 
1183
        new_b = self._find_new(self.b_rev)
 
1184
        last_i = 0
 
1185
        last_j = 0
 
1186
        a_lines = self.vf.get_lines(self.a_rev)
 
1187
        b_lines = self.vf.get_lines(self.b_rev)
 
1188
        for i, j, n in blocks:
 
1189
            # determine why lines aren't common
 
1190
            for a_index in range(last_i, i):
 
1191
                if a_index in new_a:
 
1192
                    cause = 'new-a'
 
1193
                else:
 
1194
                    cause = 'killed-b'
 
1195
                yield cause, a_lines[a_index]
 
1196
            for b_index in range(last_j, j):
 
1197
                if b_index in new_b:
 
1198
                    cause = 'new-b'
 
1199
                else:
 
1200
                    cause = 'killed-a'
 
1201
                yield cause, b_lines[b_index]
 
1202
            # handle common lines
 
1203
            for a_index in range(i, i+n):
 
1204
                yield 'unchanged', a_lines[a_index]
 
1205
            last_i = i+n
 
1206
            last_j = j+n
 
1207
 
 
1208
    def _get_matching_blocks(self, left_revision, right_revision):
 
1209
        """Return a description of which sections of two revisions match.
 
1210
 
 
1211
        See SequenceMatcher.get_matching_blocks
 
1212
        """
 
1213
        if self._last_lines_revision_id == left_revision:
 
1214
            left_lines = self._last_lines
 
1215
        else:
 
1216
            left_lines = self.vf.get_lines(left_revision)
 
1217
        right_lines = self.vf.get_lines(right_revision)
 
1218
        self._last_lines = right_lines
 
1219
        self._last_lines_revision_id = right_revision
 
1220
        matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
 
1221
                                                       right_lines)
 
1222
        return matcher.get_matching_blocks()
 
1223
 
 
1224
    def _unique_lines(self, matching_blocks):
 
1225
        """Analyse matching_blocks to determine which lines are unique
 
1226
 
 
1227
        :return: a tuple of (unique_left, unique_right), where the values are
 
1228
            sets of line numbers of unique lines.
 
1229
        """
 
1230
        last_i = 0
 
1231
        last_j = 0
 
1232
        unique_left = []
 
1233
        unique_right = []
 
1234
        for i, j, n in matching_blocks:
 
1235
            unique_left.extend(range(last_i, i))
 
1236
            unique_right.extend(range(last_j, j))
 
1237
            last_i = i + n
 
1238
            last_j = j + n
 
1239
        return unique_left, unique_right
 
1240
 
 
1241
    def _find_new(self, version_id):
 
1242
        """Determine which lines are new in the ancestry of this version.
 
1243
 
 
1244
        If a lines is present in this version, and not present in any
 
1245
        common ancestor, it is considered new.
 
1246
        """
 
1247
        if version_id not in self.uncommon:
 
1248
            return set()
 
1249
        parents = self.vf.get_parents(version_id)
 
1250
        if len(parents) == 0:
 
1251
            return set(range(len(self.vf.get_lines(version_id))))
 
1252
        new = None
 
1253
        for parent in parents:
 
1254
            blocks = self._get_matching_blocks(version_id, parent)
 
1255
            result, unused = self._unique_lines(blocks)
 
1256
            parent_new = self._find_new(parent)
 
1257
            for i, j, n in blocks:
 
1258
                for ii, jj in [(i+r, j+r) for r in range(n)]:
 
1259
                    if jj in parent_new:
 
1260
                        result.append(ii)
 
1261
            if new is None:
 
1262
                new = set(result)
 
1263
            else:
 
1264
                new.intersection_update(result)
 
1265
        return new