monolith

public
Star0
Watch0
338 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 outputs;
mod scratchpad;
mod tree;

#[cfg(test)]
mod tests;

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

use outputs::Parked;
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>,
    /// `float_rect` is the layout's default, not a size the window or the
    /// user chose.
    pub float_default: bool,
    pub fullscreen: bool,
    /// The window this one is a dialog or other transient of.
    pub parent: Option<WindowId>,
    /// Focus aimed at the parent goes to this window while it is mapped.
    pub modal: bool,
    pub sticky: bool,
    pub scratchpad: Option<usize>,
    pub urgent: bool,
    /// Its client took the buffer away, as when hiding to a tray. The entry
    /// stays for when the client maps it again, but nothing shows or focuses it.
    pub hidden: bool,
    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>,
}

impl Output {
    /// The area left once bars and panels have taken their edges.
    pub fn usable(&self) -> Rect {
        let (a, r) = (self.area, self.reserved);
        Rect::new(
            a.x + r.left,
            a.y + r.top,
            (a.w - r.left - r.right).max(0.0),
            (a.h - r.top - r.bottom).max(0.0),
        )
    }
}

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

#[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>,
    /// Floating transients of the fullscreen window and shown scratchpads,
    /// which stay above it.
    pub over: Vec<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>,
    /// How many windows are modal, so focus lookups skip the scan for one.
    modals: usize,
    scratchpads: Vec<Scratchpad>,
    last_scratchpad: Option<usize>,
    parked: HashMap<String, Parked>,
    pub gaps: Gaps,
    pub autotile: bool,
}

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(),
            modals: 0,
            scratchpads: Vec::new(),
            last_scratchpad: None,
            parked: HashMap::new(),
            gaps: Gaps::default(),
            autotile: false,
        }
    }
}

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);
        }
    }

    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;
        }
    }

    /// Brings `w`'s tag into view beside the others when `w` is the only
    /// window on it there.
    pub fn view_if_alone(&mut self, w: WindowId) {
        let Some(win) = self.windows.get(w) else {
            return;
        };
        let (Some(o), tag) = (win.output, win.tag) else {
            return;
        };
        if win.scratchpad.is_some() || self.is_viewed(o, tag) {
            return;
        }
        let alone = !self.windows.iter().any(|(x, v)| {
            x != w && v.output == Some(o) && v.tag == tag && v.scratchpad.is_none() && !v.hidden
        });
        if alone {
            self.toggle_view(o, tag);
        }
    }

    /// The tag a launch from `o` belongs to, the focused window's tag or else
    /// homeless.
    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)
            .map_or(self.homeless, |w| w.tag)
    }

    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.filter(|_| !win.hidden) 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,
            float_default: false,
            fullscreen: false,
            parent: None,
            modal: false,
            sticky: false,
            scratchpad: None,
            urgent: false,
            hidden: false,
            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);
        self.modals -= usize::from(self.windows[w].modal);
        if let Some(s) = self.windows[w].scratchpad {
            self.leave_scratchpad(s, w);
        }
        for win in self.windows.values_mut() {
            if win.parent == Some(w) {
                win.parent = None;
            }
        }
        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 {
            let usable = self.outputs[o].usable();
            let win = &mut self.windows[w];
            match win.float_rect {
                Some(rect) => win.float_rect = Some(clamp_float(rect, usable)),
                None => {
                    win.float_rect = Some(centred(usable, 0.6));
                    win.float_default = true;
                }
            }
            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 split = anchor
            .filter(|_| self.autotile)
            .and_then(|a| self.split_axis(o, a));
        let mut tree = std::mem::take(&mut self.outputs[o].tree);
        let vis = self.vis_on(o);
        match (anchor, split) {
            (Some(a), Some(axis)) => tree.insert_split(w, a, axis, vis),
            (Some(a), None) => tree.insert_after(w, a, vis),
            (None, _) => tree.insert_row(w, vis),
        }
        self.outputs[o].tree = tree;
    }

    /// The axis a window opening beside `anchor` should split it along, the
    /// way the anchor is laid out right now. Hidden anchors have no shape.
    fn split_axis(&self, o: OutputId, anchor: WindowId) -> Option<Axis> {
        let rect = self
            .arrange(o)
            .tiled
            .iter()
            .find(|p| p.window == anchor && p.visible)?
            .rect;
        let axis = if rect.w > rect.h {
            Axis::Horizontal
        } else {
            Axis::Vertical
        };
        (rect.w > 0.0 && rect.h > 0.0).then_some(axis)
    }

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

    /// Focuses `w`, or the deepest modal dialog over it, which is returned.
    /// The windows between stay below it in the history, and a modal dialog
    /// focused on its own brings its parent up beneath it, so closing the
    /// dialog hands focus back to its parent.
    pub fn focus(&mut self, mut w: WindowId) -> Option<WindowId> {
        if self.eclipsed(w) {
            return None;
        }
        loop {
            let win = self.windows.get(w)?;
            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);
                }
            }
            let parent = win.parent.filter(|_| win.modal);
            self.history.retain(|&h| h != w);
            self.history.push(w);
            if let Some(p) = parent {
                self.history.retain(|&h| h != p);
                self.history.insert(self.history.len() - 1, p);
            }
            self.windows[w].urgent = false;
            match self.modal_child(w) {
                Some(child) => w = child,
                None => return Some(w),
            }
        }
    }

    /// Marks `w` as a modal dialog of its parent, or not.
    pub fn set_modal(&mut self, w: WindowId, modal: bool) {
        if let Some(win) = self.windows.get_mut(w)
            && std::mem::replace(&mut win.modal, modal) != modal
        {
            self.modals = if modal {
                self.modals + 1
            } else {
                self.modals - 1
            };
        }
    }

    /// The visible modal dialog of `w` on its output, the most recently
    /// focused if it has several.
    pub fn modal_child(&self, w: WindowId) -> Option<WindowId> {
        if self.modals == 0 {
            return None;
        }
        let output = self.windows.get(w)?.output;
        self.windows
            .iter()
            .filter(|&(c, win)| {
                win.modal && win.parent == Some(w) && win.output == output && self.visible(c)
            })
            .max_by_key(|&(c, _)| self.history.iter().rposition(|&h| h == c))
            .map(|(c, _)| c)
    }

    /// The window that takes focus aimed at `w`, the deepest modal dialog
    /// over it or `w` itself.
    pub fn modal_leaf(&self, mut w: WindowId) -> WindowId {
        while let Some(child) = self.modal_child(w) {
            w = child;
        }
        w
    }

    /// Whether focus aimed at `w` would change nothing.
    pub fn is_focused(&self, w: WindowId) -> bool {
        self.focused() == Some(self.modal_leaf(w))
    }

    /// The most recently focused visible window on the active output. Focus
    /// falling back to another output would leave keybinds acting on one
    /// output while the keyboard and pointer sit on another.
    pub fn focused(&self) -> Option<WindowId> {
        self.focused_on(self.active?)
    }

    /// 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) && !self.eclipsed(w))
            .map(|w| self.modal_leaf(w))
    }

    /// Focuses the nearest visible window in `dir` on the focused window's
    /// layer, tiled or floating, 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 current = self.focused_on(o);
        let from = current.and_then(|f| self.rect_of(f));
        let target = from.and_then(|from| {
            let arr = self.arrange(o);
            let floating = current.is_some_and(|f| arr.floating.iter().any(|p| p.0 == f));
            let candidates = self
                .layer(&arr, floating)
                .filter(|&(w, _)| Some(self.modal_leaf(w)) != current);
            if floating {
                nearest_centre(from, dir, candidates)
            } else {
                nearest(from, dir, candidates)
            }
        });
        if let Some(w) = target {
            return self.focus(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
    }

    /// Focuses the most recently focused window on the other layer, floating
    /// when a tiled window has focus and tiled otherwise.
    pub fn focus_layer(&mut self) -> Option<WindowId> {
        let o = self.active?;
        let arr = self.arrange(o);
        let floating = self
            .focused_on(o)
            .is_some_and(|f| arr.floating.iter().any(|p| p.0 == f));
        let w = self
            .layer(&arr, !floating)
            .map(|(w, _)| w)
            .max_by_key(|&w| self.history.iter().position(|&h| h == w))?;
        self.focus(w)
    }

    /// The windows focus can reach on one layer of an arrangement.
    fn layer<'a>(
        &'a self,
        arr: &'a Arrangement,
        floating: bool,
    ) -> impl Iterator<Item = (WindowId, Rect)> + 'a {
        let tiled = arr
            .tiled
            .iter()
            .filter(move |p| !floating && p.visible && !self.eclipsed(p.window))
            .map(|p| (p.window, p.rect));
        let floats = arr.floating.iter().copied().filter(move |_| floating);
        tiled.chain(floats).filter(|&(w, _)| {
            arr.fullscreen
                .is_none_or(|f| w == f || arr.over.contains(&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, merge: bool) -> 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, merge, 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, or a container holding it, is extended over
    /// others.
    pub fn extended(&self, w: WindowId) -> bool {
        let Some(o) = self.windows.get(w).and_then(|w| w.output) else {
            return false;
        };
        self.outputs[o].tree.extended(w, self.vis_on(o))
    }

    /// Whether another window is extended over the tiled window `w`, which
    /// leaves it no room and takes it out of reach of focus.
    pub fn eclipsed(&self, w: WindowId) -> bool {
        let Some(o) = self
            .windows
            .get(w)
            .filter(|w| !w.fullscreen)
            .and_then(|w| w.output)
        else {
            return false;
        };
        self.outputs[o].tree.eclipsed(w, self.vis_on(o))
    }

    /// 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, self.vis_on(o))
    }

    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 balance(&mut self) -> 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.balance(w, self.vis_on(o));
        self.outputs[o].tree = tree;
        done
    }

    /// Whether `w` is tiled with a visible window across the split on side `dir`.
    pub fn has_split(&self, w: WindowId, dir: Dir) -> bool {
        let Some(o) = self.windows.get(w).and_then(|w| w.output) else {
            return false;
        };
        self.outputs[o].tree.has_split(w, dir, self.vis_on(o))
    }

    /// Moves the split on side `dir` of the tiled window `w` by `px`, positive
    /// toward the right or bottom.
    pub fn move_split(&mut self, w: WindowId, dir: Dir, px: f64) -> bool {
        let Some(o) = self.windows.get(w).and_then(|w| w.output) else {
            return false;
        };
        let area = inset(self.outputs[o].usable(), self.gaps.outer);
        let mut tree = std::mem::take(&mut self.outputs[o].tree);
        let moved = tree.move_split(w, dir, px, area, self.gaps.inner, self.vis_on(o));
        self.outputs[o].tree = tree;
        moved
    }

    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),
        };
        let mut tree = std::mem::take(&mut self.outputs[o].tree);
        let expanded = tree.toggle_expand(w, skip, count, self.vis_on(o));
        self.outputs[o].tree = tree;
        expanded
    }

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

    /// Retags a window along with the windows it is extended over. They keep
    /// their slots and disappear if the new tag is not viewed.
    pub fn set_tag(&mut self, w: WindowId, tag: TagId) {
        let Some(win) = self.windows.get(w) else {
            return;
        };
        if !self.tags.contains_key(tag) {
            return;
        }
        let group = match win.output {
            Some(o) => self.outputs[o].tree.group_windows(w, self.vis_on(o)),
            None => vec![w],
        };
        for g in group {
            self.windows[g].tag = tag;
        }
    }

    /// Moves a window to `tag` on `o`, marking the tag urgent when the window
    /// ends up out of sight.
    pub fn relocate(&mut self, w: WindowId, o: Option<OutputId>, tag: TagId) {
        if let Some(o) = o {
            self.send_to_output(w, o);
        }
        self.set_tag(w, tag);
        self.mark_urgent(w);
    }

    /// Flags a window that wants attention unless it already has the focus,
    /// and its tag too when the window is out of sight.
    pub fn mark_urgent(&mut self, w: WindowId) {
        if self.windows.get(w).is_none_or(|win| win.hidden) {
            return;
        }
        if self.focused() != Some(w) {
            self.windows[w].urgent = true;
        }
        if !self.visible(w) {
            let tag = self.windows[w].tag;
            self.tags[tag].urgent = true;
        }
    }

    /// Drops the flag of the window holding the focus, which can reach it
    /// without `focus`, when the window before it closes or its tag is viewed.
    pub fn clear_focused_urgent(&mut self) {
        if let Some(w) = self.focused() {
            self.windows[w].urgent = false;
        }
    }

    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].usable());
        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].usable()));
        }
        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
                .and_then(|o| self.outputs.get(o)?.viewed.first().copied())
                .unwrap_or(self.homeless);
            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);
            win.float_default = false;
        }
    }

    /// Places a float without settling its size, so a window still deciding
    /// on one is asked again after being tiled.
    pub fn hold_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;
        }
    }

    /// Hides `w` or shows it again, keeping everything else about it.
    pub fn set_hidden(&mut self, w: WindowId, hidden: bool) {
        if let Some(win) = self.windows.get_mut(w) {
            win.hidden = hidden;
            win.urgent &= !hidden;
        }
    }

    /// 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 area = inset(out.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 floating = self.floating_on(o, out, vis);
        let fullscreen = self.fullscreen_in(vis);
        let over = fullscreen.map_or_else(Vec::new, |f| self.above_fullscreen(f, &floating));
        Arrangement {
            tiled,
            floating,
            fullscreen,
            over,
        }
    }

    fn floating_on(
        &self,
        o: OutputId,
        out: &Output,
        vis: &dyn Fn(WindowId) -> bool,
    ) -> Vec<(WindowId, Rect)> {
        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)
                && !self.windows[sp.windows[i]].hidden
                && let Some(r) = self.windows[sp.windows[i]].float_rect
            {
                floating.push((sp.windows[i], centre_in(out.usable(), r.w, r.h)));
            }
        }
        floating
    }

    fn fullscreen_in(&self, vis: &dyn Fn(WindowId) -> bool) -> Option<WindowId> {
        let is_fullscreen = |w: WindowId| self.windows[w].fullscreen && vis(w);
        self.history
            .iter()
            .rev()
            .copied()
            .find(|&w| is_fullscreen(w))
            .or_else(|| self.windows.keys().find(|&w| is_fullscreen(w)))
    }

    fn above_fullscreen(&self, f: WindowId, floating: &[(WindowId, Rect)]) -> Vec<WindowId> {
        floating
            .iter()
            .map(|&(w, _)| w)
            .filter(|&w| w != f && (self.descends(w, f) || self.windows[w].scratchpad.is_some()))
            .collect()
    }

    /// The fullscreen window of the output under (x, y), with the floating
    /// transients that stay above it. Cheaper than arranging the output.
    pub fn fullscreen_at(&self, x: f64, y: f64) -> Option<(WindowId, Vec<WindowId>)> {
        let (o, out) = self
            .outputs
            .iter()
            .find(|(_, out)| out.area.contains(x, y))?;
        let vis = self.vis_on(o);
        let f = self.fullscreen_in(&vis)?;
        Some((f, self.above_fullscreen(f, &self.floating_on(o, out, &vis))))
    }

    /// Records that `w` is a transient of `parent`.
    pub fn set_parent(&mut self, w: WindowId, parent: Option<WindowId>) {
        if parent.is_some_and(|p| p == w || self.descends(p, w)) {
            return;
        }
        if let Some(win) = self.windows.get_mut(w) {
            win.parent = parent;
        }
    }

    fn descends(&self, mut w: WindowId, of: WindowId) -> bool {
        for _ in 0..self.windows.len() {
            match self.windows.get(w).and_then(|x| x.parent) {
                Some(p) if p == of => return true,
                Some(p) => w = p,
                None => return false,
            }
        }
        false
    }

    /// Moves focus to a fullscreen `w` when it covers the focused window,
    /// unless that is one of its own transients.
    pub fn focus_if_covering(&mut self, w: WindowId) {
        let Some(win) = self.windows.get(w).filter(|win| win.fullscreen) else {
            return;
        };
        let covers = self.focused().is_some_and(|f| {
            f != w && self.windows[f].output == win.output && !self.descends(f, w)
        });
        if covers && self.visible(w) {
            self.focus(w);
        }
    }

    /// Focuses `w` unless it is out of sight or a fullscreen window hides it,
    /// flagging it urgent then. Returns whether it took the focus.
    pub fn focus_unless_covered(&mut self, w: WindowId) -> bool {
        if self.visible(w) && !self.covered(w) {
            self.focus(w);
            return true;
        }
        self.mark_urgent(w);
        false
    }

    /// Whether a fullscreen or extended window on `w`'s output hides it. The
    /// fullscreen window's transients and shown scratchpads are not hidden,
    /// and a window that is itself fullscreen takes over.
    pub fn covered(&self, w: WindowId) -> bool {
        if self.eclipsed(w) {
            return true;
        }
        let Some(win) = self.windows.get(w) else {
            return false;
        };
        let Some(o) = win.output else {
            return false;
        };
        let arr = self.arrange(o);
        !win.fullscreen && arr.fullscreen.is_some_and(|f| f != w) && !arr.over.contains(&w)
    }

    #[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)
}

/// The candidate whose centre is nearest `from`'s within 45 degrees of
/// `dir`. Floating windows overlap freely, so their edges say little about
/// which way one lies from another.
fn nearest_centre<K: Copy>(
    from: Rect,
    dir: Dir,
    candidates: impl Iterator<Item = (K, Rect)>,
) -> Option<K> {
    candidates
        .filter_map(|(k, r)| {
            let (dx, dy) = (
                r.center_x() - from.center_x(),
                r.center_y() - from.center_y(),
            );
            let (along, across) = match dir {
                Dir::Right => (dx, dy),
                Dir::Left => (-dx, dy),
                Dir::Down => (dy, dx),
                Dir::Up => (-dy, dx),
            };
            (along > 0.0 && along >= across.abs()).then_some((k, along.hypot(across)))
        })
        .min_by(|a, b| a.1.total_cmp(&b.1))
        .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 {
    centre_in(area, area.w * frac, area.h * frac)
}

/// A w by h rect centred in area, shrunk to fit it.
pub(crate) fn centre_in(area: Rect, w: f64, h: f64) -> Rect {
    let (w, h) = (w.min(area.w), h.min(area.h));
    Rect::new(
        area.x + (area.w - w) / 2.0,
        area.y + (area.h - h) / 2.0,
        w,
        h,
    )
}

/// The smallest a floating window gets when dragged or rescaled.
pub const MIN_FLOAT_SIZE: f64 = 32.0;

/// How much of a floating window stays reachable when it is larger than
/// the area it lives in.
const STRIP: f64 = 64.0;

/// Moves a floating rect to keep it reachable inside bounds. A window that
/// fits stays whole inside, a larger one keeps its top edge and a strip.
pub fn clamp_float(r: Rect, bounds: Rect) -> Rect {
    let x = if r.w <= bounds.w {
        r.x.clamp(bounds.x, bounds.right() - r.w)
    } else {
        let strip = STRIP.min(bounds.w);
        r.x.clamp(bounds.x + strip - r.w, bounds.right() - strip)
    };
    let y = if r.h <= bounds.h {
        r.y.clamp(bounds.y, bounds.bottom() - r.h)
    } else {
        r.y.clamp(bounds.y, bounds.bottom() - STRIP.min(bounds.h))
    };
    Rect::new(x, y, r.w, r.h)
}

/// Keeps a floating rect at the same relative spot and size when the area
/// it lives in changes.
fn translate(r: Rect, from: Rect, to: Rect) -> Rect {
    if to.w <= 0.0 || to.h <= 0.0 {
        return r;
    }
    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 };
    let scaled = Rect::new(
        to.x + (r.x - from.x) * sx,
        to.y + (r.y - from.y) * sy,
        (r.w * sx).max(MIN_FLOAT_SIZE),
        (r.h * sy).max(MIN_FLOAT_SIZE),
    );
    clamp_float(scaled, to)
}