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

5 messages, 2 authors, 2016-06-15 · open the first message on its own page

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

From: Junio C Hamano <hidden>
Date: 2016-06-15 22:47:22

Linus Torvalds [off-list ref] writes:

On Sun, 6 Sep 2009, Junio C Hamano wrote:
...

quoted

 * 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)

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: 2016-06-15 22:47:22


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)

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: 2016-06-15 22:47:22


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)

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: 2016-06-15 22:47:22


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)

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: 2016-06-15 22:47:22


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);

`h`	back out one level
`j`	next message in thread
`k`	previous message in thread
`l`	drill in
`Esc`	close help / fold thread tree
`?`	toggle this help