GCC Code Coverage Report
Directory: . Exec Total Coverage
File: src/prop/minisat/minisat.cpp Lines: 143 176 81.3 %
Date: 2021-08-01 Branches: 101 314 32.2 %

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
9905
MinisatSatSolver::MinisatSatSolver(StatisticsRegistry& registry)
34
9905
    : d_minisat(NULL), d_context(NULL), d_assumptions(), d_statistics(registry)
35
9905
{}
36
37
29715
MinisatSatSolver::~MinisatSatSolver()
38
{
39
9905
  d_statistics.deinit();
40
9905
  delete d_minisat;
41
19810
}
42
43
6502693
SatVariable MinisatSatSolver::toSatVariable(Minisat::Var var) {
44
6502693
  if (var == var_Undef) {
45
    return undefSatVariable;
46
  }
47
6502693
  return SatVariable(var);
48
}
49
50
42989089
Minisat::Lit MinisatSatSolver::toMinisatLit(SatLiteral lit) {
51
42989089
  if (lit == undefSatLiteral) {
52
4172768
    return Minisat::lit_Undef;
53
  }
54
38816321
  return Minisat::mkLit(lit.getSatVariable(), lit.isNegated());
55
}
56
57
24315572
SatLiteral MinisatSatSolver::toSatLiteral(Minisat::Lit lit) {
58
24315572
  if (lit == Minisat::lit_Undef) {
59
    return undefSatLiteral;
60
  }
61
62
48631144
  return SatLiteral(SatVariable(Minisat::var(lit)),
63
48631144
                    Minisat::sign(lit));
64
}
65
66
18878707
SatValue MinisatSatSolver::toSatLiteralValue(Minisat::lbool res) {
67
18878707
  if(res == (Minisat::lbool((uint8_t)0))) return SAT_VALUE_TRUE;
68
10042064
  if(res == (Minisat::lbool((uint8_t)2))) return SAT_VALUE_UNKNOWN;
69
2840532
  Assert(res == (Minisat::lbool((uint8_t)1)));
70
2840532
  return SAT_VALUE_FALSE;
71
}
72
73
1428740
Minisat::lbool MinisatSatSolver::toMinisatlbool(SatValue val)
74
{
75
1428740
  if(val == SAT_VALUE_TRUE) return Minisat::lbool((uint8_t)0);
76
1428740
  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
8056714
void MinisatSatSolver::toMinisatClause(SatClause& clause,
89
                                           Minisat::vec<Minisat::Lit>& minisat_clause) {
90
26535423
  for (unsigned i = 0; i < clause.size(); ++i) {
91
18478709
    minisat_clause.push(toMinisatLit(clause[i]));
92
  }
93
8056714
  Assert(clause.size() == (unsigned)minisat_clause.size());
94
8056714
}
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
9905
void MinisatSatSolver::initialize(context::Context* context,
105
                                  TheoryProxy* theoryProxy,
106
                                  context::UserContext* userContext,
107
                                  ProofNodeManager* pnm)
108
{
109
9905
  d_context = context;
110
111
9905
  if (options::decisionMode() != options::DecisionMode::INTERNAL)
112
  {
113
7727
    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
9905
  d_minisat = new Minisat::SimpSolver(
119
      theoryProxy,
120
      d_context,
121
      userContext,
122
      pnm,
123
9905
      options::incrementalSolving()
124
9905
          || options::decisionMode() != options::DecisionMode::INTERNAL);
125
126
9905
  d_statistics.init(d_minisat);
127
9905
}
128
129
// Like initialize() above, but called just before each search when in
130
// incremental mode
131
15186
void MinisatSatSolver::setupOptions() {
132
  // Copy options from cvc5 options structure into minisat, as appropriate
133
134
  // Set up the verbosity
135
30372
  d_minisat->verbosity = (options::verbosity() > 0) ? 1 : -1;
136
137
  // Set up the random decision parameters
138
30372
  d_minisat->random_var_freq = options::satRandomFreq();
139
  // If 0, we use whatever we like (here, the Minisat default seed)
140
30374
  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
30372
  d_minisat->var_decay = options::satVarDecay();
146
30372
  d_minisat->clause_decay = options::satClauseDecay();
147
30372
  d_minisat->restart_first = options::satRestartFirst();
148
30372
  d_minisat->restart_inc = options::satRestartInc();
149
15186
}
150
151
3923374
ClauseId MinisatSatSolver::addClause(SatClause& clause, bool removable) {
152
7846748
  Minisat::vec<Minisat::Lit> minisat_clause;
153
3923374
  toMinisatClause(clause, minisat_clause);
154
3923374
  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
3923374
  if (!ok()) {
158
6310
    return ClauseIdUndef;
159
  }
160
3917064
  d_minisat->addClause(minisat_clause, removable, clause_id);
161
  // FIXME: to be deleted when we kill old proof code for unsat cores
162
3917064
  Assert(!options::unsatCores() || options::produceProofs()
163
         || clause_id != ClauseIdError);
164
3917064
  return clause_id;
165
}
166
167
1296975
SatVariable MinisatSatSolver::newVar(bool isTheoryAtom, bool preRegister, bool canErase) {
168
1296975
  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
11561
SatValue MinisatSatSolver::solve() {
189
11561
  setupOptions();
190
11561
  d_minisat->budgetOff();
191
11561
  SatValue result = toSatLiteralValue(d_minisat->solve());
192
11545
  d_minisat->clearInterrupt();
193
11545
  return result;
194
}
195
196
3625
SatValue MinisatSatSolver::solve(const std::vector<SatLiteral>& assumptions)
197
{
198
3625
  setupOptions();
199
3625
  d_minisat->budgetOff();
200
201
3625
  d_assumptions.clear();
202
7250
  Minisat::vec<Minisat::Lit> assumps;
203
204
51919
  for (const SatLiteral& lit : assumptions)
205
  {
206
48294
    Minisat::Lit mlit = toMinisatLit(lit);
207
48294
    assumps.push(mlit);
208
48294
    d_assumptions.emplace(lit);
209
  }
210
211
3625
  SatValue result = toSatLiteralValue(d_minisat->solve(assumps));
212
3625
  d_minisat->clearInterrupt();
213
7250
  return result;
214
}
215
216
1368
void MinisatSatSolver::getUnsatAssumptions(
217
    std::vector<SatLiteral>& unsat_assumptions)
218
{
219
8132
  for (size_t i = 0, size = d_minisat->d_conflict.size(); i < size; ++i)
220
  {
221
6764
    Minisat::Lit mlit = d_minisat->d_conflict[i];
222
6764
    SatLiteral lit = ~toSatLiteral(mlit);
223
6764
    if (d_assumptions.find(lit) != d_assumptions.end())
224
    {
225
6764
      unsat_assumptions.push_back(lit);
226
    }
227
  }
228
1368
}
229
230
3923374
bool MinisatSatSolver::ok() const {
231
3923374
  return d_minisat->okay();
232
}
233
234
void MinisatSatSolver::interrupt() {
235
  d_minisat->interrupt();
236
}
237
238
18863537
SatValue MinisatSatSolver::value(SatLiteral l) {
239
18863537
  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
66192
void MinisatSatSolver::requirePhase(SatLiteral lit) {
251
66192
  Assert(!d_minisat->rnd_pol);
252
66192
  Debug("minisat") << "requirePhase(" << lit << ")" << " " <<  lit.getSatVariable() << " " << lit.isNegated() << std::endl;
253
66192
  SatVariable v = lit.getSatVariable();
254
66192
  d_minisat->freezePolarity(v, lit.isNegated());
255
66192
}
256
257
176861
bool MinisatSatSolver::isDecision(SatVariable decn) const {
258
176861
  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
2496
SatProofManager* MinisatSatSolver::getProofManager()
272
{
273
2496
  return d_minisat->getProofManager();
274
}
275
276
2797
std::shared_ptr<ProofNode> MinisatSatSolver::getProof()
277
{
278
2797
  return d_minisat->getProof();
279
}
280
281
/** Incremental interface */
282
283
18862
unsigned MinisatSatSolver::getAssertionLevel() const {
284
18862
  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
15173
void MinisatSatSolver::resetTrail() { d_minisat->resetTrail(); }
296
297
/// Statistics for MinisatSatSolver
298
299
9905
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
9905
          registry.registerReference<int64_t>("sat::tot_literals"))
315
{
316
9905
}
317
318
9905
void MinisatSatSolver::Statistics::init(Minisat::SimpSolver* minisat){
319
9905
  d_statStarts.set(minisat->starts);
320
9905
  d_statDecisions.set(minisat->decisions);
321
9905
  d_statRndDecisions.set(minisat->rnd_decisions);
322
9905
  d_statPropagations.set(minisat->propagations);
323
9905
  d_statConflicts.set(minisat->conflicts);
324
9905
  d_statClausesLiterals.set(minisat->clauses_literals);
325
9905
  d_statLearntsLiterals.set(minisat->learnts_literals);
326
9905
  d_statMaxLiterals.set(minisat->max_literals);
327
9905
  d_statTotLiterals.set(minisat->tot_literals);
328
9905
}
329
9905
void MinisatSatSolver::Statistics::deinit()
330
{
331
9905
  d_statStarts.reset();
332
9905
  d_statDecisions.reset();
333
9905
  d_statRndDecisions.reset();
334
9905
  d_statPropagations.reset();
335
9905
  d_statConflicts.reset();
336
9905
  d_statClausesLiterals.reset();
337
9905
  d_statLearntsLiterals.reset();
338
9905
  d_statMaxLiterals.reset();
339
9905
  d_statTotLiterals.reset();
340
9905
}
341
342
}  // namespace prop
343
}  // namespace cvc5
344
345
namespace cvc5 {
346
template <>
347
51303
prop::SatLiteral toSatLiteral<cvc5::Minisat::Solver>(Minisat::Solver::TLit lit)
348
{
349
51303
  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
135584
}  // namespace cvc5