tiny.preserves

Overview · API · Code relationships · Verification · Audit

Overview

Two programs that exchange structured data have to agree on what a value is and when two values are the same, whichever encoding carried them. The package gives Zig programs one model of such data, with patterns written over its values and serialization that needs no schema. A value is an atom, a compound, or an embedded value that the host program supplies. The atoms are booleans, doubles, integers of any size, strings, byte strings and symbols. The compounds are records, sequences, sets and dictionaries. A record is a label with a list of fields. Values travel in a text syntax, in a compact binary syntax, and as JSON.

Two copies of one value have to be equal, sort to the same place and hash alike, so a value can key a hash map and sort the same way in every program. A set or a dictionary has no order of its own, so the order of its storage must leave equality, order and hash unchanged. A set holds each element once and a dictionary holds each key once, so reading or writing data that repeats one has to fail. A program has to know which memory each value owns and which call frees it.

Sets arrive in any order: a program builds them by hand, and a text document lists elements in the order its author wrote them. Comparing or hashing two sets element by element needs both in sorted order, and sorting a copy would allocate memory on every call. Embedded values belong to the host program, so the package has no way to compare, hash, free or copy them by itself. Integers in these values can exceed the range of every fixed-width Zig integer. A tree of values can mix bytes it owns with bytes it borrows, and freeing the tree then depends on knowing which is which. A Lean model of parser results proves that when a borrowed symbol and an owned symbol look the same, no single cleanup frees exactly the owned bytes of both.

The package implements the Preserves data language, which Tony Garnock-Jones and the Preserves contributors designed for the Syndicate ecosystem. A second source is Garnock-Jones's dissertation Conversational Concurrency. From these sources the package keeps the Preserves values, the patterns that match them, and the text, binary and JSON representations. The Preserves specification treats sets and dictionaries as unordered, requires distinct elements and keys, and compares two of them through their elements in ascending order. The specification's binary syntax writes set elements and dictionary keys sorted by their encoded bytes. The package follows both rules: its comparison reads sets and dictionaries in ascending order, and its binary writer sorts by encoded bytes.

The package changes two things so that it fits explicit memory management: the caller owns and frees all storage, and the binary and text decoders run within explicit limits. Every call that allocates takes an allocator from the caller, and the caller frees what the call returns. The binary decoder takes caller-set limits on nesting depth, value count, collection size and retained bytes. Both text decoders stop at 256 levels of nesting. One generic type, Value, holds every value. That type takes the type of its embedded values (domain) as a parameter, which also supplies their equality, order, cleanup and copy. assertIsDomain stops compilation when a type lacks one of those four functions. Two domains ship with the package. NoEmbedded has one value, and that value carries no data. AnyEmbedded points to a payload of the host program and carries optional functions to compare, hash, free and copy it. Custom equality, hashing and ordering for AnyEmbedded payloads come as one table of functions (SemanticOps). Two payloads are equal only when they share that table. The table's order must be total, its equality must hold exactly when the order returns .eq, and equal payloads must hash equally. An embedded value with no table compares and hashes by the address of its payload.

Value also holds four kinds of pattern (pattern form) beside the data: a discard, a capture of an inner pattern, a bind that gives an inner pattern a name, and a rest pattern that holds a sequence prefix and one pattern for the items after it. So one type carries both data and the patterns written over it. The JSON codec is the one codec that writes the four kinds of pattern and reads them back as patterns. The binary writer and text.encode refuse a pattern with error.PatternFormNotEncodable. toText prints a pattern in its record form, and the text readers read that text back as plain data. The package stores patterns and converts them to and from records, and it runs no match itself. Pattern forms order after every data kind.

Equality, order and hash read every set and dictionary in ascending order under compare, whatever the order of its storage. That walk allocates nothing, and it finds each next element by scanning the whole set, so its cost grows with the square of the set's size. A Lean model proves that sorted copies of two sets are equal exactly when their elements are permutations of each other. The same model proves that every observation of a sorted copy gives one answer for all such permutations. The set and dictionary constructors and every codec reject two equal set elements or two equal dictionary keys, on reading and on writing. Value.initSet and Value.initDictionary store the caller's slice unchecked. The binary writer emits set elements and dictionary keys sorted by their encoded bytes, and the binary reader rejects any other order.

Every decoder copies the bytes it reads, so a decoded value owns all its storage and stays valid after the input is freed. Value.deinit frees a decoded value. A value built by hand can borrow: string and symbol keep the caller's slice, and record, sequence, set and dictionary copy only the outer slice. Three calls free a value, one for each kind of ownership. Value.deinit frees a tree that owns every byte. freeValueDeep frees the compound storage of a tree and leaves its string, byte-string and symbol bytes. freeValue frees only the outer storage of one compound. cloneValueDeep copies a tree into new storage that owns every byte, and Value.deinit frees the copy. A SignedInteger holds an integer in 128 signed bits when it fits, in 128 unsigned bits when it is larger but still fits, and otherwise as its shortest big-endian two's-complement bytes.

The functions at the package root work on values whose domain is AnyEmbedded, the domain that parse and the JSON codec produce. The namespaces group the package: value, atom, integer_mod, domain, embedded_mod and ownership hold the value model. Beside them, symbols, constructors_mod, records_mod, predicates, patterns_mod and containers build and inspect values. parse_error names the text parser's errors, and text, packed and json are the codecs.

1const preserves = @import("preserves");23const fields = [_]preserves.Value(preserves.Embedded){4    preserves.string("world"),5};6const greeting = try preserves.record(7    allocator,8    preserves.symbol("greet"),9    &fields,10);11defer preserves.freeValue(allocator, greeting);1213const text = try preserves.toText(allocator, greeting);14defer allocator.free(text);

Definitions

Actions

Public operations.

• decodeText: Returns the one value text holds, allocated with allocator.
• encodeText: Returns the text of value as new bytes allocated with allocator.
• parsedEmbeddedOps: Returns one table whose equality, hash and order read each payload as a pointer to a Value and call eql, hash and compare on it.
• assertIsDomain: Stops compilation unless D declares public functions named eql, order, deinit and clone.
• Constructors: Returns a namespace of constructors for Value(D), the Preserves value whose embedded values hold a D.
• Records: Returns a namespace of protocol record builders for Value(D).
• foreachEmbedded: Calls callback(context, e) once for each embedded value e inside v, in storage order.
• mapEmbedded: Returns a copy of v in which each embedded value e is replaced by the value map_fn(context, alloc, e) returns.
• observeObserver: Returns the second field of an <Observe pattern observer> record with exactly two fields, and null for any other value.
• observePattern: Returns the first field of an <Observe pattern observer> record with exactly two fields, and null for any other value.
• parse: Returns the one value text holds, allocated with alloc.
• patternToPreserves: Writes the pattern values of pattern as records, the reverse of preservesToPattern.
• preserve: Returns v unchanged.
• preservePattern: Reads a pattern written as records and returns it as pattern values.
• preservesToPattern: Reads a pattern written as records and returns it as pattern values, with the same mapping as preservePattern.
• symbolEql: Returns whether the bytes sym_bytes equal the name of the symbol constant s, byte for byte.
• toText: Returns value as text, allocated with alloc.
• valueCompare: Returns the order of a against b, the same answer as a.compare(b).
• valueEqual: Returns whether a and b are equal, the same answer as a.eql(b).
• valueHash: Returns the value's 64-bit hash, the same answer as v.hash().
• decodePacked: Returns the one value that bytes encodes, allocated with allocator.
• encodePacked: Returns the binary encoding of value as new bytes allocated with allocator, for code that stores, sends or fingerprints a value.
• Value: Returns the tagged union of all values whose embedded values have type D.
• Conversions: Returns a namespace of pattern conversions for Value(D).
• cloneValueDeep: Copies v all the way down into storage from alloc: atom bytes, integer digits, bind names and compound storage.
• freeValue: Frees the outer storage of one compound value and nothing below it.
• freeValueDeep: Frees a value's compound storage all the way down: records, sequences, sets, dictionaries and the cells of the four pattern forms.
• isAtom: Returns whether v is a boolean, double, integer, string, byte string or symbol.
• isCompound: Returns whether v is a record, sequence, set or dictionary.
• isEmbedded: Returns whether v is an embedded value.
• isNull: Returns whether v is the symbol null, compared byte for byte.
• isObserve: Returns whether v is a record labeled with the symbol Observe that has exactly two fields.
• isPatternForm: Returns whether v is a discard, capture, bind or rest pattern.
• isRecord: Returns whether v is a record whose label is the symbol label and whose field count is arity.
• isSymbol: Returns whether v is a symbol.
• recordAttributes: Returns the attribute entries of a record whose fields are named.
• toJsonString: Returns value as minified JSON text, allocated with alloc, for code that logs or sends a value to a JSON consumer.
• fromJsonString: Parses json_text and returns the Preserves value it describes, allocated with alloc, for code that receives JSON text.
• fromJsonValue: Returns the Preserves value that json_value describes, allocated with alloc, for code that already holds a parsed std.json.Value, so the JSON is parsed once.

Types and contracts

Public types and contracts.

• SignedInteger: A signed integer of any size, stored in the smallest of three representations that holds it.
• AnyEmbedded: An embedded value that points to a payload of the host program, with optional functions to compare, hash, free and copy it.
• Embedded: An embedded value that points to a payload of the host program, with optional functions to compare, hash, free and copy it.
• CowBytes: A byte slice with a tag that says whether its holder owns the bytes.
• PackedTag: The tag byte that starts each encoded value, as an enum over u8, so code that writes encoded bytes by hand names each tag through it.
• AtomClass: The six kinds of atom, in the order Value ranks them: boolean, double, integer, string, byte string and symbol.
• CompoundClass: The four compound kinds, in the order compare ranks them: record, sequence, set and dictionary.
• NoEmbedded: A type of embedded values whose one value carries no data, for programs that embed nothing.
• Ownership: Whether the holder of some bytes owns them, and frees them with its own deinit, or borrows them from an owner that keeps them alive.
• ParseError: The errors parse returns: one tag per kind of malformed text, plus running out of nesting depth or memory.
• PatternFormClass: The four kinds of pattern, in the order compare ranks them: discard, capture, bind and rest pattern.
• SYM_ARR: The label arr of <arr>, the type of a group that matches sequences.
• SYM_BIND_PAT: The label bind of the <bind P> record, the wire form of a capture.
• SYM_DICT: The label dict of <dict>, the type of a group that matches dictionaries.
• SYM_DISCARD: The symbol _, the wire form of the discard pattern, alone or as the record <_>.
• SYM_ENTITY_RUNTIME: The label EntityRuntime, which entityRuntimeRecord writes.
• SYM_GROUP: The label group of the <group type {…}> record, the wire form of a record, sequence or dictionary pattern.
• SYM_LIT: The label lit of the <lit v> record, which matches the value v itself.
• SYM_NULL: The symbol null, the value the package uses for JSON's null.
• SYM_OBSERVE: The label Observe of the <Observe pattern observer> record.
• SYM_REACTOR_ERROR: The label ReactorError, which reactorErrorRecord writes.
• SYM_REC: The label rec of <rec L>, the type of a group that matches records labeled L.
• SYM_REQUIRE_SERVICE: The label RequireService, which requireServiceRecord writes.
• SYM_RESTART_SERVICE: The label RestartService, which restartServiceRecord writes.
• SYM_RUN_SERVICE: The label RunService, which runServiceRecord writes.
• SYM_SERVICE_DEPENDENCY: The label ServiceDependency, which serviceDependencyRecord writes.
• SYM_SERVICE_OBJECT: The label ServiceObject, which serviceObjectRecord writes.
• SYM_SERVICE_STATE: The label ServiceState, which serviceStateRecord writes.
• SYM_SYNCED: The label Synced, which syncedRecord writes.
• SemanticOps: One table of equality, hash and order functions over untyped payload pointers.
• Symbol: A symbol's name, held as a byte slice.
• ValueKind: A value's kind: its group and, for an atom, a compound or a pattern, which one.
• ValueKindTag: The four groups of kinds: atom, compound, embedded value and pattern.
• Bind: The parts of a bind: a name and a pointer to the inner pattern it names.
• Capture: A pointer to the inner pattern of a capture.
• DictEntry: One key and value pair of a dictionary, for values that use AnyEmbedded as the type of the embedded values, its domain.
• Dictionary: A slice of key and value entries, the storage of a dictionary value.
• Record: The parts of a record: a pointer to its label value and a slice of its field values.
• RestPattern: The parts of a rest pattern: a slice of patterns for the first items of a sequence and a pointer to one pattern for the items after them.
• ValueContext: A hash-map context whose hash calls Value.hash and whose equality calls Value.eql.
• ValueHashMap: A standard-library unmanaged hash map from values to values, keyed through ValueContext, with a maximum load of 80 percent.
• ValueSet: A standard-library unmanaged hash map from values to nothing, keyed through ValueContext, with a maximum load of 80 percent.
• CowSignedInteger: An integer with a tag that says whether its holder owns the integer's heap digits.
• Atom: A copy of one atom, tagged by its kind.

Namespaces

Public namespaces.

• integer_mod: Signed integers of any size, as data values carry them.
• symbols: Named constants for the symbols the package builds and matches: protocol record labels, null, and the pattern wire form.
• text_reader: Reads values from text, whatever the type of their embedded values.
• text_writer: Writes values as text, whatever the type of their embedded values.
• parse_error: The error set of the package's text parser, one tag per kind of bad input.
• domain: The rules for a type whose values a host program embeds inside data values, and one such type that carries nothing.
• packed_constants: The tag bytes of the binary syntax, one per kind of value, plus the end marker.
• text: A text syntax for values, with two readers and two writers.
• packed_reader: Reads one value back from its binary encoding.
• packed_writer: Writes values as bytes in a binary encoding.
• atom: A copy of one atom, taken out of a value, records whether its holder owns the bytes behind it.
• @"packed": A binary encoding of values: a writer that turns a value into bytes, and a reader that turns bytes back into one value under limits the caller sets.
• value: One type holds every data value: atoms, compounds and embedded values of the host program.
• predicates: Predicates that test a value's shape.
• ownership: Calls that copy a whole value tree and free one, each by the rule that matches how the tree was built.
• containers: A hash map and a hash set keyed by the package's values.
• embedded_mod: An embedded value points to a payload of the host program and carries optional functions to compare, hash, free and copy it.
• constructors_mod: Each function here builds one value from Zig data in a single call.
• json: Converts the package's values to JSON text, and JSON text back to values.
• patterns_mod: Converts patterns between their in-memory form and a wire form made of plain records, reads the pattern and the observer out of a record that asks to observe a pattern, and walks the embedded values in a value.
• records_mod: Builders for ten kinds of record, each with a fixed label and a fixed number of fields.

Values and defaults

Public values and defaults.

• any_constructors: The constructors for values whose embedded values hold any pointer (AnyEmbedded).
• any_conversions: The pattern conversions for values whose embedded values hold any pointer (AnyEmbedded).
• any_records: The protocol record builders for values whose embedded values hold any pointer (AnyEmbedded).
• constructors: The constructors for Value(NoEmbedded).
• conversions: The pattern conversions for Value(NoEmbedded).
• records: The protocol record builders for Value(NoEmbedded).
• bindVal: Makes a bind that gives the pattern inner the name name.
• boolean: Makes a boolean value from v.
• capture: Makes a capture of the pattern inner.
• dictionary: Makes a dictionary holding a copy of the slice entries, sorted in ascending order of their keys under compare.
• discard: Makes the discard pattern, written <_> in text.
• embedded: Makes an embedded value that points to the payload ptr.
• entityRuntimeRecord: Builds the record <EntityRuntime kind observe during>, with its three fields in that order, for values whose domain is AnyEmbedded.
• float: Makes a double value from v.
• integer: Makes an integer value from the signed 64-bit v.
• null_val: Makes the symbol null, which the JSON codec reads and writes as JSON null.
• observeRecord: Builds the record <Observe pattern observer> for values whose domain is AnyEmbedded.
• reactorErrorRecord: Builds the record <ReactorError stage facet reactor err>, with its four fields in that order, for values whose domain is AnyEmbedded.
• record: Makes a record with label label and fields fields.
• requireServiceRecord: Builds the record <RequireService name> for values whose domain is AnyEmbedded.
• restPattern: Makes a rest pattern from the patterns prefix for the first items and the pattern rest for the items after them.
• restartServiceRecord: Builds the record <RestartService name> for values whose domain is AnyEmbedded.
• runServiceRecord: Builds the record <RunService name> for values whose domain is AnyEmbedded.
• sequence: Makes a sequence holding a copy of the slice items.
• serviceDependencyRecord: Builds the record <ServiceDependency depender dependee> for values whose domain is AnyEmbedded.
• serviceObjectRecord: Builds the record <ServiceObject name obj> for values whose domain is AnyEmbedded.
• serviceStateRecord: Builds the record <ServiceState name state> for values whose domain is AnyEmbedded.
• set: Makes a set holding a copy of the slice items, sorted in ascending order under compare.
• string: Makes a string value that points at the caller's bytes s.
• symbol: Makes a symbol value that points at the caller's bytes name.
• syncedRecord: Builds the record <Synced>, which has no fields, for values whose domain is AnyEmbedded.

Code relationships

Direct static dependencies extracted from parsed source by semantic graph analysis.

Uses: tiny.hypothesis, tiny.peer, tiny.profiling, tiny.python, tiny.sql
Used by: tiny.choir, tiny.smg

Verification

No verification records are cataloged for this module in this build.

Audit