substrate_data/wire/binary/decode/
decoder_ref.rs

1//! [`Decoder`] reading a value borrowed: strings point into the bytes,
2//! lists and maps go in an arena.
3
4use std::collections::HashSet;
5
6use bumpalo::Bump;
7
8use super::decoder::{F32_BYTES, F64_BYTES, MAP_ENTRY_MIN};
9use super::decoder_value::inline_int;
10use crate::binary::{DecodeError, Decoder, tag, unzigzag};
11use crate::model::borrowed::{MapRef, ValueRef};
12use crate::model::quick_hash::QuickBuild;
13
14/// Maps up to this many keys are checked for a repeat by scanning.
15const SCAN_MAX: usize = 16;
16
17impl<'b> Decoder<'b> {
18    /// The next value, borrowed: strings point into the bytes, lists and maps go in `arena`.
19    ///
20    /// # Errors
21    ///
22    /// [`DecodeError`] when the bytes aren't a value.
23    pub fn value_ref<'a>(&mut self, arena: &'a Bump) -> Result<ValueRef<'a>, DecodeError>
24    where
25        'b: 'a,
26    {
27        let mut stack = Vec::new();
28        self.value_ref_in(arena, &mut stack)
29    }
30
31    /// [`Decoder::value_ref`]: children gather on `stack`, then move into `arena` as one slice.
32    fn value_ref_in<'a>(
33        &mut self,
34        arena: &'a Bump,
35        stack: &mut Vec<ValueRef<'a>>,
36    ) -> Result<ValueRef<'a>, DecodeError>
37    where
38        'b: 'a,
39    {
40        let t = self.byte()?;
41        Ok(match t {
42            tag::NULL => ValueRef::Null,
43            tag::FALSE => ValueRef::Bool(false),
44            tag::TRUE => ValueRef::Bool(true),
45            tag::INT => ValueRef::Int(unzigzag(self.varint()?)),
46            tag::FLOAT => ValueRef::Float(f64::from_le_bytes(self.fixed()?)),
47            tag::FLOAT32 => ValueRef::Float(f64::from(f32::from_le_bytes(self.fixed()?))),
48            tag::STR => ValueRef::Str(self.string()?),
49            tag::LIST => {
50                let n = self.count(1)?;
51                self.deeper()?;
52                let items = self.items_ref(arena, stack, n)?;
53                self.depth -= 1;
54                ValueRef::List(items)
55            }
56            tag::MAP => self.map_ref(arena, stack)?,
57            tag::REF => {
58                let (kind, id) = self.reference()?;
59                ValueRef::Ref { kind, id }
60            }
61            tag::BYTES => ValueRef::Bytes(self.length_bytes()?),
62            tag::STREAM => self.stream_ref(arena, stack)?,
63            tag::INTS | tag::FLOATS | tag::FLOATS32 => self.packed_ref(arena, t)?,
64            tag::MAP_SHAPE if self.v2 => {
65                let shape = self.shape_spec()?;
66                self.shaped_ref(arena, stack, shape)?
67            }
68            tag::RECORDS if self.v2 => self.records_ref(arena, stack)?,
69            t if self.is_inline_int(t) => ValueRef::Int(inline_int(t)),
70            t if self.is_indexed(t) => ValueRef::Str(self.indexed(t)?),
71            _ => {
72                self.i -= 1;
73                return Err(self.error(format!("unknown tag {t}")));
74            }
75        })
76    }
77
78    fn stream_ref<'a>(
79        &mut self,
80        arena: &'a Bump,
81        stack: &mut Vec<ValueRef<'a>>,
82    ) -> Result<ValueRef<'a>, DecodeError>
83    where
84        'b: 'a,
85    {
86        let body = self.stream_body()?;
87        let mut d = self.inner(body);
88        let n = d.count(1)?;
89        let items = d.items_ref(arena, stack, n)?;
90        d.end()?;
91        Ok(ValueRef::List(items))
92    }
93
94    /// `n` values gathered on `stack`, then moved into `arena` as one slice.
95    fn items_ref<'a>(
96        &mut self,
97        arena: &'a Bump,
98        stack: &mut Vec<ValueRef<'a>>,
99        n: usize,
100    ) -> Result<&'a [ValueRef<'a>], DecodeError>
101    where
102        'b: 'a,
103    {
104        let start = stack.len();
105        for _ in 0..n {
106            let v = self.value_ref_in(arena, stack)?;
107            stack.push(v);
108        }
109        let items = arena.alloc_slice_copy(&stack[start..]);
110        stack.truncate(start);
111        Ok(items)
112    }
113
114    fn map_ref<'a>(
115        &mut self,
116        arena: &'a Bump,
117        stack: &mut Vec<ValueRef<'a>>,
118    ) -> Result<ValueRef<'a>, DecodeError>
119    where
120        'b: 'a,
121    {
122        let n = self.count(MAP_ENTRY_MIN)?;
123        self.deeper()?;
124        let mut entries = bumpalo::collections::Vec::with_capacity_in(n, arena);
125        let mut set = None;
126        for _ in 0..n {
127            let at = self.i;
128            let k = self.string()?;
129            if repeats(&entries, k, &mut set) {
130                return Err(DecodeError::duplicate_key(k, at));
131            }
132            entries.push((k, self.value_ref_in(arena, stack)?));
133        }
134        self.depth -= 1;
135        Ok(ValueRef::Map(MapRef(entries.into_bump_slice())))
136    }
137
138    /// The entries of a map of shape `shape`: its values, one per key.
139    fn shaped_entries_ref<'a>(
140        &mut self,
141        arena: &'a Bump,
142        stack: &mut Vec<ValueRef<'a>>,
143        shape: usize,
144        n: usize,
145    ) -> Result<ValueRef<'a>, DecodeError>
146    where
147        'b: 'a,
148    {
149        let mut entries = bumpalo::collections::Vec::with_capacity_in(n, arena);
150        for at in 0..n {
151            let k = self.strings[self.shapes.key(shape, at)];
152            entries.push((k, self.value_ref_in(arena, stack)?));
153        }
154        Ok(ValueRef::Map(MapRef(entries.into_bump_slice())))
155    }
156
157    fn shaped_ref<'a>(
158        &mut self,
159        arena: &'a Bump,
160        stack: &mut Vec<ValueRef<'a>>,
161        shape: usize,
162    ) -> Result<ValueRef<'a>, DecodeError>
163    where
164        'b: 'a,
165    {
166        let n = self.shape_width(shape)?;
167        self.deeper()?;
168        let map = self.shaped_entries_ref(arena, stack, shape, n)?;
169        self.depth -= 1;
170        Ok(map)
171    }
172
173    fn records_ref<'a>(
174        &mut self,
175        arena: &'a Bump,
176        stack: &mut Vec<ValueRef<'a>>,
177    ) -> Result<ValueRef<'a>, DecodeError>
178    where
179        'b: 'a,
180    {
181        let n = self.count(1)?;
182        let shape = self.shape_spec()?;
183        let width = self.shapes.width(shape);
184        let left = self.b.len() - self.i;
185        if n > left / width {
186            return Err(self.error(format!("length {n} past the end ({left} bytes left)")));
187        }
188        self.deeper()?;
189        let start = stack.len();
190        for _ in 0..n {
191            self.deeper()?;
192            let record = self.shaped_entries_ref(arena, stack, shape, width)?;
193            stack.push(record);
194            self.depth -= 1;
195        }
196        self.depth -= 1;
197        let items = arena.alloc_slice_copy(&stack[start..]);
198        stack.truncate(start);
199        Ok(ValueRef::List(items))
200    }
201
202    /// A packed list of ints (`t` is [`tag::INTS`]) or floats.
203    fn packed_ref<'a>(&mut self, arena: &'a Bump, t: u8) -> Result<ValueRef<'a>, DecodeError> {
204        let items: Vec<ValueRef<'a>> = match t {
205            tag::INTS => {
206                let n = self.count(1)?;
207                let mut items = Vec::with_capacity(n);
208                for _ in 0..n {
209                    items.push(ValueRef::Int(unzigzag(self.varint()?)));
210                }
211                items
212            }
213            tag::FLOATS => self
214                .packed_floats::<F64_BYTES>()?
215                .map(|f| ValueRef::Float(f64::from_le_bytes(*f)))
216                .collect(),
217            _ => self
218                .packed_floats::<F32_BYTES>()?
219                .map(|f| ValueRef::Float(f64::from(f32::from_le_bytes(*f))))
220                .collect(),
221        };
222        Ok(ValueRef::List(arena.alloc_slice_copy(&items)))
223    }
224}
225
226/// Whether `entries` has `key` already (when it doesn't, `key` is noted in
227/// `set`, if there are enough entries to keep one).
228fn repeats<'a>(
229    entries: &bumpalo::collections::Vec<'_, (&'a str, ValueRef<'_>)>,
230    key: &'a str,
231    set: &mut Option<HashSet<&'a str, QuickBuild>>,
232) -> bool {
233    if let Some(set) = set {
234        return !set.insert(key);
235    }
236    if entries.iter().any(|(k, _)| *k == key) {
237        return true;
238    }
239    if entries.len() >= SCAN_MAX {
240        let mut all: HashSet<&str, QuickBuild> = entries.iter().map(|(k, _)| *k).collect();
241        all.insert(key);
242        *set = Some(all);
243    }
244    false
245}
substrate_data/wire/binary/decode/decoder_ref.rs

substrate_data/wire/binary/decode/
decoder_ref.rs
