lang_forge/
image.rs

1//! The language image (`.lsl`, ISSUES M12): a forged [`Language`] as bytes.
2//!
3//! An image is the forged tables themselves — kinds, lexer, parser tables,
4//! fields, supertypes, injections — so loading one skips forging entirely.
5//! It is deterministic: the same sketch forged by the same lang-forge gives
6//! byte-identical images on every platform and every run (LSF2 §5).
7//!
8//! # Layout
9//!
10//! ```text
11//! magic     4 bytes   "LSL\0"
12//! format    u16 LE    IMAGE_FORMAT (1 for lang-forge 2.0.0-alpha.1)
13//! reserved  u16 LE    0
14//! length    u64 LE    length of the body
15//! hash      u64 LE    FNV-1a 64 of the body
16//! body                the tables, little-endian, length-prefixed slices
17//! ```
18//!
19//! # Untrusted images
20//!
21//! An image may come from anywhere, so loading one assumes nothing: the
22//! header, length, and hash are checked first; every slice's length is
23//! checked against the bytes left before anything is allocated; every
24//! string is checked to be UTF-8; and once decoded, every index the lexer
25//! and parser follow at run time — expression, item, rule, set, kind, mode,
26//! class, level, automaton row — is checked to be in range, so a language
27//! loaded from any bytes that pass parses without panicking. A damaged or
28//! foreign image is an [`ImageError`], never a crash.
29//!
30//! Forge-time warnings ([`Language::warnings`]) are not stored.
31
32use alloc::{boxed::Box, vec::Vec};
33use core::fmt;
34
35use syntax_lang::Span;
36
37use crate::{Language, kind::Kind};
38
39/// The image format this lang-forge writes and reads.
40///
41/// It changes whenever the image layout does; an image of another format is
42/// refused with [`ImageError::Format`]. Re-forge the sketch to get an image
43/// in the current format.
44///
45/// # Examples
46///
47/// ```
48/// use lang_forge::{IMAGE_FORMAT, Language};
49///
50/// let lang = Language::from_lsf("[language]\nname = \"x\"\n[rules]\nx = \"NUMBER\"\n")?;
51/// let image = lang.to_image();
52/// assert_eq!(u16::from_le_bytes([image[4], image[5]]), IMAGE_FORMAT);
53/// # Ok::<(), lang_forge::Error>(())
54/// ```
55pub const IMAGE_FORMAT: u16 = 1;
56
57const MAGIC: &[u8; 4] = b"LSL\0";
58const HEADER: usize = 4 + 2 + 2 + 8 + 8;
59
60/// Why bytes could not be loaded as a language image.
61///
62/// # Examples
63///
64/// ```
65/// use lang_forge::{ImageError, Language};
66///
67/// assert_eq!(Language::from_image(b"not an image").unwrap_err(), ImageError::NotAnImage);
68///
69/// let lang = Language::from_lsf("[language]\nname = \"x\"\n[rules]\nx = \"NUMBER\"\n")?;
70/// let mut image = lang.to_image();
71/// let last = image.len() - 1;
72/// image[last] ^= 0xFF;
73/// assert_eq!(Language::from_image(&image).unwrap_err(), ImageError::Corrupt);
74/// # Ok::<(), lang_forge::Error>(())
75/// ```
76#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
77#[non_exhaustive]
78pub enum ImageError {
79    /// The bytes do not start with the image header.
80    NotAnImage,
81    /// The image is of a format this lang-forge does not read. Re-forge the
82    /// sketch.
83    Format(u16),
84    /// The image is truncated, or its body does not match its hash.
85    Corrupt,
86    /// The image's hash matches, but its tables are not ones lang-forge
87    /// builds: an index out of range, a malformed automaton, or invalid
88    /// text. It was not written by this lang-forge.
89    Invalid,
90}
91
92impl fmt::Display for ImageError {
93    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
94        match self {
95            Self::NotAnImage => f.write_str("not a lang-forge language image"),
96            Self::Format(v) => write!(
97                f,
98                "language image format {v} is not {IMAGE_FORMAT}, the format this lang-forge reads; forge the sketch again"
99            ),
100            Self::Corrupt => f.write_str("the language image is truncated or damaged"),
101            Self::Invalid => {
102                f.write_str("the language image holds tables lang-forge does not build")
103            }
104        }
105    }
106}
107
108impl core::error::Error for ImageError {}
109
110/// FNV-1a, 64 bits: a fixed, platform-independent hash of the body.
111pub(crate) fn fnv1a(bytes: &[u8]) -> u64 {
112    let mut h: u64 = 0xcbf2_9ce4_8422_2325;
113    for &b in bytes {
114        h ^= u64::from(b);
115        h = h.wrapping_mul(0x0000_0100_0000_01b3);
116    }
117    h
118}
119
120/// Appends little-endian values.
121#[derive(Default)]
122pub(crate) struct Writer {
123    pub(crate) out: Vec<u8>,
124}
125
126/// Reads little-endian values, failing on anything out of range.
127pub(crate) struct Reader<'a> {
128    bytes: &'a [u8],
129    pos: usize,
130}
131
132/// The result of a decode step.
133pub(crate) type Res<T> = Result<T, ImageError>;
134
135impl<'a> Reader<'a> {
136    pub(crate) fn new(bytes: &'a [u8]) -> Self {
137        Self { bytes, pos: 0 }
138    }
139
140    fn take(&mut self, n: usize) -> Res<&'a [u8]> {
141        let end = self.pos.checked_add(n).ok_or(ImageError::Invalid)?;
142        let slice = self.bytes.get(self.pos..end).ok_or(ImageError::Invalid)?;
143        self.pos = end;
144        Ok(slice)
145    }
146
147    /// The number of bytes left.
148    pub(crate) fn left(&self) -> usize {
149        self.bytes.len() - self.pos
150    }
151
152    /// A slice length, checked against the bytes left (each item takes at
153    /// least `min` bytes), so no decode allocates more than the input allows.
154    pub(crate) fn len(&mut self, min: usize) -> Res<usize> {
155        let n = u32::get(self)? as usize;
156        if n.saturating_mul(min.max(1)) > self.left() {
157            return Err(ImageError::Invalid);
158        }
159        Ok(n)
160    }
161
162    pub(crate) fn done(&self) -> bool {
163        self.pos == self.bytes.len()
164    }
165}
166
167/// A value that can be written to and read from an image.
168pub(crate) trait Image: Sized {
169    /// The fewest bytes one value takes, for allocation checks.
170    const MIN: usize = 1;
171    fn put(&self, w: &mut Writer);
172    fn get(r: &mut Reader<'_>) -> Res<Self>;
173}
174
175macro_rules! int_image {
176    ($($t:ty),*) => {$(
177        impl Image for $t {
178            const MIN: usize = core::mem::size_of::<$t>();
179            fn put(&self, w: &mut Writer) {
180                w.out.extend_from_slice(&self.to_le_bytes());
181            }
182            fn get(r: &mut Reader<'_>) -> Res<Self> {
183                let bytes = r.take(core::mem::size_of::<$t>())?;
184                let mut buf = [0u8; core::mem::size_of::<$t>()];
185                buf.copy_from_slice(bytes);
186                Ok(<$t>::from_le_bytes(buf))
187            }
188        }
189    )*};
190}
191int_image!(u8, u16, u32, u64, i8);
192
193impl Image for bool {
194    fn put(&self, w: &mut Writer) {
195        w.out.push(u8::from(*self));
196    }
197    fn get(r: &mut Reader<'_>) -> Res<Self> {
198        match u8::get(r)? {
199            0 => Ok(false),
200            1 => Ok(true),
201            _ => Err(ImageError::Invalid),
202        }
203    }
204}
205
206impl Image for char {
207    const MIN: usize = 4;
208    fn put(&self, w: &mut Writer) {
209        (*self as u32).put(w);
210    }
211    fn get(r: &mut Reader<'_>) -> Res<Self> {
212        char::from_u32(u32::get(r)?).ok_or(ImageError::Invalid)
213    }
214}
215
216impl Image for Kind {
217    const MIN: usize = 4;
218    fn put(&self, w: &mut Writer) {
219        self.bits().put(w);
220    }
221    fn get(r: &mut Reader<'_>) -> Res<Self> {
222        Ok(Kind::from_bits(u32::get(r)?))
223    }
224}
225
226impl Image for Span {
227    const MIN: usize = 8;
228    fn put(&self, w: &mut Writer) {
229        self.start().to_u32().put(w);
230        self.end().to_u32().put(w);
231    }
232    fn get(r: &mut Reader<'_>) -> Res<Self> {
233        let (start, end) = (u32::get(r)?, u32::get(r)?);
234        if start > end {
235            return Err(ImageError::Invalid);
236        }
237        Ok(Span::new(start, end))
238    }
239}
240
241impl Image for Box<str> {
242    const MIN: usize = 4;
243    fn put(&self, w: &mut Writer) {
244        (self.len() as u32).put(w);
245        w.out.extend_from_slice(self.as_bytes());
246    }
247    fn get(r: &mut Reader<'_>) -> Res<Self> {
248        let n = r.len(1)?;
249        let bytes = r.take(n)?;
250        core::str::from_utf8(bytes)
251            .map(Box::from)
252            .map_err(|_| ImageError::Invalid)
253    }
254}
255
256impl<T: Image> Image for Box<[T]> {
257    const MIN: usize = 4;
258    fn put(&self, w: &mut Writer) {
259        (self.len() as u32).put(w);
260        for item in self.iter() {
261            item.put(w);
262        }
263    }
264    fn get(r: &mut Reader<'_>) -> Res<Self> {
265        Ok(Vec::<T>::get(r)?.into())
266    }
267}
268
269impl<T: Image> Image for Vec<T> {
270    const MIN: usize = 4;
271    fn put(&self, w: &mut Writer) {
272        (self.len() as u32).put(w);
273        for item in self {
274            item.put(w);
275        }
276    }
277    fn get(r: &mut Reader<'_>) -> Res<Self> {
278        let n = r.len(T::MIN)?;
279        let mut out = Vec::with_capacity(n);
280        for _ in 0..n {
281            out.push(T::get(r)?);
282        }
283        Ok(out)
284    }
285}
286
287impl<T: Image> Image for Option<T> {
288    fn put(&self, w: &mut Writer) {
289        match self {
290            None => 0u8.put(w),
291            Some(v) => {
292                1u8.put(w);
293                v.put(w);
294            }
295        }
296    }
297    fn get(r: &mut Reader<'_>) -> Res<Self> {
298        match u8::get(r)? {
299            0 => Ok(None),
300            1 => Ok(Some(T::get(r)?)),
301            _ => Err(ImageError::Invalid),
302        }
303    }
304}
305
306impl<A: Image, B: Image> Image for (A, B) {
307    const MIN: usize = A::MIN + B::MIN;
308    fn put(&self, w: &mut Writer) {
309        self.0.put(w);
310        self.1.put(w);
311    }
312    fn get(r: &mut Reader<'_>) -> Res<Self> {
313        Ok((A::get(r)?, B::get(r)?))
314    }
315}
316
317impl<A: Image, B: Image, C: Image> Image for (A, B, C) {
318    const MIN: usize = A::MIN + B::MIN + C::MIN;
319    fn put(&self, w: &mut Writer) {
320        self.0.put(w);
321        self.1.put(w);
322        self.2.put(w);
323    }
324    fn get(r: &mut Reader<'_>) -> Res<Self> {
325        Ok((A::get(r)?, B::get(r)?, C::get(r)?))
326    }
327}
328
329impl<T: Image + Copy + Default, const N: usize> Image for [T; N] {
330    const MIN: usize = T::MIN * N;
331    fn put(&self, w: &mut Writer) {
332        for item in self {
333            item.put(w);
334        }
335    }
336    fn get(r: &mut Reader<'_>) -> Res<Self> {
337        let mut out = [T::default(); N];
338        for slot in &mut out {
339            *slot = T::get(r)?;
340        }
341        Ok(out)
342    }
343}
344
345impl<T: Image> Image for Box<T> {
346    const MIN: usize = T::MIN;
347    fn put(&self, w: &mut Writer) {
348        (**self).put(w);
349    }
350    fn get(r: &mut Reader<'_>) -> Res<Self> {
351        Ok(Box::new(T::get(r)?))
352    }
353}
354
355impl Language {
356    /// Writes the forged language as a `.lsl` image.
357    ///
358    /// Loading the image with [`from_image`](Self::from_image) gives a
359    /// language that lexes and parses exactly as this one, without forging
360    /// the sketch again (Packaged mode, fast startup). The bytes are
361    /// deterministic: the same sketch forged by the same lang-forge writes
362    /// the same image on every platform. Forge-time
363    /// [`warnings`](Self::warnings) are not part of the image.
364    ///
365    /// # Examples
366    ///
367    /// ```
368    /// use lang_forge::Language;
369    ///
370    /// let lang = Language::from_lsf(
371    ///     "[language]\nname = \"sum\"\n[rules]\nsum = \"NUMBER ('+' NUMBER)*\"\n",
372    /// )?;
373    /// let image = lang.to_image();
374    /// assert_eq!(&image[..4], b"LSL\0");
375    ///
376    /// let loaded = Language::from_image(&image).expect("a valid image");
377    /// assert_eq!(loaded.parse("1 + 2").dump(), lang.parse("1 + 2").dump());
378    /// assert_eq!(loaded.to_image(), image);
379    /// # Ok::<(), lang_forge::Error>(())
380    /// ```
381    #[must_use]
382    pub fn to_image(&self) -> Vec<u8> {
383        let mut body = Writer::default();
384        self.tables().put(&mut body);
385        let body = body.out;
386        let mut out = Vec::with_capacity(HEADER + body.len());
387        out.extend_from_slice(MAGIC);
388        out.extend_from_slice(&IMAGE_FORMAT.to_le_bytes());
389        out.extend_from_slice(&0u16.to_le_bytes());
390        out.extend_from_slice(&(body.len() as u64).to_le_bytes());
391        out.extend_from_slice(&fnv1a(&body).to_le_bytes());
392        out.extend_from_slice(&body);
393        out
394    }
395
396    /// Loads a language from a `.lsl` image written by
397    /// [`to_image`](Self::to_image).
398    ///
399    /// The image is treated as untrusted: it is checked completely before
400    /// it is used (see the module documentation), so any bytes either load
401    /// as a working language or are refused.
402    ///
403    /// # Errors
404    ///
405    /// [`ImageError::NotAnImage`] for bytes without the image header,
406    /// [`ImageError::Format`] for an image of another format,
407    /// [`ImageError::Corrupt`] for a truncated or damaged one, and
408    /// [`ImageError::Invalid`] for tables lang-forge does not build.
409    ///
410    /// # Examples
411    ///
412    /// ```
413    /// use lang_forge::Language;
414    ///
415    /// let lang = Language::from_lsf("[language]\nname = \"n\"\n[rules]\nn = \"NUMBER+\"\n")?;
416    /// let loaded = Language::from_image(&lang.to_image()).expect("valid");
417    /// assert_eq!(loaded.name(), "n");
418    /// assert!(!loaded.parse("1 2 3").has_errors());
419    /// # Ok::<(), lang_forge::Error>(())
420    /// ```
421    pub fn from_image(bytes: &[u8]) -> Result<Language, ImageError> {
422        if bytes.len() < HEADER || &bytes[..4] != MAGIC {
423            return Err(ImageError::NotAnImage);
424        }
425        let format = u16::from_le_bytes([bytes[4], bytes[5]]);
426        if format != IMAGE_FORMAT {
427            return Err(ImageError::Format(format));
428        }
429        let mut word = [0u8; 8];
430        word.copy_from_slice(&bytes[8..16]);
431        let length = u64::from_le_bytes(word);
432        word.copy_from_slice(&bytes[16..24]);
433        let hash = u64::from_le_bytes(word);
434        let body = &bytes[HEADER..];
435        if bytes[6..8] != [0, 0] || body.len() as u64 != length || fnv1a(body) != hash {
436            return Err(ImageError::Corrupt);
437        }
438        let mut r = Reader::new(body);
439        let grammar = crate::grammar::Grammar::get(&mut r)?;
440        if !r.done() {
441            return Err(ImageError::Invalid);
442        }
443        grammar.validate()?;
444        Ok(Language::from_grammar(grammar))
445    }
446}
447
448/// Fails with [`ImageError::Invalid`] unless `ok`.
449pub(crate) fn check(ok: bool) -> Res<()> {
450    if ok { Ok(()) } else { Err(ImageError::Invalid) }
451}
452
453impl Image for usize {
454    const MIN: usize = 8;
455    fn put(&self, w: &mut Writer) {
456        (*self as u64).put(w);
457    }
458    fn get(r: &mut Reader<'_>) -> Res<Self> {
459        usize::try_from(u64::get(r)?).map_err(|_| ImageError::Invalid)
460    }
461}
462
463/// Implements [`Image`] for a struct field by field, in declaration order.
464macro_rules! image_struct {
465    ($t:ident { $($f:ident),* $(,)? }) => {
466        impl crate::image::Image for $t {
467            fn put(&self, w: &mut crate::image::Writer) {
468                $( crate::image::Image::put(&self.$f, w); )*
469            }
470            fn get(r: &mut crate::image::Reader<'_>) -> crate::image::Res<Self> {
471                Ok(Self { $( $f: crate::image::Image::get(r)?, )* })
472            }
473        }
474    };
475}
476pub(crate) use image_struct;
477
478/// Implements [`Image`] for a field-less enum, each variant with its tag.
479macro_rules! image_enum {
480    ($t:ident { $($v:ident = $n:literal),* $(,)? }) => {
481        impl crate::image::Image for $t {
482            fn put(&self, w: &mut crate::image::Writer) {
483                let tag: u8 = match self { $( $t::$v => $n, )* };
484                crate::image::Image::put(&tag, w);
485            }
486            fn get(r: &mut crate::image::Reader<'_>) -> crate::image::Res<Self> {
487                match <u8 as crate::image::Image>::get(r)? {
488                    $( $n => Ok($t::$v), )*
489                    _ => Err(crate::image::ImageError::Invalid),
490                }
491            }
492        }
493    };
494}
495pub(crate) use image_enum;
496
497#[cfg(test)]
498mod tests {
499    #![allow(clippy::unwrap_used, clippy::expect_used)]
500
501    use super::*;
502
503    #[test]
504    fn test_primitives_round_trip_and_bounds() {
505        let mut w = Writer::default();
506        (7u8, 300u16, 70_000u32).put(&mut w);
507        Some(Box::<str>::from("é")).put(&mut w);
508        Vec::from([1u16, 2, 3]).put(&mut w);
509        true.put(&mut w);
510        let mut r = Reader::new(&w.out);
511        assert_eq!(<(u8, u16, u32)>::get(&mut r), Ok((7, 300, 70_000)));
512        assert_eq!(Option::<Box<str>>::get(&mut r), Ok(Some(Box::from("é"))));
513        assert_eq!(Vec::<u16>::get(&mut r), Ok(Vec::from([1, 2, 3])));
514        assert_eq!(bool::get(&mut r), Ok(true));
515        assert!(r.done());
516        // A length larger than the input is refused before allocating.
517        let mut r = Reader::new(&[0xFF, 0xFF, 0xFF, 0x7F]);
518        assert_eq!(Vec::<u64>::get(&mut r), Err(ImageError::Invalid));
519        // Bad booleans, bad UTF-8, bad chars.
520        assert_eq!(bool::get(&mut Reader::new(&[2])), Err(ImageError::Invalid));
521        assert_eq!(
522            Box::<str>::get(&mut Reader::new(&[1, 0, 0, 0, 0xFF])),
523            Err(ImageError::Invalid)
524        );
525        assert_eq!(
526            char::get(&mut Reader::new(&[0, 0xD8, 0, 0])),
527            Err(ImageError::Invalid)
528        );
529        assert_eq!(fnv1a(b""), 0xcbf2_9ce4_8422_2325);
530    }
531}
lang_forge/image.rs

lang_forge/
image.rs
