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