← 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: 2008-05-05 23:15:58 UTC
  • mfrom: (3377.3.45 submitted)
  • Revision ID: pqm@pqm.ubuntu.com-20080505231558-7w3zaehbvtcjk7jv
(jam) Make Graph.find_differences() correct,
        and create a Graph.find_unique_ancestors function.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
165
165
# Complex shortcut
166
166
# This has a failure mode in that a shortcut will find some nodes in common,
167
167
# but the common searcher won't have time to find that one branch is actually
168
 
# in common. The extra nodes at the top are because we want to avoid
 
168
# in common. The extra nodes at the beginning are because we want to avoid
169
169
# walking off the graph. Specifically, node G should be considered common, but
170
170
# is likely to be seen by M long before the common searcher finds it.
171
171
#
181
181
#     |\
182
182
#     e f
183
183
#     | |\
184
 
#     i | h
185
 
#     |\| |
186
 
#     | g |
187
 
#     | | |
188
 
#     | j |
 
184
#     | g h
 
185
#     |/| |
 
186
#     i j |
189
187
#     | | |
190
188
#     | k |
191
189
#     | | |
192
190
#     | l |
193
191
#     |/|/
194
192
#     m n
195
 
complex_shortcut = {'d':[NULL_REVISION],
196
 
                    'x':['d'], 'y':['x'],
197
 
                    'e':['y'], 'f':['d'], 'g':['f', 'i'], 'h':['f'],
198
 
                    'i':['e'], 'j':['g'], 'k':['j'],
199
 
                    'l':['k'], 'm':['i', 's'], 'n':['s', 'h'],
200
 
                    'o':['l'], 'p':['o'], 'q':['p'],
201
 
                    'r':['q'], 's':['r'],
 
193
complex_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
 
194
                    'e':['d'], 'f':['d'], 'g':['f'], 'h':['f'],
 
195
                    'i':['e', 'g'], 'j':['g'], 'k':['j'],
 
196
                    'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
 
197
 
 
198
# NULL_REVISION
 
199
#     |
 
200
#     a
 
201
#     |
 
202
#     b
 
203
#     |
 
204
#     c
 
205
#     |
 
206
#     d
 
207
#     |\
 
208
#     e |
 
209
#     | |
 
210
#     f |
 
211
#     | |
 
212
#     g h
 
213
#     | |\
 
214
#     i | j
 
215
#     |\| |
 
216
#     | k |
 
217
#     | | |
 
218
#     | l |
 
219
#     | | |
 
220
#     | m |
 
221
#     | | |
 
222
#     | n |
 
223
#     | | |
 
224
#     | o |
 
225
#     | | |
 
226
#     | p |
 
227
#     | | |
 
228
#     | q |
 
229
#     | | |
 
230
#     | r |
 
231
#     | | |
 
232
#     | s |
 
233
#     | | |
 
234
#     |/|/
 
235
#     t u
 
236
complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
 
237
                    'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
 
238
                    'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
 
239
                    'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
 
240
                    't':['i', 's'], 'u':['s', 'j'], 
202
241
                    }
203
242
 
 
243
# Graph where different walkers will race to find the common and uncommon
 
244
# nodes.
 
245
#
 
246
# NULL_REVISION
 
247
#     |
 
248
#     a
 
249
#     |
 
250
#     b
 
251
#     |
 
252
#     c
 
253
#     |
 
254
#     d
 
255
#     |\
 
256
#     e k
 
257
#     | |
 
258
#     f-+-p
 
259
#     | | |
 
260
#     | l |
 
261
#     | | |
 
262
#     | m |
 
263
#     | |\|
 
264
#     g n q
 
265
#     |\| |
 
266
#     h o |
 
267
#     |/| |
 
268
#     i r |
 
269
#     | | |
 
270
#     | s |
 
271
#     | | |
 
272
#     | t |
 
273
#     | | |
 
274
#     | u |
 
275
#     | | |
 
276
#     | v |
 
277
#     | | |
 
278
#     | w |
 
279
#     | | |
 
280
#     | x |
 
281
#     | |\|
 
282
#     | y z
 
283
#     |/
 
284
#     j
 
285
#
 
286
# y is found to be common right away, but is the start of a long series of
 
287
# common commits.
 
288
# o is actually common, but the i-j shortcut makes it look like it is actually
 
289
# unique to j at first, you have to traverse all of y->o to find it.
 
290
# q,n give the walker from j a common point to stop searching, as does p,f.
 
291
# k-n exists so that the second pass still has nodes that are worth searching,
 
292
# rather than instantly cancelling the extra walker.
 
293
 
 
294
racing_shortcuts = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
 
295
    'e':['d'], 'f':['e'], 'g':['f'], 'h':['g'], 'i':['h', 'o'], 'j':['i', 'y'],
 
296
    'k':['d'], 'l':['k'], 'm':['l'], 'n':['m'], 'o':['n', 'g'], 'p':['f'],
 
297
    'q':['p', 'm'], 'r':['o'], 's':['r'], 't':['s'], 'u':['t'], 'v':['u'],
 
298
    'w':['v'], 'x':['w'], 'y':['x'], 'z':['x', 'q']}
 
299
 
 
300
 
 
301
# A graph with multiple nodes unique to one side.
 
302
#
 
303
# NULL_REVISION
 
304
#     |
 
305
#     a
 
306
#     |
 
307
#     b
 
308
#     |
 
309
#     c
 
310
#     |
 
311
#     d
 
312
#     |\
 
313
#     e f
 
314
#     |\ \
 
315
#     g h i
 
316
#     |\ \ \
 
317
#     j k l m
 
318
#     | |/ x|
 
319
#     | n o p
 
320
#     | |/  |
 
321
#     | q   |
 
322
#     | |   |
 
323
#     | r   |
 
324
#     | |   |
 
325
#     | s   |
 
326
#     | |   |
 
327
#     | t   |
 
328
#     | |   |
 
329
#     | u   |
 
330
#     | |   |
 
331
#     | v   |
 
332
#     | |   |
 
333
#     | w   |
 
334
#     | |   |
 
335
#     | x   |
 
336
#     |/ \ /
 
337
#     y   z
 
338
#
 
339
 
 
340
multiple_interesting_unique = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
 
341
    'd':['c'], 'e':['d'], 'f':['d'], 'g':['e'], 'h':['e'], 'i':['f'],
 
342
    'j':['g'], 'k':['g'], 'l':['h'], 'm':['i'], 'n':['k', 'l'],
 
343
    'o':['m'], 'p':['m', 'l'], 'q':['n', 'o'], 'r':['q'], 's':['r'],
 
344
    't':['s'], 'u':['t'], 'v':['u'], 'w':['v'], 'x':['w'],
 
345
    'y':['j', 'x'], 'z':['x', 'p']}
 
346
 
 
347
 
204
348
# Shortcut with extra root
205
349
# We have a long history shortcut, and an extra root, which is why we can't
206
350
# stop searchers based on seeing NULL_REVISION
357
501
                         graph.find_unique_lca('rev2a', 'rev2b',
358
502
                         count_steps=True))
359
503
 
 
504
    def assertRemoveDescendants(self, expected, graph, revisions):
 
505
        parents = graph.get_parent_map(revisions)
 
506
        self.assertEqual(expected,
 
507
                         graph._remove_simple_descendants(revisions, parents))
 
508
 
 
509
    def test__remove_simple_descendants(self):
 
510
        graph = self.make_graph(ancestry_1)
 
511
        self.assertRemoveDescendants(set(['rev1']), graph,
 
512
            set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
 
513
 
 
514
    def test__remove_simple_descendants_disjoint(self):
 
515
        graph = self.make_graph(ancestry_1)
 
516
        self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
 
517
            set(['rev1', 'rev3']))
 
518
 
 
519
    def test__remove_simple_descendants_chain(self):
 
520
        graph = self.make_graph(ancestry_1)
 
521
        self.assertRemoveDescendants(set(['rev1']), graph,
 
522
            set(['rev1', 'rev2a', 'rev3']))
 
523
 
 
524
    def test__remove_simple_descendants_siblings(self):
 
525
        graph = self.make_graph(ancestry_1)
 
526
        self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
 
527
            set(['rev2a', 'rev2b', 'rev3']))
 
528
 
360
529
    def test_unique_lca_criss_cross(self):
361
530
        """Ensure we don't pick non-unique lcas in a criss-cross"""
362
531
        graph = self.make_graph(criss_cross)
427
596
 
428
597
    def test_graph_difference_extended_history(self):
429
598
        graph = self.make_graph(extended_history_shortcut)
430
 
        self.expectFailure('find_difference cannot handle shortcuts',
431
 
            self.assertEqual, (set(['e']), set(['f'])),
432
 
                graph.find_difference('e', 'f'))
433
599
        self.assertEqual((set(['e']), set(['f'])),
434
600
                         graph.find_difference('e', 'f'))
435
601
        self.assertEqual((set(['f']), set(['e'])),
442
608
 
443
609
    def test_graph_difference_complex_shortcut(self):
444
610
        graph = self.make_graph(complex_shortcut)
445
 
        self.expectFailure('find_difference cannot handle shortcuts',
446
 
            self.assertEqual, (set(['m']), set(['h', 'n'])),
447
 
                graph.find_difference('m', 'n'))
448
 
        self.assertEqual((set(['m']), set(['h', 'n'])),
 
611
        self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
449
612
                         graph.find_difference('m', 'n'))
450
613
 
 
614
    def test_graph_difference_complex_shortcut2(self):
 
615
        graph = self.make_graph(complex_shortcut2)
 
616
        self.assertEqual((set(['t']), set(['j', 'u'])),
 
617
                         graph.find_difference('t', 'u'))
 
618
 
451
619
    def test_graph_difference_shortcut_extra_root(self):
452
620
        graph = self.make_graph(shortcut_extra_root)
453
 
        self.expectFailure('find_difference cannot handle shortcuts',
454
 
            self.assertEqual, (set(['e']), set(['f', 'g'])),
455
 
                graph.find_difference('e', 'f'))
456
621
        self.assertEqual((set(['e']), set(['f', 'g'])),
457
622
                         graph.find_difference('e', 'f'))
458
623
 
973
1138
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
974
1139
 
975
1140
 
 
1141
class TestFindUniqueAncestors(tests.TestCase):
 
1142
 
 
1143
    def make_graph(self, ancestors):
 
1144
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
 
1145
 
 
1146
    def make_breaking_graph(self, ancestors, break_on):
 
1147
        """Make a Graph that raises an exception if we hit a node."""
 
1148
        g = self.make_graph(ancestors)
 
1149
        orig_parent_map = g.get_parent_map
 
1150
        def get_parent_map(keys):
 
1151
            bad_keys = set(keys).intersection(break_on)
 
1152
            if bad_keys:
 
1153
                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
 
1154
            return orig_parent_map(keys)
 
1155
        g.get_parent_map = get_parent_map
 
1156
        return g
 
1157
 
 
1158
    def assertFindUniqueAncestors(self, graph, expected, node, common):
 
1159
        actual = graph.find_unique_ancestors(node, common)
 
1160
        self.assertEqual(expected, sorted(actual))
 
1161
 
 
1162
    def test_empty_set(self):
 
1163
        graph = self.make_graph(ancestry_1)
 
1164
        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
 
1165
        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
 
1166
        self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
 
1167
 
 
1168
    def test_single_node(self):
 
1169
        graph = self.make_graph(ancestry_1)
 
1170
        self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
 
1171
        self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
 
1172
        self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
 
1173
 
 
1174
    def test_minimal_ancestry(self):
 
1175
        graph = self.make_breaking_graph(extended_history_shortcut,
 
1176
                                         [NULL_REVISION, 'a', 'b'])
 
1177
        self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
 
1178
 
 
1179
        graph = self.make_breaking_graph(extended_history_shortcut,
 
1180
                                         ['b'])
 
1181
        self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
 
1182
 
 
1183
        graph = self.make_breaking_graph(complex_shortcut,
 
1184
                                         ['a', 'b'])
 
1185
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
 
1186
        self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
 
1187
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
 
1188
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
 
1189
 
 
1190
    def test_in_ancestry(self):
 
1191
        graph = self.make_graph(ancestry_1)
 
1192
        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
 
1193
        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
 
1194
 
 
1195
    def test_multiple_revisions(self):
 
1196
        graph = self.make_graph(ancestry_1)
 
1197
        self.assertFindUniqueAncestors(graph,
 
1198
            ['rev4'], 'rev4', ['rev3', 'rev2b'])
 
1199
        self.assertFindUniqueAncestors(graph,
 
1200
            ['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
 
1201
 
 
1202
    def test_complex_shortcut(self):
 
1203
        graph = self.make_graph(complex_shortcut)
 
1204
        self.assertFindUniqueAncestors(graph,
 
1205
            ['h', 'n'], 'n', ['m'])
 
1206
        self.assertFindUniqueAncestors(graph,
 
1207
            ['e', 'i', 'm'], 'm', ['n'])
 
1208
 
 
1209
    def test_complex_shortcut2(self):
 
1210
        graph = self.make_graph(complex_shortcut2)
 
1211
        self.assertFindUniqueAncestors(graph,
 
1212
            ['j', 'u'], 'u', ['t'])
 
1213
        self.assertFindUniqueAncestors(graph,
 
1214
            ['t'], 't', ['u'])
 
1215
 
 
1216
    def test_multiple_interesting_unique(self):
 
1217
        graph = self.make_graph(multiple_interesting_unique)
 
1218
        self.assertFindUniqueAncestors(graph,
 
1219
            ['j', 'y'], 'y', ['z'])
 
1220
        self.assertFindUniqueAncestors(graph,
 
1221
            ['p', 'z'], 'z', ['y'])
 
1222
 
 
1223
    def test_racing_shortcuts(self):
 
1224
        graph = self.make_graph(racing_shortcuts)
 
1225
        self.assertFindUniqueAncestors(graph,
 
1226
            ['p', 'q', 'z'], 'z', ['y'])
 
1227
        self.assertFindUniqueAncestors(graph,
 
1228
            ['h', 'i', 'j', 'y'], 'j', ['z'])
 
1229
 
 
1230
 
976
1231
class TestCachingParentsProvider(tests.TestCase):
977
1232
 
978
1233
    def setUp(self):