summaryrefslogtreecommitdiff
path: root/graph.c
diff options
context:
space:
mode:
Diffstat (limited to 'graph.c')
-rw-r--r--graph.c654
1 files changed, 377 insertions, 277 deletions
diff --git a/graph.c b/graph.c
index f53135485f..aaf97069bd 100644
--- a/graph.c
+++ b/graph.c
@@ -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,14 +1224,10 @@ 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
@@ -1148,20 +1239,25 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
}
/*
+ * 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 +1266,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 +1288,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 +1347,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