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