Andrew's git / gitweb.git / refs/iterator.c
?
refs / iterator.con commit ref_iterator: keep track of whether the iterator output is ordered (8738a8a)
   1/*
   2 * Generic reference iterator infrastructure. See refs-internal.h for
   3 * documentation about the design and use of reference iterators.
   4 */
   5
   6#include "cache.h"
   7#include "refs.h"
   8#include "refs/refs-internal.h"
   9#include "iterator.h"
  10
  11int ref_iterator_advance(struct ref_iterator *ref_iterator)
  12{
  13        return ref_iterator->vtable->advance(ref_iterator);
  14}
  15
  16int ref_iterator_peel(struct ref_iterator *ref_iterator,
  17                      struct object_id *peeled)
  18{
  19        return ref_iterator->vtable->peel(ref_iterator, peeled);
  20}
  21
  22int ref_iterator_abort(struct ref_iterator *ref_iterator)
  23{
  24        return ref_iterator->vtable->abort(ref_iterator);
  25}
  26
  27void base_ref_iterator_init(struct ref_iterator *iter,
  28                            struct ref_iterator_vtable *vtable,
  29                            int ordered)
  30{
  31        iter->vtable = vtable;
  32        iter->ordered = !!ordered;
  33        iter->refname = NULL;
  34        iter->oid = NULL;
  35        iter->flags = 0;
  36}
  37
  38void base_ref_iterator_free(struct ref_iterator *iter)
  39{
  40        /* Help make use-after-free bugs fail quickly: */
  41        iter->vtable = NULL;
  42        free(iter);
  43}
  44
  45struct empty_ref_iterator {
  46        struct ref_iterator base;
  47};
  48
  49static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator)
  50{
  51        return ref_iterator_abort(ref_iterator);
  52}
  53
  54static int empty_ref_iterator_peel(struct ref_iterator *ref_iterator,
  55                                   struct object_id *peeled)
  56{
  57        die("BUG: peel called for empty iterator");
  58}
  59
  60static int empty_ref_iterator_abort(struct ref_iterator *ref_iterator)
  61{
  62        base_ref_iterator_free(ref_iterator);
  63        return ITER_DONE;
  64}
  65
  66static struct ref_iterator_vtable empty_ref_iterator_vtable = {
  67        empty_ref_iterator_advance,
  68        empty_ref_iterator_peel,
  69        empty_ref_iterator_abort
  70};
  71
  72struct ref_iterator *empty_ref_iterator_begin(void)
  73{
  74        struct empty_ref_iterator *iter = xcalloc(1, sizeof(*iter));
  75        struct ref_iterator *ref_iterator = &iter->base;
  76
  77        base_ref_iterator_init(ref_iterator, &empty_ref_iterator_vtable, 1);
  78        return ref_iterator;
  79}
  80
  81int is_empty_ref_iterator(struct ref_iterator *ref_iterator)
  82{
  83        return ref_iterator->vtable == &empty_ref_iterator_vtable;
  84}
  85
  86struct merge_ref_iterator {
  87        struct ref_iterator base;
  88
  89        struct ref_iterator *iter0, *iter1;
  90
  91        ref_iterator_select_fn *select;
  92        void *cb_data;
  93
  94        /*
  95         * A pointer to iter0 or iter1 (whichever is supplying the
  96         * current value), or NULL if advance has not yet been called.
  97         */
  98        struct ref_iterator **current;
  99};
 100
 101static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator)
 102{
 103        struct merge_ref_iterator *iter =
 104                (struct merge_ref_iterator *)ref_iterator;
 105        int ok;
 106
 107        if (!iter->current) {
 108                /* Initialize: advance both iterators to their first entries */
 109                if ((ok = ref_iterator_advance(iter->iter0)) != ITER_OK) {
 110                        iter->iter0 = NULL;
 111                        if (ok == ITER_ERROR)
 112                                goto error;
 113                }
 114                if ((ok = ref_iterator_advance(iter->iter1)) != ITER_OK) {
 115                        iter->iter1 = NULL;
 116                        if (ok == ITER_ERROR)
 117                                goto error;
 118                }
 119        } else {
 120                /*
 121                 * Advance the current iterator past the just-used
 122                 * entry:
 123                 */
 124                if ((ok = ref_iterator_advance(*iter->current)) != ITER_OK) {
 125                        *iter->current = NULL;
 126                        if (ok == ITER_ERROR)
 127                                goto error;
 128                }
 129        }
 130
 131        /* Loop until we find an entry that we can yield. */
 132        while (1) {
 133                struct ref_iterator **secondary;
 134                enum iterator_selection selection =
 135                        iter->select(iter->iter0, iter->iter1, iter->cb_data);
 136
 137                if (selection == ITER_SELECT_DONE) {
 138                        return ref_iterator_abort(ref_iterator);
 139                } else if (selection == ITER_SELECT_ERROR) {
 140                        ref_iterator_abort(ref_iterator);
 141                        return ITER_ERROR;
 142                }
 143
 144                if ((selection & ITER_CURRENT_SELECTION_MASK) == 0) {
 145                        iter->current = &iter->iter0;
 146                        secondary = &iter->iter1;
 147                } else {
 148                        iter->current = &iter->iter1;
 149                        secondary = &iter->iter0;
 150                }
 151
 152                if (selection & ITER_SKIP_SECONDARY) {
 153                        if ((ok = ref_iterator_advance(*secondary)) != ITER_OK) {
 154                                *secondary = NULL;
 155                                if (ok == ITER_ERROR)
 156                                        goto error;
 157                        }
 158                }
 159
 160                if (selection & ITER_YIELD_CURRENT) {
 161                        iter->base.refname = (*iter->current)->refname;
 162                        iter->base.oid = (*iter->current)->oid;
 163                        iter->base.flags = (*iter->current)->flags;
 164                        return ITER_OK;
 165                }
 166        }
 167
 168error:
 169        ref_iterator_abort(ref_iterator);
 170        return ITER_ERROR;
 171}
 172
 173static int merge_ref_iterator_peel(struct ref_iterator *ref_iterator,
 174                                   struct object_id *peeled)
 175{
 176        struct merge_ref_iterator *iter =
 177                (struct merge_ref_iterator *)ref_iterator;
 178
 179        if (!iter->current) {
 180                die("BUG: peel called before advance for merge iterator");
 181        }
 182        return ref_iterator_peel(*iter->current, peeled);
 183}
 184
 185static int merge_ref_iterator_abort(struct ref_iterator *ref_iterator)
 186{
 187        struct merge_ref_iterator *iter =
 188                (struct merge_ref_iterator *)ref_iterator;
 189        int ok = ITER_DONE;
 190
 191        if (iter->iter0) {
 192                if (ref_iterator_abort(iter->iter0) != ITER_DONE)
 193                        ok = ITER_ERROR;
 194        }
 195        if (iter->iter1) {
 196                if (ref_iterator_abort(iter->iter1) != ITER_DONE)
 197                        ok = ITER_ERROR;
 198        }
 199        base_ref_iterator_free(ref_iterator);
 200        return ok;
 201}
 202
 203static struct ref_iterator_vtable merge_ref_iterator_vtable = {
 204        merge_ref_iterator_advance,
 205        merge_ref_iterator_peel,
 206        merge_ref_iterator_abort
 207};
 208
 209struct ref_iterator *merge_ref_iterator_begin(
 210                int ordered,
 211                struct ref_iterator *iter0, struct ref_iterator *iter1,
 212                ref_iterator_select_fn *select, void *cb_data)
 213{
 214        struct merge_ref_iterator *iter = xcalloc(1, sizeof(*iter));
 215        struct ref_iterator *ref_iterator = &iter->base;
 216
 217        /*
 218         * We can't do the same kind of is_empty_ref_iterator()-style
 219         * optimization here as overlay_ref_iterator_begin() does,
 220         * because we don't know the semantics of the select function.
 221         * It might, for example, implement "intersect" by passing
 222         * references through only if they exist in both iterators.
 223         */
 224
 225        base_ref_iterator_init(ref_iterator, &merge_ref_iterator_vtable, ordered);
 226        iter->iter0 = iter0;
 227        iter->iter1 = iter1;
 228        iter->select = select;
 229        iter->cb_data = cb_data;
 230        iter->current = NULL;
 231        return ref_iterator;
 232}
 233
 234/*
 235 * A ref_iterator_select_fn that overlays the items from front on top
 236 * of those from back (like loose refs over packed refs). See
 237 * overlay_ref_iterator_begin().
 238 */
 239static enum iterator_selection overlay_iterator_select(
 240                struct ref_iterator *front, struct ref_iterator *back,
 241                void *cb_data)
 242{
 243        int cmp;
 244
 245        if (!back)
 246                return front ? ITER_SELECT_0 : ITER_SELECT_DONE;
 247        else if (!front)
 248                return ITER_SELECT_1;
 249
 250        cmp = strcmp(front->refname, back->refname);
 251
 252        if (cmp < 0)
 253                return ITER_SELECT_0;
 254        else if (cmp > 0)
 255                return ITER_SELECT_1;
 256        else
 257                return ITER_SELECT_0_SKIP_1;
 258}
 259
 260struct ref_iterator *overlay_ref_iterator_begin(
 261                struct ref_iterator *front, struct ref_iterator *back)
 262{
 263        /*
 264         * Optimization: if one of the iterators is empty, return the
 265         * other one rather than incurring the overhead of wrapping
 266         * them.
 267         */
 268        if (is_empty_ref_iterator(front)) {
 269                ref_iterator_abort(front);
 270                return back;
 271        } else if (is_empty_ref_iterator(back)) {
 272                ref_iterator_abort(back);
 273                return front;
 274        } else if (!front->ordered || !back->ordered) {
 275                BUG("overlay_ref_iterator requires ordered inputs");
 276        }
 277
 278        return merge_ref_iterator_begin(1, front, back,
 279                                        overlay_iterator_select, NULL);
 280}
 281
 282struct prefix_ref_iterator {
 283        struct ref_iterator base;
 284
 285        struct ref_iterator *iter0;
 286        char *prefix;
 287        int trim;
 288};
 289
 290static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator)
 291{
 292        struct prefix_ref_iterator *iter =
 293                (struct prefix_ref_iterator *)ref_iterator;
 294        int ok;
 295
 296        while ((ok = ref_iterator_advance(iter->iter0)) == ITER_OK) {
 297                if (!starts_with(iter->iter0->refname, iter->prefix))
 298                        continue;
 299
 300                if (iter->trim) {
 301                        /*
 302                         * It is nonsense to trim off characters that
 303                         * you haven't already checked for via a
 304                         * prefix check, whether via this
 305                         * `prefix_ref_iterator` or upstream in
 306                         * `iter0`). So if there wouldn't be at least
 307                         * one character left in the refname after
 308                         * trimming, report it as a bug:
 309                         */
 310                        if (strlen(iter->iter0->refname) <= iter->trim)
 311                                die("BUG: attempt to trim too many characters");
 312                        iter->base.refname = iter->iter0->refname + iter->trim;
 313                } else {
 314                        iter->base.refname = iter->iter0->refname;
 315                }
 316
 317                iter->base.oid = iter->iter0->oid;
 318                iter->base.flags = iter->iter0->flags;
 319                return ITER_OK;
 320        }
 321
 322        iter->iter0 = NULL;
 323        if (ref_iterator_abort(ref_iterator) != ITER_DONE)
 324                return ITER_ERROR;
 325        return ok;
 326}
 327
 328static int prefix_ref_iterator_peel(struct ref_iterator *ref_iterator,
 329                                    struct object_id *peeled)
 330{
 331        struct prefix_ref_iterator *iter =
 332                (struct prefix_ref_iterator *)ref_iterator;
 333
 334        return ref_iterator_peel(iter->iter0, peeled);
 335}
 336
 337static int prefix_ref_iterator_abort(struct ref_iterator *ref_iterator)
 338{
 339        struct prefix_ref_iterator *iter =
 340                (struct prefix_ref_iterator *)ref_iterator;
 341        int ok = ITER_DONE;
 342
 343        if (iter->iter0)
 344                ok = ref_iterator_abort(iter->iter0);
 345        free(iter->prefix);
 346        base_ref_iterator_free(ref_iterator);
 347        return ok;
 348}
 349
 350static struct ref_iterator_vtable prefix_ref_iterator_vtable = {
 351        prefix_ref_iterator_advance,
 352        prefix_ref_iterator_peel,
 353        prefix_ref_iterator_abort
 354};
 355
 356struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,
 357                                               const char *prefix,
 358                                               int trim)
 359{
 360        struct prefix_ref_iterator *iter;
 361        struct ref_iterator *ref_iterator;
 362
 363        if (!*prefix && !trim)
 364                return iter0; /* optimization: no need to wrap iterator */
 365
 366        iter = xcalloc(1, sizeof(*iter));
 367        ref_iterator = &iter->base;
 368
 369        base_ref_iterator_init(ref_iterator, &prefix_ref_iterator_vtable, iter0->ordered);
 370
 371        iter->iter0 = iter0;
 372        iter->prefix = xstrdup(prefix);
 373        iter->trim = trim;
 374
 375        return ref_iterator;
 376}
 377
 378struct ref_iterator *current_ref_iter = NULL;
 379
 380int do_for_each_ref_iterator(struct ref_iterator *iter,
 381                             each_ref_fn fn, void *cb_data)
 382{
 383        int retval = 0, ok;
 384        struct ref_iterator *old_ref_iter = current_ref_iter;
 385
 386        current_ref_iter = iter;
 387        while ((ok = ref_iterator_advance(iter)) == ITER_OK) {
 388                retval = fn(iter->refname, iter->oid, iter->flags, cb_data);
 389                if (retval) {
 390                        /*
 391                         * If ref_iterator_abort() returns ITER_ERROR,
 392                         * we ignore that error in deference to the
 393                         * callback function's return value.
 394                         */
 395                        ref_iterator_abort(iter);
 396                        goto out;
 397                }
 398        }
 399
 400out:
 401        current_ref_iter = old_ref_iter;
 402        if (ok == ITER_ERROR)
 403                return -1;
 404        return retval;
 405}