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