#![cfg_attr(feature = "parse", doc = "```")]
#![cfg_attr(not(feature = "parse"), doc = "```ignore")]
#![deny(clippy::wildcard_enum_match_arm)]
mod decide;
mod derivation;
#[cfg(feature = "interactive")]
mod interactive;
pub mod interpolant;
pub mod ljt;
mod model;
pub mod negative;
#[cfg(feature = "parse")]
mod parse;
#[cfg(feature = "rocq")]
pub(crate) mod rocq;
#[cfg(feature = "sat")]
pub mod sat;
mod table;
#[cfg(feature = "interactive")]
mod tableau;
mod translate;
pub use decide::{
EVIDENCE_WORK, Evidence, Outcome, Search, Verdict, decide, decide_within, gives_way,
};
pub use derivation::{Derivation, Inference, Rule, Side};
#[cfg(all(feature = "interactive", feature = "serialize"))]
pub(crate) use interactive::Parts;
#[cfg(feature = "interactive")]
pub use interactive::{Applicable, Closed, Context, Hint, Interactive, Needs, Step, StepError};
pub use model::{Countermodel, Forcing, MODEL_CELLS};
#[cfg(feature = "parse")]
pub use parse::{Problem, read_tptp};
pub use table::{TruthTable, truth_table};
#[cfg(feature = "interactive")]
pub use tableau::{End, Sign, Signed, Tableau, TableauNode};
pub use translate::{FALSE, Image, translate};
use crate::Error;
use crate::hash::HashMap;
use crate::limits::{Refusal, Space};
use crate::linear::fragment::{Fragment, Mode};
use crate::linear::sequents::notation::TEXT;
use crate::linear::sequents::{Stop, Stops};
use std::fmt::{Display, Formatter, Result as FmtResult, Write};
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serialize", serde(rename_all = "lowercase"))]
pub enum Logic {
Classical,
#[default]
Intuitionistic,
Minimal,
}
impl Logic {
pub const ALL: &'static [Self] = &[Self::Classical, Self::Intuitionistic, Self::Minimal];
pub const NAMES: &'static [&'static str] = &["classical", "intuitionistic", "minimal"];
pub const fn name(self) -> &'static str {
match self {
Self::Classical => "classical",
Self::Intuitionistic => "intuitionistic",
Self::Minimal => "minimal",
}
}
pub const fn calculus(self) -> &'static str {
match self {
Self::Classical => "LK",
Self::Intuitionistic | Self::Minimal => "LJ",
}
}
}
impl Display for Logic {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
f.write_str(self.name())
}
}
impl std::str::FromStr for Logic {
type Err = Error;
fn from_str(name: &str) -> Result<Self, Error> {
Self::ALL
.iter()
.copied()
.find(|logic| logic.name() == name)
.ok_or_else(|| Error::UnknownName {
what: "logic",
name: name.into(),
known: Self::NAMES,
})
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
pub enum Translation {
#[cfg_attr(feature = "serialize", serde(rename = "affine"))]
Affine,
#[cfg_attr(feature = "serialize", serde(rename = "cbn"))]
CallByName,
#[cfg_attr(feature = "serialize", serde(rename = "cbv"))]
CallByValue,
#[cfg_attr(feature = "serialize", serde(rename = "01"))]
ZeroOne,
}
impl Translation {
pub const ALL: &'static [Self] = &[
Self::Affine,
Self::CallByName,
Self::CallByValue,
Self::ZeroOne,
];
pub const DEFAULT_INTUITIONISTIC: Self = Self::CallByName;
pub const NAMES: &'static [&'static str] = &["affine", "cbn", "cbv", "01"];
pub const fn name(self) -> &'static str {
match self {
Self::Affine => "affine",
Self::CallByName => "cbn",
Self::CallByValue => "cbv",
Self::ZeroOne => "01",
}
}
pub const fn default_for(logic: Logic) -> Self {
match logic {
Logic::Classical => Self::Affine,
Logic::Intuitionistic | Logic::Minimal => Self::DEFAULT_INTUITIONISTIC,
}
}
pub const fn decides(self, logic: Logic) -> bool {
matches!(
(self, logic),
(Self::Affine, Logic::Classical)
| (
Self::CallByName | Self::CallByValue | Self::ZeroOne,
Logic::Intuitionistic | Logic::Minimal
)
)
}
pub const fn target(self) -> Target {
match self {
Self::Affine => Target {
fragment: Fragment::MALL,
mode: Mode::CLASSICAL.with_affine(),
},
Self::CallByName | Self::CallByValue | Self::ZeroOne => Target {
fragment: Fragment::LL,
mode: Mode::INTUITIONISTIC,
},
}
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Target {
pub fragment: Fragment,
pub mode: Mode,
}
impl Display for Target {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
if self.mode.is_affine() && !self.mode.is_intuitionistic() {
f.write_str("affine ")?;
}
f.write_str(self.fragment.name_in(self.mode))
}
}
impl Display for Translation {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
f.write_str(self.name())
}
}
impl std::str::FromStr for Translation {
type Err = Error;
fn from_str(name: &str) -> Result<Self, Error> {
Self::ALL
.iter()
.copied()
.find(|translation| translation.name() == name)
.ok_or_else(|| Error::UnknownName {
what: "translation",
name: name.into(),
known: Self::NAMES,
})
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serialize", serde(rename_all = "lowercase"))]
pub enum Method {
Embedding,
Ljt,
#[cfg(feature = "sat")]
Sat,
Table,
#[cfg(feature = "interactive")]
Tableau,
}
impl Method {
pub const ALL: &'static [Self] = &[
Self::Embedding,
Self::Ljt,
#[cfg(feature = "sat")]
Self::Sat,
Self::Table,
#[cfg(feature = "interactive")]
Self::Tableau,
];
pub const NAMES: &'static [&'static str] = &[
"embedding",
"ljt",
#[cfg(feature = "sat")]
"sat",
"table",
#[cfg(feature = "interactive")]
"tableau",
];
pub const fn name(self) -> &'static str {
match self {
Self::Embedding => "embedding",
Self::Ljt => "ljt",
#[cfg(feature = "sat")]
Self::Sat => "sat",
Self::Table => "table",
#[cfg(feature = "interactive")]
Self::Tableau => "tableau",
}
}
pub(crate) const fn title(self) -> &'static str {
match self {
Self::Embedding => "the embedding",
Self::Ljt => "LJT",
#[cfg(feature = "sat")]
Self::Sat => "the SAT solver",
Self::Table => "a truth table",
#[cfg(feature = "interactive")]
Self::Tableau => "a tableau",
}
}
pub(crate) const fn logics(self) -> &'static str {
match self {
Self::Embedding => "every logic",
#[cfg(feature = "sat")]
Self::Sat => "every logic",
Self::Ljt => "intuitionistic and minimal logic",
Self::Table => "classical logic",
#[cfg(feature = "interactive")]
Self::Tableau => "classical logic",
}
}
pub const fn default_for(logic: Logic) -> Self {
match logic {
#[cfg(feature = "sat")]
Logic::Classical | Logic::Intuitionistic | Logic::Minimal => Self::Sat,
#[cfg(not(feature = "sat"))]
Logic::Classical => Self::Embedding,
#[cfg(not(feature = "sat"))]
Logic::Intuitionistic | Logic::Minimal => Self::Ljt,
}
}
pub const fn decides(self, logic: Logic) -> bool {
match self {
Self::Embedding => true,
Self::Ljt => !matches!(logic, Logic::Classical),
#[cfg(feature = "sat")]
Self::Sat => true,
Self::Table => matches!(logic, Logic::Classical),
#[cfg(feature = "interactive")]
Self::Tableau => matches!(logic, Logic::Classical),
}
}
}
impl Display for Method {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
f.write_str(self.name())
}
}
impl std::str::FromStr for Method {
type Err = Error;
fn from_str(name: &str) -> Result<Self, Error> {
Self::ALL
.iter()
.copied()
.find(|method| method.name() == name)
.ok_or_else(|| Error::UnknownName {
what: "method",
name: name.into(),
known: Self::NAMES,
})
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serialize", serde(default, deny_unknown_fields))]
pub struct Options {
pub logic: Logic,
pub translation: Option<Translation>,
pub method: Option<Method>,
}
impl Options {
#[must_use]
pub const fn with_logic(self, logic: Logic) -> Self {
Self { logic, ..self }
}
#[must_use]
pub const fn with_translation(self, translation: Option<Translation>) -> Self {
Self {
translation,
..self
}
}
pub const fn translation(&self) -> Translation {
match self.translation {
Some(translation) => translation,
None => Translation::default_for(self.logic),
}
}
#[must_use]
pub const fn with_method(self, method: Option<Method>) -> Self {
Self { method, ..self }
}
pub const fn method(&self) -> Method {
match (self.method, self.translation) {
(Some(method), _) => method,
(None, Some(_)) => Method::Embedding,
(None, None) => Method::default_for(self.logic),
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct NodeId(u32);
impl NodeId {
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Node {
Atom(u32),
True,
False,
Not(NodeId),
And(NodeId, NodeId),
Or(NodeId, NodeId),
Implies(NodeId, NodeId),
Iff(NodeId, NodeId),
}
const _: () = assert!(size_of::<Node>() == 12);
impl Node {
pub const fn operands(self) -> (Option<NodeId>, Option<NodeId>) {
match self {
Self::Atom(_) | Self::True | Self::False => (None, None),
Self::Not(a) => (Some(a), None),
Self::And(a, b) | Self::Or(a, b) | Self::Implies(a, b) | Self::Iff(a, b) => {
(Some(a), Some(b))
}
}
}
}
#[derive(Clone, Debug, Default)]
pub struct Formulas {
nodes: Vec<Node>,
atoms: Vec<String>,
names: HashMap<String, u32>,
ids: HashMap<Node, NodeId>,
}
impl Formulas {
pub(crate) fn find(&self, node: Node) -> Option<NodeId> {
self.ids.get(&node).copied()
}
pub const MOST: usize = u32::MAX as usize;
pub fn node(&self, id: NodeId) -> Node {
self.nodes[id.index()]
}
#[cfg(any(feature = "serialize", feature = "svg"))]
pub(crate) fn nodes(&self) -> &[Node] {
&self.nodes
}
pub fn len(&self) -> usize {
self.nodes.len()
}
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
pub fn atom_name(&self, atom: u32) -> &str {
&self.atoms[atom as usize]
}
pub fn atom_names(&self) -> &[String] {
&self.atoms
}
#[cfg_attr(
target_pointer_width = "32",
expect(
clippy::absurd_extreme_comparisons,
reason = "`MOST` is `usize::MAX` on 32 bits, where the test still holds"
)
)]
pub fn add(&mut self, node: Node) -> Result<NodeId, Error> {
if let Some(&id) = self.ids.get(&node) {
return Ok(id);
}
let (a, b) = node.operands();
for id in [a, b].into_iter().flatten() {
self.holds(id)?;
}
if let Node::Atom(atom) = node
&& atom as usize >= self.atoms.len()
{
return Err(Error::IndexOutOfBounds {
space: Space::Atom,
index: atom as usize,
len: self.atoms.len(),
});
}
if self.nodes.len() >= Self::MOST {
return Err(Error::Refused(Refusal::Index {
what: Space::Formula,
count: Self::MOST as u64 + 1,
most: Self::MOST as u64,
}));
}
let id = NodeId(self.nodes.len() as u32);
self.nodes.push(node);
self.ids.insert(node, id);
Ok(id)
}
fn holds(&self, id: NodeId) -> Result<(), Error> {
if id.index() < self.nodes.len() {
Ok(())
} else {
Err(Error::IndexOutOfBounds {
space: Space::Formula,
index: id.index(),
len: self.nodes.len(),
})
}
}
pub fn atom(&mut self, name: &str) -> Result<NodeId, Error> {
let name = &*crate::linear::sequents::name::normalized(name);
let index = match self.names.get(name) {
Some(&index) => index,
None => {
crate::linear::sequents::name::check_ordinary(name)?;
let index = self.atoms.len() as u32;
self.atoms.push(name.to_owned());
self.names.insert(name.to_owned(), index);
index
}
};
self.add(Node::Atom(index))
}
pub fn formula(&self, id: NodeId) -> Formula<'_> {
Formula { formulas: self, id }
}
pub(crate) fn write<W: Write>(
&self,
out: &mut W,
id: NodeId,
brackets: bool,
symbols: &Symbols,
atom: impl Fn(&mut W, u32) -> FmtResult,
) -> FmtResult {
for visit in Stops::new(id, brackets, |k| self.node(k).operands()) {
match visit {
Stop::Enter(k, nested) => match self.node(k) {
Node::Atom(a) => atom(out, a)?,
Node::True => out.write_str(symbols.truth)?,
Node::False => out.write_str(symbols.falsity)?,
Node::Not(_) => out.write_str(symbols.not)?,
_ if nested => out.write_char('(')?,
Node::And(..) | Node::Or(..) | Node::Implies(..) | Node::Iff(..) => {}
},
Stop::Between(k) => {
out.write_char(' ')?;
out.write_str(match self.node(k) {
Node::And(..) => symbols.and,
Node::Or(..) => symbols.or,
Node::Implies(..) => symbols.implies,
Node::Atom(_) | Node::True | Node::False | Node::Not(_) | Node::Iff(..) => {
symbols.iff
}
})?;
out.write_char(' ')?;
}
Stop::Exit(k, nested) => {
if nested && self.node(k).operands().1.is_some() {
out.write_char(')')?;
}
}
}
}
Ok(())
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Symbols {
pub(crate) not: &'static str,
pub(crate) and: &'static str,
pub(crate) or: &'static str,
pub(crate) implies: &'static str,
pub(crate) iff: &'static str,
pub(crate) truth: &'static str,
pub(crate) falsity: &'static str,
}
impl Symbols {
pub(crate) const UNICODE: Self = Self {
not: "¬",
and: "∧",
or: "∨",
implies: "→",
iff: "↔",
truth: "⊤",
falsity: "⊥",
};
}
#[derive(Clone, Copy, Debug)]
pub struct Formula<'a> {
formulas: &'a Formulas,
id: NodeId,
}
impl Display for Formula<'_> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.formulas
.write(f, self.id, false, &Symbols::UNICODE, |o, a| {
o.write_str(self.formulas.atom_name(a))
})
}
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug)]
pub struct Sequent {
formulas: Formulas,
left: Vec<NodeId>,
right: Vec<NodeId>,
}
impl Sequent {
pub fn new(formulas: Formulas, left: Vec<NodeId>, right: Vec<NodeId>) -> Result<Self, Error> {
for &id in left.iter().chain(&right) {
formulas.holds(id)?;
}
Ok(Self {
formulas,
left,
right,
})
}
pub fn formulas(&self) -> &Formulas {
&self.formulas
}
pub fn left(&self) -> &[NodeId] {
&self.left
}
pub fn right(&self) -> &[NodeId] {
&self.right
}
}
impl Display for Sequent {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
let sides = (&self.left[..], &self.right[..]);
TEXT.ordinary(f, &self.formulas, sides, false, false)
}
}
fn occurrences<'a>(formulas: &Formulas, roots: impl Iterator<Item = &'a NodeId>) -> u64 {
let mut size: Vec<u64> = Vec::with_capacity(formulas.len());
for node in &formulas.nodes {
let (a, b) = node.operands();
let of = |k: Option<NodeId>| k.map_or(0, |k| size[k.index()]);
size.push(1u64.saturating_add(of(a)).saturating_add(of(b)));
}
roots.fold(0, |sum, id| sum.saturating_add(size[id.index()]))
}
pub(crate) fn bound(
formulas: &Formulas,
left: &[NodeId],
right: &[NodeId],
limits: &crate::Limits,
) -> Result<(), Error> {
let occurrences = occurrences(formulas, left.iter().chain(right));
match limits.occurrences {
Some(limit) if occurrences > limit => {
Err(Error::Refused(Refusal::Occurrences { occurrences, limit }))
}
_ => Ok(()),
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::search::generate::Rng;
use crate::linear::{Options as Search, Verdict, prove};
fn decide(text: &str, logic: Logic, translation: Translation) -> Option<bool> {
let sequent: Sequent = text.parse().unwrap();
let image = translate(&sequent, logic, translation, &crate::Limits::default()).unwrap();
let search = Search::default().with_copies(Some(8));
let outcome = prove(image.sequent(), image.mode(), &search).unwrap();
match &outcome.verdict {
Verdict::Proved(proof) => {
let unbounded = crate::Limits::default();
let derivation = image.read_back(proof, &unbounded, |_| false).unwrap();
derivation
.check(&unbounded, |_| false)
.unwrap_or_else(|e| panic!("{text} ({translation}): {e}"));
Some(true)
}
Verdict::Unprovable(_) => Some(false),
Verdict::Unknown(_) => None,
}
}
#[test]
fn names_read_back_and_bounds_hold() {
let logics: Vec<_> = Logic::ALL.iter().map(|l| l.name()).collect();
let translations: Vec<_> = Translation::ALL.iter().map(|t| t.name()).collect();
assert_eq!(logics, Logic::NAMES);
assert_eq!(translations, Translation::NAMES);
for &logic in Logic::ALL {
assert_eq!(logic.name().parse::<Logic>().unwrap(), logic);
}
for &translation in Translation::ALL {
assert_eq!(
translation.name().parse::<Translation>().unwrap(),
translation
);
}
assert!(matches!(
"cbz".parse::<Translation>(),
Err(Error::UnknownName { known, .. }) if known == Translation::NAMES
));
let bound = |n| crate::Limits::default().with_occurrences(Some(n));
let refused = |result: Result<(), Error>| {
matches!(result, Err(Error::Refused(Refusal::Occurrences { .. })))
};
assert!(Sequent::parse_within("a /\\ b -> c", &bound(5)).is_ok());
assert!(refused(
Sequent::parse_within("a /\\ b -> c", &bound(4)).map(|_| ())
));
let tptp = "fof(c, conjecture, (a & b) => c).";
assert!(read_tptp(tptp, &bound(5)).is_ok());
assert!(refused(read_tptp(tptp, &bound(4)).map(|_| ())));
let repeated = ["a"; 6].join(", ");
assert!(Sequent::parse_within(&repeated, &bound(6)).is_ok());
assert!(refused(
Sequent::parse_within(&repeated, &bound(5)).map(|_| ())
));
assert!(Sequent::parse_within("~(~(a))", &bound(3)).is_ok());
for run in ["~".repeat(100), "a -> ".repeat(100), "(".repeat(100)] {
assert!(refused(
Sequent::parse_within(&format!("{run}a b"), &bound(10)).map(|_| ())
));
}
let hypotheses = "fof(h, axiom, a).\n".repeat(5) + "fof(c, conjecture, a).";
assert!(read_tptp(&hypotheses, &bound(6)).is_ok());
assert!(refused(read_tptp(&hypotheses, &bound(5)).map(|_| ())));
let sequent: Sequent = "a /\\ b -> c".parse().unwrap();
let image = translate(
&sequent,
Logic::Classical,
Translation::Affine,
&bound(1_000),
)
.unwrap();
let size = image.sequent().occurrences();
let classical = |n| translate(&sequent, Logic::Classical, Translation::Affine, &bound(n));
assert!(classical(size).is_ok());
assert!(refused(classical(size - 1).map(|_| ())));
}
#[test]
fn atom_names_are_composed_identifiers() {
let mut formulas = Formulas::default();
let composed = formulas.atom("\u{e9}").unwrap();
assert_eq!(formulas.atom("e\u{301}").unwrap(), composed);
assert_eq!(formulas.atom_names(), ["\u{e9}"]);
for name in ["top", "true", "forall", "a b"] {
assert!(
matches!(formulas.atom(name), Err(Error::AtomName { .. })),
"{name}"
);
}
}
#[test]
fn foreign_ids_are_refused() {
let mut other = Formulas::default();
let (a, b) = (other.atom("a").unwrap(), other.atom("b").unwrap());
let and = other.add(Node::And(a, b)).unwrap();
let mut formulas = Formulas::default();
let x = formulas.atom("x").unwrap();
let refused = |result: Result<_, Error>, space| matches!(result, Err(Error::IndexOutOfBounds { space: s, .. }) if s == space);
assert!(refused(formulas.add(Node::Not(and)), Space::Formula));
assert!(refused(formulas.add(Node::Atom(5)), Space::Atom));
let sequent = Sequent::new(formulas.clone(), vec![x], vec![and]);
assert!(refused(sequent.map(|_| x), Space::Formula));
assert!(Sequent::new(formulas, vec![], vec![x]).is_ok());
}
#[test]
fn false_is_no_atom_of_the_sequent() {
let read = read_tptp(
"fof(a, axiom, p). fof(b, axiom, ~p). fof(c, conjecture, false).",
&crate::Limits::default(),
);
assert!(matches!(read, Err(Error::AtomName { name }) if name == FALSE));
}
#[test]
fn decides_and_reads_back() {
let cases = [
("a -> a", true, true, true),
("a \\/ ~a", true, false, false),
("~~a -> a", true, false, false),
("a -> ~~a", true, true, true),
("((a -> b) -> a) -> a", true, false, false),
("false -> a", true, true, false),
("~a -> a -> b", true, true, false),
("~a -> a -> ~b", true, true, true),
("a /\\ b <-> b /\\ a", true, true, true),
("a \\/ b, ~a |- b", true, true, false),
("(a -> b) /\\ (a -> c) |- a -> b /\\ c", true, true, true),
("a -> b, b -> c |- a -> c", true, true, true),
("~(a \\/ b) <-> ~a /\\ ~b", true, true, true),
("~(a /\\ b) -> ~a \\/ ~b", true, false, false),
("true, a |- a /\\ true", true, true, true),
("a -> (a -> b) -> b", true, true, true),
("(a <-> b) -> (b <-> a)", true, true, true),
("a |- b", false, false, false),
("a \\/ b |- a /\\ b", false, false, false),
("~~(a \\/ ~a)", true, true, true),
("false |- ~true", true, true, true),
("false |- a -> a", true, true, true),
("q |- r -> ((false \\/ q) -> r)", true, true, true),
];
for (text, classical, intuitionistic, minimal) in cases {
assert_eq!(
decide(text, Logic::Classical, Translation::Affine),
Some(classical),
"{text} classically"
);
for translation in [
Translation::CallByName,
Translation::CallByValue,
Translation::ZeroOne,
] {
for (logic, valid) in [
(Logic::Intuitionistic, intuitionistic),
(Logic::Minimal, minimal),
] {
let verdict = decide(text, logic, translation);
assert!(
verdict.is_none() || verdict == Some(valid),
"{text} in {logic} logic by {translation}: {verdict:?}"
);
if valid {
assert_eq!(
verdict,
Some(true),
"{text} in {logic} logic by {translation}"
);
}
}
}
}
}
fn generated(rng: &mut Rng, formulas: &mut Formulas, atoms: &[NodeId], depth: usize) -> NodeId {
if depth == 0 || rng.one_in(4) {
let leaf = rng.below(2 * atoms.len() + 2);
let node = match leaf.checked_sub(2 * atoms.len()) {
None => return atoms[leaf % atoms.len()],
Some(0) => Node::True,
Some(_) => Node::False,
};
return formulas.add(node).unwrap();
}
let a = generated(rng, formulas, atoms, depth - 1);
let node = match rng.below(4) {
0 => Node::Not(a),
choice => {
let b = generated(rng, formulas, atoms, depth - 1);
match choice {
1 => Node::And(a, b),
2 => Node::Or(a, b),
_ => Node::Implies(a, b),
}
}
};
formulas.add(node).unwrap()
}
pub(super) fn generated_sequent(rng: &mut Rng) -> Sequent {
let mut formulas = Formulas::default();
let atoms: Vec<_> = ["a", "b", "c"]
.into_iter()
.map(|name| formulas.atom(name).unwrap())
.collect();
let left = (0..rng.below(3))
.map(|_| generated(rng, &mut formulas, &atoms, 3))
.collect();
let right = (0..usize::from(!rng.one_in(6)))
.map(|_| generated(rng, &mut formulas, &atoms, 3))
.collect();
Sequent::new(formulas, left, right).unwrap()
}
pub(super) fn valid_by_truth_table(sequent: &Sequent) -> bool {
let formulas = sequent.formulas();
(0..1_u32 << formulas.atom_names().len()).all(|assignment| {
let mut value: Vec<bool> = Vec::with_capacity(formulas.len());
for n in 0..formulas.len() {
let of = |id: NodeId| value[id.index()];
let holds = match formulas.node(NodeId(n as u32)) {
Node::Atom(atom) => assignment >> atom & 1 == 1,
Node::True => true,
Node::False => false,
Node::Not(a) => !of(a),
Node::And(a, b) => of(a) && of(b),
Node::Or(a, b) => of(a) || of(b),
Node::Implies(a, b) => !of(a) || of(b),
Node::Iff(a, b) => of(a) == of(b),
};
value.push(holds);
}
!sequent.left().iter().all(|id| value[id.index()])
|| sequent.right().iter().any(|id| value[id.index()])
})
}
#[test]
fn translations_agree_with_each_other_and_the_truth_table() {
const SEQUENTS: usize = 300;
let search = Search::default().with_copies(Some(6));
let limits = crate::Limits::default().with_work(Some(50_000));
let mut rng = Rng::new(2_026);
let mut decided: HashMap<(Logic, Translation), usize> = HashMap::default();
for _ in 0..SEQUENTS {
let sequent = generated_sequent(&mut rng);
let classical = valid_by_truth_table(&sequent);
for &logic in Logic::ALL {
let verdicts: Vec<_> = Translation::ALL
.iter()
.filter(|translation| translation.decides(logic))
.map(|&translation| {
let options = Options::default()
.with_logic(logic)
.with_translation(Some(translation));
let outcome =
super::decide_within(&sequent, &options, &search, &limits, |_| false)
.unwrap_or_else(|e| {
panic!("{sequent} in {logic} logic by {translation}: {e}")
});
let valid = match outcome.verdict {
super::Verdict::Valid(_) => Some(true),
super::Verdict::NotValid => Some(false),
super::Verdict::Unknown(_) => None,
};
if valid.is_some() {
*decided.entry((logic, translation)).or_default() += 1;
}
(translation, valid)
})
.collect();
let answers: Vec<bool> = verdicts.iter().filter_map(|&(_, valid)| valid).collect();
assert!(
answers.windows(2).all(|pair| pair[0] == pair[1]),
"{sequent} in {logic} logic: {verdicts:?}"
);
if logic == Logic::Classical {
assert!(
answers.iter().all(|&valid| valid == classical),
"{sequent} classically: {verdicts:?}, the truth table says {classical}"
);
} else {
assert!(
classical || !answers.contains(&true),
"{sequent} in {logic} logic: {verdicts:?}, the truth table refutes it"
);
}
}
}
for &logic in Logic::ALL {
for &translation in Translation::ALL.iter().filter(|t| t.decides(logic)) {
let count = decided.get(&(logic, translation)).copied().unwrap_or(0);
assert!(
2 * count >= SEQUENTS,
"{translation} decided {count} of {SEQUENTS} sequents in {logic} logic"
);
}
}
}
}