Tree delta patch format - a bit of process

[Erik Huelsmann <eh...@gmail.com>]

[ This mail may seem directed mostly at Charles and Nicolas, but I
think it may apply to all of us ]


As you may or may not know, we've had discussions about the patch
format and what it should look like before. As before, we've started
out this time (again) with a proposal for a format. This proposal then
triggers a lot of reactions, many of which point out flaws in the
design.

I have wanted the patch discussion to materialize for a long time now,
so I'm hoping this time will be *it*.

I see a problem with how we've gone about achieving this goal: we've
forgotten to define (or assumed implicit) the use-cases for this patch
format.

So, I'd like us to come up with a number of use-cases, then decide
which ones we're actually going to solve. From that, we can distill
the requirements for the format. From there on we can implement it and
use that as a solid basis to conquer the world. :-)

bye,


Erik.

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Tree delta patch format - a bit of process

[Malcolm Rowe <ma...@farside.org.uk>]

On Sun, Apr 01, 2007 at 05:53:46PM +0200, Erik Huelsmann wrote:
> I see a problem with how we've gone about achieving this goal: we've
> forgotten to define (or assumed implicit) the use-cases for this patch
> format.
> 
> So, I'd like us to come up with a number of use-cases, then decide
> which ones we're actually going to solve. From that, we can distill
> the requirements for the format. From there on we can implement it and
> use that as a solid basis to conquer the world. :-)
> 

I agree.  Some use cases are mentioned at
http://subversion.tigris.org/project_tasks.html#svn-augmented-diff, but
we should also document the problems we're not trying to solve (or not
trying to solve _yet_; for the SoC work, imprecise tree-delta
application would probably be a good example of the latter).

Regards,
Malcolm

Re: Tree delta patch format - a bit of process

[Michael Brouwer <mb...@gmail.com>]

I just wanted to point out how svk does this.  As far as I know SVK does no
tree fuzzing at all.  Instead if the tree of the wc that you are trying to
merge a patch to doesn't exactly match the tree in the patch, you need to
svk patch --update the patch first to effectively do a svk merge between the
tree the patch represents, the current wc with the tree the patch was based
on as a common ancestor.  The algorithm used to merge tree changes in this
case is the same as for any other 3 way merge.

in addition svk has another operation which lets you refresh the contents of
a patch if the versions on which the patch was based have changed (say you
made a patch to apply all the changes on a branch, but you have committed a
new change to that branch).  svk patch --regenerate will re-create the patch
as if the command used to create the patch was run against the repository as
it exists today.

Another note on both patches and merge tracking.  Assuming merge tracking
keep track of all the metadata it tracks today on a per repository uuid
basis, and patches contain the repository uuids from which they were created
(as well as any merge tracking info that comes with the trees in the patch),
applying a patch can import new merge tracking data into the tree, in a way
that new patches can be applied while taking already merged changes
potentially included in the patch into account.  This process would be made
even easier if patches spanning multiple changes could be created as
incremental patch sets, where each set represent one or more source
revisions.

Michael


On 4/3/07, Charles Acknin <ch...@gmail.com> wrote:
>
> On 4/1/07, Erik Huelsmann <eh...@gmail.com> wrote:
> > [ This mail may seem directed mostly at Charles and Nicolas, but I
> > think it may apply to all of us ]
> >
> >
> > As you may or may not know, we've had discussions about the patch
> > format and what it should look like before. As before, we've started
> > out this time (again) with a proposal for a format. This proposal then
> > triggers a lot of reactions, many of which point out flaws in the
> > design.
> >
> > I have wanted the patch discussion to materialize for a long time now,
> > so I'm hoping this time will be *it*.
> >
> > I see a problem with how we've gone about achieving this goal: we've
> > forgotten to define (or assumed implicit) the use-cases for this patch
> > format.
> >
> > So, I'd like us to come up with a number of use-cases, then decide
> > which ones we're actually going to solve. From that, we can distill
> > the requirements for the format. From there on we can implement it and
> > use that as a solid basis to conquer the world. :-)
>
> There are a couple of _patch format_ use-cases that I have in mind,
> randomly:
> (below 'patch' means a patch with the new format we're talking about)
>
> a) a user wants to read the patch
> b) a user wants his patch to represent a complete set of changes (bin
> files, directories, props)
> c) when a user applies the patch, the target path differs from the
> patch in some ways; it could be caused by:
>    - tree changes
>    - file changes (context or checksum don't match)
> d) a user wants to modify the patch
> e) a user applies the patch on a mixed-revision WC
>
> Now, assuming those few use-cases are right, some problems arise.
>
> (a) and (d) are incompatible with (b) at least for binary files.  How
> do we represent the change of a binary file?  Do we build some sort of
> [context -> data -> context] binary hunk (call it binary-patch(1)) or
> do we send the whole new binary file?  I guess the latter doesn't make
> the world happy with rather large files but would be way easier and
> fit with the SoC timeframe.  BTW, does anybody have a clue how large
> binary files are (average with Subversion's users)?
>
> If we store tree and property changes into an encoded hunk, (a) and
> possibly (d) disappear again.  One solution would be to store those
> changes in plain-text but I'm not sure this is the right way to take.
>
> (c) and (e) are all about fuzzy patching.  It is OK if we (initially)
> decide to call patch(1) in Subversion to take advantage of its
> contextual-file non-precise patching feature.  But about tree changes,
> we'd have to define the amount of fuzzing we want.  I'm doubtful this
> could be done in a 2-month period.  This has been discussed elsethread
> (Malcolm's redirection, March 29).
>
> Any thoughts?
>
> Cheers,
>
> Charles
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
> For additional commands, e-mail: dev-help@subversion.tigris.org
>
>

Re: Tree delta patch format - a bit of process

[Charles Acknin <ch...@gmail.com>]

On 4/1/07, Erik Huelsmann <eh...@gmail.com> wrote:
> [ This mail may seem directed mostly at Charles and Nicolas, but I
> think it may apply to all of us ]
>
>
> As you may or may not know, we've had discussions about the patch
> format and what it should look like before. As before, we've started
> out this time (again) with a proposal for a format. This proposal then
> triggers a lot of reactions, many of which point out flaws in the
> design.
>
> I have wanted the patch discussion to materialize for a long time now,
> so I'm hoping this time will be *it*.
>
> I see a problem with how we've gone about achieving this goal: we've
> forgotten to define (or assumed implicit) the use-cases for this patch
> format.
>
> So, I'd like us to come up with a number of use-cases, then decide
> which ones we're actually going to solve. From that, we can distill
> the requirements for the format. From there on we can implement it and
> use that as a solid basis to conquer the world. :-)

There are a couple of _patch format_ use-cases that I have in mind, randomly:
(below 'patch' means a patch with the new format we're talking about)

 a) a user wants to read the patch
 b) a user wants his patch to represent a complete set of changes (bin
files, directories, props)
 c) when a user applies the patch, the target path differs from the
patch in some ways; it could be caused by:
   - tree changes
   - file changes (context or checksum don't match)
 d) a user wants to modify the patch
 e) a user applies the patch on a mixed-revision WC

Now, assuming those few use-cases are right, some problems arise.

(a) and (d) are incompatible with (b) at least for binary files.  How
do we represent the change of a binary file?  Do we build some sort of
[context -> data -> context] binary hunk (call it binary-patch(1)) or
do we send the whole new binary file?  I guess the latter doesn't make
the world happy with rather large files but would be way easier and
fit with the SoC timeframe.  BTW, does anybody have a clue how large
binary files are (average with Subversion's users)?

If we store tree and property changes into an encoded hunk, (a) and
possibly (d) disappear again.  One solution would be to store those
changes in plain-text but I'm not sure this is the right way to take.

(c) and (e) are all about fuzzy patching.  It is OK if we (initially)
decide to call patch(1) in Subversion to take advantage of its
contextual-file non-precise patching feature.  But about tree changes,
we'd have to define the amount of fuzzing we want.  I'm doubtful this
could be done in a 2-month period.  This has been discussed elsethread
(Malcolm's redirection, March 29).

Any thoughts?

Cheers,

Charles

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org