Start preparing for 1.8.1.3
[git/git.git] / graph.c
CommitLineData
c12172d2
AS
1#include "cache.h"
2#include "commit.h"
427fc5b8 3#include "color.h"
c12172d2
AS
4#include "graph.h"
5#include "diff.h"
6#include "revision.h"
7
064bfbde
NS
8/* Internal API */
9
ba354804
JH
10/*
11 * Output the next line for a graph.
12 * This formats the next graph line into the specified strbuf. It is not
13 * terminated with a newline.
14 *
15 * Returns 1 if the line includes the current commit, and 0 otherwise.
16 * graph_next_line() will return 1 exactly once for each time
17 * graph_update() is called.
18 */
19static int graph_next_line(struct git_graph *graph, struct strbuf *sb);
20
21/*
22 * Set up a custom scheme for column colors.
23 *
24 * The default column color scheme inserts ANSI color escapes to colorize
25 * the graph. The various color escapes are stored in an array of strings
26 * where each entry corresponds to a color, except for the last entry,
27 * which denotes the escape for resetting the color back to the default.
28 * When generating the graph, strings from this array are inserted before
29 * and after the various column characters.
30 *
31 * This function allows you to enable a custom array of color escapes.
32 * The 'colors_max' argument is the index of the last "reset" entry.
33 *
34 * This functions must be called BEFORE graph_init() is called.
35 */
36static void graph_set_column_colors(const char **colors, unsigned short colors_max);
37
064bfbde
NS
38/*
39 * Output a padding line in the graph.
40 * This is similar to graph_next_line(). However, it is guaranteed to
41 * never print the current commit line. Instead, if the commit line is
42 * next, it will simply output a line of vertical padding, extending the
43 * branch lines downwards, but leaving them otherwise unchanged.
44 */
45static void graph_padding_line(struct git_graph *graph, struct strbuf *sb);
46
47/*
48 * Print a strbuf to stdout. If the graph is non-NULL, all lines but the
49 * first will be prefixed with the graph output.
50 *
51 * If the strbuf ends with a newline, the output will end after this
52 * newline. A new graph line will not be printed after the final newline.
53 * If the strbuf is empty, no output will be printed.
54 *
3ea3c215 55 * Since the first line will not include the graph output, the caller is
064bfbde
NS
56 * responsible for printing this line's graph (perhaps via
57 * graph_show_commit() or graph_show_oneline()) before calling
58 * graph_show_strbuf().
59 */
60static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
61
c12172d2
AS
62/*
63 * TODO:
c12172d2
AS
64 * - Limit the number of columns, similar to the way gitk does.
65 * If we reach more than a specified number of columns, omit
66 * sections of some columns.
c12172d2
AS
67 */
68
69struct column {
70 /*
71 * The parent commit of this column.
72 */
73 struct commit *commit;
74 /*
427fc5b8
AC
75 * The color to (optionally) print this column in. This is an
76 * index into column_colors.
c12172d2 77 */
427fc5b8 78 unsigned short color;
c12172d2
AS
79};
80
81enum graph_state {
82 GRAPH_PADDING,
83 GRAPH_SKIP,
84 GRAPH_PRE_COMMIT,
85 GRAPH_COMMIT,
86 GRAPH_POST_MERGE,
87 GRAPH_COLLAPSING
88};
89
1e3d4119
JH
90static const char **column_colors;
91static unsigned short column_colors_max;
92
ba354804 93static void graph_set_column_colors(const char **colors, unsigned short colors_max)
1e3d4119
JH
94{
95 column_colors = colors;
96 column_colors_max = colors_max;
97}
98
99static const char *column_get_color_code(unsigned short color)
427fc5b8 100{
1e3d4119 101 return column_colors[color];
427fc5b8
AC
102}
103
104static void strbuf_write_column(struct strbuf *sb, const struct column *c,
105 char col_char)
106{
1e3d4119
JH
107 if (c->color < column_colors_max)
108 strbuf_addstr(sb, column_get_color_code(c->color));
427fc5b8 109 strbuf_addch(sb, col_char);
1e3d4119
JH
110 if (c->color < column_colors_max)
111 strbuf_addstr(sb, column_get_color_code(column_colors_max));
427fc5b8
AC
112}
113
c12172d2
AS
114struct git_graph {
115 /*
116 * The commit currently being processed
117 */
118 struct commit *commit;
7528f27d
AS
119 /* The rev-info used for the current traversal */
120 struct rev_info *revs;
c12172d2 121 /*
37a75abc
AS
122 * The number of interesting parents that this commit has.
123 *
124 * Note that this is not the same as the actual number of parents.
125 * This count excludes parents that won't be printed in the graph
126 * output, as determined by graph_is_interesting().
c12172d2
AS
127 */
128 int num_parents;
0724cb86
AS
129 /*
130 * The width of the graph output for this commit.
131 * All rows for this commit are padded to this width, so that
132 * messages printed after the graph output are aligned.
133 */
134 int width;
c12172d2
AS
135 /*
136 * The next expansion row to print
137 * when state is GRAPH_PRE_COMMIT
138 */
139 int expansion_row;
140 /*
141 * The current output state.
142 * This tells us what kind of line graph_next_line() should output.
143 */
144 enum graph_state state;
3395908e
AS
145 /*
146 * The output state for the previous line of output.
147 * This is primarily used to determine how the first merge line
148 * should appear, based on the last line of the previous commit.
149 */
150 enum graph_state prev_state;
151 /*
152 * The index of the column that refers to this commit.
153 *
154 * If none of the incoming columns refer to this commit,
155 * this will be equal to num_columns.
156 */
157 int commit_index;
158 /*
159 * The commit_index for the previously displayed commit.
160 *
161 * This is used to determine how the first line of a merge
162 * graph output should appear, based on the last line of the
163 * previous commit.
164 */
165 int prev_commit_index;
c12172d2
AS
166 /*
167 * The maximum number of columns that can be stored in the columns
168 * and new_columns arrays. This is also half the number of entries
169 * that can be stored in the mapping and new_mapping arrays.
170 */
171 int column_capacity;
172 /*
173 * The number of columns (also called "branch lines" in some places)
174 */
175 int num_columns;
176 /*
177 * The number of columns in the new_columns array
178 */
179 int num_new_columns;
180 /*
181 * The number of entries in the mapping array
182 */
183 int mapping_size;
184 /*
185 * The column state before we output the current commit.
186 */
187 struct column *columns;
188 /*
189 * The new column state after we output the current commit.
190 * Only valid when state is GRAPH_COLLAPSING.
191 */
192 struct column *new_columns;
193 /*
194 * An array that tracks the current state of each
195 * character in the output line during state GRAPH_COLLAPSING.
196 * Each entry is -1 if this character is empty, or a non-negative
197 * integer if the character contains a branch line. The value of
198 * the integer indicates the target position for this branch line.
199 * (I.e., this array maps the current column positions to their
200 * desired positions.)
201 *
202 * The maximum capacity of this array is always
203 * sizeof(int) * 2 * column_capacity.
204 */
205 int *mapping;
206 /*
207 * A temporary array for computing the next mapping state
208 * while we are outputting a mapping line. This is stored as part
209 * of the git_graph simply so we don't have to allocate a new
210 * temporary array each time we have to output a collapsing line.
211 */
212 int *new_mapping;
427fc5b8
AC
213 /*
214 * The current default column color being used. This is
215 * stored as an index into the array column_colors.
216 */
217 unsigned short default_column_color;
c12172d2
AS
218};
219
b5a4de9d
BY
220static struct strbuf *diff_output_prefix_callback(struct diff_options *opt, void *data)
221{
222 struct git_graph *graph = data;
223 static struct strbuf msgbuf = STRBUF_INIT;
224
5e71a84a 225 assert(opt);
b5a4de9d
BY
226 assert(graph);
227
5e71a84a 228 opt->output_prefix_length = graph->width;
b5a4de9d
BY
229 strbuf_reset(&msgbuf);
230 graph_padding_line(graph, &msgbuf);
231 return &msgbuf;
232}
233
7528f27d 234struct git_graph *graph_init(struct rev_info *opt)
c12172d2
AS
235{
236 struct git_graph *graph = xmalloc(sizeof(struct git_graph));
1e3d4119
JH
237
238 if (!column_colors)
239 graph_set_column_colors(column_colors_ansi,
7cd52b5b 240 column_colors_ansi_max);
1e3d4119 241
c12172d2 242 graph->commit = NULL;
7528f27d 243 graph->revs = opt;
c12172d2
AS
244 graph->num_parents = 0;
245 graph->expansion_row = 0;
246 graph->state = GRAPH_PADDING;
3395908e
AS
247 graph->prev_state = GRAPH_PADDING;
248 graph->commit_index = 0;
249 graph->prev_commit_index = 0;
c12172d2
AS
250 graph->num_columns = 0;
251 graph->num_new_columns = 0;
252 graph->mapping_size = 0;
91e50b2c
AS
253 /*
254 * Start the column color at the maximum value, since we'll
255 * always increment it for the first commit we output.
256 * This way we start at 0 for the first commit.
257 */
1e3d4119 258 graph->default_column_color = column_colors_max - 1;
c12172d2
AS
259
260 /*
261 * Allocate a reasonably large default number of columns
262 * We'll automatically grow columns later if we need more room.
263 */
264 graph->column_capacity = 30;
265 graph->columns = xmalloc(sizeof(struct column) *
266 graph->column_capacity);
267 graph->new_columns = xmalloc(sizeof(struct column) *
268 graph->column_capacity);
269 graph->mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity);
270 graph->new_mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity);
271
b5a4de9d
BY
272 /*
273 * The diff output prefix callback, with this we can make
274 * all the diff output to align with the graph lines.
275 */
276 opt->diffopt.output_prefix = diff_output_prefix_callback;
277 opt->diffopt.output_prefix_data = graph;
5e71a84a 278 opt->diffopt.output_prefix_length = 0;
b5a4de9d 279
c12172d2
AS
280 return graph;
281}
282
3395908e
AS
283static void graph_update_state(struct git_graph *graph, enum graph_state s)
284{
285 graph->prev_state = graph->state;
286 graph->state = s;
287}
288
c12172d2
AS
289static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
290{
291 if (graph->column_capacity >= num_columns)
292 return;
293
294 do {
295 graph->column_capacity *= 2;
296 } while (graph->column_capacity < num_columns);
297
298 graph->columns = xrealloc(graph->columns,
299 sizeof(struct column) *
300 graph->column_capacity);
301 graph->new_columns = xrealloc(graph->new_columns,
302 sizeof(struct column) *
303 graph->column_capacity);
304 graph->mapping = xrealloc(graph->mapping,
305 sizeof(int) * 2 * graph->column_capacity);
306 graph->new_mapping = xrealloc(graph->new_mapping,
307 sizeof(int) * 2 * graph->column_capacity);
308}
309
37a75abc
AS
310/*
311 * Returns 1 if the commit will be printed in the graph output,
312 * and 0 otherwise.
313 */
3c68d67b 314static int graph_is_interesting(struct git_graph *graph, struct commit *commit)
37a75abc 315{
3c68d67b
AS
316 /*
317 * If revs->boundary is set, commits whose children have
318 * been shown are always interesting, even if they have the
319 * UNINTERESTING or TREESAME flags set.
3c68d67b
AS
320 */
321 if (graph->revs && graph->revs->boundary) {
4603ec0f 322 if (commit->object.flags & CHILD_SHOWN)
3c68d67b
AS
323 return 1;
324 }
325
37a75abc 326 /*
beb5af43
AS
327 * Otherwise, use get_commit_action() to see if this commit is
328 * interesting
37a75abc 329 */
beb5af43 330 return get_commit_action(graph->revs, commit) == commit_show;
37a75abc
AS
331}
332
a0ebe573
AS
333static struct commit_list *next_interesting_parent(struct git_graph *graph,
334 struct commit_list *orig)
335{
336 struct commit_list *list;
337
338 /*
339 * If revs->first_parent_only is set, only the first
340 * parent is interesting. None of the others are.
341 */
342 if (graph->revs->first_parent_only)
343 return NULL;
344
345 /*
346 * Return the next interesting commit after orig
347 */
348 for (list = orig->next; list; list = list->next) {
349 if (graph_is_interesting(graph, list->item))
350 return list;
351 }
352
353 return NULL;
354}
355
356static struct commit_list *first_interesting_parent(struct git_graph *graph)
357{
358 struct commit_list *parents = graph->commit->parents;
359
360 /*
361 * If this commit has no parents, ignore it
362 */
363 if (!parents)
364 return NULL;
365
366 /*
367 * If the first parent is interesting, return it
368 */
369 if (graph_is_interesting(graph, parents->item))
370 return parents;
371
372 /*
373 * Otherwise, call next_interesting_parent() to get
374 * the next interesting parent
375 */
376 return next_interesting_parent(graph, parents);
377}
378
427fc5b8
AC
379static unsigned short graph_get_current_column_color(const struct git_graph *graph)
380{
daa0c3d9 381 if (!want_color(graph->revs->diffopt.use_color))
1e3d4119 382 return column_colors_max;
427fc5b8
AC
383 return graph->default_column_color;
384}
385
386/*
387 * Update the graph's default column color.
388 */
389static void graph_increment_column_color(struct git_graph *graph)
390{
391 graph->default_column_color = (graph->default_column_color + 1) %
1e3d4119 392 column_colors_max;
427fc5b8
AC
393}
394
395static unsigned short graph_find_commit_color(const struct git_graph *graph,
396 const struct commit *commit)
397{
398 int i;
399 for (i = 0; i < graph->num_columns; i++) {
400 if (graph->columns[i].commit == commit)
401 return graph->columns[i].color;
402 }
403 return graph_get_current_column_color(graph);
404}
405
c12172d2
AS
406static void graph_insert_into_new_columns(struct git_graph *graph,
407 struct commit *commit,
408 int *mapping_index)
409{
410 int i;
411
c12172d2
AS
412 /*
413 * If the commit is already in the new_columns list, we don't need to
414 * add it. Just update the mapping correctly.
415 */
416 for (i = 0; i < graph->num_new_columns; i++) {
417 if (graph->new_columns[i].commit == commit) {
418 graph->mapping[*mapping_index] = i;
419 *mapping_index += 2;
420 return;
421 }
422 }
423
424 /*
425 * This commit isn't already in new_columns. Add it.
426 */
427 graph->new_columns[graph->num_new_columns].commit = commit;
427fc5b8 428 graph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit);
c12172d2
AS
429 graph->mapping[*mapping_index] = graph->num_new_columns;
430 *mapping_index += 2;
431 graph->num_new_columns++;
432}
433
0724cb86
AS
434static void graph_update_width(struct git_graph *graph,
435 int is_commit_in_existing_columns)
436{
437 /*
438 * Compute the width needed to display the graph for this commit.
439 * This is the maximum width needed for any row. All other rows
440 * will be padded to this width.
441 *
442 * Compute the number of columns in the widest row:
443 * Count each existing column (graph->num_columns), and each new
444 * column added by this commit.
445 */
446 int max_cols = graph->num_columns + graph->num_parents;
447
448 /*
37a75abc
AS
449 * Even if the current commit has no parents to be printed, it
450 * still takes up a column for itself.
0724cb86
AS
451 */
452 if (graph->num_parents < 1)
453 max_cols++;
454
455 /*
22e5e58a 456 * We added a column for the current commit as part of
0724cb86
AS
457 * graph->num_parents. If the current commit was already in
458 * graph->columns, then we have double counted it.
459 */
460 if (is_commit_in_existing_columns)
461 max_cols--;
462
463 /*
464 * Each column takes up 2 spaces
465 */
466 graph->width = max_cols * 2;
467}
468
c12172d2
AS
469static void graph_update_columns(struct git_graph *graph)
470{
471 struct commit_list *parent;
472 struct column *tmp_columns;
473 int max_new_columns;
474 int mapping_idx;
0724cb86 475 int i, seen_this, is_commit_in_columns;
c12172d2
AS
476
477 /*
478 * Swap graph->columns with graph->new_columns
479 * graph->columns contains the state for the previous commit,
480 * and new_columns now contains the state for our commit.
481 *
482 * We'll re-use the old columns array as storage to compute the new
483 * columns list for the commit after this one.
484 */
485 tmp_columns = graph->columns;
486 graph->columns = graph->new_columns;
487 graph->num_columns = graph->num_new_columns;
488
489 graph->new_columns = tmp_columns;
490 graph->num_new_columns = 0;
491
492 /*
493 * Now update new_columns and mapping with the information for the
494 * commit after this one.
495 *
496 * First, make sure we have enough room. At most, there will
497 * be graph->num_columns + graph->num_parents columns for the next
498 * commit.
499 */
500 max_new_columns = graph->num_columns + graph->num_parents;
501 graph_ensure_capacity(graph, max_new_columns);
502
503 /*
504 * Clear out graph->mapping
505 */
506 graph->mapping_size = 2 * max_new_columns;
507 for (i = 0; i < graph->mapping_size; i++)
508 graph->mapping[i] = -1;
509
510 /*
511 * Populate graph->new_columns and graph->mapping
512 *
513 * Some of the parents of this commit may already be in
514 * graph->columns. If so, graph->new_columns should only contain a
515 * single entry for each such commit. graph->mapping should
516 * contain information about where each current branch line is
517 * supposed to end up after the collapsing is performed.
518 */
519 seen_this = 0;
520 mapping_idx = 0;
0724cb86 521 is_commit_in_columns = 1;
c12172d2
AS
522 for (i = 0; i <= graph->num_columns; i++) {
523 struct commit *col_commit;
524 if (i == graph->num_columns) {
525 if (seen_this)
526 break;
0724cb86 527 is_commit_in_columns = 0;
c12172d2
AS
528 col_commit = graph->commit;
529 } else {
530 col_commit = graph->columns[i].commit;
531 }
532
533 if (col_commit == graph->commit) {
37a75abc 534 int old_mapping_idx = mapping_idx;
c12172d2 535 seen_this = 1;
3395908e 536 graph->commit_index = i;
a0ebe573 537 for (parent = first_interesting_parent(graph);
c12172d2 538 parent;
a0ebe573 539 parent = next_interesting_parent(graph, parent)) {
427fc5b8 540 /*
91e50b2c
AS
541 * If this is a merge, or the start of a new
542 * childless column, increment the current
427fc5b8
AC
543 * color.
544 */
91e50b2c
AS
545 if (graph->num_parents > 1 ||
546 !is_commit_in_columns) {
427fc5b8 547 graph_increment_column_color(graph);
91e50b2c 548 }
c12172d2
AS
549 graph_insert_into_new_columns(graph,
550 parent->item,
551 &mapping_idx);
552 }
37a75abc
AS
553 /*
554 * We always need to increment mapping_idx by at
555 * least 2, even if it has no interesting parents.
556 * The current commit always takes up at least 2
557 * spaces.
558 */
559 if (mapping_idx == old_mapping_idx)
560 mapping_idx += 2;
c12172d2
AS
561 } else {
562 graph_insert_into_new_columns(graph, col_commit,
563 &mapping_idx);
564 }
565 }
566
567 /*
568 * Shrink mapping_size to be the minimum necessary
569 */
570 while (graph->mapping_size > 1 &&
571 graph->mapping[graph->mapping_size - 1] < 0)
572 graph->mapping_size--;
0724cb86
AS
573
574 /*
575 * Compute graph->width for this commit
576 */
577 graph_update_width(graph, is_commit_in_columns);
c12172d2
AS
578}
579
580void graph_update(struct git_graph *graph, struct commit *commit)
581{
582 struct commit_list *parent;
583
584 /*
585 * Set the new commit
586 */
587 graph->commit = commit;
588
589 /*
37a75abc 590 * Count how many interesting parents this commit has
c12172d2
AS
591 */
592 graph->num_parents = 0;
a0ebe573
AS
593 for (parent = first_interesting_parent(graph);
594 parent;
595 parent = next_interesting_parent(graph, parent))
596 {
597 graph->num_parents++;
37a75abc 598 }
c12172d2 599
3395908e
AS
600 /*
601 * Store the old commit_index in prev_commit_index.
602 * graph_update_columns() will update graph->commit_index for this
603 * commit.
604 */
605 graph->prev_commit_index = graph->commit_index;
606
c12172d2
AS
607 /*
608 * Call graph_update_columns() to update
609 * columns, new_columns, and mapping.
610 */
611 graph_update_columns(graph);
612
613 graph->expansion_row = 0;
614
615 /*
616 * Update graph->state.
3395908e
AS
617 * Note that we don't call graph_update_state() here, since
618 * we don't want to update graph->prev_state. No line for
619 * graph->state was ever printed.
c12172d2
AS
620 *
621 * If the previous commit didn't get to the GRAPH_PADDING state,
622 * it never finished its output. Goto GRAPH_SKIP, to print out
623 * a line to indicate that portion of the graph is missing.
624 *
f1979d6b
AS
625 * If there are 3 or more parents, we may need to print extra rows
626 * before the commit, to expand the branch lines around it and make
627 * room for it. We need to do this only if there is a branch row
628 * (or more) to the right of this commit.
c12172d2
AS
629 *
630 * If there are less than 3 parents, we can immediately print the
631 * commit line.
632 */
633 if (graph->state != GRAPH_PADDING)
634 graph->state = GRAPH_SKIP;
f1979d6b
AS
635 else if (graph->num_parents >= 3 &&
636 graph->commit_index < (graph->num_columns - 1))
c12172d2
AS
637 graph->state = GRAPH_PRE_COMMIT;
638 else
639 graph->state = GRAPH_COMMIT;
640}
641
642static int graph_is_mapping_correct(struct git_graph *graph)
643{
644 int i;
645
646 /*
647 * The mapping is up to date if each entry is at its target,
648 * or is 1 greater than its target.
649 * (If it is 1 greater than the target, '/' will be printed, so it
650 * will look correct on the next row.)
651 */
652 for (i = 0; i < graph->mapping_size; i++) {
653 int target = graph->mapping[i];
654 if (target < 0)
655 continue;
656 if (target == (i / 2))
657 continue;
658 return 0;
659 }
660
661 return 1;
662}
663
427fc5b8
AC
664static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
665 int chars_written)
c12172d2
AS
666{
667 /*
668 * Add additional spaces to the end of the strbuf, so that all
669 * lines for a particular commit have the same width.
670 *
671 * This way, fields printed to the right of the graph will remain
672 * aligned for the entire commit.
c12172d2 673 */
0724cb86 674 int extra;
427fc5b8 675 if (chars_written >= graph->width)
c12172d2
AS
676 return;
677
427fc5b8 678 extra = graph->width - chars_written;
c12172d2
AS
679 strbuf_addf(sb, "%*s", (int) extra, "");
680}
681
682static void graph_output_padding_line(struct git_graph *graph,
683 struct strbuf *sb)
684{
685 int i;
686
687 /*
688 * We could conceivable be called with a NULL commit
689 * if our caller has a bug, and invokes graph_next_line()
690 * immediately after graph_init(), without first calling
691 * graph_update(). Return without outputting anything in this
692 * case.
693 */
694 if (!graph->commit)
695 return;
696
697 /*
698 * Output a padding row, that leaves all branch lines unchanged
699 */
700 for (i = 0; i < graph->num_new_columns; i++) {
427fc5b8
AC
701 strbuf_write_column(sb, &graph->new_columns[i], '|');
702 strbuf_addch(sb, ' ');
c12172d2
AS
703 }
704
427fc5b8 705 graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
c12172d2
AS
706}
707
708static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
709{
710 /*
711 * Output an ellipsis to indicate that a portion
712 * of the graph is missing.
713 */
714 strbuf_addstr(sb, "...");
427fc5b8 715 graph_pad_horizontally(graph, sb, 3);
c12172d2 716
f1979d6b
AS
717 if (graph->num_parents >= 3 &&
718 graph->commit_index < (graph->num_columns - 1))
3395908e 719 graph_update_state(graph, GRAPH_PRE_COMMIT);
c12172d2 720 else
3395908e 721 graph_update_state(graph, GRAPH_COMMIT);
c12172d2
AS
722}
723
724static void graph_output_pre_commit_line(struct git_graph *graph,
725 struct strbuf *sb)
726{
727 int num_expansion_rows;
728 int i, seen_this;
427fc5b8 729 int chars_written;
c12172d2
AS
730
731 /*
732 * This function formats a row that increases the space around a commit
733 * with multiple parents, to make room for it. It should only be
734 * called when there are 3 or more parents.
735 *
736 * We need 2 extra rows for every parent over 2.
737 */
738 assert(graph->num_parents >= 3);
739 num_expansion_rows = (graph->num_parents - 2) * 2;
740
741 /*
742 * graph->expansion_row tracks the current expansion row we are on.
743 * It should be in the range [0, num_expansion_rows - 1]
744 */
745 assert(0 <= graph->expansion_row &&
746 graph->expansion_row < num_expansion_rows);
747
748 /*
749 * Output the row
750 */
751 seen_this = 0;
427fc5b8 752 chars_written = 0;
c12172d2
AS
753 for (i = 0; i < graph->num_columns; i++) {
754 struct column *col = &graph->columns[i];
755 if (col->commit == graph->commit) {
756 seen_this = 1;
427fc5b8 757 strbuf_write_column(sb, col, '|');
36a31fea
AC
758 strbuf_addf(sb, "%*s", graph->expansion_row, "");
759 chars_written += 1 + graph->expansion_row;
3395908e
AS
760 } else if (seen_this && (graph->expansion_row == 0)) {
761 /*
762 * This is the first line of the pre-commit output.
763 * If the previous commit was a merge commit and
764 * ended in the GRAPH_POST_MERGE state, all branch
765 * lines after graph->prev_commit_index were
766 * printed as "\" on the previous line. Continue
767 * to print them as "\" on this line. Otherwise,
768 * print the branch lines as "|".
769 */
770 if (graph->prev_state == GRAPH_POST_MERGE &&
771 graph->prev_commit_index < i)
427fc5b8 772 strbuf_write_column(sb, col, '\\');
3395908e 773 else
427fc5b8
AC
774 strbuf_write_column(sb, col, '|');
775 chars_written++;
3395908e 776 } else if (seen_this && (graph->expansion_row > 0)) {
427fc5b8
AC
777 strbuf_write_column(sb, col, '\\');
778 chars_written++;
c12172d2 779 } else {
427fc5b8
AC
780 strbuf_write_column(sb, col, '|');
781 chars_written++;
c12172d2 782 }
427fc5b8
AC
783 strbuf_addch(sb, ' ');
784 chars_written++;
c12172d2
AS
785 }
786
427fc5b8 787 graph_pad_horizontally(graph, sb, chars_written);
c12172d2
AS
788
789 /*
790 * Increment graph->expansion_row,
791 * and move to state GRAPH_COMMIT if necessary
792 */
793 graph->expansion_row++;
794 if (graph->expansion_row >= num_expansion_rows)
3395908e 795 graph_update_state(graph, GRAPH_COMMIT);
c12172d2
AS
796}
797
3c68d67b
AS
798static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
799{
800 /*
801 * For boundary commits, print 'o'
802 * (We should only see boundary commits when revs->boundary is set.)
803 */
804 if (graph->commit->object.flags & BOUNDARY) {
805 assert(graph->revs->boundary);
806 strbuf_addch(sb, 'o');
807 return;
808 }
809
810 /*
1df2d656 811 * get_revision_mark() handles all other cases without assert()
3c68d67b 812 */
1df2d656 813 strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit));
3c68d67b
AS
814}
815
427fc5b8
AC
816/*
817 * Draw an octopus merge and return the number of characters written.
818 */
819static int graph_draw_octopus_merge(struct git_graph *graph,
820 struct strbuf *sb)
821{
822 /*
823 * Here dashless_commits represents the number of parents
824 * which don't need to have dashes (because their edges fit
825 * neatly under the commit).
826 */
827 const int dashless_commits = 2;
828 int col_num, i;
829 int num_dashes =
830 ((graph->num_parents - dashless_commits) * 2) - 1;
831 for (i = 0; i < num_dashes; i++) {
832 col_num = (i / 2) + dashless_commits;
833 strbuf_write_column(sb, &graph->new_columns[col_num], '-');
834 }
835 col_num = (i / 2) + dashless_commits;
836 strbuf_write_column(sb, &graph->new_columns[col_num], '.');
837 return num_dashes + 1;
838}
839
064bfbde 840static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
c12172d2
AS
841{
842 int seen_this = 0;
427fc5b8 843 int i, chars_written;
c12172d2
AS
844
845 /*
846 * Output the row containing this commit
847 * Iterate up to and including graph->num_columns,
848 * since the current commit may not be in any of the existing
849 * columns. (This happens when the current commit doesn't have any
850 * children that we have already processed.)
851 */
852 seen_this = 0;
427fc5b8 853 chars_written = 0;
c12172d2 854 for (i = 0; i <= graph->num_columns; i++) {
427fc5b8 855 struct column *col = &graph->columns[i];
c12172d2
AS
856 struct commit *col_commit;
857 if (i == graph->num_columns) {
858 if (seen_this)
859 break;
860 col_commit = graph->commit;
861 } else {
862 col_commit = graph->columns[i].commit;
863 }
864
865 if (col_commit == graph->commit) {
866 seen_this = 1;
3c68d67b 867 graph_output_commit_char(graph, sb);
427fc5b8 868 chars_written++;
c12172d2 869
a6c1a382 870 if (graph->num_parents > 2)
427fc5b8
AC
871 chars_written += graph_draw_octopus_merge(graph,
872 sb);
3395908e 873 } else if (seen_this && (graph->num_parents > 2)) {
427fc5b8
AC
874 strbuf_write_column(sb, col, '\\');
875 chars_written++;
3395908e
AS
876 } else if (seen_this && (graph->num_parents == 2)) {
877 /*
878 * This is a 2-way merge commit.
879 * There is no GRAPH_PRE_COMMIT stage for 2-way
880 * merges, so this is the first line of output
881 * for this commit. Check to see what the previous
882 * line of output was.
883 *
884 * If it was GRAPH_POST_MERGE, the branch line
885 * coming into this commit may have been '\',
886 * and not '|' or '/'. If so, output the branch
887 * line as '\' on this line, instead of '|'. This
888 * makes the output look nicer.
889 */
890 if (graph->prev_state == GRAPH_POST_MERGE &&
891 graph->prev_commit_index < i)
427fc5b8 892 strbuf_write_column(sb, col, '\\');
3395908e 893 else
427fc5b8
AC
894 strbuf_write_column(sb, col, '|');
895 chars_written++;
c12172d2 896 } else {
427fc5b8
AC
897 strbuf_write_column(sb, col, '|');
898 chars_written++;
c12172d2 899 }
427fc5b8
AC
900 strbuf_addch(sb, ' ');
901 chars_written++;
c12172d2
AS
902 }
903
427fc5b8 904 graph_pad_horizontally(graph, sb, chars_written);
c12172d2
AS
905
906 /*
907 * Update graph->state
908 */
909 if (graph->num_parents > 1)
3395908e 910 graph_update_state(graph, GRAPH_POST_MERGE);
c12172d2 911 else if (graph_is_mapping_correct(graph))
3395908e 912 graph_update_state(graph, GRAPH_PADDING);
c12172d2 913 else
3395908e 914 graph_update_state(graph, GRAPH_COLLAPSING);
c12172d2
AS
915}
916
427fc5b8
AC
917static struct column *find_new_column_by_commit(struct git_graph *graph,
918 struct commit *commit)
919{
920 int i;
921 for (i = 0; i < graph->num_new_columns; i++) {
922 if (graph->new_columns[i].commit == commit)
923 return &graph->new_columns[i];
924 }
67da52be 925 return NULL;
427fc5b8
AC
926}
927
064bfbde 928static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
c12172d2
AS
929{
930 int seen_this = 0;
427fc5b8 931 int i, j, chars_written;
c12172d2
AS
932
933 /*
934 * Output the post-merge row
935 */
427fc5b8 936 chars_written = 0;
c12172d2 937 for (i = 0; i <= graph->num_columns; i++) {
427fc5b8 938 struct column *col = &graph->columns[i];
c12172d2
AS
939 struct commit *col_commit;
940 if (i == graph->num_columns) {
941 if (seen_this)
942 break;
943 col_commit = graph->commit;
944 } else {
427fc5b8 945 col_commit = col->commit;
c12172d2
AS
946 }
947
948 if (col_commit == graph->commit) {
427fc5b8
AC
949 /*
950 * Since the current commit is a merge find
951 * the columns for the parent commits in
952 * new_columns and use those to format the
953 * edges.
954 */
955 struct commit_list *parents = NULL;
956 struct column *par_column;
c12172d2 957 seen_this = 1;
427fc5b8
AC
958 parents = first_interesting_parent(graph);
959 assert(parents);
960 par_column = find_new_column_by_commit(graph, parents->item);
961 assert(par_column);
962
963 strbuf_write_column(sb, par_column, '|');
964 chars_written++;
965 for (j = 0; j < graph->num_parents - 1; j++) {
966 parents = next_interesting_parent(graph, parents);
967 assert(parents);
968 par_column = find_new_column_by_commit(graph, parents->item);
969 assert(par_column);
970 strbuf_write_column(sb, par_column, '\\');
971 strbuf_addch(sb, ' ');
972 }
973 chars_written += j * 2;
3395908e 974 } else if (seen_this) {
427fc5b8
AC
975 strbuf_write_column(sb, col, '\\');
976 strbuf_addch(sb, ' ');
977 chars_written += 2;
c12172d2 978 } else {
427fc5b8
AC
979 strbuf_write_column(sb, col, '|');
980 strbuf_addch(sb, ' ');
981 chars_written += 2;
c12172d2
AS
982 }
983 }
984
427fc5b8 985 graph_pad_horizontally(graph, sb, chars_written);
c12172d2
AS
986
987 /*
988 * Update graph->state
989 */
990 if (graph_is_mapping_correct(graph))
3395908e 991 graph_update_state(graph, GRAPH_PADDING);
c12172d2 992 else
3395908e 993 graph_update_state(graph, GRAPH_COLLAPSING);
c12172d2
AS
994}
995
064bfbde 996static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
c12172d2
AS
997{
998 int i;
999 int *tmp_mapping;
eaf158f8
AC
1000 short used_horizontal = 0;
1001 int horizontal_edge = -1;
1002 int horizontal_edge_target = -1;
c12172d2
AS
1003
1004 /*
1005 * Clear out the new_mapping array
1006 */
1007 for (i = 0; i < graph->mapping_size; i++)
1008 graph->new_mapping[i] = -1;
1009
1010 for (i = 0; i < graph->mapping_size; i++) {
1011 int target = graph->mapping[i];
1012 if (target < 0)
1013 continue;
1014
1015 /*
1016 * Since update_columns() always inserts the leftmost
1017 * column first, each branch's target location should
1018 * always be either its current location or to the left of
1019 * its current location.
1020 *
1021 * We never have to move branches to the right. This makes
1022 * the graph much more legible, since whenever branches
1023 * cross, only one is moving directions.
1024 */
1025 assert(target * 2 <= i);
1026
1027 if (target * 2 == i) {
1028 /*
1029 * This column is already in the
1030 * correct place
1031 */
1032 assert(graph->new_mapping[i] == -1);
1033 graph->new_mapping[i] = target;
1034 } else if (graph->new_mapping[i - 1] < 0) {
1035 /*
1036 * Nothing is to the left.
1037 * Move to the left by one
1038 */
1039 graph->new_mapping[i - 1] = target;
eaf158f8
AC
1040 /*
1041 * If there isn't already an edge moving horizontally
1042 * select this one.
1043 */
1044 if (horizontal_edge == -1) {
1045 int j;
1046 horizontal_edge = i;
1047 horizontal_edge_target = target;
1048 /*
1049 * The variable target is the index of the graph
1050 * column, and therefore target*2+3 is the
1051 * actual screen column of the first horizontal
1052 * line.
1053 */
1054 for (j = (target * 2)+3; j < (i - 2); j += 2)
1055 graph->new_mapping[j] = target;
1056 }
c12172d2
AS
1057 } else if (graph->new_mapping[i - 1] == target) {
1058 /*
1059 * There is a branch line to our left
1060 * already, and it is our target. We
1061 * combine with this line, since we share
1062 * the same parent commit.
1063 *
1064 * We don't have to add anything to the
1065 * output or new_mapping, since the
1066 * existing branch line has already taken
1067 * care of it.
1068 */
1069 } else {
1070 /*
1071 * There is a branch line to our left,
1072 * but it isn't our target. We need to
1073 * cross over it.
1074 *
1075 * The space just to the left of this
1076 * branch should always be empty.
eaf158f8
AC
1077 *
1078 * The branch to the left of that space
1079 * should be our eventual target.
c12172d2
AS
1080 */
1081 assert(graph->new_mapping[i - 1] > target);
1082 assert(graph->new_mapping[i - 2] < 0);
eaf158f8 1083 assert(graph->new_mapping[i - 3] == target);
c12172d2 1084 graph->new_mapping[i - 2] = target;
eaf158f8
AC
1085 /*
1086 * Mark this branch as the horizontal edge to
1087 * prevent any other edges from moving
1088 * horizontally.
1089 */
1090 if (horizontal_edge == -1)
1091 horizontal_edge = i;
c12172d2
AS
1092 }
1093 }
1094
1095 /*
1096 * The new mapping may be 1 smaller than the old mapping
1097 */
1098 if (graph->new_mapping[graph->mapping_size - 1] < 0)
1099 graph->mapping_size--;
1100
1101 /*
1102 * Output out a line based on the new mapping info
1103 */
1104 for (i = 0; i < graph->mapping_size; i++) {
1105 int target = graph->new_mapping[i];
1106 if (target < 0)
1107 strbuf_addch(sb, ' ');
1108 else if (target * 2 == i)
427fc5b8 1109 strbuf_write_column(sb, &graph->new_columns[target], '|');
eaf158f8
AC
1110 else if (target == horizontal_edge_target &&
1111 i != horizontal_edge - 1) {
1112 /*
1113 * Set the mappings for all but the
1114 * first segment to -1 so that they
1115 * won't continue into the next line.
1116 */
1117 if (i != (target * 2)+3)
1118 graph->new_mapping[i] = -1;
1119 used_horizontal = 1;
1120 strbuf_write_column(sb, &graph->new_columns[target], '_');
1121 } else {
1122 if (used_horizontal && i < horizontal_edge)
1123 graph->new_mapping[i] = -1;
427fc5b8 1124 strbuf_write_column(sb, &graph->new_columns[target], '/');
eaf158f8
AC
1125
1126 }
c12172d2
AS
1127 }
1128
427fc5b8 1129 graph_pad_horizontally(graph, sb, graph->mapping_size);
c12172d2
AS
1130
1131 /*
1132 * Swap mapping and new_mapping
1133 */
1134 tmp_mapping = graph->mapping;
1135 graph->mapping = graph->new_mapping;
1136 graph->new_mapping = tmp_mapping;
1137
1138 /*
1139 * If graph->mapping indicates that all of the branch lines
1140 * are already in the correct positions, we are done.
1141 * Otherwise, we need to collapse some branch lines together.
1142 */
1143 if (graph_is_mapping_correct(graph))
3395908e 1144 graph_update_state(graph, GRAPH_PADDING);
c12172d2
AS
1145}
1146
ba354804 1147static int graph_next_line(struct git_graph *graph, struct strbuf *sb)
c12172d2
AS
1148{
1149 switch (graph->state) {
1150 case GRAPH_PADDING:
1151 graph_output_padding_line(graph, sb);
1152 return 0;
1153 case GRAPH_SKIP:
1154 graph_output_skip_line(graph, sb);
1155 return 0;
1156 case GRAPH_PRE_COMMIT:
1157 graph_output_pre_commit_line(graph, sb);
1158 return 0;
1159 case GRAPH_COMMIT:
1160 graph_output_commit_line(graph, sb);
1161 return 1;
1162 case GRAPH_POST_MERGE:
1163 graph_output_post_merge_line(graph, sb);
1164 return 0;
1165 case GRAPH_COLLAPSING:
1166 graph_output_collapsing_line(graph, sb);
1167 return 0;
1168 }
1169
1170 assert(0);
1171 return 0;
1172}
1173
064bfbde 1174static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
c12172d2
AS
1175{
1176 int i, j;
1177
1178 if (graph->state != GRAPH_COMMIT) {
1179 graph_next_line(graph, sb);
1180 return;
1181 }
1182
1183 /*
1184 * Output the row containing this commit
1185 * Iterate up to and including graph->num_columns,
1186 * since the current commit may not be in any of the existing
1187 * columns. (This happens when the current commit doesn't have any
1188 * children that we have already processed.)
1189 */
1190 for (i = 0; i < graph->num_columns; i++) {
427fc5b8
AC
1191 struct column *col = &graph->columns[i];
1192 struct commit *col_commit = col->commit;
c12172d2 1193 if (col_commit == graph->commit) {
427fc5b8 1194 strbuf_write_column(sb, col, '|');
c12172d2
AS
1195
1196 if (graph->num_parents < 3)
1197 strbuf_addch(sb, ' ');
1198 else {
1199 int num_spaces = ((graph->num_parents - 2) * 2);
1200 for (j = 0; j < num_spaces; j++)
1201 strbuf_addch(sb, ' ');
1202 }
1203 } else {
427fc5b8
AC
1204 strbuf_write_column(sb, col, '|');
1205 strbuf_addch(sb, ' ');
c12172d2
AS
1206 }
1207 }
1208
427fc5b8 1209 graph_pad_horizontally(graph, sb, graph->num_columns);
3395908e
AS
1210
1211 /*
1212 * Update graph->prev_state since we have output a padding line
1213 */
1214 graph->prev_state = GRAPH_PADDING;
c12172d2
AS
1215}
1216
1217int graph_is_commit_finished(struct git_graph const *graph)
1218{
1219 return (graph->state == GRAPH_PADDING);
1220}
1221
1222void graph_show_commit(struct git_graph *graph)
1223{
f285a2d7 1224 struct strbuf msgbuf = STRBUF_INIT;
c12172d2
AS
1225 int shown_commit_line = 0;
1226
1227 if (!graph)
1228 return;
1229
656197ad 1230 while (!shown_commit_line && !graph_is_commit_finished(graph)) {
c12172d2
AS
1231 shown_commit_line = graph_next_line(graph, &msgbuf);
1232 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1233 if (!shown_commit_line)
1234 putchar('\n');
1235 strbuf_setlen(&msgbuf, 0);
1236 }
1237
1238 strbuf_release(&msgbuf);
1239}
1240
1241void graph_show_oneline(struct git_graph *graph)
1242{
f285a2d7 1243 struct strbuf msgbuf = STRBUF_INIT;
c12172d2
AS
1244
1245 if (!graph)
1246 return;
1247
c12172d2
AS
1248 graph_next_line(graph, &msgbuf);
1249 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1250 strbuf_release(&msgbuf);
1251}
1252
1253void graph_show_padding(struct git_graph *graph)
1254{
f285a2d7 1255 struct strbuf msgbuf = STRBUF_INIT;
c12172d2
AS
1256
1257 if (!graph)
1258 return;
1259
c12172d2
AS
1260 graph_padding_line(graph, &msgbuf);
1261 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1262 strbuf_release(&msgbuf);
1263}
1264
1265int graph_show_remainder(struct git_graph *graph)
1266{
f285a2d7 1267 struct strbuf msgbuf = STRBUF_INIT;
c12172d2
AS
1268 int shown = 0;
1269
1270 if (!graph)
1271 return 0;
1272
1273 if (graph_is_commit_finished(graph))
1274 return 0;
1275
c12172d2
AS
1276 for (;;) {
1277 graph_next_line(graph, &msgbuf);
1278 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1279 strbuf_setlen(&msgbuf, 0);
1280 shown = 1;
1281
1282 if (!graph_is_commit_finished(graph))
1283 putchar('\n');
1284 else
1285 break;
1286 }
1287 strbuf_release(&msgbuf);
1288
1289 return shown;
1290}
1291
1292
064bfbde 1293static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)
c12172d2
AS
1294{
1295 char *p;
1296
1297 if (!graph) {
1298 fwrite(sb->buf, sizeof(char), sb->len, stdout);
1299 return;
1300 }
1301
1302 /*
1303 * Print the strbuf line by line,
1304 * and display the graph info before each line but the first.
1305 */
1306 p = sb->buf;
1307 while (p) {
1308 size_t len;
1309 char *next_p = strchr(p, '\n');
1310 if (next_p) {
1311 next_p++;
1312 len = next_p - p;
1313 } else {
1314 len = (sb->buf + sb->len) - p;
1315 }
1316 fwrite(p, sizeof(char), len, stdout);
1317 if (next_p && *next_p != '\0')
1318 graph_show_oneline(graph);
1319 p = next_p;
1320 }
1321}
1322
1323void graph_show_commit_msg(struct git_graph *graph,
1324 struct strbuf const *sb)
1325{
1326 int newline_terminated;
1327
1328 if (!graph) {
1329 /*
1330 * If there's no graph, just print the message buffer.
1331 *
1332 * The message buffer for CMIT_FMT_ONELINE and
1333 * CMIT_FMT_USERFORMAT are already missing a terminating
1334 * newline. All of the other formats should have it.
1335 */
1336 fwrite(sb->buf, sizeof(char), sb->len, stdout);
1337 return;
1338 }
1339
1340 newline_terminated = (sb->len && sb->buf[sb->len - 1] == '\n');
1341
1342 /*
1343 * Show the commit message
1344 */
1345 graph_show_strbuf(graph, sb);
1346
1347 /*
1348 * If there is more output needed for this commit, show it now
1349 */
1350 if (!graph_is_commit_finished(graph)) {
1351 /*
1352 * If sb doesn't have a terminating newline, print one now,
1353 * so we can start the remainder of the graph output on a
1354 * new line.
1355 */
1356 if (!newline_terminated)
1357 putchar('\n');
1358
1359 graph_show_remainder(graph);
1360
1361 /*
1362 * If sb ends with a newline, our output should too.
1363 */
1364 if (newline_terminated)
1365 putchar('\n');
1366 }
1367}