~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


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\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\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\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\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\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\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\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\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\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\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\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\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\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\n"
            "key\x00\x0066\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\n"
            "key\x00\x00071\r088\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\n"
            "keference\x00\x00\t\x00data\n"
            "rey\x00\x0053\t53\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\n"
            "aeference2\x00a\x00\x00\n"
            "beference\x00a\x00\x00\n"
            "rey\x00\x0068\r53\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\n"
            "0\x00a\x00\x00\n"
            "1\x00a\x00\x00\n"
            "2\x00a\x00\x00\n"
            "2-key\x00\x00145\r139\r133\r127\r121\r115\r065\r059\r053\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\n"
            "aail\x00a\x00\x00\n"
            "parent\x00\x0053\r78\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_index(self, ref_lists=0, key_elements=1, nodes=[]):
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
        for node, value, references in nodes:
            builder.add_node(node, value, references)
        stream = builder.finish()
        trans = self.get_transport()
        trans.put_file('index', stream)
        return GraphIndex(trans, 'index')

    def test_open_bad_index_no_error(self):
        trans = self.get_transport()
        trans.put_bytes('name', "not an index\n")
        index = GraphIndex(trans, 'name')

    def test_iter_all_entries_empty(self):
        index = self.make_index()
        self.assertEqual([], list(index.iter_all_entries()))

    def test_iter_all_entries_simple(self):
        index = self.make_index(nodes=[(('name', ), 'data', ())])
        self.assertEqual([(('name', ), 'data')],
            list(index.iter_all_entries()))

    def test_iter_all_entries_simple_2_elements(self):
        index = self.make_index(key_elements=2,
            nodes=[(('name', 'surname'), 'data', ())])
        self.assertEqual([(('name', 'surname'), 'data')],
            list(index.iter_all_entries()))

    def test_iter_all_entries_references_resolved(self):
        index = self.make_index(1, nodes=[
            (('name', ), 'data', ([('ref', )], )),
            (('ref', ), 'refdata', ([], ))])
        self.assertEqual(set([(('name', ), 'data', ((('ref',),),)),
            (('ref', ), 'refdata', ((), ))]),
            set(index.iter_all_entries()))

    def test_iteration_absent_skipped(self):
        index = self.make_index(1, nodes=[
            (('name', ), 'data', ([('ref', )], ))])
        self.assertEqual(set([(('name', ), 'data', ((('ref',),),))]),
            set(index.iter_all_entries()))
        self.assertEqual(set([(('name', ), 'data', ((('ref',),),))]),
            set(index.iter_entries([('name', )])))
        self.assertEqual([], list(index.iter_entries([('ref', )])))

    def test_iteration_absent_skipped_2_element_keys(self):
        index = self.make_index(1, key_elements=2, nodes=[
            (('name', 'fin'), 'data', ([('ref', 'erence')], ))])
        self.assertEqual(set([(('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
            set(index.iter_all_entries()))
        self.assertEqual(set([(('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
            set(index.iter_entries([('name', 'fin')])))
        self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))

    def test_iter_all_keys(self):
        index = self.make_index(1, nodes=[
            (('name', ), 'data', ([('ref', )], )),
            (('ref', ), 'refdata', ([], ))])
        self.assertEqual(set([(('name', ), 'data', ((('ref',),),)),
            (('ref', ), 'refdata', ((), ))]),
            set(index.iter_entries([('name', ), ('ref', )])))

    def test_iter_nothing_empty(self):
        index = self.make_index()
        self.assertEqual([], list(index.iter_entries([])))

    def test_iter_missing_entry_empty(self):
        index = self.make_index()
        self.assertEqual([], list(index.iter_entries([('a', )])))

    def test_iter_key_prefix_1_element_key_None(self):
        index = self.make_index()
        self.assertRaises(errors.BadIndexKey, list,
            index.iter_entries_prefix([(None, )]))

    def test_iter_key_prefix_wrong_length(self):
        index = self.make_index()
        self.assertRaises(errors.BadIndexKey, list,
            index.iter_entries_prefix([('foo', None)]))
        index = self.make_index(key_elements=2)
        self.assertRaises(errors.BadIndexKey, list,
            index.iter_entries_prefix([('foo', )]))
        self.assertRaises(errors.BadIndexKey, list,
            index.iter_entries_prefix([('foo', None, None)]))

    def test_iter_key_prefix_1_key_element_no_refs(self):
        index = self.make_index( nodes=[
            (('name', ), 'data', ()),
            (('ref', ), 'refdata', ())])
        self.assertEqual(set([(('name', ), 'data'),
            (('ref', ), 'refdata')]),
            set(index.iter_entries_prefix([('name', ), ('ref', )])))

    def test_iter_key_prefix_1_key_element_refs(self):
        index = self.make_index(1, nodes=[
            (('name', ), 'data', ([('ref', )], )),
            (('ref', ), 'refdata', ([], ))])
        self.assertEqual(set([(('name', ), 'data', ((('ref',),),)),
            (('ref', ), 'refdata', ((), ))]),
            set(index.iter_entries_prefix([('name', ), ('ref', )])))

    def test_iter_key_prefix_2_key_element_no_refs(self):
        index = self.make_index(key_elements=2, nodes=[
            (('name', 'fin1'), 'data', ()),
            (('name', 'fin2'), 'beta', ()),
            (('ref', 'erence'), 'refdata', ())])
        self.assertEqual(set([(('name', 'fin1'), 'data'),
            (('ref', 'erence'), 'refdata')]),
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
        self.assertEqual(set([(('name', 'fin1'), 'data'),
            (('name', 'fin2'), 'beta')]),
            set(index.iter_entries_prefix([('name', None)])))

    def test_iter_key_prefix_2_key_element_refs(self):
        index = self.make_index(1, key_elements=2, nodes=[
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
            (('name', 'fin2'), 'beta', ([], )),
            (('ref', 'erence'), 'refdata', ([], ))])
        self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
            (('ref', 'erence'), 'refdata', ((), ))]),
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
        self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
            (('name', 'fin2'), 'beta', ((), ))]),
            set(index.iter_entries_prefix([('name', None)])))

    def test_validate_bad_index_errors(self):
        trans = self.get_transport()
        trans.put_bytes('name', "not an index\n")
        index = GraphIndex(trans, 'name')
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)

    def test_validate_bad_node_refs(self):
        index = self.make_index(2)
        trans = self.get_transport()
        content = trans.get_bytes('index')
        # change the options line to end with a rather than a parseable number
        new_content = content[:-2] + 'a\n\n'
        trans.put_bytes('index', new_content)
        self.assertRaises(errors.BadIndexOptions, index.validate)

    def test_validate_missing_end_line_empty(self):
        index = self.make_index(2)
        trans = self.get_transport()
        content = trans.get_bytes('index')
        # truncate the last byte
        trans.put_bytes('index', content[:-1])
        self.assertRaises(errors.BadIndexData, index.validate)

    def test_validate_missing_end_line_nonempty(self):
        index = self.make_index(2, nodes=[(('key', ), '', ([], []))])
        trans = self.get_transport()
        content = trans.get_bytes('index')
        # truncate the last byte
        trans.put_bytes('index', content[:-1])
        self.assertRaises(errors.BadIndexData, index.validate)

    def test_validate_empty(self):
        index = self.make_index()
        index.validate()

    def test_validate_no_refs_content(self):
        index = self.make_index(nodes=[(('key', ), 'value', ())])
        index.validate()


class TestCombinedGraphIndex(TestCaseWithMemoryTransport):

    def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
        for node, value, references in nodes:
            builder.add_node(node, value, references)
        stream = builder.finish()
        trans = self.get_transport()
        trans.put_file(name, stream)
        return GraphIndex(trans, name)

    def test_open_missing_index_no_error(self):
        trans = self.get_transport()
        index1 = GraphIndex(trans, 'missing')
        index = CombinedGraphIndex([index1])

    def test_add_index(self):
        index = CombinedGraphIndex([])
        index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
        index.insert_index(0, index1)
        self.assertEqual([(('key', ), '')], list(index.iter_all_entries()))

    def test_iter_all_entries_empty(self):
        index = CombinedGraphIndex([])
        self.assertEqual([], list(index.iter_all_entries()))

    def test_iter_all_entries_children_empty(self):
        index1 = self.make_index('name')
        index = CombinedGraphIndex([index1])
        self.assertEqual([], list(index.iter_all_entries()))

    def test_iter_all_entries_simple(self):
        index1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
        index = CombinedGraphIndex([index1])
        self.assertEqual([(('name', ), 'data')],
            list(index.iter_all_entries()))

    def test_iter_all_entries_two_indices(self):
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
        index2 = self.make_index('name2', nodes=[(('2', ), '', ())])
        index = CombinedGraphIndex([index1, index2])
        self.assertEqual([(('name', ), 'data'),
            (('2', ), '')],
            list(index.iter_all_entries()))

    def test_iter_entries_two_indices_dup_key(self):
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
        index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
        index = CombinedGraphIndex([index1, index2])
        self.assertEqual([(('name', ), 'data')],
            list(index.iter_entries([('name', )])))

    def test_iter_all_entries_two_indices_dup_key(self):
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
        index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
        index = CombinedGraphIndex([index1, index2])
        self.assertEqual([(('name', ), 'data')],
            list(index.iter_all_entries()))

    def test_iter_key_prefix_2_key_element_refs(self):
        index1 = self.make_index('1', 1, key_elements=2, nodes=[
            (('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
        index2 = self.make_index('2', 1, key_elements=2, nodes=[
            (('name', 'fin2'), 'beta', ([], )),
            (('ref', 'erence'), 'refdata', ([], ))])
        index = CombinedGraphIndex([index1, index2])
        self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
            (('ref', 'erence'), 'refdata', ((), ))]),
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
        self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
            (('name', 'fin2'), 'beta', ((), ))]),
            set(index.iter_entries_prefix([('name', None)])))

    def test_iter_nothing_empty(self):
        index = CombinedGraphIndex([])
        self.assertEqual([], list(index.iter_entries([])))

    def test_iter_nothing_children_empty(self):
        index1 = self.make_index('name')
        index = CombinedGraphIndex([index1])
        self.assertEqual([], list(index.iter_entries([])))

    def test_iter_all_keys(self):
        index1 = self.make_index('1', 1, nodes=[
            (('name', ), 'data', ([('ref', )], ))])
        index2 = self.make_index('2', 1, nodes=[
            (('ref', ), 'refdata', ((), ))])
        index = CombinedGraphIndex([index1, index2])
        self.assertEqual(set([(('name', ), 'data', ((('ref', ), ), )),
            (('ref', ), 'refdata', ((), ))]),
            set(index.iter_entries([('name', ), ('ref', )])))
 
    def test_iter_all_keys_dup_entry(self):
        index1 = self.make_index('1', 1, nodes=[
            (('name', ), 'data', ([('ref', )], )),
            (('ref', ), 'refdata', ([], ))])
        index2 = self.make_index('2', 1, nodes=[
            (('ref', ), 'refdata', ([], ))])
        index = CombinedGraphIndex([index1, index2])
        self.assertEqual(set([(('name', ), 'data', ((('ref',),),)),
            (('ref', ), 'refdata', ((), ))]),
            set(index.iter_entries([('name', ), ('ref', )])))
 
    def test_iter_missing_entry_empty(self):
        index = CombinedGraphIndex([])
        self.assertEqual([], list(index.iter_entries([('a', )])))

    def test_iter_missing_entry_one_index(self):
        index1 = self.make_index('1')
        index = CombinedGraphIndex([index1])
        self.assertEqual([], list(index.iter_entries([('a', )])))

    def test_iter_missing_entry_two_index(self):
        index1 = self.make_index('1')
        index2 = self.make_index('2')
        index = CombinedGraphIndex([index1, index2])
        self.assertEqual([], list(index.iter_entries([('a', )])))
 
    def test_iter_entry_present_one_index_only(self):
        index1 = self.make_index('1', nodes=[(('key', ), '', ())])
        index2 = self.make_index('2', nodes=[])
        index = CombinedGraphIndex([index1, index2])
        self.assertEqual([(('key', ), '')],
            list(index.iter_entries([('key', )])))
        # and in the other direction
        index = CombinedGraphIndex([index2, index1])
        self.assertEqual([(('key', ), '')],
            list(index.iter_entries([('key', )])))

    def test_validate_bad_child_index_errors(self):
        trans = self.get_transport()
        trans.put_bytes('name', "not an index\n")
        index1 = GraphIndex(trans, 'name')
        index = CombinedGraphIndex([index1])
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)

    def test_validate_empty(self):
        index = CombinedGraphIndex([])
        index.validate()


class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):

    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
        result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
        result.add_nodes(nodes)
        return result

    def test_add_nodes_no_refs(self):
        index = self.make_index(0)
        index.add_nodes([(('name', ), 'data')])
        index.add_nodes([(('name2', ), ''), (('name3', ), '')])
        self.assertEqual(set([
            (('name', ), 'data'),
            (('name2', ), ''),
            (('name3', ), ''),
            ]), set(index.iter_all_entries()))

    def test_add_nodes(self):
        index = self.make_index(1)
        index.add_nodes([(('name', ), 'data', ([],))])
        index.add_nodes([(('name2', ), '', ([],)), (('name3', ), '', ([('r', )],))])
        self.assertEqual(set([
            (('name', ), 'data', ((),)),
            (('name2', ), '', ((),)),
            (('name3', ), '', ((('r', ), ), )),
            ]), set(index.iter_all_entries()))

    def test_iter_all_entries_empty(self):
        index = self.make_index()
        self.assertEqual([], list(index.iter_all_entries()))

    def test_iter_all_entries_simple(self):
        index = self.make_index(nodes=[(('name', ), 'data')])
        self.assertEqual([(('name', ), 'data')],
            list(index.iter_all_entries()))

    def test_iter_all_entries_references(self):
        index = self.make_index(1, nodes=[
            (('name', ), 'data', ([('ref', )], )),
            (('ref', ), 'refdata', ([], ))])
        self.assertEqual(set([(('name', ), 'data', ((('ref', ),),)),
            (('ref', ), 'refdata', ((), ))]),
            set(index.iter_all_entries()))

    def test_iteration_absent_skipped(self):
        index = self.make_index(1, nodes=[
            (('name', ), 'data', ([('ref', )], ))])
        self.assertEqual(set([(('name', ), 'data', ((('ref',),),))]),
            set(index.iter_all_entries()))
        self.assertEqual(set([(('name', ), 'data', ((('ref',),),))]),
            set(index.iter_entries([('name', )])))
        self.assertEqual([], list(index.iter_entries([('ref', )])))

    def test_iter_all_keys(self):
        index = self.make_index(1, nodes=[
            (('name', ), 'data', ([('ref', )], )),
            (('ref', ), 'refdata', ([], ))])
        self.assertEqual(set([(('name', ), 'data', ((('ref',),),)),
            (('ref', ), 'refdata', ((), ))]),
            set(index.iter_entries([('name', ), ('ref', )])))

    def test_iter_key_prefix_1_key_element_no_refs(self):
        index = self.make_index( nodes=[
            (('name', ), 'data'),
            (('ref', ), 'refdata')])
        self.assertEqual(set([(('name', ), 'data'),
            (('ref', ), 'refdata')]),
            set(index.iter_entries_prefix([('name', ), ('ref', )])))

    def test_iter_key_prefix_1_key_element_refs(self):
        index = self.make_index(1, nodes=[
            (('name', ), 'data', ([('ref', )], )),
            (('ref', ), 'refdata', ([], ))])
        self.assertEqual(set([(('name', ), 'data', ((('ref',),),)),
            (('ref', ), 'refdata', ((), ))]),
            set(index.iter_entries_prefix([('name', ), ('ref', )])))

    def test_iter_key_prefix_2_key_element_no_refs(self):
        index = self.make_index(key_elements=2, nodes=[
            (('name', 'fin1'), 'data'),
            (('name', 'fin2'), 'beta'),
            (('ref', 'erence'), 'refdata')])
        self.assertEqual(set([(('name', 'fin1'), 'data'),
            (('ref', 'erence'), 'refdata')]),
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
        self.assertEqual(set([(('name', 'fin1'), 'data'),
            (('name', 'fin2'), 'beta')]),
            set(index.iter_entries_prefix([('name', None)])))

    def test_iter_key_prefix_2_key_element_refs(self):
        index = self.make_index(1, key_elements=2, nodes=[
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
            (('name', 'fin2'), 'beta', ([], )),
            (('ref', 'erence'), 'refdata', ([], ))])
        self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
            (('ref', 'erence'), 'refdata', ((), ))]),
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
        self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
            (('name', 'fin2'), 'beta', ((), ))]),
            set(index.iter_entries_prefix([('name', None)])))

    def test_iter_nothing_empty(self):
        index = self.make_index()
        self.assertEqual([], list(index.iter_entries([])))

    def test_iter_missing_entry_empty(self):
        index = self.make_index()
        self.assertEqual([], list(index.iter_entries(['a'])))

    def test_validate_empty(self):
        index = self.make_index()
        index.validate()

    def test_validate_no_refs_content(self):
        index = self.make_index(nodes=[(('key', ), 'value')])
        index.validate()