From: Junio C Hamano Date: Sun, 18 Nov 2018 09:23:52 +0000 (+0900) Subject: Merge branch 'ds/reachable-topo-order' X-Git-Tag: v2.20.0-rc0~27 X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/62ca33e02a4ea93dd59538ac986a082430253b27?ds=inline;hp=-c Merge branch 'ds/reachable-topo-order' The revision walker machinery learned to take advantage of the commit generation numbers stored in the commit-graph file. * ds/reachable-topo-order: t6012: make rev-list tests more interesting revision.c: generation-based topo-order algorithm commit/revisions: bookkeeping before refactoring revision.c: begin refactoring --topo-order logic test-reach: add rev-list tests test-reach: add run_three_modes method prio-queue: add 'peek' operation --- 62ca33e02a4ea93dd59538ac986a082430253b27 diff --combined commit.c index d566d7e45c,a025a0db60..bee7b7b62e --- a/commit.c +++ b/commit.c @@@ -17,8 -17,6 +17,8 @@@ #include "sha1-lookup.h" #include "wt-status.h" #include "advice.h" +#include "refs.h" +#include "commit-reach.h" static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **); @@@ -211,7 -209,7 +211,7 @@@ static int read_graft_file(struct repos return 0; } -static void prepare_commit_graft(struct repository *r) +void prepare_commit_graft(struct repository *r) { char *graft_file; @@@ -657,11 -655,10 +657,10 @@@ struct commit *pop_commit(struct commit /* count number of children that have not been emitted */ define_commit_slab(indegree_slab, int); - /* record author-date for each commit object */ define_commit_slab(author_date_slab, timestamp_t); - static void record_author_date(struct author_date_slab *author_date, - struct commit *commit) + void record_author_date(struct author_date_slab *author_date, + struct commit *commit) { const char *buffer = get_commit_buffer(commit, NULL); struct ident_split ident; @@@ -686,8 -683,8 +685,8 @@@ fail_exit unuse_commit_buffer(commit, buffer); } - static int compare_commits_by_author_date(const void *a_, const void *b_, - void *cb_data) + int compare_commits_by_author_date(const void *a_, const void *b_, + void *cb_data) { const struct commit *a = a_, *b = b_; struct author_date_slab *author_date = cb_data; @@@ -845,86 -842,6 +844,86 @@@ void sort_in_topological_order(struct c clear_author_date_slab(&author_date); } +struct rev_collect { + struct commit **commit; + int nr; + int alloc; + unsigned int initial : 1; +}; + +static void add_one_commit(struct object_id *oid, struct rev_collect *revs) +{ + struct commit *commit; + + if (is_null_oid(oid)) + return; + + commit = lookup_commit(the_repository, oid); + if (!commit || + (commit->object.flags & TMP_MARK) || + parse_commit(commit)) + return; + + ALLOC_GROW(revs->commit, revs->nr + 1, revs->alloc); + revs->commit[revs->nr++] = commit; + commit->object.flags |= TMP_MARK; +} + +static int collect_one_reflog_ent(struct object_id *ooid, struct object_id *noid, + const char *ident, timestamp_t timestamp, + int tz, const char *message, void *cbdata) +{ + struct rev_collect *revs = cbdata; + + if (revs->initial) { + revs->initial = 0; + add_one_commit(ooid, revs); + } + add_one_commit(noid, revs); + return 0; +} + +struct commit *get_fork_point(const char *refname, struct commit *commit) +{ + struct object_id oid; + struct rev_collect revs; + struct commit_list *bases; + int i; + struct commit *ret = NULL; + + memset(&revs, 0, sizeof(revs)); + revs.initial = 1; + for_each_reflog_ent(refname, collect_one_reflog_ent, &revs); + + if (!revs.nr && !get_oid(refname, &oid)) + add_one_commit(&oid, &revs); + + for (i = 0; i < revs.nr; i++) + revs.commit[i]->object.flags &= ~TMP_MARK; + + bases = get_merge_bases_many(commit, revs.nr, revs.commit); + + /* + * There should be one and only one merge base, when we found + * a common ancestor among reflog entries. + */ + if (!bases || bases->next) + goto cleanup_return; + + /* And the found one must be one of the reflog entries */ + for (i = 0; i < revs.nr; i++) + if (&bases->item->object == &revs.commit[i]->object) + break; /* found */ + if (revs.nr <= i) + goto cleanup_return; + + ret = bases->item; + +cleanup_return: + free_commit_list(bases); + return ret; +} + static const char gpg_sig_header[] = "gpgsig"; static const int gpg_sig_header_len = sizeof(gpg_sig_header) - 1; diff --combined commit.h index 8f15cfd43b,ec5b9093ad..03ab19508f --- a/commit.h +++ b/commit.h @@@ -8,6 -8,7 +8,7 @@@ #include "gpg-interface.h" #include "string-list.h" #include "pretty.h" + #include "commit-slab.h" #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF #define GENERATION_NUMBER_INFINITY 0xFFFFFFFF @@@ -202,11 -203,8 +203,11 @@@ typedef int (*each_commit_graft_fn)(con struct commit_graft *read_graft_line(struct strbuf *line); int register_commit_graft(struct repository *r, struct commit_graft *, int); +void prepare_commit_graft(struct repository *r); struct commit_graft *lookup_commit_graft(struct repository *r, const struct object_id *oid); +struct commit *get_fork_point(const char *refname, struct commit *commit); + /* largest positive number a signed 32-bit integer can contain */ #define INFINITE_DEPTH 0x7fffffff @@@ -251,9 -249,7 +252,9 @@@ extern void assign_shallow_commits_to_r uint32_t **used, int *ref_status); extern int delayed_reachability_test(struct shallow_info *si, int c); -extern void prune_shallow(int show_only); +#define PRUNE_SHOW_ONLY 1 +#define PRUNE_QUICK 2 +extern void prune_shallow(unsigned options); extern struct trace_key trace_shallow; extern int interactive_add(int argc, const char **argv, const char *prefix, int patch); @@@ -333,6 -329,12 +334,12 @@@ extern int remove_signature(struct strb */ extern int check_commit_signature(const struct commit *commit, struct signature_check *sigc); + /* record author-date for each commit object */ + struct author_date_slab; + void record_author_date(struct author_date_slab *author_date, + struct commit *commit); + + int compare_commits_by_author_date(const void *a_, const void *b_, void *unused); int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused); int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused); diff --combined revision.c index bdd3e7c9f1,4ef47d2fb4..13e0519c02 --- a/revision.c +++ b/revision.c @@@ -25,6 -25,8 +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,8 -54,7 +54,8 @@@ static void mark_blob_uninteresting(str 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; @@@ -65,10 -66,10 +67,10 @@@ 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 */ @@@ -83,7 -84,7 +85,7 @@@ free_tree_buffer(tree); } -void mark_tree_uninteresting(struct tree *tree) +void mark_tree_uninteresting(struct repository *r, struct tree *tree) { struct object *obj; @@@ -94,7 -95,7 +96,7 @@@ if (obj->flags & UNINTERESTING) return; obj->flags |= UNINTERESTING; - mark_tree_contents_uninteresting(tree); + mark_tree_contents_uninteresting(r, tree); } struct commit_stack { @@@ -177,6 -178,7 +179,6 @@@ static void add_pending_object_with_pat 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 +201,7 @@@ void add_head_to_pending(struct rev_inf 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 +213,7 @@@ static struct object *get_reference(str { 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 +250,7 @@@ static struct commit *handle_commit(str 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 +300,7 @@@ 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 +769,8 @@@ static void commit_list_insert_by_date_ *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 +809,8 @@@ 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 +849,8 @@@ 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 +882,7 @@@ static void cherry_pick_list(struct com 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 +1094,7 @@@ static int limit_list(struct rev_info * 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); @@@ -1177,7 -1181,7 +1181,7 @@@ struct all_refs_cb int warned_bad_reflog; struct rev_info *all_revs; const char *name_for_errormsg; - struct ref_store *refs; + struct worktree *wt; }; int ref_excluded(struct string_list *ref_excludes, const char *path) @@@ -1214,7 -1218,7 +1218,7 @@@ static void init_all_refs_cb(struct all cb->all_revs = revs; cb->all_flags = flags; revs->rev_input_given = 1; - cb->refs = NULL; + cb->wt = NULL; } void clear_ref_exclusion(struct string_list **ref_excludes_p) @@@ -1254,7 -1258,7 +1258,7 @@@ static void handle_one_reflog_commit(st { 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 ??? */ @@@ -1277,20 -1281,14 +1281,20 @@@ static int handle_one_reflog_ent(struc return 0; } -static int handle_one_reflog(const char *path, const struct object_id *oid, +static int handle_one_reflog(const char *refname_in_wt, + const struct object_id *oid, int flag, void *cb_data) { struct all_refs_cb *cb = cb_data; + struct strbuf refname = STRBUF_INIT; + cb->warned_bad_reflog = 0; - cb->name_for_errormsg = path; - refs_for_each_reflog_ent(cb->refs, path, + strbuf_worktree_ref(cb->wt, &refname, refname_in_wt); + cb->name_for_errormsg = refname.buf; + refs_for_each_reflog_ent(get_main_ref_store(the_repository), + refname.buf, handle_one_reflog_ent, cb_data); + strbuf_release(&refname); return 0; } @@@ -1305,8 -1303,8 +1309,8 @@@ static void add_other_reflogs_to_pendin if (wt->is_current) continue; - cb->refs = get_worktree_ref_store(wt); - refs_for_each_reflog(cb->refs, + cb->wt = wt; + refs_for_each_reflog(get_worktree_ref_store(wt), handle_one_reflog, cb); } @@@ -1319,7 -1317,7 +1323,7 @@@ void add_reflogs_to_pending(struct rev_ cb.all_revs = revs; cb.all_flags = flags; - cb.refs = get_main_ref_store(the_repository); + cb.wt = NULL; for_each_reflog(handle_one_reflog, &cb); if (!revs->single_worktree) @@@ -1327,14 -1325,13 +1331,14 @@@ } 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); } @@@ -1342,15 -1339,14 +1346,15 @@@ 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; @@@ -1361,17 -1357,16 +1365,17 @@@ 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); } } @@@ -1380,8 -1375,8 +1384,8 @@@ void add_index_objects_to_pending(struc { 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; @@@ -1397,7 -1392,7 +1401,7 @@@ 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); @@@ -1449,13 -1444,10 +1453,13 @@@ static int add_parents_only(struct rev_ 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; @@@ -1477,11 -1469,11 +1481,11 @@@ 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); @@@ -1509,7 -1501,6 +1513,7 @@@ static void prepare_show_merge(struct r 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?"); @@@ -1525,20 -1516,20 +1529,20 @@@ 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); @@@ -1595,8 -1586,8 +1599,8 @@@ static int handle_dotdot_1(const char * *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); @@@ -1609,8 -1600,8 +1613,8 @@@ 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); @@@ -2147,8 -2138,7 +2151,8 @@@ static int handle_revision_opt(struct r 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; @@@ -2219,7 -2209,7 +2223,7 @@@ static int handle_revision_pseudo_opt(c 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! @@@ -2468,7 -2458,7 +2472,7 @@@ int setup_revisions(int argc, const cha 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) { @@@ -2899,14 -2889,224 +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; @@@ -2935,7 -3135,7 +3150,7 @@@ 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); } @@@ -2943,11 -3143,13 +3158,13 @@@ 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) @@@ -2964,7 -3166,7 +3181,7 @@@ static enum rewrite_result rewrite_one( 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; @@@ -3272,6 -3474,8 +3489,8 @@@ static struct commit *get_revision_1(st 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); @@@ -3293,7 -3497,9 +3512,9 @@@ 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)); diff --combined revision.h index 0d2abc2d36,b0b3bb8025..7987bfcd2e --- a/revision.h +++ b/revision.h @@@ -21,23 -21,17 +21,26 @@@ #define SYMMETRIC_LEFT (1u<<8) #define PATCHSAME (1u<<9) #define BOTTOM (1u<<10) -#define USER_GIVEN (1u<<25) /* given directly by the user */ +/* + * Indicates object was reached by traversal. i.e. not given by user on + * command-line or stdin. + * NEEDSWORK: NOT_USER_GIVEN doesn't apply to commits because we only support + * filtering trees and blobs, but it may be useful to support filtering commits + * in the future. + */ +#define NOT_USER_GIVEN (1u<<25) #define TRACK_LINEAR (1u<<26) -#define ALL_REV_FLAGS (((1u<<11)-1) | USER_GIVEN | TRACK_LINEAR) +#define ALL_REV_FLAGS (((1u<<11)-1) | NOT_USER_GIVEN | TRACK_LINEAR) + + #define TOPO_WALK_EXPLORED (1u<<27) + #define TOPO_WALK_INDEGREE (1u<<28) + #define DECORATE_SHORT_REFS 1 #define DECORATE_FULL_REFS 2 -struct rev_info; struct log_info; +struct repository; +struct rev_info; struct string_list; struct saved_parents; define_shared_commit_slab(revision_sources, char *); @@@ -64,11 -58,12 +67,13 @@@ struct rev_cmdline_info #define REVISION_WALK_NO_WALK_SORTED 1 #define REVISION_WALK_NO_WALK_UNSORTED 2 + struct topo_walk_info; + struct rev_info { /* Starting list */ struct commit_list *commits; struct object_array pending; + struct repository *repo; /* Parents of shown commits */ struct object_array boundary_commits; @@@ -140,23 -135,7 +145,23 @@@ line_level_traverse:1, tree_blobs_in_commit_order:1, + /* + * Blobs are shown without regard for their existence. + * But not so for trees: unless exclude_promisor_objects + * is set and the tree in question is a promisor object; + * OR ignore_missing_links is set, the revision walker + * dies with a "bad tree object HASH" message when + * encountering a missing tree. For callers that can + * handle missing trees and want them to be filterable + * and showable, set this to true. The revision walker + * will filter and show such a missing tree as usual, + * but will not attempt to recurse into this tree + * object. + */ + do_not_die_on_missing_tree:1, + /* for internal use only */ + allow_exclude_promisor_objects_opt:1, exclude_promisor_objects:1; /* Diff flags */ @@@ -270,6 -249,8 +275,8 @@@ const char *break_bar; struct revision_sources *sources; + + struct topo_walk_info *topo_walk_info; }; int ref_excluded(struct string_list *, const char *path); @@@ -289,17 -270,12 +296,17 @@@ extern volatile show_early_output_fn_t struct setup_revision_opt { const char *def; void (*tweak)(struct rev_info *, struct setup_revision_opt *); - const char *submodule; + const char *submodule; /* TODO: drop this and use rev_info->repo */ int assume_dashdash; unsigned revarg_opt; }; -void init_revisions(struct rev_info *revs, const char *prefix); +#ifndef NO_THE_REPOSITORY_COMPATIBILITY_MACROS +#define init_revisions(revs, prefix) repo_init_revisions(the_repository, revs, prefix) +#endif +void repo_init_revisions(struct repository *r, + struct rev_info *revs, + const char *prefix); int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct setup_revision_opt *); void parse_revision_opt(struct rev_info *revs, struct parse_opt_ctx_t *ctx, @@@ -319,7 -295,7 +326,7 @@@ void put_revision_mark(const struct rev const struct commit *commit); void mark_parents_uninteresting(struct commit *commit); -void mark_tree_uninteresting(struct tree *tree); +void mark_tree_uninteresting(struct repository *r, struct tree *tree); void show_object_with_name(FILE *, struct object *, const char *); diff --combined t/t6600-test-reach.sh index a0c64e617a,288f703b7b..b24d850036 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@@ -31,8 -31,7 +31,8 @@@ test_expect_success 'setup' for i in $(test_seq 1 10) do test_commit "1-$i" && - git branch -f commit-1-$i + git branch -f commit-1-$i && + git tag -a -m "1-$i" tag-1-$i commit-1-$i done && for j in $(test_seq 1 9) do @@@ -40,13 -39,11 +40,13 @@@ x=$(($j + 1)) && test_commit "$x-1" && git branch -f commit-$x-1 && + git tag -a -m "$x-1" tag-$x-1 commit-$x-1 && for i in $(test_seq 2 10) do git merge commit-$j-$i -m "$x-$i" && - git branch -f commit-$x-$i + git branch -f commit-$x-$i && + git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i done done && git commit-graph write --reachable && @@@ -56,18 -53,22 +56,22 @@@ git config core.commitGraph true ' - test_three_modes () { + run_three_modes () { test_when_finished rm -rf .git/objects/info/commit-graph && - test-tool reach $1 actual && + "$@" actual && test_cmp expect actual && cp commit-graph-full .git/objects/info/commit-graph && - test-tool reach $1 actual && + "$@" actual && test_cmp expect actual && cp commit-graph-half .git/objects/info/commit-graph && - test-tool reach $1 actual && + "$@" actual && test_cmp expect actual } + test_three_modes () { + run_three_modes test-tool reach "$@" + } + test_expect_success 'ref_newer:miss' ' cat >input <<-\EOF && A:commit-5-7 @@@ -208,29 -209,6 +212,29 @@@ test_expect_success 'can_all_from_reach test_three_modes can_all_from_reach ' +test_expect_success 'can_all_from_reach_with_flag: tags case' ' + cat >input <<-\EOF && + X:tag-2-10 + X:tag-3-9 + X:tag-4-8 + X:commit-5-7 + X:commit-6-6 + X:commit-7-5 + X:commit-8-4 + X:commit-9-3 + Y:tag-1-9 + Y:tag-2-8 + Y:tag-3-7 + Y:commit-4-6 + Y:commit-5-5 + Y:commit-6-4 + Y:commit-7-3 + Y:commit-8-1 + EOF + echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect && + test_three_modes can_all_from_reach_with_flag +' + test_expect_success 'commit_contains:hit' ' cat >input <<-\EOF && A:commit-7-7 @@@ -265,56 -243,88 +269,140 @@@ test_expect_success 'commit_contains:mi test_three_modes commit_contains --tag ' + test_expect_success 'rev-list: basic topo-order' ' + git rev-parse \ + commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \ + commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \ + commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \ + commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \ + commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \ + commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \ + >expect && + run_three_modes git rev-list --topo-order commit-6-6 + ' + + test_expect_success 'rev-list: first-parent topo-order' ' + git rev-parse \ + commit-6-6 \ + commit-6-5 \ + commit-6-4 \ + commit-6-3 \ + commit-6-2 \ + commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \ + >expect && + run_three_modes git rev-list --first-parent --topo-order commit-6-6 + ' + + test_expect_success 'rev-list: range topo-order' ' + git rev-parse \ + commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \ + commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \ + commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \ + commit-6-3 commit-5-3 commit-4-3 \ + commit-6-2 commit-5-2 commit-4-2 \ + commit-6-1 commit-5-1 commit-4-1 \ + >expect && + run_three_modes git rev-list --topo-order commit-3-3..commit-6-6 + ' + + test_expect_success 'rev-list: range topo-order' ' + git rev-parse \ + commit-6-6 commit-5-6 commit-4-6 \ + commit-6-5 commit-5-5 commit-4-5 \ + commit-6-4 commit-5-4 commit-4-4 \ + commit-6-3 commit-5-3 commit-4-3 \ + commit-6-2 commit-5-2 commit-4-2 \ + commit-6-1 commit-5-1 commit-4-1 \ + >expect && + run_three_modes git rev-list --topo-order commit-3-8..commit-6-6 + ' + + test_expect_success 'rev-list: first-parent range topo-order' ' + git rev-parse \ + commit-6-6 \ + commit-6-5 \ + commit-6-4 \ + commit-6-3 \ + commit-6-2 \ + commit-6-1 commit-5-1 commit-4-1 \ + >expect && + run_three_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6 + ' + + test_expect_success 'rev-list: ancestry-path topo-order' ' + git rev-parse \ + commit-6-6 commit-5-6 commit-4-6 commit-3-6 \ + commit-6-5 commit-5-5 commit-4-5 commit-3-5 \ + commit-6-4 commit-5-4 commit-4-4 commit-3-4 \ + commit-6-3 commit-5-3 commit-4-3 \ + >expect && + run_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6 + ' + + test_expect_success 'rev-list: symmetric difference topo-order' ' + git rev-parse \ + commit-6-6 commit-5-6 commit-4-6 \ + commit-6-5 commit-5-5 commit-4-5 \ + commit-6-4 commit-5-4 commit-4-4 \ + commit-6-3 commit-5-3 commit-4-3 \ + commit-6-2 commit-5-2 commit-4-2 \ + commit-6-1 commit-5-1 commit-4-1 \ + commit-3-8 commit-2-8 commit-1-8 \ + commit-3-7 commit-2-7 commit-1-7 \ + >expect && + run_three_modes git rev-list --topo-order commit-3-8...commit-6-6 + ' + +test_expect_success 'get_reachable_subset:all' ' + cat >input <<-\EOF && + X:commit-9-1 + X:commit-8-3 + X:commit-7-5 + X:commit-6-6 + X:commit-1-7 + Y:commit-3-3 + Y:commit-1-7 + Y:commit-5-6 + EOF + ( + echo "get_reachable_subset(X,Y)" && + git rev-parse commit-3-3 \ + commit-1-7 \ + commit-5-6 | sort + ) >expect && + test_three_modes get_reachable_subset +' + +test_expect_success 'get_reachable_subset:some' ' + cat >input <<-\EOF && + X:commit-9-1 + X:commit-8-3 + X:commit-7-5 + X:commit-1-7 + Y:commit-3-3 + Y:commit-1-7 + Y:commit-5-6 + EOF + ( + echo "get_reachable_subset(X,Y)" && + git rev-parse commit-3-3 \ + commit-1-7 | sort + ) >expect && + test_three_modes get_reachable_subset +' + +test_expect_success 'get_reachable_subset:none' ' + cat >input <<-\EOF && + X:commit-9-1 + X:commit-8-3 + X:commit-7-5 + X:commit-1-7 + Y:commit-9-3 + Y:commit-7-6 + Y:commit-2-8 + EOF + echo "get_reachable_subset(X,Y)" >expect && + test_three_modes get_reachable_subset +' + test_done