1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Andrew Reynolds, Haniel Barbosa, 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 |
|
* Implementation of the propositional engine of cvc5. |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "prop/prop_engine.h" |
17 |
|
|
18 |
|
#include <iomanip> |
19 |
|
#include <map> |
20 |
|
#include <utility> |
21 |
|
|
22 |
|
#include "base/check.h" |
23 |
|
#include "base/output.h" |
24 |
|
#include "decision/decision_engine_old.h" |
25 |
|
#include "decision/justification_strategy.h" |
26 |
|
#include "options/base_options.h" |
27 |
|
#include "options/decision_options.h" |
28 |
|
#include "options/main_options.h" |
29 |
|
#include "options/options.h" |
30 |
|
#include "options/proof_options.h" |
31 |
|
#include "options/smt_options.h" |
32 |
|
#include "prop/cnf_stream.h" |
33 |
|
#include "prop/minisat/minisat.h" |
34 |
|
#include "prop/prop_proof_manager.h" |
35 |
|
#include "prop/sat_solver.h" |
36 |
|
#include "prop/sat_solver_factory.h" |
37 |
|
#include "prop/theory_proxy.h" |
38 |
|
#include "smt/env.h" |
39 |
|
#include "smt/smt_statistics_registry.h" |
40 |
|
#include "theory/output_channel.h" |
41 |
|
#include "theory/theory_engine.h" |
42 |
|
#include "util/resource_manager.h" |
43 |
|
#include "util/result.h" |
44 |
|
|
45 |
|
namespace cvc5 { |
46 |
|
namespace prop { |
47 |
|
|
48 |
|
/** Keeps a boolean flag scoped */ |
49 |
|
class ScopedBool { |
50 |
|
|
51 |
|
private: |
52 |
|
|
53 |
|
bool d_original; |
54 |
|
bool& d_reference; |
55 |
|
|
56 |
|
public: |
57 |
|
|
58 |
20558 |
ScopedBool(bool& reference) : |
59 |
20558 |
d_reference(reference) { |
60 |
20558 |
d_original = reference; |
61 |
20558 |
} |
62 |
|
|
63 |
41116 |
~ScopedBool() { |
64 |
20558 |
d_reference = d_original; |
65 |
20558 |
} |
66 |
|
}; |
67 |
|
|
68 |
15338 |
PropEngine::PropEngine(TheoryEngine* te, Env& env) |
69 |
|
: d_inCheckSat(false), |
70 |
|
d_theoryEngine(te), |
71 |
|
d_env(env), |
72 |
15338 |
d_skdm(new SkolemDefManager(d_env.getContext(), d_env.getUserContext())), |
73 |
|
d_theoryProxy(nullptr), |
74 |
|
d_satSolver(nullptr), |
75 |
|
d_cnfStream(nullptr), |
76 |
|
d_pfCnfStream(nullptr), |
77 |
|
d_ppm(nullptr), |
78 |
|
d_interrupted(false), |
79 |
30676 |
d_assumptions(d_env.getUserContext()) |
80 |
|
{ |
81 |
15338 |
Debug("prop") << "Constructing the PropEngine" << std::endl; |
82 |
15338 |
context::UserContext* userContext = d_env.getUserContext(); |
83 |
15338 |
ProofNodeManager* pnm = d_env.getProofNodeManager(); |
84 |
15338 |
ResourceManager* rm = d_env.getResourceManager(); |
85 |
|
|
86 |
15338 |
options::DecisionMode dmode = options::decisionMode(); |
87 |
15338 |
if (dmode == options::DecisionMode::JUSTIFICATION |
88 |
3009 |
|| dmode == options::DecisionMode::STOPONLY) |
89 |
|
{ |
90 |
12754 |
d_decisionEngine.reset(new decision::JustificationStrategy(env)); |
91 |
|
} |
92 |
2584 |
else if (dmode == options::DecisionMode::JUSTIFICATION_OLD |
93 |
2581 |
|| dmode == options::DecisionMode::STOPONLY_OLD) |
94 |
|
{ |
95 |
3 |
d_decisionEngine.reset(new DecisionEngineOld(env)); |
96 |
|
} |
97 |
|
else |
98 |
|
{ |
99 |
2581 |
d_decisionEngine.reset(new decision::DecisionEngineEmpty(env)); |
100 |
|
} |
101 |
|
|
102 |
15338 |
d_satSolver = SatSolverFactory::createCDCLTMinisat(smtStatisticsRegistry()); |
103 |
|
|
104 |
|
// CNF stream and theory proxy required pointers to each other, make the |
105 |
|
// theory proxy first |
106 |
15338 |
d_theoryProxy = new TheoryProxy( |
107 |
15338 |
this, d_theoryEngine, d_decisionEngine.get(), d_skdm.get(), d_env); |
108 |
46014 |
d_cnfStream = new CnfStream(d_satSolver, |
109 |
15338 |
d_theoryProxy, |
110 |
|
userContext, |
111 |
15338 |
&d_env, |
112 |
|
rm, |
113 |
|
FormulaLitPolicy::TRACK, |
114 |
30676 |
"prop"); |
115 |
|
|
116 |
|
// connect theory proxy |
117 |
15338 |
d_theoryProxy->finishInit(d_cnfStream); |
118 |
15338 |
bool satProofs = d_env.isSatProofProducing(); |
119 |
|
// connect SAT solver |
120 |
46014 |
d_satSolver->initialize(d_env.getContext(), |
121 |
|
d_theoryProxy, |
122 |
15338 |
d_env.getUserContext(), |
123 |
15338 |
satProofs ? pnm : nullptr); |
124 |
|
|
125 |
15338 |
d_decisionEngine->finishInit(d_satSolver, d_cnfStream); |
126 |
15338 |
if (satProofs) |
127 |
|
{ |
128 |
10762 |
d_pfCnfStream.reset(new ProofCnfStream( |
129 |
|
userContext, |
130 |
5381 |
*d_cnfStream, |
131 |
5381 |
static_cast<MinisatSatSolver*>(d_satSolver)->getProofManager(), |
132 |
10762 |
pnm)); |
133 |
10762 |
d_ppm.reset( |
134 |
5381 |
new PropPfManager(userContext, pnm, d_satSolver, d_pfCnfStream.get())); |
135 |
|
} |
136 |
15338 |
} |
137 |
|
|
138 |
15338 |
void PropEngine::finishInit() |
139 |
|
{ |
140 |
15338 |
NodeManager* nm = NodeManager::currentNM(); |
141 |
15338 |
d_cnfStream->convertAndAssert(nm->mkConst(true), false, false); |
142 |
|
// this is necessary because if True is later asserted to the prop engine the |
143 |
|
// CNF stream will ignore it since the SAT solver already had it registered, |
144 |
|
// thus not having True as an assumption for the SAT proof. To solve this |
145 |
|
// issue we track it directly here |
146 |
15338 |
if (isProofEnabled()) |
147 |
|
{ |
148 |
5381 |
static_cast<MinisatSatSolver*>(d_satSolver) |
149 |
|
->getProofManager() |
150 |
5381 |
->registerSatAssumptions({nm->mkConst(true)}); |
151 |
|
} |
152 |
15338 |
d_cnfStream->convertAndAssert(nm->mkConst(false).notNode(), false, false); |
153 |
15338 |
} |
154 |
|
|
155 |
30666 |
PropEngine::~PropEngine() { |
156 |
15333 |
Debug("prop") << "Destructing the PropEngine" << std::endl; |
157 |
15333 |
d_decisionEngine.reset(nullptr); |
158 |
15333 |
delete d_cnfStream; |
159 |
15333 |
delete d_satSolver; |
160 |
15333 |
delete d_theoryProxy; |
161 |
15333 |
} |
162 |
|
|
163 |
117644 |
TrustNode PropEngine::preprocess(TNode node, |
164 |
|
std::vector<theory::SkolemLemma>& newLemmas) |
165 |
|
{ |
166 |
117644 |
return d_theoryProxy->preprocess(node, newLemmas); |
167 |
|
} |
168 |
|
|
169 |
2 |
TrustNode PropEngine::removeItes(TNode node, |
170 |
|
std::vector<theory::SkolemLemma>& newLemmas) |
171 |
|
{ |
172 |
2 |
return d_theoryProxy->removeItes(node, newLemmas); |
173 |
|
} |
174 |
|
|
175 |
19093 |
void PropEngine::assertInputFormulas( |
176 |
|
const std::vector<Node>& assertions, |
177 |
|
std::unordered_map<size_t, Node>& skolemMap) |
178 |
|
{ |
179 |
19093 |
Assert(!d_inCheckSat) << "Sat solver in solve()!"; |
180 |
|
// notify the theory engine of preprocessed assertions |
181 |
19093 |
d_theoryEngine->notifyPreprocessedAssertions(assertions); |
182 |
|
// Now, notify the theory proxy of the assertions and skolem definitions. |
183 |
|
// Notice we do this before asserting the formulas to the CNF stream below, |
184 |
|
// since (preregistration) lemmas may occur during calls to assertInternal. |
185 |
|
// These lemmas we want to be notified about after the theory proxy has |
186 |
|
// been notified about all input assertions. |
187 |
19093 |
std::unordered_map<size_t, Node>::iterator it; |
188 |
154901 |
for (size_t i = 0, asize = assertions.size(); i < asize; i++) |
189 |
|
{ |
190 |
|
// is the assertion a skolem definition? |
191 |
135808 |
it = skolemMap.find(i); |
192 |
271616 |
Node skolem; |
193 |
135808 |
if (it != skolemMap.end()) |
194 |
|
{ |
195 |
18506 |
skolem = it->second; |
196 |
|
} |
197 |
135808 |
d_theoryProxy->notifyAssertion(assertions[i], skolem, false); |
198 |
|
} |
199 |
154891 |
for (const Node& node : assertions) |
200 |
|
{ |
201 |
135802 |
Debug("prop") << "assertFormula(" << node << ")" << std::endl; |
202 |
135806 |
assertInternal(node, false, false, true); |
203 |
|
} |
204 |
19089 |
} |
205 |
|
|
206 |
509538 |
void PropEngine::assertLemma(TrustNode tlemma, theory::LemmaProperty p) |
207 |
|
{ |
208 |
509538 |
bool removable = isLemmaPropertyRemovable(p); |
209 |
|
|
210 |
|
// call preprocessor |
211 |
1019076 |
std::vector<theory::SkolemLemma> ppLemmas; |
212 |
1019076 |
TrustNode tplemma = d_theoryProxy->preprocessLemma(tlemma, ppLemmas); |
213 |
|
|
214 |
|
// do final checks on the lemmas we are about to send |
215 |
1019072 |
if (isProofEnabled() |
216 |
509536 |
&& options::proofCheck() == options::ProofCheckMode::EAGER) |
217 |
|
{ |
218 |
106 |
Assert(tplemma.getGenerator() != nullptr); |
219 |
|
// ensure closed, make the proof node eagerly here to debug |
220 |
106 |
tplemma.debugCheckClosed("te-proof-debug", "TheoryEngine::lemma"); |
221 |
106 |
for (theory::SkolemLemma& lem : ppLemmas) |
222 |
|
{ |
223 |
|
Assert(lem.d_lemma.getGenerator() != nullptr); |
224 |
|
lem.d_lemma.debugCheckClosed("te-proof-debug", "TheoryEngine::lemma_new"); |
225 |
|
} |
226 |
|
} |
227 |
|
|
228 |
509536 |
if (Trace.isOn("te-lemma")) |
229 |
|
{ |
230 |
|
Trace("te-lemma") << "Lemma, output: " << tplemma.getProven() << std::endl; |
231 |
|
for (const theory::SkolemLemma& lem : ppLemmas) |
232 |
|
{ |
233 |
|
Trace("te-lemma") << "Lemma, new lemma: " << lem.d_lemma.getProven() |
234 |
|
<< " (skolem is " << lem.d_skolem << ")" << std::endl; |
235 |
|
} |
236 |
|
} |
237 |
|
|
238 |
|
// now, assert the lemmas |
239 |
509536 |
assertLemmasInternal(tplemma, ppLemmas, removable); |
240 |
509536 |
} |
241 |
|
|
242 |
520405 |
void PropEngine::assertTrustedLemmaInternal(TrustNode trn, bool removable) |
243 |
|
{ |
244 |
1040810 |
Node node = trn.getNode(); |
245 |
520405 |
Debug("prop::lemmas") << "assertLemma(" << node << ")" << std::endl; |
246 |
520405 |
bool negated = trn.getKind() == TrustNodeKind::CONFLICT; |
247 |
520405 |
Assert( |
248 |
|
!isProofEnabled() || trn.getGenerator() != nullptr |
249 |
|
|| options::unsatCores() |
250 |
|
|| (options::unsatCores() |
251 |
|
&& options::unsatCoresMode() != options::UnsatCoresMode::FULL_PROOF)); |
252 |
520405 |
assertInternal(trn.getNode(), negated, removable, false, trn.getGenerator()); |
253 |
520405 |
} |
254 |
|
|
255 |
656207 |
void PropEngine::assertInternal( |
256 |
|
TNode node, bool negated, bool removable, bool input, ProofGenerator* pg) |
257 |
|
{ |
258 |
|
// Assert as (possibly) removable |
259 |
656207 |
if (options::unsatCoresMode() == options::UnsatCoresMode::ASSUMPTIONS) |
260 |
|
{ |
261 |
172312 |
if (input) |
262 |
|
{ |
263 |
35454 |
d_cnfStream->ensureLiteral(node); |
264 |
35454 |
if (negated) |
265 |
|
{ |
266 |
|
d_assumptions.push_back(node.notNode()); |
267 |
|
} |
268 |
|
else |
269 |
|
{ |
270 |
35454 |
d_assumptions.push_back(node); |
271 |
|
} |
272 |
|
} |
273 |
|
else |
274 |
|
{ |
275 |
136858 |
d_cnfStream->convertAndAssert(node, removable, negated, input); |
276 |
|
} |
277 |
|
} |
278 |
483895 |
else if (isProofEnabled()) |
279 |
|
{ |
280 |
98297 |
d_pfCnfStream->convertAndAssert(node, negated, removable, pg); |
281 |
|
// if input, register the assertion in the proof manager |
282 |
98297 |
if (input) |
283 |
|
{ |
284 |
26797 |
d_ppm->registerAssertion(node); |
285 |
|
} |
286 |
|
} |
287 |
|
else |
288 |
|
{ |
289 |
385602 |
d_cnfStream->convertAndAssert(node, removable, negated, input); |
290 |
|
} |
291 |
656203 |
} |
292 |
|
|
293 |
731953 |
void PropEngine::assertLemmasInternal( |
294 |
|
TrustNode trn, |
295 |
|
const std::vector<theory::SkolemLemma>& ppLemmas, |
296 |
|
bool removable) |
297 |
|
{ |
298 |
731953 |
if (!trn.isNull()) |
299 |
|
{ |
300 |
509536 |
assertTrustedLemmaInternal(trn, removable); |
301 |
|
} |
302 |
742822 |
for (const theory::SkolemLemma& lem : ppLemmas) |
303 |
|
{ |
304 |
10869 |
assertTrustedLemmaInternal(lem.d_lemma, removable); |
305 |
|
} |
306 |
|
// assert to decision engine |
307 |
731953 |
if (!removable) |
308 |
|
{ |
309 |
|
// also add to the decision engine, where notice we don't need proofs |
310 |
586809 |
if (!trn.isNull()) |
311 |
|
{ |
312 |
|
// notify the theory proxy of the lemma |
313 |
364392 |
d_theoryProxy->notifyAssertion(trn.getProven(), TNode::null(), true); |
314 |
|
} |
315 |
597678 |
for (const theory::SkolemLemma& lem : ppLemmas) |
316 |
|
{ |
317 |
10869 |
d_theoryProxy->notifyAssertion(lem.getProven(), lem.d_skolem, true); |
318 |
|
} |
319 |
|
} |
320 |
731953 |
} |
321 |
|
|
322 |
72028 |
void PropEngine::requirePhase(TNode n, bool phase) { |
323 |
72028 |
Debug("prop") << "requirePhase(" << n << ", " << phase << ")" << std::endl; |
324 |
|
|
325 |
72028 |
Assert(n.getType().isBoolean()); |
326 |
72028 |
SatLiteral lit = d_cnfStream->getLiteral(n); |
327 |
72028 |
d_satSolver->requirePhase(phase ? lit : ~lit); |
328 |
72028 |
} |
329 |
|
|
330 |
171444 |
bool PropEngine::isDecision(Node lit) const { |
331 |
171444 |
Assert(isSatLiteral(lit)); |
332 |
171444 |
return d_satSolver->isDecision(d_cnfStream->getLiteral(lit).getSatVariable()); |
333 |
|
} |
334 |
|
|
335 |
8 |
int32_t PropEngine::getDecisionLevel(Node lit) const |
336 |
|
{ |
337 |
8 |
Assert(isSatLiteral(lit)); |
338 |
16 |
return d_satSolver->getDecisionLevel( |
339 |
16 |
d_cnfStream->getLiteral(lit).getSatVariable()); |
340 |
|
} |
341 |
|
|
342 |
8 |
int32_t PropEngine::getIntroLevel(Node lit) const |
343 |
|
{ |
344 |
8 |
Assert(isSatLiteral(lit)); |
345 |
16 |
return d_satSolver->getIntroLevel( |
346 |
16 |
d_cnfStream->getLiteral(lit).getSatVariable()); |
347 |
|
} |
348 |
|
|
349 |
|
void PropEngine::printSatisfyingAssignment(){ |
350 |
|
const CnfStream::NodeToLiteralMap& transCache = |
351 |
|
d_cnfStream->getTranslationCache(); |
352 |
|
Debug("prop-value") << "Literal | Value | Expr" << std::endl |
353 |
|
<< "----------------------------------------" |
354 |
|
<< "-----------------" << std::endl; |
355 |
|
for(CnfStream::NodeToLiteralMap::const_iterator i = transCache.begin(), |
356 |
|
end = transCache.end(); |
357 |
|
i != end; |
358 |
|
++i) { |
359 |
|
std::pair<Node, SatLiteral> curr = *i; |
360 |
|
SatLiteral l = curr.second; |
361 |
|
if(!l.isNegated()) { |
362 |
|
Node n = curr.first; |
363 |
|
SatValue value = d_satSolver->modelValue(l); |
364 |
|
Debug("prop-value") << "'" << l << "' " << value << " " << n << std::endl; |
365 |
|
} |
366 |
|
} |
367 |
|
} |
368 |
|
|
369 |
20558 |
Result PropEngine::checkSat() { |
370 |
20558 |
Assert(!d_inCheckSat) << "Sat solver in solve()!"; |
371 |
20558 |
Debug("prop") << "PropEngine::checkSat()" << std::endl; |
372 |
|
|
373 |
|
// Mark that we are in the checkSat |
374 |
41116 |
ScopedBool scopedBool(d_inCheckSat); |
375 |
20558 |
d_inCheckSat = true; |
376 |
|
|
377 |
|
// Note this currently ignores conflicts (a dangerous practice). |
378 |
20558 |
d_theoryProxy->presolve(); |
379 |
|
|
380 |
20558 |
if(options::preprocessOnly()) { |
381 |
3 |
return Result(Result::SAT_UNKNOWN, Result::REQUIRES_FULL_CHECK); |
382 |
|
} |
383 |
|
|
384 |
|
// Reset the interrupted flag |
385 |
20555 |
d_interrupted = false; |
386 |
|
|
387 |
|
// Check the problem |
388 |
|
SatValue result; |
389 |
20555 |
if (d_assumptions.size() == 0) |
390 |
|
{ |
391 |
16842 |
result = d_satSolver->solve(); |
392 |
|
} |
393 |
|
else |
394 |
|
{ |
395 |
7426 |
std::vector<SatLiteral> assumptions; |
396 |
53923 |
for (const Node& node : d_assumptions) |
397 |
|
{ |
398 |
50210 |
assumptions.push_back(d_cnfStream->getLiteral(node)); |
399 |
|
} |
400 |
3713 |
result = d_satSolver->solve(assumptions); |
401 |
|
} |
402 |
|
|
403 |
20532 |
if( result == SAT_VALUE_UNKNOWN ) { |
404 |
|
ResourceManager* rm = d_env.getResourceManager(); |
405 |
|
Result::UnknownExplanation why = Result::INTERRUPTED; |
406 |
|
if (rm->outOfTime()) |
407 |
|
{ |
408 |
|
why = Result::TIMEOUT; |
409 |
|
} |
410 |
|
if (rm->outOfResources()) |
411 |
|
{ |
412 |
|
why = Result::RESOURCEOUT; |
413 |
|
} |
414 |
|
return Result(Result::SAT_UNKNOWN, why); |
415 |
|
} |
416 |
|
|
417 |
20532 |
if( result == SAT_VALUE_TRUE && Debug.isOn("prop") ) { |
418 |
|
printSatisfyingAssignment(); |
419 |
|
} |
420 |
|
|
421 |
20532 |
Debug("prop") << "PropEngine::checkSat() => " << result << std::endl; |
422 |
20532 |
if(result == SAT_VALUE_TRUE && d_theoryEngine->isIncomplete()) { |
423 |
145 |
return Result(Result::SAT_UNKNOWN, Result::INCOMPLETE); |
424 |
|
} |
425 |
20387 |
return Result(result == SAT_VALUE_TRUE ? Result::SAT : Result::UNSAT); |
426 |
|
} |
427 |
|
|
428 |
50905 |
Node PropEngine::getValue(TNode node) const |
429 |
|
{ |
430 |
50905 |
Assert(node.getType().isBoolean()); |
431 |
50905 |
Assert(d_cnfStream->hasLiteral(node)); |
432 |
|
|
433 |
50905 |
SatLiteral lit = d_cnfStream->getLiteral(node); |
434 |
|
|
435 |
50905 |
SatValue v = d_satSolver->value(lit); |
436 |
50905 |
if (v == SAT_VALUE_TRUE) |
437 |
|
{ |
438 |
50872 |
return NodeManager::currentNM()->mkConst(true); |
439 |
|
} |
440 |
33 |
else if (v == SAT_VALUE_FALSE) |
441 |
|
{ |
442 |
33 |
return NodeManager::currentNM()->mkConst(false); |
443 |
|
} |
444 |
|
else |
445 |
|
{ |
446 |
|
Assert(v == SAT_VALUE_UNKNOWN); |
447 |
|
return Node::null(); |
448 |
|
} |
449 |
|
} |
450 |
|
|
451 |
35265678 |
bool PropEngine::isSatLiteral(TNode node) const |
452 |
|
{ |
453 |
35265678 |
return d_cnfStream->hasLiteral(node); |
454 |
|
} |
455 |
|
|
456 |
12627434 |
bool PropEngine::hasValue(TNode node, bool& value) const |
457 |
|
{ |
458 |
12627434 |
Assert(node.getType().isBoolean()); |
459 |
12627434 |
Assert(d_cnfStream->hasLiteral(node)) << node; |
460 |
|
|
461 |
12627434 |
SatLiteral lit = d_cnfStream->getLiteral(node); |
462 |
|
|
463 |
12627434 |
SatValue v = d_satSolver->value(lit); |
464 |
12627434 |
if (v == SAT_VALUE_TRUE) |
465 |
|
{ |
466 |
7609770 |
value = true; |
467 |
7609770 |
return true; |
468 |
|
} |
469 |
5017664 |
else if (v == SAT_VALUE_FALSE) |
470 |
|
{ |
471 |
169145 |
value = false; |
472 |
169145 |
return true; |
473 |
|
} |
474 |
|
else |
475 |
|
{ |
476 |
4848519 |
Assert(v == SAT_VALUE_UNKNOWN); |
477 |
4848519 |
return false; |
478 |
|
} |
479 |
|
} |
480 |
|
|
481 |
24830 |
void PropEngine::getBooleanVariables(std::vector<TNode>& outputVariables) const |
482 |
|
{ |
483 |
24830 |
d_cnfStream->getBooleanVariables(outputVariables); |
484 |
24830 |
} |
485 |
|
|
486 |
217228 |
Node PropEngine::ensureLiteral(TNode n) |
487 |
|
{ |
488 |
|
// must preprocess |
489 |
217228 |
Node preprocessed = getPreprocessedTerm(n); |
490 |
434456 |
Trace("ensureLiteral") << "ensureLiteral preprocessed: " << preprocessed |
491 |
217228 |
<< std::endl; |
492 |
217228 |
if (isProofEnabled()) |
493 |
|
{ |
494 |
26663 |
d_pfCnfStream->ensureLiteral(preprocessed); |
495 |
|
} |
496 |
|
else |
497 |
|
{ |
498 |
190565 |
d_cnfStream->ensureLiteral(preprocessed); |
499 |
|
} |
500 |
217228 |
return preprocessed; |
501 |
|
} |
502 |
|
|
503 |
222417 |
Node PropEngine::getPreprocessedTerm(TNode n) |
504 |
|
{ |
505 |
|
// must preprocess |
506 |
444834 |
std::vector<theory::SkolemLemma> newLemmas; |
507 |
444834 |
TrustNode tpn = d_theoryProxy->preprocess(n, newLemmas); |
508 |
|
// send lemmas corresponding to the skolems introduced by preprocessing n |
509 |
444834 |
TrustNode trnNull; |
510 |
222417 |
assertLemmasInternal(trnNull, newLemmas, false); |
511 |
444834 |
return tpn.isNull() ? Node(n) : tpn.getNode(); |
512 |
|
} |
513 |
|
|
514 |
2498 |
Node PropEngine::getPreprocessedTerm(TNode n, |
515 |
|
std::vector<Node>& skAsserts, |
516 |
|
std::vector<Node>& sks) |
517 |
|
{ |
518 |
|
// get the preprocessed form of the term |
519 |
2498 |
Node pn = getPreprocessedTerm(n); |
520 |
|
// initialize the set of skolems and assertions to process |
521 |
4996 |
std::vector<Node> toProcessAsserts; |
522 |
4996 |
std::vector<Node> toProcess; |
523 |
2498 |
d_theoryProxy->getSkolems(pn, toProcessAsserts, toProcess); |
524 |
2498 |
size_t index = 0; |
525 |
|
// until fixed point is reached |
526 |
7544 |
while (index < toProcess.size()) |
527 |
|
{ |
528 |
3701 |
Node ka = toProcessAsserts[index]; |
529 |
3701 |
Node k = toProcess[index]; |
530 |
2523 |
index++; |
531 |
2523 |
if (std::find(sks.begin(), sks.end(), k) != sks.end()) |
532 |
|
{ |
533 |
|
// already added the skolem to the list |
534 |
1345 |
continue; |
535 |
|
} |
536 |
|
// must preprocess lemmas as well |
537 |
2356 |
Node kap = getPreprocessedTerm(ka); |
538 |
1178 |
skAsserts.push_back(kap); |
539 |
1178 |
sks.push_back(k); |
540 |
|
// get the skolems in the preprocessed form of the lemma ka |
541 |
1178 |
d_theoryProxy->getSkolems(kap, toProcessAsserts, toProcess); |
542 |
|
} |
543 |
|
// return the preprocessed term |
544 |
4996 |
return pn; |
545 |
|
} |
546 |
|
|
547 |
4937 |
void PropEngine::push() |
548 |
|
{ |
549 |
4937 |
Assert(!d_inCheckSat) << "Sat solver in solve()!"; |
550 |
4937 |
d_satSolver->push(); |
551 |
4937 |
Debug("prop") << "push()" << std::endl; |
552 |
4937 |
} |
553 |
|
|
554 |
4937 |
void PropEngine::pop() |
555 |
|
{ |
556 |
4937 |
Assert(!d_inCheckSat) << "Sat solver in solve()!"; |
557 |
4937 |
d_satSolver->pop(); |
558 |
4937 |
Debug("prop") << "pop()" << std::endl; |
559 |
4937 |
} |
560 |
|
|
561 |
20535 |
void PropEngine::resetTrail() |
562 |
|
{ |
563 |
20535 |
d_satSolver->resetTrail(); |
564 |
20535 |
Debug("prop") << "resetTrail()" << std::endl; |
565 |
20535 |
} |
566 |
|
|
567 |
24508 |
unsigned PropEngine::getAssertionLevel() const |
568 |
|
{ |
569 |
24508 |
return d_satSolver->getAssertionLevel(); |
570 |
|
} |
571 |
|
|
572 |
|
bool PropEngine::isRunning() const { return d_inCheckSat; } |
573 |
|
void PropEngine::interrupt() |
574 |
|
{ |
575 |
|
if (!d_inCheckSat) |
576 |
|
{ |
577 |
|
return; |
578 |
|
} |
579 |
|
|
580 |
|
d_interrupted = true; |
581 |
|
d_satSolver->interrupt(); |
582 |
|
Debug("prop") << "interrupt()" << std::endl; |
583 |
|
} |
584 |
|
|
585 |
2631 |
void PropEngine::spendResource(Resource r) |
586 |
|
{ |
587 |
2631 |
d_env.getResourceManager()->spendResource(r); |
588 |
2631 |
} |
589 |
|
|
590 |
|
bool PropEngine::properExplanation(TNode node, TNode expl) const |
591 |
|
{ |
592 |
|
if (!d_cnfStream->hasLiteral(node)) |
593 |
|
{ |
594 |
|
Trace("properExplanation") |
595 |
|
<< "properExplanation(): Failing because node " |
596 |
|
<< "being explained doesn't have a SAT literal ?!" << std::endl |
597 |
|
<< "properExplanation(): The node is: " << node << std::endl; |
598 |
|
return false; |
599 |
|
} |
600 |
|
|
601 |
|
SatLiteral nodeLit = d_cnfStream->getLiteral(node); |
602 |
|
|
603 |
|
for (TNode::kinded_iterator i = expl.begin(kind::AND), |
604 |
|
i_end = expl.end(kind::AND); |
605 |
|
i != i_end; |
606 |
|
++i) |
607 |
|
{ |
608 |
|
if (!d_cnfStream->hasLiteral(*i)) |
609 |
|
{ |
610 |
|
Trace("properExplanation") |
611 |
|
<< "properExplanation(): Failing because one of explanation " |
612 |
|
<< "nodes doesn't have a SAT literal" << std::endl |
613 |
|
<< "properExplanation(): The explanation node is: " << *i |
614 |
|
<< std::endl; |
615 |
|
return false; |
616 |
|
} |
617 |
|
|
618 |
|
SatLiteral iLit = d_cnfStream->getLiteral(*i); |
619 |
|
|
620 |
|
if (iLit == nodeLit) |
621 |
|
{ |
622 |
|
Trace("properExplanation") |
623 |
|
<< "properExplanation(): Failing because the node" << std::endl |
624 |
|
<< "properExplanation(): " << node << std::endl |
625 |
|
<< "properExplanation(): cannot be made to explain itself!" |
626 |
|
<< std::endl; |
627 |
|
return false; |
628 |
|
} |
629 |
|
|
630 |
|
if (!d_satSolver->properExplanation(nodeLit, iLit)) |
631 |
|
{ |
632 |
|
Trace("properExplanation") |
633 |
|
<< "properExplanation(): SAT solver told us that node" << std::endl |
634 |
|
<< "properExplanation(): " << *i << std::endl |
635 |
|
<< "properExplanation(): is not part of a proper explanation node for" |
636 |
|
<< std::endl |
637 |
|
<< "properExplanation(): " << node << std::endl |
638 |
|
<< "properExplanation(): Perhaps it one of the two isn't assigned or " |
639 |
|
"the explanation" |
640 |
|
<< std::endl |
641 |
|
<< "properExplanation(): node wasn't propagated before the node " |
642 |
|
"being explained" |
643 |
|
<< std::endl; |
644 |
|
return false; |
645 |
|
} |
646 |
|
} |
647 |
|
|
648 |
|
return true; |
649 |
|
} |
650 |
|
|
651 |
|
void PropEngine::checkProof(const context::CDList<Node>& assertions) |
652 |
|
{ |
653 |
|
if (!d_env.isSatProofProducing()) |
654 |
|
{ |
655 |
|
return; |
656 |
|
} |
657 |
|
return d_ppm->checkProof(assertions); |
658 |
|
} |
659 |
|
|
660 |
15225 |
ProofCnfStream* PropEngine::getProofCnfStream() { return d_pfCnfStream.get(); } |
661 |
|
|
662 |
10060 |
std::shared_ptr<ProofNode> PropEngine::getProof() |
663 |
|
{ |
664 |
10060 |
if (!d_env.isSatProofProducing()) |
665 |
|
{ |
666 |
|
return nullptr; |
667 |
|
} |
668 |
10060 |
return d_ppm->getProof(); |
669 |
|
} |
670 |
|
|
671 |
1746402 |
bool PropEngine::isProofEnabled() const { return d_pfCnfStream != nullptr; } |
672 |
|
|
673 |
1409 |
void PropEngine::getUnsatCore(std::vector<Node>& core) |
674 |
|
{ |
675 |
1409 |
Assert(options::unsatCoresMode() == options::UnsatCoresMode::ASSUMPTIONS); |
676 |
2818 |
std::vector<SatLiteral> unsat_assumptions; |
677 |
1409 |
d_satSolver->getUnsatAssumptions(unsat_assumptions); |
678 |
8352 |
for (const SatLiteral& lit : unsat_assumptions) |
679 |
|
{ |
680 |
6943 |
core.push_back(d_cnfStream->getNode(lit)); |
681 |
|
} |
682 |
1409 |
} |
683 |
|
|
684 |
1409 |
std::shared_ptr<ProofNode> PropEngine::getRefutation() |
685 |
|
{ |
686 |
1409 |
Assert(options::unsatCoresMode() == options::UnsatCoresMode::ASSUMPTIONS); |
687 |
2818 |
std::vector<Node> core; |
688 |
1409 |
getUnsatCore(core); |
689 |
2818 |
CDProof cdp(d_env.getProofNodeManager()); |
690 |
2818 |
Node fnode = NodeManager::currentNM()->mkConst(false); |
691 |
1409 |
cdp.addStep(fnode, PfRule::SAT_REFUTATION, core, {}); |
692 |
2818 |
return cdp.getProofFor(fnode); |
693 |
|
} |
694 |
|
|
695 |
|
} // namespace prop |
696 |
31125 |
} // namespace cvc5 |