Skip to main content

qualia_core_db/q42/volume/
range_volume.rs

1//! Range-backed Q42 segment reader for local, HTTP, and IPFS sources.
2
3use 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
19/// Build an `InvalidData` io::Error for malformed volume content.
20fn invalid(message: impl Into<String>) -> io::Error {
21    io::Error::new(io::ErrorKind::InvalidData, message.into())
22}
23
24/// Fail closed on a decoded SuperBlock before any Quin is copied out.
25fn 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
44/// A Q42 reader that fetches exactly the bytes needed from a random-access
45/// source. All variable-size buffers remain caller-owned.
46pub struct Q42RangeVolume<S: Q42RangeSource> {
47    source: S,
48    header: Q42VolumeHeader,
49    source_length: u64,
50}
51
52/// Resume state for a caller-buffered object search. It is tied to the object
53/// hash passed to [`Q42RangeVolume::find_object_into`].
54#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
55pub struct Q42ObjectSearchCursor {
56    /// Offset into the matching BIDX block interval.
57    pub block_offset: usize,
58    /// Quin offset in the current decoded block.
59    pub quin_offset: usize,
60}
61
62/// One page of exact object matches written by [`Q42RangeVolume::find_object_into`].
63#[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/// A simple physical pattern for range-backed Q42 scans. `None` is an
71/// unbound SPARQL position.  The planner selects the BIDX object index when
72/// `object` is bound and otherwise performs a bounded sequential block scan.
73#[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    /// Pick the scan strategy for `pattern`: object BIDX when an object
96    /// constraint is present, field-range index for s/p/c constraints,
97    /// sequential scan otherwise.
98    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/// Resume state for a bounded range-query page.
116#[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    /// Open and validate a range source: header version/flags, section
130    /// bounds, directory-vs-block-count consistency, and BIDX +
131    /// field-index headers all checked before first use.
132    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    /// The validated volume header.
201    pub fn header(&self) -> &Q42VolumeHeader {
202        &self.header
203    }
204    /// Byte length of the underlying range source.
205    pub fn source_length(&self) -> u64 {
206        self.source_length
207    }
208    /// Number of superblocks declared in the header.
209    pub fn block_count(&self) -> u64 {
210        self.header.block_count
211    }
212
213    /// Execute one caller-buffered page of a physical Q42 scan.  A bound
214    /// object uses BIDX to avoid unrelated SuperBlocks; all other patterns
215    /// stream one block at a time.  This is the reusable low-level path that
216    /// a SPARQL planner can drive without materialising a graph snapshot.
217    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    /// Borrow the underlying range source.
331    pub fn source(&self) -> &S {
332        &self.source
333    }
334
335    /// Read the lexicon section into `out` (must match its byte
336    /// length exactly).
337    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    /// Read the fixed Q42LEX header only.  This is used to validate a routed
342    /// lexicon shard without transferring its dictionary pages.
343    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    /// Resolve a string from a paged Q42LEX dictionary using exact range reads.
360    /// `page_scratch` and `out` are caller-owned; neither a full lexicon nor a
361    /// decoded page is retained by the reader.  Returns the UTF-8 byte length
362    /// written into `out`, or `None` when the hash is absent.
363    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                // Resolve the namespace from this page's local table. The
535                // walk is bounds-checked at every entry so a corrupt ns_id
536                // fails closed instead of slicing past the page.
537                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                // Namespace table entries are [u16 len][utf-8] — no tag byte.
542                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    /// Read the whole BIDX index section into `out` (must match its
585    /// byte length exactly).
586    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    /// Return the size of the front-embedded logical-volume manifest, if this
591    /// segment is a root. The caller can use [`Self::read_volume_manifest_into`]
592    /// to retrieve exactly those bytes.
593    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    /// Copy the front-embedded manifest into `out`; `false` when this
609    /// segment is not a root (no embedded manifest). Buffer length
610    /// must equal `volume_manifest_length()`.
611    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    /// Read exactly `length` bytes at `offset` — `out.len()` must
630    /// equal the section length (exact-fit contract).
631    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    /// Fetch directory entry `index` — a single bounded range read,
645    /// bounds-checked against `block_count`.
646    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    /// Object-hash bounds read from the first and last BIDX entry. This avoids
670    /// materialising the index merely to validate a manifest segment.
671    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    /// Return the complete BIDX interval which can contain an object hash.
685    /// Each comparison fetches one fixed 16-byte BIDX entry; there is no index
686    /// allocation or whole-index transfer.
687    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    /// Fill one bounded page of BIDX block indices. This retains complete
723    /// heavy-hitter semantics while forcing callers to provide the cap.
724    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    /// Find Quins whose object equals `object_hash`, using the BIDX to fetch
758    /// only candidate SuperBlocks. `compressed`, `decoded`, and `out` are all
759    /// caller-owned. Reuse `cursor` from the returned page until it is `None`.
760    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    /// Fetch and decode one block. `compressed` must fit the directory entry;
828    /// `out` must be at least one full decoded SuperBlock.
829    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    /// Consume the volume and return the underlying range source.
877    pub fn into_source(self) -> S {
878        self.source
879    }
880
881    /// Validate the BIDX header (magic, version, count vs directory,
882    /// section-length arithmetic) and return its entry count.
883    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    /// Read BIDX entry `index` — the (min, max) object-hash range of
918    /// one block; rejects min > max.
919    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    /// When present, check the field-range index header (magic,
951    /// version, count) and its section-length arithmetic.
952    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    /// When present, check the field-postings header (magic, version,
981    /// per-block count).
982    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    /// Combined prune test: postings first (definitive), then the
1006    /// coarser field-range index. `true` means "may match — must scan".
1007    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    /// Postings-table prune for `block_index`: reads the block's
1019    /// payload interval and tests s/p/c pattern values against the
1020    /// per-field membership filter. `None` when the volume has no
1021    /// postings section.
1022    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    /// Min/max field-range prune for `block_index`: each present
1066    /// pattern value must fall inside the block's recorded hash range.
1067    /// `true` when the index section is absent (cannot prune).
1068    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}