cbor.rs 90.7%

175 of 193 lines run, 44 of 52 functions · run #36 on main · run missed

//! Deterministic CBOR (RFC 8949 §4.2), as much of it as Spectra encodes:
//! unsigned integers, byte and text strings, arrays, maps with integer
//! keys, null and booleans. Shortest forms, definite lengths, map keys in
//! ascending order; the decoder refuses anything else, so one value has
//! exactly one encoding and hashing it is meaningful (spec §9.5).

use std::collections::BTreeMap;

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Value {
    Uint(u64),
    Bytes(Vec<u8>),
    Text(String),
    Array(Vec<Value>),
    Map(BTreeMap<u64, Value>),
    Bool(bool),
    Null,
}

impl Value {
    pub fn map<const N: usize>(entries: [(u64, Value); N]) -> Value {
        Value::Map(entries.into_iter().collect())
    }
    pub fn as_uint(&self) -> Option<u64> {
        match self {
            Value::Uint(u) => Some(*u),
            _ => None,
        }
    }
    pub fn as_bytes(&self) -> Option<&[u8]> {
        match self {
            Value::Bytes(b) => Some(b),
            _ => None,
        }
    }
    pub fn as_text(&self) -> Option<&str> {
        match self {
            Value::Text(t) => Some(t),
            _ => None,
        }
    }
    pub fn as_array(&self) -> Option<&[Value]> {
        match self {
            Value::Array(a) => Some(a),
            _ => None,
        }
    }
    pub fn as_map(&self) -> Option<&BTreeMap<u64, Value>> {
        match self {
            Value::Map(m) => Some(m),
            _ => None,
        }
    }
    pub fn is_null(&self) -> bool {
        matches!(self, Value::Null)
    }
}

fn head(out: &mut Vec<u8>, major: u8, n: u64) {
    let m = major << 5;
    match n {
        0..=23 => out.push(m | n as u8),
        24..=0xff => out.extend_from_slice(&[m | 24, n as u8]),
        0x100..=0xffff => {
            out.push(m | 25);
            out.extend_from_slice(&(n as u16).to_be_bytes());
        }
        0x1_0000..=0xffff_ffff => {
            out.push(m | 26);
            out.extend_from_slice(&(n as u32).to_be_bytes());
        }
        _ => {
            out.push(m | 27);
            out.extend_from_slice(&n.to_be_bytes());
        }
    }
}

fn put(out: &mut Vec<u8>, v: &Value) {
    match v {
        Value::Uint(n) => head(out, 0, *n),
        Value::Bytes(b) => {
            head(out, 2, b.len() as u64);
            out.extend_from_slice(b);
        }
        Value::Text(t) => {
            head(out, 3, t.len() as u64);
            out.extend_from_slice(t.as_bytes());
        }
        Value::Array(a) => {
            head(out, 4, a.len() as u64);
            for x in a {
                put(out, x);
            }
        }
        // BTreeMap iterates keys ascending, which for unsigned integers is
        // the order of their shortest encodings.
        Value::Map(m) => {
            head(out, 5, m.len() as u64);
            for (k, x) in m {
                head(out, 0, *k);
                put(out, x);
            }
        }
        Value::Bool(false) => out.push(0xf4),
        Value::Bool(true) => out.push(0xf5),
        Value::Null => out.push(0xf6),
    }
}

pub fn encode(v: &Value) -> Vec<u8> {
    let mut out = Vec::new();
    put(&mut out, v);
    out
}

/// Why bytes are not a value Spectra encodes.
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
#[error("malformed CBOR: {0}")]
pub struct Error(pub String);

struct Reader<'a> {
    b: &'a [u8],
    at: usize,
    depth: usize,
}

const MAX_DEPTH: usize = 32;

impl<'a> Reader<'a> {
    fn take(&mut self, n: usize) -> Result<&'a [u8], Error> {
        let end = self.at.checked_add(n).filter(|e| *e <= self.b.len()).ok_or_else(|| Error("truncated".into()))?;
        let s = &self.b[self.at..end];
        self.at = end;
        Ok(s)
    }

    fn head(&mut self) -> Result<(u8, u64), Error> {
        let first = self.take(1)?[0];
        let (major, info) = (first >> 5, first & 0x1f);
        let n = match info {
            0..=23 => info as u64,
            24 => self.take(1)?[0] as u64,
            25 => u16::from_be_bytes(self.take(2)?.try_into().unwrap()) as u64,
            26 => u32::from_be_bytes(self.take(4)?.try_into().unwrap()) as u64,
            27 => u64::from_be_bytes(self.take(8)?.try_into().unwrap()),
            _ if major == 7 => return Ok((7, info as u64)),
            _ => return Err(Error("an indefinite length or a reserved form".into())),
        };
        let minimal = match info {
            24 => n >= 24,
            25 => n > 0xff,
            26 => n > 0xffff,
            27 => n > 0xffff_ffff,
            _ => true,
        };
        if !minimal && major != 7 {
            return Err(Error("a length or number not in its shortest form".into()));
        }
        Ok((major, n))
    }

    fn len(&mut self, n: u64) -> Result<usize, Error> {
        let n = usize::try_from(n).map_err(|_| Error("too long".into()))?;
        if n > self.b.len() - self.at {
            return Err(Error("truncated".into()));
        }
        Ok(n)
    }

    fn value(&mut self) -> Result<Value, Error> {
        self.depth += 1;
        if self.depth > MAX_DEPTH {
            return Err(Error("nested too deeply".into()));
        }
        let (major, n) = self.head()?;
        let v = match major {
            0 => Value::Uint(n),
            2 => {
                let l = self.len(n)?;
                Value::Bytes(self.take(l)?.to_vec())
            }
            3 => {
                let l = self.len(n)?;
                Value::Text(String::from_utf8(self.take(l)?.to_vec()).map_err(|_| Error("text that is not UTF-8".into()))?)
            }
            4 => {
                let l = self.len(n)?;
                let mut a = Vec::with_capacity(l);
                for _ in 0..l {
                    a.push(self.value()?);
                }
                Value::Array(a)
            }
            5 => {
                let l = self.len(n)?;
                let mut m = BTreeMap::new();
                let mut last: Option<u64> = None;
                for _ in 0..l {
                    let (km, k) = self.head()?;
                    if km != 0 {
                        return Err(Error("a map key that is not an unsigned integer".into()));
                    }
                    if last.is_some_and(|p| k <= p) {
                        return Err(Error("map keys out of order or repeated".into()));
                    }
                    last = Some(k);
                    m.insert(k, self.value()?);
                }
                Value::Map(m)
            }
            7 => match n {
                20 => Value::Bool(false),
                21 => Value::Bool(true),
                22 => Value::Null,
                _ => return Err(Error("an unsupported simple value or float".into())),
            },
            _ => return Err(Error("a negative integer or a tag".into())),
        };
        self.depth -= 1;
        Ok(v)
    }
}

/// Decode exactly one value, refusing any non-canonical encoding.
pub fn decode(b: &[u8]) -> Result<Value, Error> {
    let mut r = Reader { b, at: 0, depth: 0 };
    let v = r.value()?;
    if r.at != b.len() {
        return Err(Error("bytes after the value".into()));
    }
    Ok(v)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn round_trips_and_known_encodings() {
        let v = Value::map([
            (0, Value::Uint(1)),
            (1, Value::Text("é".into())),
            (2, Value::Bytes(vec![1, 2])),
            (3, Value::Array(vec![Value::Null, Value::Bool(true), Value::Uint(500)])),
            (24, Value::Uint(u64::MAX)),
        ]);
        let b = encode(&v);
        assert_eq!(decode(&b).unwrap(), v);
        assert_eq!(encode(&Value::Uint(23)), [0x17]);
        assert_eq!(encode(&Value::Uint(24)), [0x18, 24]);
        assert_eq!(encode(&Value::Uint(1000)), [0x19, 0x03, 0xe8]);
        assert_eq!(encode(&Value::Text("a".into())), [0x61, b'a']);
    }

    #[test]
    fn refuses_what_is_not_canonical() {
        assert!(decode(&[0x18, 5]).is_err(), "5 in two bytes");
        assert!(decode(&[0xa2, 0x01, 0x00, 0x00, 0x00]).is_err(), "keys out of order");
        assert!(decode(&[0x5f]).is_err(), "indefinite length");
        assert!(decode(&[0x01, 0x02]).is_err(), "trailing bytes");
        assert!(decode(&[0x5a, 0xff, 0xff, 0xff, 0xff]).is_err(), "truncated");
        assert!(decode(&[0x20]).is_err(), "negative");
        let deep = [0x81u8; 64];
        assert!(decode(&deep).is_err(), "too deep");
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1		//! Deterministic CBOR (RFC 8949 §4.2), as much of it as Spectra encodes:
2		//! unsigned integers, byte and text strings, arrays, maps with integer
3		//! keys, null and booleans. Shortest forms, definite lengths, map keys in
4		//! ascending order; the decoder refuses anything else, so one value has
5		//! exactly one encoding and hashing it is meaningful (spec §9.5).
6
7		use std::collections::BTreeMap;
8
9		#[derive(Clone, Debug, PartialEq, Eq)]
10		pub enum Value {
11		Uint(u64),
12		Bytes(Vec<u8>),
13		Text(String),
14		Array(Vec<Value>),
15		Map(BTreeMap<u64, Value>),
16		Bool(bool),
17		Null,
18		}
19
20		impl Value {
21	68295×	pub fn map<const N: usize>(entries: [(u64, Value); N]) -> Value {
22	68295×	Value::Map(entries.into_iter().collect())
23	68295×	}
24	5121×	pub fn as_uint(&self) -> Option<u64> {
25	5121×	match self {
26	5121×	Value::Uint(u) => Some(*u),
27	0×	_ => None,
28		}
29	5121×	}
30	13606×	pub fn as_bytes(&self) -> Option<&[u8]> {
31	13606×	match self {
32	13606×	Value::Bytes(b) => Some(b),
33	0×	_ => None,
34		}
35	13606×	}
36	4654×	pub fn as_text(&self) -> Option<&str> {
37	4654×	match self {
38	4654×	Value::Text(t) => Some(t),
39	0×	_ => None,
40		}
41	4654×	}
42	1762×	pub fn as_array(&self) -> Option<&[Value]> {
43	1762×	match self {
44	1762×	Value::Array(a) => Some(a),
45	0×	_ => None,
46		}
47	1762×	}
48	6129×	pub fn as_map(&self) -> Option<&BTreeMap<u64, Value>> {
49	6129×	match self {
50	6129×	Value::Map(m) => Some(m),
51	0×	_ => None,
52		}
53	6129×	}
54	0×	pub fn is_null(&self) -> bool {
55	0×	matches!(self, Value::Null)
56	0×	}
57		}
58
59	984630×	fn head(out: &mut Vec<u8>, major: u8, n: u64) {
60	984630×	let m = major << 5;
61	984630×	match n {
62	984630×	0..=23 => out.push(m \| n as u8),
63	189552×	24..=0xff => out.extend_from_slice(&[m \| 24, n as u8]),
64	89256×	0x100..=0xffff => {
65	31498×	out.push(m \| 25);
66	31498×	out.extend_from_slice(&(n as u16).to_be_bytes());
67	31498×	}
68	57758×	0x1_0000..=0xffff_ffff => {
69	0×	out.push(m \| 26);
70	0×	out.extend_from_slice(&(n as u32).to_be_bytes());
71	0×	}
72	57758×	_ => {
73	57758×	out.push(m \| 27);
74	57758×	out.extend_from_slice(&n.to_be_bytes());
75	57758×	}
76		}
77	984630×	}
78
79	607166×	fn put(out: &mut Vec<u8>, v: &Value) {
80	607166×	match v {
81	186017×	Value::Uint(n) => head(out, 0, *n),
82	87034×	Value::Bytes(b) => {
83	87034×	head(out, 2, b.len() as u64);
84	87034×	out.extend_from_slice(b);
85	87034×	}
86	94048×	Value::Text(t) => {
87	94048×	head(out, 3, t.len() as u64);
88	94048×	out.extend_from_slice(t.as_bytes());
89	94048×	}
90	33569×	Value::Array(a) => {
91	33569×	head(out, 4, a.len() as u64);
92	56991×	for x in a {
93	56991×	put(out, x);
94	56991×	}
95		}
96		// BTreeMap iterates keys ascending, which for unsigned integers is
97		// the order of their shortest encodings.
98	68295×	Value::Map(m) => {
99	68295×	head(out, 5, m.len() as u64);
100	515667×	for (k, x) in m {
101	515667×	head(out, 0, *k);
102	515667×	put(out, x);
103	515667×	}
104		}
105	0×	Value::Bool(false) => out.push(0xf4),
106	1×	Value::Bool(true) => out.push(0xf5),
107	138202×	Value::Null => out.push(0xf6),
108		}
109	607166×	}
110
111	34508×	pub fn encode(v: &Value) -> Vec<u8> {
112	34508×	let mut out = Vec::new();
113	34508×	put(&mut out, v);
114	34508×	out
115	34508×	}
116
117		/// Why bytes are not a value Spectra encodes.
118		#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
119		#[error("malformed CBOR: {0}")]
120		pub struct Error(pub String);
121
122		struct Reader<'a> {
123		b: &'a [u8],
124		at: usize,
125		depth: usize,
126		}
127
128		const MAX_DEPTH: usize = 32;
129
130		impl<'a> Reader<'a> {
131	99373×	fn take(&mut self, n: usize) -> Result<&'a [u8], Error> {
132	99373×	let end = self.at.checked_add(n).filter(\|e\| *e <= self.b.len()).ok_or_else(\|\| Error("truncated".into()))?;
133	99373×	let s = &self.b[self.at..end];
134	99373×	self.at = end;
135	99373×	Ok(s)
136	99373×	}
137
138	65712×	fn head(&mut self) -> Result<(u8, u64), Error> {
139	65712×	let first = self.take(1)?[0];
140	65712×	let (major, info) = (first >> 5, first & 0x1f);
141	65711×	let n = match info {
142	65712×	0..=23 => info as u64,
143	9305×	24 => self.take(1)?[0] as u64,
144	3176×	25 => u16::from_be_bytes(self.take(2)?.try_into().unwrap()) as u64,
145	1×	26 => u32::from_be_bytes(self.take(4)?.try_into().unwrap()) as u64,
146	2917×	27 => u64::from_be_bytes(self.take(8)?.try_into().unwrap()),
147	1×	_ if major == 7 => return Ok((7, info as u64)),
148	1×	_ => return Err(Error("an indefinite length or a reserved form".into())),
149		};
150	65711×	let minimal = match info {
151	9305×	24 => n >= 24,
152	3176×	25 => n > 0xff,
153	1×	26 => n > 0xffff,
154	2917×	27 => n > 0xffff_ffff,
155	50312×	_ => true,
156		};
157	65711×	if !minimal && major != 7 {
158	1×	return Err(Error("a length or number not in its shortest form".into()));
159	65710×	}
160	65710×	Ok((major, n))
161	65712×	}
162
163	26189×	fn len(&mut self, n: u64) -> Result<usize, Error> {
164	26189×	let n = usize::try_from(n).map_err(\|_\| Error("too long".into()))?;
165	26189×	if n > self.b.len() - self.at {
166	1×	return Err(Error("truncated".into()));
167	26188×	}
168	26188×	Ok(n)
169	26189×	}
170
171	35377×	fn value(&mut self) -> Result<Value, Error> {
172	35377×	self.depth += 1;
173	35377×	if self.depth > MAX_DEPTH {
174	1×	return Err(Error("nested too deeply".into()));
175	35376×	}
176	35376×	let (major, n) = self.head()?;
177	35374×	let v = match major {
178	5151×	0 => Value::Uint(n),
179		2 => {
180	13608×	let l = self.len(n)?;
181	13607×	Value::Bytes(self.take(l)?.to_vec())
182		}
183		3 => {
184	4655×	let l = self.len(n)?;
185	4655×	Value::Text(String::from_utf8(self.take(l)?.to_vec()).map_err(\|_\| Error("text that is not UTF-8".into()))?)
186		}
187		4 => {
188	1795×	let l = self.len(n)?;
189	1795×	let mut a = Vec::with_capacity(l);
190	1795×	for _ in 0..l {
191	1392×	a.push(self.value()?);
192		}
193	1763×	Value::Array(a)
194		}
195		5 => {
196	6131×	let l = self.len(n)?;
197	6131×	let mut m = BTreeMap::new();
198	6131×	let mut last: Option<u64> = None;
199	6131×	for _ in 0..l {
200	30336×	let (km, k) = self.head()?;
201	30336×	if km != 0 {
202	0×	return Err(Error("a map key that is not an unsigned integer".into()));
203	30336×	}
204	30336×	if last.is_some_and(\|p\| k <= p) {
205	1×	return Err(Error("map keys out of order or repeated".into()));
206	30335×	}
207	30335×	last = Some(k);
208	30335×	m.insert(k, self.value()?);
209		}
210	6130×	Value::Map(m)
211		}
212	4033×	7 => match n {
213	0×	20 => Value::Bool(false),
214	1×	21 => Value::Bool(true),
215	4032×	22 => Value::Null,
216	0×	_ => return Err(Error("an unsupported simple value or float".into())),
217		},
218	1×	_ => return Err(Error("a negative integer or a tag".into())),
219		};
220	35339×	self.depth -= 1;
221	35339×	Ok(v)
222	35377×	}
223		}
224
225		/// Decode exactly one value, refusing any non-canonical encoding.
226	3650×	pub fn decode(b: &[u8]) -> Result<Value, Error> {
227	3650×	let mut r = Reader { b, at: 0, depth: 0 };
228	3650×	let v = r.value()?;
229	3644×	if r.at != b.len() {
230	1×	return Err(Error("bytes after the value".into()));
231	3643×	}
232	3643×	Ok(v)
233	3650×	}
234
235		#[cfg(test)]
236		mod tests {
237		use super::*;
238
239		#[test]
240	1×	fn round_trips_and_known_encodings() {
241	1×	let v = Value::map([
242	1×	(0, Value::Uint(1)),
243	1×	(1, Value::Text("é".into())),
244	1×	(2, Value::Bytes(vec![1, 2])),
245	1×	(3, Value::Array(vec![Value::Null, Value::Bool(true), Value::Uint(500)])),
246	1×	(24, Value::Uint(u64::MAX)),
247	1×	]);
248	1×	let b = encode(&v);
249	1×	assert_eq!(decode(&b).unwrap(), v);
250	1×	assert_eq!(encode(&Value::Uint(23)), [0x17]);
251	1×	assert_eq!(encode(&Value::Uint(24)), [0x18, 24]);
252	1×	assert_eq!(encode(&Value::Uint(1000)), [0x19, 0x03, 0xe8]);
253	1×	assert_eq!(encode(&Value::Text("a".into())), [0x61, b'a']);
254	1×	}
255
256		#[test]
257	1×	fn refuses_what_is_not_canonical() {
258	1×	assert!(decode(&[0x18, 5]).is_err(), "5 in two bytes");
259	1×	assert!(decode(&[0xa2, 0x01, 0x00, 0x00, 0x00]).is_err(), "keys out of order");
260	1×	assert!(decode(&[0x5f]).is_err(), "indefinite length");
261	1×	assert!(decode(&[0x01, 0x02]).is_err(), "trailing bytes");
262	1×	assert!(decode(&[0x5a, 0xff, 0xff, 0xff, 0xff]).is_err(), "truncated");
263	1×	assert!(decode(&[0x20]).is_err(), "negative");
264	1×	let deep = [0x81u8; 64];
265	1×	assert!(decode(&deep).is_err(), "too deep");
266	1×	}
267		}

Coverage / crates/spectra-core/src/cbor.rs 90.7%

Keyboard