ref_iterator: keep track of whether the iterator output is ordered
[git/git.git] / refs / iterator.c
CommitLineData
3bc581b9
MH
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,
8738a8a4
MH
28 struct ref_iterator_vtable *vtable,
29 int ordered)
3bc581b9
MH
30{
31 iter->vtable = vtable;
8738a8a4 32 iter->ordered = !!ordered;
3bc581b9
MH
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
8738a8a4 77 base_ref_iterator_init(ref_iterator, &empty_ref_iterator_vtable, 1);
3bc581b9
MH
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(
8738a8a4 210 int ordered,
3bc581b9
MH
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
8738a8a4 225 base_ref_iterator_init(ref_iterator, &merge_ref_iterator_vtable, ordered);
3bc581b9
MH
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;
8738a8a4
MH
274 } else if (!front->ordered || !back->ordered) {
275 BUG("overlay_ref_iterator requires ordered inputs");
3bc581b9
MH
276 }
277
8738a8a4 278 return merge_ref_iterator_begin(1, front, back,
3bc581b9
MH
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
b9c8e7f2
MH
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
3bc581b9
MH
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
8738a8a4 369 base_ref_iterator_init(ref_iterator, &prefix_ref_iterator_vtable, iter0->ordered);
3bc581b9
MH
370
371 iter->iter0 = iter0;
372 iter->prefix = xstrdup(prefix);
373 iter->trim = trim;
374
375 return ref_iterator;
376}
4c4de895
MH
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}