use super::drup::{ClausalProof, Rejection, Step};
use super::solver::{Answer, Batsat, Lit, Solver};
use super::{Outcome, Statistics};
use crate::Error;
use crate::kripke::{Model, World};
use crate::limits::{Limits, Phase, Progress};
use crate::linear::search::Reason;
use crate::linear::search::memory::Account;
use crate::ordinary::{Evidence, Formulas, Logic, Node, NodeId, Sequent, Verdict};
const TRUE: u8 = 1;
const FALSE: u8 = 2;
pub(super) struct Encoding {
pub(super) vars: Vec<Option<u32>>,
pub(super) variables: u32,
pub(super) clauses: Vec<Vec<Lit>>,
}
fn polarities(formulas: &Formulas, left: &[NodeId], right: &[NodeId]) -> Vec<u8> {
let mut polarity = vec![0u8; formulas.len()];
for h in left {
polarity[h.index()] |= TRUE;
}
for c in right {
polarity[c.index()] |= FALSE;
}
for id in (0..formulas.len()).rev() {
let p = polarity[id];
if p == 0 {
continue;
}
let flipped = ((p & TRUE) << 1) | ((p & FALSE) >> 1);
match formulas.node(NodeId(id as u32)) {
Node::Atom(_) | Node::True | Node::False => {}
Node::Not(a) => polarity[a.index()] |= flipped,
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()] |= TRUE | FALSE;
polarity[b.index()] |= TRUE | FALSE;
}
}
}
polarity
}
const POLL: usize = 1 << 12;
const CLAUSE_BYTES: usize = size_of::<Vec<Lit>>() + 16;
pub(super) fn encode(
formulas: &Formulas,
left: &[NodeId],
right: &[NodeId],
most: u32,
account: &Account,
stop: &mut impl FnMut(Progress) -> bool,
) -> Result<Encoding, Reason> {
let over = || {
account.over().then(|| Reason::MemoryLimit {
limit_bytes: account.limit(),
})
};
let polarity = polarities(formulas, left, right);
let mut vars = vec![None; formulas.len()];
let mut variables = 0u32;
for (var, &p) in vars.iter_mut().zip(&polarity) {
if p != 0 {
if variables >= most {
return Err(Reason::IndexLimit);
}
*var = Some(variables);
variables += 1;
}
}
let var = |x: NodeId| vars[x.index()].unwrap_or_else(|| unreachable!("a polarity"));
let (t, f) = (|x| Lit::positive(var(x)), |x| Lit::negative(var(x)));
let mut clauses: Vec<Vec<Lit>> = Vec::new();
let mut add = |clause: Vec<Lit>| {
account.charge(clause.len() * size_of::<Lit>() + CLAUSE_BYTES);
clauses.push(clause);
over()
};
for h in left {
add(vec![t(*h)]).map_or(Ok(()), Err)?;
}
for c in right {
add(vec![f(*c)]).map_or(Ok(()), Err)?;
}
for (id, &p) in polarity.iter().enumerate() {
if id % POLL == 0 && stop(Progress::new(Phase::Search, POLL as u64, 0)) {
return Err(Reason::Stopped);
}
if p == 0 {
continue;
}
let x = NodeId(id as u32);
let (forward, backward) = (p & TRUE != 0, p & FALSE != 0);
let mut definition: Vec<Vec<Lit>> = Vec::new();
match formulas.node(x) {
Node::Atom(_) => {}
Node::True => {
if backward {
definition.push(vec![t(x)]);
}
}
Node::False => {
if forward {
definition.push(vec![f(x)]);
}
}
Node::Not(a) => {
if forward {
definition.push(vec![f(x), f(a)]);
}
if backward {
definition.push(vec![t(a), t(x)]);
}
}
Node::And(a, b) => {
if forward {
definition.push(vec![f(x), t(a)]);
definition.push(vec![f(x), t(b)]);
}
if backward {
definition.push(vec![f(a), f(b), t(x)]);
}
}
Node::Or(a, b) => {
if forward {
definition.push(vec![f(x), t(a), t(b)]);
}
if backward {
definition.push(vec![f(a), t(x)]);
definition.push(vec![f(b), t(x)]);
}
}
Node::Implies(a, b) => {
if forward {
definition.push(vec![f(x), f(a), t(b)]);
}
if backward {
definition.push(vec![t(a), t(x)]);
definition.push(vec![f(b), t(x)]);
}
}
Node::Iff(a, b) => {
if forward {
definition.push(vec![f(x), f(a), t(b)]);
definition.push(vec![f(x), t(a), f(b)]);
}
if backward {
definition.push(vec![t(a), t(b), t(x)]);
definition.push(vec![f(a), f(b), t(x)]);
}
}
}
for clause in definition {
add(clause).map_or(Ok(()), Err)?;
}
}
Ok(Encoding {
vars,
variables,
clauses,
})
}
pub(super) fn decide(
sequent: &Sequent,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
most: u32,
) -> Result<Outcome, Error> {
let logic = Logic::Classical;
let formulas = sequent.formulas();
let account = Account::holding(limits.memory_bytes, 0);
let mut statistics = Statistics::default();
let encoded = encode(
formulas,
sequent.left(),
sequent.right(),
most,
&account,
&mut stop,
);
let found = encoded.and_then(|clauses| {
statistics.clauses = clauses.clauses.len() as u64;
let work = limits.work.unwrap_or(u64::MAX);
let mut solver = Batsat::recording(work, &account, &mut stop);
for _ in 0..clauses.variables {
solver.new_var();
}
for (n, clause) in clauses.clauses.iter().enumerate() {
solver.add_clause(clause);
if n % POLL == 0
&& let Some(reason) = solver.poll(POLL as u64)
{
return Err(reason);
}
}
let answer = solver.solve(&[]);
statistics.calls = solver.calls();
statistics.conflicts = solver.conflicts();
match answer {
Answer::Satisfiable => {
let atoms = assignment(formulas, &clauses, &solver);
Ok(Found::Assignment(atoms))
}
Answer::Unsatisfiable => {
let mut proof = solver.proof().unwrap_or_default();
account.charge(Step::bytes(0));
proof.push(Step::Add(Box::new([])));
Ok(Found::Proof(clauses, proof))
}
Answer::Stopped(reason) => Err(reason),
}
});
let (verdict, model) = match found {
Err(reason) => (Verdict::Unknown(reason), None),
Ok(Found::Assignment(atoms)) => {
statistics.worlds = 1;
let names = sequent.formulas().atom_names();
let atoms = atoms.iter().map(|&a| names[a as usize].clone()).collect();
let model = Model::new(vec![World::new(atoms, false, Vec::new())], 0);
let model = super::super::Countermodel::found(
sequent.clone(),
model,
logic,
limits,
&mut stop,
)?;
(Verdict::NotValid, model)
}
Ok(Found::Proof(clauses, proof)) => {
statistics.proof_steps = proof.len() as u64;
let held = clauses
.clauses
.iter()
.map(|c| c.len() * size_of::<Lit>() + size_of::<Vec<Lit>>())
.chain(proof.iter().map(|step| {
let (Step::Add(c) | Step::Delete(c)) = step;
Step::bytes(c.len())
}))
.sum::<usize>();
let account = Account::holding(limits.memory_bytes, held as u64);
match ClausalProof::checked(
clauses.variables,
&clauses.clauses,
&proof,
limits,
&account,
&mut stop,
) {
Ok(checked) => (Verdict::Valid(Evidence::Clausal(checked)), None),
Err(Rejection::Refused(refusal)) => return Err(Error::Refused(refusal)),
Err(Rejection::Flaw(flaw)) => {
return Err(Error::ReadBack {
calculus: logic.calculus(),
reason: format!("the solver's clausal proof fails its check: {flaw}"),
});
}
}
}
};
Ok(Outcome {
verdict,
logic,
statistics,
model,
})
}
enum Found {
Assignment(Vec<u32>),
Proof(Encoding, Vec<Step>),
}
fn assignment(formulas: &Formulas, clauses: &Encoding, solver: &impl Solver) -> Vec<u32> {
let mut atoms: Vec<u32> = (0..formulas.len())
.filter_map(|id| match formulas.node(NodeId(id as u32)) {
Node::Atom(a) => clauses.vars[id]
.filter(|&v| solver.value(Lit::positive(v)))
.map(|_| a),
Node::True
| Node::False
| Node::Not(_)
| Node::And(..)
| Node::Or(..)
| Node::Implies(..)
| Node::Iff(..) => None,
})
.collect();
atoms.sort_unstable();
atoms
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::super::{MOST_VARIABLES, drup};
use super::*;
use crate::limits::Refusal;
use crate::linear::search;
use crate::linear::search::generate::Rng;
use crate::ordinary::tests::{generated_sequent, valid_by_truth_table};
use crate::ordinary::{Method, Options};
fn pigeons(n: usize) -> Sequent {
let mut hypotheses = Vec::new();
for i in 0..=n {
let holes: Vec<String> = (0..n).map(|j| format!("p{i}h{j}")).collect();
hypotheses.push(holes.join(" \\/ "));
}
for j in 0..n {
for i in 0..=n {
for k in i + 1..=n {
hypotheses.push(format!("~(p{i}h{j} /\\ p{k}h{j})"));
}
}
}
format!("{} |-", hypotheses.join(", ")).parse().unwrap()
}
fn refuted(sequent: &Sequent) -> (Encoding, Vec<Step>) {
let account = Account::holding(None, 0);
let clauses = encode(
sequent.formulas(),
sequent.left(),
sequent.right(),
MOST_VARIABLES,
&account,
&mut |_| false,
)
.unwrap();
let mut stop = |_| false;
let mut solver = Batsat::recording(u64::MAX, &account, &mut stop);
for _ in 0..clauses.variables {
solver.new_var();
}
for clause in &clauses.clauses {
solver.add_clause(clause);
}
assert_eq!(solver.solve(&[]), Answer::Unsatisfiable);
let mut proof = solver.proof().unwrap();
proof.push(Step::Add(Box::new([])));
(clauses, proof)
}
fn checked(clauses: &Encoding, proof: &[Step]) -> Result<(), Rejection> {
let limits = Limits::default();
let account = Account::holding(limits.memory_bytes, 0);
drup::check(
clauses.variables,
&clauses.clauses,
proof,
&limits,
&account,
|_| false,
)
}
#[test]
fn agrees_with_the_truth_table_and_the_embedding() {
let limits = Limits::default();
let mut rng = Rng::new(54);
let written = [
"a \\/ ~a",
"((a -> b) -> a) -> a",
"a \\/ b |- a, b",
"a |- b, c",
"|-",
"a, ~a |-",
"false |-",
"|- true",
"true |- false",
"(a <-> b) <-> (b <-> a)",
"a <-> b, b |- a",
"a |- a",
]
.map(|text| text.parse::<Sequent>().unwrap());
let generated = (0..400).map(|_| generated_sequent(&mut rng));
let (mut proved, mut refuted) = (0, 0);
for sequent in written.into_iter().chain(generated) {
let outcome = decide(&sequent, &limits, |_| false, MOST_VARIABLES)
.unwrap_or_else(|e| panic!("{sequent}: {e}"));
let valid = match &outcome.verdict {
Verdict::Valid(Evidence::Clausal(proof)) => {
assert_eq!(proof.steps(), outcome.statistics.proof_steps, "{sequent}");
assert_eq!(proof.clauses(), outcome.statistics.clauses, "{sequent}");
assert!(proof.steps() > 0, "{sequent}");
proved += 1;
true
}
Verdict::NotValid => {
let model = &outcome.model.as_ref().unwrap().model;
assert_eq!(model.worlds.len(), 1, "{sequent}");
assert_eq!(
model.refutes(&sequent, Logic::Classical, &Limits::default(), |_| false),
Ok(())
);
refuted += 1;
false
}
verdict @ (Verdict::Valid(
Evidence::Derivation(_) | Evidence::Image | Evidence::Table,
)
| Verdict::Unknown(_)) => {
panic!("{sequent}: {verdict:?}")
}
};
assert_eq!(valid, valid_by_truth_table(&sequent), "{sequent}");
let options = Options::default().with_logic(Logic::Classical);
let embedded = crate::ordinary::decide_within(
&sequent,
&options,
&search::Options::default(),
&limits,
|_| false,
)
.unwrap();
assert_eq!(
valid,
matches!(embedded.verdict, Verdict::Valid(_)),
"{sequent}"
);
}
assert!(
proved > 50 && refuted > 50,
"{proved} proved, {refuted} refuted"
);
}
#[test]
fn a_planted_wrong_proof_step_is_refused() {
let sequent = pigeons(4);
let (clauses, proof) = refuted(&sequent);
assert_eq!(checked(&clauses, &proof), Ok(()));
let last = proof.len() - 1;
assert!(last > 1, "{proof:?}");
assert_eq!(
checked(&clauses, &proof[last..]),
Err(Rejection::Flaw(drup::Flaw::NotRup { step: 0 }))
);
let mut planted = proof.clone();
let first = Lit::positive(clauses.vars[0].unwrap());
assert!(matches!(sequent.formulas().node(NodeId(0)), Node::Atom(_)));
planted.insert(0, Step::Add(Box::new([first])));
assert_eq!(
checked(&clauses, &planted),
Err(Rejection::Flaw(drup::Flaw::NotRup { step: 0 }))
);
let sequent: Sequent = "a |- a, b".parse().unwrap();
let model = Model::new(vec![World::new(vec!["a".to_owned()], false, Vec::new())], 0);
let Err(Error::Model { reason }) =
model.refutes(&sequent, Logic::Classical, &Limits::default(), |_| false)
else {
panic!("a true conclusion accepted");
};
assert!(reason.contains("forces the conclusion"), "{reason}");
let two = Model::new(vec![model.worlds[0].clone(), World::default()], 0);
assert!(
two.refutes(&sequent, Logic::Classical, &Limits::default(), |_| false)
.is_err()
);
}
#[test]
fn the_search_and_the_check_keep_to_their_bounds() {
let sequent = pigeons(7);
let (_, proof) = refuted(&sequent);
let adds = proof.iter().filter(|s| matches!(s, Step::Add(_))).count() as u64;
let deletions = proof.len() as u64 - adds;
assert!(
deletions > 0 && adds > 100,
"{adds} added, {deletions} deleted"
);
let limits = Limits::default();
let at = |work| limits.with_work(Some(work));
let outcome = decide(&sequent, &at(adds / 2), |_| false, MOST_VARIABLES).unwrap();
assert!(matches!(
outcome.verdict,
Verdict::Unknown(Reason::WorkLimit { .. })
));
let outcome = decide(&sequent, &limits, |_| true, MOST_VARIABLES).unwrap();
assert!(matches!(outcome.verdict, Verdict::Unknown(Reason::Stopped)));
let tight = limits.with_memory_bytes(Some(1024));
let outcome = decide(&sequent, &tight, |_| false, MOST_VARIABLES).unwrap();
assert!(matches!(
outcome.verdict,
Verdict::Unknown(Reason::MemoryLimit { .. })
));
let outcome = decide(&sequent, &limits, |_| false, 3).unwrap();
assert!(matches!(
outcome.verdict,
Verdict::Unknown(Reason::IndexLimit)
));
assert!(matches!(
decide(&sequent, &at(adds), |_| false, MOST_VARIABLES),
Err(Error::Refused(Refusal::Work { limit })) if limit == adds
));
}
#[test]
fn valid_by_the_clausal_proof_where_the_embedding_stops() {
let options = Options::default()
.with_logic(Logic::Classical)
.with_method(Some(Method::Embedding));
let embedded = |sequent: &Sequent, limits: &Limits| {
crate::ordinary::decide_within(
sequent,
&options,
&search::Options::default(),
limits,
|_| false,
)
.unwrap()
.verdict
};
let peirce: Sequent = "|- ((a -> b) -> a) -> a".parse().unwrap();
let shallow = Limits::default().with_recursion_depth(1);
let pigeons = pigeons(5);
let short = Limits::default().with_work(Some(100_000));
for (sequent, limits) in [(&peirce, &shallow), (&pigeons, &short)] {
assert!(
matches!(embedded(sequent, limits), Verdict::Unknown(_)),
"{sequent}"
);
let outcome = decide(sequent, limits, |_| false, MOST_VARIABLES).unwrap();
let Verdict::Valid(evidence @ Evidence::Clausal(proof)) = &outcome.verdict else {
panic!("{sequent}: {:?}", outcome.verdict);
};
assert_eq!(proof.steps(), outcome.statistics.proof_steps);
assert!(matches!(
evidence.derivation(),
Err(Error::NoDerivation { .. })
));
}
let Verdict::Valid(evidence) = embedded(&peirce, &Limits::default()) else {
panic!("the embedding proves Peirce's law");
};
assert!(evidence.derivation().is_ok());
}
#[cfg(feature = "serialize")]
#[test]
fn a_clausal_proof_is_written_as_its_counts() {
let sequent: Sequent = "|- ((a -> b) -> a) -> a".parse().unwrap();
let outcome = decide(&sequent, &Limits::default(), |_| false, MOST_VARIABLES).unwrap();
let Verdict::Valid(Evidence::Clausal(proof)) = outcome.verdict else {
panic!("{:?}", outcome.verdict);
};
let ordinary = crate::ordinary::Outcome::from(outcome);
let json = serde_json::to_value(&ordinary).unwrap();
assert_eq!(json["version"], crate::wire::SEARCH);
assert_eq!(json["verdict"], "valid");
assert_eq!(json["search"]["method"], "sat");
assert!(json.get("derivation").is_none(), "{json}");
assert_eq!(
json["clausal_proof"],
serde_json::json!({
"variables": proof.variables(),
"clauses": proof.clauses(),
"steps": proof.steps(),
})
);
assert_eq!(json["search"]["statistics"]["proof_steps"], proof.steps());
let options = Options::default().with_logic(Logic::Classical);
let embedded = crate::ordinary::decide_within(
&sequent,
&options,
&search::Options::default(),
&Limits::default(),
|_| false,
)
.unwrap();
let json = serde_json::to_value(&embedded).unwrap();
assert_eq!(json["version"], crate::wire::SEARCH);
assert!(json.get("clausal_proof").is_none(), "{json}");
}
#[test]
fn the_encoder_asks_the_stop() {
let atoms: Vec<String> = (0..3 * POLL).map(|i| format!("a{i}")).collect();
let sequent: Sequent = format!("{} |-", atoms.join(" /\\ ")).parse().unwrap();
let mut asked = 0;
let outcome = decide(
&sequent,
&Limits::default(),
|_| {
asked += 1;
asked > 1
},
MOST_VARIABLES,
)
.unwrap();
assert!(matches!(outcome.verdict, Verdict::Unknown(Reason::Stopped)));
assert_eq!(outcome.statistics.calls, 0);
}
#[test]
#[ignore = "needs drat-trim on the PATH: nix shell nixpkgs#drat-trim"]
fn drat_trim_accepts_the_proof() {
let directory = std::env::temp_dir().join(format!("deduxit-drup-{}", std::process::id()));
std::fs::create_dir_all(&directory).unwrap();
for (name, sequent) in [
("peirce", "|- ((a -> b) -> a) -> a".parse().unwrap()),
("pigeons-7", pigeons(7)),
] {
let (clauses, proof) = refuted(&sequent);
assert_eq!(checked(&clauses, &proof), Ok(()), "{name}");
let deletions = proof
.iter()
.filter(|s| matches!(s, Step::Delete(_)))
.count();
let (cnf, drup) = drup::dimacs(clauses.variables, &clauses.clauses, &proof);
let (cnf_path, drup_path) = (
directory.join(format!("{name}.cnf")),
directory.join(format!("{name}.drup")),
);
std::fs::write(&cnf_path, cnf).unwrap();
std::fs::write(&drup_path, drup).unwrap();
let output = std::process::Command::new("drat-trim")
.arg(&cnf_path)
.arg(&drup_path)
.output()
.expect("drat-trim on the PATH");
let text = String::from_utf8_lossy(&output.stdout);
println!(
"{name}: {} clauses, {} steps, {deletions} deletions\n{text}",
clauses.clauses.len(),
proof.len()
);
assert!(
text.lines().any(|l| l.trim() == "s VERIFIED"),
"{name}: {text}"
);
if name == "pigeons-7" {
assert!(deletions > 0, "{name} deletes no clause");
}
}
std::fs::remove_dir_all(&directory).unwrap();
}
}