{"thread":{"id":"862","subject":"[PATCH] three --merge-order bug fixes","startedAt":"2005-06-08T14:37:41Z","lastAt":"2005-06-08T16:04:01Z","messageCount":2,"participants":["Jon Seymour","Radoslaw Szkodzinski"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"4699","messageId":"20050608143741.30382.qmail@blackcubes.dyndns.org","threadId":"862","inReplyTo":null,"subject":"[PATCH] three --merge-order bug fixes","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-08T14:37:41Z","receivedAt":"2005-06-08T14:37:41Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"[PATCH] three --merge-order bug fixes\n\nThis patch fixes three bugs in --merge-order support\n    * mark_ancestors_uninteresting was unnecessarily exponential which \n      caused a problem when a commit with no parents was merged near the \n      head of something like the linux kernel\n    * removed a spurious statement from find_base which wasn't\n      apparently causing problems now, but wasn't correct either.\n    * removed an unnecessarily strict check from find_base_for_list\n      that causes a problem if git-rev-list commit ^parent-of-commit \n      is specified.\n    * added some unit tests which were accidentally omitted from\n      original merge-order patch\n\nThe fix to mark_ancestors_uninteresting isn't an optimal fix - a full\ngraph scan will still be performed in this case even though it is\nnot strictly required. However, a full graph scan is linear \nand still no worse than git-rev-list HEAD which runs in less than 2\nseconds on a warm cache.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n\nDiverged from fcbfd5a6b2c87dc5ecd1d6c4e94c56eebf44c8ac by Linus Torvalds <torvalds@ppc970.osdl.org>\n---\ndiff --git a/epoch.c b/epoch.c\n--- a/epoch.c\n+++ b/epoch.c\n@@ -229,7 +229,7 @@ static int find_base_for_list(struct com\n \n \t\tstruct commit *item = list->item;\n \n-\t\tif (item->object.util || (item->object.flags & UNINTERESTING)) {\n+\t\tif (item->object.util) {\n \t\t\tdie(\"%s:%d:%s: logic error: this should not have happened - commit %s\\n\",\n \t\t\t    __FILE__, __LINE__, __FUNCTION__, sha1_to_hex(item->object.sha1));\n \t\t}\n@@ -323,7 +323,6 @@ static int find_base(struct commit *head\n \tstruct commit_list *pending = NULL;\n \tstruct commit_list *next;\n \n-\tcommit_list_insert(head, &pending);\n \tfor (next = head->parents; next; next = next->next) {\n \t\tcommit_list_insert(next->item, &pending);\n \t}\n@@ -418,8 +417,8 @@ static void mark_ancestors_uninteresting\n \tint boundary = flags & BOUNDARY;\n \tint uninteresting = flags & UNINTERESTING;\n \n+\tcommit->object.flags |= UNINTERESTING;\n \tif (uninteresting || boundary || !visited) {\n-\t\tcommit->object.flags |= UNINTERESTING;\n \t\treturn;\n \n \t\t// we only need to recurse if\ndiff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh\nnew file mode 100644\n--- /dev/null\n+++ b/t/t6001-rev-list-merge-order.sh\n@@ -0,0 +1,175 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2005 Jon Seymour\n+#\n+\n+test_description='Test rev-list --merge-order\n+'\n+. ./test-lib.sh\n+\n+function do_commit\n+{\n+    git-commit-tree \"$@\" </dev/null\n+}\n+\n+function check_adjacency\n+{\n+    read previous\n+    echo \"= $previous\"\n+    while read next\n+    do\n+        if ! (git-cat-file commit $previous | grep \"^parent $next\" >/dev/null)\n+        then\n+            echo \"^ $next\"\n+        else\n+            echo \"| $next\"\n+        fi\n+        previous=$next\n+    done\n+}\n+\n+function sed_script\n+{\n+   for c in root a0 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 l0 l1 l2 l3 l4 l5\n+   do\n+       echo -n \"s/${!c}/$c/;\"\n+   done\n+}\n+\n+date >path0\n+git-update-cache --add path0\n+tree=$(git-write-tree)\n+root=$(do_commit $tree 2>/dev/null)\n+export GIT_COMMITTER_NAME=foobar  # to guarantee that the commit is different\n+l0=$(do_commit $tree -p $root)\n+l1=$(do_commit $tree -p $l0)\n+l2=$(do_commit $tree -p $l1)\n+a0=$(do_commit $tree -p $l2)\n+a1=$(do_commit $tree -p $a0)\n+export GIT_COMMITTER_NAME=foobar2 # to guarantee that the commit is different\n+b1=$(do_commit $tree -p $a0)\n+c1=$(do_commit $tree -p $b1)\n+export GIT_COMMITTER_NAME=foobar3 # to guarantee that the commit is different\n+b2=$(do_commit $tree -p $b1)\n+b3=$(do_commit $tree -p $b2)\n+c2=$(do_commit $tree -p $c1 -p $b2)\n+c3=$(do_commit $tree -p $c2)\n+a2=$(do_commit $tree -p $a1)\n+a3=$(do_commit $tree -p $a2)\n+b4=$(do_commit $tree -p $b3 -p $a3)\n+a4=$(do_commit $tree -p $a3 -p $b4 -p $c3)\n+l3=$(do_commit $tree -p $a4)\n+l4=$(do_commit $tree -p $l3)\n+l5=$(do_commit $tree -p $l4)\n+echo $l5 > .git/HEAD\n+\n+git-rev-list --merge-order --show-breaks HEAD | sed \"$(sed_script)\" > actual-merge-order\n+cat > expected-merge-order <<EOF\n+= l5\n+| l4\n+| l3\n+= a4\n+| c3\n+| c2\n+| c1\n+^ b4\n+| b3\n+| b2\n+| b1\n+^ a3\n+| a2\n+| a1\n+= a0\n+| l2\n+| l1\n+| l0\n+= root\n+EOF\n+\n+git-rev-list HEAD | check_adjacency | sed \"$(sed_script)\" > actual-default-order\n+normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep -c \"\\^\" | tr -d ' ')\n+merge_order_adjacency_count=$(git-rev-list --merge-order HEAD | check_adjacency | grep -c \"\\^\" | tr -d ' ')\n+\n+test_expect_success 'Testing that the rev-list has correct number of entries' '[ $(git-rev-list HEAD | wc -l) -eq 19 ]'\n+test_expect_success 'Testing that --merge-order produces the correct result' 'diff expected-merge-order actual-merge-order'\n+test_expect_success 'Testing that --merge-order produces as many or fewer discontinuities' '[ $merge_order_adjacency_count -le $normal_adjacency_count ]'\n+\n+cat > expected-merge-order-1 <<EOF\n+c3\n+c2\n+c1\n+b3\n+b2\n+b1\n+a3\n+a2\n+a1\n+a0\n+l2\n+l1\n+l0\n+root\n+EOF\n+\n+git-rev-list --merge-order $a3 $b3 $c3 | sed \"$(sed_script)\" > actual-merge-order-1\n+test_expect_success 'Testing multiple heads' 'diff expected-merge-order-1 actual-merge-order-1'\n+\n+cat > expected-merge-order-2 <<EOF\n+c3\n+c2\n+c1\n+b3\n+b2\n+b1\n+a3\n+a2\n+EOF\n+\n+git-rev-list --merge-order $a3 $b3 $c3 ^$a1 | sed \"$(sed_script)\" > actual-merge-order-2\n+test_expect_success 'Testing stop' 'diff expected-merge-order-2 actual-merge-order-2'\n+\n+cat > expected-merge-order-3 <<EOF\n+c3\n+c2\n+c1\n+b3\n+b2\n+b1\n+a3\n+a2\n+a1\n+a0\n+l2\n+EOF\n+\n+git-rev-list --merge-order $a3 $b3 $c3 ^$l1 | sed \"$(sed_script)\" > actual-merge-order-3\n+test_expect_success 'Testing stop in linear epoch' 'diff expected-merge-order-3 actual-merge-order-3'\n+\n+cat > expected-merge-order-4 <<EOF\n+l5\n+l4\n+l3\n+a4\n+c3\n+c2\n+c1\n+b4\n+b3\n+b2\n+b1\n+a3\n+a2\n+a1\n+a0\n+l2\n+EOF\n+\n+git-rev-list --merge-order $l5 ^$l1 | sed \"$(sed_script)\" > actual-merge-order-4\n+test_expect_success 'Testing start in linear epoch, stop after non-linear epoch' 'diff expected-merge-order-4 actual-merge-order-4'\n+\n+git-rev-list --merge-order $l5 $l5 ^$l1 2>/dev/null | sed \"$(sed_script)\" > actual-merge-order-5\n+test_expect_success 'Testing duplicated start arguments' 'diff expected-merge-order-4 actual-merge-order-5'\n+\n+test_expect_success 'Testing exclusion near merge' 'git-rev-list --merge-order $a4 ^$c3 2>/dev/null'\n+\n+test_done\n"},{"id":"4703","messageId":"42A716F1.7010805@gorzow.mm.pl","threadId":"862","inReplyTo":"20050608143741.30382.qmail@blackcubes.dyndns.org","subject":"Re: [PATCH] three --merge-order bug fixes","fromName":"Radoslaw Szkodzinski","fromEmail":"astralstorm@gorzow.mm.pl","sentAt":"2005-06-08T16:04:01Z","receivedAt":"2005-06-08T16:04:01Z","isPatch":true,"sender":{"key":"astralstorm@gorzow.mm.pl","avatar":null},"body":"Jon Seymour wrote:\n\n>[PATCH] three --merge-order bug fixes\n>  \n>\nThe patch fixes the problem I reported. Well done.\nPlease apply.\n\nAstralStorm\n"}]}