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.
encodeis lossless. Decoding gives back the same representation, not just an equal value:1..3stays an interval, an unnormalized set stays unnormalized (with TLC’sisNormflag), 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_canonicalis the exact-store key. Within one run (oneInternerand oneCtx), 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 (so1..3and{1, 2, 3}agree, and0..2147483646costs O(1)), and records ignore the record-literal bit. It fails exactly where TLC’s fingerprinting fails (Natin 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)
| Tag | Value | Payload |
|---|---|---|
0x00, 0x01 | FALSE, TRUE | |
0x02 | integer in i64 range | zigzag varint |
0x03 | integer outside i64 range | sign byte, varint length, magnitude bytes (little-endian) |
0x04 | string | varint token |
0x05 | model value | varint token |
0x08 | literal tuple (also the unchanged canonical-key tuple tag) | varint n, n values |
0x0A | nonliteral tuple-domain function | varint n, n values |
0x10 | normalized set | varint n, n values in the set’s order |
0x12 | unnormalized set | isNorm byte, varint n, n values as constructed |
0x14 | lo..hi | two integers |
0x16 | SUBSET S | S |
0x18 | [S -> T] | S, T |
0x1A | [f1 : S1, ...] | varint n, n × (token, value) |
0x1C | S1 \X ... | varint n, n values |
0x1E, 0x20, 0x22 | Nat, Int, STRING | |
0x24 | Seq(S) | S |
0x26 | record literal | varint n, n × (token, value) |
0x28 | function with a string domain | varint n, n × (token, value) |
0x2A | other function | varint 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
encodeorencode_canonicalfrom the front ofinput, advancing it past the value. - encode
- Encodes
vlosslessly, appending toout(see the module documentation). - encode_
canonical - Encodes
vas its canonical exact-store key, appending toout(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
encodecontract remains unchanged. - read_
varint - Reads an unsigned LEB128 varint written by
write_varint. - write_
varint - Appends
xas an unsigned LEB128 varint.