Graph draw wrong line

[letieu]

on the line 78, i found the wrong line connect.

M         │                 9eded02 12:44 25-07-24 hieu.nguyen
├─╮       │                         Merge branch 'huytn-cicd-mes-domain' into 'develop'
│ *       │                 5f29384 19:40 25-07-24 Huy Nguyen (origin/huytn-cicd-mes-domain)
│ │       │                         huytn/cicd/add-manual-deployment-stage
│ │ M     │                 b753132 11:32 25-07-24 hieu.nguyen (origin/production)
│ │ ├─╮   │                         Merge branch 'uat' into 'production'
│ │ │ M   │                 c397bd3 11:17 25-07-24 hieu.nguyen (origin/uat)
│ │ │ ├─╮ │                         Merge branch 'resolve-merge-conlict-uat' into 'uat'
│ │ │ │ M │                 b2008d6 18:14 25-07-24 Thanh Quach
├─┴─│─│─┼─│─╮                       Merge branch 'uat' into resolve-merge-conlict-uat
*   │ │ │ │ │               c8f4695 08:22 25-07-24 hieu.nguyen

c8f4695 have 2 child: 5f29384, 9eded02, but in the image, we se connect line to b2008d6

[letieu]

BTW, this is very complex stuff, I try to read the blog and figure out how to write a cli version to drawl git log, but i'm stuck now :))

[isakbm]

Great find, can you try to add it to our test cases?

I'm sure we will be able to render those connections better eventually.

It happens due to a bi-crossing I think, where there is a Merge commit immediately after that also wants a connection to something that overlaps with and conflicts with the connect.

In your case the pair of commits that complicate things are the regular commit c8f4 and the merge commit b200.

I am already doing some tricks to resolve "bi-connectors", the techniques are just not viable in all cases. I have some other ideas for ways to fail over to resolve those types of connectors better.

But first we need to add it to our test cases.

[letieu]

I think you need to apply more standard way to write unit test :D

[isakbm]

Oh sure things are not being perfect at all. But do you understand the format

Child Parent1 Parent2 etc ? :)

[letieu]

How can I run the test :))

[isakbm]

I can just add the test later :)

[letieu]

I have non relate question. I see that vim-flog can drawl pretty nice graph, can you explain me about what different bettween

[isakbm]

It is quite tricky to explain the difference honestly, there are so many 😅

The main one though is branches not taking up too much vertical space, I can show you what happens in a few of my repos with flog

And then just performance wise, the scrolling is very laggy.

I also just don't like the look of the graph, as it tries to use just single line per commit, etc etc.

There are other edge cases too where it simply fails to draw the commit. 🤷

[isakbm]

Basically the issue seems to be that flog deals very poorly with multiple subsequent merges.

There are lots of other issues too, but look at comparatively how nice it is to be able to view multiple merges without all the unnecessary horizontal space using "our" gitgraph plugin :)

[rbong]

flog deals very poorly with multiple subsequent merges

I would like to share that it's not simply bad at dealing with multiple subsequent merges. Flog's intentionally avoids reordering branches in most cases. This is a consequence of the fact of a couple design decisions.

Flog does not sort branches itself, unlike gitgraph.nvim. It allows git log to do it. This allows us to avoid sorting branches in Lua and letting Git do it in C and rely on git commit-graph write to cache graph data, but means that if we aggressively reorder branches to preserve horizontal space without being able to determine commit order ourselves and while parsing commits mostly linearly without determining branch position, I found it can mean excessive crossovers, which look just as ugly.

The other factor is that we use branch order to determine their color, so reordering branches aggressively would break that. As noted, highlighting in Flog can be slow because it uses a syntax file for highlighting. This is not only seems to cause lag as reported by @isakbm, but can be inaccurate. However, when I tested similar highlighting to what gitgraph.nvim uses now years ago, that caused lag for me. I will be revisiting the highlight system now that gitgraph.nvim has proved it's possible without lag.

So I would say as the author of Flog the biggest differences right now are that:

• Flog does not sort branches itself, meaning that gitgraph.nvim is able to get a nicer layout.
• gitgraph.nvim has much more accurate highlighting.

There are other edge cases too where it simply fails to draw the commit.

Please report this issue if you can. Are you saying this because of the tokens Flog injects into git log output? Sorry I know you're busy trying to improve your plugin, but I'm sure you can understand as a maintainer that random unreported bugs are worrying :sweat_smile:

Edit: Also, Flog integrates with Fugitive.

[isakbm]

@rbong

For the record, the sorting that gitgraph does is unnecessary and I could most likely remove it as git log does it correctly by itself already if provided with the correct command line arguments.

As for the bug, I will show you an ascii representation of it below. I have no idea what causes the bug though and have not had the time to try to reproduce it minimally, I just know that I cannot really trust what flog outputs.

git log reference ...

      │ │ * 0aa3d0d4 (3 months ago)
      │ │/
      │/│
      │ │
      * │   db9993c8
      │\ \
      │ │/
      │/│
      │ │
:NOTE │ * 7422ae7f (3 weeks ago)
      │/
      │
      │
      *   47229305 (3 weeks ago)
      │\
      │ │
      │ │

fugitive ...

      │ │ • 3 months ago [0aa3d0d4]
      ├─┊─╯
      • │ 3 weeks ago [db9993c8]
      ├─┤
:NOTE │ 3 weeks ago [7422ae7f]
      ├─╯
      • 3 weeks ago [47229305]
      ├─╮

Note the missing commit at :NOTE

[isakbm]

@letieu

Could you help me get kick started on the graph edge case that you encountered?

It would be great if you could share a repo with me that has the issue you have uncovered!

[isakbm]

@letieu

I have made a test case that I think captures the issue, am working on making the test setup a bit more intuitive, and will display some commit letters on the graph itself to make it more clear, at the moment you can see the names of the commits follow by pseudo commit age, and a commit -> parents relation.

 ------ letieu ------ 
H CG
G C
F BE
E BD
D BA
C B
B A
A
 ------  result  ------ 
01   H               M               H 1  H -> CG
02   c g             ├─╮
03   C G             │ *             G 2  G -> C
04   C c             │ │
05   C C F           │ │ M           F 3  F -> BE
06   C C b e         │ │ ├─╮
07   C C B E         │ │ │ M         E 4  E -> BD
08   C C B b d       │ │ │ ├─╮
09   C C B B D       │ │ │ │ M       D 5  D -> BA
10   C C B B b a     ├─┴─│─│─┼─╮
11   C   B B B A     *   │ │ │ │     C 6  C -> B
12   b   B B B A     ├───┴─┴─╯ │
13   B         A     *         │     B 7  B -> A
14   a         A     ├─────────╯
15   A               *               A 8  A ->

You can see that here the children of C are H and G, however the graph also makes it look like D could be a child, which is incorrect.

FYI, the way to read these scenarios is

<commit> <parent-0><parent-1>...<parent-n>
...

[isakbm]

Here's a much clearer rendition of your test scenario @letieu :)

I am rather confident that I'll resolve this bug, I think it's purely a simple blunder on my part relating to the horizontal connectors.

  H               H 1  _ -> H -> CG
  ├─╮
  │ G             G 2  H -> G -> C
  │ │
  │ │ F           F 3  _ -> F -> BE
  │ │ ├─╮
  │ │ │ E         E 4  F -> E -> BD
  │ │ │ ├─╮
  │ │ │ │ D       D 5  E -> D -> BA
  ├─┴─│─│─┼─╮
  C   │ │ │ │     C 6  HG -> C -> B
  ├───┴─┴─╯ │
  B         │     B 7  FEDC -> B -> A
  ├─────────╯
  A               A 8  DB -> A ->

[isakbm]

@letieu 🤞 I really hope this also fixes it for the case you found in your repo. Here's what the troubling case looks like after the attempted fix. It was much simpler than I thought 😅

 ------ letieu ------ 
H CG
G C
F BE
E BD
D BA
C B
B A
A
 ------  result  ------ 
01   H               H               H 1  _ -> H -> CG
02   c g             ├─╮
03   C G             │ G             G 2  H -> G -> C
04   C c             │ │
05   C C F           │ │ F           F 3  _ -> F -> BE
06   C C b e         │ │ ├─╮
07   C C B E         │ │ │ E         E 4  F -> E -> BD
08   C C B b d       │ │ │ ├─╮
09   C C B B D       │ │ │ │ D       D 5  E -> D -> BA
10   C C B B b a     ├─╯ │ │ ├─╮
11   C   B B B A     C   │ │ │ │     C 6  HG -> C -> B
12   b   B B B A     ├───┴─┴─╯ │
13   B         A     B         │     B 7  FEDC -> B -> A
14   a         A     ├─────────╯
15   A               A               A 8  DB -> A ->

14 of 14 tests passed

[rbong]

For the record, the sorting that gitgraph does is unnecessary and I could most likely remove it as git log does it correctly by itself already if provided with the correct command line arguments.

In that case the differences in our graphs may come down entirely to highlighting approach, since I try to keep branches straight. Whatever it is, I believe your horizontal branch placement is better right now.

As for the bug, I will show you an ascii representation of it below. I have no idea what causes the bug though and have not had the time to try to reproduce it minimally, I just know that I cannot really trust what flog outputs.

Thanks for reporting what you can. I cannot reproduce this, but I just refactored how branches are drawn to increase performance and make the algorithm simpler, so it may be fixed.

Sorry for losing your trust. FWIW, other than this new issue, Flog has only required two fixes for graph branch drawing accuracy, both very shortly after it was added and both fairly small. I hope it's fair to say that there is not an insurmountable accuracy issue.

I have added an issue for the bug for Flog here to hopefully not crowd your issue tracker any more: https://github.com/rbong/vim-flog/issues/133

[letieu]

Very nice, thanks you very much. Very complex, I know :))

[isakbm]

@letieu , lovely to see that it fixes it now for your repo as well. Gives me more confidence in the maintainability of this repo, and the graph drawing algo.

1. was relatively easy to reproduce your edge case without access to your git repo
2. was easy to figure out and resolve what the issue was once I had this test case

I'll refer to the test case as letieu for now if you don't mind 😅

[isakbm]

@rbong

Sorry for losing your trust. FWIW, other than this new issue, Flog has only required two fixes for graph branch drawing accuracy, both very shortly after it was added and both fairly small. I hope it's fair to say that there is not an insurmountable accuracy issue.

Don't worry, there is not a single open source asccii (grid based) git graph renderer out there that is good enough for me. Otherwise I would never have bothered to take on this daunting task of writing one myself. It is hard work, and the devil is in the details. There is a reason why I do not work on any other side projects at the moment. Correctly drawing git graphs in terminal is no joke, that is why the original git log --graph looks so messed up to begin with. It has nothing to do with the connector symbols, it has everything to do with providing space for, or finding space, for connectors between commits.

FYI: correct commit placement is the easy part of this problem. Finding space for connectors, is the hard part.