acyclic_fs/kernel/
tree_mutation.rs

1//! Sparse persistent directory-tree mutation with shared-ancestor rewrites.
2
3use super::allocation::AllocationError;
4use super::codec::DecodedPageShape;
5use super::persistent_btree::{self, Child, Format, Page, PageRef};
6use super::tree::{
7    encode_tree_internal_children, encode_tree_leaf_entries, tree_page_decode_shape,
8};
9use super::{
10    CanonicalDecodeError, DecodeLimits, LogicalName, TreeEntry, TreePage, decode_tree_page,
11};
12use crate::foundation::FileId;
13use crate::performance::{OperationFailure, WorkBudget, WorkCounters, WorkError};
14use crate::storage::{ObjectId, ObjectKind, ObjectStoreError};
15use thiserror::Error;
16
17pub(crate) struct TreeFormat;
18
19impl Format for TreeFormat {
20    type Key = LogicalName;
21    type Value = TreeEntry;
22
23    fn kind() -> ObjectKind {
24        ObjectKind::TreePage
25    }
26
27    fn key(value: &Self::Value) -> &Self::Key {
28        &value.name
29    }
30
31    fn decode(bytes: &[u8], limits: DecodeLimits) -> Result<Page<Self>, CanonicalDecodeError> {
32        Ok(match decode_tree_page(bytes, limits)? {
33            TreePage::Leaf(entries) => Page::Leaf(entries),
34            TreePage::Internal(children) => Page::Internal(
35                children
36                    .into_iter()
37                    .map(|child| Child {
38                        first: child.first_name,
39                        page: child.page,
40                    })
41                    .collect(),
42            ),
43        })
44    }
45
46    fn decode_shape(
47        bytes: &[u8],
48        limits: DecodeLimits,
49    ) -> Result<DecodedPageShape, CanonicalDecodeError> {
50        tree_page_decode_shape(bytes, limits)
51    }
52
53    fn encode(
54        page: &PageRef<'_, Self>,
55        maximum_items: u32,
56    ) -> Result<Vec<u8>, CanonicalDecodeError> {
57        match page {
58            PageRef::Leaf(entries) => encode_tree_leaf_entries(entries, maximum_items),
59            PageRef::Internal(children) => encode_tree_internal_children(
60                children.iter().map(|child| (&child.first, child.page)),
61                maximum_items,
62            ),
63        }
64    }
65
66    fn page_encoded_length(
67        page: &PageRef<'_, Self>,
68        maximum_items: u32,
69    ) -> Result<usize, CanonicalDecodeError> {
70        let count = match page {
71            PageRef::Leaf(entries) => entries.len(),
72            PageRef::Internal(children) => children.len(),
73        };
74        if u32::try_from(count).unwrap_or(u32::MAX) > maximum_items {
75            return Err(CanonicalDecodeError::LengthOverflow);
76        }
77        let mut bytes = 8_usize + 2 + 1 + 4;
78        match page {
79            PageRef::Leaf(entries) => {
80                for entry in *entries {
81                    bytes = bytes
82                        .checked_add(Self::leaf_item_encoded_length(entry)?)
83                        .ok_or(CanonicalDecodeError::LengthOverflow)?;
84                }
85            }
86            PageRef::Internal(children) => {
87                for child in *children {
88                    bytes = bytes
89                        .checked_add(Self::internal_item_encoded_length(&child.first)?)
90                        .ok_or(CanonicalDecodeError::LengthOverflow)?;
91                }
92            }
93        }
94        Ok(bytes)
95    }
96
97    fn leaf_item_encoded_length(value: &Self::Value) -> Result<usize, CanonicalDecodeError> {
98        value
99            .name
100            .as_bytes()
101            .len()
102            .checked_add(1 + 4 + 16 + 1)
103            .ok_or(CanonicalDecodeError::LengthOverflow)
104    }
105
106    fn internal_item_encoded_length(key: &Self::Key) -> Result<usize, CanonicalDecodeError> {
107        key.as_bytes()
108            .len()
109            .checked_add(1 + 4 + 32)
110            .ok_or(CanonicalDecodeError::LengthOverflow)
111    }
112
113    fn key_nested_bytes(key: &Self::Key) -> u64 {
114        u64::try_from(key.as_bytes().len()).unwrap_or(u64::MAX)
115    }
116
117    fn value_nested_bytes(value: &Self::Value) -> u64 {
118        Self::key_nested_bytes(&value.name)
119    }
120
121    fn try_clone_key(
122        key: &Self::Key,
123        maximum_bytes: u32,
124    ) -> Result<Self::Key, CanonicalDecodeError> {
125        let mut bytes = Vec::new();
126        bytes
127            .try_reserve_exact(key.as_bytes().len())
128            .map_err(|_| CanonicalDecodeError::AllocationFailed)?;
129        bytes.extend_from_slice(key.as_bytes());
130        LogicalName::new(key.encoding(), bytes, maximum_bytes)
131            .map_err(|error| CanonicalDecodeError::Invariant(error.to_string()))
132    }
133
134    fn try_clone_value(
135        value: &Self::Value,
136        maximum_bytes: u32,
137    ) -> Result<Self::Value, CanonicalDecodeError> {
138        Ok(TreeEntry {
139            name: Self::try_clone_key(&value.name, maximum_bytes)?,
140            file_id: value.file_id,
141            kind: value.kind,
142        })
143    }
144}
145
146/// One ordered mutation to a directory name binding.
147#[derive(Clone, Debug, Eq, PartialEq)]
148pub enum TreeMutation {
149    /// Inserts a binding only if the name is absent.
150    Insert(TreeEntry),
151    /// Removes an existing binding, optionally checking its stable file identity.
152    Remove {
153        /// Exact canonical name.
154        name: LogicalName,
155        /// Exact identity precondition, or any existing identity.
156        expected_file_id: Option<FileId>,
157    },
158    /// Replaces one existing binding after checking its identity.
159    Replace {
160        /// Complete replacement entry; its name is unchanged.
161        entry: TreeEntry,
162        /// Exact existing identity.
163        expected_file_id: FileId,
164    },
165}
166
167impl persistent_btree::Mutation<TreeFormat> for TreeMutation {
168    type Error = TreeSemanticError;
169
170    fn key(&self) -> &LogicalName {
171        match self {
172            Self::Insert(entry) | Self::Replace { entry, .. } => &entry.name,
173            Self::Remove { name, .. } => name,
174        }
175    }
176
177    fn changes_cardinality(&self) -> bool {
178        matches!(self, Self::Insert(_) | Self::Remove { .. })
179    }
180
181    fn apply_current(&self, current: &mut Option<TreeEntry>) -> Result<(), Self::Error> {
182        match self {
183            Self::Insert(_) if current.is_some() => Err(TreeSemanticError::AlreadyExists),
184            Self::Insert(entry) => {
185                *current = Some(entry.clone());
186                Ok(())
187            }
188            Self::Remove { .. } | Self::Replace { .. } if current.is_none() => {
189                Err(TreeSemanticError::Missing)
190            }
191            Self::Remove {
192                expected_file_id, ..
193            } => {
194                let existing = current.as_ref().ok_or(TreeSemanticError::Missing)?;
195                if expected_file_id.is_some_and(|expected| existing.file_id != expected) {
196                    return Err(TreeSemanticError::FileIdentityConflict);
197                }
198                *current = None;
199                Ok(())
200            }
201            Self::Replace {
202                entry,
203                expected_file_id,
204            } => {
205                let existing = current.as_ref().ok_or(TreeSemanticError::Missing)?;
206                if existing.file_id != *expected_file_id {
207                    return Err(TreeSemanticError::FileIdentityConflict);
208                }
209                *current = Some(entry.clone());
210                Ok(())
211            }
212        }
213    }
214}
215
216/// New immutable directory root and exact path-copy work.
217#[derive(Clone, Debug, Eq, PartialEq)]
218pub struct TreeMutationReceipt {
219    /// Candidate root. It is not authoritative until its generation is published.
220    pub root: ObjectId,
221    /// Exact authenticated reads, canonical writes, and backend work.
222    pub work: WorkCounters,
223}
224
225/// Sparse tree mutation failure preserving all work and orphan writes.
226pub type TreeMutationFailure = OperationFailure<TreeMutationError>;
227
228/// Applies one ordered mutation batch by path-copying only intersecting pages.
229///
230/// Mutations are stably grouped by name, preserving order for repeated names.
231/// One touched page and each shared ancestor are rewritten at most once.
232/// Untouched child identities are copied verbatim. A failure returns no root;
233/// already-written immutable objects are harmless orphans.
234///
235/// # Errors
236///
237/// Rejects empty/excessive batches, invalid page bounds, failed preconditions,
238/// malformed/cyclic trees, storage errors, or unadmitted work.
239pub fn apply_tree_mutations<S: crate::ImmediateObjectStore>(
240    store: &S,
241    root: ObjectId,
242    mutations: Vec<TreeMutation>,
243    maximum_mutations: u32,
244    limits: DecodeLimits,
245    budget: WorkBudget,
246) -> Result<TreeMutationReceipt, TreeMutationFailure> {
247    let receipt = persistent_btree::apply::<S, TreeFormat, TreeMutation>(
248        store,
249        root,
250        mutations,
251        maximum_mutations,
252        limits,
253        budget,
254    )
255    .map_err(|failure| OperationFailure::new(map_error(failure.error), *failure.work))?;
256    Ok(TreeMutationReceipt {
257        root: receipt.root,
258        work: receipt.work,
259    })
260}
261
262/// Asynchronously applies one ordered sparse directory mutation batch.
263///
264/// Native and browser execution drive the same iterative path-copy machine;
265/// only immutable-object suspension differs.
266///
267/// # Errors
268///
269/// Returns the same semantic, validation, storage, cancellation, and work
270/// failures as [`apply_tree_mutations`].
271pub async fn apply_tree_mutations_async<S: crate::AsyncObjectStore>(
272    store: &S,
273    root: ObjectId,
274    mutations: Vec<TreeMutation>,
275    maximum_mutations: u32,
276    limits: DecodeLimits,
277    budget: WorkBudget,
278    cancellation: &crate::CancellationToken,
279) -> Result<TreeMutationReceipt, TreeMutationFailure> {
280    let receipt = persistent_btree::apply_async::<S, TreeFormat, TreeMutation>(
281        store,
282        root,
283        mutations,
284        maximum_mutations,
285        limits,
286        budget,
287        cancellation,
288    )
289    .await
290    .map_err(|failure| OperationFailure::new(map_error(failure.error), *failure.work))?;
291    Ok(TreeMutationReceipt {
292        root: receipt.root,
293        work: receipt.work,
294    })
295}
296
297fn map_error(error: persistent_btree::Error<TreeSemanticError>) -> TreeMutationError {
298    match error {
299        persistent_btree::Error::Empty => TreeMutationError::Empty,
300        persistent_btree::Error::TooManyMutations => TreeMutationError::TooManyMutations,
301        persistent_btree::Error::WrongRootKind => TreeMutationError::WrongRootKind,
302        persistent_btree::Error::InvalidLimits => TreeMutationError::InvalidLimits,
303        persistent_btree::Error::PageItemTooLarge => TreeMutationError::PageItemTooLarge,
304        persistent_btree::Error::HeightExceeded => TreeMutationError::HeightExceeded,
305        persistent_btree::Error::CycleOrAlias => TreeMutationError::CycleOrAlias,
306        persistent_btree::Error::ChildBoundsMismatch => TreeMutationError::ChildBoundsMismatch,
307        persistent_btree::Error::MutationContract => TreeMutationError::MutationContract,
308        persistent_btree::Error::Allocation(AllocationError::Work(error)) => {
309            TreeMutationError::Work(error)
310        }
311        persistent_btree::Error::AllocationFailed | persistent_btree::Error::Allocation(_) => {
312            TreeMutationError::AllocationFailed
313        }
314        persistent_btree::Error::Semantic(error) => error.into(),
315        persistent_btree::Error::Storage(error) => TreeMutationError::Storage(error),
316        persistent_btree::Error::Decode(error) => TreeMutationError::Decode(error),
317        persistent_btree::Error::Work(error) => TreeMutationError::Work(error),
318    }
319}
320
321#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
322pub(crate) enum TreeSemanticError {
323    #[error("tree mutation name already exists")]
324    AlreadyExists,
325    #[error("tree mutation name is absent")]
326    Missing,
327    #[error("tree mutation file identity precondition failed")]
328    FileIdentityConflict,
329}
330
331/// Persistent directory mutation failures.
332#[derive(Debug, Error)]
333pub enum TreeMutationError {
334    /// Batch contains no mutation.
335    #[error("tree mutation batch is empty")]
336    Empty,
337    /// Batch count is zero-bounded, excessive, or unrepresentable.
338    #[error("tree mutation count exceeds its admitted bound")]
339    TooManyMutations,
340    /// Root object has the wrong class.
341    #[error("tree mutation root is not a tree page")]
342    WrongRootKind,
343    /// Page width/height cannot support a persistent tree.
344    #[error("tree mutation limits are invalid")]
345    InvalidLimits,
346    /// One encoded binding cannot fit under the page byte bound.
347    #[error("tree mutation item exceeds its page byte bound")]
348    PageItemTooLarge,
349    /// Traversal or root growth exceeds the page-height bound.
350    #[error("tree mutation exceeds its admitted height")]
351    HeightExceeded,
352    /// Authenticated page graph cycles or aliases.
353    #[error("tree mutation encountered a cycle or page alias")]
354    CycleOrAlias,
355    /// Parent routing bounds do not match a child page.
356    #[error("tree mutation child bounds mismatch")]
357    ChildBoundsMismatch,
358    /// A private mutation implementation violated plan invariants.
359    #[error("tree mutation violated its physical-plan contract")]
360    MutationContract,
361    /// Bounded scratch allocation could not be satisfied.
362    #[error("tree mutation scratch allocation failed")]
363    AllocationFailed,
364    /// Insert expected an absent name.
365    #[error("tree mutation name already exists")]
366    AlreadyExists,
367    /// Remove/replace expected an existing name.
368    #[error("tree mutation name is absent")]
369    Missing,
370    /// Existing file identity differs from the mutation precondition.
371    #[error("tree mutation file identity precondition failed")]
372    FileIdentityConflict,
373    /// Immutable object storage failed.
374    #[error(transparent)]
375    Storage(#[from] ObjectStoreError),
376    /// Canonical page encoding/decoding failed.
377    #[error(transparent)]
378    Decode(#[from] CanonicalDecodeError),
379    /// Exact work exceeded or overflowed its budget.
380    #[error(transparent)]
381    Work(#[from] WorkError),
382}
383
384impl From<TreeSemanticError> for TreeMutationError {
385    fn from(value: TreeSemanticError) -> Self {
386        match value {
387            TreeSemanticError::AlreadyExists => Self::AlreadyExists,
388            TreeSemanticError::Missing => Self::Missing,
389            TreeSemanticError::FileIdentityConflict => Self::FileIdentityConflict,
390        }
391    }
392}
393
394#[cfg(all(test, feature = "memory"))]
395#[path = "tests/tree_mutation.rs"]
396mod tests;
acyclic_fs/kernel/tree_mutation.rs

acyclic_fs/kernel/
tree_mutation.rs
