Skip to main content

proof_graph/
lib.rs

1// Copyright 2026 Proof Engine Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3//! proof-graph: typed directed-graph validation over VERIFIED records.
4//! This crate never touches bytes or signatures. Callers must verify artifact
5//! ids (canonical form + schema + id binding) BEFORE constructing `EdgeRecord`s
6//! — typically via `proof-crypto::build`. Topology checks here assume authentic inputs.
7
8use proof_core::{
9    model::{RelType, Relationship},
10    ErrorCode, Limits, ProofError,
11};
12use std::collections::{HashMap, HashSet};
13
14/// A relationship whose bytes have already been verified (id binding checked).
15#[derive(Debug, Clone)]
16pub struct EdgeRecord {
17    pub content: Relationship,
18    pub id: String,
19}
20
21impl EdgeRecord {
22    /// Construct from already-verified parts. CALLER MUST have checked the id
23    /// binding first (e.g. `proof-crypto::build::verify_relationship`); this
24    /// constructor cannot tell a forged id from a real one.
25    pub fn new(content: Relationship, id: String) -> Self {
26        Self { content, id }
27    }
28}
29
30/// All known artifact ids (events, attestations, evidence) that edges may reference.
31#[derive(Debug, Clone, Default)]
32pub struct NodeSet {
33    ids: HashSet<String>,
34}
35
36impl NodeSet {
37    pub fn new(ids: impl IntoIterator<Item = String>) -> Self {
38        Self {
39            ids: ids.into_iter().collect(),
40        }
41    }
42
43    pub fn contains(&self, id: &str) -> bool {
44        self.ids.contains(id)
45    }
46}
47
48/// Successful validation summary. The validated edge ids are returned so the
49/// pipeline can prove exactly which edges passed (explanation support).
50#[derive(Debug, Clone)]
51pub struct ValidatedGraph {
52    pub edge_ids: Vec<String>,
53    pub node_count: usize,
54    pub edge_count: usize,
55    pub longest_supersedes_chain: usize,
56}
57
58/// Validate edge topology:
59/// 1. counts within limits; 2. endpoints + refs resolve; 3. trust-relevant
60///    edges grounded; 4. SUPERSEDES subgraph linear, acyclic, depth-bounded.
61// PE-GRAPH-001 (grounding) · PE-GRAPH-002 (dangling) · PE-GRAPH-004 (limits).
62pub fn validate_graph(
63    edges: &[EdgeRecord],
64    nodes: &NodeSet,
65    limits: &Limits,
66) -> Result<ValidatedGraph, ProofError> {
67    if edges.len() > limits.max_edges {
68        return Err(ErrorCode::LimitExceeded.err(format!(
69            "edges {} > max_edges {}",
70            edges.len(),
71            limits.max_edges
72        )));
73    }
74
75    let mut endpoints: HashSet<&str> = HashSet::new();
76    for e in edges {
77        let r = &e.content;
78        if r.v != 1 {
79            return Err(ErrorCode::UnsupportedVersion.err("only relationship v=1 supported"));
80        }
81        if r.from.is_empty() || r.to.is_empty() {
82            return Err(ErrorCode::DanglingReference.err("empty endpoint"));
83        }
84        if r.from == r.to {
85            return Err(ErrorCode::SchemaViolation.err("self-edge forbidden"));
86        }
87        if !nodes.contains(&r.from) {
88            return Err(ErrorCode::DanglingReference.err(format!("unknown from {}", r.from)));
89        }
90        if !nodes.contains(&r.to) {
91            return Err(ErrorCode::DanglingReference.err(format!("unknown to {}", r.to)));
92        }
93        if r.rel_type.requires_grounding()
94            && r.evidence_ref.is_none()
95            && r.attestation_ref.is_none()
96        {
97            return Err(ErrorCode::RelationshipUngrounded.err(format!(
98                "edge {} ({}) lacks backing evidence",
99                e.id,
100                r.rel_type.as_str()
101            )));
102        }
103        for label in ["evidence_ref", "attestation_ref"] {
104            let opt = if label == "evidence_ref" {
105                &r.evidence_ref
106            } else {
107                &r.attestation_ref
108            };
109            if let Some(id) = opt {
110                if id.is_empty() {
111                    return Err(ErrorCode::SchemaViolation.err(format!("empty {label}")));
112                }
113                if !nodes.contains(id) {
114                    return Err(ErrorCode::DanglingReference.err(format!("unknown {label} {id}")));
115                }
116            }
117        }
118        endpoints.insert(r.from.as_str());
119        endpoints.insert(r.to.as_str());
120    }
121    if endpoints.len() > limits.max_nodes {
122        return Err(ErrorCode::LimitExceeded.err(format!(
123            "nodes {} > max_nodes {}",
124            endpoints.len(),
125            limits.max_nodes
126        )));
127    }
128
129    let longest = check_supersedes(edges, limits)?;
130
131    Ok(ValidatedGraph {
132        edge_ids: edges.iter().map(|e| e.id.clone()).collect(),
133        node_count: endpoints.len(),
134        edge_count: edges.len(),
135        longest_supersedes_chain: longest,
136    })
137}
138
139/// SUPERSEDES subgraph must be a set of linear chains: acyclic, indegree ≤ 1,
140/// outdegree ≤ 1, longest chain ≤ max_depth. Iterative (no recursion on hostile input).
141// PE-GRAPH-003 (SUPERSEDES acyclic/linear/depth-bounded).
142fn check_supersedes(edges: &[EdgeRecord], limits: &Limits) -> Result<usize, ProofError> {
143    let sup: Vec<(&str, &str)> = edges
144        .iter()
145        .filter(|e| e.content.rel_type.as_str() == RelType::SUPERSEDES)
146        .map(|e| (e.content.from.as_str(), e.content.to.as_str()))
147        .collect();
148    if sup.is_empty() {
149        return Ok(0);
150    }
151    let mut out_deg: HashMap<&str, usize> = HashMap::new();
152    let mut in_deg: HashMap<&str, usize> = HashMap::new();
153    let mut adj: HashMap<&str, Vec<&str>> = HashMap::new();
154    let mut nodes: HashSet<&str> = HashSet::new();
155    for (a, b) in &sup {
156        *out_deg.entry(a).or_insert(0) += 1;
157        *in_deg.entry(b).or_insert(0) += 1;
158        nodes.insert(a);
159        nodes.insert(b);
160        adj.entry(a).or_default().push(b);
161    }
162    for n in &nodes {
163        if out_deg.get(n).copied().unwrap_or(0) > 1 || in_deg.get(n).copied().unwrap_or(0) > 1 {
164            return Err(ErrorCode::SchemaViolation
165                .err(format!("supersedes must be linear chains (branch at {n})")));
166        }
167    }
168    // Kahn's algorithm: longest path + cycle detection.
169    let mut indeg = in_deg.clone();
170    let mut dist: HashMap<&str, usize> = nodes.iter().map(|n| (*n, 1)).collect();
171    let mut stack: Vec<&str> = nodes
172        .iter()
173        .filter(|n| indeg.get(*n).copied().unwrap_or(0) == 0)
174        .copied()
175        .collect();
176    let mut seen = 0usize;
177    let mut longest = 1usize;
178    while let Some(n) = stack.pop() {
179        seen += 1;
180        let d = dist[&n];
181        if let Some(nexts) = adj.get(n) {
182            for m in nexts {
183                let dm = dist.get_mut(m).expect("node");
184                if *dm < d + 1 {
185                    *dm = d + 1;
186                    longest = longest.max(d + 1);
187                }
188                let e = indeg.get_mut(m).expect("node");
189                *e -= 1;
190                if *e == 0 {
191                    stack.push(m);
192                }
193            }
194        }
195    }
196    if seen != nodes.len() {
197        return Err(ErrorCode::CycleDetected.err("cycle in SUPERSEDES subgraph"));
198    }
199    if longest > limits.max_depth {
200        return Err(ErrorCode::LimitExceeded.err(format!(
201            "supersedes chain {longest} > max_depth {}",
202            limits.max_depth
203        )));
204    }
205    Ok(longest)
206}
207
208// Test-only sugar to vary edge ids while reusing one content shape.
209#[cfg(test)]
210impl EdgeRecord {
211    fn clone_with_id(&self, id: &str) -> Self {
212        Self {
213            content: self.content.clone(),
214            id: id.into(),
215        }
216    }
217}
218
219#[cfg(test)]
220mod tests {
221    use super::*;
222
223    fn edge(from: &str, t: RelType, to: &str, grounded: bool) -> EdgeRecord {
224        let (ev, at) = if grounded {
225            (Some("evd:v1:g".to_string()), None)
226        } else {
227            (None, None)
228        };
229        EdgeRecord::new(
230            Relationship {
231                v: 1,
232                from: from.into(),
233                rel_type: t,
234                to: to.into(),
235                evidence_ref: ev,
236                attestation_ref: at,
237            },
238            format!("rel:v1:{from}-{to}"),
239        )
240    }
241
242    fn nodes(ids: &[&str]) -> NodeSet {
243        NodeSet::new(
244            ids.iter()
245                .map(|s| s.to_string())
246                .chain(["evd:v1:g".to_string()]),
247        )
248    }
249
250    fn lim() -> Limits {
251        Limits::default()
252    }
253
254    #[test]
255    fn valid_chain_passes() {
256        // Company OWNS Account CREATED Payment SETTLES Invoice (all grounded).
257        let n = nodes(&["obj:co", "obj:acct", "obj:pay", "obj:inv"]);
258        let edges = vec![
259            edge("obj:co", RelType::new(RelType::OWNS), "obj:acct", true),
260            edge("obj:acct", RelType::new(RelType::CREATED), "obj:pay", true),
261            edge("obj:pay", RelType::new(RelType::SETTLES), "obj:inv", true),
262        ];
263        let g = validate_graph(&edges, &n, &lim()).unwrap();
264        assert_eq!(g.edge_count, 3);
265        assert_eq!(g.node_count, 4);
266        assert_eq!(g.edge_ids.len(), 3);
267    }
268
269    #[test]
270    fn ungrounded_settles_rejected() {
271        let n = nodes(&["obj:pay", "obj:inv"]);
272        let e = edge("obj:pay", RelType::new(RelType::SETTLES), "obj:inv", false);
273        let err = validate_graph(&[e], &n, &lim()).unwrap_err();
274        assert_eq!(err.code, ErrorCode::RelationshipUngrounded);
275    }
276
277    #[test]
278    fn ungrounded_references_allowed() {
279        // Non-trust-relevant types may be bare (logged, not rejected).
280        let n = nodes(&["a", "b"]);
281        let e = edge("a", RelType::new(RelType::REFERENCES), "b", false);
282        validate_graph(&[e], &n, &lim()).unwrap();
283    }
284
285    #[test]
286    fn dangling_endpoint_rejected() {
287        let n = nodes(&["a"]);
288        let e = edge("a", RelType::new(RelType::REFERENCES), "ghost", false);
289        let err = validate_graph(&[e], &n, &lim()).unwrap_err();
290        assert_eq!(err.code, ErrorCode::DanglingReference);
291    }
292
293    #[test]
294    fn dangling_ref_rejected() {
295        let n = nodes(&["a", "b"]);
296        let mut e = edge("a", RelType::new(RelType::CREATED), "b", false);
297        e.content.evidence_ref = Some("evd:v1:ghost".into());
298        let err = validate_graph(&[e], &n, &lim()).unwrap_err();
299        assert_eq!(err.code, ErrorCode::DanglingReference);
300    }
301
302    #[test]
303    fn supersedes_cycle_rejected() {
304        let n = nodes(&["v1", "v2"]);
305        let edges = vec![
306            edge("v1", RelType::new(RelType::SUPERSEDES), "v2", false),
307            edge("v2", RelType::new(RelType::SUPERSEDES), "v1", false),
308        ];
309        let err = validate_graph(&edges, &n, &lim()).unwrap_err();
310        assert_eq!(err.code, ErrorCode::CycleDetected);
311    }
312
313    #[test]
314    fn supersedes_branch_rejected() {
315        let n = nodes(&["v1", "v2", "v3"]);
316        let edges = vec![
317            edge("v1", RelType::new(RelType::SUPERSEDES), "v2", false),
318            edge("v1", RelType::new(RelType::SUPERSEDES), "v3", false),
319        ];
320        let err = validate_graph(&edges, &n, &lim()).unwrap_err();
321        assert_eq!(err.code, ErrorCode::SchemaViolation);
322    }
323
324    #[test]
325    fn supersedes_linear_chain_ok() {
326        let n = nodes(&["v1", "v2", "v3"]);
327        let edges = vec![
328            edge("v1", RelType::new(RelType::SUPERSEDES), "v2", false),
329            edge("v2", RelType::new(RelType::SUPERSEDES), "v3", false),
330        ];
331        let g = validate_graph(&edges, &n, &lim()).unwrap();
332        assert_eq!(g.longest_supersedes_chain, 3);
333    }
334
335    #[test]
336    fn non_supersedes_cycles_allowed() {
337        // REFERENCES cycles are not forbidden in V0.1 (only SUPERSEDES is).
338        let n = nodes(&["a", "b"]);
339        let edges = vec![
340            edge("a", RelType::new(RelType::REFERENCES), "b", false),
341            edge("b", RelType::new(RelType::REFERENCES), "a", false),
342        ];
343        validate_graph(&edges, &n, &lim()).unwrap();
344    }
345
346    #[test]
347    fn edge_limit_enforced() {
348        // Plan acceptance: 300 edges against default max_edges=256.
349        let lim = lim();
350        assert_eq!(lim.max_edges, 256);
351        let n = NodeSet::new(["n0".to_string(), "n1".to_string()]);
352        let edges: Vec<_> = (0..300)
353            .map(|i| {
354                edge("n0", RelType::new(RelType::REFERENCES), "n1", false)
355                    .clone_with_id(&format!("e{i}"))
356            })
357            .collect();
358        let err = validate_graph(&edges, &n, &lim).unwrap_err();
359        assert_eq!(err.code, ErrorCode::LimitExceeded);
360    }
361
362    #[test]
363    fn depth_limit_enforced() {
364        let mut lim = lim();
365        lim.max_depth = 2;
366        let n = nodes(&["v1", "v2", "v3"]);
367        let edges = vec![
368            edge("v1", RelType::new(RelType::SUPERSEDES), "v2", false),
369            edge("v2", RelType::new(RelType::SUPERSEDES), "v3", false),
370        ];
371        let err = validate_graph(&edges, &n, &lim).unwrap_err();
372        assert_eq!(err.code, ErrorCode::LimitExceeded);
373    }
374}