monolith

public
Star0
Watch0
47 commits 1 branch 0 tags 0 releases1.5 MiB
//! Window organisation without smithay. Tags with per-output views, one
//! tiling tree per output filtered by those views, floating windows,
//! scratchpads, focus, and restoring windows when an output comes back.

mod tree;

#[cfg(test)]
mod tests;

pub use monolith_planner::Rect;
pub use tree::{Axis, Dir, Tree};

use slotmap::{SlotMap, new_key_type};
use std::collections::HashMap;

new_key_type! {
    pub struct WindowId;
    pub struct TagId;
    pub struct OutputId;
}

pub const HOMELESS: &str = "homeless";

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ExpandScope {
    Window,
    Container,
    All,
}

/// Space taken from an output's edges by bars and other panels.
#[derive(Clone, Copy, Debug, PartialEq, Default)]
pub struct Insets {
    pub top: f64,
    pub right: f64,
    pub bottom: f64,
    pub left: f64,
}

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Gaps {
    pub inner: f64,
    pub outer: f64,
}

impl Default for Gaps {
    fn default() -> Self {
        Self {
            inner: 8.0,
            outer: 8.0,
        }
    }
}

#[derive(Clone, Debug)]
pub struct Window {
    pub output: Option<OutputId>,
    pub tag: TagId,
    pub floating: bool,
    pub float_rect: Option<Rect>,
    pub fullscreen: bool,
    pub sticky: bool,
    pub scratchpad: Option<usize>,
    evicted_from: Option<String>,
}

#[derive(Clone, Debug)]
pub struct Tag {
    pub name: String,
    pub urgent: bool,
}

#[derive(Clone, Debug)]
pub struct Output {
    pub name: String,
    pub area: Rect,
    pub reserved: Insets,
    pub tree: Tree<WindowId>,
    /// Viewed tags besides the homeless tag, which is always viewed.
    pub viewed: Vec<TagId>,
    /// Floating windows, bottom to top.
    pub floating: Vec<WindowId>,
}

#[derive(Clone, Debug)]
pub struct Scratchpad {
    pub name: String,
    pub windows: Vec<WindowId>,
    pub shown: Option<usize>,
    pub output: Option<OutputId>,
}

#[derive(Clone, Debug)]
struct Parked {
    tree: Tree<WindowId>,
    viewed: Vec<TagId>,
    floating: Vec<WindowId>,
    area: Rect,
}

#[derive(Clone, Debug, Default)]
pub struct Arrangement {
    /// Every tiled window on the output. Hidden ones are zero-size seeds.
    pub tiled: Vec<Placed>,
    /// Visible floating windows and shown scratchpads, bottom to top.
    pub floating: Vec<(WindowId, Rect)>,
    pub fullscreen: Option<WindowId>,
}

#[derive(Clone, Copy, Debug)]
pub struct Placed {
    pub window: WindowId,
    pub rect: Rect,
    pub visible: bool,
}

#[derive(Clone, Debug)]
pub struct Layout {
    windows: SlotMap<WindowId, Window>,
    tags: SlotMap<TagId, Tag>,
    tag_order: Vec<TagId>,
    homeless: TagId,
    outputs: SlotMap<OutputId, Output>,
    active: Option<OutputId>,
    /// Focus history, most recent last.
    history: Vec<WindowId>,
    scratchpads: Vec<Scratchpad>,
    last_scratchpad: Option<usize>,
    parked: HashMap<String, Parked>,
    pub gaps: Gaps,
}

impl Default for Layout {
    fn default() -> Self {
        let mut tags = SlotMap::with_key();
        let homeless = tags.insert(Tag {
            name: HOMELESS.into(),
            urgent: false,
        });
        Self {
            windows: SlotMap::with_key(),
            tags,
            tag_order: vec![homeless],
            homeless,
            outputs: SlotMap::with_key(),
            active: None,
            history: Vec::new(),
            scratchpads: Vec::new(),
            last_scratchpad: None,
            parked: HashMap::new(),
            gaps: Gaps::default(),
        }
    }
}

impl Layout {
    pub fn homeless(&self) -> TagId {
        self.homeless
    }

    /// Looks a tag up by name, creating it at the end of the order.
    pub fn tag(&mut self, name: &str) -> TagId {
        if let Some(id) = self.tag_id(name) {
            return id;
        }
        let id = self.tags.insert(Tag {
            name: name.into(),
            urgent: false,
        });
        self.tag_order.push(id);
        id
    }

    pub fn tag_id(&self, name: &str) -> Option<TagId> {
        self.tag_order
            .iter()
            .copied()
            .find(|&t| self.tags[t].name == name)
    }

    pub fn tags(&self) -> impl Iterator<Item = (TagId, &Tag)> {
        self.tag_order.iter().map(|&t| (t, &self.tags[t]))
    }

    pub fn reorder_tag(&mut self, tag: TagId, index: usize) {
        if let Some(i) = self.tag_order.iter().position(|&t| t == tag) {
            self.tag_order.remove(i);
            let index = index.min(self.tag_order.len());
            self.tag_order.insert(index, tag);
        }
    }

    pub fn window(&self, w: WindowId) -> Option<&Window> {
        self.windows.get(w)
    }

    pub fn windows(&self) -> impl Iterator<Item = (WindowId, &Window)> {
        self.windows.iter()
    }

    pub fn output(&self, o: OutputId) -> Option<&Output> {
        self.outputs.get(o)
    }

    pub fn outputs(&self) -> impl Iterator<Item = (OutputId, &Output)> {
        self.outputs.iter()
    }

    pub fn scratchpads(&self) -> &[Scratchpad] {
        &self.scratchpads
    }

    pub fn active_output(&self) -> Option<OutputId> {
        self.active
    }

    pub fn set_active_output(&mut self, o: OutputId) {
        if self.outputs.contains_key(o) {
            self.active = Some(o);
        }
    }

    /// Adds an output. One that was unplugged before gets back its tree,
    /// views and the windows that had to leave it.
    pub fn add_output(&mut self, name: &str, area: Rect) -> OutputId {
        let id = self.outputs.insert(Output {
            name: name.into(),
            area,
            reserved: Insets::default(),
            tree: Tree::default(),
            viewed: Vec::new(),
            floating: Vec::new(),
        });
        if let Some(parked) = self.parked.remove(name) {
            self.restore(id, parked);
        }
        self.active.get_or_insert(id);
        let detached: Vec<WindowId> = self
            .windows
            .iter()
            .filter(|(_, w)| w.output.is_none())
            .map(|(id, _)| id)
            .collect();
        for w in detached {
            self.windows[w].output = Some(id);
            self.place(w);
        }
        id
    }

    fn restore(&mut self, id: OutputId, parked: Parked) {
        let name = self.outputs[id].name.clone();
        let ours = |l: &Self, w: WindowId| {
            l.windows
                .get(w)
                .is_some_and(|x| x.evicted_from.as_deref() == Some(&name) && x.scratchpad.is_none())
        };
        let mut tree = parked.tree;
        tree.retain(|w| ours(self, w) && !self.windows[w].floating);
        let floating: Vec<WindowId> = parked
            .floating
            .into_iter()
            .filter(|&w| ours(self, w) && self.windows[w].floating)
            .collect();
        for w in tree
            .windows()
            .chain(floating.iter().copied())
            .collect::<Vec<_>>()
        {
            self.unplace(w);
            let win = &mut self.windows[w];
            if let (Some(from), Some(rect)) = (win.output, win.float_rect) {
                win.float_rect = Some(translate(rect, self.outputs[from].area, parked.area));
            }
            win.output = Some(id);
            win.evicted_from = None;
        }
        let out = &mut self.outputs[id];
        out.tree = tree;
        out.floating = floating;
        out.viewed = parked
            .viewed
            .into_iter()
            .filter(|&t| self.tags.contains_key(t))
            .collect();
    }

    /// Removes an output. Its windows move to an output viewing their tag,
    /// or the active one, and remember where they came from.
    pub fn remove_output(&mut self, o: OutputId) {
        let Some(out) = self.outputs.remove(o) else {
            return;
        };
        self.parked.insert(
            out.name.clone(),
            Parked {
                tree: out.tree,
                viewed: out.viewed,
                floating: out.floating,
                area: out.area,
            },
        );
        if self.active == Some(o) {
            self.active = self.outputs.keys().next();
        }
        for sp in &mut self.scratchpads {
            if sp.output == Some(o) {
                sp.output = self.active;
            }
        }
        let leaving: Vec<WindowId> = self
            .windows
            .iter()
            .filter(|(_, w)| w.output == Some(o))
            .map(|(id, _)| id)
            .collect();
        for w in leaving {
            let tag = self.windows[w].tag;
            let target = self
                .outputs
                .keys()
                .find(|&t| self.is_viewed(t, tag))
                .or(self.active);
            let win = &mut self.windows[w];
            if let (Some(t), Some(rect)) = (target, win.float_rect) {
                win.float_rect = Some(translate(rect, out.area, self.outputs[t].area));
            }
            win.output = target;
            if win.scratchpad.is_some() {
                continue;
            }
            win.evicted_from = Some(out.name.clone());
            if target.is_some() {
                self.place(w);
            }
        }
    }

    pub fn set_output_area(&mut self, o: OutputId, area: Rect) {
        if let Some(out) = self.outputs.get_mut(o) {
            out.area = area;
        }
    }

    /// Returns whether anything changed.
    pub fn set_reserved(&mut self, o: OutputId, reserved: Insets) -> bool {
        match self.outputs.get_mut(o) {
            Some(out) if out.reserved != reserved => {
                out.reserved = reserved;
                true
            }
            _ => false,
        }
    }

    pub fn is_viewed(&self, o: OutputId, tag: TagId) -> bool {
        tag == self.homeless
            || self
                .outputs
                .get(o)
                .is_some_and(|out| out.viewed.contains(&tag))
    }

    /// Views `tag` alone, besides the homeless tag.
    pub fn view(&mut self, o: OutputId, tag: TagId) {
        let Some(out) = self.outputs.get_mut(o) else {
            return;
        };
        out.viewed.clear();
        if tag != self.homeless {
            out.viewed.push(tag);
        }
        self.tags[tag].urgent = false;
    }

    pub fn toggle_view(&mut self, o: OutputId, tag: TagId) {
        if tag == self.homeless {
            return;
        }
        let Some(out) = self.outputs.get_mut(o) else {
            return;
        };
        if let Some(i) = out.viewed.iter().position(|&t| t == tag) {
            out.viewed.remove(i);
        } else {
            out.viewed.push(tag);
            self.tags[tag].urgent = false;
        }
    }

    /// The tag a launch from `o` belongs to. The focused window's tag, else
    /// the first viewed tag, else homeless. Homeless is always on screen, so
    /// focusing one of its windows does not mean the user left their tag.
    pub fn launch_tag(&self, o: OutputId) -> TagId {
        self.focused_on(o)
            .map(|w| &self.windows[w])
            .filter(|w| w.scratchpad.is_none() && !w.sticky && w.tag != self.homeless)
            .map(|w| w.tag)
            .or_else(|| self.outputs.get(o)?.viewed.first().copied())
            .unwrap_or(self.homeless)
    }

    pub fn view_everywhere(&mut self, tag: TagId) {
        for o in self.outputs.keys().collect::<Vec<_>>() {
            self.view(o, tag);
        }
    }

    pub fn visible(&self, w: WindowId) -> bool {
        let Some(win) = self.windows.get(w) else {
            return false;
        };
        let Some(o) = win.output else {
            return false;
        };
        match win.scratchpad {
            Some(s) => {
                let sp = &self.scratchpads[s];
                sp.output == Some(o) && sp.shown.map(|i| sp.windows[i]) == Some(w)
            }
            None => win.sticky || self.is_viewed(o, win.tag),
        }
    }

    /// Adds a window on `output` (default the active one) and `tag` (default
    /// homeless). A window landing on a tag its output is not viewing marks
    /// the tag urgent.
    pub fn add_window(
        &mut self,
        output: Option<OutputId>,
        tag: Option<TagId>,
        floating: Option<Rect>,
    ) -> WindowId {
        let output = output
            .filter(|&o| self.outputs.contains_key(o))
            .or(self.active);
        let tag = tag
            .filter(|&t| self.tags.contains_key(t))
            .unwrap_or(self.homeless);
        let w = self.windows.insert(Window {
            output,
            tag,
            floating: floating.is_some(),
            float_rect: floating,
            fullscreen: false,
            sticky: false,
            scratchpad: None,
            evicted_from: None,
        });
        if let Some(o) = output {
            if !self.is_viewed(o, tag) {
                self.tags[tag].urgent = true;
            }
            self.place(w);
        }
        w
    }

    pub fn remove_window(&mut self, w: WindowId) {
        if !self.windows.contains_key(w) {
            return;
        }
        self.unplace(w);
        self.history.retain(|&h| h != w);
        if let Some(s) = self.windows[w].scratchpad {
            self.leave_scratchpad(s, w);
        }
        self.windows.remove(w);
    }

    /// Puts a window into its output's tree or floating stack. Tiled windows
    /// go next to the focused window if both are visible, else next to the
    /// latest window of their tag, else into a new row.
    fn place(&mut self, w: WindowId) {
        let win = &self.windows[w];
        let Some(o) = win.output else { return };
        if win.scratchpad.is_some() {
            return;
        }
        if win.floating {
            if win.float_rect.is_none() {
                let rect = centred(self.outputs[o].area, 0.6);
                self.windows[w].float_rect = Some(rect);
            }
            self.outputs[o].floating.push(w);
            return;
        }
        let tag = win.tag;
        let tree = &self.outputs[o].tree;
        let focused = self
            .focused()
            .filter(|&f| tree.contains(f) && self.is_viewed(o, tag));
        let anchor = focused.or_else(|| {
            self.history
                .iter()
                .rev()
                .copied()
                .find(|&h| tree.contains(h) && self.windows[h].tag == tag)
        });
        let tree = &mut self.outputs[o].tree;
        match anchor {
            Some(a) => tree.insert_after(w, a),
            None => tree.insert_row(w),
        }
    }

    fn unplace(&mut self, w: WindowId) {
        let Some(o) = self.windows[w].output else {
            return;
        };
        let out = &mut self.outputs[o];
        out.tree.remove(w);
        out.floating.retain(|&f| f != w);
    }

    pub fn focus(&mut self, w: WindowId) {
        let Some(win) = self.windows.get(w) else {
            return;
        };
        self.active = win.output.or(self.active);
        if let Some(o) = win.output {
            let stack = &mut self.outputs[o].floating;
            if let Some(i) = stack.iter().position(|&f| f == w) {
                stack.remove(i);
                stack.push(w);
            }
        }
        self.history.retain(|&h| h != w);
        self.history.push(w);
    }

    /// The most recently focused visible window.
    pub fn focused(&self) -> Option<WindowId> {
        self.history
            .iter()
            .rev()
            .copied()
            .find(|&w| self.visible(w))
    }

    /// The most recently focused visible window on `o`.
    pub fn focused_on(&self, o: OutputId) -> Option<WindowId> {
        self.history
            .iter()
            .rev()
            .copied()
            .find(|&w| self.windows[w].output == Some(o) && self.visible(w))
    }

    /// Focuses the nearest visible window in `dir`, crossing to the next
    /// output when there is none on this one.
    pub fn focus_dir(&mut self, dir: Dir) -> Option<WindowId> {
        let o = self.active?;
        let from = self.focused_on(o).and_then(|f| self.rect_of(f));
        let target = from.and_then(|from| {
            let arr = self.arrange(o);
            let candidates = arr
                .tiled
                .iter()
                .filter(|p| p.visible)
                .map(|p| (p.window, p.rect))
                .chain(arr.floating.iter().copied())
                .filter(|&(w, _)| Some(w) != self.focused_on(o));
            nearest(from, dir, candidates)
        });
        if let Some(w) = target {
            self.focus(w);
            return Some(w);
        }
        let next = self.output_towards(o, dir)?;
        self.active = Some(next);
        let w = self.focused_on(next);
        if let Some(w) = w {
            self.focus(w);
        }
        w
    }

    pub fn output_towards(&self, from: OutputId, dir: Dir) -> Option<OutputId> {
        let here = self.outputs.get(from)?.area;
        let others = self
            .outputs
            .iter()
            .filter(|&(id, _)| id != from)
            .map(|(id, out)| (id, out.area));
        nearest(here, dir, others)
    }

    fn rect_of(&self, w: WindowId) -> Option<Rect> {
        let o = self.windows.get(w)?.output?;
        let arr = self.arrange(o);
        arr.tiled
            .iter()
            .find(|p| p.window == w)
            .map(|p| p.rect)
            .or_else(|| arr.floating.iter().find(|f| f.0 == w).map(|f| f.1))
    }

    fn vis_on(&self, o: OutputId) -> impl Fn(WindowId) -> bool + '_ {
        move |w| self.windows[w].output == Some(o) && self.visible(w)
    }

    fn focused_tiled(&self) -> Option<(WindowId, OutputId)> {
        let w = self.focused()?;
        let o = self.windows[w].output?;
        self.outputs[o].tree.contains(w).then_some((w, o))
    }

    pub fn move_window(&mut self, dir: Dir) -> bool {
        let Some((w, o)) = self.focused_tiled() else {
            return false;
        };
        let mut tree = std::mem::take(&mut self.outputs[o].tree);
        let moved = tree.move_window(w, dir, self.vis_on(o));
        self.outputs[o].tree = tree;
        moved
    }

    pub fn move_container(&mut self, dir: Dir) -> bool {
        let Some((w, o)) = self.focused_tiled() else {
            return false;
        };
        let mut tree = std::mem::take(&mut self.outputs[o].tree);
        let moved = tree.move_container(w, dir, self.vis_on(o));
        self.outputs[o].tree = tree;
        moved
    }

    pub fn merge_window(&mut self, dir: Dir) -> bool {
        let Some((w, o)) = self.focused_tiled() else {
            return false;
        };
        let mut tree = std::mem::take(&mut self.outputs[o].tree);
        let merged = tree.merge_window(w, dir, self.vis_on(o));
        self.outputs[o].tree = tree;
        merged
    }

    /// Whether a tiled window fills its output through expansion.
    pub fn maximized(&self, w: WindowId) -> bool {
        let Some(o) = self.windows.get(w).and_then(|w| w.output) else {
            return false;
        };
        self.outputs[o].tree.maximized(w)
    }

    pub fn resize(&mut self, axis: Axis, delta: f64) -> bool {
        let Some((w, o)) = self.focused_tiled() else {
            return false;
        };
        let mut tree = std::mem::take(&mut self.outputs[o].tree);
        let done = tree.resize(w, axis, delta, self.vis_on(o));
        self.outputs[o].tree = tree;
        done
    }

    pub fn expand(&mut self, scope: ExpandScope) -> bool {
        let Some((w, o)) = self.focused_tiled() else {
            return false;
        };
        let (skip, count) = match scope {
            ExpandScope::Window => (0, 1),
            ExpandScope::Container => (1, 1),
            ExpandScope::All => (0, usize::MAX),
        };
        self.outputs[o].tree.toggle_expand(w, skip, count)
    }

    pub fn flip(&mut self, o: OutputId) {
        if let Some(out) = self.outputs.get_mut(o) {
            out.tree.flip();
        }
    }

    /// Retags a window. It keeps its slot and disappears if the new tag is
    /// not viewed.
    pub fn set_tag(&mut self, w: WindowId, tag: TagId) {
        if self.tags.contains_key(tag)
            && let Some(win) = self.windows.get_mut(w)
        {
            win.tag = tag;
        }
    }

    pub fn send_to_output(&mut self, w: WindowId, o: OutputId) {
        let Some(win) = self.windows.get(w) else {
            return;
        };
        if !self.outputs.contains_key(o) || win.output == Some(o) || win.scratchpad.is_some() {
            return;
        }
        let from = win.output.map(|f| self.outputs[f].area);
        self.unplace(w);
        let win = &mut self.windows[w];
        if let (Some(from), Some(rect)) = (from, win.float_rect) {
            win.float_rect = Some(translate(rect, from, self.outputs[o].area));
        }
        win.output = Some(o);
        win.evicted_from = None;
        self.place(w);
    }

    /// Switches a window between tiled and floating. A scratchpad window
    /// leaves its scratchpad and tiles on the tag being viewed, since its own
    /// tag may well be hidden.
    pub fn toggle_floating(&mut self, w: WindowId) {
        let Some(win) = self.windows.get(w) else {
            return;
        };
        if let Some(s) = win.scratchpad {
            let o = win.output.or(self.active);
            let tag = o.map_or(self.homeless, |o| self.launch_tag(o));
            self.leave_scratchpad(s, w);
            let win = &mut self.windows[w];
            win.output = o;
            win.tag = tag;
            win.floating = false;
            self.place(w);
            return;
        }
        self.unplace(w);
        let win = &mut self.windows[w];
        win.floating = !win.floating;
        self.place(w);
    }

    pub fn set_float_rect(&mut self, w: WindowId, rect: Rect) {
        if let Some(win) = self.windows.get_mut(w) {
            win.float_rect = Some(rect);
        }
    }

    pub fn toggle_fullscreen(&mut self, w: WindowId) {
        if let Some(win) = self.windows.get_mut(w) {
            win.fullscreen = !win.fullscreen;
        }
    }

    pub fn toggle_sticky(&mut self, w: WindowId) {
        if let Some(win) = self.windows.get_mut(w) {
            win.sticky = !win.sticky;
        }
    }

    /// Adds a window to a named scratchpad, creating it. Scratchpad windows
    /// float and are shown only by summoning.
    pub fn scratchpad_add(&mut self, w: WindowId, name: &str) {
        let Some(win) = self.windows.get(w) else {
            return;
        };
        if let Some(s) = win.scratchpad {
            self.leave_scratchpad(s, w);
        }
        self.unplace(w);
        let s = match self.scratchpads.iter().position(|sp| sp.name == name) {
            Some(s) => s,
            None => {
                self.scratchpads.push(Scratchpad {
                    name: name.into(),
                    windows: Vec::new(),
                    shown: None,
                    output: None,
                });
                self.scratchpads.len() - 1
            }
        };
        self.scratchpads[s].windows.push(w);
        let area = self.windows[w].output.map(|o| self.outputs[o].area);
        let win = &mut self.windows[w];
        win.scratchpad = Some(s);
        win.floating = true;
        if win.float_rect.is_none() {
            win.float_rect = area.map(|a| centred(a, 0.6));
        }
    }

    /// Cycles a scratchpad through off, each window, and off again, on the
    /// active output.
    pub fn summon(&mut self, name: &str) -> Option<WindowId> {
        let s = self.scratchpads.iter().position(|sp| sp.name == name)?;
        let o = self.active?;
        let sp = &mut self.scratchpads[s];
        let next = match sp.shown {
            None => 0,
            Some(i) => i + 1,
        };
        if next >= sp.windows.len() {
            sp.shown = None;
            return None;
        }
        let from = sp.output.map(|f| self.outputs[f].area);
        sp.shown = Some(next);
        sp.output = Some(o);
        let w = sp.windows[next];
        self.last_scratchpad = Some(s);
        let area = self.outputs[o].area;
        let win = &mut self.windows[w];
        if win.output != Some(o) {
            win.float_rect = match (from, win.float_rect) {
                (Some(from), Some(r)) => Some(translate(r, from, area)),
                _ => Some(centred(area, 0.6)),
            };
            win.output = Some(o);
        }
        self.focus(w);
        Some(w)
    }

    /// Hides a scratchpad, by default the last one summoned.
    pub fn dismiss(&mut self, name: Option<&str>) {
        let s = match name {
            Some(name) => self.scratchpads.iter().position(|sp| sp.name == name),
            None => self.last_scratchpad,
        };
        if let Some(sp) = s.and_then(|s| self.scratchpads.get_mut(s)) {
            sp.shown = None;
        }
    }

    fn leave_scratchpad(&mut self, s: usize, w: WindowId) {
        let sp = &mut self.scratchpads[s];
        let Some(i) = sp.windows.iter().position(|&x| x == w) else {
            return;
        };
        sp.windows.remove(i);
        sp.shown = match sp.shown {
            Some(j) if j == i => None,
            Some(j) if j > i => Some(j - 1),
            other => other,
        };
        self.windows[w].scratchpad = None;
    }

    /// Target geometry for everything on `o`, in output-local logical
    /// coordinates offset by the output's area.
    pub fn arrange(&self, o: OutputId) -> Arrangement {
        self.arrange_hiding(o, &[])
    }

    /// Like `arrange` with `hide` treated as hidden, which places them on the
    /// seeds they would grow from.
    pub fn arrange_hiding(&self, o: OutputId, hide: &[WindowId]) -> Arrangement {
        let Some(out) = self.outputs.get(o) else {
            return Arrangement::default();
        };
        let r = out.reserved;
        let usable = Rect::new(
            out.area.x + r.left,
            out.area.y + r.top,
            (out.area.w - r.left - r.right).max(0.0),
            (out.area.h - r.top - r.bottom).max(0.0),
        );
        let area = inset(usable, self.gaps.outer);
        let shown = self.vis_on(o);
        let vis = &|w: WindowId| shown(w) && !hide.contains(&w);
        let tiled = out
            .tree
            .arrange(area, self.gaps.inner, vis)
            .into_iter()
            .map(|(window, rect)| Placed {
                window,
                rect,
                visible: vis(window),
            })
            .collect();
        let mut floating: Vec<(WindowId, Rect)> = out
            .floating
            .iter()
            .copied()
            .filter(|&w| vis(w))
            .filter_map(|w| Some((w, self.windows[w].float_rect?)))
            .collect();
        for sp in &self.scratchpads {
            if let Some(i) = sp.shown
                && sp.output == Some(o)
                && let Some(r) = self.windows[sp.windows[i]].float_rect
            {
                floating.push((sp.windows[i], r));
            }
        }
        let fullscreen = self
            .history
            .iter()
            .rev()
            .copied()
            .find(|&w| self.windows[w].fullscreen && vis(w));
        Arrangement {
            tiled,
            floating,
            fullscreen,
        }
    }

    #[cfg(test)]
    pub(crate) fn check(&self) {
        for (o, out) in &self.outputs {
            out.tree.check();
            for w in out.tree.windows() {
                let win = &self.windows[w];
                assert_eq!(win.output, Some(o));
                assert!(!win.floating && win.scratchpad.is_none());
            }
            for &w in &out.floating {
                assert_eq!(self.windows[w].output, Some(o));
                assert!(self.windows[w].floating);
            }
        }
        for (w, win) in &self.windows {
            let homes = self
                .outputs
                .values()
                .filter(|out| out.tree.contains(w) || out.floating.contains(&w))
                .count();
            let expected = usize::from(win.output.is_some() && win.scratchpad.is_none());
            assert_eq!(homes, expected, "window placed {homes} times");
        }
    }
}

fn nearest<K: Copy>(
    from: Rect,
    dir: Dir,
    candidates: impl Iterator<Item = (K, Rect)>,
) -> Option<K> {
    const TOL: f64 = 0.5;
    let score = |r: Rect| -> Option<(bool, f64, f64)> {
        let (gap, overlap, offset) = match dir {
            Dir::Right => (
                r.x - from.right(),
                span_overlap(from.y, from.h, r.y, r.h),
                r.center_y() - from.center_y(),
            ),
            Dir::Left => (
                from.x - r.right(),
                span_overlap(from.y, from.h, r.y, r.h),
                r.center_y() - from.center_y(),
            ),
            Dir::Down => (
                r.y - from.bottom(),
                span_overlap(from.x, from.w, r.x, r.w),
                r.center_x() - from.center_x(),
            ),
            Dir::Up => (
                from.y - r.bottom(),
                span_overlap(from.x, from.w, r.x, r.w),
                r.center_x() - from.center_x(),
            ),
        };
        (gap > -TOL).then_some((overlap <= 0.0, gap.max(0.0), offset.abs()))
    };
    candidates
        .filter_map(|(k, r)| score(r).map(|s| (k, s)))
        .min_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal))
        .map(|(k, _)| k)
}

fn span_overlap(a: f64, al: f64, b: f64, bl: f64) -> f64 {
    (a + al).min(b + bl) - a.max(b)
}

fn inset(r: Rect, by: f64) -> Rect {
    Rect::new(
        r.x + by,
        r.y + by,
        (r.w - 2.0 * by).max(0.0),
        (r.h - 2.0 * by).max(0.0),
    )
}

fn centred(area: Rect, frac: f64) -> Rect {
    let (w, h) = (area.w * frac, area.h * frac);
    Rect::new(
        area.x + (area.w - w) / 2.0,
        area.y + (area.h - h) / 2.0,
        w,
        h,
    )
}

/// Keeps a rect at the same relative spot when it changes output.
fn translate(r: Rect, from: Rect, to: Rect) -> Rect {
    let sx = if from.w > 0.0 { to.w / from.w } else { 1.0 };
    let sy = if from.h > 0.0 { to.h / from.h } else { 1.0 };
    Rect::new(
        to.x + (r.x - from.x) * sx,
        to.y + (r.y - from.y) * sy,
        r.w.min(to.w),
        r.h.min(to.h),
    )
}