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