1use crate::indexing::QuinIndex;
2use crate::NQuin;
3
4use super::identity::{derive_prefix_identity, PrefixIdentity};
5
6#[repr(C)]
7#[derive(Clone, Copy, Debug, PartialEq, Eq)]
8pub struct GraphQuery {
9 pub context: u64,
11 pub subject: u64,
13 pub predicate: u64,
15 pub object: u64,
17}
18
19#[repr(C)]
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub struct GraphAssistPolicy {
22 pub max_facts: u32,
23 pub sensitivity_ceiling: u8,
24 pub require_valid_parity: bool,
25 pub _pad: [u8; 2],
26}
27
28impl Default for GraphAssistPolicy {
29 fn default() -> Self {
30 Self {
31 max_facts: 64,
32 sensitivity_ceiling: 0,
33 require_valid_parity: true,
34 _pad: [0; 2],
35 }
36 }
37}
38
39#[derive(Clone, Copy, Debug, PartialEq, Eq)]
40pub enum GraphQueryError {
41 InvalidPolicy,
42 OutputBufferFull,
43}
44
45#[repr(C)]
46#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
47pub struct GraphSelectionReceipt {
48 pub scanned: u32,
49 pub matched: u32,
50 pub written: u32,
51 pub rejected_sensitivity: u32,
52 pub rejected_parity: u32,
53 pub prefix_identity: PrefixIdentity,
54}
55
56#[inline]
57fn matches(query: &GraphQuery, quin: &NQuin) -> bool {
58 (query.context == 0 || query.context == quin.context)
59 && (query.subject == 0 || query.subject == quin.subject)
60 && (query.predicate == 0 || query.predicate == quin.predicate)
61 && (query.object == 0 || query.object == quin.object)
62}
63
64pub fn query_graph_into(
69 graph: &[NQuin],
70 query: &GraphQuery,
71 policy: GraphAssistPolicy,
72 model_instance: u64,
73 tokenizer_revision: u64,
74 graph_revision: u64,
75 out: &mut [NQuin],
76) -> Result<GraphSelectionReceipt, GraphQueryError> {
77 if policy.max_facts == 0 {
78 return Err(GraphQueryError::InvalidPolicy);
79 }
80 let capacity = out.len().min(policy.max_facts as usize);
81 let mut receipt = GraphSelectionReceipt::default();
82 for quin in graph {
83 receipt.scanned = receipt.scanned.saturating_add(1);
84 if !matches(query, quin) {
85 continue;
86 }
87 let sensitivity = (quin.context >> 56) as u8;
88 if sensitivity > policy.sensitivity_ceiling {
89 receipt.rejected_sensitivity = receipt.rejected_sensitivity.saturating_add(1);
90 continue;
91 }
92 if policy.require_valid_parity
93 && quin.parity != (quin.subject ^ quin.predicate ^ quin.object ^ quin.context)
94 {
95 receipt.rejected_parity = receipt.rejected_parity.saturating_add(1);
96 continue;
97 }
98 receipt.matched = receipt.matched.saturating_add(1);
99 if receipt.written as usize >= capacity {
100 return Err(GraphQueryError::OutputBufferFull);
101 }
102 out[receipt.written as usize] = *quin;
103 receipt.written += 1;
104 }
105 receipt.prefix_identity = derive_prefix_identity(
106 model_instance,
107 tokenizer_revision,
108 query.context,
109 graph_revision,
110 &out[..receipt.written as usize],
111 );
112 Ok(receipt)
113}
114
115pub fn query_graph_indexed_into(
121 graph: &[NQuin],
122 index: &QuinIndex,
123 query: &GraphQuery,
124 policy: GraphAssistPolicy,
125 model_instance: u64,
126 tokenizer_revision: u64,
127 graph_revision: u64,
128 out: &mut [NQuin],
129) -> Result<GraphSelectionReceipt, GraphQueryError> {
130 if policy.max_facts == 0 {
131 return Err(GraphQueryError::InvalidPolicy);
132 }
133 if (query.context == 0 && query.subject == 0 && query.predicate == 0 && query.object == 0)
135 || index.len() != graph.len()
136 {
137 return query_graph_into(
138 graph,
139 query,
140 policy,
141 model_instance,
142 tokenizer_revision,
143 graph_revision,
144 out,
145 );
146 }
147
148 let mut slices: [&[usize]; 4] = [&[]; 4];
149 let mut slice_count = 0usize;
150 if query.subject != 0 {
151 slices[slice_count] = index.rows_by_subject(query.subject);
152 slice_count += 1;
153 }
154 if query.predicate != 0 {
155 slices[slice_count] = index.rows_by_predicate(query.predicate);
156 slice_count += 1;
157 }
158 if query.object != 0 {
159 slices[slice_count] = index.rows_by_object(query.object);
160 slice_count += 1;
161 }
162 if query.context != 0 {
163 slices[slice_count] = index.rows_by_context(query.context);
164 slice_count += 1;
165 }
166
167 let mut best_idx = 0usize;
168 for i in 1..slice_count {
169 if slices[i].len() < slices[best_idx].len() {
170 best_idx = i;
171 }
172 }
173 let candidates = slices[best_idx];
174
175 let capacity = out.len().min(policy.max_facts as usize);
176 let mut receipt = GraphSelectionReceipt::default();
177 for &row_idx in candidates {
178 let Some(quin) = graph.get(row_idx) else {
179 continue;
180 };
181 receipt.scanned = receipt.scanned.saturating_add(1);
182 if !matches(query, quin) {
183 continue;
184 }
185 let sensitivity = (quin.context >> 56) as u8;
186 if sensitivity > policy.sensitivity_ceiling {
187 receipt.rejected_sensitivity = receipt.rejected_sensitivity.saturating_add(1);
188 continue;
189 }
190 if policy.require_valid_parity
191 && quin.parity != (quin.subject ^ quin.predicate ^ quin.object ^ quin.context)
192 {
193 receipt.rejected_parity = receipt.rejected_parity.saturating_add(1);
194 continue;
195 }
196 receipt.matched = receipt.matched.saturating_add(1);
197 if receipt.written as usize >= capacity {
198 return Err(GraphQueryError::OutputBufferFull);
199 }
200 out[receipt.written as usize] = *quin;
201 receipt.written += 1;
202 }
203 receipt.prefix_identity = derive_prefix_identity(
204 model_instance,
205 tokenizer_revision,
206 query.context,
207 graph_revision,
208 &out[..receipt.written as usize],
209 );
210 Ok(receipt)
211}
212
213#[cfg(test)]
214mod unit_tests {
215 use super::*;
216
217 fn make_quin(subject: u64, predicate: u64, object: u64, context: u64) -> NQuin {
218 NQuin {
219 subject,
220 predicate,
221 object,
222 context,
223 metadata: 0,
224 parity: subject ^ predicate ^ object ^ context,
225 }
226 }
227
228 #[test]
229 fn indexed_query_is_bit_exact_with_linear_scan_and_reduces_scanned_rows() {
230 let mut bad_parity = make_quin(1, 10, 999, 7);
231 bad_parity.parity ^= 1;
232 let restricted_ctx = (1u64 << 56) | 7;
233 let restricted = make_quin(1, 10, 888, restricted_ctx);
234
235 let graph = [
236 make_quin(1, 10, 100, 7),
237 make_quin(2, 20, 200, 7),
238 bad_parity,
239 make_quin(1, 10, 300, 7),
240 restricted,
241 make_quin(3, 10, 400, 8),
242 make_quin(4, 30, 500, 7),
243 make_quin(1, 10, 600, 7),
244 ];
245 let index = QuinIndex::from_slice(&graph);
246
247 let queries = [
248 GraphQuery {
250 context: 7,
251 subject: 1,
252 predicate: 10,
253 object: 0,
254 },
255 GraphQuery {
257 context: 0,
258 subject: 0,
259 predicate: 10,
260 object: 0,
261 },
262 GraphQuery {
264 context: 7,
265 subject: 0,
266 predicate: 10,
267 object: 300,
268 },
269 GraphQuery {
271 context: restricted_ctx,
272 subject: 1,
273 predicate: 10,
274 object: 0,
275 },
276 GraphQuery {
278 context: 7,
279 subject: 9999,
280 predicate: 10,
281 object: 0,
282 },
283 GraphQuery {
285 context: 0,
286 subject: 0,
287 predicate: 0,
288 object: 0,
289 },
290 ];
291
292 for query in &queries {
293 let mut out_linear = [NQuin::default(); 8];
294 let mut out_indexed = [NQuin::default(); 8];
295 let r_linear = query_graph_into(
296 &graph,
297 query,
298 GraphAssistPolicy::default(),
299 41,
300 42,
301 43,
302 &mut out_linear,
303 )
304 .unwrap();
305 let r_indexed = query_graph_indexed_into(
306 &graph,
307 &index,
308 query,
309 GraphAssistPolicy::default(),
310 41,
311 42,
312 43,
313 &mut out_indexed,
314 )
315 .unwrap();
316
317 assert_eq!(r_indexed.matched, r_linear.matched);
318 assert_eq!(r_indexed.written, r_linear.written);
319 assert_eq!(r_indexed.rejected_sensitivity, r_linear.rejected_sensitivity);
320 assert_eq!(r_indexed.rejected_parity, r_linear.rejected_parity);
321 assert_eq!(r_indexed.prefix_identity, r_linear.prefix_identity);
322 assert_eq!(out_indexed, out_linear);
323 assert!(r_indexed.scanned <= r_linear.scanned);
324 }
325
326 let mut out_narrow = [NQuin::default(); 4];
329 let r_narrow = query_graph_indexed_into(
330 &graph,
331 &index,
332 &queries[2],
333 GraphAssistPolicy::default(),
334 41,
335 42,
336 43,
337 &mut out_narrow,
338 )
339 .unwrap();
340 assert_eq!(r_narrow.scanned, 1);
341 assert_eq!(r_narrow.written, 1);
342 }
343
344 #[test]
345 fn indexed_query_matches_error_contracts() {
346 let graph = [make_quin(1, 10, 100, 7), make_quin(1, 10, 200, 7)];
347 let index = QuinIndex::from_slice(&graph);
348 let query = GraphQuery {
349 context: 7,
350 subject: 1,
351 predicate: 10,
352 object: 0,
353 };
354
355 let mut out = [NQuin::default(); 1];
356 let bad_policy = GraphAssistPolicy {
357 max_facts: 0,
358 ..GraphAssistPolicy::default()
359 };
360 assert_eq!(
361 query_graph_indexed_into(&graph, &index, &query, bad_policy, 1, 1, 1, &mut out),
362 Err(GraphQueryError::InvalidPolicy)
363 );
364 assert_eq!(
365 query_graph_indexed_into(
366 &graph,
367 &index,
368 &query,
369 GraphAssistPolicy::default(),
370 1,
371 1,
372 1,
373 &mut out
374 ),
375 Err(GraphQueryError::OutputBufferFull)
376 );
377 }
378}