1 /********************* */
2 /*! \file theory_engine.cpp
4 ** Top contributors (to current version):
5 ** Dejan Jovanovic, Morgan Deters, Andrew Reynolds
6 ** This file is part of the CVC4 project.
7 ** Copyright (c) 2009-2019 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.\endverbatim
12 ** \brief The theory engine
17 #include "theory/theory_engine.h"
22 #include "base/map_util.h"
23 #include "decision/decision_engine.h"
24 #include "expr/attribute.h"
25 #include "expr/node.h"
26 #include "expr/node_algorithm.h"
27 #include "expr/node_builder.h"
28 #include "expr/node_visitor.h"
29 #include "options/bv_options.h"
30 #include "options/options.h"
31 #include "options/proof_options.h"
32 #include "options/quantifiers_options.h"
33 #include "options/theory_options.h"
34 #include "preprocessing/assertion_pipeline.h"
35 #include "proof/cnf_proof.h"
36 #include "proof/lemma_proof.h"
37 #include "proof/proof_manager.h"
38 #include "proof/theory_proof.h"
39 #include "smt/logic_exception.h"
40 #include "smt/term_formula_removal.h"
41 #include "theory/arith/arith_ite_utils.h"
42 #include "theory/bv/theory_bv_utils.h"
43 #include "theory/care_graph.h"
44 #include "theory/quantifiers/first_order_model.h"
45 #include "theory/quantifiers/fmf/model_engine.h"
46 #include "theory/quantifiers/theory_quantifiers.h"
47 #include "theory/quantifiers_engine.h"
48 #include "theory/rewriter.h"
49 #include "theory/theory.h"
50 #include "theory/theory_model.h"
51 #include "theory/theory_traits.h"
52 #include "theory/uf/equality_engine.h"
53 #include "util/resource_manager.h"
57 using namespace CVC4::preprocessing
;
58 using namespace CVC4::theory
;
62 /* -------------------------------------------------------------------------- */
67 * IMPORTANT: The order of the theories is important. For example, strings
68 * depends on arith, quantifiers needs to come as the very last.
69 * Do not change this order.
72 #define CVC4_FOR_EACH_THEORY \
73 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BUILTIN) \
74 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BOOL) \
75 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_UF) \
76 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_ARITH) \
77 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BV) \
78 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_FP) \
79 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_ARRAYS) \
80 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_DATATYPES) \
81 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_SEP) \
82 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_SETS) \
83 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_STRINGS) \
84 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_QUANTIFIERS)
88 /* -------------------------------------------------------------------------- */
90 inline void flattenAnd(Node n
, std::vector
<TNode
>& out
){
91 Assert(n
.getKind() == kind::AND
);
92 for(Node::iterator i
=n
.begin(), i_end
=n
.end(); i
!= i_end
; ++i
){
94 if(curr
.getKind() == kind::AND
){
95 flattenAnd(curr
, out
);
102 inline Node
flattenAnd(Node n
){
103 std::vector
<TNode
> out
;
105 return NodeManager::currentNM()->mkNode(kind::AND
, out
);
109 * Compute the string for a given theory id. In this module, we use
110 * THEORY_SAT_SOLVER as an id, which is not a normal id but maps to
111 * THEORY_LAST. Thus, we need our own string conversion here.
113 * @param id The theory id
114 * @return The string corresponding to the theory id
116 std::string
getTheoryString(theory::TheoryId id
)
118 if (id
== theory::THEORY_SAT_SOLVER
)
120 return "THEORY_SAT_SOLVER";
124 std::stringstream ss
;
130 theory::LemmaStatus
TheoryEngine::EngineOutputChannel::lemma(TNode lemma
,
135 Debug("theory::lemma") << "EngineOutputChannel<" << d_theory
<< ">::lemma("
137 << ", preprocess = " << preprocess
<< std::endl
;
138 ++d_statistics
.lemmas
;
139 d_engine
->d_outputChannelUsed
= true;
141 PROOF({ registerLemmaRecipe(lemma
, lemma
, preprocess
, d_theory
); });
143 theory::LemmaStatus result
=
144 d_engine
->lemma(lemma
, rule
, false, removable
, preprocess
,
145 sendAtoms
? d_theory
: theory::THEORY_LAST
);
149 void TheoryEngine::EngineOutputChannel::registerLemmaRecipe(Node lemma
, Node originalLemma
, bool preprocess
, theory::TheoryId theoryId
) {
150 // During CNF conversion, conjunctions will be broken down into
151 // multiple lemmas. In order for the recipes to match, we have to do
153 NodeManager
* nm
= NodeManager::currentNM();
156 lemma
= d_engine
->preprocess(lemma
);
158 bool negated
= (lemma
.getKind() == kind::NOT
);
159 Node nnLemma
= negated
? lemma
[0] : lemma
;
161 switch (nnLemma
.getKind()) {
165 for (unsigned i
= 0; i
< nnLemma
.getNumChildren(); ++i
)
166 registerLemmaRecipe(nnLemma
[i
], originalLemma
, false, theoryId
);
168 NodeBuilder
<> builder(kind::OR
);
169 for (unsigned i
= 0; i
< nnLemma
.getNumChildren(); ++i
)
170 builder
<< nnLemma
[i
].negate();
172 Node disjunction
= (builder
.getNumChildren() == 1) ? builder
[0] : builder
;
173 registerLemmaRecipe(disjunction
, originalLemma
, false, theoryId
);
178 if( nnLemma
[0].getType().isBoolean() ){
180 registerLemmaRecipe(nm
->mkNode(kind::OR
, nnLemma
[0], nnLemma
[1].negate()), originalLemma
, false, theoryId
);
181 registerLemmaRecipe(nm
->mkNode(kind::OR
, nnLemma
[0].negate(), nnLemma
[1]), originalLemma
, false, theoryId
);
183 registerLemmaRecipe(nm
->mkNode(kind::OR
, nnLemma
[0], nnLemma
[1]), originalLemma
, false, theoryId
);
184 registerLemmaRecipe(nm
->mkNode(kind::OR
, nnLemma
[0].negate(), nnLemma
[1].negate()), originalLemma
, false, theoryId
);
191 registerLemmaRecipe(nm
->mkNode(kind::OR
, nnLemma
[0].negate(), nnLemma
[1]), originalLemma
, false, theoryId
);
192 registerLemmaRecipe(nm
->mkNode(kind::OR
, nnLemma
[0], nnLemma
[2]), originalLemma
, false, theoryId
);
194 registerLemmaRecipe(nm
->mkNode(kind::OR
, nnLemma
[0].negate(), nnLemma
[1].negate()), originalLemma
, false, theoryId
);
195 registerLemmaRecipe(nm
->mkNode(kind::OR
, nnLemma
[0], nnLemma
[2].negate()), originalLemma
, false, theoryId
);
203 // Theory lemmas have one step that proves the empty clause
204 LemmaProofRecipe proofRecipe
;
206 LemmaProofRecipe::ProofStep
proofStep(theoryId
, emptyNode
);
208 // Remember the original lemma, so we can report this later when asked to
209 proofRecipe
.setOriginalLemma(originalLemma
);
211 // Record the assertions and rewrites
213 if (lemma
.getKind() == kind::OR
) {
214 for (unsigned i
= 0; i
< lemma
.getNumChildren(); ++i
) {
215 rewritten
= theory::Rewriter::rewrite(lemma
[i
]);
216 if (rewritten
!= lemma
[i
]) {
217 proofRecipe
.addRewriteRule(lemma
[i
].negate(), rewritten
.negate());
219 proofStep
.addAssertion(lemma
[i
]);
220 proofRecipe
.addBaseAssertion(rewritten
);
223 rewritten
= theory::Rewriter::rewrite(lemma
);
224 if (rewritten
!= lemma
) {
225 proofRecipe
.addRewriteRule(lemma
.negate(), rewritten
.negate());
227 proofStep
.addAssertion(lemma
);
228 proofRecipe
.addBaseAssertion(rewritten
);
230 proofRecipe
.addStep(proofStep
);
231 ProofManager::getCnfProof()->setProofRecipe(&proofRecipe
);
234 theory::LemmaStatus
TheoryEngine::EngineOutputChannel::splitLemma(
235 TNode lemma
, bool removable
) {
236 Debug("theory::lemma") << "EngineOutputChannel<" << d_theory
<< ">::lemma("
237 << lemma
<< ")" << std::endl
;
238 ++d_statistics
.lemmas
;
239 d_engine
->d_outputChannelUsed
= true;
241 Debug("pf::explain") << "TheoryEngine::EngineOutputChannel::splitLemma( "
242 << lemma
<< " )" << std::endl
;
243 theory::LemmaStatus result
=
244 d_engine
->lemma(lemma
, RULE_SPLIT
, false, removable
, false, d_theory
);
248 bool TheoryEngine::EngineOutputChannel::propagate(TNode literal
) {
249 Debug("theory::propagate") << "EngineOutputChannel<" << d_theory
250 << ">::propagate(" << literal
<< ")" << std::endl
;
251 ++d_statistics
.propagations
;
252 d_engine
->d_outputChannelUsed
= true;
253 return d_engine
->propagate(literal
, d_theory
);
256 void TheoryEngine::EngineOutputChannel::conflict(TNode conflictNode
,
257 std::unique_ptr
<Proof
> proof
)
259 Trace("theory::conflict")
260 << "EngineOutputChannel<" << d_theory
<< ">::conflict(" << conflictNode
262 Assert(!proof
); // Theory shouldn't be producing proofs yet
263 ++d_statistics
.conflicts
;
264 d_engine
->d_outputChannelUsed
= true;
265 d_engine
->conflict(conflictNode
, d_theory
);
268 void TheoryEngine::finishInit() {
270 //initialize the quantifiers engine, master equality engine, model, model builder
271 if( d_logicInfo
.isQuantified() ) {
272 // initialize the quantifiers engine
273 d_quantEngine
= new QuantifiersEngine(d_context
, d_userContext
, this);
274 Assert(d_masterEqualityEngine
== 0);
275 d_masterEqualityEngine
= new eq::EqualityEngine(d_masterEENotify
,getSatContext(), "theory::master", false);
277 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
; ++ theoryId
) {
278 if (d_theoryTable
[theoryId
]) {
279 d_theoryTable
[theoryId
]->setQuantifiersEngine(d_quantEngine
);
280 d_theoryTable
[theoryId
]->setMasterEqualityEngine(d_masterEqualityEngine
);
284 d_curr_model_builder
= d_quantEngine
->getModelBuilder();
285 d_curr_model
= d_quantEngine
->getModel();
287 d_curr_model
= new theory::TheoryModel(
288 d_userContext
, "DefaultModel", options::assignFunctionValues());
289 d_aloc_curr_model
= true;
291 //make the default builder, e.g. in the case that the quantifiers engine does not have a model builder
292 if( d_curr_model_builder
==NULL
){
293 d_curr_model_builder
= new theory::TheoryEngineModelBuilder(this);
294 d_aloc_curr_model_builder
= true;
297 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
; ++ theoryId
) {
298 if (d_theoryTable
[theoryId
]) {
299 // set the decision manager for the theory
300 d_theoryTable
[theoryId
]->setDecisionManager(d_decManager
.get());
301 // finish initializing the theory
302 d_theoryTable
[theoryId
]->finishInit();
307 void TheoryEngine::eqNotifyNewClass(TNode t
){
308 if (d_logicInfo
.isQuantified()) {
309 d_quantEngine
->eqNotifyNewClass( t
);
313 TheoryEngine::TheoryEngine(context::Context
* context
,
314 context::UserContext
* userContext
,
315 RemoveTermFormulas
& iteRemover
,
316 const LogicInfo
& logicInfo
)
317 : d_propEngine(nullptr),
319 d_userContext(userContext
),
320 d_logicInfo(logicInfo
),
321 d_sharedTerms(this, context
),
322 d_masterEqualityEngine(nullptr),
323 d_masterEENotify(*this),
324 d_quantEngine(nullptr),
325 d_decManager(new DecisionManager(userContext
)),
326 d_curr_model(nullptr),
327 d_aloc_curr_model(false),
328 d_curr_model_builder(nullptr),
329 d_aloc_curr_model_builder(false),
330 d_eager_model_building(false),
332 d_possiblePropagations(context
),
333 d_hasPropagated(context
),
334 d_inConflict(context
, false),
336 d_hasShutDown(false),
337 d_incomplete(context
, false),
338 d_propagationMap(context
),
339 d_propagationMapTimestamp(context
, 0),
340 d_propagatedLiterals(context
),
341 d_propagatedLiteralsIndex(context
, 0),
342 d_atomRequests(context
),
343 d_tform_remover(iteRemover
),
344 d_combineTheoriesTime("TheoryEngine::combineTheoriesTime"),
347 d_interrupted(false),
348 d_resourceManager(NodeManager::currentResourceManager()),
349 d_inPreregister(false),
350 d_factsAsserted(context
, false),
351 d_preRegistrationVisitor(this, context
),
352 d_sharedTermsVisitor(d_sharedTerms
),
353 d_theoryAlternatives(),
355 d_arithSubstitutionsAdded("theory::arith::zzz::arith::substitutions", 0)
357 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
;
360 d_theoryTable
[theoryId
] = NULL
;
361 d_theoryOut
[theoryId
] = NULL
;
364 smtStatisticsRegistry()->registerStat(&d_combineTheoriesTime
);
365 d_true
= NodeManager::currentNM()->mkConst
<bool>(true);
366 d_false
= NodeManager::currentNM()->mkConst
<bool>(false);
369 ProofManager::currentPM()->initTheoryProofEngine();
372 smtStatisticsRegistry()->registerStat(&d_arithSubstitutionsAdded
);
375 TheoryEngine::~TheoryEngine() {
376 Assert(d_hasShutDown
);
378 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
; ++ theoryId
) {
379 if(d_theoryTable
[theoryId
] != NULL
) {
380 delete d_theoryTable
[theoryId
];
381 delete d_theoryOut
[theoryId
];
385 if( d_aloc_curr_model_builder
){
386 delete d_curr_model_builder
;
388 if( d_aloc_curr_model
){
392 delete d_quantEngine
;
394 delete d_masterEqualityEngine
;
396 smtStatisticsRegistry()->unregisterStat(&d_combineTheoriesTime
);
397 smtStatisticsRegistry()->unregisterStat(&d_arithSubstitutionsAdded
);
400 void TheoryEngine::interrupt() { d_interrupted
= true; }
401 void TheoryEngine::preRegister(TNode preprocessed
) {
403 Debug("theory") << "TheoryEngine::preRegister( " << preprocessed
<< ")" << std::endl
;
404 if(Dump
.isOn("missed-t-propagations")) {
405 d_possiblePropagations
.push_back(preprocessed
);
407 d_preregisterQueue
.push(preprocessed
);
409 if (!d_inPreregister
) {
410 // We're in pre-register
411 d_inPreregister
= true;
413 // Process the pre-registration queue
414 while (!d_preregisterQueue
.empty()) {
415 // Get the next atom to pre-register
416 preprocessed
= d_preregisterQueue
.front();
417 d_preregisterQueue
.pop();
419 if (d_logicInfo
.isSharingEnabled() && preprocessed
.getKind() == kind::EQUAL
) {
420 // When sharing is enabled, we propagate from the shared terms manager also
421 d_sharedTerms
.addEqualityToPropagate(preprocessed
);
424 // the atom should not have free variables
425 Debug("theory") << "TheoryEngine::preRegister: " << preprocessed
427 Assert(!expr::hasFreeVar(preprocessed
));
428 // Pre-register the terms in the atom
429 Theory::Set theories
= NodeVisitor
<PreRegisterVisitor
>::run(d_preRegistrationVisitor
, preprocessed
);
430 theories
= Theory::setRemove(THEORY_BOOL
, theories
);
431 // Remove the top theory, if any more that means multiple theories were involved
432 bool multipleTheories
= Theory::setRemove(Theory::theoryOf(preprocessed
), theories
);
434 // These checks don't work with finite model finding, because it
435 // uses Rational constants to represent cardinality constraints,
436 // even though arithmetic isn't actually involved.
437 if(!options::finiteModelFind()) {
438 while((i
= Theory::setPop(theories
)) != THEORY_LAST
) {
439 if(!d_logicInfo
.isTheoryEnabled(i
)) {
440 LogicInfo newLogicInfo
= d_logicInfo
.getUnlockedCopy();
441 newLogicInfo
.enableTheory(i
);
444 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
445 << ", which doesn't include " << i
446 << ", but found a term in that theory." << endl
447 << "You might want to extend your logic to "
448 << newLogicInfo
.getLogicString() << endl
;
449 throw LogicException(ss
.str());
453 if (multipleTheories
) {
454 // Collect the shared terms if there are multiple theories
455 NodeVisitor
<SharedTermsVisitor
>::run(d_sharedTermsVisitor
, preprocessed
);
459 // Leaving pre-register
460 d_inPreregister
= false;
464 void TheoryEngine::printAssertions(const char* tag
) {
465 if (Trace
.isOn(tag
)) {
467 for (TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
468 Theory
* theory
= d_theoryTable
[theoryId
];
469 if (theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
470 Trace(tag
) << "--------------------------------------------" << endl
;
471 Trace(tag
) << "Assertions of " << theory
->getId() << ": " << endl
;
473 context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(),
476 for (unsigned i
= 0; it
!= it_end
; ++it
, ++i
)
478 if ((*it
).d_isPreregistered
)
480 Trace(tag
) << "[" << i
<< "]: ";
484 Trace(tag
) << "(" << i
<< "): ";
486 Trace(tag
) << (*it
).d_assertion
<< endl
;
490 if (d_logicInfo
.isSharingEnabled()) {
491 Trace(tag
) << "Shared terms of " << theory
->getId() << ": " << endl
;
492 context::CDList
<TNode
>::const_iterator it
= theory
->shared_terms_begin(), it_end
= theory
->shared_terms_end();
493 for (unsigned i
= 0; it
!= it_end
; ++ it
, ++i
) {
494 Trace(tag
) << "[" << i
<< "]: " << (*it
) << endl
;
502 void TheoryEngine::dumpAssertions(const char* tag
) {
503 if (Dump
.isOn(tag
)) {
504 Dump(tag
) << CommentCommand("Starting completeness check");
505 for (TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
506 Theory
* theory
= d_theoryTable
[theoryId
];
507 if (theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
508 Dump(tag
) << CommentCommand("Completeness check");
509 Dump(tag
) << PushCommand();
511 // Dump the shared terms
512 if (d_logicInfo
.isSharingEnabled()) {
513 Dump(tag
) << CommentCommand("Shared terms");
514 context::CDList
<TNode
>::const_iterator it
= theory
->shared_terms_begin(), it_end
= theory
->shared_terms_end();
515 for (unsigned i
= 0; it
!= it_end
; ++ it
, ++i
) {
518 Dump(tag
) << CommentCommand(ss
.str());
522 // Dump the assertions
523 Dump(tag
) << CommentCommand("Assertions");
524 context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(), it_end
= theory
->facts_end();
525 for (; it
!= it_end
; ++ it
) {
527 Node assertionNode
= (*it
).d_assertion
;
528 // Purify all the terms
530 if ((*it
).d_isPreregistered
)
532 Dump(tag
) << CommentCommand("Preregistered");
536 Dump(tag
) << CommentCommand("Shared assertion");
538 Dump(tag
) << AssertCommand(assertionNode
.toExpr());
540 Dump(tag
) << CheckSatCommand();
542 Dump(tag
) << PopCommand();
549 * Check all (currently-active) theories for conflicts.
550 * @param effort the effort level to use
552 void TheoryEngine::check(Theory::Effort effort
) {
555 // Reset the interrupt flag
556 d_interrupted
= false;
558 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
559 #undef CVC4_FOR_EACH_THEORY_STATEMENT
561 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
562 if (theory::TheoryTraits<THEORY>::hasCheck && d_logicInfo.isTheoryEnabled(THEORY)) { \
563 theoryOf(THEORY)->check(effort); \
564 if (d_inConflict) { \
565 Debug("conflict") << THEORY << " in conflict. " << std::endl; \
573 // Mark the output channel unused (if this is FULL_EFFORT, and nothing
574 // is done by the theories, no additional check will be needed)
575 d_outputChannelUsed
= false;
577 // Mark the lemmas flag (no lemmas added)
578 d_lemmasAdded
= false;
580 Debug("theory") << "TheoryEngine::check(" << effort
<< "): d_factsAsserted = " << (d_factsAsserted
? "true" : "false") << endl
;
582 // If in full effort, we have a fake new assertion just to jumpstart the checking
583 if (Theory::fullEffort(effort
)) {
584 d_factsAsserted
= true;
588 while (d_factsAsserted
&& !d_inConflict
&& !d_lemmasAdded
) {
590 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running check" << endl
;
592 Trace("theory::assertions") << endl
;
593 if (Trace
.isOn("theory::assertions")) {
594 printAssertions("theory::assertions");
597 if(Theory::fullEffort(effort
)) {
598 Trace("theory::assertions::fulleffort") << endl
;
599 if (Trace
.isOn("theory::assertions::fulleffort")) {
600 printAssertions("theory::assertions::fulleffort");
604 // Note that we've discharged all the facts
605 d_factsAsserted
= false;
608 CVC4_FOR_EACH_THEORY
;
610 if(Dump
.isOn("missed-t-conflicts")) {
611 Dump("missed-t-conflicts")
612 << CommentCommand("Completeness check for T-conflicts; expect sat")
613 << CheckSatCommand();
616 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running propagation after the initial check" << endl
;
618 // We are still satisfiable, propagate as much as possible
621 // We do combination if all has been processed and we are in fullcheck
622 if (Theory::fullEffort(effort
) && d_logicInfo
.isSharingEnabled() && !d_factsAsserted
&& !d_lemmasAdded
&& !d_inConflict
) {
623 // Do the combination
624 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running combination" << endl
;
626 if(d_logicInfo
.isQuantified()){
627 d_quantEngine
->notifyCombineTheories();
632 // Must consult quantifiers theory for last call to ensure sat, or otherwise add a lemma
633 if( Theory::fullEffort(effort
) && ! d_inConflict
&& ! needCheck() ) {
634 Trace("theory::assertions-model") << endl
;
635 if (Trace
.isOn("theory::assertions-model")) {
636 printAssertions("theory::assertions-model");
638 //checks for theories requiring the model go at last call
639 d_curr_model
->reset();
640 for (TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
641 if( theoryId
!=THEORY_QUANTIFIERS
){
642 Theory
* theory
= d_theoryTable
[theoryId
];
643 if (theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
644 if( theory
->needsCheckLastEffort() ){
645 if( !d_curr_model
->isBuilt() ){
646 if( !d_curr_model_builder
->buildModel(d_curr_model
) ){
650 theory
->check(Theory::EFFORT_LAST_CALL
);
657 if(d_logicInfo
.isQuantified()) {
658 // quantifiers engine must check at last call effort
659 d_quantEngine
->check(Theory::EFFORT_LAST_CALL
);
662 if (!d_inConflict
&& !needCheck())
664 // If d_eager_model_building is false, then we only mark that we
665 // are in "SAT mode". We build the model later only if the user asks
666 // for it via getBuiltModel.
668 if (d_eager_model_building
&& !d_curr_model
->isBuilt())
670 d_curr_model_builder
->buildModel(d_curr_model
);
675 Debug("theory") << "TheoryEngine::check(" << effort
<< "): done, we are " << (d_inConflict
? "unsat" : "sat") << (d_lemmasAdded
? " with new lemmas" : " with no new lemmas");
676 Debug("theory") << ", need check = " << (needCheck() ? "YES" : "NO") << endl
;
678 if( Theory::fullEffort(effort
) && !d_inConflict
&& !needCheck()) {
679 // case where we are about to answer SAT
680 if( d_masterEqualityEngine
!= NULL
){
681 AlwaysAssert(d_masterEqualityEngine
->consistent());
683 if (d_curr_model
->isBuilt())
685 // model construction should always succeed unless lemmas were added
686 AlwaysAssert(d_curr_model
->isBuiltSuccess());
687 if (options::produceModels())
689 // Do post-processing of model from the theories (used for THEORY_SEP
690 // to construct heap model)
691 postProcessModel(d_curr_model
);
692 // also call the model builder's post-process model
693 d_curr_model_builder
->postProcessModel(d_incomplete
.get(),
698 } catch(const theory::Interrupted
&) {
699 Trace("theory") << "TheoryEngine::check() => interrupted" << endl
;
701 // If fulleffort, check all theories
702 if(Dump
.isOn("theory::fullcheck") && Theory::fullEffort(effort
)) {
703 if (!d_inConflict
&& !needCheck()) {
704 dumpAssertions("theory::fullcheck");
709 void TheoryEngine::combineTheories() {
711 Trace("combineTheories") << "TheoryEngine::combineTheories()" << endl
;
713 TimerStat::CodeTimer
combineTheoriesTimer(d_combineTheoriesTime
);
715 // Care graph we'll be building
718 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
719 #undef CVC4_FOR_EACH_THEORY_STATEMENT
721 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
722 if (theory::TheoryTraits<THEORY>::isParametric && d_logicInfo.isTheoryEnabled(THEORY)) { \
723 theoryOf(THEORY)->getCareGraph(&careGraph); \
726 // Call on each parametric theory to give us its care graph
727 CVC4_FOR_EACH_THEORY
;
729 Trace("combineTheories") << "TheoryEngine::combineTheories(): care graph size = " << careGraph
.size() << endl
;
731 // Now add splitters for the ones we are interested in
732 CareGraph::const_iterator care_it
= careGraph
.begin();
733 CareGraph::const_iterator care_it_end
= careGraph
.end();
735 for (; care_it
!= care_it_end
; ++ care_it
) {
736 const CarePair
& carePair
= *care_it
;
738 Debug("combineTheories")
739 << "TheoryEngine::combineTheories(): checking " << carePair
.d_a
<< " = "
740 << carePair
.d_b
<< " from " << carePair
.d_theory
<< endl
;
742 Assert(d_sharedTerms
.isShared(carePair
.d_a
) || carePair
.d_a
.isConst());
743 Assert(d_sharedTerms
.isShared(carePair
.d_b
) || carePair
.d_b
.isConst());
745 // The equality in question (order for no repetition)
746 Node equality
= carePair
.d_a
.eqNode(carePair
.d_b
);
747 // EqualityStatus es = getEqualityStatus(carePair.d_a, carePair.d_b);
748 // Debug("combineTheories") << "TheoryEngine::combineTheories(): " <<
749 // (es == EQUALITY_TRUE_AND_PROPAGATED ? "EQUALITY_TRUE_AND_PROPAGATED" :
750 // es == EQUALITY_FALSE_AND_PROPAGATED ? "EQUALITY_FALSE_AND_PROPAGATED" :
751 // es == EQUALITY_TRUE ? "EQUALITY_TRUE" :
752 // es == EQUALITY_FALSE ? "EQUALITY_FALSE" :
753 // es == EQUALITY_TRUE_IN_MODEL ? "EQUALITY_TRUE_IN_MODEL" :
754 // es == EQUALITY_FALSE_IN_MODEL ? "EQUALITY_FALSE_IN_MODEL" :
755 // es == EQUALITY_UNKNOWN ? "EQUALITY_UNKNOWN" :
756 // "Unexpected case") << endl;
758 // We need to split on it
759 Debug("combineTheories") << "TheoryEngine::combineTheories(): requesting a split " << endl
;
761 lemma(equality
.orNode(equality
.notNode()),
768 // This code is supposed to force preference to follow what the theory models already have
769 // but it doesn't seem to make a big difference - need to explore more -Clark
771 // if (es == EQUALITY_TRUE || es == EQUALITY_TRUE_IN_MODEL) {
772 Node e
= ensureLiteral(equality
);
773 d_propEngine
->requirePhase(e
, true);
775 // else if (es == EQUALITY_FALSE_IN_MODEL) {
776 // Node e = ensureLiteral(equality);
777 // d_propEngine->requirePhase(e, false);
783 void TheoryEngine::propagate(Theory::Effort effort
) {
784 // Reset the interrupt flag
785 d_interrupted
= false;
787 // Definition of the statement that is to be run by every theory
788 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
789 #undef CVC4_FOR_EACH_THEORY_STATEMENT
791 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
792 if (theory::TheoryTraits<THEORY>::hasPropagate && d_logicInfo.isTheoryEnabled(THEORY)) { \
793 theoryOf(THEORY)->propagate(effort); \
796 // Reset the interrupt flag
797 d_interrupted
= false;
799 // Propagate for each theory using the statement above
800 CVC4_FOR_EACH_THEORY
;
802 if(Dump
.isOn("missed-t-propagations")) {
803 for(unsigned i
= 0; i
< d_possiblePropagations
.size(); ++i
) {
804 Node atom
= d_possiblePropagations
[i
];
806 if(d_propEngine
->hasValue(atom
, value
)) {
809 // Doesn't have a value, check it (and the negation)
810 if(d_hasPropagated
.find(atom
) == d_hasPropagated
.end()) {
811 Dump("missed-t-propagations")
812 << CommentCommand("Completeness check for T-propagations; expect invalid")
813 << EchoCommand(atom
.toString())
814 << QueryCommand(atom
.toExpr())
815 << EchoCommand(atom
.notNode().toString())
816 << QueryCommand(atom
.notNode().toExpr());
822 Node
TheoryEngine::getNextDecisionRequest()
824 return d_decManager
->getNextDecisionRequest();
827 bool TheoryEngine::properConflict(TNode conflict
) const {
829 if (conflict
.getKind() == kind::AND
) {
830 for (unsigned i
= 0; i
< conflict
.getNumChildren(); ++ i
) {
831 if (! getPropEngine()->hasValue(conflict
[i
], value
)) {
832 Debug("properConflict") << "Bad conflict is due to unassigned atom: "
833 << conflict
[i
] << endl
;
837 Debug("properConflict") << "Bad conflict is due to false atom: "
838 << conflict
[i
] << endl
;
841 if (conflict
[i
] != Rewriter::rewrite(conflict
[i
])) {
842 Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
843 << conflict
[i
] << " vs " << Rewriter::rewrite(conflict
[i
]) << endl
;
848 if (! getPropEngine()->hasValue(conflict
, value
)) {
849 Debug("properConflict") << "Bad conflict is due to unassigned atom: "
854 Debug("properConflict") << "Bad conflict is due to false atom: "
858 if (conflict
!= Rewriter::rewrite(conflict
)) {
859 Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
860 << conflict
<< " vs " << Rewriter::rewrite(conflict
) << endl
;
867 bool TheoryEngine::properPropagation(TNode lit
) const {
868 if(!getPropEngine()->isSatLiteral(lit
)) {
872 return !getPropEngine()->hasValue(lit
, b
);
875 bool TheoryEngine::properExplanation(TNode node
, TNode expl
) const {
876 // Explanation must be either a conjunction of true literals that have true SAT values already
877 // or a singled literal that has a true SAT value already.
878 if (expl
.getKind() == kind::AND
) {
879 for (unsigned i
= 0; i
< expl
.getNumChildren(); ++ i
) {
881 if (!d_propEngine
->hasValue(expl
[i
], value
) || !value
) {
887 return d_propEngine
->hasValue(expl
, value
) && value
;
892 bool TheoryEngine::collectModelInfo(theory::TheoryModel
* m
)
894 //have shared term engine collectModelInfo
895 // d_sharedTerms.collectModelInfo( m );
896 // Consult each active theory to get all relevant information
897 // concerning the model.
898 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
; ++theoryId
) {
899 if(d_logicInfo
.isTheoryEnabled(theoryId
)) {
900 Trace("model-builder") << " CollectModelInfo on theory: " << theoryId
<< endl
;
901 if (!d_theoryTable
[theoryId
]->collectModelInfo(m
))
907 Trace("model-builder") << " CollectModelInfo boolean variables" << std::endl
;
908 // Get the Boolean variables
909 vector
<TNode
> boolVars
;
910 d_propEngine
->getBooleanVariables(boolVars
);
911 vector
<TNode
>::iterator it
, iend
= boolVars
.end();
912 bool hasValue
, value
;
913 for (it
= boolVars
.begin(); it
!= iend
; ++it
) {
915 hasValue
= d_propEngine
->hasValue(var
, value
);
916 // TODO: Assert that hasValue is true?
918 Trace("model-builder-assertions")
919 << " has no value : " << var
<< std::endl
;
922 Trace("model-builder-assertions") << "(assert" << (value
? " " : " (not ") << var
<< (value
? ");" : "));") << endl
;
923 if (!m
->assertPredicate(var
, value
))
931 void TheoryEngine::postProcessModel( theory::TheoryModel
* m
){
932 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
; ++theoryId
) {
933 if(d_logicInfo
.isTheoryEnabled(theoryId
)) {
934 Trace("model-builder-debug") << " PostProcessModel on theory: " << theoryId
<< endl
;
935 d_theoryTable
[theoryId
]->postProcessModel( m
);
940 TheoryModel
* TheoryEngine::getModel() {
944 TheoryModel
* TheoryEngine::getBuiltModel()
946 if (!d_curr_model
->isBuilt())
948 // If this method was called, we should be in SAT mode, and produceModels
950 AlwaysAssert(options::produceModels());
953 // not available, perhaps due to interuption.
956 // must build model at this point
957 d_curr_model_builder
->buildModel(d_curr_model
);
962 bool TheoryEngine::getSynthSolutions(
963 std::map
<Node
, std::map
<Node
, Node
>>& sol_map
)
967 return d_quantEngine
->getSynthSolutions(sol_map
);
969 // we are not in a quantified logic, there is no synthesis solution
973 bool TheoryEngine::presolve() {
974 // Reset the interrupt flag
975 d_interrupted
= false;
977 // Reset the decision manager. This clears its decision strategies that are
978 // no longer valid in this user context.
979 d_decManager
->presolve();
982 // Definition of the statement that is to be run by every theory
983 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
984 #undef CVC4_FOR_EACH_THEORY_STATEMENT
986 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
987 if (theory::TheoryTraits<THEORY>::hasPresolve) { \
988 theoryOf(THEORY)->presolve(); \
994 // Presolve for each theory using the statement above
995 CVC4_FOR_EACH_THEORY
;
996 } catch(const theory::Interrupted
&) {
997 Trace("theory") << "TheoryEngine::presolve() => interrupted" << endl
;
999 // return whether we have a conflict
1001 }/* TheoryEngine::presolve() */
1003 void TheoryEngine::postsolve() {
1004 // no longer in SAT mode
1005 d_inSatMode
= false;
1006 // Reset the interrupt flag
1007 d_interrupted
= false;
1008 bool CVC4_UNUSED wasInConflict
= d_inConflict
;
1011 // Definition of the statement that is to be run by every theory
1012 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
1013 #undef CVC4_FOR_EACH_THEORY_STATEMENT
1015 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
1016 if (theory::TheoryTraits<THEORY>::hasPostsolve) \
1018 theoryOf(THEORY)->postsolve(); \
1019 Assert(!d_inConflict || wasInConflict) \
1020 << "conflict raised during postsolve()"; \
1023 // Postsolve for each theory using the statement above
1024 CVC4_FOR_EACH_THEORY
;
1025 } catch(const theory::Interrupted
&) {
1026 Trace("theory") << "TheoryEngine::postsolve() => interrupted" << endl
;
1028 }/* TheoryEngine::postsolve() */
1031 void TheoryEngine::notifyRestart() {
1032 // Reset the interrupt flag
1033 d_interrupted
= false;
1035 // Definition of the statement that is to be run by every theory
1036 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
1037 #undef CVC4_FOR_EACH_THEORY_STATEMENT
1039 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
1040 if (theory::TheoryTraits<THEORY>::hasNotifyRestart && d_logicInfo.isTheoryEnabled(THEORY)) { \
1041 theoryOf(THEORY)->notifyRestart(); \
1044 // notify each theory using the statement above
1045 CVC4_FOR_EACH_THEORY
;
1048 void TheoryEngine::ppStaticLearn(TNode in
, NodeBuilder
<>& learned
) {
1049 // Reset the interrupt flag
1050 d_interrupted
= false;
1052 // Definition of the statement that is to be run by every theory
1053 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
1054 #undef CVC4_FOR_EACH_THEORY_STATEMENT
1056 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
1057 if (theory::TheoryTraits<THEORY>::hasPpStaticLearn) { \
1058 theoryOf(THEORY)->ppStaticLearn(in, learned); \
1061 // static learning for each theory using the statement above
1062 CVC4_FOR_EACH_THEORY
;
1065 void TheoryEngine::shutdown() {
1066 // Set this first; if a Theory shutdown() throws an exception,
1067 // at least the destruction of the TheoryEngine won't confound
1069 d_hasShutDown
= true;
1071 // Shutdown all the theories
1072 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
; ++theoryId
) {
1073 if(d_theoryTable
[theoryId
]) {
1074 theoryOf(theoryId
)->shutdown();
1081 theory::Theory::PPAssertStatus
TheoryEngine::solve(TNode literal
, SubstitutionMap
& substitutionOut
) {
1082 // Reset the interrupt flag
1083 d_interrupted
= false;
1085 TNode atom
= literal
.getKind() == kind::NOT
? literal
[0] : literal
;
1086 Trace("theory::solve") << "TheoryEngine::solve(" << literal
<< "): solving with " << theoryOf(atom
)->getId() << endl
;
1088 if(! d_logicInfo
.isTheoryEnabled(Theory::theoryOf(atom
)) &&
1089 Theory::theoryOf(atom
) != THEORY_SAT_SOLVER
) {
1091 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
1092 << ", which doesn't include " << Theory::theoryOf(atom
)
1093 << ", but got a preprocessing-time fact for that theory." << endl
1094 << "The fact:" << endl
1096 throw LogicException(ss
.str());
1099 Theory::PPAssertStatus solveStatus
= theoryOf(atom
)->ppAssert(literal
, substitutionOut
);
1100 Trace("theory::solve") << "TheoryEngine::solve(" << literal
<< ") => " << solveStatus
<< endl
;
1104 // Recursively traverse a term and call the theory rewriter on its sub-terms
1105 Node
TheoryEngine::ppTheoryRewrite(TNode term
) {
1106 NodeMap::iterator find
= d_ppCache
.find(term
);
1107 if (find
!= d_ppCache
.end()) {
1108 return (*find
).second
;
1110 unsigned nc
= term
.getNumChildren();
1112 return theoryOf(term
)->ppRewrite(term
);
1114 Trace("theory-pp") << "ppTheoryRewrite { " << term
<< endl
;
1117 // do not rewrite inside quantifiers
1118 if (term
.isClosure())
1120 newTerm
= Rewriter::rewrite(term
);
1124 NodeBuilder
<> newNode(term
.getKind());
1125 if (term
.getMetaKind() == kind::metakind::PARAMETERIZED
) {
1126 newNode
<< term
.getOperator();
1129 for (i
= 0; i
< nc
; ++i
) {
1130 newNode
<< ppTheoryRewrite(term
[i
]);
1132 newTerm
= Rewriter::rewrite(Node(newNode
));
1134 Node newTerm2
= theoryOf(newTerm
)->ppRewrite(newTerm
);
1135 if (newTerm
!= newTerm2
) {
1136 newTerm
= ppTheoryRewrite(Rewriter::rewrite(newTerm2
));
1138 d_ppCache
[term
] = newTerm
;
1139 Trace("theory-pp")<< "ppTheoryRewrite returning " << newTerm
<< "}" << endl
;
1144 void TheoryEngine::preprocessStart()
1150 struct preprocess_stack_element
{
1152 bool children_added
;
1153 preprocess_stack_element(TNode n
) : node(n
), children_added(false) {}
1154 };/* struct preprocess_stack_element */
1157 Node
TheoryEngine::preprocess(TNode assertion
) {
1159 Trace("theory::preprocess") << "TheoryEngine::preprocess(" << assertion
<< ")" << endl
;
1162 // Do a topological sort of the subexpressions and substitute them
1163 vector
<preprocess_stack_element
> toVisit
;
1164 toVisit
.push_back(assertion
);
1166 while (!toVisit
.empty())
1168 // The current node we are processing
1169 preprocess_stack_element
& stackHead
= toVisit
.back();
1170 TNode current
= stackHead
.node
;
1172 Debug("theory::internal") << "TheoryEngine::preprocess(" << assertion
<< "): processing " << current
<< endl
;
1174 // If node already in the cache we're done, pop from the stack
1175 NodeMap::iterator find
= d_ppCache
.find(current
);
1176 if (find
!= d_ppCache
.end()) {
1181 if(! d_logicInfo
.isTheoryEnabled(Theory::theoryOf(current
)) &&
1182 Theory::theoryOf(current
) != THEORY_SAT_SOLVER
) {
1184 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
1185 << ", which doesn't include " << Theory::theoryOf(current
)
1186 << ", but got a preprocessing-time fact for that theory." << endl
1187 << "The fact:" << endl
1189 throw LogicException(ss
.str());
1192 // If this is an atom, we preprocess its terms with the theory ppRewriter
1193 if (Theory::theoryOf(current
) != THEORY_BOOL
) {
1194 Node ppRewritten
= ppTheoryRewrite(current
);
1195 d_ppCache
[current
] = ppRewritten
;
1196 Assert(Rewriter::rewrite(d_ppCache
[current
]) == d_ppCache
[current
]);
1200 // Not yet substituted, so process
1201 if (stackHead
.children_added
) {
1202 // Children have been processed, so substitute
1203 NodeBuilder
<> builder(current
.getKind());
1204 if (current
.getMetaKind() == kind::metakind::PARAMETERIZED
) {
1205 builder
<< current
.getOperator();
1207 for (unsigned i
= 0; i
< current
.getNumChildren(); ++ i
) {
1208 Assert(d_ppCache
.find(current
[i
]) != d_ppCache
.end());
1209 builder
<< d_ppCache
[current
[i
]];
1211 // Mark the substitution and continue
1212 Node result
= builder
;
1213 if (result
!= current
) {
1214 result
= Rewriter::rewrite(result
);
1216 Debug("theory::internal") << "TheoryEngine::preprocess(" << assertion
<< "): setting " << current
<< " -> " << result
<< endl
;
1217 d_ppCache
[current
] = result
;
1220 // Mark that we have added the children if any
1221 if (current
.getNumChildren() > 0) {
1222 stackHead
.children_added
= true;
1223 // We need to add the children
1224 for(TNode::iterator child_it
= current
.begin(); child_it
!= current
.end(); ++ child_it
) {
1225 TNode childNode
= *child_it
;
1226 NodeMap::iterator childFind
= d_ppCache
.find(childNode
);
1227 if (childFind
== d_ppCache
.end()) {
1228 toVisit
.push_back(childNode
);
1232 // No children, so we're done
1233 Debug("substitution::internal") << "SubstitutionMap::internalSubstitute(" << assertion
<< "): setting " << current
<< " -> " << current
<< endl
;
1234 d_ppCache
[current
] = current
;
1240 // Return the substituted version
1241 return d_ppCache
[assertion
];
1244 void TheoryEngine::notifyPreprocessedAssertions(
1245 const std::vector
<Node
>& assertions
) {
1246 // call all the theories
1247 for (TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
;
1249 if (d_theoryTable
[theoryId
]) {
1250 theoryOf(theoryId
)->ppNotifyAssertions(assertions
);
1255 bool TheoryEngine::markPropagation(TNode assertion
, TNode originalAssertion
, theory::TheoryId toTheoryId
, theory::TheoryId fromTheoryId
) {
1257 // What and where we are asserting
1258 NodeTheoryPair
toAssert(assertion
, toTheoryId
, d_propagationMapTimestamp
);
1259 // What and where it came from
1260 NodeTheoryPair
toExplain(originalAssertion
, fromTheoryId
, d_propagationMapTimestamp
);
1262 // See if the theory already got this literal
1263 PropagationMap::const_iterator find
= d_propagationMap
.find(toAssert
);
1264 if (find
!= d_propagationMap
.end()) {
1265 // The theory already knows this
1266 Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): already there" << endl
;
1270 Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): marking [" << d_propagationMapTimestamp
<< "] " << assertion
<< ", " << toTheoryId
<< " from " << originalAssertion
<< ", " << fromTheoryId
<< endl
;
1272 // Mark the propagation
1273 d_propagationMap
[toAssert
] = toExplain
;
1274 d_propagationMapTimestamp
= d_propagationMapTimestamp
+ 1;
1280 void TheoryEngine::assertToTheory(TNode assertion
, TNode originalAssertion
, theory::TheoryId toTheoryId
, theory::TheoryId fromTheoryId
) {
1282 Trace("theory::assertToTheory") << "TheoryEngine::assertToTheory(" << assertion
<< ", " << originalAssertion
<< "," << toTheoryId
<< ", " << fromTheoryId
<< ")" << endl
;
1284 Assert(toTheoryId
!= fromTheoryId
);
1285 if(toTheoryId
!= THEORY_SAT_SOLVER
&&
1286 ! d_logicInfo
.isTheoryEnabled(toTheoryId
)) {
1288 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
1289 << ", which doesn't include " << toTheoryId
1290 << ", but got an asserted fact to that theory." << endl
1291 << "The fact:" << endl
1293 throw LogicException(ss
.str());
1300 // If sharing is disabled, things are easy
1301 if (!d_logicInfo
.isSharingEnabled()) {
1302 Assert(assertion
== originalAssertion
);
1303 if (fromTheoryId
== THEORY_SAT_SOLVER
) {
1304 // Send to the apropriate theory
1305 theory::Theory
* toTheory
= theoryOf(toTheoryId
);
1306 // We assert it, and we know it's preregistereed
1307 toTheory
->assertFact(assertion
, true);
1308 // Mark that we have more information
1309 d_factsAsserted
= true;
1311 Assert(toTheoryId
== THEORY_SAT_SOLVER
);
1312 // Check for propositional conflict
1314 if (d_propEngine
->hasValue(assertion
, value
)) {
1316 Trace("theory::propagate") << "TheoryEngine::assertToTheory(" << assertion
<< ", " << toTheoryId
<< ", " << fromTheoryId
<< "): conflict (no sharing)" << endl
;
1317 Trace("dtview::conflict")
1318 << ":THEORY-CONFLICT: " << assertion
<< std::endl
;
1319 d_inConflict
= true;
1324 d_propagatedLiterals
.push_back(assertion
);
1329 // Polarity of the assertion
1330 bool polarity
= assertion
.getKind() != kind::NOT
;
1332 // Atom of the assertion
1333 TNode atom
= polarity
? assertion
: assertion
[0];
1335 // If sending to the shared terms database, it's also simple
1336 if (toTheoryId
== THEORY_BUILTIN
) {
1337 Assert(atom
.getKind() == kind::EQUAL
)
1338 << "atom should be an EQUALity, not `" << atom
<< "'";
1339 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1340 d_sharedTerms
.assertEquality(atom
, polarity
, assertion
);
1345 // Things from the SAT solver are already normalized, so they go
1346 // directly to the apropriate theory
1347 if (fromTheoryId
== THEORY_SAT_SOLVER
) {
1348 // We know that this is normalized, so just send it off to the theory
1349 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1350 // Is it preregistered
1351 bool preregistered
= d_propEngine
->isSatLiteral(assertion
) && Theory::theoryOf(assertion
) == toTheoryId
;
1353 theoryOf(toTheoryId
)->assertFact(assertion
, preregistered
);
1354 // Mark that we have more information
1355 d_factsAsserted
= true;
1360 // Propagations to the SAT solver are just enqueued for pickup by
1361 // the SAT solver later
1362 if (toTheoryId
== THEORY_SAT_SOLVER
) {
1363 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1364 // Enqueue for propagation to the SAT solver
1365 d_propagatedLiterals
.push_back(assertion
);
1366 // Check for propositional conflicts
1368 if (d_propEngine
->hasValue(assertion
, value
) && !value
) {
1369 Trace("theory::propagate")
1370 << "TheoryEngine::assertToTheory(" << assertion
<< ", "
1371 << toTheoryId
<< ", " << fromTheoryId
<< "): conflict (sharing)"
1373 Trace("dtview::conflict")
1374 << ":THEORY-CONFLICT: " << assertion
<< std::endl
;
1375 d_inConflict
= true;
1381 Assert(atom
.getKind() == kind::EQUAL
);
1384 Node normalizedLiteral
= Rewriter::rewrite(assertion
);
1386 // See if it rewrites false directly -> conflict
1387 if (normalizedLiteral
.isConst()) {
1388 if (!normalizedLiteral
.getConst
<bool>()) {
1389 // Mark the propagation for explanations
1390 if (markPropagation(normalizedLiteral
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1391 // Get the explanation (conflict will figure out where it came from)
1392 conflict(normalizedLiteral
, toTheoryId
);
1400 // Try and assert (note that we assert the non-normalized one)
1401 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1402 // Check if has been pre-registered with the theory
1403 bool preregistered
= d_propEngine
->isSatLiteral(assertion
) && Theory::theoryOf(assertion
) == toTheoryId
;
1405 theoryOf(toTheoryId
)->assertFact(assertion
, preregistered
);
1406 d_factsAsserted
= true;
1412 void TheoryEngine::assertFact(TNode literal
)
1414 Trace("theory") << "TheoryEngine::assertFact(" << literal
<< ")" << endl
;
1418 // If we're in conflict, nothing to do
1424 bool polarity
= literal
.getKind() != kind::NOT
;
1425 TNode atom
= polarity
? literal
: literal
[0];
1427 if (d_logicInfo
.isSharingEnabled()) {
1429 // If any shared terms, it's time to do sharing work
1430 if (d_sharedTerms
.hasSharedTerms(atom
)) {
1431 // Notify the theories the shared terms
1432 SharedTermsDatabase::shared_terms_iterator it
= d_sharedTerms
.begin(atom
);
1433 SharedTermsDatabase::shared_terms_iterator it_end
= d_sharedTerms
.end(atom
);
1434 for (; it
!= it_end
; ++ it
) {
1436 Theory::Set theories
= d_sharedTerms
.getTheoriesToNotify(atom
, term
);
1437 for (TheoryId id
= THEORY_FIRST
; id
!= THEORY_LAST
; ++ id
) {
1438 if (Theory::setContains(id
, theories
)) {
1439 theoryOf(id
)->addSharedTermInternal(term
);
1442 d_sharedTerms
.markNotified(term
, theories
);
1446 // If it's an equality, assert it to the shared term manager, even though the terms are not
1447 // yet shared. As the terms become shared later, the shared terms manager will then add them
1448 // to the assert the equality to the interested theories
1449 if (atom
.getKind() == kind::EQUAL
) {
1450 // Assert it to the the owning theory
1451 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1452 // Shared terms manager will assert to interested theories directly, as the terms become shared
1453 assertToTheory(literal
, literal
, /* to */ THEORY_BUILTIN
, /* from */ THEORY_SAT_SOLVER
);
1455 // Now, let's check for any atom triggers from lemmas
1456 AtomRequests::atom_iterator it
= d_atomRequests
.getAtomIterator(atom
);
1457 while (!it
.done()) {
1458 const AtomRequests::Request
& request
= it
.get();
1460 polarity
? (Node
)request
.d_atom
: request
.d_atom
.notNode();
1461 Debug("theory::atoms") << "TheoryEngine::assertFact(" << literal
<< "): sending requested " << toAssert
<< endl
;
1463 toAssert
, literal
, request
.d_toTheory
, THEORY_SAT_SOLVER
);
1468 // Not an equality, just assert to the appropriate theory
1469 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1472 // Assert the fact to the appropriate theory directly
1473 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1477 bool TheoryEngine::propagate(TNode literal
, theory::TheoryId theory
) {
1479 Debug("theory::propagate") << "TheoryEngine::propagate(" << literal
<< ", " << theory
<< ")" << endl
;
1481 Trace("dtview::prop") << std::string(d_context
->getLevel(), ' ')
1482 << ":THEORY-PROP: " << literal
<< endl
;
1486 if(Dump
.isOn("t-propagations")) {
1487 Dump("t-propagations") << CommentCommand("negation of theory propagation: expect valid")
1488 << QueryCommand(literal
.toExpr());
1490 if(Dump
.isOn("missed-t-propagations")) {
1491 d_hasPropagated
.insert(literal
);
1495 bool polarity
= literal
.getKind() != kind::NOT
;
1496 TNode atom
= polarity
? literal
: literal
[0];
1498 if (d_logicInfo
.isSharingEnabled() && atom
.getKind() == kind::EQUAL
) {
1499 if (d_propEngine
->isSatLiteral(literal
)) {
1500 // We propagate SAT literals to SAT
1501 assertToTheory(literal
, literal
, /* to */ THEORY_SAT_SOLVER
, /* from */ theory
);
1503 if (theory
!= THEORY_BUILTIN
) {
1504 // Assert to the shared terms database
1505 assertToTheory(literal
, literal
, /* to */ THEORY_BUILTIN
, /* from */ theory
);
1508 // We could be propagating a unit-clause lemma. In this case, we need to provide a
1510 // TODO: Consider putting this someplace else? This is the only refence to the proof
1511 // manager in this class.
1514 LemmaProofRecipe proofRecipe
;
1515 proofRecipe
.addBaseAssertion(literal
);
1518 LemmaProofRecipe::ProofStep
proofStep(theory
, emptyNode
);
1519 proofStep
.addAssertion(literal
);
1520 proofRecipe
.addStep(proofStep
);
1522 ProofManager::getCnfProof()->setProofRecipe(&proofRecipe
);
1525 // Just send off to the SAT solver
1526 Assert(d_propEngine
->isSatLiteral(literal
));
1527 assertToTheory(literal
, literal
, /* to */ THEORY_SAT_SOLVER
, /* from */ theory
);
1530 return !d_inConflict
;
1533 const LogicInfo
& TheoryEngine::getLogicInfo() const { return d_logicInfo
; }
1535 theory::EqualityStatus
TheoryEngine::getEqualityStatus(TNode a
, TNode b
) {
1536 Assert(a
.getType().isComparableTo(b
.getType()));
1537 if (d_sharedTerms
.isShared(a
) && d_sharedTerms
.isShared(b
)) {
1538 if (d_sharedTerms
.areEqual(a
,b
)) {
1539 return EQUALITY_TRUE_AND_PROPAGATED
;
1541 else if (d_sharedTerms
.areDisequal(a
,b
)) {
1542 return EQUALITY_FALSE_AND_PROPAGATED
;
1545 return theoryOf(Theory::theoryOf(a
.getType()))->getEqualityStatus(a
, b
);
1548 Node
TheoryEngine::getModelValue(TNode var
) {
1551 // the model value of a constant must be itself
1554 Assert(d_sharedTerms
.isShared(var
));
1555 return theoryOf(Theory::theoryOf(var
.getType()))->getModelValue(var
);
1559 Node
TheoryEngine::ensureLiteral(TNode n
) {
1560 Debug("ensureLiteral") << "rewriting: " << n
<< std::endl
;
1561 Node rewritten
= Rewriter::rewrite(n
);
1562 Debug("ensureLiteral") << " got: " << rewritten
<< std::endl
;
1563 Node preprocessed
= preprocess(rewritten
);
1564 Debug("ensureLiteral") << "preprocessed: " << preprocessed
<< std::endl
;
1565 d_propEngine
->ensureLiteral(preprocessed
);
1566 return preprocessed
;
1570 void TheoryEngine::printInstantiations( std::ostream
& out
) {
1571 if( d_quantEngine
){
1572 d_quantEngine
->printInstantiations( out
);
1574 out
<< "Internal error : instantiations not available when quantifiers are not present." << std::endl
;
1579 void TheoryEngine::printSynthSolution( std::ostream
& out
) {
1580 if( d_quantEngine
){
1581 d_quantEngine
->printSynthSolution( out
);
1583 out
<< "Internal error : synth solution not available when quantifiers are not present." << std::endl
;
1588 void TheoryEngine::getInstantiatedQuantifiedFormulas( std::vector
< Node
>& qs
) {
1589 if( d_quantEngine
){
1590 d_quantEngine
->getInstantiatedQuantifiedFormulas( qs
);
1596 void TheoryEngine::getInstantiations( Node q
, std::vector
< Node
>& insts
) {
1597 if( d_quantEngine
){
1598 d_quantEngine
->getInstantiations( q
, insts
);
1604 void TheoryEngine::getInstantiationTermVectors( Node q
, std::vector
< std::vector
< Node
> >& tvecs
) {
1605 if( d_quantEngine
){
1606 d_quantEngine
->getInstantiationTermVectors( q
, tvecs
);
1612 void TheoryEngine::getInstantiations( std::map
< Node
, std::vector
< Node
> >& insts
) {
1613 if( d_quantEngine
){
1614 d_quantEngine
->getInstantiations( insts
);
1620 void TheoryEngine::getInstantiationTermVectors( std::map
< Node
, std::vector
< std::vector
< Node
> > >& insts
) {
1621 if( d_quantEngine
){
1622 d_quantEngine
->getInstantiationTermVectors( insts
);
1628 Node
TheoryEngine::getInstantiatedConjunction( Node q
) {
1629 if( d_quantEngine
){
1630 return d_quantEngine
->getInstantiatedConjunction( q
);
1633 return Node::null();
1638 static Node
mkExplanation(const std::vector
<NodeTheoryPair
>& explanation
) {
1640 std::set
<TNode
> all
;
1641 for (unsigned i
= 0; i
< explanation
.size(); ++ i
) {
1642 Assert(explanation
[i
].d_theory
== THEORY_SAT_SOLVER
);
1643 all
.insert(explanation
[i
].d_node
);
1646 if (all
.size() == 0) {
1647 // Normalize to true
1648 return NodeManager::currentNM()->mkConst
<bool>(true);
1651 if (all
.size() == 1) {
1652 // All the same, or just one
1653 return explanation
[0].d_node
;
1656 NodeBuilder
<> conjunction(kind::AND
);
1657 std::set
<TNode
>::const_iterator it
= all
.begin();
1658 std::set
<TNode
>::const_iterator it_end
= all
.end();
1659 while (it
!= it_end
) {
1667 Node
TheoryEngine::getExplanationAndRecipe(TNode node
, LemmaProofRecipe
* proofRecipe
) {
1668 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
<< "): current propagation index = " << d_propagationMapTimestamp
<< endl
;
1670 bool polarity
= node
.getKind() != kind::NOT
;
1671 TNode atom
= polarity
? node
: node
[0];
1673 // If we're not in shared mode, explanations are simple
1674 if (!d_logicInfo
.isSharingEnabled()) {
1675 Debug("theory::explain") << "TheoryEngine::getExplanation: sharing is NOT enabled. "
1676 << " Responsible theory is: "
1677 << theoryOf(atom
)->getId() << std::endl
;
1679 Node explanation
= theoryOf(atom
)->explain(node
);
1680 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
<< ") => " << explanation
<< endl
;
1684 LemmaProofRecipe::ProofStep
proofStep(theoryOf(atom
)->getId(), emptyNode
);
1685 proofStep
.addAssertion(node
);
1686 proofRecipe
->addBaseAssertion(node
);
1688 if (explanation
.getKind() == kind::AND
) {
1689 // If the explanation is a conjunction, the recipe for the corresponding lemma is
1690 // the negation of its conjuncts.
1691 Node flat
= flattenAnd(explanation
);
1692 for (unsigned i
= 0; i
< flat
.getNumChildren(); ++i
) {
1693 if (flat
[i
].isConst() && flat
[i
].getConst
<bool>()) {
1697 if (flat
[i
].getKind() == kind::NOT
&&
1698 flat
[i
][0].isConst() && !flat
[i
][0].getConst
<bool>()) {
1702 Debug("theory::explain") << "TheoryEngine::getExplanationAndRecipe: adding recipe assertion: "
1703 << flat
[i
].negate() << std::endl
;
1704 proofStep
.addAssertion(flat
[i
].negate());
1705 proofRecipe
->addBaseAssertion(flat
[i
].negate());
1708 // The recipe for proving it is by negating it. "True" is not an acceptable reason.
1709 if (!((explanation
.isConst() && explanation
.getConst
<bool>()) ||
1710 (explanation
.getKind() == kind::NOT
&&
1711 explanation
[0].isConst() && !explanation
[0].getConst
<bool>()))) {
1712 proofStep
.addAssertion(explanation
.negate());
1713 proofRecipe
->addBaseAssertion(explanation
.negate());
1717 proofRecipe
->addStep(proofStep
);
1724 Debug("theory::explain") << "TheoryEngine::getExplanation: sharing IS enabled" << std::endl
;
1726 // Initial thing to explain
1727 NodeTheoryPair
toExplain(node
, THEORY_SAT_SOLVER
, d_propagationMapTimestamp
);
1728 Assert(d_propagationMap
.find(toExplain
) != d_propagationMap
.end());
1730 NodeTheoryPair nodeExplainerPair
= d_propagationMap
[toExplain
];
1731 Debug("theory::explain")
1732 << "TheoryEngine::getExplanation: explainer for node "
1733 << nodeExplainerPair
.d_node
1734 << " is theory: " << nodeExplainerPair
.d_theory
<< std::endl
;
1735 TheoryId explainer
= nodeExplainerPair
.d_theory
;
1737 // Create the workplace for explanations
1738 std::vector
<NodeTheoryPair
> explanationVector
;
1739 explanationVector
.push_back(d_propagationMap
[toExplain
]);
1740 // Process the explanation
1743 LemmaProofRecipe::ProofStep
proofStep(explainer
, emptyNode
);
1744 proofStep
.addAssertion(node
);
1745 proofRecipe
->addStep(proofStep
);
1746 proofRecipe
->addBaseAssertion(node
);
1749 getExplanation(explanationVector
, proofRecipe
);
1750 Node explanation
= mkExplanation(explanationVector
);
1752 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
<< ") => " << explanation
<< endl
;
1757 Node
TheoryEngine::getExplanation(TNode node
) {
1758 LemmaProofRecipe
*dontCareRecipe
= NULL
;
1759 return getExplanationAndRecipe(node
, dontCareRecipe
);
1762 struct AtomsCollect
{
1764 std::vector
<TNode
> d_atoms
;
1765 std::unordered_set
<TNode
, TNodeHashFunction
> d_visited
;
1769 typedef void return_type
;
1771 bool alreadyVisited(TNode current
, TNode parent
) {
1772 // Check if already visited
1773 if (d_visited
.find(current
) != d_visited
.end()) return true;
1774 // Don't visit non-boolean
1775 if (!current
.getType().isBoolean()) return true;
1780 void visit(TNode current
, TNode parent
) {
1781 if (Theory::theoryOf(current
) != theory::THEORY_BOOL
) {
1782 d_atoms
.push_back(current
);
1784 d_visited
.insert(current
);
1787 void start(TNode node
) {}
1788 void done(TNode node
) {}
1790 std::vector
<TNode
> getAtoms() const {
1795 void TheoryEngine::ensureLemmaAtoms(const std::vector
<TNode
>& atoms
, theory::TheoryId atomsTo
) {
1796 for (unsigned i
= 0; i
< atoms
.size(); ++ i
) {
1798 // Non-equality atoms are either owned by theory or they don't make sense
1799 if (atoms
[i
].getKind() != kind::EQUAL
) {
1805 // Simple normalization to not repeat stuff
1806 if (eq
[0] > eq
[1]) {
1807 eq
= eq
[1].eqNode(eq
[0]);
1810 // Rewrite the equality
1811 Node eqNormalized
= Rewriter::rewrite(atoms
[i
]);
1813 Debug("theory::atoms") << "TheoryEngine::ensureLemmaAtoms(): " << eq
<< " with nf " << eqNormalized
<< endl
;
1815 // If the equality is a boolean constant, we send immediately
1816 if (eqNormalized
.isConst()) {
1817 if (eqNormalized
.getConst
<bool>()) {
1818 assertToTheory(eq
, eqNormalized
, /** to */ atomsTo
, /** Sat solver */ theory::THEORY_SAT_SOLVER
);
1820 assertToTheory(eq
.notNode(), eqNormalized
.notNode(), /** to */ atomsTo
, /** Sat solver */ theory::THEORY_SAT_SOLVER
);
1823 }else if( eqNormalized
.getKind() != kind::EQUAL
){
1824 Assert(eqNormalized
.getKind() == kind::BOOLEAN_TERM_VARIABLE
1825 || (eqNormalized
.getKind() == kind::NOT
1826 && eqNormalized
[0].getKind() == kind::BOOLEAN_TERM_VARIABLE
));
1827 // this happens for Boolean term equalities V = true that are rewritten to V, we should skip
1828 // TODO : revisit this
1832 // If the normalization did the just flips, keep the flip
1833 if (eqNormalized
[0] == eq
[1] && eqNormalized
[1] == eq
[0]) {
1837 // Check if the equality is already known by the sat solver
1838 if (d_propEngine
->isSatLiteral(eqNormalized
)) {
1840 if (d_propEngine
->hasValue(eqNormalized
, value
)) {
1842 assertToTheory(eq
, eqNormalized
, atomsTo
, theory::THEORY_SAT_SOLVER
);
1845 assertToTheory(eq
.notNode(), eqNormalized
.notNode(), atomsTo
, theory::THEORY_SAT_SOLVER
);
1851 // If the theory is asking about a different form, or the form is ok but if will go to a different theory
1852 // then we must figure it out
1853 if (eqNormalized
!= eq
|| Theory::theoryOf(eq
) != atomsTo
) {
1854 // If you get eqNormalized, send atoms[i] to atomsTo
1855 d_atomRequests
.add(eqNormalized
, eq
, atomsTo
);
1860 theory::LemmaStatus
TheoryEngine::lemma(TNode node
,
1865 theory::TheoryId atomsTo
) {
1866 // For resource-limiting (also does a time check).
1869 // Do we need to check atoms
1870 if (atomsTo
!= theory::THEORY_LAST
) {
1871 Debug("theory::atoms") << "TheoryEngine::lemma(" << node
<< ", " << atomsTo
<< ")" << endl
;
1872 AtomsCollect collectAtoms
;
1873 NodeVisitor
<AtomsCollect
>::run(collectAtoms
, node
);
1874 ensureLemmaAtoms(collectAtoms
.getAtoms(), atomsTo
);
1877 if(Dump
.isOn("t-lemmas")) {
1882 Dump("t-lemmas") << CommentCommand("theory lemma: expect valid")
1883 << CheckSatCommand(n
.toExpr());
1886 AssertionPipeline additionalLemmas
;
1888 // Run theory preprocessing, maybe
1889 Node ppNode
= preprocess
? this->preprocess(node
) : Node(node
);
1892 Debug("ite") << "Remove ITE from " << ppNode
<< std::endl
;
1893 additionalLemmas
.push_back(ppNode
);
1894 additionalLemmas
.updateRealAssertionsEnd();
1895 d_tform_remover
.run(additionalLemmas
.ref(),
1896 additionalLemmas
.getIteSkolemMap());
1897 Debug("ite") << "..done " << additionalLemmas
[0] << std::endl
;
1898 additionalLemmas
.replace(0, theory::Rewriter::rewrite(additionalLemmas
[0]));
1900 if(Debug
.isOn("lemma-ites")) {
1901 Debug("lemma-ites") << "removed ITEs from lemma: " << ppNode
<< endl
;
1902 Debug("lemma-ites") << " + now have the following "
1903 << additionalLemmas
.size() << " lemma(s):" << endl
;
1904 for(std::vector
<Node
>::const_iterator i
= additionalLemmas
.begin();
1905 i
!= additionalLemmas
.end();
1907 Debug("lemma-ites") << " + " << *i
<< endl
;
1909 Debug("lemma-ites") << endl
;
1912 // assert to prop engine
1913 d_propEngine
->assertLemma(additionalLemmas
[0], negated
, removable
, rule
, node
);
1914 for (unsigned i
= 1; i
< additionalLemmas
.size(); ++ i
) {
1915 additionalLemmas
.replace(i
, theory::Rewriter::rewrite(additionalLemmas
[i
]));
1916 d_propEngine
->assertLemma(additionalLemmas
[i
], false, removable
, rule
, node
);
1919 // WARNING: Below this point don't assume additionalLemmas[0] to be not negated.
1921 additionalLemmas
.replace(0, additionalLemmas
[0].notNode());
1925 // assert to decision engine
1928 d_propEngine
->addAssertionsToDecisionEngine(additionalLemmas
);
1931 // Mark that we added some lemmas
1932 d_lemmasAdded
= true;
1934 // Lemma analysis isn't online yet; this lemma may only live for this
1936 return theory::LemmaStatus(additionalLemmas
[0], d_userContext
->getLevel());
1939 void TheoryEngine::conflict(TNode conflict
, TheoryId theoryId
) {
1941 Debug("theory::conflict") << "TheoryEngine::conflict(" << conflict
<< ", " << theoryId
<< ")" << endl
;
1943 Trace("dtview::conflict") << ":THEORY-CONFLICT: " << conflict
<< std::endl
;
1945 // Mark that we are in conflict
1946 d_inConflict
= true;
1948 if(Dump
.isOn("t-conflicts")) {
1949 Dump("t-conflicts") << CommentCommand("theory conflict: expect unsat")
1950 << CheckSatCommand(conflict
.toExpr());
1953 LemmaProofRecipe
* proofRecipe
= NULL
;
1955 proofRecipe
= new LemmaProofRecipe
;
1957 LemmaProofRecipe::ProofStep
proofStep(theoryId
, emptyNode
);
1959 if (conflict
.getKind() == kind::AND
) {
1960 for (unsigned i
= 0; i
< conflict
.getNumChildren(); ++i
) {
1961 proofStep
.addAssertion(conflict
[i
].negate());
1964 proofStep
.addAssertion(conflict
.negate());
1967 proofRecipe
->addStep(proofStep
);
1970 // In the multiple-theories case, we need to reconstruct the conflict
1971 if (d_logicInfo
.isSharingEnabled()) {
1972 // Create the workplace for explanations
1973 std::vector
<NodeTheoryPair
> explanationVector
;
1974 explanationVector
.push_back(NodeTheoryPair(conflict
, theoryId
, d_propagationMapTimestamp
));
1976 // Process the explanation
1977 getExplanation(explanationVector
, proofRecipe
);
1978 PROOF(ProofManager::getCnfProof()->setProofRecipe(proofRecipe
));
1979 Node fullConflict
= mkExplanation(explanationVector
);
1980 Debug("theory::conflict") << "TheoryEngine::conflict(" << conflict
<< ", " << theoryId
<< "): full = " << fullConflict
<< endl
;
1981 Assert(properConflict(fullConflict
));
1982 lemma(fullConflict
, RULE_CONFLICT
, true, true, false, THEORY_LAST
);
1985 // When only one theory, the conflict should need no processing
1986 Assert(properConflict(conflict
));
1988 if (conflict
.getKind() == kind::AND
) {
1989 // If the conflict is a conjunction, the corresponding lemma is derived by negating
1991 for (unsigned i
= 0; i
< conflict
.getNumChildren(); ++i
) {
1992 if (conflict
[i
].isConst() && conflict
[i
].getConst
<bool>()) {
1996 if (conflict
[i
].getKind() == kind::NOT
&&
1997 conflict
[i
][0].isConst() && !conflict
[i
][0].getConst
<bool>()) {
2001 proofRecipe
->getStep(0)->addAssertion(conflict
[i
].negate());
2002 proofRecipe
->addBaseAssertion(conflict
[i
].negate());
2005 proofRecipe
->getStep(0)->addAssertion(conflict
.negate());
2006 proofRecipe
->addBaseAssertion(conflict
.negate());
2009 ProofManager::getCnfProof()->setProofRecipe(proofRecipe
);
2012 lemma(conflict
, RULE_CONFLICT
, true, true, false, THEORY_LAST
);
2021 void TheoryEngine::staticInitializeBVOptions(
2022 const std::vector
<Node
>& assertions
)
2024 bool useSlicer
= true;
2025 if (options::bitvectorEqualitySlicer() == options::BvSlicerMode::ON
)
2027 if (!d_logicInfo
.isPure(theory::THEORY_BV
) || d_logicInfo
.isQuantified())
2028 throw ModalException(
2029 "Slicer currently only supports pure QF_BV formulas. Use "
2030 "--bv-eq-slicer=off");
2031 if (options::incrementalSolving())
2032 throw ModalException(
2033 "Slicer does not currently support incremental mode. Use "
2034 "--bv-eq-slicer=off");
2035 if (options::produceModels())
2036 throw ModalException(
2037 "Slicer does not currently support model generation. Use "
2038 "--bv-eq-slicer=off");
2040 else if (options::bitvectorEqualitySlicer() == options::BvSlicerMode::OFF
)
2044 else if (options::bitvectorEqualitySlicer() == options::BvSlicerMode::AUTO
)
2046 if ((!d_logicInfo
.isPure(theory::THEORY_BV
) || d_logicInfo
.isQuantified())
2047 || options::incrementalSolving()
2048 || options::produceModels())
2051 bv::utils::TNodeBoolMap cache
;
2052 for (unsigned i
= 0; i
< assertions
.size(); ++i
)
2054 useSlicer
= useSlicer
&& bv::utils::isCoreTerm(assertions
[i
], cache
);
2060 bv::TheoryBV
* bv_theory
= (bv::TheoryBV
*)d_theoryTable
[THEORY_BV
];
2061 bv_theory
->enableCoreTheorySlicer();
2065 void TheoryEngine::getExplanation(std::vector
<NodeTheoryPair
>& explanationVector
, LemmaProofRecipe
* proofRecipe
) {
2066 Assert(explanationVector
.size() > 0);
2068 unsigned i
= 0; // Index of the current literal we are processing
2069 unsigned j
= 0; // Index of the last literal we are keeping
2071 std::unique_ptr
<std::set
<Node
>> inputAssertions
= nullptr;
2075 inputAssertions
.reset(
2076 new std::set
<Node
>(proofRecipe
->getStep(0)->getAssertions()));
2080 while (i
< explanationVector
.size()) {
2081 // Get the current literal to explain
2082 NodeTheoryPair toExplain
= explanationVector
[i
];
2084 Debug("theory::explain")
2085 << "[i=" << i
<< "] TheoryEngine::explain(): processing ["
2086 << toExplain
.d_timestamp
<< "] " << toExplain
.d_node
<< " sent from "
2087 << toExplain
.d_theory
<< endl
;
2089 // If a true constant or a negation of a false constant we can ignore it
2090 if (toExplain
.d_node
.isConst() && toExplain
.d_node
.getConst
<bool>())
2095 if (toExplain
.d_node
.getKind() == kind::NOT
&& toExplain
.d_node
[0].isConst()
2096 && !toExplain
.d_node
[0].getConst
<bool>())
2102 // If from the SAT solver, keep it
2103 if (toExplain
.d_theory
== THEORY_SAT_SOLVER
)
2105 Debug("theory::explain") << "\tLiteral came from THEORY_SAT_SOLVER. Kepping it." << endl
;
2106 explanationVector
[j
++] = explanationVector
[i
++];
2110 // If an and, expand it
2111 if (toExplain
.d_node
.getKind() == kind::AND
)
2113 Debug("theory::explain")
2114 << "TheoryEngine::explain(): expanding " << toExplain
.d_node
2115 << " got from " << toExplain
.d_theory
<< endl
;
2116 for (unsigned k
= 0; k
< toExplain
.d_node
.getNumChildren(); ++k
)
2118 NodeTheoryPair
newExplain(
2119 toExplain
.d_node
[k
], toExplain
.d_theory
, toExplain
.d_timestamp
);
2120 explanationVector
.push_back(newExplain
);
2126 // See if it was sent to the theory by another theory
2127 PropagationMap::const_iterator find
= d_propagationMap
.find(toExplain
);
2128 if (find
!= d_propagationMap
.end()) {
2129 Debug("theory::explain")
2130 << "\tTerm was propagated by another theory (theory = "
2131 << getTheoryString((*find
).second
.d_theory
) << ")" << std::endl
;
2132 // There is some propagation, check if its a timely one
2133 if ((*find
).second
.d_timestamp
< toExplain
.d_timestamp
)
2135 Debug("theory::explain")
2136 << "\tRelevant timetsamp, pushing " << (*find
).second
.d_node
2137 << "to index = " << explanationVector
.size() << std::endl
;
2138 explanationVector
.push_back((*find
).second
);
2142 if (toExplain
.d_node
!= (*find
).second
.d_node
)
2144 Debug("pf::explain")
2145 << "TheoryEngine::getExplanation: Rewrite alert! toAssert = "
2146 << toExplain
.d_node
<< ", toExplain = " << (*find
).second
.d_node
2151 proofRecipe
->addRewriteRule(toExplain
.d_node
,
2152 (*find
).second
.d_node
);
2161 // It was produced by the theory, so ask for an explanation
2163 if (toExplain
.d_theory
== THEORY_BUILTIN
)
2165 explanation
= d_sharedTerms
.explain(toExplain
.d_node
);
2166 Debug("theory::explain") << "\tTerm was propagated by THEORY_BUILTIN. Explanation: " << explanation
<< std::endl
;
2170 explanation
= theoryOf(toExplain
.d_theory
)->explain(toExplain
.d_node
);
2171 Debug("theory::explain") << "\tTerm was propagated by owner theory: "
2172 << theoryOf(toExplain
.d_theory
)->getId()
2173 << ". Explanation: " << explanation
<< std::endl
;
2176 Debug("theory::explain")
2177 << "TheoryEngine::explain(): got explanation " << explanation
2178 << " got from " << toExplain
.d_theory
<< endl
;
2179 Assert(explanation
!= toExplain
.d_node
)
2180 << "wasn't sent to you, so why are you explaining it trivially";
2181 // Mark the explanation
2182 NodeTheoryPair
newExplain(
2183 explanation
, toExplain
.d_theory
, toExplain
.d_timestamp
);
2184 explanationVector
.push_back(newExplain
);
2189 if (proofRecipe
&& inputAssertions
)
2191 // If we're expanding the target node of the explanation (this is the
2192 // first expansion...), we don't want to add it as a separate proof
2193 // step. It is already part of the assertions.
2194 if (!ContainsKey(*inputAssertions
, toExplain
.d_node
))
2196 LemmaProofRecipe::ProofStep
proofStep(toExplain
.d_theory
,
2198 if (explanation
.getKind() == kind::AND
)
2200 Node flat
= flattenAnd(explanation
);
2201 for (unsigned k
= 0; k
< flat
.getNumChildren(); ++k
)
2203 // If a true constant or a negation of a false constant we can
2205 if (!((flat
[k
].isConst() && flat
[k
].getConst
<bool>())
2206 || (flat
[k
].getKind() == kind::NOT
&& flat
[k
][0].isConst()
2207 && !flat
[k
][0].getConst
<bool>())))
2209 proofStep
.addAssertion(flat
[k
].negate());
2215 if (!((explanation
.isConst() && explanation
.getConst
<bool>())
2216 || (explanation
.getKind() == kind::NOT
2217 && explanation
[0].isConst()
2218 && !explanation
[0].getConst
<bool>())))
2220 proofStep
.addAssertion(explanation
.negate());
2223 proofRecipe
->addStep(proofStep
);
2229 // Keep only the relevant literals
2230 explanationVector
.resize(j
);
2234 // The remaining literals are the base of the proof
2235 for (unsigned k
= 0; k
< explanationVector
.size(); ++k
) {
2236 proofRecipe
->addBaseAssertion(explanationVector
[k
].d_node
.negate());
2242 void TheoryEngine::setUserAttribute(const std::string
& attr
,
2244 const std::vector
<Node
>& node_values
,
2245 const std::string
& str_value
)
2247 Trace("te-attr") << "set user attribute " << attr
<< " " << n
<< endl
;
2248 if( d_attr_handle
.find( attr
)!=d_attr_handle
.end() ){
2249 for( size_t i
=0; i
<d_attr_handle
[attr
].size(); i
++ ){
2250 d_attr_handle
[attr
][i
]->setUserAttribute(attr
, n
, node_values
, str_value
);
2253 //unhandled exception?
2257 void TheoryEngine::handleUserAttribute(const char* attr
, Theory
* t
) {
2258 Trace("te-attr") << "Handle user attribute " << attr
<< " " << t
<< endl
;
2259 std::string
str( attr
);
2260 d_attr_handle
[ str
].push_back( t
);
2263 void TheoryEngine::checkTheoryAssertionsWithModel(bool hardFailure
) {
2264 for(TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
2265 Theory
* theory
= d_theoryTable
[theoryId
];
2266 if(theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
2267 for(context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(),
2268 it_end
= theory
->facts_end();
2271 Node assertion
= (*it
).d_assertion
;
2272 Node val
= getModel()->getValue(assertion
);
2275 std::stringstream ss
;
2277 << " has an asserted fact that the model doesn't satisfy." << endl
2278 << "The fact: " << assertion
<< endl
2279 << "Model value: " << val
<< endl
;
2284 // Always an error if it is false
2285 InternalError() << ss
.str();
2289 // Otherwise just a warning. Notice this case may happen for
2290 // assertions with unevaluable operators, e.g. transcendental
2291 // functions. It also may happen for separation logic, where
2292 // check-model support is limited.
2293 Warning() << ss
.str();
2302 std::pair
<bool, Node
> TheoryEngine::entailmentCheck(
2303 options::TheoryOfMode mode
,
2305 const EntailmentCheckParameters
* params
,
2306 EntailmentCheckSideEffects
* seffects
)
2308 TNode atom
= (lit
.getKind() == kind::NOT
) ? lit
[0] : lit
;
2309 if( atom
.getKind()==kind::AND
|| atom
.getKind()==kind::OR
|| atom
.getKind()==kind::IMPLIES
){
2310 //Boolean connective, recurse
2311 std::vector
< Node
> children
;
2312 bool pol
= (lit
.getKind()!=kind::NOT
);
2313 bool is_conjunction
= pol
==(lit
.getKind()==kind::AND
);
2314 for( unsigned i
=0; i
<atom
.getNumChildren(); i
++ ){
2316 if( pol
==( lit
.getKind()==kind::IMPLIES
&& i
==0 ) ){
2317 ch
= atom
[i
].negate();
2319 std::pair
<bool, Node
> chres
= entailmentCheck( mode
, ch
, params
, seffects
);
2321 if( !is_conjunction
){
2324 children
.push_back( chres
.second
);
2326 }else if( !chres
.first
&& is_conjunction
){
2327 return std::pair
<bool, Node
>(false, Node::null());
2330 if( is_conjunction
){
2331 return std::pair
<bool, Node
>(true, NodeManager::currentNM()->mkNode(kind::AND
, children
));
2333 return std::pair
<bool, Node
>(false, Node::null());
2335 }else if( atom
.getKind()==kind::ITE
|| ( atom
.getKind()==kind::EQUAL
&& atom
[0].getType().isBoolean() ) ){
2336 bool pol
= (lit
.getKind()!=kind::NOT
);
2337 for( unsigned r
=0; r
<2; r
++ ){
2342 std::pair
<bool, Node
> chres
= entailmentCheck( mode
, ch
, params
, seffects
);
2344 Node ch2
= atom
[ atom
.getKind()==kind::ITE
? r
+1 : 1 ];
2345 if( pol
==( atom
.getKind()==kind::ITE
? true : r
==1 ) ){
2348 std::pair
<bool, Node
> chres2
= entailmentCheck( mode
, ch2
, params
, seffects
);
2350 return std::pair
<bool, Node
>(true, NodeManager::currentNM()->mkNode(kind::AND
, chres
.second
, chres2
.second
));
2356 return std::pair
<bool, Node
>(false, Node::null());
2358 //it is a theory atom
2359 theory::TheoryId tid
= theory::Theory::theoryOf(mode
, atom
);
2360 theory::Theory
* th
= theoryOf(tid
);
2363 Assert(params
== NULL
|| tid
== params
->getTheoryId());
2364 Assert(seffects
== NULL
|| tid
== seffects
->getTheoryId());
2365 Trace("theory-engine-entc") << "Entailment check : " << lit
<< std::endl
;
2367 std::pair
<bool, Node
> chres
= th
->entailmentCheck(lit
, params
, seffects
);
2372 void TheoryEngine::spendResource(ResourceManager::Resource r
)
2374 d_resourceManager
->spendResource(r
);
2377 void TheoryEngine::enableTheoryAlternative(const std::string
& name
){
2378 Debug("TheoryEngine::enableTheoryAlternative")
2379 << "TheoryEngine::enableTheoryAlternative(" << name
<< ")" << std::endl
;
2381 d_theoryAlternatives
.insert(name
);
2384 bool TheoryEngine::useTheoryAlternative(const std::string
& name
) {
2385 return d_theoryAlternatives
.find(name
) != d_theoryAlternatives
.end();
2389 TheoryEngine::Statistics::Statistics(theory::TheoryId theory
):
2390 conflicts(getStatsPrefix(theory
) + "::conflicts", 0),
2391 propagations(getStatsPrefix(theory
) + "::propagations", 0),
2392 lemmas(getStatsPrefix(theory
) + "::lemmas", 0),
2393 requirePhase(getStatsPrefix(theory
) + "::requirePhase", 0),
2394 restartDemands(getStatsPrefix(theory
) + "::restartDemands", 0)
2396 smtStatisticsRegistry()->registerStat(&conflicts
);
2397 smtStatisticsRegistry()->registerStat(&propagations
);
2398 smtStatisticsRegistry()->registerStat(&lemmas
);
2399 smtStatisticsRegistry()->registerStat(&requirePhase
);
2400 smtStatisticsRegistry()->registerStat(&restartDemands
);
2403 TheoryEngine::Statistics::~Statistics() {
2404 smtStatisticsRegistry()->unregisterStat(&conflicts
);
2405 smtStatisticsRegistry()->unregisterStat(&propagations
);
2406 smtStatisticsRegistry()->unregisterStat(&lemmas
);
2407 smtStatisticsRegistry()->unregisterStat(&requirePhase
);
2408 smtStatisticsRegistry()->unregisterStat(&restartDemands
);
2411 }/* CVC4 namespace */