diff options
| -rw-r--r-- | builtin-fmt-merge-msg.c | 2 | ||||
| -rw-r--r-- | builtin-log.c | 123 | ||||
| -rw-r--r-- | builtin-rev-list.c | 16 | ||||
| -rw-r--r-- | commit.c | 150 | ||||
| -rw-r--r-- | commit.h | 25 | ||||
| -rw-r--r-- | revision.c | 125 | ||||
| -rw-r--r-- | revision.h | 21 |
7 files changed, 286 insertions, 176 deletions
diff --git a/builtin-fmt-merge-msg.c b/builtin-fmt-merge-msg.c index 8a3c962f89..6163bd4975 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 197f6eec03..e1f1cf6714 100644 --- a/builtin-log.c +++ b/builtin-log.c @@ -77,11 +77,134 @@ 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 & (TREESAME | UNINTERESTING))) + 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; + 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; + } + + /* 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) +{ + show_early_output = log_show_early; +} + +static void setup_early_output(struct rev_info *rev) +{ + struct sigaction sa; + + /* + * 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. + */ + 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); + show_early_header(rev, "done", 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/builtin-rev-list.c b/builtin-rev-list.c index f5149e59b7..1cb5f67119 100644 --- a/builtin-rev-list.c +++ b/builtin-rev-list.c @@ -153,7 +153,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 & TREESAME)) nr++; commit->object.flags |= COUNTED; p = commit->parents; @@ -209,7 +209,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 & TREESAME) return 0; if (DEBUG_BISECT) return 0; @@ -245,7 +245,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) @@ -279,7 +279,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 & TREESAME) continue; distance = weight(p); if (nr - distance < distance) @@ -319,7 +319,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 & TREESAME) continue; distance = weight(p); if (nr - distance < distance) @@ -373,7 +373,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 & TREESAME)) { weight_set(p, 1); counted++; show_list("bisection 2 count one", @@ -446,7 +446,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 & TREESAME)) { weight_set(p, weight(q)+1); counted++; show_list("bisection 2 count one", @@ -493,7 +493,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 & TREESAME)) nr++; on_list++; } @@ -8,22 +8,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 commit *check_commit(struct object *obj, @@ -431,69 +415,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 * @@ -501,55 +454,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 */ @@ -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]; @@ -135,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 f5b0e83ee3..8f0287fcc0 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; @@ -306,15 +308,28 @@ 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) + 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; } + /* + * 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) + return; + pp = &commit->parents; while ((parent = *pp) != NULL) { struct commit *p = parent->item; @@ -338,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: @@ -366,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) @@ -413,8 +430,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; @@ -533,6 +549,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 +567,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); @@ -674,12 +698,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->topo_setter = topo_sort_default_setter; - revs->topo_getter = topo_sort_default_getter; - revs->commit_format = CMIT_FMT_DEFAULT; diff_setup(&revs->diffopt); @@ -994,6 +1012,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; @@ -1252,7 +1282,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 (!DIFF_OPT_TST(&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); } @@ -1303,9 +1333,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; } @@ -1324,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; @@ -1381,6 +1411,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 && revs->dense) { + /* Commit without changes? */ + if (commit->object.flags & TREESAME) { + /* 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) @@ -1408,36 +1468,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 98a0a8f3fa..992e1e9dd5 100644 --- a/revision.h +++ b/revision.h @@ -3,19 +3,18 @@ #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) #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; -typedef void (prune_fn_t)(struct rev_info *revs, struct commit *commit); - struct rev_info { /* Starting list */ struct commit_list *commits; @@ -27,10 +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, @@ -96,9 +96,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; }; @@ -107,6 +104,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); @@ -131,4 +130,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 |