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