qualia_core_db/query/
indexing.rs

1use crate::NQuin;
2use std::collections::HashMap;
3
4/// In-memory inverted index over a `NQuin` collection.
5///
6/// Provides O(1) average lookup by subject, predicate, object, or context. Build once
7/// from a slice (`from_slice`) or grow incrementally (`insert`); the zero-alloc
8/// `iter_*` / `object_of` accessors yield copies, so they stay valid across the `Vec`
9/// reallocation an `insert` can trigger. Designed to live per 512 MB cell; wiring it to
10/// BIDX/demand-paging across cells is separate (task #22).
11pub struct QuinIndex {
12    quins: Vec<NQuin>,
13    by_subject: HashMap<u64, Vec<usize>>,
14    by_predicate: HashMap<u64, Vec<usize>>,
15    by_object: HashMap<u64, Vec<usize>>,
16    by_context: HashMap<u64, Vec<usize>>,
17}
18
19impl QuinIndex {
20    /// Build an index from a slice of quins (copied into the index).
21    pub fn from_slice(quins: &[NQuin]) -> Self {
22        let mut idx = Self {
23            quins: quins.to_vec(),
24            by_subject: HashMap::new(),
25            by_predicate: HashMap::new(),
26            by_object: HashMap::new(),
27            by_context: HashMap::new(),
28        };
29        for (i, q) in idx.quins.iter().enumerate() {
30            idx.by_subject.entry(q.subject).or_default().push(i);
31            idx.by_predicate.entry(q.predicate).or_default().push(i);
32            idx.by_object.entry(q.object).or_default().push(i);
33            idx.by_context.entry(q.context).or_default().push(i);
34        }
35        idx
36    }
37
38    /// Build an empty index and populate via `insert()`.
39    pub fn new() -> Self {
40        Self {
41            quins: Vec::new(),
42            by_subject: HashMap::new(),
43            by_predicate: HashMap::new(),
44            by_object: HashMap::new(),
45            by_context: HashMap::new(),
46        }
47    }
48
49    /// Insert a single quin into the index.
50    pub fn insert(&mut self, quin: NQuin) {
51        let i = self.quins.len();
52        self.by_subject.entry(quin.subject).or_default().push(i);
53        self.by_predicate.entry(quin.predicate).or_default().push(i);
54        self.by_object.entry(quin.object).or_default().push(i);
55        self.by_context.entry(quin.context).or_default().push(i);
56        self.quins.push(quin);
57    }
58
59    pub fn len(&self) -> usize {
60        self.quins.len()
61    }
62
63    pub fn is_empty(&self) -> bool {
64        self.quins.is_empty()
65    }
66
67    pub fn by_subject(&self, id: u64) -> Vec<NQuin> {
68        self.lookup(&self.by_subject, id)
69    }
70
71    pub fn by_predicate(&self, id: u64) -> Vec<NQuin> {
72        self.lookup(&self.by_predicate, id)
73    }
74
75    pub fn by_object(&self, id: u64) -> Vec<NQuin> {
76        self.lookup(&self.by_object, id)
77    }
78
79    pub fn by_context(&self, id: u64) -> Vec<NQuin> {
80        self.lookup(&self.by_context, id)
81    }
82
83    /// Returns all quins where subject==s AND predicate==p.
84    pub fn by_subject_and_predicate(&self, s: u64, p: u64) -> Vec<NQuin> {
85        let Some(rows) = self.by_subject.get(&s) else {
86            return vec![];
87        };
88        rows.iter()
89            .filter_map(|&i| {
90                let q = &self.quins[i];
91                if q.predicate == p {
92                    Some(*q)
93                } else {
94                    None
95                }
96            })
97            .collect()
98    }
99
100    // ── Zero-allocation accessors (the modal-kind resolution hot path, task #22) ──
101    // The `by_*` methods above each return `Vec<NQuin>` — one heap allocation per
102    // call, unacceptable for continuous resolution. These yield `NQuin` BY VALUE (it
103    // is `Copy`, 48 bytes) while borrowing the index: no per-call heap alloc, and —
104    // because they yield copies, not `&NQuin` into the backing `Vec` — they remain
105    // valid across the incremental `insert()` that may reallocate it. Keep them OUT of
106    // the SIMD/GPU vectorized loop (random-access gather): this is the CPU/logic-layer
107    // resolution path (see `frame_layout` "Tag policy").
108
109    /// Zero-alloc: every quin with this subject, yielded by copy.
110    pub fn iter_by_subject(&self, s: u64) -> impl Iterator<Item = NQuin> + '_ {
111        self.by_subject
112            .get(&s)
113            .map(Vec::as_slice)
114            .unwrap_or(&[])
115            .iter()
116            .map(move |&i| self.quins[i])
117    }
118
119    /// Zero-alloc: every quin matching subject AND predicate, yielded by copy.
120    pub fn iter_by_subject_and_predicate(
121        &self,
122        s: u64,
123        p: u64,
124    ) -> impl Iterator<Item = NQuin> + '_ {
125        self.iter_by_subject(s).filter(move |q| q.predicate == p)
126    }
127
128    /// Zero-alloc modal-kind resolution primitive: the first object of `(s, p)`.
129    /// e.g. `object_of(identifier, has_modality_kind)` resolves an identifier's kind
130    /// in one point lookup with no heap allocation.
131    pub fn object_of(&self, s: u64, p: u64) -> Option<u64> {
132        self.iter_by_subject_and_predicate(s, p)
133            .next()
134            .map(|q| q.object)
135    }
136
137    /// Zero-copy raw backing-store row indices for a subject, for callers that gather
138    /// into their own contiguous scratch buffer (pair with `quin_at`).
139    pub fn rows_by_subject(&self, s: u64) -> &[usize] {
140        self.by_subject.get(&s).map(Vec::as_slice).unwrap_or(&[])
141    }
142
143    /// The quin at a backing-store row index. Copy, no allocation.
144    #[inline]
145    pub fn quin_at(&self, i: usize) -> NQuin {
146        self.quins[i]
147    }
148
149    fn lookup(&self, map: &HashMap<u64, Vec<usize>>, key: u64) -> Vec<NQuin> {
150        map.get(&key)
151            .map(|indices| indices.iter().map(|&i| self.quins[i]).collect())
152            .unwrap_or_default()
153    }
154}
155
156impl Default for QuinIndex {
157    fn default() -> Self {
158        Self::new()
159    }
160}
161
162#[cfg(test)]
163mod tests {
164    use super::*;
165
166    fn make_quin(s: u64, p: u64, o: u64, c: u64) -> NQuin {
167        NQuin {
168            subject: s,
169            predicate: p,
170            object: o,
171            context: c,
172            metadata: 0,
173            parity: NQuin::calculate_parity(s, p, o, c, 0),
174        }
175    }
176
177    #[test]
178    fn index_lookup_by_subject() {
179        let quins = vec![
180            make_quin(1, 10, 100, 1000),
181            make_quin(2, 20, 200, 2000),
182            make_quin(1, 30, 300, 3000),
183        ];
184        let idx = QuinIndex::from_slice(&quins);
185        let hits = idx.by_subject(1);
186        assert_eq!(hits.len(), 2);
187        assert!(hits.iter().all(|q| q.subject == 1));
188    }
189
190    #[test]
191    fn index_lookup_by_context() {
192        let quins = vec![
193            make_quin(1, 10, 100, 42),
194            make_quin(2, 20, 200, 42),
195            make_quin(3, 30, 300, 99),
196        ];
197        let idx = QuinIndex::from_slice(&quins);
198        assert_eq!(idx.by_context(42).len(), 2);
199        assert_eq!(idx.by_context(99).len(), 1);
200        assert_eq!(idx.by_context(0).len(), 0);
201    }
202
203    #[test]
204    fn index_incremental_insert() {
205        let mut idx = QuinIndex::new();
206        idx.insert(make_quin(5, 6, 7, 8));
207        idx.insert(make_quin(5, 9, 10, 11));
208        assert_eq!(idx.len(), 2);
209        assert_eq!(idx.by_subject(5).len(), 2);
210    }
211
212    #[test]
213    fn index_subject_and_predicate() {
214        let quins = vec![
215            make_quin(1, 10, 100, 1000),
216            make_quin(1, 20, 200, 2000),
217            make_quin(2, 10, 300, 3000),
218        ];
219        let idx = QuinIndex::from_slice(&quins);
220        let hits = idx.by_subject_and_predicate(1, 10);
221        assert_eq!(hits.len(), 1);
222        assert_eq!(hits[0].object, 100);
223    }
224
225    #[test]
226    fn incremental_insert_survives_reallocation_with_zero_alloc_accessors() {
227        // Grow well past initial capacity so the backing Vec reallocates, then confirm
228        // the copy-yielding accessors still resolve correctly (the basis for per-cell
229        // incremental indexing — task #22).
230        let mut idx = QuinIndex::new();
231        // Kind subjects are OUTSIDE the growth range (0..2000) so each appears once.
232        idx.insert(make_quin(5000, 101, 12345, 0)); // before the growth
233        for i in 0..2000u64 {
234            idx.insert(make_quin(i, 200, i + 1, 0));
235        }
236        idx.insert(make_quin(6000, 101, 67890, 0)); // and one after
237        assert_eq!(idx.len(), 2002);
238
239        // object_of / iter_* yield copies, so they survive the reallocation above.
240        assert_eq!(idx.object_of(5000, 101), Some(12345));
241        assert_eq!(idx.object_of(6000, 101), Some(67890));
242        assert_eq!(idx.iter_by_subject(5000).count(), 1);
243        assert_eq!(idx.iter_by_subject_and_predicate(6000, 101).count(), 1);
244        assert!(idx.object_of(5000, 999).is_none());
245    }
246}
qualia_core_db/query/indexing.rs

qualia_core_db/query/
indexing.rs
