sim_lib_discrete_graph/
control.rs

1//! Work, memory, deadline, and cancellation control for graph algorithms.
2
3use std::time::Duration;
4
5use crate::GraphError;
6
7/// Work charged for one dynamic-programming cell and one examined edge.
8#[derive(Clone, Copy, Debug, PartialEq, Eq)]
9pub struct AlgorithmWorkCosts {
10    /// Work units charged before evaluating a table cell.
11    pub cell: u64,
12    /// Work units charged before examining a transition or residual edge.
13    pub edge: u64,
14}
15
16impl Default for AlgorithmWorkCosts {
17    fn default() -> Self {
18        Self { cell: 1, edge: 1 }
19    }
20}
21
22/// Bounds and accounting policy for a graph algorithm run.
23#[derive(Clone, Debug, Default, PartialEq, Eq)]
24pub struct AlgorithmControl {
25    /// Optional maximum charged work.
26    pub max_work: Option<u64>,
27    /// Optional maximum simultaneously retained table cells.
28    pub max_memory_cells: Option<usize>,
29    /// Optional wall-clock deadline relative to the start of the call.
30    pub max_time: Option<Duration>,
31    /// Per-operation work costs.
32    pub costs: AlgorithmWorkCosts,
33}
34
35impl AlgorithmControl {
36    /// Returns a copy with a maximum work bound.
37    pub fn with_max_work(mut self, max_work: u64) -> Self {
38        self.max_work = Some(max_work);
39        self
40    }
41
42    /// Returns a copy with a maximum retained-cell bound.
43    pub fn with_max_memory_cells(mut self, max_memory_cells: usize) -> Self {
44        self.max_memory_cells = Some(max_memory_cells);
45        self
46    }
47
48    /// Returns a copy with a relative wall-clock deadline.
49    pub fn with_max_time(mut self, max_time: Duration) -> Self {
50        self.max_time = Some(max_time);
51        self
52    }
53
54    /// Returns a copy with explicit cell and edge charges.
55    pub fn with_costs(mut self, costs: AlgorithmWorkCosts) -> Self {
56        self.costs = costs;
57        self
58    }
59}
60
61/// Cooperative cancellation source for graph algorithms.
62pub trait AlgorithmInterrupt {
63    /// Returns true when the active computation should stop.
64    fn is_cancelled(&self) -> bool;
65
66    /// Elapsed monotonic time supplied by the caller's model or platform.
67    fn elapsed(&self) -> Duration {
68        Duration::ZERO
69    }
70}
71
72/// Cancellation source that never interrupts.
73#[derive(Clone, Copy, Debug, Default)]
74pub struct NeverInterrupt;
75
76impl AlgorithmInterrupt for NeverInterrupt {
77    fn is_cancelled(&self) -> bool {
78        false
79    }
80}
81
82/// Deterministic accounting evidence returned by a completed algorithm.
83#[derive(Clone, Debug, PartialEq, Eq)]
84pub struct AlgorithmReceipt {
85    /// Total charged work.
86    pub work_used: u64,
87    /// Number of evaluated dynamic-programming cells.
88    pub cells: u64,
89    /// Number of examined transitions or residual edges.
90    pub edges: u64,
91    /// Maximum table cells retained simultaneously.
92    pub peak_memory_cells: usize,
93    /// Work charged per cell.
94    pub cell_work: u64,
95    /// Work charged per edge.
96    pub edge_work: u64,
97}
98
99impl AlgorithmReceipt {
100    pub(crate) fn validate(&self) -> Result<(), GraphError> {
101        let cell_work = self
102            .cells
103            .checked_mul(self.cell_work)
104            .ok_or_else(|| GraphError::CertificateInvalid("cell work overflowed".to_owned()))?;
105        let edge_work = self
106            .edges
107            .checked_mul(self.edge_work)
108            .ok_or_else(|| GraphError::CertificateInvalid("edge work overflowed".to_owned()))?;
109        let expected = cell_work
110            .checked_add(edge_work)
111            .ok_or_else(|| GraphError::CertificateInvalid("total work overflowed".to_owned()))?;
112        if self.cell_work == 0 || self.edge_work == 0 {
113            return Err(GraphError::CertificateInvalid(
114                "algorithm work charges must be positive".to_owned(),
115            ));
116        }
117        if self.work_used != expected {
118            return Err(GraphError::CertificateInvalid(
119                "algorithm receipt work total is inconsistent".to_owned(),
120            ));
121        }
122        Ok(())
123    }
124}
125
126pub(crate) struct WorkMeter<'a> {
127    control: &'a AlgorithmControl,
128    interrupt: &'a dyn AlgorithmInterrupt,
129    receipt: AlgorithmReceipt,
130}
131
132impl<'a> WorkMeter<'a> {
133    pub(crate) fn new(
134        control: &'a AlgorithmControl,
135        interrupt: &'a dyn AlgorithmInterrupt,
136        peak_memory_cells: usize,
137    ) -> Result<Self, GraphError> {
138        if control.costs.cell == 0 || control.costs.edge == 0 {
139            return Err(GraphError::InvalidControl(
140                "cell and edge work costs must be positive".to_owned(),
141            ));
142        }
143        if control
144            .max_memory_cells
145            .is_some_and(|limit| peak_memory_cells > limit)
146        {
147            return Err(GraphError::ControlStopped(format!(
148                "memory-cell bound reached: required {peak_memory_cells}"
149            )));
150        }
151        Ok(Self {
152            control,
153            interrupt,
154            receipt: AlgorithmReceipt {
155                work_used: 0,
156                cells: 0,
157                edges: 0,
158                peak_memory_cells,
159                cell_work: control.costs.cell,
160                edge_work: control.costs.edge,
161            },
162        })
163    }
164
165    pub(crate) fn cell(&mut self) -> Result<(), GraphError> {
166        self.charge(self.control.costs.cell)?;
167        self.receipt.cells = self
168            .receipt
169            .cells
170            .checked_add(1)
171            .ok_or_else(|| GraphError::WeightOverflow("cell counter".to_owned()))?;
172        Ok(())
173    }
174
175    pub(crate) fn edge(&mut self) -> Result<(), GraphError> {
176        self.charge(self.control.costs.edge)?;
177        self.receipt.edges = self
178            .receipt
179            .edges
180            .checked_add(1)
181            .ok_or_else(|| GraphError::WeightOverflow("edge counter".to_owned()))?;
182        Ok(())
183    }
184
185    pub(crate) fn finish(self) -> AlgorithmReceipt {
186        self.receipt
187    }
188
189    fn charge(&mut self, work: u64) -> Result<(), GraphError> {
190        if self.interrupt.is_cancelled() {
191            return Err(GraphError::ControlStopped(
192                "algorithm interrupt cancelled the run".to_owned(),
193            ));
194        }
195        if self
196            .control
197            .max_time
198            .is_some_and(|limit| self.interrupt.elapsed() >= limit)
199        {
200            return Err(GraphError::ControlStopped(
201                "algorithm time bound reached".to_owned(),
202            ));
203        }
204        let next = self
205            .receipt
206            .work_used
207            .checked_add(work)
208            .ok_or_else(|| GraphError::WeightOverflow("work counter".to_owned()))?;
209        if self.control.max_work.is_some_and(|limit| next > limit) {
210            return Err(GraphError::ControlStopped(
211                "algorithm work bound reached".to_owned(),
212            ));
213        }
214        self.receipt.work_used = next;
215        Ok(())
216    }
217}
sim_lib_discrete_graph/control.rs

sim_lib_discrete_graph/
control.rs
