aranya_runtime/storage/
mod.rs

1//! Interfaces for graph storage.
2//!
3//! The [`StorageProvider`] and [`Storage`] interfaces enable high-level
4//! actions on the graph. Traversing the graph is made simpler by splitting
5//! its [`Command`]s into [`Segment`]s. Updating the graph is possible using
6//! [`Perspective`]s, which represent a slice of state.
7
8use alloc::{boxed::Box, string::String, vec::Vec};
9use core::{fmt, ops::Deref};
10
11use buggy::{Bug, BugExt as _};
12use serde::{Deserialize, Serialize};
13
14use crate::{Address, CmdId, Command, PolicyId, Prior};
15
16pub mod linear;
17pub mod memory;
18
19/// The maximum size of a serialized message
20pub const MAX_COMMAND_LENGTH: usize = 2048;
21
22aranya_crypto::custom_id! {
23    /// The ID of the graph, taken from initialization.
24    pub struct GraphId;
25}
26
27#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
28pub struct Location {
29    pub segment: usize,
30    pub command: usize,
31}
32
33impl From<(usize, usize)> for Location {
34    fn from((segment, command): (usize, usize)) -> Self {
35        Self::new(segment, command)
36    }
37}
38
39impl AsRef<Self> for Location {
40    fn as_ref(&self) -> &Self {
41        self
42    }
43}
44
45impl Location {
46    pub fn new(segment: usize, command: usize) -> Self {
47        Self { segment, command }
48    }
49
50    /// If this is not the first command in a segment, return a location
51    /// pointing to the previous command.
52    #[must_use]
53    pub fn previous(mut self) -> Option<Self> {
54        if let Some(n) = usize::checked_sub(self.command, 1) {
55            self.command = n;
56            Some(self)
57        } else {
58            None
59        }
60    }
61
62    /// Returns true if other location is in the same segment.
63    pub fn same_segment(self, other: Self) -> bool {
64        self.segment == other.segment
65    }
66}
67
68impl fmt::Display for Location {
69    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
70        write!(f, "{}:{}", self.segment, self.command)
71    }
72}
73
74/// An error returned by [`Storage`] or [`StorageProvider`].
75#[derive(Debug, PartialEq, Eq, thiserror::Error)]
76pub enum StorageError {
77    #[error("storage already exists")]
78    StorageExists,
79    #[error("no such storage")]
80    NoSuchStorage,
81    #[error("segment index {} is out of bounds", .0.segment)]
82    SegmentOutOfBounds(Location),
83    #[error("command index {} is out of bounds in segment {}", .0.command, .0.segment)]
84    CommandOutOfBounds(Location),
85    #[error("IO error")]
86    IoError,
87    #[error("not a merge command")]
88    NotMerge,
89    #[error("command with id {0} not found")]
90    NoSuchId(CmdId),
91    #[error("policy mismatch")]
92    PolicyMismatch,
93    #[error("cannot write an empty perspective")]
94    EmptyPerspective,
95    #[error("segment must be a descendant of the head for commit")]
96    HeadNotAncestor,
97    #[error("command's parents do not match the perspective head")]
98    PerspectiveHeadMismatch,
99    #[error(transparent)]
100    Bug(#[from] Bug),
101}
102
103/// Handle to storage implementations used by the runtime.
104pub trait StorageProvider {
105    type Perspective: Perspective + Revertable;
106    type Segment: Segment;
107    type Storage: Storage<
108            Segment = Self::Segment,
109            Perspective = Self::Perspective,
110            FactIndex = <Self::Segment as Segment>::FactIndex,
111        >;
112
113    /// Create an unrooted perspective, intended for creating a new graph.
114    ///
115    /// # Arguments
116    ///
117    /// * `policy_id` - The policy to associate with the graph.
118    fn new_perspective(&mut self, policy_id: PolicyId) -> Self::Perspective;
119
120    /// Create a new graph.
121    ///
122    /// # Arguments
123    ///
124    /// * `graph` - ID of the graph, taken from the initialization command.
125    /// * `init` - Contains the data necessary to initialize the new graph.
126    fn new_storage(
127        &mut self,
128        init: Self::Perspective,
129    ) -> Result<(GraphId, &mut Self::Storage), StorageError>;
130
131    /// Get an existing graph.
132    ///
133    /// # Arguments
134    ///
135    /// * `graph` - ID of the graph, taken from the initialization command.
136    fn get_storage(&mut self, graph: GraphId) -> Result<&mut Self::Storage, StorageError>;
137
138    /// Remove a graph.
139    ///
140    /// # Arguments
141    ///
142    /// * `graph` - ID of the graph, taken from the initialization command.
143    fn remove_storage(&mut self, graph: GraphId) -> Result<(), StorageError>;
144
145    /// Gets a list of all stored graphs by their graph ID.
146    // TODO(nikki): rewrite this once we can use coroutines/generators?
147    fn list_graph_ids(
148        &mut self,
149    ) -> Result<impl Iterator<Item = Result<GraphId, StorageError>>, StorageError>;
150}
151
152/// Represents the runtime's graph; [`Command`]s in storage have been validated
153/// by an associated policy and committed to state.
154pub trait Storage {
155    type Perspective: Perspective + Revertable;
156    type FactPerspective: FactPerspective;
157    type Segment: Segment<FactIndex = Self::FactIndex>;
158    type FactIndex: FactIndex;
159
160    /// Returns the location of Command with id if it has been stored by
161    /// searching from the head.
162    fn get_location(&self, address: Address) -> Result<Option<Location>, StorageError> {
163        self.get_location_from(self.get_head()?, address)
164    }
165
166    /// Returns the location of Command with id by searching from the given location.
167    fn get_location_from(
168        &self,
169        start: Location,
170        address: Address,
171    ) -> Result<Option<Location>, StorageError> {
172        let mut queue = Vec::new();
173        queue.push(start);
174        'outer: while let Some(loc) = queue.pop() {
175            let head = self.get_segment(loc)?;
176            if address.max_cut > head.longest_max_cut()? {
177                continue;
178            }
179            if let Some(loc) = head.get_by_address(address) {
180                return Ok(Some(loc));
181            }
182            // Assumes skip list is sorted in ascending order.
183            // We always want to skip as close to the root as possible.
184            for (skip, max_cut) in head.skip_list() {
185                if max_cut >= &address.max_cut {
186                    queue.push(*skip);
187                    continue 'outer;
188                }
189            }
190            queue.extend(head.prior());
191        }
192        Ok(None)
193    }
194
195    /// Returns the address of the command at the given location.
196    ///
197    /// By default, this fetches the segment, then the command, then the address.
198    fn get_command_address(&self, location: Location) -> Result<Address, StorageError> {
199        let segment = self.get_segment(location)?;
200        let command = segment
201            .get_command(location)
202            .ok_or(StorageError::CommandOutOfBounds(location))?;
203        let address = command.address()?;
204        Ok(address)
205    }
206
207    /// Returns a linear perspective at the given location.
208    fn get_linear_perspective(&self, parent: Location) -> Result<Self::Perspective, StorageError>;
209
210    /// Returns a fact perspective at the given location, intended for evaluating braids.
211    /// The fact perspective will include the facts of the command at the given location.
212    fn get_fact_perspective(&self, first: Location) -> Result<Self::FactPerspective, StorageError>;
213
214    /// Returns a merge perspective based on the given locations with the braid as prior facts.
215    fn new_merge_perspective(
216        &self,
217        left: Location,
218        right: Location,
219        last_common_ancestor: (Location, usize),
220        policy_id: PolicyId,
221        braid: Self::FactIndex,
222    ) -> Result<Self::Perspective, StorageError>;
223
224    /// Returns the segment at the given location.
225    fn get_segment(&self, location: Location) -> Result<Self::Segment, StorageError>;
226
227    /// Returns the location of head of the graph.
228    fn get_head(&self) -> Result<Location, StorageError>;
229
230    /// Returns the address of the head of the graph.
231    fn get_head_address(&self) -> Result<Address, StorageError> {
232        self.get_command_address(self.get_head()?)
233    }
234
235    /// Sets the given segment as the head of the graph.  Returns an error if
236    /// the current head is not an ancestor of the provided segment.
237    fn commit(&mut self, segment: Self::Segment) -> Result<(), StorageError>;
238
239    /// Writes the given perspective to a segment.
240    fn write(&mut self, perspective: Self::Perspective) -> Result<Self::Segment, StorageError>;
241
242    /// Writes the given fact perspective to a fact index.
243    fn write_facts(
244        &mut self,
245        fact_perspective: Self::FactPerspective,
246    ) -> Result<Self::FactIndex, StorageError>;
247
248    /// Determine whether the given location is an ancestor of the given segment.
249    fn is_ancestor(
250        &self,
251        search_location: Location,
252        segment: &Self::Segment,
253    ) -> Result<bool, StorageError> {
254        let mut queue = Vec::new();
255        queue.extend(segment.prior());
256        let segment = self.get_segment(search_location)?;
257        let address = segment
258            .get_command(search_location)
259            .assume("location must exist")?
260            .address()?;
261        'outer: while let Some(location) = queue.pop() {
262            if location.segment == search_location.segment
263                && location.command >= search_location.command
264            {
265                return Ok(true);
266            }
267            let segment = self.get_segment(location)?;
268            if address.max_cut > segment.longest_max_cut()? {
269                continue;
270            }
271            for (skip, max_cut) in segment.skip_list() {
272                if max_cut >= &address.max_cut {
273                    queue.push(*skip);
274                    continue 'outer;
275                }
276            }
277            queue.extend(segment.prior());
278        }
279        Ok(false)
280    }
281}
282
283type MaxCut = usize;
284
285/// A segment is a nonempty sequence of commands persisted to storage.
286///
287/// A segment can be one of three types. This might be encoded in a future version of the API.
288/// * init   - This segment is the first segment of the graph and begins with an init command.
289/// * linear - This segment has a single prior command and is simply a sequence of linear commands.
290/// * merge  - This segment merges two other segments and thus begins with a merge command. A merge
291///   segment has a braid as it's prior facts.
292///
293/// Each command past the first must have the parent of the previous command in the segment.
294pub trait Segment {
295    type FactIndex: FactIndex;
296    type Command<'a>: Command
297    where
298        Self: 'a;
299
300    /// Returns the head of the segment.
301    fn head(&self) -> Result<Self::Command<'_>, StorageError>;
302
303    /// Returns the first Command in the segment.
304    fn first(&self) -> Self::Command<'_>;
305
306    /// Returns the location of the head of the segment.
307    fn head_location(&self) -> Location;
308
309    /// Returns the location of the first command.
310    fn first_location(&self) -> Location;
311
312    /// Returns true if the segment contains the location.
313    fn contains(&self, location: Location) -> bool;
314
315    /// Returns the id for the policy used for this segment.
316    fn policy(&self) -> PolicyId;
317
318    /// Returns the prior segments for this segment.
319    fn prior(&self) -> Prior<Location>;
320
321    /// Returns the command at the given location.
322    fn get_command(&self, location: Location) -> Option<Self::Command<'_>>;
323
324    /// Returns the location of the command with the given address from within this segment.
325    fn get_by_address(&self, address: Address) -> Option<Location>;
326
327    /// Returns an iterator of commands starting at the given location.
328    fn get_from(&self, location: Location) -> Vec<Self::Command<'_>>;
329
330    /// Get the fact index associated with this segment.
331    fn facts(&self) -> Result<Self::FactIndex, StorageError>;
332
333    fn contains_any<I>(&self, locations: I) -> bool
334    where
335        I: IntoIterator,
336        I::Item: AsRef<Location>,
337    {
338        locations
339            .into_iter()
340            .any(|loc| self.contains(*loc.as_ref()))
341    }
342
343    /// The shortest max cut for this segment.
344    ///
345    /// This will always the max cut of the first command in the segment.
346    fn shortest_max_cut(&self) -> MaxCut;
347
348    /// The longest max cut for this segment.
349    ///
350    /// This will always be the max cut of the last command in the segment.
351    fn longest_max_cut(&self) -> Result<MaxCut, StorageError>;
352
353    /// The skip list is a series of locations that can be safely jumped to
354    /// when searching for a location. As long as the max cut of the location
355    /// you're jumping to is greater than or equal to the location you're
356    /// searching for you can jump to it and be guaranteed not to miss
357    /// the location you're searching for.
358    ///
359    /// For merge commands the last location in the skip list is the least
360    /// common ancestor.
361    fn skip_list(&self) -> &[(Location, MaxCut)];
362}
363
364/// An index of facts in storage.
365pub trait FactIndex: Query {}
366
367/// A perspective is essentially a mutable, in-memory version of a [`Segment`],
368/// with the same three types.
369pub trait Perspective: FactPerspective {
370    /// Returns the id for the policy used for this perspective.
371    fn policy(&self) -> PolicyId;
372
373    /// Adds the given command to the head of the perspective. The command's
374    /// parent must be the head of the perspective.
375    fn add_command(&mut self, command: &impl Command) -> Result<usize, StorageError>;
376
377    /// Returns true if the perspective contains a command with the given ID.
378    fn includes(&self, id: CmdId) -> bool;
379
380    /// Returns the head address in the perspective, if it exists
381    fn head_address(&self) -> Result<Prior<Address>, Bug>;
382}
383
384/// A fact perspective is essentially a mutable, in-memory version of a [`FactIndex`].
385pub trait FactPerspective: QueryMut {}
386
387/// A revertable perspective can make checkpoints and be reverted such that the
388/// state of the perspective matches that when the checkpoint was created.
389pub trait Revertable {
390    /// Create a checkpoint which can be used to revert the perspective.
391    fn checkpoint(&self) -> Checkpoint;
392
393    /// Revert the perspective to the state it was at when the checkpoint was created.
394    fn revert(&mut self, checkpoint: Checkpoint) -> Result<(), Bug>;
395}
396
397/// A checkpoint used to revert perspectives.
398pub struct Checkpoint {
399    /// An index interpreted by a given `Revertable` implementation to revert to a prior point.
400    pub index: usize,
401}
402
403/// Can be queried to look up facts.
404///
405/// Facts are labeled by a name, which are generally a bounded set of human-readable strings determined in advance.
406///
407/// Within a name, facts are an association of compound keys to values. The facts are keyed by a compound key
408/// `(k_1, k_2, ..., k_n)`, where each `k` is a sequence of bytes. The fact value is also a sequence of bytes.
409pub trait Query {
410    /// Look up a named fact by an exact match of the compound key.
411    fn query(&self, name: &str, keys: &[Box<[u8]>]) -> Result<Option<Box<[u8]>>, StorageError>;
412
413    /// Iterator for [`Query::query_prefix`].
414    type QueryIterator: Iterator<Item = Result<Fact, StorageError>>;
415
416    /// Look up all named facts that begin with the prefix of keys, in sorted key order.
417    ///
418    /// The `prefix` is a partial compound key `(k_1, k_2, ..., k_n)`, where each `k` is a sequence of bytes.
419    /// This returns all facts under the name with keys such that `prefix` is equal to a prefix of the fact's keys.
420    fn query_prefix(
421        &self,
422        name: &str,
423        prefix: &[Box<[u8]>],
424    ) -> Result<Self::QueryIterator, StorageError>;
425}
426
427/// A fact with a key and value.
428#[derive(Debug, PartialEq, Eq)]
429pub struct Fact {
430    /// The sequence of keys.
431    pub key: Keys,
432    /// The bytes of the value.
433    pub value: Box<[u8]>,
434}
435
436/// Can mutate facts by inserting and deleting them.
437///
438/// See [`Query`] for details on the nature of facts.
439pub trait QueryMut: Query {
440    /// Insert a fact labeled by a name, with a given compound key and a value.
441    ///
442    /// This fact can later be looked up by [`Query`] methods, using the name and keys.
443    fn insert(&mut self, name: String, keys: Keys, value: Box<[u8]>);
444
445    /// Delete any fact associated to the compound key, under the given name.
446    fn delete(&mut self, name: String, keys: Keys);
447}
448
449/// A sequence of byte-based keys, used for facts.
450#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
451pub struct Keys(Box<[Box<[u8]>]>);
452
453impl Deref for Keys {
454    type Target = [Box<[u8]>];
455    fn deref(&self) -> &[Box<[u8]>] {
456        self.0.as_ref()
457    }
458}
459
460impl AsRef<[Box<[u8]>]> for Keys {
461    fn as_ref(&self) -> &[Box<[u8]>] {
462        self.0.as_ref()
463    }
464}
465
466impl core::borrow::Borrow<[Box<[u8]>]> for Keys {
467    fn borrow(&self) -> &[Box<[u8]>] {
468        self.0.as_ref()
469    }
470}
471
472impl From<&[&[u8]]> for Keys {
473    fn from(value: &[&[u8]]) -> Self {
474        value.iter().copied().collect()
475    }
476}
477
478impl Keys {
479    fn starts_with(&self, prefix: &[Box<[u8]>]) -> bool {
480        self.as_ref().starts_with(prefix)
481    }
482}
483
484impl<B: Into<Box<[u8]>>> FromIterator<B> for Keys {
485    fn from_iter<T: IntoIterator<Item = B>>(iter: T) -> Self {
486        Self(iter.into_iter().map(Into::into).collect())
487    }
488}
489
490// TODO: Fix and enable
491// #[cfg(test)]
492// mod tests;
aranya_runtime/storage/mod.rs

aranya_runtime/storage/
mod.rs
