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:

    Before                    After
    ------                    -----

    *
    |\
    | *                       *
    | |\                      |\
    | | *                     | *
    | | |                     | |\
    | |  \                    | | *
    | *-. \                   | * |
    | |\ \ \                  |/|\|
    |/ / / /                  | | *
    | | | /                   | * |
    | | |/                    | |/
    | | *                     * /
    | * |                     |/
    | |/                      *
    * |
    |/
    *

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

Submitted-As: https://public-inbox.org/git/pull.383.v3.git.1571183279.gitgitgadget@gmail.com
In-Reply-To: https://public-inbox.org/git/pull.383.git.gitgitgadget@gmail.com
In-Reply-To: https://public-inbox.org/git/pull.383.v2.git.1571182864.gitgitgadget@gmail.com