How to understand git log --graph

With Git 2.25 (Q1 2020), The implementation of "git log --graph" got refactored and then its output got simplified.

That in turn can fix the color for some cases.
The following provides an illustration on how colors and edges are managed with git log --graph.

See commit d784d97 (12 Nov 2019) by Denton Liu (Denton-L).
See commit bbb13e8, commit 92beecc, commit 479db18, commit 0195285, commit d62893e, commit 0f0f389, commit 458152c, commit ee7abb5, commit 46ba2ab, commit a551fd5, commit 9157a2a, commit 210179a, commit fbccf25 (15 Oct 2019) by James Coglan (jcoglan).
^{(Merged by Junio C Hamano -- gitster -- in commit 0be5caf, 01 Dec 2019)}

graph: fix coloring of octopus dashes

^{Signed-off-by: James Coglan}

In 04005834ed ("log: fix coloring of certain octopus merge shapes", 2018-09-01, Git v2.20.0-rc0 -- merge listed in batch #6), 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.

Regarding edges (still with Git 2.25, Q1 2020):

graph: smooth appearance of collapsing edges on commit lines

^{Signed-off-by: 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.

More generally:

graph: commit and post-merge lines for left-skewed merges

^{Signed-off-by: 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.

The classic output has been simplified:

graph: example of graph output that can be simplified

^{Signed-off-by: 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

Since recent updates to the log graph rendering code, drawing certain merges started triggering an assert on a condition that would no longer hold true, which has been corrected with Git 2.25 (Q1 2020).

See commit a1087c9, commit 0d251c3 (07 Jan 2020) by Derrick Stolee (derrickstolee).
^{(Merged by Junio C Hamano -- gitster -- in commit 1f5f3ff, 08 Jan 2020)}

graph: drop assert() for merge with two collapsing parents

^{Helped-by: Jeff King}
^{Reported-by: Bradley Smith}
^{Signed-off-by: Derrick Stolee}

When "git log --graph" shows a merge commit that has two collapsing lines, like:
| | | | *
| |_|_|/|
|/| | |/
| | |/|
| |/| |
| * | |
* | | |
we trigger an assert():
graph.c:1228: graph_output_collapsing_line: Assertion
              `graph->mapping[i - 3] == target' failed.
The assert was introduced by eaf158f8 ("graph API: Use horizontal lines for more compact graphs", 2009-04-21, Git v1.6.4-rc0 -- merge), which is quite old.
This assert is trying to say that when we complete a horizontal line with a single slash, it is because we have reached our target.

It is actually the _second_ collapsing line that hits this assert.
The reason we are in this code path is because we are collapsing the first line, and in that case we are hitting our target now that the horizontal line is complete.
However, the second line cannot be a horizontal line, so it will collapse without horizontal lines. In this case, it is inappropriate to assert that we have reached our target, as we need to continue for another column before reaching the target.
Dropping the assert is safe here.

The new behavior in 0f0f389f12 ("graph: tidy up display of left-skewed merges", 2019-10-15, Git v2.25.0-rc0 -- merge listed in batch #2) caused the behavior change that made this assertion failure possible.
In addition to making the assert possible, it also changed how multiple edges collapse.

In a larger example, the current code will output a collapse as follows:
| | | | | | *
| |_|_|_|_|/|\
|/| | | | |/ /
| | | | |/| /
| | | |/| |/
| | |/| |/|
| |/| |/| |
| | |/| | |
| | * | | |
However, the intended collapse should allow multiple horizontal lines as follows:
| | | | | | *
| |_|_|_|_|/|\
|/| | | | |/ /
| | |_|_|/| /
| |/| | | |/
| | | |_|/|
| | |/| | |
| | * | | |
This behavior is not corrected by this change, but is noted for a later update.

Rendering by "git log --graph" of ancestry lines leading to a merge commit were made suboptimal to waste vertical space a bit with a recent update, which has been corrected with Git 2.26 (Q1 2020).

See commit c958d3b, commit 8588932 (08 Jan 2020) by Derrick Stolee (derrickstolee).
^{(Merged by Junio C Hamano -- gitster -- in commit d52adee, 30 Jan 2020)}

graph: fix collapse of multiple edges

^{Signed-off-by: Derrick Stolee}

This fix resolves the previously-added test_expect_failure in t4215-log-skewed-merges.sh.

The issue lies in the "else" condition while updating the mapping inside graph_output_collapsing_line().
In 0f0f389f ("graph: tidy up display of left-skewed merges", 2019-10-15, Git v2.25.0-rc0 -- merge listed in batch #2), the output of left-skewed merges was changed to allow an immediate horizontal edge in the first parent, output by graph_output_post_merge_line() instead of by graph_output_collapsing_line().
This condensed the first line behavior as follows:

Before 0f0f389f:
| | | | | | *-.
| | | | | | |\ \
| |_|_|_|_|/ | |
|/| | | | | / /
After 0f0f389f:
| | | | | | *
| |_|_|_|_|/|\
|/| | | | |/ /
| | | | |/| /
However, a very subtle issue arose when the second and third parent edges are collapsed in later steps. The second parent edge is now immediately adjacent to a vertical edge. This means that the condition
} else if (graph->mapping[i - 1] < 0) {
in graph_output_collapsing_line() evaluates as false. The block for this condition was the only place where we connected the target column with the current position with horizontal edge markers.

In this case, the final "else" block is run, and the edge is marked as horizontal, but did not back-fill the blank columns between the target and the current edge.
Since the second parent edge is marked as horizontal, the third parent edge is not marked as horizontal.
This causes the output to continue as follows:

Before this change:
| | | | | | *
| |_|_|_|_|/|\
|/| | | | |/ /
| | | | |/| /
| | | |/| |/
| | |/| |/|
| |/| |/| |
| | |/| | |
By adding the logic for "filling" a horizontal edge between the target column and the current column, we are able to resolve the issue.

After this change:
| | | | | | *
| |_|_|_|_|/|\
|/| | | | |/ /
| | |_|_|/| /
| |/| | | |/
| | | |_|/|
| | |/| | |
This output properly matches the expected blend of the edge behavior before 0f0f389f and the merge commit rendering from 0f0f389f.

Git works from the current commit looking at ancestors. Branches are not "entities", they are (moving) references. There is no way for git log (or gitk which has a different color scheme but is analoguous to git log --graph or tig) to know if the current branch is the descendant of branch A or branch B. It only knows parents. From man git-log:

   git log -p -m --first-parent
       Shows the history including change diffs, but only from the "main 
       branch"   perspective, skipping commits that come from merged
       branches, and showing full diffs of changes introduced by the merges. 
       This makes sense only when following a strict policy of merging
       all topic branches when staying on a single integration branch.

Would somewhat address your concern. git log by default use current checked out commit as a reference (identical to executing git log HEAD

While I personnaly think the man page is quite clear for git, you may want to take a look at gitk or tig. The former is a graphical interface the later is a terminal-like minimal gitk tool. I use both depending on what I want to do.

How to understand git log --graph

`graph`: fix coloring of octopus dashes

`graph`: smooth appearance of collapsing edges on commit lines

`graph`: commit and post-merge lines for left-skewed merges

`graph`: example of graph output that can be simplified

`graph`: drop assert() for merge with two collapsing parents

`graph`: fix collapse of multiple edges

Tags:

Git

Git Log

Related

Recent Posts

How to understand git log --graph

graph: fix coloring of octopus dashes

graph: smooth appearance of collapsing edges on commit lines

graph: commit and post-merge lines for left-skewed merges

graph: example of graph output that can be simplified

graph: drop assert() for merge with two collapsing parents

graph: fix collapse of multiple edges

Tags:

Git

Git Log

Related

`graph`: fix coloring of octopus dashes

`graph`: smooth appearance of collapsing edges on commit lines

`graph`: commit and post-merge lines for left-skewed merges

`graph`: example of graph output that can be simplified

`graph`: drop assert() for merge with two collapsing parents

`graph`: fix collapse of multiple edges