Merge branch 'jk/ui-color-always-to-auto-maint' into jk/ui-color-always-to-auto
[git] / 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         die("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                 die("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                                 die("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 }