Skip to main content

dive_value/
codec.rs

1//! A compact, deterministic byte encoding of values.
2//!
3//! State storage (`dive-store`) keeps states as bytes: frontier blocks, the exact
4//! store, disk spill and checkpoints. This module encodes one value; a state is the
5//! concatenation of its variables' encodings. Two encodings are provided.
6//!
7//! - [`encode`] is **lossless**. Decoding gives back the same representation, not just
8//!   an equal value: `1..3` stays an interval, an unnormalized set stays unnormalized
9//!   (with TLC's `isNorm` flag), a record literal stays a record literal. TLC's
10//!   observable behaviour depends on representation (printing, comparability), so the
11//!   frontier and disk spill use this encoding.
12//! - [`encode_canonical`] is the **exact-store key**. Within one run (one
13//!   [`Interner`](crate::Interner) and one [`Ctx`]), two values have equal canonical
14//!   bytes exactly when they are equal (`==`). Sets are written as their normalized
15//!   elements, a non-empty set of consecutive integers as its bounds (so `1..3` and
16//!   `{1, 2, 3}` agree, and `0..2147483646` costs O(1)), and records ignore the
17//!   record-literal bit. It fails exactly where TLC's fingerprinting fails (`Nat` in a
18//!   state, say) and normalizes what fingerprinting normalizes. Decoding it gives an
19//!   equal value, possibly with another representation.
20//!
21//! Both encodings are prefix-free, so a concatenation of encodings decodes uniquely.
22//! They are deterministic and platform-independent: integers are LEB128 varints
23//! (zigzag for signed values), and names are written as their intern token
24//! ([`Atom::tok`]), which [`decode`] resolves through the run's interner
25//! ([`Interner::resolve`](crate::Interner::resolve)).
26//!
27//! Encoding and decoding are iterative, so any nesting depth is safe.
28//!
29//! The structural tuple/function distinction was ambiguous in version 1: both
30//! used `0x08`. Persisted value-bearing formats must reject old archives, since
31//! the missing literal bit cannot be inferred. Raw old `0x08` decodes only as a
32//! literal tuple; it is not a migration of an old tuple-domain function.
33//! Canonical keys deliberately keep `0x08` for both equal representations.
34//!
35//! # Structural format (version 2)
36//!
37//! | Tag | Value | Payload |
38//! |---|---|---|
39//! | `0x00`, `0x01` | `FALSE`, `TRUE` | |
40//! | `0x02` | integer in `i64` range | zigzag varint |
41//! | `0x03` | integer outside `i64` range | sign byte, varint length, magnitude bytes (little-endian) |
42//! | `0x04` | string | varint token |
43//! | `0x05` | model value | varint token |
44//! | `0x08` | literal tuple (also the unchanged canonical-key tuple tag) | varint `n`, `n` values |
45//! | `0x0A` | nonliteral tuple-domain function | varint `n`, `n` values |
46//! | `0x10` | normalized set | varint `n`, `n` values in the set's order |
47//! | `0x12` | unnormalized set | `isNorm` byte, varint `n`, `n` values as constructed |
48//! | `0x14` | `lo..hi` | two integers |
49//! | `0x16` | `SUBSET S` | `S` |
50//! | `0x18` | `[S -> T]` | `S`, `T` |
51//! | `0x1A` | `[f1 : S1, ...]` | varint `n`, `n` × (token, value) |
52//! | `0x1C` | `S1 \X ...` | varint `n`, `n` values |
53//! | `0x1E`, `0x20`, `0x22` | `Nat`, `Int`, `STRING` | |
54//! | `0x24` | `Seq(S)` | `S` |
55//! | `0x26` | record literal | varint `n`, `n` × (token, value) |
56//! | `0x28` | function with a string domain | varint `n`, `n` × (token, value) |
57//! | `0x2A` | other function | varint `n`, `n` × (argument, value) |
58//!
59//! For tags `0x10` and above, bit 0 is the [`ValueOrder`] the set or function is
60//! sorted in (`1` for [`ValueOrder::Tlc`]). Evaluator-driven lazy sets
61//! ([`DeferredSet`](crate::DeferredSet)) cannot be written as their definition; both
62//! encodings write their elements as a normalized set, which needs a [`Ctx`] and can
63//! fail with the evaluator's error.
64//!
65//! ```
66//! use dive_value::{codec, Ctx, Int, Interner, Value};
67//!
68//! let names = Interner::new();
69//! let ctx = Ctx::tlc();
70//! let v = Value::tuple(vec![
71//!     Value::interval(Int::from(1), Int::from(3), ctx),
72//!     Value::string(&names, "a"),
73//! ]);
74//! let mut bytes = Vec::new();
75//! codec::encode(&v, ctx, &mut bytes)?;
76//! let back = codec::decode(&mut bytes.as_slice(), &mut |t| names.resolve(t))?;
77//! assert_eq!(back, v);
78//!
79//! // The canonical key does not depend on representation.
80//! let (mut k1, mut k2) = (Vec::new(), Vec::new());
81//! codec::encode_canonical(&Value::interval(Int::from(1), Int::from(3), ctx), ctx, &mut k1)?;
82//! let enumerated = Value::set(vec![Value::Int(3), Value::Int(1), Value::Int(2)], ctx)?;
83//! codec::encode_canonical(&enumerated, ctx, &mut k2)?;
84//! assert_eq!(k1, k2);
85//! # Ok::<(), dive_value::ValueError>(())
86//! ```
87
88use num_bigint::{BigInt, Sign};
89
90use crate::atom::Atom;
91use crate::ctx::{Ctx, ValueOrder};
92use crate::error::{ErrorKind, Result, ValueError};
93use crate::fp64::{is_fingerprintable, not_fingerprintable};
94use crate::int::Int;
95use crate::stream::elems_in;
96use crate::value::{Fcn, FcnRepr, Set, SetRepr, Value};
97
98mod tag {
99    pub const FALSE: u8 = 0x00;
100    pub const TRUE: u8 = 0x01;
101    pub const INT: u8 = 0x02;
102    pub const BIGINT: u8 = 0x03;
103    pub const STR: u8 = 0x04;
104    pub const MODEL: u8 = 0x05;
105    pub const TUPLE: u8 = 0x08;
106    pub const TUPLEFCN: u8 = 0x0A;
107    pub const SET: u8 = 0x10;
108    pub const RAW: u8 = 0x12;
109    pub const INTERVAL: u8 = 0x14;
110    pub const SUBSET: u8 = 0x16;
111    pub const FCNSET: u8 = 0x18;
112    pub const RCDSET: u8 = 0x1A;
113    pub const PRODUCT: u8 = 0x1C;
114    pub const NAT: u8 = 0x1E;
115    pub const INTSET: u8 = 0x20;
116    pub const STRINGS: u8 = 0x22;
117    pub const SEQ: u8 = 0x24;
118    pub const RECORD: u8 = 0x26;
119    pub const RCDFCN: u8 = 0x28;
120    pub const FCN: u8 = 0x2A;
121}
122
123fn order_bit(order: ValueOrder) -> u8 {
124    match order {
125        ValueOrder::Canonical => 0,
126        ValueOrder::Tlc => 1,
127    }
128}
129
130fn order_of(tag: u8) -> ValueOrder {
131    if tag & 1 == 1 {
132        ValueOrder::Tlc
133    } else {
134        ValueOrder::Canonical
135    }
136}
137
138/// Appends `x` as an unsigned LEB128 varint.
139pub fn write_varint(out: &mut Vec<u8>, mut x: u64) {
140    while x >= 0x80 {
141        out.push(x.to_le_bytes()[0] | 0x80);
142        x >>= 7;
143    }
144    out.push(x.to_le_bytes()[0]);
145}
146
147/// Reads an unsigned LEB128 varint written by [`write_varint`].
148///
149/// # Errors
150/// [`ErrorKind::Codec`] on truncated or overlong input.
151pub fn read_varint(input: &mut &[u8]) -> Result<u64> {
152    let mut x = 0u64;
153    for shift in (0..64).step_by(7) {
154        let b = read_u8(input)?;
155        let low = u64::from(b & 0x7F);
156        if shift == 63 && low > 1 {
157            return Err(corrupt("varint overflows 64 bits"));
158        }
159        x |= low << shift;
160        if b & 0x80 == 0 {
161            return Ok(x);
162        }
163    }
164    Err(corrupt("varint longer than 10 bytes"))
165}
166
167fn zigzag(v: i64) -> u64 {
168    #[allow(clippy::cast_sign_loss, reason = "zigzag is a bit reinterpretation")]
169    let z = ((v << 1) ^ (v >> 63)) as u64;
170    z
171}
172
173fn unzigzag(z: u64) -> i64 {
174    #[allow(
175        clippy::cast_possible_wrap,
176        reason = "zigzag is a bit reinterpretation"
177    )]
178    let v = ((z >> 1) as i64) ^ -((z & 1) as i64);
179    v
180}
181
182fn corrupt(what: &str) -> ValueError {
183    ValueError::new(ErrorKind::Codec, format!("invalid value encoding: {what}"))
184}
185
186fn read_u8(input: &mut &[u8]) -> Result<u8> {
187    let (&b, rest) = input.split_first().ok_or_else(|| corrupt("truncated"))?;
188    *input = rest;
189    Ok(b)
190}
191
192fn write_len(out: &mut Vec<u8>, n: usize) {
193    write_varint(out, n as u64);
194}
195
196fn write_tok(out: &mut Vec<u8>, a: &Atom) {
197    write_varint(out, u64::from(a.tok()));
198}
199
200fn write_int(out: &mut Vec<u8>, i: &Int) {
201    if let Some(v) = i.to_i64() {
202        out.push(tag::INT);
203        write_varint(out, zigzag(v));
204    } else {
205        let (sign, mag) = i.to_big().to_bytes_le();
206        out.push(tag::BIGINT);
207        out.push(u8::from(sign == Sign::Minus));
208        write_len(out, mag.len());
209        out.extend_from_slice(&mag);
210    }
211}
212
213/// One pending item of an iterative encoding.
214enum Frame<'a> {
215    /// A value borrowed from the value being encoded.
216    Ref(&'a Value),
217    /// A value generated on the way, encoded by a nested traversal.
218    Own(Value),
219    /// A name written as its token.
220    Tok(&'a Atom),
221}
222
223/// Maximum nodes inspected by one callback-free frontier codec admission.
224pub const FRONTIER_MAX_NODES: usize = 65_536;
225
226/// A conservative byte bound for callback-free lossless frontier encoding.
227/// This walks representation only, never normalizes a set or evaluates a
228/// deferred callback. Its traversal is capped at 65,536 nodes. The ordinary
229/// [`encode`] contract remains unchanged.
230///
231/// # Errors
232/// [`ErrorKind::NotEnumerable`] for any evaluator-driven deferred set, or
233/// [`ErrorKind::DiveLimit`] when the byte/traversal admission limit is exceeded.
234#[allow(clippy::too_many_lines, reason = "all lossless representation forms")]
235pub fn frontier_size_bound(value: &Value, maximum: usize) -> Result<usize> {
236    let limit = || {
237        ValueError::new(
238            ErrorKind::DiveLimit,
239            "frontier codec byte or 65536-node admission limit",
240        )
241    };
242    let mut stack = vec![value];
243    let mut visited = 0usize;
244    let mut bytes = 0usize;
245    while let Some(v) = stack.pop() {
246        visited += 1;
247        if visited + stack.len() > FRONTIER_MAX_NODES {
248            return Err(limit());
249        }
250        let mut overhead = 11usize;
251        match v {
252            Value::Bool(_) => overhead = 1,
253            Value::Int(_) | Value::Str(_) | Value::Model(_) => {}
254            Value::BigInt(b) => {
255                overhead = usize::try_from(b.bits().div_ceil(8))
256                    .map_err(|_| limit())?
257                    .saturating_add(12);
258            }
259            Value::Fcn(f) => match &f.0.repr {
260                FcnRepr::Tuple(e) => {
261                    if visited + stack.len() + e.len() > FRONTIER_MAX_NODES {
262                        return Err(limit());
263                    }
264                    stack.extend(e.iter());
265                }
266                FcnRepr::Record(fields) => {
267                    if visited + stack.len() + fields.len() > FRONTIER_MAX_NODES {
268                        return Err(limit());
269                    }
270                    overhead = overhead.saturating_add(fields.len().saturating_mul(10));
271                    stack.extend(fields.iter().map(|(_, v)| v));
272                }
273                FcnRepr::General(pairs) => {
274                    if visited + stack.len() + pairs.len().saturating_mul(2) > FRONTIER_MAX_NODES {
275                        return Err(limit());
276                    }
277                    for (d, v) in pairs {
278                        stack.push(d);
279                        stack.push(v);
280                    }
281                }
282            },
283            Value::Set(set) => match set.repr() {
284                SetRepr::Deferred(_) => {
285                    return Err(ValueError::new(
286                        ErrorKind::NotEnumerable,
287                        "frontier spill refuses evaluator-driven deferred values without evaluating them",
288                    ));
289                }
290                SetRepr::Enum => {
291                    if let Some(e) = set.0.elems.get() {
292                        if visited + stack.len() + e.len() > FRONTIER_MAX_NODES {
293                            return Err(limit());
294                        }
295                        stack.extend(e.iter());
296                    }
297                }
298                SetRepr::Raw(e) | SetRepr::Product(e) => {
299                    if visited + stack.len() + e.len() > FRONTIER_MAX_NODES {
300                        return Err(limit());
301                    }
302                    overhead += 1;
303                    stack.extend(e.iter());
304                }
305                SetRepr::Subset(v) | SetRepr::Seq(v) => stack.push(v),
306                SetRepr::FcnSet(d, r) => {
307                    stack.push(d);
308                    stack.push(r);
309                }
310                SetRepr::RcdSet(fields) => {
311                    if visited + stack.len() + fields.len() > FRONTIER_MAX_NODES {
312                        return Err(limit());
313                    }
314                    overhead = overhead.saturating_add(fields.len().saturating_mul(10));
315                    stack.extend(fields.iter().map(|(_, v)| v));
316                }
317                SetRepr::Interval(a, b) => {
318                    for i in [a, b] {
319                        let n = match i {
320                            Int::Small(_) => 11,
321                            Int::Big(v) => usize::try_from(v.bits().div_ceil(8))
322                                .map_err(|_| limit())?
323                                .saturating_add(12),
324                        };
325                        overhead = overhead.saturating_add(n);
326                    }
327                }
328                SetRepr::Nat | SetRepr::Int | SetRepr::Strings => overhead = 1,
329            },
330        }
331        bytes = bytes.checked_add(overhead).ok_or_else(limit)?;
332        if bytes > maximum {
333            return Err(limit());
334        }
335    }
336    Ok(bytes)
337}
338
339/// Encodes `v` losslessly, appending to `out` (see the module documentation).
340///
341/// `ctx` is needed only to enumerate evaluator-driven lazy sets.
342///
343/// # Errors
344/// Only from enumerating an evaluator-driven lazy set.
345pub fn encode(v: &Value, ctx: Ctx, out: &mut Vec<u8>) -> Result<()> {
346    let mut stack = vec![Frame::Ref(v)];
347    while let Some(frame) = stack.pop() {
348        match frame {
349            Frame::Tok(a) => write_tok(out, a),
350            Frame::Own(v) => encode(&v, ctx, out)?,
351            Frame::Ref(v) => encode_step(v, ctx, out, &mut stack)?,
352        }
353    }
354    Ok(())
355}
356
357fn tuple_tag(f: &Fcn) -> u8 {
358    if f.is_tuple_literal() {
359        tag::TUPLE
360    } else {
361        tag::TUPLEFCN
362    }
363}
364
365#[allow(
366    clippy::many_single_char_names,
367    reason = "short names mirror the format table: value, set, function, order"
368)]
369fn encode_step<'a>(
370    v: &'a Value,
371    ctx: Ctx,
372    out: &mut Vec<u8>,
373    stack: &mut Vec<Frame<'a>>,
374) -> Result<()> {
375    match v {
376        Value::Bool(b) => out.push(if *b { tag::TRUE } else { tag::FALSE }),
377        Value::Int(_) | Value::BigInt(_) => write_int(out, &v.as_int().unwrap_or(Int::ZERO)),
378        Value::Str(a) => {
379            out.push(tag::STR);
380            write_tok(out, a);
381        }
382        Value::Model(a) => {
383            out.push(tag::MODEL);
384            write_tok(out, a);
385        }
386        Value::Set(s) => {
387            let o = order_bit(s.order());
388            match s.repr() {
389                SetRepr::Enum | SetRepr::Deferred(_) => {
390                    if matches!(s.repr(), SetRepr::Deferred(_)) {
391                        s.elements(ctx)?;
392                    }
393                    let e = s.0.elems.get().map_or(&[][..], |e| &e[..]);
394                    out.push(tag::SET | o);
395                    write_len(out, e.len());
396                    stack.extend(e.iter().rev().map(Frame::Ref));
397                }
398                SetRepr::Raw(e) => {
399                    out.push(tag::RAW | o);
400                    out.push(u8::from(s.is_tlc_normalized()));
401                    write_len(out, e.len());
402                    stack.extend(e.iter().rev().map(Frame::Ref));
403                }
404                SetRepr::Interval(lo, hi) => {
405                    out.push(tag::INTERVAL | o);
406                    write_int(out, lo);
407                    write_int(out, hi);
408                }
409                SetRepr::Subset(b) => {
410                    out.push(tag::SUBSET | o);
411                    stack.push(Frame::Ref(b));
412                }
413                SetRepr::Seq(b) => {
414                    out.push(tag::SEQ | o);
415                    stack.push(Frame::Ref(b));
416                }
417                SetRepr::FcnSet(d, r) => {
418                    out.push(tag::FCNSET | o);
419                    stack.push(Frame::Ref(r));
420                    stack.push(Frame::Ref(d));
421                }
422                SetRepr::RcdSet(fs) => {
423                    out.push(tag::RCDSET | o);
424                    write_len(out, fs.len());
425                    for (a, x) in fs.iter().rev() {
426                        stack.push(Frame::Ref(x));
427                        stack.push(Frame::Tok(a));
428                    }
429                }
430                SetRepr::Product(fs) => {
431                    out.push(tag::PRODUCT | o);
432                    write_len(out, fs.len());
433                    stack.extend(fs.iter().rev().map(Frame::Ref));
434                }
435                SetRepr::Nat => out.push(tag::NAT | o),
436                SetRepr::Int => out.push(tag::INTSET | o),
437                SetRepr::Strings => out.push(tag::STRINGS | o),
438            }
439        }
440        Value::Fcn(f) => {
441            let o = order_bit(f.order());
442            match &f.0.repr {
443                FcnRepr::Tuple(e) => {
444                    out.push(tuple_tag(f));
445                    write_len(out, e.len());
446                    stack.extend(e.iter().rev().map(Frame::Ref));
447                }
448                FcnRepr::Record(fs) => {
449                    let t = if f.is_record_literal() {
450                        tag::RECORD
451                    } else {
452                        tag::RCDFCN
453                    };
454                    out.push(t | o);
455                    write_len(out, fs.len());
456                    for (a, x) in fs.iter().rev() {
457                        stack.push(Frame::Ref(x));
458                        stack.push(Frame::Tok(a));
459                    }
460                }
461                FcnRepr::General(ps) => {
462                    out.push(tag::FCN | o);
463                    write_len(out, ps.len());
464                    for (d, x) in ps.iter().rev() {
465                        stack.push(Frame::Ref(x));
466                        stack.push(Frame::Ref(d));
467                    }
468                }
469            }
470        }
471    }
472    Ok(())
473}
474
475/// Encodes `v` as its canonical exact-store key, appending to `out` (see the module
476/// documentation): within one run, equal values, and only equal values, have equal
477/// keys.
478///
479/// # Errors
480/// Exactly TLC's fingerprinting errors: a set that cannot be fingerprinted (such as
481/// `Nat`), and size, enumeration and normalization errors.
482pub fn encode_canonical(v: &Value, ctx: Ctx, out: &mut Vec<u8>) -> Result<()> {
483    let mut stack = vec![Frame::Ref(v)];
484    while let Some(frame) = stack.pop() {
485        match frame {
486            Frame::Tok(a) => write_tok(out, a),
487            Frame::Own(v) => encode_canonical(&v, ctx, out)?,
488            Frame::Ref(v) => canonical_step(v, ctx, out, &mut stack)?,
489        }
490    }
491    Ok(())
492}
493
494/// The bounds `(lo, hi)` if the normalized `elems` are exactly the integers `lo..hi`.
495fn int_range(elems: &[Value]) -> Option<(Int, Int)> {
496    let first = elems.first()?.as_int()?;
497    let last = elems.last()?.as_int()?;
498    if !elems
499        .iter()
500        .all(|e| matches!(e, Value::Int(_) | Value::BigInt(_)))
501    {
502        return None;
503    }
504    // Normalized integer sets are sorted ascending without duplicates (in both
505    // orders), so they are consecutive exactly when they span `len` values.
506    let span = last.to_big() - first.to_big() + 1u32;
507    (span == BigInt::from(elems.len())).then_some((first, last))
508}
509
510fn canonical_step<'a>(
511    v: &'a Value,
512    ctx: Ctx,
513    out: &mut Vec<u8>,
514    stack: &mut Vec<Frame<'a>>,
515) -> Result<()> {
516    match v {
517        Value::Set(s) => canonical_set(v, s, ctx, out, stack),
518        Value::Fcn(f) => {
519            canonical_fcn(f, ctx, out, stack);
520            Ok(())
521        }
522        _ => encode_step(v, ctx, out, stack),
523    }
524}
525
526fn canonical_set<'a>(
527    v: &'a Value,
528    s: &'a Set,
529    ctx: Ctx,
530    out: &mut Vec<u8>,
531    stack: &mut Vec<Frame<'a>>,
532) -> Result<()> {
533    if !is_fingerprintable(s) {
534        return Err(not_fingerprintable(v, ctx));
535    }
536    // As TLC's fingerprinting, size (and normalize) the set first.
537    s.size(ctx)?;
538    let o = order_bit(ctx.order);
539    if let SetRepr::Interval(lo, hi) = s.repr() {
540        if hi < lo {
541            out.push(tag::SET | o);
542            write_len(out, 0);
543        } else {
544            out.push(tag::INTERVAL | o);
545            write_int(out, lo);
546            write_int(out, hi);
547        }
548        return Ok(());
549    }
550    if s.order() == ctx.order {
551        s.elements(ctx)?;
552        let e = s.0.elems.get().map_or(&[][..], |e| &e[..]);
553        if let Some((lo, hi)) = int_range(e) {
554            out.push(tag::INTERVAL | o);
555            write_int(out, &lo);
556            write_int(out, &hi);
557        } else {
558            out.push(tag::SET | o);
559            write_len(out, e.len());
560            stack.extend(e.iter().rev().map(Frame::Ref));
561        }
562    } else {
563        let e = elems_in(s, ctx, true)?;
564        if let Some((lo, hi)) = int_range(&e) {
565            out.push(tag::INTERVAL | o);
566            write_int(out, &lo);
567            write_int(out, &hi);
568        } else {
569            out.push(tag::SET | o);
570            write_len(out, e.len());
571            stack.extend(e.iter().rev().cloned().map(Frame::Own));
572        }
573    }
574    Ok(())
575}
576
577fn canonical_fcn<'a>(f: &'a Fcn, ctx: Ctx, out: &mut Vec<u8>, stack: &mut Vec<Frame<'a>>) {
578    let o = order_bit(ctx.order);
579    match &f.0.repr {
580        FcnRepr::Tuple(e) => {
581            out.push(tag::TUPLE);
582            write_len(out, e.len());
583            stack.extend(e.iter().rev().map(Frame::Ref));
584        }
585        FcnRepr::Record(fs) if f.order() == ctx.order => {
586            out.push(tag::RCDFCN | o);
587            write_len(out, fs.len());
588            for (a, x) in fs.iter().rev() {
589                stack.push(Frame::Ref(x));
590                stack.push(Frame::Tok(a));
591            }
592        }
593        FcnRepr::General(ps) if f.order() == ctx.order => {
594            out.push(tag::FCN | o);
595            write_len(out, ps.len());
596            for (d, x) in ps.iter().rev() {
597                stack.push(Frame::Ref(x));
598                stack.push(Frame::Ref(d));
599            }
600        }
601        FcnRepr::Record(fs) => {
602            let mut fs: Vec<&(Atom, Value)> = fs.iter().collect();
603            fs.sort_by(|a, b| a.0.cmp_with(&b.0, ctx.order));
604            out.push(tag::RCDFCN | o);
605            write_len(out, fs.len());
606            for (a, x) in fs.into_iter().rev() {
607                stack.push(Frame::Ref(x));
608                stack.push(Frame::Tok(a));
609            }
610        }
611        FcnRepr::General(ps) => {
612            let mut ps: Vec<(&Value, &Value)> = ps.iter().collect();
613            ps.sort_by(|a, b| a.0.cmp_with(b.0, ctx.order));
614            out.push(tag::FCN | o);
615            write_len(out, ps.len());
616            for (d, x) in ps.into_iter().rev() {
617                stack.push(Frame::Ref(x));
618                stack.push(Frame::Ref(d));
619            }
620        }
621    }
622}
623
624/// A compound value being decoded: its tag, the items read so far, and how many it
625/// needs.
626struct Build {
627    tag: u8,
628    /// `isNorm` for an unnormalized set.
629    flag: bool,
630    need: usize,
631    names: Vec<Atom>,
632    items: Vec<Value>,
633}
634
635impl Build {
636    fn named(&self) -> bool {
637        matches!(self.tag & !1, tag::RCDSET | tag::RECORD | tag::RCDFCN)
638    }
639
640    fn finish(self) -> Value {
641        let order = order_of(self.tag);
642        let ctx = Ctx {
643            order,
644            ..Ctx::default()
645        };
646        let mut items = self.items.into_iter();
647        let mut next = || items.next().unwrap_or(Value::FALSE);
648        match self.tag & !1 {
649            tag::TUPLE => Value::Fcn(Fcn::tuple(items.collect())),
650            tag::TUPLEFCN => Value::Fcn(Fcn::tuple_fcn(items.collect())),
651            tag::SET => Value::Set(Set::from_sorted(order, items.collect())),
652            tag::RAW => {
653                let v = Value::set_raw(items.collect(), ctx);
654                if let (true, Value::Set(s)) = (self.flag, &v) {
655                    s.mark_normalized();
656                }
657                v
658            }
659            tag::SUBSET => Value::Set(Set::new(order, SetRepr::Subset(next()))),
660            tag::SEQ => Value::Set(Set::new(order, SetRepr::Seq(next()))),
661            tag::FCNSET => {
662                let d = next();
663                let r = next();
664                Value::Set(Set::new(order, SetRepr::FcnSet(d, r)))
665            }
666            tag::PRODUCT => Value::Set(Set::new(
667                order,
668                SetRepr::Product(items.collect::<Vec<_>>().into_boxed_slice()),
669            )),
670            tag::RCDSET => Value::Set(Set::new(
671                order,
672                SetRepr::RcdSet(self.names.into_iter().zip(items).collect()),
673            )),
674            tag::RECORD | tag::RCDFCN => Value::Fcn(Fcn::record(
675                self.names.into_iter().zip(items).collect(),
676                order,
677                self.tag & !1 == tag::RECORD,
678            )),
679            _ => {
680                // tag::FCN: arguments and values alternate.
681                let mut pairs = Vec::with_capacity(self.need / 2);
682                while let (Some(d), Some(x)) = (items.next(), items.next()) {
683                    pairs.push((d, x));
684                }
685                Value::Fcn(Fcn::general(pairs, order))
686            }
687        }
688    }
689}
690
691fn read_tok<A: FnMut(u32) -> Option<Atom>>(input: &mut &[u8], atoms: &mut A) -> Result<Atom> {
692    let tok = u32::try_from(read_varint(input)?).map_err(|_| corrupt("token out of range"))?;
693    atoms(tok).ok_or_else(|| corrupt("unknown name token"))
694}
695
696/// Reads a tagged integer.
697fn read_int(input: &mut &[u8]) -> Result<Int> {
698    let t = read_u8(input)?;
699    read_int_body(t, input)
700}
701
702/// Reads an integer's payload after its tag `t`.
703fn read_int_body(t: u8, input: &mut &[u8]) -> Result<Int> {
704    match t {
705        tag::INT => Ok(Int::Small(unzigzag(read_varint(input)?))),
706        tag::BIGINT => {
707            let neg = read_u8(input)? != 0;
708            let n = read_count(input)?;
709            if n > input.len() {
710                return Err(corrupt("truncated integer"));
711            }
712            let (mag, rest) = input.split_at(n);
713            *input = rest;
714            let sign = if neg { Sign::Minus } else { Sign::Plus };
715            Ok(Int::from_big(BigInt::from_bytes_le(sign, mag)))
716        }
717        _ => Err(corrupt("expected an integer")),
718    }
719}
720
721fn read_count(input: &mut &[u8]) -> Result<usize> {
722    usize::try_from(read_varint(input)?).map_err(|_| corrupt("count out of range"))
723}
724
725/// Decodes one value written by [`encode`] or [`encode_canonical`] from the front of
726/// `input`, advancing it past the value.
727///
728/// `atoms` maps an intern token back to its name; pass `&mut |t| names.resolve(t)`
729/// for the run's [`Interner`](crate::Interner), or a caching wrapper.
730///
731/// # Errors
732/// [`ErrorKind::Codec`] if `input` does not start with a valid encoding or names an
733/// unknown token. Decoding never panics, whatever the input.
734pub fn decode<A: FnMut(u32) -> Option<Atom>>(input: &mut &[u8], atoms: &mut A) -> Result<Value> {
735    let mut stack: Vec<Build> = Vec::new();
736    loop {
737        if let Some(top) = stack.last_mut()
738            && top.named()
739            && top.names.len() == top.items.len()
740        {
741            top.names.push(read_tok(input, atoms)?);
742        }
743        let t = read_u8(input)?;
744        let leaf = match t {
745            tag::FALSE => Some(Value::FALSE),
746            tag::TRUE => Some(Value::TRUE),
747            tag::INT | tag::BIGINT => Some(Value::int(read_int_body(t, input)?)),
748            tag::STR => Some(Value::Str(read_tok(input, atoms)?)),
749            tag::MODEL => Some(Value::Model(read_tok(input, atoms)?)),
750            _ => {
751                let order = order_of(t);
752                match t & !1 {
753                    tag::INTERVAL => {
754                        let lo = read_int(input)?;
755                        let hi = read_int(input)?;
756                        Some(Value::Set(Set::new(order, SetRepr::Interval(lo, hi))))
757                    }
758                    tag::NAT => Some(Value::Set(Set::new(order, SetRepr::Nat))),
759                    tag::INTSET => Some(Value::Set(Set::new(order, SetRepr::Int))),
760                    tag::STRINGS => Some(Value::Set(Set::new(order, SetRepr::Strings))),
761                    tag::SUBSET | tag::SEQ | tag::FCNSET => {
762                        let need = if t & !1 == tag::FCNSET { 2 } else { 1 };
763                        stack.push(build(t, false, need, input));
764                        None
765                    }
766                    tag::TUPLE
767                    | tag::TUPLEFCN
768                    | tag::SET
769                    | tag::RAW
770                    | tag::RCDSET
771                    | tag::PRODUCT
772                    | tag::RECORD
773                    | tag::RCDFCN
774                    | tag::FCN => {
775                        let flag = if t & !1 == tag::RAW {
776                            read_u8(input)? != 0
777                        } else {
778                            false
779                        };
780                        let n = read_count(input)?;
781                        let need = if t & !1 == tag::FCN {
782                            n.checked_mul(2)
783                                .ok_or_else(|| corrupt("count out of range"))?
784                        } else {
785                            n
786                        };
787                        let b = build(t, flag, need, input);
788                        if need == 0 {
789                            Some(b.finish())
790                        } else {
791                            stack.push(b);
792                            None
793                        }
794                    }
795                    _ => return Err(corrupt("unknown tag")),
796                }
797            }
798        };
799        let Some(mut v) = leaf else { continue };
800        loop {
801            let Some(top) = stack.last_mut() else {
802                return Ok(v);
803            };
804            top.items.push(v);
805            if top.items.len() < top.need {
806                break;
807            }
808            let Some(done) = stack.pop() else {
809                return Err(corrupt("internal decoder state"));
810            };
811            v = done.finish();
812        }
813    }
814}
815
816/// Starts a compound value, reserving no more than the remaining input could hold
817/// (every item takes at least one byte), so corrupt counts cannot exhaust memory.
818fn build(t: u8, flag: bool, need: usize, input: &[u8]) -> Build {
819    let cap = need.min(input.len());
820    let named = matches!(t & !1, tag::RCDSET | tag::RECORD | tag::RCDFCN);
821    Build {
822        tag: t,
823        flag,
824        need,
825        names: Vec::with_capacity(if named { cap } else { 0 }),
826        items: Vec::with_capacity(cap),
827    }
828}
829
830/// Encoded byte length used by size regression controls.
831#[cfg(test)]
832fn encoded_len(v: &Value) -> usize {
833    let mut out = Vec::new();
834    let _ = encode(v, Ctx::default(), &mut out);
835    out.len()
836}
837
838#[cfg(test)]
839mod tests {
840    use super::*;
841
842    #[test]
843    fn varints_round_trip() {
844        for x in [0u64, 1, 127, 128, 300, u64::from(u32::MAX), u64::MAX] {
845            let mut out = Vec::new();
846            write_varint(&mut out, x);
847            assert_eq!(read_varint(&mut out.as_slice()).ok(), Some(x));
848        }
849        for v in [0i64, -1, 1, i64::MIN, i64::MAX] {
850            assert_eq!(unzigzag(zigzag(v)), v);
851        }
852    }
853
854    #[test]
855    fn small_values_are_small() {
856        assert_eq!(encoded_len(&Value::Int(5)), 2);
857        assert_eq!(encoded_len(&Value::TRUE), 1);
858        assert_eq!(
859            encoded_len(&Value::tuple(vec![Value::Int(1), Value::Int(2)])),
860            6
861        );
862    }
863
864    #[test]
865    fn truncated_input_is_an_error() {
866        let v = Value::tuple(vec![Value::Int(1000), Value::Int(2)]);
867        let mut out = Vec::new();
868        assert!(encode(&v, Ctx::default(), &mut out).is_ok());
869        for cut in 0..out.len() {
870            let r = decode(&mut &out[..cut], &mut |_| None);
871            assert!(r.is_err(), "prefix of {cut} bytes decoded");
872        }
873    }
874}