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

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