use crate::Error;
use crate::hash::{HashMap, HashSet};
use crate::limits::{Limits, Phase, Progress, Refusal};
use crate::linear::fragment::Mode;
use crate::linear::occurrences::{Forest, Member, OccId, Reading, Side};
use crate::linear::proofs::check::{self, Allowance, CheckError, Facts, Observer, State};
use crate::linear::proofs::multiset::Multiset;
use crate::linear::proofs::{Branch, Node, NodeId, Proof};
use crate::linear::sequents::{Eigen, FoTermId};
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(
feature = "serialize",
derive(serde::Serialize, serde::Deserialize),
serde(default, deny_unknown_fields)
)]
pub struct Options {
pub strategy: Strategy,
#[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
pub steps: Option<u64>,
#[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
pub nodes: Option<u64>,
#[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
pub drawn_bytes: Option<u64>,
}
impl Options {
pub const DEFAULT_STEPS: u64 = 10_000;
pub const DEFAULT_NODES: u64 = 100_000;
pub const DEFAULT_DRAWN_BYTES: u64 = 256 << 20;
#[must_use]
pub const fn with_strategy(self, strategy: Strategy) -> Self {
Self { strategy, ..self }
}
#[must_use]
pub const fn with_steps(self, steps: Option<u64>) -> Self {
Self { steps, ..self }
}
#[must_use]
pub const fn with_nodes(self, nodes: Option<u64>) -> Self {
Self { nodes, ..self }
}
#[must_use]
pub const fn with_drawn_bytes(self, drawn_bytes: Option<u64>) -> Self {
Self {
drawn_bytes,
..self
}
}
}
impl Default for Options {
fn default() -> Self {
Self {
strategy: Strategy::default(),
steps: Some(Self::DEFAULT_STEPS),
nodes: Some(Self::DEFAULT_NODES),
drawn_bytes: Some(Self::DEFAULT_DRAWN_BYTES),
}
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[cfg_attr(
feature = "serialize",
derive(serde::Serialize, serde::Deserialize),
serde(rename_all = "snake_case")
)]
pub enum Strategy {
#[default]
Topmost,
}
impl Strategy {
pub fn pick(self, proof: &Proof) -> Option<NodeId> {
match self {
Self::Topmost => proof
.ids()
.find(|&id| matches!(proof.node(id), Node::Cut(..))),
}
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(
feature = "serialize",
derive(serde::Serialize, serde::Deserialize),
serde(rename_all = "snake_case")
)]
pub enum Case {
Axiom,
TensorPar,
OneBot,
WithPlus,
Weakening,
Dereliction,
Contraction,
BoxIntoBox,
ForallExists,
Commutative,
}
impl Case {
pub const ALL: &'static [Self] = &[
Self::Axiom,
Self::TensorPar,
Self::OneBot,
Self::WithPlus,
Self::Weakening,
Self::Dereliction,
Self::Contraction,
Self::BoxIntoBox,
Self::ForallExists,
Self::Commutative,
];
pub const fn name(self) -> &'static str {
match self {
Self::Axiom => "the axiom case",
Self::TensorPar => "the key case of ⊗ and ⅋",
Self::OneBot => "the key case of 1 and ⊥",
Self::WithPlus => "the key case of & and ⊕",
Self::Weakening => "weakening",
Self::Dereliction => "dereliction",
Self::Contraction => "contraction",
Self::BoxIntoBox => "a box entering a box",
Self::ForallExists => "the key case of ∀ and ∃",
Self::Commutative => "a commutative case",
}
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Step {
pub cut: NodeId,
pub formula: Member,
pub case: Case,
pub above: Option<NodeId>,
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Reduction {
pub proof: Proof,
pub step: Step,
}
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum End {
CutFree,
Refused(Refusal),
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Elimination {
pub proof: Proof,
pub steps: Vec<Step>,
pub end: End,
}
pub fn step(
proof: &Proof,
mode: Mode,
at: Option<NodeId>,
options: &Options,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Reduction, Error> {
let record = Record::of(proof, mode, limits, &mut stop).map_err(Error::Check)?;
let cut = match at {
Some(at) if matches!(proof.nodes().get(at.index()), Some(Node::Cut(..))) => at,
Some(at) => {
return Err(Error::NoCut {
node: Some(at.get()),
});
}
None => options
.strategy
.pick(proof)
.ok_or(Error::NoCut { node: None })?,
};
let (made, step) =
reduce(proof, &record, mode, cut, options, limits, &mut stop).map_err(Error::Refused)?;
let reading = check::reading(&made, mode).map_err(Error::Check)?;
let allowance = Allowance::new(limits, Phase::Eliminate, &mut stop);
match check::examine(
&made,
&made.conclusion(),
mode,
reading.as_ref(),
allowance,
&mut (),
) {
Ok(()) => Ok(Reduction { proof: made, step }),
Err(refused @ CheckError::Refused(_)) => Err(Error::Check(refused)),
Err(invalid) => Err(Error::Reduction(Box::new(invalid))),
}
}
pub fn eliminate(
proof: &Proof,
mode: Mode,
at: Option<NodeId>,
options: &Options,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
mut each: impl FnMut(&Proof, &Step),
) -> Result<Elimination, Error> {
let mut steps: Vec<Step> = Vec::new();
let mut current = proof.clone();
let mut checked: Option<Proof> = None;
loop {
let ended = |proof: Proof, steps: Vec<Step>, refusal: Refusal| Elimination {
proof,
steps,
end: End::Refused(refusal),
};
let record = match Record::of(¤t, mode, limits, &mut stop) {
Ok(record) => record,
Err(CheckError::Refused(refused)) => {
let Some(checked) = checked else {
return Err(Error::Check(CheckError::Refused(refused)));
};
steps.pop();
return Ok(ended(checked, steps, refused.refusal));
}
Err(invalid) if checked.is_none() => return Err(Error::Check(invalid)),
Err(invalid) => return Err(Error::Reduction(Box::new(invalid))),
};
if let (Some(before), Some(last)) = (&checked, steps.last()) {
each(before, last);
}
let cut = match at.filter(|_| steps.is_empty()) {
Some(at) if matches!(current.nodes().get(at.index()), Some(Node::Cut(..))) => Some(at),
Some(at) => {
return Err(Error::NoCut {
node: Some(at.get()),
});
}
None => options.strategy.pick(¤t),
};
let Some(cut) = cut else {
return Ok(Elimination {
proof: current,
steps,
end: End::CutFree,
});
};
if let Some(limit) = options.steps
&& steps.len() as u64 >= limit
{
let refusal = Refusal::Elimination {
what: crate::limits::Bound::Steps,
limit,
};
return Ok(ended(current, steps, refusal));
}
if stop(Progress::new(Phase::Eliminate, 1, steps.len() as u64)) {
let refusal = Refusal::Stopped {
phase: Phase::Eliminate,
};
return Ok(ended(current, steps, refusal));
}
match reduce(¤t, &record, mode, cut, options, limits, &mut stop) {
Ok((made, step)) => {
steps.push(step);
checked = Some(std::mem::replace(&mut current, made));
}
Err(refusal) => return Ok(ended(current, steps, refusal)),
}
}
}
struct Record {
absorbs: Vec<bool>,
kept: Vec<bool>,
zones: HashMap<NodeId, Multiset<Member>>,
held: u64,
}
impl Record {
const ENTRY: u64 = 96;
fn of(
proof: &Proof,
mode: Mode,
limits: &Limits,
stop: &mut dyn FnMut(Progress) -> bool,
) -> Result<Self, CheckError> {
let len = proof.nodes().len();
let mut kept = vec![false; len];
for id in proof.ids() {
if let node @ (Node::Tensor(..) | Node::Mix(..) | Node::Cut(..)) = proof.node(id) {
for p in node.premises() {
kept[p.index()] = true;
}
}
}
let mut record = Self {
absorbs: vec![false; len],
kept,
zones: HashMap::default(),
held: 0,
};
let reading = check::reading(proof, mode)?;
check::examine(
proof,
&proof.conclusion(),
mode,
reading.as_ref(),
Allowance::new(limits, Phase::Eliminate, stop),
&mut record,
)?;
Ok(record)
}
fn zone(&self, id: NodeId) -> &Multiset<Member> {
&self.zones[&id]
}
}
impl Observer for Record {
fn bytes(&self) -> u64 {
self.held.saturating_add(self.kept.len() as u64 * 2)
}
fn derived(&mut self, id: NodeId, state: &State, _: &Facts<'_>) {
self.absorbs[id.index()] = state.absorbs();
if self.kept[id.index()] {
let zone = Multiset::of(
state
.linear()
.flat_map(|(m, n)| std::iter::repeat_n(m, n as usize)),
);
let bytes = (zone.as_slice().len() as u64).saturating_mul(4);
self.held = self.held.saturating_add(Self::ENTRY).saturating_add(bytes);
self.zones.insert(id, zone);
}
}
}
fn reduce(
proof: &Proof,
record: &Record,
mode: Mode,
cut: NodeId,
options: &Options,
limits: &Limits,
stop: &mut dyn FnMut(Progress) -> bool,
) -> Result<(Proof, Step), Refusal> {
let reading = check::reading(proof, mode).unwrap_or_default();
let most = options
.nodes
.map_or(usize::MAX, |n| usize::try_from(n).unwrap_or(usize::MAX));
let mut rewrite = Rewrite {
proof,
forest: proof.forest(),
record,
reading,
nodes: proof.nodes().to_vec(),
overflowed: false,
table: framed::Table::of(proof),
most,
memory: limits.memory_bytes,
};
let (made, step) = rewrite.reduce(cut, mode)?;
let mut root = match made {
Made::Subproof(replacement) => rewrite.replace(cut, replacement, proof.root()),
Made::Erasure { kept, proved } => {
rewrite.specialize(cut, kept, &proved, most, limits.memory_bytes, stop)?
}
};
rewrite.within_ids()?;
let mut instances = None;
if rewrite.table.is_some() {
root = rewrite.apart(root, stop)?;
instances = Some(rewrite.compact(root));
}
let nodes = rewrite.nodes;
let forest = proof.forest.clone();
let made = match instances {
None => Proof::new(forest, nodes, root),
Some(instances) => Proof::with_instances(forest, instances, nodes, root),
}
.map_err(|error| match error {
Error::Refused(refusal) => refusal,
error => unreachable!("a rewrite keeps the arena's order and the table: {error}"),
})?;
let count = made.nodes().len() as u64;
if let Some(limit) = options.nodes
&& count > limit
{
return Err(Refusal::Elimination {
what: crate::limits::Bound::Nodes,
limit,
});
}
let bytes = count.saturating_mul(size_of::<Node>() as u64);
if let Some(limit) = limits.memory_bytes
&& bytes > limit
{
return Err(Refusal::Memory {
phase: Phase::Eliminate,
limit_bytes: limit,
needed_bytes: Some(bytes),
});
}
let made = Proof {
goal: proof.goal.clone(),
mode: Some(mode),
..made
};
Ok((made, step))
}
enum Made {
Subproof(NodeId),
Erasure {
kept: NodeId,
proved: Multiset<Member>,
},
}
struct Rewrite<'a> {
proof: &'a Proof,
forest: &'a Forest,
record: &'a Record,
reading: Option<Reading<'a>>,
nodes: Vec<Node>,
overflowed: bool,
table: Option<framed::Table>,
most: usize,
memory: Option<u64>,
}
impl Rewrite<'_> {
fn push(&mut self, node: Node) -> NodeId {
let id = match u32::try_from(self.nodes.len()) {
Ok(id) if id < u32::MAX => id,
_ => {
self.overflowed = true;
u32::MAX
}
};
self.nodes.push(node);
NodeId::new(id)
}
fn within_ids(&self) -> Result<(), Refusal> {
if self.overflowed {
return Err(Refusal::Index {
what: crate::limits::Space::Node,
count: self.nodes.len() as u64,
most: u64::from(u32::MAX),
});
}
Ok(())
}
fn node(&self, id: NodeId) -> Node {
self.nodes[id.index()]
}
fn cut(&mut self, a: Member, first: NodeId, second: NodeId) -> NodeId {
self.push(Node::Cut(a, first, second))
}
fn occ(&self, m: Member) -> OccId {
match &self.table {
Some(table) => table.resolve(m).0,
None => m.occ(),
}
}
fn beside(&mut self, o: OccId, like: Member) -> Member {
match &mut self.table {
Some(table) => table.beside(o, like),
None => Member::from(o),
}
}
fn left(&mut self, m: Member) -> Member {
let o = self.forest.left(self.occ(m)).expect("a connective");
self.beside(o, m)
}
fn right(&mut self, m: Member) -> Member {
let o = self.forest.right(self.occ(m)).expect("a binary connective");
self.beside(o, m)
}
fn child(&mut self, m: Member, side: Branch) -> Member {
match side {
Branch::Left => self.left(m),
Branch::Right => self.right(m),
}
}
fn dual(&mut self, m: Member) -> Member {
let o = self.forest.dual(self.occ(m)).expect("a cut formula's tree");
self.beside(o, m)
}
fn body(&mut self, m: Member, term: FoTermId) -> Member {
self.table
.as_mut()
.expect("a binder's proof has instances")
.body(m, term)
}
fn holds(&self, id: NodeId, x: Member, consumed: Option<Member>) -> bool {
let zone = self.record.zone(id).as_slice();
let count = zone.partition_point(|&o| o <= x) - zone.partition_point(|&o| o < x);
count > usize::from(consumed == Some(x))
}
fn holder(
&self,
x: Member,
first: (NodeId, Option<Member>),
second: (NodeId, Option<Member>),
) -> Branch {
if self.holds(first.0, x, first.1) {
Branch::Left
} else if self.holds(second.0, x, second.1) {
Branch::Right
} else {
self.absorber(self.is_output(x), first, second)
}
}
fn absorber(
&self,
output: bool,
first: (NodeId, Option<Member>),
second: (NodeId, Option<Member>),
) -> Branch {
let takes = |(id, taken): (NodeId, Option<Member>)| {
self.record.absorbs[id.index()] && !(output && self.has_output(id, taken))
};
if takes(first) || !takes(second) {
Branch::Left
} else {
Branch::Right
}
}
fn is_output(&self, x: Member) -> bool {
self.reading
.as_ref()
.is_some_and(|reading| reading.position(self.occ(x)) == Side::Output)
}
fn has_output(&self, id: NodeId, taken: Option<Member>) -> bool {
self.reading.is_some()
&& (self
.record
.zone(id)
.as_slice()
.iter()
.any(|&o| self.is_output(o))
|| taken.is_some_and(|t| self.is_output(t)))
}
fn split(&mut self, node: Node) -> Option<[(NodeId, Option<Member>); 2]> {
match node {
Node::Tensor(o, p, q) => {
let (l, r) = (self.left(o), self.right(o));
Some([(p, Some(l)), (q, Some(r))])
}
Node::Cut(b, p, q) => {
let d = self.dual(b);
Some([(p, Some(b)), (q, Some(d))])
}
Node::Mix(p, q) => Some([(p, None), (q, None)]),
_ => None,
}
}
fn reduce(&mut self, cut: NodeId, mode: Mode) -> Result<(Made, Step), Refusal> {
let Node::Cut(a, l, r) = self.node(cut) else {
unreachable!("the node reduced is a cut")
};
let da = self.dual(a);
let (nl, nr) = (self.node(l), self.node(r));
let step = |case, above| Step {
cut,
formula: a,
case,
above,
};
if let Node::Ax(x, y) = nl {
let other = if x == a { y } else { x };
let made = self.rename(r, da, other);
return Ok((Made::Subproof(made), step(Case::Axiom, None)));
}
if let Node::Ax(x, y) = nr {
let other = if x == da { y } else { x };
let made = self.rename(l, a, other);
return Ok((Made::Subproof(made), step(Case::Axiom, None)));
}
if mode.affine {
if let Node::Weaken(w, k) = nl
&& w == a
{
return Ok((self.erase(k, l, a, r, da), step(Case::Weakening, None)));
}
if let Node::Weaken(w, k) = nr
&& w == da
{
return Ok((self.erase(k, r, da, l, a), step(Case::Weakening, None)));
}
}
if !principal(nl, a) {
let made = self.commute(cut, Branch::Left);
return Ok((Made::Subproof(made), step(Case::Commutative, Some(l))));
}
if !principal(nr, da) {
let made = self.commute(cut, Branch::Right);
return Ok((Made::Subproof(made), step(Case::Commutative, Some(r))));
}
let key = |made, case| (Made::Subproof(made), step(case, None));
Ok(match (nl, nr) {
(Node::Tensor(_, l1, l2), Node::Par(_, r1)) => {
let (left, right) = (self.left(a), self.right(a));
let inner = self.cut(right, l2, r1);
key(self.cut(left, l1, inner), Case::TensorPar)
}
(Node::Par(_, l1), Node::Tensor(_, r1, r2)) => {
let (left, right) = (self.left(a), self.right(a));
let inner = self.cut(right, l1, r2);
key(self.cut(left, inner, r1), Case::TensorPar)
}
(Node::One(_), Node::Bot(_, r1)) => key(r1, Case::OneBot),
(Node::Bot(_, l1), Node::One(_)) => key(l1, Case::OneBot),
(Node::With(_, l1, l2), Node::Plus(_, side, r1)) => {
let premise = if side == Branch::Left { l1 } else { l2 };
let child = self.child(a, side);
key(self.cut(child, premise, r1), Case::WithPlus)
}
(Node::Plus(_, side, l1), Node::With(_, r1, r2)) => {
let premise = if side == Branch::Left { r1 } else { r2 };
let child = self.child(a, side);
key(self.cut(child, l1, premise), Case::WithPlus)
}
(Node::Bang(..), Node::Weaken(_, r1)) => key(r1, Case::Weakening),
(Node::Weaken(_, l1), Node::Bang(..)) => key(l1, Case::Weakening),
(Node::Bang(_, l1), Node::Quest(_, r1)) => {
let (made, case, above) = self.exponential(cut, Branch::Left, l1, r1);
(Made::Subproof(made), step(case, above))
}
(Node::Quest(_, l1), Node::Bang(_, r1)) => {
let (made, case, above) = self.exponential(cut, Branch::Right, r1, l1);
(Made::Subproof(made), step(case, above))
}
(Node::Forall(_, e, l1), Node::Exists(_, w, r1)) => {
let body = self.body(a, w);
let l1 = self.substitute(l1, &witness(e, w))?;
key(self.cut(body, l1, r1), Case::ForallExists)
}
(Node::Exists(_, w, l1), Node::Forall(_, e, r1)) => {
let body = self.body(a, w);
let r1 = self.substitute(r1, &witness(e, w))?;
key(self.cut(body, l1, r1), Case::ForallExists)
}
(nl, nr) => unreachable!("no rule of a checked proof gives {nl} against {nr}"),
})
}
fn commute(&mut self, cut: NodeId, side: Branch) -> NodeId {
let Node::Cut(a, l, r) = self.node(cut) else {
unreachable!("the node reduced is a cut")
};
let (premise, x) = match side {
Branch::Left => (l, a),
Branch::Right => (r, self.dual(a)),
};
let cut_with = |this: &mut Self, p: NodeId| match side {
Branch::Left => this.cut(a, p, r),
Branch::Right => this.cut(a, l, p),
};
let node = self.node(premise);
if let Node::Top(_) = node {
return premise;
}
if let Node::With(o, p, q) = node {
let (p, q) = (cut_with(self, p), cut_with(self, q));
return self.push(Node::With(o, p, q));
}
if let Some([(p, tp), (q, tq)]) = self.split(node) {
let made = match self.holder(x, (p, tp), (q, tq)) {
Branch::Left => {
let p = cut_with(self, p);
node.with_premises(p, q)
}
Branch::Right => {
let q = cut_with(self, q);
node.with_premises(p, q)
}
};
return self.push(made);
}
let [p] = node.premises().collect::<Vec<_>>()[..] else {
unreachable!("{node} acts on the cut formula or has one premise")
};
let p = cut_with(self, p);
self.push(node.map_premises(|_| p))
}
fn exponential(
&mut self,
cut: NodeId,
boxed: Branch,
content: NodeId,
quest: NodeId,
) -> (NodeId, Case, Option<NodeId>) {
let Node::Cut(a, l, r) = self.node(cut) else {
unreachable!("the node reduced is a cut")
};
let inside = self.left(a);
let x = match boxed {
Branch::Left => self.dual(inside),
Branch::Right => inside,
};
let uses = self.uses(quest, x);
let wrap = |this: &mut Self, p: NodeId| {
if !uses[p.index()] {
return p;
}
match boxed {
Branch::Left => {
let Node::Quest(q, _) = this.node(r) else {
unreachable!("the other premise is a ? step")
};
let p = this.push(Node::Quest(q, p));
this.cut(a, l, p)
}
Branch::Right => {
let Node::Quest(q, _) = this.node(l) else {
unreachable!("the other premise is a ? step")
};
let p = this.push(Node::Quest(q, p));
this.cut(a, p, r)
}
}
};
let open = |this: &mut Self, p: NodeId| match boxed {
Branch::Left => this.cut(inside, content, p),
Branch::Right => this.cut(inside, p, content),
};
if !uses[quest.index()] {
return (quest, Case::Weakening, None);
}
let node = self.node(quest);
match node {
Node::Copy(o, p) if o == x => {
if uses[p.index()] {
let kept = wrap(self, p);
(open(self, kept), Case::Contraction, Some(quest))
} else {
(open(self, p), Case::Dereliction, Some(quest))
}
}
Node::Bang(o, p) => {
let p = wrap(self, p);
(self.push(Node::Bang(o, p)), Case::BoxIntoBox, Some(quest))
}
Node::With(o, p, q) => {
let (p, q) = (wrap(self, p), wrap(self, q));
(
self.push(Node::With(o, p, q)),
Case::Commutative,
Some(quest),
)
}
Node::Tensor(_, p, q) | Node::Mix(p, q) | Node::Cut(_, p, q) => {
let case = if uses[p.index()] && uses[q.index()] {
Case::Contraction
} else {
Case::Commutative
};
let (p, q) = (wrap(self, p), wrap(self, q));
(self.push(node.with_premises(p, q)), case, Some(quest))
}
node => {
let [p] = node.premises().collect::<Vec<_>>()[..] else {
unreachable!("a node that uses the zone has premises")
};
let p = wrap(self, p);
(
self.push(node.map_premises(|_| p)),
Case::Commutative,
Some(quest),
)
}
}
}
fn uses(&mut self, top: NodeId, x: Member) -> Vec<bool> {
let quest = self.forest.parent(self.occ(x)).map(|q| self.beside(q, x));
let mut uses = vec![false; top.index() + 1];
for i in 0..=top.index() {
uses[i] = match self.nodes[i] {
Node::Copy(o, p) => o == x || uses[p.index()],
Node::Quest(o, p) => Some(o) != quest && uses[p.index()],
node => node.premises().any(|p| uses[p.index()]),
};
}
uses
}
fn rename(&mut self, top: NodeId, from: Member, to: Member) -> NodeId {
let mut seen: HashSet<NodeId> = HashSet::default();
let mut on: Vec<(NodeId, Option<Branch>)> = Vec::new();
let mut stack = vec![top];
while let Some(id) = stack.pop() {
if !seen.insert(id) {
continue;
}
let node = self.node(id);
let mut entered = None;
match node {
Node::Ax(..) | Node::One(_) | Node::Top(_) => {}
Node::Weaken(o, _) if o == from => {}
Node::With(_, p, q) => stack.extend([p, q]),
node => match self.split(node) {
Some([first, second]) => {
let side = self.holder(from, first, second);
entered = Some(side);
stack.push(match side {
Branch::Left => first.0,
Branch::Right => second.0,
});
}
None => stack.extend(node.premises()),
},
}
on.push((id, entered));
}
on.sort_unstable_by_key(|&(id, _)| id);
let mut made: HashMap<NodeId, NodeId> = HashMap::default();
for (id, entered) in on {
let old = self.node(id);
let split = entered.and_then(|_| self.split(old));
let new = |p: NodeId| made.get(&p).copied().unwrap_or(p);
let node = match (old, entered) {
(Node::Ax(x, y), _) if x == from => Node::Ax(to, y),
(Node::Ax(x, y), _) if y == from => Node::Ax(x, to),
(Node::Weaken(o, p), _) if o == from => Node::Weaken(to, p),
(node, Some(side)) => {
let [first, second] = split.expect("a rule of two premises");
match side {
Branch::Left => node.with_premises(new(first.0), second.0),
Branch::Right => node.with_premises(first.0, new(second.0)),
}
}
(node, None) => node.map_premises(new),
};
if node != old {
let new = self.push(node);
made.insert(id, new);
}
}
made.get(&top).copied().unwrap_or(top)
}
fn erase(
&mut self,
kept: NodeId,
weakened: NodeId,
ours: Member,
erased: NodeId,
theirs: Member,
) -> Made {
let mut proved = self.record.zone(weakened).clone();
proved.remove(ours);
if self.record.absorbs[erased.index()] && !self.record.absorbs[kept.index()] {
return Made::Erasure { kept, proved };
}
let mut context = self.record.zone(erased).clone();
context.remove(theirs);
Made::Subproof(self.weaken(kept, &context))
}
fn weaken(&mut self, kept: NodeId, context: &Multiset<Member>) -> NodeId {
context
.as_slice()
.iter()
.fold(kept, |p, &o| self.push(Node::Weaken(o, p)))
}
fn replace(&mut self, at: NodeId, replacement: NodeId, root: NodeId) -> NodeId {
let mut made: Vec<Option<NodeId>> = vec![None; root.index() + 1];
made[at.index()] = Some(replacement);
for i in at.index() + 1..=root.index() {
let node = self.nodes[i];
if node.premises().any(|p| made[p.index()].is_some()) {
let node = node.map_premises(|p| made[p.index()].unwrap_or(p));
made[i] = Some(self.push(node));
}
}
made[root.index()].unwrap_or(root)
}
fn specialize(
&mut self,
cut: NodeId,
kept: NodeId,
proved: &Multiset<Member>,
most: usize,
memory: Option<u64>,
stop: &mut dyn FnMut(Progress) -> bool,
) -> Result<NodeId, Refusal> {
const POLL: usize = 4096;
struct Pair {
id: NodeId,
zone: Multiset<Member>,
premises: [Option<usize>; 2],
}
let root = self.proof.root();
let mut reaches = vec![false; root.index() + 1];
reaches[cut.index()] = true;
for i in cut.index() + 1..=root.index() {
reaches[i] = self.nodes[i].premises().any(|p| reaches[p.index()]);
}
let mut pairs = vec![Pair {
id: root,
zone: Multiset::of(self.proof.conclusion().into_iter().map(Member::from)),
premises: [None; 2],
}];
let mut index: HashMap<(NodeId, Multiset<Member>), usize> = HashMap::default();
let mut stack = vec![0];
let refused = || Refusal::Elimination {
what: crate::limits::Bound::Nodes,
limit: most as u64,
};
let mut held: u64 = 0;
let mut hold = |members: usize, nodes: usize| -> Result<(), Refusal> {
held = held
.saturating_add((members as u64).saturating_mul(8))
.saturating_add((nodes as u64).saturating_mul(64));
match memory {
Some(limit) if held > limit => Err(Refusal::Memory {
phase: Phase::Eliminate,
limit_bytes: limit,
needed_bytes: None,
}),
_ => Ok(()),
}
};
let mut popped: usize = 0;
while let Some(k) = stack.pop() {
popped += 1;
if popped.is_multiple_of(POLL)
&& stop(Progress::new(Phase::Eliminate, POLL as u64, popped as u64))
{
return Err(Refusal::Stopped {
phase: Phase::Eliminate,
});
}
let id = pairs[k].id;
if id == cut {
continue;
}
let node = self.nodes[id.index()];
let zone = pairs[k].zone.clone();
let above = self.above(node, &zone);
for (j, (p, zone)) in node.premises().zip(above).enumerate() {
if !reaches[p.index()] {
continue;
}
let at = match index.get(&(p, zone.clone())) {
Some(&at) => at,
None => {
if pairs.len() >= most {
return Err(refused());
}
hold(zone.as_slice().len(), 1)?;
pairs.push(Pair {
id: p,
zone: zone.clone(),
premises: [None; 2],
});
index.insert((p, zone), pairs.len() - 1);
stack.push(pairs.len() - 1);
pairs.len() - 1
}
};
pairs[k].premises[j] = Some(at);
}
}
let weakenings = pairs
.iter()
.filter(|pair| pair.id == cut)
.fold(0usize, |sum, pair| {
sum.saturating_add(pair.zone.difference(proved).as_slice().len())
});
if pairs.len().saturating_add(weakenings) > most {
return Err(refused());
}
hold(0, weakenings)?;
let mut order: Vec<usize> = (0..pairs.len()).collect();
order.sort_unstable_by_key(|&k| pairs[k].id);
let mut made = vec![NodeId::new(0); pairs.len()];
for k in order {
let pair = &pairs[k];
made[k] = if pair.id == cut {
let context = pair.zone.difference(proved);
self.weaken(kept, &context)
} else {
let node = self.nodes[pair.id.index()];
let mut j = 0;
let premises = pair.premises;
let node = node.map_premises(|p| {
let at = premises[j];
j += 1;
at.map_or(p, |at| made[at])
});
self.push(node)
};
}
Ok(made[0])
}
fn above(&mut self, node: Node, zone: &Multiset<Member>) -> Vec<Multiset<Member>> {
let change = |removed: Option<Member>, added: &[Member]| {
let mut up = zone.clone();
if let Some(o) = removed {
up.remove(o);
}
for &o in added {
up.insert(o);
}
up
};
if let Some([(p, tp), (q, tq)]) = self.split(node) {
let removed = match node {
Node::Tensor(o, ..) => Some(o),
_ => None,
};
let mut rest = change(removed, &[]);
let derived = |id: NodeId, taken: Option<Member>| {
let mut up = self.record.zone(id).clone();
if let Some(t) = taken
&& !up.contains(t)
{
up.insert(t);
}
up
};
let (mut up_p, mut up_q) = (derived(p, tp), derived(q, tq));
for (up, taken) in [(&up_p, tp), (&up_q, tq)] {
let mut own = up.clone();
if let Some(t) = taken {
own.remove(t);
}
rest = rest.difference(&own);
}
let output = rest.as_slice().iter().any(|&o| self.is_output(o));
match self.absorber(output, (p, tp), (q, tq)) {
Branch::Left => up_p = up_p.sum(&rest),
Branch::Right => up_q = up_q.sum(&rest),
}
return vec![up_p, up_q];
}
match node {
Node::Par(o, _) => {
let (l, r) = (self.left(o), self.right(o));
vec![change(Some(o), &[l, r])]
}
Node::Bang(o, _) => {
let content = self.left(o);
vec![change(Some(o), &[content])]
}
Node::Bot(o, _) | Node::Quest(o, _) | Node::Weaken(o, _) => vec![change(Some(o), &[])],
Node::Plus(o, side, _) => {
let child = self.child(o, side);
vec![change(Some(o), &[child])]
}
Node::With(o, ..) => {
let (l, r) = (self.left(o), self.right(o));
vec![change(Some(o), &[l]), change(Some(o), &[r])]
}
Node::Copy(o, _) => vec![change(None, &[o])],
Node::Forall(o, a, _) => {
let term = self
.table
.as_mut()
.expect("a binder's proof has instances")
.eigen(a);
let body = self.body(o, term);
vec![change(Some(o), &[body])]
}
Node::Exists(o, w, _) => {
let body = self.body(o, w);
vec![change(Some(o), &[body])]
}
_ => vec![],
}
}
}
fn principal(node: Node, x: Member) -> bool {
match node {
Node::Ax(p, q) => p == x || q == x,
Node::Copy(..) | Node::Mix(..) | Node::Cut(..) => false,
node => node.principal() == Some(x),
}
}
fn witness(a: Eigen, w: FoTermId) -> HashMap<Eigen, FoTermId> {
let mut sigma = HashMap::default();
sigma.insert(a, w);
sigma
}
impl Node {
fn with_premises(self, first: NodeId, second: NodeId) -> Self {
match self {
Self::Tensor(o, ..) => Self::Tensor(o, first, second),
Self::With(o, ..) => Self::With(o, first, second),
Self::Mix(..) => Self::Mix(first, second),
Self::Cut(o, ..) => Self::Cut(o, first, second),
node => unreachable!("{node} has two premises"),
}
}
}
mod framed;
#[cfg(all(test, feature = "parse", feature = "interactive"))]
mod tests;