urna_format/encoding/
dedup.rs

1//! content-hash dedup of canonical texts BEFORE zstd (the dedup-map
2//! optional section, id 0x0B). a build-time pass over the DECOMPRESSED
3//! canonical texts (the load-bearing nix/ipfs order rule: dedup on
4//! decompressed bytes, compress the unique pool AFTERWARD) collapses
5//! repeated chunks to one stored copy plus a u32 back-reference per chunk.
6//!
7//! the unique pool is stored in `chunks_canonical` (0x02) under whatever
8//! text codec wins (raw / zstd / dict / fsst); the back-reference array
9//! lives in `SECTION_DEDUP_MAP` (0x0B), excluded from `content_hash`, so it
10//! never moves a `urna://` citation. [`expand`] re-expands the unique pool
11//! through the back-references to the EXACT original canonical byte stream
12//! before `content_hash` sees it, so a deduped file and its non-deduped twin
13//! share the same `content_hash`.
14//!
15//! draws from nixos/nix store-optimise (content-hash equality dedup, ~25-35%
16//! on redundant corpora before any entropy coder) and ipfs/kubo block-level
17//! dedup (identical content collapses to one stored block); the "dedup on
18//! decompressed bytes, compress afterward" invariant is the nix-casync/tvix
19//! lesson encoded as a guardrail.
20
21use super::intpack::{IntpackReader, pack_u64s};
22use crate::error::UrnaError;
23use crate::layout::SECTION_DEDUP_MAP;
24use std::collections::HashMap;
25
26/// dedup-map payload version byte (leads the back-reference array).
27pub const DEDUP_MAP_V1: u8 = 0;
28
29fn malformed(reason: impl Into<String>) -> UrnaError {
30    UrnaError::MalformedSectionPayload {
31        section_id: SECTION_DEDUP_MAP,
32        reason: reason.into(),
33    }
34}
35
36/// the result of a dedup pass: the first-seen unique texts (in first-seen
37/// order, deterministic) and a per-chunk back-reference into that pool.
38pub struct Deduped {
39    pub unique: Vec<String>,
40    pub back_refs: Vec<u32>,
41}
42
43/// run the first-seen dedup pass over `texts` (the decompressed canonical
44/// strings, in chunk order). deterministic: a `HashMap` keyed by the text
45/// only decides membership, while first-seen ORDER is driven by the input
46/// sequence, so two builds over the same corpus match exactly.
47pub fn dedup(texts: &[String]) -> Deduped {
48    let mut index: HashMap<&str, u32> = HashMap::with_capacity(texts.len());
49    let mut unique: Vec<String> = Vec::new();
50    let mut back_refs: Vec<u32> = Vec::with_capacity(texts.len());
51    for t in texts {
52        match index.get(t.as_str()) {
53            Some(&i) => back_refs.push(i),
54            None => {
55                let i = unique.len() as u32;
56                index.insert(t.as_str(), i);
57                unique.push(t.clone());
58                back_refs.push(i);
59            }
60        }
61    }
62    Deduped { unique, back_refs }
63}
64
65/// serialize the back-reference array: a version byte then an intpack
66/// (encoding-id-4 primitive, reused) packing of the u32 refs as u64. a pure
67/// function of the refs, so two builds are byte-identical.
68pub fn encode_map(back_refs: &[u32]) -> Vec<u8> {
69    let as_u64: Vec<u64> = back_refs.iter().map(|&r| r as u64).collect();
70    let packed = pack_u64s(&as_u64);
71    let mut out = Vec::with_capacity(1 + packed.len());
72    out.push(DEDUP_MAP_V1);
73    out.extend_from_slice(&packed);
74    out
75}
76
77/// parse a dedup-map payload back to the back-reference array, bounds-checked.
78pub fn decode_map(bytes: &[u8]) -> crate::Result<Vec<u32>> {
79    let (kind, rest) = bytes
80        .split_first()
81        .ok_or_else(|| malformed("dedup_map: empty"))?;
82    if *kind != DEDUP_MAP_V1 {
83        return Err(malformed(format!("dedup_map: unknown kind {}", *kind)));
84    }
85    let reader = IntpackReader::parse(rest)?;
86    let mut refs = Vec::with_capacity(reader.len().min(1 << 20));
87    for i in 0..reader.len() {
88        let v = reader.get(i)?;
89        let r = u32::try_from(v).map_err(|_| malformed("dedup_map: back-ref exceeds u32"))?;
90        refs.push(r);
91    }
92    Ok(refs)
93}
94
95/// re-expand the unique pool through the back-references to the full ordered
96/// list of canonical texts, byte-identical to the original. every ref must
97/// index a real unique entry; a hostile map errors, never panics.
98pub fn expand(unique: &[String], back_refs: &[u32]) -> crate::Result<Vec<String>> {
99    let mut out = Vec::with_capacity(back_refs.len());
100    for &r in back_refs {
101        let s = unique
102            .get(r as usize)
103            .ok_or_else(|| malformed("dedup_map: back-ref out of unique-pool range"))?;
104        out.push(s.clone());
105    }
106    Ok(out)
107}
108
109#[cfg(test)]
110mod tests {
111    use super::*;
112
113    fn texts(items: &[&str]) -> Vec<String> {
114        items.iter().map(|s| s.to_string()).collect()
115    }
116
117    #[test]
118    fn dedup_then_expand_roundtrips() {
119        for corpus in [
120            texts(&[]),
121            texts(&["a", "b", "c"]),                // all unique
122            texts(&["x", "x", "x", "x"]),           // all duplicate
123            texts(&["a", "b", "a", "c", "b", "a"]), // mixed
124        ] {
125            let d = dedup(&corpus);
126            let back = expand(&d.unique, &d.back_refs).unwrap();
127            assert_eq!(back, corpus, "expand must rebuild the original order");
128            // the map round-trips through its serialized form too.
129            let blob = encode_map(&d.back_refs);
130            assert_eq!(decode_map(&blob).unwrap(), d.back_refs);
131        }
132    }
133
134    #[test]
135    fn all_duplicate_collapses_to_one() {
136        let d = dedup(&texts(&["same", "same", "same"]));
137        assert_eq!(d.unique.len(), 1);
138        assert_eq!(d.back_refs, vec![0, 0, 0]);
139    }
140
141    #[test]
142    fn determinism_two_passes_identical() {
143        let corpus = texts(&["p", "q", "p", "r", "q"]);
144        let a = dedup(&corpus);
145        let b = dedup(&corpus);
146        assert_eq!(a.unique, b.unique);
147        assert_eq!(a.back_refs, b.back_refs);
148        assert_eq!(encode_map(&a.back_refs), encode_map(&b.back_refs));
149    }
150}
urna_format/encoding/dedup.rs

urna_format/encoding/
dedup.rs
