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