Skip to main content

rete_core/v06/
write.rs

1//! The `0x06` assembler: [`super::parts::Parts`] in, a `0x06` file out. Every
2//! writer goes through here — the in-RAM build (via `0x05` section images),
3//! `rete convert`, and the memory-bounded build and `merge` (which hand it their
4//! spill as an address space, see `extbuild_v06`). `recard` only re-lays the
5//! front.
6//!
7//! The front (root, card region, stats, leaf directories) is built in memory;
8//! the data region is streamed from the input reader, hashed on the way. The
9//! data is written first at its final offset, then the front at offset 0, so the
10//! output needs `Write + Seek` and the input is read once.
11
12use std::io::{Seek, SeekFrom, Write};
13
14use super::parts::Parts;
15use super::*;
16use crate::file::{compress, FileError};
17use crate::reader::RangeReader;
18
19/// How quad tiles are clustered in the data region.
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub enum QuadClustering {
22    /// Graph-major when the mean graph is smaller than a tile, else order-major.
23    Auto,
24    /// The tiles of every order for one block of graphs side by side.
25    GraphMajor,
26    /// Each order's tiles contiguous.
27    OrderMajor,
28}
29
30impl QuadClustering {
31    /// `RETE_QUAD_CLUSTERING=graph|order|auto` (default auto).
32    pub fn from_env() -> Self {
33        match std::env::var("RETE_QUAD_CLUSTERING").ok().as_deref() {
34            Some("graph") => QuadClustering::GraphMajor,
35            Some("order") => QuadClustering::OrderMajor,
36            _ => QuadClustering::Auto,
37        }
38    }
39}
40
41/// How big the writer makes directory leaves (SPEC.md §9): small, because a
42/// leaf is what a cold lookup transfers; the root carries the leaf lists.
43#[derive(Debug, Clone, Copy, PartialEq, Eq)]
44pub struct LeafPolicy {
45    /// Uncompressed size a leaf is cut at to begin with.
46    pub start: usize,
47    /// The largest a leaf grows to in order to bring the root under
48    /// `root_budget`. Growing happens only if one leaf per directory would
49    /// fit the budget.
50    pub max: usize,
51    /// Stored root size the writer tries to stay under.
52    pub root_budget: usize,
53    /// The most the leaf lists may add to the root of one leaf per directory;
54    /// past that every directory's leaves grow, beyond `max`.
55    pub list_cap: usize,
56}
57
58impl Default for LeafPolicy {
59    fn default() -> Self {
60        LeafPolicy {
61            start: LEAF_START,
62            max: LEAF_MAX,
63            root_budget: ROOT_BUDGET,
64            list_cap: LIST_CAP,
65        }
66    }
67}
68
69/// Assembly options.
70#[derive(Debug, Clone)]
71pub struct WriteOpts {
72    /// Codec of the root, leaves, card and stats (`writer_codec()`).
73    pub internal_codec: u8,
74    /// Quad tile clustering.
75    pub quad: QuadClustering,
76    /// Directory leaf sizes.
77    pub leaves: LeafPolicy,
78    /// The generation to write: [`VERSION`] (always, for every real writer) or
79    /// [`VERSION_06`], which the tests use to make a `0x06` input for `convert`
80    /// (label root inside the root, no annex).
81    pub version: u8,
82    /// Cluster the subject-leading permutations by class (`0x07` only); `None`
83    /// writes them in subject order, and un-clusters a clustered input.
84    pub cluster: Option<crate::write_opts::ClusterOpts>,
85    /// Find derived IRI families (`0x08`, SPEC.md section 5.3): the writer looks
86    /// for IRIs the index spells out, and drops the subject-only dictionary
87    /// chunks whose terms all derive, when that is worth it. `None` = never.
88    /// On by default.
89    pub derive: Option<crate::derived::DeriveOpts>,
90    /// Where this writer spills the sort runs of the `0x07` quad orders and of
91    /// class clustering; `None` = the system temporary directory. Per writer,
92    /// never shared: another writer in the process may delete its own.
93    pub spill_dir: Option<std::path::PathBuf>,
94}
95
96impl WriteOpts {
97    /// These options spilling into `dir`.
98    pub fn with_spill_dir(mut self, dir: Option<std::path::PathBuf>) -> Self {
99        self.spill_dir = dir;
100        self
101    }
102
103    /// The directory the spill runs go to.
104    pub(crate) fn spill(&self) -> std::path::PathBuf {
105        // A browser build has no disk (and no temporary directory to ask for).
106        #[cfg(target_arch = "wasm32")]
107        {
108            self.spill_dir.clone().unwrap_or_default()
109        }
110        #[cfg(not(target_arch = "wasm32"))]
111        {
112            self.spill_dir.clone().unwrap_or_else(std::env::temp_dir)
113        }
114    }
115
116    /// These options with derived-IRI detection on (`Some`) or off.
117    pub fn with_derive(mut self, derive: Option<crate::derived::DeriveOpts>) -> Self {
118        self.derive = derive;
119        self
120    }
121
122    /// These options with class clustering on (`Some`) or off.
123    pub fn with_cluster(mut self, c: Option<crate::write_opts::ClusterOpts>) -> Self {
124        self.cluster = c;
125        self
126    }
127}
128
129impl Default for WriteOpts {
130    fn default() -> Self {
131        WriteOpts {
132            internal_codec: crate::file::writer_codec(),
133            quad: QuadClustering::from_env(),
134            leaves: LeafPolicy::default(),
135            version: VERSION,
136            cluster: crate::write_opts::cluster(),
137            derive: Some(crate::derived::DeriveOpts::default()),
138            spill_dir: None,
139        }
140    }
141}
142
143/// What the assembler wrote.
144#[derive(Debug, Clone)]
145pub struct Written {
146    /// The header as written.
147    pub header: Header06,
148    /// The root as written.
149    pub root: Root06,
150}
151
152/// One segment of the data region: input bytes to copy.
153#[derive(Debug, Clone, Copy)]
154struct Seg {
155    input: u64,
156    len: u64,
157    /// The block is stored uncompressed (a raw quad tile).
158    raw: bool,
159}
160
161/// A data section: its kind and the input segments, in output order.
162struct DataSec {
163    kind: u8,
164    segs: Vec<Seg>,
165    /// Each segment is one compressed block of this codec, whose decompressed
166    /// size the writer records ([`Sec06::max_block`]); `None` = not measured.
167    measure: Option<u8>,
168    /// A largest block known without measuring (the dictionary's, from the
169    /// rekey), or 0.
170    known_max: u64,
171    /// Bytes written from memory rather than copied from the input (the card
172    /// annex); `segs` is empty then.
173    inline: Option<Vec<u8>>,
174}
175
176impl DataSec {
177    fn len(&self) -> u64 {
178        if let Some(b) = &self.inline {
179            return b.len() as u64;
180        }
181        self.segs.iter().map(|s| s.len).sum()
182    }
183}
184
185/// Leaf groups whose leaf size the root budget may grow.
186#[derive(Clone)]
187struct Targets {
188    dict: [usize; 4],
189    index: [usize; 6],
190    quad: [usize; crate::quad7::NUM_SLOTS],
191    text: usize,
192}
193
194/// The front built for a set of leaf targets.
195struct Front {
196    units: Vec<(u8, Vec<u8>)>,
197    dict_leaves: Vec<u8>,
198    index_leaves: Vec<u8>,
199    quad_leaves: Vec<u8>,
200    text_leaves: Vec<u8>,
201    /// The largest leaf of each leaves section, decompressed: dict, index,
202    /// quad, text.
203    leaf_max: [u64; 4],
204    /// Leaves per group, to pick which group to grow: `(group id, count)`.
205    counts: Vec<(usize, usize)>,
206}
207
208/// Leaf-group id of the text index (dictionary 0..4, index 4..10, quad 10..19).
209const TEXT_GROUP: usize = 19;
210
211/// Order in which dictionary sections are laid out (predicates first).
212const DICT_ORDER: [usize; 4] = [3, 0, 1, 2];
213
214/// Lay out the data region: the input segments of every data section and, for
215/// the quad index, each tile's new offset within QUAD_DATA.
216#[allow(clippy::type_complexity)]
217fn layout_data(
218    parts: &Parts,
219    graph_major: bool,
220) -> (Vec<DataSec>, [u64; 4], Vec<u64>, Vec<Vec<u64>>) {
221    let mut secs = Vec::new();
222    // Dictionary: sections in DICT_ORDER, each a run of chunks.
223    let mut dict_off = [0u64; 4];
224    let mut segs = Vec::new();
225    let mut at = 0u64;
226    for &s in &DICT_ORDER {
227        dict_off[s] = at;
228        for (c, inp) in &parts.dict[s].chunks {
229            segs.push(Seg {
230                input: *inp,
231                len: c.clen,
232                raw: false,
233            });
234            at += c.clen;
235        }
236    }
237    if at > 0 {
238        secs.push(DataSec {
239            kind: kind::DICT_DATA,
240            segs,
241            measure: None,
242            known_max: parts.dict.iter().map(|d| d.max_raw).max().unwrap_or(0),
243            inline: None,
244        });
245    }
246    // Index: permutations in section-index order.
247    let mut perm_off = Vec::new();
248    let mut segs = Vec::new();
249    let mut at = 0u64;
250    for p in &parts.index {
251        perm_off.push(at);
252        for (t, inp) in &p.tiles {
253            segs.push(Seg {
254                input: *inp,
255                len: t.clen,
256                raw: false,
257            });
258            at += t.clen;
259        }
260    }
261    if at > 0 {
262        secs.push(DataSec {
263            kind: kind::INDEX_DATA,
264            segs,
265            measure: Some(parts.block_codec),
266            known_max: 0,
267            inline: None,
268        });
269    }
270    // Quad: order-major, or graph-major by directory block.
271    let mut quad_off: Vec<Vec<u64>> = Vec::new();
272    if let Some(q) = &parts.quad {
273        let mut segs = Vec::new();
274        quad_off = q.orders.iter().map(|(_, t)| vec![0u64; t.len()]).collect();
275        let mut at = 0u64;
276        if graph_major {
277            let firsts = block_first_graphs(&q.p0);
278            // The block a tile belongs to: the last block whose first graph is
279            // <= the tile's first graph.
280            let block_of = |g: u32| firsts.partition_point(|&f| f <= g).saturating_sub(1);
281            let mut cursor = vec![0usize; q.orders.len()];
282            for b in 0..firsts.len().max(1) {
283                for (k, (_, tiles)) in q.orders.iter().enumerate() {
284                    while cursor[k] < tiles.len()
285                        && (firsts.is_empty() || block_of(tiles[cursor[k]].first.0) <= b)
286                    {
287                        let t = &tiles[cursor[k]];
288                        quad_off[k][cursor[k]] = at;
289                        segs.push(Seg {
290                            input: t.off,
291                            len: t.clen,
292                            raw: t.raw,
293                        });
294                        at += t.clen;
295                        cursor[k] += 1;
296                    }
297                }
298            }
299            // Anything left (a tile past the last block's first graph is already
300            // covered above; this only guards a malformed P0).
301            for (k, (_, tiles)) in q.orders.iter().enumerate() {
302                while cursor[k] < tiles.len() {
303                    let t = &tiles[cursor[k]];
304                    quad_off[k][cursor[k]] = at;
305                    segs.push(Seg {
306                        input: t.off,
307                        len: t.clen,
308                        raw: t.raw,
309                    });
310                    at += t.clen;
311                    cursor[k] += 1;
312                }
313            }
314        } else {
315            for (k, (_, tiles)) in q.orders.iter().enumerate() {
316                for (i, t) in tiles.iter().enumerate() {
317                    quad_off[k][i] = at;
318                    segs.push(Seg {
319                        input: t.off,
320                        len: t.clen,
321                        raw: t.raw,
322                    });
323                    at += t.clen;
324                }
325            }
326        }
327        if at > 0 {
328            secs.push(DataSec {
329                kind: kind::QUAD_DATA,
330                segs,
331                measure: Some(parts.block_codec),
332                known_max: 0,
333                inline: None,
334            });
335        }
336    }
337    if let Some(l) = &parts.labels {
338        if l.data_len > 0 {
339            secs.push(DataSec {
340                kind: kind::LABEL_DATA,
341                segs: vec![Seg {
342                    input: l.body.offset,
343                    len: l.data_len,
344                    raw: false,
345                }],
346                measure: None,
347                known_max: 0,
348                inline: None,
349            });
350        }
351    }
352    if let Some(t) = &parts.text {
353        if t.postings.len > 0 {
354            secs.push(DataSec {
355                kind: kind::TEXT_DATA,
356                segs: vec![Seg {
357                    input: t.postings.offset,
358                    len: t.postings.len,
359                    raw: false,
360                }],
361                measure: None,
362                known_max: 0,
363                inline: None,
364            });
365        }
366    }
367    if let Some(py) = parts.pyramid {
368        if py.len > 0 {
369            secs.push(DataSec {
370                kind: kind::PYRAMID,
371                segs: vec![Seg {
372                    input: py.offset,
373                    len: py.len,
374                    raw: false,
375                }],
376                measure: None,
377                known_max: 0,
378                inline: None,
379            });
380        }
381    }
382    (secs, dict_off, perm_off, quad_off)
383}
384
385/// First graph id of each graph-directory block, from a `P0` block index.
386fn block_first_graphs(p0: &[u8]) -> Vec<u32> {
387    let mut c = Cur::new(p0);
388    let mut out = Vec::new();
389    let Ok(n) = c.count(u32::MAX as u64) else {
390        return out;
391    };
392    let mut g = 0u32;
393    for _ in 0..n {
394        let (Ok(d), Ok(_)) = (c.u32v(), c.uv()) else {
395            break;
396        };
397        g = g.saturating_add(d);
398        out.push(g);
399    }
400    out
401}
402
403/// Compress each leaf of `entries` (cut at `target` encoded bytes) and append
404/// it to `section`. Returns `(leaf ref, first entry index)` per leaf.
405fn leaves_of<E>(
406    entries: &[E],
407    target: usize,
408    codec: u8,
409    section: &mut Vec<u8>,
410    max_raw: &mut u64,
411    encode: impl Fn(&[E], usize) -> Vec<u8>,
412) -> Vec<LeafRef> {
413    let sizes: Vec<usize> = entries
414        .chunks(1)
415        .enumerate()
416        .map(|(i, e)| encode(e, i).len())
417        .collect();
418    let mut out = Vec::new();
419    for (a, b) in cut(&sizes, target) {
420        let raw = encode(&entries[a..b], a);
421        *max_raw = (*max_raw).max(raw.len() as u64);
422        let stored = compress(codec, &raw);
423        out.push(LeafRef {
424            first: a,
425            n: b - a,
426            off: section.len() as u64,
427            len: stored.len() as u64,
428        });
429        section.extend_from_slice(&stored);
430    }
431    out
432}
433
434#[allow(clippy::too_many_arguments)]
435fn build_front(
436    parts: &Parts,
437    t: &Targets,
438    codec: u8,
439    dict_off: &[u64; 4],
440    perm_off: &[u64],
441    quad_off: &[Vec<u64>],
442    quad_gdir: &[u8],
443    version: u8,
444) -> Front {
445    let mut f = Front {
446        units: Vec::new(),
447        dict_leaves: Vec::new(),
448        index_leaves: Vec::new(),
449        quad_leaves: Vec::new(),
450        text_leaves: Vec::new(),
451        leaf_max: [0; 4],
452        counts: Vec::new(),
453    };
454    // Dictionary.
455    let mut droots: [DictSecRoot; 4] = Default::default();
456    for &s in &DICT_ORDER {
457        let d = &parts.dict[s];
458        let ents: Vec<ChunkEnt> = d.chunks.iter().map(|(c, _)| c.clone()).collect();
459        let leaves = leaves_of(
460            &ents,
461            t.dict[s],
462            codec,
463            &mut f.dict_leaves,
464            &mut f.leaf_max[0],
465            |e, _| encode_chunk_leaf(e),
466        );
467        // Offset of each chunk within the section's data.
468        let mut coff = Vec::with_capacity(ents.len());
469        let mut at = 0u64;
470        for e in &ents {
471            coff.push(at);
472            at += e.clen;
473        }
474        f.counts.push((s, leaves.len()));
475        droots[s] = DictSecRoot {
476            term_count: d.term_count,
477            restart_interval: d.restart_interval,
478            n_chunks: ents.len(),
479            data_off: dict_off[s],
480            data_len: at,
481            leaves: leaves
482                .into_iter()
483                .map(|l| {
484                    let e = &ents[l.first];
485                    let run = e.first_run;
486                    let key = e.key.clone();
487                    let co = coff[l.first];
488                    (l, run, co, key)
489                })
490                .collect(),
491            groups: d.groups,
492        };
493    }
494    f.units
495        .push((tag::DICT, encode_dict_root(&droots, version)));
496    if !parts.derived.is_empty() {
497        f.units.push((
498            tag::DERIVED,
499            crate::derived::encode_families(&parts.derived),
500        ));
501    }
502    // Index.
503    let mut proots = Vec::new();
504    for (pi, p) in parts.index.iter().enumerate() {
505        let ents: Vec<TileEnt> = p.tiles.iter().map(|(t, _)| *t).collect();
506        // A clustered permutation cuts its leaves at the runs: no leaf spans two.
507        let runs: Vec<(usize, usize)> = match parts.cluster.iter().find(|c| c.si == p.si) {
508            Some(c) => {
509                let mut at = 0;
510                c.run_tiles
511                    .iter()
512                    .map(|&n| {
513                        at += n;
514                        (at - n, at)
515                    })
516                    .collect()
517            }
518            None => vec![(0, ents.len())],
519        };
520        let mut leaves = Vec::new();
521        for (a, b) in runs {
522            for mut l in leaves_of(
523                &ents[a..b],
524                t.index[p.si],
525                codec,
526                &mut f.index_leaves,
527                &mut f.leaf_max[1],
528                |e, _| encode_tile_leaf(e),
529            ) {
530                l.first += a;
531                leaves.push(l);
532            }
533        }
534        let mut toff = Vec::with_capacity(ents.len());
535        let mut at = 0u64;
536        for e in &ents {
537            toff.push(at);
538            at += e.clen;
539        }
540        f.counts.push((4 + p.si, leaves.len()));
541        proots.push(PermRoot {
542            si: p.si,
543            n_tiles: ents.len(),
544            data_off: perm_off[pi],
545            data_len: at,
546            leaves: leaves
547                .into_iter()
548                .map(|l| {
549                    let mn = ents[l.first].min_a;
550                    let mx = ents[l.first + l.n - 1].max_a;
551                    let o = toff[l.first];
552                    (l, mn, mx, o)
553                })
554                .collect(),
555        });
556    }
557    f.units.push((tag::INDEX, encode_index_root(&proots)));
558    if !parts.cluster.is_empty() {
559        f.units
560            .push((tag::CLUSTER, encode_cluster_root(&parts.cluster)));
561    }
562    // Quad.
563    if let Some(q) = &parts.quad {
564        f.quad_leaves.extend_from_slice(quad_gdir);
565        let mut orders = Vec::new();
566        for (k, (si, tiles)) in q.orders.iter().enumerate() {
567            let ents: Vec<QTileEnt> = tiles
568                .iter()
569                .enumerate()
570                .map(|(i, e)| QTileEnt {
571                    off: quad_off[k][i],
572                    ..*e
573                })
574                .collect();
575            // A clustered order (SPOG) cuts its leaves at the runs.
576            let runs: Vec<(usize, usize)> = match parts
577                .cluster
578                .iter()
579                .find(|c| c.si == QUAD_SPOG && *si == QUAD_SPOG)
580            {
581                Some(c) => {
582                    let mut at = 0;
583                    c.run_tiles
584                        .iter()
585                        .map(|&n| {
586                            at += n;
587                            (at - n, at)
588                        })
589                        .collect()
590                }
591                None => vec![(0, ents.len())],
592            };
593            let mut leaves = Vec::new();
594            for (a, b) in runs {
595                for mut l in leaves_of(
596                    &ents[a..b],
597                    t.quad[*si],
598                    codec,
599                    &mut f.quad_leaves,
600                    &mut f.leaf_max[2],
601                    |e, i| {
602                        let _ = i;
603                        encode_qtile_leaf(e, e[0].off, has_v07(version))
604                    },
605                ) {
606                    l.first += a;
607                    leaves.push(l);
608                }
609            }
610            f.counts.push((10 + si, leaves.len()));
611            orders.push(QuadOrderRoot {
612                si: *si,
613                n_tiles: ents.len(),
614                leaves: leaves
615                    .into_iter()
616                    .map(|l| {
617                        let a = &ents[l.first];
618                        let b = &ents[l.first + l.n - 1];
619                        let o = a.off;
620                        (l, a.first, b.last, o)
621                    })
622                    .collect(),
623            });
624        }
625        f.units.push((
626            tag::QUAD,
627            encode_quad_root(&QuadRoot {
628                graph_count: q.graph_count,
629                quad_count: q.quad_count,
630                block_graphs: q.block_graphs,
631                p0: q.p0.clone(),
632                gdir_len: quad_gdir.len() as u64,
633                orders,
634            }),
635        ));
636    }
637    // Labels.
638    if let Some(l) = &parts.labels {
639        f.units.push((
640            tag::LABELS,
641            // 0x07: the unit root keeps the 32-byte preamble only; the root
642            // node follows in its own section (kind LABEL_ROOT).
643            encode_label_root(&LabelRoot {
644                data_len: l.data_len,
645                head: if has_v07(version) {
646                    l.head[..l.head.len().min(crate::label_index::PREAMBLE_LEN)].to_vec()
647                } else {
648                    l.head.clone()
649                },
650            }),
651        ));
652    }
653    // Text.
654    if let Some(tp) = &parts.text {
655        let leaves = leaves_of(
656            &tp.tokens,
657            t.text,
658            codec,
659            &mut f.text_leaves,
660            &mut f.leaf_max[3],
661            |e, _| encode_token_leaf(e),
662        );
663        f.counts.push((TEXT_GROUP, leaves.len()));
664        f.units.push((
665            tag::TEXT,
666            encode_text_root(&TextRoot {
667                scope: tp.scope.clone(),
668                n_tokens: tp.tokens.len(),
669                leaves: leaves
670                    .into_iter()
671                    .map(|l| {
672                        let tok = tp.tokens[l.first].token.clone();
673                        (l, tok)
674                    })
675                    .collect(),
676            }),
677        ));
678    }
679    f
680}
681
682/// Copy `segs` from `input` to `out`, coalescing input-adjacent segments into
683/// reads of at most 8 MiB, hashing everything written into `h`.
684#[allow(clippy::too_many_arguments)]
685fn copy_segs(
686    input: &dyn RangeReader,
687    segs: &[Seg],
688    measure: Option<u8>,
689    out: &mut dyn Write,
690    h: &mut blake3::Hasher,
691    progress: &mut dyn FnMut(u64),
692    consumed: &mut dyn FnMut(u64, u64),
693    settle: &mut dyn FnMut(&mut dyn Write) -> std::io::Result<()>,
694) -> Result<u64, FileError> {
695    const SPAN: u64 = 8 << 20;
696    // The ceiling for measuring a block whose frame does not state its size:
697    // generous, since this only bounds the writer's own check.
698    const MEASURE_CEILING: u64 = 1 << 30;
699    let mut max_raw = 0u64;
700    let mut done = 0u64;
701    let mut i = 0;
702    while i < segs.len() {
703        let start = segs[i].input;
704        let mut end = start + segs[i].len;
705        let mut j = i + 1;
706        while j < segs.len() && segs[j].input == end && end - start < SPAN {
707            end += segs[j].len;
708            j += 1;
709        }
710        if let Some(codec) = measure {
711            // Blocks are measured whole, so the run is read in one piece.
712            let b = input.read_at(start, end - start)?;
713            for sg in &segs[i..j] {
714                let lo = (sg.input - start) as usize;
715                let blk = &b[lo..lo + sg.len as usize];
716                let n = if sg.raw {
717                    sg.len
718                } else {
719                    crate::file::block_raw_len(codec, blk, MEASURE_CEILING)?
720                };
721                max_raw = max_raw.max(n);
722            }
723            h.update(&b);
724            out.write_all(&b)?;
725            done += b.len() as u64;
726            progress(done);
727        } else {
728            let mut at = start;
729            while at < end {
730                let n = (end - at).min(SPAN);
731                let b = input.read_at(at, n)?;
732                h.update(&b);
733                out.write_all(&b)?;
734                at += n;
735                done += n;
736                progress(done);
737            }
738        }
739        for sg in &segs[i..j] {
740            consumed(sg.input, sg.len);
741        }
742        settle(out)?;
743        i = j;
744    }
745    Ok(max_raw)
746}
747
748/// The largest graph-directory block of a quad index, decompressed.
749fn gdir_max(p0: &[u8], gdir: &[u8], codec: u8) -> Result<u64, FileError> {
750    let mut c = Cur::new(p0);
751    let n = c.count(u32::MAX as u64)?;
752    let (mut at, mut max) = (0usize, 0u64);
753    for _ in 0..n {
754        let _ = c.u32v()?;
755        let packed = c.uv()?;
756        let len = (packed >> 1) as usize;
757        let blk = gdir
758            .get(at..at + len)
759            .ok_or(FileError::Container("quad graph directory overruns"))?;
760        let raw = if packed & 1 == 1 {
761            len as u64
762        } else {
763            crate::file::block_raw_len(codec, blk, 1 << 30)?
764        };
765        max = max.max(raw);
766        at += len;
767    }
768    Ok(max)
769}
770
771/// Assemble a `0x06` file from `parts`, whose payload ranges point into `input`.
772pub fn assemble<W: Write + Seek>(
773    parts: &Parts,
774    input: &dyn RangeReader,
775    out: &mut W,
776    opts: WriteOpts,
777) -> Result<Written, FileError> {
778    assemble_with(
779        parts,
780        input,
781        out,
782        opts,
783        &mut Hooks {
784            copied: &mut |_| {},
785            progress: &mut |_, _| {},
786            needed: &mut |_, _| {},
787            consumed: &mut |_, _| {},
788            settle: &mut |_| Ok(()),
789        },
790    )
791}
792
793/// What [`assemble_with`] reports while it writes.
794pub struct Hooks<'a> {
795    /// Called once each data section (a [`kind`] of `DICT_DATA`, `INDEX_DATA`,
796    /// `QUAD_DATA`, `LABEL_DATA`, `TEXT_DATA` or `PYRAMID`) is in the output:
797    /// the input bytes it came from are not read again.
798    pub copied: &'a mut dyn FnMut(u8),
799    /// `(data bytes written so far, data bytes in all)`, after each write.
800    pub progress: &'a mut dyn FnMut(u64, u64),
801    /// `(input offset, length)` of every payload range the copy will read,
802    /// announced once before the first byte is written.
803    pub needed: &'a mut dyn FnMut(u64, u64),
804    /// `(input offset, length)` of a payload range now in the output, whatever
805    /// order the ranges come in. Once every announced range of a spill file
806    /// has been consumed, nothing reads that file again.
807    pub consumed: &'a mut dyn FnMut(u64, u64),
808    /// Called with the output after every copied run and every finished data
809    /// section, once `consumed` / `copied` may have made spill files ready to
810    /// go. The implementation flushes `out`, makes the bytes durable, and only
811    /// then deletes: a file must never be removed while its bytes are still in
812    /// a buffer or an unsynced page.
813    pub settle: &'a mut dyn FnMut(&mut dyn Write) -> std::io::Result<()>,
814}
815
816/// [`assemble`], reporting through `hooks`. The memory-bounded build deletes
817/// each spill file as soon as every range it feeds is in the output, so the
818/// output grows as the spill shrinks, and drives `--progress` from the byte
819/// count.
820pub fn assemble_with<W: Write + Seek>(
821    parts: &Parts,
822    input: &dyn RangeReader,
823    out: &mut W,
824    opts: WriteOpts,
825    hooks: &mut Hooks<'_>,
826) -> Result<Written, FileError> {
827    // The terms' order is part of the generation: a `0x08` file holds its
828    // dictionary in the SPARQL order, an older one in byte order, and a reader
829    // searches with the one its version names.
830    if parts.order != term_order(opts.version) {
831        return Err(FileError::Container(
832            "the dictionary's term order is not that of the format generation being written: `rete convert` re-sorts a dictionary",
833        ));
834    }
835    if parts.order == crate::term_order::TermOrder::Sparql
836        && parts
837            .dict
838            .iter()
839            .any(|d| d.groups.total() != d.term_count as u64)
840    {
841        return Err(FileError::Container(
842            "0x08 dictionary term groups do not add up to the term count",
843        ));
844    }
845    // `0x07` writes SPOG, POSG and OSPG next to GSPO: derive them from the GSPO
846    // tiles first (the other graph-leading orders of the input are dropped).
847    if has_v07(opts.version) && super::neworders::needed(parts) {
848        let (derived, extras) = super::neworders::derive(parts, input, &opts.spill())?;
849        let layered = super::neworders::Layered::new(input, &extras);
850        return assemble_with(&derived, &layered, out, opts.clone(), hooks);
851    }
852    // `--cluster-subjects-by-class`: the subject-leading permutations by class
853    // (or back to subject order). Another pass over the input, same shape.
854    if has_v07(opts.version) && super::cluster::needed(parts, opts.cluster) {
855        if let Some((derived, extras)) =
856            super::cluster::derive(parts, input, opts.cluster, &opts.spill())?
857        {
858            let layered = super::neworders::Layered::new(input, &extras);
859            return assemble_with(&derived, &layered, out, opts.clone(), hooks);
860        }
861    }
862    // Derived IRI families: find the subject-only chunks whose terms the index
863    // and the object dictionary rebuild, and drop their bodies when that is
864    // worth it; either way the build record says what was found. The pass
865    // runs once: the next call has it off.
866    if opts.version >= VERSION {
867        if let (Some(d), true) = (opts.derive, super::derived::needed(parts)) {
868            if let Some(derived) = super::derived::detect_and_derive(parts, input, &d)? {
869                return assemble_with(&derived, input, out, opts.with_derive(None), hooks);
870            }
871        }
872    }
873    let codec = opts.internal_codec;
874    if parts.pyramid_levels > u8::MAX as u16 {
875        return Err(FileError::Container(
876            "0x06 stores at most 255 pyramid levels",
877        ));
878    }
879    // Ids are dense and 1-based, so no position holds an id above the term
880    // count (graphs: the graph count). Checked, never truncated.
881    let id_widths = super::id_widths_for([
882        parts.term_count,
883        parts.term_count,
884        parts.term_count,
885        parts.quad.as_ref().map_or(0, |q| q.graph_count),
886    ])?;
887    // `0x07` is order-major, always: its graph-leading order is one, and the
888    // graph-last orders have no graph neighbourhood to cluster on.
889    // Quad clustering (`0x06`): graph-major when the mean graph is under a tile.
890    let graph_major = match (&parts.quad, opts.quad) {
891        (None, _) => false,
892        (_, _) if has_v07(opts.version) => false,
893        (Some(_), QuadClustering::GraphMajor) => true,
894        (Some(_), QuadClustering::OrderMajor) => false,
895        (Some(q), QuadClustering::Auto) => {
896            let bytes: u64 = q.orders.iter().flat_map(|(_, t)| t).map(|t| t.clen).sum();
897            q.graph_count > 0 && bytes / q.graph_count.max(1) < 64 * 1024
898        }
899    };
900    let (data, dict_off, perm_off, quad_off) = layout_data(parts, graph_major);
901    for d in &data {
902        for sg in &d.segs {
903            (hooks.needed)(sg.input, sg.len);
904        }
905    }
906    let quad_gdir = match &parts.quad {
907        Some(q) if q.gdir.len > 0 => input.read_at(q.gdir.offset, q.gdir.len)?,
908        _ => Vec::new(),
909    };
910    let label_nodes = match &parts.labels {
911        Some(l) if l.nodes.is_some_and(|n| n.len > 0) => {
912            let n = l.nodes.unwrap_or_default();
913            input.read_at(n.offset, n.len)?
914        }
915        Some(l) if l.nodes.is_none() && l.body.len > l.data_len => {
916            input.read_at(l.body.offset + l.data_len, l.body.len - l.data_len)?
917        }
918        _ => Vec::new(),
919    };
920
921    // Leaf policy (`opts.leaves`). A leaf is a cold lookup's unit of transfer,
922    // so leaves stay small (`start`) and the root carries the leaf lists.
923    //  1. They grow, up to `max`, only to bring the stored root under
924    //     `root_budget`, and only when that can work: if the root is over
925    //     budget even with one leaf per directory (the graph directory's block
926    //     index alone can do that), bigger leaves would cost every lookup
927    //     bytes and buy nothing.
928    //  2. The leaf lists add at most `list_cap` to the root of one leaf per
929    //     directory; past that every directory's leaves double, beyond `max`.
930    let pol = opts.leaves;
931    let root_len_of = |front: &Front| {
932        Root06 {
933            sections: vec![
934                Sec06 {
935                    kind: 0,
936                    max_block: 0,
937                    offset: 0,
938                    len: 0,
939                    digest: [0; 16]
940                };
941                kind::ORDER.len()
942            ],
943            units: front.units.clone(),
944        }
945        .encode(codec)
946        .len()
947    };
948    let size_of = |t: &Targets, g: usize| match g {
949        0..=3 => t.dict[g],
950        4..=9 => t.index[g - 4],
951        10..=18 => t.quad[g - 10],
952        _ => t.text,
953    };
954    let grow = |t: &mut Targets, g: usize| match g {
955        0..=3 => t.dict[g] = t.dict[g].saturating_mul(2),
956        4..=9 => t.index[g - 4] = t.index[g - 4].saturating_mul(2),
957        10..=18 => t.quad[g - 10] = t.quad[g - 10].saturating_mul(2),
958        _ => t.text = t.text.saturating_mul(2),
959    };
960    let build = |t: &Targets| {
961        build_front(
962            parts,
963            t,
964            codec,
965            &dict_off,
966            &perm_off,
967            &quad_off,
968            &quad_gdir,
969            opts.version,
970        )
971    };
972    let mut t = Targets {
973        dict: [pol.start; 4],
974        index: [pol.start; 6],
975        quad: [pol.start; crate::quad7::NUM_SLOTS],
976        text: pol.start,
977    };
978    let mut front = build(&t);
979    let mut root_len = root_len_of(&front);
980    if root_len > pol.root_budget && front.counts.iter().any(|(_, n)| *n > 1) {
981        // The root with one leaf per directory: what no leaf size can go under.
982        let one = usize::MAX / 4;
983        let floor = root_len_of(&build(&Targets {
984            dict: [one; 4],
985            index: [one; 6],
986            quad: [one; crate::quad7::NUM_SLOTS],
987            text: one,
988        }));
989        if floor <= pol.root_budget {
990            while root_len > pol.root_budget {
991                let pick = front
992                    .counts
993                    .iter()
994                    .filter(|(g, n)| *n > 1 && size_of(&t, *g) < pol.max)
995                    .max_by_key(|(_, n)| *n);
996                let Some(&(g, _)) = pick else {
997                    break;
998                };
999                grow(&mut t, g);
1000                front = build(&t);
1001                root_len = root_len_of(&front);
1002            }
1003        }
1004        while root_len > floor + pol.list_cap && front.counts.iter().any(|(_, n)| *n > 1) {
1005            for (g, n) in front.counts.clone() {
1006                if n > 1 {
1007                    grow(&mut t, g);
1008                }
1009            }
1010            front = build(&t);
1011            root_len = root_len_of(&front);
1012        }
1013    }
1014
1015    // Front sections, in file order, with their largest block.
1016    let schema = parts
1017        .schema
1018        .as_ref()
1019        .map(|s| (compress(codec, s), s.len() as u64));
1020    let quad_gdir_max = match &parts.quad {
1021        Some(q) if !quad_gdir.is_empty() => gdir_max(&q.p0, &quad_gdir, parts.block_codec)?,
1022        _ => 0,
1023    };
1024    let mut fronts: Vec<(u8, Vec<u8>, u64)> = Vec::new();
1025    if let Some((s, raw)) = schema {
1026        fronts.push((kind::SCHEMA, s, raw));
1027    }
1028    if !front.dict_leaves.is_empty() {
1029        fronts.push((
1030            kind::DICT_LEAVES,
1031            std::mem::take(&mut front.dict_leaves),
1032            front.leaf_max[0],
1033        ));
1034    }
1035    if !front.index_leaves.is_empty() {
1036        fronts.push((
1037            kind::INDEX_LEAVES,
1038            std::mem::take(&mut front.index_leaves),
1039            front.leaf_max[1],
1040        ));
1041    }
1042    if !front.quad_leaves.is_empty() {
1043        fronts.push((
1044            kind::QUAD_LEAVES,
1045            std::mem::take(&mut front.quad_leaves),
1046            front.leaf_max[2].max(quad_gdir_max),
1047        ));
1048    }
1049    if !label_nodes.is_empty() {
1050        fronts.push((kind::LABEL_LEAVES, label_nodes, 0));
1051    }
1052    if !front.text_leaves.is_empty() {
1053        fronts.push((
1054            kind::TEXT_LEAVES,
1055            std::mem::take(&mut front.text_leaves),
1056            front.leaf_max[3],
1057        ));
1058    }
1059    // The label index's root node: cold, read only by a label search.
1060    if let (Some(l), true) = (&parts.labels, has_v07(opts.version)) {
1061        let pre = crate::label_index::PREAMBLE_LEN;
1062        if l.head.len() > pre {
1063            fronts.push((kind::LABEL_ROOT, l.head[pre..].to_vec(), 0));
1064        }
1065    }
1066    let clamp = |n: u64| n.min(u32::MAX as u64) as u32;
1067
1068    // Card region: card | record | slack.
1069    // A card with a field over the hot cap is split: the field goes to the
1070    // annex, the last data section. A card handed over with its annex (a
1071    // `0x07` source) keeps both as they are.
1072    let (hot_card, annex_raw) = match (&parts.card, &parts.annex) {
1073        (Some(c), None) if !c.is_empty() => {
1074            let s = super::annex::split(c);
1075            (Some(s.hot), s.annex)
1076        }
1077        (c, a) => (c.clone(), a.clone()),
1078    };
1079    let card = hot_card
1080        .as_ref()
1081        .filter(|c| !c.is_empty())
1082        .map(|c| compress(codec, &stamp_card_version(c, opts.version)));
1083    let mut data = data;
1084    if let Some(raw) = annex_raw.as_ref().filter(|a| !a.is_empty()) {
1085        if !has_v07(opts.version) {
1086            return Err(FileError::Container("0x06 has no card annex"));
1087        }
1088        data.push(DataSec {
1089            kind: kind::CARD_ANNEX,
1090            segs: Vec::new(),
1091            measure: None,
1092            known_max: raw.len() as u64,
1093            inline: Some(compress(codec, raw)),
1094        });
1095    }
1096    let build = parts.build.clone().filter(|b| !b.is_empty());
1097    let card_len = card.as_ref().map_or(0, |c| c.len()) as u32;
1098    let build_len = build.as_ref().map_or(0, |b| b.len()) as u32;
1099    let mut region_len = card_region_len(card_len, build_len);
1100
1101    // Section table (digests filled once the data is hashed).
1102    let mut sections = Vec::new();
1103    let mut at = 0u64;
1104    for (k, b, raw) in &fronts {
1105        sections.push(Sec06 {
1106            kind: *k,
1107            max_block: clamp(*raw),
1108            offset: at,
1109            len: b.len() as u64,
1110            digest: digest16(b),
1111        });
1112        at += b.len() as u64;
1113    }
1114    let front_sections_len = at;
1115    let mut at = 0u64;
1116    for d in &data {
1117        sections.push(Sec06 {
1118            kind: d.kind,
1119            max_block: clamp(d.known_max),
1120            offset: at,
1121            len: d.len(),
1122            digest: [0; 16],
1123        });
1124        at += d.len();
1125    }
1126    let data_len = at;
1127    let mut root = Root06 {
1128        sections,
1129        units: front.units,
1130    };
1131    let root_len = root.encode(codec).len() as u32;
1132    // A file is never shorter than the 1 KiB a 0x05-era reader fetches first:
1133    // a tiny one gets the difference as card-region slack.
1134    let total = HEADER_LEN as u64
1135        + root_len as u64
1136        + region_len as u64
1137        + front_sections_len
1138        + data_len
1139        + FOOTER.len() as u64;
1140    if total < MIN_FILE_LEN {
1141        region_len += (MIN_FILE_LEN - total) as u32;
1142    }
1143    let data_offset = HEADER_LEN as u64 + root_len as u64 + region_len as u64 + front_sections_len;
1144
1145    // Data first, at its final offset, hashed per section.
1146    out.seek(SeekFrom::Start(data_offset))?;
1147    let n_front = fronts.len();
1148    let mut written_before = 0u64;
1149    for (i, d) in data.iter().enumerate() {
1150        let mut h = blake3::Hasher::new();
1151        let progress = &mut hooks.progress;
1152        let consumed = &mut hooks.consumed;
1153        let settle = &mut hooks.settle;
1154        let measured = if let Some(b) = &d.inline {
1155            h.update(b);
1156            out.write_all(b)?;
1157            0
1158        } else {
1159            copy_segs(
1160                input,
1161                &d.segs,
1162                d.measure,
1163                out,
1164                &mut h,
1165                &mut |n| progress(written_before + n, data_len),
1166                &mut **consumed,
1167                &mut **settle,
1168            )?
1169        };
1170        written_before += d.len();
1171        (hooks.copied)(d.kind);
1172        (hooks.settle)(out)?;
1173        let sec = &mut root.sections[n_front + i];
1174        sec.digest.copy_from_slice(&h.finalize().as_bytes()[..16]);
1175        if d.measure.is_some() {
1176            sec.max_block = clamp(measured);
1177        }
1178    }
1179    out.write_all(&footer(opts.version))?;
1180    let root_bytes = root.encode(codec);
1181    debug_assert_eq!(root_bytes.len() as u32, root_len);
1182
1183    let mut header = Header06 {
1184        version: opts.version,
1185        flags: (if parts.named { F_NAMED } else { 0 })
1186            | (if parts.quoted { F_QUOTED } else { 0 })
1187            | (if parts.text.as_ref().is_some_and(|t| t.named) {
1188                F_TEXT_NAMED
1189            } else {
1190                0
1191            })
1192            | (if graph_major { F_QUAD_GRAPH_MAJOR } else { 0 })
1193            | (if parts.cluster.is_empty() {
1194                0
1195            } else {
1196                F_CLUSTERED
1197            })
1198            | (if parts.derived.is_empty() {
1199                0
1200            } else {
1201                F_DERIVED
1202            }),
1203        content_hash: [0; 16],
1204        file_len: data_offset + data_len + FOOTER.len() as u64,
1205        root_len,
1206        card_region_len: region_len,
1207        data_offset,
1208        quad_count: parts.quad_count,
1209        term_count: parts.term_count,
1210        graph_count: parts.quad.as_ref().map_or(0, |q| q.graph_count),
1211        perm_mask: parts.perm_mask,
1212        dict_codec: parts.dict_codec,
1213        block_codec: parts.block_codec,
1214        internal_codec: codec,
1215        pyramid_levels: parts.pyramid_levels,
1216        id_widths,
1217        presence: presence_of(parts),
1218        card_off: 0,
1219        card_len,
1220        card_digest: card.as_ref().map_or([0; 16], |c| digest16(c)),
1221        build_off: card_len,
1222        build_len,
1223        root_digest: digest16(&root_bytes),
1224    };
1225    header.content_hash = content_hash(&header);
1226
1227    out.seek(SeekFrom::Start(0))?;
1228    out.write_all(&header.to_bytes())?;
1229    out.write_all(&root_bytes)?;
1230    let mut region = Vec::with_capacity(region_len as usize);
1231    if let Some(c) = &card {
1232        region.extend_from_slice(c);
1233    }
1234    if let Some(b) = &build {
1235        region.extend_from_slice(b);
1236    }
1237    region.resize(region_len as usize, 0);
1238    out.write_all(&region)?;
1239    for (_, b, _) in &fronts {
1240        out.write_all(b)?;
1241    }
1242    out.seek(SeekFrom::Start(header.file_len))?;
1243    out.flush()?;
1244    Ok(Written { header, root })
1245}
1246
1247/// The smallest `0x06` file: 1 KiB, what every reader reads first anyway.
1248pub const MIN_FILE_LEN: u64 = 1024;
1249
1250/// The card region's length for a card and record of these stored lengths.
1251///
1252/// With a card: both, twice over, plus [`CARD_SLACK_MIN`] — so a re-card can
1253/// write the new pair beside the old one and switch with one header write
1254/// (SPEC.md §4.4). With **no card** the region is the record alone: that space
1255/// is in the 64 KiB the open reads first, so slack there would only push the
1256/// leaf directories out of it, and a file nobody carded yet is re-carded by a
1257/// copy. No card and no record: no region.
1258pub fn card_region_len(card_len: u32, build_len: u32) -> u32 {
1259    match (card_len, build_len) {
1260        (0, 0) => 0,
1261        (0, b) => b,
1262        (c, b) => 2 * (c + b) + CARD_SLACK_MIN,
1263    }
1264}
1265
1266fn presence_of(p: &Parts) -> u16 {
1267    let mut x = 0u16;
1268    if let Some(t) = &p.text {
1269        x |= P_TEXT;
1270        if t.partial {
1271            x |= P_TEXT_PARTIAL;
1272        }
1273    }
1274    if p.labels.is_some() {
1275        x |= P_LABELS;
1276    }
1277    if p.schema.is_some() {
1278        x |= P_SCHEMA;
1279    }
1280    if p.pyramid.is_some_and(|r| r.len > 0) {
1281        x |= P_PYRAMID;
1282    }
1283    if p.quad.as_ref().is_some_and(|q| q.graph_count > 0) {
1284        x |= P_QUAD;
1285    }
1286    x
1287}
1288
1289/// A card written into a `0x08` file says `"format_version":8` (`version` is
1290/// the generation of the file it enters; a `0x07` file keeps saying 7). The cards the
1291/// core builders derive stamp the `0x05` layout they were produced for
1292/// (`LEGACY_FORMAT_VERSION`); every card entering a `0x06` file passes here, so
1293/// a build, a converted build and a re-card agree on the stamp. Only the first
1294/// compact `"format_version":N` with N below `version` is rewritten; anything else is
1295/// returned unchanged.
1296pub fn stamp_card_version(card: &[u8], version: u8) -> std::borrow::Cow<'_, [u8]> {
1297    const KEY: &[u8] = b"\"format_version\":";
1298    let Some(at) = card.windows(KEY.len()).position(|w| w == KEY) else {
1299        return std::borrow::Cow::Borrowed(card);
1300    };
1301    let s = at + KEY.len();
1302    let digits = card[s..].iter().take_while(|b| b.is_ascii_digit()).count();
1303    let old = std::str::from_utf8(&card[s..s + digits]).unwrap_or("");
1304    match old.parse::<u8>() {
1305        Ok(v) if v < version => {
1306            let mut out = card[..s].to_vec();
1307            out.extend_from_slice(version.to_string().as_bytes());
1308            out.extend_from_slice(&card[s + digits..]);
1309            std::borrow::Cow::Owned(out)
1310        }
1311        _ => std::borrow::Cow::Borrowed(card),
1312    }
1313}
1314
1315/// Convert a whole `0x05` image held in memory to a `0x06` image.
1316pub fn convert_image(image: &[u8], opts: WriteOpts) -> Result<Vec<u8>, FileError> {
1317    let r = crate::reader::SliceReader::new(image);
1318    let parts = parts::from_v05(&r)?;
1319    let mut out = std::io::Cursor::new(Vec::with_capacity(image.len()));
1320    assemble(&parts, &r, &mut out, opts)?;
1321    Ok(out.into_inner())
1322}
1323
1324/// Convert a `0x05` file read through `input` into `out`.
1325pub fn convert<W: Write + Seek>(
1326    input: &dyn RangeReader,
1327    out: &mut W,
1328    opts: WriteOpts,
1329) -> Result<Written, FileError> {
1330    convert_with_labels(input, None, out, opts)
1331}
1332
1333/// [`convert`], giving the file the LABEL_INDEX section `labels` (its `0x05`
1334/// encoding, from [`label_section`]) when it has none.
1335pub fn convert_with_labels<W: Write + Seek>(
1336    input: &dyn RangeReader,
1337    labels: Option<&[u8]>,
1338    out: &mut W,
1339    opts: WriteOpts,
1340) -> Result<Written, FileError> {
1341    convert_with_record(input, labels, None, out, opts)
1342}
1343
1344/// The source file's build record as stored (raw JSON, possibly padded), or
1345/// `None` when it has none — what [`convert_with_record`] is given to extend.
1346pub fn source_build_record(input: &dyn RangeReader) -> Result<Option<Vec<u8>>, FileError> {
1347    let len = input.len().min(crate::header::HEADER_LEN as u64);
1348    let h = crate::header::Header::from_bytes(&input.read_at(0, len)?)?;
1349    if h.build_info_len == 0 {
1350        return Ok(None);
1351    }
1352    Ok(Some(input.read_at(h.build_info_offset, h.build_info_len)?))
1353}
1354
1355/// [`convert_with_labels`], writing `record` as the build record instead of
1356/// the input's own (`None` keeps the input's, byte for byte). The record is
1357/// outside the content hash.
1358pub fn convert_with_record<W: Write + Seek>(
1359    input: &dyn RangeReader,
1360    labels: Option<&[u8]>,
1361    record: Option<Vec<u8>>,
1362    out: &mut W,
1363    opts: WriteOpts,
1364) -> Result<Written, FileError> {
1365    let mut parts = parts::from_v05(input)?;
1366    if record.is_some() {
1367        parts.build = record;
1368    }
1369    let Some(sec) = labels.filter(|s| !s.is_empty() && parts.labels.is_none()) else {
1370        return assemble(&parts, input, out, opts);
1371    };
1372    // The new section is read through an overlay that places it right after
1373    // the input, so the assembler copies it like any other.
1374    let overlay = Overlay {
1375        base: input,
1376        extra: sec,
1377    };
1378    parts.labels = Some(parts::label_part(
1379        &overlay,
1380        input.len(),
1381        sec.len() as u64,
1382        parts.block_codec,
1383    )?);
1384    assemble(&parts, &overlay, out, opts)
1385}
1386
1387/// `base`, then `extra` past its end.
1388struct Overlay<'a> {
1389    base: &'a dyn RangeReader,
1390    extra: &'a [u8],
1391}
1392
1393impl RangeReader for Overlay<'_> {
1394    fn len(&self) -> u64 {
1395        self.base.len() + self.extra.len() as u64
1396    }
1397
1398    fn read_at(&self, offset: u64, len: u64) -> std::io::Result<Vec<u8>> {
1399        let b = self.base.len();
1400        if offset + len <= b {
1401            return self.base.read_at(offset, len);
1402        }
1403        if offset >= b {
1404            let s = (offset - b) as usize;
1405            return self
1406                .extra
1407                .get(s..s + len as usize)
1408                .map(<[u8]>::to_vec)
1409                .ok_or_else(|| std::io::Error::new(std::io::ErrorKind::UnexpectedEof, "oob"));
1410        }
1411        let mut v = self.base.read_at(offset, b - offset)?;
1412        v.extend_from_slice(self.read_at(b, offset + len - b)?.as_slice());
1413        Ok(v)
1414    }
1415}
1416
1417/// The LABEL_INDEX section (`0x05` encoding) of the default graph of `rete`,
1418/// computed as `rete build --label-index` computes it — from the triples of
1419/// the label predicates only, read through the index. Empty when the graph
1420/// has no label predicate.
1421pub fn label_section(rete: &crate::file::Rete) -> Vec<u8> {
1422    use crate::label_index::{
1423        DIRECT_LABEL_PREDICATES, FAMILY_NAME_PREDICATES, GIVEN_NAME_PREDICATES,
1424    };
1425    let dict = rete.dictionary();
1426    let index = rete.default_index();
1427    let mut triples: Vec<(u32, u32, u32)> = Vec::new();
1428    for list in [
1429        DIRECT_LABEL_PREDICATES,
1430        FAMILY_NAME_PREDICATES,
1431        GIVEN_NAME_PREDICATES,
1432    ] {
1433        for p in list {
1434            if let Some(pid) = dict.predicate_id(p) {
1435                triples.extend(index.scan_iter((None, Some(pid), None)));
1436            }
1437        }
1438    }
1439    triples.sort_unstable();
1440    triples.dedup();
1441    let entries = crate::label_index::entries_from_sorted_triples(dict, &triples);
1442    if entries.is_empty() {
1443        return Vec::new();
1444    }
1445    crate::label_index::encode_section(&entries, crate::file::writer_codec())
1446}
1447
1448/// The card a re-card writes.
1449#[derive(Debug, Clone, Copy)]
1450pub enum NewCard<'a> {
1451    /// The file's own card, byte for byte (only the build record changes, so
1452    /// the content hash does not).
1453    Keep,
1454    /// This card (JSON), or none. A field over the hot cap moves to the annex
1455    /// ([`super::annex::split`]); the full card goes in, the hot one is stored.
1456    Set(Option<&'a [u8]>),
1457}
1458
1459/// A card change, resolved: what is stored in the card region and what happens
1460/// to the annex (the last data section).
1461struct CardPlan {
1462    /// The hot card, stored (compressed); `None` = no card.
1463    stored: Option<Vec<u8>>,
1464    /// The root block to write: the old one unless the annex changes (its
1465    /// section-table entry then does, and with it the root digest).
1466    root_bytes: Vec<u8>,
1467    /// The annex changes: `(offset where the old tail starts, new stored annex
1468    /// or empty for none)`. The data region is copied only up to the offset;
1469    /// the new annex and the footer follow.
1470    tail: Option<(u64, Vec<u8>)>,
1471}
1472
1473/// Resolve `card` against the file `h` with root block `root_bytes`.
1474/// `old_card` is the file's stored card (for [`NewCard::Keep`]).
1475fn plan_card(
1476    h: &Header06,
1477    root_bytes: &[u8],
1478    card: NewCard<'_>,
1479    old_card: Option<Vec<u8>>,
1480) -> Result<CardPlan, FileError> {
1481    let codec = h.internal_codec;
1482    let keep = |stored: Option<Vec<u8>>| CardPlan {
1483        stored,
1484        root_bytes: root_bytes.to_vec(),
1485        tail: None,
1486    };
1487    let c = match card {
1488        NewCard::Keep => return Ok(keep(old_card)),
1489        NewCard::Set(c) => c.filter(|c| !c.is_empty()),
1490    };
1491    let (hot, annex_raw) = match c {
1492        Some(c) => {
1493            let s = annex::split(c);
1494            (Some(s.hot), s.annex)
1495        }
1496        None => (None, None),
1497    };
1498    let stored = hot.map(|c| compress(codec, &stamp_card_version(&c, h.version)));
1499    let root = Root06::decode(root_bytes, codec)?;
1500    let old = root.section(kind::CARD_ANNEX).copied();
1501    let new_stored = annex_raw.as_ref().map(|a| compress(codec, a));
1502    let same = match (&old, &new_stored) {
1503        (None, None) => true,
1504        (Some(o), Some(n)) => o.len == n.len() as u64 && o.digest == digest16(n),
1505        _ => false,
1506    };
1507    if same {
1508        return Ok(keep(stored));
1509    }
1510    if h.version == VERSION_06 && new_stored.is_some() {
1511        return Err(FileError::Container(
1512            "this card has fields over the hot-card cap, which need a card annex; \
1513             a 0x06 file has none: run `rete convert` to 0x07 first, or trim the card",
1514        ));
1515    }
1516    let end = h.file_len - FOOTER.len() as u64;
1517    let cut = match &old {
1518        Some(o) => {
1519            let a = o.abs(h)?;
1520            if a.offset + a.len != end {
1521                return Err(FileError::Container(
1522                    "0x07 card annex is not the last section",
1523                ));
1524            }
1525            a.offset
1526        }
1527        None => end,
1528    };
1529    let mut nr = root.clone();
1530    nr.sections.retain(|s| s.kind != kind::CARD_ANNEX);
1531    if let (Some(n), Some(raw)) = (&new_stored, &annex_raw) {
1532        nr.sections.push(Sec06 {
1533            kind: kind::CARD_ANNEX,
1534            max_block: raw.len().min(u32::MAX as usize) as u32,
1535            offset: cut - h.data_offset,
1536            len: n.len() as u64,
1537            digest: digest16(n),
1538        });
1539    }
1540    Ok(CardPlan {
1541        stored,
1542        root_bytes: nr.encode(codec),
1543        tail: Some((cut, new_stored.unwrap_or_default())),
1544    })
1545}
1546
1547/// The bytes after the copied part of the data region when the annex changes:
1548/// the new annex, then the footer.
1549fn tail_bytes(h: &Header06, annex: &[u8]) -> Vec<u8> {
1550    let mut v = annex.to_vec();
1551    v.extend_from_slice(&footer(h.version));
1552    v
1553}
1554
1555/// Replace the card (and the build record) of a `0x06`/`0x07` image held in
1556/// memory: the front is re-laid out with the new card region; every section is
1557/// copied byte for byte (a changed card annex replaces the last section). The
1558/// content hash follows the card.
1559pub fn replace_card(
1560    image: &[u8],
1561    card: Option<&[u8]>,
1562    build: Option<&[u8]>,
1563) -> Result<Vec<u8>, FileError> {
1564    replace_card_with(image, NewCard::Set(card), build)
1565}
1566
1567/// [`replace_card`] with the card given as a [`NewCard`]: `Keep` leaves the
1568/// file's own card (and its annex) as they are, so only the record changes.
1569pub fn replace_card_with(
1570    image: &[u8],
1571    card: NewCard<'_>,
1572    build: Option<&[u8]>,
1573) -> Result<Vec<u8>, FileError> {
1574    let h = Header06::from_bytes(image)?;
1575    let front = image
1576        .get(..h.data_offset as usize)
1577        .ok_or(FileError::Container("0x06 front overruns"))?;
1578    let root_bytes = front
1579        .get(HEADER_LEN..HEADER_LEN + h.root_len as usize)
1580        .ok_or(FileError::Container("0x06 root overruns"))?;
1581    let r = h.card_range();
1582    let old = (r.len > 0)
1583        .then(|| front.get(r.offset as usize..(r.offset + r.len) as usize))
1584        .flatten()
1585        .map(<[u8]>::to_vec);
1586    let plan = plan_card(&h, root_bytes, card, old)?;
1587    let end = plan.tail.as_ref().map_or(h.file_len, |t| t.0);
1588    let mut rest = image
1589        .get(h.data_offset as usize..end as usize)
1590        .ok_or(FileError::Container("0x06 data overruns"))?
1591        .to_vec();
1592    if let Some((_, a)) = &plan.tail {
1593        rest.extend_from_slice(&tail_bytes(&h, a));
1594    }
1595    let (_, mut out) = recard_front(
1596        &h,
1597        front,
1598        &plan.root_bytes,
1599        plan.stored.as_deref(),
1600        build,
1601        rest.len() as u64,
1602    )?;
1603    out.extend_from_slice(&rest);
1604    Ok(out)
1605}
1606
1607/// The header and front (everything before the data region) of `h`'s file
1608/// with a new card and build record: the card region re-laid out (no slack
1609/// reuse: a fresh region sized for the new pair), the root block as given
1610/// (`root_bytes`), the front sections copied, the data region (`new_data_len`
1611/// bytes) shifted by the front's change.
1612fn recard_front(
1613    h: &Header06,
1614    front: &[u8],
1615    root_bytes: &[u8],
1616    card_stored: Option<&[u8]>,
1617    build: Option<&[u8]>,
1618    new_data_len: u64,
1619) -> Result<(Header06, Vec<u8>), FileError> {
1620    let sections = front
1621        .get(h.front_base() as usize..h.data_offset as usize)
1622        .ok_or(FileError::Container("0x06 front overruns"))?;
1623    let card_len = card_stored.map_or(0, |c| c.len()) as u32;
1624    let build_len = build.map_or(0, |b| b.len()) as u32;
1625    let mut region_len = card_region_len(card_len, build_len);
1626    let total = HEADER_LEN as u64
1627        + root_bytes.len() as u64
1628        + region_len as u64
1629        + sections.len() as u64
1630        + new_data_len;
1631    if total < MIN_FILE_LEN {
1632        region_len += (MIN_FILE_LEN - total) as u32;
1633    }
1634    let mut nh = h.clone();
1635    nh.root_len = root_bytes.len() as u32;
1636    nh.root_digest = digest16(root_bytes);
1637    nh.card_region_len = region_len;
1638    nh.card_off = 0;
1639    nh.card_len = card_len;
1640    nh.card_digest = card_stored.map_or([0; 16], digest16);
1641    nh.build_off = card_len;
1642    nh.build_len = build_len;
1643    nh.data_offset =
1644        HEADER_LEN as u64 + root_bytes.len() as u64 + region_len as u64 + sections.len() as u64;
1645    nh.file_len = nh.data_offset + new_data_len;
1646    nh.content_hash = content_hash(&nh);
1647    let mut out = Vec::with_capacity(nh.data_offset as usize);
1648    out.extend_from_slice(&nh.to_bytes());
1649    out.extend_from_slice(root_bytes);
1650    let mut region = Vec::with_capacity(region_len as usize);
1651    if let Some(c) = card_stored {
1652        region.extend_from_slice(c);
1653    }
1654    if let Some(b) = build {
1655        region.extend_from_slice(b);
1656    }
1657    region.resize(region_len as usize, 0);
1658    out.extend_from_slice(&region);
1659    out.extend_from_slice(sections);
1660    Ok((nh, out))
1661}
1662
1663/// Rewrite a `0x06`/`0x07` file read through `src` into `out` with a new card
1664/// and build record: [`replace_card`] without holding the file. The front is
1665/// re-laid out around the new card region and the data region copied byte for
1666/// byte (its digests unchanged); a changed card annex replaces the file's last
1667/// section, and the root with it. `progress` receives the data bytes copied so
1668/// far.
1669pub fn rewrite_card_stream<W: Write>(
1670    src: &dyn RangeReader,
1671    out: &mut W,
1672    card: NewCard<'_>,
1673    build: Option<&[u8]>,
1674    progress: &mut dyn FnMut(u64),
1675) -> Result<Header06, FileError> {
1676    const SPAN: u64 = 8 << 20;
1677    let head = src.read_at(0, HEADER_LEN as u64)?;
1678    let h = Header06::from_bytes(&head)?;
1679    if h.file_len != src.len() {
1680        return Err(FileError::Container(
1681            "0x06 file length does not match its header",
1682        ));
1683    }
1684    // Everything before the data region is small: the header, the root, the
1685    // card region and the front sections.
1686    let front = src.read_at(0, h.data_offset)?;
1687    let root_bytes = front
1688        .get(HEADER_LEN..HEADER_LEN + h.root_len as usize)
1689        .ok_or(FileError::Container("0x06 root overruns"))?;
1690    let r = h.card_range();
1691    let old = (r.len > 0).then(|| front[r.offset as usize..(r.offset + r.len) as usize].to_vec());
1692    let plan = plan_card(&h, root_bytes, card, old)?;
1693    let end = plan.tail.as_ref().map_or(h.file_len, |t| t.0);
1694    let tail = plan.tail.as_ref().map(|(_, a)| tail_bytes(&h, a));
1695    let new_data_len = end - h.data_offset + tail.as_ref().map_or(0, |t| t.len() as u64);
1696    let (nh, new_front) = recard_front(
1697        &h,
1698        &front,
1699        &plan.root_bytes,
1700        plan.stored.as_deref(),
1701        build,
1702        new_data_len,
1703    )?;
1704    out.write_all(&new_front)?;
1705    let mut at = h.data_offset;
1706    while at < end {
1707        let n = (end - at).min(SPAN);
1708        out.write_all(&src.read_at(at, n)?)?;
1709        at += n;
1710        progress(at - h.data_offset);
1711    }
1712    if let Some(t) = tail {
1713        out.write_all(&t)?;
1714    }
1715    out.flush()?;
1716    Ok(nh)
1717}
1718
1719/// Re-card a `0x06` file **in place**, when the new card and record fit in a
1720/// free gap of its card region (beside the old pair, which stays readable until
1721/// the switch): they are written there and the new header is returned, *not*
1722/// written. The caller syncs the file, then [`commit_header`] — the 128-byte
1723/// header is the one commit point, so a crash before it leaves the old file
1724/// whole. A card equal to the current one stays where it is (only the record
1725/// moves; the content hash does not change). `Ok(None)` when the pair does not
1726/// fit: the caller copies instead ([`rewrite_card_stream`]).
1727pub fn recard_in_place<F: std::io::Read + Write + Seek>(
1728    file: &mut F,
1729    card: NewCard<'_>,
1730    build: Option<&[u8]>,
1731) -> Result<Option<Header06>, FileError> {
1732    let mut head = vec![0u8; HEADER_LEN];
1733    file.seek(SeekFrom::Start(0))?;
1734    file.read_exact(&mut head)?;
1735    let h = Header06::from_bytes(&head)?;
1736    // A changed annex is the file's last section and its root entry: that is a
1737    // copy, not an in-place write (the header is the one commit point).
1738    let mut root_bytes = vec![0u8; h.root_len as usize];
1739    file.read_exact(&mut root_bytes)?;
1740    let plan = plan_card(&h, &root_bytes, card, None)?;
1741    if plan.tail.is_some() {
1742        return Ok(None);
1743    }
1744    let card_stored = match card {
1745        NewCard::Keep => None,
1746        NewCard::Set(_) => plan.stored,
1747    };
1748    let keep_card = match (card, &card_stored) {
1749        (NewCard::Keep, _) => true,
1750        (_, Some(c)) => c.len() as u32 == h.card_len && digest16(c) == h.card_digest,
1751        (_, None) => h.card_len == 0,
1752    };
1753    let card_need = if keep_card {
1754        0
1755    } else {
1756        card_stored.as_ref().map_or(0, |c| c.len()) as u64
1757    };
1758    let build_need = build.map_or(0, |b| b.len()) as u64;
1759    let need = card_need + build_need;
1760    // The free gaps of the region around the pair in use.
1761    let mut used: Vec<(u64, u64)> = [
1762        (h.card_off as u64, h.card_len as u64),
1763        (h.build_off as u64, h.build_len as u64),
1764    ]
1765    .into_iter()
1766    .filter(|&(_, l)| l > 0)
1767    .collect();
1768    used.sort_unstable();
1769    let region = h.card_region_len as u64;
1770    let mut gaps = Vec::new();
1771    let mut at = 0u64;
1772    for (o, l) in used {
1773        if o > at {
1774            gaps.push((at, o - at));
1775        }
1776        at = at.max(o + l);
1777    }
1778    if region > at {
1779        gaps.push((at, region - at));
1780    }
1781    let start = if need == 0 {
1782        0
1783    } else {
1784        match gaps.iter().find(|&&(_, l)| l >= need) {
1785            Some(&(o, _)) => o,
1786            None => return Ok(None),
1787        }
1788    };
1789    file.seek(SeekFrom::Start(h.card_region_offset() + start))?;
1790    if !keep_card {
1791        if let Some(c) = &card_stored {
1792            file.write_all(c)?;
1793        }
1794    }
1795    if let Some(b) = build {
1796        file.write_all(b)?;
1797    }
1798    file.flush()?;
1799    let mut nh = h.clone();
1800    if !keep_card {
1801        nh.card_off = if card_need > 0 { start as u32 } else { 0 };
1802        nh.card_len = card_need as u32;
1803        nh.card_digest = card_stored.as_ref().map_or([0; 16], |c| digest16(c));
1804    }
1805    nh.build_off = if build_need > 0 {
1806        (start + card_need) as u32
1807    } else {
1808        0
1809    };
1810    nh.build_len = build_need as u32;
1811    nh.content_hash = content_hash(&nh);
1812    Ok(Some(nh))
1813}
1814
1815/// Write `h` over the first 128 bytes (the commit of [`recard_in_place`]).
1816pub fn commit_header<F: Write + Seek>(file: &mut F, h: &Header06) -> Result<(), FileError> {
1817    file.seek(SeekFrom::Start(0))?;
1818    file.write_all(&h.to_bytes())?;
1819    file.flush()?;
1820    Ok(())
1821}
1822
1823/// Write the `0x06` file `input` again under the writer's current leaf policy:
1824/// the payload is copied verbatim and only the directory leaves, the root and
1825/// the section table change. `opts.quad` keeps the input's own clustering when
1826/// it is `Auto`.
1827pub fn rewrite<W: Write + Seek>(
1828    input: &dyn RangeReader,
1829    out: &mut W,
1830    mut opts: WriteOpts,
1831) -> Result<Written, FileError> {
1832    let parts = parts::from_v06(input)?;
1833    if opts.quad == QuadClustering::Auto {
1834        let head = input.read_at(0, HEADER_LEN as u64)?;
1835        let h = Header06::from_bytes(&head)?;
1836        opts.quad = if h.flags & F_QUAD_GRAPH_MAJOR != 0 {
1837            QuadClustering::GraphMajor
1838        } else {
1839            QuadClustering::OrderMajor
1840        };
1841    }
1842    assemble(&parts, input, out, opts)
1843}
1844
1845#[cfg(test)]
1846mod stamp_tests {
1847    use super::stamp_card_version;
1848
1849    #[test]
1850    fn stamps_older_versions_only() {
1851        let s = |b: &[u8]| stamp_card_version(b, 8).into_owned();
1852        assert_eq!(
1853            s(br#"{"a":1,"format_version":5}"#),
1854            br#"{"a":1,"format_version":8}"#
1855        );
1856        assert_eq!(
1857            s(br#"{"format_version":5,"z":2}"#),
1858            br#"{"format_version":8,"z":2}"#
1859        );
1860        assert_eq!(s(br#"{"format_version":6}"#), br#"{"format_version":8}"#);
1861        assert_eq!(s(br#"{"format_version":7}"#), br#"{"format_version":8}"#);
1862        assert_eq!(s(br#"{"format_version":8}"#), br#"{"format_version":8}"#);
1863        assert_eq!(s(br#"{"format_version":9}"#), br#"{"format_version":9}"#);
1864        assert_eq!(s(br#"{"title":"x"}"#), br#"{"title":"x"}"#);
1865        // a 0x07 file keeps saying 7
1866        assert_eq!(
1867            stamp_card_version(br#"{"format_version":5}"#, 7).as_ref(),
1868            br#"{"format_version":7}"#
1869        );
1870        assert_eq!(
1871            stamp_card_version(br#"{"format_version":7}"#, 7).as_ref(),
1872            br#"{"format_version":7}"#
1873        );
1874    }
1875}