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