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