← 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

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2008-09-03 22:30:56 UTC
  • mfrom: (3644.2.13 index_builder_cleanup)
  • Revision ID: pqm@pqm.ubuntu.com-20080903223056-b108iytb38xkznci
(jam) Streamline BTreeBuilder.add_node et al to make btree creation
        faster.

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))