/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: John Arbash Meinel
  • Date: 2007-12-04 18:11:51 UTC
  • mfrom: (3074 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3075.
  • Revision ID: john@arbash-meinel.com-20071204181151-br85qwsgshso16q5
[merge] bzr.dev 3074

Show diffs side-by-side

added added

removed removed

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