graph.c

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