lib/preserves/src/root.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 //! Two programs that exchange structured data have to agree on what a value is and when two values
  2 //! are the same, whichever encoding carried them. The package gives Zig programs one model of such
  3 //! data, with patterns written over its values and serialization that needs no schema. A value is
  4 //! an atom, a compound, or an embedded value that the host program supplies. The atoms are
  5 //! booleans, doubles, integers of any size, strings, byte strings and symbols. The compounds are
  6 //! records, sequences, sets and dictionaries. A record is a label with a list of fields. Values
  7 //! travel in a text syntax, in a compact binary syntax, and as JSON.
  8 //!
  9 //! Two copies of one value have to be equal, sort to the same place and hash alike, so a value can
 10 //! key a hash map and sort the same way in every program. A set or a dictionary has no order of its
 11 //! own, so the order of its storage must leave equality, order and hash unchanged. A set holds each
 12 //! element once and a dictionary holds each key once, so reading or writing data that repeats one
 13 //! has to fail. A program has to know which memory each value owns and which call frees it.
 14 //!
 15 //! Sets arrive in any order: a program builds them by hand, and a text document lists elements in
 16 //! the order its author wrote them. Comparing or hashing two sets element by element needs both in
 17 //! sorted order, and sorting a copy would allocate memory on every call. Embedded values belong to
 18 //! the host program, so the package has no way to compare, hash, free or copy them by itself.
 19 //! Integers in these values can exceed the range of every fixed-width Zig integer. A tree of values
 20 //! can mix bytes it owns with bytes it borrows, and freeing the tree then depends on knowing which
 21 //! is which. A Lean model of parser results proves that when a borrowed symbol and an owned symbol
 22 //! look the same, no single cleanup frees exactly the owned bytes of both.
 23 //!
 24 //! The package implements the [Preserves](https://preserves.dev/) data language, which Tony
 25 //! Garnock-Jones and the Preserves contributors designed for the Syndicate ecosystem. A second
 26 //! source is Garnock-Jones's dissertation [Conversational
 27 //! Concurrency](https://syndicate-lang.org/tonyg-dissertation/html/). From these sources the
 28 //! package keeps the Preserves values, the patterns that match them, and the text, binary and JSON
 29 //! representations. The Preserves specification treats sets and dictionaries as unordered, requires
 30 //! distinct elements and keys, and compares two of them through their elements in ascending order.
 31 //! The specification's binary syntax writes set elements and dictionary keys sorted by their
 32 //! encoded bytes. The package follows both rules: its comparison reads sets and dictionaries in
 33 //! ascending order, and its binary writer sorts by encoded bytes.
 34 //!
 35 //! The package changes two things so that it fits explicit memory management: the caller owns and
 36 //! frees all storage, and the binary and text decoders run within explicit limits. Every call that
 37 //! allocates takes an allocator from the caller, and the caller frees what the call returns. The
 38 //! binary decoder takes caller-set limits on nesting depth, value count, collection size and
 39 //! retained bytes. Both text decoders stop at 256 levels of nesting. One generic type, `Value`,
 40 //! holds every value. That type takes the type of its embedded values (*domain*) as a parameter,
 41 //! which also supplies their equality, order, cleanup and copy. `assertIsDomain` stops compilation
 42 //! when a type lacks one of those four functions. Two domains ship with the package. `NoEmbedded`
 43 //! has one value, and that value carries no data. `AnyEmbedded` points to a payload of the host
 44 //! program and carries optional functions to compare, hash, free and copy it. Custom equality,
 45 //! hashing and ordering for `AnyEmbedded` payloads come as one table of functions (`SemanticOps`).
 46 //! Two payloads are equal only when they share that table. The table's order must be total, its
 47 //! equality must hold exactly when the order returns `.eq`, and equal payloads must hash equally.
 48 //! An embedded value with no table compares and hashes by the address of its payload.
 49 //!
 50 //! `Value` also holds four kinds of pattern (*pattern form*) beside the data: a discard, a capture
 51 //! of an inner pattern, a bind that gives an inner pattern a name, and a rest pattern that holds a
 52 //! sequence prefix and one pattern for the items after it. So one type carries both data and the
 53 //! patterns written over it. The JSON codec is the one codec that writes the four kinds of pattern
 54 //! and reads them back as patterns. The binary writer and `text.encode` refuse a pattern with
 55 //! `error.PatternFormNotEncodable`. `toText` prints a pattern in its record form, and the text
 56 //! readers read that text back as plain data. The package stores patterns and converts them to and
 57 //! from records, and it runs no match itself. Pattern forms order after every data kind.
 58 //!
 59 //! Equality, order and hash read every set and dictionary in ascending order under `compare`,
 60 //! whatever the order of its storage. That walk allocates nothing, and it finds each next element
 61 //! by scanning the whole set, so its cost grows with the square of the set's size. A Lean model
 62 //! proves that sorted copies of two sets are equal exactly when their elements are permutations of
 63 //! each other. The same model proves that every observation of a sorted copy gives one answer for
 64 //! all such permutations. The `set` and `dictionary` constructors and every codec reject two equal
 65 //! set elements or two equal dictionary keys, on reading and on writing. `Value.initSet` and
 66 //! `Value.initDictionary` store the caller's slice unchecked. The binary writer emits set elements
 67 //! and dictionary keys sorted by their encoded bytes, and the binary reader rejects any other
 68 //! order.
 69 //!
 70 //! Every decoder copies the bytes it reads, so a decoded value owns all its storage and stays valid
 71 //! after the input is freed. `Value.deinit` frees a decoded value. A value built by hand can
 72 //! borrow: `string` and `symbol` keep the caller's slice, and `record`, `sequence`, `set` and
 73 //! `dictionary` copy only the outer slice. Three calls free a value, one for each kind of
 74 //! ownership. `Value.deinit` frees a tree that owns every byte. `freeValueDeep` frees the compound
 75 //! storage of a tree and leaves its string, byte-string and symbol bytes. `freeValue` frees only
 76 //! the outer storage of one compound. `cloneValueDeep` copies a tree into new storage that owns
 77 //! every byte, and `Value.deinit` frees the copy. A `SignedInteger` holds an integer in 128 signed
 78 //! bits when it fits, in 128 unsigned bits when it is larger but still fits, and otherwise as its
 79 //! shortest big-endian two's-complement bytes.
 80 //!
 81 //! The functions at the package root work on values whose domain is `AnyEmbedded`, the domain that
 82 //! `parse` and the JSON codec produce. The namespaces group the package: `value`, `atom`,
 83 //! `integer_mod`, `domain`, `embedded_mod` and `ownership` hold the value model. Beside them,
 84 //! `symbols`, `constructors_mod`, `records_mod`, `predicates`, `patterns_mod` and `containers`
 85 //! build and inspect values. `parse_error` names the text parser's errors, and `text`, `packed` and
 86 //! `json` are the codecs.
 87 //!
 88 //! ```zig
 89 //! const preserves = @import("preserves");
 90 //!
 91 //! const fields = [_]preserves.Value(preserves.Embedded){
 92 //!     preserves.string("world"),
 93 //! };
 94 //! const greeting = try preserves.record(
 95 //!     allocator,
 96 //!     preserves.symbol("greet"),
 97 //!     &fields,
 98 //! );
 99 //! defer preserves.freeValue(allocator, greeting);
100 //!
101 //! const text = try preserves.toText(allocator, greeting);
102 //! defer allocator.free(text);
103 //! ```
104 
105 pub const integer_mod = @import("integer.zig");
106 pub const atom = @import("atom.zig");
107 pub const domain = @import("domain.zig");
108 pub const value = @import("value.zig");
109 pub const symbols = @import("symbols.zig");
110 pub const embedded_mod = @import("embedded.zig");
111 pub const containers = @import("containers.zig");
112 pub const parse_error = @import("error.zig");
113 pub const constructors_mod = @import("constructors.zig");
114 pub const ownership = @import("ownership.zig");
115 pub const predicates = @import("predicates.zig");
116 pub const records_mod = @import("records.zig");
117 pub const patterns_mod = @import("patterns.zig");
118 pub const @"packed" = @import("packed/root.zig");
119 pub const text = @import("text/root.zig");
120 pub const packed_writer = @"packed".writer;
121 pub const packed_reader = @"packed".reader;
122 pub const packed_constants = @"packed".constants;
123 pub const text_writer = text.writer;
124 pub const text_reader = text.reader;
125 pub const json = @import("json.zig");
126 const any = @import("any.zig");
127 
128 pub const SignedInteger = integer_mod.SignedInteger;
129 pub const AtomClass = atom.AtomClass;
130 pub const Atom = atom.Atom;
131 pub const CowBytes = atom.CowBytes;
132 pub const CowSignedInteger = atom.CowSignedInteger;
133 pub const Ownership = atom.Ownership;
134 pub const NoEmbedded = domain.NoEmbedded;
135 pub const assertIsDomain = domain.assertIsDomain;
136 pub const CompoundClass = value.CompoundClass;
137 pub const PatternFormClass = value.PatternFormClass;
138 pub const ValueKind = value.ValueKind;
139 pub const ValueKindTag = value.ValueKindTag;
140 pub const Value = value.Value;
141 pub const Symbol = symbols.Symbol;
142 pub const SYM_OBSERVE = symbols.SYM_OBSERVE;
143 pub const SYM_SYNCED = symbols.SYM_SYNCED;
144 pub const SYM_REQUIRE_SERVICE = symbols.SYM_REQUIRE_SERVICE;
145 pub const SYM_RUN_SERVICE = symbols.SYM_RUN_SERVICE;
146 pub const SYM_SERVICE_STATE = symbols.SYM_SERVICE_STATE;
147 pub const SYM_SERVICE_OBJECT = symbols.SYM_SERVICE_OBJECT;
148 pub const SYM_REACTOR_ERROR = symbols.SYM_REACTOR_ERROR;
149 pub const SYM_ENTITY_RUNTIME = symbols.SYM_ENTITY_RUNTIME;
150 pub const SYM_SERVICE_DEPENDENCY = symbols.SYM_SERVICE_DEPENDENCY;
151 pub const SYM_RESTART_SERVICE = symbols.SYM_RESTART_SERVICE;
152 pub const SYM_NULL = symbols.SYM_NULL;
153 pub const SYM_DISCARD = symbols.SYM_DISCARD;
154 pub const SYM_BIND_PAT = symbols.SYM_BIND_PAT;
155 pub const SYM_LIT = symbols.SYM_LIT;
156 pub const SYM_GROUP = symbols.SYM_GROUP;
157 pub const SYM_REC = symbols.SYM_REC;
158 pub const SYM_ARR = symbols.SYM_ARR;
159 pub const SYM_DICT = symbols.SYM_DICT;
160 pub const AnyEmbedded = embedded_mod.AnyEmbedded;
161 pub const SemanticOps = embedded_mod.SemanticOps;
162 pub const parsedEmbeddedOps = embedded_mod.parsedEmbeddedOps;
163 pub const ParseError = parse_error.ParseError;
164 pub const Constructors = constructors_mod.Constructors;
165 pub const constructors = constructors_mod.constructors;
166 pub const any_constructors = constructors_mod.any_constructors;
167 
168 const AnyValue = any.AnyValue;
169 
170 pub const DictEntry = any.DictEntry;
171 pub const Record = any.Record;
172 pub const Dictionary = any.Dictionary;
173 pub const Embedded = any.Embedded;
174 pub const Capture = any.Capture;
175 pub const Bind = any.Bind;
176 pub const RestPattern = any.RestPattern;
177 
178 pub const ValueContext = any.ValueContext;
179 pub const ValueHashMap = any.ValueHashMap;
180 pub const ValueSet = any.ValueSet;
181 
182 pub const valueEqual = any.valueEqual;
183 pub const valueHash = any.valueHash;
184 pub const valueCompare = any.valueCompare;
185 pub const freeValue = any.freeValue;
186 pub const freeValueDeep = any.freeValueDeep;
187 pub const cloneValueDeep = any.cloneValueDeep;
188 
189 pub const boolean = any.boolean;
190 pub const integer = any.integer;
191 pub const float = any.float;
192 pub const string = any.string;
193 pub const symbol = any.symbol;
194 pub const discard = any.discard;
195 pub const null_val = any.null_val;
196 pub const record = any.record;
197 pub const sequence = any.sequence;
198 pub const set = any.set;
199 pub const dictionary = any.dictionary;
200 pub const capture = any.capture;
201 pub const bindVal = any.bindVal;
202 pub const restPattern = any.restPattern;
203 pub const embedded = any.embedded;
204 
205 pub const recordAttributes = any.recordAttributes;
206 pub const isRecord = any.isRecord;
207 pub const isObserve = any.isObserve;
208 pub const isEmbedded = any.isEmbedded;
209 pub const isSymbol = any.isSymbol;
210 pub const isNull = any.isNull;
211 pub const isCompound = any.isCompound;
212 pub const isPatternForm = any.isPatternForm;
213 pub const isAtom = any.isAtom;
214 pub const symbolEql = any.symbolEql;
215 
216 pub const Records = records_mod.Records;
217 pub const records = records_mod.records;
218 pub const any_records = records_mod.any_records;
219 pub const Conversions = patterns_mod.Conversions;
220 pub const conversions = patterns_mod.conversions;
221 pub const any_conversions = patterns_mod.any_conversions;
222 
223 pub const preserve = any.preserve;
224 pub const preservePattern = any.preservePattern;
225 pub const patternToPreserves = any.patternToPreserves;
226 pub const preservesToPattern = any.preservesToPattern;
227 pub const observeObserver = any.observeObserver;
228 pub const observePattern = any.observePattern;
229 pub const foreachEmbedded = any.foreachEmbedded;
230 pub const mapEmbedded = any.mapEmbedded;
231 
232 /// Builds the record `<Observe pattern observer>` for values whose domain is `AnyEmbedded`. Code
233 /// that asks for matches of a pattern calls it for a record with its label spelled once, in
234 /// `symbols`. The label is a new copy of the symbol `Observe`. An observer other than an embedded
235 /// value moves into a new allocation. The record then holds that observer as an embedded value that
236 /// compares, hashes, frees and copies it as a value. An observer that is already an embedded value
237 /// goes into the record unchanged. The record takes ownership of the pattern and the observer, so
238 /// `Value.deinit` frees the record with both. On `error.OutOfMemory` the call frees what it
239 /// allocated, and the caller still owns the pattern and the observer.
240 pub const observeRecord = any_records.observeRecord;
241 /// Builds the record `<Synced>`, which has no fields, for values whose domain is `AnyEmbedded`.
242 /// Code that marks a sync point calls it for a record with its label spelled once, in `symbols`.
243 /// The label is a new copy of the symbol `Synced`. `Value.deinit` frees the record. On
244 /// `error.OutOfMemory` the call frees what it allocated.
245 pub const syncedRecord = any_records.syncedRecord;
246 /// Builds the record `<RequireService name>` for values whose domain is `AnyEmbedded`. Code that
247 /// asks for a service calls it for a record with its label spelled once, in `symbols`. The label is
248 /// a new copy of the symbol `RequireService`. The record takes ownership of `name`, so
249 /// `Value.deinit` frees the record with it. On `error.OutOfMemory` the call frees what it
250 /// allocated, and the caller still owns `name`.
251 pub const requireServiceRecord = any_records.requireServiceRecord;
252 /// Builds the record `<RunService name>` for values whose domain is `AnyEmbedded`. Code that
253 /// reports a running service calls it for a record with its label spelled once, in `symbols`. The
254 /// label is a new copy of the symbol `RunService`. The record takes ownership of `name`, so
255 /// `Value.deinit` frees the record with it. On `error.OutOfMemory` the call frees what it
256 /// allocated, and the caller still owns `name`.
257 pub const runServiceRecord = any_records.runServiceRecord;
258 /// Builds the record `<ServiceState name state>` for values whose domain is `AnyEmbedded`. Code
259 /// that reports a service's state calls it for a record with its label spelled once, in `symbols`.
260 /// The label is a new copy of the symbol `ServiceState`. The record takes ownership of `name` and
261 /// `state`, so `Value.deinit` frees the record with both. On `error.OutOfMemory` the call frees
262 /// what it allocated, and the caller still owns `name` and `state`.
263 pub const serviceStateRecord = any_records.serviceStateRecord;
264 /// Builds the record `<ServiceObject name obj>` for values whose domain is `AnyEmbedded`. Code that
265 /// publishes a service's object calls it for a record with its label spelled once, in `symbols`.
266 /// The label is a new copy of the symbol `ServiceObject`. The record takes ownership of `name` and
267 /// `obj`, so `Value.deinit` frees the record with both. On `error.OutOfMemory` the call frees what
268 /// it allocated, and the caller still owns `name` and `obj`.
269 pub const serviceObjectRecord = any_records.serviceObjectRecord;
270 /// Builds the record `<ReactorError stage facet reactor err>`, with its four fields in that order,
271 /// for values whose domain is `AnyEmbedded`. Code that reports a failed reactor calls it for a
272 /// record with its label spelled once, in `symbols`. The label is a new copy of the symbol
273 /// `ReactorError`. The record takes ownership of the four field values, so `Value.deinit` frees the
274 /// record with them. On `error.OutOfMemory` the call frees what it allocated, and the caller still
275 /// owns the four field values.
276 pub const reactorErrorRecord = any_records.reactorErrorRecord;
277 /// Builds the record `<EntityRuntime kind observe during>`, with its three fields in that order,
278 /// for values whose domain is `AnyEmbedded`. Code that describes a running entity calls it for a
279 /// record with its label spelled once, in `symbols`. The label is a new copy of the symbol
280 /// `EntityRuntime`. The record takes ownership of the three field values, so `Value.deinit` frees
281 /// the record with them. On `error.OutOfMemory` the call frees what it allocated, and the caller
282 /// still owns the three field values.
283 pub const entityRuntimeRecord = any_records.entityRuntimeRecord;
284 /// Builds the record `<ServiceDependency depender dependee>` for values whose domain is
285 /// `AnyEmbedded`. Code that records that one service needs another calls it for a record with its
286 /// label spelled once, in `symbols`. The label is a new copy of the symbol `ServiceDependency`. The
287 /// record takes ownership of `depender` and `dependee`, so `Value.deinit` frees the record with
288 /// both. On `error.OutOfMemory` the call frees what it allocated, and the caller still owns
289 /// `depender` and `dependee`.
290 pub const serviceDependencyRecord = any_records.serviceDependencyRecord;
291 /// Builds the record `<RestartService name>` for values whose domain is `AnyEmbedded`. Code that
292 /// asks for a restart calls it for a record with its label spelled once, in `symbols`. The label is
293 /// a new copy of the symbol `RestartService`. The record takes ownership of `name`, so
294 /// `Value.deinit` frees the record with it. On `error.OutOfMemory` the call frees what it
295 /// allocated, and the caller still owns `name`.
296 pub const restartServiceRecord = any_records.restartServiceRecord;
297 pub const PackedTag = @"packed".Tag;
298 pub const encodePacked = @"packed".encode;
299 pub const decodePacked = @"packed".decode;
300 pub const encodeText = text.encode;
301 pub const decodeText = text.decode;
302 pub const toText = text.toText;
303 pub const parse = text.parse;
304 pub const toJsonString = json.toJsonString;
305 pub const fromJsonString = json.fromJsonString;
306 pub const fromJsonValue = json.fromJsonValue;