Skip to main content

mimir_node_map/
contraction.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//! Derive order from proven absent/optional hole boundaries. No wire witness.
3use std::collections::{BTreeMap, BTreeSet};
4
5pub type Position = (u32, u32);
6pub type Pair = (u32, u32, u32);
7
8#[derive(Clone, Debug, Default, PartialEq, Eq)]
9pub struct Relation {
10    pub nodes: BTreeSet<Position>,
11    pub first: BTreeSet<Position>,
12    pub pairs: BTreeSet<Pair>,
13}
14
15#[derive(Clone, Debug, PartialEq, Eq)]
16pub enum Refusal {
17    UnknownPosition(Position),
18    ConflictingPosition(Position),
19    OrdinaryCall(Position),
20    NewCallPair(Pair),
21}
22
23/// The caller must establish the two sets with the shared evidence checker.
24/// Ordinary call nodes include unknown/open calls, irrespective of their bounds.
25pub fn contract(
26    raw: &Relation,
27    never: &BTreeSet<Position>,
28    optional: &BTreeSet<Position>,
29    calls: &BTreeSet<u32>,
30) -> Result<Relation, Refusal> {
31    for &p in never.union(optional) {
32        if !raw.nodes.contains(&p) {
33            return Err(Refusal::UnknownPosition(p));
34        }
35        if never.contains(&p) && optional.contains(&p) {
36            return Err(Refusal::ConflictingPosition(p));
37        }
38        if calls.contains(&p.1) {
39            return Err(Refusal::OrdinaryCall(p));
40        }
41    }
42    let mut next = BTreeMap::<Position, BTreeSet<Position>>::new();
43    for &(entry, a, b) in &raw.pairs {
44        for p in [(entry, a), (entry, b)] {
45            if !raw.nodes.contains(&p) {
46                return Err(Refusal::UnknownPosition(p));
47            }
48        }
49        next.entry((entry, a)).or_default().insert((entry, b));
50    }
51    for &p in &raw.first {
52        if !raw.nodes.contains(&p) {
53            return Err(Refusal::UnknownPosition(p));
54        }
55    }
56    let mut result = Relation {
57        nodes: raw.nodes.difference(never).copied().collect(),
58        first: through(&next, raw.first.iter().copied(), never, optional),
59        pairs: BTreeSet::new(),
60    };
61    for (&(entry, a), successors) in &next {
62        if never.contains(&(entry, a)) {
63            continue;
64        }
65        for (_, b) in through(&next, successors.iter().copied(), never, optional) {
66            let pair = (entry, a, b);
67            if calls.contains(&a) && calls.contains(&b) && !raw.pairs.contains(&pair) {
68                return Err(Refusal::NewCallPair(pair));
69            }
70            result.pairs.insert(pair);
71        }
72    }
73    Ok(result)
74}
75
76/// Expand paths through removed nodes and optional boundaries. Optional nodes
77/// remain outputs as well as being traversed. Other retained nodes stop a path.
78/// Entry identity belongs in N when traversing a relation with multiple entries.
79pub fn through<N: Ord + Clone>(
80    next: &BTreeMap<N, BTreeSet<N>>,
81    starts: impl IntoIterator<Item = N>,
82    never: &BTreeSet<N>,
83    optional: &BTreeSet<N>,
84) -> BTreeSet<N> {
85    let mut out = BTreeSet::new();
86    let mut seen = BTreeSet::new();
87    let mut work: Vec<_> = starts.into_iter().collect();
88    while let Some(n) = work.pop() {
89        if !seen.insert(n.clone()) {
90            continue;
91        }
92        if !never.contains(&n) {
93            out.insert(n.clone());
94        }
95        if never.contains(&n) || optional.contains(&n) {
96            work.extend(next.get(&n).into_iter().flatten().cloned());
97        }
98    }
99    out
100}