#![deny(clippy::wildcard_enum_match_arm)]
pub mod fmt;
pub mod fo;
pub(crate) mod name;
pub(crate) mod notation;
pub mod term;
pub use fmt::Formula;
pub(crate) use fmt::{Stop, Stops};
pub use fmt::{Visit, Walk};
pub use fo::{Args, Eigen, FoTerm, FoTermId, Symbol, SymbolFault};
pub use term::{Atom, Kind, Term, TermId};
use crate::hash::HashMap;
#[cfg_attr(all(feature = "parse", feature = "serialize"), doc = "```")]
#[cfg_attr(not(all(feature = "parse", feature = "serialize")), doc = "```ignore")]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Sequent {
pub(crate) terms: Vec<Term>,
pub(crate) roots: Vec<TermId>,
pub(crate) atoms: Vec<String>,
pub(crate) antecedents: Option<u32>,
pub(crate) cuts: Vec<[TermId; 2]>,
pub(crate) fo: fo::FirstOrder,
}
impl std::default::Default for Sequent {
fn default() -> Self {
Self::new()
}
}
impl Sequent {
pub const fn new() -> Self {
Self {
terms: vec![],
roots: vec![],
atoms: vec![],
antecedents: None,
cuts: vec![],
fo: fo::FirstOrder::new(),
}
}
pub fn terms(&self) -> &[Term] {
&self.terms
}
pub fn term(&self, id: TermId) -> Term {
self.terms[id.index()]
}
pub fn roots(&self) -> &[TermId] {
&self.roots
}
pub fn antecedents(&self) -> Option<u32> {
self.antecedents
}
pub fn cuts(&self) -> &[[TermId; 2]] {
&self.cuts
}
pub fn add_cut(&mut self, formula: Self) -> Result<(), crate::Error> {
if formula.roots.len() != 1 || !formula.cuts.is_empty() {
return Err(crate::Error::CutFormula {
formulas: formula.roots.len(),
});
}
let offset_atoms = self.atoms.len() as u32;
let offset_terms = self.terms.len() as u32;
self.terms.extend(
formula
.terms
.into_iter()
.map(|e| e.offset(offset_atoms, offset_terms)),
);
self.atoms.extend(formula.atoms);
self.join_first_order(formula.fo, offset_terms);
self.merge_atoms();
self.push_cuts(&[TermId::new(formula.roots[0].get() + offset_terms)]);
Ok(())
}
pub(crate) fn push_cuts(&mut self, cuts: &[TermId]) {
if cuts.is_empty() {
return;
}
let mut known =
HashMap::<Term, TermId>::with_capacity_and_hasher(self.terms.len(), Default::default());
for (n, &term) in self.terms.iter().enumerate().rev() {
known.insert(term, TermId::new(n as u32));
}
let mut dual = HashMap::<TermId, TermId>::default();
let mut waiting: Vec<(TermId, bool)> = Vec::new();
for &a in cuts {
waiting.push((a, false));
while let Some((t, ready)) = waiting.pop() {
if dual.contains_key(&t) {
continue;
}
if !ready {
waiting.push((t, true));
let below = self.terms[t.index()].subterms();
waiting.extend(below.filter(|k| !dual.contains_key(k)).map(|k| (k, false)));
continue;
}
let term = self.terms[t.index()].dual().map_subterms(|k| dual[&k]);
let id = match known.get(&term) {
Some(&id) => id,
None => {
let fresh = TermId::new(self.terms.len() as u32);
known.insert(term, fresh);
self.terms.push(term);
if let Some(name) = self.fo.binder_name(t) {
let name = name.to_owned();
self.fo.binders.push((fresh, name));
}
fresh
}
};
dual.insert(t, id);
}
self.cuts.push([a, dual[&a]]);
}
}
#[cfg(feature = "interactive")]
pub(crate) fn pop_cut(&mut self) {
self.pop_cut_keeping(0, false);
}
#[cfg(feature = "interactive")]
pub(crate) fn pop_cut_keeping(&mut self, terms: usize, symbols: bool) {
self.cuts.pop();
let end = self
.roots
.iter()
.chain(self.cuts.iter().flatten())
.map(|t| t.index() + 1)
.max()
.unwrap_or(0);
self.terms.truncate(end);
let atoms = self
.terms
.iter()
.filter_map(|t| t.atom())
.map(|a| a.index() + 1)
.max()
.unwrap_or(0);
self.atoms.truncate(atoms);
self.fo.atoms.truncate(atoms.min(self.fo.atoms.len()));
self.fo.binders.retain(|&(t, _)| t.index() < end);
if !self.fo.is_empty() {
self.fo.trim(terms, symbols);
}
}
#[cfg(feature = "parse")]
pub(crate) fn from_parts(
terms: Vec<Term>,
roots: Vec<TermId>,
atoms: Vec<String>,
antecedents: Option<u32>,
) -> Self {
let sequent = Self {
terms,
roots,
atoms,
antecedents,
cuts: vec![],
fo: fo::FirstOrder::new(),
};
debug_assert!(sequent.check().is_ok());
sequent
}
pub fn atom_names(&self) -> &[String] {
&self.atoms
}
pub fn atom_name(&self, atom: Atom) -> &str {
&self.atoms[atom.index()]
}
pub fn atom(&self, name: &str) -> Option<Atom> {
self.atoms
.iter()
.position(|n| n == name)
.map(|i| Atom::new(i as u32))
}
pub fn is_first_order(&self) -> bool {
!self.fo.is_empty()
}
pub fn atom_predicate(&self, atom: Atom) -> Option<(Symbol, Args)> {
self.fo.atoms.get(atom.index()).copied()
}
pub fn fo_size(&self) -> u64 {
if self.fo.atoms.is_empty() {
return 0;
}
let unfolded = self.fo.unfolded();
self.fo.atoms.iter().fold(0u64, |sum, &(_, args)| {
self.fo
.list(args)
.iter()
.fold(sum, |sum, t| sum.saturating_add(unfolded[t.index()]))
})
}
pub fn atom_is_open(&self, atom: Atom) -> bool {
self.atom_predicate(atom).is_some_and(|(_, args)| {
let loose = self.fo.loose();
self.fo.list(args).iter().any(|t| loose[t.index()] > 0)
})
}
pub fn symbols(&self) -> &[(String, u32)] {
&self.fo.symbols
}
pub fn fo_terms(&self) -> &[FoTerm] {
&self.fo.terms
}
pub fn arguments(&self, args: Args) -> &[FoTermId] {
self.fo.list(args)
}
pub fn binder_name(&self, term: TermId) -> Option<&str> {
self.fo.binder_name(term)
}
pub(crate) fn sizes(&self) -> Vec<u64> {
let mut sizes = vec![0u64; self.terms.len()];
for (n, term) in self.terms.iter().enumerate() {
sizes[n] = term
.subterms()
.fold(1u64, |sum, k| sum.saturating_add(sizes[k.index()]));
}
sizes
}
pub fn occurrences(&self) -> u64 {
self.occurrences_of(&self.sizes())
}
pub(crate) fn occurrences_of(&self, sizes: &[u64]) -> u64 {
self.roots
.iter()
.chain(self.cuts.iter().flatten())
.fold(0u64, |sum, r| sum.saturating_add(sizes[r.index()]))
}
#[cfg(any(test, feature = "parse", feature = "serialize"))]
pub(crate) fn check(&self) -> Result<(), crate::Error> {
let num_atoms = self.atoms.len() as u32;
let num_terms = self.terms.len() as u32;
self.terms
.iter()
.enumerate()
.try_for_each(|(n, e)| e.check_bounds(num_atoms, n as u32))?;
self.roots
.iter()
.chain(self.cuts.iter().flatten())
.try_for_each(|n| {
if n.get() >= num_terms {
Err(crate::Error::IndexOutOfBounds {
space: crate::limits::Space::Term,
index: n.index(),
len: num_terms as usize,
})
} else {
Ok(())
}
})?;
match self.antecedents {
Some(k) if k as usize > self.roots.len() => {
return Err(crate::Error::Antecedents {
antecedents: k as usize,
roots: self.roots.len(),
});
}
_ => {}
}
if self.fo.is_empty() {
return Ok(());
}
self.fo.check(self.atoms.len())?;
let fo_loose = self.fo.loose();
let mut loose = vec![0u32; self.terms.len()];
for (n, term) in self.terms.iter().enumerate() {
loose[n] = match *term {
Term::Atom(a) | Term::DualAtom(a) => {
self.fo.atoms.get(a.index()).map_or(0, |&(_, args)| {
self.fo
.list(args)
.iter()
.map(|t| fo_loose[t.index()])
.max()
.unwrap_or(0)
})
}
Term::Forall(k) | Term::Exists(k) => loose[k.index()].saturating_sub(1),
Term::One
| Term::Bot
| Term::Top
| Term::Zero
| Term::Tensor(..)
| Term::Par(..)
| Term::With(..)
| Term::Plus(..)
| Term::Bang(_)
| Term::Quest(_) => term.subterms().map(|k| loose[k.index()]).max().unwrap_or(0),
};
}
for root in self.roots.iter().chain(self.cuts.iter().flatten()) {
if loose[root.index()] > 0 {
return Err(crate::Error::LooseVariable { term: root.index() });
}
}
for &(t, _) in &self.fo.binders {
if t.index() >= self.terms.len() || !self.terms[t.index()].kind().is_binder() {
return Err(crate::Error::IndexOutOfBounds {
space: crate::limits::Space::Term,
index: t.index(),
len: self.terms.len(),
});
}
}
Ok(())
}
fn optimize_terms(&mut self) {
let num_terms = self.terms.len();
let mut reachable = vec![false; num_terms];
for n in self.roots.iter().chain(self.cuts.iter().flatten()) {
reachable[n.index()] = true;
}
for n in (0..num_terms).rev() {
if !reachable[n] {
continue;
}
for k in self.terms[n].subterms() {
debug_assert!(k.index() < n, "a subterm precedes its parent");
reachable[k.index()] = true;
}
}
let mut new_index = vec![None; num_terms];
let mut terms = Vec::with_capacity(num_terms);
let mut kept = HashMap::<Term, TermId>::default();
for (n, e) in self.terms.iter().enumerate() {
if !reachable[n] {
continue;
}
let e = e.map_subterms(|k| new_index[k.index()].unwrap());
let fresh_index = TermId::new(terms.len() as u32);
let index = *kept.entry(e).or_insert(fresh_index);
if index == fresh_index {
terms.push(e);
}
new_index[n] = Some(index);
}
self.terms = terms;
self.roots = self
.roots
.iter()
.map(|k| new_index[k.index()].unwrap())
.collect();
for pair in &mut self.cuts {
*pair = pair.map(|k| new_index[k.index()].unwrap());
}
if !self.fo.binders.is_empty() {
let mut binders = Vec::with_capacity(self.fo.binders.len());
for (t, name) in std::mem::take(&mut self.fo.binders) {
if let Some(t) = new_index[t.index()] {
binders.push((t, name));
}
}
binders.sort_by_key(|&(t, _)| t);
binders.dedup_by_key(|&mut (t, _)| t);
self.fo.binders = binders;
}
}
fn renumber_atoms(&mut self) {
use Term::*;
const UNUSED: u32 = u32::MAX;
let mut number = vec![UNUSED; self.atoms.len()];
let mut entries = Vec::with_capacity(self.atoms.len());
for e in &mut self.terms {
let (Atom(a) | DualAtom(a)) = e else {
continue;
};
let slot = &mut number[a.index()];
if *slot == UNUSED {
*slot = entries.len() as u32;
entries.push(a.index());
}
*a = term::Atom::new(*slot);
}
let mut names = std::mem::take(&mut self.atoms);
if !self.fo.atoms.is_empty() {
let predicates = std::mem::take(&mut self.fo.atoms);
self.fo.atoms = entries.iter().map(|&entry| predicates[entry]).collect();
}
self.atoms = entries
.into_iter()
.map(|entry| std::mem::take(&mut names[entry]))
.collect();
}
pub fn optimize(&mut self) {
self.merge_atoms();
self.optimize_terms();
self.renumber_atoms();
}
pub(crate) fn merge_atoms(&mut self) {
use Term::*;
let mut seen = HashMap::<&str, term::Atom>::with_capacity_and_hasher(
self.atoms.len(),
Default::default(),
);
let mut merged = Vec::with_capacity(self.atoms.len());
for name in &self.atoms {
let fresh = term::Atom::new(seen.len() as u32);
merged.push(*seen.entry(name).or_insert(fresh));
}
let distinct = seen.len();
drop(seen);
if distinct == self.atoms.len() {
return;
}
for e in &mut self.terms {
*e = match *e {
Atom(a) => Atom(merged[a.index()]),
DualAtom(a) => DualAtom(merged[a.index()]),
other @ One
| other @ Bot
| other @ Top
| other @ Zero
| other @ Tensor(..)
| other @ Par(..)
| other @ With(..)
| other @ Plus(..)
| other @ Bang(_)
| other @ Quest(_)
| other @ Forall(_)
| other @ Exists(_) => other,
};
}
let (mut old, mut kept) = (0, 0);
self.atoms.retain(|_| {
let first = merged[old].index() == kept;
old += 1;
kept += usize::from(first);
first
});
if !self.fo.atoms.is_empty() {
let (mut old, mut kept) = (0, 0);
self.fo.atoms.retain(|_| {
let first = merged[old].index() == kept;
old += 1;
kept += usize::from(first);
first
});
}
}
pub fn add(&mut self, s: Self) {
let offset_atoms = self.atoms.len() as u32;
let offset_terms = self.terms.len() as u32;
self.terms.extend(
s.terms
.into_iter()
.map(|e| e.offset(offset_atoms, offset_terms)),
);
self.roots.extend(
s.roots
.into_iter()
.map(|n| TermId::new(n.get() + offset_terms)),
);
self.cuts.extend(
s.cuts
.into_iter()
.map(|pair| pair.map(|n| TermId::new(n.get() + offset_terms))),
);
self.atoms.extend(s.atoms);
self.join_first_order(s.fo, offset_terms);
self.antecedents = None;
self.merge_atoms();
}
fn join_first_order(&mut self, other: fo::FirstOrder, terms_offset: u32) {
if other.is_empty() && self.fo.is_empty() {
return;
}
let own_atoms = if self.fo.is_empty() {
self.atoms.len() - other_atoms(&other, self.atoms.len())
} else {
self.fo.atoms.len()
};
fn other_atoms(other: &fo::FirstOrder, total: usize) -> usize {
if other.is_empty() {
0
} else {
other.atoms.len()
}
.min(total)
}
let mut interner = fo::Interner::new();
let mut atoms = Vec::with_capacity(self.atoms.len());
let names = std::mem::take(&mut self.atoms);
let intern_symbol = |interner: &mut fo::Interner, name: &str, arity, predicate| {
let mut name = name.to_owned();
loop {
match interner.symbol(&name, arity, predicate) {
Ok(symbol) => return symbol,
Err(_) => name.push('_'),
}
}
};
let sides = [(&self.fo, 0, own_atoms), (&other, own_atoms, names.len())];
for (tables, from, to) in sides {
let mut predicate = vec![false; tables.symbols.len()];
for &(p, _) in &tables.atoms {
predicate[p.index()] = true;
}
let symbols: Vec<Symbol> = tables
.symbols
.iter()
.enumerate()
.map(|(i, (name, arity))| intern_symbol(&mut interner, name, *arity, predicate[i]))
.collect();
let mut terms: Vec<FoTermId> = Vec::with_capacity(tables.terms.len());
let mut lists: Vec<Option<Args>> = vec![None; tables.lists.len()];
for term in &tables.terms {
let term = match *term {
FoTerm::Bound(i) => FoTerm::Bound(i),
FoTerm::Eigen(a) => FoTerm::Eigen(a),
FoTerm::Meta(k) => FoTerm::Meta(k),
FoTerm::App(f, args) => FoTerm::App(
symbols[f.index()],
join_list(&mut interner, tables, &terms, &mut lists, args),
),
};
terms.push(interner.term(term));
}
for (a, name) in names[from..to].iter().enumerate() {
atoms.push(match tables.atoms.get(a) {
Some(&(p, args)) => (
symbols[p.index()],
join_list(&mut interner, tables, &terms, &mut lists, args),
),
None => (
intern_symbol(&mut interner, name, 0, true),
interner.list(&[]),
),
});
}
}
fn join_list(
interner: &mut fo::Interner,
tables: &fo::FirstOrder,
terms: &[FoTermId],
lists: &mut [Option<Args>],
args: Args,
) -> Args {
*lists[args.index()].get_or_insert_with(|| {
let items: Vec<FoTermId> =
tables.list(args).iter().map(|t| terms[t.index()]).collect();
interner.list(&items)
})
}
let mut fo = interner.tables;
fo.atoms = atoms;
fo.binders = std::mem::take(&mut self.fo.binders);
fo.binders.extend(
other
.binders
.into_iter()
.map(|(t, name)| (TermId::new(t.get() + terms_offset), name)),
);
self.atoms = fo
.atoms
.iter()
.map(|&(p, args)| fo.atom_key(p, args))
.collect();
self.fo = fo;
}
}
#[cfg(test)]
mod tests {
use super::*;
pub(crate) fn raw(terms: Vec<Term>, roots: &[u32], atoms: &[&str]) -> Sequent {
Sequent {
terms,
roots: roots.iter().map(|&n| TermId::new(n)).collect(),
atoms: atoms.iter().map(|s| s.to_string()).collect(),
antecedents: None,
cuts: vec![],
fo: fo::FirstOrder::new(),
}
}
pub(crate) const fn var(a: u32) -> Term {
Term::Atom(Atom::new(a))
}
pub(crate) const fn dual_var(a: u32) -> Term {
Term::DualAtom(Atom::new(a))
}
pub(crate) const fn tensor(k: u32, l: u32) -> Term {
Term::Tensor(TermId::new(k), TermId::new(l))
}
pub(crate) const fn bang(k: u32) -> Term {
Term::Bang(TermId::new(k))
}
#[test]
fn add_merges_atoms_by_name() {
let mut s = raw(vec![dual_var(0), var(1)], &[0, 1], &["A", "B"]);
s.add(raw(
vec![var(0), var(1), var(2)],
&[0, 1, 2],
&["C", "A", "B"],
));
assert_eq!(s.atoms, ["A", "B", "C"]);
assert_eq!(s.terms, [dual_var(0), var(1), var(2), var(0), var(1)]);
assert_eq!(s.roots.len(), 5);
}
#[test]
fn optimize_empty() {
let mut s = Sequent::new();
s.optimize();
assert!(s.terms.is_empty() && s.roots.is_empty() && s.atoms.is_empty());
}
#[test]
fn optimize_merges_atoms() {
let mut s = raw(
vec![var(0), dual_var(1), var(2)],
&[0, 1, 2],
&["A", "A", "B"],
);
s.optimize();
assert_eq!(s.atoms, ["A", "B"]);
assert_eq!(s.terms, [var(0), dual_var(0), var(1)]);
}
#[test]
fn optimize_numbers_atoms_as_the_terms_name_them() {
let mut s = raw(
vec![var(2), dual_var(0), var(2)],
&[0, 1, 2],
&["B", "C", "A"],
);
s.optimize();
assert_eq!(s.atoms, ["A", "B"]);
assert_eq!(s.terms, [var(0), dual_var(1)]);
assert_eq!(s.roots, [TermId::new(0), TermId::new(1), TermId::new(0)]);
}
#[test]
fn optimize_redirects_duplicates() {
use Term::*;
let mut s = raw(vec![Zero, One, Top, Top, tensor(1, 3)], &[2, 4], &[]);
s.optimize();
assert_eq!(s.terms, [One, Top, tensor(0, 1)]);
assert_eq!(s.roots, [TermId::new(1), TermId::new(2)]);
}
#[test]
fn subterm_order_error_names_both_terms() {
use Term::*;
let s = raw(vec![One, bang(2), Bot], &[1], &[]);
assert_eq!(
s.check().unwrap_err().to_string(),
"term 1 refers to term 2, but a subterm must come before the terms that use it"
);
}
#[test]
fn optimize_merges_equal_subterms() {
let mut s = raw(
vec![
var(0),
var(1),
tensor(0, 1),
bang(2),
var(0),
var(1),
tensor(4, 5),
bang(6),
],
&[3, 7],
&["A", "B"],
);
s.optimize();
assert_eq!(s.terms, [var(0), var(1), tensor(0, 1), bang(2)]);
assert_eq!(s.roots, [TermId::new(3), TermId::new(3)]);
}
#[test]
fn add_offsets_indices() {
let mut s = raw(vec![var(0)], &[0], &["A"]);
s.add(raw(vec![dual_var(0), bang(0)], &[1], &["B"]));
assert_eq!(s.terms, [var(0), dual_var(1), bang(1)]);
assert_eq!(s.roots, [TermId::new(0), TermId::new(2)]);
assert_eq!(s.atoms, ["A", "B"]);
}
}