Andrew's git - gitweb.git/blob

   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        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                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
 290/* Return -1, 0, 1 if refname is before, inside, or after the prefix. */
 291static int compare_prefix(const char *refname, const char *prefix)
 292{
 293        while (*prefix) {
 294                if (*refname != *prefix)
 295                        return ((unsigned char)*refname < (unsigned char)*prefix) ? -1 : +1;
 296
 297                refname++;
 298                prefix++;
 299        }
 300
 301        return 0;
 302}
 303
 304static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator)
 305{
 306        struct prefix_ref_iterator *iter =
 307                (struct prefix_ref_iterator *)ref_iterator;
 308        int ok;
 309
 310        while ((ok = ref_iterator_advance(iter->iter0)) == ITER_OK) {
 311                int cmp = compare_prefix(iter->iter0->refname, iter->prefix);
 312
 313                if (cmp < 0)
 314                        continue;
 315
 316                if (cmp > 0) {
 317                        /*
 318                         * If the source iterator is ordered, then we
 319                         * can stop the iteration as soon as we see a
 320                         * refname that comes after the prefix:
 321                         */
 322                        if (iter->iter0->ordered) {
 323                                ok = ref_iterator_abort(iter->iter0);
 324                                break;
 325                        } else {
 326                                continue;
 327                        }
 328                }
 329
 330                if (iter->trim) {
 331                        /*
 332                         * It is nonsense to trim off characters that
 333                         * you haven't already checked for via a
 334                         * prefix check, whether via this
 335                         * `prefix_ref_iterator` or upstream in
 336                         * `iter0`). So if there wouldn't be at least
 337                         * one character left in the refname after
 338                         * trimming, report it as a bug:
 339                         */
 340                        if (strlen(iter->iter0->refname) <= iter->trim)
 341                                BUG("attempt to trim too many characters");
 342                        iter->base.refname = iter->iter0->refname + iter->trim;
 343                } else {
 344                        iter->base.refname = iter->iter0->refname;
 345                }
 346
 347                iter->base.oid = iter->iter0->oid;
 348                iter->base.flags = iter->iter0->flags;
 349                return ITER_OK;
 350        }
 351
 352        iter->iter0 = NULL;
 353        if (ref_iterator_abort(ref_iterator) != ITER_DONE)
 354                return ITER_ERROR;
 355        return ok;
 356}
 357
 358static int prefix_ref_iterator_peel(struct ref_iterator *ref_iterator,
 359                                    struct object_id *peeled)
 360{
 361        struct prefix_ref_iterator *iter =
 362                (struct prefix_ref_iterator *)ref_iterator;
 363
 364        return ref_iterator_peel(iter->iter0, peeled);
 365}
 366
 367static int prefix_ref_iterator_abort(struct ref_iterator *ref_iterator)
 368{
 369        struct prefix_ref_iterator *iter =
 370                (struct prefix_ref_iterator *)ref_iterator;
 371        int ok = ITER_DONE;
 372
 373        if (iter->iter0)
 374                ok = ref_iterator_abort(iter->iter0);
 375        free(iter->prefix);
 376        base_ref_iterator_free(ref_iterator);
 377        return ok;
 378}
 379
 380static struct ref_iterator_vtable prefix_ref_iterator_vtable = {
 381        prefix_ref_iterator_advance,
 382        prefix_ref_iterator_peel,
 383        prefix_ref_iterator_abort
 384};
 385
 386struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,
 387                                               const char *prefix,
 388                                               int trim)
 389{
 390        struct prefix_ref_iterator *iter;
 391        struct ref_iterator *ref_iterator;
 392
 393        if (!*prefix && !trim)
 394                return iter0; /* optimization: no need to wrap iterator */
 395
 396        iter = xcalloc(1, sizeof(*iter));
 397        ref_iterator = &iter->base;
 398
 399        base_ref_iterator_init(ref_iterator, &prefix_ref_iterator_vtable, iter0->ordered);
 400
 401        iter->iter0 = iter0;
 402        iter->prefix = xstrdup(prefix);
 403        iter->trim = trim;
 404
 405        return ref_iterator;
 406}
 407
 408struct ref_iterator *current_ref_iter = NULL;
 409
 410int do_for_each_ref_iterator(struct ref_iterator *iter,
 411                             each_ref_fn fn, void *cb_data)
 412{
 413        int retval = 0, ok;
 414        struct ref_iterator *old_ref_iter = current_ref_iter;
 415
 416        current_ref_iter = iter;
 417        while ((ok = ref_iterator_advance(iter)) == ITER_OK) {
 418                retval = fn(iter->refname, iter->oid, iter->flags, cb_data);
 419                if (retval) {
 420                        /*
 421                         * If ref_iterator_abort() returns ITER_ERROR,
 422                         * we ignore that error in deference to the
 423                         * callback function's return value.
 424                         */
 425                        ref_iterator_abort(iter);
 426                        goto out;
 427                }
 428        }
 429
 430out:
 431        current_ref_iter = old_ref_iter;
 432        if (ok == ITER_ERROR)
 433                return -1;
 434        return retval;
 435}