1use std::io;
4
5use super::super::{
6 header_from_bytes, BlockDirectoryEntry, Q42VolumeHeader, BIDX_MAGIC, FIELD_RANGE_INDEX_MAGIC,
7 FLAG_BLOCKS_LZ4, HEADER_SIZE, MAX_COMPRESSED_SUPERBLOCK_SIZE, Q42_VERSION_V3, Q42_VERSION_V4,
8 QUINS_PER_BLOCK, QUIN_SIZE, SUPERBLOCK_HEADER, SUPERBLOCK_SIZE,
9};
10use super::index::{BidxBlockRange, BidxMatchPage};
11use super::range::{Q42ByteRange, Q42RangeSource};
12use crate::NQuin;
13
14const BIDX_HEADER_BYTES: usize = 16;
15const BIDX_ENTRY_BYTES: usize = 16;
16const FIELD_RANGE_INDEX_HEADER_BYTES: usize = 16;
17const FIELD_RANGE_INDEX_ENTRY_BYTES: usize = 48;
18
19fn invalid(message: impl Into<String>) -> io::Error {
21 io::Error::new(io::ErrorKind::InvalidData, message.into())
22}
23
24fn verify_decoded_superblock(decoded: &[u8]) -> io::Result<()> {
26 if decoded.len() != SUPERBLOCK_SIZE {
27 return Err(invalid("decoded Q42 SuperBlock has the wrong length"));
28 }
29 let count = u64::from_le_bytes(decoded[16..24].try_into().unwrap()) as usize;
30 if count > QUINS_PER_BLOCK {
31 return Err(invalid(
32 "decoded Q42 SuperBlock Quin count exceeds capacity",
33 ));
34 }
35 let occupied = SUPERBLOCK_HEADER + count * QUIN_SIZE;
36 if occupied > SUPERBLOCK_SIZE {
37 return Err(invalid(
38 "decoded Q42 SuperBlock Quin payload overruns the block",
39 ));
40 }
41 Ok(())
42}
43
44pub struct Q42RangeVolume<S: Q42RangeSource> {
47 source: S,
48 header: Q42VolumeHeader,
49 source_length: u64,
50}
51
52#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
55pub struct Q42ObjectSearchCursor {
56 pub block_offset: usize,
58 pub quin_offset: usize,
60}
61
62#[derive(Clone, Copy, Debug, Eq, PartialEq)]
64pub struct Q42ObjectMatchPage {
65 pub block_range: BidxBlockRange,
66 pub returned: usize,
67 pub next_cursor: Option<Q42ObjectSearchCursor>,
68}
69
70#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
74pub struct Q42RangeQueryPattern {
75 pub subject: Option<u64>,
76 pub predicate: Option<u64>,
77 pub object: Option<u64>,
78 pub context: Option<u64>,
79}
80
81#[derive(Clone, Copy, Debug, Eq, PartialEq)]
82pub enum Q42RangeQueryStrategy {
83 ObjectBidx,
84 FieldRanges,
85 Sequential,
86}
87
88#[derive(Clone, Copy, Debug, Eq, PartialEq)]
89pub struct Q42RangeQueryPlan {
90 pub pattern: Q42RangeQueryPattern,
91 pub strategy: Q42RangeQueryStrategy,
92}
93
94impl Q42RangeQueryPlan {
95 pub fn for_pattern(pattern: Q42RangeQueryPattern) -> Self {
99 Self {
100 strategy: if pattern.object.is_some() {
101 Q42RangeQueryStrategy::ObjectBidx
102 } else if pattern.subject.is_some()
103 || pattern.predicate.is_some()
104 || pattern.context.is_some()
105 {
106 Q42RangeQueryStrategy::FieldRanges
107 } else {
108 Q42RangeQueryStrategy::Sequential
109 },
110 pattern,
111 }
112 }
113}
114
115#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
117pub struct Q42RangeQueryCursor {
118 pub block_index: usize,
119 pub quin_offset: usize,
120}
121
122#[derive(Clone, Copy, Debug, Eq, PartialEq)]
123pub struct Q42RangeQueryPage {
124 pub returned: usize,
125 pub next_cursor: Option<Q42RangeQueryCursor>,
126}
127
128impl<S: Q42RangeSource> Q42RangeVolume<S> {
129 pub fn open(source: S) -> io::Result<Self> {
133 let source_length = source.length()?;
134 if source_length < HEADER_SIZE as u64 {
135 return Err(invalid("Q42 range source is shorter than its header"));
136 }
137 let mut bytes = [0u8; HEADER_SIZE];
138 source.read_range_into(
139 Q42ByteRange {
140 offset: 0,
141 length: HEADER_SIZE,
142 },
143 &mut bytes,
144 )?;
145 let header = header_from_bytes(&bytes)?;
146 let version = header.version;
147 let flags = header.flags;
148 let block_size = header.block_size;
149 let quins_per_block = header.quins_per_block;
150 if (version != Q42_VERSION_V3 && version != Q42_VERSION_V4)
151 || flags & FLAG_BLOCKS_LZ4 == 0
152 || block_size != SUPERBLOCK_SIZE as u32
153 || quins_per_block != QUINS_PER_BLOCK as u32
154 {
155 return Err(invalid("unsupported Q42 range-volume header"));
156 }
157 for (name, offset, length) in [
158 ("lexicon", header.lex_offset, header.lex_length),
159 ("BIDX", header.bidx_offset, header.bidx_length),
160 match header.field_range_index_range() {
161 Some((offset, length)) => ("field-range index", offset, length),
162 None => ("field-range index", 0, 0),
163 },
164 (
165 "block directory",
166 header.block_dir_offset,
167 header.block_dir_length,
168 ),
169 ("block data", header.data_offset, header.data_length),
170 ] {
171 if length != 0
172 && (offset < HEADER_SIZE as u64
173 || offset
174 .checked_add(length)
175 .is_none_or(|end| end > source_length))
176 {
177 return Err(invalid(format!(
178 "Q42 {name} section lies outside the range source"
179 )));
180 }
181 }
182 let expected_directory = header
183 .block_count
184 .checked_mul(BlockDirectoryEntry::SIZE as u64)
185 .ok_or_else(|| invalid("Q42 directory length overflow"))?;
186 if header.block_dir_length != expected_directory {
187 return Err(invalid("Q42 directory does not match its block count"));
188 }
189 let volume = Self {
190 source,
191 header,
192 source_length,
193 };
194 volume.bidx_block_count()?;
195 volume.validate_field_range_index()?;
196 volume.validate_field_postings()?;
197 Ok(volume)
198 }
199
200 pub fn header(&self) -> &Q42VolumeHeader {
202 &self.header
203 }
204 pub fn source_length(&self) -> u64 {
206 self.source_length
207 }
208 pub fn block_count(&self) -> u64 {
210 self.header.block_count
211 }
212
213 pub fn execute_query_page_into(
218 &self,
219 plan: Q42RangeQueryPlan,
220 cursor: Q42RangeQueryCursor,
221 compressed: &mut [u8],
222 decoded: &mut [u8],
223 out: &mut [NQuin],
224 ) -> io::Result<Q42RangeQueryPage> {
225 if out.is_empty() {
226 return Err(io::Error::new(
227 io::ErrorKind::InvalidInput,
228 "Q42 query output buffer is empty",
229 ));
230 }
231 let (start, end) = match plan.strategy {
232 Q42RangeQueryStrategy::ObjectBidx => match self.bidx_block_range_for_hash(
233 plan.pattern
234 .object
235 .expect("object strategy requires object"),
236 )? {
237 Some(range) => (range.start, range.end),
238 None => {
239 return Ok(Q42RangeQueryPage {
240 returned: 0,
241 next_cursor: None,
242 })
243 }
244 },
245 Q42RangeQueryStrategy::FieldRanges | Q42RangeQueryStrategy::Sequential => {
246 (0, self.header.block_count as usize)
247 }
248 };
249 let mut block_index = cursor.block_index.max(start);
250 let mut quin_offset = if block_index == cursor.block_index {
251 cursor.quin_offset
252 } else {
253 0
254 };
255 let mut returned = 0usize;
256 while block_index < end {
257 if plan.strategy == Q42RangeQueryStrategy::FieldRanges
258 && !self.field_membership_may_match(block_index, plan.pattern)?
259 {
260 block_index += 1;
261 quin_offset = 0;
262 continue;
263 }
264 self.read_superblock_into(block_index, compressed, decoded)?;
265 let count = u64::from_le_bytes(decoded[16..24].try_into().unwrap()) as usize;
266 if count > QUINS_PER_BLOCK {
267 return Err(invalid("Q42 decoded SuperBlock has invalid Quin count"));
268 }
269 while quin_offset < count {
270 let offset = SUPERBLOCK_HEADER + quin_offset * QUIN_SIZE;
271 let quin = NQuin {
272 subject: u64::from_le_bytes(decoded[offset..offset + 8].try_into().unwrap()),
273 predicate: u64::from_le_bytes(
274 decoded[offset + 8..offset + 16].try_into().unwrap(),
275 ),
276 object: u64::from_le_bytes(
277 decoded[offset + 16..offset + 24].try_into().unwrap(),
278 ),
279 context: u64::from_le_bytes(
280 decoded[offset + 24..offset + 32].try_into().unwrap(),
281 ),
282 metadata: u64::from_le_bytes(
283 decoded[offset + 32..offset + 40].try_into().unwrap(),
284 ),
285 parity: u64::from_le_bytes(
286 decoded[offset + 40..offset + 48].try_into().unwrap(),
287 ),
288 };
289 quin_offset += 1;
290 let pattern = plan.pattern;
291 if pattern.subject.is_some_and(|value| value != quin.subject)
292 || pattern
293 .predicate
294 .is_some_and(|value| value != quin.predicate)
295 || pattern.object.is_some_and(|value| value != quin.object)
296 || pattern.context.is_some_and(|value| value != quin.context)
297 {
298 continue;
299 }
300 out[returned] = quin;
301 returned += 1;
302 if returned == out.len() {
303 let next = if quin_offset < count {
304 Some(Q42RangeQueryCursor {
305 block_index,
306 quin_offset,
307 })
308 } else if block_index + 1 < end {
309 Some(Q42RangeQueryCursor {
310 block_index: block_index + 1,
311 quin_offset: 0,
312 })
313 } else {
314 None
315 };
316 return Ok(Q42RangeQueryPage {
317 returned,
318 next_cursor: next,
319 });
320 }
321 }
322 block_index += 1;
323 quin_offset = 0;
324 }
325 Ok(Q42RangeQueryPage {
326 returned,
327 next_cursor: None,
328 })
329 }
330 pub fn source(&self) -> &S {
332 &self.source
333 }
334
335 pub fn read_lexicon_into(&self, out: &mut [u8]) -> io::Result<()> {
338 self.read_section(self.header.lex_offset, self.header.lex_length, out)
339 }
340
341 pub fn read_lexicon_prefix_into(
344 &self,
345 out: &mut [u8; crate::q42_lex::LEX_HEADER_SIZE],
346 ) -> io::Result<()> {
347 if self.header.lex_length < crate::q42_lex::LEX_HEADER_SIZE as u64 {
348 return Err(invalid("Q42 lexicon is shorter than its fixed header"));
349 }
350 self.source.read_range_into(
351 Q42ByteRange {
352 offset: self.header.lex_offset,
353 length: crate::q42_lex::LEX_HEADER_SIZE,
354 },
355 out,
356 )
357 }
358
359 pub fn lookup_lexicon_hash_into(
364 &self,
365 hash: u64,
366 page_scratch: &mut [u8],
367 out: &mut [u8],
368 ) -> io::Result<Option<usize>> {
369 use crate::q42_lex::{
370 LEX_HEADER_SIZE, LEX_MAGIC, LEX_TAG_NAMESPACED, LEX_VERSION_PAGED, LEX_VERSION_V4,
371 PAGED_DIRECTORY_ENTRY_SIZE, PAGED_DIRECTORY_HEADER_SIZE, PAGED_PAGE_HEADER_SIZE,
372 };
373 if self.header.lex_length < (LEX_HEADER_SIZE + PAGED_DIRECTORY_HEADER_SIZE) as u64 {
374 return Err(invalid("Q42 lexicon is too short for paged lookup"));
375 }
376 let mut header = [0u8; LEX_HEADER_SIZE];
377 self.source.read_range_into(
378 Q42ByteRange {
379 offset: self.header.lex_offset,
380 length: LEX_HEADER_SIZE,
381 },
382 &mut header,
383 )?;
384 let lex_version = u64::from_le_bytes(header[24..32].try_into().unwrap());
385 if header[0..8] != LEX_MAGIC
386 || (lex_version != LEX_VERSION_PAGED && lex_version != LEX_VERSION_V4)
387 {
388 return Err(io::Error::new(
389 io::ErrorKind::Unsupported,
390 "Q42 range lexicon is not paged Q42LEX v2/v4",
391 ));
392 }
393 let directory_offset = u64::from_le_bytes(header[16..24].try_into().unwrap());
394 if directory_offset != LEX_HEADER_SIZE as u64 {
395 return Err(invalid("Q42 paged lexicon has an invalid directory offset"));
396 }
397 let mut page_count_bytes = [0u8; PAGED_DIRECTORY_HEADER_SIZE];
398 self.source.read_range_into(
399 Q42ByteRange {
400 offset: self.header.lex_offset + directory_offset,
401 length: PAGED_DIRECTORY_HEADER_SIZE,
402 },
403 &mut page_count_bytes,
404 )?;
405 let page_count = usize::try_from(u64::from_le_bytes(page_count_bytes))
406 .map_err(|_| invalid("Q42 paged lexicon page count exceeds platform"))?;
407 let mut lo = 0usize;
408 let mut hi = page_count;
409 let mut entry = [0u8; PAGED_DIRECTORY_ENTRY_SIZE];
410 while lo < hi {
411 let mid = lo + (hi - lo) / 2;
412 let offset = self.header.lex_offset
413 + directory_offset
414 + PAGED_DIRECTORY_HEADER_SIZE as u64
415 + (mid * PAGED_DIRECTORY_ENTRY_SIZE) as u64;
416 self.source.read_range_into(
417 Q42ByteRange {
418 offset,
419 length: PAGED_DIRECTORY_ENTRY_SIZE,
420 },
421 &mut entry,
422 )?;
423 if u64::from_le_bytes(entry[0..8].try_into().unwrap()) <= hash {
424 lo = mid + 1;
425 } else {
426 hi = mid;
427 }
428 }
429 let Some(page_index) = lo.checked_sub(1) else {
430 return Ok(None);
431 };
432 let offset = self.header.lex_offset
433 + directory_offset
434 + PAGED_DIRECTORY_HEADER_SIZE as u64
435 + (page_index * PAGED_DIRECTORY_ENTRY_SIZE) as u64;
436 self.source.read_range_into(
437 Q42ByteRange {
438 offset,
439 length: PAGED_DIRECTORY_ENTRY_SIZE,
440 },
441 &mut entry,
442 )?;
443 let page_offset = u64::from_le_bytes(entry[8..16].try_into().unwrap());
444 let page_length = usize::try_from(u64::from_le_bytes(entry[16..24].try_into().unwrap()))
445 .map_err(|_| invalid("Q42 lexicon page exceeds platform"))?;
446 let count = u32::from_le_bytes(entry[24..28].try_into().unwrap()) as usize;
447 if page_length > page_scratch.len()
448 || page_length < PAGED_PAGE_HEADER_SIZE
449 || page_offset
450 .checked_add(page_length as u64)
451 .is_none_or(|end| end > self.header.lex_length)
452 {
453 return Err(invalid(
454 "Q42 lexicon page is out of bounds or exceeds scratch",
455 ));
456 }
457 let page = &mut page_scratch[..page_length];
458 self.source.read_range_into(
459 Q42ByteRange {
460 offset: self.header.lex_offset + page_offset,
461 length: page_length,
462 },
463 page,
464 )?;
465 let declared_count = u32::from_le_bytes(page[0..4].try_into().unwrap()) as usize;
466 let blob_offset = usize::try_from(u64::from_le_bytes(page[8..16].try_into().unwrap()))
467 .map_err(|_| invalid("Q42 lexicon blob offset exceeds platform"))?;
468 if declared_count != count
469 || blob_offset != PAGED_PAGE_HEADER_SIZE + count * 16
470 || blob_offset > page.len()
471 {
472 return Err(invalid("Q42 lexicon page is malformed"));
473 }
474 let mut left = 0usize;
475 let mut right = count;
476 while left < right {
477 let mid = left + (right - left) / 2;
478 let index = PAGED_PAGE_HEADER_SIZE + mid * 16;
479 let entry_hash = u64::from_le_bytes(page[index..index + 8].try_into().unwrap());
480 if entry_hash < hash {
481 left = mid + 1;
482 continue;
483 }
484 if entry_hash > hash {
485 right = mid;
486 continue;
487 }
488 let relative = usize::try_from(u64::from_le_bytes(
489 page[index + 8..index + 16].try_into().unwrap(),
490 ))
491 .map_err(|_| invalid("Q42 lexicon string offset exceeds platform"))?;
492 let start = blob_offset
493 .checked_add(relative)
494 .ok_or_else(|| invalid("Q42 lexicon string offset overflow"))?;
495 if start + 3 > page.len() {
496 return Err(invalid("Q42 lexicon string entry is malformed"));
497 }
498 let tag = page[start];
499 if tag == 1 {
500 let length =
501 u16::from_le_bytes(page[start + 1..start + 3].try_into().unwrap()) as usize;
502 let end = start
503 .checked_add(3 + length)
504 .ok_or_else(|| invalid("Q42 lexicon string length overflow"))?;
505 if end > page.len() {
506 return Err(invalid("Q42 lexicon string extends beyond page"));
507 }
508 if length > out.len() {
509 return Err(io::Error::new(
510 io::ErrorKind::WriteZero,
511 "Q42 lexicon output buffer is too small",
512 ));
513 }
514 std::str::from_utf8(&page[start + 3..end])
515 .map_err(|_| invalid("Q42 lexicon string is not UTF-8"))?;
516 out[..length].copy_from_slice(&page[start + 3..end]);
517 return Ok(Some(length));
518 }
519 if tag == LEX_TAG_NAMESPACED && lex_version == LEX_VERSION_V4 {
520 if start + 5 > page.len() {
521 return Err(invalid("Q42 lexicon namespaced entry is malformed"));
522 }
523 let ns_id =
524 u16::from_le_bytes(page[start + 1..start + 3].try_into().unwrap()) as usize;
525 let local_len =
526 u16::from_le_bytes(page[start + 3..start + 5].try_into().unwrap()) as usize;
527 let local_start = start + 5;
528 let local_end = local_start
529 .checked_add(local_len)
530 .ok_or_else(|| invalid("Q42 lexicon local name length overflow"))?;
531 if local_end > page.len() {
532 return Err(invalid("Q42 lexicon local name extends beyond page"));
533 }
534 let ns_count = u32::from_le_bytes(page[4..8].try_into().unwrap()) as usize;
538 if ns_id >= ns_count {
539 return Err(invalid("Q42 lexicon namespace id is out of range"));
540 }
541 let mut cursor = blob_offset;
543 for _ in 0..ns_id {
544 if cursor + 2 > page.len() {
545 return Err(invalid("Q42 lexicon namespace table is malformed"));
546 }
547 let len =
548 u16::from_le_bytes(page[cursor..cursor + 2].try_into().unwrap()) as usize;
549 cursor = cursor
550 .checked_add(2 + len)
551 .ok_or_else(|| invalid("Q42 lexicon namespace table overflow"))?;
552 }
553 if cursor + 2 > page.len() {
554 return Err(invalid("Q42 lexicon namespace table is malformed"));
555 }
556 let ns_len =
557 u16::from_le_bytes(page[cursor..cursor + 2].try_into().unwrap()) as usize;
558 let ns_start = cursor + 2;
559 let ns_end = ns_start
560 .checked_add(ns_len)
561 .ok_or_else(|| invalid("Q42 lexicon namespace length overflow"))?;
562 if ns_end > page.len() {
563 return Err(invalid("Q42 lexicon namespace extends beyond page"));
564 }
565 let total = ns_len + local_len;
566 if total > out.len() {
567 return Err(io::Error::new(
568 io::ErrorKind::WriteZero,
569 "Q42 lexicon output buffer is too small",
570 ));
571 }
572 std::str::from_utf8(&page[ns_start..ns_end])
573 .map_err(|_| invalid("Q42 lexicon namespace is not UTF-8"))?;
574 std::str::from_utf8(&page[local_start..local_end])
575 .map_err(|_| invalid("Q42 lexicon local name is not UTF-8"))?;
576 out[..ns_len].copy_from_slice(&page[ns_start..ns_end]);
577 out[ns_len..total].copy_from_slice(&page[local_start..local_end]);
578 return Ok(Some(total));
579 }
580 return Err(invalid("Q42 lexicon string entry is malformed"));
581 }
582 Ok(None)
583 }
584 pub fn read_bidx_into(&self, out: &mut [u8]) -> io::Result<()> {
587 self.read_section(self.header.bidx_offset, self.header.bidx_length, out)
588 }
589
590 pub fn volume_manifest_length(&self) -> io::Result<Option<usize>> {
594 let Some((offset, length)) = self.header.volume_manifest_range() else {
595 return Ok(None);
596 };
597 let length =
598 usize::try_from(length).map_err(|_| invalid("Q42 manifest exceeds platform"))?;
599 if length == 0 || length > super::manifest::MAX_VOLUME_MANIFEST_BYTES {
600 return Err(invalid(
601 "Q42 root has an invalid embedded volume manifest length",
602 ));
603 }
604 Q42ByteRange { offset, length }.validate_for(self.source_length)?;
605 Ok(Some(length))
606 }
607
608 pub fn read_volume_manifest_into(&self, out: &mut [u8]) -> io::Result<bool> {
612 let Some(length) = self.volume_manifest_length()? else {
613 return Ok(false);
614 };
615 if out.len() != length {
616 return Err(io::Error::new(
617 io::ErrorKind::InvalidInput,
618 "Q42 manifest output buffer has wrong length",
619 ));
620 }
621 let (offset, _) = self
622 .header
623 .volume_manifest_range()
624 .expect("manifest length was present");
625 self.source
626 .read_range_into(Q42ByteRange { offset, length }, out)?;
627 Ok(true)
628 }
629 fn read_section(&self, offset: u64, length: u64, out: &mut [u8]) -> io::Result<()> {
632 let length =
633 usize::try_from(length).map_err(|_| invalid("Q42 section exceeds platform"))?;
634 if out.len() != length {
635 return Err(io::Error::new(
636 io::ErrorKind::InvalidInput,
637 "Q42 section output buffer has wrong length",
638 ));
639 }
640 self.source
641 .read_range_into(Q42ByteRange { offset, length }, out)
642 }
643
644 pub fn block_directory_entry(&self, index: usize) -> io::Result<BlockDirectoryEntry> {
647 if index >= self.header.block_count as usize {
648 return Err(io::Error::new(
649 io::ErrorKind::InvalidInput,
650 "Q42 block index out of range",
651 ));
652 }
653 let offset = self
654 .header
655 .block_dir_offset
656 .checked_add((index * BlockDirectoryEntry::SIZE) as u64)
657 .ok_or_else(|| invalid("Q42 directory offset overflow"))?;
658 let mut bytes = [0u8; BlockDirectoryEntry::SIZE];
659 self.source.read_range_into(
660 Q42ByteRange {
661 offset,
662 length: BlockDirectoryEntry::SIZE,
663 },
664 &mut bytes,
665 )?;
666 Ok(BlockDirectoryEntry::from_bytes(&bytes))
667 }
668
669 pub fn object_hash_bounds(&self) -> io::Result<Option<(u64, u64)>> {
672 let count = self.bidx_block_count()?;
673 if count == 0 {
674 return Ok(None);
675 }
676 let first = self.bidx_entry(0)?;
677 let last = self.bidx_entry(count - 1)?;
678 if first.0 > first.1 || last.0 > last.1 || first.0 > last.1 {
679 return Err(invalid("Q42 BIDX object bounds are invalid"));
680 }
681 Ok(Some((first.0, last.1)))
682 }
683
684 pub fn bidx_block_range_for_hash(
688 &self,
689 object_hash: u64,
690 ) -> io::Result<Option<BidxBlockRange>> {
691 let block_count = self.bidx_block_count()?;
692 if block_count == 0 {
693 return Ok(None);
694 }
695 let mut lo = 0usize;
696 let mut hi = block_count;
697 while lo < hi {
698 let mid = lo + (hi - lo) / 2;
699 if self.bidx_entry(mid)?.1 < object_hash {
700 lo = mid + 1;
701 } else {
702 hi = mid;
703 }
704 }
705 let start = lo;
706 if start == block_count || self.bidx_entry(start)?.0 > object_hash {
707 return Ok(None);
708 }
709 lo = start;
710 hi = block_count;
711 while lo < hi {
712 let mid = lo + (hi - lo) / 2;
713 if self.bidx_entry(mid)?.0 <= object_hash {
714 lo = mid + 1;
715 } else {
716 hi = mid;
717 }
718 }
719 Ok(Some(BidxBlockRange { start, end: lo }))
720 }
721
722 pub fn bidx_blocks_for_hash_into(
725 &self,
726 object_hash: u64,
727 cursor: usize,
728 out: &mut [usize],
729 ) -> io::Result<Option<BidxMatchPage>> {
730 let Some(range) = self.bidx_block_range_for_hash(object_hash)? else {
731 return Ok(None);
732 };
733 if cursor > range.len() {
734 return Err(io::Error::new(
735 io::ErrorKind::InvalidInput,
736 "Q42 BIDX cursor is beyond the matching interval",
737 ));
738 }
739 if out.is_empty() && cursor < range.len() {
740 return Err(io::Error::new(
741 io::ErrorKind::InvalidInput,
742 "Q42 BIDX page buffer must contain at least one block index",
743 ));
744 }
745 let returned = (range.len() - cursor).min(out.len());
746 for (offset, slot) in out.iter_mut().take(returned).enumerate() {
747 *slot = range.start + cursor + offset;
748 }
749 let next = cursor + returned;
750 Ok(Some(BidxMatchPage {
751 range,
752 returned,
753 next_cursor: (next < range.len()).then_some(next),
754 }))
755 }
756
757 pub fn find_object_into(
761 &self,
762 object_hash: u64,
763 cursor: Q42ObjectSearchCursor,
764 compressed: &mut [u8],
765 decoded: &mut [u8],
766 out: &mut [NQuin],
767 ) -> io::Result<Option<Q42ObjectMatchPage>> {
768 let Some(block_range) = self.bidx_block_range_for_hash(object_hash)? else {
769 return Ok(None);
770 };
771 if cursor.block_offset > block_range.len() {
772 return Err(io::Error::new(
773 io::ErrorKind::InvalidInput,
774 "Q42 object search cursor is beyond the matching block interval",
775 ));
776 }
777 if out.is_empty() && cursor.block_offset < block_range.len() {
778 return Err(io::Error::new(
779 io::ErrorKind::InvalidInput,
780 "Q42 object search output buffer must contain at least one Quin",
781 ));
782 }
783
784 let mut written = 0usize;
785 let mut block_offset = cursor.block_offset;
786 let mut quin_offset = cursor.quin_offset;
787 while block_offset < block_range.len() && written < out.len() {
788 self.read_superblock_into(block_range.start + block_offset, compressed, decoded)?;
789 let live = u64::from_le_bytes(decoded[16..24].try_into().unwrap()) as usize;
790 if live > QUINS_PER_BLOCK || quin_offset > live {
791 return Err(invalid(
792 "Q42 object search encountered an invalid SuperBlock",
793 ));
794 }
795 while quin_offset < live && written < out.len() {
796 let offset = SUPERBLOCK_HEADER + quin_offset * QUIN_SIZE;
797 let quin =
798 bytemuck::pod_read_unaligned::<NQuin>(&decoded[offset..offset + QUIN_SIZE]);
799 if quin.object < object_hash {
800 quin_offset += 1;
801 continue;
802 }
803 if quin.object > object_hash {
804 quin_offset = live;
805 break;
806 }
807 out[written] = quin;
808 written += 1;
809 quin_offset += 1;
810 }
811 if quin_offset == live {
812 block_offset += 1;
813 quin_offset = 0;
814 }
815 }
816 let next_cursor = (block_offset < block_range.len()).then_some(Q42ObjectSearchCursor {
817 block_offset,
818 quin_offset,
819 });
820 Ok(Some(Q42ObjectMatchPage {
821 block_range,
822 returned: written,
823 next_cursor,
824 }))
825 }
826
827 pub fn read_superblock_into(
830 &self,
831 index: usize,
832 compressed: &mut [u8],
833 out: &mut [u8],
834 ) -> io::Result<usize> {
835 if out.len() < SUPERBLOCK_SIZE {
836 return Err(io::Error::new(
837 io::ErrorKind::InvalidInput,
838 "Q42 decoded output buffer is too small",
839 ));
840 }
841 let entry = self.block_directory_entry(index)?;
842 let compressed_len = entry.comp_len as usize;
843 if compressed_len < 4
844 || compressed_len > MAX_COMPRESSED_SUPERBLOCK_SIZE
845 || compressed.len() < compressed_len
846 || entry.uncomp_len != SUPERBLOCK_SIZE as u32
847 {
848 return Err(invalid("invalid Q42 compressed block directory entry"));
849 }
850 let offset = self
851 .header
852 .data_offset
853 .checked_add(entry.rel_offset)
854 .ok_or_else(|| invalid("Q42 compressed block offset overflow"))?;
855 self.source.read_range_into(
856 Q42ByteRange {
857 offset,
858 length: compressed_len,
859 },
860 &mut compressed[..compressed_len],
861 )?;
862 let declared = u32::from_le_bytes(compressed[0..4].try_into().unwrap()) as usize;
863 if declared != SUPERBLOCK_SIZE {
864 return Err(invalid("Q42 LZ4 prefix does not declare one SuperBlock"));
865 }
866 let decoded =
867 lz4_flex::decompress_into(&compressed[4..compressed_len], &mut out[..declared])
868 .map_err(|error| invalid(format!("decode Q42 range block: {error}")))?;
869 if decoded != declared {
870 return Err(invalid("Q42 range block decoded to an unexpected length"));
871 }
872 verify_decoded_superblock(&out[..decoded])?;
873 Ok(decoded)
874 }
875
876 pub fn into_source(self) -> S {
878 self.source
879 }
880
881 fn bidx_block_count(&self) -> io::Result<usize> {
884 let bidx_length = self.header.bidx_length;
885 if bidx_length < BIDX_HEADER_BYTES as u64 {
886 return Err(invalid("Q42 BIDX is shorter than its header"));
887 }
888 let mut bytes = [0u8; BIDX_HEADER_BYTES];
889 let offset = self.header.bidx_offset;
890 self.source.read_range_into(
891 Q42ByteRange {
892 offset,
893 length: BIDX_HEADER_BYTES,
894 },
895 &mut bytes,
896 )?;
897 if bytes[0..4] != BIDX_MAGIC || u32::from_le_bytes(bytes[4..8].try_into().unwrap()) != 1 {
898 return Err(invalid("unsupported Q42 BIDX header"));
899 }
900 let count = u32::from_le_bytes(bytes[8..12].try_into().unwrap()) as usize;
901 if count != self.header.block_count as usize {
902 return Err(invalid("Q42 BIDX count does not match the block directory"));
903 }
904 let expected = BIDX_HEADER_BYTES
905 .checked_add(
906 count
907 .checked_mul(BIDX_ENTRY_BYTES)
908 .ok_or_else(|| invalid("Q42 BIDX entry count overflow"))?,
909 )
910 .ok_or_else(|| invalid("Q42 BIDX length overflow"))?;
911 if bidx_length != expected as u64 {
912 return Err(invalid("Q42 BIDX length does not match its entry count"));
913 }
914 Ok(count)
915 }
916
917 fn bidx_entry(&self, index: usize) -> io::Result<(u64, u64)> {
920 let block_count = usize::try_from(self.header.block_count)
921 .map_err(|_| invalid("Q42 block count exceeds platform"))?;
922 if index >= block_count {
923 return Err(io::Error::new(
924 io::ErrorKind::InvalidInput,
925 "Q42 BIDX entry index out of range",
926 ));
927 }
928 let offset = self
929 .header
930 .bidx_offset
931 .checked_add(BIDX_HEADER_BYTES as u64)
932 .and_then(|value| value.checked_add((index * BIDX_ENTRY_BYTES) as u64))
933 .ok_or_else(|| invalid("Q42 BIDX entry offset overflow"))?;
934 let mut bytes = [0u8; BIDX_ENTRY_BYTES];
935 self.source.read_range_into(
936 Q42ByteRange {
937 offset,
938 length: BIDX_ENTRY_BYTES,
939 },
940 &mut bytes,
941 )?;
942 let min = u64::from_le_bytes(bytes[0..8].try_into().unwrap());
943 let max = u64::from_le_bytes(bytes[8..16].try_into().unwrap());
944 if min > max {
945 return Err(invalid("Q42 BIDX entry has min > max"));
946 }
947 Ok((min, max))
948 }
949
950 fn validate_field_range_index(&self) -> io::Result<()> {
953 let Some((offset, length)) = self.header.field_range_index_range() else {
954 return Ok(());
955 };
956 let expected = FIELD_RANGE_INDEX_HEADER_BYTES
957 .checked_add(
958 (self.header.block_count as usize)
959 .checked_mul(FIELD_RANGE_INDEX_ENTRY_BYTES)
960 .ok_or_else(|| invalid("Q42 field-range index length overflows"))?,
961 )
962 .ok_or_else(|| invalid("Q42 field-range index length overflows"))?;
963 if length != expected as u64 {
964 return Err(invalid(
965 "Q42 field-range index length does not match block count",
966 ));
967 }
968 let mut header = [0u8; FIELD_RANGE_INDEX_HEADER_BYTES];
969 self.read_section(offset, FIELD_RANGE_INDEX_HEADER_BYTES as u64, &mut header)?;
970 if header[0..4] != FIELD_RANGE_INDEX_MAGIC
971 || u32::from_le_bytes(header[4..8].try_into().unwrap()) != 1
972 || u32::from_le_bytes(header[8..12].try_into().unwrap()) as u64
973 != self.header.block_count
974 {
975 return Err(invalid("Q42 field-range index header is invalid"));
976 }
977 Ok(())
978 }
979
980 fn validate_field_postings(&self) -> io::Result<()> {
983 let Some((offset, length)) = self.header.field_postings_range() else {
984 return Ok(());
985 };
986 if length < super::postings::FIELD_POSTINGS_HEADER_BYTES as u64 {
987 return Err(invalid("Q42 field postings shorter than header"));
988 }
989 let mut header = [0u8; super::postings::FIELD_POSTINGS_HEADER_BYTES];
990 self.read_section(
991 offset,
992 super::postings::FIELD_POSTINGS_HEADER_BYTES as u64,
993 &mut header,
994 )?;
995 if header[0..4] != super::postings::FIELD_POSTINGS_MAGIC
996 || u32::from_le_bytes(header[4..8].try_into().unwrap()) != 1
997 || u32::from_le_bytes(header[8..12].try_into().unwrap()) as u64
998 != self.header.block_count
999 {
1000 return Err(invalid("Q42 field postings header is invalid"));
1001 }
1002 Ok(())
1003 }
1004
1005 fn field_membership_may_match(
1008 &self,
1009 block_index: usize,
1010 pattern: Q42RangeQueryPattern,
1011 ) -> io::Result<bool> {
1012 if let Some(matches) = self.field_postings_may_match(block_index, pattern)? {
1013 return Ok(matches);
1014 }
1015 self.field_range_may_match(block_index, pattern)
1016 }
1017
1018 fn field_postings_may_match(
1023 &self,
1024 block_index: usize,
1025 pattern: Q42RangeQueryPattern,
1026 ) -> io::Result<Option<bool>> {
1027 let Some((offset, length)) = self.header.field_postings_range() else {
1028 return Ok(None);
1029 };
1030 if block_index >= self.header.block_count as usize {
1031 return Err(invalid("Q42 field postings block index is out of bounds"));
1032 }
1033 let table =
1034 offset + super::postings::FIELD_POSTINGS_HEADER_BYTES as u64 + (block_index as u64) * 4;
1035 let mut ends = [0u8; 8];
1036 self.read_section(table, 8, &mut ends)?;
1037 let start = u32::from_le_bytes(ends[0..4].try_into().unwrap());
1038 let end = u32::from_le_bytes(ends[4..8].try_into().unwrap());
1039 let (rel_from, rel_to) = super::postings::block_payload_interval(
1040 self.header.block_count as usize,
1041 block_index,
1042 start,
1043 end,
1044 )?;
1045 let payload_offset = offset + rel_from as u64;
1046 let payload_len = rel_to - rel_from;
1047 if payload_offset + payload_len as u64 > offset + length {
1048 return Err(invalid("Q42 field postings payload leaves its section"));
1049 }
1050 let mut payload = vec![0u8; payload_len];
1051 self.read_section(payload_offset, payload_len as u64, &mut payload)?;
1052 let check = |field: usize, value: Option<u64>| -> io::Result<bool> {
1053 match value {
1054 None => Ok(true),
1055 Some(hash) => super::postings::field_may_contain(&payload, field, hash),
1056 }
1057 };
1058 Ok(Some(
1059 check(0, pattern.subject)?
1060 && check(1, pattern.predicate)?
1061 && check(2, pattern.context)?,
1062 ))
1063 }
1064
1065 fn field_range_may_match(
1069 &self,
1070 block_index: usize,
1071 pattern: Q42RangeQueryPattern,
1072 ) -> io::Result<bool> {
1073 let Some((offset, _)) = self.header.field_range_index_range() else {
1074 return Ok(true);
1075 };
1076 if block_index >= self.header.block_count as usize {
1077 return Err(invalid("Q42 field-range block index is out of bounds"));
1078 }
1079 let entry_offset = offset
1080 .checked_add(FIELD_RANGE_INDEX_HEADER_BYTES as u64)
1081 .and_then(|value| {
1082 value.checked_add((block_index * FIELD_RANGE_INDEX_ENTRY_BYTES) as u64)
1083 })
1084 .ok_or_else(|| invalid("Q42 field-range entry offset overflows"))?;
1085 let mut entry = [0u8; FIELD_RANGE_INDEX_ENTRY_BYTES];
1086 self.read_section(
1087 entry_offset,
1088 FIELD_RANGE_INDEX_ENTRY_BYTES as u64,
1089 &mut entry,
1090 )?;
1091 let includes = |field: usize, value: Option<u64>| {
1092 let start = field * 16;
1093 let min = u64::from_le_bytes(entry[start..start + 8].try_into().unwrap());
1094 let max = u64::from_le_bytes(entry[start + 8..start + 16].try_into().unwrap());
1095 min <= max && value.is_none_or(|value| min <= value && value <= max)
1096 };
1097 Ok(includes(0, pattern.subject)
1098 && includes(1, pattern.predicate)
1099 && includes(2, pattern.context))
1100 }
1101}
1102
1103#[cfg(all(test, not(target_arch = "wasm32")))]
1104mod tests {
1105 use super::super::super::{
1106 write_unified_volume, write_volume_root, Q42RangeVolumeSet, Q42VolumeManifest,
1107 };
1108 use super::*;
1109 use crate::mini_parser::hash_token;
1110 use crate::specialized_libs::computational_geometry::allocation_counter::assert_zero_alloc;
1111 use crate::NQuin;
1112 use std::collections::HashMap;
1113 use tempfile::NamedTempFile;
1114
1115 fn sample_volume() -> (NamedTempFile, NQuin) {
1116 let subject = hash_token("urn:q42:range-subject");
1117 let predicate = hash_token("urn:q42:range-predicate");
1118 let object = hash_token("urn:q42:range-object");
1119 let quin = NQuin {
1120 subject,
1121 predicate,
1122 object,
1123 context: 0,
1124 metadata: 0,
1125 parity: 0,
1126 };
1127 let mut lex = HashMap::new();
1128 lex.insert(subject, "urn:q42:range-subject".to_string());
1129 lex.insert(predicate, "urn:q42:range-predicate".to_string());
1130 lex.insert(object, "urn:q42:range-object".to_string());
1131 let file = NamedTempFile::new().unwrap();
1132 write_unified_volume(file.path(), &lex, &[(object, object)], &[vec![quin]]).unwrap();
1133 (file, quin)
1134 }
1135
1136 #[test]
1137 fn range_volume_reads_only_the_directory_entry_and_block() {
1138 let (file, quin) = sample_volume();
1139 let source = super::super::range::LocalFileRangeSource::open(file.path()).unwrap();
1140 let volume = Q42RangeVolume::open(source).unwrap();
1141 assert_eq!(volume.block_count(), 1);
1142 let entry = volume.block_directory_entry(0).unwrap();
1143 assert!(entry.comp_len as usize <= MAX_COMPRESSED_SUPERBLOCK_SIZE);
1144
1145 let mut compressed = [0u8; MAX_COMPRESSED_SUPERBLOCK_SIZE];
1146 let mut decoded = [0u8; SUPERBLOCK_SIZE];
1147 assert_eq!(
1148 volume
1149 .read_superblock_into(0, &mut compressed, &mut decoded)
1150 .unwrap(),
1151 SUPERBLOCK_SIZE
1152 );
1153 assert_eq!(u64::from_le_bytes(decoded[16..24].try_into().unwrap()), 1);
1154 assert_eq!(
1155 u64::from_le_bytes(decoded[160..168].try_into().unwrap()),
1156 quin.subject
1157 );
1158 }
1159
1160 #[test]
1161 fn range_volume_block_read_is_zero_heap() {
1162 let (file, _) = sample_volume();
1163 let source = super::super::range::LocalFileRangeSource::open(file.path()).unwrap();
1164 let volume = Q42RangeVolume::open(source).unwrap();
1165 let mut compressed = [0u8; MAX_COMPRESSED_SUPERBLOCK_SIZE];
1166 let mut decoded = [0u8; SUPERBLOCK_SIZE];
1167 assert_zero_alloc("q42_range_volume_block_read", || {
1168 volume
1169 .read_superblock_into(0, &mut compressed, &mut decoded)
1170 .unwrap();
1171 });
1172 }
1173
1174 #[test]
1175 fn range_volume_resolves_one_paged_lexicon_page_without_heap() {
1176 let (file, quin) = sample_volume();
1177 let source = super::super::range::LocalFileRangeSource::open(file.path()).unwrap();
1178 let volume = Q42RangeVolume::open(source).unwrap();
1179 let mut page = [0u8; 4_096];
1180 let mut text = [0u8; 128];
1181 let length = volume
1182 .lookup_lexicon_hash_into(quin.object, &mut page, &mut text)
1183 .unwrap()
1184 .unwrap();
1185 assert_eq!(&text[..length], b"urn:q42:range-object");
1186 assert_eq!(
1187 volume
1188 .lookup_lexicon_hash_into(7, &mut page, &mut text)
1189 .unwrap(),
1190 None
1191 );
1192 assert_zero_alloc("q42_range_volume_paged_lex_lookup", || {
1193 volume
1194 .lookup_lexicon_hash_into(quin.object, &mut page, &mut text)
1195 .unwrap();
1196 });
1197 }
1198
1199 #[test]
1200 fn range_volume_bidx_pages_complete_heavy_hitters() {
1201 let (file, quin) = sample_volume();
1202 let mut lex = HashMap::new();
1203 lex.insert(quin.subject, "urn:q42:range-subject".to_string());
1204 lex.insert(quin.predicate, "urn:q42:range-predicate".to_string());
1205 lex.insert(quin.object, "urn:q42:range-object".to_string());
1206 write_unified_volume(
1207 file.path(),
1208 &lex,
1209 &[(quin.object, quin.object); 5],
1210 &[vec![quin], vec![quin], vec![quin], vec![quin], vec![quin]],
1211 )
1212 .unwrap();
1213 let source = super::super::range::LocalFileRangeSource::open(file.path()).unwrap();
1214 let volume = Q42RangeVolume::open(source).unwrap();
1215 let mut page = [usize::MAX; 2];
1216 let first = volume
1217 .bidx_blocks_for_hash_into(quin.object, 0, &mut page)
1218 .unwrap()
1219 .unwrap();
1220 assert_eq!(first.range, BidxBlockRange { start: 0, end: 5 });
1221 assert_eq!(&page, &[0, 1]);
1222 let last = volume
1223 .bidx_blocks_for_hash_into(quin.object, first.next_cursor.unwrap(), &mut page)
1224 .unwrap()
1225 .unwrap();
1226 assert_eq!(&page, &[2, 3]);
1227 assert_eq!(last.next_cursor, Some(4));
1228 }
1229
1230 #[test]
1231 fn range_volume_object_search_is_paged_and_zero_heap() {
1232 let (file, quin) = sample_volume();
1233 let mut lex = HashMap::new();
1234 lex.insert(quin.subject, "urn:q42:range-subject".to_string());
1235 lex.insert(quin.predicate, "urn:q42:range-predicate".to_string());
1236 lex.insert(quin.object, "urn:q42:range-object".to_string());
1237 write_unified_volume(
1238 file.path(),
1239 &lex,
1240 &[(quin.object, quin.object); 3],
1241 &[vec![quin], vec![quin], vec![quin]],
1242 )
1243 .unwrap();
1244 let source = super::super::range::LocalFileRangeSource::open(file.path()).unwrap();
1245 let volume = Q42RangeVolume::open(source).unwrap();
1246 let mut compressed = [0u8; MAX_COMPRESSED_SUPERBLOCK_SIZE];
1247 let mut decoded = [0u8; SUPERBLOCK_SIZE];
1248 let mut out = [NQuin::default(); 2];
1249 let first = volume
1250 .find_object_into(
1251 quin.object,
1252 Q42ObjectSearchCursor::default(),
1253 &mut compressed,
1254 &mut decoded,
1255 &mut out,
1256 )
1257 .unwrap()
1258 .unwrap();
1259 assert_eq!(first.returned, 2);
1260 assert_eq!(out, [quin, quin]);
1261 let second = volume
1262 .find_object_into(
1263 quin.object,
1264 first.next_cursor.unwrap(),
1265 &mut compressed,
1266 &mut decoded,
1267 &mut out,
1268 )
1269 .unwrap()
1270 .unwrap();
1271 assert_eq!(second.returned, 1);
1272 assert_eq!(out[0], quin);
1273 assert_eq!(second.next_cursor, None);
1274
1275 assert_zero_alloc("q42_range_volume_object_search", || {
1276 volume
1277 .find_object_into(
1278 quin.object,
1279 Q42ObjectSearchCursor::default(),
1280 &mut compressed,
1281 &mut decoded,
1282 &mut out,
1283 )
1284 .unwrap();
1285 });
1286 }
1287
1288 #[test]
1289 fn range_query_planner_uses_bidx_and_pages_matching_quins() {
1290 let (file, quin) = sample_volume();
1291 let mut lex = HashMap::new();
1292 lex.insert(quin.subject, "urn:q42:range-subject".to_string());
1293 lex.insert(quin.predicate, "urn:q42:range-predicate".to_string());
1294 lex.insert(quin.object, "urn:q42:range-object".to_string());
1295 write_unified_volume(
1296 file.path(),
1297 &lex,
1298 &[(quin.object, quin.object); 3],
1299 &[vec![quin], vec![quin], vec![quin]],
1300 )
1301 .unwrap();
1302 let source = super::super::range::LocalFileRangeSource::open(file.path()).unwrap();
1303 let volume = Q42RangeVolume::open(source).unwrap();
1304 let plan = Q42RangeQueryPlan::for_pattern(Q42RangeQueryPattern {
1305 object: Some(quin.object),
1306 predicate: Some(quin.predicate),
1307 ..Default::default()
1308 });
1309 assert_eq!(plan.strategy, Q42RangeQueryStrategy::ObjectBidx);
1310 let mut compressed = [0u8; MAX_COMPRESSED_SUPERBLOCK_SIZE];
1311 let mut decoded = [0u8; SUPERBLOCK_SIZE];
1312 let mut out = [NQuin::default(); 2];
1313 let first = volume
1314 .execute_query_page_into(
1315 plan,
1316 Q42RangeQueryCursor::default(),
1317 &mut compressed,
1318 &mut decoded,
1319 &mut out,
1320 )
1321 .unwrap();
1322 assert_eq!(first.returned, 2);
1323 assert_eq!(out, [quin, quin]);
1324 let second = volume
1325 .execute_query_page_into(
1326 plan,
1327 first.next_cursor.unwrap(),
1328 &mut compressed,
1329 &mut decoded,
1330 &mut out,
1331 )
1332 .unwrap();
1333 assert_eq!(second.returned, 1);
1334 assert_eq!(second.next_cursor, None);
1335 assert_zero_alloc("q42_range_query_bidx_page", || {
1336 volume
1337 .execute_query_page_into(
1338 plan,
1339 Q42RangeQueryCursor::default(),
1340 &mut compressed,
1341 &mut decoded,
1342 &mut out,
1343 )
1344 .unwrap();
1345 });
1346 }
1347
1348 #[test]
1349 fn range_volume_set_opens_front_embedded_root_and_verifies_segments() {
1350 let dir = tempfile::TempDir::new().unwrap();
1351 let root_path = dir.path().join("root.q42");
1352 let first_path = dir.path().join("segment-000.q42");
1353 let second_path = dir.path().join("segment-001.q42");
1354 let lex_path = dir.path().join("lex-000.q42");
1355 let (first_quin, first_lex) = sample_quin("urn:q42:one");
1356 let (second_quin, second_lex) = sample_quin("urn:q42:two");
1357 let mut entries = [(first_quin, first_lex), (second_quin, second_lex)];
1358 entries.sort_unstable_by_key(|(quin, _)| quin.object);
1359 write_unified_volume(
1360 &first_path,
1361 &entries[0].1,
1362 &[(entries[0].0.object, entries[0].0.object)],
1363 &[vec![entries[0].0]],
1364 )
1365 .unwrap();
1366 write_unified_volume(
1367 &second_path,
1368 &entries[1].1,
1369 &[(entries[1].0.object, entries[1].0.object)],
1370 &[vec![entries[1].0]],
1371 )
1372 .unwrap();
1373 write_unified_volume(&lex_path, &entries[0].1, &[], &[]).unwrap();
1374 let manifest = Q42VolumeManifest {
1375 generation: 1,
1376 segments: vec![
1377 Q42VolumeManifest::segment_from_file(&first_path, "segment-000.q42".into())
1378 .unwrap(),
1379 Q42VolumeManifest::segment_from_file(&second_path, "segment-001.q42".into())
1380 .unwrap(),
1381 ],
1382 lexicon_segments: vec![Q42VolumeManifest::lexicon_segment_from_file(
1383 &lex_path,
1384 "lex-000.q42".into(),
1385 )
1386 .unwrap()],
1387 };
1388 write_volume_root(&root_path, &manifest).unwrap();
1389
1390 let root_source = super::super::range::LocalFileRangeSource::open(&root_path).unwrap();
1391 let root = Q42RangeVolume::open(root_source).unwrap();
1392 let factory = |entry: &super::super::manifest::Q42VolumeSegment| {
1393 super::super::range::LocalFileRangeSource::open(&dir.path().join(&entry.locator))
1394 };
1395 let mut set = Q42RangeVolumeSet::open_root(&root, &factory).unwrap();
1396 set.attach_lexicon_segments(&|entry: &super::super::manifest::Q42LexiconSegment| {
1397 super::super::range::LocalFileRangeSource::open(&dir.path().join(&entry.locator))
1398 })
1399 .unwrap();
1400 let mut lex_page = [0u8; 4096];
1401 let mut lex_text = [0u8; 128];
1402 let lex_len = set
1403 .lookup_lexicon_hash_into(entries[0].0.object, &mut lex_page, &mut lex_text)
1404 .unwrap()
1405 .unwrap();
1406 assert_eq!(
1407 &lex_text[..lex_len],
1408 entries[0].1[&entries[0].0.object].as_bytes()
1409 );
1410 assert_eq!(set.segment_index_for_object(entries[0].0.object), Some(0));
1411 assert_eq!(set.segment_index_for_object(entries[1].0.object), Some(1));
1412 let mut digest_scratch = [0u8; 1024];
1413 set.verify_segment_hashes(&mut digest_scratch).unwrap();
1414 let mut compressed = [0u8; MAX_COMPRESSED_SUPERBLOCK_SIZE];
1415 let mut decoded = [0u8; SUPERBLOCK_SIZE];
1416 set.verify_segment_quin_counts(&mut compressed, &mut decoded)
1417 .unwrap();
1418 let plan = Q42RangeQueryPlan::for_pattern(Q42RangeQueryPattern {
1419 predicate: Some(entries[0].0.predicate),
1420 ..Default::default()
1421 });
1422 let mut out = [NQuin::default(); 2];
1423 let page = set
1424 .execute_query_page_into(
1425 plan,
1426 super::super::manifest::Q42VolumeSetQueryCursor::default(),
1427 &mut compressed,
1428 &mut decoded,
1429 &mut out,
1430 )
1431 .unwrap();
1432 assert_eq!(page.returned, 2);
1433 assert_eq!(page.next_cursor, None);
1434 }
1435
1436 fn sample_quin(object_text: &str) -> (NQuin, HashMap<u64, String>) {
1437 let subject = hash_token("urn:q42:range-subject");
1438 let predicate = hash_token("urn:q42:range-predicate");
1439 let object = hash_token(object_text);
1440 let quin = NQuin {
1441 subject,
1442 predicate,
1443 object,
1444 context: 0,
1445 metadata: 0,
1446 parity: 0,
1447 };
1448 let mut lex = HashMap::new();
1449 lex.insert(subject, "urn:q42:range-subject".to_string());
1450 lex.insert(predicate, "urn:q42:range-predicate".to_string());
1451 lex.insert(object, object_text.to_string());
1452 (quin, lex)
1453 }
1454}
1455#[test]
1456fn field_ranges_prune_non_object_constant_scans() {
1457 let file = tempfile::NamedTempFile::new().unwrap();
1458 let first = NQuin {
1459 subject: 10,
1460 predicate: 20,
1461 object: 1,
1462 context: 30,
1463 metadata: 0,
1464 parity: 0,
1465 };
1466 let second = NQuin {
1467 subject: 40,
1468 predicate: 50,
1469 object: 2,
1470 context: 60,
1471 metadata: 0,
1472 parity: 0,
1473 };
1474 crate::q42_volume::write_unified_volume(
1475 file.path(),
1476 &std::collections::HashMap::new(),
1477 &[(1, 1), (2, 2)],
1478 &[vec![first], vec![second]],
1479 )
1480 .unwrap();
1481 let source = crate::q42_volume::LocalFileRangeSource::open(file.path()).unwrap();
1482 let volume = Q42RangeVolume::open(source).unwrap();
1483 let pattern = Q42RangeQueryPattern {
1484 predicate: Some(second.predicate),
1485 ..Q42RangeQueryPattern::default()
1486 };
1487 assert_eq!(
1488 Q42RangeQueryPlan::for_pattern(pattern).strategy,
1489 Q42RangeQueryStrategy::FieldRanges
1490 );
1491 let mut compressed = [0u8; MAX_COMPRESSED_SUPERBLOCK_SIZE];
1492 let mut decoded = [0u8; SUPERBLOCK_SIZE];
1493 let mut out = [NQuin::default(); 1];
1494 let page = volume
1495 .execute_query_page_into(
1496 Q42RangeQueryPlan::for_pattern(pattern),
1497 Q42RangeQueryCursor::default(),
1498 &mut compressed,
1499 &mut decoded,
1500 &mut out,
1501 )
1502 .unwrap();
1503 assert_eq!(page.returned, 1);
1504 assert_eq!(out[0], second);
1505 assert!(page.next_cursor.is_none());
1506}