2 * Generic reference iterator infrastructure. See refs-internal.h for
3 * documentation about the design and use of reference iterators.
8 #include "refs/refs-internal.h"
11 int ref_iterator_advance(struct ref_iterator
*ref_iterator
)
13 return ref_iterator
->vtable
->advance(ref_iterator
);
16 int ref_iterator_peel(struct ref_iterator
*ref_iterator
,
17 struct object_id
*peeled
)
19 return ref_iterator
->vtable
->peel(ref_iterator
, peeled
);
22 int ref_iterator_abort(struct ref_iterator
*ref_iterator
)
24 return ref_iterator
->vtable
->abort(ref_iterator
);
27 void base_ref_iterator_init(struct ref_iterator
*iter
,
28 struct ref_iterator_vtable
*vtable
,
31 iter
->vtable
= vtable
;
32 iter
->ordered
= !!ordered
;
38 void base_ref_iterator_free(struct ref_iterator
*iter
)
40 /* Help make use-after-free bugs fail quickly: */
45 struct empty_ref_iterator
{
46 struct ref_iterator base
;
49 static int empty_ref_iterator_advance(struct ref_iterator
*ref_iterator
)
51 return ref_iterator_abort(ref_iterator
);
54 static int empty_ref_iterator_peel(struct ref_iterator
*ref_iterator
,
55 struct object_id
*peeled
)
57 BUG("peel called for empty iterator");
60 static int empty_ref_iterator_abort(struct ref_iterator
*ref_iterator
)
62 base_ref_iterator_free(ref_iterator
);
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
72 struct ref_iterator
*empty_ref_iterator_begin(void)
74 struct empty_ref_iterator
*iter
= xcalloc(1, sizeof(*iter
));
75 struct ref_iterator
*ref_iterator
= &iter
->base
;
77 base_ref_iterator_init(ref_iterator
, &empty_ref_iterator_vtable
, 1);
81 int is_empty_ref_iterator(struct ref_iterator
*ref_iterator
)
83 return ref_iterator
->vtable
== &empty_ref_iterator_vtable
;
86 struct merge_ref_iterator
{
87 struct ref_iterator base
;
89 struct ref_iterator
*iter0
, *iter1
;
91 ref_iterator_select_fn
*select
;
95 * A pointer to iter0 or iter1 (whichever is supplying the
96 * current value), or NULL if advance has not yet been called.
98 struct ref_iterator
**current
;
101 static int merge_ref_iterator_advance(struct ref_iterator
*ref_iterator
)
103 struct merge_ref_iterator
*iter
=
104 (struct merge_ref_iterator
*)ref_iterator
;
107 if (!iter
->current
) {
108 /* Initialize: advance both iterators to their first entries */
109 if ((ok
= ref_iterator_advance(iter
->iter0
)) != ITER_OK
) {
111 if (ok
== ITER_ERROR
)
114 if ((ok
= ref_iterator_advance(iter
->iter1
)) != ITER_OK
) {
116 if (ok
== ITER_ERROR
)
121 * Advance the current iterator past the just-used
124 if ((ok
= ref_iterator_advance(*iter
->current
)) != ITER_OK
) {
125 *iter
->current
= NULL
;
126 if (ok
== ITER_ERROR
)
131 /* Loop until we find an entry that we can yield. */
133 struct ref_iterator
**secondary
;
134 enum iterator_selection selection
=
135 iter
->select(iter
->iter0
, iter
->iter1
, iter
->cb_data
);
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
);
144 if ((selection
& ITER_CURRENT_SELECTION_MASK
) == 0) {
145 iter
->current
= &iter
->iter0
;
146 secondary
= &iter
->iter1
;
148 iter
->current
= &iter
->iter1
;
149 secondary
= &iter
->iter0
;
152 if (selection
& ITER_SKIP_SECONDARY
) {
153 if ((ok
= ref_iterator_advance(*secondary
)) != ITER_OK
) {
155 if (ok
== ITER_ERROR
)
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
;
169 ref_iterator_abort(ref_iterator
);
173 static int merge_ref_iterator_peel(struct ref_iterator
*ref_iterator
,
174 struct object_id
*peeled
)
176 struct merge_ref_iterator
*iter
=
177 (struct merge_ref_iterator
*)ref_iterator
;
179 if (!iter
->current
) {
180 BUG("peel called before advance for merge iterator");
182 return ref_iterator_peel(*iter
->current
, peeled
);
185 static int merge_ref_iterator_abort(struct ref_iterator
*ref_iterator
)
187 struct merge_ref_iterator
*iter
=
188 (struct merge_ref_iterator
*)ref_iterator
;
192 if (ref_iterator_abort(iter
->iter0
) != ITER_DONE
)
196 if (ref_iterator_abort(iter
->iter1
) != ITER_DONE
)
199 base_ref_iterator_free(ref_iterator
);
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
209 struct ref_iterator
*merge_ref_iterator_begin(
211 struct ref_iterator
*iter0
, struct ref_iterator
*iter1
,
212 ref_iterator_select_fn
*select
, void *cb_data
)
214 struct merge_ref_iterator
*iter
= xcalloc(1, sizeof(*iter
));
215 struct ref_iterator
*ref_iterator
= &iter
->base
;
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.
225 base_ref_iterator_init(ref_iterator
, &merge_ref_iterator_vtable
, ordered
);
228 iter
->select
= select
;
229 iter
->cb_data
= cb_data
;
230 iter
->current
= NULL
;
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().
239 static enum iterator_selection
overlay_iterator_select(
240 struct ref_iterator
*front
, struct ref_iterator
*back
,
246 return front
? ITER_SELECT_0
: ITER_SELECT_DONE
;
248 return ITER_SELECT_1
;
250 cmp
= strcmp(front
->refname
, back
->refname
);
253 return ITER_SELECT_0
;
255 return ITER_SELECT_1
;
257 return ITER_SELECT_0_SKIP_1
;
260 struct ref_iterator
*overlay_ref_iterator_begin(
261 struct ref_iterator
*front
, struct ref_iterator
*back
)
264 * Optimization: if one of the iterators is empty, return the
265 * other one rather than incurring the overhead of wrapping
268 if (is_empty_ref_iterator(front
)) {
269 ref_iterator_abort(front
);
271 } else if (is_empty_ref_iterator(back
)) {
272 ref_iterator_abort(back
);
274 } else if (!front
->ordered
|| !back
->ordered
) {
275 BUG("overlay_ref_iterator requires ordered inputs");
278 return merge_ref_iterator_begin(1, front
, back
,
279 overlay_iterator_select
, NULL
);
282 struct prefix_ref_iterator
{
283 struct ref_iterator base
;
285 struct ref_iterator
*iter0
;
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
)
294 if (*refname
!= *prefix
)
295 return ((unsigned char)*refname
< (unsigned char)*prefix
) ? -1 : +1;
304 static int prefix_ref_iterator_advance(struct ref_iterator
*ref_iterator
)
306 struct prefix_ref_iterator
*iter
=
307 (struct prefix_ref_iterator
*)ref_iterator
;
310 while ((ok
= ref_iterator_advance(iter
->iter0
)) == ITER_OK
) {
311 int cmp
= compare_prefix(iter
->iter0
->refname
, iter
->prefix
);
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:
322 if (iter
->iter0
->ordered
) {
323 ok
= ref_iterator_abort(iter
->iter0
);
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:
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
;
344 iter
->base
.refname
= iter
->iter0
->refname
;
347 iter
->base
.oid
= iter
->iter0
->oid
;
348 iter
->base
.flags
= iter
->iter0
->flags
;
353 if (ref_iterator_abort(ref_iterator
) != ITER_DONE
)
358 static int prefix_ref_iterator_peel(struct ref_iterator
*ref_iterator
,
359 struct object_id
*peeled
)
361 struct prefix_ref_iterator
*iter
=
362 (struct prefix_ref_iterator
*)ref_iterator
;
364 return ref_iterator_peel(iter
->iter0
, peeled
);
367 static int prefix_ref_iterator_abort(struct ref_iterator
*ref_iterator
)
369 struct prefix_ref_iterator
*iter
=
370 (struct prefix_ref_iterator
*)ref_iterator
;
374 ok
= ref_iterator_abort(iter
->iter0
);
376 base_ref_iterator_free(ref_iterator
);
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
386 struct ref_iterator
*prefix_ref_iterator_begin(struct ref_iterator
*iter0
,
390 struct prefix_ref_iterator
*iter
;
391 struct ref_iterator
*ref_iterator
;
393 if (!*prefix
&& !trim
)
394 return iter0
; /* optimization: no need to wrap iterator */
396 iter
= xcalloc(1, sizeof(*iter
));
397 ref_iterator
= &iter
->base
;
399 base_ref_iterator_init(ref_iterator
, &prefix_ref_iterator_vtable
, iter0
->ordered
);
402 iter
->prefix
= xstrdup(prefix
);
408 struct ref_iterator
*current_ref_iter
= NULL
;
410 int do_for_each_repo_ref_iterator(struct repository
*r
, struct ref_iterator
*iter
,
411 each_repo_ref_fn fn
, void *cb_data
)
414 struct ref_iterator
*old_ref_iter
= current_ref_iter
;
416 current_ref_iter
= iter
;
417 while ((ok
= ref_iterator_advance(iter
)) == ITER_OK
) {
418 retval
= fn(r
, iter
->refname
, iter
->oid
, iter
->flags
, cb_data
);
421 * If ref_iterator_abort() returns ITER_ERROR,
422 * we ignore that error in deference to the
423 * callback function's return value.
425 ref_iterator_abort(iter
);
431 current_ref_iter
= old_ref_iter
;
432 if (ok
== ITER_ERROR
)