[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 _______________________________________________ darcs-devel mailing list [email protected] http://www.abridgegame.org/cgi-bin/mailman/listinfo/darcs-devel
