From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jon Seymour Subject: [PATCH] Rollup of git-rev-list Patch Series 1-7 20 June, 2005 Date: Mon, 20 Jun 2005 12:45:59 +1000 Message-ID: <20050620024559.779.qmail@blackcubes.dyndns.org> Cc: torvalds@osdl.org, jon.seymour@gmail.com, paulus@samba.org X-From: git-owner@vger.kernel.org Mon Jun 20 04:43:14 2005 Return-path: Received: from vger.kernel.org ([12.107.209.244]) by ciao.gmane.org with esmtp (Exim 4.43) id 1DkCFa-00009g-Ra for gcvg-git@gmane.org; Mon, 20 Jun 2005 04:43:03 +0200 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S261388AbVFTCst (ORCPT ); Sun, 19 Jun 2005 22:48:49 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S261404AbVFTCss (ORCPT ); Sun, 19 Jun 2005 22:48:48 -0400 Received: from 203-166-247-224.dyn.iinet.net.au ([203.166.247.224]:24960 "HELO blackcubes.dyndns.org") by vger.kernel.org with SMTP id S261388AbVFTCqC (ORCPT ); Sun, 19 Jun 2005 22:46:02 -0400 Received: (qmail 789 invoked by uid 500); 20 Jun 2005 02:45:59 -0000 To: git@vger.kernel.org Sender: git-owner@vger.kernel.org Precedence: bulk X-Mailing-List: git@vger.kernel.org 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 --- 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 \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 +} + +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 < $_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 < expected-merge-order < 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' < expected-merge-order-1 < actual-merge-order-1 -test_expect_success 'Testing multiple heads' 'diff expected-merge-order-1 actual-merge-order-1' - -cat > expected-merge-order-2 < actual-merge-order-2 -test_expect_success 'Testing stop' 'diff expected-merge-order-2 actual-merge-order-2' - -cat > expected-merge-order-3 < 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' < expected-merge-order-4 < 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' </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' </dev/null' +test_output_expect_success "three nodes one head, one internal, one base" 'git-rev-list --merge-order --show-breaks l1' <