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