Merge branch 'nd/submodule-status-fix'
[git] / shallow.c
1 #include "cache.h"
2 #include "tempfile.h"
3 #include "lockfile.h"
4 #include "commit.h"
5 #include "tag.h"
6 #include "pkt-line.h"
7 #include "remote.h"
8 #include "refs.h"
9 #include "sha1-array.h"
10 #include "diff.h"
11 #include "revision.h"
12 #include "commit-slab.h"
13 #include "revision.h"
14 #include "list-objects.h"
15
16 static int is_shallow = -1;
17 static struct stat_validity shallow_stat;
18 static char *alternate_shallow_file;
19
20 void set_alternate_shallow_file(const char *path, int override)
21 {
22         if (is_shallow != -1)
23                 die("BUG: is_repository_shallow must not be called before set_alternate_shallow_file");
24         if (alternate_shallow_file && !override)
25                 return;
26         free(alternate_shallow_file);
27         alternate_shallow_file = xstrdup_or_null(path);
28 }
29
30 int register_shallow(const struct object_id *oid)
31 {
32         struct commit_graft *graft =
33                 xmalloc(sizeof(struct commit_graft));
34         struct commit *commit = lookup_commit(oid);
35
36         oidcpy(&graft->oid, oid);
37         graft->nr_parent = -1;
38         if (commit && commit->object.parsed)
39                 commit->parents = NULL;
40         return register_commit_graft(graft, 0);
41 }
42
43 int is_repository_shallow(void)
44 {
45         FILE *fp;
46         char buf[1024];
47         const char *path = alternate_shallow_file;
48
49         if (is_shallow >= 0)
50                 return is_shallow;
51
52         if (!path)
53                 path = git_path_shallow();
54         /*
55          * fetch-pack sets '--shallow-file ""' as an indicator that no
56          * shallow file should be used. We could just open it and it
57          * will likely fail. But let's do an explicit check instead.
58          */
59         if (!*path || (fp = fopen(path, "r")) == NULL) {
60                 stat_validity_clear(&shallow_stat);
61                 is_shallow = 0;
62                 return is_shallow;
63         }
64         stat_validity_update(&shallow_stat, fileno(fp));
65         is_shallow = 1;
66
67         while (fgets(buf, sizeof(buf), fp)) {
68                 struct object_id oid;
69                 if (get_oid_hex(buf, &oid))
70                         die("bad shallow line: %s", buf);
71                 register_shallow(&oid);
72         }
73         fclose(fp);
74         return is_shallow;
75 }
76
77 struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
78                 int shallow_flag, int not_shallow_flag)
79 {
80         int i = 0, cur_depth = 0;
81         struct commit_list *result = NULL;
82         struct object_array stack = OBJECT_ARRAY_INIT;
83         struct commit *commit = NULL;
84         struct commit_graft *graft;
85
86         while (commit || i < heads->nr || stack.nr) {
87                 struct commit_list *p;
88                 if (!commit) {
89                         if (i < heads->nr) {
90                                 commit = (struct commit *)
91                                         deref_tag(heads->objects[i++].item, NULL, 0);
92                                 if (!commit || commit->object.type != OBJ_COMMIT) {
93                                         commit = NULL;
94                                         continue;
95                                 }
96                                 if (!commit->util)
97                                         commit->util = xmalloc(sizeof(int));
98                                 *(int *)commit->util = 0;
99                                 cur_depth = 0;
100                         } else {
101                                 commit = (struct commit *)
102                                         object_array_pop(&stack);
103                                 cur_depth = *(int *)commit->util;
104                         }
105                 }
106                 parse_commit_or_die(commit);
107                 cur_depth++;
108                 if ((depth != INFINITE_DEPTH && cur_depth >= depth) ||
109                     (is_repository_shallow() && !commit->parents &&
110                      (graft = lookup_commit_graft(&commit->object.oid)) != NULL &&
111                      graft->nr_parent < 0)) {
112                         commit_list_insert(commit, &result);
113                         commit->object.flags |= shallow_flag;
114                         commit = NULL;
115                         continue;
116                 }
117                 commit->object.flags |= not_shallow_flag;
118                 for (p = commit->parents, commit = NULL; p; p = p->next) {
119                         if (!p->item->util) {
120                                 int *pointer = xmalloc(sizeof(int));
121                                 p->item->util = pointer;
122                                 *pointer =  cur_depth;
123                         } else {
124                                 int *pointer = p->item->util;
125                                 if (cur_depth >= *pointer)
126                                         continue;
127                                 *pointer = cur_depth;
128                         }
129                         if (p->next)
130                                 add_object_array(&p->item->object,
131                                                 NULL, &stack);
132                         else {
133                                 commit = p->item;
134                                 cur_depth = *(int *)commit->util;
135                         }
136                 }
137         }
138
139         return result;
140 }
141
142 static void show_commit(struct commit *commit, void *data)
143 {
144         commit_list_insert(commit, data);
145 }
146
147 /*
148  * Given rev-list arguments, run rev-list. All reachable commits
149  * except border ones are marked with not_shallow_flag. Border commits
150  * are marked with shallow_flag. The list of border/shallow commits
151  * are also returned.
152  */
153 struct commit_list *get_shallow_commits_by_rev_list(int ac, const char **av,
154                                                     int shallow_flag,
155                                                     int not_shallow_flag)
156 {
157         struct commit_list *result = NULL, *p;
158         struct commit_list *not_shallow_list = NULL;
159         struct rev_info revs;
160         int both_flags = shallow_flag | not_shallow_flag;
161
162         /*
163          * SHALLOW (excluded) and NOT_SHALLOW (included) should not be
164          * set at this point. But better be safe than sorry.
165          */
166         clear_object_flags(both_flags);
167
168         is_repository_shallow(); /* make sure shallows are read */
169
170         init_revisions(&revs, NULL);
171         save_commit_buffer = 0;
172         setup_revisions(ac, av, &revs, NULL);
173
174         if (prepare_revision_walk(&revs))
175                 die("revision walk setup failed");
176         traverse_commit_list(&revs, show_commit, NULL, &not_shallow_list);
177
178         /* Mark all reachable commits as NOT_SHALLOW */
179         for (p = not_shallow_list; p; p = p->next)
180                 p->item->object.flags |= not_shallow_flag;
181
182         /*
183          * mark border commits SHALLOW + NOT_SHALLOW.
184          * We cannot clear NOT_SHALLOW right now. Imagine border
185          * commit A is processed first, then commit B, whose parent is
186          * A, later. If NOT_SHALLOW on A is cleared at step 1, B
187          * itself is considered border at step 2, which is incorrect.
188          */
189         for (p = not_shallow_list; p; p = p->next) {
190                 struct commit *c = p->item;
191                 struct commit_list *parent;
192
193                 if (parse_commit(c))
194                         die("unable to parse commit %s",
195                             oid_to_hex(&c->object.oid));
196
197                 for (parent = c->parents; parent; parent = parent->next)
198                         if (!(parent->item->object.flags & not_shallow_flag)) {
199                                 c->object.flags |= shallow_flag;
200                                 commit_list_insert(c, &result);
201                                 break;
202                         }
203         }
204         free_commit_list(not_shallow_list);
205
206         /*
207          * Now we can clean up NOT_SHALLOW on border commits. Having
208          * both flags set can confuse the caller.
209          */
210         for (p = result; p; p = p->next) {
211                 struct object *o = &p->item->object;
212                 if ((o->flags & both_flags) == both_flags)
213                         o->flags &= ~not_shallow_flag;
214         }
215         return result;
216 }
217
218 static void check_shallow_file_for_update(void)
219 {
220         if (is_shallow == -1)
221                 die("BUG: shallow must be initialized by now");
222
223         if (!stat_validity_check(&shallow_stat, git_path_shallow()))
224                 die("shallow file has changed since we read it");
225 }
226
227 #define SEEN_ONLY 1
228 #define VERBOSE   2
229
230 struct write_shallow_data {
231         struct strbuf *out;
232         int use_pack_protocol;
233         int count;
234         unsigned flags;
235 };
236
237 static int write_one_shallow(const struct commit_graft *graft, void *cb_data)
238 {
239         struct write_shallow_data *data = cb_data;
240         const char *hex = oid_to_hex(&graft->oid);
241         if (graft->nr_parent != -1)
242                 return 0;
243         if (data->flags & SEEN_ONLY) {
244                 struct commit *c = lookup_commit(&graft->oid);
245                 if (!c || !(c->object.flags & SEEN)) {
246                         if (data->flags & VERBOSE)
247                                 printf("Removing %s from .git/shallow\n",
248                                        oid_to_hex(&c->object.oid));
249                         return 0;
250                 }
251         }
252         data->count++;
253         if (data->use_pack_protocol)
254                 packet_buf_write(data->out, "shallow %s", hex);
255         else {
256                 strbuf_addstr(data->out, hex);
257                 strbuf_addch(data->out, '\n');
258         }
259         return 0;
260 }
261
262 static int write_shallow_commits_1(struct strbuf *out, int use_pack_protocol,
263                                    const struct oid_array *extra,
264                                    unsigned flags)
265 {
266         struct write_shallow_data data;
267         int i;
268         data.out = out;
269         data.use_pack_protocol = use_pack_protocol;
270         data.count = 0;
271         data.flags = flags;
272         for_each_commit_graft(write_one_shallow, &data);
273         if (!extra)
274                 return data.count;
275         for (i = 0; i < extra->nr; i++) {
276                 strbuf_addstr(out, oid_to_hex(extra->oid + i));
277                 strbuf_addch(out, '\n');
278                 data.count++;
279         }
280         return data.count;
281 }
282
283 int write_shallow_commits(struct strbuf *out, int use_pack_protocol,
284                           const struct oid_array *extra)
285 {
286         return write_shallow_commits_1(out, use_pack_protocol, extra, 0);
287 }
288
289 const char *setup_temporary_shallow(const struct oid_array *extra)
290 {
291         struct tempfile *temp;
292         struct strbuf sb = STRBUF_INIT;
293
294         if (write_shallow_commits(&sb, 0, extra)) {
295                 temp = xmks_tempfile(git_path("shallow_XXXXXX"));
296
297                 if (write_in_full(temp->fd, sb.buf, sb.len) < 0 ||
298                     close_tempfile_gently(temp) < 0)
299                         die_errno("failed to write to %s",
300                                   get_tempfile_path(temp));
301                 strbuf_release(&sb);
302                 return get_tempfile_path(temp);
303         }
304         /*
305          * is_repository_shallow() sees empty string as "no shallow
306          * file".
307          */
308         return "";
309 }
310
311 void setup_alternate_shallow(struct lock_file *shallow_lock,
312                              const char **alternate_shallow_file,
313                              const struct oid_array *extra)
314 {
315         struct strbuf sb = STRBUF_INIT;
316         int fd;
317
318         fd = hold_lock_file_for_update(shallow_lock, git_path_shallow(),
319                                        LOCK_DIE_ON_ERROR);
320         check_shallow_file_for_update();
321         if (write_shallow_commits(&sb, 0, extra)) {
322                 if (write_in_full(fd, sb.buf, sb.len) < 0)
323                         die_errno("failed to write to %s",
324                                   get_lock_file_path(shallow_lock));
325                 *alternate_shallow_file = get_lock_file_path(shallow_lock);
326         } else
327                 /*
328                  * is_repository_shallow() sees empty string as "no
329                  * shallow file".
330                  */
331                 *alternate_shallow_file = "";
332         strbuf_release(&sb);
333 }
334
335 static int advertise_shallow_grafts_cb(const struct commit_graft *graft, void *cb)
336 {
337         int fd = *(int *)cb;
338         if (graft->nr_parent == -1)
339                 packet_write_fmt(fd, "shallow %s\n", oid_to_hex(&graft->oid));
340         return 0;
341 }
342
343 void advertise_shallow_grafts(int fd)
344 {
345         if (!is_repository_shallow())
346                 return;
347         for_each_commit_graft(advertise_shallow_grafts_cb, &fd);
348 }
349
350 /*
351  * mark_reachable_objects() should have been run prior to this and all
352  * reachable commits marked as "SEEN".
353  */
354 void prune_shallow(int show_only)
355 {
356         static struct lock_file shallow_lock;
357         struct strbuf sb = STRBUF_INIT;
358         int fd;
359
360         if (show_only) {
361                 write_shallow_commits_1(&sb, 0, NULL, SEEN_ONLY | VERBOSE);
362                 strbuf_release(&sb);
363                 return;
364         }
365         fd = hold_lock_file_for_update(&shallow_lock, git_path_shallow(),
366                                        LOCK_DIE_ON_ERROR);
367         check_shallow_file_for_update();
368         if (write_shallow_commits_1(&sb, 0, NULL, SEEN_ONLY)) {
369                 if (write_in_full(fd, sb.buf, sb.len) < 0)
370                         die_errno("failed to write to %s",
371                                   get_lock_file_path(&shallow_lock));
372                 commit_lock_file(&shallow_lock);
373         } else {
374                 unlink(git_path_shallow());
375                 rollback_lock_file(&shallow_lock);
376         }
377         strbuf_release(&sb);
378 }
379
380 struct trace_key trace_shallow = TRACE_KEY_INIT(SHALLOW);
381
382 /*
383  * Step 1, split sender shallow commits into "ours" and "theirs"
384  * Step 2, clean "ours" based on .git/shallow
385  */
386 void prepare_shallow_info(struct shallow_info *info, struct oid_array *sa)
387 {
388         int i;
389         trace_printf_key(&trace_shallow, "shallow: prepare_shallow_info\n");
390         memset(info, 0, sizeof(*info));
391         info->shallow = sa;
392         if (!sa)
393                 return;
394         ALLOC_ARRAY(info->ours, sa->nr);
395         ALLOC_ARRAY(info->theirs, sa->nr);
396         for (i = 0; i < sa->nr; i++) {
397                 if (has_object_file(sa->oid + i)) {
398                         struct commit_graft *graft;
399                         graft = lookup_commit_graft(&sa->oid[i]);
400                         if (graft && graft->nr_parent < 0)
401                                 continue;
402                         info->ours[info->nr_ours++] = i;
403                 } else
404                         info->theirs[info->nr_theirs++] = i;
405         }
406 }
407
408 void clear_shallow_info(struct shallow_info *info)
409 {
410         free(info->ours);
411         free(info->theirs);
412 }
413
414 /* Step 4, remove non-existent ones in "theirs" after getting the pack */
415
416 void remove_nonexistent_theirs_shallow(struct shallow_info *info)
417 {
418         struct object_id *oid = info->shallow->oid;
419         int i, dst;
420         trace_printf_key(&trace_shallow, "shallow: remove_nonexistent_theirs_shallow\n");
421         for (i = dst = 0; i < info->nr_theirs; i++) {
422                 if (i != dst)
423                         info->theirs[dst] = info->theirs[i];
424                 if (has_object_file(oid + info->theirs[i]))
425                         dst++;
426         }
427         info->nr_theirs = dst;
428 }
429
430 define_commit_slab(ref_bitmap, uint32_t *);
431
432 #define POOL_SIZE (512 * 1024)
433
434 struct paint_info {
435         struct ref_bitmap ref_bitmap;
436         unsigned nr_bits;
437         char **pools;
438         char *free, *end;
439         unsigned pool_count;
440 };
441
442 static uint32_t *paint_alloc(struct paint_info *info)
443 {
444         unsigned nr = DIV_ROUND_UP(info->nr_bits, 32);
445         unsigned size = nr * sizeof(uint32_t);
446         void *p;
447         if (!info->pool_count || size > info->end - info->free) {
448                 if (size > POOL_SIZE)
449                         die("BUG: pool size too small for %d in paint_alloc()",
450                             size);
451                 info->pool_count++;
452                 REALLOC_ARRAY(info->pools, info->pool_count);
453                 info->free = xmalloc(POOL_SIZE);
454                 info->pools[info->pool_count - 1] = info->free;
455                 info->end = info->free + POOL_SIZE;
456         }
457         p = info->free;
458         info->free += size;
459         return p;
460 }
461
462 /*
463  * Given a commit SHA-1, walk down to parents until either SEEN,
464  * UNINTERESTING or BOTTOM is hit. Set the id-th bit in ref_bitmap for
465  * all walked commits.
466  */
467 static void paint_down(struct paint_info *info, const struct object_id *oid,
468                        unsigned int id)
469 {
470         unsigned int i, nr;
471         struct commit_list *head = NULL;
472         int bitmap_nr = DIV_ROUND_UP(info->nr_bits, 32);
473         size_t bitmap_size = st_mult(sizeof(uint32_t), bitmap_nr);
474         struct commit *c = lookup_commit_reference_gently(oid, 1);
475         uint32_t *tmp; /* to be freed before return */
476         uint32_t *bitmap;
477
478         if (!c)
479                 return;
480
481         tmp = xmalloc(bitmap_size);
482         bitmap = paint_alloc(info);
483         memset(bitmap, 0, bitmap_size);
484         bitmap[id / 32] |= (1U << (id % 32));
485         commit_list_insert(c, &head);
486         while (head) {
487                 struct commit_list *p;
488                 struct commit *c = pop_commit(&head);
489                 uint32_t **refs = ref_bitmap_at(&info->ref_bitmap, c);
490
491                 /* XXX check "UNINTERESTING" from pack bitmaps if available */
492                 if (c->object.flags & (SEEN | UNINTERESTING))
493                         continue;
494                 else
495                         c->object.flags |= SEEN;
496
497                 if (*refs == NULL)
498                         *refs = bitmap;
499                 else {
500                         memcpy(tmp, *refs, bitmap_size);
501                         for (i = 0; i < bitmap_nr; i++)
502                                 tmp[i] |= bitmap[i];
503                         if (memcmp(tmp, *refs, bitmap_size)) {
504                                 *refs = paint_alloc(info);
505                                 memcpy(*refs, tmp, bitmap_size);
506                         }
507                 }
508
509                 if (c->object.flags & BOTTOM)
510                         continue;
511
512                 if (parse_commit(c))
513                         die("unable to parse commit %s",
514                             oid_to_hex(&c->object.oid));
515
516                 for (p = c->parents; p; p = p->next) {
517                         if (p->item->object.flags & SEEN)
518                                 continue;
519                         commit_list_insert(p->item, &head);
520                 }
521         }
522
523         nr = get_max_object_index();
524         for (i = 0; i < nr; i++) {
525                 struct object *o = get_indexed_object(i);
526                 if (o && o->type == OBJ_COMMIT)
527                         o->flags &= ~SEEN;
528         }
529
530         free(tmp);
531 }
532
533 static int mark_uninteresting(const char *refname, const struct object_id *oid,
534                               int flags, void *cb_data)
535 {
536         struct commit *commit = lookup_commit_reference_gently(oid, 1);
537         if (!commit)
538                 return 0;
539         commit->object.flags |= UNINTERESTING;
540         mark_parents_uninteresting(commit);
541         return 0;
542 }
543
544 static void post_assign_shallow(struct shallow_info *info,
545                                 struct ref_bitmap *ref_bitmap,
546                                 int *ref_status);
547 /*
548  * Step 6(+7), associate shallow commits with new refs
549  *
550  * info->ref must be initialized before calling this function.
551  *
552  * If used is not NULL, it's an array of info->shallow->nr
553  * bitmaps. The n-th bit set in the m-th bitmap if ref[n] needs the
554  * m-th shallow commit from info->shallow.
555  *
556  * If used is NULL, "ours" and "theirs" are updated. And if ref_status
557  * is not NULL it's an array of ref->nr ints. ref_status[i] is true if
558  * the ref needs some shallow commits from either info->ours or
559  * info->theirs.
560  */
561 void assign_shallow_commits_to_refs(struct shallow_info *info,
562                                     uint32_t **used, int *ref_status)
563 {
564         struct object_id *oid = info->shallow->oid;
565         struct oid_array *ref = info->ref;
566         unsigned int i, nr;
567         int *shallow, nr_shallow = 0;
568         struct paint_info pi;
569
570         trace_printf_key(&trace_shallow, "shallow: assign_shallow_commits_to_refs\n");
571         ALLOC_ARRAY(shallow, info->nr_ours + info->nr_theirs);
572         for (i = 0; i < info->nr_ours; i++)
573                 shallow[nr_shallow++] = info->ours[i];
574         for (i = 0; i < info->nr_theirs; i++)
575                 shallow[nr_shallow++] = info->theirs[i];
576
577         /*
578          * Prepare the commit graph to track what refs can reach what
579          * (new) shallow commits.
580          */
581         nr = get_max_object_index();
582         for (i = 0; i < nr; i++) {
583                 struct object *o = get_indexed_object(i);
584                 if (!o || o->type != OBJ_COMMIT)
585                         continue;
586
587                 o->flags &= ~(UNINTERESTING | BOTTOM | SEEN);
588         }
589
590         memset(&pi, 0, sizeof(pi));
591         init_ref_bitmap(&pi.ref_bitmap);
592         pi.nr_bits = ref->nr;
593
594         /*
595          * "--not --all" to cut short the traversal if new refs
596          * connect to old refs. If not (e.g. force ref updates) it'll
597          * have to go down to the current shallow commits.
598          */
599         head_ref(mark_uninteresting, NULL);
600         for_each_ref(mark_uninteresting, NULL);
601
602         /* Mark potential bottoms so we won't go out of bound */
603         for (i = 0; i < nr_shallow; i++) {
604                 struct commit *c = lookup_commit(&oid[shallow[i]]);
605                 c->object.flags |= BOTTOM;
606         }
607
608         for (i = 0; i < ref->nr; i++)
609                 paint_down(&pi, ref->oid + i, i);
610
611         if (used) {
612                 int bitmap_size = DIV_ROUND_UP(pi.nr_bits, 32) * sizeof(uint32_t);
613                 memset(used, 0, sizeof(*used) * info->shallow->nr);
614                 for (i = 0; i < nr_shallow; i++) {
615                         const struct commit *c = lookup_commit(&oid[shallow[i]]);
616                         uint32_t **map = ref_bitmap_at(&pi.ref_bitmap, c);
617                         if (*map)
618                                 used[shallow[i]] = xmemdupz(*map, bitmap_size);
619                 }
620                 /*
621                  * unreachable shallow commits are not removed from
622                  * "ours" and "theirs". The user is supposed to run
623                  * step 7 on every ref separately and not trust "ours"
624                  * and "theirs" any more.
625                  */
626         } else
627                 post_assign_shallow(info, &pi.ref_bitmap, ref_status);
628
629         clear_ref_bitmap(&pi.ref_bitmap);
630         for (i = 0; i < pi.pool_count; i++)
631                 free(pi.pools[i]);
632         free(pi.pools);
633         free(shallow);
634 }
635
636 struct commit_array {
637         struct commit **commits;
638         int nr, alloc;
639 };
640
641 static int add_ref(const char *refname, const struct object_id *oid,
642                    int flags, void *cb_data)
643 {
644         struct commit_array *ca = cb_data;
645         ALLOC_GROW(ca->commits, ca->nr + 1, ca->alloc);
646         ca->commits[ca->nr] = lookup_commit_reference_gently(oid, 1);
647         if (ca->commits[ca->nr])
648                 ca->nr++;
649         return 0;
650 }
651
652 static void update_refstatus(int *ref_status, int nr, uint32_t *bitmap)
653 {
654         unsigned int i;
655         if (!ref_status)
656                 return;
657         for (i = 0; i < nr; i++)
658                 if (bitmap[i / 32] & (1U << (i % 32)))
659                         ref_status[i]++;
660 }
661
662 /*
663  * Step 7, reachability test on "ours" at commit level
664  */
665 static void post_assign_shallow(struct shallow_info *info,
666                                 struct ref_bitmap *ref_bitmap,
667                                 int *ref_status)
668 {
669         struct object_id *oid = info->shallow->oid;
670         struct commit *c;
671         uint32_t **bitmap;
672         int dst, i, j;
673         int bitmap_nr = DIV_ROUND_UP(info->ref->nr, 32);
674         struct commit_array ca;
675
676         trace_printf_key(&trace_shallow, "shallow: post_assign_shallow\n");
677         if (ref_status)
678                 memset(ref_status, 0, sizeof(*ref_status) * info->ref->nr);
679
680         /* Remove unreachable shallow commits from "theirs" */
681         for (i = dst = 0; i < info->nr_theirs; i++) {
682                 if (i != dst)
683                         info->theirs[dst] = info->theirs[i];
684                 c = lookup_commit(&oid[info->theirs[i]]);
685                 bitmap = ref_bitmap_at(ref_bitmap, c);
686                 if (!*bitmap)
687                         continue;
688                 for (j = 0; j < bitmap_nr; j++)
689                         if (bitmap[0][j]) {
690                                 update_refstatus(ref_status, info->ref->nr, *bitmap);
691                                 dst++;
692                                 break;
693                         }
694         }
695         info->nr_theirs = dst;
696
697         memset(&ca, 0, sizeof(ca));
698         head_ref(add_ref, &ca);
699         for_each_ref(add_ref, &ca);
700
701         /* Remove unreachable shallow commits from "ours" */
702         for (i = dst = 0; i < info->nr_ours; i++) {
703                 if (i != dst)
704                         info->ours[dst] = info->ours[i];
705                 c = lookup_commit(&oid[info->ours[i]]);
706                 bitmap = ref_bitmap_at(ref_bitmap, c);
707                 if (!*bitmap)
708                         continue;
709                 for (j = 0; j < bitmap_nr; j++)
710                         if (bitmap[0][j] &&
711                             /* Step 7, reachability test at commit level */
712                             !in_merge_bases_many(c, ca.nr, ca.commits)) {
713                                 update_refstatus(ref_status, info->ref->nr, *bitmap);
714                                 dst++;
715                                 break;
716                         }
717         }
718         info->nr_ours = dst;
719
720         free(ca.commits);
721 }
722
723 /* (Delayed) step 7, reachability test at commit level */
724 int delayed_reachability_test(struct shallow_info *si, int c)
725 {
726         if (si->need_reachability_test[c]) {
727                 struct commit *commit = lookup_commit(&si->shallow->oid[c]);
728
729                 if (!si->commits) {
730                         struct commit_array ca;
731
732                         memset(&ca, 0, sizeof(ca));
733                         head_ref(add_ref, &ca);
734                         for_each_ref(add_ref, &ca);
735                         si->commits = ca.commits;
736                         si->nr_commits = ca.nr;
737                 }
738
739                 si->reachable[c] = in_merge_bases_many(commit,
740                                                        si->nr_commits,
741                                                        si->commits);
742                 si->need_reachability_test[c] = 0;
743         }
744         return si->reachable[c];
745 }