[darcs-users] Re: definition of "depends on"?

[Jason Dagit]

On 4/28/07, Adam Megacz <megacz at cs.berkeley.edu> wrote:
>
> "Jason Dagit" <dagit at codersbase.com> writes:
> > I think the only precise statement is to learn about darcs patch
> > theory.  You can find a section on this subject in the darcs manual:
> > http://www.darcs.net/manual/node8.html
>
> Oh, thanks.  I read this stuff a while back when I started using
> darcs, but I forgot that it actually defined what the "context" was.
>
> So, let's give this another try.
>
> The theory of patches says that "when two patches fail to commute, it
> is said that the second patch depends on the first".  Earlier it says
> that "the context of a patch consists of the set of patches that
> precede it".
>
> Using the right-to-left (group-like?) notation, if I have a repository
> like this:
>
>     P_3 P_2 P_1
>
> We would say that "P_2 is in the context of P_3, and therefore P_3
> depends on P_2".  However, if P_3 and P_2 commute, then I can
> transform the repository to an equivalent state:
>
>     P'_2 P'_3 P_1
>
> In which the "changes caused by" P_3 (that is, P'_3) do not contain
> P_2 or P'_2 in their context.  So we can say that "it is possible to
> re-order the repository so that the changes embodied in P_3 do not
> depend on the changes embodied in P_2".
>
> So it would seem that commuting patches changes what they depend on.

When commutation is possible the concrete representation of the patch
and the context of the patch can be changed.  As an example of the
concrete representation changing, when you reorder patches maybe the
line numbers need adjusted in a hunk patch.  And you pointed out the
way in which the context changes.  I'm about 90% sure this idea is
used by darcs together with a least common subsequence algorithm to
find the "minimal" context of patches.  I say minimal, because if I'm
remembering all this correctly the particular LCS algorithm used finds
a small but not necessarily smallest common subsequence.  I may be
completely off my rocker or thinking about the diff algorithm.  Can
anyone else comment here?

> If everything up to this point is correct, then my question is this:
> if two patches commute, will darcs always be able to unpull one
> without unpulling the other?

I don't know enough about unpull to comment on it.  But, this should
be true of pull (when two patches commute the LCS algorithm should
figure this out and not find that they depend on each other).

> Phrased another way, "can I get darcs to use its ability to commute
> patches to break dependencies?"  I realize this is not always
> possible, but it seems like there are situations where this *is*
> possible, but darcs does not attempt to re-order the patches (or at
> least I can't figure out how to ask it to do that).

This should be automatic and on demand.  Otherwise, darcs optimize
reorders patches, but I've not worked through enough of darcs to
understand what it does or if it applies here.  I seem to recall
hearing that it just reorders the way they are stored in the inventory
to a more "canonical" order.

> One other question: is there ever a case where a patch cannot be
> commuted past a pair of other patches, but the combination of the pair
> does commute?  In other words, is there a case where
>
>     A B C <-/-> B' A' C <-/-> B' C' A''
>
> (where one of the two <-/->'s fails) yet
>
>     A (B C) <--> (B C)' A'
>
> (where <--> indicates a successful commute)

The way things work now, if this were possible I don't think darcs
would discover it because commutation is always a pair-wise operation
(and that's how patch theory defines it).  Perhaps if someone worked
out new commutation rules this would be possible.

Jason