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)
}
}
+/*
+ * 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) {
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;
/*
* 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;
char *ep, *sp;
fprintf(stderr, "%c%c%c ",
- (flags & TREECHANGE) ? 'T' : ' ',
+ (flags & TREESAME) ? ' ' : 'T',
(flags & UNINTERESTING) ? 'U' : ' ',
(flags & COUNTED) ? 'C' : ' ');
if (commit->util)
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)
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)
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",
* 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",
continue;
p->next = last;
last = p;
- if (!revs.prune_fn || (flags & TREECHANGE))
+ if (!(flags & TREESAME))
nr++;
on_list++;
}
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,
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
*
*
* 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 */
struct commit {
struct object object;
void *util;
+ unsigned int indegree;
unsigned long date;
struct commit_list *parents;
struct tree *tree;
/*
* 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];
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 */
#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;
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;
}
parent->next = NULL;
commit->parents = parent;
+ commit->object.flags |= TREESAME;
return;
case REV_TREE_NEW:
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)
* 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;
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);
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);
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);
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_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);
}
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;
}
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;
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)
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;
}
#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;
/* 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,
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;
};
#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);
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