1use proof_core::{
9 model::{RelType, Relationship},
10 ErrorCode, Limits, ProofError,
11};
12use std::collections::{HashMap, HashSet};
13
14#[derive(Debug, Clone)]
16pub struct EdgeRecord {
17 pub content: Relationship,
18 pub id: String,
19}
20
21impl EdgeRecord {
22 pub fn new(content: Relationship, id: String) -> Self {
26 Self { content, id }
27 }
28}
29
30#[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#[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
58pub 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
139fn 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 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#[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 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 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 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 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}