1
\$\begingroup\$

I have been learning rust sporadically for a while now and decided to write some toy projects. While browsing https://github.com/codecrafters-io/build-your-own-x I came across some bittorrent client examples. As they contain many moving parts like parsing, networking and multithreading it seemed like a good idea for a mini toy project. I started with a decoder/parser for bencoding format since it is probably the simplest and most intuitive part.

I initially implemented it using nom since I was familiar with it. Here is the implementation if you're curious: https://github.com/centaurwho/domenec/blob/prototype/domenec/src/bencode_nom.rs. Later I changed that since it was usually too slow and wanted to play with bytes. After implementing it with using the augmented BNF from https://hackage.haskell.org/package/bencoding-0.4.3.0/docs/Data-BEncode.html as reference, I now have a working implementation.

Current parser has some basic error handling and many unit tests to confirm it works as intended. Since the official documentation of the format is not very good, I have assumed some details during implementation and later cross-checked using this python library's unit tests: https://github.com/fuzeman/bencode.py/tree/master/tests

Here's the code:

#[derive(Debug, Clone, Eq, PartialEq)]
pub enum DecodingError {
    Err,
    MissingIdentifier(char),
    KeyWithoutValue(String),
    StringWithoutLength,
    NotANumber,
    EndOfFile,
    NegativeZero,
}

type Result<T> = std::result::Result<T, DecodingError>;

#[derive(Debug, Eq, PartialEq)]
pub enum BEncodingType {
    Integer(i64),
    String(String),
    List(Vec<BEncodingType>),
    Dictionary(LinkedHashMap<String, BEncodingType>),
}

pub struct BDecoder<'a> {
    bytes: &'a [u8],
    cursor: usize,
}

impl BDecoder<'_> {
    fn new(bytes: &[u8]) -> BDecoder {
        BDecoder { bytes, cursor: 0 }
    }

    fn decode(&mut self) -> Result<BEncodingType> {
        self.parse_type()
    }

    fn parse_str(&mut self) -> Result<String> {
        let len = self.read_num().or(Err(DecodingError::StringWithoutLength))?;
        self.expect_char(b':')?;
        let start = self.cursor;
        let end = start + len as usize;
        if end > self.bytes.len() {
            self.cursor = self.bytes.len();
            return Err(DecodingError::EndOfFile);
        }
        self.cursor = end;
        Ok(String::from_utf8_lossy(&self.bytes[start..end]).to_string())
    }

    fn parse_int(&mut self) -> Result<i64> {
        self.expect_char(b'i')?;
        let i = self.read_num()?;
        self.expect_char(b'e')?;
        Ok(i)
    }

    fn parse_list(&mut self) -> Result<Vec<BEncodingType>> {
        self.expect_char(b'l')?;
        let mut list = Vec::new();
        while self.peek().filter(|&c| c != b'e').is_some() {
            list.push(self.parse_type()?);
        }
        self.expect_char(b'e')?;
        Ok(list)
    }

    fn parse_dict(&mut self) -> Result<LinkedHashMap<String, BEncodingType>> {
        self.expect_char(b'd')?;
        let mut dict = LinkedHashMap::new();
        while self.peek().filter(|&c| c != b'e').is_some() {
            let key = self.parse_str()?;
            let value = self.parse_type()
                .map_err(|_| DecodingError::KeyWithoutValue(key.clone()))?;
            dict.insert(key, value);
        }
        self.expect_char(b'e')?;
        Ok(dict)
    }

    fn parse_type(&mut self) -> Result<BEncodingType> {
        match self.peek() {
            None => Err(DecodingError::Err),
            Some(b'i') => self.parse_int().map(BEncodingType::Integer),
            Some(b'l') => self.parse_list().map(BEncodingType::List),
            Some(b'd') => self.parse_dict().map(BEncodingType::Dictionary),
            Some(_) => self.parse_str().map(BEncodingType::String)
        }
    }

    fn read_num(&mut self) -> Result<i64> {
        let mut neg_const = 1;
        if self.peek() == Some(b'-') {
            neg_const = -1;
            self.cursor += 1;
        }
        // FIXME: Consider a cleaner early return here, not happy with the catchall
        match self.peek() {
            None => Err(DecodingError::EndOfFile),
            Some(chr) if !chr.is_ascii_digit() => Err(DecodingError::NotANumber),
            Some(chr) if neg_const == -1 && chr == b'0' => Err(DecodingError::NegativeZero),
            _ => Ok(())
        }?;
        let mut acc = 0;
        while let Some(v) = self.peek() {
            if v.is_ascii_digit() {
                acc = acc * 10 + (v - b'0') as i64;
                self.cursor += 1;
            } else {
                break;
            }
        };
        Ok(acc * neg_const)
    }

    fn expect_char(&mut self, expected: u8) -> Result<u8> {
        match self.peek() {
            None => Err(DecodingError::EndOfFile),
            Some(chr) if chr == expected => self.advance(),
            _ => Err(DecodingError::MissingIdentifier(expected as char)),
        }
    }

    fn peek(&mut self) -> Option<u8> {
        self.bytes.get(self.cursor).cloned()
    }

    fn advance(&mut self) -> Result<u8> {
        let v = self.bytes.get(self.cursor).cloned();
        self.cursor += 1;
        v.ok_or(DecodingError::EndOfFile)
    }
}

pub fn decode(inp: &[u8]) -> Result<BEncodingType> {
    let mut parser = BDecoder::new(inp);
    parser.decode()
}

Code is pretty self explanatory, but if you have any question I can gladly help.

I know this is too long and may not result in a lot of reviews but I didn't want to exclude any part for completeness sake. There are some points where I am not sure is good practice or idiomatic rust. Some irks I have:

  • I am not a fan of classes with one public method in other languages. So I considered not having a struct at all and passing the bytes from function to function.
  • I considered using a bytes iterator instead of having a bytes and cursor field. But not sure if it would improve the code at all.
  • I am not sure if error handling is clean enough. Particularly, is the amount of custom error kinds in DecodingError necessary. I know for most languages custom errors are usually not recommended or having only 1 or 2 is enough.
  • Also on error handling, in the function read_num I am using a match expression combined with ? to early return from the function. I don't like creating Ok(()) in the catchall arm and throwing it away in the next line. I feel like there should be a better way.

These were just some questions I had while writing it and I probably missed some others. Would really appreciate a review.

\$\endgroup\$

1 Answer 1

0
\$\begingroup\$

A short, more general review since I'm not too experienced with Rust:

  • The contained type of BEncodingType::String should be changed from String to Vec<u8>. From the Bencode Wikipedia page, it's a byte string so it's a sequence of bytes, not necessarily characters, and "bencoded values often contain binary data". Example: a torrent file, where the pieces entry is a concatenation of the binary form of each piece's SHA-1 hash. So while your decoder works for byte slices that are valid UTF-8, it corrupts any data that doesn't cleanly convert to UTF-8. Example test case that demonstrates this:

    #[test]
    pub fn test_parse_byte_string() {
        let input: &[u8] = b"4:rDx\x8D";
        let expected_decoded_bytes: &[u8] = b"rDx\x8D"; // &[114, 68, 120, 141]
    
        let mut decoder = BDecoder::new(input);
        if let Ok(s) = decoder.parse_str() {
            assert_eq!(s.as_bytes(), expected_decoded_bytes);
        } else {
            panic!("test case should not return a decoding error");
        }
    }
    

    The above test yields the following output when run, where 239, 191, 189 corresponds to the U+FFFD replacement character �:

    ---- bdecode::test::test_parse_byte_string stdout ----
    thread 'bdecode::test::test_parse_byte_string' panicked at 'assertion failed: `(left == right)`
      left: `[114, 68, 120, 239, 191, 189]`,
     right: `[114, 68, 120, 141]`', src/bdecode.rs:195:13
    note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
    
  • parse_str should bail early when it sees a negative length, but instead it tries to continue parsing invalid inputs like -3:abc which will lead to either a panic or incorrect parsing.

  • As a replacement for the match statement you flagged, I don't think there's anything wrong with the following. It's straightforward and easy to understand.

    if let Some(chr) = self.peek() {
        if !chr.is_ascii_digit() {
            return Err(DecodingError::NotANumber);
        } else if neg_const == -1 && chr == b'0' {
            return Err(DecodingError::NegativeZero);
        }
    } else {
        return Err(DecodingError::EndOfFile);
    }
    
  • The number of custom errors isn't an issue, but I'd highly recommend adding the byte offset (cursor location) as contextual information to all of the errors so you know exactly where in the input the decoder ran into a problem when an error is returned.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thank you for the review! You are right about byte strings. I think I saw that the keys of dictionary must be utf-8 and generalized it to all strings. Though, wikipedia says that keys also are byte strings. I got misread something along the way I guess. Fixed the other issues as well. Appreciate it! \$\endgroup\$ Sep 22, 2023 at 9:39
  • 1
    \$\begingroup\$ For the error handling part, I changed peek() to return Result<u8> instead of Option<u8> which let me get rid of some end of file checks. It simplified the match statement too. \$\endgroup\$ Sep 22, 2023 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.