Skip to main content

qualia_core_db/query/
graph_proof.rs

1//! Bounded-memory proof of the encoded graph represented by an N-Triples source
2//! and a Q42 volume.
3//!
4//! The `qualia-cli ingest semantic` pipeline stores the default graph as hashed
5//! `(subject, predicate, object, context)` records.  This module compares those
6//! records exactly as a *set*, using sorted fixed-width disk runs rather than an
7//! in-memory graph or a lossy aggregate checksum.
8//! Blank-node graphs require lexical Q42 terms for canonical isomorphism.
9
10use std::cmp::Ordering;
11use std::fs::File;
12use std::io::{self, BufRead, BufReader, BufWriter, Read, Write};
13use std::path::{Path, PathBuf};
14
15use tempfile::TempDir;
16
17use crate::mini_parser::hash_token;
18use crate::q42_volume::{Q42Volume, QUIN_SIZE, SUPERBLOCK_HEADER, SUPERBLOCK_SIZE};
19use crate::q_hash;
20use crate::query::ingest_formats::{
21    format_from_path, object_iri_hash, parse_triples_format, RawTriple, OBJECT_IRI_MASK,
22};
23use crate::query::integrity_omit::MAX_LEX_TERM_BYTES;
24
25const RECORD_BYTES: u64 = 32;
26const READ_BUFFER_BYTES: usize = 32 * 1024;
27const MERGE_FAN_IN: usize = 16;
28
29/// Default RAM reserved for the sort buffer.  The verifier uses bounded I/O
30/// buffers in addition to this allocation.
31pub const DEFAULT_GRAPH_PROOF_MEMORY_BYTES: usize = 32 * 1024 * 1024;
32/// Default maximum temporary on-disk footprint.  The verifier fails closed
33/// rather than exhausting an arbitrary temp volume.
34pub const DEFAULT_GRAPH_PROOF_TEMP_BYTES: u64 = 24 * 1024 * 1024 * 1024;
35
36/// Which encoder the proof claims to mirror.
37#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, serde::Serialize)]
38#[serde(rename_all = "snake_case")]
39pub enum EncoderProfile {
40    /// Whitespace-split N-Triples + [`hash_token`] (legacy `ingest semantic`).
41    LegacySemantic,
42    /// Rio + [`q_hash`] / inline object tags — same as `qualia-cli import` Complete.
43    #[default]
44    ImportComplete,
45    /// Same hashed quads as Complete; documents that the twin volume used StripLiterals (empty lex).
46    ImportStripLiterals,
47}
48
49/// Resource limits for [`prove_cli_ntriples_q42_equivalence`].
50#[derive(Clone, Copy, Debug)]
51pub struct GraphProofOptions {
52    /// Upper bound for the in-memory record sort buffer, in bytes.
53    pub memory_limit_bytes: usize,
54    /// Upper bound for live temporary run files, in bytes.
55    pub temporary_byte_budget: u64,
56}
57
58impl Default for GraphProofOptions {
59    /// Sensible proof defaults (bounded temp budget, default limits).
60    fn default() -> Self {
61        Self {
62            memory_limit_bytes: DEFAULT_GRAPH_PROOF_MEMORY_BYTES,
63            temporary_byte_budget: DEFAULT_GRAPH_PROOF_TEMP_BYTES,
64        }
65    }
66}
67
68/// Options for [`prove_import_rdf_q42_equivalence`].
69#[derive(Clone, Debug)]
70pub struct ImportProofOptions {
71    pub memory_limit_bytes: usize,
72    pub temporary_byte_budget: u64,
73    /// Predicate FNV-1a hashes to drop (must match ingest omit list).
74    pub omit_predicate_hashes: Vec<u64>,
75    /// Label only — does not change hashing (StripLiterals still hashes all kept triples).
76    pub encoder_profile: EncoderProfile,
77}
78
79impl Default for ImportProofOptions {
80    /// Sensible import-proof defaults.
81    fn default() -> Self {
82        Self {
83            memory_limit_bytes: DEFAULT_GRAPH_PROOF_MEMORY_BYTES,
84            temporary_byte_budget: DEFAULT_GRAPH_PROOF_TEMP_BYTES,
85            omit_predicate_hashes: Vec::new(),
86            encoder_profile: EncoderProfile::ImportComplete,
87        }
88    }
89}
90
91impl ImportProofOptions {
92    /// Derive import-proof options from a graph-proof config.
93    pub fn from_graph_options(options: GraphProofOptions) -> Self {
94        Self {
95            memory_limit_bytes: options.memory_limit_bytes,
96            temporary_byte_budget: options.temporary_byte_budget,
97            omit_predicate_hashes: Vec::new(),
98            encoder_profile: EncoderProfile::ImportComplete,
99        }
100    }
101}
102
103/// The level of RDF claim that can be made from an encoded Q42 comparison.
104#[derive(Clone, Copy, Debug, Eq, PartialEq, serde::Serialize)]
105pub enum RdfIsomorphismStatus {
106    /// The source contains no blank-node labels, so exact encoded-set equality
107    /// is a ground-graph equivalence proof in the ingestion representation.
108    GroundGraphProven,
109    /// The sets match only when original blank-node labels are treated as
110    /// identities.  Canonical blank-node isomorphism needs lexical Q42 terms.
111    BlankNodeCanonicalizationRequired,
112    /// The encoded graph sets differ, so no isomorphism claim is possible.
113    Different,
114}
115
116/// Result of an exact, external-sort comparison.
117#[derive(Clone, Debug, serde::Serialize)]
118pub struct GraphProofReport {
119    /// Number of N-Triples accepted by the CLI-compatible normaliser.
120    pub source_records: u64,
121    /// Number of Q42 Quins examined.
122    pub q42_records: u64,
123    /// Number of unique encoded quads in the source.
124    pub source_unique_records: u64,
125    /// Number of unique encoded quads in the Q42 volume.
126    pub q42_unique_records: u64,
127    /// Source records that do not occur in the Q42 set.
128    pub missing_from_q42: u64,
129    /// Q42 records that do not occur in the source set.
130    pub unexpected_in_q42: u64,
131    /// A representative missing encoded quad, if any.
132    pub first_missing: Option<[u64; 4]>,
133    /// A representative unexpected encoded quad, if any.
134    pub first_unexpected: Option<[u64; 4]>,
135    /// Lines skipped because they are blank, comments, or not accepted by the
136    /// same three-token N-Triples compatibility parser used by CLI ingest.
137    pub source_skipped_lines: u64,
138    pub source_contains_blank_nodes: bool,
139    pub rdf_isomorphism: RdfIsomorphismStatus,
140    /// Which encoder this report claims to have mirrored.
141    pub encoder_profile: EncoderProfile,
142    /// Triples seen in the source before omit filtering (import path).
143    pub source_triple_count: u64,
144    /// Triples dropped by omit-predicate (or legacy skipped lines mirrored here).
145    pub skipped_or_filtered: u64,
146    /// Terms that would hit [`crate::q42_lex::LexError::TermTooLong`].
147    pub oversize_literal_count: u64,
148    pub first_oversize_preview: Option<String>,
149    /// Lexicon byte length from the Q42 header (0 / 32 often means empty lex).
150    pub lexicon_length_bytes: u64,
151    pub lexicon_entry_count: Option<u64>,
152    pub lexicon_has_no_terms: bool,
153}
154
155impl GraphProofReport {
156    /// Exact equality of the two encoded RDF default-graph sets.
157    pub fn encoded_sets_match(&self) -> bool {
158        self.missing_from_q42 == 0 && self.unexpected_in_q42 == 0
159    }
160}
161
162/// Compare an N-Triples input to a Q42 volume without retaining either graph
163/// in memory.
164///
165/// Source normalisation intentionally mirrors `qualia-cli ingest semantic`:
166/// it takes the first three ASCII-whitespace-delimited tokens and applies
167/// [`hash_token`] to each.  This proves the bytes that that ingest mode can
168/// encode, rather than pretending the current hash-only volume can recover
169/// lexical RDF values that it never stored.
170///
171/// Prefer [`prove_import_rdf_q42_equivalence`] for volumes built with `import`.
172pub fn prove_cli_ntriples_q42_equivalence(
173    source_path: &Path,
174    q42_path: &Path,
175    options: GraphProofOptions,
176) -> io::Result<GraphProofReport> {
177    let records_per_chunk = records_per_chunk(options.memory_limit_bytes)?;
178    let workspace = TempDir::new()?;
179    let mut budget = TempBudget::new(options.temporary_byte_budget);
180
181    let mut source_spool = DiskSpool::new(workspace.path(), "source", records_per_chunk);
182    let (source_skipped_lines, source_contains_blank_nodes) =
183        stream_source_records(source_path, &mut source_spool, &mut budget)?;
184    let source_records = source_spool.record_count;
185    let source_runs = source_spool.finish(&mut budget)?;
186    let source_run = merge_to_one(source_runs, workspace.path(), "source", &mut budget)?;
187
188    let mut q42_spool = DiskSpool::new(workspace.path(), "q42", records_per_chunk);
189    stream_q42_records(q42_path, &mut q42_spool, &mut budget)?;
190    let q42_records = q42_spool.record_count;
191    let q42_runs = q42_spool.finish(&mut budget)?;
192    let q42_run = merge_to_one(q42_runs, workspace.path(), "q42", &mut budget)?;
193
194    let comparison = compare_unique_sets(&source_run.path, &q42_run.path)?;
195    let lex = read_lex_stats(q42_path)?;
196    Ok(finish_report(
197        source_records,
198        q42_records,
199        comparison,
200        source_skipped_lines,
201        source_contains_blank_nodes,
202        EncoderProfile::LegacySemantic,
203        source_records,
204        source_skipped_lines,
205        0,
206        None,
207        lex,
208    ))
209}
210
211/// Compare an RDF source to a Q42 volume using the same Rio + `q_hash` encoding
212/// as [`crate::query::ingest::streaming_import_rdf_with_report`].
213pub fn prove_import_rdf_q42_equivalence(
214    source_path: &Path,
215    q42_path: &Path,
216    options: ImportProofOptions,
217) -> io::Result<GraphProofReport> {
218    let memory = if options.memory_limit_bytes == 0 {
219        DEFAULT_GRAPH_PROOF_MEMORY_BYTES
220    } else {
221        options.memory_limit_bytes
222    };
223    let temp = if options.temporary_byte_budget == 0 {
224        DEFAULT_GRAPH_PROOF_TEMP_BYTES
225    } else {
226        options.temporary_byte_budget
227    };
228    let records_per_chunk = records_per_chunk(memory)?;
229    let workspace = TempDir::new()?;
230    let mut budget = TempBudget::new(temp);
231
232    let mut source_spool = DiskSpool::new(workspace.path(), "source", records_per_chunk);
233    let import_stats = stream_import_source_records(
234        source_path,
235        &options.omit_predicate_hashes,
236        &mut source_spool,
237        &mut budget,
238    )?;
239    let source_records = source_spool.record_count;
240    let source_runs = source_spool.finish(&mut budget)?;
241    let source_run = merge_to_one(source_runs, workspace.path(), "source", &mut budget)?;
242
243    let mut q42_spool = DiskSpool::new(workspace.path(), "q42", records_per_chunk);
244    stream_q42_records(q42_path, &mut q42_spool, &mut budget)?;
245    let q42_records = q42_spool.record_count;
246    let q42_runs = q42_spool.finish(&mut budget)?;
247    let q42_run = merge_to_one(q42_runs, workspace.path(), "q42", &mut budget)?;
248
249    let comparison = compare_unique_sets(&source_run.path, &q42_run.path)?;
250    let lex = read_lex_stats(q42_path)?;
251    Ok(finish_report(
252        source_records,
253        q42_records,
254        comparison,
255        import_stats.filtered,
256        import_stats.has_blank_nodes,
257        options.encoder_profile,
258        import_stats.seen,
259        import_stats.filtered,
260        import_stats.oversize,
261        import_stats.first_oversize_preview,
262        lex,
263    ))
264}
265
266struct LexStats {
267    length_bytes: u64,
268    entry_count: Option<u64>,
269    has_no_terms: bool,
270}
271
272/// Read the Q42 volume's lexicon statistics (term count, collision
273/// count) from its on-disk header.
274fn read_lex_stats(q42_path: &Path) -> io::Result<LexStats> {
275    let volume = Q42Volume::open(q42_path)?;
276    let length_bytes = volume.header().lex_length;
277    let entry_count = volume.lex_view().ok().map(|lex| lex.entry_count() as u64);
278    let has_no_terms = entry_count == Some(0) || length_bytes <= 32;
279    Ok(LexStats {
280        length_bytes,
281        entry_count,
282        has_no_terms,
283    })
284}
285
286/// Assemble the final `GraphProofReport` from the set comparison,
287/// import stats, and lexicon stats.
288fn finish_report(
289    source_records: u64,
290    q42_records: u64,
291    comparison: SetComparison,
292    source_skipped_lines: u64,
293    source_contains_blank_nodes: bool,
294    encoder_profile: EncoderProfile,
295    source_triple_count: u64,
296    skipped_or_filtered: u64,
297    oversize_literal_count: u64,
298    first_oversize_preview: Option<String>,
299    lex: LexStats,
300) -> GraphProofReport {
301    let encoded_sets_match = comparison.missing == 0 && comparison.unexpected == 0;
302    let rdf_isomorphism = if !encoded_sets_match {
303        RdfIsomorphismStatus::Different
304    } else if source_contains_blank_nodes {
305        RdfIsomorphismStatus::BlankNodeCanonicalizationRequired
306    } else {
307        RdfIsomorphismStatus::GroundGraphProven
308    };
309    GraphProofReport {
310        source_records,
311        q42_records,
312        source_unique_records: comparison.left_unique,
313        q42_unique_records: comparison.right_unique,
314        missing_from_q42: comparison.missing,
315        unexpected_in_q42: comparison.unexpected,
316        first_missing: comparison.first_missing.map(QuadRecord::as_array),
317        first_unexpected: comparison.first_unexpected.map(QuadRecord::as_array),
318        source_skipped_lines,
319        source_contains_blank_nodes,
320        rdf_isomorphism,
321        encoder_profile,
322        source_triple_count,
323        skipped_or_filtered,
324        oversize_literal_count,
325        first_oversize_preview,
326        lexicon_length_bytes: lex.length_bytes,
327        lexicon_entry_count: lex.entry_count,
328        lexicon_has_no_terms: lex.has_no_terms,
329    }
330}
331
332/// Encode a raw parsed triple into the canonical 4×u64
333/// `QuadRecord` used for byte-level set comparison.
334fn encode_import_raw(raw: &RawTriple) -> QuadRecord {
335    let subject = q_hash(&raw.subject);
336    let predicate = q_hash(&raw.predicate);
337    let object = raw
338        .packed_object
339        .unwrap_or_else(|| object_iri_hash(&raw.object));
340    debug_assert_eq!(OBJECT_IRI_MASK, 0x0FFF_FFFF_FFFF_FFFF);
341    QuadRecord {
342        subject,
343        predicate,
344        object,
345        context: raw.context,
346    }
347}
348
349struct ImportStreamStats {
350    seen: u64,
351    filtered: u64,
352    oversize: u64,
353    first_oversize_preview: Option<String>,
354    has_blank_nodes: bool,
355}
356
357/// Stream triples from the import source, encoding each into
358/// `QuadRecord`s and spooling sorted runs under the temp budget.
359fn stream_import_source_records(
360    source_path: &Path,
361    omit_predicate_hashes: &[u64],
362    spool: &mut DiskSpool,
363    budget: &mut TempBudget,
364) -> io::Result<ImportStreamStats> {
365    let lower = source_path.to_string_lossy().to_ascii_lowercase();
366    let fmt = format_from_path(&lower);
367    let omit: std::collections::HashSet<u64> = omit_predicate_hashes.iter().copied().collect();
368    let file = File::open(source_path)?;
369    let reader = BufReader::with_capacity(READ_BUFFER_BYTES, file);
370    let mut stats = ImportStreamStats {
371        seen: 0,
372        filtered: 0,
373        oversize: 0,
374        first_oversize_preview: None,
375        has_blank_nodes: false,
376    };
377    let mut push_err: Option<io::Error> = None;
378    let mut on_triple = |raw: RawTriple| {
379        if push_err.is_some() {
380            return;
381        }
382        stats.seen += 1;
383        if omit.contains(&q_hash(&raw.predicate)) {
384            stats.filtered += 1;
385            return;
386        }
387        if raw.subject.starts_with("_:") || raw.object.starts_with("_:") {
388            stats.has_blank_nodes = true;
389        }
390        for part in [&raw.subject, &raw.predicate, &raw.object] {
391            if part.len() > MAX_LEX_TERM_BYTES {
392                stats.oversize += 1;
393                if stats.first_oversize_preview.is_none() {
394                    let preview: String = part.chars().take(80).collect();
395                    stats.first_oversize_preview =
396                        Some(format!("{preview}… ({} bytes)", part.len()));
397                }
398            }
399        }
400        if let Err(e) = spool.push(encode_import_raw(&raw), budget) {
401            push_err = Some(e);
402        }
403    };
404    if let Err(e) = parse_triples_format(fmt, reader, None, &mut on_triple) {
405        return Err(io::Error::new(io::ErrorKind::InvalidData, e));
406    }
407    if let Some(e) = push_err {
408        return Err(e);
409    }
410    Ok(stats)
411}
412
413#[repr(C)]
414#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, bytemuck::Pod, bytemuck::Zeroable)]
415struct QuadRecord {
416    subject: u64,
417    predicate: u64,
418    object: u64,
419    context: u64,
420}
421
422impl QuadRecord {
423    /// Record as a `[u64; 4]` for lexicographic ordering.
424    fn as_array(self) -> [u64; 4] {
425        [self.subject, self.predicate, self.object, self.context]
426    }
427}
428
429impl Ord for QuadRecord {
430    /// Lexicographic order over the record's u64 fields.
431    fn cmp(&self, other: &Self) -> Ordering {
432        (self.object, self.subject, self.predicate, self.context).cmp(&(
433            other.object,
434            other.subject,
435            other.predicate,
436            other.context,
437        ))
438    }
439}
440
441impl PartialOrd for QuadRecord {
442    /// Delegates to `Ord::cmp` (total order).
443    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
444        Some(self.cmp(other))
445    }
446}
447
448struct DiskRun {
449    path: PathBuf,
450    bytes: u64,
451}
452
453struct TempBudget {
454    maximum: u64,
455    current: u64,
456}
457
458impl TempBudget {
459    /// Budget with `maximum` bytes available.
460    fn new(maximum: u64) -> Self {
461        Self {
462            maximum,
463            current: 0,
464        }
465    }
466
467    /// Reserve `bytes`; error (fail closed) when the budget would
468    /// be exceeded.
469    fn reserve(&mut self, bytes: u64) -> io::Result<()> {
470        let next = self.current.checked_add(bytes).ok_or_else(|| {
471            io::Error::new(
472                io::ErrorKind::Other,
473                "graph-proof temporary budget overflow",
474            )
475        })?;
476        if next > self.maximum {
477            return Err(io::Error::new(
478                io::ErrorKind::Other,
479                format!(
480                    "graph-proof temporary budget exceeded: need {next} bytes, limit is {} bytes",
481                    self.maximum
482                ),
483            ));
484        }
485        self.current = next;
486        Ok(())
487    }
488
489    /// Return `bytes` to the budget.
490    fn release(&mut self, bytes: u64) {
491        self.current = self.current.saturating_sub(bytes);
492    }
493}
494
495struct DiskSpool {
496    temp_dir: PathBuf,
497    prefix: &'static str,
498    records: Vec<QuadRecord>,
499    runs: Vec<DiskRun>,
500    run_index: usize,
501    record_count: u64,
502}
503
504impl DiskSpool {
505    /// Spool writing runs of `records_per_chunk` into `temp_dir`
506    /// files named with `prefix`.
507    fn new(temp_dir: &Path, prefix: &'static str, records_per_chunk: usize) -> Self {
508        Self {
509            temp_dir: temp_dir.to_path_buf(),
510            prefix,
511            records: Vec::with_capacity(records_per_chunk),
512            runs: Vec::new(),
513            run_index: 0,
514            record_count: 0,
515        }
516    }
517
518    /// Buffer a record; flush a sorted run to disk when the chunk
519    /// fills (budget-charged).
520    fn push(&mut self, record: QuadRecord, budget: &mut TempBudget) -> io::Result<()> {
521        self.records.push(record);
522        self.record_count += 1;
523        if self.records.len() == self.records.capacity() {
524            self.flush(budget)?;
525        }
526        Ok(())
527    }
528
529    /// Sort the buffered chunk and write it as a disk run.
530    fn flush(&mut self, budget: &mut TempBudget) -> io::Result<()> {
531        if self.records.is_empty() {
532            return Ok(());
533        }
534        self.records.sort_unstable();
535        let bytes = self.records.len() as u64 * RECORD_BYTES;
536        budget.reserve(bytes)?;
537        let path = self
538            .temp_dir
539            .join(format!("{}-run-{:08}.bin", self.prefix, self.run_index));
540        self.run_index += 1;
541        let write_result = write_records(&path, &self.records);
542        if let Err(error) = write_result {
543            budget.release(bytes);
544            return Err(error);
545        }
546        self.records.clear();
547        self.runs.push(DiskRun { path, bytes });
548        Ok(())
549    }
550
551    /// Flush any remainder and return the list of disk runs.
552    fn finish(&mut self, budget: &mut TempBudget) -> io::Result<Vec<DiskRun>> {
553        self.flush(budget)?;
554        Ok(std::mem::take(&mut self.runs))
555    }
556}
557
558/// Chunk size in records for the given memory limit; fails closed
559/// when the limit can't hold one record.
560fn records_per_chunk(memory_limit_bytes: usize) -> io::Result<usize> {
561    let records = memory_limit_bytes / RECORD_BYTES as usize;
562    if records == 0 {
563        return Err(io::Error::new(
564            io::ErrorKind::InvalidInput,
565            "graph-proof memory limit must hold at least one 32-byte record",
566        ));
567    }
568    Ok(records)
569}
570
571/// Stream `QuadRecord`s from an N-Triples source into sorted
572/// disk runs.
573fn stream_source_records(
574    source_path: &Path,
575    spool: &mut DiskSpool,
576    budget: &mut TempBudget,
577) -> io::Result<(u64, bool)> {
578    let source = File::open(source_path)?;
579    let mut reader = BufReader::with_capacity(READ_BUFFER_BYTES, source);
580    let mut buffer = Vec::with_capacity(READ_BUFFER_BYTES);
581    let mut skipped = 0u64;
582    let mut has_blank_nodes = false;
583
584    loop {
585        buffer.clear();
586        if reader.read_until(b'\n', &mut buffer)? == 0 {
587            break;
588        }
589        let line = std::str::from_utf8(&buffer).map_err(|_| {
590            io::Error::new(io::ErrorKind::InvalidData, "N-Triples source is not UTF-8")
591        })?;
592        let line = line.trim();
593        if line.is_empty() || line.starts_with('#') {
594            skipped += 1;
595            continue;
596        }
597        let mut tokens = line.split_ascii_whitespace();
598        let (Some(subject), Some(predicate), Some(object)) =
599            (tokens.next(), tokens.next(), tokens.next())
600        else {
601            return Err(io::Error::new(
602                io::ErrorKind::InvalidData,
603                "source contains a non-comment line without an RDF triple",
604            ));
605        };
606        has_blank_nodes |=
607            subject.starts_with("_:") || predicate.starts_with("_:") || object.starts_with("_:");
608        spool.push(
609            QuadRecord {
610                subject: hash_token(subject),
611                predicate: hash_token(predicate),
612                object: hash_token(object),
613                context: 0,
614            },
615            budget,
616        )?;
617    }
618    Ok((skipped, has_blank_nodes))
619}
620
621/// Stream `QuadRecord`s from a single Q42 volume into sorted disk
622/// runs.
623fn stream_q42_records(
624    q42_path: &Path,
625    spool: &mut DiskSpool,
626    budget: &mut TempBudget,
627) -> io::Result<()> {
628    let volume = Q42Volume::open(q42_path)?;
629    if volume.volume_manifest()?.is_some() {
630        let set = crate::q42_volume::Q42VolumeSet::open_root(q42_path)?;
631        for segment in set.segments() {
632            stream_q42_volume_records(segment, spool, budget)?;
633        }
634        return Ok(());
635    }
636    stream_q42_volume_records(&volume, spool, budget)
637}
638
639/// Stream `QuadRecord`s across a Q42 volume set (manifest
640/// children) into sorted disk runs.
641fn stream_q42_volume_records(
642    volume: &Q42Volume,
643    spool: &mut DiskSpool,
644    budget: &mut TempBudget,
645) -> io::Result<()> {
646    let mut buffer = [0u8; SUPERBLOCK_SIZE];
647    for block_index in 0..volume.block_count() as usize {
648        volume.read_superblock_into(block_index, &mut buffer)?;
649        let quin_count = u64::from_le_bytes(buffer[16..24].try_into().unwrap()) as usize;
650        if quin_count > crate::QUINS_PER_BLOCK {
651            return Err(io::Error::new(
652                io::ErrorKind::InvalidData,
653                "Q42 superblock declares too many Quins",
654            ));
655        }
656        let mut offset = SUPERBLOCK_HEADER;
657        for _ in 0..quin_count {
658            let quin: crate::NQuin =
659                bytemuck::pod_read_unaligned(&buffer[offset..offset + QUIN_SIZE]);
660            if !quin.verify_ecc_parity() {
661                return Err(io::Error::new(
662                    io::ErrorKind::InvalidData,
663                    format!("Q42 parity mismatch in block {block_index}"),
664                ));
665            }
666            spool.push(
667                QuadRecord {
668                    subject: quin.subject,
669                    predicate: quin.predicate,
670                    object: quin.object,
671                    context: quin.context,
672                },
673                budget,
674            )?;
675            offset += QUIN_SIZE;
676        }
677    }
678    Ok(())
679}
680
681/// Write records verbatim to `path` (fixed-width binary run).
682fn write_records(path: &Path, records: &[QuadRecord]) -> io::Result<()> {
683    let mut writer = BufWriter::with_capacity(READ_BUFFER_BYTES, File::create(path)?);
684    for record in records {
685        writer.write_all(bytemuck::bytes_of(record))?;
686    }
687    writer.flush()
688}
689
690/// K-way merge all runs into a single sorted output file
691/// (grouped merges when the fan-in exceeds limits).
692fn merge_to_one(
693    mut runs: Vec<DiskRun>,
694    temp_dir: &Path,
695    prefix: &str,
696    budget: &mut TempBudget,
697) -> io::Result<DiskRun> {
698    if runs.is_empty() {
699        let path = temp_dir.join(format!("{prefix}-empty.bin"));
700        File::create(&path)?;
701        return Ok(DiskRun { path, bytes: 0 });
702    }
703    let mut round = 0usize;
704    while runs.len() > 1 {
705        let mut next = Vec::with_capacity(runs.len().div_ceil(MERGE_FAN_IN));
706        let mut group_index = 0usize;
707        while !runs.is_empty() {
708            let group_len = runs.len().min(MERGE_FAN_IN);
709            let group: Vec<DiskRun> = runs.drain(..group_len).collect();
710            let bytes: u64 = group.iter().map(|run| run.bytes).sum();
711            budget.reserve(bytes)?;
712            let output = temp_dir.join(format!("{prefix}-merge-{round:04}-{group_index:08}.bin"));
713            group_index += 1;
714            if let Err(error) = merge_group(&group, &output) {
715                budget.release(bytes);
716                return Err(error);
717            }
718            for run in group {
719                std::fs::remove_file(&run.path)?;
720                budget.release(run.bytes);
721            }
722            next.push(DiskRun {
723                path: output,
724                bytes,
725            });
726        }
727        runs = next;
728        round += 1;
729    }
730    Ok(runs.pop().expect("non-empty run list"))
731}
732
733/// Merge one group of runs into `output` via a min-heap over
734/// per-run readers.
735fn merge_group(group: &[DiskRun], output: &Path) -> io::Result<()> {
736    let mut readers = Vec::with_capacity(group.len());
737    for run in group {
738        readers.push(RecordReader::open(&run.path)?);
739    }
740    let mut writer = BufWriter::with_capacity(READ_BUFFER_BYTES, File::create(output)?);
741    loop {
742        let mut minimum: Option<(usize, QuadRecord)> = None;
743        for (index, reader) in readers.iter().enumerate() {
744            if let Some(record) = reader.peek {
745                if minimum.is_none_or(|(_, current)| record < current) {
746                    minimum = Some((index, record));
747                }
748            }
749        }
750        let Some((index, record)) = minimum else {
751            break;
752        };
753        writer.write_all(bytemuck::bytes_of(&record))?;
754        readers[index].advance()?;
755    }
756    writer.flush()
757}
758
759struct RecordReader {
760    reader: BufReader<File>,
761    peek: Option<QuadRecord>,
762}
763
764impl RecordReader {
765    /// Buffered reader over a sorted run file, positioned before
766    /// the first record.
767    fn open(path: &Path) -> io::Result<Self> {
768        let mut reader = Self {
769            reader: BufReader::with_capacity(READ_BUFFER_BYTES, File::open(path)?),
770            peek: None,
771        };
772        reader.advance()?;
773        Ok(reader)
774    }
775
776    /// Advance to the next record (EOF sets `current` to `None`).
777    fn advance(&mut self) -> io::Result<()> {
778        let mut bytes = [0u8; RECORD_BYTES as usize];
779        match self.reader.read_exact(&mut bytes) {
780            Ok(()) => {
781                self.peek = Some(bytemuck::pod_read_unaligned(&bytes));
782                Ok(())
783            }
784            Err(error) if error.kind() == io::ErrorKind::UnexpectedEof => {
785                self.peek = None;
786                Ok(())
787            }
788            Err(error) => Err(error),
789        }
790    }
791
792    /// Next record strictly greater than the previous emission —
793    /// skips duplicates in the sorted run.
794    fn next_distinct(&mut self) -> io::Result<Option<QuadRecord>> {
795        let Some(record) = self.peek else {
796            return Ok(None);
797        };
798        while self.peek == Some(record) {
799            self.advance()?;
800        }
801        Ok(Some(record))
802    }
803}
804
805#[derive(Default)]
806struct SetComparison {
807    left_unique: u64,
808    right_unique: u64,
809    missing: u64,
810    unexpected: u64,
811    first_missing: Option<QuadRecord>,
812    first_unexpected: Option<QuadRecord>,
813}
814
815/// Two-pointer scan over the two sorted-unique runs — counts
816/// common, left-only, and right-only records.
817fn compare_unique_sets(left: &Path, right: &Path) -> io::Result<SetComparison> {
818    let mut left_reader = RecordReader::open(left)?;
819    let mut right_reader = RecordReader::open(right)?;
820    let mut left_record = left_reader.next_distinct()?;
821    let mut right_record = right_reader.next_distinct()?;
822    let mut result = SetComparison::default();
823
824    loop {
825        match (left_record, right_record) {
826            (Some(left), Some(right)) => match left.cmp(&right) {
827                Ordering::Equal => {
828                    result.left_unique += 1;
829                    result.right_unique += 1;
830                    left_record = left_reader.next_distinct()?;
831                    right_record = right_reader.next_distinct()?;
832                }
833                Ordering::Less => {
834                    result.left_unique += 1;
835                    result.missing += 1;
836                    result.first_missing.get_or_insert(left);
837                    left_record = left_reader.next_distinct()?;
838                }
839                Ordering::Greater => {
840                    result.right_unique += 1;
841                    result.unexpected += 1;
842                    result.first_unexpected.get_or_insert(right);
843                    right_record = right_reader.next_distinct()?;
844                }
845            },
846            (Some(left), None) => {
847                result.left_unique += 1;
848                result.missing += 1;
849                result.first_missing.get_or_insert(left);
850                left_record = left_reader.next_distinct()?;
851            }
852            (None, Some(right)) => {
853                result.right_unique += 1;
854                result.unexpected += 1;
855                result.first_unexpected.get_or_insert(right);
856                right_record = right_reader.next_distinct()?;
857            }
858            (None, None) => return Ok(result),
859        }
860    }
861}