#![cfg_attr(feature = "parse", doc = "```")]
#![cfg_attr(not(feature = "parse"), doc = "```ignore")]
use super::{
Derivation, Evidence, Formulas, Inference, Logic, Node, NodeId, Rule, Sequent, Side, Verdict,
};
use crate::Error;
use crate::hash::{HashMap, HashSet};
use crate::limits::{Limits, Phase, Progress, Refusal, Space};
use crate::linear::proofs::InfId;
use crate::linear::search::Reason;
use crate::linear::search::memory::Account;
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Outcome {
pub verdict: Verdict,
pub logic: Logic,
pub statistics: Statistics,
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serialize", serde(default))]
pub struct Statistics {
pub sequents: u64,
pub memo_hits: u64,
pub memo_entries: u64,
pub subsumed: u64,
}
pub const POLL: u64 = 1 << 8;
const SUBSUMING: usize = 1 << 10;
pub fn decide(
sequent: &Sequent,
logic: Logic,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Outcome, Error> {
run(sequent, logic, limits, stop, None)
}
fn run(
sequent: &Sequent,
logic: Logic,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
plant: Option<Plant>,
) -> Result<Outcome, Error> {
if logic == Logic::Classical {
return Err(Error::Logic {
logic,
method: super::Method::Ljt,
});
}
if sequent.right().len() > 1 {
return Err(Error::Succedents {
count: sequent.right().len(),
});
}
let mut formulas = sequent.formulas().clone();
let falsity = formulas.add(Node::False)?;
let goal = sequent.right().first().copied().unwrap_or(falsity);
let mut search = Search {
formulas,
falsity,
logic,
account: Account::holding(limits.memory_bytes, 0),
memo: HashMap::default(),
failed: HashMap::default(),
steps: Vec::new(),
statistics: Statistics::default(),
work: limits.work.unwrap_or(u64::MAX),
unpolled: 0,
asked: 0,
};
let found = search.prove((set(sequent.left()), goal), &mut stop);
search.statistics.memo_entries = search.memo.len() as u64;
let statistics = search.statistics;
let verdict = match found {
Err(reason) => Verdict::Unknown(reason),
Ok(Known::Failed) => Verdict::NotValid,
Ok(Known::Proved(root)) => {
let mut lj = Lj::new(&search, limits, &mut stop);
lj.plant = plant;
let derivation = lj.translate(root, sequent.left(), goal)?;
derivation.check(limits, &mut stop)?;
Verdict::Valid(Evidence::Derivation(Box::new(derivation)))
}
};
Ok(Outcome {
verdict,
logic,
statistics,
})
}
fn set(left: &[NodeId]) -> Box<[NodeId]> {
let mut left = left.to_vec();
left.sort_unstable();
left.dedup();
left.into_boxed_slice()
}
type Key = (Box<[NodeId]>, NodeId);
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Kind {
Axiom,
FalseLeft,
TrueRight,
AndLeft,
IffLeft,
ImpliesRight,
AndRight,
IffRight,
OrLeft,
OrRight1,
OrRight2,
ModusPonens,
TrueImplies,
AndImplies,
IffImplies,
OrImplies,
ImpliesImplies,
}
#[derive(Clone, Copy, Debug)]
struct Move {
kind: Kind,
principal: NodeId,
}
#[derive(Debug)]
struct Step {
key: Key,
applied: Move,
premises: Vec<u32>,
}
#[derive(Clone, Copy, Debug)]
enum Known {
Proved(u32),
Failed,
}
#[derive(Debug)]
struct Frame {
key: Key,
moves: Vec<Move>,
at: usize,
premises: Option<Vec<Key>>,
proved: Vec<u32>,
}
struct Search {
formulas: Formulas,
falsity: NodeId,
logic: Logic,
account: Account,
memo: HashMap<Key, Known>,
failed: HashMap<NodeId, Vec<Box<[NodeId]>>>,
steps: Vec<Step>,
statistics: Statistics,
work: u64,
unpolled: u64,
asked: u64,
}
const fn bytes(len: usize) -> usize {
2 * (size_of::<Key>() + size_of::<Known>() + len * size_of::<NodeId>())
}
const fn frame_bytes(frame: &Frame) -> usize {
size_of::<Frame>() + bytes(frame.key.0.len()) + frame.moves.len() * size_of::<Move>()
}
impl Search {
fn implication(&mut self, a: NodeId, c: NodeId) -> Result<NodeId, Reason> {
let node = if c == self.falsity {
Node::Not(a)
} else {
Node::Implies(a, c)
};
self.add(node)
}
fn implication_of(&self, a: NodeId, c: NodeId) -> NodeId {
let node = if c == self.falsity {
Node::Not(a)
} else {
Node::Implies(a, c)
};
self.formulas
.find(node)
.unwrap_or_else(|| unreachable!("the search added it"))
}
fn add(&mut self, node: Node) -> Result<NodeId, Reason> {
let before = self.formulas.len();
let id = self.formulas.add(node).map_err(|_| Reason::IndexLimit)?;
if self.formulas.len() > before {
self.account.charge(4 * size_of::<Node>());
}
Ok(id)
}
fn split(&self, id: NodeId) -> Option<(NodeId, NodeId)> {
match self.formulas.node(id) {
Node::Implies(a, c) => Some((a, c)),
Node::Not(a) => Some((a, self.falsity)),
Node::Atom(_)
| Node::True
| Node::False
| Node::And(..)
| Node::Or(..)
| Node::Iff(..) => None,
}
}
fn moves(&self, (left, goal): (&[NodeId], NodeId)) -> Vec<Move> {
let one = |kind, principal| vec![Move { kind, principal }];
let f = &self.formulas;
let has = |x: NodeId| left.binary_search(&x).is_ok();
if has(goal) {
return one(Kind::Axiom, goal);
}
if self.logic == Logic::Intuitionistic && has(self.falsity) {
return one(Kind::FalseLeft, self.falsity);
}
let node = f.node(goal);
match node {
Node::True => return one(Kind::TrueRight, goal),
Node::Implies(..) | Node::Not(_) => return one(Kind::ImpliesRight, goal),
Node::Atom(_) | Node::False | Node::And(..) | Node::Or(..) | Node::Iff(..) => {}
}
for &h in left {
let kind = match f.node(h) {
Node::And(..) => Some(Kind::AndLeft),
Node::Iff(..) => Some(Kind::IffLeft),
Node::Atom(_) | Node::True | Node::False | Node::Or(..) => None,
Node::Implies(a, _) | Node::Not(a) => match f.node(a) {
_ if has(a) => Some(Kind::ModusPonens),
Node::True => Some(Kind::TrueImplies),
Node::And(..) => Some(Kind::AndImplies),
Node::Iff(..) => Some(Kind::IffImplies),
Node::Or(..) => Some(Kind::OrImplies),
Node::Atom(_) | Node::False | Node::Implies(..) | Node::Not(_) => None,
},
};
if let Some(kind) = kind {
return one(kind, h);
}
}
match node {
Node::And(..) => return one(Kind::AndRight, goal),
Node::Iff(..) => return one(Kind::IffRight, goal),
Node::Atom(_)
| Node::True
| Node::False
| Node::Not(_)
| Node::Or(..)
| Node::Implies(..) => {}
}
if let Some(&h) = left.iter().find(|&&h| matches!(f.node(h), Node::Or(..))) {
return one(Kind::OrLeft, h);
}
let mut moves = Vec::new();
if let Node::Or(..) = node {
for kind in [Kind::OrRight1, Kind::OrRight2] {
moves.push(Move {
kind,
principal: goal,
});
}
}
let mut implications: Vec<NodeId> = left
.iter()
.copied()
.filter(|&h| self.split(h).is_some_and(|(a, _)| self.split(a).is_some()))
.collect();
if implications.len() > 1 {
let levels = self.levels(left, goal);
let rank = |h: NodeId| {
let (_, c) = self.split(h).unwrap_or((h, h));
let mut heads = Vec::new();
self.heads(c, &mut heads);
heads
.iter()
.filter_map(|x| levels.get(x))
.min()
.copied()
.unwrap_or(u32::MAX)
};
implications.sort_by_cached_key(|&h| rank(h));
}
moves.extend(implications.into_iter().map(|principal| Move {
kind: Kind::ImpliesImplies,
principal,
}));
moves
}
fn heads(&self, x: NodeId, heads: &mut Vec<NodeId>) {
let mut seen: HashSet<NodeId> = HashSet::default();
let mut stack = vec![x];
while let Some(x) = stack.pop() {
if !seen.insert(x) {
continue;
}
match self.formulas.node(x) {
Node::Atom(_) | Node::False => heads.push(x),
Node::True => {}
Node::Not(_) => heads.push(self.falsity),
Node::Implies(_, c) => stack.push(c),
Node::And(a, b) | Node::Or(a, b) | Node::Iff(a, b) => stack.extend([a, b]),
}
}
}
fn levels(&self, left: &[NodeId], goal: NodeId) -> HashMap<NodeId, u32> {
let mut levels: HashMap<NodeId, u32> = HashMap::default();
let mut heads = Vec::new();
self.heads(goal, &mut heads);
levels.extend(heads.drain(..).map(|x| (x, 0)));
for _ in 0..left.len() {
let mut changed = false;
for &h in left {
let Some((a, c)) = self.split(h) else {
continue;
};
self.heads(c, &mut heads);
let near = heads
.drain(..)
.filter_map(|x| levels.get(&x))
.min()
.copied();
let Some(near) = near else { continue };
self.heads(a, &mut heads);
for x in heads.drain(..) {
let level = levels.entry(x).or_insert(u32::MAX);
if near + 1 < *level {
*level = near + 1;
changed = true;
}
}
}
if !changed {
break;
}
}
levels
}
fn premises(&mut self, (left, goal): (&[NodeId], NodeId), m: Move) -> Result<Vec<Key>, Reason> {
let p = m.principal;
let without = |added: &[NodeId]| {
let mut list: Vec<NodeId> = left.iter().copied().filter(|&x| x != p).collect();
list.extend_from_slice(added);
set(&list)
};
let (a, b) = match self.formulas.node(p).operands() {
(Some(a), Some(b)) => (a, b),
(Some(a), None) => (a, self.falsity),
(None, _) => (p, p),
};
Ok(match m.kind {
Kind::Axiom | Kind::FalseLeft | Kind::TrueRight => Vec::new(),
Kind::AndLeft => vec![(without(&[a, b]), goal)],
Kind::IffLeft => {
let (x, y) = (
self.add(Node::Implies(a, b))?,
self.add(Node::Implies(b, a))?,
);
vec![(without(&[x, y]), goal)]
}
Kind::ImpliesRight => {
let mut list = left.to_vec();
list.push(a);
vec![(set(&list), b)]
}
Kind::AndRight => vec![(left.into(), a), (left.into(), b)],
Kind::IffRight => {
let (x, y) = (
self.add(Node::Implies(a, b))?,
self.add(Node::Implies(b, a))?,
);
vec![(left.into(), x), (left.into(), y)]
}
Kind::OrLeft => vec![(without(&[a]), goal), (without(&[b]), goal)],
Kind::OrRight1 => vec![(left.into(), a)],
Kind::OrRight2 => vec![(left.into(), b)],
Kind::ModusPonens | Kind::TrueImplies => vec![(without(&[b]), goal)],
Kind::AndImplies | Kind::IffImplies | Kind::OrImplies => {
vec![(without(&self.made(m.kind, a, b)?), goal)]
}
Kind::ImpliesImplies => {
let made = self.made(m.kind, a, b)?;
vec![(without(&[b]), goal), (without(&made), a)]
}
})
}
fn made(&mut self, kind: Kind, antecedent: NodeId, c: NodeId) -> Result<Vec<NodeId>, Reason> {
let (x, y) = match self.formulas.node(antecedent).operands() {
(Some(x), Some(y)) => (x, y),
(Some(x), None) => (x, self.falsity),
(None, _) => (antecedent, antecedent),
};
Ok(match kind {
Kind::IffImplies => {
let (forward, backward) = (
self.add(Node::Implies(x, y))?,
self.add(Node::Implies(y, x))?,
);
let inner = self.implication(backward, c)?;
vec![self.implication(forward, inner)?]
}
Kind::OrImplies => vec![self.implication(x, c)?, self.implication(y, c)?],
Kind::ImpliesImplies => vec![self.implication(y, c)?],
Kind::AndImplies => {
let inner = self.implication(y, c)?;
vec![self.implication(x, inner)?]
}
Kind::Axiom
| Kind::FalseLeft
| Kind::TrueRight
| Kind::AndLeft
| Kind::IffLeft
| Kind::ImpliesRight
| Kind::AndRight
| Kind::IffRight
| Kind::OrLeft
| Kind::OrRight1
| Kind::OrRight2
| Kind::ModusPonens
| Kind::TrueImplies => unreachable!("{kind:?} makes no formula"),
})
}
fn prove(
&mut self,
key: Key,
stop: &mut impl FnMut(Progress) -> bool,
) -> Result<Known, Reason> {
let mut frames: Vec<Frame> = Vec::new();
let mut answer = self.open(key, &mut frames, stop)?;
loop {
let Some(top) = frames.last_mut() else {
return Ok(answer.unwrap_or_else(|| unreachable!("the root has its verdict")));
};
match answer.take() {
Some(Known::Proved(step)) => top.proved.push(step),
Some(Known::Failed)
if top.proved.is_empty()
&& top
.moves
.get(top.at)
.is_some_and(|m| m.kind == Kind::ImpliesImplies) =>
{
top.at = top.moves.len();
top.premises = None;
}
Some(Known::Failed) => {
top.at += 1;
top.premises = None;
top.proved.clear();
}
None => {}
}
if top.premises.is_none() {
let Some(&m) = top.moves.get(top.at) else {
let frame = frames.pop().unwrap_or_else(|| unreachable!("a frame"));
answer = Some(self.close(frame, false));
continue;
};
let key = (top.key.0.clone(), top.key.1);
let premises = self.premises((&key.0, key.1), m)?;
let top = frames.last_mut().unwrap_or_else(|| unreachable!("a frame"));
top.premises = Some(premises);
}
let top = frames.last_mut().unwrap_or_else(|| unreachable!("a frame"));
let premises = top.premises.as_deref().unwrap_or_default();
let Some(next) = premises.get(top.proved.len()).cloned() else {
let frame = frames.pop().unwrap_or_else(|| unreachable!("a frame"));
answer = Some(self.close(frame, true));
continue;
};
answer = self.open(next, &mut frames, stop)?;
if self.account.over() {
return Err(Reason::MemoryLimit {
limit_bytes: self.account.limit(),
});
}
}
}
fn open(
&mut self,
key: Key,
frames: &mut Vec<Frame>,
stop: &mut impl FnMut(Progress) -> bool,
) -> Result<Option<Known>, Reason> {
if let Some(&known) = self.memo.get(&key) {
self.statistics.memo_hits += 1;
return Ok(Some(known));
}
let done = self.statistics.sequents;
if done >= self.work {
return Err(Reason::WorkLimit { limit: self.work });
}
self.unpolled = self.unpolled.saturating_add(key.0.len() as u64);
if done.is_multiple_of(POLL) || self.unpolled >= POLL {
self.unpolled = 0;
let since = done - self.asked;
self.asked = done;
if stop(Progress::new(Phase::Search, since, done)) {
return Err(Reason::Stopped);
}
}
self.statistics.sequents += 1;
if self.subsumed(&key) {
self.statistics.subsumed += 1;
self.account.charge(bytes(key.0.len()));
self.memo.insert(key, Known::Failed);
return Ok(Some(Known::Failed));
}
let moves = self.moves((&key.0, key.1));
let frame = Frame {
key,
moves,
at: 0,
premises: None,
proved: Vec::new(),
};
self.account.charge(frame_bytes(&frame));
frames.push(frame);
Ok(None)
}
fn close(&mut self, frame: Frame, proved: bool) -> Known {
self.account.release(frame_bytes(&frame));
self.account.charge(bytes(frame.key.0.len()));
let known = if proved {
let applied = frame.moves[frame.at];
let mut premises = frame.proved;
if applied.kind == Kind::ImpliesImplies {
premises.reverse();
}
let id = u32::try_from(self.steps.len()).unwrap_or(u32::MAX);
self.account
.charge(size_of::<Step>() + bytes(frame.key.0.len()) + premises.len() * 4);
self.steps.push(Step {
key: frame.key.clone(),
applied,
premises,
});
Known::Proved(id)
} else {
self.account.charge(bytes(frame.key.0.len()));
let failed = self.failed.entry(frame.key.1).or_default();
failed.push(frame.key.0.clone());
Known::Failed
};
self.memo.insert(frame.key, known);
known
}
fn subsumed(&self, (left, goal): &Key) -> bool {
let Some(failed) = self.failed.get(goal) else {
return false;
};
failed
.iter()
.rev()
.take(SUBSUMING)
.any(|by| left.iter().all(|&x| self.entailed(x, by)))
}
fn entailed(&self, x: NodeId, by: &[NodeId]) -> bool {
let has = |y: NodeId| by.binary_search(&y).is_ok();
if has(x) || self.formulas.node(x) == Node::True {
return true;
}
let Some((a, c)) = self.split(x) else {
return false;
};
a == c || has(c) || self.split(a).is_some_and(|(h, b)| b == c && has(h))
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Plant {
Weakening,
Conjunct,
Disjunct,
Contraction,
}
struct Lj<'s, S> {
search: &'s Search,
widths: Vec<u64>,
inferences: Vec<Inference>,
bytes: u64,
limit: Option<u64>,
account: Account,
stop: S,
plant: Option<Plant>,
}
impl<'s, S: FnMut(Progress) -> bool> Lj<'s, S> {
fn new(search: &'s Search, limits: &Limits, stop: S) -> Self {
let widths = super::derivation::widths(&search.formulas);
let held = search.account.used();
let account = Account::holding(limits.memory_bytes, held);
account.charge(
widths.len() * size_of::<u64>() + search.formulas.len() * 4 * size_of::<Node>(),
);
Self {
search,
widths,
inferences: Vec::new(),
bytes: 0,
limit: limits.derivation_bytes,
account,
stop,
plant: None,
}
}
fn planted(&self, plant: Plant) -> bool {
self.plant == Some(plant)
}
fn push(
&mut self,
left: Vec<NodeId>,
right: Vec<NodeId>,
rule: Rule,
principal: Option<(Side, usize)>,
premises: Vec<InfId>,
) -> Result<InfId, Error> {
let n = self.inferences.len() as u64;
if (self.stop)(Progress::new(Phase::ReadBack, 1, n + 1)) {
return Err(Error::Refused(Refusal::Stopped {
phase: Phase::ReadBack,
}));
}
let estimate = super::derivation::inference_bytes(&self.widths, &left, &right);
self.bytes = self.bytes.saturating_add(estimate);
if let Some(limit) = self.limit
&& self.bytes > limit
{
return Err(Error::Refused(Refusal::Output {
what: "derivation",
estimate_bytes: self.bytes,
limit_bytes: limit,
least_bytes: None,
}));
}
let held = (left.len() + right.len() + premises.len()) * size_of::<u32>();
self.account.charge(held);
if self.account.over() {
return Err(Error::Refused(Refusal::Memory {
phase: Phase::ReadBack,
limit_bytes: self.account.limit(),
needed_bytes: None,
}));
}
let id = u32::try_from(n).map_err(|_| {
Error::Refused(Refusal::Index {
what: Space::Inference,
count: n + 1,
most: u64::from(u32::MAX),
})
})?;
let before = self.inferences.capacity();
self.inferences.push(Inference {
left,
right,
rule,
principal,
premises,
});
let size = size_of::<Inference>();
self.account
.resize(before * size, self.inferences.capacity() * size);
Ok(InfId::new(id))
}
fn axiom(&mut self, a: NodeId) -> Result<InfId, Error> {
self.push(vec![a], vec![a], Rule::Axiom, None, Vec::new())
}
fn left_rule(
&mut self,
rule: Rule,
left: Vec<NodeId>,
right: NodeId,
p: NodeId,
premises: Vec<InfId>,
) -> Result<InfId, Error> {
let principal = left.iter().position(|&x| x == p).map(|at| (Side::Left, at));
self.push(left, vec![right], rule, principal, premises)
}
fn right_rule(
&mut self,
rule: Rule,
left: Vec<NodeId>,
goal: NodeId,
premises: Vec<InfId>,
) -> Result<InfId, Error> {
self.push(left, vec![goal], rule, Some((Side::Right, 0)), premises)
}
fn implication_rule(&self, id: NodeId, side: Side) -> Rule {
let not = matches!(self.search.formulas.node(id), Node::Not(_));
match (not, side) {
(true, Side::Left) => Rule::NotLeft,
(true, Side::Right) => Rule::NotRight,
(false, Side::Left) => Rule::ImpliesLeft,
(false, Side::Right) => Rule::ImpliesRight,
}
}
fn weaken_to(&mut self, d: InfId, want: &[NodeId]) -> Result<InfId, Error> {
let inference = &self.inferences[d.index()];
let (mut have, right) = (inference.left.clone(), inference.right.clone());
let mut extra = difference(want, &have);
if self.planted(Plant::Weakening) {
extra.pop();
}
let mut d = d;
for x in extra {
have.push(x);
let at = have.len() - 1;
d = self.push(
have.clone(),
right.clone(),
Rule::WeakenLeft,
Some((Side::Left, at)),
vec![d],
)?;
}
Ok(d)
}
fn in_order(&mut self, d: InfId, left: &[NodeId]) {
let inference = &mut self.inferences[d.index()];
if !super::derivation::same(&inference.left, left) {
return;
}
if let Some((Side::Left, at)) = inference.principal {
let principal = inference.left[at];
let at = left
.iter()
.position(|&x| x == principal)
.unwrap_or_else(|| unreachable!("the same formulas as often"));
inference.principal = Some((Side::Left, at));
}
inference.left = left.to_vec();
}
fn contract_to(&mut self, d: InfId, want: &[NodeId]) -> Result<InfId, Error> {
let inference = &self.inferences[d.index()];
let (mut have, right) = (inference.left.clone(), inference.right.clone());
let mut extra = difference(&have, want);
if self.planted(Plant::Contraction) {
extra.pop();
}
let mut d = d;
for x in extra {
if let Some(at) = have.iter().position(|&y| y == x) {
have.remove(at);
}
let at = have.iter().position(|&y| y == x);
d = self.push(
have.clone(),
right.clone(),
Rule::ContractLeft,
at.map(|at| (Side::Left, at)),
vec![d],
)?;
}
Ok(d)
}
fn disjunct(
&mut self,
p: NodeId,
(x, c, xc): (NodeId, NodeId, NodeId),
rule: Rule,
) -> Result<InfId, Error> {
let (antecedent, _) = self
.search
.split(p)
.unwrap_or_else(|| unreachable!("an implication"));
let ax = self.axiom(x)?;
let or = self.right_rule(rule, vec![x], antecedent, vec![ax])?;
let cc = self.axiom(c)?;
let left = self.implication_rule(p, Side::Left);
let m = self.left_rule(left, vec![p, x], c, p, vec![or, cc])?;
let right = self.implication_rule(xc, Side::Right);
self.right_rule(right, vec![p], xc, vec![m])
}
fn translate(mut self, root: u32, left: &[NodeId], goal: NodeId) -> Result<Derivation, Error> {
enum Task {
Enter(u32),
Exit(u32),
}
let mut tasks = vec![Task::Enter(root)];
let mut made: Vec<InfId> = Vec::new();
while let Some(task) = tasks.pop() {
match task {
Task::Enter(step) => {
tasks.push(Task::Exit(step));
let premises = &self.search.steps[step as usize].premises;
tasks.extend(premises.iter().rev().map(|&p| Task::Enter(p)));
}
Task::Exit(step) => {
let count = self.search.steps[step as usize].premises.len();
let premises = made.split_off(made.len() - count);
let d = self.step(step, &premises)?;
made.push(d);
}
}
}
let d = made
.pop()
.unwrap_or_else(|| unreachable!("the root's derivation"));
let d = self.weaken_to(d, left)?;
self.in_order(d, left);
let search = self.search;
Ok(Derivation::from_parts(
search.logic,
search.formulas.clone(),
(left.to_vec(), vec![goal]),
self.inferences,
))
}
fn step(&mut self, step: u32, d: &[InfId]) -> Result<InfId, Error> {
let search = self.search;
let s = &search.steps[step as usize];
let (gamma, goal) = (s.key.0.to_vec(), s.key.1);
let p = s.applied.principal;
let f = &search.formulas;
let delta = |added: &[NodeId]| {
let mut list = gamma.clone();
if let Some(at) = list.iter().position(|&x| x == p) {
list.remove(at);
}
list.extend_from_slice(added);
list
};
let (a, b) = match f.node(p).operands() {
(Some(a), Some(b)) => (a, b),
(Some(a), None) => (a, search.falsity),
(None, _) => (p, p),
};
let implies = |x, y| {
f.find(Node::Implies(x, y))
.unwrap_or_else(|| unreachable!("the search added it"))
};
match s.applied.kind {
Kind::Axiom => {
let ax = self.axiom(goal)?;
self.weaken_to(ax, &gamma)
}
Kind::FalseLeft => self.left_rule(Rule::FalseLeft, gamma, goal, p, Vec::new()),
Kind::TrueRight => self.right_rule(Rule::TrueRight, gamma, goal, Vec::new()),
Kind::AndLeft => {
let premise = self.weaken_to(d[0], &delta(&[a, b]))?;
self.left_rule(Rule::AndLeft, gamma, goal, p, vec![premise])
}
Kind::IffLeft => {
let premise = self.weaken_to(d[0], &delta(&[implies(a, b), implies(b, a)]))?;
self.left_rule(Rule::IffLeft, gamma, goal, p, vec![premise])
}
Kind::ImpliesRight => {
let premise = self.weaken_to(d[0], &[&gamma[..], &[a]].concat())?;
let rule = self.implication_rule(goal, Side::Right);
self.right_rule(rule, gamma, goal, vec![premise])
}
Kind::AndRight => self.right_rule(Rule::AndRight, gamma, goal, d.to_vec()),
Kind::IffRight => self.right_rule(Rule::IffRight, gamma, goal, d.to_vec()),
Kind::OrRight1 => self.right_rule(Rule::OrRight1, gamma, goal, d.to_vec()),
Kind::OrRight2 => self.right_rule(Rule::OrRight2, gamma, goal, d.to_vec()),
Kind::OrLeft => {
let first = self.weaken_to(d[0], &delta(&[a]))?;
let second = self.weaken_to(d[1], &delta(&[b]))?;
self.left_rule(Rule::OrLeft, gamma, goal, p, vec![first, second])
}
Kind::TrueImplies => {
let second = self.weaken_to(d[0], &delta(&[b]))?;
let truth = self.right_rule(Rule::TrueRight, Vec::new(), a, Vec::new())?;
let rule = self.implication_rule(p, Side::Left);
self.left_rule(rule, gamma, goal, p, vec![truth, second])
}
Kind::ModusPonens => {
let second = self.weaken_to(d[0], &delta(&[b]))?;
let ax = self.axiom(a)?;
let rule = self.implication_rule(p, Side::Left);
let m = self.left_rule(rule, delta(&[a, p]), goal, p, vec![ax, second])?;
self.contract_to(m, &gamma)
}
Kind::AndImplies | Kind::IffImplies => {
let (Some(x), Some(y)) = f.node(a).operands() else {
unreachable!("a binary antecedent")
};
let (x, y, rule) = if s.applied.kind == Kind::AndImplies {
(x, y, Rule::AndRight)
} else {
(implies(x, y), implies(y, x), Rule::IffRight)
};
let ax = self.axiom(x)?;
let first = self.weaken_to(ax, &[x, y])?;
let ax = self.axiom(if self.planted(Plant::Conjunct) { x } else { y })?;
let second = self.weaken_to(ax, &[x, y])?;
let pair = self.right_rule(rule, vec![x, y], a, vec![first, second])?;
let bb = self.axiom(b)?;
let left = self.implication_rule(p, Side::Left);
let m = self.left_rule(left, vec![p, x, y], b, p, vec![pair, bb])?;
let yb = search.implication_of(y, b);
let right = self.implication_rule(yb, Side::Right);
let inner = self.right_rule(right, vec![p, x], yb, vec![m])?;
let made = search.implication_of(x, yb);
let right = self.implication_rule(made, Side::Right);
let schema = self.right_rule(right, vec![p], made, vec![inner])?;
let premise = self.weaken_to(d[0], &delta(&[made]))?;
self.push(gamma, vec![goal], Rule::Cut, None, vec![schema, premise])
}
Kind::OrImplies => {
let (Some(x), Some(y)) = f.node(a).operands() else {
unreachable!("a disjunction")
};
let (xb, yb) = (search.implication_of(x, b), search.implication_of(y, b));
let first = self.disjunct(p, (x, b, xb), Rule::OrRight1)?;
let second = self.disjunct(p, (y, b, yb), Rule::OrRight2)?;
let premise = self.weaken_to(d[0], &delta(&[xb, yb]))?;
let second = if self.planted(Plant::Disjunct) {
first
} else {
second
};
let inner = self.push(
delta(&[p, xb]),
vec![goal],
Rule::Cut,
None,
vec![second, premise],
)?;
let outer = self.push(
delta(&[p, p]),
vec![goal],
Rule::Cut,
None,
vec![first, inner],
)?;
self.contract_to(outer, &gamma)
}
Kind::ImpliesImplies => {
let (x, y) = search
.split(a)
.unwrap_or_else(|| unreachable!("an implication"));
let yb = search.implication_of(y, b);
let ax = self.axiom(y)?;
let w = self.weaken_to(ax, &[y, x])?;
let right = self.implication_rule(a, Side::Right);
let ya = self.right_rule(right, vec![y], a, vec![w])?;
let bb = self.axiom(b)?;
let left = self.implication_rule(p, Side::Left);
let m = self.left_rule(left, vec![p, y], b, p, vec![ya, bb])?;
let right = self.implication_rule(yb, Side::Right);
let schema = self.right_rule(right, vec![p], yb, vec![m])?;
let first = self.weaken_to(d[0], &delta(&[yb]))?;
let cut =
self.push(gamma.clone(), vec![a], Rule::Cut, None, vec![schema, first])?;
let second = self.weaken_to(d[1], &delta(&[b]))?;
let m = self.left_rule(
left,
[&gamma[..], &gamma[..]].concat(),
goal,
p,
vec![cut, second],
)?;
self.contract_to(m, &gamma)
}
}
}
}
fn difference(a: &[NodeId], b: &[NodeId]) -> Vec<NodeId> {
let mut rest = a.to_vec();
for x in b {
if let Some(at) = rest.iter().position(|y| y == x) {
rest.swap_remove(at);
}
}
rest
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::search::generate::Rng;
fn ljt(text: &str, logic: Logic) -> Outcome {
let sequent: Sequent = text.parse().unwrap();
decide(&sequent, logic, &Limits::default(), |_| false).unwrap()
}
fn valid(outcome: &Outcome) -> bool {
match &outcome.verdict {
Verdict::Valid(_) => true,
Verdict::NotValid => false,
Verdict::Unknown(reason) => panic!("unknown: {reason:?}"),
}
}
#[test]
fn a_large_sequent_asks_the_stop_at_each_expansion() {
let n = POLL as usize + 8;
let chain: Vec<String> = (0..n).map(|i| format!("a{i} -> a{}", i + 1)).collect();
let text = format!("a0, {} |- a{n}", chain.join(", "));
let sequent: Sequent = text.parse().unwrap();
let mut asked = Vec::new();
let outcome = decide(&sequent, Logic::Intuitionistic, &Limits::default(), |p| {
if p.phase == Phase::Search {
asked.push(p.done);
}
false
})
.unwrap();
assert!(matches!(outcome.verdict, Verdict::Valid(_)));
let expanded = outcome.statistics.sequents;
assert!(expanded > 2, "{expanded}");
assert_eq!(asked, (0..expanded).collect::<Vec<_>>());
}
#[test]
fn the_root_keeps_the_written_order() {
for text in ["a -> a -> b, a |- b", "b, a, b /\\ a |- a /\\ b"] {
let Verdict::Valid(Evidence::Derivation(d)) = ljt(text, Logic::Intuitionistic).verdict
else {
panic!("{text} is valid");
};
assert_eq!(d.inference(d.root()).left(), d.sequent().0, "{text}");
}
}
#[test]
fn agrees_with_the_embedding() {
const SEQUENTS: usize = 400;
let search = crate::linear::Options::default().with_copies(Some(6));
let bounded = Limits::default().with_work(Some(50_000));
let unbounded = Limits::default();
let mut rng = Rng::new(54);
let mut proved = 0;
for _ in 0..SEQUENTS {
let sequent = super::super::tests::generated_sequent(&mut rng);
for logic in [Logic::Intuitionistic, Logic::Minimal] {
let outcome = decide(&sequent, logic, &unbounded, |_| false).unwrap();
let answer = match &outcome.verdict {
Verdict::Valid(evidence) => {
let derivation = evidence.derivation().unwrap();
assert_eq!(derivation.check(&unbounded, |_| false), Ok(()), "{sequent}");
proved += 1;
true
}
Verdict::NotValid => false,
Verdict::Unknown(reason) => panic!("{sequent} in {logic} logic: {reason:?}"),
};
let options = super::super::Options::default()
.with_logic(logic)
.with_method(Some(super::super::Method::Embedding));
let embedded =
super::super::decide_within(&sequent, &options, &search, &bounded, |_| false)
.unwrap();
match embedded.verdict {
Verdict::Valid(_) => assert!(
answer,
"{sequent} in {logic} logic: the embedding proves it"
),
Verdict::NotValid => assert!(
!answer,
"{sequent} in {logic} logic: the embedding refutes it"
),
Verdict::Unknown(_) => {}
}
let classical = super::super::Options::default().with_logic(Logic::Classical);
let affine =
super::super::decide_within(&sequent, &classical, &search, &unbounded, |_| {
false
})
.unwrap();
if answer {
assert!(
matches!(affine.verdict, Verdict::Valid(_)),
"{sequent} is not even classically valid"
);
}
}
}
assert!(proved >= SEQUENTS / 4, "{proved} proofs");
}
#[test]
fn decides_the_separating_sequents() {
let cases = [
("a -> a", true, true),
("a \\/ ~a", false, false),
("~~(a \\/ ~a)", true, true),
("~~a -> a", false, false),
("((a -> b) -> a) -> a", false, false),
("false -> a", true, false),
("a \\/ b, ~a |- b", true, false),
("(a /\\ b -> c) |- a -> b -> c", true, true),
("(a \\/ b -> c) |- (a -> c) /\\ (b -> c)", true, true),
("((a -> b) -> c), b |- c", true, true),
("((a <-> b) -> c), a, b |- c", true, true),
("(true -> a) |- a", true, true),
("~(a /\\ b), a |- ~b", true, true),
("~(a \\/ b) |- ~a /\\ ~b", true, true),
("~(a -> b) |- ~b", true, true),
("a <-> b, a |- b", true, true),
("a, a, b |- a /\\ b", true, true),
("|- ~(a /\\ ~a)", true, true),
("a |-", false, false),
("a, ~a |-", true, true),
("~~~a -> ~a", true, true),
("((((a -> b) -> a) -> a) -> b) -> b", true, true),
];
for (text, intuitionistic, minimal) in cases {
assert_eq!(
valid(&ljt(text, Logic::Intuitionistic)),
intuitionistic,
"{text}"
);
assert_eq!(
valid(&ljt(text, Logic::Minimal)),
minimal,
"{text} minimally"
);
}
let sequent: Sequent = "a |- a".parse().unwrap();
assert!(matches!(
decide(&sequent, Logic::Classical, &Limits::default(), |_| false),
Err(Error::Logic { .. })
));
}
#[test]
fn the_benchmark_families_stay_small() {
const N: usize = 20;
let chain: Vec<String> = (1..=N)
.map(|i| format!("((b{} -> a{i}) -> a{})", i - 1, i - 1))
.collect();
let korn = format!("a0 -> f, ((b{N} -> b0) -> a{N}), {} |- f", chain.join(", "));
let conjunction: Vec<String> = (1..=N).map(|i| format!("p{i}")).collect();
let disjuncts: Vec<String> = (2..=N).map(|i| format!("(p{i} -> f)")).collect();
let franzen = format!(
"(({}) \\/ (~~p1 -> f) \\/ {}) -> f |- f",
conjunction.join(" /\\ "),
disjuncts.join(" \\/ ")
);
let work = Limits::default().with_work(Some(5_000));
for (text, valid) in [(korn, true), (franzen, false)] {
let sequent: Sequent = text.parse().unwrap();
let outcome = decide(&sequent, Logic::Intuitionistic, &work, |_| false).unwrap();
let answer = match outcome.verdict {
Verdict::Valid(_) => Some(true),
Verdict::NotValid => Some(false),
Verdict::Unknown(_) => None,
};
assert_eq!(answer, Some(valid), "{text}: {:?}", outcome.statistics);
}
}
#[test]
fn shared_formulas_cost_their_nodes() {
let mut f = Formulas::default();
let mut w = f.atom("p").unwrap();
for _ in 0..40 {
w = f.add(Node::And(w, w)).unwrap();
}
let mut left = Vec::new();
for (a, b) in [("a0", "b0"), ("a1", "b1")] {
let (a, b) = (f.atom(a).unwrap(), f.atom(b).unwrap());
let ab = f.add(Node::Implies(a, b)).unwrap();
left.push(f.add(Node::Implies(ab, w)).unwrap());
}
let goal = f.atom("g").unwrap();
let sequent = Sequent::new(f, left, vec![goal]).unwrap();
let work = Limits::default().with_work(Some(1_000));
let outcome = decide(&sequent, Logic::Intuitionistic, &work, |_| false).unwrap();
assert!(
matches!(outcome.verdict, Verdict::NotValid),
"{:?}",
outcome.verdict
);
}
#[test]
fn a_planted_wrong_translation_is_refused() {
let cases = [
(Plant::Weakening, "a, b |- a"),
(Plant::Conjunct, "(a /\\ b -> c), a, b |- c"),
(Plant::Disjunct, "(a \\/ b -> c) |- (a -> c) /\\ (b -> c)"),
(Plant::Contraction, "a, a -> b |- b"),
];
for (plant, text) in cases {
let sequent: Sequent = text.parse().unwrap();
let honest = run(
&sequent,
Logic::Intuitionistic,
&Limits::default(),
|_| false,
None,
);
assert!(
matches!(honest.unwrap().verdict, Verdict::Valid(_)),
"{text}"
);
let planted = run(
&sequent,
Logic::Intuitionistic,
&Limits::default(),
|_| false,
Some(plant),
);
assert!(
matches!(planted, Err(Error::ReadBack { .. })),
"{plant:?}: {planted:?}"
);
}
}
#[test]
fn the_search_keeps_to_its_bounds() {
let sequent: Sequent = "((a -> b) -> a) -> a".parse().unwrap();
let free = decide(&sequent, Logic::Intuitionistic, &Limits::default(), |_| {
false
})
.unwrap();
let sequents = free.statistics.sequents;
assert!(sequents > 2, "{sequents}");
let at = |work| Limits::default().with_work(Some(work));
let outcome = decide(&sequent, Logic::Intuitionistic, &at(sequents - 1), |_| {
false
})
.unwrap();
assert!(matches!(
outcome.verdict,
Verdict::Unknown(Reason::WorkLimit { .. })
));
let outcome = decide(&sequent, Logic::Intuitionistic, &at(sequents), |_| false).unwrap();
assert!(matches!(outcome.verdict, Verdict::NotValid));
let outcome = decide(&sequent, Logic::Intuitionistic, &Limits::default(), |_| {
true
})
.unwrap();
assert!(matches!(outcome.verdict, Verdict::Unknown(Reason::Stopped)));
let tight = Limits::default().with_memory_bytes(Some(64));
let outcome = decide(&sequent, Logic::Intuitionistic, &tight, |_| false).unwrap();
assert!(matches!(
outcome.verdict,
Verdict::Unknown(Reason::MemoryLimit { .. })
));
let sequent: Sequent = "a, b, c |- a /\\ (b /\\ c)".parse().unwrap();
let small = Limits::default().with_derivation_bytes(Some(100));
assert!(matches!(
decide(&sequent, Logic::Intuitionistic, &small, |_| false),
Err(Error::Refused(Refusal::Output { .. }))
));
}
}