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