use super::derivation::{check_inference, same};
use super::translate::Extra;
use super::{Derivation, Formulas, Inference, Logic, Node, NodeId, Outcome, Rule, Sequent, Side};
use super::{Translation, Verdict, bound, decide_within};
use crate::Error;
use crate::limits::{Limits, Phase, Progress, Refusal};
use crate::linear::proofs::{GoalId, InfId, Size, Structural, ViewOptions};
use crate::linear::search;
use std::fmt::{Display, Formatter, Result as FmtResult};
#[derive(Clone, Debug, PartialEq, Eq)]
#[cfg_attr(
feature = "serialize",
derive(serde::Serialize),
serde(tag = "kind", rename_all = "snake_case")
)]
#[non_exhaustive]
pub enum StepError {
#[non_exhaustive]
NoGoal {
goal: GoalId,
},
#[non_exhaustive]
NoFormula {
side: Side,
position: usize,
len: usize,
},
#[non_exhaustive]
Rule {
rule: Rule,
side: Side,
position: usize,
},
#[non_exhaustive]
Logic {
rule: Rule,
logic: Logic,
},
#[non_exhaustive]
NoPartner {
side: Side,
position: usize,
},
#[non_exhaustive]
Succedents {
count: usize,
},
#[non_exhaustive]
Split {
side: Side,
position: usize,
},
#[non_exhaustive]
NoSplit {
rule: Rule,
},
#[non_exhaustive]
Size {
estimate_bytes: u64,
limit_bytes: u64,
},
}
const fn of(side: Side) -> &'static str {
match side {
Side::Left => "left of ⊢",
Side::Right => "right of ⊢",
}
}
const fn target(rule: Rule) -> &'static str {
use Rule::*;
match rule {
Axiom => "a formula that stands on both sides of ⊢",
WeakenLeft | ContractLeft => "any formula left of ⊢",
WeakenRight | ContractRight => "any formula right of ⊢",
AndLeft | AndLeft1 | AndLeft2 => "a conjunction left of ⊢",
AndRight => "a conjunction right of ⊢",
OrLeft => "a disjunction left of ⊢",
OrRight | OrRight1 | OrRight2 => "a disjunction right of ⊢",
ImpliesLeft => "an implication left of ⊢",
ImpliesRight => "an implication right of ⊢",
NotLeft => "a negation left of ⊢",
NotRight => "a negation right of ⊢",
IffLeft | IffLeft1 | IffLeft2 => "an equivalence left of ⊢",
IffRight => "an equivalence right of ⊢",
FalseLeft => "⊥ left of ⊢",
FalseRight => "⊥ right of ⊢",
TrueLeft => "⊤ left of ⊢",
TrueRight => "⊤ right of ⊢",
Cut => "no formula of a goal, so no step takes it",
Open => "no formula, since it only marks an open goal",
}
}
impl Display for StepError {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
match self {
StepError::NoGoal { goal } => write!(f, "there is no open goal {}", goal.get()),
StepError::NoFormula {
side,
position,
len,
} => write!(
f,
"the goal has no formula {position} {}: it has {} there, and positions \
start at 0",
of(*side),
crate::errors::counted(*len, "formula", "formulas")
),
StepError::Rule {
rule,
side,
position,
} => write!(
f,
"the rule {rule} does not act on formula {position} {}: it acts on {}",
of(*side),
target(*rule)
),
StepError::Logic { rule, logic } => {
let why = match (rule, logic) {
(Rule::FalseLeft, Logic::Minimal) => "minimal logic has no ex falso",
(Rule::OrRight, _) => {
"its premise would have both disjuncts right of ⊢, and every goal of LJ \
has exactly one formula there: use ∨R₁ or ∨R₂ to keep one disjunct"
}
(Rule::ContractRight, _) => {
"its premise would have two formulas right of ⊢, and every goal of LJ \
has exactly one"
}
_ => {
"its premise would have no formula right of ⊢, and every goal of LJ has \
exactly one"
}
};
write!(
f,
"the rule {rule} is not available in {logic} logic: {why}"
)
}
StepError::NoPartner { side, position } => write!(
f,
"the axiom needs formula {position} {} to stand {} too",
of(*side),
of(side.flip())
),
StepError::Succedents { count } => write!(
f,
"a premise would have {} right of ⊢, and every goal of LJ has exactly one: \
share the context, or split it so that each premise keeps one formula right \
of ⊢",
crate::errors::counted(*count, "formula", "formulas")
),
StepError::Split { side, position } => write!(
f,
"the split's position {position} {} is out of range, named twice, or the \
formula the rule acts on: name each other formula of the goal at most once",
of(*side)
),
StepError::Size {
estimate_bytes,
limit_bytes,
} => write!(
f,
"the weakenings or contractions this step makes are estimated at \
{estimate_bytes} bytes, over the derivation bound of {limit_bytes} bytes the \
proof was started or read with: start it with a higher bound"
),
StepError::NoSplit { rule } => {
write!(
f,
"the rule {rule} has fewer than two premises and takes no split"
)
}
}
}
}
impl std::error::Error for StepError {}
#[non_exhaustive]
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub enum Context {
#[default]
Shared,
#[non_exhaustive]
Split {
left: Vec<usize>,
right: Vec<usize>,
},
}
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Step {
pub side: Side,
pub position: usize,
pub rule: Rule,
pub context: Context,
}
impl Step {
pub const fn new(side: Side, position: usize, rule: Rule) -> Self {
Self {
side,
position,
rule,
context: Context::Shared,
}
}
#[must_use]
pub fn split(self, left: &[usize], right: &[usize]) -> Self {
Self {
context: Context::Split {
left: left.to_vec(),
right: right.to_vec(),
},
..self
}
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Applicable {
pub rule: Rule,
pub needs: Needs,
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Needs {
Nothing,
Context,
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Closed {
pub outcome: Outcome,
pub grafted: Result<(), Refusal>,
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Hint {
pub outcome: Outcome,
pub steps: Vec<Step>,
}
enum Shape {
Leaf,
Unary(Vec<NodeId>, Vec<NodeId>),
Binary([(Vec<NodeId>, Vec<NodeId>); 2]),
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug)]
pub struct Interactive {
logic: Logic,
formulas: Formulas,
falsity: NodeId,
inferences: Vec<Inference>,
history: Vec<InfId>,
limit: Option<u64>,
}
const fn open(left: Vec<NodeId>, right: Vec<NodeId>) -> Inference {
Inference {
left,
right,
rule: Rule::Open,
principal: None,
premises: Vec::new(),
}
}
impl Interactive {
pub fn new(sequent: &Sequent, logic: Logic) -> Result<Self, Error> {
Self::within(sequent, logic, &Limits::default())
}
pub fn within(sequent: &Sequent, logic: Logic, limits: &Limits) -> Result<Self, Error> {
if logic != Logic::Classical && sequent.right.len() > 1 {
return Err(Error::Succedents {
count: sequent.right.len(),
});
}
let mut formulas = sequent.formulas.clone();
bound(&formulas, &sequent.left, &sequent.right, limits)?;
let falsity = Extra::add(&mut formulas)?.falsity;
let mut right = sequent.right.clone();
if logic != Logic::Classical && right.is_empty() {
right.push(falsity);
}
Ok(Self {
logic,
formulas,
falsity,
inferences: vec![open(sequent.left.clone(), right)],
history: Vec::new(),
limit: limits.derivation_bytes,
})
}
pub fn logic(&self) -> Logic {
self.logic
}
pub fn formulas(&self) -> &Formulas {
&self.formulas
}
pub fn sequent(&self) -> (&[NodeId], &[NodeId]) {
let root = &self.inferences[0];
(&root.left, &root.right)
}
pub fn goals(&self) -> impl Iterator<Item = GoalId> + '_ {
self.inferences
.iter()
.enumerate()
.filter(|(_, inference)| inference.rule == Rule::Open)
.map(|(i, _)| GoalId::new(i as u32))
}
pub fn goal(&self, id: GoalId) -> Result<(&[NodeId], &[NodeId]), StepError> {
let goal = self.open(id)?;
Ok((&goal.left, &goal.right))
}
fn open(&self, id: GoalId) -> Result<&Inference, StepError> {
self.inferences
.get(id.index())
.filter(|inference| inference.rule == Rule::Open)
.ok_or(StepError::NoGoal { goal: id })
}
pub fn is_complete(&self) -> bool {
self.goals().next().is_none()
}
pub fn steps(&self) -> usize {
self.history.len()
}
pub fn rules(
&self,
goal: GoalId,
side: Side,
position: usize,
) -> Result<Vec<Applicable>, StepError> {
let goal = self.open(goal)?;
let x = formula_at(goal, side, position)?;
let mut rules = Vec::new();
if goal.side(side.flip()).contains(&x) {
rules.push(Applicable {
rule: Rule::Axiom,
needs: Needs::Nothing,
});
}
for rule in Rule::ALL {
if let Ok(shape) = self.shape(rule, side, position, x) {
rules.push(Applicable {
rule,
needs: match shape {
Shape::Binary(_) => Needs::Context,
Shape::Leaf | Shape::Unary(..) => Needs::Nothing,
},
});
}
}
Ok(rules)
}
fn shape(
&self,
rule: Rule,
side: Side,
position: usize,
x: NodeId,
) -> Result<Shape, StepError> {
use Rule::*;
use Side::{Left, Right};
let node = self.formulas.node(x);
let fits = match rule {
Axiom | Cut | Open => false,
WeakenLeft | ContractLeft => side == Left,
WeakenRight | ContractRight => side == Right,
AndLeft | AndLeft1 | AndLeft2 => side == Left && matches!(node, Node::And(..)),
AndRight => side == Right && matches!(node, Node::And(..)),
OrLeft => side == Left && matches!(node, Node::Or(..)),
OrRight | OrRight1 | OrRight2 => side == Right && matches!(node, Node::Or(..)),
ImpliesLeft => side == Left && matches!(node, Node::Implies(..)),
ImpliesRight => side == Right && matches!(node, Node::Implies(..)),
NotLeft => side == Left && matches!(node, Node::Not(_)),
NotRight => side == Right && matches!(node, Node::Not(_)),
IffLeft | IffLeft1 | IffLeft2 => side == Left && matches!(node, Node::Iff(..)),
IffRight => side == Right && matches!(node, Node::Iff(..)),
FalseLeft => side == Left && node == Node::False,
FalseRight => side == Right && node == Node::False,
TrueLeft => side == Left && node == Node::True,
TrueRight => side == Right && node == Node::True,
};
if !fits {
return Err(StepError::Rule {
rule,
side,
position,
});
}
let classical = self.logic == Logic::Classical;
let refused = match rule {
WeakenRight | ContractRight | OrRight | FalseRight => !classical,
FalseLeft => self.logic == Logic::Minimal,
Axiom | WeakenLeft | ContractLeft | AndLeft | AndLeft1 | AndLeft2 | AndRight
| OrLeft | OrRight1 | OrRight2 | ImpliesLeft | ImpliesRight | NotLeft | NotRight
| IffLeft | IffLeft1 | IffLeft2 | IffRight | TrueLeft | TrueRight | Cut | Open => false,
};
if refused {
return Err(StepError::Logic {
rule,
logic: self.logic,
});
}
let ids = &self.formulas.ids;
let iff = |a, b| (ids[&Node::Implies(a, b)], ids[&Node::Implies(b, a)]);
let falsity = self.falsity;
Ok(match (rule, node) {
(WeakenLeft | WeakenRight | TrueLeft | FalseRight, _) => Shape::Unary(vec![], vec![]),
(ContractLeft | ContractRight, _) => Shape::Unary(vec![x, x], vec![]),
(TrueRight | FalseLeft, _) => Shape::Leaf,
(AndLeft, Node::And(a, b)) | (OrRight, Node::Or(a, b)) => {
Shape::Unary(vec![a, b], vec![])
}
(AndLeft1, Node::And(a, _)) | (OrRight1, Node::Or(a, _)) => {
Shape::Unary(vec![a], vec![])
}
(AndLeft2, Node::And(_, b)) | (OrRight2, Node::Or(_, b)) => {
Shape::Unary(vec![b], vec![])
}
(ImpliesRight, Node::Implies(a, b)) => Shape::Unary(vec![b], vec![a]),
(NotRight, Node::Not(a)) if classical => Shape::Unary(vec![], vec![a]),
(NotRight, Node::Not(a)) => Shape::Unary(vec![falsity], vec![a]),
(NotLeft, Node::Not(a)) if classical => Shape::Unary(vec![], vec![a]),
(NotLeft, Node::Not(a)) => Shape::Binary([(vec![], vec![a]), (vec![falsity], vec![])]),
(IffLeft, Node::Iff(a, b)) => {
let (forward, backward) = iff(a, b);
Shape::Unary(vec![forward, backward], vec![])
}
(IffLeft1, Node::Iff(a, b)) => Shape::Unary(vec![iff(a, b).0], vec![]),
(IffLeft2, Node::Iff(a, b)) => Shape::Unary(vec![iff(a, b).1], vec![]),
(AndRight, Node::And(a, b)) | (OrLeft, Node::Or(a, b)) => {
Shape::Binary([(vec![a], vec![]), (vec![b], vec![])])
}
(ImpliesLeft, Node::Implies(a, b)) => {
Shape::Binary([(vec![], vec![a]), (vec![b], vec![])])
}
(IffRight, Node::Iff(a, b)) => {
let (forward, backward) = iff(a, b);
Shape::Binary([(vec![forward], vec![]), (vec![backward], vec![])])
}
_ => unreachable!("{rule} fits a formula it has no shape for"),
})
}
pub fn apply(&mut self, goal: GoalId, step: &Step) -> Result<Vec<GoalId>, StepError> {
let made = self.expand(goal, step)?;
Ok(self.record(goal, made))
}
fn expand(&self, id: GoalId, step: &Step) -> Result<Vec<Inference>, StepError> {
let goal = self.open(id)?;
let (side, position, rule) = (step.side, step.position, step.rule);
let x = formula_at(goal, side, position)?;
let made = if rule == Rule::Axiom {
if step.context != Context::Shared {
return Err(StepError::NoSplit { rule });
}
let partner = goal
.side(side.flip())
.iter()
.position(|&y| y == x)
.ok_or(StepError::NoPartner { side, position })?;
let len = goal.left.len() + goal.right.len();
self.run_within(len, len)?;
axiom(goal, side, position, partner)
} else {
let shape = self.shape(rule, side, position, x)?;
if step.context != Context::Shared && !matches!(shape, Shape::Binary(_)) {
return Err(StepError::NoSplit { rule });
}
if self.logic != Logic::Classical
&& step.context == Context::Shared
&& let Shape::Binary([first, second]) = &shape
&& side == Side::Left
&& !first.1.is_empty()
{
let len = 2 * goal.left.len() + goal.right.len() + first.1.len();
self.run_within(goal.left.len() + 2, len)?;
return Ok(self.checked(contracted(goal, position, rule, first, second)));
}
let premises = match &shape {
Shape::Leaf => vec![],
Shape::Unary(same, other) => {
vec![premise(goal, side, position, same, other, |_, _| true)]
}
Shape::Binary([first, second]) => {
let to_first = self.split(goal, side, position, &step.context)?;
let goes = |s: Side, i: usize| match &to_first {
None => true,
Some((left, right)) => match s {
Side::Left => left[i],
Side::Right => right[i],
},
};
let stays = |s: Side, i: usize| to_first.is_none() || !goes(s, i);
vec![
premise(goal, side, position, &first.0, &first.1, goes),
premise(goal, side, position, &second.0, &second.1, stays),
]
}
};
if self.logic != Logic::Classical
&& let Some(p) = premises.iter().find(|p| p.right.len() != 1)
{
return Err(StepError::Succedents {
count: p.right.len(),
});
}
let mut made = vec![Inference {
left: goal.left.clone(),
right: goal.right.clone(),
rule,
principal: Some((side, position)),
premises: (1..=premises.len()).map(|k| InfId::new(k as u32)).collect(),
}];
made.extend(premises);
made
};
Ok(self.checked(made))
}
fn run_within(&self, inferences: usize, len: usize) -> Result<(), StepError> {
let (inferences, len) = (inferences as u64, len as u64);
let bytes = inferences.saturating_mul(
Size::BYTES_PER_INFERENCE.saturating_add(
len.saturating_mul(3)
.saturating_mul(Size::BYTES_PER_CHARACTER),
),
);
match self.limit {
Some(limit) if bytes > limit => Err(StepError::Size {
estimate_bytes: bytes,
limit_bytes: limit,
}),
_ => Ok(()),
}
}
fn checked(&self, made: Vec<Inference>) -> Vec<Inference> {
for inference in made.iter().filter(|i| i.rule != Rule::Open) {
let premises: Vec<&Inference> = inference
.premises
.iter()
.map(|p| &made[p.index()])
.collect();
if check_inference(&self.formulas, self.logic, inference, &premises).is_err() {
unreachable!("a step made an inference the checker refuses: {inference:?}");
}
}
made
}
#[expect(
clippy::type_complexity,
reason = "one flag per position of each side, used once"
)]
fn split(
&self,
goal: &Inference,
side: Side,
position: usize,
context: &Context,
) -> Result<Option<(Vec<bool>, Vec<bool>)>, StepError> {
let Context::Split { left, right } = context else {
return Ok(None);
};
let mut flags = (vec![false; goal.left.len()], vec![false; goal.right.len()]);
for (s, positions) in [(Side::Left, left), (Side::Right, right)] {
let list = match s {
Side::Left => &mut flags.0,
Side::Right => &mut flags.1,
};
for &p in positions {
let principal = s == side && p == position;
match list.get_mut(p) {
Some(flag) if !*flag && !principal => *flag = true,
_ => {
return Err(StepError::Split {
side: s,
position: p,
});
}
}
}
}
Ok(Some(flags))
}
fn record(&mut self, goal: GoalId, mut made: Vec<Inference>) -> Vec<GoalId> {
let base = self.inferences.len();
let global = |k: InfId| match k.index() {
0 => InfId::new(goal.get()),
k => InfId::new((base + k - 1) as u32),
};
for inference in &mut made {
for p in &mut inference.premises {
*p = global(*p);
}
}
let opened = made
.iter()
.enumerate()
.filter(|(_, i)| i.rule == Rule::Open)
.map(|(k, _)| GoalId::new(global(InfId::new(k as u32)).get()))
.collect();
let mut made = made.into_iter();
if let Some(first) = made.next() {
self.inferences[goal.index()] = first;
}
self.inferences.extend(made);
self.history.push(InfId::new(goal.get()));
opened
}
pub fn undo(&mut self) -> Option<GoalId> {
let goal = self.history.pop()?;
if let Some(first) = self.subtree(goal).into_iter().min() {
self.inferences.truncate(first.index());
}
let inference = &mut self.inferences[goal.index()];
inference.rule = Rule::Open;
inference.principal = None;
inference.premises.clear();
Some(GoalId::new(goal.get()))
}
fn subtree(&self, id: InfId) -> Vec<InfId> {
let mut ids = self.inferences[id.index()].premises.clone();
let mut i = 0;
while i < ids.len() {
ids.extend(self.inferences[ids[i].index()].premises.iter().copied());
i += 1;
}
ids
}
pub fn close(
&mut self,
goal: GoalId,
translation: Option<Translation>,
search: &search::Options,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Closed, Error> {
let outcome = self.decide(goal, translation, search, limits, stop)?;
let grafted = match &outcome.verdict {
Verdict::Valid(evidence) => match self.graft(goal, evidence.derivation()?, limits) {
Ok(()) => Ok(()),
Err(Error::Refused(refusal)) => Err(refusal),
Err(error) => return Err(error),
},
Verdict::NotValid | Verdict::Unknown(_) => Ok(()),
};
Ok(Closed { outcome, grafted })
}
pub fn hint(
&self,
goal: GoalId,
translation: Option<Translation>,
search: &search::Options,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Hint, Error> {
let outcome = self.decide(goal, translation, search, limits, stop)?;
self.open(goal)?;
let steps = match &outcome.verdict {
Verdict::Valid(evidence) => self.first_steps(goal, evidence.derivation()?),
Verdict::NotValid | Verdict::Unknown(_) => Vec::new(),
};
Ok(Hint { outcome, steps })
}
fn decide(
&self,
goal: GoalId,
translation: Option<Translation>,
search: &search::Options,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Outcome, Error> {
let goal = self.open(goal)?;
let sequent = Sequent {
formulas: self.formulas.clone(),
left: goal.left.clone(),
right: goal.right.clone(),
};
let options = super::Options::default()
.with_logic(self.logic)
.with_translation(translation)
.with_method(Some(super::Method::Embedding));
decide_within(&sequent, &options, search, limits, stop)
}
fn ids_of(formulas: &mut Formulas, other: &Formulas) -> Result<Vec<NodeId>, Error> {
let mut ids: Vec<NodeId> = Vec::with_capacity(other.len());
for &node in &other.nodes {
let at = |k: NodeId| ids[k.index()];
let id = match node {
Node::Atom(a) => formulas.atom(other.atom_name(a))?,
Node::True | Node::False => formulas.add(node)?,
Node::Not(a) => formulas.add(Node::Not(at(a)))?,
Node::And(a, b) => formulas.add(Node::And(at(a), at(b)))?,
Node::Or(a, b) => formulas.add(Node::Or(at(a), at(b)))?,
Node::Implies(a, b) => formulas.add(Node::Implies(at(a), at(b)))?,
Node::Iff(a, b) => formulas.add(Node::Iff(at(a), at(b)))?,
};
ids.push(id);
}
Ok(ids)
}
fn graft(&mut self, goal: GoalId, found: &Derivation, limits: &Limits) -> Result<(), Error> {
let estimate = estimate(found.formulas(), found.inferences());
if let Some(limit) = limits.derivation_bytes
&& estimate > limit
{
return Err(Error::Refused(Refusal::Output {
what: "derivation",
estimate_bytes: estimate,
limit_bytes: limit,
least_bytes: None,
}));
}
let ids = Self::ids_of(&mut self.formulas, found.formulas())?;
let map = |list: &[NodeId]| list.iter().map(|k| ids[k.index()]).collect::<Vec<_>>();
let root = found.inferences().len() - 1;
let base = self.inferences.len();
let at = InfId::new(goal.get());
let renumber = |id: InfId| {
if id.index() == root {
at
} else {
InfId::new((base + root - 1 - id.index()) as u32)
}
};
let mut grafted: Vec<Inference> = found
.inferences()
.iter()
.map(|inference| Inference {
left: map(&inference.left),
right: map(&inference.right),
rule: inference.rule,
principal: inference.principal,
premises: inference.premises.iter().map(|&p| renumber(p)).collect(),
})
.collect();
let mut top = grafted.pop().expect("a derivation has a root");
let goal_inference = &self.inferences[at.index()];
if !same(&top.left, &goal_inference.left) || !same(&top.right, &goal_inference.right) {
return Err(Error::GoalMismatch);
}
top.principal = top.principal.map(|(side, position)| {
let id = top.side(side)[position];
let list = goal_inference.side(side);
(side, list.iter().position(|&y| y == id).unwrap_or(position))
});
top.left.clone_from(&goal_inference.left);
top.right.clone_from(&goal_inference.right);
self.inferences[at.index()] = top;
self.inferences.extend(grafted.into_iter().rev());
self.history.push(at);
Ok(())
}
fn first_steps(&self, goal: GoalId, found: &Derivation) -> Vec<Step> {
let mut state = self.clone();
let (mut goal, mut at) = (goal, found.root());
let mut steps = Vec::new();
while let Some(step) = state
.open(goal)
.ok()
.and_then(|inference| state.step_at(inference, found, at))
{
steps.push(step.clone());
if !step.rule.is_structural() {
break;
}
match state.apply(goal, &step).as_deref() {
Ok(&[next]) => goal = next,
_ => break,
}
at = found.inference(at).premises[0];
}
steps
}
fn step_at(&self, goal: &Inference, found: &Derivation, at: InfId) -> Option<Step> {
let mut formulas = self.formulas.clone();
let ids = Self::ids_of(&mut formulas, found.formulas()).ok()?;
let map = |list: &[NodeId]| list.iter().map(|k| ids[k.index()]).collect::<Vec<_>>();
let root = found.inference(at);
let Some((side, at)) = root.principal else {
return Some(Step::new(Side::Right, 0, root.rule));
};
let x = ids[root.side(side)[at].index()];
let position = goal.side(side).iter().position(|&y| y == x)?;
let step = Step::new(side, position, root.rule);
let Ok(Shape::Binary([first, _])) = self.shape(root.rule, side, position, x) else {
return Some(step);
};
let given = found.inference(root.premises[0]);
let (left, right) = (map(&given.left), map(&given.right));
let shared = premise(goal, side, position, &first.0, &first.1, |_, _| true);
if same(&shared.left, &left) && same(&shared.right, &right) {
return Some(step);
}
let mut rest = (left, right);
let (same_side, other_side) = match side {
Side::Left => (&mut rest.0, &mut rest.1),
Side::Right => (&mut rest.1, &mut rest.0),
};
for (list, added) in [(same_side, &first.0), (other_side, &first.1)] {
for y in added {
let i = list.iter().position(|z| z == y)?;
list.swap_remove(i);
}
}
let mut positions = (Vec::new(), Vec::new());
for (s, held, out) in [
(Side::Left, &mut rest.0, &mut positions.0),
(Side::Right, &mut rest.1, &mut positions.1),
] {
for (i, y) in goal.side(s).iter().enumerate() {
if s == side && i == position {
continue;
}
if let Some(k) = held.iter().position(|z| z == y) {
held.swap_remove(k);
out.push(i);
}
}
}
Some(step.split(&positions.0, &positions.1))
}
pub fn derivation(&self) -> Result<Derivation, Error> {
self.derivation_within(&ViewOptions::default(), &Limits::default(), |_| false)
}
pub fn derivation_within(
&self,
view: &ViewOptions,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Derivation, Error> {
let estimate = estimate(&self.formulas, &self.inferences);
if let Some(limit) = limits.derivation_bytes
&& estimate > limit
{
return Err(Error::Refused(Refusal::Output {
what: "derivation",
estimate_bytes: estimate,
limit_bytes: limit,
least_bytes: None,
}));
}
if stop(Progress::new(Phase::View, 0, 0)) {
return Err(Error::Refused(Refusal::Stopped { phase: Phase::View }));
}
let order = self.postorder();
let mut new_id = vec![InfId::new(u32::MAX); self.inferences.len()];
for (i, id) in order.iter().enumerate() {
new_id[id.index()] = InfId::new(i as u32);
}
let inferences = order
.iter()
.map(|id| {
let inference = &self.inferences[id.index()];
Inference {
premises: inference
.premises
.iter()
.map(|p| new_id[p.index()])
.collect(),
..inference.clone()
}
})
.collect();
let (left, right) = self.sequent();
let derivation = Derivation::from_parts(
self.logic,
self.formulas.clone(),
(left.to_vec(), right.to_vec()),
inferences,
);
Ok(match view.structural {
Structural::Explicit => derivation,
Structural::Admissible => derivation.admissible().0,
})
}
pub fn derivation_ids(&self, structural: Structural) -> Vec<GoalId> {
let order = self.postorder();
let goal = |id: InfId| GoalId::new(id.get());
match structural {
Structural::Explicit => order.into_iter().map(goal).collect(),
Structural::Admissible => {
let mut new_id = vec![InfId::new(0); self.inferences.len()];
for (i, id) in order.iter().enumerate() {
new_id[id.index()] = InfId::new(i as u32);
}
let shape: Vec<Inference> = order
.iter()
.map(|id| {
let inference = &self.inferences[id.index()];
Inference {
left: Vec::new(),
right: Vec::new(),
rule: inference.rule,
principal: None,
premises: inference
.premises
.iter()
.map(|p| new_id[p.index()])
.collect(),
}
})
.collect();
let skeleton = Derivation::from_parts(
self.logic,
Formulas::default(),
(Vec::new(), Vec::new()),
shape,
);
let (_, origin) = skeleton.admissible();
origin.into_iter().map(|i| goal(order[i.index()])).collect()
}
}
}
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 finished(
&self,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Derivation, Error> {
let open = self.goals().count();
if open > 0 {
return Err(Error::OpenGoals { count: open });
}
let view = ViewOptions::default().with_structural(Structural::Explicit);
let derivation = self.derivation_within(&view, limits, &mut stop)?;
derivation.check(limits, stop)?;
Ok(derivation)
}
}
fn formula_at(goal: &Inference, side: Side, position: usize) -> Result<NodeId, StepError> {
let list = goal.side(side);
list.get(position).copied().ok_or(StepError::NoFormula {
side,
position,
len: list.len(),
})
}
fn premise(
goal: &Inference,
side: Side,
position: usize,
same: &[NodeId],
other: &[NodeId],
keep: impl Fn(Side, usize) -> bool,
) -> Inference {
let mut sides = [Vec::new(), Vec::new()];
for (k, s) in [Side::Left, Side::Right].into_iter().enumerate() {
for (i, &y) in goal.side(s).iter().enumerate() {
if s == side && i == position {
sides[k].extend_from_slice(same);
} else if keep(s, i) {
sides[k].push(y);
}
}
}
let [mut left, mut right] = sides;
match side {
Side::Left => right.extend_from_slice(other),
Side::Right => left.extend_from_slice(other),
}
open(left, right)
}
fn contracted(
goal: &Inference,
position: usize,
rule: Rule,
first: &(Vec<NodeId>, Vec<NodeId>),
second: &(Vec<NodeId>, Vec<NodeId>),
) -> Vec<Inference> {
let mut made = Vec::with_capacity(goal.left.len() + 2);
let mut left = goal.left.clone();
let mut copies = vec![false; left.len()];
let mut k = 0;
for i in 0..goal.left.len() {
if i == position {
continue;
}
let at = i + k;
made.push(Inference {
left: left.clone(),
right: goal.right.clone(),
rule: Rule::ContractLeft,
principal: Some((Side::Left, at)),
premises: vec![InfId::new(made.len() as u32 + 1)],
});
left.insert(at + 1, left[at]);
copies.insert(at + 1, true);
k += 1;
}
let principal = (0..left.len())
.filter(|&j| !copies[j])
.nth(position)
.expect("the rule's formula is a hypothesis of the goal");
let contracted = open(left, goal.right.clone());
let n = made.len() as u32;
made.push(Inference {
left: contracted.left.clone(),
right: contracted.right.clone(),
rule,
principal: Some((Side::Left, principal)),
premises: vec![InfId::new(n + 1), InfId::new(n + 2)],
});
let to_first = |s: Side, j: usize| s == Side::Left && !copies[j];
let to_second = |s: Side, j: usize| s == Side::Right || copies[j];
made.push(premise(
&contracted,
Side::Left,
principal,
&first.0,
&first.1,
to_first,
));
made.push(premise(
&contracted,
Side::Left,
principal,
&second.0,
&second.1,
to_second,
));
made
}
fn axiom(goal: &Inference, side: Side, position: usize, partner: usize) -> Vec<Inference> {
let (mut keep_left, mut keep_right) = match side {
Side::Left => (position, partner),
Side::Right => (partner, position),
};
let (mut left, mut right) = (goal.left.clone(), goal.right.clone());
let mut made = Vec::with_capacity(left.len() + right.len() - 1);
let mut weaken =
|rule: Rule, s: Side, at: usize, left: &mut Vec<NodeId>, right: &mut Vec<NodeId>| {
let next = InfId::new(made.len() as u32 + 1);
made.push(Inference {
left: left.clone(),
right: right.clone(),
rule,
principal: Some((s, at)),
premises: vec![next],
});
match s {
Side::Left => left.remove(at),
Side::Right => right.remove(at),
};
};
for at in (0..left.len()).rev() {
if at != keep_left {
weaken(Rule::WeakenLeft, Side::Left, at, &mut left, &mut right);
keep_left -= usize::from(at < keep_left);
}
}
for at in (0..right.len()).rev() {
if at != keep_right {
weaken(Rule::WeakenRight, Side::Right, at, &mut left, &mut right);
keep_right -= usize::from(at < keep_right);
}
}
made.push(Inference {
left,
right,
rule: Rule::Axiom,
principal: None,
premises: Vec::new(),
});
made
}
fn estimate(formulas: &Formulas, inferences: &[Inference]) -> u64 {
let widths = super::derivation::widths(formulas);
inferences.iter().fold(0u64, |sum, inference| {
let bytes = super::derivation::inference_bytes(&widths, &inference.left, &inference.right);
sum.saturating_add(bytes)
})
}
#[cfg(feature = "serialize")]
pub(crate) struct Parts {
pub(crate) logic: Logic,
pub(crate) formulas: Formulas,
pub(crate) inferences: Vec<Inference>,
pub(crate) history: Vec<InfId>,
}
#[cfg(feature = "serialize")]
impl Interactive {
pub(crate) fn parts(&self) -> (Logic, &Formulas, &[Inference], &[InfId]) {
(self.logic, &self.formulas, &self.inferences, &self.history)
}
pub(crate) fn from_parts(parts: Parts, limits: &Limits) -> Result<Self, Error> {
let Parts {
logic,
mut formulas,
inferences,
history,
} = parts;
let inconsistent = |reason| Error::InconsistentSession { reason };
let root = inferences
.first()
.ok_or(inconsistent("the session has no inference"))?;
bound(&formulas, &root.left, &root.right, limits)?;
let falsity = Extra::add(&mut formulas)?.falsity;
let len = inferences.len();
let mut parents = vec![0u8; len];
for (n, inference) in inferences.iter().enumerate() {
for id in inference.left.iter().chain(&inference.right) {
formulas.holds(*id)?;
}
if let Some((side, at)) = inference.principal
&& at >= inference.side(side).len()
{
return Err(inconsistent(
"a principal position lies outside its sequent",
));
}
for p in &inference.premises {
if p.index() <= n || p.index() >= len {
return Err(inconsistent("a premise does not follow its conclusion"));
}
parents[p.index()] = parents[p.index()].saturating_add(1);
}
if inference.rule == Rule::Open {
let right = inference.right.len();
if inference.principal.is_some() || !inference.premises.is_empty() {
return Err(inconsistent("an open goal has a principal or premises"));
}
if logic != Logic::Classical && right != 1 {
return Err(inconsistent(
"an open goal of LJ must have exactly one formula right of ⊢",
));
}
continue;
}
let premises: Vec<&Inference> = inference
.premises
.iter()
.map(|p| &inferences[p.index()])
.collect();
if check_inference(&formulas, logic, inference, &premises).is_err() {
return Err(inconsistent("an inference breaks the rule it names"));
}
}
if parents[0] != 0 || parents[1..].iter().any(|&n| n != 1) {
return Err(inconsistent(
"an inference is not the premise of exactly one",
));
}
let mut end = len;
let mut named = vec![false; len];
for &goal in history.iter().rev() {
let g = goal.index();
if g >= end || named[g] || inferences[g].rule == Rule::Open {
return Err(inconsistent(
"a step names no inference it could have closed",
));
}
if logic != Logic::Classical && inferences[g].right.len() != 1 {
return Err(inconsistent(
"a step of LJ closed a goal that has no formula or several right of ⊢",
));
}
named[g] = true;
let mut added = 0;
let mut least = end;
let mut stack: Vec<InfId> = inferences[g].premises.clone();
while let Some(p) = stack.pop() {
if p.index() >= end {
continue;
}
added += 1;
least = least.min(p.index());
stack.extend(inferences[p.index()].premises.iter().copied());
}
if least != end - added || g >= end - added {
return Err(inconsistent("a step did not add the suffix of the arena"));
}
end -= added;
}
Ok(Self {
logic,
formulas,
falsity,
inferences,
history,
limit: limits.derivation_bytes,
})
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::search::generate::Rng;
use Side::{Left, Right};
fn start(text: &str, logic: Logic) -> (Interactive, GoalId) {
let sequent: Sequent = text.parse().unwrap();
let state = Interactive::new(&sequent, logic).unwrap();
let goal = state.goals().next().unwrap();
(state, goal)
}
fn at(state: &Interactive, goal: GoalId, side: Side, text: &str) -> usize {
let (left, right) = state.goal(goal).unwrap();
let list = if side == Left { left } else { right };
list.iter()
.position(|&k| state.formulas().formula(k).to_string() == text)
.unwrap_or_else(|| panic!("no {text} {side:?} in goal {}", goal.get()))
}
fn step(
state: &mut Interactive,
goal: GoalId,
(side, text): (Side, &str),
rule: Rule,
first: Option<(&[&str], &[&str])>,
) -> Vec<GoalId> {
let mut step = Step::new(side, at(state, goal, side, text), rule);
if let Some((left, right)) = first {
let left: Vec<usize> = left.iter().map(|t| at(state, goal, Left, t)).collect();
let right: Vec<usize> = right.iter().map(|t| at(state, goal, Right, t)).collect();
step = step.split(&left, &right);
}
state
.apply(goal, &step)
.unwrap_or_else(|e| panic!("{rule} on {text}: {e}"))
}
fn axiom(state: &mut Interactive, goal: GoalId, text: &str) {
assert_eq!(step(state, goal, (Right, text), Rule::Axiom, None), []);
}
#[test]
fn a_finished_state_checks() {
let finished = |s: &Interactive| {
assert!(s.is_complete());
s.finished(&Limits::default(), |_| false).unwrap()
};
for logic in [Logic::Intuitionistic, Logic::Minimal] {
let (mut s, g) = start("a /\\ b |- b /\\ a", logic);
let [g] = step(&mut s, g, (Left, "a ∧ b"), Rule::AndLeft, None)[..] else {
panic!()
};
for (g, text) in step(&mut s, g, (Right, "b ∧ a"), Rule::AndRight, None)
.into_iter()
.zip(["b", "a"])
{
axiom(&mut s, g, text);
}
finished(&s);
let (mut s, g) = start("a -> b, a |- b", logic);
let first: &[&str] = &["a"];
let [p, q] = step(
&mut s,
g,
(Left, "a → b"),
Rule::ImpliesLeft,
Some((first, &[])),
)[..] else {
panic!()
};
axiom(&mut s, p, "a");
axiom(&mut s, q, "b");
finished(&s);
let (mut s, g) = start("a |- ~~a", logic);
let [g] = step(&mut s, g, (Right, "¬¬a"), Rule::NotRight, None)[..] else {
panic!()
};
let [p, q] = step(&mut s, g, (Left, "¬a"), Rule::NotLeft, Some((first, &[])))[..]
else {
panic!()
};
axiom(&mut s, p, "a");
axiom(&mut s, q, "⊥");
let derivation = finished(&s);
assert_eq!(derivation.sequent().1.len(), 1);
}
let k = Logic::Classical;
let (mut s, g) = start("|- a \\/ ~a", k);
let [g] = step(&mut s, g, (Right, "a ∨ ¬a"), Rule::OrRight, None)[..] else {
panic!()
};
let [g] = step(&mut s, g, (Right, "¬a"), Rule::NotRight, None)[..] else {
panic!()
};
assert_eq!(s.goal(g).unwrap().0.len(), 1);
axiom(&mut s, g, "a");
finished(&s);
let (mut s, g) = start("|- ((a -> b) -> a) -> a", k);
let [g] = step(
&mut s,
g,
(Right, "((a → b) → a) → a"),
Rule::ImpliesRight,
None,
)[..] else {
panic!()
};
let [p, q] = step(&mut s, g, (Left, "(a → b) → a"), Rule::ImpliesLeft, None)[..] else {
panic!()
};
let [p] = step(&mut s, p, (Right, "a → b"), Rule::ImpliesRight, None)[..] else {
panic!()
};
axiom(&mut s, p, "a");
axiom(&mut s, q, "a");
finished(&s);
let (mut s, g) = start("a <-> b, b |- a", k);
let [g] = step(&mut s, g, (Left, "a ↔ b"), Rule::IffLeft2, None)[..] else {
panic!()
};
let [g] = step(&mut s, g, (Left, "b"), Rule::ContractLeft, None)[..] else {
panic!()
};
let [p, q] = step(
&mut s,
g,
(Left, "b → a"),
Rule::ImpliesLeft,
Some((&["b"], &[])),
)[..] else {
panic!()
};
axiom(&mut s, p, "b");
axiom(&mut s, q, "a");
finished(&s);
}
#[test]
fn structural_rules_explicit_or_admissible() {
let (mut s, g) = start("a -> b, a, c |- b", Logic::Intuitionistic);
let [g] = step(&mut s, g, (Left, "a"), Rule::ContractLeft, None)[..] else {
panic!()
};
let first: &[&str] = &["a"];
let [p, q] = step(
&mut s,
g,
(Left, "a → b"),
Rule::ImpliesLeft,
Some((first, &[])),
)[..] else {
panic!()
};
axiom(&mut s, p, "a");
axiom(&mut s, q, "b");
let view = |structural| {
let view = ViewOptions::default().with_structural(structural);
let derivation = s
.derivation_within(&view, &Limits::default(), |_| false)
.unwrap();
(derivation.to_string(), s.derivation_ids(structural))
};
let (explicit, ids) = view(Structural::Explicit);
assert_eq!(
explicit,
" ───── ax\n\
\x20 b ⊢ b\n\
\x20 ──────── WL\n\
\x20 b, a ⊢ b\n\
───── ax ─────────── WL\n\
a ⊢ a b, a, c ⊢ b\n\
────────────────────── →L\n\
\x20 a → b, a, a, c ⊢ b\n\
\x20 ────────────────── CL\n\
\x20 a → b, a, c ⊢ b"
);
assert_eq!(ids.len(), 6);
let (admissible, ids) = view(Structural::Admissible);
assert_eq!(
admissible,
"───── ax ─────────── ax\n\
a ⊢ a b, a, c ⊢ b\n\
────────────────────── →L\n\
\x20 a → b, a, c ⊢ b"
);
assert_eq!(ids.len(), 3);
assert_eq!(s.inferences[ids[2].index()].rule, Rule::ImpliesLeft);
let (mut s, g) = start("a, c |- a", Logic::Intuitionistic);
step(&mut s, g, (Left, "c"), Rule::WeakenLeft, None);
let view = ViewOptions::default().with_structural(Structural::Admissible);
let shown = s
.derivation_within(&view, &Limits::default(), |_| false)
.unwrap();
assert_eq!(shown.to_string(), " a ⊢ a\n──────── WL\na, c ⊢ a");
}
#[test]
fn a_shared_implication_left_checks() {
for logic in [Logic::Intuitionistic, Logic::Minimal] {
let (mut s, g) = start("c, a -> b, a |- b", logic);
let [p, q] = step(&mut s, g, (Left, "a → b"), Rule::ImpliesLeft, None)[..] else {
panic!()
};
let text = |s: &Interactive, g| {
let (left, right) = s.goal(g).unwrap();
let side = |list: &[NodeId]| -> Vec<String> {
list.iter()
.map(|&k| s.formulas().formula(k).to_string())
.collect()
};
(side(left), side(right))
};
assert_eq!(
text(&s, p),
(vec!["c".into(), "a".into()], vec!["a".into()])
);
assert_eq!(
text(&s, q),
(vec!["c".into(), "b".into(), "a".into()], vec!["b".into()])
);
axiom(&mut s, p, "a");
axiom(&mut s, q, "b");
let derivation = s.finished(&Limits::default(), |_| false).unwrap();
let contractions = derivation
.inferences()
.iter()
.filter(|i| i.rule() == Rule::ContractLeft)
.count();
assert_eq!(contractions, 2);
let shown = s.derivation().unwrap().to_string();
assert_eq!(
shown,
"──────── ax ─────────── ax\n\
c, a ⊢ a c, b, a ⊢ b\n\
───────────────────────── →L\n\
\x20 c, a → b, a ⊢ b"
);
assert_eq!(s.undo(), Some(q));
}
}
#[test]
fn undo_restores() {
let (mut s, g) = start("a /\\ b, c |- b /\\ a", Logic::Intuitionistic);
let parts = |s: &Interactive| (s.inferences.clone(), s.history.clone());
let before = parts(&s);
let [h] = step(&mut s, g, (Left, "a ∧ b"), Rule::AndLeft, None)[..] else {
panic!()
};
let middle = parts(&s);
let goals = step(&mut s, h, (Right, "b ∧ a"), Rule::AndRight, None);
axiom(&mut s, goals[0], "b");
let closed = s
.close(
goals[1],
None,
&search::Options::default(),
&Limits::default(),
|_| false,
)
.unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Valid(_)) && closed.grafted.is_ok());
assert!(s.is_complete());
assert_eq!(s.steps(), 4);
for _ in 0..3 {
s.undo();
}
assert_eq!(parts(&s), middle);
assert_eq!(s.undo(), Some(g));
assert_eq!(parts(&s), before);
assert_eq!(s.undo(), None);
}
#[test]
fn a_rule_that_does_not_fit_is_refused_with_why() {
let (mut s, g) = start("a /\\ b, a -> c |- c \\/ a", Logic::Intuitionistic);
let before = (s.inferences.clone(), s.history.clone());
let refused = |s: &mut Interactive, step: Step| s.apply(g, &step).unwrap_err();
let error = refused(&mut s, Step::new(Left, 0, Rule::AndRight));
assert_eq!(
error,
StepError::Rule {
rule: Rule::AndRight,
side: Left,
position: 0
}
);
assert_eq!(
error.to_string(),
"the rule ∧R does not act on formula 0 left of ⊢: it acts on a conjunction right of ⊢"
);
let error = refused(&mut s, Step::new(Right, 0, Rule::OrRight));
assert_eq!(
error.to_string(),
"the rule ∨R is not available in intuitionistic logic: its premise would have both \
disjuncts right of ⊢, and every goal of LJ has exactly one formula there: use ∨R₁ \
or ∨R₂ to keep one disjunct"
);
let error = refused(
&mut s,
Step::new(Left, 1, Rule::ImpliesLeft).split(&[], &[0]),
);
assert_eq!(error, StepError::Succedents { count: 2 });
assert!(
error
.to_string()
.starts_with("a premise would have 2 formulas right of ⊢")
);
assert_eq!(
refused(&mut s, Step::new(Left, 0, Rule::Axiom)).to_string(),
"the axiom needs formula 0 left of ⊢ to stand right of ⊢ too"
);
assert_eq!(
refused(
&mut s,
Step::new(Left, 1, Rule::ImpliesLeft).split(&[1], &[])
),
StepError::Split {
side: Left,
position: 1
}
);
assert_eq!(
refused(&mut s, Step::new(Left, 0, Rule::AndLeft).split(&[1], &[])),
StepError::NoSplit {
rule: Rule::AndLeft
}
);
assert_eq!(
refused(&mut s, Step::new(Right, 3, Rule::OrRight1)).to_string(),
"the goal has no formula 3 right of ⊢: it has 1 formula there, and positions start at 0"
);
assert_eq!(
s.apply(GoalId::new(9), &Step::new(Left, 0, Rule::AndLeft)),
Err(StepError::NoGoal {
goal: GoalId::new(9)
})
);
assert_eq!((s.inferences.clone(), s.history.clone()), before);
let (mut s, g) = start("false |- a", Logic::Minimal);
assert_eq!(
s.apply(g, &Step::new(Left, 0, Rule::FalseLeft))
.unwrap_err()
.to_string(),
"the rule ⊥L is not available in minimal logic: minimal logic has no ex falso"
);
let rules = |s: &Interactive, side, position| -> Vec<Rule> {
s.rules(g, side, position)
.unwrap()
.into_iter()
.map(|a| a.rule)
.collect()
};
assert_eq!(rules(&s, Left, 0), [Rule::WeakenLeft, Rule::ContractLeft]);
let (s, g) = start("a -> b, a |- b", Logic::Intuitionistic);
let applicable = s.rules(g, Left, 0).unwrap();
assert_eq!(
applicable,
[
Applicable {
rule: Rule::WeakenLeft,
needs: Needs::Nothing
},
Applicable {
rule: Rule::ContractLeft,
needs: Needs::Nothing
},
Applicable {
rule: Rule::ImpliesLeft,
needs: Needs::Context
},
]
);
let (s, g) = start("a -> b, a |- a", Logic::Intuitionistic);
assert_eq!(s.rules(g, Left, 1).unwrap()[0].rule, Rule::Axiom);
}
#[test]
fn close_and_hint() {
let options = search::Options::default();
let limits = Limits::default();
let (mut s, g) = start("a -> b, b -> c |- a -> c", Logic::Intuitionistic);
let hint = s.hint(g, None, &options, &limits, |_| false).unwrap();
let [step] = &hint.steps[..] else {
panic!("{:?}", hint.steps)
};
assert_eq!((step.side, step.rule), (Right, Rule::ImpliesRight));
let [g] = s.apply(g, step).unwrap()[..] else {
panic!()
};
let hint = s.hint(g, None, &options, &limits, |_| false).unwrap();
let [step] = &hint.steps[..] else {
panic!("{:?}", hint.steps)
};
assert_eq!(step.rule, Rule::ImpliesLeft);
assert!(matches!(step.context, Context::Split { .. }));
s.apply(g, step).unwrap();
for goal in s.goals().collect::<Vec<_>>() {
let closed = s.close(goal, None, &options, &limits, |_| false).unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Valid(_)));
}
s.finished(&limits, |_| false).unwrap();
let (mut s, g) = start("|- ~~(a \\/ ~a)", Logic::Intuitionistic);
let one = options.clone().with_copies(Some(1));
let closed = s.close(g, None, &one, &limits, |_| false).unwrap();
let Verdict::Unknown(reason) = closed.outcome.verdict else {
panic!("{:?}", closed.outcome.verdict)
};
assert_eq!(reason, search::Reason::CopyBound { copies: 1 });
assert_eq!(s.goals().collect::<Vec<_>>(), [g]);
assert_eq!(s.hint(g, None, &one, &limits, |_| false).unwrap().steps, []);
let (mut s, g) = start("|- ((a -> b) -> a) -> a", Logic::Intuitionistic);
let closed = s.close(g, None, &options, &limits, |_| false).unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::NotValid));
assert_eq!(s.steps(), 0);
}
#[test]
fn following_the_hints_proves_a_sequent() {
let options = search::Options::default().with_copies(None);
let limits = Limits::default();
for (text, logic) in [
(
"a /\\ (b \\/ c) |- (a /\\ b) \\/ (a /\\ c)",
Logic::Intuitionistic,
),
("|- ~~(a \\/ ~a)", Logic::Intuitionistic),
("|- ~~(a \\/ ~a)", Logic::Minimal),
("(a -> b) -> a, a -> b |- b", Logic::Intuitionistic),
] {
let (mut s, _) = start(text, logic);
for _ in 0..50 {
let Some(goal) = s.goals().next() else { break };
let hint = s.hint(goal, None, &options, &limits, |_| false).unwrap();
let mut goal = goal;
for step in &hint.steps {
let opened = s.apply(goal, step).unwrap();
if let [next, ..] = opened[..] {
goal = next;
}
}
assert!(!hint.steps.is_empty(), "{text}");
}
assert!(s.is_complete(), "{text}");
s.finished(&limits, |_| false).unwrap();
}
}
#[test]
fn the_bounds_hold() {
let sequent: Sequent = "a /\\ b |- b /\\ a".parse().unwrap();
let at = |n| Limits::default().with_occurrences(Some(n));
assert!(Interactive::within(&sequent, Logic::Classical, &at(6)).is_ok());
assert!(matches!(
Interactive::within(&sequent, Logic::Classical, &at(5)),
Err(Error::Refused(Refusal::Occurrences {
occurrences: 6,
limit: 5
}))
));
let s = Interactive::new(&sequent, Logic::Classical).unwrap();
let view = ViewOptions::default();
let small = Limits::default().with_derivation_bytes(Some(100));
assert!(matches!(
s.derivation_within(&view, &small, |_| false),
Err(Error::Refused(Refusal::Output { .. }))
));
assert!(matches!(
s.derivation_within(&view, &Limits::default(), |_| true),
Err(Error::Refused(Refusal::Stopped { .. }))
));
let mut s = s;
let g = s.goals().next().unwrap();
let stopped = s
.close(
g,
None,
&search::Options::default(),
&Limits::default(),
|_| true,
)
.unwrap();
assert!(matches!(
stopped.outcome.verdict,
Verdict::Unknown(search::Reason::Stopped)
));
assert_eq!(s.goals().count(), 1);
assert!(matches!(
s.finished(&Limits::default(), |_| false),
Err(Error::OpenGoals { count: 1 })
));
let hypotheses: Vec<String> = (0..200).map(|i| format!("p{i}")).collect();
let text = format!("a -> b, {}, a |- b", hypotheses.join(", "));
let sequent: Sequent = text.parse().unwrap();
let small = Limits::default().with_derivation_bytes(Some(1 << 20));
let mut s = Interactive::within(&sequent, Logic::Intuitionistic, &small).unwrap();
let g = s.goals().next().unwrap();
let refused = s.apply(g, &Step::new(Left, 0, Rule::ImpliesLeft));
assert!(matches!(
refused,
Err(StepError::Size {
limit_bytes: 1_048_576,
..
})
));
assert_eq!(s.steps(), 0);
let mut s = Interactive::new(&sequent, Logic::Intuitionistic).unwrap();
assert_eq!(
s.apply(g, &Step::new(Left, 0, Rule::ImpliesLeft))
.map(|g| g.len()),
Ok(2)
);
}
#[test]
fn random_steps_finish_as_checked_derivations() {
const SEQUENTS: usize = 60;
let search = search::Options::default().with_copies(Some(4));
let limits = Limits::default().with_work(Some(20_000));
let mut rng = Rng::new(49);
let mut finished = 0;
for _ in 0..SEQUENTS {
let sequent = super::super::tests::generated_sequent(&mut rng);
for &logic in Logic::ALL {
let Ok(mut s) = Interactive::new(&sequent, logic) else {
continue;
};
for _ in 0..12 {
if rng.one_in(6) {
s.undo();
continue;
}
let goals: Vec<GoalId> = s.goals().collect();
let Some(&goal) = goals.get(rng.below(goals.len().max(1))) else {
break;
};
let (left, right) = s.goal(goal).unwrap();
let (nl, nr) = (left.len(), right.len());
if nl + nr == 0 {
break;
}
let k = rng.below(nl + nr);
let (side, position) = if k < nl { (Left, k) } else { (Right, k - nl) };
let rules = s.rules(goal, side, position).unwrap();
let Some(applicable) = rules.get(rng.below(rules.len().max(1))) else {
continue;
};
let mut step = Step::new(side, position, applicable.rule);
if applicable.needs == Needs::Context && rng.one_in(2) {
let pick = |n: usize, rng: &mut Rng, s: Side| -> Vec<usize> {
(0..n)
.filter(|&i| !(s == side && i == position) && rng.one_in(2))
.collect()
};
let first = (pick(nl, &mut rng, Left), pick(nr, &mut rng, Right));
step = step.split(&first.0, &first.1);
}
let _ = s.apply(goal, &step);
}
#[cfg(feature = "serialize")]
{
let json = serde_json::to_string(&s).unwrap();
let mut document = serde_json::Deserializer::from_str(&json);
let read: Interactive = crate::wire::upgrade(&mut document, &limits)
.unwrap_or_else(|e| panic!("{sequent} in {logic}: {e}\n{json}"));
assert_eq!(serde_json::to_string(&read).unwrap(), json);
}
let goals: Vec<GoalId> = s.goals().collect();
let proved = goals.into_iter().all(|goal| {
s.close(goal, None, &search, &limits, |_| false)
.is_ok_and(|c| matches!(c.outcome.verdict, Verdict::Valid(_)))
});
if proved {
s.finished(&Limits::default(), |_| false)
.unwrap_or_else(|e| panic!("{sequent} in {logic}: {e}"));
finished += 1;
}
}
}
assert!(finished >= SEQUENTS / 4, "{finished} states finished");
}
#[cfg(feature = "serialize")]
#[test]
fn a_forged_document_is_refused() {
let read = |json: &str| {
let mut document = serde_json::Deserializer::from_str(json);
crate::wire::upgrade::<Interactive, _>(&mut document, &Limits::default()).map(|_| ())
};
let session = r#"{"version":8,"logic":"intuitionistic","sequent":{"formulas":[{"V":0},{"V":1},{"→":[0,1]},"⊥"],"atoms":["a","b"],"left":[2,0],"right":[1]},"inferences":[{"left":[2,0],"right":[1],"rule":"→L","principal":["left",0],"premises":[1,2]},{"left":[0],"right":[0],"rule":"ax"},{"left":[1],"right":[1]}],"history":[0,1]}"#;
assert_eq!(read(session), Ok(()));
let inconsistent =
|json: &str| matches!(read(json), Err(Error::InconsistentSession { .. }));
assert!(inconsistent(
&session.replace(r#""rule":"ax""#, r#""rule":"⊤R""#)
));
assert!(inconsistent(&session.replace(
r#""left":[0],"right":[0]"#,
r#""left":[1],"right":[1]"#
)));
assert!(inconsistent(
&session.replace(r#""history":[0,1]"#, r#""history":[1,0]"#)
));
let derivation = r#"{"version":8,"logic":"classical","sequent":{"formulas":[{"V":0}],"atoms":["a"],"left":[0],"right":[0]},"inferences":[{"left":[0],"right":[0],"rule":"ax"},{"left":[0],"right":[0],"rule":"ax"}]}"#;
let derivation_of = |json: &str| {
let mut document = serde_json::Deserializer::from_str(json);
crate::wire::upgrade::<Derivation, _>(&mut document, &Limits::default())
};
assert!(matches!(derivation_of(derivation), Err(Error::Json { .. })));
let open = r#"{"version":8,"logic":"classical","sequent":{"formulas":[{"V":0},{"V":1}],"atoms":["a","b"],"left":[1],"right":[1]},"inferences":[{"left":[1],"right":[1],"rule":"ax"},{"left":[1],"right":[1],"rule":"open","premises":[0]}]}"#;
assert!(matches!(derivation_of(open), Err(Error::Json { .. })));
let empty = r#"{"version":8,"logic":"intuitionistic","sequent":{"formulas":[{"V":0},{"V":1},{"¬":0}],"atoms":["a","b"],"left":[0,2],"right":[1]},"inferences":[{"left":[0,2],"right":[1],"rule":"WR","principal":["right",0],"premises":[1]},{"left":[0,2],"right":[],"rule":"¬L","principal":["left",1],"premises":[2]},{"left":[0],"right":[0],"rule":"ax"}],"history":[0,1,2]}"#;
assert!(inconsistent(empty));
let arrow = r#"{"version":8,"logic":"classical","sequent":{"formulas":[{"V":0},"⊥",{"¬":0}],"atoms":["a"],"left":[1],"right":[2]},"inferences":[{"left":[1],"right":[1],"rule":"ax"},{"left":[1,0],"right":[1],"rule":"WL","principal":["left",1],"premises":[0]},{"left":[1],"right":[2],"rule":"¬R","principal":["right",0],"premises":[1]}]}"#;
let arrow = derivation_of(arrow).unwrap();
assert!(matches!(
arrow.check(&Limits::default(), |_| false),
Err(Error::ReadBack { .. })
));
#[cfg(feature = "rocq")]
{
let mut out = String::new();
let options = crate::export::rocq::Options::default();
let written = crate::export::rocq::write(&arrow, &options, &mut out, |_| false);
assert!(written.is_err());
}
let lacking = r#"{"version":8,"logic":"classical","sequent":{"formulas":[{"V":0},{"V":1},"⊤"],"atoms":["a","b"],"left":[],"right":[1,1]},"inferences":[{"left":[],"right":[0,2],"rule":"⊤R","principal":["right",1]},{"left":[],"right":[1],"rule":"WR","principal":["right",0],"premises":[0]},{"left":[],"right":[1,1],"rule":"WR","principal":["right",0],"premises":[1]}]}"#;
let lacking = derivation_of(lacking).unwrap();
assert_eq!(lacking.shown(Structural::Admissible).inferences().len(), 2);
}
}