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                 return;
 194
 195         /*
 196          * If the commit is already in the new_columns list, we don't need to
 197          * add it.  Just update the mapping correctly.
 198          */
 199         for (i = 0; i < graph->num_new_columns; i++) {
 200                 if (graph->new_columns[i].commit == commit) {
 201                         graph->mapping[*mapping_index] = i;
 202                         *mapping_index += 2;
 203                         return;
 204                 }
 205         }
 206
 207         /*
 208          * This commit isn't already in new_columns.  Add it.
 209          */
 210         graph->new_columns[graph->num_new_columns].commit = commit;
 211         graph->mapping[*mapping_index] = graph->num_new_columns;
 212         *mapping_index += 2;
 213         graph->num_new_columns++;
 214 }
 215
 216 static void graph_update_width(struct git_graph *graph,
 217                                int is_commit_in_existing_columns)
 218 {
 219         /*
 220          * Compute the width needed to display the graph for this commit.
 221          * This is the maximum width needed for any row.  All other rows
 222          * will be padded to this width.
 223          *
 224          * Compute the number of columns in the widest row:
 225          * Count each existing column (graph->num_columns), and each new
 226          * column added by this commit.
 227          */
 228         int max_cols = graph->num_columns + graph->num_parents;
 229
 230         /*
 231          * Even if the current commit has no parents, it still takes up a
 232          * column for itself.
 233          */
 234         if (graph->num_parents < 1)
 235                 max_cols++;
 236
 237         /*
 238          * We added a column for the the current commit as part of
 239          * graph->num_parents.  If the current commit was already in
 240          * graph->columns, then we have double counted it.
 241          */
 242         if (is_commit_in_existing_columns)
 243                 max_cols--;
 244
 245         /*
 246          * Each column takes up 2 spaces
 247          */
 248         graph->width = max_cols * 2;
 249 }
 250
 251 static void graph_update_columns(struct git_graph *graph)
 252 {
 253         struct commit_list *parent;
 254         struct column *tmp_columns;
 255         int max_new_columns;
 256         int mapping_idx;
 257         int i, seen_this, is_commit_in_columns;
 258
 259         /*
 260          * Swap graph->columns with graph->new_columns
 261          * graph->columns contains the state for the previous commit,
 262          * and new_columns now contains the state for our commit.
 263          *
 264          * We'll re-use the old columns array as storage to compute the new
 265          * columns list for the commit after this one.
 266          */
 267         tmp_columns = graph->columns;
 268         graph->columns = graph->new_columns;
 269         graph->num_columns = graph->num_new_columns;
 270
 271         graph->new_columns = tmp_columns;
 272         graph->num_new_columns = 0;
 273
 274         /*
 275          * Now update new_columns and mapping with the information for the
 276          * commit after this one.
 277          *
 278          * First, make sure we have enough room.  At most, there will
 279          * be graph->num_columns + graph->num_parents columns for the next
 280          * commit.
 281          */
 282         max_new_columns = graph->num_columns + graph->num_parents;
 283         graph_ensure_capacity(graph, max_new_columns);
 284
 285         /*
 286          * Clear out graph->mapping
 287          */
 288         graph->mapping_size = 2 * max_new_columns;
 289         for (i = 0; i < graph->mapping_size; i++)
 290                 graph->mapping[i] = -1;
 291
 292         /*
 293          * Populate graph->new_columns and graph->mapping
 294          *
 295          * Some of the parents of this commit may already be in
 296          * graph->columns.  If so, graph->new_columns should only contain a
 297          * single entry for each such commit.  graph->mapping should
 298          * contain information about where each current branch line is
 299          * supposed to end up after the collapsing is performed.
 300          */
 301         seen_this = 0;
 302         mapping_idx = 0;
 303         is_commit_in_columns = 1;
 304         for (i = 0; i <= graph->num_columns; i++) {
 305                 struct commit *col_commit;
 306                 if (i == graph->num_columns) {
 307                         if (seen_this)
 308                                 break;
 309                         is_commit_in_columns = 0;
 310                         col_commit = graph->commit;
 311                 } else {
 312                         col_commit = graph->columns[i].commit;
 313                 }
 314
 315                 if (col_commit == graph->commit) {
 316                         seen_this = 1;
 317                         for (parent = graph->commit->parents;
 318                              parent;
 319                              parent = parent->next) {
 320                                 graph_insert_into_new_columns(graph,
 321                                                               parent->item,
 322                                                               &mapping_idx);
 323                         }
 324                 } else {
 325                         graph_insert_into_new_columns(graph, col_commit,
 326                                                       &mapping_idx);
 327                 }
 328         }
 329
 330         /*
 331          * Shrink mapping_size to be the minimum necessary
 332          */
 333         while (graph->mapping_size > 1 &&
 334                graph->mapping[graph->mapping_size - 1] < 0)
 335                 graph->mapping_size--;
 336
 337         /*
 338          * Compute graph->width for this commit
 339          */
 340         graph_update_width(graph, is_commit_in_columns);
 341 }
 342
 343 void graph_update(struct git_graph *graph, struct commit *commit)
 344 {
 345         struct commit_list *parent;
 346
 347         /*
 348          * Set the new commit
 349          */
 350         graph->commit = commit;
 351
 352         /*
 353          * Count how many parents this commit has
 354          */
 355         graph->num_parents = 0;
 356         for (parent = commit->parents; parent; parent = parent->next)
 357                 graph->num_parents++;
 358
 359         /*
 360          * Call graph_update_columns() to update
 361          * columns, new_columns, and mapping.
 362          */
 363         graph_update_columns(graph);
 364
 365         graph->expansion_row = 0;
 366
 367         /*
 368          * Update graph->state.
 369          *
 370          * If the previous commit didn't get to the GRAPH_PADDING state,
 371          * it never finished its output.  Goto GRAPH_SKIP, to print out
 372          * a line to indicate that portion of the graph is missing.
 373          *
 374          * Otherwise, if there are 3 or more parents, we need to print
 375          * extra rows before the commit, to expand the branch lines around
 376          * it and make room for it.
 377          *
 378          * If there are less than 3 parents, we can immediately print the
 379          * commit line.
 380          */
 381         if (graph->state != GRAPH_PADDING)
 382                 graph->state = GRAPH_SKIP;
 383         else if (graph->num_parents >= 3)
 384                 graph->state = GRAPH_PRE_COMMIT;
 385         else
 386                 graph->state = GRAPH_COMMIT;
 387 }
 388
 389 static int graph_is_mapping_correct(struct git_graph *graph)
 390 {
 391         int i;
 392
 393         /*
 394          * The mapping is up to date if each entry is at its target,
 395          * or is 1 greater than its target.
 396          * (If it is 1 greater than the target, '/' will be printed, so it
 397          * will look correct on the next row.)
 398          */
 399         for (i = 0; i < graph->mapping_size; i++) {
 400                 int target = graph->mapping[i];
 401                 if (target < 0)
 402                         continue;
 403                 if (target == (i / 2))
 404                         continue;
 405                 return 0;
 406         }
 407
 408         return 1;
 409 }
 410
 411 static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb)
 412 {
 413         /*
 414          * Add additional spaces to the end of the strbuf, so that all
 415          * lines for a particular commit have the same width.
 416          *
 417          * This way, fields printed to the right of the graph will remain
 418          * aligned for the entire commit.
 419          */
 420         int extra;
 421         if (sb->len >= graph->width)
 422                 return;
 423
 424         extra = graph->width - sb->len;
 425         strbuf_addf(sb, "%*s", (int) extra, "");
 426 }
 427
 428 static void graph_output_padding_line(struct git_graph *graph,
 429                                       struct strbuf *sb)
 430 {
 431         int i;
 432
 433         /*
 434          * We could conceivable be called with a NULL commit
 435          * if our caller has a bug, and invokes graph_next_line()
 436          * immediately after graph_init(), without first calling
 437          * graph_update().  Return without outputting anything in this
 438          * case.
 439          */
 440         if (!graph->commit)
 441                 return;
 442
 443         /*
 444          * Output a padding row, that leaves all branch lines unchanged
 445          */
 446         for (i = 0; i < graph->num_new_columns; i++) {
 447                 strbuf_addstr(sb, "| ");
 448         }
 449
 450         graph_pad_horizontally(graph, sb);
 451 }
 452
 453 static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
 454 {
 455         /*
 456          * Output an ellipsis to indicate that a portion
 457          * of the graph is missing.
 458          */
 459         strbuf_addstr(sb, "...");
 460         graph_pad_horizontally(graph, sb);
 461
 462         if (graph->num_parents >= 3)
 463                 graph->state = GRAPH_PRE_COMMIT;
 464         else
 465                 graph->state = GRAPH_COMMIT;
 466 }
 467
 468 static void graph_output_pre_commit_line(struct git_graph *graph,
 469                                          struct strbuf *sb)
 470 {
 471         int num_expansion_rows;
 472         int i, seen_this;
 473
 474         /*
 475          * This function formats a row that increases the space around a commit
 476          * with multiple parents, to make room for it.  It should only be
 477          * called when there are 3 or more parents.
 478          *
 479          * We need 2 extra rows for every parent over 2.
 480          */
 481         assert(graph->num_parents >= 3);
 482         num_expansion_rows = (graph->num_parents - 2) * 2;
 483
 484         /*
 485          * graph->expansion_row tracks the current expansion row we are on.
 486          * It should be in the range [0, num_expansion_rows - 1]
 487          */
 488         assert(0 <= graph->expansion_row &&
 489                graph->expansion_row < num_expansion_rows);
 490
 491         /*
 492          * Output the row
 493          */
 494         seen_this = 0;
 495         for (i = 0; i < graph->num_columns; i++) {
 496                 struct column *col = &graph->columns[i];
 497                 if (col->commit == graph->commit) {
 498                         seen_this = 1;
 499                         strbuf_addf(sb, "| %*s", graph->expansion_row, "");
 500                 } else if (seen_this) {
 501                         strbuf_addstr(sb, "\\ ");
 502                 } else {
 503                         strbuf_addstr(sb, "| ");
 504                 }
 505         }
 506
 507         graph_pad_horizontally(graph, sb);
 508
 509         /*
 510          * Increment graph->expansion_row,
 511          * and move to state GRAPH_COMMIT if necessary
 512          */
 513         graph->expansion_row++;
 514         if (graph->expansion_row >= num_expansion_rows)
 515                 graph->state = GRAPH_COMMIT;
 516 }
 517
 518 void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 519 {
 520         int seen_this = 0;
 521         int i, j;
 522
 523         /*
 524          * Output the row containing this commit
 525          * Iterate up to and including graph->num_columns,
 526          * since the current commit may not be in any of the existing
 527          * columns.  (This happens when the current commit doesn't have any
 528          * children that we have already processed.)
 529          */
 530         seen_this = 0;
 531         for (i = 0; i <= graph->num_columns; i++) {
 532                 struct commit *col_commit;
 533                 if (i == graph->num_columns) {
 534                         if (seen_this)
 535                                 break;
 536                         col_commit = graph->commit;
 537                 } else {
 538                         col_commit = graph->columns[i].commit;
 539                 }
 540
 541                 if (col_commit == graph->commit) {
 542                         seen_this = 1;
 543                         if (graph->num_parents > 1)
 544                                 strbuf_addch(sb, 'M');
 545                         else
 546                                 strbuf_addch(sb, '*');
 547
 548                         if (graph->num_parents < 2)
 549                                 strbuf_addch(sb, ' ');
 550                         else if (graph->num_parents == 2)
 551                                 strbuf_addstr(sb, "  ");
 552                         else {
 553                                 int num_dashes =
 554                                         ((graph->num_parents - 2) * 2) - 1;
 555                                 for (j = 0; j < num_dashes; j++)
 556                                         strbuf_addch(sb, '-');
 557                                 strbuf_addstr(sb, ". ");
 558                         }
 559                 } else if (seen_this && (graph->num_parents > 1)) {
 560                         strbuf_addstr(sb, "\\ ");
 561                 } else {
 562                         strbuf_addstr(sb, "| ");
 563                 }
 564         }
 565
 566         graph_pad_horizontally(graph, sb);
 567
 568         /*
 569          * Update graph->state
 570          */
 571         if (graph->num_parents > 1)
 572                 graph->state = GRAPH_POST_MERGE;
 573         else if (graph_is_mapping_correct(graph))
 574                 graph->state = GRAPH_PADDING;
 575         else
 576                 graph->state = GRAPH_COLLAPSING;
 577 }
 578
 579 void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
 580 {
 581         int seen_this = 0;
 582         int i, j;
 583
 584         /*
 585          * Output the post-merge row
 586          */
 587         for (i = 0; i <= graph->num_columns; i++) {
 588                 struct commit *col_commit;
 589                 if (i == graph->num_columns) {
 590                         if (seen_this)
 591                                 break;
 592                         col_commit = graph->commit;
 593                 } else {
 594                         col_commit = graph->columns[i].commit;
 595                 }
 596
 597                 if (col_commit == graph->commit) {
 598                         seen_this = 1;
 599                         strbuf_addch(sb, '|');
 600                         for (j = 0; j < graph->num_parents - 1; j++)
 601                                 strbuf_addstr(sb, "\\ ");
 602                         if (graph->num_parents == 2)
 603                                 strbuf_addch(sb, ' ');
 604                 } else if (seen_this && (graph->num_parents > 2)) {
 605                         strbuf_addstr(sb, "\\ ");
 606                 } else {
 607                         strbuf_addstr(sb, "| ");
 608                 }
 609         }
 610
 611         graph_pad_horizontally(graph, sb);
 612
 613         /*
 614          * Update graph->state
 615          */
 616         if (graph_is_mapping_correct(graph))
 617                 graph->state = GRAPH_PADDING;
 618         else
 619                 graph->state = GRAPH_COLLAPSING;
 620 }
 621
 622 void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
 623 {
 624         int i;
 625         int *tmp_mapping;
 626
 627         /*
 628          * Clear out the new_mapping array
 629          */
 630         for (i = 0; i < graph->mapping_size; i++)
 631                 graph->new_mapping[i] = -1;
 632
 633         for (i = 0; i < graph->mapping_size; i++) {
 634                 int target = graph->mapping[i];
 635                 if (target < 0)
 636                         continue;
 637
 638                 /*
 639                  * Since update_columns() always inserts the leftmost
 640                  * column first, each branch's target location should
 641                  * always be either its current location or to the left of
 642                  * its current location.
 643                  *
 644                  * We never have to move branches to the right.  This makes
 645                  * the graph much more legible, since whenever branches
 646                  * cross, only one is moving directions.
 647                  */
 648                 assert(target * 2 <= i);
 649
 650                 if (target * 2 == i) {
 651                         /*
 652                          * This column is already in the
 653                          * correct place
 654                          */
 655                         assert(graph->new_mapping[i] == -1);
 656                         graph->new_mapping[i] = target;
 657                 } else if (graph->new_mapping[i - 1] < 0) {
 658                         /*
 659                          * Nothing is to the left.
 660                          * Move to the left by one
 661                          */
 662                         graph->new_mapping[i - 1] = target;
 663                 } else if (graph->new_mapping[i - 1] == target) {
 664                         /*
 665                          * There is a branch line to our left
 666                          * already, and it is our target.  We
 667                          * combine with this line, since we share
 668                          * the same parent commit.
 669                          *
 670                          * We don't have to add anything to the
 671                          * output or new_mapping, since the
 672                          * existing branch line has already taken
 673                          * care of it.
 674                          */
 675                 } else {
 676                         /*
 677                          * There is a branch line to our left,
 678                          * but it isn't our target.  We need to
 679                          * cross over it.
 680                          *
 681                          * The space just to the left of this
 682                          * branch should always be empty.
 683                          */
 684                         assert(graph->new_mapping[i - 1] > target);
 685                         assert(graph->new_mapping[i - 2] < 0);
 686                         graph->new_mapping[i - 2] = target;
 687                 }
 688         }
 689
 690         /*
 691          * The new mapping may be 1 smaller than the old mapping
 692          */
 693         if (graph->new_mapping[graph->mapping_size - 1] < 0)
 694                 graph->mapping_size--;
 695
 696         /*
 697          * Output out a line based on the new mapping info
 698          */
 699         for (i = 0; i < graph->mapping_size; i++) {
 700                 int target = graph->new_mapping[i];
 701                 if (target < 0)
 702                         strbuf_addch(sb, ' ');
 703                 else if (target * 2 == i)
 704                         strbuf_addch(sb, '|');
 705                 else
 706                         strbuf_addch(sb, '/');
 707         }
 708
 709         graph_pad_horizontally(graph, sb);
 710
 711         /*
 712          * Swap mapping and new_mapping
 713          */
 714         tmp_mapping = graph->mapping;
 715         graph->mapping = graph->new_mapping;
 716         graph->new_mapping = tmp_mapping;
 717
 718         /*
 719          * If graph->mapping indicates that all of the branch lines
 720          * are already in the correct positions, we are done.
 721          * Otherwise, we need to collapse some branch lines together.
 722          */
 723         if (graph_is_mapping_correct(graph))
 724                 graph->state = GRAPH_PADDING;
 725 }
 726
 727 int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 728 {
 729         switch (graph->state) {
 730         case GRAPH_PADDING:
 731                 graph_output_padding_line(graph, sb);
 732                 return 0;
 733         case GRAPH_SKIP:
 734                 graph_output_skip_line(graph, sb);
 735                 return 0;
 736         case GRAPH_PRE_COMMIT:
 737                 graph_output_pre_commit_line(graph, sb);
 738                 return 0;
 739         case GRAPH_COMMIT:
 740                 graph_output_commit_line(graph, sb);
 741                 return 1;
 742         case GRAPH_POST_MERGE:
 743                 graph_output_post_merge_line(graph, sb);
 744                 return 0;
 745         case GRAPH_COLLAPSING:
 746                 graph_output_collapsing_line(graph, sb);
 747                 return 0;
 748         }
 749
 750         assert(0);
 751         return 0;
 752 }
 753
 754 void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 755 {
 756         int i, j;
 757
 758         if (graph->state != GRAPH_COMMIT) {
 759                 graph_next_line(graph, sb);
 760                 return;
 761         }
 762
 763         /*
 764          * Output the row containing this commit
 765          * Iterate up to and including graph->num_columns,
 766          * since the current commit may not be in any of the existing
 767          * columns.  (This happens when the current commit doesn't have any
 768          * children that we have already processed.)
 769          */
 770         for (i = 0; i < graph->num_columns; i++) {
 771                 struct commit *col_commit = graph->columns[i].commit;
 772                 if (col_commit == graph->commit) {
 773                         strbuf_addch(sb, '|');
 774
 775                         if (graph->num_parents < 3)
 776                                 strbuf_addch(sb, ' ');
 777                         else {
 778                                 int num_spaces = ((graph->num_parents - 2) * 2);
 779                                 for (j = 0; j < num_spaces; j++)
 780                                         strbuf_addch(sb, ' ');
 781                         }
 782                 } else {
 783                         strbuf_addstr(sb, "| ");
 784                 }
 785         }
 786
 787         graph_pad_horizontally(graph, sb);
 788 }
 789
 790 int graph_is_commit_finished(struct git_graph const *graph)
 791 {
 792         return (graph->state == GRAPH_PADDING);
 793 }
 794
 795 void graph_show_commit(struct git_graph *graph)
 796 {
 797         struct strbuf msgbuf;
 798         int shown_commit_line = 0;
 799
 800         if (!graph)
 801                 return;
 802
 803         strbuf_init(&msgbuf, 0);
 804
 805         while (!shown_commit_line) {
 806                 shown_commit_line = graph_next_line(graph, &msgbuf);
 807                 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
 808                 if (!shown_commit_line)
 809                         putchar('\n');
 810                 strbuf_setlen(&msgbuf, 0);
 811         }
 812
 813         strbuf_release(&msgbuf);
 814 }
 815
 816 void graph_show_oneline(struct git_graph *graph)
 817 {
 818         struct strbuf msgbuf;
 819
 820         if (!graph)
 821                 return;
 822
 823         strbuf_init(&msgbuf, 0);
 824         graph_next_line(graph, &msgbuf);
 825         fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
 826         strbuf_release(&msgbuf);
 827 }
 828
 829 void graph_show_padding(struct git_graph *graph)
 830 {
 831         struct strbuf msgbuf;
 832
 833         if (!graph)
 834                 return;
 835
 836         strbuf_init(&msgbuf, 0);
 837         graph_padding_line(graph, &msgbuf);
 838         fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
 839         strbuf_release(&msgbuf);
 840 }
 841
 842 int graph_show_remainder(struct git_graph *graph)
 843 {
 844         struct strbuf msgbuf;
 845         int shown = 0;
 846
 847         if (!graph)
 848                 return 0;
 849
 850         if (graph_is_commit_finished(graph))
 851                 return 0;
 852
 853         strbuf_init(&msgbuf, 0);
 854         for (;;) {
 855                 graph_next_line(graph, &msgbuf);
 856                 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
 857                 strbuf_setlen(&msgbuf, 0);
 858                 shown = 1;
 859
 860                 if (!graph_is_commit_finished(graph))
 861                         putchar('\n');
 862                 else
 863                         break;
 864         }
 865         strbuf_release(&msgbuf);
 866
 867         return shown;
 868 }
 869
 870
 871 void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)
 872 {
 873         char *p;
 874
 875         if (!graph) {
 876                 fwrite(sb->buf, sizeof(char), sb->len, stdout);
 877                 return;
 878         }
 879
 880         /*
 881          * Print the strbuf line by line,
 882          * and display the graph info before each line but the first.
 883          */
 884         p = sb->buf;
 885         while (p) {
 886                 size_t len;
 887                 char *next_p = strchr(p, '\n');
 888                 if (next_p) {
 889                         next_p++;
 890                         len = next_p - p;
 891                 } else {
 892                         len = (sb->buf + sb->len) - p;
 893                 }
 894                 fwrite(p, sizeof(char), len, stdout);
 895                 if (next_p && *next_p != '\0')
 896                         graph_show_oneline(graph);
 897                 p = next_p;
 898         }
 899 }
 900
 901 void graph_show_commit_msg(struct git_graph *graph,
 902                            struct strbuf const *sb)
 903 {
 904         int newline_terminated;
 905
 906         if (!graph) {
 907                 /*
 908                  * If there's no graph, just print the message buffer.
 909                  *
 910                  * The message buffer for CMIT_FMT_ONELINE and
 911                  * CMIT_FMT_USERFORMAT are already missing a terminating
 912                  * newline.  All of the other formats should have it.
 913                  */
 914                 fwrite(sb->buf, sizeof(char), sb->len, stdout);
 915                 return;
 916         }
 917
 918         newline_terminated = (sb->len && sb->buf[sb->len - 1] == '\n');
 919
 920         /*
 921          * Show the commit message
 922          */
 923         graph_show_strbuf(graph, sb);
 924
 925         /*
 926          * If there is more output needed for this commit, show it now
 927          */
 928         if (!graph_is_commit_finished(graph)) {
 929                 /*
 930                  * If sb doesn't have a terminating newline, print one now,
 931                  * so we can start the remainder of the graph output on a
 932                  * new line.
 933                  */
 934                 if (!newline_terminated)
 935                         putchar('\n');
 936
 937                 graph_show_remainder(graph);
 938
 939                 /*
 940                  * If sb ends with a newline, our output should too.
 941                  */
 942                 if (newline_terminated)
 943                         putchar('\n');
 944         }
 945 }