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         /* The rev-info used for the current traversal */
  58         struct rev_info *revs;
  59         /*
  60          * The number of interesting parents that this commit has.
  61          *
  62          * Note that this is not the same as the actual number of parents.
  63          * This count excludes parents that won't be printed in the graph
  64          * output, as determined by graph_is_interesting().
  65          */
  66         int num_parents;
  67         /*
  68          * The width of the graph output for this commit.
  69          * All rows for this commit are padded to this width, so that
  70          * messages printed after the graph output are aligned.
  71          */
  72         int width;
  73         /*
  74          * The next expansion row to print
  75          * when state is GRAPH_PRE_COMMIT
  76          */
  77         int expansion_row;
  78         /*
  79          * The current output state.
  80          * This tells us what kind of line graph_next_line() should output.
  81          */
  82         enum graph_state state;
  83         /*
  84          * The maximum number of columns that can be stored in the columns
  85          * and new_columns arrays.  This is also half the number of entries
  86          * that can be stored in the mapping and new_mapping arrays.
  87          */
  88         int column_capacity;
  89         /*
  90          * The number of columns (also called "branch lines" in some places)
  91          */
  92         int num_columns;
  93         /*
  94          * The number of columns in the new_columns array
  95          */
  96         int num_new_columns;
  97         /*
  98          * The number of entries in the mapping array
  99          */
 100         int mapping_size;
 101         /*
 102          * The column state before we output the current commit.
 103          */
 104         struct column *columns;
 105         /*
 106          * The new column state after we output the current commit.
 107          * Only valid when state is GRAPH_COLLAPSING.
 108          */
 109         struct column *new_columns;
 110         /*
 111          * An array that tracks the current state of each
 112          * character in the output line during state GRAPH_COLLAPSING.
 113          * Each entry is -1 if this character is empty, or a non-negative
 114          * integer if the character contains a branch line.  The value of
 115          * the integer indicates the target position for this branch line.
 116          * (I.e., this array maps the current column positions to their
 117          * desired positions.)
 118          *
 119          * The maximum capacity of this array is always
 120          * sizeof(int) * 2 * column_capacity.
 121          */
 122         int *mapping;
 123         /*
 124          * A temporary array for computing the next mapping state
 125          * while we are outputting a mapping line.  This is stored as part
 126          * of the git_graph simply so we don't have to allocate a new
 127          * temporary array each time we have to output a collapsing line.
 128          */
 129         int *new_mapping;
 130 };
 131
 132 struct git_graph *graph_init(struct rev_info *opt)
 133 {
 134         struct git_graph *graph = xmalloc(sizeof(struct git_graph));
 135         graph->commit = NULL;
 136         graph->revs = opt;
 137         graph->num_parents = 0;
 138         graph->expansion_row = 0;
 139         graph->state = GRAPH_PADDING;
 140         graph->num_columns = 0;
 141         graph->num_new_columns = 0;
 142         graph->mapping_size = 0;
 143
 144         /*
 145          * Allocate a reasonably large default number of columns
 146          * We'll automatically grow columns later if we need more room.
 147          */
 148         graph->column_capacity = 30;
 149         graph->columns = xmalloc(sizeof(struct column) *
 150                                  graph->column_capacity);
 151         graph->new_columns = xmalloc(sizeof(struct column) *
 152                                      graph->column_capacity);
 153         graph->mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity);
 154         graph->new_mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity);
 155
 156         return graph;
 157 }
 158
 159 void graph_release(struct git_graph *graph)
 160 {
 161         free(graph->columns);
 162         free(graph->new_columns);
 163         free(graph->mapping);
 164         free(graph);
 165 }
 166
 167 static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
 168 {
 169         if (graph->column_capacity >= num_columns)
 170                 return;
 171
 172         do {
 173                 graph->column_capacity *= 2;
 174         } while (graph->column_capacity < num_columns);
 175
 176         graph->columns = xrealloc(graph->columns,
 177                                   sizeof(struct column) *
 178                                   graph->column_capacity);
 179         graph->new_columns = xrealloc(graph->new_columns,
 180                                       sizeof(struct column) *
 181                                       graph->column_capacity);
 182         graph->mapping = xrealloc(graph->mapping,
 183                                   sizeof(int) * 2 * graph->column_capacity);
 184         graph->new_mapping = xrealloc(graph->new_mapping,
 185                                       sizeof(int) * 2 * graph->column_capacity);
 186 }
 187
 188 /*
 189  * Returns 1 if the commit will be printed in the graph output,
 190  * and 0 otherwise.
 191  */
 192 static int graph_is_interesting(struct commit *commit)
 193 {
 194         /*
 195          * Uninteresting and pruned commits won't be printed
 196          */
 197         return (commit->object.flags & (UNINTERESTING | TREESAME)) ? 0 : 1;
 198 }
 199
 200 static void graph_insert_into_new_columns(struct git_graph *graph,
 201                                           struct commit *commit,
 202                                           int *mapping_index)
 203 {
 204         int i;
 205
 206         /*
 207          * Ignore uinteresting commits
 208          */
 209         if (!graph_is_interesting(commit))
 210                 return;
 211
 212         /*
 213          * If the commit is already in the new_columns list, we don't need to
 214          * add it.  Just update the mapping correctly.
 215          */
 216         for (i = 0; i < graph->num_new_columns; i++) {
 217                 if (graph->new_columns[i].commit == commit) {
 218                         graph->mapping[*mapping_index] = i;
 219                         *mapping_index += 2;
 220                         return;
 221                 }
 222         }
 223
 224         /*
 225          * This commit isn't already in new_columns.  Add it.
 226          */
 227         graph->new_columns[graph->num_new_columns].commit = commit;
 228         graph->mapping[*mapping_index] = graph->num_new_columns;
 229         *mapping_index += 2;
 230         graph->num_new_columns++;
 231 }
 232
 233 static void graph_update_width(struct git_graph *graph,
 234                                int is_commit_in_existing_columns)
 235 {
 236         /*
 237          * Compute the width needed to display the graph for this commit.
 238          * This is the maximum width needed for any row.  All other rows
 239          * will be padded to this width.
 240          *
 241          * Compute the number of columns in the widest row:
 242          * Count each existing column (graph->num_columns), and each new
 243          * column added by this commit.
 244          */
 245         int max_cols = graph->num_columns + graph->num_parents;
 246
 247         /*
 248          * Even if the current commit has no parents to be printed, it
 249          * still takes up a column for itself.
 250          */
 251         if (graph->num_parents < 1)
 252                 max_cols++;
 253
 254         /*
 255          * We added a column for the the current commit as part of
 256          * graph->num_parents.  If the current commit was already in
 257          * graph->columns, then we have double counted it.
 258          */
 259         if (is_commit_in_existing_columns)
 260                 max_cols--;
 261
 262         /*
 263          * Each column takes up 2 spaces
 264          */
 265         graph->width = max_cols * 2;
 266 }
 267
 268 static void graph_update_columns(struct git_graph *graph)
 269 {
 270         struct commit_list *parent;
 271         struct column *tmp_columns;
 272         int max_new_columns;
 273         int mapping_idx;
 274         int i, seen_this, is_commit_in_columns;
 275
 276         /*
 277          * Swap graph->columns with graph->new_columns
 278          * graph->columns contains the state for the previous commit,
 279          * and new_columns now contains the state for our commit.
 280          *
 281          * We'll re-use the old columns array as storage to compute the new
 282          * columns list for the commit after this one.
 283          */
 284         tmp_columns = graph->columns;
 285         graph->columns = graph->new_columns;
 286         graph->num_columns = graph->num_new_columns;
 287
 288         graph->new_columns = tmp_columns;
 289         graph->num_new_columns = 0;
 290
 291         /*
 292          * Now update new_columns and mapping with the information for the
 293          * commit after this one.
 294          *
 295          * First, make sure we have enough room.  At most, there will
 296          * be graph->num_columns + graph->num_parents columns for the next
 297          * commit.
 298          */
 299         max_new_columns = graph->num_columns + graph->num_parents;
 300         graph_ensure_capacity(graph, max_new_columns);
 301
 302         /*
 303          * Clear out graph->mapping
 304          */
 305         graph->mapping_size = 2 * max_new_columns;
 306         for (i = 0; i < graph->mapping_size; i++)
 307                 graph->mapping[i] = -1;
 308
 309         /*
 310          * Populate graph->new_columns and graph->mapping
 311          *
 312          * Some of the parents of this commit may already be in
 313          * graph->columns.  If so, graph->new_columns should only contain a
 314          * single entry for each such commit.  graph->mapping should
 315          * contain information about where each current branch line is
 316          * supposed to end up after the collapsing is performed.
 317          */
 318         seen_this = 0;
 319         mapping_idx = 0;
 320         is_commit_in_columns = 1;
 321         for (i = 0; i <= graph->num_columns; i++) {
 322                 struct commit *col_commit;
 323                 if (i == graph->num_columns) {
 324                         if (seen_this)
 325                                 break;
 326                         is_commit_in_columns = 0;
 327                         col_commit = graph->commit;
 328                 } else {
 329                         col_commit = graph->columns[i].commit;
 330                 }
 331
 332                 if (col_commit == graph->commit) {
 333                         int old_mapping_idx = mapping_idx;
 334                         seen_this = 1;
 335                         for (parent = graph->commit->parents;
 336                              parent;
 337                              parent = parent->next) {
 338                                 graph_insert_into_new_columns(graph,
 339                                                               parent->item,
 340                                                               &mapping_idx);
 341                         }
 342                         /*
 343                          * We always need to increment mapping_idx by at
 344                          * least 2, even if it has no interesting parents.
 345                          * The current commit always takes up at least 2
 346                          * spaces.
 347                          */
 348                         if (mapping_idx == old_mapping_idx)
 349                                 mapping_idx += 2;
 350                 } else {
 351                         graph_insert_into_new_columns(graph, col_commit,
 352                                                       &mapping_idx);
 353                 }
 354         }
 355
 356         /*
 357          * Shrink mapping_size to be the minimum necessary
 358          */
 359         while (graph->mapping_size > 1 &&
 360                graph->mapping[graph->mapping_size - 1] < 0)
 361                 graph->mapping_size--;
 362
 363         /*
 364          * Compute graph->width for this commit
 365          */
 366         graph_update_width(graph, is_commit_in_columns);
 367 }
 368
 369 void graph_update(struct git_graph *graph, struct commit *commit)
 370 {
 371         struct commit_list *parent;
 372
 373         /*
 374          * Set the new commit
 375          */
 376         graph->commit = commit;
 377
 378         /*
 379          * Count how many interesting parents this commit has
 380          */
 381         graph->num_parents = 0;
 382         for (parent = commit->parents; parent; parent = parent->next) {
 383                 if (graph_is_interesting(parent->item))
 384                         graph->num_parents++;
 385         }
 386
 387         /*
 388          * Call graph_update_columns() to update
 389          * columns, new_columns, and mapping.
 390          */
 391         graph_update_columns(graph);
 392
 393         graph->expansion_row = 0;
 394
 395         /*
 396          * Update graph->state.
 397          *
 398          * If the previous commit didn't get to the GRAPH_PADDING state,
 399          * it never finished its output.  Goto GRAPH_SKIP, to print out
 400          * a line to indicate that portion of the graph is missing.
 401          *
 402          * Otherwise, if there are 3 or more parents, we need to print
 403          * extra rows before the commit, to expand the branch lines around
 404          * it and make room for it.
 405          *
 406          * If there are less than 3 parents, we can immediately print the
 407          * commit line.
 408          */
 409         if (graph->state != GRAPH_PADDING)
 410                 graph->state = GRAPH_SKIP;
 411         else if (graph->num_parents >= 3)
 412                 graph->state = GRAPH_PRE_COMMIT;
 413         else
 414                 graph->state = GRAPH_COMMIT;
 415 }
 416
 417 static int graph_is_mapping_correct(struct git_graph *graph)
 418 {
 419         int i;
 420
 421         /*
 422          * The mapping is up to date if each entry is at its target,
 423          * or is 1 greater than its target.
 424          * (If it is 1 greater than the target, '/' will be printed, so it
 425          * will look correct on the next row.)
 426          */
 427         for (i = 0; i < graph->mapping_size; i++) {
 428                 int target = graph->mapping[i];
 429                 if (target < 0)
 430                         continue;
 431                 if (target == (i / 2))
 432                         continue;
 433                 return 0;
 434         }
 435
 436         return 1;
 437 }
 438
 439 static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb)
 440 {
 441         /*
 442          * Add additional spaces to the end of the strbuf, so that all
 443          * lines for a particular commit have the same width.
 444          *
 445          * This way, fields printed to the right of the graph will remain
 446          * aligned for the entire commit.
 447          */
 448         int extra;
 449         if (sb->len >= graph->width)
 450                 return;
 451
 452         extra = graph->width - sb->len;
 453         strbuf_addf(sb, "%*s", (int) extra, "");
 454 }
 455
 456 static void graph_output_padding_line(struct git_graph *graph,
 457                                       struct strbuf *sb)
 458 {
 459         int i;
 460
 461         /*
 462          * We could conceivable be called with a NULL commit
 463          * if our caller has a bug, and invokes graph_next_line()
 464          * immediately after graph_init(), without first calling
 465          * graph_update().  Return without outputting anything in this
 466          * case.
 467          */
 468         if (!graph->commit)
 469                 return;
 470
 471         /*
 472          * Output a padding row, that leaves all branch lines unchanged
 473          */
 474         for (i = 0; i < graph->num_new_columns; i++) {
 475                 strbuf_addstr(sb, "| ");
 476         }
 477
 478         graph_pad_horizontally(graph, sb);
 479 }
 480
 481 static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
 482 {
 483         /*
 484          * Output an ellipsis to indicate that a portion
 485          * of the graph is missing.
 486          */
 487         strbuf_addstr(sb, "...");
 488         graph_pad_horizontally(graph, sb);
 489
 490         if (graph->num_parents >= 3)
 491                 graph->state = GRAPH_PRE_COMMIT;
 492         else
 493                 graph->state = GRAPH_COMMIT;
 494 }
 495
 496 static void graph_output_pre_commit_line(struct git_graph *graph,
 497                                          struct strbuf *sb)
 498 {
 499         int num_expansion_rows;
 500         int i, seen_this;
 501
 502         /*
 503          * This function formats a row that increases the space around a commit
 504          * with multiple parents, to make room for it.  It should only be
 505          * called when there are 3 or more parents.
 506          *
 507          * We need 2 extra rows for every parent over 2.
 508          */
 509         assert(graph->num_parents >= 3);
 510         num_expansion_rows = (graph->num_parents - 2) * 2;
 511
 512         /*
 513          * graph->expansion_row tracks the current expansion row we are on.
 514          * It should be in the range [0, num_expansion_rows - 1]
 515          */
 516         assert(0 <= graph->expansion_row &&
 517                graph->expansion_row < num_expansion_rows);
 518
 519         /*
 520          * Output the row
 521          */
 522         seen_this = 0;
 523         for (i = 0; i < graph->num_columns; i++) {
 524                 struct column *col = &graph->columns[i];
 525                 if (col->commit == graph->commit) {
 526                         seen_this = 1;
 527                         strbuf_addf(sb, "| %*s", graph->expansion_row, "");
 528                 } else if (seen_this) {
 529                         strbuf_addstr(sb, "\\ ");
 530                 } else {
 531                         strbuf_addstr(sb, "| ");
 532                 }
 533         }
 534
 535         graph_pad_horizontally(graph, sb);
 536
 537         /*
 538          * Increment graph->expansion_row,
 539          * and move to state GRAPH_COMMIT if necessary
 540          */
 541         graph->expansion_row++;
 542         if (graph->expansion_row >= num_expansion_rows)
 543                 graph->state = GRAPH_COMMIT;
 544 }
 545
 546 void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 547 {
 548         int seen_this = 0;
 549         int i, j;
 550
 551         /*
 552          * Output the row containing this commit
 553          * Iterate up to and including graph->num_columns,
 554          * since the current commit may not be in any of the existing
 555          * columns.  (This happens when the current commit doesn't have any
 556          * children that we have already processed.)
 557          */
 558         seen_this = 0;
 559         for (i = 0; i <= graph->num_columns; i++) {
 560                 struct commit *col_commit;
 561                 if (i == graph->num_columns) {
 562                         if (seen_this)
 563                                 break;
 564                         col_commit = graph->commit;
 565                 } else {
 566                         col_commit = graph->columns[i].commit;
 567                 }
 568
 569                 if (col_commit == graph->commit) {
 570                         seen_this = 1;
 571
 572                         if (graph->revs && graph->revs->left_right) {
 573                                 if (graph->commit->object.flags & SYMMETRIC_LEFT)
 574                                         strbuf_addch(sb, '<');
 575                                 else
 576                                         strbuf_addch(sb, '>');
 577                         } else 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 }