Merge lp:~gz/brz/py3_simple_set into lp:brz

[Martin Packman]

Update _simple_set_pyx to more modern cython

So simple set did actually compile on Python 3 already, this branch mostly just tidies things up a bit and makes cython do some more work for us. Ideally we'd remove the manual memory block usage, but that turned out to be a pretty large change.

I wonder a bit if this is the correct optimisation level, but can put off questions like that for now. I diffed the generated C and this ends up much the same as before.

[Jelmer Vernooij (jelmer)]

review: Approve

=== modified file 'breezy/_simple_set_pyx.pxd'
--- breezy/_simple_set_pyx.pxd	2010-02-17 17:11:16 +0000
+++ breezy/_simple_set_pyx.pxd	2017-06-21 22:37:45 +0000
@@ -23,9 +23,7 @@
      eg. SimpleSet.add(key) => saved_key and SimpleSet[key] => saved_key
 """
 
-cdef extern from "Python.h":
-    ctypedef struct PyObject:
-        pass
+from cpython.object cimport PyObject
 
 
 cdef public api class SimpleSet [object SimpleSetObject, type SimpleSet_Type]:
@@ -74,8 +72,8 @@
                             # so we manage it manually
 
     cdef PyObject *_get(self, object key) except? NULL
-    cdef object _add(self, key)
-    cdef int _discard(self, key) except -1
+    cpdef object add(self, key)
+    cpdef bint discard(self, key) except -1
     cdef int _insert_clean(self, PyObject *key) except -1
     cdef Py_ssize_t _resize(self, Py_ssize_t min_unused) except -1
 
 
=== modified file 'breezy/_simple_set_pyx.pyx'
--- breezy/_simple_set_pyx.pyx	2017-06-10 00:09:13 +0000
+++ breezy/_simple_set_pyx.pyx	2017-06-21 22:37:45 +0000
@@ -18,31 +18,25 @@
 
 from __future__ import absolute_import
 
-cdef extern from "python-compat.h":
-    pass
-
-cdef extern from "Python.h":
-    ctypedef unsigned long size_t
-    ctypedef long (*hashfunc)(PyObject*) except -1
-    ctypedef object (*richcmpfunc)(PyObject *, PyObject *, int)
-    ctypedef int (*visitproc)(PyObject *, void *)
-    ctypedef int (*traverseproc)(PyObject *, visitproc, void *)
-    int Py_EQ
-    void Py_INCREF(PyObject *)
-    void Py_DECREF(PyObject *)
-    ctypedef struct PyTypeObject:
-        hashfunc tp_hash
-        richcmpfunc tp_richcompare
-        traverseproc tp_traverse
-
-    PyTypeObject *Py_TYPE(PyObject *)
-    # Note: *Don't* use hash(), Pyrex 0.9.8.5 thinks it returns an 'int', and
-    #       thus silently truncates to 32-bits on 64-bit machines.
-    long PyObject_Hash(PyObject *) except -1
-        
-    void *PyMem_Malloc(size_t nbytes)
-    void PyMem_Free(void *)
-    void memset(void *, int, size_t)
+from cpython.object cimport (
+    hashfunc,
+    Py_EQ,
+    PyObject_Hash,
+    PyTypeObject,
+    Py_TYPE,
+    richcmpfunc,
+    traverseproc,
+    visitproc,
+    )
+from cpython.mem cimport (
+    PyMem_Malloc,
+    PyMem_Free,
+    )
+from cpython.ref cimport (
+    Py_INCREF,
+    Py_DECREF,
+    )
+from libc.string cimport memset
 
 
 # Dummy is an object used to mark nodes that have been deleted. Since
@@ -61,11 +55,9 @@
 _NotImplemented = NotImplemented
 
 
-cdef int _is_equal(PyObject *this, long this_hash, PyObject *other) except -1:
+cdef int _is_equal(object this, long this_hash, object other) except -1:
     cdef long other_hash
 
-    if this == other:
-        return 1
     other_hash = PyObject_Hash(other)
     if other_hash != this_hash:
         return 0
@@ -204,13 +196,14 @@
         """
         cdef size_t i, n_lookup
         cdef long the_hash
-        cdef PyObject **table, **slot
+        cdef PyObject **table
+        cdef PyObject **slot
         cdef Py_ssize_t mask
 
         mask = self._mask
         table = self._table
 
-        the_hash = PyObject_Hash(key)
+        the_hash = PyObject_Hash(<object>key)
         i = the_hash
         for n_lookup from 0 <= n_lookup <= <size_t>mask: # Don't loop forever
             slot = &table[i & mask]
@@ -236,7 +229,9 @@
         :return: The new size of the internal table
         """
         cdef Py_ssize_t new_size, n_bytes, remaining
-        cdef PyObject **new_table, **old_table, **slot
+        cdef PyObject **new_table
+        cdef PyObject **old_table
+        cdef PyObject **slot
 
         new_size = DEFAULT_SIZE
         while new_size <= min_used and new_size > 0:
@@ -269,7 +264,7 @@
         slot = old_table
         while remaining > 0:
             if slot[0] == NULL: # unused slot
-                pass 
+                pass
             elif slot[0] == _dummy: # dummy slot
                 remaining = remaining - 1
             else: # active slot
@@ -279,22 +274,18 @@
         PyMem_Free(old_table)
         return new_size
 
-    def add(self, key):
+    cpdef object add(self, key):
         """Similar to set.add(), start tracking this key.
-        
+
         There is one small difference, which is that we return the object that
         is stored at the given location. (which is closer to the
         dict.setdefault() functionality.)
         """
-        return self._add(key)
-
-    cdef object _add(self, key):
-        cdef PyObject **slot, *py_key
-        cdef int added
-
-        py_key = <PyObject *>key
-        if (Py_TYPE(py_key).tp_richcompare == NULL
-            or Py_TYPE(py_key).tp_hash == NULL):
+        cdef PyObject **slot
+        cdef bint added
+
+        if (Py_TYPE(key).tp_richcompare == NULL
+            or Py_TYPE(key).tp_hash == NULL):
             raise TypeError('Types added to SimpleSet must implement'
                             ' both tp_richcompare and tp_hash')
         added = 0
@@ -302,15 +293,15 @@
         assert self._used < self._mask
         slot = _lookup(self, key)
         if (slot[0] == NULL):
-            Py_INCREF(py_key)
+            Py_INCREF(key)
             self._fill = self._fill + 1
             self._used = self._used + 1
-            slot[0] = py_key
+            slot[0] = <PyObject *>key
             added = 1
         elif (slot[0] == _dummy):
-            Py_INCREF(py_key)
+            Py_INCREF(key)
             self._used = self._used + 1
-            slot[0] = py_key
+            slot[0] = <PyObject *>key
             added = 1
         # No else: clause. If _lookup returns a pointer to
         # a live object, then we already have a value at this location.
@@ -324,23 +315,18 @@
         # so we can still return it
         return retval
 
-    def discard(self, key):
+    cpdef bint discard(self, key) except -1:
         """Remove key from the set, whether it exists or not.
 
         :return: False if the item did not exist, True if it did
         """
-        if self._discard(key):
-            return True
-        return False
-
-    cdef int _discard(self, key) except -1:
-        cdef PyObject **slot, *py_key
+        cdef PyObject **slot
 
         slot = _lookup(self, key)
         if slot[0] == NULL or slot[0] == _dummy:
             return 0
         self._used = self._used - 1
-        Py_DECREF(slot[0])
+        Py_DECREF(<object>slot[0])
         slot[0] = _dummy
         # PySet uses the heuristic: If more than 1/5 are dummies, then resize
         #                           them away
@@ -399,7 +385,6 @@
         if self.set is not None and self._used == self.set._used:
             return self.len
         return 0
-    
 
 
 cdef api SimpleSet SimpleSet_New():
@@ -461,12 +446,12 @@
     cdef size_t i, n_lookup
     cdef Py_ssize_t mask
     cdef long key_hash
-    cdef PyObject **table, **slot, *cur, **free_slot, *py_key
+    cdef PyObject **table
+    cdef PyObject **slot
+    cdef PyObject *cur
+    cdef PyObject **free_slot
 
-    py_key = <PyObject *>key
-    # Note: avoid using hash(obj) because of a bug w/ pyrex 0.9.8.5 and 64-bit
-    #       (it treats hash() as returning an 'int' rather than a 'long')
-    key_hash = PyObject_Hash(py_key)
+    key_hash = PyObject_Hash(key)
     i = <size_t>key_hash
     mask = self._mask
     table = self._table
@@ -481,13 +466,13 @@
                 return free_slot
             else:
                 return slot
-        if cur == py_key:
+        if cur == <PyObject *>key:
             # Found an exact pointer to the key
             return slot
         if cur == _dummy:
             if free_slot == NULL:
                 free_slot = slot
-        elif _is_equal(py_key, key_hash, cur):
+        elif _is_equal(key, key_hash, <object>cur):
             # Both py_key and cur belong in this slot, return it
             return slot
         i = i + 1 + n_lookup
@@ -519,8 +504,8 @@
         This may be the same object, or it may be an equivalent object.
         (consider dict.setdefault(key, key))
     """
-    return _check_self(self)._add(key)
-    
+    return _check_self(self).add(key)
+
 
 cdef api int SimpleSet_Contains(object self, object key) except -1:
     """Is key present in self?"""
@@ -535,7 +520,7 @@
     :return: 1 if there was an object present, 0 if there was not, and -1 on
         error.
     """
-    return _check_self(self)._discard(key)
+    return _check_self(self).discard(key)
 
 
 cdef api PyObject *SimpleSet_Get(SimpleSet self, object key) except? NULL:
 
=== modified file 'breezy/tests/test__simple_set.py'
--- breezy/tests/test__simple_set.py	2017-05-25 01:35:55 +0000
+++ breezy/tests/test__simple_set.py	2017-06-21 22:37:45 +0000
@@ -35,7 +35,7 @@
     """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...
+    implement tp_richcompare in Python 2.
     """
 
     def __init__(self, the_hash):
@@ -69,12 +69,16 @@
     def __eq__(self, other):
         raise RuntimeError('I refuse to play nice')
 
+    __hash__ = _Hashable.__hash__
+
 
 class _NoImplementCompare(_Hashable):
 
     def __eq__(self, other):
         return NotImplemented
 
+    __hash__ = _Hashable.__hash__
+
 
 # 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
@@ -87,14 +91,6 @@
     _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))
 
@@ -281,9 +277,10 @@
 
     def test__resize(self):
         obj = self.module.SimpleSet()
-        k1 = ('foo',)
-        k2 = ('bar',)
-        k3 = ('baz',)
+        # Need objects with exact hash as checking offset of <null> later
+        k1 = _Hashable(501)
+        k2 = _Hashable(591)
+        k3 = _Hashable(2051)
         obj.add(k1)
         obj.add(k2)
         obj.add(k3)
@@ -373,7 +370,7 @@
             all.add(key)
         self.assertEqual(sorted([k1, k2, k3]), sorted(all))
         iterator = iter(obj)
-        next(iterator)
+        self.assertIn(next(iterator), all)
         obj.add(('foo',))
         # Set changed size
         self.assertRaises(RuntimeError, next, iterator)