blockworx_kernel/

nav.rs

//! The navigator's tree, flattened into the rows a panel draws.
//!
//! [`NavTree`] is what the document holds; what a panel puts on screen is a
//! flat list, because three things have to happen to a nested tree before it
//! is legible in a narrow panel and all three change which rows exist rather
//! than how they look:
//!
//! 1. **Focus re-roots.** The tree is redrawn from one node, so indentation
//!    resets and a name's width does not depend on how deep it really is.
//! 2. **The filter flattens.** Matches become a flat list carrying their
//!    ancestry as text; ancestors are never rows of their own, since three
//!    matches would otherwise become fifteen rows of context. The filter
//!    reads the whole document, crossing the focus boundary.
//! 3. **Reveal opens ancestors.** Selecting geometry opens every ancestor of
//!    the block, and gives up a focus that would hide it.
//!
//! Which rows those are is one answer, here, so two front ends browsing one
//! document browse the same tree. What is *not* here is the state the answer
//! is taken against — the expand set, the focus, the filter text — which is
//! each shell's own (shell-on-kernel D7).

use std::collections::{HashMap, HashSet};

use blockworx_doc::id::BlockId;
use blockworx_editor::path::Scope;

use crate::chrome::NavTree;

/// Whether the tree is showing a filtered subset.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Filtered {
    Yes,
    No,
}

impl Filtered {
    /// What `filter` asks for, and the trimmed filter itself where it asks
    /// for anything at all.
    #[must_use]
    pub fn of(filter: &str) -> (Self, Option<&str>) {
        match Some(filter.trim()).filter(|text| !text.is_empty()) {
            Some(text) => (Filtered::Yes, Some(text)),
            None => (Filtered::No, None),
        }
    }
}

/// One row of the flattened tree.
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct Row {
    pub id: BlockId,
    pub depth: usize,
    pub has_children: bool,
    /// Whether this row's children are shown beneath it.
    pub open: bool,
    pub label: String,
    /// Where this row lives, root-first — drawn under the label while the
    /// filter has flattened the tree. `None` in the unfiltered tree, whose
    /// indentation says it already.
    pub ancestors: Option<Vec<String>>,
    /// How many leaves this branch holds, printed while it is closed. `None`
    /// on a leaf and on an open branch, both of which show their contents
    /// instead.
    pub leaves: Option<usize>,
    /// The block's own accent index, which colours its dot. `None` where the
    /// block has taken no accent.
    pub accent: Option<u8>,
    /// Whether this row is the last of its parent's children on screen —
    /// which is where the guide down from that parent stops.
    pub last_child: bool,
}

/// The child→parent links of the whole reachable tree and, while searching,
/// the blocks whose own label matches.
///
/// Ancestors are *not* in the matched set: a match's ancestry renders as a
/// path under its label, never as rows of its own. The top block is never
/// included either — it is the invisible root the tree hangs from.
pub struct Index {
    parent: HashMap<BlockId, Scope>,
    matched: HashSet<BlockId>,
}

impl Index {
    /// Index `tree`, marking what `filter` matches.
    ///
    /// The walk starts at the document's root whatever the tree is focused
    /// on, which is what makes the filter cross the focus boundary.
    #[must_use]
    pub fn of(tree: &NavTree, filter: Option<&str>) -> Self {
        let mut parent: HashMap<BlockId, Scope> = HashMap::new();
        let mut matched: HashSet<BlockId> = HashSet::new();
        for (node, above) in tree.walk() {
            parent.insert(
                node.id,
                above.last().map_or(Scope::Root, |&id| Scope::Block(id)),
            );
            if filter.is_some_and(|text| matches_filter(&node.label, text)) {
                matched.insert(node.id);
            }
        }
        Self { parent, matched }
    }

    /// Where `id` hangs — the scope holding it, which is the tree's root for
    /// a block the root itself holds.
    #[must_use]
    pub fn parent_of(&self, id: BlockId) -> Option<Scope> {
        self.parent.get(&id).copied()
    }

    /// Every ancestor of `target` between `top` and it, outermost first.
    #[must_use]
    pub fn ancestor_ids(&self, top: Scope, target: BlockId) -> Vec<BlockId> {
        let mut up = Vec::new();
        let mut cur = target;
        while let Some(&at) = self.parent.get(&cur) {
            if at == top {
                break;
            }
            let Scope::Block(next) = at else { break };
            up.push(next);
            cur = next;
        }
        up.reverse();
        up
    }

    /// Whether `target` is inside `root`'s subtree — what tells a reveal
    /// whether the current focus would hide the row it is about to select.
    #[must_use]
    pub fn under(&self, root: BlockId, target: BlockId) -> bool {
        let mut cur = target;
        while let Some(&at) = self.parent.get(&cur) {
            let Scope::Block(next) = at else { return false };
            if next == root {
                return true;
            }
            cur = next;
        }
        false
    }

    /// Open every ancestor of `target` up to, but not including, `top`, so
    /// `target`'s row appears in the flattened tree. `target` itself is left
    /// as it was — revealing a block does not expand its own children.
    pub fn expand_ancestors(&self, top: Scope, target: BlockId, expanded: &mut HashSet<BlockId>) {
        for id in self.ancestor_ids(top, target) {
            expanded.insert(id);
        }
    }

    /// The labels between the tree's root and `id`, root first — what is
    /// printed under a match. Empty for a child of the root, which has no
    /// ancestry to explain.
    #[must_use]
    pub fn ancestry(&self, tree: &NavTree, id: BlockId) -> Vec<String> {
        self.ancestor_ids(Scope::Root, id)
            .into_iter()
            .map(|at| label_of(tree, at))
            .collect()
    }

    /// Depth-first flatten of the tree hanging from `root`.
    ///
    /// [`Filtered::Yes`] descends everywhere but emits only the matches, flat
    /// and carrying their ancestry; [`Filtered::No`] emits the tree as it
    /// stands, opened where the user opened it.
    #[must_use]
    pub fn rows(
        &self,
        tree: &NavTree,
        expanded: &HashSet<BlockId>,
        root: Scope,
        filtered: Filtered,
    ) -> Vec<Row> {
        let mut out = Vec::new();
        self.walk(
            Walk {
                tree,
                expanded,
                node: root,
                depth: 0,
                filtered,
            },
            &mut out,
        );
        mark_last_children(&mut out);
        out
    }

    fn walk(&self, at: Walk<'_>, out: &mut Vec<Row>) {
        let Walk {
            tree,
            expanded,
            node,
            depth,
            filtered,
        } = at;
        for child in tree.children_of(node) {
            let cid = child.id;
            let has_children = child.opens_a_scope();
            match filtered {
                Filtered::Yes => {
                    if self.matched.contains(&cid) {
                        out.push(Row {
                            id: cid,
                            depth: 0,
                            has_children,
                            open: false,
                            label: child.label.clone(),
                            ancestors: Some(self.ancestry(tree, cid)),
                            leaves: None,
                            accent: child.accent,
                            last_child: true,
                        });
                    }
                    self.walk(
                        Walk {
                            node: Scope::Block(cid),
                            ..at
                        },
                        out,
                    );
                }
                Filtered::No => {
                    let open = has_children && expanded.contains(&cid);
                    out.push(Row {
                        id: cid,
                        depth,
                        has_children,
                        open,
                        label: child.label.clone(),
                        ancestors: None,
                        leaves: (has_children && !open).then(|| child.leaves()),
                        accent: child.accent,
                        last_child: false,
                    });
                    if open {
                        self.walk(
                            Walk {
                                node: Scope::Block(cid),
                                depth: depth + 1,
                                ..at
                            },
                            out,
                        );
                    }
                }
            }
        }
    }
}

/// One step of the depth-first flatten: where it is, and everything constant
/// across the whole walk.
#[derive(Clone, Copy)]
struct Walk<'a> {
    tree: &'a NavTree,
    expanded: &'a HashSet<BlockId>,
    node: Scope,
    depth: usize,
    filtered: Filtered,
}

/// Which rows end their parent's run of children: the last row at a given
/// depth before the tree steps back out of it. A directory tree's guide down
/// from a parent stops at its last child rather than running on past the
/// family, and the flat row list is enough to say which row that is.
fn mark_last_children(rows: &mut [Row]) {
    for i in 0..rows.len() {
        let depth = rows[i].depth;
        rows[i].last_child = rows[i + 1..]
            .iter()
            .take_while(|later| later.depth >= depth)
            .all(|later| later.depth > depth);
    }
}

/// The scope the tree hangs from: the focused block, or the tree's own root
/// when nothing is focused or the focused block has since left the document.
///
/// [`Scope::Root`] is the tree's root here — the document's top block, whose
/// children the tree lists — since the top is never a row of its own.
#[must_use]
pub fn rooted_at(tree: &NavTree, focus: Option<BlockId>) -> Scope {
    focus
        .filter(|id| tree.node(*id).is_some())
        .map_or(Scope::Root, Scope::Block)
}

/// Case-insensitive substring match against the block's `name/type` label; an
/// empty or whitespace filter matches all.
#[must_use]
pub fn matches_filter(label: &str, filter: &str) -> bool {
    let wanted = filter.trim().to_lowercase();
    wanted.is_empty() || label.to_lowercase().contains(&wanted)
}

/// A row's label, falling back to the block's id when the block has left the
/// tree so a breadcrumb never shows a blank segment.
#[must_use]
pub fn label_of(tree: &NavTree, id: BlockId) -> String {
    tree.node(id)
        .map_or_else(|| id.to_string(), |node| node.label.clone())
}

/// `segments` joined into a path that fits `room`, dropped from the LEFT: the
/// immediate parent is what tells two matches apart, so it is the end that
/// survives. `measure` is the caller's own text measurement, so what is
/// dropped depends on the font actually painting it.
#[must_use]
pub fn shortened(segments: &[String], room: f32, measure: impl Fn(&str) -> f32) -> String {
    if segments.is_empty() {
        return String::new();
    }
    for start in 0..segments.len() {
        let text = if start == 0 {
            segments.join("/")
        } else {
            format!("\u{2026}/{}", segments[start..].join("/"))
        };
        if measure(&text) <= room || start + 1 == segments.len() {
            return text;
        }
    }
    String::new()
}

/// Every block the tree hangs a disclosure triangle on, read off the rows
/// themselves with every branch expanded — the navigator's own answer, for
/// the test that holds it to the canvas's double borders and the PDF's pages.
/// The tree root is never a row of its own, so it is never here.
#[cfg(any(test, feature = "test-support"))]
#[must_use]
pub fn branch_rows(tree: &NavTree) -> Vec<BlockId> {
    let expanded: HashSet<BlockId> = tree.walk().map(|(node, _)| node.id).collect();
    Index::of(tree, None)
        .rows(tree, &expanded, Scope::Root, Filtered::No)
        .into_iter()
        .filter(|row| row.has_children)
        .map(|row| row.id)
        .collect()
}

#[cfg(test)]
mod tests {
    use blockworx_doc::fixtures::block_id;
    use blockworx_editor::path::{BlockPath, tree_root};
    use blockworx_editor::widget::test_fixtures::{self as fx, Scene};
    use blockworx_geom::{Rect, pos2};

    use super::*;

    /// The navigator's tree over `scene`, the way the session builds it.
    fn tree_of(scene: &mut Scene) -> NavTree {
        NavTree::of(&scene.indexed(), BlockPath::empty(), Vec::new())
    }

    fn square(n: u32, name: &str) -> Vec<blockworx_doc::opcode::OpCodes> {
        vec![
            fx::block_in(
                n,
                Scope::Root,
                Rect::from_min_max(pos2(0.0, 0.0), pos2(60.0, 60.0)),
            ),
            fx::titled(n, name),
        ]
    }

    fn nested(n: u32, parent: u32, name: &str) -> Vec<blockworx_doc::opcode::OpCodes> {
        vec![
            fx::block_in(
                n,
                Scope::Block(block_id(parent)),
                Rect::from_min_max(pos2(0.0, 0.0), pos2(60.0, 60.0)),
            ),
            fx::titled(n, name),
        ]
    }

    /// Platform > Services > Auth, with Marketing off to one side: three
    /// levels and a sibling subtree to prove a re-rooting left behind.
    fn deep() -> Vec<blockworx_doc::opcode::OpCodes> {
        square(1, "Platform")
            .into_iter()
            .chain(nested(2, 1, "Services"))
            .chain(nested(3, 2, "Auth"))
            .chain(square(4, "Marketing"))
            .collect()
    }

    /// A walk over `tree` hanging from `root`, matching `filter` — the shape
    /// the flatten tests read.
    fn rows_of(
        tree: &NavTree,
        root: Scope,
        filter: Option<&str>,
        expanded: &HashSet<BlockId>,
    ) -> Vec<Row> {
        let (filtered, _) = Filtered::of(filter.unwrap_or_default());
        Index::of(tree, filter).rows(tree, expanded, root, filtered)
    }

    fn labels(rows: &[Row]) -> Vec<(&str, usize, bool)> {
        rows.iter()
            .map(|row| (row.label.as_str(), row.depth, row.last_child))
            .collect()
    }

    #[test]
    fn matches_filter_is_case_insensitive_substring_and_empty_matches_all() {
        assert!(matches_filter("Adder", ""));
        assert!(matches_filter("Adder", "   "));
        assert!(matches_filter("Adder", "add"));
        assert!(matches_filter("Adder", "DER"));
        assert!(!matches_filter("Adder", "mux"));
    }

    /// The filter reads the whole label, so a block's type is searchable too.
    #[test]
    fn the_filter_reads_the_type_as_well_as_the_name() {
        let mut scene = Scene::new(
            square(1, "Adder")
                .into_iter()
                .chain([fx::typed(1, "ALU")])
                .collect(),
        );
        let label = crate::chrome::block_label(&scene.indexed(), block_id(1));
        assert_eq!(label, "Adder/ALU");
        assert!(matches_filter(&label, "alu"));
    }

    /// A search flattens the tree to the matches themselves. The ancestors
    /// are NOT rows — they ride under each match as its path — and an
    /// unrelated subtree contributes nothing at all.
    #[test]
    fn a_search_flattens_to_the_matches_with_their_path_beneath() {
        let target = block_id(2);
        let mut scene = Scene::new(
            square(1, "Platform")
                .into_iter()
                .chain(nested(2, 1, "Authentication"))
                .chain(square(3, "Marketing"))
                .collect(),
        );
        let tree = tree_of(&mut scene);

        let rows = rows_of(&tree, Scope::Root, Some("auth"), &HashSet::new());
        assert_eq!(
            rows.iter().map(|row| row.id).collect::<Vec<_>>(),
            vec![target],
            "only the matching label matches, and the ancestor is not a row",
        );
        assert_eq!(rows[0].depth, 0, "a flattened match is not indented");
        assert_eq!(
            rows[0].ancestors.as_deref(),
            Some(["Platform".to_owned()].as_slice()),
            "the match does not carry the path it lives at",
        );
        assert_eq!(
            Index::of(&tree, None).ancestry(&tree, target),
            vec!["Platform"],
        );
    }

    /// A path too long for the panel is dropped from the left, so the
    /// immediate parent — the segment that tells two matches apart —
    /// survives.
    #[test]
    fn an_ancestor_path_is_shortened_from_the_left() {
        let segments: Vec<String> = ["Platform", "Services", "Auth"]
            .iter()
            .map(|at| (*at).to_owned())
            .collect();
        // One unit per character, so the assertions are about which segments
        // survive rather than about a font.
        let measure = |text: &str| text.chars().count() as f32;

        assert_eq!(
            shortened(&segments, 100.0, measure),
            "Platform/Services/Auth"
        );
        assert_eq!(
            shortened(&segments, 20.0, measure),
            "\u{2026}/Services/Auth"
        );
        assert_eq!(
            shortened(&segments, 6.0, measure),
            "\u{2026}/Auth",
            "the immediate parent is the last thing to go",
        );
        assert_eq!(shortened(&[], 100.0, measure), "");
    }

    /// A closed branch says how many leaves it holds, so its size is legible
    /// without opening it; an open one shows them instead.
    #[test]
    fn a_closed_branch_counts_its_leaves() {
        let mut scene = Scene::new(
            square(1, "Platform")
                .into_iter()
                .chain(nested(2, 1, "Services"))
                .chain(nested(3, 2, "Auth"))
                .chain(nested(4, 2, "Billing"))
                .collect(),
        );
        let tree = tree_of(&mut scene);
        let closed = rows_of(&tree, Scope::Root, None, &HashSet::new());
        assert_eq!(closed.len(), 1, "precondition: one closed branch");
        assert_eq!(
            closed[0].leaves,
            Some(2),
            "Platform holds two leaves, however deep they sit",
        );

        let expanded: HashSet<BlockId> = std::iter::once(block_id(1)).collect();
        let open = rows_of(&tree, Scope::Root, None, &expanded);
        assert_eq!(open[0].leaves, None, "an open branch shows its contents");
        assert_eq!(open[1].leaves, Some(2), "and its closed child counts");
    }

    /// Focusing a block re-roots the tree on it, so its children become the
    /// first rows at depth zero and everything outside is gone.
    #[test]
    fn a_focus_re_roots_the_tree_and_resets_the_indentation() {
        let mut scene = Scene::new(deep());
        let tree = tree_of(&mut scene);
        assert_eq!(
            rooted_at(&tree, None),
            Scope::Root,
            "no focus hangs the tree from the document",
        );
        let root = rooted_at(&tree, Some(block_id(2)));
        assert_eq!(root, Scope::Block(block_id(2)));

        let rows = rows_of(&tree, root, None, &HashSet::new());
        assert_eq!(
            rows.iter().map(|row| row.id).collect::<Vec<_>>(),
            vec![block_id(3)]
        );
        assert_eq!(rows[0].depth, 0, "the focused root's children start over");

        // A block that has since left the document cannot hold the tree.
        assert_eq!(rooted_at(&tree, Some(block_id(9))), Scope::Root);
    }

    /// What makes the guides read as a tree rather than as a grid is where
    /// they *stop* — a parent's trunk ends at its last child, so the flat row
    /// list has to know which row that is.
    #[test]
    fn a_parents_guide_stops_at_its_last_child() {
        let mut scene = Scene::new(deep());
        let tree = tree_of(&mut scene);
        let expanded: HashSet<BlockId> = [block_id(1), block_id(2)].into_iter().collect();
        let rows = rows_of(&tree, Scope::Root, None, &expanded);
        let named = |name: &str| {
            rows.iter()
                .find(|row| row.label.starts_with(name))
                .unwrap_or_else(|| panic!("no {name} row: {:?}", labels(&rows)))
        };
        assert_eq!(
            rows.len(),
            4,
            "precondition: Platform > Services > Auth, and Marketing beside them: {:?}",
            labels(&rows),
        );
        assert!(
            !named("Platform").last_child,
            "Marketing follows Platform at the root, so Platform is not the last child",
        );
        assert!(
            named("Marketing").last_child,
            "nothing follows Marketing at the root",
        );
        assert!(
            named("Services").last_child && named("Auth").last_child,
            "an only child is its parent's last: {:?}",
            labels(&rows),
        );
        assert!(
            named("Auth").depth > named("Services").depth,
            "precondition: the deep row really is deeper",
        );
    }

    /// What tells a reveal whether the current focus would hide the row the
    /// canvas just asked for.
    #[test]
    fn a_block_is_under_its_ancestors_and_nothing_else() {
        let mut scene = Scene::new(deep());
        let tree = tree_of(&mut scene);
        let index = Index::of(&tree, None);
        assert!(
            index.under(block_id(1), block_id(3)),
            "Auth is inside Platform"
        );
        assert!(index.under(block_id(2), block_id(3)));
        assert!(
            !index.under(block_id(4), block_id(3)),
            "Auth is not inside Marketing",
        );
        assert!(
            !index.under(block_id(3), block_id(3)),
            "nothing is inside itself",
        );
    }

    /// Revealing a deep block opens its whole ancestor chain (but not the
    /// block itself), so it becomes a visible row.
    #[test]
    fn expand_ancestors_opens_the_chain_to_a_deep_block() {
        let (a, b, c) = (block_id(1), block_id(2), block_id(3));
        let mut scene = Scene::new(
            square(1, "A")
                .into_iter()
                .chain(nested(2, 1, "B"))
                .chain(nested(3, 2, "C"))
                .collect(),
        );
        let tree = tree_of(&mut scene);

        let mut expanded = HashSet::new();
        Index::of(&tree, None).expand_ancestors(Scope::Root, c, &mut expanded);
        assert!(expanded.contains(&a));
        assert!(expanded.contains(&b));
        assert!(!expanded.contains(&c), "the target is not force-expanded");

        let rows = rows_of(&tree, Scope::Root, None, &expanded);
        assert!(
            rows.iter().any(|row| row.id == c),
            "the deep block is now a row",
        );
    }

    /// Collapsed by default: only the root scope's own children are rows
    /// until a branch is expanded.
    #[test]
    fn flatten_is_collapsed_until_expanded() {
        let (parent, child) = (block_id(1), block_id(2));
        let mut scene = Scene::new(
            square(1, "Platform")
                .into_iter()
                .chain(nested(2, 1, "Services"))
                .collect(),
        );
        let tree = tree_of(&mut scene);

        let collapsed = rows_of(&tree, Scope::Root, None, &HashSet::new());
        assert_eq!(
            collapsed.iter().map(|row| row.id).collect::<Vec<_>>(),
            vec![parent]
        );
        assert!(collapsed[0].has_children);
        assert!(!collapsed[0].open);

        let expanded: HashSet<BlockId> = std::iter::once(parent).collect();
        let opened = rows_of(&tree, Scope::Root, None, &expanded);
        assert_eq!(
            opened.iter().map(|row| row.id).collect::<Vec<_>>(),
            vec![parent, child]
        );
    }

    /// With no designated top the tree hangs from the document root, so
    /// root-level blocks are the first rows. Designating one as the top makes
    /// it the invisible root instead — its children become the first rows and
    /// it shows no row of its own.
    #[test]
    fn the_tree_hangs_from_the_designated_top_or_the_document_root() {
        let (outer, inner) = (block_id(1), block_id(2));
        let ops: Vec<_> = square(1, "Platform")
            .into_iter()
            .chain(nested(2, 1, "Services"))
            .collect();

        let mut rooted = Scene::new(ops.clone());
        let indexed = rooted.indexed();
        assert_eq!(tree_root(&indexed), Scope::Root, "no top designated yet");
        let tree = NavTree::of(&indexed, BlockPath::empty(), Vec::new());
        let rows = rows_of(&tree, Scope::Root, None, &HashSet::new());
        assert_eq!(
            rows.iter().map(|row| row.id).collect::<Vec<_>>(),
            vec![outer]
        );

        let mut topped = Scene::new(ops.into_iter().chain([fx::top(1)]).collect());
        let indexed = topped.indexed();
        assert_eq!(tree_root(&indexed), Scope::Block(outer));
        let tree = NavTree::of(&indexed, BlockPath::empty(), Vec::new());
        let rows = rows_of(&tree, Scope::Root, None, &HashSet::new());
        assert_eq!(
            rows.iter().map(|row| row.id).collect::<Vec<_>>(),
            vec![inner],
            "the top block is the invisible root, not a row",
        );
    }
}