terminals_core/substrate/
graph.rs

1//! GraphProjection — HNSW neighbor topology + p-adic address.
2//!
3//! Stores the atom's position in the approximate nearest neighbor graph
4//! and its hierarchical locality label (p-adic address).
5
6use super::projection::{Projection, ProjectionId};
7
8/// Max neighbor slots per atom in the HNSW graph.
9pub const MAX_NEIGHBORS: usize = 8;
10
11/// Bytes: 8 neighbors × 2 (u16) + 1 layer (u8) + 3 padding + 12 address bytes = 32 bytes.
12/// Simplified: neighbors(16) + layer(4 as f32) + address base(4) + address coeffs(8) = 32.
13const GRAPH_BYTES: usize = MAX_NEIGHBORS * 2 + 4 + 4 + 8;
14
15/// P-adic address: hierarchical locality label.
16/// Format: "kindIndex.depth.counter" encoded as (base: u32, coeff0: u16, coeff1: u16).
17#[derive(Debug, Clone, Copy, Default, PartialEq, serde::Serialize, serde::Deserialize)]
18pub struct PadicAddr {
19    pub base: u32,
20    pub coeff0: u16,
21    pub coeff1: u16,
22}
23
24impl PadicAddr {
25    /// Format as "base.coeff0.coeff1" string.
26    pub fn to_string(&self) -> String {
27        format!("{}.{}.{}", self.base, self.coeff0, self.coeff1)
28    }
29}
30
31#[derive(Debug, Clone)]
32pub struct GraphProjection {
33    /// Neighbor indices in the HNSW graph (u16::MAX = empty slot).
34    pub neighbors: [u16; MAX_NEIGHBORS],
35    /// HNSW layer level.
36    pub layer: u8,
37    /// P-adic hierarchical address.
38    pub address: PadicAddr,
39}
40
41impl Default for GraphProjection {
42    fn default() -> Self {
43        Self {
44            neighbors: [u16::MAX; MAX_NEIGHBORS],
45            layer: 0,
46            address: PadicAddr::default(),
47        }
48    }
49}
50
51impl Projection for GraphProjection {
52    fn byte_size() -> usize {
53        GRAPH_BYTES
54    }
55
56    fn id() -> ProjectionId {
57        ProjectionId::Graph
58    }
59
60    fn read(buf: &[u8]) -> Self {
61        assert!(buf.len() >= GRAPH_BYTES);
62        let mut neighbors = [u16::MAX; MAX_NEIGHBORS];
63        for i in 0..MAX_NEIGHBORS {
64            let off = i * 2;
65            neighbors[i] = u16::from_le_bytes([buf[off], buf[off + 1]]);
66        }
67        let layer_off = MAX_NEIGHBORS * 2;
68        let layer = buf[layer_off];
69
70        let addr_off = layer_off + 4; // 3 bytes padding after layer
71        let base = u32::from_le_bytes([
72            buf[addr_off],
73            buf[addr_off + 1],
74            buf[addr_off + 2],
75            buf[addr_off + 3],
76        ]);
77        let coeff0 = u16::from_le_bytes([buf[addr_off + 4], buf[addr_off + 5]]);
78        let coeff1 = u16::from_le_bytes([buf[addr_off + 6], buf[addr_off + 7]]);
79
80        Self {
81            neighbors,
82            layer,
83            address: PadicAddr {
84                base,
85                coeff0,
86                coeff1,
87            },
88        }
89    }
90
91    fn write(&self, buf: &mut [u8]) {
92        assert!(buf.len() >= GRAPH_BYTES);
93        for i in 0..MAX_NEIGHBORS {
94            let off = i * 2;
95            buf[off..off + 2].copy_from_slice(&self.neighbors[i].to_le_bytes());
96        }
97        let layer_off = MAX_NEIGHBORS * 2;
98        buf[layer_off] = self.layer;
99        buf[layer_off + 1] = 0; // padding
100        buf[layer_off + 2] = 0;
101        buf[layer_off + 3] = 0;
102
103        let addr_off = layer_off + 4;
104        buf[addr_off..addr_off + 4].copy_from_slice(&self.address.base.to_le_bytes());
105        buf[addr_off + 4..addr_off + 6].copy_from_slice(&self.address.coeff0.to_le_bytes());
106        buf[addr_off + 6..addr_off + 8].copy_from_slice(&self.address.coeff1.to_le_bytes());
107    }
108
109    fn shape_hash_contribution(&self) -> u32 {
110        let mut hash = 0x811c_9dc5u32;
111        // Hash the neighbor topology (which connections exist)
112        for &n in &self.neighbors {
113            for byte in n.to_le_bytes() {
114                hash ^= byte as u32;
115                hash = hash.wrapping_mul(0x0100_0193);
116            }
117        }
118        hash
119    }
120}
121
122#[cfg(test)]
123mod tests {
124    use super::*;
125
126    #[test]
127    fn test_graph_byte_size() {
128        assert_eq!(GraphProjection::byte_size(), 32);
129    }
130
131    #[test]
132    fn test_graph_roundtrip() {
133        let mut proj = GraphProjection::default();
134        proj.neighbors[0] = 42;
135        proj.neighbors[3] = 100;
136        proj.layer = 2;
137        proj.address = PadicAddr {
138            base: 5,
139            coeff0: 1,
140            coeff1: 77,
141        };
142
143        let mut buf = vec![0u8; GraphProjection::byte_size()];
144        proj.write(&mut buf);
145        let restored = GraphProjection::read(&buf);
146
147        assert_eq!(restored.neighbors[0], 42);
148        assert_eq!(restored.neighbors[3], 100);
149        assert_eq!(restored.neighbors[7], u16::MAX); // empty slot
150        assert_eq!(restored.layer, 2);
151        assert_eq!(restored.address.base, 5);
152        assert_eq!(restored.address.coeff0, 1);
153        assert_eq!(restored.address.coeff1, 77);
154    }
155
156    #[test]
157    fn test_padic_to_string() {
158        let addr = PadicAddr {
159            base: 3,
160            coeff0: 0,
161            coeff1: 42,
162        };
163        assert_eq!(addr.to_string(), "3.0.42");
164    }
165}
terminals_core/substrate/graph.rs

terminals_core/substrate/
graph.rs
