git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: git merge -s subtree seems to be broken.

From
Jeff King <peff@peff.net>
Date
Aug 2, 2018, 18:58 UTC
Message-ID
<20180802185821.GD23690@sigill.intra.peff.net>
In-Reply-To
<d60fc243-7271-bc49-b687-ade2b6e315ea@web.de>
On Wed, Aug 01, 2018 at 02:58:50AM +0200, René Scharfe wrote:
Show 9 quoted lines
> Am 31.07.2018 um 23:06 schrieb Junio C Hamano:
> > Jeff King <peff@peff.net> writes:
> > 
> >> On Tue, Jul 31, 2018 at 01:23:04PM -0400, Jeff King wrote:
> >> ...
> >> So here it is fixed, and with a commit message. I'm not happy to omit a
> >> regression test, but I actually couldn't come up with a minimal one that
> >> tickled the problem, because we're playing around with heuristics.
> How about something like this? (squashable)

Thanks. This is quite similar to what I tried, but I had started a new script, and I suspect that what is in t6029's master branch tickles the heuristic in a more interesting way. Or possibly I just botched my attempt, though I did spend quite a bit of time fiddling with it. The master branch seems to only contain one file, "hello". Hmph.

At any rate, it does trigger the bug and demonstrate the fix, so let's go with it. I see Junio already squashed the tests into jk/merge-subtree-heuristics, but I think we can cut down the commit message a bit (and stop claiming that we don't have a test ;) ). Like so (and yes, this version omits the extra scissors):

-- >8 --
Subject: score_trees(): fix iteration over trees with missing entries

In score_trees(), we walk over two sorted trees to find which entries are missing or have different content between the two. So if we have two trees with these entries:

  one   two
  ---   ---
  a     a
  b     c
  c     d
we'd expect the loop to:
  - compare "a" to "a"
  - compare "b" to "c"; because these are sorted lists, we
    know that the second tree does not have "b"
  - compare "c" to "c"
  - compare "d" to end-of-list; we know that the first tree
    does not have "d"

And prior to d8febde370 (match-trees: simplify score_trees() using tree_entry(), 2013-03-24) that worked. But after that commit, we mistakenly increment the tree pointers for every loop iteration, even when we've processed the entry for only one side. As a result, we end up doing this:

  - compare "a" to "a"
  - compare "b" to "c"; we know that we do not have "b", but
    we still increment both tree pointers; at this point
    we're out of sync and all further comparisons are wrong
  - compare "c" to "d" and mistakenly claim that the second
    tree does not have "c"
  - exit the loop, mistakenly not realizing that the first
    tree does not have "d"

So contrary to the claim in d8febde370, we really do need to manually use update_tree_entry(), because advancing the tree pointer depends on the entry comparison.

That means we must stop using tree_entry() to access each entry, since it auto-advances the pointer. Instead:

  - we'll use tree_desc.size directly to know if there's
    anything left to look at (which is what tree_entry() was
    doing under the hood)
  - rather than do an extra struct assignment to "e1" and
    "e2", we can just access the "entry" field of tree_desc
    directly

That makes us a little more intimate with the tree_desc code, but that's not uncommon for its callers.

The included test shows off the bug by adding a new entry "bar.t", which sorts early in the tree and de-syncs the comparison for "foo.t", which comes after.

Reported-by: George Shammas <georgyo@gmail.com>
Helped-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Jeff King <peff@peff.net>
---
 match-trees.c            | 43 ++++++++++++++++++++++++----------------
 t/t6029-merge-subtree.sh | 28 ++++++++++++++++++++++++++
 2 files changed, 54 insertions(+), 17 deletions(-)
diff --git a/match-trees.c b/match-trees.c
index 4cdeff53e1..37653308d3 100644
--- a/match-trees.c
+++ b/match-trees.c
@@ -83,34 +83,43 @@ static int score_trees(const struct object_id *hash1, const struct object_id *ha
 	int score = 0;
 
 	for (;;) {
-		struct name_entry e1, e2;
-		int got_entry_from_one = tree_entry(&one, &e1);
-		int got_entry_from_two = tree_entry(&two, &e2);
 		int cmp;
 
-		if (got_entry_from_one && got_entry_from_two)
-			cmp = base_name_entries_compare(&e1, &e2);
-		else if (got_entry_from_one)
+		if (one.size && two.size)
+			cmp = base_name_entries_compare(&one.entry, &two.entry);
+		else if (one.size)
 			/* two lacks this entry */
 			cmp = -1;
-		else if (got_entry_from_two)
+		else if (two.size)
 			/* two has more entries */
 			cmp = 1;
 		else
 			break;
 
-		if (cmp < 0)
+		if (cmp < 0) {
 			/* path1 does not appear in two */
-			score += score_missing(e1.mode, e1.path);
-		else if (cmp > 0)
+			score += score_missing(one.entry.mode, one.entry.path);
+			update_tree_entry(&one);
+		} else if (cmp > 0) {
 			/* path2 does not appear in one */
-			score += score_missing(e2.mode, e2.path);
-		else if (oidcmp(e1.oid, e2.oid))
-			/* they are different */
-			score += score_differs(e1.mode, e2.mode, e1.path);
-		else
-			/* same subtree or blob */
-			score += score_matches(e1.mode, e2.mode, e1.path);
+			score += score_missing(two.entry.mode, two.entry.path);
+			update_tree_entry(&two);
+		} else {
+			/* path appears in both */
+			if (oidcmp(one.entry.oid, two.entry.oid)) {
+				/* they are different */
+				score += score_differs(one.entry.mode,
+						       two.entry.mode,
+						       one.entry.path);
+			} else {
+				/* same subtree or blob */
+				score += score_matches(one.entry.mode,
+						       two.entry.mode,
+						       one.entry.path);
+			}
+			update_tree_entry(&one);
+			update_tree_entry(&two);
+		}
 	}
 	free(one_buf);
 	free(two_buf);
diff --git a/t/t6029-merge-subtree.sh b/t/t6029-merge-subtree.sh
index 3e692454a7..474a850de6 100755
--- a/t/t6029-merge-subtree.sh
+++ b/t/t6029-merge-subtree.sh
@@ -29,6 +29,34 @@ test_expect_success 'subtree available and works like recursive' '
 
 '
 
+test_expect_success 'setup branch sub' '
+	git checkout --orphan sub &&
+	git rm -rf . &&
+	test_commit foo
+'
+
+test_expect_success 'setup branch main' '
+	git checkout -b main master &&
+	git merge -s ours --no-commit --allow-unrelated-histories sub &&
+	git read-tree --prefix=dir/ -u sub &&
+	git commit -m "initial merge of sub into main" &&
+	test_path_is_file dir/foo.t &&
+	test_path_is_file hello
+'
+
+test_expect_success 'update branch sub' '
+	git checkout sub &&
+	test_commit bar
+'
+
+test_expect_success 'update branch main' '
+	git checkout main &&
+	git merge -s subtree sub -m "second merge of sub into main" &&
+	test_path_is_file dir/bar.t &&
+	test_path_is_file dir/foo.t &&
+	test_path_is_file hello
+'
+
 test_expect_success 'setup' '
 	mkdir git-gui &&
 	cd git-gui &&

-- 
2.18.0.800.g770d9f3396
Previous: René ScharfeNext: Jeff King
Message 16 of 17 in “git merge -s subtree seems to be broken.”
  1. George ShammasJul 31, 2018
  2. George ShammasJul 31, 2018
  3. Jeff KingJul 31, 2018
  4. Junio C HamanoJul 31, 2018
  5. René ScharfeAug 1, 2018
  6. Junio C HamanoJul 31, 2018
  7. George ShammasJul 31, 2018
  8. Jeff KingJul 31, 2018
  9. Junio C HamanoJul 31, 2018
  10. Jeff KingJul 31, 2018
  11. Jeff KingJul 31, 2018
  12. George ShammasJul 31, 2018
  13. Jeff KingJul 31, 2018
  14. Junio C HamanoJul 31, 2018
  15. René ScharfeAug 1, 2018
  16. Jeff KingAug 2, 2018
  17. Jeff KingAug 2, 2018

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.