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