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