threads / patch / 14952

patch, 3 partsfilter-branch: Extend test to show rewriting bug

Subject: [PATCH 1/3] filter-branch: Extend test to show rewriting bug

## tl;dr

5 messages between Aug 12, 2008 and Aug 12, 2008. Diffs are folded; open one to read it.

replies: 4people: 2as markdown or json

Thomas Rast· Aug 12, 2008, 08:45 UTC · lore

[PATCH 0/3] filter-branch --subdirectory-filter improvements

Junio C Hamano wrote:
> Anything parked in 'pu' is a fair game for replacement later, so please
> send a replacement series and tell me to drop the previous ones from 'pu'.

So let's try this one. The first two do not depend on --simplify-merges.

1/3 is new, and extends the --subdirectory-filter test to prove the existence of the bug in current filter-branch. I hope it helps explain the issue.

2/3 is the same as before[*] modulo changing the test to expect success again.

The third one does depend on --simplify-merges.

3/3 introduces --simplify-merges, which improves the history that results from --subdirectory-filter. It has absolutely nothing to do with 2/3, except that it touches the same area of code. (You could s/rev-list/rev-list --simplify-merges/ in master:git-filter-branch.sh, and get the improved history without the bugfix.)

Sorry that I dispersed the patches and v2s randomly across the thread.
- Thomas

[*] http://kerneltrap.org/mailarchive/git/2008/8/8/2867244 "[PATCH v2] filter-branch: fix ref rewriting with --subdirectory-filter"

Thomas Rast (3):
  filter-branch: Extend test to show rewriting bug
  filter-branch: fix ref rewriting with --subdirectory-filter
  filter-branch: use --simplify-merges
Thomas Rast· Aug 12, 2008, 08:45 UTC · re: Thomas Rast · lore

This extends the --subdirectory-filter test in t7003 to demonstrate a rewriting bug: when rewriting two refs A and B such that B is an ancestor of A, it fails to rewrite B.

The underlying issue is that the rev-list invocation at git-filter-branch.sh:332 more or less boils down to

  git rev-list B --boundary ^A
which outputs nothing because B is an ancestor of A.
Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 t/t7003-filter-branch.sh |   10 +++++++---
 1 files changed, 7 insertions(+), 3 deletions(-)
Show changes to t/t7003-filter-branch.sh +7 −3
diff --git a/t/t7003-filter-branch.sh b/t/t7003-filter-branch.sh
index a0ab096..4382baa 100755
--- a/t/t7003-filter-branch.sh
+++ b/t/t7003-filter-branch.sh
@@ -96,13 +96,17 @@ test_expect_success 'filter subdirectory only' '
 	test_tick &&
 	git commit -m "again not subdir" &&
 	git branch sub &&
-	git-filter-branch -f --subdirectory-filter subdir refs/heads/sub
+	git branch sub-earlier HEAD~2 &&
+	git-filter-branch -f --subdirectory-filter subdir \
+		refs/heads/sub refs/heads/sub-earlier
 '
 
-test_expect_success 'subdirectory filter result looks okay' '
+test_expect_failure 'subdirectory filter result looks okay' '
 	test 2 = $(git rev-list sub | wc -l) &&
 	git show sub:new &&
-	test_must_fail git show sub:subdir
+	test_must_fail git show sub:subdir &&
+	git show sub-earlier:new &&
+	test_must_fail git show sub-earlier:subdir
 '
 
 test_expect_success 'more setup' '
-- 
1.6.0.rc2.30.gb6bda
Thomas Rast· Aug 12, 2008, 08:45 UTC · re: Thomas Rast · lore

[PATCH 2/3] filter-branch: fix ref rewriting with --subdirectory-filter

The previous ancestor discovery code failed on any refs that are (pre-rewrite) ancestors of commits marked for rewriting. This means that in a situation

   A -- B(topic) -- C(master)

where B is dropped by --subdirectory-filter pruning, the 'topic' was not moved up to A as intended, but left unrewritten because we asked about 'git rev-list ^master topic', which does not return anything.

Instead, we use the straightforward
   git rev-list -1 $ref -- $filter_subdir

to find the right ancestor. To justify this, note that the nearest ancestor is unique: We use the output of

  git rev-list --parents -- $filter_subdir

to rewrite commits in the first pass, before any ref rewriting. If B is a non-merge commit, the only candidate is its parent. If it is a merge, there are two cases:

- All sides of the merge bring the same subdirectory contents.  Then
  rev-list already pruned away the merge in favour for just one of its
  parents, so there is only one candidate.
- Some merge sides, or the merge outcome, differ.  Then the merge is
  not pruned and can be rewritten directly.
So it is always safe to use rev-list -1.
Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 git-filter-branch.sh     |   27 +++++++++++----------------
 t/t7003-filter-branch.sh |    2 +-
 2 files changed, 12 insertions(+), 17 deletions(-)
Show changes to 2 files +12 −17

git-filter-branch.sh, t/t7003-filter-branch.sh

diff --git a/git-filter-branch.sh b/git-filter-branch.sh
index a324cf0..a140337 100755
--- a/git-filter-branch.sh
+++ b/git-filter-branch.sh
@@ -317,24 +317,19 @@ done <../revs
 
 # In case of a subdirectory filter, it is possible that a specified head
 # is not in the set of rewritten commits, because it was pruned by the
-# revision walker.  Fix it by mapping these heads to the next rewritten
-# ancestor(s), i.e. the boundaries in the set of rewritten commits.
+# revision walker.  Fix it by mapping these heads to the unique nearest
+# ancestor that survived the pruning.
 
-# NEEDSWORK: we should sort the unmapped refs topologically first
-while read ref
-do
-	sha1=$(git rev-parse "$ref"^0)
-	test -f "$workdir"/../map/$sha1 && continue
-	# Assign the boundarie(s) in the set of rewritten commits
-	# as the replacement commit(s).
-	# (This would look a bit nicer if --not --stdin worked.)
-	for p in $( (cd "$workdir"/../map; ls | sed "s/^/^/") |
-		git rev-list $ref --boundary --stdin |
-		sed -n "s/^-//p")
+if test "$filter_subdir"
+then
+	while read ref
 	do
-		map $p >> "$workdir"/../map/$sha1
-	done
-done < "$tempdir"/heads
+		sha1=$(git rev-parse "$ref"^0)
+		test -f "$workdir"/../map/$sha1 && continue
+		ancestor=$(git rev-list -1 $ref -- "$filter_subdir")
+		test "$ancestor" && echo $(map $ancestor) >> "$workdir"/../map/$sha1
+	done < "$tempdir"/heads
+fi
 
 # Finally update the refs
 
diff --git a/t/t7003-filter-branch.sh b/t/t7003-filter-branch.sh
index 4382baa..233254f 100755
--- a/t/t7003-filter-branch.sh
+++ b/t/t7003-filter-branch.sh
@@ -101,7 +101,7 @@ test_expect_success 'filter subdirectory only' '
 		refs/heads/sub refs/heads/sub-earlier
 '
 
-test_expect_failure 'subdirectory filter result looks okay' '
+test_expect_success 'subdirectory filter result looks okay' '
 	test 2 = $(git rev-list sub | wc -l) &&
 	git show sub:new &&
 	test_must_fail git show sub:subdir &&
-- 
1.6.0.rc2.30.gb6bda
Thomas Rast· Aug 12, 2008, 08:45 UTC · re: Thomas Rast · lore

[PATCH 3/3] filter-branch: use --simplify-merges

Use rev-list --simplify-merges everywhere. This changes the behaviour of --subdirectory-filter in cases such as

  O -- A -\
   \       \
    \- B -- M

where A and B bring the same changes to the subdirectory: It now keeps both sides of the merge. Previously, the history would have been simplified to 'O -- A'. Merges of unrelated side histories that never touch the subdirectory are still removed.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 git-filter-branch.sh |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)
Show changes to git-filter-branch.sh +4 −3
diff --git a/git-filter-branch.sh b/git-filter-branch.sh
index a140337..2688254 100755
--- a/git-filter-branch.sh
+++ b/git-filter-branch.sh
@@ -232,11 +232,11 @@ mkdir ../map || die "Could not create map/ directory"
 case "$filter_subdir" in
 "")
 	git rev-list --reverse --topo-order --default HEAD \
-		--parents "$@"
+		--parents --simplify-merges "$@"
 	;;
 *)
 	git rev-list --reverse --topo-order --default HEAD \
-		--parents "$@" -- "$filter_subdir"
+		--parents --simplify-merges "$@" -- "$filter_subdir"
 esac > ../revs || die "Could not get the commits"
 commits=$(wc -l <../revs | tr -d " ")
 
@@ -326,7 +326,8 @@ then
 	do
 		sha1=$(git rev-parse "$ref"^0)
 		test -f "$workdir"/../map/$sha1 && continue
-		ancestor=$(git rev-list -1 $ref -- "$filter_subdir")
+		ancestor=$(git rev-list --simplify-merges -1 \
+				$ref -- "$filter_subdir")
 		test "$ancestor" && echo $(map $ancestor) >> "$workdir"/../map/$sha1
 	done < "$tempdir"/heads
 fi
-- 
1.6.0.rc2.30.gb6bda
Jan Wielemaker· Aug 12, 2008, 12:11 UTC · re: Thomas Rast · lore

Re: [PATCH 0/3] filter-branch --subdirectory-filter improvements

On Tuesday 12 August 2008 10:45:56 am Thomas Rast wrote:
Show 7 quoted lines
> Junio C Hamano wrote:
> > Anything parked in 'pu' is a fair game for replacement later, so please
> > send a replacement series and tell me to drop the previous ones from
> > 'pu'.
>
> So let's try this one.  The first two do not depend on
> --simplify-merges.

And I can confirm that (2) is a very important fix and (3) is a necessary step to achieve what I believe --subdirectory-filter is meant for: extract a directory from a big project and turn it into stand-alone project. In this case I want:

	% filter out dir X, creating X.git
	% git rm -r X
	% git submodule add <url> X

And someone with a totally unrelated project adds X.git to his project. That requires the history of X to become totally independent from the original project.

This works great with Thomas' patches.
	Cheers --- Jan
P.s.	Note that this is a common problem for people moving from some
	unnamed ancient SCM system, either transferring a repository or
	simply starting the wrong way due to historical brainwashing :-)
Show 27 quoted lines
> 1/3 is new, and extends the --subdirectory-filter test to prove the
> existence of the bug in current filter-branch.  I hope it helps
> explain the issue.
>
> 2/3 is the same as before[*] modulo changing the test to expect
> success again.
>
> The third one does depend on --simplify-merges.
>
> 3/3 introduces --simplify-merges, which improves the history that
> results from --subdirectory-filter.  It has absolutely nothing to do
> with 2/3, except that it touches the same area of code.  (You could
> s/rev-list/rev-list --simplify-merges/ in master:git-filter-branch.sh,
> and get the improved history without the bugfix.)
>
> Sorry that I dispersed the patches and v2s randomly across the thread.
>
> - Thomas
>
> [*] http://kerneltrap.org/mailarchive/git/2008/8/8/2867244
> "[PATCH v2] filter-branch: fix ref rewriting with --subdirectory-filter"
>
>
> Thomas Rast (3):
>   filter-branch: Extend test to show rewriting bug
>   filter-branch: fix ref rewriting with --subdirectory-filter
>   filter-branch: use --simplify-merges

← back to recent threads