GCC Code Coverage Report
Directory: . Exec Total Coverage
File: src/prop/minisat/minisat.cpp Lines: 145 177 81.9 %
Date: 2021-11-07 Branches: 92 278 33.1 %

Line Exec Source
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
15340
MinisatSatSolver::MinisatSatSolver(Env& env, StatisticsRegistry& registry)
34
    : EnvObj(env),
35
      d_minisat(NULL),
36
      d_context(NULL),
37
      d_assumptions(),
38
15340
      d_statistics(registry)
39
15340
{}
40
41
46005
MinisatSatSolver::~MinisatSatSolver()
42
{
43
15335
  d_statistics.deinit();
44
15335
  delete d_minisat;
45
30670
}
46
47
9380566
SatVariable MinisatSatSolver::toSatVariable(Minisat::Var var) {
48
9380566
  if (var == var_Undef) {
49
    return undefSatVariable;
50
  }
51
9380566
  return SatVariable(var);
52
}
53
54
54259753
Minisat::Lit MinisatSatSolver::toMinisatLit(SatLiteral lit) {
55
54259753
  if (lit == undefSatLiteral) {
56
5615383
    return Minisat::lit_Undef;
57
  }
58
48644370
  return Minisat::mkLit(lit.getSatVariable(), lit.isNegated());
59
}
60
61
24285054
SatLiteral MinisatSatSolver::toSatLiteral(Minisat::Lit lit) {
62
24285054
  if (lit == Minisat::lit_Undef) {
63
    return undefSatLiteral;
64
  }
65
66
48570108
  return SatLiteral(SatVariable(Minisat::var(lit)),
67
48570108
                    Minisat::sign(lit));
68
}
69
70
25417663
SatValue MinisatSatSolver::toSatLiteralValue(Minisat::lbool res) {
71
25417663
  if(res == (Minisat::lbool((uint8_t)0))) return SAT_VALUE_TRUE;
72
13302448
  if(res == (Minisat::lbool((uint8_t)2))) return SAT_VALUE_UNKNOWN;
73
3426965
  Assert(res == (Minisat::lbool((uint8_t)1)));
74
3426965
  return SAT_VALUE_FALSE;
75
}
76
77
2076491
Minisat::lbool MinisatSatSolver::toMinisatlbool(SatValue val)
78
{
79
2076491
  if(val == SAT_VALUE_TRUE) return Minisat::lbool((uint8_t)0);
80
2076491
  if(val == SAT_VALUE_UNKNOWN) return Minisat::lbool((uint8_t)2);
81
  Assert(val == SAT_VALUE_FALSE);
82
  return Minisat::lbool((uint8_t)1);
83
}
84
85
/*bool MinisatSatSolver::tobool(SatValue val)
86
{
87
  if(val == SAT_VALUE_TRUE) return true;
88
  Assert(val == SAT_VALUE_FALSE);
89
  return false;
90
  }*/
91
92
9067136
void MinisatSatSolver::toMinisatClause(SatClause& clause,
93
                                           Minisat::vec<Minisat::Lit>& minisat_clause) {
94
30781756
  for (unsigned i = 0; i < clause.size(); ++i) {
95
21714620
    minisat_clause.push(toMinisatLit(clause[i]));
96
  }
97
9067136
  Assert(clause.size() == (unsigned)minisat_clause.size());
98
9067136
}
99
100
void MinisatSatSolver::toSatClause(const Minisat::Clause& clause,
101
                                       SatClause& sat_clause) {
102
  for (int i = 0; i < clause.size(); ++i) {
103
    sat_clause.push_back(toSatLiteral(clause[i]));
104
  }
105
  Assert((unsigned)clause.size() == sat_clause.size());
106
}
107
108
15340
void MinisatSatSolver::initialize(context::Context* context,
109
                                  TheoryProxy* theoryProxy,
110
                                  context::UserContext* userContext,
111
                                  ProofNodeManager* pnm)
112
{
113
15340
  d_context = context;
114
115
15340
  if (options().decision.decisionMode != options::DecisionMode::INTERNAL)
116
  {
117
12757
    verbose(1) << "minisat: Incremental solving is forced on (to avoid "
118
                  "variable elimination)"
119
12757
               << " unless using internal decision strategy." << std::endl;
120
  }
121
122
  // Create the solver
123
15340
  d_minisat =
124
      new Minisat::SimpSolver(theoryProxy,
125
                              d_context,
126
                              userContext,
127
                              pnm,
128
15340
                              options().base.incrementalSolving
129
15340
                                  || options().decision.decisionMode
130
15340
                                         != options::DecisionMode::INTERNAL);
131
132
15340
  d_statistics.init(d_minisat);
133
15340
}
134
135
// Like initialize() above, but called just before each search when in
136
// incremental mode
137
20557
void MinisatSatSolver::setupOptions() {
138
  // Copy options from cvc5 options structure into minisat, as appropriate
139
140
  // Set up the verbosity
141
20557
  d_minisat->verbosity = (options().base.verbosity > 0) ? 1 : -1;
142
143
  // Set up the random decision parameters
144
20557
  d_minisat->random_var_freq = options().prop.satRandomFreq;
145
  // If 0, we use whatever we like (here, the Minisat default seed)
146
20557
  if (options().prop.satRandomSeed != 0)
147
  {
148
2
    d_minisat->random_seed = double(options().prop.satRandomSeed);
149
  }
150
151
  // Give access to all possible options in the sat solver
152
20557
  d_minisat->var_decay = options().prop.satVarDecay;
153
20557
  d_minisat->clause_decay = options().prop.satClauseDecay;
154
20557
  d_minisat->restart_first = options().prop.satRestartFirst;
155
20557
  d_minisat->restart_inc = options().prop.satRestartInc;
156
20557
}
157
158
3718417
ClauseId MinisatSatSolver::addClause(SatClause& clause, bool removable) {
159
7436834
  Minisat::vec<Minisat::Lit> minisat_clause;
160
3718417
  toMinisatClause(clause, minisat_clause);
161
3718417
  ClauseId clause_id = ClauseIdError;
162
  // FIXME: This relies on the invariant that when ok() is false
163
  // the SAT solver does not add the clause (which is what Minisat currently does)
164
3718417
  if (!ok()) {
165
6854
    return ClauseIdUndef;
166
  }
167
3711563
  d_minisat->addClause(minisat_clause, removable, clause_id);
168
  // FIXME: to be deleted when we kill old proof code for unsat cores
169
3711563
  Assert(!options().smt.unsatCores || options().smt.produceProofs
170
         || clause_id != ClauseIdError);
171
3711563
  return clause_id;
172
}
173
174
1324882
SatVariable MinisatSatSolver::newVar(bool isTheoryAtom, bool preRegister, bool canErase) {
175
1324882
  return d_minisat->newVar(true, true, isTheoryAtom, preRegister, canErase);
176
}
177
178
SatValue MinisatSatSolver::solve(unsigned long& resource) {
179
  Trace("limit") << "SatSolver::solve(): have limit of " << resource << " conflicts" << std::endl;
180
  setupOptions();
181
  if(resource == 0) {
182
    d_minisat->budgetOff();
183
  } else {
184
    d_minisat->setConfBudget(resource);
185
  }
186
  Minisat::vec<Minisat::Lit> empty;
187
  unsigned long conflictsBefore = d_minisat->conflicts + d_minisat->resources_consumed;
188
  SatValue result = toSatLiteralValue(d_minisat->solveLimited(empty));
189
  d_minisat->clearInterrupt();
190
  resource = d_minisat->conflicts + d_minisat->resources_consumed - conflictsBefore;
191
  Trace("limit") << "SatSolver::solve(): it took " << resource << " conflicts" << std::endl;
192
  return result;
193
}
194
195
16842
SatValue MinisatSatSolver::solve() {
196
16842
  setupOptions();
197
16842
  d_minisat->budgetOff();
198
16842
  SatValue result = toSatLiteralValue(d_minisat->solve());
199
16819
  d_minisat->clearInterrupt();
200
16819
  return result;
201
}
202
203
3715
SatValue MinisatSatSolver::solve(const std::vector<SatLiteral>& assumptions)
204
{
205
3715
  setupOptions();
206
3715
  d_minisat->budgetOff();
207
208
3715
  d_assumptions.clear();
209
7430
  Minisat::vec<Minisat::Lit> assumps;
210
211
53960
  for (const SatLiteral& lit : assumptions)
212
  {
213
50245
    Minisat::Lit mlit = toMinisatLit(lit);
214
50245
    assumps.push(mlit);
215
50245
    d_assumptions.emplace(lit);
216
  }
217
218
3715
  SatValue result = toSatLiteralValue(d_minisat->solve(assumps));
219
3715
  d_minisat->clearInterrupt();
220
7430
  return result;
221
}
222
223
1410
void MinisatSatSolver::getUnsatAssumptions(
224
    std::vector<SatLiteral>& unsat_assumptions)
225
{
226
8363
  for (size_t i = 0, size = d_minisat->d_conflict.size(); i < size; ++i)
227
  {
228
6953
    Minisat::Lit mlit = d_minisat->d_conflict[i];
229
6953
    SatLiteral lit = ~toSatLiteral(mlit);
230
6953
    if (d_assumptions.find(lit) != d_assumptions.end())
231
    {
232
6953
      unsat_assumptions.push_back(lit);
233
    }
234
  }
235
1410
}
236
237
3718417
bool MinisatSatSolver::ok() const {
238
3718417
  return d_minisat->okay();
239
}
240
241
void MinisatSatSolver::interrupt() {
242
  d_minisat->interrupt();
243
}
244
245
25397129
SatValue MinisatSatSolver::value(SatLiteral l) {
246
25397129
  return toSatLiteralValue(d_minisat->value(toMinisatLit(l)));
247
}
248
249
SatValue MinisatSatSolver::modelValue(SatLiteral l){
250
  return toSatLiteralValue(d_minisat->modelValue(toMinisatLit(l)));
251
}
252
253
bool MinisatSatSolver::properExplanation(SatLiteral lit, SatLiteral expl) const {
254
  return true;
255
}
256
257
81161
void MinisatSatSolver::requirePhase(SatLiteral lit) {
258
81161
  Assert(!d_minisat->rnd_pol);
259
81161
  Debug("minisat") << "requirePhase(" << lit << ")" << " " <<  lit.getSatVariable() << " " << lit.isNegated() << std::endl;
260
81161
  SatVariable v = lit.getSatVariable();
261
81161
  d_minisat->freezePolarity(v, lit.isNegated());
262
81161
}
263
264
171751
bool MinisatSatSolver::isDecision(SatVariable decn) const {
265
171751
  return d_minisat->isDecision( decn );
266
}
267
268
8
int32_t MinisatSatSolver::getDecisionLevel(SatVariable v) const
269
{
270
8
  return d_minisat->level(v) + d_minisat->user_level(v);
271
}
272
273
8
int32_t MinisatSatSolver::getIntroLevel(SatVariable v) const
274
{
275
8
  return d_minisat->intro_level(v);
276
}
277
278
10762
SatProofManager* MinisatSatSolver::getProofManager()
279
{
280
10762
  return d_minisat->getProofManager();
281
}
282
283
10064
std::shared_ptr<ProofNode> MinisatSatSolver::getProof()
284
{
285
10064
  return d_minisat->getProof();
286
}
287
288
/** Incremental interface */
289
290
24392
unsigned MinisatSatSolver::getAssertionLevel() const {
291
24392
  return d_minisat->getAssertionLevel();
292
}
293
294
4937
void MinisatSatSolver::push() {
295
4937
  d_minisat->push();
296
4937
}
297
298
4937
void MinisatSatSolver::pop() {
299
4937
  d_minisat->pop();
300
4937
}
301
302
20537
void MinisatSatSolver::resetTrail() { d_minisat->resetTrail(); }
303
304
/// Statistics for MinisatSatSolver
305
306
15340
MinisatSatSolver::Statistics::Statistics(StatisticsRegistry& registry)
307
    : d_statStarts(registry.registerReference<int64_t>("sat::starts")),
308
      d_statDecisions(registry.registerReference<int64_t>("sat::decisions")),
309
      d_statRndDecisions(
310
          registry.registerReference<int64_t>("sat::rnd_decisions")),
311
      d_statPropagations(
312
          registry.registerReference<int64_t>("sat::propagations")),
313
      d_statConflicts(registry.registerReference<int64_t>("sat::conflicts")),
314
      d_statClausesLiterals(
315
          registry.registerReference<int64_t>("sat::clauses_literals")),
316
      d_statLearntsLiterals(
317
          registry.registerReference<int64_t>("sat::learnts_literals")),
318
      d_statMaxLiterals(
319
          registry.registerReference<int64_t>("sat::max_literals")),
320
      d_statTotLiterals(
321
15340
          registry.registerReference<int64_t>("sat::tot_literals"))
322
{
323
15340
}
324
325
15340
void MinisatSatSolver::Statistics::init(Minisat::SimpSolver* minisat){
326
15340
  d_statStarts.set(minisat->starts);
327
15340
  d_statDecisions.set(minisat->decisions);
328
15340
  d_statRndDecisions.set(minisat->rnd_decisions);
329
15340
  d_statPropagations.set(minisat->propagations);
330
15340
  d_statConflicts.set(minisat->conflicts);
331
15340
  d_statClausesLiterals.set(minisat->clauses_literals);
332
15340
  d_statLearntsLiterals.set(minisat->learnts_literals);
333
15340
  d_statMaxLiterals.set(minisat->max_literals);
334
15340
  d_statTotLiterals.set(minisat->tot_literals);
335
15340
}
336
15335
void MinisatSatSolver::Statistics::deinit()
337
{
338
15335
  d_statStarts.reset();
339
15335
  d_statDecisions.reset();
340
15335
  d_statRndDecisions.reset();
341
15335
  d_statPropagations.reset();
342
15335
  d_statConflicts.reset();
343
15335
  d_statClausesLiterals.reset();
344
15335
  d_statLearntsLiterals.reset();
345
15335
  d_statMaxLiterals.reset();
346
15335
  d_statTotLiterals.reset();
347
15335
}
348
349
}  // namespace prop
350
}  // namespace cvc5
351
352
namespace cvc5 {
353
template <>
354
28697
prop::SatLiteral toSatLiteral<cvc5::Minisat::Solver>(Minisat::Solver::TLit lit)
355
{
356
28697
  return prop::MinisatSatSolver::toSatLiteral(lit);
357
}
358
359
template <>
360
void toSatClause<cvc5::Minisat::Solver>(
361
    const cvc5::Minisat::Solver::TClause& minisat_cl, prop::SatClause& sat_cl)
362
{
363
  prop::MinisatSatSolver::toSatClause(minisat_cl, sat_cl);
364
}
365
366
31137
}  // namespace cvc5