1#include "cache.h" 2#include "commit.h" 3#include "graph.h" 4#include "diff.h" 5#include "revision.h" 6 7/* 8 * TODO: 9 * - Add colors to the graph. 10 * Pick a color for each column, and print all characters 11 * in that column with the specified color. 12 * 13 * - Limit the number of columns, similar to the way gitk does. 14 * If we reach more than a specified number of columns, omit 15 * sections of some columns. 16 * 17 * - The output during the GRAPH_PRE_COMMIT and GRAPH_COLLAPSING states 18 * could be made more compact by printing horizontal lines, instead of 19 * long diagonal lines. For example, during collapsing, something like 20 * this: instead of this: 21 * | | | | | | | | | | 22 * | |_|_|/ | | | |/ 23 * |/| | | | | |/| 24 * | | | | | |/| | 25 * |/| | | 26 * | | | | 27 * 28 * If there are several parallel diagonal lines, they will need to be 29 * replaced with horizontal lines on subsequent rows. 30 */ 31 32struct column { 33 /* 34 * The parent commit of this column. 35 */ 36 struct commit *commit; 37 /* 38 * XXX: Once we add support for colors, struct column could also 39 * contain the color of its branch line. 40 */ 41}; 42 43enum graph_state { 44 GRAPH_PADDING, 45 GRAPH_SKIP, 46 GRAPH_PRE_COMMIT, 47 GRAPH_COMMIT, 48 GRAPH_POST_MERGE, 49 GRAPH_COLLAPSING 50}; 51 52struct git_graph { 53 /* 54 * The commit currently being processed 55 */ 56 struct commit *commit; 57 /* The rev-info used for the current traversal */ 58 struct rev_info *revs; 59 /* 60 * The number of interesting parents that this commit has. 61 * 62 * Note that this is not the same as the actual number of parents. 63 * This count excludes parents that won't be printed in the graph 64 * output, as determined by graph_is_interesting(). 65 */ 66 int num_parents; 67 /* 68 * The width of the graph output for this commit. 69 * All rows for this commit are padded to this width, so that 70 * messages printed after the graph output are aligned. 71 */ 72 int width; 73 /* 74 * The next expansion row to print 75 * when state is GRAPH_PRE_COMMIT 76 */ 77 int expansion_row; 78 /* 79 * The current output state. 80 * This tells us what kind of line graph_next_line() should output. 81 */ 82 enum graph_state state; 83 /* 84 * The output state for the previous line of output. 85 * This is primarily used to determine how the first merge line 86 * should appear, based on the last line of the previous commit. 87 */ 88 enum graph_state prev_state; 89 /* 90 * The index of the column that refers to this commit. 91 * 92 * If none of the incoming columns refer to this commit, 93 * this will be equal to num_columns. 94 */ 95 int commit_index; 96 /* 97 * The commit_index for the previously displayed commit. 98 * 99 * This is used to determine how the first line of a merge 100 * graph output should appear, based on the last line of the 101 * previous commit. 102 */ 103 int prev_commit_index; 104 /* 105 * The maximum number of columns that can be stored in the columns 106 * and new_columns arrays. This is also half the number of entries 107 * that can be stored in the mapping and new_mapping arrays. 108 */ 109 int column_capacity; 110 /* 111 * The number of columns (also called "branch lines" in some places) 112 */ 113 int num_columns; 114 /* 115 * The number of columns in the new_columns array 116 */ 117 int num_new_columns; 118 /* 119 * The number of entries in the mapping array 120 */ 121 int mapping_size; 122 /* 123 * The column state before we output the current commit. 124 */ 125 struct column *columns; 126 /* 127 * The new column state after we output the current commit. 128 * Only valid when state is GRAPH_COLLAPSING. 129 */ 130 struct column *new_columns; 131 /* 132 * An array that tracks the current state of each 133 * character in the output line during state GRAPH_COLLAPSING. 134 * Each entry is -1 if this character is empty, or a non-negative 135 * integer if the character contains a branch line. The value of 136 * the integer indicates the target position for this branch line. 137 * (I.e., this array maps the current column positions to their 138 * desired positions.) 139 * 140 * The maximum capacity of this array is always 141 * sizeof(int) * 2 * column_capacity. 142 */ 143 int *mapping; 144 /* 145 * A temporary array for computing the next mapping state 146 * while we are outputting a mapping line. This is stored as part 147 * of the git_graph simply so we don't have to allocate a new 148 * temporary array each time we have to output a collapsing line. 149 */ 150 int *new_mapping; 151}; 152 153struct git_graph *graph_init(struct rev_info *opt) 154{ 155 struct git_graph *graph = xmalloc(sizeof(struct git_graph)); 156 graph->commit = NULL; 157 graph->revs = opt; 158 graph->num_parents = 0; 159 graph->expansion_row = 0; 160 graph->state = GRAPH_PADDING; 161 graph->prev_state = GRAPH_PADDING; 162 graph->commit_index = 0; 163 graph->prev_commit_index = 0; 164 graph->num_columns = 0; 165 graph->num_new_columns = 0; 166 graph->mapping_size = 0; 167 168 /* 169 * Allocate a reasonably large default number of columns 170 * We'll automatically grow columns later if we need more room. 171 */ 172 graph->column_capacity = 30; 173 graph->columns = xmalloc(sizeof(struct column) * 174 graph->column_capacity); 175 graph->new_columns = xmalloc(sizeof(struct column) * 176 graph->column_capacity); 177 graph->mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity); 178 graph->new_mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity); 179 180 return graph; 181} 182 183void graph_release(struct git_graph *graph) 184{ 185 free(graph->columns); 186 free(graph->new_columns); 187 free(graph->mapping); 188 free(graph); 189} 190 191static void graph_update_state(struct git_graph *graph, enum graph_state s) 192{ 193 graph->prev_state = graph->state; 194 graph->state = s; 195} 196 197static void graph_ensure_capacity(struct git_graph *graph, int num_columns) 198{ 199 if (graph->column_capacity >= num_columns) 200 return; 201 202 do { 203 graph->column_capacity *= 2; 204 } while (graph->column_capacity < num_columns); 205 206 graph->columns = xrealloc(graph->columns, 207 sizeof(struct column) * 208 graph->column_capacity); 209 graph->new_columns = xrealloc(graph->new_columns, 210 sizeof(struct column) * 211 graph->column_capacity); 212 graph->mapping = xrealloc(graph->mapping, 213 sizeof(int) * 2 * graph->column_capacity); 214 graph->new_mapping = xrealloc(graph->new_mapping, 215 sizeof(int) * 2 * graph->column_capacity); 216} 217 218/* 219 * Returns 1 if the commit will be printed in the graph output, 220 * and 0 otherwise. 221 */ 222static int graph_is_interesting(struct git_graph *graph, struct commit *commit) 223{ 224 /* 225 * If revs->boundary is set, commits whose children have 226 * been shown are always interesting, even if they have the 227 * UNINTERESTING or TREESAME flags set. 228 */ 229 if (graph->revs && graph->revs->boundary) { 230 if (commit->object.flags & CHILD_SHOWN) 231 return 1; 232 } 233 234 /* 235 * Uninteresting and pruned commits won't be printed 236 */ 237 return (commit->object.flags & (UNINTERESTING | TREESAME)) ? 0 : 1; 238} 239 240static struct commit_list *next_interesting_parent(struct git_graph *graph, 241 struct commit_list *orig) 242{ 243 struct commit_list *list; 244 245 /* 246 * If revs->first_parent_only is set, only the first 247 * parent is interesting. None of the others are. 248 */ 249 if (graph->revs->first_parent_only) 250 return NULL; 251 252 /* 253 * Return the next interesting commit after orig 254 */ 255 for (list = orig->next; list; list = list->next) { 256 if (graph_is_interesting(graph, list->item)) 257 return list; 258 } 259 260 return NULL; 261} 262 263static struct commit_list *first_interesting_parent(struct git_graph *graph) 264{ 265 struct commit_list *parents = graph->commit->parents; 266 267 /* 268 * If this commit has no parents, ignore it 269 */ 270 if (!parents) 271 return NULL; 272 273 /* 274 * If the first parent is interesting, return it 275 */ 276 if (graph_is_interesting(graph, parents->item)) 277 return parents; 278 279 /* 280 * Otherwise, call next_interesting_parent() to get 281 * the next interesting parent 282 */ 283 return next_interesting_parent(graph, parents); 284} 285 286static void graph_insert_into_new_columns(struct git_graph *graph, 287 struct commit *commit, 288 int *mapping_index) 289{ 290 int i; 291 292 /* 293 * If the commit is already in the new_columns list, we don't need to 294 * add it. Just update the mapping correctly. 295 */ 296 for (i = 0; i < graph->num_new_columns; i++) { 297 if (graph->new_columns[i].commit == commit) { 298 graph->mapping[*mapping_index] = i; 299 *mapping_index += 2; 300 return; 301 } 302 } 303 304 /* 305 * This commit isn't already in new_columns. Add it. 306 */ 307 graph->new_columns[graph->num_new_columns].commit = commit; 308 graph->mapping[*mapping_index] = graph->num_new_columns; 309 *mapping_index += 2; 310 graph->num_new_columns++; 311} 312 313static void graph_update_width(struct git_graph *graph, 314 int is_commit_in_existing_columns) 315{ 316 /* 317 * Compute the width needed to display the graph for this commit. 318 * This is the maximum width needed for any row. All other rows 319 * will be padded to this width. 320 * 321 * Compute the number of columns in the widest row: 322 * Count each existing column (graph->num_columns), and each new 323 * column added by this commit. 324 */ 325 int max_cols = graph->num_columns + graph->num_parents; 326 327 /* 328 * Even if the current commit has no parents to be printed, it 329 * still takes up a column for itself. 330 */ 331 if (graph->num_parents < 1) 332 max_cols++; 333 334 /* 335 * We added a column for the the current commit as part of 336 * graph->num_parents. If the current commit was already in 337 * graph->columns, then we have double counted it. 338 */ 339 if (is_commit_in_existing_columns) 340 max_cols--; 341 342 /* 343 * Each column takes up 2 spaces 344 */ 345 graph->width = max_cols * 2; 346} 347 348static void graph_update_columns(struct git_graph *graph) 349{ 350 struct commit_list *parent; 351 struct column *tmp_columns; 352 int max_new_columns; 353 int mapping_idx; 354 int i, seen_this, is_commit_in_columns; 355 356 /* 357 * Swap graph->columns with graph->new_columns 358 * graph->columns contains the state for the previous commit, 359 * and new_columns now contains the state for our commit. 360 * 361 * We'll re-use the old columns array as storage to compute the new 362 * columns list for the commit after this one. 363 */ 364 tmp_columns = graph->columns; 365 graph->columns = graph->new_columns; 366 graph->num_columns = graph->num_new_columns; 367 368 graph->new_columns = tmp_columns; 369 graph->num_new_columns = 0; 370 371 /* 372 * Now update new_columns and mapping with the information for the 373 * commit after this one. 374 * 375 * First, make sure we have enough room. At most, there will 376 * be graph->num_columns + graph->num_parents columns for the next 377 * commit. 378 */ 379 max_new_columns = graph->num_columns + graph->num_parents; 380 graph_ensure_capacity(graph, max_new_columns); 381 382 /* 383 * Clear out graph->mapping 384 */ 385 graph->mapping_size = 2 * max_new_columns; 386 for (i = 0; i < graph->mapping_size; i++) 387 graph->mapping[i] = -1; 388 389 /* 390 * Populate graph->new_columns and graph->mapping 391 * 392 * Some of the parents of this commit may already be in 393 * graph->columns. If so, graph->new_columns should only contain a 394 * single entry for each such commit. graph->mapping should 395 * contain information about where each current branch line is 396 * supposed to end up after the collapsing is performed. 397 */ 398 seen_this = 0; 399 mapping_idx = 0; 400 is_commit_in_columns = 1; 401 for (i = 0; i <= graph->num_columns; i++) { 402 struct commit *col_commit; 403 if (i == graph->num_columns) { 404 if (seen_this) 405 break; 406 is_commit_in_columns = 0; 407 col_commit = graph->commit; 408 } else { 409 col_commit = graph->columns[i].commit; 410 } 411 412 if (col_commit == graph->commit) { 413 int old_mapping_idx = mapping_idx; 414 seen_this = 1; 415 graph->commit_index = i; 416 for (parent = first_interesting_parent(graph); 417 parent; 418 parent = next_interesting_parent(graph, parent)) { 419 graph_insert_into_new_columns(graph, 420 parent->item, 421 &mapping_idx); 422 } 423 /* 424 * We always need to increment mapping_idx by at 425 * least 2, even if it has no interesting parents. 426 * The current commit always takes up at least 2 427 * spaces. 428 */ 429 if (mapping_idx == old_mapping_idx) 430 mapping_idx += 2; 431 } else { 432 graph_insert_into_new_columns(graph, col_commit, 433 &mapping_idx); 434 } 435 } 436 437 /* 438 * Shrink mapping_size to be the minimum necessary 439 */ 440 while (graph->mapping_size > 1 && 441 graph->mapping[graph->mapping_size - 1] < 0) 442 graph->mapping_size--; 443 444 /* 445 * Compute graph->width for this commit 446 */ 447 graph_update_width(graph, is_commit_in_columns); 448} 449 450void graph_update(struct git_graph *graph, struct commit *commit) 451{ 452 struct commit_list *parent; 453 454 /* 455 * Set the new commit 456 */ 457 graph->commit = commit; 458 459 /* 460 * Count how many interesting parents this commit has 461 */ 462 graph->num_parents = 0; 463 for (parent = first_interesting_parent(graph); 464 parent; 465 parent = next_interesting_parent(graph, parent)) 466 { 467 graph->num_parents++; 468 } 469 470 /* 471 * Store the old commit_index in prev_commit_index. 472 * graph_update_columns() will update graph->commit_index for this 473 * commit. 474 */ 475 graph->prev_commit_index = graph->commit_index; 476 477 /* 478 * Call graph_update_columns() to update 479 * columns, new_columns, and mapping. 480 */ 481 graph_update_columns(graph); 482 483 graph->expansion_row = 0; 484 485 /* 486 * Update graph->state. 487 * Note that we don't call graph_update_state() here, since 488 * we don't want to update graph->prev_state. No line for 489 * graph->state was ever printed. 490 * 491 * If the previous commit didn't get to the GRAPH_PADDING state, 492 * it never finished its output. Goto GRAPH_SKIP, to print out 493 * a line to indicate that portion of the graph is missing. 494 * 495 * If there are 3 or more parents, we may need to print extra rows 496 * before the commit, to expand the branch lines around it and make 497 * room for it. We need to do this only if there is a branch row 498 * (or more) to the right of this commit. 499 * 500 * If there are less than 3 parents, we can immediately print the 501 * commit line. 502 */ 503 if (graph->state != GRAPH_PADDING) 504 graph->state = GRAPH_SKIP; 505 else if (graph->num_parents >= 3 && 506 graph->commit_index < (graph->num_columns - 1)) 507 graph->state = GRAPH_PRE_COMMIT; 508 else 509 graph->state = GRAPH_COMMIT; 510} 511 512static int graph_is_mapping_correct(struct git_graph *graph) 513{ 514 int i; 515 516 /* 517 * The mapping is up to date if each entry is at its target, 518 * or is 1 greater than its target. 519 * (If it is 1 greater than the target, '/' will be printed, so it 520 * will look correct on the next row.) 521 */ 522 for (i = 0; i < graph->mapping_size; i++) { 523 int target = graph->mapping[i]; 524 if (target < 0) 525 continue; 526 if (target == (i / 2)) 527 continue; 528 return 0; 529 } 530 531 return 1; 532} 533 534static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb) 535{ 536 /* 537 * Add additional spaces to the end of the strbuf, so that all 538 * lines for a particular commit have the same width. 539 * 540 * This way, fields printed to the right of the graph will remain 541 * aligned for the entire commit. 542 */ 543 int extra; 544 if (sb->len >= graph->width) 545 return; 546 547 extra = graph->width - sb->len; 548 strbuf_addf(sb, "%*s", (int) extra, ""); 549} 550 551static void graph_output_padding_line(struct git_graph *graph, 552 struct strbuf *sb) 553{ 554 int i; 555 556 /* 557 * We could conceivable be called with a NULL commit 558 * if our caller has a bug, and invokes graph_next_line() 559 * immediately after graph_init(), without first calling 560 * graph_update(). Return without outputting anything in this 561 * case. 562 */ 563 if (!graph->commit) 564 return; 565 566 /* 567 * Output a padding row, that leaves all branch lines unchanged 568 */ 569 for (i = 0; i < graph->num_new_columns; i++) { 570 strbuf_addstr(sb, "| "); 571 } 572 573 graph_pad_horizontally(graph, sb); 574} 575 576static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb) 577{ 578 /* 579 * Output an ellipsis to indicate that a portion 580 * of the graph is missing. 581 */ 582 strbuf_addstr(sb, "..."); 583 graph_pad_horizontally(graph, sb); 584 585 if (graph->num_parents >= 3 && 586 graph->commit_index < (graph->num_columns - 1)) 587 graph_update_state(graph, GRAPH_PRE_COMMIT); 588 else 589 graph_update_state(graph, GRAPH_COMMIT); 590} 591 592static void graph_output_pre_commit_line(struct git_graph *graph, 593 struct strbuf *sb) 594{ 595 int num_expansion_rows; 596 int i, seen_this; 597 598 /* 599 * This function formats a row that increases the space around a commit 600 * with multiple parents, to make room for it. It should only be 601 * called when there are 3 or more parents. 602 * 603 * We need 2 extra rows for every parent over 2. 604 */ 605 assert(graph->num_parents >= 3); 606 num_expansion_rows = (graph->num_parents - 2) * 2; 607 608 /* 609 * graph->expansion_row tracks the current expansion row we are on. 610 * It should be in the range [0, num_expansion_rows - 1] 611 */ 612 assert(0 <= graph->expansion_row && 613 graph->expansion_row < num_expansion_rows); 614 615 /* 616 * Output the row 617 */ 618 seen_this = 0; 619 for (i = 0; i < graph->num_columns; i++) { 620 struct column *col = &graph->columns[i]; 621 if (col->commit == graph->commit) { 622 seen_this = 1; 623 strbuf_addf(sb, "| %*s", graph->expansion_row, ""); 624 } else if (seen_this && (graph->expansion_row == 0)) { 625 /* 626 * This is the first line of the pre-commit output. 627 * If the previous commit was a merge commit and 628 * ended in the GRAPH_POST_MERGE state, all branch 629 * lines after graph->prev_commit_index were 630 * printed as "\" on the previous line. Continue 631 * to print them as "\" on this line. Otherwise, 632 * print the branch lines as "|". 633 */ 634 if (graph->prev_state == GRAPH_POST_MERGE && 635 graph->prev_commit_index < i) 636 strbuf_addstr(sb, "\\ "); 637 else 638 strbuf_addstr(sb, "| "); 639 } else if (seen_this && (graph->expansion_row > 0)) { 640 strbuf_addstr(sb, "\\ "); 641 } else { 642 strbuf_addstr(sb, "| "); 643 } 644 } 645 646 graph_pad_horizontally(graph, sb); 647 648 /* 649 * Increment graph->expansion_row, 650 * and move to state GRAPH_COMMIT if necessary 651 */ 652 graph->expansion_row++; 653 if (graph->expansion_row >= num_expansion_rows) 654 graph_update_state(graph, GRAPH_COMMIT); 655} 656 657static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb) 658{ 659 /* 660 * For boundary commits, print 'o' 661 * (We should only see boundary commits when revs->boundary is set.) 662 */ 663 if (graph->commit->object.flags & BOUNDARY) { 664 assert(graph->revs->boundary); 665 strbuf_addch(sb, 'o'); 666 return; 667 } 668 669 /* 670 * If revs->left_right is set, print '<' for commits that 671 * come from the left side, and '>' for commits from the right 672 * side. 673 */ 674 if (graph->revs && graph->revs->left_right) { 675 if (graph->commit->object.flags & SYMMETRIC_LEFT) 676 strbuf_addch(sb, '<'); 677 else 678 strbuf_addch(sb, '>'); 679 return; 680 } 681 682 /* 683 * Print '*' in all other cases 684 */ 685 strbuf_addch(sb, '*'); 686} 687 688void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) 689{ 690 int seen_this = 0; 691 int i, j; 692 693 /* 694 * Output the row containing this commit 695 * Iterate up to and including graph->num_columns, 696 * since the current commit may not be in any of the existing 697 * columns. (This happens when the current commit doesn't have any 698 * children that we have already processed.) 699 */ 700 seen_this = 0; 701 for (i = 0; i <= graph->num_columns; i++) { 702 struct commit *col_commit; 703 if (i == graph->num_columns) { 704 if (seen_this) 705 break; 706 col_commit = graph->commit; 707 } else { 708 col_commit = graph->columns[i].commit; 709 } 710 711 if (col_commit == graph->commit) { 712 seen_this = 1; 713 graph_output_commit_char(graph, sb); 714 715 if (graph->num_parents < 3) 716 strbuf_addch(sb, ' '); 717 else { 718 int num_dashes = 719 ((graph->num_parents - 2) * 2) - 1; 720 for (j = 0; j < num_dashes; j++) 721 strbuf_addch(sb, '-'); 722 strbuf_addstr(sb, ". "); 723 } 724 } else if (seen_this && (graph->num_parents > 2)) { 725 strbuf_addstr(sb, "\\ "); 726 } else if (seen_this && (graph->num_parents == 2)) { 727 /* 728 * This is a 2-way merge commit. 729 * There is no GRAPH_PRE_COMMIT stage for 2-way 730 * merges, so this is the first line of output 731 * for this commit. Check to see what the previous 732 * line of output was. 733 * 734 * If it was GRAPH_POST_MERGE, the branch line 735 * coming into this commit may have been '\', 736 * and not '|' or '/'. If so, output the branch 737 * line as '\' on this line, instead of '|'. This 738 * makes the output look nicer. 739 */ 740 if (graph->prev_state == GRAPH_POST_MERGE && 741 graph->prev_commit_index < i) 742 strbuf_addstr(sb, "\\ "); 743 else 744 strbuf_addstr(sb, "| "); 745 } else { 746 strbuf_addstr(sb, "| "); 747 } 748 } 749 750 graph_pad_horizontally(graph, sb); 751 752 /* 753 * Update graph->state 754 */ 755 if (graph->num_parents > 1) 756 graph_update_state(graph, GRAPH_POST_MERGE); 757 else if (graph_is_mapping_correct(graph)) 758 graph_update_state(graph, GRAPH_PADDING); 759 else 760 graph_update_state(graph, GRAPH_COLLAPSING); 761} 762 763void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb) 764{ 765 int seen_this = 0; 766 int i, j; 767 768 /* 769 * Output the post-merge row 770 */ 771 for (i = 0; i <= graph->num_columns; i++) { 772 struct commit *col_commit; 773 if (i == graph->num_columns) { 774 if (seen_this) 775 break; 776 col_commit = graph->commit; 777 } else { 778 col_commit = graph->columns[i].commit; 779 } 780 781 if (col_commit == graph->commit) { 782 seen_this = 1; 783 strbuf_addch(sb, '|'); 784 for (j = 0; j < graph->num_parents - 1; j++) 785 strbuf_addstr(sb, "\\ "); 786 } else if (seen_this) { 787 strbuf_addstr(sb, "\\ "); 788 } else { 789 strbuf_addstr(sb, "| "); 790 } 791 } 792 793 graph_pad_horizontally(graph, sb); 794 795 /* 796 * Update graph->state 797 */ 798 if (graph_is_mapping_correct(graph)) 799 graph_update_state(graph, GRAPH_PADDING); 800 else 801 graph_update_state(graph, GRAPH_COLLAPSING); 802} 803 804void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb) 805{ 806 int i; 807 int *tmp_mapping; 808 809 /* 810 * Clear out the new_mapping array 811 */ 812 for (i = 0; i < graph->mapping_size; i++) 813 graph->new_mapping[i] = -1; 814 815 for (i = 0; i < graph->mapping_size; i++) { 816 int target = graph->mapping[i]; 817 if (target < 0) 818 continue; 819 820 /* 821 * Since update_columns() always inserts the leftmost 822 * column first, each branch's target location should 823 * always be either its current location or to the left of 824 * its current location. 825 * 826 * We never have to move branches to the right. This makes 827 * the graph much more legible, since whenever branches 828 * cross, only one is moving directions. 829 */ 830 assert(target * 2 <= i); 831 832 if (target * 2 == i) { 833 /* 834 * This column is already in the 835 * correct place 836 */ 837 assert(graph->new_mapping[i] == -1); 838 graph->new_mapping[i] = target; 839 } else if (graph->new_mapping[i - 1] < 0) { 840 /* 841 * Nothing is to the left. 842 * Move to the left by one 843 */ 844 graph->new_mapping[i - 1] = target; 845 } else if (graph->new_mapping[i - 1] == target) { 846 /* 847 * There is a branch line to our left 848 * already, and it is our target. We 849 * combine with this line, since we share 850 * the same parent commit. 851 * 852 * We don't have to add anything to the 853 * output or new_mapping, since the 854 * existing branch line has already taken 855 * care of it. 856 */ 857 } else { 858 /* 859 * There is a branch line to our left, 860 * but it isn't our target. We need to 861 * cross over it. 862 * 863 * The space just to the left of this 864 * branch should always be empty. 865 */ 866 assert(graph->new_mapping[i - 1] > target); 867 assert(graph->new_mapping[i - 2] < 0); 868 graph->new_mapping[i - 2] = target; 869 } 870 } 871 872 /* 873 * The new mapping may be 1 smaller than the old mapping 874 */ 875 if (graph->new_mapping[graph->mapping_size - 1] < 0) 876 graph->mapping_size--; 877 878 /* 879 * Output out a line based on the new mapping info 880 */ 881 for (i = 0; i < graph->mapping_size; i++) { 882 int target = graph->new_mapping[i]; 883 if (target < 0) 884 strbuf_addch(sb, ' '); 885 else if (target * 2 == i) 886 strbuf_addch(sb, '|'); 887 else 888 strbuf_addch(sb, '/'); 889 } 890 891 graph_pad_horizontally(graph, sb); 892 893 /* 894 * Swap mapping and new_mapping 895 */ 896 tmp_mapping = graph->mapping; 897 graph->mapping = graph->new_mapping; 898 graph->new_mapping = tmp_mapping; 899 900 /* 901 * If graph->mapping indicates that all of the branch lines 902 * are already in the correct positions, we are done. 903 * Otherwise, we need to collapse some branch lines together. 904 */ 905 if (graph_is_mapping_correct(graph)) 906 graph_update_state(graph, GRAPH_PADDING); 907} 908 909int graph_next_line(struct git_graph *graph, struct strbuf *sb) 910{ 911 switch (graph->state) { 912 case GRAPH_PADDING: 913 graph_output_padding_line(graph, sb); 914 return 0; 915 case GRAPH_SKIP: 916 graph_output_skip_line(graph, sb); 917 return 0; 918 case GRAPH_PRE_COMMIT: 919 graph_output_pre_commit_line(graph, sb); 920 return 0; 921 case GRAPH_COMMIT: 922 graph_output_commit_line(graph, sb); 923 return 1; 924 case GRAPH_POST_MERGE: 925 graph_output_post_merge_line(graph, sb); 926 return 0; 927 case GRAPH_COLLAPSING: 928 graph_output_collapsing_line(graph, sb); 929 return 0; 930 } 931 932 assert(0); 933 return 0; 934} 935 936void graph_padding_line(struct git_graph *graph, struct strbuf *sb) 937{ 938 int i, j; 939 940 if (graph->state != GRAPH_COMMIT) { 941 graph_next_line(graph, sb); 942 return; 943 } 944 945 /* 946 * Output the row containing this commit 947 * Iterate up to and including graph->num_columns, 948 * since the current commit may not be in any of the existing 949 * columns. (This happens when the current commit doesn't have any 950 * children that we have already processed.) 951 */ 952 for (i = 0; i < graph->num_columns; i++) { 953 struct commit *col_commit = graph->columns[i].commit; 954 if (col_commit == graph->commit) { 955 strbuf_addch(sb, '|'); 956 957 if (graph->num_parents < 3) 958 strbuf_addch(sb, ' '); 959 else { 960 int num_spaces = ((graph->num_parents - 2) * 2); 961 for (j = 0; j < num_spaces; j++) 962 strbuf_addch(sb, ' '); 963 } 964 } else { 965 strbuf_addstr(sb, "| "); 966 } 967 } 968 969 graph_pad_horizontally(graph, sb); 970 971 /* 972 * Update graph->prev_state since we have output a padding line 973 */ 974 graph->prev_state = GRAPH_PADDING; 975} 976 977int graph_is_commit_finished(struct git_graph const *graph) 978{ 979 return (graph->state == GRAPH_PADDING); 980} 981 982void graph_show_commit(struct git_graph *graph) 983{ 984 struct strbuf msgbuf; 985 int shown_commit_line = 0; 986 987 if (!graph) 988 return; 989 990 strbuf_init(&msgbuf, 0); 991 992 while (!shown_commit_line) { 993 shown_commit_line = graph_next_line(graph, &msgbuf); 994 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout); 995 if (!shown_commit_line) 996 putchar('\n'); 997 strbuf_setlen(&msgbuf, 0); 998 } 9991000 strbuf_release(&msgbuf);1001}10021003void graph_show_oneline(struct git_graph *graph)1004{1005 struct strbuf msgbuf;10061007 if (!graph)1008 return;10091010 strbuf_init(&msgbuf, 0);1011 graph_next_line(graph, &msgbuf);1012 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);1013 strbuf_release(&msgbuf);1014}10151016void graph_show_padding(struct git_graph *graph)1017{1018 struct strbuf msgbuf;10191020 if (!graph)1021 return;10221023 strbuf_init(&msgbuf, 0);1024 graph_padding_line(graph, &msgbuf);1025 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);1026 strbuf_release(&msgbuf);1027}10281029int graph_show_remainder(struct git_graph *graph)1030{1031 struct strbuf msgbuf;1032 int shown = 0;10331034 if (!graph)1035 return 0;10361037 if (graph_is_commit_finished(graph))1038 return 0;10391040 strbuf_init(&msgbuf, 0);1041 for (;;) {1042 graph_next_line(graph, &msgbuf);1043 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);1044 strbuf_setlen(&msgbuf, 0);1045 shown = 1;10461047 if (!graph_is_commit_finished(graph))1048 putchar('\n');1049 else1050 break;1051 }1052 strbuf_release(&msgbuf);10531054 return shown;1055}105610571058void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)1059{1060 char *p;10611062 if (!graph) {1063 fwrite(sb->buf, sizeof(char), sb->len, stdout);1064 return;1065 }10661067 /*1068 * Print the strbuf line by line,1069 * and display the graph info before each line but the first.1070 */1071 p = sb->buf;1072 while (p) {1073 size_t len;1074 char *next_p = strchr(p, '\n');1075 if (next_p) {1076 next_p++;1077 len = next_p - p;1078 } else {1079 len = (sb->buf + sb->len) - p;1080 }1081 fwrite(p, sizeof(char), len, stdout);1082 if (next_p && *next_p != '\0')1083 graph_show_oneline(graph);1084 p = next_p;1085 }1086}10871088void graph_show_commit_msg(struct git_graph *graph,1089 struct strbuf const *sb)1090{1091 int newline_terminated;10921093 if (!graph) {1094 /*1095 * If there's no graph, just print the message buffer.1096 *1097 * The message buffer for CMIT_FMT_ONELINE and1098 * CMIT_FMT_USERFORMAT are already missing a terminating1099 * newline. All of the other formats should have it.1100 */1101 fwrite(sb->buf, sizeof(char), sb->len, stdout);1102 return;1103 }11041105 newline_terminated = (sb->len && sb->buf[sb->len - 1] == '\n');11061107 /*1108 * Show the commit message1109 */1110 graph_show_strbuf(graph, sb);11111112 /*1113 * If there is more output needed for this commit, show it now1114 */1115 if (!graph_is_commit_finished(graph)) {1116 /*1117 * If sb doesn't have a terminating newline, print one now,1118 * so we can start the remainder of the graph output on a1119 * new line.1120 */1121 if (!newline_terminated)1122 putchar('\n');11231124 graph_show_remainder(graph);11251126 /*1127 * If sb ends with a newline, our output should too.1128 */1129 if (newline_terminated)1130 putchar('\n');1131 }1132}