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;