refs/iterator.c

   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
  11 int ref_iterator_advance(struct ref_iterator *ref_iterator)
  12 {
  13         return ref_iterator->vtable->advance(ref_iterator);
  14 }
  15
  16 int 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
  22 int ref_iterator_abort(struct ref_iterator *ref_iterator)
  23 {
  24         return ref_iterator->vtable->abort(ref_iterator);
  25 }
  26
  27 void 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
  38 void 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
  45 struct empty_ref_iterator {
  46         struct ref_iterator base;
  47 };
  48
  49 static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator)
  50 {
  51         return ref_iterator_abort(ref_iterator);
  52 }
  53
  54 static 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
  60 static int empty_ref_iterator_abort(struct ref_iterator *ref_iterator)
  61 {
  62         base_ref_iterator_free(ref_iterator);
  63         return ITER_DONE;
  64 }
  65
  66 static 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
  72 struct 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
  81 int is_empty_ref_iterator(struct ref_iterator *ref_iterator)
  82 {
  83         return ref_iterator->vtable == &empty_ref_iterator_vtable;
  84 }
  85
  86 struct 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
 101 static 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
 168 error:
 169         ref_iterator_abort(ref_iterator);
 170         return ITER_ERROR;
 171 }
 172
 173 static 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
 185 static 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
 203 static 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
 209 struct 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  */
 239 static 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
 260 struct 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
 282 struct 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. */
 291 static 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
 304 static 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
 358 static 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
 367 static 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
 380 static 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
 386 struct 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
 408 struct ref_iterator *current_ref_iter = NULL;
 409
 410 int 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
 430 out:
 431         current_ref_iter = old_ref_iter;
 432         if (ok == ITER_ERROR)
 433                 return -1;
 434         return retval;
 435 }