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

From: Junio C Hamano <gitster@pobox.com>
Date: Sep 6, 2009, 00:33 UTC
Message-ID: <7vzl98vrmt.fsf@alter.siamese.dyndns.org>
In-Reply-To: <7vab191dz1.fsf@alter.siamese.dyndns.org>

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

Show 11 quoted lines

> 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?

Show 35 quoted lines

>  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