diff options
Diffstat (limited to 'src/revwalk.c')
| -rw-r--r-- | src/revwalk.c | 820 |
1 files changed, 0 insertions, 820 deletions
diff --git a/src/revwalk.c b/src/revwalk.c deleted file mode 100644 index a686a9f6f..000000000 --- a/src/revwalk.c +++ /dev/null @@ -1,820 +0,0 @@ -/* - * Copyright (C) the libgit2 contributors. All rights reserved. - * - * This file is part of libgit2, distributed under the GNU GPL v2 with - * a Linking Exception. For full terms see the included COPYING file. - */ - -#include "revwalk.h" - -#include "commit.h" -#include "odb.h" -#include "pool.h" - -#include "git2/revparse.h" -#include "merge.h" -#include "vector.h" - -static int get_revision(git_commit_list_node **out, git_revwalk *walk, git_commit_list **list); - -git_commit_list_node *git_revwalk__commit_lookup( - git_revwalk *walk, const git_oid *oid) -{ - git_commit_list_node *commit; - - /* lookup and reserve space if not already present */ - if ((commit = git_oidmap_get(walk->commits, oid)) != NULL) - return commit; - - commit = git_commit_list_alloc_node(walk); - if (commit == NULL) - return NULL; - - git_oid_cpy(&commit->oid, oid); - - if ((git_oidmap_set(walk->commits, &commit->oid, commit)) < 0) - return NULL; - - return commit; -} - -int git_revwalk__push_commit(git_revwalk *walk, const git_oid *oid, const git_revwalk__push_options *opts) -{ - git_oid commit_id; - int error; - git_object *obj, *oobj; - git_commit_list_node *commit; - git_commit_list *list; - - if ((error = git_object_lookup(&oobj, walk->repo, oid, GIT_OBJECT_ANY)) < 0) - return error; - - error = git_object_peel(&obj, oobj, GIT_OBJECT_COMMIT); - git_object_free(oobj); - - if (error == GIT_ENOTFOUND || error == GIT_EINVALIDSPEC || error == GIT_EPEEL) { - /* If this comes from e.g. push_glob("tags"), ignore this */ - if (opts->from_glob) - return 0; - - git_error_set(GIT_ERROR_INVALID, "object is not a committish"); - return error; - } - if (error < 0) - return error; - - git_oid_cpy(&commit_id, git_object_id(obj)); - git_object_free(obj); - - commit = git_revwalk__commit_lookup(walk, &commit_id); - if (commit == NULL) - return -1; /* error already reported by failed lookup */ - - /* A previous hide already told us we don't want this commit */ - if (commit->uninteresting) - return 0; - - if (opts->uninteresting) { - walk->limited = 1; - walk->did_hide = 1; - } else { - walk->did_push = 1; - } - - commit->uninteresting = opts->uninteresting; - list = walk->user_input; - if ((opts->insert_by_date && - git_commit_list_insert_by_date(commit, &list) == NULL) || - git_commit_list_insert(commit, &list) == NULL) { - git_error_set_oom(); - return -1; - } - - walk->user_input = list; - - return 0; -} - -int git_revwalk_push(git_revwalk *walk, const git_oid *oid) -{ - git_revwalk__push_options opts = GIT_REVWALK__PUSH_OPTIONS_INIT; - - GIT_ASSERT_ARG(walk); - GIT_ASSERT_ARG(oid); - - return git_revwalk__push_commit(walk, oid, &opts); -} - - -int git_revwalk_hide(git_revwalk *walk, const git_oid *oid) -{ - git_revwalk__push_options opts = GIT_REVWALK__PUSH_OPTIONS_INIT; - - GIT_ASSERT_ARG(walk); - GIT_ASSERT_ARG(oid); - - opts.uninteresting = 1; - return git_revwalk__push_commit(walk, oid, &opts); -} - -int git_revwalk__push_ref(git_revwalk *walk, const char *refname, const git_revwalk__push_options *opts) -{ - git_oid oid; - - if (git_reference_name_to_id(&oid, walk->repo, refname) < 0) - return -1; - - return git_revwalk__push_commit(walk, &oid, opts); -} - -int git_revwalk__push_glob(git_revwalk *walk, const char *glob, const git_revwalk__push_options *given_opts) -{ - git_revwalk__push_options opts = GIT_REVWALK__PUSH_OPTIONS_INIT; - int error = 0; - git_buf buf = GIT_BUF_INIT; - git_reference *ref; - git_reference_iterator *iter; - size_t wildcard; - - GIT_ASSERT_ARG(walk); - GIT_ASSERT_ARG(glob); - - if (given_opts) - memcpy(&opts, given_opts, sizeof(opts)); - - /* refs/ is implied if not given in the glob */ - if (git__prefixcmp(glob, GIT_REFS_DIR) != 0) - git_buf_joinpath(&buf, GIT_REFS_DIR, glob); - else - git_buf_puts(&buf, glob); - GIT_ERROR_CHECK_ALLOC_BUF(&buf); - - /* If no '?', '*' or '[' exist, we append '/ *' to the glob */ - wildcard = strcspn(glob, "?*["); - if (!glob[wildcard]) - git_buf_put(&buf, "/*", 2); - - if ((error = git_reference_iterator_glob_new(&iter, walk->repo, buf.ptr)) < 0) - goto out; - - opts.from_glob = true; - while ((error = git_reference_next(&ref, iter)) == 0) { - error = git_revwalk__push_ref(walk, git_reference_name(ref), &opts); - git_reference_free(ref); - if (error < 0) - break; - } - git_reference_iterator_free(iter); - - if (error == GIT_ITEROVER) - error = 0; -out: - git_buf_dispose(&buf); - return error; -} - -int git_revwalk_push_glob(git_revwalk *walk, const char *glob) -{ - git_revwalk__push_options opts = GIT_REVWALK__PUSH_OPTIONS_INIT; - - GIT_ASSERT_ARG(walk); - GIT_ASSERT_ARG(glob); - - return git_revwalk__push_glob(walk, glob, &opts); -} - -int git_revwalk_hide_glob(git_revwalk *walk, const char *glob) -{ - git_revwalk__push_options opts = GIT_REVWALK__PUSH_OPTIONS_INIT; - - GIT_ASSERT_ARG(walk); - GIT_ASSERT_ARG(glob); - - opts.uninteresting = 1; - return git_revwalk__push_glob(walk, glob, &opts); -} - -int git_revwalk_push_head(git_revwalk *walk) -{ - git_revwalk__push_options opts = GIT_REVWALK__PUSH_OPTIONS_INIT; - - GIT_ASSERT_ARG(walk); - - return git_revwalk__push_ref(walk, GIT_HEAD_FILE, &opts); -} - -int git_revwalk_hide_head(git_revwalk *walk) -{ - git_revwalk__push_options opts = GIT_REVWALK__PUSH_OPTIONS_INIT; - - GIT_ASSERT_ARG(walk); - - opts.uninteresting = 1; - return git_revwalk__push_ref(walk, GIT_HEAD_FILE, &opts); -} - -int git_revwalk_push_ref(git_revwalk *walk, const char *refname) -{ - git_revwalk__push_options opts = GIT_REVWALK__PUSH_OPTIONS_INIT; - - GIT_ASSERT_ARG(walk); - GIT_ASSERT_ARG(refname); - - return git_revwalk__push_ref(walk, refname, &opts); -} - -int git_revwalk_push_range(git_revwalk *walk, const char *range) -{ - git_revwalk__push_options opts = GIT_REVWALK__PUSH_OPTIONS_INIT; - git_revspec revspec; - int error = 0; - - if ((error = git_revparse(&revspec, walk->repo, range))) - return error; - - if (!revspec.to) { - git_error_set(GIT_ERROR_INVALID, "invalid revspec: range not provided"); - error = GIT_EINVALIDSPEC; - goto out; - } - - if (revspec.flags & GIT_REVSPEC_MERGE_BASE) { - /* TODO: support "<commit>...<commit>" */ - git_error_set(GIT_ERROR_INVALID, "symmetric differences not implemented in revwalk"); - error = GIT_EINVALIDSPEC; - goto out; - } - - opts.uninteresting = 1; - if ((error = git_revwalk__push_commit(walk, git_object_id(revspec.from), &opts))) - goto out; - - opts.uninteresting = 0; - error = git_revwalk__push_commit(walk, git_object_id(revspec.to), &opts); - -out: - git_object_free(revspec.from); - git_object_free(revspec.to); - return error; -} - -int git_revwalk_hide_ref(git_revwalk *walk, const char *refname) -{ - git_revwalk__push_options opts = GIT_REVWALK__PUSH_OPTIONS_INIT; - - GIT_ASSERT_ARG(walk); - GIT_ASSERT_ARG(refname); - - opts.uninteresting = 1; - return git_revwalk__push_ref(walk, refname, &opts); -} - -static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit) -{ - return git_pqueue_insert(&walk->iterator_time, commit); -} - -static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit) -{ - return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1; -} - -static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk) -{ - git_commit_list_node *next; - - while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) { - /* Some commits might become uninteresting after being added to the list */ - if (!next->uninteresting) { - *object_out = next; - return 0; - } - } - - git_error_clear(); - return GIT_ITEROVER; -} - -static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk) -{ - int error; - git_commit_list_node *next; - - while (!(error = get_revision(&next, walk, &walk->iterator_rand))) { - /* Some commits might become uninteresting after being added to the list */ - if (!next->uninteresting) { - *object_out = next; - return 0; - } - } - - return error; -} - -static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk) -{ - int error; - git_commit_list_node *next; - - while (!(error = get_revision(&next, walk, &walk->iterator_topo))) { - /* Some commits might become uninteresting after being added to the list */ - if (!next->uninteresting) { - *object_out = next; - return 0; - } - } - - return error; -} - -static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk) -{ - *object_out = git_commit_list_pop(&walk->iterator_reverse); - return *object_out ? 0 : GIT_ITEROVER; -} - -static void mark_parents_uninteresting(git_commit_list_node *commit) -{ - unsigned short i; - git_commit_list *parents = NULL; - - for (i = 0; i < commit->out_degree; i++) - git_commit_list_insert(commit->parents[i], &parents); - - - while (parents) { - commit = git_commit_list_pop(&parents); - - while (commit) { - if (commit->uninteresting) - break; - - commit->uninteresting = 1; - /* - * If we've reached this commit some other way - * already, we need to mark its parents uninteresting - * as well. - */ - if (!commit->parents) - break; - - for (i = 0; i < commit->out_degree; i++) - git_commit_list_insert(commit->parents[i], &parents); - commit = commit->parents[0]; - } - } -} - -static int add_parents_to_list(git_revwalk *walk, git_commit_list_node *commit, git_commit_list **list) -{ - unsigned short i; - int error; - - if (commit->added) - return 0; - - commit->added = 1; - - /* - * Go full on in the uninteresting case as we want to include - * as many of these as we can. - * - * Usually we haven't parsed the parent of a parent, but if we - * have it we reached it via other means so we want to mark - * its parents recursively too. - */ - if (commit->uninteresting) { - for (i = 0; i < commit->out_degree; i++) { - git_commit_list_node *p = commit->parents[i]; - p->uninteresting = 1; - - /* git does it gently here, but we don't like missing objects */ - if ((error = git_commit_list_parse(walk, p)) < 0) - return error; - - if (p->parents) - mark_parents_uninteresting(p); - - p->seen = 1; - git_commit_list_insert_by_date(p, list); - } - - return 0; - } - - /* - * Now on to what we do if the commit is indeed - * interesting. Here we do want things like first-parent take - * effect as this is what we'll be showing. - */ - for (i = 0; i < commit->out_degree; i++) { - git_commit_list_node *p = commit->parents[i]; - - if ((error = git_commit_list_parse(walk, p)) < 0) - return error; - - if (walk->hide_cb && walk->hide_cb(&p->oid, walk->hide_cb_payload)) - continue; - - if (!p->seen) { - p->seen = 1; - git_commit_list_insert_by_date(p, list); - } - - if (walk->first_parent) - break; - } - return 0; -} - -/* How many unintersting commits we want to look at after we run out of interesting ones */ -#define SLOP 5 - -static int still_interesting(git_commit_list *list, int64_t time, int slop) -{ - /* The empty list is pretty boring */ - if (!list) - return 0; - - /* - * If the destination list has commits with an earlier date than our - * source, we want to reset the slop counter as we're not done. - */ - if (time <= list->item->time) - return SLOP; - - for (; list; list = list->next) { - /* - * If the destination list still contains interesting commits we - * want to continue looking. - */ - if (!list->item->uninteresting || list->item->time > time) - return SLOP; - } - - /* Everything's uninteresting, reduce the count */ - return slop - 1; -} - -static int limit_list(git_commit_list **out, git_revwalk *walk, git_commit_list *commits) -{ - int error, slop = SLOP; - int64_t time = INT64_MAX; - git_commit_list *list = commits; - git_commit_list *newlist = NULL; - git_commit_list **p = &newlist; - - while (list) { - git_commit_list_node *commit = git_commit_list_pop(&list); - - if ((error = add_parents_to_list(walk, commit, &list)) < 0) - return error; - - if (commit->uninteresting) { - mark_parents_uninteresting(commit); - - slop = still_interesting(list, time, slop); - if (slop) - continue; - - break; - } - - if (walk->hide_cb && walk->hide_cb(&commit->oid, walk->hide_cb_payload)) - continue; - - time = commit->time; - p = &git_commit_list_insert(commit, p)->next; - } - - git_commit_list_free(&list); - *out = newlist; - return 0; -} - -static int get_revision(git_commit_list_node **out, git_revwalk *walk, git_commit_list **list) -{ - int error; - git_commit_list_node *commit; - - commit = git_commit_list_pop(list); - if (!commit) { - git_error_clear(); - return GIT_ITEROVER; - } - - /* - * If we did not run limit_list and we must add parents to the - * list ourselves. - */ - if (!walk->limited) { - if ((error = add_parents_to_list(walk, commit, list)) < 0) - return error; - } - - *out = commit; - return 0; -} - -static int sort_in_topological_order(git_commit_list **out, git_revwalk *walk, git_commit_list *list) -{ - git_commit_list *ll = NULL, *newlist, **pptr; - git_commit_list_node *next; - git_pqueue queue; - git_vector_cmp queue_cmp = NULL; - unsigned short i; - int error; - - if (walk->sorting & GIT_SORT_TIME) - queue_cmp = git_commit_list_time_cmp; - - if ((error = git_pqueue_init(&queue, 0, 8, queue_cmp))) - return error; - - /* - * Start by resetting the in-degree to 1 for the commits in - * our list. We want to go through this list again, so we - * store it in the commit list as we extract it from the lower - * machinery. - */ - for (ll = list; ll; ll = ll->next) { - ll->item->in_degree = 1; - } - - /* - * Count up how many children each commit has. We limit - * ourselves to those commits in the original list (in-degree - * of 1) avoiding setting it for any parent that was hidden. - */ - for(ll = list; ll; ll = ll->next) { - for (i = 0; i < ll->item->out_degree; ++i) { - git_commit_list_node *parent = ll->item->parents[i]; - if (parent->in_degree) - parent->in_degree++; - } - } - - /* - * Now we find the tips i.e. those not reachable from any other node - * i.e. those which still have an in-degree of 1. - */ - for(ll = list; ll; ll = ll->next) { - if (ll->item->in_degree == 1) { - if ((error = git_pqueue_insert(&queue, ll->item))) - goto cleanup; - } - } - - /* - * We need to output the tips in the order that they came out of the - * traversal, so if we're not doing time-sorting, we need to reverse the - * pqueue in order to get them to come out as we inserted them. - */ - if ((walk->sorting & GIT_SORT_TIME) == 0) - git_pqueue_reverse(&queue); - - - pptr = &newlist; - newlist = NULL; - while ((next = git_pqueue_pop(&queue)) != NULL) { - for (i = 0; i < next->out_degree; ++i) { - git_commit_list_node *parent = next->parents[i]; - if (parent->in_degree == 0) - continue; - - if (--parent->in_degree == 1) { - if ((error = git_pqueue_insert(&queue, parent))) - goto cleanup; - } - } - - /* All the children of 'item' have been emitted (since we got to it via the priority queue) */ - next->in_degree = 0; - - pptr = &git_commit_list_insert(next, pptr)->next; - } - - *out = newlist; - error = 0; - -cleanup: - git_pqueue_free(&queue); - return error; -} - -static int prepare_walk(git_revwalk *walk) -{ - int error = 0; - git_commit_list *list, *commits = NULL; - git_commit_list_node *next; - - /* If there were no pushes, we know that the walk is already over */ - if (!walk->did_push) { - git_error_clear(); - return GIT_ITEROVER; - } - - for (list = walk->user_input; list; list = list->next) { - git_commit_list_node *commit = list->item; - if ((error = git_commit_list_parse(walk, commit)) < 0) - return error; - - if (commit->uninteresting) - mark_parents_uninteresting(commit); - - if (!commit->seen) { - commit->seen = 1; - git_commit_list_insert(commit, &commits); - } - } - - if (walk->limited && (error = limit_list(&commits, walk, commits)) < 0) - return error; - - if (walk->sorting & GIT_SORT_TOPOLOGICAL) { - error = sort_in_topological_order(&walk->iterator_topo, walk, commits); - git_commit_list_free(&commits); - - if (error < 0) - return error; - - walk->get_next = &revwalk_next_toposort; - } else if (walk->sorting & GIT_SORT_TIME) { - for (list = commits; list && !error; list = list->next) - error = walk->enqueue(walk, list->item); - - git_commit_list_free(&commits); - - if (error < 0) - return error; - } else { - walk->iterator_rand = commits; - walk->get_next = revwalk_next_unsorted; - } - - if (walk->sorting & GIT_SORT_REVERSE) { - - while ((error = walk->get_next(&next, walk)) == 0) - if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL) - return -1; - - if (error != GIT_ITEROVER) - return error; - - walk->get_next = &revwalk_next_reverse; - } - - walk->walking = 1; - return 0; -} - - -int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo) -{ - git_revwalk *walk = git__calloc(1, sizeof(git_revwalk)); - GIT_ERROR_CHECK_ALLOC(walk); - - if (git_oidmap_new(&walk->commits) < 0 || - git_pqueue_init(&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0 || - git_pool_init(&walk->commit_pool, COMMIT_ALLOC) < 0) - return -1; - - walk->get_next = &revwalk_next_unsorted; - walk->enqueue = &revwalk_enqueue_unsorted; - - walk->repo = repo; - - if (git_repository_odb(&walk->odb, repo) < 0) { - git_revwalk_free(walk); - return -1; - } - - *revwalk_out = walk; - return 0; -} - -void git_revwalk_free(git_revwalk *walk) -{ - if (walk == NULL) - return; - - git_revwalk_reset(walk); - git_odb_free(walk->odb); - - git_oidmap_free(walk->commits); - git_pool_clear(&walk->commit_pool); - git_pqueue_free(&walk->iterator_time); - git__free(walk); -} - -git_repository *git_revwalk_repository(git_revwalk *walk) -{ - GIT_ASSERT_ARG_WITH_RETVAL(walk, NULL); - - return walk->repo; -} - -int git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode) -{ - GIT_ASSERT_ARG(walk); - - if (walk->walking) - git_revwalk_reset(walk); - - walk->sorting = sort_mode; - - if (walk->sorting & GIT_SORT_TIME) { - walk->get_next = &revwalk_next_timesort; - walk->enqueue = &revwalk_enqueue_timesort; - } else { - walk->get_next = &revwalk_next_unsorted; - walk->enqueue = &revwalk_enqueue_unsorted; - } - - if (walk->sorting != GIT_SORT_NONE) - walk->limited = 1; - - return 0; -} - -int git_revwalk_simplify_first_parent(git_revwalk *walk) -{ - walk->first_parent = 1; - return 0; -} - -int git_revwalk_next(git_oid *oid, git_revwalk *walk) -{ - int error; - git_commit_list_node *next; - - GIT_ASSERT_ARG(walk); - GIT_ASSERT_ARG(oid); - - if (!walk->walking) { - if ((error = prepare_walk(walk)) < 0) - return error; - } - - error = walk->get_next(&next, walk); - - if (error == GIT_ITEROVER) { - git_revwalk_reset(walk); - git_error_clear(); - return GIT_ITEROVER; - } - - if (!error) - git_oid_cpy(oid, &next->oid); - - return error; -} - -int git_revwalk_reset(git_revwalk *walk) -{ - git_commit_list_node *commit; - - GIT_ASSERT_ARG(walk); - - git_oidmap_foreach_value(walk->commits, commit, { - commit->seen = 0; - commit->in_degree = 0; - commit->topo_delay = 0; - commit->uninteresting = 0; - commit->added = 0; - commit->flags = 0; - }); - - git_pqueue_clear(&walk->iterator_time); - git_commit_list_free(&walk->iterator_topo); - git_commit_list_free(&walk->iterator_rand); - git_commit_list_free(&walk->iterator_reverse); - git_commit_list_free(&walk->user_input); - walk->first_parent = 0; - walk->walking = 0; - walk->limited = 0; - walk->did_push = walk->did_hide = 0; - walk->sorting = GIT_SORT_NONE; - - return 0; -} - -int git_revwalk_add_hide_cb( - git_revwalk *walk, - git_revwalk_hide_cb hide_cb, - void *payload) -{ - GIT_ASSERT_ARG(walk); - - if (walk->walking) - git_revwalk_reset(walk); - - walk->hide_cb = hide_cb; - walk->hide_cb_payload = payload; - - if (hide_cb) - walk->limited = 1; - - return 0; -} - |