I had a file with line x in it.  In one repository, I added several lines after
line x.  In another repository I changed line x.  When I pulled the change of
line x, the added lines were considered a conflict.  This may be a tricky
problem, but it just wasn't what I expected.

Thank you.
-Amber

\   L. Amber Wilcox-O'Hearn * http://www.cs.toronto.edu/~amber/   /
-\  Graduate student * Computational Linguistics Research Group  /-
--\   Department of Computer Science * University of Toronto    /--

On Mon, Feb 11, 2008 at 07:25:57PM -0000, L. Amber Wilcox-O'Hearn wrote:
> I had a file with line x in it.  In one repository, I added several lines after
> line x.  In another repository I changed line x.  When I pulled the change of
> line x, the added lines were considered a conflict.  This may be a tricky
> problem, but it just wasn't what I expected.

In a perfect world the two patches 'line x' and 'lines after x'
could be unpulled and pulled arbitrarily, so that the file could
contain none, one, the other or both of them, with the only
restriction being that if you have both they are always in the
same (correct) order.

The current hunk patch format (both darcs1 and darcs2) doesn't
have a way to store this order dependency, so what darcs does
instead is to over-react and treat it as a normal (full)
dependency, i.e., you can't unpull the 'line x' patch without
also unpulling the 'lines after x' patch. This (unintuitive)
dependency is also what's causing (by the mathematics of patch
theory) the unexpected conflict.

It would probably be a bit complicated to fix this, although I
think it would be worth it, considering what's known as The
Changelog Problem.

[The following is my emptying the brain in the bug tracker, and
not so much a reply...]

Without much deeper thought, one way could be to add / remove
patch id:s to / from a "preceding list" when commuting adjacent
hunks:

  G A B  <=>  G (B' [preceding: a]) A'

If A was later pulled from GA we would commute:

  (invB' [preceding: a]) A  <=>  A' invB''

and hopefully patch a would end up with the right line numbers.

If we instead pull patch x, with the same line number as patch
b, but not previously commuted past patch b, and thus not in b's
preceding list, we'd get:

  (invB' [preceding: a]) X  =>  b and x conflict

Let's add another patch c before pulling, that changes lines
from both patch g and patch b in a way that spans over the
"missing" lines of patch a:

  G (B' [preceding: a]) C

If we now pull patch a back we'd have to commute:

  invC (invB' [preceding: a) A  <=>  invC A' invB''  =>  c and a conflict

Hm, I guess A' should have the right line numbers, and the
conflict should be as expected?

But it feels awkward to record context _inside_ the patches...

I'm re-casting this a wishlist item, but someone else is welcome to re-declare
it as a bug.

I was a bit tired when I emptied my brain last night.

Darcs-2 format deals with primitive patches and couldn't use
id:s for named patches, so that idea won't work, I think. I also
tried with an idea to leave dark matter patches (or maybe darc
matter, he) behind, like A B <=> \A B' A', but that didn't seam
to lead anywhere.

Also, to be fair to The Changelog Problem, that problem is also,
or perhaps even more so, about the conflicts you get when
several distributed contributers simultaneously add a
description of their respective changes to the end (or
beginning) of the same Changelog file, causing a multiple
conflict in the master repo. But the only way with darcs to
solve that part of the problem, as I can see, is a special
changelog patch that orders parallel adjacent patches by some
global unique identifier.

Would a new patch type be a better way of dealing with this?

On Mon, Feb 11, 2008 at 11:30:32PM +0000, tommy wrote:

> In a perfect world the two patches 'line x' and 'lines after x'
> could be unpulled and pulled arbitrarily, so that the file could
> contain none, one, the other or both of them, with the only
> restriction being that if you have both they are always in the
> same (correct) order.

I don't understand why the patches need to be ordered.

Given line x, I can either modify it to A, then insert B after it, or
first insert B after it, then modify x to A. Either way, the result is
the same: AB.

Now, if there were two patches, one adding C after x, the other adding
D after x, they would need to be ordered, or I could end up with either
xCD or xDC. And if recorded in isolation, they would conflict.

But in the first case, there is no way to end up with BA instead of AB.

Am I seeing things too simply, or is this perhaps just an implementation 
problem?
-- 
Vincent Zweije <zweije@xs4all.nl>    | "If you're flamed in a group you
<http://www.xs4all.nl/~zweije/>      | don't read, does anybody get burnt?"
[Xhost should be taken out and shot] |            -- Paul Tomblin on a.s.r.

Ganesh explained the ChangeLog problem at 
http://irclog.perlgeek.de/darcs/2010-09-19#i_2842608 (stop at 13:01)

Why does "lines after x" depend on "line x"?  Let's simplify this to be 
both one-liners on an empty file.

It's useful to understand that hunks in the current Darcs are associated 
with line numbers. So the hunk patches here would be "+line x" on line 1 
and "+line after x" on line 2.

If we were to allow them to commute, it would be possible to have two 
parallel repositories, with "+line x" and "+line after x", both of which 
on line 1 (!).  The fact that these patches would both touch line 1 
means we'll have introduced an ambiguity.  Which one goes first?  You 
could get alternatively

line x
line after x

or

line after x
line x

Hope I've got that right!

On Thu, Sep 23, 2010 at 04:51:22PM +0000, Eric Kow wrote:

> Why does "lines after x" depend on "line x"?  Let's simplify
> this to be both one-liners on an empty file.

This issue, 674, as submitted by Amber, is *not* the changelog
problem.

The changelog problem is about two patches that only insert
lines at the same position. Since they can be applied in
either order, this causes an ambiguity which results in the
two patches conflicting.

Issue 674 is about one patch *inserting* a line after a given
line, and the other patch *modifying* the given line.

So, given line 1 is currently "line x", there are two patches
depending on it:

 A: at line 1, remove "line x" and insert "line x-prime"

 B: at line 2, insert "line y"

Ordering B after A as B' gives:

 B': at line 2, insert "line y"

Ordering A after B as A' gives:

 A': at line 1, remove "line x" and insert "line x-prime"

In either case, the end result is the same: two lines being
"line x-prime" followed by "line y".

In this case, A'=A and B'=B, but that's not true in
general. For instance, if B inserts a line before "line x",
the line number of A' becomes 2, but the commute still holds.

Vincent.
-- 
WCC - Smart Search & Match
NL  +31 30 7503222
vzweije@wcc-group.com
www.wcc-group.com