use super::generate::Tree;
use crate::linear::Sequent;
use crate::linear::fragment::Mode;
use crate::linear::sequents::{Term, TermId};
use std::collections::HashMap;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Answer {
Proved,
Unprovable,
Unknown,
}
pub(crate) const VISITS: usize = 1_000_000;
pub(crate) fn classical(formulas: &[Tree], mode: Mode, copies: u32) -> Answer {
assert!(!mode.intuitionistic, "a one-sided sequent is classical");
let mut prover = Prover::new(mode);
let mut sequent: Vec<u32> = formulas.iter().map(|t| prover.tree(t)).collect();
sequent.sort_unstable();
prover.deepen(copies, |prover, budget| prover.one_sided(&sequent, budget))
}
pub(crate) fn intuitionistic(hypotheses: &[Tree], goal: &Tree, mode: Mode, copies: u32) -> Answer {
assert!(
mode.intuitionistic && !mode.mix,
"a two-sided sequent is intuitionistic, without Mix"
);
let mut prover = Prover::new(mode);
let mut left: Vec<u32> = hypotheses.iter().map(|t| prover.tree(t)).collect();
left.sort_unstable();
let goal = prover.tree(goal);
prover.deepen(copies, |prover, budget| {
prover.two_sided(&left, goal, budget)
})
}
pub(crate) fn sequent(sequent: &Sequent, mode: Mode, copies: u32) -> Answer {
assert!(!mode.intuitionistic, "a one-sided sequent is classical");
let mut prover = Prover::new(mode);
let mut ids = HashMap::new();
let mut formulas: Vec<u32> = sequent
.roots()
.iter()
.map(|&root| prover.term(sequent, root, &mut ids))
.collect();
formulas.sort_unstable();
prover.deepen(copies, |prover, budget| prover.one_sided(&formulas, budget))
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
enum F {
Atom(u32),
Dual(u32),
One,
Bot,
Top,
Zero,
Tensor(u32, u32),
Par(u32, u32),
With(u32, u32),
Plus(u32, u32),
Bang(u32),
Quest(u32),
Lolli(u32, u32),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Found {
Proved,
Failed {
cut: bool,
},
}
#[derive(Clone, Copy, Debug, Default)]
struct Known {
proved: Option<u32>,
refuted: bool,
cut: Option<u32>,
}
impl Known {
fn at(&self, budget: u32) -> Option<Found> {
if self.proved.is_some_and(|b| b <= budget) {
Some(Found::Proved)
} else if self.refuted {
Some(Found::Failed { cut: false })
} else if self.cut.is_some_and(|b| b >= budget) {
Some(Found::Failed { cut: true })
} else {
None
}
}
fn record(&mut self, budget: u32, found: Found) {
match found {
Found::Proved => self.proved = Some(self.proved.map_or(budget, |b| b.min(budget))),
Found::Failed { cut: false } => self.refuted = true,
Found::Failed { cut: true } => {
self.cut = Some(self.cut.map_or(budget, |b| b.max(budget)))
}
}
}
}
struct Prover {
formulas: Vec<F>,
index: HashMap<F, u32>,
affine: bool,
mix: bool,
one_sided: HashMap<Vec<u32>, Known>,
two_sided: HashMap<(Vec<u32>, u32), Known>,
visits: usize,
gave_up: bool,
}
impl Prover {
fn new(mode: Mode) -> Self {
Self {
formulas: Vec::new(),
index: HashMap::new(),
affine: mode.affine,
mix: mode.mix,
one_sided: HashMap::new(),
two_sided: HashMap::new(),
visits: 0,
gave_up: false,
}
}
fn deepen(&mut self, copies: u32, mut search: impl FnMut(&mut Self, u32) -> Found) -> Answer {
for budget in 0..=copies {
if self.gave_up {
break;
}
match search(self, budget) {
Found::Proved => return Answer::Proved,
Found::Failed { cut: false } if !self.gave_up => return Answer::Unprovable,
Found::Failed { .. } => {}
}
}
Answer::Unknown
}
fn add(&mut self, f: F) -> u32 {
if let Some(&i) = self.index.get(&f) {
return i;
}
let i = self.formulas.len() as u32;
self.formulas.push(f);
self.index.insert(f, i);
i
}
fn tree(&mut self, t: &Tree) -> u32 {
let f = match t {
Tree::Atom(a) => F::Atom(u32::from(*a)),
Tree::Dual(a) => F::Dual(u32::from(*a)),
Tree::One => F::One,
Tree::Bot => F::Bot,
Tree::Top => F::Top,
Tree::Zero => F::Zero,
Tree::Tensor(l, r) => F::Tensor(self.tree(l), self.tree(r)),
Tree::Par(l, r) => F::Par(self.tree(l), self.tree(r)),
Tree::With(l, r) => F::With(self.tree(l), self.tree(r)),
Tree::Plus(l, r) => F::Plus(self.tree(l), self.tree(r)),
Tree::Bang(a) => F::Bang(self.tree(a)),
Tree::Quest(a) => F::Quest(self.tree(a)),
Tree::Lolli(l, r) => F::Lolli(self.tree(l), self.tree(r)),
};
self.add(f)
}
fn term(&mut self, sequent: &Sequent, id: TermId, ids: &mut HashMap<TermId, u32>) -> u32 {
if let Some(&i) = ids.get(&id) {
return i;
}
let f = match sequent.term(id) {
Term::Atom(a) => F::Atom(a.index() as u32),
Term::DualAtom(a) => F::Dual(a.index() as u32),
Term::One => F::One,
Term::Bot => F::Bot,
Term::Top => F::Top,
Term::Zero => F::Zero,
Term::Tensor(l, r) => F::Tensor(self.term(sequent, l, ids), self.term(sequent, r, ids)),
Term::Par(l, r) => F::Par(self.term(sequent, l, ids), self.term(sequent, r, ids)),
Term::With(l, r) => F::With(self.term(sequent, l, ids), self.term(sequent, r, ids)),
Term::Plus(l, r) => F::Plus(self.term(sequent, l, ids), self.term(sequent, r, ids)),
Term::Bang(a) => F::Bang(self.term(sequent, a, ids)),
Term::Quest(a) => F::Quest(self.term(sequent, a, ids)),
Term::Forall(_) | Term::Exists(_) => {
unreachable!("the reference prover decides propositional sequents alone")
}
};
let i = self.add(f);
ids.insert(id, i);
i
}
fn visit(&mut self) -> bool {
self.visits += 1;
if self.visits > VISITS {
self.gave_up = true;
}
self.gave_up
}
fn one_sided(&mut self, sequent: &[u32], budget: u32) -> Found {
if let Some(found) = self.one_sided.get(sequent).and_then(|k| k.at(budget)) {
return found;
}
if self.visit() {
return Found::Failed { cut: true };
}
let found = self.one_sided_rules(sequent, budget);
self.one_sided
.entry(sequent.to_vec())
.or_default()
.record(budget, found);
found
}
fn one_sided_rules(&mut self, sequent: &[u32], budget: u32) -> Found {
let mut cut = false;
let mut tried = |found: Found| match found {
Found::Proved => true,
Found::Failed { cut: c } => {
cut |= c;
false
}
};
for (i, &f) in sequent.iter().enumerate() {
if i > 0 && sequent[i - 1] == f {
continue;
}
let rest = without(sequent, i);
if self.affine && tried(self.one_sided(&rest, budget)) {
return Found::Proved;
}
let found = match self.formulas[f as usize] {
F::Atom(a) => {
let dual = self.index.get(&F::Dual(a)).copied();
if rest.len() == 1 && Some(rest[0]) == dual {
return Found::Proved;
}
continue;
}
F::Dual(_) | F::Zero => continue,
F::One if rest.is_empty() => return Found::Proved,
F::One => continue,
F::Top => return Found::Proved,
F::Bot => self.one_sided(&rest, budget),
F::Par(a, b) => self.one_sided(&with(&rest, &[a, b]), budget),
F::Plus(a, b) => {
if tried(self.one_sided(&with(&rest, &[a]), budget)) {
return Found::Proved;
}
self.one_sided(&with(&rest, &[b]), budget)
}
F::With(a, b) => {
self.both_one_sided(&with(&rest, &[a]), &with(&rest, &[b]), budget)
}
F::Tensor(a, b) => {
let mut found = Found::Failed { cut: false };
for (left, right) in splits(&rest) {
if self.visit() {
return Found::Failed { cut: true };
}
let attempt =
self.both_one_sided(&with(&left, &[a]), &with(&right, &[b]), budget);
if tried(attempt) {
return Found::Proved;
}
found = attempt;
}
found
}
F::Bang(a) => {
let all_quest = rest
.iter()
.all(|&g| matches!(self.formulas[g as usize], F::Quest(_)));
if !all_quest {
continue;
}
self.one_sided(&with(&rest, &[a]), budget)
}
F::Quest(a) => {
if tried(self.one_sided(&with(&rest, &[a]), budget))
|| tried(self.one_sided(&rest, budget))
{
return Found::Proved;
}
if budget == 0 {
Found::Failed { cut: true }
} else {
self.one_sided(&with(sequent, &[f]), budget - 1)
}
}
F::Lolli(..) => unreachable!("no ⊸ in a one-sided sequent"),
};
if tried(found) {
return Found::Proved;
}
}
if self.mix {
for (left, right) in splits(sequent) {
if self.visit() {
return Found::Failed { cut: true };
}
if left.is_empty() || right.is_empty() {
continue;
}
if tried(self.both_one_sided(&left, &right, budget)) {
return Found::Proved;
}
}
}
Found::Failed { cut }
}
fn both_one_sided(&mut self, first: &[u32], second: &[u32], budget: u32) -> Found {
match self.one_sided(first, budget) {
Found::Proved => self.one_sided(second, budget),
failed => failed,
}
}
fn two_sided(&mut self, hypotheses: &[u32], goal: u32, budget: u32) -> Found {
let key = (hypotheses.to_vec(), goal);
if let Some(found) = self.two_sided.get(&key).and_then(|k| k.at(budget)) {
return found;
}
if self.visit() {
return Found::Failed { cut: true };
}
let found = self.two_sided_rules(hypotheses, goal, budget);
self.two_sided.entry(key).or_default().record(budget, found);
found
}
fn two_sided_rules(&mut self, hypotheses: &[u32], goal: u32, budget: u32) -> Found {
let mut cut = false;
let mut tried = |found: Found| match found {
Found::Proved => true,
Found::Failed { cut: c } => {
cut |= c;
false
}
};
let found = match self.formulas[goal as usize] {
F::Atom(_) => {
if hypotheses == [goal] {
return Found::Proved;
}
Found::Failed { cut: false }
}
F::One if hypotheses.is_empty() => return Found::Proved,
F::One | F::Zero => Found::Failed { cut: false },
F::Top => return Found::Proved,
F::Tensor(a, b) => {
let mut found = Found::Failed { cut: false };
for (left, right) in splits(hypotheses) {
if self.visit() {
return Found::Failed { cut: true };
}
let attempt = self.both_two_sided((&left, a), (&right, b), budget);
if tried(attempt) {
return Found::Proved;
}
found = attempt;
}
found
}
F::Lolli(a, b) => self.two_sided(&with(hypotheses, &[a]), b, budget),
F::With(a, b) => self.both_two_sided((hypotheses, a), (hypotheses, b), budget),
F::Plus(a, b) => {
if tried(self.two_sided(hypotheses, a, budget)) {
return Found::Proved;
}
self.two_sided(hypotheses, b, budget)
}
F::Bang(a) => {
let all_bang = hypotheses
.iter()
.all(|&h| matches!(self.formulas[h as usize], F::Bang(_)));
if all_bang {
self.two_sided(hypotheses, a, budget)
} else {
Found::Failed { cut: false }
}
}
f => unreachable!("{f:?} is no intuitionistic goal"),
};
if tried(found) {
return Found::Proved;
}
for (i, &h) in hypotheses.iter().enumerate() {
if i > 0 && hypotheses[i - 1] == h {
continue;
}
let rest = without(hypotheses, i);
if self.affine && tried(self.two_sided(&rest, goal, budget)) {
return Found::Proved;
}
let found = match self.formulas[h as usize] {
F::Atom(_) | F::Top => continue,
F::Zero => return Found::Proved,
F::One => self.two_sided(&rest, goal, budget),
F::Tensor(a, b) => self.two_sided(&with(&rest, &[a, b]), goal, budget),
F::With(a, b) => {
if tried(self.two_sided(&with(&rest, &[a]), goal, budget)) {
return Found::Proved;
}
self.two_sided(&with(&rest, &[b]), goal, budget)
}
F::Plus(a, b) => self.both_two_sided(
(&with(&rest, &[a]), goal),
(&with(&rest, &[b]), goal),
budget,
),
F::Lolli(a, b) => {
let mut found = Found::Failed { cut: false };
for (left, right) in splits(&rest) {
if self.visit() {
return Found::Failed { cut: true };
}
let attempt =
self.both_two_sided((&left, a), (&with(&right, &[b]), goal), budget);
if tried(attempt) {
return Found::Proved;
}
found = attempt;
}
found
}
F::Bang(a) => {
if tried(self.two_sided(&with(&rest, &[a]), goal, budget))
|| tried(self.two_sided(&rest, goal, budget))
{
return Found::Proved;
}
if budget == 0 {
Found::Failed { cut: true }
} else {
self.two_sided(&with(hypotheses, &[h]), goal, budget - 1)
}
}
f => unreachable!("{f:?} is no intuitionistic hypothesis"),
};
if tried(found) {
return Found::Proved;
}
}
Found::Failed { cut }
}
fn both_two_sided(
&mut self,
first: (&[u32], u32),
second: (&[u32], u32),
budget: u32,
) -> Found {
match self.two_sided(first.0, first.1, budget) {
Found::Proved => self.two_sided(second.0, second.1, budget),
failed => failed,
}
}
}
fn without(sequent: &[u32], i: usize) -> Vec<u32> {
let mut rest = sequent.to_vec();
rest.remove(i);
rest
}
fn with(sequent: &[u32], added: &[u32]) -> Vec<u32> {
let mut larger = sequent.to_vec();
larger.extend_from_slice(added);
larger.sort_unstable();
larger
}
fn splits(sequent: &[u32]) -> Splits {
let mut runs: Vec<(u32, usize)> = Vec::new();
for &f in sequent {
match runs.last_mut() {
Some((g, n)) if *g == f => *n += 1,
_ => runs.push((f, 1)),
}
}
Splits {
taken: vec![0; runs.len()],
runs,
done: false,
}
}
struct Splits {
runs: Vec<(u32, usize)>,
taken: Vec<usize>,
done: bool,
}
impl Iterator for Splits {
type Item = (Vec<u32>, Vec<u32>);
fn next(&mut self) -> Option<Self::Item> {
if self.done {
return None;
}
let (mut left, mut right) = (Vec::new(), Vec::new());
for (&(f, n), &k) in self.runs.iter().zip(&self.taken) {
left.extend(std::iter::repeat_n(f, k));
right.extend(std::iter::repeat_n(f, n - k));
}
self.done = true;
for (k, &(_, n)) in self.taken.iter_mut().zip(&self.runs) {
if *k < n {
*k += 1;
self.done = false;
break;
}
*k = 0;
}
Some((left, right))
}
}
#[cfg(feature = "parse")]
mod tests {
use super::*;
use crate::Error;
use crate::linear::families::FAMILIES;
use crate::linear::search::Bias;
use crate::linear::search::generate::{self, IllRules, Rng, Rules};
use crate::linear::search::{Engine, Options, Verdict, prove_within};
fn configurations(copies: u32) -> Vec<(String, Options)> {
let base = Options::default().with_copies(Some(copies));
let mut all = vec![("dispatch".to_owned(), base.clone())];
for engine in [Engine::Net, Engine::Essential, Engine::Additive] {
all.push((format!("{engine}"), base.clone().with_engine(Some(engine))));
}
all.push((
"horn".to_owned(),
base.clone().with_engine(Some(Engine::Horn)),
));
all.push((
"inverse".to_owned(),
base.clone().with_engine(Some(Engine::Inverse)),
));
for engine in [Engine::Focus, Engine::TwoSided] {
for bias in [Bias::Auto, Bias::Rarer, Bias::Factors] {
all.push((
format!("{engine} {bias:?}"),
base.clone().with_engine(Some(engine)).with_bias(bias),
));
}
}
#[cfg(feature = "parallel")]
all.push((
"dispatch on two threads".to_owned(),
base.clone().with_jobs(2),
));
all
}
const INVERSE_POLLS: u64 = 1 << 8;
#[derive(Default)]
struct Tally {
cases: usize,
decided: usize,
judged: usize,
}
fn judge(text: &str, mode: Mode, copies: u32, reference: Answer, tally: &mut Tally) {
judge_within(text, mode, copies, reference, tally, u64::MAX);
}
fn judge_within(
text: &str,
mode: Mode,
copies: u32,
reference: Answer,
tally: &mut Tally,
polls: u64,
) {
let sequent: Sequent = text.parse().unwrap_or_else(|e| panic!("{text:?}: {e}"));
tally.cases += 1;
if reference != Answer::Unknown {
tally.decided += 1;
}
for (name, options) in configurations(copies) {
let mut left = match options.engine {
None | Some(Engine::Horn) => polls,
Some(Engine::Inverse) => polls.min(INVERSE_POLLS),
Some(_) => u64::MAX,
};
let stop = |_| {
left = left.saturating_sub(1);
left == 0
};
let limits = crate::Limits::default();
let outcome = match prove_within(&sequent, mode, &options, &limits, stop) {
Ok(outcome) => outcome,
Err(Error::EngineRefused { .. }) => continue,
Err(e) => panic!("{text:?} in {mode} mode, {name}: {e}"),
};
let contradiction = match outcome.verdict {
Verdict::Proved(_) => reference == Answer::Unprovable,
Verdict::Unprovable(_) => reference == Answer::Proved,
Verdict::Unknown(_) => false,
};
assert!(
!contradiction,
"{text:?} in {mode} mode within {copies} copies: {name} answers {:?}, the reference {reference:?}",
outcome.verdict
);
if reference != Answer::Unknown {
tally.judged += 1;
}
}
}
#[test]
fn agrees_with_the_families() {
for (name, sizes) in [
("3-partition-mll-yes", &[4][..]),
("3-partition-mll-no", &[4]),
("partition-yes", &[2]),
("qbf", &[3, 4]),
("wide-m1", &[2, 3, 4]),
("wide-m2", &[2, 4]),
("wide-m3", &[3]),
("wide-m4", &[4]),
("mix", &[1, 2, 3]),
("counter", &[2, 4]),
("counter-over", &[2, 4]),
("growing", &[1, 2]),
("chain", &[1, 2, 3]),
("additive", &[1, 2, 3]),
] {
let family = FAMILIES.iter().find(|f| f.name == name).unwrap();
for &size in sizes {
for index in 0..family.instances {
let instance = family.instance(size, index).unwrap();
let copies = instance.copies.unwrap_or(0);
let answer = super::sequent(&instance.sequent, instance.mode, copies);
let exponentials = instance.sequent.fragment().has_exponentials();
let expected = match (instance.provable, exponentials) {
(true, _) => answer == Answer::Proved,
(false, false) => answer == Answer::Unprovable,
(false, true) => answer != Answer::Proved,
};
assert!(expected, "{}: {answer:?}", instance.name);
}
}
}
}
#[test]
fn classical_engines_agree() {
let mut tally = Tally::default();
for (i, rules) in Rules::ALL.into_iter().enumerate() {
let mut rng = Rng::new(300 + i as u64);
for _ in 0..8 {
let budget = 2 + rng.below(8);
let generate::Provable {
mut formulas,
copies,
} = generate::provable(&mut rng, rules, 3, budget);
let mut cases = vec![formulas.clone()];
if generate::mutate(&mut rng, &mut formulas, 3) {
cases.push(formulas);
}
for formulas in &cases {
let text = generate::sequent(formulas);
for affine in [false, true] {
let mut mode = if rules.mix {
Mode::CLASSICAL.with_mix()
} else {
Mode::CLASSICAL
};
if affine {
mode = mode.with_affine();
}
let reference = classical(formulas, mode, copies);
judge(&text, mode, copies, reference, &mut tally);
}
}
}
}
assert!(
4 * tally.decided >= 3 * tally.cases,
"the reference decided {} of {} sequents ({} runs judged)",
tally.decided,
tally.cases,
tally.judged
);
}
#[test]
fn engines_agree_on_horn_programs() {
use Tree::{Atom, Bang, Bot, Dual, Lolli, One, Par, Quest, Tensor};
let b = Box::new;
fn join(atoms: &[u8], negated: bool) -> Tree {
let atom = |&a: &u8| if negated { Dual(a) } else { Atom(a) };
let unit = if negated { Bot } else { One };
atoms
.iter()
.map(atom)
.reduce(|l, r| {
if negated {
Par(Box::new(l), Box::new(r))
} else {
Tensor(Box::new(l), Box::new(r))
}
})
.unwrap_or(unit)
}
let mut rng = Rng::new(2_700);
let atoms = |rng: &mut Rng, most: usize| -> Vec<u8> {
(0..rng.below(most + 1))
.map(|_| rng.below(3) as u8)
.collect()
};
let mut tally = Tally::default();
for case in 0..100 {
let (mut hypotheses, mut formulas) = (Vec::new(), Vec::new());
let walk = case % 2 == 0;
let mut clauses = Vec::new();
for reusable in [true, true, false, false] {
if rng.below(2) == 0 || (walk && !reusable) {
continue;
}
let (body, head) = (atoms(&mut rng, 2), atoms(&mut rng, 2));
let clause = Lolli(b(join(&body, false)), b(join(&head, false)));
let negated = Tensor(b(join(&body, false)), b(join(&head, true)));
if reusable {
hypotheses.push(Bang(b(clause)));
formulas.push(Quest(b(negated)));
} else {
hypotheses.push(clause);
formulas.push(negated);
}
clauses.push((body, head));
}
let mut marking = atoms(&mut rng, 3);
for &a in &marking {
hypotheses.push(Atom(a));
formulas.push(Dual(a));
}
let goal = if walk {
for _ in 0..rng.below(3) {
let enabled: Vec<_> = clauses
.iter()
.filter(|(body, _)| {
body.iter().all(|a| {
body.iter().filter(|&b| b == a).count()
<= marking.iter().filter(|&b| b == a).count()
})
})
.collect();
if enabled.is_empty() {
break;
}
let (body, head) = enabled[rng.below(enabled.len())];
for a in body {
let at = marking.iter().position(|b| b == a).unwrap();
marking.remove(at);
}
marking.extend(head);
}
join(&marking, false)
} else {
join(&atoms(&mut rng, 2), false)
};
formulas.push(goal.clone());
let copies = 3;
let polls = 5_000;
let text = generate::two_sided(&hypotheses, &goal);
for mode in [Mode::INTUITIONISTIC, Mode::INTUITIONISTIC.with_affine()] {
let reference = intuitionistic(&hypotheses, &goal, mode, copies);
judge_within(&text, mode, copies, reference, &mut tally, polls);
}
let text = generate::sequent(&formulas);
for mode in [
Mode::CLASSICAL,
Mode::CLASSICAL.with_mix(),
Mode::CLASSICAL.with_affine(),
] {
let reference = classical(&formulas, mode, copies);
judge_within(&text, mode, copies, reference, &mut tally, polls);
}
}
assert!(
2 * tally.decided >= tally.cases,
"the reference decided {} of {} programs ({} runs judged)",
tally.decided,
tally.cases,
tally.judged
);
}
type OneSided = (Vec<Tree>, u32);
type TwoSided = (Vec<Tree>, Tree, u32);
fn contractions() -> (Vec<OneSided>, Vec<TwoSided>) {
use Tree::{Atom, Bang, Dual, Lolli, Quest, Tensor};
let b = Box::new;
let (a, c) = (|| Atom(0), || Atom(1));
let classical = vec![
(vec![Quest(b(Dual(0))), Tensor(b(a()), b(a()))], 2),
(
vec![Quest(b(Dual(0))), Tensor(b(Tensor(b(a()), b(a()))), b(a()))],
3,
),
(
vec![
Quest(b(Dual(0))),
Quest(b(Dual(1))),
Tensor(b(a()), b(Tensor(b(a()), b(c())))),
],
3,
),
];
let intuitionistic = vec![
(vec![Bang(b(a()))], Tensor(b(a()), b(a())), 2),
(
vec![Bang(b(a()))],
Tensor(b(Tensor(b(a()), b(a()))), b(a())),
3,
),
(
vec![Bang(b(Lolli(b(a()), b(c())))), a(), a()],
Tensor(b(c()), b(c())),
2,
),
(vec![Bang(b(a()))], Bang(b(Tensor(b(a()), b(a())))), 2),
];
(classical, intuitionistic)
}
#[test]
fn engines_agree_where_contractions_are_needed() {
let mut tally = Tally::default();
let (classical_cases, intuitionistic_cases) = contractions();
for (formulas, copies) in &classical_cases {
let text = generate::sequent(formulas);
for mode in [
Mode::CLASSICAL,
Mode::CLASSICAL.with_affine(),
Mode::CLASSICAL.with_mix(),
] {
let reference = classical(formulas, mode, *copies);
assert_eq!(reference, Answer::Proved, "{text:?} in {mode} mode");
judge(&text, mode, *copies, reference, &mut tally);
}
}
for (hypotheses, goal, copies) in &intuitionistic_cases {
let text = generate::two_sided(hypotheses, goal);
for mode in [Mode::INTUITIONISTIC, Mode::INTUITIONISTIC.with_affine()] {
let reference = intuitionistic(hypotheses, goal, mode, *copies);
assert_eq!(reference, Answer::Proved, "{text:?} in {mode} mode");
judge(&text, mode, *copies, reference, &mut tally);
}
}
}
#[test]
fn intuitionistic_engines_agree() {
let mut tally = Tally::default();
for (i, rules) in IllRules::ALL.into_iter().enumerate() {
let mut rng = Rng::new(400 + i as u64);
for _ in 0..8 {
let budget = 2 + rng.below(8);
let generate::Ill {
mut hypotheses,
mut goal,
copies,
..
} = generate::ill(&mut rng, rules, 3, budget);
let mut cases = vec![(hypotheses.clone(), goal.clone())];
if generate::mutate_two_sided(&mut rng, &mut hypotheses, &mut goal, 3) {
cases.push((hypotheses, goal));
}
for (hypotheses, goal) in &cases {
let text = generate::two_sided(hypotheses, goal);
for mode in [Mode::INTUITIONISTIC, Mode::INTUITIONISTIC.with_affine()] {
let reference = intuitionistic(hypotheses, goal, mode, copies);
judge(&text, mode, copies, reference, &mut tally);
}
}
}
}
assert!(
4 * tally.decided >= 3 * tally.cases,
"the reference decided {} of {} sequents ({} runs judged)",
tally.decided,
tally.cases,
tally.judged
);
}
fn additive(rng: &mut Rng, depth: usize, negated: bool) -> Tree {
let pick = if depth == 0 {
4 + rng.below(4)
} else {
rng.below(8)
};
let boxed = Box::new;
match pick {
0 | 1 => Tree::With(
boxed(additive(rng, depth - 1, negated)),
boxed(additive(rng, depth - 1, negated)),
),
2 | 3 => Tree::Plus(
boxed(additive(rng, depth - 1, negated)),
boxed(additive(rng, depth - 1, negated)),
),
4 if rng.one_in(3) => Tree::Top,
4 if rng.one_in(2) => Tree::Zero,
5 if negated => Tree::Dual(rng.below(3) as u8),
_ => Tree::Atom(rng.below(3) as u8),
}
}
#[test]
fn additive_engines_agree() {
let mut tally = Tally::default();
let mut rng = Rng::new(500);
for _ in 0..120 {
let (a, b) = (additive(&mut rng, 3, true), additive(&mut rng, 3, true));
let formulas = [a, b];
let text = generate::sequent(&formulas);
let reference = classical(&formulas, Mode::CLASSICAL, 0);
judge(&text, Mode::CLASSICAL, 0, reference, &mut tally);
let (a, b) = (additive(&mut rng, 3, false), additive(&mut rng, 3, false));
let text = generate::two_sided(std::slice::from_ref(&a), &b);
for mode in [Mode::INTUITIONISTIC, Mode::INTUITIONISTIC.with_affine()] {
let reference = intuitionistic(std::slice::from_ref(&a), &b, mode, 0);
judge(&text, mode, 0, reference, &mut tally);
}
}
assert_eq!(
tally.decided, tally.cases,
"the additive fragment is decided"
);
}
}