monolith

public

Star0

Watch0

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

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

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

    pub fn mark_urgent(&mut self, w: WindowId) {
        if !self.visible(w)
            && let Some(tag) = self.windows.get(w).map(|win| win.tag)
        {
            self.tags[tag].urgent = true;
        }
    }

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

    /// 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),
    )
}

1	//! Window organisation without smithay. Tags with per-output views, one
2	//! tiling tree per output filtered by those views, floating windows,
3	//! scratchpads, focus, and restoring windows when an output comes back.
4
5	mod outputs;
6	mod scratchpad;
7	mod tree;
8
9	#[cfg(test)]
10	mod tests;
11
12	pub use monolith_planner::Rect;
13	pub use tree::{Axis, Dir, Tree};
14
15	use outputs::Parked;
16	use slotmap::{SlotMap, new_key_type};
17	use std::collections::HashMap;
18
19	new_key_type! {
20	pub struct WindowId;
21	pub struct TagId;
22	pub struct OutputId;
23	}
24
25	pub const HOMELESS: &str = "homeless";
26
27	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
28	pub enum ExpandScope {
29	Window,
30	Container,
31	All,
32	}
33
34	/// Space taken from an output's edges by bars and other panels.
35	#[derive(Clone, Copy, Debug, PartialEq, Default)]
36	pub struct Insets {
37	pub top: f64,
38	pub right: f64,
39	pub bottom: f64,
40	pub left: f64,
41	}
42
43	#[derive(Clone, Copy, Debug, PartialEq)]
44	pub struct Gaps {
45	pub inner: f64,
46	pub outer: f64,
47	}
48
49	impl Default for Gaps {
50	fn default() -> Self {
51	Self {
52	inner: 8.0,
53	outer: 8.0,
54	}
55	}
56	}
57
58	#[derive(Clone, Debug)]
59	pub struct Window {
60	pub output: Option<OutputId>,
61	pub tag: TagId,
62	pub floating: bool,
63	pub float_rect: Option<Rect>,
64	pub fullscreen: bool,
65	pub sticky: bool,
66	pub scratchpad: Option<usize>,
67	evicted_from: Option<String>,
68	}
69
70	#[derive(Clone, Debug)]
71	pub struct Tag {
72	pub name: String,
73	pub urgent: bool,
74	}
75
76	#[derive(Clone, Debug)]
77	pub struct Output {
78	pub name: String,
79	pub area: Rect,
80	pub reserved: Insets,
81	pub tree: Tree<WindowId>,
82	/// Viewed tags besides the homeless tag, which is always viewed.
83	pub viewed: Vec<TagId>,
84	/// Floating windows, bottom to top.
85	pub floating: Vec<WindowId>,
86	}
87
88	#[derive(Clone, Debug)]
89	pub struct Scratchpad {
90	pub name: String,
91	pub windows: Vec<WindowId>,
92	pub shown: Option<usize>,
93	pub output: Option<OutputId>,
94	}
95
96	#[derive(Clone, Debug, Default)]
97	pub struct Arrangement {
98	/// Every tiled window on the output. Hidden ones are zero-size seeds.
99	pub tiled: Vec<Placed>,
100	/// Visible floating windows and shown scratchpads, bottom to top.
101	pub floating: Vec<(WindowId, Rect)>,
102	pub fullscreen: Option<WindowId>,
103	}
104
105	#[derive(Clone, Copy, Debug)]
106	pub struct Placed {
107	pub window: WindowId,
108	pub rect: Rect,
109	pub visible: bool,
110	}
111
112	#[derive(Clone, Debug)]
113	pub struct Layout {
114	windows: SlotMap<WindowId, Window>,
115	tags: SlotMap<TagId, Tag>,
116	tag_order: Vec<TagId>,
117	homeless: TagId,
118	outputs: SlotMap<OutputId, Output>,
119	active: Option<OutputId>,
120	/// Focus history, most recent last.
121	history: Vec<WindowId>,
122	scratchpads: Vec<Scratchpad>,
123	last_scratchpad: Option<usize>,
124	parked: HashMap<String, Parked>,
125	pub gaps: Gaps,
126	}
127
128	impl Default for Layout {
129	fn default() -> Self {
130	let mut tags = SlotMap::with_key();
131	let homeless = tags.insert(Tag {
132	name: HOMELESS.into(),
133	urgent: false,
134	});
135	Self {
136	windows: SlotMap::with_key(),
137	tags,
138	tag_order: vec![homeless],
139	homeless,
140	outputs: SlotMap::with_key(),
141	active: None,
142	history: Vec::new(),
143	scratchpads: Vec::new(),
144	last_scratchpad: None,
145	parked: HashMap::new(),
146	gaps: Gaps::default(),
147	}
148	}
149	}
150
151	impl Layout {
152	pub fn homeless(&self) -> TagId {
153	self.homeless
154	}
155
156	/// Looks a tag up by name, creating it at the end of the order.
157	pub fn tag(&mut self, name: &str) -> TagId {
158	if let Some(id) = self.tag_id(name) {
159	return id;
160	}
161	let id = self.tags.insert(Tag {
162	name: name.into(),
163	urgent: false,
164	});
165	self.tag_order.push(id);
166	id
167	}
168
169	pub fn tag_id(&self, name: &str) -> Option<TagId> {
170	self.tag_order
171	.iter()
172	.copied()
173	.find(\|&t\| self.tags[t].name == name)
174	}
175
176	pub fn tags(&self) -> impl Iterator<Item = (TagId, &Tag)> {
177	self.tag_order.iter().map(\|&t\| (t, &self.tags[t]))
178	}
179
180	pub fn reorder_tag(&mut self, tag: TagId, index: usize) {
181	if let Some(i) = self.tag_order.iter().position(\|&t\| t == tag) {
182	self.tag_order.remove(i);
183	let index = index.min(self.tag_order.len());
184	self.tag_order.insert(index, tag);
185	}
186	}
187
188	pub fn window(&self, w: WindowId) -> Option<&Window> {
189	self.windows.get(w)
190	}
191
192	pub fn windows(&self) -> impl Iterator<Item = (WindowId, &Window)> {
193	self.windows.iter()
194	}
195
196	pub fn output(&self, o: OutputId) -> Option<&Output> {
197	self.outputs.get(o)
198	}
199
200	pub fn outputs(&self) -> impl Iterator<Item = (OutputId, &Output)> {
201	self.outputs.iter()
202	}
203
204	pub fn scratchpads(&self) -> &[Scratchpad] {
205	&self.scratchpads
206	}
207
208	pub fn active_output(&self) -> Option<OutputId> {
209	self.active
210	}
211
212	pub fn set_active_output(&mut self, o: OutputId) {
213	if self.outputs.contains_key(o) {
214	self.active = Some(o);
215	}
216	}
217
218	pub fn is_viewed(&self, o: OutputId, tag: TagId) -> bool {
219	tag == self.homeless
220	\|\| self
221	.outputs
222	.get(o)
223	.is_some_and(\|out\| out.viewed.contains(&tag))
224	}
225
226	/// Views `tag` alone, besides the homeless tag.
227	pub fn view(&mut self, o: OutputId, tag: TagId) {
228	let Some(out) = self.outputs.get_mut(o) else {
229	return;
230	};
231	out.viewed.clear();
232	if tag != self.homeless {
233	out.viewed.push(tag);
234	}
235	self.tags[tag].urgent = false;
236	}
237
238	pub fn toggle_view(&mut self, o: OutputId, tag: TagId) {
239	if tag == self.homeless {
240	return;
241	}
242	let Some(out) = self.outputs.get_mut(o) else {
243	return;
244	};
245	if let Some(i) = out.viewed.iter().position(\|&t\| t == tag) {
246	out.viewed.remove(i);
247	} else {
248	out.viewed.push(tag);
249	self.tags[tag].urgent = false;
250	}
251	}
252
253	/// The tag a launch from `o` belongs to. The focused window's tag, else
254	/// the first viewed tag, else homeless. Homeless is always on screen, so
255	/// focusing one of its windows does not mean the user left their tag.
256	pub fn launch_tag(&self, o: OutputId) -> TagId {
257	self.focused_on(o)
258	.map(\|w\| &self.windows[w])
259	.filter(\|w\| w.scratchpad.is_none() && !w.sticky && w.tag != self.homeless)
260	.map(\|w\| w.tag)
261	.or_else(\|\| self.outputs.get(o)?.viewed.first().copied())
262	.unwrap_or(self.homeless)
263	}
264
265	pub fn view_everywhere(&mut self, tag: TagId) {
266	for o in self.outputs.keys().collect::<Vec<_>>() {
267	self.view(o, tag);
268	}
269	}
270
271	pub fn visible(&self, w: WindowId) -> bool {
272	let Some(win) = self.windows.get(w) else {
273	return false;
274	};
275	let Some(o) = win.output else {
276	return false;
277	};
278	match win.scratchpad {
279	Some(s) => {
280	let sp = &self.scratchpads[s];
281	sp.output == Some(o) && sp.shown.map(\|i\| sp.windows[i]) == Some(w)
282	}
283	None => win.sticky \|\| self.is_viewed(o, win.tag),
284	}
285	}
286
287	/// Adds a window on `output` (default the active one) and `tag` (default
288	/// homeless). A window landing on a tag its output is not viewing marks
289	/// the tag urgent.
290	pub fn add_window(
291	&mut self,
292	output: Option<OutputId>,
293	tag: Option<TagId>,
294	floating: Option<Rect>,
295	) -> WindowId {
296	let output = output
297	.filter(\|&o\| self.outputs.contains_key(o))
298	.or(self.active);
299	let tag = tag
300	.filter(\|&t\| self.tags.contains_key(t))
301	.unwrap_or(self.homeless);
302	let w = self.windows.insert(Window {
303	output,
304	tag,
305	floating: floating.is_some(),
306	float_rect: floating,
307	fullscreen: false,
308	sticky: false,
309	scratchpad: None,
310	evicted_from: None,
311	});
312	if let Some(o) = output {
313	if !self.is_viewed(o, tag) {
314	self.tags[tag].urgent = true;
315	}
316	self.place(w);
317	}
318	w
319	}
320
321	pub fn remove_window(&mut self, w: WindowId) {
322	if !self.windows.contains_key(w) {
323	return;
324	}
325	self.unplace(w);
326	self.history.retain(\|&h\| h != w);
327	if let Some(s) = self.windows[w].scratchpad {
328	self.leave_scratchpad(s, w);
329	}
330	self.windows.remove(w);
331	}
332
333	/// Puts a window into its output's tree or floating stack. Tiled windows
334	/// go next to the focused window if both are visible, else next to the
335	/// latest window of their tag, else into a new row.
336	fn place(&mut self, w: WindowId) {
337	let win = &self.windows[w];
338	let Some(o) = win.output else { return };
339	if win.scratchpad.is_some() {
340	return;
341	}
342	if win.floating {
343	if win.float_rect.is_none() {
344	let rect = centred(self.outputs[o].area, 0.6);
345	self.windows[w].float_rect = Some(rect);
346	}
347	self.outputs[o].floating.push(w);
348	return;
349	}
350	let tag = win.tag;
351	let tree = &self.outputs[o].tree;
352	let focused = self
353	.focused()
354	.filter(\|&f\| tree.contains(f) && self.is_viewed(o, tag));
355	let anchor = focused.or_else(\|\| {
356	self.history
357	.iter()
358	.rev()
359	.copied()
360	.find(\|&h\| tree.contains(h) && self.windows[h].tag == tag)
361	});
362	let tree = &mut self.outputs[o].tree;
363	match anchor {
364	Some(a) => tree.insert_after(w, a),
365	None => tree.insert_row(w),
366	}
367	}
368
369	fn unplace(&mut self, w: WindowId) {
370	let Some(o) = self.windows[w].output else {
371	return;
372	};
373	let out = &mut self.outputs[o];
374	out.tree.remove(w);
375	out.floating.retain(\|&f\| f != w);
376	}
377
378	pub fn focus(&mut self, w: WindowId) {
379	let Some(win) = self.windows.get(w) else {
380	return;
381	};
382	self.active = win.output.or(self.active);
383	if let Some(o) = win.output {
384	let stack = &mut self.outputs[o].floating;
385	if let Some(i) = stack.iter().position(\|&f\| f == w) {
386	stack.remove(i);
387	stack.push(w);
388	}
389	}
390	self.history.retain(\|&h\| h != w);
391	self.history.push(w);
392	}
393
394	/// The most recently focused visible window.
395	pub fn focused(&self) -> Option<WindowId> {
396	self.history
397	.iter()
398	.rev()
399	.copied()
400	.find(\|&w\| self.visible(w))
401	}
402
403	/// The most recently focused visible window on `o`.
404	pub fn focused_on(&self, o: OutputId) -> Option<WindowId> {
405	self.history
406	.iter()
407	.rev()
408	.copied()
409	.find(\|&w\| self.windows[w].output == Some(o) && self.visible(w))
410	}
411
412	/// Focuses the nearest visible window in `dir`, crossing to the next
413	/// output when there is none on this one.
414	pub fn focus_dir(&mut self, dir: Dir) -> Option<WindowId> {
415	let o = self.active?;
416	let from = self.focused_on(o).and_then(\|f\| self.rect_of(f));
417	let target = from.and_then(\|from\| {
418	let arr = self.arrange(o);
419	let candidates = arr
420	.tiled
421	.iter()
422	.filter(\|p\| p.visible)
423	.map(\|p\| (p.window, p.rect))
424	.chain(arr.floating.iter().copied())
425	.filter(\|&(w, _)\| Some(w) != self.focused_on(o));
426	nearest(from, dir, candidates)
427	});
428	if let Some(w) = target {
429	self.focus(w);
430	return Some(w);
431	}
432	let next = self.output_towards(o, dir)?;
433	self.active = Some(next);
434	let w = self.focused_on(next);
435	if let Some(w) = w {
436	self.focus(w);
437	}
438	w
439	}
440
441	pub fn output_towards(&self, from: OutputId, dir: Dir) -> Option<OutputId> {
442	let here = self.outputs.get(from)?.area;
443	let others = self
444	.outputs
445	.iter()
446	.filter(\|&(id, _)\| id != from)
447	.map(\|(id, out)\| (id, out.area));
448	nearest(here, dir, others)
449	}
450
451	fn rect_of(&self, w: WindowId) -> Option<Rect> {
452	let o = self.windows.get(w)?.output?;
453	let arr = self.arrange(o);
454	arr.tiled
455	.iter()
456	.find(\|p\| p.window == w)
457	.map(\|p\| p.rect)
458	.or_else(\|\| arr.floating.iter().find(\|f\| f.0 == w).map(\|f\| f.1))
459	}
460
461	fn vis_on(&self, o: OutputId) -> impl Fn(WindowId) -> bool + '_ {
462	move \|w\| self.windows[w].output == Some(o) && self.visible(w)
463	}
464
465	fn focused_tiled(&self) -> Option<(WindowId, OutputId)> {
466	let w = self.focused()?;
467	let o = self.windows[w].output?;
468	self.outputs[o].tree.contains(w).then_some((w, o))
469	}
470
471	pub fn move_window(&mut self, dir: Dir) -> bool {
472	let Some((w, o)) = self.focused_tiled() else {
473	return false;
474	};
475	let mut tree = std::mem::take(&mut self.outputs[o].tree);
476	let moved = tree.move_window(w, dir, self.vis_on(o));
477	self.outputs[o].tree = tree;
478	moved
479	}
480
481	pub fn move_container(&mut self, dir: Dir) -> bool {
482	let Some((w, o)) = self.focused_tiled() else {
483	return false;
484	};
485	let mut tree = std::mem::take(&mut self.outputs[o].tree);
486	let moved = tree.move_container(w, dir, self.vis_on(o));
487	self.outputs[o].tree = tree;
488	moved
489	}
490
491	pub fn merge_window(&mut self, dir: Dir) -> bool {
492	let Some((w, o)) = self.focused_tiled() else {
493	return false;
494	};
495	let mut tree = std::mem::take(&mut self.outputs[o].tree);
496	let merged = tree.merge_window(w, dir, self.vis_on(o));
497	self.outputs[o].tree = tree;
498	merged
499	}
500
501	/// Whether a tiled window fills its output through expansion.
502	pub fn maximized(&self, w: WindowId) -> bool {
503	let Some(o) = self.windows.get(w).and_then(\|w\| w.output) else {
504	return false;
505	};
506	self.outputs[o].tree.maximized(w)
507	}
508
509	pub fn resize(&mut self, axis: Axis, delta: f64) -> bool {
510	let Some((w, o)) = self.focused_tiled() else {
511	return false;
512	};
513	let mut tree = std::mem::take(&mut self.outputs[o].tree);
514	let done = tree.resize(w, axis, delta, self.vis_on(o));
515	self.outputs[o].tree = tree;
516	done
517	}
518
519	pub fn expand(&mut self, scope: ExpandScope) -> bool {
520	let Some((w, o)) = self.focused_tiled() else {
521	return false;
522	};
523	let (skip, count) = match scope {
524	ExpandScope::Window => (0, 1),
525	ExpandScope::Container => (1, 1),
526	ExpandScope::All => (0, usize::MAX),
527	};
528	self.outputs[o].tree.toggle_expand(w, skip, count)
529	}
530
531	pub fn flip(&mut self, o: OutputId) {
532	if let Some(out) = self.outputs.get_mut(o) {
533	out.tree.flip();
534	}
535	}
536
537	/// Retags a window. It keeps its slot and disappears if the new tag is
538	/// not viewed.
539	pub fn set_tag(&mut self, w: WindowId, tag: TagId) {
540	if self.tags.contains_key(tag)
541	&& let Some(win) = self.windows.get_mut(w)
542	{
543	win.tag = tag;
544	}
545	}
546
547	/// Moves a window to `tag` on `o`, marking the tag urgent when the window
548	/// ends up out of sight.
549	pub fn relocate(&mut self, w: WindowId, o: Option<OutputId>, tag: TagId) {
550	if let Some(o) = o {
551	self.send_to_output(w, o);
552	}
553	self.set_tag(w, tag);
554	self.mark_urgent(w);
555	}
556
557	pub fn mark_urgent(&mut self, w: WindowId) {
558	if !self.visible(w)
559	&& let Some(tag) = self.windows.get(w).map(\|win\| win.tag)
560	{
561	self.tags[tag].urgent = true;
562	}
563	}
564
565	pub fn send_to_output(&mut self, w: WindowId, o: OutputId) {
566	let Some(win) = self.windows.get(w) else {
567	return;
568	};
569	if !self.outputs.contains_key(o) \|\| win.output == Some(o) \|\| win.scratchpad.is_some() {
570	return;
571	}
572	let from = win.output.map(\|f\| self.outputs[f].area);
573	self.unplace(w);
574	let win = &mut self.windows[w];
575	if let (Some(from), Some(rect)) = (from, win.float_rect) {
576	win.float_rect = Some(translate(rect, from, self.outputs[o].area));
577	}
578	win.output = Some(o);
579	win.evicted_from = None;
580	self.place(w);
581	}
582
583	/// Switches a window between tiled and floating. A scratchpad window
584	/// leaves its scratchpad and tiles on the tag being viewed, since its own
585	/// tag may well be hidden.
586	pub fn toggle_floating(&mut self, w: WindowId) {
587	let Some(win) = self.windows.get(w) else {
588	return;
589	};
590	if let Some(s) = win.scratchpad {
591	let o = win.output.or(self.active);
592	let tag = o.map_or(self.homeless, \|o\| self.launch_tag(o));
593	self.leave_scratchpad(s, w);
594	let win = &mut self.windows[w];
595	win.output = o;
596	win.tag = tag;
597	win.floating = false;
598	self.place(w);
599	return;
600	}
601	self.unplace(w);
602	let win = &mut self.windows[w];
603	win.floating = !win.floating;
604	self.place(w);
605	}
606
607	pub fn set_float_rect(&mut self, w: WindowId, rect: Rect) {
608	if let Some(win) = self.windows.get_mut(w) {
609	win.float_rect = Some(rect);
610	}
611	}
612
613	pub fn toggle_fullscreen(&mut self, w: WindowId) {
614	if let Some(win) = self.windows.get_mut(w) {
615	win.fullscreen = !win.fullscreen;
616	}
617	}
618
619	pub fn toggle_sticky(&mut self, w: WindowId) {
620	if let Some(win) = self.windows.get_mut(w) {
621	win.sticky = !win.sticky;
622	}
623	}
624
625	/// Target geometry for everything on `o`, in output-local logical
626	/// coordinates offset by the output's area.
627	pub fn arrange(&self, o: OutputId) -> Arrangement {
628	self.arrange_hiding(o, &[])
629	}
630
631	/// Like `arrange` with `hide` treated as hidden, which places them on the
632	/// seeds they would grow from.
633	pub fn arrange_hiding(&self, o: OutputId, hide: &[WindowId]) -> Arrangement {
634	let Some(out) = self.outputs.get(o) else {
635	return Arrangement::default();
636	};
637	let r = out.reserved;
638	let usable = Rect::new(
639	out.area.x + r.left,
640	out.area.y + r.top,
641	(out.area.w - r.left - r.right).max(0.0),
642	(out.area.h - r.top - r.bottom).max(0.0),
643	);
644	let area = inset(usable, self.gaps.outer);
645	let shown = self.vis_on(o);
646	let vis = &\|w: WindowId\| shown(w) && !hide.contains(&w);
647	let tiled = out
648	.tree
649	.arrange(area, self.gaps.inner, vis)
650	.into_iter()
651	.map(\|(window, rect)\| Placed {
652	window,
653	rect,
654	visible: vis(window),
655	})
656	.collect();
657	let mut floating: Vec<(WindowId, Rect)> = out
658	.floating
659	.iter()
660	.copied()
661	.filter(\|&w\| vis(w))
662	.filter_map(\|w\| Some((w, self.windows[w].float_rect?)))
663	.collect();
664	for sp in &self.scratchpads {
665	if let Some(i) = sp.shown
666	&& sp.output == Some(o)
667	&& let Some(r) = self.windows[sp.windows[i]].float_rect
668	{
669	floating.push((sp.windows[i], r));
670	}
671	}
672	let fullscreen = self
673	.history
674	.iter()
675	.rev()
676	.copied()
677	.find(\|&w\| self.windows[w].fullscreen && vis(w));
678	Arrangement {
679	tiled,
680	floating,
681	fullscreen,
682	}
683	}
684
685	#[cfg(test)]
686	pub(crate) fn check(&self) {
687	for (o, out) in &self.outputs {
688	out.tree.check();
689	for w in out.tree.windows() {
690	let win = &self.windows[w];
691	assert_eq!(win.output, Some(o));
692	assert!(!win.floating && win.scratchpad.is_none());
693	}
694	for &w in &out.floating {
695	assert_eq!(self.windows[w].output, Some(o));
696	assert!(self.windows[w].floating);
697	}
698	}
699	for (w, win) in &self.windows {
700	let homes = self
701	.outputs
702	.values()
703	.filter(\|out\| out.tree.contains(w) \|\| out.floating.contains(&w))
704	.count();
705	let expected = usize::from(win.output.is_some() && win.scratchpad.is_none());
706	assert_eq!(homes, expected, "window placed {homes} times");
707	}
708	}
709	}
710
711	fn nearest<K: Copy>(
712	from: Rect,
713	dir: Dir,
714	candidates: impl Iterator<Item = (K, Rect)>,
715	) -> Option<K> {
716	const TOL: f64 = 0.5;
717	let score = \|r: Rect\| -> Option<(bool, f64, f64)> {
718	let (gap, overlap, offset) = match dir {
719	Dir::Right => (
720	r.x - from.right(),
721	span_overlap(from.y, from.h, r.y, r.h),
722	r.center_y() - from.center_y(),
723	),
724	Dir::Left => (
725	from.x - r.right(),
726	span_overlap(from.y, from.h, r.y, r.h),
727	r.center_y() - from.center_y(),
728	),
729	Dir::Down => (
730	r.y - from.bottom(),
731	span_overlap(from.x, from.w, r.x, r.w),
732	r.center_x() - from.center_x(),
733	),
734	Dir::Up => (
735	from.y - r.bottom(),
736	span_overlap(from.x, from.w, r.x, r.w),
737	r.center_x() - from.center_x(),
738	),
739	};
740	(gap > -TOL).then_some((overlap <= 0.0, gap.max(0.0), offset.abs()))
741	};
742	candidates
743	.filter_map(\|(k, r)\| score(r).map(\|s\| (k, s)))
744	.min_by(\|a, b\| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal))
745	.map(\|(k, _)\| k)
746	}
747
748	fn span_overlap(a: f64, al: f64, b: f64, bl: f64) -> f64 {
749	(a + al).min(b + bl) - a.max(b)
750	}
751
752	fn inset(r: Rect, by: f64) -> Rect {
753	Rect::new(
754	r.x + by,
755	r.y + by,
756	(r.w - 2.0 * by).max(0.0),
757	(r.h - 2.0 * by).max(0.0),
758	)
759	}
760
761	fn centred(area: Rect, frac: f64) -> Rect {
762	let (w, h) = (area.w * frac, area.h * frac);
763	Rect::new(
764	area.x + (area.w - w) / 2.0,
765	area.y + (area.h - h) / 2.0,
766	w,
767	h,
768	)
769	}
770
771	/// Keeps a rect at the same relative spot when it changes output.
772	fn translate(r: Rect, from: Rect, to: Rect) -> Rect {
773	let sx = if from.w > 0.0 { to.w / from.w } else { 1.0 };
774	let sy = if from.h > 0.0 { to.h / from.h } else { 1.0 };
775	Rect::new(
776	to.x + (r.x - from.x) * sx,
777	to.y + (r.y - from.y) * sy,
778	r.w.min(to.w),
779	r.h.min(to.h),
780	)
781	}