graph.con commit Merge branch 'jk/maint-pass-c-config-in-env' (6b948a7)
   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         * If revs->left_right is set, print '<' for commits that
 802         * come from the left side, and '>' for commits from the right
 803         * side.
 804         */
 805        if (graph->revs && graph->revs->left_right) {
 806                if (graph->commit->object.flags & SYMMETRIC_LEFT)
 807                        strbuf_addch(sb, '<');
 808                else
 809                        strbuf_addch(sb, '>');
 810                return;
 811        }
 812
 813        /*
 814         * Print '*' in all other cases
 815         */
 816        strbuf_addch(sb, '*');
 817}
 818
 819/*
 820 * Draw an octopus merge and return the number of characters written.
 821 */
 822static int graph_draw_octopus_merge(struct git_graph *graph,
 823                                    struct strbuf *sb)
 824{
 825        /*
 826         * Here dashless_commits represents the number of parents
 827         * which don't need to have dashes (because their edges fit
 828         * neatly under the commit).
 829         */
 830        const int dashless_commits = 2;
 831        int col_num, i;
 832        int num_dashes =
 833                ((graph->num_parents - dashless_commits) * 2) - 1;
 834        for (i = 0; i < num_dashes; i++) {
 835                col_num = (i / 2) + dashless_commits;
 836                strbuf_write_column(sb, &graph->new_columns[col_num], '-');
 837        }
 838        col_num = (i / 2) + dashless_commits;
 839        strbuf_write_column(sb, &graph->new_columns[col_num], '.');
 840        return num_dashes + 1;
 841}
 842
 843static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 844{
 845        int seen_this = 0;
 846        int i, chars_written;
 847
 848        /*
 849         * Output the row containing this commit
 850         * Iterate up to and including graph->num_columns,
 851         * since the current commit may not be in any of the existing
 852         * columns.  (This happens when the current commit doesn't have any
 853         * children that we have already processed.)
 854         */
 855        seen_this = 0;
 856        chars_written = 0;
 857        for (i = 0; i <= graph->num_columns; i++) {
 858                struct column *col = &graph->columns[i];
 859                struct commit *col_commit;
 860                if (i == graph->num_columns) {
 861                        if (seen_this)
 862                                break;
 863                        col_commit = graph->commit;
 864                } else {
 865                        col_commit = graph->columns[i].commit;
 866                }
 867
 868                if (col_commit == graph->commit) {
 869                        seen_this = 1;
 870                        graph_output_commit_char(graph, sb);
 871                        chars_written++;
 872
 873                        if (graph->num_parents > 2)
 874                                chars_written += graph_draw_octopus_merge(graph,
 875                                                                          sb);
 876                } else if (seen_this && (graph->num_parents > 2)) {
 877                        strbuf_write_column(sb, col, '\\');
 878                        chars_written++;
 879                } else if (seen_this && (graph->num_parents == 2)) {
 880                        /*
 881                         * This is a 2-way merge commit.
 882                         * There is no GRAPH_PRE_COMMIT stage for 2-way
 883                         * merges, so this is the first line of output
 884                         * for this commit.  Check to see what the previous
 885                         * line of output was.
 886                         *
 887                         * If it was GRAPH_POST_MERGE, the branch line
 888                         * coming into this commit may have been '\',
 889                         * and not '|' or '/'.  If so, output the branch
 890                         * line as '\' on this line, instead of '|'.  This
 891                         * makes the output look nicer.
 892                         */
 893                        if (graph->prev_state == GRAPH_POST_MERGE &&
 894                            graph->prev_commit_index < i)
 895                                strbuf_write_column(sb, col, '\\');
 896                        else
 897                                strbuf_write_column(sb, col, '|');
 898                        chars_written++;
 899                } else {
 900                        strbuf_write_column(sb, col, '|');
 901                        chars_written++;
 902                }
 903                strbuf_addch(sb, ' ');
 904                chars_written++;
 905        }
 906
 907        graph_pad_horizontally(graph, sb, chars_written);
 908
 909        /*
 910         * Update graph->state
 911         */
 912        if (graph->num_parents > 1)
 913                graph_update_state(graph, GRAPH_POST_MERGE);
 914        else if (graph_is_mapping_correct(graph))
 915                graph_update_state(graph, GRAPH_PADDING);
 916        else
 917                graph_update_state(graph, GRAPH_COLLAPSING);
 918}
 919
 920static struct column *find_new_column_by_commit(struct git_graph *graph,
 921                                                struct commit *commit)
 922{
 923        int i;
 924        for (i = 0; i < graph->num_new_columns; i++) {
 925                if (graph->new_columns[i].commit == commit)
 926                        return &graph->new_columns[i];
 927        }
 928        return NULL;
 929}
 930
 931static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
 932{
 933        int seen_this = 0;
 934        int i, j, chars_written;
 935
 936        /*
 937         * Output the post-merge row
 938         */
 939        chars_written = 0;
 940        for (i = 0; i <= graph->num_columns; i++) {
 941                struct column *col = &graph->columns[i];
 942                struct commit *col_commit;
 943                if (i == graph->num_columns) {
 944                        if (seen_this)
 945                                break;
 946                        col_commit = graph->commit;
 947                } else {
 948                        col_commit = col->commit;
 949                }
 950
 951                if (col_commit == graph->commit) {
 952                        /*
 953                         * Since the current commit is a merge find
 954                         * the columns for the parent commits in
 955                         * new_columns and use those to format the
 956                         * edges.
 957                         */
 958                        struct commit_list *parents = NULL;
 959                        struct column *par_column;
 960                        seen_this = 1;
 961                        parents = first_interesting_parent(graph);
 962                        assert(parents);
 963                        par_column = find_new_column_by_commit(graph, parents->item);
 964                        assert(par_column);
 965
 966                        strbuf_write_column(sb, par_column, '|');
 967                        chars_written++;
 968                        for (j = 0; j < graph->num_parents - 1; j++) {
 969                                parents = next_interesting_parent(graph, parents);
 970                                assert(parents);
 971                                par_column = find_new_column_by_commit(graph, parents->item);
 972                                assert(par_column);
 973                                strbuf_write_column(sb, par_column, '\\');
 974                                strbuf_addch(sb, ' ');
 975                        }
 976                        chars_written += j * 2;
 977                } else if (seen_this) {
 978                        strbuf_write_column(sb, col, '\\');
 979                        strbuf_addch(sb, ' ');
 980                        chars_written += 2;
 981                } else {
 982                        strbuf_write_column(sb, col, '|');
 983                        strbuf_addch(sb, ' ');
 984                        chars_written += 2;
 985                }
 986        }
 987
 988        graph_pad_horizontally(graph, sb, chars_written);
 989
 990        /*
 991         * Update graph->state
 992         */
 993        if (graph_is_mapping_correct(graph))
 994                graph_update_state(graph, GRAPH_PADDING);
 995        else
 996                graph_update_state(graph, GRAPH_COLLAPSING);
 997}
 998
 999static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
1000{
1001        int i;
1002        int *tmp_mapping;
1003        short used_horizontal = 0;
1004        int horizontal_edge = -1;
1005        int horizontal_edge_target = -1;
1006
1007        /*
1008         * Clear out the new_mapping array
1009         */
1010        for (i = 0; i < graph->mapping_size; i++)
1011                graph->new_mapping[i] = -1;
1012
1013        for (i = 0; i < graph->mapping_size; i++) {
1014                int target = graph->mapping[i];
1015                if (target < 0)
1016                        continue;
1017
1018                /*
1019                 * Since update_columns() always inserts the leftmost
1020                 * column first, each branch's target location should
1021                 * always be either its current location or to the left of
1022                 * its current location.
1023                 *
1024                 * We never have to move branches to the right.  This makes
1025                 * the graph much more legible, since whenever branches
1026                 * cross, only one is moving directions.
1027                 */
1028                assert(target * 2 <= i);
1029
1030                if (target * 2 == i) {
1031                        /*
1032                         * This column is already in the
1033                         * correct place
1034                         */
1035                        assert(graph->new_mapping[i] == -1);
1036                        graph->new_mapping[i] = target;
1037                } else if (graph->new_mapping[i - 1] < 0) {
1038                        /*
1039                         * Nothing is to the left.
1040                         * Move to the left by one
1041                         */
1042                        graph->new_mapping[i - 1] = target;
1043                        /*
1044                         * If there isn't already an edge moving horizontally
1045                         * select this one.
1046                         */
1047                        if (horizontal_edge == -1) {
1048                                int j;
1049                                horizontal_edge = i;
1050                                horizontal_edge_target = target;
1051                                /*
1052                                 * The variable target is the index of the graph
1053                                 * column, and therefore target*2+3 is the
1054                                 * actual screen column of the first horizontal
1055                                 * line.
1056                                 */
1057                                for (j = (target * 2)+3; j < (i - 2); j += 2)
1058                                        graph->new_mapping[j] = target;
1059                        }
1060                } else if (graph->new_mapping[i - 1] == target) {
1061                        /*
1062                         * There is a branch line to our left
1063                         * already, and it is our target.  We
1064                         * combine with this line, since we share
1065                         * the same parent commit.
1066                         *
1067                         * We don't have to add anything to the
1068                         * output or new_mapping, since the
1069                         * existing branch line has already taken
1070                         * care of it.
1071                         */
1072                } else {
1073                        /*
1074                         * There is a branch line to our left,
1075                         * but it isn't our target.  We need to
1076                         * cross over it.
1077                         *
1078                         * The space just to the left of this
1079                         * branch should always be empty.
1080                         *
1081                         * The branch to the left of that space
1082                         * should be our eventual target.
1083                         */
1084                        assert(graph->new_mapping[i - 1] > target);
1085                        assert(graph->new_mapping[i - 2] < 0);
1086                        assert(graph->new_mapping[i - 3] == target);
1087                        graph->new_mapping[i - 2] = target;
1088                        /*
1089                         * Mark this branch as the horizontal edge to
1090                         * prevent any other edges from moving
1091                         * horizontally.
1092                         */
1093                        if (horizontal_edge == -1)
1094                                horizontal_edge = i;
1095                }
1096        }
1097
1098        /*
1099         * The new mapping may be 1 smaller than the old mapping
1100         */
1101        if (graph->new_mapping[graph->mapping_size - 1] < 0)
1102                graph->mapping_size--;
1103
1104        /*
1105         * Output out a line based on the new mapping info
1106         */
1107        for (i = 0; i < graph->mapping_size; i++) {
1108                int target = graph->new_mapping[i];
1109                if (target < 0)
1110                        strbuf_addch(sb, ' ');
1111                else if (target * 2 == i)
1112                        strbuf_write_column(sb, &graph->new_columns[target], '|');
1113                else if (target == horizontal_edge_target &&
1114                         i != horizontal_edge - 1) {
1115                                /*
1116                                 * Set the mappings for all but the
1117                                 * first segment to -1 so that they
1118                                 * won't continue into the next line.
1119                                 */
1120                                if (i != (target * 2)+3)
1121                                        graph->new_mapping[i] = -1;
1122                                used_horizontal = 1;
1123                        strbuf_write_column(sb, &graph->new_columns[target], '_');
1124                } else {
1125                        if (used_horizontal && i < horizontal_edge)
1126                                graph->new_mapping[i] = -1;
1127                        strbuf_write_column(sb, &graph->new_columns[target], '/');
1128
1129                }
1130        }
1131
1132        graph_pad_horizontally(graph, sb, graph->mapping_size);
1133
1134        /*
1135         * Swap mapping and new_mapping
1136         */
1137        tmp_mapping = graph->mapping;
1138        graph->mapping = graph->new_mapping;
1139        graph->new_mapping = tmp_mapping;
1140
1141        /*
1142         * If graph->mapping indicates that all of the branch lines
1143         * are already in the correct positions, we are done.
1144         * Otherwise, we need to collapse some branch lines together.
1145         */
1146        if (graph_is_mapping_correct(graph))
1147                graph_update_state(graph, GRAPH_PADDING);
1148}
1149
1150int graph_next_line(struct git_graph *graph, struct strbuf *sb)
1151{
1152        switch (graph->state) {
1153        case GRAPH_PADDING:
1154                graph_output_padding_line(graph, sb);
1155                return 0;
1156        case GRAPH_SKIP:
1157                graph_output_skip_line(graph, sb);
1158                return 0;
1159        case GRAPH_PRE_COMMIT:
1160                graph_output_pre_commit_line(graph, sb);
1161                return 0;
1162        case GRAPH_COMMIT:
1163                graph_output_commit_line(graph, sb);
1164                return 1;
1165        case GRAPH_POST_MERGE:
1166                graph_output_post_merge_line(graph, sb);
1167                return 0;
1168        case GRAPH_COLLAPSING:
1169                graph_output_collapsing_line(graph, sb);
1170                return 0;
1171        }
1172
1173        assert(0);
1174        return 0;
1175}
1176
1177static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
1178{
1179        int i, j;
1180
1181        if (graph->state != GRAPH_COMMIT) {
1182                graph_next_line(graph, sb);
1183                return;
1184        }
1185
1186        /*
1187         * Output the row containing this commit
1188         * Iterate up to and including graph->num_columns,
1189         * since the current commit may not be in any of the existing
1190         * columns.  (This happens when the current commit doesn't have any
1191         * children that we have already processed.)
1192         */
1193        for (i = 0; i < graph->num_columns; i++) {
1194                struct column *col = &graph->columns[i];
1195                struct commit *col_commit = col->commit;
1196                if (col_commit == graph->commit) {
1197                        strbuf_write_column(sb, col, '|');
1198
1199                        if (graph->num_parents < 3)
1200                                strbuf_addch(sb, ' ');
1201                        else {
1202                                int num_spaces = ((graph->num_parents - 2) * 2);
1203                                for (j = 0; j < num_spaces; j++)
1204                                        strbuf_addch(sb, ' ');
1205                        }
1206                } else {
1207                        strbuf_write_column(sb, col, '|');
1208                        strbuf_addch(sb, ' ');
1209                }
1210        }
1211
1212        graph_pad_horizontally(graph, sb, graph->num_columns);
1213
1214        /*
1215         * Update graph->prev_state since we have output a padding line
1216         */
1217        graph->prev_state = GRAPH_PADDING;
1218}
1219
1220int graph_is_commit_finished(struct git_graph const *graph)
1221{
1222        return (graph->state == GRAPH_PADDING);
1223}
1224
1225void graph_show_commit(struct git_graph *graph)
1226{
1227        struct strbuf msgbuf = STRBUF_INIT;
1228        int shown_commit_line = 0;
1229
1230        if (!graph)
1231                return;
1232
1233        while (!shown_commit_line) {
1234                shown_commit_line = graph_next_line(graph, &msgbuf);
1235                fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1236                if (!shown_commit_line)
1237                        putchar('\n');
1238                strbuf_setlen(&msgbuf, 0);
1239        }
1240
1241        strbuf_release(&msgbuf);
1242}
1243
1244void graph_show_oneline(struct git_graph *graph)
1245{
1246        struct strbuf msgbuf = STRBUF_INIT;
1247
1248        if (!graph)
1249                return;
1250
1251        graph_next_line(graph, &msgbuf);
1252        fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1253        strbuf_release(&msgbuf);
1254}
1255
1256void graph_show_padding(struct git_graph *graph)
1257{
1258        struct strbuf msgbuf = STRBUF_INIT;
1259
1260        if (!graph)
1261                return;
1262
1263        graph_padding_line(graph, &msgbuf);
1264        fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1265        strbuf_release(&msgbuf);
1266}
1267
1268int graph_show_remainder(struct git_graph *graph)
1269{
1270        struct strbuf msgbuf = STRBUF_INIT;
1271        int shown = 0;
1272
1273        if (!graph)
1274                return 0;
1275
1276        if (graph_is_commit_finished(graph))
1277                return 0;
1278
1279        for (;;) {
1280                graph_next_line(graph, &msgbuf);
1281                fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
1282                strbuf_setlen(&msgbuf, 0);
1283                shown = 1;
1284
1285                if (!graph_is_commit_finished(graph))
1286                        putchar('\n');
1287                else
1288                        break;
1289        }
1290        strbuf_release(&msgbuf);
1291
1292        return shown;
1293}
1294
1295
1296static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)
1297{
1298        char *p;
1299
1300        if (!graph) {
1301                fwrite(sb->buf, sizeof(char), sb->len, stdout);
1302                return;
1303        }
1304
1305        /*
1306         * Print the strbuf line by line,
1307         * and display the graph info before each line but the first.
1308         */
1309        p = sb->buf;
1310        while (p) {
1311                size_t len;
1312                char *next_p = strchr(p, '\n');
1313                if (next_p) {
1314                        next_p++;
1315                        len = next_p - p;
1316                } else {
1317                        len = (sb->buf + sb->len) - p;
1318                }
1319                fwrite(p, sizeof(char), len, stdout);
1320                if (next_p && *next_p != '\0')
1321                        graph_show_oneline(graph);
1322                p = next_p;
1323        }
1324}
1325
1326void graph_show_commit_msg(struct git_graph *graph,
1327                           struct strbuf const *sb)
1328{
1329        int newline_terminated;
1330
1331        if (!graph) {
1332                /*
1333                 * If there's no graph, just print the message buffer.
1334                 *
1335                 * The message buffer for CMIT_FMT_ONELINE and
1336                 * CMIT_FMT_USERFORMAT are already missing a terminating
1337                 * newline.  All of the other formats should have it.
1338                 */
1339                fwrite(sb->buf, sizeof(char), sb->len, stdout);
1340                return;
1341        }
1342
1343        newline_terminated = (sb->len && sb->buf[sb->len - 1] == '\n');
1344
1345        /*
1346         * Show the commit message
1347         */
1348        graph_show_strbuf(graph, sb);
1349
1350        /*
1351         * If there is more output needed for this commit, show it now
1352         */
1353        if (!graph_is_commit_finished(graph)) {
1354                /*
1355                 * If sb doesn't have a terminating newline, print one now,
1356                 * so we can start the remainder of the graph output on a
1357                 * new line.
1358                 */
1359                if (!newline_terminated)
1360                        putchar('\n');
1361
1362                graph_show_remainder(graph);
1363
1364                /*
1365                 * If sb ends with a newline, our output should too.
1366                 */
1367                if (newline_terminated)
1368                        putchar('\n');
1369        }
1370}