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
19
class PlanMerge(object):
20
"""Plan an annotate merge using on-the-fly annotation"""
22
def __init__(self, a_rev, b_rev, vf):
25
self.lines_a = vf.get_lines(a_rev)
26
self.lines_b = vf.get_lines(b_rev)
28
a_ancestry = set(vf.get_ancestry(a_rev))
29
b_ancestry = set(vf.get_ancestry(b_rev))
30
self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
33
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
34
new_a = self._find_new(self.a_rev)
35
new_b = self._find_new(self.b_rev)
38
a_lines = self.vf.get_lines(self.a_rev)
39
b_lines = self.vf.get_lines(self.b_rev)
40
for i, j, n in blocks:
41
# determine why lines aren't common
42
for a_index in range(last_i, i):
47
yield cause, a_lines[a_index]
48
for b_index in range(last_j, j):
53
yield cause, b_lines[b_index]
55
for a_index in range(i, i+n):
56
yield 'unchanged', a_lines[a_index]
60
def _get_matching_blocks(self, left_revision, right_revision):
61
left_lines = self.vf.get_lines(left_revision)
62
right_lines = self.vf.get_lines(right_revision)
63
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
65
return matcher.get_matching_blocks()
67
def _unique_lines(self, matching_blocks):
72
for i, j, n in matching_blocks:
73
unique_left.extend(range(last_i, i))
74
unique_right.extend(range(last_j, j))
77
return unique_left, unique_right
79
def _find_new(self, version_id):
80
"""Determine which lines are new in the ancestry of this version.
82
If a lines is present in this version, and not present in any
83
common ancestor, it is considered new.
85
if version_id not in self.uncommon:
87
parents = self.vf.get_parents(version_id)
89
return set(range(len(self.vf.get_lines(version_id))))
91
for parent in parents:
92
blocks = self._get_matching_blocks(version_id, parent)
93
result, unused = self._unique_lines(blocks)
94
parent_new = self._find_new(parent)
95
for i, j, n in blocks:
96
for ii, jj in [(i+r, j+r) for r in range(n)]:
102
new.intersection_update(result)
106
class _PlanMergeVersionedfile(object):
107
"""A VersionedFile for uncommitted and committed texts.
109
Intended to allow merges to be planned with working tree texts.
112
def __init__(self, file_id, fallback_versionedfiles=None):
113
self._file_id = file_id
114
if fallback_versionedfiles is None:
115
self.fallback_versionedfiles = []
117
self.fallback_versionedfiles = fallback_versionedfiles
121
def add_lines(self, version_id, parents, lines):
122
if not revision.is_reserved_id(version_id):
123
raise ValueError('Only reserved ids may be used')
125
raise ValueError('Parents may not be None')
127
raise ValueError('Lines may not be None')
128
self._parents[version_id] = parents
129
self._lines[version_id] = lines
131
def get_lines(self, version_id):
132
lines = self._lines.get(version_id)
133
if lines is not None:
135
for versionedfile in self.fallback_versionedfiles:
137
return versionedfile.get_lines(version_id)
138
except errors.RevisionNotPresent:
141
raise errors.RevisionNotPresent(version_id, self._file_id)
143
def get_ancestry(self, version_id):
144
"""See Versionedfile.get_ancestry.
146
Note that this implementation assumes that if a Versionedfile can
147
answer get_ancestry at all, it can give an authoritative answer. In
148
fact, ghosts can invalidate this assumption. But it's good enough
149
99% of the time, and far cheaper/simpler.
151
Also note that the results of this version are never topologically
152
sorted, and are a set.
154
parents = self._parents.get(version_id)
156
for vf in self.fallback_versionedfiles:
158
return vf.get_ancestry(version_id)
159
except errors.RevisionNotPresent:
162
raise errors.RevisionNotPresent(version_id, self._file_id)
163
ancestry = set([version_id])
164
for parent in parents:
165
ancestry.update(self.get_ancestry(parent))
168
def get_parents(self, version_id):
169
parents = self._parents.get(version_id)
170
if parents is not None:
172
for versionedfile in self.fallback_versionedfiles:
174
return versionedfile.get_parents(version_id)
175
except errors.RevisionNotPresent:
178
raise errors.RevisionNotPresent(version_id, self._file_id)
added
removed
bzrlib/plan_merge.py
