Merge master.kernel.org:/pub/scm/gitk/gitk
[git/git.git] / epoch.c
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
20 struct fraction {
21 BIGNUM numerator;
22 BIGNUM denominator;
23 };
24
25 #define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)
26
27 static BN_CTX *context = NULL;
28 static struct fraction *one = NULL;
29 static struct fraction *zero = NULL;
30
31 static BN_CTX *get_BN_CTX(void)
32 {
33 if (!context) {
34 context = BN_CTX_new();
35 }
36 return context;
37 }
38
39 static 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
49 static void clear_fraction(struct fraction *fraction)
50 {
51 BN_clear(&fraction->numerator);
52 BN_clear(&fraction->denominator);
53 }
54
55 static 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
69 static 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
78 static struct fraction *get_one(void)
79 {
80 if (!one) {
81 one = new_zero();
82 BN_one(&one->numerator);
83 }
84 return one;
85 }
86
87 static struct fraction *get_zero(void)
88 {
89 if (!zero) {
90 zero = new_zero();
91 }
92 return zero;
93 }
94
95 static 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
102 static 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
126 static 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
145 struct mass_counter {
146 struct fraction seen;
147 struct fraction pending;
148 };
149
150 static 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
171 static 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 */
215 static 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 */
293 static 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 */
316 static 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 */
350 static 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 */
366 static 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 */
387 static 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 */
424 static 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 */
491 static 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 */
521 static 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 */
577 int 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 struct commit *next = list->item;
587
588 if (!(next->object.flags & DUPCHECK)) {
589 next->object.flags |= DUPCHECK;
590 commit_list_insert(list->item, &reversed);
591 }
592 }
593
594 if (!reversed)
595 return ret;
596 else if (!reversed->next) {
597 /*
598 * If there is only one element in the list, we can sort it
599 * using sort_in_merge_order.
600 */
601 base = reversed->item;
602 } else {
603 /*
604 * Otherwise, we search for the base of the list.
605 */
606 ret = find_base_for_list(reversed, &base);
607 if (ret)
608 return ret;
609 if (base)
610 base->object.flags |= BOUNDARY;
611
612 while (reversed) {
613 struct commit * next = pop_commit(&reversed);
614
615 if (!(next->object.flags & VISITED)) {
616 sort_first_epoch(next, &stack);
617 if (reversed) {
618 /*
619 * If we have more commits
620 * to push, then the first
621 * push for the next parent may
622 * (or may * not) represent a
623 * discontinuity with respect
624 * to the parent currently on
625 * the top of the stack.
626 *
627 * Mark it for checking here,
628 * and check it with the next
629 * push. See sort_first_epoch()
630 * for more details.
631 */
632 stack->item->object.flags |= DISCONTINUITY;
633 }
634 }
635 }
636
637 action = emit_stack(&stack, emitter, (base==NULL));
638 }
639
640 if (base && (action != STOP)) {
641 ret = sort_in_merge_order(base, emitter);
642 }
643
644 return ret;
645 }