acyclic_fs/kernel/
file_table_mutation.rs

1//! Sparse persistent path-independent file-table mutation.
2
3use super::allocation::AllocationError;
4use super::codec::DecodedPageShape;
5use super::file_table::{
6    encode_file_table_internal_children, encode_file_table_leaf_records,
7    file_record_encoded_length, file_table_page_decode_shape,
8};
9use super::persistent_btree::{self, Child, Format, Page, PageRef};
10use super::{
11    CanonicalDecodeError, DecodeLimits, FileRecord, FileTablePage, decode_file_table_page,
12};
13use crate::foundation::FileId;
14use crate::performance::{OperationFailure, WorkBudget, WorkCounters, WorkError};
15use crate::storage::{ObjectId, ObjectKind, ObjectStoreError};
16use thiserror::Error;
17
18pub(crate) struct FileTableFormat;
19
20impl Format for FileTableFormat {
21    type Key = FileId;
22    type Value = FileRecord;
23
24    fn kind() -> ObjectKind {
25        ObjectKind::FileTablePage
26    }
27
28    fn key(value: &Self::Value) -> &Self::Key {
29        &value.file_id
30    }
31
32    fn decode(bytes: &[u8], limits: DecodeLimits) -> Result<Page<Self>, CanonicalDecodeError> {
33        Ok(match decode_file_table_page(bytes, limits)? {
34            FileTablePage::Leaf(records) => Page::Leaf(records),
35            FileTablePage::Internal(children) => Page::Internal(
36                children
37                    .into_iter()
38                    .map(|child| Child {
39                        first: child.first_file_id,
40                        page: child.page,
41                    })
42                    .collect(),
43            ),
44        })
45    }
46
47    fn decode_shape(
48        bytes: &[u8],
49        limits: DecodeLimits,
50    ) -> Result<DecodedPageShape, CanonicalDecodeError> {
51        file_table_page_decode_shape(bytes, limits)
52    }
53
54    fn encode(
55        page: &PageRef<'_, Self>,
56        maximum_items: u32,
57    ) -> Result<Vec<u8>, CanonicalDecodeError> {
58        match page {
59            PageRef::Leaf(records) => encode_file_table_leaf_records(records, maximum_items),
60            PageRef::Internal(children) => encode_file_table_internal_children(
61                children.iter().map(|child| (child.first, child.page)),
62                maximum_items,
63            ),
64        }
65    }
66
67    fn page_encoded_length(
68        page: &PageRef<'_, Self>,
69        maximum_items: u32,
70    ) -> Result<usize, CanonicalDecodeError> {
71        let count = match page {
72            PageRef::Leaf(records) => records.len(),
73            PageRef::Internal(children) => children.len(),
74        };
75        if u32::try_from(count).unwrap_or(u32::MAX) > maximum_items {
76            return Err(CanonicalDecodeError::LengthOverflow);
77        }
78        let mut bytes = 8_usize + 2 + 1 + 4;
79        match page {
80            PageRef::Leaf(records) => {
81                for record in *records {
82                    bytes = bytes
83                        .checked_add(Self::leaf_item_encoded_length(record)?)
84                        .ok_or(CanonicalDecodeError::LengthOverflow)?;
85                }
86            }
87            PageRef::Internal(children) => {
88                for child in *children {
89                    bytes = bytes
90                        .checked_add(Self::internal_item_encoded_length(&child.first)?)
91                        .ok_or(CanonicalDecodeError::LengthOverflow)?;
92                }
93            }
94        }
95        Ok(bytes)
96    }
97
98    fn leaf_item_encoded_length(value: &Self::Value) -> Result<usize, CanonicalDecodeError> {
99        file_record_encoded_length(*value)
100    }
101
102    fn internal_item_encoded_length(_key: &Self::Key) -> Result<usize, CanonicalDecodeError> {
103        Ok(16 + 32)
104    }
105
106    fn key_nested_bytes(_key: &Self::Key) -> u64 {
107        0
108    }
109
110    fn value_nested_bytes(_value: &Self::Value) -> u64 {
111        0
112    }
113
114    fn try_clone_key(
115        key: &Self::Key,
116        _maximum_bytes: u32,
117    ) -> Result<Self::Key, CanonicalDecodeError> {
118        Ok(*key)
119    }
120
121    fn try_clone_value(
122        value: &Self::Value,
123        _maximum_bytes: u32,
124    ) -> Result<Self::Value, CanonicalDecodeError> {
125        Ok(*value)
126    }
127}
128
129/// One ordered path-independent record mutation.
130#[derive(Clone, Copy, Debug, Eq, PartialEq)]
131pub enum FileTableMutation {
132    /// Inserts a record only if its identity is absent.
133    Insert(FileRecord),
134    /// Removes an existing record with an optional complete-state precondition.
135    Remove {
136        /// Stable file identity.
137        file_id: FileId,
138        /// Exact expected record, or any record with this identity.
139        expected: Option<FileRecord>,
140    },
141    /// Replaces a record after checking its complete prior state.
142    Replace {
143        /// Exact prior record.
144        expected: FileRecord,
145        /// Complete replacement with the same stable identity.
146        replacement: FileRecord,
147    },
148}
149
150impl FileTableMutation {
151    fn validate(self) -> Result<(), FileTableSemanticError> {
152        match self {
153            Self::Insert(record) => record
154                .validate()
155                .map_err(|_| FileTableSemanticError::InvalidRecord),
156            Self::Remove {
157                file_id,
158                expected: Some(expected),
159            } => {
160                expected
161                    .validate()
162                    .map_err(|_| FileTableSemanticError::InvalidRecord)?;
163                if expected.file_id != file_id {
164                    return Err(FileTableSemanticError::IdentityMismatch);
165                }
166                Ok(())
167            }
168            Self::Replace {
169                expected,
170                replacement,
171            } => {
172                expected
173                    .validate()
174                    .map_err(|_| FileTableSemanticError::InvalidRecord)?;
175                replacement
176                    .validate()
177                    .map_err(|_| FileTableSemanticError::InvalidRecord)?;
178                if expected.file_id != replacement.file_id {
179                    return Err(FileTableSemanticError::IdentityMismatch);
180                }
181                Ok(())
182            }
183            Self::Remove { expected: None, .. } => Ok(()),
184        }
185    }
186}
187
188impl persistent_btree::Mutation<FileTableFormat> for FileTableMutation {
189    type Error = FileTableSemanticError;
190
191    fn key(&self) -> &FileId {
192        match self {
193            Self::Insert(record) => &record.file_id,
194            Self::Remove { file_id, .. } => file_id,
195            Self::Replace { replacement, .. } => &replacement.file_id,
196        }
197    }
198
199    fn changes_cardinality(&self) -> bool {
200        matches!(self, Self::Insert(_) | Self::Remove { .. })
201    }
202
203    fn apply_current(&self, current: &mut Option<FileRecord>) -> Result<(), Self::Error> {
204        match self {
205            Self::Insert(_) if current.is_some() => Err(FileTableSemanticError::AlreadyExists),
206            Self::Insert(record) => {
207                *current = Some(*record);
208                Ok(())
209            }
210            Self::Remove { .. } | Self::Replace { .. } if current.is_none() => {
211                Err(FileTableSemanticError::Missing)
212            }
213            Self::Remove { expected, .. } => {
214                let existing = current.ok_or(FileTableSemanticError::Missing)?;
215                if expected.is_some_and(|value| existing != value) {
216                    return Err(FileTableSemanticError::StateConflict);
217                }
218                *current = None;
219                Ok(())
220            }
221            Self::Replace {
222                expected,
223                replacement,
224            } => {
225                let existing = current.ok_or(FileTableSemanticError::Missing)?;
226                if existing != *expected {
227                    return Err(FileTableSemanticError::StateConflict);
228                }
229                *current = Some(*replacement);
230                Ok(())
231            }
232        }
233    }
234}
235
236/// Candidate file-table root and exact sparse path-copy work.
237#[derive(Clone, Copy, Debug, Eq, PartialEq)]
238pub struct FileTableMutationReceipt {
239    /// Candidate immutable file-table root.
240    pub root: ObjectId,
241    /// Exact work; no authority publication is included.
242    pub work: WorkCounters,
243}
244
245/// File-table mutation failure retaining all work and possible orphan writes.
246pub type FileTableMutationFailure = OperationFailure<FileTableMutationError>;
247
248/// Applies a bounded ordered file-table mutation batch.
249///
250/// # Errors
251///
252/// Rejects malformed records/preconditions before backend access, then fails
253/// closed on semantic conflicts, authenticated routing errors, storage failure,
254/// or work-budget exhaustion.
255pub fn apply_file_table_mutations<S: crate::ImmediateObjectStore>(
256    store: &S,
257    root: ObjectId,
258    mutations: Vec<FileTableMutation>,
259    maximum_mutations: u32,
260    limits: DecodeLimits,
261    budget: WorkBudget,
262) -> Result<FileTableMutationReceipt, FileTableMutationFailure> {
263    for mutation in &mutations {
264        mutation
265            .validate()
266            .map_err(|error| OperationFailure::before_work(error.into()))?;
267    }
268    let receipt = persistent_btree::apply::<S, FileTableFormat, FileTableMutation>(
269        store,
270        root,
271        mutations,
272        maximum_mutations,
273        limits,
274        budget,
275    )
276    .map_err(|failure| OperationFailure::new(map_error(failure.error), *failure.work))?;
277    Ok(FileTableMutationReceipt {
278        root: receipt.root,
279        work: receipt.work,
280    })
281}
282
283/// Asynchronously applies one ordered sparse file-table mutation batch.
284///
285/// This drives the same iterative persistent B+tree machine as the native
286/// synchronous API.
287///
288/// # Errors
289///
290/// Returns the same semantic, validation, storage, cancellation, and work
291/// failures as [`apply_file_table_mutations`].
292pub async fn apply_file_table_mutations_async<S: crate::AsyncObjectStore>(
293    store: &S,
294    root: ObjectId,
295    mutations: Vec<FileTableMutation>,
296    maximum_mutations: u32,
297    limits: DecodeLimits,
298    budget: WorkBudget,
299    cancellation: &crate::CancellationToken,
300) -> Result<FileTableMutationReceipt, FileTableMutationFailure> {
301    let receipt = persistent_btree::apply_async::<S, FileTableFormat, FileTableMutation>(
302        store,
303        root,
304        mutations,
305        maximum_mutations,
306        limits,
307        budget,
308        cancellation,
309    )
310    .await
311    .map_err(|failure| OperationFailure::new(map_error(failure.error), *failure.work))?;
312    Ok(FileTableMutationReceipt {
313        root: receipt.root,
314        work: receipt.work,
315    })
316}
317
318fn map_error(error: persistent_btree::Error<FileTableSemanticError>) -> FileTableMutationError {
319    match error {
320        persistent_btree::Error::Empty => FileTableMutationError::Empty,
321        persistent_btree::Error::TooManyMutations => FileTableMutationError::TooManyMutations,
322        persistent_btree::Error::WrongRootKind => FileTableMutationError::WrongRootKind,
323        persistent_btree::Error::InvalidLimits => FileTableMutationError::InvalidLimits,
324        persistent_btree::Error::PageItemTooLarge => FileTableMutationError::PageItemTooLarge,
325        persistent_btree::Error::HeightExceeded => FileTableMutationError::HeightExceeded,
326        persistent_btree::Error::CycleOrAlias => FileTableMutationError::CycleOrAlias,
327        persistent_btree::Error::ChildBoundsMismatch => FileTableMutationError::ChildBoundsMismatch,
328        persistent_btree::Error::MutationContract => FileTableMutationError::MutationContract,
329        persistent_btree::Error::Allocation(AllocationError::Work(error)) => {
330            FileTableMutationError::Work(error)
331        }
332        persistent_btree::Error::AllocationFailed | persistent_btree::Error::Allocation(_) => {
333            FileTableMutationError::AllocationFailed
334        }
335        persistent_btree::Error::Semantic(error) => error.into(),
336        persistent_btree::Error::Storage(error) => FileTableMutationError::Storage(error),
337        persistent_btree::Error::Decode(error) => FileTableMutationError::Decode(error),
338        persistent_btree::Error::Work(error) => FileTableMutationError::Work(error),
339    }
340}
341
342/// File-record mutation semantic failures.
343#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
344pub enum FileTableSemanticError {
345    /// Record violates canonical kind/link/payload invariants.
346    #[error("file-table mutation record is invalid")]
347    InvalidRecord,
348    /// Mutation precondition and replacement use different stable identities.
349    #[error("file-table mutation identities differ")]
350    IdentityMismatch,
351    /// Insert expected an absent file identity.
352    #[error("file-table record already exists")]
353    AlreadyExists,
354    /// Remove/replace expected an existing file identity.
355    #[error("file-table record is missing")]
356    Missing,
357    /// Existing complete record differs from the mutation precondition.
358    #[error("file-table record state precondition failed")]
359    StateConflict,
360}
361
362/// Persistent file-table path-copy failures.
363#[derive(Debug, Error)]
364pub enum FileTableMutationError {
365    /// Batch contains no mutations.
366    #[error("file-table mutation batch is empty")]
367    Empty,
368    /// Batch exceeds its bound.
369    #[error("file-table mutation count exceeds its bound")]
370    TooManyMutations,
371    /// Root has the wrong object class.
372    #[error("file-table mutation root has the wrong kind")]
373    WrongRootKind,
374    /// Page width/height cannot support mutation.
375    #[error("file-table mutation limits are invalid")]
376    InvalidLimits,
377    /// One encoded file record cannot fit under the page byte bound.
378    #[error("file-table mutation item exceeds its page byte bound")]
379    PageItemTooLarge,
380    /// Traversal or root growth exceeds the height bound.
381    #[error("file-table mutation exceeds its height bound")]
382    HeightExceeded,
383    /// Authenticated graph cycles or aliases.
384    #[error("file-table mutation encountered a cycle or alias")]
385    CycleOrAlias,
386    /// Parent and child routing bounds differ.
387    #[error("file-table child bounds mismatch")]
388    ChildBoundsMismatch,
389    /// A private mutation implementation violated plan invariants.
390    #[error("file-table mutation violated its physical-plan contract")]
391    MutationContract,
392    /// Bounded scratch allocation could not be satisfied.
393    #[error("file-table mutation scratch allocation failed")]
394    AllocationFailed,
395    /// Record violates canonical invariants.
396    #[error("file-table mutation record is invalid")]
397    InvalidRecord,
398    /// Mutation identities differ.
399    #[error("file-table mutation identities differ")]
400    IdentityMismatch,
401    /// Insert found an existing identity.
402    #[error("file-table record already exists")]
403    AlreadyExists,
404    /// Remove/replace found no identity.
405    #[error("file-table record is missing")]
406    Missing,
407    /// Complete-state precondition failed.
408    #[error("file-table record state precondition failed")]
409    StateConflict,
410    /// Immutable object storage failed.
411    #[error(transparent)]
412    Storage(#[from] ObjectStoreError),
413    /// Canonical encoding/decoding failed.
414    #[error(transparent)]
415    Decode(#[from] CanonicalDecodeError),
416    /// Exact work exceeded or overflowed its budget.
417    #[error(transparent)]
418    Work(#[from] WorkError),
419}
420
421impl From<FileTableSemanticError> for FileTableMutationError {
422    fn from(value: FileTableSemanticError) -> Self {
423        match value {
424            FileTableSemanticError::InvalidRecord => Self::InvalidRecord,
425            FileTableSemanticError::IdentityMismatch => Self::IdentityMismatch,
426            FileTableSemanticError::AlreadyExists => Self::AlreadyExists,
427            FileTableSemanticError::Missing => Self::Missing,
428            FileTableSemanticError::StateConflict => Self::StateConflict,
429        }
430    }
431}
432
433#[cfg(all(test, feature = "memory"))]
434#[path = "tests/file_table_mutation.rs"]
435mod tests;
acyclic_fs/kernel/file_table_mutation.rs

acyclic_fs/kernel/
file_table_mutation.rs
