Merge lp:~jameinel/bzr/2.1-static-tuple-btree-string-intern into lp:bzr

[John A Meinel]

[John A Meinel (jameinel)]

This is the same as an earlier patch for using StaticTuple as part of the btree code. It has a couple small additions.

1) Small fix for 'bzr dump-btree' that casts the objects back to tuples for nicer formatting.
2) Add 'StaticTuple' as a type that 'bencode' knows how to deal with (just treats it as another
   Tuple/List object.)
   Arguably we probably want to end up with 'decode_as_tuples=True' to return StaticTuple
   instances. For now, though, this was all that was necessary to get the test suite to pass on my
   machine. (Though a lot of the tests that were failing on PQM weren't failing here anyway...)

[Andrew Bennetts (spiv)]

384 + refs_as_tuples = tuple([tuple([tuple(ref) for ref in ref_list])
385 + for ref_list in node[3]])

I wonder if it would be worth adding a convenience method, perhaps StaticTuple.as_tuples(), that recursively does this conversion. That would make this ugliness unnecessary.

431 + # I don't believe we can define a method by which
432 + # (prefix,) + StaticTuple will work, though we could

In plain Python you could define an __radd__ for this, so surely there's a way to do this in C?

class T(object):
    def __radd__(self, other):
        return 'haha!'
t = T()

print ('tuple',) + t # prints 'haha!'

You may need to do something odd like provide the nb_add slot, even though this isn't really a numeric type, but I think that's ok. (All pure python classes would have that I think, even the non-numeric ones, so presumably having tp_as_number filled doesn't automatically make Python do dumb things.)

I think we can live without this, but it would be nice.

488 + k1 = stuple(stuple('<email address hidden>',),
489 + stuple('<email address hidden>',))
490 + k2 = stuple(stuple(stuple('<email address hidden>',),
491 + stuple('<email address hidden>',)),
492 + stuple('<email address hidden>',))

This test data is needlessly complex and hard to read. Why not e.g.:

    k1 = stuple(stuple('a',), stuple('b',))
    k2 = stuple(stuple(stuple('c',), stuple('d',)), stuple('a',))

Which is structurally the same and much easier to follow.

review: Approve

[John A Meinel (jameinel)]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Andrew Bennetts wrote:
> Review: Approve
> 384 + refs_as_tuples = tuple([tuple([tuple(ref) for ref in ref_list])
> 385 + for ref_list in node[3]])
>
> I wonder if it would be worth adding a convenience method, perhaps StaticTuple.as_tuples(), that recursively does this conversion. That would make this ugliness unnecessary.

As for "as_tuples()" I would be fine just extending ".as_tuple()" to do
exactly that. The main restriction is that we may not always have tuples
at this point.

At least so far, tuple is interchangeable w/ StaticTuple.

>
> 431 + # I don't believe we can define a method by which
> 432 + # (prefix,) + StaticTuple will work, though we could
>
> In plain Python you could define an __radd__ for this, so surely there's a way to do this in C?
>
> class T(object):
> def __radd__(self, other):
> return 'haha!'
> t = T()
>
> print ('tuple',) + t # prints 'haha!'
>

Tuple uses "tp_as_sequence.sq_concat" to handle ('tuple',) + t, which I
didn't think worked the other way. But thanks for pointing me to this,
I'll look into it.

> You may need to do something odd like provide the nb_add slot, even though this isn't really a numeric type, but I think that's ok. (All pure python classes would have that I think, even the non-numeric ones, so presumably having tp_as_number filled doesn't automatically make Python do dumb things.)
>
> I think we can live without this, but it would be nice.

Actually, the main reason I added the comment is because I expect things
to fail at that point, but I haven't gotten a test case to trigger it,
and it also won't trigger with --2a formats... (They don't have missing
compression parents.)

>
> 488 + k1 = stuple(stuple('<email address hidden>',),
> 489 + stuple('<email address hidden>',))
> 490 + k2 = stuple(stuple(stuple('<email address hidden>',),
> 491 + stuple('<email address hidden>',)),
> 492 + stuple('<email address hidden>',))
>
> This test data is needlessly complex and hard to read. Why not e.g.:
>
> k1 = stuple(stuple('a',), stuple('b',))
> k2 = stuple(stuple(stuple('c',), stuple('d',)), stuple('a',))
>
> Which is structurally the same and much easier to follow.

Sure. I did the above because that was the actual data I was getting. Of
course, I've since narrowed it down to a bug in interning....

Anyway, I'm happy to simplify it, and should have done so before submitting.
John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkrVNP8ACgkQJdeBCYSNAAN61QCbBceibTUybQ2cwzsABrC2rcPc
RwcAni/o9YUyAE/7ShfvcoeHZFGUMwDw
=ZhaX
-----END PGP SIGNATURE-----

[Andrew Bennetts (spiv)]

[...]
> > In plain Python you could define an __radd__ for this, so surely there's a
> > way to do this in C?
[...]
> > You may need to do something odd like provide the nb_add slot, even though
> > this isn't really a numeric type, but I think that's ok. (All pure python
> > classes would have that I think, even the non-numeric ones, so presumably
> > having tp_as_number filled doesn't automatically make Python do dumb
> > things.)

By the way, because lack of support for tuple + StaticTuple caused all the
babune builders to go red, I took a look at this. (specifically,
bzrlib.tests.per_repository.test_write_group.TestResumeableWriteGroup.test_commit_resumed_write_group_with_missing_parents
was failing)

You actually need nb_coerce as well as nb_add. Here's a rough patch that does
this. The error it gives when you try to add a plain tuple with incompatible
elements (e.g. ints) is probably not ideal, but it works.

-Andrew.

=== modified file 'NEWS'
--- NEWS	2009-10-15 04:06:32 +0000
+++ NEWS	2009-10-15 18:31:17 +0000
@@ -25,6 +25,11 @@
 Improvements
 ************
 
+* When reading index files, we now use a ``StaticTuple`` rather than a
+  plain ``tuple`` object. This generally gives a 20% decrease in peak
+  memory, and can give a performance boost up to 40% on large projects.
+  (John Arbash Meinel)
+
 Documentation
 *************
 
@@ -45,13 +50,14 @@
   used as the interning structure for StaticTuple objects.
   (John Arbash Meinel)
 
-* ``bzrlib._static_tuple_pyx.StaticTuple`` is now available. This class
-  functions similarly to ``tuple`` objects. However, it can only point at
-  other ``StaticTuple`` instances or strings. This allows us to remove it
-  from the garbage collector (it cannot be in a cycle), it also allows us
-  to intern the objects. In testing, this can reduce peak memory by
-  20-40%, and significantly improve performance by removing objects from
-  being inspected by the garbage collector. (John Arbash Meinel)
+* ``bzrlib._static_tuple_pyx.StaticTuple`` is now available and used by
+  the btree index parser. This class functions similarly to ``tuple``
+  objects. However, it can only point at other ``StaticTuple`` instances
+  or strings. This allows us to remove it from the garbage collector (it
+  cannot be in a cycle), it also allows us to intern the objects. In
+  testing, this can reduce peak memory by 20-40%, and significantly
+  improve performance by removing objects from being inspected by the
+  garbage collector. (John Arbash Meinel)
 
 Testing
 *******
 
=== modified file 'bzrlib/_bencode_pyx.pyx'
--- bzrlib/_bencode_pyx.pyx	2009-06-05 01:48:32 +0000
+++ bzrlib/_bencode_pyx.pyx	2009-10-15 18:31:17 +0000
@@ -58,6 +58,13 @@
     void D_UPDATE_TAIL(Decoder, int n)
     void E_UPDATE_TAIL(Encoder, int n)
 
+# To maintain compatibility with older versions of pyrex, we have to use the
+# relative import here, rather than 'bzrlib._static_tuple_c'
+from _static_tuple_c cimport StaticTuple, StaticTuple_CheckExact, \
+    import_static_tuple_c
+
+import_static_tuple_c()
+
 
 cdef class Decoder:
     """Bencode decoder"""
@@ -371,7 +378,8 @@
                 self._encode_int(x)
             elif PyLong_CheckExact(x):
                 self._encode_long(x)
-            elif PyList_CheckExact(x) or PyTuple_CheckExact(x):
+            elif (PyList_CheckExact(x) or PyTuple_CheckExact(x)
+                  or StaticTuple_CheckExact(x)):
                 self._encode_list(x)
             elif PyDict_CheckExact(x):
                 self._encode_dict(x)
 
=== modified file 'bzrlib/_btree_serializer_pyx.pyx'
--- bzrlib/_btree_serializer_pyx.pyx	2009-10-08 05:12:01 +0000
+++ bzrlib/_btree_serializer_pyx.pyx	2009-10-15 18:31:17 +0000
@@ -38,6 +38,8 @@
     Py_ssize_t PyString_Size(object p)
     Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *)
     char * PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *)
+    char * PyString_AS_STRING(object)
+    Py_ssize_t PyString_GET_SIZE(object)
     int PyString_AsStringAndSize_ptr(PyObject *, char **buf, Py_ssize_t *len)
     void PyString_InternInPlace(PyObject **)
     int PyTuple_CheckExact(object t)
@@ -55,6 +57,12 @@
     # void *memrchr(void *s, int c, size_t n)
     int strncmp(char *s1, char *s2, size_t n)
 
+# It seems we need to import the definitions so that the pyrex compiler has
+# local names to access them.
+from _static_tuple_c cimport StaticTuple, \
+    import_static_tuple_c, StaticTuple_New, \
+    StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact
+
 
 # TODO: Find some way to import this from _dirstate_helpers
 cdef void* _my_memrchr(void *s, int c, size_t n):
@@ -71,6 +79,7 @@
         pos = pos - 1
     return NULL
 
+
 # TODO: Import this from _dirstate_helpers when it is merged
 cdef object safe_string_from_size(char *s, Py_ssize_t size):
     if size < 0:
@@ -94,6 +103,10 @@
     Py_DECREF_ptr(py_str)
     return result
 
+from bzrlib import _static_tuple_c
+# This sets up the StaticTuple C_API functionality
+import_static_tuple_c()
+
 
 cdef class BTreeLeafParser:
     """Parse the leaf nodes of a BTree index.
@@ -133,6 +146,7 @@
         self._cur_str = NULL
         self._end_str = NULL
         self._header_found = 0
+        # keys are tuples
 
     cdef extract_key(self, char * last):
         """Extract a key.
@@ -142,8 +156,9 @@
         """
         cdef char *temp_ptr
         cdef int loop_counter
-        # keys are tuples
-        key = PyTuple_New(self.key_length)
+        cdef StaticTuple key
+
+        key = StaticTuple_New(self.key_length)
         for loop_counter from 0 <= loop_counter < self.key_length:
             # grab a key segment
             temp_ptr = <char*>memchr(self._start, c'\0', last - self._start)
@@ -158,15 +173,19 @@
                                                    last - self._start)))
                     raise AssertionError(failure_string)
             # capture the key string
-            # TODO: Consider using PyIntern_FromString, the only caveat is that
-            # it assumes a NULL-terminated string, so we have to check if
-            # temp_ptr[0] == c'\0' or some other char.
-            key_element = safe_interned_string_from_size(self._start,
+            if (self.key_length == 1
+                and (temp_ptr - self._start) == 45
+                and strncmp(self._start, 'sha1:', 5) == 0):
+                key_element = safe_string_from_size(self._start,
+                                                    temp_ptr - self._start)
+            else:
+                key_element = safe_interned_string_from_size(self._start,
                                                          temp_ptr - self._start)
             # advance our pointer
             self._start = temp_ptr + 1
             Py_INCREF(key_element)
-            PyTuple_SET_ITEM(key, loop_counter, key_element)
+            StaticTuple_SET_ITEM(key, loop_counter, key_element)
+        key = StaticTuple_Intern(key)
         return key
 
     cdef int process_line(self) except -1:
@@ -176,6 +195,7 @@
         cdef char *ref_ptr
         cdef char *next_start
         cdef int loop_counter
+        cdef Py_ssize_t str_len
 
         self._start = self._cur_str
         # Find the next newline
@@ -211,12 +231,25 @@
             # Invalid line
             raise AssertionError("Failed to find the value area")
         else:
-            # capture the value string
-            value = safe_string_from_size(temp_ptr + 1, last - temp_ptr - 1)
+            # Because of how conversions were done, we ended up with *lots* of
+            # values that are identical. These are all of the 0-length nodes
+            # that are referred to by the TREE_ROOT (and likely some other
+            # directory nodes.) For example, bzr has 25k references to
+            # something like '12607215 328306 0 0', which ends up consuming 1MB
+            # of memory, just for those strings.
+            str_len = last - temp_ptr - 1
+            if (str_len > 4
+                and strncmp(" 0 0", last - 4, 4) == 0):
+                # This drops peak mem for bzr.dev from 87.4MB => 86.2MB
+                # For Launchpad 236MB => 232MB
+                value = safe_interned_string_from_size(temp_ptr + 1, str_len)
+            else:
+                value = safe_string_from_size(temp_ptr + 1, str_len)
             # shrink the references end point
             last = temp_ptr
+
         if self.ref_list_length:
-            ref_lists = []
+            ref_lists = StaticTuple_New(self.ref_list_length)
             loop_counter = 0
             while loop_counter < self.ref_list_length:
                 ref_list = []
@@ -248,18 +281,20 @@
                     if temp_ptr == NULL:
                         # key runs to the end
                         temp_ptr = ref_ptr
+
                     PyList_Append(ref_list, self.extract_key(temp_ptr))
-                PyList_Append(ref_lists, tuple(ref_list))
+                ref_list = StaticTuple_Intern(StaticTuple(*ref_list))
+                Py_INCREF(ref_list)
+                StaticTuple_SET_ITEM(ref_lists, loop_counter - 1, ref_list)
                 # prepare for the next reference list
                 self._start = next_start
-            ref_lists = tuple(ref_lists)
-            node_value = (value, ref_lists)
+            node_value = StaticTuple(value, ref_lists)
         else:
             if last != self._start:
                 # unexpected reference data present
                 raise AssertionError("unexpected reference data present")
-            node_value = (value, ())
-        PyList_Append(self.keys, (key, node_value))
+            node_value = StaticTuple(value, StaticTuple())
+        PyList_Append(self.keys, StaticTuple(key, node_value))
         return 0
 
     def parse(self):
@@ -294,7 +329,6 @@
     cdef Py_ssize_t flat_len
     cdef Py_ssize_t key_len
     cdef Py_ssize_t node_len
-    cdef PyObject * val
     cdef char * value
     cdef Py_ssize_t value_len
     cdef char * out
@@ -303,13 +337,12 @@
     cdef int first_ref_list
     cdef int first_reference
     cdef int i
-    cdef PyObject *ref_bit
     cdef Py_ssize_t ref_bit_len
 
-    if not PyTuple_CheckExact(node):
-        raise TypeError('We expected a tuple() for node not: %s'
+    if not PyTuple_CheckExact(node) and not StaticTuple_CheckExact(node):
+        raise TypeError('We expected a tuple() or StaticTuple() for node not: %s'
             % type(node))
-    node_len = PyTuple_GET_SIZE(node)
+    node_len = len(node)
     have_reference_lists = reference_lists
     if have_reference_lists:
         if node_len != 4:
@@ -318,8 +351,17 @@
     elif node_len < 3:
         raise ValueError('Without ref_lists, we need at least 3 entries not: %s'
             % len(node))
-    # I don't expect that we can do faster than string.join()
-    string_key = '\0'.join(<object>PyTuple_GET_ITEM_ptr_object(node, 1))
+    # TODO: We can probably do better than string.join(), namely
+    #       when key has only 1 item, we can just grab that string
+    #       And when there are 2 items, we could do a single malloc + len() + 1
+    #       also, doing .join() requires a PyObject_GetAttrString call, which
+    #       we could also avoid.
+    # TODO: Note that pyrex 0.9.6 generates fairly crummy code here, using the
+    #       python object interface, versus 0.9.8+ which uses a helper that
+    #       checks if this supports the sequence interface.
+    #       We *could* do more work on our own, and grab the actual items
+    #       lists. For now, just ask people to use a better compiler. :)
+    string_key = '\0'.join(node[1])
 
     # TODO: instead of using string joins, precompute the final string length,
     #       and then malloc a single string and copy everything in.
@@ -336,7 +378,7 @@
     refs_len = 0
     if have_reference_lists:
         # Figure out how many bytes it will take to store the references
-        ref_lists = <object>PyTuple_GET_ITEM_ptr_object(node, 3)
+        ref_lists = node[3]
         next_len = len(ref_lists) # TODO: use a Py function
         if next_len > 0:
             # If there are no nodes, we don't need to do any work
@@ -350,31 +392,31 @@
                     # references
                     refs_len = refs_len + (next_len - 1)
                     for reference in ref_list:
-                        if not PyTuple_CheckExact(reference):
+                        if (not PyTuple_CheckExact(reference)
+                            and not StaticTuple_CheckExact(reference)):
                             raise TypeError(
                                 'We expect references to be tuples not: %s'
                                 % type(reference))
-                        next_len = PyTuple_GET_SIZE(reference)
+                        next_len = len(reference)
                         if next_len > 0:
                             # We will need (len - 1) '\x00' characters to
                             # separate the reference key
                             refs_len = refs_len + (next_len - 1)
-                            for i from 0 <= i < next_len:
-                                ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
-                                if not PyString_CheckExact_ptr(ref_bit):
+                            for ref_bit in reference:
+                                if not PyString_CheckExact(ref_bit):
                                     raise TypeError('We expect reference bits'
                                         ' to be strings not: %s'
                                         % type(<object>ref_bit))
-                                refs_len = refs_len + PyString_GET_SIZE_ptr(ref_bit)
+                                refs_len = refs_len + PyString_GET_SIZE(ref_bit)
 
     # So we have the (key NULL refs NULL value LF)
     key_len = PyString_Size(string_key)
-    val = PyTuple_GET_ITEM_ptr_object(node, 2)
-    if not PyString_CheckExact_ptr(val):
+    val = node[2]
+    if not PyString_CheckExact(val):
         raise TypeError('Expected a plain str for value not: %s'
-                        % type(<object>val))
-    value = PyString_AS_STRING_ptr(val)
-    value_len = PyString_GET_SIZE_ptr(val)
+                        % type(val))
+    value = PyString_AS_STRING(val)
+    value_len = PyString_GET_SIZE(val)
     flat_len = (key_len + 1 + refs_len + 1 + value_len + 1)
     line = PyString_FromStringAndSize(NULL, flat_len)
     # Get a pointer to the new buffer
@@ -396,14 +438,14 @@
                     out[0] = c'\r'
                     out = out + 1
                 first_reference = 0
-                next_len = PyTuple_GET_SIZE(reference)
+                next_len = len(reference)
                 for i from 0 <= i < next_len:
                     if i != 0:
                         out[0] = c'\x00'
                         out = out + 1
-                    ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
-                    ref_bit_len = PyString_GET_SIZE_ptr(ref_bit)
-                    memcpy(out, PyString_AS_STRING_ptr(ref_bit), ref_bit_len)
+                    ref_bit = reference[i]
+                    ref_bit_len = PyString_GET_SIZE(ref_bit)
+                    memcpy(out, PyString_AS_STRING(ref_bit), ref_bit_len)
                     out = out + ref_bit_len
     out[0] = c'\0'
     out = out  + 1
 
=== modified file 'bzrlib/_static_tuple_c.c'
--- bzrlib/_static_tuple_c.c	2009-10-15 16:18:47 +0000
+++ bzrlib/_static_tuple_c.c	2009-10-15 18:31:17 +0000
@@ -418,9 +418,15 @@
             return NULL; /* There seems to be an error */
         }
         if (result == Py_NotImplemented) {
-            PyErr_BadInternalCall();
             Py_DECREF(result);
-            return NULL;
+            /* One side must have had a string and the other a StaticTuple.
+             * This clearly means that they are not equal.
+             */
+            if (op == Py_EQ) {
+                Py_INCREF(Py_False);
+                return Py_False;
+            }
+            result = PyObject_RichCompare(v_obj, w_obj, Py_EQ);
         }
         if (result == Py_False) {
             /* This entry is not identical
 
=== modified file 'bzrlib/btree_index.py'
--- bzrlib/btree_index.py	2009-10-15 04:01:26 +0000
+++ bzrlib/btree_index.py	2009-10-15 18:31:17 +0000
@@ -163,6 +163,7 @@
         node_refs, _ = self._check_key_ref_value(key, references, value)
         if key in self._nodes:
             raise errors.BadIndexDuplicateKey(key, self)
+        # TODO: StaticTuple
         self._nodes[key] = (node_refs, value)
         self._keys.add(key)
         if self._nodes_by_key is not None and self._key_length > 1:
@@ -625,6 +626,7 @@
         for line in lines[2:]:
             if line == '':
                 break
+            # TODO: Switch to StaticTuple here.
             nodes.append(tuple(map(intern, line.split('\0'))))
         return nodes
 
 
=== modified file 'bzrlib/builtins.py'
--- bzrlib/builtins.py	2009-10-08 16:32:43 +0000
+++ bzrlib/builtins.py	2009-10-15 18:31:17 +0000
@@ -431,7 +431,10 @@
         for node in bt.iter_all_entries():
             # Node is made up of:
             # (index, key, value, [references])
-            self.outf.write('%s\n' % (node[1:],))
+            refs_as_tuples = tuple([tuple([tuple(ref) for ref in ref_list])
+                                   for ref_list in node[3]])
+            as_tuple = (tuple(node[1]), node[2], refs_as_tuples)
+            self.outf.write('%s\n' % (as_tuple,))
 
 
 class cmd_remove_tree(Command):
 
=== modified file 'bzrlib/index.py'
--- bzrlib/index.py	2009-10-13 05:20:50 +0000
+++ bzrlib/index.py	2009-10-15 18:31:17 +0000
@@ -40,6 +40,7 @@
     debug,
     errors,
     )
+from bzrlib.static_tuple import StaticTuple
 
 _HEADER_READV = (0, 200)
 _OPTION_KEY_ELEMENTS = "key_elements="
@@ -102,7 +103,7 @@
 
     def _check_key(self, key):
         """Raise BadIndexKey if key is not a valid key for this index."""
-        if type(key) != tuple:
+        if type(key) not in (tuple, StaticTuple):
             raise errors.BadIndexKey(key)
         if self._key_length != len(key):
             raise errors.BadIndexKey(key)
@@ -202,7 +203,9 @@
                 if reference not in self._nodes:
                     self._check_key(reference)
                     absent_references.append(reference)
+            # TODO: StaticTuple
             node_refs.append(tuple(reference_list))
+        # TODO: StaticTuple
         return tuple(node_refs), absent_references
 
     def add_node(self, key, value, references=()):
 
=== modified file 'bzrlib/repository.py'
--- bzrlib/repository.py	2009-10-08 22:53:13 +0000
+++ bzrlib/repository.py	2009-10-15 18:31:17 +0000
@@ -4319,6 +4319,13 @@
                 ):
                 if versioned_file is None:
                     continue
+                # TODO: key is often going to be a StaticTuple object
+                #       I don't believe we can define a method by which
+                #       (prefix,) + StaticTuple will work, though we could
+                #       define a StaticTuple.sq_concat that would allow you to
+                #       pass in either a tuple or a StaticTuple as the second
+                #       object, so instead we could have:
+                #       StaticTuple(prefix) + key here...
                 missing_keys.update((prefix,) + key for key in
                     versioned_file.get_missing_compression_parent_keys())
         except NotImplementedError:
 
=== added file 'bzrlib/static_tuple.py'
--- bzrlib/static_tuple.py	1970-01-01 00:00:00 +0000
+++ bzrlib/static_tuple.py	2009-10-15 18:31:17 +0000
@@ -0,0 +1,25 @@
+# Copyright (C) 2009 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
+
+"""Interface thunk for a StaticTuple implementation."""
+
+try:
+    from bzrlib._static_tuple_c import StaticTuple
+except ImportError, e:
+    from bzrlib import osutils
+    osutils.failed_to_load_extension(e)
+    from bzrlib._static_tuple_py import StaticTuple
+
 
=== modified file 'bzrlib/tests/test__static_tuple.py'
--- bzrlib/tests/test__static_tuple.py	2009-10-12 18:10:24 +0000
+++ bzrlib/tests/test__static_tuple.py	2009-10-15 18:31:17 +0000
@@ -23,6 +23,7 @@
     _static_tuple_py,
     errors,
     osutils,
+    static_tuple,
     tests,
     )
 
@@ -278,6 +279,16 @@
         self.assertCompareEqual(k3, (k1, ('foo', 'bar')))
         self.assertCompareEqual((k1, ('foo', 'bar')), k3)
 
+    def test_compare_mixed_depths(self):
+        stuple = self.module.StaticTuple
+        k1 = stuple(stuple('a',), stuple('b',))
+        k2 = stuple(stuple(stuple('c',), stuple('d',)),
+                    stuple('b',))
+        # This requires comparing a StaticTuple to a 'string', and then
+        # interpreting that value in the next higher StaticTuple. This used to
+        # generate a PyErr_BadIternalCall. We now fall back to *something*.
+        self.assertCompareNoRelation(k1, k2)
+
     def test_hash(self):
         k = self.module.StaticTuple('foo')
         self.assertEqual(hash(k), hash(('foo',)))
@@ -416,3 +427,13 @@
         if self.module is _static_tuple_py:
             return
         self.assertIsNot(None, self.module._C_API)
+
+    def test_static_tuple_thunk(self):
+        # Make sure the right implementation is available from
+        # bzrlib.static_tuple.StaticTuple.
+        if self.module is _static_tuple_py:
+            if CompiledStaticTuple.available():
+                # We will be using the C version
+                return
+        self.assertIs(static_tuple.StaticTuple, 
+                      self.module.StaticTuple)
 
=== modified file 'bzrlib/util/_bencode_py.py'
--- bzrlib/util/_bencode_py.py	2009-06-10 03:56:49 +0000
+++ bzrlib/util/_bencode_py.py	2009-10-15 18:31:17 +0000
@@ -154,6 +154,13 @@
         encode_int(int(x), r)
     encode_func[BooleanType] = encode_bool
 
+try:
+    from bzrlib._static_tuple_c import StaticTuple
+except ImportError:
+    pass
+else:
+    encode_func[StaticTuple] = encode_list
+
 
 def bencode(x):
     r = []
 
=== modified file 'setup.py'
--- setup.py	2009-10-12 17:03:40 +0000
+++ setup.py	2009-10-15 18:31:17 +0000
@@ -270,7 +270,6 @@
 
 add_pyrex_extension('bzrlib._annotator_pyx')
 add_pyrex_extension('bzrlib._bencode_pyx')
-add_pyrex_extension('bzrlib._btree_serializer_pyx')
 add_pyrex_extension('bzrlib._chunks_to_lines_pyx')
 add_pyrex_extension('bzrlib._groupcompress_pyx',
                     extra_source=['bzrlib/diff-delta.c'])
@@ -303,6 +302,8 @@
 add_pyrex_extension('bzrlib._simple_set_pyx')
 ext_modules.append(Extension('bzrlib._static_tuple_c',
                              ['bzrlib/_static_tuple_c.c']))
+add_pyrex_extension('bzrlib._btree_serializer_pyx')
+
 
 if unavailable_files:
     print 'C extension(s) not found:'