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