use super::Interactive;
use crate::Error;
use crate::limits::{Limits, Progress};
use crate::linear::occurrences::Member;
use crate::linear::proofs::Rule;
use crate::linear::proofs::derivation::InfId;
use crate::linear::proofs::{Branch, Node, NodeId, Proof};
use crate::linear::sequents::Kind;
impl Interactive {
pub(super) fn postorder(&self) -> Vec<InfId> {
let mut order = Vec::with_capacity(self.inferences.len());
let mut stack = vec![(InfId::new(0), false)];
while let Some((id, visited)) = stack.pop() {
if visited {
order.push(id);
} else {
stack.push((id, true));
let premises = &self.inferences[id.index()].premises;
stack.extend(premises.iter().rev().map(|&p| (p, false)));
}
}
order
}
pub fn proof(
&self,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Proof, Error> {
let open = self.goals().count();
if open > 0 {
return Err(Error::OpenGoals { count: open });
}
let mut terms = Terms {
state: self,
nodes: Vec::with_capacity(self.inferences.len()),
};
let mut root = terms.term(InfId::new(0));
for &r in self.forest.roots() {
if self.forest.kind(r) == Kind::Quest {
root = terms.push(Node::Quest(Member::from(r), root));
}
}
let nodes = terms.nodes;
let proof = match &self.fo {
Some(q) => Proof::with_instances(self.forest.clone(), q.closed_table()?, nodes, root)?,
None => Proof::new(self.forest.clone(), nodes, root)?,
}
.with_mode(self.mode);
proof.check_within(self.mode, limits, stop)?;
Ok(proof)
}
}
pub(super) struct Terms<'a> {
state: &'a Interactive,
nodes: Vec<Node>,
}
impl Terms<'_> {
pub(super) fn push(&mut self, node: Node) -> NodeId {
self.nodes.push(node);
NodeId::new(self.nodes.len() as u32 - 1)
}
pub(super) fn term(&mut self, root: InfId) -> NodeId {
use Rule::*;
enum Step {
Visit(InfId),
Quests([Option<Member>; 2]),
Build(InfId),
}
let state = self.state;
let f = &state.forest;
let mut steps = vec![Step::Visit(root)];
let mut done: Vec<NodeId> = Vec::new();
while let Some(step) = steps.pop() {
let id = match step {
Step::Visit(id) | Step::Build(id) => id,
Step::Quests(introduced) => {
let mut node = done.pop().expect("the premise's term");
for x in introduced.into_iter().flatten() {
if f.kind(state.occurrence(x)) == Kind::Quest {
node = self.push(Node::Quest(x, node));
}
}
done.push(node);
continue;
}
};
let inference = &state.inferences[id.index()];
let sequent = &inference.sequent;
let premises = &inference.premises;
let o = || {
sequent[inference
.principal
.expect("every rule but ax and mix has one")]
};
let principal = || state.occurrence(o());
let a = || {
state.child(
o(),
f.left(principal()).expect("a connective with a subformula"),
)
};
let b = || state.child(o(), f.right(principal()).expect("a binary connective"));
let rule = inference.rule.rule;
if matches!(step, Step::Visit(_)) {
let introduced: [[Option<Member>; 2]; 2] = match rule {
Forall | Exists => [[state.body(id), None], [None; 2]],
Ax | One | Top => {
#[expect(
clippy::wildcard_enum_match_arm,
reason = "the arm holds three rules"
)]
let leaf = match rule {
Ax => Node::Ax(sequent[0], sequent[1]),
One => Node::One(o()),
_ => Node::Top(o()),
};
let leaf = self.push(leaf);
done.push(leaf);
continue;
}
Contraction | Weakening => {
steps.push(Step::Visit(premises[0]));
continue;
}
Par => [[Some(a()), Some(b())], [None; 2]],
Bot | AffineWeakening | Mix => [[None; 2]; 2],
PlusLeft | Promotion | Dereliction => [[Some(a()), None], [None; 2]],
PlusRight => [[Some(b()), None], [None; 2]],
With | Tensor => [[Some(a()), None], [Some(b()), None]],
Cut => {
let (a, dual) = state
.cut_pair(inference.cut.expect("a cut names its formula"))
.expect("a session's cut is on a cut formula or its instance");
[[Some(a), None], [Some(dual), None]]
}
Open => unreachable!("no goal is open"),
};
steps.push(Step::Build(id));
for (&premise, introduced) in premises.iter().zip(introduced).rev() {
steps.push(Step::Quests(introduced));
steps.push(Step::Visit(premise));
}
continue;
}
let mut premise = || done.pop().expect("a premise's term");
let node = match rule {
Forall => Node::Forall(
o(),
state
.introduced(id)
.expect("a ∀ step introduces an eigenvariable"),
premise(),
),
Exists => Node::Exists(
o(),
state.shown_witness(id).expect("an ∃ step has a witness"),
premise(),
),
Par => Node::Par(o(), premise()),
Bot => Node::Bot(o(), premise()),
PlusLeft => Node::Plus(o(), Branch::Left, premise()),
PlusRight => Node::Plus(o(), Branch::Right, premise()),
Promotion => Node::Bang(o(), premise()),
Dereliction => Node::Copy(a(), premise()),
AffineWeakening => Node::Weaken(o(), premise()),
With => {
let (r, l) = (premise(), premise());
Node::With(o(), l, r)
}
Tensor => {
let (r, l) = (premise(), premise());
Node::Tensor(o(), l, r)
}
Mix => {
let (r, l) = (premise(), premise());
Node::Mix(l, r)
}
Cut => {
let (r, l) = (premise(), premise());
Node::Cut(inference.cut.expect("a cut names its formula"), l, r)
}
Ax | One | Top | Contraction | Weakening | Open => {
unreachable!("a rule that is no node over its premises")
}
};
let node = self.push(node);
done.push(node);
}
done.pop().expect("the root's term")
}
}