From 23c17d4a4a0e1fc9a5fa347f1fc6be3cf477e543 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Fri, 2 Nov 2007 13:32:58 -0700 Subject: Simplify topo-sort logic .. by not using quite so much indirection. This currently grows the "struct commit" a bit, which could be avoided by using a union for "util" and "indegree" (the topo-sort used to use "util" anyway, so you cannot use them together), but for now the goal of this was to simplify, not optimize. Signed-off-by: Linus Torvalds diff --git a/commit.c b/commit.c index 8262f6a..ab4eb8b 100644 --- a/commit.c +++ b/commit.c @@ -9,22 +9,6 @@ int save_commit_buffer = 1; -struct sort_node -{ - /* - * the number of children of the associated commit - * that also occur in the list being sorted. - */ - unsigned int indegree; - - /* - * reference to original list item that we will re-use - * on output. - */ - struct commit_list * list_item; - -}; - const char *commit_type = "commit"; static struct cmt_fmt_map { @@ -1149,69 +1133,38 @@ struct commit *pop_commit(struct commit_list **stack) return item; } -void topo_sort_default_setter(struct commit *c, void *data) -{ - c->util = data; -} - -void *topo_sort_default_getter(struct commit *c) -{ - return c->util; -} - /* * Performs an in-place topological sort on the list supplied. */ void sort_in_topological_order(struct commit_list ** list, int lifo) { - sort_in_topological_order_fn(list, lifo, topo_sort_default_setter, - topo_sort_default_getter); -} - -void sort_in_topological_order_fn(struct commit_list ** list, int lifo, - topo_sort_set_fn_t setter, - topo_sort_get_fn_t getter) -{ - struct commit_list * next = *list; - struct commit_list * work = NULL, **insert; - struct commit_list ** pptr = list; - struct sort_node * nodes; - struct sort_node * next_nodes; - int count = 0; - - /* determine the size of the list */ - while (next) { - next = next->next; - count++; - } + struct commit_list *next, *orig = *list; + struct commit_list *work, **insert; + struct commit_list **pptr; - if (!count) + if (!orig) return; - /* allocate an array to help sort the list */ - nodes = xcalloc(count, sizeof(*nodes)); - /* link the list to the array */ - next_nodes = nodes; - next=*list; - while (next) { - next_nodes->list_item = next; - setter(next->item, next_nodes); - next_nodes++; - next = next->next; + *list = NULL; + + /* Mark them and clear the indegree */ + for (next = orig; next; next = next->next) { + struct commit *commit = next->item; + commit->object.flags |= TOPOSORT; + commit->indegree = 0; } + /* update the indegree */ - next=*list; - while (next) { + for (next = orig; next; next = next->next) { struct commit_list * parents = next->item->parents; while (parents) { - struct commit * parent=parents->item; - struct sort_node * pn = (struct sort_node *) getter(parent); + struct commit *parent = parents->item; - if (pn) - pn->indegree++; - parents=parents->next; + if (parent->object.flags & TOPOSORT) + parent->indegree++; + parents = parents->next; } - next=next->next; } + /* * find the tips * @@ -1219,55 +1172,56 @@ void sort_in_topological_order_fn(struct commit_list ** list, int lifo, * * the tips serve as a starting set for the work queue. */ - next=*list; + work = NULL; insert = &work; - while (next) { - struct sort_node * node = (struct sort_node *) getter(next->item); + for (next = orig; next; next = next->next) { + struct commit *commit = next->item; - if (node->indegree == 0) { - insert = &commit_list_insert(next->item, insert)->next; - } - next=next->next; + if (!commit->indegree) + insert = &commit_list_insert(commit, insert)->next; } /* process the list in topological order */ if (!lifo) sort_by_date(&work); + + pptr = list; + *list = NULL; while (work) { - struct commit * work_item = pop_commit(&work); - struct sort_node * work_node = (struct sort_node *) getter(work_item); - struct commit_list * parents = work_item->parents; + struct commit *commit; + struct commit_list *parents, *work_item; - while (parents) { - struct commit * parent=parents->item; - struct sort_node * pn = (struct sort_node *) getter(parent); - - if (pn) { - /* - * parents are only enqueued for emission - * when all their children have been emitted thereby - * guaranteeing topological order. - */ - pn->indegree--; - if (!pn->indegree) { - if (!lifo) - insert_by_date(parent, &work); - else - commit_list_insert(parent, &work); - } + work_item = work; + work = work_item->next; + work_item->next = NULL; + + commit = work_item->item; + for (parents = commit->parents; parents ; parents = parents->next) { + struct commit *parent=parents->item; + + if (!(parent->object.flags & TOPOSORT)) + continue; + + /* + * parents are only enqueued for emission + * when all their children have been emitted thereby + * guaranteeing topological order. + */ + if (!--parent->indegree) { + if (!lifo) + insert_by_date(parent, &work); + else + commit_list_insert(parent, &work); } - parents=parents->next; } /* * work_item is a commit all of whose children * have already been emitted. we can emit it now. */ - *pptr = work_node->list_item; - pptr = &(*pptr)->next; - *pptr = NULL; - setter(work_item, NULL); + commit->object.flags &= ~TOPOSORT; + *pptr = work_item; + pptr = &work_item->next; } - free(nodes); } /* merge-base stuff */ diff --git a/commit.h b/commit.h index 13b5372..4ed0c1c 100644 --- a/commit.h +++ b/commit.h @@ -14,6 +14,7 @@ struct commit_list { struct commit { struct object object; void *util; + unsigned int indegree; unsigned long date; struct commit_list *parents; struct tree *tree; @@ -84,31 +85,12 @@ void clear_commit_marks(struct commit *commit, unsigned int mark); /* * Performs an in-place topological sort of list supplied. * - * Pre-conditions for sort_in_topological_order: - * all commits in input list and all parents of those - * commits must have object.util == NULL - * - * Pre-conditions for sort_in_topological_order_fn: - * all commits in input list and all parents of those - * commits must have getter(commit) == NULL - * - * Post-conditions: * invariant of resulting list is: * a reachable from b => ord(b) < ord(a) * in addition, when lifo == 0, commits on parallel tracks are * sorted in the dates order. */ - -typedef void (*topo_sort_set_fn_t)(struct commit*, void *data); -typedef void* (*topo_sort_get_fn_t)(struct commit*); - -void topo_sort_default_setter(struct commit *c, void *data); -void *topo_sort_default_getter(struct commit *c); - void sort_in_topological_order(struct commit_list ** list, int lifo); -void sort_in_topological_order_fn(struct commit_list ** list, int lifo, - topo_sort_set_fn_t setter, - topo_sort_get_fn_t getter); struct commit_graft { unsigned char sha1[20]; diff --git a/revision.c b/revision.c index e76da0d..e85b4af 100644 --- a/revision.c +++ b/revision.c @@ -677,9 +677,6 @@ void init_revisions(struct rev_info *revs, const char *prefix) revs->prune_fn = NULL; revs->prune_data = NULL; - revs->topo_setter = topo_sort_default_setter; - revs->topo_getter = topo_sort_default_getter; - revs->commit_format = CMIT_FMT_DEFAULT; diff_setup(&revs->diffopt); @@ -1303,9 +1300,7 @@ int prepare_revision_walk(struct rev_info *revs) if (limit_list(revs) < 0) return -1; if (revs->topo_order) - sort_in_topological_order_fn(&revs->commits, revs->lifo, - revs->topo_setter, - revs->topo_getter); + sort_in_topological_order(&revs->commits, revs->lifo); return 0; } diff --git a/revision.h b/revision.h index 98a0a8f..1f64576 100644 --- a/revision.h +++ b/revision.h @@ -10,6 +10,7 @@ #define CHILD_SHOWN (1u<<6) #define ADDED (1u<<7) /* Parents already parsed and added? */ #define SYMMETRIC_LEFT (1u<<8) +#define TOPOSORT (1u<<9) /* In the active toposort list.. */ struct rev_info; struct log_info; @@ -96,9 +97,6 @@ struct rev_info { struct diff_options diffopt; struct diff_options pruning; - topo_sort_set_fn_t topo_setter; - topo_sort_get_fn_t topo_getter; - struct reflog_walk_info *reflog_info; }; -- cgit v0.10.2-6-g49f6 From cdcefbc971d8fcdd293750af7571d4c715f86964 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sat, 3 Nov 2007 11:11:10 -0700 Subject: Add "--early-output" log flag for interactive GUI use This adds support for "--early-output[=n]" as a flag to the "git log" family of commands. This allows GUI programs to state that they want to get some output early, in order to be able to show at least something quickly, even if the full output may take longer to generate. If no count is specified, a default count of a hundred commits will be used, although the actual numbr of commits output may be smaller depending on how many commits were actually found in the first tenth of a second (or if *everything* was found before that, in which case no early output will be provided, and only the final list is made available). When the full list is generated, there will be a "Final output:" string prepended to it, regardless of whether any early commits were shown or not, so that the consumer can always know the difference between early output and the final list. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano diff --git a/builtin-log.c b/builtin-log.c index 8b2bf63..4e9d0cb 100644 --- a/builtin-log.c +++ b/builtin-log.c @@ -77,11 +77,78 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix, } } +static void log_show_early(struct rev_info *revs, struct commit_list *list) +{ + int i = revs->early_output; + + sort_in_topological_order(&list, revs->lifo); + while (list && i) { + struct commit *commit = list->item; + log_tree_commit(revs, commit); + list = list->next; + i--; + } +} + +static void early_output(int signal) +{ + show_early_output = log_show_early; +} + +static void setup_early_output(struct rev_info *rev) +{ + struct sigaction sa; + struct itimerval v; + + /* + * Set up the signal handler, minimally intrusively: + * we only set a single volatile integer word (not + * using sigatomic_t - trying to avoid unnecessary + * system dependencies and headers), and using + * SA_RESTART. + */ + memset(&sa, 0, sizeof(sa)); + sa.sa_handler = early_output; + sigemptyset(&sa.sa_mask); + sa.sa_flags = SA_RESTART; + sigaction(SIGALRM, &sa, NULL); + + /* + * If we can get the whole output in less than a + * tenth of a second, don't even bother doing the + * early-output thing.. + * + * This is a one-time-only trigger. + */ + memset(&v, 0, sizeof(v)); + v.it_value.tv_sec = 0; + v.it_value.tv_usec = 100000; + setitimer(ITIMER_REAL, &v, NULL); +} + +static void finish_early_output(struct rev_info *rev) +{ + signal(SIGALRM, SIG_IGN); + if (rev->shown_one) { + rev->shown_one = 0; + if (rev->commit_format != CMIT_FMT_ONELINE) + putchar(rev->diffopt.line_termination); + } + printf("Final output:\n"); +} + static int cmd_log_walk(struct rev_info *rev) { struct commit *commit; + if (rev->early_output) + setup_early_output(rev); + prepare_revision_walk(rev); + + if (rev->early_output) + finish_early_output(rev); + while ((commit = get_revision(rev)) != NULL) { log_tree_commit(rev, commit); if (!rev->reflog_info) { diff --git a/revision.c b/revision.c index e85b4af..26610bb 100644 --- a/revision.c +++ b/revision.c @@ -10,6 +10,8 @@ #include "reflog-walk.h" #include "patch-ids.h" +volatile show_early_output_fn_t show_early_output; + static char *path_name(struct name_path *path, const char *name) { struct name_path *p; @@ -533,6 +535,7 @@ static int limit_list(struct rev_info *revs) struct commit_list *entry = list; struct commit *commit = list->item; struct object *obj = &commit->object; + show_early_output_fn_t show; list = list->next; free(entry); @@ -550,6 +553,13 @@ static int limit_list(struct rev_info *revs) if (revs->min_age != -1 && (commit->date > revs->min_age)) continue; p = &commit_list_insert(commit, p)->next; + + show = show_early_output; + if (!show) + continue; + + show(revs, newlist); + show_early_output = NULL; } if (revs->cherry_pick) cherry_pick_list(newlist, revs); @@ -991,6 +1001,18 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch revs->topo_order = 1; continue; } + if (!prefixcmp(arg, "--early-output")) { + int count = 100; + switch (arg[14]) { + case '=': + count = atoi(arg+15); + /* Fallthrough */ + case 0: + revs->topo_order = 1; + revs->early_output = count; + continue; + } + } if (!strcmp(arg, "--parents")) { revs->parents = 1; continue; diff --git a/revision.h b/revision.h index 1f64576..d8a5a50 100644 --- a/revision.h +++ b/revision.h @@ -30,6 +30,8 @@ struct rev_info { void *prune_data; prune_fn_t *prune_fn; + unsigned int early_output; + /* Traversal flags */ unsigned int dense:1, no_merges:1, @@ -105,6 +107,8 @@ struct rev_info { #define REV_TREE_DIFFERENT 2 /* revision.c */ +typedef void (*show_early_output_fn_t)(struct rev_info *, struct commit_list *); +volatile show_early_output_fn_t show_early_output; extern void init_revisions(struct rev_info *revs, const char *prefix); extern int setup_revisions(int argc, const char **argv, struct rev_info *revs, const char *def); -- cgit v0.10.2-6-g49f6 From 252a7c02354a3e2825cfde3c5053a04acc07be9c Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sun, 4 Nov 2007 12:12:05 -0800 Subject: Enhance --early-output format This makes --early-output a bit more advanced, and actually makes it generate multiple "Final output:" headers as it updates things asynchronously. I realize that the "Final output:" line is now illogical, since it's not really final until it also says "done", but It now _always_ generates a "Final output:" header in front of any commit list, and that output header gives you a *guess* at the maximum number of commits available. However, it should be noted that the guess can be completely off: I do a reasonable job estimating it, but it is not meant to be exact. So what happens is that you may get output like this: - at 0.1 seconds: Final output: 2 incomplete .. 2 commits listed .. - half a second later: Final output: 33 incomplete .. 33 commits listed .. - another half a second after that: Final output: 71 incomplete .. 71 commits listed .. - another half second later: Final output: 136 incomplete .. 100 commits listed: we hit the --early-output limit, and .. will only output 100 commits, and after this you'll not .. see an "incomplete" report any more since you got as much .. early output as you asked for! - .. and then finally: Final output: 73106 done .. all the commits .. The above is a real-life scenario on my current kernel tree after having flushed all the caches. Tested with the experimental gitk patch that Paul sent out, and by looking at the actual log output (and verifying that my commit count guesses actually match real life fairly well). Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano diff --git a/builtin-log.c b/builtin-log.c index 4e9d0cb..981f388 100644 --- a/builtin-log.c +++ b/builtin-log.c @@ -77,17 +77,85 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix, } } +/* + * This gives a rough estimate for how many commits we + * will print out in the list. + */ +static int estimate_commit_count(struct rev_info *rev, struct commit_list *list) +{ + int n = 0; + + while (list) { + struct commit *commit = list->item; + unsigned int flags = commit->object.flags; + + list = list->next; + if (flags & UNINTERESTING) + continue; + if (rev->prune_fn && rev->dense && !(flags & TREECHANGE)) { + if (commit->parents && !commit->parents->next) + continue; + } + n++; + } + return n; +} + +static void show_early_header(struct rev_info *rev, const char *stage, int nr) +{ + if (rev->shown_one) { + rev->shown_one = 0; + if (rev->commit_format != CMIT_FMT_ONELINE) + putchar(rev->diffopt.line_termination); + } + printf("Final output: %d %s\n", nr, stage); +} + +struct itimerval early_output_timer; + static void log_show_early(struct rev_info *revs, struct commit_list *list) { int i = revs->early_output; + int show_header = 1; sort_in_topological_order(&list, revs->lifo); while (list && i) { struct commit *commit = list->item; - log_tree_commit(revs, commit); + switch (simplify_commit(revs, commit)) { + case commit_show: + if (show_header) { + int n = estimate_commit_count(revs, list); + show_early_header(revs, "incomplete", n); + show_header = 0; + } + log_tree_commit(revs, commit); + i--; + break; + case commit_ignore: + break; + case commit_error: + return; + } list = list->next; - i--; } + + /* Did we already get enough commits for the early output? */ + if (!i) + return; + + /* + * ..if no, then repeat it twice a second until we + * do. + * + * NOTE! We don't use "it_interval", because if the + * reader isn't listening, we want our output to be + * throttled by the writing, and not have the timer + * trigger every second even if we're blocked on a + * reader! + */ + early_output_timer.it_value.tv_sec = 0; + early_output_timer.it_value.tv_usec = 500000; + setitimer(ITIMER_REAL, &early_output_timer, NULL); } static void early_output(int signal) @@ -98,7 +166,6 @@ static void early_output(int signal) static void setup_early_output(struct rev_info *rev) { struct sigaction sa; - struct itimerval v; /* * Set up the signal handler, minimally intrusively: @@ -120,21 +187,16 @@ static void setup_early_output(struct rev_info *rev) * * This is a one-time-only trigger. */ - memset(&v, 0, sizeof(v)); - v.it_value.tv_sec = 0; - v.it_value.tv_usec = 100000; - setitimer(ITIMER_REAL, &v, NULL); + early_output_timer.it_value.tv_sec = 0; + early_output_timer.it_value.tv_usec = 100000; + setitimer(ITIMER_REAL, &early_output_timer, NULL); } static void finish_early_output(struct rev_info *rev) { + int n = estimate_commit_count(rev, rev->commits); signal(SIGALRM, SIG_IGN); - if (rev->shown_one) { - rev->shown_one = 0; - if (rev->commit_format != CMIT_FMT_ONELINE) - putchar(rev->diffopt.line_termination); - } - printf("Final output:\n"); + show_early_header(rev, "done", n); } static int cmd_log_walk(struct rev_info *rev) diff --git a/revision.c b/revision.c index 26610bb..2e6121f 100644 --- a/revision.c +++ b/revision.c @@ -1398,6 +1398,36 @@ static int commit_match(struct commit *commit, struct rev_info *opt) commit->buffer, strlen(commit->buffer)); } +enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit) +{ + if (commit->object.flags & SHOWN) + return commit_ignore; + if (revs->unpacked && has_sha1_pack(commit->object.sha1, revs->ignore_packed)) + return commit_ignore; + if (commit->object.flags & UNINTERESTING) + return commit_ignore; + if (revs->min_age != -1 && (commit->date > revs->min_age)) + return commit_ignore; + if (revs->no_merges && commit->parents && commit->parents->next) + return commit_ignore; + if (!commit_match(commit, revs)) + return commit_ignore; + if (revs->prune_fn && revs->dense) { + /* Commit without changes? */ + if (!(commit->object.flags & TREECHANGE)) { + /* drop merges unless we want parenthood */ + if (!revs->parents) + return commit_ignore; + /* non-merge - always ignore it */ + if (!commit->parents || !commit->parents->next) + return commit_ignore; + } + if (revs->parents && rewrite_parents(revs, commit) < 0) + return commit_error; + } + return commit_show; +} + static struct commit *get_revision_1(struct rev_info *revs) { if (!revs->commits) @@ -1425,36 +1455,15 @@ static struct commit *get_revision_1(struct rev_info *revs) if (add_parents_to_list(revs, commit, &revs->commits) < 0) return NULL; } - if (commit->object.flags & SHOWN) - continue; - - if (revs->unpacked && has_sha1_pack(commit->object.sha1, - revs->ignore_packed)) - continue; - if (commit->object.flags & UNINTERESTING) - continue; - if (revs->min_age != -1 && (commit->date > revs->min_age)) - continue; - if (revs->no_merges && - commit->parents && commit->parents->next) - continue; - if (!commit_match(commit, revs)) + switch (simplify_commit(revs, commit)) { + case commit_ignore: continue; - if (revs->prune_fn && revs->dense) { - /* Commit without changes? */ - if (!(commit->object.flags & TREECHANGE)) { - /* drop merges unless we want parenthood */ - if (!revs->parents) - continue; - /* non-merge - always ignore it */ - if (!commit->parents || !commit->parents->next) - continue; - } - if (revs->parents && rewrite_parents(revs, commit) < 0) - return NULL; + case commit_error: + return NULL; + default: + return commit; } - return commit; } while (revs->commits); return NULL; } diff --git a/revision.h b/revision.h index d8a5a50..2232247 100644 --- a/revision.h +++ b/revision.h @@ -133,4 +133,12 @@ extern void add_object(struct object *obj, extern void add_pending_object(struct rev_info *revs, struct object *obj, const char *name); +enum commit_action { + commit_ignore, + commit_show, + commit_error +}; + +extern enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit); + #endif -- cgit v0.10.2-6-g49f6 From 53b2c823f6e862e0c83a4a25bab43e8c32e9c289 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 5 Nov 2007 13:22:34 -0800 Subject: revision walker: mini clean-up This removes the unnecessary indirection of "revs->prune_fn", since that function is always the same one (or NULL), and there is in fact not even an abstraction reason to make it a function (i.e. its not called from some other file and doesn't allow us to keep the function itself static or anything like that). It then just replaces it with a bit that says "prune or not", and if not pruning, every commit gets TREECHANGE. That in turn means that - if (!revs->prune_fn || (flags & TREECHANGE)) - if (revs->prune_fn && !(flags & TREECHANGE)) just become - if (flags & TREECHANGE) - if (!(flags & TREECHANGE)) respectively. Together with adding the "single_parent()" helper function, the "complex" conditional now becomes if (!(flags & TREECHANGE) && rev->dense && single_parent(commit)) continue; Also indirection of "revs->dense" checking is thrown away the same way, because TREECHANGE bit is set appropriately now. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano diff --git a/builtin-log.c b/builtin-log.c index 981f388..d6845bc 100644 --- a/builtin-log.c +++ b/builtin-log.c @@ -88,15 +88,9 @@ static int estimate_commit_count(struct rev_info *rev, struct commit_list *list) while (list) { struct commit *commit = list->item; unsigned int flags = commit->object.flags; - list = list->next; - if (flags & UNINTERESTING) - continue; - if (rev->prune_fn && rev->dense && !(flags & TREECHANGE)) { - if (commit->parents && !commit->parents->next) - continue; - } - n++; + if ((flags & TREECHANGE) && !(flags & UNINTERESTING)) + n++; } return n; } diff --git a/builtin-rev-list.c b/builtin-rev-list.c index 6970467..2dec887 100644 --- a/builtin-rev-list.c +++ b/builtin-rev-list.c @@ -142,7 +142,7 @@ static int count_distance(struct commit_list *entry) if (commit->object.flags & (UNINTERESTING | COUNTED)) break; - if (!revs.prune_fn || (commit->object.flags & TREECHANGE)) + if (commit->object.flags & TREECHANGE) nr++; commit->object.flags |= COUNTED; p = commit->parents; @@ -198,7 +198,7 @@ static inline int halfway(struct commit_list *p, int nr) /* * Don't short-cut something we are not going to return! */ - if (revs.prune_fn && !(p->item->object.flags & TREECHANGE)) + if (!(p->item->object.flags & TREECHANGE)) return 0; if (DEBUG_BISECT) return 0; @@ -268,7 +268,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr) int distance; unsigned flags = p->item->object.flags; - if (revs.prune_fn && !(flags & TREECHANGE)) + if (!(flags & TREECHANGE)) continue; distance = weight(p); if (nr - distance < distance) @@ -308,7 +308,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n int distance; unsigned flags = p->item->object.flags; - if (revs.prune_fn && !(flags & TREECHANGE)) + if (!(flags & TREECHANGE)) continue; distance = weight(p); if (nr - distance < distance) @@ -362,7 +362,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list, p->item->util = &weights[n++]; switch (count_interesting_parents(commit)) { case 0: - if (!revs.prune_fn || (flags & TREECHANGE)) { + if (flags & TREECHANGE) { weight_set(p, 1); counted++; show_list("bisection 2 count one", @@ -435,7 +435,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list, * add one for p itself if p is to be counted, * otherwise inherit it from q directly. */ - if (!revs.prune_fn || (flags & TREECHANGE)) { + if (flags & TREECHANGE) { weight_set(p, weight(q)+1); counted++; show_list("bisection 2 count one", @@ -482,7 +482,7 @@ static struct commit_list *find_bisection(struct commit_list *list, continue; p->next = last; last = p; - if (!revs.prune_fn || (flags & TREECHANGE)) + if (flags & TREECHANGE) nr++; on_list++; } diff --git a/commit.h b/commit.h index 4ed0c1c..aa67986 100644 --- a/commit.h +++ b/commit.h @@ -117,4 +117,9 @@ extern int interactive_add(void); extern void add_files_to_cache(int verbose, const char *prefix, const char **files); extern int rerere(void); +static inline int single_parent(struct commit *commit) +{ + return commit->parents && !commit->parents->next; +} + #endif /* COMMIT_H */ diff --git a/revision.c b/revision.c index 2e6121f..931f978 100644 --- a/revision.c +++ b/revision.c @@ -308,6 +308,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) struct commit_list **pp, *parent; int tree_changed = 0, tree_same = 0; + /* + * If we don't do pruning, everything is interesting + */ + if (!revs->prune) { + commit->object.flags |= TREECHANGE; + return; + } + if (!commit->tree) return; @@ -317,6 +325,15 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) return; } + /* + * Normal non-merge commit? If we don't want to make the + * history dense, we consider it always to be a change.. + */ + if (!revs->dense && !commit->parents->next) { + commit->object.flags |= TREECHANGE; + return; + } + pp = &commit->parents; while ((parent = *pp) != NULL) { struct commit *p = parent->item; @@ -415,8 +432,7 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit, str * simplify the commit history and find the parent * that has no differences in the path set if one exists. */ - if (revs->prune_fn) - revs->prune_fn(revs, commit); + try_to_simplify_commit(revs, commit); if (revs->no_walk) return 0; @@ -684,9 +700,6 @@ void init_revisions(struct rev_info *revs, const char *prefix) revs->skip_count = -1; revs->max_count = -1; - revs->prune_fn = NULL; - revs->prune_data = NULL; - revs->commit_format = CMIT_FMT_DEFAULT; diff_setup(&revs->diffopt); @@ -1271,7 +1284,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch diff_tree_setup_paths(revs->prune_data, &revs->pruning); /* Can't prune commits with rename following: the paths change.. */ if (!revs->diffopt.follow_renames) - revs->prune_fn = try_to_simplify_commit; + revs->prune = 1; if (!revs->full_diff) diff_tree_setup_paths(revs->prune_data, &revs->diffopt); } @@ -1412,7 +1425,7 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit) return commit_ignore; if (!commit_match(commit, revs)) return commit_ignore; - if (revs->prune_fn && revs->dense) { + if (revs->prune && revs->dense) { /* Commit without changes? */ if (!(commit->object.flags & TREECHANGE)) { /* drop merges unless we want parenthood */ diff --git a/revision.h b/revision.h index 2232247..a798514 100644 --- a/revision.h +++ b/revision.h @@ -15,8 +15,6 @@ struct rev_info; struct log_info; -typedef void (prune_fn_t)(struct rev_info *revs, struct commit *commit); - struct rev_info { /* Starting list */ struct commit_list *commits; @@ -28,12 +26,11 @@ struct rev_info { /* Basic information */ const char *prefix; void *prune_data; - prune_fn_t *prune_fn; - unsigned int early_output; /* Traversal flags */ unsigned int dense:1, + prune:1, no_merges:1, no_walk:1, remove_empty_trees:1, -- cgit v0.10.2-6-g49f6 From 7dc0fe3be5c949e83e96a1b829be0e72eafffb47 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 12 Nov 2007 23:16:08 -0800 Subject: Fix parent rewriting in --early-output We cannot tell a node that has been checked and found not to be interesting (which does not have the TREECHANGE flag) from a node that hasn't been checked if it is interesting or not, without relying on something else, such as object->parsed. But an object can get the "parsed" flag for other reasons. Which means that "TREECHANGE" has the wrong polarity. This changes the way how the path pruning logic marks an uninteresting commits. From now on, we consider a commit interesting by default, and explicitly mark the ones we decided to prune. The flag is renamed to "TREESAME". Then, this fixes the logic to show the early output with incomplete pruning. It basically says "a commit that has TREESAME set is kind-of-UNINTERESTING", but obviously in a different way than an outright UNINTERESTING commit. Until we parse and examine enough parents to determine if a commit becomes surely "kind-of-UNINTERESTING", we avoid rewriting the ancestry so that later rounds can fix things up. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano diff --git a/builtin-fmt-merge-msg.c b/builtin-fmt-merge-msg.c index 8a3c962..6163bd4 100644 --- a/builtin-fmt-merge-msg.c +++ b/builtin-fmt-merge-msg.c @@ -176,7 +176,7 @@ static void shortlog(const char *name, unsigned char *sha1, struct commit *commit; struct object *branch; struct list subjects = { NULL, NULL, 0, 0 }; - int flags = UNINTERESTING | TREECHANGE | SEEN | SHOWN | ADDED; + int flags = UNINTERESTING | TREESAME | SEEN | SHOWN | ADDED; branch = deref_tag(parse_object(sha1), sha1_to_hex(sha1), 40); if (!branch || branch->type != OBJ_COMMIT) diff --git a/builtin-log.c b/builtin-log.c index d6845bc..54ddaad 100644 --- a/builtin-log.c +++ b/builtin-log.c @@ -89,7 +89,7 @@ static int estimate_commit_count(struct rev_info *rev, struct commit_list *list) struct commit *commit = list->item; unsigned int flags = commit->object.flags; list = list->next; - if ((flags & TREECHANGE) && !(flags & UNINTERESTING)) + if (!(flags & (TREESAME | UNINTERESTING))) n++; } return n; diff --git a/builtin-rev-list.c b/builtin-rev-list.c index 2dec887..0258ec4 100644 --- a/builtin-rev-list.c +++ b/builtin-rev-list.c @@ -142,7 +142,7 @@ static int count_distance(struct commit_list *entry) if (commit->object.flags & (UNINTERESTING | COUNTED)) break; - if (commit->object.flags & TREECHANGE) + if (!(commit->object.flags & TREESAME)) nr++; commit->object.flags |= COUNTED; p = commit->parents; @@ -198,7 +198,7 @@ static inline int halfway(struct commit_list *p, int nr) /* * Don't short-cut something we are not going to return! */ - if (!(p->item->object.flags & TREECHANGE)) + if (p->item->object.flags & TREESAME) return 0; if (DEBUG_BISECT) return 0; @@ -234,7 +234,7 @@ static void show_list(const char *debug, int counted, int nr, char *ep, *sp; fprintf(stderr, "%c%c%c ", - (flags & TREECHANGE) ? 'T' : ' ', + (flags & TREESAME) ? ' ' : 'T', (flags & UNINTERESTING) ? 'U' : ' ', (flags & COUNTED) ? 'C' : ' '); if (commit->util) @@ -268,7 +268,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr) int distance; unsigned flags = p->item->object.flags; - if (!(flags & TREECHANGE)) + if (flags & TREESAME) continue; distance = weight(p); if (nr - distance < distance) @@ -308,7 +308,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n int distance; unsigned flags = p->item->object.flags; - if (!(flags & TREECHANGE)) + if (flags & TREESAME) continue; distance = weight(p); if (nr - distance < distance) @@ -362,7 +362,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list, p->item->util = &weights[n++]; switch (count_interesting_parents(commit)) { case 0: - if (flags & TREECHANGE) { + if (!(flags & TREESAME)) { weight_set(p, 1); counted++; show_list("bisection 2 count one", @@ -435,7 +435,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list, * add one for p itself if p is to be counted, * otherwise inherit it from q directly. */ - if (flags & TREECHANGE) { + if (!(flags & TREESAME)) { weight_set(p, weight(q)+1); counted++; show_list("bisection 2 count one", @@ -482,7 +482,7 @@ static struct commit_list *find_bisection(struct commit_list *list, continue; p->next = last; last = p; - if (flags & TREECHANGE) + if (!(flags & TREESAME)) nr++; on_list++; } diff --git a/revision.c b/revision.c index 931f978..5796153 100644 --- a/revision.c +++ b/revision.c @@ -311,17 +311,15 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) /* * If we don't do pruning, everything is interesting */ - if (!revs->prune) { - commit->object.flags |= TREECHANGE; + if (!revs->prune) return; - } if (!commit->tree) return; if (!commit->parents) { - if (!rev_same_tree_as_empty(revs, commit->tree)) - commit->object.flags |= TREECHANGE; + if (rev_same_tree_as_empty(revs, commit->tree)) + commit->object.flags |= TREESAME; return; } @@ -329,10 +327,8 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) * Normal non-merge commit? If we don't want to make the * history dense, we consider it always to be a change.. */ - if (!revs->dense && !commit->parents->next) { - commit->object.flags |= TREECHANGE; + if (!revs->dense && !commit->parents->next) return; - } pp = &commit->parents; while ((parent = *pp) != NULL) { @@ -357,6 +353,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) } parent->next = NULL; commit->parents = parent; + commit->object.flags |= TREESAME; return; case REV_TREE_NEW: @@ -385,7 +382,8 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1)); } if (tree_changed && !tree_same) - commit->object.flags |= TREECHANGE; + return; + commit->object.flags |= TREESAME; } static int add_parents_to_list(struct rev_info *revs, struct commit *commit, struct commit_list **list) @@ -1354,7 +1352,9 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp return rewrite_one_error; if (p->parents && p->parents->next) return rewrite_one_ok; - if (p->object.flags & (TREECHANGE | UNINTERESTING)) + if (p->object.flags & UNINTERESTING) + return rewrite_one_ok; + if (!(p->object.flags & TREESAME)) return rewrite_one_ok; if (!p->parents) return rewrite_one_noparents; @@ -1427,7 +1427,7 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit) return commit_ignore; if (revs->prune && revs->dense) { /* Commit without changes? */ - if (!(commit->object.flags & TREECHANGE)) { + if (commit->object.flags & TREESAME) { /* drop merges unless we want parenthood */ if (!revs->parents) return commit_ignore; diff --git a/revision.h b/revision.h index a798514..992e1e9 100644 --- a/revision.h +++ b/revision.h @@ -3,7 +3,7 @@ #define SEEN (1u<<0) #define UNINTERESTING (1u<<1) -#define TREECHANGE (1u<<2) +#define TREESAME (1u<<2) #define SHOWN (1u<<3) #define TMP_MARK (1u<<4) /* for isolated cases; clean after use */ #define BOUNDARY (1u<<5) -- cgit v0.10.2-6-g49f6