Skip to main content

rustango_cms/
tree.rs

1//! Materialized-path encoding for the page tree.
2//!
3//! A page's `path` is its ancestors' row ids as hex segments
4//! followed by its own, so `ORDER BY path` is a depth-first walk and a
5//! subtree is one prefix range. This module only builds and parses
6//! paths; tree mutations live in [`crate::tree_ops`].
7
8use thiserror::Error;
9
10/// Width of a materialized-path segment for ids up to 65 535: 4 hex chars.
11///
12/// A segment is the node's **row id**, not its position under its parent,
13/// so this bounds ids per tenant, not children per parent. Larger ids use
14/// [`WIDE_MARKER`] + [`WIDE_WIDTH`] hex chars instead.
15pub const SEGMENT_WIDTH: usize = 4;
16
17/// Marks a segment for an id above 65 535. `~` sorts after every hex
18/// digit, so wide siblings order after narrow ones and by id among
19/// themselves; like any segment it ends in [`SEPARATOR`], which sorts
20/// below every digit, so a subtree stays contiguous under `ORDER BY path`.
21pub const WIDE_MARKER: char = '~';
22
23/// Hex width of a wide segment: ids up to `u32::MAX`.
24pub const WIDE_WIDTH: usize = 8;
25pub const SEPARATOR: char = '/';
26
27#[derive(Debug, Error)]
28pub enum PathError {
29    #[error("tree id {id} is outside 1..={max}", max = u32::MAX)]
30    SegmentOverflow { id: i64 },
31    #[error("path segment {segment:?} is not a valid {SEGMENT_WIDTH}-wide hex id")]
32    BadSegment { segment: String },
33}
34
35/// Helper for building, parsing, and querying materialized paths.
36///
37/// A path is a sequence of hex id segments joined by `/` with a trailing
38/// `/`. Example for ids 1, 3, 8: `"0001/0003/0008/"`; an id above 65 535
39/// is written wide, e.g. 70 000 → `"~00011170/"`.
40///
41/// Trailing slash matters — it makes prefix queries (`path LIKE 'parent/%'`)
42/// safe against false matches like `0001/00012/` matching `0001/0001/`.
43#[derive(Debug, Clone, PartialEq, Eq)]
44pub struct MaterializedPath(String);
45
46impl MaterializedPath {
47    pub fn root(id: i64) -> Result<Self, PathError> {
48        let mut s = String::with_capacity(SEGMENT_WIDTH + 1);
49        push_segment(&mut s, id)?;
50        Ok(Self(s))
51    }
52
53    pub fn child_of(parent: &str, id: i64) -> Result<Self, PathError> {
54        let mut s = String::with_capacity(parent.len() + SEGMENT_WIDTH + 1);
55        s.push_str(parent);
56        push_segment(&mut s, id)?;
57        Ok(Self(s))
58    }
59
60    pub fn as_str(&self) -> &str {
61        &self.0
62    }
63
64    pub fn into_string(self) -> String {
65        self.0
66    }
67
68    pub fn depth(&self) -> i32 {
69        depth_of(&self.0)
70    }
71
72    /// Returns the parent's path, or None if this is a root.
73    pub fn parent(&self) -> Option<String> {
74        parent_of(&self.0).map(str::to_owned)
75    }
76
77    /// All ancestor paths from root → immediate parent (excludes self).
78    pub fn ancestors(&self) -> Vec<String> {
79        let mut out = Vec::new();
80        let mut acc = String::new();
81        for seg in self.0.split(SEPARATOR).filter(|s| !s.is_empty()) {
82            acc.push_str(seg);
83            acc.push(SEPARATOR);
84            if acc != self.0 {
85                out.push(acc.clone());
86            }
87        }
88        out
89    }
90}
91
92/// Compute depth from a raw path string. Trailing-slash safe.
93pub fn depth_of(path: &str) -> i32 {
94    path.split(SEPARATOR).filter(|s| !s.is_empty()).count() as i32
95}
96
97/// Strip the last segment, returning the parent prefix (with trailing `/`),
98/// or None if the path was already a single segment.
99pub fn parent_of(path: &str) -> Option<&str> {
100    let trimmed = path.strip_suffix(SEPARATOR).unwrap_or(path);
101    let cut = trimmed.rfind(SEPARATOR)?;
102    Some(&path[..=cut])
103}
104
105/// SQL `LIKE` pattern matching every descendant of `parent_path` — and the
106/// parent itself, since `%` matches the empty string. Callers that want
107/// descendants only add `path != parent_path`.
108pub fn descendants_like(parent_path: &str) -> String {
109    format!("{parent_path}%")
110}
111
112fn push_segment(buf: &mut String, id: i64) -> Result<(), PathError> {
113    use std::fmt::Write;
114    if id <= 0 || id > i64::from(u32::MAX) {
115        return Err(PathError::SegmentOverflow { id });
116    }
117    // Writing into a String cannot fail.
118    if id <= i64::from(u16::MAX) {
119        let _ = write!(buf, "{:0width$x}{}", id, SEPARATOR, width = SEGMENT_WIDTH);
120    } else {
121        let _ = write!(buf, "{WIDE_MARKER}{:0width$x}{}", id, SEPARATOR, width = WIDE_WIDTH);
122    }
123    Ok(())
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129
130    #[test]
131    fn root_and_child() {
132        let root = MaterializedPath::root(1).unwrap();
133        assert_eq!(root.as_str(), "0001/");
134        let child = MaterializedPath::child_of(root.as_str(), 3).unwrap();
135        assert_eq!(child.as_str(), "0001/0003/");
136        assert_eq!(child.depth(), 2);
137        assert_eq!(child.parent().as_deref(), Some("0001/"));
138    }
139
140    #[test]
141    fn ancestors_excludes_self() {
142        let p = MaterializedPath::child_of("0001/0003/", 8).unwrap();
143        assert_eq!(
144            p.ancestors(),
145            vec!["0001/".to_string(), "0001/0003/".to_string()]
146        );
147    }
148
149    #[test]
150    fn descendants_like_pattern() {
151        assert_eq!(descendants_like("0001/"), "0001/%");
152    }
153
154    #[test]
155    fn segment_overflow_rejected() {
156        assert!(matches!(
157            MaterializedPath::root(0),
158            Err(PathError::SegmentOverflow { id: 0 })
159        ));
160        assert!(matches!(
161            MaterializedPath::root(i64::from(u32::MAX) + 1),
162            Err(PathError::SegmentOverflow { .. })
163        ));
164    }
165
166    #[test]
167    fn ids_past_65535_get_a_wide_segment() {
168        // #678 — a tenant's 65 536th page used to be impossible to create.
169        assert_eq!(MaterializedPath::root(0xffff).unwrap().as_str(), "ffff/");
170        assert_eq!(MaterializedPath::root(0x1_0000).unwrap().as_str(), "~00010000/");
171        let child = MaterializedPath::child_of("0001/", 70_000).unwrap();
172        assert_eq!(child.as_str(), "0001/~00011170/");
173        assert_eq!(child.depth(), 2);
174        assert_eq!(child.parent().as_deref(), Some("0001/"));
175    }
176
177    #[test]
178    fn mixed_widths_keep_sibling_order_and_subtree_contiguity() {
179        let parent = "0001/";
180        let narrow = MaterializedPath::child_of(parent, 0xfffe).unwrap().into_string();
181        let narrow_kid = MaterializedPath::child_of(&narrow, 2).unwrap().into_string();
182        let wide = MaterializedPath::child_of(parent, 0x1_0001).unwrap().into_string();
183        let wider = MaterializedPath::child_of(parent, 0x2_0000).unwrap().into_string();
184        let mut sorted = vec![wider.clone(), wide.clone(), narrow_kid.clone(), narrow.clone()];
185        sorted.sort();
186        // Pre-order: each node before its subtree, subtrees contiguous,
187        // siblings in id order across the width boundary.
188        assert_eq!(sorted, vec![narrow, narrow_kid, wide, wider]);
189    }
190}