zub/types/
tree.rs

1use serde::{Deserialize, Serialize};
2
3use crate::error::{Error, Result};
4use crate::hash::Hash;
5use crate::types::{SparseRegion, Xattr};
6
7/// a directory tree - collection of entries sorted by name
8#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
9pub struct Tree {
10    entries: Vec<TreeEntry>,
11}
12
13impl Tree {
14    /// create a new tree, validating and sorting entries
15    pub fn new(mut entries: Vec<TreeEntry>) -> Result<Self> {
16        // validate entry names
17        for entry in &entries {
18            validate_entry_name(&entry.name)?;
19        }
20
21        // sort by name (byte-wise)
22        entries.sort_by(|a, b| a.name.as_bytes().cmp(b.name.as_bytes()));
23
24        // check for duplicates
25        for window in entries.windows(2) {
26            if window[0].name == window[1].name {
27                return Err(Error::DuplicateEntryName(window[0].name.clone()));
28            }
29        }
30
31        Ok(Self { entries })
32    }
33
34    /// create an empty tree
35    pub fn empty() -> Self {
36        Self { entries: vec![] }
37    }
38
39    /// get entries slice
40    pub fn entries(&self) -> &[TreeEntry] {
41        &self.entries
42    }
43
44    /// consume and return entries
45    pub fn into_entries(self) -> Vec<TreeEntry> {
46        self.entries
47    }
48
49    /// look up entry by name
50    pub fn get(&self, name: &str) -> Option<&TreeEntry> {
51        self.entries
52            .binary_search_by(|e| e.name.as_bytes().cmp(name.as_bytes()))
53            .ok()
54            .map(|i| &self.entries[i])
55    }
56
57    /// number of entries
58    pub fn len(&self) -> usize {
59        self.entries.len()
60    }
61
62    /// is tree empty
63    pub fn is_empty(&self) -> bool {
64        self.entries.is_empty()
65    }
66}
67
68/// validate an entry name
69fn validate_entry_name(name: &str) -> Result<()> {
70    if name.is_empty() {
71        return Err(Error::InvalidEntryName("empty name".to_string()));
72    }
73    if name.contains('/') {
74        return Err(Error::InvalidEntryName(format!(
75            "name contains '/': {}",
76            name
77        )));
78    }
79    if name.contains('\0') {
80        return Err(Error::InvalidEntryName(format!(
81            "name contains null byte: {}",
82            name
83        )));
84    }
85    if name == "." || name == ".." {
86        return Err(Error::InvalidEntryName(format!("reserved name: {}", name)));
87    }
88    Ok(())
89}
90
91/// a single entry in a tree
92#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
93pub struct TreeEntry {
94    pub name: String,
95    pub kind: EntryKind,
96}
97
98impl TreeEntry {
99    pub fn new(name: impl Into<String>, kind: EntryKind) -> Self {
100        Self {
101            name: name.into(),
102            kind,
103        }
104    }
105
106    /// get the type name for error messages
107    pub fn type_name(&self) -> &'static str {
108        self.kind.type_name()
109    }
110}
111
112/// kind of tree entry with associated metadata
113#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
114#[serde(tag = "type", rename_all = "snake_case")]
115pub enum EntryKind {
116    /// regular file
117    Regular {
118        hash: Hash,
119        size: u64,
120        #[serde(skip_serializing_if = "Option::is_none", default)]
121        sparse_map: Option<Vec<SparseRegion>>,
122    },
123
124    /// symbolic link
125    Symlink { hash: Hash },
126
127    /// directory
128    Directory {
129        hash: Hash,
130        uid: u32,
131        gid: u32,
132        mode: u32,
133        #[serde(default, skip_serializing_if = "Vec::is_empty")]
134        xattrs: Vec<Xattr>,
135    },
136
137    /// block device
138    BlockDevice {
139        major: u32,
140        minor: u32,
141        uid: u32,
142        gid: u32,
143        mode: u32,
144        #[serde(default, skip_serializing_if = "Vec::is_empty")]
145        xattrs: Vec<Xattr>,
146    },
147
148    /// character device
149    CharDevice {
150        major: u32,
151        minor: u32,
152        uid: u32,
153        gid: u32,
154        mode: u32,
155        #[serde(default, skip_serializing_if = "Vec::is_empty")]
156        xattrs: Vec<Xattr>,
157    },
158
159    /// named pipe (fifo)
160    Fifo {
161        uid: u32,
162        gid: u32,
163        mode: u32,
164        #[serde(default, skip_serializing_if = "Vec::is_empty")]
165        xattrs: Vec<Xattr>,
166    },
167
168    /// unix socket
169    Socket {
170        uid: u32,
171        gid: u32,
172        mode: u32,
173        #[serde(default, skip_serializing_if = "Vec::is_empty")]
174        xattrs: Vec<Xattr>,
175    },
176
177    /// hardlink to another file in the same tree
178    Hardlink {
179        /// path relative to tree root
180        target_path: String,
181    },
182}
183
184impl EntryKind {
185    /// get the type name for error messages
186    pub fn type_name(&self) -> &'static str {
187        match self {
188            EntryKind::Regular { .. } => "regular",
189            EntryKind::Symlink { .. } => "symlink",
190            EntryKind::Directory { .. } => "directory",
191            EntryKind::BlockDevice { .. } => "block_device",
192            EntryKind::CharDevice { .. } => "char_device",
193            EntryKind::Fifo { .. } => "fifo",
194            EntryKind::Socket { .. } => "socket",
195            EntryKind::Hardlink { .. } => "hardlink",
196        }
197    }
198
199    /// is this a directory entry
200    pub fn is_directory(&self) -> bool {
201        matches!(self, EntryKind::Directory { .. })
202    }
203
204    /// is this a regular file entry
205    pub fn is_regular(&self) -> bool {
206        matches!(self, EntryKind::Regular { .. })
207    }
208
209    /// is this a symlink entry
210    pub fn is_symlink(&self) -> bool {
211        matches!(self, EntryKind::Symlink { .. })
212    }
213
214    /// get the hash if this entry has one (files, symlinks, directories)
215    pub fn hash(&self) -> Option<&Hash> {
216        match self {
217            EntryKind::Regular { hash, .. } => Some(hash),
218            EntryKind::Symlink { hash } => Some(hash),
219            EntryKind::Directory { hash, .. } => Some(hash),
220            _ => None,
221        }
222    }
223
224    /// create a regular file entry
225    pub fn regular(hash: Hash, size: u64) -> Self {
226        Self::Regular {
227            hash,
228            size,
229            sparse_map: None,
230        }
231    }
232
233    /// create a sparse regular file entry
234    pub fn sparse(hash: Hash, size: u64, sparse_map: Vec<SparseRegion>) -> Self {
235        Self::Regular {
236            hash,
237            size,
238            sparse_map: Some(sparse_map),
239        }
240    }
241
242    /// create a symlink entry
243    pub fn symlink(hash: Hash) -> Self {
244        Self::Symlink { hash }
245    }
246
247    /// create a directory entry
248    pub fn directory(hash: Hash, uid: u32, gid: u32, mode: u32) -> Self {
249        Self::Directory {
250            hash,
251            uid,
252            gid,
253            mode,
254            xattrs: vec![],
255        }
256    }
257
258    /// create a directory entry with xattrs
259    pub fn directory_with_xattrs(
260        hash: Hash,
261        uid: u32,
262        gid: u32,
263        mode: u32,
264        xattrs: Vec<Xattr>,
265    ) -> Self {
266        Self::Directory {
267            hash,
268            uid,
269            gid,
270            mode,
271            xattrs,
272        }
273    }
274
275    /// create a hardlink entry
276    pub fn hardlink(target_path: impl Into<String>) -> Self {
277        Self::Hardlink {
278            target_path: target_path.into(),
279        }
280    }
281}
282
283#[cfg(test)]
284mod tests {
285    use super::*;
286
287    #[test]
288    fn test_tree_empty() {
289        let t = Tree::empty();
290        assert!(t.is_empty());
291        assert_eq!(t.len(), 0);
292    }
293
294    #[test]
295    fn test_tree_sorting() {
296        let entries = vec![
297            TreeEntry::new("zebra", EntryKind::regular(Hash::ZERO, 0)),
298            TreeEntry::new("alpha", EntryKind::regular(Hash::ZERO, 0)),
299            TreeEntry::new("beta", EntryKind::regular(Hash::ZERO, 0)),
300        ];
301        let tree = Tree::new(entries).unwrap();
302        let names: Vec<_> = tree.entries().iter().map(|e| e.name.as_str()).collect();
303        assert_eq!(names, vec!["alpha", "beta", "zebra"]);
304    }
305
306    #[test]
307    fn test_tree_get() {
308        let entries = vec![
309            TreeEntry::new("alpha", EntryKind::regular(Hash::ZERO, 10)),
310            TreeEntry::new("beta", EntryKind::regular(Hash::ZERO, 20)),
311        ];
312        let tree = Tree::new(entries).unwrap();
313
314        assert!(tree.get("alpha").is_some());
315        assert!(tree.get("beta").is_some());
316        assert!(tree.get("gamma").is_none());
317    }
318
319    #[test]
320    fn test_tree_rejects_empty_name() {
321        let entries = vec![TreeEntry::new("", EntryKind::regular(Hash::ZERO, 0))];
322        assert!(Tree::new(entries).is_err());
323    }
324
325    #[test]
326    fn test_tree_rejects_slash_in_name() {
327        let entries = vec![TreeEntry::new("foo/bar", EntryKind::regular(Hash::ZERO, 0))];
328        assert!(Tree::new(entries).is_err());
329    }
330
331    #[test]
332    fn test_tree_rejects_null_in_name() {
333        let entries = vec![TreeEntry::new(
334            "foo\0bar",
335            EntryKind::regular(Hash::ZERO, 0),
336        )];
337        assert!(Tree::new(entries).is_err());
338    }
339
340    #[test]
341    fn test_tree_rejects_dot() {
342        let entries = vec![TreeEntry::new(".", EntryKind::regular(Hash::ZERO, 0))];
343        assert!(Tree::new(entries).is_err());
344    }
345
346    #[test]
347    fn test_tree_rejects_dotdot() {
348        let entries = vec![TreeEntry::new("..", EntryKind::regular(Hash::ZERO, 0))];
349        assert!(Tree::new(entries).is_err());
350    }
351
352    #[test]
353    fn test_tree_rejects_duplicates() {
354        let entries = vec![
355            TreeEntry::new("same", EntryKind::regular(Hash::ZERO, 0)),
356            TreeEntry::new("same", EntryKind::regular(Hash::ZERO, 0)),
357        ];
358        assert!(Tree::new(entries).is_err());
359    }
360
361    #[test]
362    fn test_entry_kind_type_names() {
363        assert_eq!(EntryKind::regular(Hash::ZERO, 0).type_name(), "regular");
364        assert_eq!(EntryKind::symlink(Hash::ZERO).type_name(), "symlink");
365        assert_eq!(
366            EntryKind::directory(Hash::ZERO, 0, 0, 0o755).type_name(),
367            "directory"
368        );
369        assert_eq!(EntryKind::hardlink("foo").type_name(), "hardlink");
370    }
371
372    #[test]
373    fn test_entry_kind_predicates() {
374        assert!(EntryKind::directory(Hash::ZERO, 0, 0, 0o755).is_directory());
375        assert!(!EntryKind::regular(Hash::ZERO, 0).is_directory());
376
377        assert!(EntryKind::regular(Hash::ZERO, 0).is_regular());
378        assert!(!EntryKind::symlink(Hash::ZERO).is_regular());
379
380        assert!(EntryKind::symlink(Hash::ZERO).is_symlink());
381        assert!(!EntryKind::regular(Hash::ZERO, 0).is_symlink());
382    }
383
384    #[test]
385    fn test_entry_kind_hash() {
386        let h = Hash::from_hex("abcdef0123456789abcdef0123456789abcdef0123456789abcdef0123456789")
387            .unwrap();
388
389        assert_eq!(EntryKind::regular(h, 0).hash(), Some(&h));
390        assert_eq!(EntryKind::symlink(h).hash(), Some(&h));
391        assert_eq!(EntryKind::directory(h, 0, 0, 0o755).hash(), Some(&h));
392
393        // these don't have hashes
394        assert!(EntryKind::hardlink("foo").hash().is_none());
395        assert!(EntryKind::Fifo {
396            uid: 0,
397            gid: 0,
398            mode: 0o644,
399            xattrs: vec![]
400        }
401        .hash()
402        .is_none());
403    }
404
405    #[test]
406    fn test_tree_cbor_roundtrip() {
407        let entries = vec![
408            TreeEntry::new("file.txt", EntryKind::regular(Hash::ZERO, 100)),
409            TreeEntry::new("link", EntryKind::symlink(Hash::ZERO)),
410            TreeEntry::new("dir", EntryKind::directory(Hash::ZERO, 1000, 1000, 0o755)),
411            TreeEntry::new(
412                "dev",
413                EntryKind::BlockDevice {
414                    major: 8,
415                    minor: 0,
416                    uid: 0,
417                    gid: 6,
418                    mode: 0o660,
419                    xattrs: vec![],
420                },
421            ),
422            TreeEntry::new("hardlink", EntryKind::hardlink("file.txt")),
423        ];
424
425        let tree = Tree::new(entries).unwrap();
426
427        // serialize to cbor
428        let mut cbor_bytes = Vec::new();
429        ciborium::into_writer(&tree, &mut cbor_bytes).unwrap();
430
431        // deserialize
432        let parsed: Tree = ciborium::from_reader(&cbor_bytes[..]).unwrap();
433
434        assert_eq!(tree, parsed);
435    }
436
437    #[test]
438    fn test_tree_cbor_determinism() {
439        // same tree should produce identical cbor bytes
440        let entries1 = vec![
441            TreeEntry::new("b", EntryKind::regular(Hash::ZERO, 0)),
442            TreeEntry::new("a", EntryKind::regular(Hash::ZERO, 0)),
443        ];
444        let entries2 = vec![
445            TreeEntry::new("a", EntryKind::regular(Hash::ZERO, 0)),
446            TreeEntry::new("b", EntryKind::regular(Hash::ZERO, 0)),
447        ];
448
449        let tree1 = Tree::new(entries1).unwrap();
450        let tree2 = Tree::new(entries2).unwrap();
451
452        let mut bytes1 = Vec::new();
453        let mut bytes2 = Vec::new();
454        ciborium::into_writer(&tree1, &mut bytes1).unwrap();
455        ciborium::into_writer(&tree2, &mut bytes2).unwrap();
456
457        assert_eq!(bytes1, bytes2);
458    }
459
460    #[test]
461    fn test_sparse_entry() {
462        let regions = vec![SparseRegion::new(0, 100), SparseRegion::new(1000, 200)];
463        let kind = EntryKind::sparse(Hash::ZERO, 2000, regions.clone());
464
465        if let EntryKind::Regular {
466            sparse_map, size, ..
467        } = kind
468        {
469            assert_eq!(size, 2000);
470            assert_eq!(sparse_map, Some(regions));
471        } else {
472            panic!("expected regular");
473        }
474    }
475}
zub/types/tree.rs

zub/types/
tree.rs
