yo_shape/
parse.rs

1//! Reading a description back into a tree.
2//!
3//! Writing a description is the hot side and it is a `Vec<u8>` push. Reading
4//! one happens when a tag comparison already failed, or when a tool wants to
5//! print what is in a file, so this side is written for clarity and for saying
6//! exactly where a description went wrong.
7
8use core::fmt;
9
10use yo_common::{Code, Error, Result};
11
12use crate::desc::{Desc, Metric, Prim};
13
14/// A description, parsed.
15#[derive(Debug, Clone, PartialEq)]
16pub enum Type {
17    /// A primitive.
18    Prim(Prim),
19    /// An optional value.
20    Optional(Box<Type>),
21    /// A sequence.
22    List(Box<Type>),
23    /// A mapping.
24    Map(Box<Type>, Box<Type>),
25    /// A struct with its fields in declaration order.
26    Struct {
27        /// The type's name.
28        name: String,
29        /// Name and type, in declaration order.
30        fields: Vec<(String, Type)>,
31    },
32    /// An enumeration with its variants in declaration order.
33    Enum {
34        /// The type's name.
35        name: String,
36        /// Variant names, in declaration order.
37        variants: Vec<String>,
38    },
39    /// A vector of a fixed width, compared one way.
40    Vector {
41        /// How many dimensions.
42        dim: u32,
43        /// How it is compared. Held as written, because a file may name a
44        /// metric this build has never heard of.
45        metric: String,
46    },
47    /// A reference back to a struct that encloses this one.
48    Ref(String),
49}
50
51impl Type {
52    /// The name, for the types that have one.
53    #[must_use]
54    pub fn name(&self) -> Option<&str> {
55        match self {
56            Type::Struct { name, .. } | Type::Enum { name, .. } | Type::Ref(name) => Some(name),
57            _ => None,
58        }
59    }
60
61    /// What to call this kind of type in a message.
62    #[must_use]
63    pub fn kind(&self) -> &'static str {
64        match self {
65            Type::Prim(_) => "primitive",
66            Type::Optional(_) => "optional",
67            Type::List(_) => "list",
68            Type::Map(_, _) => "map",
69            Type::Struct { .. } => "struct",
70            Type::Enum { .. } => "enum",
71            Type::Vector { .. } => "vector",
72            Type::Ref(_) => "reference",
73        }
74    }
75}
76
77/// Parse a whole description. Trailing bytes are an error, because a
78/// description that is a valid type followed by rubbish is not a description.
79///
80/// # Errors
81///
82/// [`Code::Corrupt`] with the byte offset, for anything that is not a
83/// description this build can read.
84pub fn parse(desc: &Desc) -> Result<Type> {
85    let bytes = desc.as_bytes();
86    let mut p = Parser { bytes, at: 0 };
87    let ty = p.ty()?;
88    if p.at != bytes.len() {
89        return Err(p.bad("trailing bytes after the type"));
90    }
91    Ok(ty)
92}
93
94struct Parser<'a> {
95    bytes: &'a [u8],
96    at: usize,
97}
98
99impl Parser<'_> {
100    fn bad(&self, what: &str) -> Error {
101        Error::fmt(
102            Code::Corrupt,
103            format_args!("shape description is malformed at byte {}: {what}", self.at),
104        )
105        .at(u32::try_from(self.at).unwrap_or(u32::MAX))
106    }
107
108    fn peek(&self) -> Result<u8> {
109        self.bytes
110            .get(self.at)
111            .copied()
112            .ok_or_else(|| self.bad("the description ends here"))
113    }
114
115    fn varint(&mut self) -> Result<u32> {
116        let mut value: u32 = 0;
117        let mut shift = 0;
118        loop {
119            let byte = self.peek()?;
120            self.at += 1;
121            let part = u32::from(byte & 0x7f);
122            value |= part
123                .checked_shl(shift)
124                .ok_or_else(|| self.bad("a length does not fit in 32 bits"))?;
125            if byte & 0x80 == 0 {
126                return Ok(value);
127            }
128            shift += 7;
129            if shift >= 32 {
130                return Err(self.bad("a length does not fit in 32 bits"));
131            }
132        }
133    }
134
135    fn name(&mut self) -> Result<String> {
136        let len = self.varint()? as usize;
137        let end = self
138            .at
139            .checked_add(len)
140            .filter(|&end| end <= self.bytes.len())
141            .ok_or_else(|| self.bad("a name runs past the end"))?;
142        let text = core::str::from_utf8(&self.bytes[self.at..end])
143            .map_err(|_| self.bad("a name is not UTF-8"))?
144            .to_owned();
145        self.at = end;
146        Ok(text)
147    }
148
149    fn ty(&mut self) -> Result<Type> {
150        match self.peek()? {
151            b'O' => {
152                self.at += 1;
153                Ok(Type::Optional(Box::new(self.ty()?)))
154            }
155            b'L' => {
156                self.at += 1;
157                Ok(Type::List(Box::new(self.ty()?)))
158            }
159            b'M' => {
160                self.at += 1;
161                let key = self.ty()?;
162                let value = self.ty()?;
163                Ok(Type::Map(Box::new(key), Box::new(value)))
164            }
165            b'R' => {
166                self.at += 1;
167                Ok(Type::Ref(self.name()?))
168            }
169            b'V' => {
170                self.at += 1;
171                let dim = self.varint()?;
172                let metric = self.name()?;
173                Ok(Type::Vector { dim, metric })
174            }
175            b'S' => {
176                self.at += 1;
177                let name = self.name()?;
178                let count = self.varint()?;
179                let mut fields = Vec::with_capacity(count.min(64) as usize);
180                for _ in 0..count {
181                    let field = self.name()?;
182                    fields.push((field, self.ty()?));
183                }
184                Ok(Type::Struct { name, fields })
185            }
186            b'E' => {
187                self.at += 1;
188                let name = self.name()?;
189                let count = self.varint()?;
190                let mut variants = Vec::with_capacity(count.min(64) as usize);
191                for _ in 0..count {
192                    variants.push(self.name()?);
193                }
194                Ok(Type::Enum { name, variants })
195            }
196            _ => self.prim(),
197        }
198    }
199
200    fn prim(&mut self) -> Result<Type> {
201        let rest = &self.bytes[self.at..];
202        for &p in Prim::ALL {
203            if rest.starts_with(p.token().as_bytes()) {
204                self.at += p.token().len();
205                return Ok(Type::Prim(p));
206            }
207        }
208        Err(self.bad("not a type"))
209    }
210}
211
212/// The metric a parsed vector names, when this build knows it.
213#[must_use]
214pub fn metric_of(name: &str) -> Option<Metric> {
215    [Metric::L2, Metric::Cosine, Metric::Ip, Metric::Hamming]
216        .into_iter()
217        .find(|m| m.token() == name)
218}
219
220impl fmt::Display for Type {
221    /// The rendering used in messages: a struct at the top shows its fields,
222    /// a struct anywhere else shows its name. A shape mismatch message has to
223    /// fit on a terminal and the field that changed is usually near the top.
224    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
225        match self {
226            Type::Struct { name, fields } => {
227                write!(f, "{name} {{ ")?;
228                for (i, (field, ty)) in fields.iter().enumerate() {
229                    if i > 0 {
230                        f.write_str(", ")?;
231                    }
232                    write!(f, "{field}: {}", Inner(ty))?;
233                }
234                f.write_str(" }")
235            }
236            other => write!(f, "{}", Inner(other)),
237        }
238    }
239}
240
241/// A type in field position, where a struct is only its name.
242struct Inner<'a>(&'a Type);
243
244impl fmt::Display for Inner<'_> {
245    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
246        match self.0 {
247            Type::Prim(p) => write!(f, "{p}"),
248            Type::Optional(t) => write!(f, "O {}", Inner(t)),
249            Type::List(t) => write!(f, "L {}", Inner(t)),
250            Type::Map(k, v) => write!(f, "M {} {}", Inner(k), Inner(v)),
251            Type::Struct { name, .. } => f.write_str(name),
252            Type::Enum { name, variants } => {
253                write!(f, "E {name}[{}]", variants.join(","))
254            }
255            Type::Vector { dim, metric } => write!(f, "V {dim} {metric}"),
256            Type::Ref(name) => write!(f, "R {name}"),
257        }
258    }
259}
260
261#[cfg(test)]
262mod tests {
263    use super::*;
264    use crate::desc::{Describe, Shape};
265
266    fn parsed(build: impl FnOnce(&mut Desc)) -> Type {
267        let mut d = Desc::new();
268        build(&mut d);
269        parse(&d).expect("this description was just written")
270    }
271
272    #[test]
273    fn every_primitive_survives_a_round_trip() {
274        for &p in Prim::ALL {
275            let ty = parsed(|d| d.prim(p));
276            assert_eq!(ty, Type::Prim(p), "{p}");
277        }
278    }
279
280    #[test]
281    fn containers_survive_a_round_trip() {
282        assert_eq!(
283            parsed(|d| d.optional(u64::describe)),
284            Type::Optional(Box::new(Type::Prim(Prim::U64)))
285        );
286        assert_eq!(
287            parsed(|d| d.map(String::describe, <Vec<u8> as Shape>::describe)),
288            Type::Map(
289                Box::new(Type::Prim(Prim::Str)),
290                Box::new(Type::List(Box::new(Type::Prim(Prim::U8))))
291            )
292        );
293    }
294
295    #[test]
296    fn a_struct_keeps_its_field_order() {
297        let ty = parsed(|d| {
298            d.strukt(
299                "Order",
300                &[
301                    ("id", u64::describe),
302                    ("note", <Option<String> as Shape>::describe),
303                ],
304            );
305        });
306        let Type::Struct { name, fields } = &ty else {
307            panic!("expected a struct, got {ty:?}");
308        };
309        assert_eq!(name, "Order");
310        assert_eq!(fields[0].0, "id");
311        assert_eq!(fields[1].0, "note");
312        assert_eq!(ty.to_string(), "Order { id: u64, note: O str }");
313    }
314
315    #[test]
316    fn an_enum_keeps_its_variant_order() {
317        let ty = parsed(|d| d.enumeration("Status", &["Open", "Paid", "Shipped"]));
318        assert_eq!(ty.to_string(), "E Status[Open,Paid,Shipped]");
319    }
320
321    #[test]
322    fn a_vector_keeps_its_dimension() {
323        let ty = parsed(|d| d.vector(1536, Metric::Ip));
324        assert_eq!(
325            ty,
326            Type::Vector {
327                dim: 1536,
328                metric: "ip".into()
329            }
330        );
331        assert_eq!(ty.to_string(), "V 1536 ip");
332        assert_eq!(metric_of("ip"), Some(Metric::Ip));
333        assert_eq!(metric_of("euclidean"), None);
334    }
335
336    #[test]
337    fn a_recursive_type_parses_to_a_reference() {
338        fn node(d: &mut Desc) {
339            d.strukt("Node", &[("kids", kids as Describe)]);
340        }
341        fn kids(d: &mut Desc) {
342            d.list(node);
343        }
344        let ty = parsed(node);
345        assert_eq!(ty.to_string(), "Node { kids: L R Node }");
346    }
347
348    /// A nested struct shows as its name, which is what `15` section 3.2's
349    /// example message does.
350    #[test]
351    fn a_nested_struct_renders_as_its_name() {
352        fn line(d: &mut Desc) {
353            d.strukt("Line", &[("sku", String::describe)]);
354        }
355        let ty = parsed(|d| d.strukt("Order", &[("lines", |d: &mut Desc| d.list(line))]));
356        assert_eq!(ty.to_string(), "Order { lines: L Line }");
357    }
358
359    #[test]
360    fn rubbish_is_rejected_with_the_offset() {
361        let bad = Desc::from_bytes(b"u64u64".to_vec());
362        let e = parse(&bad).expect_err("two types in a row is not one type");
363        assert_eq!(e.code(), Code::Corrupt);
364        assert_eq!(e.position(), Some(3));
365
366        for cut in ["S", "S\u{5}Ord", "L", "MstrL", "V\u{80}"] {
367            let e = parse(&Desc::from_bytes(cut.as_bytes().to_vec()))
368                .expect_err("a truncated description is not a description");
369            assert_eq!(e.code(), Code::Corrupt, "{cut:?}");
370        }
371
372        let e = parse(&Desc::from_bytes(b"q".to_vec())).expect_err("q is not a type");
373        assert!(e.message().contains("not a type"), "{e}");
374    }
375
376    /// A count that says more fields than are there fails rather than
377    /// returning half a struct, because half a struct compares as a shape
378    /// change and would send the caller after the wrong bug.
379    #[test]
380    fn a_lying_field_count_is_rejected() {
381        let bad = Desc::from_bytes(b"S\x01P\x02\x01xu64".to_vec());
382        assert_eq!(
383            parse(&bad).expect_err("one field, not two").code(),
384            Code::Corrupt
385        );
386    }
387}
yo_shape/parse.rs

yo_shape/
parse.rs
