Skip to main content

hyprstream_pds/
dag_cbor.rs

1//! Hyprstream's existing deterministic CBOR encoding/decoding.
2//!
3//! Compatibility note: this codec uses lexical text-key ordering. Public
4//! AT Protocol DAG-CBOR instead orders encoded keys (length first). Use
5//! [`crate::atproto_cbor`] for that explicit boundary. Existing native signed
6//! artifacts retain this codec; do not silently change their bytes or verifier.
7//!
8//! DAG-CBOR is a restricted subset of [CBOR (RFC 7049)](https://tools.ietf.org/html/rfc7049)
9//! with additional constraints so that a given value always produces the
10//! **exact same bytes** — and therefore the same CID. This determinism is
11//! load-bearing for the MST (whose internal CIDs are computed over DAG-CBOR
12//! node bytes) and for the commit signature (which signs DAG-CBOR bytes).
13//!
14//! # Constraints enforced here
15//!
16//! 1. **Map keys are sorted** in pure lexicographic text-byte order, preserving
17//!    the existing native format. This differs from public DAG-CBOR ordering.
18//! 2. **Integers use minimal encoding**: `u8` < 24 → one byte (major 0/1);
19//!    otherwise the smallest power-of-two width (1/2/4/8 bytes).
20//! 3. **No duplicate keys**: decoding rejects them.
21//! 4. **Map keys are text strings**: DAG-CBOR does not allow non-string keys.
22//! 5. **Recursion is bounded**: decoding rejects containers nested deeper than
23//!    [`MAX_RECURSION_DEPTH`] instead of risking stack overflow.
24//! 6. **CIDs are CBOR tag 42** byte strings carrying the DAG-CBOR link payload
25//!    (leading 0x00 identity marker + raw CID bytes), per the
26//!    [DAG-CBOR spec](https://github.com/ipld/specs/blob/master/block-layer/codecs/dag-cbor.md).
27//! 7. **Tag 42 byte strings are reserved**: any non-CID byte string is decoded
28//!    as [`DagCbor::Bytes`], never confused with a link.
29//!
30//! # Why a custom enum rather than `serde` + `ciborium` directly
31//!
32//! `serde`-driven CBOR cannot (a) guarantee map key ordering for arbitrary
33//! structs without a manual sorted-map type, nor (b) round-trip CBOR tag 42
34//! links as first-class values. By going through a small typed [`DagCbor`]
35//! enum we make both invariants explicit and verifiable in tests (same record
36//! → same bytes → same CID).
37
38use anyhow::{anyhow, bail, ensure, Result};
39
40use crate::cid::Cid;
41
42/// CBOR major types (RFC 7049 §3.1).
43const MT_UNSIGNED: u8 = 0;
44const MT_NEGATIVE: u8 = 1;
45const MT_BYTES: u8 = 2;
46const MT_TEXT: u8 = 3;
47const MT_ARRAY: u8 = 4;
48const MT_MAP: u8 = 5;
49const MT_TAG: u8 = 6;
50const MT_SIMPLE: u8 = 7;
51
52/// The CBOR tag identifying a DAG-CBOR link (CID).
53const TAG_CID: u64 = 42;
54
55/// Maximum nested container/link depth accepted by [`DagCbor::decode`].
56const MAX_RECURSION_DEPTH: usize = 128;
57
58/// A typed DAG-CBOR value.
59///
60/// Construction is deliberate (no `From<&str>` footguns): callers build the
61/// exact shape they need via [`DagCbor::map`] / [`DagCbor::list`] / etc., so
62/// the determinism rules (sorted keys, minimal ints, tag-42 links) are enforced
63/// at encode time rather than relying on the input order.
64#[derive(Clone, Debug, PartialEq)]
65pub enum DagCbor {
66    Null,
67    Bool(bool),
68    /// Non-negative integer (CBOR major 0).
69    Unsigned(u64),
70    /// Negative integer (CBOR major 1); `-1 - n`.
71    ///
72    /// **Invariant:** the wrapped value MUST be `< 0`. The variant encodes as
73    /// CBOR major type 1 (`-1 - n`); a non-negative `n` has no valid encoding
74    /// there and is a programmer error caught (loudly, in release too) at
75    /// [`DagCbor::encode`]. Construct negatives via literal `i128` values
76    /// (`DagCbor::Negative(-1)`) — never compute `Negative(x)` from an
77    /// unbounded `x` without first checking `x < 0`.
78    Negative(i128),
79    /// Byte string (major 2).
80    Bytes(Vec<u8>),
81    /// UTF-8 text string (major 3).
82    Text(String),
83    /// Array (major 4), in given order.
84    List(Vec<DagCbor>),
85    /// Map (major 5). Keys are stored in the existing native lexical text-byte
86    /// order at construction; public AT ordering is applied by
87    /// [`crate::atproto_cbor`] at its explicit boundary.
88    Map(Vec<(DagCbor, DagCbor)>),
89    /// CID link — encoded as CBOR tag 42.
90    Link(Cid),
91}
92
93impl DagCbor {
94    /// Convenience: empty map.
95    pub fn map() -> Self {
96        DagCbor::Map(Vec::new())
97    }
98
99    /// Convenience: build a map from key/value string pairs, sorted canonically.
100    ///
101    /// Only string keys are supported here (the common case for records/commits).
102    /// For non-string keys build the `Map` variant manually.
103    pub fn str_map(pairs: impl IntoIterator<Item = (impl Into<String>, DagCbor)>) -> Self {
104        let mut v: Vec<(String, DagCbor)> = pairs.into_iter().map(|(k, v)| (k.into(), v)).collect();
105        v.sort_by(|a, b| canonical_key_cmp(a.0.as_bytes(), b.0.as_bytes()));
106        // Reject duplicate keys — they'd silently collapse in CBOR and produce
107        // a CID-collision risk across implementations. This is a programmer
108        // error (the caller fed the same key twice), so it is a hard,
109        // always-on panic rather than a `debug_assert!` that vanishes in
110        // release builds and lets duplicate keys reach the wire.
111        if let Some(i) = v.windows(2).position(|w| w[0].0 == w[1].0) {
112            panic!("duplicate DAG-CBOR map key: {:?}", v[i].0);
113        }
114        let sorted = v
115            .into_iter()
116            .map(|(k, val)| (DagCbor::Text(k), val))
117            .collect();
118        DagCbor::Map(sorted)
119    }
120
121    /// Convenience: build a list.
122    pub fn list(items: impl IntoIterator<Item = DagCbor>) -> Self {
123        DagCbor::List(items.into_iter().collect())
124    }
125
126    // ── Encoding ────────────────────────────────────────────────────────────
127
128    /// Encode to canonical DAG-CBOR bytes.
129    pub fn encode(&self) -> Vec<u8> {
130        let mut out = Vec::new();
131        self.write(&mut out);
132        out
133    }
134
135    fn write(&self, out: &mut Vec<u8>) {
136        match self {
137            DagCbor::Null => write_head(out, MT_SIMPLE, 22), // 0xf6
138            DagCbor::Bool(false) => write_head(out, MT_SIMPLE, 20), // 0xf4
139            DagCbor::Bool(true) => write_head(out, MT_SIMPLE, 21), // 0xf5
140            DagCbor::Unsigned(n) => write_uint(out, MT_UNSIGNED, *n),
141            DagCbor::Negative(n) => {
142                // CBOR encodes negatives as -1 - n in major type 1 (uint).
143                // The variant invariant requires n < 0; a non-negative value is
144                // a programmer error (it belongs in `Unsigned`), and computing
145                // `-1 - n` then casting to u64 would silently mis-encode it.
146                // Reject loudly in release as well as debug.
147                assert!(
148                    *n < 0,
149                    "DagCbor::Negative must hold a negative value; got {n} (use Unsigned instead)"
150                );
151                let val = (-1_i128 - n) as u64;
152                write_uint(out, MT_NEGATIVE, val);
153            }
154            DagCbor::Bytes(b) => {
155                write_uint(out, MT_BYTES, b.len() as u64);
156                out.extend_from_slice(b);
157            }
158            DagCbor::Text(s) => {
159                write_uint(out, MT_TEXT, s.len() as u64);
160                out.extend_from_slice(s.as_bytes());
161            }
162            DagCbor::List(items) => {
163                write_uint(out, MT_ARRAY, items.len() as u64);
164                for it in items {
165                    it.write(out);
166                }
167            }
168            DagCbor::Map(pairs) => {
169                write_uint(out, MT_MAP, pairs.len() as u64);
170                for (k, v) in pairs {
171                    k.write(out);
172                    v.write(out);
173                }
174            }
175            DagCbor::Link(cid) => {
176                // Tag 42 + byte string of the link payload (0x00 marker + CID).
177                write_uint(out, MT_TAG, TAG_CID);
178                let link = cid.to_link_bytes();
179                write_uint(out, MT_BYTES, link.len() as u64);
180                out.extend_from_slice(&link);
181            }
182        }
183    }
184
185    // ── Decoding ────────────────────────────────────────────────────────────
186
187    /// Decode canonical DAG-CBOR bytes, enforcing the determinism constraints:
188    /// sorted text keys, no duplicates, bounded recursion, and minimal integer
189    /// and length widths on the wire.
190    pub fn decode(input: &[u8]) -> Result<Self> {
191        Self::decode_with_order(input, canonical_key_cmp)
192    }
193
194    pub(crate) fn decode_with_order(
195        input: &[u8],
196        key_order: fn(&[u8], &[u8]) -> std::cmp::Ordering,
197    ) -> Result<Self> {
198        let mut cursor = 0usize;
199        let val = Self::read(input, &mut cursor, 0, key_order)?;
200        ensure!(cursor == input.len(), "trailing bytes after DAG-CBOR value");
201        Ok(val)
202    }
203
204    fn read(
205        input: &[u8],
206        cursor: &mut usize,
207        depth: usize,
208        key_order: fn(&[u8], &[u8]) -> std::cmp::Ordering,
209    ) -> Result<Self> {
210        ensure!(
211            depth <= MAX_RECURSION_DEPTH,
212            "DepthLimitExceeded: DAG-CBOR nesting exceeds {MAX_RECURSION_DEPTH}"
213        );
214        let head = *input
215            .get(*cursor)
216            .ok_or_else(|| anyhow!("truncated DAG-CBOR (need at least one byte)"))?;
217        *cursor += 1;
218        let major = head >> 5;
219        let info = head & 0x1f;
220
221        // Tag 42 → link.
222        if major == MT_TAG {
223            let tag = read_arg(info, input, cursor)?;
224            ensure!(
225                tag == TAG_CID,
226                "only CBOR tag 42 (CID link) is supported, got {tag}"
227            );
228            // Next item must be a byte string carrying the link payload.
229            return Self::read_link_payload(input, cursor);
230        }
231
232        match major {
233            MT_UNSIGNED => Ok(DagCbor::Unsigned(read_arg(info, input, cursor)?)),
234            MT_NEGATIVE => {
235                let n = read_arg(info, input, cursor)?;
236                // Decode major-1 uint into -1 - n as i128.
237                Ok(DagCbor::Negative(-1_i128 - n as i128))
238            }
239            MT_BYTES => {
240                let len = read_arg(info, input, cursor)? as usize;
241                let b = take(input, cursor, len)?;
242                Ok(DagCbor::Bytes(b.to_vec()))
243            }
244            MT_TEXT => {
245                let len = read_arg(info, input, cursor)? as usize;
246                let b = take(input, cursor, len)?;
247                let s =
248                    String::from_utf8(b.to_vec()).map_err(|_| anyhow!("invalid UTF-8 in text"))?;
249                Ok(DagCbor::Text(s))
250            }
251            MT_ARRAY => {
252                let len = read_arg(info, input, cursor)? as usize;
253                // Cap preallocation by what the remaining input could possibly
254                // hold (each element needs at least 1 byte) — the length arg is
255                // untrusted and a huge value must not trigger a capacity panic.
256                let mut items = Vec::with_capacity(len.min(input.len().saturating_sub(*cursor)));
257                for _ in 0..len {
258                    items.push(Self::read(input, cursor, depth + 1, key_order)?);
259                }
260                Ok(DagCbor::List(items))
261            }
262            MT_MAP => {
263                let len = read_arg(info, input, cursor)? as usize;
264                // Same untrusted-length cap as the array arm (each entry needs
265                // at least 2 bytes, so remaining-input is a safe upper bound).
266                let mut pairs: Vec<(DagCbor, DagCbor)> =
267                    Vec::with_capacity(len.min(input.len().saturating_sub(*cursor)));
268                let mut prev_key: Option<Vec<u8>> = None;
269                for _ in 0..len {
270                    let k = Self::read(input, cursor, depth + 1, key_order)?;
271                    ensure!(
272                        matches!(k, DagCbor::Text(_)),
273                        "DAG-CBOR map key must be a text string"
274                    );
275                    let v = Self::read(input, cursor, depth + 1, key_order)?;
276                    // Enforce sorted + unique keys: compare against previous.
277                    let key_bytes = canonical_key_of(&k);
278                    if let Some(ref prev) = prev_key {
279                        ensure!(
280                            key_order(prev, &key_bytes) == std::cmp::Ordering::Less,
281                            "DAG-CBOR map keys not in canonical order / duplicate"
282                        );
283                    }
284                    prev_key = Some(key_bytes);
285                    pairs.push((k, v));
286                }
287                Ok(DagCbor::Map(pairs))
288            }
289            MT_TAG => bail!("unexpected CBOR tag (only tag 42/CID is supported)"),
290            MT_SIMPLE => match info {
291                20 => Ok(DagCbor::Bool(false)),
292                21 => Ok(DagCbor::Bool(true)),
293                22 => Ok(DagCbor::Null),
294                _ => bail!("unsupported CBOR simple value {info}"),
295            },
296            _ => bail!("unknown CBOR major type {major}"),
297        }
298    }
299
300    fn read_link_payload(input: &[u8], cursor: &mut usize) -> Result<Self> {
301        // Expect a byte-string item: head + payload.
302        let head = *input
303            .get(*cursor)
304            .ok_or_else(|| anyhow!("truncated DAG-CBOR link payload"))?;
305        *cursor += 1;
306        let major = head >> 5;
307        let info = head & 0x1f;
308        ensure!(
309            major == MT_BYTES,
310            "tag-42 must be followed by a byte string"
311        );
312        let len = read_arg(info, input, cursor)? as usize;
313        let payload = take(input, cursor, len)?;
314        let cid = Cid::from_link_bytes(payload)?;
315        Ok(DagCbor::Link(cid))
316    }
317
318    // ── Helpers to extract typed values (used by record/commit decode) ──────
319
320    pub fn as_str(&self) -> Result<&str> {
321        match self {
322            DagCbor::Text(s) => Ok(s),
323            _ => bail!("expected text string, got {:?}", self),
324        }
325    }
326    pub fn as_bytes(&self) -> Result<&[u8]> {
327        match self {
328            DagCbor::Bytes(b) => Ok(b),
329            _ => bail!("expected byte string, got {:?}", self),
330        }
331    }
332    pub fn as_unsigned(&self) -> Result<u64> {
333        match self {
334            DagCbor::Unsigned(n) => Ok(*n),
335            _ => bail!("expected unsigned int, got {:?}", self),
336        }
337    }
338    pub fn as_link(&self) -> Result<&Cid> {
339        match self {
340            DagCbor::Link(c) => Ok(c),
341            _ => bail!("expected CID link, got {:?}", self),
342        }
343    }
344    pub fn as_map(&self) -> Result<&[(DagCbor, DagCbor)]> {
345        match self {
346            DagCbor::Map(v) => Ok(v),
347            _ => bail!("expected map, got {:?}", self),
348        }
349    }
350    pub fn as_list(&self) -> Result<&[DagCbor]> {
351        match self {
352            DagCbor::List(v) => Ok(v),
353            _ => bail!("expected list, got {:?}", self),
354        }
355    }
356    /// Look up a string-keyed entry in a map.
357    pub fn get(&self, key: &str) -> Option<&DagCbor> {
358        if let DagCbor::Map(v) = self {
359            v.iter().find_map(|(k, val)| match k {
360                DagCbor::Text(s) if s == key => Some(val),
361                _ => None,
362            })
363        } else {
364            None
365        }
366    }
367    pub fn is_null(&self) -> bool {
368        matches!(self, DagCbor::Null)
369    }
370}
371
372// ── encoding primitives ──────────────────────────────────────────────────────
373
374fn write_head(out: &mut Vec<u8>, major: u8, info: u8) {
375    out.push((major << 5) | info);
376}
377
378/// Write a CBOR head with a major type and an unsigned argument, choosing the
379/// minimal-width encoding (RFC 7049 §3.9 determinism).
380fn write_uint(out: &mut Vec<u8>, major: u8, val: u64) {
381    let m = major << 5;
382    if val < 24 {
383        out.push(m | val as u8);
384    } else if val < 0x1_00 {
385        out.push(m | 24);
386        out.push(val as u8);
387    } else if val < 0x1_0000 {
388        out.push(m | 25);
389        out.extend_from_slice(&(val as u16).to_be_bytes());
390    } else if val < 0x1_0000_0000 {
391        out.push(m | 26);
392        out.extend_from_slice(&(val as u32).to_be_bytes());
393    } else {
394        out.push(m | 27);
395        out.extend_from_slice(&val.to_be_bytes());
396    }
397}
398
399/// Read the argument following a CBOR head byte, consuming the appropriate
400/// number of bytes from `input` (the full buffer) and advancing `cursor`.
401/// Non-minimal argument widths are rejected, matching canonical DAG-CBOR.
402fn read_arg(info: u8, input: &[u8], cursor: &mut usize) -> Result<u64> {
403    match info {
404        0..=23 => Ok(info as u64),
405        24 => {
406            let b = take(input, cursor, 1)?;
407            let val = b[0] as u64;
408            ensure!(val >= 24, "non-minimal CBOR integer encoding");
409            Ok(val)
410        }
411        25 => {
412            let b = take(input, cursor, 2)?;
413            let val = u16::from_be_bytes([b[0], b[1]]) as u64;
414            ensure!(val >= 0x1_00, "non-minimal CBOR integer encoding");
415            Ok(val)
416        }
417        26 => {
418            let b = take(input, cursor, 4)?;
419            let val = u32::from_be_bytes([b[0], b[1], b[2], b[3]]) as u64;
420            ensure!(val >= 0x1_0000, "non-minimal CBOR integer encoding");
421            Ok(val)
422        }
423        27 => {
424            let b = take(input, cursor, 8)?;
425            let val = u64::from_be_bytes([b[0], b[1], b[2], b[3], b[4], b[5], b[6], b[7]]);
426            ensure!(val >= 0x1_0000_0000, "non-minimal CBOR integer encoding");
427            Ok(val)
428        }
429        _ => bail!("invalid CBOR argument info {info}"),
430    }
431}
432
433/// Take `n` bytes starting at the absolute offset `*cursor` in `input`,
434/// advancing `cursor`. Bounds-checked against `input.len()`.
435fn take<'a>(input: &'a [u8], cursor: &mut usize, n: usize) -> Result<&'a [u8]> {
436    let end = input.len();
437    let cur = *cursor;
438    let abs_end = cur
439        .checked_add(n)
440        .ok_or_else(|| anyhow!("CBOR length overflow"))?;
441    if abs_end > end {
442        bail!(
443            "truncated DAG-CBOR: need {n} bytes at offset {cur}, have {}",
444            end.saturating_sub(cur)
445        );
446    }
447    let slice = &input[cur..abs_end];
448    *cursor = abs_end;
449    Ok(slice)
450}
451
452// ── native key ordering ──────────────────────────────────────────────────────
453
454/// Canonical comparison for a map key: returns the "canonical key" byte
455/// representation used both for sorting at construction and for verifying order
456/// at decode. Native map keys are text strings, so this is always UTF-8 bytes.
457fn canonical_key_of(key: &DagCbor) -> Vec<u8> {
458    match key {
459        DagCbor::Text(s) => s.as_bytes().to_vec(),
460        _ => Vec::new(), // non-string keys are rejected before ordering is checked
461    }
462}
463
464/// Preserve the existing native codec's lexical text-key ordering. Public
465/// AT Protocol ordering is separate in `atproto_cbor`; do not change this
466/// comparator without an explicit migration of native signed artifacts.
467fn canonical_key_cmp(a: &[u8], b: &[u8]) -> std::cmp::Ordering {
468    a.cmp(b)
469}
470
471#[cfg(test)]
472mod tests {
473    #![allow(
474        clippy::unwrap_used,
475        clippy::expect_used,
476        clippy::indexing_slicing,
477        clippy::panic
478    )]
479    use super::*;
480
481    #[test]
482    fn encode_deterministic_text_map() {
483        // Order of insertion must NOT affect the encoded bytes.
484        let a = DagCbor::str_map([("b", DagCbor::Unsigned(2)), ("a", DagCbor::Unsigned(1))]);
485        let b = DagCbor::str_map([("a", DagCbor::Unsigned(1)), ("b", DagCbor::Unsigned(2))]);
486        assert_eq!(a.encode(), b.encode(), "str_map must canonicalize order");
487    }
488
489    #[test]
490    fn round_trip_primitives() {
491        for v in [
492            DagCbor::Null,
493            DagCbor::Bool(true),
494            DagCbor::Bool(false),
495            DagCbor::Unsigned(0),
496            DagCbor::Unsigned(20),
497            DagCbor::Unsigned(21),
498            DagCbor::Unsigned(22),
499            DagCbor::Unsigned(23),
500            DagCbor::Unsigned(24),
501            DagCbor::Unsigned(0x1_0000),
502            DagCbor::Unsigned(u64::MAX),
503            DagCbor::Negative(-1),
504            DagCbor::Negative(-100),
505            DagCbor::Bytes(vec![1, 2, 3]),
506            DagCbor::Text("hello".into()),
507            DagCbor::list([DagCbor::Unsigned(1), DagCbor::Text("x".into())]),
508        ] {
509            let enc = v.encode();
510            let dec = DagCbor::decode(&enc).expect("round-trip");
511            assert_eq!(v, dec, "round-trip {:?}", v);
512        }
513    }
514
515    #[test]
516    fn round_trip_map_with_link() {
517        let cid = Cid::from_dag_cbor(b"block");
518        let v = DagCbor::str_map([
519            ("data", DagCbor::Link(cid)),
520            ("did", DagCbor::Text("did:web:example.com".into())),
521        ]);
522        let enc = v.encode();
523        let dec = DagCbor::decode(&enc).expect("round-trip");
524        assert_eq!(v, dec);
525    }
526
527    #[test]
528    fn decode_huge_array_header_errors_not_panics() {
529        // 0x9b = array with 8-byte length arg; length claims 2^64-1 elements
530        // but the input is only 9 bytes. Must return Err — not panic with a
531        // capacity overflow or attempt a huge allocation.
532        let input = [0x9b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff];
533        assert!(DagCbor::decode(&input).is_err());
534    }
535
536    #[test]
537    fn decode_huge_map_header_errors_not_panics() {
538        // 0xbb = map with 8-byte length arg claiming 2^64-1 entries.
539        let input = [0xbb, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff];
540        assert!(DagCbor::decode(&input).is_err());
541    }
542
543    #[test]
544    fn decode_deep_nesting_hits_depth_limit() {
545        let input = vec![0x81; 200 * 1024];
546        let err = DagCbor::decode(&input).expect_err("deep nesting must fail");
547        assert!(
548            err.to_string().contains("DepthLimitExceeded"),
549            "unexpected error: {err:#}"
550        );
551    }
552
553    #[test]
554    fn decode_rejects_non_string_map_key() {
555        // { 1: 2 } is valid generic CBOR, but DAG-CBOR map keys must be text.
556        let input = [0xa1, 0x01, 0x02];
557        let err = DagCbor::decode(&input).expect_err("integer key must fail");
558        assert!(
559            err.to_string().contains("map key must be a text string"),
560            "unexpected error: {err:#}"
561        );
562    }
563
564    #[test]
565    fn decode_rejects_non_minimal_unsigned_integer() {
566        // 23 encoded with additional-info 24 instead of the single-byte form.
567        let input = [0x18, 0x17];
568        let err = DagCbor::decode(&input).expect_err("non-minimal int must fail");
569        assert!(
570            err.to_string()
571                .contains("non-minimal CBOR integer encoding"),
572            "unexpected error: {err:#}"
573        );
574    }
575
576    #[test]
577    fn decode_rejects_unsorted_keys() {
578        // Hand-build a map with keys in WRONG order; decode must reject it.
579        let bad = {
580            let mut out = Vec::new();
581            write_head(&mut out, MT_MAP, 2);
582            // emit "b" then "a" — wrong canonical order.
583            write_uint(&mut out, MT_TEXT, 1);
584            out.push(b'b');
585            write_uint(&mut out, MT_UNSIGNED, 1);
586            write_uint(&mut out, MT_TEXT, 1);
587            out.push(b'a');
588            write_uint(&mut out, MT_UNSIGNED, 0);
589            out
590        };
591        assert!(
592            DagCbor::decode(&bad).is_err(),
593            "unsorted map keys must fail"
594        );
595    }
596
597    #[test]
598    fn canonical_key_order_is_pure_lex_not_length_first() {
599        // The placement `node` record's 5 keys. Their pure-lexicographic byte
600        // order (`createdAt, groups, labels, repo, resources`) differs from the
601        // length-first-then-lex order atproto rejects (`repo, groups, labels,
602        // createdAt, resources`), so this fixture is a real discriminator.
603        // Lock the pure-lex bytes: a "fix" toward length-first (the older RFC
604        // 7049 §3.9 "canonical CBOR" form) would silently break CID/CAR interop
605        // against every other atproto implementation.
606        let keys = ["repo", "labels", "resources", "groups", "createdAt"];
607        let map = DagCbor::str_map(keys.into_iter().map(|k| (k, DagCbor::Unsigned(1))));
608        let decoded = DagCbor::decode(&map.encode()).expect("round-trip");
609        let emitted: Vec<&str> = decoded
610            .as_map()
611            .expect("map")
612            .iter()
613            .map(|(k, _)| k.as_str().expect("text key"))
614            .collect();
615        assert_eq!(
616            emitted,
617            vec!["createdAt", "groups", "labels", "repo", "resources"],
618            "DAG-CBOR map keys must be pure-lexicographic byte order"
619        );
620        assert_ne!(
621            emitted,
622            vec!["repo", "groups", "labels", "createdAt", "resources"],
623            "length-first-then-lex order is the rejected RFC 7049 §3.9 form"
624        );
625    }
626
627    #[test]
628    fn encode_minimal_widths() {
629        // Determinism: minimal-width integer heads.
630        assert_eq!(DagCbor::Unsigned(0).encode(), vec![0x00]);
631        assert_eq!(DagCbor::Bool(false).encode(), vec![0xf4]);
632        assert_eq!(DagCbor::Bool(true).encode(), vec![0xf5]);
633        assert_eq!(DagCbor::Null.encode(), vec![0xf6]);
634        assert_eq!(DagCbor::Unsigned(20).encode(), vec![20]);
635        assert_eq!(DagCbor::Unsigned(23).encode(), vec![23]);
636        assert_eq!(DagCbor::Unsigned(24).encode(), vec![24, 24]);
637        assert_eq!(
638            DagCbor::Unsigned(256).encode(),
639            vec![0x19, 0x01, 0x00],
640            "u16 must use head 25"
641        );
642    }
643
644    /// Issue #934: duplicate keys fed to `str_map` must be a *hard* error in
645    /// release builds too, not a silent `debug_assert!` that lets two keys
646    /// collapse on the wire (a CID-collision risk across implementations).
647    #[test]
648    #[should_panic(expected = "duplicate DAG-CBOR map key")]
649    fn str_map_rejects_duplicate_keys_in_release() {
650        let _ = DagCbor::str_map([("a", DagCbor::Unsigned(1)), ("a", DagCbor::Unsigned(2))]);
651    }
652
653    /// Issue #934: `Negative(n)` with `n >= 0` has no valid CBOR major-1
654    /// encoding and must be rejected at encode (loudly, in release too) rather
655    /// than silently mis-encoded via the `-1 - n` cast.
656    #[test]
657    #[should_panic(expected = "must hold a negative value")]
658    fn negative_must_be_negative() {
659        // 0 and positive values belong in `Unsigned`; encoding them through
660        // `Negative` would wrap `-1 - n as u64` into a huge bogus major-1 arg.
661        DagCbor::Negative(0).encode();
662    }
663
664    #[test]
665    fn negative_boundary_round_trips() {
666        // The smallest representable negative (-1) and a deep negative both
667        // round-trip correctly through the validated encode path.
668        for n in [
669            DagCbor::Negative(-1),
670            DagCbor::Negative(-24),
671            DagCbor::Negative(-256),
672        ] {
673            let dec = DagCbor::decode(&n.encode()).expect("round-trip");
674            assert_eq!(n, dec);
675        }
676    }
677}