Skip to main content

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    /// Indexed quins.
60    pub fn len(&self) -> usize {
61        self.quins.len()
62    }
63
64    /// `true` when empty.
65    pub fn is_empty(&self) -> bool {
66        self.quins.is_empty()
67    }
68
69    /// All quins with subject `id`.
70    pub fn by_subject(&self, id: u64) -> Vec<NQuin> {
71        self.lookup(&self.by_subject, id)
72    }
73
74    /// All quins with predicate `id`.
75    pub fn by_predicate(&self, id: u64) -> Vec<NQuin> {
76        self.lookup(&self.by_predicate, id)
77    }
78
79    /// All quins with object `id`.
80    pub fn by_object(&self, id: u64) -> Vec<NQuin> {
81        self.lookup(&self.by_object, id)
82    }
83
84    /// All quins with context `id`.
85    pub fn by_context(&self, id: u64) -> Vec<NQuin> {
86        self.lookup(&self.by_context, id)
87    }
88
89    /// Returns all quins where subject==s AND predicate==p.
90    pub fn by_subject_and_predicate(&self, s: u64, p: u64) -> Vec<NQuin> {
91        let Some(rows) = self.by_subject.get(&s) else {
92            return vec![];
93        };
94        rows.iter()
95            .filter_map(|&i| {
96                let q = &self.quins[i];
97                if q.predicate == p {
98                    Some(*q)
99                } else {
100                    None
101                }
102            })
103            .collect()
104    }
105
106    // ── Zero-allocation accessors (the modal-kind resolution hot path, task #22) ──
107    // The `by_*` methods above each return `Vec<NQuin>` — one heap allocation per
108    // call, unacceptable for continuous resolution. These yield `NQuin` BY VALUE (it
109    // is `Copy`, 48 bytes) while borrowing the index: no per-call heap alloc, and —
110    // because they yield copies, not `&NQuin` into the backing `Vec` — they remain
111    // valid across the incremental `insert()` that may reallocate it. Keep them OUT of
112    // the SIMD/GPU vectorized loop (random-access gather): this is the CPU/logic-layer
113    // resolution path (see `frame_layout` "Tag policy").
114
115    /// Zero-alloc: every quin with this subject, yielded by copy.
116    pub fn iter_by_subject(&self, s: u64) -> impl Iterator<Item = NQuin> + '_ {
117        self.by_subject
118            .get(&s)
119            .map(Vec::as_slice)
120            .unwrap_or(&[])
121            .iter()
122            .map(move |&i| self.quins[i])
123    }
124
125    /// Zero-alloc: every quin matching subject AND predicate, yielded by copy.
126    pub fn iter_by_subject_and_predicate(
127        &self,
128        s: u64,
129        p: u64,
130    ) -> impl Iterator<Item = NQuin> + '_ {
131        self.iter_by_subject(s).filter(move |q| q.predicate == p)
132    }
133
134    /// Zero-alloc modal-kind resolution primitive: the first object of `(s, p)`.
135    /// e.g. `object_of(identifier, has_modality_kind)` resolves an identifier's kind
136    /// in one point lookup with no heap allocation.
137    pub fn object_of(&self, s: u64, p: u64) -> Option<u64> {
138        self.iter_by_subject_and_predicate(s, p)
139            .next()
140            .map(|q| q.object)
141    }
142
143    /// Zero-copy raw backing-store row indices for a subject, for callers that gather
144    /// into their own contiguous scratch buffer (pair with `quin_at`).
145    pub fn rows_by_subject(&self, s: u64) -> &[usize] {
146        self.by_subject.get(&s).map(Vec::as_slice).unwrap_or(&[])
147    }
148
149    /// Zero-copy raw backing-store row indices for a predicate, in ascending row order.
150    pub fn rows_by_predicate(&self, p: u64) -> &[usize] {
151        self.by_predicate.get(&p).map(Vec::as_slice).unwrap_or(&[])
152    }
153
154    /// Zero-copy raw backing-store row indices for an object, in ascending row order.
155    pub fn rows_by_object(&self, o: u64) -> &[usize] {
156        self.by_object.get(&o).map(Vec::as_slice).unwrap_or(&[])
157    }
158
159    /// Zero-copy raw backing-store row indices for a context, in ascending row order.
160    pub fn rows_by_context(&self, c: u64) -> &[usize] {
161        self.by_context.get(&c).map(Vec::as_slice).unwrap_or(&[])
162    }
163
164    /// The quin at a backing-store row index. Copy, no allocation.
165    #[inline]
166    pub fn quin_at(&self, i: usize) -> NQuin {
167        self.quins[i]
168    }
169
170    fn lookup(&self, map: &HashMap<u64, Vec<usize>>, key: u64) -> Vec<NQuin> {
171        map.get(&key)
172            .map(|indices| indices.iter().map(|&i| self.quins[i]).collect())
173            .unwrap_or_default()
174    }
175}
176
177impl Default for QuinIndex {
178    fn default() -> Self {
179        Self::new()
180    }
181}
182
183#[cfg(test)]
184mod tests {
185    use super::*;
186
187    fn make_quin(s: u64, p: u64, o: u64, c: u64) -> NQuin {
188        NQuin {
189            subject: s,
190            predicate: p,
191            object: o,
192            context: c,
193            metadata: 0,
194            parity: NQuin::calculate_parity(s, p, o, c, 0),
195        }
196    }
197
198    #[test]
199    fn index_lookup_by_subject() {
200        let quins = vec![
201            make_quin(1, 10, 100, 1000),
202            make_quin(2, 20, 200, 2000),
203            make_quin(1, 30, 300, 3000),
204        ];
205        let idx = QuinIndex::from_slice(&quins);
206        let hits = idx.by_subject(1);
207        assert_eq!(hits.len(), 2);
208        assert!(hits.iter().all(|q| q.subject == 1));
209    }
210
211    #[test]
212    fn index_lookup_by_context() {
213        let quins = vec![
214            make_quin(1, 10, 100, 42),
215            make_quin(2, 20, 200, 42),
216            make_quin(3, 30, 300, 99),
217        ];
218        let idx = QuinIndex::from_slice(&quins);
219        assert_eq!(idx.by_context(42).len(), 2);
220        assert_eq!(idx.by_context(99).len(), 1);
221        assert_eq!(idx.by_context(0).len(), 0);
222    }
223
224    #[test]
225    fn index_incremental_insert() {
226        let mut idx = QuinIndex::new();
227        idx.insert(make_quin(5, 6, 7, 8));
228        idx.insert(make_quin(5, 9, 10, 11));
229        assert_eq!(idx.len(), 2);
230        assert_eq!(idx.by_subject(5).len(), 2);
231    }
232
233    #[test]
234    fn index_subject_and_predicate() {
235        let quins = vec![
236            make_quin(1, 10, 100, 1000),
237            make_quin(1, 20, 200, 2000),
238            make_quin(2, 10, 300, 3000),
239        ];
240        let idx = QuinIndex::from_slice(&quins);
241        let hits = idx.by_subject_and_predicate(1, 10);
242        assert_eq!(hits.len(), 1);
243        assert_eq!(hits[0].object, 100);
244    }
245
246    #[test]
247    fn incremental_insert_survives_reallocation_with_zero_alloc_accessors() {
248        // Grow well past initial capacity so the backing Vec reallocates, then confirm
249        // the copy-yielding accessors still resolve correctly (the basis for per-cell
250        // incremental indexing — task #22).
251        let mut idx = QuinIndex::new();
252        // Kind subjects are OUTSIDE the growth range (0..2000) so each appears once.
253        idx.insert(make_quin(5000, 101, 12345, 0)); // before the growth
254        for i in 0..2000u64 {
255            idx.insert(make_quin(i, 200, i + 1, 0));
256        }
257        idx.insert(make_quin(6000, 101, 67890, 0)); // and one after
258        assert_eq!(idx.len(), 2002);
259
260        // object_of / iter_* yield copies, so they survive the reallocation above.
261        assert_eq!(idx.object_of(5000, 101), Some(12345));
262        assert_eq!(idx.object_of(6000, 101), Some(67890));
263        assert_eq!(idx.iter_by_subject(5000).count(), 1);
264        assert_eq!(idx.iter_by_subject_and_predicate(6000, 101).count(), 1);
265        assert!(idx.object_of(5000, 999).is_none());
266    }
267}