Skip to main content

rustango_cms/
tree_build.rs

1//! Turn a flat, parent-linked row set into a nested tree.
2//!
3//! Four places in this crate had grown their own version of this —
4//! `auto_menu` (page-derived menus), `navigation` (curated menus), the
5//! admin page list, and `menu-builder.js` in the browser. The shape is
6//! always the same: bucket rows by `parent_id`, then walk down from a
7//! root, bounded by a depth.
8//!
9//! Both functions here are **pure and query-free**. That is the whole
10//! point: the caller does exactly one bounded fetch, and the nesting
11//! costs nothing more. Building a tree by asking the database for each
12//! node's children is the N+1 that this module exists to prevent —
13//! and on `cms_page` it would be an unindexed lookup per node, since
14//! only `path`, `status`, `url_path` and `page_type_id` are indexed.
15
16use std::collections::HashMap;
17
18/// Bucket rows by their parent id.
19///
20/// Order within each bucket is the order rows arrive in, so a caller
21/// that fetched with `ORDER BY path` (tree pre-order) or
22/// `ORDER BY sort_order, id` gets a stable, correctly-ordered tree for
23/// free.
24pub fn index_by_parent<T, F>(rows: &[T], parent_of: F) -> HashMap<Option<i64>, Vec<&T>>
25where
26    F: Fn(&T) -> Option<i64>,
27{
28    let mut by_parent: HashMap<Option<i64>, Vec<&T>> = HashMap::new();
29    for r in rows {
30        by_parent.entry(parent_of(r)).or_default().push(r);
31    }
32    by_parent
33}
34
35/// Materialize the nodes under `parent`, at most `depth` levels deep.
36///
37/// `depth = 1` yields immediate children with empty child lists; a
38/// depth of `0` or less yields nothing. `make` receives each row with
39/// its already-built children, so the caller decides the node shape
40/// without this module knowing anything about it.
41pub fn build<'a, T, N, I, M>(
42    by_parent: &HashMap<Option<i64>, Vec<&'a T>>,
43    parent: Option<i64>,
44    depth: i64,
45    id_of: &I,
46    make: &M,
47) -> Vec<N>
48where
49    I: Fn(&T) -> i64,
50    M: Fn(&'a T, Vec<N>) -> N,
51{
52    if depth <= 0 {
53        return Vec::new();
54    }
55    let Some(rows) = by_parent.get(&parent) else {
56        return Vec::new();
57    };
58    rows.iter()
59        .map(|r| {
60            let children = if depth > 1 {
61                build(by_parent, Some(id_of(r)), depth - 1, id_of, make)
62            } else {
63                Vec::new()
64            };
65            make(r, children)
66        })
67        .collect()
68}
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[derive(Debug)]
75    struct Row {
76        id: i64,
77        parent: Option<i64>,
78        label: &'static str,
79    }
80
81    #[derive(Debug, PartialEq)]
82    struct Node {
83        label: &'static str,
84        children: Vec<Node>,
85    }
86
87    fn rows() -> Vec<Row> {
88        // 1 ─ 2 ─ 4
89        //   └ 3
90        // 5 (second root)
91        vec![
92            Row { id: 1, parent: None, label: "root-a" },
93            Row { id: 2, parent: Some(1), label: "child-a1" },
94            Row { id: 3, parent: Some(1), label: "child-a2" },
95            Row { id: 4, parent: Some(2), label: "grandchild" },
96            Row { id: 5, parent: None, label: "root-b" },
97        ]
98    }
99
100    fn tree(depth: i64) -> Vec<Node> {
101        let rows = rows();
102        let idx = index_by_parent(&rows, |r| r.parent);
103        build(
104            &idx,
105            None,
106            depth,
107            &|r: &Row| r.id,
108            &|r: &Row, children| Node { label: r.label, children },
109        )
110    }
111
112    #[test]
113    fn nests_children_under_their_parent() {
114        let t = tree(10);
115        assert_eq!(t.len(), 2, "two roots");
116        assert_eq!(t[0].label, "root-a");
117        assert_eq!(t[0].children.len(), 2);
118        assert_eq!(t[0].children[0].children[0].label, "grandchild");
119        assert!(t[1].children.is_empty(), "root-b is childless");
120    }
121
122    #[test]
123    fn depth_bounds_the_walk() {
124        // The bound is what keeps a whole-site tree from being an
125        // unbounded response.
126        let t = tree(1);
127        assert_eq!(t.len(), 2);
128        assert!(t[0].children.is_empty(), "depth 1 = roots only");
129
130        let t = tree(2);
131        assert_eq!(t[0].children.len(), 2);
132        assert!(
133            t[0].children[0].children.is_empty(),
134            "depth 2 stops before grandchildren"
135        );
136    }
137
138    #[test]
139    fn a_zero_or_negative_depth_yields_nothing() {
140        assert!(tree(0).is_empty());
141        assert!(tree(-1).is_empty());
142    }
143
144    #[test]
145    fn bucket_order_follows_input_order() {
146        // Callers rely on this: they sort in SQL (`ORDER BY path`) and
147        // expect the tree to come out in that order.
148        let rows = rows();
149        let idx = index_by_parent(&rows, |r| r.parent);
150        let kids: Vec<&str> = idx[&Some(1)].iter().map(|r| r.label).collect();
151        assert_eq!(kids, vec!["child-a1", "child-a2"]);
152    }
153
154    #[test]
155    fn an_orphan_row_is_simply_absent() {
156        // A row whose parent isn't in the set (filtered out by status or
157        // a view restriction) must not surface at the root — that would
158        // leak a page out of a subtree its parent gates.
159        let rows = vec![
160            Row { id: 1, parent: None, label: "root" },
161            Row { id: 9, parent: Some(404), label: "orphan" },
162        ];
163        let idx = index_by_parent(&rows, |r| r.parent);
164        let t: Vec<Node> = build(
165            &idx,
166            None,
167            10,
168            &|r: &Row| r.id,
169            &|r: &Row, children| Node { label: r.label, children },
170        );
171        assert_eq!(t.len(), 1);
172        assert_eq!(t[0].label, "root");
173    }
174}