[darcs-users] darcs conflicts/dependencies -- is patch theory the place to start?

Kevin Quick quick at sparq.org
Sun Sep 16 18:26:25 UTC 2012


On Sun, 16 Sep 2012 01:37:15 -0700, AntC <anthony_clayden at clear.net.nz>  
wrote:

> On reflection, there's another possibility: the test for observational
> equivalence could be richer. Take these scenarios:
> - branch A has <addfile F, hunk change F, move/rename F to G>
>   (I assume git could detect this as a move because the content is the  
> same.)
> - branches B and C each start by pulling the addfile from A.
> - then branch B pulls the move F to G.
> - but C removes F, adds G -- note both are empty files
> - each of B and C then pull the hunk change
> Here's the observational non-equivalence:
> - in B I expect the hunk change applies to G, no difficulty
> - in C I suspect the hunk change will fail with a dependency on F
>   (or will want to pull addfile F again)

I believe the effort to determine equivalence becomes exponentially hard.

To explain that statement, let me first talk about my understanding of how  
darcs implements this (with the repeated caveat that it has been a while  
since I've been working with the innards of darcs, so I welcome any  
corrections by current darcs contributors)---apologies in advance for the  
didacticism.

To simplify the discussion, here's a condensed representation of the above:

A:  a--c--r
B:  a--r
C:  a--d--n

Considering Branch (repo) B in step 5 above, pulling the hunk change from  
A would cause darcs to perform the following steps:

1. Find the common patches in A and B:  a--r
2. Commute those common patches to before any other patches
       A: a--r'--c'
       B: a--r      (unchanged)
    At this point, c' is now a Hunk Change in file G.
3. Starting with the requested patch, find all dependencies back to the  
common point.  In this case, it's trivial because only c' is considered.
4. Attempt to apply c' to the *working directory*/tip of B.  The c' patch  
specifies hunk location, original contents, and new contents (two  
preconditions and a post-condition).  The preconditions are compared to  
the CWD{B} and it is found that they match, so c' can be applied without  
conflict.
End result: matches your expectation.

Now consider Branch (repo) C doing the same operation:

1. Find common: a
2. Commute common before unique.  In this case both repos considered are  
unchanged because they trivially share only the first patch.
3. Find dependencies of requested patch c in A.  Again, this is trivial  
because c immediately follows a.
4. Attempt to apply patch c.  This fails because of patch d, so there is  
no file F to apply the change to (precondition "original contents" fails).
End result: again matches your expectation (depending on what you mean by  
"dependency" on F).

Now however, consider what would need to occur to pull c into C.  Under  
the above operations, darcs would need to determine that "r" is equivalent  
to "d--n"  (is it??).  This would be more complicated given that there  
could be other patches between d--n, and nearly impossible if d or n  
included other changes (e.g. n also adds File Y).  This also requires  
darcs to consider r which is a future of c and not a proper dependency.   
Again, this could be complicated by other patches between c--r or other  
components of r.  This is what I mean by the exponential difficulty of  
finding equivalence: all combinations of pasts in C must be compared to  
all combinations of futures of c in A.  And even at that point the  
equivalence of "r" to "d--n" is still subjective.

> Possibly we could expose the non-equivalence to the programmer even  
> before
> pulling the hunk change, by the VCS linking B's file G to F to branch A,  
> but
> not linking C's file G.

Explicit dependencies like that (which are normally impossible or at best  
over-restrictive in darcs because it forces explicit repo relationships)  
tend to resolve the "r" to "d--n" question, but even if they are deemed  
equivalent you still need to determine when r should be part of the pull  
operation, which imports the combinatoric explosion above.  The only  
practical possibility I can see is that an explicit declaration that r ==  
d--n by the user then identifies those as common patches in my step 2,  
resulting in consideration of:
       A:  a----r'----c'
       C:  a--{d--n}
which then becomes a simple pull of c' to C.  The issue with this is the  
correctness of the user's identification of patch set equivalencies:
    * did they get it right?
    * what if n contains other changes?  should it be possible to split n  
into n1--n2 where n1 contains the "Addfile G" and n2 is the other stuff?
    * what if n (or n2!) is part of another, separate equivalency  
declaration made by the user?

I would love it if these were tractible problems because it would give us  
much more effective VCS capabilities, but it's starting to look N-P hard  
to me.

> I think the meaning of "same effect" must be about an equivalence in all
> contexts (that meet pre-conditions). (I appreciate this doesn't help much
> without a precise definition of what's significant about contexts or  
> what pre-
> conditions look like.)

I agree.

-- 
-KQ


More information about the darcs-users mailing list