← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2007-08-01 17:14:51 UTC
  • mfrom: (2662.1.1 bzr.easy_install)
  • Revision ID: pqm@pqm.ubuntu.com-20070801171451-en3tds1hzlru2j83
allow ``easy_install bzr`` runs without fatal errors. (#125521, bialix,
 r=mbp)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
 
1
# Copyright (C) 2007 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
 
17
from bzrlib import (
 
18
    errors,
 
19
    graph as _mod_graph,
 
20
    )
 
21
from bzrlib.revision import NULL_REVISION
 
22
from bzrlib.tests import TestCaseWithMemoryTransport
 
23
 
 
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
 
 
40
# Ancestry 2:
 
41
#
 
42
#  NULL_REVISION
 
43
#    /    \
 
44
# rev1a  rev1b
 
45
#   |
 
46
# rev2a
 
47
#   |
 
48
# rev3a
 
49
#   |
 
50
# rev4a
 
51
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
 
52
              'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
 
53
 
 
54
 
 
55
# Criss cross ancestry
 
56
#
 
57
#     NULL_REVISION
 
58
#         |
 
59
#        rev1
 
60
#        /  \
 
61
#    rev2a  rev2b
 
62
#       |\  /|
 
63
#       |  X |
 
64
#       |/  \|
 
65
#    rev3a  rev3b
 
66
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
 
67
               'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
 
68
 
 
69
 
 
70
# Criss-cross 2
 
71
#
 
72
#  NULL_REVISION
 
73
#    /   \
 
74
# rev1a  rev1b
 
75
#   |\   /|
 
76
#   | \ / |
 
77
#   |  X  |
 
78
#   | / \ |
 
79
#   |/   \|
 
80
# rev2a  rev2b
 
81
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
 
82
                'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
 
83
 
 
84
 
 
85
# Mainline:
 
86
#
 
87
#  NULL_REVISION
 
88
#       |
 
89
#      rev1
 
90
#      /  \
 
91
#      | rev2b
 
92
#      |  /
 
93
#     rev2a
 
94
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
 
95
            'rev2b': ['rev1']}
 
96
 
 
97
 
 
98
# feature branch:
 
99
#
 
100
#  NULL_REVISION
 
101
#       |
 
102
#      rev1
 
103
#       |
 
104
#     rev2b
 
105
#       |
 
106
#     rev3b
 
107
feature_branch = {'rev1': [NULL_REVISION],
 
108
                  'rev2b': ['rev1'], 'rev3b': ['rev2b']}
 
109
 
 
110
 
 
111
# History shortcut
 
112
#  NULL_REVISION
 
113
#       |
 
114
#     rev1------
 
115
#     /  \      \
 
116
#  rev2a rev2b rev2c
 
117
#    |  /   \   /
 
118
#  rev3a    reveb
 
119
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
 
120
                    'rev2b': ['rev1'], 'rev2c': ['rev1'],
 
121
                    'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
 
122
 
 
123
#  NULL_REVISION
 
124
#       |
 
125
#       f
 
126
#       |
 
127
#       e
 
128
#      / \
 
129
#     b   d
 
130
#     | \ |
 
131
#     a   c
 
132
 
 
133
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
 
134
            'f':[NULL_REVISION]}
 
135
 
 
136
 
 
137
class InstrumentedParentsProvider(object):
 
138
 
 
139
    def __init__(self, parents_provider):
 
140
        self.calls = []
 
141
        self._real_parents_provider = parents_provider
 
142
 
 
143
    def get_parents(self, nodes):
 
144
        self.calls.extend(nodes)
 
145
        return self._real_parents_provider.get_parents(nodes)
 
146
 
 
147
 
 
148
class TestGraph(TestCaseWithMemoryTransport):
 
149
 
 
150
    def make_graph(self, ancestors):
 
151
        tree = self.prepare_memory_tree('.')
 
152
        self.build_ancestry(tree, ancestors)
 
153
        tree.unlock()
 
154
        return tree.branch.repository.get_graph()
 
155
 
 
156
    def prepare_memory_tree(self, location):
 
157
        tree = self.make_branch_and_memory_tree(location)
 
158
        tree.lock_write()
 
159
        tree.add('.')
 
160
        return tree
 
161
 
 
162
    def build_ancestry(self, tree, ancestors):
 
163
        """Create an ancestry as specified by a graph dict
 
164
 
 
165
        :param tree: A tree to use
 
166
        :param ancestors: a dict of {node: [node_parent, ...]}
 
167
        """
 
168
        pending = [NULL_REVISION]
 
169
        descendants = {}
 
170
        for descendant, parents in ancestors.iteritems():
 
171
            for parent in parents:
 
172
                descendants.setdefault(parent, []).append(descendant)
 
173
        while len(pending) > 0:
 
174
            cur_node = pending.pop()
 
175
            for descendant in descendants.get(cur_node, []):
 
176
                if tree.branch.repository.has_revision(descendant):
 
177
                    continue
 
178
                parents = [p for p in ancestors[descendant] if p is not
 
179
                           NULL_REVISION]
 
180
                if len([p for p in parents if not
 
181
                    tree.branch.repository.has_revision(p)]) > 0:
 
182
                    continue
 
183
                tree.set_parent_ids(parents)
 
184
                if len(parents) > 0:
 
185
                    left_parent = parents[0]
 
186
                else:
 
187
                    left_parent = NULL_REVISION
 
188
                tree.branch.set_last_revision_info(
 
189
                    len(tree.branch._lefthand_history(left_parent)),
 
190
                    left_parent)
 
191
                tree.commit(descendant, rev_id=descendant)
 
192
                pending.append(descendant)
 
193
 
 
194
    def test_lca(self):
 
195
        """Test finding least common ancestor.
 
196
 
 
197
        ancestry_1 should always have a single common ancestor
 
198
        """
 
199
        graph = self.make_graph(ancestry_1)
 
200
        self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
 
201
        self.assertEqual(set([NULL_REVISION]),
 
202
                         graph.find_lca(NULL_REVISION, NULL_REVISION))
 
203
        self.assertEqual(set([NULL_REVISION]),
 
204
                         graph.find_lca(NULL_REVISION, 'rev1'))
 
205
        self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
 
206
        self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
 
207
 
 
208
    def test_no_unique_lca(self):
 
209
        """Test error when one revision is not in the graph"""
 
210
        graph = self.make_graph(ancestry_1)
 
211
        self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
 
212
                          'rev1', '1rev')
 
213
 
 
214
    def test_lca_criss_cross(self):
 
215
        """Test least-common-ancestor after a criss-cross merge."""
 
216
        graph = self.make_graph(criss_cross)
 
217
        self.assertEqual(set(['rev2a', 'rev2b']),
 
218
                         graph.find_lca('rev3a', 'rev3b'))
 
219
        self.assertEqual(set(['rev2b']),
 
220
                         graph.find_lca('rev3a', 'rev3b', 'rev2b'))
 
221
 
 
222
    def test_lca_shortcut(self):
 
223
        """Test least-common ancestor on this history shortcut"""
 
224
        graph = self.make_graph(history_shortcut)
 
225
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
 
226
 
 
227
    def test_recursive_unique_lca(self):
 
228
        """Test finding a unique least common ancestor.
 
229
 
 
230
        ancestry_1 should always have a single common ancestor
 
231
        """
 
232
        graph = self.make_graph(ancestry_1)
 
233
        self.assertEqual(NULL_REVISION,
 
234
                         graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
 
235
        self.assertEqual(NULL_REVISION,
 
236
                         graph.find_unique_lca(NULL_REVISION, 'rev1'))
 
237
        self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
 
238
        self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
 
239
 
 
240
    def test_unique_lca_criss_cross(self):
 
241
        """Ensure we don't pick non-unique lcas in a criss-cross"""
 
242
        graph = self.make_graph(criss_cross)
 
243
        self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
 
244
 
 
245
    def test_unique_lca_null_revision(self):
 
246
        """Ensure we pick NULL_REVISION when necessary"""
 
247
        graph = self.make_graph(criss_cross2)
 
248
        self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
 
249
        self.assertEqual(NULL_REVISION,
 
250
                         graph.find_unique_lca('rev2a', 'rev2b'))
 
251
 
 
252
    def test_unique_lca_null_revision2(self):
 
253
        """Ensure we pick NULL_REVISION when necessary"""
 
254
        graph = self.make_graph(ancestry_2)
 
255
        self.assertEqual(NULL_REVISION,
 
256
                         graph.find_unique_lca('rev4a', 'rev1b'))
 
257
 
 
258
    def test_common_ancestor_two_repos(self):
 
259
        """Ensure we do unique_lca using data from two repos"""
 
260
        mainline_tree = self.prepare_memory_tree('mainline')
 
261
        self.build_ancestry(mainline_tree, mainline)
 
262
        mainline_tree.unlock()
 
263
 
 
264
        # This is cheating, because the revisions in the graph are actually
 
265
        # different revisions, despite having the same revision-id.
 
266
        feature_tree = self.prepare_memory_tree('feature')
 
267
        self.build_ancestry(feature_tree, feature_branch)
 
268
        feature_tree.unlock()
 
269
        graph = mainline_tree.branch.repository.get_graph(
 
270
            feature_tree.branch.repository)
 
271
        self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
 
272
 
 
273
    def test_graph_difference(self):
 
274
        graph = self.make_graph(ancestry_1)
 
275
        self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
 
276
        self.assertEqual((set(), set(['rev1'])),
 
277
                         graph.find_difference(NULL_REVISION, 'rev1'))
 
278
        self.assertEqual((set(['rev1']), set()),
 
279
                         graph.find_difference('rev1', NULL_REVISION))
 
280
        self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
 
281
                         graph.find_difference('rev3', 'rev2b'))
 
282
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
 
283
                         graph.find_difference('rev4', 'rev2b'))
 
284
 
 
285
    def test_graph_difference_criss_cross(self):
 
286
        graph = self.make_graph(criss_cross)
 
287
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
 
288
                         graph.find_difference('rev3a', 'rev3b'))
 
289
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
 
290
                         graph.find_difference('rev2a', 'rev3b'))
 
291
 
 
292
    def test_stacked_parents_provider(self):
 
293
 
 
294
        class ParentsProvider(object):
 
295
 
 
296
            def __init__(self, ancestry):
 
297
                self.ancestry = ancestry
 
298
 
 
299
            def get_parents(self, revisions):
 
300
                return [self.ancestry.get(r, None) for r in revisions]
 
301
 
 
302
        parents1 = ParentsProvider({'rev2': ['rev3']})
 
303
        parents2 = ParentsProvider({'rev1': ['rev4']})
 
304
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
 
305
        self.assertEqual([['rev4',], ['rev3']],
 
306
                         stacked.get_parents(['rev1', 'rev2']))
 
307
        self.assertEqual([['rev3',], ['rev4']],
 
308
                         stacked.get_parents(['rev2', 'rev1']))
 
309
        self.assertEqual([['rev3',], ['rev3']],
 
310
                         stacked.get_parents(['rev2', 'rev2']))
 
311
        self.assertEqual([['rev4',], ['rev4']],
 
312
                         stacked.get_parents(['rev1', 'rev1']))
 
313
 
 
314
    def test_iter_topo_order(self):
 
315
        graph = self.make_graph(ancestry_1)
 
316
        args = ['rev2a', 'rev3', 'rev1']
 
317
        topo_args = list(graph.iter_topo_order(args))
 
318
        self.assertEqual(set(args), set(topo_args))
 
319
        self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
 
320
        self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
 
321
 
 
322
    def test_is_ancestor(self):
 
323
        graph = self.make_graph(ancestry_1)
 
324
        self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
 
325
        self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
 
326
        self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
 
327
        self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
 
328
        self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
 
329
        self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
 
330
        self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
 
331
        self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
 
332
        self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
 
333
        instrumented_provider = InstrumentedParentsProvider(graph)
 
334
        instrumented_graph = _mod_graph.Graph(instrumented_provider)
 
335
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
 
336
        self.assertTrue('null:' not in instrumented_provider.calls)
 
337
 
 
338
    def test_is_ancestor_boundary(self):
 
339
        """Ensure that we avoid searching the whole graph.
 
340
        
 
341
        This requires searching through b as a common ancestor, so we
 
342
        can identify that e is common.
 
343
        """
 
344
        graph = self.make_graph(boundary)
 
345
        instrumented_provider = InstrumentedParentsProvider(graph)
 
346
        graph = _mod_graph.Graph(instrumented_provider)
 
347
        self.assertFalse(graph.is_ancestor('a', 'c'))
 
348
        self.assertTrue('null:' not in instrumented_provider.calls)