essential_types/
predicate.rs

1//! # Predicates
2//! Types needed to represent a predicate.
3
4use crate::{serde::bytecode, ContentAddress};
5pub use encode::{PredicateDecodeError, PredicateEncodeError};
6use serde::{Deserialize, Serialize};
7
8#[cfg(feature = "schema")]
9use schemars::JsonSchema;
10
11pub mod encode;
12
13/// The state a program has access to.
14#[derive(
15    Debug, Default, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize,
16)]
17#[repr(u8)]
18#[cfg_attr(feature = "schema", derive(JsonSchema))]
19pub enum Reads {
20    /// State prior to mutations.
21    #[default]
22    Pre = 0,
23    /// State post mutations.
24    Post,
25}
26
27/// A node in the graph.
28#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
29#[cfg_attr(feature = "schema", derive(JsonSchema))]
30pub struct Node {
31    /// The start of relevant edges to this node in the edge list of the graph.
32    ///
33    /// Specifying [`Edge::MAX`] indicates that this node is a leaf.
34    pub edge_start: Edge,
35    /// The content address of the [`Program`] that this node executes.
36    pub program_address: ContentAddress,
37    /// Which type of state this program has access to.
38    pub reads: Reads,
39}
40
41/// An edge in the graph.
42pub type Edge = u16;
43
44/// A program dependency graph.
45#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
46#[cfg_attr(feature = "schema", derive(JsonSchema))]
47pub struct Predicate {
48    /// Programs in the graph.
49    pub nodes: Vec<Node>,
50    /// Dependencies between programs in the graph.
51    ///
52    /// Edges are directed.
53    /// The edge from `A` to `B` indicates that `B` depends on `A`, i.e., `B` is a child of `A`.
54    pub edges: Vec<Edge>,
55}
56
57/// A program to be executed.
58#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
59pub struct Program(
60    #[serde(
61        serialize_with = "bytecode::serialize",
62        deserialize_with = "bytecode::deserialize"
63    )]
64    pub Vec<u8>,
65);
66
67impl Predicate {
68    /// Maximum number of nodes in a predicate.
69    pub const MAX_NODES: u16 = 1000;
70    /// Maximum number of edges in a predicate.
71    pub const MAX_EDGES: u16 = 1000;
72
73    /// Encode the predicate into a bytes iterator.
74    pub fn encode(&self) -> Result<impl Iterator<Item = u8> + '_, PredicateEncodeError> {
75        encode::encode_predicate(self)
76    }
77
78    /// The size of the encoded predicate in bytes.
79    pub fn encoded_size(&self) -> usize {
80        encode::predicate_encoded_size(self)
81    }
82
83    /// Decode a predicate from bytes.
84    pub fn decode(bytes: &[u8]) -> Result<Self, PredicateDecodeError> {
85        encode::decode_predicate(bytes)
86    }
87
88    /// The slice of edges associated with the node at the given index.
89    ///
90    /// Returns `None` in the case that the given node index is out of bound, or if any of the
91    /// node's edges are out of bounds of the predicate's `edges` slice.
92    ///
93    /// If the node is a leaf, returns an empty slice.
94    pub fn node_edges(&self, node_ix: usize) -> Option<&[Edge]> {
95        let node = self.nodes.get(node_ix)?;
96        if node.edge_start == Edge::MAX {
97            return Some(&[]);
98        }
99        let e_start = usize::from(node.edge_start);
100        let next_node_ix = node_ix.saturating_add(1);
101        let e_end = match self.nodes.get(next_node_ix) {
102            // If the next node isn't a leaf, use its `edge_start` as our `end`.
103            Some(next) if next.edge_start != Edge::MAX => usize::from(next.edge_start),
104            // If the next node is a leaf, or there is no next node, the `end` is `edges.len()`.
105            Some(_) | None => self.edges.len(),
106        };
107        let edges = self.edges.get(e_start..e_end)?;
108        Some(edges)
109    }
110}
111
112impl Program {
113    /// Maximum size of a program in bytes.
114    pub const MAX_SIZE: u16 = 10_000;
115}
essential_types/predicate.rs

essential_types/
predicate.rs
