~bzr-pqm/bzr/bzr.dev

# Copyright (C) 2007 Canonical Ltd

#

# This program is free software; you can redistribute it and/or modify

# it under the terms of the GNU General Public License as published by

# the Free Software Foundation; either version 2 of the License, or

# (at your option) any later version.

#

# This program is distributed in the hope that it will be useful,

# but WITHOUT ANY WARRANTY; without even the implied warranty of

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

# GNU General Public License for more details.

#

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

# along with this program; if not, write to the Free Software

# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

"""Tests for indices."""

from bzrlib import errors

from bzrlib.index import *

from bzrlib.tests import TestCaseWithMemoryTransport

from bzrlib.transport import get_transport

class TestGraphIndexBuilder(TestCaseWithMemoryTransport):

    def test_build_index_empty(self):

        builder = GraphIndexBuilder()

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=0\n\n",

            contents)

    def test_build_index_empty_two_element_keys(self):

        builder = GraphIndexBuilder(key_elements=2)

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=0\n\n",

            contents)

    def test_build_index_one_reference_list_empty(self):

        builder = GraphIndexBuilder(reference_lists=1)

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=0\n\n",

            contents)

    def test_build_index_two_reference_list_empty(self):

        builder = GraphIndexBuilder(reference_lists=2)

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=0\n\n",

            contents)

    def test_build_index_one_node_no_refs(self):

        builder = GraphIndexBuilder()

        builder.add_node(('akey', ), 'data')

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"

            "akey\x00\x00\x00data\n\n", contents)

    def test_build_index_one_node_no_refs_accepts_empty_reflist(self):

        builder = GraphIndexBuilder()

        builder.add_node(('akey', ), 'data', ())

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"

            "akey\x00\x00\x00data\n\n", contents)

    def test_build_index_one_node_2_element_keys(self):

        # multipart keys are separated by \x00 - because they are fixed length,

        # not variable this does not cause any issues, and seems clearer to the

        # author.

        builder = GraphIndexBuilder(key_elements=2)

        builder.add_node(('akey', 'secondpart'), 'data')

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=1\n"

            "akey\x00secondpart\x00\x00\x00data\n\n", contents)

    def test_add_node_empty_value(self):

        builder = GraphIndexBuilder()

        builder.add_node(('akey', ), '')

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"

            "akey\x00\x00\x00\n\n", contents)

    def test_build_index_nodes_sorted(self):

        # the highest sorted node comes first.

        builder = GraphIndexBuilder()

        # use three to have a good chance of glitching dictionary hash

        # lookups etc. Insert in randomish order that is not correct

        # and not the reverse of the correct order.

        builder.add_node(('2002', ), 'data')

        builder.add_node(('2000', ), 'data')

        builder.add_node(('2001', ), 'data')

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=3\n"

            "2000\x00\x00\x00data\n"

            "2001\x00\x00\x00data\n"

            "2002\x00\x00\x00data\n"

            "\n", contents)

    def test_build_index_2_element_key_nodes_sorted(self):

        # multiple element keys are sorted first-key, second-key.

        builder = GraphIndexBuilder(key_elements=2)

        # use three values of each key element, to have a good chance of

        # glitching dictionary hash lookups etc. Insert in randomish order that

        # is not correct and not the reverse of the correct order.

        builder.add_node(('2002', '2002'), 'data')

        builder.add_node(('2002', '2000'), 'data')

        builder.add_node(('2002', '2001'), 'data')

        builder.add_node(('2000', '2002'), 'data')

        builder.add_node(('2000', '2000'), 'data')

        builder.add_node(('2000', '2001'), 'data')

        builder.add_node(('2001', '2002'), 'data')

        builder.add_node(('2001', '2000'), 'data')

        builder.add_node(('2001', '2001'), 'data')

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=9\n"

            "2000\x002000\x00\x00\x00data\n"

            "2000\x002001\x00\x00\x00data\n"

            "2000\x002002\x00\x00\x00data\n"

            "2001\x002000\x00\x00\x00data\n"

            "2001\x002001\x00\x00\x00data\n"

            "2001\x002002\x00\x00\x00data\n"

            "2002\x002000\x00\x00\x00data\n"

            "2002\x002001\x00\x00\x00data\n"

            "2002\x002002\x00\x00\x00data\n"

            "\n", contents)

    def test_build_index_reference_lists_are_included_one(self):

        builder = GraphIndexBuilder(reference_lists=1)

        builder.add_node(('key', ), 'data', ([], ))

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"

            "key\x00\x00\x00data\n"

            "\n", contents)

    def test_build_index_reference_lists_with_2_element_keys(self):

        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)

        builder.add_node(('key', 'key2'), 'data', ([], ))

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\nlen=1\n"

            "key\x00key2\x00\x00\x00data\n"

            "\n", contents)

    def test_build_index_reference_lists_are_included_two(self):

        builder = GraphIndexBuilder(reference_lists=2)

        builder.add_node(('key', ), 'data', ([], []))

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"

            "key\x00\x00\t\x00data\n"

            "\n", contents)

    def test_node_references_are_byte_offsets(self):

        builder = GraphIndexBuilder(reference_lists=1)

        builder.add_node(('reference', ), 'data', ([], ))

        builder.add_node(('key', ), 'data', ([('reference', )], ))

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=2\n"

            "key\x00\x0072\x00data\n"

            "reference\x00\x00\x00data\n"

            "\n", contents)

    def test_node_references_are_cr_delimited(self):

        builder = GraphIndexBuilder(reference_lists=1)

        builder.add_node(('reference', ), 'data', ([], ))

        builder.add_node(('reference2', ), 'data', ([], ))

        builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=3\n"

            "key\x00\x00077\r094\x00data\n"

            "reference\x00\x00\x00data\n"

            "reference2\x00\x00\x00data\n"

            "\n", contents)

    def test_multiple_reference_lists_are_tab_delimited(self):

        builder = GraphIndexBuilder(reference_lists=2)

        builder.add_node(('keference', ), 'data', ([], []))

        builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=2\n"

            "keference\x00\x00\t\x00data\n"

            "rey\x00\x0059\t59\x00data\n"

            "\n", contents)

    def test_add_node_referencing_missing_key_makes_absent(self):

        builder = GraphIndexBuilder(reference_lists=1)

        builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"

            "aeference2\x00a\x00\x00\n"

            "beference\x00a\x00\x00\n"

            "rey\x00\x00074\r059\x00data\n"

            "\n", contents)

    def test_node_references_three_digits(self):

        # test the node digit expands as needed.

        builder = GraphIndexBuilder(reference_lists=1)

        references = [(str(val), ) for val in reversed(range(9))]

        builder.add_node(('2-key', ), '', (references, ))

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"

            "0\x00a\x00\x00\n"

            "1\x00a\x00\x00\n"

            "2\x00a\x00\x00\n"

            "2-key\x00\x00151\r145\r139\r133\r127\r121\r071\r065\r059\x00\n"

            "3\x00a\x00\x00\n"

            "4\x00a\x00\x00\n"

            "5\x00a\x00\x00\n"

            "6\x00a\x00\x00\n"

            "7\x00a\x00\x00\n"

            "8\x00a\x00\x00\n"

            "\n", contents)

    def test_absent_has_no_reference_overhead(self):

        # the offsets after an absent record should be correct when there are

        # >1 reference lists.

        builder = GraphIndexBuilder(reference_lists=2)

        builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))

        stream = builder.finish()

        contents = stream.read()

        self.assertEqual(

            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"

            "aail\x00a\x00\x00\n"

            "parent\x00\x0059\r84\t\x00\n"

            "zther\x00a\x00\x00\n"

            "\n", contents)

    def test_add_node_bad_key(self):

        builder = GraphIndexBuilder()

        for bad_char in '\t\n\x0b\x0c\r\x00 ':

            self.assertRaises(errors.BadIndexKey, builder.add_node,

                ('a%skey' % bad_char, ), 'data')

        self.assertRaises(errors.BadIndexKey, builder.add_node,

                ('', ), 'data')

        self.assertRaises(errors.BadIndexKey, builder.add_node,

                'not-a-tuple', 'data')

        # not enough length

        self.assertRaises(errors.BadIndexKey, builder.add_node,

                (), 'data')

        # too long

        self.assertRaises(errors.BadIndexKey, builder.add_node,

                ('primary', 'secondary'), 'data')

        # secondary key elements get checked too:

        builder = GraphIndexBuilder(key_elements=2)

        for bad_char in '\t\n\x0b\x0c\r\x00 ':

            self.assertRaises(errors.BadIndexKey, builder.add_node,

                ('prefix', 'a%skey' % bad_char), 'data')

    def test_add_node_bad_data(self):

        builder = GraphIndexBuilder()

        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),

            'data\naa')

        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),

            'data\x00aa')

    def test_add_node_bad_mismatched_ref_lists_length(self):

        builder = GraphIndexBuilder()

        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),

            'data aa', ([], ))

        builder = GraphIndexBuilder(reference_lists=1)

        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),

            'data aa')

        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),

            'data aa', (), )

        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),

            'data aa', ([], []))

        builder = GraphIndexBuilder(reference_lists=2)

        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),

            'data aa')

        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),

            'data aa', ([], ))

        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),

            'data aa', ([], [], []))

    def test_add_node_bad_key_in_reference_lists(self):

        # first list, first key - trivial

        builder = GraphIndexBuilder(reference_lists=1)

        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),

            'data aa', ([('a key', )], ))

        # references keys must be tuples too

        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),

            'data aa', (['not-a-tuple'], ))

        # not enough length

        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),

            'data aa', ([()], ))

        # too long

        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),

            'data aa', ([('primary', 'secondary')], ))

        # need to check more than the first key in the list

        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),

            'data aa', ([('agoodkey', ), ('that is a bad key', )], ))

        # and if there is more than one list it should be getting checked

        # too

        builder = GraphIndexBuilder(reference_lists=2)

        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),

            'data aa', ([], ['a bad key']))

    def test_add_duplicate_key(self):

        builder = GraphIndexBuilder()

        builder.add_node(('key', ), 'data')

        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),

            'data')

    def test_add_duplicate_key_2_elements(self):

        builder = GraphIndexBuilder(key_elements=2)

        builder.add_node(('key', 'key'), 'data')

        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,

            ('key', 'key'), 'data')

    def test_add_key_after_referencing_key(self):

        builder = GraphIndexBuilder(reference_lists=1)

        builder.add_node(('key', ), 'data', ([('reference', )], ))

        builder.add_node(('reference', ), 'data', ([],))

    def test_add_key_after_referencing_key_2_elements(self):

        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)

        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))

        builder.add_node(('reference', 'tokey'), 'data', ([],))

class TestGraphIndex(TestCaseWithMemoryTransport):

    def make_key(self, number):

        return (str(number) + 'X'*100,)

    def make_value(self, number):

            return str(number) + 'Y'*100

    def make_nodes(self, count=64):

        # generate a big enough index that we only read some of it on a typical

        # bisection lookup.

        nodes = []

        for counter in range(count):

            nodes.append((self.make_key(counter), self.make_value(counter), ()))

        return nodes

    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):

        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)

        for key, value, references in nodes:

            builder.add_node(key, value, references)

        stream = builder.finish()

        trans = get_transport('trace+' + self.get_url())

        size = trans.put_file('index', stream)

        return GraphIndex(trans, 'index', size)

    def test_open_bad_index_no_error(self):

        trans = self.get_transport()

        trans.put_bytes('name', "not an index\n")

        index = GraphIndex(trans, 'name', 13)

    def test_open_sets_parsed_map_empty(self):

        index = self.make_index()

        self.assertEqual([], index._parsed_byte_map)

        self.assertEqual([], index._parsed_key_map)

    def test_key_count_buffers(self):

        index = self.make_index(nodes=self.make_nodes(2))

        # reset the transport log

        del index._transport._activity[:]

        self.assertEqual(2, index.key_count())

        # We should have requested reading the header bytes

        self.assertEqual([

            ('readv', 'index', [(0, 200)], True, index._size),

            ],

            index._transport._activity)

        # And that should have been enough to trigger reading the whole index

        # with buffering

        self.assertIsNot(None, index._nodes)

    def test_lookup_key_via_location_buffers(self):

        index = self.make_index()

        # reset the transport log

        del index._transport._activity[:]

        # do a _lookup_keys_via_location call for the middle of the file, which

        # is what bisection uses.

        result = index._lookup_keys_via_location(

            [(index._size // 2, ('missing', ))])

        # this should have asked for a readv request, with adjust_for_latency,

        # and two regions: the header, and half-way into the file.

        self.assertEqual([

            ('readv', 'index', [(30, 30), (0, 200)], True, 60),

            ],

            index._transport._activity)

        # and the result should be that the key cannot be present, because this

        # is a trivial index.

        self.assertEqual([((index._size // 2, ('missing', )), False)],

            result)

        # And this should have caused the file to be fully buffered

        self.assertIsNot(None, index._nodes)

        self.assertEqual([], index._parsed_byte_map)

    def test_first_lookup_key_via_location(self):

        # We need enough data so that the _HEADER_READV doesn't consume the

        # whole file. We always read 800 bytes for every key, and the local

        # transport natural expansion is 4096 bytes. So we have to have >8192

        # bytes or we will trigger "buffer_all".

        # We also want the 'missing' key to fall within the range that *did*

        # read

        nodes = []

        index = self.make_index(nodes=self.make_nodes(64))

        # reset the transport log

        del index._transport._activity[:]

        # do a _lookup_keys_via_location call for the middle of the file, which

        # is what bisection uses.

        start_lookup = index._size // 2

        result = index._lookup_keys_via_location(

            [(start_lookup, ('40missing', ))])

        # this should have asked for a readv request, with adjust_for_latency,

        # and two regions: the header, and half-way into the file.

        self.assertEqual([

            ('readv', 'index',

             [(start_lookup, 800), (0, 200)], True, index._size),

            ],

            index._transport._activity)

        # and the result should be that the key cannot be present, because this

        # is a trivial index.

        self.assertEqual([((start_lookup, ('40missing', )), False)],

            result)

        # And this should not have caused the file to be fully buffered

        self.assertIs(None, index._nodes)

        # And the regions of the file that have been parsed should be in the

        # parsed_byte_map and the parsed_key_map

        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)

        self.assertEqual([(None, self.make_key(26)),

                          (self.make_key(31), self.make_key(48))],

                         index._parsed_key_map)

    def test_parsing_non_adjacent_data_trims(self):

        index = self.make_index(nodes=self.make_nodes(64))

        result = index._lookup_keys_via_location(

            [(index._size // 2, ('40', ))])

        # and the result should be that the key cannot be present, because key is

        # in the middle of the observed data from a 4K read - the smallest transport

        # will do today with this api.

        self.assertEqual([((index._size // 2, ('40', )), False)],

            result)

        # and we should have a parse map that includes the header and the

        # region that was parsed after trimming.

        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)

        self.assertEqual([(None, self.make_key(26)),

                          (self.make_key(31), self.make_key(48))],

            index._parsed_key_map)

    def test_parsing_data_handles_parsed_contained_regions(self):

        # the following patten creates a parsed region that is wholly within a

        # single result from the readv layer:

        # .... single-read (readv-minimum-size) ...

        # which then trims the start and end so the parsed size is < readv

        # miniumum.

        # then a dual lookup (or a reference lookup for that matter) which

        # abuts or overlaps the parsed region on both sides will need to

        # discard the data in the middle, but parse the end as well.

        #

        # we test this by doing a single lookup to seed the data, then

        # a lookup for two keys that are present, and adjacent -

        # we except both to be found, and the parsed byte map to include the

        # locations of both keys.

        index = self.make_index(nodes=self.make_nodes(128))

        result = index._lookup_keys_via_location(

            [(index._size // 2, ('40', ))])

        # and we should have a parse map that includes the header and the

        # region that was parsed after trimming.

        self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)

        self.assertEqual([(None, self.make_key(116)),

                          (self.make_key(35), self.make_key(51))],

            index._parsed_key_map)

        # now ask for two keys, right before and after the parsed region

        result = index._lookup_keys_via_location(

            [(11450, self.make_key(34)), (15707, self.make_key(52))])

        self.assertEqual([

            ((11450, self.make_key(34)),

             (index, self.make_key(34), self.make_value(34))),

            ((15707, self.make_key(52)),

             (index, self.make_key(52), self.make_value(52))),

            ],

            result)

        self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)

    def test_lookup_missing_key_answers_without_io_when_map_permits(self):

        # generate a big enough index that we only read some of it on a typical

        # bisection lookup.

        index = self.make_index(nodes=self.make_nodes(64))

        # lookup the keys in the middle of the file

        result =index._lookup_keys_via_location(

            [(index._size // 2, ('40', ))])

        # check the parse map, this determines the test validity

        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)

        self.assertEqual([(None, self.make_key(26)),

                          (self.make_key(31), self.make_key(48))],

            index._parsed_key_map)

        # reset the transport log

        del index._transport._activity[:]

        # now looking up a key in the portion of the file already parsed should

        # not create a new transport request, and should return False (cannot

        # be in the index) - even when the byte location we ask for is outside

        # the parsed region

        result = index._lookup_keys_via_location(

            [(4000, ('40', ))])

        self.assertEqual([((4000, ('40', )), False)],

            result)

        self.assertEqual([], index._transport._activity)

    def test_lookup_present_key_answers_without_io_when_map_permits(self):

        # generate a big enough index that we only read some of it on a typical

        # bisection lookup.

        index = self.make_index(nodes=self.make_nodes(64))

        # lookup the keys in the middle of the file

        result =index._lookup_keys_via_location(

            [(index._size // 2, ('40', ))])

        # check the parse map, this determines the test validity

        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)

        self.assertEqual([(None, self.make_key(26)),

                          (self.make_key(31), self.make_key(48))],

            index._parsed_key_map)

        # reset the transport log

        del index._transport._activity[:]

        # now looking up a key in the portion of the file already parsed should

        # not create a new transport request, and should return False (cannot

        # be in the index) - even when the byte location we ask for is outside

        # the parsed region

        # 

        result = index._lookup_keys_via_location([(4000, self.make_key(40))])

        self.assertEqual(

            [((4000, self.make_key(40)),

              (index, self.make_key(40), self.make_value(40)))],

            result)

        self.assertEqual([], index._transport._activity)

    def test_lookup_key_below_probed_area(self):

        # generate a big enough index that we only read some of it on a typical

        # bisection lookup.

        index = self.make_index(nodes=self.make_nodes(64))

        # ask for the key in the middle, but a key that is located in the

        # unparsed region before the middle.

        result =index._lookup_keys_via_location(

            [(index._size // 2, ('30', ))])

        # check the parse map, this determines the test validity

        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)

        self.assertEqual([(None, self.make_key(26)),

                          (self.make_key(31), self.make_key(48))],

            index._parsed_key_map)