acyclic_fs/kernel/
types.rs

1//! Typed invariants shared by authenticated namespace algorithms.
2
3use crate::foundation::{Digest, FileId};
4use crate::model::FilesystemProfile;
5use crate::storage::{ObjectId, ObjectKind};
6use std::borrow::Cow;
7use thiserror::Error;
8
9/// Canonical host-name representation.
10#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
11pub enum NameEncoding {
12    /// Portable UTF-8 scalar sequence.
13    Utf8,
14    /// Raw POSIX bytes excluding NUL and `/`.
15    PosixBytes,
16    /// Little-endian UTF-16 code units excluding NUL, `/`, and `\`.
17    WindowsUtf16Le,
18}
19
20impl NameEncoding {
21    pub(crate) const fn tag(self) -> u8 {
22        match self {
23            Self::Utf8 => 1,
24            Self::PosixBytes => 2,
25            Self::WindowsUtf16Le => 3,
26        }
27    }
28
29    pub(crate) const fn from_tag(tag: u8) -> Result<Self, TreePageError> {
30        match tag {
31            1 => Ok(Self::Utf8),
32            2 => Ok(Self::PosixBytes),
33            3 => Ok(Self::WindowsUtf16Le),
34            value => Err(TreePageError::UnknownNameEncoding(value)),
35        }
36    }
37}
38
39/// One separator-free canonical logical name.
40#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
41pub struct LogicalName {
42    encoding: NameEncoding,
43    bytes: Vec<u8>,
44}
45
46impl LogicalName {
47    /// Validates a bounded name in its declared host representation.
48    ///
49    /// # Errors
50    ///
51    /// Rejects empty, oversized, malformed, NUL, or separator-bearing names.
52    pub fn new(
53        encoding: NameEncoding,
54        bytes: Vec<u8>,
55        maximum_bytes: u32,
56    ) -> Result<Self, TreePageError> {
57        if bytes.is_empty() {
58            return Err(TreePageError::EmptyName);
59        }
60        if u32::try_from(bytes.len()).unwrap_or(u32::MAX) > maximum_bytes {
61            return Err(TreePageError::NameTooLarge);
62        }
63        match encoding {
64            NameEncoding::Utf8 => {
65                let value = std::str::from_utf8(&bytes).map_err(|_| TreePageError::InvalidName)?;
66                if value == "." || value == ".." || value.contains('/') || value.contains('\0') {
67                    return Err(TreePageError::InvalidName);
68                }
69            }
70            NameEncoding::PosixBytes => {
71                if bytes.contains(&0) || bytes.contains(&b'/') || bytes == b"." || bytes == b".." {
72                    return Err(TreePageError::InvalidName);
73                }
74            }
75            NameEncoding::WindowsUtf16Le => {
76                if !bytes.len().is_multiple_of(2) {
77                    return Err(TreePageError::InvalidName);
78                }
79                let units = bytes.chunks_exact(2).map(|pair| {
80                    let [low, high] = pair else {
81                        unreachable!("chunks_exact(2) always yields a length-2 slice")
82                    };
83                    u16::from_le_bytes([*low, *high])
84                });
85                if bytes == [b'.', 0]
86                    || bytes == [b'.', 0, b'.', 0]
87                    || units.clone().any(|unit| {
88                        unit == 0 || unit == u16::from(b'/') || unit == u16::from(b'\\')
89                    })
90                    || char::decode_utf16(units).any(|decoded| decoded.is_err())
91                {
92                    return Err(TreePageError::InvalidName);
93                }
94            }
95        }
96        Ok(Self { encoding, bytes })
97    }
98
99    /// Returns the canonical representation kind.
100    #[must_use]
101    pub const fn encoding(&self) -> NameEncoding {
102        self.encoding
103    }
104
105    /// Borrows canonical name bytes.
106    #[must_use]
107    pub fn as_bytes(&self) -> &[u8] {
108        &self.bytes
109    }
110
111    /// Presents this exact name as Unicode when its host encoding permits it.
112    /// Raw POSIX names outside UTF-8 remain unrepresentable as strings.
113    #[must_use]
114    pub fn unicode_text(&self) -> Option<Cow<'_, str>> {
115        match self.encoding {
116            NameEncoding::Utf8 | NameEncoding::PosixBytes => {
117                std::str::from_utf8(&self.bytes).ok().map(Cow::Borrowed)
118            }
119            NameEncoding::WindowsUtf16Le => {
120                let units = self.bytes.chunks_exact(2).map(|pair| {
121                    let [low, high] = pair else {
122                        unreachable!("chunks_exact(2) yields pairs")
123                    };
124                    u16::from_le_bytes([*low, *high])
125                });
126                char::decode_utf16(units)
127                    .collect::<Result<String, _>>()
128                    .ok()
129                    .map(Cow::Owned)
130            }
131        }
132    }
133
134    pub(crate) fn retained_bytes(&self) -> usize {
135        self.bytes.capacity()
136    }
137
138    /// Comparison key for `CaseSensitivity::ProfileFolded` lookup and
139    /// collision detection.
140    ///
141    /// Only [`NameEncoding::Utf8`] names are folded (via full Unicode
142    /// case-folding, `str::to_lowercase`); other encodings return their raw
143    /// bytes unchanged, so `ProfileFolded` behaves like `Sensitive` for
144    /// `PosixBytes`/`WindowsUtf16Le` names. This never changes the physical,
145    /// byte-ordered on-disk representation — it is a comparison-only key used
146    /// by callers that already hold the name, not a new canonical form.
147    #[must_use]
148    pub fn case_fold_key(&self) -> Vec<u8> {
149        match self.encoding {
150            NameEncoding::Utf8 => {
151                // `LogicalName::new` already rejected non-UTF-8 bytes for
152                // this encoding, so this is exact, not lossy.
153                let Ok(value) = std::str::from_utf8(&self.bytes) else {
154                    return self.bytes.clone();
155                };
156                value.to_lowercase().into_bytes()
157            }
158            NameEncoding::PosixBytes | NameEncoding::WindowsUtf16Le => self.bytes.clone(),
159        }
160    }
161}
162
163/// Complete namespace entry kind.
164#[derive(Clone, Copy, Debug, Eq, PartialEq)]
165pub enum FileKind {
166    /// Ordinary byte file.
167    Regular,
168    /// Directory namespace.
169    Directory,
170    /// Symbolic link.
171    SymbolicLink,
172    /// FIFO.
173    Fifo,
174    /// Socket namespace entry.
175    Socket,
176    /// Character device.
177    CharacterDevice,
178    /// Block device.
179    BlockDevice,
180    /// Windows reparse point not represented as a symbolic link.
181    ReparsePoint,
182    /// Opaque boundary delegated to another mounted volume.
183    MountBoundary,
184}
185
186impl FileKind {
187    /// Whether this kind has an exact representation in one volume profile.
188    #[must_use]
189    pub const fn is_supported_by_profile(self, profile: FilesystemProfile) -> bool {
190        match self {
191            Self::Regular | Self::Directory | Self::SymbolicLink | Self::MountBoundary => true,
192            Self::Fifo | Self::Socket | Self::CharacterDevice | Self::BlockDevice => {
193                matches!(profile, FilesystemProfile::Posix)
194            }
195            Self::ReparsePoint => matches!(profile, FilesystemProfile::Windows),
196        }
197    }
198
199    pub(crate) const fn tag(self) -> u8 {
200        match self {
201            Self::Regular => 1,
202            Self::Directory => 2,
203            Self::SymbolicLink => 3,
204            Self::Fifo => 4,
205            Self::Socket => 5,
206            Self::CharacterDevice => 6,
207            Self::BlockDevice => 7,
208            Self::ReparsePoint => 8,
209            Self::MountBoundary => 9,
210        }
211    }
212
213    pub(crate) const fn from_tag(tag: u8) -> Result<Self, TreePageError> {
214        match tag {
215            1 => Ok(Self::Regular),
216            2 => Ok(Self::Directory),
217            3 => Ok(Self::SymbolicLink),
218            4 => Ok(Self::Fifo),
219            5 => Ok(Self::Socket),
220            6 => Ok(Self::CharacterDevice),
221            7 => Ok(Self::BlockDevice),
222            8 => Ok(Self::ReparsePoint),
223            9 => Ok(Self::MountBoundary),
224            value => Err(TreePageError::UnknownFileKind(value)),
225        }
226    }
227}
228
229/// One name-to-file binding in a directory leaf page.
230#[derive(Clone, Debug, Eq, PartialEq)]
231pub struct TreeEntry {
232    /// Canonical logical name.
233    pub name: LogicalName,
234    /// Path-independent file record identity; hard links reuse it.
235    pub file_id: FileId,
236    /// Namespace kind used for bounded routing and restoration.
237    pub kind: FileKind,
238}
239
240/// One lower-bound-to-page binding in an internal page.
241#[derive(Clone, Debug, Eq, PartialEq)]
242pub struct TreeChild {
243    /// Exact first name represented by the child subtree.
244    pub first_name: LogicalName,
245    /// Authenticated tree-page identity.
246    pub page: ObjectId,
247}
248
249/// One immutable authenticated directory B+tree page.
250#[derive(Clone, Debug, Eq, PartialEq)]
251pub enum TreePage {
252    /// Ordered file bindings.
253    Leaf(Vec<TreeEntry>),
254    /// Ordered child lower bounds.
255    Internal(Vec<TreeChild>),
256}
257
258impl TreePage {
259    /// Validates ordering, uniqueness, object kinds, and page bounds.
260    ///
261    /// # Errors
262    ///
263    /// Rejects malformed pages before hashing or publication.
264    pub fn validate(&self, maximum_items: u32) -> Result<(), TreePageError> {
265        let count = match self {
266            Self::Leaf(entries) => {
267                validate_order(entries.iter().map(|entry| &entry.name))?;
268                entries.len()
269            }
270            Self::Internal(children) => {
271                if children.is_empty() {
272                    return Err(TreePageError::EmptyInternalPage);
273                }
274                validate_order(children.iter().map(|child| &child.first_name))?;
275                if children
276                    .iter()
277                    .any(|child| child.page.kind != ObjectKind::TreePage)
278                {
279                    return Err(TreePageError::WrongChildKind);
280                }
281                children.len()
282            }
283        };
284        if u32::try_from(count).unwrap_or(u32::MAX) > maximum_items {
285            return Err(TreePageError::TooManyItems);
286        }
287        Ok(())
288    }
289}
290
291fn validate_order<'a>(
292    mut names: impl Iterator<Item = &'a LogicalName>,
293) -> Result<(), TreePageError> {
294    let Some(mut previous) = names.next() else {
295        return Ok(());
296    };
297    for name in names {
298        if previous >= name {
299            return Err(TreePageError::NamesNotStrictlyOrdered);
300        }
301        previous = name;
302    }
303    Ok(())
304}
305
306/// Authenticated tree-page invariant failures.
307#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
308pub enum TreePageError {
309    /// Logical names cannot be empty.
310    #[error("logical name is empty")]
311    EmptyName,
312    /// Name exceeds the configured encoded-byte bound.
313    #[error("logical name exceeds its byte bound")]
314    NameTooLarge,
315    /// Name bytes are malformed or contain a forbidden separator/component.
316    #[error("logical name is invalid for its declared encoding")]
317    InvalidName,
318    /// Decoder encountered an unknown name representation.
319    #[error("unknown logical name encoding {0}")]
320    UnknownNameEncoding(u8),
321    /// Decoder encountered an unknown file kind.
322    #[error("unknown file kind {0}")]
323    UnknownFileKind(u8),
324    /// Names must be canonical, strictly ordered, and unique.
325    #[error("tree page names are not strictly ordered")]
326    NamesNotStrictlyOrdered,
327    /// Internal pages must contain at least one routed child.
328    #[error("internal tree page is empty")]
329    EmptyInternalPage,
330    /// Internal child points at another object class.
331    #[error("internal tree child is not a tree page")]
332    WrongChildKind,
333    /// Page exceeds its admitted item bound.
334    #[error("tree page exceeds its item bound")]
335    TooManyItems,
336    /// Canonical bytes contain an invalid digest or field.
337    #[error("invalid canonical tree page field: {0}")]
338    InvalidCanonicalField(&'static str),
339}
340
341pub(crate) fn digest_object(kind: ObjectKind, digest: [u8; 32]) -> ObjectId {
342    ObjectId {
343        kind,
344        digest: Digest::from_bytes(digest),
345    }
346}
347
348/// Physical representation of one logical byte interval.
349#[derive(Clone, Debug, Eq, PartialEq)]
350pub enum ExtentKind {
351    /// Unallocated bytes that read as zero.
352    Hole,
353    /// Physically allocated bytes whose canonical value is zero.
354    AllocatedZero,
355    /// Bytes stored in one immutable blob span.
356    Content {
357        /// Typed immutable blob.
358        object: ObjectId,
359        /// First byte used from the blob.
360        object_offset: u64,
361    },
362}
363
364/// One non-empty logical file interval.
365#[derive(Clone, Debug, Eq, PartialEq)]
366pub struct Extent {
367    /// Inclusive logical byte offset.
368    pub offset: u64,
369    /// Positive logical byte length.
370    pub length: u64,
371    /// Physical representation.
372    pub kind: ExtentKind,
373}
374
375/// One lower-bound-to-page entry in an extent B+tree.
376#[derive(Clone, Debug, Eq, PartialEq)]
377pub struct ExtentChild {
378    /// First logical byte represented by the child.
379    pub first_offset: u64,
380    /// Exclusive logical end represented by the child.
381    pub end_offset: u64,
382    /// Authenticated extent page.
383    pub page: ObjectId,
384}
385
386/// One immutable authenticated extent B+tree page.
387#[derive(Clone, Debug, Eq, PartialEq)]
388pub enum ExtentPage {
389    /// Ordered non-overlapping extents.
390    Leaf(Vec<Extent>),
391    /// Ordered child lower bounds.
392    Internal(Vec<ExtentChild>),
393}
394
395impl ExtentPage {
396    /// Validates bounds, ordering, non-overlap, and typed child/content identities.
397    ///
398    /// # Errors
399    ///
400    /// Rejects malformed extent pages before hashing or publication.
401    pub fn validate(&self, maximum_items: u32) -> Result<(), ExtentPageError> {
402        let count = match self {
403            Self::Leaf(extents) => {
404                let mut previous_end = None;
405                for extent in extents {
406                    if extent.length == 0 {
407                        return Err(ExtentPageError::ZeroLength);
408                    }
409                    let end = extent
410                        .offset
411                        .checked_add(extent.length)
412                        .ok_or(ExtentPageError::RangeOverflow)?;
413                    if previous_end.is_some_and(|prior| extent.offset != prior) {
414                        return Err(ExtentPageError::NonContiguous);
415                    }
416                    if let ExtentKind::Content {
417                        object,
418                        object_offset,
419                    } = extent.kind
420                    {
421                        if object.kind != ObjectKind::Blob {
422                            return Err(ExtentPageError::WrongContentKind);
423                        }
424                        object_offset
425                            .checked_add(extent.length)
426                            .ok_or(ExtentPageError::RangeOverflow)?;
427                    }
428                    previous_end = Some(end);
429                }
430                extents.len()
431            }
432            Self::Internal(children) => {
433                if children.is_empty() {
434                    return Err(ExtentPageError::EmptyInternalPage);
435                }
436                if children.windows(2).any(|pair| {
437                    let [left, right] = pair else {
438                        unreachable!("windows(2) always yields exactly two elements")
439                    };
440                    left.end_offset != right.first_offset
441                }) {
442                    return Err(ExtentPageError::NonContiguous);
443                }
444                if children
445                    .iter()
446                    .any(|child| child.first_offset >= child.end_offset)
447                {
448                    return Err(ExtentPageError::InvalidChildRange);
449                }
450                if children
451                    .iter()
452                    .any(|child| child.page.kind != ObjectKind::ExtentPage)
453                {
454                    return Err(ExtentPageError::WrongChildKind);
455                }
456                children.len()
457            }
458        };
459        if u32::try_from(count).unwrap_or(u32::MAX) > maximum_items {
460            return Err(ExtentPageError::TooManyItems);
461        }
462        Ok(())
463    }
464}
465
466/// Authenticated extent-page invariant failures.
467#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
468pub enum ExtentPageError {
469    /// Extents must represent at least one logical byte.
470    #[error("extent length is zero")]
471    ZeroLength,
472    /// Logical or content-offset arithmetic overflowed.
473    #[error("extent range overflowed")]
474    RangeOverflow,
475    /// Extents/children overlap, have a gap, or are out of order.
476    #[error("extent page ranges are not contiguous")]
477    NonContiguous,
478    /// Content extent references another object class.
479    #[error("extent content is not a blob object")]
480    WrongContentKind,
481    /// Internal page has no routed children.
482    #[error("internal extent page is empty")]
483    EmptyInternalPage,
484    /// Internal child has an empty or reversed range.
485    #[error("extent child range is empty or reversed")]
486    InvalidChildRange,
487    /// Internal child references another object class.
488    #[error("extent child is not an extent page")]
489    WrongChildKind,
490    /// Page exceeds the admitted item bound.
491    #[error("extent page exceeds its item bound")]
492    TooManyItems,
493    /// Decoder encountered an unknown physical representation.
494    #[error("unknown extent kind {0}")]
495    UnknownKind(u8),
496}
497
498#[cfg(test)]
499#[path = "tests/types.rs"]
500mod tests;
acyclic_fs/kernel/types.rs

acyclic_fs/kernel/
types.rs
