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(void) 32{ 33 if (!context) { 34 context = BN_CTX_new(); 35 } 36 return context; 37} 38 39static struct fraction *new_zero(void) 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(void) 79{ 80 if (!one) { 81 one = new_zero(); 82 BN_one(&one->numerator); 83 } 84 return one; 85} 86 87static struct fraction *get_zero(void) 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(parent, &pending); 259 commit_list_insert(parent, &cleaner); 260 } else { 261 if (!compare(&parent_node->pending, get_zero())) 262 insert_by_date(parent, &pending); 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 428 head->object.flags |= VISITED; 429 430 /* 431 * TODO: By sorting the parents in a different order, we can alter the 432 * merge order to show contemporaneous changes in parallel branches 433 * occurring after "local" changes. This is useful for a developer 434 * when a developer wants to see all changes that were incorporated 435 * into the same merge as her own changes occur after her own 436 * changes. 437 */ 438 439 for (parents = head->parents; parents; parents = parents->next) { 440 struct commit *parent = parents->item; 441 442 if (head->object.flags & UNINTERESTING) { 443 /* 444 * Propagates the uninteresting bit to all parents. 445 * if we have already visited this parent, then 446 * the uninteresting bit will be propagated to each 447 * reachable commit that is still not marked 448 * uninteresting and won't otherwise be reached. 449 */ 450 mark_ancestors_uninteresting(parent); 451 } 452 453 if (!(parent->object.flags & VISITED)) { 454 if (parent->object.flags & BOUNDARY) { 455 if (*stack) { 456 die("something else is on the stack - %s", 457 sha1_to_hex((*stack)->item->object.sha1)); 458 } 459 push_onto_merge_order_stack(stack, parent); 460 parent->object.flags |= VISITED; 461 462 } else { 463 sort_first_epoch(parent, stack); 464 if (parents) { 465 /* 466 * This indicates a possible 467 * discontinuity it may not be be 468 * actual discontinuity if the head 469 * of parent N happens to be the tail 470 * of parent N+1. 471 * 472 * The next push onto the stack will 473 * resolve the question. 474 */ 475 (*stack)->item->object.flags |= DISCONTINUITY; 476 } 477 } 478 } 479 } 480 481 push_onto_merge_order_stack(stack, head); 482} 483 484/* 485 * Emit the contents of the stack. 486 * 487 * The stack is freed and replaced by NULL. 488 * 489 * Sets the return value to STOP if no further output should be generated. 490 */ 491static int emit_stack(struct commit_list **stack, emitter_func emitter, int include_last) 492{ 493 unsigned int seen = 0; 494 int action = CONTINUE; 495 496 while (*stack && (action != STOP)) { 497 struct commit *next = pop_commit(stack); 498 seen |= next->object.flags; 499 if (*stack || include_last) { 500 if (!*stack) 501 next->object.flags |= BOUNDARY; 502 action = emitter(next); 503 } 504 } 505 506 if (*stack) { 507 free_commit_list(*stack); 508 *stack = NULL; 509 } 510 511 return (action == STOP || (seen & UNINTERESTING)) ? STOP : CONTINUE; 512} 513 514/* 515 * Sorts an arbitrary epoch into merge order by sorting each epoch 516 * of its epoch sequence into order. 517 * 518 * Note: this algorithm currently leaves traces of its execution in the 519 * object flags of nodes it discovers. This should probably be fixed. 520 */ 521static int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter) 522{ 523 struct commit *next = head_of_epoch; 524 int ret = 0; 525 int action = CONTINUE; 526 527 ret = parse_commit(head_of_epoch); 528 529 next->object.flags |= BOUNDARY; 530 531 while (next && next->parents && !ret && (action != STOP)) { 532 struct commit *base = NULL; 533 534 ret = find_next_epoch_boundary(next, &base); 535 if (ret) 536 return ret; 537 next->object.flags |= BOUNDARY; 538 if (base) 539 base->object.flags |= BOUNDARY; 540 541 if (HAS_EXACTLY_ONE_PARENT(next)) { 542 while (HAS_EXACTLY_ONE_PARENT(next) 543 && (action != STOP) 544 && !ret) { 545 if (next->object.flags & UNINTERESTING) { 546 action = STOP; 547 } else { 548 action = emitter(next); 549 } 550 if (action != STOP) { 551 next = next->parents->item; 552 ret = parse_commit(next); 553 } 554 } 555 556 } else { 557 struct commit_list *stack = NULL; 558 sort_first_epoch(next, &stack); 559 action = emit_stack(&stack, emitter, (base == NULL)); 560 next = base; 561 } 562 } 563 564 if (next && (action != STOP) && !ret) { 565 emitter(next); 566 } 567 568 return ret; 569} 570 571/* 572 * Sorts the nodes reachable from a starting list in merge order, we 573 * first find the base for the starting list and then sort all nodes 574 * in this subgraph using the sort_first_epoch algorithm. Once we have 575 * reached the base we can continue sorting using sort_in_merge_order. 576 */ 577int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter) 578{ 579 struct commit_list *stack = NULL; 580 struct commit *base; 581 int ret = 0; 582 int action = CONTINUE; 583 struct commit_list *reversed = NULL; 584 585 for (; list; list = list->next) 586 commit_list_insert(list->item, &reversed); 587 588 if (!reversed) 589 return ret; 590 else if (!reversed->next) { 591 /* 592 * If there is only one element in the list, we can sort it 593 * using sort_in_merge_order. 594 */ 595 base = reversed->item; 596 } else { 597 /* 598 * Otherwise, we search for the base of the list. 599 */ 600 ret = find_base_for_list(reversed, &base); 601 if (ret) 602 return ret; 603 if (base) 604 base->object.flags |= BOUNDARY; 605 606 while (reversed) { 607 struct commit * next = pop_commit(&reversed); 608 609 if (!(next->object.flags & VISITED) && next!=base) { 610 sort_first_epoch(next, &stack); 611 if (reversed) { 612 /* 613 * If we have more commits 614 * to push, then the first 615 * push for the next parent may 616 * (or may * not) represent a 617 * discontinuity with respect 618 * to the parent currently on 619 * the top of the stack. 620 * 621 * Mark it for checking here, 622 * and check it with the next 623 * push. See sort_first_epoch() 624 * for more details. 625 */ 626 stack->item->object.flags |= DISCONTINUITY; 627 } 628 } 629 } 630 631 action = emit_stack(&stack, emitter, (base==NULL)); 632 } 633 634 if (base && (action != STOP)) { 635 ret = sort_in_merge_order(base, emitter); 636 } 637 638 return ret; 639}