/brz/remove-bazaar

# Copyright (C) 2008 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 maps built on a CHK versionedfiles facility."""

from itertools import izip

from bzrlib import chk_map

from bzrlib.chk_map import (

    CHKMap,

    InternalNode,

    LeafNode,

    _deserialise,

    )

from bzrlib.tests import TestCaseWithTransport

class TestCaseWithStore(TestCaseWithTransport):

    def get_chk_bytes(self):

        # The eassiest way to get a CHK store is a development3 repository and

        # then work with the chk_bytes attribute directly.

        repo = self.make_repository(".", format="development3")

        repo.lock_write()

        self.addCleanup(repo.unlock)

        repo.start_write_group()

        self.addCleanup(repo.abort_write_group)

        return repo.chk_bytes

    def _get_map(self, a_dict, maximum_size=0, chk_bytes=None, key_width=1):

        if chk_bytes is None:

            chk_bytes = self.get_chk_bytes()

        root_key = CHKMap.from_dict(chk_bytes, a_dict,

            maximum_size=maximum_size, key_width=key_width)

        chkmap = CHKMap(chk_bytes, root_key)

        return chkmap

    def read_bytes(self, chk_bytes, key):

        stream = chk_bytes.get_record_stream([key], 'unordered', True)

        return stream.next().get_bytes_as("fulltext")

    def to_dict(self, node, *args):

        return dict(node.iteritems(*args))

class TestMap(TestCaseWithStore):

    def assertHasABMap(self, chk_bytes):

        root_key = ('sha1:f14dd34def95036bc06bb5c0ed95437d7383a04a',)

        self.assertEqual(

            'chkleaf:\n0\n1\n1\na\x00b\n',

            self.read_bytes(chk_bytes, root_key))

        return root_key

    def assertHasEmptyMap(self, chk_bytes):

        root_key = ('sha1:4e6482a3a5cb2d61699971ac77befe11a0ec5779',)

        self.assertEqual("chkleaf:\n0\n1\n0\n", self.read_bytes(chk_bytes, root_key))

        return root_key

    def test_from_dict_empty(self):

        chk_bytes = self.get_chk_bytes()

        root_key = CHKMap.from_dict(chk_bytes, {})

        # Check the data was saved and inserted correctly.

        expected_root_key = self.assertHasEmptyMap(chk_bytes)

        self.assertEqual(expected_root_key, root_key)

    def test_from_dict_ab(self):

        chk_bytes = self.get_chk_bytes()

        root_key = CHKMap.from_dict(chk_bytes, {"a":"b"})

        # Check the data was saved and inserted correctly.

        expected_root_key = self.assertHasABMap(chk_bytes)

        self.assertEqual(expected_root_key, root_key)

    def test_apply_empty_ab(self):

        # applying a delta (None, "a", "b") to an empty chkmap generates the

        # same map as from_dict_ab.

        chk_bytes = self.get_chk_bytes()

        root_key = CHKMap.from_dict(chk_bytes, {})

        chkmap = CHKMap(chk_bytes, root_key)

        new_root = chkmap.apply_delta([(None, "a", "b")])

        # Check the data was saved and inserted correctly.

        expected_root_key = self.assertHasABMap(chk_bytes)

        self.assertEqual(expected_root_key, new_root)

        # The update should have left us with an in memory root node, with an

        # updated key.

        self.assertEqual(new_root, chkmap._root_node._key)

    def test_apply_ab_empty(self):

        # applying a delta ("a", None, None) to a map with 'a' in it generates

        # an empty map.

        chk_bytes = self.get_chk_bytes()

        root_key = CHKMap.from_dict(chk_bytes, {("a",):"b"})

        chkmap = CHKMap(chk_bytes, root_key)

        new_root = chkmap.apply_delta([(("a",), None, None)])

        # Check the data was saved and inserted correctly.

        expected_root_key = self.assertHasEmptyMap(chk_bytes)

        self.assertEqual(expected_root_key, new_root)

        # The update should have left us with an in memory root node, with an

        # updated key.

        self.assertEqual(new_root, chkmap._root_node._key)

    def test_apply_delta_is_deterministic(self):

        chk_bytes = self.get_chk_bytes()

        chkmap1 = CHKMap(chk_bytes, None)

        chkmap1._root_node.set_maximum_size(10)

        chkmap1.apply_delta([(None, ('aaa',), 'common'),

                             (None, ('bba',), 'target2'),

                             (None, ('bbb',), 'common')])

        root_key1 = chkmap1._save()

        chkmap2 = CHKMap(chk_bytes, None)

        chkmap2._root_node.set_maximum_size(10)

        chkmap2.apply_delta([(None, ('bbb',), 'common'),

                             (None, ('bba',), 'target2'),

                             (None, ('aaa',), 'common')])

        root_key2 = chkmap2._save()

        self.assertEqualDiff(chkmap1._dump_tree(), chkmap2._dump_tree())

        self.assertEqual(root_key1, root_key2)

    def test_stable_splitting(self):

        store = self.get_chk_bytes()

        chkmap = CHKMap(store, None)

        # Should fit 2 keys per LeafNode

        chkmap._root_node.set_maximum_size(30)

        chkmap.map(('aaa',), 'v')

        self.assertEqualDiff("'' LeafNode None\n"

                             "      ('aaa',) 'v'",

                             chkmap._dump_tree())

        chkmap.map(('aab',), 'v')

        self.assertEqualDiff("'' LeafNode None\n"

                             "      ('aaa',) 'v'\n"

                             "      ('aab',) 'v'",

                             chkmap._dump_tree())

        # Creates a new internal node, and splits the others into leaves

        chkmap.map(('aac',), 'v')

        self.assertEqualDiff("'' InternalNode None\n"

                             "  'aaa' LeafNode None\n"

                             "      ('aaa',) 'v'\n"

                             "  'aab' LeafNode None\n"

                             "      ('aab',) 'v'\n"

                             "  'aac' LeafNode None\n"

                             "      ('aac',) 'v'",

                             chkmap._dump_tree())

        # Splits again, because it can't fit in the current structure

        chkmap.map(('bbb',), 'v')

        self.assertEqualDiff("'' InternalNode None\n"

                             "  'a' InternalNode None\n"

                             "    'aaa' LeafNode None\n"

                             "      ('aaa',) 'v'\n"

                             "    'aab' LeafNode None\n"

                             "      ('aab',) 'v'\n"

                             "    'aac' LeafNode None\n"

                             "      ('aac',) 'v'\n"

                             "  'b' LeafNode None\n"

                             "      ('bbb',) 'v'",

                             chkmap._dump_tree())

    def test_deep_splitting(self):

        store = self.get_chk_bytes()

        chkmap = CHKMap(store, None)

        # Should fit 2 keys per LeafNode

        chkmap._root_node.set_maximum_size(40)

        chkmap.map(('aaaaaaaa',), 'v')

        chkmap.map(('aaaaabaa',), 'v')

        self.assertEqualDiff("'' LeafNode None\n"

                             "      ('aaaaaaaa',) 'v'\n"

                             "      ('aaaaabaa',) 'v'",

                             chkmap._dump_tree())

        chkmap.map(('aaabaaaa',), 'v')

        chkmap.map(('aaababaa',), 'v')

        self.assertEqualDiff("'' InternalNode None\n"

                             "  'aaaa' LeafNode None\n"

                             "      ('aaaaaaaa',) 'v'\n"

                             "      ('aaaaabaa',) 'v'\n"

                             "  'aaab' LeafNode None\n"

                             "      ('aaabaaaa',) 'v'\n"

                             "      ('aaababaa',) 'v'",

                             chkmap._dump_tree())

        chkmap.map(('aaabacaa',), 'v')

        chkmap.map(('aaabadaa',), 'v')

        self.assertEqualDiff("'' InternalNode None\n"

                             "  'aaaa' LeafNode None\n"

                             "      ('aaaaaaaa',) 'v'\n"

                             "      ('aaaaabaa',) 'v'\n"

                             "  'aaab' InternalNode None\n"

                             "    'aaabaa' LeafNode None\n"

                             "      ('aaabaaaa',) 'v'\n"

                             "    'aaabab' LeafNode None\n"

                             "      ('aaababaa',) 'v'\n"

                             "    'aaabac' LeafNode None\n"

                             "      ('aaabacaa',) 'v'\n"

                             "    'aaabad' LeafNode None\n"

                             "      ('aaabadaa',) 'v'",

                             chkmap._dump_tree())

        chkmap.map(('aaababba',), 'v')

        chkmap.map(('aaababca',), 'v')

        self.assertEqualDiff("'' InternalNode None\n"

                             "  'aaaa' LeafNode None\n"

                             "      ('aaaaaaaa',) 'v'\n"

                             "      ('aaaaabaa',) 'v'\n"

                             "  'aaab' InternalNode None\n"

                             "    'aaabaa' LeafNode None\n"

                             "      ('aaabaaaa',) 'v'\n"

                             "    'aaabab' InternalNode None\n"

                             "      'aaababa' LeafNode None\n"

                             "      ('aaababaa',) 'v'\n"

                             "      'aaababb' LeafNode None\n"

                             "      ('aaababba',) 'v'\n"

                             "      'aaababc' LeafNode None\n"

                             "      ('aaababca',) 'v'\n"

                             "    'aaabac' LeafNode None\n"

                             "      ('aaabacaa',) 'v'\n"

                             "    'aaabad' LeafNode None\n"

                             "      ('aaabadaa',) 'v'",

                             chkmap._dump_tree())

        # Now we add a node that should fit around an existing InternalNode,

        # but has a slightly different key prefix, which causes a new

        # InternalNode split

        chkmap.map(('aaabDaaa',), 'v')

        self.assertEqualDiff("'' InternalNode None\n"

                             "  'aaaa' LeafNode None\n"

                             "      ('aaaaaaaa',) 'v'\n"

                             "      ('aaaaabaa',) 'v'\n"

                             "  'aaab' InternalNode None\n"

                             "    'aaabD' LeafNode None\n"

                             "      ('aaabDaaa',) 'v'\n"

                             "    'aaaba' InternalNode None\n"

                             "      'aaabaa' LeafNode None\n"

                             "      ('aaabaaaa',) 'v'\n"

                             "      'aaabab' InternalNode None\n"

                             "        'aaababa' LeafNode None\n"

                             "      ('aaababaa',) 'v'\n"

                             "        'aaababb' LeafNode None\n"

                             "      ('aaababba',) 'v'\n"

                             "        'aaababc' LeafNode None\n"

                             "      ('aaababca',) 'v'\n"

                             "      'aaabac' LeafNode None\n"

                             "      ('aaabacaa',) 'v'\n"

                             "      'aaabad' LeafNode None\n"

                             "      ('aaabadaa',) 'v'",

                             chkmap._dump_tree())

    def test_iter_changes_empty_ab(self):

        # Asking for changes between an empty dict to a dict with keys returns

        # all the keys.

        basis = self._get_map({}, maximum_size=10)

        target = self._get_map(

            {('a',): 'content here', ('b',): 'more content'},

            chk_bytes=basis._store, maximum_size=10)

        self.assertEqual([(('a',), None, 'content here'),

            (('b',), None, 'more content')],

            sorted(list(target.iter_changes(basis))))

    def test_iter_changes_ab_empty(self):

        # Asking for changes between a dict with keys to an empty dict returns

        # all the keys.

        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},

            maximum_size=10)

        target = self._get_map({}, chk_bytes=basis._store, maximum_size=10)

        self.assertEqual([(('a',), 'content here', None),

            (('b',), 'more content', None)],

            sorted(list(target.iter_changes(basis))))

    def test_iter_changes_empty_empty_is_empty(self):

        basis = self._get_map({}, maximum_size=10)

        target = self._get_map({}, chk_bytes=basis._store, maximum_size=10)

        self.assertEqual([], sorted(list(target.iter_changes(basis))))

    def test_iter_changes_ab_ab_is_empty(self):

        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},

            maximum_size=10)

        target = self._get_map(

            {('a',): 'content here', ('b',): 'more content'},

            chk_bytes=basis._store, maximum_size=10)

        self.assertEqual([], sorted(list(target.iter_changes(basis))))

    def test_iter_changes_ab_ab_nodes_not_loaded(self):

        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},

            maximum_size=10)

        target = self._get_map(

            {('a',): 'content here', ('b',): 'more content'},

            chk_bytes=basis._store, maximum_size=10)

        list(target.iter_changes(basis))

        self.assertIsInstance(target._root_node, tuple)

        self.assertIsInstance(basis._root_node, tuple)

    def test_iter_changes_ab_ab_changed_values_shown(self):

        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},

            maximum_size=10)

        target = self._get_map(

            {('a',): 'content here', ('b',): 'different content'},

            chk_bytes=basis._store, maximum_size=10)

        result = sorted(list(target.iter_changes(basis)))

        self.assertEqual([(('b',), 'more content', 'different content')],

            result)

    def test_iter_changes_mixed_node_length(self):

        # When one side has different node lengths than the other, common

        # but different keys still need to be show, and new-and-old included

        # appropriately.

        # aaa - common unaltered

        # aab - common altered

        # b - basis only

        # at - target only

        # we expect: 

        # aaa to be not loaded (later test)

        # aab, b, at to be returned.

        # basis splits at byte 0,1,2, aaa is commonb is basis only

        basis_dict = {('aaa',): 'foo bar',

            ('aab',): 'common altered a', ('b',): 'foo bar b'}

        # target splits at byte 1,2, at is target only

        target_dict = {('aaa',): 'foo bar',

            ('aab',): 'common altered b', ('at',): 'foo bar t'}

        changes = [

            (('aab',), 'common altered a', 'common altered b'),

            (('at',), None, 'foo bar t'),

            (('b',), 'foo bar b', None),

            ]

        basis = self._get_map(basis_dict, maximum_size=10)

        target = self._get_map(target_dict, maximum_size=10,

            chk_bytes=basis._store)

        self.assertEqual(changes, sorted(list(target.iter_changes(basis))))

    def test_iter_changes_common_pages_not_loaded(self):

        # aaa - common unaltered

        # aab - common altered

        # b - basis only

        # at - target only

        # we expect: 

        # aaa to be not loaded

        # aaa not to be in result.

        basis_dict = {('aaa',): 'foo bar',

            ('aab',): 'common altered a', ('b',): 'foo bar b'}

        # target splits at byte 1, at is target only

        target_dict = {('aaa',): 'foo bar',

            ('aab',): 'common altered b', ('at',): 'foo bar t'}

        basis = self._get_map(basis_dict, maximum_size=10)

        target = self._get_map(target_dict, maximum_size=10,

            chk_bytes=basis._store)

        basis_get = basis._store.get_record_stream

        def get_record_stream(keys, order, fulltext):

            if ('sha1:1adf7c0d1b9140ab5f33bb64c6275fa78b1580b7',) in keys:

                self.fail("'aaa' pointer was followed %r" % keys)

            return basis_get(keys, order, fulltext)

        basis._store.get_record_stream = get_record_stream

        result = sorted(list(target.iter_changes(basis)))

        for change in result:

            if change[0] == ('aaa',):

                self.fail("Found unexpected change: %s" % change)

    def test_iter_changes_unchanged_keys_in_multi_key_leafs_ignored(self):

        # Within a leaf there are no hash's to exclude keys, make sure multi

        # value leaf nodes are handled well.

        basis_dict = {('aaa',): 'foo bar',

            ('aab',): 'common altered a', ('b',): 'foo bar b'}

        target_dict = {('aaa',): 'foo bar',

            ('aab',): 'common altered b', ('at',): 'foo bar t'}

        changes = [

            (('aab',), 'common altered a', 'common altered b'),

            (('at',), None, 'foo bar t'),

            (('b',), 'foo bar b', None),

            ]

        basis = self._get_map(basis_dict)

        target = self._get_map(target_dict, chk_bytes=basis._store)

        self.assertEqual(changes, sorted(list(target.iter_changes(basis))))

    def test_iteritems_empty(self):

        chk_bytes = self.get_chk_bytes()

        root_key = CHKMap.from_dict(chk_bytes, {})

        chkmap = CHKMap(chk_bytes, root_key)

        self.assertEqual([], list(chkmap.iteritems()))

    def test_iteritems_two_items(self):

        chk_bytes = self.get_chk_bytes()

        root_key = CHKMap.from_dict(chk_bytes,

            {"a":"content here", "b":"more content"})

        chkmap = CHKMap(chk_bytes, root_key)

        self.assertEqual([(("a",), "content here"), (("b",), "more content")],

            sorted(list(chkmap.iteritems())))

    def test_iteritems_selected_one_of_two_items(self):

        chkmap = self._get_map( {("a",):"content here", ("b",):"more content"})

        self.assertEqual({("a",): "content here"},

            self.to_dict(chkmap, [("a",)]))

    def test_iteritems_keys_prefixed_by_2_width_nodes(self):

        chkmap = self._get_map(

            {("a","a"):"content here", ("a", "b",):"more content",

             ("b", ""): 'boring content'},

            maximum_size=10, key_width=2)

        self.assertEqual(

            {("a", "a"): "content here", ("a", "b"): 'more content'},

            self.to_dict(chkmap, [("a",)]))

    def test_iteritems_keys_prefixed_by_2_width_one_leaf(self):

        chkmap = self._get_map(

            {("a","a"):"content here", ("a", "b",):"more content",

             ("b", ""): 'boring content'}, key_width=2)

        self.assertEqual(

            {("a", "a"): "content here", ("a", "b"): 'more content'},

            self.to_dict(chkmap, [("a",)]))

    def test___len__empty(self):

        chkmap = self._get_map({})

        self.assertEqual(0, len(chkmap))

    def test___len__2(self):

        chkmap = self._get_map({"foo":"bar", "gam":"quux"})

        self.assertEqual(2, len(chkmap))

    def test_max_size_100_bytes_new(self):

        # When there is a 100 byte upper node limit, a tree is formed.

        chkmap = self._get_map({("k1"*50,):"v1", ("k2"*50,):"v2"}, maximum_size=100)

        # We expect three nodes:

        # A root, with two children, and with two key prefixes - k1 to one, and

        # k2 to the other as our node splitting is only just being developed.

        # The maximum size should be embedded

        chkmap._ensure_root()

        self.assertEqual(100, chkmap._root_node.maximum_size)

        self.assertEqual(1, chkmap._root_node._key_width)

        # There should be two child nodes, and prefix of 2(bytes):

        self.assertEqual(2, len(chkmap._root_node._items))

        self.assertEqual("k", chkmap._root_node.unique_serialised_prefix())

        # The actual nodes pointed at will change as serialisers change; so

        # here we test that the key prefix is correct; then load the nodes and

        # check they have the right pointed at key; whether they have the

        # pointed at value inline or not is also unrelated to this test so we

        # don't check that in detail - rather we just check the aggregate

        # value.

        nodes = sorted(chkmap._root_node._items.items())

        ptr1 = nodes[0]

        ptr2 = nodes[1]

        self.assertEqual('k1', ptr1[0])

        self.assertEqual('k2', ptr2[0])

        node1 = _deserialise(chkmap._read_bytes(ptr1[1]), ptr1[1])

        self.assertIsInstance(node1, LeafNode)

        self.assertEqual(1, len(node1))

        self.assertEqual({('k1'*50,): 'v1'}, self.to_dict(node1, chkmap._store))

        node2 = _deserialise(chkmap._read_bytes(ptr2[1]), ptr2[1])

        self.assertIsInstance(node2, LeafNode)

        self.assertEqual(1, len(node2))

        self.assertEqual({('k2'*50,): 'v2'}, self.to_dict(node2, chkmap._store))

        # Having checked we have a good structure, check that the content is

        # still accessible.

        self.assertEqual(2, len(chkmap))

        self.assertEqual({("k1"*50,): "v1", ("k2"*50,): "v2"},

            self.to_dict(chkmap))

    def test_init_root_is_LeafNode_new(self):

        chk_bytes = self.get_chk_bytes()

        chkmap = CHKMap(chk_bytes, None)

        self.assertIsInstance(chkmap._root_node, LeafNode)

        self.assertEqual({}, self.to_dict(chkmap))

        self.assertEqual(0, len(chkmap))

    def test_init_and_save_new(self):

        chk_bytes = self.get_chk_bytes()

        chkmap = CHKMap(chk_bytes, None)

        key = chkmap._save()

        leaf_node = LeafNode()

        self.assertEqual([key], leaf_node.serialise(chk_bytes))

    def test_map_first_item_new(self):

        chk_bytes = self.get_chk_bytes()

        chkmap = CHKMap(chk_bytes, None)

        chkmap.map(("foo,",), "bar")

        self.assertEqual({('foo,',): 'bar'}, self.to_dict(chkmap))

        self.assertEqual(1, len(chkmap))

        key = chkmap._save()

        leaf_node = LeafNode()

        leaf_node.map(chk_bytes, ("foo,",), "bar")

        self.assertEqual([key], leaf_node.serialise(chk_bytes))

    def test_unmap_last_item_root_is_leaf_new(self):

        chkmap = self._get_map({("k1"*50,): "v1", ("k2"*50,): "v2"})

        chkmap.unmap(("k1"*50,))

        chkmap.unmap(("k2"*50,))

        self.assertEqual(0, len(chkmap))

        self.assertEqual({}, self.to_dict(chkmap))

        key = chkmap._save()

        leaf_node = LeafNode()

        self.assertEqual([key], leaf_node.serialise(chkmap._store))

    def test__dump_tree(self):

        chkmap = self._get_map({("aaa",): "value1", ("aab",): "value2",

                                ("bbb",): "value3",},

                               maximum_size=10)

        self.assertEqualDiff('\n'.join([

            "'' InternalNode sha1:cd9b68f18c9754a79065b06379fba543f9031742",

            "  'a' InternalNode sha1:ed0ceb5aeb87c56df007a17997134328ff4d0b8d",

            "    'aaa' LeafNode sha1:16fa5a38b80d29b529afc45f7a4f894650fc067f",

            "      ('aaa',) 'value1'",

            "    'aab' LeafNode sha1:8fca5400dc99ef1b464e60ca25da53b57406ed38",

            "      ('aab',) 'value2'",

            "  'b' LeafNode sha1:67f15d1dfa451d388ed08ff17b4f9578ba010d01",

            "      ('bbb',) 'value3'",

            ]), chkmap._dump_tree())

    def test__dump_tree_in_progress(self):

        chkmap = self._get_map({("aaa",): "value1", ("aab",): "value2"},

                               maximum_size=10)

        chkmap.map(('bbb',), 'value3')

        # XXX: Note that this representation is different than the one for

        #      test__dump_tree, even though they have the same values

        self.assertEqualDiff('\n'.join([

            "'' InternalNode None",

            "  'a' InternalNode sha1:ed0ceb5aeb87c56df007a17997134328ff4d0b8d",

            "    'aaa' LeafNode sha1:16fa5a38b80d29b529afc45f7a4f894650fc067f",

            "      ('aaa',) 'value1'",

            "    'aab' LeafNode sha1:8fca5400dc99ef1b464e60ca25da53b57406ed38",

            "      ('aab',) 'value2'",

            "  'b' LeafNode None",

            "      ('bbb',) 'value3'",

            ]), chkmap._dump_tree())

class TestLeafNode(TestCaseWithStore):

    def test_current_size_empty(self):

        node = LeafNode()

        self.assertEqual(15, node._current_size())

    def test_current_size_size_changed(self):

        node = LeafNode()

        node.set_maximum_size(10)

        self.assertEqual(16, node._current_size())

    def test_current_size_width_changed(self):

        node = LeafNode()

        node._key_width = 10

        self.assertEqual(16, node._current_size())

    def test_current_size_items(self):

        node = LeafNode()

        base_size = node._current_size()

        node.map(None, ("foo bar",), "baz")

        self.assertEqual(base_size + 12, node._current_size())

    def test_deserialise_empty(self):

        node = LeafNode.deserialise("chkleaf:\n10\n1\n0\n", ("sha1:1234",))

        self.assertEqual(0, len(node))

        self.assertEqual(10, node.maximum_size)

        self.assertEqual(("sha1:1234",), node.key())

    def test_deserialise_items(self):

        node = LeafNode.deserialise(

            "chkleaf:\n0\n1\n2\nfoo bar\x00baz\nquux\x00blarh\n", ("sha1:1234",))

        self.assertEqual(2, len(node))

        self.assertEqual([(("foo bar",), "baz"), (("quux",), "blarh")],

            sorted(node.iteritems(None)))

    def test_deserialise_item_with_null_width_1(self):

        node = LeafNode.deserialise(

            "chkleaf:\n0\n1\n2\nfoo\x00bar\x00baz\nquux\x00blarh\n",

            ("sha1:1234",))

        self.assertEqual(2, len(node))

        self.assertEqual([(("foo",), "bar\x00baz"), (("quux",), "blarh")],

            sorted(node.iteritems(None)))

    def test_deserialise_item_with_null_width_2(self):

        node = LeafNode.deserialise(

            "chkleaf:\n0\n2\n2\nfoo\x001\x00bar\x00baz\nquux\x00\x00blarh\n",

            ("sha1:1234",))

        self.assertEqual(2, len(node))

        self.assertEqual([(("foo", "1"), "bar\x00baz"), (("quux", ""), "blarh")],

            sorted(node.iteritems(None)))

    def test_iteritems_selected_one_of_two_items(self):

        node = LeafNode.deserialise(

            "chkleaf:\n0\n1\n2\nfoo bar\x00baz\nquux\x00blarh\n", ("sha1:1234",))

        self.assertEqual(2, len(node))

        self.assertEqual([(("quux",), "blarh")],

            sorted(node.iteritems(None, [("quux",), ("qaz",)])))

    def test_key_new(self):

        node = LeafNode()

        self.assertEqual(None, node.key())

    def test_key_after_map(self):

        node = LeafNode.deserialise("chkleaf:\n10\n1\n0\n", ("sha1:1234",))

        node.map(None, ("foo bar",), "baz quux")

        self.assertEqual(None, node.key())

    def test_key_after_unmap(self):

        node = LeafNode.deserialise(

            "chkleaf:\n0\n1\n2\nfoo bar\x00baz\nquux\x00blarh\n", ("sha1:1234",))

        node.unmap(None, ("foo bar",))

        self.assertEqual(None, node.key())

    def test_map_exceeding_max_size_only_entry_new(self):

        node = LeafNode()

        node.set_maximum_size(10)

        result = node.map(None, ("foo bar",), "baz quux")

        self.assertEqual(("foo bar", [("", node)]), result)

        self.assertTrue(10 < node._current_size())

    def test_map_exceeding_max_size_second_entry_early_difference_new(self):

        node = LeafNode()

        node.set_maximum_size(10)

        node.map(None, ("foo bar",), "baz quux")

        prefix, result = list(node.map(None, ("blue",), "red"))

        self.assertEqual("", prefix)

        self.assertEqual(2, len(result))

        split_chars = set([result[0][0], result[1][0]])

        self.assertEqual(set(["f", "b"]), split_chars)

        nodes = dict(result)

        node = nodes["f"]

        self.assertEqual({("foo bar",): "baz quux"}, self.to_dict(node, None))

        self.assertEqual(10, node.maximum_size)

        self.assertEqual(1, node._key_width)

        node = nodes["b"]

        self.assertEqual({("blue",): "red"}, self.to_dict(node, None))

        self.assertEqual(10, node.maximum_size)

        self.assertEqual(1, node._key_width)

    def test_map_first(self):

        node = LeafNode()