[PATCH 03/11] graph: reduce duplication in `graph_insert_into_new_columns()`
From: James Coglan
I will shortly be making some changes to this function and so am trying
to simplify it. It currently contains some duplicated logic; both
branches the function can take assign the commit's column index into
the `mapping` array and increment `mapping_index`.
Here I change the function so that the only conditional behaviour is
that it appends the commit to `new_columns` if it's not present. All
manipulation of `mapping` now happens on a single code path.
Signed-off-by: James Coglan
---
graph.c | 20 +++-
1 file changed, 7 insertions(+), 13 deletions(-)
diff --git a/graph.c b/graph.c
index a890c9d8bb..1cd30f80e6 100644
--- a/graph.c
+++ b/graph.c
@@ -459,23 +459,17 @@ static void graph_insert_into_new_columns(struct
git_graph *graph,
int i = graph_find_new_column_by_commit(graph, commit);
/*
-* If the commit is already in the new_columns list, we don't need to
-* add it. Just update the mapping correctly.
+* If the commit is not already in the new_columns array, then add it
+* and record it as being in the final column.
*/
- if (i >= 0) {
- graph->mapping[*mapping_index] = i;
- *mapping_index += 2;
- return;
+ 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);
}
- /*
-* 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;
+ graph->mapping[*mapping_index] = i;
*mapping_index += 2;
- graph->num_new_columns++;
}
static void graph_update_width(struct git_graph *graph,
--
gitgitgadget
[PATCH 02/11] graph: reuse `find_new_column_by_commit()`
From: James Coglan
I will shortly be making some changes to
`graph_insert_into_new_columns()` and so am trying to simplify it. One
possible simplification is that we can extract the loop for finding the
element in `new_columns` containing the given commit.
`find_new_column_by_commit()` contains a very similar loop but it
returns a `struct column *` rather than an `int` offset into the array.
Here I'm introducing a version that returns `int` and using that in
`graph_insert_into_new_columns()` and `graph_output_post_merge_line()`.
Signed-off-by: James Coglan
---
graph.c | 48 +++-
1 file changed, 23 insertions(+), 25 deletions(-)
diff --git a/graph.c b/graph.c
index c56fdec1fc..a890c9d8bb 100644
--- a/graph.c
+++ b/graph.c
@@ -441,22 +441,31 @@ static unsigned short graph_find_commit_color(const
struct git_graph *graph,
return graph_get_current_column_color(graph);
}
+static int graph_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 i;
+ }
+ return -1;
+}
+
static void graph_insert_into_new_columns(struct git_graph *graph,
struct commit *commit,
int *mapping_index)
{
- int i;
+ int i = graph_find_new_column_by_commit(graph, commit);
/*
* 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 (i >= 0) {
+ graph->mapping[*mapping_index] = i;
+ *mapping_index += 2;
+ return;
}
/*
@@ -961,17 +970,6 @@ 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;
-}
-
static void graph_output_post_merge_line(struct git_graph *graph, struct
strbuf *sb)
{
int seen_this = 0;
@@ -999,20 +997,20 @@ static void graph_output_post_merge_line(struct git_graph
*graph, struct strbuf
* edges.
*/
struct commit_list *parents = NULL;
- struct column *par_column;
+ int par_column;
seen_this = 1;
parents = first_interesting_parent(graph);
assert(parents);
- par_column = find_new_column_by_commit(graph,
parents->item);
- assert(par_column);
+ par_column = graph_find_new_column_by_commit(graph,
parents->item);
+ assert(par_column >= 0);
- strbuf_write_column(sb, par_column, '|');
+ strbuf_write_column(sb,
&graph->new_columns[par_column], '|');
for (j = 0; j < graph->num_parents - 1; j++) {
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, '\\');
+ par_column =
graph_find_new_column_by_commit(graph, parents->item);
+ assert(par_column >= 0);
+ strbuf_write_column(sb,
&graph->new_columns[par_column], '\\');
strbuf_addch(sb, ' ');
}
} else if (seen_this) {
--
gitgitgadget
[PATCH 01/11] graph: automatically track visible width of `strbuf`
From: James Coglan
All the output functions in `graph.c` currently keep track of how many
printable chars they've written to the buffer, before calling
`graph_pad_horizontally()` to pad the line with spaces. Some functions
do this by incrementing a counter whenever they write to the buffer, and
others do it by encoding an assumption about how many chars are written,
as in:
graph_pad_horizontally(graph, sb, graph->num_columns * 2);
This adds a fair amount of noise to the functions' logic and is easily
broken if one forgets to increment the right counter or update the
calculations used for padding.
To make this easier to use, I'm adding a `width` field to `strbuf` that
tracks the number of printing characters added after the line prefix.
It's set to 0 at the start of `graph_next_line()`, and then various
`strbuf` functions update it as follows:
- `strbuf_write_column()` increments `width` by 1
- `strbuf_setlen()` changes `width` by the amount added to `len` if
`len` is increased, or makes `width` and `len` the same if it's
decreased
- `strbuf_addch()` increments `width` by 1
This is enough to ensure that the functions used by `graph.c` update
`strbuf->width` correctly, and `graph_pad_horizontally()` can then use
this field instead of taking `chars_written` as a parameter.
Signed-off-by: James Coglan
---
graph.c | 68 ++--
strbuf.h | 8 ++-
2 files changed, 33 insertions(+), 43 deletions(-)
diff --git a/graph.c b/graph.c
index f53135485f..c56fdec1fc 100644
--- a/graph.c
+++ b/graph.c
@@ -115,11 +115,20 @@ static const char *column_get_color_code(unsigned short
color)
static void strbuf_write_column(struct strbuf *sb, const struct column *c,
char col_char)
{
+ /*
+* Remember the buffer's width as we're about to add non-printing
+* content to it, and we want to avoid counting the byte length
+* of this content towards the buffer's visible width
+*/
+ size_t prev_width = sb->width;
+
if (c->color < column_colors_max)
strbuf_addstr(sb, column_get_color_code(c->color));
strbuf_addch(sb, col_char);
if (c->color < column_colors_max)
strbuf_addstr(sb, column_get_color_code(column_colors_max));
+
+ sb->width = prev_width + 1;
}
struct git_graph {
@@ -686,8 +695,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 strbuf *sb)
{
/*
* Add additional spaces to the end of the strbuf, so that all
@@ -696,8 +704,8 @@ 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 (sb->width < graph->width)
+ strbuf_addchars(sb, ' ', graph->width - sb->width);
}
static void graph_output_padding_line(struct git_graph *graph,
@@ -723,7 +731,7 @@ static void graph_output_padding_line(struct git_graph
*graph,
strbuf_addch(sb, ' ');
}
- graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
+ graph_pad_horizontally(graph, sb);
}
@@ -740,7 +748,7 @@ static void graph_output_skip_line(struct git_graph *graph,
struct strbuf *sb)
* of the graph is missing.
*/
strbuf_addstr(sb, "...");
- graph_pad_horizontally(graph, sb, 3);
+ graph_pad_horizontally(graph, sb);
if (graph->num_parents >= 3 &&
graph->commit_index < (graph->num_columns - 1))
@@ -754,7 +762,6 @@ static void graph_output_pre_commit_line(struct git_graph
*graph,
{
int num_expansion_rows;
int i, seen_this;
- int chars_written;
/*
* This function formats a row that increases the space around a commit
@@ -777,14 +784,12 @@ static void graph_output_pre_commit_line(struct git_graph
*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;
} else if (seen_this && (graph->expansion_row == 0)) {
/*
* This is the first line of the pre-commit output.
@@ -800,19 +805,15 @@ static void grap
[PATCH 00/11] Improve the readability of log --graph output
This series of patches are designed to improve the output of the log --graph command; their effect can be summed up in the following diagram: BeforeAfter --- * |\ | * * | |\ |\ | | * | * | | | | |\ | | \| | * | *-. \ | * | | |\ \ \ |/|\| |/ / / / | | * | | | / | * | | | |/| |/ | | * * / | * | |/ | |/ * * | |/ * These changes aim to make the edges in graph diagrams easier to read, by straightening lines and making certain kinds of topologies display more compactly. Three distinct changes are included. First, if the first parent of a merge fuses with an edge to the left of the commit, then we display that by making the edges fuse immediately rather than by drawing a line straight down and then having it track to the left. That is, where we currently display these graphs: | * | | | * | |\| | | |\ |/ /| |_|/ / | | |/| | | We will now display these merges as follows: | * | | | * |/| | |_|/| | | |/| | | This transformation is applied to merges with any number of parents, for example we currently display 3-parent merges like this: | *-. | | | *-. | |\ \ | | | |\ \ |/ / / | |_|/ / / | | | |/| | | | And we will now display them like this: | * | | | * |/|\| |_|/|\ | | | |/| | | | If the edge the first parent fuses with is separated from the commit by multiple columns, a horizontal edge is drawn just as we currently do in the 'collapsing' state. This change also affects the display of commit and post-merge lines in subtle ways that are more thoroughly described in the relevant commits. The second change is that if the final parent of a merge fuses with the edge to the right of the commit, then we can remove the zig-zag effect that currently results. We currently display these merges like this: * | |\ \ | |/ | * After these changes, this merge will now be displayed like so: * | |\| | * If the final parent fuses with an edge that's further to the right, its display is unchanged and it will still display like this: * | | | |\ \ \ \ | | |_|/ | |/| | | * | | The final structural change smooths out lines that are collapsing through commit lines. For example, consider the following history: *-. \ |\ \ \ | | * | | * | | | |/ / * | | |/ / * | |/ * This is now rendered so that commit lines display an edge using / instead of |, if that edge is tracking to the left both above and below the commit line. That results in this improved display: *-. \ |\ \ \ | | * | | * | | | |/ / * / / |/ / * / |/ * Taken together, these changes produce the change shown in the first diagram above, with the current rendering on the left and the new rendering on the right. A final addition to that set of changes fixes the coloring of dashes that are drawn next to octopus merges, in a manner compatible with all these changes. The early commits in this set are refactorings that make the functional changes easier to introduce. James Coglan (11): graph: automatically track visible width of `strbuf` graph: reuse `find_new_column_by_commit()` graph: reduce duplication in `graph_insert_into_new_columns()` graph: remove `mapping_idx` and `graph_update_width()` graph: extract logic for moving to GRAPH_PRE_COMMIT state graph: tidy up display of left-skewed merges graph: commit and post-merge lines for left-skewed merges graph: rename `new_mapping` to `old_mapping` graph: smooth appearance of collapsing edges on commit lines graph: flatten edges that join to their right neighbor graph: fix coloring of octopus dashes graph.c| 499 - strbuf.h | 8 +- t/t3430-rebase-merges.sh | 2 +- t/t4202-log.sh | 2 +- t/t4214-log-graph-octopus.sh | 85 +++- t/t4215-log-skewed-merges.sh | 267 +++ t/t6016-rev-list-graph-simplify-history.sh | 30 +- 7 files changed, 649 insertions(+), 244 deletions(-) create mode 100755 t/t4215-log-skewed-merges.sh base-commit: 5fa0f5238b0cd46cfe7f6fa76c3f526ea98148d9 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-383%2Fjcoglan%2Fjc%2Fsimplify-graph-v1 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-383/jcoglan/jc/simplify-graph-v1 Pull-Request: https://github.com/gitgitgad
[PATCH 04/11] graph: remove `mapping_idx` and `graph_update_width()`
From: James Coglan
There's a duplication of logic between `graph_insert_into_new_columns()`
and `graph_update_width()`. `graph_insert_into_new_columns()` is called
repeatedly by `graph_update_columns()` with an `int *` that tracks the
offset into the `mapping` array where we should write the next value.
Each call to `graph_insert_into_new_columns()` effectively pushes one
column index and one "null" value (-1) onto the `mapping` array and
therefore increments `mapping_idx` by 2.
`graph_update_width()` duplicates this process: the `width` of the graph
is essentially the initial width of the `mapping` array before edges
begin collapsing. The `graph_update_width()` function's logic
effectively works out how many times `graph_insert_into_new_columns()`
was called based on the relationship of the current commit to the rest
of the graph.
I'm about to make some changes that make the assignment of values into
the `mapping` array more complicated. Rather than make
`graph_update_width()` more complicated at the same time, we can simply
remove this function and use `graph->width` to track the offset into the
`mapping` array as we're building it. This removes the duplication and
makes sure that `graph->width` is the same as the visual width of the
`mapping` array once `graph_update_columns()` is complete.
Signed-off-by: James Coglan
---
graph.c | 65 +
1 file changed, 10 insertions(+), 55 deletions(-)
diff --git a/graph.c b/graph.c
index 1cd30f80e6..a71ae5cd61 100644
--- a/graph.c
+++ b/graph.c
@@ -453,8 +453,7 @@ static int graph_find_new_column_by_commit(struct git_graph
*graph,
}
static void graph_insert_into_new_columns(struct git_graph *graph,
- struct commit *commit,
- int *mapping_index)
+ struct commit *commit)
{
int i = graph_find_new_column_by_commit(graph, commit);
@@ -468,50 +467,14 @@ static void graph_insert_into_new_columns(struct
git_graph *graph,
graph->new_columns[i].color = graph_find_commit_color(graph,
commit);
}
- graph->mapping[*mapping_index] = i;
- *mapping_index += 2;
-}
-
-static void graph_update_width(struct git_graph *graph,
- int is_commit_in_existing_columns)
-{
- /*
-* 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;
-
- /*
-* Even if the current commit has no parents to be printed, it
-* still takes up a column for itself.
-*/
- if (graph->num_parents < 1)
- max_cols++;
-
- /*
-* 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--;
-
- /*
-* Each column takes up 2 spaces
-*/
- graph->width = max_cols * 2;
+ graph->mapping[graph->width] = i;
+ graph->width += 2;
}
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;
/*
@@ -544,6 +507,8 @@ static void graph_update_columns(struct git_graph *graph)
for (i = 0; i < graph->mapping_size; i++)
graph->mapping[i] = -1;
+ graph->width = 0;
+
/*
* Populate graph->new_columns and graph->mapping
*
@@ -554,7 +519,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;
@@ -568,7 +532,6 @@ 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;
for (parent = first_interesting_parent(graph);
@@ -583,21 +546,18 @@ static void graph_update_columns(struct git_graph *graph)
!is_commit_in_columns) {
graph_increment_column_color(graph);
}
- graph_i
[PATCH 05/11] graph: extract logic for moving to GRAPH_PRE_COMMIT state
From: James Coglan
This computation is repeated in a couple of places and I need to add
another condition to it to implement a further improvement to the graph
rendering, so I'm extracting this into a function.
Signed-off-by: James Coglan
---
graph.c | 12
1 file changed, 8 insertions(+), 4 deletions(-)
diff --git a/graph.c b/graph.c
index a71ae5cd61..98e8777db4 100644
--- a/graph.c
+++ b/graph.c
@@ -569,6 +569,12 @@ static void graph_update_columns(struct git_graph *graph)
graph->mapping_size--;
}
+static int graph_needs_pre_commit_line(struct git_graph *graph)
+{
+ return graph->num_parents >= 3 &&
+ graph->commit_index < (graph->num_columns - 1);
+}
+
void graph_update(struct git_graph *graph, struct commit *commit)
{
struct commit_list *parent;
@@ -624,8 +630,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;
@@ -708,8 +713,7 @@ static void graph_output_skip_line(struct git_graph *graph,
struct strbuf *sb)
strbuf_addstr(sb, "...");
graph_pad_horizontally(graph, sb);
- 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);
--
gitgitgadget
[PATCH 09/11] graph: smooth appearance of collapsing edges on commit lines
From: James Coglan
When a graph contains edges that are in the process of collapsing to the
left, but those edges cross a commit line, the effect is that the edges
have a jagged appearance:
*
|\
| *
| \
*-. \
|\ \ \
| | * |
| * | |
| |/ /
* | |
|/ /
* |
|/
*
We already takes steps to smooth edges like this when they're expanding;
when an edge appears to the right of a merge commit marker on a
GRAPH_COMMIT line immediately following a GRAPH_POST_MERGE line, we
render it as a `\`:
* \
|\ \
| * \
| |\ \
We can make a similar improvement to collapsing edges, making them
easier to follow and giving the overall graph a feeling of increased
symmetry:
*
|\
| *
| \
*-. \
|\ \ \
| | * |
| * | |
| |/ /
* / /
|/ /
* /
|/
*
To do this, we introduce a new special case for edges on GRAPH_COMMIT
lines that immediately follow a GRAPH_COLLAPSING line. By retaining a
copy of the `mapping` array used to render the GRAPH_COLLAPSING line in
the `old_mapping` array, we can determine that an edge is collapsing
through the GRAPH_COMMIT line and should be smoothed.
Signed-off-by: James Coglan
---
graph.c| 17 +
t/t3430-rebase-merges.sh | 2 +-
t/t4202-log.sh | 2 +-
t/t4214-log-graph-octopus.sh | 16
t/t4215-log-skewed-merges.sh | 2 +-
t/t6016-rev-list-graph-simplify-history.sh | 4 ++--
6 files changed, 26 insertions(+), 17 deletions(-)
diff --git a/graph.c b/graph.c
index b0e31e23ca..6391e393ec 100644
--- a/graph.c
+++ b/graph.c
@@ -278,10 +278,10 @@ 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 *old_mapping;
/*
@@ -1011,6 +1011,10 @@ static void graph_output_commit_line(struct git_graph
*graph, struct strbuf *sb)
strbuf_write_column(sb, col, '\\');
else
strbuf_write_column(sb, col, '|');
+ } else if (graph->prev_state == GRAPH_COLLAPSING &&
+ graph->old_mapping[2 * i + 1] == i &&
+ graph->mapping[2 * i] < i) {
+ strbuf_write_column(sb, col, '/');
} else {
strbuf_write_column(sb, col, '|');
}
@@ -1211,6 +1215,11 @@ 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
*/
diff --git a/t/t3430-rebase-merges.sh b/t/t3430-rebase-merges.sh
index 7b6c4847ad..051351ecdf 100755
--- a/t/t3430-rebase-merges.sh
+++ b/t/t3430-rebase-merges.sh
@@ -402,7 +402,7 @@ test_expect_success 'octopus merges' '
| | * three
| * | two
| |/
- * | one
+ * / one
|/
o before-octopus
EOF
diff --git a/t/t4202-log.sh b/t/t4202-log.sh
index c20209324c..c7aa0532c1 100755
--- a/t/t4202-log.sh
+++ b/t/t4202-log.sh
@@ -667,7 +667,7 @@ cat > expect <<\EOF
* | | fifth
* | | fourth
|/ /
-* | third
+* / third
|/
* second
* initial
diff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh
index 40f420877b..9ada687628 100755
--- a/t/t4214-log-graph-octopus.sh
+++ b/t/t4214-log-graph-octopus.sh
@@ -12,9 +12,9 @@ test_expect_success 'set up merge history' '
| | | * 4
| | * | 3
| | |/
- | * | 2
+ | * / 2
| |/
- * | 1
+ * / 1
|/
* initial
EOF
@@ -25,9 +25,9 @@ test_expect_success 'set up merge history' '
| | | * 4
| | * | 3
| | |/
- | * | 2
+ | * / 2
| |/
- * | 1
+ * / 1
|/
* initial
EOF
@@ -68,9 +68,9 @@ test_expect_success 'log --graph with normal octopus merge,
no color' '
| | | * 4
| | * | 3
| | |/
- | * | 2
+ | * / 2
| |/
- *
[PATCH 08/11] graph: rename `new_mapping` to `old_mapping`
From: James Coglan
The change I'm about to make requires being able to inspect the mapping
array that was used to render the last GRAPH_COLLAPSING line while
rendering a GRAPH_COMMIT line. The `new_mapping` array currently exists
as a pre-allocated space for computing the next `mapping` array during
`graph_output_collapsing_line()`, but we can repurpose it to let us see
the previous `mapping` state.
To support this use it will make more sense if this array is named
`old_mapping`, as it will contain the mapping data for the previous line
we rendered, at the point we're rendering a commit line.
Signed-off-by: James Coglan
---
graph.c | 54 +++---
1 file changed, 27 insertions(+), 27 deletions(-)
diff --git a/graph.c b/graph.c
index fb2e42850f..b0e31e23ca 100644
--- a/graph.c
+++ b/graph.c
@@ -240,7 +240,7 @@ struct git_graph {
/*
* 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;
/*
@@ -283,7 +283,7 @@ struct git_graph {
* 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.
*/
- int *new_mapping;
+ int *old_mapping;
/*
* The current default column color being used. This is
* stored as an index into the array column_colors.
@@ -369,7 +369,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
@@ -399,7 +399,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);
}
/*
@@ -1116,13 +1116,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;
@@ -1143,14 +1148,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.
@@ -1166,9 +1171,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
@@ -1176,7 +118
[PATCH 11/11] graph: fix coloring of octopus dashes
From: James Coglan
In 04005834ed ("log: fix coloring of certain octopus merge shapes",
2018-09-01) there is a fix for the coloring of dashes following an
octopus merge. It makes a distinction between the case where all parents
introduce a new column, versus the case where the first parent collapses
into an existing column:
| *-. | *-.
| |\ \ | |\ \
| | | | |/ / /
The latter case means that the columns for the merge parents begin one
place to the left in the `new_columns` array compared to the former
case.
However, the implementation only works if the commit's parents are kept
in order as they map onto the visual columns, as we get the colors by
iterating over `new_columns` as we print the dashes. In general, the
commit's parents can arbitrarily merge with existing columns, and change
their ordering in the process.
For example, in the following diagram, the number of each column
indicates which commit parent appears in each column.
| | *---.
| | |\ \ \
| | |/ / /
| |/| | /
| |_|_|/
|/| | |
3 1 0 2
If the columns are colored (red, green, yellow, blue), then the dashes
will currently be colored yellow and blue, whereas they should be blue
and red.
To fix this, we need to look up each column in the `mapping` array,
which before the `GRAPH_COLLAPSING` state indicates which logical column
is displayed in each visual column. This implementation is simpler as it
doesn't have any edge cases, and it also handles how left-skewed first
parents are now displayed:
| *-.
|/|\ \
| | | |
0 1 2 3
The color of the first dashes is always the color found in `mapping` two
columns to the right of the commit symbol. Because commits are displayed
after all edges have been collapsed together and the visual columns
match the logical ones, we can find the visual offset of the commit
symbol using `commit_index`.
Signed-off-by: James Coglan
---
graph.c | 71 +++-
t/t4214-log-graph-octopus.sh | 59 --
2 files changed, 92 insertions(+), 38 deletions(-)
diff --git a/graph.c b/graph.c
index 7dd2fab625..908f257018 100644
--- a/graph.c
+++ b/graph.c
@@ -665,6 +665,11 @@ static void graph_update_columns(struct git_graph *graph)
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)
{
/*
@@ -687,7 +692,7 @@ static int graph_num_expansion_rows(struct git_graph *graph)
* | * \
* |/|\ \
*/
- return (graph->num_parents + graph->merge_layout - 3) * 2;
+ return graph_num_dashed_parents(graph) * 2;
}
static int graph_needs_pre_commit_line(struct git_graph *graph)
@@ -930,47 +935,45 @@ static void graph_output_commit_char(struct git_graph
*graph, struct strbuf *sb)
static void graph_draw_octopus_merge(struct git_graph *graph, struct strbuf
*sb)
{
/*
-* 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 = 3 - graph->merge_layout;
- 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.
[PATCH 07/11] graph: commit and post-merge lines for left-skewed merges
From: James Coglan
Following the introduction of "left-skewed" merges, which are merges
whose first parent fuses with another edge to its left, we have some
more edge cases to deal with in the display of commit and post-merge
lines.
The current graph code handles the following cases for edges appearing
to the right of the commit (*) on commit lines. A 2-way merge is usually
followed by vertical lines:
| | |
| * |
| |\ \
An octopus merge (more than two parents) is always followed by edges
sloping to the right:
| | \ | |\
| *-. \ | *---. \
| |\ \ \| |\ \ \ \
A 2-way merge is followed by a right-sloping edge if the commit line
immediately follows a post-merge line for a commit that appears in the
same column as the current commit, or any column to the left of that:
| * | * |
| |\| |\ \
| * \ | | * \
| |\ \ | | |\ \
This commit introduces the following new cases for commit lines. If a
2-way merge skews to the left, then the edges to its right are always
vertical lines, even if the commit follows a post-merge line:
| | | | |\
| * | | * |
|/| | |/| |
A commit with 3 parents that skews left is followed by vertical edges:
| | |
| * |
|/|\ \
If a 3-way left-skewed merge commit appears immediately after a
post-merge line, then it may be followed the right-sloping edges, just
like a 2-way merge that is not skewed.
| |\
| * \
|/|\ \
Octopus merges with 4 or more parents that skew to the left will always
be followed by right-sloping edges, because the existing columns need to
expand around the merge.
| | \
| *-. \
|/|\ \ \
On post-merge lines, usually all edges following the current commit
slope to the right:
| * | |
| |\ \ \
However, if the commit is a left-skewed 2-way merge, the edges to its
right remain vertical. We also need to display a space after the
vertical line descending from the commit marker, whereas this line would
normally be followed by a backslash.
| * | |
|/| | |
If a left-skewed merge has more than 2 parents, then the edges to its
right are still sloped as they bend around the edges introduced by the
merge.
| * | |
|/|\ \ \
To handle these new cases, we need to know not just how many parents
each commit has, but how many new columns it adds to the display; this
quantity is recorded in the `edges_added` field for the current commit,
and `prev_edges_added` field for the previous commit.
Here, "column" refers to visual columns, not the logical columns of the
`columns` array. This is because even if all the commit's parents end up
fusing with existing edges, they initially introduce distinct edges in
the commit and post-merge lines before those edges collapse. For
example, a 3-way merge whose 2nd and 3rd parents fuse with existing
edges still introduces 2 visual columns that affect the display of edges
to their right.
| | | \
| | *-. \
| | |\ \ \
| |_|/ / /
|/| | / /
| | |/ /
| |/| |
| | | |
This merge does not introduce any *logical* columns; there are 4 edges
before and after this commit once all edges have collapsed. But it does
initially introduce 2 new edges that need to be accommodated by the
edges to their right.
Signed-off-by: James Coglan
---
graph.c | 63 +--
t/t4215-log-skewed-merges.sh | 151 +++
2 files changed, 209 insertions(+), 5 deletions(-)
diff --git a/graph.c b/graph.c
index 9136173e03..fb2e42850f 100644
--- a/graph.c
+++ b/graph.c
@@ -197,6 +197,46 @@ struct git_graph {
* |/| | | | | | | | | | *
*/
int merge_layout;
+ /*
+* The number of columns added to the graph by the current commit. For
+* 2-way and octopus merges, this is 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
[PATCH 06/11] graph: tidy up display of left-skewed merges
From: James Coglan
Currently, when we display a merge whose first parent is already present
in a column to the left of the merge commit, we display the first parent
as a veritcal pipe `|` in the GRAPH_POST_MERGE line and then immediately
enter the GRAPH_COLLAPSING state. The first-parent line tracks to the
left and all the other parent lines follow it; this creates a "kink" in
those lines:
| *---.
| |\ \ \
|/ / / /
| | | *
This change tidies the display of such commits such that if the first
parent appears to the left of the merge, we render it as a `/` and the
second parent as a `|`. This reduces the horizontal and vertical space
needed to render the merge, and makes the resulting lines easier to
read.
| *-.
|/|\ \
| | | *
If the first parent is separated from the merge by several columns, a
horizontal line is drawn in a similar manner to how the GRAPH_COLLAPSING
state displays the line.
| | | *-.
| |_|/|\ \
|/| | | | *
This effect is applied to both "normal" two-parent merges, and to
octopus merges. It also reduces the vertical space needed for pre-commit
lines, as the merge occupies one less column than usual.
Before: After:
| * | *
| |\| |\
| | \ | * \
| | \ |/|\ \
| *-. \
| |\ \ \
Signed-off-by: James Coglan
---
graph.c | 125 +++
t/t4214-log-graph-octopus.sh | 10 ++-
t/t4215-log-skewed-merges.sh | 42
3 files changed, 143 insertions(+), 34 deletions(-)
create mode 100755 t/t4215-log-skewed-merges.sh
diff --git a/graph.c b/graph.c
index 98e8777db4..9136173e03 100644
--- a/graph.c
+++ b/graph.c
@@ -183,6 +183,20 @@ struct git_graph {
* previous commit.
*/
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 maximum number of columns that can be stored in the columns
* and new_columns arrays. This is also half the number of entries
@@ -294,6 +308,7 @@ 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->num_columns = 0;
graph->num_new_columns = 0;
graph->mapping_size = 0;
@@ -453,9 +468,11 @@ static int graph_find_new_column_by_commit(struct
git_graph *graph,
}
static void graph_insert_into_new_columns(struct git_graph *graph,
- struct commit *commit)
+ struct commit *commit,
+ int idx)
{
int i = graph_find_new_column_by_commit(graph, commit);
+ int mapping_idx;
/*
* If the commit is not already in the new_columns array, then add it
@@ -467,8 +484,26 @@ static void graph_insert_into_new_columns(struct git_graph
*graph,
graph->new_columns[i].color = graph_find_commit_color(graph,
commit);
}
- graph->mapping[graph->width] = i;
- graph->width += 2;
+ 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;
+
+ dist = idx - i;
+ shift = (dist > 1) ? 2 * dist - 3 : 1;
+
+ graph->merge_layout = (dist > 0) ? 0 : 1;
+ mapping_idx = graph->width + (graph->merge_layout - 1) * shift;
+ graph->width += 2 * graph->merge_layout;
+ } else {
+ mapping_idx = graph->width;
+ graph->width += 2;
+ }
+
+ graph->mapping[mapping_idx] = i;
}
static void graph_update_columns(struct git_graph *graph)
@@ -534,6 +569,7 @@ static void graph_update_columns(struct git_graph *graph)
if (col_commit == graph->commit) {
seen_this = 1;
graph->commit_index = i;
+ graph->merge_layout = -1;
for (par
[PATCH 10/11] graph: flatten edges that join to their right neighbor
From: James Coglan
When a merge commit is printed and its final parent is the same commit
that occupies the column to the right of the merge, this results in a
kink in the displayed edges:
* |
|\ \
| |/
| *
Graphs containing these shapes can be hard to read, as the expansion to
the right followed immediately by collapsing back to the left creates a
lot of zig-zagging edges, especially when many columns are present.
We can improve this by eliminating the zig-zag and having the merge's
final parent edge fuse immediately with its neighbor:
* |
|\|
| *
This reduces the horizontal width for the current commit by 2, and
requires one less row, making the graph display more compact. Taken in
combination with other graph-smoothing enhancements, it greatly
compresses the space needed to display certain histories:
*
|\
| * *
| |\ |\
| | * | *
| | | | |\
| | \| | *
| *-. \ | * |
| |\ \ \=>|/|\|
|/ / / / | | *
| | | / | * |
| | |/| |/
| | * * /
| * | |/
| |/ *
* |
|/
*
One of the test cases here cannot be correctly rendered in Git v2.23.0;
it produces this output following commit E:
| | *-. \ 5_E
| | |\ \ \
| |/ / / /
| | | / _
| |_|/
|/| |
The new implementation makes sure that the rightmost edge in this
history is not left dangling as above.
Signed-off-by: James Coglan
---
graph.c| 34 ++---
t/t4215-log-skewed-merges.sh | 80 +-
t/t6016-rev-list-graph-simplify-history.sh | 30
3 files changed, 116 insertions(+), 28 deletions(-)
diff --git a/graph.c b/graph.c
index 6391e393ec..7dd2fab625 100644
--- a/graph.c
+++ b/graph.c
@@ -538,8 +538,24 @@ static void graph_insert_into_new_columns(struct git_graph
*graph,
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;
@@ -585,6 +601,8 @@ static void graph_update_columns(struct git_graph *graph)
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
@@ -712,9 +730,6 @@ void graph_update(struct git_graph *graph, struct commit
*commit)
*/
graph_update_columns(graph);
- graph->prev_edges_added = graph->edges_added;
- graph->edges_added = graph->num_parents + graph->merge_layout - 2;
-
graph->expansion_row = 0;
/*
@@ -1039,7 +1054,7 @@ const char merge_chars[] = {'/', '|', '\\'};
static void graph_output_post_merge_line(struct git_graph *graph, struct
strbuf *sb)
{
int seen_this = 0;
- int i;
+ int i, j;
struct commit_list *first_parent = first_interesting_parent(graph);
int seen_parent = 0;
@@ -1071,16 +1086,19 @@ static void graph_output_post_merge_line(struct
git_graph *graph, struct strbuf
char c;
seen_this = 1;
- for (; parents; parents =
next_interesting_parent(graph, parents)) {
+ 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];
strbuf_write_column(sb,
&graph->new_columns[par_column], c);
- if (idx == 2)
- strbuf_
[PATCH v2 05/13] graph: remove `mapping_idx` and `graph_update_width()`
From: James Coglan
There's a duplication of logic between `graph_insert_into_new_columns()`
and `graph_update_width()`. `graph_insert_into_new_columns()` is called
repeatedly by `graph_update_columns()` with an `int *` that tracks the
offset into the `mapping` array where we should write the next value.
Each call to `graph_insert_into_new_columns()` effectively pushes one
column index and one "null" value (-1) onto the `mapping` array and
therefore increments `mapping_idx` by 2.
`graph_update_width()` duplicates this process: the `width` of the graph
is essentially the initial width of the `mapping` array before edges
begin collapsing. The `graph_update_width()` function's logic
effectively works out how many times `graph_insert_into_new_columns()`
was called based on the relationship of the current commit to the rest
of the graph.
I'm about to make some changes that make the assignment of values into
the `mapping` array more complicated. Rather than make
`graph_update_width()` more complicated at the same time, we can simply
remove this function and use `graph->width` to track the offset into the
`mapping` array as we're building it. This removes the duplication and
makes sure that `graph->width` is the same as the visual width of the
`mapping` array once `graph_update_columns()` is complete.
Signed-off-by: James Coglan
---
graph.c | 65 +
1 file changed, 10 insertions(+), 55 deletions(-)
diff --git a/graph.c b/graph.c
index 512ae16535..d724ef25c3 100644
--- a/graph.c
+++ b/graph.c
@@ -472,8 +472,7 @@ static int graph_find_new_column_by_commit(struct git_graph
*graph,
}
static void graph_insert_into_new_columns(struct git_graph *graph,
- struct commit *commit,
- int *mapping_index)
+ struct commit *commit)
{
int i = graph_find_new_column_by_commit(graph, commit);
@@ -487,50 +486,14 @@ static void graph_insert_into_new_columns(struct
git_graph *graph,
graph->new_columns[i].color = graph_find_commit_color(graph,
commit);
}
- graph->mapping[*mapping_index] = i;
- *mapping_index += 2;
-}
-
-static void graph_update_width(struct git_graph *graph,
- int is_commit_in_existing_columns)
-{
- /*
-* 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;
-
- /*
-* Even if the current commit has no parents to be printed, it
-* still takes up a column for itself.
-*/
- if (graph->num_parents < 1)
- max_cols++;
-
- /*
-* 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--;
-
- /*
-* Each column takes up 2 spaces
-*/
- graph->width = max_cols * 2;
+ graph->mapping[graph->width] = i;
+ graph->width += 2;
}
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;
/*
@@ -563,6 +526,8 @@ static void graph_update_columns(struct git_graph *graph)
for (i = 0; i < graph->mapping_size; i++)
graph->mapping[i] = -1;
+ graph->width = 0;
+
/*
* Populate graph->new_columns and graph->mapping
*
@@ -573,7 +538,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;
@@ -587,7 +551,6 @@ 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;
for (parent = first_interesting_parent(graph);
@@ -602,21 +565,18 @@ static void graph_update_columns(struct git_graph *graph)
!is_commit_in_columns) {
graph_increment_column_color(graph);
}
- graph_i
[PATCH v2 06/13] graph: extract logic for moving to GRAPH_PRE_COMMIT state
From: James Coglan
This computation is repeated in a couple of places and I need to add
another condition to it to implement a further improvement to the graph
rendering, so I'm extracting this into a function.
Signed-off-by: James Coglan
---
graph.c | 12
1 file changed, 8 insertions(+), 4 deletions(-)
diff --git a/graph.c b/graph.c
index d724ef25c3..bd7403065e 100644
--- a/graph.c
+++ b/graph.c
@@ -588,6 +588,12 @@ static void graph_update_columns(struct git_graph *graph)
graph->mapping_size--;
}
+static int graph_needs_pre_commit_line(struct git_graph *graph)
+{
+ return graph->num_parents >= 3 &&
+ graph->commit_index < (graph->num_columns - 1);
+}
+
void graph_update(struct git_graph *graph, struct commit *commit)
{
struct commit_list *parent;
@@ -643,8 +649,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;
@@ -714,8 +719,7 @@ static void graph_output_skip_line(struct git_graph *graph,
struct graph_line *l
*/
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);
--
gitgitgadget
[PATCH v2 02/13] graph: handle line padding in `graph_next_line()`
From: James Coglan
Now that the display width of graph lines is implicitly tracked via the
`graph_line` interface, the calls to `graph_pad_horizontally()` no
longer need to be located inside the individual output functions, where
the character counting was previously being done.
All the functions called by `graph_next_line()` generate a line of
output, then call `graph_pad_horizontally()`, and finally change the
graph state if necessary. As padding is the final change to the output
done by all these functions, it can be removed from all of them and done
in `graph_next_line()` instead.
I've also moved the guard in `graph_output_padding_line()` that checks
the graph has a commit; this function is only called by
`graph_next_line()` and we must not pad the `graph_line` if no commit is
set.
---
graph.c | 49 -
1 file changed, 20 insertions(+), 29 deletions(-)
diff --git a/graph.c b/graph.c
index 2f81a5d23d..4c68557b17 100644
--- a/graph.c
+++ b/graph.c
@@ -732,16 +732,6 @@ static void graph_output_padding_line(struct git_graph
*graph,
{
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
*/
@@ -749,8 +739,6 @@ static void graph_output_padding_line(struct git_graph
*graph,
graph_line_write_column(line, &graph->new_columns[i], '|');
graph_line_addch(line, ' ');
}
-
- graph_pad_horizontally(graph, line);
}
@@ -767,7 +755,6 @@ static void graph_output_skip_line(struct git_graph *graph,
struct graph_line *l
* of the graph is missing.
*/
graph_line_addstr(line, "...");
- graph_pad_horizontally(graph, line);
if (graph->num_parents >= 3 &&
graph->commit_index < (graph->num_columns - 1))
@@ -832,8 +819,6 @@ static void graph_output_pre_commit_line(struct git_graph
*graph,
graph_line_addch(line, ' ');
}
- graph_pad_horizontally(graph, line);
-
/*
* Increment graph->expansion_row,
* and move to state GRAPH_COMMIT if necessary
@@ -967,8 +952,6 @@ static void graph_output_commit_line(struct git_graph
*graph, struct graph_line
graph_line_addch(line, ' ');
}
- graph_pad_horizontally(graph, line);
-
/*
* Update graph->state
*/
@@ -1043,8 +1026,6 @@ static void graph_output_post_merge_line(struct git_graph
*graph, struct graph_l
}
}
- graph_pad_horizontally(graph, line);
-
/*
* Update graph->state
*/
@@ -1186,8 +1167,6 @@ static void graph_output_collapsing_line(struct git_graph
*graph, struct graph_l
}
}
- graph_pad_horizontally(graph, line);
-
/*
* Swap mapping and new_mapping
*/
@@ -1204,31 +1183,43 @@ static void graph_output_collapsing_line(struct
git_graph *graph, struct graph_l
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, &line);
- return 0;
+ break;
case GRAPH_SKIP:
graph_output_skip_line(graph, &line);
- return 0;
+ break;
case GRAPH_PRE_COMMIT:
graph_output_pre_commit_line(graph, &line);
- return 0;
+ break;
case GRAPH_COMMIT:
graph_output_commit_line(graph, &line);
- return 1;
+ shown_commit_line = 1;
+ break;
case GRAPH_POST_MERGE:
graph_output_post_merge_line(graph, &line);
- return 0;
+ break;
case GRAPH_COLLAPSING:
graph_output_collapsing_line(graph, &line);
- return 0;
+ 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)
--
gitgitgadget
[PATCH v2 01/13] graph: automatically track display width of graph lines
From: James Coglan
All the output functions called by `graph_next_line()` currently keep
track of how many printable chars they've written to the buffer, before
calling `graph_pad_horizontally()` to pad the line with spaces. Some
functions do this by incrementing a counter whenever they write to the
buffer, and others do it by encoding an assumption about how many chars
are written, as in:
graph_pad_horizontally(graph, sb, graph->num_columns * 2);
This adds a fair amount of noise to the functions' logic and is easily
broken if one forgets to increment the right counter or update the
calculations used for padding.
To make this easier to use, I'm introducing a new struct called
`graph_line` that wraps a `strbuf` and keeps count of its display width
implicitly. `graph_next_line()` wraps this around the `struct strbuf *`
it's given and passes a `struct graph_line *` to the output functions,
which use its interface.
The `graph_line` interface wraps the `strbuf_addch()`,
`strbuf_addchars()` and `strbuf_addstr()` functions, and adds the
`graph_line_write_column()` function for adding a single character with
color formatting. The `graph_pad_horizontally()` function can then use
the `width` field from the struct rather than taking a character count
as a parameter.
Signed-off-by: James Coglan
---
graph.c | 194 +---
1 file changed, 99 insertions(+), 95 deletions(-)
diff --git a/graph.c b/graph.c
index f53135485f..2f81a5d23d 100644
--- a/graph.c
+++ b/graph.c
@@ -112,14 +112,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 {
@@ -686,8 +714,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,12 +723,12 @@ 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;
@@ -719,11 +746,11 @@ static void graph_output_padding_line(struct git_graph
*graph,
* 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);
+ graph_pad_horizontally(graph, line);
}
@@ -733,14 +760,14 @@ 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)
{
/*
* O
[PATCH v2 04/13] graph: reduce duplication in `graph_insert_into_new_columns()`
From: James Coglan
I will shortly be making some changes to this function and so am trying
to simplify it. It currently contains some duplicated logic; both
branches the function can take assign the commit's column index into
the `mapping` array and increment `mapping_index`.
Here I change the function so that the only conditional behaviour is
that it appends the commit to `new_columns` if it's not present. All
manipulation of `mapping` now happens on a single code path.
Signed-off-by: James Coglan
---
graph.c | 20 +++-
1 file changed, 7 insertions(+), 13 deletions(-)
diff --git a/graph.c b/graph.c
index c9646d9e00..512ae16535 100644
--- a/graph.c
+++ b/graph.c
@@ -478,23 +478,17 @@ static void graph_insert_into_new_columns(struct
git_graph *graph,
int i = graph_find_new_column_by_commit(graph, commit);
/*
-* If the commit is already in the new_columns list, we don't need to
-* add it. Just update the mapping correctly.
+* If the commit is not already in the new_columns array, then add it
+* and record it as being in the final column.
*/
- if (i >= 0) {
- graph->mapping[*mapping_index] = i;
- *mapping_index += 2;
- return;
+ 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);
}
- /*
-* 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;
+ graph->mapping[*mapping_index] = i;
*mapping_index += 2;
- graph->num_new_columns++;
}
static void graph_update_width(struct git_graph *graph,
--
gitgitgadget
[PATCH v2 03/13] graph: reuse `find_new_column_by_commit()`
From: James Coglan
I will shortly be making some changes to
`graph_insert_into_new_columns()` and so am trying to simplify it. One
possible simplification is that we can extract the loop for finding the
element in `new_columns` containing the given commit.
`find_new_column_by_commit()` contains a very similar loop but it
returns a `struct column *` rather than an `int` offset into the array.
Here I'm introducing a version that returns `int` and using that in
`graph_insert_into_new_columns()` and `graph_output_post_merge_line()`.
Signed-off-by: James Coglan
---
graph.c | 48 +++-
1 file changed, 23 insertions(+), 25 deletions(-)
diff --git a/graph.c b/graph.c
index 4c68557b17..c9646d9e00 100644
--- a/graph.c
+++ b/graph.c
@@ -460,22 +460,31 @@ static unsigned short graph_find_commit_color(const
struct git_graph *graph,
return graph_get_current_column_color(graph);
}
+static int graph_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 i;
+ }
+ return -1;
+}
+
static void graph_insert_into_new_columns(struct git_graph *graph,
struct commit *commit,
int *mapping_index)
{
- int i;
+ int i = graph_find_new_column_by_commit(graph, commit);
/*
* 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 (i >= 0) {
+ graph->mapping[*mapping_index] = i;
+ *mapping_index += 2;
+ return;
}
/*
@@ -963,17 +972,6 @@ static void graph_output_commit_line(struct git_graph
*graph, struct graph_line
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;
-}
-
static void graph_output_post_merge_line(struct git_graph *graph, struct
graph_line *line)
{
int seen_this = 0;
@@ -1001,20 +999,20 @@ static void graph_output_post_merge_line(struct
git_graph *graph, struct graph_l
* edges.
*/
struct commit_list *parents = NULL;
- struct column *par_column;
+ int par_column;
seen_this = 1;
parents = first_interesting_parent(graph);
assert(parents);
- par_column = find_new_column_by_commit(graph,
parents->item);
- assert(par_column);
+ par_column = graph_find_new_column_by_commit(graph,
parents->item);
+ assert(par_column >= 0);
- graph_line_write_column(line, par_column, '|');
+ graph_line_write_column(line,
&graph->new_columns[par_column], '|');
for (j = 0; j < graph->num_parents - 1; j++) {
parents = next_interesting_parent(graph,
parents);
assert(parents);
- par_column = find_new_column_by_commit(graph,
parents->item);
- assert(par_column);
- graph_line_write_column(line, par_column, '\\');
+ par_column =
graph_find_new_column_by_commit(graph, parents->item);
+ assert(par_column >= 0);
+ graph_line_write_column(line,
&graph->new_columns[par_column], '\\');
graph_line_addch(line, ' ');
}
} else if (seen_this) {
--
gitgitgadget
[PATCH v2 12/13] graph: flatten edges that fuse with their right neighbor
From: James Coglan
When a merge commit is printed and its final parent is the same commit
that occupies the column to the right of the merge, this results in a
kink in the displayed edges:
* |
|\ \
| |/
| *
Graphs containing these shapes can be hard to read, as the expansion to
the right followed immediately by collapsing back to the left creates a
lot of zig-zagging edges, especially when many columns are present.
We can improve this by eliminating the zig-zag and having the merge's
final parent edge fuse immediately with its neighbor:
* |
|\|
| *
This reduces the horizontal width for the current commit by 2, and
requires one less row, making the graph display more compact. Taken in
combination with other graph-smoothing enhancements, it greatly
compresses the space needed to display certain histories:
*
|\
| * *
| |\ |\
| | * | *
| | | | |\
| | \| | *
| *-. \ | * |
| |\ \ \=>|/|\|
|/ / / / | | *
| | | / | * |
| | |/| |/
| | * * /
| * | |/
| |/ *
* |
|/
*
One of the test cases here cannot be correctly rendered in Git v2.23.0;
it produces this output following commit E:
| | *-. \ 5_E
| | |\ \ \
| |/ / / /
| | | / _
| |_|/
|/| |
The new implementation makes sure that the rightmost edge in this
history is not left dangling as above.
Signed-off-by: James Coglan
---
graph.c| 34 +
t/t4215-log-skewed-merges.sh | 56 ++
t/t6016-rev-list-graph-simplify-history.sh | 30 +---
3 files changed, 86 insertions(+), 34 deletions(-)
diff --git a/graph.c b/graph.c
index 63f8d18baa..80db74aee6 100644
--- a/graph.c
+++ b/graph.c
@@ -557,8 +557,24 @@ static void graph_insert_into_new_columns(struct git_graph
*graph,
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;
@@ -604,6 +620,8 @@ static void graph_update_columns(struct git_graph *graph)
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
@@ -731,9 +749,6 @@ void graph_update(struct git_graph *graph, struct commit
*commit)
*/
graph_update_columns(graph);
- graph->prev_edges_added = graph->edges_added;
- graph->edges_added = graph->num_parents + graph->merge_layout - 2;
-
graph->expansion_row = 0;
/*
@@ -1041,7 +1056,7 @@ const char merge_chars[] = {'/', '|', '\\'};
static void graph_output_post_merge_line(struct git_graph *graph, struct
graph_line *line)
{
int seen_this = 0;
- int i;
+ int i, j;
struct commit_list *first_parent = first_interesting_parent(graph);
int seen_parent = 0;
@@ -1073,16 +1088,19 @@ static void graph_output_post_merge_line(struct
git_graph *graph, struct graph_l
char c;
seen_this = 1;
- for (; parents; parents =
next_interesting_parent(graph, parents)) {
+ 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)
-
[PATCH v2 09/13] graph: commit and post-merge lines for left-skewed merges
From: James Coglan
Following the introduction of "left-skewed" merges, which are merges
whose first parent fuses with another edge to its left, we have some
more edge cases to deal with in the display of commit and post-merge
lines.
The current graph code handles the following cases for edges appearing
to the right of the commit (*) on commit lines. A 2-way merge is usually
followed by vertical lines:
| | |
| * |
| |\ \
An octopus merge (more than two parents) is always followed by edges
sloping to the right:
| | \ | |\
| *-. \ | *---. \
| |\ \ \| |\ \ \ \
A 2-way merge is followed by a right-sloping edge if the commit line
immediately follows a post-merge line for a commit that appears in the
same column as the current commit, or any column to the left of that:
| * | * |
| |\| |\ \
| * \ | | * \
| |\ \ | | |\ \
This commit introduces the following new cases for commit lines. If a
2-way merge skews to the left, then the edges to its right are always
vertical lines, even if the commit follows a post-merge line:
| | | | |\
| * | | * |
|/| | |/| |
A commit with 3 parents that skews left is followed by vertical edges:
| | |
| * |
|/|\ \
If a 3-way left-skewed merge commit appears immediately after a
post-merge line, then it may be followed the right-sloping edges, just
like a 2-way merge that is not skewed.
| |\
| * \
|/|\ \
Octopus merges with 4 or more parents that skew to the left will always
be followed by right-sloping edges, because the existing columns need to
expand around the merge.
| | \
| *-. \
|/|\ \ \
On post-merge lines, usually all edges following the current commit
slope to the right:
| * | |
| |\ \ \
However, if the commit is a left-skewed 2-way merge, the edges to its
right remain vertical. We also need to display a space after the
vertical line descending from the commit marker, whereas this line would
normally be followed by a backslash.
| * | |
|/| | |
If a left-skewed merge has more than 2 parents, then the edges to its
right are still sloped as they bend around the edges introduced by the
merge.
| * | |
|/|\ \ \
To handle these new cases, we need to know not just how many parents
each commit has, but how many new columns it adds to the display; this
quantity is recorded in the `edges_added` field for the current commit,
and `prev_edges_added` field for the previous commit.
Here, "column" refers to visual columns, not the logical columns of the
`columns` array. This is because even if all the commit's parents end up
fusing with existing edges, they initially introduce distinct edges in
the commit and post-merge lines before those edges collapse. For
example, a 3-way merge whose 2nd and 3rd parents fuse with existing
edges still introduces 2 visual columns that affect the display of edges
to their right.
| | | \
| | *-. \
| | |\ \ \
| |_|/ / /
|/| | / /
| | |/ /
| |/| |
| | | |
This merge does not introduce any *logical* columns; there are 4 edges
before and after this commit once all edges have collapsed. But it does
initially introduce 2 new edges that need to be accommodated by the
edges to their right.
Signed-off-by: James Coglan
---
graph.c | 63 +--
t/t4215-log-skewed-merges.sh | 147 ++-
2 files changed, 203 insertions(+), 7 deletions(-)
diff --git a/graph.c b/graph.c
index e37127f5ab..21edad8085 100644
--- a/graph.c
+++ b/graph.c
@@ -216,6 +216,46 @@ struct git_graph {
* |/| | | | | | | | | | *
*/
int merge_layout;
+ /*
+* The number of columns added to the graph by the current commit. For
+* 2-way and octopus merges, this is 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
[PATCH v2 00/13] Improve the readability of log --graph output
This series of patches are designed to improve the output of the log --graph command; their effect can be summed up in the following diagram: BeforeAfter --- * |\ | * * | |\ |\ | | * | * | | | | |\ | | \| | * | *-. \ | * | | |\ \ \ |/|\| |/ / / / | | * | | | / | * | | | |/| |/ | | * * / | * | |/ | |/ * * | |/ * These changes aim to make the edges in graph diagrams easier to read, by straightening lines and making certain kinds of topologies display more compactly. Three distinct changes are included. First, if the first parent of a merge fuses with an edge to the left of the commit, then we display that by making the edges fuse immediately rather than by drawing a line straight down and then having it track to the left. That is, where we currently display these graphs: | * | | | * | |\| | | |\ |/ /| |_|/ / | | |/| | | We will now display these merges as follows: | * | | | * |/| | |_|/| | | |/| | | This transformation is applied to merges with any number of parents, for example we currently display 3-parent merges like this: | *-. | | | *-. | |\ \ | | | |\ \ |/ / / | |_|/ / / | | | |/| | | | And we will now display them like this: | * | | | * |/|\| |_|/|\ | | | |/| | | | If the edge the first parent fuses with is separated from the commit by multiple columns, a horizontal edge is drawn just as we currently do in the 'collapsing' state. This change also affects the display of commit and post-merge lines in subtle ways that are more thoroughly described in the relevant commits. The second change is that if the final parent of a merge fuses with the edge to the right of the commit, then we can remove the zig-zag effect that currently results. We currently display these merges like this: * | |\ \ | |/ | * After these changes, this merge will now be displayed like so: * | |\| | * If the final parent fuses with an edge that's further to the right, its display is unchanged and it will still display like this: * | | | |\ \ \ \ | | |_|/ | |/| | | * | | The final structural change smooths out lines that are collapsing through commit lines. For example, consider the following history: *-. \ |\ \ \ | | * | | * | | | |/ / * | | |/ / * | |/ * This is now rendered so that commit lines display an edge using / instead of |, if that edge is tracking to the left both above and below the commit line. That results in this improved display: *-. \ |\ \ \ | | * | | * | | | |/ / * / / |/ / * / |/ * Taken together, these changes produce the change shown in the first diagram above, with the current rendering on the left and the new rendering on the right. A final addition to that set of changes fixes the coloring of dashes that are drawn next to octopus merges, in a manner compatible with all these changes. The early commits in this set are refactorings that make the functional changes easier to introduce. James Coglan (13): graph: automatically track display width of graph lines graph: handle line padding in `graph_next_line()` graph: reuse `find_new_column_by_commit()` graph: reduce duplication in `graph_insert_into_new_columns()` graph: remove `mapping_idx` and `graph_update_width()` graph: extract logic for moving to GRAPH_PRE_COMMIT state graph: example of graph output that can be simplified graph: tidy up display of left-skewed merges graph: commit and post-merge lines for left-skewed merges graph: rename `new_mapping` to `old_mapping` graph: smooth appearance of collapsing edges on commit lines graph: flatten edges that fuse with their right neighbor graph: fix coloring of octopus dashes graph.c| 646 - t/t3430-rebase-merges.sh | 2 +- t/t4202-log.sh | 2 +- t/t4214-log-graph-octopus.sh | 62 +- t/t4215-log-skewed-merges.sh | 257 t/t6016-rev-list-graph-simplify-history.sh | 30 +- 6 files changed, 673 insertions(+), 326 deletions(-) create mode 100755 t/t4215-log-skewed-merges.sh base-commit: 108b97dc372828f0e72e56bbb40cae8e1e83ece6 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-383%2Fjcoglan%2Fjc%2Fsimplify-graph-v2 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-383/jcoglan/jc/simpl
[PATCH v2 07/13] graph: example of graph output that can be simplified
From: James Coglan The commits following this one introduce a series of improvements to the layout of graphs, tidying up a few edge cases, namely: - merge whose first parent fuses with an existing column to the left - merge whose last parent fuses with its immediate neighbor on the right - edges that collapse to the left above and below a commit line This test case exemplifies these cases and provides a motivating example of the kind of history I'm aiming to clear up. The first parent of merge E is the same as the parent of H, so those edges fuse together. * H | | *-. E | |\ \ |/ / / | * B We can "skew" the display of this merge so that it doesn't introduce additional columns that immediately collapse: * H | | * E |/|\ | * B The last parent of E is D, the same as the parent of F which is the edge to the right of the merge. * F | \ *-. \ E |\ \ \ / / / / | / |/ * D The two edges leading to D could be fused sooner: rather than expanding the F edge around the merge and then letting the edges collapse, the F edge could fuse with the E edge in the post-merge line: * F | \ *-. | E |\ \| / / / | * D If this is combined with the "skew" effect above, we get a much cleaner graph display for these edges: * F | * | E /|\| | * D Finally, the edge leading from C to A appears jagged as it passes through the commit line for B: | * | C | |/ * | B |/ * A This can be smoothed out so that such edges are easier to read: | * | C | |/ * / B |/ * A --- t/t4215-log-skewed-merges.sh | 43 1 file changed, 43 insertions(+) create mode 100755 t/t4215-log-skewed-merges.sh diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh new file mode 100755 index 00..4582ba066a --- /dev/null +++ b/t/t4215-log-skewed-merges.sh @@ -0,0 +1,43 @@ +#!/bin/sh + +test_description='git log --graph of skewed merges' + +. ./test-lib.sh + +test_expect_success 'log --graph with merge fusing with its left and right neighbors' ' + cat >expect <<-\EOF && + * H + |\ + | * G + | |\ + | | * F + | | | + | | \ + | *-. \ E + | |\ \ \ + |/ / / / + | | | / + | | |/ + | | * D + | * | C + | |/ + * | B + |/ + * A + EOF + + git checkout --orphan _p && + test_commit A && + test_commit B && + git checkout -b _q @^ && test_commit C && + git checkout -b _r @^ && test_commit D && + git checkout _p && git merge --no-ff _q _r -m E && + git checkout _r && test_commit F && + git checkout _p && git merge --no-ff _r -m G && + git checkout @^^ && git merge --no-ff _p -m H && + + git log --graph --pretty=tformat:%s | sed "s/ *$//" >actual && + test_cmp expect actual +' + +test_done -- gitgitgadget
[PATCH v2 11/13] graph: smooth appearance of collapsing edges on commit lines
From: James Coglan
When a graph contains edges that are in the process of collapsing to the
left, but those edges cross a commit line, the effect is that the edges
have a jagged appearance:
*
|\
| *
| \
*-. \
|\ \ \
| | * |
| * | |
| |/ /
* | |
|/ /
* |
|/
*
We already takes steps to smooth edges like this when they're expanding;
when an edge appears to the right of a merge commit marker on a
GRAPH_COMMIT line immediately following a GRAPH_POST_MERGE line, we
render it as a `\`:
* \
|\ \
| * \
| |\ \
We can make a similar improvement to collapsing edges, making them
easier to follow and giving the overall graph a feeling of increased
symmetry:
*
|\
| *
| \
*-. \
|\ \ \
| | * |
| * | |
| |/ /
* / /
|/ /
* /
|/
*
To do this, we introduce a new special case for edges on GRAPH_COMMIT
lines that immediately follow a GRAPH_COLLAPSING line. By retaining a
copy of the `mapping` array used to render the GRAPH_COLLAPSING line in
the `old_mapping` array, we can determine that an edge is collapsing
through the GRAPH_COMMIT line and should be smoothed.
Signed-off-by: James Coglan
---
graph.c| 17 +---
t/t3430-rebase-merges.sh | 2 +-
t/t4202-log.sh | 2 +-
t/t4214-log-graph-octopus.sh | 32 +++---
t/t4215-log-skewed-merges.sh | 4 +--
t/t6016-rev-list-graph-simplify-history.sh | 4 +--
6 files changed, 35 insertions(+), 26 deletions(-)
diff --git a/graph.c b/graph.c
index 2315f3604d..63f8d18baa 100644
--- a/graph.c
+++ b/graph.c
@@ -297,10 +297,10 @@ 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 *old_mapping;
/*
@@ -1015,6 +1015,10 @@ static void graph_output_commit_line(struct git_graph
*graph, struct graph_line
graph_line_write_column(line, col, '\\');
else
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 {
graph_line_write_column(line, col, '|');
}
@@ -1211,6 +1215,11 @@ static void graph_output_collapsing_line(struct
git_graph *graph, struct graph_l
}
}
+ /*
+* 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
*/
diff --git a/t/t3430-rebase-merges.sh b/t/t3430-rebase-merges.sh
index 9efcf4808a..a30d27e9f3 100755
--- a/t/t3430-rebase-merges.sh
+++ b/t/t3430-rebase-merges.sh
@@ -408,7 +408,7 @@ test_expect_success 'octopus merges' '
| | * three
| * | two
| |/
- * | one
+ * / one
|/
o before-octopus
EOF
diff --git a/t/t4202-log.sh b/t/t4202-log.sh
index e803ba402e..ab0d021365 100755
--- a/t/t4202-log.sh
+++ b/t/t4202-log.sh
@@ -667,7 +667,7 @@ cat > expect <<\EOF
* | | fifth
* | | fourth
|/ /
-* | third
+* / third
|/
* second
* initial
diff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh
index 1b96276894..21bc600a82 100755
--- a/t/t4214-log-graph-octopus.sh
+++ b/t/t4214-log-graph-octopus.sh
@@ -31,9 +31,9 @@ test_expect_success 'log --graph with tricky octopus merge,
no color' '
| | | * 4
| | * | 3
| | |/
- | * | 2
+ | * / 2
| |/
- * | 1
+ * / 1
|/
* initial
EOF
@@ -51,9 +51,9 @@ test_expect_success 'log --graph with tricky octopus merge
with colors' '
| | | * 4
| | * | 3
| | |/
- | * | 2
+ | * / 2
| |/
- * | 1
+ * / 1
|/
* initial
EOF
@@ -72,9 +72,9 @@ test_expect_success 'log --graph with normal octopus merge,
no color' '
| | | * 4
[PATCH v2 08/13] graph: tidy up display of left-skewed merges
From: James Coglan
Currently, when we display a merge whose first parent is already present
in a column to the left of the merge commit, we display the first parent
as a vertical pipe `|` in the GRAPH_POST_MERGE line and then immediately
enter the GRAPH_COLLAPSING state. The first-parent line tracks to the
left and all the other parent lines follow it; this creates a "kink" in
those lines:
| *---.
| |\ \ \
|/ / / /
| | | *
This change tidies the display of such commits such that if the first
parent appears to the left of the merge, we render it as a `/` and the
second parent as a `|`. This reduces the horizontal and vertical space
needed to render the merge, and makes the resulting lines easier to
read.
| *-.
|/|\ \
| | | *
If the first parent is separated from the merge by several columns, a
horizontal line is drawn in a similar manner to how the GRAPH_COLLAPSING
state displays the line.
| | | *-.
| |_|/|\ \
|/| | | | *
This effect is applied to both "normal" two-parent merges, and to
octopus merges. It also reduces the vertical space needed for pre-commit
lines, as the merge occupies one less column than usual.
Before: After:
| * | *
| |\| |\
| | \ | * \
| | \ |/|\ \
| *-. \
| |\ \ \
Signed-off-by: James Coglan
---
graph.c | 125 +++
t/t4214-log-graph-octopus.sh | 20 +++---
t/t4215-log-skewed-merges.sh | 45 +++--
3 files changed, 144 insertions(+), 46 deletions(-)
diff --git a/graph.c b/graph.c
index bd7403065e..e37127f5ab 100644
--- a/graph.c
+++ b/graph.c
@@ -202,6 +202,20 @@ struct git_graph {
* previous commit.
*/
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 maximum number of columns that can be stored in the columns
* and new_columns arrays. This is also half the number of entries
@@ -313,6 +327,7 @@ 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->num_columns = 0;
graph->num_new_columns = 0;
graph->mapping_size = 0;
@@ -472,9 +487,11 @@ static int graph_find_new_column_by_commit(struct
git_graph *graph,
}
static void graph_insert_into_new_columns(struct git_graph *graph,
- struct commit *commit)
+ struct commit *commit,
+ int idx)
{
int i = graph_find_new_column_by_commit(graph, commit);
+ int mapping_idx;
/*
* If the commit is not already in the new_columns array, then add it
@@ -486,8 +503,26 @@ static void graph_insert_into_new_columns(struct git_graph
*graph,
graph->new_columns[i].color = graph_find_commit_color(graph,
commit);
}
- graph->mapping[graph->width] = i;
- graph->width += 2;
+ 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;
+
+ dist = idx - i;
+ shift = (dist > 1) ? 2 * dist - 3 : 1;
+
+ graph->merge_layout = (dist > 0) ? 0 : 1;
+ mapping_idx = graph->width + (graph->merge_layout - 1) * shift;
+ graph->width += 2 * graph->merge_layout;
+ } else {
+ mapping_idx = graph->width;
+ graph->width += 2;
+ }
+
+ graph->mapping[mapping_idx] = i;
}
static void graph_update_columns(struct git_graph *graph)
@@ -553,6 +588,7 @@ static void graph_update_columns(struct git_graph *graph)
if (col_commit == graph->commit) {
seen_this = 1;
graph->commit_index = i;
+ graph->merge_layout = -1;
for (parent = first_interesting_parent(graph);
[PATCH v2 13/13] graph: fix coloring of octopus dashes
From: James Coglan
In 04005834ed ("log: fix coloring of certain octopus merge shapes",
2018-09-01) there is a fix for the coloring of dashes following an
octopus merge. It makes a distinction between the case where all parents
introduce a new column, versus the case where the first parent collapses
into an existing column:
| *-. | *-.
| |\ \ | |\ \
| | | | |/ / /
The latter case means that the columns for the merge parents begin one
place to the left in the `new_columns` array compared to the former
case.
However, the implementation only works if the commit's parents are kept
in order as they map onto the visual columns, as we get the colors by
iterating over `new_columns` as we print the dashes. In general, the
commit's parents can arbitrarily merge with existing columns, and change
their ordering in the process.
For example, in the following diagram, the number of each column
indicates which commit parent appears in each column.
| | *---.
| | |\ \ \
| | |/ / /
| |/| | /
| |_|_|/
|/| | |
3 1 0 2
If the columns are colored (red, green, yellow, blue), then the dashes
will currently be colored yellow and blue, whereas they should be blue
and red.
To fix this, we need to look up each column in the `mapping` array,
which before the `GRAPH_COLLAPSING` state indicates which logical column
is displayed in each visual column. This implementation is simpler as it
doesn't have any edge cases, and it also handles how left-skewed first
parents are now displayed:
| *-.
|/|\ \
| | | |
0 1 2 3
The color of the first dashes is always the color found in `mapping` two
columns to the right of the commit symbol. Because commits are displayed
after all edges have been collapsed together and the visual columns
match the logical ones, we can find the visual offset of the commit
symbol using `commit_index`.
Signed-off-by: James Coglan
---
graph.c | 71 +++-
t/t4214-log-graph-octopus.sh | 10 ++---
2 files changed, 42 insertions(+), 39 deletions(-)
diff --git a/graph.c b/graph.c
index 80db74aee6..e3fd0ea5f8 100644
--- a/graph.c
+++ b/graph.c
@@ -684,6 +684,11 @@ static void graph_update_columns(struct git_graph *graph)
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)
{
/*
@@ -706,7 +711,7 @@ static int graph_num_expansion_rows(struct git_graph *graph)
* | * \
* |/|\ \
*/
- return (graph->num_parents + graph->merge_layout - 3) * 2;
+ return graph_num_dashed_parents(graph) * 2;
}
static int graph_needs_pre_commit_line(struct git_graph *graph)
@@ -934,47 +939,45 @@ static void graph_output_commit_char(struct git_graph
*graph, struct graph_line
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 = 3 - graph->merge_layout;
- 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 adde
[PATCH v2 10/13] graph: rename `new_mapping` to `old_mapping`
From: James Coglan
The change I'm about to make requires being able to inspect the mapping
array that was used to render the last GRAPH_COLLAPSING line while
rendering a GRAPH_COMMIT line. The `new_mapping` array currently exists
as a pre-allocated space for computing the next `mapping` array during
`graph_output_collapsing_line()`, but we can repurpose it to let us see
the previous `mapping` state.
To support this use it will make more sense if this array is named
`old_mapping`, as it will contain the mapping data for the previous line
we rendered, at the point we're rendering a commit line.
Signed-off-by: James Coglan
---
graph.c | 54 +++---
1 file changed, 27 insertions(+), 27 deletions(-)
diff --git a/graph.c b/graph.c
index 21edad8085..2315f3604d 100644
--- a/graph.c
+++ b/graph.c
@@ -259,7 +259,7 @@ struct git_graph {
/*
* 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;
/*
@@ -302,7 +302,7 @@ struct git_graph {
* 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.
*/
- int *new_mapping;
+ int *old_mapping;
/*
* The current default column color being used. This is
* stored as an index into the array column_colors.
@@ -388,7 +388,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
@@ -418,7 +418,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);
}
/*
@@ -1116,13 +1116,18 @@ static void graph_output_collapsing_line(struct
git_graph *graph, struct graph_l
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;
@@ -1143,14 +1148,14 @@ static void graph_output_collapsing_line(struct
git_graph *graph, struct graph_l
* 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.
@@ -1166,9 +1171,9 @@ static void graph_output_collapsing_line(struct git_graph
*graph, struct graph_l
* 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
@@ -1176,7 +
[PATCH v3 06/13] graph: extract logic for moving to GRAPH_PRE_COMMIT state
From: James Coglan
This computation is repeated in a couple of places and I need to add
another condition to it to implement a further improvement to the graph
rendering, so I'm extracting this into a function.
Signed-off-by: James Coglan
---
graph.c | 12
1 file changed, 8 insertions(+), 4 deletions(-)
diff --git a/graph.c b/graph.c
index d724ef25c3..bd7403065e 100644
--- a/graph.c
+++ b/graph.c
@@ -588,6 +588,12 @@ static void graph_update_columns(struct git_graph *graph)
graph->mapping_size--;
}
+static int graph_needs_pre_commit_line(struct git_graph *graph)
+{
+ return graph->num_parents >= 3 &&
+ graph->commit_index < (graph->num_columns - 1);
+}
+
void graph_update(struct git_graph *graph, struct commit *commit)
{
struct commit_list *parent;
@@ -643,8 +649,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;
@@ -714,8 +719,7 @@ static void graph_output_skip_line(struct git_graph *graph,
struct graph_line *l
*/
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);
--
gitgitgadget
[PATCH v3 00/13] Improve the readability of log --graph output
This series of patches are designed to improve the output of the log --graph command; their effect can be summed up in the following diagram: BeforeAfter --- * |\ | * * | |\ |\ | | * | * | | | | |\ | | \| | * | *-. \ | * | | |\ \ \ |/|\| |/ / / / | | * | | | / | * | | | |/| |/ | | * * / | * | |/ | |/ * * | |/ * These changes aim to make the edges in graph diagrams easier to read, by straightening lines and making certain kinds of topologies display more compactly. Three distinct changes are included. First, if the first parent of a merge fuses with an edge to the left of the commit, then we display that by making the edges fuse immediately rather than by drawing a line straight down and then having it track to the left. That is, where we currently display these graphs: | * | | | * | |\| | | |\ |/ /| |_|/ / | | |/| | | We will now display these merges as follows: | * | | | * |/| | |_|/| | | |/| | | This transformation is applied to merges with any number of parents, for example we currently display 3-parent merges like this: | *-. | | | *-. | |\ \ | | | |\ \ |/ / / | |_|/ / / | | | |/| | | | And we will now display them like this: | * | | | * |/|\| |_|/|\ | | | |/| | | | If the edge the first parent fuses with is separated from the commit by multiple columns, a horizontal edge is drawn just as we currently do in the 'collapsing' state. This change also affects the display of commit and post-merge lines in subtle ways that are more thoroughly described in the relevant commits. The second change is that if the final parent of a merge fuses with the edge to the right of the commit, then we can remove the zig-zag effect that currently results. We currently display these merges like this: * | |\ \ | |/ | * After these changes, this merge will now be displayed like so: * | |\| | * If the final parent fuses with an edge that's further to the right, its display is unchanged and it will still display like this: * | | | |\ \ \ \ | | |_|/ | |/| | | * | | The final structural change smooths out lines that are collapsing through commit lines. For example, consider the following history: *-. \ |\ \ \ | | * | | * | | | |/ / * | | |/ / * | |/ * This is now rendered so that commit lines display an edge using / instead of |, if that edge is tracking to the left both above and below the commit line. That results in this improved display: *-. \ |\ \ \ | | * | | * | | | |/ / * / / |/ / * / |/ * Taken together, these changes produce the change shown in the first diagram above, with the current rendering on the left and the new rendering on the right. A final addition to that set of changes fixes the coloring of dashes that are drawn next to octopus merges, in a manner compatible with all these changes. The early commits in this set are refactorings that make the functional changes easier to introduce. James Coglan (13): graph: automatically track display width of graph lines graph: handle line padding in `graph_next_line()` graph: reuse `find_new_column_by_commit()` graph: reduce duplication in `graph_insert_into_new_columns()` graph: remove `mapping_idx` and `graph_update_width()` graph: extract logic for moving to GRAPH_PRE_COMMIT state graph: example of graph output that can be simplified graph: tidy up display of left-skewed merges graph: commit and post-merge lines for left-skewed merges graph: rename `new_mapping` to `old_mapping` graph: smooth appearance of collapsing edges on commit lines graph: flatten edges that fuse with their right neighbor graph: fix coloring of octopus dashes graph.c| 646 - t/t3430-rebase-merges.sh | 2 +- t/t4202-log.sh | 2 +- t/t4214-log-graph-octopus.sh | 62 +- t/t4215-log-skewed-merges.sh | 257 t/t6016-rev-list-graph-simplify-history.sh | 30 +- 6 files changed, 673 insertions(+), 326 deletions(-) create mode 100755 t/t4215-log-skewed-merges.sh base-commit: 108b97dc372828f0e72e56bbb40cae8e1e83ece6 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-383%2Fjcoglan%2Fjc%2Fsimplify-graph-v3 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-383/jcoglan/jc/simpl
[PATCH v3 02/13] graph: handle line padding in `graph_next_line()`
From: James Coglan
Now that the display width of graph lines is implicitly tracked via the
`graph_line` interface, the calls to `graph_pad_horizontally()` no
longer need to be located inside the individual output functions, where
the character counting was previously being done.
All the functions called by `graph_next_line()` generate a line of
output, then call `graph_pad_horizontally()`, and finally change the
graph state if necessary. As padding is the final change to the output
done by all these functions, it can be removed from all of them and done
in `graph_next_line()` instead.
I've also moved the guard in `graph_output_padding_line()` that checks
the graph has a commit; this function is only called by
`graph_next_line()` and we must not pad the `graph_line` if no commit is
set.
Signed-off-by: James Coglan
---
graph.c | 49 -
1 file changed, 20 insertions(+), 29 deletions(-)
diff --git a/graph.c b/graph.c
index 2f81a5d23d..4c68557b17 100644
--- a/graph.c
+++ b/graph.c
@@ -732,16 +732,6 @@ static void graph_output_padding_line(struct git_graph
*graph,
{
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
*/
@@ -749,8 +739,6 @@ static void graph_output_padding_line(struct git_graph
*graph,
graph_line_write_column(line, &graph->new_columns[i], '|');
graph_line_addch(line, ' ');
}
-
- graph_pad_horizontally(graph, line);
}
@@ -767,7 +755,6 @@ static void graph_output_skip_line(struct git_graph *graph,
struct graph_line *l
* of the graph is missing.
*/
graph_line_addstr(line, "...");
- graph_pad_horizontally(graph, line);
if (graph->num_parents >= 3 &&
graph->commit_index < (graph->num_columns - 1))
@@ -832,8 +819,6 @@ static void graph_output_pre_commit_line(struct git_graph
*graph,
graph_line_addch(line, ' ');
}
- graph_pad_horizontally(graph, line);
-
/*
* Increment graph->expansion_row,
* and move to state GRAPH_COMMIT if necessary
@@ -967,8 +952,6 @@ static void graph_output_commit_line(struct git_graph
*graph, struct graph_line
graph_line_addch(line, ' ');
}
- graph_pad_horizontally(graph, line);
-
/*
* Update graph->state
*/
@@ -1043,8 +1026,6 @@ static void graph_output_post_merge_line(struct git_graph
*graph, struct graph_l
}
}
- graph_pad_horizontally(graph, line);
-
/*
* Update graph->state
*/
@@ -1186,8 +1167,6 @@ static void graph_output_collapsing_line(struct git_graph
*graph, struct graph_l
}
}
- graph_pad_horizontally(graph, line);
-
/*
* Swap mapping and new_mapping
*/
@@ -1204,31 +1183,43 @@ static void graph_output_collapsing_line(struct
git_graph *graph, struct graph_l
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, &line);
- return 0;
+ break;
case GRAPH_SKIP:
graph_output_skip_line(graph, &line);
- return 0;
+ break;
case GRAPH_PRE_COMMIT:
graph_output_pre_commit_line(graph, &line);
- return 0;
+ break;
case GRAPH_COMMIT:
graph_output_commit_line(graph, &line);
- return 1;
+ shown_commit_line = 1;
+ break;
case GRAPH_POST_MERGE:
graph_output_post_merge_line(graph, &line);
- return 0;
+ break;
case GRAPH_COLLAPSING:
graph_output_collapsing_line(graph, &line);
- return 0;
+ 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)
--
gitgitgadget
[PATCH v3 11/13] graph: smooth appearance of collapsing edges on commit lines
From: James Coglan
When a graph contains edges that are in the process of collapsing to the
left, but those edges cross a commit line, the effect is that the edges
have a jagged appearance:
*
|\
| *
| \
*-. \
|\ \ \
| | * |
| * | |
| |/ /
* | |
|/ /
* |
|/
*
We already takes steps to smooth edges like this when they're expanding;
when an edge appears to the right of a merge commit marker on a
GRAPH_COMMIT line immediately following a GRAPH_POST_MERGE line, we
render it as a `\`:
* \
|\ \
| * \
| |\ \
We can make a similar improvement to collapsing edges, making them
easier to follow and giving the overall graph a feeling of increased
symmetry:
*
|\
| *
| \
*-. \
|\ \ \
| | * |
| * | |
| |/ /
* / /
|/ /
* /
|/
*
To do this, we introduce a new special case for edges on GRAPH_COMMIT
lines that immediately follow a GRAPH_COLLAPSING line. By retaining a
copy of the `mapping` array used to render the GRAPH_COLLAPSING line in
the `old_mapping` array, we can determine that an edge is collapsing
through the GRAPH_COMMIT line and should be smoothed.
Signed-off-by: James Coglan
---
graph.c| 17 +---
t/t3430-rebase-merges.sh | 2 +-
t/t4202-log.sh | 2 +-
t/t4214-log-graph-octopus.sh | 32 +++---
t/t4215-log-skewed-merges.sh | 4 +--
t/t6016-rev-list-graph-simplify-history.sh | 4 +--
6 files changed, 35 insertions(+), 26 deletions(-)
diff --git a/graph.c b/graph.c
index 2315f3604d..63f8d18baa 100644
--- a/graph.c
+++ b/graph.c
@@ -297,10 +297,10 @@ 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 *old_mapping;
/*
@@ -1015,6 +1015,10 @@ static void graph_output_commit_line(struct git_graph
*graph, struct graph_line
graph_line_write_column(line, col, '\\');
else
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 {
graph_line_write_column(line, col, '|');
}
@@ -1211,6 +1215,11 @@ static void graph_output_collapsing_line(struct
git_graph *graph, struct graph_l
}
}
+ /*
+* 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
*/
diff --git a/t/t3430-rebase-merges.sh b/t/t3430-rebase-merges.sh
index 9efcf4808a..a30d27e9f3 100755
--- a/t/t3430-rebase-merges.sh
+++ b/t/t3430-rebase-merges.sh
@@ -408,7 +408,7 @@ test_expect_success 'octopus merges' '
| | * three
| * | two
| |/
- * | one
+ * / one
|/
o before-octopus
EOF
diff --git a/t/t4202-log.sh b/t/t4202-log.sh
index e803ba402e..ab0d021365 100755
--- a/t/t4202-log.sh
+++ b/t/t4202-log.sh
@@ -667,7 +667,7 @@ cat > expect <<\EOF
* | | fifth
* | | fourth
|/ /
-* | third
+* / third
|/
* second
* initial
diff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh
index 1b96276894..21bc600a82 100755
--- a/t/t4214-log-graph-octopus.sh
+++ b/t/t4214-log-graph-octopus.sh
@@ -31,9 +31,9 @@ test_expect_success 'log --graph with tricky octopus merge,
no color' '
| | | * 4
| | * | 3
| | |/
- | * | 2
+ | * / 2
| |/
- * | 1
+ * / 1
|/
* initial
EOF
@@ -51,9 +51,9 @@ test_expect_success 'log --graph with tricky octopus merge
with colors' '
| | | * 4
| | * | 3
| | |/
- | * | 2
+ | * / 2
| |/
- * | 1
+ * / 1
|/
* initial
EOF
@@ -72,9 +72,9 @@ test_expect_success 'log --graph with normal octopus merge,
no color' '
| | | * 4
[PATCH v3 05/13] graph: remove `mapping_idx` and `graph_update_width()`
From: James Coglan
There's a duplication of logic between `graph_insert_into_new_columns()`
and `graph_update_width()`. `graph_insert_into_new_columns()` is called
repeatedly by `graph_update_columns()` with an `int *` that tracks the
offset into the `mapping` array where we should write the next value.
Each call to `graph_insert_into_new_columns()` effectively pushes one
column index and one "null" value (-1) onto the `mapping` array and
therefore increments `mapping_idx` by 2.
`graph_update_width()` duplicates this process: the `width` of the graph
is essentially the initial width of the `mapping` array before edges
begin collapsing. The `graph_update_width()` function's logic
effectively works out how many times `graph_insert_into_new_columns()`
was called based on the relationship of the current commit to the rest
of the graph.
I'm about to make some changes that make the assignment of values into
the `mapping` array more complicated. Rather than make
`graph_update_width()` more complicated at the same time, we can simply
remove this function and use `graph->width` to track the offset into the
`mapping` array as we're building it. This removes the duplication and
makes sure that `graph->width` is the same as the visual width of the
`mapping` array once `graph_update_columns()` is complete.
Signed-off-by: James Coglan
---
graph.c | 65 +
1 file changed, 10 insertions(+), 55 deletions(-)
diff --git a/graph.c b/graph.c
index 512ae16535..d724ef25c3 100644
--- a/graph.c
+++ b/graph.c
@@ -472,8 +472,7 @@ static int graph_find_new_column_by_commit(struct git_graph
*graph,
}
static void graph_insert_into_new_columns(struct git_graph *graph,
- struct commit *commit,
- int *mapping_index)
+ struct commit *commit)
{
int i = graph_find_new_column_by_commit(graph, commit);
@@ -487,50 +486,14 @@ static void graph_insert_into_new_columns(struct
git_graph *graph,
graph->new_columns[i].color = graph_find_commit_color(graph,
commit);
}
- graph->mapping[*mapping_index] = i;
- *mapping_index += 2;
-}
-
-static void graph_update_width(struct git_graph *graph,
- int is_commit_in_existing_columns)
-{
- /*
-* 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;
-
- /*
-* Even if the current commit has no parents to be printed, it
-* still takes up a column for itself.
-*/
- if (graph->num_parents < 1)
- max_cols++;
-
- /*
-* 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--;
-
- /*
-* Each column takes up 2 spaces
-*/
- graph->width = max_cols * 2;
+ graph->mapping[graph->width] = i;
+ graph->width += 2;
}
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;
/*
@@ -563,6 +526,8 @@ static void graph_update_columns(struct git_graph *graph)
for (i = 0; i < graph->mapping_size; i++)
graph->mapping[i] = -1;
+ graph->width = 0;
+
/*
* Populate graph->new_columns and graph->mapping
*
@@ -573,7 +538,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;
@@ -587,7 +551,6 @@ 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;
for (parent = first_interesting_parent(graph);
@@ -602,21 +565,18 @@ static void graph_update_columns(struct git_graph *graph)
!is_commit_in_columns) {
graph_increment_column_color(graph);
}
- graph_i
[PATCH v3 07/13] graph: example of graph output that can be simplified
From: James Coglan The commits following this one introduce a series of improvements to the layout of graphs, tidying up a few edge cases, namely: - merge whose first parent fuses with an existing column to the left - merge whose last parent fuses with its immediate neighbor on the right - edges that collapse to the left above and below a commit line This test case exemplifies these cases and provides a motivating example of the kind of history I'm aiming to clear up. The first parent of merge E is the same as the parent of H, so those edges fuse together. * H | | *-. E | |\ \ |/ / / | * B We can "skew" the display of this merge so that it doesn't introduce additional columns that immediately collapse: * H | | * E |/|\ | * B The last parent of E is D, the same as the parent of F which is the edge to the right of the merge. * F | \ *-. \ E |\ \ \ / / / / | / |/ * D The two edges leading to D could be fused sooner: rather than expanding the F edge around the merge and then letting the edges collapse, the F edge could fuse with the E edge in the post-merge line: * F | \ *-. | E |\ \| / / / | * D If this is combined with the "skew" effect above, we get a much cleaner graph display for these edges: * F | * | E /|\| | * D Finally, the edge leading from C to A appears jagged as it passes through the commit line for B: | * | C | |/ * | B |/ * A This can be smoothed out so that such edges are easier to read: | * | C | |/ * / B |/ * A Signed-off-by: James Coglan --- t/t4215-log-skewed-merges.sh | 43 1 file changed, 43 insertions(+) create mode 100755 t/t4215-log-skewed-merges.sh diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh new file mode 100755 index 00..4582ba066a --- /dev/null +++ b/t/t4215-log-skewed-merges.sh @@ -0,0 +1,43 @@ +#!/bin/sh + +test_description='git log --graph of skewed merges' + +. ./test-lib.sh + +test_expect_success 'log --graph with merge fusing with its left and right neighbors' ' + cat >expect <<-\EOF && + * H + |\ + | * G + | |\ + | | * F + | | | + | | \ + | *-. \ E + | |\ \ \ + |/ / / / + | | | / + | | |/ + | | * D + | * | C + | |/ + * | B + |/ + * A + EOF + + git checkout --orphan _p && + test_commit A && + test_commit B && + git checkout -b _q @^ && test_commit C && + git checkout -b _r @^ && test_commit D && + git checkout _p && git merge --no-ff _q _r -m E && + git checkout _r && test_commit F && + git checkout _p && git merge --no-ff _r -m G && + git checkout @^^ && git merge --no-ff _p -m H && + + git log --graph --pretty=tformat:%s | sed "s/ *$//" >actual && + test_cmp expect actual +' + +test_done -- gitgitgadget
[PATCH v3 03/13] graph: reuse `find_new_column_by_commit()`
From: James Coglan
I will shortly be making some changes to
`graph_insert_into_new_columns()` and so am trying to simplify it. One
possible simplification is that we can extract the loop for finding the
element in `new_columns` containing the given commit.
`find_new_column_by_commit()` contains a very similar loop but it
returns a `struct column *` rather than an `int` offset into the array.
Here I'm introducing a version that returns `int` and using that in
`graph_insert_into_new_columns()` and `graph_output_post_merge_line()`.
Signed-off-by: James Coglan
---
graph.c | 48 +++-
1 file changed, 23 insertions(+), 25 deletions(-)
diff --git a/graph.c b/graph.c
index 4c68557b17..c9646d9e00 100644
--- a/graph.c
+++ b/graph.c
@@ -460,22 +460,31 @@ static unsigned short graph_find_commit_color(const
struct git_graph *graph,
return graph_get_current_column_color(graph);
}
+static int graph_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 i;
+ }
+ return -1;
+}
+
static void graph_insert_into_new_columns(struct git_graph *graph,
struct commit *commit,
int *mapping_index)
{
- int i;
+ int i = graph_find_new_column_by_commit(graph, commit);
/*
* 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 (i >= 0) {
+ graph->mapping[*mapping_index] = i;
+ *mapping_index += 2;
+ return;
}
/*
@@ -963,17 +972,6 @@ static void graph_output_commit_line(struct git_graph
*graph, struct graph_line
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;
-}
-
static void graph_output_post_merge_line(struct git_graph *graph, struct
graph_line *line)
{
int seen_this = 0;
@@ -1001,20 +999,20 @@ static void graph_output_post_merge_line(struct
git_graph *graph, struct graph_l
* edges.
*/
struct commit_list *parents = NULL;
- struct column *par_column;
+ int par_column;
seen_this = 1;
parents = first_interesting_parent(graph);
assert(parents);
- par_column = find_new_column_by_commit(graph,
parents->item);
- assert(par_column);
+ par_column = graph_find_new_column_by_commit(graph,
parents->item);
+ assert(par_column >= 0);
- graph_line_write_column(line, par_column, '|');
+ graph_line_write_column(line,
&graph->new_columns[par_column], '|');
for (j = 0; j < graph->num_parents - 1; j++) {
parents = next_interesting_parent(graph,
parents);
assert(parents);
- par_column = find_new_column_by_commit(graph,
parents->item);
- assert(par_column);
- graph_line_write_column(line, par_column, '\\');
+ par_column =
graph_find_new_column_by_commit(graph, parents->item);
+ assert(par_column >= 0);
+ graph_line_write_column(line,
&graph->new_columns[par_column], '\\');
graph_line_addch(line, ' ');
}
} else if (seen_this) {
--
gitgitgadget
[PATCH v3 09/13] graph: commit and post-merge lines for left-skewed merges
From: James Coglan
Following the introduction of "left-skewed" merges, which are merges
whose first parent fuses with another edge to its left, we have some
more edge cases to deal with in the display of commit and post-merge
lines.
The current graph code handles the following cases for edges appearing
to the right of the commit (*) on commit lines. A 2-way merge is usually
followed by vertical lines:
| | |
| * |
| |\ \
An octopus merge (more than two parents) is always followed by edges
sloping to the right:
| | \ | |\
| *-. \ | *---. \
| |\ \ \| |\ \ \ \
A 2-way merge is followed by a right-sloping edge if the commit line
immediately follows a post-merge line for a commit that appears in the
same column as the current commit, or any column to the left of that:
| * | * |
| |\| |\ \
| * \ | | * \
| |\ \ | | |\ \
This commit introduces the following new cases for commit lines. If a
2-way merge skews to the left, then the edges to its right are always
vertical lines, even if the commit follows a post-merge line:
| | | | |\
| * | | * |
|/| | |/| |
A commit with 3 parents that skews left is followed by vertical edges:
| | |
| * |
|/|\ \
If a 3-way left-skewed merge commit appears immediately after a
post-merge line, then it may be followed the right-sloping edges, just
like a 2-way merge that is not skewed.
| |\
| * \
|/|\ \
Octopus merges with 4 or more parents that skew to the left will always
be followed by right-sloping edges, because the existing columns need to
expand around the merge.
| | \
| *-. \
|/|\ \ \
On post-merge lines, usually all edges following the current commit
slope to the right:
| * | |
| |\ \ \
However, if the commit is a left-skewed 2-way merge, the edges to its
right remain vertical. We also need to display a space after the
vertical line descending from the commit marker, whereas this line would
normally be followed by a backslash.
| * | |
|/| | |
If a left-skewed merge has more than 2 parents, then the edges to its
right are still sloped as they bend around the edges introduced by the
merge.
| * | |
|/|\ \ \
To handle these new cases, we need to know not just how many parents
each commit has, but how many new columns it adds to the display; this
quantity is recorded in the `edges_added` field for the current commit,
and `prev_edges_added` field for the previous commit.
Here, "column" refers to visual columns, not the logical columns of the
`columns` array. This is because even if all the commit's parents end up
fusing with existing edges, they initially introduce distinct edges in
the commit and post-merge lines before those edges collapse. For
example, a 3-way merge whose 2nd and 3rd parents fuse with existing
edges still introduces 2 visual columns that affect the display of edges
to their right.
| | | \
| | *-. \
| | |\ \ \
| |_|/ / /
|/| | / /
| | |/ /
| |/| |
| | | |
This merge does not introduce any *logical* columns; there are 4 edges
before and after this commit once all edges have collapsed. But it does
initially introduce 2 new edges that need to be accommodated by the
edges to their right.
Signed-off-by: James Coglan
---
graph.c | 63 +--
t/t4215-log-skewed-merges.sh | 147 ++-
2 files changed, 203 insertions(+), 7 deletions(-)
diff --git a/graph.c b/graph.c
index e37127f5ab..21edad8085 100644
--- a/graph.c
+++ b/graph.c
@@ -216,6 +216,46 @@ struct git_graph {
* |/| | | | | | | | | | *
*/
int merge_layout;
+ /*
+* The number of columns added to the graph by the current commit. For
+* 2-way and octopus merges, this is 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
[PATCH v3 04/13] graph: reduce duplication in `graph_insert_into_new_columns()`
From: James Coglan
I will shortly be making some changes to this function and so am trying
to simplify it. It currently contains some duplicated logic; both
branches the function can take assign the commit's column index into
the `mapping` array and increment `mapping_index`.
Here I change the function so that the only conditional behaviour is
that it appends the commit to `new_columns` if it's not present. All
manipulation of `mapping` now happens on a single code path.
Signed-off-by: James Coglan
---
graph.c | 20 +++-
1 file changed, 7 insertions(+), 13 deletions(-)
diff --git a/graph.c b/graph.c
index c9646d9e00..512ae16535 100644
--- a/graph.c
+++ b/graph.c
@@ -478,23 +478,17 @@ static void graph_insert_into_new_columns(struct
git_graph *graph,
int i = graph_find_new_column_by_commit(graph, commit);
/*
-* If the commit is already in the new_columns list, we don't need to
-* add it. Just update the mapping correctly.
+* If the commit is not already in the new_columns array, then add it
+* and record it as being in the final column.
*/
- if (i >= 0) {
- graph->mapping[*mapping_index] = i;
- *mapping_index += 2;
- return;
+ 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);
}
- /*
-* 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;
+ graph->mapping[*mapping_index] = i;
*mapping_index += 2;
- graph->num_new_columns++;
}
static void graph_update_width(struct git_graph *graph,
--
gitgitgadget
[PATCH v3 01/13] graph: automatically track display width of graph lines
From: James Coglan
All the output functions called by `graph_next_line()` currently keep
track of how many printable chars they've written to the buffer, before
calling `graph_pad_horizontally()` to pad the line with spaces. Some
functions do this by incrementing a counter whenever they write to the
buffer, and others do it by encoding an assumption about how many chars
are written, as in:
graph_pad_horizontally(graph, sb, graph->num_columns * 2);
This adds a fair amount of noise to the functions' logic and is easily
broken if one forgets to increment the right counter or update the
calculations used for padding.
To make this easier to use, I'm introducing a new struct called
`graph_line` that wraps a `strbuf` and keeps count of its display width
implicitly. `graph_next_line()` wraps this around the `struct strbuf *`
it's given and passes a `struct graph_line *` to the output functions,
which use its interface.
The `graph_line` interface wraps the `strbuf_addch()`,
`strbuf_addchars()` and `strbuf_addstr()` functions, and adds the
`graph_line_write_column()` function for adding a single character with
color formatting. The `graph_pad_horizontally()` function can then use
the `width` field from the struct rather than taking a character count
as a parameter.
Signed-off-by: James Coglan
---
graph.c | 194 +---
1 file changed, 99 insertions(+), 95 deletions(-)
diff --git a/graph.c b/graph.c
index f53135485f..2f81a5d23d 100644
--- a/graph.c
+++ b/graph.c
@@ -112,14 +112,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 {
@@ -686,8 +714,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,12 +723,12 @@ 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;
@@ -719,11 +746,11 @@ static void graph_output_padding_line(struct git_graph
*graph,
* 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);
+ graph_pad_horizontally(graph, line);
}
@@ -733,14 +760,14 @@ 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)
{
/*
* O
[PATCH v3 10/13] graph: rename `new_mapping` to `old_mapping`
From: James Coglan
The change I'm about to make requires being able to inspect the mapping
array that was used to render the last GRAPH_COLLAPSING line while
rendering a GRAPH_COMMIT line. The `new_mapping` array currently exists
as a pre-allocated space for computing the next `mapping` array during
`graph_output_collapsing_line()`, but we can repurpose it to let us see
the previous `mapping` state.
To support this use it will make more sense if this array is named
`old_mapping`, as it will contain the mapping data for the previous line
we rendered, at the point we're rendering a commit line.
Signed-off-by: James Coglan
---
graph.c | 54 +++---
1 file changed, 27 insertions(+), 27 deletions(-)
diff --git a/graph.c b/graph.c
index 21edad8085..2315f3604d 100644
--- a/graph.c
+++ b/graph.c
@@ -259,7 +259,7 @@ struct git_graph {
/*
* 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;
/*
@@ -302,7 +302,7 @@ struct git_graph {
* 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.
*/
- int *new_mapping;
+ int *old_mapping;
/*
* The current default column color being used. This is
* stored as an index into the array column_colors.
@@ -388,7 +388,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
@@ -418,7 +418,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);
}
/*
@@ -1116,13 +1116,18 @@ static void graph_output_collapsing_line(struct
git_graph *graph, struct graph_l
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;
@@ -1143,14 +1148,14 @@ static void graph_output_collapsing_line(struct
git_graph *graph, struct graph_l
* 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.
@@ -1166,9 +1171,9 @@ static void graph_output_collapsing_line(struct git_graph
*graph, struct graph_l
* 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
@@ -1176,7 +
[PATCH v3 13/13] graph: fix coloring of octopus dashes
From: James Coglan
In 04005834ed ("log: fix coloring of certain octopus merge shapes",
2018-09-01) there is a fix for the coloring of dashes following an
octopus merge. It makes a distinction between the case where all parents
introduce a new column, versus the case where the first parent collapses
into an existing column:
| *-. | *-.
| |\ \ | |\ \
| | | | |/ / /
The latter case means that the columns for the merge parents begin one
place to the left in the `new_columns` array compared to the former
case.
However, the implementation only works if the commit's parents are kept
in order as they map onto the visual columns, as we get the colors by
iterating over `new_columns` as we print the dashes. In general, the
commit's parents can arbitrarily merge with existing columns, and change
their ordering in the process.
For example, in the following diagram, the number of each column
indicates which commit parent appears in each column.
| | *---.
| | |\ \ \
| | |/ / /
| |/| | /
| |_|_|/
|/| | |
3 1 0 2
If the columns are colored (red, green, yellow, blue), then the dashes
will currently be colored yellow and blue, whereas they should be blue
and red.
To fix this, we need to look up each column in the `mapping` array,
which before the `GRAPH_COLLAPSING` state indicates which logical column
is displayed in each visual column. This implementation is simpler as it
doesn't have any edge cases, and it also handles how left-skewed first
parents are now displayed:
| *-.
|/|\ \
| | | |
0 1 2 3
The color of the first dashes is always the color found in `mapping` two
columns to the right of the commit symbol. Because commits are displayed
after all edges have been collapsed together and the visual columns
match the logical ones, we can find the visual offset of the commit
symbol using `commit_index`.
Signed-off-by: James Coglan
---
graph.c | 71 +++-
t/t4214-log-graph-octopus.sh | 10 ++---
2 files changed, 42 insertions(+), 39 deletions(-)
diff --git a/graph.c b/graph.c
index 80db74aee6..e3fd0ea5f8 100644
--- a/graph.c
+++ b/graph.c
@@ -684,6 +684,11 @@ static void graph_update_columns(struct git_graph *graph)
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)
{
/*
@@ -706,7 +711,7 @@ static int graph_num_expansion_rows(struct git_graph *graph)
* | * \
* |/|\ \
*/
- return (graph->num_parents + graph->merge_layout - 3) * 2;
+ return graph_num_dashed_parents(graph) * 2;
}
static int graph_needs_pre_commit_line(struct git_graph *graph)
@@ -934,47 +939,45 @@ static void graph_output_commit_char(struct git_graph
*graph, struct graph_line
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 = 3 - graph->merge_layout;
- 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 adde
[PATCH v3 12/13] graph: flatten edges that fuse with their right neighbor
From: James Coglan
When a merge commit is printed and its final parent is the same commit
that occupies the column to the right of the merge, this results in a
kink in the displayed edges:
* |
|\ \
| |/
| *
Graphs containing these shapes can be hard to read, as the expansion to
the right followed immediately by collapsing back to the left creates a
lot of zig-zagging edges, especially when many columns are present.
We can improve this by eliminating the zig-zag and having the merge's
final parent edge fuse immediately with its neighbor:
* |
|\|
| *
This reduces the horizontal width for the current commit by 2, and
requires one less row, making the graph display more compact. Taken in
combination with other graph-smoothing enhancements, it greatly
compresses the space needed to display certain histories:
*
|\
| * *
| |\ |\
| | * | *
| | | | |\
| | \| | *
| *-. \ | * |
| |\ \ \=>|/|\|
|/ / / / | | *
| | | / | * |
| | |/| |/
| | * * /
| * | |/
| |/ *
* |
|/
*
One of the test cases here cannot be correctly rendered in Git v2.23.0;
it produces this output following commit E:
| | *-. \ 5_E
| | |\ \ \
| |/ / / /
| | | / _
| |_|/
|/| |
The new implementation makes sure that the rightmost edge in this
history is not left dangling as above.
Signed-off-by: James Coglan
---
graph.c| 34 +
t/t4215-log-skewed-merges.sh | 56 ++
t/t6016-rev-list-graph-simplify-history.sh | 30 +---
3 files changed, 86 insertions(+), 34 deletions(-)
diff --git a/graph.c b/graph.c
index 63f8d18baa..80db74aee6 100644
--- a/graph.c
+++ b/graph.c
@@ -557,8 +557,24 @@ static void graph_insert_into_new_columns(struct git_graph
*graph,
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;
@@ -604,6 +620,8 @@ static void graph_update_columns(struct git_graph *graph)
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
@@ -731,9 +749,6 @@ void graph_update(struct git_graph *graph, struct commit
*commit)
*/
graph_update_columns(graph);
- graph->prev_edges_added = graph->edges_added;
- graph->edges_added = graph->num_parents + graph->merge_layout - 2;
-
graph->expansion_row = 0;
/*
@@ -1041,7 +1056,7 @@ const char merge_chars[] = {'/', '|', '\\'};
static void graph_output_post_merge_line(struct git_graph *graph, struct
graph_line *line)
{
int seen_this = 0;
- int i;
+ int i, j;
struct commit_list *first_parent = first_interesting_parent(graph);
int seen_parent = 0;
@@ -1073,16 +1088,19 @@ static void graph_output_post_merge_line(struct
git_graph *graph, struct graph_l
char c;
seen_this = 1;
- for (; parents; parents =
next_interesting_parent(graph, parents)) {
+ 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)
-
[PATCH v3 08/13] graph: tidy up display of left-skewed merges
From: James Coglan
Currently, when we display a merge whose first parent is already present
in a column to the left of the merge commit, we display the first parent
as a vertical pipe `|` in the GRAPH_POST_MERGE line and then immediately
enter the GRAPH_COLLAPSING state. The first-parent line tracks to the
left and all the other parent lines follow it; this creates a "kink" in
those lines:
| *---.
| |\ \ \
|/ / / /
| | | *
This change tidies the display of such commits such that if the first
parent appears to the left of the merge, we render it as a `/` and the
second parent as a `|`. This reduces the horizontal and vertical space
needed to render the merge, and makes the resulting lines easier to
read.
| *-.
|/|\ \
| | | *
If the first parent is separated from the merge by several columns, a
horizontal line is drawn in a similar manner to how the GRAPH_COLLAPSING
state displays the line.
| | | *-.
| |_|/|\ \
|/| | | | *
This effect is applied to both "normal" two-parent merges, and to
octopus merges. It also reduces the vertical space needed for pre-commit
lines, as the merge occupies one less column than usual.
Before: After:
| * | *
| |\| |\
| | \ | * \
| | \ |/|\ \
| *-. \
| |\ \ \
Signed-off-by: James Coglan
---
graph.c | 125 +++
t/t4214-log-graph-octopus.sh | 20 +++---
t/t4215-log-skewed-merges.sh | 45 +++--
3 files changed, 144 insertions(+), 46 deletions(-)
diff --git a/graph.c b/graph.c
index bd7403065e..e37127f5ab 100644
--- a/graph.c
+++ b/graph.c
@@ -202,6 +202,20 @@ struct git_graph {
* previous commit.
*/
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 maximum number of columns that can be stored in the columns
* and new_columns arrays. This is also half the number of entries
@@ -313,6 +327,7 @@ 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->num_columns = 0;
graph->num_new_columns = 0;
graph->mapping_size = 0;
@@ -472,9 +487,11 @@ static int graph_find_new_column_by_commit(struct
git_graph *graph,
}
static void graph_insert_into_new_columns(struct git_graph *graph,
- struct commit *commit)
+ struct commit *commit,
+ int idx)
{
int i = graph_find_new_column_by_commit(graph, commit);
+ int mapping_idx;
/*
* If the commit is not already in the new_columns array, then add it
@@ -486,8 +503,26 @@ static void graph_insert_into_new_columns(struct git_graph
*graph,
graph->new_columns[i].color = graph_find_commit_color(graph,
commit);
}
- graph->mapping[graph->width] = i;
- graph->width += 2;
+ 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;
+
+ dist = idx - i;
+ shift = (dist > 1) ? 2 * dist - 3 : 1;
+
+ graph->merge_layout = (dist > 0) ? 0 : 1;
+ mapping_idx = graph->width + (graph->merge_layout - 1) * shift;
+ graph->width += 2 * graph->merge_layout;
+ } else {
+ mapping_idx = graph->width;
+ graph->width += 2;
+ }
+
+ graph->mapping[mapping_idx] = i;
}
static void graph_update_columns(struct git_graph *graph)
@@ -553,6 +588,7 @@ static void graph_update_columns(struct git_graph *graph)
if (col_commit == graph->commit) {
seen_this = 1;
graph->commit_index = i;
+ graph->merge_layout = -1;
for (parent = first_interesting_parent(graph);
