graph.con commit Merge branch 'jk/maint-docs' into maint (2dd7984)
   1#include "cache.h"
   2#include "commit.h"
   3#include "color.h"
   4#include "graph.h"
   5#include "diff.h"
   6#include "revision.h"
   7
   8/* Internal API */
   9
  10/*
  11 * Output a padding line in the graph.
  12 * This is similar to graph_next_line().  However, it is guaranteed to
  13 * never print the current commit line.  Instead, if the commit line is
  14 * next, it will simply output a line of vertical padding, extending the
  15 * branch lines downwards, but leaving them otherwise unchanged.
  16 */
  17static void graph_padding_line(struct git_graph *graph, struct strbuf *sb);
  18
  19/*
  20 * Print a strbuf to stdout.  If the graph is non-NULL, all lines but the
  21 * first will be prefixed with the graph output.
  22 *
  23 * If the strbuf ends with a newline, the output will end after this
  24 * newline.  A new graph line will not be printed after the final newline.
  25 * If the strbuf is empty, no output will be printed.
  26 *
  27 * Since the first line will not include the graph output, the caller is
  28 * responsible for printing this line's graph (perhaps via
  29 * graph_show_commit() or graph_show_oneline()) before calling
  30 * graph_show_strbuf().
  31 */
  32static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
  33
  34/*
  35 * TODO:
  36 * - Limit the number of columns, similar to the way gitk does.
  37 *   If we reach more than a specified number of columns, omit
  38 *   sections of some columns.
  39 */
  40
  41struct column {
  42        /*
  43         * The parent commit of this column.
  44         */
  45        struct commit *commit;
  46        /*
  47         * The color to (optionally) print this column in.  This is an
  48         * index into column_colors.
  49         */
  50        unsigned short color;
  51};
  52
  53enum graph_state {
  54        GRAPH_PADDING,
  55        GRAPH_SKIP,
  56        GRAPH_PRE_COMMIT,
  57        GRAPH_COMMIT,
  58        GRAPH_POST_MERGE,
  59        GRAPH_COLLAPSING
  60};
  61
  62/*
  63 * The list of available column colors.
  64 */
  65static const char *column_colors_ansi[] = {
  66        GIT_COLOR_RED,
  67        GIT_COLOR_GREEN,
  68        GIT_COLOR_YELLOW,
  69        GIT_COLOR_BLUE,
  70        GIT_COLOR_MAGENTA,
  71        GIT_COLOR_CYAN,
  72        GIT_COLOR_BOLD_RED,
  73        GIT_COLOR_BOLD_GREEN,
  74        GIT_COLOR_BOLD_YELLOW,
  75        GIT_COLOR_BOLD_BLUE,
  76        GIT_COLOR_BOLD_MAGENTA,
  77        GIT_COLOR_BOLD_CYAN,
  78        GIT_COLOR_RESET,
  79};
  80
  81#define COLUMN_COLORS_ANSI_MAX (ARRAY_SIZE(column_colors_ansi) - 1)
  82
  83static const char **column_colors;
  84static unsigned short column_colors_max;
  85
  86void graph_set_column_colors(const char **colors, unsigned short colors_max)
  87{
  88        column_colors = colors;
  89        column_colors_max = colors_max;
  90}
  91
  92static const char *column_get_color_code(unsigned short color)
  93{
  94        return column_colors[color];
  95}
  96
  97static void strbuf_write_column(struct strbuf *sb, const struct column *c,
  98                                char col_char)
  99{
 100        if (c->color < column_colors_max)
 101                strbuf_addstr(sb, column_get_color_code(c->color));
 102        strbuf_addch(sb, col_char);
 103        if (c->color < column_colors_max)
 104                strbuf_addstr(sb, column_get_color_code(column_colors_max));
 105}
 106
 107struct git_graph {
 108        /*
 109         * The commit currently being processed
 110         */
 111        struct commit *commit;
 112        /* The rev-info used for the current traversal */
 113        struct rev_info *revs;
 114        /*
 115         * The number of interesting parents that this commit has.
 116         *
 117         * Note that this is not the same as the actual number of parents.
 118         * This count excludes parents that won't be printed in the graph
 119         * output, as determined by graph_is_interesting().
 120         */
 121        int num_parents;
 122        /*
 123         * The width of the graph output for this commit.
 124         * All rows for this commit are padded to this width, so that
 125         * messages printed after the graph output are aligned.
 126         */
 127        int width;
 128        /*
 129         * The next expansion row to print
 130         * when state is GRAPH_PRE_COMMIT
 131         */
 132        int expansion_row;
 133        /*
 134         * The current output state.
 135         * This tells us what kind of line graph_next_line() should output.
 136         */
 137        enum graph_state state;
 138        /*
 139         * The output state for the previous line of output.
 140         * This is primarily used to determine how the first merge line
 141         * should appear, based on the last line of the previous commit.
 142         */
 143        enum graph_state prev_state;
 144        /*
 145         * The index of the column that refers to this commit.
 146         *
 147         * If none of the incoming columns refer to this commit,
 148         * this will be equal to num_columns.
 149         */
 150        int commit_index;
 151        /*
 152         * The commit_index for the previously displayed commit.
 153         *
 154         * This is used to determine how the first line of a merge
 155         * graph output should appear, based on the last line of the
 156         * previous commit.
 157         */
 158        int prev_commit_index;
 159        /*
 160         * The maximum number of columns that can be stored in the columns
 161         * and new_columns arrays.  This is also half the number of entries
 162         * that can be stored in the mapping and new_mapping arrays.
 163         */
 164        int column_capacity;
 165        /*
 166         * The number of columns (also called "branch lines" in some places)
 167         */
 168        int num_columns;
 169        /*
 170         * The number of columns in the new_columns array
 171         */
 172        int num_new_columns;
 173        /*
 174         * The number of entries in the mapping array
 175         */
 176        int mapping_size;
 177        /*
 178         * The column state before we output the current commit.
 179         */
 180        struct column *columns;
 181        /*
 182         * The new column state after we output the current commit.
 183         * Only valid when state is GRAPH_COLLAPSING.
 184         */
 185        struct column *new_columns;
 186        /*
 187         * An array that tracks the current state of each
 188         * character in the output line during state GRAPH_COLLAPSING.
 189         * Each entry is -1 if this character is empty, or a non-negative
 190         * integer if the character contains a branch line.  The value of
 191         * the integer indicates the target position for this branch line.
 192         * (I.e., this array maps the current column positions to their
 193         * desired positions.)
 194         *
 195         * The maximum capacity of this array is always
 196         * sizeof(int) * 2 * column_capacity.
 197         */
 198        int *mapping;
 199        /*
 200         * A temporary array for computing the next mapping state
 201         * while we are outputting a mapping line.  This is stored as part
 202         * of the git_graph simply so we don't have to allocate a new
 203         * temporary array each time we have to output a collapsing line.
 204         */
 205        int *new_mapping;
 206        /*
 207         * The current default column color being used.  This is
 208         * stored as an index into the array column_colors.
 209         */
 210        unsigned short default_column_color;
 211};
 212
 213static struct strbuf *diff_output_prefix_callback(struct diff_options *opt, void *data)
 214{
 215        struct git_graph *graph = data;
 216        static struct strbuf msgbuf = STRBUF_INIT;
 217
 218        assert(graph);
 219
 220        strbuf_reset(&msgbuf);
 221        graph_padding_line(graph, &msgbuf);
 222        return &msgbuf;
 223}
 224
 225struct git_graph *graph_init(struct rev_info *opt)
 226{
 227        struct git_graph *graph = xmalloc(sizeof(struct git_graph));
 228
 229        if (!column_colors)
 230                graph_set_column_colors(column_colors_ansi,
 231                                        COLUMN_COLORS_ANSI_MAX);
 232
 233        graph->commit = NULL;
 234        graph->revs = opt;
 235        graph->num_parents = 0;
 236        graph->expansion_row = 0;
 237        graph->state = GRAPH_PADDING;
 238        graph->prev_state = GRAPH_PADDING;
 239        graph->commit_index = 0;
 240        graph->prev_commit_index = 0;
 241        graph->num_columns = 0;
 242        graph->num_new_columns = 0;
 243        graph->mapping_size = 0;
 244        /*
 245         * Start the column color at the maximum value, since we'll
 246         * always increment it for the first commit we output.
 247         * This way we start at 0 for the first commit.
 248         */
 249        graph->default_column_color = column_colors_max - 1;
 250
 251        /*
 252         * Allocate a reasonably large default number of columns
 253         * We'll automatically grow columns later if we need more room.
 254         */
 255        graph->column_capacity = 30;
 256        graph->columns = xmalloc(sizeof(struct column) *
 257                                 graph->column_capacity);
 258        graph->new_columns = xmalloc(sizeof(struct column) *
 259                                     graph->column_capacity);
 260        graph->mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity);
 261        graph->new_mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity);
 262
 263        /*
 264         * The diff output prefix callback, with this we can make
 265         * all the diff output to align with the graph lines.
 266         */
 267        opt->diffopt.output_prefix = diff_output_prefix_callback;
 268        opt->diffopt.output_prefix_data = graph;
 269
 270        return graph;
 271}
 272
 273static void graph_update_state(struct git_graph *graph, enum graph_state s)
 274{
 275        graph->prev_state = graph->state;
 276        graph->state = s;
 277}
 278
 279static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
 280{
 281        if (graph->column_capacity >= num_columns)
 282                return;
 283
 284        do {
 285                graph->column_capacity *= 2;
 286        } while (graph->column_capacity < num_columns);
 287
 288        graph->columns = xrealloc(graph->columns,
 289                                  sizeof(struct column) *
 290                                  graph->column_capacity);
 291        graph->new_columns = xrealloc(graph->new_columns,
 292                                      sizeof(struct column) *
 293                                      graph->column_capacity);
 294        graph->mapping = xrealloc(graph->mapping,
 295                                  sizeof(int) * 2 * graph->column_capacity);
 296        graph->new_mapping = xrealloc(graph->new_mapping,
 297                                      sizeof(int) * 2 * graph->column_capacity);
 298}
 299
 300/*
 301 * Returns 1 if the commit will be printed in the graph output,
 302 * and 0 otherwise.
 303 */
 304static int graph_is_interesting(struct git_graph *graph, struct commit *commit)
 305{
 306        /*
 307         * If revs->boundary is set, commits whose children have
 308         * been shown are always interesting, even if they have the
 309         * UNINTERESTING or TREESAME flags set.
 310         */
 311        if (graph->revs && graph->revs->boundary) {
 312                if (commit->object.flags & CHILD_SHOWN)
 313                        return 1;
 314        }
 315
 316        /*
 317         * Otherwise, use get_commit_action() to see if this commit is
 318         * interesting
 319         */
 320        return get_commit_action(graph->revs, commit) == commit_show;
 321}
 322
 323static struct commit_list *next_interesting_parent(struct git_graph *graph,
 324                                                   struct commit_list *orig)
 325{
 326        struct commit_list *list;
 327
 328        /*
 329         * If revs->first_parent_only is set, only the first
 330         * parent is interesting.  None of the others are.
 331         */
 332        if (graph->revs->first_parent_only)
 333                return NULL;
 334
 335        /*
 336         * Return the next interesting commit after orig
 337         */
 338        for (list = orig->next; list; list = list->next) {
 339                if (graph_is_interesting(graph, list->item))
 340                        return list;
 341        }
 342
 343        return NULL;
 344}
 345
 346static struct commit_list *first_interesting_parent(struct git_graph *graph)
 347{
 348        struct commit_list *parents = graph->commit->parents;
 349
 350        /*
 351         * If this commit has no parents, ignore it
 352         */
 353        if (!parents)
 354                return NULL;
 355
 356        /*
 357         * If the first parent is interesting, return it
 358         */
 359        if (graph_is_interesting(graph, parents->item))
 360                return parents;
 361
 362        /*
 363         * Otherwise, call next_interesting_parent() to get
 364         * the next interesting parent
 365         */
 366        return next_interesting_parent(graph, parents);
 367}
 368
 369static unsigned short graph_get_current_column_color(const struct git_graph *graph)
 370{
 371        if (!DIFF_OPT_TST(&graph->revs->diffopt, COLOR_DIFF))
 372                return column_colors_max;
 373        return graph->default_column_color;
 374}
 375
 376/*
 377 * Update the graph's default column color.
 378 */
 379static void graph_increment_column_color(struct git_graph *graph)
 380{
 381        graph->default_column_color = (graph->default_column_color + 1) %
 382                column_colors_max;
 383}
 384
 385static unsigned short graph_find_commit_color(const struct git_graph *graph,
 386                                              const struct commit *commit)
 387{
 388        int i;
 389        for (i = 0; i < graph->num_columns; i++) {
 390                if (graph->columns[i].commit == commit)
 391                        return graph->columns[i].color;
 392        }
 393        return graph_get_current_column_color(graph);
 394}
 395
 396static void graph_insert_into_new_columns(struct git_graph *graph,
 397                                          struct commit *commit,
 398                                          int *mapping_index)
 399{
 400        int i;
 401
 402        /*
 403         * If the commit is already in the new_columns list, we don't need to
 404         * add it.  Just update the mapping correctly.
 405         */
 406        for (i = 0; i < graph->num_new_columns; i++) {
 407                if (graph->new_columns[i].commit == commit) {
 408                        graph->mapping[*mapping_index] = i;
 409                        *mapping_index += 2;
 410                        return;
 411                }
 412        }
 413
 414        /*
 415         * This commit isn't already in new_columns.  Add it.
 416         */
 417        graph->new_columns[graph->num_new_columns].commit = commit;
 418        graph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit);
 419        graph->mapping[*mapping_index] = graph->num_new_columns;
 420        *mapping_index += 2;
 421        graph->num_new_columns++;
 422}
 423
 424static void graph_update_width(struct git_graph *graph,
 425                               int is_commit_in_existing_columns)
 426{
 427        /*
 428         * Compute the width needed to display the graph for this commit.
 429         * This is the maximum width needed for any row.  All other rows
 430         * will be padded to this width.
 431         *
 432         * Compute the number of columns in the widest row:
 433         * Count each existing column (graph->num_columns), and each new
 434         * column added by this commit.
 435         */
 436        int max_cols = graph->num_columns + graph->num_parents;
 437
 438        /*
 439         * Even if the current commit has no parents to be printed, it
 440         * still takes up a column for itself.
 441         */
 442        if (graph->num_parents < 1)
 443                max_cols++;
 444
 445        /*
 446         * We added a column for the current commit as part of
 447         * graph->num_parents.  If the current commit was already in
 448         * graph->columns, then we have double counted it.
 449         */
 450        if (is_commit_in_existing_columns)
 451                max_cols--;
 452
 453        /*
 454         * Each column takes up 2 spaces
 455         */
 456        graph->width = max_cols * 2;
 457}
 458
 459static void graph_update_columns(struct git_graph *graph)
 460{
 461        struct commit_list *parent;
 462        struct column *tmp_columns;
 463        int max_new_columns;
 464        int mapping_idx;
 465        int i, seen_this, is_commit_in_columns;
 466
 467        /*
 468         * Swap graph->columns with graph->new_columns
 469         * graph->columns contains the state for the previous commit,
 470         * and new_columns now contains the state for our commit.
 471         *
 472         * We'll re-use the old columns array as storage to compute the new
 473         * columns list for the commit after this one.
 474         */
 475        tmp_columns = graph->columns;
 476        graph->columns = graph->new_columns;
 477        graph->num_columns = graph->num_new_columns;
 478
 479        graph->new_columns = tmp_columns;
 480        graph->num_new_columns = 0;
 481
 482        /*
 483         * Now update new_columns and mapping with the information for the
 484         * commit after this one.
 485         *
 486         * First, make sure we have enough room.  At most, there will
 487         * be graph->num_columns + graph->num_parents columns for the next
 488         * commit.
 489         */
 490        max_new_columns = graph->num_columns + graph->num_parents;
 491        graph_ensure_capacity(graph, max_new_columns);
 492
 493        /*
 494         * Clear out graph->mapping
 495         */
 496        graph->mapping_size = 2 * max_new_columns;
 497        for (i = 0; i < graph->mapping_size; i++)
 498                graph->mapping[i] = -1;
 499
 500        /*
 501         * Populate graph->new_columns and graph->mapping
 502         *
 503         * Some of the parents of this commit may already be in
 504         * graph->columns.  If so, graph->new_columns should only contain a
 505         * single entry for each such commit.  graph->mapping should
 506         * contain information about where each current branch line is
 507         * supposed to end up after the collapsing is performed.
 508         */
 509        seen_this = 0;
 510        mapping_idx = 0;
 511        is_commit_in_columns = 1;
 512        for (i = 0; i <= graph->num_columns; i++) {
 513                struct commit *col_commit;
 514                if (i == graph->num_columns) {
 515                        if (seen_this)
 516                                break;
 517                        is_commit_in_columns = 0;
 518                        col_commit = graph->commit;
 519                } else {
 520                        col_commit = graph->columns[i].commit;
 521                }
 522
 523                if (col_commit == graph->commit) {
 524                        int old_mapping_idx = mapping_idx;
 525                        seen_this = 1;
 526                        graph->commit_index = i;
 527                        for (parent = first_interesting_parent(graph);
 528                             parent;
 529                             parent = next_interesting_parent(graph, parent)) {
 530                                /*
 531                                 * If this is a merge, or the start of a new
 532                                 * childless column, increment the current
 533                                 * color.
 534                                 */
 535                                if (graph->num_parents > 1 ||
 536                                    !is_commit_in_columns) {
 537                                        graph_increment_column_color(graph);
 538                                }
 539                                graph_insert_into_new_columns(graph,
 540                                                              parent->item,
 541                                                              &mapping_idx);
 542                        }
 543                        /*
 544                         * We always need to increment mapping_idx by at
 545                         * least 2, even if it has no interesting parents.
 546                         * The current commit always takes up at least 2
 547                         * spaces.
 548                         */
 549                        if (mapping_idx == old_mapping_idx)
 550                                mapping_idx += 2;
 551                } else {
 552                        graph_insert_into_new_columns(graph, col_commit,
 553                                                      &mapping_idx);
 554                }
 555        }
 556
 557        /*
 558         * Shrink mapping_size to be the minimum necessary
 559         */
 560        while (graph->mapping_size > 1 &&
 561               graph->mapping[graph->mapping_size - 1] < 0)
 562                graph->mapping_size--;
 563
 564        /*
 565         * Compute graph->width for this commit
 566         */
 567        graph_update_width(graph, is_commit_in_columns);
 568}
 569
 570void graph_update(struct git_graph *graph, struct commit *commit)
 571{
 572        struct commit_list *parent;
 573
 574        /*
 575         * Set the new commit
 576         */
 577        graph->commit = commit;
 578
 579        /*
 580         * Count how many interesting parents this commit has
 581         */
 582        graph->num_parents = 0;
 583        for (parent = first_interesting_parent(graph);
 584             parent;
 585             parent = next_interesting_parent(graph, parent))
 586        {
 587                graph->num_parents++;
 588        }
 589
 590        /*
 591         * Store the old commit_index in prev_commit_index.
 592         * graph_update_columns() will update graph->commit_index for this
 593         * commit.
 594         */
 595        graph->prev_commit_index = graph->commit_index;
 596
 597        /*
 598         * Call graph_update_columns() to update
 599         * columns, new_columns, and mapping.
 600         */
 601        graph_update_columns(graph);
 602
 603        graph->expansion_row = 0;
 604
 605        /*
 606         * Update graph->state.
 607         * Note that we don't call graph_update_state() here, since
 608         * we don't want to update graph->prev_state.  No line for
 609         * graph->state was ever printed.
 610         *
 611         * If the previous commit didn't get to the GRAPH_PADDING state,
 612         * it never finished its output.  Goto GRAPH_SKIP, to print out
 613         * a line to indicate that portion of the graph is missing.
 614         *
 615         * If there are 3 or more parents, we may need to print extra rows
 616         * before the commit, to expand the branch lines around it and make
 617         * room for it.  We need to do this only if there is a branch row
 618         * (or more) to the right of this commit.
 619         *
 620         * If there are less than 3 parents, we can immediately print the
 621         * commit line.
 622         */
 623        if (graph->state != GRAPH_PADDING)
 624                graph->state = GRAPH_SKIP;
 625        else if (graph->num_parents >= 3 &&
 626                 graph->commit_index < (graph->num_columns - 1))
 627                graph->state = GRAPH_PRE_COMMIT;
 628        else
 629                graph->state = GRAPH_COMMIT;
 630}
 631
 632static int graph_is_mapping_correct(struct git_graph *graph)
 633{
 634        int i;
 635
 636        /*
 637         * The mapping is up to date if each entry is at its target,
 638         * or is 1 greater than its target.
 639         * (If it is 1 greater than the target, '/' will be printed, so it
 640         * will look correct on the next row.)
 641         */
 642        for (i = 0; i < graph->mapping_size; i++) {
 643                int target = graph->mapping[i];
 644                if (target < 0)
 645                        continue;
 646                if (target == (i / 2))
 647                        continue;
 648                return 0;
 649        }
 650
 651        return 1;
 652}
 653
 654static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
 655                                   int chars_written)
 656{
 657        /*
 658         * Add additional spaces to the end of the strbuf, so that all
 659         * lines for a particular commit have the same width.
 660         *
 661         * This way, fields printed to the right of the graph will remain
 662         * aligned for the entire commit.
 663         */
 664        int extra;
 665        if (chars_written >= graph->width)
 666                return;
 667
 668        extra = graph->width - chars_written;
 669        strbuf_addf(sb, "%*s", (int) extra, "");
 670}
 671
 672static void graph_output_padding_line(struct git_graph *graph,
 673                                      struct strbuf *sb)
 674{
 675        int i;
 676
 677        /*
 678         * We could conceivable be called with a NULL commit
 679         * if our caller has a bug, and invokes graph_next_line()
 680         * immediately after graph_init(), without first calling
 681         * graph_update().  Return without outputting anything in this
 682         * case.
 683         */
 684        if (!graph->commit)
 685                return;
 686
 687        /*
 688         * Output a padding row, that leaves all branch lines unchanged
 689         */
 690        for (i = 0; i < graph->num_new_columns; i++) {
 691                strbuf_write_column(sb, &graph->new_columns[i], '|');
 692                strbuf_addch(sb, ' ');
 693        }
 694
 695        graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
 696}
 697
 698static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
 699{
 700        /*
 701         * Output an ellipsis to indicate that a portion
 702         * of the graph is missing.
 703         */
 704        strbuf_addstr(sb, "...");
 705        graph_pad_horizontally(graph, sb, 3);
 706
 707        if (graph->num_parents >= 3 &&
 708            graph->commit_index < (graph->num_columns - 1))
 709                graph_update_state(graph, GRAPH_PRE_COMMIT);
 710        else
 711                graph_update_state(graph, GRAPH_COMMIT);
 712}
 713
 714static void graph_output_pre_commit_line(struct git_graph *graph,
 715                                         struct strbuf *sb)
 716{
 717        int num_expansion_rows;
 718        int i, seen_this;
 719        int chars_written;
 720
 721        /*
 722         * This function formats a row that increases the space around a commit
 723         * with multiple parents, to make room for it.  It should only be
 724         * called when there are 3 or more parents.
 725         *
 726         * We need 2 extra rows for every parent over 2.
 727         */
 728        assert(graph->num_parents >= 3);
 729        num_expansion_rows = (graph->num_parents - 2) * 2;
 730
 731        /*
 732         * graph->expansion_row tracks the current expansion row we are on.
 733         * It should be in the range [0, num_expansion_rows - 1]
 734         */
 735        assert(0 <= graph->expansion_row &&
 736               graph->expansion_row < num_expansion_rows);
 737
 738        /*
 739         * Output the row
 740         */
 741        seen_this = 0;
 742        chars_written = 0;
 743        for (i = 0; i < graph->num_columns; i++) {
 744                struct column *col = &graph->columns[i];
 745                if (col->commit == graph->commit) {
 746                        seen_this = 1;
 747                        strbuf_write_column(sb, col, '|');
 748                        strbuf_addf(sb, "%*s", graph->expansion_row, "");
 749                        chars_written += 1 + graph->expansion_row;
 750                } else if (seen_this && (graph->expansion_row == 0)) {
 751                        /*
 752                         * This is the first line of the pre-commit output.
 753                         * If the previous commit was a merge commit and
 754                         * ended in the GRAPH_POST_MERGE state, all branch
 755                         * lines after graph->prev_commit_index were
 756                         * printed as "\" on the previous line.  Continue
 757                         * to print them as "\" on this line.  Otherwise,
 758                         * print the branch lines as "|".
 759                         */
 760                        if (graph->prev_state == GRAPH_POST_MERGE &&
 761                            graph->prev_commit_index < i)
 762                                strbuf_write_column(sb, col, '\\');
 763                        else
 764                                strbuf_write_column(sb, col, '|');
 765                        chars_written++;
 766                } else if (seen_this && (graph->expansion_row > 0)) {
 767                        strbuf_write_column(sb, col, '\\');
 768                        chars_written++;
 769                } else {
 770                        strbuf_write_column(sb, col, '|');
 771                        chars_written++;
 772                }
 773                strbuf_addch(sb, ' ');
 774                chars_written++;
 775        }
 776
 777        graph_pad_horizontally(graph, sb, chars_written);
 778
 779        /*
 780         * Increment graph->expansion_row,
 781         * and move to state GRAPH_COMMIT if necessary
 782         */
 783        graph->expansion_row++;
 784        if (graph->expansion_row >= num_expansion_rows)
 785                graph_update_state(graph, GRAPH_COMMIT);
 786}
 787
 788static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
 789{
 790        /*
 791         * For boundary commits, print 'o'
 792         * (We should only see boundary commits when revs->boundary is set.)
 793         */
 794        if (graph->commit->object.flags & BOUNDARY) {
 795                assert(graph->revs->boundary);
 796                strbuf_addch(sb, 'o');
 797                return;
 798        }
 799
 800        /*
 801         * get_revision_mark() handles all other cases without assert()
 802         */
 803        strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit));
 804}
 805
 806/*
 807 * Draw an octopus merge and return the number of characters written.
 808 */
 809static int graph_draw_octopus_merge(struct git_graph *graph,
 810                                    struct strbuf *sb)
 811{
 812        /*
 813         * Here dashless_commits represents the number of parents
 814         * which don't need to have dashes (because their edges fit
 815         * neatly under the commit).
 816         */
 817        const int dashless_commits = 2;
 818        int col_num, i;
 819        int num_dashes =
 820                ((graph->num_parents - dashless_commits) * 2) - 1;
 821        for (i = 0; i < num_dashes; i++) {
 822                col_num = (i / 2) + dashless_commits;
 823                strbuf_write_column(sb, &graph->new_columns[col_num], '-');
 824        }
 825        col_num = (i / 2) + dashless_commits;
 826        strbuf_write_column(sb, &graph->new_columns[col_num], '.');
 827        return num_dashes + 1;
 828}
 829
 830static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 831{
 832        int seen_this = 0;
 833        int i, chars_written;
 834
 835        /*
 836         * Output the row containing this commit
 837         * Iterate up to and including graph->num_columns,
 838         * since the current commit may not be in any of the existing
 839         * columns.  (This happens when the current commit doesn't have any
 840         * children that we have already processed.)
 841         */
 842        seen_this = 0;
 843        chars_written = 0;
 844        for (i = 0; i <= graph->num_columns; i++) {
 845                struct column *col = &graph->columns[i];
 846                struct commit *col_commit;
 847                if (i == graph->num_columns) {
 848                        if (seen_this)
 849                                break;
 850                        col_commit = graph->commit;
 851                } else {
 852                        col_commit = graph->columns[i].commit;
 853                }
 854
 855                if (col_commit == graph->commit) {
 856                        seen_this = 1;
 857                        graph_output_commit_char(graph, sb);
 858                        chars_written++;
 859
 860                        if (graph->num_parents > 2)
 861                                chars_written += graph_draw_octopus_merge(graph,
 862                                                                          sb);
 863                } else if (seen_this && (graph->num_parents > 2)) {
 864                        strbuf_write_column(sb, col, '\\');
 865                        chars_written++;
 866                } else if (seen_this && (graph->num_parents == 2)) {
 867                        /*
 868                         * This is a 2-way merge commit.
 869                         * There is no GRAPH_PRE_COMMIT stage for 2-way
 870                         * merges, so this is the first line of output
 871                         * for this commit.  Check to see what the previous
 872                         * line of output was.
 873                         *
 874                         * If it was GRAPH_POST_MERGE, the branch line
 875                         * coming into this commit may have been '\',
 876                         * and not '|' or '/'.  If so, output the branch
 877                         * line as '\' on this line, instead of '|'.  This
 878                         * makes the output look nicer.
 879                         */
 880                        if (graph->prev_state == GRAPH_POST_MERGE &&
 881                            graph->prev_commit_index < i)
 882                                strbuf_write_column(sb, col, '\\');
 883                        else
 884                                strbuf_write_column(sb, col, '|');
 885                        chars_written++;
 886                } else {
 887                        strbuf_write_column(sb, col, '|');
 888                        chars_written++;
 889                }
 890                strbuf_addch(sb, ' ');
 891                chars_written++;
 892        }
 893
 894        graph_pad_horizontally(graph, sb, chars_written);
 895
 896        /*
 897         * Update graph->state
 898         */
 899        if (graph->num_parents > 1)
 900                graph_update_state(graph, GRAPH_POST_MERGE);
 901        else if (graph_is_mapping_correct(graph))
 902                graph_update_state(graph, GRAPH_PADDING);
 903        else
 904                graph_update_state(graph, GRAPH_COLLAPSING);
 905}
 906
 907static struct column *find_new_column_by_commit(struct git_graph *graph,
 908                                                struct commit *commit)
 909{
 910        int i;
 911        for (i = 0; i < graph->num_new_columns; i++) {
 912                if (graph->new_columns[i].commit == commit)
 913                        return &graph->new_columns[i];
 914        }
 915        return NULL;
 916}
 917
 918static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
 919{
 920        int seen_this = 0;
 921        int i, j, chars_written;
 922
 923        /*
 924         * Output the post-merge row
 925         */
 926        chars_written = 0;
 927        for (i = 0; i <= graph->num_columns; i++) {
 928                struct column *col = &graph->columns[i];
 929                struct commit *col_commit;
 930                if (i == graph->num_columns) {
 931                        if (seen_this)
 932                                break;
 933                        col_commit = graph->commit;
 934                } else {
 935                        col_commit = col->commit;
 936                }
 937
 938                if (col_commit == graph->commit) {
 939                        /*
 940                         * Since the current commit is a merge find
 941                         * the columns for the parent commits in
 942                         * new_columns and use those to format the
 943                         * edges.
 944                         */
 945                        struct commit_list *parents = NULL;
 946                        struct column *par_column;
 947                        seen_this = 1;
 948                        parents = first_interesting_parent(graph);
 949                        assert(parents);
 950                        par_column = find_new_column_by_commit(graph, parents->item);
 951                        assert(par_column);
 952
 953                        strbuf_write_column(sb, par_column, '|');
 954                        chars_written++;
 955                        for (j = 0; j < graph->num_parents - 1; j++) {
 956                                parents = next_interesting_parent(graph, parents);
 957                                assert(parents);
 958                                par_column = find_new_column_by_commit(graph, parents->item);
 959                                assert(par_column);
 960                                strbuf_write_column(sb, par_column, '\\');
 961                                strbuf_addch(sb, ' ');
 962                        }
 963                        chars_written += j * 2;
 964                } else if (seen_this) {
 965                        strbuf_write_column(sb, col, '\\');
 966                        strbuf_addch(sb, ' ');
 967                        chars_written += 2;
 968                } else {
 969                        strbuf_write_column(sb, col, '|');
 970                        strbuf_addch(sb, ' ');
 971                        chars_written += 2;
 972                }
 973        }
 974
 975        graph_pad_horizontally(graph, sb, chars_written);
 976
 977        /*
 978         * Update graph->state
 979         */
 980        if (graph_is_mapping_correct(graph))
 981                graph_update_state(graph, GRAPH_PADDING);
 982        else
 983                graph_update_state(graph, GRAPH_COLLAPSING);
 984}
 985
 986static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
 987{
 988        int i;
 989        int *tmp_mapping;
 990        short used_horizontal = 0;
 991        int horizontal_edge = -1;
 992        int horizontal_edge_target = -1;
 993
 994        /*
 995         * Clear out the new_mapping array
 996         */
 997        for (i = 0; i < graph->mapping_size; i++)
 998                graph->new_mapping[i] = -1;
 999
1000        for (i = 0; i < graph->mapping_size; i++) {
1001                int target = graph->mapping[i];
1002                if (target < 0)
1003                        continue;
1004
1005                /*
1006                 * Since update_columns() always inserts the leftmost
1007                 * column first, each branch's target location should
1008                 * always be either its current location or to the left of
1009                 * its current location.
1010                 *
1011                 * We never have to move branches to the right.  This makes
1012                 * the graph much more legible, since whenever branches
1013                 * cross, only one is moving directions.
1014                 */
1015                assert(target * 2 <= i);
1016
1017                if (target * 2 == i) {
1018                        /*
1019                         * This column is already in the
1020                         * correct place
1021                         */
1022                        assert(graph->new_mapping[i] == -1);
1023                        graph->new_mapping[i] = target;
1024                } else if (graph->new_mapping[i - 1] < 0) {
1025                        /*
1026                         * Nothing is to the left.
1027                         * Move to the left by one
1028                         */
1029                        graph->new_mapping[i - 1] = target;
1030                        /*
1031                         * If there isn't already an edge moving horizontally
1032                         * select this one.
1033                         */
1034                        if (horizontal_edge == -1) {
1035                                int j;
1036                                horizontal_edge = i;
1037                                horizontal_edge_target = target;
1038                                /*
1039                                 * The variable target is the index of the graph
1040                                 * column, and therefore target*2+3 is the
1041                                 * actual screen column of the first horizontal
1042                                 * line.
1043                                 */
1044                                for (j = (target * 2)+3; j < (i - 2); j += 2)
1045                                        graph->new_mapping[j] = target;
1046                        }
1047                } else if (graph->new_mapping[i - 1] == target) {
1048                        /*
1049                         * There is a branch line to our left
1050                         * already, and it is our target.  We
1051                         * combine with this line, since we share
1052                         * the same parent commit.
1053                         *
1054                         * We don't have to add anything to the
1055                         * output or new_mapping, since the
1056                         * existing branch line has already taken
1057                         * care of it.
1058                         */
1059                } else {
1060                        /*
1061                         * There is a branch line to our left,
1062                         * but it isn't our target.  We need to
1063                         * cross over it.
1064                         *
1065                         * The space just to the left of this
1066                         * branch should always be empty.
1067                         *
1068                         * The branch to the left of that space
1069                         * should be our eventual target.
1070                         */
1071                        assert(graph->new_mapping[i - 1] > target);
1072                        assert(graph->new_mapping[i - 2] < 0);
1073                        assert(graph->new_mapping[i - 3] == target);
1074                        graph->new_mapping[i - 2] = target;
1075                        /*
1076                         * Mark this branch as the horizontal edge to
1077                         * prevent any other edges from moving
1078                         * horizontally.
1079                         */
1080                        if (horizontal_edge == -1)
1081                                horizontal_edge = i;
1082                }
1083        }
1084
1085        /*
1086         * The new mapping may be 1 smaller than the old mapping
1087         */
1088        if (graph->new_mapping[graph->mapping_size - 1] < 0)
1089                graph->mapping_size--;
1090
1091        /*
1092         * Output out a line based on the new mapping info
1093         */
1094        for (i = 0; i < graph->mapping_size; i++) {
1095                int target = graph->new_mapping[i];
1096                if (target < 0)
1097                        strbuf_addch(sb, ' ');
1098                else if (target * 2 == i)
1099                        strbuf_write_column(sb, &graph->new_columns[target], '|');
1100                else if (target == horizontal_edge_target &&
1101                         i != horizontal_edge - 1) {
1102                                /*
1103                                 * Set the mappings for all but the
1104                                 * first segment to -1 so that they
1105                                 * won't continue into the next line.
1106                                 */
1107                                if (i != (target * 2)+3)
1108                                        graph->new_mapping[i] = -1;
1109                                used_horizontal = 1;
1110                        strbuf_write_column(sb, &graph->new_columns[target], '_');
1111                } else {
1112                        if (used_horizontal && i < horizontal_edge)
1113                                graph->new_mapping[i] = -1;
1114                        strbuf_write_column(sb, &graph->new_columns[target], '/');
1115
1116                }
1117        }
1118
1119        graph_pad_horizontally(graph, sb, graph->mapping_size);
1120
1121        /*
1122         * Swap mapping and new_mapping
1123         */
1124        tmp_mapping = graph->mapping;
1125        graph->mapping = graph->new_mapping;
1126        graph->new_mapping = tmp_mapping;
1127
1128        /*
1129         * If graph->mapping indicates that all of the branch lines
1130         * are already in the correct positions, we are done.
1131         * Otherwise, we need to collapse some branch lines together.
1132         */
1133        if (graph_is_mapping_correct(graph))
1134                graph_update_state(graph, GRAPH_PADDING);
1135}
1136
1137int graph_next_line(struct git_graph *graph, struct strbuf *sb)
1138{
1139        switch (graph->state) {
1140        case GRAPH_PADDING:
1141                graph_output_padding_line(graph, sb);
1142                return 0;
1143        case GRAPH_SKIP:
1144                graph_output_skip_line(graph, sb);
1145                return 0;
1146        case GRAPH_PRE_COMMIT:
1147                graph_output_pre_commit_line(graph, sb);
1148                return 0;
1149        case GRAPH_COMMIT:
1150                graph_output_commit_line(graph, sb);
1151                return 1;
1152        case GRAPH_POST_MERGE:
1153                graph_output_post_merge_line(graph, sb);
1154                return 0;
1155        case GRAPH_COLLAPSING:
1156                graph_output_collapsing_line(graph, sb);
1157                return 0;
1158        }
1159
1160        assert(0);
1161        return 0;
1162}
1163
1164static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
1165{
1166        int i, j;
1167
1168        if (graph->state != GRAPH_COMMIT) {
1169                graph_next_line(graph, sb);
1170                return;
1171        }
1172
1173        /*
1174         * Output the row containing this commit
1175         * Iterate up to and including graph->num_columns,
1176         * since the current commit may not be in any of the existing
1177         * columns.  (This happens when the current commit doesn't have any
1178         * children that we have already processed.)
1179         */
1180        for (i = 0; i < graph->num_columns; i++) {
1181                struct column *col = &graph->columns[i];
1182                struct commit *col_commit = col->commit;
1183                if (col_commit == graph->commit) {
1184                        strbuf_write_column(sb, col, '|');
1185
1186                        if (graph->num_parents < 3)
1187                                strbuf_addch(sb, ' ');
1188                        else {
1189                                int num_spaces = ((graph->num_parents - 2) * 2);
1190                                for (j = 0; j < num_spaces; j++)
1191                                        strbuf_addch(sb, ' ');
1192                        }
1193                } else {
1194                        strbuf_write_column(sb, col, '|');
1195                        strbuf_addch(sb, ' ');
1196                }
1197        }
1198
1199        graph_pad_horizontally(graph, sb, graph->num_columns);
1200
1201        /*
1202         * Update graph->prev_state since we have output a padding line
1203         */
1204        graph->prev_state = GRAPH_PADDING;
1205}
1206
1207int graph_is_commit_finished(struct git_graph const *graph)
1208{
1209        return (graph->state == GRAPH_PADDING);
1210}
1211
1212void graph_show_commit(struct git_graph *graph)
1213{
1214        struct strbuf msgbuf = STRBUF_INIT;
1215        int shown_commit_line = 0;
1216
1217        if (!graph)
1218                return;
1219
1220        while (!shown_commit_line) {
1221                shown_commit_line = graph_next_line(graph, &msgbuf);
1222                fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1223                if (!shown_commit_line)
1224                        putchar('\n');
1225                strbuf_setlen(&msgbuf, 0);
1226        }
1227
1228        strbuf_release(&msgbuf);
1229}
1230
1231void graph_show_oneline(struct git_graph *graph)
1232{
1233        struct strbuf msgbuf = STRBUF_INIT;
1234
1235        if (!graph)
1236                return;
1237
1238        graph_next_line(graph, &msgbuf);
1239        fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1240        strbuf_release(&msgbuf);
1241}
1242
1243void graph_show_padding(struct git_graph *graph)
1244{
1245        struct strbuf msgbuf = STRBUF_INIT;
1246
1247        if (!graph)
1248                return;
1249
1250        graph_padding_line(graph, &msgbuf);
1251        fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1252        strbuf_release(&msgbuf);
1253}
1254
1255int graph_show_remainder(struct git_graph *graph)
1256{
1257        struct strbuf msgbuf = STRBUF_INIT;
1258        int shown = 0;
1259
1260        if (!graph)
1261                return 0;
1262
1263        if (graph_is_commit_finished(graph))
1264                return 0;
1265
1266        for (;;) {
1267                graph_next_line(graph, &msgbuf);
1268                fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1269                strbuf_setlen(&msgbuf, 0);
1270                shown = 1;
1271
1272                if (!graph_is_commit_finished(graph))
1273                        putchar('\n');
1274                else
1275                        break;
1276        }
1277        strbuf_release(&msgbuf);
1278
1279        return shown;
1280}
1281
1282
1283static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)
1284{
1285        char *p;
1286
1287        if (!graph) {
1288                fwrite(sb->buf, sizeof(char), sb->len, stdout);
1289                return;
1290        }
1291
1292        /*
1293         * Print the strbuf line by line,
1294         * and display the graph info before each line but the first.
1295         */
1296        p = sb->buf;
1297        while (p) {
1298                size_t len;
1299                char *next_p = strchr(p, '\n');
1300                if (next_p) {
1301                        next_p++;
1302                        len = next_p - p;
1303                } else {
1304                        len = (sb->buf + sb->len) - p;
1305                }
1306                fwrite(p, sizeof(char), len, stdout);
1307                if (next_p && *next_p != '\0')
1308                        graph_show_oneline(graph);
1309                p = next_p;
1310        }
1311}
1312
1313void graph_show_commit_msg(struct git_graph *graph,
1314                           struct strbuf const *sb)
1315{
1316        int newline_terminated;
1317
1318        if (!graph) {
1319                /*
1320                 * If there's no graph, just print the message buffer.
1321                 *
1322                 * The message buffer for CMIT_FMT_ONELINE and
1323                 * CMIT_FMT_USERFORMAT are already missing a terminating
1324                 * newline.  All of the other formats should have it.
1325                 */
1326                fwrite(sb->buf, sizeof(char), sb->len, stdout);
1327                return;
1328        }
1329
1330        newline_terminated = (sb->len && sb->buf[sb->len - 1] == '\n');
1331
1332        /*
1333         * Show the commit message
1334         */
1335        graph_show_strbuf(graph, sb);
1336
1337        /*
1338         * If there is more output needed for this commit, show it now
1339         */
1340        if (!graph_is_commit_finished(graph)) {
1341                /*
1342                 * If sb doesn't have a terminating newline, print one now,
1343                 * so we can start the remainder of the graph output on a
1344                 * new line.
1345                 */
1346                if (!newline_terminated)
1347                        putchar('\n');
1348
1349                graph_show_remainder(graph);
1350
1351                /*
1352                 * If sb ends with a newline, our output should too.
1353                 */
1354                if (newline_terminated)
1355                        putchar('\n');
1356        }
1357}