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