]>
Commit | Line | Data |
---|---|---|
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 | ||
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, | |
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 | ||
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 | { | |
033abf97 | 57 | BUG("peel called for empty iterator"); |
3bc581b9 MH |
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 | ||
8738a8a4 | 77 | base_ref_iterator_init(ref_iterator, &empty_ref_iterator_vtable, 1); |
3bc581b9 MH |
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) { | |
033abf97 | 180 | BUG("peel called before advance for merge iterator"); |
3bc581b9 MH |
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( | |
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 | */ | |
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; | |
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 | ||
282 | struct prefix_ref_iterator { | |
283 | struct ref_iterator base; | |
284 | ||
285 | struct ref_iterator *iter0; | |
286 | char *prefix; | |
287 | int trim; | |
288 | }; | |
289 | ||
157113c6 JK |
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 | ||
3bc581b9 MH |
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) { | |
157113c6 JK |
311 | int cmp = compare_prefix(iter->iter0->refname, iter->prefix); |
312 | ||
313 | if (cmp < 0) | |
3bc581b9 MH |
314 | continue; |
315 | ||
157113c6 JK |
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 | ||
b9c8e7f2 MH |
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) | |
033abf97 | 341 | BUG("attempt to trim too many characters"); |
b9c8e7f2 MH |
342 | iter->base.refname = iter->iter0->refname + iter->trim; |
343 | } else { | |
344 | iter->base.refname = iter->iter0->refname; | |
345 | } | |
346 | ||
3bc581b9 MH |
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 | ||
8738a8a4 | 399 | base_ref_iterator_init(ref_iterator, &prefix_ref_iterator_vtable, iter0->ordered); |
3bc581b9 MH |
400 | |
401 | iter->iter0 = iter0; | |
402 | iter->prefix = xstrdup(prefix); | |
403 | iter->trim = trim; | |
404 | ||
405 | return ref_iterator; | |
406 | } | |
4c4de895 MH |
407 | |
408 | struct ref_iterator *current_ref_iter = NULL; | |
409 | ||
4a6067cd SB |
410 | int do_for_each_repo_ref_iterator(struct repository *r, struct ref_iterator *iter, |
411 | each_repo_ref_fn fn, void *cb_data) | |
4c4de895 MH |
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) { | |
4a6067cd | 418 | retval = fn(r, iter->refname, iter->oid, iter->flags, cb_data); |
4c4de895 MH |
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 | } |