monolith planner, draft 1
Design for the multiphase layout animation planner (milestone M1). Every demo runs a small JavaScript port of the proposed algorithm, so what you see is what the design does. Red means two windows overlap.
1. What the planner does
The layout engine produces a target rectangle for every window. The planner turns "where windows are on screen now" and "where they should be" into a short sequence of keyframe layouts. Each step between two keyframes is a phase. Every window in a phase moves on the same curve and the phase takes exactly t, the configured duration, so a plan lasts phases × t.
Rules carried over from wry master.
- Tiled windows never overlap while they move.
- Phases are synchronised. Everything in a phase starts and stops together.
- An interrupt throws the plan away and replans from what is on screen. Plans never stack.
New requirements wry never met.
- Diagonal moves, moves between outputs, and large groups such as viewing or hiding a tag.
- Best-effort velocity continuity when an interrupt lands mid-phase.
- A hard bound on plan length, so interrupts can never produce long animations.
2. The problem
Swapping two windows by interpolating straight from start to end drives them through each other. Toggle "naive" to compare.
3. The core rule, shared separators
For any two windows there are four ways they can be apart. A is left of B, right of B, above B, or below B. Each is a linear inequality on window edges, for example A.right ≤ B.left. If an inequality holds at both ends of a phase and both windows move on the same curve, it holds for the whole phase, because every edge is the same weighted average of its start and end value.
So the planner's entire job reduces to this. Pick keyframes so that for every pair of windows, every two consecutive keyframes share at least one separating relation. Diagonal motion is perfectly safe under this rule. wry needed single-axis steps because its solver checked overlap directly. This rule proves it instead.
Looking at a single pair gives a lower bound on phases.
| pair goes from | to | minimum phases | why |
|---|---|---|---|
| left of | left of (any sizes) | 1 | relation shared |
| left of | above | 2 | needs a middle keyframe where A is both left of and above B |
| left of | right of | 3 | left and right can't both hold, so the pair must pass through above or below on the way |
The plan length is the worst pair, so every plan is 1, 2 or 3 phases, with one fallback described in section 10. The rule is sufficient, not necessary. Some overlap-free phases break it, and the Rust validator keeps an exact check for those, but the planner only constructs plans that satisfy it.
4. One phase
Anything that keeps the arrangement of windows intact is a single phase, including changes in both axes at once. That covers ratio changes, inserting and removing windows, splitting a column, and viewing or hiding a tag.
Seeds. A window that appears starts as a zero-size rectangle sitting on the edge where space will open. A closing window ends as one. A seed on an edge is already separated from its neighbours, so it obeys the rule from the first frame. wry grew spawns from the centre of their target, which overlaps the neighbours early in the phase while they are still making room.
Viewing and hiding a tag is the same thing at a larger scale. The new tag's windows are seeds on the edge where their row will open.
5. Two phases, axis order
When a pair turns a corner (left of becomes above), the middle keyframe is built from a mixed rectangle. Each window takes its horizontal extent from one end and its vertical extent from the other. "X first" means the window takes its target horizontal extent in phase 1 and its target vertical extent in phase 2. "Y first" is the reverse. Every window then moves along exactly one axis per phase.
Each window's choice is one boolean. Every pair rules out some of the four combinations, and each forbidden combination is a clause over two variables. That makes it a 2-SAT problem, solvable in linear time with no search. Windows that only change one axis use the same boolean to choose whether they move in phase 1 or phase 2, and the planner prefers phase 1 so nothing waits needlessly.
The style selector at the top matters here. Growing a window in both directions inside a grid is a valid single phase in direct style, because every pair keeps a relation. Orthogonal style forbids moving a window on both axes in one phase, which gives wry's look of making space first and then growing, at the cost of an extra phase.
6. Three phases, lanes
Reversals (left of becomes right of) need two middle keyframes. Windows shrink into lanes across the axis of travel, slide past each other, then expand. Two windows may share a lane only if they never pass each other. Windows stacked on top of each other must keep their stacking order in the lanes, at both ends. Picking lanes is a small constrained colouring problem. For a pure reordering of a row the lane count equals the length of the longest decreasing subsequence of the new order (Dilworth's theorem). Swapping two neighbours or rotating needs 2 lanes, and full reversal of four windows needs 4.
Only windows involved in a reversal enter lanes. Everything else moves in whichever phase validates, preferring the slide phase.
7. Tags as rigid blocks
Swapping the order of two viewed tags reverses every window of one tag against every window of the other. Planned window by window, that needs one lane per window (5 thin strips in the demo below). Planned with each tag as a rigid block, it needs 2 lanes, and the windows ride inside their block. The block planner is the same algorithm one level up, followed by mapping each window into its block's keyframes.
8. Interrupts and velocity
An interrupt samples the current on-screen rectangles and plans from there to the new target. The new plan has at most 3 phases, however many times you interrupt. Try the storm button, which fires a new target every few hundred milliseconds.
Velocity. The base curve starts and ends at rest, so a window that is moving when interrupted stops dead. Velocity matching measures how fast things were moving and starts the first phase of the new plan at that speed, by setting the first control point of the bezier so the initial slope matches. The slope only applies when the first phase continues in the direction things were already moving. Otherwise the window stops and turns, which reads as deliberate. The control point's height is clamped to 1, which mathematically rules out overshoot, since a cubic bezier never leaves the range of its control points.
One curve per motion group, never per window. Windows that share an edge must move that edge on the same curve or the edge tears open or overlaps. So the group gets a single curve, matched to its fastest mover. The graph shows window A's speed, and turning matching off shows the drop to zero at every interrupt.
9. Across outputs
Outputs live in one global coordinate space, so a move between outputs is planned like any other move and drawn clipped to each output. The window crosses the bezel and appears on the other side. Moving B over is one phase. Moving A over means A has to pass B, a reversal, so it takes lanes, and the lanes span both outputs.
Not shown. Outputs at different scales draw the same window at different sizes. The planner works in logical coordinates and each output scales its part. If two outputs aren't adjacent in the global space, the window would travel through empty space, and the pinch fallback is probably better there.
10. Fallback, pinch
If no 1, 2 or 3 phase plan validates, the windows that can't be routed shrink to a point, jump invisibly, and grow at their target. That's two visible phases, never overlaps, and always works. I couldn't find a tiling transition in these demos that needs it, but the bound has to hold for every input, including arbitrary floating-to-tiled transitions and malformed layouts.
11. Algorithm
plan(from, to):
groups = motion groups (windows whose swept areas can touch, transitively)
for each group:
if every pair shares a relation between from and to
and (style is direct or every window changes only one axis):
return [from, to] # 1 phase
if 2-SAT over axis order finds K1: # mixed rects
return [from, K1, to] # 2 phases
for lane_axis in [y, x]: # strips, then columns
for set in [windows in reversals, all movers, all]:
for k in 2..|set|:
if lanes assignable with k lanes and all three phases validate:
return [from, K1, K2, to] # 3 phases
return pinch(from, to) # 2 visible phases
rigid blocks: run plan() on block rectangles first, then map windows into them
interrupts: from = rectangles sampled at the current presentation time
velocity: first-phase curve per group, slope from the fastest mover,
applied only if moving the same way, control point height ≤ 1
validation: exact pairwise check over the curve actually used
Cost. Pair checks are O(n²) per group. 2-SAT is linear in clauses, so also O(n²). Lane assignment is backtracking over small sets with a greedy cut-off for large ones. Fifty windows is about 1,200 pairs, which is microseconds.
Everything here is pure geometry with no smithay dependency, so the planner crate gets property tests. Generate random layouts and random interrupt sequences, then check every frame of every plan for overlap, every plan for ≤ 3 phases, and every interrupt for continuity of position.
12. Compared with wry master
| wry master | this design |
|---|---|
| SingleAction, MixedSinglePhase | 1 phase, now including diagonal moves in direct style |
| SpaceThenOrthogonalGrowth, OrientationChange, HierarchyOrderedScales | 2 phases, one 2-SAT problem instead of three strategies |
| SwapLanes | 3 phases, general lane assignment for any permutation |
| ReversedForwardPlan | not needed, the construction is symmetric |
| Diagonal falls back to overlapping plain interpolation | diagonal is legal whenever relations are shared, pinch otherwise |
| Bridged retarget can make plans longer than the original | every replan is ≤ 3 phases |
| Per-phase duration, plans grow with strategy | per-phase duration kept, plan length bounded |
| Spawns grow from the target centre | spawns grow from a seed on the opening edge |
| Exact rational overlap check validates every plan | plans are correct by construction, the exact check remains as a safety net and for velocity-shaped curves |
| Cross-output moves skip animation | planned in global coordinates, clipped per output |
13. Interspersing tags (new, changes the layout model)
Row stacking answers "what does a combined view look like" but not "what happens when I drag A from tag 1's row in between D and E of tag 2". There are four answers.
| option | meaning | verdict |
|---|---|---|
| Forbid it | tags stay in their rows | limiting, as you said |
| Dragging retags | moving A into tag 2's row makes A a tag 2 window | honest and simple, but A then vanishes from tag 1 viewed alone, which is usually not what the drag meant |
| 2D positional merging (L/C/R × T/M/B) | windows merge into slots by position | kill it. Users must predict an implicit rule, and every edit in a combined view is ambiguous about which tag's tree it changes |
| Layout per view combination | each set of viewed tags gets its own tree, seeded by row stacking | no surprises between views, but N combinations of trees to keep in sync, and every new window has to be inserted into all of them |
| One tree per output, tags filter it | every window of every tag lives in a single tree per output. Viewing tags shows a projection with hidden windows collapsed. Each tag starts as its own row, so row stacking becomes the default arrangement instead of a merge rule | recommended |
The last option is dwm's model (one client list, tags as a filter) with a tree in place of the list. Its advantages are one source of truth and no sync problem. Interspersing is just moving a window in the tree. And for the planner, viewing or hiding any tag is always a single phase, because hidden windows are zero-weight seeds sitting at their own spot in the same tree. Switching views never rearranges anything.
Its cost is action at a distance. Intersperse A into tag 2's row below, then view tag 1 alone. A now sits under B and C, because in the tree it lives in the lower row. You changed tag 1's single view without ever viewing it alone. That's consistent, but some will find it surprising. It also reverses an earlier decision. Layout state moves from per tag-on-output to per output.