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

  • Committer: Vincent Ladeuil
  • Date: 2012-01-18 14:09:19 UTC
  • mto: This revision was merged to the branch mainline in revision 6468.
  • Revision ID: v.ladeuil+lp@free.fr-20120118140919-rlvdrhpc0nq1lbwi
Change set/remove to require a lock for the branch config files.

This means that tests (or any plugin for that matter) do not requires an
explicit lock on the branch anymore to change a single option. This also
means the optimisation becomes "opt-in" and as such won't be as
spectacular as it may be and/or harder to get right (nothing fails
anymore).

This reduces the diff by ~300 lines.

Code/tests that were updating more than one config option is still taking
a lock to at least avoid some IOs and demonstrate the benefits through
the decreased number of hpss calls.

The duplication between BranchStack and BranchOnlyStack will be removed
once the same sharing is in place for local config files, at which point
the Stack class itself may be able to host the changes.

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