rain_lang/parser/

mod.rs

/*!
A simple parser, AST and prettyprinter for a textual representation of `rain` programs
*/
use nom::{
    IResult,
    multi::{many0, many0_count, separated_list, separated_nonempty_list},
    sequence::{preceded, terminated, delimited, tuple, separated_pair},
    combinator::{opt, map, complete, recognize},
    branch::alt,
    bytes::complete::{tag, is_not, is_a},
    bytes::streaming::take_until,
    character::complete::{not_line_ending, digit1, hex_digit1, oct_digit1},
    character::streaming::multispace0,
};
use num::BigUint;

pub mod ast;
use ast::{
    Path, Expr, Pattern, Let, Scope, SimpleAssignment, Parametrized, Lambda, Pi, Phi, Gamma, Sexpr
};
use crate::value::primitive::{
    logical::{LogicalOp, Binary, Unary, Bool},
    binary::{Natural, BinaryDisplay}
};
pub mod symbol_table;
pub mod builder;

macro_rules! special_chars { () => (" \t\r\n(){}[]|:.=;#,'\"") }
macro_rules! digits { () => ("0123456789") }

const LET: &'static str = "let";
const DEFEQ: &'static str = "=";
const TERM: &'static str = ";";

/// Parse a single line `rain` comment
pub fn parse_single_comment(input: &str) -> IResult<&str, &str> {
    preceded(tag("//"), not_line_ending)(input)
}

/// Parse a multi line `rain` comment
pub fn parse_multi_comment(input: &str) -> IResult<&str, &str> {
    preceded(
        tag("/*"),
        take_until("*/")
    )(input)
}

/// Parse a `rain` comment. TODO: distinguish documentation comments, and don't ignore those
pub fn parse_comment(input: &str) -> IResult<&str, &str> {
    alt((
        parse_single_comment,
        parse_multi_comment
    ))(input)
}

/// Parse whitespace, including ignored comments. Returns the count of comments.
pub fn whitespace(input: &str) -> IResult<&str, usize> {
    terminated(
        many0_count(preceded(multispace0, parse_comment)),
        multispace0
    )(input)
}

/// Parse a `rain` identifier, which is composed of any non-special character.
/// Does *not* accept whitespace before the identifier, and does *not* consume whitespace after it.
pub fn parse_ident(input: &str) -> IResult<&str, &str> {
    recognize(
        tuple((is_not(concat!(special_chars!(), digits!())), opt(is_not(special_chars!()))))
    )(input)
}

/// Parse a path separator
pub fn path_separator(input: &str) -> IResult<&str, &str> { tag(".")(input) }

/// Parse a `rain` path.
/// Does *not* accept whitespace before the path and does *not* consume whitespace after it.
pub fn parse_path(input: &str) -> IResult<&str, Path> {
    map(
        separated_nonempty_list(path_separator, parse_ident),
        |names| { names.into() }
    )(input)
}

/// Parse a binary logical operation
pub fn parse_binary_logical_op(input: &str) -> IResult<&str, Binary> {
    use Binary::*;
    preceded(whitespace, alt((
        map(tag(And.get_string()), |_| And),
        map(tag(Or.get_string()), |_| Or),
        map(tag(Xor.get_string()), |_| Xor),
        map(tag(Nand.get_string()), |_| Nand),
        map(tag(Nor.get_string()), |_| Nor),
        map(tag(Eq.get_string()), |_| Eq),
        map(tag(Implies.get_string()), |_| Implies),
        map(tag(ImpliedBy.get_string()), |_| ImpliedBy)
    )))(input)
}

/// Parse a unary logical operation
pub fn parse_unary_logical_op(input: &str) -> IResult<&str, Unary> {
    use Unary::*;
    preceded(whitespace, alt((
        map(tag(Id.get_string()), |_| Id),
        map(tag(Not.get_string()), |_| Not),
        map(tag(Constant(true).get_string()), |_| Constant(true)),
        map(tag(Constant(false).get_string()), |_| Constant(false)),
    )))(input)
}

/// Parse a logical operation
pub fn parse_logical_op(input: &str) -> IResult<&str, LogicalOp> {
    use LogicalOp::*;
    alt((
        map(parse_binary_logical_op, Binary),
        map(parse_unary_logical_op, Unary)
    ))(input)
}

/// Parse the Boolean type
pub fn parse_bool_type(input: &str) -> IResult<&str, Bool> {
    map(preceded(whitespace, tag("#bool")), |_| Bool)(input)
}

/// Parse a boolean
pub fn parse_bool(input: &str) -> IResult<&str, bool> {
    preceded(whitespace, alt((
        map(tag("#true"), |_| true),
        map(tag("#false"), |_| false)
    )))(input)
}

/// Parse a natural number
pub fn parse_natural(input: &str) -> IResult<&str, Natural> {
    use BinaryDisplay::*;
    alt((
        map(
            preceded(tag("0b"), is_a("01")),
            |bytes: &str| Natural(BigUint::parse_bytes(bytes.as_bytes(), 2).unwrap(), Bin)
        ),
        map(
            preceded(tag("0o"), oct_digit1),
            |bytes: &str| Natural(BigUint::parse_bytes(bytes.as_bytes(), 8).unwrap(), Oct)
        ),
        map(
            preceded(tag("0x"), hex_digit1),
            |bytes: &str| Natural(BigUint::parse_bytes(bytes.as_bytes(), 2).unwrap(), Hex)
        ),
        map(
            digit1,
            |bytes: &str| Natural(BigUint::parse_bytes(bytes.as_bytes(), 10).unwrap(), Dec)
        ),
    ))(input)
}

/// Parse an atomic `rain` expression
/// Does *not* accept whitespace before the expression, and does *not* consume whitespace after it.
pub fn parse_atom(input: &str) -> IResult<&str, Expr> {
    alt((
        map(parse_natural, Expr::Natural), // Natural values
        map(parse_bool, Expr::Bool), // Boolean values
        map(parse_logical_op, Expr::LogicalOp), // Binary logical operations
        map(parse_bool_type, Expr::BoolTy), // Parse the boolean type
        map(parse_phi, Expr::Phi), // Phis
        map(parse_lambda, Expr::Lambda), // Lambdas
        map(parse_gamma, Expr::Gamma), // Match statements
        map(parse_pi, Expr::Pi), // Pi types
        map(parse_path, Expr::Path), // Paths
        map(parse_scope, Expr::Scope), // Scopes
        delimited(tag("("), parse_expr, preceded(whitespace, tag(")")))
    ))(input)
}

/// Parse a `rain` expression, which is either an atom or an application of them
/// Accepts whitespace before the expression
pub fn parse_expr(input: &str) -> IResult<&str, Expr> {
    map(
        tuple((
            preceded(whitespace, parse_atom),
            many0(preceded(complete(whitespace), map(parse_atom, Box::new)))
        )),
        |(first, mut ops)| {
            if ops.len() == 0 { first }
            else { ops.reverse(); ops.push(Box::new(first)); Expr::Sexpr(Sexpr { ops })}
        }
    )(input)
}

/// Parse a type bound
pub fn parse_type_bound(input: &str) -> IResult<&str, Expr> {
    preceded(preceded(whitespace, tag(":")), parse_expr)(input)
}

/// Parse a simple assignment. Accepts whitespace before it
pub fn parse_simple_assignment(input: &str) -> IResult<&str, SimpleAssignment> {
    map(
        tuple((
            whitespace,
            parse_ident,
            opt(parse_type_bound)
        )),
        |(_, name, ty)| SimpleAssignment { name, ty }
    )(input)
}

/// Parse a pattern for assignment
/// Accepts whitespace before the pattern
pub fn parse_pattern(input: &str) -> IResult<&str, Pattern> {
    map(preceded(whitespace, parse_simple_assignment), Pattern::Simple)(input) //TODO: this
}

/// Parse an equality separator, optionally preceded by whitespace
pub fn defeq(input: &str) -> IResult<&str, &str> { preceded(whitespace, tag(DEFEQ))(input) }

/// Parse a terminator, optionally preceded by whitespace
pub fn terminator(input: &str) -> IResult<&str, &str> { preceded(whitespace, tag(TERM))(input) }

/// Parse a `let`-statement
pub fn parse_statement(input: &str) -> IResult<&str, Let> {
    delimited(
        preceded(whitespace, tag(LET)),
        map(
            separated_pair(parse_pattern, defeq, parse_expr),
            |(pattern, expr)| { Let { pattern, expr } }
        ),
        terminator
    )(input)
}

/// Parse a scope, consuming all whitespace before it
pub fn parse_scope(input: &str) -> IResult<&str, Scope> {
    map(
        delimited(
            preceded(whitespace, tag("{")),
            tuple((
                many0(parse_statement),
                opt(parse_expr)
            )),
            preceded(whitespace, tag("}"))
        ),
        |(definitions, value)| Scope { definitions, value: value.map(Box::new) }
    )(input)
}

/// Parse a phi node, consuming all whitespace beforeit
pub fn parse_phi(input: &str) -> IResult<&str, Phi> {
    map(
        preceded(
            preceded(whitespace, tag("#phi")),
            parse_scope
        ),
        Phi
    )(input)
}

/// Parse an optional ident
pub fn parse_opt_ident(input: &str) -> IResult<&str, Option<&str>> {
    alt((
        map(tag("_"), |_| None),
        map(parse_ident, Some)
    ))(input)
}

/// Parse a list of typed identifiers
pub fn parse_typed_idents(input: &str) -> IResult<&str, Vec<(Option<&str>, Expr)>> {
    separated_nonempty_list(
        delimited(whitespace, tag(","), whitespace),
        tuple((parse_opt_ident, parse_type_bound))
    )(input)
}

/// Parse a list of typed arguments
pub fn parse_typed_args(input: &str) -> IResult<&str, Vec<(Option<&str>, Expr)>> {
    delimited(
        preceded(whitespace, tag("|")),
        parse_typed_idents,
        preceded(whitespace, tag("|"))
    )(input)
}

/// Parse a function type arrow
pub fn parse_type_arrow(input: &str) -> IResult<&str, Expr> {
    preceded(
        delimited(whitespace, tag("=>"), whitespace),
        parse_atom
    )(input)
}

/// Parse a lambda function, consuming all whitespace before it
pub fn parse_lambda(input: &str) -> IResult<&str, Lambda> {
    map(
        preceded(
            preceded(whitespace, tag("#lambda")),
            parse_parametrized
        ),
        |p| Lambda(p)
    )(input)
}

/// Parse a pi type, consuming all whitespace before it
pub fn parse_pi(input: &str) -> IResult<&str, Pi> {
    map(
        preceded(
            preceded(whitespace, tag("#pi")),
            parse_parametrized
        ),
        |p| Pi(p)
    )(input)
}

/// Parse a parametrized expression
pub fn parse_parametrized(input: &str) -> IResult<&str, Parametrized> {
    map(
        tuple((parse_typed_args, opt(parse_type_arrow), parse_expr)),
        |(args, ret_ty, result)| Parametrized {
            args, result: Box::new(result), ret_ty: ret_ty.map(|r| Box::new(r))
        }
    )(input)
}

/// Parse a gamma node, consuming all whitespace before it
pub fn parse_gamma(input: &str) -> IResult<&str, Gamma> {
    map(
        preceded(
            preceded(whitespace, tag("#match")),
            parse_pattern_matches
        ),
        |branches| Gamma { branches }
    )(input)
}

/// Parse a set of pattern matches
pub fn parse_pattern_matches(input: &str) -> IResult<&str, Vec<(Pattern, Expr)>> {
    delimited(
        preceded(whitespace, tag("{")),
        separated_list(
            preceded(whitespace, tag(",")),
            parse_pattern_match
        ),
        preceded(delimited(whitespace, opt(tag(",")), whitespace), tag("}"))
    )(input)
}

/// Parse a pattern match
pub fn parse_pattern_match(input: &str) -> IResult<&str, (Pattern, Expr)> {
    separated_pair(parse_pattern, preceded(whitespace, tag("=>")), parse_expr)(input)
}

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

    macro_rules! parse_tester {
        ($parser:expr, $string:expr, $correct:expr, $tail:expr) => {{
            let parser = $parser;
            let string = $string;
            let correct = $correct;
            let tail: Option<&str> = $tail;
            let (rest, parsed) = match parser(string) {
                Ok(result) => result,
                Err(err) => {
                    panic!("Error {:?} parsing input string {:?}", err, string)
                }
            };
            if let Some(correct) = correct { assert_eq!(parsed, correct, "Input parses wrong!"); }
            if let Some(tail) = tail { assert_eq!(rest, tail, "Invalid tail on input!"); }
            let displayed = format!("{}", parsed);
            let (rest, d_parsed) = match parser(&displayed) {
                Ok(result) => result,
                Err(err) => {
                    panic!(
                        "Error {:?} parsing display string {:?} (input = {:?})",
                        err, displayed, string
                    )
                }
            };
            assert_eq!(
                d_parsed, parsed,
                "Display output parses to the wrong result! (input = {:?}, displayed = {:?})",
                string, displayed
            );
            assert_eq!(
                rest, "",
                "Unparsed display output (input = {:?}, displayed = {:?})!", string, displayed
            );
            assert_eq!(displayed, format!("{}", d_parsed));
        }}
    }

    macro_rules! assert_parses {
        ($parser:expr, $string:expr) => { parse_tester!($parser, $string, None, Some("")) }
    }

    macro_rules! assert_parses_to {
        ($parser:expr, $string:expr, $correct:expr, $tail:expr) => {
            parse_tester!($parser, $string, Some($correct), Some($tail))
        }
    }

    #[test]
    fn idents_parse_properly() {
        assert_parses_to!(parse_ident, "hello world", "hello", " world");
        assert_parses_to!(parse_ident, "h3110 w0rld", "h3110", " w0rld");
        assert_parses_to!(parse_ident, "helloworld", "helloworld", "");
        assert_parses_to!(parse_ident, "hello() world", "hello", "() world");
        assert!(parse_ident(" helloworld").is_err());
        assert!(parse_ident(".helloworld").is_err());
        assert!(parse_ident(".12345").is_err());
        assert!(parse_ident("").is_err());
    }

    #[test]
    fn nested_exprs_dont_merge_improperly() {
        assert_eq!(
            &(format!("{:?}", parse_expr("a (b c) (d e)").unwrap())),
            "(\"\", (a (b c) (d e)))"
        );
    }

    #[test]
    fn paths_parse_properly() {
        assert_parses_to!(parse_path, "hello world", Path::ident("hello"), " world");
        assert_parses_to!(parse_path, "hello.world", Path::from(vec!["hello", "world"]), "");
        assert_parses_to!(parse_path, "hello.", Path::ident("hello"), ".");
        assert_parses_to!(parse_path, "h3110.w0rld", Path::from(vec!["h3110", "w0rld"]), "");
        assert!(parse_path(" helloworld").is_err());
        assert!(parse_path(".helloworld").is_err());
        assert!(parse_path(".12345").is_err());
        assert!(parse_path("").is_err());
    }

    #[test]
    fn atoms_parse_properly() {
        assert_parses_to!(parse_atom, "x y", Expr::ident("x"), " y");
        assert_parses_to!(parse_atom, "x.y", Expr::Path(Path::from(vec!["x", "y"])), "");
        assert_parses_to!(parse_atom, "(x) y", Expr::ident("x"), " y");
        assert_parses_to!(parse_atom, "(x.y) z", Expr::Path(Path::from(vec!["x", "y"])), " z");
    }

    #[test]
    fn simple_exprs_parse_properly() {
        assert_parses_to!(parse_expr, "(x y)", Expr::Sexpr(vec![
            Expr::ident("y").into(), Expr::ident("x").into()
        ].into()), "");
        assert_parses_to!(parse_expr, "(x.y)", Expr::Path(Path::from(vec!["x", "y"])), "");
        assert_parses_to!(parse_expr, "((x) y)", Expr::Sexpr(vec![
            Expr::ident("y").into(), Expr::ident("x").into()
        ].into()), "");
        assert_parses_to!(parse_expr, "((x.y) z)", Expr::Sexpr(vec![
            Expr::ident("z").into(),
            Expr::Path(Path::from(vec!["x", "y"])).into()
        ].into()), "");
    }

    #[test]
    fn nested_exprs_parse_properly() {
        let yz = Box::new(
            Expr::Sexpr(vec![Expr::ident("z").into(), Expr::ident("y").into()].into())
        );
        let xyz = Box::new(Expr::Sexpr(
            vec![
            Expr::Sexpr(vec![Expr::ident("z").into(), Expr::ident("y").into()].into()).into(),
            Expr::ident("x").into()
            ]
        .into()));
        assert_parses_to!(parse_expr, "(x (y z) (x (y z)) ((y z) w))", Expr::Sexpr(vec![
            Expr::Sexpr(vec![Expr::ident("w").into(), yz.clone()].into()).into(),
            xyz,
            yz.clone(),
            Expr::ident("x").into()
        ].into()), "")
    }

    #[test]
    fn simple_let_statements_parse_properly() {
        let statements = [
            "let x = y;",
            "let x = x.y;",
            "let hello = (world y) z;",
            "let z = 43 (54 2);"
        ];
        for statement in statements.iter() { assert_parses!(parse_statement, statement) }
    }

    #[test]
    fn simple_scopes_parse_properly() {
        let scopes = [
            "{}",
            "{ /* my variable x*/ x }",
            "{ let x = y; x }",
            "{ let hello = (world y) z; let x = world hello; hello x }"
        ];
        for scope in scopes.iter() { assert_parses!(parse_scope, scope) }
    }

    #[test]
    fn lambda_arguments_parse_properly() {
        let args = [
            "|x : A|",
            "|x : A|",
            "|y : B, z : C|",
            "|world: F, y: C|"
        ];
        for arg in args.iter() {
            assert!(parse_typed_args(arg).is_ok(), "Failed to parse {}", arg)
        }
    }

    #[test]
    fn type_arrows_parse_properly() {
        let args = [
            "=> x",
        ];
        for arg in args.iter() {
            match parse_type_arrow(arg) {
                Ok(_) => {},
                Err(err) => panic!("Failed to parse {:?}, got {:?}", arg, err)
            }
        }
    }

    #[test]
    fn simple_functions_parse_properly() {
        let fns = [
            "#lambda |x : A| {}",
            "#lambda |x : A| x",
            "#lambda |_ : A| x",
            "#lambda |x : A| /*some comment*/ x",
            "#lambda |x : A| { /* my variable x*/ x }",
            "#lambda |y : B, z : C| { let x = y; x }",
            "#lambda |world: F, y: C| { let hello = (world y) z; let x = world hello; hello x }",
            "#lambda |world: F, y: C| => T { let hello = (world y) z; let x = world hello; hello x }"
        ];
        for func in fns.iter() { assert_parses!(parse_lambda, func) }
    }

    #[test]
    fn phi_nodes_parse_properly() {
        let phis = [
            "#phi { let f = #lambda |x : A| { g x }; let g = #lambda |x : A| { f x }; }",
            "#phi { let x = 6; let y = 43; let z = 341; }"
        ];
        for phi in phis.iter() { assert_parses!(parse_phi, phi) }
    }

    #[test]
    fn gamma_nodes_parse_properly() {
        let gammas = [
            "#match {}",
            "#match { x => y }"
        ];
        for gamma in gammas.iter() { assert_parses!(parse_gamma, gamma) }
    }
}