Subject: Re: git pack/unpack over bittorrent - works!

From: Artur Skawina <[email-masked]>
Date: Sat, 04 Sep 2010 07:42:12 +0200

>> 2) Git doesn't use chained deltas. IOW given commits "A --d1-> B --d2-> C",
>>    "C" can be represented as a delta against "A" or "B", but _not_ against "d1". 
>>    (Think of the case where "C" reverts /part of/ "B")
> 
> Git does use chained deltas indeed.  But deltas are used only at the 
> object level within a pack file.  Any blob object can be represented as 
> a delta against any other blob in the pack, regardless of the commit(s) 
> those blob objects belong to.  Same thing for tree objects.  So you can 
> have deltas going in total random directions if you look them from a 
> commit perspective.  So "C" can have some of its objects being deltas 
> against objects from "B", or "A", or any other commit for that matter, 
> or even objects belonging to the same commit "C". And some other objects 
> from "B" can delta against objects from "C" too. There is simply no 
> restrictions at all on the actual delta direction.  The only rule is 
> that an object may only delta against another object of the same type.
> 
> Of course we don't try to delta each object against all the other 
> available objects as that would be a O(n^2) operation (imagine with n = 
> 1.7 million objects).  So we use many heuristics to make this delta 
> packing efficient without taking an infinite amount of time.
> 
> For example, if we have objects X and Y that need to be packed together 
> and sent to a client over the net, and we find that Y is already a delta 
> against X in one pack that exists locally, then we simply and literally 
> copy the delta representation of Y from that local pack file and send it 
> out without recomputing that delta.

What i meant by 'chained deltas' is a representation that takes delta#1 and
applies delta#2 to the first delta, and applies the result to the source of
delta#1. Which could be a more compact representation of eg. a partial revert.

IOW, if I have commits A..Y, ask (via git pull) for commits X and Z, then I'm
guaranteed to receive them either raw, or as a delta vs commits A..X, right?
What I'm really asking is, if a (modified) git-upload-pack skips transferring
commit X, and just sends me commit Z (possibly as delta vs 'X'), _and_ I 
obtain commit 'X" in some other way, I will be able to reconstruct 'Z', correct?

TIA, 

artur