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