* [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
* [PATCH 2/7] Tweaked --merge-order --show-breaks output in case specified head has no parent
From: Jon Seymour @ 2005-06-20 2:29 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour, paulus
git-rev-list --merge-order --show-breaks root
Was outputing:
| root
It now outputs:
= root
Which is consistent with the behaviour of other cases.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 2 ++
1 files changed, 2 insertions(+), 0 deletions(-)
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -536,6 +536,8 @@ static int sort_in_merge_order(struct co
ret = parse_commit(head_of_epoch);
+ next->object.flags |= BOUNDARY;
+
while (next && next->parents && !ret && (action != STOP)) {
struct commit *base = NULL;
------------
^ permalink raw reply
* [PATCH 3/7] Fixes problem with --merge-order head ^head
From: Jon Seymour @ 2005-06-20 2:29 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour, paulus
git-rev-list --merge-order HEAD ^HEAD was faulting rather than generating an empty output.
This patch fixes that problem.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 4 +++-
1 files changed, 3 insertions(+), 1 deletions(-)
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -606,7 +606,9 @@ int sort_list_in_merge_order(struct comm
}
}
- if (!reversed->next) {
+ if (!reversed)
+ return ret;
+ else if (!reversed->next) {
/*
* If there is only one element in the list, we can sort it
* using sort_in_merge_order.
------------
^ permalink raw reply
* [PATCH 4/7] Relaxes error checking in epoch.c to allow duplicate parents
From: Jon Seymour @ 2005-06-20 2:29 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour, paulus
Given that real trees in the wild include parents with duplicate parents, I have relaxed
over-zealous error checking in epoch.c and dealt with the problem a different way - duplicate
parents are now silently ignored.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 16 ++++++----------
1 files changed, 6 insertions(+), 10 deletions(-)
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -224,17 +224,13 @@ static int find_base_for_list(struct com
for (; list; list = list->next) {
struct commit *item = list->item;
- if (item->object.util) {
- die("%s:%d:%s: logic error: this should not have happened - commit %s",
- __FILE__, __LINE__, __FUNCTION__,
- sha1_to_hex(item->object.sha1));
- }
-
- new_mass_counter(list->item, get_one());
- add(&injected, &injected, get_one());
+ if (!item->object.util) {
+ new_mass_counter(list->item, get_one());
+ add(&injected, &injected, get_one());
- commit_list_insert(list->item, &cleaner);
- commit_list_insert(list->item, &pending);
+ commit_list_insert(list->item, &cleaner);
+ commit_list_insert(list->item, &pending);
+ }
}
while (!*boundary && pending && !ret) {
------------
^ permalink raw reply
* [PATCH 5/7] Prevent git-rev-list --merge-order producing duplicates in the output
From: Jon Seymour @ 2005-06-20 2:29 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour, paulus
If a is reachable from b, then git-rev-list --merge-order b a would
produce a duplicate output of b.
This causes a problem for an upcoming version of gitk since it
breaks the --merge-order ordering invariant.
This patch fixes the problem for the --merge-order switch. A subsequent
patch will fix the problem for the non --merge-order switch.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 35 +++++++++++++++++++++--------------
1 files changed, 21 insertions(+), 14 deletions(-)
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -621,20 +621,27 @@ int sort_list_in_merge_order(struct comm
base->object.flags |= BOUNDARY;
while (reversed) {
- sort_first_epoch(pop_commit(&reversed), &stack);
- if (reversed) {
- /*
- * If we have more commits to push, then the
- * first push for the next parent may (or may
- * not) represent a discontinuity with respect
- * to the parent currently on the top of
- * the stack.
- *
- * Mark it for checking here, and check it
- * with the next push. See sort_first_epoch()
- * for more details.
- */
- stack->item->object.flags |= DISCONTINUITY;
+ struct commit * next = pop_commit(&reversed);
+
+ if (!(next->object.flags & VISITED)) {
+ sort_first_epoch(next, &stack);
+ if (reversed) {
+ /*
+ * If we have more commits
+ * to push, then the first
+ * push for the next parent may
+ * (or may * not) represent a
+ * discontinuity with respect
+ * to the parent currently on
+ * the top of the stack.
+ *
+ * Mark it for checking here,
+ * and check it with the next
+ * push. See sort_first_epoch()
+ * for more details.
+ */
+ stack->item->object.flags |= DISCONTINUITY;
+ }
}
}
------------
^ permalink raw reply
* [PATCH 6/7] Prevent git-rev-list without --merge-order producing duplicates in output
From: Jon Seymour @ 2005-06-20 2:29 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour, paulus
If b is reachable from a, then:
git-rev-list a b
argument would print one of the commits twice.
This patch fixes that problem. A previous problem fixed it for the
--merge-order switch.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.h | 13 +++++++------
rev-list.c | 5 +++--
2 files changed, 10 insertions(+), 8 deletions(-)
diff --git a/epoch.h b/epoch.h
--- a/epoch.h
+++ b/epoch.h
@@ -10,11 +10,12 @@ 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 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)
-#endif /* EPOCH_H */
+#endif /* EPOCH_H */
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -5,6 +5,7 @@
#define SEEN (1u << 0)
#define INTERESTING (1u << 1)
#define COUNTED (1u << 2)
+#define SHOWN (LAST_EPOCH_FLAG << 2)
static const char rev_list_usage[] =
"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
@@ -29,6 +30,7 @@ static int show_breaks = 0;
static void show_commit(struct commit *commit)
{
+ commit->object.flags |= SHOWN;
if (show_breaks) {
prefix = "| ";
if (commit->object.flags & DISCONTINUITY) {
@@ -55,7 +57,7 @@ static void show_commit(struct commit *c
static int filter_commit(struct commit * commit)
{
- if (commit->object.flags & UNINTERESTING)
+ if (commit->object.flags & (UNINTERESTING|SHOWN))
return CONTINUE;
if (min_age != -1 && (commit->date > min_age))
return CONTINUE;
@@ -63,7 +65,6 @@ static int filter_commit(struct commit *
return STOP;
if (max_count != -1 && !max_count--)
return STOP;
-
return DO;
}
------------
^ permalink raw reply
* [PATCH 7/7] Fix for --merge-order, --max-age interaction issue
From: Jon Seymour @ 2005-06-20 2:29 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour, paulus
This patch fixes a problem reported by Paul Mackerras regarding the interaction
of the --merge-order and --max-age switches of git-rev-list.
This patch applies to the current Linus HEAD. A cleaner fix for the same problem
in my current HEAD will follow later.
With this change, --merge-order produces the same result as no --merge-order
on the linux-2.6 git repository, to wit:
$> git-rev-list --max-age=1116330140 bcfff0b471a60df350338bcd727fc9b8a6aa54b2 | wc -l
655
$> git-rev-list --merge-order --max-age=1116330140 bcfff0b471a60df350338bcd727fc9b8a6aa54b2 | wc -l
655
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
rev-list.c | 13 +++++++++++--
1 files changed, 11 insertions(+), 2 deletions(-)
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -27,6 +27,7 @@ static int max_count = -1;
static enum cmit_fmt commit_format = CMIT_FMT_RAW;
static int merge_order = 0;
static int show_breaks = 0;
+static int stop_traversal = 0;
static void show_commit(struct commit *commit)
{
@@ -57,12 +58,20 @@ static void show_commit(struct commit *c
static int filter_commit(struct commit * commit)
{
+ if (merge_order && 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))
- return STOP;
+ if (max_age != -1 && (commit->date < max_age)) {
+ if (!merge_order)
+ return STOP;
+ else {
+ stop_traversal = 1;
+ return CONTINUE;
+ }
+ }
if (max_count != -1 && !max_count--)
return STOP;
return DO;
------------
^ permalink raw reply
* Re: 'git commit' duplicates parents?
From: Linus Torvalds @ 2005-06-20 2:33 UTC (permalink / raw)
To: Jeff Garzik; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506191921270.2268@ppc970.osdl.org>
On Sun, 19 Jun 2005, Linus Torvalds wrote:
>
> Your commit is a merge. A corrupted one.
Btw, if possibly, you should just undo it. It's "valid" in the sense that
having the same parent duplicated will just be considered to be a merge by
a paritcularly strange person, but it's definitely not good practice, and
since it _is_ technically a merge, programs that avoid showing merges
(like "git-whatchanged" - because it doesn't know what it should show as
the "difference") won't show it.
Other programs, like "git-diff-tree -m", which show _all_ sides of a
merge, will show the diff twice (because it shows the diff against all
parents). Which is also why you see it twice in your git-changes-script.
Again, "git commit" _did_ warn about this, I'm sure, but I actually see
why that stupid MERGE_HEAD file was there - a null merge won't remove a
stale MERGE_HEAD, so it's probably because you did a "git pull" that was a
trivial merge, and that would have left that turd around..
Linus
^ permalink raw reply
* Re: 'git commit' duplicates parents?
From: Jeff Garzik @ 2005-06-20 2:40 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506191926530.2268@ppc970.osdl.org>
Linus Torvalds wrote:
> Btw, if possibly, you should just undo it. It's "valid" in the sense that
Any crap like this, I undo it manually (cat previous head to .git/HEAD)
> Again, "git commit" _did_ warn about this, I'm sure, but I actually see
> why that stupid MERGE_HEAD file was there - a null merge won't remove a
> stale MERGE_HEAD, so it's probably because you did a "git pull" that was a
> trivial merge, and that would have left that turd around..
Probably PEBCAK... my missing the big "MERGE_HEAD exists" warning
caused the problem, it sounds like.
I simply assumed that the vanilla git scripts would clean up after
themselves :)
Jeff
^ permalink raw reply
* [PATCH] Rollup of git-rev-list Patch Series 1-7 20 June, 2005
From: Jon Seymour @ 2005-06-20 2:45 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour, paulus
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
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
This rollup provided for ease of application only.
---
epoch.c | 57 +++--
epoch.h | 13 +
rev-list.c | 18 +-
t/t6001-rev-list-merge-order.sh | 434 ++++++++++++++++++++++++++++++++++-----
4 files changed, 427 insertions(+), 95 deletions(-)
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -224,17 +224,13 @@ static int find_base_for_list(struct com
for (; list; list = list->next) {
struct commit *item = list->item;
- if (item->object.util) {
- die("%s:%d:%s: logic error: this should not have happened - commit %s",
- __FILE__, __LINE__, __FUNCTION__,
- sha1_to_hex(item->object.sha1));
- }
-
- new_mass_counter(list->item, get_one());
- add(&injected, &injected, get_one());
+ if (!item->object.util) {
+ new_mass_counter(list->item, get_one());
+ add(&injected, &injected, get_one());
- commit_list_insert(list->item, &cleaner);
- commit_list_insert(list->item, &pending);
+ commit_list_insert(list->item, &cleaner);
+ commit_list_insert(list->item, &pending);
+ }
}
while (!*boundary && pending && !ret) {
@@ -536,6 +532,8 @@ static int sort_in_merge_order(struct co
ret = parse_commit(head_of_epoch);
+ next->object.flags |= BOUNDARY;
+
while (next && next->parents && !ret && (action != STOP)) {
struct commit *base = NULL;
@@ -604,7 +602,9 @@ int sort_list_in_merge_order(struct comm
}
}
- if (!reversed->next) {
+ if (!reversed)
+ return ret;
+ else if (!reversed->next) {
/*
* If there is only one element in the list, we can sort it
* using sort_in_merge_order.
@@ -621,20 +621,27 @@ int sort_list_in_merge_order(struct comm
base->object.flags |= BOUNDARY;
while (reversed) {
- sort_first_epoch(pop_commit(&reversed), &stack);
- if (reversed) {
- /*
- * If we have more commits to push, then the
- * first push for the next parent may (or may
- * not) represent a discontinuity with respect
- * to the parent currently on the top of
- * the stack.
- *
- * Mark it for checking here, and check it
- * with the next push. See sort_first_epoch()
- * for more details.
- */
- stack->item->object.flags |= DISCONTINUITY;
+ struct commit * next = pop_commit(&reversed);
+
+ if (!(next->object.flags & VISITED)) {
+ sort_first_epoch(next, &stack);
+ if (reversed) {
+ /*
+ * If we have more commits
+ * to push, then the first
+ * push for the next parent may
+ * (or may * not) represent a
+ * discontinuity with respect
+ * to the parent currently on
+ * the top of the stack.
+ *
+ * Mark it for checking here,
+ * and check it with the next
+ * push. See sort_first_epoch()
+ * for more details.
+ */
+ stack->item->object.flags |= DISCONTINUITY;
+ }
}
}
diff --git a/epoch.h b/epoch.h
--- a/epoch.h
+++ b/epoch.h
@@ -10,11 +10,12 @@ 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 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)
-#endif /* EPOCH_H */
+#endif /* EPOCH_H */
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -5,6 +5,7 @@
#define SEEN (1u << 0)
#define INTERESTING (1u << 1)
#define COUNTED (1u << 2)
+#define SHOWN (LAST_EPOCH_FLAG << 2)
static const char rev_list_usage[] =
"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
@@ -26,9 +27,11 @@ static int max_count = -1;
static enum cmit_fmt commit_format = CMIT_FMT_RAW;
static int merge_order = 0;
static int show_breaks = 0;
+static int stop_traversal = 0;
static void show_commit(struct commit *commit)
{
+ commit->object.flags |= SHOWN;
if (show_breaks) {
prefix = "| ";
if (commit->object.flags & DISCONTINUITY) {
@@ -55,15 +58,22 @@ static void show_commit(struct commit *c
static int filter_commit(struct commit * commit)
{
- if (commit->object.flags & UNINTERESTING)
+ if (merge_order && 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))
- return STOP;
+ if (max_age != -1 && (commit->date < max_age)) {
+ if (!merge_order)
+ return STOP;
+ else {
+ stop_traversal = 1;
+ return CONTINUE;
+ }
+ }
if (max_count != -1 && !max_count--)
return STOP;
-
return DO;
}
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: Linus Torvalds @ 2005-06-20 3:00 UTC (permalink / raw)
To: Jeff Garzik; +Cc: Git Mailing List
In-Reply-To: <42B62C85.10701@pobox.com>
On Sun, 19 Jun 2005, Jeff Garzik wrote:
>
> I simply assumed that the vanilla git scripts would clean up after
> themselves :)
Hey, they definitely should. I've pushed out the fixes so far (just pushed
out the ".cmitmsg/.editmsg" cleanup).
Keep the complaints coming when something doesn't work the way it should.
I'll continue to try to blame your incompetence as much as I humanly can,
but hey, some of it is occasionally mine too... ;(
Linus
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Linus Torvalds @ 2005-06-20 3:09 UTC (permalink / raw)
To: jon; +Cc: Git Mailing List
In-Reply-To: <2cfc4032050619125537dee354@mail.gmail.com>
On Mon, 20 Jun 2005, Jon Seymour wrote:
>
> 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.
Exactly.
> 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.
Yes. In many cases it's ok to have parallellism, and the fact that any
normal merges will always be two-way (ie there's never a commit in
practice that has a very high fan-in), I do believe that you normally get
pretty close to that O(log2N) behaviour. In fact, your numbers seemed to
say that we're normally within 10% of it.
> I presume you mean O(N^3)?
Yup again.
> 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).
Well, it depends on how nasty it ends up being. I thought my stupid
algorithm would suck horribly, but considering that it can trivially
bisect all of the git history so far in basically zero time, it doesn't
seem to be that bad. You're more likely to have problems with having to
bring in all the commits from disk in the cold-cache case than you are to
have problems with the current algorithm performance.
Even at O(N^3) it shouldn't be too nasty even if some crazy person tried
to bisect a years worth of development (which really isn't very reasonable
behaviour anyway, it's just not sensible to not try a few standard
releases in between first).
Linus
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Jon Seymour @ 2005-06-20 3:27 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506192002240.2268@ppc970.osdl.org>
> Well, it depends on how nasty it ends up being. I thought my stupid
> algorithm would suck horribly, but considering that it can trivially
> bisect all of the git history so far in basically zero time, it doesn't
> seem to be that bad. You're more likely to have problems with having to
> bring in all the commits from disk in the cold-cache case than you are to
> have problems with the current algorithm performance.
>
I'll give you a sketch of the algorithm.
First, recall that merge-order code uses an incremental topological
sort whose key idea is to employ a conservation of mass analogy. A
similar analogy can help here.
1. count all visible nodes [ i.e. nodes that git-rev-list would print
], call this value N
2. at the top node inject N units of mass
3. traverse the visible graph, in topological order
4. at each node, send all the mass received from parents minus 1 unit
onto visible parents. Record how much mass you have sent downstream.
Keep a record of the nodes that have seen nearest to half of that
mass.
5. when the traversal completes, choose the node that saw closest to
1/2 of the original mass [ or pick one at random if there is more than
one ]. It must be able to reach close to 1/2 of the visible graph,
'cos all that mass it has seen has to drain somewhere!
This algorithm is demonstrably O(V+E) because the traversal is O(V+E)
My intention is to add this algorithm to my refactored
epoch.c/traversal.c, since this is a much better framework for doing
traversals than the current epoch.c.
Do you have any objections to me doing that?
jon.
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Jon Seymour @ 2005-06-20 3:30 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <2cfc403205061920272ee47166@mail.gmail.com>
> 1. count all visible nodes [ i.e. nodes that git-rev-list would print
> ], call this value N
> 2. at the top node inject N units of mass
> 3. traverse the visible graph, in topological order
> 4. at each node, send all the mass received from parents minus 1 unit
> onto visible parents. Record how much mass you have sent downstream.
> Keep a record of the nodes that have seen nearest to half of that
> mass.
Correction - at each node, send all mass received from _children_
^ permalink raw reply
* [PATCH] fix scalability problems with git-deltafy-script
From: Nicolas Pitre @ 2005-06-20 4:37 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
Current version would spin forever and exhaust memory while
attempting to sort all files from all revisions at once, until it
dies before even doing any real work. This is especially noticeable
when used on a big repository like the imported bkcvs repo for the
Linux kernel.
This patch allows for batching the sort to put a bound on needed
resources and making progress early, as well as including some small
cleanups.
Signed-off-by: Nicolas Pitre <nico@cam.org>
diff --git a/git-deltafy-script b/git-deltafy-script
--- a/git-deltafy-script
+++ b/git-deltafy-script
@@ -1,6 +1,6 @@
#!/bin/bash
-# Example script to deltafy an entire GIT repository based on the commit list.
+# Example script to deltify an entire GIT repository based on the commit list.
# The most recent version of a file is the reference and previous versions
# are made delta against the best earlier version available. And so on for
# successive versions going back in time. This way the increasing delta
@@ -25,37 +25,51 @@
set -e
-depth=
-[ "$1" == "-d" ] && depth="--max-depth=$2" && shift 2
+max_depth=
+[ "$1" == "-d" ] && max_depth="--max-depth=$2" && shift 2
+
+overlap=30
+max_behind="--max-behind=$overlap"
function process_list() {
if [ "$list" ]; then
echo "Processing $curr_file"
- echo "$head $list" | xargs git-mkdelta $depth --max-behind=30 -v
+ echo "$list" | xargs git-mkdelta $max_depth $max_behind -v
fi
}
+rev_list=""
curr_file=""
git-rev-list HEAD |
-git-diff-tree -r -t --stdin |
-awk '/^:/ { if ($5 == "M" || $5 == "N") print $4, $6;
- if ($5 == "M") print $3, $6 }' |
-LC_ALL=C sort -s -k 2 | uniq |
-while read sha1 file; do
- if [ "$file" == "$curr_file" ]; then
- list="$list $sha1"
- else
- process_list
- curr_file="$file"
- list=""
- head="$sha1"
- fi
+while true; do
+ # Let's batch revisions into groups of 1000 to give it a chance to
+ # scale with repositories containing long revision lists. We also
+ # overlap with the previous batch the size of mkdelta's look behind
+ # value in order to account for the processing discontinuity.
+ rev_list="$(echo -e -n "$rev_list" | tail --lines=$overlap)"
+ for i in $(seq 1000); do
+ read rev || break
+ rev_list="$rev_list$rev\n"
+ done
+ echo -e -n "$rev_list" |
+ git-diff-tree -r -t --stdin |
+ awk '/^:/ { if ($5 == "M") printf "%s %s\n%s %s\n", $4, $6, $3, $6 }' |
+ LC_ALL=C sort -s -k 2 | uniq |
+ while read sha1 file; do
+ if [ "$file" == "$curr_file" ]; then
+ list="$list $sha1"
+ else
+ process_list
+ curr_file="$file"
+ list="$sha1"
+ fi
+ done
+ [ "$rev" ] || break
done
process_list
curr_file="root directory"
-head=""
list="$(
git-rev-list HEAD |
while read commit; do
^ permalink raw reply
* (no subject)
From: dierbro @ 2005-06-20 7:08 UTC (permalink / raw)
To: git
unsubscribe git
^ permalink raw reply
* Re: 'git commit' duplicates parents?
From: Dan Holmsand @ 2005-06-20 9:48 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506191958010.2268@ppc970.osdl.org>
[-- Attachment #1: Type: text/plain, Size: 687 bytes --]
Linus Torvalds wrote:
> Keep the complaints coming when something doesn't work the way it should.
> I'll continue to try to blame your incompetence as much as I humanly can,
> but hey, some of it is occasionally mine too... ;(
Well, since it's obviously complaint time :-)
git-resolve-script still seems a bit too eager to write MERGE_HEAD and
ORIG_HEAD - they only make sense if there's actually been any merging
done, don't they?
Patch below shows what I mean.
/dan
---
[PATCH] Make git-resolve-script less eager to write MERGE_HEAD
MERGE_HEAD and ORIG_HEAD should only be written if there's actually
been any merging done.
Signed-off-by: Dan Holmsand <holmsand@gmail.com>
[-- Attachment #2: git-resolve-script.patch.txt --]
[-- Type: text/plain, Size: 1468 bytes --]
diff --git a/git-resolve-script b/git-resolve-script
--- a/git-resolve-script
+++ b/git-resolve-script
@@ -12,8 +12,6 @@ merge_repo="$3"
: ${GIT_OBJECT_DIRECTORY="${SHA1_FILE_DIRECTORY-"$GIT_DIR/objects"}"}
rm -f "$GIT_DIR"/MERGE_HEAD "$GIT_DIR"/ORIG_HEAD
-echo $head > "$GIT_DIR"/ORIG_HEAD
-echo $merge > "$GIT_DIR"/MERGE_HEAD
#
# The remote name is just used for the message,
@@ -32,15 +30,13 @@ fi
if [ "$common" == "$merge" ]; then
echo "Already up-to-date. Yeeah!"
- rm -f -- "$GIT_DIR/ORIG_HEAD" "$GIT_DIR/MERGE_HEAD"
exit 0
fi
if [ "$common" == "$head" ]; then
echo "Updating from $head to $merge."
git-read-tree -u -m $head $merge || exit 1
echo $merge > "$GIT_DIR"/HEAD
- git-diff-tree -p ORIG_HEAD HEAD | git-apply --stat
- rm -f -- "$GIT_DIR/ORIG_HEAD" "$GIT_DIR/MERGE_HEAD"
+ git-diff-tree -p $head HEAD | git-apply --stat
exit 0
fi
echo "Trying to merge $merge into $head"
@@ -51,6 +47,8 @@ if [ $? -ne 0 ]; then
echo "Simple merge failed, trying Automatic merge"
git-merge-cache -o git-merge-one-file-script -a
if [ $? -ne 0 ]; then
+ echo $merge > "$GIT_DIR"/MERGE_HEAD
+ echo $head > "$GIT_DIR"/ORIG_HEAD
echo "Automatic merge failed, fix up by hand"
exit 1
fi
@@ -60,4 +58,3 @@ result_commit=$(echo "$merge_msg" | git-
echo "Committed merge $result_commit"
echo $result_commit > "$GIT_DIR"/HEAD
git-diff-tree -p $head $result_commit | git-apply --stat
-rm -f -- "$GIT_DIR/ORIG_HEAD" "$GIT_DIR/MERGE_HEAD"
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Jon Seymour @ 2005-06-20 10:29 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <2cfc40320506192030290187af@mail.gmail.com>
On 6/20/05, Jon Seymour <jon.seymour@gmail.com> wrote:
> > 1. count all visible nodes [ i.e. nodes that git-rev-list would print
> > ], call this value N
> > 2. at the top node inject N units of mass
> > 3. traverse the visible graph, in topological order
> > 4. at each node, send all the mass received from parents minus 1 unit
> > onto visible parents. Record how much mass you have sent downstream.
> > Keep a record of the nodes that have seen nearest to half of that
> > mass.
>
> Correction - at each node, send all mass received from _children_
>
This is a little too simple. It would work if the all nodes in the
visible graph were all connected to the base of an epoch. However, the
pruning behaviour of known goods effectively installs blockages into
the network and causes "backflow" which complicates things somewhat -
a plumbers nightmare!
I am exploring another variation of the idea which is even simpler.
Experimentally it seems quite similar to your average case
performance, but doesn't yet approach your low std deviations.
However, I think I know why that is, so I will, after a few games of
pool and a similar number of beers, have another crack at it.
jon.
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/
^ permalink raw reply
* Re: git merging
From: Jens Axboe @ 2005-06-20 12:30 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Jeff Garzik, Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506171700200.2268@ppc970.osdl.org>
On Fri, Jun 17 2005, Linus Torvalds wrote:
>
>
> On Fri, 17 Jun 2005, Jeff Garzik wrote:
> >
> > This is definitely not the case; my .git/HEAD is _always_ a symlink.
>
> Ok. Are you sure that you gave the same arguments (or rather, lack of
> arguments) to both fsck and "git prune"? The thing is, they are both
> really the same thing, so I'm pretty surprised. If git prune says
> something is unreachable, then git-fsck-cache shouldn't complain about it
> being gone, because one just depends on the other..
Seeing something weird here as well, my setup is similar to Jeffs in
that I have branches in refs/heads/* and HEAD a symlink to the active
one.
I committed a bad patch, so wanting to reverse that change I did an
# echo sha_of_previous_commit > .git/HEAD
# git-read-tree -m HEAD && git-checkout-cache -q -f -u -a
which, if I understand correctly, should put me back where I was before.
So continuing commits, checking the tree now gives me:
axboe@nelson:[.]l/git/linux-2.6-block.git $ git prune
error: cannot map sha1 file c39ae07f393806ccf406ef966e9a15afc43cc36a
bad sha1 entry '5dc01c595e6c6ec9ccda4f6f69c131c0dd945f8c'
axboe@nelson:[.]l/git/linux-2.6-block.git $ git-fsck-cache
error: cannot map sha1 file c39ae07f393806ccf406ef966e9a15afc43cc36a
bad object in tag 5dc01c595e6c6ec9ccda4f6f69c131c0dd945f8c
bad sha1 entry '5dc01c595e6c6ec9ccda4f6f69c131c0dd945f8c'
Running git prune again gives me the same output. What is wrong?
--
Jens Axboe
^ permalink raw reply
* git-read-tree -m -u doesn't delete files: ?
From: Matthias Urlichs @ 2005-06-20 13:46 UTC (permalink / raw)
To: git
Documentation/git-read-tree.txt states:
10 yes yes N/A exists nothing remove path from cache
and
-u::
After a successful merge, update the files in the work
tree with the result of the merge.
... which suggests that the file in question should be deleted.
In fcat, if I have a clean tree A, and I do "git-read-tree -m -u A B",
I'd assume that I should have a clean tree B afterwards.
Would it be safe to add all files for which read_tree.c:merge_cache:fn()
returns zero to a "delete me" list?
--
Matthias Urlichs | {M:U} IT Design @ m-u-it.de | smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
- -
The greatest productive force is human selfishness.
^ permalink raw reply
* Re: git merging
From: Matthias Urlichs @ 2005-06-20 13:48 UTC (permalink / raw)
To: git
In-Reply-To: <20050620123053.GI15021@suse.de>
Hi, Jens Axboe wrote:
> error: cannot map sha1 file c39ae07f393806ccf406ef966e9a15afc43cc36a
> bad object in tag 5dc01c595e6c6ec9ccda4f6f69c131c0dd945f8c
What does "git-cat-file -t" say on these two -- are they botth vald commit
objects?
--
Matthias Urlichs | {M:U} IT Design @ m-u-it.de | smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
- -
He that is giddy thinks the world turns round.
-- William Shakespeare, "The Taming of the Shrew"
^ permalink raw reply
* Re: git merging
From: Jens Axboe @ 2005-06-20 14:13 UTC (permalink / raw)
To: Matthias Urlichs; +Cc: git
In-Reply-To: <pan.2005.06.20.13.48.30.2680@smurf.noris.de>
On Mon, Jun 20 2005, Matthias Urlichs wrote:
> Hi, Jens Axboe wrote:
>
> > error: cannot map sha1 file c39ae07f393806ccf406ef966e9a15afc43cc36a
> > bad object in tag 5dc01c595e6c6ec9ccda4f6f69c131c0dd945f8c
>
> What does "git-cat-file -t" say on these two -- are they botth vald commit
> objects?
axboe@nelson:[.]l/git/linux-2.6-block.git $ git-cat-file -t c39ae07f393806ccf406ef966e9a15afc43cc36a
error: cannot map sha1 file c39ae07f393806ccf406ef966e9a15afc43cc36a
fatal: git-cat-file c39ae07f393806ccf406ef966e9a15afc43cc36a: bad file
axboe@nelson:[.]l/git/linux-2.6-block.git $ git-cat-file -t 5dc01c595e6c6ec9ccda4f6f69c131c0dd945f8c
tag
--
Jens Axboe
^ permalink raw reply
* Re: git-rev-list: "--bisect" flag
From: Jon Seymour @ 2005-06-20 14:37 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <2cfc403205062003292db2b457@mail.gmail.com>
> I am exploring another variation of the idea which is even simpler.
> Experimentally it seems quite similar to your average case
> performance, but doesn't yet approach your low std deviations.
> However, I think I know why that is, so I will, after a few games of
> pool and a similar number of beers, have another crack at it.
>
Ok, just for information, I have a linear bisection algorithm which
results in a bug-blatt algorithm with the following characteristics on
the Linux 2.6 kernel:
AVERAGE 13.64589235
MEDIAN 13
MAX 28
MIN 9
STDEV 2.171923221
These results were derived by running the algorithm over the full 2118
commits of the
current Linux 2.6 source.
I'll document what this algorithm is and what its flaws are.
The algorithm is as follows:
Consider the graph as a closed network of pipes with N reservoirs of 1
unit of volume. Rotate this graph so the head is at the top. Now, pour
N units of liquid into the top of the network of pipes. The liquid
percolates through the network of pipes and ends up in the reservoirs.
The selected bisection point is the node that saw as close to N/2
units of liquid as any other node.
Now, why isn't this as good (in terms of average and stdev) as Linus'
algorithm? The flaw with this algorithm is that some liquid from peer
nodes reaches the lower half of the network before the liquid that
went through the selected node. As a result, the selected node is
elevated "above" the ideal bisection point, by a factor that I believe
would be sufficient to explain the higher average and also the greater
standard deviation.
Still, my algorithm is very simple and very linear, so it's very good a start.
As it happens, I believe I have (re-?)discovered a precise way to
discover the bisection points in O(n). I am in the midst of
implementing that now.
jon.
^ permalink raw reply
* Re: 'git commit' duplicates parents?
From: Linus Torvalds @ 2005-06-20 15:11 UTC (permalink / raw)
To: Dan Holmsand; +Cc: Git Mailing List
In-Reply-To: <42B690EA.2080605@gmail.com>
On Mon, 20 Jun 2005, Dan Holmsand wrote:
>
> git-resolve-script still seems a bit too eager to write MERGE_HEAD and
> ORIG_HEAD - they only make sense if there's actually been any merging
> done, don't they?
>
> Patch below shows what I mean.
I considered this, but decided that MERGE_HEAD is potentially very useful
for some of the other failure exits. There's a few "exit 1"'s in there,
for example when the "git-read-tree -m" fails because of a dirty
workspace.
Of course, you can always re-do the merge completely (and maybe that's
what people end up doing), but at least in theory you can fix it up and
just re-resolve. But in order to do that, you need to know what the
MERGE_HEAD was...
So I'm not sure what the right answer is, which is why my fix was the
minimally invasive one that only removes the heads on success..
Linus
^ permalink raw reply
* How did this odd merge happen?
From: Wayne Scott @ 2005-06-20 15:09 UTC (permalink / raw)
To: git
$ git-cat-file commit 13e652800d1644dfedcd0d59ac95ef0beb7f3165
tree 6cdd9771bd9a56de1b0246a330ccd916ecdb1d41
parent 4332bdd332a2dca93dc3b1d017b2dd27d5c8cef3
parent 88d7bd8cb9eb8d64bf7997600b0d64f7834047c5
parent 88d7bd8cb9eb8d64bf7997600b0d64f7834047c5
author David Woodhouse <dwmw2@shinybook.infradead.org> 1115555034 +0100
committer David Woodhouse <dwmw2@shinybook.infradead.org> 1115555034 +0100
Merge with master.kernel.org:/pub/scm/linux/kernel/git/torvalds/linux-2.6.git
-Wayne
^ 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