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