use super::memory::Account;
use super::planar::Planar;
use super::{
Answer, Cadence, Decide, Engine, NotTaken, Options, Reason, Statistics, Stop, Task, Work,
};
use crate::Error;
use crate::hash::HashMap;
use crate::limits::{Limits, Refusal};
use crate::linear::fragment::{Fragment, Mode};
use crate::linear::nets::{Criterion, NetError, ProofStructure, Scratch, VertexId};
use crate::linear::occurrences::{Forest, OccId, Sign};
use crate::linear::proofs::{Node, Proof};
use crate::linear::sequents::{Atom, Kind};
const NONE: u32 = u32::MAX;
pub(crate) struct Nets;
impl Decide for Nets {
fn admits(&self, task: &Task<'_>) -> Result<(), Error> {
let refused = |because| Error::EngineRefused {
engine: Engine::Net,
because,
};
crate::linear::nets::exist(task.fragment, task.mode).map_err(|error| match error {
NetError::Fragment { fragment } => refused(NotTaken::Fragment {
decides: Fragment::MLL,
goal: fragment,
}),
NetError::Mode { mode } => refused(NotTaken::Mode { mode }),
other => other.into(),
})?;
if task.mode.is_ordered() && task.mode.is_intuitionistic() {
return Err(refused(NotTaken::Mode { mode: task.mode }));
}
if !task.roots && !(task.mode.is_ordered() && apart(task.forest, task.goal)) {
return Err(refused(NotTaken::Goal));
}
crate::linear::nets::fits(task.forest.len())
}
fn decide(
&self,
task: &Task<'_>,
options: &Options,
limits: &Limits,
_account: &Account,
work: &Work,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Answer, Error> {
#[cfg(feature = "parallel")]
if options.threads() > 1 && !task.mode.is_ordered() {
let runtime = super::parallel::Lent::take(
options.pool.as_ref(),
options.threads(),
limits.stack_bytes(),
)?;
return Ok(parallel::search(
task.forest,
task.mode,
options,
limits,
&runtime,
work,
stop,
));
}
#[cfg(not(feature = "parallel"))]
let _ = work;
if !task.roots {
return goal(task, limits, |own| {
Ok(search(own, task.mode, options, limits, stop))
});
}
Ok(search(task.forest, task.mode, options, limits, stop))
}
}
pub(super) fn apart(forest: &Forest, goal: &[OccId]) -> bool {
let mut sorted = goal.to_vec();
sorted.sort_unstable();
sorted
.windows(2)
.all(|w| u64::from(w[0].get()) + u64::from(forest.size(w[0])) <= u64::from(w[1].get()))
}
pub(super) fn goal(
task: &Task<'_>,
limits: &Limits,
run: impl FnOnce(&Forest) -> Result<Answer, Error>,
) -> Result<Answer, Error> {
let forest = task.forest;
let mut members = task.goal.to_vec();
members.sort_unstable();
let sequent = forest.sequent();
let own = crate::linear::Sequent {
terms: sequent.terms().to_vec(),
roots: members.iter().map(|&o| forest.term(o)).collect(),
atoms: sequent.atom_names().to_vec(),
antecedents: None,
cuts: vec![],
fo: sequent.fo.clone(),
};
let own = Forest::within(&own, limits)?;
let mut answer = run(&own)?;
let lift = |m: crate::linear::Member| {
let o = m.occ();
let root = own.root(o);
let i = own.roots().partition_point(|&r| r < root);
crate::linear::Member::from(OccId::new(members[i].get() + (o.get() - root.get())))
};
answer.result = answer.result.map(|proof| {
proof.map(|proof| {
let nodes = proof
.nodes()
.iter()
.map(|&node| match node {
Node::Ax(x, y) => Node::Ax(lift(x), lift(y)),
Node::Par(o, p) => Node::Par(lift(o), p),
Node::Tensor(o, l, r) => Node::Tensor(lift(o), l, r),
other => unreachable!("a net sequentializes into {} nodes", other.name()),
})
.collect();
Proof::new(forest.clone(), nodes, proof.root())
.expect("the shift keeps every node's order and occurrence in the forest")
.with_mode(task.mode)
})
});
answer.net = None;
Ok(answer)
}
pub(crate) fn search(
forest: &Forest,
mode: Mode,
options: &Options,
limits: &Limits,
stop: &mut dyn FnMut(u64) -> bool,
) -> Answer {
if !counts_admit(forest, mode.mix) {
return answer(Ok(false), Statistics::default(), None, limits, stop);
}
let (result, statistics, net) = if mode.is_ordered() {
let criterion = Planar::new(Switching::new(forest, mode));
let mut engine = Linker::with(criterion, options, Stop::Closure(stop), Prunes::PLANAR);
let result = engine.run();
let net = matches!(result, Ok(true)).then_some(engine.criterion.into_inner().net);
(result, engine.statistics, net)
} else {
let mut engine = Linker::new(forest, mode, options, Stop::Closure(stop));
let result = engine.run();
let net = matches!(result, Ok(true)).then_some(engine.criterion.net);
(result, engine.statistics, net)
};
answer(result, statistics, net, limits, stop)
}
pub(super) fn answer(
result: Result<bool, Reason>,
statistics: Statistics,
net: Option<ProofStructure>,
limits: &Limits,
stop: &mut dyn FnMut(u64) -> bool,
) -> Answer {
let result = result.and_then(|linked| {
if !linked {
return Ok(None);
}
let net = net.as_ref().expect("a proof net was found");
match net.sequentialize(limits, |_| stop(0)) {
Ok(proof) => Ok(Some(proof)),
Err(Error::Net(error)) => match *error {
NetError::Refused {
refusal: Refusal::Memory { limit_bytes, .. },
} => Err(Reason::MemoryLimit { limit_bytes }),
NetError::Refused { .. } => Err(Reason::Stopped),
error => {
panic!("a complete linking that passed the exact test is a proof net: {error}")
}
},
Err(error) => panic!("a proof net sequentializes: {error}"),
}
});
let net = net.filter(|_| matches!(result, Ok(Some(_))));
Answer {
result,
statistics,
net,
refutation: None,
}
}
pub(super) fn counts_admit(forest: &Forest, mix: bool) -> bool {
let (mut tensors, mut pars) = (0i64, 0i64);
for o in forest.ids() {
match forest.kind(o) {
Kind::Tensor => tensors += 1,
Kind::Par => pars += 1,
_ => {}
}
}
let conclusions = forest.roots().len() as i64;
let needed = tensors - pars + 2;
if if mix {
conclusions < needed
} else {
conclusions != needed
} {
return false;
}
atoms(forest)
.all(|a| forest.literals(a, Sign::Atom).len() == forest.literals(a, Sign::Dual).len())
}
fn atoms(forest: &Forest) -> impl Iterator<Item = Atom> {
(0..forest.sequent().atom_names().len()).map(|a| Atom::new(a as u32))
}
#[derive(Clone, Copy, Debug)]
pub(super) struct Prunes {
conclusions: bool,
leaves: bool,
compounds: bool,
balance: bool,
}
impl Prunes {
pub(super) const ALL: Self = Self {
conclusions: true,
leaves: true,
compounds: true,
balance: true,
};
pub(super) const PLANAR: Self = Self {
conclusions: false,
leaves: false,
compounds: false,
balance: true,
};
}
#[derive(Clone, Debug)]
struct Symmetry {
chains: Box<[Chains]>,
key: Box<[u32]>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Chains {
before: u32,
after: u32,
key_before: u32,
key_after: u32,
}
impl Chains {
const NONE: Self = Self {
before: NONE,
after: NONE,
key_before: NONE,
key_after: NONE,
};
}
impl Symmetry {
fn new(forest: &Forest, prunes: Prunes) -> Self {
let n = forest.len();
let mut top = vec![NONE; n];
let mut anchor = vec![n as u32; n];
for o in forest.ids() {
if let Some(p) = forest.parent(o) {
anchor[o.index()] = top[p.index()];
}
if !forest.is_literal(o) {
top[o.index()] = match forest.parent(o) {
Some(p) if forest.kind(p) == forest.kind(o) => top[p.index()],
_ => o.get(),
};
}
}
let chained = |l: &&OccId| {
if anchor[l.index()] == n as u32 {
prunes.conclusions
} else {
prunes.leaves
}
};
let (mut before, mut after) = (vec![NONE; n], vec![NONE; n]);
let mut last = vec![NONE; n + 1];
for a in atoms(forest) {
for sign in [Sign::Atom, Sign::Dual] {
let literals = forest.literals(a, sign);
for &l in literals.iter().filter(chained) {
let previous = &mut last[anchor[l.index()] as usize];
if *previous != NONE {
after[*previous as usize] = l.get();
before[l.index()] = *previous;
}
*previous = l.get();
}
for &l in literals.iter().filter(chained) {
last[anchor[l.index()] as usize] = NONE;
}
}
}
let mut shape = vec![0u32; n];
let mut shapes = HashMap::<(Kind, u32, u32), u32>::default();
let mut compounds = Vec::new();
for o in forest.ids().rev() {
let key = match (forest.left(o), forest.right(o)) {
(Some(l), Some(r)) => (forest.kind(o), shape[l.index()], shape[r.index()]),
_ => (forest.kind(o), forest.atom(o).map_or(0, Atom::get), 0),
};
let next = shapes.len() as u32;
shape[o.index()] = *shapes.entry(key).or_insert(next);
let leaf = forest
.parent(o)
.is_none_or(|p| forest.kind(p) != forest.kind(o));
if prunes.compounds && !forest.is_literal(o) && leaf {
compounds.push((anchor[o.index()], shape[o.index()], o));
}
}
compounds.sort_unstable();
let mut classes: Vec<&[(u32, u32, OccId)]> = compounds
.chunk_by(|x, y| (x.0, x.1) == (y.0, y.1))
.filter(|class| class.len() > 1)
.collect();
classes.sort_unstable_by_key(|class| std::cmp::Reverse(class[0].2));
let (mut key_before, mut key_after) = (vec![NONE; n], vec![NONE; n]);
let mut broken = vec![false; n];
let mut keyed = Vec::new();
for class in classes {
let first = class[0].2;
let Some(offset) = forest.subtree(first).position(|x| {
forest.is_literal(x)
&& before[x.index()] == NONE
&& after[x.index()] == NONE
&& !broken[x.index()]
}) else {
continue;
};
keyed.push((class, offset as u32));
for &(_, _, copy) in class {
for x in forest.subtree(copy) {
broken[x.index()] = true;
}
}
}
let mut key = vec![NONE; n];
for o in forest.ids() {
if forest.is_literal(o) && !broken[o.index()] {
key[o.index()] = match before[o.index()] {
NONE => o.get(),
b => key[b as usize],
};
}
}
for (class, offset) in keyed {
let l = OccId::new(class[0].2.get() + offset);
let (atom, sign) = (forest.atom(l).unwrap(), forest.sign(l).unwrap());
if forest
.literals(atom, !sign)
.iter()
.all(|y| key[y.index()] == NONE)
{
continue;
}
let mut previous = NONE;
for &(_, _, copy) in class {
let l = copy.get() + offset;
if previous != NONE {
key_after[previous as usize] = l;
key_before[l as usize] = previous;
}
previous = l;
}
}
let chains = (0..n)
.map(|i| Chains {
before: before[i],
after: after[i],
key_before: key_before[i],
key_after: key_after[i],
})
.collect();
Self {
chains,
key: key.into_boxed_slice(),
}
}
}
pub(super) trait Correctness {
fn forest(&self) -> &Forest;
fn mate(&self, x: OccId) -> Option<OccId>;
fn links(&self) -> &[(VertexId, VertexId)];
fn is_complete(&self) -> bool;
fn admits(&self, x: OccId, y: OccId) -> bool;
fn link(&mut self, x: OccId, y: OccId) -> Result<(), Reason>;
fn unlink(&mut self) -> OccId;
fn test(&mut self) -> bool;
fn balanced(&self, atom: Atom, remaining: u32, tally: &mut [u32]) -> bool;
}
pub(super) struct Switching {
net: ProofStructure,
scratch: Scratch,
}
impl Switching {
pub(super) fn new(forest: &Forest, mode: Mode) -> Self {
let net = ProofStructure::new(
forest.clone(),
Criterion {
mix: mode.mix,
order: mode.order,
},
)
.expect("the dispatch routes unit-free MLL only");
let scratch = net.scratch();
Self { net, scratch }
}
}
impl Correctness for Switching {
fn forest(&self) -> &Forest {
self.net.forest()
}
fn mate(&self, x: OccId) -> Option<OccId> {
self.net.mate(VertexId::of(x)).map(VertexId::occ)
}
fn links(&self) -> &[(VertexId, VertexId)] {
self.net.links()
}
fn is_complete(&self) -> bool {
self.net.is_complete()
}
fn admits(&self, x: OccId, y: OccId) -> bool {
let forest = self.net.forest();
if let Some(a) = forest.lca(x, y)
&& forest.kind(a) == Kind::Tensor
{
return false;
}
!self.net.joined(VertexId::of(x), VertexId::of(y))
}
fn link(&mut self, x: OccId, y: OccId) -> Result<(), Reason> {
self.net.link_unchecked(VertexId::of(x), VertexId::of(y));
Ok(())
}
fn unlink(&mut self) -> OccId {
let (x, _) = self.net.unlink().expect("a link to take back");
x.occ()
}
fn test(&mut self) -> bool {
self.net.is_acyclic(&mut self.scratch)
}
fn balanced(&self, atom: Atom, remaining: u32, tally: &mut [u32]) -> bool {
let net = &self.net;
let forest = net.forest();
let unlinked = || {
[Sign::Atom, Sign::Dual]
.into_iter()
.flat_map(move |sign| forest.literals(atom, sign))
.filter(|&&x| net.mate(VertexId::of(x)).is_none())
.map(|&x| net.component(VertexId::of(x)) as usize)
};
let mut balanced = true;
for c in unlinked() {
tally[c] += 1;
balanced &= tally[c] <= remaining;
}
for c in unlinked() {
tally[c] = 0;
}
balanced
}
}
#[derive(Clone, Copy, Debug)]
struct Frame {
literal: OccId,
next: u32,
forced: bool,
}
#[derive(Clone, Copy, Debug)]
enum Choice {
Complete,
DeadEnd,
Literal(OccId, bool),
}
pub(super) struct Linker<'a, C> {
pub(super) criterion: C,
remaining: Box<[u32]>,
symmetry: Symmetry,
balance: bool,
tally: Box<[u32]>,
stack: Vec<Frame>,
choices: usize,
period: u32,
pub(super) statistics: Statistics,
stop: Stop<'a>,
}
impl<'a> Linker<'a, Switching> {
fn new(forest: &Forest, mode: Mode, options: &Options, stop: Stop<'a>) -> Self {
Self::with_prunes(forest, mode, options, stop, Prunes::ALL)
}
fn with_prunes(
forest: &Forest,
mode: Mode,
options: &Options,
stop: Stop<'a>,
prunes: Prunes,
) -> Self {
Linker::with(Switching::new(forest, mode), options, stop, prunes)
}
}
impl<'a, C: Correctness> Linker<'a, C> {
pub(super) fn with(criterion: C, options: &Options, stop: Stop<'a>, prunes: Prunes) -> Self {
let forest = criterion.forest();
let remaining = atoms(forest)
.map(|a| forest.literals(a, Sign::Atom).len() as u32)
.collect();
let n = forest.len();
let period = match options.test_period {
Cadence::Every(period) => period.max(1),
Cadence::Auto if n <= Cadence::AUTO_SMALL => 1,
Cadence::Auto => Cadence::AUTO_PERIOD,
};
Self {
remaining,
symmetry: Symmetry::new(forest, prunes),
balance: prunes.balance,
tally: vec![0; n].into_boxed_slice(),
stack: Vec::with_capacity(forest.all_literals().len() / 2 + 1),
choices: 0,
period,
statistics: Statistics::default(),
stop,
criterion,
}
}
pub(super) fn run(&mut self) -> Result<bool, Reason> {
self.explore(None, &mut Vec::new())
}
fn explore(
&mut self,
limit: Option<usize>,
cubes: &mut Vec<Vec<(VertexId, VertexId)>>,
) -> Result<bool, Reason> {
let Choice::Literal(first, forced) = self.decide()? else {
return Ok(false);
};
self.push(first, forced);
loop {
let Some(y) = self.next_partner() else {
self.pop();
if self.stack.is_empty() {
return Ok(false);
}
self.unlink();
continue;
};
let x = self.stack.last().unwrap().literal;
self.link(x, y)?;
let complete = self.criterion.is_complete();
if complete || (self.criterion.links().len() as u32).is_multiple_of(self.period) {
self.statistics.tests += 1;
if !self.criterion.test() {
self.unlink();
if self.stop.fired(1) {
return Err(Reason::Stopped);
}
continue;
}
}
if complete {
return Ok(true);
}
if limit == Some(self.choices) {
cubes.push(self.criterion.links().to_vec());
self.unlink();
continue;
}
match self.decide()? {
Choice::Literal(literal, forced) => self.push(literal, forced),
Choice::DeadEnd => self.unlink(),
Choice::Complete => unreachable!("an incomplete structure has an unlinked literal"),
}
}
}
fn push(&mut self, literal: OccId, forced: bool) {
self.choices += usize::from(!forced);
self.stack.push(Frame {
literal,
next: 0,
forced,
});
}
fn pop(&mut self) {
let frame = self.stack.pop().expect("a decision to close");
self.choices -= usize::from(!frame.forced);
}
fn decide(&mut self) -> Result<Choice, Reason> {
self.statistics.nodes += 1;
if self.stop.fired(1) {
return Err(Reason::Stopped);
}
Ok(self.choose())
}
#[cfg(feature = "parallel")]
fn seed(&mut self, links: &[(VertexId, VertexId)]) {
debug_assert!(
self.criterion.links().is_empty(),
"a seed goes on an empty structure"
);
for &(x, y) in links {
self.link(x.occ(), y.occ())
.expect("the classical criterion links without a bound");
}
}
#[cfg(feature = "parallel")]
fn reset(&mut self) {
self.stack.clear();
self.choices = 0;
while !self.criterion.links().is_empty() {
self.unlink();
}
}
fn choose(&mut self) -> Choice {
let balance =
self.balance && (self.criterion.links().len() as u32).is_multiple_of(self.period);
let mut best: Option<(usize, OccId)> = None;
for a in 0..self.remaining.len() {
let remaining = self.remaining[a];
if remaining == 0 {
continue;
}
let atom = Atom::new(a as u32);
if balance
&& remaining > 2
&& !self.criterion.balanced(atom, remaining, &mut self.tally)
{
return Choice::DeadEnd;
}
let forest = self.criterion.forest();
for sign in [Sign::Atom, Sign::Dual] {
let partners = forest.literals(atom, !sign);
for &x in forest.literals(atom, sign) {
if self.criterion.mate(x).is_some() {
continue;
}
let bound = best.map_or(usize::MAX, |(count, _)| count);
let mut count = 0;
for &y in partners {
if self.criterion.mate(y).is_none() && self.admissible(x, y) {
count += 1;
if count >= bound {
break;
}
}
}
if count == 0 {
return Choice::DeadEnd;
}
if count < bound {
best = Some((count, x));
}
}
}
}
match best {
Some((count, literal)) => Choice::Literal(literal, count == 1),
None => Choice::Complete,
}
}
fn next_partner(&mut self) -> Option<OccId> {
let Frame {
literal: x, next, ..
} = *self.stack.last().unwrap();
let forest = self.criterion.forest();
let partners = forest.literals(forest.atom(x).unwrap(), !forest.sign(x).unwrap());
for (i, &y) in partners.iter().enumerate().skip(next as usize) {
if self.criterion.mate(y).is_none() && self.admissible(x, y) {
self.stack.last_mut().unwrap().next = i as u32 + 1;
return Some(y);
}
}
None
}
fn admissible(&self, x: OccId, y: OccId) -> bool {
if !self.criterion.admits(x, y) {
return false;
}
let chains = &self.symmetry.chains;
let (cx, cy) = (chains[x.index()], chains[y.index()]);
(cx == Chains::NONE || self.ordered(cx, y)) && (cy == Chains::NONE || self.ordered(cy, x))
}
fn ordered(&self, chains: Chains, y: OccId) -> bool {
let partner = |l: u32| {
(l != NONE)
.then(|| self.criterion.mate(OccId::new(l)))
.flatten()
};
let key = &self.symmetry.key;
if partner(chains.before).is_some_and(|p| p > y)
|| partner(chains.after).is_some_and(|q| q < y)
{
return false;
}
!(partner(chains.key_before).is_some_and(|p| key[p.index()] > key[y.index()])
|| partner(chains.key_after).is_some_and(|q| key[y.index()] > key[q.index()]))
}
fn link(&mut self, x: OccId, y: OccId) -> Result<(), Reason> {
self.criterion.link(x, y)?;
let atom = self.criterion.forest().atom(x).unwrap();
self.remaining[atom.index()] -= 1;
self.statistics.links += 1;
Ok(())
}
fn unlink(&mut self) {
let x = self.criterion.unlink();
let atom = self.criterion.forest().atom(x).unwrap();
self.remaining[atom.index()] += 1;
}
}
#[cfg(all(test, feature = "parse"))]
pub(super) mod tests {
use super::*;
use crate::linear::search::generate::{self, Rng, Rules, Tree};
use crate::linear::search::{Engine, Verdict, prove};
use crate::linear::sequents::Sequent;
fn run(input: &str, mode: Mode, options: &Options) -> (Verdict, Statistics) {
let s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
let options = options.clone().with_engine(Some(Engine::Net));
let outcome = prove(&s, mode, &options).unwrap_or_else(|e| panic!("{input:?}: {e}"));
let (verdict, statistics, net) = (outcome.verdict, outcome.statistics, outcome.net);
match (&verdict, &net) {
(Verdict::Proved(proof), Some(net)) => {
assert_eq!(proof.sequent(), &s);
proof
.check(mode)
.unwrap_or_else(|e| panic!("{input:?}: the proof is wrong: {e}"));
assert_eq!(net.is_correct(|_| false), Ok(()), "{input:?}");
let criterion = Criterion {
mix: mode.mix,
..Criterion::MLL
};
let again =
ProofStructure::from_proof(proof, criterion, &Limits::default(), |_| false)
.unwrap();
assert_eq!(sorted(&again), sorted(net), "{input:?}: the proof's net");
}
(Verdict::Proved(_), None) | (_, Some(_)) => {
panic!("{input:?}: a net exactly when proved")
}
_ => {}
}
(verdict, statistics)
}
fn sorted(net: &ProofStructure) -> Vec<(VertexId, VertexId)> {
let mut links: Vec<(VertexId, VertexId)> = net
.links()
.iter()
.map(|&(x, y)| (x.min(y), x.max(y)))
.collect();
links.sort();
links
}
fn provable(input: &str, mode: Mode) -> bool {
match run(input, mode, &Options::default()).0 {
Verdict::Proved(_) => true,
Verdict::Unprovable(_) => false,
Verdict::Unknown(reason) => panic!("{input:?}: {reason}"),
}
}
fn mode_for(mix: bool) -> Mode {
if mix {
Mode::CLASSICAL.with_mix()
} else {
Mode::CLASSICAL
}
}
#[test]
fn classic_sequents() {
let m = Mode::CLASSICAL;
for (input, expected) in [
("|- ~a, a", true),
("a |- a", true),
("|- a, a", false),
("|-", false),
("|- a, ~a, a, ~a", false),
("a * b |- a * b", true),
("|- a * b, ~a par ~b", true),
("|- a * b, ~a, ~b", true),
("|- a par b, ~a, ~b", false),
("|- (a * b) par (~a * ~b)", false),
("|- a * ~a", false),
("|- a par ~a", true),
("|- a * b, ~a * ~b", false),
("|- a * b, c * (~a par ~b), ~c", true),
("a, a -o b, b -o c |- c", true),
("a -o b, b -o c |- a -o c", true),
("a -o b |- b -o a", false),
("|- (a par ~a) par (b par ~b)", false),
("|- a, a, ~a * ~a", true),
("|- a, a, a, ~a * (~a * ~a)", true),
("|- a, ~a, a, ~a", false),
] {
assert_eq!(provable(input, m), expected, "{input:?}");
}
let mix = m.with_mix();
for (input, expected) in [
("|-", false),
("|- a, ~a, a, ~a", true),
("|- a par b, ~a, ~b", true),
("|- a * b, ~a * ~b", false),
("|- a * ~a", false),
("|- (a par ~a) par (b par ~b)", true),
("|- a, a, ~a * ~a", true),
("|- a, a, ~a, ~a, b par c, ~b, ~c", true),
] {
assert_eq!(provable(input, mix), expected, "{input:?} with Mix");
}
}
#[test]
fn distinct_atoms_need_no_backtracking() {
let k = 40;
let atoms: Vec<String> = (0..k).map(|i| format!("a{i}")).collect();
let tensors = atoms.join(" * ");
let pars: Vec<String> = atoms.iter().map(|a| format!("~{a}")).collect();
let input = format!("|- {tensors}, {}", pars.join(" par "));
let (verdict, statistics) = run(&input, Mode::CLASSICAL, &Options::default());
assert!(verdict.proof().is_some());
assert_eq!(statistics.nodes, k as u64);
assert_eq!(statistics.links, k as u64);
assert_eq!(statistics.tests, k as u64);
let (verdict, statistics) = run(
&input,
Mode::CLASSICAL,
&Options::default().with_test_period(Some(7)),
);
assert!(verdict.proof().is_some());
assert_eq!(statistics.links, k as u64);
assert_eq!(statistics.tests, (k / 7 + 1) as u64);
let long: Vec<String> = (0..120).map(|i| format!("b{i}")).collect();
let input = format!(
"|- {}, {}",
long.join(" * "),
long.iter()
.map(|a| format!("~{a}"))
.collect::<Vec<_>>()
.join(" par ")
);
let (verdict, statistics) = run(&input, Mode::CLASSICAL, &Options::default());
assert!(verdict.proof().is_some());
assert_eq!(statistics.links, 120);
assert_eq!(statistics.tests, 30);
}
#[test]
fn symmetry_of_equal_conclusions() {
let input = "|- a, a, a, a, ((~a * ~a) * (~a * ~a)) * (b * c), \
(~b par d) * (~c par f), ~d * ~f";
let postponed = Options::default().with_test_period(Some(100));
let (verdict, statistics) = run(input, Mode::CLASSICAL, &postponed);
assert!(matches!(verdict, Verdict::Unprovable(_)));
assert_eq!(statistics.tests, 1);
assert!(statistics.links < 40, "{statistics:?}");
let (verdict, statistics) = run(input, Mode::CLASSICAL, &Options::default());
assert!(matches!(verdict, Verdict::Unprovable(_)));
assert_eq!(statistics.links, 2, "the cycle is seen at the second link");
assert!(statistics.work > statistics.nodes, "{statistics:?}");
let provable_twin = "|- a, a, a, a, ((~a * ~a) * (~a * ~a)) * (b * c), \
(~b par ~c) * (d * f), ~d, ~f";
assert!(provable(provable_twin, Mode::CLASSICAL));
}
#[test]
fn stop() {
let s: Sequent = "|- a * b, ~a, ~b".parse().unwrap();
let forest = Forest::new(&s).unwrap();
let mut polls = 0;
let (options, limits) = (Options::default(), Limits::default());
let answer = search(&forest, Mode::CLASSICAL, &options, &limits, &mut |_| {
polls += 1;
polls == 2
});
assert_eq!(answer.result.err(), Some(Reason::Stopped));
assert!(answer.net.is_none());
assert_eq!(answer.statistics.nodes, 2);
assert_eq!(answer.statistics.links, 1);
}
fn focus_verdict(s: &Sequent, mode: Mode) -> bool {
let options = Options::default().with_engine(Some(Engine::Focus));
match prove(s, mode, &options).unwrap().verdict {
Verdict::Proved(proof) => {
assert_eq!(proof.check(mode), Ok(()));
true
}
Verdict::Unprovable(_) => false,
Verdict::Unknown(reason) => panic!("{s}: the focused engine says {reason}"),
}
}
fn net_verdict(text: &str, mode: Mode, options: &Options) -> bool {
match run(text, mode, options).0 {
Verdict::Proved(_) => true,
Verdict::Unprovable(_) => false,
Verdict::Unknown(reason) => panic!("{text}: {reason}"),
}
}
pub(super) fn sample(samples: usize, budget: usize, pairs: usize) -> Vec<(String, Mode)> {
let mut texts = Vec::new();
for mix in [false, true] {
let mode = mode_for(mix);
let rules = Rules {
units: false,
additives: false,
mix,
exponentials: false,
};
let mut rng = Rng::new(u64::from(mix) + 10);
for _ in 0..samples {
let budget = 2 + rng.below(budget - 1);
let mut formulas = generate::provable(&mut rng, rules, 3, budget).formulas;
texts.push((generate::sequent(&formulas), mode));
let doubled: Vec<_> = formulas.iter().chain(&formulas).cloned().collect();
texts.push((generate::sequent(&doubled), mode));
if generate::mutate(&mut rng, &mut formulas, 3) {
texts.push((generate::sequent(&formulas), mode));
}
let pairs = 1 + rng.below(pairs);
let atoms = 1 + rng.below(3) as u8;
let balanced = generate::balanced(&mut rng, atoms, pairs, mix);
texts.push((generate::sequent(&balanced), mode));
}
}
texts
}
fn compare(sample: &[(String, Mode)], period: Option<u32>) -> (usize, usize) {
let options = Options::default().with_test_period(period);
let mut provable = 0;
for (text, mode) in sample {
let s: Sequent = text.parse().unwrap();
let by_focus = focus_verdict(&s, *mode);
let by_net = net_verdict(text, *mode, &options);
assert_eq!(
by_net, by_focus,
"{text:?} in {mode} mode: net {by_net}, focus {by_focus}"
);
provable += usize::from(by_net);
}
(sample.len(), provable)
}
#[test]
fn agrees_with_the_focused_engine() {
let sample = sample(60, 12, 8);
let (decided, provable) = compare(&sample, None);
assert_eq!(decided, sample.len());
assert!(
provable > 100 && provable < decided - 100,
"{provable} of {decided}"
);
compare(&sample, Some(3));
}
fn every_linking(text: &str, mix: bool, limit: u64) -> Option<bool> {
let sequent: Sequent = text.parse().unwrap();
let forest = Forest::new(&sequent).unwrap();
let mut pairings = 1u64;
let mut positives = Vec::new();
for a in atoms(&forest) {
let (p, q) = (
forest.literals(a, Sign::Atom),
forest.literals(a, Sign::Dual),
);
if p.len() != q.len() {
return Some(false);
}
pairings = pairings.saturating_mul((1..=p.len() as u64).product());
if pairings > limit {
return None;
}
positives.extend_from_slice(p);
}
let mut net = ProofStructure::new(
forest,
Criterion {
mix,
..Criterion::MLL
},
)
.unwrap();
Some(some_net(&mut net, &positives))
}
fn some_net(net: &mut ProofStructure, positives: &[OccId]) -> bool {
let Some((&x, rest)) = positives.split_first() else {
return net.is_correct(|_| false).is_ok();
};
let forest = net.forest().clone();
for &y in forest.literals(forest.atom(x).unwrap(), Sign::Dual) {
if net.partner(VertexId::of(y)).is_none() {
net.link(VertexId::of(x), VertexId::of(y)).unwrap();
let found = some_net(net, rest);
net.unlink();
if found {
return true;
}
}
}
false
}
fn dual(formula: &Tree) -> Tree {
match formula {
Tree::Atom(a) => Tree::Dual(*a),
Tree::Dual(a) => Tree::Atom(*a),
Tree::Tensor(l, r) => Tree::Par(Box::new(dual(l)), Box::new(dual(r))),
Tree::Par(l, r) => Tree::Tensor(Box::new(dual(l)), Box::new(dual(r))),
other => unreachable!("{other:?} is not unit-free MLL"),
}
}
fn decide_with(text: &str, mode: Mode, prunes: Prunes) -> (bool, u64) {
let sequent: Sequent = text.parse().unwrap();
let forest = Forest::new(&sequent).unwrap();
if !counts_admit(&forest, mode.mix) {
return (false, 0);
}
let options = Options::default();
let mut never = |_| false;
let mut linker =
Linker::with_prunes(&forest, mode, &options, Stop::Closure(&mut never), prunes);
(linker.run().unwrap(), linker.statistics.nodes)
}
const WITHOUT_ONE: [Prunes; 4] = [
Prunes {
leaves: false,
..Prunes::ALL
},
Prunes {
compounds: false,
..Prunes::ALL
},
Prunes {
balance: false,
..Prunes::ALL
},
Prunes {
leaves: false,
compounds: false,
balance: false,
..Prunes::ALL
},
];
#[test]
fn agrees_with_every_linking() {
let mut rng = Rng::new(35);
let (mut decided, mut proved) = (0, 0);
let (mut nodes, mut without) = (0, [0; 4]);
for round in 0..800 {
let mix = round % 2 == 1;
let atoms = 1 + rng.below(2) as u8;
let pairs = 1 + rng.below(5);
let formulas = generate::balanced(&mut rng, atoms, pairs, mix);
let mut texts = vec![generate::sequent(&formulas)];
let first = formulas[0].clone();
let mut doubled = vec![Tree::Tensor(Box::new(first.clone()), Box::new(first))];
for f in &formulas[1..] {
doubled.extend([f.clone(), f.clone()]);
}
texts.push(generate::sequent(&doubled));
let f = &formulas[0];
if matches!(f, Tree::Tensor(..) | Tree::Par(..)) {
let (y, not_y) = (Tree::Atom(7), Tree::Dual(7));
let tensor =
|l: &Tree, r: &Tree| Tree::Tensor(Box::new(l.clone()), Box::new(r.clone()));
let g = dual(f);
for mut copies in [
vec![f.clone(), f.clone(), tensor(&g, &y), tensor(¬_y, &g)],
vec![tensor(f, f), tensor(&g, &y), g.clone(), not_y.clone()],
] {
texts.push(generate::sequent(&copies));
if generate::mutate(&mut rng, &mut copies, atoms) {
texts.push(generate::sequent(&copies));
}
}
}
for text in texts {
let Some(expected) = every_linking(&text, mix, 5_040) else {
continue;
};
let mode = mode_for(mix);
let found = net_verdict(&text, mode, &Options::default());
assert_eq!(found, expected, "{text:?} in {mode} mode");
nodes += decide_with(&text, mode, Prunes::ALL).1;
for (prunes, sum) in WITHOUT_ONE.iter().zip(&mut without) {
let (found, n) = decide_with(&text, mode, *prunes);
assert_eq!(found, expected, "{text:?} in {mode} mode, {prunes:?}");
*sum += n;
}
decided += 1;
proved += usize::from(expected);
}
}
assert!(
decided > 1_000 && proved > 100 && decided - proved > 100,
"{proved} of {decided}"
);
assert!(without.iter().all(|&n| n > nodes), "{nodes} {without:?}");
}
#[test]
fn partition_instances() {
for (sizes, expected) in [
(&[1, 1][..], true),
(&[1, 3], false),
(&[2, 1, 1], true),
(&[1, 1, 4], false),
] {
let s = crate::linear::families::partition(sizes);
assert_eq!(
provable(&s.to_string(), Mode::CLASSICAL),
expected,
"{sizes:?}"
);
assert_eq!(focus_verdict(&s, Mode::CLASSICAL), expected, "{sizes:?}");
}
}
#[test]
fn deterministic() {
let input = "|- a, a, ~a * (b par ~b), ~a * (c * ~c) par d, ~d";
let (first, stats) = run(input, Mode::CLASSICAL.with_mix(), &Options::default());
let (second, again) = run(input, Mode::CLASSICAL.with_mix(), &Options::default());
assert_eq!(stats, again);
assert_eq!(
first.proof().map(|p| p.nodes().to_vec()),
second.proof().map(|p| p.nodes().to_vec())
);
assert_eq!(Engine::Net.to_string(), "net");
}
}
#[cfg(feature = "parallel")]
pub(crate) mod parallel {
use super::{Linker, counts_admit};
use crate::limits::Limits;
use crate::linear::fragment::Mode;
use crate::linear::nets::{ProofStructure, VertexId};
use crate::linear::occurrences::Forest;
use crate::linear::search::parallel::{RaiseOnPanic, Runtime, record};
use crate::linear::search::{Answer, Options, Reason, Statistics, Stop, Work};
use crate::linear::search::{lock, taken};
use std::sync::Mutex;
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
const CUBES_PER_THREAD: usize = 16;
type Cube = Vec<(VertexId, VertexId)>;
struct Collected {
net: Option<ProofStructure>,
error: Option<Reason>,
statistics: Statistics,
}
pub(crate) fn search(
forest: &Forest,
mode: Mode,
options: &Options,
limits: &Limits,
runtime: &Runtime,
work: &Work,
stop: &mut dyn FnMut(u64) -> bool,
) -> Answer {
if !counts_admit(forest, mode.mix) {
return super::answer(Ok(false), Statistics::default(), None, limits, stop);
}
let threads = runtime.threads();
let (result, statistics, net) = runtime.drive(stop, work, |flags| {
let mut root = Linker::new(forest, mode, options, Stop::flags(flags));
let mut cubes = vec![Cube::new()];
while cubes.len() < CUBES_PER_THREAD * threads {
let mut split = Vec::new();
for cube in &cubes {
root.reset();
root.seed(cube);
match root.explore(Some(1), &mut split) {
Ok(true) => return (Ok(true), root.statistics, Some(root.criterion.net)),
Ok(false) => {}
Err(reason) => return (Err(reason), root.statistics, None),
}
}
if split.is_empty() {
return (Ok(false), root.statistics, None);
}
cubes = split;
}
let next = AtomicUsize::new(0);
let found = AtomicBool::new(false);
let collected = Mutex::new(Collected {
net: None,
error: None,
statistics: root.statistics,
});
runtime.pool.scope(|scope| {
for _ in 0..threads {
let (cubes, next, found, collected, flags) =
(&cubes, &next, &found, &collected, &flags);
scope.spawn(move |_| {
let _found = RaiseOnPanic(found);
let mut engine =
Linker::new(forest, mode, options, Stop::flags(flags.child(found)));
loop {
let i = next.fetch_add(1, Ordering::Relaxed);
let Some(cube) = cubes.get(i) else {
break;
};
engine.reset();
engine.seed(cube);
match engine.run() {
Ok(false) => continue,
Ok(true) => {
let mut collected = lock(collected);
if collected.net.is_none() {
collected.net = Some(engine.criterion.net.clone());
}
found.store(true, Ordering::Relaxed);
}
Err(Reason::Stopped) if found.load(Ordering::Relaxed) => {}
Err(reason) => {
record(&mut lock(collected).error, reason);
found.store(true, Ordering::Relaxed);
}
}
break;
}
lock(collected).statistics.add_run(&engine.statistics);
});
}
});
let collected = taken(collected);
match (collected.net, collected.error) {
(Some(net), _) => (Ok(true), collected.statistics, Some(net)),
(None, Some(reason)) => (Err(reason), collected.statistics, None),
(None, None) => (Ok(false), collected.statistics, None),
}
});
super::answer(result, statistics, net, limits, stop)
}
}
#[cfg(all(test, feature = "parse", feature = "parallel"))]
mod parallel_tests {
use super::tests::sample;
use crate::linear::fragment::Mode;
use crate::linear::search::{Engine, Options, Reason, Verdict, prove, prove_within};
use crate::linear::sequents::Sequent;
fn verdict(text: &str, mode: Mode, jobs: usize) -> Verdict {
let sequent: Sequent = text.parse().unwrap();
let options = Options::default()
.with_engine(Some(Engine::Net))
.with_jobs(jobs);
let outcome = prove(&sequent, mode, &options).unwrap();
if let Verdict::Proved(proof) = &outcome.verdict {
assert_eq!(proof.check(mode), Ok(()), "{text:?}");
let net = outcome.net.as_ref().expect("the net found");
assert_eq!(net.is_correct(|_| false), Ok(()), "{text:?}");
}
outcome.verdict
}
#[test]
fn cubes_agree_with_the_sequential_search() {
for (text, mode) in sample(20, 6, 6) {
let sequential = verdict(&text, mode, 1);
for jobs in [2, 4] {
let parallel = verdict(&text, mode, jobs);
assert_eq!(
matches!(sequential, Verdict::Proved(_)),
matches!(parallel, Verdict::Proved(_)),
"{text:?} in {mode} mode: {sequential:?} on one thread, {parallel:?} on {jobs}"
);
assert_eq!(
matches!(sequential, Verdict::Unprovable(_)),
matches!(parallel, Verdict::Unprovable(_)),
"{text:?} in {mode} mode: {sequential:?} on one thread, {parallel:?} on {jobs}"
);
}
}
}
#[test]
fn forced_links_are_made_once() {
let sequent = crate::linear::families::wide(64, 1);
let options = Options::default().with_engine(Some(Engine::Net));
let sequential = prove(&sequent, Mode::CLASSICAL, &options).unwrap();
assert!(matches!(sequential.verdict, Verdict::Proved(_)));
let parallel = prove(&sequent, Mode::CLASSICAL, &options.with_jobs(2)).unwrap();
assert!(matches!(parallel.verdict, Verdict::Proved(_)));
assert_eq!(parallel.statistics, sequential.statistics);
}
#[test]
fn stops() {
let family = crate::linear::families::find("partition-no").unwrap();
let sequent = family.instance(9, 0).unwrap().sequent;
let options = Options::default()
.with_engine(Some(Engine::Net))
.with_jobs(2);
let outcome = prove_within(
&sequent,
Mode::CLASSICAL,
&options,
&crate::Limits::default(),
|_| true,
)
.unwrap();
assert!(
matches!(outcome.verdict, Verdict::Unknown(Reason::Stopped)),
"{:?}",
outcome.verdict
);
}
}