[darcs-users] The theory of patches

Antonio Regidor García a_regidor at yahoo.es
Mon Jun 6 03:59:28 UTC 2005


 --- "Stephen J. Turnbull" <stephen at xemacs.org> escribió: 
>     Antonio> No, the directory tree is a repository, and patches are
>     Antonio> changes to this repository. How patches arrive to the
>     Antonio> repository (as tarfiles, messages, ...) is irrelevant for
>     Antonio> the theory I described.
> 
> It's not delivery I'm talking about, it's representation.  You can
> represent all the directory information that darcs cares about with
> ls -alR.  So you can represent file deletions and renames as hunk
> patches to the listing.  This simplifies the theory because we only
> need to worry about string manipulations, now.

Ok.

> On the other hand, one difference between a hunk patch and a token
> replace patch is that a hunk patch can only result in a bounded number
> of changes, while a TR patch clearly may result in an arbitrarily
> large number of changes.  So there is no representation where hunk
> patches can replace TR patches.  Or vice versa.

A general hunk patch can't replace a token replace patch (and vice versa), but a concrete hunk
patch can replace a concrete token replace patch (and vice versa).

>     Antonio> If concrete patches are always succesful, this makes
>     Antonio> things more regular.
> 
> Hold it there a second!  Your notation for concrete patches is (S,T)
> where S and T are trees.  You also said that a concrete patch has
> "unitary" domain, which I took to mean the singleton {S}.  Ie, it's
> "diff -urN S T" (plus some stuff for directory manipulations).  Such a
> patch is _always_ successful because it can only be applied to S.
> (Ie, it's the arrow from S to T.)
> 
> Is that you mean by a "concrete patch"?

A concrete patch is not "diff -urN S T" and stuff for directory manipulations, but the pair formed
by the original tree and the modified tree. This is only a theorical representation, how it is
actually encoded is an implementation detail. It's the arrow from {S} to {T}. I didn't make any
assumptions on what a directory tree is for the theorical definitions, since this doesn't matter
for the theorical proofs and it changes from an OS to other. But to define hunk and token replace
patches I did assume that the files contain text, can be found by path names, etc.

>     >> I don't think it's appropriate in general.  Token replace is a
>     >> good example.  Suppose that you've discovered that as far as
>     >> users are concerned, ERR_A and ERR_B are semantically
>     >> indistinguishable (ie, they indicate the same kind of bug, but
>     >> the context is a little different), but ERR_B is rarely emitted
>     >> in practice (even though it may occur in many places in the
>     >> code).  Then a hunk deletion of the place where ERR_B is mapped
>     >> to an actual message plus token_replace(ERR_B,ERR_A) is a very
>     >> plausible description of the desired patch.
> 
>     Antonio> I don't understand this. Why do you need a hunk replace?
> 
> Because you have a switch like this:
> 
>     switch (error_code) {
>     case ERR_A:
>         fprintf (stderr, "Encountered error A\n");
>         break;
>     case ERR_B:
>         fprintf (stderr, "Encountered error B\n");
>         break;
>     default:
>         fprintf (stderr, "Well, excuse me!!\n");
>         exit (-42);
>     }
> 
> And after the TR you need to get rid of the second "case ERR_A" clause.

Ok. Anyway, I see the need for applying TR(A,B) to files that contain A and B instances. And also
for the sort patch. This brokens invertibility for general patches and a different approach is
needed :(

> Sure.  Pick a file in R.  Rename it, and call the resulting tree R'.
> Now the concrete patches (R,S) and (S,T) will commute via P = {(R,S)
> (R',T)} and Q = {(S,T),(R,R')}.  But if (S,T) is a hunk patch that
> only affects some other file, there's no way we can say they have "the
> same effect".

Yes, the general patches are too general :( Probably we need invertibility only for concrete
patches but not for general patches. I will think about this more carefully.

Best regards,

Antonio Regidor García


		
______________________________________________ 
Renovamos el Correo Yahoo! 
Nuevos servicios, más seguridad 
http://correo.yahoo.es




More information about the darcs-users mailing list