Partial-state inventory deltas

Aaron Bentley aaron at
Thu Jan 3 18:53:02 GMT 2008

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

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.

Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla -


More information about the bazaar mailing list