yo_shape/
desc.rs

1//! The canonical description and the tag over it (`15` section 3.1).
2
3use core::fmt;
4
5use yo_common::blake3;
6
7/// The primitives. Every one of them says its width, because "int" means a
8/// different number of bytes in every language that will open the file.
9#[derive(Debug, Clone, Copy, PartialEq, Eq)]
10pub enum Prim {
11    /// An unsigned byte.
12    U8,
13    /// An unsigned 16 bit integer.
14    U16,
15    /// An unsigned 32 bit integer.
16    U32,
17    /// An unsigned 64 bit integer.
18    U64,
19    /// A signed byte.
20    I8,
21    /// A signed 16 bit integer.
22    I16,
23    /// A signed 32 bit integer.
24    I32,
25    /// A signed 64 bit integer.
26    I64,
27    /// A 32 bit float.
28    F32,
29    /// A 64 bit float.
30    F64,
31    /// A boolean.
32    Bool,
33    /// UTF-8 text.
34    Str,
35    /// Bytes with no encoding attached.
36    Bytes,
37}
38
39impl Prim {
40    /// The token this primitive is written as.
41    #[must_use]
42    pub const fn token(self) -> &'static str {
43        match self {
44            Prim::U8 => "u8",
45            Prim::U16 => "u16",
46            Prim::U32 => "u32",
47            Prim::U64 => "u64",
48            Prim::I8 => "i8",
49            Prim::I16 => "i16",
50            Prim::I32 => "i32",
51            Prim::I64 => "i64",
52            Prim::F32 => "f32",
53            Prim::F64 => "f64",
54            Prim::Bool => "bool",
55            Prim::Str => "str",
56            Prim::Bytes => "bytes",
57        }
58    }
59
60    /// Every token. No token is a prefix of another, so a parser can try them
61    /// in any order and still read a description exactly one way.
62    pub(crate) const ALL: &'static [Prim] = &[
63        Prim::Bytes,
64        Prim::Bool,
65        Prim::Str,
66        Prim::U8,
67        Prim::U16,
68        Prim::U32,
69        Prim::U64,
70        Prim::I8,
71        Prim::I16,
72        Prim::I32,
73        Prim::I64,
74        Prim::F32,
75        Prim::F64,
76    ];
77}
78
79impl fmt::Display for Prim {
80    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
81        f.write_str(self.token())
82    }
83}
84
85/// How a vector is compared. Part of the shape because a collection built for
86/// cosine and searched as if it were L2 gives wrong answers quietly.
87#[derive(Debug, Clone, Copy, PartialEq, Eq)]
88pub enum Metric {
89    /// Euclidean distance.
90    L2,
91    /// Cosine similarity.
92    Cosine,
93    /// Inner product.
94    Ip,
95    /// Hamming distance, for binary vectors.
96    Hamming,
97}
98
99impl Metric {
100    /// The name this metric is written as.
101    #[must_use]
102    pub const fn token(self) -> &'static str {
103        match self {
104            Metric::L2 => "l2",
105            Metric::Cosine => "cosine",
106            Metric::Ip => "ip",
107            Metric::Hamming => "hamming",
108        }
109    }
110}
111
112impl fmt::Display for Metric {
113    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
114        f.write_str(self.token())
115    }
116}
117
118/// What a type contributes to a description.
119///
120/// A plain function pointer rather than a closure, so that a struct's field
121/// list is a constant slice and the field count can never disagree with the
122/// number of fields written.
123pub type Describe = fn(&mut Desc);
124
125/// A type that can describe itself.
126///
127/// The description is the type's identity in the file, so two types that
128/// describe themselves the same way are the same type as far as `yo` is
129/// concerned, whatever they are called in the host language.
130pub trait Shape {
131    /// Write this type into the description being built.
132    fn describe(d: &mut Desc);
133}
134
135/// A canonical description, built by writing and read as bytes.
136///
137/// The bytes are the whole point: they are what gets stored, what gets hashed
138/// into the [`Tag`], and what a binding in another language has to produce
139/// exactly. Nothing here depends on Rust.
140#[derive(Debug, Clone, Default, PartialEq, Eq)]
141pub struct Desc {
142    bytes: Vec<u8>,
143    /// Ranges into `bytes` naming the structs currently being written, so that
144    /// a type that contains itself writes a reference instead of recursing
145    /// until the stack runs out.
146    open: Vec<(usize, usize)>,
147}
148
149impl Desc {
150    /// An empty description.
151    #[must_use]
152    pub fn new() -> Desc {
153        Desc {
154            bytes: Vec::new(),
155            open: Vec::new(),
156        }
157    }
158
159    /// The description of `T`.
160    #[must_use]
161    pub fn of<T: Shape + ?Sized>() -> Desc {
162        let mut d = Desc::new();
163        T::describe(&mut d);
164        d
165    }
166
167    /// A description someone else produced, from the catalogue or the wire.
168    #[must_use]
169    pub fn from_bytes(bytes: impl Into<Vec<u8>>) -> Desc {
170        Desc {
171            bytes: bytes.into(),
172            open: Vec::new(),
173        }
174    }
175
176    /// The bytes, which are what gets stored.
177    #[must_use]
178    pub fn as_bytes(&self) -> &[u8] {
179        &self.bytes
180    }
181
182    /// The description as text, for a message or a log line. It is all ASCII
183    /// apart from names, which are UTF-8, so this never fails in practice.
184    #[must_use]
185    pub fn as_text(&self) -> String {
186        String::from_utf8_lossy(&self.bytes).into_owned()
187    }
188
189    /// The tag: the first 128 bits of the BLAKE3 hash of these bytes.
190    #[must_use]
191    pub fn tag(&self) -> Tag {
192        Tag::of(&self.bytes)
193    }
194
195    /// Whether anything has been written.
196    #[must_use]
197    pub fn is_empty(&self) -> bool {
198        self.bytes.is_empty()
199    }
200
201    /// A primitive.
202    pub fn prim(&mut self, p: Prim) {
203        self.bytes.extend_from_slice(p.token().as_bytes());
204    }
205
206    /// An optional value.
207    pub fn optional(&mut self, inner: Describe) {
208        self.bytes.push(b'O');
209        inner(self);
210    }
211
212    /// A sequence.
213    pub fn list(&mut self, inner: Describe) {
214        self.bytes.push(b'L');
215        inner(self);
216    }
217
218    /// A mapping, key type then value type.
219    pub fn map(&mut self, key: Describe, value: Describe) {
220        self.bytes.push(b'M');
221        key(self);
222        value(self);
223    }
224
225    /// A vector of `dim` dimensions compared with `metric`.
226    pub fn vector(&mut self, dim: u32, metric: Metric) {
227        self.bytes.push(b'V');
228        self.varint(dim);
229        self.name(metric.token());
230    }
231
232    /// A named reference, which is what a recursive type writes on the way
233    /// down. Written for you by [`Desc::strukt`]; call it directly only when
234    /// building a description by hand.
235    pub fn reference(&mut self, name: &str) {
236        self.bytes.push(b'R');
237        self.name(name);
238    }
239
240    /// A struct, with its fields in declaration order.
241    ///
242    /// Order is layout, so it is part of the shape and reordering fields is a
243    /// breaking change (`15` section 5). That is why this takes a slice rather
244    /// than a map.
245    ///
246    /// If `name` is already being written further up, this writes a reference
247    /// instead and does not descend, which is what makes a linked list or a
248    /// tree describable at all.
249    pub fn strukt(&mut self, name: &str, fields: &[(&str, Describe)]) {
250        if self.is_open(name) {
251            self.reference(name);
252            return;
253        }
254
255        self.bytes.push(b'S');
256        let at = self.name(name);
257        self.open.push(at);
258        self.varint(len_as_u32(fields.len()));
259        for (field, describe) in fields {
260            self.name(field);
261            describe(self);
262        }
263        self.open.pop();
264    }
265
266    /// An enumeration, with its variants in declaration order.
267    ///
268    /// Variants carry no payload here. A variant that carries data is a struct
269    /// in a field of its own, which is how it has to be written until the
270    /// grammar grows a form for it.
271    pub fn enumeration(&mut self, name: &str, variants: &[&str]) {
272        self.bytes.push(b'E');
273        self.name(name);
274        self.varint(len_as_u32(variants.len()));
275        for variant in variants {
276            self.name(variant);
277        }
278    }
279
280    /// Length prefixed UTF-8, returning where it landed.
281    fn name(&mut self, s: &str) -> (usize, usize) {
282        self.varint(len_as_u32(s.len()));
283        let at = self.bytes.len();
284        self.bytes.extend_from_slice(s.as_bytes());
285        (at, s.len())
286    }
287
288    /// LEB128, because a length has to be one number in every language and a
289    /// fixed width would either waste bytes or cap a name.
290    fn varint(&mut self, mut n: u32) {
291        loop {
292            let byte = (n & 0x7f) as u8;
293            n >>= 7;
294            if n == 0 {
295                self.bytes.push(byte);
296                return;
297            }
298            self.bytes.push(byte | 0x80);
299        }
300    }
301
302    fn is_open(&self, name: &str) -> bool {
303        self.open
304            .iter()
305            .any(|&(at, len)| &self.bytes[at..at + len] == name.as_bytes())
306    }
307}
308
309/// A name or a count that does not fit in 32 bits is a bug in the caller, not
310/// a case to handle. Saturating keeps the description well formed either way.
311fn len_as_u32(n: usize) -> u32 {
312    u32::try_from(n).unwrap_or(u32::MAX)
313}
314
315/// The 128 bit shape tag.
316///
317/// Half of a BLAKE3 hash, which is enough: the tag is compared, never searched
318/// for, and a collision would need two descriptions someone deliberately built
319/// to collide.
320#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
321pub struct Tag([u8; 16]);
322
323impl Tag {
324    /// The tag of a collection created over the wire, which has no type.
325    pub const UNTYPED: Tag = Tag([0; 16]);
326
327    /// The tag of these description bytes.
328    #[must_use]
329    pub fn of(description: &[u8]) -> Tag {
330        let full = blake3::hash(description);
331        let mut tag = [0u8; 16];
332        tag.copy_from_slice(&full[..16]);
333        Tag(tag)
334    }
335
336    /// The tag of `T`, which is the call a typed handle makes when it opens.
337    #[must_use]
338    pub fn for_type<T: Shape + ?Sized>() -> Tag {
339        Desc::of::<T>().tag()
340    }
341
342    /// The bytes as stored in the catalogue.
343    #[must_use]
344    pub const fn as_bytes(&self) -> &[u8; 16] {
345        &self.0
346    }
347
348    /// A tag read back out of the catalogue.
349    #[must_use]
350    pub const fn from_bytes(bytes: [u8; 16]) -> Tag {
351        Tag(bytes)
352    }
353
354    /// Whether this is the untyped tag, meaning the collection was created
355    /// over RESP3 and is checked per element instead (`15` section 3.3).
356    #[must_use]
357    pub fn is_untyped(&self) -> bool {
358        self.0 == [0; 16]
359    }
360}
361
362impl fmt::Display for Tag {
363    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
364        f.write_str(&blake3::to_hex(&self.0))
365    }
366}
367
368macro_rules! prim_shape {
369    ($($t:ty => $p:expr),* $(,)?) => {
370        $(impl Shape for $t {
371            fn describe(d: &mut Desc) {
372                d.prim($p);
373            }
374        })*
375    };
376}
377
378prim_shape! {
379    u8 => Prim::U8,
380    u16 => Prim::U16,
381    u32 => Prim::U32,
382    u64 => Prim::U64,
383    i8 => Prim::I8,
384    i16 => Prim::I16,
385    i32 => Prim::I32,
386    i64 => Prim::I64,
387    f32 => Prim::F32,
388    f64 => Prim::F64,
389    bool => Prim::Bool,
390    str => Prim::Str,
391    String => Prim::Str,
392}
393
394/// Raw bytes, for a field that holds a blob rather than text or a list.
395///
396/// `Vec<u8>` describes as a list of `u8`, which is a different shape and a
397/// different layout, so a field that means "bytes" says so with this.
398#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
399pub struct Bytes;
400
401impl Shape for Bytes {
402    fn describe(d: &mut Desc) {
403        d.prim(Prim::Bytes);
404    }
405}
406
407impl<T: Shape> Shape for Option<T> {
408    fn describe(d: &mut Desc) {
409        d.optional(T::describe);
410    }
411}
412
413impl<T: Shape> Shape for Vec<T> {
414    fn describe(d: &mut Desc) {
415        d.list(T::describe);
416    }
417}
418
419impl<T: Shape> Shape for [T] {
420    fn describe(d: &mut Desc) {
421        d.list(T::describe);
422    }
423}
424
425impl<T: Shape, const N: usize> Shape for [T; N] {
426    fn describe(d: &mut Desc) {
427        d.list(T::describe);
428    }
429}
430
431impl<T: Shape + ?Sized> Shape for &T {
432    fn describe(d: &mut Desc) {
433        T::describe(d);
434    }
435}
436
437impl<T: Shape + ?Sized> Shape for Box<T> {
438    fn describe(d: &mut Desc) {
439        T::describe(d);
440    }
441}
442
443impl<K: Shape, V: Shape> Shape for std::collections::BTreeMap<K, V> {
444    fn describe(d: &mut Desc) {
445        d.map(K::describe, V::describe);
446    }
447}
448
449impl<K: Shape, V: Shape, S> Shape for std::collections::HashMap<K, V, S> {
450    fn describe(d: &mut Desc) {
451        d.map(K::describe, V::describe);
452    }
453}
454
455#[cfg(test)]
456mod tests {
457    use super::*;
458
459    #[test]
460    fn primitives_write_their_own_token() {
461        assert_eq!(Desc::of::<u64>().as_text(), "u64");
462        assert_eq!(Desc::of::<i8>().as_text(), "i8");
463        assert_eq!(Desc::of::<f32>().as_text(), "f32");
464        assert_eq!(Desc::of::<bool>().as_text(), "bool");
465        assert_eq!(Desc::of::<String>().as_text(), "str");
466        assert_eq!(Desc::of::<Bytes>().as_text(), "bytes");
467    }
468
469    #[test]
470    fn containers_nest_left_to_right() {
471        assert_eq!(Desc::of::<Option<u32>>().as_text(), "Ou32");
472        assert_eq!(Desc::of::<Vec<Option<i64>>>().as_text(), "LOi64");
473        assert_eq!(
474            Desc::of::<std::collections::BTreeMap<String, Vec<u8>>>().as_text(),
475            "MstrLu8"
476        );
477    }
478
479    /// A borrow and a box describe as the thing they hold, because the file
480    /// does not know what a pointer is.
481    #[test]
482    fn indirection_is_not_part_of_the_shape() {
483        assert_eq!(Desc::of::<Box<u64>>(), Desc::of::<u64>());
484        assert_eq!(Desc::of::<&str>(), Desc::of::<String>());
485        assert_eq!(Desc::of::<[u16; 4]>(), Desc::of::<Vec<u16>>());
486    }
487
488    fn order(d: &mut Desc) {
489        d.strukt("Order", &[("id", u64::describe), ("total", f64::describe)]);
490    }
491
492    #[test]
493    fn a_struct_writes_its_name_then_its_fields_in_order() {
494        let mut d = Desc::new();
495        order(&mut d);
496        assert_eq!(d.as_text(), "S\u{5}Order\u{2}\u{2}idu64\u{5}totalf64");
497    }
498
499    /// The one that matters most, because it is the mistake the tag exists to
500    /// catch and the one a schema tool that sorts field names would miss.
501    #[test]
502    fn reordering_fields_changes_the_tag() {
503        let mut a = Desc::new();
504        a.strukt("P", &[("x", u64::describe), ("y", u64::describe)]);
505        let mut b = Desc::new();
506        b.strukt("P", &[("y", u64::describe), ("x", u64::describe)]);
507        assert_ne!(a.tag(), b.tag());
508    }
509
510    #[test]
511    fn a_widening_changes_the_tag() {
512        let mut a = Desc::new();
513        a.strukt("P", &[("x", u32::describe)]);
514        let mut b = Desc::new();
515        b.strukt("P", &[("x", u64::describe)]);
516        assert_ne!(a.tag(), b.tag());
517        assert_ne!(a.as_bytes(), b.as_bytes());
518    }
519
520    #[test]
521    fn the_same_shape_written_twice_gets_the_same_tag() {
522        let mut a = Desc::new();
523        order(&mut a);
524        let mut b = Desc::new();
525        order(&mut b);
526        assert_eq!(a.tag(), b.tag());
527        assert_eq!(a.tag().to_string().len(), 32);
528    }
529
530    /// A type that contains itself stops at the second mention. Without this
531    /// the describer runs until the stack ends, which is a poor way to learn
532    /// that a tree is a tree.
533    #[test]
534    fn recursion_writes_a_reference() {
535        fn node(d: &mut Desc) {
536            d.strukt("Node", &[("value", u64::describe), ("kids", kids)]);
537        }
538        fn kids(d: &mut Desc) {
539            d.list(node);
540        }
541
542        let mut d = Desc::new();
543        node(&mut d);
544        assert_eq!(
545            d.as_text(),
546            "S\u{4}Node\u{2}\u{5}valueu64\u{4}kidsLR\u{4}Node"
547        );
548    }
549
550    /// Two fields of the same struct type are not recursion and both expand.
551    #[test]
552    fn siblings_of_the_same_type_both_expand() {
553        fn point(d: &mut Desc) {
554            d.strukt("Point", &[("x", f64::describe)]);
555        }
556        let mut d = Desc::new();
557        d.strukt("Line", &[("a", point), ("b", point)]);
558        let text = d.as_text();
559        assert_eq!(text.matches("Point").count(), 2);
560        assert!(!text.contains('R'));
561    }
562
563    #[test]
564    fn an_enum_writes_its_variants_in_order() {
565        let mut d = Desc::new();
566        d.enumeration("Status", &["Open", "Paid"]);
567        assert_eq!(d.as_text(), "E\u{6}Status\u{2}\u{4}Open\u{4}Paid");
568    }
569
570    /// Asserted as bytes rather than as text, because 768 in LEB128 is `80 06`
571    /// and `0x80` is not a character.
572    #[test]
573    fn a_vector_carries_its_dimension_and_metric() {
574        let mut d = Desc::new();
575        d.vector(768, Metric::Cosine);
576        assert_eq!(d.as_bytes(), b"V\x80\x06\x06cosine");
577    }
578
579    /// A name longer than 127 bytes needs two length bytes, which is the only
580    /// interesting thing about LEB128 and the thing a binding gets wrong.
581    #[test]
582    fn a_long_name_gets_a_two_byte_length() {
583        let long = "a".repeat(200);
584        let mut d = Desc::new();
585        d.enumeration(&long, &[]);
586        assert_eq!(d.as_bytes()[1], 0xc8);
587        assert_eq!(d.as_bytes()[2], 0x01);
588        assert_eq!(d.as_bytes().len(), 1 + 2 + 200 + 1);
589    }
590
591    #[test]
592    fn the_untyped_tag_is_zero_and_says_so() {
593        assert!(Tag::UNTYPED.is_untyped());
594        assert_eq!(Tag::UNTYPED.to_string(), "0".repeat(32));
595        assert!(!Tag::for_type::<u64>().is_untyped());
596    }
597
598    /// The tag is the first half of the BLAKE3 hash, and nothing else.
599    #[test]
600    fn the_tag_is_the_first_half_of_the_hash() {
601        let d = Desc::of::<u64>();
602        let full = blake3::hash(d.as_bytes());
603        assert_eq!(d.tag().as_bytes(), &full[..16]);
604        assert_eq!(d.tag().to_string(), blake3::to_hex(&full[..16]));
605        assert_eq!(Tag::from_bytes(*d.tag().as_bytes()), d.tag());
606    }
607}
yo_shape/desc.rs

yo_shape/
desc.rs
