graph.c

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