Strange merge failure (would be overwritten by merge / cannot merge)

Strange merge failure (would be overwritten by merge / cannot merge)

[Christoph Haas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Dear list,

I'm struggling with a pretty simple Git repository where I maintain one
of my Debian packages. It has two branches:

 - upstream (contains the unaltered original software unpacked from
   a .tar.gz)
 - master (derived from upstream plus Debian specific changes)

Now I imported a new upstream version into the upstream branch. And then
tried to merge the 'upstream' branch into the 'master' branch to work on
it. And suddenly I get this error:

   error: Entry 'cream-abbr-eng.vim' would be overwritten by merge.
   Cannot merge.

So it looks like the 'cream-abbr-eng.vim' file has been altered. And it
contains some non-ASCII characters (it's a VIM script file) so perhaps
automatic merging fails. But can't I just tell Git to screw my file in
the 'master' branch and just overwrite my file? No merge strategy helped
me accomplish that.

To reproduce my problem:

  $> git clone git://git.workaround.org/cream
  $> cd cream
  $> git merge origin/upstream
  error: Entry 'cream-abbr-eng.vim' would be overwritten by merge.
  Cannot merge.
  fatal: merging of trees 70008c82f82a7985531aa2d039c03fdf944ea267 and
  78d3a35e300434d6369424dd873bb587beacfaa4 failed

Help welcome. I'm no Git guru and totally at a loss here. As a last
resort I would start from scratch losing all of my Git history.

Kindly
 Christoph

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkqheHQACgkQCV53xXnMZYZSaQCdF4JovwKUx1FIOq82+joGUIlq
a7UAoIoC2mm2L6Pv7MvZGzOIRNgktb2B
=pklM
-----END PGP SIGNATURE-----

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[David Aguilar]

On Fri, Sep 04, 2009 at 10:28:36PM +0200, Christoph Haas wrote:
> 
> Now I imported a new upstream version into the upstream branch. And then
> tried to merge the 'upstream' branch into the 'master' branch to work on
> it. And suddenly I get this error:
> 
>    error: Entry 'cream-abbr-eng.vim' would be overwritten by merge.
>    Cannot merge.
> 
> To reproduce my problem:
> 
>   $> git clone git://git.workaround.org/cream
>   $> cd cream
>   $> git merge origin/upstream
>   error: Entry 'cream-abbr-eng.vim' would be overwritten by merge.
>   Cannot merge.
>   fatal: merging of trees 70008c82f82a7985531aa2d039c03fdf944ea267 and
>   78d3a35e300434d6369424dd873bb587beacfaa4 failed

Very odd indeed!

$ git version
git version 1.6.4.2.264.g79b4f

I was able to workaround it:

$ rm *
$ git add -u
$ git merge origin/upstream

I've never run into this before.
I think it has to do with all the renamed files.
It looks like you're running into ain unfortunate edge case.

The merge-base of both branches (the initial commit) has all
files underneath a cream/ directory.

Both descendants (upstream and master) moved files up to the
root.  So when you go to merge those histories the merge driver
gets confused.

What happened in master?    cream/A -> A
What happened in upstream?  cream/A -> A

That seems like an edge case that might need some attention.

Anyways, once you do the workaround merge it'll settle
itself out and won't happen to you again since the merge will
resolve it for all your future commits (future merges will
have a new, rename-safe merge base).

Does anyone else on the list have any insights?

-- 
		David

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Christoph Haas]

David Aguilar schrieb:
> On Fri, Sep 04, 2009 at 10:28:36PM +0200, Christoph Haas wrote:
>> Now I imported a new upstream version into the upstream branch. And then
>> tried to merge the 'upstream' branch into the 'master' branch to work on
>> it. And suddenly I get this error:
>>
>>    error: Entry 'cream-abbr-eng.vim' would be overwritten by merge.
>>    Cannot merge.
>>
>> To reproduce my problem:
>>
>>   $> git clone git://git.workaround.org/cream
>>   $> cd cream
>>   $> git merge origin/upstream
>>   error: Entry 'cream-abbr-eng.vim' would be overwritten by merge.
>>   Cannot merge.
>>   fatal: merging of trees 70008c82f82a7985531aa2d039c03fdf944ea267 and
>>   78d3a35e300434d6369424dd873bb587beacfaa4 failed
> 
> Very odd indeed!
> 
> $ git version
> git version 1.6.4.2.264.g79b4f
> 
> I was able to workaround it:
> 
> $ rm *
> $ git add -u
> $ git merge origin/upstream

Thank you. I had to "rm -r addons", too, but the general hint helped me
a lot.

> I've never run into this before.
> I think it has to do with all the renamed files.
> It looks like you're running into ain unfortunate edge case.

Actually I'm not aware of any renames. But I don't claim that I always
know what I'm doing. :)

> Does anyone else on the list have any insights?

I'd be curious, too.

Kindly
 Christoph

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Junio C Hamano]

David Aguilar <davvid@gmail.com> writes:

> Does anyone else on the list have any insights?

Yes; the problem does not have anything to do with renames but
unfortunately is much deeper.  See $gmane/127783.

Here is a reproduction recipe for the lowest-level ingredient of the
breakage in "git read-tree -m"that needs to be fixed, before we can start
looking at what "git merge-recursive" does incorrectly (if any) and what
"git merge" does incorrectly (again, if any).

 t/t1004-read-tree-m-u-wf.sh |   23 +++++++++++++++++++++++
 1 files changed, 23 insertions(+), 0 deletions(-)

diff --git a/t/t1004-read-tree-m-u-wf.sh b/t/t1004-read-tree-m-u-wf.sh
index f19b4a2..055bb00 100755
--- a/t/t1004-read-tree-m-u-wf.sh
+++ b/t/t1004-read-tree-m-u-wf.sh
@@ -238,4 +238,27 @@ test_expect_success 'D/F recursive' '
 
 '
 
+################################################################
+
+test_expect_failure 'D/F D-F' '
+	git reset --hard &&
+	git rm -f -r . &&
+
+	mkdir t && echo 1 >t/f && git add t &&
+	git tag ONE $(git write-tree) &&
+
+	echo 3 >t-f && echo 3 >t/f && git add t-f t &&
+	git tag THREE $(git write-tree) &&
+
+	git rm -f -r t &&
+	echo 2 >t && echo 2 >t-f && git add t t-f &&
+	git tag TWO $(git write-tree) &&
+	git commit -a -m TWO &&
+
+	test_must_fail git read-tree -m -u ONE TWO THREE &&
+	git ls-files -u >actual &&
+	grep t/f actual &&
+	grep t-f actual
+'
+
 test_done

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> David Aguilar <davvid@gmail.com> writes:
>
>> Does anyone else on the list have any insights?
>
> Yes; the problem does not have anything to do with renames but
> unfortunately is much deeper.  See $gmane/127783.
>
> Here is a reproduction recipe for the lowest-level ingredient of the
> breakage in "git read-tree -m"that needs to be fixed, before we can start
> looking at what "git merge-recursive" does incorrectly (if any) and what
> "git merge" does incorrectly (again, if any).

To summarize the expected failure in this test, we merge these three trees:

    $ git ls-tree -t -r ONE
    040000 tree fd43cc879db368e808a98b81005d6f21a8852a15    t
    100644 blob d00491fd7e5bb6fa28c517a0bb32b8b506539d4d    t/f
    $ git ls-tree -t -r TWO
    100644 blob 0cfbf08886fca9a91cb753ec8734c84fcbe52c9f    t
    100644 blob 0cfbf08886fca9a91cb753ec8734c84fcbe52c9f    t-f
    $ git ls-tree -t -r THREE
    100644 blob 00750edc07d6415dcc07ae0351e9397b0222b7ba    t-f
    040000 tree 5b372f88770ab124f5149bc6eae19714b16ee363    t
    100644 blob 00750edc07d6415dcc07ae0351e9397b0222b7ba    t/f

while the index matches TWO.  The callback to unpack_trees() wants to get
"t" fed by the tree-walk API in a single call, but it is hard to arrange,
as in tree TWO the name "t-f" comes after name "t" and in tree THREE it
comes before "t".  When other trees want to yield "t", somebody in the
callchain needs to notice the situation, and yield "t" from tree THREE,
and then later yield "t-f", to meet the expectation of unpack_trees().

I was staring at this a bit more until my head started aching, and my
tentative conclusion is that the cleanest solution would be to change
tree-walk API so that it returns the entries in the order as if everything
were blobs.  E.g. even though in tree THREE, a subtree "t" is stored after
blob "t-f", we return "t".  Later, when told to update_tree_entry(), skip
back and yield "t-f".  After that when told to update_tree_entry(), notice
we have already given "t" back and skip to finish traversing THREE.

This would be necessary because unpack_callback() in unpack-trees.c wants
to see if the entry of the same name happens to be at the o->pos in the
index.  What it means is if all trees being merged (including TWO, that is
supposed to be similar to the index) had "t" as tree and "t-f" as blob, if
the index had "t-f" and "t" both as blobs, we would not be able to match
up the "t" (tree) entries from the merged trees with "t" (blob) entry
taken from the index.

Unfortunately, the callers of tree-walk API checks desc->size to see if
the traversal reached at the end before calling update_tree_entry(), so
the safest and simplest fix might end up to be sorting the tree buffer in
init_tree_desc().

What do you think?  Am I completely off the track?

>  t/t1004-read-tree-m-u-wf.sh |   23 +++++++++++++++++++++++
>  1 files changed, 23 insertions(+), 0 deletions(-)
>
> diff --git a/t/t1004-read-tree-m-u-wf.sh b/t/t1004-read-tree-m-u-wf.sh
> index f19b4a2..055bb00 100755
> --- a/t/t1004-read-tree-m-u-wf.sh
> +++ b/t/t1004-read-tree-m-u-wf.sh
> @@ -238,4 +238,27 @@ test_expect_success 'D/F recursive' '
>  
>  '
>  
> +################################################################
> +
> +test_expect_failure 'D/F D-F' '
> +	git reset --hard &&
> +	git rm -f -r . &&
> +
> +	mkdir t && echo 1 >t/f && git add t &&
> +	git tag ONE $(git write-tree) &&
> +
> +	echo 3 >t-f && echo 3 >t/f && git add t-f t &&
> +	git tag THREE $(git write-tree) &&
> +
> +	git rm -f -r t &&
> +	echo 2 >t && echo 2 >t-f && git add t t-f &&
> +	git tag TWO $(git write-tree) &&
> +	git commit -a -m TWO &&
> +
> +	test_must_fail git read-tree -m -u ONE TWO THREE &&
> +	git ls-files -u >actual &&
> +	grep t/f actual &&
> +	grep t-f actual
> +'
> +
>  test_done

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Junio C Hamano]

I was looking at this loop in traverse_trees() from tree-walk.c

	for (i = 0; i < n; i++) {
		if (!t[i].size)
			continue;
		entry_extract(t+i, entry+i);
		if (last >= 0) {
			int cmp = entry_compare(entry+i, entry+last);

			/*
			 * Is the new name bigger than the old one?
			 * Ignore it
			 */
			if (cmp > 0)
				continue;
			/*
			 * Is the new name smaller than the old one?
			 * Ignore all old ones
			 */
			if (cmp < 0)
				mask = 0;
		}
		mask |= 1ul << i;
		if (S_ISDIR(entry[i].mode))
			dirmask |= 1ul << i;
		last = i;
	}

The logic to update last breaks down while merging these three trees:

    Tree #1: tree "t"
    Tree #2: blob "t"
             blob "t-f"
    Tree #3: blob "t-f"
             tree "t"

When looking at Tree #3, "last" points at "t" (blob) from Tree #2
and we decide "t-f" comes later than that to ignore it because "cmp > 0".

We instead somehow need to look ahead and find "t", while remembering to
revisit "t-f" from it in the later rounds (of an outer loop that has this
loop inside).

Also the second comparison to update last breaks down while merging these:

    Tree #1: blob "t-f" 
             tree "t"
    Tree #2: blob "t"
    Tree #3: blob "t"
             blob "t-f"

When looking at Tree #2, "last" points at "t-f" (blob) from Tree #1 and we
decide to use "t" because it sorts earlier.  We will match "t" from Tree #3
but we somehow need to go back to Tree #1 and look beyond "t-f" to find
the matchig "t" from there as well, while remembering that we need to
revisit "t-f" from it in the later rounds..

I am thinking about changing the function this way.

 (0) take an optional "candidate for the earliest name" from the caller,
     in a new member in traverse_info structure. unpack_callback() would
     give the path of the index entry it is looking at after stripping the
     leading paths as necessary.

 (1) find the "earliest name" N among the given trees (and the optional
     additional candidate from the above).  The "earliest" is computed by
     comparing names as if everything were a blob;

 (2) for each tree t[i], if the current entry entry[i] compares
     differently with N between the cases where the N were a blob and
     where N were a tree, and if entry[i] is a blob, a tree with the name
     N might be hidden behind it.  remember the current position so we can
     come back, and scan forward to find such tree (this does not have to
     run to the end of the tree), and if we do find one, then instead of
     saying "we do not have an entry with that name", use that tree in
     entry[i].  This will collect entries with name N from all trees in
     the entry[] array;

 (3) make the callback as usual; unpack_callback(), after processing this
     round with entries with name N, may or may not advance o->pos but if
     it did so, it would also update the "candidate for the earliest name"
     field passed back in the traverse_info structure to prepare for the
     next round.

 (4) traverse_trees() will go back to step (0).

The tricky part is step (1) and the latter half of step (2) to skip,
rewind, and avoid re-processing what was processed already after
rewinding, and the progress is much slower than I would like.

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Linus Torvalds]

Sorry, I was off for the week with very limited computer time (my main 
computer was a Suunto Gekko that I wore underwater), and spent yesterday 
doing the last kernel -rc.

Anyway, this is a problem I knew about, and it comes directly from the 
insane historical behavior of unpack_trees(), where it would mix up blobs 
and trees. The problem was _very_ obvious when I rewrote the tree-walking 
to be readable.

See commit 91e4f03604bd089e09154e95294d5d08c805ea49, and in particular the 
change from using base_name_compare() to using the idiotic df_name_compare().

It's called 'df_name_compare()' for a reason. That 'df' is because of the 
insane directory/file semantics that are simply not a compete ordering. 
And because it's not a complete ordering, it's impossible to handle 
certain cases, exactly because of the following situation:

	a < a-b < a/

but at the same time

	a == a/

ie you have a unsatisfiable situation.

And no, changing the ordering to "pure blob order" is _not_ the solution. 
Because then you'll no longer traverse the trees in the same order as you 
traverse the index, and you'll get into _much_ deeper trouble.

So the real solution was always to never use 'df_name_compare()': any user 
of that function is broken by design. It's sadly just the case that the 
original unpack_trees() always had those insane semantics, and when I 
rewrote it, I was very careful to keep the old semantics. Trust me, I very 
much wanted to change them.

So the solution is to change the 'df_name_compare()' (that fundamentally 
has that impossible constraint of 'a' == 'a/') to 'base_name_compare()'. 
That way name comparisons are always meaningful, and always follow the 
rules. The df_name_compare() thing was always a broken hack - just one 
that got the semantics we wanted for all the truly simple cases.

And then fix the fallout from that: callers never get mixed-up tree and 
blob entries, and have to do their DF checking themselves.

IOW, the starting point is the following. And let me try to see what we 
need to do in the callers (this really is just a starting point: we'll 
need to clean up all the insane DF conflict marker code that is now 
pointless)

		Linus
---
From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Sun, 6 Sep 2009 11:15:04 -0700
Subject: [PATCH] Get rid of the broken 'df_name_compare()'

This _will_ break the test-suite, but anything that depends on
df_name_compare() is fundamentally flawed.  Because it is designed to
compare directory and blob names as equal, you have 'a' == 'a/', but at
the same time you also have 'a' < 'a-b' < 'a/'.

Out old unpack_trees() semantics depend on that impossible situation,
and we've kept this hack around for a long time.  But now somebody has
finally hit the impossible case, and we need to bite the bullet and get
rid of the hack, and fix D/F conflict handling properly.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 cache.h        |    1 -
 read-cache.c   |   35 -----------------------------------
 tree-walk.c    |    2 +-
 unpack-trees.c |    2 +-
 4 files changed, 2 insertions(+), 38 deletions(-)

diff --git a/cache.h b/cache.h
index 5fad24c..fda9a49 100644
--- a/cache.h
+++ b/cache.h
@@ -709,7 +709,6 @@ extern int create_symref(const char *ref, const char *refs_heads_master, const c
 extern int validate_headref(const char *ref);
 
 extern int base_name_compare(const char *name1, int len1, int mode1, const char *name2, int len2, int mode2);
-extern int df_name_compare(const char *name1, int len1, int mode1, const char *name2, int len2, int mode2);
 extern int cache_name_compare(const char *name1, int len1, const char *name2, int len2);
 
 extern void *read_object_with_reference(const unsigned char *sha1,
diff --git a/read-cache.c b/read-cache.c
index 1bbaf1c..f3143d8 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -362,41 +362,6 @@ int base_name_compare(const char *name1, int len1, int mode1,
 	return (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0;
 }
 
-/*
- * df_name_compare() is identical to base_name_compare(), except it
- * compares conflicting directory/file entries as equal. Note that
- * while a directory name compares as equal to a regular file, they
- * then individually compare _differently_ to a filename that has
- * a dot after the basename (because '\0' < '.' < '/').
- *
- * This is used by routines that want to traverse the git namespace
- * but then handle conflicting entries together when possible.
- */
-int df_name_compare(const char *name1, int len1, int mode1,
-		    const char *name2, int len2, int mode2)
-{
-	int len = len1 < len2 ? len1 : len2, cmp;
-	unsigned char c1, c2;
-
-	cmp = memcmp(name1, name2, len);
-	if (cmp)
-		return cmp;
-	/* Directories and files compare equal (same length, same name) */
-	if (len1 == len2)
-		return 0;
-	c1 = name1[len];
-	if (!c1 && S_ISDIR(mode1))
-		c1 = '/';
-	c2 = name2[len];
-	if (!c2 && S_ISDIR(mode2))
-		c2 = '/';
-	if (c1 == '/' && !c2)
-		return 0;
-	if (c2 == '/' && !c1)
-		return 0;
-	return c1 - c2;
-}
-
 int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)
 {
 	int len1 = flags1 & CE_NAMEMASK;
diff --git a/tree-walk.c b/tree-walk.c
index 02e2aed..8fc0ddc 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -62,7 +62,7 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
 
 static int entry_compare(struct name_entry *a, struct name_entry *b)
 {
-	return df_name_compare(
+	return base_name_compare(
 			a->path, tree_entry_len(a->path, a->sha1), a->mode,
 			b->path, tree_entry_len(b->path, b->sha1), b->mode);
 }
diff --git a/unpack-trees.c b/unpack-trees.c
index 720f7a1..548fef4 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -196,7 +196,7 @@ static int do_compare_entry(const struct cache_entry *ce, const struct traverse_
 	ce_name = ce->name + pathlen;
 
 	len = tree_entry_len(n->path, n->sha1);
-	return df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);
+	return base_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);
 }
 
 static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> And then fix the fallout from that: callers never get mixed-up tree and 
> blob entries, and have to do their DF checking themselves.

There are two levels of internal APIs involved, and I am getting confused
as to which level of callers you are referrring to in the above.

My understanding of the current situation is:

 * unpack_trees() takes a callback from the caller in o->fn().  It
   promises (but fails to keep the promise) that the callback is called
   with entries with matching names, so that it gets to see D/F
   conflicting entries in one go.

 * traverse_trees() takes a callback from the caller in info->fn().  It
   feeds the callback the entries with the same name most of the time, but
   that is not a guarantee, and the bug we are seeing is coming from a
   caller, unpack_trees_callback(), assuming it.

Do you mean we would still keep the promise unpack_trees() makes to its
callbacks, e.g. threeway_merge(), or do you mean these callbacks are to be
prepared to get DF-split input themselves and expected to coalesce them
as necessary?

There are only two callers of traverse_trees() interface.  unpack_trees()
codepath is the primary one (the other being the merge-tree.c, which is in
disuse).

If you mean unpack_trees() by "callers, ... have to do their DF checking",
it may be a much isolated fix than what I had in mind in the last message
from me---the one that makes traverse_trees() pay attention to the caller
supplied "candiate 'earliest' name" and tries to push the "give entries
from all the trees with the same name to the callback in one go" promise
down to traverse_trees() layer.

If traverse_trees() did not do this name coalescing, on the other hand, I
wonder if it is doing only half of the job to be useful.  I do not think
of a plausible scenario where a caller, who wants to walk multiple trees
in parallel, does not want to be fed the entries with the same name from
all the input trees in one invocation of the callback it gives.

If all the callers need to do the name coalescing in order to notice the
situation that led to this bug, I wonder if it would be nicer to do so in
traverse_trees()?

unpack_trees() would of course be helped if traverse_trees() gave that
promise, and I suspect merge-tree.c::threeway_callback() would expect that
behaviour, too.

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Linus Torvalds]

On Sun, 6 Sep 2009, Junio C Hamano wrote:
> Linus Torvalds <torvalds@linux-foundation.org> writes:
> 
> > And then fix the fallout from that: callers never get mixed-up tree and 
> > blob entries, and have to do their DF checking themselves.
> 
> There are two levels of internal APIs involved, and I am getting confused
> as to which level of callers you are referrring to in the above.

It could be done at any level, but there's a few places where it's easier 
than others.

> My understanding of the current situation is:
> 
>  * unpack_trees() takes a callback from the caller in o->fn().  It
>    promises (but fails to keep the promise) that the callback is called
>    with entries with matching names, so that it gets to see D/F
>    conflicting entries in one go.

Indeed. I'd _like_ to do it at this level (or even at the o->fn() level), 
but quite frankly, unpack_trees() is so horribly complicated, and you'd 
have to remember state, that doing it at this level is not realy 
maintainable.

>  * traverse_trees() takes a callback from the caller in info->fn().  It
>    feeds the callback the entries with the same name most of the time, but
>    that is not a guarantee, and the bug we are seeing is coming from a
>    caller, unpack_trees_callback(), assuming it.

This is the level I'm looking at. In fact, I'm going to cheat. I'm not 
going to do it when we call info->fn(), I'm going to do it _before_ the 
call, and have a special "find conflicts" phase inside traverse_trees() 
itself.

That way, any traverse_trees() user will see the conflicts exactly like 
they used to, because I'm just going to add a special "find conflicts" 
phase there that does the right thing. It's a hack, but it's a "useful" 
hack, and it at least avoids being the current "it can't work for the 
special case" thing.

> Do you mean we would still keep the promise unpack_trees() makes to its
> callbacks, e.g. threeway_merge(), or do you mean these callbacks are to be
> prepared to get DF-split input themselves and expected to coalesce them
> as necessary?

Either would work, but changing unpack_trees() semantics would just be 
very painful. There are just too many users of it, and they are too 
ingrained in their expectations of getting conflict information in a 
single pass.

I think I have a good solution, give me half an hour to actually get it to 
work.

			Linus

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> On Sun, 6 Sep 2009, Junio C Hamano wrote:
>...
>>  * traverse_trees() takes a callback from the caller in info->fn().  It
>>    feeds the callback the entries with the same name most of the time, but
>>    that is not a guarantee, and the bug we are seeing is coming from a
>>    caller, unpack_trees_callback(), assuming it.
>
> This is the level I'm looking at. In fact, I'm going to cheat. I'm not 
> going to do it when we call info->fn(), I'm going to do it _before_ the 
> call, and have a special "find conflicts" phase inside traverse_trees() 
> itself.
>
> That way, any traverse_trees() user will see the conflicts exactly like 
> they used to, because I'm just going to add a special "find conflicts" 
> phase there that does the right thing. It's a hack, but it's a "useful" 
> hack, and it at least avoids being the current "it can't work for the 
> special case" thing.
> ...
> I think I have a good solution, give me half an hour to actually get it to 
> work.

Thanks.

The reason I brought up adding the "candidate for the earliest name"
interface to the function was to avoid a case where the index has

    blob "t"
    blob "t-f"

and all the trees being merged have

    blob "t-f"
    tree "t"

in which case the "Are we supposed to look at the index too?" logic in
unpack_callback() may not catch the "t-f" entry from the index when the
first callback from traverse_trees() feeds it "t-f".  It would notice that
the entry at o->pos is "t".  When that happens, I did not think of a clean
way to avoid the codepath from emitting "t" as "only exists in the index".
With the "candidate" addition, traverse_trees() could say "You asked me
that I may have to return 't' to you, and here are the entries from all
the trees." before giving "t-f" back.

Other than that, I think find_conflicts() phase in the traverse_trees()
makes sense.

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Linus Torvalds]

On Sun, 6 Sep 2009, Junio C Hamano wrote:
> 
> The reason I brought up adding the "candidate for the earliest name"
> interface to the function was to avoid a case where the index has
> 
>     blob "t"
>     blob "t-f"
> 
> and all the trees being merged have
> 
>     blob "t-f"
>     tree "t"
> 
> in which case the "Are we supposed to look at the index too?" logic in
> unpack_callback() may not catch the "t-f" entry from the index when the
> first callback from traverse_trees() feeds it "t-f".

I agree. It's why I initially wanted to do it _all_ in the 
unpack_callback() thing, but the more I tried, the more complex it got.

So now my plan is to do the conflict handling at a tree level in 
traverse_trees(), and get rid of the use of 'df_name_compare()' just there 
first. 

The index case is slightly easier, as we can go back-and-forth in the 
source index (we do try to avoid it right now, but that's a small 
optimization rather than anything fundamental), so the index we can 
traverse in a more flexible manner, and find the 't' conflict that way.

		Linus

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Linus Torvalds]

On Sun, 6 Sep 2009, Linus Torvalds wrote:
> 
> I agree. It's why I initially wanted to do it _all_ in the 
> unpack_callback() thing, but the more I tried, the more complex it got.
> 
> So now my plan is to do the conflict handling at a tree level in 
> traverse_trees(), and get rid of the use of 'df_name_compare()' just there 
> first. 

Grr. I need to go off and do some other things, and this still fails a few 
tests. This is not my more exhaustive patch that actually tries to 
remember the conflict entries we've used up, this is the most cut-down and 
simplified "just remove df_name_compare() in tree-walk.c".

And it's not working, for some reason I'm not seeing, but I thought I'd 
send it to you just as a way to show where I'm trying to take this. Maybe 
you see what my thinko is.

[ In other words: in this version, we only do a single-entry lookahead, 
  exactly like we used to do before. So this is not meant to _fix_ 
  anything, or change any semantics. It's an incremental "change the model 
  so that we can look ahead more in a future patch" patch.

  But it's broken, and I have to run away for a while. ]

		Linus

---
 tree-walk.c |   69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 67 insertions(+), 2 deletions(-)

diff --git a/tree-walk.c b/tree-walk.c
index 02e2aed..dd563e9 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -62,7 +62,7 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
 
 static int entry_compare(struct name_entry *a, struct name_entry *b)
 {
-	return df_name_compare(
+	return base_name_compare(
 			a->path, tree_entry_len(a->path, a->sha1), a->mode,
 			b->path, tree_entry_len(b->path, b->sha1), b->mode);
 }
@@ -138,6 +138,68 @@ char *make_traverse_path(char *path, const struct traverse_info *info, const str
 	return path;
 }
 
+/*
+ * See if 'entry' may conflict with a later tree entry in 't': if so,
+ * fill in 'conflict' with the conflicting tree entry from 't'.
+ *
+ * NOTE! Right now we do _not_ create a create a private copy of the tree
+ * descriptor, so we can't actually walk it any further without losing
+ * our place. We should change it to a loop over a copy of the tree
+ * descriptor, but then we'd also have to remember the skipped entries,
+ * so this is a hacky simple case that only handles the case we used
+ * to handle historically (ie clash in the very first entry)
+ *
+ * Note that only a regular file 'entry' can conflict with a later
+ * directory, since a directory with the same name will sort later.
+ */
+static int find_df_conflict(struct tree_desc *t, struct name_entry *entry, struct name_entry *conflict)
+{
+	int len;
+
+	if (S_ISDIR(entry->mode))
+		return 0;
+	len = tree_entry_len(entry->path, entry->sha1);
+
+	while (t->size) {
+		int nlen;
+
+		entry_extract(t, conflict);
+		nlen = tree_entry_len(conflict->path, conflict->sha1);
+
+		/*
+		 * We can only have a future conflict if the entry matches the
+		 * beginning of the name exactly, and if the next character is
+		 * smaller than '/'.
+		 *
+		 * Break out otherwise.
+		 */
+		if (nlen < len)
+			break;
+		if (memcmp(conflict->path, entry->path, nlen))
+			break;
+
+		/*
+		 * FIXME! This is the case where we'd like to mark the tree
+		 * entry used in the original 't' rather than modify 't'!
+		 */
+		if (nlen == len) {
+			update_tree_entry(t);
+			return 1;
+		}
+
+		if (conflict->path[len] > '/')
+			break;
+		/*
+		 * FIXME! Here we'd really like to do 'update_tree_entry(&copy);'
+		 * but that requires us to remember the conflict position specially
+		 * so now we just punt and stop looking for conflicts
+		 */
+		break;
+	}
+	entry_clear(conflict);
+	return 0;
+}
+
 int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 {
 	int ret = 0;
@@ -179,12 +241,15 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 		dirmask &= mask;
 
 		/*
-		 * Clear all the unused name-entries.
+		 * Clear all the unused name-entries, and look for
+		 * conflicts.
 		 */
 		for (i = 0; i < n; i++) {
 			if (mask & (1ul << i))
 				continue;
 			entry_clear(entry + i);
+			if (find_df_conflict(t+i, entry+last, entry+i))
+				dirmask |= (1ul << i);
 		}
 		ret = info->fn(n, mask, dirmask, entry, info);
 		if (ret < 0)

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> Grr. I need to go off and do some other things, and this still fails a few 
> tests...
> [ In other words: in this version, we only do a single-entry lookahead, 
>   exactly like we used to do before. So this is not meant to _fix_ 
>   anything, or change any semantics. It's an incremental "change the model 
>   so that we can look ahead more in a future patch" patch.
>
>   But it's broken, and I have to run away for a while. ]

That's okay.  I myself have to go and give a final review to the galley
proof of my book, before the publisher gives a go to the printing press
now.

I do not think we are in a hurry, as this issue, as far as I can tell, has
been with us from early days of git; I would say for the whole lifetime of
the unpack_trees() interface, but I didn't check.

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Linus Torvalds]

On Sun, 6 Sep 2009, Linus Torvalds wrote:
> 
> And it's not working, for some reason I'm not seeing, but I thought I'd 
> send it to you just as a way to show where I'm trying to take this. Maybe 
> you see what my thinko is.

Duh. My thinko was that I wasn't testing the right thing. The patch works 
fine, my test failures came from the fact that I was working on a branch 
with some other broken experimental features.

Now, the patch I sent out did have a buglet: when a conflict happens, 
'mask' will not have the conflicting bits we just added to 'dirmask'. But 
that buglet doesn't actually seem to affect any of the traverse_tree() 
callers, and they are fine with 'dirmask' being separate from 'mask'.

So here's a slightly updated version, and it passes all the tests.

Again, an important note: this is _not_ meant to change semantics, it's 
really only meant to re-organize the code so that we _can_ do look-ahead 
in the trees for conflicts. But in its current form, the look-ahead is 
limited to the next entry, the same as the old code.

So there should be no semantic changes from this patch. Just avoid using 
'df_name_compare()' and create that 'find_df_conflict()' function that can 
be expanded to actually look ahead more.

		Linus

---
 tree-walk.c |   72 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 69 insertions(+), 3 deletions(-)

diff --git a/tree-walk.c b/tree-walk.c
index 02e2aed..fb5ca1e 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -62,7 +62,7 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
 
 static int entry_compare(struct name_entry *a, struct name_entry *b)
 {
-	return df_name_compare(
+	return base_name_compare(
 			a->path, tree_entry_len(a->path, a->sha1), a->mode,
 			b->path, tree_entry_len(b->path, b->sha1), b->mode);
 }
@@ -138,6 +138,68 @@ char *make_traverse_path(char *path, const struct traverse_info *info, const str
 	return path;
 }
 
+/*
+ * See if 'entry' may conflict with a later tree entry in 't': if so,
+ * fill in 'conflict' with the conflicting tree entry from 't'.
+ *
+ * NOTE! Right now we do _not_ create a create a private copy of the tree
+ * descriptor, so we can't actually walk it any further without losing
+ * our place. We should change it to a loop over a copy of the tree
+ * descriptor, but then we'd also have to remember the skipped entries,
+ * so this is a hacky simple case that only handles the case we used
+ * to handle historically (ie clash in the very first entry)
+ *
+ * Note that only a regular file 'entry' can conflict with a later
+ * directory, since a directory with the same name will sort later.
+ */
+static int find_df_conflict(struct tree_desc *t, struct name_entry *entry, struct name_entry *conflict)
+{
+	int len;
+
+	if (S_ISDIR(entry->mode))
+		return 0;
+	len = tree_entry_len(entry->path, entry->sha1);
+
+	while (t->size) {
+		int nlen;
+
+		entry_extract(t, conflict);
+		nlen = tree_entry_len(conflict->path, conflict->sha1);
+
+		/*
+		 * We can only have a future conflict if the entry matches the
+		 * beginning of the name exactly, and if the next character is
+		 * smaller than '/'.
+		 *
+		 * Break out otherwise.
+		 */
+		if (nlen < len)
+			break;
+		if (memcmp(conflict->path, entry->path, nlen))
+			break;
+
+		/*
+		 * FIXME! This is the case where we'd like to mark the tree
+		 * entry used in the original 't' rather than modify 't'!
+		 */
+		if (nlen == len) {
+			update_tree_entry(t);
+			return 1;
+		}
+
+		if (conflict->path[len] > '/')
+			break;
+		/*
+		 * FIXME! Here we'd really like to do 'update_tree_entry(&copy);'
+		 * but that requires us to remember the conflict position specially
+		 * so now we just punt and stop looking for conflicts
+		 */
+		break;
+	}
+	entry_clear(conflict);
+	return 0;
+}
+
 int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 {
 	int ret = 0;
@@ -179,14 +241,18 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 		dirmask &= mask;
 
 		/*
-		 * Clear all the unused name-entries.
+		 * Clear all the unused name-entries, and look for
+		 * conflicts.
 		 */
 		for (i = 0; i < n; i++) {
 			if (mask & (1ul << i))
 				continue;
 			entry_clear(entry + i);
+			if (find_df_conflict(t+i, entry+last, entry+i))
+				dirmask |= (1ul << i);
 		}
-		ret = info->fn(n, mask, dirmask, entry, info);
+
+		ret = info->fn(n, mask | dirmask, dirmask, entry, info);
 		if (ret < 0)
 			break;
 		if (ret)

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Linus Torvalds]

On Sun, 6 Sep 2009, Linus Torvalds wrote:
> 
> So here's a slightly updated version, and it passes all the tests.

.. and here's something with a bit more abstraction, a bit more cleanup, 
and making more sure that there's no semantic changes. So that I can feel 
happy signing off on it.

		Linus
---
From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Sun, 6 Sep 2009 14:37:21 -0700
Subject: [PATCH] Prepare 'traverse_trees()' for D/F conflict lookahead

traverse_trees() used to always walk the trees in order, and used the
special (and fundamentally broken) 'df_name_compare()' function to
compare directory and file entries as equal.

That works fine for all the common cases, when the D/F conflicts are
immediately adjacent, and there are no other entries that could confuse
the ordering.  But if you have one tree with a file 'a', and another
tree with a file 'a-1' and a directory 'a/', then you would not see the
D/F conflict of 'a' and 'a/' without looking ahead past the 'a-1' file
in the other tree.

So this re-organizes the tree walking code so that we can start doing
look-ahead for those cases.  It doesn't actually _do_ that lookahead
yet, because it requires marking the conflicts we've used, but the code
is now organized to do so.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 tree-walk.c |   90 +++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 files changed, 85 insertions(+), 5 deletions(-)

diff --git a/tree-walk.c b/tree-walk.c
index 02e2aed..7251dd2 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -62,7 +62,7 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
 
 static int entry_compare(struct name_entry *a, struct name_entry *b)
 {
-	return df_name_compare(
+	return base_name_compare(
 			a->path, tree_entry_len(a->path, a->sha1), a->mode,
 			b->path, tree_entry_len(b->path, b->sha1), b->mode);
 }
@@ -138,6 +138,80 @@ char *make_traverse_path(char *path, const struct traverse_info *info, const str
 	return path;
 }
 
+/*
+ * See if 'entry' may conflict with a later tree entry in 't': if so,
+ * fill in 'conflict' with the conflicting tree entry from 't'.
+ *
+ * NOTE! Right now we do _not_ create a create a private copy of the tree
+ * descriptor, so we can't actually walk it any further without losing
+ * our place. We should change it to a loop over a copy of the tree
+ * descriptor, but then we'd also have to remember the skipped entries,
+ * so this is a hacky simple case that only handles the case we used
+ * to handle historically (ie clash in the very first entry)
+ *
+ * Note that only a regular file 'entry' can conflict with a later
+ * directory, since a directory with the same name will sort later.
+ */
+static int find_df_conflict(struct tree_desc *t, struct name_entry *entry, struct name_entry *conflict)
+{
+	int len;
+
+	if (S_ISDIR(entry->mode))
+		return 0;
+	len = tree_entry_len(entry->path, entry->sha1);
+
+	while (t->size) {
+		int nlen;
+
+		entry_extract(t, conflict);
+		nlen = tree_entry_len(conflict->path, conflict->sha1);
+
+		/*
+		 * We can only have a future conflict if the entry matches the
+		 * beginning of the name exactly, and if the next character is
+		 * smaller than '/'.
+		 *
+		 * Break out otherwise.
+		 */
+		if (nlen < len)
+			break;
+		if (memcmp(conflict->path, entry->path, nlen))
+			break;
+		if (nlen == len)
+			return 1;
+
+		if (conflict->path[len] > '/')
+			break;
+		/*
+		 * FIXME! Here we'd really like to do 'update_tree_entry(&copy);'
+		 * but that requires us to remember the conflict position specially
+		 * so now we just punt and stop looking for conflicts
+		 */
+		break;
+	}
+	entry_clear(conflict);
+	return 0;
+}
+
+/*
+ * For now, the used entries are always at the head of the tree_desc
+ * (no look-ahead), so marking an entry used is always just a matter
+ * of doing an 'update_tree_entry()'
+ */
+static void used_entry(struct tree_desc *t, struct name_entry *entry)
+{
+	update_tree_entry(t);
+}
+
+static int get_entry(struct tree_desc *t, struct name_entry *entry)
+{
+	if (t->size) {
+		entry_extract(t, entry);
+		return 1;
+	}
+	return 0;
+}
+
 int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 {
 	int ret = 0;
@@ -150,9 +224,8 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 
 		last = -1;
 		for (i = 0; i < n; i++) {
-			if (!t[i].size)
+			if (!get_entry(t+i, entry+i))
 				continue;
-			entry_extract(t+i, entry+i);
 			if (last >= 0) {
 				int cmp = entry_compare(entry+i, entry+last);
 
@@ -179,13 +252,20 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 		dirmask &= mask;
 
 		/*
-		 * Clear all the unused name-entries.
+		 * Clear all the unused name-entries, and look for
+		 * conflicts.
 		 */
 		for (i = 0; i < n; i++) {
 			if (mask & (1ul << i))
 				continue;
 			entry_clear(entry + i);
+			if (find_df_conflict(t+i, entry+last, entry+i))
+				dirmask |= (1ul << i);
 		}
+
+		/* Add in the DF conflict entries into the mask */
+		mask |= dirmask;
+
 		ret = info->fn(n, mask, dirmask, entry, info);
 		if (ret < 0)
 			break;
@@ -194,7 +274,7 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 		ret = 0;
 		for (i = 0; i < n; i++) {
 			if (mask & (1ul << i))
-				update_tree_entry(t + i);
+				used_entry(t+i, entry+i);
 		}
 	}
 	free(entry);

Re: Strange merge failure (would be overwritten by merge / cannot merge)

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> The index case is slightly easier, as we can go back-and-forth in the 
> source index (we do try to avoid it right now, but that's a small 
> optimization rather than anything fundamental),...

Almost true, but there is the final "Any left-over entries in the index?"
phase in unpack_trees() that relies on o->pos being correct.

unpack-trees traversing with index quite broken...

[Junio C Hamano]

Linus,

I found an issue I do not know how to resolve.

Suppose you try to merge these three trees:

 - Tree #1 (ancestor)
   t   tree, in which there is an entry f that is a blob
   t/f blob

 - Tree #2 (ours)
   t   blob
   t-f blob

 - Tree #3 (theirs)
   t-f blob

The index matches our tree.

The callchain that causes "read-tree -m -u #1 #2 #3" misbehave looks like this.

unpack_trees()
->traverse_trees()
  entry[0] = "t" (tree taken from Tree #1)
  entry[1] = "t" (blob taken from Tree #2)
  entry[2] = nothing
  ->unpack_callback()
    ce = "t" (blob taken from the index)
    ->unpack_nondirectories()
      src[0] = "t" (blob from the index)
      src[1] = conflict (tree taken from Tree #1)
      src[2] = "t" (blob taken from Tree #2)
      src[3] = NULL
    ->call_unpack_fn()
      This callback is perfectly fine.
    /* Now handle any directories.. unpack-trees.c, ll.336- */
    ->traverse_trees_recursive()
      Now we stepped into tree "t".
      ->traverse_trees()
        entry[0] = "f" (blob from "t/" tree in Tree #1)
        entry[1] = nothing (Tree #2 does not have "t/" subtree)
        entry[2] = nothing (Tree #3 does not have "t/" subtree)
        ->unpack_callback()
          ce = "t-f" (blob taken from the index)
          ->compare_entry(ce, entry[])
          <- "t-f" comes anything in "t/" directory, return negative

          Because we are processing "t/something" at this level, and
          "t-f" that should come earlier than any "t/something", we
          assume that there is no matching entries in the trees.
          ->unpack_index_entry(ce = "t-f")
            ->call_unpack_fn()
              This callback is utterly wrong.  "t-f" from the index
              has a matching entry in Tree #2 and Tree #3, but we
              haven't seen them yet!

At first, I thought that we could fudge this particular example by
noticing that "t-f" is earlier only because "t-f" sorts before "t/", the
path-prefix of the problematic level, and pretend the negative return from
compare_entry() as if it was positive (i.e. deferring the processing of
the index entry).  While this approach lets the problematic level
correctly feed only "t/f" to call_unpack_fn() and come back, and the rest
may proceed cleanly for this particular case, I do not think it is the
right solution.

If Tree #3 had another tree "t/" in it, the situation would look like this
instead:

 - Tree #1 (ancestor)
   t   tree, in which there is an entry f that is a blob
   t/f blob

 - Tree #2 (ours, matches the index)
   t   blob
   t-f blob

 - Tree #3 (theirs)
   t-f blob
   t   tree, in which there is an entry f that is a blob    

Since traverse_trees() wants to walk the trees in parallel, never seeking
back, I do not think it would feed t-f from Tree #2 and Tree #3 to the
unpack_callback() sanely.  Worse yet, the logic to walk the index in
parallel while this is happening (i.e. "Are we supposed to look at the
index too?" part) does not want to seek o->pos pointer back either, so I
am stuck X-<...