struct ref_transaction: add a place for backends to store data
[git/git.git] / refs / iterator.c
... / ...
CommitLineData
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{
30 iter->vtable = vtable;
31 iter->refname = NULL;
32 iter->oid = NULL;
33 iter->flags = 0;
34}
35
36void base_ref_iterator_free(struct ref_iterator *iter)
37{
38 /* Help make use-after-free bugs fail quickly: */
39 iter->vtable = NULL;
40 free(iter);
41}
42
43struct empty_ref_iterator {
44 struct ref_iterator base;
45};
46
47static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator)
48{
49 return ref_iterator_abort(ref_iterator);
50}
51
52static int empty_ref_iterator_peel(struct ref_iterator *ref_iterator,
53 struct object_id *peeled)
54{
55 die("BUG: peel called for empty iterator");
56}
57
58static int empty_ref_iterator_abort(struct ref_iterator *ref_iterator)
59{
60 base_ref_iterator_free(ref_iterator);
61 return ITER_DONE;
62}
63
64static struct ref_iterator_vtable empty_ref_iterator_vtable = {
65 empty_ref_iterator_advance,
66 empty_ref_iterator_peel,
67 empty_ref_iterator_abort
68};
69
70struct ref_iterator *empty_ref_iterator_begin(void)
71{
72 struct empty_ref_iterator *iter = xcalloc(1, sizeof(*iter));
73 struct ref_iterator *ref_iterator = &iter->base;
74
75 base_ref_iterator_init(ref_iterator, &empty_ref_iterator_vtable);
76 return ref_iterator;
77}
78
79int is_empty_ref_iterator(struct ref_iterator *ref_iterator)
80{
81 return ref_iterator->vtable == &empty_ref_iterator_vtable;
82}
83
84struct merge_ref_iterator {
85 struct ref_iterator base;
86
87 struct ref_iterator *iter0, *iter1;
88
89 ref_iterator_select_fn *select;
90 void *cb_data;
91
92 /*
93 * A pointer to iter0 or iter1 (whichever is supplying the
94 * current value), or NULL if advance has not yet been called.
95 */
96 struct ref_iterator **current;
97};
98
99static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator)
100{
101 struct merge_ref_iterator *iter =
102 (struct merge_ref_iterator *)ref_iterator;
103 int ok;
104
105 if (!iter->current) {
106 /* Initialize: advance both iterators to their first entries */
107 if ((ok = ref_iterator_advance(iter->iter0)) != ITER_OK) {
108 iter->iter0 = NULL;
109 if (ok == ITER_ERROR)
110 goto error;
111 }
112 if ((ok = ref_iterator_advance(iter->iter1)) != ITER_OK) {
113 iter->iter1 = NULL;
114 if (ok == ITER_ERROR)
115 goto error;
116 }
117 } else {
118 /*
119 * Advance the current iterator past the just-used
120 * entry:
121 */
122 if ((ok = ref_iterator_advance(*iter->current)) != ITER_OK) {
123 *iter->current = NULL;
124 if (ok == ITER_ERROR)
125 goto error;
126 }
127 }
128
129 /* Loop until we find an entry that we can yield. */
130 while (1) {
131 struct ref_iterator **secondary;
132 enum iterator_selection selection =
133 iter->select(iter->iter0, iter->iter1, iter->cb_data);
134
135 if (selection == ITER_SELECT_DONE) {
136 return ref_iterator_abort(ref_iterator);
137 } else if (selection == ITER_SELECT_ERROR) {
138 ref_iterator_abort(ref_iterator);
139 return ITER_ERROR;
140 }
141
142 if ((selection & ITER_CURRENT_SELECTION_MASK) == 0) {
143 iter->current = &iter->iter0;
144 secondary = &iter->iter1;
145 } else {
146 iter->current = &iter->iter1;
147 secondary = &iter->iter0;
148 }
149
150 if (selection & ITER_SKIP_SECONDARY) {
151 if ((ok = ref_iterator_advance(*secondary)) != ITER_OK) {
152 *secondary = NULL;
153 if (ok == ITER_ERROR)
154 goto error;
155 }
156 }
157
158 if (selection & ITER_YIELD_CURRENT) {
159 iter->base.refname = (*iter->current)->refname;
160 iter->base.oid = (*iter->current)->oid;
161 iter->base.flags = (*iter->current)->flags;
162 return ITER_OK;
163 }
164 }
165
166error:
167 ref_iterator_abort(ref_iterator);
168 return ITER_ERROR;
169}
170
171static int merge_ref_iterator_peel(struct ref_iterator *ref_iterator,
172 struct object_id *peeled)
173{
174 struct merge_ref_iterator *iter =
175 (struct merge_ref_iterator *)ref_iterator;
176
177 if (!iter->current) {
178 die("BUG: peel called before advance for merge iterator");
179 }
180 return ref_iterator_peel(*iter->current, peeled);
181}
182
183static int merge_ref_iterator_abort(struct ref_iterator *ref_iterator)
184{
185 struct merge_ref_iterator *iter =
186 (struct merge_ref_iterator *)ref_iterator;
187 int ok = ITER_DONE;
188
189 if (iter->iter0) {
190 if (ref_iterator_abort(iter->iter0) != ITER_DONE)
191 ok = ITER_ERROR;
192 }
193 if (iter->iter1) {
194 if (ref_iterator_abort(iter->iter1) != ITER_DONE)
195 ok = ITER_ERROR;
196 }
197 base_ref_iterator_free(ref_iterator);
198 return ok;
199}
200
201static struct ref_iterator_vtable merge_ref_iterator_vtable = {
202 merge_ref_iterator_advance,
203 merge_ref_iterator_peel,
204 merge_ref_iterator_abort
205};
206
207struct ref_iterator *merge_ref_iterator_begin(
208 struct ref_iterator *iter0, struct ref_iterator *iter1,
209 ref_iterator_select_fn *select, void *cb_data)
210{
211 struct merge_ref_iterator *iter = xcalloc(1, sizeof(*iter));
212 struct ref_iterator *ref_iterator = &iter->base;
213
214 /*
215 * We can't do the same kind of is_empty_ref_iterator()-style
216 * optimization here as overlay_ref_iterator_begin() does,
217 * because we don't know the semantics of the select function.
218 * It might, for example, implement "intersect" by passing
219 * references through only if they exist in both iterators.
220 */
221
222 base_ref_iterator_init(ref_iterator, &merge_ref_iterator_vtable);
223 iter->iter0 = iter0;
224 iter->iter1 = iter1;
225 iter->select = select;
226 iter->cb_data = cb_data;
227 iter->current = NULL;
228 return ref_iterator;
229}
230
231/*
232 * A ref_iterator_select_fn that overlays the items from front on top
233 * of those from back (like loose refs over packed refs). See
234 * overlay_ref_iterator_begin().
235 */
236static enum iterator_selection overlay_iterator_select(
237 struct ref_iterator *front, struct ref_iterator *back,
238 void *cb_data)
239{
240 int cmp;
241
242 if (!back)
243 return front ? ITER_SELECT_0 : ITER_SELECT_DONE;
244 else if (!front)
245 return ITER_SELECT_1;
246
247 cmp = strcmp(front->refname, back->refname);
248
249 if (cmp < 0)
250 return ITER_SELECT_0;
251 else if (cmp > 0)
252 return ITER_SELECT_1;
253 else
254 return ITER_SELECT_0_SKIP_1;
255}
256
257struct ref_iterator *overlay_ref_iterator_begin(
258 struct ref_iterator *front, struct ref_iterator *back)
259{
260 /*
261 * Optimization: if one of the iterators is empty, return the
262 * other one rather than incurring the overhead of wrapping
263 * them.
264 */
265 if (is_empty_ref_iterator(front)) {
266 ref_iterator_abort(front);
267 return back;
268 } else if (is_empty_ref_iterator(back)) {
269 ref_iterator_abort(back);
270 return front;
271 }
272
273 return merge_ref_iterator_begin(front, back,
274 overlay_iterator_select, NULL);
275}
276
277struct prefix_ref_iterator {
278 struct ref_iterator base;
279
280 struct ref_iterator *iter0;
281 char *prefix;
282 int trim;
283};
284
285static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator)
286{
287 struct prefix_ref_iterator *iter =
288 (struct prefix_ref_iterator *)ref_iterator;
289 int ok;
290
291 while ((ok = ref_iterator_advance(iter->iter0)) == ITER_OK) {
292 if (!starts_with(iter->iter0->refname, iter->prefix))
293 continue;
294
295 if (iter->trim) {
296 /*
297 * It is nonsense to trim off characters that
298 * you haven't already checked for via a
299 * prefix check, whether via this
300 * `prefix_ref_iterator` or upstream in
301 * `iter0`). So if there wouldn't be at least
302 * one character left in the refname after
303 * trimming, report it as a bug:
304 */
305 if (strlen(iter->iter0->refname) <= iter->trim)
306 die("BUG: attempt to trim too many characters");
307 iter->base.refname = iter->iter0->refname + iter->trim;
308 } else {
309 iter->base.refname = iter->iter0->refname;
310 }
311
312 iter->base.oid = iter->iter0->oid;
313 iter->base.flags = iter->iter0->flags;
314 return ITER_OK;
315 }
316
317 iter->iter0 = NULL;
318 if (ref_iterator_abort(ref_iterator) != ITER_DONE)
319 return ITER_ERROR;
320 return ok;
321}
322
323static int prefix_ref_iterator_peel(struct ref_iterator *ref_iterator,
324 struct object_id *peeled)
325{
326 struct prefix_ref_iterator *iter =
327 (struct prefix_ref_iterator *)ref_iterator;
328
329 return ref_iterator_peel(iter->iter0, peeled);
330}
331
332static int prefix_ref_iterator_abort(struct ref_iterator *ref_iterator)
333{
334 struct prefix_ref_iterator *iter =
335 (struct prefix_ref_iterator *)ref_iterator;
336 int ok = ITER_DONE;
337
338 if (iter->iter0)
339 ok = ref_iterator_abort(iter->iter0);
340 free(iter->prefix);
341 base_ref_iterator_free(ref_iterator);
342 return ok;
343}
344
345static struct ref_iterator_vtable prefix_ref_iterator_vtable = {
346 prefix_ref_iterator_advance,
347 prefix_ref_iterator_peel,
348 prefix_ref_iterator_abort
349};
350
351struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,
352 const char *prefix,
353 int trim)
354{
355 struct prefix_ref_iterator *iter;
356 struct ref_iterator *ref_iterator;
357
358 if (!*prefix && !trim)
359 return iter0; /* optimization: no need to wrap iterator */
360
361 iter = xcalloc(1, sizeof(*iter));
362 ref_iterator = &iter->base;
363
364 base_ref_iterator_init(ref_iterator, &prefix_ref_iterator_vtable);
365
366 iter->iter0 = iter0;
367 iter->prefix = xstrdup(prefix);
368 iter->trim = trim;
369
370 return ref_iterator;
371}
372
373struct ref_iterator *current_ref_iter = NULL;
374
375int do_for_each_ref_iterator(struct ref_iterator *iter,
376 each_ref_fn fn, void *cb_data)
377{
378 int retval = 0, ok;
379 struct ref_iterator *old_ref_iter = current_ref_iter;
380
381 current_ref_iter = iter;
382 while ((ok = ref_iterator_advance(iter)) == ITER_OK) {
383 retval = fn(iter->refname, iter->oid, iter->flags, cb_data);
384 if (retval) {
385 /*
386 * If ref_iterator_abort() returns ITER_ERROR,
387 * we ignore that error in deference to the
388 * callback function's return value.
389 */
390 ref_iterator_abort(iter);
391 goto out;
392 }
393 }
394
395out:
396 current_ref_iter = old_ref_iter;
397 if (ok == ITER_ERROR)
398 return -1;
399 return retval;
400}