use super::{Logic, Node, NodeId, Sequent};
use crate::Error;
use crate::kripke::Model;
use crate::limits::{Limits, Phase, Progress, Refusal};
pub const MODEL_CELLS: u64 = 1 << 27;
const WORLD_BYTES: u64 = 4 * 24 + 4 + 8 + 2;
const ATOM_BYTES: u64 = 4 + 32;
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Countermodel {
pub sequent: Sequent,
pub model: Model,
}
impl Countermodel {
pub const fn new(sequent: Sequent, model: Model) -> Self {
Self { sequent, model }
}
pub fn check(
&self,
logic: Logic,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<(), Error> {
self.model.refutes(&self.sequent, logic, limits, stop)
}
pub(crate) fn found(
sequent: Sequent,
model: Model,
logic: Logic,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Option<Self>, Error> {
match model.refutes(&sequent, logic, limits, stop) {
Ok(()) => Ok(Some(Self::new(sequent, model))),
Err(Error::Refused(Refusal::Memory { .. })) => Ok(None),
Err(Error::Model { reason }) => Err(Error::Countermodel { reason }),
Err(error) => Err(error),
}
}
}
#[derive(Clone, Debug)]
pub struct Forcing {
width: usize,
table: Vec<u64>,
holds: Vec<bool>,
fails: Vec<bool>,
arrows: Vec<Vec<u32>>,
}
impl Forcing {
pub fn forces(&self, world: u32, id: NodeId) -> bool {
assert!(id.index() < self.width, "a formula of the sequent's arena");
assert!((world as usize) < self.holds.len(), "a world of the model");
let cell = world as usize * self.width + id.index();
self.table[cell / 64] >> (cell % 64) & 1 == 1
}
pub fn at(&self, world: u32) -> impl Iterator<Item = (NodeId, bool)> + '_ {
(0..self.width).map(move |id| {
let id = NodeId(id as u32);
(id, self.forces(world, id))
})
}
pub fn holds(&self, world: u32) -> bool {
self.holds[world as usize]
}
pub fn failing_anywhere(&self) -> Option<u32> {
self.fails.iter().position(|&fails| fails).map(|w| w as u32)
}
pub fn failing(&self, world: u32) -> Option<u32> {
let mut seen = vec![false; self.fails.len()];
let mut stack = vec![world];
while let Some(w) = stack.pop() {
if std::mem::replace(&mut seen[w as usize], true) {
continue;
}
if self.fails[w as usize] {
return Some(w);
}
stack.extend(&self.arrows[w as usize]);
}
None
}
}
impl Model {
pub fn forcing(
&self,
sequent: &Sequent,
logic: Logic,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Forcing, Error> {
if logic != Logic::Classical && sequent.right().len() > 1 {
return Err(Error::Succedents {
count: sequent.right().len(),
});
}
let flaw = |reason: String| Error::Model { reason };
let worlds = self.worlds.len();
if worlds == 0 {
return Err(flaw("no world".to_owned()));
}
if self.world as usize >= worlds {
return Err(flaw(format!(
"the model's world {} is not one of its {worlds} worlds",
self.world
)));
}
if logic == Logic::Classical && worlds > 1 {
return Err(flaw(format!(
"{worlds} worlds where classical logic has one"
)));
}
let formulas = sequent.formulas();
let width = formulas.len();
let (arrows, atoms) = self.worlds.iter().fold((0u64, 0u64), |(r, a), w| {
(
r.saturating_add(w.arrows.len() as u64),
a.saturating_add(w.atoms.len() as u64),
)
});
let cells = (worlds as u64)
.saturating_add(arrows)
.saturating_mul(width as u64);
let refused = |limit_bytes: u64, needed: u64| {
Err(Error::Refused(Refusal::Memory {
phase: Phase::Check,
limit_bytes,
needed_bytes: Some(needed),
}))
};
if cells > MODEL_CELLS {
return refused(MODEL_CELLS / 8, cells / 8);
}
let held = (worlds as u64)
.saturating_mul(WORLD_BYTES)
.saturating_add(arrows.saturating_mul(8))
.saturating_add(atoms.saturating_mul(ATOM_BYTES))
.saturating_add(cells / 8);
if let Some(limit) = limits.memory_bytes
&& held > limit
{
return refused(limit, held);
}
let mut polls = 0u64;
let mut poll = |stop: &mut dyn FnMut(Progress) -> bool| {
polls += 1;
if stop(Progress::new(Phase::Check, 1, polls)) {
Err(Error::Refused(Refusal::Stopped {
phase: Phase::Check,
}))
} else {
Ok(())
}
};
let named = formulas.atom_names().len();
let mut index: std::collections::HashMap<&str, u32> = formulas
.atom_names()
.iter()
.enumerate()
.map(|(i, name)| (name.as_str(), i as u32))
.collect();
let mut forced: Vec<Vec<u32>> = Vec::with_capacity(worlds);
for world in &self.worlds {
poll(&mut stop)?;
let mut ids: Vec<u32> = world
.atoms
.iter()
.map(|name| {
let next = u32::try_from(index.len()).unwrap_or(u32::MAX);
*index.entry(name.as_str()).or_insert(next)
})
.collect();
ids.sort_unstable();
ids.dedup();
forced.push(ids);
}
let mut above: Vec<Vec<u32>> = Vec::with_capacity(worlds);
for (n, world) in self.worlds.iter().enumerate() {
poll(&mut stop)?;
if world.falsity && logic != Logic::Minimal {
return Err(flaw(format!("world {n} forces ⊥ in {logic} logic")));
}
let mut ups = world.arrows.clone();
ups.sort_unstable();
ups.dedup();
for &up in &ups {
let Some(higher) = self.worlds.get(up as usize) else {
return Err(flaw(format!(
"world {n} has an arrow to world {up}, which the model does not have"
)));
};
let superset = &forced[up as usize];
if forced[n].iter().any(|a| superset.binary_search(a).is_err())
|| (world.falsity && !higher.falsity)
{
return Err(flaw(format!(
"world {up} above world {n} does not force all it forces"
)));
}
}
above.push(ups);
}
let mut pending: Vec<usize> = above.iter().map(Vec::len).collect();
let mut into: Vec<Vec<u32>> = vec![Vec::new(); worlds];
for (n, ups) in above.iter().enumerate() {
for &up in ups {
into[up as usize].push(n as u32);
}
}
let mut ready: Vec<u32> = (0..worlds as u32)
.filter(|&n| pending[n as usize] == 0)
.collect();
let mut order = Vec::with_capacity(worlds);
while let Some(n) = ready.pop() {
order.push(n);
for &low in &into[n as usize] {
pending[low as usize] -= 1;
if pending[low as usize] == 0 {
ready.push(low);
}
}
}
drop(into);
if order.len() < worlds {
let round = (0..worlds).find(|&n| pending[n] > 0).unwrap_or(0);
return Err(flaw(format!(
"the arrows go round through world {round}: worlds above each other are one world"
)));
}
let mut table = vec![0u64; (worlds * width).div_ceil(64)];
let get = |table: &[u64], cell: usize| table[cell / 64] >> (cell % 64) & 1 == 1;
for &n in &order {
poll(&mut stop)?;
let n = n as usize;
let falsity = self.worlds[n].falsity;
let known = &forced[n][..forced[n].partition_point(|&a| (a as usize) < named)];
for id in 0..width {
let at = |table: &[u64], k: NodeId| get(table, n * width + k.index());
let higher = |table: &[u64]| {
above[n]
.iter()
.all(|&up| get(table, up as usize * width + id))
};
let t = &table[..];
let value = match formulas.node(NodeId(id as u32)) {
Node::Atom(a) => known.binary_search(&a).is_ok(),
Node::True => true,
Node::False => falsity,
Node::And(a, b) => at(t, a) && at(t, b),
Node::Or(a, b) => at(t, a) || at(t, b),
Node::Not(a) => (!at(t, a) || falsity) && higher(t),
Node::Implies(a, b) => (!at(t, a) || at(t, b)) && higher(t),
Node::Iff(a, b) => at(t, a) == at(t, b) && higher(t),
};
let cell = n * width + id;
table[cell / 64] |= u64::from(value) << (cell % 64);
}
}
let is = |n: usize, k: NodeId| get(&table, n * width + k.index());
let fails: Vec<bool> = (0..worlds)
.map(|n| {
sequent.left().iter().all(|&h| is(n, h))
&& match sequent.right() {
[] => !self.worlds[n].falsity,
right => right.iter().all(|&c| !is(n, c)),
}
})
.collect();
let mut holds = vec![true; worlds];
for &n in &order {
let n = n as usize;
holds[n] = !fails[n] && above[n].iter().all(|&up| holds[up as usize]);
}
Ok(Forcing {
width,
table,
holds,
fails,
arrows: above,
})
}
pub fn refutes(
&self,
sequent: &Sequent,
logic: Logic,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<(), Error> {
let forcing = self.forcing(sequent, logic, limits, stop)?;
let formulas = sequent.formulas();
let world = self.world;
let flaw = |reason: String| Error::Model { reason };
if let Some(&h) = sequent.left().iter().find(|&&h| !forcing.forces(world, h)) {
return Err(flaw(format!(
"world {world} does not force the hypothesis {}",
formulas.formula(h)
)));
}
if let Some(&c) = sequent.right().iter().find(|&&c| forcing.forces(world, c)) {
return Err(flaw(format!(
"world {world} forces the conclusion {}",
formulas.formula(c)
)));
}
if sequent.right().is_empty() && self.worlds[world as usize].falsity {
return Err(flaw(format!("world {world} forces ⊥")));
}
Ok(())
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::super::{Countermodel, Logic, Sequent};
use crate::kripke::{Model, World};
use crate::{Error, Limits, Refusal};
fn world(atoms: &[&str], arrows: &[u32]) -> World {
World::new(
atoms.iter().map(|&a| a.to_owned()).collect(),
false,
arrows.to_vec(),
)
}
#[test]
fn forcing_says_where_a_sequent_holds_and_fails() {
let limits = Limits::default();
let sequent: Sequent = "|- a \\/ ~a".parse().unwrap();
let logic = Logic::Intuitionistic;
let model = Model::new(vec![world(&["a"], &[]), world(&[], &[0])], 1);
let forcing = model.forcing(&sequent, logic, &limits, |_| false).unwrap();
assert!(!forcing.holds(1) && forcing.holds(0));
assert_eq!(forcing.failing(1), Some(1));
assert_eq!(forcing.failing(0), None);
assert_eq!(model.refutes(&sequent, logic, &limits, |_| false), Ok(()));
assert_eq!(
model.to_string(),
"world 0: forces a\nworld 1 (the model's world): forces nothing; below 0"
);
let negation: Sequent = "~a".parse().unwrap();
let mut minimal = Model::new(vec![world(&[], &[1]), world(&[], &[])], 0);
minimal.worlds[1].falsity = true;
let forcing = minimal
.forcing(&negation, Logic::Minimal, &limits, |_| false)
.unwrap();
assert!(forcing.holds(0));
minimal.worlds[0].falsity = true;
minimal.worlds[1].falsity = false;
let Err(Error::Model { reason }) =
minimal.forcing(&negation, Logic::Minimal, &limits, |_| false)
else {
panic!("falsity that shrinks upward accepted");
};
assert!(reason.contains("does not force all it forces"), "{reason}");
let Err(Error::Model { reason }) = minimal.forcing(&negation, logic, &limits, |_| false)
else {
panic!("⊥ forced in intuitionistic logic");
};
assert!(reason.contains("forces ⊥"), "{reason}");
#[cfg(feature = "serialize")]
{
let json = serde_json::to_string(&model).unwrap();
assert_eq!(
json,
r#"{"version":13,"worlds":[{"atoms":["a"]},{"atoms":[],"arrows":[0]}],"world":1}"#
);
let read: Model = serde_json::from_str(&json).unwrap();
assert_eq!(read, model);
let keyword = r#"{"worlds":[{"atoms":["par"]}]}"#;
assert!(serde_json::from_str::<Model>(keyword).is_err());
let misspelt = r#"{"worlds":[{"atoms":[],"arrow":[1]},{"atoms":["a"]}]}"#;
let error = serde_json::from_str::<Model>(misspelt).unwrap_err();
assert!(
error.to_string().contains("unknown field `arrow`"),
"{error}"
);
}
}
#[test]
fn the_check_asks_the_stop_and_keeps_to_its_memory() {
let sequent: Sequent = "a |- b".parse().unwrap();
let logic = Logic::Intuitionistic;
let model = Model::new(vec![world(&["a"], &[1, 1]), world(&["a"], &[])], 0);
let limits = Limits::default();
assert_eq!(
model.forcing(&sequent, logic, &limits, |_| true).err(),
Some(Error::Refused(Refusal::Stopped {
phase: crate::Phase::Check
}))
);
let forcing = model.forcing(&sequent, logic, &limits, |_| false).unwrap();
assert_eq!(forcing.failing_anywhere(), Some(0));
let small = limits.with_memory_bytes(Some(16));
let Err(Error::Refused(Refusal::Memory { .. })) =
model.forcing(&sequent, logic, &small, |_| false)
else {
panic!("a check past the memory bound ran");
};
let found = Countermodel::found(sequent.clone(), model.clone(), logic, &small, |_| false);
assert!(matches!(found, Ok(None)), "{found:?}");
let wrong = Model::new(vec![world(&["b"], &[])], 0);
let found = Countermodel::found(sequent, wrong, logic, &limits, |_| false);
assert!(
matches!(found, Err(Error::Countermodel { .. })),
"{found:?}"
);
}
}