Skip to main content

logicaffeine_proof/
satcli.rs

1//! The SAT command-line driver shared by `logos-sat` and `largo sat`.
2//!
3//! One implementation of the SAT Competition main-track interface — read a
4//! DIMACS CNF, run the certified solve, print `s SATISFIABLE`/`s
5//! UNSATISFIABLE` (+ a `v` model for SAT), optionally export an UNSAT
6//! certificate — with the output streams injected so both binaries stay in
7//! lockstep and the driver is directly testable.
8//!
9//! Exit codes follow the competition convention: `10` = SAT, `20` = UNSAT,
10//! `1` = usage/parse/IO error.
11
12use std::io::Write;
13use std::path::Path;
14
15use crate::cdcl::Lit;
16use crate::dimacs;
17use crate::proof::ProofStep;
18use crate::proof_emit;
19use crate::solve::{solve_structured, Answer, Route};
20
21/// Run the solver on `input`, writing the solution to `out` and comments /
22/// diagnostics to `err`. When `proof_path` is given and the verdict is
23/// UNSAT, an exportable certificate is written there. `stats` prints a
24/// `c stats …` line to `err`.
25pub fn run(
26    input: &Path,
27    proof_path: Option<&Path>,
28    stats: bool,
29    out: &mut dyn Write,
30    err: &mut dyn Write,
31) -> u8 {
32    let text = match std::fs::read_to_string(input) {
33        Ok(t) => t,
34        Err(e) => {
35            let _ = writeln!(err, "c error: cannot read {}: {e}", input.display());
36            return 1;
37        }
38    };
39    let cnf = match dimacs::parse(&text) {
40        Ok(c) => c,
41        Err(e) => {
42            let _ = writeln!(err, "c error: malformed DIMACS: {e:?}");
43            return 1;
44        }
45    };
46
47    let t = std::time::Instant::now();
48    let solved = solve_structured(cnf.num_vars, &cnf.clauses);
49    let secs = t.elapsed().as_secs_f64();
50    if stats {
51        let _ = writeln!(
52            err,
53            "c stats vars={} clauses={} time={:.3}s via={:?} conflicts={}",
54            cnf.num_vars,
55            cnf.clauses.len(),
56            secs,
57            solved.via,
58            solved.conflicts
59        );
60    }
61    match solved.answer {
62        Answer::Sat(model) => {
63            let _ = writeln!(out, "s SATISFIABLE");
64            print_model(out, &model, cnf.num_vars);
65            10
66        }
67        Answer::Unsat => {
68            let _ = writeln!(out, "s UNSATISFIABLE");
69            if let Some(path) = proof_path {
70                write_proof(
71                    err,
72                    path,
73                    solved.via,
74                    cnf.num_vars,
75                    &cnf.clauses,
76                    &solved.proof,
77                );
78            }
79            20
80        }
81    }
82}
83
84/// Compile an algebraic route's refutation (GF(2) parity or GF(p) modular) to DRAT resolvent steps,
85/// or `None` if the resolution route blows past its budget (then the verdict stands on the native
86/// algebraic certificate, but no clausal proof is exported — see [`crate::xor_drat`]).
87fn algebraic_drat(via: Route, num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<ProofStep>> {
88    use crate::xor_drat::{emit_modp_drat, emit_xor_drat};
89    let resolvents = match via {
90        Route::Parity => {
91            let eqs = crate::lyapunov::extract_xor(num_vars, clauses);
92            let refutation = match crate::xorsat::solve(&eqs, num_vars) {
93                crate::xorsat::XorOutcome::Unsat(s) => s,
94                crate::xorsat::XorOutcome::Sat(_) => return None,
95            };
96            emit_xor_drat(&eqs, &refutation)?
97        }
98        Route::ModP => emit_modp_drat(num_vars, clauses)?,
99        _ => return None,
100    };
101    Some(resolvents.into_iter().map(ProofStep::Rup).collect())
102}
103
104/// Write the UNSAT certificate: DRAT for a RUP-only proof (the CDCL route), DPR for a proof that
105/// carries PR symmetry steps (the symmetry route), or the algebraic GF(2)/GF(p) bridge compiled to
106/// DRAT (the parity / mod-p routes). The internal solve already verified it.
107fn write_proof(
108    err: &mut dyn Write,
109    path: &Path,
110    via: Route,
111    num_vars: usize,
112    clauses: &[Vec<Lit>],
113    steps: &[ProofStep],
114) {
115    let display = path.display();
116    // Parity / mod-p routes certify internally with a native algebraic witness and carry no clausal
117    // steps; compile their linear-dependency refutation to a strict DRAT proof on demand.
118    if matches!(via, Route::Parity | Route::ModP) {
119        match algebraic_drat(via, num_vars, clauses) {
120            Some(alg) => match proof_emit::emit_drat(num_vars, clauses, &alg) {
121                Ok(drat) => {
122                    if let Err(e) = std::fs::write(path, drat) {
123                        let _ = writeln!(err, "c error: cannot write proof {display}: {e}");
124                    } else {
125                        let _ = writeln!(err, "c proof: DRAT via the {via:?} algebraic bridge — verify with `drat-trim {display}`");
126                    }
127                }
128                Err(e) => {
129                    let _ = writeln!(err, "c warning: algebraic proof not RUP-emittable ({e:?}) — verified internally");
130                }
131            },
132            None => {
133                let _ = writeln!(
134                    err,
135                    "c warning: {via:?} DRAT exceeded the resolution budget (would blow up) — verdict certified internally only"
136                );
137            }
138        }
139        return;
140    }
141    if let Ok(drat) = proof_emit::emit_drat(num_vars, clauses, steps) {
142        if let Err(e) = std::fs::write(path, drat) {
143            let _ = writeln!(err, "c error: cannot write proof {display}: {e}");
144        }
145        return;
146    }
147    if let Ok(dpr) = proof_emit::emit_dpr(num_vars, clauses, steps) {
148        if let Err(e) = std::fs::write(path, dpr) {
149            let _ = writeln!(err, "c error: cannot write proof {display}: {e}");
150        }
151        return;
152    }
153    // Substitution-redundancy proof (the symmetry route): emit the `.sr` format, which `sr2drat`
154    // expands to plain DRAT for `drat-trim` to verify externally.
155    match proof_emit::emit_sr(num_vars, clauses, steps) {
156        Ok(sr) => {
157            if let Err(e) = std::fs::write(path, sr) {
158                let _ = writeln!(err, "c error: cannot write proof {display}: {e}");
159            } else {
160                let _ = writeln!(err, "c proof: substitution-redundancy (.sr) — verify with `sr2drat {display} | drat-trim`");
161            }
162        }
163        Err(e) => {
164            let _ = writeln!(
165                err,
166                "c warning: proof not exportable ({e:?}) — verified internally"
167            );
168        }
169    }
170}
171
172/// Print the model as wrapped `v` lines over variables `1..=num_vars`, terminated by `0`, per the
173/// DIMACS solution convention. Variable `i` (0-based in the model) is literal `i+1`.
174fn print_model(out: &mut dyn Write, model: &[bool], num_vars: usize) {
175    const PER_LINE: usize = 20;
176    let mut line = String::from("v");
177    let mut on_line = 0usize;
178    for v in 0..num_vars {
179        let lit = if model.get(v).copied().unwrap_or(false) {
180            (v + 1) as i64
181        } else {
182            -((v + 1) as i64)
183        };
184        line.push(' ');
185        line.push_str(&lit.to_string());
186        on_line += 1;
187        if on_line == PER_LINE {
188            let _ = writeln!(out, "{line}");
189            line = String::from("v");
190            on_line = 0;
191        }
192    }
193    line.push_str(" 0");
194    let _ = writeln!(out, "{line}");
195}
196
197/// The `logos-sat` process: `logos-sat <input.cnf> [proof.drat]`, with `LOGOS_STATS` for solver
198/// statistics. `src/bin/logos-sat.rs` is exactly this call, and so is the test crate's
199/// `logos-sat-under-test`.
200pub fn main() -> std::process::ExitCode {
201    let args: Vec<String> = std::env::args().collect();
202    let positional: Vec<&String> = args[1..].iter().filter(|a| !a.starts_with('-')).collect();
203
204    let Some(input) = positional.first() else {
205        eprintln!("usage: logos-sat <input.cnf> [proof.drat]");
206        return std::process::ExitCode::from(1);
207    };
208    let proof_path = positional.get(1).map(|p| std::path::Path::new(p.as_str()));
209    let stats = std::env::var("LOGOS_STATS").is_ok();
210
211    let code = run(
212        std::path::Path::new(input.as_str()),
213        proof_path,
214        stats,
215        &mut std::io::stdout(),
216        &mut std::io::stderr(),
217    );
218    std::process::ExitCode::from(code)
219}