1/* 2 * Copyright (c) 2005, Jon Seymour 3 * 4 * For more information about epoch theory on which this module is based, 5 * refer to http://blackcubes.dyndns.org/epoch/. That web page defines 6 * terms such as "epoch" and "minimal, non-linear epoch" and provides rationales 7 * for some of the algorithms used here. 8 * 9 */ 10#include <stdlib.h> 11 12/* Provides arbitrary precision integers required to accurately represent 13 * fractional mass: */ 14#include <openssl/bn.h> 15 16#include "cache.h" 17#include "commit.h" 18#include "epoch.h" 19 20struct fraction { 21 BIGNUM numerator; 22 BIGNUM denominator; 23}; 24 25#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next) 26 27static BN_CTX *context = NULL; 28static struct fraction *one = NULL; 29static struct fraction *zero = NULL; 30 31static BN_CTX *get_BN_CTX() 32{ 33 if (!context) { 34 context = BN_CTX_new(); 35 } 36 return context; 37} 38 39static struct fraction *new_zero() 40{ 41 struct fraction *result = xmalloc(sizeof(*result)); 42 BN_init(&result->numerator); 43 BN_init(&result->denominator); 44 BN_zero(&result->numerator); 45 BN_one(&result->denominator); 46 return result; 47} 48 49static void clear_fraction(struct fraction *fraction) 50{ 51 BN_clear(&fraction->numerator); 52 BN_clear(&fraction->denominator); 53} 54 55static struct fraction *divide(struct fraction *result, struct fraction *fraction, int divisor) 56{ 57 BIGNUM bn_divisor; 58 59 BN_init(&bn_divisor); 60 BN_set_word(&bn_divisor, divisor); 61 62 BN_copy(&result->numerator, &fraction->numerator); 63 BN_mul(&result->denominator, &fraction->denominator, &bn_divisor, get_BN_CTX()); 64 65 BN_clear(&bn_divisor); 66 return result; 67} 68 69static struct fraction *init_fraction(struct fraction *fraction) 70{ 71 BN_init(&fraction->numerator); 72 BN_init(&fraction->denominator); 73 BN_zero(&fraction->numerator); 74 BN_one(&fraction->denominator); 75 return fraction; 76} 77 78static struct fraction *get_one() 79{ 80 if (!one) { 81 one = new_zero(); 82 BN_one(&one->numerator); 83 } 84 return one; 85} 86 87static struct fraction *get_zero() 88{ 89 if (!zero) { 90 zero = new_zero(); 91 } 92 return zero; 93} 94 95static struct fraction *copy(struct fraction *to, struct fraction *from) 96{ 97 BN_copy(&to->numerator, &from->numerator); 98 BN_copy(&to->denominator, &from->denominator); 99 return to; 100} 101 102static struct fraction *add(struct fraction *result, struct fraction *left, struct fraction *right) 103{ 104 BIGNUM a, b, gcd; 105 106 BN_init(&a); 107 BN_init(&b); 108 BN_init(&gcd); 109 110 BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX()); 111 BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX()); 112 BN_mul(&result->denominator, &left->denominator, &right->denominator, get_BN_CTX()); 113 BN_add(&result->numerator, &a, &b); 114 115 BN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX()); 116 BN_div(&result->denominator, NULL, &result->denominator, &gcd, get_BN_CTX()); 117 BN_div(&result->numerator, NULL, &result->numerator, &gcd, get_BN_CTX()); 118 119 BN_clear(&a); 120 BN_clear(&b); 121 BN_clear(&gcd); 122 123 return result; 124} 125 126static int compare(struct fraction *left, struct fraction *right) 127{ 128 BIGNUM a, b; 129 int result; 130 131 BN_init(&a); 132 BN_init(&b); 133 134 BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX()); 135 BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX()); 136 137 result = BN_cmp(&a, &b); 138 139 BN_clear(&a); 140 BN_clear(&b); 141 142 return result; 143} 144 145struct mass_counter { 146 struct fraction seen; 147 struct fraction pending; 148}; 149 150static struct mass_counter *new_mass_counter(struct commit *commit, struct fraction *pending) 151{ 152 struct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter)); 153 memset(mass_counter, 0, sizeof(*mass_counter)); 154 155 init_fraction(&mass_counter->seen); 156 init_fraction(&mass_counter->pending); 157 158 copy(&mass_counter->pending, pending); 159 copy(&mass_counter->seen, get_zero()); 160 161 if (commit->object.util) { 162 die("multiple attempts to initialize mass counter for %s", 163 sha1_to_hex(commit->object.sha1)); 164 } 165 166 commit->object.util = mass_counter; 167 168 return mass_counter; 169} 170 171static void free_mass_counter(struct mass_counter *counter) 172{ 173 clear_fraction(&counter->seen); 174 clear_fraction(&counter->pending); 175 free(counter); 176} 177 178/* 179 * Finds the base commit of a list of commits. 180 * 181 * One property of the commit being searched for is that every commit reachable 182 * from the base commit is reachable from the commits in the starting list only 183 * via paths that include the base commit. 184 * 185 * This algorithm uses a conservation of mass approach to find the base commit. 186 * 187 * We start by injecting one unit of mass into the graph at each 188 * of the commits in the starting list. Injecting mass into a commit 189 * is achieved by adding to its pending mass counter and, if it is not already 190 * enqueued, enqueuing the commit in a list of pending commits, in latest 191 * commit date first order. 192 * 193 * The algorithm then preceeds to visit each commit in the pending queue. 194 * Upon each visit, the pending mass is added to the mass already seen for that 195 * commit and then divided into N equal portions, where N is the number of 196 * parents of the commit being visited. The divided portions are then injected 197 * into each of the parents. 198 * 199 * The algorithm continues until we discover a commit which has seen all the 200 * mass originally injected or until we run out of things to do. 201 * 202 * If we find a commit that has seen all the original mass, we have found 203 * the common base of all the commits in the starting list. 204 * 205 * The algorithm does _not_ depend on accurate timestamps for correct operation. 206 * However, reasonably sane (e.g. non-random) timestamps are required in order 207 * to prevent an exponential performance characteristic. The occasional 208 * timestamp inaccuracy will not dramatically affect performance but may 209 * result in more nodes being processed than strictly necessary. 210 * 211 * This procedure sets *boundary to the address of the base commit. It returns 212 * non-zero if, and only if, there was a problem parsing one of the 213 * commits discovered during the traversal. 214 */ 215static int find_base_for_list(struct commit_list *list, struct commit **boundary) 216{ 217 int ret = 0; 218 struct commit_list *cleaner = NULL; 219 struct commit_list *pending = NULL; 220 struct fraction injected; 221 init_fraction(&injected); 222 *boundary = NULL; 223 224 for (; list; list = list->next) { 225 struct commit *item = list->item; 226 227 if (!item->object.util) { 228 new_mass_counter(list->item, get_one()); 229 add(&injected, &injected, get_one()); 230 231 commit_list_insert(list->item, &cleaner); 232 commit_list_insert(list->item, &pending); 233 } 234 } 235 236 while (!*boundary && pending && !ret) { 237 struct commit *latest = pop_commit(&pending); 238 struct mass_counter *latest_node = (struct mass_counter *) latest->object.util; 239 int num_parents; 240 241 if ((ret = parse_commit(latest))) 242 continue; 243 add(&latest_node->seen, &latest_node->seen, &latest_node->pending); 244 245 num_parents = count_parents(latest); 246 if (num_parents) { 247 struct fraction distribution; 248 struct commit_list *parents; 249 250 divide(init_fraction(&distribution), &latest_node->pending, num_parents); 251 252 for (parents = latest->parents; parents; parents = parents->next) { 253 struct commit *parent = parents->item; 254 struct mass_counter *parent_node = (struct mass_counter *) parent->object.util; 255 256 if (!parent_node) { 257 parent_node = new_mass_counter(parent, &distribution); 258 insert_by_date(&pending, parent); 259 commit_list_insert(parent, &cleaner); 260 } else { 261 if (!compare(&parent_node->pending, get_zero())) 262 insert_by_date(&pending, parent); 263 add(&parent_node->pending, &parent_node->pending, &distribution); 264 } 265 } 266 267 clear_fraction(&distribution); 268 } 269 270 if (!compare(&latest_node->seen, &injected)) 271 *boundary = latest; 272 copy(&latest_node->pending, get_zero()); 273 } 274 275 while (cleaner) { 276 struct commit *next = pop_commit(&cleaner); 277 free_mass_counter((struct mass_counter *) next->object.util); 278 next->object.util = NULL; 279 } 280 281 if (pending) 282 free_commit_list(pending); 283 284 clear_fraction(&injected); 285 return ret; 286} 287 288 289/* 290 * Finds the base of an minimal, non-linear epoch, headed at head, by 291 * applying the find_base_for_list to a list consisting of the parents 292 */ 293static int find_base(struct commit *head, struct commit **boundary) 294{ 295 int ret = 0; 296 struct commit_list *pending = NULL; 297 struct commit_list *next; 298 299 for (next = head->parents; next; next = next->next) { 300 commit_list_insert(next->item, &pending); 301 } 302 ret = find_base_for_list(pending, boundary); 303 free_commit_list(pending); 304 305 return ret; 306} 307 308/* 309 * This procedure traverses to the boundary of the first epoch in the epoch 310 * sequence of the epoch headed at head_of_epoch. This is either the end of 311 * the maximal linear epoch or the base of a minimal non-linear epoch. 312 * 313 * The queue of pending nodes is sorted in reverse date order and each node 314 * is currently in the queue at most once. 315 */ 316static int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary) 317{ 318 int ret; 319 struct commit *item = head_of_epoch; 320 321 ret = parse_commit(item); 322 if (ret) 323 return ret; 324 325 if (HAS_EXACTLY_ONE_PARENT(item)) { 326 /* 327 * We are at the start of a maximimal linear epoch. 328 * Traverse to the end. 329 */ 330 while (HAS_EXACTLY_ONE_PARENT(item) && !ret) { 331 item = item->parents->item; 332 ret = parse_commit(item); 333 } 334 *boundary = item; 335 336 } else { 337 /* 338 * Otherwise, we are at the start of a minimal, non-linear 339 * epoch - find the common base of all parents. 340 */ 341 ret = find_base(item, boundary); 342 } 343 344 return ret; 345} 346 347/* 348 * Returns non-zero if parent is known to be a parent of child. 349 */ 350static int is_parent_of(struct commit *parent, struct commit *child) 351{ 352 struct commit_list *parents; 353 for (parents = child->parents; parents; parents = parents->next) { 354 if (!memcmp(parent->object.sha1, parents->item->object.sha1, 355 sizeof(parents->item->object.sha1))) 356 return 1; 357 } 358 return 0; 359} 360 361/* 362 * Pushes an item onto the merge order stack. If the top of the stack is 363 * marked as being a possible "break", we check to see whether it actually 364 * is a break. 365 */ 366static void push_onto_merge_order_stack(struct commit_list **stack, struct commit *item) 367{ 368 struct commit_list *top = *stack; 369 if (top && (top->item->object.flags & DISCONTINUITY)) { 370 if (is_parent_of(top->item, item)) { 371 top->item->object.flags &= ~DISCONTINUITY; 372 } 373 } 374 commit_list_insert(item, stack); 375} 376 377/* 378 * Marks all interesting, visited commits reachable from this commit 379 * as uninteresting. We stop recursing when we reach the epoch boundary, 380 * an unvisited node or a node that has already been marking uninteresting. 381 * 382 * This doesn't actually mark all ancestors between the start node and the 383 * epoch boundary uninteresting, but does ensure that they will eventually 384 * be marked uninteresting when the main sort_first_epoch() traversal 385 * eventually reaches them. 386 */ 387static void mark_ancestors_uninteresting(struct commit *commit) 388{ 389 unsigned int flags = commit->object.flags; 390 int visited = flags & VISITED; 391 int boundary = flags & BOUNDARY; 392 int uninteresting = flags & UNINTERESTING; 393 struct commit_list *next; 394 395 commit->object.flags |= UNINTERESTING; 396 397 /* 398 * We only need to recurse if 399 * we are not on the boundary and 400 * we have not already been marked uninteresting and 401 * we have already been visited. 402 * 403 * The main sort_first_epoch traverse will mark unreachable 404 * all uninteresting, unvisited parents as they are visited 405 * so there is no need to duplicate that traversal here. 406 * 407 * Similarly, if we are already marked uninteresting 408 * then either all ancestors have already been marked 409 * uninteresting or will be once the sort_first_epoch 410 * traverse reaches them. 411 */ 412 413 if (uninteresting || boundary || !visited) 414 return; 415 416 for (next = commit->parents; next; next = next->next) 417 mark_ancestors_uninteresting(next->item); 418} 419 420/* 421 * Sorts the nodes of the first epoch of the epoch sequence of the epoch headed at head 422 * into merge order. 423 */ 424static void sort_first_epoch(struct commit *head, struct commit_list **stack) 425{ 426 struct commit_list *parents; 427 struct commit_list *reversed_parents = NULL; 428 429 head->object.flags |= VISITED; 430 431 /* 432 * parse_commit() builds the parent list in reverse order with respect 433 * to the order of the git-commit-tree arguments. So we need to reverse 434 * this list to output the oldest (or most "local") commits last. 435 */ 436 for (parents = head->parents; parents; parents = parents->next) 437 commit_list_insert(parents->item, &reversed_parents); 438 439 /* 440 * TODO: By sorting the parents in a different order, we can alter the 441 * merge order to show contemporaneous changes in parallel branches 442 * occurring after "local" changes. This is useful for a developer 443 * when a developer wants to see all changes that were incorporated 444 * into the same merge as her own changes occur after her own 445 * changes. 446 */ 447 448 while (reversed_parents) { 449 struct commit *parent = pop_commit(&reversed_parents); 450 451 if (head->object.flags & UNINTERESTING) { 452 /* 453 * Propagates the uninteresting bit to all parents. 454 * if we have already visited this parent, then 455 * the uninteresting bit will be propagated to each 456 * reachable commit that is still not marked 457 * uninteresting and won't otherwise be reached. 458 */ 459 mark_ancestors_uninteresting(parent); 460 } 461 462 if (!(parent->object.flags & VISITED)) { 463 if (parent->object.flags & BOUNDARY) { 464 if (*stack) { 465 die("something else is on the stack - %s", 466 sha1_to_hex((*stack)->item->object.sha1)); 467 } 468 push_onto_merge_order_stack(stack, parent); 469 parent->object.flags |= VISITED; 470 471 } else { 472 sort_first_epoch(parent, stack); 473 if (reversed_parents) { 474 /* 475 * This indicates a possible 476 * discontinuity it may not be be 477 * actual discontinuity if the head 478 * of parent N happens to be the tail 479 * of parent N+1. 480 * 481 * The next push onto the stack will 482 * resolve the question. 483 */ 484 (*stack)->item->object.flags |= DISCONTINUITY; 485 } 486 } 487 } 488 } 489 490 push_onto_merge_order_stack(stack, head); 491} 492 493/* 494 * Emit the contents of the stack. 495 * 496 * The stack is freed and replaced by NULL. 497 * 498 * Sets the return value to STOP if no further output should be generated. 499 */ 500static int emit_stack(struct commit_list **stack, emitter_func emitter) 501{ 502 unsigned int seen = 0; 503 int action = CONTINUE; 504 505 while (*stack && (action != STOP)) { 506 struct commit *next = pop_commit(stack); 507 seen |= next->object.flags; 508 if (*stack) 509 action = (*emitter) (next); 510 } 511 512 if (*stack) { 513 free_commit_list(*stack); 514 *stack = NULL; 515 } 516 517 return (action == STOP || (seen & UNINTERESTING)) ? STOP : CONTINUE; 518} 519 520/* 521 * Sorts an arbitrary epoch into merge order by sorting each epoch 522 * of its epoch sequence into order. 523 * 524 * Note: this algorithm currently leaves traces of its execution in the 525 * object flags of nodes it discovers. This should probably be fixed. 526 */ 527static int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter) 528{ 529 struct commit *next = head_of_epoch; 530 int ret = 0; 531 int action = CONTINUE; 532 533 ret = parse_commit(head_of_epoch); 534 535 next->object.flags |= BOUNDARY; 536 537 while (next && next->parents && !ret && (action != STOP)) { 538 struct commit *base = NULL; 539 540 ret = find_next_epoch_boundary(next, &base); 541 if (ret) 542 return ret; 543 next->object.flags |= BOUNDARY; 544 if (base) 545 base->object.flags |= BOUNDARY; 546 547 if (HAS_EXACTLY_ONE_PARENT(next)) { 548 while (HAS_EXACTLY_ONE_PARENT(next) 549 && (action != STOP) 550 && !ret) { 551 if (next->object.flags & UNINTERESTING) { 552 action = STOP; 553 } else { 554 action = (*emitter) (next); 555 } 556 if (action != STOP) { 557 next = next->parents->item; 558 ret = parse_commit(next); 559 } 560 } 561 562 } else { 563 struct commit_list *stack = NULL; 564 sort_first_epoch(next, &stack); 565 action = emit_stack(&stack, emitter); 566 next = base; 567 } 568 } 569 570 if (next && (action != STOP) && !ret) { 571 (*emitter) (next); 572 } 573 574 return ret; 575} 576 577/* 578 * Sorts the nodes reachable from a starting list in merge order, we 579 * first find the base for the starting list and then sort all nodes 580 * in this subgraph using the sort_first_epoch algorithm. Once we have 581 * reached the base we can continue sorting using sort_in_merge_order. 582 */ 583int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter) 584{ 585 struct commit_list *stack = NULL; 586 struct commit *base; 587 int ret = 0; 588 int action = CONTINUE; 589 struct commit_list *reversed = NULL; 590 591 for (; list; list = list->next) { 592 struct commit *next = list->item; 593 594 if (!(next->object.flags & UNINTERESTING)) { 595 if (next->object.flags & DUPCHECK) { 596 fprintf(stderr, "%s: duplicate commit %s ignored\n", 597 __FUNCTION__, sha1_to_hex(next->object.sha1)); 598 } else { 599 next->object.flags |= DUPCHECK; 600 commit_list_insert(list->item, &reversed); 601 } 602 } 603 } 604 605 if (!reversed) 606 return ret; 607 else if (!reversed->next) { 608 /* 609 * If there is only one element in the list, we can sort it 610 * using sort_in_merge_order. 611 */ 612 base = reversed->item; 613 } else { 614 /* 615 * Otherwise, we search for the base of the list. 616 */ 617 ret = find_base_for_list(reversed, &base); 618 if (ret) 619 return ret; 620 if (base) 621 base->object.flags |= BOUNDARY; 622 623 while (reversed) { 624 struct commit * next = pop_commit(&reversed); 625 626 if (!(next->object.flags & VISITED)) { 627 sort_first_epoch(next, &stack); 628 if (reversed) { 629 /* 630 * If we have more commits 631 * to push, then the first 632 * push for the next parent may 633 * (or may * not) represent a 634 * discontinuity with respect 635 * to the parent currently on 636 * the top of the stack. 637 * 638 * Mark it for checking here, 639 * and check it with the next 640 * push. See sort_first_epoch() 641 * for more details. 642 */ 643 stack->item->object.flags |= DISCONTINUITY; 644 } 645 } 646 } 647 648 action = emit_stack(&stack, emitter); 649 } 650 651 if (base && (action != STOP)) { 652 ret = sort_in_merge_order(base, emitter); 653 } 654 655 return ret; 656}