weavatrix_graph/payload/stable/
core.rs

1use super::adjacency::{EdgeKeys, NONE_SLOT};
2use crate::Vec;
3use crate::{EdgeEndpoints, GraphError, Result, StableEdgeKey, StableNodeKey};
4
5#[derive(Debug, Clone)]
6pub(super) struct NodeSlot<NodePayload> {
7    pub(super) generation: u32,
8    pub(super) value: Option<NodePayload>,
9    pub(super) outgoing: u32,
10    pub(super) incoming: u32,
11}
12
13#[derive(Debug, Clone)]
14pub(super) struct EdgeSlot<EdgePayload> {
15    pub(super) generation: u32,
16    pub(super) value: Option<EdgePayload>,
17    pub(super) source: u32,
18    pub(super) target: u32,
19    pub(super) next_outgoing: u32,
20    pub(super) next_incoming: u32,
21}
22
23/// A mutable directed payload graph with generation-checked stable keys.
24#[derive(Debug, Clone)]
25pub struct StablePayloadGraph<NodePayload, EdgePayload> {
26    pub(super) nodes: Vec<NodeSlot<NodePayload>>,
27    pub(super) edges: Vec<EdgeSlot<EdgePayload>>,
28    pub(super) free_nodes: Vec<u32>,
29    pub(super) free_edges: Vec<u32>,
30    pub(super) node_count: usize,
31    pub(super) edge_count: usize,
32}
33
34impl<NodePayload, EdgePayload> Default for StablePayloadGraph<NodePayload, EdgePayload> {
35    fn default() -> Self {
36        Self::new()
37    }
38}
39
40impl<NodePayload, EdgePayload> StablePayloadGraph<NodePayload, EdgePayload> {
41    #[must_use]
42    pub const fn new() -> Self {
43        Self {
44            nodes: Vec::new(),
45            edges: Vec::new(),
46            free_nodes: Vec::new(),
47            free_edges: Vec::new(),
48            node_count: 0,
49            edge_count: 0,
50        }
51    }
52
53    #[must_use]
54    pub fn with_capacity(nodes: usize, edges: usize) -> Self {
55        Self {
56            nodes: Vec::with_capacity(nodes),
57            edges: Vec::with_capacity(edges),
58            free_nodes: Vec::new(),
59            free_edges: Vec::new(),
60            node_count: 0,
61            edge_count: 0,
62        }
63    }
64
65    /// Adds a payload and returns a key that detects later slot reuse.
66    ///
67    /// # Errors
68    ///
69    /// Returns an error when the stable index space is exhausted.
70    pub fn add_node(&mut self, payload: NodePayload) -> Result<StableNodeKey> {
71        let key = if let Some(slot) = self.free_nodes.pop() {
72            let entry = &mut self.nodes[slot as usize];
73            entry.value = Some(payload);
74            entry.outgoing = NONE_SLOT;
75            entry.incoming = NONE_SLOT;
76            StableNodeKey::new(slot, entry.generation)
77        } else {
78            let slot = next_slot(self.nodes.len(), "stable payload nodes")?;
79            self.nodes.push(NodeSlot {
80                generation: 0,
81                value: Some(payload),
82                outgoing: NONE_SLOT,
83                incoming: NONE_SLOT,
84            });
85            StableNodeKey::new(slot, 0)
86        };
87        self.node_count += 1;
88        Ok(key)
89    }
90
91    /// Adds a directed edge between two live stable node keys.
92    ///
93    /// # Errors
94    ///
95    /// Returns an error for stale endpoints or exhausted stable indices.
96    pub fn add_edge(
97        &mut self,
98        source: StableNodeKey,
99        target: StableNodeKey,
100        payload: EdgePayload,
101    ) -> Result<StableEdgeKey> {
102        self.require_node(source)?;
103        self.require_node(target)?;
104        let key = self.allocate_edge(source, target, payload)?;
105        self.link_outgoing(source, key);
106        self.link_incoming(target, key);
107        self.edge_count += 1;
108        Ok(key)
109    }
110
111    #[must_use]
112    pub fn node(&self, key: StableNodeKey) -> Option<&NodePayload> {
113        self.node_slot(key)?.value.as_ref()
114    }
115
116    #[must_use]
117    pub fn node_mut(&mut self, key: StableNodeKey) -> Option<&mut NodePayload> {
118        self.node_slot_mut(key)?.value.as_mut()
119    }
120
121    #[must_use]
122    pub fn edge(&self, key: StableEdgeKey) -> Option<&EdgePayload> {
123        self.edge_slot(key)?.value.as_ref()
124    }
125
126    #[must_use]
127    pub fn edge_mut(&mut self, key: StableEdgeKey) -> Option<&mut EdgePayload> {
128        self.edge_slot_mut(key)?.value.as_mut()
129    }
130
131    #[must_use]
132    pub fn edge_endpoints(&self, key: StableEdgeKey) -> Option<EdgeEndpoints<StableNodeKey>> {
133        let slot = self.edge_slot(key)?;
134        Some(EdgeEndpoints::new(
135            self.node_key_at(slot.source)?,
136            self.node_key_at(slot.target)?,
137        ))
138    }
139
140    pub fn nodes(&self) -> impl Iterator<Item = (StableNodeKey, &NodePayload)> {
141        self.nodes.iter().enumerate().filter_map(|(slot, entry)| {
142            Some((
143                StableNodeKey::new(u32::try_from(slot).ok()?, entry.generation),
144                entry.value.as_ref()?,
145            ))
146        })
147    }
148
149    pub fn edges(&self) -> impl Iterator<Item = (StableEdgeKey, &EdgePayload)> {
150        self.edges.iter().enumerate().filter_map(|(slot, entry)| {
151            Some((
152                StableEdgeKey::new(u32::try_from(slot).ok()?, entry.generation),
153                entry.value.as_ref()?,
154            ))
155        })
156    }
157
158    pub fn outgoing_edges(&self, node: StableNodeKey) -> impl Iterator<Item = StableEdgeKey> + '_ {
159        self.node_slot(node).map_or_else(
160            || EdgeKeys::empty(&self.edges, true),
161            |slot| EdgeKeys::new(&self.edges, slot.outgoing, true),
162        )
163    }
164
165    pub fn incoming_edges(&self, node: StableNodeKey) -> impl Iterator<Item = StableEdgeKey> + '_ {
166        self.node_slot(node).map_or_else(
167            || EdgeKeys::empty(&self.edges, false),
168            |slot| EdgeKeys::new(&self.edges, slot.incoming, false),
169        )
170    }
171
172    #[must_use]
173    pub const fn node_count(&self) -> usize {
174        self.node_count
175    }
176
177    #[must_use]
178    pub const fn edge_count(&self) -> usize {
179        self.edge_count
180    }
181
182    #[must_use]
183    pub const fn is_empty(&self) -> bool {
184        self.node_count == 0 && self.edge_count == 0
185    }
186
187    pub(super) fn node_slot(&self, key: StableNodeKey) -> Option<&NodeSlot<NodePayload>> {
188        let slot = self.nodes.get(key.index())?;
189        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
190    }
191
192    pub(super) fn node_slot_mut(
193        &mut self,
194        key: StableNodeKey,
195    ) -> Option<&mut NodeSlot<NodePayload>> {
196        let slot = self.nodes.get_mut(key.index())?;
197        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
198    }
199
200    pub(super) fn edge_slot(&self, key: StableEdgeKey) -> Option<&EdgeSlot<EdgePayload>> {
201        let slot = self.edges.get(key.index())?;
202        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
203    }
204
205    pub(super) fn edge_slot_mut(
206        &mut self,
207        key: StableEdgeKey,
208    ) -> Option<&mut EdgeSlot<EdgePayload>> {
209        let slot = self.edges.get_mut(key.index())?;
210        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
211    }
212
213    pub(super) fn require_node(&self, key: StableNodeKey) -> Result<()> {
214        if self.node_slot(key).is_some() {
215            Ok(())
216        } else {
217            Err(GraphError::InvalidStableKey {
218                category: "node",
219                slot: key.slot(),
220                generation: key.generation(),
221            })
222        }
223    }
224
225    fn allocate_edge(
226        &mut self,
227        source: StableNodeKey,
228        target: StableNodeKey,
229        payload: EdgePayload,
230    ) -> Result<StableEdgeKey> {
231        if let Some(slot) = self.free_edges.pop() {
232            let entry = &mut self.edges[slot as usize];
233            entry.value = Some(payload);
234            entry.source = source.slot();
235            entry.target = target.slot();
236            entry.next_outgoing = NONE_SLOT;
237            entry.next_incoming = NONE_SLOT;
238            return Ok(StableEdgeKey::new(slot, entry.generation));
239        }
240        let slot = next_slot(self.edges.len(), "stable payload edges")?;
241        self.edges.push(EdgeSlot {
242            generation: 0,
243            value: Some(payload),
244            source: source.slot(),
245            target: target.slot(),
246            next_outgoing: NONE_SLOT,
247            next_incoming: NONE_SLOT,
248        });
249        Ok(StableEdgeKey::new(slot, 0))
250    }
251
252    fn node_key_at(&self, slot: u32) -> Option<StableNodeKey> {
253        let entry = self.nodes.get(slot as usize)?;
254        entry
255            .value
256            .as_ref()
257            .map(|_| StableNodeKey::new(slot, entry.generation))
258    }
259}
260
261pub(crate) fn next_slot(count: usize, category: &'static str) -> Result<u32> {
262    u32::try_from(count).map_err(|_| GraphError::IndexCapacityExceeded { category, count })
263}
weavatrix_graph/payload/stable/core.rs

weavatrix_graph/payload/stable/
core.rs
