Subject: PATCH delta: dsfantf1

From: [email-masked]
Date: Sat, 26 Aug 2006 00:27:03 +0200 (MEST)

Lisa asked for my delta format recently.
FWIW here the spec of my delta format.
This is from es.VCSBase.Mod. A WebDAV/DeltaV contribution package to the Native Oberon
system of Niklaus Wirth and Juerg Gutknecht of ETH Zuerich. 
Succeeeded by Bluebottle now (http://bluebottle.ethz.ch)
Please keep in mind that this is from the last millenium and wasn't meant to be 
scrutinized by "RFC professionals". It was written as a quick and dirty reminder
for me to remember the format of my delta files.

>From es.VCSBase.Mod:

$   1, [email-masked], 31 Jan 99, 1:7:28
$ first version for new format
(** new delta file format
description
	(ci) = compressed integer in Oberon style
	(d) =  data as array of bytes
	tags = numbers coded as a byte
---------
DeltaFile =  # newest revision of file + deltas
	FormatName Flags Text 1{ Diff } .
FormatName = "dsfantf1" .
Flags = SET{31..1,MakroBit}.
Text = TextTag TextLen(ci) Text(d) .
Diff = # newer before older diffs
	DiffTag DiffLen(ci) OldTextLen(ci)
	Versiontag Version(ci)
	DateTag DateLen(ci) Date(d)
	AuthorTag AuthorLen(ci) Author(d)
	LogTextTag  LogTextLen(ci)  LogText(d)
	{ DeltaAddTag   AddLen(ci) AddData(d) 
	  | DeltaCopyTag CopyLen(ci) CopyOffset(ci) }
	[ AttachmentTag AttachmentLen(ci) Attachment(d) ] .
*)

So perhaps some remarks are useful:
- The email address given probably doesn't work anymore.
- (ci) is a number which uses as many bytes as necessary. 7 bits of a byte.
  The msb is used to show that another byte follows. Niklaus Wirth used such
  numbers in parts of his Native Oberon system.
- The new resource is created by:
  - Add: n bytes from delta.
  - Copy: n bytes from source. Referenced by an offset to a source file rider.
          Offset can be negative. So you can get some stretch repeatedly or move 
          parts of source around.
  - Attachment: add some miscellaneous data to a version. E.g. WebDAV properties.
          Not further specified yet.

That's all :-)

Some trivial extensions (For perhaps "dsfantf2") are
(Not checked for sanity. Just brainstorming):
- Use bit 7 of the tag byte to work with an additional source rider on the newly
  created resource for copy.
- Use bit 6 of the tag byte to specify absolute positioning instead of the moving
  rider offset.
- DeltaCallTag CallLen(ci) CallOffset(ci) could be used to define a sort of
  "functions" in the delta. "DeltaCallTag 0 offset" will skip a "function" definition.
- Use another target rider to patch the original resource for further copy/call
  tricks.
The "call" and targer rider stuff just came to my mind when I thought about possible
extensions of the format. Could give some tricky ways to "compress" data with patterns.

Now if anybody thinks that "dsfantf1" could be a simple mandatory delta format
for binary files with a PATCH I wouldn't mind. I would be surprised if you find
something similar enough to give IPR problems anywhere. But OTOH you never know.

Cheers, Edgar

---

From: Julian Reschke <[email-masked]>
Date: Sat, 26 Aug 2006 12:41:17 +0200

Hi Edgar,

thanks for the proposal. However, it's not easy to read. Perhaps you 
also have some simple real-world examples?

Related to that I spent some more time thinking at what formats are IMHO 
desirable:

1) A format for specifying text diffs,

2) A format that can transport simple changes to binary files, such as 
replacements, truncates and appends (that format may be useful for 
WebDAV clients that act as file system drivers),

3) potentially a patch format for XML.

Of these, 1) and 2) are well understood and probably simple to implement 
on the server-side. Now a specification of a PATCH format has reduced 
value if the client can't rely on some formats everybody understands. 
Does this mean that we would want to require support for 1) and 2)?

Requiring an XML patch format on the other hand IMHO would be premature, 
and probably not acceptable for a general purpose server.

So how do we get 1) and 2)?

The simplest possible approach for 1) seems to be writing down a concise 
description of the simple diff format, as created by the original Unix 
diff program (see 
<http://www.opengroup.org/onlinepubs/000095399/utilities/diff.html>). I 
think we could get away with defining our profile of that format, and 
then refer to the ISO or IEEE spec. A precedent for that approach is 
RFC3339 (which describes a profile of ISO8601).

The simplest approach for 2) seems to define a new (binary) format that 
can capture POSIX file I/O operations on a byte stream (truncate, seek, 
write, additionally perhaps "copy range from source"). We may want to 
also define a profile that allows streaming (that is, disallows seeking 
back from the current position). If I would have to define the format, 
I'd probably model it similarly to the HTTP chunked encoding format 
(http://greenbytes.de/tech/webdav/rfc2616.html#rfc.section.3.6.1) -- 
"plain text" instructions interleaved by binary content.

 From a procedural point of view I think it would be best to define 
these formats in separate documents, and let the PATCH spec just refer 
to them.

Best regards, Julian