Straighten revision graph in more cases #10778

o-kloster · 2023-02-27T15:17:19Z

Fixes #5782
Improves on #9050

Proposed changes

As of now, segments in the revision graph are straightened only of they contain no intermediate commits (i.e. it's just one segment). This change allows straightening also when there are intermediate commits and/or merges.

Screenshots

Before

After

Test methodology

Manual with GE repo
Unit tests verify the graph layout

Test environment(s)

Git Extensions 33.33.33
Build 8d82309
Git 2.36.0.windows.1 (recommended: 2.38.1 or later)
Microsoft Windows NT 10.0.19044.0
.NET 6.0.14
DPI 96dpi (no scaling)

Merge strategy

I agree that the maintainer squash merge this PR (if the commit message is clear).

✒️ I contribute this code under The Developer Certificate of Origin.

gerhardol · 2023-02-27T17:55:04Z

@o-kloster @mstv Merge this and #10637 ?

mstv · 2023-02-27T19:52:52Z

Merge this and #10637 ?

These two PRs are orthogonal and work well together.

These changes look promising. There are edge cases though - as most of the time...

The yellow area is unused space without benefit for the curves of the pink segments.
c20fe54803f3b6875f0b19302e85d5f2b415576c before / after:

o-kloster · 2023-03-01T15:38:37Z

I've found a few cases where the PR does not behave as desired. I'll be back with fixes.

o-kloster · 2023-03-03T09:52:17Z

Ok, I've fixed the issues that I found:

Straightening could lead to increasing the width of the graph.
Straightening could lead to other segments becoming curved or shifting across more lanes than before.

The latter can also happen in the current version of GE, although more rarely. An example is at e75b40425321694fbf6f91f6898cdec18c4b739c:

Today	With PR

mstv · 2023-03-03T21:47:33Z

Apart from cases like the following, many parts of the graph clearly look better.

4.0.2 / This PR above 885eb0c59f0f4ae11b8b510fec962b17df27ff0f

The violet segment should be kept straight. There are no nodes in it.

Straightening could lead to increasing the width of the graph.

This is not a strict rule IMO. I think a few additional lanes should be accepted.
In this example, the graph even has the same width.

RussKie · 2023-03-04T08:43:53Z

Ok, I've fixed the issues that I found:

Straightening could lead to increasing the width of the graph.

Straightening could lead to other segments becoming curved or shifting across more lanes than before.

The latter can also happen in the current version of GE, although more rarely. An example is at e75b40425321694fbf6f91f6898cdec18c4b739c:

Today With PR

Looking at this specific sample, I wonder if we could do this?

RussKie · 2023-03-04T08:46:46Z

4.0.2 / This PR above 885eb0c59f0f4ae11b8b510fec962b17df27ff0f

The violet segment should be kept straight. There are no nodes in it.

Straightening could lead to increasing the width of the graph.

This is not a strict rule IMO. I think a few additional lanes should be accepted. In this example, the graph even has the same width.

Is is possible to avoid the "bump" on the second lane? It'd allow avoiding all subsequent "bumps"...

mstv · 2023-03-04T11:26:36Z

Is is possible to avoid the "bump" on the second lane? It'd allow avoiding all subsequent "bumps"...

👍 Yes, this would be a valid graph. Though only, because the reason for the "bump" is the node in the left lane.
I.e. there is no risk that the crossing segments get in conflict with a node.
It is crucial that one can distinguish whether the segments just cross each other or whether there is a junction.

But would turn into . This might be confusing although still unambiguous.

The following (not occurring) graph would be definitely unclear:

Since crossings and junctions cannot clearly be distinguished, your first suggestion is problematic.
With the diagonals drawn by #10637, it might be doable - as long as there are no nodes or perpendicular segments in the way as in this:

Anyway, both proposals affect an even lower layer ("lane creation / selection") than this PR ("lane shifting") or #10637 ("segment drawing").
So they should be addressed in follow-up PRs.

mstv · 2023-03-04T12:02:23Z

Conflicting files: contributors.txt

Could you file your sign off in a separate PR, please, @o-kloster?

mstv · 2023-03-06T08:58:59Z

o-kloster · 2023-03-07T09:52:58Z

4.0.2 / This PR above 885eb0c59f0f4ae11b8b510fec962b17df27ff0f

The violet segment should be kept straight. There are no nodes in it.

Fixed in latest update. The rule against increasing the width has been relaxed somewhat.

Straightening could lead to increasing the width of the graph.

This is not a strict rule IMO. I think a few additional lanes should be accepted.

While I agree, I'm not sure how to formulate this precisely and fear the logic might become complex. It could quickly turn into an optimization problem of width against straightness.

As for the need to keep the width in check at all, you can see an example if you run the first version of this PR on 6d5defb20f78f52c21882c71fb68029ba1b642e5 and onward:

o-kloster · 2023-03-07T09:54:15Z

Conflicting files: contributors.txt

Could you file your sign off in a separate PR, please, @o-kloster?

Done in #10791

o-kloster · 2023-03-07T09:55:11Z

Which commit is this?

mstv · 2023-03-07T15:16:08Z

Which commit is this?

This example is from a private company repo.

mstv · 2023-03-07T19:39:11Z

There still is a too attracting condition:

3644218d8a7954db2b29e4b1af85b564a5edc28c

ca7e05c421c7c3b80eb97dd2a785be543ceb92bf

mstv

unfinished review

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

mstv · 2023-03-07T21:42:41Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraphRow.cs

+        /// If this row is the parent row of <paramref name="segment"/>, returns the segment leading
+        /// to this row's first parent (if any). Otherwise, returns <paramref name="segment"/>.
+        /// </summary>
+        public RevisionGraphSegment FirstParentOrSelf(RevisionGraphSegment segment)


I guess it should rather be SelfOrFirstParent in order to keep the segment straight as far as possible.
Only if it ends, take the first parent as continuation.

The first parent should only be chosen for the first child. If coming from another child, the segment should not be continued.

I guess it should rather be SelfOrFirstParent in order to keep the segment straight as far as possible. Only if it ends, take the first parent as continuation.

Are you arguing for just a name change, or for a functionality change? SelfOrFirstParent and FirstParentOrSelf are essentially the same, since the segment cannot both continue and have a parent in this row. But I opted for the latter since it returns self also in the case where the segment ends and has no parent segment.

The first parent should only be chosen for the first child.

I considered this. But how do you define the 'first' child segment? By order in the Segments list? By lane order in the row above (is this the same?)? By distance to the row of the child revision? In each case, I think I can find an example where this would lead to less straightening than desired.

SelfOrFirstParent and FirstParentOrSelf are essentially the same, since the segment cannot both continue and have a parent in this row. But I opted for the latter since it returns self also in the case where the segment ends and has no parent segment.

👍 Thank you for the explanation. I agree.
(From just reading if (segment.Parent != Revision), I do not get the meaning without looking into the docs of all these properties. Let's think about inversion and comments later when we have an agreed implementation.)

I was just dropping guesses how to avoid the yellow segment being bent one lane to the right unnecessarily early (resulting in the free lane under the mouse cursor).
The cyan branch is branched from and back to the yellow branch - at least as I read the graph.
The cyan branch should not "attract" the yellow branch (although it would save one bend for the cyan branch without adding one to the yellow branch).

I considered this. But how do you define the 'first' child segment? By order in the Segments list? By lane order in the row above?

👍
The yellow branch is the "first", the cyan one is the "second" and should not be continued with the ancestor.

(is this the same?)

I guess yes. Though this is not guaranteed. It depends on the sorting algorithm. I am experimenting with an (immature) alternative in my private build.
Using GetLaneIndexForSegment() will be safe and shouldn't be too expensive.

Sorry, the above seems to be not caused by this PR. The yellow and the cyan segments share the same lane since they have the same parent.
Since StraightenLanes operates on single segments, it cannot be detected / avoided not easily.
So I am dropping this part of the request.

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

o-kloster · 2023-03-08T17:17:48Z

This example is from a private company repo.

Could you show more of the graph? I don't see how to reproduce this. The two leftmost segments (yellow and blue) should have gotten the same lane, since neither connects to the revision of the first row, right?

- if any affected row becomes wider than the row immediately before the affected rows - if an already straight segment gets bent, or a segment shifting across lanes ends up shifting across more lanes than before

Before: Not more that the width of the row immediately above the changed rows Now: Not more than the max existing width nearby (up to lookahead distance above or below)

mstv · 2023-03-08T22:42:57Z

The two leftmost segments (yellow and blue) should have gotten the same lane, since neither connects to the revision of the first row, right?

In theory yes. But that's not the point. This is just caused by that I prefer a clearer graph where all branches fan out at their parent: 73e6a83

Could you show more of the graph? I don't see how to reproduce this.

I found it in the GE repo, too, at 083eef2e2c5030354bb33cefd14e233c58f72e41 "Merge pull request 5009":

Current | This PR

RussKie · 2023-03-11T10:45:38Z

💭 I wonder if we should consider allowing a branch to be on the left side as well if space allows it, e.g.:

RussKie · 2023-03-11T10:47:03Z

Current | This PR

I kind of like the left one better - it's "straighter", easier to follow.

RussKie · 2023-03-29T07:59:26Z

So where are we with this?

mstv · 2023-03-29T16:30:45Z

So where are we with this?

Let's take #10842 first (perhaps after v4.1). Then StraightenLanes() is called more consistently.

Open:

only switch to ancestor from 'first' child segment
Bulges like the following need to be straightened again yet:

mstv · 2023-04-01T23:00:12Z

#10842 has been merged. It calls StraightenLanes() more consistently. There shouldn't be many conflicts when rebasing.

ghost · 2023-04-22T19:00:48Z

This pull request has been automatically marked as stale because it has been marked as requiring author feedback but has not had any activity for 14 days. It will be closed if no further activity occurs.

ghost assigned o-kloster Feb 27, 2023

o-kloster changed the title ~~O kloster/straighten segments~~ O-kloster/straighten segments Feb 27, 2023

o-kloster changed the title ~~O-kloster/straighten segments~~ O kloster/straighten segments Feb 27, 2023

o-kloster changed the title ~~O kloster/straighten segments~~ Straighten revision graph in more cases Feb 27, 2023

gerhardol added the 🖊️ status: cla signed label Feb 27, 2023

o-kloster marked this pull request as draft March 1, 2023 15:36

o-kloster marked this pull request as ready for review March 3, 2023 09:52

mstv reviewed Mar 7, 2023

View reviewed changes

This comment was marked as outdated.

Sign in to view

This comment was marked as resolved.

Sign in to view

o-kloster added 4 commits March 8, 2023 18:33

Straighten multiple segments, including when there are merges

8dea3f8

Avoid straightening segments when this has undesired effects:

0be05e1

- if any affected row becomes wider than the row immediately before the affected rows - if an already straight segment gets bent, or a segment shifting across lanes ends up shifting across more lanes than before

Relax the limit on how wide a changed row may become

28008df

Before: Not more that the width of the row immediately above the changed rows Now: Not more than the max existing width nearby (up to lookahead distance above or below)

Stop loop when segments have been moved

3ea18db

Rename variable; inline a temporary

ba94923

o-kloster force-pushed the o-kloster/straightenSegments branch from 37ba8d8 to ba94923 Compare March 8, 2023 17:36

mstv mentioned this pull request Mar 11, 2023

Render graph lines with less curves #10637

Merged

mstv mentioned this pull request Mar 29, 2023

Refactor and fixup graph loading #10842

Merged

RussKie added the 📭 needs: author feedback More info/confirmation awaited from OP; issues typically get closed after 30 days of inactivity label Mar 29, 2023

mstv mentioned this pull request Apr 7, 2023

Do not straighten re-used graph lanes #10864

Merged

ghost added the 💤 status: no recent activity The issue is stale label Apr 22, 2023

ghost closed this Apr 29, 2023

ghost added the status: abandoned label Apr 29, 2023

mstv mentioned this pull request Jun 10, 2023

Preview of graph with diagonals #11036

Closed

mstv mentioned this pull request Jun 18, 2023

Straighten multiple segments, including when there are commits #11059

Merged

This pull request was closed.

Uh oh!

Straighten revision graph in more cases #10778

Straighten revision graph in more cases #10778

Uh oh!

Conversation

o-kloster commented Feb 27, 2023

Proposed changes

Screenshots

Before

After

Test methodology

Test environment(s)

Merge strategy

Uh oh!

gerhardol commented Feb 27, 2023

Uh oh!

mstv commented Feb 27, 2023

Uh oh!

o-kloster commented Mar 1, 2023

Uh oh!

o-kloster commented Mar 3, 2023

Uh oh!

mstv commented Mar 3, 2023

Uh oh!

RussKie commented Mar 4, 2023

Uh oh!

RussKie commented Mar 4, 2023

Uh oh!

mstv commented Mar 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mstv commented Mar 4, 2023

Uh oh!

mstv commented Mar 6, 2023

Uh oh!

o-kloster commented Mar 7, 2023

Uh oh!

o-kloster commented Mar 7, 2023

Uh oh!

o-kloster commented Mar 7, 2023

Uh oh!

mstv commented Mar 7, 2023

Uh oh!

mstv commented Mar 7, 2023

Uh oh!

mstv left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

mstv Mar 7, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mstv Mar 8, 2023

Choose a reason for hiding this comment

Uh oh!

o-kloster Mar 8, 2023

Choose a reason for hiding this comment

Uh oh!

mstv Mar 8, 2023

Choose a reason for hiding this comment

Uh oh!

mstv Apr 1, 2023

Choose a reason for hiding this comment

Uh oh!

Uh oh!

This comment was marked as outdated.

o-kloster commented Mar 8, 2023

Uh oh!

This comment was marked as resolved.

mstv commented Mar 8, 2023

Uh oh!

RussKie commented Mar 11, 2023

Uh oh!

RussKie commented Mar 11, 2023

Uh oh!

RussKie commented Mar 29, 2023

Uh oh!

mstv commented Mar 4, 2023 •

edited

Loading

mstv Mar 7, 2023 •

edited

Loading