commit-reach.c

   1 #define USE_THE_REPOSITORY_VARIABLE
   2
   3 #include "git-compat-util.h"
   4 #include "commit.h"
   5 #include "commit-graph.h"
   6 #include "decorate.h"
   7 #include "hex.h"
   8 #include "prio-queue.h"
   9 #include "ref-filter.h"
  10 #include "revision.h"
  11 #include "tag.h"
  12 #include "commit-reach.h"
  13 #include "ewah/ewok.h"
  14
  15 /* Remember to update object flag allocation in object.h */
  16 #define PARENT1         (1u<<16)
  17 #define PARENT2         (1u<<17)
  18 #define STALE           (1u<<18)
  19 #define RESULT          (1u<<19)
  20
  21 static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
  22
  23 static int compare_commits_by_gen(const void *_a, const void *_b)
  24 {
  25         const struct commit *a = *(const struct commit * const *)_a;
  26         const struct commit *b = *(const struct commit * const *)_b;
  27
  28         timestamp_t generation_a = commit_graph_generation(a);
  29         timestamp_t generation_b = commit_graph_generation(b);
  30
  31         if (generation_a < generation_b)
  32                 return -1;
  33         if (generation_a > generation_b)
  34                 return 1;
  35         if (a->date < b->date)
  36                 return -1;
  37         if (a->date > b->date)
  38                 return 1;
  39         return 0;
  40 }
  41
  42 static int queue_has_nonstale(struct prio_queue *queue)
  43 {
  44         int i;
  45         for (i = 0; i < queue->nr; i++) {
  46                 struct commit *commit = queue->array[i].data;
  47                 if (!(commit->object.flags & STALE))
  48                         return 1;
  49         }
  50         return 0;
  51 }
  52
  53 /* all input commits in one and twos[] must have been parsed! */
  54 static int paint_down_to_common(struct repository *r,
  55                                 struct commit *one, int n,
  56                                 struct commit **twos,
  57                                 timestamp_t min_generation,
  58                                 int ignore_missing_commits,
  59                                 struct commit_list **result)
  60 {
  61         struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
  62         int i;
  63         timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
  64
  65         if (!min_generation && !corrected_commit_dates_enabled(r))
  66                 queue.compare = compare_commits_by_commit_date;
  67
  68         one->object.flags |= PARENT1;
  69         if (!n) {
  70                 commit_list_append(one, result);
  71                 return 0;
  72         }
  73         prio_queue_put(&queue, one);
  74
  75         for (i = 0; i < n; i++) {
  76                 twos[i]->object.flags |= PARENT2;
  77                 prio_queue_put(&queue, twos[i]);
  78         }
  79
  80         while (queue_has_nonstale(&queue)) {
  81                 struct commit *commit = prio_queue_get(&queue);
  82                 struct commit_list *parents;
  83                 int flags;
  84                 timestamp_t generation = commit_graph_generation(commit);
  85
  86                 if (min_generation && generation > last_gen)
  87                         BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
  88                             generation, last_gen,
  89                             oid_to_hex(&commit->object.oid));
  90                 last_gen = generation;
  91
  92                 if (generation < min_generation)
  93                         break;
  94
  95                 flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
  96                 if (flags == (PARENT1 | PARENT2)) {
  97                         if (!(commit->object.flags & RESULT)) {
  98                                 commit->object.flags |= RESULT;
  99                                 commit_list_insert_by_date(commit, result);
 100                         }
 101                         /* Mark parents of a found merge stale */
 102                         flags |= STALE;
 103                 }
 104                 parents = commit->parents;
 105                 while (parents) {
 106                         struct commit *p = parents->item;
 107                         parents = parents->next;
 108                         if ((p->object.flags & flags) == flags)
 109                                 continue;
 110                         if (repo_parse_commit(r, p)) {
 111                                 clear_prio_queue(&queue);
 112                                 free_commit_list(*result);
 113                                 *result = NULL;
 114                                 /*
 115                                  * At this stage, we know that the commit is
 116                                  * missing: `repo_parse_commit()` uses
 117                                  * `OBJECT_INFO_DIE_IF_CORRUPT` and therefore
 118                                  * corrupt commits would already have been
 119                                  * dispatched with a `die()`.
 120                                  */
 121                                 if (ignore_missing_commits)
 122                                         return 0;
 123                                 return error(_("could not parse commit %s"),
 124                                              oid_to_hex(&p->object.oid));
 125                         }
 126                         p->object.flags |= flags;
 127                         prio_queue_put(&queue, p);
 128                 }
 129         }
 130
 131         clear_prio_queue(&queue);
 132         return 0;
 133 }
 134
 135 static int merge_bases_many(struct repository *r,
 136                             struct commit *one, int n,
 137                             struct commit **twos,
 138                             struct commit_list **result)
 139 {
 140         struct commit_list *list = NULL;
 141         int i;
 142
 143         for (i = 0; i < n; i++) {
 144                 if (one == twos[i]) {
 145                         /*
 146                          * We do not mark this even with RESULT so we do not
 147                          * have to clean it up.
 148                          */
 149                         *result = commit_list_insert(one, result);
 150                         return 0;
 151                 }
 152         }
 153
 154         if (!one)
 155                 return 0;
 156         if (repo_parse_commit(r, one))
 157                 return error(_("could not parse commit %s"),
 158                              oid_to_hex(&one->object.oid));
 159         for (i = 0; i < n; i++) {
 160                 if (!twos[i])
 161                         return 0;
 162                 if (repo_parse_commit(r, twos[i]))
 163                         return error(_("could not parse commit %s"),
 164                                      oid_to_hex(&twos[i]->object.oid));
 165         }
 166
 167         if (paint_down_to_common(r, one, n, twos, 0, 0, &list)) {
 168                 free_commit_list(list);
 169                 return -1;
 170         }
 171
 172         while (list) {
 173                 struct commit *commit = pop_commit(&list);
 174                 if (!(commit->object.flags & STALE))
 175                         commit_list_insert_by_date(commit, result);
 176         }
 177         return 0;
 178 }
 179
 180 int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result)
 181 {
 182         struct commit_list *i, *j, *k;
 183
 184         if (!in)
 185                 return 0;
 186
 187         commit_list_insert(in->item, result);
 188
 189         for (i = in->next; i; i = i->next) {
 190                 struct commit_list *new_commits = NULL, *end = NULL;
 191
 192                 for (j = *result; j; j = j->next) {
 193                         struct commit_list *bases = NULL;
 194                         if (repo_get_merge_bases(the_repository, i->item,
 195                                                  j->item, &bases) < 0) {
 196                                 free_commit_list(bases);
 197                                 free_commit_list(*result);
 198                                 *result = NULL;
 199                                 return -1;
 200                         }
 201                         if (!new_commits)
 202                                 new_commits = bases;
 203                         else
 204                                 end->next = bases;
 205                         for (k = bases; k; k = k->next)
 206                                 end = k;
 207                 }
 208                 free_commit_list(*result);
 209                 *result = new_commits;
 210         }
 211         return 0;
 212 }
 213
 214 static int remove_redundant_no_gen(struct repository *r,
 215                                    struct commit **array, int cnt)
 216 {
 217         struct commit **work;
 218         unsigned char *redundant;
 219         int *filled_index;
 220         int i, j, filled;
 221
 222         CALLOC_ARRAY(work, cnt);
 223         redundant = xcalloc(cnt, 1);
 224         ALLOC_ARRAY(filled_index, cnt - 1);
 225
 226         for (i = 0; i < cnt; i++)
 227                 repo_parse_commit(r, array[i]);
 228         for (i = 0; i < cnt; i++) {
 229                 struct commit_list *common = NULL;
 230                 timestamp_t min_generation = commit_graph_generation(array[i]);
 231
 232                 if (redundant[i])
 233                         continue;
 234                 for (j = filled = 0; j < cnt; j++) {
 235                         timestamp_t curr_generation;
 236                         if (i == j || redundant[j])
 237                                 continue;
 238                         filled_index[filled] = j;
 239                         work[filled++] = array[j];
 240
 241                         curr_generation = commit_graph_generation(array[j]);
 242                         if (curr_generation < min_generation)
 243                                 min_generation = curr_generation;
 244                 }
 245                 if (paint_down_to_common(r, array[i], filled,
 246                                          work, min_generation, 0, &common)) {
 247                         clear_commit_marks(array[i], all_flags);
 248                         clear_commit_marks_many(filled, work, all_flags);
 249                         free_commit_list(common);
 250                         free(work);
 251                         free(redundant);
 252                         free(filled_index);
 253                         return -1;
 254                 }
 255                 if (array[i]->object.flags & PARENT2)
 256                         redundant[i] = 1;
 257                 for (j = 0; j < filled; j++)
 258                         if (work[j]->object.flags & PARENT1)
 259                                 redundant[filled_index[j]] = 1;
 260                 clear_commit_marks(array[i], all_flags);
 261                 clear_commit_marks_many(filled, work, all_flags);
 262                 free_commit_list(common);
 263         }
 264
 265         /* Now collect the result */
 266         COPY_ARRAY(work, array, cnt);
 267         for (i = filled = 0; i < cnt; i++)
 268                 if (!redundant[i])
 269                         array[filled++] = work[i];
 270         free(work);
 271         free(redundant);
 272         free(filled_index);
 273         return filled;
 274 }
 275
 276 static int remove_redundant_with_gen(struct repository *r,
 277                                      struct commit **array, int cnt)
 278 {
 279         int i, count_non_stale = 0, count_still_independent = cnt;
 280         timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
 281         struct commit **walk_start, **sorted;
 282         size_t walk_start_nr = 0, walk_start_alloc = cnt;
 283         int min_gen_pos = 0;
 284
 285         /*
 286          * Sort the input by generation number, ascending. This allows
 287          * us to increase the "min_generation" limit when we discover
 288          * the commit with lowest generation is STALE. The index
 289          * min_gen_pos points to the current position within 'array'
 290          * that is not yet known to be STALE.
 291          */
 292         DUP_ARRAY(sorted, array, cnt);
 293         QSORT(sorted, cnt, compare_commits_by_gen);
 294         min_generation = commit_graph_generation(sorted[0]);
 295
 296         ALLOC_ARRAY(walk_start, walk_start_alloc);
 297
 298         /* Mark all parents of the input as STALE */
 299         for (i = 0; i < cnt; i++) {
 300                 struct commit_list *parents;
 301
 302                 repo_parse_commit(r, array[i]);
 303                 array[i]->object.flags |= RESULT;
 304                 parents = array[i]->parents;
 305
 306                 while (parents) {
 307                         repo_parse_commit(r, parents->item);
 308                         if (!(parents->item->object.flags & STALE)) {
 309                                 parents->item->object.flags |= STALE;
 310                                 ALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);
 311                                 walk_start[walk_start_nr++] = parents->item;
 312                         }
 313                         parents = parents->next;
 314                 }
 315         }
 316
 317         QSORT(walk_start, walk_start_nr, compare_commits_by_gen);
 318
 319         /* remove STALE bit for now to allow walking through parents */
 320         for (i = 0; i < walk_start_nr; i++)
 321                 walk_start[i]->object.flags &= ~STALE;
 322
 323         /*
 324          * Start walking from the highest generation. Hopefully, it will
 325          * find all other items during the first-parent walk, and we can
 326          * terminate early. Otherwise, we will do the same amount of work
 327          * as before.
 328          */
 329         for (i = walk_start_nr - 1; i >= 0 && count_still_independent > 1; i--) {
 330                 /* push the STALE bits up to min generation */
 331                 struct commit_list *stack = NULL;
 332
 333                 commit_list_insert(walk_start[i], &stack);
 334                 walk_start[i]->object.flags |= STALE;
 335
 336                 while (stack) {
 337                         struct commit_list *parents;
 338                         struct commit *c = stack->item;
 339
 340                         repo_parse_commit(r, c);
 341
 342                         if (c->object.flags & RESULT) {
 343                                 c->object.flags &= ~RESULT;
 344                                 if (--count_still_independent <= 1)
 345                                         break;
 346                                 if (oideq(&c->object.oid, &sorted[min_gen_pos]->object.oid)) {
 347                                         while (min_gen_pos < cnt - 1 &&
 348                                                (sorted[min_gen_pos]->object.flags & STALE))
 349                                                 min_gen_pos++;
 350                                         min_generation = commit_graph_generation(sorted[min_gen_pos]);
 351                                 }
 352                         }
 353
 354                         if (commit_graph_generation(c) < min_generation) {
 355                                 pop_commit(&stack);
 356                                 continue;
 357                         }
 358
 359                         parents = c->parents;
 360                         while (parents) {
 361                                 if (!(parents->item->object.flags & STALE)) {
 362                                         parents->item->object.flags |= STALE;
 363                                         commit_list_insert(parents->item, &stack);
 364                                         break;
 365                                 }
 366                                 parents = parents->next;
 367                         }
 368
 369                         /* pop if all parents have been visited already */
 370                         if (!parents)
 371                                 pop_commit(&stack);
 372                 }
 373                 free_commit_list(stack);
 374         }
 375         free(sorted);
 376
 377         /* clear result */
 378         for (i = 0; i < cnt; i++)
 379                 array[i]->object.flags &= ~RESULT;
 380
 381         /* rearrange array */
 382         for (i = count_non_stale = 0; i < cnt; i++) {
 383                 if (!(array[i]->object.flags & STALE))
 384                         array[count_non_stale++] = array[i];
 385         }
 386
 387         /* clear marks */
 388         clear_commit_marks_many(walk_start_nr, walk_start, STALE);
 389         free(walk_start);
 390
 391         return count_non_stale;
 392 }
 393
 394 static int remove_redundant(struct repository *r, struct commit **array, int cnt)
 395 {
 396         /*
 397          * Some commit in the array may be an ancestor of
 398          * another commit.  Move the independent commits to the
 399          * beginning of 'array' and return their number. Callers
 400          * should not rely upon the contents of 'array' after
 401          * that number.
 402          */
 403         if (generation_numbers_enabled(r)) {
 404                 int i;
 405
 406                 /*
 407                  * If we have a single commit with finite generation
 408                  * number, then the _with_gen algorithm is preferred.
 409                  */
 410                 for (i = 0; i < cnt; i++) {
 411                         if (commit_graph_generation(array[i]) < GENERATION_NUMBER_INFINITY)
 412                                 return remove_redundant_with_gen(r, array, cnt);
 413                 }
 414         }
 415
 416         return remove_redundant_no_gen(r, array, cnt);
 417 }
 418
 419 static int get_merge_bases_many_0(struct repository *r,
 420                                   struct commit *one,
 421                                   int n,
 422                                   struct commit **twos,
 423                                   int cleanup,
 424                                   struct commit_list **result)
 425 {
 426         struct commit_list *list;
 427         struct commit **rslt;
 428         int cnt, i;
 429
 430         if (merge_bases_many(r, one, n, twos, result) < 0)
 431                 return -1;
 432         for (i = 0; i < n; i++) {
 433                 if (one == twos[i])
 434                         return 0;
 435         }
 436         if (!*result || !(*result)->next) {
 437                 if (cleanup) {
 438                         clear_commit_marks(one, all_flags);
 439                         clear_commit_marks_many(n, twos, all_flags);
 440                 }
 441                 return 0;
 442         }
 443
 444         /* There are more than one */
 445         cnt = commit_list_count(*result);
 446         CALLOC_ARRAY(rslt, cnt);
 447         for (list = *result, i = 0; list; list = list->next)
 448                 rslt[i++] = list->item;
 449         free_commit_list(*result);
 450         *result = NULL;
 451
 452         clear_commit_marks(one, all_flags);
 453         clear_commit_marks_many(n, twos, all_flags);
 454
 455         cnt = remove_redundant(r, rslt, cnt);
 456         if (cnt < 0) {
 457                 free(rslt);
 458                 return -1;
 459         }
 460         for (i = 0; i < cnt; i++)
 461                 commit_list_insert_by_date(rslt[i], result);
 462         free(rslt);
 463         return 0;
 464 }
 465
 466 int repo_get_merge_bases_many(struct repository *r,
 467                               struct commit *one,
 468                               int n,
 469                               struct commit **twos,
 470                               struct commit_list **result)
 471 {
 472         return get_merge_bases_many_0(r, one, n, twos, 1, result);
 473 }
 474
 475 int repo_get_merge_bases_many_dirty(struct repository *r,
 476                                     struct commit *one,
 477                                     int n,
 478                                     struct commit **twos,
 479                                     struct commit_list **result)
 480 {
 481         return get_merge_bases_many_0(r, one, n, twos, 0, result);
 482 }
 483
 484 int repo_get_merge_bases(struct repository *r,
 485                          struct commit *one,
 486                          struct commit *two,
 487                          struct commit_list **result)
 488 {
 489         return get_merge_bases_many_0(r, one, 1, &two, 1, result);
 490 }
 491
 492 /*
 493  * Is "commit" a descendant of one of the elements on the "with_commit" list?
 494  */
 495 int repo_is_descendant_of(struct repository *r,
 496                           struct commit *commit,
 497                           struct commit_list *with_commit)
 498 {
 499         if (!with_commit)
 500                 return 1;
 501
 502         if (generation_numbers_enabled(r)) {
 503                 struct commit_list *from_list = NULL;
 504                 int result;
 505                 commit_list_insert(commit, &from_list);
 506                 result = can_all_from_reach(from_list, with_commit, 0);
 507                 free_commit_list(from_list);
 508                 return result;
 509         } else {
 510                 while (with_commit) {
 511                         struct commit *other;
 512                         int ret;
 513
 514                         other = with_commit->item;
 515                         with_commit = with_commit->next;
 516                         ret = repo_in_merge_bases_many(r, other, 1, &commit, 0);
 517                         if (ret)
 518                                 return ret;
 519                 }
 520                 return 0;
 521         }
 522 }
 523
 524 /*
 525  * Is "commit" an ancestor of one of the "references"?
 526  */
 527 int repo_in_merge_bases_many(struct repository *r, struct commit *commit,
 528                              int nr_reference, struct commit **reference,
 529                              int ignore_missing_commits)
 530 {
 531         struct commit_list *bases = NULL;
 532         int ret = 0, i;
 533         timestamp_t generation, max_generation = GENERATION_NUMBER_ZERO;
 534
 535         if (repo_parse_commit(r, commit))
 536                 return ignore_missing_commits ? 0 : -1;
 537         for (i = 0; i < nr_reference; i++) {
 538                 if (repo_parse_commit(r, reference[i]))
 539                         return ignore_missing_commits ? 0 : -1;
 540
 541                 generation = commit_graph_generation(reference[i]);
 542                 if (generation > max_generation)
 543                         max_generation = generation;
 544         }
 545
 546         generation = commit_graph_generation(commit);
 547         if (generation > max_generation)
 548                 return ret;
 549
 550         if (paint_down_to_common(r, commit,
 551                                  nr_reference, reference,
 552                                  generation, ignore_missing_commits, &bases))
 553                 ret = -1;
 554         else if (commit->object.flags & PARENT2)
 555                 ret = 1;
 556         clear_commit_marks(commit, all_flags);
 557         clear_commit_marks_many(nr_reference, reference, all_flags);
 558         free_commit_list(bases);
 559         return ret;
 560 }
 561
 562 /*
 563  * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
 564  */
 565 int repo_in_merge_bases(struct repository *r,
 566                         struct commit *commit,
 567                         struct commit *reference)
 568 {
 569         int res;
 570         struct commit_list *list = NULL;
 571         struct commit_list **next = &list;
 572
 573         next = commit_list_append(commit, next);
 574         res = repo_is_descendant_of(r, reference, list);
 575         free_commit_list(list);
 576
 577         return res;
 578 }
 579
 580 struct commit_list *reduce_heads(struct commit_list *heads)
 581 {
 582         struct commit_list *p;
 583         struct commit_list *result = NULL, **tail = &result;
 584         struct commit **array;
 585         int num_head, i;
 586
 587         if (!heads)
 588                 return NULL;
 589
 590         /* Uniquify */
 591         for (p = heads; p; p = p->next)
 592                 p->item->object.flags &= ~STALE;
 593         for (p = heads, num_head = 0; p; p = p->next) {
 594                 if (p->item->object.flags & STALE)
 595                         continue;
 596                 p->item->object.flags |= STALE;
 597                 num_head++;
 598         }
 599         CALLOC_ARRAY(array, num_head);
 600         for (p = heads, i = 0; p; p = p->next) {
 601                 if (p->item->object.flags & STALE) {
 602                         array[i++] = p->item;
 603                         p->item->object.flags &= ~STALE;
 604                 }
 605         }
 606         num_head = remove_redundant(the_repository, array, num_head);
 607         if (num_head < 0) {
 608                 free(array);
 609                 return NULL;
 610         }
 611         for (i = 0; i < num_head; i++)
 612                 tail = &commit_list_insert(array[i], tail)->next;
 613         free(array);
 614         return result;
 615 }
 616
 617 void reduce_heads_replace(struct commit_list **heads)
 618 {
 619         struct commit_list *result = reduce_heads(*heads);
 620         free_commit_list(*heads);
 621         *heads = result;
 622 }
 623
 624 int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
 625 {
 626         struct object *o;
 627         struct commit *old_commit, *new_commit;
 628         struct commit_list *old_commit_list = NULL;
 629         int ret;
 630
 631         /*
 632          * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
 633          * old_commit.  Otherwise we require --force.
 634          */
 635         o = deref_tag(the_repository, parse_object(the_repository, old_oid),
 636                       NULL, 0);
 637         if (!o || o->type != OBJ_COMMIT)
 638                 return 0;
 639         old_commit = (struct commit *) o;
 640
 641         o = deref_tag(the_repository, parse_object(the_repository, new_oid),
 642                       NULL, 0);
 643         if (!o || o->type != OBJ_COMMIT)
 644                 return 0;
 645         new_commit = (struct commit *) o;
 646
 647         if (repo_parse_commit(the_repository, new_commit) < 0)
 648                 return 0;
 649
 650         commit_list_insert(old_commit, &old_commit_list);
 651         ret = repo_is_descendant_of(the_repository,
 652                                     new_commit, old_commit_list);
 653         if (ret < 0)
 654                 exit(128);
 655         free_commit_list(old_commit_list);
 656         return ret;
 657 }
 658
 659 /*
 660  * Mimicking the real stack, this stack lives on the heap, avoiding stack
 661  * overflows.
 662  *
 663  * At each recursion step, the stack items points to the commits whose
 664  * ancestors are to be inspected.
 665  */
 666 struct contains_stack {
 667         int nr, alloc;
 668         struct contains_stack_entry {
 669                 struct commit *commit;
 670                 struct commit_list *parents;
 671         } *contains_stack;
 672 };
 673
 674 static int in_commit_list(const struct commit_list *want, struct commit *c)
 675 {
 676         for (; want; want = want->next)
 677                 if (oideq(&want->item->object.oid, &c->object.oid))
 678                         return 1;
 679         return 0;
 680 }
 681
 682 /*
 683  * Test whether the candidate is contained in the list.
 684  * Do not recurse to find out, though, but return -1 if inconclusive.
 685  */
 686 static enum contains_result contains_test(struct commit *candidate,
 687                                           const struct commit_list *want,
 688                                           struct contains_cache *cache,
 689                                           timestamp_t cutoff)
 690 {
 691         enum contains_result *cached = contains_cache_at(cache, candidate);
 692
 693         /* If we already have the answer cached, return that. */
 694         if (*cached)
 695                 return *cached;
 696
 697         /* or are we it? */
 698         if (in_commit_list(want, candidate)) {
 699                 *cached = CONTAINS_YES;
 700                 return CONTAINS_YES;
 701         }
 702
 703         /* Otherwise, we don't know; prepare to recurse */
 704         parse_commit_or_die(candidate);
 705
 706         if (commit_graph_generation(candidate) < cutoff)
 707                 return CONTAINS_NO;
 708
 709         return CONTAINS_UNKNOWN;
 710 }
 711
 712 static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)
 713 {
 714         ALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc);
 715         contains_stack->contains_stack[contains_stack->nr].commit = candidate;
 716         contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
 717 }
 718
 719 static enum contains_result contains_tag_algo(struct commit *candidate,
 720                                               const struct commit_list *want,
 721                                               struct contains_cache *cache)
 722 {
 723         struct contains_stack contains_stack = { 0, 0, NULL };
 724         enum contains_result result;
 725         timestamp_t cutoff = GENERATION_NUMBER_INFINITY;
 726         const struct commit_list *p;
 727
 728         for (p = want; p; p = p->next) {
 729                 timestamp_t generation;
 730                 struct commit *c = p->item;
 731                 load_commit_graph_info(the_repository, c);
 732                 generation = commit_graph_generation(c);
 733                 if (generation < cutoff)
 734                         cutoff = generation;
 735         }
 736
 737         result = contains_test(candidate, want, cache, cutoff);
 738         if (result != CONTAINS_UNKNOWN)
 739                 return result;
 740
 741         push_to_contains_stack(candidate, &contains_stack);
 742         while (contains_stack.nr) {
 743                 struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
 744                 struct commit *commit = entry->commit;
 745                 struct commit_list *parents = entry->parents;
 746
 747                 if (!parents) {
 748                         *contains_cache_at(cache, commit) = CONTAINS_NO;
 749                         contains_stack.nr--;
 750                 }
 751                 /*
 752                  * If we just popped the stack, parents->item has been marked,
 753                  * therefore contains_test will return a meaningful yes/no.
 754                  */
 755                 else switch (contains_test(parents->item, want, cache, cutoff)) {
 756                 case CONTAINS_YES:
 757                         *contains_cache_at(cache, commit) = CONTAINS_YES;
 758                         contains_stack.nr--;
 759                         break;
 760                 case CONTAINS_NO:
 761                         entry->parents = parents->next;
 762                         break;
 763                 case CONTAINS_UNKNOWN:
 764                         push_to_contains_stack(parents->item, &contains_stack);
 765                         break;
 766                 }
 767         }
 768         free(contains_stack.contains_stack);
 769         return contains_test(candidate, want, cache, cutoff);
 770 }
 771
 772 int commit_contains(struct ref_filter *filter, struct commit *commit,
 773                     struct commit_list *list, struct contains_cache *cache)
 774 {
 775         if (filter->with_commit_tag_algo)
 776                 return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
 777         return repo_is_descendant_of(the_repository, commit, list);
 778 }
 779
 780 int can_all_from_reach_with_flag(struct object_array *from,
 781                                  unsigned int with_flag,
 782                                  unsigned int assign_flag,
 783                                  time_t min_commit_date,
 784                                  timestamp_t min_generation)
 785 {
 786         struct commit **list = NULL;
 787         int i;
 788         int nr_commits;
 789         int result = 1;
 790
 791         ALLOC_ARRAY(list, from->nr);
 792         nr_commits = 0;
 793         for (i = 0; i < from->nr; i++) {
 794                 struct object *from_one = from->objects[i].item;
 795
 796                 if (!from_one || from_one->flags & assign_flag)
 797                         continue;
 798
 799                 from_one = deref_tag(the_repository, from_one,
 800                                      "a from object", 0);
 801                 if (!from_one || from_one->type != OBJ_COMMIT) {
 802                         /*
 803                          * no way to tell if this is reachable by
 804                          * looking at the ancestry chain alone, so
 805                          * leave a note to ourselves not to worry about
 806                          * this object anymore.
 807                          */
 808                         from->objects[i].item->flags |= assign_flag;
 809                         continue;
 810                 }
 811
 812                 list[nr_commits] = (struct commit *)from_one;
 813                 if (repo_parse_commit(the_repository, list[nr_commits]) ||
 814                     commit_graph_generation(list[nr_commits]) < min_generation) {
 815                         result = 0;
 816                         goto cleanup;
 817                 }
 818
 819                 nr_commits++;
 820         }
 821
 822         QSORT(list, nr_commits, compare_commits_by_gen);
 823
 824         for (i = 0; i < nr_commits; i++) {
 825                 /* DFS from list[i] */
 826                 struct commit_list *stack = NULL;
 827
 828                 list[i]->object.flags |= assign_flag;
 829                 commit_list_insert(list[i], &stack);
 830
 831                 while (stack) {
 832                         struct commit_list *parent;
 833
 834                         if (stack->item->object.flags & (with_flag | RESULT)) {
 835                                 pop_commit(&stack);
 836                                 if (stack)
 837                                         stack->item->object.flags |= RESULT;
 838                                 continue;
 839                         }
 840
 841                         for (parent = stack->item->parents; parent; parent = parent->next) {
 842                                 if (parent->item->object.flags & (with_flag | RESULT))
 843                                         stack->item->object.flags |= RESULT;
 844
 845                                 if (!(parent->item->object.flags & assign_flag)) {
 846                                         parent->item->object.flags |= assign_flag;
 847
 848                                         if (repo_parse_commit(the_repository, parent->item) ||
 849                                             parent->item->date < min_commit_date ||
 850                                             commit_graph_generation(parent->item) < min_generation)
 851                                                 continue;
 852
 853                                         commit_list_insert(parent->item, &stack);
 854                                         break;
 855                                 }
 856                         }
 857
 858                         if (!parent)
 859                                 pop_commit(&stack);
 860                 }
 861
 862                 if (!(list[i]->object.flags & (with_flag | RESULT))) {
 863                         result = 0;
 864                         goto cleanup;
 865                 }
 866         }
 867
 868 cleanup:
 869         clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
 870         free(list);
 871
 872         for (i = 0; i < from->nr; i++) {
 873                 struct object *from_one = from->objects[i].item;
 874
 875                 if (from_one)
 876                         from_one->flags &= ~assign_flag;
 877         }
 878
 879         return result;
 880 }
 881
 882 int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 883                        int cutoff_by_min_date)
 884 {
 885         struct object_array from_objs = OBJECT_ARRAY_INIT;
 886         time_t min_commit_date = cutoff_by_min_date ? from->item->date : 0;
 887         struct commit_list *from_iter = from, *to_iter = to;
 888         int result;
 889         timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
 890
 891         while (from_iter) {
 892                 add_object_array(&from_iter->item->object, NULL, &from_objs);
 893
 894                 if (!repo_parse_commit(the_repository, from_iter->item)) {
 895                         timestamp_t generation;
 896                         if (from_iter->item->date < min_commit_date)
 897                                 min_commit_date = from_iter->item->date;
 898
 899                         generation = commit_graph_generation(from_iter->item);
 900                         if (generation < min_generation)
 901                                 min_generation = generation;
 902                 }
 903
 904                 from_iter = from_iter->next;
 905         }
 906
 907         while (to_iter) {
 908                 if (!repo_parse_commit(the_repository, to_iter->item)) {
 909                         timestamp_t generation;
 910                         if (to_iter->item->date < min_commit_date)
 911                                 min_commit_date = to_iter->item->date;
 912
 913                         generation = commit_graph_generation(to_iter->item);
 914                         if (generation < min_generation)
 915                                 min_generation = generation;
 916                 }
 917
 918                 to_iter->item->object.flags |= PARENT2;
 919
 920                 to_iter = to_iter->next;
 921         }
 922
 923         result = can_all_from_reach_with_flag(&from_objs, PARENT2, PARENT1,
 924                                               min_commit_date, min_generation);
 925
 926         while (from) {
 927                 clear_commit_marks(from->item, PARENT1);
 928                 from = from->next;
 929         }
 930
 931         while (to) {
 932                 clear_commit_marks(to->item, PARENT2);
 933                 to = to->next;
 934         }
 935
 936         object_array_clear(&from_objs);
 937         return result;
 938 }
 939
 940 struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
 941                                          struct commit **to, int nr_to,
 942                                          unsigned int reachable_flag)
 943 {
 944         struct commit **item;
 945         struct commit *current;
 946         struct commit_list *found_commits = NULL;
 947         struct commit **to_last = to + nr_to;
 948         struct commit **from_last = from + nr_from;
 949         timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
 950         int num_to_find = 0;
 951
 952         struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
 953
 954         for (item = to; item < to_last; item++) {
 955                 timestamp_t generation;
 956                 struct commit *c = *item;
 957
 958                 repo_parse_commit(the_repository, c);
 959                 generation = commit_graph_generation(c);
 960                 if (generation < min_generation)
 961                         min_generation = generation;
 962
 963                 if (!(c->object.flags & PARENT1)) {
 964                         c->object.flags |= PARENT1;
 965                         num_to_find++;
 966                 }
 967         }
 968
 969         for (item = from; item < from_last; item++) {
 970                 struct commit *c = *item;
 971                 if (!(c->object.flags & PARENT2)) {
 972                         c->object.flags |= PARENT2;
 973                         repo_parse_commit(the_repository, c);
 974
 975                         prio_queue_put(&queue, *item);
 976                 }
 977         }
 978
 979         while (num_to_find && (current = prio_queue_get(&queue)) != NULL) {
 980                 struct commit_list *parents;
 981
 982                 if (current->object.flags & PARENT1) {
 983                         current->object.flags &= ~PARENT1;
 984                         current->object.flags |= reachable_flag;
 985                         commit_list_insert(current, &found_commits);
 986                         num_to_find--;
 987                 }
 988
 989                 for (parents = current->parents; parents; parents = parents->next) {
 990                         struct commit *p = parents->item;
 991
 992                         repo_parse_commit(the_repository, p);
 993
 994                         if (commit_graph_generation(p) < min_generation)
 995                                 continue;
 996
 997                         if (p->object.flags & PARENT2)
 998                                 continue;
 999
1000                         p->object.flags |= PARENT2;
1001                         prio_queue_put(&queue, p);
1002                 }
1003         }
1004
1005         clear_prio_queue(&queue);
1006
1007         clear_commit_marks_many(nr_to, to, PARENT1);
1008         clear_commit_marks_many(nr_from, from, PARENT2);
1009
1010         return found_commits;
1011 }
1012
1013 define_commit_slab(bit_arrays, struct bitmap *);
1014 static struct bit_arrays bit_arrays;
1015
1016 static void insert_no_dup(struct prio_queue *queue, struct commit *c)
1017 {
1018         if (c->object.flags & PARENT2)
1019                 return;
1020         prio_queue_put(queue, c);
1021         c->object.flags |= PARENT2;
1022 }
1023
1024 static struct bitmap *get_bit_array(struct commit *c, int width)
1025 {
1026         struct bitmap **bitmap = bit_arrays_at(&bit_arrays, c);
1027         if (!*bitmap)
1028                 *bitmap = bitmap_word_alloc(width);
1029         return *bitmap;
1030 }
1031
1032 static void free_bit_array(struct commit *c)
1033 {
1034         struct bitmap **bitmap = bit_arrays_at(&bit_arrays, c);
1035         if (!*bitmap)
1036                 return;
1037         bitmap_free(*bitmap);
1038         *bitmap = NULL;
1039 }
1040
1041 void ahead_behind(struct repository *r,
1042                   struct commit **commits, size_t commits_nr,
1043                   struct ahead_behind_count *counts, size_t counts_nr)
1044 {
1045         struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
1046         size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);
1047
1048         if (!commits_nr || !counts_nr)
1049                 return;
1050
1051         for (size_t i = 0; i < counts_nr; i++) {
1052                 counts[i].ahead = 0;
1053                 counts[i].behind = 0;
1054         }
1055
1056         ensure_generations_valid(r, commits, commits_nr);
1057
1058         init_bit_arrays(&bit_arrays);
1059
1060         for (size_t i = 0; i < commits_nr; i++) {
1061                 struct commit *c = commits[i];
1062                 struct bitmap *bitmap = get_bit_array(c, width);
1063
1064                 bitmap_set(bitmap, i);
1065                 insert_no_dup(&queue, c);
1066         }
1067
1068         while (queue_has_nonstale(&queue)) {
1069                 struct commit *c = prio_queue_get(&queue);
1070                 struct commit_list *p;
1071                 struct bitmap *bitmap_c = get_bit_array(c, width);
1072
1073                 for (size_t i = 0; i < counts_nr; i++) {
1074                         int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);
1075                         int reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);
1076
1077                         if (reach_from_tip ^ reach_from_base) {
1078                                 if (reach_from_base)
1079                                         counts[i].behind++;
1080                                 else
1081                                         counts[i].ahead++;
1082                         }
1083                 }
1084
1085                 for (p = c->parents; p; p = p->next) {
1086                         struct bitmap *bitmap_p;
1087
1088                         repo_parse_commit(r, p->item);
1089
1090                         bitmap_p = get_bit_array(p->item, width);
1091                         bitmap_or(bitmap_p, bitmap_c);
1092
1093                         /*
1094                          * If this parent is reachable from every starting
1095                          * commit, then none of its ancestors can contribute
1096                          * to the ahead/behind count. Mark it as STALE, so
1097                          * we can stop the walk when every commit in the
1098                          * queue is STALE.
1099                          */
1100                         if (bitmap_popcount(bitmap_p) == commits_nr)
1101                                 p->item->object.flags |= STALE;
1102
1103                         insert_no_dup(&queue, p->item);
1104                 }
1105
1106                 free_bit_array(c);
1107         }
1108
1109         /* STALE is used here, PARENT2 is used by insert_no_dup(). */
1110         repo_clear_commit_marks(r, PARENT2 | STALE);
1111         while (prio_queue_peek(&queue)) {
1112                 struct commit *c = prio_queue_get(&queue);
1113                 free_bit_array(c);
1114         }
1115         clear_bit_arrays(&bit_arrays);
1116         clear_prio_queue(&queue);
1117 }
1118
1119 struct commit_and_index {
1120         struct commit *commit;
1121         unsigned int index;
1122         timestamp_t generation;
1123 };
1124
1125 static int compare_commit_and_index_by_generation(const void *va, const void *vb)
1126 {
1127         const struct commit_and_index *a = (const struct commit_and_index *)va;
1128         const struct commit_and_index *b = (const struct commit_and_index *)vb;
1129
1130         if (a->generation > b->generation)
1131                 return 1;
1132         if (a->generation < b->generation)
1133                 return -1;
1134         return 0;
1135 }
1136
1137 void tips_reachable_from_bases(struct repository *r,
1138                                struct commit_list *bases,
1139                                struct commit **tips, size_t tips_nr,
1140                                int mark)
1141 {
1142         struct commit_and_index *commits;
1143         size_t min_generation_index = 0;
1144         timestamp_t min_generation;
1145         struct commit_list *stack = NULL;
1146
1147         if (!bases || !tips || !tips_nr)
1148                 return;
1149
1150         /*
1151          * Do a depth-first search starting at 'bases' to search for the
1152          * tips. Stop at the lowest (un-found) generation number. When
1153          * finding the lowest commit, increase the minimum generation
1154          * number to the next lowest (un-found) generation number.
1155          */
1156
1157         CALLOC_ARRAY(commits, tips_nr);
1158
1159         for (size_t i = 0; i < tips_nr; i++) {
1160                 commits[i].commit = tips[i];
1161                 commits[i].index = i;
1162                 commits[i].generation = commit_graph_generation(tips[i]);
1163         }
1164
1165         /* Sort with generation number ascending. */
1166         QSORT(commits, tips_nr, compare_commit_and_index_by_generation);
1167         min_generation = commits[0].generation;
1168
1169         while (bases) {
1170                 repo_parse_commit(r, bases->item);
1171                 commit_list_insert(bases->item, &stack);
1172                 bases = bases->next;
1173         }
1174
1175         while (stack) {
1176                 int explored_all_parents = 1;
1177                 struct commit_list *p;
1178                 struct commit *c = stack->item;
1179                 timestamp_t c_gen = commit_graph_generation(c);
1180
1181                 /* Does it match any of our tips? */
1182                 for (size_t j = min_generation_index; j < tips_nr; j++) {
1183                         if (c_gen < commits[j].generation)
1184                                 break;
1185
1186                         if (commits[j].commit == c) {
1187                                 tips[commits[j].index]->object.flags |= mark;
1188
1189                                 if (j == min_generation_index) {
1190                                         unsigned int k = j + 1;
1191                                         while (k < tips_nr &&
1192                                                (tips[commits[k].index]->object.flags & mark))
1193                                                 k++;
1194
1195                                         /* Terminate early if all found. */
1196                                         if (k >= tips_nr)
1197                                                 goto done;
1198
1199                                         min_generation_index = k;
1200                                         min_generation = commits[k].generation;
1201                                 }
1202                         }
1203                 }
1204
1205                 for (p = c->parents; p; p = p->next) {
1206                         repo_parse_commit(r, p->item);
1207
1208                         /* Have we already explored this parent? */
1209                         if (p->item->object.flags & SEEN)
1210                                 continue;
1211
1212                         /* Is it below the current minimum generation? */
1213                         if (commit_graph_generation(p->item) < min_generation)
1214                                 continue;
1215
1216                         /* Ok, we will explore from here on. */
1217                         p->item->object.flags |= SEEN;
1218                         explored_all_parents = 0;
1219                         commit_list_insert(p->item, &stack);
1220                         break;
1221                 }
1222
1223                 if (explored_all_parents)
1224                         pop_commit(&stack);
1225         }
1226
1227 done:
1228         free(commits);
1229         repo_clear_commit_marks(r, SEEN);
1230         free_commit_list(stack);
1231 }