Do a cross-project merge of Paul Mackerras' gitk visualizer
[git/git.git] / epoch.c
CommitLineData
a3437b8c
JS
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>
17ebe977
PB
11
12/* Provides arbitrary precision integers required to accurately represent
13 * fractional mass: */
14#include <openssl/bn.h>
a3437b8c
JS
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;
a3437b8c
JS
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) {
17ebe977
PB
162 die("multiple attempts to initialize mass counter for %s",
163 sha1_to_hex(commit->object.sha1));
a3437b8c
JS
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
17ebe977
PB
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 */
a3437b8c
JS
215static int find_base_for_list(struct commit_list *list, struct commit **boundary)
216{
a3437b8c 217 int ret = 0;
a3437b8c
JS
218 struct commit_list *cleaner = NULL;
219 struct commit_list *pending = NULL;
a3437b8c 220 struct fraction injected;
a3437b8c 221 init_fraction(&injected);
17ebe977 222 *boundary = NULL;
a3437b8c
JS
223
224 for (; list; list = list->next) {
a3437b8c
JS
225 struct commit *item = list->item;
226
c3c11631
JS
227 if (!item->object.util) {
228 new_mass_counter(list->item, get_one());
229 add(&injected, &injected, get_one());
a3437b8c 230
c3c11631
JS
231 commit_list_insert(list->item, &cleaner);
232 commit_list_insert(list->item, &pending);
233 }
a3437b8c
JS
234 }
235
236 while (!*boundary && pending && !ret) {
a3437b8c 237 struct commit *latest = pop_commit(&pending);
a3437b8c 238 struct mass_counter *latest_node = (struct mass_counter *) latest->object.util;
17ebe977 239 int num_parents;
a3437b8c
JS
240
241 if ((ret = parse_commit(latest)))
242 continue;
a3437b8c
JS
243 add(&latest_node->seen, &latest_node->seen, &latest_node->pending);
244
17ebe977 245 num_parents = count_parents(latest);
a3437b8c 246 if (num_parents) {
a3437b8c
JS
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) {
a3437b8c
JS
253 struct commit *parent = parents->item;
254 struct mass_counter *parent_node = (struct mass_counter *) parent->object.util;
255
256 if (!parent_node) {
a3437b8c 257 parent_node = new_mass_counter(parent, &distribution);
a3437b8c
JS
258 insert_by_date(&pending, parent);
259 commit_list_insert(parent, &cleaner);
a3437b8c 260 } else {
17ebe977 261 if (!compare(&parent_node->pending, get_zero()))
a3437b8c 262 insert_by_date(&pending, parent);
a3437b8c 263 add(&parent_node->pending, &parent_node->pending, &distribution);
a3437b8c
JS
264 }
265 }
266
267 clear_fraction(&distribution);
a3437b8c
JS
268 }
269
17ebe977 270 if (!compare(&latest_node->seen, &injected))
a3437b8c 271 *boundary = latest;
a3437b8c 272 copy(&latest_node->pending, get_zero());
a3437b8c
JS
273 }
274
275 while (cleaner) {
a3437b8c
JS
276 struct commit *next = pop_commit(&cleaner);
277 free_mass_counter((struct mass_counter *) next->object.util);
278 next->object.util = NULL;
a3437b8c
JS
279 }
280
281 if (pending)
282 free_commit_list(pending);
283
284 clear_fraction(&injected);
a3437b8c 285 return ret;
a3437b8c
JS
286}
287
288
17ebe977
PB
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 */
a3437b8c
JS
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
a3437b8c
JS
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
17ebe977
PB
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 */
a3437b8c
JS
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)) {
17ebe977
PB
326 /*
327 * We are at the start of a maximimal linear epoch.
328 * Traverse to the end.
329 */
a3437b8c
JS
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 {
17ebe977
PB
337 /*
338 * Otherwise, we are at the start of a minimal, non-linear
339 * epoch - find the common base of all parents.
340 */
a3437b8c 341 ret = find_base(item, boundary);
a3437b8c
JS
342 }
343
344 return ret;
345}
346
17ebe977
PB
347/*
348 * Returns non-zero if parent is known to be a parent of child.
349 */
a3437b8c
JS
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) {
17ebe977
PB
354 if (!memcmp(parent->object.sha1, parents->item->object.sha1,
355 sizeof(parents->item->object.sha1)))
a3437b8c
JS
356 return 1;
357 }
358 return 0;
359}
360
17ebe977
PB
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 */
a3437b8c
JS
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
17ebe977
PB
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 */
a3437b8c
JS
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;
17ebe977 393 struct commit_list *next;
a3437b8c 394
4e734673 395 commit->object.flags |= UNINTERESTING;
a3437b8c 396
17ebe977
PB
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;
a3437b8c
JS
415
416 for (next = commit->parents; next; next = next->next)
417 mark_ancestors_uninteresting(next->item);
418}
419
17ebe977
PB
420/*
421 * Sorts the nodes of the first epoch of the epoch sequence of the epoch headed at head
422 * into merge order.
423 */
a3437b8c
JS
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
17ebe977
PB
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 */
a3437b8c
JS
436 for (parents = head->parents; parents; parents = parents->next)
437 commit_list_insert(parents->item, &reversed_parents);
438
17ebe977
PB
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 */
a3437b8c
JS
447
448 while (reversed_parents) {
a3437b8c
JS
449 struct commit *parent = pop_commit(&reversed_parents);
450
451 if (head->object.flags & UNINTERESTING) {
17ebe977
PB
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 */
a3437b8c
JS
459 mark_ancestors_uninteresting(parent);
460 }
461
462 if (!(parent->object.flags & VISITED)) {
463 if (parent->object.flags & BOUNDARY) {
a3437b8c 464 if (*stack) {
17ebe977
PB
465 die("something else is on the stack - %s",
466 sha1_to_hex((*stack)->item->object.sha1));
a3437b8c 467 }
a3437b8c
JS
468 push_onto_merge_order_stack(stack, parent);
469 parent->object.flags |= VISITED;
470
471 } else {
a3437b8c 472 sort_first_epoch(parent, stack);
a3437b8c 473 if (reversed_parents) {
17ebe977
PB
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 */
a3437b8c
JS
484 (*stack)->item->object.flags |= DISCONTINUITY;
485 }
486 }
487 }
488 }
489
490 push_onto_merge_order_stack(stack, head);
491}
492
17ebe977
PB
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 */
a3437b8c
JS
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)) {
a3437b8c 506 struct commit *next = pop_commit(stack);
a3437b8c 507 seen |= next->object.flags;
17ebe977 508 if (*stack)
a3437b8c 509 action = (*emitter) (next);
a3437b8c
JS
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
17ebe977
PB
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 */
a3437b8c
JS
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
8cd1033e
JS
535 next->object.flags |= BOUNDARY;
536
a3437b8c 537 while (next && next->parents && !ret && (action != STOP)) {
a3437b8c
JS
538 struct commit *base = NULL;
539
17ebe977
PB
540 ret = find_next_epoch_boundary(next, &base);
541 if (ret)
a3437b8c 542 return ret;
a3437b8c 543 next->object.flags |= BOUNDARY;
17ebe977 544 if (base)
a3437b8c 545 base->object.flags |= BOUNDARY;
a3437b8c
JS
546
547 if (HAS_EXACTLY_ONE_PARENT(next)) {
a3437b8c
JS
548 while (HAS_EXACTLY_ONE_PARENT(next)
549 && (action != STOP)
550 && !ret) {
a3437b8c
JS
551 if (next->object.flags & UNINTERESTING) {
552 action = STOP;
553 } else {
554 action = (*emitter) (next);
555 }
a3437b8c
JS
556 if (action != STOP) {
557 next = next->parents->item;
558 ret = parse_commit(next);
559 }
560 }
561
562 } else {
a3437b8c
JS
563 struct commit_list *stack = NULL;
564 sort_first_epoch(next, &stack);
565 action = emit_stack(&stack, emitter);
566 next = base;
a3437b8c 567 }
a3437b8c
JS
568 }
569
570 if (next && (action != STOP) && !ret) {
571 (*emitter) (next);
572 }
573
574 return ret;
575}
576
17ebe977
PB
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 */
a3437b8c
JS
583int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter)
584{
585 struct commit_list *stack = NULL;
586 struct commit *base;
a3437b8c
JS
587 int ret = 0;
588 int action = CONTINUE;
a3437b8c
JS
589 struct commit_list *reversed = NULL;
590
591 for (; list; list = list->next) {
a3437b8c
JS
592 struct commit *next = list->item;
593
594 if (!(next->object.flags & UNINTERESTING)) {
595 if (next->object.flags & DUPCHECK) {
17ebe977
PB
596 fprintf(stderr, "%s: duplicate commit %s ignored\n",
597 __FUNCTION__, sha1_to_hex(next->object.sha1));
a3437b8c
JS
598 } else {
599 next->object.flags |= DUPCHECK;
600 commit_list_insert(list->item, &reversed);
601 }
602 }
603 }
604
d6bd56a0
JS
605 if (!reversed)
606 return ret;
607 else if (!reversed->next) {
17ebe977
PB
608 /*
609 * If there is only one element in the list, we can sort it
610 * using sort_in_merge_order.
611 */
a3437b8c 612 base = reversed->item;
a3437b8c 613 } else {
17ebe977
PB
614 /*
615 * Otherwise, we search for the base of the list.
616 */
617 ret = find_base_for_list(reversed, &base);
618 if (ret)
a3437b8c 619 return ret;
17ebe977 620 if (base)
a3437b8c 621 base->object.flags |= BOUNDARY;
a3437b8c
JS
622
623 while (reversed) {
eff19d5e
JS
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 }
a3437b8c
JS
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}