On Sun, 16 Sep 2012 01:37:15 -0700, AntC <anthony_clay...@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
_______________________________________________
darcs-users mailing list
darcs-users@darcs.net
http://lists.osuosl.org/mailman/listinfo/darcs-users
