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