btpc_core/
bencode.rs

1//! Borrowed bencode syntax tree with exact source spans.
2
3use std::ops::Range;
4
5use crate::limits::AllocationBudget;
6use crate::{Error, ParseLimits, Result};
7
8/// Half-open byte offsets into the original bencoded input.
9#[derive(Clone, Copy, Debug, Eq, PartialEq)]
10pub struct Span {
11    start: usize,
12    end: usize,
13}
14
15impl Span {
16    pub(crate) const fn new(start: usize, end: usize) -> Self {
17        Self { start, end }
18    }
19
20    /// Returns the start byte offset.
21    #[must_use]
22    pub const fn start(self) -> usize {
23        self.start
24    }
25
26    /// Returns the exclusive end byte offset.
27    #[must_use]
28    pub const fn end(self) -> usize {
29        self.end
30    }
31
32    /// Returns the span as a standard half-open range.
33    #[must_use]
34    pub const fn range(self) -> Range<usize> {
35        self.start..self.end
36    }
37}
38
39/// A borrowed bencode byte string.
40#[derive(Clone, Copy, Debug, Eq, PartialEq)]
41pub struct ByteString<'a> {
42    bytes: &'a [u8],
43    span: Span,
44}
45
46impl<'a> ByteString<'a> {
47    /// Returns the raw byte contents without UTF-8 decoding.
48    #[must_use]
49    pub const fn bytes(self) -> &'a [u8] {
50        self.bytes
51    }
52
53    /// Returns the exact encoded source span, including length prefix.
54    #[must_use]
55    pub const fn span(self) -> Span {
56        self.span
57    }
58}
59
60/// The payload of a borrowed bencode value.
61#[derive(Debug)]
62pub enum ValueKind<'a> {
63    /// Lossless signed bencode integer text.
64    Integer(Integer<'a>),
65    /// Raw byte string.
66    Bytes(&'a [u8]),
67    /// Ordered list of values.
68    List(Vec<Value<'a>>),
69    /// Ordered dictionary entries with raw byte-string keys.
70    Dictionary(Vec<(ByteString<'a>, Value<'a>)>),
71}
72
73/// Borrowed, lossless bencode integer representation.
74#[derive(Clone, Copy, Debug, Eq, PartialEq)]
75pub struct Integer<'a> {
76    encoded: &'a [u8],
77}
78
79impl<'a> Integer<'a> {
80    /// Returns the signed decimal bytes between the `i` and `e` delimiters.
81    #[must_use]
82    pub const fn encoded(self) -> &'a [u8] {
83        self.encoded
84    }
85
86    /// Converts to `i64` when representable.
87    #[must_use]
88    pub fn to_i64(self) -> Option<i64> {
89        std::str::from_utf8(self.encoded).ok()?.parse().ok()
90    }
91
92    /// Converts to `u64` when non-negative and representable.
93    #[must_use]
94    pub fn to_u64(self) -> Option<u64> {
95        std::str::from_utf8(self.encoded).ok()?.parse().ok()
96    }
97
98    pub(crate) fn canonical_bytes(self) -> Vec<u8> {
99        let (negative, digits) = self
100            .encoded
101            .strip_prefix(b"-")
102            .map_or((false, self.encoded), |digits| (true, digits));
103        let significant = digits
104            .iter()
105            .position(|digit| *digit != b'0')
106            .map_or(&digits[digits.len()..], |start| &digits[start..]);
107        if significant.is_empty() {
108            return b"0".to_vec();
109        }
110        let mut output = Vec::with_capacity(significant.len() + usize::from(negative));
111        if negative {
112            output.push(b'-');
113        }
114        output.extend_from_slice(significant);
115        output
116    }
117}
118
119/// A parsed bencode value borrowing byte strings from its input.
120#[derive(Debug)]
121pub struct Value<'a> {
122    kind: ValueKind<'a>,
123    span: Span,
124}
125
126impl<'a> Value<'a> {
127    /// Returns this value's payload.
128    #[must_use]
129    pub const fn kind(&self) -> &ValueKind<'a> {
130        &self.kind
131    }
132
133    /// Returns the exact encoded source span.
134    #[must_use]
135    pub const fn span(&self) -> Span {
136        self.span
137    }
138
139    /// Returns the integer payload when this is an integer.
140    #[must_use]
141    pub fn as_integer(&self) -> Option<i64> {
142        match self.kind {
143            ValueKind::Integer(value) => value.to_i64(),
144            _ => None,
145        }
146    }
147
148    /// Returns the lossless integer payload when this is an integer.
149    #[must_use]
150    pub const fn integer(&self) -> Option<Integer<'a>> {
151        match self.kind {
152            ValueKind::Integer(value) => Some(value),
153            _ => None,
154        }
155    }
156
157    /// Returns the raw bytes when this is a byte string.
158    #[must_use]
159    pub const fn as_bytes(&self) -> Option<&'a [u8]> {
160        match self.kind {
161            ValueKind::Bytes(bytes) => Some(bytes),
162            _ => None,
163        }
164    }
165
166    /// Looks up a raw byte key without allocation.
167    #[must_use]
168    pub fn get(&self, key: &[u8]) -> Option<&Value<'a>> {
169        let ValueKind::Dictionary(entries) = &self.kind else {
170            return None;
171        };
172        entries
173            .iter()
174            .find_map(|(candidate, value)| (candidate.bytes == key).then_some(value))
175    }
176}
177
178/// Parses exactly one bencode value using default resource limits.
179///
180/// # Errors
181///
182/// Returns a syntax or resource-limit error for malformed, trailing, or
183/// over-limit input.
184pub fn parse(input: &[u8]) -> Result<Value<'_>> {
185    parse_with_limits(input, ParseLimits::default())
186}
187
188/// Parses exactly one bencode value using caller-provided resource limits.
189///
190/// # Errors
191///
192/// Returns a syntax or resource-limit error for malformed, trailing, or
193/// over-limit input.
194pub fn parse_with_limits(input: &[u8], limits: ParseLimits) -> Result<Value<'_>> {
195    let mut budget = AllocationBudget::new(limits);
196    parse_with_budget(input, limits, &mut budget)
197}
198
199pub(crate) fn parse_with_budget<'input>(
200    input: &'input [u8],
201    limits: ParseLimits,
202    budget: &mut AllocationBudget,
203) -> Result<Value<'input>> {
204    limits.check_total_input(input.len())?;
205    let mut parser = Parser {
206        input,
207        position: 0,
208        items: 0,
209        limits,
210        budget,
211    };
212    let value = parser.parse_value(0)?;
213    if parser.position != input.len() {
214        return Err(Error::bencode_syntax(
215            parser.position,
216            "trailing bytes after top-level value",
217        ));
218    }
219    Ok(value)
220}
221
222struct Parser<'input, 'budget> {
223    input: &'input [u8],
224    position: usize,
225    items: usize,
226    limits: ParseLimits,
227    budget: &'budget mut AllocationBudget,
228}
229
230impl<'input> Parser<'input, '_> {
231    fn parse_value(&mut self, depth: usize) -> Result<Value<'input>> {
232        self.count_item()?;
233        match self.peek()? {
234            b'i' => self.parse_integer(),
235            b'l' => self.parse_list(depth),
236            b'd' => self.parse_dictionary(depth),
237            b'0'..=b'9' => self.parse_byte_value(),
238            byte => Err(Error::bencode_syntax(
239                self.position,
240                format!("unexpected byte 0x{byte:02x}"),
241            )),
242        }
243    }
244
245    fn parse_integer(&mut self) -> Result<Value<'input>> {
246        let start = self.position;
247        self.position += 1;
248        let number_start = self.position;
249        while let Some(byte) = self.input.get(self.position) {
250            if *byte == b'e' {
251                break;
252            }
253            self.position += 1;
254        }
255        if self.input.get(self.position) != Some(&b'e') {
256            return Err(Error::bencode_syntax(start, "unterminated integer"));
257        }
258        let encoded = &self.input[number_start..self.position];
259        if encoded.is_empty() {
260            return Err(Error::bencode_syntax(number_start, "empty integer"));
261        }
262        if encoded[0] == b'+' {
263            return Err(Error::bencode_syntax(
264                number_start,
265                "plus sign is not allowed",
266            ));
267        }
268        let digits = encoded.strip_prefix(b"-").unwrap_or(encoded);
269        if digits.is_empty() || !digits.iter().all(u8::is_ascii_digit) {
270            return Err(Error::bencode_syntax(
271                number_start,
272                "invalid integer digits",
273            ));
274        }
275        self.limits.check_integer_digits(digits.len())?;
276        self.position += 1;
277        Ok(Value {
278            kind: ValueKind::Integer(Integer { encoded }),
279            span: Span::new(start, self.position),
280        })
281    }
282
283    fn parse_byte_value(&mut self) -> Result<Value<'input>> {
284        let byte_string = self.parse_byte_string(false)?;
285        Ok(Value {
286            kind: ValueKind::Bytes(byte_string.bytes),
287            span: byte_string.span,
288        })
289    }
290
291    fn parse_byte_string(&mut self, count_item: bool) -> Result<ByteString<'input>> {
292        if count_item {
293            self.count_item()?;
294        }
295        let start = self.position;
296        let length_start = self.position;
297        while matches!(self.input.get(self.position), Some(b'0'..=b'9')) {
298            self.position += 1;
299        }
300        if self.position == length_start || self.input.get(self.position) != Some(&b':') {
301            return Err(Error::bencode_syntax(start, "invalid byte-string length"));
302        }
303        let length_text = std::str::from_utf8(&self.input[length_start..self.position])
304            .map_err(|_| Error::bencode_syntax(start, "invalid byte-string length"))?;
305        let length = length_text
306            .parse::<usize>()
307            .map_err(|_| Error::bencode_syntax(start, "byte-string length is out of range"))?;
308        self.limits.check_byte_string_length(length)?;
309        self.position += 1;
310        let end = self
311            .position
312            .checked_add(length)
313            .ok_or_else(|| Error::bencode_syntax(start, "byte-string end offset overflowed"))?;
314        let Some(bytes) = self.input.get(self.position..end) else {
315            return Err(Error::bencode_syntax(start, "truncated byte string"));
316        };
317        self.position = end;
318        Ok(ByteString {
319            bytes,
320            span: Span::new(start, end),
321        })
322    }
323
324    fn parse_list(&mut self, depth: usize) -> Result<Value<'input>> {
325        let container_depth = depth
326            .checked_add(1)
327            .ok_or_else(|| Error::resource_limit("depth", usize::MAX, self.limits.max_depth()))?;
328        self.limits.check_depth(container_depth)?;
329        let start = self.position;
330        self.position += 1;
331        let mut items = Vec::new();
332        loop {
333            match self.input.get(self.position) {
334                Some(b'e') => {
335                    self.position += 1;
336                    break;
337                }
338                Some(_) => {
339                    self.budget.charge(std::mem::size_of::<Value<'input>>())?;
340                    items.try_reserve_exact(1).map_err(|_| {
341                        Error::resource_limit(
342                            "owned allocation",
343                            usize::MAX,
344                            self.limits.max_owned_allocation(),
345                        )
346                    })?;
347                    items.push(self.parse_value(container_depth)?);
348                }
349                None => return Err(Error::bencode_syntax(start, "unterminated list")),
350            }
351        }
352        Ok(Value {
353            kind: ValueKind::List(items),
354            span: Span::new(start, self.position),
355        })
356    }
357
358    fn parse_dictionary(&mut self, depth: usize) -> Result<Value<'input>> {
359        let container_depth = depth
360            .checked_add(1)
361            .ok_or_else(|| Error::resource_limit("depth", usize::MAX, self.limits.max_depth()))?;
362        self.limits.check_depth(container_depth)?;
363        let start = self.position;
364        self.position += 1;
365        let mut entries = Vec::new();
366        loop {
367            match self.input.get(self.position) {
368                Some(b'e') => {
369                    self.position += 1;
370                    break;
371                }
372                Some(b'0'..=b'9') => {
373                    self.budget
374                        .charge(std::mem::size_of::<(ByteString<'input>, Value<'input>)>())?;
375                    entries.try_reserve_exact(1).map_err(|_| {
376                        Error::resource_limit(
377                            "owned allocation",
378                            usize::MAX,
379                            self.limits.max_owned_allocation(),
380                        )
381                    })?;
382                    let key = self.parse_byte_string(true)?;
383                    if self.input.get(self.position).is_none() {
384                        return Err(Error::bencode_syntax(start, "dictionary key has no value"));
385                    }
386                    let value = self.parse_value(container_depth)?;
387                    entries.push((key, value));
388                }
389                Some(_) => {
390                    return Err(Error::bencode_syntax(
391                        self.position,
392                        "dictionary key must be a byte string",
393                    ));
394                }
395                None => return Err(Error::bencode_syntax(start, "unterminated dictionary")),
396            }
397        }
398        Ok(Value {
399            kind: ValueKind::Dictionary(entries),
400            span: Span::new(start, self.position),
401        })
402    }
403
404    fn count_item(&mut self) -> Result<()> {
405        self.items = self.items.checked_add(1).ok_or_else(|| {
406            Error::resource_limit("item count", usize::MAX, self.limits.max_items())
407        })?;
408        self.limits.check_items(self.items)
409    }
410
411    fn peek(&self) -> Result<u8> {
412        self.input
413            .get(self.position)
414            .copied()
415            .ok_or_else(|| Error::bencode_syntax(self.position, "expected a value"))
416    }
417}
418
419/// An owned bencode value that serializes canonically.
420#[derive(Clone, Debug, Eq, PartialEq)]
421pub enum OwnedValue {
422    /// Signed bencode integer.
423    Integer(i64),
424    /// Arbitrary-precision canonical signed decimal bytes.
425    IntegerBytes(Vec<u8>),
426    /// Raw byte string.
427    Bytes(Vec<u8>),
428    /// Ordered list of values.
429    List(Vec<Self>),
430    /// Dictionary stored in canonical raw-byte key order.
431    Dictionary(std::collections::BTreeMap<Vec<u8>, Self>),
432}
433
434impl OwnedValue {
435    /// Creates an integer value.
436    #[must_use]
437    pub const fn integer(value: i64) -> Self {
438        Self::Integer(value)
439    }
440
441    /// Creates an arbitrary-precision canonical integer.
442    ///
443    /// # Errors
444    ///
445    /// Returns a canonical error for empty digits, non-digits, a plus sign,
446    /// leading zeroes, or negative zero.
447    pub fn integer_bytes(value: impl AsRef<[u8]>) -> Result<Self> {
448        let value = value.as_ref();
449        let digits = value.strip_prefix(b"-").unwrap_or(value);
450        let valid = !digits.is_empty() && digits.iter().all(u8::is_ascii_digit);
451        let canonical_zero = digits == b"0" && !value.starts_with(b"-");
452        let canonical_nonzero = digits.first().is_some_and(|digit| *digit != b'0');
453        if value.starts_with(b"+") || !valid || !(canonical_zero || canonical_nonzero) {
454            return Err(Error::bencode_canonical(0, "invalid canonical integer"));
455        }
456        Ok(Self::IntegerBytes(value.to_vec()))
457    }
458
459    /// Creates a byte-string value.
460    #[must_use]
461    pub fn bytes(value: impl Into<Vec<u8>>) -> Self {
462        Self::Bytes(value.into())
463    }
464
465    /// Creates a list value.
466    #[must_use]
467    pub fn list(values: impl IntoIterator<Item = Self>) -> Self {
468        Self::List(values.into_iter().collect())
469    }
470
471    /// Creates a dictionary and rejects duplicate raw byte keys.
472    ///
473    /// # Errors
474    ///
475    /// Returns a canonical error if the input contains duplicate keys.
476    pub fn dictionary(entries: impl IntoIterator<Item = (Vec<u8>, Self)>) -> Result<Self> {
477        let mut dictionary = std::collections::BTreeMap::new();
478        for (key, value) in entries {
479            if dictionary.insert(key, value).is_some() {
480                return Err(Error::bencode_canonical(0, "duplicate dictionary key"));
481            }
482        }
483        Ok(Self::Dictionary(dictionary))
484    }
485
486    /// Returns the exact canonical encoded length.
487    #[must_use]
488    pub fn encoded_len(&self) -> usize {
489        match self {
490            Self::Integer(value) => 2 + decimal_len_i64(*value),
491            Self::IntegerBytes(value) => 2 + value.len(),
492            Self::Bytes(bytes) => decimal_len_usize(bytes.len()) + 1 + bytes.len(),
493            Self::List(values) => 2 + values.iter().map(Self::encoded_len).sum::<usize>(),
494            Self::Dictionary(entries) => {
495                2 + entries
496                    .iter()
497                    .map(|(key, value)| {
498                        decimal_len_usize(key.len()) + 1 + key.len() + value.encoded_len()
499                    })
500                    .sum::<usize>()
501            }
502        }
503    }
504
505    /// Writes canonical bencode to a byte writer.
506    ///
507    /// # Errors
508    ///
509    /// Returns an I/O error preserving the writer's original error as its source.
510    pub fn write_to(&self, writer: &mut impl std::io::Write) -> Result<()> {
511        self.validate_integer_bytes()?;
512        self.write_canonical(writer)
513            .map_err(|source| Error::io("<writer>", source))
514    }
515
516    /// Encodes this value into a pre-sized byte vector.
517    ///
518    /// # Errors
519    ///
520    /// Returns an I/O error if writing to the vector unexpectedly fails.
521    pub fn to_vec(&self) -> Result<Vec<u8>> {
522        self.validate_integer_bytes()?;
523        let mut encoded = Vec::with_capacity(self.encoded_len());
524        self.write_canonical(&mut encoded)
525            .map_err(|source| Error::io("<writer>", source))?;
526        Ok(encoded)
527    }
528
529    fn write_canonical(&self, writer: &mut impl std::io::Write) -> std::io::Result<()> {
530        match self {
531            Self::Integer(value) => write!(writer, "i{value}e"),
532            Self::IntegerBytes(value) => {
533                writer.write_all(b"i")?;
534                writer.write_all(value)?;
535                writer.write_all(b"e")
536            }
537            Self::Bytes(bytes) => {
538                write!(writer, "{}:", bytes.len())?;
539                writer.write_all(bytes)
540            }
541            Self::List(values) => {
542                writer.write_all(b"l")?;
543                for value in values {
544                    value.write_canonical(writer)?;
545                }
546                writer.write_all(b"e")
547            }
548            Self::Dictionary(entries) => {
549                writer.write_all(b"d")?;
550                for (key, value) in entries {
551                    write!(writer, "{}:", key.len())?;
552                    writer.write_all(key)?;
553                    value.write_canonical(writer)?;
554                }
555                writer.write_all(b"e")
556            }
557        }
558    }
559
560    fn validate_integer_bytes(&self) -> Result<()> {
561        match self {
562            Self::IntegerBytes(value) => Self::integer_bytes(value).map(|_| ()),
563            Self::List(values) => values.iter().try_for_each(Self::validate_integer_bytes),
564            Self::Dictionary(entries) => {
565                entries.values().try_for_each(Self::validate_integer_bytes)
566            }
567            Self::Integer(_) | Self::Bytes(_) => Ok(()),
568        }
569    }
570}
571
572/// Validates that an input is syntactically valid and canonically encoded.
573///
574/// # Errors
575///
576/// Returns syntax/resource errors from parsing or canonical errors with precise
577/// source offsets for non-minimal integers and lengths, unsorted keys, or
578/// duplicate dictionary keys.
579pub fn validate_canonical(input: &[u8]) -> Result<()> {
580    let value = parse(input)?;
581    validate_value_canonical(input, &value)
582}
583
584pub(crate) fn validate_parsed_canonical(input: &[u8], value: &Value<'_>) -> Result<()> {
585    validate_value_canonical(input, value)
586}
587
588fn validate_value_canonical(input: &[u8], value: &Value<'_>) -> Result<()> {
589    match value.kind() {
590        ValueKind::Integer(_) => validate_integer_encoding(input, value.span()),
591        ValueKind::Bytes(_) => validate_byte_string_encoding(input, value.span()),
592        ValueKind::List(values) => {
593            for value in values {
594                validate_value_canonical(input, value)?;
595            }
596            Ok(())
597        }
598        ValueKind::Dictionary(entries) => {
599            let mut previous: Option<&[u8]> = None;
600            for (key, value) in entries {
601                validate_byte_string_encoding(input, key.span())?;
602                if let Some(previous) = previous {
603                    match key.bytes().cmp(previous) {
604                        std::cmp::Ordering::Less => {
605                            return Err(Error::bencode_canonical(
606                                key.span().start(),
607                                "dictionary keys are not sorted",
608                            ));
609                        }
610                        std::cmp::Ordering::Equal => {
611                            return Err(Error::bencode_canonical(
612                                key.span().start(),
613                                "duplicate dictionary key",
614                            ));
615                        }
616                        std::cmp::Ordering::Greater => {}
617                    }
618                }
619                previous = Some(key.bytes());
620                validate_value_canonical(input, value)?;
621            }
622            Ok(())
623        }
624    }
625}
626
627fn validate_integer_encoding(input: &[u8], span: Span) -> Result<()> {
628    let encoded = &input[span.start() + 1..span.end() - 1];
629    if encoded == b"-0" {
630        return Err(Error::bencode_canonical(
631            span.start() + 1,
632            "negative zero is not canonical",
633        ));
634    }
635    let digits = encoded.strip_prefix(b"-").unwrap_or(encoded);
636    if digits.len() > 1 && digits[0] == b'0' {
637        return Err(Error::bencode_canonical(
638            span.start() + 1,
639            "integer has a leading zero",
640        ));
641    }
642    Ok(())
643}
644
645fn validate_byte_string_encoding(input: &[u8], span: Span) -> Result<()> {
646    let encoded = &input[span.start()..span.end()];
647    let colon = encoded
648        .iter()
649        .position(|byte| *byte == b':')
650        .expect("parsed byte strings always contain a colon");
651    if colon > 1 && encoded[0] == b'0' {
652        return Err(Error::bencode_canonical(
653            span.start(),
654            "byte-string length has a leading zero",
655        ));
656    }
657    Ok(())
658}
659
660fn decimal_len_usize(value: usize) -> usize {
661    value.checked_ilog10().map_or(1, |log| log as usize + 1)
662}
663
664fn decimal_len_i64(value: i64) -> usize {
665    if value < 0 {
666        1 + decimal_len_u64(value.unsigned_abs())
667    } else {
668        decimal_len_u64(value.unsigned_abs())
669    }
670}
671
672fn decimal_len_u64(value: u64) -> usize {
673    value.checked_ilog10().map_or(1, |log| log as usize + 1)
674}
btpc_core/bencode.rs

btpc_core/
bencode.rs
