← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-08-14 19:14:23 UTC
  • mfrom: (4593.4.17 1.18-faster-iter-ancestry)
  • Revision ID: pqm@pqm.ubuntu.com-20090814191423-zs4ej0tde7yhamha
(jam) Introduce CombinedGraphIndex.find_ancestry and
        BTreeGraphIndex._find_ancestors()

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
1
 
# Copyright (C) 2008 Canonical Ltd
 
1
# Copyright (C) 2008, 2009 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
23
23
from bzrlib import (
24
24
    btree_index,
25
25
    errors,
 
26
    osutils,
26
27
    tests,
27
28
    )
28
29
from bzrlib.tests import (
980
981
            ])
981
982
        self.assertEqual(set([]), index.external_references(0))
982
983
 
 
984
    def test__find_ancestors_one_page(self):
 
985
        key1 = ('key-1',)
 
986
        key2 = ('key-2',)
 
987
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
988
            (key1, 'value', ([key2],)),
 
989
            (key2, 'value', ([],)),
 
990
            ])
 
991
        parent_map = {}
 
992
        missing_keys = set()
 
993
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
 
994
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
 
995
        self.assertEqual(set(), missing_keys)
 
996
        self.assertEqual(set(), search_keys)
 
997
 
 
998
    def test__find_ancestors_one_page_w_missing(self):
 
999
        key1 = ('key-1',)
 
1000
        key2 = ('key-2',)
 
1001
        key3 = ('key-3',)
 
1002
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1003
            (key1, 'value', ([key2],)),
 
1004
            (key2, 'value', ([],)),
 
1005
            ])
 
1006
        parent_map = {}
 
1007
        missing_keys = set()
 
1008
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
 
1009
                                            missing_keys)
 
1010
        self.assertEqual({key2: ()}, parent_map)
 
1011
        # we know that key3 is missing because we read the page that it would
 
1012
        # otherwise be on
 
1013
        self.assertEqual(set([key3]), missing_keys)
 
1014
        self.assertEqual(set(), search_keys)
 
1015
 
 
1016
    def test__find_ancestors_one_parent_missing(self):
 
1017
        key1 = ('key-1',)
 
1018
        key2 = ('key-2',)
 
1019
        key3 = ('key-3',)
 
1020
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1021
            (key1, 'value', ([key2],)),
 
1022
            (key2, 'value', ([key3],)),
 
1023
            ])
 
1024
        parent_map = {}
 
1025
        missing_keys = set()
 
1026
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1027
                                            missing_keys)
 
1028
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1029
        self.assertEqual(set(), missing_keys)
 
1030
        # all we know is that key3 wasn't present on the page we were reading
 
1031
        # but if you look, the last key is key2 which comes before key3, so we
 
1032
        # don't know whether key3 would land on this page or not.
 
1033
        self.assertEqual(set([key3]), search_keys)
 
1034
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
 
1035
                                            missing_keys)
 
1036
        # passing it back in, we are sure it is 'missing'
 
1037
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1038
        self.assertEqual(set([key3]), missing_keys)
 
1039
        self.assertEqual(set([]), search_keys)
 
1040
 
 
1041
    def test__find_ancestors_dont_search_known(self):
 
1042
        key1 = ('key-1',)
 
1043
        key2 = ('key-2',)
 
1044
        key3 = ('key-3',)
 
1045
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1046
            (key1, 'value', ([key2],)),
 
1047
            (key2, 'value', ([key3],)),
 
1048
            (key3, 'value', ([],)),
 
1049
            ])
 
1050
        # We already know about key2, so we won't try to search for key3
 
1051
        parent_map = {key2: (key3,)}
 
1052
        missing_keys = set()
 
1053
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1054
                                            missing_keys)
 
1055
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1056
        self.assertEqual(set(), missing_keys)
 
1057
        self.assertEqual(set(), search_keys)
 
1058
 
 
1059
    def test__find_ancestors_multiple_pages(self):
 
1060
        # We need to use enough keys that we actually cause a split
 
1061
        start_time = 1249671539
 
1062
        email = "joebob@example.com"
 
1063
        nodes = []
 
1064
        ref_lists = ((),)
 
1065
        rev_keys = []
 
1066
        for i in xrange(400):
 
1067
            rev_id = '%s-%s-%s' % (email,
 
1068
                                   osutils.compact_date(start_time + i),
 
1069
                                   osutils.rand_chars(16))
 
1070
            rev_key = (rev_id,)
 
1071
            nodes.append((rev_key, 'value', ref_lists))
 
1072
            # We have a ref 'list' of length 1, with a list of parents, with 1
 
1073
            # parent which is a key
 
1074
            ref_lists = ((rev_key,),)
 
1075
            rev_keys.append(rev_key)
 
1076
        index = self.make_index(ref_lists=1, key_elements=1, nodes=nodes)
 
1077
        self.assertEqual(400, index.key_count())
 
1078
        self.assertEqual(3, len(index._row_offsets))
 
1079
        nodes = dict(index._read_nodes([1, 2]))
 
1080
        l1 = nodes[1]
 
1081
        l2 = nodes[2]
 
1082
        min_l2_key = l2.min_key
 
1083
        max_l1_key = l1.max_key
 
1084
        self.assertTrue(max_l1_key < min_l2_key)
 
1085
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
 
1086
        self.assertEqual((l1.max_key,), parents_min_l2_key)
 
1087
        # Now, whatever key we select that would fall on the second page,
 
1088
        # should give us all the parents until the page break
 
1089
        key_idx = rev_keys.index(min_l2_key)
 
1090
        next_key = rev_keys[key_idx+1]
 
1091
        # So now when we get the parent map, we should get the key we are
 
1092
        # looking for, min_l2_key, and then a reference to go look for the
 
1093
        # parent of that key
 
1094
        parent_map = {}
 
1095
        missing_keys = set()
 
1096
        search_keys = index._find_ancestors([next_key], 0, parent_map,
 
1097
                                            missing_keys)
 
1098
        self.assertEqual([min_l2_key, next_key], sorted(parent_map))
 
1099
        self.assertEqual(set(), missing_keys)
 
1100
        self.assertEqual(set([max_l1_key]), search_keys)
 
1101
        parent_map = {}
 
1102
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
 
1103
                                            missing_keys)
 
1104
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
 
1105
        self.assertEqual(set(), missing_keys)
 
1106
        self.assertEqual(set(), search_keys)
 
1107
 
 
1108
    def test__find_ancestors_empty_index(self):
 
1109
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[])
 
1110
        parent_map = {}
 
1111
        missing_keys = set()
 
1112
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
 
1113
                                            missing_keys)
 
1114
        self.assertEqual(set(), search_keys)
 
1115
        self.assertEqual({}, parent_map)
 
1116
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
 
1117
 
983
1118
 
984
1119
class TestBTreeNodes(BTreeTestCase):
985
1120