bside/

parser.rs

use nom::IResult;
use nom::Parser;
use nom::branch::alt;
use nom::character::{self, one_of};
use nom::combinator::recognize;
use nom::multi::{length_data, many0};
use nom::sequence::{delimited, pair, terminated};
use std::collections::HashMap;

use crate::error::Error;
use crate::value::Value;

/// Parses a bencoded value into a [`Value`]. If `strict` is `true`, dictionaries are required to
/// be sorted (in keeping with the specification).
pub fn parse(input: &[u8], strict: bool) -> Result<Value, Error> {
    if input.is_empty() {
        Err(Error::Message(String::from("Input is empty.")))
    } else {
        match parse_value(input, strict) {
            Ok((remaining, value)) => {
                if remaining.is_empty() {
                    Ok(value)
                } else {
                    Err(Error::Message(String::from("Non-singular root item.")))
                }
            }

            _ => Err(Error::Message(String::from("Invalid input."))),
        }
    }
}

fn parse_int(input: &[u8]) -> IResult<&[u8], Value> {
    fn recognize_positive_int(input: &[u8]) -> IResult<&[u8], &[u8]> {
        recognize((one_of("123456789"), many0(one_of("0123456789")))).parse(input)
    }

    fn recognize_negative_int(input: &[u8]) -> IResult<&[u8], &[u8]> {
        recognize((
            character::complete::char('-'),
            one_of("123456789"),
            many0(one_of("0123456789")),
        ))
        .parse(input)
    }

    fn recognize_zero(input: &[u8]) -> IResult<&[u8], &[u8]> {
        recognize(character::complete::char('0')).parse(input)
    }

    fn recognize_int_chars(input: &[u8]) -> IResult<&[u8], &[u8]> {
        alt((
            recognize_positive_int,
            recognize_negative_int,
            recognize_zero,
        ))
        .parse(input)
    }

    let (remaining, int_chars) = delimited(
        character::complete::char('i'),
        recognize_int_chars,
        character::complete::char('e'),
    )
    .parse(input)?;

    let (_, int) = character::complete::i64.parse(int_chars)?;
    Ok((remaining, Value::Int(int)))
}

fn parse_byte_slice(input: &[u8]) -> IResult<&[u8], &[u8]> {
    fn parse_length(input: &[u8]) -> IResult<&[u8], u64> {
        terminated(character::complete::u64, character::complete::char(':')).parse(input)
    }

    length_data(parse_length).parse(input)
}

fn parse_bytes(input: &[u8]) -> IResult<&[u8], Value> {
    let (remaining, parsed) = parse_byte_slice(input)?;
    Ok((remaining, Value::Bytes(parsed.into())))
}

fn parse_list(input: &[u8], strict: bool) -> IResult<&[u8], Value> {
    let (remaining, parsed) = delimited(
        character::complete::char('l'),
        many0(|input| parse_value(input, strict)),
        character::complete::char('e'),
    )
    .parse(input)?;

    Ok((remaining, Value::List(parsed)))
}

fn parse_dict(input: &[u8], strict: bool) -> IResult<&[u8], Value> {
    let (remaining, pairs) = delimited(
        character::complete::char('d'),
        many0(pair(parse_byte_slice, |input| parse_value(input, strict))),
        character::complete::char('e'),
    )
    .parse(input)?;

    if !strict || pairs.is_sorted_by_key(|(key, _)| key) {
        Ok((
            remaining,
            Value::Dict(HashMap::from_iter(
                pairs.into_iter().map(|(key, value)| (key.into(), value)),
            )),
        ))
    } else {
        Err(nom::Err::Failure(nom::error::Error {
            input,
            code: nom::error::ErrorKind::Fail,
        }))
    }
}

fn parse_value(input: &[u8], strict: bool) -> IResult<&[u8], Value> {
    alt((
        parse_int,
        parse_bytes,
        |input| parse_list(input, strict),
        |input| parse_dict(input, strict),
    ))
    .parse(input)
}

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

    #[test]
    fn positive_integer() {
        assert_eq!(parse(b"i1203e", true).unwrap(), Value::Int(1203));
    }

    #[test]
    fn negative_integer() {
        assert_eq!(parse(b"i-1203e", true).unwrap(), Value::Int(-1203));
    }

    #[test]
    fn zero() {
        assert_eq!(parse(b"i0e", true).unwrap(), Value::Int(0));
    }

    #[test]
    fn byte_string() {
        assert_eq!(
            parse(b"7:bencode", true).unwrap(),
            Value::Bytes(b"bencode".into())
        );
    }

    #[test]
    fn list() {
        assert_eq!(
            parse(b"l7:bencodei-20ee", true).unwrap(),
            Value::List(vec![Value::Bytes(b"bencode".into()), Value::Int(-20)])
        );
    }

    #[test]
    fn dict() {
        assert_eq!(
            parse(b"d7:meaningi42e4:wiki7:bencodee", true).unwrap(),

            Value::Dict(HashMap::from([
                (b"wiki".into(), Value::Bytes(b"bencode".into())),
                (b"meaning".into(), Value::Int(42))
            ]))
        );
    }

    #[test]
    fn dict_not_sorted_not_strict() {
        assert_eq!(
            parse(b"d4:wiki7:bencode7:meaningi42ee", false).unwrap(),

            Value::Dict(HashMap::from([
                (b"wiki".into(), Value::Bytes(b"bencode".into())),
                (b"meaning".into(), Value::Int(42))
            ]))
        );
    }

    fn expect_parse_error(result: Result<Value, Error>) {
        assert!(matches!(result, Err(Error::Message(_))))
    }

    #[test]
    fn empty_input() {
        expect_parse_error(parse(b"", true));
    }

    #[test]
    fn non_singular_root_item() {
        expect_parse_error(parse(b"i123ei456e", true));
    }

    #[test]
    fn invalid_type() {
        expect_parse_error(parse(b"a1e", true));
    }

    #[test]
    fn missing_colon() {
        expect_parse_error(parse(b"1a", true));
    }

    #[test]
    fn missing_int_terminator() {
        expect_parse_error(parse(b"i123", true));
    }

    #[test]
    fn eof_before_completing_byte_string() {
        expect_parse_error(parse(b"7:abc", true));
    }

    #[test]
    fn missing_list_terminator() {
        expect_parse_error(parse(b"l7:bencodei-20e", true));
    }

    #[test]
    fn missing_dict_terminator() {
        expect_parse_error(parse(b"d7:meaningi42e4:wiki7:bencode", true));
    }

    #[test]
    fn integer_contains_non_digit() {
        expect_parse_error(parse(b"i1_2e", true));
    }

    #[test]
    fn negative_zero() {
        expect_parse_error(parse(b"i-0e", true));
    }

    #[test]
    fn positive_int_with_leading_zero() {
        expect_parse_error(parse(b"i01e", true));
    }

    #[test]
    fn negative_int_with_leading_zero() {
        expect_parse_error(parse(b"i-01e", true));
    }

    #[test]
    fn dict_key_not_byte_string() {
        expect_parse_error(parse(b"di3ei4ee", true))
    }

    #[test]
    fn dict_missing_value() {
        expect_parse_error(parse(b"d7:meaninge", true))
    }

    #[test]
    fn dict_not_sorted_strict() {
        expect_parse_error(parse(b"d4:wiki7:bencode7:meaningi42ee", true));
    }
}