git.oblomov.eu Git - git/blob - graph.c

   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  */
  17 static 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  */
  32 static 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
  41 struct 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
  53 enum graph_state {
  54         GRAPH_PADDING,
  55         GRAPH_SKIP,
  56         GRAPH_PRE_COMMIT,
  57         GRAPH_COMMIT,
  58         GRAPH_POST_MERGE,
  59         GRAPH_COLLAPSING
  60 };
  61
  62 static const char **column_colors;
  63 static unsigned short column_colors_max;
  64
  65 void graph_set_column_colors(const char **colors, unsigned short colors_max)
  66 {
  67         column_colors = colors;
  68         column_colors_max = colors_max;
  69 }
  70
  71 static const char *column_get_color_code(unsigned short color)
  72 {
  73         return column_colors[color];
  74 }
  75
  76 static 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
  86 struct 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
 192 static 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
 206 struct 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
 253 static 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
 259 static 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  */
 278 static 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
 297 static 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
 320 static 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
 343 static 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  */
 353 static 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
 359 static 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
 370 static 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
 398 static 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
 433 static 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
 544 void 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
 606 static 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
 628 static 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
 646 static 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
 673 int graph_width(struct git_graph *graph)
 674 {
 675         return graph->width;
 676 }
 677
 678
 679 static 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
 695 static 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
 769 static 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  */
 790 static 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
 811 static 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
 888 static 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
 899 static 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
 967 static 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
1118 int 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
1145 static 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
1178 int graph_is_commit_finished(struct git_graph const *graph)
1179 {
1180         return (graph->state == GRAPH_PADDING);
1181 }
1182
1183 void 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
1213 void 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
1225 void 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
1237 int 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
1266 static 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
1297 void 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 }