~bzr-pqm/bzr/bzr.dev

# Copyright (C) 2008-2011 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

#

"""Tests for btree indices."""

import pprint

import zlib

from bzrlib import (

    btree_index,

    errors,

    fifo_cache,

    lru_cache,

    osutils,

    tests,

    transport,

    )

from bzrlib.tests import (

    TestCaseWithTransport,

    scenarios,

    )

from bzrlib.tests import (

    features,

    )

load_tests = scenarios.load_tests_apply_scenarios

def btreeparser_scenarios():

    import bzrlib._btree_serializer_py as py_module

    scenarios = [('python', {'parse_btree': py_module})]

    if compiled_btreeparser_feature.available():

        scenarios.append(('C', 

            {'parse_btree': compiled_btreeparser_feature.module}))

    return scenarios

compiled_btreeparser_feature = features.ModuleAvailableFeature(

    'bzrlib._btree_serializer_pyx')

class BTreeTestCase(TestCaseWithTransport):

    # test names here are suffixed by the key length and reference list count

    # that they test.

    def setUp(self):

        super(BTreeTestCase, self).setUp()

        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)

    def make_nodes(self, count, key_elements, reference_lists):

        """Generate count*key_elements sample nodes."""

        keys = []

        for prefix_pos in range(key_elements):

            if key_elements - 1:

                prefix = (str(prefix_pos) * 40,)

            else:

                prefix = ()

            for pos in xrange(count):

                # TODO: This creates odd keys. When count == 100,000, it

                #       creates a 240 byte key

                key = prefix + (str(pos) * 40,)

                value = "value:%s" % pos

                if reference_lists:

                    # generate some references

                    refs = []

                    for list_pos in range(reference_lists):

                        # as many keys in each list as its index + the key depth

                        # mod 2 - this generates both 0 length lists and

                        # ones slightly longer than the number of lists.

                        # It also ensures we have non homogeneous lists.

                        refs.append([])

                        for ref_pos in range(list_pos + pos % 2):

                            if pos % 2:

                                # refer to a nearby key

                                refs[-1].append(prefix + ("ref" + str(pos - 1) * 40,))

                            else:

                                # serial of this ref in the ref list

                                refs[-1].append(prefix + ("ref" + str(ref_pos) * 40,))

                        refs[-1] = tuple(refs[-1])

                    refs = tuple(refs)

                else:

                    refs = ()

                keys.append((key, value, refs))

        return keys

    def shrink_page_size(self):

        """Shrink the default page size so that less fits in a page."""

        self.overrideAttr(btree_index, '_PAGE_SIZE')

        btree_index._PAGE_SIZE = 2048

    def assertEqualsApproxCompressed(self, expected, actual, slop=6):

        """Check a count of compressed bytes is approximately as expected

        Relying on compressed length being stable even with fixed inputs is

        slightly bogus, but zlib is stable enough that this mostly works.

        """

        if not expected - slop < actual < expected + slop:

            self.fail("Expected around %d bytes compressed but got %d" %

                (expected, actual))

class TestBTreeBuilder(BTreeTestCase):

    def test_clear_cache(self):

        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)

        # This is a no-op, but we need the api to be consistent with other

        # BTreeGraphIndex apis.

        builder.clear_cache()

    def test_empty_1_0(self):

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"

            "row_lengths=\n",

            content)

    def test_empty_2_1(self):

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=1)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"

            "row_lengths=\n",

            content)

    def test_root_leaf_1_0(self):

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

        nodes = self.make_nodes(5, 1, 0)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(131, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"

            "row_lengths=1\n",

            content[:73])

        node_content = content[73:]

        node_bytes = zlib.decompress(node_content)

        expected_node = ("type=leaf\n"

            "0000000000000000000000000000000000000000\x00\x00value:0\n"

            "1111111111111111111111111111111111111111\x00\x00value:1\n"

            "2222222222222222222222222222222222222222\x00\x00value:2\n"

            "3333333333333333333333333333333333333333\x00\x00value:3\n"

            "4444444444444444444444444444444444444444\x00\x00value:4\n")

        self.assertEqual(expected_node, node_bytes)

    def test_root_leaf_2_2(self):

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)

        nodes = self.make_nodes(5, 2, 2)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(238, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"

            "row_lengths=1\n",

            content[:74])

        node_content = content[74:]

        node_bytes = zlib.decompress(node_content)

        expected_node = (

            "type=leaf\n"

            "0000000000000000000000000000000000000000\x000000000000000000000000000000000000000000\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:0\n"

            "0000000000000000000000000000000000000000\x001111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\r0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:1\n"

            "0000000000000000000000000000000000000000\x002222222222222222222222222222222222222222\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:2\n"

            "0000000000000000000000000000000000000000\x003333333333333333333333333333333333333333\x000000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\t0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\r0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\x00value:3\n"

            "0000000000000000000000000000000000000000\x004444444444444444444444444444444444444444\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:4\n"

            "1111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:0\n"

            "1111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\r1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:1\n"

            "1111111111111111111111111111111111111111\x002222222222222222222222222222222222222222\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:2\n"

            "1111111111111111111111111111111111111111\x003333333333333333333333333333333333333333\x001111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\t1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\r1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\x00value:3\n"

            "1111111111111111111111111111111111111111\x004444444444444444444444444444444444444444\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:4\n"

            ""

            )

        self.assertEqual(expected_node, node_bytes)

    def test_2_leaves_1_0(self):

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

        nodes = self.make_nodes(400, 1, 0)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqualsApproxCompressed(9283, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"

            "row_lengths=1,2\n",

            content[:77])

        root = content[77:4096]

        leaf1 = content[4096:8192]

        leaf2 = content[8192:]

        root_bytes = zlib.decompress(root)

        expected_root = (

            "type=internal\n"

            "offset=0\n"

            ) + ("307" * 40) + "\n"

        self.assertEqual(expected_root, root_bytes)

        # We already know serialisation works for leaves, check key selection:

        leaf1_bytes = zlib.decompress(leaf1)

        sorted_node_keys = sorted(node[0] for node in nodes)

        node = btree_index._LeafNode(leaf1_bytes, 1, 0)

        self.assertEqual(231, len(node))

        self.assertEqual(sorted_node_keys[:231], node.all_keys())

        leaf2_bytes = zlib.decompress(leaf2)

        node = btree_index._LeafNode(leaf2_bytes, 1, 0)

        self.assertEqual(400 - 231, len(node))

        self.assertEqual(sorted_node_keys[231:], node.all_keys())

    def test_last_page_rounded_1_layer(self):

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

        nodes = self.make_nodes(10, 1, 0)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqualsApproxCompressed(155, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"

            "row_lengths=1\n",

            content[:74])

        # Check thelast page is well formed

        leaf2 = content[74:]

        leaf2_bytes = zlib.decompress(leaf2)

        node = btree_index._LeafNode(leaf2_bytes, 1, 0)

        self.assertEqual(10, len(node))

        sorted_node_keys = sorted(node[0] for node in nodes)

        self.assertEqual(sorted_node_keys, node.all_keys())

    def test_last_page_not_rounded_2_layer(self):

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

        nodes = self.make_nodes(400, 1, 0)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqualsApproxCompressed(9283, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"

            "row_lengths=1,2\n",

            content[:77])

        # Check the last page is well formed

        leaf2 = content[8192:]

        leaf2_bytes = zlib.decompress(leaf2)

        node = btree_index._LeafNode(leaf2_bytes, 1, 0)

        self.assertEqual(400 - 231, len(node))

        sorted_node_keys = sorted(node[0] for node in nodes)

        self.assertEqual(sorted_node_keys[231:], node.all_keys())

    def test_three_level_tree_details(self):

        # The left most pointer in the second internal node in a row should

        # pointer to the second node that the internal node is for, _not_

        # the first, otherwise the first node overlaps with the last node of

        # the prior internal node on that row.

        self.shrink_page_size()

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)

        # 40K nodes is enough to create a two internal nodes on the second

        # level, with a 2K page size

        nodes = self.make_nodes(20000, 2, 2)

        for node in nodes:

            builder.add_node(*node)

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

        size = t.put_file('index', self.time(builder.finish))

        del builder

        index = btree_index.BTreeGraphIndex(t, 'index', size)

        # Seed the metadata, we're using internal calls now.

        index.key_count()

        self.assertEqual(3, len(index._row_lengths),

            "Not enough rows: %r" % index._row_lengths)

        self.assertEqual(4, len(index._row_offsets))

        self.assertEqual(sum(index._row_lengths), index._row_offsets[-1])

        internal_nodes = index._get_internal_nodes([0, 1, 2])

        root_node = internal_nodes[0]

        internal_node1 = internal_nodes[1]

        internal_node2 = internal_nodes[2]

        # The left most node node2 points at should be one after the right most

        # node pointed at by node1.

        self.assertEqual(internal_node2.offset, 1 + len(internal_node1.keys))

        # The left most key of the second node pointed at by internal_node2

        # should be its first key. We can check this by looking for its first key

        # in the second node it points at

        pos = index._row_offsets[2] + internal_node2.offset + 1

        leaf = index._get_leaf_nodes([pos])[pos]

        self.assertTrue(internal_node2.keys[0] in leaf)

    def test_2_leaves_2_2(self):

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)

        nodes = self.make_nodes(100, 2, 2)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqualsApproxCompressed(12643, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"

            "row_lengths=1,3\n",

            content[:77])

        root = content[77:4096]

        leaf1 = content[4096:8192]

        leaf2 = content[8192:12288]

        leaf3 = content[12288:]

        root_bytes = zlib.decompress(root)

        expected_root = (

            "type=internal\n"

            "offset=0\n"

            + ("0" * 40) + "\x00" + ("91" * 40) + "\n"

            + ("1" * 40) + "\x00" + ("81" * 40) + "\n"

            )

        self.assertEqual(expected_root, root_bytes)

        # We assume the other leaf nodes have been written correctly - layering

        # FTW.

    def test_spill_index_stress_1_1(self):

        builder = btree_index.BTreeBuilder(key_elements=1, spill_at=2)

        nodes = [node[0:2] for node in self.make_nodes(16, 1, 0)]

        builder.add_node(*nodes[0])

        # Test the parts of the index that take up memory are doing so

        # predictably.

        self.assertEqual(1, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        builder.add_node(*nodes[1])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(1, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        # now back to memory

        builder.add_node(*nodes[2])

        self.assertEqual(1, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        # And spills to a second backing index combing all

        builder.add_node(*nodes[3])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(2, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(4, builder._backing_indices[1].key_count())

        # The next spills to the 2-len slot

        builder.add_node(*nodes[4])

        builder.add_node(*nodes[5])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(2, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        self.assertEqual(4, builder._backing_indices[1].key_count())

        # Next spill combines

        builder.add_node(*nodes[6])

        builder.add_node(*nodes[7])

        self.assertEqual(3, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(None, builder._backing_indices[1])

        self.assertEqual(8, builder._backing_indices[2].key_count())

        # And so forth - counting up in binary.

        builder.add_node(*nodes[8])

        builder.add_node(*nodes[9])

        self.assertEqual(3, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        self.assertEqual(None, builder._backing_indices[1])

        self.assertEqual(8, builder._backing_indices[2].key_count())

        builder.add_node(*nodes[10])

        builder.add_node(*nodes[11])

        self.assertEqual(3, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(4, builder._backing_indices[1].key_count())

        self.assertEqual(8, builder._backing_indices[2].key_count())

        builder.add_node(*nodes[12])

        # Test that memory and disk are both used for query methods; and that

        # None is skipped over happily.

        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],

            list(builder.iter_all_entries()))

        # Two nodes - one memory one disk

        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),

            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))

        self.assertEqual(13, builder.key_count())

        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),

            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))

        builder.add_node(*nodes[13])

        self.assertEqual(3, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        self.assertEqual(4, builder._backing_indices[1].key_count())

        self.assertEqual(8, builder._backing_indices[2].key_count())

        builder.add_node(*nodes[14])

        builder.add_node(*nodes[15])

        self.assertEqual(4, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(None, builder._backing_indices[1])

        self.assertEqual(None, builder._backing_indices[2])

        self.assertEqual(16, builder._backing_indices[3].key_count())

        # Now finish, and check we got a correctly ordered tree

        t = self.get_transport('')

        size = t.put_file('index', builder.finish())

        index = btree_index.BTreeGraphIndex(t, 'index', size)

        nodes = list(index.iter_all_entries())

        self.assertEqual(sorted(nodes), nodes)

        self.assertEqual(16, len(nodes))

    def test_spill_index_stress_1_1_no_combine(self):

        builder = btree_index.BTreeBuilder(key_elements=1, spill_at=2)

        builder.set_optimize(for_size=False, combine_backing_indices=False)

        nodes = [node[0:2] for node in self.make_nodes(16, 1, 0)]

        builder.add_node(*nodes[0])

        # Test the parts of the index that take up memory are doing so

        # predictably.

        self.assertEqual(1, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        builder.add_node(*nodes[1])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(1, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        # now back to memory

        builder.add_node(*nodes[2])

        self.assertEqual(1, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        # And spills to a second backing index but doesn't combine

        builder.add_node(*nodes[3])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(2, len(builder._backing_indices))

        for backing_index in builder._backing_indices:

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

        # The next spills to the 3rd slot

        builder.add_node(*nodes[4])

        builder.add_node(*nodes[5])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(3, len(builder._backing_indices))

        for backing_index in builder._backing_indices:

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

        # Now spill a few more, and check that we don't combine

        builder.add_node(*nodes[6])

        builder.add_node(*nodes[7])

        builder.add_node(*nodes[8])

        builder.add_node(*nodes[9])

        builder.add_node(*nodes[10])

        builder.add_node(*nodes[11])

        builder.add_node(*nodes[12])

        self.assertEqual(6, len(builder._backing_indices))

        for backing_index in builder._backing_indices:

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

        # Test that memory and disk are both used for query methods; and that

        # None is skipped over happily.

        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],

            list(builder.iter_all_entries()))

        # Two nodes - one memory one disk

        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),

            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))

        self.assertEqual(13, builder.key_count())

        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),

            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))

        builder.add_node(*nodes[13])

        builder.add_node(*nodes[14])

        builder.add_node(*nodes[15])

        self.assertEqual(8, len(builder._backing_indices))

        for backing_index in builder._backing_indices:

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

        # Now finish, and check we got a correctly ordered tree

        transport = self.get_transport('')

        size = transport.put_file('index', builder.finish())

        index = btree_index.BTreeGraphIndex(transport, 'index', size)

        nodes = list(index.iter_all_entries())

        self.assertEqual(sorted(nodes), nodes)

        self.assertEqual(16, len(nodes))

    def test_set_optimize(self):

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)

        builder.set_optimize(for_size=True)

        self.assertTrue(builder._optimize_for_size)

        builder.set_optimize(for_size=False)

        self.assertFalse(builder._optimize_for_size)

        # test that we can set combine_backing_indices without effecting

        # _optimize_for_size

        obj = object()

        builder._optimize_for_size = obj

        builder.set_optimize(combine_backing_indices=False)

        self.assertFalse(builder._combine_backing_indices)

        self.assertIs(obj, builder._optimize_for_size)

        builder.set_optimize(combine_backing_indices=True)

        self.assertTrue(builder._combine_backing_indices)

        self.assertIs(obj, builder._optimize_for_size)

    def test_spill_index_stress_2_2(self):

        # test that references and longer keys don't confuse things.

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,

            spill_at=2)

        nodes = self.make_nodes(16, 2, 2)

        builder.add_node(*nodes[0])

        # Test the parts of the index that take up memory are doing so

        # predictably.

        self.assertEqual(1, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        builder.add_node(*nodes[1])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(1, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        # now back to memory

        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict

        builder.add_node(*nodes[2])

        self.assertEqual(1, len(builder._nodes))

        self.assertIsNot(None, builder._nodes_by_key)

        self.assertNotEqual({}, builder._nodes_by_key)

        # We should have a new entry

        self.assertNotEqual(old, builder._nodes_by_key)

        # And spills to a second backing index combing all

        builder.add_node(*nodes[3])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(2, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(4, builder._backing_indices[1].key_count())

        # The next spills to the 2-len slot

        builder.add_node(*nodes[4])

        builder.add_node(*nodes[5])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(2, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        self.assertEqual(4, builder._backing_indices[1].key_count())

        # Next spill combines

        builder.add_node(*nodes[6])

        builder.add_node(*nodes[7])

        self.assertEqual(3, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(None, builder._backing_indices[1])