claimr 0.1.0

// SPDX-License-Identifier: Apache-2.0

//! Claimr — a constraint logic programming language (Prolog III inspired).
//!
//! This crate currently provides the front end: the [`ast`] (with exact
//! rational [`Number`]s — no floating point) and a parser
//! generated by [rustemo](https://crates.io/crates/rustemo) from the
//! authoritative grammar `src/parser/claimr.rustemo`. Evaluation and
//! constraint solving are future work.
//!
//! ```
//! use claimr::{parse_program, Clause};
//!
//! let clauses = parse_program("human(socrates).\n?- human(socrates).\n").unwrap();
//! assert!(matches!(clauses[0], Clause::Fact(_)));
//! assert!(matches!(clauses[1], Clause::Query(_)));
//! ```

pub mod ast;
pub mod eval;
pub mod number;
pub mod solver;
mod parser;

pub use ast::*;
pub use eval::{Answer, EvalError, Program, Query, Solutions};
pub use number::{Number, ParseNumberError};

use rustemo::Parser as _;

/// A position in the source: 1-based line and column, plus byte offset.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Span {
    pub line: usize,
    pub column: usize,
    pub offset: usize,
}

impl From<rustemo::Position> for Span {
    fn from(p: rustemo::Position) -> Self {
        Span {
            line: p.line().unwrap_or(0),
            column: p.column().map(|c| c + 1).unwrap_or(0),
            offset: p.pos,
        }
    }
}

impl std::fmt::Display for Span {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}:{}", self.line, self.column)
    }
}

/// A syntax error, with its position in the source when known.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub struct ParseError {
    /// What went wrong, including the tokens the parser expected.
    pub message: String,
    /// 1-based line of the offending position, if known.
    pub line: Option<usize>,
    /// 1-based column of the offending position, if known.
    pub column: Option<usize>,
    /// Byte offset of the offending position, if known.
    pub offset: Option<usize>,
}

impl std::fmt::Display for ParseError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match (self.line, self.column) {
            (Some(line), Some(column)) => write!(f, "{line}:{column}: {}", self.message),
            (Some(line), None) => write!(f, "{line}: {}", self.message),
            _ => f.write_str(&self.message),
        }
    }
}

impl From<rustemo::Error> for ParseError {
    fn from(err: rustemo::Error) -> Self {
        match err {
            rustemo::Error::ParseError(e) => {
                let start = e.span.map(|s| s.start);
                ParseError {
                    message: e.message,
                    line: start.and_then(|p| p.line()),
                    column: start.and_then(|p| p.column()).map(|c| c + 1),
                    offset: start.map(|p| p.pos),
                }
            }
            rustemo::Error::IOError(e) => ParseError {
                message: e.to_string(),
                line: None,
                column: None,
                offset: None,
            },
        }
    }
}

/// Parse a whole program — a sequence of clauses — from source text.
///
/// The entire input must be consumed; whitespace and comments between clauses
/// are ignored.
pub fn parse_program(source: &str) -> Result<Vec<Clause>, ParseError> {
    parse_program_spanned(source).map(|cs| cs.into_iter().map(|(c, _)| c).collect())
}

/// Like [`parse_program`], but pairs each clause with the [`Span`] where it
/// starts — for diagnostics that must point back into the source.
pub fn parse_program_spanned(source: &str) -> Result<Vec<(Clause, Span)>, ParseError> {
    parser::claimr::ClaimrParser::new()
        .parse(source)
        .map_err(ParseError::from)
}

/// Parse exactly one clause from source text.
///
/// Fails if the input holds zero clauses or more than one.
pub fn parse_clause(source: &str) -> Result<Clause, ParseError> {
    let mut clauses = parse_program(source)?;
    match clauses.len() {
        1 => Ok(clauses.remove(0)),
        n => Err(ParseError {
            message: format!("expected exactly one clause, found {n}"),
            line: None,
            column: None,
            offset: None,
        }),
    }
}

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

    #[test]
    fn parses_fact() {
        assert!(matches!(parse_clause("human(socrates)."), Ok(Clause::Fact(_))));
    }

    #[test]
    fn parses_rule() {
        assert!(matches!(parse_clause("mortal(X) :- human(X)."), Ok(Clause::Rule { .. })));
    }

    #[test]
    fn parses_constraint_fact() {
        assert!(matches!(
            parse_clause("{ age(socrates) > 70 }."),
            Ok(Clause::ConstraintFact(_))
        ));
    }

    #[test]
    fn parses_constraint_rule() {
        assert!(matches!(
            parse_clause("eligible(X) :- { age(X) >= 18 }."),
            Ok(Clause::ConstraintRule { .. })
        ));
    }

    #[test]
    fn parses_implication() {
        assert!(matches!(
            parse_clause("{ age(X) >= 18 } => eligible(X)."),
            Ok(Clause::Implication { .. })
        ));
    }

    #[test]
    fn parses_query() {
        assert!(matches!(
            parse_clause("?- eligible(alice), { age(alice) >= 18 }."),
            Ok(Clause::Query(_))
        ));
    }

    #[test]
    fn parses_query_with_only_a_constraint_block() {
        let Clause::Query(body) = parse_clause("?- { X > 1, X < 10 }.").unwrap() else {
            panic!("expected query");
        };
        assert_eq!(body.len(), 1);
        assert!(matches!(body[0], Goal::Constraint(ref c) if c.terms.len() == 2));
    }

    #[test]
    fn parses_program() {
        let input = "human(socrates).\nmortal(X) :- human(X).\n\n?- mortal(socrates).\n";
        let clauses = parse_program(input).expect("program parses");
        assert_eq!(clauses.len(), 3);
    }

    #[test]
    fn empty_program_is_ok() {
        assert_eq!(parse_program("").unwrap(), vec![]);
        assert_eq!(parse_program("  \n\n").unwrap(), vec![]);
    }

    #[test]
    fn nested_atoms_as_arguments() {
        let clause = parse_clause("likes(mary, father(john)).").unwrap();
        let Clause::Fact(atom) = clause else { panic!("expected fact") };
        assert_eq!(atom.name, "likes");
        assert_eq!(atom.args[0], Expr::Ident("mary".into()));
        assert_eq!(
            atom.args[1],
            Expr::Atom(Box::new(Atom { name: "father".into(), args: vec![Expr::Ident("john".into())] }))
        );
    }

    #[test]
    fn numbers_and_variables() {
        let Clause::ConstraintFact(c) = parse_clause("{ X >= 18.5, Y != 3 }.").unwrap() else {
            panic!("expected constraint fact");
        };
        assert_eq!(c.terms[0].left, Expr::Var("X".into()));
        assert_eq!(c.terms[0].op, RelOp::Ge);
        assert_eq!(c.terms[0].right, Expr::Number(Number::from_ratio(37, 2).unwrap()));
        assert_eq!(c.terms[1].op, RelOp::Neq);
        assert_eq!(c.terms[1].right, Expr::Number(Number::from(3)));
    }

    #[test]
    fn all_relops() {
        for (src, op) in [
            ("=", RelOp::Eq), ("!=", RelOp::Neq), ("<", RelOp::Lt),
            (">", RelOp::Gt), ("<=", RelOp::Le), (">=", RelOp::Ge),
        ] {
            let Clause::ConstraintFact(c) = parse_clause(&format!("{{ X {src} 1 }}.")).unwrap() else {
                panic!("expected constraint fact for {src}");
            };
            assert_eq!(c.terms[0].op, op, "operator {src}");
        }
    }

    // --- arithmetic ---------------------------------------------------------

    fn num(n: i64) -> Expr {
        Expr::Number(Number::from(n))
    }
    fn var(v: &str) -> Expr {
        Expr::Var(v.into())
    }
    fn bin(op: ArithOp, l: Expr, r: Expr) -> Expr {
        Expr::Binary { op, left: Box::new(l), right: Box::new(r) }
    }
    /// The left operand of the single constraint in `{ <src> }.`
    fn lhs(src: &str) -> Expr {
        let Clause::ConstraintFact(c) = parse_clause(&format!("{{ {src} = 0 }}.")).unwrap() else {
            panic!("expected constraint fact for {src}");
        };
        c.terms.into_iter().next().unwrap().left
    }

    #[test]
    fn precedence_mul_over_add() {
        assert_eq!(lhs("1 + 2 * 3"), bin(ArithOp::Add, num(1), bin(ArithOp::Mul, num(2), num(3))));
        assert_eq!(lhs("1 * 2 + 3"), bin(ArithOp::Add, bin(ArithOp::Mul, num(1), num(2)), num(3)));
        assert_eq!(lhs("X / 2 - Y"), bin(ArithOp::Sub, bin(ArithOp::Div, var("X"), num(2)), var("Y")));
    }

    #[test]
    fn left_associativity() {
        assert_eq!(lhs("1 - 2 - 3"), bin(ArithOp::Sub, bin(ArithOp::Sub, num(1), num(2)), num(3)));
        assert_eq!(lhs("8 / 4 / 2"), bin(ArithOp::Div, bin(ArithOp::Div, num(8), num(4)), num(2)));
    }

    #[test]
    fn parentheses_group_and_vanish() {
        assert_eq!(lhs("(1 + 2) * 3"), bin(ArithOp::Mul, bin(ArithOp::Add, num(1), num(2)), num(3)));
        assert_eq!(lhs("((X))"), var("X"));
    }

    #[test]
    fn unary_minus_binds_tightest() {
        assert_eq!(lhs("-X * Y"), bin(ArithOp::Mul, Expr::Neg(Box::new(var("X"))), var("Y")));
        assert_eq!(lhs("-3"), Expr::Neg(Box::new(num(3))));
        assert_eq!(lhs("- - X"), Expr::Neg(Box::new(Expr::Neg(Box::new(var("X"))))));
        assert_eq!(lhs("-(X + 1)"), Expr::Neg(Box::new(bin(ArithOp::Add, var("X"), num(1)))));
        assert_eq!(lhs("2 - -3"), bin(ArithOp::Sub, num(2), Expr::Neg(Box::new(num(3)))));
    }

    #[test]
    fn division_is_a_node_not_a_folded_constant() {
        assert_eq!(lhs("1/3"), bin(ArithOp::Div, num(1), num(3)));
    }

    #[test]
    fn arithmetic_over_attribute_terms() {
        let age_x = Expr::Atom(Box::new(Atom { name: "age".into(), args: vec![var("X")] }));
        assert_eq!(lhs("age(X) + 1"), bin(ArithOp::Add, age_x, num(1)));
    }

    #[test]
    fn arithmetic_in_atom_arguments() {
        let Clause::Fact(atom) = parse_clause("p(X + 1, f(-(2 * Y)), 3).").unwrap() else {
            panic!("expected fact");
        };
        assert_eq!(atom.args.len(), 3);
        assert_eq!(atom.args[0], bin(ArithOp::Add, var("X"), num(1)));
        let inner = Expr::Neg(Box::new(bin(ArithOp::Mul, num(2), var("Y"))));
        assert_eq!(atom.args[1], Expr::Atom(Box::new(Atom { name: "f".into(), args: vec![inner] })));
        // ...and in rule bodies and queries.
        assert!(matches!(parse_clause("q(X) :- p(X * 2)."), Ok(Clause::Rule { .. })));
        assert!(matches!(parse_clause("?- p(1 + 1)."), Ok(Clause::Query(_))));
    }

    #[test]
    fn multi_constraint_arithmetic() {
        let Clause::ConstraintFact(c) = parse_clause("{ X + Y = 10, 2*X - Y >= 1/3 }.").unwrap() else {
            panic!("expected constraint fact");
        };
        assert_eq!(c.terms.len(), 2);
        assert_eq!(c.terms[1].op, RelOp::Ge);
        assert_eq!(c.terms[1].right, bin(ArithOp::Div, num(1), num(3)));
    }

    // --- comments -----------------------------------------------------------

    #[test]
    fn line_comments_are_layout() {
        let src = "% leading comment
                   human(socrates). % trailing comment
                   mortal(X) :- % inside a clause
                       human(X).
                   %% double percent, empty clause list follows
                   ?- mortal(socrates). % at EOF without newline";
        let clauses = parse_program(src).expect("comments should be layout");
        assert_eq!(clauses.len(), 3);
        assert_eq!(parse_program("% only a comment").unwrap(), vec![]);
        assert_eq!(parse_program("%").unwrap(), vec![]);
    }

    #[test]
    fn comment_does_not_swallow_the_next_line() {
        let clauses = parse_program("p(a). % c1
q(b).
").unwrap();
        assert_eq!(clauses.len(), 2);
    }

    #[test]
    fn error_carries_position() {
        // Missing closing paren: the `.` on line 2 sits at column 21 (1-based).
        let err = parse_program("human(socrates).\nmortal(X) :- human(X.\n").unwrap_err();
        assert_eq!(err.line, Some(2));
        assert_eq!(err.column, Some(21));
        assert!(err.message.contains("Expected"), "message: {}", err.message);
        assert!(err.to_string().starts_with("2:21: "), "display: {err}");
    }

    #[test]
    fn missing_terminating_dot_is_an_error() {
        let err = parse_program("human(socrates)").unwrap_err();
        assert_eq!(err.line, Some(1));
    }

    #[test]
    fn parse_clause_rejects_multiple_clauses() {
        let err = parse_clause("a(x). b(y).").unwrap_err();
        assert!(err.message.contains("exactly one clause"));
    }
}