← 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-10-23 08:21:11 UTC
  • mfrom: (2921.3.5 graph)
  • Revision ID: pqm@pqm.ubuntu.com-20071023082111-h6u34i4gvlb2nwch
(robertc) Prevent heads() calls from accessing all history unnecessarily. (Robert Collins)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
453
453
                         graph.heads(['rev2a', 'rev3b']))
454
454
        self.assertEqual(set(['rev2c', 'rev3a']),
455
455
                         graph.heads(['rev2c', 'rev3a']))
 
456
 
 
457
    def _run_heads_break_deeper(self, graph_dict, search):
 
458
        """Run heads on a graph-as-a-dict.
 
459
        
 
460
        If the search asks for the parents of 'deeper' the test will fail.
 
461
        """
 
462
        class stub(object):
 
463
            pass
 
464
        def get_parents(keys):
 
465
            result = []
 
466
            for key in keys:
 
467
                if key == 'deeper':
 
468
                    self.fail('key deeper was accessed')
 
469
                result.append(graph_dict[key])
 
470
            return result
 
471
        an_obj = stub()
 
472
        an_obj.get_parents = get_parents
 
473
        graph = _mod_graph.Graph(an_obj)
 
474
        return graph.heads(search)
 
475
 
 
476
    def test_heads_limits_search(self):
 
477
        # test that a heads query does not search all of history
 
478
        graph_dict = {
 
479
            'left':['common'],
 
480
            'right':['common'],
 
481
            'common':['deeper'],
 
482
        }
 
483
        self.assertEqual(set(['left', 'right']),
 
484
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
 
485
 
 
486
    def test_heads_limits_search_assymetric(self):
 
487
        # test that a heads query does not search all of history
 
488
        graph_dict = {
 
489
            'left':['midleft'],
 
490
            'midleft':['common'],
 
491
            'right':['common'],
 
492
            'common':['aftercommon'],
 
493
            'aftercommon':['deeper'],
 
494
        }
 
495
        self.assertEqual(set(['left', 'right']),
 
496
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
 
497
 
 
498
    def test_heads_limits_search_common_search_must_continue(self):
 
499
        # test that common nodes are still queried, preventing
 
500
        # all-the-way-to-origin behaviour in the following graph:
 
501
        graph_dict = {
 
502
            'h1':['shortcut', 'common1'],
 
503
            'h2':['common1'],
 
504
            'shortcut':['common2'],
 
505
            'common1':['common2'],
 
506
            'common2':['deeper'],
 
507
        }
 
508
        self.assertEqual(set(['h1', 'h2']),
 
509
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))