* [PATCH 1/3] Factor out useful test case infrastructure from t/t6001... into t/t6000-lib.sh
From: Jon Seymour @ 2005-07-06 10:11 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>
---
This patch series introduces tests for the git-rev-list --bisect functionality
and includes Mark Allen's sed separator patch.
The patches included are:
[PATCH 1/3] Factor out useful test case infrastructure from t/t6001... into t/t6000-lib.sh
[PATCH 2/3] Introduce unit tests for git-rev-list --bisect
[PATCH 3/3] Change the sed seperator in t/t6000-lib.sh.
---
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
a6686d8335905d55ef6cf996af1d3eb229ad955c
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
* Re: cvsimport: rewritten in Perl
From: Wolfgang Denk @ 2005-07-06 10:24 UTC (permalink / raw)
To: git
In-Reply-To: <Pine.LNX.4.58.0507051936350.3570@g5.osdl.org>
[-- Attachment #1: Type: text/plain, Size: 663 bytes --]
In message <Pine.LNX.4.58.0507051936350.3570@g5.osdl.org> Linus Torvalds wrote:
>
> If you make it print out its <pid> and then pause, you can use
>
> ls -l /proc/<pid>/fd/
>
> to get an idea of what the files may be. Looks like the new perl version
> is leaking file descriptors..
It does. In case it's still of interest: log file attached.
Best regards,
Wolfgang Denk
Software Engineering: Embedded and Realtime Systems, Embedded Linux
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd@denx.de
It seems intuitively obvious to me, which means that it might be
wrong. -- Chris Torek
[-- Attachment #2: git-cvsimport-script.log.gz --]
[-- Type: application/x-gzip , Size: 1925 bytes --]
^ permalink raw reply
* [PATCH 2/3] Introduce unit tests for git-rev-list --bisect
From: Jon Seymour @ 2005-07-06 10:11 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
98721c0ec0eef1e96c51848c528da0a793fe07a5
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 3/3] Change the sed seperator in t/t6000-lib.sh.
From: Jon Seymour @ 2005-07-06 10:11 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This trivial patch removes the semicolon as the sed seperator in the t/t6000-lib.sh test script
and replaces it with white space. This makes BSD sed(1) much happier.
Signed-off-by: Mark Allen <mrallen1@yahoo.com>
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
I've applied this to the code that was moved from t/t6001... into t/t6000-lib.sh
---
t/t6000-lib.sh | 4 +++-
1 files changed, 3 insertions(+), 1 deletions(-)
ca2833542fed15371f9acde4c1bdeb6bc53046c0
diff --git a/t/t6000-lib.sh b/t/t6000-lib.sh
--- a/t/t6000-lib.sh
+++ b/t/t6000-lib.sh
@@ -28,7 +28,9 @@ 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
* Re: [ANNOUNCE] Cogito-0.12
From: Brian Gerst @ 2005-07-06 12:01 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050703234629.GF13848@pasky.ji.cz>
Petr Baudis wrote:
> Hello,
>
> I'm happy to announce the release of the 0.12 version of the Cogito
> SCM-like layer over Linus' GIT tree history storage tool. Get it at
>
> http://www.kernel.org/pub/software/scm/cogito/
>
> or cg-update if you have an older version cloned.
>
> I wanted to release it later with more cool features, but after all
> releasing often is good and people will get to test things more, and
> I wanted to make it possible for kernel.org to upgrade to newer RPM.
> But it may not be as stable as I'd wish and may have some rough edges,
> so be warned.
>
> This release contains the latest stuff from Linus, with all the
> packing stuff and everything. Other things include heaps of bugfixes,
> enhanced options parsing, ~/.cgrc support, cg-push, real cg-tag, and
> plenty of smaller but nice stuff. And more to come in next days!
>
> About cg-push, it:
>
> (i) works only locally or over git+ssh branches
>
> (ii) the head updated on the other side must be 'master' too
> (high priority to fix)
>
> (iii) the head updated on the other side is re-created, thus losing
> all attributes (ownership, permissions)
> (high priority to fix)
>
> (iv) won't update the remote working tree if there is any associated
> with the repository - do cg-cancel to catch up, but that will
> lose any local changes you did (note that I plan to rename
> cg-cancel to cg-reset)
>
> Also, I've deprecated rsync, as I explained in another mail. Use
> cg-branch-chg to change the branch URLs to some more sensible scheme -
> most likely HTTP, or SSH if you want to push as well.
I really question removing rsync before HTTP pulls become more
effecient. I did a complete pull of cogito from kernel.org, and http
took over 50 minutes to pull everything, while rsync was done in just
over 1 minute. I dared not even try to pull the full kernel at that speed.
I suspect that part of the problem is that the pull methods are doing a
depth first search, so we can't request the next object until the
current object is fully received and parsed. Changing to a breadth
first search would allow multiple requests in flight and asynchronous
processing which should speed things up. I am exploring using the
curl_multi_* functions to do this, but this will require changes to
common code in pull.c.
--
Brian Gerst
^ permalink raw reply
* BUG: cg-clone accepts '_' in git_ssh: URI's, but cg-push does not.
From: John Ellson @ 2005-07-06 3:08 UTC (permalink / raw)
To: git
BUG: cg-clone accepts '_' in git+ssh: URI's, but cg-push does not.
I suggest '_' be added to the allowed character table in send-pack.c
John
^ permalink raw reply
* [PATCH 1/2] Add a t/t6001 test case for a --merge-order bug
From: Jon Seymour @ 2005-07-06 14:44 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This test case demonstrates a problem with --merge-order.
A
|
B
|\
C D
|/
E
|
F
git-rev-list --merge-order A B doesn't produce the expected output of
A
B
D
C
E
F
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
This patch is known designed to apply on top of:
[PATCH 1/6] Temporary fixup to rev-list.c to restore expected order of arguments presented to --merge-order sort.
[PATCH 2/6] Swap order of insert_by_date arguments
[PATCH 3/6] Introduce struct rev_list_fns to rev-list.c to reduce amount of conditional processing.
[PATCH 4/6] Add a topological sort procedure to commit.c [rev 4]
[PATCH 5/6] Introduce --topo-order switch to git-rev-list
[PATCH 6/6] Change gitk so that it uses --topo-order rather than --merge-order
and
[PATCH 1/3] Factor out useful test case infrastructure from t/t6001... into t/t6000-lib.sh
[PATCH 2/3] Introduce unit tests for git-rev-list --bisect
[PATCH 3/3] Change the sed seperator in t/t6000-lib.sh.
A subsequent patch will fix the problem.
---
t/t6001-rev-list-merge-order.sh | 20 ++++++++++++++++++++
1 files changed, 20 insertions(+), 0 deletions(-)
3c04d86fbc9310e823a6a46ac7bf295fda57c7b7
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
@@ -438,6 +438,26 @@ a2
a1
EOF
+test_output_expect_success "--merge-order a4 l3" "git-rev-list --merge-order a4 l3" <<EOF
+l3
+a4
+c3
+c2
+c1
+b4
+b3
+b2
+b1
+a3
+a2
+a1
+a0
+l2
+l1
+l0
+root
+EOF
+
#
#
------------
^ permalink raw reply
* [PATCH 2/2] Fixes a problem with --merge-order A B (A is linear descendent of a merge B)
From: Jon Seymour @ 2005-07-06 14:44 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch passes the test case in the first patch of this series.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
e4f793b932b30a7bee16610e311630515fe88330
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -612,7 +612,7 @@ int sort_list_in_merge_order(struct comm
while (reversed) {
struct commit * next = pop_commit(&reversed);
- if (!(next->object.flags & VISITED)) {
+ if (!(next->object.flags & VISITED) && next!=base) {
sort_first_epoch(next, &stack);
if (reversed) {
/*
------------
^ permalink raw reply
* Re: [PATCH] Short-circuit git-clone-pack while cloning locally.
From: Linus Torvalds @ 2005-07-06 16:13 UTC (permalink / raw)
To: Junio C Hamano; +Cc: David S. Miller, Git Mailing List
In-Reply-To: <7v8y0kxsfq.fsf_-_@assigned-by-dhcp.cox.net>
On Wed, 6 Jul 2005, Junio C Hamano wrote:
>
> By invitation.
>
> ------------
> When we are cloning a repository on a local filesystem [...]
Hmm.. Did you test the ssh case?
> +case "$local_use,$is_local" in
> +default,f)
> + ;;
It would seem that you don't do anything at all for the non-local case.
Linus
^ permalink raw reply
* [PATCH 9/13] Factor out useful test case infrastructure from t/t6001... into t/t6000-lib.sh
From: Jon Seymour @ 2005-07-06 16:39 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
98aea4ed9ea8b2c17b65502cab27b77beb6fdaab
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 13/13] Fixes a problem with --merge-order A B (A is linear descendent of a merge B)
From: Jon Seymour @ 2005-07-06 16:39 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch passes the test case introduced by the previous patch.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
6f7f90901ec4aafd12ac4179110b78fc426395cd
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -612,7 +612,7 @@ int sort_list_in_merge_order(struct comm
while (reversed) {
struct commit * next = pop_commit(&reversed);
- if (!(next->object.flags & VISITED)) {
+ if (!(next->object.flags & VISITED) && next!=base) {
sort_first_epoch(next, &stack);
if (reversed) {
/*
------------
^ permalink raw reply
* [PATCH 12/13] Add a t/t6001 test case for a --merge-order bug
From: Jon Seymour @ 2005-07-06 16:39 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This test case demonstrates a problem with --merge-order.
A
|
B
|\
C D
|/
E
|
F
git-rev-list --merge-order A B doesn't produce the expected output of
A
B
D
C
E
F
The problem is fixed by a subsequent patch.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
t/t6001-rev-list-merge-order.sh | 20 ++++++++++++++++++++
1 files changed, 20 insertions(+), 0 deletions(-)
eb702818ec4e0db40da78dd27623d33fdbaabe8b
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
@@ -438,6 +438,26 @@ a2
a1
EOF
+test_output_expect_success "--merge-order a4 l3" "git-rev-list --merge-order a4 l3" <<EOF
+l3
+a4
+c3
+c2
+c1
+b4
+b3
+b2
+b1
+a3
+a2
+a1
+a0
+l2
+l1
+l0
+root
+EOF
+
#
#
------------
^ permalink raw reply
* [PATCH 11/13] Change the sed seperator in t/t6000-lib.sh.
From: Jon Seymour @ 2005-07-06 16:39 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This trivial patch removes the semicolon as the sed seperator in the t/t6000-lib.sh test script
and replaces it with white space. This makes BSD sed(1) much happier.
Signed-off-by: Mark Allen <mrallen1@yahoo.com>
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
I've applied this to the code that was moved from t/t6001... into t/t6000-lib.sh
---
t/t6000-lib.sh | 4 +++-
1 files changed, 3 insertions(+), 1 deletions(-)
b49ca001a8b60bdcdce989a65b120a7183486cf8
diff --git a/t/t6000-lib.sh b/t/t6000-lib.sh
--- a/t/t6000-lib.sh
+++ b/t/t6000-lib.sh
@@ -28,7 +28,9 @@ 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
* [PATCH 10/13] Introduce unit tests for git-rev-list --bisect
From: Jon Seymour @ 2005-07-06 16:39 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
5c47ce16a5b71238bddd7ae75cc694b9479fd0d9
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 8/13] Fix handling of duplicates by topological order.
From: Jon Seymour @ 2005-07-06 16:39 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
git-rev-list --topo-order HEAD HEAD
caused a segmentation violation.
This has now been fixed.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
commit.c | 15 +++++++++++----
commit.h | 3 +++
epoch.h | 13 ++++++-------
rev-list.c | 8 ++++----
4 files changed, 24 insertions(+), 15 deletions(-)
60a355172fdf6583465e1c237a3e82af64065332
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -374,11 +374,17 @@ void sort_in_topological_order(struct co
struct sort_node * next_nodes;
int count = 0;
- /* determine the size of the list */
- while (next) {
- next = next->next;
- count++;
+ /* determine the size of the list and elide duplicates */
+ while (*pptr) {
+ next=*pptr;
+ if (!(next->item->object.flags & DUPCHECK)) {
+ count++;
+ next->item->object.flags |= DUPCHECK;
+ pptr=&next->next;
+ } else
+ *pptr=next->next;
}
+ pptr=list;
/* allocate an array to help sort the list */
nodes = xcalloc(count, sizeof(*nodes));
/* link the list to the array */
@@ -387,6 +393,7 @@ void sort_in_topological_order(struct co
while (next) {
next_nodes->list_item = next;
next->item->object.util = next_nodes;
+ next->item->object.flags &= ~DUPCHECK;
next_nodes++;
next = next->next;
}
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -4,6 +4,9 @@
#include "object.h"
#include "tree.h"
+#define DUPCHECK (1u<<0)
+#define LAST_COMMIT_FLAG (DUPCHECK)
+
struct commit_list {
struct commit *item;
struct commit_list *next;
diff --git a/epoch.h b/epoch.h
--- a/epoch.h
+++ b/epoch.h
@@ -1,6 +1,6 @@
#ifndef EPOCH_H
#define EPOCH_H
-
+#include "commit.h"
// return codes for emitter_func
#define STOP 0
@@ -10,12 +10,11 @@ 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 UNINTERESTING (LAST_COMMIT_FLAG<<1)
+#define BOUNDARY (LAST_COMMIT_FLAG<<2)
+#define VISITED (LAST_COMMIT_FLAG<<3)
+#define DISCONTINUITY (LAST_COMMIT_FLAG<<4)
+#define LAST_EPOCH_FLAG (LAST_COMMIT_FLAG<<4)
#endif /* EPOCH_H */
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -5,10 +5,10 @@
#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 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"
------------
^ permalink raw reply
* [PATCH 7/13] Tidy up - slight simplification of rev-list.c
From: Jon Seymour @ 2005-07-06 16:39 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch implements a small tidy up of rev-list.c to reduce
(but not eliminate) the amount of ugliness associated
with the merge_order flag.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Linus: I decided not to abstract this out as a function
as _too_ much abstraction can be a bad thing from a
readability point of view. Let me know if you disagree.
---
rev-list.c | 10 +++-------
1 files changed, 3 insertions(+), 7 deletions(-)
f5d3f5e7540acdd319da2697a9ad39d1cfe09796
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -78,19 +78,15 @@ static void show_commit(struct commit *c
static int filter_commit(struct commit * commit)
{
- if (merge_order && stop_traversal && commit->object.flags & BOUNDARY)
+ if (stop_traversal && (commit->object.flags & BOUNDARY))
return STOP;
if (commit->object.flags & (UNINTERESTING|SHOWN))
return CONTINUE;
if (min_age != -1 && (commit->date > min_age))
return CONTINUE;
if (max_age != -1 && (commit->date < max_age)) {
- if (!merge_order)
- return STOP;
- else {
- stop_traversal = 1;
- return CONTINUE;
- }
+ stop_traversal=1;
+ return merge_order?CONTINUE:STOP;
}
if (max_count != -1 && !max_count--)
return STOP;
------------
^ permalink raw reply
* [PATCH 6/13] Change gitk so that it uses --topo-order rather than --merge-order
From: Jon Seymour @ 2005-07-06 16:39 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This change is made so that gitk --all produces the same result for
every user irrespective of whether git-rev-parse --all produces
the same result for every user. By using --topo-order rather than
--merge-order this can be guaranteed and the existing (non-timestamp dependent)
behaviour of --merge-order can be maintained.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Paul, could you review this patch and if you agree, ack it.
The rationale for changing gitk to use --topo-order is that git-rev-list will
produce the same order for --topo-order irrespective of the order of the
start list, whereas git-rev-list --merge-order produces an order that is deliberately
sensitive to the order of the start list.
Linus wants gitk --all to behave the same way, irrespective of what order
git-rev-parse --all produces its output. I want --merge-order to keep its
existing behaviour, so we agreed on this compromise whereby gitk uses
--topo-order rather than --merge-order by default.
My understanding of your code is that you only expect a minimal topological ordering
guarantee and the ordering produced by --topo-order should be sufficient
for your needs - that is, you don't rely on the other aspect of the
--merge-order invariant.
I'll leave it to you and Linus to decide how you want to manage the merge between
your HEAD and Linus'.
---
gitk | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
19c9032b06b370511ef1091434df0d1d644fee06
diff --git a/gitk b/gitk
--- a/gitk
+++ b/gitk
@@ -37,7 +37,7 @@ proc getcommits {rargs} {
set parsed_args $rargs
}
if [catch {
- set commfd [open "|git-rev-list --header --merge-order $parsed_args" r]
+ set commfd [open "|git-rev-list --header --topo-order $parsed_args" r]
} err] {
puts stderr "Error executing git-rev-list: $err"
exit 1
------------
^ permalink raw reply
* [PATCH 5/13] Introduce --topo-order switch to git-rev-list
From: Jon Seymour @ 2005-07-06 16:39 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch introduces a --topo-order switch to git-rev-list.
When this --switch is specified, a minimal topological sort
weaker than the --merge-order sort is applied to the output
list.
The invariant of the resulting list is:
a is reachable from b => ord(b) < ord(a)
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Documentation/git-rev-list.txt | 9 +++++++--
rev-list.c | 27 +++++++++++++++++++++++++--
2 files changed, 32 insertions(+), 4 deletions(-)
99d3a2318171f611f1c186a7ed4881b2f34b6b49
diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
--- a/Documentation/git-rev-list.txt
+++ b/Documentation/git-rev-list.txt
@@ -9,13 +9,15 @@ git-rev-list - Lists commit objects in r
SYNOPSIS
--------
-'git-rev-list' [ *--max-count*=number ] [ *--max-age*=timestamp ] [ *--min-age*=timestamp ] [ *--merge-order* [ *--show-breaks* ] ] <commit>
+'git-rev-list' [ *--max-count*=number ] [ *--max-age*=timestamp ] [ *--min-age*=timestamp ] [ *--merge-order* ] [ *--show-breaks* ] [ *--topo-order* ] <commit>... ^<prune>...
DESCRIPTION
-----------
Lists commit objects in reverse chronological order starting at the
given commit, taking ancestry relationship into account. This is
-useful to produce human-readable log output.
+useful to produce human-readable log output. If prune points are specified
+with ^<prune>... arguments, the output will not include any commits reachable
+from (and including) the prune points.
If *--merge-order* is specified, the commit history is decomposed into a
unique sequence of minimal, non-linear epochs and maximal, linear epochs.
@@ -59,6 +61,9 @@ represent an arbtirary DAG in a linear f
*--show-breaks* implies **-merge-order*.
+If *--topo-order* is specified, the commit history is sorted in a topological
+order that is weaker than the topological order generated by *--merge-order*.
+
Author
------
Written by Linus Torvalds <torvalds@osdl.org>
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -20,6 +20,7 @@ static const char rev_list_usage[] =
" --unpacked\n"
" --header\n"
" --pretty\n"
+ " --topo-order\n"
" --merge-order [ --show-breaks ]";
static int unpacked = 0;
@@ -38,10 +39,12 @@ static enum cmit_fmt commit_format = CMI
static int merge_order = 0;
static int show_breaks = 0;
static int stop_traversal = 0;
+static int topo_order = 0;
struct rev_list_fns {
struct commit_list * (*insert)(struct commit *, struct commit_list **);
struct commit_list * (*limit)(struct commit_list *);
+ void (*sort)(struct commit_list **);
void (*process)(struct commit_list *);
};
@@ -425,12 +428,21 @@ static void merge_order_sort(struct comm
struct rev_list_fns default_fns = {
&insert_by_date,
&limit_list,
- &show_commit_list
+ NULL,
+ &show_commit_list
+};
+
+struct rev_list_fns topo_order_fns = {
+ &insert_by_date,
+ &limit_list,
+ &sort_in_topological_order,
+ &show_commit_list
};
struct rev_list_fns merge_order_fns = {
&commit_list_insert,
NULL,
+ NULL,
&merge_order_sort
};
@@ -439,7 +451,7 @@ int main(int argc, char **argv)
struct commit_list *list = NULL;
struct commit_list *sorted = NULL;
struct commit_list **list_tail = &list;
- struct rev_list_fns * fns = &default_fns;
+ struct rev_list_fns * fns = NULL;
int i, limited = 0;
for (i = 1 ; i < argc; i++) {
@@ -498,6 +510,11 @@ int main(int argc, char **argv)
merge_order = 1;
continue;
}
+ if (!strcmp(arg, "--topo-order")) {
+ topo_order = 1;
+ limited=1;
+ continue;
+ }
flags = 0;
if (*arg == '^') {
@@ -512,11 +529,17 @@ int main(int argc, char **argv)
}
if (merge_order)
fns=&merge_order_fns;
+ else if (topo_order)
+ fns=&topo_order_fns;
+ else
+ fns=&default_fns;
while (list)
fns->insert(pop_commit(&list), &sorted);
list=sorted;
if (limited && fns->limit)
list = fns->limit(list);
+ if (fns->sort)
+ fns->sort(&list);
fns->process(list);
return 0;
}
------------
^ permalink raw reply
* [PATCH 2/13] Swap order of insert_by_date arguments
From: Jon Seymour @ 2005-07-06 16:39 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
Swap the order of insert_by_date arguments so that it
matches the order of commit_list_insert.
This patch anticipates a future change which will call the
function via a pointer.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
commit.c | 8 ++++----
commit.h | 6 +++++-
epoch.c | 4 ++--
rev-list.c | 2 +-
4 files changed, 12 insertions(+), 8 deletions(-)
486d4dee9772a59b955574951e8d4946b75cf9fa
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -147,7 +147,7 @@ void free_commit_list(struct commit_list
}
}
-void insert_by_date(struct commit_list **list, struct commit *item)
+struct commit_list * insert_by_date(struct commit *item, struct commit_list **list)
{
struct commit_list **pp = list;
struct commit_list *p;
@@ -157,7 +157,7 @@ void insert_by_date(struct commit_list *
}
pp = &p->next;
}
- commit_list_insert(item, pp);
+ return commit_list_insert(item, pp);
}
@@ -165,7 +165,7 @@ void sort_by_date(struct commit_list **l
{
struct commit_list *ret = NULL;
while (*list) {
- insert_by_date(&ret, (*list)->item);
+ insert_by_date((*list)->item, &ret);
*list = (*list)->next;
}
*list = ret;
@@ -186,7 +186,7 @@ struct commit *pop_most_recent_commit(st
parse_commit(commit);
if (!(commit->object.flags & mark)) {
commit->object.flags |= mark;
- insert_by_date(list, commit);
+ insert_by_date(commit, list);
}
parents = parents->next;
}
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -44,7 +44,11 @@ enum cmit_fmt {
extern enum cmit_fmt get_commit_format(const char *arg);
extern unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space);
-void insert_by_date(struct commit_list **list, struct commit *item);
+/*
+ * Inserts item into the list specified in most recent commit date first order.
+ * A pointer to the most recently inserted item is returned.
+ */
+struct commit_list * insert_by_date(struct commit *item, struct commit_list **list);
/** Removes the first commit from a list sorted by date, and adds all
* of its parents.
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -255,11 +255,11 @@ static int find_base_for_list(struct com
if (!parent_node) {
parent_node = new_mass_counter(parent, &distribution);
- insert_by_date(&pending, parent);
+ insert_by_date(parent, &pending);
commit_list_insert(parent, &cleaner);
} else {
if (!compare(&parent_node->pending, get_zero()))
- insert_by_date(&pending, parent);
+ insert_by_date(parent, &pending);
add(&parent_node->pending, &parent_node->pending, &distribution);
}
}
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -483,7 +483,7 @@ int main(int argc, char **argv)
if (!commit)
continue;
if (!merge_order)
- insert_by_date(&list, commit);
+ insert_by_date(commit, &list);
else
commit_list_insert(commit, &list);
}
------------
^ permalink raw reply
* [PATCH 0/13] Patch Series
From: Jon Seymour @ 2005-07-06 16:39 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
I have re-issued the patches I have created in the last day after checking
that they apply correctly when applied in this order to the
current Linus HEAD (b43d44779bf98977b211256f936d0edda8a9625a)
Introduction of --topo-order and tidy up of rev-list.c
[PATCH 1/13] Temporary fixup to rev-list.c to restore expected order of arguments presented to --merge-order sort.
[PATCH 2/13] Swap order of insert_by_date arguments
[PATCH 3/13] Introduce struct rev_list_fns to rev-list.c to reduce amount of conditional processing.
[PATCH 4/13] Add a topological sort procedure to commit.c [rev 4]
[PATCH 5/13] Introduce --topo-order switch to git-rev-list
[PATCH 6/13] Change gitk so that it uses --topo-order rather than --merge-order
[PATCH 7/13] Tidy up - slight simplification of rev-list.c
[PATCH 8/13] Fix handling of duplicates by topological order.
Tidy up and extension of t6xxx test cases
[PATCH 9/13] Factor out useful test case infrastructure from t/t6001... into t/t6000-lib.sh
[PATCH 10/13] Introduce unit tests for git-rev-list --bisect
[PATCH 11/13] Change the sed seperator in t/t6000-lib.sh.
Test for and fix of recently discovered --merge-order bug
[PATCH 12/13] Add a t/t6001 test case for a --merge-order bug
[PATCH 13/13] Fixes a problem with --merge-order A B (A is linear descendent of a merge B)
^ permalink raw reply
* [PATCH 1/13] Temporary fixup to rev-list.c to restore expected order of arguments presented to --merge-order sort.
From: Jon Seymour @ 2005-07-06 16:39 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch adds a hacky special case to the rev-list main to restore the order in which
the --merge-order sort algorithm receives arguments.
A subsequent patch will abstract this out more cleanly.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
rev-list.c | 5 ++++-
1 files changed, 4 insertions(+), 1 deletions(-)
c63fe4678d33db15db076606f7a133868e91f1bc
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -482,7 +482,10 @@ int main(int argc, char **argv)
commit = get_commit_reference(arg, flags);
if (!commit)
continue;
- insert_by_date(&list, commit);
+ if (!merge_order)
+ insert_by_date(&list, commit);
+ else
+ commit_list_insert(commit, &list);
}
if (!merge_order) {
------------
^ permalink raw reply
* [PATCH 4/13] Add a topological sort procedure to commit.c [rev 4]
From: Jon Seymour @ 2005-07-06 16:39 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
support for a --topo-order flag.
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
[rev 4]
* re-applied rev 3 to new patch series - no other change
---
commit.c | 107 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
commit.h | 13 ++++++++
2 files changed, 120 insertions(+), 0 deletions(-)
155c21a7e0295deab710345d22f0551706a7f84a
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
@@ -59,4 +59,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 3/13] Introduce struct rev_list_fns to rev-list.c to reduce amount of conditional processing.
From: Jon Seymour @ 2005-07-06 16:39 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
Per a suggestion from Linus, I have introduced the rev_list_fns structure into
rev-list.c
The intent of this change is to make use of a strategy pattern to configure
the behaviour of git-rev-list and so help limit the ever-increasing
proliferation of boolean switches throughout the body of the code.
This change also makes --show-breaks imply --merge-order rather than require
it as before. There was no advantage to the previous strict argument
checking.
A subsequent change will take advantage of this pattern to introduce a
topological sort switch.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Documentation/git-rev-list.txt | 2 +
rev-list.c | 54 +++++++++++++++++++++++++++-------------
2 files changed, 38 insertions(+), 18 deletions(-)
77418fc85cc40e56ef66c5031025399c5e6ed787
diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
--- a/Documentation/git-rev-list.txt
+++ b/Documentation/git-rev-list.txt
@@ -57,7 +57,7 @@ Commits marked with (^) are not parents
These "breaks" represent necessary discontinuities implied by trying to
represent an arbtirary DAG in a linear form.
-*--show-breaks* is only valid if *--merge-order* is also specified.
+*--show-breaks* implies **-merge-order*.
Author
------
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -39,6 +39,12 @@ static int merge_order = 0;
static int show_breaks = 0;
static int stop_traversal = 0;
+struct rev_list_fns {
+ struct commit_list * (*insert)(struct commit *, struct commit_list **);
+ struct commit_list * (*limit)(struct commit_list *);
+ void (*process)(struct commit_list *);
+};
+
static void show_commit(struct commit *commit)
{
commit->object.flags |= SHOWN;
@@ -410,9 +416,30 @@ static struct commit *get_commit_referen
die("%s is unknown object", name);
}
+static void merge_order_sort(struct commit_list * list)
+{
+ if (sort_list_in_merge_order(list, &process_commit))
+ die("commit graph traversal failed");
+}
+
+struct rev_list_fns default_fns = {
+ &insert_by_date,
+ &limit_list,
+ &show_commit_list
+};
+
+struct rev_list_fns merge_order_fns = {
+ &commit_list_insert,
+ NULL,
+ &merge_order_sort
+};
+
int main(int argc, char **argv)
{
struct commit_list *list = NULL;
+ struct commit_list *sorted = NULL;
+ struct commit_list **list_tail = &list;
+ struct rev_list_fns * fns = &default_fns;
int i, limited = 0;
for (i = 1 ; i < argc; i++) {
@@ -468,6 +495,7 @@ int main(int argc, char **argv)
}
if (!strcmp(arg, "--show-breaks")) {
show_breaks = 1;
+ merge_order = 1;
continue;
}
@@ -477,26 +505,18 @@ int main(int argc, char **argv)
arg++;
limited = 1;
}
- if (show_breaks && !merge_order)
- usage(rev_list_usage);
commit = get_commit_reference(arg, flags);
if (!commit)
continue;
- if (!merge_order)
- insert_by_date(commit, &list);
- else
- commit_list_insert(commit, &list);
+ list_tail = &commit_list_insert(commit, list_tail)->next;
}
-
- if (!merge_order) {
- if (limited)
- list = limit_list(list);
- show_commit_list(list);
- } else {
- if (sort_list_in_merge_order(list, &process_commit)) {
- die("merge order sort failed\n");
- }
- }
-
+ if (merge_order)
+ fns=&merge_order_fns;
+ while (list)
+ fns->insert(pop_commit(&list), &sorted);
+ list=sorted;
+ if (limited && fns->limit)
+ list = fns->limit(list);
+ fns->process(list);
return 0;
}
------------
^ permalink raw reply
* Re: BUG: cg-clone accepts '_' in git_ssh: URI's, but cg-push does not.
From: Horst von Brand @ 2005-07-06 16:58 UTC (permalink / raw)
To: John Ellson; +Cc: git
In-Reply-To: <pan.2005.07.06.03.08.55.724181@comcast.net>
John Ellson <john.ellson@comcast.net> wrote:
> BUG: cg-clone accepts '_' in git+ssh: URI's, but cg-push does not.
Right. '_' is illegal in domain names...
--
Dr. Horst H. von Brand User #22616 counter.li.org
Departamento de Informatica Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria +56 32 654239
Casilla 110-V, Valparaiso, Chile Fax: +56 32 797513
^ permalink raw reply
* Re: [PATCH] Add commify function to cg-Xlib
From: Frank Sorenson @ 2005-07-06 17:57 UTC (permalink / raw)
To: Petr Baudis; +Cc: Git Mailing List
In-Reply-To: <20050706075938.GB7054@pasky.ji.cz>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Petr Baudis wrote:
> I don't know. Could you give some supporting argumentation, please? Is
> it really that hard to read for the Americans without the commas? It is
> at least harder to read for me as an European - we don't have any
> commas in there, just spaces (if anything at all). Besides, the number
> is usually not in higher order than thousands, so... why is it worth it?
Okay. Not a problem. It just cleaned things up a little for me. If I
want to keep it, I'll probably just maintain it in my local tree.
Frank
- --
Frank Sorenson - KD7TZK
Systems Manager, Computer Science Department
Brigham Young University
frank@tuxrocks.com
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.6 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org
iD8DBQFCzBumaI0dwg4A47wRAmKKAJ90HJymEjSHwvpKq7pjQkXf9wz7sACfXl8F
BttVqvdhovFaGYEn9PibeC0=
=N90S
-----END PGP SIGNATURE-----
^ 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