codecraft 0.1.2

//! Positions for the graph: a wall of nested boxes on a unit grid, read like a file explorer.
//! A container lays its children out on its front face — folders first, then files, in rows —
//! and every level sits one unit deeper than the one around it.
use std::collections::HashMap;
use std::ops::Sub;

use glam::{IVec3, Vec3};

use super::graph::{Graph, Id, Kind};

/// Room left round a container's contents, and the band at the top its name sits in.
const MARGIN: i32 = 1;
const HEADER: i32 = 2;
/// Clear space between two containers side by side.
const GAP: i32 = 1;
/// Width over height a block of children aims for: a screen, roughly.
const ASPECT: f32 = 1.6;

/// The side of an empty file's tile from its lines alone: ten times the lines, twice the side, never under one.
pub fn lines_side(lines: usize) -> i32 {
    (lines.max(1) as f32 / 100.0)
        .powf(std::f32::consts::LOG10_2)
        .min(1e6)
        .sub(1e-4)
        .ceil()
        .max(1.0) as i32
}

#[derive(Clone, Debug, Default)]
pub struct Layout {
    /// Box centres: where the wall put them, plus whatever forces have done since.
    pub positions: HashMap<Id, Vec3>,
    rest: HashMap<Id, Vec3>,
    /// Integer size of each node's box: across, up, deep. A symbol is one cell.
    size: HashMap<Id, IVec3>,
    /// A child's min corner, relative to its parent's.
    offset: HashMap<Id, IVec3>,
    /// Levels of containers under a node: 0 for a symbol, 1 for a module of symbols.
    height: HashMap<Id, u32>,
    /// The band at the top of a container its name sits in.
    header: HashMap<Id, i32>,
}

impl Layout {
    pub fn of(graph: &Graph) -> Self {
        let mut layout = Self::default();
        let root = graph.root();
        let size = layout.measure(graph, root);
        // Centred across and up, its front face on z = 0, the rest going away from the viewer.
        layout.place(graph, root, IVec3::new(-size.x / 2, -size.y / 2, -size.z));
        layout.rest = layout.positions.clone();
        layout
    }

    pub fn position(&self, id: Id) -> Vec3 {
        self.positions.get(&id).copied().unwrap_or(Vec3::ZERO)
    }

    /// Where the wall put a node, before any forces.
    pub fn rest(&self, id: Id) -> Vec3 {
        self.rest.get(&id).copied().unwrap_or(Vec3::ZERO)
    }

    /// The size of a node's box in world units: across, up, deep.
    pub fn size_of(&self, id: Id) -> Vec3 {
        self.size.get(&id).copied().unwrap_or(IVec3::ONE).as_vec3()
    }

    /// How wide a node's box is.
    pub fn side_of(&self, id: Id) -> f32 {
        self.size_of(id).x
    }

    /// How far a node's box reaches from its centre, corner included.
    pub fn radius_of(&self, id: Id) -> f32 {
        self.size_of(id).length() * 0.5
    }

    /// The middle of a node's front face.
    pub fn front_of(&self, id: Id) -> Vec3 {
        self.position(id) + Vec3::Z * (self.size_of(id).z * 0.5)
    }

    /// Levels of containers under a node.
    pub fn height_of(&self, id: Id) -> u32 {
        self.height.get(&id).copied().unwrap_or(0)
    }

    /// How tall the band a container's name sits in is, in world units.
    pub fn header_of(&self, id: Id) -> f32 {
        self.header.get(&id).copied().unwrap_or(HEADER) as f32
    }

    /// The middle of everything and how far the farthest node is from it.
    pub fn bounds(&self) -> (Vec3, f32) {
        if self.positions.is_empty() {
            return (Vec3::ZERO, 1.0);
        }
        let sum: Vec3 = self.positions.values().copied().sum();
        let centre = sum / self.positions.len() as f32;
        let extent = self
            .positions
            .values()
            .map(|p| p.distance(centre))
            .fold(0.0, f32::max);
        (centre, extent.max(1.0))
    }

    /// Moves containers by `displacement` from rest, carrying everything under them along.
    pub fn displace(&mut self, graph: &Graph, displacement: &HashMap<Id, Vec3>) {
        let mut stack = vec![(graph.root(), Vec3::ZERO)];
        while let Some((id, inherited)) = stack.pop() {
            let shift = inherited + displacement.get(&id).copied().unwrap_or(Vec3::ZERO);
            if let Some(&rest) = self.rest.get(&id) {
                self.positions.insert(id, rest + shift);
            }
            for child in graph.children(id) {
                stack.push((child, shift));
            }
        }
    }

    /// Sizes `id`'s box from its children's, remembering where each child goes on its face.
    fn measure(&mut self, graph: &Graph, id: Id) -> IVec3 {
        let node = graph.node(id);
        let children = graph.children(id);
        // A file is a tile with no margin round its symbols; a folder keeps a margin.
        let margin = match node.kind {
            Kind::File => 0,
            _ => MARGIN,
        };
        let size = if children.is_empty() {
            self.height.insert(id, 0);
            match node.kind {
                Kind::File => IVec3::new(lines_side(node.lines), lines_side(node.lines), 1),
                kind if kind.is_container() => IVec3::new(2, 2, 1),
                _ => IVec3::ONE,
            }
        } else {
            let (folders, files): (Vec<Id>, Vec<Id>) = children
                .iter()
                .partition(|&&child| graph.node(child).kind.is_container());
            let mut sized: Vec<(Id, IVec3)> = folders
                .iter()
                .map(|&child| (child, self.measure(graph, child)))
                .collect();
            // Biggest first so the rows pack, and the eye lands on what matters; names break ties.
            sized.sort_by(|a, b| {
                (b.1.x * b.1.y)
                    .cmp(&(a.1.x * a.1.y))
                    .then_with(|| graph.node(a.0).name.cmp(&graph.node(b.0).name))
            });
            for &file in &files {
                self.measure(graph, file);
            }
            let height = 1 + children
                .iter()
                .map(|child| self.height[child])
                .max()
                .unwrap_or(0);
            self.height.insert(id, height);

            let (content, placed) = shelve(&sized, files.len() as i32);
            // The name band grows with the box, as a window's title bar does; a file gets a thin one.
            let header = match node.kind {
                Kind::File => 1,
                _ => (content.x / 25).max(HEADER),
            };
            self.header.insert(id, header);
            let deepest = children
                .iter()
                .map(|child| self.size[child].z)
                .max()
                .unwrap_or(0);
            let size = IVec3::new(
                content.x + 2 * margin,
                content.y + header + margin,
                deepest + 1,
            );
            for (child, at) in placed {
                let child_size = self.size[&child];
                self.offset.insert(
                    child,
                    IVec3::new(
                        margin + at.x,
                        size.y - header - at.y - child_size.y,
                        size.z - 1 - child_size.z,
                    ),
                );
            }
            // Files fill rows under the folders, tile against tile.
            let files_top = if sized.is_empty() {
                0
            } else {
                content.y - files.len().div_ceil(content.x.max(1) as usize) as i32
            };
            for (i, &file) in files.iter().enumerate() {
                let columns = content.x.max(1) as usize;
                let (row, column) = (i / columns, i % columns);
                self.offset.insert(
                    file,
                    IVec3::new(
                        margin + column as i32,
                        size.y - header - files_top - row as i32 - 1,
                        size.z - 2,
                    ),
                );
            }
            size
        };
        self.size.insert(id, size);
        size
    }

    fn place(&mut self, graph: &Graph, id: Id, corner: IVec3) {
        let size = self.size[&id];
        self.positions
            .insert(id, corner.as_vec3() + size.as_vec3() * 0.5);
        for child in graph.children(id) {
            self.place(graph, child, corner + self.offset[&child]);
        }
    }
}

/// Rows of folders, wrapped to a width that keeps the block screen-shaped, with `files` unit
/// tiles to follow underneath; returns the content size and where each folder's top-left goes,
/// measured across and down from the content's top-left.
fn shelve(folders: &[(Id, IVec3)], files: i32) -> (IVec3, Vec<(Id, IVec3)>) {
    let folder_area: i32 = folders.iter().map(|(_, s)| (s.x + GAP) * (s.y + GAP)).sum();
    let widest = folders.iter().map(|(_, s)| s.x).max().unwrap_or(0);
    let area = folder_area + files;
    let width = ((area as f32 * ASPECT).sqrt().ceil() as i32)
        .max(widest)
        .max(1);

    let mut placed = Vec::with_capacity(folders.len());
    let (mut x, mut y, mut row_height, mut used) = (0, 0, 0, 0);
    for &(id, size) in folders {
        if x > 0 && x + size.x > width {
            x = 0;
            y += row_height + GAP;
            row_height = 0;
        }
        placed.push((id, IVec3::new(x, y, 0)));
        x += size.x + GAP;
        used = used.max(x - GAP);
        row_height = row_height.max(size.y);
    }
    let mut content_height = if folders.is_empty() {
        0
    } else {
        y + row_height
    };
    let content_width = used.max(if files > 0 { width } else { 0 }).max(1);
    if files > 0 {
        if !folders.is_empty() {
            content_height += GAP;
        }
        content_height += (files as usize).div_ceil(content_width as usize) as i32;
    }
    (IVec3::new(content_width, content_height, 0), placed)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::code::graph::{Kind, Node, Relation};

    fn sample() -> Graph {
        let mut graph = Graph::new("ws");
        let engine = graph.add(graph.root(), Node::new(Kind::Crate, "engine"));
        let game = graph.add(graph.root(), Node::new(Kind::Crate, "game"));
        graph.relate(game, engine, Relation::DependsOn);
        graph.add(engine, Node::new(Kind::Fn, "init"));
        for (name, count) in [("render", 40), ("audio", 9), ("input", 3)] {
            let module = graph.add(engine, Node::new(Kind::Module, name));
            for i in 0..count {
                graph.add(module, Node::new(Kind::Struct, format!("S{i}")));
            }
        }
        let nested = graph.add(game, Node::new(Kind::Module, "world"));
        let deep = graph.add(nested, Node::new(Kind::Module, "physics"));
        graph.add(deep, Node::new(Kind::Fn, "step"));
        graph
    }

    fn corners(layout: &Layout, id: Id) -> (Vec3, Vec3) {
        let lo = layout.position(id) - layout.size_of(id) * 0.5;
        (lo, lo + layout.size_of(id))
    }

    fn inside(layout: &Layout, child: Id, parent: Id) -> bool {
        let (lo, hi) = corners(layout, child);
        let (plo, phi) = corners(layout, parent);
        lo.cmpge(plo - 1e-4).all() && hi.cmple(phi + 1e-4).all()
    }

    fn overlap(layout: &Layout, a: Id, b: Id) -> bool {
        let (alo, ahi) = corners(layout, a);
        let (blo, bhi) = corners(layout, b);
        alo.cmplt(bhi - 1e-4).all() && blo.cmplt(ahi - 1e-4).all()
    }

    #[test]
    fn every_box_sits_on_the_unit_grid_with_the_wall_facing_forward() {
        let graph = sample();
        let layout = Layout::of(&graph);
        for id in graph.ids() {
            let (corner, _) = corners(&layout, id);
            assert!(
                (corner - corner.round()).abs().max_element() < 1e-4,
                "{corner}"
            );
            assert!(layout.size_of(id).min_element() >= 1.0);
        }
        let (_, hi) = corners(&layout, graph.root());
        assert_eq!(hi.z, 0.0, "the workspace's front face is at z = 0");
    }

    #[test]
    fn children_fit_in_their_parent_and_keep_apart() {
        let graph = sample();
        let layout = Layout::of(&graph);
        for parent in graph.ids() {
            let children = graph.children(parent);
            for (i, &a) in children.iter().enumerate() {
                assert!(
                    inside(&layout, a, parent),
                    "{} in {}",
                    graph.node(a).path,
                    graph.node(parent).path
                );
                for &b in &children[i + 1..] {
                    assert!(
                        !overlap(&layout, a, b),
                        "{} and {}",
                        graph.node(a).path,
                        graph.node(b).path
                    );
                }
            }
        }
    }

    #[test]
    fn each_level_sits_one_unit_deeper_with_a_margin_and_header_round_it() {
        let graph = sample();
        let layout = Layout::of(&graph);
        let engine = graph.find("engine").unwrap();
        let render = graph.find("engine::render").unwrap();
        let symbol = graph.children(render)[0];
        assert_eq!(layout.size_of(symbol), Vec3::ONE);
        assert_eq!(
            layout.size_of(render).z,
            2.0,
            "a file is a unit deeper than its symbols"
        );
        assert_eq!(layout.size_of(engine).z, 3.0);
        assert_eq!(
            layout.size_of(graph.root()).z,
            5.0,
            "game::world::physics goes deepest"
        );

        let (elo, ehi) = corners(&layout, engine);
        let (rlo, rhi) = corners(&layout, render);
        assert_eq!(rhi.z, ehi.z - 1.0, "recessed one unit into its crate");
        assert!(rlo.x >= elo.x + 1.0, "a margin on the left");
        assert!(rhi.y <= ehi.y - 2.0, "a header band above");
    }

    #[test]
    fn folders_come_first_in_rows_and_files_fill_tiles_under_them() {
        let graph = sample();
        let layout = Layout::of(&graph);
        let engine = graph.find("engine").unwrap();
        let init = graph.find("engine::init").unwrap();
        for module in ["render", "audio", "input"] {
            let module = graph.find(&format!("engine::{module}")).unwrap();
            assert!(
                layout.position(module).y > layout.position(init).y,
                "{} above the file",
                graph.node(module).name
            );
            let size = layout.size_of(module);
            assert!(
                size.x >= size.y,
                "a block of tiles is wider than tall: {size}"
            );
        }
        let render = graph.find("engine::render").unwrap();
        let symbols = graph.children(render);
        let (a, b) = (corners(&layout, symbols[0]), corners(&layout, symbols[1]));
        assert_eq!(b.0.x, a.1.x, "tiles touch");
        assert_eq!(a.0.y, b.0.y, "along a row");
        assert!(
            layout.size_of(engine).x < 40.0,
            "forty tiles wrap into rows"
        );
    }

    #[test]
    fn a_big_empty_file_gets_a_bigger_tile() {
        assert_eq!(lines_side(50), 1);
        assert_eq!(lines_side(1000), 2);
        assert_eq!(lines_side(10_000), 4);
        let mut graph = Graph::new("ws");
        let krate = graph.add(graph.root(), Node::new(Kind::Crate, "k"));
        let big = graph.add(krate, Node::new(Kind::File, "big.rs"));
        graph.node_mut(big).lines = 10_000;
        let layout = Layout::of(&graph);
        assert_eq!(layout.size_of(big), Vec3::new(4.0, 4.0, 1.0));
    }

    #[test]
    fn bigger_folders_come_first_in_reading_order() {
        let graph = sample();
        let layout = Layout::of(&graph);
        // Rows from the top, then left to right, by a box's top-left corner.
        let reading = |path: &str| {
            let (lo, hi) = corners(&layout, graph.find(path).unwrap());
            ((-hi.y * 100.0) as i64, (lo.x * 100.0) as i64)
        };
        assert!(reading("engine::render") < reading("engine::audio"));
        assert!(reading("engine::audio") < reading("engine::input"));
        assert!(reading("engine") < reading("game"));
    }

    #[test]
    fn the_layout_is_deterministic_and_centred() {
        let graph = sample();
        let one = Layout::of(&graph);
        let two = Layout::of(&graph);
        for id in graph.ids() {
            assert_eq!(one.position(id), two.position(id));
        }
        let (centre, extent) = one.bounds();
        assert!(extent > 1.0);
        assert!(centre.length() < one.radius_of(graph.root()));
    }
}