git subtree bug produces divergent descendants

git subtree bug produces divergent descendants

[David Ware]

[-- Attachment #1: Type: text/plain, Size: 1535 bytes --]

My group has run into a bug with "git-subtree split". Under some
circumstances a split created from a descendant of another earlier
split is not a descendant of that earlier split (thus blocking
pushes). We originally noticed this on v1.9.1 but have also checked it
on v2.6.3

When scanning the commits to produce the subtree it seems to skip
creating a new commit if any of the parent commits have the same tree
and instead uses that tree in its place. This is fine when the cause
is a branch that did not cause any changes to the subtree.  However it
creates an issue when the cause is both branches ending up with the
same tree through identical alterations (or more likely, one of the
branches has just a subset of the alterations on the other, such as a
branch just containing cherry-picks).

The attached bash script (makerepo.sh) reproduces the problem. To use
create an empty directory and run the script in it. The resulting
'master' branch has had the latest commits on the 'branch' branch
merged into it, so it follows that a subtree on 'folder/' at 'master'
should contain all the commits of a subtree on 'folder/' at 'branch'.
(These subtrees have been produced at 'subtree_tip' and
'subtree_branch' respectively.)

The attached patch (against v2.6.3) fixes the issue for the cases
we've encountered, however since we're not particularly familiar with
git internals we may not have approached this optimally. We suspect it
could be improved to also handle the cases where there are more than 2
parents.

Cheers,
Dave Ware

[-- Attachment #2: makerepo.sh --]
[-- Type: application/x-sh, Size: 945 bytes --]

[-- Attachment #3: 0001-Fix-bug-in-git-subtree-split.patch --]
[-- Type: text/x-patch, Size: 1287 bytes --]

From 4bdcd742e5f21d7af57de3e307741efede7d2c6c Mon Sep 17 00:00:00 2001
From: Dave Ware <davidw@netvalue.net.nz>
Date: Fri, 4 Dec 2015 16:30:03 +1300
Subject: [PATCH] Fix bug in git-subtree split.

A bug occurs in 'git-subtree split' where a merge is skipped even when
both parents act on the subtree, provided the merge results in a tree
identical to one of the parents. Fixed by copying the merge if at least
one parent is non-identical, and the non-identical parent is not an
ancestor of the identical parent.
---
 contrib/subtree/git-subtree.sh | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh
index 9f06571..b837531 100755
--- a/contrib/subtree/git-subtree.sh
+++ b/contrib/subtree/git-subtree.sh
@@ -479,8 +479,16 @@ copy_or_skip()
 			p="$p -p $parent"
 		fi
 	done
-	
-	if [ -n "$identical" ]; then
+
+	copycommit=
+	if [ -n "$identical" ] && [ -n "$nonidentical" ]; then
+		extras=$(git rev-list --boundary $identical..$nonidentical)
+		if [ -n "$extras" ]; then
+			# we need to preserve history along the other branch
+			copycommit=1
+		fi
+	fi
+	if [ -n "$identical" ] && [ -z "$copycommit" ]; then
 		echo $identical
 	else
 		copy_commit $rev $tree "$p" || exit $?
-- 
1.9.1

Re: git subtree bug produces divergent descendants

[David Ware]

Sorry for the double post, I received a mail blocking notification
message (due to the attached .sh file) and erroneously thought this
message had been blocked from the entire list. My later one includes
the test case as part of the attached patch.

Cheers,
Dave Ware

On Mon, Dec 7, 2015 at 9:41 AM, David Ware <davidw@realtimegenomics.com> wrote:
> My group has run into a bug with "git-subtree split". Under some
> circumstances a split created from a descendant of another earlier
> split is not a descendant of that earlier split (thus blocking
> pushes). We originally noticed this on v1.9.1 but have also checked it
> on v2.6.3
>
> When scanning the commits to produce the subtree it seems to skip
> creating a new commit if any of the parent commits have the same tree
> and instead uses that tree in its place. This is fine when the cause
> is a branch that did not cause any changes to the subtree.  However it
> creates an issue when the cause is both branches ending up with the
> same tree through identical alterations (or more likely, one of the
> branches has just a subset of the alterations on the other, such as a
> branch just containing cherry-picks).
>
> The attached bash script (makerepo.sh) reproduces the problem. To use
> create an empty directory and run the script in it. The resulting
> 'master' branch has had the latest commits on the 'branch' branch
> merged into it, so it follows that a subtree on 'folder/' at 'master'
> should contain all the commits of a subtree on 'folder/' at 'branch'.
> (These subtrees have been produced at 'subtree_tip' and
> 'subtree_branch' respectively.)
>
> The attached patch (against v2.6.3) fixes the issue for the cases
> we've encountered, however since we're not particularly familiar with
> git internals we may not have approached this optimally. We suspect it
> could be improved to also handle the cases where there are more than 2
> parents.
>
> Cheers,
> Dave Ware

Re: git subtree bug produces divergent descendants

[David Ware]

Thanks for taking the time to look over it. I'm not familiar with the
process here.

On Mon, Dec 7, 2015 at 5:53 PM, Eric Sunshine <sunshine@sunshineco.com> wrote:
> Tests don't automatically return to the directory prior to the 'cd',
> so when this test ends, the current directory will still be
> 'git_subtree_split_check'. If someone later adds a test following
> this one, that test will execute within 'git_subtree_split_check',
> which might not be expected by the test writer.
>
> To ensure that the prior working directory is restored at the end of
> the test (regardless of success or failure), tests typically employ a
> subshell using this idiom:
>
>     mkdir foo &&
>     (
>         cd foo &&
>         ... &&
>         ...
>     )
>

I'm not at all familiar with this test harness so I had a few problems
here (like this, and the bash variable). Thank you for the advice.

Cheers,
Dave Ware

Re: git subtree bug produces divergent descendants

[Eric Sunshine]

On Mon, Dec 07, 2015 at 11:09:48AM +1300, David Ware wrote:
> My group has run into a bug with "git-subtree split". Under some
> circumstances a split created from a descendant of another earlier
> split is not a descendant of that earlier split (thus blocking
> pushes). [...]

I'm not a git-subtree user, so this review will be superficial.

> The attached patch (against v2.6.3) includes a test that reproduces
> the problem. [...]

Please include patches inline rather than as attachments since
reviewers will want to comment on portions of the patch as part of
their response to your email. Patches as attachments make this
process more painful.

> From: Dave Ware <davidw@netvalue.net.nz>
> Date: Fri, 4 Dec 2015 16:30:03 +1300
> Subject: [PATCH] Fix bug in git-subtree split.

For the subject, mention the area you're working on, followed by a
colon, followed by a concise description of the problem. If possible,
try to say something more specific than "fix bug". You might, for
instance, say something like:

    contrib/subtree: fix "subtree split" skipped-merge bug

> A bug occurs in 'git-subtree split' where a merge is skipped even when
> both parents act on the subtree, provided the merge results in a tree
> identical to one of the parents. Fixed by copying the merge if at least

Imperative mood: s/Fixed/Fix/

> one parent is non-identical, and the non-identical parent is not an
> ancestor of the identical parent.
> 
> Also adding a test case, this checks that a descendant can be pushed to
> it's ancestor in this case.

Your Signed-off-by: is missing. See Documentation/SubmittingPatches.

> ---
> diff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh
> index 9f06571..b837531 100755
> --- a/contrib/subtree/git-subtree.sh
> +++ b/contrib/subtree/git-subtree.sh
> @@ -479,8 +479,16 @@ copy_or_skip()
>  			p="$p -p $parent"
>  		fi
>  	done
> -	
> -	if [ -n "$identical" ]; then
> +
> +	copycommit=
> +	if [ -n "$identical" ] && [ -n "$nonidentical" ]; then
> +		extras=$(git rev-list --boundary $identical..$nonidentical)
> +		if [ -n "$extras" ]; then
> +			# we need to preserve history along the other branch
> +			copycommit=1
> +		fi
> +	fi
> +	if [ -n "$identical" ] && [ -z "$copycommit" ]; then

Typically, I'd say something about how this project uses 'test'
rather than '[' and that 'then' is placed on its own line (with no
semicolon), however, in this case, you're sticking to existing style
(in this script), so I won't mention it.

>  		echo $identical
>  	else
>  		copy_commit $rev $tree "$p" || exit $?
> diff --git a/contrib/subtree/t/t7901-subtree-split.sh b/contrib/subtree/t/t7901-subtree-split.sh
> new file mode 100755
> index 0000000..0a1ea56
> --- /dev/null
> +++ b/contrib/subtree/t/t7901-subtree-split.sh

Is there a strong reason why this demands a new test script rather
than being incorporated into the existing t7900-subtree.sh?

> @@ -0,0 +1,62 @@
> +#!/bin/bash
> +
> +test_description='Test for bug in subtree commit filtering'

A somewhat strange description. Typically, scripts want to verify
correct behavior, rather than buggy behavior.

> +TEST_DIRECTORY=$(pwd)/../../../t
> +export TEST_DIRECTORY
> +
> +. ../../../t/test-lib.sh
> +
> +
> +test_expect_success 'subtree descendent check' '
> +  mkdir git_subtree_split_check &&
> +  cd git_subtree_split_check &&

Tests don't automatically return to the directory prior to the 'cd',
so when this test ends, the current directory will still be
'git_subtree_split_check'. If someone later adds a test following
this one, that test will execute within 'git_subtree_split_check',
which might not be expected by the test writer.

To ensure that the prior working directory is restored at the end of
the test (regardless of success or failure), tests typically employ a
subshell using this idiom:

    mkdir foo &&
    (
        cd foo &&
        ... &&
        ...
    )

In this case, though, I'm wondering what is the purpose of having the
'git_subtree_split_check' subdirectory at all? Is there a reason you
can't just perform the test in the existing directory created
automatically specifically for the test script (which is already the
script's current working directory)? If, on the other hand, you
incorporate this test into t7900-subtree.sh, then the separate
'git_subtree_split_check' directory may make sense if it needs to be
isolated from the other gunk in that script's test directory.

> +  git init &&
> +
> +  mkdir folder &&
> +
> +  echo a > folder/a &&

Typical style is to drop the space after the redirection operator,
however, since you're following existing style in t7900-subtree.sh, I
won't mention it.

> +  git add . &&
> +  git commit -m "first commit" &&
> +
> +  git branch branch &&
> +
> +  echo 0 > folder/0 &&
> +  git add . &&
> +  git commit -m "adding 0 to folder" &&
> +
> +  echo b > folder/b &&
> +  git add . &&
> +  git commit -m "adding b to folder" &&
> +  git rev-list HEAD -1 > cherry.rev &&

Can this value instead just be assigned to a shell variable rather
than being dumped to a file?

    cherryrev=$(git rev-list HEAD -1) &&
    ... &&
    git cherry-pick $cherryrev &&

> +  git checkout branch &&
> +  echo text > textBranch.txt &&
> +  git add . &&
> +  git commit -m "commit to fiddle with branch: branch" &&
> +
> +  git cherry-pick $(cat cherry.rev) &&

See above: git cherry-pick $cherryrev &&

> +  git checkout master &&
> +  git merge -m "merge" branch &&
> +
> +  git branch noop_branch &&
> +
> +  echo d > folder/d &&
> +  git add . &&
> +  git commit -m "adding d to folder" &&
> +
> +  git checkout noop_branch &&
> +  echo moreText > anotherText.txt &&
> +  git add . &&
> +  git commit -m "irrelevant" &&
> +
> +  git checkout master &&
> +  git merge -m "second merge" noop_branch &&
> +
> +  git subtree split --prefix folder/ --branch subtree_tip master &&
> +  git subtree split --prefix folder/ --branch subtree_branch branch &&
> +  git push . subtree_tip:subtree_branch
> +  '
> +
> +test_done
> -- 
> 1.9.1

git subtree bug produces divergent descendants

[David Ware]

[-- Attachment #1: Type: text/plain, Size: 1491 bytes --]

My group has run into a bug with "git-subtree split". Under some
circumstances a split created from a descendant of another earlier
split is not a descendant of that earlier split (thus blocking
pushes). We originally noticed this on v1.9.1 but have also checked it
on v2.6.3

When scanning the commits to produce the subtree it seems to skip
creating a new commit if any of the parent commits have the same tree
and instead uses that tree in its place. This is fine when the cause
is a branch that did not cause any changes to the subtree.  However it
creates an issue when the cause is both branches ending up with the
same tree through identical alterations (or more likely, one of the
branches has just a subset of the alterations on the other, such as a
branch just containing cherry-picks).

The attached patch (against v2.6.3) includes a test that reproduces
the problem.  The created 'master' branch has had the latest commits
on the 'branch' branch merged into it, so it follows that a subtree on
'folder/' at 'master' (subtree_tip) should contain all the commits of
a subtree on 'folder/' at 'branch' (subtree_branch). Hence it should
be possible to push subtree_tip to subtree_branch.

The attached patch also fixes the issue for the cases we've
encountered, however since we're not particularly familiar with git
internals we may not have approached this optimally. We suspect it
could be improved to also handle the cases where there are more than 2
parents.

Cheers,
Dave Ware

[-- Attachment #2: 0001-Fix-bug-in-git-subtree-split.patch --]
[-- Type: text/x-patch, Size: 3135 bytes --]

From ce6e2bcb2116624082bf46663aa33c706fcab930 Mon Sep 17 00:00:00 2001
From: Dave Ware <davidw@netvalue.net.nz>
Date: Fri, 4 Dec 2015 16:30:03 +1300
Subject: [PATCH] Fix bug in git-subtree split.

A bug occurs in 'git-subtree split' where a merge is skipped even when
both parents act on the subtree, provided the merge results in a tree
identical to one of the parents. Fixed by copying the merge if at least
one parent is non-identical, and the non-identical parent is not an
ancestor of the identical parent.

Also adding a test case, this checks that a descendant can be pushed to
it's ancestor in this case.
---
 contrib/subtree/git-subtree.sh           | 12 +++++--
 contrib/subtree/t/t7901-subtree-split.sh | 62 ++++++++++++++++++++++++++++++++
 2 files changed, 72 insertions(+), 2 deletions(-)
 create mode 100755 contrib/subtree/t/t7901-subtree-split.sh

diff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh
index 9f06571..b837531 100755
--- a/contrib/subtree/git-subtree.sh
+++ b/contrib/subtree/git-subtree.sh
@@ -479,8 +479,16 @@ copy_or_skip()
 			p="$p -p $parent"
 		fi
 	done
-	
-	if [ -n "$identical" ]; then
+
+	copycommit=
+	if [ -n "$identical" ] && [ -n "$nonidentical" ]; then
+		extras=$(git rev-list --boundary $identical..$nonidentical)
+		if [ -n "$extras" ]; then
+			# we need to preserve history along the other branch
+			copycommit=1
+		fi
+	fi
+	if [ -n "$identical" ] && [ -z "$copycommit" ]; then
 		echo $identical
 	else
 		copy_commit $rev $tree "$p" || exit $?
diff --git a/contrib/subtree/t/t7901-subtree-split.sh b/contrib/subtree/t/t7901-subtree-split.sh
new file mode 100755
index 0000000..0a1ea56
--- /dev/null
+++ b/contrib/subtree/t/t7901-subtree-split.sh
@@ -0,0 +1,62 @@
+#!/bin/bash
+
+test_description='Test for bug in subtree commit filtering'
+
+
+TEST_DIRECTORY=$(pwd)/../../../t
+export TEST_DIRECTORY
+
+. ../../../t/test-lib.sh
+
+
+test_expect_success 'subtree descendent check' '
+  mkdir git_subtree_split_check &&
+  cd git_subtree_split_check &&
+  git init &&
+
+  mkdir folder &&
+
+  echo a > folder/a &&
+  git add . &&
+  git commit -m "first commit" &&
+
+  git branch branch &&
+
+  echo 0 > folder/0 &&
+  git add . &&
+  git commit -m "adding 0 to folder" &&
+
+  echo b > folder/b &&
+  git add . &&
+  git commit -m "adding b to folder" &&
+  git rev-list HEAD -1 > cherry.rev &&
+
+  git checkout branch &&
+  echo text > textBranch.txt &&
+  git add . &&
+  git commit -m "commit to fiddle with branch: branch" &&
+
+  git cherry-pick $(cat cherry.rev) &&
+  git checkout master &&
+  git merge -m "merge" branch &&
+
+  git branch noop_branch &&
+
+  echo d > folder/d &&
+  git add . &&
+  git commit -m "adding d to folder" &&
+
+  git checkout noop_branch &&
+  echo moreText > anotherText.txt &&
+  git add . &&
+  git commit -m "irrelevant" &&
+
+  git checkout master &&
+  git merge -m "second merge" noop_branch &&
+
+  git subtree split --prefix folder/ --branch subtree_tip master &&
+  git subtree split --prefix folder/ --branch subtree_branch branch &&
+  git push . subtree_tip:subtree_branch
+  '
+
+test_done
-- 
1.9.1