git.oblomov.eu Git - git/blob - graph.c

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