Skip to main content

vibe/stdlib_v2/topology_and_manifold/
simplex_and_sheaf.rs

1//! Higher-Order Simplicial Complexes, Hypergraphs, Cellular Sheaves & Persistent Homology (ยง22).
2
3use super::{extract_i64, extract_list, extract_record, extract_str, fnv1a_64, fnv1a_value};
4use crate::error::{DiagCode, Diagnostic};
5use crate::sheaf::{Simplex, Stalk, TopologicalTear};
6use crate::span::Span;
7use crate::value::Value;
8use std::collections::{BTreeMap, BTreeSet};
9
10pub fn call_simplex_and_sheaf(
11    path: &str,
12    args: &[Value],
13    span: Span,
14) -> Result<Option<Value>, Diagnostic> {
15    match path {
16        "simplex.define" => Ok(Some(simplex_define(args, span)?)),
17        "simplex.fold" => Ok(Some(simplex_fold(args, span)?)),
18        "hypergraph.bind_hyperedge" => Ok(Some(hypergraph_bind_hyperedge(args, span)?)),
19        "sheaf.project_stalk" => Ok(Some(sheaf_project_stalk(args, span)?)),
20        "sheaf.verify_intersection" => Ok(Some(sheaf_verify_intersection(args, span)?)),
21        "sheaf.apply_glue" => Ok(Some(sheaf_apply_glue(args, span)?)),
22        "topology.betti_numbers" | "topology.detect_voids" => {
23            Ok(Some(topology_betti_and_voids(args, span)?))
24        }
25        "homotopy.verify_equivalence" => Ok(Some(homotopy_verify_equivalence(args, span)?)),
26        _ => Ok(None),
27    }
28}
29
30fn simplex_define(args: &[Value], span: Span) -> Result<Value, Diagnostic> {
31    let name = extract_str(args, 0, "simplex.define", span)?;
32    let dim_i64 = extract_i64(args, 1, "simplex.define", span)?.max(0);
33    let dim = dim_i64.min(255) as u8;
34    let vertices = extract_list(args, 2, "simplex.define", span)?;
35    let member_hashes: Vec<u64> = vertices.iter().map(fnv1a_value).collect();
36    let simplex = Simplex::new(name, dim, member_hashes);
37
38    let expected_vertices = (dim as usize) + 1;
39    let mut boundary_faces = Vec::new();
40    let mut missing_face = None;
41
42    if let Some(Value::List(explicit_faces)) = args.get(3) {
43        boundary_faces = explicit_faces.clone();
44        if dim > 0 && boundary_faces.len() < expected_vertices {
45            missing_face = Some(format!(
46                "expected {} boundary faces for {dim}-simplex, found {}",
47                expected_vertices,
48                boundary_faces.len()
49            ));
50        }
51    } else if dim > 0 && vertices.len() == expected_vertices {
52        for omit in 0..vertices.len() {
53            let face: Vec<Value> = vertices
54                .iter()
55                .enumerate()
56                .filter(|(i, _)| *i != omit)
57                .map(|(_, v)| v.clone())
58                .collect();
59            boundary_faces.push(Value::List(face));
60        }
61    }
62
63    let intact = simplex.dimension == dim
64        && vertices.len() == expected_vertices
65        && missing_face.is_none();
66    let tear_diagnostic = if intact {
67        Value::Null
68    } else {
69        let reason = missing_face.unwrap_or_else(|| {
70            format!("expected {expected_vertices} vertices, got {}", vertices.len())
71        });
72        let tear = TopologicalTear::new(
73            &format!(
74                "TopologicalTear({name}): expected dim {dim}, got {} vertices ({reason})",
75                vertices.len()
76            ),
77            1.0,
78            0.5,
79            0,
80            span,
81        );
82        Value::String(tear.diagnostic)
83    };
84
85    let mut out = BTreeMap::new();
86    out.insert("__simplex".into(), Value::Bool(true));
87    out.insert("name".into(), Value::String(name.to_string()));
88    out.insert("dimension".into(), Value::I64(dim as i64));
89    out.insert("vertices".into(), Value::List(vertices.to_vec()));
90    out.insert("boundary_faces".into(), Value::List(boundary_faces));
91    out.insert("intact".into(), Value::Bool(intact));
92    out.insert("tear_diagnostic".into(), tear_diagnostic);
93    Ok(Value::Record(out))
94}
95
96fn simplex_fold(args: &[Value], span: Span) -> Result<Value, Diagnostic> {
97    let rec = extract_record(args, 0, "simplex.fold", span)?;
98    let transform = args
99        .get(1)
100        .and_then(|v| v.as_str())
101        .unwrap_or("barycentric");
102    let mut out = rec.clone();
103    let vertices = rec
104        .get("vertices")
105        .and_then(|v| match v {
106            Value::List(l) => Some(l.clone()),
107            _ => None,
108        })
109        .unwrap_or_default();
110    let folded_hash = vertices.iter().fold(0u64, |acc, v| acc ^ fnv1a_value(v));
111    out.insert("transform".into(), Value::String(transform.to_string()));
112    out.insert("folded_invariant".into(), Value::U64(folded_hash));
113    out.insert(
114        "intact".into(),
115        rec.get("intact").cloned().unwrap_or(Value::Bool(!vertices.is_empty())),
116    );
117    Ok(Value::Record(out))
118}
119
120fn hypergraph_bind_hyperedge(args: &[Value], span: Span) -> Result<Value, Diagnostic> {
121    let edge_id = extract_str(args, 0, "hypergraph.bind_hyperedge", span)?;
122    let nodes = extract_list(args, 1, "hypergraph.bind_hyperedge", span)?;
123    let inv_satisfied = match args.get(2) {
124        Some(Value::Bool(b)) => *b,
125        Some(Value::Record(r)) => {
126            let min_arity = r.get("min_arity").and_then(|v| v.as_i64()).unwrap_or(2) as usize;
127            nodes.len() >= min_arity
128        }
129        _ => nodes.len() >= 2,
130    };
131    let mut out = BTreeMap::new();
132    out.insert("hyperedge_id".into(), Value::String(edge_id.to_string()));
133    out.insert("arity".into(), Value::I64(nodes.len() as i64));
134    out.insert("nodes".into(), Value::List(nodes.to_vec()));
135    out.insert("satisfied".into(), Value::Bool(inv_satisfied));
136    Ok(Value::Record(out))
137}
138
139fn sheaf_project_stalk(args: &[Value], span: Span) -> Result<Value, Diagnostic> {
140    let global_rec = extract_record(args, 0, "sheaf.project_stalk", span)?;
141    let keys_list = extract_list(args, 1, "sheaf.project_stalk", span)?;
142    let agent_did = args
143        .get(2)
144        .and_then(|v| v.as_str())
145        .unwrap_or("did:q42:agent:local");
146
147    let mut neighborhood = Vec::new();
148    let mut local_section = BTreeMap::new();
149    for k_val in keys_list {
150        if let Some(k) = k_val.as_str() {
151            neighborhood.push(Value::String(k.to_string()));
152            if let Some(v) = global_rec.get(k) {
153                local_section.insert(k.to_string(), v.clone());
154            }
155        }
156    }
157    let snap_hash = fnv1a_value(&Value::Record(local_section.clone()));
158    let stalk = Stalk::new(snap_hash, snap_hash ^ 0x42, "sheaf:stalk", agent_did);
159
160    let mut out = BTreeMap::new();
161    out.insert("__stalk".into(), Value::Bool(true));
162    out.insert("agent_did".into(), Value::Iri(stalk.agent_did));
163    out.insert("neighborhood".into(), Value::List(neighborhood));
164    out.insert("local_section".into(), Value::Record(local_section));
165    out.insert("snapshot_hash".into(), Value::U64(stalk.snapshot_id));
166    Ok(Value::Record(out))
167}
168
169fn extract_section(stalk_rec: &BTreeMap<String, Value>) -> &BTreeMap<String, Value> {
170    if let Some(Value::Record(sec)) = stalk_rec.get("local_section") {
171        sec
172    } else {
173        stalk_rec
174    }
175}
176
177fn sheaf_verify_intersection(args: &[Value], span: Span) -> Result<Value, Diagnostic> {
178    let rec_a = extract_record(args, 0, "sheaf.verify_intersection", span)?;
179    let rec_b = extract_record(args, 1, "sheaf.verify_intersection", span)?;
180    let sec_a = extract_section(rec_a);
181    let sec_b = extract_section(rec_b);
182
183    let mut overlap_keys = Vec::new();
184    let mut conflicts = Vec::new();
185    for (k, va) in sec_a {
186        if k.starts_with("__") {
187            continue;
188        }
189        if let Some(vb) = sec_b.get(k) {
190            overlap_keys.push(Value::String(k.clone()));
191            if va != vb {
192                conflicts.push(Value::String(k.clone()));
193            }
194        }
195    }
196    let mut out = BTreeMap::new();
197    out.insert("agrees".into(), Value::Bool(conflicts.is_empty()));
198    out.insert("overlap_keys".into(), Value::List(overlap_keys));
199    out.insert("conflicts".into(), Value::List(conflicts));
200    Ok(Value::Record(out))
201}
202
203fn sheaf_apply_glue(args: &[Value], span: Span) -> Result<Value, Diagnostic> {
204    let stalks = extract_list(args, 0, "sheaf.apply_glue", span)?;
205    let mut global_section: BTreeMap<String, Value> = BTreeMap::new();
206    let mut conflict_set: BTreeSet<String> = BTreeSet::new();
207
208    for item in stalks {
209        let Value::Record(rec) = item else {
210            return Err(Diagnostic::new(
211                DiagCode::E100,
212                span,
213                "sheaf.apply_glue: every stalk must be a Record",
214            ));
215        };
216        let sec = extract_section(rec);
217        for (k, v) in sec {
218            if k.starts_with("__") {
219                continue;
220            }
221            if let Some(existing) = global_section.get(k) {
222                if existing != v {
223                    conflict_set.insert(k.clone());
224                }
225            } else {
226                global_section.insert(k.clone(), v.clone());
227            }
228        }
229    }
230
231    let tear_conflicts: Vec<Value> = conflict_set.into_iter().map(Value::String).collect();
232    let glued = tear_conflicts.is_empty();
233    let mut out = BTreeMap::new();
234    out.insert("glued".into(), Value::Bool(glued));
235    out.insert(
236        "global_section".into(),
237        if glued {
238            Value::Record(global_section)
239        } else {
240            Value::Record(BTreeMap::new())
241        },
242    );
243    out.insert("tear_conflicts".into(), Value::List(tear_conflicts));
244    Ok(Value::Record(out))
245}
246
247/// Compute rank of a binary matrix over GF(2) where each column is a bit-vector of row indices.
248fn gf2_rank(num_rows: usize, cols: &[Vec<usize>]) -> usize {
249    if num_rows == 0 || cols.is_empty() {
250        return 0;
251    }
252    let words = (num_rows + 63) / 64;
253    let mut basis: Vec<(usize, Vec<u64>)> = Vec::new();
254    for col in cols {
255        let mut vec = vec![0u64; words];
256        for &r in col {
257            if r < num_rows {
258                vec[r / 64] |= 1u64 << (r % 64);
259            }
260        }
261        for (pivot, bvec) in &basis {
262            if (vec[pivot / 64] >> (pivot % 64)) & 1 == 1 {
263                for w in 0..words {
264                    vec[w] ^= bvec[w];
265                }
266            }
267        }
268        let mut lead = None;
269        for (w_idx, &word) in vec.iter().enumerate() {
270            if word != 0 {
271                lead = Some(w_idx * 64 + word.trailing_zeros() as usize);
272                break;
273            }
274        }
275        if let Some(p) = lead {
276            basis.push((p, vec));
277            basis.sort_by_key(|(piv, _)| *piv);
278        }
279    }
280    basis.len()
281}
282
283fn compute_homology(rec: &BTreeMap<String, Value>) -> (i64, i64, i64, i64) {
284    let mut v_map: BTreeMap<u64, usize> = BTreeMap::new();
285    if let Some(Value::List(verts)) = rec.get("vertices") {
286        for v in verts {
287            let h = fnv1a_value(v);
288            let next = v_map.len();
289            v_map.entry(h).or_insert(next);
290        }
291    }
292    let mut edges: Vec<[usize; 2]> = Vec::new();
293    let mut e_map: BTreeMap<[usize; 2], usize> = BTreeMap::new();
294    if let Some(Value::List(raw_edges)) = rec.get("edges") {
295        for e in raw_edges {
296            if let Value::List(pair) = e {
297                if pair.len() >= 2 {
298                    let h0 = fnv1a_value(&pair[0]);
299                    let h1 = fnv1a_value(&pair[1]);
300                    let n0 = v_map.len();
301                    let u = *v_map.entry(h0).or_insert(n0);
302                    let n1 = v_map.len();
303                    let v = *v_map.entry(h1).or_insert(n1);
304                    if u != v {
305                        let key = if u < v { [u, v] } else { [v, u] };
306                        if !e_map.contains_key(&key) {
307                            let idx = edges.len();
308                            edges.push(key);
309                            e_map.insert(key, idx);
310                        }
311                    }
312                }
313            }
314        }
315    }
316    let mut d2_cols: Vec<Vec<usize>> = Vec::new();
317    let mut face_count = 0usize;
318    if let Some(Value::List(raw_faces)) = rec.get("faces") {
319        for f in raw_faces {
320            if let Value::List(tri) = f {
321                if tri.len() >= 3 {
322                    let mut vs: Vec<usize> = tri
323                        .iter()
324                        .take(3)
325                        .map(|val| {
326                            let h = fnv1a_value(val);
327                            let n = v_map.len();
328                            *v_map.entry(h).or_insert(n)
329                        })
330                        .collect();
331                    vs.sort_unstable();
332                    vs.dedup();
333                    if vs.len() == 3 {
334                        face_count += 1;
335                        let pairs = [[vs[0], vs[1]], [vs[0], vs[2]], [vs[1], vs[2]]];
336                        let mut col = Vec::with_capacity(3);
337                        for p in pairs {
338                            let idx = *e_map.entry(p).or_insert_with(|| {
339                                let i = edges.len();
340                                edges.push(p);
341                                i
342                            });
343                            col.push(idx);
344                        }
345                        d2_cols.push(col);
346                    }
347                }
348            }
349        }
350    }
351    let tet_count = match rec.get("tetrahedra") {
352        Some(Value::List(t)) => t.len() as i64,
353        _ => 0,
354    };
355    let v_count = v_map.len();
356    let e_count = edges.len();
357    let d1_cols: Vec<Vec<usize>> = edges.iter().map(|e| vec![e[0], e[1]]).collect();
358    let rank_d1 = gf2_rank(v_count, &d1_cols) as i64;
359    let rank_d2 = gf2_rank(e_count, &d2_cols) as i64;
360
361    let beta_0 = (v_count as i64 - rank_d1).max(0);
362    let beta_1 = ((e_count as i64 - rank_d1) - rank_d2).max(0);
363    let beta_2 = (face_count as i64 - rank_d2 - tet_count).max(0);
364    let euler = (v_count as i64) - (e_count as i64) + (face_count as i64) - tet_count;
365    (beta_0, beta_1, beta_2, euler)
366}
367
368fn topology_betti_and_voids(args: &[Value], span: Span) -> Result<Value, Diagnostic> {
369    let rec = extract_record(args, 0, "topology.betti_numbers", span)?;
370    let (beta_0, beta_1, beta_2, euler) = compute_homology(rec);
371    let mut out = BTreeMap::new();
372    out.insert("beta_0".into(), Value::I64(beta_0));
373    out.insert("beta_1".into(), Value::I64(beta_1));
374    out.insert("beta_2".into(), Value::I64(beta_2));
375    out.insert("euler_characteristic".into(), Value::I64(euler));
376    out.insert("has_voids".into(), Value::Bool(beta_1 > 0 || beta_2 > 0));
377    out.insert("unbridged_cycles".into(), Value::I64(beta_1));
378    Ok(Value::Record(out))
379}
380
381fn homotopy_verify_equivalence(args: &[Value], span: Span) -> Result<Value, Diagnostic> {
382    let rec_a = extract_record(args, 0, "homotopy.verify_equivalence", span)?;
383    let rec_b = extract_record(args, 1, "homotopy.verify_equivalence", span)?;
384    let (b0_a, b1_a, b2_a, chi_a) = compute_homology(rec_a);
385    let (b0_b, b1_b, b2_b, chi_b) = compute_homology(rec_b);
386    let inv_match = b0_a == b0_b && b1_a == b1_b && b2_a == b2_b && chi_a == chi_b;
387    let endpoints_match = rec_a.get("endpoints") == rec_b.get("endpoints");
388    let homotopic = inv_match && endpoints_match;
389    let dist = ((b0_a - b0_b).abs() + (b1_a - b1_b).abs() + (b2_a - b2_b).abs()) as f64;
390    let _ = fnv1a_64(b"homotopy");
391
392    let mut out = BTreeMap::new();
393    out.insert("homotopic".into(), Value::Bool(homotopic));
394    out.insert("invariant_match".into(), Value::Bool(inv_match));
395    out.insert("distance".into(), Value::F64(dist));
396    Ok(Value::Record(out))
397}