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(
151            a.iter()
152                .map(|it| replace(it, counts, index, index_of))
153                .collect(),
154        ),
155        _ => v.clone(),
156    }
157}
158
159/// Expands a whole document: if it's our `{__tf_dict__, __tf_data__}` wrapper, resolve every
160/// reference in the data against the dictionary; otherwise return it unchanged.
161fn restore(v: &Value) -> Value {
162    let Some((dict, data)) = as_wrapper(v) else {
163        return v.clone();
164    };
165    expand(data, dict)
166}
167
168fn as_wrapper(v: &Value) -> Option<(&Vec<Value>, &Value)> {
169    let m = v.as_object()?;
170    if m.len() != 2 {
171        return None;
172    }
173    let dict = m.get(DICT)?.as_array()?;
174    let data = m.get(DATA)?;
175    Some((dict, data))
176}
177
178fn expand(v: &Value, dict: &[Value]) -> Value {
179    if let Some(idx) = as_ref(v) {
180        // Dictionary entries are stored ref-free, so this resolves in one step; out-of-range
181        // indices are left as-is (the round-trip gate then rejects the fold).
182        return dict.get(idx).cloned().unwrap_or_else(|| v.clone());
183    }
184    match v {
185        Value::Object(m) => {
186            let mut o = Map::new();
187            for (k, val) in m {
188                o.insert(k.clone(), expand(val, dict));
189            }
190            Value::Object(o)
191        }
192        Value::Array(a) => Value::Array(a.iter().map(|it| expand(it, dict)).collect()),
193        _ => v.clone(),
194    }
195}
196
197fn as_ref(v: &Value) -> Option<usize> {
198    let m = v.as_object()?;
199    if m.len() != 1 {
200        return None;
201    }
202    Some(m.get(REF)?.as_u64()? as usize)
203}
204
205#[cfg(test)]
206mod tests {
207    use super::*;
208
209    fn parse(b: &[u8]) -> Value {
210        serde_json::from_slice(b).unwrap()
211    }
212
213    #[test]
214    fn dedups_a_repeated_large_object() {
215        let obj = r#"{"kind":"widget","color":"blue","size":"large"}"#;
216        let input = format!(r#"{{"a":{obj},"b":{obj},"c":{obj}}}"#);
217        let out = dict_json(input.as_bytes()).unwrap();
218        let s = String::from_utf8(out.clone()).unwrap();
219        assert!(s.contains("__tf_dict__"), "expected dict form, got {s}");
220        // the object literal appears once (in the dict), not three times
221        assert_eq!(s.matches("widget").count(), 1);
222        assert!(round_trips(input.as_bytes(), &out));
223    }
224
225    #[test]
226    fn dict_then_undict_reproduces_original() {
227        let obj = r#"{"kind":"widget","color":"blue","size":"large"}"#;
228        let input = format!(r#"[{obj},{obj},{obj},{obj}]"#);
229        let folded = dict_json(input.as_bytes()).unwrap();
230        let back = undict_json(&folded).unwrap();
231        assert_eq!(parse(&back), parse(input.as_bytes()));
232    }
233
234    #[test]
235    fn short_repeated_values_are_left_alone() {
236        // "member" is short; a reference would be longer, so it must NOT be dictionaried.
237        let input = br#"{"a":"member","b":"member","c":"member"}"#;
238        let out = dict_json(input).unwrap();
239        assert_eq!(parse(&out), parse(input));
240        assert!(!String::from_utf8(out).unwrap().contains("__tf_dict__"));
241    }
242
243    #[test]
244    fn single_occurrence_is_not_dictionaried() {
245        let input = br#"{"only":{"a":"quite a long value here indeed yes"}}"#;
246        let out = dict_json(input).unwrap();
247        assert!(!String::from_utf8(out).unwrap().contains("__tf_dict__"));
248    }
249
250    #[test]
251    fn nested_repeats_do_not_create_dead_entries() {
252        let inner = r#"{"deeply":"nested repeated value that is long"}"#;
253        let parent = format!(r#"{{"p":{inner},"q":"x"}}"#);
254        let input = format!(r#"[{parent},{parent}]"#);
255        let out = dict_json(input.as_bytes()).unwrap();
256        assert!(round_trips(input.as_bytes(), &out));
257    }
258
259    #[test]
260    fn empty_and_invalid_inputs() {
261        assert!(dict_json(b"").unwrap().is_empty());
262        assert!(dict_json(b"{bad").is_err());
263    }
264
265    use proptest::prelude::*;
266
267    fn arb_json() -> impl Strategy<Value = Value> {
268        let leaf = prop_oneof![
269            Just(Value::Null),
270            any::<bool>().prop_map(Value::Bool),
271            any::<i64>().prop_map(|n| Value::Number(n.into())),
272            "[^\"\\\\]{0,20}".prop_map(Value::String),
273        ];
274        leaf.prop_recursive(4, 48, 6, |inner| {
275            prop_oneof![
276                prop::collection::vec(inner.clone(), 0..6).prop_map(Value::Array),
277                prop::collection::hash_map("[a-z]{1,6}", inner, 0..6)
278                    .prop_map(|m| Value::Object(m.into_iter().collect())),
279            ]
280        })
281    }
282
283    proptest! {
284        #[test]
285        fn dict_then_undict_is_the_identity_on_arbitrary_json(v in arb_json()) {
286            let bytes = serde_json::to_vec(&v).unwrap();
287            let dicted = dict_json(&bytes).unwrap();
288            prop_assert!(round_trips(&bytes, &dicted));
289            let back: Value = serde_json::from_slice(&undict_json(&dicted).unwrap()).unwrap();
290            prop_assert_eq!(back, v);
291        }
292    }
293}
tokenfold_core/transforms/json_dict.rs

tokenfold_core/transforms/
json_dict.rs
