limnifs_core/
directory_node.rs

1//! Directory node (spec §4.2, `bit-level/34-directory-node.md`).
2//!
3//! A directory node is a leaf of the deterministic Merkle B-tree that
4//! represents a directory's entries. Per pivot D2, v0.1 defines a
5//! single layout: the **leaf node** (all entries in one node). Future
6//! revisions may introduce internal nodes to scale beyond the leaf
7//! ceiling.
8//!
9//! Entries within a node MUST be lexicographic by name (§1.4). This
10//! makes range reads and diff walks deterministic.
11
12use crate::cursor::ManifestCursor;
13use crate::error::CoreError;
14
15/// Currently supported node version.
16pub const DIRECTORY_NODE_VERSION: u8 = 1;
17
18/// POSIX-equivalent file-type tags used in directory entries.
19///
20/// These are the same values the [`crate::inode`] module uses for the
21/// `S_IFMT` bits, narrowed to the four shapes the directory node
22/// allows. Values outside `0x01..=0x04` are reserved.
23pub mod entry_type {
24    pub const FILE: u8 = 0x01;
25    pub const DIRECTORY: u8 = 0x02;
26    pub const SYMLINK: u8 = 0x03;
27    pub const SPECIAL: u8 = 0x04;
28}
29
30/// One directory entry: a name, an inode number, and a type tag.
31#[derive(Clone, Debug, Eq, PartialEq)]
32pub struct DirEntry {
33    pub name: String,
34    pub inode_number: u64,
35    pub entry_type: u8,
36}
37
38/// A parsed directory node (leaf only in v0.1).
39#[derive(Clone, Debug, Eq, PartialEq)]
40pub struct DirectoryNode {
41    pub version: u8,
42    pub entries: Vec<DirEntry>,
43}
44
45/// Parse one directory node from the cursor's current position.
46///
47/// # Errors
48///
49/// - [`CoreError::Corrupt`] for structural problems (unsorted entries,
50///   duplicate names, empty names, names containing `/` or NUL, an
51///   invalid `entry_type`).
52/// - [`CoreError::UnsupportedFeature`] for an unknown node version.
53/// - [`CoreError::TooShort`] if the cursor underruns.
54pub fn parse_directory_node(cursor: &mut ManifestCursor<'_>) -> Result<DirectoryNode, CoreError> {
55    let version = cursor.read_u8()?;
56    if version != DIRECTORY_NODE_VERSION {
57        return Err(CoreError::UnsupportedFeature {
58            feature: format!("directory node version {version}"),
59        });
60    }
61    let entry_count = cursor.read_u32_le()?;
62    let entry_count_us = usize::try_from(entry_count).map_err(|_| CoreError::Corrupt {
63        reason: format!("directory node entry_count {entry_count} exceeds usize"),
64    })?;
65    let mut entries: Vec<DirEntry> = Vec::with_capacity(entry_count_us);
66    let mut prev_name: Option<&str> = None;
67    for i in 0..entry_count_us {
68        let name_len = cursor.read_u32_le()?;
69        let name_len_us = usize::try_from(name_len).map_err(|_| CoreError::Corrupt {
70            reason: format!("directory node entry {i} name_len {name_len} exceeds usize"),
71        })?;
72        let name_bytes = cursor.read_n(name_len_us)?;
73        if name_bytes.is_empty() {
74            return Err(CoreError::Corrupt {
75                reason: format!("directory node entry {i}: empty name"),
76            });
77        }
78        if name_bytes.contains(&b'/') {
79            return Err(CoreError::Corrupt {
80                reason: format!("directory node entry {i}: name contains '/'"),
81            });
82        }
83        if name_bytes.contains(&0) {
84            return Err(CoreError::Corrupt {
85                reason: format!("directory node entry {i}: name contains NUL byte"),
86            });
87        }
88        let name = std::str::from_utf8(name_bytes).map_err(|_| CoreError::Corrupt {
89            reason: format!("directory node entry {i}: name is not valid UTF-8"),
90        })?;
91        if let Some(prev) = prev_name {
92            if prev >= name {
93                return Err(CoreError::Corrupt {
94                    reason: format!("directory node: entries not sorted ({prev:?} >= {name:?})"),
95                });
96            }
97        }
98        let inode_number = cursor.read_u64_le()?;
99        let entry_type = cursor.read_u8()?;
100        if !matches!(
101            entry_type,
102            entry_type::FILE | entry_type::DIRECTORY | entry_type::SYMLINK | entry_type::SPECIAL
103        ) {
104            return Err(CoreError::Corrupt {
105                reason: format!("directory node entry {i}: invalid entry_type 0x{entry_type:02X}"),
106            });
107        }
108        prev_name = Some(name);
109        entries.push(DirEntry {
110            name: name.to_owned(),
111            inode_number,
112            entry_type,
113        });
114    }
115    Ok(DirectoryNode { version, entries })
116}
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121
122    fn encode_node(entries: &[(&str, u64, u8)]) -> Vec<u8> {
123        let mut bytes = Vec::new();
124        bytes.push(DIRECTORY_NODE_VERSION);
125        bytes.extend_from_slice(&u32::try_from(entries.len()).unwrap().to_le_bytes());
126        for (name, inode_number, entry_type) in entries {
127            let name_bytes = name.as_bytes();
128            let name_len = u32::try_from(name_bytes.len()).unwrap();
129            bytes.extend_from_slice(&name_len.to_le_bytes());
130            bytes.extend_from_slice(name_bytes);
131            bytes.extend_from_slice(&inode_number.to_le_bytes());
132            bytes.push(*entry_type);
133        }
134        bytes
135    }
136
137    #[test]
138    fn parses_sorted_directory_node() {
139        let bytes = encode_node(&[
140            ("README.md", 3, entry_type::FILE),
141            ("bin", 1, entry_type::DIRECTORY),
142            ("hello.txt", 2, entry_type::FILE),
143        ]);
144        let mut cursor = ManifestCursor::new(&bytes);
145        let node = parse_directory_node(&mut cursor).expect("parses");
146        assert_eq!(node.version, 1);
147        assert_eq!(node.entries.len(), 3);
148        assert_eq!(node.entries[0].name, "README.md");
149        assert_eq!(node.entries[1].name, "bin");
150        assert_eq!(node.entries[2].name, "hello.txt");
151        assert_eq!(node.entries[1].entry_type, entry_type::DIRECTORY);
152    }
153
154    #[test]
155    fn parses_empty_directory() {
156        let bytes = encode_node(&[]);
157        let mut cursor = ManifestCursor::new(&bytes);
158        let node = parse_directory_node(&mut cursor).expect("empty node parses");
159        assert_eq!(node.version, 1);
160        assert!(node.entries.is_empty());
161        assert_eq!(cursor.position(), bytes.len());
162    }
163
164    #[test]
165    fn rejects_unsorted_entries() {
166        // "z" comes before "a" — out of order.
167        let bytes = encode_node(&[("z", 1, entry_type::FILE), ("a", 2, entry_type::FILE)]);
168        let mut cursor = ManifestCursor::new(&bytes);
169        match parse_directory_node(&mut cursor) {
170            Err(CoreError::Corrupt { reason }) => {
171                assert!(reason.contains("not sorted"), "got: {reason}");
172            }
173            other => panic!("expected Corrupt, got {other:?}"),
174        }
175    }
176
177    #[test]
178    fn rejects_empty_name() {
179        // Manually build a node with a zero-length name to bypass the
180        // encoder's `&str` typing.
181        let mut bytes = Vec::new();
182        bytes.push(DIRECTORY_NODE_VERSION);
183        bytes.extend_from_slice(&1u32.to_le_bytes());
184        bytes.extend_from_slice(&0u32.to_le_bytes()); // name_len = 0
185        bytes.extend_from_slice(&1u64.to_le_bytes()); // inode_number
186        bytes.push(entry_type::FILE);
187        let mut cursor = ManifestCursor::new(&bytes);
188        match parse_directory_node(&mut cursor) {
189            Err(CoreError::Corrupt { reason }) => {
190                assert!(reason.contains("empty name"), "got: {reason}");
191            }
192            other => panic!("expected Corrupt, got {other:?}"),
193        }
194    }
195
196    #[test]
197    fn rejects_name_with_slash() {
198        let bytes = encode_node(&[("foo/bar", 1, entry_type::FILE)]);
199        let mut cursor = ManifestCursor::new(&bytes);
200        match parse_directory_node(&mut cursor) {
201            Err(CoreError::Corrupt { reason }) => {
202                assert!(reason.contains("'/'"), "got: {reason}");
203            }
204            other => panic!("expected Corrupt, got {other:?}"),
205        }
206    }
207
208    #[test]
209    fn rejects_invalid_entry_type() {
210        let mut bytes = Vec::new();
211        bytes.push(DIRECTORY_NODE_VERSION);
212        bytes.extend_from_slice(&1u32.to_le_bytes());
213        bytes.extend_from_slice(&1u32.to_le_bytes()); // name_len
214        bytes.extend_from_slice(b"x");
215        bytes.extend_from_slice(&1u64.to_le_bytes());
216        bytes.push(0x05); // reserved
217        let mut cursor = ManifestCursor::new(&bytes);
218        match parse_directory_node(&mut cursor) {
219            Err(CoreError::Corrupt { reason }) => {
220                assert!(reason.contains("invalid entry_type"), "got: {reason}");
221            }
222            other => panic!("expected Corrupt, got {other:?}"),
223        }
224    }
225
226    #[test]
227    fn rejects_unknown_node_version() {
228        let mut bytes = vec![0x07]; // version 7
229        bytes.extend_from_slice(&0u32.to_le_bytes());
230        let mut cursor = ManifestCursor::new(&bytes);
231        match parse_directory_node(&mut cursor) {
232            Err(CoreError::UnsupportedFeature { feature }) => {
233                assert!(feature.contains('7'), "got: {feature}");
234            }
235            other => panic!("expected UnsupportedFeature, got {other:?}"),
236        }
237    }
238
239    #[test]
240    fn rejects_too_short_for_prefix() {
241        let bytes = [DIRECTORY_NODE_VERSION];
242        let mut cursor = ManifestCursor::new(&bytes);
243        match parse_directory_node(&mut cursor) {
244            Err(CoreError::TooShort { .. }) => {}
245            other => panic!("expected TooShort, got {other:?}"),
246        }
247    }
248}
limnifs_core/directory_node.rs

limnifs_core/
directory_node.rs
