← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_vf_search.py

(vila) Fix test failures blocking package builds. (Vincent Ladeuil)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_vf_search.py
 
1
# Copyright (C) 2007-2011 Canonical Ltd
 
2
#
 
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.
 
7
#
 
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.
 
12
#
 
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
 
16
 
 
17
from bzrlib import (
 
18
    graph as _mod_graph,
 
19
    tests,
 
20
    vf_search,
 
21
    )
 
22
from bzrlib.revision import NULL_REVISION
 
23
from bzrlib.tests.test_graph import TestGraphBase
 
24
 
 
25
# Ancestry 1:
 
26
#
 
27
#  NULL_REVISION
 
28
#       |
 
29
#     rev1
 
30
#      /\
 
31
#  rev2a rev2b
 
32
#     |    |
 
33
#   rev3  /
 
34
#     |  /
 
35
#   rev4
 
36
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
 
37
              'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
 
38
 
 
39
# Ancestry 2:
 
40
#
 
41
#  NULL_REVISION
 
42
#    /    \
 
43
# rev1a  rev1b
 
44
#   |
 
45
# rev2a
 
46
#   |
 
47
# rev3a
 
48
#   |
 
49
# rev4a
 
50
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
 
51
              'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
 
52
 
 
53
 
 
54
# Extended history shortcut
 
55
#  NULL_REVISION
 
56
#       |
 
57
#       a
 
58
#       |\
 
59
#       b |
 
60
#       | |
 
61
#       c |
 
62
#       | |
 
63
#       d |
 
64
#       |\|
 
65
#       e f
 
66
extended_history_shortcut = {'a': [NULL_REVISION],
 
67
                             'b': ['a'],
 
68
                             'c': ['b'],
 
69
                             'd': ['c'],
 
70
                             'e': ['d'],
 
71
                             'f': ['a', 'd'],
 
72
                            }
 
73
 
 
74
 
 
75
class TestSearchResultRefine(tests.TestCase):
 
76
 
 
77
    def make_graph(self, ancestors):
 
78
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
 
79
 
 
80
    def test_refine(self):
 
81
        # Used when pulling from a stacked repository, so test some revisions
 
82
        # being satisfied from the stacking branch.
 
83
        g = self.make_graph(
 
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']),
 
96
            set([NULL_REVISION]))
 
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())
 
107
 
 
108
 
 
109
class TestSearchResultFromParentMap(TestGraphBase):
 
110
 
 
111
    def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
 
112
                           missing_keys=()):
 
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))
 
117
 
 
118
    def test_no_parents(self):
 
119
        self.assertSearchResult([], [], 0, {})
 
120
        self.assertSearchResult([], [], 0, None)
 
121
 
 
122
    def test_ancestry_1(self):
 
123
        self.assertSearchResult(['rev4'], [NULL_REVISION], len(ancestry_1),
 
124
                                ancestry_1)
 
125
 
 
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])
 
132
 
 
133
    def test_partial_search(self):
 
134
        parent_map = dict((k,extended_history_shortcut[k])
 
135
                          for k in ['e', 'f'])
 
136
        self.assertSearchResult(['e', 'f'], ['d', 'a'], 2,
 
137
                                parent_map)
 
138
        parent_map.update((k,extended_history_shortcut[k])
 
139
                          for k in ['d', 'a'])
 
140
        self.assertSearchResult(['e', 'f'], ['c', NULL_REVISION], 4,
 
141
                                parent_map)
 
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])
 
148
 
 
149
 
 
150
class TestLimitedSearchResultFromParentMap(TestGraphBase):
 
151
 
 
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))
 
158
 
 
159
    def test_empty_ancestry(self):
 
160
        self.assertSearchResult([], [], 0, {}, (), ['tip-rev-id'], 10)
 
161
 
 
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)
 
167
 
 
168
 
 
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)
 
178
 
 
179
 
 
180
class TestPendingAncestryResultRefine(tests.TestCase):
 
181
 
 
182
    def make_graph(self, ancestors):
 
183
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
 
184
 
 
185
    def test_refine(self):
 
186
        # Used when pulling from a stacked repository, so test some revisions
 
187
        # being satisfied from the stacking branch.
 
188
        g = self.make_graph(
 
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())
 
198
 
 
199
 
 
200
class TestPendingAncestryResultGetKeys(tests.TestCaseWithMemoryTransport):
 
201
    """Tests for bzrlib.graph.PendingAncestryResult."""
 
202
 
 
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
 
211
        repo.lock_read()
 
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()))
 
215
 
 
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
 
224
        repo.lock_read()
 
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()))
 
228
 
 
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
 
232
        # ancestries.
 
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))