Look for a free spot before piling a new window on the last one

Reported: windows spawn predominantly on one side and on top of each other,
with no smart placement. Measured first, in a nested compositor: five
windows opened at 30,30 then 60,60 then 90,90 then 120,120 then 150,150 --
every pair overlapping, all in the top-left. The cascade was the only thing
running.

The grid never engaged, and could not. It asked whether a grid CELL was
free and then placed the window at that cell's corner at its own, larger
size. An ordinary 800x600 window on a 1280x800 screen overlaps every cell
of a 2x2 grid, so no cell was ever free, the grid returned nothing, and
everything fell through to the cascade.

Placement now looks for a position where the window overlaps nothing at
all, and only cascades when the screen genuinely cannot fit one - which is
what Windows does once its own screen fills up, and what makes the cascade
the right last resort rather than the first answer.

The candidates are the edges of what is already on screen: every window's
left and right edge plus the monitor's own, taken both as "put my left edge
here" and "put my right edge here", and the same vertically. That is
Openbox's place_overlap reduced to this case (~/reference-wms/openbox), and
it works because a rectangle packed against other rectangles is always
flush with one of their edges - nothing is gained by testing the space in
between.

Two things the naive version got wrong, both fixed here:

Ties go to the position nearest the middle of the monitor, and the choice
rotates through the four most central free spots. Least-overlap placement
is deterministic, so opening one window at a time - open, use, close, open
the next - put every one of them in exactly the same place, which is this
project's own earlier bug report. Every candidate rotated between is free,
so variety never costs the guarantee.

And placement now runs again once the client's real size is known. It has
to happen before the client commits anything, so it was deciding where an
800x600 placeholder should go rather than the window - a small terminal
was told it was 800x600, no two of those fit, and it cascaded. Only when
the client actually chooses a different size: re-running it otherwise
consumed a second cascade step for nothing, and the cascade wraps, which
measured as two windows landing on exactly the same spot.

287 core tests pass, clippy clean.

2 files changed, 93 insertions, 0 deletions

diff --git a/crates/core/src/manager/tests.rs b/crates/core/src/manager/tests.rs
index e20bb74..b5a54c0 100644
--- a/crates/core/src/manager/tests.rs
+++ b/crates/core/src/manager/tests.rs
@@ -116,6 +116,46 @@
         assert!(!win.size_is_provisional, "a deliberately remembered size must never be second-guessed by the client's own default");
     }
 
+    /// A client that accepts the size placement assumed must not be moved
+    /// again: re-placing would consume another cascade step for nothing,
+    /// and the cascade wraps - measured, two windows landing on exactly
+    /// the same spot because the extra steps wrapped one back to the origin.
+    #[test]
+    fn a_window_that_keeps_the_assumed_size_is_not_placed_twice() {
+        let mut wm = wm_with_monitor();
+        let id = wm.alloc_window_id();
+        wm.add_window(Window::new(id, "w"));
+        let placed = wm.window(id).unwrap().geometry;
+        assert!(!wm.replace_with_real_size(id, (placed.width, placed.height)));
+        assert_eq!(wm.window(id).unwrap().geometry, placed);
+    }
+
+    /// And a client that chooses a different size gets placed for the size
+    /// it really is, not for the placeholder a backend guessed.
+    #[test]
+    fn a_window_that_chooses_its_own_size_is_placed_again_for_it() {
+        let mut wm = wm_with_monitor();
+        let first = wm.alloc_window_id();
+        wm.add_window(Window::new(first, "first"));
+        let second = wm.alloc_window_id();
+        wm.add_window(Window::new(second, "second"));
+        let assumed = wm.window(second).unwrap().geometry;
+        // The client turns out to be much smaller than the placeholder.
+        {
+            let w = wm.window_mut(second).unwrap();
+            w.geometry.width = 300;
+            w.geometry.height = 200;
+        }
+        // The return value is an implementation detail - it says whether
+        // anything moved, and the right position may be the one it already
+        // had. What matters is where it ends up.
+        wm.replace_with_real_size(second, (assumed.width, assumed.height));
+        let placed = wm.window(second).unwrap().geometry;
+        assert_eq!((placed.width, placed.height), (300, 200), "the real size must be kept");
+        let other = wm.window(first).unwrap().geometry;
+        assert!(!other.overlaps(&placed), "a window small enough to fit clear should not be stacked: {other:?} vs {placed:?}");
+    }
+
     /// The real shape of the bug: a Wayland toplevel exists before its
     /// client sends `set_app_id`, so `add_window` searched the store for the
     /// empty string and every window fell through to a fresh cascade. That
diff --git a/crates/core/src/manager/windows.rs b/crates/core/src/manager/windows.rs
index 1e8a6cb..69d5e9e 100644
--- a/crates/core/src/manager/windows.rs
+++ b/crates/core/src/manager/windows.rs
@@ -411,6 +411,59 @@ impl WindowManager {
         self.order.iter().filter_map(|id| self.windows.get(id))
     }
 
+    /// Re-runs smart placement for a window that has just learned its real
+    /// size.
+    ///
+    /// `add_window` has to place a window before its client has committed
+    /// anything, so it places the placeholder size a backend guessed --
+    /// `800x600` - and not the size the window actually turns out to be.
+    /// Every placement decision was therefore made about the wrong
+    /// rectangle: measured on a 1280x800 screen, four small terminals were
+    /// all told they were 800x600, no two of those fit side by side, so
+    /// every one of them fell through to the cascade and landed on top of
+    /// the last. The windows themselves were a quarter of that size and
+    /// would have fitted four abreast.
+    ///
+    /// Called from the backend at the moment the client's real size is
+    /// adopted, which is still before its first buffer, so nothing has been
+    /// drawn at the placeholder-sized position.
+    ///
+    /// Only for a window still sitting where placement put it: a remembered
+    /// geometry, a rule, a dialog and a maximize have all already cleared
+    /// `size_is_provisional` by this point, and each is a more deliberate
+    /// decision than smart placement.
+    pub fn replace_with_real_size(&mut self, id: WindowId, placed_size: (u32, u32)) -> bool {
+        let Some(w) = self.windows.get(&id) else { return false };
+        if w.is_dialog || w.maximized || w.fullscreen {
+            return false;
+        }
+        // The client accepted the size placement already assumed, so the
+        // decision it made was about the right rectangle after all. Leaving
+        // it alone matters: re-running placement here would consume another
+        // cascade step for no reason, and the cascade wraps - measured, two
+        // windows landing on exactly the same spot because the extra steps
+        // wrapped one of them back to the origin.
+        if placed_size == (w.geometry.width, w.geometry.height) {
+            return false;
+        }
+        let (workspace, monitor_id, size) = (w.workspace, w.monitor, (w.geometry.width, w.geometry.height));
+        let layout_name = self.workspace(workspace).map(|ws| ws.layout.clone()).unwrap_or_default();
+        if layout_name == "tiling" {
+            return false;
+        }
+        let Some(monitor) = self.monitors.iter().find(|m| m.id == monitor_id).cloned() else { return false };
+        let existing: Vec<Rect> = self.windows_on_workspace(workspace).filter(|other| other.id != id).map(|other| other.geometry).collect();
+        let step = self.next_cascade_step.get();
+        self.next_cascade_step.set(step.wrapping_add(1));
+        let placed = SmartPlacement::place(&monitor, &existing, size, &self.placement, step);
+        let Some(w) = self.windows.get_mut(&id) else { return false };
+        if w.geometry == placed {
+            return false;
+        }
+        w.geometry = placed;
+        true
+    }
+
     pub(super) fn windows_on_workspace(&self, workspace: WorkspaceId) -> impl Iterator<Item = &Window> {
         self.windows.values().filter(move |w| w.workspace == workspace)
     }