[darcs-users] Internals question: How to apply a merger patch?

David Roundy droundy at abridgegame.org
Sun Nov 30 19:00:11 UTC 2003

On Sat, Nov 29, 2003 at 05:23:26PM -0800, Kevin Smith wrote:
> After the 0.9.10 tag, darcs included its first 'merger' patch, in the 
> patch file that begins "Place_1etc_under" (note that's a 1, not an l, 
> since the patch label was "Place /etc under"). I'm trying to figure out 
> how to apply this merger patch to the tree. The merger itself is pretty 
> small:
> merger 0.9 (
> hunk ./Makefile 38
> -       install -m 0644 cgi.conf /etc/darcs/cgi.conf
> +       test -e $(DESTDIR)/etc/darcs/cgi.conf || \
> +           install -m 0644 cgi.conf $(DESTDIR)/etc/darcs/cgi.conf
> hunk ./Makefile 37
> -       install -d $(DESTDIR)/etc/darcs
> -       install -m 0644 cgi.conf /etc/darcs/cgi.conf
> +       install -d $(DESTDIR)/$(PREFIX)/etc/darcs
> +       install -m 0644 cgi.conf $(DESTDIR)/$(PREFIX)/etc/darcs/cgi.conf
> )

First, I'd like to point out that merger 0.9 patches are no longer created,
and unravel is now only used in modifying the working directory in the case
of conflicts (which doesn't affect the repository integrity).  The reason
being that I couldn't get the merger 0.9 code bullet-proof in terms of
always giving the same result regardless of the order of merges.  Nowdays
darcs creates merge 0.0 patches, which are much easier to understand (as
they require only the unwind, not the unravel).

> Looking at the code, I am supposed to invert p1 (because neither of the 
> merged patches are themselves mergers, so merger_undo is just to invert 
> p1), then glump p1 and p2. All of that is then run through 
> sort_coalesce_composite, which due to my poor haskell skills (and 
> currently tired brain) is hard to tell whether it sorts before or after 
> coalescing.

sort_coalesce_composite does a simultaneous sort and coalesce.  The
algorithm is essentially the same as the sort, but every time you would
compare two patchers, you first try to coalesce them.

> Oh, and I may have to invert this patch. I think that happens it's if 
> it's a 'regrem' patch instead of a 'merger' patch.


> Now, the glump ("0.9") seems to call unravel, and if it returns an array 
> of patches we can just join them. But if it returns a 'pss' (?) we 
> either run it through mangle_unravelled_hunks (if it is only hunks), or 
> otherwise just join the head of pss. But I thought pss wasn't an array, 
> so this is confusing.

The relevant code is:

glump "0.9" p1 p2 = case unravel $ Merger True "0.9" p1 p2 of
                    [ps] -> join_patches ps
                    pss -> if only_hunks pss
                           then mangle_unravelled_hunks pss
                           else join_patches $ head pss

ps and pss are just local variables bound to the result of the unravel.  In
this case I'm using the (common?) convention that a 's' suffix indicates a
list (think of ps as the plural of p and pss as the plural of ps).

[ps] means a list containing just one list of patches--i.e. there's only
one solution to the unravel--this happens, for example, if the two
conflicting patches were identical.

The other possibility (pss) means we have either zero (which shouldn't
happen--that would be a bug in unravel) or more than one list of patches.
This is the common case.  If they were all hunk patches, we can join them
together into one big conflict-marker hunk patch.  Otherwise we just have
to choose one of the solutions to try, so we pick the first one.  That's
why sorting was necesary (so the first one would "always" be the same), and
that's also why merger 0.9 is buggy, since sort isn't guaranteed to always
give a list of patches in the same order, which is why darcs now uses
merger 0.0, which is simpler anyways.

> My questions:
> 1. Can you confirm where p1 and p2 came from, and what context they were 
> intended to be applied to before they got merged? I'm guessing that p1 
> was already in your tree when you tried to apply p2 that came from 
> somewhere else.

p1 was already in the tree, and p2 conflicted with it.  Both p1 and p2
have the same context.

> 2. In this specific case, can you describe what would end up in lines 
> 37-39 of the file? It looks like we would roll back the test -e line to 
> be install -m. Then, we would apply a mangled unravelled version of the 
> combination of p1 and p2. But there doesn't seem to be enough 
> information here to reconcile the $(PREFIX) change with the test -e change.

(copying merger again)

> merger 0.9 (
> hunk ./Makefile 38
> -       install -m 0644 cgi.conf /etc/darcs/cgi.conf
> +       test -e $(DESTDIR)/etc/darcs/cgi.conf || \
> +           install -m 0644 cgi.conf $(DESTDIR)/etc/darcs/cgi.conf
> hunk ./Makefile 37
> -       install -d $(DESTDIR)/etc/darcs
> -       install -m 0644 cgi.conf /etc/darcs/cgi.conf
> +       install -d $(DESTDIR)/$(PREFIX)/etc/darcs
> +       install -m 0644 cgi.conf $(DESTDIR)/$(PREFIX)/etc/darcs/cgi.conf
> )

You will get something like the following:

hunk ./Makefile 37
-       install -d $(DESTDIR)/etc/darcs
-       install -m 0644 cgi.conf /etc/darcs/cgi.conf
+v v v v v
+       install -d $(DESTDIR)/etc/darcs
+       test -e $(DESTDIR)/etc/darcs/cgi.conf || \
+           install -m 0644 cgi.conf $(DESTDIR)/etc/darcs/cgi.conf
+       install -d $(DESTDIR)/$(PREFIX)/etc/darcs
+       install -m 0644 cgi.conf $(DESTDIR)/$(PREFIX)/etc/darcs/cgi.conf
+^ ^ ^ ^ ^

The actual patch created won't probably look exactly like this (since this
could be simplified), and I'm not sure of the order of the two
possibilities (it would be determined by a sort), and the number of ** and
v v v etc given above is almost certainly not correct.

> 3. When would a 'regrem' patch be created?

If you take the inverse of a merger patch!  :)  This could happen (but not
be stored) in an unpull or unrecord.  It also could happen *and* be stored,
if you do a rollback of a patch that had conflicts.

> 4. Is the sort step necessary here, or could I just do a coalesce?

Yes, the sort is necesary for backwards compatibility with old merger 0.9
patches (which as I said before are no longer created).

> 5. Would unravel here return an array, or a pss? What is a pss?

It returns a list of lists of patches.

> 6. Is it possible to briefly summarize the algorithm used by 
> mangle_unravelled_hunks?

1) Figure out what the original version of the modified part of the file
was by looking (carefully) at the removed sections of all the hunks.

2) For each set of hunks returned by unravel, apply those hunks to the
original version to give a modified version.  This gives us N modified
versions, one for each hunk sequence output by unravel.

Each patch sequence output by unravel corresponds to a different version
that got merged together.  So if three people make three different changes
to the same line, unravel of the final merger created would give three

3) Sort these N possible versions.

4) Output a (canonized) hunk that 

a) removes the original version of the lines modified.
b) adds a line containing v v v v v
c) adds each of the N versions with a ****** separating them
d) adds a final ^ ^ ^ ^ ^ line to indicate the end of the conflict. 

> 7. What does dbcp stand for?

Debug check patch.  It is debugging code left over from quite a while
back.  I've actually removed it from the latest darcs.
David Roundy

More information about the darcs-users mailing list