1
# Copyright (C) 2007-2011 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
22
from bzrlib.revision import NULL_REVISION
23
from bzrlib.tests.test_graph import TestGraphBase
36
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
37
'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
50
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
51
'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
54
# Extended history shortcut
66
extended_history_shortcut = {'a': [NULL_REVISION],
75
class TestSearchResultRefine(tests.TestCase):
77
def make_graph(self, ancestors):
78
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
80
def test_refine(self):
81
# Used when pulling from a stacked repository, so test some revisions
82
# being satisfied from the stacking branch.
84
{"tip":["mid"], "mid":["base"], "tag":["base"],
85
"base":[NULL_REVISION], NULL_REVISION:[]})
86
result = vf_search.SearchResult(set(['tip', 'tag']),
87
set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
88
result = result.refine(set(['tip']), set(['mid']))
89
recipe = result.get_recipe()
90
# We should be starting from tag (original head) and mid (seen ref)
91
self.assertEqual(set(['mid', 'tag']), recipe[1])
92
# We should be stopping at NULL (original stop) and tip (seen head)
93
self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
94
self.assertEqual(3, recipe[3])
95
result = result.refine(set(['mid', 'tag', 'base']),
97
recipe = result.get_recipe()
98
# We should be starting from nothing (NULL was known as a cut point)
99
self.assertEqual(set([]), recipe[1])
100
# We should be stopping at NULL (original stop) and tip (seen head) and
101
# tag (seen head) and mid(seen mid-point head). We could come back and
102
# define this as not including mid, for minimal results, but it is
103
# still 'correct' to include mid, and simpler/easier.
104
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
105
self.assertEqual(0, recipe[3])
106
self.assertTrue(result.is_empty())
109
class TestSearchResultFromParentMap(TestGraphBase):
111
def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
113
(start, stop, count) = vf_search.search_result_from_parent_map(
114
parent_map, missing_keys)
115
self.assertEqual((sorted(start_keys), sorted(stop_keys), key_count),
116
(sorted(start), sorted(stop), count))
118
def test_no_parents(self):
119
self.assertSearchResult([], [], 0, {})
120
self.assertSearchResult([], [], 0, None)
122
def test_ancestry_1(self):
123
self.assertSearchResult(['rev4'], [NULL_REVISION], len(ancestry_1),
126
def test_ancestry_2(self):
127
self.assertSearchResult(['rev1b', 'rev4a'], [NULL_REVISION],
128
len(ancestry_2), ancestry_2)
129
self.assertSearchResult(['rev1b', 'rev4a'], [],
130
len(ancestry_2)+1, ancestry_2,
131
missing_keys=[NULL_REVISION])
133
def test_partial_search(self):
134
parent_map = dict((k,extended_history_shortcut[k])
136
self.assertSearchResult(['e', 'f'], ['d', 'a'], 2,
138
parent_map.update((k,extended_history_shortcut[k])
140
self.assertSearchResult(['e', 'f'], ['c', NULL_REVISION], 4,
142
parent_map['c'] = extended_history_shortcut['c']
143
self.assertSearchResult(['e', 'f'], ['b'], 6,
144
parent_map, missing_keys=[NULL_REVISION])
145
parent_map['b'] = extended_history_shortcut['b']
146
self.assertSearchResult(['e', 'f'], [], 7,
147
parent_map, missing_keys=[NULL_REVISION])
150
class TestLimitedSearchResultFromParentMap(TestGraphBase):
152
def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
153
missing_keys, tip_keys, depth):
154
(start, stop, count) = vf_search.limited_search_result_from_parent_map(
155
parent_map, missing_keys, tip_keys, depth)
156
self.assertEqual((sorted(start_keys), sorted(stop_keys), key_count),
157
(sorted(start), sorted(stop), count))
159
def test_empty_ancestry(self):
160
self.assertSearchResult([], [], 0, {}, (), ['tip-rev-id'], 10)
162
def test_ancestry_1(self):
163
self.assertSearchResult(['rev4'], ['rev1'], 4,
164
ancestry_1, (), ['rev1'], 10)
165
self.assertSearchResult(['rev2a', 'rev2b'], ['rev1'], 2,
166
ancestry_1, (), ['rev1'], 1)
169
def test_multiple_heads(self):
170
self.assertSearchResult(['e', 'f'], ['a'], 5,
171
extended_history_shortcut, (), ['a'], 10)
172
# Note that even though we only take 1 step back, we find 'f', which
173
# means the described search will still find d and c.
174
self.assertSearchResult(['f'], ['a'], 4,
175
extended_history_shortcut, (), ['a'], 1)
176
self.assertSearchResult(['f'], ['a'], 4,
177
extended_history_shortcut, (), ['a'], 2)
180
class TestPendingAncestryResultRefine(tests.TestCase):
182
def make_graph(self, ancestors):
183
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
185
def test_refine(self):
186
# Used when pulling from a stacked repository, so test some revisions
187
# being satisfied from the stacking branch.
189
{"tip":["mid"], "mid":["base"], "tag":["base"],
190
"base":[NULL_REVISION], NULL_REVISION:[]})
191
result = vf_search.PendingAncestryResult(['tip', 'tag'], None)
192
result = result.refine(set(['tip']), set(['mid']))
193
self.assertEqual(set(['mid', 'tag']), result.heads)
194
result = result.refine(set(['mid', 'tag', 'base']),
195
set([NULL_REVISION]))
196
self.assertEqual(set([NULL_REVISION]), result.heads)
197
self.assertTrue(result.is_empty())
200
class TestPendingAncestryResultGetKeys(tests.TestCaseWithMemoryTransport):
201
"""Tests for bzrlib.graph.PendingAncestryResult."""
203
def test_get_keys(self):
204
builder = self.make_branch_builder('b')
205
builder.start_series()
206
builder.build_snapshot('rev-1', None, [
207
('add', ('', 'root-id', 'directory', ''))])
208
builder.build_snapshot('rev-2', ['rev-1'], [])
209
builder.finish_series()
210
repo = builder.get_branch().repository
212
self.addCleanup(repo.unlock)
213
result = vf_search.PendingAncestryResult(['rev-2'], repo)
214
self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
216
def test_get_keys_excludes_ghosts(self):
217
builder = self.make_branch_builder('b')
218
builder.start_series()
219
builder.build_snapshot('rev-1', None, [
220
('add', ('', 'root-id', 'directory', ''))])
221
builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
222
builder.finish_series()
223
repo = builder.get_branch().repository
225
self.addCleanup(repo.unlock)
226
result = vf_search.PendingAncestryResult(['rev-2'], repo)
227
self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
229
def test_get_keys_excludes_null(self):
230
# Make a 'graph' with an iter_ancestry that returns NULL_REVISION
231
# somewhere other than the last element, which can happen in real
233
class StubGraph(object):
234
def iter_ancestry(self, keys):
235
return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
236
result = vf_search.PendingAncestryResult(['rev-3'], None)
237
result_keys = result._get_keys(StubGraph())
238
# Only the non-null keys from the ancestry appear.
239
self.assertEqual(set(['foo']), set(result_keys))
added
removed
bzrlib/tests/test_vf_search.py
