deduxit 0.4.0

A collection of logic suites: decides, checks, proves step by step and exports sequents of linear logic and of classical, intuitionistic and minimal propositional logic, with checked proofs, Kripke countermodels and Rocq certificates.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
// deduxit © Fabian Lukas Grubmüller 2026
// Licensed under the EUPL

//! Clausal proofs of unsatisfiability in the DRUP format, and a checker of
//! them. A DRUP proof (deletion and reverse unit propagation) is a list of
//! clauses added and deleted; each added clause follows from the clauses
//! before it by unit propagation.
//!
//! A clause `C` follows from clauses `F` by reverse unit propagation (RUP)
//! when assigning every literal of `C` false and propagating the unit
//! clauses of `F` meets a clause with every literal false. Propagation
//! only assigns what `F` and that assignment imply, so `F` entails `C`.
//! The checker keeps the clauses of the formula and of the proof that
//! are not deleted, checks each added clause by RUP against them, and
//! accepts the proof at the first empty clause it adds: every clause it
//! keeps follows from the formula, so the formula entails the empty
//! clause and is unsatisfiable. Deleting a clause only weakens what is
//! kept, so deletions need no check, and a deletion of a clause that is
//! not kept is ignored, as DRAT checkers do.
//!
//! Each check starts from no assignment, propagates the unit clauses
//! kept and the negated clause, and undoes everything after, so nothing
//! of one check carries over to the next but the clauses and their
//! watches. A clause's two watched literals are its first two, which
//! with nothing assigned may be any two.

use super::solver::Lit;
use crate::hash::HashMap;
use crate::limits::{Limits, Phase, Progress, Refusal};
use crate::linear::search::memory::Account;

/// A step of a clausal proof.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum Step {
    /// A clause added, which must follow by RUP.
    Add(Box<[Lit]>),
    /// A clause deleted.
    Delete(Box<[Lit]>),
}

impl Step {
    /// Returns the bytes the step is charged to the memory account.
    pub(crate) const fn bytes(len: usize) -> usize {
        size_of::<Self>() + len * size_of::<Lit>()
    }
}

/// Why the checker refuses a proof: the proof is wrong, whatever the
/// bounds.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Flaw {
    /// A literal of a clause names no variable of the formula.
    Variable {
        /// The step, by its index; `None` for a clause of the formula.
        step: Option<usize>,
    },
    /// A clause added does not follow by RUP.
    NotRup {
        /// The step, by its index.
        step: usize,
    },
    /// The proof never adds the empty clause.
    NoEmptyClause,
}

impl std::fmt::Display for Flaw {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Variable { step: None } => {
                write!(f, "a clause of the formula names no variable of it")
            }
            Self::Variable { step: Some(step) } => {
                write!(f, "step {step} names no variable of the formula")
            }
            Self::NotRup { step } => write!(
                f,
                "the clause of step {step} does not follow by unit propagation"
            ),
            Self::NoEmptyClause => write!(f, "the proof never adds the empty clause"),
        }
    }
}

/// Why a proof was not accepted.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum Rejection {
    /// The proof is wrong.
    Flaw(Flaw),
    /// A bound or the stop ended the check; the proof may be right.
    Refused(Refusal),
}

/// A clausal proof that a classical sequent is valid, which this crate's
/// checker accepted: the clauses of the sequent's negation (every
/// hypothesis true, every formula right of `⊢` false) have no model,
/// since the proof's steps derive the empty clause from them, each added
/// clause by unit propagation.
///
/// It holds what was checked, not the proof itself. Only the check makes
/// one, so a value of this type is a proof that passed it.
///
/// # JSON
///
/// With the feature `serialize` it is written (never read) as
/// `{"variables": 7, "clauses": 12, "steps": 3}`: the variables and the
/// clauses of the negation, and the proof's steps, the clauses it adds and
/// deletes.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize))]
pub struct ClausalProof {
    /// The variables of the clauses: one per formula of the sequent.
    variables: u32,
    /// The clauses of the sequent's negation.
    clauses: u64,
    /// The proof's steps, the empty clause included.
    steps: u64,
}

impl ClausalProof {
    /// Checks `proof` against the clauses `formula` as [`check`] does and
    /// returns what was checked when the check accepts it.
    pub(super) fn checked(
        variables: u32,
        formula: &[Vec<Lit>],
        proof: &[Step],
        limits: &Limits,
        account: &Account,
        stop: impl FnMut(Progress) -> bool,
    ) -> Result<Self, Rejection> {
        check(variables, formula, proof, limits, account, stop)?;
        Ok(Self {
            variables,
            clauses: formula.len() as u64,
            steps: proof.len() as u64,
        })
    }

    /// Returns the variables of the clauses, one per formula of the
    /// sequent.
    pub const fn variables(&self) -> u32 {
        self.variables
    }

    /// Returns how many clauses the sequent's negation has.
    pub const fn clauses(&self) -> u64 {
        self.clauses
    }

    /// Returns how many steps the proof has: the clauses it adds, the empty
    /// one included, and those it deletes.
    pub const fn steps(&self) -> u64 {
        self.steps
    }
}

impl std::fmt::Display for ClausalProof {
    /// Writes what the proof is, for a person: `a checked clausal proof of
    /// 3 steps against the 12 clauses of the sequent's negation`.
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let plural = |n: u64| if n == 1 { "" } else { "s" };
        write!(
            f,
            "a checked clausal proof of {} step{} against the {} clause{} of the sequent's \
             negation",
            self.steps,
            plural(self.steps),
            self.clauses,
            plural(self.clauses)
        )
    }
}

/// How many units of the checker's work (a step, a clause of the formula
/// kept, a unit clause assigned, a literal propagated, a visit of a
/// clause) lie between two polls of the stop.
const POLL: u64 = 1 << 12;

/// How a clause kept is charged to the memory account besides 8 bytes per
/// literal (its literals in the clause and in the index's key): the clause,
/// the index's entry (its key, its vector of indices, a slot of the
/// table), two watches with the slack of their vectors, and the headers of
/// three allocations.
const CLAUSE_BYTES: usize = 224;

/// A clause the checker keeps.
struct Clause {
    /// Its literals, by code ([`code`]), without repeats; the first two are
    /// watched.
    literals: Box<[u32]>,
    /// Whether it is kept, not deleted. A deleted clause leaves the watch
    /// lists when propagation next meets it.
    live: bool,
}

/// Returns a literal's code: twice its variable, plus one for a negation.
/// Codes index the assignment and the watch lists. The variable is below
/// the formula's count, which the solver keeps below `u32::MAX / 2`
/// (`MOST_VARIABLES`), so the code fits a `u32`.
const fn code(literal: Lit) -> u32 {
    literal.var() * 2 + !literal.is_positive() as u32
}

/// The checker's state: the clauses kept, their watches, and the
/// assignment of one check.
struct Checker<'a> {
    /// Every clause added, kept or deleted, by index. An index is below
    /// the vector's length, which memory bounds far below `usize::MAX`.
    clauses: Vec<Clause>,
    /// The clauses kept, by their sorted literals, for deletions.
    index: HashMap<Box<[u32]>, Vec<usize>>,
    /// Per literal code, the clauses of two or more literals watching it.
    watches: Vec<Vec<usize>>,
    /// The clauses of one literal; a deleted one leaves the list at the
    /// next check.
    units: Vec<usize>,
    /// How many empty clauses are kept.
    empty: usize,
    /// Per literal code, whether the check assigned it true.
    holds: Vec<bool>,
    /// The literals the check assigned true, in order.
    trail: Vec<u32>,
    /// The variables of the formula.
    variables: u32,
    /// The memory account the clauses are charged to.
    account: &'a Account,
    /// The units of work (as [`POLL`] lists them) since the stop was last
    /// asked, at most `POLL`.
    ticks: u64,
    /// The steps checked, at most `Limits::work`, which a `u64` holds
    /// since each costs a step of the proof in memory.
    steps: u64,
}

/// Checks that `proof` refutes the clauses `formula` over `variables`
/// variables: each clause added follows by RUP from the formula's and the
/// proof's clauses kept before it, and an empty clause is added. A step
/// is a unit of `limits.work`; the clauses kept are charged to `account`,
/// which refuses past `limits.memory_bytes`; the stop is asked every
/// [`POLL`] units of the checker's work.
pub(crate) fn check(
    variables: u32,
    formula: &[Vec<Lit>],
    proof: &[Step],
    limits: &Limits,
    account: &Account,
    mut stop: impl FnMut(Progress) -> bool,
) -> Result<(), Rejection> {
    let codes = 2 * variables as usize;
    // Saturating: on a 32-bit target the charge refuses before the
    // vectors are made, and never wraps.
    account.charge(codes.saturating_mul(size_of::<Vec<usize>>() + size_of::<bool>()));
    if account.over() {
        return Err(over(account));
    }
    let mut checker = Checker {
        clauses: Vec::new(),
        index: HashMap::default(),
        watches: vec![Vec::new(); codes],
        units: Vec::new(),
        empty: 0,
        holds: vec![false; codes],
        trail: Vec::new(),
        variables,
        account,
        ticks: 0,
        steps: 0,
    };
    for clause in formula {
        checker.tick(1, &mut stop)?;
        let literals = checker
            .normal(clause)
            .ok_or(Rejection::Flaw(Flaw::Variable { step: None }))?;
        checker.keep(literals)?;
    }
    for (n, step) in proof.iter().enumerate() {
        checker.steps += 1;
        if limits.work.is_some_and(|work| checker.steps > work) {
            return Err(Rejection::Refused(Refusal::Work {
                limit: limits.work.unwrap_or(u64::MAX),
            }));
        }
        checker.tick(1, &mut stop)?;
        let (Step::Add(clause) | Step::Delete(clause)) = step;
        let literals = checker
            .normal(clause)
            .ok_or(Rejection::Flaw(Flaw::Variable { step: Some(n) }))?;
        match step {
            Step::Add(_) => {
                if !checker.conflicts(clause, &mut stop)? {
                    return Err(Rejection::Flaw(Flaw::NotRup { step: n }));
                }
                if clause.is_empty() {
                    return Ok(());
                }
                checker.keep(literals)?;
            }
            Step::Delete(_) => checker.delete(literals),
        }
    }
    Err(Rejection::Flaw(Flaw::NoEmptyClause))
}

impl Checker<'_> {
    /// Returns the clause's codes, sorted and without repeats;
    /// `Some(None)` for a tautology, which holds under every assignment
    /// and is never kept; `None` where a literal names no variable of the
    /// formula.
    #[expect(
        clippy::option_option,
        reason = "a clause of a missing variable, a tautology and a clause are three answers"
    )]
    fn normal(&self, clause: &[Lit]) -> Option<Option<Box<[u32]>>> {
        if clause.iter().any(|l| l.var() >= self.variables) {
            return None;
        }
        let mut literals: Vec<u32> = clause.iter().map(|&l| code(l)).collect();
        literals.sort_unstable();
        literals.dedup();
        // Sorted, a literal and its negation are neighbours.
        let tautology = literals.windows(2).any(|w| w[0] ^ 1 == w[1]);
        Some((!tautology).then(|| literals.into_boxed_slice()))
    }

    /// Keeps a clause, sorted without repeats, unless it is a tautology,
    /// charging it to the account.
    fn keep(&mut self, literals: Option<Box<[u32]>>) -> Result<(), Rejection> {
        let Some(literals) = literals else {
            return Ok(());
        };
        let id = self.clauses.len();
        self.account
            .charge(2 * literals.len() * size_of::<u32>() + CLAUSE_BYTES);
        match literals.len() {
            0 => self.empty += 1,
            1 => self.units.push(id),
            _ => {
                self.watches[literals[0] as usize].push(id);
                self.watches[literals[1] as usize].push(id);
            }
        }
        self.index.entry(literals.clone()).or_default().push(id);
        self.clauses.push(Clause {
            literals,
            live: true,
        });
        if self.account.over() {
            return Err(over(self.account));
        }
        Ok(())
    }

    /// Deletes one kept copy of a clause, sorted without repeats; a clause
    /// not kept, or a tautology, is ignored.
    fn delete(&mut self, literals: Option<Box<[u32]>>) {
        let Some(literals) = literals else {
            return;
        };
        let Some(ids) = self.index.get_mut(&literals) else {
            return;
        };
        let Some(id) = ids.pop() else {
            return;
        };
        if ids.is_empty() {
            self.index.remove(&literals);
        }
        self.clauses[id].live = false;
        if literals.is_empty() {
            self.empty -= 1;
        }
    }

    /// Counts `n` units of work, asking the stop once [`POLL`] of them
    /// have passed since it was last asked.
    fn tick(&mut self, n: u64, stop: &mut impl FnMut(Progress) -> bool) -> Result<(), Rejection> {
        // Below `POLL` before, and `n` is at most a vector's length: no
        // wrap.
        self.ticks += n;
        if self.ticks >= POLL {
            let ticks = std::mem::take(&mut self.ticks);
            if stop(Progress::new(Phase::Check, ticks, self.steps)) {
                return Err(Rejection::Refused(Refusal::Stopped {
                    phase: Phase::Check,
                }));
            }
        }
        Ok(())
    }

    /// Assigns the literal true; returns `false` where its negation holds
    /// already, a conflict.
    fn assign(&mut self, literal: u32) -> bool {
        if self.holds[(literal ^ 1) as usize] {
            return false;
        }
        if !self.holds[literal as usize] {
            self.holds[literal as usize] = true;
            self.trail.push(literal);
        }
        true
    }

    /// Returns whether assigning every literal of `clause` false and
    /// propagating the unit clauses kept meets a conflict, undoing the
    /// assignment after.
    fn conflicts(
        &mut self,
        clause: &[Lit],
        stop: &mut impl FnMut(Progress) -> bool,
    ) -> Result<bool, Rejection> {
        let found = self.propagate(clause, stop);
        for &literal in &self.trail {
            self.holds[literal as usize] = false;
        }
        self.trail.clear();
        found
    }

    /// Assigns every literal of `clause` false and the literal of every
    /// unit clause kept true, then propagates; returns whether a conflict
    /// was met. A kept empty clause is a conflict at once.
    fn propagate(
        &mut self,
        clause: &[Lit],
        stop: &mut impl FnMut(Progress) -> bool,
    ) -> Result<bool, Rejection> {
        if self.empty > 0 {
            return Ok(true);
        }
        for &literal in clause {
            if !self.assign(code(literal) ^ 1) {
                return Ok(true);
            }
        }
        // Deleted unit clauses leave the list here.
        let mut units = std::mem::take(&mut self.units);
        units.retain(|&id| self.clauses[id].live);
        let mut conflict = Ok(false);
        for &id in &units {
            if let Err(refused) = self.tick(1, stop) {
                conflict = Err(refused);
                break;
            }
            if !self.assign(self.clauses[id].literals[0]) {
                conflict = Ok(true);
                break;
            }
        }
        self.units = units;
        if conflict != Ok(false) {
            return conflict;
        }
        let mut head = 0;
        while let Some(&holds) = self.trail.get(head) {
            head += 1;
            self.tick(1, stop)?;
            let falsified = holds ^ 1;
            let mut watching = std::mem::take(&mut self.watches[falsified as usize]);
            let mut kept = 0;
            let mut at = 0;
            let mut conflict = false;
            while at < watching.len() {
                let id = watching[at];
                at += 1;
                if let Err(refused) = self.tick(1, stop) {
                    // Keep the watches whole before giving up.
                    watching.drain(kept..at - 1);
                    self.watches[falsified as usize] = watching;
                    return Err(refused);
                }
                let clause = &mut self.clauses[id];
                if !clause.live {
                    continue;
                }
                if clause.literals[0] == falsified {
                    clause.literals.swap(0, 1);
                }
                let first = clause.literals[0];
                if self.holds[first as usize] {
                    watching[kept] = id;
                    kept += 1;
                    continue;
                }
                let other = clause.literals[2..]
                    .iter()
                    .position(|&l| !self.holds[(l ^ 1) as usize]);
                if let Some(k) = other {
                    clause.literals.swap(1, k + 2);
                    let watched = clause.literals[1];
                    self.watches[watched as usize].push(id);
                    continue;
                }
                watching[kept] = id;
                kept += 1;
                if !self.assign(first) {
                    conflict = true;
                    break;
                }
            }
            // Drop the clauses visited that moved to another watch or were
            // deleted; those not visited stay watched.
            watching.drain(kept..at);
            self.watches[falsified as usize] = watching;
            if conflict {
                return Ok(true);
            }
        }
        Ok(false)
    }
}

/// The refusal of a check past the memory account's bound.
fn over(account: &Account) -> Rejection {
    Rejection::Refused(Refusal::Memory {
        phase: Phase::Check,
        limit_bytes: account.limit(),
        needed_bytes: None,
    })
}

/// Writes the formula in DIMACS's CNF format and the proof in DRUP's text
/// format, for an outside checker.
#[cfg(all(test, feature = "parse"))]
pub(crate) fn dimacs(variables: u32, formula: &[Vec<Lit>], proof: &[Step]) -> (String, String) {
    use std::fmt::Write;
    let number = |l: Lit| {
        let n = i64::from(l.var()) + 1;
        if l.is_positive() { n } else { -n }
    };
    let mut cnf = format!("p cnf {variables} {}\n", formula.len());
    for clause in formula {
        for &l in clause {
            write!(cnf, "{} ", number(l)).unwrap();
        }
        cnf.push_str("0\n");
    }
    let mut drup = String::new();
    for step in proof {
        let (Step::Add(clause) | Step::Delete(clause)) = step;
        if matches!(step, Step::Delete(_)) {
            drup.push_str("d ");
        }
        for &l in clause.iter() {
            write!(drup, "{} ", number(l)).unwrap();
        }
        drup.push_str("0\n");
    }
    (cnf, drup)
}

#[cfg(test)]
mod tests {
    use super::{Flaw, Rejection, Step, check};
    use crate::limits::{Limits, Refusal};
    use crate::linear::search::memory::Account;
    use crate::ordinary::sat::solver::Lit;

    /// The literal of a DIMACS number.
    fn lit(n: i32) -> Lit {
        let var = n.unsigned_abs() - 1;
        if n > 0 {
            Lit::positive(var)
        } else {
            Lit::negative(var)
        }
    }

    /// The clauses of DIMACS numbers.
    fn clauses(numbers: &[&[i32]]) -> Vec<Vec<Lit>> {
        numbers
            .iter()
            .map(|c| c.iter().map(|&n| lit(n)).collect())
            .collect()
    }

    /// A step adding the clause.
    fn add(numbers: &[i32]) -> Step {
        Step::Add(numbers.iter().map(|&n| lit(n)).collect())
    }

    /// A step deleting the clause.
    fn delete(numbers: &[i32]) -> Step {
        Step::Delete(numbers.iter().map(|&n| lit(n)).collect())
    }

    /// Checks the proof within the default limits.
    fn run(variables: u32, formula: &[&[i32]], proof: &[Step]) -> Result<(), Rejection> {
        let limits = Limits::default();
        let account = Account::holding(limits.memory_bytes, 0);
        check(
            variables,
            &clauses(formula),
            proof,
            &limits,
            &account,
            |_| false,
        )
    }

    /// Every pair of two variables' literals as a clause: unsatisfiable,
    /// refuted by learning `x₁` and then the empty clause.
    const SQUARE: &[&[i32]] = &[&[1, 2], &[1, -2], &[-1, 2], &[-1, -2]];

    /// A correct proof is accepted; a planted wrong step, a missing empty
    /// clause, a deletion of a clause a later step needs and an unknown
    /// variable are refused, each for its reason.
    #[test]
    fn a_planted_wrong_step_is_refused() {
        assert_eq!(run(2, SQUARE, &[add(&[1]), add(&[])]), Ok(()));
        // A clause deleted that nothing kept, and a tautology, are ignored.
        let ignored = [delete(&[1, 2, -2]), delete(&[2]), add(&[1]), add(&[])];
        assert_eq!(run(2, SQUARE, &ignored), Ok(()));
        // `x₁ ∨ x₂` alone does not give `x₂` by propagation.
        let wrong = [add(&[2]), add(&[1]), add(&[])];
        let partial: &[&[i32]] = &[&[1, 2], &[1, -2], &[-1, -2]];
        assert_eq!(
            run(2, partial, &wrong),
            Err(Rejection::Flaw(Flaw::NotRup { step: 0 }))
        );
        assert_eq!(
            run(2, SQUARE, &[add(&[1])]),
            Err(Rejection::Flaw(Flaw::NoEmptyClause))
        );
        // Without `¬x₁ ∨ x₂` the empty clause no longer follows from `x₁`.
        let deleted = [add(&[1]), delete(&[-1, 2]), add(&[])];
        assert_eq!(
            run(2, SQUARE, &deleted),
            Err(Rejection::Flaw(Flaw::NotRup { step: 2 }))
        );
        assert_eq!(
            run(2, SQUARE, &[add(&[3]), add(&[])]),
            Err(Rejection::Flaw(Flaw::Variable { step: Some(0) }))
        );
        assert_eq!(
            run(1, SQUARE, &[add(&[])]),
            Err(Rejection::Flaw(Flaw::Variable { step: None }))
        );
    }

    /// The work, the memory and the stop refuse a check, none a flaw.
    #[test]
    fn the_bounds_refuse_a_check() {
        let proof = [add(&[1]), add(&[])];
        let limits = Limits::default().with_work(Some(1));
        let account = Account::holding(limits.memory_bytes, 0);
        let formula = clauses(SQUARE);
        assert_eq!(
            check(2, &formula, &proof, &limits, &account, |_| false),
            Err(Rejection::Refused(Refusal::Work { limit: 1 }))
        );
        let limits = Limits::default().with_memory_bytes(Some(64));
        let account = Account::holding(limits.memory_bytes, 0);
        assert!(matches!(
            check(2, &formula, &proof, &limits, &account, |_| false),
            Err(Rejection::Refused(Refusal::Memory { .. }))
        ));
        // `x₁`, a chain of implications `xᵢ → xᵢ₊₁` and `¬xₙ`, long enough
        // that the one check visits more clauses than two polls' worth.
        let n = 3 * super::POLL as i32;
        let mut chain: Vec<Vec<i32>> = (1..n).map(|i| vec![-i, i + 1]).collect();
        chain.push(vec![1]);
        chain.push(vec![-n]);
        let chain: Vec<&[i32]> = chain.iter().map(Vec::as_slice).collect();
        let limits = Limits::default();
        let account = Account::holding(limits.memory_bytes, 0);
        let mut asked = 0;
        let result = check(
            n as u32,
            &clauses(&chain),
            &[add(&[])],
            &limits,
            &account,
            |_| {
                asked += 1;
                asked > 1
            },
        );
        assert_eq!(
            result,
            Err(Rejection::Refused(Refusal::Stopped {
                phase: crate::limits::Phase::Check
            }))
        );
        assert_eq!(run(n as u32, &chain, &[add(&[])]), Ok(()));
        // Many unit clauses, `x₁` last: each check assigns them all before
        // the conflict, and asks the stop at least once on the way.
        let n = super::POLL as i32;
        let mut units: Vec<Vec<i32>> = (2..=n).map(|i| vec![i]).collect();
        units.push(vec![1]);
        let units: Vec<&[i32]> = units.iter().map(Vec::as_slice).collect();
        let steps = 8;
        let proof: Vec<Step> = (0..steps).map(|_| add(&[1, n + 1])).collect();
        let mut asked = 0;
        let result = check(
            n as u32 + 1,
            &clauses(&units),
            &proof,
            &limits,
            &account,
            |_| {
                asked += 1;
                false
            },
        );
        assert_eq!(result, Err(Rejection::Flaw(Flaw::NoEmptyClause)));
        assert!(asked >= steps, "{asked} polls for {steps} checks");
    }
}