[darcs-users] questions on patch theory

David Roundy droundy at abridgegame.org
Sun Sep 14 00:40:41 UTC 2003


On Sat, Sep 13, 2003 at 01:19:16PM -0400, Mirian Crzig Lennox wrote:
> droundy at abridgegame.org (David Roundy) writes:
> > This brings up one other problem, which is that I have two different
> > meanings for the term patch.  One is the logical change defined by the
> > patch.  The other is the "representation" of the patch.  So in a commute
> > 
> > AB <-> B'A'
> > 
> > A' is the same patch as A (in the first sense), but its representation is
> > different, because its representation is with respect to a context that is
> > lacking B.  This second issue is more serious than the first, since in the
> > first case the two definitions are equivalent, but certainly the
> > representation of a patch mustn't be mistaken for the patch itself, and I
> > suspect that at places I refer to the representation of a patch as a
> > "patch."
> 
> Thank you for the clarification.  I suspect that much of my confusion
> has arisen from an incomplete understanding of the distinction between
> a patch and its representation.
> 
> Most of the time when you use the term "patch" in your theory of
> patches, you do appear to mean the representation rather than the
> logical change.  In fact, the only time when you appear to use "patch"
> at all in the other sense is when justifying why commutation works.  I
> imagine that a lot of people get tripped up by this; I certainly did.

The other time that I take patch to mean the patch itself rather than its
representation is when I say that a tree (or equivalently the context of a
patch--that is the context of the representation of a patch...) is defined
by a set of patches, it must either be an unordered set of patches, or an
ordered set of representations of patches.  It is key to the workings of
darcs that the context is an unordered set of patches, since otherwise
merges of two similar but differently ordered repositories would tend
towards being O(n^2) where n is the number of patches in the two
repositories.  That would be a bad thing.  As it is, even in the worst case
scenario the merge is only O(n).

> In my opinion, it would be much more clear to have "patch" mean
> exclusively the representation, and rely on the <-> operator to convey
> the notion of semantic equality.  If necessary, coin a new term such
> as "change", "logical change", or "semantic change" to mean "what the
> patch represents".  Or perhaps, "metapatch", to coin an entirely new
> word but keep the (logically abstracted) connection to patches
> explicit.
> 
> So, in your illustration above, I would say that A and A' are separate
> and distinct patches.  However, in their respective contexts, they
> describe the same change (or semantic change, or metapatch, etc.).
> 
> What do you think?

Hmmmm.  That's an appealing idea.  I hadn't been able to figure out a
terminology I was really happy with for the distinction between a patch and
its representation.  Now that I think about it, calling the unchanging
thing a change and its representation a patch is pretty intuitive.
"Patches A and A' represent the same change" is a statement that is pretty
clear, and would only become more clear with a good definition of what a
change is and what a patch is...  I think I'll make this change whenever I
get around to revising my theory of patches appendix.  Thanks for the
suggestion!  :)

> > I think what you are calling precedence I would call dependency (assuming
> > it is a property of patches themselves rather than the representations of
> > patches), and I think to define it properly you need to mention involve
> > commutation, more specifically, its failure.
> 
> What I was aiming at with precedence was actually an extension of the
> dependence concept; you can tell me if it's useful or not.  Obviously,
> if two patches don't commute, then their precedence relationship is
> clear.  But even if they do commute, there may be a preferred order of
> composition.  If patch A adds several lines near to the bottom of a
> file, and patch B adds several lines to the top, then patch B can be
> applied either before or after A, but A cannot be applied after B
> without resort to Theorem 2.  Thus, I would say that patch A implies a
> precedence over patch B.
> 
> Again, you can let me know if this is a useful concept; it may be
> superfluous given the way merge conflict resolution works.

Well, I think it becomes redundant if you simply modify it so that the
precedence relationship becomes a relationship between a patch and a
change.  A patch is preceded by every change that is in its context.  If
you like, you could defined it in terms of patches by saying that a patch
is preceded by every patch that represent a change in its context, and
whose context is a subset of the first patch's context.  I think with this
second (and somewhat more awkward) definition, your transitivity
relationships and so on would be true.
-- 
David Roundy
http://www.abridgegame.org




More information about the darcs-users mailing list