graph.con commit log --graph --left-right: show left/right information in place of '*' (7528f27)
   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
  32struct 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
  43enum graph_state {
  44        GRAPH_PADDING,
  45        GRAPH_SKIP,
  46        GRAPH_PRE_COMMIT,
  47        GRAPH_COMMIT,
  48        GRAPH_POST_MERGE,
  49        GRAPH_COLLAPSING
  50};
  51
  52struct 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
 132struct 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
 159void 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
 167static 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 */
 192static 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
 200static 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
 233static 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
 268static 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
 369void 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
 417static 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
 439static 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
 456static 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
 481static 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
 496static 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
 546void 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
 613void 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
 656void 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
 761int 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
 788void 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
 824int graph_is_commit_finished(struct git_graph const *graph)
 825{
 826        return (graph->state == GRAPH_PADDING);
 827}
 828
 829void 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
 850void 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
 863void 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
 876int 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
 905void 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
 935void 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}