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

essential_types/
predicate.rs
