* [PATCH 1/7] Additional git-rev-list unit tests to demonstrate problems that require fixes
From: Jon Seymour @ 2005-06-20 2:29 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour, paulus
1. --merge-order doesn't deal properly with a specified head that has no parent
* FAIL 11: head has no parent
2. --merge-order doesn't deal properly with arguments of the form
head ^head
* FAIL 30: head ^head --merge-order git-rev-list --merge-order
--show-breaks a3 ^a3
3. if one of the specified heads is reachable from the other, the
head gets printed twice and this causes problems for upcoming
versions of gitk. This is true for both --merge-order and non
--merge-order style of invocations.
* FAIL 24: one specified head reachable from another a4, c3, --merge-order
* FAIL 26: one specified head reachable from another a4, c3, no --merge-order
* FAIL 27: one specified head reachable from another c3, a4, no --merge-order
4. --merge-order aborts with commits that list the same parent twice...it should handle it more gracefully.
* no longer unit testable
5. broken interaction between --merge-order and --max-age
previously posted as:
"[PATCH 1/2] Test case that demonstrates problem with --merge-order, --max-age interaction"
* FAIL 23: --max-age=c3, --merge-order
Later patches in this patch set fix these problems.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
This patch series contains:
[PATCH 1/7] Additional git-rev-list unit tests to demonstrate problems that require fixes
[PATCH 2/7] Tweaked --merge-order --show-breaks output in case specified head has no parent
[PATCH 3/7] Fixes problem with --merge-order head ^head
[PATCH 4/7] Relaxes error checking in epoch.c to allow duplicate parents
[PATCH 5/7] Prevent git-rev-list --merge-order producing duplicates in the output
[PATCH 6/7] Prevent git-rev-list without --merge-order producing duplicates in output
[PATCH 7/7] Fix for --merge-order, --max-age interaction issue
It is a complete superset of this series:
[PATCH 2/2] Fix for --merge-order, --max-age interaction issue
[PATCH 1/2] Test case that demonstrates problem with --merge-order, --max-age interaction
Patches apply cleanly to Linus HEAD - 31b6d200d6c5ed019f62d88ef0926faeb0150aac.
Some unit tests fail until all patches have been applied and built at which point
they pass.
t/t6001-rev-list-merge-order.sh | 434 ++++++++++++++++++++++++++++++++++-----
1 files changed, 374 insertions(+), 60 deletions(-)
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
@@ -3,16 +3,124 @@
# Copyright (c) 2005 Jon Seymour
#
-test_description='Test rev-list --merge-order
-'
+test_description='Tests git-rev-list --merge-order functionality'
+
. ./test-lib.sh
-function do_commit
+#
+# 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()
{
- git-commit-tree "$@" </dev/null
+ "$@" 2>/dev/null
+}
+
+check_output()
+{
+ _name=$1
+ shift 1
+ if "$@" | 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"
}
-function check_adjacency
+# --- end of stuff to move ---
+
+# test-case specific test function
+check_adjacency()
{
read previous
echo "= $previous"
@@ -28,43 +136,94 @@ function check_adjacency
done
}
-function sed_script
+list_duplicates()
+{
+ "$@" | sort | uniq -d
+}
+
+grep_stderr()
{
- for c in root a0 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 l0 l1 l2 l3 l4 l5
- do
- echo -n "s/${!c}/$c/;"
- done
+ args=$1
+ shift 1
+ "$@" 2>&1 | grep "$args"
}
date >path0
git-update-cache --add path0
-tree=$(git-write-tree)
-root=$(do_commit $tree 2>/dev/null)
-export GIT_COMMITTER_NAME=foobar # to guarantee that the commit is different
-l0=$(do_commit $tree -p $root)
-l1=$(do_commit $tree -p $l0)
-l2=$(do_commit $tree -p $l1)
-a0=$(do_commit $tree -p $l2)
-a1=$(do_commit $tree -p $a0)
-export GIT_COMMITTER_NAME=foobar2 # to guarantee that the commit is different
-b1=$(do_commit $tree -p $a0)
-c1=$(do_commit $tree -p $b1)
-export GIT_COMMITTER_NAME=foobar3 # to guarantee that the commit is different
-b2=$(do_commit $tree -p $b1)
-b3=$(do_commit $tree -p $b2)
-c2=$(do_commit $tree -p $c1 -p $b2)
-c3=$(do_commit $tree -p $c2)
-a2=$(do_commit $tree -p $a1)
-a3=$(do_commit $tree -p $a2)
-b4=$(do_commit $tree -p $b3 -p $a3)
-a4=$(do_commit $tree -p $a3 -p $b4 -p $c3)
-l3=$(do_commit $tree -p $a4)
-l4=$(do_commit $tree -p $l3)
-l5=$(do_commit $tree -p $l4)
-echo $l5 > .git/HEAD
+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" as_author foobar@example.com 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
+on_committer_date "1971-08-16 00:00:19" save_tag m1 unique_commit m1 tree -p a4 -p c3
+on_committer_date "1971-08-16 00:00:20" save_tag m2 unique_commit m2 tree -p c3 -p a4
+#
+# note: as of 20/6, it isn't possible to create duplicate parents, so this
+# can't be tested.
+#
+#on_committer_date "1971-08-16 00:00:20" save_tag m3 unique_commit m3 tree -p c3 -p a4 -p c3
+hide_error save_tag e1 as_author e@example.com unique_commit e1 tree
+save_tag e2 as_author e@example.com unique_commit e2 tree -p e1
+save_tag f1 as_author f@example.com unique_commit f1 tree -p e1
+save_tag e3 as_author e@example.com unique_commit e3 tree -p e2
+save_tag f2 as_author f@example.com unique_commit f2 tree -p f1
+save_tag e4 as_author e@example.com unique_commit e4 tree -p e3 -p f2
+save_tag e5 as_author e@example.com unique_commit e5 tree -p e4
+save_tag f3 as_author f@example.com unique_commit f3 tree -p f2
+save_tag f4 as_author f@example.com unique_commit f4 tree -p f3
+save_tag e6 as_author e@example.com unique_commit e6 tree -p e5 -p f4
+save_tag f5 as_author f@example.com unique_commit f5 tree -p f4
+save_tag f6 as_author f@example.com unique_commit f6 tree -p f5 -p e6
+save_tag e7 as_author e@example.com unique_commit e7 tree -p e6
+save_tag e8 as_author e@example.com unique_commit e8 tree -p e7
+save_tag e9 as_author e@example.com unique_commit e9 tree -p e8
+save_tag f7 as_author f@example.com unique_commit f7 tree -p f6
+save_tag f8 as_author f@example.com unique_commit f8 tree -p f7
+save_tag f9 as_author f@example.com unique_commit f9 tree -p f8
+save_tag e10 as_author e@example.com unique_commit e1 tree -p e9 -p f8
+
+hide_error save_tag g0 unique_commit g0 tree
+save_tag g1 unique_commit g1 tree -p g0
+save_tag h1 unique_commit g2 tree -p g0
+save_tag g2 unique_commit g3 tree -p g1 -p h1
+save_tag h2 unique_commit g4 tree -p g2
+save_tag g3 unique_commit g5 tree -p g2
+save_tag g4 unique_commit g6 tree -p g3 -p h2
+
+tag l5 > .git/HEAD
+
+#
+# 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
-git-rev-list --merge-order --show-breaks HEAD | sed "$(sed_script)" > actual-merge-order
-cat > expected-merge-order <<EOF
+test_expect_success 'rev-list has correct number of entries' 'git-rev-list HEAD | wc -l | tr -s " "' <<EOF
+19
+EOF
+
+normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
+merge_order_adjacency_count=$(git-rev-list --merge-order HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
+test_expect_success '--merge-order produces as many or fewer discontinuities' '[ $merge_order_adjacency_count -le $normal_adjacency_count ]'
+test_output_expect_success 'simple merge order' 'git-rev-list --merge-order --show-breaks HEAD' <<EOF
= l5
| l4
| l3
@@ -86,15 +245,17 @@ cat > expected-merge-order <<EOF
= root
EOF
-git-rev-list HEAD | check_adjacency | sed "$(sed_script)" > actual-default-order
-normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
-merge_order_adjacency_count=$(git-rev-list --merge-order HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
-
-test_expect_success 'Testing that the rev-list has correct number of entries' '[ $(git-rev-list HEAD | wc -l) -eq 19 ]'
-test_expect_success 'Testing that --merge-order produces the correct result' 'diff expected-merge-order actual-merge-order'
-test_expect_success 'Testing that --merge-order produces as many or fewer discontinuities' '[ $merge_order_adjacency_count -le $normal_adjacency_count ]'
+test_output_expect_success 'two diamonds merge order (g6)' 'git-rev-list --merge-order --show-breaks g4' <<EOF
+= g4
+| h2
+^ g3
+= g2
+| h1
+^ g1
+= g0
+EOF
-cat > expected-merge-order-1 <<EOF
+test_output_expect_success 'multiple heads' 'git-rev-list --merge-order a3 b3 c3' <<EOF
c3
c2
c1
@@ -111,10 +272,7 @@ l0
root
EOF
-git-rev-list --merge-order $a3 $b3 $c3 | sed "$(sed_script)" > actual-merge-order-1
-test_expect_success 'Testing multiple heads' 'diff expected-merge-order-1 actual-merge-order-1'
-
-cat > expected-merge-order-2 <<EOF
+test_output_expect_success 'multiple heads, prune at a1' 'git-rev-list --merge-order a3 b3 c3 ^a1' <<EOF
c3
c2
c1
@@ -125,10 +283,7 @@ a3
a2
EOF
-git-rev-list --merge-order $a3 $b3 $c3 ^$a1 | sed "$(sed_script)" > actual-merge-order-2
-test_expect_success 'Testing stop' 'diff expected-merge-order-2 actual-merge-order-2'
-
-cat > expected-merge-order-3 <<EOF
+test_output_expect_success 'multiple heads, prune at l1' 'git-rev-list --merge-order a3 b3 c3 ^l1' <<EOF
c3
c2
c1
@@ -142,10 +297,26 @@ a0
l2
EOF
-git-rev-list --merge-order $a3 $b3 $c3 ^$l1 | sed "$(sed_script)" > actual-merge-order-3
-test_expect_success 'Testing stop in linear epoch' 'diff expected-merge-order-3 actual-merge-order-3'
+test_output_expect_success 'cross-epoch, head at l5, prune at l1' 'git-rev-list --merge-order l5 ^l1' <<EOF
+l5
+l4
+l3
+a4
+c3
+c2
+c1
+b4
+b3
+b2
+b1
+a3
+a2
+a1
+a0
+l2
+EOF
-cat > expected-merge-order-4 <<EOF
+test_output_expect_success 'duplicated head arguments' 'git-rev-list --merge-order l5 l5 ^l1' <<EOF
l5
l4
l3
@@ -164,12 +335,155 @@ a0
l2
EOF
-git-rev-list --merge-order $l5 ^$l1 | sed "$(sed_script)" > actual-merge-order-4
-test_expect_success 'Testing start in linear epoch, stop after non-linear epoch' 'diff expected-merge-order-4 actual-merge-order-4'
+test_output_expect_success 'prune near merge' 'git-rev-list --merge-order a4 ^c3' <<EOF
+a4
+b4
+b3
+a3
+a2
+a1
+EOF
+
+test_output_expect_success "head has no parent" 'git-rev-list --merge-order --show-breaks root' <<EOF
+= root
+EOF
-git-rev-list --merge-order $l5 $l5 ^$l1 2>/dev/null | sed "$(sed_script)" > actual-merge-order-5
-test_expect_success 'Testing duplicated start arguments' 'diff expected-merge-order-4 actual-merge-order-5'
+test_output_expect_success "two nodes - one head, one base" 'git-rev-list --merge-order --show-breaks l0' <<EOF
+= l0
+= root
+EOF
-test_expect_success 'Testing exclusion near merge' 'git-rev-list --merge-order $a4 ^$c3 2>/dev/null'
+test_output_expect_success "three nodes one head, one internal, one base" 'git-rev-list --merge-order --show-breaks l1' <<EOF
+= l1
+| l0
+= root
+EOF
+
+test_output_expect_success "linear prune l2 ^root" 'git-rev-list --merge-order --show-breaks l2 ^root' <<EOF
+= l2
+| l1
+| l0
+EOF
+
+test_output_expect_success "linear prune l2 ^l0" 'git-rev-list --merge-order --show-breaks l2 ^l0' <<EOF
+= l2
+| l1
+EOF
+
+test_output_expect_success "linear prune l2 ^l1" 'git-rev-list --merge-order --show-breaks l2 ^l1' <<EOF
+= l2
+EOF
+
+test_output_expect_success "linear prune l5 ^a4" 'git-rev-list --merge-order --show-breaks l5 ^a4' <<EOF
+= l5
+| l4
+| l3
+EOF
+
+test_output_expect_success "linear prune l5 ^l3" 'git-rev-list --merge-order --show-breaks l5 ^l3' <<EOF
+= l5
+| l4
+EOF
+
+test_output_expect_success "linear prune l5 ^l4" 'git-rev-list --merge-order --show-breaks l5 ^l4' <<EOF
+= l5
+EOF
+
+test_output_expect_success "max-count 10 - merge order" 'git-rev-list --merge-order --show-breaks --max-count=10 l5' <<EOF
+= l5
+| l4
+| l3
+= a4
+| c3
+| c2
+| c1
+^ b4
+| b3
+| b2
+EOF
+
+test_output_expect_success "max-count 10 - non merge order" 'git-rev-list --max-count=10 l5 | sort' <<EOF
+a4
+b2
+b3
+b4
+c1
+c2
+c3
+l3
+l4
+l5
+EOF
+
+test_output_expect_success '--max-age=c3, no --merge-order' "git-rev-list --max-age=$(commit_date c3) l5" <<EOF
+l5
+l4
+l3
+a4
+b4
+a3
+a2
+c3
+EOF
+
+test_output_expect_success '--max-age=c3, --merge-order' "git-rev-list --merge-order --max-age=$(commit_date c3) l5" <<EOF
+l5
+l4
+l3
+a4
+c3
+b4
+a3
+a2
+EOF
+
+test_output_expect_success 'one specified head reachable from another a4, c3, --merge-order' "list_duplicates git-rev-list --merge-order a4 c3" <<EOF
+EOF
+
+test_output_expect_success 'one specified head reachable from another c3, a4, --merge-order' "list_duplicates git-rev-list --merge-order c3 a4" <<EOF
+EOF
+
+test_output_expect_success 'one specified head reachable from another a4, c3, no --merge-order' "list_duplicates git-rev-list a4 c3" <<EOF
+EOF
+
+test_output_expect_success 'one specified head reachable from another c3, a4, no --merge-order' "list_duplicates git-rev-list c3 a4" <<EOF
+EOF
+
+test_output_expect_success 'graph with c3 and a4 parents of head' "list_duplicates git-rev-list m1" <<EOF
+EOF
+
+test_output_expect_success 'graph with a4 and c3 parents of head' "list_duplicates git-rev-list m2" <<EOF
+EOF
+
+test_expect_success "head ^head --merge-order" 'git-rev-list --merge-order --show-breaks a3 ^a3' <<EOF
+EOF
+
+#
+# can't test this now - duplicate parents can't be created
+#
+#test_output_expect_success 'duplicate parents' 'git-rev-list --parents --merge-order --show-breaks m3' <<EOF
+#= m3 c3 a4 c3
+#| a4 c3 b4 a3
+#| b4 a3 b3
+#| b3 b2
+#^ a3 a2
+#| a2 a1
+#| a1 a0
+#^ c3 c2
+#| c2 b2 c1
+#| b2 b1
+#^ c1 b1
+#| b1 a0
+#= a0 l2
+#| l2 l1
+#| l1 l0
+#| l0 root
+#= root
+#EOF
+
+test_expect_success "head ^head no --merge-order" 'git-rev-list a3 ^a3' <<EOF
+EOF
+#
+#
test_done
------------
^ permalink raw reply
* Re: 'git commit' duplicates parents?
From: Jeff Garzik @ 2005-06-20 2:28 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506191921270.2268@ppc970.osdl.org>
Linus Torvalds wrote:
> As to why you had a .git/MERGE_HEAD in your tree, it's probably because
> your merge scripts haven't kept up with mine.
Nope, I use vanilla latest ones. FWIW my setup is 100% vanilla git plus
two small scripts, 'git-switch-tree' and 'git-new-branch', which switch
around .git/HEAD.
Doing some experimenting, it seems that git-pull-script does not remove
MERGE_HEAD and ORIG_HEAD after its done.
This is reproducible by updating vanilla linux-2.6.git using vanilla
git-pull-script. Just a standard update-to-latest-kernel, with no
conflicts/merges/etc.
Jeff
^ permalink raw reply
* Re: 'git commit' duplicates parents?
From: Linus Torvalds @ 2005-06-20 2:24 UTC (permalink / raw)
To: Jeff Garzik; +Cc: Git Mailing List
In-Reply-To: <42B59CF7.3080509@pobox.com>
On Sun, 19 Jun 2005, Jeff Garzik wrote:
>
> I just checked in a change with 'git commit' (no arguments). Two
> strange things occurred:
>
> 1) git-whatchanged does not list the change at all. However,
> a) I verified that my change is indeed top-of-tree
> b) git-changes-script (attached) does show the change
Your commit is a merge. A corrupted one.
> 2) git-changes-script shows the parents in a readable fashion, and it
> shows two duplicate parent entries. In contrast, other changes do not
> have two parents:
>
> my change:
> > commit 4864989199fa62c7044be2258550ddc561411ab6
> ^^^ top of tree aka .git/HEAD
> > tree b40996c7a0a5446875aa3664045af7e377451bf6
> > parent 7df551254add79a445d2e47e8f849cef8fee6e38
> > parent 7df551254add79a445d2e47e8f849cef8fee6e38
Notice: two times the same head.
You had a MERGE_HEAD in your tree, and "git commit" warned you about it in
big bold letters and told you what to do, but you ignored it.
"git commit" said:
echo "#"
echo "# It looks like your may be committing a MERGE."
echo "# If this is not correct, please remove the file"
echo "# $GIT_DIR/MERGE_HEAD"
echo "# and try again"
echo "#"
and if you had just done as it asked you, you'd have been ok.
As to why you had a .git/MERGE_HEAD in your tree, it's probably because
your merge scripts haven't kept up with mine.
Linus
^ permalink raw reply
* git droppings
From: Jeff Garzik @ 2005-06-20 1:51 UTC (permalink / raw)
To: Git Mailing List
'git commit' fails to clean up the following files
.cmitmsg
.editmsg
after it completes successfully.
Jeff
^ permalink raw reply
* Re: cloning a complete repository with cogito
From: Petr Baudis @ 2005-06-19 22:39 UTC (permalink / raw)
To: git
In-Reply-To: <20050619154249.GB5992MdfPADPa@garage.linux.student.kuleuven.ac.be>
Dear diary, on Sun, Jun 19, 2005 at 05:42:50PM CEST, I got a letter
where Sven Verdoolaege <skimo@kotnet.org> told me that...
> How can I clone a complete repository with cogito ?
>
> cg-clone will only pull in everything from the master branch.
> Then it pulls in the objects pointed to by tags, which
> may live on other brachnes, resulting in a repository
> that is not git-fsck-clean.
>
> I'd like to be able to clone the whole thing or even
> particular branches, different from master.
>
> Think of a repository converted from cvs.
Well, pulling a specific branch can be done by appending #branchname to
the URL. If you use rsync:// URL, it will pull everything, too. Pulling
everything referenced by refs/ might be a nice thing, yes. ;-)
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
<Espy> be careful, some twit might quote you out of context..
^ permalink raw reply
* Re: qgit-0.6
From: Radoslaw Szkodzinski @ 2005-06-19 20:15 UTC (permalink / raw)
To: Marco Costalba; +Cc: mingo, git
In-Reply-To: <20050619195812.66959.qmail@web26309.mail.ukl.yahoo.com>
[-- Attachment #1: Type: text/plain, Size: 851 bytes --]
On Sun, 19 Jun 2005 12:58:12 -0700 (PDT)
Marco Costalba <mcostalba@yahoo.it> wrote:
>
> >* Ingo Molnar <mingo@elte.hu> wrote:
> >
> >>works fine here and is nice and fast, but there are a few minor visual
> >>glitches:
> >
> >
> >one more thing: for the annotated output it would be nicer to have
> >fixed-width fonts to display code. For commit messages the current
> >output is fine, but code is much more readable in fixed-width output.
> >
> > Ingo
> >
>
> Next release will use Courier 10 for all annotated output, I know from my tree it works.
> The only concern is about box with no courier font installed, I don't know if this can be
> a problem.
>
You'd better use system alias Monospace. I have that set to a
nice-looking constant width font. And it's guaranteed to at least
resolve to Fixed.
AstralStorm
[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: qgit-0.6
From: Marco Costalba @ 2005-06-19 20:05 UTC (permalink / raw)
To: Ingo Molnar; +Cc: berkus, git
Ingo Molnar ha scritto:
>on FC4 the build is quite noisy. Not a big issue because it otherwise
>builds and works fine:
>
>scons -Q
>/usr/lib/qt-3.3/bin/uic -o src/diffbase.h src/diffbase.ui
>/usr/lib/qt-3.3/bin/uic -impl diffbase.h -o src/uic_diffbase.cc src/diffbase.ui
>/usr/lib/qt-3.3/bin/moc -o src/moc_diffbase.cc src/diffbase.h
>QSettings: error creating /.qt
>QSettings: error creating /.qt
>QSettings: error creating /.qt
I have the same output from day one on my box too, but I am not so familiar with scons to be able
to fix it.
Peraphs someone (Stanislav?) can provide a fix?
Marco
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
^ permalink raw reply
* Re: qgit-0.6
From: Marco Costalba @ 2005-06-19 19:58 UTC (permalink / raw)
To: Ingo Molnar; +Cc: git
>* Ingo Molnar <mingo@elte.hu> wrote:
>
>>works fine here and is nice and fast, but there are a few minor visual
>>glitches:
>
>
>one more thing: for the annotated output it would be nicer to have
>fixed-width fonts to display code. For commit messages the current
>output is fine, but code is much more readable in fixed-width output.
>
> Ingo
>
Next release will use Courier 10 for all annotated output, I know from my tree it works.
The only concern is about box with no courier font installed, I don't know if this can be
a problem.
Marco
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Jon Seymour @ 2005-06-19 19:55 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506190951330.2268@ppc970.osdl.org>
On 6/20/05, Linus Torvalds <torvalds@osdl.org> wrote:
>
>
> On Mon, 20 Jun 2005, Jon Seymour wrote:
> >
> > Would I be correct in stating that an intuitive reason why your
> > algorithm is better than selecting the linear middle is the following:
> >
> > If you concentrate on testing merges, rather than non-merges, the
> > chances are you are going to eliminate N-times as many possible good
> > commits as if you pick a random commit, where N is the average fan-out
> > of the commit graph.
>
> No. You really shouldn't concentrate on merges either.
>
> The thing is, you do _not_ want to test as many commits as possible, or as
> few commits as possible.
>
> This is _not_ a "try to eliminate as many commits as possible" problem.
> It's really one of trying to eliminate _half_ the commits. Not more, not
> less.
>
Yep, ok, so the node you are looking for is one that can reach as
close to half of the rest of the graph as possible - that's what you
mean by half-way reachability. If the graph was N nodes deep (no
fan-out) that would be the literal middle. If it was N nodes wide
(e.g. fanout N), there is no good node and you basically have to test
everything since one test doesn't imply anything about the other N-1
nodes.
A typical commit graph is worse than O(log2 N) by a factor that is
determined by some measure of the parallel branching in the graph.
>
> The reason my algorithm is so horrid (O(3)) is that you can't even cache
> the dang thing sanely: you can't optimize if by remembering how many
> interesting commits are reachable from one commit, and then doing "this
> commit reaches commits X and Y, so I can reach X.count + Y.count commits
> from it". That's just not true, because often (basically always) there is
> lots of common commits in X.count and Y.count..
I presume you mean O(N^3)?
Will you accept a patch that can reduce the worst case cost to some
lower order? I have a hunch (conceivably wrong, of course) that it can
be done in O(N).
> > This compares with my naive literal middle algorithm (measurements
> > only for the first 619 commits):
> >
> > average(21), median(16), stdev(10.6), max(49), min(8).
>
> Yes. I really don't believe you can do better than 12, unless you start
> depending on knowledge of the distribution of bugs.
>
Agreed.
jon.
^ permalink raw reply
* Re: qgit-0.6
From: Marco Costalba @ 2005-06-19 19:54 UTC (permalink / raw)
To: Ingo Molnar; +Cc: git
Ingo Molnar wrote:
thanks for your feedback
>
>works fine here and is nice and fast, but there are a few minor visual
>glitches:
>
>- annotated file contents are not properly aligned over each other. E.g.
> check commit 7875b50d1a9928e683299b283bfe94778b6c344e in the current
> git repository, and select read-tree.c and view it annotated - the
> lines start right after the author field ends, not in any aligned way.
>
Yes, it depends on variable spaced font, If you note the number of characters of the header of
each line is always the same and is calculated for each file (the gray color part has always a
fixed number of chars). I have already switched to a fixed font (courier) in my tree,
plus others little things like truncation if exceeds a maximum lenght with
first name collpasing (Marco Costalba -> M. Costalba).
>- the tree visualization is hard to follow - gitk's output is much
> nicer. As an example of nice rendering check out the octopus merge
> around commit 211232bae64bcc60bbf5d1b5e5b2344c22ed767e. One glance at
> the gitk output shows what happened - qgit's output is in essence
> unreadable.
>
You are definitely right! The problem is graph is not drawed! I precalculate at startup all
the diffrents pixmaps and put in a vector, drawing a graph is just correct indexing
the vector for each lane and do some bitblt. This is because QT has good pixmaps handling in
QListView ( the main log list) but not line drawings capapility and because this way is very fast.
But in any case I definitely have to find something better. Suggestions are welcomed :-).
>and a few requests for enhancements if you dont mind:
>
more then welcomed.
> - in annotated mode, it would be nice to select a particular line
> and then double-click would jump to the commit that added that line.
> This would nicely round up annotation support.
>
Ok, I'll add this. By the way, now you can select the corresponding commit in the
history list above file content (it's the one with the same number) and the
main view will update.
I can make the selection: 'line content number -> line history number' automatic and that
should be enough.
> - plaintext search capability in every window. E.g. in the annotated
> file window i often would like to search for some code, or to jump to
> a given line.
Ok. I'll add this.
Marco
__________________________________
Discover Yahoo!
Stay in touch with email, IM, photo sharing and more. Check it out!
http://discover.yahoo.com/stayintouch.html
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Linus Torvalds @ 2005-06-19 19:01 UTC (permalink / raw)
To: Ingo Molnar; +Cc: jon, Git Mailing List
In-Reply-To: <20050619173634.GA25768@elte.hu>
On Sun, 19 Jun 2005, Ingo Molnar wrote:
>
> another assumption is that the number of testsystems is a power of two
> minus 1. With 2 or more testsystems (and automated testing) you could
> dissect the search space into 3, 5 or more roughly equal pieces in the
> first step (2, 4, 8 ... sections are already supported via the bisect
> flag).
Yeah. I don't think it matters much, though, since the "more testsystems"
thing will only really end up helping by a fairly small amount, at the
cost of much more complexity. The difference between "log2(N)" and
"log5(N)" isn't _that_ big, and it's even smaller when you just do the
power-of-two thing and use 4 systems instead of 5 (ie now it's "log4(N)"
vs "log5(N)").
Also, to use multiple test-systems efficiently, they all end up having to
be synchronized (ie the next iteration needs to get the result from all
the test-systems from the previous one), so it's quite a lot of bother for
not a lot of improvement. It also assumes you can partition the problem
space well into <n> roughly equal pieces - which may or may not be true.
More importantly, quite often the nasty problems are the ones that only
happen for one machine. Trying to make it easy for non-developers to test
different kernels is what this is about: I started thinking about this
when we had the "x86-64 SIGSEGV's for me" issue, where bisection was
fairly easy in the -mm series due to a nice linear series, but even then
you had to have tools to apply/unapply different patches etc.
Linus
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Ingo Molnar @ 2005-06-19 17:36 UTC (permalink / raw)
To: Linus Torvalds; +Cc: jon, Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506190951330.2268@ppc970.osdl.org>
* Linus Torvalds <torvalds@osdl.org> wrote:
> NOTE NOTE NOTE! The above is all based on random distribution of bugs,
> where all commits count equally, which is obviously not even true. You
> coudl try to do a "weighted bisection", where you weigh commits
> differently: you might say, for example, that if the author field
> matches the string "torvalds", then the likelihood of a bug is
> obviously miniscule, so such a commit only counts as 0.1.
another assumption is that the number of testsystems is a power of two
minus 1. With 2 or more testsystems (and automated testing) you could
dissect the search space into 3, 5 or more roughly equal pieces in the
first step (2, 4, 8 ... sections are already supported via the bisect
flag). To decrease the time needed to find a bug it makes sense to
increase the number of testsystems, especially if it takes minutes to
boot - or if it takes minutes (or hours) to reproduce a bug. If each box
runs a separate kernel then statistically, if one of them triggers the
bug, only half of them have to be rebooted with new kernels, the others
would still be kept running in a "commit space of interest".
But i guess it's not a big degradation to just round the test method to
the nearest power-of-2 bisection method.
Ingo
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Linus Torvalds @ 2005-06-19 17:20 UTC (permalink / raw)
To: jon; +Cc: Git Mailing List
In-Reply-To: <2cfc40320506190741409f3a5@mail.gmail.com>
On Mon, 20 Jun 2005, Jon Seymour wrote:
>
> Would I be correct in stating that an intuitive reason why your
> algorithm is better than selecting the linear middle is the following:
>
> If you concentrate on testing merges, rather than non-merges, the
> chances are you are going to eliminate N-times as many possible good
> commits as if you pick a random commit, where N is the average fan-out
> of the commit graph.
No. You really shouldn't concentrate on merges either.
The thing is, you do _not_ want to test as many commits as possible, or as
few commits as possible.
This is _not_ a "try to eliminate as many commits as possible" problem.
It's really one of trying to eliminate _half_ the commits. Not more, not
less.
So to some degree you want to _avoid_ merges, because they pick up a lot
of commits, and that might take you over the limit. But at the same time
you need to be very aware of merges, since if you ignore them, you'll pick
up too _few_ commits.
So in a very real sense, whether you pick a merge or not doesn't depend on
whether that one entry is a merge itself - it really depends on the whole
flow. You can't do any local measurements.
The reason my algorithm is so horrid (O(3)) is that you can't even cache
the dang thing sanely: you can't optimize if by remembering how many
interesting commits are reachable from one commit, and then doing "this
commit reaches commits X and Y, so I can reach X.count + Y.count commits
from it". That's just not true, because often (basically always) there is
lots of common commits in X.count and Y.count..
So that's why I do that strange full reachability thing for _each_ commit,
and then clear the reachability flags and start with the next commit. It's
horrid, but I can't see a sane way to avoid it (I could do the clearing
less often by introducing the notion of "generations" in the reachability,
but I didn't want to add a new counter to the data structures - and it
wouldn't really change anything fundamental).
In your measurements:
> FWIW: my measurements of your algorithm thus far show that if the bug
> exists in the first 1070 of the 2119 commits between HEAD and
> v2.6.12-rc2 it consistently (very consistently) takes between 11 and
> 13 iterations of git-bug-blatt-script to find the bug.
>
> Specifically: average (12.10), median (12), stdev(0.412), max(13),
> min(11).
Yes. Consistency is the name of the game. A low standard deviation is what
it's all about, because that's how binary searches work. The point about
binary searching for a bug is that you're not really looking for "the one"
commit, you're really looking for the _range_ of two adjacent commits: it
doesn't even help if you happen to pick the buggy commit on the first try,
because the only thing that matters is when you have zeroed in on the
"buggy and previous" one.
In other words, in a traditional search, when you pick an entry, you know
that you got it right: you might be lucky and pick it first, and you'll be
happy. But in the "search for a bug" case, you always have to go the
_full_ "log2()" thing, because you will always have to not just pick the
right entry, you will also have had to "bisect to zero" so that you know
that the entry before it was not buggy.
This is because the "is it buggy" is not a unique thing, it's really just
a partial ordering in the set (if you're really unlucky, you might have
two bugs that interact, and you'll not actually find "the commit" at all,
but the one you do end up zeroing in on should at least be _one_ border
condition for the bug, so it should help you somewhat regardless).
So you basically cannot avoid doing "ceil(log2(N))" tests, and with 2119
commits, you should pretty much _always_ get 12, and basically a standard
deviation of zero.
The reason you don't get that is that _occasionally_ you can't get close
enough to "half-way", and depending on whether the bug was in the smaller
set or bigger set, you might be lucky or unlucky. The problem here is that
by definition you'll be unlucky more of the time: the bigger set (the
unlucky case) is _bigger_, so it's more likely to have the bug, so what
you should see statistically is that you can't actually do _better_ than
ceil(log2(N)).
("cannot do better" obviously is true only in the statistical sense. You
can always be lucky in any individual test, and if you are intelligent and
choose the commits to test based on the symptoms of the bug you can always
do better, of course).
NOTE NOTE NOTE! The above is all based on random distribution of bugs,
where all commits count equally, which is obviously not even true. You
coudl try to do a "weighted bisection", where you weigh commits
differently: you might say, for example, that if the author field matches
the string "torvalds", then the likelihood of a bug is obviously
miniscule, so such a commit only counts as 0.1.
Or you could argue that a pure merge seldom introduces a bug (which is
probably not true, but hey, this is theory), and you could decide that
when you "count commits", then normal commits count as two, and merges
count as one, and the bisection is trying to get equal "weights" on both
sides, not "equal number of commits".
However, that's where "consistency" has another advantage: maybe it's
possible to get better results on average by taking statistical bug
distribution behaviour into account (like "bugs are likely new - try to
weigh the bisection 60% reachable / 40% unreachable instead of 50-50"),
but that means that then occasionally you do worse, and from a
psychological angle I think that's unacceptable. I think most bug hunters
would much prefer to know that "I need to reboot 7 times and I'll get it",
over "I probably need to reboot only 5 times, but it might be 10 if I'm
unlucky".
> This compares with my naive literal middle algorithm (measurements
> only for the first 619 commits):
>
> average(21), median(16), stdev(10.6), max(49), min(8).
Yes. I really don't believe you can do better than 12, unless you start
depending on knowledge of the distribution of bugs.
Linus
^ permalink raw reply
* Re: 'git commit' duplicates parents?
From: Jeff Garzik @ 2005-06-19 16:32 UTC (permalink / raw)
To: Git Mailing List
In-Reply-To: <42B59CF7.3080509@pobox.com>
Jeff Garzik wrote:
> I just checked in a change with 'git commit' (no arguments). Two
> strange things occurred:
FWIW you can see the problem yourself at
'fc4-fix' branch of
rsync://rsync.kernel.org/pub/scm/linux/kernel/git/jgarzik/misc-2.6.git
(just one change checked in, the change referenced in the previous email)
^ permalink raw reply
* 'git commit' duplicates parents?
From: Jeff Garzik @ 2005-06-19 16:27 UTC (permalink / raw)
To: Git Mailing List
[-- Attachment #1: Type: text/plain, Size: 1447 bytes --]
I just checked in a change with 'git commit' (no arguments). Two
strange things occurred:
1) git-whatchanged does not list the change at all. However,
a) I verified that my change is indeed top-of-tree
b) git-changes-script (attached) does show the change
2) git-changes-script shows the parents in a readable fashion, and it
shows two duplicate parent entries. In contrast, other changes do not
have two parents:
my change:
> commit 4864989199fa62c7044be2258550ddc561411ab6
^^^ top of tree aka .git/HEAD
> tree b40996c7a0a5446875aa3664045af7e377451bf6
> parent 7df551254add79a445d2e47e8f849cef8fee6e38
> parent 7df551254add79a445d2e47e8f849cef8fee6e38
> author Jeff Garzik <jgarzik@pretzel.yyz.us> Sun, 19 Jun 2005 20:06:28 -0400
> committer Jeff Garzik <jgarzik@pobox.com> Sun, 19 Jun 2005 20:06:28 -0400
>
> fc4/fc: fix warnings/errors caused by recent changes
a random change not committed by 'git commit':
> commit 7df551254add79a445d2e47e8f849cef8fee6e38
> tree 468a43ac3f94b9bf8618b102a7d609e29d3900f5
> parent f7d7fc0322c1770fe7ee836ca2732c2f88e2e1a4
> author David S. Miller <davem@davemloft.net> Sun, 19 Jun 2005 13:01:10 -0700
> committer David S. Miller <davem@davemloft.net> Sun, 19 Jun 2005 13:01:10 -0700
>
> [TCP]: Fix sysctl_tcp_low_latency
>
> When enabled, this should disable UCOPY prequeue'ing altogether,
> but it does not due to a missing test.
>
> Signed-off-by: David S. Miller <davem@davemloft.net>
[-- Attachment #2: git-changes-script --]
[-- Type: text/plain, Size: 2373 bytes --]
#!/bin/bash
#
# Make a log of changes in a GIT branch.
#
# This script was originally written by (c) Ross Vandegrift.
# Adapted to his scripts set by (c) Petr Baudis, 2005.
# Major optimizations by (c) Phillip Lougher.
# Rendered trivial by Linus Torvalds.
# Added -L|-R option by James Bottomley
#
# options:
# script [-L <dir> | -R <dir> |-r <from_sha1> [ -r <to_sha1] ] [<sha1>]
#
# With no options shows all the revisions from HEAD to the root
# -L shows all the changes in the local tree compared to the tree at <dir>
# -R shows all the changes in the remote tree at <dir> compared to the local
# -r shows all the changes in one commit or between two
tmpfile=/tmp/git_changes.$$
r1=
r2=
showcommit() {
commit="$1"
echo commit ${commit%:*};
git-cat-file commit $commit | \
while read key rest; do
case "$key" in
"author"|"committer")
date=(${rest#*> })
sec=${date[0]}; tz=${date[1]}
dtz=${tz/+/+ }; dtz=${dtz/-/- }
pdate="$(date -Rud "1970-01-01 UTC + $sec sec $dtz" 2>/dev/null)"
if [ "$pdate" ]; then
echo $key $rest | sed "s/>.*/> ${pdate/+0000/$tz}/"
else
echo $key $rest
fi
;;
"")
echo; cat
;;
*)
echo $key $rest
;;
esac
done
}
while true; do
case "$1" in
-R) shift;
diffsearch=+
remote="$1"
shift;;
-L) shift;
diffsearch=-
remote="$1"
shift;;
-r) shift;
if [ -z "$r1" ]; then
r1="$1"
else
r2="$1"
fi
shift;;
*) base="$1"
break;;
esac
done
if [ -n "$r1" ]; then
if [ -z "$r2" ]; then
showcommit $r1
exit 0
fi
diffsearch=+
remote=`pwd`;
tobase="$r2";
base="$r1"
fi
if [ -z "$base" ]; then
base=$(cat .git/HEAD) || exit 1
fi
git-rev-tree $base | sort -rn > ${tmpfile}.base
if [ -n "$remote" ]; then
[ -d $remote/.git ] || exit 1
if [ -z "$tobase" ]; then
tobase=$(cat $remote/.git/HEAD) || exit 1
fi
pushd $remote > /dev/null
git-rev-tree $tobase | sort -rn > ${tmpfile}.remote
diff -u ${tmpfile}.base ${tmpfile}.remote | grep "^${diffsearch}[^${diffsearch}]" | cut -c 1- > ${tmpfile}.diff
rm -f ${tmpfile}.base ${tmpfile}.remote
mv ${tmpfile}.diff ${tmpfile}.base
if [ $diffsearch = "-" ]; then
popd > /dev/null
fi
fi
[ -s "${tmpfile}.base" ] || exit 0
cat ${tmpfile}.base | while read time commit parents; do
showcommit $commit
echo -e "\n--------------------------"
done
rm -f ${tmpfile}.base
^ permalink raw reply
* cloning a complete repository with cogito
From: Sven Verdoolaege @ 2005-06-19 15:42 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
How can I clone a complete repository with cogito ?
cg-clone will only pull in everything from the master branch.
Then it pulls in the objects pointed to by tags, which
may live on other brachnes, resulting in a repository
that is not git-fsck-clean.
I'd like to be able to clone the whole thing or even
particular branches, different from master.
Think of a repository converted from cvs.
skimo
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Jon Seymour @ 2005-06-19 14:41 UTC (permalink / raw)
To: Git Mailing List, Linus Torvalds
In-Reply-To: <2cfc403205061903155a6090db@mail.gmail.com>
Linus,
Would I be correct in stating that an intuitive reason why your
algorithm is better than selecting the linear middle is the following:
If you concentrate on testing merges, rather than non-merges, the
chances are you are going to eliminate N-times as many possible good
commits as if you pick a random commit, where N is the average fan-out
of the commit graph.
With the linear middle algorithm, it doesn't really matter if you pick
a child of a merge - that is almost as good as picking the merge
itself. But if you happen to pick a parent of merge, then if it is
good and the parent is also good, you have wasted the opportunity to
clean up the peer branches of the parent you chose.
So the heuristic should be:
- focus on branches until there are no branches left, then keep
bisecting the list that remains.
Building on this insight, though, I'd like to point out that if you
want to eliminate things on a large scale, the things to focus on
first are epoch boundaries. Epoch boundaries are defined in such a way
that if an epoch boundary is good then everything reachable from an
epoch boundary is also good [ assuming exactly one fault ].
If you happen to choose a child of an epoch boundary, that's ok on
one-level, but on another level it's not ok. In particular, you
haven't eliminated everything beyond the epoch boundary so the open
list will be longer than it strictly needs to be.
So, I propose a modification to my "linear middle" bisection algorithm
as follows:
If there is more than one epoch boundary in the interesting graph,
choose the literal middle epoch boundary, otherwise, if there is more
than one merge in the interesting graph, chose the literal middle
merge, otherwise if there are no merges in the interesting graph,
choose the literal middle of the remaining list.
I am going to build a version of my linear middle code that
demonstrates this algorithm and then test it against the Linux 2.6
kernel.
FWIW: my measurements of your algorithm thus far show that if the bug
exists in the first 1070 of the 2119 commits between HEAD and
v2.6.12-rc2 it consistently (very consistently) takes between 11 and
13 iterations of git-bug-blatt-script to find the bug.
Specifically: average (12.10), median (12), stdev(0.412), max(13), min(11).
This compares with my naive literal middle algorithm (measurements
only for the first 619 commits):
average(21), median(16), stdev(10.6), max(49), min(8).
The number of commits is 2118, the number with a fanout > 1 is 173.
The average fanout of those with fanout is 2. My average is currently
2 times worse than yours and my worst case is 4-5 times worse than
yours.
So, you will be pleased to know that your intuition about the
correctness of your own algorithm has been objectively verified.
My intuition at this point is that my revised algorithm won't
significantly differ from your algorithm. I am thinking it will
require ~ 3 epoch boundary tests to identify the relevant epoch, 5
merge tests to identify the relevant segment and 4 bisections of a
linear segment to identify the correct merge which ends up being 12
iterations of the bug-blatt algorithm which really is no different to
yours. I suspect my algorithm might be better for really, really, big
repositories, with long histories, but I judge that the chance an
interesting bug will be deep in the long history is somewhat remote.
Both algorithms will benefit, however, if the intuition that most bugs
are recent is correct. git-bug-blatt-script could be modified to test
the first epoch boundary before recursively bisecting things. This
will make the typical bug search ~ 9 iterations long (since the
average epoch appears to be less than 512 commits and more than 256
commits big).
jon.
^ permalink raw reply
* Re: qgit-0.6
From: Ingo Molnar @ 2005-06-19 13:05 UTC (permalink / raw)
To: Marco Costalba; +Cc: git, berkus
In-Reply-To: <20050619130035.GA15355@elte.hu>
on FC4 the build is quite noisy. Not a big issue because it otherwise
builds and works fine:
scons -Q
/usr/lib/qt-3.3/bin/uic -o src/diffbase.h src/diffbase.ui
/usr/lib/qt-3.3/bin/uic -impl diffbase.h -o src/uic_diffbase.cc src/diffbase.ui
/usr/lib/qt-3.3/bin/moc -o src/moc_diffbase.cc src/diffbase.h
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/uic_diffbase.o src/uic_diffbase.cc
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/moc_diffbase.o src/moc_diffbase.cc
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/diffimpl.o src/diffimpl.cpp
/usr/lib/qt-3.3/bin/uic -o src/filebase.h src/filebase.ui
/usr/lib/qt-3.3/bin/uic -impl filebase.h -o src/uic_filebase.cc src/filebase.ui
/usr/lib/qt-3.3/bin/moc -o src/moc_filebase.cc src/filebase.h
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/uic_filebase.o src/uic_filebase.cc
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/moc_filebase.o src/moc_filebase.cc
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/fileimpl.o src/fileimpl.cpp
/usr/lib/qt-3.3/bin/uic -o src/mainbase.h src/mainbase.ui
/usr/lib/qt-3.3/bin/uic -impl mainbase.h -o src/uic_mainbase.cc src/mainbase.ui
/usr/lib/qt-3.3/bin/moc -o src/moc_mainbase.cc src/mainbase.h
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
QSettings: error creating /.qt
QSettings::sync: filename is null/empty
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/git.o src/git.cpp
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/uic_mainbase.o src/uic_mainbase.cc
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/moc_mainbase.o src/moc_mainbase.cc
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/mainimpl.o src/mainimpl.cpp
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/qgit.o src/qgit.cpp
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/thread.o src/thread.cpp
/usr/lib/qt-3.3/bin/moc -o src/moc_diffimpl.cc src/diffimpl.h
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/moc_diffimpl.o src/moc_diffimpl.cc
/usr/lib/qt-3.3/bin/moc -o src/moc_fileimpl.cc src/fileimpl.h
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/moc_fileimpl.o src/moc_fileimpl.cc
/usr/lib/qt-3.3/bin/moc -o src/moc_git.cc src/git.h
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/moc_git.o src/moc_git.cc
/usr/lib/qt-3.3/bin/moc -o src/moc_mainimpl.cc src/mainimpl.h
g++ -DQT_THREAD_SUPPORT -D_REENTRANT -I/usr/lib/qt-3.3/include -c -o src/moc_mainimpl.o src/moc_mainimpl.cc
g++ -o bin/qgit src/uic_diffbase.o src/moc_diffbase.o src/diffimpl.o src/uic_filebase.o src/moc_filebase.o src/fileimpl.o src/git.o src/uic_mainbase.o src/moc_mainbase.o src/mainimpl.o src/qgit.o src/thread.o src/moc_diffimpl.o src/moc_fileimpl.o src/moc_git.o src/moc_mainimpl.o -L/usr/lib/qt-3.3/lib -lqt-mt
^ permalink raw reply
* Re: qgit-0.6
From: Ingo Molnar @ 2005-06-19 13:02 UTC (permalink / raw)
To: Marco Costalba; +Cc: git, berkus
In-Reply-To: <20050619130035.GA15355@elte.hu>
* Ingo Molnar <mingo@elte.hu> wrote:
> works fine here and is nice and fast, but there are a few minor visual
> glitches:
one more thing: for the annotated output it would be nicer to have
fixed-width fonts to display code. For commit messages the current
output is fine, but code is much more readable in fixed-width output.
Ingo
^ permalink raw reply
* Re: qgit-0.6
From: Ingo Molnar @ 2005-06-19 13:00 UTC (permalink / raw)
To: Marco Costalba; +Cc: git, berkus
In-Reply-To: <20050618103805.8461.qmail@web26302.mail.ukl.yahoo.com>
* Marco Costalba <mcostalba@yahoo.it> wrote:
> A word on annotate: In file viewer, after a while :-), the file
> contents will change to show the annotations. Annotations are
> calculated in background so it may takes some time to show (it depends
> mostly on fetching history patches with git-diff-tree -p ). History is
> snapshotted to actual loaded data so peraphs you need qgit to have
> loaded an interesting amount of data before calling file viewer.
works fine here and is nice and fast, but there are a few minor visual
glitches:
- annotated file contents are not properly aligned over each other. E.g.
check commit 7875b50d1a9928e683299b283bfe94778b6c344e in the current
git repository, and select read-tree.c and view it annotated - the
lines start right after the author field ends, not in any aligned way.
- the tree visualization is hard to follow - gitk's output is much
nicer. As an example of nice rendering check out the octopus merge
around commit 211232bae64bcc60bbf5d1b5e5b2344c22ed767e. One glance at
the gitk output shows what happened - qgit's output is in essence
unreadable.
and a few requests for enhancements if you dont mind:
- in annotated mode, it would be nice to select a particular line
and then double-click would jump to the commit that added that line.
This would nicely round up annotation support.
- plaintext search capability in every window. E.g. in the annotated
file window i often would like to search for some code, or to jump to
a given line.
Ingo
^ permalink raw reply
* quick patch for gitk-1.1
From: Paul Mackerras @ 2005-06-19 12:01 UTC (permalink / raw)
To: git
It turns out that Linus' linux-2.6 tree now has a commit in it with
one of the parents listed twice, which confuses gitk and causes it to
stop with an error. I have a new version of gitk almost ready to go,
but in the meantime here is a quick patch for gitk-1.1 to fix the
problem.
The confusing commit is 13e652800d1644dfedcd0d59ac95ef0beb7f3165.
Paul.
--- gitk~ 2005-06-01 18:14:51.000000000 +1000
+++ gitk 2005-06-19 21:55:02.000000000 +1000
@@ -582,6 +582,7 @@
set ofill white
if {[info exists parents($id)]} {
foreach p $parents($id) {
+ if {[lsearch -exact $actualparents $p] >= 0} continue
if {[info exists ncleft($p)]} {
incr ncleft($p) -1
if {![info exists commitinfo($p)]} {
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Jon Seymour @ 2005-06-19 10:15 UTC (permalink / raw)
To: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506182141400.2268@ppc970.osdl.org>
FWIW, I accept that Linus' bisection algorithm does have better worst
case performance (in terms of number of build/test iterations) on at
least some examples than the literal middle bisection algorithm and
that the "literal middle" bisection algorithm has degenerate cases
which mean that its performance is sometimes worse than O(log 2 N).
I don't actually have a good feel for what the actual bound on Linus'
algorithm is, but I'll measure it on the 2.6 kernel and post the
results.
Regards,
jon.
On 6/19/05, Linus Torvalds <torvalds@osdl.org> wrote:
>
>
> On Sat, 18 Jun 2005, Linus Torvalds wrote:
> >
> > Now, I say "roughly", because there may not _be_ any commit that exactly
> > bisects the case. For a trivial case, let's say that we know that 'A' is
> > bad, and 'B' is good, but the graph in between them looks like this:
>
> Let's make a different case, just to make it even more obvious.
>
> Let's say that the graph is
>
>
> A
> / \
> a1 b1
> | |
> a2 b2
> | |
> a3 b3
> | |
> a4 b4
> | |
> a5 b5
> | |
> a6 b6
> | |
> a7 b7
> | |
> a8 b8
> | |
> a9 b9
> \ /
> B
>
> and we know that "A" is bad, and "B" is good, but we don't know which of
> a1-a9/b1-b9 are buggy.
>
> Where do we start testing?
>
> We start testing at either 'a1' or 'b1', because those are the two values
> that bisect the list either into the "a1-a9" series, or the "b1-b9"
> series. Any other starting point would be a bug.
>
> Or, let's say that the graph is
>
> A
> / \
> | b1
> | |
> | b2
> | |
> | b3
> | |
> a1 b4
> | |
> a2 b5
> | |
> a3 b6
> | |
> | b7
> | |
> | b8
> | |
> | b9
> \ /
> B
>
>
> and in this case the right place to pick is 'b4', because that's the one
> that reaches 6 commits (b4-b9), while it leaves 6 commits unreachable
> (a1-a3, b1-b3): that's a perfect bisection, and now it's totally
> unambiguous (in the previous case a1 and b1 were equally good choices, in
> this case there is only one valid choice).
>
> It gets more interesting when you have intermediate merges:
>
> A
> / \
> | b1
> | |
> | b2
> | |
> | b3
> | |
> a1 b4
> | |
> a2 b5
> | / |
> a3 b6
> | |
> | b7
> | |
> | b8
> | |
> | b9
> \ /
> B
>
> The above graph _looks_ very similar, but now the right place to bisect is
> 'b5', because that reaches six commits (a3 + b5-b9), and again there are
> six commits unreachable (a1-a2 + b1-b4). Again, this is unambiguous -
> there is one clearly superior choice.
>
> The current --bisect algorithm may not always pick that best choice: I
> think I should subtract one from the total number of commits, since right
> now it counts the "good" commit too, ie 'A'. But I think it's at most
> off-by-one.
>
> The bigger problem is that the algorithm is something like O(N^3) in cost
> - albeit with a fairly cheap constant factor. In other words, it might not
> be worthwhile bisecting three years worth of development with it, and you
> migth be better off starting with a rougher half-way-point algorithm
> ("let's try some release a year and a half ago first").
>
> The performance problem seems to really be pretty theoretical: I can
> bisect the developemnt from 2.6.12-rc2 to current head in 0.59 seconds, so
> it's not like it's horribly slow for something like a couple of months
> worth of development.
>
> Linus
>
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/
^ permalink raw reply
* Re: Stacked GIT 0.1 (a.k.a. quilt for git)
From: Catalin Marinas @ 2005-06-19 9:24 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: git
In-Reply-To: <Pine.LNX.4.21.0506182338300.30848-100000@iabervon.org>
Daniel Barkalow <barkalow@iabervon.org> wrote:
> On Sat, 18 Jun 2005, Catalin Marinas wrote:
>> Having different series would be a good idea but it might complicate
>> the tool usage. I will thing about it once I'm sure the basic
>> operations work fine.
>
> You could future-proof yourself a bit by simply saving the base as
> .git/refs/bases/master and making the patches be
> .git/patches/master/. That way, you'd be ready when you start to support
> multiple series.
You are right. I will do this for the next release (0.2, probably of
the end of this week), something like the tree structure below:
.git/refs/bases/<head>
.git/series/<head>/
.git/series/<head>/applied
.git/series/<head>/unapplied
.git/series/<head>/current
.git/series/<head>/patches/*
I don't know whether a git-diff-* command would look into
.git/refs/bases (I can do this in stgit but, this was only for
convenience).
[...]
> Note that it gets more complex if mainline takes only your second patch
> (due to it not requiring your first, and your first not being as
> acceptable). In this case, it needs to entire mainline as a patch, because
> merges can't cherrypick, whereas patches can act arbitrarily. But it would
> be nice to store the information of what happened even with patches that
> cherrypick, such that we have a better chance for managing things
> later.
You can cherry-pick the second patch by first commuting it with the
previous patches. If they are independent, the commuting via diff3
wouldn't generate any conflict. Even with the current stgit, you can
pop all the patches and only push those to be merged upstream. HEAD
would only contain the those patches.
If you want to implement a full-featured patch treacking, you might
end up with something like darcs which doesn't scale to the size of
the Linux kernel. On the other hand, you might not agree with the
changes to your accepted patch and a conflict is welcomed so that you
can choose whether to keep the old version or not.
> But I think that you have the right ideas about how
> patches should be represented, and it would be good to get your
> representation implemented inside git, because operations more central to
> git would benefit from having this information.
Do you mean creating a new git type like the blob, tree or commit? I
would prefer not to modify git or have my own version of git. StGIT
should be a tool running directly on top of an existing installation
of git.
Instead of having a directory for every patch (with bottom, top
etc. files), I could create a git blob to store this information and
the series files (applied/unapplied files) would only contain the blob
id. This could simplify things if, in a future version, stgit would
allow patch cherry-picking.
--
Catalin
^ permalink raw reply
* [PATCH 1/1] git-bug-blatt-script - a script to automate bug finding using Linus' bug blatt algorithm.
From: Jon Seymour @ 2005-06-19 9:22 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This script uses Linus' bug-blatt algorithm to locate a commit which introduced a bug.
To use this script you need to have the following:
- a script that will seek, build and install a specified commit
- a script that will test a build and determine whether it contains a bug
An example test script is included which will simulate an injected bug at a given
commit.
To run this test, use:
count=$(git-rev-list HEAD | wc -l)
root=$(git-rev-list HEAD | tail -1)
# choose an example, 1/3 of the way through the list.
bug=$(git-rev-list HEAD | head -$(echo $count 3 / | dc) | tail -1)
# use "" in second argument to specify a null build
git bug-blatt "" "t/simulate-bug-at $bug" HEAD $root 2>/dev/null
A test case for git-bug-blatt-script has been included in t/t6002-bug-blatt.sh
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
git-bug-blatt-script | 91 +++++++++++++
t/simulate-bug-at | 11 ++
t/t6002-git-bug-blatt-script.sh | 280 +++++++++++++++++++++++++++++++++++++++
3 files changed, 382 insertions(+), 0 deletions(-)
diff --git a/git-bug-blatt-script b/git-bug-blatt-script
new file mode 100755
--- /dev/null
+++ b/git-bug-blatt-script
@@ -0,0 +1,91 @@
+#!/bin/sh
+#
+# (C) Linus Torvalds, Jon Seymour 2005
+#
+# Based on an algorithm posted to the git-list by Linus
+# Torvalds.
+#
+
+die()
+{
+ echo "$*" 1>&2
+ exit 1
+}
+
+info()
+{
+ echo "$@" 1>&2
+}
+
+build_commit()
+{
+ _commit=$1
+ info -n "build @ $_commit..."
+ [ -n "$build" ] || build="echo"
+ if eval "$build $_commit" >/dev/null 2>&1
+ then
+ info "ok"
+ else
+ info "bad"
+ die "git-bug-blatt-script: build failed @ $_commit"
+ fi
+}
+
+test_commit()
+{
+ _commit=$1
+ info -n "test @ $_commit..."
+ eval "$test $_commit" >/dev/null 2>&1
+ if [ $? -eq 0 ]
+ then
+ info "ok"
+ return 0
+ else
+ info "failed"
+ return 1
+ fi
+}
+
+build=$1
+test=$2
+known_bad=$3
+shift 3
+known_goods="$*"
+
+[ -n "$known_goods" ] || die "usage: git-bug-blatt-script build-cmd test-cmd known-bad known-good ...";
+
+(
+build_commit $known_bad
+test_commit $known_bad && die "$known_bad doesn't actually look bad - please check the test"
+
+good_args=""
+for g in $known_goods
+do
+ build_commit $g
+ test_commit $g || die "$g isn't actually good - please check the test"
+ good_args=${good_args}${good_args+ }^$g
+done
+
+start_size=$(git-rev-list $known_bad $good_args | wc -l)
+iterations=0
+while true
+do
+ iterations=`expr $iterations + 1`
+ bisection=$(git-rev-list --bisect $known_bad $good_args)
+ if [ "$bisection" == "$known_bad" ]
+ then
+ info "bug found @ $bisection in $iterations iterations"
+ echo $bisection
+ exit 0
+ fi
+ build_commit $bisection
+ if test_commit $bisection
+ then
+ good_args=${good_args}${good_args+ }"^$bisection"
+ else
+ known_bad=${bisection}
+ fi
+done
+)
+rc=$?
+exit $rc
diff --git a/t/simulate-bug-at b/t/simulate-bug-at
new file mode 100755
--- /dev/null
+++ b/t/simulate-bug-at
@@ -0,0 +1,11 @@
+#!/bin/sh
+bug=$1
+commit=$2
+if git-rev-list $commit | grep "$bug"
+then
+ echo "simulated test failed at $commit"
+ exit 1;
+else
+ echo "simulated test ok at $commit"
+ exit 0;
+fi
diff --git a/t/t6002-git-bug-blatt-script.sh b/t/t6002-git-bug-blatt-script.sh
new file mode 100755
--- /dev/null
+++ b/t/t6002-git-bug-blatt-script.sh
@@ -0,0 +1,280 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Jon Seymour
+#
+
+test_description='Tests git-bug-blatt and --bisect functionality'
+
+. ./test-lib.sh
+
+
+on_committer_date()
+{
+ _date=$1
+ shift 1
+ GIT_COMMITTER_DATE=$_date "$@"
+}
+
+#
+# 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 and suppress any error output.
+hide_error()
+{
+ "$@" 2>/dev/null
+}
+
+check_output()
+{
+ _name=$1
+ shift 1
+ if "$@" | 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 ---
+
+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
+
+
+test_bug_blatt()
+{
+ _bug=$1
+ shift 1
+ git bug-blatt '' "../simulate-bug-at $_bug" "$@" 2>/dev/null
+}
+
+#
+# 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
+
+#
+# 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 l5 ^root' <<EOF
+c3
+EOF
+
+test_output_expect_success "--bisect l5 ^root ^c3" 'git-rev-list --bisect l5 ^root ^c3' <<EOF
+b4
+EOF
+
+test_output_expect_success "--bisect l5 ^root ^c3 ^b4" 'git-rev-list --bisect l5 ^c3 ^b4' <<EOF
+l3
+EOF
+
+test_output_expect_success "--bisect l3 ^root ^c3 ^b4" 'git-rev-list --bisect l3 ^root ^c3 ^b4' <<EOF
+a4
+EOF
+
+test_output_expect_success "--bisect l5 ^b3 ^a3 ^b4 ^a4" 'git-rev-list --bisect 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 l4 ^a2 ^a3 ^b ^a4" 'git-rev-list --bisect l4 ^a2 ^a3 ^a4' <<EOF
+l3
+EOF
+
+test_output_expect_success "--bisect l3 ^a2 ^a3 ^b ^a4" 'git-rev-list --bisect 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 a4 ^a2 ^a3 ^b4" 'git-rev-list --bisect a4 ^a2 ^a3 ^b4' <<EOF
+c2
+EOF
+
+test_output_expect_success "--bisect a4 ^a2 ^a3 ^b4 ^c2" 'git-rev-list --bisect a4 ^a2 ^a3 ^b4 ^c2' <<EOF
+c3
+EOF
+
+test_output_expect_success "--bisect a4 ^a2 ^a3 ^b4 ^c2 ^c3" 'git-rev-list --bisect a4 ^a2 ^a3 ^b4 ^c2 ^c3' <<EOF
+a4
+EOF
+
+# found!
+
+#
+# or consider c3 to be the bad head
+#
+
+test_output_expect_success "--bisect a4 ^a2 ^a3 ^b4" 'git-rev-list --bisect a4 ^a2 ^a3 ^b4' <<EOF
+c2
+EOF
+
+test_output_expect_success "--bisect c3 ^a2 ^a3 ^b4 ^c2" 'git-rev-list --bisect c3 ^a2 ^a3 ^b4 ^c2' <<EOF
+c3
+EOF
+
+# found!
+
+test_output_expect_success "bug-blatt l5 @ l3" "test_bug_blatt $(tag l3) $(tag l5) root" <<EOF
+l3
+EOF
+
+test_output_expect_success "bug-blatt l5 @ a4" "test_bug_blatt $(tag a4) $(tag l5) root" <<EOF
+a4
+EOF
+
+test_output_expect_success "bug-blatt l5 @ c3" "test_bug_blatt $(tag c3) $(tag l5) root" <<EOF
+c3
+EOF
+
+#
+#
+test_done
------------
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Linus Torvalds @ 2005-06-19 5:30 UTC (permalink / raw)
To: David Lang; +Cc: jon, Git Mailing List
In-Reply-To: <Pine.LNX.4.62.0506182204350.11617@qynat.qvtvafvgr.pbz>
On Sat, 18 Jun 2005, David Lang wrote:
>
> if it takes you about as long to type the command (and scan it to make
> sure you didn't mistype it) as it does to execute you don't have a
> performance problem :-)
Yeah, well, in all honesty, I haven't actually verified that my bisection
gives the right answer.
I verified "visually" that it does something half-way sane with this:
git-rev-list --bisect HEAD ^v2.6.12-rc2 > .git/refs/tags/bisect-1
git-rev-list --bisect HEAD ^v2.6.12-rc2 ^bisect-1 > .git/refs/tags/bisect-2
git-rev-list --bisect HEAD ^v2.6.12-rc2 ^bisect-1 ^bisect-2 > .git/refs/tags/bisect-3
git-rev-list --bisect HEAD ^v2.6.12-rc2 ^bisect-1 ^bisect-2 ^bisect-3 > .git/refs/tags/bisect-4
git-rev-list --bisect HEAD ^v2.6.12-rc2 ^bisect-1 ^bisect-2 ^bisect-3 ^bisect-4 > .git/refs/tags/bisect-5
gitk
and it looked sane (ie "bisect-1" should show up as a tag about half-way,
and the others should get progressively closer to the HEAD). But when I
now tried it again (I did the above originally with plain 2.6.12), I get
errors from "gitk":
ERROR: none of the pending commits can be done yet:
bd6ae2f6d61da0f90c6b66e9a4ab6c53ef8c159a
2512809255d018744fe6c2f5e996c83769846c07
88d7bd8cb9eb8d64bf7997600b0d64f7834047c5
b3214970abbe983cd89842ae24ea00e21bba79f6
which looks like the current kernel overflows gitk some way (there's
suddenly a lot more parallellism, since there were a number of merges that
were pending, waiting for the 2.6.12 release).
Linus
^ 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