tokenfold_core/transforms/
json_dict.rs

1//! `json_value_dict` transform (canonical id `"json_value_dict"`, v1.0.0).
2//!
3//! Content-aware, **losslessly reversible** value deduplication for generic JSON data.
4//! Where `json_field_fold` factors out repeated *keys*, this factors out repeated *values*:
5//! the same large object/array/string appearing many times (a constant nested record, a
6//! repeated timestamp, an identical config blob) is stored once in a dictionary and every
7//! occurrence is replaced by a compact reference.
8//!
9//! ```text
10//! {"a":{"x":1,"y":2,"z":3},"b":{"x":1,"y":2,"z":3}}
11//!   -> {"__tf_dict__":[{"x":1,"y":2,"z":3}],
12//!       "__tf_data__":{"a":{"__tf_ref__":0},"b":{"__tf_ref__":0}}}
13//! ```
14//!
15//! It runs *after* `json_field_fold` in the pipeline, so it also collapses the repeated
16//! nested values that folding surfaces across rows. Only values whose serialized form is
17//! large enough that a reference is cheaper are dictionaried (see `MIN_VALUE_BYTES`), and the
18//! pipeline's exact-token gate drops the whole transform if it fails to net a saving — so it
19//! can never make a payload worse. Reversibility is guaranteed by `round_trips` (the pipeline
20//! safety gate): a fold that wouldn't restore exactly is rolled back.
21
22use std::collections::HashMap;
23
24use serde_json::{Map, Value};
25
26/// Canonical transform id, as registered with the pipeline.
27pub const TRANSFORM_ID: &str = "json_value_dict";
28
29/// Semantic version of this transform's output behavior.
30pub const TRANSFORM_VERSION: &str = "1.0.0";
31
32const DICT: &str = "__tf_dict__";
33const DATA: &str = "__tf_data__";
34const REF: &str = "__tf_ref__";
35
36/// Minimum serialized byte length for a value to be worth dictionarying. A reference is
37/// `{"__tf_ref__":N}` (~16 bytes), so shorter values would only grow; the exact-token gate is
38/// the final arbiter, this is just a cheap pre-filter that keeps the transform net-positive.
39const MIN_VALUE_BYTES: usize = 24;
40
41/// A value must repeat at least this many times to be dictionaried.
42const MIN_COUNT: usize = 2;
43
44#[derive(Debug, thiserror::Error)]
45pub enum JsonDictError {
46    #[error("invalid json: {0}")]
47    Invalid(#[from] serde_json::Error),
48}
49
50/// Replaces repeated large values in `input` with dictionary references. No-op-safe: empty
51/// input returns empty; input with nothing worth dictionarying returns unchanged.
52pub fn dict_json(input: &[u8]) -> Result<Vec<u8>, JsonDictError> {
53    if input.is_empty() {
54        return Ok(Vec::new());
55    }
56    let value: Value = serde_json::from_slice(input)?;
57
58    let mut counts: HashMap<String, usize> = HashMap::new();
59    count_dictable(&value, &mut counts);
60
61    let mut index: Vec<String> = Vec::new();
62    let mut index_of: HashMap<String, usize> = HashMap::new();
63    let data = replace(&value, &counts, &mut index, &mut index_of);
64
65    if index.is_empty() {
66        return Ok(input.to_vec());
67    }
68    let dict: Vec<Value> = index
69        .iter()
70        .map(|s| serde_json::from_str(s).expect("canonical string from our own to_string"))
71        .collect();
72    let mut wrapper = Map::new();
73    wrapper.insert(DICT.to_string(), Value::Array(dict));
74    wrapper.insert(DATA.to_string(), data);
75    Ok(serde_json::to_vec(&Value::Object(wrapper))?)
76}
77
78/// Inverse of [`dict_json`]: expands every `{__tf_ref__: i}` back to `dict[i]`.
79pub fn undict_json(input: &[u8]) -> Result<Vec<u8>, JsonDictError> {
80    if input.is_empty() {
81        return Ok(Vec::new());
82    }
83    let value: Value = serde_json::from_slice(input)?;
84    let restored = restore(&value);
85    Ok(serde_json::to_vec(&restored)?)
86}
87
88/// True iff expanding `after` reproduces `before` exactly (as JSON values) — the pipeline's
89/// safety gate for this transform.
90pub fn round_trips(before: &[u8], after: &[u8]) -> bool {
91    let (Ok(before_v), Ok(after_v)) = (
92        serde_json::from_slice::<Value>(before),
93        serde_json::from_slice::<Value>(after),
94    ) else {
95        return false;
96    };
97    restore(&after_v) == before_v
98}
99
100/// Canonical dictionary key for a value, or `None` if it isn't a dictionary candidate
101/// (too small, or a scalar that a reference couldn't beat).
102fn dict_key(v: &Value) -> Option<String> {
103    if !matches!(v, Value::Object(_) | Value::Array(_) | Value::String(_)) {
104        return None;
105    }
106    let key = serde_json::to_string(v).ok()?;
107    (key.len() >= MIN_VALUE_BYTES).then_some(key)
108}
109
110fn count_dictable(v: &Value, counts: &mut HashMap<String, usize>) {
111    if let Some(k) = dict_key(v) {
112        *counts.entry(k).or_insert(0) += 1;
113    }
114    match v {
115        Value::Object(m) => m.values().for_each(|val| count_dictable(val, counts)),
116        Value::Array(a) => a.iter().for_each(|item| count_dictable(item, counts)),
117        _ => {}
118    }
119}
120
121/// Top-down replacement: the outermost repeated value at any position becomes a reference and
122/// is not descended into (so a repeated parent object swallows its children rather than
123/// leaving dead dictionary entries). Indices are assigned lazily, so only referenced values
124/// end up in the dictionary.
125fn replace(
126    v: &Value,
127    counts: &HashMap<String, usize>,
128    index: &mut Vec<String>,
129    index_of: &mut HashMap<String, usize>,
130) -> Value {
131    if let Some(k) = dict_key(v)
132        && counts.get(&k).copied().unwrap_or(0) >= MIN_COUNT
133    {
134        let idx = *index_of.entry(k.clone()).or_insert_with(|| {
135            index.push(k);
136            index.len() - 1
137        });
138        let mut r = Map::new();
139        r.insert(REF.to_string(), Value::from(idx as u64));
140        return Value::Object(r);
141    }
142    match v {
143        Value::Object(m) => {
144            let mut o = Map::new();
145            for (kk, val) in m {
146                o.insert(kk.clone(), replace(val, counts, index, index_of));
147            }
148            Value::Object(o)
149        }
150        Value::Array(a) => Value::Array(a.iter().map(|it| replace(it, counts, index, index_of)).collect()),
151        _ => v.clone(),
152    }
153}
154
155/// Expands a whole document: if it's our `{__tf_dict__, __tf_data__}` wrapper, resolve every
156/// reference in the data against the dictionary; otherwise return it unchanged.
157fn restore(v: &Value) -> Value {
158    let Some((dict, data)) = as_wrapper(v) else {
159        return v.clone();
160    };
161    expand(data, dict)
162}
163
164fn as_wrapper(v: &Value) -> Option<(&Vec<Value>, &Value)> {
165    let m = v.as_object()?;
166    if m.len() != 2 {
167        return None;
168    }
169    let dict = m.get(DICT)?.as_array()?;
170    let data = m.get(DATA)?;
171    Some((dict, data))
172}
173
174fn expand(v: &Value, dict: &[Value]) -> Value {
175    if let Some(idx) = as_ref(v) {
176        // Dictionary entries are stored ref-free, so this resolves in one step; out-of-range
177        // indices are left as-is (the round-trip gate then rejects the fold).
178        return dict.get(idx).cloned().unwrap_or_else(|| v.clone());
179    }
180    match v {
181        Value::Object(m) => {
182            let mut o = Map::new();
183            for (k, val) in m {
184                o.insert(k.clone(), expand(val, dict));
185            }
186            Value::Object(o)
187        }
188        Value::Array(a) => Value::Array(a.iter().map(|it| expand(it, dict)).collect()),
189        _ => v.clone(),
190    }
191}
192
193fn as_ref(v: &Value) -> Option<usize> {
194    let m = v.as_object()?;
195    if m.len() != 1 {
196        return None;
197    }
198    Some(m.get(REF)?.as_u64()? as usize)
199}
200
201#[cfg(test)]
202mod tests {
203    use super::*;
204
205    fn parse(b: &[u8]) -> Value {
206        serde_json::from_slice(b).unwrap()
207    }
208
209    #[test]
210    fn dedups_a_repeated_large_object() {
211        let obj = r#"{"kind":"widget","color":"blue","size":"large"}"#;
212        let input = format!(r#"{{"a":{obj},"b":{obj},"c":{obj}}}"#);
213        let out = dict_json(input.as_bytes()).unwrap();
214        let s = String::from_utf8(out.clone()).unwrap();
215        assert!(s.contains("__tf_dict__"), "expected dict form, got {s}");
216        // the object literal appears once (in the dict), not three times
217        assert_eq!(s.matches("widget").count(), 1);
218        assert!(round_trips(input.as_bytes(), &out));
219    }
220
221    #[test]
222    fn dict_then_undict_reproduces_original() {
223        let obj = r#"{"kind":"widget","color":"blue","size":"large"}"#;
224        let input = format!(r#"[{obj},{obj},{obj},{obj}]"#);
225        let folded = dict_json(input.as_bytes()).unwrap();
226        let back = undict_json(&folded).unwrap();
227        assert_eq!(parse(&back), parse(input.as_bytes()));
228    }
229
230    #[test]
231    fn short_repeated_values_are_left_alone() {
232        // "member" is short; a reference would be longer, so it must NOT be dictionaried.
233        let input = br#"{"a":"member","b":"member","c":"member"}"#;
234        let out = dict_json(input).unwrap();
235        assert_eq!(parse(&out), parse(input));
236        assert!(!String::from_utf8(out).unwrap().contains("__tf_dict__"));
237    }
238
239    #[test]
240    fn single_occurrence_is_not_dictionaried() {
241        let input = br#"{"only":{"a":"quite a long value here indeed yes"}}"#;
242        let out = dict_json(input).unwrap();
243        assert!(!String::from_utf8(out).unwrap().contains("__tf_dict__"));
244    }
245
246    #[test]
247    fn nested_repeats_do_not_create_dead_entries() {
248        let inner = r#"{"deeply":"nested repeated value that is long"}"#;
249        let parent = format!(r#"{{"p":{inner},"q":"x"}}"#);
250        let input = format!(r#"[{parent},{parent}]"#);
251        let out = dict_json(input.as_bytes()).unwrap();
252        assert!(round_trips(input.as_bytes(), &out));
253    }
254
255    #[test]
256    fn empty_and_invalid_inputs() {
257        assert!(dict_json(b"").unwrap().is_empty());
258        assert!(dict_json(b"{bad").is_err());
259    }
260
261    use proptest::prelude::*;
262
263    fn arb_json() -> impl Strategy<Value = Value> {
264        let leaf = prop_oneof![
265            Just(Value::Null),
266            any::<bool>().prop_map(Value::Bool),
267            any::<i64>().prop_map(|n| Value::Number(n.into())),
268            "[^\"\\\\]{0,20}".prop_map(Value::String),
269        ];
270        leaf.prop_recursive(4, 48, 6, |inner| {
271            prop_oneof![
272                prop::collection::vec(inner.clone(), 0..6).prop_map(Value::Array),
273                prop::collection::hash_map("[a-z]{1,6}", inner, 0..6)
274                    .prop_map(|m| Value::Object(m.into_iter().collect())),
275            ]
276        })
277    }
278
279    proptest! {
280        #[test]
281        fn dict_then_undict_is_the_identity_on_arbitrary_json(v in arb_json()) {
282            let bytes = serde_json::to_vec(&v).unwrap();
283            let dicted = dict_json(&bytes).unwrap();
284            prop_assert!(round_trips(&bytes, &dicted));
285            let back: Value = serde_json::from_slice(&undict_json(&dicted).unwrap()).unwrap();
286            prop_assert_eq!(back, v);
287        }
288    }
289}
tokenfold_core/transforms/json_dict.rs

tokenfold_core/transforms/
json_dict.rs
