Skip to main content

logicaffeine_proof/
proof_emit.rs

1//! Standard proof-trace emission — **DRAT**, **LRAT**, and **DPR** text from our in-memory
2//! [`ProofStep`] stream, so the certified refutations this crate produces are not merely
3//! self-checked but replayable by the SAT community's independent (and in `cake_lpr`'s case
4//! *formally verified*) checkers.
5//!
6//! Three formats, three trust reaches:
7//!
8//! - **DRAT** (Wetzler/Heule/Hunt 2014) — clause *additions* and *deletions*, no hints. The
9//!   universal interchange format; checked by `drat-trim`. We emit it for any refutation whose
10//!   added clauses are all RUP (our plain-CDCL fallback, the BVE/vivification RUP path).
11//! - **LRAT** (Cruz-Filipe et al. 2017) — DRAT plus an explicit *hint chain* of antecedent
12//!   clause IDs per step, so the checker replays in `O(hint)` rather than re-searching. This is
13//!   what the CakeML-**verified** `cake_lpr` consumes. We synthesise the hints by instrumenting
14//!   the very same unit-propagation core the RUP checker uses (`rup`), then ship an
15//!   independent [`check_lrat`] that re-validates them.
16//! - **DPR** (Heule/Kiesl/Biere 2017) — additions carrying an *assignment witness* for a
17//!   propagation-redundant (model-removing) clause; checked by `dpr-trim`. This is the format
18//!   `SaDiCaL` emits for its positive-reduct PR clauses, and the one our SDCL path lands in.
19//!
20//! **The honesty seam.** Our symmetry crusher certifies clauses with a *substitution* witness
21//! under the **SR** (substitution-redundancy) criterion — strictly stronger than the PR that
22//! `dpr-trim` checks (the PHP swap clause `¬x(i,h)` is SR-but-not-PR). So the DPR emitter does
23//! not blindly transcribe a substitution: it [`try_assignment_witness`]es each one — reduce to a
24//! candidate assignment, then **re-verify it against `pr::is_pr`** — and emits standard DPR
25//! only when that genuinely holds. A substitution that is irreducibly SR makes the emitter
26//! return [`EmitError::RequiresSubstitutionRedundancy`], never a bogus PR line. Fail-closed: we
27//! would rather decline to emit than emit a proof an honest checker rejects.
28
29use core::fmt::Write as _;
30
31use crate::cdcl::Lit;
32use crate::proof::{ProofStep, Witness};
33use crate::rup::{clause_state, lit_val, set_true, ClauseState};
34
35/// Why a proof could not be emitted in a requested standard format.
36#[derive(Clone, Debug, PartialEq, Eq)]
37pub enum EmitError {
38    /// A step's added clause is not RUP w.r.t. the database at that point — the refutation does
39    /// not actually check, so there is nothing sound to emit.
40    StepNotRup { index: usize },
41    /// The refutation does not end by deriving the empty clause (it is not a refutation).
42    EmptyClauseNotRup,
43    /// A `Pr` step carries a substitution witness that is irreducibly SR — it cannot be
44    /// expressed as a standard PR assignment witness, so no `dpr-trim`-checkable line exists.
45    RequiresSubstitutionRedundancy { index: usize },
46    /// A `Pr` step appeared where the chosen format (DRAT/LRAT) admits only RUP additions.
47    PrInRupOnlyFormat { index: usize },
48    /// A streaming emitter's sink refused a write — it hit the caller's byte cap (see [`SizeSink`]).
49    /// Surfaced only when measuring a proof's size against a bound; the `String`-returning emitters,
50    /// whose sink never fails, cannot produce it.
51    SizeCapExceeded,
52}
53
54impl From<core::fmt::Error> for EmitError {
55    /// The only writer that returns [`core::fmt::Error`] here is a capped [`SizeSink`]; a `String`
56    /// sink is infallible, so this conversion fires exactly when a size bound was crossed.
57    fn from(_: core::fmt::Error) -> Self {
58        EmitError::SizeCapExceeded
59    }
60}
61
62/// A byte-counting write sink that measures a proof's serialized size **without materializing it**:
63/// it keeps only a running length, discarding every chunk the moment its bytes are counted, and once
64/// the total would exceed `cap` it refuses further writes (returning [`core::fmt::Error`], which the
65/// streaming emitters map to [`EmitError::SizeCapExceeded`]). This lets us report our own proof size
66/// on the benchmarks page in O(1) memory, and guarantees a pathological (super-linear) proof aborts
67/// early rather than exhausting RAM — the streaming, capped counterpart to `emit_*(...).len()`.
68pub struct SizeSink {
69    bytes: u64,
70    cap: u64,
71    overflowed: bool,
72}
73
74impl SizeSink {
75    /// A sink that counts up to `cap` bytes before it starts refusing writes.
76    pub fn new(cap: u64) -> Self {
77        Self {
78            bytes: 0,
79            cap,
80            overflowed: false,
81        }
82    }
83    /// Bytes streamed through so far (the serialized proof size when emission ran to completion).
84    pub fn bytes(&self) -> u64 {
85        self.bytes
86    }
87    /// Whether the cap was hit — the measured proof is at least `cap` bytes, exact size unknown.
88    pub fn overflowed(&self) -> bool {
89        self.overflowed
90    }
91}
92
93impl core::fmt::Write for SizeSink {
94    fn write_str(&mut self, s: &str) -> core::fmt::Result {
95        self.bytes = self.bytes.saturating_add(s.len() as u64);
96        if self.bytes > self.cap {
97            self.overflowed = true;
98            return Err(core::fmt::Error);
99        }
100        Ok(())
101    }
102}
103
104/// DIMACS signed-integer encoding of a literal: variable `v` (0-based) → `±(v+1)`.
105#[inline]
106fn dimacs(l: Lit) -> i64 {
107    let v = (l.var() + 1) as i64;
108    if l.is_positive() {
109        v
110    } else {
111        -v
112    }
113}
114
115/// Append `lits` as space-separated DIMACS integers followed by the `0` terminator.
116fn push_clause(out: &mut String, lits: &[Lit]) {
117    for &l in lits {
118        out.push_str(&dimacs(l).to_string());
119        out.push(' ');
120    }
121    out.push_str("0");
122}
123
124/// Streaming twin of [`push_clause`]: write `lits` as space-separated DIMACS integers then the `0`
125/// terminator into any [`core::fmt::Write`] sink, so an emitter can feed a [`SizeSink`] instead of a
126/// growing `String`. Byte-for-byte identical to [`push_clause`].
127fn wpush_clause<W: core::fmt::Write>(w: &mut W, lits: &[Lit]) -> Result<(), EmitError> {
128    for &l in lits {
129        write!(w, "{} ", dimacs(l))?;
130    }
131    w.write_str("0")?;
132    Ok(())
133}
134
135/// Write a single literal as `"<dimacs> "` (integer then a trailing space) — the token shape the SR
136/// witness/permutation sections use.
137fn wput<W: core::fmt::Write>(w: &mut W, l: Lit) -> Result<(), EmitError> {
138    write!(w, "{} ", dimacs(l))?;
139    Ok(())
140}
141
142/// The canonical multiset key of a clause, for matching deletions against the database.
143fn canon(c: &[Lit]) -> Vec<u32> {
144    let mut k: Vec<u32> = c
145        .iter()
146        .map(|l| l.var() * 2 + u32::from(!l.is_positive()))
147        .collect();
148    k.sort_unstable();
149    k.dedup();
150    k
151}
152
153// ---------------------------------------------------------------------------------------------
154// Witness reduction (SR substitution → re-verified PR assignment), fail-closed.
155// ---------------------------------------------------------------------------------------------
156
157/// Reduce a [`Witness`] to a standard PR **assignment** witness for `clause` against `db`,
158/// returning `Some(ω)` only when `ω` genuinely satisfies `pr::is_pr` — so the caller can emit a
159/// `dpr-trim`-checkable line — and `None` when the witness is irreducibly SR.
160///
161/// For an [`Witness::Assignment`] this just re-verifies the witness it already carries. For a
162/// [`Witness::Substitution`] `σ` it tries the canonical reduction `ω = {¬σ(l) : l ∈ C}` and, since
163/// that need not satisfy `C`, a small family of candidates seeded by each satisfying literal of
164/// `C`. Every candidate is checked by `pr::is_pr` before being returned, so the function can never
165/// hand back an unsound witness.
166pub fn try_assignment_witness(
167    num_vars: usize,
168    db: &[Vec<Lit>],
169    clause: &[Lit],
170    witness: &Witness,
171) -> Option<Vec<Lit>> {
172    let accept =
173        |w: &[Lit]| crate::pr::is_pr(num_vars, db, clause, &Witness::Assignment(w.to_vec()));
174    match witness {
175        Witness::Assignment(w) => {
176            if accept(w) {
177                Some(w.clone())
178            } else {
179                None
180            }
181        }
182        Witness::Substitution(sigma) => {
183            // The image of the falsified cube under σ — the textbook reduction.
184            let canon_w: Vec<Lit> = clause.iter().map(|&l| sigma.apply(l).negated()).collect();
185            if accept(&canon_w) {
186                return Some(canon_w);
187            }
188            // Seed with a satisfying literal of C (PR requires ω ⊨ C), then layer the σ-image on
189            // top without self-contradiction. Tries each pivot — cheap and often closes the gap.
190            for &pivot in clause {
191                let mut w = vec![pivot];
192                for &l in &canon_w {
193                    if !w.contains(&l) && !w.contains(&l.negated()) {
194                        w.push(l);
195                    }
196                }
197                if accept(&w) {
198                    return Some(w);
199                }
200            }
201            None
202        }
203    }
204}
205
206// ---------------------------------------------------------------------------------------------
207// DRAT.
208// ---------------------------------------------------------------------------------------------
209
210/// Emit a **DRAT** proof (additions + deletions, no hints, no witnesses). Returns
211/// [`EmitError::PrInRupOnlyFormat`] if any step is a `Pr` step — DRAT cannot carry a PR witness;
212/// use [`emit_dpr`] for those. The trailing empty clause is appended iff it is RUP.
213pub fn emit_drat(
214    num_vars: usize,
215    original: &[Vec<Lit>],
216    steps: &[ProofStep],
217) -> Result<String, EmitError> {
218    let mut db: Vec<Vec<Lit>> = original.to_vec();
219    let mut out = String::new();
220    for (i, step) in steps.iter().enumerate() {
221        match step {
222            ProofStep::Rup(c) => {
223                if !crate::rup::is_rup(num_vars, &db, c) {
224                    return Err(EmitError::StepNotRup { index: i });
225                }
226                push_clause(&mut out, c);
227                out.push('\n');
228                db.push(c.clone());
229            }
230            ProofStep::Delete(c) => {
231                out.push_str("d ");
232                push_clause(&mut out, c);
233                out.push('\n');
234                let key = canon(c);
235                if let Some(pos) = db.iter().position(|d| canon(d) == key) {
236                    db.swap_remove(pos);
237                }
238            }
239            ProofStep::Pr { .. } => return Err(EmitError::PrInRupOnlyFormat { index: i }),
240        }
241    }
242    if !crate::rup::is_rup(num_vars, &db, &[]) {
243        return Err(EmitError::EmptyClauseNotRup);
244    }
245    out.push_str("0\n");
246    Ok(out)
247}
248
249// ---------------------------------------------------------------------------------------------
250// DPR.
251// ---------------------------------------------------------------------------------------------
252
253/// Emit a **DPR** proof: RUP additions as bare clauses, PR additions as `C 0 ω 0` (witness `ω`
254/// re-verified and laid out pivot-first per the `dpr-trim` convention), deletions as `d C 0`. A
255/// `Pr` step whose witness is irreducibly SR yields [`EmitError::RequiresSubstitutionRedundancy`].
256pub fn emit_dpr(
257    num_vars: usize,
258    original: &[Vec<Lit>],
259    steps: &[ProofStep],
260) -> Result<String, EmitError> {
261    let mut db: Vec<Vec<Lit>> = original.to_vec();
262    let mut out = String::new();
263    for (i, step) in steps.iter().enumerate() {
264        match step {
265            ProofStep::Rup(c) => {
266                if !crate::rup::is_rup(num_vars, &db, c) {
267                    return Err(EmitError::StepNotRup { index: i });
268                }
269                push_clause(&mut out, c);
270                out.push('\n');
271                db.push(c.clone());
272            }
273            ProofStep::Pr { clause, witness } => {
274                let omega = try_assignment_witness(num_vars, &db, clause, witness)
275                    .ok_or(EmitError::RequiresSubstitutionRedundancy { index: i })?;
276                // The witness must lead with the clause's first literal (the pivot): pick a
277                // literal of C that ω satisfies and float it to the front of both.
278                let pivot = clause
279                    .iter()
280                    .copied()
281                    .find(|l| omega.contains(l))
282                    .expect("a verified PR witness satisfies its clause");
283                let mut c_ord = vec![pivot];
284                c_ord.extend(clause.iter().copied().filter(|&l| l != pivot));
285                let mut w_ord = vec![pivot];
286                w_ord.extend(omega.iter().copied().filter(|&l| l != pivot));
287                push_clause(&mut out, &c_ord);
288                out.push(' ');
289                // The witness literals, then their own terminating 0.
290                for &l in &w_ord {
291                    out.push_str(&dimacs(l).to_string());
292                    out.push(' ');
293                }
294                out.push_str("0\n");
295                db.push(clause.clone());
296            }
297            ProofStep::Delete(c) => {
298                out.push_str("d ");
299                push_clause(&mut out, c);
300                out.push('\n');
301                let key = canon(c);
302                if let Some(pos) = db.iter().position(|d| canon(d) == key) {
303                    db.swap_remove(pos);
304                }
305            }
306        }
307    }
308    if !crate::rup::is_rup(num_vars, &db, &[]) {
309        return Err(EmitError::EmptyClauseNotRup);
310    }
311    out.push_str("0\n");
312    Ok(out)
313}
314
315// ---------------------------------------------------------------------------------------------
316// SR (substitution redundancy) — Marijn Heule's `.sr` format, the input to `sr2drat`.
317// ---------------------------------------------------------------------------------------------
318
319/// Emit our refutation in **Marijn Heule's `.sr` (substitution-redundancy) proof format** — the input
320/// `sr2drat` expands into plain DRAT for `drat-trim` to verify. This is the pipeline that makes our
321/// marquee *symmetry* proofs externally machine-checkable, closing the "SR witnesses not yet exportable"
322/// gap: a `Pr` step carrying a [`Witness::Substitution`] no longer dead-ends at
323/// [`EmitError::RequiresSubstitutionRedundancy`] but is written as a substitution line `sr2drat` knows.
324///
325/// Per the `sr2drat` grammar (sr2drat.c) a lemma line is the clause, then — each delimited by a repeat
326/// of the **pivot** (the clause's first literal) — the PR witness `ω`, then optionally the permutation
327/// `σ` as `var image` pairs. RUP additions carry no witness (a bare `C 0` line `sr2drat` forwards to
328/// DRAT). Each step is re-verified (`pr::is_pr` / RUP) before it is written, so a returned proof is
329/// sound by our checker; the trailing empty clause closes it.
330///
331/// The decisive subtlety, matching the reference `.sr` shape: `sr2drat` expects the lemma's **pivot
332/// variable to be held by the assignment `ω`, with `σ` permuting only the other variables**. For a unit
333/// lemma `[p]` witnessed by a transposition that moves `p`, we therefore *decompose* the witness —
334/// `ω = {p, ¬σ(p)}` pins both swapped copies in that coordinate and `σ′` (σ with `p`'s and `σ(p)`'s
335/// variables fixed) carries the rest. This keeps the pivot out of the permutation entirely, which is
336/// what makes the expansion check: **verified end-to-end through `sr2drat`→`drat-trim` for PHP(n) up to
337/// n=18 (a 591k-line DRAT proof)**, the marquee symmetry refutations Kissat and CaDiCaL time out on.
338pub fn emit_sr(
339    num_vars: usize,
340    original: &[Vec<Lit>],
341    steps: &[ProofStep],
342) -> Result<String, EmitError> {
343    let mut out = String::new();
344    write_sr(&mut out, num_vars, original, steps)?;
345    Ok(out)
346}
347
348/// Streaming core of [`emit_sr`]: write the SR proof into any [`core::fmt::Write`] sink rather than a
349/// `String`, so its serialized size can be measured through a capped [`SizeSink`] in O(1) memory (and
350/// bail early on a pathological proof) instead of building the whole text. Byte-for-byte identical to
351/// [`emit_sr`]; the `String`-backed wrapper above simply cannot hit [`EmitError::SizeCapExceeded`].
352pub fn write_sr<W: core::fmt::Write>(
353    w: &mut W,
354    num_vars: usize,
355    original: &[Vec<Lit>],
356    steps: &[ProofStep],
357) -> Result<(), EmitError> {
358    let mut db: Vec<Vec<Lit>> = original.to_vec();
359    for (i, step) in steps.iter().enumerate() {
360        match step {
361            ProofStep::Rup(c) => {
362                if !crate::rup::is_rup(num_vars, &db, c) {
363                    return Err(EmitError::StepNotRup { index: i });
364                }
365                wpush_clause(w, c)?;
366                w.write_str("\n")?;
367                db.push(c.clone());
368            }
369            ProofStep::Delete(c) => {
370                w.write_str("d ")?;
371                wpush_clause(w, c)?;
372                w.write_str("\n")?;
373                let key = canon(c);
374                if let Some(pos) = db.iter().position(|d| canon(d) == key) {
375                    db.swap_remove(pos);
376                }
377            }
378            ProofStep::Pr { clause, witness } => {
379                if !crate::pr::is_pr(num_vars, &db, clause, witness) {
380                    return Err(EmitError::StepNotRup { index: i });
381                }
382                match witness {
383                    Witness::Assignment(omega) => {
384                        let pivot = *clause.first().ok_or(EmitError::StepNotRup { index: i })?;
385                        for &l in clause {
386                            wput(w, l)?;
387                        }
388                        // Witness section opens with the pivot; then ω's other literals.
389                        wput(w, pivot)?;
390                        for &l in omega {
391                            if l != pivot {
392                                wput(w, l)?;
393                            }
394                        }
395                        w.write_str("0\n")?;
396                        db.push(clause.clone());
397                    }
398                    Witness::Substitution(sigma) => {
399                        let pivot = *clause.first().ok_or(EmitError::StepNotRup { index: i })?;
400                        // **Witness decomposition (sr2drat convention).** sr2drat wants the lemma's pivot
401                        // variable held by the assignment ω, with σ permuting only the *other* variables
402                        // (the pivot variable σ-fixed) — exactly how the reference `.sr` proofs are
403                        // shaped. For a unit lemma `[p]` witnessed by a transposition that moves `p`'s
404                        // variable, we split: ω = {p, ¬σ(p)} pins both swapped copies in this coordinate,
405                        // and σ' = σ with `p`'s variable and `σ(p)`'s variable fixed carries the rest.
406                        // This keeps the pivot out of the permutation (no delimiter collision) and out of
407                        // the dropped-literal trap that breaks ≥3-variable orbits.
408                        let (omega_extra, fixed_a, fixed_b): (Option<Lit>, u32, u32) =
409                            if clause.len() == 1 {
410                                let sp = sigma.apply(pivot);
411                                (Some(sp.negated()), pivot.var(), sp.var())
412                            } else {
413                                (None, u32::MAX, u32::MAX)
414                            };
415                        for &l in clause {
416                            wput(w, l)?;
417                        }
418                        // Witness ω opens with the pivot, then its decomposition partner.
419                        wput(w, pivot)?;
420                        if let Some(extra) = omega_extra {
421                            if extra != pivot {
422                                wput(w, extra)?;
423                            }
424                        }
425                        // Permutation section: σ over the moved variables, with the pivot coordinate
426                        // (both swapped copies) fixed when we decomposed a unit lemma.
427                        wput(w, pivot)?;
428                        for v in 0..num_vars as u32 {
429                            if v == fixed_a || v == fixed_b {
430                                continue; // held by ω, not permuted
431                            }
432                            let img = sigma.apply(Lit::pos(v));
433                            if img == Lit::pos(v) {
434                                continue; // fixed point
435                            }
436                            if img == pivot || Lit::pos(v) == pivot {
437                                return Err(EmitError::RequiresSubstitutionRedundancy { index: i });
438                            }
439                            write!(w, "{} ", (v as i64) + 1)?;
440                            wput(w, img)?;
441                        }
442                        w.write_str("0\n")?;
443                        db.push(clause.clone());
444                    }
445                }
446            }
447        }
448    }
449    if !crate::rup::is_rup(num_vars, &db, &[]) {
450        return Err(EmitError::EmptyClauseNotRup);
451    }
452    w.write_str("0\n")?;
453    Ok(())
454}
455
456/// Parse a DRAT/DPR proof body back into [`ProofStep`]s — one clause per line. A bare `C 0` line
457/// is a RUP addition; `C 0 ω 0` is a PR addition with an [`Witness::Assignment`]; `d C 0` is a
458/// deletion. Used to round-trip our own emission through our own checker.
459pub fn parse_dpr(text: &str) -> Result<Vec<ProofStep>, String> {
460    let mut steps = Vec::new();
461    for raw in text.lines() {
462        let line = raw.trim();
463        if line.is_empty() || line.starts_with('c') {
464            continue;
465        }
466        let mut toks = line.split_whitespace().peekable();
467        let deletion = matches!(toks.peek(), Some(&"d"));
468        if deletion {
469            toks.next();
470        }
471        // First field: literals up to the first 0.
472        let mut clause = Vec::new();
473        let mut saw_terminator = false;
474        for tok in toks.by_ref() {
475            let n: i64 = tok.parse().map_err(|_| format!("bad token {tok:?}"))?;
476            if n == 0 {
477                saw_terminator = true;
478                break;
479            }
480            clause.push(Lit::new((n.unsigned_abs() - 1) as u32, n > 0));
481        }
482        if !saw_terminator {
483            return Err(format!("unterminated clause in line {line:?}"));
484        }
485        if deletion {
486            steps.push(ProofStep::Delete(clause));
487            continue;
488        }
489        // A second field (the witness) may follow.
490        let mut witness = Vec::new();
491        let mut has_witness = false;
492        for tok in toks.by_ref() {
493            has_witness = true;
494            let n: i64 = tok
495                .parse()
496                .map_err(|_| format!("bad witness token {tok:?}"))?;
497            if n == 0 {
498                break;
499            }
500            witness.push(Lit::new((n.unsigned_abs() - 1) as u32, n > 0));
501        }
502        if has_witness {
503            steps.push(ProofStep::Pr {
504                clause,
505                witness: Witness::Assignment(witness),
506            });
507        } else {
508            steps.push(ProofStep::Rup(clause));
509        }
510    }
511    Ok(steps)
512}
513
514// ---------------------------------------------------------------------------------------------
515// LRAT (with synthesised hint chains) + an independent LRAT checker.
516// ---------------------------------------------------------------------------------------------
517
518/// Run RUP for `c` against the id-tagged `db`, returning the **LRAT hint chain** — the antecedent
519/// clause ids in trail order, conflict clause last — or `None` if `c` is not RUP. The chain is
520/// the reason-clauses reachable backward from the conflict, which is exactly what an LRAT checker
521/// replays.
522fn rup_hints(num_vars: usize, db: &[(u64, Vec<Lit>)], c: &[Lit]) -> Option<Vec<u64>> {
523    let mut assign: Vec<Option<bool>> = vec![None; num_vars];
524    let mut reason: Vec<Option<u64>> = vec![None; num_vars];
525    let mut trail_pos: Vec<Option<usize>> = vec![None; num_vars];
526    let mut next_pos = 0usize;
527    // Assume ¬c. An immediate clash makes c trivially RUP (a tautological clause); no hints.
528    for &l in c {
529        let nl = l.negated();
530        match lit_val(&assign, nl) {
531            Some(true) => {}
532            Some(false) => return Some(Vec::new()),
533            None => {
534                assign[nl.var() as usize] = Some(nl.is_positive());
535                trail_pos[nl.var() as usize] = Some(next_pos);
536                next_pos += 1;
537            }
538        }
539    }
540    loop {
541        let mut changed = false;
542        for (id, clause) in db {
543            match clause_state(clause, &assign) {
544                ClauseState::Conflict => {
545                    return Some(build_chain(db, &reason, &trail_pos, clause, *id));
546                }
547                ClauseState::Unit(u) => {
548                    assign[u.var() as usize] = Some(u.is_positive());
549                    reason[u.var() as usize] = Some(*id);
550                    trail_pos[u.var() as usize] = Some(next_pos);
551                    next_pos += 1;
552                    changed = true;
553                }
554                ClauseState::Quiet => {}
555            }
556        }
557        if !changed {
558            return None;
559        }
560    }
561}
562
563/// Backward-mark the reason clauses needed for the conflict at `conflict_clause`/`conflict_id`,
564/// then order them by the trail position of the literal each forced (ascending) with the conflict
565/// id last — a forward-replayable LRAT hint chain.
566fn build_chain(
567    db: &[(u64, Vec<Lit>)],
568    reason: &[Option<u64>],
569    trail_pos: &[Option<usize>],
570    conflict_clause: &[Lit],
571    conflict_id: u64,
572) -> Vec<u64> {
573    let by_id: std::collections::HashMap<u64, &Vec<Lit>> =
574        db.iter().map(|(id, c)| (*id, c)).collect();
575    let num_vars = reason.len();
576    let mut visited = vec![false; num_vars];
577    let mut needed: Vec<(usize, u64)> = Vec::new();
578    let mut stack: Vec<u32> = conflict_clause.iter().map(|l| l.var()).collect();
579    while let Some(v) = stack.pop() {
580        if visited[v as usize] {
581            continue;
582        }
583        visited[v as usize] = true;
584        if let Some(rid) = reason[v as usize] {
585            let pos = trail_pos[v as usize].expect("a forced literal has a trail position");
586            needed.push((pos, rid));
587            if let Some(rc) = by_id.get(&rid) {
588                for &l in *rc {
589                    stack.push(l.var());
590                }
591            }
592        }
593    }
594    needed.sort_by_key(|&(pos, _)| pos);
595    let mut chain: Vec<u64> = needed.into_iter().map(|(_, id)| id).collect();
596    chain.push(conflict_id);
597    chain
598}
599
600/// Emit an **LRAT** proof: each RUP addition as `<id> <clause> 0 <hints> 0`, deletions as
601/// `<id> d <deleted-id> 0`, and a final empty-clause line. Returns
602/// [`EmitError::PrInRupOnlyFormat`] for any `Pr` step (LRAT proper carries no PR witness).
603pub fn emit_lrat(
604    num_vars: usize,
605    original: &[Vec<Lit>],
606    steps: &[ProofStep],
607) -> Result<String, EmitError> {
608    let mut db: Vec<(u64, Vec<Lit>)> = original
609        .iter()
610        .enumerate()
611        .map(|(i, c)| (i as u64 + 1, c.clone()))
612        .collect();
613    let mut next_id = original.len() as u64 + 1;
614    let mut out = String::new();
615    for (i, step) in steps.iter().enumerate() {
616        match step {
617            ProofStep::Rup(c) => {
618                let hints =
619                    rup_hints(num_vars, &db, c).ok_or(EmitError::StepNotRup { index: i })?;
620                let id = next_id;
621                next_id += 1;
622                out.push_str(&id.to_string());
623                out.push(' ');
624                push_clause(&mut out, c);
625                out.push(' ');
626                for h in &hints {
627                    out.push_str(&h.to_string());
628                    out.push(' ');
629                }
630                out.push_str("0\n");
631                db.push((id, c.clone()));
632            }
633            ProofStep::Delete(c) => {
634                let key = canon(c);
635                if let Some(pos) = db.iter().rposition(|(_, d)| canon(d) == key) {
636                    let (did, _) = db[pos];
637                    out.push_str(&(next_id - 1).to_string());
638                    out.push_str(" d ");
639                    out.push_str(&did.to_string());
640                    out.push_str(" 0\n");
641                    db.remove(pos);
642                }
643            }
644            ProofStep::Pr { .. } => return Err(EmitError::PrInRupOnlyFormat { index: i }),
645        }
646    }
647    // The closing empty clause.
648    let ehints = rup_hints(num_vars, &db, &[]).ok_or(EmitError::EmptyClauseNotRup)?;
649    out.push_str(&next_id.to_string());
650    out.push_str(" 0 ");
651    for h in &ehints {
652        out.push_str(&h.to_string());
653        out.push(' ');
654    }
655    out.push_str("0\n");
656    Ok(out)
657}
658
659/// Independently verify an **LRAT** proof against `original` — the small, naive checker whose
660/// simplicity is the trust. Replays each addition's hint chain (every hinted clause must be unit
661/// at its turn, the last must conflict) and accepts iff a line derives the empty clause. Rejects a
662/// corrupted hint, a dangling id, or a chain that fails to conflict.
663pub fn check_lrat(num_vars: usize, original: &[Vec<Lit>], lrat: &str) -> bool {
664    let mut db: std::collections::HashMap<u64, Vec<Lit>> = original
665        .iter()
666        .enumerate()
667        .map(|(i, c)| (i as u64 + 1, c.clone()))
668        .collect();
669    for raw in lrat.lines() {
670        let line = raw.trim();
671        if line.is_empty() || line.starts_with('c') {
672            continue;
673        }
674        let mut toks = line.split_whitespace();
675        let Some(id_tok) = toks.next() else { continue };
676        let Ok(id) = id_tok.parse::<u64>() else {
677            return false;
678        };
679        let rest: Vec<&str> = toks.collect();
680        if rest.first() == Some(&"d") {
681            for t in &rest[1..] {
682                if let Ok(d) = t.parse::<u64>() {
683                    if d != 0 {
684                        db.remove(&d);
685                    }
686                }
687            }
688            continue;
689        }
690        // Split the line into the clause (up to the first 0) and the hint chain (up to the next).
691        let mut clause = Vec::new();
692        let mut k = 0usize;
693        while k < rest.len() {
694            let Ok(n) = rest[k].parse::<i64>() else {
695                return false;
696            };
697            k += 1;
698            if n == 0 {
699                break;
700            }
701            clause.push(Lit::new((n.unsigned_abs() - 1) as u32, n > 0));
702        }
703        let mut hints = Vec::new();
704        while k < rest.len() {
705            let Ok(n) = rest[k].parse::<i64>() else {
706                return false;
707            };
708            k += 1;
709            if n == 0 {
710                break;
711            }
712            hints.push(n as u64);
713        }
714        if !verify_rup_step(num_vars, &db, &clause, &hints) {
715            return false;
716        }
717        if clause.is_empty() {
718            return true;
719        }
720        db.insert(id, clause);
721    }
722    false
723}
724
725/// Replay one LRAT step: assume `¬clause`, then for each hint id (in order) the hinted clause must
726/// be unit (propagate its literal) until the last hint conflicts.
727fn verify_rup_step(
728    num_vars: usize,
729    db: &std::collections::HashMap<u64, Vec<Lit>>,
730    clause: &[Lit],
731    hints: &[u64],
732) -> bool {
733    let mut assign: Vec<Option<bool>> = vec![None; num_vars];
734    for &l in clause {
735        if !set_true(&mut assign, l.negated()) {
736            return true; // ¬clause self-contradictory ⇒ trivially valid
737        }
738    }
739    for (i, &h) in hints.iter().enumerate() {
740        let Some(cl) = db.get(&h) else { return false };
741        match clause_state(cl, &assign) {
742            ClauseState::Conflict => return i == hints.len() - 1, // conflict — must be the final hint
743            ClauseState::Unit(u) => {
744                set_true(&mut assign, u);
745            }
746            ClauseState::Quiet => return false, // satisfied, or not unit: never a valid hint
747        }
748    }
749    false
750}
751
752#[cfg(test)]
753#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/proof_emit/tests.rs"]
754mod tests;