use thiserror::Error;
pub const SEGMENT_WIDTH: usize = 4;
pub const WIDE_MARKER: char = '~';
pub const WIDE_WIDTH: usize = 8;
pub const SEPARATOR: char = '/';
#[derive(Debug, Error)]
pub enum PathError {
#[error("tree id {id} is outside 1..={max}", max = u32::MAX)]
SegmentOverflow { id: i64 },
#[error("path segment {segment:?} is not a valid {SEGMENT_WIDTH}-wide hex id")]
BadSegment { segment: String },
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MaterializedPath(String);
impl MaterializedPath {
pub fn root(id: i64) -> Result<Self, PathError> {
let mut s = String::with_capacity(SEGMENT_WIDTH + 1);
push_segment(&mut s, id)?;
Ok(Self(s))
}
pub fn child_of(parent: &str, id: i64) -> Result<Self, PathError> {
let mut s = String::with_capacity(parent.len() + SEGMENT_WIDTH + 1);
s.push_str(parent);
push_segment(&mut s, id)?;
Ok(Self(s))
}
pub fn as_str(&self) -> &str {
&self.0
}
pub fn into_string(self) -> String {
self.0
}
pub fn depth(&self) -> i32 {
depth_of(&self.0)
}
pub fn parent(&self) -> Option<String> {
parent_of(&self.0).map(str::to_owned)
}
pub fn ancestors(&self) -> Vec<String> {
let mut out = Vec::new();
let mut acc = String::new();
for seg in self.0.split(SEPARATOR).filter(|s| !s.is_empty()) {
acc.push_str(seg);
acc.push(SEPARATOR);
if acc != self.0 {
out.push(acc.clone());
}
}
out
}
}
pub fn depth_of(path: &str) -> i32 {
path.split(SEPARATOR).filter(|s| !s.is_empty()).count() as i32
}
pub fn parent_of(path: &str) -> Option<&str> {
let trimmed = path.strip_suffix(SEPARATOR).unwrap_or(path);
let cut = trimmed.rfind(SEPARATOR)?;
Some(&path[..=cut])
}
pub fn descendants_like(parent_path: &str) -> String {
format!("{parent_path}%")
}
fn push_segment(buf: &mut String, id: i64) -> Result<(), PathError> {
use std::fmt::Write;
if id <= 0 || id > i64::from(u32::MAX) {
return Err(PathError::SegmentOverflow { id });
}
if id <= i64::from(u16::MAX) {
let _ = write!(buf, "{:0width$x}{}", id, SEPARATOR, width = SEGMENT_WIDTH);
} else {
let _ = write!(buf, "{WIDE_MARKER}{:0width$x}{}", id, SEPARATOR, width = WIDE_WIDTH);
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn root_and_child() {
let root = MaterializedPath::root(1).unwrap();
assert_eq!(root.as_str(), "0001/");
let child = MaterializedPath::child_of(root.as_str(), 3).unwrap();
assert_eq!(child.as_str(), "0001/0003/");
assert_eq!(child.depth(), 2);
assert_eq!(child.parent().as_deref(), Some("0001/"));
}
#[test]
fn ancestors_excludes_self() {
let p = MaterializedPath::child_of("0001/0003/", 8).unwrap();
assert_eq!(
p.ancestors(),
vec!["0001/".to_string(), "0001/0003/".to_string()]
);
}
#[test]
fn descendants_like_pattern() {
assert_eq!(descendants_like("0001/"), "0001/%");
}
#[test]
fn segment_overflow_rejected() {
assert!(matches!(
MaterializedPath::root(0),
Err(PathError::SegmentOverflow { id: 0 })
));
assert!(matches!(
MaterializedPath::root(i64::from(u32::MAX) + 1),
Err(PathError::SegmentOverflow { .. })
));
}
#[test]
fn ids_past_65535_get_a_wide_segment() {
assert_eq!(MaterializedPath::root(0xffff).unwrap().as_str(), "ffff/");
assert_eq!(MaterializedPath::root(0x1_0000).unwrap().as_str(), "~00010000/");
let child = MaterializedPath::child_of("0001/", 70_000).unwrap();
assert_eq!(child.as_str(), "0001/~00011170/");
assert_eq!(child.depth(), 2);
assert_eq!(child.parent().as_deref(), Some("0001/"));
}
#[test]
fn mixed_widths_keep_sibling_order_and_subtree_contiguity() {
let parent = "0001/";
let narrow = MaterializedPath::child_of(parent, 0xfffe).unwrap().into_string();
let narrow_kid = MaterializedPath::child_of(&narrow, 2).unwrap().into_string();
let wide = MaterializedPath::child_of(parent, 0x1_0001).unwrap().into_string();
let wider = MaterializedPath::child_of(parent, 0x2_0000).unwrap().into_string();
let mut sorted = vec![wider.clone(), wide.clone(), narrow_kid.clone(), narrow.clone()];
sorted.sort();
assert_eq!(sorted, vec![narrow, narrow_kid, wide, wider]);
}
}