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>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/match-trees.c b/match-trees.c
index 396b7338df2c53009900fbd3df36dd06a7219493..ad9e5e97444aeb7b2371a171a2133070b3e2e630 100644 (file)
--- a/match-trees.c
+++ b/match-trees.c
@@ -82,34 +82,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 3e692454a719324a7ed3c12238416f45df080efa..474a850de6084966f5137cb4fa4d8c5cf036e8e7 100755 (executable)
--- 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 &&