1 /********************* */
2 /*! \file theory_engine.cpp
4 ** Original author: Morgan Deters
5 ** Major contributors: Dejan Jovanovic
6 ** Minor contributors (to current version): Christopher L. Conway, Tianyi Liang, Kshitij Bansal, Clark Barrett, Liana Hadarean, Andrew Reynolds, Tim King
7 ** This file is part of the CVC4 project.
8 ** Copyright (c) 2009-2014 New York University and The University of Iowa
9 ** See the file COPYING in the top-level source directory for licensing
10 ** information.\endverbatim
12 ** \brief The theory engine
20 #include "theory/arith/arith_ite_utils.h"
22 #include "decision/decision_engine.h"
24 #include "expr/attribute.h"
25 #include "expr/node.h"
26 #include "expr/node_builder.h"
27 #include "options/options.h"
28 #include "util/lemma_output_channel.h"
30 #include "theory/theory.h"
31 #include "theory/theory_engine.h"
32 #include "theory/rewriter.h"
33 #include "theory/theory_traits.h"
35 #include "smt/logic_exception.h"
37 #include "proof/proof_manager.h"
39 #include "util/node_visitor.h"
40 #include "util/ite_removal.h"
42 //#include "theory/ite_simplifier.h"
43 //#include "theory/ite_compressor.h"
44 #include "theory/ite_utilities.h"
45 #include "theory/unconstrained_simplifier.h"
47 #include "theory/theory_model.h"
49 #include "theory/quantifiers_engine.h"
50 #include "theory/quantifiers/theory_quantifiers.h"
51 #include "theory/quantifiers/options.h"
52 #include "theory/quantifiers/model_engine.h"
53 #include "theory/quantifiers/first_order_model.h"
55 #include "theory/uf/equality_engine.h"
56 //#include "theory/rewriterules/efficient_e_matching.h"
57 #include "theory/bv/theory_bv_utils.h"
58 #include "theory/bv/options.h"
60 #include "proof/proof_manager.h"
65 using namespace CVC4::theory
;
67 void TheoryEngine::finishInit() {
68 PROOF (ProofManager::initTheoryProof(); );
70 // initialize the quantifiers engine
71 d_quantEngine
= new QuantifiersEngine(d_context
, d_userContext
, this);
73 if (d_logicInfo
.isQuantified()) {
74 d_quantEngine
->finishInit();
75 Assert(d_masterEqualityEngine
== 0);
76 d_masterEqualityEngine
= new eq::EqualityEngine(d_masterEENotify
,getSatContext(), "theory::master");
78 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
; ++ theoryId
) {
79 if (d_theoryTable
[theoryId
]) {
80 d_theoryTable
[theoryId
]->setQuantifiersEngine(d_quantEngine
);
81 d_theoryTable
[theoryId
]->setMasterEqualityEngine(d_masterEqualityEngine
);
86 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
; ++ theoryId
) {
87 if (d_theoryTable
[theoryId
]) {
88 d_theoryTable
[theoryId
]->finishInit();
93 void TheoryEngine::eqNotifyNewClass(TNode t
){
94 d_quantEngine
->addTermToDatabase( t
);
95 if( d_logicInfo
.isQuantified() && options::quantConflictFind() ){
96 d_quantEngine
->getConflictFind()->newEqClass( t
);
100 void TheoryEngine::eqNotifyPreMerge(TNode t1
, TNode t2
){
101 //TODO: add notification to efficient E-matching
102 if( d_logicInfo
.isQuantified() ){
103 //d_quantEngine->getEfficientEMatcher()->merge( t1, t2 );
104 if( options::quantConflictFind() ){
105 d_quantEngine
->getConflictFind()->merge( t1
, t2
);
110 void TheoryEngine::eqNotifyPostMerge(TNode t1
, TNode t2
){
114 void TheoryEngine::eqNotifyDisequal(TNode t1
, TNode t2
, TNode reason
){
115 if( d_logicInfo
.isQuantified() ){
116 if( options::quantConflictFind() ){
117 d_quantEngine
->getConflictFind()->assertDisequal( t1
, t2
);
123 TheoryEngine::TheoryEngine(context::Context
* context
,
124 context::UserContext
* userContext
,
125 RemoveITE
& iteRemover
,
126 const LogicInfo
& logicInfo
)
127 : d_propEngine(NULL
),
128 d_decisionEngine(NULL
),
130 d_userContext(userContext
),
131 d_logicInfo(logicInfo
),
132 d_sharedTerms(this, context
),
133 d_masterEqualityEngine(NULL
),
134 d_masterEENotify(*this),
137 d_curr_model_builder(NULL
),
139 d_possiblePropagations(context
),
140 d_hasPropagated(context
),
141 d_inConflict(context
, false),
142 d_hasShutDown(false),
143 d_incomplete(context
, false),
144 d_propagationMap(context
),
145 d_propagationMapTimestamp(context
, 0),
146 d_propagatedLiterals(context
),
147 d_propagatedLiteralsIndex(context
, 0),
148 d_atomRequests(context
),
149 d_iteRemover(iteRemover
),
150 d_combineTheoriesTime("TheoryEngine::combineTheoriesTime"),
153 d_interrupted(false),
154 d_inPreregister(false),
155 d_factsAsserted(context
, false),
156 d_preRegistrationVisitor(this, context
),
157 d_sharedTermsVisitor(d_sharedTerms
),
158 d_unconstrainedSimp(new UnconstrainedSimplifier(context
, logicInfo
)),
159 d_bvToBoolPreprocessor(),
160 d_arithSubstitutionsAdded("theory::arith::zzz::arith::substitutions", 0)
162 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
; ++ theoryId
) {
163 d_theoryTable
[theoryId
] = NULL
;
164 d_theoryOut
[theoryId
] = NULL
;
167 // build model information if applicable
168 d_curr_model
= new theory::TheoryModel(userContext
, "DefaultModel", true);
169 d_curr_model_builder
= new theory::TheoryEngineModelBuilder(this);
171 StatisticsRegistry::registerStat(&d_combineTheoriesTime
);
172 d_true
= NodeManager::currentNM()->mkConst
<bool>(true);
173 d_false
= NodeManager::currentNM()->mkConst
<bool>(false);
175 d_iteUtilities
= new ITEUtilities(d_iteRemover
.getContainsVisitor());
177 StatisticsRegistry::registerStat(&d_arithSubstitutionsAdded
);
180 TheoryEngine::~TheoryEngine() {
181 Assert(d_hasShutDown
);
183 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
; ++ theoryId
) {
184 if(d_theoryTable
[theoryId
] != NULL
) {
185 delete d_theoryTable
[theoryId
];
186 delete d_theoryOut
[theoryId
];
190 delete d_curr_model_builder
;
193 delete d_quantEngine
;
195 delete d_masterEqualityEngine
;
197 StatisticsRegistry::unregisterStat(&d_combineTheoriesTime
);
199 delete d_unconstrainedSimp
;
201 delete d_iteUtilities
;
203 StatisticsRegistry::unregisterStat(&d_arithSubstitutionsAdded
);
206 void TheoryEngine::interrupt() throw(ModalException
) {
207 d_interrupted
= true;
210 void TheoryEngine::preRegister(TNode preprocessed
) {
212 if(Dump
.isOn("missed-t-propagations")) {
213 d_possiblePropagations
.push_back(preprocessed
);
215 d_preregisterQueue
.push(preprocessed
);
217 if (!d_inPreregister
) {
218 // We're in pre-register
219 d_inPreregister
= true;
221 // Process the pre-registration queue
222 while (!d_preregisterQueue
.empty()) {
223 // Get the next atom to pre-register
224 preprocessed
= d_preregisterQueue
.front();
225 d_preregisterQueue
.pop();
227 if (d_logicInfo
.isSharingEnabled() && preprocessed
.getKind() == kind::EQUAL
) {
228 // When sharing is enabled, we propagate from the shared terms manager also
229 d_sharedTerms
.addEqualityToPropagate(preprocessed
);
232 // Pre-register the terms in the atom
233 Theory::Set theories
= NodeVisitor
<PreRegisterVisitor
>::run(d_preRegistrationVisitor
, preprocessed
);
234 theories
= Theory::setRemove(THEORY_BOOL
, theories
);
235 // Remove the top theory, if any more that means multiple theories were involved
236 bool multipleTheories
= Theory::setRemove(Theory::theoryOf(preprocessed
), theories
);
238 // These checks don't work with finite model finding, because it
239 // uses Rational constants to represent cardinality constraints,
240 // even though arithmetic isn't actually involved.
241 if(!options::finiteModelFind()) {
242 while((i
= Theory::setPop(theories
)) != THEORY_LAST
) {
243 if(!d_logicInfo
.isTheoryEnabled(i
)) {
244 LogicInfo newLogicInfo
= d_logicInfo
.getUnlockedCopy();
245 newLogicInfo
.enableTheory(i
);
248 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
249 << ", which doesn't include " << i
250 << ", but found a term in that theory." << endl
251 << "You might want to extend your logic to "
252 << newLogicInfo
.getLogicString() << endl
;
253 throw LogicException(ss
.str());
257 if (multipleTheories
) {
258 // Collect the shared terms if there are multiple theories
259 NodeVisitor
<SharedTermsVisitor
>::run(d_sharedTermsVisitor
, preprocessed
);
263 // Leaving pre-register
264 d_inPreregister
= false;
268 void TheoryEngine::printAssertions(const char* tag
) {
269 if (Trace
.isOn(tag
)) {
271 for (TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
272 Theory
* theory
= d_theoryTable
[theoryId
];
273 if (theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
274 Trace(tag
) << "--------------------------------------------" << endl
;
275 Trace(tag
) << "Assertions of " << theory
->getId() << ": " << endl
;
276 context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(), it_end
= theory
->facts_end();
277 for (unsigned i
= 0; it
!= it_end
; ++ it
, ++i
) {
278 if ((*it
).isPreregistered
) {
279 Trace(tag
) << "[" << i
<< "]: ";
281 Trace(tag
) << "(" << i
<< "): ";
283 Trace(tag
) << (*it
).assertion
<< endl
;
286 if (d_logicInfo
.isSharingEnabled()) {
287 Trace(tag
) << "Shared terms of " << theory
->getId() << ": " << endl
;
288 context::CDList
<TNode
>::const_iterator it
= theory
->shared_terms_begin(), it_end
= theory
->shared_terms_end();
289 for (unsigned i
= 0; it
!= it_end
; ++ it
, ++i
) {
290 Trace(tag
) << "[" << i
<< "]: " << (*it
) << endl
;
298 void TheoryEngine::dumpAssertions(const char* tag
) {
299 if (Dump
.isOn(tag
)) {
300 Dump(tag
) << CommentCommand("Starting completeness check");
301 for (TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
302 Theory
* theory
= d_theoryTable
[theoryId
];
303 if (theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
304 Dump(tag
) << CommentCommand("Completeness check");
305 Dump(tag
) << PushCommand();
307 // Dump the shared terms
308 if (d_logicInfo
.isSharingEnabled()) {
309 Dump(tag
) << CommentCommand("Shared terms");
310 context::CDList
<TNode
>::const_iterator it
= theory
->shared_terms_begin(), it_end
= theory
->shared_terms_end();
311 for (unsigned i
= 0; it
!= it_end
; ++ it
, ++i
) {
314 Dump(tag
) << CommentCommand(ss
.str());
318 // Dump the assertions
319 Dump(tag
) << CommentCommand("Assertions");
320 context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(), it_end
= theory
->facts_end();
321 for (; it
!= it_end
; ++ it
) {
323 Node assertionNode
= (*it
).assertion
;
324 // Purify all the terms
326 if ((*it
).isPreregistered
) {
327 Dump(tag
) << CommentCommand("Preregistered");
329 Dump(tag
) << CommentCommand("Shared assertion");
331 Dump(tag
) << AssertCommand(assertionNode
.toExpr());
333 Dump(tag
) << CheckSatCommand();
335 Dump(tag
) << PopCommand();
342 * Check all (currently-active) theories for conflicts.
343 * @param effort the effort level to use
345 void TheoryEngine::check(Theory::Effort effort
) {
347 d_propEngine
->checkTime();
349 // Reset the interrupt flag
350 d_interrupted
= false;
352 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
353 #undef CVC4_FOR_EACH_THEORY_STATEMENT
355 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
356 if (theory::TheoryTraits<THEORY>::hasCheck && d_logicInfo.isTheoryEnabled(THEORY)) { \
357 theoryOf(THEORY)->check(effort); \
358 if (d_inConflict) { \
366 // Mark the output channel unused (if this is FULL_EFFORT, and nothing
367 // is done by the theories, no additional check will be needed)
368 d_outputChannelUsed
= false;
370 // Mark the lemmas flag (no lemmas added)
371 d_lemmasAdded
= false;
373 Debug("theory") << "TheoryEngine::check(" << effort
<< "): d_factsAsserted = " << (d_factsAsserted
? "true" : "false") << endl
;
375 // If in full effort, we have a fake new assertion just to jumpstart the checking
376 if (Theory::fullEffort(effort
)) {
377 d_factsAsserted
= true;
381 while (d_factsAsserted
&& !d_inConflict
&& !d_lemmasAdded
) {
383 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running check" << endl
;
385 Trace("theory::assertions") << endl
;
386 if (Trace
.isOn("theory::assertions")) {
387 printAssertions("theory::assertions");
390 // Note that we've discharged all the facts
391 d_factsAsserted
= false;
394 CVC4_FOR_EACH_THEORY
;
396 if(Dump
.isOn("missed-t-conflicts")) {
397 Dump("missed-t-conflicts")
398 << CommentCommand("Completeness check for T-conflicts; expect sat")
399 << CheckSatCommand();
402 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running propagation after the initial check" << endl
;
404 // We are still satisfiable, propagate as much as possible
407 // We do combination if all has been processed and we are in fullcheck
408 if (Theory::fullEffort(effort
) && d_logicInfo
.isSharingEnabled() && !d_factsAsserted
&& !d_lemmasAdded
&& !d_inConflict
) {
409 // Do the combination
410 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running combination" << endl
;
415 // Must consult quantifiers theory for last call to ensure sat, or otherwise add a lemma
416 if( effort
== Theory::EFFORT_FULL
&& ! d_inConflict
&& ! needCheck() ) {
417 //d_theoryTable[THEORY_STRINGS]->check(Theory::EFFORT_LAST_CALL);
418 if(d_logicInfo
.isQuantified()) {
419 // quantifiers engine must pass effort last call check
420 d_quantEngine
->check(Theory::EFFORT_LAST_CALL
);
421 // if we have given up, then possibly flip decision
422 if(options::flipDecision()) {
423 if(d_incomplete
&& !d_inConflict
&& !needCheck()) {
424 ((theory::quantifiers::TheoryQuantifiers
*) d_theoryTable
[THEORY_QUANTIFIERS
])->flipDecision();
427 // if returning incomplete or SAT, we have ensured that the model in the quantifiers engine has been built
428 } else if(options::produceModels()) {
429 // must build model at this point
430 d_curr_model_builder
->buildModel(d_curr_model
, true);
432 Trace("theory::assertions-model") << endl
;
433 if (Trace
.isOn("theory::assertions-model")) {
434 printAssertions("theory::assertions-model");
438 Debug("theory") << "TheoryEngine::check(" << effort
<< "): done, we are " << (d_inConflict
? "unsat" : "sat") << (d_lemmasAdded
? " with new lemmas" : " with no new lemmas") << endl
;
440 if(!d_inConflict
&& Theory::fullEffort(effort
) && d_masterEqualityEngine
!= NULL
&& !d_lemmasAdded
) {
441 AlwaysAssert(d_masterEqualityEngine
->consistent());
443 } catch(const theory::Interrupted
&) {
444 Trace("theory") << "TheoryEngine::check() => interrupted" << endl
;
446 // If fulleffort, check all theories
447 if(Dump
.isOn("theory::fullcheck") && Theory::fullEffort(effort
)) {
448 if (!d_inConflict
&& !needCheck()) {
449 dumpAssertions("theory::fullcheck");
454 void TheoryEngine::combineTheories() {
456 Trace("combineTheories") << "TheoryEngine::combineTheories()" << endl
;
458 TimerStat::CodeTimer
combineTheoriesTimer(d_combineTheoriesTime
);
460 // Care graph we'll be building
463 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
464 #undef CVC4_FOR_EACH_THEORY_STATEMENT
466 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
467 if (theory::TheoryTraits<THEORY>::isParametric && d_logicInfo.isTheoryEnabled(THEORY)) { \
468 theoryOf(THEORY)->getCareGraph(careGraph); \
471 // Call on each parametric theory to give us its care graph
472 CVC4_FOR_EACH_THEORY
;
474 Trace("combineTheories") << "TheoryEngine::combineTheories(): care graph size = " << careGraph
.size() << endl
;
476 // Now add splitters for the ones we are interested in
477 CareGraph::const_iterator care_it
= careGraph
.begin();
478 CareGraph::const_iterator care_it_end
= careGraph
.end();
480 for (; care_it
!= care_it_end
; ++ care_it
) {
481 const CarePair
& carePair
= *care_it
;
483 Debug("combineTheories") << "TheoryEngine::combineTheories(): checking " << carePair
.a
<< " = " << carePair
.b
<< " from " << carePair
.theory
<< endl
;
485 Assert(d_sharedTerms
.isShared(carePair
.a
) || carePair
.a
.isConst());
486 Assert(d_sharedTerms
.isShared(carePair
.b
) || carePair
.b
.isConst());
488 // The equality in question (order for no repetition)
489 Node equality
= carePair
.a
.eqNode(carePair
.b
);
490 // EqualityStatus es = getEqualityStatus(carePair.a, carePair.b);
491 // Debug("combineTheories") << "TheoryEngine::combineTheories(): " <<
492 // (es == EQUALITY_TRUE_AND_PROPAGATED ? "EQUALITY_TRUE_AND_PROPAGATED" :
493 // es == EQUALITY_FALSE_AND_PROPAGATED ? "EQUALITY_FALSE_AND_PROPAGATED" :
494 // es == EQUALITY_TRUE ? "EQUALITY_TRUE" :
495 // es == EQUALITY_FALSE ? "EQUALITY_FALSE" :
496 // es == EQUALITY_TRUE_IN_MODEL ? "EQUALITY_TRUE_IN_MODEL" :
497 // es == EQUALITY_FALSE_IN_MODEL ? "EQUALITY_FALSE_IN_MODEL" :
498 // es == EQUALITY_UNKNOWN ? "EQUALITY_UNKNOWN" :
499 // "Unexpected case") << endl;
501 // We need to split on it
502 Debug("combineTheories") << "TheoryEngine::combineTheories(): requesting a split " << endl
;
503 lemma(equality
.orNode(equality
.notNode()), false, false, false, carePair
.theory
);
504 // This code is supposed to force preference to follow what the theory models already have
505 // but it doesn't seem to make a big difference - need to explore more -Clark
507 // if (es == EQUALITY_TRUE || es == EQUALITY_TRUE_IN_MODEL) {
508 Node e
= ensureLiteral(equality
);
509 d_propEngine
->requirePhase(e
, true);
511 // else if (es == EQUALITY_FALSE_IN_MODEL) {
512 // Node e = ensureLiteral(equality);
513 // d_propEngine->requirePhase(e, false);
519 void TheoryEngine::propagate(Theory::Effort effort
) {
520 // Reset the interrupt flag
521 d_interrupted
= false;
523 // Definition of the statement that is to be run by every theory
524 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
525 #undef CVC4_FOR_EACH_THEORY_STATEMENT
527 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
528 if (theory::TheoryTraits<THEORY>::hasPropagate && d_logicInfo.isTheoryEnabled(THEORY)) { \
529 theoryOf(THEORY)->propagate(effort); \
532 // Reset the interrupt flag
533 d_interrupted
= false;
535 // Propagate for each theory using the statement above
536 CVC4_FOR_EACH_THEORY
;
538 if(Dump
.isOn("missed-t-propagations")) {
539 for(unsigned i
= 0; i
< d_possiblePropagations
.size(); ++i
) {
540 Node atom
= d_possiblePropagations
[i
];
542 if(d_propEngine
->hasValue(atom
, value
)) {
545 // Doesn't have a value, check it (and the negation)
546 if(d_hasPropagated
.find(atom
) == d_hasPropagated
.end()) {
547 Dump("missed-t-propagations")
548 << CommentCommand("Completeness check for T-propagations; expect invalid")
549 << EchoCommand(atom
.toString())
550 << QueryCommand(atom
.toExpr())
551 << EchoCommand(atom
.notNode().toString())
552 << QueryCommand(atom
.notNode().toExpr());
558 Node
TheoryEngine::getNextDecisionRequest() {
559 // Definition of the statement that is to be run by every theory
560 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
561 #undef CVC4_FOR_EACH_THEORY_STATEMENT
563 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
564 if (theory::TheoryTraits<THEORY>::hasGetNextDecisionRequest && d_logicInfo.isTheoryEnabled(THEORY)) { \
565 Node n = theoryOf(THEORY)->getNextDecisionRequest(); \
571 // Request decision from each theory using the statement above
572 CVC4_FOR_EACH_THEORY
;
577 bool TheoryEngine::properConflict(TNode conflict
) const {
579 if (conflict
.getKind() == kind::AND
) {
580 for (unsigned i
= 0; i
< conflict
.getNumChildren(); ++ i
) {
581 if (! getPropEngine()->hasValue(conflict
[i
], value
)) {
582 Debug("properConflict") << "Bad conflict is due to unassigned atom: "
583 << conflict
[i
] << endl
;
587 Debug("properConflict") << "Bad conflict is due to false atom: "
588 << conflict
[i
] << endl
;
591 if (conflict
[i
] != Rewriter::rewrite(conflict
[i
])) {
592 Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
593 << conflict
[i
] << " vs " << Rewriter::rewrite(conflict
[i
]) << endl
;
598 if (! getPropEngine()->hasValue(conflict
, value
)) {
599 Debug("properConflict") << "Bad conflict is due to unassigned atom: "
604 Debug("properConflict") << "Bad conflict is due to false atom: "
608 if (conflict
!= Rewriter::rewrite(conflict
)) {
609 Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
610 << conflict
<< " vs " << Rewriter::rewrite(conflict
) << endl
;
617 bool TheoryEngine::properPropagation(TNode lit
) const {
618 if(!getPropEngine()->isSatLiteral(lit
)) {
622 return !getPropEngine()->hasValue(lit
, b
);
625 bool TheoryEngine::properExplanation(TNode node
, TNode expl
) const {
626 // Explanation must be either a conjunction of true literals that have true SAT values already
627 // or a singled literal that has a true SAT value already.
628 if (expl
.getKind() == kind::AND
) {
629 for (unsigned i
= 0; i
< expl
.getNumChildren(); ++ i
) {
631 if (!d_propEngine
->hasValue(expl
[i
], value
) || !value
) {
637 return d_propEngine
->hasValue(expl
, value
) && value
;
642 void TheoryEngine::collectModelInfo( theory::TheoryModel
* m
, bool fullModel
){
643 //have shared term engine collectModelInfo
644 // d_sharedTerms.collectModelInfo( m, fullModel );
645 // Consult each active theory to get all relevant information
646 // concerning the model.
647 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
; ++theoryId
) {
648 if(d_logicInfo
.isTheoryEnabled(theoryId
)) {
649 Trace("model-builder") << " CollectModelInfo on theory: " << theoryId
<< endl
;
650 d_theoryTable
[theoryId
]->collectModelInfo( m
, fullModel
);
653 // Get the Boolean variables
654 vector
<TNode
> boolVars
;
655 d_propEngine
->getBooleanVariables(boolVars
);
656 vector
<TNode
>::iterator it
, iend
= boolVars
.end();
657 bool hasValue
, value
;
658 for (it
= boolVars
.begin(); it
!= iend
; ++it
) {
660 hasValue
= d_propEngine
->hasValue(var
, value
);
661 // TODO: Assert that hasValue is true?
665 Trace("model-builder-assertions") << "(assert" << (value
? " " : " (not ") << var
<< (value
? ");" : "));") << endl
;
666 m
->assertPredicate(var
, value
);
671 TheoryModel
* TheoryEngine::getModel() {
672 Debug("model") << "TheoryEngine::getModel()" << endl
;
673 if( d_logicInfo
.isQuantified() ) {
674 Debug("model") << "Get model from quantifiers engine." << endl
;
675 return d_quantEngine
->getModel();
677 Debug("model") << "Get default model." << endl
;
682 bool TheoryEngine::presolve() {
683 // Reset the interrupt flag
684 d_interrupted
= false;
687 // Definition of the statement that is to be run by every theory
688 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
689 #undef CVC4_FOR_EACH_THEORY_STATEMENT
691 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
692 if (theory::TheoryTraits<THEORY>::hasPresolve) { \
693 theoryOf(THEORY)->presolve(); \
699 // Presolve for each theory using the statement above
700 CVC4_FOR_EACH_THEORY
;
701 } catch(const theory::Interrupted
&) {
702 Trace("theory") << "TheoryEngine::presolve() => interrupted" << endl
;
704 // return whether we have a conflict
706 }/* TheoryEngine::presolve() */
708 void TheoryEngine::postsolve() {
709 // Reset the interrupt flag
710 d_interrupted
= false;
711 bool CVC4_UNUSED wasInConflict
= d_inConflict
;
714 // Definition of the statement that is to be run by every theory
715 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
716 #undef CVC4_FOR_EACH_THEORY_STATEMENT
718 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
719 if (theory::TheoryTraits<THEORY>::hasPostsolve) { \
720 theoryOf(THEORY)->postsolve(); \
721 Assert(! d_inConflict || wasInConflict, "conflict raised during postsolve()"); \
724 // Postsolve for each theory using the statement above
725 CVC4_FOR_EACH_THEORY
;
726 } catch(const theory::Interrupted
&) {
727 Trace("theory") << "TheoryEngine::postsolve() => interrupted" << endl
;
729 }/* TheoryEngine::postsolve() */
732 void TheoryEngine::notifyRestart() {
733 // Reset the interrupt flag
734 d_interrupted
= false;
736 // Definition of the statement that is to be run by every theory
737 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
738 #undef CVC4_FOR_EACH_THEORY_STATEMENT
740 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
741 if (theory::TheoryTraits<THEORY>::hasNotifyRestart && d_logicInfo.isTheoryEnabled(THEORY)) { \
742 theoryOf(THEORY)->notifyRestart(); \
745 // notify each theory using the statement above
746 CVC4_FOR_EACH_THEORY
;
749 void TheoryEngine::ppStaticLearn(TNode in
, NodeBuilder
<>& learned
) {
750 // Reset the interrupt flag
751 d_interrupted
= false;
753 // Definition of the statement that is to be run by every theory
754 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
755 #undef CVC4_FOR_EACH_THEORY_STATEMENT
757 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
758 if (theory::TheoryTraits<THEORY>::hasPpStaticLearn) { \
759 theoryOf(THEORY)->ppStaticLearn(in, learned); \
762 // static learning for each theory using the statement above
763 CVC4_FOR_EACH_THEORY
;
766 void TheoryEngine::shutdown() {
767 // Set this first; if a Theory shutdown() throws an exception,
768 // at least the destruction of the TheoryEngine won't confound
770 d_hasShutDown
= true;
772 // Shutdown all the theories
773 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
; ++theoryId
) {
774 if(d_theoryTable
[theoryId
]) {
775 theoryOf(theoryId
)->shutdown();
782 theory::Theory::PPAssertStatus
TheoryEngine::solve(TNode literal
, SubstitutionMap
& substitutionOut
) {
783 // Reset the interrupt flag
784 d_interrupted
= false;
786 TNode atom
= literal
.getKind() == kind::NOT
? literal
[0] : literal
;
787 Trace("theory::solve") << "TheoryEngine::solve(" << literal
<< "): solving with " << theoryOf(atom
)->getId() << endl
;
789 if(! d_logicInfo
.isTheoryEnabled(Theory::theoryOf(atom
)) &&
790 Theory::theoryOf(atom
) != THEORY_SAT_SOLVER
) {
792 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
793 << ", which doesn't include " << Theory::theoryOf(atom
)
794 << ", but got a preprocessing-time fact for that theory." << endl
795 << "The fact:" << endl
797 throw LogicException(ss
.str());
800 Theory::PPAssertStatus solveStatus
= theoryOf(atom
)->ppAssert(literal
, substitutionOut
);
801 Trace("theory::solve") << "TheoryEngine::solve(" << literal
<< ") => " << solveStatus
<< endl
;
805 // Recursively traverse a term and call the theory rewriter on its sub-terms
806 Node
TheoryEngine::ppTheoryRewrite(TNode term
) {
807 NodeMap::iterator find
= d_ppCache
.find(term
);
808 if (find
!= d_ppCache
.end()) {
809 return (*find
).second
;
811 unsigned nc
= term
.getNumChildren();
813 return theoryOf(term
)->ppRewrite(term
);
815 Trace("theory-pp") << "ppTheoryRewrite { " << term
<< endl
;
818 if (theoryOf(term
)->ppDontRewriteSubterm(term
)) {
819 newTerm
= Rewriter::rewrite(term
);
821 NodeBuilder
<> newNode(term
.getKind());
822 if (term
.getMetaKind() == kind::metakind::PARAMETERIZED
) {
823 newNode
<< term
.getOperator();
826 for (i
= 0; i
< nc
; ++i
) {
827 newNode
<< ppTheoryRewrite(term
[i
]);
829 newTerm
= Rewriter::rewrite(Node(newNode
));
831 Node newTerm2
= theoryOf(newTerm
)->ppRewrite(newTerm
);
832 if (newTerm
!= newTerm2
) {
833 newTerm
= ppTheoryRewrite(Rewriter::rewrite(newTerm2
));
835 d_ppCache
[term
] = newTerm
;
836 Trace("theory-pp")<< "ppTheoryRewrite returning " << newTerm
<< "}" << endl
;
841 void TheoryEngine::preprocessStart()
847 struct preprocess_stack_element
{
850 preprocess_stack_element(TNode node
)
851 : node(node
), children_added(false) {}
852 };/* struct preprocess_stack_element */
855 Node
TheoryEngine::preprocess(TNode assertion
) {
857 Trace("theory::preprocess") << "TheoryEngine::preprocess(" << assertion
<< ")" << endl
;
859 // Do a topological sort of the subexpressions and substitute them
860 vector
<preprocess_stack_element
> toVisit
;
861 toVisit
.push_back(assertion
);
863 while (!toVisit
.empty())
865 // The current node we are processing
866 preprocess_stack_element
& stackHead
= toVisit
.back();
867 TNode current
= stackHead
.node
;
869 Debug("theory::internal") << "TheoryEngine::preprocess(" << assertion
<< "): processing " << current
<< endl
;
871 // If node already in the cache we're done, pop from the stack
872 NodeMap::iterator find
= d_ppCache
.find(current
);
873 if (find
!= d_ppCache
.end()) {
878 if(! d_logicInfo
.isTheoryEnabled(Theory::theoryOf(current
)) &&
879 Theory::theoryOf(current
) != THEORY_SAT_SOLVER
) {
881 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
882 << ", which doesn't include " << Theory::theoryOf(current
)
883 << ", but got a preprocessing-time fact for that theory." << endl
884 << "The fact:" << endl
886 throw LogicException(ss
.str());
889 // If this is an atom, we preprocess its terms with the theory ppRewriter
890 if (Theory::theoryOf(current
) != THEORY_BOOL
) {
891 Node ppRewritten
= ppTheoryRewrite(current
);
892 d_ppCache
[current
] = ppRewritten
;
893 Assert(Rewriter::rewrite(d_ppCache
[current
]) == d_ppCache
[current
]);
897 // Not yet substituted, so process
898 if (stackHead
.children_added
) {
899 // Children have been processed, so substitute
900 NodeBuilder
<> builder(current
.getKind());
901 if (current
.getMetaKind() == kind::metakind::PARAMETERIZED
) {
902 builder
<< current
.getOperator();
904 for (unsigned i
= 0; i
< current
.getNumChildren(); ++ i
) {
905 Assert(d_ppCache
.find(current
[i
]) != d_ppCache
.end());
906 builder
<< d_ppCache
[current
[i
]];
908 // Mark the substitution and continue
909 Node result
= builder
;
910 if (result
!= current
) {
911 result
= Rewriter::rewrite(result
);
913 Debug("theory::internal") << "TheoryEngine::preprocess(" << assertion
<< "): setting " << current
<< " -> " << result
<< endl
;
914 d_ppCache
[current
] = result
;
917 // Mark that we have added the children if any
918 if (current
.getNumChildren() > 0) {
919 stackHead
.children_added
= true;
920 // We need to add the children
921 for(TNode::iterator child_it
= current
.begin(); child_it
!= current
.end(); ++ child_it
) {
922 TNode childNode
= *child_it
;
923 NodeMap::iterator childFind
= d_ppCache
.find(childNode
);
924 if (childFind
== d_ppCache
.end()) {
925 toVisit
.push_back(childNode
);
929 // No children, so we're done
930 Debug("substitution::internal") << "SubstitutionMap::internalSubstitute(" << assertion
<< "): setting " << current
<< " -> " << current
<< endl
;
931 d_ppCache
[current
] = current
;
937 // Return the substituted version
938 return d_ppCache
[assertion
];
941 bool TheoryEngine::markPropagation(TNode assertion
, TNode originalAssertion
, theory::TheoryId toTheoryId
, theory::TheoryId fromTheoryId
) {
943 // What and where we are asserting
944 NodeTheoryPair
toAssert(assertion
, toTheoryId
, d_propagationMapTimestamp
);
945 // What and where it came from
946 NodeTheoryPair
toExplain(originalAssertion
, fromTheoryId
, d_propagationMapTimestamp
);
948 // See if the theory already got this literal
949 PropagationMap::const_iterator find
= d_propagationMap
.find(toAssert
);
950 if (find
!= d_propagationMap
.end()) {
951 // The theory already knows this
952 Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): already there" << endl
;
956 Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): marking [" << d_propagationMapTimestamp
<< "] " << assertion
<< ", " << toTheoryId
<< " from " << originalAssertion
<< ", " << fromTheoryId
<< endl
;
958 // Mark the propagation
959 d_propagationMap
[toAssert
] = toExplain
;
960 d_propagationMapTimestamp
= d_propagationMapTimestamp
+ 1;
966 void TheoryEngine::assertToTheory(TNode assertion
, TNode originalAssertion
, theory::TheoryId toTheoryId
, theory::TheoryId fromTheoryId
) {
968 Trace("theory::assertToTheory") << "TheoryEngine::assertToTheory(" << assertion
<< ", " << toTheoryId
<< ", " << fromTheoryId
<< ")" << endl
;
970 Assert(toTheoryId
!= fromTheoryId
);
971 if(! d_logicInfo
.isTheoryEnabled(toTheoryId
) &&
972 toTheoryId
!= THEORY_SAT_SOLVER
) {
974 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
975 << ", which doesn't include " << toTheoryId
976 << ", but got an asserted fact to that theory." << endl
977 << "The fact:" << endl
979 throw LogicException(ss
.str());
986 // If sharing is disabled, things are easy
987 if (!d_logicInfo
.isSharingEnabled()) {
988 Assert(assertion
== originalAssertion
);
989 if (fromTheoryId
== THEORY_SAT_SOLVER
) {
990 // Send to the apropriate theory
991 theory::Theory
* toTheory
= theoryOf(toTheoryId
);
992 // We assert it, and we know it's preregistereed
993 toTheory
->assertFact(assertion
, true);
994 // Mark that we have more information
995 d_factsAsserted
= true;
997 Assert(toTheoryId
== THEORY_SAT_SOLVER
);
998 // Check for propositional conflict
1000 if (d_propEngine
->hasValue(assertion
, value
)) {
1002 Trace("theory::propagate") << "TheoryEngine::assertToTheory(" << assertion
<< ", " << toTheoryId
<< ", " << fromTheoryId
<< "): conflict (no sharing)" << endl
;
1003 d_inConflict
= true;
1008 d_propagatedLiterals
.push_back(assertion
);
1013 // Polarity of the assertion
1014 bool polarity
= assertion
.getKind() != kind::NOT
;
1016 // Atom of the assertion
1017 TNode atom
= polarity
? assertion
: assertion
[0];
1019 // If sending to the shared terms database, it's also simple
1020 if (toTheoryId
== THEORY_BUILTIN
) {
1021 Assert(atom
.getKind() == kind::EQUAL
, "atom should be an EQUALity, not `%s'", atom
.toString().c_str());
1022 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1023 d_sharedTerms
.assertEquality(atom
, polarity
, assertion
);
1028 // Things from the SAT solver are already normalized, so they go
1029 // directly to the apropriate theory
1030 if (fromTheoryId
== THEORY_SAT_SOLVER
) {
1031 // We know that this is normalized, so just send it off to the theory
1032 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1033 // Is it preregistered
1034 bool preregistered
= d_propEngine
->isSatLiteral(assertion
) && Theory::theoryOf(assertion
) == toTheoryId
;
1036 theoryOf(toTheoryId
)->assertFact(assertion
, preregistered
);
1037 // Mark that we have more information
1038 d_factsAsserted
= true;
1043 // Propagations to the SAT solver are just enqueued for pickup by
1044 // the SAT solver later
1045 if (toTheoryId
== THEORY_SAT_SOLVER
) {
1046 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1047 // Enqueue for propagation to the SAT solver
1048 d_propagatedLiterals
.push_back(assertion
);
1049 // Check for propositional conflicts
1051 if (d_propEngine
->hasValue(assertion
, value
) && !value
) {
1052 Trace("theory::propagate") << "TheoryEngine::assertToTheory(" << assertion
<< ", " << toTheoryId
<< ", " << fromTheoryId
<< "): conflict (sharing)" << endl
;
1053 d_inConflict
= true;
1059 Assert(atom
.getKind() == kind::EQUAL
);
1062 Node normalizedLiteral
= Rewriter::rewrite(assertion
);
1064 // See if it rewrites false directly -> conflict
1065 if (normalizedLiteral
.isConst()) {
1066 if (!normalizedLiteral
.getConst
<bool>()) {
1067 // Mark the propagation for explanations
1068 if (markPropagation(normalizedLiteral
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1069 // Get the explanation (conflict will figure out where it came from)
1070 conflict(normalizedLiteral
, toTheoryId
);
1078 // Try and assert (note that we assert the non-normalized one)
1079 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1080 // Check if has been pre-registered with the theory
1081 bool preregistered
= d_propEngine
->isSatLiteral(assertion
) && Theory::theoryOf(assertion
) == toTheoryId
;
1083 theoryOf(toTheoryId
)->assertFact(assertion
, preregistered
);
1084 d_factsAsserted
= true;
1090 void TheoryEngine::assertFact(TNode literal
)
1092 Trace("theory") << "TheoryEngine::assertFact(" << literal
<< ")" << endl
;
1094 d_propEngine
->checkTime();
1096 // If we're in conflict, nothing to do
1102 bool polarity
= literal
.getKind() != kind::NOT
;
1103 TNode atom
= polarity
? literal
: literal
[0];
1105 if (d_logicInfo
.isSharingEnabled()) {
1107 // If any shared terms, it's time to do sharing work
1108 if (d_sharedTerms
.hasSharedTerms(atom
)) {
1109 // Notify the theories the shared terms
1110 SharedTermsDatabase::shared_terms_iterator it
= d_sharedTerms
.begin(atom
);
1111 SharedTermsDatabase::shared_terms_iterator it_end
= d_sharedTerms
.end(atom
);
1112 for (; it
!= it_end
; ++ it
) {
1114 Theory::Set theories
= d_sharedTerms
.getTheoriesToNotify(atom
, term
);
1115 for (TheoryId id
= THEORY_FIRST
; id
!= THEORY_LAST
; ++ id
) {
1116 if (Theory::setContains(id
, theories
)) {
1117 theoryOf(id
)->addSharedTermInternal(term
);
1120 d_sharedTerms
.markNotified(term
, theories
);
1124 // If it's an equality, assert it to the shared term manager, even though the terms are not
1125 // yet shared. As the terms become shared later, the shared terms manager will then add them
1126 // to the assert the equality to the interested theories
1127 if (atom
.getKind() == kind::EQUAL
) {
1128 // Assert it to the the owning theory
1129 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1130 // Shared terms manager will assert to interested theories directly, as the terms become shared
1131 assertToTheory(literal
, literal
, /* to */ THEORY_BUILTIN
, /* from */ THEORY_SAT_SOLVER
);
1133 // Now, let's check for any atom triggers from lemmas
1134 AtomRequests::atom_iterator it
= d_atomRequests
.getAtomIterator(atom
);
1135 while (!it
.done()) {
1136 const AtomRequests::Request
& request
= it
.get();
1137 Node toAssert
= polarity
? (Node
) request
.atom
: request
.atom
.notNode();
1138 Debug("theory::atoms") << "TheoryEngine::assertFact(" << literal
<< "): sending requested " << toAssert
<< endl
;
1139 assertToTheory(toAssert
, literal
, request
.toTheory
, THEORY_SAT_SOLVER
);
1144 // Not an equality, just assert to the appropriate theory
1145 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1148 // Assert the fact to the appropriate theory directly
1149 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1153 bool TheoryEngine::propagate(TNode literal
, theory::TheoryId theory
) {
1155 Debug("theory::propagate") << "TheoryEngine::propagate(" << literal
<< ", " << theory
<< ")" << endl
;
1157 d_propEngine
->checkTime();
1159 if(Dump
.isOn("t-propagations")) {
1160 Dump("t-propagations") << CommentCommand("negation of theory propagation: expect valid")
1161 << QueryCommand(literal
.toExpr());
1163 if(Dump
.isOn("missed-t-propagations")) {
1164 d_hasPropagated
.insert(literal
);
1168 bool polarity
= literal
.getKind() != kind::NOT
;
1169 TNode atom
= polarity
? literal
: literal
[0];
1171 if (d_logicInfo
.isSharingEnabled() && atom
.getKind() == kind::EQUAL
) {
1172 if (d_propEngine
->isSatLiteral(literal
)) {
1173 // We propagate SAT literals to SAT
1174 assertToTheory(literal
, literal
, /* to */ THEORY_SAT_SOLVER
, /* from */ theory
);
1176 if (theory
!= THEORY_BUILTIN
) {
1177 // Assert to the shared terms database
1178 assertToTheory(literal
, literal
, /* to */ THEORY_BUILTIN
, /* from */ theory
);
1181 // Just send off to the SAT solver
1182 Assert(d_propEngine
->isSatLiteral(literal
));
1183 assertToTheory(literal
, literal
, /* to */ THEORY_SAT_SOLVER
, /* from */ theory
);
1186 return !d_inConflict
;
1190 theory::EqualityStatus
TheoryEngine::getEqualityStatus(TNode a
, TNode b
) {
1191 Assert(a
.getType().isComparableTo(b
.getType()));
1192 if (d_sharedTerms
.isShared(a
) && d_sharedTerms
.isShared(b
)) {
1193 if (d_sharedTerms
.areEqual(a
,b
)) {
1194 return EQUALITY_TRUE_AND_PROPAGATED
;
1196 else if (d_sharedTerms
.areDisequal(a
,b
)) {
1197 return EQUALITY_FALSE_AND_PROPAGATED
;
1200 return theoryOf(Theory::theoryOf(a
.getType()))->getEqualityStatus(a
, b
);
1203 Node
TheoryEngine::getModelValue(TNode var
) {
1204 Assert(d_sharedTerms
.isShared(var
));
1205 return theoryOf(Theory::theoryOf(var
.getType()))->getModelValue(var
);
1209 Node
TheoryEngine::ensureLiteral(TNode n
) {
1210 Debug("ensureLiteral") << "rewriting: " << n
<< std::endl
;
1211 Node rewritten
= Rewriter::rewrite(n
);
1212 Debug("ensureLiteral") << " got: " << rewritten
<< std::endl
;
1213 Node preprocessed
= preprocess(rewritten
);
1214 Debug("ensureLiteral") << "preprocessed: " << preprocessed
<< std::endl
;
1215 d_propEngine
->ensureLiteral(preprocessed
);
1216 return preprocessed
;
1220 void TheoryEngine::printInstantiations( std::ostream
& out
) {
1221 if( d_quantEngine
){
1222 d_quantEngine
->printInstantiations( out
);
1226 static Node
mkExplanation(const std::vector
<NodeTheoryPair
>& explanation
) {
1228 std::set
<TNode
> all
;
1229 for (unsigned i
= 0; i
< explanation
.size(); ++ i
) {
1230 Assert(explanation
[i
].theory
== THEORY_SAT_SOLVER
);
1231 all
.insert(explanation
[i
].node
);
1234 if (all
.size() == 0) {
1235 // Normalize to true
1236 return NodeManager::currentNM()->mkConst
<bool>(true);
1239 if (all
.size() == 1) {
1240 // All the same, or just one
1241 return explanation
[0].node
;
1244 NodeBuilder
<> conjunction(kind::AND
);
1245 std::set
<TNode
>::const_iterator it
= all
.begin();
1246 std::set
<TNode
>::const_iterator it_end
= all
.end();
1247 while (it
!= it_end
) {
1256 Node
TheoryEngine::getExplanation(TNode node
) {
1257 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
<< "): current propagation index = " << d_propagationMapTimestamp
<< endl
;
1259 bool polarity
= node
.getKind() != kind::NOT
;
1260 TNode atom
= polarity
? node
: node
[0];
1262 // If we're not in shared mode, explanations are simple
1263 if (!d_logicInfo
.isSharingEnabled()) {
1264 Node explanation
= theoryOf(atom
)->explain(node
);
1265 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
<< ") => " << explanation
<< endl
;
1269 // Initial thing to explain
1270 NodeTheoryPair
toExplain(node
, THEORY_SAT_SOLVER
, d_propagationMapTimestamp
);
1271 Assert(d_propagationMap
.find(toExplain
) != d_propagationMap
.end());
1272 // Create the workplace for explanations
1273 std::vector
<NodeTheoryPair
> explanationVector
;
1274 explanationVector
.push_back(d_propagationMap
[toExplain
]);
1275 // Process the explanation
1276 getExplanation(explanationVector
);
1277 Node explanation
= mkExplanation(explanationVector
);
1279 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
<< ") => " << explanation
<< endl
;
1284 struct AtomsCollect
{
1286 std::vector
<TNode
> d_atoms
;
1287 std::hash_set
<TNode
, TNodeHashFunction
> d_visited
;
1291 typedef void return_type
;
1293 bool alreadyVisited(TNode current
, TNode parent
) {
1294 // Check if already visited
1295 if (d_visited
.find(current
) != d_visited
.end()) return true;
1296 // Don't visit non-boolean
1297 if (!current
.getType().isBoolean()) return true;
1302 void visit(TNode current
, TNode parent
) {
1303 if (Theory::theoryOf(current
) != theory::THEORY_BOOL
) {
1304 d_atoms
.push_back(current
);
1306 d_visited
.insert(current
);
1309 void start(TNode node
) {}
1310 void done(TNode node
) {}
1312 std::vector
<TNode
> getAtoms() const {
1317 void TheoryEngine::ensureLemmaAtoms(const std::vector
<TNode
>& atoms
, theory::TheoryId atomsTo
) {
1318 for (unsigned i
= 0; i
< atoms
.size(); ++ i
) {
1320 // Non-equality atoms are either owned by theory or they don't make sense
1321 if (atoms
[i
].getKind() != kind::EQUAL
) {
1327 // Simple normalization to not repeat stuff
1328 if (eq
[0] > eq
[1]) {
1329 eq
= eq
[1].eqNode(eq
[0]);
1332 // Rewrite the equality
1333 Node eqNormalized
= Rewriter::rewrite(atoms
[i
]);
1335 Debug("theory::atoms") << "TheoryEngine::ensureLemmaAtoms(): " << eq
<< " with nf " << eqNormalized
<< endl
;
1337 // If the equality is a boolean constant, we send immediately
1338 if (eqNormalized
.isConst()) {
1339 if (eqNormalized
.getConst
<bool>()) {
1340 assertToTheory(eq
, eqNormalized
, /** to */ atomsTo
, /** Sat solver */ theory::THEORY_SAT_SOLVER
);
1342 assertToTheory(eq
.notNode(), eqNormalized
.notNode(), /** to */ atomsTo
, /** Sat solver */ theory::THEORY_SAT_SOLVER
);
1347 Assert(eqNormalized
.getKind() == kind::EQUAL
);
1350 // If the normalization did the just flips, keep the flip
1351 if (eqNormalized
[0] == eq
[1] && eqNormalized
[1] == eq
[0]) {
1355 // Check if the equality is already known by the sat solver
1356 if (d_propEngine
->isSatLiteral(eqNormalized
)) {
1358 if (d_propEngine
->hasValue(eqNormalized
, value
)) {
1360 assertToTheory(eq
, eqNormalized
, atomsTo
, theory::THEORY_SAT_SOLVER
);
1363 assertToTheory(eq
.notNode(), eqNormalized
.notNode(), atomsTo
, theory::THEORY_SAT_SOLVER
);
1369 // If the theory is asking about a different form, or the form is ok but if will go to a different theory
1370 // then we must figure it out
1371 if (eqNormalized
!= eq
|| Theory::theoryOf(eq
) != atomsTo
) {
1372 // If you get eqNormalized, send atoms[i] to atomsTo
1373 d_atomRequests
.add(eqNormalized
, eq
, atomsTo
);
1378 theory::LemmaStatus
TheoryEngine::lemma(TNode node
, bool negated
, bool removable
, bool preprocess
, theory::TheoryId atomsTo
) {
1379 // For resource-limiting (also does a time check).
1382 // Do we need to check atoms
1383 if (atomsTo
!= theory::THEORY_LAST
) {
1384 Debug("theory::atoms") << "TheoryEngine::lemma(" << node
<< ", " << atomsTo
<< ")" << endl
;
1385 AtomsCollect collectAtoms
;
1386 NodeVisitor
<AtomsCollect
>::run(collectAtoms
, node
);
1387 ensureLemmaAtoms(collectAtoms
.getAtoms(), atomsTo
);
1390 if(Dump
.isOn("t-lemmas")) {
1395 Dump("t-lemmas") << CommentCommand("theory lemma: expect valid")
1396 << QueryCommand(n
.toExpr());
1399 // Share with other portfolio threads
1400 if(options::lemmaOutputChannel() != NULL
) {
1401 options::lemmaOutputChannel()->notifyNewLemma(node
.toExpr());
1404 // Run theory preprocessing, maybe
1405 Node ppNode
= preprocess
? this->preprocess(node
) : Node(node
);
1408 std::vector
<Node
> additionalLemmas
;
1409 IteSkolemMap iteSkolemMap
;
1410 additionalLemmas
.push_back(ppNode
);
1411 d_iteRemover
.run(additionalLemmas
, iteSkolemMap
);
1412 additionalLemmas
[0] = theory::Rewriter::rewrite(additionalLemmas
[0]);
1414 if(Debug
.isOn("lemma-ites")) {
1415 Debug("lemma-ites") << "removed ITEs from lemma: " << ppNode
<< endl
;
1416 Debug("lemma-ites") << " + now have the following "
1417 << additionalLemmas
.size() << " lemma(s):" << endl
;
1418 for(std::vector
<Node
>::const_iterator i
= additionalLemmas
.begin();
1419 i
!= additionalLemmas
.end();
1421 Debug("lemma-ites") << " + " << *i
<< endl
;
1423 Debug("lemma-ites") << endl
;
1426 // assert to prop engine
1427 d_propEngine
->assertLemma(additionalLemmas
[0], negated
, removable
, RULE_INVALID
, node
);
1428 for (unsigned i
= 1; i
< additionalLemmas
.size(); ++ i
) {
1429 additionalLemmas
[i
] = theory::Rewriter::rewrite(additionalLemmas
[i
]);
1430 d_propEngine
->assertLemma(additionalLemmas
[i
], false, removable
, RULE_INVALID
, node
);
1433 // WARNING: Below this point don't assume additionalLemmas[0] to be not negated.
1435 additionalLemmas
[0] = additionalLemmas
[0].notNode();
1439 // assert to decision engine
1441 d_decisionEngine
->addAssertions(additionalLemmas
, 1, iteSkolemMap
);
1444 // Mark that we added some lemmas
1445 d_lemmasAdded
= true;
1447 // Lemma analysis isn't online yet; this lemma may only live for this
1449 return theory::LemmaStatus(additionalLemmas
[0], d_userContext
->getLevel());
1452 void TheoryEngine::conflict(TNode conflict
, TheoryId theoryId
) {
1454 Debug("theory::conflict") << "TheoryEngine::conflict(" << conflict
<< ", " << theoryId
<< ")" << endl
;
1456 // Mark that we are in conflict
1457 d_inConflict
= true;
1459 if(Dump
.isOn("t-conflicts")) {
1460 Dump("t-conflicts") << CommentCommand("theory conflict: expect unsat")
1461 << CheckSatCommand(conflict
.toExpr());
1464 // In the multiple-theories case, we need to reconstruct the conflict
1465 if (d_logicInfo
.isSharingEnabled()) {
1466 // Create the workplace for explanations
1467 std::vector
<NodeTheoryPair
> explanationVector
;
1468 explanationVector
.push_back(NodeTheoryPair(conflict
, theoryId
, d_propagationMapTimestamp
));
1469 // Process the explanation
1470 getExplanation(explanationVector
);
1471 Node fullConflict
= mkExplanation(explanationVector
);
1472 Debug("theory::conflict") << "TheoryEngine::conflict(" << conflict
<< ", " << theoryId
<< "): full = " << fullConflict
<< endl
;
1473 Assert(properConflict(fullConflict
));
1474 lemma(fullConflict
, true, true, false, THEORY_LAST
);
1476 // When only one theory, the conflict should need no processing
1477 Assert(properConflict(conflict
));
1478 lemma(conflict
, true, true, false, THEORY_LAST
);
1482 void TheoryEngine::staticInitializeBVOptions(const std::vector
<Node
>& assertions
) {
1483 bool useSlicer
= true;
1484 if (options::bitvectorEqualitySlicer() == bv::BITVECTOR_SLICER_ON
) {
1485 if (options::incrementalSolving())
1486 throw ModalException("Slicer does not currently support incremental mode. Use --bv-eq-slicer=off");
1487 if (options::produceModels())
1488 throw ModalException("Slicer does not currently support model generation. Use --bv-eq-slicer=off");
1491 } else if (options::bitvectorEqualitySlicer() == bv::BITVECTOR_SLICER_OFF
) {
1494 } else if (options::bitvectorEqualitySlicer() == bv::BITVECTOR_SLICER_AUTO
) {
1495 if (options::incrementalSolving() ||
1496 options::produceModels())
1500 bv::utils::TNodeBoolMap cache
;
1501 for (unsigned i
= 0; i
< assertions
.size(); ++i
) {
1502 useSlicer
= useSlicer
&& bv::utils::isCoreTerm(assertions
[i
], cache
);
1507 bv::TheoryBV
* bv_theory
= (bv::TheoryBV
*)d_theoryTable
[THEORY_BV
];
1508 bv_theory
->enableCoreTheorySlicer();
1513 void TheoryEngine::ppBvToBool(const std::vector
<Node
>& assertions
, std::vector
<Node
>& new_assertions
) {
1514 d_bvToBoolPreprocessor
.liftBvToBool(assertions
, new_assertions
);
1517 bool TheoryEngine::ppBvAbstraction(const std::vector
<Node
>& assertions
, std::vector
<Node
>& new_assertions
) {
1518 bv::TheoryBV
* bv_theory
= (bv::TheoryBV
*)d_theoryTable
[THEORY_BV
];
1519 return bv_theory
->applyAbstraction(assertions
, new_assertions
);
1522 void TheoryEngine::mkAckermanizationAsssertions(std::vector
<Node
>& assertions
) {
1523 bv::TheoryBV
* bv_theory
= (bv::TheoryBV
*)d_theoryTable
[THEORY_BV
];
1524 bv_theory
->mkAckermanizationAsssertions(assertions
);
1527 Node
TheoryEngine::ppSimpITE(TNode assertion
)
1529 if(!d_iteRemover
.containsTermITE(assertion
)){
1533 Node result
= d_iteUtilities
->simpITE(assertion
);
1534 Node res_rewritten
= Rewriter::rewrite(result
);
1536 if(options::simplifyWithCareEnabled()){
1537 Chat() << "starting simplifyWithCare()" << endl
;
1538 Node postSimpWithCare
= d_iteUtilities
->simplifyWithCare(res_rewritten
);
1539 Chat() << "ending simplifyWithCare()"
1540 << " post simplifyWithCare()" << postSimpWithCare
.getId() << endl
;
1541 result
= Rewriter::rewrite(postSimpWithCare
);
1543 result
= res_rewritten
;
1550 bool TheoryEngine::donePPSimpITE(std::vector
<Node
>& assertions
){
1552 bool simpDidALotOfWork
= d_iteUtilities
->simpIteDidALotOfWorkHeuristic();
1553 if(simpDidALotOfWork
){
1554 if(options::compressItes()){
1555 result
= d_iteUtilities
->compress(assertions
);
1559 // if false, don't bother to reclaim memory here.
1560 NodeManager
* nm
= NodeManager::currentNM();
1561 if(nm
->poolSize() >= options::zombieHuntThreshold()){
1562 Chat() << "..ite simplifier did quite a bit of work.. " << nm
->poolSize() << endl
;
1563 Chat() << "....node manager contains " << nm
->poolSize() << " nodes before cleanup" << endl
;
1564 d_iteUtilities
->clear();
1565 Rewriter::garbageCollect();
1566 d_iteRemover
.garbageCollect();
1567 nm
->reclaimZombiesUntil(options::zombieHuntThreshold());
1568 Chat() << "....node manager contains " << nm
->poolSize() << " nodes after cleanup" << endl
;
1573 // Do theory specific preprocessing passes
1574 if(d_logicInfo
.isTheoryEnabled(theory::THEORY_ARITH
)){
1575 if(!simpDidALotOfWork
){
1576 ContainsTermITEVisitor
& contains
= *d_iteRemover
.getContainsVisitor();
1577 arith::ArithIteUtils
aiteu(contains
, d_userContext
, getModel());
1578 bool anyItes
= false;
1579 for(size_t i
= 0; i
< assertions
.size(); ++i
){
1580 Node curr
= assertions
[i
];
1581 if(contains
.containsTermITE(curr
)){
1583 Node res
= aiteu
.reduceVariablesInItes(curr
);
1584 Debug("arith::ite::red") << "@ " << i
<< " ... " << curr
<< endl
<< " ->" << res
<< endl
;
1586 Node more
= aiteu
.reduceConstantIteByGCD(res
);
1587 Debug("arith::ite::red") << " gcd->" << more
<< endl
;
1588 assertions
[i
] = more
;
1593 unsigned prevSubCount
= aiteu
.getSubCount();
1594 aiteu
.learnSubstitutions(assertions
);
1595 if(prevSubCount
< aiteu
.getSubCount()){
1596 d_arithSubstitutionsAdded
+= aiteu
.getSubCount() - prevSubCount
;
1597 bool anySuccess
= false;
1598 for(size_t i
= 0, N
= assertions
.size(); i
< N
; ++i
){
1599 Node curr
= assertions
[i
];
1600 Node next
= Rewriter::rewrite(aiteu
.applySubstitutions(curr
));
1601 Node res
= aiteu
.reduceVariablesInItes(next
);
1602 Debug("arith::ite::red") << "@ " << i
<< " ... " << next
<< endl
<< " ->" << res
<< endl
;
1603 Node more
= aiteu
.reduceConstantIteByGCD(res
);
1604 Debug("arith::ite::red") << " gcd->" << more
<< endl
;
1610 for(size_t i
= 0, N
= assertions
.size(); anySuccess
&& i
< N
; ++i
){
1611 Node curr
= assertions
[i
];
1612 Node next
= Rewriter::rewrite(aiteu
.applySubstitutions(curr
));
1613 Node res
= aiteu
.reduceVariablesInItes(next
);
1614 Debug("arith::ite::red") << "@ " << i
<< " ... " << next
<< endl
<< " ->" << res
<< endl
;
1615 Node more
= aiteu
.reduceConstantIteByGCD(res
);
1616 Debug("arith::ite::red") << " gcd->" << more
<< endl
;
1617 assertions
[i
] = Rewriter::rewrite(more
);
1626 void TheoryEngine::getExplanation(std::vector
<NodeTheoryPair
>& explanationVector
)
1628 Assert(explanationVector
.size() > 0);
1630 unsigned i
= 0; // Index of the current literal we are processing
1631 unsigned j
= 0; // Index of the last literal we are keeping
1633 while (i
< explanationVector
.size()) {
1635 // Get the current literal to explain
1636 NodeTheoryPair toExplain
= explanationVector
[i
];
1638 Debug("theory::explain") << "TheoryEngine::explain(): processing [" << toExplain
.timestamp
<< "] " << toExplain
.node
<< " sent from " << toExplain
.theory
<< endl
;
1640 // If a true constant or a negation of a false constant we can ignore it
1641 if (toExplain
.node
.isConst() && toExplain
.node
.getConst
<bool>()) {
1645 if (toExplain
.node
.getKind() == kind::NOT
&& toExplain
.node
[0].isConst() && !toExplain
.node
[0].getConst
<bool>()) {
1650 // If from the SAT solver, keep it
1651 if (toExplain
.theory
== THEORY_SAT_SOLVER
) {
1652 explanationVector
[j
++] = explanationVector
[i
++];
1656 // If an and, expand it
1657 if (toExplain
.node
.getKind() == kind::AND
) {
1658 Debug("theory::explain") << "TheoryEngine::explain(): expanding " << toExplain
.node
<< " got from " << toExplain
.theory
<< endl
;
1659 for (unsigned k
= 0; k
< toExplain
.node
.getNumChildren(); ++ k
) {
1660 NodeTheoryPair
newExplain(toExplain
.node
[k
], toExplain
.theory
, toExplain
.timestamp
);
1661 explanationVector
.push_back(newExplain
);
1667 // See if it was sent to the theory by another theory
1668 PropagationMap::const_iterator find
= d_propagationMap
.find(toExplain
);
1669 if (find
!= d_propagationMap
.end()) {
1670 // There is some propagation, check if its a timely one
1671 if ((*find
).second
.timestamp
< toExplain
.timestamp
) {
1672 explanationVector
.push_back((*find
).second
);
1678 // It was produced by the theory, so ask for an explanation
1680 if (toExplain
.theory
== THEORY_BUILTIN
) {
1681 explanation
= d_sharedTerms
.explain(toExplain
.node
);
1683 explanation
= theoryOf(toExplain
.theory
)->explain(toExplain
.node
);
1685 Debug("theory::explain") << "TheoryEngine::explain(): got explanation " << explanation
<< " got from " << toExplain
.theory
<< endl
;
1686 Assert(explanation
!= toExplain
.node
, "wasn't sent to you, so why are you explaining it trivially");
1687 // Mark the explanation
1688 NodeTheoryPair
newExplain(explanation
, toExplain
.theory
, toExplain
.timestamp
);
1689 explanationVector
.push_back(newExplain
);
1693 // Keep only the relevant literals
1694 explanationVector
.resize(j
);
1698 void TheoryEngine::ppUnconstrainedSimp(vector
<Node
>& assertions
)
1700 d_unconstrainedSimp
->processAssertions(assertions
);
1704 void TheoryEngine::setUserAttribute(const std::string
& attr
, Node n
, std::vector
<Node
> node_values
, std::string str_value
) {
1705 Trace("te-attr") << "set user attribute " << attr
<< " " << n
<< endl
;
1706 if( d_attr_handle
.find( attr
)!=d_attr_handle
.end() ){
1707 for( size_t i
=0; i
<d_attr_handle
[attr
].size(); i
++ ){
1708 d_attr_handle
[attr
][i
]->setUserAttribute(attr
, n
, node_values
, str_value
);
1711 //unhandled exception?
1715 void TheoryEngine::handleUserAttribute(const char* attr
, Theory
* t
) {
1716 Trace("te-attr") << "Handle user attribute " << attr
<< " " << t
<< endl
;
1717 std::string
str( attr
);
1718 d_attr_handle
[ str
].push_back( t
);
1721 void TheoryEngine::checkTheoryAssertionsWithModel() {
1722 for(TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
1723 Theory
* theory
= d_theoryTable
[theoryId
];
1724 if(theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
1725 for(context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(),
1726 it_end
= theory
->facts_end();
1729 Node assertion
= (*it
).assertion
;
1730 Node val
= getModel()->getValue(assertion
);
1733 ss
<< theoryId
<< " has an asserted fact that the model doesn't satisfy." << endl
1734 << "The fact: " << assertion
<< endl
1735 << "Model value: " << val
<< endl
;
1736 InternalError(ss
.str());
1743 std::pair
<bool, Node
> TheoryEngine::entailmentCheck(theory::TheoryOfMode mode
, TNode lit
, const EntailmentCheckParameters
* params
, EntailmentCheckSideEffects
* seffects
) {
1744 TNode atom
= (lit
.getKind() == kind::NOT
) ? lit
[0] : lit
;
1745 theory::TheoryId tid
= theory::Theory::theoryOf(mode
, atom
);
1746 theory::Theory
* th
= theoryOf(tid
);
1749 Assert(params
== NULL
|| tid
== params
->getTheoryId());
1750 Assert(seffects
== NULL
|| tid
== seffects
->getTheoryId());
1752 return th
->entailmentCheck(lit
, params
, seffects
);