use crate::Error;
use crate::errors::ParseError;
use crate::hash::HashMap;
use crate::limits::{Limits, Refusal, Space};
use crate::linear::fragment::Order;
use crate::linear::occurrences::Forest;
use crate::linear::occurrences::reading::Side;
use crate::linear::occurrences::written::Written;
use crate::linear::sequents::fo::{self, FoTerm, FoTermId, Interner, SymbolFault};
use crate::linear::sequents::name::{KEYWORDS, RESERVED, normalized, starts_identifier};
use crate::linear::sequents::{Atom, Sequent, Term, TermId};
use std::borrow::Cow;
const ARITY: &str = "a symbol takes the same number of arguments everywhere: \
this use differs from the first";
const ROLE: &str = "a name is a predicate or a function symbol, not both";
const KEYWORD: &str = "a keyword names no variable, constant or function symbol";
const ARROW: &str = "-> is ordinary logic's arrow: write -o";
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Binary {
Tensor,
Par,
With,
Plus,
Lollipop,
Under,
Over,
}
impl Binary {
const fn strength(self) -> u8 {
match self {
Binary::Tensor => 5,
Binary::Par => 4,
Binary::With => 3,
Binary::Plus => 2,
Binary::Lollipop | Binary::Under | Binary::Over => 1,
}
}
fn takes_before(self, next: Binary) -> bool {
self.strength() > next.strength()
|| (self == next && !matches!(self, Binary::Lollipop | Binary::Under))
}
}
#[derive(Clone, Copy, Debug)]
enum Pending {
Open,
Dual,
Bang,
Quest,
Binder(bool),
Binary(Binary, TermId),
}
enum State {
Operand,
Operator(TermId),
End,
}
struct Parser<'a> {
input: &'a str,
at: usize,
left: bool,
empty: bool,
terms: Vec<Term>,
negated: Vec<bool>,
roots: Vec<TermId>,
antecedents: u32,
atoms: Vec<String>,
names: HashMap<Cow<'a, str>, Atom>,
pending: Vec<Pending>,
open: usize,
owed: u64,
marks: u64,
most: u64,
limit: Option<u64>,
order: Order,
recording: bool,
implications: Vec<TermId>,
scope: Vec<&'a str>,
interner: Interner,
first_order: bool,
predicates: Vec<(fo::Symbol, fo::Args)>,
binders: Vec<(TermId, String)>,
}
fn read(
text: &str,
limit: Option<u64>,
terms: Option<u64>,
order: Order,
written: Option<&mut Vec<Written>>,
) -> Result<Sequent, Error> {
let mut parser = Parser::new(text, limit, order);
parser.recording = written.is_some();
let sequent = parser.sequent(written)?;
if sequent.fo.atoms.is_empty() {
return Ok(sequent);
}
first_order_within(sequent, terms)
}
#[cold]
#[inline(never)]
fn first_order_within(sequent: Sequent, terms: Option<u64>) -> Result<Sequent, Error> {
match terms {
Some(limit) if sequent.fo_size() > limit => Err(Error::Refused(Refusal::Terms {
terms: sequent.fo_size(),
limit,
})),
_ => Ok(sequent),
}
}
pub(crate) fn written(text: &str, limits: &Limits) -> Result<(Sequent, Vec<Written>), Error> {
let mut writing = Vec::new();
let sequent = read(
text,
limits.occurrences,
limits.terms,
Order::Commutative,
Some(&mut writing),
)?;
Ok((sequent, writing))
}
impl<'a> Parser<'a> {
fn new(input: &'a str, limit: Option<u64>, order: Order) -> Self {
let most = limit.unwrap_or(Forest::MOST).min(Forest::MOST);
Self {
input,
at: 0,
left: true,
empty: true,
terms: Vec::new(),
negated: Vec::new(),
roots: Vec::new(),
antecedents: 0,
atoms: Vec::new(),
names: HashMap::default(),
pending: Vec::new(),
open: 0,
owed: 0,
marks: 0,
most,
limit,
order,
recording: false,
implications: Vec::new(),
scope: Vec::new(),
interner: Interner::new(),
first_order: false,
predicates: Vec::new(),
binders: Vec::new(),
}
}
fn peek(&self) -> Option<char> {
self.input[self.at..].chars().next()
}
fn unexpected(&self, at: usize, expected: &'static [&'static str]) -> Error {
Error::from(ParseError::new(self.input, at, expected))
}
const fn operands(&self) -> &'static [&'static str] {
if self.empty && self.left {
&["a formula", "`|-`"]
} else {
&["a formula"]
}
}
const fn operators(&self) -> &'static [&'static str] {
if self.open > 0 {
&["a connective", "`)`"]
} else if self.left {
&["a connective", "`,`", "`|-`"]
} else {
&["a connective", "`,`", "the end"]
}
}
fn push(&mut self, term: Term) -> Result<TermId, Error> {
let index = self.terms.len() as u64;
if index.saturating_add(self.owed) >= self.most {
return Err(self.past_bound());
}
self.terms.push(term);
self.negated.push(false);
Ok(TermId::new(index as u32))
}
fn negate(&mut self, term: TermId) {
self.negated[term.index()] ^= true;
}
fn identifier(&mut self, start: usize) -> &'a str {
let rest = &self.input[self.at..];
let end = rest
.find(|c| !unicode_ident::is_xid_continue(c))
.unwrap_or(rest.len());
self.at += end;
&self.input[start..self.at]
}
fn atom(&mut self, name: &'a str) -> Atom {
use std::collections::hash_map::Entry;
let next = Atom::new(self.atoms.len() as u32);
match self.names.entry(normalized(name)) {
Entry::Occupied(known) => *known.get(),
Entry::Vacant(new) => {
self.atoms.push(new.key().clone().into_owned());
new.insert(next);
next
}
}
}
#[cold]
#[inline(never)]
fn nullary(&mut self, atom: Atom, name: &'a str) -> Result<(), Error> {
if atom.index() < self.predicates.len() {
return Ok(());
}
let start = self.at - name.len();
let key = self.atoms[atom.index()].clone();
let symbol = self.symbol(&key, 0, true, start..self.at)?;
let empty = self.interner.list(&[]);
self.predicates.push((symbol, empty));
Ok(())
}
#[cold]
#[inline(never)]
fn enter_first_order(&mut self, span: std::ops::Range<usize>) -> Result<(), Error> {
if std::mem::replace(&mut self.first_order, true) || self.atoms.is_empty() {
return Ok(());
}
let empty = self.interner.list(&[]);
for a in 0..self.atoms.len() {
let name = std::mem::take(&mut self.atoms[a]);
let symbol = self.symbol(&name, 0, true, span.clone());
self.atoms[a] = name;
self.predicates.push((symbol?, empty));
}
Ok(())
}
#[cold]
#[inline(never)]
fn symbol(
&mut self,
name: &str,
arity: u32,
predicate: bool,
span: std::ops::Range<usize>,
) -> Result<fo::Symbol, Error> {
self.interner
.symbol(name, arity, predicate)
.map_err(|fault| {
let hint = match fault {
SymbolFault::Arity { .. } => ARITY,
SymbolFault::Role | SymbolFault::Repeated => ROLE,
};
ParseError::spanning(self.input, span, &[])
.with_hint(hint)
.into()
})
}
#[cold]
#[inline(never)]
fn binder(&mut self, universal: bool) -> Result<State, Error> {
let keyword = self.at;
self.enter_first_order(keyword..self.at)?;
let mut names = 0;
loop {
self.skip_blank();
let start = self.at;
let Some(c) = self.peek() else {
return Err(self.unexpected(start, &["a variable name"]));
};
if c == '.' && names > 0 {
self.at += 1;
break;
}
if !starts_identifier(c) {
let expected: &'static [&'static str] = if names > 0 {
&["a variable name", "`.`"]
} else {
&["a variable name"]
};
return Err(self.unexpected(start, expected));
}
self.at += c.len_utf8();
let name = self.identifier(start);
if KEYWORDS.contains(&name) || RESERVED.contains(&name) {
let error = ParseError::spanning(self.input, start..self.at, &["a variable name"]);
return Err(error.with_hint(KEYWORD).into());
}
self.scope.push(name);
names += 1;
}
for _ in 0..names {
self.prefix(Pending::Binder(universal))?;
}
Ok(State::Operand)
}
fn skip_blank(&mut self) {
let blank = &self.input[self.at..];
self.at += blank.len() - blank.trim_start().len();
}
#[cold]
#[inline(never)]
fn predicate(&mut self, name: &'a str, start: usize) -> Result<Atom, Error> {
self.enter_first_order(start..self.at)?;
let mut open: Vec<(Cow<'a, str>, usize, Vec<FoTermId>)> =
vec![(normalized(name), start, Vec::new())];
loop {
self.skip_blank();
let at = self.at;
match self.peek() {
Some(c) if starts_identifier(c) => {
self.at += c.len_utf8();
}
_ => return Err(self.unexpected(at, &["a term"])),
}
let word = self.identifier(at);
if KEYWORDS.contains(&word) || RESERVED.contains(&word) {
let error = ParseError::spanning(self.input, at..self.at, &["a term"]);
return Err(error.with_hint(KEYWORD).into());
}
let word = normalized(word);
self.skip_blank();
if self.peek() == Some('(') {
self.at += 1;
open.push((word, at, Vec::new()));
continue;
}
let mut term = match self.scope.iter().rev().position(|&v| *v == *word) {
Some(index) => FoTerm::Bound(index as u32),
None => {
let symbol = self.symbol(&word, 0, false, at..self.at)?;
FoTerm::App(symbol, self.interner.list(&[]))
}
};
loop {
let id = self.interner.term(term);
let list = &mut open.last_mut().expect("the predicate's list is open").2;
list.push(id);
self.skip_blank();
let at = self.at;
match self.peek() {
Some(',') => {
self.at += 1;
break;
}
Some(')') => self.at += 1,
_ => return Err(self.unexpected(at, &["`,`", "`)`"])),
}
let (symbol, from, items) = open.pop().expect("an application was open");
let arity = u32::try_from(items.len()).map_err(|_| self.past_bound())?;
let args = self.interner.list(&items);
if open.is_empty() {
let symbol = self.symbol(&symbol, arity, true, from..self.at)?;
let key = self.interner.tables.atom_key(symbol, args);
let atom = match self.names.get(key.as_str()) {
Some(&atom) => atom,
None => {
let atom = Atom::new(self.atoms.len() as u32);
self.atoms.push(key.clone());
self.names.insert(Cow::Owned(key), atom);
self.predicates.push((symbol, args));
atom
}
};
return Ok(atom);
}
let symbol = self.symbol(&symbol, arity, false, from..self.at)?;
term = FoTerm::App(symbol, args);
}
}
}
fn reduce(&mut self, mut operand: TermId, next: Option<Binary>) -> Result<TermId, Error> {
while let Some(&top) = self.pending.last() {
let term = match top {
Pending::Open => break,
Pending::Dual => {
self.negate(operand);
self.pending.pop();
self.marks -= 1;
continue;
}
Pending::Bang => {
self.owed -= 1;
Term::Bang(operand)
}
Pending::Quest => {
self.owed -= 1;
Term::Quest(operand)
}
Pending::Binder(universal) => {
if next.is_some() {
break;
}
self.close_binder(universal, operand)
}
Pending::Binary(connective, left) => {
if next.is_some_and(|next| !connective.takes_before(next)) {
break;
}
match connective {
Binary::Tensor => Term::Tensor(left, operand),
Binary::Par => Term::Par(left, operand),
Binary::With => Term::With(left, operand),
Binary::Plus => Term::Plus(left, operand),
Binary::Lollipop | Binary::Under => {
self.negate(left);
if self.recording {
self.implications.push(TermId::new(self.terms.len() as u32));
}
Term::Par(left, operand)
}
Binary::Over => {
self.negate(operand);
Term::Par(left, operand)
}
}
}
};
self.pending.pop();
operand = self.push(term)?;
}
Ok(operand)
}
#[cold]
#[inline(never)]
fn close_binder(&mut self, universal: bool, operand: TermId) -> Term {
self.owed -= 1;
let name = self.scope.pop().expect("a binder has its variable");
self.binders
.push((TermId::new(self.terms.len() as u32), name.to_owned()));
if universal {
Term::Forall(operand)
} else {
Term::Exists(operand)
}
}
fn root(&mut self, operand: TermId) -> Result<(), Error> {
let root = self.reduce(operand, None)?;
if self.left {
self.negate(root);
}
self.roots.push(root);
Ok(())
}
fn turnstile(&mut self) -> State {
self.antecedents = self.roots.len() as u32;
self.left = false;
self.empty = true;
State::Operand
}
fn past_bound(&self) -> Error {
Error::Refused(match self.limit {
Some(limit) if limit < Forest::MOST => Refusal::Occurrences {
occurrences: limit.saturating_add(1),
limit,
},
_ => Refusal::Index {
what: Space::Occurrence,
count: Forest::MOST.saturating_add(1),
most: Forest::MOST,
},
})
}
fn prefix(&mut self, operator: Pending) -> Result<State, Error> {
self.empty = false;
match operator {
Pending::Dual if matches!(self.pending.last(), Some(Pending::Dual)) => {
self.pending.pop();
self.marks -= 1;
return Ok(State::Operand);
}
Pending::Bang | Pending::Quest | Pending::Binder(_) => {
self.owed += 1;
if (self.terms.len() as u64).saturating_add(self.owed) > self.most {
return Err(self.past_bound());
}
}
Pending::Open | Pending::Dual => {
self.marks += 1;
if self.marks > self.most {
return Err(self.past_bound());
}
}
Pending::Binary(..) => {}
}
self.pending.push(operator);
Ok(State::Operand)
}
fn operand(&mut self) -> Result<State, Error> {
let start = self.at;
let Some(c) = self.peek() else {
return if self.empty && !self.left {
Ok(State::End)
} else {
Err(self.unexpected(start, self.operands()))
};
};
self.at += c.len_utf8();
let term = match c {
'~' => return self.prefix(Pending::Dual),
'!' => return self.prefix(Pending::Bang),
'?' => return self.prefix(Pending::Quest),
'(' => {
self.open += 1;
return self.prefix(Pending::Open);
}
'0' => Term::Zero,
'1' => Term::One,
'⊥' => Term::Bot,
'⊤' => Term::Top,
'∀' => return self.binder(true),
'∃' => return self.binder(false),
'⊢' if self.empty && self.left => return Ok(self.turnstile()),
'|' if self.empty && self.left => {
if self.peek() != Some('-') {
return Err(self.unexpected(self.at, &["the `-` of `|-`"]));
}
self.at += 1;
return Ok(self.turnstile());
}
_ if starts_identifier(c) => match self.identifier(start) {
"bot" => Term::Bot,
"top" => Term::Top,
"par" => {
let error = ParseError::spanning(self.input, start..self.at, self.operands());
return Err(error.into());
}
"forall" => return self.binder(true),
"exists" => return self.binder(false),
name if self.input.as_bytes().get(self.at) == Some(&b'(') => {
self.at += 1;
Term::Atom(self.predicate(name, start)?)
}
name => {
let atom = self.atom(name);
if self.first_order {
self.nullary(atom, name)?;
}
Term::Atom(atom)
}
},
_ => return Err(self.unexpected(start, self.operands())),
};
self.empty = false;
Ok(State::Operator(self.push(term)?))
}
fn operator(&mut self, operand: TermId) -> Result<State, Error> {
let start = self.at;
let outermost = self.open == 0;
let Some(c) = self.peek() else {
if self.left || !outermost {
return Err(self.unexpected(start, self.operators()));
}
self.root(operand)?;
return Ok(State::End);
};
self.at += c.len_utf8();
let connective = match c {
'^' => {
self.negate(operand);
return Ok(State::Operator(operand));
}
'*' | '⊗' => Binary::Tensor,
'⅋' => Binary::Par,
'&' => Binary::With,
'+' | '⊕' => Binary::Plus,
'⊸' => Binary::Lollipop,
'-' => {
if self.peek() == Some('>') {
return Err(ParseError::new(self.input, self.at, &["the `o` of `-o`"])
.with_hint(ARROW)
.into());
}
if self.peek() != Some('o') {
return Err(self.unexpected(self.at, &["the `o` of `-o`"]));
}
self.at += 1;
Binary::Lollipop
}
'\\' if self.order != Order::Commutative => Binary::Under,
'/' if self.order != Order::Commutative => Binary::Over,
'|' if self.left && outermost && self.peek() == Some('-') => {
self.at += 1;
self.root(operand)?;
return Ok(self.turnstile());
}
'|' => Binary::Par,
'⊢' if self.left && outermost => {
self.root(operand)?;
return Ok(self.turnstile());
}
',' if outermost => {
self.root(operand)?;
return Ok(State::Operand);
}
')' if !outermost => {
let inner = self.reduce(operand, None)?;
self.pending.pop();
self.open -= 1;
self.marks -= 1;
return Ok(State::Operator(inner));
}
_ if starts_identifier(c) && self.identifier(start) == "par" => Binary::Par,
_ => return Err(self.unexpected(start, self.operators())),
};
let left = self.reduce(operand, Some(connective))?;
self.pending.push(Pending::Binary(connective, left));
Ok(State::Operand)
}
fn sequent(mut self, written: Option<&mut Vec<Written>>) -> Result<Sequent, Error> {
let mut state = State::Operand;
loop {
let blank = &self.input[self.at..];
self.at += blank.len() - blank.trim_start().len();
state = match state {
State::Operand => self.operand()?,
State::Operator(operand) => self.operator(operand)?,
State::End => return self.finish(written),
};
}
}
fn dualise<const ORDERED: bool>(&mut self) {
for n in (0..self.terms.len()).rev() {
if self.negated[n] {
let mut term = self.terms[n].dual();
if ORDERED {
term = match term {
Term::Tensor(l, r) => Term::Tensor(r, l),
Term::Par(l, r) => Term::Par(r, l),
other => other,
};
}
self.terms[n] = term;
for k in term.subterms() {
self.negated[k.index()] ^= true;
}
}
}
}
fn written(&self) -> Vec<Written> {
let mut implication = vec![false; self.terms.len()];
for &term in &self.implications {
implication[term.index()] = true;
}
let mut writing = Vec::with_capacity(self.terms.len());
let mut stack = Vec::new();
for &root in &self.roots {
stack.push(root);
while let Some(term) = stack.pop() {
let side = if self.negated[term.index()] {
Side::Input
} else {
Side::Output
};
writing.push(Written::new(side, implication[term.index()]));
let (left, right) = self.terms[term.index()].operands();
stack.extend(right);
stack.extend(left);
}
}
writing
}
fn finish(mut self, written: Option<&mut Vec<Written>>) -> Result<Sequent, Error> {
if self.order == Order::Commutative {
self.dualise::<false>();
} else {
self.dualise::<true>();
self.roots[..self.antecedents as usize].reverse();
}
if let Some(written) = written {
*written = self.written();
}
let mut fo = self.interner.tables;
fo.atoms = self.predicates;
fo.binders = self.binders;
let mut sequent = Sequent {
terms: self.terms,
roots: self.roots,
atoms: self.atoms,
antecedents: Some(self.antecedents),
cuts: vec![],
fo,
};
debug_assert!(sequent.check().is_ok(), "{:?}", sequent.check());
sequent.optimize();
Ok(sequent)
}
}
impl Sequent {
pub fn parse_within(text: &str, limits: &Limits) -> Result<Self, Error> {
read(
text,
limits.occurrences,
limits.terms,
Order::Commutative,
None,
)
}
pub fn parse_ordered(text: &str, order: Order, limits: &Limits) -> Result<Self, Error> {
read(text, limits.occurrences, limits.terms, order, None)
}
}
const NEGATION: &str = "intuitionistic linear logic has no negation: write a negated formula \
on the other side of |- (A |- B, not |- ~A, B), and ~A par B as A -o B";
const PAR: &str = "intuitionistic linear logic has no par: write ~A par B as A -o B";
const QUEST: &str = "intuitionistic linear logic has no ?: write ?~A right of |- as !A left of it";
const BOT: &str = "intuitionistic linear logic has no bot: write bot right of |- as 1 left of it";
pub(crate) fn classical(text: &str, before: usize) -> Option<ParseError> {
let mut chars = text.char_indices().peekable();
while let Some((at, c)) = chars.next() {
if at >= before {
return None;
}
let mut end = at + c.len_utf8();
let mut next_is = |d: char| {
let is = chars.peek().is_some_and(|&(_, next)| next == d);
if is {
chars.next();
}
is
};
let hint = match c {
'~' | '^' => NEGATION,
'⅋' => PAR,
'|' if next_is('-') => continue,
'-' if next_is('o') => continue,
'|' => PAR,
'?' => QUEST,
'⊥' => BOT,
_ if starts_identifier(c) => {
while let Some(&(next, d)) = chars.peek() {
if !unicode_ident::is_xid_continue(d) {
break;
}
end = next + d.len_utf8();
chars.next();
}
match &text[at..end] {
"par" => PAR,
"bot" => BOT,
_ => continue,
}
}
_ => continue,
};
return Some(ParseError::spanning(text, at..end, &[]).with_hint(hint));
}
None
}
impl std::str::FromStr for Sequent {
type Err = Error;
fn from_str(s: &str) -> Result<Self, Self::Err> {
Self::parse_within(s, &Limits::default())
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn refuses_more_terms_than_the_arena_holds() {
let input = "A |- !A * B";
assert_eq!(
Parser::new(input, Some(5), Order::Commutative)
.sequent(None)
.unwrap()
.terms()
.len(),
5
);
assert!(matches!(
Parser::new(input, Some(4), Order::Commutative).sequent(None),
Err(Error::Refused(Refusal::Occurrences {
occurrences: 5,
limit: 4
}))
));
}
}