Lines
93.99 %
Functions
68.57 %
Branches
100 %
use winnow::ascii::{digit1, line_ending, space0, till_line_ending};
use winnow::combinator::{alt, cut_err, opt, preceded};
use winnow::error::{AddContext, ContextError, ErrMode, ModalResult, StrContext, StrContextValue};
use winnow::prelude::*;
use winnow::token::{any, none_of, take_till, take_while};
use tracing::debug;
use crate::ast::{Annotation, Expr, Fraction, Program};
use crate::error::{Error, Result};
pub struct Reader;
impl Reader {
pub fn parse(input: &str) -> Result<Program> {
debug!(input_len = input.len(), "parse start");
let mut remaining = input;
let (exprs, annotations) = parse_program(&mut remaining).map_err(|e| {
let offset = input.len() - remaining.len();
Error::parse(format_parse_error(e), input, offset..offset + 1)
})?;
debug!(
expr_count = exprs.len(),
annotation_count = annotations.len(),
"parse complete"
);
Ok(Program::with_annotations(exprs, annotations))
}
#[must_use]
pub fn is_incomplete(input: &str) -> bool {
parse_program(&mut remaining).is_err() && remaining.is_empty()
pub fn parse_expr(input: &str) -> Result<Expr> {
parse_expr(&mut remaining).map_err(|e| {
})
fn format_parse_error(err: ErrMode<ContextError>) -> String {
match err {
ErrMode::Backtrack(ctx) | ErrMode::Cut(ctx) => format_context_error(&ctx),
ErrMode::Incomplete(_) => "unexpected end of input".to_string(),
fn format_context_error(ctx: &ContextError) -> String {
let mut parts = Vec::new();
for c in ctx.context() {
match c {
StrContext::Label(label) => parts.push(format!("in {label}")),
StrContext::Expected(StrContextValue::Description(desc)) => {
parts.push(format!("expected {desc}"));
StrContext::Expected(StrContextValue::CharLiteral(c)) => {
parts.push(format!("expected '{c}'"));
StrContext::Expected(StrContextValue::StringLiteral(s)) => {
parts.push(format!("expected \"{s}\""));
_ => {}
if parts.is_empty() {
"parse error".to_string()
} else {
parts.join(", ")
fn skip_ws_and_comments(input: &mut &str, annotations: &mut Vec<Annotation>) -> ModalResult<()> {
loop {
let _ = space0.parse_next(input)?;
if input.starts_with("; @") {
let _ = "; @".parse_next(input)?;
let name: &str = take_while(1.., |c: char| c.is_alphanumeric() || c == '-' || c == '_')
.parse_next(input)?;
let value = parse_expr(input).unwrap_or(Expr::Nil);
annotations.push(Annotation {
name: name.to_string(),
value,
});
let _ = till_line_ending.parse_next(input)?;
let _ = opt(line_ending).parse_next(input)?;
} else if input.starts_with(';') {
} else if input.starts_with('\n') || input.starts_with('\r') {
let _ = line_ending.parse_next(input)?;
break;
Ok(())
fn skip_ws_and_comments_no_annotations(input: &mut &str) -> ModalResult<()> {
let mut dummy = Vec::new();
skip_ws_and_comments(input, &mut dummy)
fn parse_program(input: &mut &str) -> ModalResult<(Vec<Expr>, Vec<Annotation>)> {
let mut annotations = Vec::new();
skip_ws_and_comments(input, &mut annotations)?;
let mut exprs = Vec::new();
if input.is_empty() {
let expr = parse_expr(input)?;
exprs.push(expr);
Ok((exprs, annotations))
fn parse_expr(input: &mut &str) -> ModalResult<Expr> {
let expr = alt((
parse_nil,
parse_bool,
parse_number,
parse_string,
parse_quote,
parse_quasiquote,
parse_unquote,
parse_list,
parse_keyword,
parse_symbol,
))
debug!(expr = ?expr, "parsed expression");
Ok(expr)
fn parse_nil(input: &mut &str) -> ModalResult<Expr> {
alt(("nil", "NIL", "Nil"))
.value(Expr::Nil)
.parse_next(input)
fn parse_bool(input: &mut &str) -> ModalResult<Expr> {
alt(("#t", "#T", "#f", "#F"))
.map(|s: &str| match s {
"#t" | "#T" => Expr::Bool(true),
_ => Expr::Nil,
fn is_delimiter(c: char) -> bool {
c.is_whitespace() || "()\"'`,;".contains(c)
fn parse_number(input: &mut &str) -> ModalResult<Expr> {
let sign = opt(alt(("-".value(-1i64), "+".value(1i64))))
.map(|s| s.unwrap_or(1))
let int_part: &str = digit1.parse_next(input)?;
let int_val: i64 = int_part
.parse()
.map_err(|_| ErrMode::Cut(ContextError::new()))?;
let frac_part = opt(preceded('.', digit1)).parse_next(input)?;
if input.starts_with(|c: char| !is_delimiter(c)) {
return Err(ErrMode::Backtrack(ContextError::new()));
let fraction = if let Some(decimals) = frac_part {
let decimal_places = decimals.len() as u32;
let decimal_val: i64 = decimals
let denom = 10i64.pow(decimal_places);
Fraction::new(sign * (int_val * denom + decimal_val), denom)
Fraction::from_integer(sign * int_val)
};
Ok(Expr::Number(fraction))
fn parse_string(input: &mut &str) -> ModalResult<Expr> {
alt((parse_triple_quoted_string, parse_double_quoted_string)).parse_next(input)
fn parse_double_quoted_string(input: &mut &str) -> ModalResult<Expr> {
let _ = '"'.parse_next(input)?;
let mut result = String::new();
let chunk: &str = take_till(0.., |c| c == '"' || c == '\\').parse_next(input)?;
result.push_str(chunk);
match cut_err(any)
.context(StrContext::Label("string"))
.context(StrContext::Expected(StrContextValue::Description(
"closing quote",
)))
.parse_next(input)?
{
'"' => return Ok(Expr::String(result)),
'\\' => {
let escaped = any.parse_next(input)?;
match escaped {
'n' => result.push('\n'),
't' => result.push('\t'),
'r' => result.push('\r'),
'\\' => result.push('\\'),
'"' => result.push('"'),
c => {
result.push('\\');
result.push(c);
_ => unreachable!(),
fn parse_triple_quoted_string(input: &mut &str) -> ModalResult<Expr> {
let _ = "\"\"\"".parse_next(input)?;
let mut content = String::new();
if input.starts_with("\"\"\"") {
return Ok(Expr::String(content));
return Err(ErrMode::Cut(
ContextError::new()
.add_context(input, &input.checkpoint(), StrContext::Label("string"))
.add_context(
input,
&input.checkpoint(),
StrContext::Expected(StrContextValue::Description("closing \"\"\"")),
),
));
content.push(any.parse_next(input)?);
fn parse_quote(input: &mut &str) -> ModalResult<Expr> {
let _ = '\''.parse_next(input)?;
let expr = parse_expr.parse_next(input)?;
Ok(Expr::Quote(Box::new(expr)))
fn parse_quasiquote(input: &mut &str) -> ModalResult<Expr> {
let _ = '`'.parse_next(input)?;
Ok(Expr::Quasiquote(Box::new(expr)))
fn parse_unquote(input: &mut &str) -> ModalResult<Expr> {
let _ = ','.parse_next(input)?;
if input.starts_with('@') {
let _ = '@'.parse_next(input)?;
return Ok(Expr::UnquoteSplicing(Box::new(expr)));
Ok(Expr::Unquote(Box::new(expr)))
fn parse_list(input: &mut &str) -> ModalResult<Expr> {
let _ = '('.parse_next(input)?;
skip_ws_and_comments_no_annotations(input)?;
let mut items = Vec::new();
let mut dotted_cdr: Option<Expr> = None;
if input.starts_with(')') {
.add_context(input, &input.checkpoint(), StrContext::Label("list"))
StrContext::Expected(StrContextValue::Description("closing paren")),
if input.starts_with('.') && input.chars().nth(1).is_some_and(char::is_whitespace) {
let _ = '.'.parse_next(input)?;
dotted_cdr = Some(
cut_err(parse_expr)
.context(StrContext::Label("cdr expression"))
.parse_next(input)?,
cut_err(')')
.context(StrContext::Label("closing paren"))
"only one expression after dot in dotted pair",
items.push(expr);
if dotted_cdr.is_none() {
.context(StrContext::Label("list"))
"closing paren",
if let Some(cdr) = dotted_cdr {
let mut result = cdr;
for item in items.into_iter().rev() {
result = Expr::cons(item, result);
Ok(result)
Ok(Expr::List(items))
fn parse_keyword(input: &mut &str) -> ModalResult<Expr> {
let _ = ':'.parse_next(input)?;
let first: char =
none_of(|c: char| c.is_whitespace() || "()\"'`,".contains(c)).parse_next(input)?;
let rest: &str = take_while(0.., |c: char| !c.is_whitespace() && !"()\"'`,".contains(c))
let mut name = String::with_capacity(1 + rest.len());
name.push(first);
name.push_str(rest);
name.make_ascii_uppercase();
Ok(Expr::Keyword(name))
fn parse_symbol(input: &mut &str) -> ModalResult<Expr> {
if name == "NIL" {
return Ok(Expr::Nil);
if name == "T" {
return Ok(Expr::Bool(true));
Ok(Expr::Symbol(name))
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_parse_nil() {
let program = Reader::parse("nil").unwrap();
assert_eq!(program.exprs, vec![Expr::Nil]);
fn test_parse_bool() {
let program = Reader::parse("#t #T t T").unwrap();
assert_eq!(
program.exprs,
vec![
Expr::Bool(true),
]
fn test_parse_false_is_nil() {
let program = Reader::parse("#f #F").unwrap();
assert_eq!(program.exprs, vec![Expr::Nil, Expr::Nil]);
fn test_parse_nil_case_insensitive() {
assert_eq!(Reader::parse("nil").unwrap().exprs, vec![Expr::Nil]);
assert_eq!(Reader::parse("NIL").unwrap().exprs, vec![Expr::Nil]);
assert_eq!(Reader::parse("Nil").unwrap().exprs, vec![Expr::Nil]);
fn test_parse_integer() {
let program = Reader::parse("42").unwrap();
vec![Expr::Number(Fraction::from_integer(42))]
fn test_parse_negative_number() {
let program = Reader::parse("-17").unwrap();
vec![Expr::Number(Fraction::from_integer(-17))]
fn test_parse_decimal() {
let program = Reader::parse("0.1").unwrap();
assert_eq!(program.exprs, vec![Expr::Number(Fraction::new(1, 10))]);
fn test_parse_symbol() {
let program = Reader::parse("foo").unwrap();
assert_eq!(program.exprs, vec![Expr::Symbol("FOO".into())]);
fn test_parse_symbol_case_insensitive() {
Reader::parse("foo").unwrap().exprs,
Reader::parse("FOO").unwrap().exprs
Reader::parse("Sum").unwrap().exprs,
Reader::parse("SUM").unwrap().exprs
fn test_parse_keyword() {
let program = Reader::parse(":foo").unwrap();
assert_eq!(program.exprs, vec![Expr::Keyword("FOO".into())]);
fn test_parse_keyword_case_insensitive() {
Reader::parse(":foo").unwrap().exprs,
Reader::parse(":FOO").unwrap().exprs
Reader::parse(":Name").unwrap().exprs,
Reader::parse(":NAME").unwrap().exprs
fn test_parse_string() {
let program = Reader::parse(r#""hello""#).unwrap();
assert_eq!(program.exprs, vec![Expr::String("hello".into())]);
fn test_parse_string_with_escapes() {
let program = Reader::parse(r#""hello\nworld""#).unwrap();
assert_eq!(program.exprs, vec![Expr::String("hello\nworld".into())]);
fn test_parse_list() {
let program = Reader::parse("(+ 1 2)").unwrap();
vec![Expr::List(vec![
Expr::Symbol("+".into()),
Expr::Number(Fraction::from_integer(1)),
Expr::Number(Fraction::from_integer(2)),
])]
fn test_parse_nested_list() {
let program = Reader::parse("(define (square x) (* x x))").unwrap();
Expr::Symbol("DEFINE".into()),
Expr::List(vec![
Expr::Symbol("SQUARE".into()),
Expr::Symbol("X".into()),
]),
Expr::Symbol("*".into()),
fn test_parse_quote() {
let program = Reader::parse("'foo").unwrap();
vec![Expr::Quote(Box::new(Expr::Symbol("FOO".into())))]
fn test_parse_quoted_list() {
let program = Reader::parse("'(1 2 3)").unwrap();
vec![Expr::Quote(Box::new(Expr::List(vec![
Expr::Number(Fraction::from_integer(3)),
])))]
fn test_parse_multiple_exprs() {
let program = Reader::parse("(DEFINE x 10) (+ x 5)").unwrap();
assert_eq!(program.exprs.len(), 2);
fn test_parse_line_comment() {
let program = Reader::parse("; this is a comment\n42").unwrap();
fn test_parse_inline_comment() {
let program = Reader::parse("42 ; inline comment").unwrap();
fn test_parse_comment_in_list() {
let program = Reader::parse("(+ 1 ; add one\n 2)").unwrap();
fn test_parse_multiple_comments() {
let code = "; comment 1
; comment 2
42
; comment 3";
let program = Reader::parse(code).unwrap();
fn test_parse_only_comments() {
let program = Reader::parse("; just a comment").unwrap();
assert!(program.exprs.is_empty());
fn test_parse_annotation() {
let code = "; @test (= (count 'defun) 5)\n42";
assert_eq!(program.exprs.len(), 1);
assert_eq!(program.annotations.len(), 1);
assert_eq!(program.annotations[0].name, "test");
assert!(matches!(&program.annotations[0].value, Expr::List(_)));
fn test_parse_multiple_annotations() {
let code = "; @test (= (count 'defun) 5)\n; @test (= (count 'defvar) 2)\n42";
assert_eq!(program.annotations.len(), 2);
fn test_annotation_with_simple_expr() {
let code = "; @version 1\n42";
assert_eq!(program.annotations[0].name, "version");
program.annotations[0].value,
Expr::Number(Fraction::from_integer(1))
fn test_regular_comment_no_annotation() {
let code = "; just a comment\n42";
assert!(program.annotations.is_empty());
fn test_parse_cons() {
let program = Reader::parse("(a . b)").unwrap();
vec![Expr::cons(
Expr::Symbol("A".into()),
Expr::Symbol("B".into())
)]
fn test_parse_cons_proper_list() {
let program = Reader::parse("(a . (b . nil))").unwrap();
Expr::cons(Expr::Symbol("B".into()), Expr::Nil)
fn test_parse_improper_list() {
let program = Reader::parse("(1 2 . 3)").unwrap();
Expr::cons(
Expr::Number(Fraction::from_integer(3))
)
fn test_invalid_dotted_pair_multiple_exprs_after_dot() {
let result = Reader::parse("(1 . (2 . 3) (3 . nil))");
assert!(result.is_err());
let err = result.unwrap_err();
let msg = err.to_string();
assert!(
msg.contains("closing paren") || msg.contains("one expression after dot"),
"Error should mention closing paren or one expression after dot, got: {msg}"
fn test_parse_quasiquote() {
let program = Reader::parse("`foo").unwrap();
vec![Expr::Quasiquote(Box::new(Expr::Symbol("FOO".into())))]
fn test_parse_unquote() {
let program = Reader::parse(",foo").unwrap();
vec![Expr::Unquote(Box::new(Expr::Symbol("FOO".into())))]
fn test_parse_unquote_splicing() {
let program = Reader::parse(",@foo").unwrap();
vec![Expr::UnquoteSplicing(Box::new(Expr::Symbol("FOO".into())))]
fn test_parse_quasiquoted_list() {
let program = Reader::parse("`(if ,test ,body)").unwrap();
vec![Expr::Quasiquote(Box::new(Expr::List(vec![
Expr::Symbol("IF".into()),
Expr::Unquote(Box::new(Expr::Symbol("TEST".into()))),
Expr::Unquote(Box::new(Expr::Symbol("BODY".into()))),