* [PATCH] Make O(n) algorithm the default implementation of --bisect
From: Jon Seymour @ 2005-07-01 6:31 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch makes the O(n) the default implementation of the git-rev-list
--bisect switch.
The original O(n^2) algorithm is still available as --bisect-orig.
It is left around to provide a quick and simple way to verify the
accuracy of the O(n) algorithm.
A subsequent patch is supplied to remove support for --bisect-orig
completely.
Signed-off: Jon Seymour <jon.seymour@gmail.com>
---
Linus: you may choose to defer application of this patch if you are
not confident that the O(n) algorithm is good.
---
rev-list.c | 5 +++--
1 files changed, 3 insertions(+), 2 deletions(-)
342b91442a303b222f1601ef34ef37fffe5a9d57
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -16,6 +16,7 @@ static const char rev_list_usage[] =
" --min-age=epoch\n"
" --header\n"
" --pretty\n"
+ " --bisect\n"
" --merge-order [ --show-breaks ]";
static int bisect_list = 0;
@@ -365,11 +366,11 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
- if (!strcmp(arg, "--bisect-by-cut")) {
+ if (!strcmp(arg, "--bisect")) {
bisect_by_cut_option = 1;
continue;
}
- if (!strcmp(arg, "--bisect")) {
+ if (!strcmp(arg, "--bisect-orig")) {
bisect_list = 1;
continue;
}
------------
^ permalink raw reply
* [PATCH] Factor out useful test case infrastructure from t/t6001... into t/t6000-lib.sh
From: Jon Seymour @ 2005-07-01 6:31 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
Functions that are useful to other t6xxx testcases are moved into t6000-lib.sh
To use these functions in a test case, use a test-case pre-amble like:
. ./test-lib.sh
. ../t6000-lib.sh # t6xxx specific functions
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
t/t6000-lib.sh | 105 +++++++++++++++++++++++++++++++++++++
t/t6001-rev-list-merge-order.sh | 112 ---------------------------------------
2 files changed, 106 insertions(+), 111 deletions(-)
create mode 100644 t/t6000-lib.sh
127ff5409fda605196f4a237b1c075f3b5b2a0b6
diff --git a/t/t6000-lib.sh b/t/t6000-lib.sh
new file mode 100644
--- /dev/null
+++ b/t/t6000-lib.sh
@@ -0,0 +1,105 @@
+[ -d .git/refs/tags ] || mkdir -p .git/refs/tags
+
+sed_script="";
+
+# Answer the sha1 has associated with the tag. The tag must exist in .git or .git/refs/tags
+tag()
+{
+ _tag=$1
+ [ -f .git/refs/tags/$_tag ] || error "tag: \"$_tag\" does not exist"
+ cat .git/refs/tags/$_tag
+}
+
+# Generate a commit using the text specified to make it unique and the tree
+# named by the tag specified.
+unique_commit()
+{
+ _text=$1
+ _tree=$2
+ shift 2
+ echo $_text | git-commit-tree $(tag $_tree) "$@"
+}
+
+# Save the output of a command into the tag specified. Prepend
+# a substitution script for the tag onto the front of $sed_script
+save_tag()
+{
+ _tag=$1
+ [ -n "$_tag" ] || error "usage: save_tag tag commit-args ..."
+ shift 1
+ "$@" >.git/refs/tags/$_tag
+ sed_script="s/$(tag $_tag)/$_tag/g${sed_script+;}$sed_script"
+}
+
+# Replace unhelpful sha1 hashses with their symbolic equivalents
+entag()
+{
+ sed "$sed_script"
+}
+
+# Execute a command after first saving, then setting the GIT_AUTHOR_EMAIL
+# tag to a specified value. Restore the original value on return.
+as_author()
+{
+ _author=$1
+ shift 1
+ _save=$GIT_AUTHOR_EMAIL
+
+ export GIT_AUTHOR_EMAIL="$_author"
+ "$@"
+ export GIT_AUTHOR_EMAIL="$_save"
+}
+
+commit_date()
+{
+ _commit=$1
+ git-cat-file commit $_commit | sed -n "s/^committer .*> \([0-9]*\) .*/\1/p"
+}
+
+on_committer_date()
+{
+ _date=$1
+ shift 1
+ GIT_COMMITTER_DATE=$_date "$@"
+}
+
+# Execute a command and suppress any error output.
+hide_error()
+{
+ "$@" 2>/dev/null
+}
+
+check_output()
+{
+ _name=$1
+ shift 1
+ if eval "$*" | entag > $_name.actual
+ then
+ diff $_name.expected $_name.actual
+ else
+ return 1;
+ fi
+}
+
+# Turn a reasonable test description into a reasonable test name.
+# All alphanums translated into -'s which are then compressed and stripped
+# from front and back.
+name_from_description()
+{
+ tr "'" '-' | tr '~`!@#$%^&*()_+={}[]|\;:"<>,/? ' '-' | tr -s '-' | tr '[A-Z]' '[a-z]' | sed "s/^-*//;s/-*\$//"
+}
+
+
+# Execute the test described by the first argument, by eval'ing
+# command line specified in the 2nd argument. Check the status code
+# is zero and that the output matches the stream read from
+# stdin.
+test_output_expect_success()
+{
+ _description=$1
+ _test=$2
+ [ $# -eq 2 ] || error "usage: test_output_expect_success description test <<EOF ... EOF"
+ _name=$(echo $_description | name_from_description)
+ cat > $_name.expected
+ test_expect_success "$_description" "check_output $_name \"$_test\""
+}
diff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh
--- a/t/t6001-rev-list-merge-order.sh
+++ b/t/t6001-rev-list-merge-order.sh
@@ -6,117 +6,7 @@
test_description='Tests git-rev-list --merge-order functionality'
. ./test-lib.sh
-
-#
-# TODO: move the following block (upto --- end ...) into testlib.sh
-#
-[ -d .git/refs/tags ] || mkdir -p .git/refs/tags
-
-sed_script="";
-
-# Answer the sha1 has associated with the tag. The tag must exist in .git or .git/refs/tags
-tag()
-{
- _tag=$1
- [ -f .git/refs/tags/$_tag ] || error "tag: \"$_tag\" does not exist"
- cat .git/refs/tags/$_tag
-}
-
-# Generate a commit using the text specified to make it unique and the tree
-# named by the tag specified.
-unique_commit()
-{
- _text=$1
- _tree=$2
- shift 2
- echo $_text | git-commit-tree $(tag $_tree) "$@"
-}
-
-# Save the output of a command into the tag specified. Prepend
-# a substitution script for the tag onto the front of $sed_script
-save_tag()
-{
- _tag=$1
- [ -n "$_tag" ] || error "usage: save_tag tag commit-args ..."
- shift 1
- "$@" >.git/refs/tags/$_tag
- sed_script="s/$(tag $_tag)/$_tag/g${sed_script+;}$sed_script"
-}
-
-# Replace unhelpful sha1 hashses with their symbolic equivalents
-entag()
-{
- sed "$sed_script"
-}
-
-# Execute a command after first saving, then setting the GIT_AUTHOR_EMAIL
-# tag to a specified value. Restore the original value on return.
-as_author()
-{
- _author=$1
- shift 1
- _save=$GIT_AUTHOR_EMAIL
-
- export GIT_AUTHOR_EMAIL="$_author"
- "$@"
- export GIT_AUTHOR_EMAIL="$_save"
-}
-
-commit_date()
-{
- _commit=$1
- git-cat-file commit $_commit | sed -n "s/^committer .*> \([0-9]*\) .*/\1/p"
-}
-
-on_committer_date()
-{
- _date=$1
- shift 1
- GIT_COMMITTER_DATE=$_date "$@"
-}
-
-# Execute a command and suppress any error output.
-hide_error()
-{
- "$@" 2>/dev/null
-}
-
-check_output()
-{
- _name=$1
- shift 1
- if eval "$*" | entag > $_name.actual
- then
- diff $_name.expected $_name.actual
- else
- return 1;
- fi
-}
-
-# Turn a reasonable test description into a reasonable test name.
-# All alphanums translated into -'s which are then compressed and stripped
-# from front and back.
-name_from_description()
-{
- tr "'" '-' | tr '~`!@#$%^&*()_+={}[]|\;:"<>,/? ' '-' | tr -s '-' | tr '[A-Z]' '[a-z]' | sed "s/^-*//;s/-*\$//"
-}
-
-
-# Execute the test described by the first argument, by eval'ing
-# command line specified in the 2nd argument. Check the status code
-# is zero and that the output matches the stream read from
-# stdin.
-test_output_expect_success()
-{
- _description=$1
- _test=$2
- [ $# -eq 2 ] || error "usage: test_output_expect_success description test <<EOF ... EOF"
- _name=$(echo $_description | name_from_description)
- cat > $_name.expected
- test_expect_success "$_description" "check_output $_name \"$_test\""
-}
-
-# --- end of stuff to move ---
+. ../t6000-lib.sh # t6xxx specific functions
# test-case specific test function
check_adjacency()
------------
^ permalink raw reply
* [PATCH] Introduce unit tests for git-rev-list --bisect
From: Jon Seymour @ 2005-07-01 6:31 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch introduces some unit tests for the git-rev-list --bisect functionality.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
t/t6002-rev-list-bisect.sh | 247 ++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 247 insertions(+), 0 deletions(-)
create mode 100755 t/t6002-rev-list-bisect.sh
e733f670291290de2a7821e02eeb2a27f133aac0
diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
new file mode 100755
--- /dev/null
+++ b/t/t6002-rev-list-bisect.sh
@@ -0,0 +1,247 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Jon Seymour
+#
+test_description='Tests git-rev-list --bisect functionality'
+
+. ./test-lib.sh
+. ../t6000-lib.sh
+
+bc_expr()
+{
+bc <<EOF
+scale=1
+define abs(x) { if (x>=0) { return x; } else { return -x; } }
+define floor(x) { save=scale; scale=0; result=x/1; scale=save; return result; }
+$*
+EOF
+}
+
+# usage: test_bisection max-diff bisect-option head ^prune...
+#
+# e.g. test_bisection 1 --bisect l1 ^l0
+#
+test_bisection_diff()
+{
+ _max_diff=$1
+ _bisect_option=$2
+ shift 2
+ _bisection=$(git-rev-list $_bisect_option "$@")
+ _list_size=$(git-rev-list "$@" | wc -l)
+ _head=$1
+ shift 1
+ _bisection_size=$(git-rev-list $_bisection "$@" | wc -l)
+ [ -n "$_list_size" -a -n "$_bisection_size" ] || error "test_bisection_diff failed"
+ test_expect_success "bisection diff $_bisect_option $_head $* <= $_max_diff" "[ $(bc_expr "floor(abs($_list_size/2)-$_bisection_size)") -le $_max_diff ]"
+}
+
+date >path0
+git-update-cache --add path0
+save_tag tree git-write-tree
+on_committer_date "1971-08-16 00:00:00" hide_error save_tag root unique_commit root tree
+on_committer_date "1971-08-16 00:00:01" save_tag l0 unique_commit l0 tree -p root
+on_committer_date "1971-08-16 00:00:02" save_tag l1 unique_commit l1 tree -p l0
+on_committer_date "1971-08-16 00:00:03" save_tag l2 unique_commit l2 tree -p l1
+on_committer_date "1971-08-16 00:00:04" save_tag a0 unique_commit a0 tree -p l2
+on_committer_date "1971-08-16 00:00:05" save_tag a1 unique_commit a1 tree -p a0
+on_committer_date "1971-08-16 00:00:06" save_tag b1 unique_commit b1 tree -p a0
+on_committer_date "1971-08-16 00:00:07" save_tag c1 unique_commit c1 tree -p b1
+on_committer_date "1971-08-16 00:00:08" save_tag b2 unique_commit b2 tree -p b1
+on_committer_date "1971-08-16 00:00:09" save_tag b3 unique_commit b2 tree -p b2
+on_committer_date "1971-08-16 00:00:10" save_tag c2 unique_commit c2 tree -p c1 -p b2
+on_committer_date "1971-08-16 00:00:11" save_tag c3 unique_commit c3 tree -p c2
+on_committer_date "1971-08-16 00:00:12" save_tag a2 unique_commit a2 tree -p a1
+on_committer_date "1971-08-16 00:00:13" save_tag a3 unique_commit a3 tree -p a2
+on_committer_date "1971-08-16 00:00:14" save_tag b4 unique_commit b4 tree -p b3 -p a3
+on_committer_date "1971-08-16 00:00:15" save_tag a4 unique_commit a4 tree -p a3 -p b4 -p c3
+on_committer_date "1971-08-16 00:00:16" save_tag l3 unique_commit l3 tree -p a4
+on_committer_date "1971-08-16 00:00:17" save_tag l4 unique_commit l4 tree -p l3
+on_committer_date "1971-08-16 00:00:18" save_tag l5 unique_commit l5 tree -p l4
+tag l5 > .git/HEAD
+
+
+# E
+# / \
+# e1 |
+# | |
+# e2 |
+# | |
+# e3 |
+# | |
+# e4 |
+# | |
+# | f1
+# | |
+# | f2
+# | |
+# | f3
+# | |
+# | f4
+# | |
+# e5 |
+# | |
+# e6 |
+# | |
+# e7 |
+# | |
+# e8 |
+# \ /
+# F
+
+
+on_committer_date "1971-08-16 00:00:00" hide_error save_tag F unique_commit F tree
+on_committer_date "1971-08-16 00:00:01" save_tag e8 unique_commit e8 tree -p F
+on_committer_date "1971-08-16 00:00:02" save_tag e7 unique_commit e7 tree -p e8
+on_committer_date "1971-08-16 00:00:03" save_tag e6 unique_commit e6 tree -p e7
+on_committer_date "1971-08-16 00:00:04" save_tag e5 unique_commit e5 tree -p e6
+on_committer_date "1971-08-16 00:00:05" save_tag f4 unique_commit f4 tree -p F
+on_committer_date "1971-08-16 00:00:06" save_tag f3 unique_commit f3 tree -p f4
+on_committer_date "1971-08-16 00:00:07" save_tag f2 unique_commit f2 tree -p f3
+on_committer_date "1971-08-16 00:00:08" save_tag f1 unique_commit f1 tree -p f2
+on_committer_date "1971-08-16 00:00:09" save_tag e4 unique_commit e4 tree -p e5
+on_committer_date "1971-08-16 00:00:10" save_tag e3 unique_commit e3 tree -p e4
+on_committer_date "1971-08-16 00:00:11" save_tag e2 unique_commit e2 tree -p e3
+on_committer_date "1971-08-16 00:00:12" save_tag e1 unique_commit e1 tree -p e2
+on_committer_date "1971-08-16 00:00:13" save_tag E unique_commit E tree -p e1 -p f1
+
+on_committer_date "1971-08-16 00:00:00" hide_error save_tag U unique_commit U tree
+on_committer_date "1971-08-16 00:00:01" save_tag u0 unique_commit u0 tree -p U
+on_committer_date "1971-08-16 00:00:01" save_tag u1 unique_commit u1 tree -p u0
+on_committer_date "1971-08-16 00:00:02" save_tag u2 unique_commit u2 tree -p u0
+on_committer_date "1971-08-16 00:00:03" save_tag u3 unique_commit u3 tree -p u0
+on_committer_date "1971-08-16 00:00:04" save_tag u4 unique_commit u4 tree -p u0
+on_committer_date "1971-08-16 00:00:05" save_tag u5 unique_commit u5 tree -p u0
+on_committer_date "1971-08-16 00:00:06" save_tag V unique_commit V tree -p u1 -p u2 -p u3 -p u4 -p u5
+
+
+#
+# cd to t/trash and use
+#
+# git-rev-list ... 2>&1 | sed "$(cat sed.script)"
+#
+# if you ever want to manually debug the operation of git-rev-list
+#
+echo $sed_script > sed.script
+
+test_sequence()
+{
+ _bisect_option=$1
+
+ test_bisection_diff 0 $_bisect_option l0 ^root
+ test_bisection_diff 0 $_bisect_option l1 ^root
+ test_bisection_diff 0 $_bisect_option l2 ^root
+ test_bisection_diff 0 $_bisect_option a0 ^root
+ test_bisection_diff 0 $_bisect_option a1 ^root
+ test_bisection_diff 0 $_bisect_option a2 ^root
+ test_bisection_diff 0 $_bisect_option a3 ^root
+ test_bisection_diff 0 $_bisect_option b1 ^root
+ test_bisection_diff 0 $_bisect_option b2 ^root
+ test_bisection_diff 0 $_bisect_option b3 ^root
+ test_bisection_diff 0 $_bisect_option c1 ^root
+ test_bisection_diff 0 $_bisect_option c2 ^root
+ test_bisection_diff 0 $_bisect_option c3 ^root
+ test_bisection_diff 0 $_bisect_option E ^F
+ test_bisection_diff 0 $_bisect_option e1 ^F
+ test_bisection_diff 0 $_bisect_option e2 ^F
+ test_bisection_diff 0 $_bisect_option e3 ^F
+ test_bisection_diff 0 $_bisect_option e4 ^F
+ test_bisection_diff 0 $_bisect_option e5 ^F
+ test_bisection_diff 0 $_bisect_option e6 ^F
+ test_bisection_diff 0 $_bisect_option e7 ^F
+ test_bisection_diff 0 $_bisect_option f1 ^F
+ test_bisection_diff 0 $_bisect_option f2 ^F
+ test_bisection_diff 0 $_bisect_option f3 ^F
+ test_bisection_diff 0 $_bisect_option f4 ^F
+ test_bisection_diff 0 $_bisect_option E ^F
+
+ test_bisection_diff 1 $_bisect_option V ^U
+ test_bisection_diff 0 $_bisect_option V ^U ^u1 ^u2 ^u3
+ test_bisection_diff 0 $_bisect_option u1 ^U
+ test_bisection_diff 0 $_bisect_option u2 ^U
+ test_bisection_diff 0 $_bisect_option u3 ^U
+ test_bisection_diff 0 $_bisect_option u4 ^U
+ test_bisection_diff 0 $_bisect_option u5 ^U
+
+#
+# the following illustrate's Linus' binary bug blatt idea.
+#
+# assume the bug is actually at l3, but you don't know that - all you know is that l3 is broken
+# and it wasn't broken before
+#
+# keep bisecting the list, advancing the "bad" head and accumulating "good" heads until
+# the bisection point is the head - this is the bad point.
+#
+
+test_output_expect_success "--bisect l5 ^root" 'git-rev-list $_bisect_option l5 ^root' <<EOF
+c3
+EOF
+
+test_output_expect_success "$_bisect_option l5 ^root ^c3" 'git-rev-list $_bisect_option l5 ^root ^c3' <<EOF
+b4
+EOF
+
+test_output_expect_success "$_bisect_option l5 ^root ^c3 ^b4" 'git-rev-list $_bisect_option l5 ^c3 ^b4' <<EOF
+l3
+EOF
+
+test_output_expect_success "$_bisect_option l3 ^root ^c3 ^b4" 'git-rev-list $_bisect_option l3 ^root ^c3 ^b4' <<EOF
+a4
+EOF
+
+test_output_expect_success "$_bisect_option l5 ^b3 ^a3 ^b4 ^a4" 'git-rev-list $_bisect_option l3 ^b3 ^a3 ^a4' <<EOF
+l3
+EOF
+
+#
+# if l3 is bad, then l4 is bad too - so advance the bad pointer by making b4 the known bad head
+#
+
+test_output_expect_success "$_bisect_option l4 ^a2 ^a3 ^b ^a4" 'git-rev-list $_bisect_option l4 ^a2 ^a3 ^a4' <<EOF
+l3
+EOF
+
+test_output_expect_success "$_bisect_option l3 ^a2 ^a3 ^b ^a4" 'git-rev-list $_bisect_option l3 ^a2 ^a3 ^a4' <<EOF
+l3
+EOF
+
+# found!
+
+#
+# as another example, let's consider a4 to be the bad head, in which case
+#
+
+test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
+c2
+EOF
+
+test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2' <<EOF
+c3
+EOF
+
+test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3' <<EOF
+a4
+EOF
+
+# found!
+
+#
+# or consider c3 to be the bad head
+#
+
+test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
+c2
+EOF
+
+test_output_expect_success "$_bisect_option c3 ^a2 ^a3 ^b4 ^c2" 'git-rev-list $_bisect_option c3 ^a2 ^a3 ^b4 ^c2' <<EOF
+c3
+EOF
+
+# found!
+
+}
+
+test_sequence "--bisect"
+
+#
+#
+test_done
------------
^ permalink raw reply
* [PATCH] This patch introduces a O(n) bisection algorithm to git.
From: Jon Seymour @ 2005-07-01 6:31 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
For the purposes of comparison, this patch:
* enables debugging (-DDEBUG)
* adds a --debug switch to git-rev-list
* adds a --bisect-by-cut switch to git-rev-list
This allows the same git-rev-list binary to be used to compare the existing
O(n^2) behaviour (--bisect) with the O(n) behaviour (--bisect-by-cut).
A measure of complexity of each algorithm can be obtained on stderr,
by using the --debug switch.
My measurements suggest that on a 2000 commit kernel history, this
algorithm is ~ 5 times faster than the O(n^2) algorithm. If this
is true, it should be ~25 times faster on a 10,000 commit kernel history.
This is the difference between a 16 second bisection and a 0.6 second
bisection on that size repository.
The next patch in the series removes all the debug code.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
The Makefile is modified for one patch only to enable experimentation
with this patch. The next patch reverses the Makefile mods.
---
Makefile | 2
rev-list.c | 243 ++++++++++++++++++++++++++++++++++++++++++--
t/t6002-rev-list-bisect.sh | 1
3 files changed, 234 insertions(+), 12 deletions(-)
f26b313fc06d18a0aa44b0d3113805bcde0c0c1f
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -10,7 +10,7 @@
# break unless your underlying filesystem supports those sub-second times
# (my ext3 doesn't).
COPTS=-O2
-CFLAGS=-g $(COPTS) -Wall
+CFLAGS=-DDEBUG -g $(COPTS) -Wall
prefix=$(HOME)
bin=$(prefix)/bin
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -5,10 +5,19 @@
#include "blob.h"
#include "epoch.h"
-#define SEEN (1u << 0)
-#define INTERESTING (1u << 1)
-#define COUNTED (1u << 2)
-#define SHOWN (LAST_EPOCH_FLAG << 2)
+#define ABOVE (1u<<1)
+struct bisect_by_cut_node
+{
+ unsigned int flags;
+ unsigned int count;
+ struct commit_list * children;
+ struct commit_list * visible_parents;
+};
+
+#define SEEN (LAST_EPOCH_FLAG << 1)
+#define INTERESTING (LAST_EPOCH_FLAG << 2)
+#define COUNTED (LAST_EPOCH_FLAG << 3)
+#define SHOWN (LAST_EPOCH_FLAG << 4)
static const char rev_list_usage[] =
"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
@@ -34,6 +43,11 @@ static enum cmit_fmt commit_format = CMI
static int merge_order = 0;
static int show_breaks = 0;
static int stop_traversal = 0;
+static int bisect_by_cut_option = 0;
+#ifdef DEBUG
+static int debug = 0;
+static unsigned int complexity = 0;
+#endif
static void show_commit(struct commit *commit)
{
@@ -90,13 +104,10 @@ static int process_commit(struct commit
if (action == STOP) {
return STOP;
}
-
if (action == CONTINUE) {
return CONTINUE;
}
-
show_commit(commit);
-
return CONTINUE;
}
@@ -264,7 +275,7 @@ static int count_distance(struct commit_
while (p) {
nr += count_distance(p);
p = p->next;
- }
+ }
}
}
return nr;
@@ -272,6 +283,9 @@ static int count_distance(struct commit_
static void clear_distance(struct commit_list *list)
{
+#ifdef DEBUG
+ complexity++;
+#endif
while (list) {
struct commit *commit = list->item;
commit->object.flags &= ~COUNTED;
@@ -403,6 +417,196 @@ static struct commit *get_commit_referen
die("%s is unknown object", name);
}
+static inline struct bisect_by_cut_node * get_bisect_by_cut_node(struct commit * commit)
+{
+ return (struct bisect_by_cut_node *)commit->object.util;
+}
+
+#ifdef DEBUG
+static void print_bisect_by_cut_node(struct commit * commit, const char * prefix)
+{
+ struct bisect_by_cut_node * node = get_bisect_by_cut_node(commit);
+ fprintf(stderr, "%s%s %u %d\n", prefix, sha1_to_hex(commit->object.sha1), node->flags, node->count);
+}
+#endif
+
+/*
+ * Find the best bisection point by cutting a topological order in two then
+ * identifying a set of boundary nodes with a reachability known to be
+ * less than the desired bisection point. The boundary is advanced until all nodes
+ * in the boundary have a reachability greater than or equal to the desired
+ * reachability.
+ *
+ * This algorithm is roughly O(kn) where k is a factor related to the typical
+ * amount of parallel branching within the graph and is not related to n.
+ *
+ * The algorithm borrows the notion of making an arbitrary cut in the graph
+ * from the Kernighan-Lin (1969) graph bisection algorithm but differs in
+ * other respects. In particular, by using the topological order to make the
+ * cut the width of the advancing boundary is reduced to some kind of minimum.
+ * Full graph scans (e.g. calls to count_distance()) are avoided except where
+ * absolutely necessary (i.e. a merge node is encountered).
+ */
+struct commit * bisect_by_cut(struct commit_list * topological_order)
+{
+ unsigned int count=0;
+ unsigned int i;
+ struct commit_list * next;
+ struct commit_list * work = NULL;
+ struct commit * best = topological_order->item;
+ struct bisect_by_cut_node * nodes;
+ struct bisect_by_cut_node * next_node;
+ struct commit_list counter;
+ unsigned int fittest, goal;
+
+ counter.next=NULL;
+ /* count the size of the topological order */
+ next=topological_order;
+ while (next) {
+ count++;
+ next = next->next;
+ }
+ fittest=count;
+ i=(count+1)/2;
+ goal=count/2;
+ /* allocate and initialize the bisect_by_cut_node structure */
+ next_node=nodes=xmalloc(sizeof(*nodes)*count);
+ memset(nodes, 0, sizeof(*nodes)*count);
+ /*
+ * initialize the structures for all nodes of interest
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ next->item->object.util=next_node++;
+ next=next->next;
+ }
+ /*
+ * Mark half the nodes as being above the boundary.
+ * Mark nodes that aren't in the topological order as uninteresting.
+ * Initialize lists of visible children and parents.
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ struct commit * next_item = next->item;
+ struct commit_list * parents;
+
+ if (i > 0) {
+ next_node->flags |= ABOVE;
+ i--;
+ }
+ parents=next_item->parents;
+ while (parents) {
+ struct commit * parent = parents->item;
+ struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parent);
+
+ if (pn) {
+ commit_list_insert(next_item, &pn->children);
+ commit_list_insert(parent, &next_node->visible_parents);
+ } else
+ parent->object.flags |= UNINTERESTING;
+ parent->object.flags &= ~COUNTED;
+ parents=parents->next;
+ }
+ next=next->next;
+ next_node++;
+ }
+ /*
+ * Initialize the work queue with commits that are on the boundary
+ * and with < the desired reachability.
+ *
+ * We know these commits have less than the desired
+ * reachability because by the definition of the topological order
+ * nodes can only reach nodes to the right of them in the topological
+ * order and by construction, there there are no more than
+ * (count-1)/2 nodes to the right of each node in the boundary.
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ struct commit_list * parents;
+
+ parents=next_node->visible_parents;
+ while (parents) {
+ struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parents->item);
+
+ if ((next_node->flags & ABOVE)
+ && !(pn->flags & ABOVE)
+ && (pn->count == 0)) {
+ counter.item=parents->item;
+ pn->count = count_distance(&counter);
+ clear_distance(topological_order);
+ commit_list_insert(parents->item, &work);
+ }
+ parents=parents->next;
+ }
+ next=next->next;
+ next_node++;
+ }
+ /*
+ * Process the work queue until done.
+ */
+ while (work) {
+ struct commit * work_item = pop_commit(&work);
+ struct bisect_by_cut_node * wn = get_bisect_by_cut_node(work_item);
+ struct commit_list * children = wn->children;
+ unsigned int goal_test = wn->count;
+ unsigned int fitness = (goal_test>goal)?(goal_test-goal):(goal-goal_test);
+
+ if (fitness < fittest) {
+ best = work_item;
+ fittest = fitness;
+ }
+#ifdef DEBUG
+ if (debug) {
+ print_bisect_by_cut_node(work_item, "work ");
+ }
+#endif
+ if (goal_test < goal) {
+ while (children) {
+ struct bisect_by_cut_node * cn
+ = get_bisect_by_cut_node(children->item);
+ if (cn->flags & ABOVE) {
+ /* move the boundary up */
+ cn->flags &= ~ABOVE;
+ if (cn->visible_parents && !cn->visible_parents->next)
+ /*
+ * If the child only has one visible parent
+ * the goal_test increases by one
+ */
+ cn->count = wn->count+1;
+ else {
+ /*
+ * Otherwise, we need to count it explicitly.
+ */
+ counter.item=children->item;
+ cn->count = count_distance(&counter);
+ clear_distance(topological_order);
+ }
+ commit_list_insert(children->item, &work);
+ }
+ children=children->next;
+ }
+ } else if (goal_test > goal)
+ continue;
+ else
+ break; /* can't do better than this */
+ }
+ if (work)
+ free_commit_list(work);
+ /*
+ * reset the util pointers.
+ */
+ next=topological_order;
+ while (next) {
+ next->item->object.util=NULL;
+ next = next->next;
+ }
+ free(nodes);
+ return best;
+}
+
int main(int argc, char **argv)
{
struct commit_list *list = NULL;
@@ -440,6 +644,10 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
+ if (!strcmp(arg, "--bisect-by-cut")) {
+ bisect_by_cut_option = 1;
+ continue;
+ }
if (!strcmp(arg, "--bisect")) {
bisect_list = 1;
continue;
@@ -458,7 +666,12 @@ int main(int argc, char **argv)
show_breaks = 1;
continue;
}
-
+#ifdef DEBUG
+ if (!strcmp(arg, "--debug")) {
+ debug = 1;
+ continue;
+ }
+#endif
flags = 0;
if (*arg == '^') {
flags = UNINTERESTING;
@@ -476,12 +689,20 @@ int main(int argc, char **argv)
if (!merge_order) {
if (limited)
list = limit_list(list);
- show_commit_list(list);
+ if (!bisect_by_cut_option)
+ show_commit_list(list);
+ else {
+ sort_in_topological_order(&list);
+ show_commit(bisect_by_cut(list));
+ }
} else {
if (sort_list_in_merge_order(list, &process_commit)) {
die("merge order sort failed\n");
}
}
-
+#ifdef DEBUG
+ if (debug)
+ fprintf(stderr, "complexity=%d\n", complexity);
+#endif
return 0;
}
diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
--- a/t/t6002-rev-list-bisect.sh
+++ b/t/t6002-rev-list-bisect.sh
@@ -241,6 +241,7 @@ EOF
}
test_sequence "--bisect"
+test_sequence "--bisect-by-cut"
#
#
------------
^ permalink raw reply
* [PATCH] Move bisection algorithms into commit.c
From: Jon Seymour @ 2005-07-01 6:31 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch moves the bisection algorithms into commit.c.
The bisection algorithms are more lib'ish than tool'ish, so they
have been moved into commit.c.
This has required the definition of the UNINTERESTING and COUNTED
flags to be moved into commit.h and the introduction of the
the LAST_COMMIT_FLAG into commit.h.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
commit.c | 258 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
commit.h | 17 ++++
epoch.h | 12 +--
rev-list.c | 261 ------------------------------------------------------------
4 files changed, 281 insertions(+), 267 deletions(-)
751d906f842fabd42d191fe7df7ab61d44765de7
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -3,6 +3,15 @@
#include "commit.h"
#include "cache.h"
+#define ABOVE (1u<<1)
+struct bisect_by_cut_node
+{
+ unsigned int flags;
+ unsigned int count;
+ struct commit_list * children;
+ struct commit_list * visible_parents;
+};
+
struct sort_node
{
/*
@@ -453,3 +462,252 @@ void sort_in_topological_order(struct co
}
free(nodes);
}
+
+/*
+ * This is a truly stupid algorithm, but it's only
+ * used for bisection, and we just don't care enough.
+ *
+ * We care just barely enough to avoid recursing for
+ * non-merge entries.
+ */
+static int count_distance(struct commit_list *entry)
+{
+ int nr = 0;
+
+ while (entry) {
+ struct commit *commit = entry->item;
+ struct commit_list *p;
+
+ if (commit->object.flags & (UNINTERESTING | COUNTED))
+ break;
+ nr++;
+ commit->object.flags |= COUNTED;
+ p = commit->parents;
+ entry = p;
+ if (p) {
+ p = p->next;
+ while (p) {
+ nr += count_distance(p);
+ p = p->next;
+ }
+ }
+ }
+ return nr;
+}
+
+static void clear_distance(struct commit_list *list)
+{
+ while (list) {
+ struct commit *commit = list->item;
+ commit->object.flags &= ~COUNTED;
+ list = list->next;
+ }
+}
+
+struct commit_list *find_bisection(struct commit_list *list)
+{
+ int nr, closest;
+ struct commit_list *p, *best;
+
+ nr = 0;
+ p = list;
+ while (p) {
+ nr++;
+ p = p->next;
+ }
+ closest = 0;
+ best = list;
+
+ p = list;
+ while (p) {
+ int distance = count_distance(p);
+ clear_distance(list);
+ if (nr - distance < distance)
+ distance = nr - distance;
+ if (distance > closest) {
+ best = p;
+ closest = distance;
+ }
+ p = p->next;
+ }
+ if (best)
+ best->next = NULL;
+ return best;
+}
+
+static inline struct bisect_by_cut_node * get_bisect_by_cut_node(struct commit * commit)
+{
+ return (struct bisect_by_cut_node *)commit->object.util;
+}
+
+/*
+ * Find the best bisection point by cutting a topological order in two then
+ * identifying a set of boundary nodes with a reachability known to be
+ * less than the desired bisection point. The boundary is advanced until all nodes
+ * in the boundary have a reachability greater than or equal to the desired
+ * reachability.
+ *
+ * This algorithm is roughly O(kn) where k is a factor related to the typical
+ * amount of parallel branching within the graph and is not related to n.
+ *
+ * The algorithm borrows the notion of making an arbitrary cut in the graph
+ * from the Kernighan-Lin (1969) graph bisection algorithm but differs in
+ * other respects. In particular, by using the topological order to make the
+ * cut the width of the advancing boundary is reduced to some kind of minimum.
+ * Full graph scans (e.g. calls to count_distance()) are avoided except where
+ * absolutely necessary (i.e. a merge node is encountered).
+ */
+struct commit * bisect_by_cut(struct commit_list * topological_order)
+{
+ unsigned int count=0;
+ unsigned int i;
+ struct commit_list * next;
+ struct commit_list * work = NULL;
+ struct commit * best = topological_order->item;
+ struct bisect_by_cut_node * nodes;
+ struct bisect_by_cut_node * next_node;
+ struct commit_list counter;
+ unsigned int fittest, goal;
+
+ counter.next=NULL;
+ /* count the size of the topological order */
+ next=topological_order;
+ while (next) {
+ count++;
+ next = next->next;
+ }
+ fittest=count;
+ i=(count+1)/2;
+ goal=count/2;
+ /* allocate and initialize the bisect_by_cut_node structure */
+ next_node=nodes=xmalloc(sizeof(*nodes)*count);
+ memset(nodes, 0, sizeof(*nodes)*count);
+ /*
+ * initialize the structures for all nodes of interest
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ next->item->object.util=next_node++;
+ next=next->next;
+ }
+ /*
+ * Mark half the nodes as being above the boundary.
+ * Mark nodes that aren't in the topological order as uninteresting.
+ * Initialize lists of visible children and parents.
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ struct commit * next_item = next->item;
+ struct commit_list * parents;
+
+ if (i > 0) {
+ next_node->flags |= ABOVE;
+ i--;
+ }
+ parents=next_item->parents;
+ while (parents) {
+ struct commit * parent = parents->item;
+ struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parent);
+
+ if (pn) {
+ commit_list_insert(next_item, &pn->children);
+ commit_list_insert(parent, &next_node->visible_parents);
+ } else
+ parent->object.flags |= UNINTERESTING;
+ parent->object.flags &= ~COUNTED;
+ parents=parents->next;
+ }
+ next=next->next;
+ next_node++;
+ }
+ /*
+ * Initialize the work queue with commits that are on the boundary
+ * and with < the desired reachability.
+ *
+ * We know these commits have less than the desired
+ * reachability because by the definition of the topological order
+ * nodes can only reach nodes to the right of them in the topological
+ * order and by construction, there there are no more than
+ * (count-1)/2 nodes to the right of each node in the boundary.
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ struct commit_list * parents;
+
+ parents=next_node->visible_parents;
+ while (parents) {
+ struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parents->item);
+
+ if ((next_node->flags & ABOVE)
+ && !(pn->flags & ABOVE)
+ && (pn->count == 0)) {
+ counter.item=parents->item;
+ pn->count = count_distance(&counter);
+ clear_distance(topological_order);
+ commit_list_insert(parents->item, &work);
+ }
+ parents=parents->next;
+ }
+ next=next->next;
+ next_node++;
+ }
+ /*
+ * Process the work queue until done.
+ */
+ while (work) {
+ struct commit * work_item = pop_commit(&work);
+ struct bisect_by_cut_node * wn = get_bisect_by_cut_node(work_item);
+ struct commit_list * children = wn->children;
+ unsigned int goal_test = wn->count;
+ unsigned int fitness = (goal_test>goal)?(goal_test-goal):(goal-goal_test);
+
+ if (fitness < fittest) {
+ best = work_item;
+ fittest = fitness;
+ }
+ if (goal_test < goal) {
+ while (children) {
+ struct bisect_by_cut_node * cn
+ = get_bisect_by_cut_node(children->item);
+ if (cn->flags & ABOVE) {
+ /* move the boundary up */
+ cn->flags &= ~ABOVE;
+ if (cn->visible_parents && !cn->visible_parents->next)
+ /*
+ * If the child only has one visible parent
+ * the goal_test increases by one
+ */
+ cn->count = wn->count+1;
+ else {
+ /*
+ * Otherwise, we need to count it explicitly.
+ */
+ counter.item=children->item;
+ cn->count = count_distance(&counter);
+ clear_distance(topological_order);
+ }
+ commit_list_insert(children->item, &work);
+ }
+ children=children->next;
+ }
+ } else if (goal_test > goal)
+ continue;
+ else
+ break; /* can't do better than this */
+ }
+ if (work)
+ free_commit_list(work);
+ /*
+ * reset the util pointers.
+ */
+ next=topological_order;
+ while (next) {
+ next->item->object.util=NULL;
+ next = next->next;
+ }
+ free(nodes);
+ return best;
+}
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -4,6 +4,10 @@
#include "object.h"
#include "tree.h"
+#define UNINTERESTING (1u<<0)
+#define COUNTED (1u<<1)
+#define LAST_COMMIT_FLAG (COUNTED)
+
struct commit_list {
struct commit *item;
struct commit_list *next;
@@ -68,4 +72,17 @@ int count_parents(struct commit * commit
* a reachable from b => ord(b) < ord(a)
*/
void sort_in_topological_order(struct commit_list ** list);
+
+/*
+ * Uses an O(n^2) algorithm to find the commit that bisects
+ * the subgraph represented by the list of commits. The boundaries
+ * of the subgraph are delimited by adjacent nodes that have
+ */
+struct commit_list *find_bisection(struct commit_list *list);
+
+/*
+ * Uses O(n) to find the bisection of a list of commits
+ * which is already sorted in topological order.
+ */
+struct commit * bisect_by_cut(struct commit_list * topological_order);
#endif /* COMMIT_H */
diff --git a/epoch.h b/epoch.h
--- a/epoch.h
+++ b/epoch.h
@@ -10,12 +10,10 @@ typedef int (*emitter_func) (struct comm
int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter);
-#define UNINTERESTING (1u<<2)
-#define BOUNDARY (1u<<3)
-#define VISITED (1u<<4)
-#define DISCONTINUITY (1u<<5)
-#define DUPCHECK (1u<<6)
-#define LAST_EPOCH_FLAG (1u<<6)
-
+#define BOUNDARY (LAST_COMMIT_FLAG<<1)
+#define VISITED (LAST_COMMIT_FLAG<<2)
+#define DISCONTINUITY (LAST_COMMIT_FLAG<<3)
+#define DUPCHECK (LAST_COMMIT_FLAG<<4)
+#define LAST_EPOCH_FLAG (DUPCHECK)
#endif /* EPOCH_H */
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -5,19 +5,9 @@
#include "blob.h"
#include "epoch.h"
-#define ABOVE (1u<<1)
-struct bisect_by_cut_node
-{
- unsigned int flags;
- unsigned int count;
- struct commit_list * children;
- struct commit_list * visible_parents;
-};
-
#define SEEN (LAST_EPOCH_FLAG << 1)
#define INTERESTING (LAST_EPOCH_FLAG << 2)
-#define COUNTED (LAST_EPOCH_FLAG << 3)
-#define SHOWN (LAST_EPOCH_FLAG << 4)
+#define SHOWN (LAST_EPOCH_FLAG << 3)
static const char rev_list_usage[] =
"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
@@ -245,78 +235,6 @@ static int everybody_uninteresting(struc
return 1;
}
-/*
- * This is a truly stupid algorithm, but it's only
- * used for bisection, and we just don't care enough.
- *
- * We care just barely enough to avoid recursing for
- * non-merge entries.
- */
-static int count_distance(struct commit_list *entry)
-{
- int nr = 0;
-
- while (entry) {
- struct commit *commit = entry->item;
- struct commit_list *p;
-
- if (commit->object.flags & (UNINTERESTING | COUNTED))
- break;
- nr++;
- commit->object.flags |= COUNTED;
- p = commit->parents;
- entry = p;
- if (p) {
- p = p->next;
- while (p) {
- nr += count_distance(p);
- p = p->next;
- }
- }
- }
- return nr;
-}
-
-static void clear_distance(struct commit_list *list)
-{
- while (list) {
- struct commit *commit = list->item;
- commit->object.flags &= ~COUNTED;
- list = list->next;
- }
-}
-
-static struct commit_list *find_bisection(struct commit_list *list)
-{
- int nr, closest;
- struct commit_list *p, *best;
-
- nr = 0;
- p = list;
- while (p) {
- nr++;
- p = p->next;
- }
- closest = 0;
- best = list;
-
- p = list;
- while (p) {
- int distance = count_distance(p);
- clear_distance(list);
- if (nr - distance < distance)
- distance = nr - distance;
- if (distance > closest) {
- best = p;
- closest = distance;
- }
- p = p->next;
- }
- if (best)
- best->next = NULL;
- return best;
-}
-
struct commit_list *limit_list(struct commit_list *list)
{
struct commit_list *newlist = NULL;
@@ -410,183 +328,6 @@ static struct commit *get_commit_referen
die("%s is unknown object", name);
}
-static inline struct bisect_by_cut_node * get_bisect_by_cut_node(struct commit * commit)
-{
- return (struct bisect_by_cut_node *)commit->object.util;
-}
-
-/*
- * Find the best bisection point by cutting a topological order in two then
- * identifying a set of boundary nodes with a reachability known to be
- * less than the desired bisection point. The boundary is advanced until all nodes
- * in the boundary have a reachability greater than or equal to the desired
- * reachability.
- *
- * This algorithm is roughly O(kn) where k is a factor related to the typical
- * amount of parallel branching within the graph and is not related to n.
- *
- * The algorithm borrows the notion of making an arbitrary cut in the graph
- * from the Kernighan-Lin (1969) graph bisection algorithm but differs in
- * other respects. In particular, by using the topological order to make the
- * cut the width of the advancing boundary is reduced to some kind of minimum.
- * Full graph scans (e.g. calls to count_distance()) are avoided except where
- * absolutely necessary (i.e. a merge node is encountered).
- */
-struct commit * bisect_by_cut(struct commit_list * topological_order)
-{
- unsigned int count=0;
- unsigned int i;
- struct commit_list * next;
- struct commit_list * work = NULL;
- struct commit * best = topological_order->item;
- struct bisect_by_cut_node * nodes;
- struct bisect_by_cut_node * next_node;
- struct commit_list counter;
- unsigned int fittest, goal;
-
- counter.next=NULL;
- /* count the size of the topological order */
- next=topological_order;
- while (next) {
- count++;
- next = next->next;
- }
- fittest=count;
- i=(count+1)/2;
- goal=count/2;
- /* allocate and initialize the bisect_by_cut_node structure */
- next_node=nodes=xmalloc(sizeof(*nodes)*count);
- memset(nodes, 0, sizeof(*nodes)*count);
- /*
- * initialize the structures for all nodes of interest
- */
- next=topological_order;
- next_node=nodes;
- while (next) {
- next->item->object.util=next_node++;
- next=next->next;
- }
- /*
- * Mark half the nodes as being above the boundary.
- * Mark nodes that aren't in the topological order as uninteresting.
- * Initialize lists of visible children and parents.
- */
- next=topological_order;
- next_node=nodes;
- while (next) {
- struct commit * next_item = next->item;
- struct commit_list * parents;
-
- if (i > 0) {
- next_node->flags |= ABOVE;
- i--;
- }
- parents=next_item->parents;
- while (parents) {
- struct commit * parent = parents->item;
- struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parent);
-
- if (pn) {
- commit_list_insert(next_item, &pn->children);
- commit_list_insert(parent, &next_node->visible_parents);
- } else
- parent->object.flags |= UNINTERESTING;
- parent->object.flags &= ~COUNTED;
- parents=parents->next;
- }
- next=next->next;
- next_node++;
- }
- /*
- * Initialize the work queue with commits that are on the boundary
- * and with < the desired reachability.
- *
- * We know these commits have less than the desired
- * reachability because by the definition of the topological order
- * nodes can only reach nodes to the right of them in the topological
- * order and by construction, there there are no more than
- * (count-1)/2 nodes to the right of each node in the boundary.
- */
- next=topological_order;
- next_node=nodes;
- while (next) {
- struct commit_list * parents;
-
- parents=next_node->visible_parents;
- while (parents) {
- struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parents->item);
-
- if ((next_node->flags & ABOVE)
- && !(pn->flags & ABOVE)
- && (pn->count == 0)) {
- counter.item=parents->item;
- pn->count = count_distance(&counter);
- clear_distance(topological_order);
- commit_list_insert(parents->item, &work);
- }
- parents=parents->next;
- }
- next=next->next;
- next_node++;
- }
- /*
- * Process the work queue until done.
- */
- while (work) {
- struct commit * work_item = pop_commit(&work);
- struct bisect_by_cut_node * wn = get_bisect_by_cut_node(work_item);
- struct commit_list * children = wn->children;
- unsigned int goal_test = wn->count;
- unsigned int fitness = (goal_test>goal)?(goal_test-goal):(goal-goal_test);
-
- if (fitness < fittest) {
- best = work_item;
- fittest = fitness;
- }
- if (goal_test < goal) {
- while (children) {
- struct bisect_by_cut_node * cn
- = get_bisect_by_cut_node(children->item);
- if (cn->flags & ABOVE) {
- /* move the boundary up */
- cn->flags &= ~ABOVE;
- if (cn->visible_parents && !cn->visible_parents->next)
- /*
- * If the child only has one visible parent
- * the goal_test increases by one
- */
- cn->count = wn->count+1;
- else {
- /*
- * Otherwise, we need to count it explicitly.
- */
- counter.item=children->item;
- cn->count = count_distance(&counter);
- clear_distance(topological_order);
- }
- commit_list_insert(children->item, &work);
- }
- children=children->next;
- }
- } else if (goal_test > goal)
- continue;
- else
- break; /* can't do better than this */
- }
- if (work)
- free_commit_list(work);
- /*
- * reset the util pointers.
- */
- next=topological_order;
- while (next) {
- next->item->object.util=NULL;
- next = next->next;
- }
- free(nodes);
- return best;
-}
-
int main(int argc, char **argv)
{
struct commit_list *list = NULL;
------------
^ permalink raw reply
* [PATCH] Removes support for O(n^2) algorithm from git-rev-list completely
From: Jon Seymour @ 2005-07-01 6:31 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch completely removes support for the O(n^2) bisection
algorithm from commit.c, commit.h and rev-list.c
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Linus: I have included this patch to allow you to easily remove the O(n^2)
algorithm if that is your choice. I am not expecting you to do so.
---
commit.c | 31 -------------------------------
commit.h | 7 -------
rev-list.c | 7 -------
t/t6002-rev-list-bisect.sh | 1 -
4 files changed, 0 insertions(+), 46 deletions(-)
fa36c577acce519d1ef17bd807ab1486e1aa365a
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -504,37 +504,6 @@ static void clear_distance(struct commit
}
}
-struct commit_list *find_bisection(struct commit_list *list)
-{
- int nr, closest;
- struct commit_list *p, *best;
-
- nr = 0;
- p = list;
- while (p) {
- nr++;
- p = p->next;
- }
- closest = 0;
- best = list;
-
- p = list;
- while (p) {
- int distance = count_distance(p);
- clear_distance(list);
- if (nr - distance < distance)
- distance = nr - distance;
- if (distance > closest) {
- best = p;
- closest = distance;
- }
- p = p->next;
- }
- if (best)
- best->next = NULL;
- return best;
-}
-
static inline struct bisect_by_cut_node * get_bisect_by_cut_node(struct commit * commit)
{
return (struct bisect_by_cut_node *)commit->object.util;
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -74,13 +74,6 @@ int count_parents(struct commit * commit
void sort_in_topological_order(struct commit_list ** list);
/*
- * Uses an O(n^2) algorithm to find the commit that bisects
- * the subgraph represented by the list of commits. The boundaries
- * of the subgraph are delimited by adjacent nodes that have
- */
-struct commit_list *find_bisection(struct commit_list *list);
-
-/*
* Uses O(n) to find the bisection of a list of commits
* which is already sorted in topological order.
*/
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -19,7 +19,6 @@ static const char rev_list_usage[] =
" --bisect\n"
" --merge-order [ --show-breaks ]";
-static int bisect_list = 0;
static int tag_objects = 0;
static int tree_objects = 0;
static int blob_objects = 0;
@@ -252,8 +251,6 @@ struct commit_list *limit_list(struct co
}
p = &commit_list_insert(commit, p)->next;
}
- if (bisect_list)
- newlist = find_bisection(newlist);
return newlist;
}
@@ -370,10 +367,6 @@ int main(int argc, char **argv)
bisect_by_cut_option = 1;
continue;
}
- if (!strcmp(arg, "--bisect-orig")) {
- bisect_list = 1;
- continue;
- }
if (!strcmp(arg, "--objects")) {
tag_objects = 1;
tree_objects = 1;
diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
--- a/t/t6002-rev-list-bisect.sh
+++ b/t/t6002-rev-list-bisect.sh
@@ -241,7 +241,6 @@ EOF
}
test_sequence "--bisect"
-test_sequence "--bisect-by-cut"
#
#
------------
^ permalink raw reply
* OOPS: unnumbered patch series
From: Jon Seymour @ 2005-07-01 6:34 UTC (permalink / raw)
To: Git Mailing List; +Cc: Linus Torvalds, Junio C Hamano
Sorry about that. I'll resend with each patch numbered in sequence.
I forgot that git-format-patch-script no longer numbers things by default.
Junio: this is an example where the special case would be good. As it
stands, I now have to add a special case to my wrapper around your
scripts to use the -n switch if and only if I have more than 1 patch
to send.
jon.
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/
^ permalink raw reply
* [PATCH 3/8] Add a topological sort procedure to commit.c [rev 3]
From: Jon Seymour @ 2005-07-01 6:46 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch introduces an in-place topological sort procedure to commit.c.
Given a list of commits, sort_in_topological_order() will perform an in-place
topological sort of that list.
The invariant that applies to the resulting list is:
a reachable from b => ord(b) < ord(a)
This invariant is weaker than the --merge-order invariant, but is cheaper
to calculate (assuming the list has been identified) and will serve any
purpose where only a minimal topological order guarantee is required.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Note: this patch currently has no observable consequences since nothing
in this patch calls it. A future patch will use this algorithm to provide
an O(n) bisection algorithm as a suggested replacement for the
existing O(n^2) bisection algorithm.
This patch is a complete replacement for earlier revisions of this patch.
[rev 2]
* incorporates Junio's questions/comments as commentary,
* adds object.util save/restore functionality so that no
assumption is made about the pre-existing state of object.util
upon entry to the procedure.
[rev 3]
* removed object.util save/restore
* added more documentation to header about pre-conditions
---
commit.c | 107 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
commit.h | 13 ++++++++
2 files changed, 120 insertions(+), 0 deletions(-)
5213443ab584624c3ebcec9a6d2624615c934e5b
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -3,6 +3,22 @@
#include "commit.h"
#include "cache.h"
+struct sort_node
+{
+ /*
+ * the number of children of the associated commit
+ * that also occur in the list being sorted.
+ */
+ unsigned int indegree;
+
+ /*
+ * reference to original list item that we will re-use
+ * on output.
+ */
+ struct commit_list * list_item;
+
+};
+
const char *commit_type = "commit";
enum cmit_fmt get_commit_format(const char *arg)
@@ -346,3 +362,94 @@ int count_parents(struct commit * commit
return count;
}
+/*
+ * Performs an in-place topological sort on the list supplied.
+ */
+void sort_in_topological_order(struct commit_list ** list)
+{
+ struct commit_list * next = *list;
+ struct commit_list * work = NULL;
+ struct commit_list ** pptr = list;
+ struct sort_node * nodes;
+ struct sort_node * next_nodes;
+ int count = 0;
+
+ /* determine the size of the list */
+ while (next) {
+ next = next->next;
+ count++;
+ }
+ /* allocate an array to help sort the list */
+ nodes = xcalloc(count, sizeof(*nodes));
+ /* link the list to the array */
+ next_nodes = nodes;
+ next=*list;
+ while (next) {
+ next_nodes->list_item = next;
+ next->item->object.util = next_nodes;
+ next_nodes++;
+ next = next->next;
+ }
+ /* update the indegree */
+ next=*list;
+ while (next) {
+ struct commit_list * parents = next->item->parents;
+ while (parents) {
+ struct commit * parent=parents->item;
+ struct sort_node * pn = (struct sort_node *)parent->object.util;
+
+ if (pn)
+ pn->indegree++;
+ parents=parents->next;
+ }
+ next=next->next;
+ }
+ /*
+ * find the tips
+ *
+ * tips are nodes not reachable from any other node in the list
+ *
+ * the tips serve as a starting set for the work queue.
+ */
+ next=*list;
+ while (next) {
+ struct sort_node * node = (struct sort_node *)next->item->object.util;
+
+ if (node->indegree == 0) {
+ commit_list_insert(next->item, &work);
+ }
+ next=next->next;
+ }
+ /* process the list in topological order */
+ while (work) {
+ struct commit * work_item = pop_commit(&work);
+ struct sort_node * work_node = (struct sort_node *)work_item->object.util;
+ struct commit_list * parents = work_item->parents;
+
+ while (parents) {
+ struct commit * parent=parents->item;
+ struct sort_node * pn = (struct sort_node *)parent->object.util;
+
+ if (pn) {
+ /*
+ * parents are only enqueued for emission
+ * when all their children have been emitted thereby
+ * guaranteeing topological order.
+ */
+ pn->indegree--;
+ if (!pn->indegree)
+ commit_list_insert(parent, &work);
+ }
+ parents=parents->next;
+ }
+ /*
+ * work_item is a commit all of whose children
+ * have already been emitted. we can emit it now.
+ */
+ *pptr = work_node->list_item;
+ pptr = &(*pptr)->next;
+ *pptr = NULL;
+ work_item->object.util = NULL;
+ }
+ free(nodes);
+}
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -55,4 +55,17 @@ struct commit *pop_most_recent_commit(st
struct commit *pop_commit(struct commit_list **stack);
int count_parents(struct commit * commit);
+
+/*
+ * Performs an in-place topological sort of list supplied.
+ *
+ * Pre-conditions:
+ * all commits in input list and all parents of those
+ * commits must have object.util == NULL
+ *
+ * Post-conditions:
+ * invariant of resulting list is:
+ * a reachable from b => ord(b) < ord(a)
+ */
+void sort_in_topological_order(struct commit_list ** list);
#endif /* COMMIT_H */
------------
^ permalink raw reply
* [PATCH 5/8] Removes DEBUG code from rev-list.c and -DDEBUG from Makefile
From: Jon Seymour @ 2005-07-01 6:46 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch removes DEBUG code and -DDEBUG flag from Makefile.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Makefile | 2 +-
rev-list.c | 30 ------------------------------
2 files changed, 1 insertions(+), 31 deletions(-)
be52c026e003b9774acc3d0f53ae5ed67d878b03
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -10,7 +10,7 @@
# break unless your underlying filesystem supports those sub-second times
# (my ext3 doesn't).
COPTS=-O2
-CFLAGS=-DDEBUG -g $(COPTS) -Wall
+CFLAGS=-g $(COPTS) -Wall
prefix=$(HOME)
bin=$(prefix)/bin
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -44,10 +44,6 @@ static int merge_order = 0;
static int show_breaks = 0;
static int stop_traversal = 0;
static int bisect_by_cut_option = 0;
-#ifdef DEBUG
-static int debug = 0;
-static unsigned int complexity = 0;
-#endif
static void show_commit(struct commit *commit)
{
@@ -283,9 +279,6 @@ static int count_distance(struct commit_
static void clear_distance(struct commit_list *list)
{
-#ifdef DEBUG
- complexity++;
-#endif
while (list) {
struct commit *commit = list->item;
commit->object.flags &= ~COUNTED;
@@ -422,14 +415,6 @@ static inline struct bisect_by_cut_node
return (struct bisect_by_cut_node *)commit->object.util;
}
-#ifdef DEBUG
-static void print_bisect_by_cut_node(struct commit * commit, const char * prefix)
-{
- struct bisect_by_cut_node * node = get_bisect_by_cut_node(commit);
- fprintf(stderr, "%s%s %u %d\n", prefix, sha1_to_hex(commit->object.sha1), node->flags, node->count);
-}
-#endif
-
/*
* Find the best bisection point by cutting a topological order in two then
* identifying a set of boundary nodes with a reachability known to be
@@ -558,11 +543,6 @@ struct commit * bisect_by_cut(struct com
best = work_item;
fittest = fitness;
}
-#ifdef DEBUG
- if (debug) {
- print_bisect_by_cut_node(work_item, "work ");
- }
-#endif
if (goal_test < goal) {
while (children) {
struct bisect_by_cut_node * cn
@@ -666,12 +646,6 @@ int main(int argc, char **argv)
show_breaks = 1;
continue;
}
-#ifdef DEBUG
- if (!strcmp(arg, "--debug")) {
- debug = 1;
- continue;
- }
-#endif
flags = 0;
if (*arg == '^') {
flags = UNINTERESTING;
@@ -700,9 +674,5 @@ int main(int argc, char **argv)
die("merge order sort failed\n");
}
}
-#ifdef DEBUG
- if (debug)
- fprintf(stderr, "complexity=%d\n", complexity);
-#endif
return 0;
}
------------
^ permalink raw reply
* [PATCH 1/8] Factor out useful test case infrastructure from t/t6001... into t/t6000-lib.sh
From: Jon Seymour @ 2005-07-01 6:46 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
Functions that are useful to other t6xxx testcases are moved into t6000-lib.sh
To use these functions in a test case, use a test-case pre-amble like:
. ./test-lib.sh
. ../t6000-lib.sh # t6xxx specific functions
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
t/t6000-lib.sh | 105 +++++++++++++++++++++++++++++++++++++
t/t6001-rev-list-merge-order.sh | 112 ---------------------------------------
2 files changed, 106 insertions(+), 111 deletions(-)
create mode 100644 t/t6000-lib.sh
127ff5409fda605196f4a237b1c075f3b5b2a0b6
diff --git a/t/t6000-lib.sh b/t/t6000-lib.sh
new file mode 100644
--- /dev/null
+++ b/t/t6000-lib.sh
@@ -0,0 +1,105 @@
+[ -d .git/refs/tags ] || mkdir -p .git/refs/tags
+
+sed_script="";
+
+# Answer the sha1 has associated with the tag. The tag must exist in .git or .git/refs/tags
+tag()
+{
+ _tag=$1
+ [ -f .git/refs/tags/$_tag ] || error "tag: \"$_tag\" does not exist"
+ cat .git/refs/tags/$_tag
+}
+
+# Generate a commit using the text specified to make it unique and the tree
+# named by the tag specified.
+unique_commit()
+{
+ _text=$1
+ _tree=$2
+ shift 2
+ echo $_text | git-commit-tree $(tag $_tree) "$@"
+}
+
+# Save the output of a command into the tag specified. Prepend
+# a substitution script for the tag onto the front of $sed_script
+save_tag()
+{
+ _tag=$1
+ [ -n "$_tag" ] || error "usage: save_tag tag commit-args ..."
+ shift 1
+ "$@" >.git/refs/tags/$_tag
+ sed_script="s/$(tag $_tag)/$_tag/g${sed_script+;}$sed_script"
+}
+
+# Replace unhelpful sha1 hashses with their symbolic equivalents
+entag()
+{
+ sed "$sed_script"
+}
+
+# Execute a command after first saving, then setting the GIT_AUTHOR_EMAIL
+# tag to a specified value. Restore the original value on return.
+as_author()
+{
+ _author=$1
+ shift 1
+ _save=$GIT_AUTHOR_EMAIL
+
+ export GIT_AUTHOR_EMAIL="$_author"
+ "$@"
+ export GIT_AUTHOR_EMAIL="$_save"
+}
+
+commit_date()
+{
+ _commit=$1
+ git-cat-file commit $_commit | sed -n "s/^committer .*> \([0-9]*\) .*/\1/p"
+}
+
+on_committer_date()
+{
+ _date=$1
+ shift 1
+ GIT_COMMITTER_DATE=$_date "$@"
+}
+
+# Execute a command and suppress any error output.
+hide_error()
+{
+ "$@" 2>/dev/null
+}
+
+check_output()
+{
+ _name=$1
+ shift 1
+ if eval "$*" | entag > $_name.actual
+ then
+ diff $_name.expected $_name.actual
+ else
+ return 1;
+ fi
+}
+
+# Turn a reasonable test description into a reasonable test name.
+# All alphanums translated into -'s which are then compressed and stripped
+# from front and back.
+name_from_description()
+{
+ tr "'" '-' | tr '~`!@#$%^&*()_+={}[]|\;:"<>,/? ' '-' | tr -s '-' | tr '[A-Z]' '[a-z]' | sed "s/^-*//;s/-*\$//"
+}
+
+
+# Execute the test described by the first argument, by eval'ing
+# command line specified in the 2nd argument. Check the status code
+# is zero and that the output matches the stream read from
+# stdin.
+test_output_expect_success()
+{
+ _description=$1
+ _test=$2
+ [ $# -eq 2 ] || error "usage: test_output_expect_success description test <<EOF ... EOF"
+ _name=$(echo $_description | name_from_description)
+ cat > $_name.expected
+ test_expect_success "$_description" "check_output $_name \"$_test\""
+}
diff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh
--- a/t/t6001-rev-list-merge-order.sh
+++ b/t/t6001-rev-list-merge-order.sh
@@ -6,117 +6,7 @@
test_description='Tests git-rev-list --merge-order functionality'
. ./test-lib.sh
-
-#
-# TODO: move the following block (upto --- end ...) into testlib.sh
-#
-[ -d .git/refs/tags ] || mkdir -p .git/refs/tags
-
-sed_script="";
-
-# Answer the sha1 has associated with the tag. The tag must exist in .git or .git/refs/tags
-tag()
-{
- _tag=$1
- [ -f .git/refs/tags/$_tag ] || error "tag: \"$_tag\" does not exist"
- cat .git/refs/tags/$_tag
-}
-
-# Generate a commit using the text specified to make it unique and the tree
-# named by the tag specified.
-unique_commit()
-{
- _text=$1
- _tree=$2
- shift 2
- echo $_text | git-commit-tree $(tag $_tree) "$@"
-}
-
-# Save the output of a command into the tag specified. Prepend
-# a substitution script for the tag onto the front of $sed_script
-save_tag()
-{
- _tag=$1
- [ -n "$_tag" ] || error "usage: save_tag tag commit-args ..."
- shift 1
- "$@" >.git/refs/tags/$_tag
- sed_script="s/$(tag $_tag)/$_tag/g${sed_script+;}$sed_script"
-}
-
-# Replace unhelpful sha1 hashses with their symbolic equivalents
-entag()
-{
- sed "$sed_script"
-}
-
-# Execute a command after first saving, then setting the GIT_AUTHOR_EMAIL
-# tag to a specified value. Restore the original value on return.
-as_author()
-{
- _author=$1
- shift 1
- _save=$GIT_AUTHOR_EMAIL
-
- export GIT_AUTHOR_EMAIL="$_author"
- "$@"
- export GIT_AUTHOR_EMAIL="$_save"
-}
-
-commit_date()
-{
- _commit=$1
- git-cat-file commit $_commit | sed -n "s/^committer .*> \([0-9]*\) .*/\1/p"
-}
-
-on_committer_date()
-{
- _date=$1
- shift 1
- GIT_COMMITTER_DATE=$_date "$@"
-}
-
-# Execute a command and suppress any error output.
-hide_error()
-{
- "$@" 2>/dev/null
-}
-
-check_output()
-{
- _name=$1
- shift 1
- if eval "$*" | entag > $_name.actual
- then
- diff $_name.expected $_name.actual
- else
- return 1;
- fi
-}
-
-# Turn a reasonable test description into a reasonable test name.
-# All alphanums translated into -'s which are then compressed and stripped
-# from front and back.
-name_from_description()
-{
- tr "'" '-' | tr '~`!@#$%^&*()_+={}[]|\;:"<>,/? ' '-' | tr -s '-' | tr '[A-Z]' '[a-z]' | sed "s/^-*//;s/-*\$//"
-}
-
-
-# Execute the test described by the first argument, by eval'ing
-# command line specified in the 2nd argument. Check the status code
-# is zero and that the output matches the stream read from
-# stdin.
-test_output_expect_success()
-{
- _description=$1
- _test=$2
- [ $# -eq 2 ] || error "usage: test_output_expect_success description test <<EOF ... EOF"
- _name=$(echo $_description | name_from_description)
- cat > $_name.expected
- test_expect_success "$_description" "check_output $_name \"$_test\""
-}
-
-# --- end of stuff to move ---
+. ../t6000-lib.sh # t6xxx specific functions
# test-case specific test function
check_adjacency()
------------
^ permalink raw reply
* [PATCH 7/8] Make O(n) algorithm the default implementation of --bisect
From: Jon Seymour @ 2005-07-01 6:46 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch makes the O(n) the default implementation of the git-rev-list
--bisect switch.
The original O(n^2) algorithm is still available as --bisect-orig.
It is left around to provide a quick and simple way to verify the
accuracy of the O(n) algorithm.
A subsequent patch is supplied to remove support for --bisect-orig
completely.
Signed-off: Jon Seymour <jon.seymour@gmail.com>
---
Linus: you may choose to defer application of this patch if you are
not confident that the O(n) algorithm is good.
---
rev-list.c | 5 +++--
1 files changed, 3 insertions(+), 2 deletions(-)
342b91442a303b222f1601ef34ef37fffe5a9d57
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -16,6 +16,7 @@ static const char rev_list_usage[] =
" --min-age=epoch\n"
" --header\n"
" --pretty\n"
+ " --bisect\n"
" --merge-order [ --show-breaks ]";
static int bisect_list = 0;
@@ -365,11 +366,11 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
- if (!strcmp(arg, "--bisect-by-cut")) {
+ if (!strcmp(arg, "--bisect")) {
bisect_by_cut_option = 1;
continue;
}
- if (!strcmp(arg, "--bisect")) {
+ if (!strcmp(arg, "--bisect-orig")) {
bisect_list = 1;
continue;
}
------------
^ permalink raw reply
* [PATCH 2/8] Introduce unit tests for git-rev-list --bisect
From: Jon Seymour @ 2005-07-01 6:46 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch introduces some unit tests for the git-rev-list --bisect functionality.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
t/t6002-rev-list-bisect.sh | 247 ++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 247 insertions(+), 0 deletions(-)
create mode 100755 t/t6002-rev-list-bisect.sh
e733f670291290de2a7821e02eeb2a27f133aac0
diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
new file mode 100755
--- /dev/null
+++ b/t/t6002-rev-list-bisect.sh
@@ -0,0 +1,247 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Jon Seymour
+#
+test_description='Tests git-rev-list --bisect functionality'
+
+. ./test-lib.sh
+. ../t6000-lib.sh
+
+bc_expr()
+{
+bc <<EOF
+scale=1
+define abs(x) { if (x>=0) { return x; } else { return -x; } }
+define floor(x) { save=scale; scale=0; result=x/1; scale=save; return result; }
+$*
+EOF
+}
+
+# usage: test_bisection max-diff bisect-option head ^prune...
+#
+# e.g. test_bisection 1 --bisect l1 ^l0
+#
+test_bisection_diff()
+{
+ _max_diff=$1
+ _bisect_option=$2
+ shift 2
+ _bisection=$(git-rev-list $_bisect_option "$@")
+ _list_size=$(git-rev-list "$@" | wc -l)
+ _head=$1
+ shift 1
+ _bisection_size=$(git-rev-list $_bisection "$@" | wc -l)
+ [ -n "$_list_size" -a -n "$_bisection_size" ] || error "test_bisection_diff failed"
+ test_expect_success "bisection diff $_bisect_option $_head $* <= $_max_diff" "[ $(bc_expr "floor(abs($_list_size/2)-$_bisection_size)") -le $_max_diff ]"
+}
+
+date >path0
+git-update-cache --add path0
+save_tag tree git-write-tree
+on_committer_date "1971-08-16 00:00:00" hide_error save_tag root unique_commit root tree
+on_committer_date "1971-08-16 00:00:01" save_tag l0 unique_commit l0 tree -p root
+on_committer_date "1971-08-16 00:00:02" save_tag l1 unique_commit l1 tree -p l0
+on_committer_date "1971-08-16 00:00:03" save_tag l2 unique_commit l2 tree -p l1
+on_committer_date "1971-08-16 00:00:04" save_tag a0 unique_commit a0 tree -p l2
+on_committer_date "1971-08-16 00:00:05" save_tag a1 unique_commit a1 tree -p a0
+on_committer_date "1971-08-16 00:00:06" save_tag b1 unique_commit b1 tree -p a0
+on_committer_date "1971-08-16 00:00:07" save_tag c1 unique_commit c1 tree -p b1
+on_committer_date "1971-08-16 00:00:08" save_tag b2 unique_commit b2 tree -p b1
+on_committer_date "1971-08-16 00:00:09" save_tag b3 unique_commit b2 tree -p b2
+on_committer_date "1971-08-16 00:00:10" save_tag c2 unique_commit c2 tree -p c1 -p b2
+on_committer_date "1971-08-16 00:00:11" save_tag c3 unique_commit c3 tree -p c2
+on_committer_date "1971-08-16 00:00:12" save_tag a2 unique_commit a2 tree -p a1
+on_committer_date "1971-08-16 00:00:13" save_tag a3 unique_commit a3 tree -p a2
+on_committer_date "1971-08-16 00:00:14" save_tag b4 unique_commit b4 tree -p b3 -p a3
+on_committer_date "1971-08-16 00:00:15" save_tag a4 unique_commit a4 tree -p a3 -p b4 -p c3
+on_committer_date "1971-08-16 00:00:16" save_tag l3 unique_commit l3 tree -p a4
+on_committer_date "1971-08-16 00:00:17" save_tag l4 unique_commit l4 tree -p l3
+on_committer_date "1971-08-16 00:00:18" save_tag l5 unique_commit l5 tree -p l4
+tag l5 > .git/HEAD
+
+
+# E
+# / \
+# e1 |
+# | |
+# e2 |
+# | |
+# e3 |
+# | |
+# e4 |
+# | |
+# | f1
+# | |
+# | f2
+# | |
+# | f3
+# | |
+# | f4
+# | |
+# e5 |
+# | |
+# e6 |
+# | |
+# e7 |
+# | |
+# e8 |
+# \ /
+# F
+
+
+on_committer_date "1971-08-16 00:00:00" hide_error save_tag F unique_commit F tree
+on_committer_date "1971-08-16 00:00:01" save_tag e8 unique_commit e8 tree -p F
+on_committer_date "1971-08-16 00:00:02" save_tag e7 unique_commit e7 tree -p e8
+on_committer_date "1971-08-16 00:00:03" save_tag e6 unique_commit e6 tree -p e7
+on_committer_date "1971-08-16 00:00:04" save_tag e5 unique_commit e5 tree -p e6
+on_committer_date "1971-08-16 00:00:05" save_tag f4 unique_commit f4 tree -p F
+on_committer_date "1971-08-16 00:00:06" save_tag f3 unique_commit f3 tree -p f4
+on_committer_date "1971-08-16 00:00:07" save_tag f2 unique_commit f2 tree -p f3
+on_committer_date "1971-08-16 00:00:08" save_tag f1 unique_commit f1 tree -p f2
+on_committer_date "1971-08-16 00:00:09" save_tag e4 unique_commit e4 tree -p e5
+on_committer_date "1971-08-16 00:00:10" save_tag e3 unique_commit e3 tree -p e4
+on_committer_date "1971-08-16 00:00:11" save_tag e2 unique_commit e2 tree -p e3
+on_committer_date "1971-08-16 00:00:12" save_tag e1 unique_commit e1 tree -p e2
+on_committer_date "1971-08-16 00:00:13" save_tag E unique_commit E tree -p e1 -p f1
+
+on_committer_date "1971-08-16 00:00:00" hide_error save_tag U unique_commit U tree
+on_committer_date "1971-08-16 00:00:01" save_tag u0 unique_commit u0 tree -p U
+on_committer_date "1971-08-16 00:00:01" save_tag u1 unique_commit u1 tree -p u0
+on_committer_date "1971-08-16 00:00:02" save_tag u2 unique_commit u2 tree -p u0
+on_committer_date "1971-08-16 00:00:03" save_tag u3 unique_commit u3 tree -p u0
+on_committer_date "1971-08-16 00:00:04" save_tag u4 unique_commit u4 tree -p u0
+on_committer_date "1971-08-16 00:00:05" save_tag u5 unique_commit u5 tree -p u0
+on_committer_date "1971-08-16 00:00:06" save_tag V unique_commit V tree -p u1 -p u2 -p u3 -p u4 -p u5
+
+
+#
+# cd to t/trash and use
+#
+# git-rev-list ... 2>&1 | sed "$(cat sed.script)"
+#
+# if you ever want to manually debug the operation of git-rev-list
+#
+echo $sed_script > sed.script
+
+test_sequence()
+{
+ _bisect_option=$1
+
+ test_bisection_diff 0 $_bisect_option l0 ^root
+ test_bisection_diff 0 $_bisect_option l1 ^root
+ test_bisection_diff 0 $_bisect_option l2 ^root
+ test_bisection_diff 0 $_bisect_option a0 ^root
+ test_bisection_diff 0 $_bisect_option a1 ^root
+ test_bisection_diff 0 $_bisect_option a2 ^root
+ test_bisection_diff 0 $_bisect_option a3 ^root
+ test_bisection_diff 0 $_bisect_option b1 ^root
+ test_bisection_diff 0 $_bisect_option b2 ^root
+ test_bisection_diff 0 $_bisect_option b3 ^root
+ test_bisection_diff 0 $_bisect_option c1 ^root
+ test_bisection_diff 0 $_bisect_option c2 ^root
+ test_bisection_diff 0 $_bisect_option c3 ^root
+ test_bisection_diff 0 $_bisect_option E ^F
+ test_bisection_diff 0 $_bisect_option e1 ^F
+ test_bisection_diff 0 $_bisect_option e2 ^F
+ test_bisection_diff 0 $_bisect_option e3 ^F
+ test_bisection_diff 0 $_bisect_option e4 ^F
+ test_bisection_diff 0 $_bisect_option e5 ^F
+ test_bisection_diff 0 $_bisect_option e6 ^F
+ test_bisection_diff 0 $_bisect_option e7 ^F
+ test_bisection_diff 0 $_bisect_option f1 ^F
+ test_bisection_diff 0 $_bisect_option f2 ^F
+ test_bisection_diff 0 $_bisect_option f3 ^F
+ test_bisection_diff 0 $_bisect_option f4 ^F
+ test_bisection_diff 0 $_bisect_option E ^F
+
+ test_bisection_diff 1 $_bisect_option V ^U
+ test_bisection_diff 0 $_bisect_option V ^U ^u1 ^u2 ^u3
+ test_bisection_diff 0 $_bisect_option u1 ^U
+ test_bisection_diff 0 $_bisect_option u2 ^U
+ test_bisection_diff 0 $_bisect_option u3 ^U
+ test_bisection_diff 0 $_bisect_option u4 ^U
+ test_bisection_diff 0 $_bisect_option u5 ^U
+
+#
+# the following illustrate's Linus' binary bug blatt idea.
+#
+# assume the bug is actually at l3, but you don't know that - all you know is that l3 is broken
+# and it wasn't broken before
+#
+# keep bisecting the list, advancing the "bad" head and accumulating "good" heads until
+# the bisection point is the head - this is the bad point.
+#
+
+test_output_expect_success "--bisect l5 ^root" 'git-rev-list $_bisect_option l5 ^root' <<EOF
+c3
+EOF
+
+test_output_expect_success "$_bisect_option l5 ^root ^c3" 'git-rev-list $_bisect_option l5 ^root ^c3' <<EOF
+b4
+EOF
+
+test_output_expect_success "$_bisect_option l5 ^root ^c3 ^b4" 'git-rev-list $_bisect_option l5 ^c3 ^b4' <<EOF
+l3
+EOF
+
+test_output_expect_success "$_bisect_option l3 ^root ^c3 ^b4" 'git-rev-list $_bisect_option l3 ^root ^c3 ^b4' <<EOF
+a4
+EOF
+
+test_output_expect_success "$_bisect_option l5 ^b3 ^a3 ^b4 ^a4" 'git-rev-list $_bisect_option l3 ^b3 ^a3 ^a4' <<EOF
+l3
+EOF
+
+#
+# if l3 is bad, then l4 is bad too - so advance the bad pointer by making b4 the known bad head
+#
+
+test_output_expect_success "$_bisect_option l4 ^a2 ^a3 ^b ^a4" 'git-rev-list $_bisect_option l4 ^a2 ^a3 ^a4' <<EOF
+l3
+EOF
+
+test_output_expect_success "$_bisect_option l3 ^a2 ^a3 ^b ^a4" 'git-rev-list $_bisect_option l3 ^a2 ^a3 ^a4' <<EOF
+l3
+EOF
+
+# found!
+
+#
+# as another example, let's consider a4 to be the bad head, in which case
+#
+
+test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
+c2
+EOF
+
+test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2' <<EOF
+c3
+EOF
+
+test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3' <<EOF
+a4
+EOF
+
+# found!
+
+#
+# or consider c3 to be the bad head
+#
+
+test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
+c2
+EOF
+
+test_output_expect_success "$_bisect_option c3 ^a2 ^a3 ^b4 ^c2" 'git-rev-list $_bisect_option c3 ^a2 ^a3 ^b4 ^c2' <<EOF
+c3
+EOF
+
+# found!
+
+}
+
+test_sequence "--bisect"
+
+#
+#
+test_done
------------
^ permalink raw reply
* [PATCH 4/8] This patch introduces a O(n) bisection algorithm to git.
From: Jon Seymour @ 2005-07-01 6:46 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
For the purposes of comparison, this patch:
* enables debugging (-DDEBUG)
* adds a --debug switch to git-rev-list
* adds a --bisect-by-cut switch to git-rev-list
This allows the same git-rev-list binary to be used to compare the existing
O(n^2) behaviour (--bisect) with the O(n) behaviour (--bisect-by-cut).
A measure of complexity of each algorithm can be obtained on stderr,
by using the --debug switch.
My measurements suggest that on a 2000 commit kernel history, this
algorithm is ~ 5 times faster than the O(n^2) algorithm. If this
is true, it should be ~25 times faster on a 10,000 commit kernel history.
This is the difference between a 16 second bisection and a 0.6 second
bisection on that size repository.
The next patch in the series removes all the debug code.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
The Makefile is modified for one patch only to enable experimentation
with this patch. The next patch reverses the Makefile mods.
---
Makefile | 2
rev-list.c | 243 ++++++++++++++++++++++++++++++++++++++++++--
t/t6002-rev-list-bisect.sh | 1
3 files changed, 234 insertions(+), 12 deletions(-)
f26b313fc06d18a0aa44b0d3113805bcde0c0c1f
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -10,7 +10,7 @@
# break unless your underlying filesystem supports those sub-second times
# (my ext3 doesn't).
COPTS=-O2
-CFLAGS=-g $(COPTS) -Wall
+CFLAGS=-DDEBUG -g $(COPTS) -Wall
prefix=$(HOME)
bin=$(prefix)/bin
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -5,10 +5,19 @@
#include "blob.h"
#include "epoch.h"
-#define SEEN (1u << 0)
-#define INTERESTING (1u << 1)
-#define COUNTED (1u << 2)
-#define SHOWN (LAST_EPOCH_FLAG << 2)
+#define ABOVE (1u<<1)
+struct bisect_by_cut_node
+{
+ unsigned int flags;
+ unsigned int count;
+ struct commit_list * children;
+ struct commit_list * visible_parents;
+};
+
+#define SEEN (LAST_EPOCH_FLAG << 1)
+#define INTERESTING (LAST_EPOCH_FLAG << 2)
+#define COUNTED (LAST_EPOCH_FLAG << 3)
+#define SHOWN (LAST_EPOCH_FLAG << 4)
static const char rev_list_usage[] =
"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
@@ -34,6 +43,11 @@ static enum cmit_fmt commit_format = CMI
static int merge_order = 0;
static int show_breaks = 0;
static int stop_traversal = 0;
+static int bisect_by_cut_option = 0;
+#ifdef DEBUG
+static int debug = 0;
+static unsigned int complexity = 0;
+#endif
static void show_commit(struct commit *commit)
{
@@ -90,13 +104,10 @@ static int process_commit(struct commit
if (action == STOP) {
return STOP;
}
-
if (action == CONTINUE) {
return CONTINUE;
}
-
show_commit(commit);
-
return CONTINUE;
}
@@ -264,7 +275,7 @@ static int count_distance(struct commit_
while (p) {
nr += count_distance(p);
p = p->next;
- }
+ }
}
}
return nr;
@@ -272,6 +283,9 @@ static int count_distance(struct commit_
static void clear_distance(struct commit_list *list)
{
+#ifdef DEBUG
+ complexity++;
+#endif
while (list) {
struct commit *commit = list->item;
commit->object.flags &= ~COUNTED;
@@ -403,6 +417,196 @@ static struct commit *get_commit_referen
die("%s is unknown object", name);
}
+static inline struct bisect_by_cut_node * get_bisect_by_cut_node(struct commit * commit)
+{
+ return (struct bisect_by_cut_node *)commit->object.util;
+}
+
+#ifdef DEBUG
+static void print_bisect_by_cut_node(struct commit * commit, const char * prefix)
+{
+ struct bisect_by_cut_node * node = get_bisect_by_cut_node(commit);
+ fprintf(stderr, "%s%s %u %d\n", prefix, sha1_to_hex(commit->object.sha1), node->flags, node->count);
+}
+#endif
+
+/*
+ * Find the best bisection point by cutting a topological order in two then
+ * identifying a set of boundary nodes with a reachability known to be
+ * less than the desired bisection point. The boundary is advanced until all nodes
+ * in the boundary have a reachability greater than or equal to the desired
+ * reachability.
+ *
+ * This algorithm is roughly O(kn) where k is a factor related to the typical
+ * amount of parallel branching within the graph and is not related to n.
+ *
+ * The algorithm borrows the notion of making an arbitrary cut in the graph
+ * from the Kernighan-Lin (1969) graph bisection algorithm but differs in
+ * other respects. In particular, by using the topological order to make the
+ * cut the width of the advancing boundary is reduced to some kind of minimum.
+ * Full graph scans (e.g. calls to count_distance()) are avoided except where
+ * absolutely necessary (i.e. a merge node is encountered).
+ */
+struct commit * bisect_by_cut(struct commit_list * topological_order)
+{
+ unsigned int count=0;
+ unsigned int i;
+ struct commit_list * next;
+ struct commit_list * work = NULL;
+ struct commit * best = topological_order->item;
+ struct bisect_by_cut_node * nodes;
+ struct bisect_by_cut_node * next_node;
+ struct commit_list counter;
+ unsigned int fittest, goal;
+
+ counter.next=NULL;
+ /* count the size of the topological order */
+ next=topological_order;
+ while (next) {
+ count++;
+ next = next->next;
+ }
+ fittest=count;
+ i=(count+1)/2;
+ goal=count/2;
+ /* allocate and initialize the bisect_by_cut_node structure */
+ next_node=nodes=xmalloc(sizeof(*nodes)*count);
+ memset(nodes, 0, sizeof(*nodes)*count);
+ /*
+ * initialize the structures for all nodes of interest
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ next->item->object.util=next_node++;
+ next=next->next;
+ }
+ /*
+ * Mark half the nodes as being above the boundary.
+ * Mark nodes that aren't in the topological order as uninteresting.
+ * Initialize lists of visible children and parents.
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ struct commit * next_item = next->item;
+ struct commit_list * parents;
+
+ if (i > 0) {
+ next_node->flags |= ABOVE;
+ i--;
+ }
+ parents=next_item->parents;
+ while (parents) {
+ struct commit * parent = parents->item;
+ struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parent);
+
+ if (pn) {
+ commit_list_insert(next_item, &pn->children);
+ commit_list_insert(parent, &next_node->visible_parents);
+ } else
+ parent->object.flags |= UNINTERESTING;
+ parent->object.flags &= ~COUNTED;
+ parents=parents->next;
+ }
+ next=next->next;
+ next_node++;
+ }
+ /*
+ * Initialize the work queue with commits that are on the boundary
+ * and with < the desired reachability.
+ *
+ * We know these commits have less than the desired
+ * reachability because by the definition of the topological order
+ * nodes can only reach nodes to the right of them in the topological
+ * order and by construction, there there are no more than
+ * (count-1)/2 nodes to the right of each node in the boundary.
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ struct commit_list * parents;
+
+ parents=next_node->visible_parents;
+ while (parents) {
+ struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parents->item);
+
+ if ((next_node->flags & ABOVE)
+ && !(pn->flags & ABOVE)
+ && (pn->count == 0)) {
+ counter.item=parents->item;
+ pn->count = count_distance(&counter);
+ clear_distance(topological_order);
+ commit_list_insert(parents->item, &work);
+ }
+ parents=parents->next;
+ }
+ next=next->next;
+ next_node++;
+ }
+ /*
+ * Process the work queue until done.
+ */
+ while (work) {
+ struct commit * work_item = pop_commit(&work);
+ struct bisect_by_cut_node * wn = get_bisect_by_cut_node(work_item);
+ struct commit_list * children = wn->children;
+ unsigned int goal_test = wn->count;
+ unsigned int fitness = (goal_test>goal)?(goal_test-goal):(goal-goal_test);
+
+ if (fitness < fittest) {
+ best = work_item;
+ fittest = fitness;
+ }
+#ifdef DEBUG
+ if (debug) {
+ print_bisect_by_cut_node(work_item, "work ");
+ }
+#endif
+ if (goal_test < goal) {
+ while (children) {
+ struct bisect_by_cut_node * cn
+ = get_bisect_by_cut_node(children->item);
+ if (cn->flags & ABOVE) {
+ /* move the boundary up */
+ cn->flags &= ~ABOVE;
+ if (cn->visible_parents && !cn->visible_parents->next)
+ /*
+ * If the child only has one visible parent
+ * the goal_test increases by one
+ */
+ cn->count = wn->count+1;
+ else {
+ /*
+ * Otherwise, we need to count it explicitly.
+ */
+ counter.item=children->item;
+ cn->count = count_distance(&counter);
+ clear_distance(topological_order);
+ }
+ commit_list_insert(children->item, &work);
+ }
+ children=children->next;
+ }
+ } else if (goal_test > goal)
+ continue;
+ else
+ break; /* can't do better than this */
+ }
+ if (work)
+ free_commit_list(work);
+ /*
+ * reset the util pointers.
+ */
+ next=topological_order;
+ while (next) {
+ next->item->object.util=NULL;
+ next = next->next;
+ }
+ free(nodes);
+ return best;
+}
+
int main(int argc, char **argv)
{
struct commit_list *list = NULL;
@@ -440,6 +644,10 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
+ if (!strcmp(arg, "--bisect-by-cut")) {
+ bisect_by_cut_option = 1;
+ continue;
+ }
if (!strcmp(arg, "--bisect")) {
bisect_list = 1;
continue;
@@ -458,7 +666,12 @@ int main(int argc, char **argv)
show_breaks = 1;
continue;
}
-
+#ifdef DEBUG
+ if (!strcmp(arg, "--debug")) {
+ debug = 1;
+ continue;
+ }
+#endif
flags = 0;
if (*arg == '^') {
flags = UNINTERESTING;
@@ -476,12 +689,20 @@ int main(int argc, char **argv)
if (!merge_order) {
if (limited)
list = limit_list(list);
- show_commit_list(list);
+ if (!bisect_by_cut_option)
+ show_commit_list(list);
+ else {
+ sort_in_topological_order(&list);
+ show_commit(bisect_by_cut(list));
+ }
} else {
if (sort_list_in_merge_order(list, &process_commit)) {
die("merge order sort failed\n");
}
}
-
+#ifdef DEBUG
+ if (debug)
+ fprintf(stderr, "complexity=%d\n", complexity);
+#endif
return 0;
}
diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
--- a/t/t6002-rev-list-bisect.sh
+++ b/t/t6002-rev-list-bisect.sh
@@ -241,6 +241,7 @@ EOF
}
test_sequence "--bisect"
+test_sequence "--bisect-by-cut"
#
#
------------
^ permalink raw reply
* [PATCH 6/8] Move bisection algorithms into commit.c
From: Jon Seymour @ 2005-07-01 6:46 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch moves the bisection algorithms into commit.c.
The bisection algorithms are more lib'ish than tool'ish, so they
have been moved into commit.c.
This has required the definition of the UNINTERESTING and COUNTED
flags to be moved into commit.h and the introduction of the
the LAST_COMMIT_FLAG into commit.h.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
commit.c | 258 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
commit.h | 17 ++++
epoch.h | 12 +--
rev-list.c | 261 ------------------------------------------------------------
4 files changed, 281 insertions(+), 267 deletions(-)
751d906f842fabd42d191fe7df7ab61d44765de7
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -3,6 +3,15 @@
#include "commit.h"
#include "cache.h"
+#define ABOVE (1u<<1)
+struct bisect_by_cut_node
+{
+ unsigned int flags;
+ unsigned int count;
+ struct commit_list * children;
+ struct commit_list * visible_parents;
+};
+
struct sort_node
{
/*
@@ -453,3 +462,252 @@ void sort_in_topological_order(struct co
}
free(nodes);
}
+
+/*
+ * This is a truly stupid algorithm, but it's only
+ * used for bisection, and we just don't care enough.
+ *
+ * We care just barely enough to avoid recursing for
+ * non-merge entries.
+ */
+static int count_distance(struct commit_list *entry)
+{
+ int nr = 0;
+
+ while (entry) {
+ struct commit *commit = entry->item;
+ struct commit_list *p;
+
+ if (commit->object.flags & (UNINTERESTING | COUNTED))
+ break;
+ nr++;
+ commit->object.flags |= COUNTED;
+ p = commit->parents;
+ entry = p;
+ if (p) {
+ p = p->next;
+ while (p) {
+ nr += count_distance(p);
+ p = p->next;
+ }
+ }
+ }
+ return nr;
+}
+
+static void clear_distance(struct commit_list *list)
+{
+ while (list) {
+ struct commit *commit = list->item;
+ commit->object.flags &= ~COUNTED;
+ list = list->next;
+ }
+}
+
+struct commit_list *find_bisection(struct commit_list *list)
+{
+ int nr, closest;
+ struct commit_list *p, *best;
+
+ nr = 0;
+ p = list;
+ while (p) {
+ nr++;
+ p = p->next;
+ }
+ closest = 0;
+ best = list;
+
+ p = list;
+ while (p) {
+ int distance = count_distance(p);
+ clear_distance(list);
+ if (nr - distance < distance)
+ distance = nr - distance;
+ if (distance > closest) {
+ best = p;
+ closest = distance;
+ }
+ p = p->next;
+ }
+ if (best)
+ best->next = NULL;
+ return best;
+}
+
+static inline struct bisect_by_cut_node * get_bisect_by_cut_node(struct commit * commit)
+{
+ return (struct bisect_by_cut_node *)commit->object.util;
+}
+
+/*
+ * Find the best bisection point by cutting a topological order in two then
+ * identifying a set of boundary nodes with a reachability known to be
+ * less than the desired bisection point. The boundary is advanced until all nodes
+ * in the boundary have a reachability greater than or equal to the desired
+ * reachability.
+ *
+ * This algorithm is roughly O(kn) where k is a factor related to the typical
+ * amount of parallel branching within the graph and is not related to n.
+ *
+ * The algorithm borrows the notion of making an arbitrary cut in the graph
+ * from the Kernighan-Lin (1969) graph bisection algorithm but differs in
+ * other respects. In particular, by using the topological order to make the
+ * cut the width of the advancing boundary is reduced to some kind of minimum.
+ * Full graph scans (e.g. calls to count_distance()) are avoided except where
+ * absolutely necessary (i.e. a merge node is encountered).
+ */
+struct commit * bisect_by_cut(struct commit_list * topological_order)
+{
+ unsigned int count=0;
+ unsigned int i;
+ struct commit_list * next;
+ struct commit_list * work = NULL;
+ struct commit * best = topological_order->item;
+ struct bisect_by_cut_node * nodes;
+ struct bisect_by_cut_node * next_node;
+ struct commit_list counter;
+ unsigned int fittest, goal;
+
+ counter.next=NULL;
+ /* count the size of the topological order */
+ next=topological_order;
+ while (next) {
+ count++;
+ next = next->next;
+ }
+ fittest=count;
+ i=(count+1)/2;
+ goal=count/2;
+ /* allocate and initialize the bisect_by_cut_node structure */
+ next_node=nodes=xmalloc(sizeof(*nodes)*count);
+ memset(nodes, 0, sizeof(*nodes)*count);
+ /*
+ * initialize the structures for all nodes of interest
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ next->item->object.util=next_node++;
+ next=next->next;
+ }
+ /*
+ * Mark half the nodes as being above the boundary.
+ * Mark nodes that aren't in the topological order as uninteresting.
+ * Initialize lists of visible children and parents.
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ struct commit * next_item = next->item;
+ struct commit_list * parents;
+
+ if (i > 0) {
+ next_node->flags |= ABOVE;
+ i--;
+ }
+ parents=next_item->parents;
+ while (parents) {
+ struct commit * parent = parents->item;
+ struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parent);
+
+ if (pn) {
+ commit_list_insert(next_item, &pn->children);
+ commit_list_insert(parent, &next_node->visible_parents);
+ } else
+ parent->object.flags |= UNINTERESTING;
+ parent->object.flags &= ~COUNTED;
+ parents=parents->next;
+ }
+ next=next->next;
+ next_node++;
+ }
+ /*
+ * Initialize the work queue with commits that are on the boundary
+ * and with < the desired reachability.
+ *
+ * We know these commits have less than the desired
+ * reachability because by the definition of the topological order
+ * nodes can only reach nodes to the right of them in the topological
+ * order and by construction, there there are no more than
+ * (count-1)/2 nodes to the right of each node in the boundary.
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ struct commit_list * parents;
+
+ parents=next_node->visible_parents;
+ while (parents) {
+ struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parents->item);
+
+ if ((next_node->flags & ABOVE)
+ && !(pn->flags & ABOVE)
+ && (pn->count == 0)) {
+ counter.item=parents->item;
+ pn->count = count_distance(&counter);
+ clear_distance(topological_order);
+ commit_list_insert(parents->item, &work);
+ }
+ parents=parents->next;
+ }
+ next=next->next;
+ next_node++;
+ }
+ /*
+ * Process the work queue until done.
+ */
+ while (work) {
+ struct commit * work_item = pop_commit(&work);
+ struct bisect_by_cut_node * wn = get_bisect_by_cut_node(work_item);
+ struct commit_list * children = wn->children;
+ unsigned int goal_test = wn->count;
+ unsigned int fitness = (goal_test>goal)?(goal_test-goal):(goal-goal_test);
+
+ if (fitness < fittest) {
+ best = work_item;
+ fittest = fitness;
+ }
+ if (goal_test < goal) {
+ while (children) {
+ struct bisect_by_cut_node * cn
+ = get_bisect_by_cut_node(children->item);
+ if (cn->flags & ABOVE) {
+ /* move the boundary up */
+ cn->flags &= ~ABOVE;
+ if (cn->visible_parents && !cn->visible_parents->next)
+ /*
+ * If the child only has one visible parent
+ * the goal_test increases by one
+ */
+ cn->count = wn->count+1;
+ else {
+ /*
+ * Otherwise, we need to count it explicitly.
+ */
+ counter.item=children->item;
+ cn->count = count_distance(&counter);
+ clear_distance(topological_order);
+ }
+ commit_list_insert(children->item, &work);
+ }
+ children=children->next;
+ }
+ } else if (goal_test > goal)
+ continue;
+ else
+ break; /* can't do better than this */
+ }
+ if (work)
+ free_commit_list(work);
+ /*
+ * reset the util pointers.
+ */
+ next=topological_order;
+ while (next) {
+ next->item->object.util=NULL;
+ next = next->next;
+ }
+ free(nodes);
+ return best;
+}
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -4,6 +4,10 @@
#include "object.h"
#include "tree.h"
+#define UNINTERESTING (1u<<0)
+#define COUNTED (1u<<1)
+#define LAST_COMMIT_FLAG (COUNTED)
+
struct commit_list {
struct commit *item;
struct commit_list *next;
@@ -68,4 +72,17 @@ int count_parents(struct commit * commit
* a reachable from b => ord(b) < ord(a)
*/
void sort_in_topological_order(struct commit_list ** list);
+
+/*
+ * Uses an O(n^2) algorithm to find the commit that bisects
+ * the subgraph represented by the list of commits. The boundaries
+ * of the subgraph are delimited by adjacent nodes that have
+ */
+struct commit_list *find_bisection(struct commit_list *list);
+
+/*
+ * Uses O(n) to find the bisection of a list of commits
+ * which is already sorted in topological order.
+ */
+struct commit * bisect_by_cut(struct commit_list * topological_order);
#endif /* COMMIT_H */
diff --git a/epoch.h b/epoch.h
--- a/epoch.h
+++ b/epoch.h
@@ -10,12 +10,10 @@ typedef int (*emitter_func) (struct comm
int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter);
-#define UNINTERESTING (1u<<2)
-#define BOUNDARY (1u<<3)
-#define VISITED (1u<<4)
-#define DISCONTINUITY (1u<<5)
-#define DUPCHECK (1u<<6)
-#define LAST_EPOCH_FLAG (1u<<6)
-
+#define BOUNDARY (LAST_COMMIT_FLAG<<1)
+#define VISITED (LAST_COMMIT_FLAG<<2)
+#define DISCONTINUITY (LAST_COMMIT_FLAG<<3)
+#define DUPCHECK (LAST_COMMIT_FLAG<<4)
+#define LAST_EPOCH_FLAG (DUPCHECK)
#endif /* EPOCH_H */
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -5,19 +5,9 @@
#include "blob.h"
#include "epoch.h"
-#define ABOVE (1u<<1)
-struct bisect_by_cut_node
-{
- unsigned int flags;
- unsigned int count;
- struct commit_list * children;
- struct commit_list * visible_parents;
-};
-
#define SEEN (LAST_EPOCH_FLAG << 1)
#define INTERESTING (LAST_EPOCH_FLAG << 2)
-#define COUNTED (LAST_EPOCH_FLAG << 3)
-#define SHOWN (LAST_EPOCH_FLAG << 4)
+#define SHOWN (LAST_EPOCH_FLAG << 3)
static const char rev_list_usage[] =
"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
@@ -245,78 +235,6 @@ static int everybody_uninteresting(struc
return 1;
}
-/*
- * This is a truly stupid algorithm, but it's only
- * used for bisection, and we just don't care enough.
- *
- * We care just barely enough to avoid recursing for
- * non-merge entries.
- */
-static int count_distance(struct commit_list *entry)
-{
- int nr = 0;
-
- while (entry) {
- struct commit *commit = entry->item;
- struct commit_list *p;
-
- if (commit->object.flags & (UNINTERESTING | COUNTED))
- break;
- nr++;
- commit->object.flags |= COUNTED;
- p = commit->parents;
- entry = p;
- if (p) {
- p = p->next;
- while (p) {
- nr += count_distance(p);
- p = p->next;
- }
- }
- }
- return nr;
-}
-
-static void clear_distance(struct commit_list *list)
-{
- while (list) {
- struct commit *commit = list->item;
- commit->object.flags &= ~COUNTED;
- list = list->next;
- }
-}
-
-static struct commit_list *find_bisection(struct commit_list *list)
-{
- int nr, closest;
- struct commit_list *p, *best;
-
- nr = 0;
- p = list;
- while (p) {
- nr++;
- p = p->next;
- }
- closest = 0;
- best = list;
-
- p = list;
- while (p) {
- int distance = count_distance(p);
- clear_distance(list);
- if (nr - distance < distance)
- distance = nr - distance;
- if (distance > closest) {
- best = p;
- closest = distance;
- }
- p = p->next;
- }
- if (best)
- best->next = NULL;
- return best;
-}
-
struct commit_list *limit_list(struct commit_list *list)
{
struct commit_list *newlist = NULL;
@@ -410,183 +328,6 @@ static struct commit *get_commit_referen
die("%s is unknown object", name);
}
-static inline struct bisect_by_cut_node * get_bisect_by_cut_node(struct commit * commit)
-{
- return (struct bisect_by_cut_node *)commit->object.util;
-}
-
-/*
- * Find the best bisection point by cutting a topological order in two then
- * identifying a set of boundary nodes with a reachability known to be
- * less than the desired bisection point. The boundary is advanced until all nodes
- * in the boundary have a reachability greater than or equal to the desired
- * reachability.
- *
- * This algorithm is roughly O(kn) where k is a factor related to the typical
- * amount of parallel branching within the graph and is not related to n.
- *
- * The algorithm borrows the notion of making an arbitrary cut in the graph
- * from the Kernighan-Lin (1969) graph bisection algorithm but differs in
- * other respects. In particular, by using the topological order to make the
- * cut the width of the advancing boundary is reduced to some kind of minimum.
- * Full graph scans (e.g. calls to count_distance()) are avoided except where
- * absolutely necessary (i.e. a merge node is encountered).
- */
-struct commit * bisect_by_cut(struct commit_list * topological_order)
-{
- unsigned int count=0;
- unsigned int i;
- struct commit_list * next;
- struct commit_list * work = NULL;
- struct commit * best = topological_order->item;
- struct bisect_by_cut_node * nodes;
- struct bisect_by_cut_node * next_node;
- struct commit_list counter;
- unsigned int fittest, goal;
-
- counter.next=NULL;
- /* count the size of the topological order */
- next=topological_order;
- while (next) {
- count++;
- next = next->next;
- }
- fittest=count;
- i=(count+1)/2;
- goal=count/2;
- /* allocate and initialize the bisect_by_cut_node structure */
- next_node=nodes=xmalloc(sizeof(*nodes)*count);
- memset(nodes, 0, sizeof(*nodes)*count);
- /*
- * initialize the structures for all nodes of interest
- */
- next=topological_order;
- next_node=nodes;
- while (next) {
- next->item->object.util=next_node++;
- next=next->next;
- }
- /*
- * Mark half the nodes as being above the boundary.
- * Mark nodes that aren't in the topological order as uninteresting.
- * Initialize lists of visible children and parents.
- */
- next=topological_order;
- next_node=nodes;
- while (next) {
- struct commit * next_item = next->item;
- struct commit_list * parents;
-
- if (i > 0) {
- next_node->flags |= ABOVE;
- i--;
- }
- parents=next_item->parents;
- while (parents) {
- struct commit * parent = parents->item;
- struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parent);
-
- if (pn) {
- commit_list_insert(next_item, &pn->children);
- commit_list_insert(parent, &next_node->visible_parents);
- } else
- parent->object.flags |= UNINTERESTING;
- parent->object.flags &= ~COUNTED;
- parents=parents->next;
- }
- next=next->next;
- next_node++;
- }
- /*
- * Initialize the work queue with commits that are on the boundary
- * and with < the desired reachability.
- *
- * We know these commits have less than the desired
- * reachability because by the definition of the topological order
- * nodes can only reach nodes to the right of them in the topological
- * order and by construction, there there are no more than
- * (count-1)/2 nodes to the right of each node in the boundary.
- */
- next=topological_order;
- next_node=nodes;
- while (next) {
- struct commit_list * parents;
-
- parents=next_node->visible_parents;
- while (parents) {
- struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parents->item);
-
- if ((next_node->flags & ABOVE)
- && !(pn->flags & ABOVE)
- && (pn->count == 0)) {
- counter.item=parents->item;
- pn->count = count_distance(&counter);
- clear_distance(topological_order);
- commit_list_insert(parents->item, &work);
- }
- parents=parents->next;
- }
- next=next->next;
- next_node++;
- }
- /*
- * Process the work queue until done.
- */
- while (work) {
- struct commit * work_item = pop_commit(&work);
- struct bisect_by_cut_node * wn = get_bisect_by_cut_node(work_item);
- struct commit_list * children = wn->children;
- unsigned int goal_test = wn->count;
- unsigned int fitness = (goal_test>goal)?(goal_test-goal):(goal-goal_test);
-
- if (fitness < fittest) {
- best = work_item;
- fittest = fitness;
- }
- if (goal_test < goal) {
- while (children) {
- struct bisect_by_cut_node * cn
- = get_bisect_by_cut_node(children->item);
- if (cn->flags & ABOVE) {
- /* move the boundary up */
- cn->flags &= ~ABOVE;
- if (cn->visible_parents && !cn->visible_parents->next)
- /*
- * If the child only has one visible parent
- * the goal_test increases by one
- */
- cn->count = wn->count+1;
- else {
- /*
- * Otherwise, we need to count it explicitly.
- */
- counter.item=children->item;
- cn->count = count_distance(&counter);
- clear_distance(topological_order);
- }
- commit_list_insert(children->item, &work);
- }
- children=children->next;
- }
- } else if (goal_test > goal)
- continue;
- else
- break; /* can't do better than this */
- }
- if (work)
- free_commit_list(work);
- /*
- * reset the util pointers.
- */
- next=topological_order;
- while (next) {
- next->item->object.util=NULL;
- next = next->next;
- }
- free(nodes);
- return best;
-}
-
int main(int argc, char **argv)
{
struct commit_list *list = NULL;
------------
^ permalink raw reply
* [PATCH 8/8] Removes support for O(n^2) algorithm from git-rev-list completely
From: Jon Seymour @ 2005-07-01 6:46 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch completely removes support for the O(n^2) bisection
algorithm from commit.c, commit.h and rev-list.c
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Linus: I have included this patch to allow you to easily remove the O(n^2)
algorithm if that is your choice. I am not expecting you to do so.
---
commit.c | 31 -------------------------------
commit.h | 7 -------
rev-list.c | 7 -------
t/t6002-rev-list-bisect.sh | 1 -
4 files changed, 0 insertions(+), 46 deletions(-)
fa36c577acce519d1ef17bd807ab1486e1aa365a
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -504,37 +504,6 @@ static void clear_distance(struct commit
}
}
-struct commit_list *find_bisection(struct commit_list *list)
-{
- int nr, closest;
- struct commit_list *p, *best;
-
- nr = 0;
- p = list;
- while (p) {
- nr++;
- p = p->next;
- }
- closest = 0;
- best = list;
-
- p = list;
- while (p) {
- int distance = count_distance(p);
- clear_distance(list);
- if (nr - distance < distance)
- distance = nr - distance;
- if (distance > closest) {
- best = p;
- closest = distance;
- }
- p = p->next;
- }
- if (best)
- best->next = NULL;
- return best;
-}
-
static inline struct bisect_by_cut_node * get_bisect_by_cut_node(struct commit * commit)
{
return (struct bisect_by_cut_node *)commit->object.util;
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -74,13 +74,6 @@ int count_parents(struct commit * commit
void sort_in_topological_order(struct commit_list ** list);
/*
- * Uses an O(n^2) algorithm to find the commit that bisects
- * the subgraph represented by the list of commits. The boundaries
- * of the subgraph are delimited by adjacent nodes that have
- */
-struct commit_list *find_bisection(struct commit_list *list);
-
-/*
* Uses O(n) to find the bisection of a list of commits
* which is already sorted in topological order.
*/
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -19,7 +19,6 @@ static const char rev_list_usage[] =
" --bisect\n"
" --merge-order [ --show-breaks ]";
-static int bisect_list = 0;
static int tag_objects = 0;
static int tree_objects = 0;
static int blob_objects = 0;
@@ -252,8 +251,6 @@ struct commit_list *limit_list(struct co
}
p = &commit_list_insert(commit, p)->next;
}
- if (bisect_list)
- newlist = find_bisection(newlist);
return newlist;
}
@@ -370,10 +367,6 @@ int main(int argc, char **argv)
bisect_by_cut_option = 1;
continue;
}
- if (!strcmp(arg, "--bisect-orig")) {
- bisect_list = 1;
- continue;
- }
if (!strcmp(arg, "--objects")) {
tag_objects = 1;
tree_objects = 1;
diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
--- a/t/t6002-rev-list-bisect.sh
+++ b/t/t6002-rev-list-bisect.sh
@@ -241,7 +241,6 @@ EOF
}
test_sequence "--bisect"
-test_sequence "--bisect-by-cut"
#
#
------------
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Sven Verdoolaege @ 2005-07-01 7:01 UTC (permalink / raw)
To: Matthias Urlichs; +Cc: git
In-Reply-To: <20050630210023.GY10850@kiste.smurf.noris.de>
On Thu, Jun 30, 2005 at 11:00:23PM +0200, Matthias Urlichs wrote:
> Sven Verdoolaege:
> > It would also be nice if the user could pass extra options
> > to cvsps (notably '-z').
> >
> Ditto. ;-)
>
Actually, do you really have to call cvsps from within your
script ? Why don't you just keep the small shell script
that links cvsps to cvs2git (your version) ?
skimo
^ permalink raw reply
* Re: OOPS: unnumbered patch series
From: Junio C Hamano @ 2005-07-01 7:01 UTC (permalink / raw)
To: jon; +Cc: git, Linus Torvalds
In-Reply-To: <2cfc40320506302334357a9f29@mail.gmail.com>
>>>>> "JS" == Jon Seymour <jon.seymour@gmail.com> writes:
JS> Junio: this is an example where the special case would be good.
I do not think -n would number [PATCH 1/1]. Please try it and
complain loudly if that does not work for you.
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Matthias Urlichs @ 2005-07-01 7:25 UTC (permalink / raw)
To: Sven Verdoolaege; +Cc: git
In-Reply-To: <20050701070108.GA25803@pc117b.liacs.nl>
[-- Attachment #1: Type: text/plain, Size: 1120 bytes --]
Hi,
Sven Verdoolaege:
> On Thu, Jun 30, 2005 at 11:00:23PM +0200, Matthias Urlichs wrote:
> > Sven Verdoolaege:
> > > It would also be nice if the user could pass extra options
> > > to cvsps (notably '-z').
> > >
> > Ditto. ;-)
>
> Actually, do you really have to call cvsps from within your
> script ? Why don't you just keep the small shell script
> that links cvsps to cvs2git (your version) ?
I dislike temporary files, a shell pipe can't catch errors in earlier
stages without major hackery, Linus didn't have a problem with ripping
it out, and in an earlier life this script was called cvs2bk and called
bk directly, so I kept that.
Enough reasons? ;-) Sure, none of them really prevent me from doing it,
but OTOH I see no reason to resurrect the shell script either.
--
Matthias Urlichs | {M:U} IT Design @ m-u-it.de | smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
- -
Christianity has nothing to offer a happy man
living in a natural, intelligible universe.
-- George H. Smith, "Atheism: The Case Against God"
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: cvsimport: rewritten in Perl
From: Matthias Urlichs @ 2005-07-01 9:43 UTC (permalink / raw)
To: git
In-Reply-To: <Pine.LNX.4.63.0506301321350.1667@localhost.localdomain>
Hi, Nicolas Pitre wrote:
> On Thu, 30 Jun 2005, Matthias Urlichs wrote:
>
>> Duh. Will post an incremental patch shortly.
>
> Until Linus merges it I'd suggest that you post the updated full patch
> instead.
Personally, I'd prefer merging.
Linus/everybody_else :-) : Please pull from
rsync://netz.smurf.noris.de/git.git#cvs2git
--
Matthias Urlichs | {M:U} IT Design @ m-u-it.de | smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
- -
We were hungry when we got to Moscow, Soviet.
-- Groucho Marx
^ permalink raw reply
* Re: "git-send-pack"
From: Matthias Urlichs @ 2005-07-01 9:50 UTC (permalink / raw)
To: git
In-Reply-To: <Pine.LNX.4.58.0506301233270.14331@ppc970.osdl.org>
Hi, Linus Torvalds wrote:
> maybe it would be ok to
> even have "git-receive-pack" as the shell for the receiver side, so that
> you don't actually give the mirrorer any shell access at all.
You can probably just set the remote command (in ~/.ssh/authorized_keys)
to git-receive-pack. That also works around any $PATH issues.
Once this is stable, master.kernel.org should be updated with the
latest git.
--
Matthias Urlichs | {M:U} IT Design @ m-u-it.de | smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
- -
People are never so ready to believe you as when you say things in dispraise
of yourself; and you are never so much annoyed as when they take you at your
word.
-- Somerset Maugham
^ permalink raw reply
* Re: "git-send-pack"
From: Matthias Urlichs @ 2005-07-01 10:31 UTC (permalink / raw)
To: git
In-Reply-To: <42C46B86.8070006@zytor.com>
Hi, H. Peter Anvin wrote:
> In the end, it might be that the right thing to do for git on kernel.org
> is to have a single, unified object store which isn't accessible by
> anything other than git-specific protocols.
Makes sense.
> There would have to be some
> way of dealing with, for example, conflicting tags that apply to
> different repositories, though.
>
It seems that user-specific subdirectories in refs/heads (and, presumably,
../tags) mostly work already.
--
Matthias Urlichs | {M:U} IT Design @ m-u-it.de | smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
- -
Don't lock the barn after it is stolen.
^ permalink raw reply
* [PATCH] Trivial sed fix up in t/t6001
From: Mark Allen @ 2005-07-01 13:55 UTC (permalink / raw)
To: jon.seymour, torvalds; +Cc: git
[-- Attachment #1: Type: text/plain, Size: 359 bytes --]
Change the sed seperator in t/t6001.
This trivial patch removes the semicolon as the sed seperator in the t/t6001 test script
and replaces it with white space. This makes BSD sed(1) much happier.
Signed-off-by: Mark Allen <mrallen1@yahoo.com>
===
Jon,
If you could ack this patch or incorporate it into your tree, I'd be very obliged.
Thanks,
--Mark
[-- Attachment #2: 1890562984-t6001-sed-fixup.patch.txt --]
[-- Type: text/plain, Size: 486 bytes --]
diff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh
--- a/t/t6001-rev-list-merge-order.sh
+++ b/t/t6001-rev-list-merge-order.sh
@@ -40,7 +40,8 @@ save_tag()
[ -n "$_tag" ] || error "usage: save_tag tag commit-args ..."
shift 1
"$@" >.git/refs/tags/$_tag
- sed_script="s/$(tag $_tag)/$_tag/g${sed_script+;}$sed_script"
+ sed_script="s/$(tag $_tag)/$_tag/g
+$sed_script"
}
# Replace unhelpful sha1 hashses with their symbolic equivalents
^ permalink raw reply
* Tags
From: Eric W. Biederman @ 2005-07-01 13:56 UTC (permalink / raw)
To: H. Peter Anvin
Cc: Linus Torvalds, Daniel Barkalow, Git Mailing List, Junio C Hamano,
ftpadmin
In-Reply-To: <42C46B86.8070006@zytor.com>
"H. Peter Anvin" <hpa@zytor.com> writes:
> In the end, it might be that the right thing to do for git on kernel.org is to
> have a single, unified object store which isn't accessible by anything other
> than git-specific protocols. There would have to be some way of dealing with,
> for example, conflicting tags that apply to different repositories, though.
As far as I can tell public distributed tags are not that hard and if
you are going to be synching them it is probably worth working on.
The basic idea is that instead of having one global tag of
'linux-2.6.13-rc1' you have a global tag of
'torvalds@osdl.org/linux-2.6.13-rc1'.
The important part is that the tag namespace is made hierarchical
with at least 2 levels. Where the top level is a globally
unique tag owner id and the bottom level is the actual tag. This
prevents collisions when merging trees because two peoples
tags are never in the same namespace, as least when
people are not actively hostile :)
Still being a complete git dummy I think the trivial mapping is
to put tags in:
.git/refs/tags/user@domain/tag
and then have a symlink at:
.git/TAGS
that points to your default directory of tags.
Eric
^ permalink raw reply
* Re: "git-send-pack"
From: Jan Harkes @ 2005-07-01 14:43 UTC (permalink / raw)
To: Matthias Urlichs; +Cc: git
In-Reply-To: <pan.2005.07.01.10.31.53.906759@smurf.noris.de>
On Fri, Jul 01, 2005 at 12:31:53PM +0200, Matthias Urlichs wrote:
> > In the end, it might be that the right thing to do for git on kernel.org
> > is to have a single, unified object store which isn't accessible by
> > anything other than git-specific protocols.
>
> Makes sense.
>
> > There would have to be some
> > way of dealing with, for example, conflicting tags that apply to
> > different repositories, though.
>
> It seems that user-specific subdirectories in refs/heads (and, presumably,
> ../tags) mostly work already.
They work pretty well, the core git commands have no problem with them
and I just sent off some patches for gitweb and gitk.
All git/objects directories can be merged into a common repository. The
refs/heads and refs/tags be copied to user specific subdirectories.
Then a pull like,
git pull http://www.kernel.org/.../torvalds/linux-2.6.git
Would become,
git pull http://www.kernel.org/.../linux-2.6.git torvalds/linux-2.6/master
It would make rsync more expensive for people who are interested in only
a branch or two, but there is only one repository which should be easier
on the mirrors. The http, ssh, and some future 'pack' transfer methods
won't see a difference since they only pull the specific commits they
need to catch up with a branch.
Jan
^ permalink raw reply
* Re: OOPS: unnumbered patch series
From: Jon Seymour @ 2005-07-01 14:56 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, Linus Torvalds
In-Reply-To: <7vvf3vvwkh.fsf@assigned-by-dhcp.cox.net>
On 7/1/05, Junio C Hamano <junkio@cox.net> wrote:
> >>>>> "JS" == Jon Seymour <jon.seymour@gmail.com> writes:
>
> JS> Junio: this is an example where the special case would be good.
>
> I do not think -n would number [PATCH 1/1]. Please try it and
> complain loudly if that does not work for you.
>
Apologises loudly :-)
jon.
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox