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