substrate_data/wire/binary/
decoder.rs

1//! [`Decoder`]: reads the binary form — as a [`Value`] here, borrowed as a
2//! [`ValueRef`] (`decoder_ref`), or step by step by a schema reading itself
3//! (`decoder_straight`).
4
5use super::seen_keys::SeenKeys;
6use super::{
7    DecodeError, MAGIC, MAX_DEPTH, NEW_STRING, STREAM_LEN_BYTES, VERSION, read_varint, tag,
8    unzigzag,
9};
10use crate::model::value::{KindName, Map, Ref, RefKey, Value};
11use crate::sync::Arc;
12
13/// Strings a decoder makes room for at once: a message's keys and values.
14pub(super) const STRINGS_START: usize = 16;
15
16/// Bytes of a float, and of a 32-bit one.
17pub(super) const F64_BYTES: usize = 8;
18pub(super) const F32_BYTES: usize = 4;
19
20/// Bytes a map entry takes at least: its key and its value's tag.
21pub(super) const MAP_ENTRY_MIN: usize = 2;
22
23/// Reads the binary form. The step-by-step reads ([`Decoder::int`],
24/// [`Decoder::map`] …) answer `None` for anything but what
25/// [`crate::Schema::encode`] writes there — the schema then reads the
26/// slow way, which says what's wrong.
27#[derive(Debug)]
28pub struct Decoder<'b> {
29    pub(super) b: &'b [u8],
30    pub(super) i: usize,
31    pub(super) strings: Vec<&'b str>,
32    /// Map keys made so far, by table index: each key is allocated once.
33    pub(super) keys: Vec<Option<Arc<str>>>,
34    pub(super) depth: usize,
35}
36
37impl<'b> Decoder<'b> {
38    /// After the header: the root value next.
39    ///
40    /// # Errors
41    ///
42    /// [`DecodeError`] when the header isn't `SDAT` and this version.
43    pub fn open(bytes: &'b [u8]) -> Result<Self, DecodeError> {
44        let mut d = Decoder {
45            b: bytes,
46            i: 0,
47            strings: Vec::with_capacity(STRINGS_START),
48            keys: Vec::new(),
49            depth: 0,
50        };
51        if !bytes.starts_with(MAGIC) {
52            return Err(d.error("not Substrate Data (no `SDAT` header)"));
53        }
54        d.i = MAGIC.len();
55        let version = d.byte()?;
56        if version != VERSION {
57            return Err(d.error(format!(
58                "Substrate Data version {version}, this reads version {VERSION}"
59            )));
60        }
61        Ok(d)
62    }
63
64    /// A stream's body ([`crate::Stream`]): its count and values, its strings its own.
65    pub(crate) fn body(bytes: &'b [u8]) -> Self {
66        Decoder {
67            b: bytes,
68            i: 0,
69            strings: Vec::with_capacity(STRINGS_START),
70            keys: Vec::new(),
71            depth: 0,
72        }
73    }
74
75    /// A stream's body: its bytes, read past.
76    pub(super) fn stream_body(&mut self) -> Result<&'b [u8], DecodeError> {
77        let len = u32::from_le_bytes(self.fixed::<STREAM_LEN_BYTES>()?) as usize;
78        self.take(len)
79    }
80
81    /// A stream's values, decoded as a list.
82    pub(super) fn stream_values(&mut self) -> Result<Vec<Value>, DecodeError> {
83        let mut d = Decoder::body(self.stream_body()?);
84        d.depth = self.depth;
85        let n = d.count(1)?;
86        let mut items = Vec::with_capacity(n);
87        for _ in 0..n {
88            items.push(d.value()?);
89        }
90        d.end()?;
91        Ok(items)
92    }
93
94    /// Whether every byte was read.
95    #[must_use]
96    pub fn at_end(&self) -> bool {
97        self.i == self.b.len()
98    }
99
100    pub(super) fn end(&self) -> Result<(), DecodeError> {
101        if self.at_end() {
102            Ok(())
103        } else {
104            Err(self.error("bytes after the value"))
105        }
106    }
107
108    pub(super) fn error(&self, message: impl Into<String>) -> DecodeError {
109        DecodeError {
110            message: message.into(),
111            offset: self.i,
112        }
113    }
114
115    pub(super) fn byte(&mut self) -> Result<u8, DecodeError> {
116        let b = *self
117            .b
118            .get(self.i)
119            .ok_or_else(|| self.error("unexpected end"))?;
120        self.i += 1;
121        Ok(b)
122    }
123
124    pub(super) fn varint(&mut self) -> Result<u64, DecodeError> {
125        read_varint(self.b, &mut self.i)
126            .ok_or_else(|| self.error("a varint cut short or longer than 64 bits"))
127    }
128
129    /// A length, checked against what's left: each of the `count` things takes at least `min` bytes.
130    pub(super) fn count(&mut self, min: usize) -> Result<usize, DecodeError> {
131        let n = self.varint()?;
132        let left = self.b.len() - self.i;
133        match usize::try_from(n) {
134            Ok(n) if n <= left / min.max(1) => Ok(n),
135            _ => Err(self.error(format!("length {n} past the end ({left} bytes left)"))),
136        }
137    }
138
139    pub(super) fn fixed<const N: usize>(&mut self) -> Result<[u8; N], DecodeError> {
140        let bytes = self
141            .b
142            .get(self.i..self.i + N)
143            .ok_or_else(|| self.error("unexpected end"))?;
144        self.i += N;
145        bytes.try_into().map_err(|_| self.error("unexpected end"))
146    }
147
148    /// `len` bytes.
149    pub(super) fn take(&mut self, len: usize) -> Result<&'b [u8], DecodeError> {
150        let end = self
151            .i
152            .checked_add(len)
153            .filter(|&e| e <= self.b.len())
154            .ok_or_else(|| self.error("bytes past the end"))?;
155        let out = &self.b[self.i..end];
156        self.i = end;
157        Ok(out)
158    }
159
160    /// A packed list of floats `N` bytes wide: each one's bytes, read in place (no alignment asked).
161    pub(super) fn packed_floats<const N: usize>(
162        &mut self,
163    ) -> Result<std::slice::Iter<'b, [u8; N]>, DecodeError> {
164        let n = self.count(N)?;
165        let bytes = self.take(n * N)?;
166        Ok(bytes.as_chunks::<N>().0.iter())
167    }
168
169    /// A length and that many bytes.
170    pub(super) fn length_bytes(&mut self) -> Result<&'b [u8], DecodeError> {
171        let len =
172            usize::try_from(self.varint()?).map_err(|_| self.error("a length beyond memory"))?;
173        self.take(len)
174    }
175
176    /// A string: new (read, and added to the table) or the table's.
177    pub(super) fn string(&mut self) -> Result<&'b str, DecodeError> {
178        let i = self.string_index()?;
179        Ok(self.strings[i])
180    }
181
182    pub(super) fn string_index(&mut self) -> Result<usize, DecodeError> {
183        let v = self.varint()?;
184        if v & NEW_STRING == 0 {
185            let i = (v >> 1) as usize;
186            return if i < self.strings.len() {
187                Ok(i)
188            } else {
189                Err(self.error(format!("string {i} isn't in the table")))
190            };
191        }
192        let len = usize::try_from(v >> 1).map_err(|_| self.error("a length beyond memory"))?;
193        let at = self.i;
194        let s = crate::utf8::from_utf8(self.take(len)?).map_err(|_| DecodeError {
195            message: "a string isn't UTF-8".into(),
196            offset: at,
197        })?;
198        self.strings.push(s);
199        Ok(self.strings.len() - 1)
200    }
201
202    /// The key at table index `i`: shared with every other map that has it.
203    fn shared_key_at(&mut self, i: usize) -> Arc<str> {
204        if self.keys.len() <= i {
205            self.keys.resize(i + 1, None);
206        }
207        self.keys[i]
208            .get_or_insert_with(|| self.strings[i].into())
209            .clone()
210    }
211
212    /// A reference's kind and id, each checked: a malformed one is an error.
213    pub(super) fn reference(&mut self) -> Result<(KindName, &'b str), DecodeError> {
214        let kind_at = self.i;
215        let kind = KindName::new(self.string()?).map_err(|e| DecodeError {
216            message: e.to_string(),
217            offset: kind_at,
218        })?;
219        let id_at = self.i;
220        let id = self.string()?;
221        if !RefKey::is_valid(id) {
222            return Err(DecodeError {
223                message: format!("`{id}` isn't a reference's id"),
224                offset: id_at,
225            });
226        }
227        Ok((kind, id))
228    }
229
230    pub(super) fn deeper(&mut self) -> Result<(), DecodeError> {
231        self.depth += 1;
232        if self.depth > MAX_DEPTH {
233            return Err(self.error(format!("nested deeper than {MAX_DEPTH} levels")));
234        }
235        Ok(())
236    }
237
238    /// The next value, owned.
239    ///
240    /// # Errors
241    ///
242    /// [`DecodeError`] when the bytes aren't a value.
243    pub fn value(&mut self) -> Result<Value, DecodeError> {
244        Ok(match self.byte()? {
245            tag::NULL => Value::Null,
246            tag::FALSE => Value::Bool(false),
247            tag::TRUE => Value::Bool(true),
248            tag::INT => Value::Int(unzigzag(self.varint()?)),
249            tag::FLOAT => Value::Float(f64::from_le_bytes(self.fixed()?)),
250            tag::FLOAT32 => Value::Float(f64::from(f32::from_le_bytes(self.fixed()?))),
251            tag::FLOATS => Value::List(
252                self.packed_floats::<F64_BYTES>()?
253                    .map(|f| Value::Float(f64::from_le_bytes(*f)))
254                    .collect(),
255            ),
256            tag::FLOATS32 => Value::List(
257                self.packed_floats::<F32_BYTES>()?
258                    .map(|f| Value::Float(f64::from(f32::from_le_bytes(*f))))
259                    .collect(),
260            ),
261            tag::STR => Value::Str(self.string()?.to_owned()),
262            tag::LIST => self.list_value()?,
263            tag::MAP => self.map_value()?,
264            tag::REF => {
265                let (kind, id) = self.reference()?;
266                Value::Ref(Ref::new(kind, RefKey::spelled(id)))
267            }
268            tag::BYTES => Value::Bytes(self.length_bytes()?.to_vec()),
269            tag::INTS => self.ints_value()?,
270            tag::STREAM => Value::List(self.stream_values()?),
271            t => {
272                self.i -= 1;
273                return Err(self.error(format!("unknown tag {t}")));
274            }
275        })
276    }
277
278    fn list_value(&mut self) -> Result<Value, DecodeError> {
279        let n = self.count(1)?;
280        self.deeper()?;
281        let mut items = Vec::with_capacity(n);
282        for _ in 0..n {
283            items.push(self.value()?);
284        }
285        self.depth -= 1;
286        Ok(Value::List(items))
287    }
288
289    fn map_value(&mut self) -> Result<Value, DecodeError> {
290        let n = self.count(MAP_ENTRY_MIN)?;
291        self.deeper()?;
292        let mut map = Map::with_capacity(n);
293        let mut seen = SeenKeys::default();
294        for _ in 0..n {
295            let at = self.i;
296            let i = self.string_index()?;
297            if !seen.insert(self.strings[i]) {
298                return Err(DecodeError::duplicate_key(self.strings[i], at));
299            }
300            let k = self.shared_key_at(i);
301            map.push_unchecked(k, self.value()?);
302        }
303        self.depth -= 1;
304        Ok(Value::Map(map))
305    }
306
307    fn ints_value(&mut self) -> Result<Value, DecodeError> {
308        let n = self.count(1)?;
309        let mut items = Vec::with_capacity(n);
310        for _ in 0..n {
311            items.push(Value::Int(unzigzag(self.varint()?)));
312        }
313        Ok(Value::List(items))
314    }
315}
substrate_data/wire/binary/decoder.rs

substrate_data/wire/binary/
decoder.rs
