#![deny(clippy::wildcard_enum_match_arm)]
pub mod ill;
pub mod instances;
pub mod reading;
pub(crate) mod set;
pub mod written;
pub use ill::{IllSequent, IllSyntax, InputOptions};
pub use instances::{FrameId, Instances};
pub use reading::{IllConnective, IllFormula, Reading, ShapeError, Side};
pub(crate) use set::OccSet;
pub use written::{ClassicalSequent, Written};
use crate::Error;
use crate::limits::{Limits, Refusal, Space};
use crate::linear::sequents::{Atom, Formula, Kind, Sequent, TermId};
use std::ops::Not;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct OccId(u32);
impl OccId {
pub const fn new(index: u32) -> Self {
Self(index)
}
pub const fn get(self) -> u32 {
self.0
}
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[repr(transparent)]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(
feature = "serialize",
derive(serde::Serialize, serde::Deserialize),
serde(transparent)
)]
pub struct Member(u32);
impl Member {
pub const fn new(raw: u32) -> Self {
Self(raw)
}
pub const fn get(self) -> u32 {
self.0
}
pub const fn index(self) -> usize {
self.0 as usize
}
pub fn occurrence(self, forest: &Forest) -> Option<OccId> {
(self.index() < forest.len()).then_some(OccId(self.0))
}
pub(crate) const fn occ(self) -> OccId {
OccId(self.0)
}
}
impl From<OccId> for Member {
fn from(o: OccId) -> Self {
Self(o.0)
}
}
const _: () = assert!(size_of::<Member>() == 4);
const NONE: u32 = u32::MAX;
#[repr(u8)]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Sign {
Atom,
Dual,
}
impl Not for Sign {
type Output = Self;
fn not(self) -> Self {
match self {
Sign::Atom => Sign::Dual,
Sign::Dual => Sign::Atom,
}
}
}
#[repr(u8)]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Polarity {
Positive,
Negative,
}
impl Not for Polarity {
type Output = Self;
fn not(self) -> Self {
match self {
Polarity::Positive => Polarity::Negative,
Polarity::Negative => Polarity::Positive,
}
}
}
impl Kind {
pub const fn sign(self) -> Option<Sign> {
match self {
Kind::Atom => Some(Sign::Atom),
Kind::DualAtom => Some(Sign::Dual),
Kind::One
| Kind::Bot
| Kind::Top
| Kind::Zero
| Kind::Tensor
| Kind::Par
| Kind::With
| Kind::Plus
| Kind::Bang
| Kind::Quest
| Kind::Forall
| Kind::Exists => None,
}
}
pub const fn polarity(self) -> Option<Polarity> {
use Kind::*;
match self {
Atom | DualAtom => None,
Tensor | One | Plus | Zero | Bang | Exists => Some(Polarity::Positive),
Par | Bot | With | Top | Quest | Forall => Some(Polarity::Negative),
}
}
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug)]
pub struct Forest {
sequent: Sequent,
roots: Box<[OccId]>,
cuts: Box<[OccId]>,
term: Box<[TermId]>,
kind: Box<[Kind]>,
parent: Box<[u32]>,
root: Box<[OccId]>,
size: Box<[u32]>,
depth: Box<[u32]>,
literals: Box<[OccId]>,
literal_start: Box<[u32]>,
}
impl Forest {
pub(crate) const MOST: u64 = NONE as u64 - 1;
pub(crate) fn held_bytes(&self) -> usize {
let sequent = &self.sequent;
size_of_val(&*self.roots)
+ size_of_val(&*self.cuts)
+ size_of_val(&*self.term)
+ size_of_val(&*self.kind)
+ size_of_val(&*self.parent)
+ size_of_val(&*self.root)
+ size_of_val(&*self.size)
+ size_of_val(&*self.depth)
+ size_of_val(&*self.literals)
+ size_of_val(&*self.literal_start)
+ sequent.terms.capacity() * size_of::<crate::linear::sequents::Term>()
+ sequent.roots.capacity() * size_of::<TermId>()
+ sequent
.atoms
.iter()
.map(|name| size_of::<String>() + name.capacity())
.sum::<usize>()
}
pub fn new(sequent: &Sequent) -> Result<Self, Error> {
Self::within(sequent, &Limits::default())
}
pub fn within(sequent: &Sequent, limits: &Limits) -> Result<Self, Error> {
let sizes = Self::measure(sequent, limits)?;
Ok(Self::build(sequent.clone(), &sizes))
}
pub fn from_owned(sequent: Sequent, limits: &Limits) -> Result<Self, Error> {
let sizes = Self::measure(&sequent, limits)?;
Ok(Self::build(sequent, &sizes))
}
fn measure(sequent: &Sequent, limits: &Limits) -> Result<Vec<u64>, Error> {
let sizes = sequent.sizes();
let occurrences = sequent.occurrences_of(&sizes);
if let Some(limit) = limits.occurrences
&& occurrences > limit
{
return Err(Error::Refused(Refusal::Occurrences { occurrences, limit }));
}
if occurrences > Self::MOST {
return Err(Error::Refused(Refusal::Index {
what: Space::Occurrence,
count: occurrences,
most: Self::MOST,
}));
}
Ok(sizes)
}
pub fn sequent(&self) -> &Sequent {
&self.sequent
}
pub fn len(&self) -> usize {
self.term.len()
}
pub fn is_empty(&self) -> bool {
self.term.is_empty()
}
pub fn ids(&self) -> impl DoubleEndedIterator<Item = OccId> + ExactSizeIterator {
(0..self.term.len() as u32).map(OccId::new)
}
#[cfg(any(feature = "latex", feature = "typst", feature = "svg"))]
pub(crate) fn root_members(&self) -> Vec<Member> {
self.roots().iter().copied().map(Member::from).collect()
}
pub fn roots(&self) -> &[OccId] {
&self.roots
}
pub fn cut_pairs(&self) -> impl ExactSizeIterator<Item = (OccId, OccId)> + '_ {
self.cuts
.iter()
.map(|&a| (a, OccId::new(a.get() + self.size(a))))
}
pub fn has_binders(&self) -> bool {
self.kind.iter().any(|k| k.is_binder())
}
pub fn has_cuts(&self) -> bool {
!self.cuts.is_empty()
}
pub fn is_conclusion(&self, o: OccId) -> bool {
self.cuts.first().is_none_or(|&first| self.root(o) < first)
}
pub fn dual(&self, o: OccId) -> Option<OccId> {
let root = self.root(o);
let at = self.cuts.partition_point(|&a| a <= root).checked_sub(1)?;
let a = self.cuts[at];
let size = self.size(a);
if root == a {
Some(OccId::new(o.get() + size))
} else if root.get() == a.get() + size {
Some(OccId::new(o.get() - size))
} else {
None
}
}
pub fn is_cut_formula(&self, o: OccId) -> bool {
self.dual(o).is_some_and(|d| o < d)
}
pub(crate) fn is_roots(&self, goal: &[OccId]) -> bool {
if goal.len() != self.roots.len() {
return false;
}
if *goal == *self.roots {
return true;
}
let mut sorted = goal.to_vec();
sorted.sort_unstable();
let mut roots = self.roots.to_vec();
roots.sort_unstable();
sorted == roots
}
pub fn term(&self, o: OccId) -> TermId {
self.term[o.index()]
}
pub fn kind(&self, o: OccId) -> Kind {
self.kind[o.index()]
}
pub fn formula(&self, o: OccId) -> Formula<'_> {
self.sequent.formula(self.term(o))
}
pub fn parent(&self, o: OccId) -> Option<OccId> {
match self.parent[o.index()] {
NONE => None,
p => Some(OccId::new(p)),
}
}
pub fn root(&self, o: OccId) -> OccId {
self.root[o.index()]
}
pub fn same_root(&self, x: OccId, y: OccId) -> bool {
self.root(x) == self.root(y)
}
pub fn size(&self, o: OccId) -> u32 {
self.size[o.index()]
}
pub fn depth(&self, o: OccId) -> u32 {
self.depth[o.index()]
}
pub fn is_literal(&self, o: OccId) -> bool {
self.kind(o).is_literal()
}
pub fn atom(&self, o: OccId) -> Option<Atom> {
self.sequent.term(self.term(o)).atom()
}
pub fn sign(&self, o: OccId) -> Option<Sign> {
self.kind(o).sign()
}
pub(crate) fn dual_literals(&self, x: OccId, y: OccId) -> bool {
self.is_literal(x) && self.atom(x) == self.atom(y) && self.sign(x) != self.sign(y)
}
pub fn left(&self, o: OccId) -> Option<OccId> {
(self.kind(o).arity() >= 1).then(|| OccId::new(o.0 + 1))
}
pub fn right(&self, o: OccId) -> Option<OccId> {
(self.kind(o).arity() == 2).then(|| {
let left = o.0 + 1;
OccId::new(left + self.size[left as usize])
})
}
pub fn children(&self, o: OccId) -> impl Iterator<Item = OccId> {
self.left(o).into_iter().chain(self.right(o))
}
pub fn subtree(&self, o: OccId) -> impl DoubleEndedIterator<Item = OccId> + ExactSizeIterator {
(o.0..o.0 + self.size(o)).map(OccId::new)
}
pub fn is_below(&self, o: OccId, ancestor: OccId) -> bool {
ancestor.0 <= o.0 && o.0 < ancestor.0 + self.size(ancestor)
}
#[inline]
pub fn lca(&self, x: OccId, y: OccId) -> Option<OccId> {
if !self.same_root(x, y) {
return None;
}
let mut a = x;
while !self.is_below(y, a) {
a = self.parent(a)?;
}
Some(a)
}
pub fn literals(&self, atom: Atom, sign: Sign) -> &[OccId] {
let group = Self::list(atom, sign);
let (start, end) = (self.literal_start[group], self.literal_start[group + 1]);
&self.literals[start as usize..end as usize]
}
pub(crate) const fn list(atom: Atom, sign: Sign) -> usize {
2 * atom.index() + sign as usize
}
pub(crate) fn lists(&self) -> usize {
2 * self.sequent.atom_names().len()
}
pub fn all_literals(&self) -> &[OccId] {
&self.literals
}
}
impl Forest {
fn build(sequent: Sequent, term_size: &[u64]) -> Self {
let terms = sequent.terms();
let n = sequent.occurrences_of(term_size) as usize;
let mut roots = Vec::with_capacity(sequent.roots().len());
let mut cuts = Vec::with_capacity(sequent.cuts().len());
let mut term = Vec::with_capacity(n);
let mut kind = Vec::with_capacity(n);
let mut parent = Vec::with_capacity(n);
let mut root = Vec::with_capacity(n);
let mut size = Vec::with_capacity(n);
let mut depth = Vec::with_capacity(n);
let mut stack: Vec<(TermId, u32, u32)> = Vec::new();
let conclusion = sequent.roots().len();
let trees = sequent
.roots()
.iter()
.chain(sequent.cuts().iter().flatten());
for (i, &r) in trees.enumerate() {
let root_id = OccId::new(term.len() as u32);
if i < conclusion {
roots.push(root_id);
} else if (i - conclusion).is_multiple_of(2) {
cuts.push(root_id);
}
stack.push((r, NONE, 0));
while let Some((t, p, d)) = stack.pop() {
let o = term.len() as u32;
let node = terms[t.index()];
term.push(t);
kind.push(node.kind());
parent.push(p);
root.push(root_id);
size.push(term_size[t.index()] as u32);
depth.push(d);
let subterms: Vec<TermId> = node.subterms().collect();
for &k in subterms.iter().rev() {
stack.push((k, o, d + 1));
}
}
}
debug_assert_eq!(term.len(), n);
let num_atoms = sequent.atom_names().len();
let mut literal_start = vec![0u32; 2 * num_atoms + 1];
for (o, k) in kind.iter().enumerate() {
if let Some(s) = k.sign() {
let a = terms[term[o].index()].atom().unwrap();
literal_start[Self::list(a, s) + 1] += 1;
}
}
for g in 1..literal_start.len() {
literal_start[g] += literal_start[g - 1];
}
let mut next = literal_start.clone();
let mut literals = vec![OccId::new(NONE); literal_start[2 * num_atoms] as usize];
for (o, k) in kind.iter().enumerate() {
if let Some(s) = k.sign() {
let a = terms[term[o].index()].atom().unwrap();
let group = Self::list(a, s);
literals[next[group] as usize] = OccId::new(o as u32);
next[group] += 1;
}
}
Self {
sequent,
roots: roots.into_boxed_slice(),
cuts: cuts.into_boxed_slice(),
term: term.into_boxed_slice(),
kind: kind.into_boxed_slice(),
parent: parent.into_boxed_slice(),
root: root.into_boxed_slice(),
size: size.into_boxed_slice(),
depth: depth.into_boxed_slice(),
literals: literals.into_boxed_slice(),
literal_start: literal_start.into_boxed_slice(),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::linear::sequents::Term;
const fn o(id: u32) -> OccId {
OccId::new(id)
}
#[cfg(feature = "parse")]
fn forest(input: &str) -> Forest {
let s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
Forest::new(&s).unwrap()
}
fn check_invariants(f: &Forest) {
let n = f.len() as u32;
assert_eq!(f.ids().count(), n as usize);
assert_eq!(
f.roots().iter().map(|&r| f.size(r)).sum::<u32>(),
n,
"the roots' subtrees partition the ids"
);
for (i, &r) in f.roots().iter().enumerate() {
let expected = f.roots()[..i].iter().map(|&q| f.size(q)).sum::<u32>();
assert_eq!(r, o(expected), "root {i} starts after the roots before it");
assert_eq!(f.parent(r), None);
assert_eq!(f.depth(r), 0);
assert_eq!(f.root(r), r);
assert_eq!(f.term(r), f.sequent().roots()[i]);
}
for x in f.ids() {
let node = f.sequent().term(f.term(x));
assert_eq!(f.kind(x), node.kind());
let children: Vec<OccId> = f.children(x).collect();
assert_eq!(children.len(), node.kind().arity() as usize);
assert_eq!(children.first().copied(), f.left(x));
assert_eq!(children.get(1).copied(), f.right(x));
let subterms: Vec<TermId> = node.subterms().collect();
for (&c, &t) in children.iter().zip(&subterms) {
assert_eq!(f.parent(c), Some(x), "the child's parent is the node");
assert_eq!(f.depth(c), f.depth(x) + 1);
assert_eq!(f.root(c), f.root(x));
assert_eq!(f.term(c), t, "children come in the term's order");
assert!(f.is_below(c, x));
}
assert_eq!(
f.size(x),
1 + children.iter().map(|&c| f.size(c)).sum::<u32>()
);
if let Some(l) = f.left(x) {
assert_eq!(l, o(x.get() + 1), "the left child follows its parent");
}
if let (Some(l), Some(r)) = (f.left(x), f.right(x)) {
assert_eq!(
r,
o(l.get() + f.size(l)),
"the right child follows the left subtree"
);
}
for y in f.ids() {
let mut a = Some(y);
while let Some(b) = a
&& b != x
{
a = f.parent(b);
}
assert_eq!(a == Some(x), f.is_below(y, x), "{y:?} below {x:?}");
assert_eq!(f.subtree(x).any(|z| z == y), f.is_below(y, x));
}
match f.parent(x) {
Some(p) => assert_eq!(f.depth(x), f.depth(p) + 1),
None => assert!(f.roots().contains(&x)),
}
assert_eq!(f.atom(x), node.atom());
assert_eq!(f.sign(x), node.kind().sign());
assert_eq!(f.is_literal(x), node.kind().is_literal());
}
let mut all: Vec<OccId> = Vec::new();
for a in 0..f.sequent().atom_names().len() {
let atom = Atom::new(a as u32);
for sign in [Sign::Atom, Sign::Dual] {
let list = f.literals(atom, sign);
assert!(list.windows(2).all(|w| w[0] < w[1]), "sorted");
for &l in list {
assert_eq!(f.atom(l), Some(atom));
assert_eq!(f.sign(l), Some(sign));
}
all.extend_from_slice(list);
}
}
assert_eq!(all, f.all_literals());
let mut literal_ids: Vec<OccId> = f.ids().filter(|&x| f.is_literal(x)).collect();
all.sort();
literal_ids.sort();
assert_eq!(all, literal_ids);
}
#[test]
fn empty() {
let f = Forest::new(&Sequent::new()).unwrap();
assert!(f.is_empty());
assert_eq!(f.len(), 0);
assert_eq!(f.roots(), []);
assert_eq!(f.all_literals(), []);
check_invariants(&f);
}
#[cfg(feature = "parse")]
#[test]
fn layout() {
let f = forest("A, A -o B |- B");
check_invariants(&f);
assert_eq!(f.len(), 5);
assert_eq!(f.roots(), [o(0), o(1), o(4)]);
let kinds: Vec<Kind> = f.ids().map(|x| f.kind(x)).collect();
use Kind::*;
assert_eq!(kinds, [DualAtom, Tensor, Atom, DualAtom, Atom]);
assert_eq!(f.formula(o(1)).to_string(), "A ⊗ ~B");
assert_eq!(f.left(o(1)), Some(o(2)));
assert_eq!(f.right(o(1)), Some(o(3)));
assert_eq!(f.subtree(o(1)).collect::<Vec<_>>(), [o(1), o(2), o(3)]);
assert_eq!(f.size(o(1)), 3);
assert_eq!(f.depth(o(3)), 1);
assert_eq!(f.root(o(3)), o(1));
assert!(f.same_root(o(2), o(3)));
assert!(!f.same_root(o(0), o(2)));
}
#[cfg(feature = "parse")]
#[test]
fn invariants_on_a_table() {
for input in [
"|- A",
"|- A, A",
"|- A * A",
"|- (A * B), (A * B)",
"|- !(A & B) + ?(A * B), 1, bot, top, 0",
"A -o B -o C, (A -o B) -o C |- (A * B) + (0 & top)",
"!A, ?B, A * B, C par D |- ~A, B^, A & B, C + D",
"|- ((A * B) * (A * B)) * ((A * B) * (A * B))",
] {
check_invariants(&forest(input));
}
}
#[cfg(feature = "parse")]
#[test]
fn lowest_common_ancestor() {
let f = forest("|- (A * B) par (C * D), E");
check_invariants(&f);
assert_eq!(f.lca(o(2), o(3)), Some(o(1)));
assert_eq!(f.lca(o(2), o(5)), Some(o(0)));
assert_eq!(f.lca(o(3), o(6)), Some(o(0)));
assert_eq!(f.lca(o(1), o(4)), Some(o(0)));
assert_eq!(f.lca(o(0), o(6)), Some(o(0)));
assert_eq!(f.lca(o(6), o(0)), Some(o(0)));
assert_eq!(f.lca(o(5), o(5)), Some(o(5)));
assert_eq!(f.lca(o(2), o(7)), None);
assert_eq!(f.lca(o(7), o(7)), Some(o(7)));
}
#[cfg(feature = "parse")]
#[test]
fn literals() {
let f = forest("A, A |- A, B, C -o C, C -o C");
check_invariants(&f);
let s = f.sequent();
let (a, b, c) = (
s.atom("A").unwrap(),
s.atom("B").unwrap(),
s.atom("C").unwrap(),
);
assert_eq!(f.literals(a, Sign::Atom), [o(2)]);
assert_eq!(f.literals(a, Sign::Dual), [o(0), o(1)]);
assert_eq!(f.literals(b, Sign::Atom), [o(3)]);
assert_eq!(f.literals(b, Sign::Dual), []);
assert_eq!(f.literals(c, Sign::Atom), [o(6), o(9)]);
assert_eq!(f.literals(c, Sign::Dual), [o(5), o(8)]);
}
#[cfg(feature = "parse")]
#[test]
fn connective_polarities() {
let f = forest("|- (A * B) par (A & B) + (!A par ?B), 1, bot, top, 0");
check_invariants(&f);
let by_kind = |k: Kind| {
f.ids()
.filter(|&x| f.kind(x) == k)
.map(|x| f.kind(x).polarity().unwrap())
.collect::<Vec<_>>()
};
use Kind::*;
use Polarity::*;
for (k, p) in [
(Tensor, Positive),
(Plus, Positive),
(One, Positive),
(Zero, Positive),
(Bang, Positive),
(Par, Negative),
(With, Negative),
(Bot, Negative),
(Top, Negative),
(Quest, Negative),
] {
assert!(!by_kind(k).is_empty(), "{k:?} occurs");
assert!(by_kind(k).iter().all(|&q| q == p), "{k:?} is {p:?}");
}
}
#[test]
fn sharing() {
let s = Sequent {
terms: vec![
Term::Atom(Atom::new(0)),
Term::Tensor(TermId::new(0), TermId::new(0)),
],
roots: vec![TermId::new(1), TermId::new(0), TermId::new(1)],
atoms: vec!["A".into()],
antecedents: None,
cuts: vec![],
fo: Default::default(),
};
let f = Forest::new(&s).unwrap();
check_invariants(&f);
assert_eq!(f.len(), 7);
assert_eq!(f.roots(), [o(0), o(3), o(4)]);
assert_eq!(
f.literals(Atom::new(0), Sign::Atom),
[o(1), o(2), o(3), o(5), o(6)]
);
assert_eq!(s.occurrences(), 7);
let limit = |n| Limits::default().with_occurrences(n);
assert_eq!(Forest::within(&s, &limit(Some(7))).unwrap().len(), 7);
assert!(matches!(
Forest::within(&s, &limit(Some(6))),
Err(Error::Refused(Refusal::Occurrences {
occurrences: 7,
limit: 6
}))
));
let s = doubling(40);
assert_eq!(s.occurrences(), (1 << 41) - 1);
assert!(matches!(
Forest::within(&s, &limit(None)),
Err(Error::Refused(Refusal::Index { what: Space::Occurrence, count, most }))
if count == (1 << 41) - 1 && most == (1 << 32) - 2
));
assert_eq!(doubling(100).occurrences(), u64::MAX, "the count saturates");
}
fn doubling(levels: u32) -> Sequent {
let mut terms = vec![Term::One];
for k in 0..levels {
terms.push(Term::Tensor(TermId::new(k), TermId::new(k)));
}
Sequent {
terms,
roots: vec![TermId::new(levels)],
atoms: vec![],
antecedents: None,
cuts: vec![],
fo: Default::default(),
}
}
#[test]
fn refuses_an_unfolding_past_the_default_limit() {
let s = doubling(26);
let refused = |result: Result<Forest, Error>| {
matches!(
result,
Err(Error::Refused(crate::limits::Refusal::Occurrences { occurrences, limit }))
if occurrences == (1 << 27) - 1 && limit == Limits::DEFAULT_OCCURRENCES
)
};
let start = std::time::Instant::now();
assert!(refused(Forest::new(&s)));
assert!(refused(Forest::from_owned(s, &Limits::default())));
assert!(start.elapsed() < std::time::Duration::from_secs(1));
}
}