Skip to main content

Module codec

Module codec 

Source
Expand description

A compact, deterministic byte encoding of values.

State storage (dive-store) keeps states as bytes: frontier blocks, the exact store, disk spill and checkpoints. This module encodes one value; a state is the concatenation of its variables’ encodings. Two encodings are provided.

  • encode is lossless. Decoding gives back the same representation, not just an equal value: 1..3 stays an interval, an unnormalized set stays unnormalized (with TLC’s isNorm flag), a record literal stays a record literal. TLC’s observable behaviour depends on representation (printing, comparability), so the frontier and disk spill use this encoding.
  • encode_canonical is the exact-store key. Within one run (one Interner and one Ctx), two values have equal canonical bytes exactly when they are equal (==). Sets are written as their normalized elements, a non-empty set of consecutive integers as its bounds (so 1..3 and {1, 2, 3} agree, and 0..2147483646 costs O(1)), and records ignore the record-literal bit. It fails exactly where TLC’s fingerprinting fails (Nat in a state, say) and normalizes what fingerprinting normalizes. Decoding it gives an equal value, possibly with another representation.

Both encodings are prefix-free, so a concatenation of encodings decodes uniquely. They are deterministic and platform-independent: integers are LEB128 varints (zigzag for signed values), and names are written as their intern token (Atom::tok), which decode resolves through the run’s interner (Interner::resolve).

Encoding and decoding are iterative, so any nesting depth is safe.

The structural tuple/function distinction was ambiguous in version 1: both used 0x08. Persisted value-bearing formats must reject old archives, since the missing literal bit cannot be inferred. Raw old 0x08 decodes only as a literal tuple; it is not a migration of an old tuple-domain function. Canonical keys deliberately keep 0x08 for both equal representations.

§Structural format (version 2)

TagValuePayload
0x00, 0x01FALSE, TRUE
0x02integer in i64 rangezigzag varint
0x03integer outside i64 rangesign byte, varint length, magnitude bytes (little-endian)
0x04stringvarint token
0x05model valuevarint token
0x08literal tuple (also the unchanged canonical-key tuple tag)varint n, n values
0x0Anonliteral tuple-domain functionvarint n, n values
0x10normalized setvarint n, n values in the set’s order
0x12unnormalized setisNorm byte, varint n, n values as constructed
0x14lo..hitwo integers
0x16SUBSET SS
0x18[S -> T]S, T
0x1A[f1 : S1, ...]varint n, n × (token, value)
0x1CS1 \X ...varint n, n values
0x1E, 0x20, 0x22Nat, Int, STRING
0x24Seq(S)S
0x26record literalvarint n, n × (token, value)
0x28function with a string domainvarint n, n × (token, value)
0x2Aother functionvarint n, n × (argument, value)

For tags 0x10 and above, bit 0 is the ValueOrder the set or function is sorted in (1 for ValueOrder::Tlc). Evaluator-driven lazy sets (DeferredSet) cannot be written as their definition; both encodings write their elements as a normalized set, which needs a Ctx and can fail with the evaluator’s error.

use dive_value::{codec, Ctx, Int, Interner, Value};

let names = Interner::new();
let ctx = Ctx::tlc();
let v = Value::tuple(vec![
    Value::interval(Int::from(1), Int::from(3), ctx),
    Value::string(&names, "a"),
]);
let mut bytes = Vec::new();
codec::encode(&v, ctx, &mut bytes)?;
let back = codec::decode(&mut bytes.as_slice(), &mut |t| names.resolve(t))?;
assert_eq!(back, v);

// The canonical key does not depend on representation.
let (mut k1, mut k2) = (Vec::new(), Vec::new());
codec::encode_canonical(&Value::interval(Int::from(1), Int::from(3), ctx), ctx, &mut k1)?;
let enumerated = Value::set(vec![Value::Int(3), Value::Int(1), Value::Int(2)], ctx)?;
codec::encode_canonical(&enumerated, ctx, &mut k2)?;
assert_eq!(k1, k2);

Constants§

FRONTIER_MAX_NODES
Maximum nodes inspected by one callback-free frontier codec admission.

Functions§

decode
Decodes one value written by encode or encode_canonical from the front of input, advancing it past the value.
encode
Encodes v losslessly, appending to out (see the module documentation).
encode_canonical
Encodes v as its canonical exact-store key, appending to out (see the module documentation): within one run, equal values, and only equal values, have equal keys.
frontier_size_bound
A conservative byte bound for callback-free lossless frontier encoding. This walks representation only, never normalizes a set or evaluates a deferred callback. Its traversal is capped at 65,536 nodes. The ordinary encode contract remains unchanged.
read_varint
Reads an unsigned LEB128 varint written by write_varint.
write_varint
Appends x as an unsigned LEB128 varint.