/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__known_graph.py

  • Committer: Richard Wilbur
  • Date: 2016-02-04 19:07:28 UTC
  • mto: This revision was merged to the branch mainline in revision 6618.
  • Revision ID: richard.wilbur@gmail.com-20160204190728-p0zvfii6zase0fw7
Update COPYING.txt from the original http://www.gnu.org/licenses/gpl-2.0.txt  (Only differences were in whitespace.)  Thanks to Petr Stodulka for pointing out the discrepancy.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__known_graph.py
18
18
 
19
19
import pprint
20
20
 
21
 
from .. import (
 
21
from bzrlib import (
22
22
    errors,
23
23
    _known_graph_py,
24
24
    tests,
25
25
    )
26
 
from . import test_graph
27
 
from ..revision import NULL_REVISION
28
 
from .scenarios import load_tests_apply_scenarios
29
 
from . import (
 
26
from bzrlib.tests import test_graph
 
27
from bzrlib.revision import NULL_REVISION
 
28
from bzrlib.tests.scenarios import load_tests_apply_scenarios
 
29
from bzrlib.tests import (
30
30
    features,
31
31
    )
32
32
 
56
56
 
57
57
 
58
58
compiled_known_graph_feature = features.ModuleAvailableFeature(
59
 
    'breezy._known_graph_pyx')
 
59
    'bzrlib._known_graph_pyx')
60
60
 
61
61
 
62
62
#  a
216
216
 
217
217
    def test_heads_null(self):
218
218
        graph = self.make_known_graph(test_graph.ancestry_1)
219
 
        self.assertEqual({'null:'}, graph.heads(['null:']))
220
 
        self.assertEqual({'rev1'}, graph.heads(['null:', 'rev1']))
221
 
        self.assertEqual({'rev1'}, graph.heads(['rev1', 'null:']))
222
 
        self.assertEqual({'rev1'}, graph.heads({'rev1', 'null:'}))
223
 
        self.assertEqual({'rev1'}, graph.heads(('rev1', 'null:')))
 
219
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
220
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
 
221
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
 
222
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
 
223
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
224
224
 
225
225
    def test_heads_one(self):
226
226
        # A single node will always be a head
227
227
        graph = self.make_known_graph(test_graph.ancestry_1)
228
 
        self.assertEqual({'null:'}, graph.heads(['null:']))
229
 
        self.assertEqual({'rev1'}, graph.heads(['rev1']))
230
 
        self.assertEqual({'rev2a'}, graph.heads(['rev2a']))
231
 
        self.assertEqual({'rev2b'}, graph.heads(['rev2b']))
232
 
        self.assertEqual({'rev3'}, graph.heads(['rev3']))
233
 
        self.assertEqual({'rev4'}, graph.heads(['rev4']))
 
228
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
229
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
 
230
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
 
231
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
 
232
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
 
233
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
234
234
 
235
235
    def test_heads_single(self):
236
236
        graph = self.make_known_graph(test_graph.ancestry_1)
237
 
        self.assertEqual({'rev4'}, graph.heads(['null:', 'rev4']))
238
 
        self.assertEqual({'rev2a'}, graph.heads(['rev1', 'rev2a']))
239
 
        self.assertEqual({'rev2b'}, graph.heads(['rev1', 'rev2b']))
240
 
        self.assertEqual({'rev3'}, graph.heads(['rev1', 'rev3']))
241
 
        self.assertEqual({'rev3'}, graph.heads(['rev3', 'rev2a']))
242
 
        self.assertEqual({'rev4'}, graph.heads(['rev1', 'rev4']))
243
 
        self.assertEqual({'rev4'}, graph.heads(['rev2a', 'rev4']))
244
 
        self.assertEqual({'rev4'}, graph.heads(['rev2b', 'rev4']))
245
 
        self.assertEqual({'rev4'}, graph.heads(['rev3', 'rev4']))
 
237
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
 
238
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
 
239
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
 
240
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
 
241
        self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
 
242
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
 
243
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
 
244
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
 
245
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
246
246
 
247
247
    def test_heads_two_heads(self):
248
248
        graph = self.make_known_graph(test_graph.ancestry_1)
249
 
        self.assertEqual({'rev2a', 'rev2b'},
 
249
        self.assertEqual(set(['rev2a', 'rev2b']),
250
250
                         graph.heads(['rev2a', 'rev2b']))
251
 
        self.assertEqual({'rev3', 'rev2b'},
 
251
        self.assertEqual(set(['rev3', 'rev2b']),
252
252
                         graph.heads(['rev3', 'rev2b']))
253
253
 
254
254
    def test_heads_criss_cross(self):
255
255
        graph = self.make_known_graph(test_graph.criss_cross)
256
 
        self.assertEqual({'rev2a'},
 
256
        self.assertEqual(set(['rev2a']),
257
257
                         graph.heads(['rev2a', 'rev1']))
258
 
        self.assertEqual({'rev2b'},
 
258
        self.assertEqual(set(['rev2b']),
259
259
                         graph.heads(['rev2b', 'rev1']))
260
 
        self.assertEqual({'rev3a'},
 
260
        self.assertEqual(set(['rev3a']),
261
261
                         graph.heads(['rev3a', 'rev1']))
262
 
        self.assertEqual({'rev3b'},
 
262
        self.assertEqual(set(['rev3b']),
263
263
                         graph.heads(['rev3b', 'rev1']))
264
 
        self.assertEqual({'rev2a', 'rev2b'},
 
264
        self.assertEqual(set(['rev2a', 'rev2b']),
265
265
                         graph.heads(['rev2a', 'rev2b']))
266
 
        self.assertEqual({'rev3a'},
 
266
        self.assertEqual(set(['rev3a']),
267
267
                         graph.heads(['rev3a', 'rev2a']))
268
 
        self.assertEqual({'rev3a'},
 
268
        self.assertEqual(set(['rev3a']),
269
269
                         graph.heads(['rev3a', 'rev2b']))
270
 
        self.assertEqual({'rev3a'},
 
270
        self.assertEqual(set(['rev3a']),
271
271
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
272
 
        self.assertEqual({'rev3b'},
 
272
        self.assertEqual(set(['rev3b']),
273
273
                         graph.heads(['rev3b', 'rev2a']))
274
 
        self.assertEqual({'rev3b'},
 
274
        self.assertEqual(set(['rev3b']),
275
275
                         graph.heads(['rev3b', 'rev2b']))
276
 
        self.assertEqual({'rev3b'},
 
276
        self.assertEqual(set(['rev3b']),
277
277
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
278
 
        self.assertEqual({'rev3a', 'rev3b'},
 
278
        self.assertEqual(set(['rev3a', 'rev3b']),
279
279
                         graph.heads(['rev3a', 'rev3b']))
280
 
        self.assertEqual({'rev3a', 'rev3b'},
 
280
        self.assertEqual(set(['rev3a', 'rev3b']),
281
281
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
282
282
 
283
283
    def test_heads_shortcut(self):
284
284
        graph = self.make_known_graph(test_graph.history_shortcut)
285
 
        self.assertEqual({'rev2a', 'rev2b', 'rev2c'},
 
285
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
286
286
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
287
 
        self.assertEqual({'rev3a', 'rev3b'},
 
287
        self.assertEqual(set(['rev3a', 'rev3b']),
288
288
                         graph.heads(['rev3a', 'rev3b']))
289
 
        self.assertEqual({'rev3a', 'rev3b'},
 
289
        self.assertEqual(set(['rev3a', 'rev3b']),
290
290
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
291
 
        self.assertEqual({'rev2a', 'rev3b'},
 
291
        self.assertEqual(set(['rev2a', 'rev3b']),
292
292
                         graph.heads(['rev2a', 'rev3b']))
293
 
        self.assertEqual({'rev2c', 'rev3a'},
 
293
        self.assertEqual(set(['rev2c', 'rev3a']),
294
294
                         graph.heads(['rev2c', 'rev3a']))
295
295
 
296
296
    def test_heads_linear(self):
297
297
        graph = self.make_known_graph(test_graph.racing_shortcuts)
298
 
        self.assertEqual({'w'}, graph.heads(['w', 's']))
299
 
        self.assertEqual({'z'}, graph.heads(['w', 's', 'z']))
300
 
        self.assertEqual({'w', 'q'}, graph.heads(['w', 's', 'q']))
301
 
        self.assertEqual({'z'}, graph.heads(['s', 'z']))
 
298
        self.assertEqual(set(['w']), graph.heads(['w', 's']))
 
299
        self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
 
300
        self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
 
301
        self.assertEqual(set(['z']), graph.heads(['s', 'z']))
302
302
 
303
303
    def test_heads_alt_merge(self):
304
304
        graph = self.make_known_graph(alt_merge)
305
 
        self.assertEqual({'c'}, graph.heads(['a', 'c']))
 
305
        self.assertEqual(set(['c']), graph.heads(['a', 'c']))
306
306
 
307
307
    def test_heads_with_ghost(self):
308
308
        graph = self.make_known_graph(test_graph.with_ghost)
309
 
        self.assertEqual({'e', 'g'}, graph.heads(['e', 'g']))
310
 
        self.assertEqual({'a', 'c'}, graph.heads(['a', 'c']))
311
 
        self.assertEqual({'a', 'g'}, graph.heads(['a', 'g']))
312
 
        self.assertEqual({'f', 'g'}, graph.heads(['f', 'g']))
313
 
        self.assertEqual({'c'}, graph.heads(['c', 'g']))
314
 
        self.assertEqual({'c'}, graph.heads(['c', 'b', 'd', 'g']))
315
 
        self.assertEqual({'a', 'c'}, graph.heads(['a', 'c', 'e', 'g']))
316
 
        self.assertEqual({'a', 'c'}, graph.heads(['a', 'c', 'f']))
 
309
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
 
310
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
 
311
        self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
 
312
        self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
 
313
        self.assertEqual(set(['c']), graph.heads(['c', 'g']))
 
314
        self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
 
315
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
 
316
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
317
317
 
318
318
    def test_filling_in_ghosts_resets_head_cache(self):
319
319
        graph = self.make_known_graph(test_graph.with_ghost)
320
 
        self.assertEqual({'e', 'g'}, graph.heads(['e', 'g']))
 
320
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
321
321
        # 'g' is filled in, and decends from 'e', so the heads result is now
322
322
        # different
323
323
        graph.add_node('g', ['e'])
324
 
        self.assertEqual({'g'}, graph.heads(['e', 'g']))
 
324
        self.assertEqual(set(['g']), graph.heads(['e', 'g']))
325
325
 
326
326
 
327
327
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
462
462
             'C': ['A', 'B']},
463
463
            'C',
464
464
            [('C', 0, (2,), False),
465
 
             ('B', 1, (1, 1, 1), True),
 
465
             ('B', 1, (1,1,1), True),
466
466
             ('A', 0, (1,), True),
467
467
             ],
468
468
            )
485
485
                 }
486
486
        self.assertSortAndIterate(graph, 'F',
487
487
            [('F', 0, (3,), False),
488
 
             ('D', 1, (2, 2, 1), False),
489
 
             ('C', 2, (2, 1, 1), True),
 
488
             ('D', 1, (2,2,1), False),
 
489
             ('C', 2, (2,1,1), True),
490
490
             ('B', 0, (2,), False),
491
491
             ('A', 0, (1,), True),
492
492
             ])
508
508
                 }
509
509
        self.assertSortAndIterate(graph, 'F',
510
510
            [('F', 0, (3,), False),
511
 
             ('D', 1, (2, 1, 2), False),
512
 
             ('C', 2, (2, 2, 1), True),
513
 
             ('X', 1, (2, 1, 1), True),
 
511
             ('D', 1, (2,1,2), False),
 
512
             ('C', 2, (2,2,1), True),
 
513
             ('X', 1, (2,1,1), True),
514
514
             ('B', 0, (2,), False),
515
515
             ('A', 0, (1,), True),
516
516
             ])
539
539
             },
540
540
            'A',
541
541
            [('A', 0, (3,),  False),
542
 
             ('B', 1, (1, 3, 2), False),
543
 
             ('C', 1, (1, 3, 1), True),
 
542
             ('B', 1, (1,3,2), False),
 
543
             ('C', 1, (1,3,1), True),
544
544
             ('D', 0, (2,), False),
545
 
             ('E', 1, (1, 1, 2), False),
546
 
             ('F', 2, (1, 2, 1), True),
547
 
             ('G', 1, (1, 1, 1), True),
 
545
             ('E', 1, (1,1,2), False),
 
546
             ('F', 2, (1,2,1), True),
 
547
             ('G', 1, (1,1,1), True),
548
548
             ('H', 0, (1,), True),
549
549
             ],
550
550
            )
577
577
            },
578
578
            'L',
579
579
            [('L', 0, (6,), False),
580
 
             ('K', 1, (1, 3, 2), False),
581
 
             ('I', 1, (1, 3, 1), True),
 
580
             ('K', 1, (1,3,2), False),
 
581
             ('I', 1, (1,3,1), True),
582
582
             ('J', 0, (5,), False),
583
 
             ('H', 1, (1, 2, 2), False),
584
 
             ('F', 1, (1, 2, 1), True),
 
583
             ('H', 1, (1,2,2), False),
 
584
             ('F', 1, (1,2,1), True),
585
585
             ('G', 0, (4,), False),
586
 
             ('E', 1, (1, 1, 2), False),
587
 
             ('C', 1, (1, 1, 1), True),
 
586
             ('E', 1, (1,1,2), False),
 
587
             ('C', 1, (1,1,1), True),
588
588
             ('D', 0, (3,), False),
589
589
             ('B', 0, (2,), False),
590
590
             ('A', 0, (1,),  True),
610
610
            },
611
611
            'N',
612
612
            [('N', 0, (7,), False),
613
 
             ('M', 1, (1, 4, 1), True),
 
613
             ('M', 1, (1,4,1), True),
614
614
             ('L', 0, (6,), False),
615
 
             ('K', 1, (1, 3, 2), False),
616
 
             ('I', 1, (1, 3, 1), True),
 
615
             ('K', 1, (1,3,2), False),
 
616
             ('I', 1, (1,3,1), True),
617
617
             ('J', 0, (5,), False),
618
 
             ('H', 1, (1, 2, 2), False),
619
 
             ('F', 1, (1, 2, 1), True),
 
618
             ('H', 1, (1,2,2), False),
 
619
             ('F', 1, (1,2,1), True),
620
620
             ('G', 0, (4,), False),
621
 
             ('E', 1, (1, 1, 2), False),
622
 
             ('C', 1, (1, 1, 1), True),
 
621
             ('E', 1, (1,1,2), False),
 
622
             ('C', 1, (1,1,1), True),
623
623
             ('D', 0, (3,), False),
624
624
             ('B', 0, (2,), False),
625
625
             ('A', 0, (1,),  True),
665
665
             },
666
666
            'A',
667
667
            [('A', 0, (2,), False),
668
 
             ('B', 1, (1, 3, 2), False),
669
 
             ('C', 2, (1, 4, 1), True),
670
 
             ('D', 1, (1, 3, 1), True),
671
 
             ('E', 1, (1, 1, 2), False),
672
 
             ('F', 2, (1, 2, 1), True),
673
 
             ('G', 1, (1, 1, 1), True),
 
668
             ('B', 1, (1,3,2), False),
 
669
             ('C', 2, (1,4,1), True),
 
670
             ('D', 1, (1,3,1), True),
 
671
             ('E', 1, (1,1,2), False),
 
672
             ('F', 2, (1,2,1), True),
 
673
             ('G', 1, (1,1,1), True),
674
674
             ('H', 0, (1,), True),
675
675
             ],
676
676
            )
683
683
             'C': ['A', 'B']},
684
684
            'C',
685
685
            [('C', 0, (2,), False),
686
 
             ('B', 1, (0, 1, 1), True),
 
686
             ('B', 1, (0,1,1), True),
687
687
             ('A', 0, (1,), True),
688
688
             ],
689
689
            )
721
721
             },
722
722
            'J',
723
723
            [('J', 0, (4,), False),
724
 
             ('I', 1, (1, 3, 2), False),
725
 
             ('H', 1, (1, 3, 1), True),
 
724
             ('I', 1, (1,3,2), False),
 
725
             ('H', 1, (1,3,1), True),
726
726
             ('G', 0, (3,), False),
727
 
             ('F', 1, (1, 2, 2), False),
728
 
             ('E', 1, (1, 2, 1), True),
 
727
             ('F', 1, (1,2,2), False),
 
728
             ('E', 1, (1,2,1), True),
729
729
             ('D', 0, (2,), False),
730
 
             ('C', 1, (1, 1, 2), False),
731
 
             ('B', 1, (1, 1, 1), True),
 
730
             ('C', 1, (1,1,2), False),
 
731
             ('B', 1, (1,1,1), True),
732
732
             ('A', 0, (1,), True),
733
733
             ],
734
734
            )
771
771
            },
772
772
            'R',
773
773
            [('R', 0, (6,), False),
774
 
             ('Q', 1, (0, 4, 5), False),
775
 
             ('P', 2, (0, 6, 1), True),
776
 
             ('O', 1, (0, 4, 4), False),
777
 
             ('N', 1, (0, 4, 3), False),
778
 
             ('M', 2, (0, 5, 1), True),
779
 
             ('L', 1, (0, 4, 2), False),
780
 
             ('K', 1, (0, 4, 1), True),
 
774
             ('Q', 1, (0,4,5), False),
 
775
             ('P', 2, (0,6,1), True),
 
776
             ('O', 1, (0,4,4), False),
 
777
             ('N', 1, (0,4,3), False),
 
778
             ('M', 2, (0,5,1), True),
 
779
             ('L', 1, (0,4,2), False),
 
780
             ('K', 1, (0,4,1), True),
781
781
             ('J', 0, (5,), False),
782
 
             ('I', 1, (0, 3, 1), True),
 
782
             ('I', 1, (0,3,1), True),
783
783
             ('H', 0, (4,), False),
784
 
             ('G', 1, (0, 1, 3), False),
785
 
             ('F', 2, (0, 2, 1), True),
786
 
             ('E', 1, (0, 1, 2), False),
787
 
             ('D', 1, (0, 1, 1), True),
 
784
             ('G', 1, (0,1,3), False),
 
785
             ('F', 2, (0,2,1), True),
 
786
             ('E', 1, (0,1,2), False),
 
787
             ('D', 1, (0,1,1), True),
788
788
             ('C', 0, (3,), False),
789
789
             ('B', 0, (2,), False),
790
790
             ('A', 0, (1,), True),
880
880
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
881
881
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
882
882
                          ],
883
 
                          {('F', 'a'): (), ('F', 'b'): (('F', 'a'),),
 
883
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
884
884
                           ('F', 'c'): (('F', 'b'),),
885
 
                           ('G', 'a'): (), ('G', 'b'): (('G', 'a'),),
 
885
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
886
886
                           ('G', 'c'): (('G', 'b'),),
887
 
                           ('Q', 'a'): (), ('Q', 'b'): (('Q', 'a'),),
 
887
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
888
888
                           ('Q', 'c'): (('Q', 'b'),),
889
889
                          })
890
890
 
900
900
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
901
901
                           'Z':('a',)})
902
902
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
903
 
                          {'a': (), 'b': ('a',), 'c': ('a',), 'd': ('a',),
904
 
                           'Z': ('a',),
905
 
                           'e': ('b', 'c', 'd'),
906
 
                           'f': ('d', 'Z'),
 
903
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
904
                           'Z':('a',),
 
905
                           'e':('b', 'c', 'd'),
 
906
                           'f':('d', 'Z'),
907
907
                           })
908
908
 
909
909
    def test_skip_ghost(self):