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