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