Skip to main content

laser_wire/
framing.rs

1// The shared CBOR entry points and the `[len: u32 LE][bytes]` socket framing,
2// sans-io: pure functions over byte slices, so the same code serves the
3// server's socket loop, LaserData Cloud's listener, and any future transport
4// without dragging a runtime into the contract. Every frame in the LaserData
5// band is named-field CBOR (RFC 8949, serde maps in declaration order via
6// `ciborium`). This module is the one encoding entry point so no consumer can
7// drift to a different encoding. Machine ids ride as fixed-width 16-byte CBOR
8// byte strings (the `wire_id!` serde uses `serialize_bytes`), not bignums.
9
10use crate::error::DecodeError;
11use crate::limits::MAX_FRAME_BYTES;
12use serde::Serialize;
13use serde::de::DeserializeOwned;
14
15/// Nesting a field scan follows before it refuses the value. Deeper input is
16/// never a named frame this band produces.
17const MAX_SCAN_DEPTH: u32 = 64;
18
19const MAJOR_BYTES: u8 = 2;
20const MAJOR_TEXT: u8 = 3;
21const MAJOR_ARRAY: u8 = 4;
22const MAJOR_MAP: u8 = 5;
23const MAJOR_TAG: u8 = 6;
24const MAJOR_SIMPLE: u8 = 7;
25const BREAK: u8 = 0xff;
26const NULL: u8 = 0xf6;
27
28/// Encode `value` as named-field CBOR (the band's canonical encoding).
29pub fn encode_named<T: Serialize + ?Sized>(value: &T) -> Result<Vec<u8>, DecodeError> {
30    let mut buffer = Vec::new();
31    encode_named_into(value, &mut buffer)?;
32    Ok(buffer)
33}
34
35/// The in-place form of [`encode_named`]: clear and fill the caller's buffer,
36/// so a hot loop reuses one allocation across encodes. Bytes identical to
37/// [`encode_named`] by construction (it delegates here), so there is still
38/// exactly one encoder.
39pub fn encode_named_into<T: Serialize + ?Sized>(
40    value: &T,
41    buffer: &mut Vec<u8>,
42) -> Result<(), DecodeError> {
43    buffer.clear();
44    ciborium::into_writer(value, &mut *buffer)
45        .map_err(|error| DecodeError::Encode(error.to_string()))
46}
47
48/// Decode named-field CBOR produced by [`encode_named`].
49///
50/// Rejects trailing bytes after the value. A band payload is exactly one CBOR
51/// item, so leftover bytes are a decode failure, never a silent skip.
52pub fn decode_named<T: DeserializeOwned>(payload: &[u8]) -> Result<T, DecodeError> {
53    let mut reader = payload;
54    let value = ciborium::from_reader(&mut reader)
55        .map_err(|error| DecodeError::Decode(error.to_string()))?;
56    if !reader.is_empty() {
57        return Err(DecodeError::Decode(format!(
58            "{} trailing byte(s) after the CBOR value",
59            reader.len()
60        )));
61    }
62    Ok(value)
63}
64
65/// Encode `value` as named-field CBOR behind its `[len: u32 LE]` prefix in one
66/// buffer sized for `capacity_hint` payload bytes, so a transport writes the
67/// frame without copying the encoded bytes again. Errors when the encoded
68/// value exceeds `max_bytes` or [`MAX_FRAME_BYTES`].
69pub fn encode_named_framed<T: Serialize + ?Sized>(
70    value: &T,
71    capacity_hint: usize,
72    max_bytes: usize,
73) -> Result<Vec<u8>, DecodeError> {
74    let mut framed = Vec::with_capacity(4 + capacity_hint);
75    framed.extend_from_slice(&[0; 4]);
76    ciborium::into_writer(value, &mut framed)
77        .map_err(|error| DecodeError::Encode(error.to_string()))?;
78    let length = framed.len() - 4;
79    if length > max_bytes.min(MAX_FRAME_BYTES) {
80        return Err(DecodeError::Frame(format!(
81            "payload is {length}B, exceeds frame cap {}B",
82            max_bytes.min(MAX_FRAME_BYTES)
83        )));
84    }
85    framed[..4].copy_from_slice(&(length as u32).to_le_bytes());
86    Ok(framed)
87}
88
89/// The top-level fields of one named-field CBOR map, each value left encoded
90/// in place.
91///
92/// One pass over the map finds every key and the bytes of its value and
93/// copies nothing: a byte string is stepped over by its length. A reader then
94/// decodes only the small values it needs and leaves a large one alone. Keys
95/// must be definite text and unique, nesting is bounded, and nothing may
96/// follow the map, so a malformed request is refused rather than read in
97/// part.
98#[derive(Debug, Default)]
99pub struct NamedFields<'a> {
100    fields: Vec<(&'a str, &'a [u8])>,
101}
102
103impl<'a> NamedFields<'a> {
104    /// Scan the fields of `payload`.
105    pub fn decode(payload: &'a [u8]) -> Result<Self, DecodeError> {
106        Self::decode_within(payload, usize::MAX)
107    }
108
109    /// [`Self::decode`], refusing a map of more than `max_fields` fields
110    /// before it scans past them, so a server can bound the work one request
111    /// costs before it authorizes it.
112    pub fn decode_within(payload: &'a [u8], max_fields: usize) -> Result<Self, DecodeError> {
113        let too_many = || {
114            DecodeError::Decode(format!(
115                "a named-field map holds more than {max_fields} fields"
116            ))
117        };
118        let mut cursor = Cursor {
119            bytes: payload,
120            at: 0,
121        };
122        let (major, argument) = cursor.head()?;
123        if major != MAJOR_MAP {
124            return Err(DecodeError::Decode(
125                "a named-field value is a map".to_owned(),
126            ));
127        }
128        let mut fields: Vec<(&'a str, &'a [u8])> = Vec::new();
129        match argument {
130            Argument::Value(count) => {
131                if usize::try_from(count)
132                    .ok()
133                    .is_none_or(|count| count > max_fields)
134                {
135                    return Err(too_many());
136                }
137                for _ in 0..count {
138                    fields.push(cursor.entry()?);
139                }
140            }
141            Argument::Indefinite => {
142                while !cursor.at_break()? {
143                    if fields.len() == max_fields {
144                        return Err(too_many());
145                    }
146                    fields.push(cursor.entry()?);
147                }
148                cursor.at += 1;
149            }
150        }
151        if cursor.at != payload.len() {
152            return Err(DecodeError::Decode(format!(
153                "{} trailing byte(s) after the CBOR value",
154                payload.len() - cursor.at
155            )));
156        }
157        // Sorted, so a map of many fields costs one sort, not a pass per field.
158        let mut keys: Vec<&str> = fields.iter().map(|(key, _)| *key).collect();
159        keys.sort_unstable();
160        if let Some(pair) = keys.windows(2).find(|pair| pair[0] == pair[1]) {
161            return Err(DecodeError::Decode(format!(
162                "duplicate field `{}`",
163                pair[0]
164            )));
165        }
166        Ok(Self { fields })
167    }
168
169    /// The encoded value of `key`, when the map holds it.
170    pub fn get(&self, key: &str) -> Option<&'a [u8]> {
171        self.fields
172            .iter()
173            .find(|(name, _)| *name == key)
174            .map(|(_, value)| *value)
175    }
176
177    /// The text value of `key`, borrowed from the payload. `Ok(None)` when the
178    /// field is absent or null, an error when it holds anything but text.
179    pub fn text(&self, key: &str) -> Result<Option<&'a str>, DecodeError> {
180        let Some(value) = self.get(key) else {
181            return Ok(None);
182        };
183        if value == [NULL] {
184            return Ok(None);
185        }
186        let mut cursor = Cursor {
187            bytes: value,
188            at: 0,
189        };
190        let (major, argument) = cursor.head()?;
191        let (MAJOR_TEXT, Argument::Value(length)) = (major, argument) else {
192            return Err(DecodeError::Decode(format!("field `{key}` is not text")));
193        };
194        let text = cursor.take(length)?;
195        std::str::from_utf8(text)
196            .map(Some)
197            .map_err(|_| DecodeError::Decode(format!("field `{key}` is not UTF-8")))
198    }
199
200    /// The value of `key` decoded on its own. `Ok(None)` when the field is
201    /// absent.
202    pub fn value<T: DeserializeOwned>(&self, key: &str) -> Result<Option<T>, DecodeError> {
203        self.get(key).map(decode_named).transpose()
204    }
205}
206
207/// The argument of one CBOR head: a count, a length, a value, or the
208/// indefinite marker.
209enum Argument {
210    Value(u64),
211    Indefinite,
212}
213
214struct Cursor<'a> {
215    bytes: &'a [u8],
216    at: usize,
217}
218
219impl<'a> Cursor<'a> {
220    fn entry(&mut self) -> Result<(&'a str, &'a [u8]), DecodeError> {
221        let (major, argument) = self.head()?;
222        let (MAJOR_TEXT, Argument::Value(length)) = (major, argument) else {
223            return Err(DecodeError::Decode(
224                "a named-field key is definite text".to_owned(),
225            ));
226        };
227        let key = std::str::from_utf8(self.take(length)?)
228            .map_err(|_| DecodeError::Decode("a named-field key is UTF-8".to_owned()))?;
229        let start = self.at;
230        self.skip(0)?;
231        Ok((key, &self.bytes[start..self.at]))
232    }
233
234    fn head(&mut self) -> Result<(u8, Argument), DecodeError> {
235        let initial = *self.bytes.get(self.at).ok_or_else(truncated)?;
236        self.at += 1;
237        let major = initial >> 5;
238        let argument = match initial & 0x1f {
239            info @ 0..=23 => Argument::Value(u64::from(info)),
240            24 => Argument::Value(u64::from(self.take(1)?[0])),
241            25 => Argument::Value(u64::from(u16::from_be_bytes(
242                self.take(2)?.try_into().map_err(|_| truncated())?,
243            ))),
244            26 => Argument::Value(u64::from(u32::from_be_bytes(
245                self.take(4)?.try_into().map_err(|_| truncated())?,
246            ))),
247            27 => Argument::Value(u64::from_be_bytes(
248                self.take(8)?.try_into().map_err(|_| truncated())?,
249            )),
250            31 => Argument::Indefinite,
251            _ => {
252                return Err(DecodeError::Decode(
253                    "reserved CBOR additional information".to_owned(),
254                ));
255            }
256        };
257        Ok((major, argument))
258    }
259
260    fn skip(&mut self, depth: u32) -> Result<(), DecodeError> {
261        if depth > MAX_SCAN_DEPTH {
262            return Err(DecodeError::Decode(format!(
263                "CBOR nesting exceeds {MAX_SCAN_DEPTH}"
264            )));
265        }
266        let (major, argument) = self.head()?;
267        match (major, argument) {
268            (MAJOR_BYTES | MAJOR_TEXT, Argument::Value(length)) => {
269                self.take(length)?;
270            }
271            (MAJOR_BYTES | MAJOR_TEXT, Argument::Indefinite) => {
272                while !self.at_break()? {
273                    let (chunk_major, chunk) = self.head()?;
274                    let Argument::Value(length) = chunk else {
275                        return Err(DecodeError::Decode(
276                            "an indefinite string chunk is definite".to_owned(),
277                        ));
278                    };
279                    if chunk_major != major {
280                        return Err(DecodeError::Decode(
281                            "an indefinite string chunk has its string's type".to_owned(),
282                        ));
283                    }
284                    self.take(length)?;
285                }
286                self.at += 1;
287            }
288            (MAJOR_ARRAY, Argument::Value(count)) => {
289                for _ in 0..count {
290                    self.skip(depth + 1)?;
291                }
292            }
293            (MAJOR_MAP, Argument::Value(count)) => {
294                for _ in 0..count {
295                    self.skip(depth + 1)?;
296                    self.skip(depth + 1)?;
297                }
298            }
299            (MAJOR_ARRAY | MAJOR_MAP, Argument::Indefinite) => {
300                let mut items = 0_u64;
301                while !self.at_break()? {
302                    self.skip(depth + 1)?;
303                    items += 1;
304                }
305                if major == MAJOR_MAP && items % 2 == 1 {
306                    return Err(DecodeError::Decode(
307                        "an indefinite map holds whole pairs".to_owned(),
308                    ));
309                }
310                self.at += 1;
311            }
312            (MAJOR_TAG, Argument::Value(_)) => self.skip(depth + 1)?,
313            (MAJOR_SIMPLE, Argument::Value(_)) => {}
314            (_, Argument::Value(_)) => {}
315            (_, Argument::Indefinite) => {
316                return Err(DecodeError::Decode(
317                    "only strings, arrays and maps are indefinite".to_owned(),
318                ));
319            }
320        }
321        Ok(())
322    }
323
324    fn at_break(&self) -> Result<bool, DecodeError> {
325        self.bytes
326            .get(self.at)
327            .map(|byte| *byte == BREAK)
328            .ok_or_else(truncated)
329    }
330
331    fn take(&mut self, length: u64) -> Result<&'a [u8], DecodeError> {
332        let end = usize::try_from(length)
333            .ok()
334            .and_then(|length| self.at.checked_add(length))
335            .filter(|end| *end <= self.bytes.len())
336            .ok_or_else(truncated)?;
337        let taken = &self.bytes[self.at..end];
338        self.at = end;
339        Ok(taken)
340    }
341}
342
343fn truncated() -> DecodeError {
344    DecodeError::Decode("the CBOR value is truncated".to_owned())
345}
346
347/// Frame `payload` as `[len: u32 LE][payload]`. Errors when the payload
348/// exceeds [`MAX_FRAME_BYTES`].
349pub fn frame_encode(payload: &[u8]) -> Result<Vec<u8>, DecodeError> {
350    if payload.len() > MAX_FRAME_BYTES {
351        return Err(DecodeError::Frame(format!(
352            "payload is {}B, exceeds frame cap {MAX_FRAME_BYTES}B",
353            payload.len()
354        )));
355    }
356    let mut framed = Vec::with_capacity(4 + payload.len());
357    framed.extend_from_slice(&(payload.len() as u32).to_le_bytes());
358    framed.extend_from_slice(payload);
359    Ok(framed)
360}
361
362/// Parse one frame from the front of `buf`. `Ok(None)` means the buffer does
363/// not yet hold a whole frame, so read more bytes. `Ok(Some((payload, consumed)))`
364/// is one payload and how many bytes of `buf` it spanned (`4 + len`). Errors
365/// when the length prefix exceeds [`MAX_FRAME_BYTES`].
366pub fn frame_decode(buf: &[u8]) -> Result<Option<(&[u8], usize)>, DecodeError> {
367    let Some(prefix) = buf.get(..4) else {
368        return Ok(None);
369    };
370    let len = u32::from_le_bytes(prefix.try_into().expect("4-byte slice")) as usize;
371    if len > MAX_FRAME_BYTES {
372        return Err(DecodeError::Frame(format!(
373            "frame length {len}B exceeds cap {MAX_FRAME_BYTES}B"
374        )));
375    }
376    match buf.get(4..4 + len) {
377        Some(payload) => Ok(Some((payload, 4 + len))),
378        None => Ok(None),
379    }
380}
381
382#[cfg(test)]
383mod tests {
384    use super::*;
385    use std::time::{Duration, Instant};
386
387    #[test]
388    fn given_a_payload_when_framed_then_should_round_trip() {
389        let framed = frame_encode(b"hello").expect("frames");
390        assert_eq!(&framed[..4], &5u32.to_le_bytes());
391        let (payload, consumed) = frame_decode(&framed)
392            .expect("decodes")
393            .expect("whole frame present");
394        assert_eq!(payload, b"hello");
395        assert_eq!(consumed, framed.len());
396    }
397
398    #[test]
399    fn given_a_partial_frame_when_decoded_then_should_ask_for_more() {
400        let framed = frame_encode(b"hello").expect("frames");
401        assert!(frame_decode(&framed[..3]).expect("no error").is_none());
402        assert!(frame_decode(&framed[..6]).expect("no error").is_none());
403    }
404
405    #[test]
406    fn given_an_oversized_length_prefix_when_decoded_then_should_error() {
407        let mut bad = Vec::new();
408        bad.extend_from_slice(&((MAX_FRAME_BYTES as u32) + 1).to_le_bytes());
409        assert!(matches!(frame_decode(&bad), Err(DecodeError::Frame(_))));
410    }
411
412    #[test]
413    fn given_named_encoding_when_round_tripped_then_should_preserve_fields() {
414        #[derive(serde::Serialize, serde::Deserialize, PartialEq, Debug)]
415        #[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
416        struct Body {
417            id: u32,
418            name: String,
419        }
420        let body = Body {
421            id: 7,
422            name: "alice".to_owned(),
423        };
424        let bytes = encode_named(&body).expect("encodes");
425        let back: Body = decode_named(&bytes).expect("decodes");
426        assert_eq!(back, body);
427    }
428
429    #[test]
430    fn given_trailing_bytes_when_decoded_then_should_error() {
431        let mut bytes = encode_named(&7u32).expect("encodes");
432        bytes.push(0x00);
433        assert!(matches!(
434            decode_named::<u32>(&bytes),
435            Err(DecodeError::Decode(_))
436        ));
437    }
438    #[test]
439    fn given_the_in_place_encoder_when_reused_then_should_match_encode_named_bytes() {
440        let value = serde_json::json!({"a": 1, "b": "two"});
441        let mut buffer = vec![0xff; 64]; // dirty, to prove the clear
442        super::encode_named_into(&value, &mut buffer).expect("encodes");
443        assert_eq!(buffer, super::encode_named(&value).expect("encodes"));
444    }
445
446    #[test]
447    fn given_the_framed_encoder_when_used_then_should_prefix_the_named_bytes_and_cap_them() {
448        let value = serde_json::json!({"a": 1, "b": "two"});
449        let framed = encode_named_framed(&value, 16, 1024).expect("frames");
450        let encoded = encode_named(&value).expect("encodes");
451        assert_eq!(&framed[..4], &(encoded.len() as u32).to_le_bytes());
452        assert_eq!(&framed[4..], &encoded);
453        assert_eq!(
454            encode_named_framed(&value, 16, encoded.len()).expect("exact cap frames"),
455            framed
456        );
457        assert!(matches!(
458            encode_named_framed(&value, 16, encoded.len() - 1),
459            Err(DecodeError::Frame(_))
460        ));
461    }
462
463    #[test]
464    fn given_a_payload_at_the_frame_cap_when_framed_then_should_round_trip_and_refuse_one_byte_more()
465     {
466        let over = vec![7u8; MAX_FRAME_BYTES + 1];
467        let payload = &over[..MAX_FRAME_BYTES];
468        let framed = frame_encode(payload).expect("a payload at the cap frames");
469        assert_eq!(&framed[..4], &(MAX_FRAME_BYTES as u32).to_le_bytes());
470        let (decoded, consumed) = frame_decode(&framed)
471            .expect("a frame at the cap decodes")
472            .expect("whole frame present");
473        assert!(decoded == payload, "the payload round trips");
474        assert_eq!(consumed, framed.len());
475        assert!(matches!(frame_encode(&over), Err(DecodeError::Frame(_))));
476    }
477
478    #[derive(serde::Serialize)]
479    #[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
480    struct Keyed {
481        v: u32,
482        namespace: String,
483        #[serde(default, skip_serializing_if = "Option::is_none")]
484        session: Option<String>,
485        #[cfg_attr(
486            feature = "schemars",
487            schemars(schema_with = "crate::encoding::bytes_schema")
488        )]
489        #[serde(with = "crate::encoding::bin_bytes")]
490        value: Vec<u8>,
491    }
492
493    fn distinct_fields(count: u32) -> Vec<u8> {
494        let mut payload = vec![0xba];
495        payload.extend_from_slice(&count.to_be_bytes());
496        for index in 0..count {
497            payload.extend(text(&format!("f{index}")));
498            payload.push(0xf6);
499        }
500        payload
501    }
502
503    fn fastest_scan(payload: &[u8]) -> Duration {
504        (0..3)
505            .map(|_| {
506                let started = Instant::now();
507                NamedFields::decode(payload).expect("distinct fields scan");
508                started.elapsed()
509            })
510            .min()
511            .unwrap_or_default()
512    }
513
514    fn text(value: &str) -> Vec<u8> {
515        let mut bytes = vec![0x60 | value.len() as u8];
516        bytes.extend_from_slice(value.as_bytes());
517        bytes
518    }
519
520    // One pass finds every field, and the large byte string is a window into
521    // the payload rather than a copy of it.
522    #[test]
523    fn given_a_named_map_when_scanned_then_should_find_each_value_in_place() {
524        let keyed = Keyed {
525            v: 1,
526            namespace: "notes".to_owned(),
527            session: None,
528            value: vec![7; 8 << 20],
529        };
530        let payload = encode_named(&keyed).expect("encodes");
531        let fields = NamedFields::decode(&payload).expect("scans");
532        assert_eq!(fields.text("namespace").expect("text"), Some("notes"));
533        assert_eq!(fields.value::<u32>("v").expect("value"), Some(1));
534        assert_eq!(fields.text("session").expect("absent"), None);
535        assert_eq!(fields.value::<u32>("session").expect("absent"), None);
536        let value = fields.get("value").expect("present");
537        assert!(value.len() > 8 << 20);
538        let range = payload.as_ptr_range();
539        assert!(
540            range.contains(&value.as_ptr()) && value.as_ptr_range().end <= range.end,
541            "the value is borrowed from the payload"
542        );
543        assert!(
544            matches!(fields.text("value"), Err(DecodeError::Decode(_))),
545            "a byte string is not text"
546        );
547        assert!(
548            matches!(
549                fields.value::<u32>("namespace"),
550                Err(DecodeError::Decode(_))
551            ),
552            "text is not a number"
553        );
554    }
555
556    #[test]
557    fn given_indefinite_and_nested_values_when_scanned_then_should_step_over_them() {
558        // {"a": [1, {"x": "y"}], "b": (_ "ab" "cd"), "c": 1(2), "d": null}
559        let mut payload = vec![0xbf];
560        payload.extend(text("a"));
561        payload.extend([0x9f, 0x01, 0xa1]);
562        payload.extend(text("x"));
563        payload.extend(text("y"));
564        payload.push(0xff);
565        payload.extend(text("b"));
566        payload.extend([0x7f, 0x62, b'a', b'b', 0x62, b'c', b'd', 0xff]);
567        payload.extend(text("c"));
568        payload.extend([0xc1, 0x02]);
569        payload.extend(text("d"));
570        payload.push(0xf6);
571        payload.push(0xff);
572        let fields = NamedFields::decode(&payload).expect("scans");
573        assert_eq!(fields.get("a"), Some(&payload[3..11]));
574        assert_eq!(
575            fields.value::<String>("b").expect("joined"),
576            Some("abcd".to_owned())
577        );
578        assert!(
579            matches!(fields.text("b"), Err(DecodeError::Decode(_))),
580            "a borrowed text is definite"
581        );
582        assert_eq!(fields.value::<u32>("c").expect("tagged"), Some(2));
583        assert_eq!(fields.text("d").expect("null reads as absent"), None);
584        assert_eq!(fields.value::<Option<u32>>("d").expect("null"), Some(None));
585    }
586
587    #[test]
588    fn given_heads_with_one_two_and_eight_byte_arguments_when_scanned_then_should_find_each_value()
589    {
590        // {"a": 24 bytes, "b": 256 bytes, "c": 1 as a 64-bit integer}
591        let mut payload = vec![0xa3];
592        payload.extend(text("a"));
593        let one = payload.len();
594        payload.extend([0x58, 24]);
595        payload.extend([7; 24]);
596        let one_end = payload.len();
597        payload.extend(text("b"));
598        let two = payload.len();
599        payload.extend([0x59, 0x01, 0x00]);
600        payload.extend([7; 256]);
601        let two_end = payload.len();
602        payload.extend(text("c"));
603        let eight = payload.len();
604        payload.extend([0x1b, 0, 0, 0, 0, 0, 0, 0, 1]);
605        let fields = NamedFields::decode(&payload).expect("scans");
606        assert_eq!(fields.get("a"), Some(&payload[one..one_end]));
607        assert_eq!(fields.get("b"), Some(&payload[two..two_end]));
608        assert_eq!(fields.get("c"), Some(&payload[eight..]));
609    }
610
611    #[test]
612    fn given_arrays_nested_to_the_scan_bound_when_scanned_then_should_accept_them_and_refuse_one_more()
613     {
614        let bound = MAX_SCAN_DEPTH as usize;
615        for (levels, accepted) in [(bound, true), (bound + 1, false)] {
616            let mut payload = vec![0xa1];
617            payload.extend(text("a"));
618            payload.extend(std::iter::repeat_n(0x81, levels));
619            payload.push(0x01);
620            assert_eq!(
621                NamedFields::decode(&payload).is_ok(),
622                accepted,
623                "levels: {levels}"
624            );
625        }
626    }
627
628    #[test]
629    fn given_nesting_past_the_scan_bound_in_any_container_when_scanned_then_should_refuse_it() {
630        let levels = MAX_SCAN_DEPTH as usize + 1;
631        let nested = |open: &[u8], close: &[u8]| {
632            let mut payload = vec![0xa1];
633            payload.extend(text("a"));
634            for _ in 0..levels {
635                payload.extend_from_slice(open);
636            }
637            payload.push(0x01);
638            for _ in 0..levels {
639                payload.extend_from_slice(close);
640            }
641            payload
642        };
643        for (case, payload) in [
644            ("map keys", nested(&[0xa1], &[0x01])),
645            ("map values", nested(&[0xa1, 0x01], &[])),
646            ("indefinite arrays", nested(&[0x9f], &[0xff])),
647            ("tags", nested(&[0xc1], &[])),
648        ] {
649            assert!(
650                matches!(NamedFields::decode(&payload), Err(DecodeError::Decode(_))),
651                "{case} must be refused"
652            );
653        }
654    }
655
656    #[test]
657    fn given_a_nested_indefinite_map_when_scanned_then_should_accept_only_whole_pairs() {
658        let field = |value: &[u8]| {
659            let mut payload = vec![0xa1];
660            payload.extend(text("a"));
661            payload.extend_from_slice(value);
662            payload
663        };
664        assert!(
665            matches!(
666                NamedFields::decode(&field(&[0xbf, 0x01, 0xff])),
667                Err(DecodeError::Decode(_))
668            ),
669            "a key without a value must be refused"
670        );
671        for (case, value) in [
672            ("one pair", &[0xbf, 0x01, 0x02, 0xff][..]),
673            ("an odd array", &[0x9f, 0x01, 0xff][..]),
674        ] {
675            let payload = field(value);
676            let fields = NamedFields::decode(&payload).expect(case);
677            assert_eq!(fields.get("a"), Some(value), "{case}");
678        }
679    }
680
681    #[test]
682    fn given_a_named_map_with_many_distinct_fields_when_scanned_then_should_check_them_in_linearithmic_time()
683     {
684        // Eight times the fields cost about ten times the work when linearithmic and 64 when quadratic.
685        let small = fastest_scan(&distinct_fields(10_000));
686        let large_payload = distinct_fields(80_000);
687        let large = fastest_scan(&large_payload);
688
689        assert!(
690            large < small.max(Duration::from_micros(100)) * 32,
691            "80,000 fields took {large:?}, 10,000 took {small:?}"
692        );
693        let fields = NamedFields::decode(&large_payload).expect("distinct fields scan");
694        assert_eq!(fields.get("f79999"), Some(&[0xf6_u8][..]));
695        let mut repeated = large_payload;
696        repeated.extend(text("f7"));
697        repeated.push(0xf6);
698        repeated[1..5].copy_from_slice(&80_001_u32.to_be_bytes());
699        assert!(matches!(
700            NamedFields::decode(&repeated),
701            Err(DecodeError::Decode(_))
702        ));
703    }
704
705    #[test]
706    fn given_a_named_map_over_the_field_bound_when_scanned_within_it_then_should_refuse_it() {
707        for indefinite in [false, true] {
708            let mut payload = if indefinite { vec![0xbf] } else { vec![0xa3] };
709            for key in ["a", "b", "c"] {
710                payload.extend(text(key));
711                payload.push(0x01);
712            }
713            if indefinite {
714                payload.push(0xff);
715            }
716
717            assert!(
718                matches!(
719                    NamedFields::decode_within(&payload, 2),
720                    Err(DecodeError::Decode(_))
721                ),
722                "indefinite: {indefinite}"
723            );
724            let within = NamedFields::decode_within(&payload, 3).expect("three fields fit");
725            assert_eq!(within.get("c"), Some(&[0x01_u8][..]));
726        }
727    }
728
729    #[test]
730    fn given_malformed_named_maps_when_scanned_then_should_refuse_them() {
731        let mut duplicate = vec![0xa2];
732        duplicate.extend(text("a"));
733        duplicate.push(0x01);
734        duplicate.extend(text("a"));
735        duplicate.push(0x02);
736        let mut trailing = vec![0xa1];
737        trailing.extend(text("a"));
738        trailing.extend([0x01, 0x00]);
739        let mut numeric_key = vec![0xa1, 0x01, 0x01];
740        let mut truncated = vec![0xa1];
741        truncated.extend(text("a"));
742        truncated.extend([0x45, 0x01, 0x02]);
743        let mut odd = vec![0xbf];
744        odd.extend(text("a"));
745        odd.extend([0x01, 0xbf, 0x01, 0xff, 0xff]);
746        let mut deep = vec![0xa1];
747        deep.extend(text("a"));
748        deep.extend(std::iter::repeat_n(0x81, MAX_SCAN_DEPTH as usize + 2));
749        deep.push(0x01);
750        let mut reserved = vec![0xa1];
751        reserved.extend(text("a"));
752        reserved.push(0x1c);
753        let mut indefinite_number = vec![0xa1];
754        indefinite_number.extend(text("a"));
755        indefinite_number.push(0x1f);
756        numeric_key.push(0x00);
757        numeric_key.truncate(3);
758        for (case, payload) in [
759            ("duplicate", duplicate),
760            ("trailing", trailing),
761            ("numeric key", numeric_key),
762            ("truncated", truncated),
763            ("odd indefinite map", odd),
764            ("deep", deep),
765            ("reserved info", reserved),
766            ("indefinite number", indefinite_number),
767            ("not a map", vec![0x01]),
768            ("empty", Vec::new()),
769        ] {
770            assert!(
771                matches!(NamedFields::decode(&payload), Err(DecodeError::Decode(_))),
772                "{case} must be refused"
773            );
774        }
775        assert!(
776            NamedFields::decode(&[0xa0])
777                .expect("empty map")
778                .get("a")
779                .is_none()
780        );
781    }
782}