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