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 */ 36struct 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 */ 56struct commit *commit; 57/* The rev-info used for the current traversal */ 58struct 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 */ 66int 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 */ 72int width; 73/* 74 * The next expansion row to print 75 * when state is GRAPH_PRE_COMMIT 76 */ 77int expansion_row; 78/* 79 * The current output state. 80 * This tells us what kind of line graph_next_line() should output. 81 */ 82enum 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 */ 88enum 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 */ 95int 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 */ 103int 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 */ 109int column_capacity; 110/* 111 * The number of columns (also called "branch lines" in some places) 112 */ 113int num_columns; 114/* 115 * The number of columns in the new_columns array 116 */ 117int num_new_columns; 118/* 119 * The number of entries in the mapping array 120 */ 121int mapping_size; 122/* 123 * The column state before we output the current commit. 124 */ 125struct column *columns; 126/* 127 * The new column state after we output the current commit. 128 * Only valid when state is GRAPH_COLLAPSING. 129 */ 130struct 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 */ 143int*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 */ 150int*new_mapping; 151}; 152 153struct git_graph *graph_init(struct rev_info *opt) 154{ 155struct 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 180return graph; 181} 182 183voidgraph_release(struct git_graph *graph) 184{ 185free(graph->columns); 186free(graph->new_columns); 187free(graph->mapping); 188free(graph); 189} 190 191static voidgraph_update_state(struct git_graph *graph,enum graph_state s) 192{ 193 graph->prev_state = graph->state; 194 graph->state = s; 195} 196 197static voidgraph_ensure_capacity(struct git_graph *graph,int num_columns) 198{ 199if(graph->column_capacity >= num_columns) 200return; 201 202do{ 203 graph->column_capacity *=2; 204}while(graph->column_capacity < num_columns); 205 206 graph->columns =xrealloc(graph->columns, 207sizeof(struct column) * 208 graph->column_capacity); 209 graph->new_columns =xrealloc(graph->new_columns, 210sizeof(struct column) * 211 graph->column_capacity); 212 graph->mapping =xrealloc(graph->mapping, 213sizeof(int) *2* graph->column_capacity); 214 graph->new_mapping =xrealloc(graph->new_mapping, 215sizeof(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 intgraph_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 */ 229if(graph->revs && graph->revs->boundary) { 230if(commit->object.flags & CHILD_SHOWN) 231return1; 232} 233 234/* 235 * Uninteresting and pruned commits won't be printed 236 */ 237return(commit->object.flags & (UNINTERESTING | TREESAME)) ?0:1; 238} 239 240static struct commit_list *next_interesting_parent(struct git_graph *graph, 241struct commit_list *orig) 242{ 243struct 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 */ 249if(graph->revs->first_parent_only) 250return NULL; 251 252/* 253 * Return the next interesting commit after orig 254 */ 255for(list = orig->next; list; list = list->next) { 256if(graph_is_interesting(graph, list->item)) 257return list; 258} 259 260return NULL; 261} 262 263static struct commit_list *first_interesting_parent(struct git_graph *graph) 264{ 265struct commit_list *parents = graph->commit->parents; 266 267/* 268 * If this commit has no parents, ignore it 269 */ 270if(!parents) 271return NULL; 272 273/* 274 * If the first parent is interesting, return it 275 */ 276if(graph_is_interesting(graph, parents->item)) 277return parents; 278 279/* 280 * Otherwise, call next_interesting_parent() to get 281 * the next interesting parent 282 */ 283returnnext_interesting_parent(graph, parents); 284} 285 286static voidgraph_insert_into_new_columns(struct git_graph *graph, 287struct commit *commit, 288int*mapping_index) 289{ 290int 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 */ 296for(i =0; i < graph->num_new_columns; i++) { 297if(graph->new_columns[i].commit == commit) { 298 graph->mapping[*mapping_index] = i; 299*mapping_index +=2; 300return; 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 voidgraph_update_width(struct git_graph *graph, 314int 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 */ 325int 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 */ 331if(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 */ 339if(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 voidgraph_update_columns(struct git_graph *graph) 349{ 350struct commit_list *parent; 351struct column *tmp_columns; 352int max_new_columns; 353int mapping_idx; 354int 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; 380graph_ensure_capacity(graph, max_new_columns); 381 382/* 383 * Clear out graph->mapping 384 */ 385 graph->mapping_size =2* max_new_columns; 386for(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; 401for(i =0; i <= graph->num_columns; i++) { 402struct commit *col_commit; 403if(i == graph->num_columns) { 404if(seen_this) 405break; 406 is_commit_in_columns =0; 407 col_commit = graph->commit; 408}else{ 409 col_commit = graph->columns[i].commit; 410} 411 412if(col_commit == graph->commit) { 413int old_mapping_idx = mapping_idx; 414 seen_this =1; 415 graph->commit_index = i; 416for(parent =first_interesting_parent(graph); 417 parent; 418 parent =next_interesting_parent(graph, parent)) { 419graph_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 */ 429if(mapping_idx == old_mapping_idx) 430 mapping_idx +=2; 431}else{ 432graph_insert_into_new_columns(graph, col_commit, 433&mapping_idx); 434} 435} 436 437/* 438 * Shrink mapping_size to be the minimum necessary 439 */ 440while(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 */ 447graph_update_width(graph, is_commit_in_columns); 448} 449 450voidgraph_update(struct git_graph *graph,struct commit *commit) 451{ 452struct 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; 463for(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 */ 481graph_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 */ 503if(graph->state != GRAPH_PADDING) 504 graph->state = GRAPH_SKIP; 505else if(graph->num_parents >=3&& 506 graph->commit_index < (graph->num_columns -1)) 507 graph->state = GRAPH_PRE_COMMIT; 508else 509 graph->state = GRAPH_COMMIT; 510} 511 512static intgraph_is_mapping_correct(struct git_graph *graph) 513{ 514int 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 */ 522for(i =0; i < graph->mapping_size; i++) { 523int target = graph->mapping[i]; 524if(target <0) 525continue; 526if(target == (i /2)) 527continue; 528return0; 529} 530 531return1; 532} 533 534static voidgraph_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 */ 543int extra; 544if(sb->len >= graph->width) 545return; 546 547 extra = graph->width - sb->len; 548strbuf_addf(sb,"%*s", (int) extra,""); 549} 550 551static voidgraph_output_padding_line(struct git_graph *graph, 552struct strbuf *sb) 553{ 554int 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 */ 563if(!graph->commit) 564return; 565 566/* 567 * Output a padding row, that leaves all branch lines unchanged 568 */ 569for(i =0; i < graph->num_new_columns; i++) { 570strbuf_addstr(sb,"| "); 571} 572 573graph_pad_horizontally(graph, sb); 574} 575 576static voidgraph_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 */ 582strbuf_addstr(sb,"..."); 583graph_pad_horizontally(graph, sb); 584 585if(graph->num_parents >=3&& 586 graph->commit_index < (graph->num_columns -1)) 587graph_update_state(graph, GRAPH_PRE_COMMIT); 588else 589graph_update_state(graph, GRAPH_COMMIT); 590} 591 592static voidgraph_output_pre_commit_line(struct git_graph *graph, 593struct strbuf *sb) 594{ 595int num_expansion_rows; 596int 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 */ 605assert(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 */ 612assert(0<= graph->expansion_row && 613 graph->expansion_row < num_expansion_rows); 614 615/* 616 * Output the row 617 */ 618 seen_this =0; 619for(i =0; i < graph->num_columns; i++) { 620struct column *col = &graph->columns[i]; 621if(col->commit == graph->commit) { 622 seen_this =1; 623strbuf_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 */ 634if(graph->prev_state == GRAPH_POST_MERGE && 635 graph->prev_commit_index < i) 636strbuf_addstr(sb,"\\"); 637else 638strbuf_addstr(sb,"| "); 639}else if(seen_this && (graph->expansion_row >0)) { 640strbuf_addstr(sb,"\\"); 641}else{ 642strbuf_addstr(sb,"| "); 643} 644} 645 646graph_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++; 653if(graph->expansion_row >= num_expansion_rows) 654graph_update_state(graph, GRAPH_COMMIT); 655} 656 657static voidgraph_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 */ 663if(graph->commit->object.flags & BOUNDARY) { 664assert(graph->revs->boundary); 665strbuf_addch(sb,'o'); 666return; 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 */ 674if(graph->revs && graph->revs->left_right) { 675if(graph->commit->object.flags & SYMMETRIC_LEFT) 676strbuf_addch(sb,'<'); 677else 678strbuf_addch(sb,'>'); 679return; 680} 681 682/* 683 * Print 'M' for merge commits 684 * 685 * Note that we don't check graph->num_parents to determine if the 686 * commit is a merge, since that only tracks the number of 687 * "interesting" parents. We want to print 'M' for merge commits 688 * even if they have less than 2 interesting parents. 689 */ 690if(graph->commit->parents != NULL && 691 graph->commit->parents->next != NULL) { 692strbuf_addch(sb,'M'); 693return; 694} 695 696/* 697 * Print '*' in all other cases 698 */ 699strbuf_addch(sb,'*'); 700} 701 702voidgraph_output_commit_line(struct git_graph *graph,struct strbuf *sb) 703{ 704int seen_this =0; 705int i, j; 706 707/* 708 * Output the row containing this commit 709 * Iterate up to and including graph->num_columns, 710 * since the current commit may not be in any of the existing 711 * columns. (This happens when the current commit doesn't have any 712 * children that we have already processed.) 713 */ 714 seen_this =0; 715for(i =0; i <= graph->num_columns; i++) { 716struct commit *col_commit; 717if(i == graph->num_columns) { 718if(seen_this) 719break; 720 col_commit = graph->commit; 721}else{ 722 col_commit = graph->columns[i].commit; 723} 724 725if(col_commit == graph->commit) { 726 seen_this =1; 727graph_output_commit_char(graph, sb); 728 729if(graph->num_parents <3) 730strbuf_addch(sb,' '); 731else{ 732int num_dashes = 733((graph->num_parents -2) *2) -1; 734for(j =0; j < num_dashes; j++) 735strbuf_addch(sb,'-'); 736strbuf_addstr(sb,". "); 737} 738}else if(seen_this && (graph->num_parents >2)) { 739strbuf_addstr(sb,"\\"); 740}else if(seen_this && (graph->num_parents ==2)) { 741/* 742 * This is a 2-way merge commit. 743 * There is no GRAPH_PRE_COMMIT stage for 2-way 744 * merges, so this is the first line of output 745 * for this commit. Check to see what the previous 746 * line of output was. 747 * 748 * If it was GRAPH_POST_MERGE, the branch line 749 * coming into this commit may have been '\', 750 * and not '|' or '/'. If so, output the branch 751 * line as '\' on this line, instead of '|'. This 752 * makes the output look nicer. 753 */ 754if(graph->prev_state == GRAPH_POST_MERGE && 755 graph->prev_commit_index < i) 756strbuf_addstr(sb,"\\"); 757else 758strbuf_addstr(sb,"| "); 759}else{ 760strbuf_addstr(sb,"| "); 761} 762} 763 764graph_pad_horizontally(graph, sb); 765 766/* 767 * Update graph->state 768 */ 769if(graph->num_parents >1) 770graph_update_state(graph, GRAPH_POST_MERGE); 771else if(graph_is_mapping_correct(graph)) 772graph_update_state(graph, GRAPH_PADDING); 773else 774graph_update_state(graph, GRAPH_COLLAPSING); 775} 776 777voidgraph_output_post_merge_line(struct git_graph *graph,struct strbuf *sb) 778{ 779int seen_this =0; 780int i, j; 781 782/* 783 * Output the post-merge row 784 */ 785for(i =0; i <= graph->num_columns; i++) { 786struct commit *col_commit; 787if(i == graph->num_columns) { 788if(seen_this) 789break; 790 col_commit = graph->commit; 791}else{ 792 col_commit = graph->columns[i].commit; 793} 794 795if(col_commit == graph->commit) { 796 seen_this =1; 797strbuf_addch(sb,'|'); 798for(j =0; j < graph->num_parents -1; j++) 799strbuf_addstr(sb,"\\"); 800}else if(seen_this) { 801strbuf_addstr(sb,"\\"); 802}else{ 803strbuf_addstr(sb,"| "); 804} 805} 806 807graph_pad_horizontally(graph, sb); 808 809/* 810 * Update graph->state 811 */ 812if(graph_is_mapping_correct(graph)) 813graph_update_state(graph, GRAPH_PADDING); 814else 815graph_update_state(graph, GRAPH_COLLAPSING); 816} 817 818voidgraph_output_collapsing_line(struct git_graph *graph,struct strbuf *sb) 819{ 820int i; 821int*tmp_mapping; 822 823/* 824 * Clear out the new_mapping array 825 */ 826for(i =0; i < graph->mapping_size; i++) 827 graph->new_mapping[i] = -1; 828 829for(i =0; i < graph->mapping_size; i++) { 830int target = graph->mapping[i]; 831if(target <0) 832continue; 833 834/* 835 * Since update_columns() always inserts the leftmost 836 * column first, each branch's target location should 837 * always be either its current location or to the left of 838 * its current location. 839 * 840 * We never have to move branches to the right. This makes 841 * the graph much more legible, since whenever branches 842 * cross, only one is moving directions. 843 */ 844assert(target *2<= i); 845 846if(target *2== i) { 847/* 848 * This column is already in the 849 * correct place 850 */ 851assert(graph->new_mapping[i] == -1); 852 graph->new_mapping[i] = target; 853}else if(graph->new_mapping[i -1] <0) { 854/* 855 * Nothing is to the left. 856 * Move to the left by one 857 */ 858 graph->new_mapping[i -1] = target; 859}else if(graph->new_mapping[i -1] == target) { 860/* 861 * There is a branch line to our left 862 * already, and it is our target. We 863 * combine with this line, since we share 864 * the same parent commit. 865 * 866 * We don't have to add anything to the 867 * output or new_mapping, since the 868 * existing branch line has already taken 869 * care of it. 870 */ 871}else{ 872/* 873 * There is a branch line to our left, 874 * but it isn't our target. We need to 875 * cross over it. 876 * 877 * The space just to the left of this 878 * branch should always be empty. 879 */ 880assert(graph->new_mapping[i -1] > target); 881assert(graph->new_mapping[i -2] <0); 882 graph->new_mapping[i -2] = target; 883} 884} 885 886/* 887 * The new mapping may be 1 smaller than the old mapping 888 */ 889if(graph->new_mapping[graph->mapping_size -1] <0) 890 graph->mapping_size--; 891 892/* 893 * Output out a line based on the new mapping info 894 */ 895for(i =0; i < graph->mapping_size; i++) { 896int target = graph->new_mapping[i]; 897if(target <0) 898strbuf_addch(sb,' '); 899else if(target *2== i) 900strbuf_addch(sb,'|'); 901else 902strbuf_addch(sb,'/'); 903} 904 905graph_pad_horizontally(graph, sb); 906 907/* 908 * Swap mapping and new_mapping 909 */ 910 tmp_mapping = graph->mapping; 911 graph->mapping = graph->new_mapping; 912 graph->new_mapping = tmp_mapping; 913 914/* 915 * If graph->mapping indicates that all of the branch lines 916 * are already in the correct positions, we are done. 917 * Otherwise, we need to collapse some branch lines together. 918 */ 919if(graph_is_mapping_correct(graph)) 920graph_update_state(graph, GRAPH_PADDING); 921} 922 923intgraph_next_line(struct git_graph *graph,struct strbuf *sb) 924{ 925switch(graph->state) { 926case GRAPH_PADDING: 927graph_output_padding_line(graph, sb); 928return0; 929case GRAPH_SKIP: 930graph_output_skip_line(graph, sb); 931return0; 932case GRAPH_PRE_COMMIT: 933graph_output_pre_commit_line(graph, sb); 934return0; 935case GRAPH_COMMIT: 936graph_output_commit_line(graph, sb); 937return1; 938case GRAPH_POST_MERGE: 939graph_output_post_merge_line(graph, sb); 940return0; 941case GRAPH_COLLAPSING: 942graph_output_collapsing_line(graph, sb); 943return0; 944} 945 946assert(0); 947return0; 948} 949 950voidgraph_padding_line(struct git_graph *graph,struct strbuf *sb) 951{ 952int i, j; 953 954if(graph->state != GRAPH_COMMIT) { 955graph_next_line(graph, sb); 956return; 957} 958 959/* 960 * Output the row containing this commit 961 * Iterate up to and including graph->num_columns, 962 * since the current commit may not be in any of the existing 963 * columns. (This happens when the current commit doesn't have any 964 * children that we have already processed.) 965 */ 966for(i =0; i < graph->num_columns; i++) { 967struct commit *col_commit = graph->columns[i].commit; 968if(col_commit == graph->commit) { 969strbuf_addch(sb,'|'); 970 971if(graph->num_parents <3) 972strbuf_addch(sb,' '); 973else{ 974int num_spaces = ((graph->num_parents -2) *2); 975for(j =0; j < num_spaces; j++) 976strbuf_addch(sb,' '); 977} 978}else{ 979strbuf_addstr(sb,"| "); 980} 981} 982 983graph_pad_horizontally(graph, sb); 984 985/* 986 * Update graph->prev_state since we have output a padding line 987 */ 988 graph->prev_state = GRAPH_PADDING; 989} 990 991intgraph_is_commit_finished(struct git_graph const*graph) 992{ 993return(graph->state == GRAPH_PADDING); 994} 995 996voidgraph_show_commit(struct git_graph *graph) 997{ 998struct strbuf msgbuf; 999int shown_commit_line =0;10001001if(!graph)1002return;10031004strbuf_init(&msgbuf,0);10051006while(!shown_commit_line) {1007 shown_commit_line =graph_next_line(graph, &msgbuf);1008fwrite(msgbuf.buf,sizeof(char), msgbuf.len, stdout);1009if(!shown_commit_line)1010putchar('\n');1011strbuf_setlen(&msgbuf,0);1012}10131014strbuf_release(&msgbuf);1015}10161017voidgraph_show_oneline(struct git_graph *graph)1018{1019struct strbuf msgbuf;10201021if(!graph)1022return;10231024strbuf_init(&msgbuf,0);1025graph_next_line(graph, &msgbuf);1026fwrite(msgbuf.buf,sizeof(char), msgbuf.len, stdout);1027strbuf_release(&msgbuf);1028}10291030voidgraph_show_padding(struct git_graph *graph)1031{1032struct strbuf msgbuf;10331034if(!graph)1035return;10361037strbuf_init(&msgbuf,0);1038graph_padding_line(graph, &msgbuf);1039fwrite(msgbuf.buf,sizeof(char), msgbuf.len, stdout);1040strbuf_release(&msgbuf);1041}10421043intgraph_show_remainder(struct git_graph *graph)1044{1045struct strbuf msgbuf;1046int shown =0;10471048if(!graph)1049return0;10501051if(graph_is_commit_finished(graph))1052return0;10531054strbuf_init(&msgbuf,0);1055for(;;) {1056graph_next_line(graph, &msgbuf);1057fwrite(msgbuf.buf,sizeof(char), msgbuf.len, stdout);1058strbuf_setlen(&msgbuf,0);1059 shown =1;10601061if(!graph_is_commit_finished(graph))1062putchar('\n');1063else1064break;1065}1066strbuf_release(&msgbuf);10671068return shown;1069}107010711072voidgraph_show_strbuf(struct git_graph *graph,struct strbuf const*sb)1073{1074char*p;10751076if(!graph) {1077fwrite(sb->buf,sizeof(char), sb->len, stdout);1078return;1079}10801081/*1082 * Print the strbuf line by line,1083 * and display the graph info before each line but the first.1084 */1085 p = sb->buf;1086while(p) {1087size_t len;1088char*next_p =strchr(p,'\n');1089if(next_p) {1090 next_p++;1091 len = next_p - p;1092}else{1093 len = (sb->buf + sb->len) - p;1094}1095fwrite(p,sizeof(char), len, stdout);1096if(next_p && *next_p !='\0')1097graph_show_oneline(graph);1098 p = next_p;1099}1100}11011102voidgraph_show_commit_msg(struct git_graph *graph,1103struct strbuf const*sb)1104{1105int newline_terminated;11061107if(!graph) {1108/*1109 * If there's no graph, just print the message buffer.1110 *1111 * The message buffer for CMIT_FMT_ONELINE and1112 * CMIT_FMT_USERFORMAT are already missing a terminating1113 * newline. All of the other formats should have it.1114 */1115fwrite(sb->buf,sizeof(char), sb->len, stdout);1116return;1117}11181119 newline_terminated = (sb->len && sb->buf[sb->len -1] =='\n');11201121/*1122 * Show the commit message1123 */1124graph_show_strbuf(graph, sb);11251126/*1127 * If there is more output needed for this commit, show it now1128 */1129if(!graph_is_commit_finished(graph)) {1130/*1131 * If sb doesn't have a terminating newline, print one now,1132 * so we can start the remainder of the graph output on a1133 * new line.1134 */1135if(!newline_terminated)1136putchar('\n');11371138graph_show_remainder(graph);11391140/*1141 * If sb ends with a newline, our output should too.1142 */1143if(newline_terminated)1144putchar('\n');1145}1146}