acyclic_fs/kernel/
list.rs

1//! Bounded authenticated directory pagination without prefix enumeration.
2
3use super::persistent_pagination;
4use super::tree_mutation::TreeFormat;
5use super::{CanonicalDecodeError, DecodeLimits, LogicalName, TreeEntry};
6use crate::async_storage::AsyncObjectStore;
7use crate::cancellation::CancellationToken;
8use crate::performance::{OperationFailure, WorkBudget, WorkCounters, WorkError};
9use crate::speculation::{ResidencyHint, ResidencyReason};
10use crate::storage::{ObjectId, ObjectStoreError};
11use thiserror::Error;
12
13/// One authenticated bounded directory page.
14#[derive(Clone, Debug, Eq, PartialEq)]
15pub struct DirectoryPage {
16    /// Entries strictly after the supplied cursor.
17    pub entries: Vec<TreeEntry>,
18    /// Whether at least one additional entry exists.
19    pub has_more: bool,
20    /// Exact unvisited successor object, when the authenticated traversal
21    /// exposed one without widening the requested listing.
22    pub next_residency: Option<ResidencyHint>,
23    /// Exact backend, traversal, copy, and logical-allocation work.
24    pub work: WorkCounters,
25}
26
27/// Returns one bounded ordered directory page and an exact continuation fact.
28///
29/// The shared persistent-tree paginator reads only the cursor frontier and
30/// enough successors to prove `maximum_entries + 1`.
31///
32/// # Errors
33///
34/// Fails closed on invalid bounds, malformed routing, cycles, storage failure,
35/// or work outside the admitted budget.
36pub fn list_tree_entries<S: crate::ImmediateObjectStore>(
37    store: &S,
38    root: ObjectId,
39    after: Option<&LogicalName>,
40    maximum_entries: u32,
41    limits: DecodeLimits,
42    budget: WorkBudget,
43) -> Result<DirectoryPage, DirectoryReadFailure> {
44    persistent_pagination::paginate::<S, TreeFormat>(
45        store,
46        root,
47        after,
48        maximum_entries,
49        limits,
50        budget,
51    )
52    .map(to_page)
53    .map_err(map_failure)
54}
55
56/// Asynchronously executes the same cursor machine as [`list_tree_entries`].
57///
58/// # Errors
59///
60/// Returns the same typed failures, including cancellation before every
61/// backend boundary.
62pub async fn list_tree_entries_async<S: AsyncObjectStore>(
63    store: &S,
64    root: ObjectId,
65    after: Option<&LogicalName>,
66    maximum_entries: u32,
67    limits: DecodeLimits,
68    budget: WorkBudget,
69    cancellation: &CancellationToken,
70) -> Result<DirectoryPage, DirectoryReadFailure> {
71    persistent_pagination::paginate_async::<S, TreeFormat>(
72        store,
73        root,
74        after,
75        maximum_entries,
76        limits,
77        budget,
78        cancellation,
79    )
80    .await
81    .map(to_page)
82    .map_err(map_failure)
83}
84
85pub(crate) async fn list_tree_entries_at_or_after_async<S: AsyncObjectStore>(
86    store: &S,
87    root: ObjectId,
88    at: &LogicalName,
89    maximum_entries: u32,
90    limits: DecodeLimits,
91    budget: WorkBudget,
92    cancellation: &CancellationToken,
93) -> Result<DirectoryPage, DirectoryReadFailure> {
94    persistent_pagination::paginate_async_at_or_after::<S, TreeFormat>(
95        store,
96        root,
97        at,
98        maximum_entries,
99        limits,
100        budget,
101        cancellation,
102    )
103    .await
104    .map(to_page)
105    .map_err(map_failure)
106}
107
108fn to_page(receipt: persistent_pagination::Receipt<TreeEntry>) -> DirectoryPage {
109    DirectoryPage {
110        entries: receipt.values,
111        has_more: receipt.has_more,
112        next_residency: receipt.next_request.map(|request| ResidencyHint {
113            request,
114            reason: ResidencyReason::DirectorySuccessor,
115        }),
116        work: receipt.work,
117    }
118}
119
120/// Bounded directory-read failure retaining exact spent work.
121pub type DirectoryReadFailure = OperationFailure<DirectoryReadError>;
122
123fn map_failure(failure: persistent_pagination::Failure) -> DirectoryReadFailure {
124    OperationFailure::new(map_error(failure.error), *failure.work)
125}
126
127fn map_error(error: persistent_pagination::Error) -> DirectoryReadError {
128    match error {
129        persistent_pagination::Error::Cancelled => DirectoryReadError::Cancelled,
130        persistent_pagination::Error::ZeroLimit => DirectoryReadError::ZeroLimit,
131        persistent_pagination::Error::LimitOverflow => DirectoryReadError::LimitOverflow,
132        persistent_pagination::Error::WrongRootKind => DirectoryReadError::WrongRootKind,
133        persistent_pagination::Error::InvalidLimits => DirectoryReadError::InvalidLimits,
134        persistent_pagination::Error::HeightExceeded => DirectoryReadError::HeightExceeded,
135        persistent_pagination::Error::CycleOrAlias => DirectoryReadError::Cycle,
136        persistent_pagination::Error::ChildBoundsMismatch => {
137            DirectoryReadError::ChildBoundsMismatch
138        }
139        persistent_pagination::Error::TraversalState => DirectoryReadError::TraversalState,
140        persistent_pagination::Error::AllocationFailed => DirectoryReadError::AllocationFailed,
141        persistent_pagination::Error::Storage(error) => error.into(),
142        persistent_pagination::Error::Decode(error) => error.into(),
143        persistent_pagination::Error::Work(error) => error.into(),
144    }
145}
146
147/// Authenticated bounded directory-read failures.
148#[derive(Debug, Error)]
149pub enum DirectoryReadError {
150    /// Cooperative cancellation occurred before the next storage boundary.
151    #[error("directory listing was cancelled")]
152    Cancelled,
153    /// The private driver attempted an impossible transition.
154    #[error("directory listing transition state is invalid")]
155    TraversalState,
156    /// Page bound must be positive.
157    #[error("directory page limit must be non-zero")]
158    ZeroLimit,
159    /// Page-bound allocation overflowed this target.
160    #[error("directory page limit cannot be represented")]
161    LimitOverflow,
162    /// Root is not a tree page.
163    #[error("directory root is not a tree page")]
164    WrongRootKind,
165    /// Decode/traversal limits are internally inconsistent.
166    #[error("directory listing limits are invalid")]
167    InvalidLimits,
168    /// Traversal exceeded the admitted height.
169    #[error("directory tree exceeds its admitted height")]
170    HeightExceeded,
171    /// Child graph references an ancestor or aliases a traversed page.
172    #[error("directory tree contains a cycle or alias")]
173    Cycle,
174    /// Parent routing bounds disagree with a child page.
175    #[error("directory child bounds do not match its page")]
176    ChildBoundsMismatch,
177    /// A bounded scratch allocation could not be represented or reserved.
178    #[error("directory listing allocation failed")]
179    AllocationFailed,
180    /// Immutable object backend failed.
181    #[error(transparent)]
182    Storage(#[from] ObjectStoreError),
183    /// Canonical tree page failed decoding.
184    #[error(transparent)]
185    Decode(#[from] CanonicalDecodeError),
186    /// Exact work exceeded or overflowed its budget.
187    #[error(transparent)]
188    Work(#[from] WorkError),
189}
190
191#[cfg(all(test, feature = "memory"))]
192#[path = "tests/list.rs"]
193mod tests;
acyclic_fs/kernel/list.rs

acyclic_fs/kernel/
list.rs
