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