[CHK/MERGE/RFC] Updates to fetch and node layout

[John Arbash Meinel]

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

And, of course, it is always better when you attach things :)

John Arbash Meinel wrote:
> I found a couple problems with inserting nodes into a CHK map. It turned
> out that you could end up with invalid InternalNodes. Specifically, if
> you had 1 key per leaf and got the keys:
> 
> aaa
> aab
> 
> This would be properly:
>   InternalNode aa?
>     Leaf aaa
>     Leaf aab
> 
> However, if you then inserted 'bbb', it would end up
> 
>   InternalNode aa?
>    Leaf aaa
>    Leaf aab
>    Leaf bbb
> 
> Rather than
> 
>  InternalNode ?
>   InternalNode aa?
>     Leaf aaa
>     Leaf aab
>   Leaf bbb
> 
> There are some other bits
> 
> 1) Reintroduce copy_to, it is actually invalid as is, because I didn't
> get the nested pages done. It isn't meant as the final answer for
> fetching (that is the 'iter_*' interface you can see started.) I think
> something like it is still useful for 'CHKInventory.from_inventory()' as
> the existing code iterates all paths and uses 'apply_delta', which is
> always O(tree). If we don't want chatter, we can keep the O(tree)
> performance and always copy all referenced (instead of only missing)
> pages, but that way it uses the serialized pages, rather than
> deserializing and re-creating the key.
> 
> I don't mind being chatty when the function is
> "CHKInventory.from_inventory()", I do plan on finishing the work for a
> better fetch function.
> 
> 2) CHKMap._dump_tree() was mostly meant as a helper, since trying to
> debug sha1 hashes is awful (is this for 'aaa' or 'aab'?) However, I
> think it can also be useful in testing, as it lets you assert the layout
> of the tree. I would consider updating it to allow a "include_key=False"
> to hide the sha hashes making it resilient to final serialization, while
> still giving the tree shape.
> 
> 
> I can split some of this stuff out if we decide not to merge it. I just
> put it together out-of-order while on the plane. The most important bit
> is getting the InternalNode.map() to be correct, as otherwise we
> generate invalid CHKMaps. I mostly wanted to get it out there before
> someone else found the problem and had to spend the time fixing what
> I've fixed.
> 
> John
> =:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkkghT4ACgkQJdeBCYSNAAPwUgCfUZVYHgXH/BMwrUGgrx4AOC4R
jSMAn2lKh/oB0lwAerfEvx3xOEiH/8Gk
=odBf
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: chk-fetch.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20081116/d9fc22e6/attachment-0001.diff