Merge branch 'jc/deref-tag'
[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         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 static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
673 {
674         /*
675          * Output an ellipsis to indicate that a portion
676          * of the graph is missing.
677          */
678         strbuf_addstr(sb, "...");
679         graph_pad_horizontally(graph, sb, 3);
680
681         if (graph->num_parents >= 3 &&
682             graph->commit_index < (graph->num_columns - 1))
683                 graph_update_state(graph, GRAPH_PRE_COMMIT);
684         else
685                 graph_update_state(graph, GRAPH_COMMIT);
686 }
687
688 static void graph_output_pre_commit_line(struct git_graph *graph,
689                                          struct strbuf *sb)
690 {
691         int num_expansion_rows;
692         int i, seen_this;
693         int chars_written;
694
695         /*
696          * This function formats a row that increases the space around a commit
697          * with multiple parents, to make room for it.  It should only be
698          * called when there are 3 or more parents.
699          *
700          * We need 2 extra rows for every parent over 2.
701          */
702         assert(graph->num_parents >= 3);
703         num_expansion_rows = (graph->num_parents - 2) * 2;
704
705         /*
706          * graph->expansion_row tracks the current expansion row we are on.
707          * It should be in the range [0, num_expansion_rows - 1]
708          */
709         assert(0 <= graph->expansion_row &&
710                graph->expansion_row < num_expansion_rows);
711
712         /*
713          * Output the row
714          */
715         seen_this = 0;
716         chars_written = 0;
717         for (i = 0; i < graph->num_columns; i++) {
718                 struct column *col = &graph->columns[i];
719                 if (col->commit == graph->commit) {
720                         seen_this = 1;
721                         strbuf_write_column(sb, col, '|');
722                         strbuf_addf(sb, "%*s", graph->expansion_row, "");
723                         chars_written += 1 + graph->expansion_row;
724                 } else if (seen_this && (graph->expansion_row == 0)) {
725                         /*
726                          * This is the first line of the pre-commit output.
727                          * If the previous commit was a merge commit and
728                          * ended in the GRAPH_POST_MERGE state, all branch
729                          * lines after graph->prev_commit_index were
730                          * printed as "\" on the previous line.  Continue
731                          * to print them as "\" on this line.  Otherwise,
732                          * print the branch lines as "|".
733                          */
734                         if (graph->prev_state == GRAPH_POST_MERGE &&
735                             graph->prev_commit_index < i)
736                                 strbuf_write_column(sb, col, '\\');
737                         else
738                                 strbuf_write_column(sb, col, '|');
739                         chars_written++;
740                 } else if (seen_this && (graph->expansion_row > 0)) {
741                         strbuf_write_column(sb, col, '\\');
742                         chars_written++;
743                 } else {
744                         strbuf_write_column(sb, col, '|');
745                         chars_written++;
746                 }
747                 strbuf_addch(sb, ' ');
748                 chars_written++;
749         }
750
751         graph_pad_horizontally(graph, sb, chars_written);
752
753         /*
754          * Increment graph->expansion_row,
755          * and move to state GRAPH_COMMIT if necessary
756          */
757         graph->expansion_row++;
758         if (graph->expansion_row >= num_expansion_rows)
759                 graph_update_state(graph, GRAPH_COMMIT);
760 }
761
762 static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
763 {
764         /*
765          * For boundary commits, print 'o'
766          * (We should only see boundary commits when revs->boundary is set.)
767          */
768         if (graph->commit->object.flags & BOUNDARY) {
769                 assert(graph->revs->boundary);
770                 strbuf_addch(sb, 'o');
771                 return;
772         }
773
774         /*
775          * get_revision_mark() handles all other cases without assert()
776          */
777         strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit));
778 }
779
780 /*
781  * Draw an octopus merge and return the number of characters written.
782  */
783 static int graph_draw_octopus_merge(struct git_graph *graph,
784                                     struct strbuf *sb)
785 {
786         /*
787          * Here dashless_commits represents the number of parents
788          * which don't need to have dashes (because their edges fit
789          * neatly under the commit).
790          */
791         const int dashless_commits = 2;
792         int col_num, i;
793         int num_dashes =
794                 ((graph->num_parents - dashless_commits) * 2) - 1;
795         for (i = 0; i < num_dashes; i++) {
796                 col_num = (i / 2) + dashless_commits + graph->commit_index;
797                 strbuf_write_column(sb, &graph->new_columns[col_num], '-');
798         }
799         col_num = (i / 2) + dashless_commits + graph->commit_index;
800         strbuf_write_column(sb, &graph->new_columns[col_num], '.');
801         return num_dashes + 1;
802 }
803
804 static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
805 {
806         int seen_this = 0;
807         int i, chars_written;
808
809         /*
810          * Output the row containing this commit
811          * Iterate up to and including graph->num_columns,
812          * since the current commit may not be in any of the existing
813          * columns.  (This happens when the current commit doesn't have any
814          * children that we have already processed.)
815          */
816         seen_this = 0;
817         chars_written = 0;
818         for (i = 0; i <= graph->num_columns; i++) {
819                 struct column *col = &graph->columns[i];
820                 struct commit *col_commit;
821                 if (i == graph->num_columns) {
822                         if (seen_this)
823                                 break;
824                         col_commit = graph->commit;
825                 } else {
826                         col_commit = graph->columns[i].commit;
827                 }
828
829                 if (col_commit == graph->commit) {
830                         seen_this = 1;
831                         graph_output_commit_char(graph, sb);
832                         chars_written++;
833
834                         if (graph->num_parents > 2)
835                                 chars_written += graph_draw_octopus_merge(graph,
836                                                                           sb);
837                 } else if (seen_this && (graph->num_parents > 2)) {
838                         strbuf_write_column(sb, col, '\\');
839                         chars_written++;
840                 } else if (seen_this && (graph->num_parents == 2)) {
841                         /*
842                          * This is a 2-way merge commit.
843                          * There is no GRAPH_PRE_COMMIT stage for 2-way
844                          * merges, so this is the first line of output
845                          * for this commit.  Check to see what the previous
846                          * line of output was.
847                          *
848                          * If it was GRAPH_POST_MERGE, the branch line
849                          * coming into this commit may have been '\',
850                          * and not '|' or '/'.  If so, output the branch
851                          * line as '\' on this line, instead of '|'.  This
852                          * makes the output look nicer.
853                          */
854                         if (graph->prev_state == GRAPH_POST_MERGE &&
855                             graph->prev_commit_index < i)
856                                 strbuf_write_column(sb, col, '\\');
857                         else
858                                 strbuf_write_column(sb, col, '|');
859                         chars_written++;
860                 } else {
861                         strbuf_write_column(sb, col, '|');
862                         chars_written++;
863                 }
864                 strbuf_addch(sb, ' ');
865                 chars_written++;
866         }
867
868         graph_pad_horizontally(graph, sb, chars_written);
869
870         /*
871          * Update graph->state
872          */
873         if (graph->num_parents > 1)
874                 graph_update_state(graph, GRAPH_POST_MERGE);
875         else if (graph_is_mapping_correct(graph))
876                 graph_update_state(graph, GRAPH_PADDING);
877         else
878                 graph_update_state(graph, GRAPH_COLLAPSING);
879 }
880
881 static struct column *find_new_column_by_commit(struct git_graph *graph,
882                                                 struct commit *commit)
883 {
884         int i;
885         for (i = 0; i < graph->num_new_columns; i++) {
886                 if (graph->new_columns[i].commit == commit)
887                         return &graph->new_columns[i];
888         }
889         return NULL;
890 }
891
892 static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
893 {
894         int seen_this = 0;
895         int i, j, chars_written;
896
897         /*
898          * Output the post-merge row
899          */
900         chars_written = 0;
901         for (i = 0; i <= graph->num_columns; i++) {
902                 struct column *col = &graph->columns[i];
903                 struct commit *col_commit;
904                 if (i == graph->num_columns) {
905                         if (seen_this)
906                                 break;
907                         col_commit = graph->commit;
908                 } else {
909                         col_commit = col->commit;
910                 }
911
912                 if (col_commit == graph->commit) {
913                         /*
914                          * Since the current commit is a merge find
915                          * the columns for the parent commits in
916                          * new_columns and use those to format the
917                          * edges.
918                          */
919                         struct commit_list *parents = NULL;
920                         struct column *par_column;
921                         seen_this = 1;
922                         parents = first_interesting_parent(graph);
923                         assert(parents);
924                         par_column = find_new_column_by_commit(graph, parents->item);
925                         assert(par_column);
926
927                         strbuf_write_column(sb, par_column, '|');
928                         chars_written++;
929                         for (j = 0; j < graph->num_parents - 1; j++) {
930                                 parents = next_interesting_parent(graph, parents);
931                                 assert(parents);
932                                 par_column = find_new_column_by_commit(graph, parents->item);
933                                 assert(par_column);
934                                 strbuf_write_column(sb, par_column, '\\');
935                                 strbuf_addch(sb, ' ');
936                         }
937                         chars_written += j * 2;
938                 } else if (seen_this) {
939                         strbuf_write_column(sb, col, '\\');
940                         strbuf_addch(sb, ' ');
941                         chars_written += 2;
942                 } else {
943                         strbuf_write_column(sb, col, '|');
944                         strbuf_addch(sb, ' ');
945                         chars_written += 2;
946                 }
947         }
948
949         graph_pad_horizontally(graph, sb, chars_written);
950
951         /*
952          * Update graph->state
953          */
954         if (graph_is_mapping_correct(graph))
955                 graph_update_state(graph, GRAPH_PADDING);
956         else
957                 graph_update_state(graph, GRAPH_COLLAPSING);
958 }
959
960 static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
961 {
962         int i;
963         int *tmp_mapping;
964         short used_horizontal = 0;
965         int horizontal_edge = -1;
966         int horizontal_edge_target = -1;
967
968         /*
969          * Clear out the new_mapping array
970          */
971         for (i = 0; i < graph->mapping_size; i++)
972                 graph->new_mapping[i] = -1;
973
974         for (i = 0; i < graph->mapping_size; i++) {
975                 int target = graph->mapping[i];
976                 if (target < 0)
977                         continue;
978
979                 /*
980                  * Since update_columns() always inserts the leftmost
981                  * column first, each branch's target location should
982                  * always be either its current location or to the left of
983                  * its current location.
984                  *
985                  * We never have to move branches to the right.  This makes
986                  * the graph much more legible, since whenever branches
987                  * cross, only one is moving directions.
988                  */
989                 assert(target * 2 <= i);
990
991                 if (target * 2 == i) {
992                         /*
993                          * This column is already in the
994                          * correct place
995                          */
996                         assert(graph->new_mapping[i] == -1);
997                         graph->new_mapping[i] = target;
998                 } else if (graph->new_mapping[i - 1] < 0) {
999                         /*
1000                          * Nothing is to the left.
1001                          * Move to the left by one
1002                          */
1003                         graph->new_mapping[i - 1] = target;
1004                         /*
1005                          * If there isn't already an edge moving horizontally
1006                          * select this one.
1007                          */
1008                         if (horizontal_edge == -1) {
1009                                 int j;
1010                                 horizontal_edge = i;
1011                                 horizontal_edge_target = target;
1012                                 /*
1013                                  * The variable target is the index of the graph
1014                                  * column, and therefore target*2+3 is the
1015                                  * actual screen column of the first horizontal
1016                                  * line.
1017                                  */
1018                                 for (j = (target * 2)+3; j < (i - 2); j += 2)
1019                                         graph->new_mapping[j] = target;
1020                         }
1021                 } else if (graph->new_mapping[i - 1] == target) {
1022                         /*
1023                          * There is a branch line to our left
1024                          * already, and it is our target.  We
1025                          * combine with this line, since we share
1026                          * the same parent commit.
1027                          *
1028                          * We don't have to add anything to the
1029                          * output or new_mapping, since the
1030                          * existing branch line has already taken
1031                          * care of it.
1032                          */
1033                 } else {
1034                         /*
1035                          * There is a branch line to our left,
1036                          * but it isn't our target.  We need to
1037                          * cross over it.
1038                          *
1039                          * The space just to the left of this
1040                          * branch should always be empty.
1041                          *
1042                          * The branch to the left of that space
1043                          * should be our eventual target.
1044                          */
1045                         assert(graph->new_mapping[i - 1] > target);
1046                         assert(graph->new_mapping[i - 2] < 0);
1047                         assert(graph->new_mapping[i - 3] == target);
1048                         graph->new_mapping[i - 2] = target;
1049                         /*
1050                          * Mark this branch as the horizontal edge to
1051                          * prevent any other edges from moving
1052                          * horizontally.
1053                          */
1054                         if (horizontal_edge == -1)
1055                                 horizontal_edge = i;
1056                 }
1057         }
1058
1059         /*
1060          * The new mapping may be 1 smaller than the old mapping
1061          */
1062         if (graph->new_mapping[graph->mapping_size - 1] < 0)
1063                 graph->mapping_size--;
1064
1065         /*
1066          * Output out a line based on the new mapping info
1067          */
1068         for (i = 0; i < graph->mapping_size; i++) {
1069                 int target = graph->new_mapping[i];
1070                 if (target < 0)
1071                         strbuf_addch(sb, ' ');
1072                 else if (target * 2 == i)
1073                         strbuf_write_column(sb, &graph->new_columns[target], '|');
1074                 else if (target == horizontal_edge_target &&
1075                          i != horizontal_edge - 1) {
1076                                 /*
1077                                  * Set the mappings for all but the
1078                                  * first segment to -1 so that they
1079                                  * won't continue into the next line.
1080                                  */
1081                                 if (i != (target * 2)+3)
1082                                         graph->new_mapping[i] = -1;
1083                                 used_horizontal = 1;
1084                         strbuf_write_column(sb, &graph->new_columns[target], '_');
1085                 } else {
1086                         if (used_horizontal && i < horizontal_edge)
1087                                 graph->new_mapping[i] = -1;
1088                         strbuf_write_column(sb, &graph->new_columns[target], '/');
1089
1090                 }
1091         }
1092
1093         graph_pad_horizontally(graph, sb, graph->mapping_size);
1094
1095         /*
1096          * Swap mapping and new_mapping
1097          */
1098         tmp_mapping = graph->mapping;
1099         graph->mapping = graph->new_mapping;
1100         graph->new_mapping = tmp_mapping;
1101
1102         /*
1103          * If graph->mapping indicates that all of the branch lines
1104          * are already in the correct positions, we are done.
1105          * Otherwise, we need to collapse some branch lines together.
1106          */
1107         if (graph_is_mapping_correct(graph))
1108                 graph_update_state(graph, GRAPH_PADDING);
1109 }
1110
1111 int graph_next_line(struct git_graph *graph, struct strbuf *sb)
1112 {
1113         switch (graph->state) {
1114         case GRAPH_PADDING:
1115                 graph_output_padding_line(graph, sb);
1116                 return 0;
1117         case GRAPH_SKIP:
1118                 graph_output_skip_line(graph, sb);
1119                 return 0;
1120         case GRAPH_PRE_COMMIT:
1121                 graph_output_pre_commit_line(graph, sb);
1122                 return 0;
1123         case GRAPH_COMMIT:
1124                 graph_output_commit_line(graph, sb);
1125                 return 1;
1126         case GRAPH_POST_MERGE:
1127                 graph_output_post_merge_line(graph, sb);
1128                 return 0;
1129         case GRAPH_COLLAPSING:
1130                 graph_output_collapsing_line(graph, sb);
1131                 return 0;
1132         }
1133
1134         assert(0);
1135         return 0;
1136 }
1137
1138 static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
1139 {
1140         int i;
1141
1142         if (graph->state != GRAPH_COMMIT) {
1143                 graph_next_line(graph, sb);
1144                 return;
1145         }
1146
1147         /*
1148          * Output the row containing this commit
1149          * Iterate up to and including graph->num_columns,
1150          * since the current commit may not be in any of the existing
1151          * columns.  (This happens when the current commit doesn't have any
1152          * children that we have already processed.)
1153          */
1154         for (i = 0; i < graph->num_columns; i++) {
1155                 struct column *col = &graph->columns[i];
1156                 strbuf_write_column(sb, col, '|');
1157                 if (col->commit == graph->commit && graph->num_parents > 2)
1158                         strbuf_addchars(sb, ' ', (graph->num_parents - 2) * 2);
1159                 else
1160                         strbuf_addch(sb, ' ');
1161         }
1162
1163         graph_pad_horizontally(graph, sb, graph->num_columns);
1164
1165         /*
1166          * Update graph->prev_state since we have output a padding line
1167          */
1168         graph->prev_state = GRAPH_PADDING;
1169 }
1170
1171 int graph_is_commit_finished(struct git_graph const *graph)
1172 {
1173         return (graph->state == GRAPH_PADDING);
1174 }
1175
1176 void graph_show_commit(struct git_graph *graph)
1177 {
1178         struct strbuf msgbuf = STRBUF_INIT;
1179         int shown_commit_line = 0;
1180
1181         if (!graph)
1182                 return;
1183
1184         /*
1185          * When showing a diff of a merge against each of its parents, we
1186          * are called once for each parent without graph_update having been
1187          * called.  In this case, simply output a single padding line.
1188          */
1189         if (graph_is_commit_finished(graph)) {
1190                 graph_show_padding(graph);
1191                 shown_commit_line = 1;
1192         }
1193
1194         while (!shown_commit_line && !graph_is_commit_finished(graph)) {
1195                 shown_commit_line = graph_next_line(graph, &msgbuf);
1196                 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1197                 if (!shown_commit_line)
1198                         putchar('\n');
1199                 strbuf_setlen(&msgbuf, 0);
1200         }
1201
1202         strbuf_release(&msgbuf);
1203 }
1204
1205 void graph_show_oneline(struct git_graph *graph)
1206 {
1207         struct strbuf msgbuf = STRBUF_INIT;
1208
1209         if (!graph)
1210                 return;
1211
1212         graph_next_line(graph, &msgbuf);
1213         fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1214         strbuf_release(&msgbuf);
1215 }
1216
1217 void graph_show_padding(struct git_graph *graph)
1218 {
1219         struct strbuf msgbuf = STRBUF_INIT;
1220
1221         if (!graph)
1222                 return;
1223
1224         graph_padding_line(graph, &msgbuf);
1225         fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1226         strbuf_release(&msgbuf);
1227 }
1228
1229 int graph_show_remainder(struct git_graph *graph)
1230 {
1231         struct strbuf msgbuf = STRBUF_INIT;
1232         int shown = 0;
1233
1234         if (!graph)
1235                 return 0;
1236
1237         if (graph_is_commit_finished(graph))
1238                 return 0;
1239
1240         for (;;) {
1241                 graph_next_line(graph, &msgbuf);
1242                 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1243                 strbuf_setlen(&msgbuf, 0);
1244                 shown = 1;
1245
1246                 if (!graph_is_commit_finished(graph))
1247                         putchar('\n');
1248                 else
1249                         break;
1250         }
1251         strbuf_release(&msgbuf);
1252
1253         return shown;
1254 }
1255
1256
1257 static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)
1258 {
1259         char *p;
1260
1261         if (!graph) {
1262                 fwrite(sb->buf, sizeof(char), sb->len, stdout);
1263                 return;
1264         }
1265
1266         /*
1267          * Print the strbuf line by line,
1268          * and display the graph info before each line but the first.
1269          */
1270         p = sb->buf;
1271         while (p) {
1272                 size_t len;
1273                 char *next_p = strchr(p, '\n');
1274                 if (next_p) {
1275                         next_p++;
1276                         len = next_p - p;
1277                 } else {
1278                         len = (sb->buf + sb->len) - p;
1279                 }
1280                 fwrite(p, sizeof(char), len, stdout);
1281                 if (next_p && *next_p != '\0')
1282                         graph_show_oneline(graph);
1283                 p = next_p;
1284         }
1285 }
1286
1287 void graph_show_commit_msg(struct git_graph *graph,
1288                            struct strbuf const *sb)
1289 {
1290         int newline_terminated;
1291
1292         if (!graph) {
1293                 /*
1294                  * If there's no graph, just print the message buffer.
1295                  *
1296                  * The message buffer for CMIT_FMT_ONELINE and
1297                  * CMIT_FMT_USERFORMAT are already missing a terminating
1298                  * newline.  All of the other formats should have it.
1299                  */
1300                 fwrite(sb->buf, sizeof(char), sb->len, stdout);
1301                 return;
1302         }
1303
1304         newline_terminated = (sb->len && sb->buf[sb->len - 1] == '\n');
1305
1306         /*
1307          * Show the commit message
1308          */
1309         graph_show_strbuf(graph, sb);
1310
1311         /*
1312          * If there is more output needed for this commit, show it now
1313          */
1314         if (!graph_is_commit_finished(graph)) {
1315                 /*
1316                  * If sb doesn't have a terminating newline, print one now,
1317                  * so we can start the remainder of the graph output on a
1318                  * new line.
1319                  */
1320                 if (!newline_terminated)
1321                         putchar('\n');
1322
1323                 graph_show_remainder(graph);
1324
1325                 /*
1326                  * If sb ends with a newline, our output should too.
1327                  */
1328                 if (newline_terminated)
1329                         putchar('\n');
1330         }
1331 }