diff options
Diffstat (limited to 'refs/iterator.c')
| -rw-r--r-- | refs/iterator.c | 490 |
1 files changed, 490 insertions, 0 deletions
diff --git a/refs/iterator.c b/refs/iterator.c new file mode 100644 index 0000000000..17ef841d8a --- /dev/null +++ b/refs/iterator.c @@ -0,0 +1,490 @@ +/* + * Generic reference iterator infrastructure. See refs-internal.h for + * documentation about the design and use of reference iterators. + */ + +#define DISABLE_SIGN_COMPARE_WARNINGS + +#include "git-compat-util.h" +#include "refs.h" +#include "refs/refs-internal.h" +#include "iterator.h" + +int ref_iterator_advance(struct ref_iterator *ref_iterator) +{ + return ref_iterator->vtable->advance(ref_iterator); +} + +int ref_iterator_seek(struct ref_iterator *ref_iterator, const char *refname, + unsigned int flags) +{ + return ref_iterator->vtable->seek(ref_iterator, refname, flags); +} + +int ref_iterator_peel(struct ref_iterator *ref_iterator, + struct object_id *peeled) +{ + return ref_iterator->vtable->peel(ref_iterator, peeled); +} + +void ref_iterator_free(struct ref_iterator *ref_iterator) +{ + if (ref_iterator) { + ref_iterator->vtable->release(ref_iterator); + /* Help make use-after-free bugs fail quickly: */ + ref_iterator->vtable = NULL; + free(ref_iterator); + } +} + +void base_ref_iterator_init(struct ref_iterator *iter, + struct ref_iterator_vtable *vtable) +{ + iter->vtable = vtable; + iter->refname = NULL; + iter->referent = NULL; + iter->oid = NULL; + iter->flags = 0; +} + +struct empty_ref_iterator { + struct ref_iterator base; +}; + +static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator UNUSED) +{ + return ITER_DONE; +} + +static int empty_ref_iterator_seek(struct ref_iterator *ref_iterator UNUSED, + const char *refname UNUSED, + unsigned int flags UNUSED) +{ + return 0; +} + +static int empty_ref_iterator_peel(struct ref_iterator *ref_iterator UNUSED, + struct object_id *peeled UNUSED) +{ + BUG("peel called for empty iterator"); +} + +static void empty_ref_iterator_release(struct ref_iterator *ref_iterator UNUSED) +{ +} + +static struct ref_iterator_vtable empty_ref_iterator_vtable = { + .advance = empty_ref_iterator_advance, + .seek = empty_ref_iterator_seek, + .peel = empty_ref_iterator_peel, + .release = empty_ref_iterator_release, +}; + +struct ref_iterator *empty_ref_iterator_begin(void) +{ + struct empty_ref_iterator *iter = xcalloc(1, sizeof(*iter)); + struct ref_iterator *ref_iterator = &iter->base; + + base_ref_iterator_init(ref_iterator, &empty_ref_iterator_vtable); + return ref_iterator; +} + +int is_empty_ref_iterator(struct ref_iterator *ref_iterator) +{ + return ref_iterator->vtable == &empty_ref_iterator_vtable; +} + +struct merge_ref_iterator { + struct ref_iterator base; + + struct ref_iterator *iter0, *iter0_owned; + struct ref_iterator *iter1, *iter1_owned; + + ref_iterator_select_fn *select; + void *cb_data; + + /* + * A pointer to iter0 or iter1 (whichever is supplying the + * current value), or NULL if advance has not yet been called. + */ + struct ref_iterator **current; +}; + +enum iterator_selection ref_iterator_select(struct ref_iterator *iter_worktree, + struct ref_iterator *iter_common, + void *cb_data UNUSED) +{ + if (iter_worktree && !iter_common) { + /* + * Return the worktree ref if there are no more common refs. + */ + return ITER_SELECT_0; + } else if (iter_common) { + /* + * In case we have pending worktree and common refs we need to + * yield them based on their lexicographical order. Worktree + * refs that have the same name as common refs shadow the + * latter. + */ + if (iter_worktree) { + int cmp = strcmp(iter_worktree->refname, + iter_common->refname); + if (cmp < 0) + return ITER_SELECT_0; + else if (!cmp) + return ITER_SELECT_0_SKIP_1; + } + + /* + * We now know that the lexicographically-next ref is a common + * ref. When the common ref is a shared one we return it. + */ + if (parse_worktree_ref(iter_common->refname, NULL, NULL, + NULL) == REF_WORKTREE_SHARED) + return ITER_SELECT_1; + + /* + * Otherwise, if the common ref is a per-worktree ref we skip + * it because it would belong to the main worktree, not ours. + */ + return ITER_SKIP_1; + } else { + return ITER_DONE; + } +} + +static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) +{ + struct merge_ref_iterator *iter = + (struct merge_ref_iterator *)ref_iterator; + int ok; + + if (!iter->current) { + /* Initialize: advance both iterators to their first entries */ + if ((ok = ref_iterator_advance(iter->iter0)) != ITER_OK) { + iter->iter0 = NULL; + if (ok == ITER_ERROR) + goto error; + } + if ((ok = ref_iterator_advance(iter->iter1)) != ITER_OK) { + iter->iter1 = NULL; + if (ok == ITER_ERROR) + goto error; + } + } else { + /* + * Advance the current iterator past the just-used + * entry: + */ + if ((ok = ref_iterator_advance(*iter->current)) != ITER_OK) { + *iter->current = NULL; + if (ok == ITER_ERROR) + goto error; + } + } + + /* Loop until we find an entry that we can yield. */ + while (1) { + struct ref_iterator **secondary; + enum iterator_selection selection = + iter->select(iter->iter0, iter->iter1, iter->cb_data); + + if (selection == ITER_SELECT_DONE) { + return ITER_DONE; + } else if (selection == ITER_SELECT_ERROR) { + return ITER_ERROR; + } + + if ((selection & ITER_CURRENT_SELECTION_MASK) == 0) { + iter->current = &iter->iter0; + secondary = &iter->iter1; + } else { + iter->current = &iter->iter1; + secondary = &iter->iter0; + } + + if (selection & ITER_SKIP_SECONDARY) { + if ((ok = ref_iterator_advance(*secondary)) != ITER_OK) { + *secondary = NULL; + if (ok == ITER_ERROR) + goto error; + } + } + + if (selection & ITER_YIELD_CURRENT) { + iter->base.referent = (*iter->current)->referent; + iter->base.refname = (*iter->current)->refname; + iter->base.oid = (*iter->current)->oid; + iter->base.flags = (*iter->current)->flags; + return ITER_OK; + } + } + +error: + return ITER_ERROR; +} + +static int merge_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *refname, unsigned int flags) +{ + struct merge_ref_iterator *iter = + (struct merge_ref_iterator *)ref_iterator; + int ret; + + iter->current = NULL; + iter->iter0 = iter->iter0_owned; + iter->iter1 = iter->iter1_owned; + + ret = ref_iterator_seek(iter->iter0, refname, flags); + if (ret < 0) + return ret; + + ret = ref_iterator_seek(iter->iter1, refname, flags); + if (ret < 0) + return ret; + + return 0; +} + +static int merge_ref_iterator_peel(struct ref_iterator *ref_iterator, + struct object_id *peeled) +{ + struct merge_ref_iterator *iter = + (struct merge_ref_iterator *)ref_iterator; + + if (!iter->current) { + BUG("peel called before advance for merge iterator"); + } + return ref_iterator_peel(*iter->current, peeled); +} + +static void merge_ref_iterator_release(struct ref_iterator *ref_iterator) +{ + struct merge_ref_iterator *iter = + (struct merge_ref_iterator *)ref_iterator; + ref_iterator_free(iter->iter0_owned); + ref_iterator_free(iter->iter1_owned); +} + +static struct ref_iterator_vtable merge_ref_iterator_vtable = { + .advance = merge_ref_iterator_advance, + .seek = merge_ref_iterator_seek, + .peel = merge_ref_iterator_peel, + .release = merge_ref_iterator_release, +}; + +struct ref_iterator *merge_ref_iterator_begin( + struct ref_iterator *iter0, struct ref_iterator *iter1, + ref_iterator_select_fn *select, void *cb_data) +{ + struct merge_ref_iterator *iter = xcalloc(1, sizeof(*iter)); + struct ref_iterator *ref_iterator = &iter->base; + + /* + * We can't do the same kind of is_empty_ref_iterator()-style + * optimization here as overlay_ref_iterator_begin() does, + * because we don't know the semantics of the select function. + * It might, for example, implement "intersect" by passing + * references through only if they exist in both iterators. + */ + + base_ref_iterator_init(ref_iterator, &merge_ref_iterator_vtable); + iter->iter0 = iter->iter0_owned = iter0; + iter->iter1 = iter->iter1_owned = iter1; + iter->select = select; + iter->cb_data = cb_data; + iter->current = NULL; + return ref_iterator; +} + +/* + * A ref_iterator_select_fn that overlays the items from front on top + * of those from back (like loose refs over packed refs). See + * overlay_ref_iterator_begin(). + */ +static enum iterator_selection overlay_iterator_select( + struct ref_iterator *front, struct ref_iterator *back, + void *cb_data UNUSED) +{ + int cmp; + + if (!back) + return front ? ITER_SELECT_0 : ITER_SELECT_DONE; + else if (!front) + return ITER_SELECT_1; + + cmp = strcmp(front->refname, back->refname); + + if (cmp < 0) + return ITER_SELECT_0; + else if (cmp > 0) + return ITER_SELECT_1; + else + return ITER_SELECT_0_SKIP_1; +} + +struct ref_iterator *overlay_ref_iterator_begin( + struct ref_iterator *front, struct ref_iterator *back) +{ + /* + * Optimization: if one of the iterators is empty, return the + * other one rather than incurring the overhead of wrapping + * them. + */ + if (is_empty_ref_iterator(front)) { + ref_iterator_free(front); + return back; + } else if (is_empty_ref_iterator(back)) { + ref_iterator_free(back); + return front; + } + + return merge_ref_iterator_begin(front, back, overlay_iterator_select, NULL); +} + +struct prefix_ref_iterator { + struct ref_iterator base; + + struct ref_iterator *iter0; + char *prefix; + int trim; +}; + +/* Return -1, 0, 1 if refname is before, inside, or after the prefix. */ +static int compare_prefix(const char *refname, const char *prefix) +{ + while (*prefix) { + if (*refname != *prefix) + return ((unsigned char)*refname < (unsigned char)*prefix) ? -1 : +1; + + refname++; + prefix++; + } + + return 0; +} + +static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator) +{ + struct prefix_ref_iterator *iter = + (struct prefix_ref_iterator *)ref_iterator; + int ok; + + while ((ok = ref_iterator_advance(iter->iter0)) == ITER_OK) { + int cmp = compare_prefix(iter->iter0->refname, iter->prefix); + if (cmp < 0) + continue; + /* + * As the source iterator is ordered, we + * can stop the iteration as soon as we see a + * refname that comes after the prefix: + */ + if (cmp > 0) + return ITER_DONE; + + if (iter->trim) { + /* + * It is nonsense to trim off characters that + * you haven't already checked for via a + * prefix check, whether via this + * `prefix_ref_iterator` or upstream in + * `iter0`). So if there wouldn't be at least + * one character left in the refname after + * trimming, report it as a bug: + */ + if (strlen(iter->iter0->refname) <= iter->trim) + BUG("attempt to trim too many characters"); + iter->base.refname = iter->iter0->refname + iter->trim; + } else { + iter->base.refname = iter->iter0->refname; + } + + iter->base.oid = iter->iter0->oid; + iter->base.flags = iter->iter0->flags; + return ITER_OK; + } + + return ok; +} + +static int prefix_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *refname, unsigned int flags) +{ + struct prefix_ref_iterator *iter = + (struct prefix_ref_iterator *)ref_iterator; + + if (flags & REF_ITERATOR_SEEK_SET_PREFIX) { + free(iter->prefix); + iter->prefix = xstrdup_or_null(refname); + } + return ref_iterator_seek(iter->iter0, refname, flags); +} + +static int prefix_ref_iterator_peel(struct ref_iterator *ref_iterator, + struct object_id *peeled) +{ + struct prefix_ref_iterator *iter = + (struct prefix_ref_iterator *)ref_iterator; + + return ref_iterator_peel(iter->iter0, peeled); +} + +static void prefix_ref_iterator_release(struct ref_iterator *ref_iterator) +{ + struct prefix_ref_iterator *iter = + (struct prefix_ref_iterator *)ref_iterator; + ref_iterator_free(iter->iter0); + free(iter->prefix); +} + +static struct ref_iterator_vtable prefix_ref_iterator_vtable = { + .advance = prefix_ref_iterator_advance, + .seek = prefix_ref_iterator_seek, + .peel = prefix_ref_iterator_peel, + .release = prefix_ref_iterator_release, +}; + +struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0, + const char *prefix, + int trim) +{ + struct prefix_ref_iterator *iter; + struct ref_iterator *ref_iterator; + + if (!*prefix && !trim) + return iter0; /* optimization: no need to wrap iterator */ + + CALLOC_ARRAY(iter, 1); + ref_iterator = &iter->base; + + base_ref_iterator_init(ref_iterator, &prefix_ref_iterator_vtable); + + iter->iter0 = iter0; + iter->prefix = xstrdup(prefix); + iter->trim = trim; + + return ref_iterator; +} + +struct ref_iterator *current_ref_iter = NULL; + +int do_for_each_ref_iterator(struct ref_iterator *iter, + each_ref_fn fn, void *cb_data) +{ + int retval = 0, ok; + struct ref_iterator *old_ref_iter = current_ref_iter; + + current_ref_iter = iter; + while ((ok = ref_iterator_advance(iter)) == ITER_OK) { + retval = fn(iter->refname, iter->referent, iter->oid, iter->flags, cb_data); + if (retval) + goto out; + } + +out: + current_ref_iter = old_ref_iter; + if (ok == ITER_ERROR) + retval = -1; + ref_iterator_free(iter); + return retval; +} |