[darcs-devel] Re: [darcs-users] FOSDEM summary

[Ganesh Sittampalam]

[This followup is to darcs-devel only]

On Mon, 27 Feb 2006, Juliusz Chroboczek wrote:

> What follows is a summary of my notes; please do correct me if I'm
> incomplete or incorrect about anything.
>
> We first met on Saturday afternoon.

There were some discussions on Friday evening at dinner, but nothing 
crucial to report, I think - some discussion about conflictors mainly.

> Conflictors are a hard problem, but people seem optimistic.  My gut
> instinct is that the concrete representation (apparently due to Arjan)
> needs to be refined, but I really don't understand the issues.

It definitely needs significantly more work by the experts (i.e. Arjan and 
David) but it is looking promising so far.

> We then walked for eight miles uphill in the freezing wind to a rather 
> nice Brasserie

It's certainly true that we walked to a nice Brasserie ;-)

> Everyone complained about Juliusz being a lazy bum.
[...]
> Everyone complained about Juliusz being a lazy bum.

These occurrences must have been when I was away from the table ;-)

> End-to-end hashing: including cryptographic hashes of the patch in
> minimal context in the patches themselves.  This is believed to
> provide end-to-end protection, but verification will be somewhat
> expensive (require some commuting).  This is more of a long-term
> project, but is definitely worth doing.  It is somewhat tricky, and
> should probably be implemented by one of David, Ganesh or Eric as far
> as the patch-specific bits are concerned, and by Juliusz for the
> hashing itself.

I believe Eric is going to do the patch-specific bits.

> Someone (my notes don't say who, but I seem to recall it was at least
> two people) requested the ability to record multiple patches

Myself and Edwin Brady were the requesters.

> simultaneously, splitting changes interactively.  After some
> discussion, people agreed that this would be a good idea, and Ganesh
> volunteered to implement the necessary extensions to patch_select.

I made no promise on doing it in a timely fashion, or indeed at all, but 
we did agree a rough design that I could follow if I were to do it. If 
anyone else reading is interested in doing so, I can give some rough 
pointers.

> About binary patches.  Unfortunately, nobody present admitted to using
> binary patches, but the reactions at David's talk clearly showed that
> this is something people do care about.  We went through a few possible
> designs.  Ganesh suggested we just keep the current format but without
> hex conversion.  Juliusz suggested we allow the use of arbitrary
> binary diff algorithms, but David worried about compatibility.  David
> and Ganesh suggested a format that contains XORs of the old and new
> contents, and David suggested that this could also contain offset
> information, but Ganesh claimed David was being too ``clever''
> (apparently a mild insult in British English).  We finally reached the
> compromise that we'll accept the format suggested by David, but will
> only generate patches that use 0 offsets for now, which will allow us
> to move to David's idea in the future if David can prove it is useful.

I don't really agree with your description of the argument, but what 
matters is the conclusion:

The key point is that we should have a patch format that is not tied to a 
specific binary diff algorithm. This does have the cost that we cannot use 
any of the clever binary diff algorithms, because those all use very 
specific formats.

The point of the XOR format is that it will make it possible to use LCS on 
binaries in future if we choose to, but initially we can construct a patch 
trivially by just XORing all the data. The representation is this triple:

(offset, length of old sequence, length of new sequence, XOR of old and 
new data with shorter data zero-padded).

For now, I intend to focus mainly on trying to formalise patch theory, 
building on my existing work on proving N-way permutivity. I'm not sure 
what the appropriate list for progress reports and discussion should be - 
any thoughts?

Cheers,

Ganesh