Rev 4768: Review feedback from Andrew Bennetts. in http://bazaar.launchpad.net/~jameinel/bzr/2.1-static-tuple-no-use
John Arbash Meinel
john at arbash-meinel.com
Mon Oct 12 18:51:02 BST 2009
At http://bazaar.launchpad.net/~jameinel/bzr/2.1-static-tuple-no-use
------------------------------------------------------------
revno: 4768
revision-id: john at arbash-meinel.com-20091012175058-c2rosf9sz6dvk0a9
parent: john at arbash-meinel.com-20091012170705-g1v51yp2kfve4f0r
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 2.1-static-tuple-no-use
timestamp: Mon 2009-10-12 12:50:58 -0500
message:
Review feedback from Andrew Bennetts.
-------------- next part --------------
=== modified file 'bzrlib/_static_tuple_c.c'
--- a/bzrlib/_static_tuple_c.c 2009-10-07 19:31:39 +0000
+++ b/bzrlib/_static_tuple_c.c 2009-10-12 17:50:58 +0000
@@ -74,7 +74,7 @@
static StaticTuple *
StaticTuple_Intern(StaticTuple *self)
{
- PyObject *unique_key = NULL;
+ PyObject *canonical_tuple = NULL;
if (_interned_tuples == NULL || _StaticTuple_is_interned(self)) {
Py_INCREF(self);
@@ -83,20 +83,18 @@
/* SimpleSet_Add returns whatever object is present at self
* or the new object if it needs to add it.
*/
- unique_key = SimpleSet_Add(_interned_tuples, (PyObject *)self);
- if (!unique_key) {
- // Suppress any error and just return the object
- PyErr_Clear();
- Py_INCREF(self);
- return self;
+ canonical_tuple = SimpleSet_Add(_interned_tuples, (PyObject *)self);
+ if (!canonical_tuple) {
+ // Some sort of exception, propogate it.
+ return NULL;
}
- if (unique_key != (PyObject *)self) {
- // There was already a key at that location
- return (StaticTuple *)unique_key;
+ if (canonical_tuple != (PyObject *)self) {
+ // There was already a tuple with that value
+ return (StaticTuple *)canonical_tuple;
}
self->flags |= STATIC_TUPLE_INTERNED_FLAG;
- // The two references in the dict do not count, so that the StaticTuple object
- // does not become immortal just because it was interned.
+ // The two references in the dict do not count, so that the StaticTuple
+ // object does not become immortal just because it was interned.
Py_REFCNT(self) -= 1;
return self;
}
@@ -187,7 +185,7 @@
if (len < 0 || len > 255) {
/* Too big or too small */
PyErr_SetString(PyExc_ValueError, "StaticTuple.__init__(...)"
- " takes from 0 to 255 key bits");
+ " takes from 0 to 255 items");
return NULL;
}
self = (StaticTuple *)StaticTuple_New(len);
@@ -199,8 +197,7 @@
if (!PyString_CheckExact(obj)) {
if (!StaticTuple_CheckExact(obj)) {
PyErr_SetString(PyExc_TypeError, "StaticTuple.__init__(...)"
- " requires that all key bits are strings or StaticTuple.");
- /* TODO: What is the proper way to dealloc ? */
+ " requires that all items are strings or StaticTuple.");
type->tp_dealloc((PyObject *)self);
return NULL;
}
@@ -236,21 +233,21 @@
/* adapted from tuplehash(), is the specific hash value considered
* 'stable'?
*/
- register long x, y;
- Py_ssize_t len = self->size;
- PyObject **p;
- long mult = 1000003L;
+ register long x, y;
+ Py_ssize_t len = self->size;
+ PyObject **p;
+ long mult = 1000003L;
#if STATIC_TUPLE_HAS_HASH
if (self->hash != -1) {
return self->hash;
}
#endif
- x = 0x345678L;
- p = self->items;
+ x = 0x345678L;
+ p = self->items;
// TODO: We could set specific flags if we know that, for example, all the
- // keys are strings. I haven't seen a real-world benefit to that yet,
- // though.
+ // items are strings. I haven't seen a real-world benefit to that
+ // yet, though.
while (--len >= 0) {
y = PyObject_Hash(*p++);
if (y == -1) /* failure */
@@ -259,18 +256,13 @@
/* the cast might truncate len; that doesn't change hash stability */
mult += (long)(82520L + len + len);
}
- x += 97531L;
- if (x == -1)
- x = -2;
+ x += 97531L;
+ if (x == -1)
+ x = -2;
#if STATIC_TUPLE_HAS_HASH
- if (self->hash != -1) {
- if (self->hash != x) {
- fprintf(stderr, "hash changed: %d => %d\n", self->hash, x);
- }
- }
self->hash = x;
#endif
- return x;
+ return x;
}
static PyObject *
@@ -281,25 +273,39 @@
vt = StaticTuple_as_tuple((StaticTuple *)v);
if (vt == NULL) {
- goto Done;
+ goto done;
}
if (!PyTuple_Check(wt)) {
PyErr_BadInternalCall();
- result = NULL;
- goto Done;
+ goto done;
}
/* Now we have 2 tuples to compare, do it */
result = PyTuple_Type.tp_richcompare(vt, wt, op);
-Done:
+done:
Py_XDECREF(vt);
return result;
}
+/** Compare two objects to determine if they are equivalent.
+ * The basic flow is as follows
+ * 1) First make sure that both objects are StaticTuple instances. If they
+ * aren't then cast self to a tuple, and have the tuple do the comparison.
+ * 2) Special case comparison to Py_None, because it happens to occur fairly
+ * often in the test suite.
+ * 3) Special case when v and w are the same pointer. As we know the answer to
+ * all queries without walking individual items.
+ * 4) For all operations, we then walk the items to find the first paired
+ * items that are not equal.
+ * 5) If all items found are equal, we then check the length of self and
+ * other to determine equality.
+ * 6) If an item differs, then we apply "op" to those last two items. (eg.
+ * StaticTuple(A, B) > StaticTuple(A, C) iff B > C)
+ */
static PyObject *
StaticTuple_richcompare(PyObject *v, PyObject *w, int op)
{
- StaticTuple *vk, *wk;
+ StaticTuple *v_st, *w_st;
Py_ssize_t vlen, wlen, min_len, i;
PyObject *v_obj, *w_obj;
richcmpfunc string_richcompare;
@@ -313,10 +319,10 @@
Py_INCREF(Py_NotImplemented);
return Py_NotImplemented;
}
- vk = (StaticTuple *)v;
+ v_st = (StaticTuple *)v;
if (StaticTuple_CheckExact(w)) {
/* The most common case */
- wk = (StaticTuple*)w;
+ w_st = (StaticTuple*)w;
} else if (PyTuple_Check(w)) {
/* One of v or w is a tuple, so we go the 'slow' route and cast up to
* tuples to compare.
@@ -325,17 +331,17 @@
* We probably want to optimize comparing self to other when
* other is a tuple.
*/
- return StaticTuple_richcompare_to_tuple(vk, w, op);
+ return StaticTuple_richcompare_to_tuple(v_st, w, op);
} else if (w == Py_None) {
// None is always less than the object
- switch (op) {
- case Py_NE:case Py_GT:case Py_GE:
+ switch (op) {
+ case Py_NE:case Py_GT:case Py_GE:
Py_INCREF(Py_True);
return Py_True;
case Py_EQ:case Py_LT:case Py_LE:
Py_INCREF(Py_False);
return Py_False;
- }
+ }
} else {
/* We don't special case this comparison, we just let python handle
* it.
@@ -344,38 +350,38 @@
return Py_NotImplemented;
}
/* Now we know that we have 2 StaticTuple objects, so let's compare them.
- * This code is somewhat borrowed from tuplerichcompare, except we know our
+ * This code is inspired from tuplerichcompare, except we know our
* objects are limited in scope, so we can inline some comparisons.
*/
if (v == w) {
/* Identical pointers, we can shortcut this easily. */
- switch (op) {
- case Py_EQ:case Py_LE:case Py_GE:
+ switch (op) {
+ case Py_EQ:case Py_LE:case Py_GE:
Py_INCREF(Py_True);
return Py_True;
- case Py_NE:case Py_LT:case Py_GT:
+ case Py_NE:case Py_LT:case Py_GT:
Py_INCREF(Py_False);
return Py_False;
- }
+ }
}
/* TODO: if STATIC_TUPLE_INTERNED_FLAG is set on both objects and they are
* not the same pointer, then we know they aren't the same object
* without having to do sub-by-sub comparison.
*/
- /* It will be rare that we compare tuples of different lengths, so we don't
- * start by optimizing the length comparision, same as the tuple code
- * TODO: Interning may change this, because we'll be comparing lots of
- * different StaticTuple objects in the intern dict
+ /* The only time we are likely to compare items of different lengths is in
+ * something like the interned_keys set. However, the hash is good enough
+ * that it is rare. Note that 'tuple_richcompare' also does not compare
+ * lengths here.
*/
- vlen = vk->size;
- wlen = wk->size;
- min_len = (vlen < wlen) ? vlen : wlen;
+ vlen = v_st->size;
+ wlen = w_st->size;
+ min_len = (vlen < wlen) ? vlen : wlen;
string_richcompare = PyString_Type.tp_richcompare;
for (i = 0; i < min_len; i++) {
PyObject *result = NULL;
- v_obj = StaticTuple_GET_ITEM(vk, i);
- w_obj = StaticTuple_GET_ITEM(wk, i);
+ v_obj = StaticTuple_GET_ITEM(v_st, i);
+ w_obj = StaticTuple_GET_ITEM(w_st, i);
if (PyString_CheckExact(v_obj) && PyString_CheckExact(w_obj)) {
result = string_richcompare(v_obj, w_obj, Py_EQ);
} else if (StaticTuple_CheckExact(v_obj) &&
@@ -415,28 +421,28 @@
}
Py_DECREF(result);
}
- if (i >= vlen || i >= wlen) {
+ if (i >= vlen || i >= wlen) {
/* We walked off one of the lists, but everything compared equal so
* far. Just compare the size.
*/
- int cmp;
- PyObject *res;
- switch (op) {
- case Py_LT: cmp = vlen < wlen; break;
- case Py_LE: cmp = vlen <= wlen; break;
- case Py_EQ: cmp = vlen == wlen; break;
- case Py_NE: cmp = vlen != wlen; break;
- case Py_GT: cmp = vlen > wlen; break;
- case Py_GE: cmp = vlen >= wlen; break;
- default: return NULL; /* cannot happen */
- }
- if (cmp)
- res = Py_True;
- else
- res = Py_False;
- Py_INCREF(res);
- return res;
- }
+ int cmp;
+ PyObject *res;
+ switch (op) {
+ case Py_LT: cmp = vlen < wlen; break;
+ case Py_LE: cmp = vlen <= wlen; break;
+ case Py_EQ: cmp = vlen == wlen; break;
+ case Py_NE: cmp = vlen != wlen; break;
+ case Py_GT: cmp = vlen > wlen; break;
+ case Py_GE: cmp = vlen >= wlen; break;
+ default: return NULL; /* cannot happen */
+ }
+ if (cmp)
+ res = Py_True;
+ else
+ res = Py_False;
+ Py_INCREF(res);
+ return res;
+ }
/* The last item differs, shortcut the Py_NE case */
if (op == Py_NE) {
Py_INCREF(Py_True);
@@ -477,15 +483,22 @@
}
static char StaticTuple__is_interned_doc[] = "_is_interned() => True/False\n"
- "Check to see if this key has been interned.\n";
+ "Check to see if this tuple has been interned.\n";
static PyObject *
StaticTuple_item(StaticTuple *self, Py_ssize_t offset)
{
PyObject *obj;
- if (offset < 0 || offset >= self->size) {
- PyErr_SetString(PyExc_IndexError, "StaticTuple index out of range");
+ /* We cast to (int) to avoid worrying about whether Py_ssize_t is a
+ * long long, etc. offsets should never be >2**31 anyway.
+ */
+ if (offset < 0) {
+ PyErr_Format(PyExc_IndexError, "StaticTuple_item does not support"
+ " negative indices: %d\n", (int)offset);
+ } else if (offset >= self->size) {
+ PyErr_Format(PyExc_IndexError, "StaticTuple index out of range"
+ " %d >= %d", (int)offset, (int)self->size);
return NULL;
}
obj = (PyObject *)self->items[offset];
@@ -519,9 +532,12 @@
static char StaticTuple_doc[] =
"C implementation of a StaticTuple structure."
- "\n This is used as StaticTuple(key_bit_1, key_bit_2, key_bit_3, ...)"
- "\n This is similar to tuple, just less flexible in what it"
- "\n supports, but also lighter memory consumption.";
+ "\n This is used as StaticTuple(item1, item2, item3)"
+ "\n This is similar to tuple, less flexible in what it"
+ "\n supports, but also lighter memory consumption."
+ "\n Note that the constructor mimics the () form of tuples"
+ "\n Rather than the 'tuple()' constructor."
+ "\n eg. StaticTuple(a, b) == (a, b) == tuple((a, b))";
static PyMethodDef StaticTuple_methods[] = {
{"as_tuple", (PyCFunction)StaticTuple_as_tuple, METH_NOARGS, StaticTuple_as_tuple_doc},
@@ -542,6 +558,11 @@
0, /* sq_contains */
};
+/* TODO: Implement StaticTuple_as_mapping.
+ * The only thing we really want to support from there is mp_subscript, so that
+ * we could support extended slicing (foo[::2]). Not worth it yet, though.
+ */
+
PyTypeObject StaticTuple_Type = {
PyObject_HEAD_INIT(NULL)
=== modified file 'bzrlib/tests/test__static_tuple.py'
--- a/bzrlib/tests/test__static_tuple.py 2009-10-07 19:34:22 +0000
+++ b/bzrlib/tests/test__static_tuple.py 2009-10-12 17:50:58 +0000
@@ -140,6 +140,13 @@
self.assertEqual('foo', k[0])
self.assertEqual('z', k[6])
self.assertEqual('z', k[-1])
+ self.assertRaises(IndexError, k.__getitem__, 7)
+ self.assertRaises(IndexError, k.__getitem__, 256+7)
+ self.assertRaises(IndexError, k.__getitem__, 12024)
+ # Python's [] resolver handles the negative arguments, so we can't
+ # really test StaticTuple_item() with negative values.
+ self.assertRaises(TypeError, k.__getitem__, 'not-an-int')
+ self.assertRaises(TypeError, k.__getitem__, '5')
def test_refcount(self):
f = 'fo' + 'oo'
@@ -276,12 +283,22 @@
k = self.module.StaticTuple('foo', 'bar', 'baz', 'bing')
self.assertEqual(('foo', 'bar'), k[:2])
self.assertEqual(('baz',), k[2:-1])
+ try:
+ val = k[::2]
+ except TypeError:
+ # C implementation raises a TypeError, we don't need the
+ # implementation yet, so allow this to pass
+ pass
+ else:
+ # Python implementation uses a regular Tuple, so make sure it gives
+ # the right result
+ self.assertEqual(('foo', 'baz'), val)
def test_referents(self):
# We implement tp_traverse so that things like 'meliae' can measure the
# amount of referenced memory. Unfortunately gc.get_referents() first
- # checks the IS_GC flag before it traverses anything. So there isn't a
- # way to expose it that I can see.
+ # checks the IS_GC flag before it traverses anything. We could write a
+ # helper func, but that won't work for the generic implementation...
self.requireFeature(Meliae)
from meliae import scanner
strs = ['foo', 'bar', 'baz', 'bing']
More information about the bazaar-commits
mailing list