[PATCH] Operations on refs
[git.git] / epoch.c
blobba63eac68ec1078dbc5a867ecd294950caab0c60
1 /*
2 * Copyright (c) 2005, Jon Seymour
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.
9 */
10 #include <stdlib.h>
11 #include <openssl/bn.h> // provides arbitrary precision integers
12 // required to accurately represent fractional
13 //mass
15 #include "cache.h"
16 #include "commit.h"
17 #include "epoch.h"
19 struct fraction {
20 BIGNUM numerator;
21 BIGNUM denominator;
24 #define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)
26 static BN_CTX *context = NULL;
27 static struct fraction *one = NULL;
28 static struct fraction *zero = NULL;
30 static BN_CTX *get_BN_CTX()
32 if (!context) {
33 context = BN_CTX_new();
35 return context;
38 static struct fraction *new_zero()
40 struct fraction *result = xmalloc(sizeof(*result));
41 BN_init(&result->numerator);
42 BN_init(&result->denominator);
43 BN_zero(&result->numerator);
44 BN_one(&result->denominator);
45 return result;
48 static void clear_fraction(struct fraction *fraction)
50 BN_clear(&fraction->numerator);
51 BN_clear(&fraction->denominator);
54 static struct fraction *divide(struct fraction *result, struct fraction *fraction, int divisor)
56 BIGNUM bn_divisor;
58 BN_init(&bn_divisor);
59 BN_set_word(&bn_divisor, divisor);
61 BN_copy(&result->numerator, &fraction->numerator);
62 BN_mul(&result->denominator, &fraction->denominator, &bn_divisor, get_BN_CTX());
64 BN_clear(&bn_divisor);
65 return result;
68 static struct fraction *init_fraction(struct fraction *fraction)
70 BN_init(&fraction->numerator);
71 BN_init(&fraction->denominator);
72 BN_zero(&fraction->numerator);
73 BN_one(&fraction->denominator);
74 return fraction;
77 static struct fraction *get_one()
79 if (!one) {
80 one = new_zero();
81 BN_one(&one->numerator);
83 return one;
86 static struct fraction *get_zero()
88 if (!zero) {
89 zero = new_zero();
91 return zero;
94 static struct fraction *copy(struct fraction *to, struct fraction *from)
96 BN_copy(&to->numerator, &from->numerator);
97 BN_copy(&to->denominator, &from->denominator);
98 return to;
101 static struct fraction *add(struct fraction *result, struct fraction *left, struct fraction *right)
103 BIGNUM a, b, gcd;
105 BN_init(&a);
106 BN_init(&b);
107 BN_init(&gcd);
109 BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
110 BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
111 BN_mul(&result->denominator, &left->denominator, &right->denominator, get_BN_CTX());
112 BN_add(&result->numerator, &a, &b);
114 BN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX());
115 BN_div(&result->denominator, NULL, &result->denominator, &gcd, get_BN_CTX());
116 BN_div(&result->numerator, NULL, &result->numerator, &gcd, get_BN_CTX());
118 BN_clear(&a);
119 BN_clear(&b);
120 BN_clear(&gcd);
122 return result;
125 static int compare(struct fraction *left, struct fraction *right)
127 BIGNUM a, b;
129 int result;
131 BN_init(&a);
132 BN_init(&b);
134 BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
135 BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
137 result = BN_cmp(&a, &b);
139 BN_clear(&a);
140 BN_clear(&b);
142 return result;
145 struct mass_counter {
146 struct fraction seen;
147 struct fraction pending;
150 static struct mass_counter *new_mass_counter(struct commit *commit, struct fraction *pending)
152 struct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter));
153 memset(mass_counter, 0, sizeof(*mass_counter));
155 init_fraction(&mass_counter->seen);
156 init_fraction(&mass_counter->pending);
158 copy(&mass_counter->pending, pending);
159 copy(&mass_counter->seen, get_zero());
161 if (commit->object.util) {
162 die("multiple attempts to initialize mass counter for %s\n", sha1_to_hex(commit->object.sha1));
165 commit->object.util = mass_counter;
167 return mass_counter;
170 static void free_mass_counter(struct mass_counter *counter)
172 clear_fraction(&counter->seen);
173 clear_fraction(&counter->pending);
174 free(counter);
178 // Finds the base commit of a list of commits.
180 // One property of the commit being searched for is that every commit reachable
181 // from the base commit is reachable from the commits in the starting list only
182 // via paths that include the base commit.
184 // This algorithm uses a conservation of mass approach to find the base commit.
186 // We start by injecting one unit of mass into the graph at each
187 // of the commits in the starting list. Injecting mass into a commit
188 // is achieved by adding to its pending mass counter and, if it is not already
189 // enqueued, enqueuing the commit in a list of pending commits, in latest
190 // commit date first order.
192 // The algorithm then preceeds to visit each commit in the pending queue.
193 // Upon each visit, the pending mass is added to the mass already seen for that
194 // commit and then divided into N equal portions, where N is the number of
195 // parents of the commit being visited. The divided portions are then injected
196 // into each of the parents.
198 // The algorithm continues until we discover a commit which has seen all the
199 // mass originally injected or until we run out of things to do.
201 // If we find a commit that has seen all the original mass, we have found
202 // the common base of all the commits in the starting list.
204 // The algorithm does _not_ depend on accurate timestamps for correct operation.
205 // However, reasonably sane (e.g. non-random) timestamps are required in order
206 // to prevent an exponential performance characteristic. The occasional
207 // timestamp inaccuracy will not dramatically affect performance but may
208 // result in more nodes being processed than strictly necessary.
210 // This procedure sets *boundary to the address of the base commit. It returns
211 // non-zero if, and only if, there was a problem parsing one of the
212 // commits discovered during the traversal.
214 static int find_base_for_list(struct commit_list *list, struct commit **boundary)
217 int ret = 0;
219 struct commit_list *cleaner = NULL;
220 struct commit_list *pending = NULL;
222 *boundary = NULL;
224 struct fraction injected;
226 init_fraction(&injected);
228 for (; list; list = list->next) {
230 struct commit *item = list->item;
232 if (item->object.util || (item->object.flags & UNINTERESTING)) {
233 die("%s:%d:%s: logic error: this should not have happened - commit %s\n",
234 __FILE__, __LINE__, __FUNCTION__, sha1_to_hex(item->object.sha1));
237 new_mass_counter(list->item, get_one());
238 add(&injected, &injected, get_one());
240 commit_list_insert(list->item, &cleaner);
241 commit_list_insert(list->item, &pending);
244 while (!*boundary && pending && !ret) {
246 struct commit *latest = pop_commit(&pending);
248 struct mass_counter *latest_node = (struct mass_counter *) latest->object.util;
250 if ((ret = parse_commit(latest)))
251 continue;
253 add(&latest_node->seen, &latest_node->seen, &latest_node->pending);
255 int num_parents = count_parents(latest);
257 if (num_parents) {
259 struct fraction distribution;
260 struct commit_list *parents;
262 divide(init_fraction(&distribution), &latest_node->pending, num_parents);
264 for (parents = latest->parents; parents; parents = parents->next) {
266 struct commit *parent = parents->item;
267 struct mass_counter *parent_node = (struct mass_counter *) parent->object.util;
269 if (!parent_node) {
271 parent_node = new_mass_counter(parent, &distribution);
273 insert_by_date(&pending, parent);
274 commit_list_insert(parent, &cleaner);
276 } else {
278 if (!compare(&parent_node->pending, get_zero())) {
279 insert_by_date(&pending, parent);
281 add(&parent_node->pending, &parent_node->pending, &distribution);
286 clear_fraction(&distribution);
290 if (!compare(&latest_node->seen, &injected)) {
291 *boundary = latest;
294 copy(&latest_node->pending, get_zero());
298 while (cleaner) {
300 struct commit *next = pop_commit(&cleaner);
301 free_mass_counter((struct mass_counter *) next->object.util);
302 next->object.util = NULL;
306 if (pending)
307 free_commit_list(pending);
309 clear_fraction(&injected);
311 return ret;
317 // Finds the base of an minimal, non-linear epoch, headed at head, by
318 // applying the find_base_for_list to a list consisting of the parents
320 static int find_base(struct commit *head, struct commit **boundary)
322 int ret = 0;
323 struct commit_list *pending = NULL;
324 struct commit_list *next;
326 commit_list_insert(head, &pending);
327 for (next = head->parents; next; next = next->next) {
328 commit_list_insert(next->item, &pending);
330 ret = find_base_for_list(pending, boundary);
331 free_commit_list(pending);
333 return ret;
337 // This procedure traverses to the boundary of the first epoch in the epoch
338 // sequence of the epoch headed at head_of_epoch. This is either the end of
339 // the maximal linear epoch or the base of a minimal non-linear epoch.
341 // The queue of pending nodes is sorted in reverse date order and each node
342 // is currently in the queue at most once.
344 static int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary)
346 int ret;
347 struct commit *item = head_of_epoch;
349 ret = parse_commit(item);
350 if (ret)
351 return ret;
353 if (HAS_EXACTLY_ONE_PARENT(item)) {
355 // we are at the start of a maximimal linear epoch .. traverse to the end
357 // traverse to the end of a maximal linear epoch
358 while (HAS_EXACTLY_ONE_PARENT(item) && !ret) {
359 item = item->parents->item;
360 ret = parse_commit(item);
362 *boundary = item;
364 } else {
366 // otherwise, we are at the start of a minimal, non-linear
367 // epoch - find the common base of all parents.
369 ret = find_base(item, boundary);
373 return ret;
377 // Returns non-zero if parent is known to be a parent of child.
379 static int is_parent_of(struct commit *parent, struct commit *child)
381 struct commit_list *parents;
382 for (parents = child->parents; parents; parents = parents->next) {
383 if (!memcmp(parent->object.sha1, parents->item->object.sha1, sizeof(parents->item->object.sha1)))
384 return 1;
386 return 0;
390 // Pushes an item onto the merge order stack. If the top of the stack is
391 // marked as being a possible "break", we check to see whether it actually
392 // is a break.
394 static void push_onto_merge_order_stack(struct commit_list **stack, struct commit *item)
396 struct commit_list *top = *stack;
397 if (top && (top->item->object.flags & DISCONTINUITY)) {
398 if (is_parent_of(top->item, item)) {
399 top->item->object.flags &= ~DISCONTINUITY;
402 commit_list_insert(item, stack);
406 // Marks all interesting, visited commits reachable from this commit
407 // as uninteresting. We stop recursing when we reach the epoch boundary,
408 // an unvisited node or a node that has already been marking uninteresting.
409 // This doesn't actually mark all ancestors between the start node and the
410 // epoch boundary uninteresting, but does ensure that they will
411 // eventually be marked uninteresting when the main sort_first_epoch
412 // traversal eventually reaches them.
414 static void mark_ancestors_uninteresting(struct commit *commit)
416 unsigned int flags = commit->object.flags;
417 int visited = flags & VISITED;
418 int boundary = flags & BOUNDARY;
419 int uninteresting = flags & UNINTERESTING;
421 if (uninteresting || boundary || !visited) {
422 commit->object.flags |= UNINTERESTING;
423 return;
425 // we only need to recurse if
426 // we are not on the boundary, and,
427 // we have not already been marked uninteresting, and,
428 // we have already been visited.
431 // the main sort_first_epoch traverse will
432 // mark unreachable all uninteresting, unvisited parents
433 // as they are visited so there is no need to duplicate
434 // that traversal here.
436 // similarly, if we are already marked uninteresting
437 // then either all ancestors have already been marked
438 // uninteresting or will be once the sort_first_epoch
439 // traverse reaches them.
443 struct commit_list *next;
445 for (next = commit->parents; next; next = next->next)
446 mark_ancestors_uninteresting(next->item);
450 // Sorts the nodes of the first epoch of the epoch sequence of the epoch headed at head
451 // into merge order.
453 static void sort_first_epoch(struct commit *head, struct commit_list **stack)
455 struct commit_list *parents;
456 struct commit_list *reversed_parents = NULL;
458 head->object.flags |= VISITED;
461 // parse_commit builds the parent list in reverse order with respect to the order of
462 // the git-commit-tree arguments.
464 // so we need to reverse this list to output the oldest (or most "local") commits last.
467 for (parents = head->parents; parents; parents = parents->next)
468 commit_list_insert(parents->item, &reversed_parents);
471 // todo: by sorting the parents in a different order, we can alter the
472 // merge order to show contemporaneous changes in parallel branches
473 // occurring after "local" changes. This is useful for a developer
474 // when a developer wants to see all changes that were incorporated
475 // into the same merge as her own changes occur after her own
476 // changes.
479 while (reversed_parents) {
481 struct commit *parent = pop_commit(&reversed_parents);
483 if (head->object.flags & UNINTERESTING) {
484 // propagates the uninteresting bit to
485 // all parents. if we have already visited
486 // this parent, then the uninteresting bit
487 // will be propagated to each reachable
488 // commit that is still not marked uninteresting
489 // and won't otherwise be reached.
490 mark_ancestors_uninteresting(parent);
493 if (!(parent->object.flags & VISITED)) {
494 if (parent->object.flags & BOUNDARY) {
496 if (*stack) {
497 die("something else is on the stack - %s\n", sha1_to_hex((*stack)->item->object.sha1));
500 push_onto_merge_order_stack(stack, parent);
501 parent->object.flags |= VISITED;
503 } else {
505 sort_first_epoch(parent, stack);
507 if (reversed_parents) {
509 // this indicates a possible discontinuity
510 // it may not be be actual discontinuity if
511 // the head of parent N happens to be the tail
512 // of parent N+1
514 // the next push onto the stack will resolve the
515 // question
517 (*stack)->item->object.flags |= DISCONTINUITY;
523 push_onto_merge_order_stack(stack, head);
527 // Emit the contents of the stack.
529 // The stack is freed and replaced by NULL.
531 // Sets the return value to STOP if no further output should be generated.
533 static int emit_stack(struct commit_list **stack, emitter_func emitter)
535 unsigned int seen = 0;
536 int action = CONTINUE;
538 while (*stack && (action != STOP)) {
540 struct commit *next = pop_commit(stack);
542 seen |= next->object.flags;
544 if (*stack) {
545 action = (*emitter) (next);
549 if (*stack) {
550 free_commit_list(*stack);
551 *stack = NULL;
554 return (action == STOP || (seen & UNINTERESTING)) ? STOP : CONTINUE;
558 // Sorts an arbitrary epoch into merge order by sorting each epoch
559 // of its epoch sequence into order.
561 // Note: this algorithm currently leaves traces of its execution in the
562 // object flags of nodes it discovers. This should probably be fixed.
564 static int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter)
566 struct commit *next = head_of_epoch;
567 int ret = 0;
568 int action = CONTINUE;
570 ret = parse_commit(head_of_epoch);
572 while (next && next->parents && !ret && (action != STOP)) {
574 struct commit *base = NULL;
576 if ((ret = find_next_epoch_boundary(next, &base)))
577 return ret;
579 next->object.flags |= BOUNDARY;
580 if (base) {
581 base->object.flags |= BOUNDARY;
584 if (HAS_EXACTLY_ONE_PARENT(next)) {
586 while (HAS_EXACTLY_ONE_PARENT(next)
587 && (action != STOP)
588 && !ret) {
590 if (next->object.flags & UNINTERESTING) {
591 action = STOP;
592 } else {
593 action = (*emitter) (next);
596 if (action != STOP) {
597 next = next->parents->item;
598 ret = parse_commit(next);
602 } else {
604 struct commit_list *stack = NULL;
605 sort_first_epoch(next, &stack);
606 action = emit_stack(&stack, emitter);
607 next = base;
613 if (next && (action != STOP) && !ret) {
614 (*emitter) (next);
617 return ret;
621 // Sorts the nodes reachable from a starting list in merge order, we
622 // first find the base for the starting list and then sort all nodes in this
623 // subgraph using the sort_first_epoch algorithm. Once we have reached the base
624 // we can continue sorting using sort_in_merge_order.
626 int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter)
628 struct commit_list *stack = NULL;
629 struct commit *base;
631 int ret = 0;
632 int action = CONTINUE;
634 struct commit_list *reversed = NULL;
636 for (; list; list = list->next) {
638 struct commit *next = list->item;
640 if (!(next->object.flags & UNINTERESTING)) {
641 if (next->object.flags & DUPCHECK) {
642 fprintf(stderr, "%s: duplicate commit %s ignored\n", __FUNCTION__, sha1_to_hex(next->object.sha1));
643 } else {
644 next->object.flags |= DUPCHECK;
645 commit_list_insert(list->item, &reversed);
650 if (!reversed->next) {
652 // if there is only one element in the list, we can sort it using
653 // sort_in_merge_order.
655 base = reversed->item;
657 } else {
659 // otherwise, we search for the base of the list
661 if ((ret = find_base_for_list(reversed, &base)))
662 return ret;
664 if (base) {
665 base->object.flags |= BOUNDARY;
668 while (reversed) {
669 sort_first_epoch(pop_commit(&reversed), &stack);
670 if (reversed) {
672 // if we have more commits to push, then the
673 // first push for the next parent may (or may not)
674 // represent a discontinuity with respect to the
675 // parent currently on the top of the stack.
677 // mark it for checking here, and check it
678 // with the next push...see sort_first_epoch for
679 // more details.
681 stack->item->object.flags |= DISCONTINUITY;
685 action = emit_stack(&stack, emitter);
688 if (base && (action != STOP)) {
689 ret = sort_in_merge_order(base, emitter);
692 return ret;