Partial-state inventory deltas

[Aaron Bentley]

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

Robert Collins wrote:
> This patch is really quite trivial:
>  - cleans up the inventory test __init__ a bit
>  - adds some very basic docs on Inventory.

Since it looks like you're driving at producing a tree format based on
inventory deltas, here's a thought I had about doing fast comparisons.

It's true that you can do strict delta composition from a common
ancestor, but I think partial-state composition is probably simpler to
implement.

For the two revisions you're comparing, find a common build-ancestor.
Now, for each revision, build the inventory as if the build-ancestor was
a snapshot, and you're building the full inventory for that revision.
You'll probably need to target a dict rather than an inventory for this
to work properly.  You'll need a special marker for inventory entries
that have been killed.  I'm using None.

You'll end up with two mappings like this:

revision A
{
  file1: x
  file2: y
  file3: z
  file4: None
}

revision B
{
  file1: x
  file2: w
  file5: None
  file6: v
}

Where vwxyz are single InventoryEntries.

To find the delta from B to A, compare the mappings.

1. For file1, the values are identical, so drop it
2. for file2, pick y, because they differ and that is the value in A

At this point, we need to start spelunking.  We don't know what the
values for file3 and file4 are in B, or file5 or file6 in A, so we don't
know whether they're changed or what they changed to.  We have to go
backward in the build-ancestry of the common ancestor until we find
those values.  Once we do, we can handle them appropriately.

It might be useful to store the FROM value as well as the TO value, in
the deltas, because that would avoid the need for spelunking.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHfS8O0F+nu1YWqI0RAibjAJ4yiQSgm0+3vBnP/KDriMRylET7iQCdHBOj
ZB9ZDzsVn9WSFq9ETkwpXp4=
=xDF9
-----END PGP SIGNATURE-----