use crate::ast::{Expr, Factor};
use crate::contrasts::ContrastKind;
use crate::terms::{Term, TermList};
use solow_core::{Error, Result};
pub(crate) struct ParsedFormula {
pub response: Option<Factor>,
pub rhs: TermList,
}
#[derive(Debug, Clone, PartialEq)]
enum Tok {
Plus,
Minus,
Star,
Colon,
Tilde,
LParen,
RParen,
Slash,
Pow,
Comma,
Ident(String),
Num(f64),
}
fn err(msg: impl Into<String>) -> Error {
Error::Value(format!("formula parse error: {}", msg.into()))
}
fn tokenize(src: &str) -> Result<Vec<Tok>> {
let chars: Vec<char> = src.chars().collect();
let mut toks = Vec::new();
let mut i = 0;
while i < chars.len() {
let c = chars[i];
match c {
' ' | '\t' | '\n' | '\r' => {
i += 1;
}
'+' => {
toks.push(Tok::Plus);
i += 1;
}
'-' => {
toks.push(Tok::Minus);
i += 1;
}
':' => {
toks.push(Tok::Colon);
i += 1;
}
'~' => {
toks.push(Tok::Tilde);
i += 1;
}
'(' => {
toks.push(Tok::LParen);
i += 1;
}
')' => {
toks.push(Tok::RParen);
i += 1;
}
',' => {
toks.push(Tok::Comma);
i += 1;
}
'/' => {
toks.push(Tok::Slash);
i += 1;
}
'*' => {
if i + 1 < chars.len() && chars[i + 1] == '*' {
toks.push(Tok::Pow);
i += 2;
} else {
toks.push(Tok::Star);
i += 1;
}
}
c if c.is_ascii_digit() || c == '.' => {
let start = i;
while i < chars.len()
&& (chars[i].is_ascii_digit()
|| chars[i] == '.'
|| chars[i] == 'e'
|| chars[i] == 'E'
|| ((chars[i] == '+' || chars[i] == '-')
&& i > start
&& (chars[i - 1] == 'e' || chars[i - 1] == 'E')))
{
i += 1;
}
let s: String = chars[start..i].iter().collect();
let v: f64 = s.parse().map_err(|_| err(format!("bad number `{s}`")))?;
toks.push(Tok::Num(v));
}
c if c.is_alphabetic() || c == '_' => {
let start = i;
while i < chars.len() && (chars[i].is_alphanumeric() || chars[i] == '_') {
i += 1;
}
let s: String = chars[start..i].iter().collect();
toks.push(Tok::Ident(s));
}
other => return Err(err(format!("unexpected character `{other}`"))),
}
}
Ok(toks)
}
struct Cursor {
toks: Vec<Tok>,
pos: usize,
}
impl Cursor {
fn peek(&self) -> Option<&Tok> {
self.toks.get(self.pos)
}
fn next(&mut self) -> Option<Tok> {
let t = self.toks.get(self.pos).cloned();
if t.is_some() {
self.pos += 1;
}
t
}
fn eat(&mut self, t: &Tok) -> bool {
if self.peek() == Some(t) {
self.pos += 1;
true
} else {
false
}
}
}
pub(crate) fn parse(src: &str) -> Result<ParsedFormula> {
let toks = tokenize(src)?;
let mut cur = Cursor { toks, pos: 0 };
let has_tilde = cur.toks.contains(&Tok::Tilde);
let response = if has_tilde {
let f = parse_factor(&mut cur)?;
if !cur.eat(&Tok::Tilde) {
return Err(err("expected `~` after response"));
}
Some(f)
} else {
None
};
let rhs = parse_term_list(&mut cur)?;
if cur.pos != cur.toks.len() {
return Err(err(format!("trailing tokens after position {}", cur.pos)));
}
Ok(ParsedFormula { response, rhs })
}
fn parse_term_list(cur: &mut Cursor) -> Result<TermList> {
let mut list = TermList::with_intercept();
let mut sign_add = true;
if cur.eat(&Tok::Plus) {
sign_add = true;
} else if cur.eat(&Tok::Minus) {
sign_add = false;
}
loop {
if let Some(Tok::Num(n)) = cur.peek().cloned() {
if n == 1.0 || n == 0.0 {
cur.next();
apply_intercept(&mut list, n, sign_add);
if !advance_sep(cur, &mut sign_add)? {
break;
}
continue;
}
}
let product = parse_product(cur)?;
if sign_add {
for t in product {
list.add(t);
}
} else {
for t in product {
list.remove(&t);
}
}
if !advance_sep(cur, &mut sign_add)? {
break;
}
}
Ok(list)
}
fn apply_intercept(list: &mut TermList, n: f64, sign_add: bool) {
let want_intercept = if n == 1.0 { sign_add } else { !sign_add };
if want_intercept {
list.set_intercept(true);
} else {
list.set_intercept(false);
}
}
fn advance_sep(cur: &mut Cursor, sign_add: &mut bool) -> Result<bool> {
match cur.peek() {
Some(Tok::Plus) => {
cur.next();
*sign_add = true;
Ok(true)
}
Some(Tok::Minus) => {
cur.next();
*sign_add = false;
Ok(true)
}
_ => Ok(false),
}
}
fn parse_product(cur: &mut Cursor) -> Result<Vec<Term>> {
let mut acc = parse_interaction(cur)?; loop {
if cur.eat(&Tok::Star) {
let rhs = parse_interaction(cur)?;
acc = full_cross(&acc, &rhs);
} else if cur.eat(&Tok::Slash) {
let rhs = parse_interaction(cur)?;
acc = nest(&acc, &rhs);
} else {
break;
}
}
Ok(acc)
}
fn full_cross(a: &[Term], b: &[Term]) -> Vec<Term> {
let mut out: Vec<Term> = Vec::new();
for t in a {
push_unique(&mut out, t.clone());
}
for t in b {
push_unique(&mut out, t.clone());
}
out.extend(interaction(a, b));
dedup_terms(out)
}
fn nest(a: &[Term], b: &[Term]) -> Vec<Term> {
let mut out: Vec<Term> = a.to_vec();
let mut combined = Term::intercept();
for t in a {
combined = combined.interact(t);
}
out.extend(interaction(std::slice::from_ref(&combined), b));
dedup_terms(out)
}
fn interaction(a: &[Term], b: &[Term]) -> Vec<Term> {
let mut out = Vec::with_capacity(a.len() * b.len());
for la in a {
for lb in b {
out.push(la.interact(lb));
}
}
out
}
fn push_unique(v: &mut Vec<Term>, t: Term) {
if !v.iter().any(|x| x == &t) {
v.push(t);
}
}
fn dedup_terms(terms: Vec<Term>) -> Vec<Term> {
let mut out: Vec<Term> = Vec::with_capacity(terms.len());
for t in terms {
push_unique(&mut out, t);
}
out
}
fn parse_interaction(cur: &mut Cursor) -> Result<Vec<Term>> {
let mut acc = parse_power(cur)?;
while cur.eat(&Tok::Colon) {
let rhs = parse_power(cur)?;
acc = dedup_terms(interaction(&acc, &rhs));
}
Ok(acc)
}
fn parse_power(cur: &mut Cursor) -> Result<Vec<Term>> {
let base = parse_term_atom(cur)?;
if cur.eat(&Tok::Pow) {
let n = match cur.next() {
Some(Tok::Num(v)) if v.fract() == 0.0 && v >= 1.0 => v as usize,
other => {
return Err(err(format!(
"`**` in a term requires a positive integer power, found {other:?}"
)))
}
};
Ok(power(&base, n))
} else {
Ok(base)
}
}
fn power(left: &[Term], n: usize) -> Vec<Term> {
let cap = n.min(left.len());
let mut all: Vec<Term> = left.to_vec();
let mut big: Vec<Term> = left.to_vec();
for _ in 1..cap {
big = dedup_terms(interaction(left, &big));
all.extend(big.iter().cloned());
}
dedup_terms(all)
}
fn parse_term_atom(cur: &mut Cursor) -> Result<Vec<Term>> {
if cur.eat(&Tok::LParen) {
let terms = parse_group(cur)?;
expect(cur, &Tok::RParen)?;
return Ok(terms);
}
Ok(vec![Term::from_factor(parse_factor(cur)?)])
}
fn parse_group(cur: &mut Cursor) -> Result<Vec<Term>> {
let mut sign_add = true;
if cur.eat(&Tok::Plus) {
sign_add = true;
} else if cur.eat(&Tok::Minus) {
sign_add = false;
}
let mut acc: Vec<Term> = Vec::new();
loop {
if let Some(Tok::Num(v)) = cur.peek().cloned() {
if v == 0.0 || v == 1.0 {
cur.next();
if !skip_sep(cur, &mut sign_add) {
break;
}
continue;
}
}
let product = parse_product(cur)?;
if sign_add {
for t in product {
push_unique(&mut acc, t);
}
} else {
for t in &product {
acc.retain(|x| x != t);
}
}
if !skip_sep(cur, &mut sign_add) {
break;
}
}
Ok(acc)
}
fn skip_sep(cur: &mut Cursor, sign_add: &mut bool) -> bool {
match cur.peek() {
Some(Tok::Plus) => {
cur.next();
*sign_add = true;
true
}
Some(Tok::Minus) => {
cur.next();
*sign_add = false;
true
}
_ => false,
}
}
fn parse_factor(cur: &mut Cursor) -> Result<Factor> {
match cur.peek().cloned() {
Some(Tok::Ident(name)) => {
cur.next();
if name == "C" {
expect(cur, &Tok::LParen)?;
let inner = match cur.next() {
Some(Tok::Ident(v)) => v,
_ => return Err(err("C(...) expects a variable name")),
};
let (contrast, arg) = if cur.eat(&Tok::Comma) {
let code = match cur.next() {
Some(Tok::Ident(c)) => c,
_ => return Err(err("C(var, ...) expects a contrast name")),
};
let kind = ContrastKind::from_name(&code).ok_or_else(|| {
err(format!("unknown contrast coding `{code}` in C(...)"))
})?;
(kind, Some(code))
} else {
(ContrastKind::Treatment, None)
};
expect(cur, &Tok::RParen)?;
Ok(Factor::Categorical {
var: inner,
contrast,
arg,
})
} else if name == "I" {
expect(cur, &Tok::LParen)?;
let expr = parse_expr(cur)?;
expect(cur, &Tok::RParen)?;
Ok(Factor::Identity {
code: format!("I({})", render_expr(&expr)),
expr,
})
} else {
Ok(Factor::Numeric(name))
}
}
other => Err(err(format!("expected a factor, found {other:?}"))),
}
}
fn expect(cur: &mut Cursor, t: &Tok) -> Result<()> {
if cur.eat(t) {
Ok(())
} else {
Err(err(format!("expected {t:?}, found {:?}", cur.peek())))
}
}
fn parse_expr(cur: &mut Cursor) -> Result<Expr> {
parse_add(cur)
}
fn parse_add(cur: &mut Cursor) -> Result<Expr> {
let mut lhs = parse_mul(cur)?;
loop {
if cur.eat(&Tok::Plus) {
let rhs = parse_mul(cur)?;
lhs = Expr::Add(Box::new(lhs), Box::new(rhs));
} else if cur.eat(&Tok::Minus) {
let rhs = parse_mul(cur)?;
lhs = Expr::Sub(Box::new(lhs), Box::new(rhs));
} else {
break;
}
}
Ok(lhs)
}
fn parse_mul(cur: &mut Cursor) -> Result<Expr> {
let mut lhs = parse_unary(cur)?;
loop {
if cur.eat(&Tok::Star) {
let rhs = parse_unary(cur)?;
lhs = Expr::Mul(Box::new(lhs), Box::new(rhs));
} else if cur.eat(&Tok::Slash) {
let rhs = parse_unary(cur)?;
lhs = Expr::Div(Box::new(lhs), Box::new(rhs));
} else {
break;
}
}
Ok(lhs)
}
fn parse_unary(cur: &mut Cursor) -> Result<Expr> {
if cur.eat(&Tok::Minus) {
let e = parse_unary(cur)?;
return Ok(Expr::Neg(Box::new(e)));
}
if cur.eat(&Tok::Plus) {
return parse_unary(cur);
}
parse_pow(cur)
}
fn parse_pow(cur: &mut Cursor) -> Result<Expr> {
let base = parse_atom(cur)?;
if cur.eat(&Tok::Pow) {
let exp = parse_unary(cur)?;
Ok(Expr::Pow(Box::new(base), Box::new(exp)))
} else {
Ok(base)
}
}
fn parse_atom(cur: &mut Cursor) -> Result<Expr> {
match cur.next() {
Some(Tok::Num(n)) => Ok(Expr::Num(n)),
Some(Tok::Ident(name)) => Ok(Expr::Var(name)),
Some(Tok::LParen) => {
let e = parse_add(cur)?;
expect(cur, &Tok::RParen)?;
Ok(e)
}
other => Err(err(format!("expected an arithmetic atom, found {other:?}"))),
}
}
fn render_expr(e: &Expr) -> String {
match e {
Expr::Num(n) => render_num(*n),
Expr::Var(v) => v.clone(),
Expr::Neg(a) => format!("-{}", render_expr(a)),
Expr::Add(a, b) => format!("{} + {}", render_expr(a), render_expr(b)),
Expr::Sub(a, b) => format!("{} - {}", render_expr(a), render_expr(b)),
Expr::Mul(a, b) => format!("{} * {}", render_expr(a), render_expr(b)),
Expr::Div(a, b) => format!("{} / {}", render_expr(a), render_expr(b)),
Expr::Pow(a, b) => format!("{} ** {}", render_expr(a), render_expr(b)),
}
}
fn render_num(n: f64) -> String {
if n.fract() == 0.0 && n.abs() < 1e15 {
format!("{}", n as i64)
} else {
format!("{n}")
}
}