1use anyhow::{anyhow, bail, ensure, Result};
39
40use crate::cid::Cid;
41
42const 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
52const TAG_CID: u64 = 42;
54
55const MAX_RECURSION_DEPTH: usize = 128;
57
58#[derive(Clone, Debug, PartialEq)]
65pub enum DagCbor {
66 Null,
67 Bool(bool),
68 Unsigned(u64),
70 Negative(i128),
79 Bytes(Vec<u8>),
81 Text(String),
83 List(Vec<DagCbor>),
85 Map(Vec<(DagCbor, DagCbor)>),
89 Link(Cid),
91}
92
93impl DagCbor {
94 pub fn map() -> Self {
96 DagCbor::Map(Vec::new())
97 }
98
99 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 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 pub fn list(items: impl IntoIterator<Item = DagCbor>) -> Self {
123 DagCbor::List(items.into_iter().collect())
124 }
125
126 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), DagCbor::Bool(false) => write_head(out, MT_SIMPLE, 20), DagCbor::Bool(true) => write_head(out, MT_SIMPLE, 21), DagCbor::Unsigned(n) => write_uint(out, MT_UNSIGNED, *n),
141 DagCbor::Negative(n) => {
142 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 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 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 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 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 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 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 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 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 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 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 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
372fn write_head(out: &mut Vec<u8>, major: u8, info: u8) {
375 out.push((major << 5) | info);
376}
377
378fn 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
399fn 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
433fn 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
452fn canonical_key_of(key: &DagCbor) -> Vec<u8> {
458 match key {
459 DagCbor::Text(s) => s.as_bytes().to_vec(),
460 _ => Vec::new(), }
462}
463
464fn 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 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 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 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 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 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 let bad = {
580 let mut out = Vec::new();
581 write_head(&mut out, MT_MAP, 2);
582 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 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 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 #[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 #[test]
657 #[should_panic(expected = "must hold a negative value")]
658 fn negative_must_be_negative() {
659 DagCbor::Negative(0).encode();
662 }
663
664 #[test]
665 fn negative_boundary_round_trips() {
666 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}