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