diff options
Diffstat (limited to 'graph.c')
| -rw-r--r-- | graph.c | 664 |
1 files changed, 385 insertions, 279 deletions
@@ -34,6 +34,7 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb); * handle directly. It is assumed that this is the same file handle as the * file specified by the graph diff options. This is necessary so that * graph_show_strbuf can be called even with a NULL graph. + * If a NULL graph is supplied, the strbuf is printed as-is. */ static void graph_show_strbuf(struct git_graph *graph, FILE *file, @@ -112,14 +113,42 @@ static const char *column_get_color_code(unsigned short color) return column_colors[color]; } -static void strbuf_write_column(struct strbuf *sb, const struct column *c, - char col_char) +struct graph_line { + struct strbuf *buf; + size_t width; +}; + +static inline void graph_line_addch(struct graph_line *line, int c) +{ + strbuf_addch(line->buf, c); + line->width++; +} + +static inline void graph_line_addchars(struct graph_line *line, int c, size_t n) +{ + strbuf_addchars(line->buf, c, n); + line->width += n; +} + +static inline void graph_line_addstr(struct graph_line *line, const char *s) +{ + strbuf_addstr(line->buf, s); + line->width += strlen(s); +} + +static inline void graph_line_addcolor(struct graph_line *line, unsigned short color) +{ + strbuf_addstr(line->buf, column_get_color_code(color)); +} + +static void graph_line_write_column(struct graph_line *line, const struct column *c, + char col_char) { if (c->color < column_colors_max) - strbuf_addstr(sb, column_get_color_code(c->color)); - strbuf_addch(sb, col_char); + graph_line_addcolor(line, c->color); + graph_line_addch(line, col_char); if (c->color < column_colors_max) - strbuf_addstr(sb, column_get_color_code(column_colors_max)); + graph_line_addcolor(line, column_colors_max); } struct git_graph { @@ -175,9 +204,63 @@ struct git_graph { */ int prev_commit_index; /* + * Which layout variant to use to display merge commits. If the + * commit's first parent is known to be in a column to the left of the + * merge, then this value is 0 and we use the layout on the left. + * Otherwise, the value is 1 and the layout on the right is used. This + * field tells us how many columns the first parent occupies. + * + * 0) 1) + * + * | | | *-. | | *---. + * | |_|/|\ \ | | |\ \ \ + * |/| | | | | | | | | | * + */ + int merge_layout; + /* + * The number of columns added to the graph by the current commit. For + * 2-way and octopus merges, this is usually one less than the + * number of parents: + * + * | | | | | \ + * | * | | *---. \ + * | |\ \ | |\ \ \ \ + * | | | | | | | | | | + * + * num_parents: 2 num_parents: 4 + * edges_added: 1 edges_added: 3 + * + * For left-skewed merges, the first parent fuses with its neighbor and + * so one less column is added: + * + * | | | | | \ + * | * | | *-. \ + * |/| | |/|\ \ \ + * | | | | | | | | + * + * num_parents: 2 num_parents: 4 + * edges_added: 0 edges_added: 2 + * + * This number determines how edges to the right of the merge are + * displayed in commit and post-merge lines; if no columns have been + * added then a vertical line should be used where a right-tracking + * line would otherwise be used. + * + * | * \ | * | + * | |\ \ |/| | + * | | * \ | * | + */ + int edges_added; + /* + * The number of columns added by the previous commit, which is used to + * smooth edges appearing to the right of a commit in a commit line + * following a post-merge line. + */ + int prev_edges_added; + /* * The maximum number of columns that can be stored in the columns * and new_columns arrays. This is also half the number of entries - * that can be stored in the mapping and new_mapping arrays. + * that can be stored in the mapping and old_mapping arrays. */ int column_capacity; /* @@ -215,12 +298,12 @@ struct git_graph { */ int *mapping; /* - * A temporary array for computing the next mapping state - * while we are outputting a mapping line. This is stored as part - * of the git_graph simply so we don't have to allocate a new - * temporary array each time we have to output a collapsing line. + * A copy of the contents of the mapping array from the last commit, + * which we use to improve the display of columns that are tracking + * from right to left through a commit line. We also use this to + * avoid allocating a fresh array when we compute the next mapping. */ - int *new_mapping; + int *old_mapping; /* * The current default column color being used. This is * stored as an index into the array column_colors. @@ -285,6 +368,9 @@ struct git_graph *graph_init(struct rev_info *opt) graph->prev_state = GRAPH_PADDING; graph->commit_index = 0; graph->prev_commit_index = 0; + graph->merge_layout = 0; + graph->edges_added = 0; + graph->prev_edges_added = 0; graph->num_columns = 0; graph->num_new_columns = 0; graph->mapping_size = 0; @@ -303,7 +389,7 @@ struct git_graph *graph_init(struct rev_info *opt) ALLOC_ARRAY(graph->columns, graph->column_capacity); ALLOC_ARRAY(graph->new_columns, graph->column_capacity); ALLOC_ARRAY(graph->mapping, 2 * graph->column_capacity); - ALLOC_ARRAY(graph->new_mapping, 2 * graph->column_capacity); + ALLOC_ARRAY(graph->old_mapping, 2 * graph->column_capacity); /* * The diff output prefix callback, with this we can make @@ -333,7 +419,7 @@ static void graph_ensure_capacity(struct git_graph *graph, int num_columns) REALLOC_ARRAY(graph->columns, graph->column_capacity); REALLOC_ARRAY(graph->new_columns, graph->column_capacity); REALLOC_ARRAY(graph->mapping, graph->column_capacity * 2); - REALLOC_ARRAY(graph->new_mapping, graph->column_capacity * 2); + REALLOC_ARRAY(graph->old_mapping, graph->column_capacity * 2); } /* @@ -432,74 +518,76 @@ static unsigned short graph_find_commit_color(const struct git_graph *graph, return graph_get_current_column_color(graph); } -static void graph_insert_into_new_columns(struct git_graph *graph, - struct commit *commit, - int *mapping_index) +static int graph_find_new_column_by_commit(struct git_graph *graph, + struct commit *commit) { int i; - - /* - * If the commit is already in the new_columns list, we don't need to - * add it. Just update the mapping correctly. - */ for (i = 0; i < graph->num_new_columns; i++) { - if (graph->new_columns[i].commit == commit) { - graph->mapping[*mapping_index] = i; - *mapping_index += 2; - return; - } + if (graph->new_columns[i].commit == commit) + return i; } - - /* - * This commit isn't already in new_columns. Add it. - */ - graph->new_columns[graph->num_new_columns].commit = commit; - graph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit); - graph->mapping[*mapping_index] = graph->num_new_columns; - *mapping_index += 2; - graph->num_new_columns++; + return -1; } -static void graph_update_width(struct git_graph *graph, - int is_commit_in_existing_columns) +static void graph_insert_into_new_columns(struct git_graph *graph, + struct commit *commit, + int idx) { - /* - * Compute the width needed to display the graph for this commit. - * This is the maximum width needed for any row. All other rows - * will be padded to this width. - * - * Compute the number of columns in the widest row: - * Count each existing column (graph->num_columns), and each new - * column added by this commit. - */ - int max_cols = graph->num_columns + graph->num_parents; + int i = graph_find_new_column_by_commit(graph, commit); + int mapping_idx; /* - * Even if the current commit has no parents to be printed, it - * still takes up a column for itself. + * If the commit is not already in the new_columns array, then add it + * and record it as being in the final column. */ - if (graph->num_parents < 1) - max_cols++; + if (i < 0) { + i = graph->num_new_columns++; + graph->new_columns[i].commit = commit; + graph->new_columns[i].color = graph_find_commit_color(graph, commit); + } - /* - * We added a column for the current commit as part of - * graph->num_parents. If the current commit was already in - * graph->columns, then we have double counted it. - */ - if (is_commit_in_existing_columns) - max_cols--; + if (graph->num_parents > 1 && idx > -1 && graph->merge_layout == -1) { + /* + * If this is the first parent of a merge, choose a layout for + * the merge line based on whether the parent appears in a + * column to the left of the merge + */ + int dist, shift; - /* - * Each column takes up 2 spaces - */ - graph->width = max_cols * 2; + dist = idx - i; + shift = (dist > 1) ? 2 * dist - 3 : 1; + + graph->merge_layout = (dist > 0) ? 0 : 1; + graph->edges_added = graph->num_parents + graph->merge_layout - 2; + + mapping_idx = graph->width + (graph->merge_layout - 1) * shift; + graph->width += 2 * graph->merge_layout; + + } else if (graph->edges_added > 0 && i == graph->mapping[graph->width - 2]) { + /* + * If some columns have been added by a merge, but this commit + * was found in the last existing column, then adjust the + * numbers so that the two edges immediately join, i.e.: + * + * * | * | + * |\ \ => |\| + * | |/ | * + * | * + */ + mapping_idx = graph->width - 2; + graph->edges_added = -1; + } else { + mapping_idx = graph->width; + graph->width += 2; + } + + graph->mapping[mapping_idx] = i; } static void graph_update_columns(struct git_graph *graph) { struct commit_list *parent; int max_new_columns; - int mapping_idx; int i, seen_this, is_commit_in_columns; /* @@ -532,6 +620,10 @@ static void graph_update_columns(struct git_graph *graph) for (i = 0; i < graph->mapping_size; i++) graph->mapping[i] = -1; + graph->width = 0; + graph->prev_edges_added = graph->edges_added; + graph->edges_added = 0; + /* * Populate graph->new_columns and graph->mapping * @@ -542,7 +634,6 @@ static void graph_update_columns(struct git_graph *graph) * supposed to end up after the collapsing is performed. */ seen_this = 0; - mapping_idx = 0; is_commit_in_columns = 1; for (i = 0; i <= graph->num_columns; i++) { struct commit *col_commit; @@ -556,9 +647,9 @@ static void graph_update_columns(struct git_graph *graph) } if (col_commit == graph->commit) { - int old_mapping_idx = mapping_idx; seen_this = 1; graph->commit_index = i; + graph->merge_layout = -1; for (parent = first_interesting_parent(graph); parent; parent = next_interesting_parent(graph, parent)) { @@ -571,21 +662,18 @@ static void graph_update_columns(struct git_graph *graph) !is_commit_in_columns) { graph_increment_column_color(graph); } - graph_insert_into_new_columns(graph, - parent->item, - &mapping_idx); + graph_insert_into_new_columns(graph, parent->item, i); } /* - * We always need to increment mapping_idx by at + * We always need to increment graph->width by at * least 2, even if it has no interesting parents. * The current commit always takes up at least 2 * spaces. */ - if (mapping_idx == old_mapping_idx) - mapping_idx += 2; + if (graph->num_parents == 0) + graph->width += 2; } else { - graph_insert_into_new_columns(graph, col_commit, - &mapping_idx); + graph_insert_into_new_columns(graph, col_commit, -1); } } @@ -595,11 +683,43 @@ static void graph_update_columns(struct git_graph *graph) while (graph->mapping_size > 1 && graph->mapping[graph->mapping_size - 1] < 0) graph->mapping_size--; +} + +static int graph_num_dashed_parents(struct git_graph *graph) +{ + return graph->num_parents + graph->merge_layout - 3; +} +static int graph_num_expansion_rows(struct git_graph *graph) +{ /* - * Compute graph->width for this commit + * Normally, we need two expansion rows for each dashed parent line from + * an octopus merge: + * + * | * + * | |\ + * | | \ + * | | \ + * | *-. \ + * | |\ \ \ + * + * If the merge is skewed to the left, then its parents occupy one less + * column, and we don't need as many expansion rows to route around it; + * in some cases that means we don't need any expansion rows at all: + * + * | * + * | |\ + * | * \ + * |/|\ \ */ - graph_update_width(graph, is_commit_in_columns); + return graph_num_dashed_parents(graph) * 2; +} + +static int graph_needs_pre_commit_line(struct git_graph *graph) +{ + return graph->num_parents >= 3 && + graph->commit_index < (graph->num_columns - 1) && + graph->expansion_row < graph_num_expansion_rows(graph); } void graph_update(struct git_graph *graph, struct commit *commit) @@ -657,8 +777,7 @@ void graph_update(struct git_graph *graph, struct commit *commit) */ if (graph->state != GRAPH_PADDING) graph->state = GRAPH_SKIP; - else if (graph->num_parents >= 3 && - graph->commit_index < (graph->num_columns - 1)) + else if (graph_needs_pre_commit_line(graph)) graph->state = GRAPH_PRE_COMMIT; else graph->state = GRAPH_COMMIT; @@ -686,8 +805,7 @@ static int graph_is_mapping_correct(struct git_graph *graph) return 1; } -static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb, - int chars_written) +static void graph_pad_horizontally(struct git_graph *graph, struct graph_line *line) { /* * Add additional spaces to the end of the strbuf, so that all @@ -696,34 +814,22 @@ static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb, * This way, fields printed to the right of the graph will remain * aligned for the entire commit. */ - if (chars_written < graph->width) - strbuf_addchars(sb, ' ', graph->width - chars_written); + if (line->width < graph->width) + graph_line_addchars(line, ' ', graph->width - line->width); } static void graph_output_padding_line(struct git_graph *graph, - struct strbuf *sb) + struct graph_line *line) { int i; /* - * We could conceivable be called with a NULL commit - * if our caller has a bug, and invokes graph_next_line() - * immediately after graph_init(), without first calling - * graph_update(). Return without outputting anything in this - * case. - */ - if (!graph->commit) - return; - - /* * Output a padding row, that leaves all branch lines unchanged */ for (i = 0; i < graph->num_new_columns; i++) { - strbuf_write_column(sb, &graph->new_columns[i], '|'); - strbuf_addch(sb, ' '); + graph_line_write_column(line, &graph->new_columns[i], '|'); + graph_line_addch(line, ' '); } - - graph_pad_horizontally(graph, sb, graph->num_new_columns * 2); } @@ -733,28 +839,24 @@ int graph_width(struct git_graph *graph) } -static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb) +static void graph_output_skip_line(struct git_graph *graph, struct graph_line *line) { /* * Output an ellipsis to indicate that a portion * of the graph is missing. */ - strbuf_addstr(sb, "..."); - graph_pad_horizontally(graph, sb, 3); + graph_line_addstr(line, "..."); - if (graph->num_parents >= 3 && - graph->commit_index < (graph->num_columns - 1)) + if (graph_needs_pre_commit_line(graph)) graph_update_state(graph, GRAPH_PRE_COMMIT); else graph_update_state(graph, GRAPH_COMMIT); } static void graph_output_pre_commit_line(struct git_graph *graph, - struct strbuf *sb) + struct graph_line *line) { - int num_expansion_rows; int i, seen_this; - int chars_written; /* * This function formats a row that increases the space around a commit @@ -764,27 +866,24 @@ static void graph_output_pre_commit_line(struct git_graph *graph, * We need 2 extra rows for every parent over 2. */ assert(graph->num_parents >= 3); - num_expansion_rows = (graph->num_parents - 2) * 2; /* * graph->expansion_row tracks the current expansion row we are on. * It should be in the range [0, num_expansion_rows - 1] */ assert(0 <= graph->expansion_row && - graph->expansion_row < num_expansion_rows); + graph->expansion_row < graph_num_expansion_rows(graph)); /* * Output the row */ seen_this = 0; - chars_written = 0; for (i = 0; i < graph->num_columns; i++) { struct column *col = &graph->columns[i]; if (col->commit == graph->commit) { seen_this = 1; - strbuf_write_column(sb, col, '|'); - strbuf_addchars(sb, ' ', graph->expansion_row); - chars_written += 1 + graph->expansion_row; + graph_line_write_column(line, col, '|'); + graph_line_addchars(line, ' ', graph->expansion_row); } else if (seen_this && (graph->expansion_row == 0)) { /* * This is the first line of the pre-commit output. @@ -797,33 +896,27 @@ static void graph_output_pre_commit_line(struct git_graph *graph, */ if (graph->prev_state == GRAPH_POST_MERGE && graph->prev_commit_index < i) - strbuf_write_column(sb, col, '\\'); + graph_line_write_column(line, col, '\\'); else - strbuf_write_column(sb, col, '|'); - chars_written++; + graph_line_write_column(line, col, '|'); } else if (seen_this && (graph->expansion_row > 0)) { - strbuf_write_column(sb, col, '\\'); - chars_written++; + graph_line_write_column(line, col, '\\'); } else { - strbuf_write_column(sb, col, '|'); - chars_written++; + graph_line_write_column(line, col, '|'); } - strbuf_addch(sb, ' '); - chars_written++; + graph_line_addch(line, ' '); } - graph_pad_horizontally(graph, sb, chars_written); - /* * Increment graph->expansion_row, * and move to state GRAPH_COMMIT if necessary */ graph->expansion_row++; - if (graph->expansion_row >= num_expansion_rows) + if (!graph_needs_pre_commit_line(graph)) graph_update_state(graph, GRAPH_COMMIT); } -static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb) +static void graph_output_commit_char(struct git_graph *graph, struct graph_line *line) { /* * For boundary commits, print 'o' @@ -831,72 +924,67 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb) */ if (graph->commit->object.flags & BOUNDARY) { assert(graph->revs->boundary); - strbuf_addch(sb, 'o'); + graph_line_addch(line, 'o'); return; } /* * get_revision_mark() handles all other cases without assert() */ - strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit)); + graph_line_addstr(line, get_revision_mark(graph->revs, graph->commit)); } /* - * Draw the horizontal dashes of an octopus merge and return the number of - * characters written. + * Draw the horizontal dashes of an octopus merge. */ -static int graph_draw_octopus_merge(struct git_graph *graph, - struct strbuf *sb) +static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_line *line) { /* - * Here dashless_parents represents the number of parents which don't - * need to have dashes (the edges labeled "0" and "1"). And - * dashful_parents are the remaining ones. + * The parents of a merge commit can be arbitrarily reordered as they + * are mapped onto display columns, for example this is a valid merge: * - * | *---. - * | |\ \ \ - * | | | | | - * x 0 1 2 3 + * | | *---. + * | | |\ \ \ + * | | |/ / / + * | |/| | / + * | |_|_|/ + * |/| | | + * 3 1 0 2 * - */ - const int dashless_parents = 2; - int dashful_parents = graph->num_parents - dashless_parents; - - /* - * Usually, we add one new column for each parent (like the diagram - * above) but sometimes the first parent goes into an existing column, - * like this: + * The numbers denote which parent of the merge each visual column + * corresponds to; we can't assume that the parents will initially + * display in the order given by new_columns. * - * | *---. - * | |\ \ \ - * |/ / / / - * x 0 1 2 + * To find the right color for each dash, we need to consult the + * mapping array, starting from the column 2 places to the right of the + * merge commit, and use that to find out which logical column each + * edge will collapse to. * - * In which case the number of parents will be one greater than the - * number of added columns. + * Commits are rendered once all edges have collapsed to their correct + * logcial column, so commit_index gives us the right visual offset for + * the merge commit. */ - int added_cols = (graph->num_new_columns - graph->num_columns); - int parent_in_old_cols = graph->num_parents - added_cols; - /* - * In both cases, commit_index corresponds to the edge labeled "0". - */ - int first_col = graph->commit_index + dashless_parents - - parent_in_old_cols; + int i, j; + struct column *col; - int i; - for (i = 0; i < dashful_parents; i++) { - strbuf_write_column(sb, &graph->new_columns[i+first_col], '-'); - strbuf_write_column(sb, &graph->new_columns[i+first_col], - i == dashful_parents-1 ? '.' : '-'); + int dashed_parents = graph_num_dashed_parents(graph); + + for (i = 0; i < dashed_parents; i++) { + j = graph->mapping[(graph->commit_index + i + 2) * 2]; + col = &graph->new_columns[j]; + + graph_line_write_column(line, col, '-'); + graph_line_write_column(line, col, (i == dashed_parents - 1) ? '.' : '-'); } - return 2 * dashful_parents; + + return; } -static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) +static void graph_output_commit_line(struct git_graph *graph, struct graph_line *line) { int seen_this = 0; - int i, chars_written; + int i; /* * Output the row containing this commit @@ -906,7 +994,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) * children that we have already processed.) */ seen_this = 0; - chars_written = 0; for (i = 0; i <= graph->num_columns; i++) { struct column *col = &graph->columns[i]; struct commit *col_commit; @@ -920,19 +1007,17 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) if (col_commit == graph->commit) { seen_this = 1; - graph_output_commit_char(graph, sb); - chars_written++; + graph_output_commit_char(graph, line); if (graph->num_parents > 2) - chars_written += graph_draw_octopus_merge(graph, - sb); - } else if (seen_this && (graph->num_parents > 2)) { - strbuf_write_column(sb, col, '\\'); - chars_written++; - } else if (seen_this && (graph->num_parents == 2)) { + graph_draw_octopus_merge(graph, line); + } else if (seen_this && (graph->edges_added > 1)) { + graph_line_write_column(line, col, '\\'); + } else if (seen_this && (graph->edges_added == 1)) { /* - * This is a 2-way merge commit. - * There is no GRAPH_PRE_COMMIT stage for 2-way + * This is either a right-skewed 2-way merge + * commit, or a left-skewed 3-way merge. + * There is no GRAPH_PRE_COMMIT stage for such * merges, so this is the first line of output * for this commit. Check to see what the previous * line of output was. @@ -944,21 +1029,21 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) * makes the output look nicer. */ if (graph->prev_state == GRAPH_POST_MERGE && + graph->prev_edges_added > 0 && graph->prev_commit_index < i) - strbuf_write_column(sb, col, '\\'); + graph_line_write_column(line, col, '\\'); else - strbuf_write_column(sb, col, '|'); - chars_written++; + graph_line_write_column(line, col, '|'); + } else if (graph->prev_state == GRAPH_COLLAPSING && + graph->old_mapping[2 * i + 1] == i && + graph->mapping[2 * i] < i) { + graph_line_write_column(line, col, '/'); } else { - strbuf_write_column(sb, col, '|'); - chars_written++; + graph_line_write_column(line, col, '|'); } - strbuf_addch(sb, ' '); - chars_written++; + graph_line_addch(line, ' '); } - graph_pad_horizontally(graph, sb, chars_written); - /* * Update graph->state */ @@ -970,26 +1055,19 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) graph_update_state(graph, GRAPH_COLLAPSING); } -static struct column *find_new_column_by_commit(struct git_graph *graph, - struct commit *commit) -{ - int i; - for (i = 0; i < graph->num_new_columns; i++) { - if (graph->new_columns[i].commit == commit) - return &graph->new_columns[i]; - } - return NULL; -} +const char merge_chars[] = {'/', '|', '\\'}; -static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb) +static void graph_output_post_merge_line(struct git_graph *graph, struct graph_line *line) { int seen_this = 0; - int i, j, chars_written; + int i, j; + + struct commit_list *first_parent = first_interesting_parent(graph); + struct column *parent_col = NULL; /* * Output the post-merge row */ - chars_written = 0; for (i = 0; i <= graph->num_columns; i++) { struct column *col = &graph->columns[i]; struct commit *col_commit; @@ -1008,37 +1086,49 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf * new_columns and use those to format the * edges. */ - struct commit_list *parents = NULL; - struct column *par_column; + struct commit_list *parents = first_parent; + int par_column; + int idx = graph->merge_layout; + char c; seen_this = 1; - parents = first_interesting_parent(graph); - assert(parents); - par_column = find_new_column_by_commit(graph, parents->item); - assert(par_column); - - strbuf_write_column(sb, par_column, '|'); - chars_written++; - for (j = 0; j < graph->num_parents - 1; j++) { + + for (j = 0; j < graph->num_parents; j++) { + par_column = graph_find_new_column_by_commit(graph, parents->item); + assert(par_column >= 0); + + c = merge_chars[idx]; + graph_line_write_column(line, &graph->new_columns[par_column], c); + if (idx == 2) { + if (graph->edges_added > 0 || j < graph->num_parents - 1) + graph_line_addch(line, ' '); + } else { + idx++; + } parents = next_interesting_parent(graph, parents); - assert(parents); - par_column = find_new_column_by_commit(graph, parents->item); - assert(par_column); - strbuf_write_column(sb, par_column, '\\'); - strbuf_addch(sb, ' '); } - chars_written += j * 2; + if (graph->edges_added == 0) + graph_line_addch(line, ' '); + } else if (seen_this) { - strbuf_write_column(sb, col, '\\'); - strbuf_addch(sb, ' '); - chars_written += 2; + if (graph->edges_added > 0) + graph_line_write_column(line, col, '\\'); + else + graph_line_write_column(line, col, '|'); + graph_line_addch(line, ' '); } else { - strbuf_write_column(sb, col, '|'); - strbuf_addch(sb, ' '); - chars_written += 2; + graph_line_write_column(line, col, '|'); + if (graph->merge_layout != 0 || i != graph->commit_index - 1) { + if (parent_col) + graph_line_write_column( + line, parent_col, '_'); + else + graph_line_addch(line, ' '); + } } - } - graph_pad_horizontally(graph, sb, chars_written); + if (col_commit == first_parent->item) + parent_col = col; + } /* * Update graph->state @@ -1049,7 +1139,7 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf graph_update_state(graph, GRAPH_COLLAPSING); } -static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb) +static void graph_output_collapsing_line(struct git_graph *graph, struct graph_line *line) { int i; short used_horizontal = 0; @@ -1057,13 +1147,18 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf int horizontal_edge_target = -1; /* - * Clear out the new_mapping array + * Swap the mapping and old_mapping arrays + */ + SWAP(graph->mapping, graph->old_mapping); + + /* + * Clear out the mapping array */ for (i = 0; i < graph->mapping_size; i++) - graph->new_mapping[i] = -1; + graph->mapping[i] = -1; for (i = 0; i < graph->mapping_size; i++) { - int target = graph->mapping[i]; + int target = graph->old_mapping[i]; if (target < 0) continue; @@ -1084,14 +1179,14 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf * This column is already in the * correct place */ - assert(graph->new_mapping[i] == -1); - graph->new_mapping[i] = target; - } else if (graph->new_mapping[i - 1] < 0) { + assert(graph->mapping[i] == -1); + graph->mapping[i] = target; + } else if (graph->mapping[i - 1] < 0) { /* * Nothing is to the left. * Move to the left by one */ - graph->new_mapping[i - 1] = target; + graph->mapping[i - 1] = target; /* * If there isn't already an edge moving horizontally * select this one. @@ -1107,9 +1202,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf * line. */ for (j = (target * 2)+3; j < (i - 2); j += 2) - graph->new_mapping[j] = target; + graph->mapping[j] = target; } - } else if (graph->new_mapping[i - 1] == target) { + } else if (graph->mapping[i - 1] == target) { /* * There is a branch line to our left * already, and it is our target. We @@ -1117,7 +1212,7 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf * the same parent commit. * * We don't have to add anything to the - * output or new_mapping, since the + * output or mapping, since the * existing branch line has already taken * care of it. */ @@ -1129,39 +1224,46 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf * * The space just to the left of this * branch should always be empty. - * - * The branch to the left of that space - * should be our eventual target. */ - assert(graph->new_mapping[i - 1] > target); - assert(graph->new_mapping[i - 2] < 0); - assert(graph->new_mapping[i - 3] == target); - graph->new_mapping[i - 2] = target; + assert(graph->mapping[i - 1] > target); + assert(graph->mapping[i - 2] < 0); + graph->mapping[i - 2] = target; /* * Mark this branch as the horizontal edge to * prevent any other edges from moving * horizontally. */ - if (horizontal_edge == -1) - horizontal_edge = i; + if (horizontal_edge == -1) { + int j; + horizontal_edge_target = target; + horizontal_edge = i - 1; + + for (j = (target * 2) + 3; j < (i - 2); j += 2) + graph->mapping[j] = target; + } } } /* + * Copy the current mapping array into old_mapping + */ + COPY_ARRAY(graph->old_mapping, graph->mapping, graph->mapping_size); + + /* * The new mapping may be 1 smaller than the old mapping */ - if (graph->new_mapping[graph->mapping_size - 1] < 0) + if (graph->mapping[graph->mapping_size - 1] < 0) graph->mapping_size--; /* * Output out a line based on the new mapping info */ for (i = 0; i < graph->mapping_size; i++) { - int target = graph->new_mapping[i]; + int target = graph->mapping[i]; if (target < 0) - strbuf_addch(sb, ' '); + graph_line_addch(line, ' '); else if (target * 2 == i) - strbuf_write_column(sb, &graph->new_columns[target], '|'); + graph_line_write_column(line, &graph->new_columns[target], '|'); else if (target == horizontal_edge_target && i != horizontal_edge - 1) { /* @@ -1170,24 +1272,17 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf * won't continue into the next line. */ if (i != (target * 2)+3) - graph->new_mapping[i] = -1; + graph->mapping[i] = -1; used_horizontal = 1; - strbuf_write_column(sb, &graph->new_columns[target], '_'); + graph_line_write_column(line, &graph->new_columns[target], '_'); } else { if (used_horizontal && i < horizontal_edge) - graph->new_mapping[i] = -1; - strbuf_write_column(sb, &graph->new_columns[target], '/'); + graph->mapping[i] = -1; + graph_line_write_column(line, &graph->new_columns[target], '/'); } } - graph_pad_horizontally(graph, sb, graph->mapping_size); - - /* - * Swap mapping and new_mapping - */ - SWAP(graph->mapping, graph->new_mapping); - /* * If graph->mapping indicates that all of the branch lines * are already in the correct positions, we are done. @@ -1199,35 +1294,49 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf int graph_next_line(struct git_graph *graph, struct strbuf *sb) { + int shown_commit_line = 0; + struct graph_line line = { .buf = sb, .width = 0 }; + + /* + * We could conceivable be called with a NULL commit + * if our caller has a bug, and invokes graph_next_line() + * immediately after graph_init(), without first calling + * graph_update(). Return without outputting anything in this + * case. + */ + if (!graph->commit) + return -1; + switch (graph->state) { case GRAPH_PADDING: - graph_output_padding_line(graph, sb); - return 0; + graph_output_padding_line(graph, &line); + break; case GRAPH_SKIP: - graph_output_skip_line(graph, sb); - return 0; + graph_output_skip_line(graph, &line); + break; case GRAPH_PRE_COMMIT: - graph_output_pre_commit_line(graph, sb); - return 0; + graph_output_pre_commit_line(graph, &line); + break; case GRAPH_COMMIT: - graph_output_commit_line(graph, sb); - return 1; + graph_output_commit_line(graph, &line); + shown_commit_line = 1; + break; case GRAPH_POST_MERGE: - graph_output_post_merge_line(graph, sb); - return 0; + graph_output_post_merge_line(graph, &line); + break; case GRAPH_COLLAPSING: - graph_output_collapsing_line(graph, sb); - return 0; + graph_output_collapsing_line(graph, &line); + break; } - assert(0); - return 0; + graph_pad_horizontally(graph, &line); + return shown_commit_line; } static void graph_padding_line(struct git_graph *graph, struct strbuf *sb) { int i; - int chars_written = 0; + struct graph_line line = { .buf = sb, .width = 0 }; if (graph->state != GRAPH_COMMIT) { graph_next_line(graph, sb); @@ -1244,20 +1353,17 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb) for (i = 0; i < graph->num_columns; i++) { struct column *col = &graph->columns[i]; - strbuf_write_column(sb, col, '|'); - chars_written++; + graph_line_write_column(&line, col, '|'); if (col->commit == graph->commit && graph->num_parents > 2) { int len = (graph->num_parents - 2) * 2; - strbuf_addchars(sb, ' ', len); - chars_written += len; + graph_line_addchars(&line, ' ', len); } else { - strbuf_addch(sb, ' '); - chars_written++; + graph_line_addch(&line, ' '); } } - graph_pad_horizontally(graph, sb, chars_written); + graph_pad_horizontally(graph, &line); /* * Update graph->prev_state since we have output a padding line |