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