monolith planner, draft 2

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 tiled windows overlap. Orthogonal is the default style, and the selector at the top switches every demo to direct.

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.
• In orthogonal style, the default, a window moves or resizes along one axis per phase.
• An interrupt throws the plan away and replans from what is on screen. Plans never stack.
• Neighbours whose edges touch at both ends of a transition keep touching throughout. No holes open mid-plan.
• Planning B to A is the exact reverse of planning A to B, so undoing a change looks like rewinding it.

New requirements wry never met.

• 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, and a construction that never needs a fallback.

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. wry checked overlap after building a plan. This rule makes plans correct by construction.

Looking at a single pair gives a lower bound on phases.

Pairs interact, so a whole layout can need one more phase than its worst pair (section 7). Every plan is 1 to 4 phases, and the 4-phase construction works for any input, so no fallback is ever required. 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 builds plans that satisfy it.

Stress test of the JavaScript port. 6,000 random pairs of layouts with 2 to 7 windows, each target a full random reshuffle, in both styles. Zero overlapping frames, zero windows moving on two axes in one phase in orthogonal style, zero fallbacks. Real edits are far smaller than random reshuffles.

4. One phase, and seeds

Anything that keeps the arrangement of windows intact is a single phase. 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 and grows while its neighbours make room, concurrently, in the same phase. The only question is where it starts growing from.

• Line on the old boundary (default). A zero-width line where the two neighbours currently meet. It is always free space, so the whole insertion is one phase in either style.
• Point at the middle of the old boundary. Looks like growing from a centre, and never overlaps. Growing from a point changes both axes, so orthogonal style splits it into two phases (grow tall, then wide).
• Point at the centre of the new window's target. At the start of the phase that point is usually still covered by a neighbour that hasn't moved out yet. The planner has to push the neighbours away first and grow second. With naive on you see the overlap instead.

Cycle the seed mode below and insert D to compare.

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.

Coupled edges. Avoiding overlap is not enough. A window can vanish in phase 1 while the neighbour that absorbs its space only moves in phase 2, leaving a hole in between. Any two neighbours whose edges touch at both ends must also touch in the middle keyframe. Among valid orderings the solver picks one that keeps every such edge together, and only accepts a hole if none exists. In the 6,000-case stress test no two-phase plan needed one.

Rewind symmetry. Every pair of layouts is planned in one canonical direction, and the other direction plays that plan backwards. Insert D and split B with E together, and D arrives first, then E. Undo it, and E leaves first, then D.

Growing a window in both directions inside a grid. Orthogonal makes space along one axis and then grows along the other. Direct does it in one diagonal phase.

6. Three phases, lanes

A lane is a temporary strip, like a motorway lane used for overtaking. Before two windows can pass each other along one axis, each shrinks along the other axis into its own strip of the space they share. For a horizontal swap the strips are horizontal, so each window gets a slice of the height. In phase 2 they slide past each other inside their strips, and in phase 3 they expand back to full size.

• Two windows may share a lane only if they never pass each other.
• Windows stacked along the strip axis must keep their stacking order in the lanes, at both ends.
• Only windows that pass something enter lanes. Everything else moves in whichever phase validates, preferring the slide phase.
• The strips span only the band the involved windows occupy, not the whole output.

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 fully reversing four windows needs 4.

Lane extent. Below, T fills the top 70% and A, B, C share a short bottom row. Reversing the row needs 3 lanes. Spanning only the involved band, each lane is a third of the short row, so the windows get thin but T never moves. Spanning the whole output, the lanes are thicker, but T is in the way and has to squeeze into a lane too.

7. Four phases, the grid

Some transitions reverse windows along both axes at once. In (A over D) | (C over B) to (A over B over C) | D, D has to pass B and C horizontally while B and C swap vertical order. Lanes along either axis contradict the other reversal. The grid handles it.

1. Every involved window shrinks vertically into its own horizontal strip, ordered by where it starts.
2. It shrinks horizontally into its own column, ordered by where it ends. Every window is now a separate small cell.
3. It moves vertically to its final height. Its column keeps it clear of everything.
4. It expands horizontally to its final width.

Each step provably keeps every pair separated, whatever the input, so this is the guarantee behind "no fallback needed". It is also the ugliest plan, so the planner only reaches it after everything else fails, and only for the windows involved.

8. Joining and leaving stacks

These have historically been the hard cases. Notation A | B is side by side and A / B is A stacked over B. Click any layout to animate to it from whatever is on screen, including mid-animation.

9. Rigid blocks and movement commands

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. 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.

Both movement units exist as commands, for example meta+shift+hjkl moves a window and meta+ctrl+hjkl moves its block. The unit being moved decides the plan. A block move plans with rigid blocks, a window move plans per window.

10. Interrupts and velocity

An interrupt samples the current on-screen rectangles and plans from there to the new target. The new plan obeys the same bound 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 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 bezier's first control point so the initial slope matches. It only applies when the first phase continues in the direction things were already moving. Otherwise the window stops and turns. The control point's height is clamped to 1, which 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 it on the same curve, or the edge tears open or overlaps. Since phases are bounded by time rather than distance, the group's curve follows its fastest mover. The graph shows window A's speed. Turn matching off to see the drop to zero at every interrupt.

11. 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, since the planner works in logical coordinates and each output scales its part. If two outputs aren't adjacent in the global space, the window travels through empty space.

12. Floating, fullscreen and expand

A floating window joining the tiled layout travels above the tiled layer and is exempt from the overlap rule while it does. The mode button cycles three choreographies. Lifting out plays each one in reverse.

• Direct glide (default). F lerps straight into the slot while the gap opens, in one phase.
• Slot opens last. F travels one axis per phase until it hovers over its slot, then the gap opens and F lands as it widens.
• Slot opens first. The gap opens while F is still travelling, then F lands.

Fullscreen

Fullscreen uses the same direct glide. The window lifts above the tiled layer and lerps to cover the output in one phase. Its tiled slot stays where it is underneath, so leaving fullscreen glides back into it and nothing else moves either way.

Expand

Expand is a tiled operation, not a glide. The expanded window or subtree grows to fill its slot while its siblings are squeezed to zero-size lines against the slot's edges, so it follows the normal planner rules, orthogonal included. Expanding a window inside its column is one vertical phase. Expanding it to the whole output changes both axes, so orthogonal style takes two.

13. Fallbacks

The grid construction means no plan should ever need a fallback, and the stress test never reached one. Two remain wired in as safety nets for malformed input. Pinch shrinks a window to a point, jumps invisibly and regrows it. Lerp interpolates straight to the target and accepts overlap. Which one is the net is a matter of trying both.

14. Algorithm

plan(from, to):
  if from > to in a canonical order: return reverse(plan(to, from))
  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, preferring no holes: # 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
    for set in [windows in reversals, all movers, all]:
      if the grid validates for set:                       # always true for all
        return [from, K1, K2, K3, to]                      # 4 phases
    return fallback(from, to)                              # unreachable in theory

  rigid blocks: run plan() on block rectangles first, then map windows into them
  floating:     slot opens via plan() with a seed, floater travels x, then y, then lands
  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 at most 4 phases, every orthogonal phase for single-axis motion, and every interrupt for continuity of position.

15. Compared with wry master

16. Interspersing tags (open, 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 five answers.

The last option is dwm's model (one client list, tags as a filter) with a tree in place of the list. The tree is the record of every relative position, permanently, because hidden windows never leave it. Nothing has to be restored. 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. 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.

Hidden windows keep their slot. They are not coupled to visible neighbours. My earlier phrasing was wrong, and your version is the rule.

• The tree never moves a hidden leaf. Moves in a filtered view swap the slots of visible windows only. Swap A and B below with tag 2 hidden, then show it again, and D is still between them.
• Containers die by the normal rule, when one child is left, counting hidden children. A hidden only child is demoted into the grandparent at the container's position. Move C next to B below with tag 2 hidden. Row 2 is left holding only E, so it collapses and E becomes a full-width row of its own.
• A container holding only hidden children survives as long as it has two or more, invisible until they return.
• New windows insert next to the focused visible window.
• Hidden windows keep their share of a container's size when visible siblings are resized.

Tick "show hidden slots" to see where hidden windows will reappear.

17. Decisions

Settled

• Orthogonal is the default and the flagship look. Direct is a toggle.
• Window moves and block moves both exist as commands. Tag reordering moves rigid blocks.
• One curve per motion group, bounded by phase time rather than amount of motion.
• Seeds start as a line on the old boundary.
• Floating to tiled and fullscreen use a direct glide. Expand is tiled and follows the planner.
• One tree per output, tags filter it. Hidden windows keep their slots.
• The planner must never need a fallback. Pinch and lerp stay as safety nets to try.

Open