pub mod check;
pub mod cut;
pub mod derivation;
#[cfg(all(test, feature = "parse"))]
mod first_order;
pub(crate) mod fmt;
#[cfg(feature = "interactive")]
pub mod interactive;
mod multiset;
#[cfg(all(test, feature = "parse"))]
mod oracle;
mod rule;
pub mod size;
pub mod style;
use crate::linear::occurrences::{Instances, instances};
pub use check::{CheckError, Dyadic, Fault, Invalid, Refused};
pub use derivation::{
ClassicalRule, ClassicalSides, Compact, Derivation, InfId, Inference, Layout, Sides,
Structural, TwoSided, ViewOptions,
};
pub use fmt::TextOptions;
#[cfg(feature = "interactive")]
pub use interactive::{CutFormula, GoalId, Interactive, Step, StepError};
pub use rule::{Division, Named, Rule};
pub use size::Size;
pub use style::{Labels, OpenGoal};
use crate::Error;
use crate::limits::{Limits, Progress};
use crate::linear::fragment::Mode;
use crate::linear::occurrences::{Forest, Member, OccId, Reading};
use crate::linear::sequents::{Eigen, FoTermId, Sequent};
use std::fmt::{Display, Formatter, Result as FmtResult};
pub(crate) struct Bytes(pub(crate) u64);
impl std::fmt::Display for Bytes {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let units = [(30, "GiB"), (20, "MiB"), (10, "KiB")];
match units
.into_iter()
.find(|&(shift, _)| self.0 != 0 && self.0.is_multiple_of(1 << shift))
{
Some((shift, unit)) => write!(f, "{} {unit}", self.0 >> shift),
None => write!(f, "{} B", self.0),
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct NodeId(u32);
impl NodeId {
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(u8)]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Branch {
Left,
Right,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Node {
Ax(Member, Member),
Tensor(Member, NodeId, NodeId),
Par(Member, NodeId),
One(Member),
Bot(Member, NodeId),
With(Member, NodeId, NodeId),
Plus(Member, Branch, NodeId),
Top(Member),
Bang(Member, NodeId),
Quest(Member, NodeId),
Copy(Member, NodeId),
Weaken(Member, NodeId),
Mix(NodeId, NodeId),
Cut(Member, NodeId, NodeId),
Forall(Member, Eigen, NodeId),
Exists(Member, FoTermId, NodeId),
}
const _: () = assert!(size_of::<Node>() == 16);
const BUILD_POLL: usize = 1 << 16;
impl Node {
pub const NAMES: &'static [&'static str] = &[
"Ax", "Tensor", "Par", "One", "Bot", "With", "Plus", "Top", "Bang", "Quest", "Copy",
"Weaken", "Mix", "Cut", "Forall", "Exists",
];
pub const TAGS: &'static [&'static str] = &[
"ax", "⊗", "⅋", "1", "⊥", "&", "⊕₁", "⊕₂", "⊤", "!", "?", "copy", "wk", "mix", "cut", "∀",
"∃",
];
pub const fn principal(self) -> Option<Member> {
use Node::*;
match self {
Ax(o, _)
| Tensor(o, ..)
| Par(o, _)
| One(o)
| Bot(o, _)
| With(o, ..)
| Plus(o, ..)
| Top(o)
| Bang(o, _)
| Quest(o, _)
| Copy(o, _)
| Weaken(o, _)
| Forall(o, ..)
| Exists(o, ..) => Some(o),
Mix(..) | Cut(..) => None,
}
}
pub fn members(self) -> impl Iterator<Item = Member> {
use Node::*;
let second = match self {
Ax(_, b) | Cut(b, ..) => Some(b),
Tensor(..) | Par(..) | One(_) | Bot(..) | With(..) | Plus(..) | Top(_) | Bang(..)
| Quest(..) | Copy(..) | Weaken(..) | Mix(..) | Forall(..) | Exists(..) => None,
};
self.principal().into_iter().chain(second)
}
pub(crate) fn renamed<E>(
self,
rename: impl Fn(Member) -> Result<Member, E>,
) -> Result<Self, E> {
use Node::*;
Ok(match self {
Ax(a, b) => Ax(rename(a)?, rename(b)?),
Tensor(o, l, r) => Tensor(rename(o)?, l, r),
Par(o, p) => Par(rename(o)?, p),
One(o) => One(rename(o)?),
Bot(o, p) => Bot(rename(o)?, p),
With(o, l, r) => With(rename(o)?, l, r),
Plus(o, b, p) => Plus(rename(o)?, b, p),
Top(o) => Top(rename(o)?),
Bang(o, p) => Bang(rename(o)?, p),
Quest(o, p) => Quest(rename(o)?, p),
Copy(o, p) => Copy(rename(o)?, p),
Weaken(o, p) => Weaken(rename(o)?, p),
Mix(l, r) => Mix(l, r),
Cut(a, l, r) => Cut(rename(a)?, l, r),
Forall(o, a, p) => Forall(rename(o)?, a, p),
Exists(o, w, p) => Exists(rename(o)?, w, p),
})
}
pub fn premises(self) -> impl Iterator<Item = NodeId> {
use Node::*;
let (first, second) = match self {
Ax(..) | One(_) | Top(_) => (None, None),
Tensor(_, l, r) | With(_, l, r) | Mix(l, r) | Cut(_, l, r) => (Some(l), Some(r)),
Par(_, p)
| Bot(_, p)
| Plus(_, _, p)
| Bang(_, p)
| Quest(_, p)
| Copy(_, p)
| Weaken(_, p)
| Forall(_, _, p)
| Exists(_, _, p) => (Some(p), None),
};
first.into_iter().chain(second)
}
pub const fn name(self) -> &'static str {
use Node::*;
match self {
Ax(..) => "ax",
Tensor(..) => "⊗",
Par(..) => "⅋",
One(_) => "1",
Bot(..) => "⊥",
With(..) => "&",
Plus(_, Branch::Left, _) => "⊕₁",
Plus(_, Branch::Right, _) => "⊕₂",
Top(_) => "⊤",
Bang(..) => "!",
Quest(..) => "?",
Copy(..) => "copy",
Weaken(..) => "wk",
Mix(..) => "mix",
Cut(..) => "cut",
Forall(..) => "∀",
Exists(..) => "∃",
}
}
}
impl Display for Node {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
f.write_str(self.name())?;
let mut occurrences = self.members().map(Member::get);
if let Some(o) = occurrences.next() {
write!(f, " on {o}")?;
for o in occurrences {
write!(f, ", {o}")?;
}
}
let mut premises = self.premises().map(|p| p.get());
if let Some(p) = premises.next() {
write!(f, " from {p}")?;
for p in premises {
write!(f, ", {p}")?;
}
}
Ok(())
}
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug)]
pub struct Proof {
forest: Forest,
nodes: Box<[Node]>,
goal: Option<Box<[Member]>>,
mode: Option<Mode>,
instances: Option<Box<Instances>>,
}
impl Proof {
pub fn new(forest: Forest, nodes: Vec<Node>, root: NodeId) -> Result<Self, Error> {
if forest.has_binders() {
let instances = Instances::new(&forest);
return Self::with_instances(forest, instances, nodes, root);
}
Self::build(forest, nodes, root, &mut || false)
}
pub fn with_instances(
forest: Forest,
instances: Instances,
nodes: Vec<Node>,
root: NodeId,
) -> Result<Self, Error> {
let members = (forest.len() as u64).saturating_add(instances.len() as u64);
let mut proof = Self::reach(forest, nodes, root, members, &mut || false)?;
let mut nodes = std::mem::take(&mut proof.nodes).into_vec();
let table = instances::canonical(&proof.forest, &instances, &mut nodes)?;
proof.nodes = nodes.into_boxed_slice();
proof.instances = (proof.forest.has_binders() || table != Instances::new(&proof.forest))
.then(|| Box::new(table));
Ok(proof)
}
pub fn instances(&self) -> Option<&Instances> {
self.instances.as_deref()
}
pub(crate) fn build(
forest: Forest,
nodes: Vec<Node>,
root: NodeId,
stopped: &mut dyn FnMut() -> bool,
) -> Result<Self, Error> {
let members = forest.len() as u64;
Self::reach(forest, nodes, root, members, stopped)
}
fn reach(
forest: Forest,
mut nodes: Vec<Node>,
root: NodeId,
members: u64,
stopped: &mut dyn FnMut() -> bool,
) -> Result<Self, Error> {
const UNREACHED: u32 = u32::MAX;
let stop = || {
Error::Refused(crate::limits::Refusal::Stopped {
phase: crate::limits::Phase::Search,
})
};
if root.index() >= nodes.len() {
return Err(Error::IndexOutOfBounds {
space: crate::limits::Space::Node,
index: root.index(),
len: nodes.len(),
});
}
let mut index = vec![UNREACHED; root.index() + 1];
index[root.index()] = 0;
for i in (0..=root.index()).rev() {
if i % BUILD_POLL == 0 && stopped() {
return Err(stop());
}
if index[i] == UNREACHED {
continue;
}
for o in nodes[i].members() {
if u64::from(o.get()) >= members {
return Err(Error::IndexOutOfBounds {
space: crate::limits::Space::Occurrence,
index: o.index(),
len: usize::try_from(members).unwrap_or(usize::MAX),
});
}
}
for p in nodes[i].premises() {
if p.index() >= i {
return Err(Error::NotTopological {
space: crate::limits::Space::Node,
index: p.index(),
parent: i,
});
}
index[p.index()] = 0;
}
}
let reached = index.iter().filter(|&&i| i != UNREACHED).count();
if u32::try_from(reached).is_err() {
return Err(Error::Refused(crate::limits::Refusal::Index {
what: crate::limits::Space::Node,
count: reached as u64,
most: u64::from(u32::MAX),
}));
}
let mut kept = 0;
for i in 0..=root.index() {
if i % BUILD_POLL == 0 && stopped() {
return Err(stop());
}
if index[i] == UNREACHED {
continue;
}
index[i] = kept as u32;
nodes[kept] = nodes[i].map_premises(|p| NodeId::new(index[p.index()]));
kept += 1;
}
nodes.truncate(kept);
Ok(Self {
forest,
nodes: nodes.into_boxed_slice(),
goal: None,
mode: None,
instances: None,
})
}
pub fn new_of_goal(
forest: Forest,
goal: &[Member],
nodes: Vec<Node>,
root: NodeId,
) -> Result<Self, Error> {
if let Some(m) = goal.iter().find(|m| m.occurrence(&forest).is_none()) {
return Err(Error::IndexOutOfBounds {
space: crate::limits::Space::Member,
index: m.index(),
len: forest.len(),
});
}
let occurrences: Vec<OccId> = goal.iter().map(|m| m.occ()).collect();
let roots = forest.is_roots(&occurrences);
let mut proof = Self::new(forest, nodes, root)?;
proof.goal = (!roots).then(|| goal.into());
Ok(proof)
}
#[must_use]
pub fn with_mode(self, mode: Mode) -> Self {
Self {
mode: Some(mode),
..self
}
}
pub fn goal(&self) -> Option<&[Member]> {
self.goal.as_deref()
}
pub fn mode(&self) -> Option<Mode> {
self.mode
}
pub fn occurrence(&self, member: Member) -> OccId {
match self.instances.as_deref().and_then(|t| t.instance(member)) {
Some((o, _)) => o,
None => member.occ(),
}
}
pub fn formula(&self, member: Member) -> impl Display + '_ {
let reading = self
.mode
.filter(|mode| mode.is_intuitionistic())
.and_then(|mode| Reading::of_mode(&self.forest, mode.with_empty_antecedents()).ok());
if let Some(table) = self.instances.as_deref()
&& member.index() >= self.forest.len()
{
let framing = instances::Framing::new(&self.forest.sequent().fo, table);
let mut text = String::new();
crate::linear::sequents::notation::TEXT
.instance(
&mut text,
&self.forest,
reading.as_ref(),
&framing,
member,
Some(crate::errors::describe::TERM),
)
.expect("writing into a string cannot fail");
return text;
}
match reading {
Some(reading) => reading.formula(member.occ()).to_string(),
None => self.forest.formula(member.occ()).to_string(),
}
}
pub(crate) fn concluding(self, goal: &[OccId]) -> Self {
Self {
goal: Some(goal.iter().copied().map(Member::from).collect()),
..self
}
}
pub fn onto(&self, forest: Forest, goal: &[Member]) -> Result<Self, Error> {
if let Some(m) = goal.iter().find(|m| m.occurrence(&forest).is_none()) {
return Err(Error::IndexOutOfBounds {
space: crate::limits::Space::Member,
index: m.index(),
len: forest.len(),
});
}
let from = &self.forest;
let name = |f: &Forest, o: OccId| f.atom(o).map(|a| f.sequent().atom_name(a).to_owned());
let alike = |o: OccId, t: OccId| {
from.size(o) == forest.size(t)
&& from.subtree(o).zip(forest.subtree(t)).all(|(a, b)| {
from.kind(a) == forest.kind(b) && name(from, a) == name(&forest, b)
})
};
let mut free: crate::hash::HashMap<String, std::collections::VecDeque<usize>> =
crate::hash::HashMap::default();
for (i, m) in goal.iter().enumerate() {
free.entry(forest.formula(m.occ()).to_string())
.or_default()
.push_back(i);
}
let mut taken = vec![false; goal.len()];
let mut place: Vec<Option<OccId>> = vec![None; from.len()];
let mut only_proof = Vec::new();
for c in self.conclusion() {
let written = from.formula(c).to_string();
let found = free.get_mut(&written).and_then(|bucket| {
let at = bucket.iter().position(|&i| alike(c, goal[i].occ()))?;
bucket.remove(at)
});
match found {
Some(i) => {
taken[i] = true;
for (o, t) in from.subtree(c).zip(forest.subtree(goal[i].occ())) {
place[o.index()] = Some(t);
}
}
None => only_proof.push(c),
}
}
let only_goal: Vec<OccId> = goal
.iter()
.zip(&taken)
.filter(|&(_, &t)| !t)
.map(|(m, _)| m.occ())
.collect();
if !only_proof.is_empty() || !only_goal.is_empty() {
let written = |f: &Forest, os: Vec<OccId>| -> Vec<String> {
let reading = self
.mode
.filter(|mode| mode.is_intuitionistic())
.and_then(|mode| Reading::of_mode(f, mode.with_empty_antecedents()).ok());
os.into_iter()
.map(|o| match &reading {
Some(reading) => reading.formula(o).to_string(),
None => f.formula(o).to_string(),
})
.collect()
};
return Err(Error::SequentMismatch {
proof: written(from, only_proof),
goal: written(&forest, only_goal),
});
}
let rename = |m: Member| {
place
.get(m.index())
.copied()
.flatten()
.map(Member::from)
.ok_or(Error::IndexOutOfBounds {
space: crate::limits::Space::Member,
index: m.index(),
len: from.len(),
})
};
let nodes = self
.nodes
.iter()
.map(|node| node.renamed(rename))
.collect::<Result<Vec<_>, _>>()?;
let mut carried = Self::new_of_goal(forest, goal, nodes, self.root())?;
carried.mode = self.mode;
Ok(carried)
}
pub(crate) fn conclusion(&self) -> Vec<OccId> {
match &self.goal {
Some(goal) => goal.iter().map(|m| m.occ()).collect(),
None => self.forest.roots().to_vec(),
}
}
pub fn forest(&self) -> &Forest {
&self.forest
}
pub fn sequent(&self) -> &Sequent {
self.forest.sequent()
}
pub fn is_cut_free(&self) -> bool {
!self.nodes.iter().any(|node| matches!(node, Node::Cut(..)))
}
pub fn nodes(&self) -> &[Node] {
&self.nodes
}
pub fn node(&self, id: NodeId) -> Node {
self.nodes[id.index()]
}
pub fn ids(&self) -> impl DoubleEndedIterator<Item = NodeId> + ExactSizeIterator {
(0..self.nodes.len() as u32).map(NodeId::new)
}
pub fn root(&self) -> NodeId {
NodeId::new(self.nodes.len() as u32 - 1)
}
pub fn check(&self, mode: Mode) -> Result<(), CheckError> {
check::check(self, mode)
}
pub fn check_within(
&self,
mode: Mode,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<(), CheckError> {
check::check_within(self, mode, limits, &mut stop)
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
pub fn derivation(&self) -> Result<Derivation<'_>, Error> {
self.derivation_within(&ViewOptions::default(), &Limits::default(), |_| false)
}
pub fn derivation_within(
&self,
view: &ViewOptions,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Derivation<'_>, Error> {
if view.two_sided(self) {
Derivation::two_sided(self, view, limits, stop)
} else {
Derivation::new(self, view, limits, stop)
}
}
#[cfg(all(test, feature = "parse"))]
pub(crate) fn two_sided(&self) -> Result<Derivation<'_>, Error> {
let view = ViewOptions::default().with_sides(Sides::Two);
self.derivation_within(&view, &Limits::default(), |_| false)
}
}
impl Node {
pub(crate) fn map_premises(self, mut f: impl FnMut(NodeId) -> NodeId) -> Self {
use Node::*;
match self {
Tensor(o, l, r) => Tensor(o, f(l), f(r)),
Par(o, p) => Par(o, f(p)),
Bot(o, p) => Bot(o, f(p)),
With(o, l, r) => With(o, f(l), f(r)),
Plus(o, s, p) => Plus(o, s, f(p)),
Bang(o, p) => Bang(o, f(p)),
Quest(o, p) => Quest(o, f(p)),
Copy(o, p) => Copy(o, f(p)),
Weaken(o, p) => Weaken(o, f(p)),
Mix(l, r) => Mix(f(l), f(r)),
Cut(o, l, r) => Cut(o, f(l), f(r)),
Forall(o, a, p) => Forall(o, a, f(p)),
Exists(o, w, p) => Exists(o, w, f(p)),
leaf @ (Ax(..) | One(_) | Top(_)) => leaf,
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn name_lists_follow_the_variants() {
let (m, n) = (Member::new(0), NodeId::new(0));
let nodes = [
Node::Ax(m, m),
Node::Tensor(m, n, n),
Node::Par(m, n),
Node::One(m),
Node::Bot(m, n),
Node::With(m, n, n),
Node::Plus(m, Branch::Left, n),
Node::Top(m),
Node::Bang(m, n),
Node::Quest(m, n),
Node::Copy(m, n),
Node::Weaken(m, n),
Node::Mix(n, n),
Node::Cut(m, n, n),
Node::Forall(m, Eigen::new(0), n),
Node::Exists(m, FoTermId::new(0), n),
];
let names: Vec<String> = nodes
.iter()
.map(|node| format!("{node:?}").split('(').next().unwrap().to_owned())
.collect();
assert_eq!(names, Node::NAMES);
let mut tags: Vec<&str> = nodes.iter().map(|node| node.name()).collect();
tags.insert(7, Node::Plus(m, Branch::Right, n).name());
assert_eq!(tags, Node::TAGS);
}
#[cfg(feature = "parse")]
#[test]
fn a_goal_is_a_sequent_of_its_mode() {
let sequent: Sequent = "0 |- a".parse().unwrap();
let top = Member::new(0);
let forest = Forest::new(&sequent).unwrap();
let proof = Proof::new_of_goal(forest, &[top], vec![Node::Top(top)], NodeId::new(0));
let proof = proof.unwrap();
assert_eq!(proof.check(Mode::CLASSICAL), Ok(()));
let Err(CheckError::Invalid(invalid)) = proof.check(Mode::INTUITIONISTIC) else {
panic!("a goal without an output is no intuitionistic sequent");
};
assert_eq!(invalid.fault, Fault::Succedents { count: 0 });
let sequent: Sequent = "A |- A".parse().unwrap();
let (a, b) = (Member::new(0), Member::new(1));
let forest = Forest::new(&sequent).unwrap();
let swapped = Proof::new_of_goal(forest, &[b, a], vec![Node::Ax(a, b)], NodeId::new(0));
assert_eq!(swapped.unwrap().goal(), None);
}
}