/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 breezy/tests/test_vf_search.py

  • Committer: Robert Collins
  • Date: 2005-10-19 10:11:57 UTC
  • mfrom: (1185.16.78)
  • mto: This revision was merged to the branch mainline in revision 1470.
  • Revision ID: robertc@robertcollins.net-20051019101157-17438d311e746b4f
merge from upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/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 .. import (
18
 
    graph as _mod_graph,
19
 
    tests,
20
 
    )
21
 
from ..bzr import (
22
 
    vf_search,
23
 
    )
24
 
from ..revision import NULL_REVISION
25
 
from .test_graph import TestGraphBase
26
 
 
27
 
# Ancestry 1:
28
 
#
29
 
#  NULL_REVISION
30
 
#       |
31
 
#     rev1
32
 
#      /\
33
 
#  rev2a rev2b
34
 
#     |    |
35
 
#   rev3  /
36
 
#     |  /
37
 
#   rev4
38
 
ancestry_1 = {b'rev1': [NULL_REVISION],
39
 
              b'rev2a': [b'rev1'],
40
 
              b'rev2b': [b'rev1'],
41
 
              b'rev3': [b'rev2a'],
42
 
              b'rev4': [b'rev3', b'rev2b']}
43
 
 
44
 
# Ancestry 2:
45
 
#
46
 
#  NULL_REVISION
47
 
#    /    \
48
 
# rev1a  rev1b
49
 
#   |
50
 
# rev2a
51
 
#   |
52
 
# rev3a
53
 
#   |
54
 
# rev4a
55
 
ancestry_2 = {b'rev1a': [NULL_REVISION],
56
 
              b'rev2a': [b'rev1a'],
57
 
              b'rev1b': [NULL_REVISION],
58
 
              b'rev3a': [b'rev2a'],
59
 
              b'rev4a': [b'rev3a']}
60
 
 
61
 
 
62
 
# Extended history shortcut
63
 
#  NULL_REVISION
64
 
#       |
65
 
#       a
66
 
#       |\
67
 
#       b |
68
 
#       | |
69
 
#       c |
70
 
#       | |
71
 
#       d |
72
 
#       |\|
73
 
#       e f
74
 
extended_history_shortcut = {b'a': [NULL_REVISION],
75
 
                             b'b': [b'a'],
76
 
                             b'c': [b'b'],
77
 
                             b'd': [b'c'],
78
 
                             b'e': [b'd'],
79
 
                             b'f': [b'a', b'd'],
80
 
                             }
81
 
 
82
 
 
83
 
class TestSearchResultRefine(tests.TestCase):
84
 
 
85
 
    def make_graph(self, ancestors):
86
 
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
87
 
 
88
 
    def test_refine(self):
89
 
        # Used when pulling from a stacked repository, so test some revisions
90
 
        # being satisfied from the stacking branch.
91
 
        self.make_graph(
92
 
            {b"tip": [b"mid"], b"mid": [b"base"], b"tag": [b"base"],
93
 
             b"base": [NULL_REVISION], NULL_REVISION: []})
94
 
        result = vf_search.SearchResult(
95
 
            {b'tip', b'tag'},
96
 
            {NULL_REVISION}, 4, {b'tip', b'mid', b'tag', b'base'})
97
 
        result = result.refine({b'tip'}, {b'mid'})
98
 
        recipe = result.get_recipe()
99
 
        # We should be starting from tag (original head) and mid (seen ref)
100
 
        self.assertEqual({b'mid', b'tag'}, recipe[1])
101
 
        # We should be stopping at NULL (original stop) and tip (seen head)
102
 
        self.assertEqual({NULL_REVISION, b'tip'}, recipe[2])
103
 
        self.assertEqual(3, recipe[3])
104
 
        result = result.refine({b'mid', b'tag', b'base'},
105
 
                               {NULL_REVISION})
106
 
        recipe = result.get_recipe()
107
 
        # We should be starting from nothing (NULL was known as a cut point)
108
 
        self.assertEqual(set([]), recipe[1])
109
 
        # We should be stopping at NULL (original stop) and tip (seen head) and
110
 
        # tag (seen head) and mid(seen mid-point head). We could come back and
111
 
        # define this as not including mid, for minimal results, but it is
112
 
        # still 'correct' to include mid, and simpler/easier.
113
 
        self.assertEqual({NULL_REVISION, b'tip', b'tag', b'mid'}, recipe[2])
114
 
        self.assertEqual(0, recipe[3])
115
 
        self.assertTrue(result.is_empty())
116
 
 
117
 
 
118
 
class TestSearchResultFromParentMap(TestGraphBase):
119
 
 
120
 
    def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
121
 
                           missing_keys=()):
122
 
        (start, stop, count) = vf_search.search_result_from_parent_map(
123
 
            parent_map, missing_keys)
124
 
        self.assertEqual((sorted(start_keys), sorted(stop_keys), key_count),
125
 
                         (sorted(start), sorted(stop), count))
126
 
 
127
 
    def test_no_parents(self):
128
 
        self.assertSearchResult([], [], 0, {})
129
 
        self.assertSearchResult([], [], 0, None)
130
 
 
131
 
    def test_ancestry_1(self):
132
 
        self.assertSearchResult([b'rev4'], [NULL_REVISION], len(ancestry_1),
133
 
                                ancestry_1)
134
 
 
135
 
    def test_ancestry_2(self):
136
 
        self.assertSearchResult([b'rev1b', b'rev4a'], [NULL_REVISION],
137
 
                                len(ancestry_2), ancestry_2)
138
 
        self.assertSearchResult([b'rev1b', b'rev4a'], [],
139
 
                                len(ancestry_2) + 1, ancestry_2,
140
 
                                missing_keys=[NULL_REVISION])
141
 
 
142
 
    def test_partial_search(self):
143
 
        parent_map = dict((k, extended_history_shortcut[k])
144
 
                          for k in [b'e', b'f'])
145
 
        self.assertSearchResult([b'e', b'f'], [b'd', b'a'], 2,
146
 
                                parent_map)
147
 
        parent_map.update((k, extended_history_shortcut[k])
148
 
                          for k in [b'd', b'a'])
149
 
        self.assertSearchResult([b'e', b'f'], [b'c', NULL_REVISION], 4,
150
 
                                parent_map)
151
 
        parent_map[b'c'] = extended_history_shortcut[b'c']
152
 
        self.assertSearchResult([b'e', b'f'], [b'b'], 6,
153
 
                                parent_map, missing_keys=[NULL_REVISION])
154
 
        parent_map[b'b'] = extended_history_shortcut[b'b']
155
 
        self.assertSearchResult([b'e', b'f'], [], 7,
156
 
                                parent_map, missing_keys=[NULL_REVISION])
157
 
 
158
 
 
159
 
class TestLimitedSearchResultFromParentMap(TestGraphBase):
160
 
 
161
 
    def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
162
 
                           missing_keys, tip_keys, depth):
163
 
        (start, stop, count) = vf_search.limited_search_result_from_parent_map(
164
 
            parent_map, missing_keys, tip_keys, depth)
165
 
        self.assertEqual((sorted(start_keys), sorted(stop_keys), key_count),
166
 
                         (sorted(start), sorted(stop), count))
167
 
 
168
 
    def test_empty_ancestry(self):
169
 
        self.assertSearchResult([], [], 0, {}, (), [b'tip-rev-id'], 10)
170
 
 
171
 
    def test_ancestry_1(self):
172
 
        self.assertSearchResult([b'rev4'], [b'rev1'], 4,
173
 
                                ancestry_1, (), [b'rev1'], 10)
174
 
        self.assertSearchResult([b'rev2a', b'rev2b'], [b'rev1'], 2,
175
 
                                ancestry_1, (), [b'rev1'], 1)
176
 
 
177
 
    def test_multiple_heads(self):
178
 
        self.assertSearchResult([b'e', b'f'], [b'a'], 5,
179
 
                                extended_history_shortcut, (), [b'a'], 10)
180
 
        # Note that even though we only take 1 step back, we find 'f', which
181
 
        # means the described search will still find d and c.
182
 
        self.assertSearchResult([b'f'], [b'a'], 4,
183
 
                                extended_history_shortcut, (), [b'a'], 1)
184
 
        self.assertSearchResult([b'f'], [b'a'], 4,
185
 
                                extended_history_shortcut, (), [b'a'], 2)
186
 
 
187
 
 
188
 
class TestPendingAncestryResultRefine(tests.TestCase):
189
 
 
190
 
    def make_graph(self, ancestors):
191
 
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
192
 
 
193
 
    def test_refine(self):
194
 
        # Used when pulling from a stacked repository, so test some revisions
195
 
        # being satisfied from the stacking branch.
196
 
        g = self.make_graph(
197
 
            {b"tip": [b"mid"], b"mid": [b"base"], b"tag": [b"base"],
198
 
             b"base": [NULL_REVISION], NULL_REVISION: []})
199
 
        result = vf_search.PendingAncestryResult([b'tip', b'tag'], None)
200
 
        result = result.refine({b'tip'}, {b'mid'})
201
 
        self.assertEqual({b'mid', b'tag'}, result.heads)
202
 
        result = result.refine({b'mid', b'tag', b'base'},
203
 
                               {NULL_REVISION})
204
 
        self.assertEqual({NULL_REVISION}, result.heads)
205
 
        self.assertTrue(result.is_empty())
206
 
 
207
 
 
208
 
class TestPendingAncestryResultGetKeys(tests.TestCaseWithMemoryTransport):
209
 
    """Tests for breezy.graph.PendingAncestryResult."""
210
 
 
211
 
    def test_get_keys(self):
212
 
        builder = self.make_branch_builder('b')
213
 
        builder.start_series()
214
 
        builder.build_snapshot(None, [
215
 
            ('add', ('', b'root-id', 'directory', ''))],
216
 
            revision_id=b'rev-1')
217
 
        builder.build_snapshot([b'rev-1'], [], revision_id=b'rev-2')
218
 
        builder.finish_series()
219
 
        repo = builder.get_branch().repository
220
 
        repo.lock_read()
221
 
        self.addCleanup(repo.unlock)
222
 
        result = vf_search.PendingAncestryResult([b'rev-2'], repo)
223
 
        self.assertEqual({b'rev-1', b'rev-2'}, set(result.get_keys()))
224
 
 
225
 
    def test_get_keys_excludes_ghosts(self):
226
 
        builder = self.make_branch_builder('b')
227
 
        builder.start_series()
228
 
        builder.build_snapshot(None, [
229
 
            ('add', ('', b'root-id', 'directory', ''))],
230
 
            revision_id=b'rev-1')
231
 
        builder.build_snapshot([b'rev-1', b'ghost'], [], revision_id=b'rev-2')
232
 
        builder.finish_series()
233
 
        repo = builder.get_branch().repository
234
 
        repo.lock_read()
235
 
        self.addCleanup(repo.unlock)
236
 
        result = vf_search.PendingAncestryResult([b'rev-2'], repo)
237
 
        self.assertEqual(sorted([b'rev-1', b'rev-2']),
238
 
                         sorted(result.get_keys()))
239
 
 
240
 
    def test_get_keys_excludes_null(self):
241
 
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
242
 
        # somewhere other than the last element, which can happen in real
243
 
        # ancestries.
244
 
        class StubGraph(object):
245
 
            def iter_ancestry(self, keys):
246
 
                return [(NULL_REVISION, ()), (b'foo', (NULL_REVISION,))]
247
 
        result = vf_search.PendingAncestryResult([b'rev-3'], None)
248
 
        result_keys = result._get_keys(StubGraph())
249
 
        # Only the non-null keys from the ancestry appear.
250
 
        self.assertEqual({b'foo'}, set(result_keys))