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

aranya_runtime/storage/
mod.rs
