Skip to main content

deduxit/ordinary/
model.rs

1// deduxit © Fabian Lukas Grubmüller 2026
2// Licensed under the EUPL
3
4//! The check of a finite Kripke model ([`kripke`](crate::kripke): worlds
5//! joined by arrows to the worlds above them, each forcing some atoms)
6//! against an ordinary sequent: whether it is a model of the logic, what
7//! each world forces, and whether the sequent holds or fails there.
8
9use super::{Logic, Node, NodeId, Sequent};
10use crate::Error;
11use crate::kripke::Model;
12use crate::limits::{Limits, Phase, Progress, Refusal};
13
14/// The most cells a check computes: a cell is a world, or an arrow to a
15/// world above, times a formula of the sequent's arena. The forcing table
16/// holds a bit per world and formula, so a check holds at most 16 MiB of
17/// it. A model past the bound is not checked, and an outcome drops a
18/// countermodel past it as too large to show.
19pub const MODEL_CELLS: u64 = 1 << 27;
20
21/// The bytes the check holds per world besides the table: its atoms' and
22/// arrows' vectors, the arrows into it, its place in the order, its
23/// pending count and two flags.
24const WORLD_BYTES: u64 = 4 * 24 + 4 + 8 + 2;
25
26/// The bytes the check holds per atom a world forces: its index, and at
27/// most one entry of the map of names (a name and an index, with the
28/// map's own share).
29const ATOM_BYTES: u64 = 4 + 32;
30
31/// A Kripke model that refutes an ordinary sequent, with the sequent: the
32/// evidence of a "not valid".
33#[non_exhaustive]
34#[derive(Clone, Debug)]
35pub struct Countermodel {
36    /// The sequent refuted.
37    pub sequent: Sequent,
38    /// The model. Its world forces every formula left of the sequent's
39    /// `⊢` and none right of it, as [`Model::refutes`] checks.
40    pub model: Model,
41}
42
43impl Countermodel {
44    /// Returns the countermodel of this sequent and model, unchecked.
45    pub const fn new(sequent: Sequent, model: Model) -> Self {
46        Self { sequent, model }
47    }
48
49    /// Checks that the model refutes the sequent in `logic`, as
50    /// [`Model::refutes`] does.
51    ///
52    /// # Errors
53    ///
54    /// As [`Model::refutes`].
55    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    /// Returns the countermodel an engine found, checked: `None` where it
65    /// is too large to check (past [`MODEL_CELLS`] or
66    /// `limits.memory_bytes`).
67    ///
68    /// # Errors
69    ///
70    /// [`Error::Countermodel`] where the model does not refute the
71    /// sequent, a defect of the engine; [`Refusal::Stopped`] when the stop
72    /// fired.
73    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/// What each world of a model forces, for every formula of a sequent's
90/// arena, as [`Model::forcing`] computes it.
91#[derive(Clone, Debug)]
92pub struct Forcing {
93    /// The number of formulas in the sequent's arena: the bits per world.
94    width: usize,
95    /// A bit per world and formula.
96    table: Vec<u64>,
97    /// Per world, whether the sequent holds there: at every world at or
98    /// above it that forces every hypothesis, the conclusion is forced.
99    holds: Vec<bool>,
100    /// Per world, whether it forces every hypothesis and not the
101    /// conclusion.
102    fails: Vec<bool>,
103    /// The arrows of each world, for the search of a failing world above.
104    arrows: Vec<Vec<u32>>,
105}
106
107impl Forcing {
108    /// Returns whether `world` forces the formula `id` of the sequent's
109    /// arena.
110    ///
111    /// # Panics
112    ///
113    /// For a world or a formula outside the model or the arena.
114    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    /// Returns what `world` forces of every formula of the sequent's
122    /// arena, each operand before its formula.
123    ///
124    /// # Panics
125    ///
126    /// For a world outside the model.
127    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    /// Returns whether the sequent holds at `world`: every world at or
135    /// above it that forces every formula left of `⊢` forces the formula
136    /// right of it (`⊥` where there is none; classically, one of them).
137    ///
138    /// # Panics
139    ///
140    /// For a world outside the model.
141    pub fn holds(&self, world: u32) -> bool {
142        self.holds[world as usize]
143    }
144
145    /// Returns a world where the sequent fails, one that forces every
146    /// formula left of `⊢` and not the formula right of it, or `None` where
147    /// it holds at every world.
148    pub fn failing_anywhere(&self) -> Option<u32> {
149        self.fails.iter().position(|&fails| fails).map(|w| w as u32)
150    }
151
152    /// Returns a world at or above `world` where the sequent fails, one
153    /// that forces every formula left of `⊢` and not the formula right of
154    /// it, or `None` where the sequent holds at `world`.
155    ///
156    /// # Panics
157    ///
158    /// For a world outside the model.
159    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    /// Checks that the model is one of `logic` and computes what each of
177    /// its worlds forces, for every formula of the sequent's arena.
178    ///
179    /// A model of the logic has:
180    /// - at least one world, the model's world among them;
181    /// - every arrow to a world of the model, and no cycle of arrows (the
182    ///   order is a partial order: two worlds each above the other would
183    ///   be one world);
184    /// - every world forcing the atoms, and `⊥`, of every world below it;
185    /// - `⊥` forced only in minimal logic;
186    /// - one world in classical logic.
187    ///
188    /// An atom the sequent does not name changes nothing the sequent's
189    /// formulas force, though it must grow along the arrows as the others
190    /// do. An arrow written twice is one arrow.
191    ///
192    /// Forcing is computed world by world, the worlds above first. An atom
193    /// is forced where the world forces it, and `⊥` where the world forces
194    /// it (minimal logic). `∧` and `∨` follow from their parts there. An
195    /// implication, a negation (`¬A` read as `A → ⊥`) or an equivalence is
196    /// forced where it holds there and is forced at every world directly
197    /// above, which then forces it at every world above. The stop is asked
198    /// once per world in each pass over the worlds. Besides the table
199    /// ([`MODEL_CELLS`]) the check holds a few words per world, arrow and
200    /// atom, which `limits.memory_bytes` bounds.
201    ///
202    /// # Errors
203    ///
204    /// [`Error::Model`] for a model that is not one of the logic, naming
205    /// what fails; [`Error::Succedents`] for more than one formula right
206    /// of `⊢` outside classical logic; [`Refusal::Memory`] where the check
207    /// would compute more than [`MODEL_CELLS`] cells or hold more than
208    /// `limits.memory_bytes`, and [`Refusal::Stopped`] when the stop
209    /// fired, neither a verdict on the model.
210    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        // Each count is below 2^64 saturating, so the product saturates.
247        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        // What the passes below hold besides the table: `WORLD_BYTES` per
261        // world, two indices per arrow and `ATOM_BYTES` per atom.
262        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        // Each world's atoms as sorted indices: the sequent's atoms keep
284        // their own, below `named`, and the other names follow.
285        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        // Each world's arrows, each once, checked: to a world of the
308        // model that forces all this one forces. A world's atoms are
309        // looked up in each world directly above it, between two polls.
310        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        // The worlds in an order where each comes after every world above
337        // it (Kahn's algorithm on the arrows reversed); a world left out
338        // lies on arrows that go round.
339        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        // A bit per world and formula; below `MODEL_CELLS` the index fits.
367        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            // The sequent's atoms the world forces: a prefix of its own.
374            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                // An implication holds where it holds locally and at every
378                // world directly above, which holds it at every world above.
379                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    /// Checks that the model refutes the sequent in `logic`: it is a model
424    /// of the logic ([`forcing`](Self::forcing)), and its world forces
425    /// every formula left of `⊢` and not the formula right of it (`⊥`
426    /// where there is none; classically, none of them).
427    ///
428    /// # Errors
429    ///
430    /// As [`forcing`](Self::forcing), and [`Error::Model`] naming the
431    /// hypothesis the model's world does not force or the conclusion it
432    /// forces.
433    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    /// Returns a world of these atoms with arrows to these worlds.
470    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    /// The excluded middle fails at the root of two worlds and holds at
479    /// the world above, whichever order the worlds are given in; minimal
480    /// logic reads `⊥` as an atom some worlds force, monotone; a model of
481    /// another logic is refused, naming why; the model reads back.
482    #[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        // The world above first: the order is the arrows', not the indices'.
488        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        // `¬a` holds in minimal logic where no world above forces `a`,
500        // even where a world forces `⊥`, and falsity must grow upward.
501        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            // A misspelt key is refused by name, not read as no arrows.
534            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    /// The check asks the stop before its first pass over the atoms, reads
544    /// an arrow written twice as one, finds a failing world without a
545    /// search per world, and refuses past the memory bound, where an
546    /// engine's model is dropped and its verdict kept.
547    #[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}