[PATCH] three --merge-order bug fixes

This patch fixes three bugs in --merge-order support
    * mark_ancestors_uninteresting was unnecessarily exponential which
      caused a problem when a commit with no parents was merged near the
      head of something like the linux kernel
    * removed a spurious statement from find_base which wasn't
      apparently causing problems now, but wasn't correct either.
    * removed an unnecessarily strict check from find_base_for_list
      that causes a problem if git-rev-list commit ^parent-of-commit
      is specified.
    * added some unit tests which were accidentally omitted from
      original merge-order patch

The fix to mark_ancestors_uninteresting isn't an optimal fix - a full
graph scan will still be performed in this case even though it is
not strictly required. However, a full graph scan is linear
and still no worse than git-rev-list HEAD which runs in less than 2
seconds on a warm cache.

Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>

2 files changed, 177 insertions, 3 deletions

diff --git a/epoch.c b/epoch.c
index ba63eac68e..3a484b00c6 100644
--- a/epoch.c
+++ b/epoch.c
@@ -229,7 +229,7 @@ static int find_base_for_list(struct commit_list *list, struct commit **boundary
 
 		struct commit *item = list->item;
 
-		if (item->object.util || (item->object.flags & UNINTERESTING)) {
+		if (item->object.util) {
 			die("%s:%d:%s: logic error: this should not have happened - commit %s\n",
 			    __FILE__, __LINE__, __FUNCTION__, sha1_to_hex(item->object.sha1));
 		}
@@ -323,7 +323,6 @@ static int find_base(struct commit *head, struct commit **boundary)
 	struct commit_list *pending = NULL;
 	struct commit_list *next;
 
-	commit_list_insert(head, &pending);
 	for (next = head->parents; next; next = next->next) {
 		commit_list_insert(next->item, &pending);
 	}
@@ -418,8 +417,8 @@ static void mark_ancestors_uninteresting(struct commit *commit)
 	int boundary = flags & BOUNDARY;
 	int uninteresting = flags & UNINTERESTING;
 
+	commit->object.flags |= UNINTERESTING;
 	if (uninteresting || boundary || !visited) {
-		commit->object.flags |= UNINTERESTING;
 		return;
 
 		// we only need to recurse if
diff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh
new file mode 100644
index 0000000000..35f1676224
--- /dev/null
+++ b/t/t6001-rev-list-merge-order.sh
@@ -0,0 +1,175 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Jon Seymour
+#
+
+test_description='Test rev-list --merge-order
+'
+. ./test-lib.sh
+
+function do_commit
+{
+    git-commit-tree "$@" </dev/null
+}
+
+function check_adjacency
+{
+    read previous
+    echo "= $previous"
+    while read next
+    do
+        if ! (git-cat-file commit $previous | grep "^parent $next" >/dev/null)
+        then
+            echo "^ $next"
+        else
+            echo "| $next"
+        fi
+        previous=$next
+    done
+}
+
+function sed_script
+{
+   for c in root a0 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 l0 l1 l2 l3 l4 l5
+   do
+       echo -n "s/${!c}/$c/;"
+   done
+}
+
+date >path0
+git-update-cache --add path0
+tree=$(git-write-tree)
+root=$(do_commit $tree 2>/dev/null)
+export GIT_COMMITTER_NAME=foobar  # to guarantee that the commit is different
+l0=$(do_commit $tree -p $root)
+l1=$(do_commit $tree -p $l0)
+l2=$(do_commit $tree -p $l1)
+a0=$(do_commit $tree -p $l2)
+a1=$(do_commit $tree -p $a0)
+export GIT_COMMITTER_NAME=foobar2 # to guarantee that the commit is different
+b1=$(do_commit $tree -p $a0)
+c1=$(do_commit $tree -p $b1)
+export GIT_COMMITTER_NAME=foobar3 # to guarantee that the commit is different
+b2=$(do_commit $tree -p $b1)
+b3=$(do_commit $tree -p $b2)
+c2=$(do_commit $tree -p $c1 -p $b2)
+c3=$(do_commit $tree -p $c2)
+a2=$(do_commit $tree -p $a1)
+a3=$(do_commit $tree -p $a2)
+b4=$(do_commit $tree -p $b3 -p $a3)
+a4=$(do_commit $tree -p $a3 -p $b4 -p $c3)
+l3=$(do_commit $tree -p $a4)
+l4=$(do_commit $tree -p $l3)
+l5=$(do_commit $tree -p $l4)
+echo $l5 > .git/HEAD
+
+git-rev-list --merge-order --show-breaks HEAD | sed "$(sed_script)" > actual-merge-order
+cat > expected-merge-order <<EOF
+= l5
+| l4
+| l3
+= a4
+| c3
+| c2
+| c1
+^ b4
+| b3
+| b2
+| b1
+^ a3
+| a2
+| a1
+= a0
+| l2
+| l1
+| l0
+= root
+EOF
+
+git-rev-list HEAD | check_adjacency | sed "$(sed_script)" > actual-default-order
+normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
+merge_order_adjacency_count=$(git-rev-list --merge-order HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
+
+test_expect_success 'Testing that the rev-list has correct number of entries' '[ $(git-rev-list HEAD | wc -l) -eq 19 ]'
+test_expect_success 'Testing that --merge-order produces the correct result' 'diff expected-merge-order actual-merge-order'
+test_expect_success 'Testing that --merge-order produces as many or fewer discontinuities' '[ $merge_order_adjacency_count -le $normal_adjacency_count ]'
+
+cat > expected-merge-order-1 <<EOF
+c3
+c2
+c1
+b3
+b2
+b1
+a3
+a2
+a1
+a0
+l2
+l1
+l0
+root
+EOF
+
+git-rev-list --merge-order $a3 $b3 $c3 | sed "$(sed_script)" > actual-merge-order-1
+test_expect_success 'Testing multiple heads' 'diff expected-merge-order-1 actual-merge-order-1'
+
+cat > expected-merge-order-2 <<EOF
+c3
+c2
+c1
+b3
+b2
+b1
+a3
+a2
+EOF
+
+git-rev-list --merge-order $a3 $b3 $c3 ^$a1 | sed "$(sed_script)" > actual-merge-order-2
+test_expect_success 'Testing stop' 'diff expected-merge-order-2 actual-merge-order-2'
+
+cat > expected-merge-order-3 <<EOF
+c3
+c2
+c1
+b3
+b2
+b1
+a3
+a2
+a1
+a0
+l2
+EOF
+
+git-rev-list --merge-order $a3 $b3 $c3 ^$l1 | sed "$(sed_script)" > actual-merge-order-3
+test_expect_success 'Testing stop in linear epoch' 'diff expected-merge-order-3 actual-merge-order-3'
+
+cat > expected-merge-order-4 <<EOF
+l5
+l4
+l3
+a4
+c3
+c2
+c1
+b4
+b3
+b2
+b1
+a3
+a2
+a1
+a0
+l2
+EOF
+
+git-rev-list --merge-order $l5 ^$l1 | sed "$(sed_script)" > actual-merge-order-4
+test_expect_success 'Testing start in linear epoch, stop after non-linear epoch' 'diff expected-merge-order-4 actual-merge-order-4'
+
+git-rev-list --merge-order $l5 $l5 ^$l1 2>/dev/null | sed "$(sed_script)" > actual-merge-order-5
+test_expect_success 'Testing duplicated start arguments' 'diff expected-merge-order-4 actual-merge-order-5'
+
+test_expect_success 'Testing exclusion near merge' 'git-rev-list --merge-order $a4 ^$c3 2>/dev/null'
+
+test_done