use super::{Formulas, Node, NodeId, Sequent};
use crate::Error;
use crate::errors::ParseError;
use crate::limits::{Limits, Refusal};
use crate::linear::lltp::{Status, clauses};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Binary {
Iff,
Xor,
Implies,
Reverse,
Or,
Nor,
And,
Nand,
}
impl Binary {
const fn strength(self) -> u8 {
match self {
Self::Iff | Self::Xor => 1,
Self::Implies | Self::Reverse => 2,
Self::Or | Self::Nor => 3,
Self::And | Self::Nand => 4,
}
}
const fn takes_before(self, next: Self) -> bool {
self.strength() > next.strength()
|| (self.strength() == next.strength() && self.strength() >= 3)
}
}
#[derive(Clone, Copy, Debug)]
enum Pending {
Open,
Not,
Binary(Binary, NodeId),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Dialect {
Native,
Tptp,
}
struct Parser<'a> {
input: &'a str,
at: usize,
dialect: Dialect,
formulas: &'a mut Formulas,
pending: Vec<Pending>,
open: usize,
limit: Option<u64>,
}
enum End {
Comma,
Turnstile,
Stop,
}
impl<'a> Parser<'a> {
fn unexpected(&self, at: usize, expected: &'static [&'static str]) -> Error {
Error::from(ParseError::new(self.input, at, expected))
}
fn rest(&mut self) -> &'a str {
let rest = &self.input[self.at..];
self.at += rest.len() - rest.trim_start().len();
&self.input[self.at..]
}
fn eat(&mut self, token: &str) -> bool {
let found = self.rest().starts_with(token);
if found {
self.at += token.len();
}
found
}
fn negation(&mut self) -> bool {
match self.dialect {
Dialect::Native => self.eat("~") || self.eat("¬"),
Dialect::Tptp => {
let rest = self.rest();
!rest.starts_with("~|") && !rest.starts_with("~&") && self.eat("~")
}
}
}
fn identifier(&mut self) -> Option<&'a str> {
let rest = self.rest();
let first = rest.chars().next()?;
if !crate::linear::sequents::name::starts_identifier(first) {
return None;
}
let end = rest
.find(|c| !unicode_ident::is_xid_continue(c))
.unwrap_or(rest.len());
self.at += end;
Some(&rest[..end])
}
fn formula(&mut self) -> Result<(NodeId, End), Error> {
loop {
let mut operand = loop {
if self.eat("(") {
self.open += 1;
self.pending.push(Pending::Open);
count_within(self.open, self.limit)?;
} else if self.negation() {
self.wait(Pending::Not)?;
} else {
break self.constant_or_atom()?;
};
};
loop {
let at = self.at;
let binary = match self.dialect {
Dialect::Native => [
("<->", Binary::Iff),
("↔", Binary::Iff),
("->", Binary::Implies),
("→", Binary::Implies),
("\\/", Binary::Or),
("∨", Binary::Or),
("/\\", Binary::And),
("∧", Binary::And),
]
.into_iter()
.find(|(token, _)| self.eat(token)),
Dialect::Tptp => [
("<=>", Binary::Iff),
("<~>", Binary::Xor),
("=>", Binary::Implies),
("<=", Binary::Reverse),
("~|", Binary::Nor),
("|", Binary::Or),
("~&", Binary::Nand),
("&", Binary::And),
]
.into_iter()
.find(|(token, _)| self.eat(token)),
};
if let Some((_, binary)) = binary {
let left = self.reduce(operand, Some(binary))?;
self.wait(Pending::Binary(binary, left))?;
break;
}
if self.open > 0 && self.eat(")") {
operand = self.reduce(operand, None)?;
self.pending.pop();
self.open -= 1;
continue;
}
let end = if self.open > 0 {
None
} else if self.dialect == Dialect::Tptp {
self.rest().is_empty().then_some(End::Stop)
} else if self.eat(",") {
Some(End::Comma)
} else if self.eat("|-") || self.eat("⊢") {
Some(End::Turnstile)
} else if self.rest().is_empty() {
Some(End::Stop)
} else {
None
};
let Some(end) = end else {
let expected: &[&str] = if self.open > 0 {
&["a connective", "`)`"]
} else if self.dialect == Dialect::Tptp {
&["a connective", "the end"]
} else {
&["a connective", "`,`", "`|-`", "the end"]
};
return Err(self.unexpected(self.at.max(at), expected));
};
return Ok((self.reduce(operand, None)?, end));
}
}
}
fn wait(&mut self, operator: Pending) -> Result<(), Error> {
self.pending.push(operator);
count_within(self.pending.len() - self.open, self.limit)
}
fn within(&self, id: NodeId) -> Result<NodeId, Error> {
count_within(self.formulas.len(), self.limit).map(|()| id)
}
fn add(&mut self, node: Node) -> Result<NodeId, Error> {
let id = self.formulas.add(node)?;
self.within(id)
}
fn constant_or_atom(&mut self) -> Result<NodeId, Error> {
let at = self.at;
let native = self.dialect == Dialect::Native;
if native && self.eat("⊤") {
return self.add(Node::True);
}
if native && self.eat("⊥") {
return self.add(Node::False);
}
if !native && self.eat("$true") {
return self.add(Node::True);
}
if !native && self.eat("$false") {
return self.add(Node::False);
}
match self.identifier() {
Some("true") if native => self.add(Node::True),
Some("false") if native => self.add(Node::False),
Some(name) => {
let id = self.formulas.atom(name)?;
self.within(id)
}
None => Err(self.unexpected(at, &["a formula"])),
}
}
fn reduce(&mut self, mut operand: NodeId, next: Option<Binary>) -> Result<NodeId, Error> {
while let Some(&top) = self.pending.last() {
let node = match top {
Pending::Open => break,
Pending::Not => Node::Not(operand),
Pending::Binary(binary, left) => {
if next.is_some_and(|next| !binary.takes_before(next)) {
break;
}
match binary {
Binary::Iff => Node::Iff(left, operand),
Binary::Xor => Node::Not(self.add(Node::Iff(left, operand))?),
Binary::Implies => Node::Implies(left, operand),
Binary::Reverse => Node::Implies(operand, left),
Binary::Or => Node::Or(left, operand),
Binary::Nor => Node::Not(self.add(Node::Or(left, operand))?),
Binary::And => Node::And(left, operand),
Binary::Nand => Node::Not(self.add(Node::And(left, operand))?),
}
}
};
self.pending.pop();
operand = self.add(node)?;
}
Ok(operand)
}
}
impl std::str::FromStr for Sequent {
type Err = Error;
fn from_str(s: &str) -> Result<Self, Error> {
Self::parse_within(s, &Limits::default())
}
}
impl Sequent {
pub fn parse_within(s: &str, limits: &Limits) -> Result<Self, Error> {
let mut formulas = Formulas::default();
let mut parser = Parser {
input: s,
at: 0,
dialect: Dialect::Native,
formulas: &mut formulas,
pending: Vec::new(),
open: 0,
limit: limits.occurrences,
};
let (mut left, mut right) = (Vec::new(), Vec::new());
let mut turnstile = false;
if parser.eat("|-") || parser.eat("⊢") {
turnstile = true;
}
if !(turnstile && parser.rest().is_empty()) {
loop {
let (formula, end) = parser.formula()?;
if turnstile { &mut right } else { &mut left }.push(formula);
count_within(left.len() + right.len(), limits.occurrences)?;
match end {
End::Comma => {}
End::Turnstile if !turnstile => {
turnstile = true;
if parser.rest().is_empty() {
break;
}
}
End::Turnstile => {
let read = &parser.input[..parser.at];
let start = read.len() - if read.ends_with("|-") { 2 } else { "⊢".len() };
let span = start..parser.at;
let expected = &["a connective", "`,`", "the end"];
return Err(ParseError::spanning(parser.input, span, expected).into());
}
End::Stop => break,
}
}
}
if !turnstile {
std::mem::swap(&mut left, &mut right);
}
Sequent::new(formulas, left, right)
}
}
fn count_within(count: usize, limit: Option<u64>) -> Result<(), Error> {
match limit {
Some(limit) if count as u64 > limit => Err(Error::Refused(Refusal::Occurrences {
occurrences: limit.saturating_add(1),
limit,
})),
_ => Ok(()),
}
}
#[derive(Clone, Debug)]
#[non_exhaustive]
pub struct Problem {
pub sequent: Sequent,
pub status: Option<Status>,
}
pub fn read_tptp(text: &str, limits: &Limits) -> Result<Problem, Error> {
let clauses = clauses(text, |message| Error::Tptp { message })?;
let mut formulas = Formulas::default();
let mut roots = 0;
let mut read = |formula: &str| {
roots += 1;
count_within(roots, limits.occurrences)?;
let mut parser = Parser {
input: formula,
at: 0,
dialect: Dialect::Tptp,
formulas: &mut formulas,
pending: Vec::new(),
open: 0,
limit: limits.occurrences,
};
let (start, len) = (
formula.as_ptr() as usize - clauses.code().as_ptr() as usize,
formula.len(),
);
parser
.formula()
.map(|(formula, _)| formula)
.map_err(|error| {
if let Error::Parse(error) = error {
let at = |at: usize| (start + at.min(len), at >= len);
Error::Parse(Box::new(clauses.located(text, &error, at)))
} else {
error
}
})
};
let left = clauses
.hypotheses()
.map(&mut read)
.collect::<Result<_, _>>()?;
let right = vec![read(clauses.conjecture())?];
Ok(Problem {
sequent: Sequent::new(formulas, left, right)?,
status: clauses.status,
})
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn reads_the_syntax() {
let read = |text: &str| text.parse::<Sequent>().unwrap().to_string();
assert_eq!(
read("a /\\ b \\/ ~c -> d <-> e"),
"⊢ (((a ∧ b) ∨ ¬c) → d) ↔ e"
);
assert_eq!(
read("a ∧ b ∨ ¬c → d ↔ e"),
read("a /\\ b \\/ ~c -> d <-> e")
);
assert_eq!(read("a -> b -> c"), "⊢ a → (b → c)");
assert_eq!(read("a /\\ b /\\ c"), "⊢ (a ∧ b) ∧ c");
assert_eq!(read("true, ⊥ |- false, ⊤"), "⊤, ⊥ ⊢ ⊥, ⊤");
assert_eq!(read("|-"), "⊢");
assert_eq!(read("a |-"), "a ⊢");
assert_eq!(read("~~(a)"), "⊢ ¬¬a");
for bad in [
"a & b",
"a | b",
"a -o b",
"a |- b |- c",
"a ⊢ b ⊢ c",
"(a",
"a)",
"a b",
"",
] {
assert!(bad.parse::<Sequent>().is_err(), "{bad:?}");
}
for (bad, column, found) in [("a |- b |- c", 8, "|-"), ("a ⊢ b ⊢ c", 7, "⊢")] {
let Err(Error::Parse(e)) = bad.parse::<Sequent>() else {
panic!("{bad:?}");
};
assert_eq!(
(e.column, e.found.as_deref()),
(column, Some(found)),
"{bad:?}"
);
}
let Err(Error::Parse(e)) = "(a".parse::<Sequent>() else {
panic!("(a");
};
assert_eq!(e.expected, ["a connective", "`)`"]);
let Err(Error::Parse(e)) = read_tptp("fof(c, conjecture, a b).", &Limits::default()) else {
panic!("a b");
};
assert_eq!(e.expected, ["a connective", "the end"]);
}
#[test]
fn reads_tptp() {
let text = "% Status (intuit.) : Non-Theorem\n\
fof(a, axiom, ~ p => (q <= r)).\n\
fof(b, hypothesis, (p <~> q) & (p ~| $true) & (q ~& $false)).\n\
fof(c, conjecture, ~ ~ p <=> p).\n";
let problem = read_tptp(text, &Limits::default()).unwrap();
assert_eq!(problem.status, Some(Status::NonTheorem));
assert_eq!(
problem.sequent.to_string(),
"¬p → (r → q), (¬(p ↔ q) ∧ ¬(p ∨ ⊤)) ∧ ¬(q ∧ ⊥) ⊢ ¬¬p ↔ p"
);
assert!(matches!(
read_tptp("fof(c, axiom, p).", &Limits::default()),
Err(Error::Tptp { .. })
));
assert!(read_tptp("fof(c, conjecture, p -> q).", &Limits::default()).is_err());
let place = |text: &str| match read_tptp(text, &Limits::default()) {
Err(Error::Parse(e)) => (e.line, e.column, e.found.clone()),
other => panic!("{other:?}"),
};
assert_eq!(
place("fof(a, axiom, p).\nfof(b, axiom, p & ).\nfof(c, conjecture, p)."),
(2, 19, Some(")".to_owned()))
);
for (text, message) in [
(
"fof(c, conjecture, true | p).",
"the atom name \"true\" is a keyword of the syntax",
),
("fof(c, axiom, p).", "not a TPTP problem: no conjecture"),
] {
assert_eq!(
read_tptp(text, &Limits::default()).unwrap_err().to_string(),
message,
"{text}"
);
}
}
#[test]
fn refuses_several_conjectures() {
let text = "fof(a, axiom, p). fof(c1, conjecture, p). fof(c2, conjecture, q).";
assert!(matches!(
read_tptp(text, &Limits::default()),
Err(Error::SeveralConjectures { second }) if second == "c2"
));
}
}