This page describes the revision graph logic from pull request: https://github.com/gitextensions/gitextensions/pull/5610

Terminology

Revision

A revision equals a git commit. In the graph a revision is a node in the graph. This is visually represented with a filled circle.

*  <- revision
|
*  <- revision

Segment

A segment represents the connection between 2 revisions.

*
|   <- segment connects two commits
*

A segment can span multiple rows when rendered as a graph. Example: This graph has 6 segements.

     *
   / | \
  |  *  |
  |  |  |
  |  *  |
   \ |  |
     *  |
     | /
     *

Row

Each commit/revision is rendered on a separate a row in the graph. The rows are created to help rendering the graph. A row has 1 revision and multiple segments that connect to this revision or crosses the row.

     *      <- Row (1 revision, 3 segments)
   / | \
  |  *  |   <- Row (1 revision, 4 segments)
  |  |  |
  |  *  |   <- Row (1 revision, 4 segments)
   \ |  |
     *  |   <- Row (1 revision, 4 segments)
     | / 
     *      <- Row (1 revision, 2 segments)

Lane

A lane represents a lane in the graph. There is no class to represent this in code. This is all done run-time. Why? Because it requires too much processing power and memory to create all lanes in memory. We only need the lanes for the visible part of the graph. We expect no more then about 30 rows to be visible. There is no need to preprocess all rows.

     *
   / | \
  |  *  |
  |  |  |
  |  *  |

  ^  ^  ^
  |  |  |
  3 lanes

The classes

RevisionGraph

This is main class of the revision graph. Each revision that is loaded is added to the graph using the Add method. The steps for adding a revision:

• Wrap the revision in the RevisionGraphRevision class.
• Give the RevisionGraphRevision a score (loading order)
• Load all parents, create an empty RevisionGraphRevision class for each parent
• Ensure that the RevisionGraphRevision has a reference to its parent/child revisions
• Create an unordered list containing all segments (connections between revisions)

All revisions get some basic preparation. Mainly raw data that is stored unordered.

RevisionGraphRevision

This class holds the revision itself and references to connected revisions. The most important method is the AddParent method. It is important that this method is light, since it is called when loading the revisions from git. This method:

• Adds a reference of the parent to an ordered list of parents
• Ensures each parent has a reference to it in its childs collection
• Ensures each parent's score is larger then its own score
• Copies its color-index to the first parent
• Generates a new color-index to all other parents
• Holds collections of all segments started by this revision

     *
   / | \   <- this revision starts 3 segments

• Holds collections of all segments ending in this revision

   \ | /   <- this revision ends 3 segments
     *

The main purpose of this class is to make sure all data that is required to create a graph later is there.

RevisionGraphSegment

This is a simple class that represents a segment. It only has to properties; Parent and Child. It connects two revisions.

RevisionGraphRow

Until now, all classes represent the data loaded from the revision log. This class is different. This class is used to draw the graph itself. There is no new data in this class, only existing data that is processed in order to draw the graph. Therefor, this class is not considered as primary data. Without this class, the revision grid is able to render all commit info without the graph.

The RevisionGraphRows are lazy-loaded when it becomes visible. This is done by the CacheTo method of the RevisionGraph. The steps to create a row:

• Copy all segments of the previous row
• Copy all startsegments from the current revisions
• Copy all endsegments from the current revision

This seems easy, but its not! The problem is, that all segments should be ordered in the row. And the order is per lane. To keep this as basic as possible, only the order is taken care of. It is possible that lanes overlap, this is not calculated yet. This is calculated when rendering. It only is calculated once, it is cached per row after a row is rendered.

Example of overlapping lane:

 *
 |
 | *
 |/
 |    <- Two segments overlap
 |
 *

Calculating these overlaps and the order of the segments is expensive. On the positive side, this can be calculated per row. Information about previous or next rows is not required. There is no need to do this for all rows.

Summary

The process of creating a graph

We now know the terminology used and the basic structure. Lets discuss how the graph is actually created. These are the steps:

• Collect basic data (revisions and segments), unordered.
• Order revisions.
• Create rows until last visible row.
• Render.

Pros

• The graph doesn't require any order for the revisions. It reorders the revisions in topo-order.
• We have the parents and children for all revisions, before the graph is loaded
• The graph is loaded fast, only the necessary data is preprocessed
• Memory usage is low, because we only store the necessary data

Cons

• Rendering is a bit slower, because not everything is prepared. Rendering is done per cell, because we use a grid as control. It would be a lot easier if we could render the entire grid at once. Since not all data is preprocessed, we need the previous row and next row for each cell. This is some overhead. It also limits in some area's. For example, to detect this we would need the previous/next 2 rows (no regression against 2.51, it was too expensive in that version):

* | |
|/ /
* |    <- It would be nice to straighten this row
|\ \
| | |

• Loading commits is a little slower, because we order (calculate scores) all revisions. This is required, because we are not sure the revisions are in topo-order.