Flog v2

[rbong]

Requests for changes in v2 and feedback on planned changes welcome.

Major changes:

• Rewrite in vim9script, subsequent speed improvements
• Rewrite performance-sensitive portions of Flog in Lua
• Flog will draw the commit graph itself
• Flog will be able to position the cursor directly on the commit
• Better commit graph highlighting
• Better default format commit content highlighting
• API will be restructured
• "Command" wording will be changed to avoid naming confusion with "Vim commands"
  • "Command windows" will be renamed "side windows"
  • The "run_command()" function will be renamed "exec()"

Deprecations:

• AnsiEsc plugin is no longer required and will be removed
• Custom branch program is no longer required and will be removed
• Most of the now "public" API will be made private (still accessible, just no deprecation warnings)

Progress:

• [X] Restructure API
• [x] Implement parts in Lua
• [x] Branch drawing
• [X] Highlighting
• [x] Graph buffer commands
• [x] Exec format
• [x] Exec commands
• [x] Graph buffer settings
• [x] Side window buffer settings
• [x] Graph buffer syntax highlighting
• [x] Misc. fixes
• [x] PR for fugitive completion
• [x] Documentation
• [X] Neovim support added
• [x] Tests
  • [X] Framework
  • [x] Tests

Prerequisites for finalizing:

• [X] Vim9script finalized
• [X] Neovim vim9script support determined (not supported)

[rbong]

This is how the branch drawing currently looks. It's similar to git-forest, with straight lines prioritized over compactness, but it uses round edges and cleaner "jumps" over branches.

Let me know how this looks.

Here is a sample in text form so you can paste it into gvim/your terminal and tell me if you have any trouble with your fonts. I expect some issues, since many fonts will fall back on default fonts for these box drawing characters. I am using the Hack font with Alacritty.

╭
├─╮
│ ├
│ ├
├ │
├─◠─╮
│ │ ├
│ │ ├
├ │ │
├─◠─◠─╮
│ │ │ ├
│ │ │ ├
├ │ │ │
├─◠─◠─◠─╮
│ │ │ │ ├
│ │ │ │ ├
│ ├─◠─◠─╯
├ │ │ │
├─◠─◠─◠─╮
│ │ │ │ ├
│ │ │ │ ├
├ │ │ │ │
├─◠─◠─◠─◠─╮
│ │ │ │ │ ├

[ThomasFeher]

Looking good with font Iosevka in Alacritty.

[TamaMcGlinn]

Looks good with Ubuntu 20.04 default terminal and font.

[rbong]

I'm working on the way I draw merges with more than one target, or octopus merges.

The way git log --graph draws these is not very nice and I don't think we can get many good ideas here.

*   main
|\
| * d
| *
| |
|  \
*-. \   c Merge a and b
|\ \ \
| | |/
| |/|
| | * b
| | *
| * | a
| * |
| |/
* |
* |
|/
*
*

git-forest does a bit better job, but it leaves a fake hanging branch that doesn't go away until the commit is reached. Note that a splits into two branches, one of which is needed only for the merge. Imagine how much space would be wasted if we merged more than two branches, or if one branch was merged multiple times.

┌ main
├─┐
│ ├ d
│ ├
├ │ c Merge a and b
├─≡─┬─┐
│ │ │ ├ b
│ │ │ ├
│ ├─┘ │
│ ├   │ a
│ ├   │
├ │   │
├ │   │
├─┴───┘
├
└

We can partially solve this by drawing the merge over two lines and visually merging the fake split branch right away. It leaves an empty space, which still makes the graph unnecessarily wide, but at least that space can be filled later. I've come up with a good algorithm for filling empty spots but it still will push commits too far right too soon.

┌ main
├─┐
│ ├ d
│ ├
├ │ c Merge a and b
├─≡─┬─┐
│ ├─┘ │
│ │   ├ b
│ │   ├
│ ├   │ a
│ ├   │
├ │   │
├ │   │
├─┴───┘
├
└

Since we're using more box drawing characters, however, we don't need to leave a space.

╭ main
├─╮
│ ├ d
│ ├
├ │ c Merge a and b
├┬◠─╮
│╰┤ │
│ │ ├ b
│ │ ├
│ ├ │ a
│ ├ │
│ ├─╯
├ │
├ │
├─╯
├
╰

Here's a wider merge:

╭
│ ╭
│ │ ╭
│ │ │ ╭
├ │ │ │
├┬◠┬◠┬◠─╮
│╰┤╰┤╰┤ │
│ │ │ │ ╰
│ │ │ ╰
│ │ ╰
│ ╰
╰

Let me know what you think of this octopus merging style, if it's too compact or if you just don't like the way it looks.

Also... I am still thinking about providing an ASCII-only version, which makes this harder to draw legibly. Maybe something like this could work:

* main
|-.
| * d
| *
* | c Merge a and b
|-=-.
|\| |
| | * b
| | *
| * | a
| * |
| |-'
* |
* |
|-'
*
*

Here's a wider merge using ASCII characters, which is definitely harder to read:

*
| *
| | *
| | | *
* | | |
|-=-=-=-.
|\|\|\| |
| | | | *
| | | *
| | *
| *
*

[TamaMcGlinn]

Looks good and whatever character-drawing algo you choose in the end, I would push forward without worrying about the ASCII-only version; I don't really see the use case for that as people already have regular git log --graph.

It seems to me though that when you draw the a branch going into the merge, it is connected with a ◠ and then also with a regular connection, which seems superfluous to me. Isn't using 0x253c ┼ simpler?

╭ main
├─╮
│ ├ d
│ ├
├ │ c Merge a and b
├─┼─╮
│ │ │
│ │ ├ b
│ │ ├
│ ├ │ a
│ ├ │
│ ├─╯
├ │
├ │
├─╯
├
╰

The more common case, I would expect, is that both a and b's branches end after they are merged:

╭ main
├ d
│
│ 
├ c Merge a and b
├─┬─╮
│ │ │
│ │ ├ b
│ │ ├
│ ├ │ a
│ ├ │
│ ├─╯
├ │
├ │
├─╯
├
╰

[TamaMcGlinn]

When I was in GitExtensions, I would be looking at a commit, and it would have a list of hyperlinks for 'parents' and a list of hyperlinks for 'children'. The link itself was just the commit hash, but mouse-over would give the commit message. I realise flog's UI will be quite different but being able to meaningfully choose between the parents/children to navigate to next is what I'll be looking for in graph navigation.

[rbong]

┼ is not enough to represent every merge. In this example, d is a child of a, b, and c, but e is only a child of b.

╭ main
├─╮
│ ├ e
├ │ d Merge b and c
├┬◠─╮
│╰┤ │
│ │ ├ c
│ ├ │ b
│ ├─╯
├─╯
├ a

If we draw an ideal graph where a and c are also parents of e, we can see that if we used ┼ in the first case it would make the parents of e ambiguous.

╭ main
├─╮
│ ├ e Merge a and c
├ │ d Merge b and c
├─┼─╮
│ │ │
│ │ ├ c
│ ├ │ b
│ ├─╯
├─╯
├ a

This is not a problem specific to Flog, as I showed above both git-forest and git log --graph seek to distinguish between which branches are in the middle of the merge but continue on afterwards. Refer to the real examples at the start of my last comment.

[rbong]

Speed is becoming a bit of a concern. Parsing output is much faster in v2 than v1, but I can't hope to match the graph drawing speed of git log --graph (however it's currently always faster than git-forest, which I'm not using for comparison).

So currently at about 5000 commits with the Linux repo, v2 is marginally faster than v1 because of the parsing improvements. But at about 10,000 commits, it becomes slower because of graph drawing.

I still have to implement graph movement, which means recording more info about each commit, which means that it will get slower still. If I do implement visual graph movement, it will get much worse.

If I claim v2 is faster, I would preferably like people to have the option of displaying more than the current practical 1k-3k commit cap before it becomes slower.

Vim recommends complex plugins should be external programs that communicate with vim. Using, say, C or C++ to draw the graph would certainly make things faster, and make the nvim version easier to implement if they decide not to merge vim9script, but I know in the past people have been opposed to the idea of Flog being bundled with a new program, and this would be quite a change on top of already switching to vim9script. However, for both graph drawing and parsing speed improvements, both changes would be necessary.

The reason this would be faster than just going back to git log --graph is I could format each commit like this:

<hash>
<refs>
<visual parents>
<number of lines of output>
<output>

Whereas using any other branch viewer program, distinguishing between the graph and the commit data and then rebuilding the output takes a large amount of string processing.

Let me ask: how important is speed optimization for you? How many commits would you like to be able to see in a buffer? Are you opposed to Flog coming bundled with a program?

[TamaMcGlinn]

Neovim plugins are recommended to be built in lua because it is an order of magnitude faster. However, that would leave Vim users low and wet (being from the Netherlands, I am unable to consider 'high and dry' a bad thing).

I am not at all opposed to bundling a separate program with Flog - that's exactly how I bundled git-forest in flog-forest.

I feel that being able to navigate to parents/children at least an order of magnitude faster than flog-navigate's jk bindings would be a really significant improvement. (currently that plugin does a bunch of string processing and of course it is very slow, but I still use it)

[rbong]

Now that I think about it, Lua might be the ideal language to implement any external program in rather than, say, something like C++/Go/Rust like I was thinking.

• LuaJIT is fast
• Would be able to use any Lua functions directly in neovim if they don't merge vim9script
• Would be very fast in neovim (don't need to externally call the program and parse output)

Seems obvious now.

I have a very optimized graph drawing algorithm now though.

Current speed stats (Linux repo, max count 10,000):

Command	Time (s)
git log --graph > /dev/null	0.244
git log --graph (GPU accelerated)	0.306
git-forest > /dev/null	1.308
git-forest (GPU accelerated)	1.527
vim -c 'qa' (base time)	2.074
vim -c 'exec "Flog" | qa' (v1 minus base time)	2.016
vim -c 'exec "Flog" | qa' (v2 minus base time)	1.08

The fact that it's twice as fast and doing exponentially more work than v1 is great. Graph drawing is also inherently slower than git log --graph's algorithm since it prioritizes straight lines and fills empty space dynamically, not to mention we have to record more information about each commit and we are using a slower language, so I consider only being 5x slower a success, and I especially consider being faster than git-forest despite using a similar algorithm a success.

The problem is that recording any visual information makes it at least 2x as slow. Now that I have the graph drawing algorithm, though, I want to just focus on getting v2 done rather than messing around with new features and languages.

I'm thinking this might be the roadmap right now:

• Complete vim9script rewrite
• Initial release (new branch)
• Neovim support/Lua
• Visual graph navigation (should not take long)

[rbong]

Better ASCII octopus merges using L (still focusing on Unicode):

*
|-.-.
| * |
| | *
* | |
|-=-=-.
|L|L| |
| * | |
| | * |
| | | *
| |-'-'
* |
|-'
*

[rbong]

Another thing I wanted to ask about - does anyone have any issues with running git commit-graph write --reachable by default if it doesn't already exist? (It will be possible to turn this off and to turn off --reachable).

[TamaMcGlinn]

Did you know that git repositories can contain multiple root-commits, and may also contain completely separate trees? These both show up when you do a git subtree split & merge. Just something to keep in mind for your drawing algorithm.

[rbong]

There's a problem with syntax highlighting, and that's how commits either look odd when they're colored differently from the branch. If we make them the same color as the branch, they're harder to make out. This isn't a problem for git-forest because it doesn't try to highlight branches.

I would like to switch to 🞄 (U1F784, black slightly small circle) for commits.

This makes it impossible to distinguish connected commits in some cases:

 🞄 
─◠─
 🞄

So for jumps I would like to switch to ┊ (U250A, light quadruple dash vertical).

 🞄 
─┊─
 🞄

This also fixes other problems with the half circle character that was used previously.

Sample:

🞄
├─╮
│ 🞄
🞄 │
├─┊─┬─╮
│ │ │ 🞄
│ ├─┊─╯
│ │ 🞄
│ ├─╯
🞄 │
├─╯
🞄

Screenshot:

[rbong]

I realized ASCII has the same issue and now looks visually inconsistent so we can use : for jumps:

*
|-.
| *
* |
|-:---.
|L| | *
| |-:-'
| | *
| |-'
* |
|-'
*

[rbong]

Preview of branch highlighting. Just like before, it's only visually highlighting columns, since that's all vim can really do, but since we control branch drawing and straight lines have been prioritized (a branch will usually not move left/right), colors actually align to branches.

Honestly it's a bit weird seeing branches colored like this, but it is exponentially easier to track branches vertically with your eyes than git-forest, especially while scrolling.

[TamaMcGlinn]

Is there any reason the dots cannot also be colored the same as the branch? Or did you choose not to?

[rbong]

That's a choice - it makes commits more visually distinct and git log --graph does the same thing

[rbong]

Preview of commit highlighting:

Of course other date formats are still supported:

Or removing items:

The difference now is that, there won't be as many false positives. For instance, if hash, refs, or author are seen more than once, they're not highlighted:

The downside is that you can no longer put format items at the end of the line. That might change, I'm not sure yet.

There are still some false positives. Some common ones could be that if you put valid ref names at the start of a commit without refs, or if you put a valid date at the start of your commit:

However, if you put non-valid refs, or put items later on in the commit message, they won't show up:

In addition, for multiline formats, since we have more control over graph drawing, everything will only be highlighted on the first line:

[rbong]

Diff syntax now works:

You can now do diffs with -no-graph, which I believe was not possible before:

Also I have a new test system in place using shell scripts. I don't want to deal with vim9script/vim-flavor, and this will work even if some of the tests use Lua.

I consider this the "proof of concept" milestone, I now know what new features will and won't work, and I'm happy that the plan right now is solid, save if I discover some performance issue when re-implementing navigation.

[rbong]

For navigating parent and child commits, how about bindings that load parents into the quickfix/location list, and another one for children?

[rbong]

Argument parsing and log command building are done, and with that it's possible to use a very rudimentary :Flog command. I've pushed it up on the dev branch if you want to try things out. Don't expect anything to work, and expect me to rewrite git history on this branch.

Major changes to arg parsing and log command building:

• All boolean args now have both -<option> args and -no-<option> args. This lets you override your defaults for boolean options.
• Option names for bools no longer have no_ prefixes.
• g:flog_default_arguments renamed to g:flog_default_opts
• g:flog_permanent_default_arguments renamed to g:flog_permanent_default_opts
• Special characters should work better for various arguments

[rbong]

:Flog completion is done.

Changes:

• Can now use g:flog_get_authors_args to control author completion
• Format completion simplified
• Open command combinations available for completion
• Various minor completion bugs fixed

[rbong]

Finished implementing :Flogsetargs, -no-graph, and buffer name. Added automatic commit graph writing.

Other changes:

• max_count now 5000 by default

[rbong]

Added support for more date formats, supported list is now:

• human
• local
• relative
• short
• iso
• iso-strict
• rfc

[rbong]

You can now use % with -limit, ex.:

:Flog -limit=1,5:%

[rbong]

Another major milestone, finished porting the internal API for the :Flog command and the floggraph file type to vim9script. No changes to report.

[rbong]

Finished exec formatting (previously command formatting), fixed a bug with mutating the path option if it has special characters and improved support for special characters in converted items.

[rbong]

Finished :Floggit. Special characters should work better. Also, argument completion now relies more on Fugitive's own internal argument completion. If something that's useful is missing, I'll make a PR there.

[rbong]

Finished mappings.

Changes:

• Fixed typo in co<Space> mapping
• cot now col
• ' commit mark is now set only if the commit changed

With that, v2 is now fully featured.

I discovered an issue with branch drawing though. With git log --graph, if commits are filtered, parent branches that don't match will not show up.

Ex. git log --graph --grep=x86 --format="%h - %p" e8ffcd3ab0e5 -- in the Linux repo:

* e8ffcd3ab0e5 - 2afa90bd1c75 57690554abe1
* 57690554abe1 - 2f5b3514c33f
* 2f5b3514c33f - fbe618399854
* fbe618399854 - 58e138d62476
* 58e138d62476 - 2585cf9dfaad
* dcce50e6cc4d - cb8747b7d2a9

Note the last two lines - the parent of 58e138d62476 is 2585cf9dfaad, however the next commit that shows up is dcce50e6cc4d.

I don't like the way git log --graph shows this, ideally it should show that the branch has a hidden parent, something like this:

🞄 e8ffcd3ab0e5 - 2afa90bd1c75 57690554abe1
🞄 57690554abe1 - 2f5b3514c33f
🞄 2f5b3514c33f - fbe618399854
🞄 fbe618399854 - 58e138d62476
🞄 58e138d62476 - 2585cf9dfaad
┆

🞄 dcce50e6cc4d - cb8747b7d2a9

There are a couple problems with this:

• git log --graph doesn't just look at the lines in the range of --max-count, we have to look at all of the commits, which is extremely expensive the way things are now
• Even if we only go by --max-count, looking for missing parents is expensive
• The way I want to show the branch tapering off is also expensive right now

The problem with leaving it the way it is now is that the graph quickly starts filling up with branches, since the ultimate parent branches of filtered commits are never encountered.

This is going to require another round of graph drawing changes and optimizations. I haven't decided if it's time to port the graph drawing algorithm to lua yet, but it might be.