Re: whither merge-tree?

Jeff King [off-list ref] writes:

  2. Rip out the weird add/add conflict resolution. This gets rid of the
     buggy code, makes merge-tree more like the rest of git, and I think
     lets us even drop the EMIT_COMMON stuff from xdiff).

That is a nice bonus.

git-merge-resolve (rather, git-merge-one-file) attempts the same
"resolve add/add by taking the common" thing, but it implements it
in quite a different way.

     That lets people keep using merge-tree if they have found it useful
     over the years.

  3. Drop merge-tree completely. This deletes even more code, and helps
     the people in (2) realize that it is utterly unmaintained. :)

I think at this point I am waffling between (2) and (3). I did (1) in a
hope that I could avoid looking deeper into the code at all, but now
that I have, I do not think (2) would be so bad. I'm happy to work up a
patch, but won't bother if we think that (3) is viable.

Yup, between 2 and 3, 2 would certainly be safer, and I agree that
it is not too bad (I have this feeling that add-add conflict is not
the only funny this code has, though).

Let's wait and see how many "please don't"s we hear, perhaps, before
deciding to go 3.?

On Mon, Feb 22, 2016 at 02:45:45PM -0800, Junio C Hamano wrote:

Jeff King [off-list ref] writes:

quoted

  2. Rip out the weird add/add conflict resolution. This gets rid of the
     buggy code, makes merge-tree more like the rest of git, and I think
     lets us even drop the EMIT_COMMON stuff from xdiff).

That is a nice bonus.

git-merge-resolve (rather, git-merge-one-file) attempts the same
"resolve add/add by taking the common" thing, but it implements it
in quite a different way.

I suppose the end result of what merge-tree is trying to do makes sense.
It's definitely a conflict, but we are interested in showing the minimal
content-level conflict. But I think xdl_merge() takes care of that for
us, if we simply feed an empty base. And that is what merge-recursive
does.

I do see that merge-one-file tries create_virtual_base(), which does
some magic with diff. But I'm having trouble conceiving of a case where
that would do something different or useful.

quoted

     That lets people keep using merge-tree if they have found it useful
     over the years.

quoted

  3. Drop merge-tree completely. This deletes even more code, and helps
     the people in (2) realize that it is utterly unmaintained. :)

I think at this point I am waffling between (2) and (3). I did (1) in a
hope that I could avoid looking deeper into the code at all, but now
that I have, I do not think (2) would be so bad. I'm happy to work up a
patch, but won't bother if we think that (3) is viable.

Yup, between 2 and 3, 2 would certainly be safer, and I agree that
it is not too bad (I have this feeling that add-add conflict is not
the only funny this code has, though).

Yeah, I do not mind doing 2, but I have no idea what else is lurking,
and I have very little interest in digging into it.

Let's wait and see how many "please don't"s we hear, perhaps, before
deciding to go 3.?

I'm guessing we won't see much either way. Even Stefan, the original
reporter, does not seem to actively be using it, but rather relaying a
report.

We'd probably get more response by doing 2 for now, then adding a
deprecation warning to the manpage (and possibly the program itself) for
the next release.

-Peff

On Tue, Feb 23, 2016 at 12:02:10AM -0500, Jeff King wrote:

quoted

git-merge-resolve (rather, git-merge-one-file) attempts the same
"resolve add/add by taking the common" thing, but it implements it
in quite a different way.

I suppose the end result of what merge-tree is trying to do makes sense.
It's definitely a conflict, but we are interested in showing the minimal
content-level conflict. But I think xdl_merge() takes care of that for
us, if we simply feed an empty base. And that is what merge-recursive
does.

I do see that merge-one-file tries create_virtual_base(), which does
some magic with diff. But I'm having trouble conceiving of a case where
that would do something different or useful.

I dug this all the way down to your cb93c19 (merge-one-file: use common
as base, instead of emptiness., 2005-11-09), which states that the goal
is just to get:

	common file contents...
	<<<<<< FILENAME
	version from our branch...
	======
	version from their branch...
	>>>>>> .merge_file_XXXXXX
	more common file contents...

But that seems to be what we produce now. Did all of this simply predate
xdl_merge, and the crappy rcs merge did not bother minimizing the diff?
That certainly seems to be the case in my tests.

If that is the case, I think we can get rid of the complex
create_virtual_base(), as well.

-Peff

On Tue, Feb 23, 2016 at 12:14:02AM -0500, Jeff King wrote:

I dug this all the way down to your cb93c19 (merge-one-file: use common
as base, instead of emptiness., 2005-11-09), which states that the goal
is just to get:

	common file contents...
	<<<<<< FILENAME
	version from our branch...
	======
	version from their branch...
	>>>>>> .merge_file_XXXXXX
	more common file contents...

But that seems to be what we produce now. Did all of this simply predate
xdl_merge, and the crappy rcs merge did not bother minimizing the diff?
That certainly seems to be the case in my tests.

If that is the case, I think we can get rid of the complex
create_virtual_base(), as well.

So here is what I would propose:

  [1/3]: merge-one-file: use empty blob for add/add base
  [2/3]: merge-tree: drop generate_common strategy
  [3/3]: xdiff: drop XDL_EMIT_COMMON

I briefly wondered if there were any bugs in merge-one-file around this
"no newline at end of file" issue. But there shouldn't be. It generates
the common file by applying the diff to the first file with "--no-add",
which should do the right thing, I think.

I stopped short of dropping the create_virtual_base function in the
first patch, for reasons explained there. But if we were to do so, I
suspect we could deprecated and eventually drop "apply --no-add", too.

-Peff

When we see an add/add conflict on a file, we generate the
conflicted content by doing a 3-way merge with a "virtual"
base consisting of the common lines of the two sides. This
strategy dates back to cb93c19 (merge-one-file: use common
as base, instead of emptiness., 2005-11-09).

Back then, the next step was to call rcs merge to generate
the 3-way conflicts. Using the virtual base produced much
better results, as rcs merge does not attempt to minimize
the hunks. As a result, you'd get a conflict with the
entirety of the files on either side.

Since then, though, we've switched to using git-merge-file,
which uses xdiff's "zealous" merge. This will find the
minimal hunks even with just the simple, empty base.

Let's switch to using that empty base. It's simpler, more
efficient, and reduces our dependencies (we no longer need a
working diff binary). It's also how the merge-recursive
strategy handles this same case.

We can almost get rid of git-sh-setup's create_virtual_base,
but we don't here, for two reasons:

  1. The functions in git-sh-setup are part of our public
     interface, so it's possible somebody is depending on
     it. We'd at least need to deprecate it first.

  2. It's also used by mergetool's p4merge driver. It's
     unknown whether its 3-way merge is as capable as git's;
     if not, then it is benefiting from the function.

Signed-off-by: Jeff King <redacted>
---
 git-merge-one-file.sh | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/git-merge-one-file.sh b/git-merge-one-file.sh
index cdc02af..424b034 100755
--- a/git-merge-one-file.sh
+++ b/git-merge-one-file.sh

@@ -120,8 +120,7 @@ case "${1:-.}${2:-.}${3:-.}" in
 	case "$1" in
 	'')
 		echo "Added $4 in both, but differently."
-		orig=$(git-unpack-file $2)
-		create_virtual_base "$orig" "$src2"
+		orig=$(git-unpack-file e69de29bb2d1d6434b8b29ae775ad8c2e48c5391)
 		;;
 	*)
 		echo "Auto-merging $4"

-- 
2.7.2.645.g4e1306c

When merge_blobs sees an add/add conflict, it tries to
create a virtual base object for the 3-way merge that
consists of the common lines of each file. It inherited this
strategy from merge-one-file in 0c79938 (Improved three-way
blob merging code, 2006-06-28), and the point is to minimize
the size of the conflict hunks. That commit talks about "if
libxdiff were to ever grow a compatible three-way merge, it
could probably be directly plugged in".

That has long since happened. So as with merge-one-file in
the previous commit, this extra step is no longer necessary.
Our 3-way merge code is smart enough to do the minimizing
itself if we simply feed it an empty base, which is what the
more modern merge-recursive strategy already does.

Not only does this let us drop some code, but it removes an
overflow bug in generate_common_file(). We allocate a buffer
as large as the smallest of the two blobs, under the
assumption that there cannot be more common content than
what is in the smaller blob. However, xdiff may feed us
more: if neither file ends in a newline, it feeds us the
"\nNo newline at end of file" marker as common content, and
we write it into the output. If the differences between the
files are small than that string, we overflow the output
buffer.  This patch solves it by simply dropping the buggy
code entirely.

Signed-off-by: Jeff King <redacted>
---
 merge-blobs.c | 38 ++------------------------------------
 1 file changed, 2 insertions(+), 36 deletions(-)

diff --git a/merge-blobs.c b/merge-blobs.c
index ddca601..9b6eac2 100644
--- a/merge-blobs.c
+++ b/merge-blobs.c

@@ -48,40 +48,6 @@ static void *three_way_filemerge(const char *path, mmfile_t *base, mmfile_t *our
 	return res.ptr;
 }
 
-static int common_outf(void *priv_, mmbuffer_t *mb, int nbuf)
-{
-	int i;
-	mmfile_t *dst = priv_;
-
-	for (i = 0; i < nbuf; i++) {
-		memcpy(dst->ptr + dst->size, mb[i].ptr, mb[i].size);
-		dst->size += mb[i].size;
-	}
-	return 0;
-}
-
-static int generate_common_file(mmfile_t *res, mmfile_t *f1, mmfile_t *f2)
-{
-	unsigned long size = f1->size < f2->size ? f1->size : f2->size;
-	void *ptr = xmalloc(size);
-	xpparam_t xpp;
-	xdemitconf_t xecfg;
-	xdemitcb_t ecb;
-
-	memset(&xpp, 0, sizeof(xpp));
-	xpp.flags = 0;
-	memset(&xecfg, 0, sizeof(xecfg));
-	xecfg.ctxlen = 3;
-	xecfg.flags = XDL_EMIT_COMMON;
-	ecb.outf = common_outf;
-
-	res->ptr = ptr;
-	res->size = 0;
-
-	ecb.priv = res;
-	return xdi_diff(f1, f2, &xpp, &xecfg, &ecb);
-}
-
 void *merge_blobs(const char *path, struct blob *base, struct blob *our, struct blob *their, unsigned long *size)
 {
 	void *res = NULL;

@@ -112,8 +78,8 @@ void *merge_blobs(const char *path, struct blob *base, struct blob *our, struct
 		if (fill_mmfile_blob(&common, base) < 0)
 			goto out_free_f2_f1;
 	} else {
-		if (generate_common_file(&common, &f1, &f2) < 0)
-			goto out_free_f2_f1;
+		common.ptr = xstrdup("");
+		common.size = 0;
 	}
 	res = three_way_filemerge(path, &common, &f1, &f2, size);
 	free_mmfile(&common);

-- 
2.7.2.645.g4e1306c

There are no more callers that use this mode, and none
likely to be added (as our xdl_merge() eliminates the common
use of it for generating 3-way merge bases).

This is effectively a revert of a9ed376 (xdiff: generate
"anti-diffs" aka what is common to two files, 2006-06-28),
though of course trying to revert that ancient commit
directly produces many textual conflicts.

Signed-off-by: Jeff King <redacted>
---
 xdiff/xdiff.h |  1 -
 xdiff/xemit.c | 18 ------------------
 2 files changed, 19 deletions(-)

diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h
index c033991..4fb7e79 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h

@@ -42,7 +42,6 @@ extern "C" {
 #define XDF_IGNORE_BLANK_LINES (1 << 7)
 
 #define XDL_EMIT_FUNCNAMES (1 << 0)
-#define XDL_EMIT_COMMON (1 << 1)
 #define XDL_EMIT_FUNCCONTEXT (1 << 2)
 
 #define XDL_MMB_READONLY (1 << 0)

diff --git a/xdiff/xemit.c b/xdiff/xemit.c
index 4266ada..993724b 100644
--- a/xdiff/xemit.c
+++ b/xdiff/xemit.c

@@ -120,21 +120,6 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)
 	return -1;
 }
 
-static int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
-                           xdemitconf_t const *xecfg) {
-	xdfile_t *xdf = &xe->xdf2;
-	const char *rchg = xdf->rchg;
-	long ix;
-
-	for (ix = 0; ix < xdf->nrec; ix++) {
-		if (rchg[ix])
-			continue;
-		if (xdl_emit_record(xdf, ix, "", ecb))
-			return -1;
-	}
-	return 0;
-}
-
 struct func_line {
 	long len;
 	char buf[80];

@@ -170,9 +155,6 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
 	long funclineprev = -1;
 	struct func_line func_line = { 0 };
 
-	if (xecfg->flags & XDL_EMIT_COMMON)
-		return xdl_emit_common(xe, xscr, ecb, xecfg);
-
 	for (xch = xscr; xch; xch = xche->next) {
 		xche = xdl_get_hunk(&xch, xecfg);
 		if (!xch)

-- 
2.7.2.645.g4e1306c

On 23.02.2016 at 06:02 Jeff King wrote:

quoted

Let's wait and see how many "please don't"s we hear, perhaps, before
deciding to go 3.?

I'm guessing we won't see much either way. Even Stefan, the original
reporter, does not seem to actively be using it, but rather relaying a
report.

I _am_ actively using it. Maybe I was unclear on that topic. I'm in 
favour of keeping it, because this means I don't have to rewrite Chris' 
Code in order to be able to use the Python library that uses merge-tree 
(Acidfs). But as a sensible human being I want what's best in the long 
run. I leave that up to you as I have no way of assessing that.

So that's a "please don't" leave the code as-is but provide a 
(transitional) solution that fixes the reported bug and has the best 
chances of not causing any more headaches :)

We'd probably get more response by doing 2 for now, then adding a
deprecation warning to the manpage (and possibly the program itself) for
the next release.

A deprecation warning would be very welcome.

Thanks,
Stefan

Hi Peff,

On Tue, 23 Feb 2016, Jeff King wrote:

On Mon, Feb 22, 2016 at 02:45:45PM -0800, Junio C Hamano wrote:

quoted

Jeff King [off-list ref] writes:

quoted

  3. Drop merge-tree completely. This deletes even more code, and
  helps the people in (2) realize that it is utterly unmaintained.
  :)

Let's wait and see how many "please don't"s we hear, perhaps, before
deciding to go 3.?

I'm guessing we won't see much either way.

We could encourage more voices by issuing a warning when merge-tree is
called, e.g.:

	warning: merge-tree is unsupported (please contact
		 git@vger.kernel.org if you use it actively)

Ciao,
Dscho

On Tue, Feb 23, 2016 at 7:36 PM, Johannes Schindelin
[off-list ref] wrote:

We could encourage more voices by issuing a warning when merge-tree is
called, e.g.:

        warning: merge-tree is unsupported (please contact
                 git@vger.kernel.org if you use it actively)

Maybe motivate them to reach git@vger by s/use it actively/do not want it gone/.
-- 
Duy

On di, 2016-02-23 at 10:49 +0100, Stefan Frühwirth wrote:

On 23.02.2016 at 06:02 Jeff King wrote:

quoted

quoted

Let's wait and see how many "please don't"s we hear, perhaps,
before
deciding to go 3.?

I'm guessing we won't see much either way. Even Stefan, the
original
reporter, does not seem to actively be using it, but rather
relaying a
report.

I _am_ actively using it. Maybe I was unclear on that topic. I'm in 
favour of keeping it, because this means I don't have to rewrite
Chris' 
Code in order to be able to use the Python library that uses merge-
tree 
(Acidfs). But as a sensible human being I want what's best in the
long 
run. I leave that up to you as I have no way of assessing that.

So that's a "please don't" leave the code as-is but provide a 
(transitional) solution that fixes the reported bug and has the best 
chances of not causing any more headaches :)

I am also actively using it. It's the only way (I know of) of trying to
preview a merge result without attempting the actual merge, which is
useful in some of my scripts.

-- 
Dennis Kaarsemaker
www.kaarsemaker.net

On Wed, Feb 24, 2016 at 08:28:59AM +0100, Dennis Kaarsemaker wrote:

quoted

So that's a "please don't" leave the code as-is but provide a 
(transitional) solution that fixes the reported bug and has the best 
chances of not causing any more headaches :)

I am also actively using it. It's the only way (I know of) of trying to
preview a merge result without attempting the actual merge, which is
useful in some of my scripts.

OK. I guess we can live with the series I posted earlier (to simplify
the add/add behavior and fix the overflow), and leave it in place.

I _do_ think it's a useful concept, and there isn't something quite like
it in git right now. At one point I contemplated teaching unpack-trees
to do the content-level merges too, so you could do this via read-tree,
but I didn't ever polish it[1]. So I am sympathetic to the goal, and
there's not another way to do it as efficiently.

And now I feel like both of you have been warned that the code might be
crufty. :)

I'm not sure what we should do about warning others.  Since people are
using it, I don't want to put a deprecation warning. It's not "this will
be removed in the next version" anymore, but "watch out, this might be
crufty". I guess that can go in the manpage, but I'm not quite sure how
to word it.

-Peff

[1] It looks like my patch has been collecting dust since 2011:

      git://github.com/peff/git.git jk/read-tree-content-merge-wip

    It's been rebased along with all of my other topics since then, but
    otherwise I have no clue if it works or even compiles (it's not part
    of my day-to-day build). Anyone is welcome to use it as a base if
    they want to pursue it.

On Tue, Feb 23, 2016 at 10:49:34AM +0100, Stefan Frühwirth wrote:

On 23.02.2016 at 06:02 Jeff King wrote:

quoted

quoted

Let's wait and see how many "please don't"s we hear, perhaps, before
deciding to go 3.?

I'm guessing we won't see much either way. Even Stefan, the original
reporter, does not seem to actively be using it, but rather relaying a
report.

I _am_ actively using it. Maybe I was unclear on that topic. I'm in favour
of keeping it, because this means I don't have to rewrite Chris' Code in
order to be able to use the Python library that uses merge-tree (Acidfs).
But as a sensible human being I want what's best in the long run. I leave
that up to you as I have no way of assessing that.

Ah, sorry for the confusion. I had thought you were just relaying bugs
on behalf of acidfs folks, but it makes sense that you are using it
indirectly through the library.

So that's a "please don't" leave the code as-is but provide a (transitional)
solution that fixes the reported bug and has the best chances of not causing
any more headaches :)

I think the series I posted does what you want, then, and we can stop
short of deprecating for now.

-Peff