From a3437b8c26a63d971437c8b6ac6f6d4f632be548 Mon Sep 17 00:00:00 2001 From: "jon@blackcubes.dyndns.org" Date: Mon, 6 Jun 2005 15:39:40 +0000 Subject: [PATCH] Modify git-rev-list to linearise the commit history in merge order. This patch linearises the GIT commit history graph into merge order which is defined by invariants specified in Documentation/git-rev-list.txt. The linearisation produced by this patch is superior in an objective sense to that produced by the existing git-rev-list implementation in that the linearisation produced is guaranteed to have the minimum number of discontinuities, where a discontinuity is defined as an adjacent pair of commits in the output list which are not related in a direct child-parent relationship. With this patch a graph like this: a4 --- | \ \ | b4 | |/ | | a3 | | | | | a2 | | | | c3 | | | | | c2 | b3 | | | /| | b2 | | | c1 | | / | b1 a1 | | | a0 | | / root Sorts like this: = a4 | c3 | c2 | c1 ^ b4 | b3 | b2 | b1 ^ a3 | a2 | a1 | a0 = root Instead of this: = a4 | c3 ^ b4 | a3 ^ c2 ^ b3 ^ a2 ^ b2 ^ c1 ^ a1 ^ b1 ^ a0 = root A test script, t/t6000-rev-list.sh, includes a test which demonstrates that the linearisation produced by --merge-order has less discontinuities than the linearisation produced by git-rev-list without the --merge-order flag specified. To see this, do the following: cd t ./t6000-rev-list.sh cd trash cat actual-default-order cat actual-merge-order The existing behaviour of git-rev-list is preserved, by default. To obtain the modified behaviour, specify --merge-order or --merge-order --show-breaks on the command line. This version of the patch has been tested on the git repository and also on the linux-2.6 repository and has reasonable performance on both - ~50-100% slower than the original algorithm. This version of the patch has incorporated a functional equivalent of the Linus' output limiting algorithm into the merge-order algorithm itself. This operates per the notes associated with Linus' commit 337cb3fb8da45f10fe9a0c3cf571600f55ead2ce. This version has incorporated Linus' feedback regarding proposed changes to rev-list.c. (see: [PATCH] Factor out filtering in rev-list.c) This version has improved the way sort_first_epoch marks commits as uninteresting. For more details about this change, refer to Documentation/git-rev-list.txt and http://blackcubes.dyndns.org/epoch/. Signed-off-by: Jon Seymour Signed-off-by: Linus Torvalds --- rev-list.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 67 insertions(+), 14 deletions(-) (limited to 'rev-list.c') diff --git a/rev-list.c b/rev-list.c index 2b098c1e88..c27b138f3a 100644 --- a/rev-list.c +++ b/rev-list.c @@ -1,9 +1,9 @@ #include "cache.h" #include "commit.h" +#include "epoch.h" #define SEEN (1u << 0) #define INTERESTING (1u << 1) -#define UNINTERESTING (1u << 2) static const char rev_list_usage[] = "usage: git-rev-list [OPTION] commit-id \n" @@ -11,7 +11,8 @@ static const char rev_list_usage[] = " --max-age=epoch\n" " --min-age=epoch\n" " --header\n" - " --pretty"; + " --pretty\n" + " --merge-order [ --show-breaks ]"; static int verbose_header = 0; static int show_parents = 0; @@ -21,9 +22,19 @@ static unsigned long max_age = -1; static unsigned long min_age = -1; 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 void show_commit(struct commit *commit) { + if (show_breaks) { + prefix = "| "; + if (commit->object.flags & DISCONTINUITY) { + prefix = "^ "; + } else if (commit->object.flags & BOUNDARY) { + prefix = "= "; + } + } printf("%s%s", prefix, sha1_to_hex(commit->object.sha1)); if (show_parents) { struct commit_list *parents = commit->parents; @@ -37,7 +48,38 @@ static void show_commit(struct commit *commit) static char pretty_header[16384]; pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header)); printf("%s%c", pretty_header, hdr_termination); + } +} + +static int filter_commit(struct commit * commit) +{ + if (commit->object.flags & UNINTERESTING) + return CONTINUE; + if (min_age != -1 && (commit->date > min_age)) + return CONTINUE; + if (max_age != -1 && (commit->date < max_age)) + return STOP; + if (max_count != -1 && !max_count--) + return STOP; + + return DO; +} + +static int process_commit(struct commit * commit) +{ + int action=filter_commit(commit); + + if (action == STOP) { + return STOP; + } + + if (action == CONTINUE) { + return CONTINUE; } + + show_commit(commit); + + return CONTINUE; } static void show_commit_list(struct commit_list *list) @@ -45,15 +87,8 @@ static void show_commit_list(struct commit_list *list) while (list) { struct commit *commit = pop_most_recent_commit(&list, SEEN); - if (commit->object.flags & UNINTERESTING) - continue; - if (min_age != -1 && (commit->date > min_age)) - continue; - if (max_age != -1 && (commit->date < max_age)) + if (process_commit(commit) == STOP) break; - if (max_count != -1 && !max_count--) - break; - show_commit(commit); } } @@ -151,6 +186,14 @@ int main(int argc, char **argv) show_parents = 1; continue; } + if (!strncmp(arg, "--merge-order", 13)) { + merge_order = 1; + continue; + } + if (!strncmp(arg, "--show-breaks", 13)) { + show_breaks = 1; + continue; + } flags = 0; if (*arg == '^') { @@ -158,7 +201,7 @@ int main(int argc, char **argv) arg++; limited = 1; } - if (get_sha1(arg, sha1)) + if (get_sha1(arg, sha1) || (show_breaks && !merge_order)) usage(rev_list_usage); commit = lookup_commit_reference(sha1); if (!commit || parse_commit(commit) < 0) @@ -170,9 +213,19 @@ int main(int argc, char **argv) if (!list) usage(rev_list_usage); - if (limited) - list = limit_list(list); + if (!merge_order) { + + if (limited) + list = limit_list(list); + show_commit_list(list); + + } else { + + if (sort_list_in_merge_order(list, &process_commit)) { + die("merge order sort failed\n"); + } + + } - show_commit_list(list); return 0; } -- cgit v1.2.1