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

[John Arbash Meinel]

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

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

iEYEARECAAYFAkkghHwACgkQJdeBCYSNAANS4gCdF3WY8izXA2Vmk0tmcDfhZPiG
Y3oAoLqc5VaeylANGdjox4QaeV7nGZpg
=kTXW
-----END PGP SIGNATURE-----