Merge branch 'nd/index-pack-l10n-buf-overflow' into maint-1.8.1
[git/jnareb-git.git] / graph.c
blob391a712e5eafbc05b8d4b739d96aaca0dd481460
1 #include "cache.h"
2 #include "commit.h"
3 #include "color.h"
4 #include "graph.h"
5 #include "diff.h"
6 #include "revision.h"
8 /* Internal API */
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.
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.
19 static int graph_next_line(struct git_graph *graph, struct strbuf *sb);
22 * Set up a custom scheme for column colors.
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.
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.
34 * This functions must be called BEFORE graph_init() is called.
36 static void graph_set_column_colors(const char **colors, unsigned short colors_max);
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.
45 static void graph_padding_line(struct git_graph *graph, struct strbuf *sb);
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.
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.
55 * Since the first line will not include the graph output, the caller is
56 * responsible for printing this line's graph (perhaps via
57 * graph_show_commit() or graph_show_oneline()) before calling
58 * graph_show_strbuf().
60 static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
63 * TODO:
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.
69 struct column {
71 * The parent commit of this column.
73 struct commit *commit;
75 * The color to (optionally) print this column in. This is an
76 * index into column_colors.
78 unsigned short color;
81 enum graph_state {
82 GRAPH_PADDING,
83 GRAPH_SKIP,
84 GRAPH_PRE_COMMIT,
85 GRAPH_COMMIT,
86 GRAPH_POST_MERGE,
87 GRAPH_COLLAPSING
90 static const char **column_colors;
91 static unsigned short column_colors_max;
93 static void graph_set_column_colors(const char **colors, unsigned short colors_max)
95 column_colors = colors;
96 column_colors_max = colors_max;
99 static const char *column_get_color_code(unsigned short color)
101 return column_colors[color];
104 static void strbuf_write_column(struct strbuf *sb, const struct column *c,
105 char col_char)
107 if (c->color < column_colors_max)
108 strbuf_addstr(sb, column_get_color_code(c->color));
109 strbuf_addch(sb, col_char);
110 if (c->color < column_colors_max)
111 strbuf_addstr(sb, column_get_color_code(column_colors_max));
114 struct git_graph {
116 * The commit currently being processed
118 struct commit *commit;
119 /* The rev-info used for the current traversal */
120 struct rev_info *revs;
122 * The number of interesting parents that this commit has.
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().
128 int num_parents;
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.
134 int width;
136 * The next expansion row to print
137 * when state is GRAPH_PRE_COMMIT
139 int expansion_row;
141 * The current output state.
142 * This tells us what kind of line graph_next_line() should output.
144 enum graph_state state;
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.
150 enum graph_state prev_state;
152 * The index of the column that refers to this commit.
154 * If none of the incoming columns refer to this commit,
155 * this will be equal to num_columns.
157 int commit_index;
159 * The commit_index for the previously displayed commit.
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.
165 int prev_commit_index;
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.
171 int column_capacity;
173 * The number of columns (also called "branch lines" in some places)
175 int num_columns;
177 * The number of columns in the new_columns array
179 int num_new_columns;
181 * The number of entries in the mapping array
183 int mapping_size;
185 * The column state before we output the current commit.
187 struct column *columns;
189 * The new column state after we output the current commit.
190 * Only valid when state is GRAPH_COLLAPSING.
192 struct column *new_columns;
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.)
202 * The maximum capacity of this array is always
203 * sizeof(int) * 2 * column_capacity.
205 int *mapping;
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.
212 int *new_mapping;
214 * The current default column color being used. This is
215 * stored as an index into the array column_colors.
217 unsigned short default_column_color;
220 static struct strbuf *diff_output_prefix_callback(struct diff_options *opt, void *data)
222 struct git_graph *graph = data;
223 static struct strbuf msgbuf = STRBUF_INIT;
225 assert(opt);
226 assert(graph);
228 opt->output_prefix_length = graph->width;
229 strbuf_reset(&msgbuf);
230 graph_padding_line(graph, &msgbuf);
231 return &msgbuf;
234 struct git_graph *graph_init(struct rev_info *opt)
236 struct git_graph *graph = xmalloc(sizeof(struct git_graph));
238 if (!column_colors)
239 graph_set_column_colors(column_colors_ansi,
240 column_colors_ansi_max);
242 graph->commit = NULL;
243 graph->revs = opt;
244 graph->num_parents = 0;
245 graph->expansion_row = 0;
246 graph->state = GRAPH_PADDING;
247 graph->prev_state = GRAPH_PADDING;
248 graph->commit_index = 0;
249 graph->prev_commit_index = 0;
250 graph->num_columns = 0;
251 graph->num_new_columns = 0;
252 graph->mapping_size = 0;
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.
258 graph->default_column_color = column_colors_max - 1;
261 * Allocate a reasonably large default number of columns
262 * We'll automatically grow columns later if we need more room.
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);
273 * The diff output prefix callback, with this we can make
274 * all the diff output to align with the graph lines.
276 opt->diffopt.output_prefix = diff_output_prefix_callback;
277 opt->diffopt.output_prefix_data = graph;
278 opt->diffopt.output_prefix_length = 0;
280 return graph;
283 static void graph_update_state(struct git_graph *graph, enum graph_state s)
285 graph->prev_state = graph->state;
286 graph->state = s;
289 static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
291 if (graph->column_capacity >= num_columns)
292 return;
294 do {
295 graph->column_capacity *= 2;
296 } while (graph->column_capacity < num_columns);
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);
311 * Returns 1 if the commit will be printed in the graph output,
312 * and 0 otherwise.
314 static int graph_is_interesting(struct git_graph *graph, struct commit *commit)
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.
321 if (graph->revs && graph->revs->boundary) {
322 if (commit->object.flags & CHILD_SHOWN)
323 return 1;
327 * Otherwise, use get_commit_action() to see if this commit is
328 * interesting
330 return get_commit_action(graph->revs, commit) == commit_show;
333 static struct commit_list *next_interesting_parent(struct git_graph *graph,
334 struct commit_list *orig)
336 struct commit_list *list;
339 * If revs->first_parent_only is set, only the first
340 * parent is interesting. None of the others are.
342 if (graph->revs->first_parent_only)
343 return NULL;
346 * Return the next interesting commit after orig
348 for (list = orig->next; list; list = list->next) {
349 if (graph_is_interesting(graph, list->item))
350 return list;
353 return NULL;
356 static struct commit_list *first_interesting_parent(struct git_graph *graph)
358 struct commit_list *parents = graph->commit->parents;
361 * If this commit has no parents, ignore it
363 if (!parents)
364 return NULL;
367 * If the first parent is interesting, return it
369 if (graph_is_interesting(graph, parents->item))
370 return parents;
373 * Otherwise, call next_interesting_parent() to get
374 * the next interesting parent
376 return next_interesting_parent(graph, parents);
379 static unsigned short graph_get_current_column_color(const struct git_graph *graph)
381 if (!want_color(graph->revs->diffopt.use_color))
382 return column_colors_max;
383 return graph->default_column_color;
387 * Update the graph's default column color.
389 static void graph_increment_column_color(struct git_graph *graph)
391 graph->default_column_color = (graph->default_column_color + 1) %
392 column_colors_max;
395 static unsigned short graph_find_commit_color(const struct git_graph *graph,
396 const struct commit *commit)
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;
403 return graph_get_current_column_color(graph);
406 static void graph_insert_into_new_columns(struct git_graph *graph,
407 struct commit *commit,
408 int *mapping_index)
410 int i;
413 * If the commit is already in the new_columns list, we don't need to
414 * add it. Just update the mapping correctly.
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;
425 * This commit isn't already in new_columns. Add it.
427 graph->new_columns[graph->num_new_columns].commit = commit;
428 graph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit);
429 graph->mapping[*mapping_index] = graph->num_new_columns;
430 *mapping_index += 2;
431 graph->num_new_columns++;
434 static void graph_update_width(struct git_graph *graph,
435 int is_commit_in_existing_columns)
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.
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.
446 int max_cols = graph->num_columns + graph->num_parents;
449 * Even if the current commit has no parents to be printed, it
450 * still takes up a column for itself.
452 if (graph->num_parents < 1)
453 max_cols++;
456 * We added a column for the current commit as part of
457 * graph->num_parents. If the current commit was already in
458 * graph->columns, then we have double counted it.
460 if (is_commit_in_existing_columns)
461 max_cols--;
464 * Each column takes up 2 spaces
466 graph->width = max_cols * 2;
469 static void graph_update_columns(struct git_graph *graph)
471 struct commit_list *parent;
472 struct column *tmp_columns;
473 int max_new_columns;
474 int mapping_idx;
475 int i, seen_this, is_commit_in_columns;
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.
482 * We'll re-use the old columns array as storage to compute the new
483 * columns list for the commit after this one.
485 tmp_columns = graph->columns;
486 graph->columns = graph->new_columns;
487 graph->num_columns = graph->num_new_columns;
489 graph->new_columns = tmp_columns;
490 graph->num_new_columns = 0;
493 * Now update new_columns and mapping with the information for the
494 * commit after this one.
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.
500 max_new_columns = graph->num_columns + graph->num_parents;
501 graph_ensure_capacity(graph, max_new_columns);
504 * Clear out graph->mapping
506 graph->mapping_size = 2 * max_new_columns;
507 for (i = 0; i < graph->mapping_size; i++)
508 graph->mapping[i] = -1;
511 * Populate graph->new_columns and graph->mapping
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.
519 seen_this = 0;
520 mapping_idx = 0;
521 is_commit_in_columns = 1;
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;
527 is_commit_in_columns = 0;
528 col_commit = graph->commit;
529 } else {
530 col_commit = graph->columns[i].commit;
533 if (col_commit == graph->commit) {
534 int old_mapping_idx = mapping_idx;
535 seen_this = 1;
536 graph->commit_index = i;
537 for (parent = first_interesting_parent(graph);
538 parent;
539 parent = next_interesting_parent(graph, parent)) {
541 * If this is a merge, or the start of a new
542 * childless column, increment the current
543 * color.
545 if (graph->num_parents > 1 ||
546 !is_commit_in_columns) {
547 graph_increment_column_color(graph);
549 graph_insert_into_new_columns(graph,
550 parent->item,
551 &mapping_idx);
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.
559 if (mapping_idx == old_mapping_idx)
560 mapping_idx += 2;
561 } else {
562 graph_insert_into_new_columns(graph, col_commit,
563 &mapping_idx);
568 * Shrink mapping_size to be the minimum necessary
570 while (graph->mapping_size > 1 &&
571 graph->mapping[graph->mapping_size - 1] < 0)
572 graph->mapping_size--;
575 * Compute graph->width for this commit
577 graph_update_width(graph, is_commit_in_columns);
580 void graph_update(struct git_graph *graph, struct commit *commit)
582 struct commit_list *parent;
585 * Set the new commit
587 graph->commit = commit;
590 * Count how many interesting parents this commit has
592 graph->num_parents = 0;
593 for (parent = first_interesting_parent(graph);
594 parent;
595 parent = next_interesting_parent(graph, parent))
597 graph->num_parents++;
601 * Store the old commit_index in prev_commit_index.
602 * graph_update_columns() will update graph->commit_index for this
603 * commit.
605 graph->prev_commit_index = graph->commit_index;
608 * Call graph_update_columns() to update
609 * columns, new_columns, and mapping.
611 graph_update_columns(graph);
613 graph->expansion_row = 0;
616 * Update graph->state.
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.
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.
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.
630 * If there are less than 3 parents, we can immediately print the
631 * commit line.
633 if (graph->state != GRAPH_PADDING)
634 graph->state = GRAPH_SKIP;
635 else if (graph->num_parents >= 3 &&
636 graph->commit_index < (graph->num_columns - 1))
637 graph->state = GRAPH_PRE_COMMIT;
638 else
639 graph->state = GRAPH_COMMIT;
642 static int graph_is_mapping_correct(struct git_graph *graph)
644 int i;
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.)
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;
661 return 1;
664 static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
665 int chars_written)
668 * Add additional spaces to the end of the strbuf, so that all
669 * lines for a particular commit have the same width.
671 * This way, fields printed to the right of the graph will remain
672 * aligned for the entire commit.
674 int extra;
675 if (chars_written >= graph->width)
676 return;
678 extra = graph->width - chars_written;
679 strbuf_addf(sb, "%*s", (int) extra, "");
682 static void graph_output_padding_line(struct git_graph *graph,
683 struct strbuf *sb)
685 int i;
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.
694 if (!graph->commit)
695 return;
698 * Output a padding row, that leaves all branch lines unchanged
700 for (i = 0; i < graph->num_new_columns; i++) {
701 strbuf_write_column(sb, &graph->new_columns[i], '|');
702 strbuf_addch(sb, ' ');
705 graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
708 static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
711 * Output an ellipsis to indicate that a portion
712 * of the graph is missing.
714 strbuf_addstr(sb, "...");
715 graph_pad_horizontally(graph, sb, 3);
717 if (graph->num_parents >= 3 &&
718 graph->commit_index < (graph->num_columns - 1))
719 graph_update_state(graph, GRAPH_PRE_COMMIT);
720 else
721 graph_update_state(graph, GRAPH_COMMIT);
724 static void graph_output_pre_commit_line(struct git_graph *graph,
725 struct strbuf *sb)
727 int num_expansion_rows;
728 int i, seen_this;
729 int chars_written;
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.
736 * We need 2 extra rows for every parent over 2.
738 assert(graph->num_parents >= 3);
739 num_expansion_rows = (graph->num_parents - 2) * 2;
742 * graph->expansion_row tracks the current expansion row we are on.
743 * It should be in the range [0, num_expansion_rows - 1]
745 assert(0 <= graph->expansion_row &&
746 graph->expansion_row < num_expansion_rows);
749 * Output the row
751 seen_this = 0;
752 chars_written = 0;
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;
757 strbuf_write_column(sb, col, '|');
758 strbuf_addf(sb, "%*s", graph->expansion_row, "");
759 chars_written += 1 + graph->expansion_row;
760 } else if (seen_this && (graph->expansion_row == 0)) {
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 "|".
770 if (graph->prev_state == GRAPH_POST_MERGE &&
771 graph->prev_commit_index < i)
772 strbuf_write_column(sb, col, '\\');
773 else
774 strbuf_write_column(sb, col, '|');
775 chars_written++;
776 } else if (seen_this && (graph->expansion_row > 0)) {
777 strbuf_write_column(sb, col, '\\');
778 chars_written++;
779 } else {
780 strbuf_write_column(sb, col, '|');
781 chars_written++;
783 strbuf_addch(sb, ' ');
784 chars_written++;
787 graph_pad_horizontally(graph, sb, chars_written);
790 * Increment graph->expansion_row,
791 * and move to state GRAPH_COMMIT if necessary
793 graph->expansion_row++;
794 if (graph->expansion_row >= num_expansion_rows)
795 graph_update_state(graph, GRAPH_COMMIT);
798 static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
801 * For boundary commits, print 'o'
802 * (We should only see boundary commits when revs->boundary is set.)
804 if (graph->commit->object.flags & BOUNDARY) {
805 assert(graph->revs->boundary);
806 strbuf_addch(sb, 'o');
807 return;
811 * get_revision_mark() handles all other cases without assert()
813 strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit));
817 * Draw an octopus merge and return the number of characters written.
819 static int graph_draw_octopus_merge(struct git_graph *graph,
820 struct strbuf *sb)
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).
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], '-');
835 col_num = (i / 2) + dashless_commits;
836 strbuf_write_column(sb, &graph->new_columns[col_num], '.');
837 return num_dashes + 1;
840 static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
842 int seen_this = 0;
843 int i, chars_written;
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.)
852 seen_this = 0;
853 chars_written = 0;
854 for (i = 0; i <= graph->num_columns; i++) {
855 struct column *col = &graph->columns[i];
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;
865 if (col_commit == graph->commit) {
866 seen_this = 1;
867 graph_output_commit_char(graph, sb);
868 chars_written++;
870 if (graph->num_parents > 2)
871 chars_written += graph_draw_octopus_merge(graph,
872 sb);
873 } else if (seen_this && (graph->num_parents > 2)) {
874 strbuf_write_column(sb, col, '\\');
875 chars_written++;
876 } else if (seen_this && (graph->num_parents == 2)) {
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.
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.
890 if (graph->prev_state == GRAPH_POST_MERGE &&
891 graph->prev_commit_index < i)
892 strbuf_write_column(sb, col, '\\');
893 else
894 strbuf_write_column(sb, col, '|');
895 chars_written++;
896 } else {
897 strbuf_write_column(sb, col, '|');
898 chars_written++;
900 strbuf_addch(sb, ' ');
901 chars_written++;
904 graph_pad_horizontally(graph, sb, chars_written);
907 * Update graph->state
909 if (graph->num_parents > 1)
910 graph_update_state(graph, GRAPH_POST_MERGE);
911 else if (graph_is_mapping_correct(graph))
912 graph_update_state(graph, GRAPH_PADDING);
913 else
914 graph_update_state(graph, GRAPH_COLLAPSING);
917 static struct column *find_new_column_by_commit(struct git_graph *graph,
918 struct commit *commit)
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];
925 return NULL;
928 static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
930 int seen_this = 0;
931 int i, j, chars_written;
934 * Output the post-merge row
936 chars_written = 0;
937 for (i = 0; i <= graph->num_columns; i++) {
938 struct column *col = &graph->columns[i];
939 struct commit *col_commit;
940 if (i == graph->num_columns) {
941 if (seen_this)
942 break;
943 col_commit = graph->commit;
944 } else {
945 col_commit = col->commit;
948 if (col_commit == graph->commit) {
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.
955 struct commit_list *parents = NULL;
956 struct column *par_column;
957 seen_this = 1;
958 parents = first_interesting_parent(graph);
959 assert(parents);
960 par_column = find_new_column_by_commit(graph, parents->item);
961 assert(par_column);
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, ' ');
973 chars_written += j * 2;
974 } else if (seen_this) {
975 strbuf_write_column(sb, col, '\\');
976 strbuf_addch(sb, ' ');
977 chars_written += 2;
978 } else {
979 strbuf_write_column(sb, col, '|');
980 strbuf_addch(sb, ' ');
981 chars_written += 2;
985 graph_pad_horizontally(graph, sb, chars_written);
988 * Update graph->state
990 if (graph_is_mapping_correct(graph))
991 graph_update_state(graph, GRAPH_PADDING);
992 else
993 graph_update_state(graph, GRAPH_COLLAPSING);
996 static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
998 int i;
999 int *tmp_mapping;
1000 short used_horizontal = 0;
1001 int horizontal_edge = -1;
1002 int horizontal_edge_target = -1;
1005 * Clear out the new_mapping array
1007 for (i = 0; i < graph->mapping_size; i++)
1008 graph->new_mapping[i] = -1;
1010 for (i = 0; i < graph->mapping_size; i++) {
1011 int target = graph->mapping[i];
1012 if (target < 0)
1013 continue;
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.
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.
1025 assert(target * 2 <= i);
1027 if (target * 2 == i) {
1029 * This column is already in the
1030 * correct place
1032 assert(graph->new_mapping[i] == -1);
1033 graph->new_mapping[i] = target;
1034 } else if (graph->new_mapping[i - 1] < 0) {
1036 * Nothing is to the left.
1037 * Move to the left by one
1039 graph->new_mapping[i - 1] = target;
1041 * If there isn't already an edge moving horizontally
1042 * select this one.
1044 if (horizontal_edge == -1) {
1045 int j;
1046 horizontal_edge = i;
1047 horizontal_edge_target = target;
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.
1054 for (j = (target * 2)+3; j < (i - 2); j += 2)
1055 graph->new_mapping[j] = target;
1057 } else if (graph->new_mapping[i - 1] == target) {
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.
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.
1069 } else {
1071 * There is a branch line to our left,
1072 * but it isn't our target. We need to
1073 * cross over it.
1075 * The space just to the left of this
1076 * branch should always be empty.
1078 * The branch to the left of that space
1079 * should be our eventual target.
1081 assert(graph->new_mapping[i - 1] > target);
1082 assert(graph->new_mapping[i - 2] < 0);
1083 assert(graph->new_mapping[i - 3] == target);
1084 graph->new_mapping[i - 2] = target;
1086 * Mark this branch as the horizontal edge to
1087 * prevent any other edges from moving
1088 * horizontally.
1090 if (horizontal_edge == -1)
1091 horizontal_edge = i;
1096 * The new mapping may be 1 smaller than the old mapping
1098 if (graph->new_mapping[graph->mapping_size - 1] < 0)
1099 graph->mapping_size--;
1102 * Output out a line based on the new mapping info
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)
1109 strbuf_write_column(sb, &graph->new_columns[target], '|');
1110 else if (target == horizontal_edge_target &&
1111 i != horizontal_edge - 1) {
1113 * Set the mappings for all but the
1114 * first segment to -1 so that they
1115 * won't continue into the next line.
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;
1124 strbuf_write_column(sb, &graph->new_columns[target], '/');
1129 graph_pad_horizontally(graph, sb, graph->mapping_size);
1132 * Swap mapping and new_mapping
1134 tmp_mapping = graph->mapping;
1135 graph->mapping = graph->new_mapping;
1136 graph->new_mapping = tmp_mapping;
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.
1143 if (graph_is_mapping_correct(graph))
1144 graph_update_state(graph, GRAPH_PADDING);
1147 static int graph_next_line(struct git_graph *graph, struct strbuf *sb)
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;
1170 assert(0);
1171 return 0;
1174 static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
1176 int i, j;
1178 if (graph->state != GRAPH_COMMIT) {
1179 graph_next_line(graph, sb);
1180 return;
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.)
1190 for (i = 0; i < graph->num_columns; i++) {
1191 struct column *col = &graph->columns[i];
1192 struct commit *col_commit = col->commit;
1193 if (col_commit == graph->commit) {
1194 strbuf_write_column(sb, col, '|');
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, ' ');
1203 } else {
1204 strbuf_write_column(sb, col, '|');
1205 strbuf_addch(sb, ' ');
1209 graph_pad_horizontally(graph, sb, graph->num_columns);
1212 * Update graph->prev_state since we have output a padding line
1214 graph->prev_state = GRAPH_PADDING;
1217 int graph_is_commit_finished(struct git_graph const *graph)
1219 return (graph->state == GRAPH_PADDING);
1222 void graph_show_commit(struct git_graph *graph)
1224 struct strbuf msgbuf = STRBUF_INIT;
1225 int shown_commit_line = 0;
1227 if (!graph)
1228 return;
1230 while (!shown_commit_line && !graph_is_commit_finished(graph)) {
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);
1238 strbuf_release(&msgbuf);
1241 void graph_show_oneline(struct git_graph *graph)
1243 struct strbuf msgbuf = STRBUF_INIT;
1245 if (!graph)
1246 return;
1248 graph_next_line(graph, &msgbuf);
1249 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1250 strbuf_release(&msgbuf);
1253 void graph_show_padding(struct git_graph *graph)
1255 struct strbuf msgbuf = STRBUF_INIT;
1257 if (!graph)
1258 return;
1260 graph_padding_line(graph, &msgbuf);
1261 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1262 strbuf_release(&msgbuf);
1265 int graph_show_remainder(struct git_graph *graph)
1267 struct strbuf msgbuf = STRBUF_INIT;
1268 int shown = 0;
1270 if (!graph)
1271 return 0;
1273 if (graph_is_commit_finished(graph))
1274 return 0;
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;
1282 if (!graph_is_commit_finished(graph))
1283 putchar('\n');
1284 else
1285 break;
1287 strbuf_release(&msgbuf);
1289 return shown;
1293 static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)
1295 char *p;
1297 if (!graph) {
1298 fwrite(sb->buf, sizeof(char), sb->len, stdout);
1299 return;
1303 * Print the strbuf line by line,
1304 * and display the graph info before each line but the first.
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;
1316 fwrite(p, sizeof(char), len, stdout);
1317 if (next_p && *next_p != '\0')
1318 graph_show_oneline(graph);
1319 p = next_p;
1323 void graph_show_commit_msg(struct git_graph *graph,
1324 struct strbuf const *sb)
1326 int newline_terminated;
1328 if (!graph) {
1330 * If there's no graph, just print the message buffer.
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.
1336 fwrite(sb->buf, sizeof(char), sb->len, stdout);
1337 return;
1340 newline_terminated = (sb->len && sb->buf[sb->len - 1] == '\n');
1343 * Show the commit message
1345 graph_show_strbuf(graph, sb);
1348 * If there is more output needed for this commit, show it now
1350 if (!graph_is_commit_finished(graph)) {
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.
1356 if (!newline_terminated)
1357 putchar('\n');
1359 graph_show_remainder(graph);
1362 * If sb ends with a newline, our output should too.
1364 if (newline_terminated)
1365 putchar('\n');