~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

• browse files at revision 4031.3.2
• compare with another revision
• compare with revision 4031.3.2
• download diff
• download tarball
• view history from revision 4031.3.2

Show diffs side-by-side

added

removed

bzrlib/tests/test_graph.py

12

12

#

13

13

# You should have received a copy of the GNU General Public License

14

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

 

15

# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

16

16

 

17

17

from bzrlib import (

18

18

    errors,

237

237

                    'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],

238

238

                    'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],

239

239

                    'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],

240

 

                    't':['i', 's'], 'u':['s', 'j'], 

 

240

                    't':['i', 's'], 'u':['s', 'j'],

241

241

                    }

242

242

 

243

243

# Graph where different walkers will race to find the common and uncommon

711

711

 

712

712

    def test_is_ancestor_boundary(self):

713

713

        """Ensure that we avoid searching the whole graph.

714

 

        

 

714

 

715

715

        This requires searching through b as a common ancestor, so we

716

716

        can identify that e is common.

717

717

        """

737

737

        # 'a' is not in the ancestry of 'c', and 'g' is a ghost

738

738

        expected['g'] = None

739

739

        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))

740

 

        expected.pop('a') 

 

740

        expected.pop('a')

741

741

        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))

742

742

 

743

743

    def test_filter_candidate_lca(self):

845

845

 

846

846

    def _run_heads_break_deeper(self, graph_dict, search):

847

847

        """Run heads on a graph-as-a-dict.

848

 

        

 

848

 

849

849

        If the search asks for the parents of 'deeper' the test will fail.

850

850

        """

851

851

        class stub(object):

992

992

        :param next: A callable to advance the search.

993

993

        """

994

994

        for seen, recipe, included_keys, starts, stops in instructions:

 

995

            # Adjust for recipe contract changes that don't vary for all the

 

996

            # current tests.

 

997

            recipe = ('search',) + recipe

995

998

            next()

996

999

            if starts is not None:

997

1000

                search.start_searching(starts)

1011

1014

        search = graph._make_breadth_first_searcher(['head'])

1012

1015

        # At the start, nothing has been seen, to its all excluded:

1013

1016

        result = search.get_result()

1014

 

        self.assertEqual((set(['head']), set(['head']), 0),

 

1017

        self.assertEqual(('search', set(['head']), set(['head']), 0),

1015

1018

            result.get_recipe())

1016

1019

        self.assertEqual(set(), result.get_keys())

1017

1020

        self.assertEqual(set(), search.seen)

1043

1046

        search.start_searching(['head'])

1044

1047

        # head has been seen:

1045

1048

        result = search.get_result()

1046

 

        self.assertEqual((set(['head']), set(['child']), 1),

 

1049

        self.assertEqual(('search', set(['head']), set(['child']), 1),

1047

1050

            result.get_recipe())

1048

1051

        self.assertEqual(set(['head']), result.get_keys())

1049

1052

        self.assertEqual(set(['head']), search.seen)

1080

1083

        search = graph._make_breadth_first_searcher(['head'])

1081

1084

        expected = [

1082

1085

            # NULL_REVISION and ghost1 have not been returned

1083

 

            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),

 

1086

            (set(['head']),

 

1087

             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),

1084

1088

             ['head'], None, [NULL_REVISION, 'ghost1']),

1085

1089

            # ghost1 has been returned, NULL_REVISION is to be returned in the

1086

1090

            # next iteration.

1202

1206

        self.assertRaises(StopIteration, search.next)

1203

1207

        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)

1204

1208

        result = search.get_result()

1205

 

        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),

 

1209

        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),

1206

1210

            result.get_recipe())

1207

1211

        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())

1208

1212

        # using next_with_ghosts:

1211

1215

        self.assertRaises(StopIteration, search.next)

1212

1216

        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)

1213

1217

        result = search.get_result()

1214

 

        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),

 

1218

        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),

1215

1219

            result.get_recipe())

1216

1220

        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())

1217

1221

 

1381

1385

 

1382

1386

 

1383

1387

class TestCachingParentsProvider(tests.TestCase):

 

1388

    """These tests run with:

 

1389

 

 

1390

    self.inst_pp, a recording parents provider with a graph of a->b, and b is a

 

1391

    ghost.

 

1392

    self.caching_pp, a CachingParentsProvider layered on inst_pp.

 

1393

    """

1384

1394

 

1385

1395

    def setUp(self):

1386

1396

        super(TestCachingParentsProvider, self).setUp()

1405

1415

        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))

1406

1416

        # No new calls

1407

1417

        self.assertEqual(['b'], self.inst_pp.calls)

1408

 

        self.assertEqual({'b':None}, self.caching_pp._cache)

1409

1418

 

1410

1419

    def test_get_parent_map_mixed(self):

1411

1420

        """Anything that can be returned from cache, should be"""

1423

1432

        # only present 1 time.

1424

1433

        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))

1425

1434

 

 

1435

    def test_note_missing_key(self):

 

1436

        """After noting that a key is missing it is cached."""

 

1437

        self.caching_pp.note_missing_key('b')

 

1438

        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))

 

1439

        self.assertEqual([], self.inst_pp.calls)

 

1440

        self.assertEqual(set(['b']), self.caching_pp.missing_keys)

 

1441

 

1426

1442

 

1427

1443

class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):

1428

1444

    """Test the behaviour when parents are provided that were not requested."""

1524

1540

        # 2 and 3 cannot be removed because 1 has 2 parents

1525

1541

        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}

1526

1542

        self.assertCollapsed(d, d)

 

1543

 

 

1544

 

 

1545

class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):

 

1546

    """Tests for bzrlib.graph.PendingAncestryResult."""

 

1547

 

 

1548

    def test_get_keys(self):

 

1549

        builder = self.make_branch_builder('b')

 

1550

        builder.start_series()

 

1551

        builder.build_snapshot('rev-1', None, [

 

1552

            ('add', ('', 'root-id', 'directory', ''))])

 

1553

        builder.build_snapshot('rev-2', ['rev-1'], [])

 

1554

        builder.finish_series()

 

1555

        repo = builder.get_branch().repository

 

1556

        repo.lock_read()

 

1557

        self.addCleanup(repo.unlock)

 

1558

        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)

 

1559

        self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))

 

1560

 

 

1561

    def test_get_keys_excludes_null(self):

 

1562

        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION

 

1563

        # somewhere other than the last element, which can happen in real

 

1564

        # ancestries.

 

1565

        class StubGraph(object):

 

1566

            def iter_ancestry(self, keys):

 

1567

                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]

 

1568

        result = _mod_graph.PendingAncestryResult(['rev-3'], None)

 

1569

        result_keys = result._get_keys(StubGraph())

 

1570

        # Only the non-null keys from the ancestry appear.

 

1571

        self.assertEqual(set(['foo']), set(result_keys))

 

1572

 

 

1573

 

 

1574

class TestPendingAncestryResultRefine(TestGraphBase):

 

1575

 

 

1576

    def test_refine(self):

 

1577

        # Used when pulling from a stacked repository, so test some revisions

 

1578

        # being satisfied from the stacking branch.

 

1579

        g = self.make_graph(

 

1580

            {"tip":["mid"], "mid":["base"], "tag":["base"],

 

1581

             "base":[NULL_REVISION], NULL_REVISION:[]})

 

1582

        result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)

 

1583

        result = result.refine(set(['tip']), set(['mid']))

 

1584

        self.assertEqual(set(['mid', 'tag']), result.heads)

 

1585

        result = result.refine(set(['mid', 'tag', 'base']),

 

1586

            set([NULL_REVISION]))

 

1587

        self.assertEqual(set([NULL_REVISION]), result.heads)

 

1588

        self.assertTrue(result.is_empty())

 

1589

 

 

1590

 

 

1591

class TestSearchResultRefine(TestGraphBase):

 

1592

 

 

1593

    def test_refine(self):

 

1594

        # Used when pulling from a stacked repository, so test some revisions

 

1595

        # being satisfied from the stacking branch.

 

1596

        g = self.make_graph(

 

1597

            {"tip":["mid"], "mid":["base"], "tag":["base"],

 

1598

             "base":[NULL_REVISION], NULL_REVISION:[]})

 

1599

        result = _mod_graph.SearchResult(set(['tip', 'tag']),

 

1600

            set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))

 

1601

        result = result.refine(set(['tip']), set(['mid']))

 

1602

        recipe = result.get_recipe()

 

1603

        # We should be starting from tag (original head) and mid (seen ref)

 

1604

        self.assertEqual(set(['mid', 'tag']), recipe[1])

 

1605

        # We should be stopping at NULL (original stop) and tip (seen head)

 

1606

        self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])

 

1607

        self.assertEqual(3, recipe[3])

 

1608

        result = result.refine(set(['mid', 'tag', 'base']),

 

1609

            set([NULL_REVISION]))

 

1610

        recipe = result.get_recipe()

 

1611

        # We should be starting from nothing (NULL was known as a cut point)

 

1612

        self.assertEqual(set([]), recipe[1])

 

1613

        # We should be stopping at NULL (original stop) and tip (seen head) and

 

1614

        # tag (seen head) and mid(seen mid-point head). We could come back and

 

1615

        # define this as not including mid, for minimal results, but it is

 

1616

        # still 'correct' to include mid, and simpler/easier.

 

1617

        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])

 

1618

        self.assertEqual(0, recipe[3])

 

1619

        self.assertTrue(result.is_empty())

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1