1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Dejan Jovanovic, Liana Hadarean, Morgan Deters |
4 |
|
* |
5 |
|
* This file is part of the cvc5 project. |
6 |
|
* |
7 |
|
* Copyright (c) 2009-2021 by the authors listed in the file AUTHORS |
8 |
|
* in the top-level source directory and their institutional affiliations. |
9 |
|
* All rights reserved. See the file COPYING in the top-level source |
10 |
|
* directory for licensing information. |
11 |
|
* **************************************************************************** |
12 |
|
* |
13 |
|
* SAT Solver. |
14 |
|
* |
15 |
|
* Implementation of the minisat interface for cvc5. |
16 |
|
*/ |
17 |
|
|
18 |
|
#include "prop/minisat/minisat.h" |
19 |
|
|
20 |
|
#include "options/base_options.h" |
21 |
|
#include "options/decision_options.h" |
22 |
|
#include "options/prop_options.h" |
23 |
|
#include "options/smt_options.h" |
24 |
|
#include "proof/clause_id.h" |
25 |
|
#include "prop/minisat/simp/SimpSolver.h" |
26 |
|
#include "util/statistics_stats.h" |
27 |
|
|
28 |
|
namespace cvc5 { |
29 |
|
namespace prop { |
30 |
|
|
31 |
|
//// DPllMinisatSatSolver |
32 |
|
|
33 |
10007 |
MinisatSatSolver::MinisatSatSolver(StatisticsRegistry& registry) |
34 |
10007 |
: d_minisat(NULL), d_context(NULL), d_assumptions(), d_statistics(registry) |
35 |
10007 |
{} |
36 |
|
|
37 |
30012 |
MinisatSatSolver::~MinisatSatSolver() |
38 |
|
{ |
39 |
10004 |
d_statistics.deinit(); |
40 |
10004 |
delete d_minisat; |
41 |
20008 |
} |
42 |
|
|
43 |
6667057 |
SatVariable MinisatSatSolver::toSatVariable(Minisat::Var var) { |
44 |
6667057 |
if (var == var_Undef) { |
45 |
|
return undefSatVariable; |
46 |
|
} |
47 |
6667057 |
return SatVariable(var); |
48 |
|
} |
49 |
|
|
50 |
45683558 |
Minisat::Lit MinisatSatSolver::toMinisatLit(SatLiteral lit) { |
51 |
45683558 |
if (lit == undefSatLiteral) { |
52 |
4291255 |
return Minisat::lit_Undef; |
53 |
|
} |
54 |
41392303 |
return Minisat::mkLit(lit.getSatVariable(), lit.isNegated()); |
55 |
|
} |
56 |
|
|
57 |
20742726 |
SatLiteral MinisatSatSolver::toSatLiteral(Minisat::Lit lit) { |
58 |
20742726 |
if (lit == Minisat::lit_Undef) { |
59 |
|
return undefSatLiteral; |
60 |
|
} |
61 |
|
|
62 |
41485452 |
return SatLiteral(SatVariable(Minisat::var(lit)), |
63 |
41485452 |
Minisat::sign(lit)); |
64 |
|
} |
65 |
|
|
66 |
21036324 |
SatValue MinisatSatSolver::toSatLiteralValue(Minisat::lbool res) { |
67 |
21036324 |
if(res == (Minisat::lbool((uint8_t)0))) return SAT_VALUE_TRUE; |
68 |
11013773 |
if(res == (Minisat::lbool((uint8_t)2))) return SAT_VALUE_UNKNOWN; |
69 |
3014546 |
Assert(res == (Minisat::lbool((uint8_t)1))); |
70 |
3014546 |
return SAT_VALUE_FALSE; |
71 |
|
} |
72 |
|
|
73 |
1486264 |
Minisat::lbool MinisatSatSolver::toMinisatlbool(SatValue val) |
74 |
|
{ |
75 |
1486264 |
if(val == SAT_VALUE_TRUE) return Minisat::lbool((uint8_t)0); |
76 |
1486264 |
if(val == SAT_VALUE_UNKNOWN) return Minisat::lbool((uint8_t)2); |
77 |
|
Assert(val == SAT_VALUE_FALSE); |
78 |
|
return Minisat::lbool((uint8_t)1); |
79 |
|
} |
80 |
|
|
81 |
|
/*bool MinisatSatSolver::tobool(SatValue val) |
82 |
|
{ |
83 |
|
if(val == SAT_VALUE_TRUE) return true; |
84 |
|
Assert(val == SAT_VALUE_FALSE); |
85 |
|
return false; |
86 |
|
}*/ |
87 |
|
|
88 |
8015117 |
void MinisatSatSolver::toMinisatClause(SatClause& clause, |
89 |
|
Minisat::vec<Minisat::Lit>& minisat_clause) { |
90 |
26974049 |
for (unsigned i = 0; i < clause.size(); ++i) { |
91 |
18958932 |
minisat_clause.push(toMinisatLit(clause[i])); |
92 |
|
} |
93 |
8015117 |
Assert(clause.size() == (unsigned)minisat_clause.size()); |
94 |
8015117 |
} |
95 |
|
|
96 |
|
void MinisatSatSolver::toSatClause(const Minisat::Clause& clause, |
97 |
|
SatClause& sat_clause) { |
98 |
|
for (int i = 0; i < clause.size(); ++i) { |
99 |
|
sat_clause.push_back(toSatLiteral(clause[i])); |
100 |
|
} |
101 |
|
Assert((unsigned)clause.size() == sat_clause.size()); |
102 |
|
} |
103 |
|
|
104 |
10007 |
void MinisatSatSolver::initialize(context::Context* context, |
105 |
|
TheoryProxy* theoryProxy, |
106 |
|
context::UserContext* userContext, |
107 |
|
ProofNodeManager* pnm) |
108 |
|
{ |
109 |
10007 |
d_context = context; |
110 |
|
|
111 |
10007 |
if (options::decisionMode() != options::DecisionMode::INTERNAL) |
112 |
|
{ |
113 |
7755 |
Notice() << "minisat: Incremental solving is forced on (to avoid variable elimination)" |
114 |
|
<< " unless using internal decision strategy." << std::endl; |
115 |
|
} |
116 |
|
|
117 |
|
// Create the solver |
118 |
10007 |
d_minisat = new Minisat::SimpSolver( |
119 |
|
theoryProxy, |
120 |
|
d_context, |
121 |
|
userContext, |
122 |
|
pnm, |
123 |
10007 |
options::incrementalSolving() |
124 |
10007 |
|| options::decisionMode() != options::DecisionMode::INTERNAL); |
125 |
|
|
126 |
10007 |
d_statistics.init(d_minisat); |
127 |
10007 |
} |
128 |
|
|
129 |
|
// Like initialize() above, but called just before each search when in |
130 |
|
// incremental mode |
131 |
15259 |
void MinisatSatSolver::setupOptions() { |
132 |
|
// Copy options from cvc5 options structure into minisat, as appropriate |
133 |
|
|
134 |
|
// Set up the verbosity |
135 |
15259 |
d_minisat->verbosity = (options::verbosity() > 0) ? 1 : -1; |
136 |
|
|
137 |
|
// Set up the random decision parameters |
138 |
15259 |
d_minisat->random_var_freq = options::satRandomFreq(); |
139 |
|
// If 0, we use whatever we like (here, the Minisat default seed) |
140 |
15259 |
if(options::satRandomSeed() != 0) { |
141 |
2 |
d_minisat->random_seed = double(options::satRandomSeed()); |
142 |
|
} |
143 |
|
|
144 |
|
// Give access to all possible options in the sat solver |
145 |
15259 |
d_minisat->var_decay = options::satVarDecay(); |
146 |
15259 |
d_minisat->clause_decay = options::satClauseDecay(); |
147 |
15259 |
d_minisat->restart_first = options::satRestartFirst(); |
148 |
15259 |
d_minisat->restart_inc = options::satRestartInc(); |
149 |
15259 |
} |
150 |
|
|
151 |
3704354 |
ClauseId MinisatSatSolver::addClause(SatClause& clause, bool removable) { |
152 |
7408708 |
Minisat::vec<Minisat::Lit> minisat_clause; |
153 |
3704354 |
toMinisatClause(clause, minisat_clause); |
154 |
3704354 |
ClauseId clause_id = ClauseIdError; |
155 |
|
// FIXME: This relies on the invariant that when ok() is false |
156 |
|
// the SAT solver does not add the clause (which is what Minisat currently does) |
157 |
3704354 |
if (!ok()) { |
158 |
6319 |
return ClauseIdUndef; |
159 |
|
} |
160 |
3698035 |
d_minisat->addClause(minisat_clause, removable, clause_id); |
161 |
|
// FIXME: to be deleted when we kill old proof code for unsat cores |
162 |
3698035 |
Assert(!options::unsatCores() || options::produceProofs() |
163 |
|
|| clause_id != ClauseIdError); |
164 |
3698035 |
return clause_id; |
165 |
|
} |
166 |
|
|
167 |
1273464 |
SatVariable MinisatSatSolver::newVar(bool isTheoryAtom, bool preRegister, bool canErase) { |
168 |
1273464 |
return d_minisat->newVar(true, true, isTheoryAtom, preRegister, canErase); |
169 |
|
} |
170 |
|
|
171 |
|
SatValue MinisatSatSolver::solve(unsigned long& resource) { |
172 |
|
Trace("limit") << "SatSolver::solve(): have limit of " << resource << " conflicts" << std::endl; |
173 |
|
setupOptions(); |
174 |
|
if(resource == 0) { |
175 |
|
d_minisat->budgetOff(); |
176 |
|
} else { |
177 |
|
d_minisat->setConfBudget(resource); |
178 |
|
} |
179 |
|
Minisat::vec<Minisat::Lit> empty; |
180 |
|
unsigned long conflictsBefore = d_minisat->conflicts + d_minisat->resources_consumed; |
181 |
|
SatValue result = toSatLiteralValue(d_minisat->solveLimited(empty)); |
182 |
|
d_minisat->clearInterrupt(); |
183 |
|
resource = d_minisat->conflicts + d_minisat->resources_consumed - conflictsBefore; |
184 |
|
Trace("limit") << "SatSolver::solve(): it took " << resource << " conflicts" << std::endl; |
185 |
|
return result; |
186 |
|
} |
187 |
|
|
188 |
11604 |
SatValue MinisatSatSolver::solve() { |
189 |
11604 |
setupOptions(); |
190 |
11604 |
d_minisat->budgetOff(); |
191 |
11604 |
SatValue result = toSatLiteralValue(d_minisat->solve()); |
192 |
11588 |
d_minisat->clearInterrupt(); |
193 |
11588 |
return result; |
194 |
|
} |
195 |
|
|
196 |
3655 |
SatValue MinisatSatSolver::solve(const std::vector<SatLiteral>& assumptions) |
197 |
|
{ |
198 |
3655 |
setupOptions(); |
199 |
3655 |
d_minisat->budgetOff(); |
200 |
|
|
201 |
3655 |
d_assumptions.clear(); |
202 |
7310 |
Minisat::vec<Minisat::Lit> assumps; |
203 |
|
|
204 |
52131 |
for (const SatLiteral& lit : assumptions) |
205 |
|
{ |
206 |
48476 |
Minisat::Lit mlit = toMinisatLit(lit); |
207 |
48476 |
assumps.push(mlit); |
208 |
48476 |
d_assumptions.emplace(lit); |
209 |
|
} |
210 |
|
|
211 |
3655 |
SatValue result = toSatLiteralValue(d_minisat->solve(assumps)); |
212 |
3655 |
d_minisat->clearInterrupt(); |
213 |
7310 |
return result; |
214 |
|
} |
215 |
|
|
216 |
1378 |
void MinisatSatSolver::getUnsatAssumptions( |
217 |
|
std::vector<SatLiteral>& unsat_assumptions) |
218 |
|
{ |
219 |
8125 |
for (size_t i = 0, size = d_minisat->d_conflict.size(); i < size; ++i) |
220 |
|
{ |
221 |
6747 |
Minisat::Lit mlit = d_minisat->d_conflict[i]; |
222 |
6747 |
SatLiteral lit = ~toSatLiteral(mlit); |
223 |
6747 |
if (d_assumptions.find(lit) != d_assumptions.end()) |
224 |
|
{ |
225 |
6747 |
unsat_assumptions.push_back(lit); |
226 |
|
} |
227 |
|
} |
228 |
1378 |
} |
229 |
|
|
230 |
3704354 |
bool MinisatSatSolver::ok() const { |
231 |
3704354 |
return d_minisat->okay(); |
232 |
|
} |
233 |
|
|
234 |
|
void MinisatSatSolver::interrupt() { |
235 |
|
d_minisat->interrupt(); |
236 |
|
} |
237 |
|
|
238 |
21021081 |
SatValue MinisatSatSolver::value(SatLiteral l) { |
239 |
21021081 |
return toSatLiteralValue(d_minisat->value(toMinisatLit(l))); |
240 |
|
} |
241 |
|
|
242 |
|
SatValue MinisatSatSolver::modelValue(SatLiteral l){ |
243 |
|
return toSatLiteralValue(d_minisat->modelValue(toMinisatLit(l))); |
244 |
|
} |
245 |
|
|
246 |
|
bool MinisatSatSolver::properExplanation(SatLiteral lit, SatLiteral expl) const { |
247 |
|
return true; |
248 |
|
} |
249 |
|
|
250 |
69401 |
void MinisatSatSolver::requirePhase(SatLiteral lit) { |
251 |
69401 |
Assert(!d_minisat->rnd_pol); |
252 |
69401 |
Debug("minisat") << "requirePhase(" << lit << ")" << " " << lit.getSatVariable() << " " << lit.isNegated() << std::endl; |
253 |
69401 |
SatVariable v = lit.getSatVariable(); |
254 |
69401 |
d_minisat->freezePolarity(v, lit.isNegated()); |
255 |
69401 |
} |
256 |
|
|
257 |
171757 |
bool MinisatSatSolver::isDecision(SatVariable decn) const { |
258 |
171757 |
return d_minisat->isDecision( decn ); |
259 |
|
} |
260 |
|
|
261 |
16 |
int32_t MinisatSatSolver::getDecisionLevel(SatVariable v) const |
262 |
|
{ |
263 |
16 |
return d_minisat->level(v) + d_minisat->user_level(v); |
264 |
|
} |
265 |
|
|
266 |
8 |
int32_t MinisatSatSolver::getIntroLevel(SatVariable v) const |
267 |
|
{ |
268 |
8 |
return d_minisat->intro_level(v); |
269 |
|
} |
270 |
|
|
271 |
2504 |
SatProofManager* MinisatSatSolver::getProofManager() |
272 |
|
{ |
273 |
2504 |
return d_minisat->getProofManager(); |
274 |
|
} |
275 |
|
|
276 |
2829 |
std::shared_ptr<ProofNode> MinisatSatSolver::getProof() |
277 |
|
{ |
278 |
2829 |
return d_minisat->getProof(); |
279 |
|
} |
280 |
|
|
281 |
|
/** Incremental interface */ |
282 |
|
|
283 |
19006 |
unsigned MinisatSatSolver::getAssertionLevel() const { |
284 |
19006 |
return d_minisat->getAssertionLevel(); |
285 |
|
} |
286 |
|
|
287 |
4869 |
void MinisatSatSolver::push() { |
288 |
4869 |
d_minisat->push(); |
289 |
4869 |
} |
290 |
|
|
291 |
4869 |
void MinisatSatSolver::pop() { |
292 |
4869 |
d_minisat->pop(); |
293 |
4869 |
} |
294 |
|
|
295 |
15246 |
void MinisatSatSolver::resetTrail() { d_minisat->resetTrail(); } |
296 |
|
|
297 |
|
/// Statistics for MinisatSatSolver |
298 |
|
|
299 |
10007 |
MinisatSatSolver::Statistics::Statistics(StatisticsRegistry& registry) |
300 |
|
: d_statStarts(registry.registerReference<int64_t>("sat::starts")), |
301 |
|
d_statDecisions(registry.registerReference<int64_t>("sat::decisions")), |
302 |
|
d_statRndDecisions( |
303 |
|
registry.registerReference<int64_t>("sat::rnd_decisions")), |
304 |
|
d_statPropagations( |
305 |
|
registry.registerReference<int64_t>("sat::propagations")), |
306 |
|
d_statConflicts(registry.registerReference<int64_t>("sat::conflicts")), |
307 |
|
d_statClausesLiterals( |
308 |
|
registry.registerReference<int64_t>("sat::clauses_literals")), |
309 |
|
d_statLearntsLiterals( |
310 |
|
registry.registerReference<int64_t>("sat::learnts_literals")), |
311 |
|
d_statMaxLiterals( |
312 |
|
registry.registerReference<int64_t>("sat::max_literals")), |
313 |
|
d_statTotLiterals( |
314 |
10007 |
registry.registerReference<int64_t>("sat::tot_literals")) |
315 |
|
{ |
316 |
10007 |
} |
317 |
|
|
318 |
10007 |
void MinisatSatSolver::Statistics::init(Minisat::SimpSolver* minisat){ |
319 |
10007 |
d_statStarts.set(minisat->starts); |
320 |
10007 |
d_statDecisions.set(minisat->decisions); |
321 |
10007 |
d_statRndDecisions.set(minisat->rnd_decisions); |
322 |
10007 |
d_statPropagations.set(minisat->propagations); |
323 |
10007 |
d_statConflicts.set(minisat->conflicts); |
324 |
10007 |
d_statClausesLiterals.set(minisat->clauses_literals); |
325 |
10007 |
d_statLearntsLiterals.set(minisat->learnts_literals); |
326 |
10007 |
d_statMaxLiterals.set(minisat->max_literals); |
327 |
10007 |
d_statTotLiterals.set(minisat->tot_literals); |
328 |
10007 |
} |
329 |
10004 |
void MinisatSatSolver::Statistics::deinit() |
330 |
|
{ |
331 |
10004 |
d_statStarts.reset(); |
332 |
10004 |
d_statDecisions.reset(); |
333 |
10004 |
d_statRndDecisions.reset(); |
334 |
10004 |
d_statPropagations.reset(); |
335 |
10004 |
d_statConflicts.reset(); |
336 |
10004 |
d_statClausesLiterals.reset(); |
337 |
10004 |
d_statLearntsLiterals.reset(); |
338 |
10004 |
d_statMaxLiterals.reset(); |
339 |
10004 |
d_statTotLiterals.reset(); |
340 |
10004 |
} |
341 |
|
|
342 |
|
} // namespace prop |
343 |
|
} // namespace cvc5 |
344 |
|
|
345 |
|
namespace cvc5 { |
346 |
|
template <> |
347 |
33321 |
prop::SatLiteral toSatLiteral<cvc5::Minisat::Solver>(Minisat::Solver::TLit lit) |
348 |
|
{ |
349 |
33321 |
return prop::MinisatSatSolver::toSatLiteral(lit); |
350 |
|
} |
351 |
|
|
352 |
|
template <> |
353 |
|
void toSatClause<cvc5::Minisat::Solver>( |
354 |
|
const cvc5::Minisat::Solver::TClause& minisat_cl, prop::SatClause& sat_cl) |
355 |
|
{ |
356 |
|
prop::MinisatSatSolver::toSatClause(minisat_cl, sat_cl); |
357 |
|
} |
358 |
|
|
359 |
29574 |
} // namespace cvc5 |