1
# Copyright (C) 2007 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
from bzrlib import errors, patiencediff, revision
20
class PlanMerge(object):
21
"""Plan an annotate merge using on-the-fly annotation"""
23
def __init__(self, a_rev, b_rev, vf):
26
:param a_rev: Revision-id of one revision to merge
27
:param b_rev: Revision-id of the other revision to merge
28
:param vf: A versionedfile containing both revisions
32
self.lines_a = vf.get_lines(a_rev)
33
self.lines_b = vf.get_lines(b_rev)
35
a_ancestry = set(vf.get_ancestry(a_rev))
36
b_ancestry = set(vf.get_ancestry(b_rev))
37
self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
40
"""Generate a 'plan' for merging the two revisions.
42
This involves comparing their texts and determining the cause of
43
differences. If text A has a line and text B does not, then either the
44
line was added to text A, or it was deleted from B. Once the causes
45
are combined, they are written out in the format described in
46
VersionedFile.plan_merge
48
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
49
new_a = self._find_new(self.a_rev)
50
new_b = self._find_new(self.b_rev)
53
a_lines = self.vf.get_lines(self.a_rev)
54
b_lines = self.vf.get_lines(self.b_rev)
55
for i, j, n in blocks:
56
# determine why lines aren't common
57
for a_index in range(last_i, i):
62
yield cause, a_lines[a_index]
63
for b_index in range(last_j, j):
68
yield cause, b_lines[b_index]
70
for a_index in range(i, i+n):
71
yield 'unchanged', a_lines[a_index]
75
def _get_matching_blocks(self, left_revision, right_revision):
76
"""Return a description of which sections of two revisions match.
78
See SequenceMatcher.get_matching_blocks
80
left_lines = self.vf.get_lines(left_revision)
81
right_lines = self.vf.get_lines(right_revision)
82
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
84
return matcher.get_matching_blocks()
86
def _unique_lines(self, matching_blocks):
87
"""Analyse matching_blocks to determine which lines are unique
89
:return: a tuple of (unique_left, unique_right), where the values are
90
sets of line numbers of unique lines.
96
for i, j, n in matching_blocks:
97
unique_left.extend(range(last_i, i))
98
unique_right.extend(range(last_j, j))
101
return unique_left, unique_right
103
def _find_new(self, version_id):
104
"""Determine which lines are new in the ancestry of this version.
106
If a lines is present in this version, and not present in any
107
common ancestor, it is considered new.
109
if version_id not in self.uncommon:
111
parents = self.vf.get_parents(version_id)
112
if len(parents) == 0:
113
return set(range(len(self.vf.get_lines(version_id))))
115
for parent in parents:
116
blocks = self._get_matching_blocks(version_id, parent)
117
result, unused = self._unique_lines(blocks)
118
parent_new = self._find_new(parent)
119
for i, j, n in blocks:
120
for ii, jj in [(i+r, j+r) for r in range(n)]:
126
new.intersection_update(result)
130
class _PlanMergeVersionedFile(object):
131
"""A VersionedFile for uncommitted and committed texts.
133
It is intended to allow merges to be planned with working tree texts.
134
It implements only the small part of the VersionedFile interface used by
135
PlanMerge. It falls back to multiple versionedfiles for data not stored in
136
_PlanMergeVersionedFile itself.
139
def __init__(self, file_id, fallback_versionedfiles=None):
142
:param file_id: Used when raising exceptions.
143
:param fallback_versionedfiles: If supplied, the set of fallbacks to
144
use. Otherwise, _PlanMergeVersionedFile.fallback_versionedfiles
145
can be appended to later.
147
self._file_id = file_id
148
if fallback_versionedfiles is None:
149
self.fallback_versionedfiles = []
151
self.fallback_versionedfiles = fallback_versionedfiles
155
def add_lines(self, version_id, parents, lines):
156
"""See VersionedFile.add_lines
158
Lines are added locally, not fallback versionedfiles. Also, ghosts are
159
permitted. Only reserved ids are permitted.
161
if not revision.is_reserved_id(version_id):
162
raise ValueError('Only reserved ids may be used')
164
raise ValueError('Parents may not be None')
166
raise ValueError('Lines may not be None')
167
self._parents[version_id] = parents
168
self._lines[version_id] = lines
170
def get_lines(self, version_id):
171
"""See VersionedFile.get_ancestry"""
172
lines = self._lines.get(version_id)
173
if lines is not None:
175
for versionedfile in self.fallback_versionedfiles:
177
return versionedfile.get_lines(version_id)
178
except errors.RevisionNotPresent:
181
raise errors.RevisionNotPresent(version_id, self._file_id)
183
def get_ancestry(self, version_id):
184
"""See VersionedFile.get_ancestry.
186
Note that this implementation assumes that if a VersionedFile can
187
answer get_ancestry at all, it can give an authoritative answer. In
188
fact, ghosts can invalidate this assumption. But it's good enough
189
99% of the time, and far cheaper/simpler.
191
Also note that the results of this version are never topologically
192
sorted, and are a set.
194
parents = self._parents.get(version_id)
196
for vf in self.fallback_versionedfiles:
198
return vf.get_ancestry(version_id)
199
except errors.RevisionNotPresent:
202
raise errors.RevisionNotPresent(version_id, self._file_id)
203
ancestry = set([version_id])
204
for parent in parents:
205
ancestry.update(self.get_ancestry(parent))
208
def get_parents(self, version_id):
209
"""See VersionedFile.get_parents"""
210
parents = self._parents.get(version_id)
211
if parents is not None:
213
for versionedfile in self.fallback_versionedfiles:
215
return versionedfile.get_parents(version_id)
216
except errors.RevisionNotPresent:
219
raise errors.RevisionNotPresent(version_id, self._file_id)
added
removed
bzrlib/plan_merge.py
