magic pathspec: add tentative ":/path/from/top/level" pathspec support
[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          * If revs->left_right is set, print '<' for commits that
802          * come from the left side, and '>' for commits from the right
803          * side.
804          */
805         if (graph->revs && graph->revs->left_right) {
806                 if (graph->commit->object.flags & SYMMETRIC_LEFT)
807                         strbuf_addch(sb, '<');
808                 else
809                         strbuf_addch(sb, '>');
810                 return;
811         }
812
813         /*
814          * Print '*' in all other cases
815          */
816         strbuf_addch(sb, '*');
817 }
818
819 /*
820  * Draw an octopus merge and return the number of characters written.
821  */
822 static int graph_draw_octopus_merge(struct git_graph *graph,
823                                     struct strbuf *sb)
824 {
825         /*
826          * Here dashless_commits represents the number of parents
827          * which don't need to have dashes (because their edges fit
828          * neatly under the commit).
829          */
830         const int dashless_commits = 2;
831         int col_num, i;
832         int num_dashes =
833                 ((graph->num_parents - dashless_commits) * 2) - 1;
834         for (i = 0; i < num_dashes; i++) {
835                 col_num = (i / 2) + dashless_commits;
836                 strbuf_write_column(sb, &graph->new_columns[col_num], '-');
837         }
838         col_num = (i / 2) + dashless_commits;
839         strbuf_write_column(sb, &graph->new_columns[col_num], '.');
840         return num_dashes + 1;
841 }
842
843 static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
844 {
845         int seen_this = 0;
846         int i, chars_written;
847
848         /*
849          * Output the row containing this commit
850          * Iterate up to and including graph->num_columns,
851          * since the current commit may not be in any of the existing
852          * columns.  (This happens when the current commit doesn't have any
853          * children that we have already processed.)
854          */
855         seen_this = 0;
856         chars_written = 0;
857         for (i = 0; i <= graph->num_columns; i++) {
858                 struct column *col = &graph->columns[i];
859                 struct commit *col_commit;
860                 if (i == graph->num_columns) {
861                         if (seen_this)
862                                 break;
863                         col_commit = graph->commit;
864                 } else {
865                         col_commit = graph->columns[i].commit;
866                 }
867
868                 if (col_commit == graph->commit) {
869                         seen_this = 1;
870                         graph_output_commit_char(graph, sb);
871                         chars_written++;
872
873                         if (graph->num_parents > 2)
874                                 chars_written += graph_draw_octopus_merge(graph,
875                                                                           sb);
876                 } else if (seen_this && (graph->num_parents > 2)) {
877                         strbuf_write_column(sb, col, '\\');
878                         chars_written++;
879                 } else if (seen_this && (graph->num_parents == 2)) {
880                         /*
881                          * This is a 2-way merge commit.
882                          * There is no GRAPH_PRE_COMMIT stage for 2-way
883                          * merges, so this is the first line of output
884                          * for this commit.  Check to see what the previous
885                          * line of output was.
886                          *
887                          * If it was GRAPH_POST_MERGE, the branch line
888                          * coming into this commit may have been '\',
889                          * and not '|' or '/'.  If so, output the branch
890                          * line as '\' on this line, instead of '|'.  This
891                          * makes the output look nicer.
892                          */
893                         if (graph->prev_state == GRAPH_POST_MERGE &&
894                             graph->prev_commit_index < i)
895                                 strbuf_write_column(sb, col, '\\');
896                         else
897                                 strbuf_write_column(sb, col, '|');
898                         chars_written++;
899                 } else {
900                         strbuf_write_column(sb, col, '|');
901                         chars_written++;
902                 }
903                 strbuf_addch(sb, ' ');
904                 chars_written++;
905         }
906
907         graph_pad_horizontally(graph, sb, chars_written);
908
909         /*
910          * Update graph->state
911          */
912         if (graph->num_parents > 1)
913                 graph_update_state(graph, GRAPH_POST_MERGE);
914         else if (graph_is_mapping_correct(graph))
915                 graph_update_state(graph, GRAPH_PADDING);
916         else
917                 graph_update_state(graph, GRAPH_COLLAPSING);
918 }
919
920 static struct column *find_new_column_by_commit(struct git_graph *graph,
921                                                 struct commit *commit)
922 {
923         int i;
924         for (i = 0; i < graph->num_new_columns; i++) {
925                 if (graph->new_columns[i].commit == commit)
926                         return &graph->new_columns[i];
927         }
928         return NULL;
929 }
930
931 static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
932 {
933         int seen_this = 0;
934         int i, j, chars_written;
935
936         /*
937          * Output the post-merge row
938          */
939         chars_written = 0;
940         for (i = 0; i <= graph->num_columns; i++) {
941                 struct column *col = &graph->columns[i];
942                 struct commit *col_commit;
943                 if (i == graph->num_columns) {
944                         if (seen_this)
945                                 break;
946                         col_commit = graph->commit;
947                 } else {
948                         col_commit = col->commit;
949                 }
950
951                 if (col_commit == graph->commit) {
952                         /*
953                          * Since the current commit is a merge find
954                          * the columns for the parent commits in
955                          * new_columns and use those to format the
956                          * edges.
957                          */
958                         struct commit_list *parents = NULL;
959                         struct column *par_column;
960                         seen_this = 1;
961                         parents = first_interesting_parent(graph);
962                         assert(parents);
963                         par_column = find_new_column_by_commit(graph, parents->item);
964                         assert(par_column);
965
966                         strbuf_write_column(sb, par_column, '|');
967                         chars_written++;
968                         for (j = 0; j < graph->num_parents - 1; j++) {
969                                 parents = next_interesting_parent(graph, parents);
970                                 assert(parents);
971                                 par_column = find_new_column_by_commit(graph, parents->item);
972                                 assert(par_column);
973                                 strbuf_write_column(sb, par_column, '\\');
974                                 strbuf_addch(sb, ' ');
975                         }
976                         chars_written += j * 2;
977                 } else if (seen_this) {
978                         strbuf_write_column(sb, col, '\\');
979                         strbuf_addch(sb, ' ');
980                         chars_written += 2;
981                 } else {
982                         strbuf_write_column(sb, col, '|');
983                         strbuf_addch(sb, ' ');
984                         chars_written += 2;
985                 }
986         }
987
988         graph_pad_horizontally(graph, sb, chars_written);
989
990         /*
991          * Update graph->state
992          */
993         if (graph_is_mapping_correct(graph))
994                 graph_update_state(graph, GRAPH_PADDING);
995         else
996                 graph_update_state(graph, GRAPH_COLLAPSING);
997 }
998
999 static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
1000 {
1001         int i;
1002         int *tmp_mapping;
1003         short used_horizontal = 0;
1004         int horizontal_edge = -1;
1005         int horizontal_edge_target = -1;
1006
1007         /*
1008          * Clear out the new_mapping array
1009          */
1010         for (i = 0; i < graph->mapping_size; i++)
1011                 graph->new_mapping[i] = -1;
1012
1013         for (i = 0; i < graph->mapping_size; i++) {
1014                 int target = graph->mapping[i];
1015                 if (target < 0)
1016                         continue;
1017
1018                 /*
1019                  * Since update_columns() always inserts the leftmost
1020                  * column first, each branch's target location should
1021                  * always be either its current location or to the left of
1022                  * its current location.
1023                  *
1024                  * We never have to move branches to the right.  This makes
1025                  * the graph much more legible, since whenever branches
1026                  * cross, only one is moving directions.
1027                  */
1028                 assert(target * 2 <= i);
1029
1030                 if (target * 2 == i) {
1031                         /*
1032                          * This column is already in the
1033                          * correct place
1034                          */
1035                         assert(graph->new_mapping[i] == -1);
1036                         graph->new_mapping[i] = target;
1037                 } else if (graph->new_mapping[i - 1] < 0) {
1038                         /*
1039                          * Nothing is to the left.
1040                          * Move to the left by one
1041                          */
1042                         graph->new_mapping[i - 1] = target;
1043                         /*
1044                          * If there isn't already an edge moving horizontally
1045                          * select this one.
1046                          */
1047                         if (horizontal_edge == -1) {
1048                                 int j;
1049                                 horizontal_edge = i;
1050                                 horizontal_edge_target = target;
1051                                 /*
1052                                  * The variable target is the index of the graph
1053                                  * column, and therefore target*2+3 is the
1054                                  * actual screen column of the first horizontal
1055                                  * line.
1056                                  */
1057                                 for (j = (target * 2)+3; j < (i - 2); j += 2)
1058                                         graph->new_mapping[j] = target;
1059                         }
1060                 } else if (graph->new_mapping[i - 1] == target) {
1061                         /*
1062                          * There is a branch line to our left
1063                          * already, and it is our target.  We
1064                          * combine with this line, since we share
1065                          * the same parent commit.
1066                          *
1067                          * We don't have to add anything to the
1068                          * output or new_mapping, since the
1069                          * existing branch line has already taken
1070                          * care of it.
1071                          */
1072                 } else {
1073                         /*
1074                          * There is a branch line to our left,
1075                          * but it isn't our target.  We need to
1076                          * cross over it.
1077                          *
1078                          * The space just to the left of this
1079                          * branch should always be empty.
1080                          *
1081                          * The branch to the left of that space
1082                          * should be our eventual target.
1083                          */
1084                         assert(graph->new_mapping[i - 1] > target);
1085                         assert(graph->new_mapping[i - 2] < 0);
1086                         assert(graph->new_mapping[i - 3] == target);
1087                         graph->new_mapping[i - 2] = target;
1088                         /*
1089                          * Mark this branch as the horizontal edge to
1090                          * prevent any other edges from moving
1091                          * horizontally.
1092                          */
1093                         if (horizontal_edge == -1)
1094                                 horizontal_edge = i;
1095                 }
1096         }
1097
1098         /*
1099          * The new mapping may be 1 smaller than the old mapping
1100          */
1101         if (graph->new_mapping[graph->mapping_size - 1] < 0)
1102                 graph->mapping_size--;
1103
1104         /*
1105          * Output out a line based on the new mapping info
1106          */
1107         for (i = 0; i < graph->mapping_size; i++) {
1108                 int target = graph->new_mapping[i];
1109                 if (target < 0)
1110                         strbuf_addch(sb, ' ');
1111                 else if (target * 2 == i)
1112                         strbuf_write_column(sb, &graph->new_columns[target], '|');
1113                 else if (target == horizontal_edge_target &&
1114                          i != horizontal_edge - 1) {
1115                                 /*
1116                                  * Set the mappings for all but the
1117                                  * first segment to -1 so that they
1118                                  * won't continue into the next line.
1119                                  */
1120                                 if (i != (target * 2)+3)
1121                                         graph->new_mapping[i] = -1;
1122                                 used_horizontal = 1;
1123                         strbuf_write_column(sb, &graph->new_columns[target], '_');
1124                 } else {
1125                         if (used_horizontal && i < horizontal_edge)
1126                                 graph->new_mapping[i] = -1;
1127                         strbuf_write_column(sb, &graph->new_columns[target], '/');
1128
1129                 }
1130         }
1131
1132         graph_pad_horizontally(graph, sb, graph->mapping_size);
1133
1134         /*
1135          * Swap mapping and new_mapping
1136          */
1137         tmp_mapping = graph->mapping;
1138         graph->mapping = graph->new_mapping;
1139         graph->new_mapping = tmp_mapping;
1140
1141         /*
1142          * If graph->mapping indicates that all of the branch lines
1143          * are already in the correct positions, we are done.
1144          * Otherwise, we need to collapse some branch lines together.
1145          */
1146         if (graph_is_mapping_correct(graph))
1147                 graph_update_state(graph, GRAPH_PADDING);
1148 }
1149
1150 int graph_next_line(struct git_graph *graph, struct strbuf *sb)
1151 {
1152         switch (graph->state) {
1153         case GRAPH_PADDING:
1154                 graph_output_padding_line(graph, sb);
1155                 return 0;
1156         case GRAPH_SKIP:
1157                 graph_output_skip_line(graph, sb);
1158                 return 0;
1159         case GRAPH_PRE_COMMIT:
1160                 graph_output_pre_commit_line(graph, sb);
1161                 return 0;
1162         case GRAPH_COMMIT:
1163                 graph_output_commit_line(graph, sb);
1164                 return 1;
1165         case GRAPH_POST_MERGE:
1166                 graph_output_post_merge_line(graph, sb);
1167                 return 0;
1168         case GRAPH_COLLAPSING:
1169                 graph_output_collapsing_line(graph, sb);
1170                 return 0;
1171         }
1172
1173         assert(0);
1174         return 0;
1175 }
1176
1177 static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
1178 {
1179         int i, j;
1180
1181         if (graph->state != GRAPH_COMMIT) {
1182                 graph_next_line(graph, sb);
1183                 return;
1184         }
1185
1186         /*
1187          * Output the row containing this commit
1188          * Iterate up to and including graph->num_columns,
1189          * since the current commit may not be in any of the existing
1190          * columns.  (This happens when the current commit doesn't have any
1191          * children that we have already processed.)
1192          */
1193         for (i = 0; i < graph->num_columns; i++) {
1194                 struct column *col = &graph->columns[i];
1195                 struct commit *col_commit = col->commit;
1196                 if (col_commit == graph->commit) {
1197                         strbuf_write_column(sb, col, '|');
1198
1199                         if (graph->num_parents < 3)
1200                                 strbuf_addch(sb, ' ');
1201                         else {
1202                                 int num_spaces = ((graph->num_parents - 2) * 2);
1203                                 for (j = 0; j < num_spaces; j++)
1204                                         strbuf_addch(sb, ' ');
1205                         }
1206                 } else {
1207                         strbuf_write_column(sb, col, '|');
1208                         strbuf_addch(sb, ' ');
1209                 }
1210         }
1211
1212         graph_pad_horizontally(graph, sb, graph->num_columns);
1213
1214         /*
1215          * Update graph->prev_state since we have output a padding line
1216          */
1217         graph->prev_state = GRAPH_PADDING;
1218 }
1219
1220 int graph_is_commit_finished(struct git_graph const *graph)
1221 {
1222         return (graph->state == GRAPH_PADDING);
1223 }
1224
1225 void graph_show_commit(struct git_graph *graph)
1226 {
1227         struct strbuf msgbuf = STRBUF_INIT;
1228         int shown_commit_line = 0;
1229
1230         if (!graph)
1231                 return;
1232
1233         while (!shown_commit_line) {
1234                 shown_commit_line = graph_next_line(graph, &msgbuf);
1235                 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1236                 if (!shown_commit_line)
1237                         putchar('\n');
1238                 strbuf_setlen(&msgbuf, 0);
1239         }
1240
1241         strbuf_release(&msgbuf);
1242 }
1243
1244 void graph_show_oneline(struct git_graph *graph)
1245 {
1246         struct strbuf msgbuf = STRBUF_INIT;
1247
1248         if (!graph)
1249                 return;
1250
1251         graph_next_line(graph, &msgbuf);
1252         fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1253         strbuf_release(&msgbuf);
1254 }
1255
1256 void graph_show_padding(struct git_graph *graph)
1257 {
1258         struct strbuf msgbuf = STRBUF_INIT;
1259
1260         if (!graph)
1261                 return;
1262
1263         graph_padding_line(graph, &msgbuf);
1264         fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1265         strbuf_release(&msgbuf);
1266 }
1267
1268 int graph_show_remainder(struct git_graph *graph)
1269 {
1270         struct strbuf msgbuf = STRBUF_INIT;
1271         int shown = 0;
1272
1273         if (!graph)
1274                 return 0;
1275
1276         if (graph_is_commit_finished(graph))
1277                 return 0;
1278
1279         for (;;) {
1280                 graph_next_line(graph, &msgbuf);
1281                 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1282                 strbuf_setlen(&msgbuf, 0);
1283                 shown = 1;
1284
1285                 if (!graph_is_commit_finished(graph))
1286                         putchar('\n');
1287                 else
1288                         break;
1289         }
1290         strbuf_release(&msgbuf);
1291
1292         return shown;
1293 }
1294
1295
1296 static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)
1297 {
1298         char *p;
1299
1300         if (!graph) {
1301                 fwrite(sb->buf, sizeof(char), sb->len, stdout);
1302                 return;
1303         }
1304
1305         /*
1306          * Print the strbuf line by line,
1307          * and display the graph info before each line but the first.
1308          */
1309         p = sb->buf;
1310         while (p) {
1311                 size_t len;
1312                 char *next_p = strchr(p, '\n');
1313                 if (next_p) {
1314                         next_p++;
1315                         len = next_p - p;
1316                 } else {
1317                         len = (sb->buf + sb->len) - p;
1318                 }
1319                 fwrite(p, sizeof(char), len, stdout);
1320                 if (next_p && *next_p != '\0')
1321                         graph_show_oneline(graph);
1322                 p = next_p;
1323         }
1324 }
1325
1326 void graph_show_commit_msg(struct git_graph *graph,
1327                            struct strbuf const *sb)
1328 {
1329         int newline_terminated;
1330
1331         if (!graph) {
1332                 /*
1333                  * If there's no graph, just print the message buffer.
1334                  *
1335                  * The message buffer for CMIT_FMT_ONELINE and
1336                  * CMIT_FMT_USERFORMAT are already missing a terminating
1337                  * newline.  All of the other formats should have it.
1338                  */
1339                 fwrite(sb->buf, sizeof(char), sb->len, stdout);
1340                 return;
1341         }
1342
1343         newline_terminated = (sb->len && sb->buf[sb->len - 1] == '\n');
1344
1345         /*
1346          * Show the commit message
1347          */
1348         graph_show_strbuf(graph, sb);
1349
1350         /*
1351          * If there is more output needed for this commit, show it now
1352          */
1353         if (!graph_is_commit_finished(graph)) {
1354                 /*
1355                  * If sb doesn't have a terminating newline, print one now,
1356                  * so we can start the remainder of the graph output on a
1357                  * new line.
1358                  */
1359                 if (!newline_terminated)
1360                         putchar('\n');
1361
1362                 graph_show_remainder(graph);
1363
1364                 /*
1365                  * If sb ends with a newline, our output should too.
1366                  */
1367                 if (newline_terminated)
1368                         putchar('\n');
1369         }
1370 }