1use sim_incremental_core::{
2 QueryBudgets, ValueFingerprint,
3 dataflow::{
4 AdmittedTransfer, Boundary, DataflowCompletionProof, DataflowError, DataflowGraph,
5 EdgeClass, EdgeSpec, FixpointEngine, GraphBuildError, GraphDirection, JoinSemilattice,
6 LawViolation, NodeSpec, StateSize, TransferPolicy,
7 },
8};
9use sim_kernel::{
10 Cx, Expr, MatchScore, Result as KernelResult, Shape, ShapeDoc, ShapeMatch, Symbol, Value,
11};
12use std::{
13 collections::{BTreeMap, BTreeSet},
14 fmt,
15};
16
17pub type NodeId = u64;
18pub type EdgeId = u64;
19
20#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
21pub enum InfluenceSource {
22 Energy,
23 Work,
24 Power,
25 Passivity,
26 BalanceResidual,
27 Derived,
28}
29
30#[derive(Clone, Debug, Default, Eq, Hash, PartialEq)]
31pub enum Influence {
32 #[default]
33 Clean,
34 EnergyObserved(Vec<InfluenceSource>),
35 Unknown,
36}
37impl Influence {
38 pub fn from_source(source: InfluenceSource) -> Self {
39 Self::EnergyObserved(vec![source])
40 }
41 pub const fn is_clean(&self) -> bool {
42 matches!(self, Self::Clean)
43 }
44}
45impl StateSize for Influence {
46 fn state_size(&self) -> usize {
47 match self {
48 Self::Clean => 0,
49 Self::EnergyObserved(v) => v.len(),
50 Self::Unknown => 1,
51 }
52 }
53}
54impl JoinSemilattice for Influence {
55 fn bottom(&self) -> Self {
56 Self::Clean
57 }
58 fn join(&self, other: &Self) -> Self {
59 match (self, other) {
60 (Self::Unknown, _) | (_, Self::Unknown) => Self::Unknown,
61 (Self::Clean, value) | (value, Self::Clean) => value.clone(),
62 (Self::EnergyObserved(left), Self::EnergyObserved(right)) => {
63 let mut sources = left.clone();
64 sources.extend(right);
65 sources.sort_unstable();
66 sources.dedup();
67 Self::EnergyObserved(sources)
68 }
69 }
70 }
71 fn less_equal(&self, other: &Self) -> bool {
72 match (self, other) {
73 (Self::Clean, _) | (_, Self::Unknown) => true,
74 (Self::Unknown, _) => false,
75 (Self::EnergyObserved(_), Self::Clean) => false,
76 (Self::EnergyObserved(left), Self::EnergyObserved(right)) => {
77 left.iter().all(|v| right.contains(v))
78 }
79 }
80 }
81}
82
83#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
84pub enum Transform {
85 Input,
86 Arithmetic,
87 DimensionChange,
88 DomainAdapter,
89 Branch,
90 Join,
91 Loop,
92 Opaque,
93 CheckedNative,
94 Sink(SinkKind),
95}
96#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
97pub enum SinkKind {
98 Selection,
99 Ranking,
100 Sizing,
101 Control,
102}
103#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
104pub struct StudyNode {
105 pub id: NodeId,
106 pub location: String,
107 pub transform: Transform,
108}
109#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
110pub struct StudyEdge {
111 pub id: EdgeId,
112 pub source: NodeId,
113 pub target: NodeId,
114}
115
116#[derive(Clone, Debug)]
117pub struct StudyGraph {
118 graph: DataflowGraph<NodeId, EdgeId, String, ()>,
119 nodes: BTreeMap<NodeId, StudyNode>,
120 declared: BTreeMap<NodeId, Influence>,
121}
122#[derive(Clone, Debug, Eq, PartialEq)]
123pub enum StudyBuildError {
124 Graph(GraphBuildError<NodeId, EdgeId>),
125 DuplicateDeclaration(NodeId),
126}
127impl StudyGraph {
128 pub fn build(
129 nodes: impl IntoIterator<Item = StudyNode>,
130 edges: impl IntoIterator<Item = StudyEdge>,
131 inputs: impl IntoIterator<Item = (NodeId, InfluenceSource)>,
132 ) -> std::result::Result<Self, StudyBuildError> {
133 let nodes = nodes
134 .into_iter()
135 .map(|n| (n.id, n))
136 .collect::<BTreeMap<_, _>>();
137 let graph_nodes = nodes.values().map(|n| NodeSpec {
138 id: n.id,
139 location: n.location.clone(),
140 boundary: if matches!(n.transform, Transform::Input) {
141 Boundary::Input
142 } else if matches!(n.transform, Transform::Sink(_)) {
143 Boundary::Output
144 } else {
145 Boundary::Internal
146 },
147 });
148 let graph_edges = edges.into_iter().map(|e| EdgeSpec {
149 id: e.id,
150 source: e.source,
151 target: e.target,
152 class: EdgeClass::Data,
153 direction: GraphDirection::Forward,
154 });
155 let graph =
156 DataflowGraph::build(graph_nodes, graph_edges).map_err(StudyBuildError::Graph)?;
157 let mut declared = BTreeMap::new();
158 for (id, source) in inputs {
159 if declared
160 .insert(id, Influence::from_source(source))
161 .is_some()
162 {
163 return Err(StudyBuildError::DuplicateDeclaration(id));
164 }
165 }
166 for node in nodes.values() {
167 if matches!(node.transform, Transform::Opaque) {
168 declared.insert(node.id, Influence::Unknown);
169 }
170 }
171 Ok(Self {
172 graph,
173 nodes,
174 declared,
175 })
176 }
177 pub fn fingerprint(&self) -> ValueFingerprint {
178 self.graph.fingerprint()
179 }
180 fn seeds(&self) -> impl Iterator<Item = (NodeId, Influence)> + '_ {
181 self.declared.iter().map(|(id, state)| (*id, state.clone()))
182 }
183}
184
185#[derive(Clone, Copy, Debug)]
186struct PreserveInfluence;
187impl TransferPolicy<Influence> for PreserveInfluence {
188 fn fingerprint(&self) -> ValueFingerprint {
189 ValueFingerprint::new(0x5048_5953_494e_464c)
190 }
191 fn policy_size(&self) -> usize {
192 0
193 }
194 fn transfer(&self, state: &Influence) -> Influence {
195 state.clone()
196 }
197}
198type Proof = DataflowCompletionProof<NodeId, EdgeId, (), Influence>;
199pub struct InfluenceAudit {
200 study: StudyGraph,
201 transfer: AdmittedTransfer<PreserveInfluence>,
202 proof: Proof,
203 budgets: QueryBudgets,
204}
205#[derive(Clone, Debug, Eq, PartialEq)]
206pub struct Refusal {
207 pub sink: NodeId,
208 pub location: String,
209 pub influence: Influence,
210 pub path: Vec<(NodeId, Option<EdgeId>)>,
211 pub path_truncated: bool,
212}
213#[derive(Debug)]
214pub enum AuditError {
215 Policy(LawViolation),
216 Dataflow(DataflowError<NodeId, EdgeId, String>),
217 NotSink(NodeId),
218 Refused(Refusal),
219}
220impl fmt::Display for AuditError {
221 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
222 write!(f, "{self:?}")
223 }
224}
225impl std::error::Error for AuditError {}
226impl InfluenceAudit {
227 pub fn complete(
228 study: StudyGraph,
229 budgets: QueryBudgets,
230 ) -> std::result::Result<Self, AuditError> {
231 let samples = [
232 Influence::Clean,
233 Influence::from_source(InfluenceSource::Energy),
234 Influence::from_source(InfluenceSource::Work),
235 Influence::Unknown,
236 ];
237 let transfer =
238 AdmittedTransfer::admit(PreserveInfluence, &samples).map_err(AuditError::Policy)?;
239 let proof = FixpointEngine::solve_proven(
240 &study.graph,
241 &transfer,
242 Influence::Clean,
243 study.seeds(),
244 budgets,
245 )
246 .map_err(AuditError::Dataflow)?;
247 Ok(Self {
248 study,
249 transfer,
250 proof,
251 budgets,
252 })
253 }
254 pub fn complete_incremental(self, study: StudyGraph) -> std::result::Result<Self, AuditError> {
255 let proof = FixpointEngine::solve_incremental(
256 &self.proof,
257 &study.graph,
258 &self.transfer,
259 Influence::Clean,
260 study.seeds(),
261 self.budgets,
262 )
263 .map_err(AuditError::Dataflow)?;
264 Ok(Self {
265 study,
266 proof,
267 ..self
268 })
269 }
270 pub fn prepare(&self, sink: NodeId) -> std::result::Result<SelectionInput, AuditError> {
271 let Some(node) = self.study.nodes.get(&sink) else {
272 return Err(AuditError::NotSink(sink));
273 };
274 if !matches!(node.transform, Transform::Sink(_)) {
275 return Err(AuditError::NotSink(sink));
276 }
277 let state = self
278 .proof
279 .solution()
280 .state(&sink)
281 .expect("sink belongs to proven graph");
282 if !state.is_clean() {
283 let mut path = Vec::new();
284 let mut visited = BTreeSet::new();
285 let path_truncated = collect_causes(&self.proof, sink, &mut visited, &mut path, 64);
286 return Err(AuditError::Refused(Refusal {
287 sink,
288 location: node.location.clone(),
289 influence: state.clone(),
290 path,
291 path_truncated,
292 }));
293 }
294 Ok(SelectionInput {
295 sink,
296 proof_identity: self.proof.identity().get(),
297 })
298 }
299 pub fn prepare_runtime(
300 &self,
301 cx: &mut Cx,
302 request: Value,
303 sink: NodeId,
304 ) -> KernelResult<SelectionInput> {
305 let checked = SelectionRequestShape.check_value(cx, request)?;
306 if !checked.accepted {
307 return Err(sim_kernel::Error::Lib(
308 "physics selection request Shape rejected".into(),
309 ));
310 }
311 self.prepare(sink)
312 .map_err(|e| sim_kernel::Error::Lib(e.to_string()))
313 }
314 pub const fn proof_identity(&self) -> u64 {
315 self.proof.identity().get()
316 }
317}
318
319fn collect_causes(
320 proof: &Proof,
321 node: NodeId,
322 visited: &mut BTreeSet<NodeId>,
323 path: &mut Vec<(NodeId, Option<EdgeId>)>,
324 limit: usize,
325) -> bool {
326 if !visited.insert(node) || path.len() >= limit {
327 return path.len() >= limit;
328 }
329 let Some(explanation) = proof
330 .solution()
331 .explain(&node, limit.saturating_sub(path.len()))
332 else {
333 return false;
334 };
335 let mut truncated = explanation.truncated();
336 for cause in explanation.predecessors() {
337 if path.len() >= limit {
338 return true;
339 }
340 path.push((cause.node, cause.edge));
341 truncated |= collect_causes(proof, cause.node, visited, path, limit);
342 }
343 truncated
344}
345#[derive(Debug)]
346pub struct SelectionInput {
347 sink: NodeId,
348 proof_identity: u64,
349}
350impl SelectionInput {
351 pub const fn sink(&self) -> NodeId {
352 self.sink
353 }
354 pub const fn proof_identity(&self) -> u64 {
355 self.proof_identity
356 }
357}
358pub trait CleanSelection {
359 fn selection_input(&self) -> &SelectionInput;
360}
361impl CleanSelection for SelectionInput {
362 fn selection_input(&self) -> &SelectionInput {
363 self
364 }
365}
366#[derive(Clone, Copy, Debug, Default)]
367pub struct SelectionRequestShape;
368impl Shape for SelectionRequestShape {
369 fn symbol(&self) -> Option<Symbol> {
370 Some(Symbol::qualified("physics/influence", "SelectionRequest"))
371 }
372 fn check_value(&self, cx: &mut Cx, value: Value) -> KernelResult<ShapeMatch> {
373 let expr = value.object().as_expr(cx)?;
374 self.check_expr(cx, &expr)
375 }
376 fn check_expr(&self, _cx: &mut Cx, expr: &Expr) -> KernelResult<ShapeMatch> {
377 match expr {
378 Expr::List(items) if items.len() == 2 => Ok(ShapeMatch::accept(MatchScore::exact(100))),
379 _ => Ok(ShapeMatch::reject(
380 "physics selection request must be (sink candidate)",
381 )),
382 }
383 }
384 fn describe(&self, _cx: &mut Cx) -> KernelResult<ShapeDoc> {
385 Ok(ShapeDoc::new("proof-prepared physics selection request").with_detail("Shape acceptance is necessary but cannot replace a clean dataflow completion proof"))
386 }
387}