1use thiserror::Error;
9
10pub const SEGMENT_WIDTH: usize = 4;
16
17pub const WIDE_MARKER: char = '~';
22
23pub 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#[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 pub fn parent(&self) -> Option<String> {
74 parent_of(&self.0).map(str::to_owned)
75 }
76
77 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
92pub fn depth_of(path: &str) -> i32 {
94 path.split(SEPARATOR).filter(|s| !s.is_empty()).count() as i32
95}
96
97pub 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
105pub 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 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 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 assert_eq!(sorted, vec![narrow, narrow_kid, wide, wider]);
189 }
190}