Merge lp:~weyrick/bzr/720853-max-recursion-depth into lp:bzr

[Shannon Weyrick]

Raise BadIndexKey rather than crashing if the key is unreasonably long.

Version 2 of this patch, which fixes the recursion issue in a way that doesn't break the pack command

[John A Meinel (jameinel)]

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

On 11/16/2011 10:09 PM, Shannon Weyrick wrote:
> Shannon Weyrick has proposed merging
> lp:~weyrick/bzr/720853-max-recursion-depth into lp:bzr.
>
> Requested reviews: bzr-core (bzr-core) Related bugs: Bug #720853 in
> Bazaar: "bzr crashed with RuntimeError in normpath(): maximum
> recursion depth exceeded while calling a Python object"
> https://bugs.launchpad.net/bzr/+bug/720853 Bug #889872 in Bazaar:
> "not a valid key error" https://bugs.launchpad.net/bzr/+bug/889872
>
> For more details, see:
> https://code.launchpad.net/~weyrick/bzr/720853-max-recursion-depth/+merge/82453
>
> Version 2 of this patch, which fixes the recursion issue in a way
> that doesn't break the pack command

 merge: approve

John
=:->

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk7E3pAACgkQJdeBCYSNAANS6wCg11uEStRmQaGk38pF45DgkuOh
Ef4AoJh16ykm7zk+kIa7PPwiRSlY4yZu
=l+zk
-----END PGP SIGNATURE-----

review: Approve

[Jelmer Vernooij (jelmer)]

sent to pqm by email

=== modified file 'bzrlib/btree_index.py'
--- bzrlib/btree_index.py	2011-11-14 04:46:48 +0000
+++ bzrlib/btree_index.py	2011-11-16 21:07:26 +0000
@@ -294,8 +294,10 @@
             flag when writing out. This is used by the _spill_mem_keys_to_disk
             functionality.
         """
+        new_leaf = False
         if rows[-1].writer is None:
             # opening a new leaf chunk;
+            new_leaf = True
             for pos, internal_row in enumerate(rows[:-1]):
                 # flesh out any internal nodes that are needed to
                 # preserve the height of the tree
@@ -320,6 +322,11 @@
                 optimize_for_size=self._optimize_for_size)
             rows[-1].writer.write(_LEAF_FLAG)
         if rows[-1].writer.write(line):
+            # if we failed to write, despite having an empty page to write to,
+            # then line is too big. raising the error avoids infinite recursion
+            # searching for a suitably large page that will not be found.
+            if new_leaf:
+                raise errors.BadIndexKey(string_key)
             # this key did not fit in the node:
             rows[-1].finish_node()
             key_line = string_key + "\n"

=== modified file 'bzrlib/tests/test_btree_index.py'
--- bzrlib/tests/test_btree_index.py	2011-11-14 04:46:48 +0000
+++ bzrlib/tests/test_btree_index.py	2011-11-16 21:07:26 +0000
@@ -831,6 +831,14 @@
             btree_index.BTreeGraphIndex(t1, 'index', 10) !=
             btree_index.BTreeGraphIndex(t1, 'index', 20))
 
+    def test_key_too_big(self):
+        # the size that matters here is the _compressed_ size of the key, so we can't
+        # do a simple character repeat.
+        bigKey = ''.join(map(repr, xrange(btree_index._PAGE_SIZE)))
+        self.assertRaises(errors.BadIndexKey,
+                          self.make_index,
+                          nodes=[((bigKey,), 'value', ())])
+        
     def test_iter_all_only_root_no_size(self):
         self.make_index(nodes=[(('key',), 'value', ())])
         t = transport.get_transport_from_url('trace+' + self.get_url(''))

=== modified file 'doc/en/release-notes/bzr-2.5.txt'
--- doc/en/release-notes/bzr-2.5.txt	2011-11-16 17:04:48 +0000
+++ doc/en/release-notes/bzr-2.5.txt	2011-11-16 21:07:26 +0000
@@ -529,6 +529,9 @@
   operations that use it, like merge, can now create trees without a root.
   (Aaron Bentley)
 
+* Raise BadIndexKey exception in btree_index when a key is too large, fixing 
+  an infinite recursion issue. (Shannon Weyrick, #720853)
+
 Documentation
 *************