use super::{Derivation, Logic, Method, Options, Sequent, Translation, ljt, translate};
use crate::limits::{Limits, Progress};
use crate::linear::search::{self, Reason};
use crate::{Error, Refusal};
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Outcome {
pub verdict: Verdict,
pub logic: Logic,
pub search: Search,
pub countermodel: Option<super::Countermodel>,
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub enum Search {
Embedding {
translation: Translation,
linear: Box<search::Outcome>,
},
Ljt(ljt::Statistics),
#[cfg(feature = "sat")]
Sat(super::sat::Statistics),
Table(Box<super::TruthTable>),
#[cfg(feature = "interactive")]
Tableau(Box<super::Tableau>),
}
impl Outcome {
pub const fn method(&self) -> Method {
match self.search {
Search::Embedding { .. } => Method::Embedding,
Search::Ljt(_) => Method::Ljt,
#[cfg(feature = "sat")]
Search::Sat(_) => Method::Sat,
Search::Table(_) => Method::Table,
#[cfg(feature = "interactive")]
Search::Tableau(_) => Method::Tableau,
}
}
}
#[cfg(feature = "sat")]
impl From<super::sat::Outcome> for Outcome {
fn from(outcome: super::sat::Outcome) -> Self {
Self {
verdict: outcome.verdict,
logic: outcome.logic,
search: Search::Sat(outcome.statistics),
countermodel: outcome.model,
}
}
}
impl From<ljt::Outcome> for Outcome {
fn from(outcome: ljt::Outcome) -> Self {
Self {
verdict: outcome.verdict,
logic: outcome.logic,
search: Search::Ljt(outcome.statistics),
countermodel: None,
}
}
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub enum Verdict {
Valid(Evidence),
NotValid,
Unknown(Reason),
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub enum Evidence {
Derivation(Box<Derivation>),
#[cfg(feature = "sat")]
Clausal(super::sat::ClausalProof),
Image,
Table,
}
impl Evidence {
pub fn derivation(&self) -> Result<&Derivation, Error> {
match self {
Self::Derivation(derivation) => Ok(derivation),
#[cfg(feature = "sat")]
Self::Clausal(_) => Err(Error::NoDerivation {
evidence: "a checked clausal proof",
}),
Self::Table => Err(Error::NoDerivation {
evidence: "its truth table",
}),
Self::Image => Err(Error::NotBuilt),
}
}
}
pub fn gives_way(decided: &Result<Outcome, Error>) -> bool {
match decided {
Ok(outcome) => {
matches!(outcome.verdict, Verdict::Unknown(reason) if reason != Reason::Stopped)
}
Err(error) => matches!(error, Error::Refused(r) if !matches!(r, Refusal::Stopped { .. })),
}
}
pub const EVIDENCE_WORK: u64 = 1 << 20;
#[cfg(feature = "sat")]
fn with_evidence(
solved: Outcome,
sequent: &Sequent,
translation: Translation,
search: &search::Options,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Outcome, Error> {
let logic = solved.logic;
let work = limits.work.map_or(EVIDENCE_WORK, |w| w.min(EVIDENCE_WORK));
let Ok(image) = translate(sequent, logic, translation, limits) else {
return Ok(solved);
};
let bounded = limits.with_work(Some(work));
let Ok(linear) =
search::prove_within(image.sequent(), image.mode(), search, &bounded, &mut stop)
else {
return Ok(solved);
};
let contradiction = || Error::ReadBack {
calculus: logic.calculus(),
reason: "the embedding contradicts the SAT solver".to_owned(),
};
let verdict = match (&linear.verdict, &solved.verdict) {
(search::Verdict::Proved(proof), Verdict::Valid(_)) => {
let derivation = match image.read_back(proof, limits, &mut stop) {
Ok(derivation) => derivation,
Err(error @ Error::ReadBack { .. }) => return Err(error),
Err(_) => return Ok(solved),
};
match derivation.check(limits, &mut stop) {
Ok(()) => Verdict::Valid(Evidence::Derivation(Box::new(derivation))),
Err(error @ Error::ReadBack { .. }) => return Err(error),
Err(_) => return Ok(solved),
}
}
(search::Verdict::Unprovable(_), Verdict::NotValid) => Verdict::NotValid,
(search::Verdict::Proved(_), _) | (search::Verdict::Unprovable(_), _) => {
return Err(contradiction());
}
(search::Verdict::Unknown(_), _) => return Ok(solved),
};
let countermodel = match image.countermodel(&linear, limits, &mut stop)? {
Some(countermodel) => Some(countermodel),
None => solved.countermodel,
};
Ok(Outcome {
verdict,
logic,
search: Search::Embedding {
translation,
linear: Box::new(linear),
},
countermodel,
})
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
pub fn decide(sequent: &Sequent, options: &Options) -> Result<Outcome, Error> {
decide_within(
sequent,
options,
&search::Options::default(),
&Limits::default(),
|_| false,
)
}
impl super::Image {
pub fn outcome(
&self,
linear: search::Outcome,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Outcome, Error> {
let verdict = match &linear.verdict {
search::Verdict::Proved(proof) => {
let checked = self
.read_back(proof, limits, &mut stop)
.and_then(|d| d.check(limits, &mut stop).map(|()| d));
match checked {
Ok(derivation) => Verdict::Valid(Evidence::Derivation(Box::new(derivation))),
Err(error) if error.is_refusal() => Verdict::Valid(Evidence::Image),
Err(error) => return Err(error),
}
}
search::Verdict::Unprovable(_) => Verdict::NotValid,
search::Verdict::Unknown(reason) => Verdict::Unknown(*reason),
};
let countermodel = self.countermodel(&linear, limits, &mut stop)?;
Ok(Outcome {
verdict,
logic: self.logic(),
search: Search::Embedding {
translation: self.translation(),
linear: Box::new(linear),
},
countermodel,
})
}
fn countermodel(
&self,
linear: &search::Outcome,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Option<super::Countermodel>, Error> {
let search::Verdict::Unprovable(disproof) = &linear.verdict else {
return Ok(None);
};
let crate::linear::Refutation::Classical(classical) = disproof.refutation() else {
return Ok(None);
};
if self.logic() != Logic::Classical {
return Ok(None);
}
let names = disproof.sequent().atom_names();
let atoms = names
.iter()
.zip(&classical.assignment)
.filter(|&(_, &value)| value)
.map(|(name, _)| name.clone())
.collect();
let world = crate::kripke::World::new(atoms, false, Vec::new());
let model = crate::kripke::Model::new(vec![world], 0);
match super::Countermodel::found(
self.ordinary().clone(),
model,
Logic::Classical,
limits,
stop,
) {
Err(Error::Refused(Refusal::Stopped { .. })) => Ok(None),
found => found,
}
}
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
pub fn decide_within(
sequent: &Sequent,
options: &Options,
search: &search::Options,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Outcome, Error> {
let (logic, translation) = (options.logic, options.translation());
let decided = match options.method() {
Method::Embedding => None,
Method::Ljt => Some(ljt::decide(sequent, logic, limits, &mut stop).map(Outcome::from)),
#[cfg(feature = "sat")]
Method::Sat if options.method.is_none() && logic == Logic::Classical => {
let decided = super::sat::decide(sequent, logic, limits, &mut stop).map(Outcome::from);
match decided {
Ok(
solved @ Outcome {
verdict: Verdict::Valid(_) | Verdict::NotValid,
..
},
) => {
return with_evidence(solved, sequent, translation, search, limits, stop);
}
decided => Some(decided),
}
}
#[cfg(feature = "sat")]
Method::Sat if options.method.is_none() => Some(
super::sat::decide_preferring_ljt(sequent, logic, limits, &mut stop).map(Outcome::from),
),
#[cfg(feature = "sat")]
Method::Sat => {
Some(super::sat::decide(sequent, logic, limits, &mut stop).map(Outcome::from))
}
Method::Table => Some(super::table::decide(sequent, logic, limits, &mut stop)),
#[cfg(feature = "interactive")]
Method::Tableau => Some(super::tableau::decide(sequent, logic, limits, &mut stop)),
};
if let Some(decided) = decided
&& (options.method.is_some() || !gives_way(&decided))
{
return decided;
}
let image = translate(sequent, logic, translation, limits)?;
let linear = search::prove_within(image.sequent(), image.mode(), search, limits, &mut stop)?;
let verdict = match &linear.verdict {
search::Verdict::Proved(proof) => {
let derivation = image.read_back(proof, limits, &mut stop)?;
derivation.check(limits, &mut stop)?;
Verdict::Valid(Evidence::Derivation(Box::new(derivation)))
}
search::Verdict::Unprovable(_) => Verdict::NotValid,
search::Verdict::Unknown(reason) => Verdict::Unknown(*reason),
};
let countermodel = image.countermodel(&linear, limits, &mut stop)?;
Ok(Outcome {
verdict,
logic,
search: Search::Embedding {
translation,
linear: Box::new(linear),
},
countermodel,
})
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::{Method, Options, Search, Verdict, decide_within};
use crate::Limits;
use crate::linear::search;
use crate::ordinary::{Logic, Sequent, Translation};
#[test]
fn the_options_choose_the_method() {
let options = Options::default().with_logic(Logic::Intuitionistic);
assert_eq!(options.method(), Method::default_for(Logic::Intuitionistic));
let translated = options.with_translation(Some(Translation::CallByValue));
assert_eq!(translated.method(), Method::Embedding);
let ljt = translated.with_method(Some(Method::Ljt));
assert_eq!(ljt.method(), Method::Ljt);
let sequent: Sequent = "~~(a \\/ ~a)".parse().unwrap();
let (search, limits) = (search::Options::default(), Limits::default());
let outcome = decide_within(&sequent, &ljt, &search, &limits, |_| false).unwrap();
assert!(matches!(outcome.verdict, Verdict::Valid(_)));
assert!(matches!(outcome.search, Search::Ljt(_)));
#[cfg(feature = "serialize")]
{
let json = serde_json::to_value(&outcome).unwrap();
assert_eq!(json["search"]["method"], "ljt");
assert!(json["search"].get("translation").is_none());
assert!(json["search"]["statistics"]["sequents"].as_u64().unwrap() > 0);
}
let embedded = decide_within(&sequent, &translated, &search, &limits, |_| false).unwrap();
assert_eq!(embedded.method(), Method::Embedding);
let classical = ljt.with_logic(Logic::Classical);
assert!(decide_within(&sequent, &classical, &search, &limits, |_| false).is_err());
let small = limits.with_derivation_bytes(Some(64));
let refused = super::ljt::decide(&sequent, Logic::Intuitionistic, &small, |_| false);
assert!(
super::gives_way(&refused.map(Into::into)),
"the derivation's bound"
);
assert!(decide_within(&sequent, &ljt, &search, &small, |_| false).is_err());
let stopped = super::ljt::decide(&sequent, Logic::Intuitionistic, &limits, |_| true);
assert!(!super::gives_way(&stopped.map(Into::into)), "the stop");
let classical = super::ljt::decide(&sequent, Logic::Classical, &limits, |_| false);
assert!(!super::gives_way(&classical.map(Into::into)), "the logic");
}
#[cfg(feature = "serialize")]
#[test]
fn outcomes_read_back() {
use super::super::Image;
let (search, limits) = (search::Options::default(), Limits::default());
let round = |outcome: &super::Outcome| {
let json = serde_json::to_string(outcome).unwrap();
let mut document = serde_json::Deserializer::from_str(&json);
let read: super::Outcome = crate::wire::upgrade(&mut document, &limits)
.unwrap_or_else(|e| panic!("{json}: {e}"));
assert_eq!(serde_json::to_string(&read).unwrap(), json);
};
let classical = Options::default()
.with_logic(Logic::Classical)
.with_method(Some(Method::Embedding));
for text in ["|- a \\/ ~a", "a |- b"] {
let sequent: Sequent = text.parse().unwrap();
round(&decide_within(&sequent, &classical, &search, &limits, |_| false).unwrap());
}
let sequent: Sequent = "~~a -> a".parse().unwrap();
for method in [Method::Ljt, Method::Embedding] {
let options = Options::default()
.with_logic(Logic::Intuitionistic)
.with_method(Some(method));
round(&decide_within(&sequent, &options, &search, &limits, |_| false).unwrap());
}
let stopped = Options::default().with_logic(Logic::Intuitionistic);
let options = stopped.with_method(Some(Method::Embedding));
let unknown = decide_within(&sequent, &options, &search, &limits, |_| true).unwrap();
assert!(matches!(unknown.verdict, Verdict::Unknown(_)));
round(&unknown);
#[cfg(feature = "sat")]
round(&decide_within(&sequent, &stopped, &search, &limits, |_| false).unwrap());
let peirce: Sequent = "((a -> b) -> a) -> a".parse().unwrap();
let image: Image =
super::super::translate(&peirce, Logic::Classical, Translation::Affine, &limits)
.unwrap();
let linear = search::prove(image.sequent(), image.mode(), &search).unwrap();
let small = limits.with_derivation_bytes(Some(64));
let outcome = image.outcome(linear, &small, |_| false).unwrap();
assert!(matches!(
outcome.verdict,
Verdict::Valid(super::Evidence::Image)
));
round(&outcome);
let refused = |json: &str| {
let mut document = serde_json::Deserializer::from_str(json);
crate::wire::upgrade::<super::Outcome, _>(&mut document, &limits).unwrap_err()
};
let old = r#"{"version":8,"verdict":"not_valid","logic":"classical","translation":"affine","engine":"focus","statistics":{}}"#;
assert!(refused(old).to_string().contains("below level 12"));
#[cfg(feature = "sat")]
{
let options = Options::default()
.with_logic(Logic::Classical)
.with_method(Some(Method::Sat));
let outcome = decide_within(&peirce, &options, &search, &limits, |_| false).unwrap();
let json = serde_json::to_string(&outcome).unwrap();
assert!(refused(&json).to_string().contains("clausal proof"));
}
}
#[cfg(feature = "sat")]
#[test]
fn the_classical_default_keeps_the_embedding_s_evidence() {
use super::Evidence;
let options = Options::default().with_logic(Logic::Classical);
let (search, limits) = (search::Options::default(), Limits::default());
let sequent: Sequent = "|- ((a -> b) -> a) -> a".parse().unwrap();
let outcome = decide_within(&sequent, &options, &search, &limits, |_| false).unwrap();
assert!(matches!(
outcome.verdict,
Verdict::Valid(Evidence::Derivation(_))
));
assert_eq!(outcome.method(), Method::Embedding);
let refuted: Sequent = "a |- b".parse().unwrap();
let outcome = decide_within(&refuted, &options, &search, &limits, |_| false).unwrap();
assert!(matches!(outcome.verdict, Verdict::NotValid));
assert_eq!(outcome.method(), Method::Embedding);
let mut polls = 0_usize;
let solved = super::super::sat::decide(&sequent, Logic::Classical, &limits, |_| {
polls += 1;
false
});
assert!(solved.is_ok());
let mut asked = 0_usize;
let outcome = decide_within(&sequent, &options, &search, &limits, |_| {
asked += 1;
asked > polls
})
.unwrap();
assert!(matches!(
outcome.verdict,
Verdict::Valid(Evidence::Clausal(_))
));
assert_eq!(outcome.method(), Method::Sat);
}
}