#![cfg_attr(feature = "parse", doc = "```")]
#![cfg_attr(not(feature = "parse"), doc = "```ignore")]
mod classical;
mod drup;
mod read_back;
mod solver;
pub use drup::ClausalProof;
use crate::kripke::{Model, World};
use self::solver::{Answer, Batsat, Lit, MOST_VARIABLES, Solver};
use super::{Derivation, Evidence, Formulas, Logic, Node, NodeId, Sequent, Verdict, ljt};
use crate::Error;
use crate::limits::{Limits, Progress, Refusal};
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,
pub model: Option<super::Countermodel>,
}
#[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 calls: u64,
pub conflicts: u64,
pub lemmas: u64,
pub worlds: u64,
pub facts: u64,
pub clauses: u64,
pub proof_steps: u64,
pub ljt: Option<ljt::Statistics>,
}
const POLL: u64 = 1 << 8;
const NEGATIVE: u8 = 1;
const POSITIVE: u8 = 2;
#[derive(Clone, Debug)]
struct Lemma {
body: Vec<NodeId>,
antecedent: NodeId,
consequent: NodeId,
made: NodeId,
}
pub fn decide(
sequent: &Sequent,
logic: Logic,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Outcome, Error> {
run(
sequent,
logic,
limits,
stop,
MOST_VARIABLES,
Derive::ReadOff,
)
}
pub fn decide_preferring_ljt(
sequent: &Sequent,
logic: Logic,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Outcome, Error> {
run(
sequent,
logic,
limits,
stop,
MOST_VARIABLES,
Derive::PreferLjt,
)
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Derive {
ReadOff,
#[cfg(test)]
Ljt,
PreferLjt,
}
fn run(
sequent: &Sequent,
logic: Logic,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
most: u32,
derive: Derive,
) -> Result<Outcome, Error> {
if logic == Logic::Classical {
return classical::decide(sequent, limits, stop, most);
}
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)?;
for id in 0..formulas.len() {
if let Node::Iff(a, b) = formulas.node(NodeId(id as u32)) {
formulas.add(Node::Implies(a, b))?;
formulas.add(Node::Implies(b, a))?;
}
}
let goal = sequent.right().first().copied().unwrap_or(falsity);
let polarity = polarities(&formulas, sequent.left(), goal, falsity);
let account = Account::holding(limits.memory_bytes, 0);
account.charge(formulas.len() * (4 * size_of::<Node>() + size_of::<u32>() + 1));
let mut statistics = Statistics::default();
let found = {
let work = limits.work.unwrap_or(u64::MAX);
let mut solver = Batsat::new(work, &account, &mut stop);
let found = Search::new(
&mut solver,
&formulas,
&polarity,
logic,
falsity,
most,
&account,
)
.and_then(|mut search| {
let found = search.run(sequent.left(), goal, &account);
statistics.lemmas = search.lemmas.len() as u64;
found.map(|found| (found, search.lemmas, search.nodes))
});
statistics.calls = solver.calls();
statistics.conflicts = solver.conflicts();
found
};
let (verdict, model) = match found {
Err(reason) => (Verdict::Unknown(reason), None),
Ok((Found::Worlds(worlds), _, nodes)) => {
statistics.worlds = worlds.len() as u64;
let cells = statistics
.worlds
.saturating_mul(sequent.formulas().len() as u64);
if cells > super::MODEL_CELLS {
(Verdict::NotValid, None)
} else {
match kripke(
&formulas,
logic,
(falsity, &nodes),
worlds,
&account,
&mut stop,
) {
Ok(model) => {
let model = super::Countermodel::found(
sequent.clone(),
model,
logic,
limits,
&mut stop,
)?;
(Verdict::NotValid, model)
}
Err(Reason::MemoryLimit { .. }) => (Verdict::NotValid, None),
Err(reason) => (Verdict::Unknown(reason), None),
}
}
}
Ok((Found::Valid, lemmas, _)) => {
let refused = Error::Refused(Refusal::Output {
what: "derivation",
estimate_bytes: 0,
limit_bytes: 0,
least_bytes: None,
});
let read = if matches!(derive, Derive::ReadOff | Derive::PreferLjt) {
read_back::derivation(
formulas,
logic,
&polarity,
(falsity, goal),
sequent.left(),
&lemmas,
limits,
account.used(),
&mut stop,
)
} else {
Err(refused)
};
let derivation = match read {
Ok((derivation, facts)) => {
statistics.facts = facts;
derivation
}
Err(Error::Refused(refusal)) if !matches!(refusal, Refusal::Stopped { .. }) => {
let (derivation, ljt) = by_ljt(sequent, logic, limits, &mut stop, refusal)?;
statistics.ljt = Some(ljt);
derivation
}
Err(error) => return Err(error),
};
derivation.check(limits, &mut stop)?;
let derivation = if derive == Derive::PreferLjt && statistics.ljt.is_none() {
prefer_ljt(
sequent,
logic,
limits,
&mut stop,
derivation,
&mut statistics,
)?
} else {
derivation
};
(
Verdict::Valid(Evidence::Derivation(Box::new(derivation))),
None,
)
}
};
Ok(Outcome {
verdict,
logic,
statistics,
model,
})
}
fn prefer_ljt(
sequent: &Sequent,
logic: Logic,
limits: &Limits,
stop: &mut impl FnMut(Progress) -> bool,
derivation: Derivation,
statistics: &mut Statistics,
) -> Result<Derivation, Error> {
let Ok(outcome) = ljt::decide(sequent, logic, limits, &mut *stop) else {
return Ok(derivation);
};
match outcome.verdict {
Verdict::Valid(Evidence::Derivation(ljt)) => {
statistics.ljt = Some(outcome.statistics);
Ok(*ljt)
}
Verdict::NotValid => Err(Error::ReadBack {
calculus: logic.calculus(),
reason: "LJT refutes a sequent the SAT search proved".to_owned(),
}),
Verdict::Valid(Evidence::Clausal(_) | Evidence::Image | Evidence::Table)
| Verdict::Unknown(_) => Ok(derivation),
}
}
fn by_ljt(
sequent: &Sequent,
logic: Logic,
limits: &Limits,
stop: &mut impl FnMut(Progress) -> bool,
refusal: Refusal,
) -> Result<(Derivation, ljt::Statistics), Error> {
let outcome = match ljt::decide(sequent, logic, limits, &mut *stop) {
Ok(outcome) => outcome,
Err(Error::Refused(stopped @ Refusal::Stopped { .. })) => {
return Err(Error::Refused(stopped));
}
Err(Error::Refused(_)) => return Err(Error::Refused(refusal)),
Err(other) => return Err(other),
};
match outcome.verdict {
Verdict::Valid(Evidence::Derivation(derivation)) => Ok((*derivation, outcome.statistics)),
Verdict::Valid(Evidence::Clausal(_)) => Err(Error::NoDerivation {
evidence: "a checked clausal proof",
}),
Verdict::Valid(Evidence::Image) => Err(Error::NotBuilt),
Verdict::Valid(Evidence::Table) => Err(Error::NoDerivation {
evidence: "its truth table",
}),
Verdict::Unknown(Reason::Stopped) => Err(Error::Refused(Refusal::Stopped {
phase: crate::limits::Phase::Search,
})),
Verdict::Unknown(_) => Err(Error::Refused(refusal)),
Verdict::NotValid => Err(Error::ReadBack {
calculus: logic.calculus(),
reason: "LJT refutes a sequent the SAT search proved".to_owned(),
}),
}
}
fn polarities(formulas: &Formulas, left: &[NodeId], goal: NodeId, falsity: NodeId) -> Vec<u8> {
let mut polarity = vec![0u8; formulas.len()];
for h in left {
polarity[h.index()] |= NEGATIVE;
}
polarity[goal.index()] |= POSITIVE;
for id in (0..formulas.len()).rev() {
let p = polarity[id];
if p == 0 {
continue;
}
let flipped = ((p & NEGATIVE) << 1) | ((p & POSITIVE) >> 1);
match formulas.node(NodeId(id as u32)) {
Node::Atom(_) | Node::True | Node::False => {}
Node::Not(a) => {
polarity[a.index()] |= flipped;
polarity[falsity.index()] |= p;
}
Node::And(a, b) | Node::Or(a, b) => {
polarity[a.index()] |= p;
polarity[b.index()] |= p;
}
Node::Implies(a, b) => {
polarity[a.index()] |= flipped;
polarity[b.index()] |= p;
}
Node::Iff(a, b) => {
polarity[a.index()] |= NEGATIVE | POSITIVE;
polarity[b.index()] |= NEGATIVE | POSITIVE;
for i in [Node::Implies(a, b), Node::Implies(b, a)] {
if let Some(i) = formulas.find(i) {
polarity[i.index()] |= p;
}
}
}
}
}
polarity
}
enum Found {
Valid,
Worlds(Vec<Bits>),
}
#[derive(Clone, Debug, PartialEq, Eq)]
struct Bits(Vec<u64>);
impl Bits {
fn new(len: usize) -> Self {
Self(vec![0; len.div_ceil(64)])
}
fn has(&self, v: u32) -> bool {
self.0[v as usize / 64] >> (v % 64) & 1 == 1
}
fn insert(&mut self, v: u32) {
self.0[v as usize / 64] |= 1 << (v % 64);
}
fn within(&self, other: &Self) -> bool {
self.0.iter().zip(&other.0).all(|(a, b)| a & !b == 0)
}
fn members(&self) -> impl Iterator<Item = u32> + '_ {
self.0.iter().enumerate().flat_map(|(k, &word)| {
(0..64u32)
.filter(move |b| word >> b & 1 == 1)
.map(move |b| k as u32 * 64 + b)
})
}
fn bytes(&self) -> usize {
self.0.len() * size_of::<u64>()
}
}
struct Search<'a, S> {
solver: &'a mut S,
nodes: Vec<NodeId>,
vars: Vec<Option<u32>>,
implications: Vec<[u32; 3]>,
lemmas: Vec<Lemma>,
}
impl<'a, S: Solver> Search<'a, S> {
fn new(
solver: &'a mut S,
formulas: &Formulas,
polarity: &[u8],
logic: Logic,
falsity: NodeId,
most: u32,
account: &Account,
) -> Result<Self, Reason> {
let over = || {
account.over().then(|| Reason::MemoryLimit {
limit_bytes: account.limit(),
})
};
let mut vars = vec![None; formulas.len()];
let mut nodes = Vec::new();
for (id, var) in vars.iter_mut().enumerate() {
if polarity[id] != 0 || id == falsity.index() {
if nodes.len() >= most as usize {
return Err(Reason::IndexLimit);
}
*var = Some(solver.new_var());
nodes.push(NodeId(id as u32));
if let Some(reason) = over() {
return Err(reason);
}
}
}
let var = |x: NodeId| vars[x.index()].unwrap_or_else(|| unreachable!("a name"));
let (pos, neg) = (|x| Lit::positive(var(x)), |x| Lit::negative(var(x)));
let mut clauses: Vec<Vec<Lit>> = Vec::new();
let mut implications = Vec::new();
let mut flush = |clauses: &mut Vec<Vec<Lit>>| {
for clause in clauses.drain(..) {
solver.add_clause(&clause);
}
over()
};
if logic == Logic::Intuitionistic {
clauses.push(vec![neg(falsity)]);
}
for (id, &p) in polarity.iter().enumerate() {
if let Some(reason) = flush(&mut clauses) {
return Err(reason);
}
if p == 0 {
continue;
}
let x = NodeId(id as u32);
let (negative, positive) = (p & NEGATIVE != 0, p & POSITIVE != 0);
match formulas.node(x) {
Node::Atom(_) | Node::False => {}
Node::True => {
if positive {
clauses.push(vec![pos(x)]);
}
}
Node::And(a, b) => {
if negative {
clauses.push(vec![neg(x), pos(a)]);
clauses.push(vec![neg(x), pos(b)]);
}
if positive {
clauses.push(vec![neg(a), neg(b), pos(x)]);
}
}
Node::Or(a, b) => {
if negative {
clauses.push(vec![neg(x), pos(a), pos(b)]);
}
if positive {
clauses.push(vec![neg(a), pos(x)]);
clauses.push(vec![neg(b), pos(x)]);
}
}
Node::Implies(a, b) => {
if negative {
clauses.push(vec![neg(x), neg(a), pos(b)]);
}
if positive {
clauses.push(vec![neg(b), pos(x)]);
implications.push([var(a), var(b), var(x)]);
}
}
Node::Not(a) => {
if negative {
clauses.push(vec![neg(x), neg(a), pos(falsity)]);
}
if positive {
clauses.push(vec![neg(falsity), pos(x)]);
implications.push([var(a), var(falsity), var(x)]);
}
}
Node::Iff(a, b) => {
let i = formulas.find(Node::Implies(a, b));
let j = formulas.find(Node::Implies(b, a));
let (Some(i), Some(j)) = (i, j) else {
unreachable!("the implications of every equivalence were added")
};
if negative {
clauses.push(vec![neg(x), pos(i)]);
clauses.push(vec![neg(x), pos(j)]);
}
if positive {
clauses.push(vec![neg(i), neg(j), pos(x)]);
}
}
}
}
if let Some(reason) = flush(&mut clauses) {
return Err(reason);
}
Ok(Self {
solver,
nodes,
vars,
implications,
lemmas: Vec::new(),
})
}
fn run(&mut self, left: &[NodeId], goal: NodeId, account: &Account) -> Result<Found, Reason> {
let var = |x: NodeId| self.vars[x.index()].unwrap_or_else(|| unreachable!("a name"));
let units: Vec<Lit> = left.iter().map(|&h| Lit::positive(var(h))).collect();
for unit in units {
self.solver.add_clause(&[unit]);
}
let goal = var(goal);
loop {
match self.solver.solve(&[Lit::negative(goal)]) {
Answer::Unsatisfiable => return Ok(Found::Valid),
Answer::Stopped(reason) => return Err(reason),
Answer::Satisfiable => {}
}
let mut worlds = vec![self.world()];
let mut held = worlds[0].bytes();
account.charge(held);
let learnt = self.realise(&mut worlds, account, &mut held);
match learnt {
Ok(true) => account.release(held),
Ok(false) => return Ok(Found::Worlds(worlds)),
Err(reason) => {
account.release(held);
return Err(reason);
}
}
}
}
fn realise(
&mut self,
worlds: &mut Vec<Bits>,
account: &Account,
held: &mut usize,
) -> Result<bool, Reason> {
let mut next: Vec<usize> = vec![0; worlds.len()];
let mut scanned = 0u64;
loop {
let mut pair = None;
'scan: for (w, at) in next.iter_mut().enumerate() {
while let Some(&[a, b, c]) = self.implications.get(*at) {
scanned += 1;
if scanned.is_multiple_of(POLL)
&& let Some(reason) = self.solver.poll(POLL)
{
return Err(reason);
}
if unrealised(worlds, w, [a, b, c]) {
pair = Some((w, [a, b, c]));
break 'scan;
}
*at += 1;
}
}
let Some((w, [a, b, c])) = pair else {
return Ok(false);
};
let mut assumptions = vec![Lit::positive(a), Lit::negative(b)];
assumptions.extend(worlds[w].members().map(Lit::positive));
match self.solver.solve(&assumptions) {
Answer::Satisfiable => {
let world = self.world();
*held += world.bytes();
account.charge(world.bytes());
worlds.push(world);
next.push(0);
if account.over() {
return Err(Reason::MemoryLimit {
limit_bytes: account.limit(),
});
}
next[w] += 1;
}
Answer::Unsatisfiable => {
let mut body: Vec<u32> = self
.solver
.failed()
.into_iter()
.filter(|l| l.is_positive() && l.var() != a)
.map(Lit::var)
.collect();
body.sort_unstable();
body.dedup();
let mut clause: Vec<Lit> = body.iter().map(|&v| Lit::negative(v)).collect();
clause.push(Lit::positive(c));
self.solver.add_clause(&clause);
let node = |v: u32| self.nodes[v as usize];
let mut body: Vec<NodeId> = body.into_iter().map(node).collect();
body.sort_unstable();
self.lemmas.push(Lemma {
body,
antecedent: node(a),
consequent: node(b),
made: node(c),
});
return Ok(true);
}
Answer::Stopped(reason) => return Err(reason),
}
}
}
fn world(&self) -> Bits {
let mut world = Bits::new(self.nodes.len());
for v in 0..self.nodes.len() as u32 {
if self.solver.value(Lit::positive(v)) {
world.insert(v);
}
}
world
}
}
fn unrealised(worlds: &[Bits], w: usize, [a, b, c]: [u32; 3]) -> bool {
let world = &worlds[w];
if world.has(a) || world.has(b) || world.has(c) {
return false;
}
!worlds
.iter()
.any(|other| other.has(a) && !other.has(b) && world.within(other))
}
fn kripke(
formulas: &Formulas,
logic: Logic,
(falsity, nodes): (NodeId, &[NodeId]),
mut worlds: Vec<Bits>,
account: &Account,
stop: &mut impl FnMut(Progress) -> bool,
) -> Result<Model, Reason> {
worlds.sort_by_key(|w| w.members().count());
let n = worlds.len();
let bytes = n.saturating_mul(Bits::new(n).bytes());
account.charge(bytes);
if account.over() {
account.release(bytes);
return Err(Reason::MemoryLimit {
limit_bytes: account.limit(),
});
}
let mut compared = 0u64;
let mut poll = |by: usize| {
let before = compared;
compared = compared.saturating_add(by as u64);
if before / POLL != compared / POLL
&& stop(Progress::new(crate::limits::Phase::Search, POLL, compared))
{
return Err(Reason::Stopped);
}
Ok(())
};
let found = (|| -> Result<Vec<Vec<u32>>, Reason> {
let mut below: Vec<Bits> = Vec::with_capacity(n);
for j in 0..n {
let mut set = Bits::new(n);
for i in 0..j {
poll(1)?;
if worlds[i] != worlds[j] && worlds[i].within(&worlds[j]) {
set.insert(i as u32);
}
}
below.push(set);
}
let mut above = vec![Vec::new(); n];
for (j, set) in below.iter().enumerate() {
let mut direct = set.clone();
for i in set.members() {
poll(1)?;
for (word, under) in direct.0.iter_mut().zip(&below[i as usize].0) {
*word &= !under;
}
}
for i in direct.members() {
above[i as usize].push(j as u32);
}
}
Ok(above)
})();
account.release(bytes);
let above = found?;
let models = worlds.iter().zip(above).map(|(world, above)| {
let mut atoms = Vec::new();
let mut forces_falsity = false;
for v in world.members() {
let x = nodes[v as usize];
match formulas.node(x) {
Node::Atom(a) => atoms.push(a),
Node::False if x == falsity && logic == Logic::Minimal => forces_falsity = true,
Node::True
| Node::False
| Node::Not(_)
| Node::And(..)
| Node::Or(..)
| Node::Implies(..)
| Node::Iff(..) => {}
}
}
atoms.sort_unstable();
let names = formulas.atom_names();
World::new(
atoms.iter().map(|&a| names[a as usize].clone()).collect(),
forces_falsity,
above,
)
});
Ok(Model::new(models.collect(), 0))
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::search::generate::Rng;
fn sat(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 agrees_with_ljt() {
const SEQUENTS: usize = 400;
let limits = Limits::default();
let mut rng = Rng::new(54);
let (mut proved, mut refuted) = (0, 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, &limits, |_| false)
.unwrap_or_else(|e| panic!("{sequent} in {logic} logic: {e}"));
let answer = match &outcome.verdict {
Verdict::Valid(evidence) => {
let derivation = evidence.derivation().unwrap();
assert_eq!(derivation.check(&limits, |_| false), Ok(()), "{sequent}");
assert_eq!(outcome.statistics.ljt, None, "{sequent}: read off");
proved += 1;
true
}
Verdict::NotValid => {
let model = &outcome.model.as_ref().unwrap().model;
assert_eq!(
model.refutes(&sequent, logic, &Limits::default(), |_| false),
Ok(())
);
refuted += 1;
false
}
Verdict::Unknown(reason) => panic!("{sequent} in {logic} logic: {reason:?}"),
};
let ljt = ljt::decide(&sequent, logic, &limits, |_| false).unwrap();
assert_eq!(
answer,
matches!(ljt.verdict, Verdict::Valid(_)),
"{sequent} in {logic} logic"
);
}
}
assert!(
proved >= SEQUENTS / 4 && refuted >= SEQUENTS / 4,
"{proved}, {refuted}"
);
}
#[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),
("(a <-> b) <-> (b <-> a)", true, true),
("|- true", true, true),
("false |- false", true, true),
];
for (text, intuitionistic, minimal) in cases {
assert_eq!(
valid(&sat(text, Logic::Intuitionistic)),
intuitionistic,
"{text}"
);
assert_eq!(
valid(&sat(text, Logic::Minimal)),
minimal,
"{text} minimally"
);
}
assert!(valid(&sat("|- a \\/ ~a", Logic::Classical)));
}
#[test]
fn a_planted_wrong_model_is_refused() {
let text = "((a -> b) -> a) -> a";
let sequent: Sequent = text.parse().unwrap();
let logic = Logic::Intuitionistic;
let model = sat(text, logic).model.unwrap().model;
assert_eq!(
model.refutes(&sequent, logic, &Limits::default(), |_| false),
Ok(())
);
assert!(model.worlds.len() >= 2, "{model:?}");
let refused = |model: &Model, why: &str| {
let Err(Error::Model { reason }) =
model.refutes(&sequent, logic, &Limits::default(), |_| false)
else {
panic!("{why}: {model:?} is accepted");
};
assert!(reason.contains(why), "{reason} for {why}");
};
let both = || vec!["a".to_owned(), "b".to_owned()];
let mut planted = model.clone();
for world in &mut planted.worlds {
world.atoms = both();
}
refused(&planted, "forces the conclusion");
let mut planted = model.clone();
let up = planted.worlds[0].arrows[0] as usize;
planted.worlds[0].atoms.push("a".to_owned());
planted.worlds[up].atoms.clear();
refused(&planted, "does not force all it forces");
let mut planted = model.clone();
planted.worlds.truncate(1);
planted.worlds[0].arrows.clear();
refused(&planted, "forces the conclusion");
let mut planted = model.clone();
let last = planted.worlds.len() - 1;
planted.worlds[last].arrows.push(last as u32);
refused(&planted, "the arrows go round");
let mut planted = model.clone();
planted.worlds[0].arrows.push(99);
refused(&planted, "which the model does not have");
let mut planted = model.clone();
planted.worlds[0].falsity = true;
refused(&planted, "forces ⊥ in intuitionistic logic");
let mut planted = model;
planted.world = 99;
refused(&planted, "is not one of its");
}
#[test]
fn the_search_keeps_to_its_bounds() {
let sequent: Sequent = "((a -> b) -> a) -> a".parse().unwrap();
let logic = Logic::Intuitionistic;
let free = decide(&sequent, logic, &Limits::default(), |_| false).unwrap();
assert!(matches!(free.verdict, Verdict::NotValid));
let calls = free.statistics.calls;
assert!(calls > 2, "{calls}");
let at = |work| Limits::default().with_work(Some(work));
let outcome = decide(&sequent, logic, &at(calls - 1), |_| false).unwrap();
assert!(matches!(
outcome.verdict,
Verdict::Unknown(Reason::WorkLimit { .. })
));
let outcome = decide(&sequent, logic, &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, &tight, |_| false).unwrap();
assert!(matches!(
outcome.verdict,
Verdict::Unknown(Reason::MemoryLimit { .. })
));
let outcome = run(
&sequent,
logic,
&Limits::default(),
|_| false,
5,
Derive::ReadOff,
)
.unwrap();
assert!(matches!(
outcome.verdict,
Verdict::Unknown(Reason::IndexLimit)
));
assert!(matches!(
run(
&sequent,
logic,
&Limits::default(),
|_| false,
6,
Derive::ReadOff
)
.unwrap()
.verdict,
Verdict::NotValid
));
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, &small, |_| false),
Err(Error::Refused(Refusal::Output { .. }))
));
let chain: Vec<String> = (0..1 << 14).map(|i| format!("a{i}")).collect();
let sequent: Sequent = format!("|- {}", chain.join(" /\\ ")).parse().unwrap();
let worlds = (super::super::MODEL_CELLS as usize).div_ceil(sequent.formulas().len()) + 1;
let model = Model::new(vec![World::default(); worlds], 0);
assert!(matches!(
model.refutes(&sequent, logic, &Limits::default(), |_| false),
Err(Error::Refused(Refusal::Memory { .. }))
));
}
#[test]
fn the_scan_of_the_worlds_asks_the_stop() {
let k = 64;
let chain: Vec<String> = (0..k).map(|i| format!("(a{i} -> a{})", i + 1)).collect();
let sequent: Sequent = format!("|- {}", chain.join(" \\/ ")).parse().unwrap();
let logic = Logic::Intuitionistic;
let mut scans = 0;
let free = decide(&sequent, logic, &Limits::default(), |p| {
scans += u64::from(p.work == POLL);
false
})
.unwrap();
assert_eq!(free.statistics.worlds, k + 1);
assert!(scans >= k * k / POLL, "{scans}");
let mut asked = 0;
let outcome = decide(&sequent, logic, &Limits::default(), |p| {
asked += u64::from(p.work == POLL);
asked == scans
})
.unwrap();
assert!(matches!(outcome.verdict, Verdict::Unknown(Reason::Stopped)));
}
#[test]
fn the_model_s_order_keeps_to_its_bounds() {
let sequent: Sequent = "|- a".parse().unwrap();
let formulas = sequent.formulas();
let n = 1000;
let chain = || {
(0..n)
.map(|k| {
let mut world = Bits::new(n);
(0..k).for_each(|v| world.insert(v as u32));
world
})
.collect::<Vec<_>>()
};
let nodes = vec![NodeId(0); n];
let free = Account::holding(None, 0);
let model = kripke(
formulas,
Logic::Intuitionistic,
(NodeId(0), &nodes),
chain(),
&free,
&mut |_| false,
);
let model = model.unwrap();
assert_eq!(model.worlds[0].arrows, vec![1]);
assert_eq!(free.used(), 0);
let small = Account::holding(Some(n as u64 * 8), 0);
let refused = kripke(
formulas,
Logic::Intuitionistic,
(NodeId(0), &nodes),
chain(),
&small,
&mut |_| false,
);
assert!(matches!(refused, Err(Reason::MemoryLimit { .. })));
let stopped = kripke(
formulas,
Logic::Intuitionistic,
(NodeId(0), &nodes),
chain(),
&free,
&mut |_| true,
);
assert!(matches!(stopped, Err(Reason::Stopped)));
}
#[test]
fn ljt_gives_the_derivation_the_read_back_cannot() {
let sequent: Sequent = "a, a -> b, b -> c |- c".parse().unwrap();
let logic = Logic::Intuitionistic;
let outcome = run(
&sequent,
logic,
&Limits::default(),
|_| false,
MOST_VARIABLES,
Derive::Ljt,
);
let outcome = outcome.unwrap();
assert!(matches!(outcome.verdict, Verdict::Valid(_)), "{outcome:?}");
assert!(outcome.statistics.ljt.is_some(), "{:?}", outcome.statistics);
let search = |p: &Progress| p.phase == crate::limits::Phase::Search;
let mut solver = 0;
let counted = |p: Progress| {
solver += u64::from(search(&p));
false
};
run(
&sequent,
logic,
&Limits::default(),
counted,
MOST_VARIABLES,
Derive::ReadOff,
)
.unwrap();
let mut asked = 0;
let ljt = |p: Progress| {
asked += u64::from(search(&p));
asked > solver
};
let stopped = run(
&sequent,
logic,
&Limits::default(),
ljt,
MOST_VARIABLES,
Derive::Ljt,
);
assert!(
matches!(stopped, Err(Error::Refused(Refusal::Stopped { .. }))),
"{stopped:?}"
);
}
}