diff options
Diffstat (limited to 'revision.c')
| -rw-r--r-- | revision.c | 334 |
1 files changed, 282 insertions, 52 deletions
diff --git a/revision.c b/revision.c index 8ce660e3b1..13e0519c02 100644 --- a/revision.c +++ b/revision.c @@ -25,6 +25,8 @@ #include "worktree.h" #include "argv-array.h" #include "commit-reach.h" +#include "commit-graph.h" +#include "prio-queue.h" volatile show_early_output_fn_t show_early_output; @@ -52,7 +54,8 @@ static void mark_blob_uninteresting(struct blob *blob) blob->object.flags |= UNINTERESTING; } -static void mark_tree_contents_uninteresting(struct tree *tree) +static void mark_tree_contents_uninteresting(struct repository *r, + struct tree *tree) { struct tree_desc desc; struct name_entry entry; @@ -64,10 +67,10 @@ static void mark_tree_contents_uninteresting(struct tree *tree) while (tree_entry(&desc, &entry)) { switch (object_type(entry.mode)) { case OBJ_TREE: - mark_tree_uninteresting(lookup_tree(the_repository, entry.oid)); + mark_tree_uninteresting(r, lookup_tree(r, entry.oid)); break; case OBJ_BLOB: - mark_blob_uninteresting(lookup_blob(the_repository, entry.oid)); + mark_blob_uninteresting(lookup_blob(r, entry.oid)); break; default: /* Subproject commit - not in this repository */ @@ -82,7 +85,7 @@ static void mark_tree_contents_uninteresting(struct tree *tree) free_tree_buffer(tree); } -void mark_tree_uninteresting(struct tree *tree) +void mark_tree_uninteresting(struct repository *r, struct tree *tree) { struct object *obj; @@ -93,7 +96,7 @@ void mark_tree_uninteresting(struct tree *tree) if (obj->flags & UNINTERESTING) return; obj->flags |= UNINTERESTING; - mark_tree_contents_uninteresting(tree); + mark_tree_contents_uninteresting(r, tree); } struct commit_stack { @@ -176,7 +179,6 @@ static void add_pending_object_with_path(struct rev_info *revs, strbuf_release(&buf); return; /* do not add the commit itself */ } - obj->flags |= USER_GIVEN; add_object_array_with_path(obj, name, &revs->pending, mode, path); } @@ -199,7 +201,7 @@ void add_head_to_pending(struct rev_info *revs) struct object *obj; if (get_oid("HEAD", &oid)) return; - obj = parse_object(the_repository, &oid); + obj = parse_object(revs->repo, &oid); if (!obj) return; add_pending_object(revs, obj, "HEAD"); @@ -211,7 +213,7 @@ static struct object *get_reference(struct rev_info *revs, const char *name, { struct object *object; - object = parse_object(the_repository, oid); + object = parse_object(revs->repo, oid); if (!object) { if (revs->ignore_missing) return object; @@ -248,7 +250,7 @@ static struct commit *handle_commit(struct rev_info *revs, add_pending_object(revs, object, tag->tag); if (!tag->tagged) die("bad tag"); - object = parse_object(the_repository, &tag->tagged->oid); + object = parse_object(revs->repo, &tag->tagged->oid); if (!object) { if (revs->ignore_missing_links || (flags & UNINTERESTING)) return NULL; @@ -298,7 +300,7 @@ static struct commit *handle_commit(struct rev_info *revs, if (!revs->tree_objects) return NULL; if (flags & UNINTERESTING) { - mark_tree_contents_uninteresting(tree); + mark_tree_contents_uninteresting(revs->repo, tree); return NULL; } add_pending_object_with_path(revs, object, name, mode, path); @@ -767,8 +769,8 @@ static void commit_list_insert_by_date_cached(struct commit *p, struct commit_li *cache = new_entry; } -static int add_parents_to_list(struct rev_info *revs, struct commit *commit, - struct commit_list **list, struct commit_list **cache_ptr) +static int process_parents(struct rev_info *revs, struct commit *commit, + struct commit_list **list, struct commit_list **cache_ptr) { struct commit_list *parent = commit->parents; unsigned left_flag; @@ -807,7 +809,8 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit, if (p->object.flags & SEEN) continue; p->object.flags |= SEEN; - commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); + if (list) + commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); } return 0; } @@ -846,7 +849,8 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit, p->object.flags |= left_flag; if (!(p->object.flags & SEEN)) { p->object.flags |= SEEN; - commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); + if (list) + commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); } if (revs->first_parent_only) break; @@ -878,7 +882,7 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs) return; left_first = left_count < right_count; - init_patch_ids(&ids); + init_patch_ids(revs->repo, &ids); ids.diffopts.pathspec = revs->diffopt.pathspec; /* Compute patch-ids for one side */ @@ -1090,7 +1094,7 @@ static int limit_list(struct rev_info *revs) if (revs->max_age != -1 && (commit->date < revs->max_age)) obj->flags |= UNINTERESTING; - if (add_parents_to_list(revs, commit, &list, NULL) < 0) + if (process_parents(revs, commit, &list, NULL) < 0) return -1; if (obj->flags & UNINTERESTING) { mark_parents_uninteresting(commit); @@ -1254,7 +1258,7 @@ static void handle_one_reflog_commit(struct object_id *oid, void *cb_data) { struct all_refs_cb *cb = cb_data; if (!is_null_oid(oid)) { - struct object *o = parse_object(the_repository, oid); + struct object *o = parse_object(cb->all_revs->repo, oid); if (o) { o->flags |= cb->all_flags; /* ??? CMDLINEFLAGS ??? */ @@ -1327,13 +1331,14 @@ void add_reflogs_to_pending(struct rev_info *revs, unsigned flags) } static void add_cache_tree(struct cache_tree *it, struct rev_info *revs, - struct strbuf *path) + struct strbuf *path, unsigned int flags) { size_t baselen = path->len; int i; if (it->entry_count >= 0) { - struct tree *tree = lookup_tree(the_repository, &it->oid); + struct tree *tree = lookup_tree(revs->repo, &it->oid); + tree->object.flags |= flags; add_pending_object_with_path(revs, &tree->object, "", 040000, path->buf); } @@ -1341,14 +1346,15 @@ static void add_cache_tree(struct cache_tree *it, struct rev_info *revs, for (i = 0; i < it->subtree_nr; i++) { struct cache_tree_sub *sub = it->down[i]; strbuf_addf(path, "%s%s", baselen ? "/" : "", sub->name); - add_cache_tree(sub->cache_tree, revs, path); + add_cache_tree(sub->cache_tree, revs, path, flags); strbuf_setlen(path, baselen); } } static void do_add_index_objects_to_pending(struct rev_info *revs, - struct index_state *istate) + struct index_state *istate, + unsigned int flags) { int i; @@ -1359,16 +1365,17 @@ static void do_add_index_objects_to_pending(struct rev_info *revs, if (S_ISGITLINK(ce->ce_mode)) continue; - blob = lookup_blob(the_repository, &ce->oid); + blob = lookup_blob(revs->repo, &ce->oid); if (!blob) die("unable to add index blob to traversal"); + blob->object.flags |= flags; add_pending_object_with_path(revs, &blob->object, "", ce->ce_mode, ce->name); } if (istate->cache_tree) { struct strbuf path = STRBUF_INIT; - add_cache_tree(istate->cache_tree, revs, &path); + add_cache_tree(istate->cache_tree, revs, &path, flags); strbuf_release(&path); } } @@ -1377,8 +1384,8 @@ void add_index_objects_to_pending(struct rev_info *revs, unsigned int flags) { struct worktree **worktrees, **p; - read_cache(); - do_add_index_objects_to_pending(revs, &the_index); + read_index(revs->repo->index); + do_add_index_objects_to_pending(revs, revs->repo->index, flags); if (revs->single_worktree) return; @@ -1394,7 +1401,7 @@ void add_index_objects_to_pending(struct rev_info *revs, unsigned int flags) if (read_index_from(&istate, worktree_git_path(wt, "index"), get_worktree_git_dir(wt)) > 0) - do_add_index_objects_to_pending(revs, &istate); + do_add_index_objects_to_pending(revs, &istate, flags); discard_index(&istate); } free_worktrees(worktrees); @@ -1446,10 +1453,13 @@ static int add_parents_only(struct rev_info *revs, const char *arg_, int flags, return 1; } -void init_revisions(struct rev_info *revs, const char *prefix) +void repo_init_revisions(struct repository *r, + struct rev_info *revs, + const char *prefix) { memset(revs, 0, sizeof(*revs)); + revs->repo = r; revs->abbrev = DEFAULT_ABBREV; revs->ignore_merges = 1; revs->simplify_history = 1; @@ -1471,11 +1481,11 @@ void init_revisions(struct rev_info *revs, const char *prefix) revs->commit_format = CMIT_FMT_DEFAULT; revs->expand_tabs_in_log_default = 8; - init_grep_defaults(); - grep_init(&revs->grep_filter, prefix); + init_grep_defaults(revs->repo); + grep_init(&revs->grep_filter, revs->repo, prefix); revs->grep_filter.status_only = 1; - diff_setup(&revs->diffopt); + repo_diff_setup(revs->repo, &revs->diffopt); if (prefix && !revs->diffopt.prefix) { revs->diffopt.prefix = prefix; revs->diffopt.prefix_length = strlen(prefix); @@ -1503,6 +1513,7 @@ static void prepare_show_merge(struct rev_info *revs) struct object_id oid; const char **prune = NULL; int i, prune_num = 1; /* counting terminating NULL */ + struct index_state *istate = revs->repo->index; if (get_oid("HEAD", &oid)) die("--merge without HEAD?"); @@ -1518,20 +1529,20 @@ static void prepare_show_merge(struct rev_info *revs) free_commit_list(bases); head->object.flags |= SYMMETRIC_LEFT; - if (!active_nr) - read_cache(); - for (i = 0; i < active_nr; i++) { - const struct cache_entry *ce = active_cache[i]; + if (!istate->cache_nr) + read_index(istate); + for (i = 0; i < istate->cache_nr; i++) { + const struct cache_entry *ce = istate->cache[i]; if (!ce_stage(ce)) continue; - if (ce_path_match(&the_index, ce, &revs->prune_data, NULL)) { + if (ce_path_match(istate, ce, &revs->prune_data, NULL)) { prune_num++; REALLOC_ARRAY(prune, prune_num); prune[prune_num-2] = ce->name; prune[prune_num-1] = NULL; } - while ((i+1 < active_nr) && - ce_same_name(ce, active_cache[i+1])) + while ((i+1 < istate->cache_nr) && + ce_same_name(ce, istate->cache[i+1])) i++; } clear_pathspec(&revs->prune_data); @@ -1588,8 +1599,8 @@ static int handle_dotdot_1(const char *arg, char *dotdot, *dotdot = '\0'; } - a_obj = parse_object(the_repository, &a_oid); - b_obj = parse_object(the_repository, &b_oid); + a_obj = parse_object(revs->repo, &a_oid); + b_obj = parse_object(revs->repo, &b_oid); if (!a_obj || !b_obj) return dotdot_missing(arg, dotdot, revs, symmetric); @@ -1602,8 +1613,8 @@ static int handle_dotdot_1(const char *arg, char *dotdot, struct commit *a, *b; struct commit_list *exclude; - a = lookup_commit_reference(the_repository, &a_obj->oid); - b = lookup_commit_reference(the_repository, &b_obj->oid); + a = lookup_commit_reference(revs->repo, &a_obj->oid); + b = lookup_commit_reference(revs->repo, &b_obj->oid); if (!a || !b) return dotdot_missing(arg, dotdot, revs, symmetric); @@ -2140,7 +2151,8 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg revs->limited = 1; } else if (!strcmp(arg, "--ignore-missing")) { revs->ignore_missing = 1; - } else if (!strcmp(arg, "--exclude-promisor-objects")) { + } else if (revs->allow_exclude_promisor_objects_opt && + !strcmp(arg, "--exclude-promisor-objects")) { if (fetch_if_missing) BUG("exclude_promisor_objects can only be used when fetch_if_missing is 0"); revs->exclude_promisor_objects = 1; @@ -2211,7 +2223,7 @@ static int handle_revision_pseudo_opt(const char *submodule, BUG("--single-worktree cannot be used together with submodule"); refs = get_submodule_ref_store(submodule); } else - refs = get_main_ref_store(the_repository); + refs = get_main_ref_store(revs->repo); /* * NOTE! @@ -2460,7 +2472,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s if (revs->diffopt.objfind) revs->simplify_history = 0; - if (revs->topo_order) + if (revs->topo_order && !generation_numbers_enabled(the_repository)) revs->limited = 1; if (revs->prune_data.nr) { @@ -2891,13 +2903,225 @@ void reset_revision_walk(void) static int mark_uninteresting(const struct object_id *oid, struct packed_git *pack, uint32_t pos, - void *unused) + void *cb) { - struct object *o = parse_object(the_repository, oid); + struct rev_info *revs = cb; + struct object *o = parse_object(revs->repo, oid); o->flags |= UNINTERESTING | SEEN; return 0; } +define_commit_slab(indegree_slab, int); +define_commit_slab(author_date_slab, timestamp_t); + +struct topo_walk_info { + uint32_t min_generation; + struct prio_queue explore_queue; + struct prio_queue indegree_queue; + struct prio_queue topo_queue; + struct indegree_slab indegree; + struct author_date_slab author_date; +}; + +static inline void test_flag_and_insert(struct prio_queue *q, struct commit *c, int flag) +{ + if (c->object.flags & flag) + return; + + c->object.flags |= flag; + prio_queue_put(q, c); +} + +static void explore_walk_step(struct rev_info *revs) +{ + struct topo_walk_info *info = revs->topo_walk_info; + struct commit_list *p; + struct commit *c = prio_queue_get(&info->explore_queue); + + if (!c) + return; + + if (parse_commit_gently(c, 1) < 0) + return; + + if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE) + record_author_date(&info->author_date, c); + + if (revs->max_age != -1 && (c->date < revs->max_age)) + c->object.flags |= UNINTERESTING; + + if (process_parents(revs, c, NULL, NULL) < 0) + return; + + if (c->object.flags & UNINTERESTING) + mark_parents_uninteresting(c); + + for (p = c->parents; p; p = p->next) + test_flag_and_insert(&info->explore_queue, p->item, TOPO_WALK_EXPLORED); +} + +static void explore_to_depth(struct rev_info *revs, + uint32_t gen_cutoff) +{ + struct topo_walk_info *info = revs->topo_walk_info; + struct commit *c; + while ((c = prio_queue_peek(&info->explore_queue)) && + c->generation >= gen_cutoff) + explore_walk_step(revs); +} + +static void indegree_walk_step(struct rev_info *revs) +{ + struct commit_list *p; + struct topo_walk_info *info = revs->topo_walk_info; + struct commit *c = prio_queue_get(&info->indegree_queue); + + if (!c) + return; + + if (parse_commit_gently(c, 1) < 0) + return; + + explore_to_depth(revs, c->generation); + + for (p = c->parents; p; p = p->next) { + struct commit *parent = p->item; + int *pi = indegree_slab_at(&info->indegree, parent); + + if (*pi) + (*pi)++; + else + *pi = 2; + + test_flag_and_insert(&info->indegree_queue, parent, TOPO_WALK_INDEGREE); + + if (revs->first_parent_only) + return; + } +} + +static void compute_indegrees_to_depth(struct rev_info *revs, + uint32_t gen_cutoff) +{ + struct topo_walk_info *info = revs->topo_walk_info; + struct commit *c; + while ((c = prio_queue_peek(&info->indegree_queue)) && + c->generation >= gen_cutoff) + indegree_walk_step(revs); +} + +static void init_topo_walk(struct rev_info *revs) +{ + struct topo_walk_info *info; + struct commit_list *list; + revs->topo_walk_info = xmalloc(sizeof(struct topo_walk_info)); + info = revs->topo_walk_info; + memset(info, 0, sizeof(struct topo_walk_info)); + + init_indegree_slab(&info->indegree); + memset(&info->explore_queue, 0, sizeof(info->explore_queue)); + memset(&info->indegree_queue, 0, sizeof(info->indegree_queue)); + memset(&info->topo_queue, 0, sizeof(info->topo_queue)); + + switch (revs->sort_order) { + default: /* REV_SORT_IN_GRAPH_ORDER */ + info->topo_queue.compare = NULL; + break; + case REV_SORT_BY_COMMIT_DATE: + info->topo_queue.compare = compare_commits_by_commit_date; + break; + case REV_SORT_BY_AUTHOR_DATE: + init_author_date_slab(&info->author_date); + info->topo_queue.compare = compare_commits_by_author_date; + info->topo_queue.cb_data = &info->author_date; + break; + } + + info->explore_queue.compare = compare_commits_by_gen_then_commit_date; + info->indegree_queue.compare = compare_commits_by_gen_then_commit_date; + + info->min_generation = GENERATION_NUMBER_INFINITY; + for (list = revs->commits; list; list = list->next) { + struct commit *c = list->item; + + if (parse_commit_gently(c, 1)) + continue; + + test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED); + test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE); + + if (c->generation < info->min_generation) + info->min_generation = c->generation; + + *(indegree_slab_at(&info->indegree, c)) = 1; + + if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE) + record_author_date(&info->author_date, c); + } + compute_indegrees_to_depth(revs, info->min_generation); + + for (list = revs->commits; list; list = list->next) { + struct commit *c = list->item; + + if (*(indegree_slab_at(&info->indegree, c)) == 1) + prio_queue_put(&info->topo_queue, c); + } + + /* + * This is unfortunate; the initial tips need to be shown + * in the order given from the revision traversal machinery. + */ + if (revs->sort_order == REV_SORT_IN_GRAPH_ORDER) + prio_queue_reverse(&info->topo_queue); +} + +static struct commit *next_topo_commit(struct rev_info *revs) +{ + struct commit *c; + struct topo_walk_info *info = revs->topo_walk_info; + + /* pop next off of topo_queue */ + c = prio_queue_get(&info->topo_queue); + + if (c) + *(indegree_slab_at(&info->indegree, c)) = 0; + + return c; +} + +static void expand_topo_walk(struct rev_info *revs, struct commit *commit) +{ + struct commit_list *p; + struct topo_walk_info *info = revs->topo_walk_info; + if (process_parents(revs, commit, NULL, NULL) < 0) { + if (!revs->ignore_missing_links) + die("Failed to traverse parents of commit %s", + oid_to_hex(&commit->object.oid)); + } + + for (p = commit->parents; p; p = p->next) { + struct commit *parent = p->item; + int *pi; + + if (parse_commit_gently(parent, 1) < 0) + continue; + + if (parent->generation < info->min_generation) { + info->min_generation = parent->generation; + compute_indegrees_to_depth(revs, info->min_generation); + } + + pi = indegree_slab_at(&info->indegree, parent); + + (*pi)--; + if (*pi == 1) + prio_queue_put(&info->topo_queue, parent); + + if (revs->first_parent_only) + return; + } +} + int prepare_revision_walk(struct rev_info *revs) { int i; @@ -2926,7 +3150,7 @@ int prepare_revision_walk(struct rev_info *revs) revs->treesame.name = "treesame"; if (revs->exclude_promisor_objects) { - for_each_packed_object(mark_uninteresting, NULL, + for_each_packed_object(mark_uninteresting, revs, FOR_EACH_OBJECT_PROMISOR_ONLY); } @@ -2934,11 +3158,13 @@ int prepare_revision_walk(struct rev_info *revs) commit_list_sort_by_date(&revs->commits); if (revs->no_walk) return 0; - if (revs->limited) + if (revs->limited) { if (limit_list(revs) < 0) return -1; - if (revs->topo_order) - sort_in_topological_order(&revs->commits, revs->sort_order); + if (revs->topo_order) + sort_in_topological_order(&revs->commits, revs->sort_order); + } else if (revs->topo_order) + init_topo_walk(revs); if (revs->line_level_traverse) line_log_filter(revs); if (revs->simplify_merges) @@ -2955,7 +3181,7 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp for (;;) { struct commit *p = *pp; if (!revs->limited) - if (add_parents_to_list(revs, p, &revs->commits, &cache) < 0) + if (process_parents(revs, p, &revs->commits, &cache) < 0) return rewrite_one_error; if (p->object.flags & UNINTERESTING) return rewrite_one_ok; @@ -3263,6 +3489,8 @@ static struct commit *get_revision_1(struct rev_info *revs) if (revs->reflog_info) commit = next_reflog_entry(revs->reflog_info); + else if (revs->topo_walk_info) + commit = next_topo_commit(revs); else commit = pop_commit(&revs->commits); @@ -3284,7 +3512,9 @@ static struct commit *get_revision_1(struct rev_info *revs) if (revs->reflog_info) try_to_simplify_commit(revs, commit); - else if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) { + else if (revs->topo_walk_info) + expand_topo_walk(revs, commit); + else if (process_parents(revs, commit, &revs->commits, NULL) < 0) { if (!revs->ignore_missing_links) die("Failed to traverse parents of commit %s", oid_to_hex(&commit->object.oid)); |