Magit: Implement more readable and semantic log graphs

[tarsius]

A long time ago there was some talk about making log graphs prettier. See #495, but note that the conversation began before then and continued afterwards.

For a while Magit optionally converted the ascii graph as output by git to use unicode characters instead, as seen in the first screenshot in #495. But that feature broke at some point and I decided to remove it instead of fixing it, see #2343.

At some point in between those two issues, I opened a another issue that outlined various issues with log graphs: #1425. Later I closed that because at the time I considered it a moonshot. The first point on that issue has been addressed by now, or rather we are using a work-around. Still it might be useful to read the initial post on that issue now, before moving on. But this issue replaces #1425.

The core change I still intend to make is to stop using git log --graph and instead use git log --parents and then format our own graphs based on that. We will have to:

1. Parse the git log --parents output. This should be easy.
2. Turn that into a pretty graph. This is hard.
3. Draw that graph.

I think we have basically two options for drawing the graph. We either draw it using text characters (ascii or unicode, user may choose), or we do so using vector graphics.

If we go with vector graphics, then one option would be svg. Emacs has built-in support for that; you can find a demo here. I don't know whether it is possible to draw over a buffer that also contains text. If it is not, and I suspect it does not, then we might as well use something else that generates an image which is then displayed in a separate window next to the window that contains the commit summaries etc.

A compromise would be continue to draw the graph as (monospaced) text, but to allow individual characters to be replaced with images, or an "image font".

The main reason I find Git's log graphs unreadable as soon as things get a bit more complicated is that it tries to hard to preserve horizontal space. In addition to making the complex graphs very hard to read, this also comes at the cost of wasting vertical space.

To fix that I intend to base our graph drawing on these two principals:

1. All commits of a given branch are drawn in the same column, even when that wastes horizontal space.

2. Arrange the branches based on their type (mainline, bug-fix, feature etc.).

   Also see #2948.

A graph might then look like this:

      *   <master> summary
*     |   <maint> summary
|   * |   <fix/14> symmary
*   | |   summary
*---' |   summary
*     |   summary
|     | * <feature/stuff> summary
|     *-' summary
|     *-. merge feature/cool
|     | * <feature/cool> summary
| *   | | summary
*-'   | | summary
|     *-' summary
|     *   summary
*-----'   summary
*         summary
...       (many commits)
*         summary
| *       <fix/1> summary      
*-'

Note how that wastes more horizontal space than git log --graph would, but unlike that it wastes no vertical space at all.

When using vector graphics, then this would look prettier of course.

We might as well waste even more horizontal space and align the summaries too (this should probably be optional:

      *   <master>        summary
*     |   <maint>         summary
|   * |   <fix/14>        symmary
*   | |                   summary
*---' |                   summary
*     |                   summary
|     | * <feature/stuff> summary
|     *-'                 summary
|     *-.                 merge feature/cool
|     | * <feature/cool>  summary
| *   | |                 summary
*-'   | |                 summary
|     *-'                 summary
|     *                   summary
*-----'                   summary
*                         summary
...                       (many commits)
*                         summary
| *                       <fix/1> summary      
*-'

Of course such an approach has issues of its own.

1. We need to avoid wasting too much horizontal space.

   feature/stuff uses the same column as feature/cool because the latter was already merged when the former was created. fix/14 does not use the same column as fix/13 because that wasn't merged yet. However fix/13 does use the same column as fix/1 because there are many commits in between the last fix/1 commit and the first fix/13 commit.

2. Graphs should probably generated/updated asynchronously. E.g. by the time we first encounter fix/14, we don't know yet that there is a recent fix/13 that hasn't been merged yet.

3. Also logs may be limited to a certain number of commits. So if no commits from fix/13 fall into the limit, then fix/14 would be displayed in the second (not third) column.

   But users can increase the limit, and then the graph would have to be adjusted, pushing fix/14 to the third column.

   The plan is to do the initial log parsing asynchronously too {TODO separate issue}. Which means that the graph might have to be adjusted even without user intervention.

   Or not. It matters less what part of the log has been inserted into the buffer, then it does what part is actually visible in the window. So moving in the buffer should probably also adjust the graph. But if the graph changes while scrolling, then that is confusing too. So it should only be done if it allows stopping to waste a large amount of horizontal waste. Not easy.

4. If a commit is both a merge commit, as well as a branch point, then it becomes hard to do express that on a single line when using ascii. With unicode it's easier but still a bit confusing. With vector graphics it's no issue at all.

   Express this:

   * 
   | *
   |/    (waste)
   *
   |\    (waste)
   | *
   *
   

   without any waste. Using ascii it looks confusing:

   *         *
   | *       | *
   *-        *<
   | *       | *
   *         *
   

5. Graph lines may "cross". That's also not easily expressed using ascii, sub-optimal in unicode, and not much of an issue using vector graphics.

6. Many others. To be updated.

---

Other details to take care of:

• #3602 Root commits should look different from other non-merge commits to be able to see orphan branches.

[cristobalito]

Would it not make more sense to make some of these changes in git itself?

[tarsius]

Would it not make more sense to make some of these changes in git itself?

Well yes, that would be nice, but I don't know enough C to do it that way.

[georgek]

After several years I've started working on a pretty graph again. I've been looking at using SVG for drawing it and had some good results so far.

Firstly, it is possible to have SVG and text in the same buffer, it just means the graph needs to be drawn in "tiles", or at least one SVG per line, so that the rest of each line can be text. It seems to work OK, apart from getting the SVGs to tile properly. This seems weird. I had to set the height of the SVGs to double the height of the text otherwise they won't tile, and then the text is aligned in a funny way with the SVGs. I wouldn't be surprised if it looks different when used with other font settings that I have (but playing with svg-test-height should help).

The nice thing is this method would allow graphs comparable to those of gitk. My current implementation uses only one line per commit, but it would need some extra heuristics to make it as nice as gitk.

As a fallback for cases with no SVG support it would be fairly easy for me to improve and modify my old code to be like tig which allows one line per commit. For no unicode support I don't think I can do better than git log.

So, for a normal repo like magit it looks quite nice so far:

My worst case is git.git, which doesn't look awful, but it is possible to improve this by copying gitk (in particular the merges with really old parents are disconnected and replaced with arrows in gitk):

The code is here: https://github.com/georgek/magit-pretty-graph

It will break with octopus merges and new heads (ie. if --all were used) but I know how to fix that. I'm sure there are many other ways it will break too. There is still a lot to do but I want to show this now before I go too far down the wrong path as I do want this to become part of magit.

[cben]

Very cool! For comparison, modern tig looks like this (omitting timestamp column):

$ cat ~/.tigrc
set line-graphics = utf-8
set main-view-commit-title-graph = v2
$ cd ~/magit; tig 79dc769
Jonas Bernoulli         ∙ magit-wip-commit-index: Remove unused CACHED-ONLY argument
Jonas Bernoulli         ∙ Favor --some over --any
Jonas Bernoulli         ∙ make: Move suppress-warnings to file where it is used
Jonas Bernoulli         ∙ Improve detection of branch at point
Jonas Bernoulli         ∙ magit-read-file-trace: Don't validate trace value
Jonas Bernoulli         ∙ magit-completion-read: Preserve this-command value
Noam Postavsky          ●─╮ Merge branch 'maint'
Noam Postavsky          │ ●─╮ Merge branch 'np/file-hook-errors' [#3505]
Noam Postavsky          │ │ ∙ git-commit-file-not-found: Handle git-rebase-filename-regexp too
Noam Postavsky          │ │ ∙ Move cygwin filename handling to ffnf-functions
Noam Postavsky          │ │ ∙ git-commit-setup-font-lock: Don't fail in non-existent directory
Jonas Bernoulli         ∙ │ │ magit-gitignore-popup: Fix autoload
Jonas Bernoulli         ∙ │ │ magit-no-confirm: Fix description of Custom choice item
Jonas Bernoulli         ∙ │ │ travis: Fetch ghub-graphql.el
Jonas Bernoulli         ∙ │ │ magit-edit-thing: New stub command
Bob Uhl                 ∙ │ │ Quote regexp-meaningful characters in function name
Jonas Bernoulli         ∙ │ │ make: Add treepy to the load-path
Jonas Bernoulli         ∙ │ │ magit-dwim-selection: Add entries for forge commands
Jonas Bernoulli         ∙ │ │ magit-branch-rename-push-target: Replace github-only with forge-only
Jonas Bernoulli         ∙ │ │ magit-buffer-lock-functions: Funcall the function
Jonas Bernoulli         ∙ │ │ Fontify commit and note messages using configured major-mode
Jonas Bernoulli         ∙ │ │ Use the same faces for commit message and note headings as for hunks
Jonas Bernoulli         ∙ │ │ Allow specifying the face to use to highlight certain section
Jonas Bernoulli         ●─│─│─╮ Merge branch 'status-logs' [#3518]
Jonas Bernoulli         │ │ │ ∙ Change order and initial visibility of logs in status buffer
Jonas Bernoulli         │ │ │ ∙ Treat recent commits as a variant of unpushed commits
Jonas Bernoulli         ∙─│─│─╯ magit-merge-into: Offer only local branches defaulting to upstream
Jonas Bernoulli         ∙ │ │ Unset $GIT_{DIR,WORK_TREE} when loading magit
Jonas Bernoulli         ∙ │ │ magit-browse-thing: New stub command
Jonas Bernoulli         ∙ │ │ magit-list-publishing-branches: Fix performance issue

$ cd ~/git/; tig ffc6fa0
Junio C Hamano                 ∙ Fourth batch for 2.19 cycle
Junio C Hamano                 ●─╮ Merge branch 'as/sequencer-customizable-comment-char'
Aaron Schrab                   │ ∙ sequencer: use configured comment character
Junio C Hamano                 ●─│─╮ Merge branch 'sb/blame-color'
Jeff King                      │ │ ∙ blame: prefer xsnprintf to strcpy for colors
Junio C Hamano                 ●─│─│─╮ Merge branch 'nd/command-list'
Johannes Schindelin            │ │ │ ∙ vcbuild/README: update to accommodate for missing common-cmds.h
Junio C Hamano                 ●─│─│─│─╮ Merge branch 'es/test-lint-one-shot-export'
Eric Sunshine                  │ │ │ │ ∙ t/check-non-portable-shell: detect "FOO=bar shell_func"
Eric Sunshine                  │ │ │ │ ∙ t/check-non-portable-shell: make error messages more compact
Eric Sunshine                  │ │ │ │ ∙ t/check-non-portable-shell: stop being so polite
Eric Sunshine                  │ │ │ │ ∙ t6046/t9833: fix use of "VAR=VAL cmd" with a shell function
Junio C Hamano                 │ │ │ │ ●─╮ Merge branch 'jc/t3404-one-shot-export-fix' into es/test-lint-one-shot-export
Junio C Hamano                 ●─│─│─│─│─│─╮ Merge branch 'wc/find-commit-with-pattern-on-detached-head'
William Chargin                │ │ │ │ │ │ ∙ sha1-name.c: for ":/", find detached HEAD commits
Junio C Hamano                 ●─│─│─│─│─│─│─╮ Merge branch 'jc/t3404-one-shot-export-fix'
Junio C Hamano                 │ │ │ │ │ ∙─│─╯ t3404: fix use of "VAR=VAL cmd" with a shell function
Junio C Hamano                 ●─│─│─│─│─│─│─╮ Merge branch 'mk/merge-in-sparse-checkout'
Max Kirillov                   │ │ │ │ │ │ │ ∙ unpack-trees: do not fail reset because of unmerged skipped entry
Junio C Hamano                 ●─│─│─│─│─│─│─│─╮ Merge branch 'hs/push-cert-check-cleanup'
Henning Schild                 │ │ │ │ │ │ │ │ ∙ gpg-interface: make parse_gpg_output static and remove from interface header
Henning Schild                 │ │ │ │ │ │ │ │ ∙ builtin/receive-pack: use check_signature from gpg-interface
Junio C Hamano                 ●─│─│─│─│─│─│─│─│─╮ Merge branch 'jk/empty-pick-fix'
Jeff King                      │ │ │ │ │ │ │ │ │ ∙ sequencer: don't say BUG on bogus input
Jeff King                      │ │ │ │ │ │ │ │ │ ∙ sequencer: handle empty-set cases consistently
Junio C Hamano                 ●─│─│─│─│─│─│─│─│─│─╮ Merge branch 'bp/log-ref-write-fd-with-strbuf'
Ben Peart                      │ │ │ │ │ │ │ │ │ │ ∙ convert log_ref_write_fd() to use strbuf
Junio C Hamano                 ●─│─│─│─│─│─│─│─│─│─│─╮ Merge branch 'jt/partial-clone-fsck-connectivity'
Jonathan Tan                   │ │ │ │ │ │ │ │ │ │ │ ∙ clone: check connectivity even if clone is partial
Jonathan Tan                   │ │ │ │ │ │ │ │ │ │ │ ∙ upload-pack: send refs' objects despite "filter"

I must say personally I like tig's better (bias disclaimer: I use tig all the time) for satisfying what you called above property "(1) All commits of a given branch are drawn in the same column, even when that wastes horizontal space."

Whereas above svg graph minimizes line crosses and horizonal waste but suffers from branch lines zigzagging all the time making them harder to follow (a problem shared with gitk).
Note especially places where a line splits without a commit (EDIT: the 2 bottom ellipses):

do I read these right that these 3 places are all the same branch? Very hard to follow by eye :-(

In comparison, tig does all splits from the commit they came from, somewhere far below (note the ┴ chars):

...
2018-06-09 21:16 -0700 Elijah Newren                  │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ∙ merge-recursive: fix numerous argument alignment issues
2018-06-09 21:16 -0700 Elijah Newren                  │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ∙ merge-recursive: fix miscellaneous grammar error in comment
2018-06-28 12:55 -0700 Junio C Hamano                 ∙─│─│─│─┴─│─│─│─┴─│─┴─│─│─│─│─│─┴─┴─│─│─│─┴─┴─│─│─│─│─╯ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ Second batch for 2.19 cycle

In this case, the common parent commit is so far down, and so many vertical lines, it's not feasible to follow:

but for small cases I like the ability to follow 1 column with my eye...

(I'm ignoring here colored lines vs B&W. you could always add color later.)

---

BTW, for point (4) above "If a commit is both a merge commit, as well as a branch point", indeed hard with ascii; tig once did it badly but nowday does a pretty good job using ⎨ U+23A8 LEFT CURLY BRACKET MIDDLE PIECE + rounded box drawing:

 │ │ │ │ │ │ o Sort array of queue names
 M─│─│─│─│─⎨ │ Merge pull request #16390 from mzazrivec/dont_include_full_path_into_gettext_catalogs
 │ │ │ │ │ o │ Don't include full file paths into gettext catalogs
 M─│─│─│─│─│─⎨ Merge pull request #16391 from chrisarcand/bz-1509172
 │ │ │ │ │ │ o settings_for_resource shouldn't blow up if the instance isn't saved yet
 M─│─│─│─│─│─╯ Merge pull request #16376 from karelhala/mwComplianceAssign

[georgek]

Essentially the difference between tig and gitk is that tig always grows out by appending to the right, while gitk grows by pushing out from the left. With box drawing the tig algorithm is the only one that works, I think. It's what I came up with when I tried to implement that same in emacs several years ago (I hadn't seen tig at that point).
The advantage gitk has is it can break very long vertical lines that you couldn't possibly follow by eye anyway. (It uses up and down arrows to break these). This reduces the complexity of the displayed graph and even makes it possible to display it within a given screen width (git log --graph and tig very quickly overflow their width as shown above).
From reading around online it looked to me like more people prefer gitk than tig, but obviously that wasn't a rigorous survey. Personally I think gitk does a better job because it isn't limited by box drawing characters.

[cben]

For comparison, here's gitg on same magit history:

This one looks pretty similar to tig, except pretty curvy lines.
However on git it gives this annoying view:

As you can see near the bottom, it too can collapse long branches with arrows (configurable threshold).
So you may want to play with it to see how a tig-like layout interacts with collapsing.

But due to the annoying ordering in this case, everything is distant and collapsed, so next page gets very silly:

It has a "topological order" configuration toggle, which once upon a time I really loved but nowdays doesn't seem to affect much — only a little bit in "all commits" view :-(

[Lenbok]

Is there any progress on integrating the display routines from magit-pretty-graph by @georgek into magit? It looks and renders super nice, I find it much more intelligible than the disconnected ascii graph, so it would already be a step ahead of the current display if the magit actions working.

[dabrahams]

Regarding display and collapsing, I'd like to suggest a different orientation, which might lead to different answers. Instead of trying to make an arbitrarily complicated commit graph intelligible, suppose magit aimed at the problem of making a graph of PRs that could be un-collapsed to reveal more detail?

Many projects/devs end up using rebases and even squashes to keep their commit history from “getting out of hand” even though it hurts bisection, merges, and comprehensibility. If their tools would show them something that hides detail by default (more like what you get from --first-parent), with the ability to explore more deeply when necessary, maybe there would be less history-rewriting-to-make-the-graph-pretty.