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