Commit graph layout

In short: createCommitNodes takes a Commit[] in which each commit lists its children. It reorders each commit's children so branches that merge back sooner sit further left, gives every commit a row (y, counting up from the oldest commit), and then places each commit in the leftmost column (x) where its own line and the lines to its children don't collide with lines already placed. Finally it walks every edge with a TileDrawer that drops line fragments into a grid of three tiles per row. The webview renders that grid as tiny inline SVGs. Everything runs in the webview, in one synchronous call, every time the state changes.

All the layout code lives in src/ui/commit_graph/algorithms/: preprocess.ts (1,304 lines) does the work, drawer.ts and range_manager.ts are its helpers, and focus_mode.ts filters the input first. The pass is pure TypeScript with no DOM access, which is why preprocess_test.ts can check coordinates and line types directly.

1. Input

The layout consumes the commits array of one CommitGraphState. Each element is a Commit. Only a few of its fields matter to the layout:

The descriptions, chips, display IDs and timestamps are all ignored here. They belong to the row's right-hand side, covered on the webview UI page.

The array arrives through the webview's $setState call, and JjApp.setState is the only caller of the layout. For each repository's state it optionally applies focus mode, calls createCommitNodes, sorts the nodes by y descending (newest at the top), and reports the resulting order back to the extension host with $informNewOrder: each node's final children order, the top-to-bottom hash list, and the working-copy row index.

At this pin, nothing produces real commit data yet. The only implementation of the extension side, createFakeWebviewState, is marked // TODO - Replace with a real implementation. and sends a single hard-coded commit. There is no jj log call anywhere in the extension. The layout is complete and heavily tested, but in a running extension it currently draws one dot. The roadmap page covers where real data is meant to come from.

The output is the same objects grown into CommitNodes (a CommitNode extends Commit). Each node gains:

2. The preprocessing pipeline

createCommitNodes(commits) is the entry point and the only export of preprocess.ts. It runs these passes in this order. Below, n is the number of commits and e the number of parent–child edges.

Building nodes

Every commit is copied into a fresh CommitNode with zeroed layout fields. A second loop turns childrenHashes into object links in both directions, pushing each child as {node, lineX: 0}. A missing child throws Commit a has child c which is not present in the commits array. (source). An empty input returns an empty map straight away. O(n + e).

Disjoint sets and the magic root

setDisjointSetIdsForAllNodes walks the input in order and floods each unvisited commit's component (through parents and children) with the next id, so component 0 is whichever contains the first commit in the array. O(n + e).

The per-component loop then runs from the last id down to 0, sharing one row counter. Since rows count upwards, the last component ends up at the bottom of the graph and component 0 (the first commit's) at the top. Within a component, the roots are the nodes with no parents. If there is exactly one, it is the root. If there are several, the pass makes a synthetic parent from ROOT_NODE_BASE (hash ROOT_NODE_UNIQUE_HASH, isMagicRoot: true) whose children are all the roots, so every later pass can treat the component as having one entry point (source). The magic root is never added to the map and never gets a row (setYRecursively skips it), but it does take part in column placement: its own one-unit vertical reservation sits at y = -1..0, below every real row.

Descendant sets

setDescendantsFieldRecursively fills each node's descendants with its own hash plus the union of its children's sets, memoised on "the set is non-empty". Only fixRedundantLines uses it. Because every set can hold up to n hashes, this is O(n · (n + e)) time and O(n²) memory in the worst case.

Optimizing the children order

optimizeChildrenOrder is the aesthetic heart of the layout. Its goal: among a node's children, put the ones whose subtrees merge back sooner to the left, so their lines stay short and don't cross the longer-lived branches. It repeats three steps:

1. setTraverseOrderRecursively numbers nodes in DFS preorder following the current children order. A node reachable from several parents keeps the number from its first visit (the leftmost path).
2. setSmallestTraverseorderRecursively gives each node the minimum preorder number in its subtree. A small value means "somewhere above me, this branch rejoins something that was reached early", that is, something to the left.
3. maybeSwapChildren walks the tree, stably sorting each node's children by smallestTraverseOrder (ties keep their current order). On the first node whose order changes, it stores the new order and returns true straight away.

A swap invalidates every traverse number, so the loop zeroes them all and starts again. It stops when a full pass swaps nothing. The source comment's example: under a, with children [b, d, e], if e merges back into c (a child of b) but d never merges back, then e's subtree contains the early-numbered c, so e sorts before d and the order becomes [b, e, d]. If d also merged into c, the two would tie and the caller's order would stand.

The loop is capped at n² iterations, after which it throws The total number of swaps reached the maximum n^2 bound. Each iteration is a full traversal, so the worst case is O(n² · (n + e)), though the source notes that in practice "the number of swaps should be much much less than that". (The preorder counter starts at 0, which is also the "unvisited" sentinel, so the root is numbered 0 and is effectively re-entered as unvisited. That's harmless, because nothing points back at a root.)

Fixing redundant lines

jj can show an edge that is implied by another path, such as A → C when A → B → C also exists. fixRedundantLines enforces one ordering rule on top of the optimizer: if a child is a descendant of a sibling listed before it, the descendant moves in front of that sibling, and the rest keep their relative order. The reason is in the doc comment above it: rows are assigned to children right to left, so the child listed first gets its row last, and a commit that sits above its sibling must get its row after that sibling. Otherwise "there's no space for B. B can now only be placed on top of C, which is wrong because it's a descendant of it." Each move retries the same index (--i). It runs over every node in the map, not just the current component's, which is redundant but harmless on later iterations. It costs O(Σ deg²) per sweep, with set lookups in O(1).

Rows: setYRecursively

setYRecursively is a topological sort written as a DFS. A node gets the next row number only once every one of its (non-magic) parents has one. If any parent is still unvisited, the call simply returns, and the node is reached again later through that last parent. It visits children right to left, so the rightmost child's branch is numbered first and sits lowest, and the leftmost child's sits highest, nearest its merge-back point. Row 0 is the root, so the graph grows upward. A row is a whole line of the rendered graph, so no two commits ever share a row, and every child is above all its parents. O(n + e).

Columns: setXRecursively

setXRecursively(node, rangeManagers) places a node and, recursively, the part of the graph that branches out of it. It is a search: try x = 0, and if anything doesn't fit, throw the attempt away and try one column further right. Each attempt works on clones of the two range managers (one for vertical segments, keyed by column, and one for horizontal segments, keyed by row), and only a successful attempt copies its clones back with replace. One attempt at column x:

1. Reserve the node's own stub: the vertical range y - 1 .. y in column x, the unit of line just below the glyph. It is shareable only with a range that leads to the same child (CRITERIA.toSameChild). If the column is taken, try the next x.
2. For each child, in children order:
   • If child.traverseOrder > node.traverseOrder, the child was first reached through this node in the ordering DFS. The code calls this a merge-out. It places the child first, recursively, using the same cloned managers. Otherwise the child was already placed through another parent (a merge-back), and only the edge needs a route.
   • Pick the edge's column (lineX): starting at the parent's own x, find the first column where the vertical range node.y .. child.y - 1 can be reserved. Ranges from the same parent may share a column (CRITERIA.fromSameParent), which is why fan-out from one commit can run up a single line.
   • Reserve the edge's horizontal run, if it has one. If the edge runs up the parent's own column and turns sideways only just below the child, the run lies on row child.y - 1. If the edge first steps right from the parent to a column further over, it lies on row node.y. Horizontal runs may only overlap runs into the same child. If this one collides, the whole attempt is abandoned and the parent moves right.
3. Respect the leftmost child: if the smallest lineX among the children is further right than x, the attempt is rejected too. In the source's words, "It's visually better for parent nodes to be placed at least as right as the left-most child node."
4. Otherwise commit: set node.x = x and replace the real managers' contents with the clones.

Because column placement recurses before the parent is finished, a branch's commits are placed before the commit they fork from. And because every retry re-runs the recursive placement of the whole merge-out subtree on fresh clones, a retry high up in a deep graph redoes everything above it. There is no polynomial bound in the code. Each recursion level just gives up with Unreachable: node.x should never be this large. at column 10,000, and every attempt also pays for cloning both managers, which is linear in the number of reserved ranges. For the graphs a VS Code side panel shows, this is fast in practice. The test No overlapping horizontal lines to the same child is the case the horizontal check exists for: without it, two runs into different children would be drawn on top of each other.

The magic root, when there is one, goes through all of this too. Its edges to the real roots reserve vertical and horizontal space, but it is not in sortedNodes, so those edges are never drawn. In effect it keeps the separate roots of one component from sharing a column.

The working-copy flag

setIsWorkingCopyCommitAncestorRecursively marks the active commit and, by memoised post-order over children, every commit with the working copy above it. It is the last per-component pass. O(n + e). The flag only affects colour: a line takes the foreground colour when the commit it leads into carries it.

Tiles: setTileGroupsForAllNodes

With every node at an (x, y) and every edge at a lineX, the remaining passes run once over all nodes, sorted by y ascending (so sortedNodes[y] is the row-y node). setTileGroupsForAllNodes calls setTileGroupsForLine for every edge, then pads each row with empty tile groups so it has at least x + 1 of them (the glyph's own column must exist). How an edge becomes tiles is the drawing section. The cost is O(Σ edge length in tiles), at most O(e · (rows + columns)).

Insert actions

Every tile can be a drop target: dragging a commit onto a line means "insert it here". setInsertActionForAllNodes precomputes, for each tile, the InsertAction to offer: from and to (either may be undefined), where to draw the ghost node (insertNode, in grid units where .5 means between two rows), and where to put the hint text (insertHint).

• The glyph's own column. The top tile means "between me and my children": no action if the node has no children (unless lines pass through), insert here for one child, and insert as common parent (to: undefined) for several. The bottom tile is the mirror image: insert here for one parent, insert as common child (from: undefined) for several.
• Every other tile goes through calculateInsertAction on the lines it holds. One line gives insert here. If all the lines share a parent, the result is insert as common parent when they cover all of that parent's children, and otherwise insert here on the first. If they share a child, the result is insert as common child when they cover all its parents, and otherwise the line with the leftmost lineX. In any other mix, the function retries with only the horizontal lines, and gives up (undefined) if there are none.
• Because horizontal runs and right-to-up curves are drawn on the boundary of the tile below (see drawing), a row's bottom tile also considers the HORIZONTAL and RIGHT_TO_UP lines from the top tile of the row below it. Hovering over where a line appears then picks it up.

getInsertNode picks the ghost node's position from the edge's shape, case by case. On a straight edge between adjacent rows it goes halfway between them, and otherwise one row below the child, "because there could be more branches forked after the midway point". On a common merge-out it goes at the midpoint of the horizontal run. On the rarer shapes it goes on the vertical segment. The hint text goes in the rightmost of the parent's, child's and line's columns, so it never covers the line (insertHere). The pass costs O(lines in all tiles) plus the parent/child set checks.

Occupied columns

setOccupiedColumnsForAllNodes trims trailing columns from each row's tile count until one holds a "space-occupying" line, meaning anything except HORIZONTAL and RIGHT_TO_UP (isSpaceOccupyingLine). Those two are drawn on the border with the row above, so they don't need room in this row. It then clamps the result to at least x + 1. The row's text starts right after occupiedColumns, which is why text can tuck in under a horizontal run. O(tiles).

Two-line mode

In RenderMode.TWO_LINE a commit takes two text lines, so the graph must stretch each row without breaking any edge. setMultiLineTiles builds three tile-group arrays per row: firstLine (the real top and glyph tiles plus an extended bottom), intermediateLine and lastLine. The tricky part, explained at length in the source, is that the curves joining a row to the row below are stored in the lower row's top tile, to avoid sub-pixel gaps between tiles. So calculateMultiLineBottomTiles reads both tiles. If the row's bottom tile already has vertical lines, it repeats them all the way down. If both are empty, it draws nothing. Otherwise it takes the lower row's top-tile lines, drops the horizontals, and turns every curve into a straight vertical for the stretched part, leaving the last line's bottom empty so the original curves still join up below. O(tiles). The row component only ever renders two lines (source), so intermediateLine is not drawn on its own at this pin. Its tiles reach the screen as the top and glyph tiles of lastLine.

3. Lanes and edges

jj-dojo has no persistent "lanes" in the sense of a branch keeping its column all the way up. A column is just whatever setXRecursively found free, so it belongs to a commit's stub and to whichever edges were reserved through it. Two facts follow from the passes above:

• A commit's column is never left of its leftmost child's edge. Edges leave a parent at its own column or further right, because lineX starts at x and only grows. With the leftmost-child rule, this keeps a branch's base under or to the right of where it forks.
• Every edge has exactly one vertical column, its lineX, plus at most two horizontal runs, one at the parent's row and one just below the child's row.

Those constraints leave six possible edge shapes, and setTileGroupsForLine has one branch for each, told apart by comparing parent.x, lineX and child.x. The source comments call an edge going right a merge-out and an edge coming back left a merge-back:

Here k = child.y − parent.y − 1, the number of rows strictly between the two. Merges need no special representation: a merge commit is simply a node with several parents, so it is the child end of several edges, and each is routed independently. Edges into the same child may share horizontal space (toSameChild), which is how several merge-back lines can meet in one run under a merge commit.

No elided ranges. The layout has no notion of hidden or elided commits, unlike jj log's ~ marker. Every commit in the input is drawn, and every childrenHashes entry must name a commit that is also in the input. The closest thing is focus mode, which removes commits before layout and simply drops edges to them, leaving no marker in the graph. There is only a count in the "Disable focus mode" link below it.

4. Drawing

The tile grid

Every row is a strip of columns, and every column is a TileGroup of three stacked tiles: a 5px top tile, a 14px glyph tile and a 5px bottom tile, all 14px wide. That makes a 24px row (constants.ts). A tile is just a list of Lines (a LineType plus the parent and child it connects) and an optional insert action. Nothing in the grid knows about whole edges. An edge is scattered across every tile it passes through.

TileDrawer

TileDrawer is a turtle over that grid. It starts on the parent's glyph tile and keeps a cursor (x, y, tile), where tile is BOTTOM = 0, GLYPH = 1 or TOP = 2 (source). moveUp advances tile and, on wrapping past TOP, moves to the next row's bottom tile. Every drawing method moves first and then draws one Line into the tile under the cursor:

• up(n): n × (move up, draw VERTICAL).
• right(n) / left(n): n × (move one column, draw HORIZONTAL).
• upToRight / upToLeft: move up, draw the curve that turns from vertical to horizontal.
• rightToUp / leftToUp: move one column, draw the curve that turns from horizontal to vertical.

Writing uses getOrInsert, which grows the target row's tileGroups with empty groups as needed. That is why rows have different widths, and why the later padding pass only has to guarantee the glyph's own column.

Where a line actually appears

lines.ts turns each Line into an SVG group (<g>) of paths, drawn in a coordinate space the size of its tile (source). Each tile puts all of its groups into one SVG with overflow: visible. The shapes are not centred in the tile the way the names suggest:

• VERTICAL runs down the tile's centre, and HORIZONTAL along its top edge (source).
• UP_TO_RIGHT and UP_TO_LEFT are quadratic Béziers between the centre of one edge and a top corner (source).
• RIGHT_TO_UP and LEFT_TO_UP are drawn inside a translate(0, −tileHeight), so they paint into the tile above the one that stores them (source).
• Every path is stretched by VSCODE_OFFSET (0.5px) at its ends, to hide a sub-pixel gap between tiles that only shows up inside VS Code (source).

So a horizontal run "at row y" is stored in row y's top tiles but painted on the border with row y + 1, and the curve that finishes it is painted in row y + 1's bottom tile. That is the reason for the extra lines in insert actions, the occupied-columns exception and the two-line special case above. All three put back what the storage location hides.

The rendering components

• jj-commit-row-left-side renders one jj-tile-group per column. Its width is 14 × occupiedColumns + 4 px (source). jj-commit-row picks tileGroups or one of the multiLineTileGroups arrays according to the CommitRowType.
• jj-tile-group stacks a top jj-merge-tile, a jj-glyph-tile and a bottom jj-merge-tile, and decides shouldDrawGlyph: true only in the node's own column, and never on the second line in two-line mode.
• jj-merge-tile is a 14×5 host that renders its tile's lines in one SVG and publishes the tile's insert action as a drag-and-drop target.
• jj-glyph-tile is 14×14. It renders the lines, then the glyph, both inside a single SVG, chosen in this order: @ for the working copy, a diamond for immutable, a cross for conflicted, and otherwise a filled circle of radius 5. The colour is the button colour while dragged or a drop destination, the error colour if conflicted, the foreground colour for working-copy ancestors, and grey otherwise (source). On the node's own column the tile is the drag source for the commit itself. In every other column it publishes its insert action instead. It also draws the rebase hint and the insert ghost node and hint text into the same SVG when they apply.
• getLineColor gives each line a colour, a width and a priority: lines matching the hovered insert action during a drag get priority 2 (2.5px, button colour), lines into working-copy ancestors priority 1, and everything else priority 0 in --inactiveLineColor. Since the lines of a tile now share one SVG, priority can no longer be a per-line z-index. Each tile sorts its lines by priority so the important ones paint last, and sets its SVG's z-index to the highest priority it holds, so a highlighted line in one tile still covers a grey line spilling over from its neighbour (source). A glyph tile showing a hint jumps to z-index 10 so the bubble sits above everything (source).

5. Ranges

range_manager.ts is the collision detector behind column placement. A Range is an interval start .. end along one row or column, plus the parentHash and childHash of the edge it belongs to and a canBeSharedBy(existing, new) predicate. All fields are readonly.

A RangeManager holds rangeGroups: Range[][], one plain list per coordinate. For the vertical manager the index is the column and the intervals are row spans. For the horizontal manager the index is the row and the intervals are column spans. It has three operations:

• reserve(coordinate, range): grow the outer array if needed, and scan the group linearly. If no existing range overlaps the new one, append it and return true. Otherwise return false and change nothing.
• clone(): copy every group array. The ranges themselves are shared, which is safe because they are immutable.
• replace(groups): adopt a clone's arrays. This is how a successful attempt in setXRecursively commits.

Ranges are never merged, split or removed. A group only ever grows by appending, and the only query is "does this collide?". The overlap rule is hasOverlapBetweenRanges:

1. If the existing range's canBeSharedBy accepts the new one, there is no overlap. Only the existing range's predicate is consulted.
2. Intervals that only touch ((1, 2) and (2, 3)) don't overlap.
3. Intervals with the same start overlap only if both have positive length. Zero-length ranges, which an edge between adjacent rows produces, therefore never collide.

The two predicates live in CRITERIA in preprocess.ts. fromSameParent is used for edge columns (fan-out may share a line). toSameChild is used for a node's own stub and for horizontal runs (fan-in may share a line).

6. Focus mode

getFocusedCommits(commits) runs before layout, in JjApp.setState, whenever the state's options carry a disableFocusMode command. The option is named for the link that turns the mode off, so providing that command is what turns the mode on (source).

1. It throws No working copy commit found. unless some commit has active set.
2. It builds a hash map and a child-to-parents map. A dangling child hash throws.
3. getReachableCommits walks out from the working copy through both parents and children, using an explicit stack. A commit reached this way is always included, but it is only expanded further if it is mutable. Immutable commits are the boundary: the first immutable ancestor appears, and nothing beyond it does.
4. The result keeps the input order, with each commit's childrenHashes filtered down to focused commits, so the layout's "every child must be present" rule still holds.

The number hidden, state.commits.length − commits.length, becomes unfocusedCommits. jj-focus-mode-text renders "Disable focus mode to see the other N commits in this workspace" under the graph, and clicking it runs the command.

What "focused" means is broader than either doc comment says. The function's comment says the working copy, its ancestors and its descendants, and the option's comment says only ancestors. But because the walk goes up and down through any mutable commit, it also takes in siblings and cousins joined through a mutable ancestor. The one test, returns the working copy commit, its ancestors, and its descendants, shows this. In its graph, f is the working copy, and h, a sibling of f on the mutable parent e, is kept. p4base is immutable, so it is kept but not expanded, which drops its other child b, its parent p4base-ancestor and that commit's child a. p4base's childrenHashes come back as ['c', 'd'].

7. Worked example

The example is the test case handles merge commits correctly: one commit a with five children, four of which (b to e) merge into f. The diagrams below were produced by running the pinned preprocess.ts on exactly this input. Every coordinate, column and tile matches what the test asserts. (The spec for this page asked for an elided range in the example too. The layout has none, as noted above.)

Stage 1: input

Stage 2: rows, columns and edge columns

The DFS numbers the commits a=0, b=1, f=2, c=3, d=4, e=5, g=6. Each of b, c, d and e reaches f, so all four subtrees have a smallest traverse order of 1 or 2, and g's is 6. Sorting a's children by that leaves them as given, and no swap happens. Rows go right to left through a's children: g, e, d, c and b. f waits until its last parent, b, has a row.

Column placement starts from a at column 0 and recurses into b, then f, which both fit in column 0. c can't take column 0, because a → b already holds rows 0–4 there and it isn't from the same parent as c's stub, so c goes to column 1. Its edge to the already-placed f is a merge-back that keeps column 1 and turns left under f. d and e follow the same pattern one column further each. g fits back in column 1, because nothing reserves rows 0–1 there. a's own edges all share column 0 thanks to fromSameParent.

Stage 3: rendered rows

The drawer then turns every edge into tiles. The highlighted edge a → e is a common merge-out with one row between (k = 1), so it is up(3), upToRight, right(2), rightToUp: vertical through a's top tile and g's bottom and glyph tiles, a curve in g's top tile at column 0, horizontals on g's top edge at columns 1 and 2, and a RIGHT_TO_UP stored in g's top tile at column 3, which paints upward into e's bottom tile. The three merge-back edges into f, from c, d and e, all end in b's top tiles, as UP_TO_LEFT, HORIZONTAL and LEFT_TO_UP lines that share one run thanks to toSameChild. That is why b, c, d and e report occupiedColumns = 4 while g reports 2: right of its glyph its row holds only horizontals and a RIGHT_TO_UP, which take no room, so the count falls back to the glyph's own column.

8. Invariants and edge cases

preprocess_test.ts checks exact coordinates and the set of line types in every tile, so it pins the layout down tightly. Any change to the algorithm shows up as a changed expectation. Its helpers coordinatesOf, linesOf, insertActionsOf and multiLineTileGroupsOf project nodes down to those values (source), and commits are built with newCommit(hash, children).

A few edge cases are visible in the code but not tested: an empty input returns an empty map, and focus mode on an empty array returns [] before looking for a working copy. Three internal-consistency checks throw: no root found for a component, the n² swap bound, and the column-10,000 bound. Only the missing-child error is reachable from bad input. The other three report bugs in the algorithm.