1use super::{Logic, Node, NodeId, Sequent};
10use crate::Error;
11use crate::kripke::Model;
12use crate::limits::{Limits, Phase, Progress, Refusal};
13
14pub const MODEL_CELLS: u64 = 1 << 27;
20
21const WORLD_BYTES: u64 = 4 * 24 + 4 + 8 + 2;
25
26const ATOM_BYTES: u64 = 4 + 32;
30
31#[non_exhaustive]
34#[derive(Clone, Debug)]
35pub struct Countermodel {
36 pub sequent: Sequent,
38 pub model: Model,
41}
42
43impl Countermodel {
44 pub const fn new(sequent: Sequent, model: Model) -> Self {
46 Self { sequent, model }
47 }
48
49 pub fn check(
56 &self,
57 logic: Logic,
58 limits: &Limits,
59 stop: impl FnMut(Progress) -> bool,
60 ) -> Result<(), Error> {
61 self.model.refutes(&self.sequent, logic, limits, stop)
62 }
63
64 pub(crate) fn found(
74 sequent: Sequent,
75 model: Model,
76 logic: Logic,
77 limits: &Limits,
78 stop: impl FnMut(Progress) -> bool,
79 ) -> Result<Option<Self>, Error> {
80 match model.refutes(&sequent, logic, limits, stop) {
81 Ok(()) => Ok(Some(Self::new(sequent, model))),
82 Err(Error::Refused(Refusal::Memory { .. })) => Ok(None),
83 Err(Error::Model { reason }) => Err(Error::Countermodel { reason }),
84 Err(error) => Err(error),
85 }
86 }
87}
88
89#[derive(Clone, Debug)]
92pub struct Forcing {
93 width: usize,
95 table: Vec<u64>,
97 holds: Vec<bool>,
100 fails: Vec<bool>,
103 arrows: Vec<Vec<u32>>,
105}
106
107impl Forcing {
108 pub fn forces(&self, world: u32, id: NodeId) -> bool {
115 assert!(id.index() < self.width, "a formula of the sequent's arena");
116 assert!((world as usize) < self.holds.len(), "a world of the model");
117 let cell = world as usize * self.width + id.index();
118 self.table[cell / 64] >> (cell % 64) & 1 == 1
119 }
120
121 pub fn at(&self, world: u32) -> impl Iterator<Item = (NodeId, bool)> + '_ {
128 (0..self.width).map(move |id| {
129 let id = NodeId(id as u32);
130 (id, self.forces(world, id))
131 })
132 }
133
134 pub fn holds(&self, world: u32) -> bool {
142 self.holds[world as usize]
143 }
144
145 pub fn failing_anywhere(&self) -> Option<u32> {
149 self.fails.iter().position(|&fails| fails).map(|w| w as u32)
150 }
151
152 pub fn failing(&self, world: u32) -> Option<u32> {
160 let mut seen = vec![false; self.fails.len()];
161 let mut stack = vec![world];
162 while let Some(w) = stack.pop() {
163 if std::mem::replace(&mut seen[w as usize], true) {
164 continue;
165 }
166 if self.fails[w as usize] {
167 return Some(w);
168 }
169 stack.extend(&self.arrows[w as usize]);
170 }
171 None
172 }
173}
174
175impl Model {
176 pub fn forcing(
211 &self,
212 sequent: &Sequent,
213 logic: Logic,
214 limits: &Limits,
215 mut stop: impl FnMut(Progress) -> bool,
216 ) -> Result<Forcing, Error> {
217 if logic != Logic::Classical && sequent.right().len() > 1 {
218 return Err(Error::Succedents {
219 count: sequent.right().len(),
220 });
221 }
222 let flaw = |reason: String| Error::Model { reason };
223 let worlds = self.worlds.len();
224 if worlds == 0 {
225 return Err(flaw("no world".to_owned()));
226 }
227 if self.world as usize >= worlds {
228 return Err(flaw(format!(
229 "the model's world {} is not one of its {worlds} worlds",
230 self.world
231 )));
232 }
233 if logic == Logic::Classical && worlds > 1 {
234 return Err(flaw(format!(
235 "{worlds} worlds where classical logic has one"
236 )));
237 }
238 let formulas = sequent.formulas();
239 let width = formulas.len();
240 let (arrows, atoms) = self.worlds.iter().fold((0u64, 0u64), |(r, a), w| {
241 (
242 r.saturating_add(w.arrows.len() as u64),
243 a.saturating_add(w.atoms.len() as u64),
244 )
245 });
246 let cells = (worlds as u64)
248 .saturating_add(arrows)
249 .saturating_mul(width as u64);
250 let refused = |limit_bytes: u64, needed: u64| {
251 Err(Error::Refused(Refusal::Memory {
252 phase: Phase::Check,
253 limit_bytes,
254 needed_bytes: Some(needed),
255 }))
256 };
257 if cells > MODEL_CELLS {
258 return refused(MODEL_CELLS / 8, cells / 8);
259 }
260 let held = (worlds as u64)
263 .saturating_mul(WORLD_BYTES)
264 .saturating_add(arrows.saturating_mul(8))
265 .saturating_add(atoms.saturating_mul(ATOM_BYTES))
266 .saturating_add(cells / 8);
267 if let Some(limit) = limits.memory_bytes
268 && held > limit
269 {
270 return refused(limit, held);
271 }
272 let mut polls = 0u64;
273 let mut poll = |stop: &mut dyn FnMut(Progress) -> bool| {
274 polls += 1;
275 if stop(Progress::new(Phase::Check, 1, polls)) {
276 Err(Error::Refused(Refusal::Stopped {
277 phase: Phase::Check,
278 }))
279 } else {
280 Ok(())
281 }
282 };
283 let named = formulas.atom_names().len();
286 let mut index: std::collections::HashMap<&str, u32> = formulas
287 .atom_names()
288 .iter()
289 .enumerate()
290 .map(|(i, name)| (name.as_str(), i as u32))
291 .collect();
292 let mut forced: Vec<Vec<u32>> = Vec::with_capacity(worlds);
293 for world in &self.worlds {
294 poll(&mut stop)?;
295 let mut ids: Vec<u32> = world
296 .atoms
297 .iter()
298 .map(|name| {
299 let next = u32::try_from(index.len()).unwrap_or(u32::MAX);
300 *index.entry(name.as_str()).or_insert(next)
301 })
302 .collect();
303 ids.sort_unstable();
304 ids.dedup();
305 forced.push(ids);
306 }
307 let mut above: Vec<Vec<u32>> = Vec::with_capacity(worlds);
311 for (n, world) in self.worlds.iter().enumerate() {
312 poll(&mut stop)?;
313 if world.falsity && logic != Logic::Minimal {
314 return Err(flaw(format!("world {n} forces ⊥ in {logic} logic")));
315 }
316 let mut ups = world.arrows.clone();
317 ups.sort_unstable();
318 ups.dedup();
319 for &up in &ups {
320 let Some(higher) = self.worlds.get(up as usize) else {
321 return Err(flaw(format!(
322 "world {n} has an arrow to world {up}, which the model does not have"
323 )));
324 };
325 let superset = &forced[up as usize];
326 if forced[n].iter().any(|a| superset.binary_search(a).is_err())
327 || (world.falsity && !higher.falsity)
328 {
329 return Err(flaw(format!(
330 "world {up} above world {n} does not force all it forces"
331 )));
332 }
333 }
334 above.push(ups);
335 }
336 let mut pending: Vec<usize> = above.iter().map(Vec::len).collect();
340 let mut into: Vec<Vec<u32>> = vec![Vec::new(); worlds];
341 for (n, ups) in above.iter().enumerate() {
342 for &up in ups {
343 into[up as usize].push(n as u32);
344 }
345 }
346 let mut ready: Vec<u32> = (0..worlds as u32)
347 .filter(|&n| pending[n as usize] == 0)
348 .collect();
349 let mut order = Vec::with_capacity(worlds);
350 while let Some(n) = ready.pop() {
351 order.push(n);
352 for &low in &into[n as usize] {
353 pending[low as usize] -= 1;
354 if pending[low as usize] == 0 {
355 ready.push(low);
356 }
357 }
358 }
359 drop(into);
360 if order.len() < worlds {
361 let round = (0..worlds).find(|&n| pending[n] > 0).unwrap_or(0);
362 return Err(flaw(format!(
363 "the arrows go round through world {round}: worlds above each other are one world"
364 )));
365 }
366 let mut table = vec![0u64; (worlds * width).div_ceil(64)];
368 let get = |table: &[u64], cell: usize| table[cell / 64] >> (cell % 64) & 1 == 1;
369 for &n in &order {
370 poll(&mut stop)?;
371 let n = n as usize;
372 let falsity = self.worlds[n].falsity;
373 let known = &forced[n][..forced[n].partition_point(|&a| (a as usize) < named)];
375 for id in 0..width {
376 let at = |table: &[u64], k: NodeId| get(table, n * width + k.index());
377 let higher = |table: &[u64]| {
380 above[n]
381 .iter()
382 .all(|&up| get(table, up as usize * width + id))
383 };
384 let t = &table[..];
385 let value = match formulas.node(NodeId(id as u32)) {
386 Node::Atom(a) => known.binary_search(&a).is_ok(),
387 Node::True => true,
388 Node::False => falsity,
389 Node::And(a, b) => at(t, a) && at(t, b),
390 Node::Or(a, b) => at(t, a) || at(t, b),
391 Node::Not(a) => (!at(t, a) || falsity) && higher(t),
392 Node::Implies(a, b) => (!at(t, a) || at(t, b)) && higher(t),
393 Node::Iff(a, b) => at(t, a) == at(t, b) && higher(t),
394 };
395 let cell = n * width + id;
396 table[cell / 64] |= u64::from(value) << (cell % 64);
397 }
398 }
399 let is = |n: usize, k: NodeId| get(&table, n * width + k.index());
400 let fails: Vec<bool> = (0..worlds)
401 .map(|n| {
402 sequent.left().iter().all(|&h| is(n, h))
403 && match sequent.right() {
404 [] => !self.worlds[n].falsity,
405 right => right.iter().all(|&c| !is(n, c)),
406 }
407 })
408 .collect();
409 let mut holds = vec![true; worlds];
410 for &n in &order {
411 let n = n as usize;
412 holds[n] = !fails[n] && above[n].iter().all(|&up| holds[up as usize]);
413 }
414 Ok(Forcing {
415 width,
416 table,
417 holds,
418 fails,
419 arrows: above,
420 })
421 }
422
423 pub fn refutes(
434 &self,
435 sequent: &Sequent,
436 logic: Logic,
437 limits: &Limits,
438 stop: impl FnMut(Progress) -> bool,
439 ) -> Result<(), Error> {
440 let forcing = self.forcing(sequent, logic, limits, stop)?;
441 let formulas = sequent.formulas();
442 let world = self.world;
443 let flaw = |reason: String| Error::Model { reason };
444 if let Some(&h) = sequent.left().iter().find(|&&h| !forcing.forces(world, h)) {
445 return Err(flaw(format!(
446 "world {world} does not force the hypothesis {}",
447 formulas.formula(h)
448 )));
449 }
450 if let Some(&c) = sequent.right().iter().find(|&&c| forcing.forces(world, c)) {
451 return Err(flaw(format!(
452 "world {world} forces the conclusion {}",
453 formulas.formula(c)
454 )));
455 }
456 if sequent.right().is_empty() && self.worlds[world as usize].falsity {
457 return Err(flaw(format!("world {world} forces ⊥")));
458 }
459 Ok(())
460 }
461}
462
463#[cfg(all(test, feature = "parse"))]
464mod tests {
465 use super::super::{Countermodel, Logic, Sequent};
466 use crate::kripke::{Model, World};
467 use crate::{Error, Limits, Refusal};
468
469 fn world(atoms: &[&str], arrows: &[u32]) -> World {
471 World::new(
472 atoms.iter().map(|&a| a.to_owned()).collect(),
473 false,
474 arrows.to_vec(),
475 )
476 }
477
478 #[test]
483 fn forcing_says_where_a_sequent_holds_and_fails() {
484 let limits = Limits::default();
485 let sequent: Sequent = "|- a \\/ ~a".parse().unwrap();
486 let logic = Logic::Intuitionistic;
487 let model = Model::new(vec![world(&["a"], &[]), world(&[], &[0])], 1);
489 let forcing = model.forcing(&sequent, logic, &limits, |_| false).unwrap();
490 assert!(!forcing.holds(1) && forcing.holds(0));
491 assert_eq!(forcing.failing(1), Some(1));
492 assert_eq!(forcing.failing(0), None);
493 assert_eq!(model.refutes(&sequent, logic, &limits, |_| false), Ok(()));
494 assert_eq!(
495 model.to_string(),
496 "world 0: forces a\nworld 1 (the model's world): forces nothing; below 0"
497 );
498
499 let negation: Sequent = "~a".parse().unwrap();
502 let mut minimal = Model::new(vec![world(&[], &[1]), world(&[], &[])], 0);
503 minimal.worlds[1].falsity = true;
504 let forcing = minimal
505 .forcing(&negation, Logic::Minimal, &limits, |_| false)
506 .unwrap();
507 assert!(forcing.holds(0));
508 minimal.worlds[0].falsity = true;
509 minimal.worlds[1].falsity = false;
510 let Err(Error::Model { reason }) =
511 minimal.forcing(&negation, Logic::Minimal, &limits, |_| false)
512 else {
513 panic!("falsity that shrinks upward accepted");
514 };
515 assert!(reason.contains("does not force all it forces"), "{reason}");
516 let Err(Error::Model { reason }) = minimal.forcing(&negation, logic, &limits, |_| false)
517 else {
518 panic!("⊥ forced in intuitionistic logic");
519 };
520 assert!(reason.contains("forces ⊥"), "{reason}");
521
522 #[cfg(feature = "serialize")]
523 {
524 let json = serde_json::to_string(&model).unwrap();
525 assert_eq!(
526 json,
527 r#"{"version":13,"worlds":[{"atoms":["a"]},{"atoms":[],"arrows":[0]}],"world":1}"#
528 );
529 let read: Model = serde_json::from_str(&json).unwrap();
530 assert_eq!(read, model);
531 let keyword = r#"{"worlds":[{"atoms":["par"]}]}"#;
532 assert!(serde_json::from_str::<Model>(keyword).is_err());
533 let misspelt = r#"{"worlds":[{"atoms":[],"arrow":[1]},{"atoms":["a"]}]}"#;
535 let error = serde_json::from_str::<Model>(misspelt).unwrap_err();
536 assert!(
537 error.to_string().contains("unknown field `arrow`"),
538 "{error}"
539 );
540 }
541 }
542
543 #[test]
548 fn the_check_asks_the_stop_and_keeps_to_its_memory() {
549 let sequent: Sequent = "a |- b".parse().unwrap();
550 let logic = Logic::Intuitionistic;
551 let model = Model::new(vec![world(&["a"], &[1, 1]), world(&["a"], &[])], 0);
552 let limits = Limits::default();
553 assert_eq!(
554 model.forcing(&sequent, logic, &limits, |_| true).err(),
555 Some(Error::Refused(Refusal::Stopped {
556 phase: crate::Phase::Check
557 }))
558 );
559 let forcing = model.forcing(&sequent, logic, &limits, |_| false).unwrap();
560 assert_eq!(forcing.failing_anywhere(), Some(0));
561 let small = limits.with_memory_bytes(Some(16));
562 let Err(Error::Refused(Refusal::Memory { .. })) =
563 model.forcing(&sequent, logic, &small, |_| false)
564 else {
565 panic!("a check past the memory bound ran");
566 };
567 let found = Countermodel::found(sequent.clone(), model.clone(), logic, &small, |_| false);
568 assert!(matches!(found, Ok(None)), "{found:?}");
569 let wrong = Model::new(vec![world(&["b"], &[])], 0);
570 let found = Countermodel::found(sequent, wrong, logic, &limits, |_| false);
571 assert!(
572 matches!(found, Err(Error::Countermodel { .. })),
573 "{found:?}"
574 );
575 }
576}