~bzr-pqm/bzr/bzr.dev

# Copyright (C) 2009, 2010, 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 the StaticTupleInterned type."""

import sys

from bzrlib import (

    tests,

    )

try:

    from bzrlib import _simple_set_pyx

except ImportError:

    _simple_set_pyx = None

class _Hashable(object):

    """A simple object which has a fixed hash value.

    We could have used an 'int', but it turns out that Int objects don't

    implement tp_richcompare...

    """

    def __init__(self, the_hash):

        self.hash = the_hash

    def __hash__(self):

        return self.hash

    def __eq__(self, other):

        if not isinstance(other, _Hashable):

            return NotImplemented

        return other.hash == self.hash

class _BadSecondHash(_Hashable):

    def __init__(self, the_hash):

        _Hashable.__init__(self, the_hash)

        self._first = True

    def __hash__(self):

        if self._first:

            self._first = False

            return self.hash

        else:

            raise ValueError('I can only be hashed once.')

class _BadCompare(_Hashable):

    def __eq__(self, other):

        raise RuntimeError('I refuse to play nice')

class _NoImplementCompare(_Hashable):

    def __eq__(self, other):

        return NotImplemented

# Even though this is an extension, we don't permute the tests for a python

# version. As the plain python version is just a dict or set

compiled_simpleset_feature = tests.ModuleAvailableFeature(

                                'bzrlib._simple_set_pyx')

class TestSimpleSet(tests.TestCase):

    _test_needs_features = [compiled_simpleset_feature]

    module = _simple_set_pyx

    def assertIn(self, obj, container):

        self.assertTrue(obj in container,

            '%s not found in %s' % (obj, container))

    def assertNotIn(self, obj, container):

        self.assertTrue(obj not in container,

            'We found %s in %s' % (obj, container))

    def assertFillState(self, used, fill, mask, obj):

        self.assertEqual((used, fill, mask), (obj.used, obj.fill, obj.mask))

    def assertLookup(self, offset, value, obj, key):

        self.assertEqual((offset, value), obj._test_lookup(key))

    def assertRefcount(self, count, obj):

        """Assert that the refcount for obj is what we expect.

        Note that this automatically adjusts for the fact that calling

        assertRefcount actually creates a new pointer, as does calling

        sys.getrefcount. So pass the expected value *before* the call.

        """

        # I'm not sure why the offset is 3, but I've check that in the caller,

        # an offset of 1 works, which is expected. Not sure why assertRefcount

        # is incrementing/decrementing 2 times

        self.assertEqual(count, sys.getrefcount(obj)-3)

    def test_initial(self):

        obj = self.module.SimpleSet()

        self.assertEqual(0, len(obj))

        st = ('foo', 'bar')

        self.assertFillState(0, 0, 0x3ff, obj)

    def test__lookup(self):

        # These are carefully chosen integers to force hash collisions in the

        # algorithm, based on the initial set size of 1024

        obj = self.module.SimpleSet()

        self.assertLookup(643, '<null>', obj, _Hashable(643))

        self.assertLookup(643, '<null>', obj, _Hashable(643 + 1024))

        self.assertLookup(643, '<null>', obj, _Hashable(643 + 50*1024))

    def test__lookup_collision(self):

        obj = self.module.SimpleSet()

        k1 = _Hashable(643)

        k2 = _Hashable(643 + 1024)

        self.assertLookup(643, '<null>', obj, k1)

        self.assertLookup(643, '<null>', obj, k2)

        obj.add(k1)

        self.assertLookup(643, k1, obj, k1)

        self.assertLookup(644, '<null>', obj, k2)

    def test__lookup_after_resize(self):

        obj = self.module.SimpleSet()

        k1 = _Hashable(643)

        k2 = _Hashable(643 + 1024)

        obj.add(k1)

        obj.add(k2)

        self.assertLookup(643, k1, obj, k1)

        self.assertLookup(644, k2, obj, k2)

        obj._py_resize(2047) # resized to 2048

        self.assertEqual(2048, obj.mask + 1)

        self.assertLookup(643, k1, obj, k1)

        self.assertLookup(643+1024, k2, obj, k2)

        obj._py_resize(1023) # resized back to 1024

        self.assertEqual(1024, obj.mask + 1)

        self.assertLookup(643, k1, obj, k1)

        self.assertLookup(644, k2, obj, k2)

    def test_get_set_del_with_collisions(self):

        obj = self.module.SimpleSet()

        h1 = 643

        h2 = 643 + 1024

        h3 = 643 + 1024*50

        h4 = 643 + 1024*25

        h5 = 644

        h6 = 644 + 1024

        k1 = _Hashable(h1)

        k2 = _Hashable(h2)

        k3 = _Hashable(h3)

        k4 = _Hashable(h4)

        k5 = _Hashable(h5)

        k6 = _Hashable(h6)

        self.assertLookup(643, '<null>', obj, k1)

        self.assertLookup(643, '<null>', obj, k2)

        self.assertLookup(643, '<null>', obj, k3)

        self.assertLookup(643, '<null>', obj, k4)

        self.assertLookup(644, '<null>', obj, k5)

        self.assertLookup(644, '<null>', obj, k6)

        obj.add(k1)

        self.assertIn(k1, obj)

        self.assertNotIn(k2, obj)

        self.assertNotIn(k3, obj)

        self.assertNotIn(k4, obj)

        self.assertLookup(643, k1, obj, k1)

        self.assertLookup(644, '<null>', obj, k2)

        self.assertLookup(644, '<null>', obj, k3)

        self.assertLookup(644, '<null>', obj, k4)

        self.assertLookup(644, '<null>', obj, k5)

        self.assertLookup(644, '<null>', obj, k6)

        self.assertIs(k1, obj[k1])

        self.assertIs(k2, obj.add(k2))

        self.assertIs(k2, obj[k2])

        self.assertLookup(643, k1, obj, k1)

        self.assertLookup(644, k2, obj, k2)

        self.assertLookup(646, '<null>', obj, k3)

        self.assertLookup(646, '<null>', obj, k4)

        self.assertLookup(645, '<null>', obj, k5)

        self.assertLookup(645, '<null>', obj, k6)

        self.assertLookup(643, k1, obj, _Hashable(h1))

        self.assertLookup(644, k2, obj, _Hashable(h2))

        self.assertLookup(646, '<null>', obj, _Hashable(h3))

        self.assertLookup(646, '<null>', obj, _Hashable(h4))

        self.assertLookup(645, '<null>', obj, _Hashable(h5))

        self.assertLookup(645, '<null>', obj, _Hashable(h6))

        obj.add(k3)

        self.assertIs(k3, obj[k3])

        self.assertIn(k1, obj)

        self.assertIn(k2, obj)

        self.assertIn(k3, obj)

        self.assertNotIn(k4, obj)

        obj.discard(k1)

        self.assertLookup(643, '<dummy>', obj, k1)

        self.assertLookup(644, k2, obj, k2)

        self.assertLookup(646, k3, obj, k3)

        self.assertLookup(643, '<dummy>', obj, k4)

        self.assertNotIn(k1, obj)

        self.assertIn(k2, obj)

        self.assertIn(k3, obj)

        self.assertNotIn(k4, obj)

    def test_add(self):

        obj = self.module.SimpleSet()

        self.assertFillState(0, 0, 0x3ff, obj)

        # We use this clumsy notation, because otherwise the refcounts are off.

        # I'm guessing the python compiler sees it is a static tuple, and adds

        # it to the function variables, or somesuch

        k1 = tuple(['foo'])

        self.assertRefcount(1, k1)

        self.assertIs(k1, obj.add(k1))

        self.assertFillState(1, 1, 0x3ff, obj)

        self.assertRefcount(2, k1)

        ktest = obj[k1]

        self.assertRefcount(3, k1)

        self.assertIs(k1, ktest)

        del ktest

        self.assertRefcount(2, k1)

        k2 = tuple(['foo'])

        self.assertRefcount(1, k2)

        self.assertIsNot(k1, k2)

        # doesn't add anything, so the counters shouldn't be adjusted

        self.assertIs(k1, obj.add(k2))

        self.assertFillState(1, 1, 0x3ff, obj)

        self.assertRefcount(2, k1) # not changed

        self.assertRefcount(1, k2) # not incremented

        self.assertIs(k1, obj[k1])

        self.assertIs(k1, obj[k2])

        self.assertRefcount(2, k1)

        self.assertRefcount(1, k2)

        # Deleting an entry should remove the fill, but not the used

        obj.discard(k1)

        self.assertFillState(0, 1, 0x3ff, obj)

        self.assertRefcount(1, k1)

        k3 = tuple(['bar'])

        self.assertRefcount(1, k3)

        self.assertIs(k3, obj.add(k3))

        self.assertFillState(1, 2, 0x3ff, obj)

        self.assertRefcount(2, k3)

        self.assertIs(k2, obj.add(k2))

        self.assertFillState(2, 2, 0x3ff, obj)

        self.assertRefcount(1, k1)

        self.assertRefcount(2, k2)

        self.assertRefcount(2, k3)

    def test_discard(self):

        obj = self.module.SimpleSet()

        k1 = tuple(['foo'])

        k2 = tuple(['foo'])

        k3 = tuple(['bar'])

        self.assertRefcount(1, k1)

        self.assertRefcount(1, k2)

        self.assertRefcount(1, k3)

        obj.add(k1)

        self.assertRefcount(2, k1)

        self.assertEqual(0, obj.discard(k3))

        self.assertRefcount(1, k3)

        obj.add(k3)

        self.assertRefcount(2, k3)

        self.assertEqual(1, obj.discard(k3))

        self.assertRefcount(1, k3)

    def test__resize(self):

        obj = self.module.SimpleSet()

        k1 = ('foo',)

        k2 = ('bar',)

        k3 = ('baz',)

        obj.add(k1)

        obj.add(k2)

        obj.add(k3)

        obj.discard(k2)

        self.assertFillState(2, 3, 0x3ff, obj)

        self.assertEqual(1024, obj._py_resize(500))

        # Doesn't change the size, but does change the content

        self.assertFillState(2, 2, 0x3ff, obj)

        obj.add(k2)

        obj.discard(k3)

        self.assertFillState(2, 3, 0x3ff, obj)

        self.assertEqual(4096, obj._py_resize(4095))

        self.assertFillState(2, 2, 0xfff, obj)

        self.assertIn(k1, obj)

        self.assertIn(k2, obj)

        self.assertNotIn(k3, obj)

        obj.add(k2)

        self.assertIn(k2, obj)

        obj.discard(k2)

        self.assertEqual((591, '<dummy>'), obj._test_lookup(k2))

        self.assertFillState(1, 2, 0xfff, obj)

        self.assertEqual(2048, obj._py_resize(1024))

        self.assertFillState(1, 1, 0x7ff, obj)

        self.assertEqual((591, '<null>'), obj._test_lookup(k2))

    def test_second_hash_failure(self):

        obj = self.module.SimpleSet()

        k1 = _BadSecondHash(200)

        k2 = _Hashable(200)

        # Should only call hash() one time

        obj.add(k1)

        self.assertFalse(k1._first)

        self.assertRaises(ValueError, obj.add, k2)

    def test_richcompare_failure(self):

        obj = self.module.SimpleSet()

        k1 = _Hashable(200)

        k2 = _BadCompare(200)

        obj.add(k1)

        # Tries to compare with k1, fails

        self.assertRaises(RuntimeError, obj.add, k2)

    def test_richcompare_not_implemented(self):

        obj = self.module.SimpleSet()

        # Even though their hashes are the same, tp_richcompare returns

        # NotImplemented, which means we treat them as not equal

        k1 = _NoImplementCompare(200)

        k2 = _NoImplementCompare(200)

        self.assertLookup(200, '<null>', obj, k1)

        self.assertLookup(200, '<null>', obj, k2)

        self.assertIs(k1, obj.add(k1))

        self.assertLookup(200, k1, obj, k1)

        self.assertLookup(201, '<null>', obj, k2)

        self.assertIs(k2, obj.add(k2))

        self.assertIs(k1, obj[k1])

    def test_add_and_remove_lots_of_items(self):

        obj = self.module.SimpleSet()

        chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890'

        for i in chars:

            for j in chars:

                k = (i, j)

                obj.add(k)

        num = len(chars)*len(chars)

        self.assertFillState(num, num, 0x1fff, obj)

        # Now delete all of the entries and it should shrink again

        for i in chars:

            for j in chars:

                k = (i, j)

                obj.discard(k)

        # It should be back to 1024 wide mask, though there may still be some

        # dummy values in there

        self.assertFillState(0, obj.fill, 0x3ff, obj)

        # but there should be fewer than 1/5th dummy entries

        self.assertTrue(obj.fill < 1024 / 5)

    def test__iter__(self):

        obj = self.module.SimpleSet()

        k1 = ('1',)

        k2 = ('1', '2')

        k3 = ('3', '4')

        obj.add(k1)

        obj.add(k2)

        obj.add(k3)

        all = set()

        for key in obj:

            all.add(key)

        self.assertEqual(sorted([k1, k2, k3]), sorted(all))

        iterator = iter(obj)

        iterator.next()

        obj.add(('foo',))

        # Set changed size

        self.assertRaises(RuntimeError, iterator.next)

        # And even removing an item still causes it to fail

        obj.discard(k2)

        self.assertRaises(RuntimeError, iterator.next)

    def test__sizeof__(self):

        # SimpleSet needs a custom sizeof implementation, because it allocates

        # memory that Python cannot directly see (_table).

        # Too much variability in platform sizes for us to give a fixed size

        # here. However without a custom implementation, __sizeof__ would give

        # us only the size of the object, and not its table. We know the table

        # is at least 4bytes*1024entries in size.

        obj = self.module.SimpleSet()

        self.assertTrue(obj.__sizeof__() > 4096)