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