1 /********************* */
2 /*! \file theory_engine.cpp
4 ** Top contributors (to current version):
5 ** Dejan Jovanovic, Andrew Reynolds, Morgan Deters
6 ** This file is part of the CVC4 project.
7 ** Copyright (c) 2009-2020 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/decision_manager.h"
45 #include "theory/ee_manager_distributed.h"
46 #include "theory/quantifiers/first_order_model.h"
47 #include "theory/quantifiers/fmf/model_engine.h"
48 #include "theory/quantifiers/theory_quantifiers.h"
49 #include "theory/quantifiers_engine.h"
50 #include "theory/relevance_manager.h"
51 #include "theory/rewriter.h"
52 #include "theory/theory.h"
53 #include "theory/theory_model.h"
54 #include "theory/theory_traits.h"
55 #include "theory/uf/equality_engine.h"
56 #include "util/resource_manager.h"
60 using namespace CVC4::preprocessing
;
61 using namespace CVC4::theory
;
65 /* -------------------------------------------------------------------------- */
70 * IMPORTANT: The order of the theories is important. For example, strings
71 * depends on arith, quantifiers needs to come as the very last.
72 * Do not change this order.
75 #define CVC4_FOR_EACH_THEORY \
76 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BUILTIN) \
77 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BOOL) \
78 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_UF) \
79 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_ARITH) \
80 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BV) \
81 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_FP) \
82 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_ARRAYS) \
83 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_DATATYPES) \
84 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_SEP) \
85 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_SETS) \
86 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_STRINGS) \
87 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_QUANTIFIERS)
91 /* -------------------------------------------------------------------------- */
93 inline void flattenAnd(Node n
, std::vector
<TNode
>& out
){
94 Assert(n
.getKind() == kind::AND
);
95 for(Node::iterator i
=n
.begin(), i_end
=n
.end(); i
!= i_end
; ++i
){
97 if(curr
.getKind() == kind::AND
){
98 flattenAnd(curr
, out
);
105 inline Node
flattenAnd(Node n
){
106 std::vector
<TNode
> out
;
108 return NodeManager::currentNM()->mkNode(kind::AND
, out
);
112 * Compute the string for a given theory id. In this module, we use
113 * THEORY_SAT_SOLVER as an id, which is not a normal id but maps to
114 * THEORY_LAST. Thus, we need our own string conversion here.
116 * @param id The theory id
117 * @return The string corresponding to the theory id
119 std::string
getTheoryString(theory::TheoryId id
)
121 if (id
== theory::THEORY_SAT_SOLVER
)
123 return "THEORY_SAT_SOLVER";
127 std::stringstream ss
;
133 void TheoryEngine::finishInit() {
134 // initialize the quantifiers engine
135 if (d_logicInfo
.isQuantified())
137 // initialize the quantifiers engine
138 d_quantEngine
= new QuantifiersEngine(d_context
, d_userContext
, this);
141 // Initialize the equality engine architecture for all theories, which
142 // includes the master equality engine.
143 d_eeDistributed
.reset(new EqEngineManagerDistributed(*this));
144 d_eeDistributed
->initializeTheories();
146 // Initialize the model and model builder.
147 if (d_logicInfo
.isQuantified())
149 d_curr_model_builder
= d_quantEngine
->getModelBuilder();
150 d_curr_model
= d_quantEngine
->getModel();
152 d_curr_model
= new theory::TheoryModel(
153 d_userContext
, "DefaultModel", options::assignFunctionValues());
154 d_aloc_curr_model
= true;
156 // create the relevance filter if any option requires it
157 if (options::relevanceFilter())
160 new RelevanceManager(d_userContext
, theory::Valuation(this)));
163 //make the default builder, e.g. in the case that the quantifiers engine does not have a model builder
164 if( d_curr_model_builder
==NULL
){
165 d_curr_model_builder
= new theory::TheoryEngineModelBuilder(this);
166 d_aloc_curr_model_builder
= true;
169 // Initialize the model
170 // !!!! temporary, will be part of combination engine initialization
171 d_eeDistributed
->initializeModel(d_curr_model
, nullptr);
173 // set the core equality engine on quantifiers engine
174 if (d_logicInfo
.isQuantified())
176 d_quantEngine
->setMasterEqualityEngine(
177 d_eeDistributed
->getCoreEqualityEngine());
180 // finish initializing the theories
181 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
; ++ theoryId
) {
182 Theory
* t
= d_theoryTable
[theoryId
];
187 // setup the pointers to the utilities
188 const EeTheoryInfo
* eeti
= d_eeDistributed
->getEeTheoryInfo(theoryId
);
189 Assert(eeti
!= nullptr);
190 // the theory's official equality engine is the one specified by the
191 // equality engine manager
192 t
->setEqualityEngine(eeti
->d_usedEe
);
193 // set the quantifiers engine
194 t
->setQuantifiersEngine(d_quantEngine
);
195 // set the decision manager for the theory
196 t
->setDecisionManager(d_decManager
.get());
197 // finish initializing the theory
202 TheoryEngine::TheoryEngine(context::Context
* context
,
203 context::UserContext
* userContext
,
205 RemoveTermFormulas
& iteRemover
,
206 const LogicInfo
& logicInfo
)
207 : d_propEngine(nullptr),
209 d_userContext(userContext
),
210 d_logicInfo(logicInfo
),
211 d_sharedTerms(this, context
),
212 d_eeDistributed(nullptr),
213 d_quantEngine(nullptr),
214 d_decManager(new DecisionManager(userContext
)),
215 d_relManager(nullptr),
216 d_curr_model(nullptr),
217 d_aloc_curr_model(false),
218 d_curr_model_builder(nullptr),
219 d_aloc_curr_model_builder(false),
220 d_eager_model_building(false),
221 d_possiblePropagations(context
),
222 d_hasPropagated(context
),
223 d_inConflict(context
, false),
225 d_hasShutDown(false),
226 d_incomplete(context
, false),
227 d_propagationMap(context
),
228 d_propagationMapTimestamp(context
, 0),
229 d_propagatedLiterals(context
),
230 d_propagatedLiteralsIndex(context
, 0),
231 d_atomRequests(context
),
232 d_tpp(*this, iteRemover
),
233 d_combineTheoriesTime("TheoryEngine::combineTheoriesTime"),
236 d_interrupted(false),
237 d_resourceManager(rm
),
238 d_inPreregister(false),
239 d_factsAsserted(context
, false),
240 d_preRegistrationVisitor(this, context
),
241 d_sharedTermsVisitor(d_sharedTerms
),
243 d_arithSubstitutionsAdded("theory::arith::zzz::arith::substitutions", 0)
245 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
;
248 d_theoryTable
[theoryId
] = NULL
;
249 d_theoryOut
[theoryId
] = NULL
;
252 smtStatisticsRegistry()->registerStat(&d_combineTheoriesTime
);
253 d_true
= NodeManager::currentNM()->mkConst
<bool>(true);
254 d_false
= NodeManager::currentNM()->mkConst
<bool>(false);
257 ProofManager::currentPM()->initTheoryProofEngine();
260 smtStatisticsRegistry()->registerStat(&d_arithSubstitutionsAdded
);
263 TheoryEngine::~TheoryEngine() {
264 Assert(d_hasShutDown
);
266 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
; ++ theoryId
) {
267 if(d_theoryTable
[theoryId
] != NULL
) {
268 delete d_theoryTable
[theoryId
];
269 delete d_theoryOut
[theoryId
];
273 if( d_aloc_curr_model_builder
){
274 delete d_curr_model_builder
;
276 if( d_aloc_curr_model
){
280 delete d_quantEngine
;
282 smtStatisticsRegistry()->unregisterStat(&d_combineTheoriesTime
);
283 smtStatisticsRegistry()->unregisterStat(&d_arithSubstitutionsAdded
);
286 void TheoryEngine::interrupt() { d_interrupted
= true; }
287 void TheoryEngine::preRegister(TNode preprocessed
) {
289 Debug("theory") << "TheoryEngine::preRegister( " << preprocessed
<< ")" << std::endl
;
290 if(Dump
.isOn("missed-t-propagations")) {
291 d_possiblePropagations
.push_back(preprocessed
);
293 d_preregisterQueue
.push(preprocessed
);
295 if (!d_inPreregister
) {
296 // We're in pre-register
297 d_inPreregister
= true;
299 // Process the pre-registration queue
300 while (!d_preregisterQueue
.empty()) {
301 // Get the next atom to pre-register
302 preprocessed
= d_preregisterQueue
.front();
303 d_preregisterQueue
.pop();
305 if (d_logicInfo
.isSharingEnabled() && preprocessed
.getKind() == kind::EQUAL
) {
306 // When sharing is enabled, we propagate from the shared terms manager also
307 d_sharedTerms
.addEqualityToPropagate(preprocessed
);
310 // the atom should not have free variables
311 Debug("theory") << "TheoryEngine::preRegister: " << preprocessed
313 Assert(!expr::hasFreeVar(preprocessed
));
314 // Pre-register the terms in the atom
315 Theory::Set theories
= NodeVisitor
<PreRegisterVisitor
>::run(d_preRegistrationVisitor
, preprocessed
);
316 theories
= Theory::setRemove(THEORY_BOOL
, theories
);
317 // Remove the top theory, if any more that means multiple theories were involved
318 bool multipleTheories
= Theory::setRemove(Theory::theoryOf(preprocessed
), theories
);
320 // These checks don't work with finite model finding, because it
321 // uses Rational constants to represent cardinality constraints,
322 // even though arithmetic isn't actually involved.
323 if(!options::finiteModelFind()) {
324 while((i
= Theory::setPop(theories
)) != THEORY_LAST
) {
325 if(!d_logicInfo
.isTheoryEnabled(i
)) {
326 LogicInfo newLogicInfo
= d_logicInfo
.getUnlockedCopy();
327 newLogicInfo
.enableTheory(i
);
330 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
331 << ", which doesn't include " << i
332 << ", but found a term in that theory." << endl
333 << "You might want to extend your logic to "
334 << newLogicInfo
.getLogicString() << endl
;
335 throw LogicException(ss
.str());
339 if (multipleTheories
) {
340 // Collect the shared terms if there are multiple theories
341 NodeVisitor
<SharedTermsVisitor
>::run(d_sharedTermsVisitor
, preprocessed
);
345 // Leaving pre-register
346 d_inPreregister
= false;
350 void TheoryEngine::printAssertions(const char* tag
) {
351 if (Trace
.isOn(tag
)) {
353 for (TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
354 Theory
* theory
= d_theoryTable
[theoryId
];
355 if (theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
356 Trace(tag
) << "--------------------------------------------" << endl
;
357 Trace(tag
) << "Assertions of " << theory
->getId() << ": " << endl
;
359 context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(),
362 for (unsigned i
= 0; it
!= it_end
; ++it
, ++i
)
364 if ((*it
).d_isPreregistered
)
366 Trace(tag
) << "[" << i
<< "]: ";
370 Trace(tag
) << "(" << i
<< "): ";
372 Trace(tag
) << (*it
).d_assertion
<< endl
;
376 if (d_logicInfo
.isSharingEnabled()) {
377 Trace(tag
) << "Shared terms of " << theory
->getId() << ": " << endl
;
378 context::CDList
<TNode
>::const_iterator it
= theory
->shared_terms_begin(), it_end
= theory
->shared_terms_end();
379 for (unsigned i
= 0; it
!= it_end
; ++ it
, ++i
) {
380 Trace(tag
) << "[" << i
<< "]: " << (*it
) << endl
;
388 void TheoryEngine::dumpAssertions(const char* tag
) {
389 if (Dump
.isOn(tag
)) {
390 Dump(tag
) << CommentCommand("Starting completeness check");
391 for (TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
392 Theory
* theory
= d_theoryTable
[theoryId
];
393 if (theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
394 Dump(tag
) << CommentCommand("Completeness check");
395 Dump(tag
) << PushCommand();
397 // Dump the shared terms
398 if (d_logicInfo
.isSharingEnabled()) {
399 Dump(tag
) << CommentCommand("Shared terms");
400 context::CDList
<TNode
>::const_iterator it
= theory
->shared_terms_begin(), it_end
= theory
->shared_terms_end();
401 for (unsigned i
= 0; it
!= it_end
; ++ it
, ++i
) {
404 Dump(tag
) << CommentCommand(ss
.str());
408 // Dump the assertions
409 Dump(tag
) << CommentCommand("Assertions");
410 context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(), it_end
= theory
->facts_end();
411 for (; it
!= it_end
; ++ it
) {
413 Node assertionNode
= (*it
).d_assertion
;
414 // Purify all the terms
416 if ((*it
).d_isPreregistered
)
418 Dump(tag
) << CommentCommand("Preregistered");
422 Dump(tag
) << CommentCommand("Shared assertion");
424 Dump(tag
) << AssertCommand(assertionNode
.toExpr());
426 Dump(tag
) << CheckSatCommand();
428 Dump(tag
) << PopCommand();
435 * Check all (currently-active) theories for conflicts.
436 * @param effort the effort level to use
438 void TheoryEngine::check(Theory::Effort effort
) {
441 // Reset the interrupt flag
442 d_interrupted
= false;
444 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
445 #undef CVC4_FOR_EACH_THEORY_STATEMENT
447 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
448 if (theory::TheoryTraits<THEORY>::hasCheck && d_logicInfo.isTheoryEnabled(THEORY)) { \
449 theoryOf(THEORY)->check(effort); \
450 if (d_inConflict) { \
451 Debug("conflict") << THEORY << " in conflict. " << std::endl; \
459 // Mark the output channel unused (if this is FULL_EFFORT, and nothing
460 // is done by the theories, no additional check will be needed)
461 d_outputChannelUsed
= false;
463 // Mark the lemmas flag (no lemmas added)
464 d_lemmasAdded
= false;
466 Debug("theory") << "TheoryEngine::check(" << effort
<< "): d_factsAsserted = " << (d_factsAsserted
? "true" : "false") << endl
;
468 // If in full effort, we have a fake new assertion just to jumpstart the checking
469 if (Theory::fullEffort(effort
)) {
470 d_factsAsserted
= true;
471 // Reset round for the relevance manager, which notice only sets a flag
472 // to indicate that its information must be recomputed.
473 if (d_relManager
!= nullptr)
475 d_relManager
->resetRound();
480 while (d_factsAsserted
&& !d_inConflict
&& !d_lemmasAdded
) {
482 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running check" << endl
;
484 Trace("theory::assertions") << endl
;
485 if (Trace
.isOn("theory::assertions")) {
486 printAssertions("theory::assertions");
489 if(Theory::fullEffort(effort
)) {
490 Trace("theory::assertions::fulleffort") << endl
;
491 if (Trace
.isOn("theory::assertions::fulleffort")) {
492 printAssertions("theory::assertions::fulleffort");
496 // Note that we've discharged all the facts
497 d_factsAsserted
= false;
500 CVC4_FOR_EACH_THEORY
;
502 if(Dump
.isOn("missed-t-conflicts")) {
503 Dump("missed-t-conflicts")
504 << CommentCommand("Completeness check for T-conflicts; expect sat")
505 << CheckSatCommand();
508 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running propagation after the initial check" << endl
;
510 // We are still satisfiable, propagate as much as possible
513 // We do combination if all has been processed and we are in fullcheck
514 if (Theory::fullEffort(effort
) && d_logicInfo
.isSharingEnabled() && !d_factsAsserted
&& !d_lemmasAdded
&& !d_inConflict
) {
515 // Do the combination
516 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running combination" << endl
;
518 if(d_logicInfo
.isQuantified()){
519 d_quantEngine
->notifyCombineTheories();
524 // Must consult quantifiers theory for last call to ensure sat, or otherwise add a lemma
525 if( Theory::fullEffort(effort
) && ! d_inConflict
&& ! needCheck() ) {
526 Trace("theory::assertions-model") << endl
;
527 if (Trace
.isOn("theory::assertions-model")) {
528 printAssertions("theory::assertions-model");
530 //checks for theories requiring the model go at last call
531 d_curr_model
->reset();
532 // !!! temporary, will be part of distributed model manager
533 context::Context
* meec
= d_eeDistributed
->getModelEqualityEngineContext();
536 for (TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
537 if( theoryId
!=THEORY_QUANTIFIERS
){
538 Theory
* theory
= d_theoryTable
[theoryId
];
539 if (theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
540 if( theory
->needsCheckLastEffort() ){
541 if( !d_curr_model
->isBuilt() ){
542 if( !d_curr_model_builder
->buildModel(d_curr_model
) ){
546 theory
->check(Theory::EFFORT_LAST_CALL
);
553 if(d_logicInfo
.isQuantified()) {
554 // quantifiers engine must check at last call effort
555 d_quantEngine
->check(Theory::EFFORT_LAST_CALL
);
558 if (!d_inConflict
&& !needCheck())
560 // If d_eager_model_building is false, then we only mark that we
561 // are in "SAT mode". We build the model later only if the user asks
562 // for it via getBuiltModel.
564 if (d_eager_model_building
&& !d_curr_model
->isBuilt())
566 d_curr_model_builder
->buildModel(d_curr_model
);
571 Debug("theory") << "TheoryEngine::check(" << effort
<< "): done, we are " << (d_inConflict
? "unsat" : "sat") << (d_lemmasAdded
? " with new lemmas" : " with no new lemmas");
572 Debug("theory") << ", need check = " << (needCheck() ? "YES" : "NO") << endl
;
574 if( Theory::fullEffort(effort
) && !d_inConflict
&& !needCheck()) {
575 // case where we are about to answer SAT, the master equality engine,
576 // if it exists, must be consistent.
577 eq::EqualityEngine
* mee
= d_eeDistributed
->getCoreEqualityEngine();
580 AlwaysAssert(mee
->consistent());
582 if (d_curr_model
->isBuilt())
584 // model construction should always succeed unless lemmas were added
585 AlwaysAssert(d_curr_model
->isBuiltSuccess());
586 if (options::produceModels())
588 // Do post-processing of model from the theories (used for THEORY_SEP
589 // to construct heap model)
590 postProcessModel(d_curr_model
);
591 // also call the model builder's post-process model
592 d_curr_model_builder
->postProcessModel(d_incomplete
.get(),
597 } catch(const theory::Interrupted
&) {
598 Trace("theory") << "TheoryEngine::check() => interrupted" << endl
;
600 // If fulleffort, check all theories
601 if(Dump
.isOn("theory::fullcheck") && Theory::fullEffort(effort
)) {
602 if (!d_inConflict
&& !needCheck()) {
603 dumpAssertions("theory::fullcheck");
608 void TheoryEngine::combineTheories() {
610 Trace("combineTheories") << "TheoryEngine::combineTheories()" << endl
;
612 TimerStat::CodeTimer
combineTheoriesTimer(d_combineTheoriesTime
);
614 // Care graph we'll be building
617 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
618 #undef CVC4_FOR_EACH_THEORY_STATEMENT
620 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
621 if (theory::TheoryTraits<THEORY>::isParametric && d_logicInfo.isTheoryEnabled(THEORY)) { \
622 theoryOf(THEORY)->getCareGraph(&careGraph); \
625 // Call on each parametric theory to give us its care graph
626 CVC4_FOR_EACH_THEORY
;
628 Trace("combineTheories") << "TheoryEngine::combineTheories(): care graph size = " << careGraph
.size() << endl
;
630 // Now add splitters for the ones we are interested in
631 CareGraph::const_iterator care_it
= careGraph
.begin();
632 CareGraph::const_iterator care_it_end
= careGraph
.end();
634 for (; care_it
!= care_it_end
; ++ care_it
) {
635 const CarePair
& carePair
= *care_it
;
637 Debug("combineTheories")
638 << "TheoryEngine::combineTheories(): checking " << carePair
.d_a
<< " = "
639 << carePair
.d_b
<< " from " << carePair
.d_theory
<< endl
;
641 Assert(d_sharedTerms
.isShared(carePair
.d_a
) || carePair
.d_a
.isConst());
642 Assert(d_sharedTerms
.isShared(carePair
.d_b
) || carePair
.d_b
.isConst());
644 // The equality in question (order for no repetition)
645 Node equality
= carePair
.d_a
.eqNode(carePair
.d_b
);
646 // EqualityStatus es = getEqualityStatus(carePair.d_a, carePair.d_b);
647 // Debug("combineTheories") << "TheoryEngine::combineTheories(): " <<
648 // (es == EQUALITY_TRUE_AND_PROPAGATED ? "EQUALITY_TRUE_AND_PROPAGATED" :
649 // es == EQUALITY_FALSE_AND_PROPAGATED ? "EQUALITY_FALSE_AND_PROPAGATED" :
650 // es == EQUALITY_TRUE ? "EQUALITY_TRUE" :
651 // es == EQUALITY_FALSE ? "EQUALITY_FALSE" :
652 // es == EQUALITY_TRUE_IN_MODEL ? "EQUALITY_TRUE_IN_MODEL" :
653 // es == EQUALITY_FALSE_IN_MODEL ? "EQUALITY_FALSE_IN_MODEL" :
654 // es == EQUALITY_UNKNOWN ? "EQUALITY_UNKNOWN" :
655 // "Unexpected case") << endl;
657 // We need to split on it
658 Debug("combineTheories") << "TheoryEngine::combineTheories(): requesting a split " << endl
;
660 lemma(equality
.orNode(equality
.notNode()),
666 // This code is supposed to force preference to follow what the theory models already have
667 // but it doesn't seem to make a big difference - need to explore more -Clark
669 // if (es == EQUALITY_TRUE || es == EQUALITY_TRUE_IN_MODEL) {
670 Node e
= ensureLiteral(equality
);
671 d_propEngine
->requirePhase(e
, true);
673 // else if (es == EQUALITY_FALSE_IN_MODEL) {
674 // Node e = ensureLiteral(equality);
675 // d_propEngine->requirePhase(e, false);
681 void TheoryEngine::propagate(Theory::Effort effort
) {
682 // Reset the interrupt flag
683 d_interrupted
= false;
685 // Definition of the statement that is to be run by every theory
686 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
687 #undef CVC4_FOR_EACH_THEORY_STATEMENT
689 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
690 if (theory::TheoryTraits<THEORY>::hasPropagate && d_logicInfo.isTheoryEnabled(THEORY)) { \
691 theoryOf(THEORY)->propagate(effort); \
694 // Reset the interrupt flag
695 d_interrupted
= false;
697 // Propagate for each theory using the statement above
698 CVC4_FOR_EACH_THEORY
;
700 if(Dump
.isOn("missed-t-propagations")) {
701 for(unsigned i
= 0; i
< d_possiblePropagations
.size(); ++i
) {
702 Node atom
= d_possiblePropagations
[i
];
704 if(d_propEngine
->hasValue(atom
, value
)) {
707 // Doesn't have a value, check it (and the negation)
708 if(d_hasPropagated
.find(atom
) == d_hasPropagated
.end()) {
709 Dump("missed-t-propagations")
710 << CommentCommand("Completeness check for T-propagations; expect invalid")
711 << EchoCommand(atom
.toString())
712 << QueryCommand(atom
.toExpr())
713 << EchoCommand(atom
.notNode().toString())
714 << QueryCommand(atom
.notNode().toExpr());
720 Node
TheoryEngine::getNextDecisionRequest()
722 return d_decManager
->getNextDecisionRequest();
725 bool TheoryEngine::properConflict(TNode conflict
) const {
727 if (conflict
.getKind() == kind::AND
) {
728 for (unsigned i
= 0; i
< conflict
.getNumChildren(); ++ i
) {
729 if (! getPropEngine()->hasValue(conflict
[i
], value
)) {
730 Debug("properConflict") << "Bad conflict is due to unassigned atom: "
731 << conflict
[i
] << endl
;
735 Debug("properConflict") << "Bad conflict is due to false atom: "
736 << conflict
[i
] << endl
;
739 if (conflict
[i
] != Rewriter::rewrite(conflict
[i
])) {
740 Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
741 << conflict
[i
] << " vs " << Rewriter::rewrite(conflict
[i
]) << endl
;
746 if (! getPropEngine()->hasValue(conflict
, value
)) {
747 Debug("properConflict") << "Bad conflict is due to unassigned atom: "
752 Debug("properConflict") << "Bad conflict is due to false atom: "
756 if (conflict
!= Rewriter::rewrite(conflict
)) {
757 Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
758 << conflict
<< " vs " << Rewriter::rewrite(conflict
) << endl
;
765 bool TheoryEngine::properPropagation(TNode lit
) const {
766 if(!getPropEngine()->isSatLiteral(lit
)) {
770 return !getPropEngine()->hasValue(lit
, b
);
773 bool TheoryEngine::properExplanation(TNode node
, TNode expl
) const {
774 // Explanation must be either a conjunction of true literals that have true SAT values already
775 // or a singled literal that has a true SAT value already.
776 if (expl
.getKind() == kind::AND
) {
777 for (unsigned i
= 0; i
< expl
.getNumChildren(); ++ i
) {
779 if (!d_propEngine
->hasValue(expl
[i
], value
) || !value
) {
785 return d_propEngine
->hasValue(expl
, value
) && value
;
790 bool TheoryEngine::collectModelInfo(theory::TheoryModel
* m
)
792 //have shared term engine collectModelInfo
793 // d_sharedTerms.collectModelInfo( m );
794 // Consult each active theory to get all relevant information
795 // concerning the model.
796 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
; ++theoryId
) {
797 if(d_logicInfo
.isTheoryEnabled(theoryId
)) {
798 Trace("model-builder") << " CollectModelInfo on theory: " << theoryId
<< endl
;
799 if (!d_theoryTable
[theoryId
]->collectModelInfo(m
))
805 Trace("model-builder") << " CollectModelInfo boolean variables" << std::endl
;
806 // Get the Boolean variables
807 vector
<TNode
> boolVars
;
808 d_propEngine
->getBooleanVariables(boolVars
);
809 vector
<TNode
>::iterator it
, iend
= boolVars
.end();
810 bool hasValue
, value
;
811 for (it
= boolVars
.begin(); it
!= iend
; ++it
) {
813 hasValue
= d_propEngine
->hasValue(var
, value
);
814 // TODO: Assert that hasValue is true?
816 Trace("model-builder-assertions")
817 << " has no value : " << var
<< std::endl
;
820 Trace("model-builder-assertions") << "(assert" << (value
? " " : " (not ") << var
<< (value
? ");" : "));") << endl
;
821 if (!m
->assertPredicate(var
, value
))
829 void TheoryEngine::postProcessModel( theory::TheoryModel
* m
){
830 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
; ++theoryId
) {
831 if(d_logicInfo
.isTheoryEnabled(theoryId
)) {
832 Trace("model-builder-debug") << " PostProcessModel on theory: " << theoryId
<< endl
;
833 d_theoryTable
[theoryId
]->postProcessModel( m
);
838 TheoryModel
* TheoryEngine::getModel() {
842 TheoryModel
* TheoryEngine::getBuiltModel()
844 if (!d_curr_model
->isBuilt())
846 // If this method was called, we should be in SAT mode, and produceModels
848 AlwaysAssert(options::produceModels());
851 // not available, perhaps due to interuption.
854 // must build model at this point
855 d_curr_model_builder
->buildModel(d_curr_model
);
860 bool TheoryEngine::getSynthSolutions(
861 std::map
<Node
, std::map
<Node
, Node
>>& sol_map
)
865 return d_quantEngine
->getSynthSolutions(sol_map
);
867 // we are not in a quantified logic, there is no synthesis solution
871 bool TheoryEngine::presolve() {
872 // Reset the interrupt flag
873 d_interrupted
= false;
875 // Reset the decision manager. This clears its decision strategies that are
876 // no longer valid in this user context.
877 d_decManager
->presolve();
880 // Definition of the statement that is to be run by every theory
881 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
882 #undef CVC4_FOR_EACH_THEORY_STATEMENT
884 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
885 if (theory::TheoryTraits<THEORY>::hasPresolve) { \
886 theoryOf(THEORY)->presolve(); \
892 // Presolve for each theory using the statement above
893 CVC4_FOR_EACH_THEORY
;
894 } catch(const theory::Interrupted
&) {
895 Trace("theory") << "TheoryEngine::presolve() => interrupted" << endl
;
897 // return whether we have a conflict
899 }/* TheoryEngine::presolve() */
901 void TheoryEngine::postsolve() {
902 // no longer in SAT mode
904 // Reset the interrupt flag
905 d_interrupted
= false;
906 bool CVC4_UNUSED wasInConflict
= d_inConflict
;
909 // Definition of the statement that is to be run by every theory
910 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
911 #undef CVC4_FOR_EACH_THEORY_STATEMENT
913 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
914 if (theory::TheoryTraits<THEORY>::hasPostsolve) \
916 theoryOf(THEORY)->postsolve(); \
917 Assert(!d_inConflict || wasInConflict) \
918 << "conflict raised during postsolve()"; \
921 // Postsolve for each theory using the statement above
922 CVC4_FOR_EACH_THEORY
;
923 } catch(const theory::Interrupted
&) {
924 Trace("theory") << "TheoryEngine::postsolve() => interrupted" << endl
;
926 }/* TheoryEngine::postsolve() */
929 void TheoryEngine::notifyRestart() {
930 // Reset the interrupt flag
931 d_interrupted
= false;
933 // Definition of the statement that is to be run by every theory
934 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
935 #undef CVC4_FOR_EACH_THEORY_STATEMENT
937 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
938 if (theory::TheoryTraits<THEORY>::hasNotifyRestart && d_logicInfo.isTheoryEnabled(THEORY)) { \
939 theoryOf(THEORY)->notifyRestart(); \
942 // notify each theory using the statement above
943 CVC4_FOR_EACH_THEORY
;
946 void TheoryEngine::ppStaticLearn(TNode in
, NodeBuilder
<>& learned
) {
947 // Reset the interrupt flag
948 d_interrupted
= false;
950 // Definition of the statement that is to be run by every theory
951 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
952 #undef CVC4_FOR_EACH_THEORY_STATEMENT
954 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
955 if (theory::TheoryTraits<THEORY>::hasPpStaticLearn) { \
956 theoryOf(THEORY)->ppStaticLearn(in, learned); \
959 // static learning for each theory using the statement above
960 CVC4_FOR_EACH_THEORY
;
963 bool TheoryEngine::isRelevant(Node lit
) const
965 if (d_relManager
!= nullptr)
967 return d_relManager
->isRelevant(lit
);
969 // otherwise must assume its relevant
973 void TheoryEngine::shutdown() {
974 // Set this first; if a Theory shutdown() throws an exception,
975 // at least the destruction of the TheoryEngine won't confound
977 d_hasShutDown
= true;
979 // Shutdown all the theories
980 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
; ++theoryId
) {
981 if(d_theoryTable
[theoryId
]) {
982 theoryOf(theoryId
)->shutdown();
989 theory::Theory::PPAssertStatus
TheoryEngine::solve(TNode literal
, SubstitutionMap
& substitutionOut
) {
990 // Reset the interrupt flag
991 d_interrupted
= false;
993 TNode atom
= literal
.getKind() == kind::NOT
? literal
[0] : literal
;
994 Trace("theory::solve") << "TheoryEngine::solve(" << literal
<< "): solving with " << theoryOf(atom
)->getId() << endl
;
996 if(! d_logicInfo
.isTheoryEnabled(Theory::theoryOf(atom
)) &&
997 Theory::theoryOf(atom
) != THEORY_SAT_SOLVER
) {
999 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
1000 << ", which doesn't include " << Theory::theoryOf(atom
)
1001 << ", but got a preprocessing-time fact for that theory." << endl
1002 << "The fact:" << endl
1004 throw LogicException(ss
.str());
1007 Theory::PPAssertStatus solveStatus
= theoryOf(atom
)->ppAssert(literal
, substitutionOut
);
1008 Trace("theory::solve") << "TheoryEngine::solve(" << literal
<< ") => " << solveStatus
<< endl
;
1012 void TheoryEngine::preprocessStart() { d_tpp
.clearCache(); }
1014 Node
TheoryEngine::preprocess(TNode assertion
) {
1015 TrustNode trn
= d_tpp
.theoryPreprocess(assertion
);
1021 return trn
.getNode();
1024 void TheoryEngine::notifyPreprocessedAssertions(
1025 const std::vector
<Node
>& assertions
) {
1026 // call all the theories
1027 for (TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
;
1029 if (d_theoryTable
[theoryId
]) {
1030 theoryOf(theoryId
)->ppNotifyAssertions(assertions
);
1033 if (d_relManager
!= nullptr)
1035 d_relManager
->notifyPreprocessedAssertions(assertions
);
1039 bool TheoryEngine::markPropagation(TNode assertion
, TNode originalAssertion
, theory::TheoryId toTheoryId
, theory::TheoryId fromTheoryId
) {
1041 // What and where we are asserting
1042 NodeTheoryPair
toAssert(assertion
, toTheoryId
, d_propagationMapTimestamp
);
1043 // What and where it came from
1044 NodeTheoryPair
toExplain(originalAssertion
, fromTheoryId
, d_propagationMapTimestamp
);
1046 // See if the theory already got this literal
1047 PropagationMap::const_iterator find
= d_propagationMap
.find(toAssert
);
1048 if (find
!= d_propagationMap
.end()) {
1049 // The theory already knows this
1050 Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): already there" << endl
;
1054 Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): marking [" << d_propagationMapTimestamp
<< "] " << assertion
<< ", " << toTheoryId
<< " from " << originalAssertion
<< ", " << fromTheoryId
<< endl
;
1056 // Mark the propagation
1057 d_propagationMap
[toAssert
] = toExplain
;
1058 d_propagationMapTimestamp
= d_propagationMapTimestamp
+ 1;
1064 void TheoryEngine::assertToTheory(TNode assertion
, TNode originalAssertion
, theory::TheoryId toTheoryId
, theory::TheoryId fromTheoryId
) {
1066 Trace("theory::assertToTheory") << "TheoryEngine::assertToTheory(" << assertion
<< ", " << originalAssertion
<< "," << toTheoryId
<< ", " << fromTheoryId
<< ")" << endl
;
1068 Assert(toTheoryId
!= fromTheoryId
);
1069 if(toTheoryId
!= THEORY_SAT_SOLVER
&&
1070 ! d_logicInfo
.isTheoryEnabled(toTheoryId
)) {
1072 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
1073 << ", which doesn't include " << toTheoryId
1074 << ", but got an asserted fact to that theory." << endl
1075 << "The fact:" << endl
1077 throw LogicException(ss
.str());
1084 // If sharing is disabled, things are easy
1085 if (!d_logicInfo
.isSharingEnabled()) {
1086 Assert(assertion
== originalAssertion
);
1087 if (fromTheoryId
== THEORY_SAT_SOLVER
) {
1088 // Send to the apropriate theory
1089 theory::Theory
* toTheory
= theoryOf(toTheoryId
);
1090 // We assert it, and we know it's preregistereed
1091 toTheory
->assertFact(assertion
, true);
1092 // Mark that we have more information
1093 d_factsAsserted
= true;
1095 Assert(toTheoryId
== THEORY_SAT_SOLVER
);
1096 // Check for propositional conflict
1098 if (d_propEngine
->hasValue(assertion
, value
)) {
1100 Trace("theory::propagate") << "TheoryEngine::assertToTheory(" << assertion
<< ", " << toTheoryId
<< ", " << fromTheoryId
<< "): conflict (no sharing)" << endl
;
1101 Trace("dtview::conflict")
1102 << ":THEORY-CONFLICT: " << assertion
<< std::endl
;
1103 d_inConflict
= true;
1108 d_propagatedLiterals
.push_back(assertion
);
1113 // Polarity of the assertion
1114 bool polarity
= assertion
.getKind() != kind::NOT
;
1116 // Atom of the assertion
1117 TNode atom
= polarity
? assertion
: assertion
[0];
1119 // If sending to the shared terms database, it's also simple
1120 if (toTheoryId
== THEORY_BUILTIN
) {
1121 Assert(atom
.getKind() == kind::EQUAL
)
1122 << "atom should be an EQUALity, not `" << atom
<< "'";
1123 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1124 d_sharedTerms
.assertEquality(atom
, polarity
, assertion
);
1129 // Things from the SAT solver are already normalized, so they go
1130 // directly to the apropriate theory
1131 if (fromTheoryId
== THEORY_SAT_SOLVER
) {
1132 // We know that this is normalized, so just send it off to the theory
1133 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1134 // Is it preregistered
1135 bool preregistered
= d_propEngine
->isSatLiteral(assertion
) && Theory::theoryOf(assertion
) == toTheoryId
;
1137 theoryOf(toTheoryId
)->assertFact(assertion
, preregistered
);
1138 // Mark that we have more information
1139 d_factsAsserted
= true;
1144 // Propagations to the SAT solver are just enqueued for pickup by
1145 // the SAT solver later
1146 if (toTheoryId
== THEORY_SAT_SOLVER
) {
1147 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1148 // Enqueue for propagation to the SAT solver
1149 d_propagatedLiterals
.push_back(assertion
);
1150 // Check for propositional conflicts
1152 if (d_propEngine
->hasValue(assertion
, value
) && !value
) {
1153 Trace("theory::propagate")
1154 << "TheoryEngine::assertToTheory(" << assertion
<< ", "
1155 << toTheoryId
<< ", " << fromTheoryId
<< "): conflict (sharing)"
1157 Trace("dtview::conflict")
1158 << ":THEORY-CONFLICT: " << assertion
<< std::endl
;
1159 d_inConflict
= true;
1165 Assert(atom
.getKind() == kind::EQUAL
);
1168 Node normalizedLiteral
= Rewriter::rewrite(assertion
);
1170 // See if it rewrites false directly -> conflict
1171 if (normalizedLiteral
.isConst()) {
1172 if (!normalizedLiteral
.getConst
<bool>()) {
1173 // Mark the propagation for explanations
1174 if (markPropagation(normalizedLiteral
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1175 // Get the explanation (conflict will figure out where it came from)
1176 conflict(normalizedLiteral
, toTheoryId
);
1184 // Try and assert (note that we assert the non-normalized one)
1185 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1186 // Check if has been pre-registered with the theory
1187 bool preregistered
= d_propEngine
->isSatLiteral(assertion
) && Theory::theoryOf(assertion
) == toTheoryId
;
1189 theoryOf(toTheoryId
)->assertFact(assertion
, preregistered
);
1190 d_factsAsserted
= true;
1196 void TheoryEngine::assertFact(TNode literal
)
1198 Trace("theory") << "TheoryEngine::assertFact(" << literal
<< ")" << endl
;
1202 // If we're in conflict, nothing to do
1208 bool polarity
= literal
.getKind() != kind::NOT
;
1209 TNode atom
= polarity
? literal
: literal
[0];
1211 if (d_logicInfo
.isSharingEnabled()) {
1213 // If any shared terms, it's time to do sharing work
1214 if (d_sharedTerms
.hasSharedTerms(atom
)) {
1215 // Notify the theories the shared terms
1216 SharedTermsDatabase::shared_terms_iterator it
= d_sharedTerms
.begin(atom
);
1217 SharedTermsDatabase::shared_terms_iterator it_end
= d_sharedTerms
.end(atom
);
1218 for (; it
!= it_end
; ++ it
) {
1220 Theory::Set theories
= d_sharedTerms
.getTheoriesToNotify(atom
, term
);
1221 for (TheoryId id
= THEORY_FIRST
; id
!= THEORY_LAST
; ++ id
) {
1222 if (Theory::setContains(id
, theories
)) {
1223 theoryOf(id
)->addSharedTerm(term
);
1226 d_sharedTerms
.markNotified(term
, theories
);
1230 // If it's an equality, assert it to the shared term manager, even though the terms are not
1231 // yet shared. As the terms become shared later, the shared terms manager will then add them
1232 // to the assert the equality to the interested theories
1233 if (atom
.getKind() == kind::EQUAL
) {
1234 // Assert it to the the owning theory
1235 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1236 // Shared terms manager will assert to interested theories directly, as the terms become shared
1237 assertToTheory(literal
, literal
, /* to */ THEORY_BUILTIN
, /* from */ THEORY_SAT_SOLVER
);
1239 // Now, let's check for any atom triggers from lemmas
1240 AtomRequests::atom_iterator it
= d_atomRequests
.getAtomIterator(atom
);
1241 while (!it
.done()) {
1242 const AtomRequests::Request
& request
= it
.get();
1244 polarity
? (Node
)request
.d_atom
: request
.d_atom
.notNode();
1245 Debug("theory::atoms") << "TheoryEngine::assertFact(" << literal
<< "): sending requested " << toAssert
<< endl
;
1247 toAssert
, literal
, request
.d_toTheory
, THEORY_SAT_SOLVER
);
1252 // Not an equality, just assert to the appropriate theory
1253 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1256 // Assert the fact to the appropriate theory directly
1257 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1261 bool TheoryEngine::propagate(TNode literal
, theory::TheoryId theory
) {
1263 Debug("theory::propagate") << "TheoryEngine::propagate(" << literal
<< ", " << theory
<< ")" << endl
;
1265 Trace("dtview::prop") << std::string(d_context
->getLevel(), ' ')
1266 << ":THEORY-PROP: " << literal
<< endl
;
1270 if(Dump
.isOn("t-propagations")) {
1271 Dump("t-propagations") << CommentCommand("negation of theory propagation: expect valid")
1272 << QueryCommand(literal
.toExpr());
1274 if(Dump
.isOn("missed-t-propagations")) {
1275 d_hasPropagated
.insert(literal
);
1279 bool polarity
= literal
.getKind() != kind::NOT
;
1280 TNode atom
= polarity
? literal
: literal
[0];
1282 if (d_logicInfo
.isSharingEnabled() && atom
.getKind() == kind::EQUAL
) {
1283 if (d_propEngine
->isSatLiteral(literal
)) {
1284 // We propagate SAT literals to SAT
1285 assertToTheory(literal
, literal
, /* to */ THEORY_SAT_SOLVER
, /* from */ theory
);
1287 if (theory
!= THEORY_BUILTIN
) {
1288 // Assert to the shared terms database
1289 assertToTheory(literal
, literal
, /* to */ THEORY_BUILTIN
, /* from */ theory
);
1292 // We could be propagating a unit-clause lemma. In this case, we need to provide a
1294 // TODO: Consider putting this someplace else? This is the only refence to the proof
1295 // manager in this class.
1298 LemmaProofRecipe proofRecipe
;
1299 proofRecipe
.addBaseAssertion(literal
);
1302 LemmaProofRecipe::ProofStep
proofStep(theory
, emptyNode
);
1303 proofStep
.addAssertion(literal
);
1304 proofRecipe
.addStep(proofStep
);
1306 ProofManager::getCnfProof()->setProofRecipe(&proofRecipe
);
1309 // Just send off to the SAT solver
1310 Assert(d_propEngine
->isSatLiteral(literal
));
1311 assertToTheory(literal
, literal
, /* to */ THEORY_SAT_SOLVER
, /* from */ theory
);
1314 return !d_inConflict
;
1317 const LogicInfo
& TheoryEngine::getLogicInfo() const { return d_logicInfo
; }
1319 theory::EqualityStatus
TheoryEngine::getEqualityStatus(TNode a
, TNode b
) {
1320 Assert(a
.getType().isComparableTo(b
.getType()));
1321 if (d_sharedTerms
.isShared(a
) && d_sharedTerms
.isShared(b
)) {
1322 if (d_sharedTerms
.areEqual(a
,b
)) {
1323 return EQUALITY_TRUE_AND_PROPAGATED
;
1325 else if (d_sharedTerms
.areDisequal(a
,b
)) {
1326 return EQUALITY_FALSE_AND_PROPAGATED
;
1329 return theoryOf(Theory::theoryOf(a
.getType()))->getEqualityStatus(a
, b
);
1332 Node
TheoryEngine::getModelValue(TNode var
) {
1335 // the model value of a constant must be itself
1338 Assert(d_sharedTerms
.isShared(var
));
1339 return theoryOf(Theory::theoryOf(var
.getType()))->getModelValue(var
);
1343 Node
TheoryEngine::ensureLiteral(TNode n
) {
1344 Debug("ensureLiteral") << "rewriting: " << n
<< std::endl
;
1345 Node rewritten
= Rewriter::rewrite(n
);
1346 Debug("ensureLiteral") << " got: " << rewritten
<< std::endl
;
1347 Node preprocessed
= preprocess(rewritten
);
1348 Debug("ensureLiteral") << "preprocessed: " << preprocessed
<< std::endl
;
1349 d_propEngine
->ensureLiteral(preprocessed
);
1350 return preprocessed
;
1354 void TheoryEngine::printInstantiations( std::ostream
& out
) {
1355 if( d_quantEngine
){
1356 d_quantEngine
->printInstantiations( out
);
1358 out
<< "Internal error : instantiations not available when quantifiers are not present." << std::endl
;
1363 void TheoryEngine::printSynthSolution( std::ostream
& out
) {
1364 if( d_quantEngine
){
1365 d_quantEngine
->printSynthSolution( out
);
1367 out
<< "Internal error : synth solution not available when quantifiers are not present." << std::endl
;
1372 void TheoryEngine::getInstantiatedQuantifiedFormulas( std::vector
< Node
>& qs
) {
1373 if( d_quantEngine
){
1374 d_quantEngine
->getInstantiatedQuantifiedFormulas( qs
);
1380 void TheoryEngine::getInstantiations( Node q
, std::vector
< Node
>& insts
) {
1381 if( d_quantEngine
){
1382 d_quantEngine
->getInstantiations( q
, insts
);
1388 void TheoryEngine::getInstantiationTermVectors( Node q
, std::vector
< std::vector
< Node
> >& tvecs
) {
1389 if( d_quantEngine
){
1390 d_quantEngine
->getInstantiationTermVectors( q
, tvecs
);
1396 void TheoryEngine::getInstantiations( std::map
< Node
, std::vector
< Node
> >& insts
) {
1397 if( d_quantEngine
){
1398 d_quantEngine
->getInstantiations( insts
);
1404 void TheoryEngine::getInstantiationTermVectors( std::map
< Node
, std::vector
< std::vector
< Node
> > >& insts
) {
1405 if( d_quantEngine
){
1406 d_quantEngine
->getInstantiationTermVectors( insts
);
1412 Node
TheoryEngine::getInstantiatedConjunction( Node q
) {
1413 if( d_quantEngine
){
1414 return d_quantEngine
->getInstantiatedConjunction( q
);
1417 return Node::null();
1422 static Node
mkExplanation(const std::vector
<NodeTheoryPair
>& explanation
) {
1424 std::set
<TNode
> all
;
1425 for (unsigned i
= 0; i
< explanation
.size(); ++ i
) {
1426 Assert(explanation
[i
].d_theory
== THEORY_SAT_SOLVER
);
1427 all
.insert(explanation
[i
].d_node
);
1430 if (all
.size() == 0) {
1431 // Normalize to true
1432 return NodeManager::currentNM()->mkConst
<bool>(true);
1435 if (all
.size() == 1) {
1436 // All the same, or just one
1437 return explanation
[0].d_node
;
1440 NodeBuilder
<> conjunction(kind::AND
);
1441 std::set
<TNode
>::const_iterator it
= all
.begin();
1442 std::set
<TNode
>::const_iterator it_end
= all
.end();
1443 while (it
!= it_end
) {
1451 Node
TheoryEngine::getExplanationAndRecipe(TNode node
, LemmaProofRecipe
* proofRecipe
) {
1452 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
<< "): current propagation index = " << d_propagationMapTimestamp
<< endl
;
1454 bool polarity
= node
.getKind() != kind::NOT
;
1455 TNode atom
= polarity
? node
: node
[0];
1457 // If we're not in shared mode, explanations are simple
1458 if (!d_logicInfo
.isSharingEnabled()) {
1459 Debug("theory::explain") << "TheoryEngine::getExplanation: sharing is NOT enabled. "
1460 << " Responsible theory is: "
1461 << theoryOf(atom
)->getId() << std::endl
;
1463 TrustNode texplanation
= theoryOf(atom
)->explain(node
);
1464 Node explanation
= texplanation
.getNode();
1465 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
<< ") => " << explanation
<< endl
;
1469 LemmaProofRecipe::ProofStep
proofStep(theoryOf(atom
)->getId(), emptyNode
);
1470 proofStep
.addAssertion(node
);
1471 proofRecipe
->addBaseAssertion(node
);
1473 if (explanation
.getKind() == kind::AND
) {
1474 // If the explanation is a conjunction, the recipe for the corresponding lemma is
1475 // the negation of its conjuncts.
1476 Node flat
= flattenAnd(explanation
);
1477 for (unsigned i
= 0; i
< flat
.getNumChildren(); ++i
) {
1478 if (flat
[i
].isConst() && flat
[i
].getConst
<bool>()) {
1482 if (flat
[i
].getKind() == kind::NOT
&&
1483 flat
[i
][0].isConst() && !flat
[i
][0].getConst
<bool>()) {
1487 Debug("theory::explain") << "TheoryEngine::getExplanationAndRecipe: adding recipe assertion: "
1488 << flat
[i
].negate() << std::endl
;
1489 proofStep
.addAssertion(flat
[i
].negate());
1490 proofRecipe
->addBaseAssertion(flat
[i
].negate());
1493 // The recipe for proving it is by negating it. "True" is not an acceptable reason.
1494 if (!((explanation
.isConst() && explanation
.getConst
<bool>()) ||
1495 (explanation
.getKind() == kind::NOT
&&
1496 explanation
[0].isConst() && !explanation
[0].getConst
<bool>()))) {
1497 proofStep
.addAssertion(explanation
.negate());
1498 proofRecipe
->addBaseAssertion(explanation
.negate());
1502 proofRecipe
->addStep(proofStep
);
1509 Debug("theory::explain") << "TheoryEngine::getExplanation: sharing IS enabled" << std::endl
;
1511 // Initial thing to explain
1512 NodeTheoryPair
toExplain(node
, THEORY_SAT_SOLVER
, d_propagationMapTimestamp
);
1513 Assert(d_propagationMap
.find(toExplain
) != d_propagationMap
.end());
1515 NodeTheoryPair nodeExplainerPair
= d_propagationMap
[toExplain
];
1516 Debug("theory::explain")
1517 << "TheoryEngine::getExplanation: explainer for node "
1518 << nodeExplainerPair
.d_node
1519 << " is theory: " << nodeExplainerPair
.d_theory
<< std::endl
;
1520 TheoryId explainer
= nodeExplainerPair
.d_theory
;
1522 // Create the workplace for explanations
1523 std::vector
<NodeTheoryPair
> explanationVector
;
1524 explanationVector
.push_back(d_propagationMap
[toExplain
]);
1525 // Process the explanation
1528 LemmaProofRecipe::ProofStep
proofStep(explainer
, emptyNode
);
1529 proofStep
.addAssertion(node
);
1530 proofRecipe
->addStep(proofStep
);
1531 proofRecipe
->addBaseAssertion(node
);
1534 getExplanation(explanationVector
, proofRecipe
);
1535 Node explanation
= mkExplanation(explanationVector
);
1537 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
<< ") => " << explanation
<< endl
;
1542 Node
TheoryEngine::getExplanation(TNode node
) {
1543 LemmaProofRecipe
*dontCareRecipe
= NULL
;
1544 return getExplanationAndRecipe(node
, dontCareRecipe
);
1547 struct AtomsCollect
{
1549 std::vector
<TNode
> d_atoms
;
1550 std::unordered_set
<TNode
, TNodeHashFunction
> d_visited
;
1554 typedef void return_type
;
1556 bool alreadyVisited(TNode current
, TNode parent
) {
1557 // Check if already visited
1558 if (d_visited
.find(current
) != d_visited
.end()) return true;
1559 // Don't visit non-boolean
1560 if (!current
.getType().isBoolean()) return true;
1565 void visit(TNode current
, TNode parent
) {
1566 if (Theory::theoryOf(current
) != theory::THEORY_BOOL
) {
1567 d_atoms
.push_back(current
);
1569 d_visited
.insert(current
);
1572 void start(TNode node
) {}
1573 void done(TNode node
) {}
1575 std::vector
<TNode
> getAtoms() const {
1580 void TheoryEngine::ensureLemmaAtoms(const std::vector
<TNode
>& atoms
, theory::TheoryId atomsTo
) {
1581 for (unsigned i
= 0; i
< atoms
.size(); ++ i
) {
1583 // Non-equality atoms are either owned by theory or they don't make sense
1584 if (atoms
[i
].getKind() != kind::EQUAL
) {
1590 // Simple normalization to not repeat stuff
1591 if (eq
[0] > eq
[1]) {
1592 eq
= eq
[1].eqNode(eq
[0]);
1595 // Rewrite the equality
1596 Node eqNormalized
= Rewriter::rewrite(atoms
[i
]);
1598 Debug("theory::atoms") << "TheoryEngine::ensureLemmaAtoms(): " << eq
<< " with nf " << eqNormalized
<< endl
;
1600 // If the equality is a boolean constant, we send immediately
1601 if (eqNormalized
.isConst()) {
1602 if (eqNormalized
.getConst
<bool>()) {
1603 assertToTheory(eq
, eqNormalized
, /** to */ atomsTo
, /** Sat solver */ theory::THEORY_SAT_SOLVER
);
1605 assertToTheory(eq
.notNode(), eqNormalized
.notNode(), /** to */ atomsTo
, /** Sat solver */ theory::THEORY_SAT_SOLVER
);
1608 }else if( eqNormalized
.getKind() != kind::EQUAL
){
1609 Assert(eqNormalized
.getKind() == kind::BOOLEAN_TERM_VARIABLE
1610 || (eqNormalized
.getKind() == kind::NOT
1611 && eqNormalized
[0].getKind() == kind::BOOLEAN_TERM_VARIABLE
));
1612 // this happens for Boolean term equalities V = true that are rewritten to V, we should skip
1613 // TODO : revisit this
1617 // If the normalization did the just flips, keep the flip
1618 if (eqNormalized
[0] == eq
[1] && eqNormalized
[1] == eq
[0]) {
1622 // Check if the equality is already known by the sat solver
1623 if (d_propEngine
->isSatLiteral(eqNormalized
)) {
1625 if (d_propEngine
->hasValue(eqNormalized
, value
)) {
1627 assertToTheory(eq
, eqNormalized
, atomsTo
, theory::THEORY_SAT_SOLVER
);
1630 assertToTheory(eq
.notNode(), eqNormalized
.notNode(), atomsTo
, theory::THEORY_SAT_SOLVER
);
1636 // If the theory is asking about a different form, or the form is ok but if will go to a different theory
1637 // then we must figure it out
1638 if (eqNormalized
!= eq
|| Theory::theoryOf(eq
) != atomsTo
) {
1639 // If you get eqNormalized, send atoms[i] to atomsTo
1640 d_atomRequests
.add(eqNormalized
, eq
, atomsTo
);
1645 theory::LemmaStatus
TheoryEngine::lemma(TNode node
,
1648 theory::LemmaProperty p
,
1649 theory::TheoryId atomsTo
)
1651 // For resource-limiting (also does a time check).
1654 // Do we need to check atoms
1655 if (atomsTo
!= theory::THEORY_LAST
) {
1656 Debug("theory::atoms") << "TheoryEngine::lemma(" << node
<< ", " << atomsTo
<< ")" << endl
;
1657 AtomsCollect collectAtoms
;
1658 NodeVisitor
<AtomsCollect
>::run(collectAtoms
, node
);
1659 ensureLemmaAtoms(collectAtoms
.getAtoms(), atomsTo
);
1662 if(Dump
.isOn("t-lemmas")) {
1667 Dump("t-lemmas") << CommentCommand("theory lemma: expect valid")
1668 << CheckSatCommand(n
.toExpr());
1670 bool removable
= isLemmaPropertyRemovable(p
);
1671 bool preprocess
= isLemmaPropertyPreprocess(p
);
1673 // call preprocessor
1674 std::vector
<TrustNode
> newLemmas
;
1675 std::vector
<Node
> newSkolems
;
1676 TrustNode tlemma
= d_tpp
.preprocess(node
, newLemmas
, newSkolems
, preprocess
);
1678 // !!!!!!! temporary, until this method is fully updated from proof-new
1679 if (tlemma
.isNull())
1681 tlemma
= TrustNode::mkTrustLemma(node
);
1684 // must use an assertion pipeline due to decision engine below
1685 AssertionPipeline lemmas
;
1686 // make the assertion pipeline
1687 lemmas
.push_back(tlemma
.getNode());
1688 lemmas
.updateRealAssertionsEnd();
1689 Assert(newSkolems
.size() == newLemmas
.size());
1690 for (size_t i
= 0, nsize
= newLemmas
.size(); i
< nsize
; i
++)
1692 // store skolem mapping here
1693 IteSkolemMap
& imap
= lemmas
.getIteSkolemMap();
1694 imap
[newSkolems
[i
]] = lemmas
.size();
1695 lemmas
.push_back(newLemmas
[i
].getNode());
1698 // If specified, we must add this lemma to the set of those that need to be
1699 // justified, where note we pass all auxiliary lemmas in lemmas, since these
1700 // by extension must be justified as well.
1701 if (d_relManager
!= nullptr && isLemmaPropertyNeedsJustify(p
))
1703 d_relManager
->notifyPreprocessedAssertions(lemmas
.ref());
1706 // assert lemmas to prop engine
1707 for (size_t i
= 0, lsize
= lemmas
.size(); i
< lsize
; ++i
)
1709 d_propEngine
->assertLemma(
1710 lemmas
[i
], i
== 0 && negated
, removable
, rule
, node
);
1713 // WARNING: Below this point don't assume lemmas[0] to be not negated.
1715 lemmas
.replace(0, lemmas
[0].notNode());
1719 // assert to decision engine
1722 d_propEngine
->addAssertionsToDecisionEngine(lemmas
);
1725 // Mark that we added some lemmas
1726 d_lemmasAdded
= true;
1728 // Lemma analysis isn't online yet; this lemma may only live for this
1730 Node retLemma
= lemmas
[0];
1731 if (lemmas
.size() > 1)
1733 // the returned lemma is the conjunction of all additional lemmas.
1734 retLemma
= NodeManager::currentNM()->mkNode(kind::AND
, lemmas
.ref());
1736 return theory::LemmaStatus(retLemma
, d_userContext
->getLevel());
1739 void TheoryEngine::conflict(TNode conflict
, TheoryId theoryId
) {
1741 Debug("theory::conflict") << "TheoryEngine::conflict(" << conflict
<< ", " << theoryId
<< ")" << endl
;
1743 Trace("dtview::conflict") << ":THEORY-CONFLICT: " << conflict
<< std::endl
;
1745 // Mark that we are in conflict
1746 d_inConflict
= true;
1748 if(Dump
.isOn("t-conflicts")) {
1749 Dump("t-conflicts") << CommentCommand("theory conflict: expect unsat")
1750 << CheckSatCommand(conflict
.toExpr());
1753 LemmaProofRecipe
* proofRecipe
= NULL
;
1755 proofRecipe
= new LemmaProofRecipe
;
1757 LemmaProofRecipe::ProofStep
proofStep(theoryId
, emptyNode
);
1759 if (conflict
.getKind() == kind::AND
) {
1760 for (unsigned i
= 0; i
< conflict
.getNumChildren(); ++i
) {
1761 proofStep
.addAssertion(conflict
[i
].negate());
1764 proofStep
.addAssertion(conflict
.negate());
1767 proofRecipe
->addStep(proofStep
);
1770 // In the multiple-theories case, we need to reconstruct the conflict
1771 if (d_logicInfo
.isSharingEnabled()) {
1772 // Create the workplace for explanations
1773 std::vector
<NodeTheoryPair
> explanationVector
;
1774 explanationVector
.push_back(NodeTheoryPair(conflict
, theoryId
, d_propagationMapTimestamp
));
1776 // Process the explanation
1777 getExplanation(explanationVector
, proofRecipe
);
1778 PROOF(ProofManager::getCnfProof()->setProofRecipe(proofRecipe
));
1779 Node fullConflict
= mkExplanation(explanationVector
);
1780 Debug("theory::conflict") << "TheoryEngine::conflict(" << conflict
<< ", " << theoryId
<< "): full = " << fullConflict
<< endl
;
1781 Assert(properConflict(fullConflict
));
1785 LemmaProperty::REMOVABLE
,
1788 // When only one theory, the conflict should need no processing
1789 Assert(properConflict(conflict
));
1791 if (conflict
.getKind() == kind::AND
) {
1792 // If the conflict is a conjunction, the corresponding lemma is derived by negating
1794 for (unsigned i
= 0; i
< conflict
.getNumChildren(); ++i
) {
1795 if (conflict
[i
].isConst() && conflict
[i
].getConst
<bool>()) {
1799 if (conflict
[i
].getKind() == kind::NOT
&&
1800 conflict
[i
][0].isConst() && !conflict
[i
][0].getConst
<bool>()) {
1804 proofRecipe
->getStep(0)->addAssertion(conflict
[i
].negate());
1805 proofRecipe
->addBaseAssertion(conflict
[i
].negate());
1808 proofRecipe
->getStep(0)->addAssertion(conflict
.negate());
1809 proofRecipe
->addBaseAssertion(conflict
.negate());
1812 ProofManager::getCnfProof()->setProofRecipe(proofRecipe
);
1815 lemma(conflict
, RULE_CONFLICT
, true, LemmaProperty::REMOVABLE
, THEORY_LAST
);
1824 SharedTermsDatabase
* TheoryEngine::getSharedTermsDatabase()
1826 return &d_sharedTerms
;
1829 void TheoryEngine::getExplanation(std::vector
<NodeTheoryPair
>& explanationVector
, LemmaProofRecipe
* proofRecipe
) {
1830 Assert(explanationVector
.size() > 0);
1832 unsigned i
= 0; // Index of the current literal we are processing
1833 unsigned j
= 0; // Index of the last literal we are keeping
1835 std::unique_ptr
<std::set
<Node
>> inputAssertions
= nullptr;
1839 inputAssertions
.reset(
1840 new std::set
<Node
>(proofRecipe
->getStep(0)->getAssertions()));
1843 // cache of nodes we have already explained by some theory
1844 std::unordered_map
<Node
, size_t, NodeHashFunction
> cache
;
1846 while (i
< explanationVector
.size()) {
1847 // Get the current literal to explain
1848 NodeTheoryPair toExplain
= explanationVector
[i
];
1850 Debug("theory::explain")
1851 << "[i=" << i
<< "] TheoryEngine::explain(): processing ["
1852 << toExplain
.d_timestamp
<< "] " << toExplain
.d_node
<< " sent from "
1853 << toExplain
.d_theory
<< endl
;
1855 if (cache
.find(toExplain
.d_node
) != cache
.end()
1856 && cache
[toExplain
.d_node
] < toExplain
.d_timestamp
)
1861 cache
[toExplain
.d_node
] = toExplain
.d_timestamp
;
1863 // If a true constant or a negation of a false constant we can ignore it
1864 if (toExplain
.d_node
.isConst() && toExplain
.d_node
.getConst
<bool>())
1869 if (toExplain
.d_node
.getKind() == kind::NOT
&& toExplain
.d_node
[0].isConst()
1870 && !toExplain
.d_node
[0].getConst
<bool>())
1876 // If from the SAT solver, keep it
1877 if (toExplain
.d_theory
== THEORY_SAT_SOLVER
)
1879 Debug("theory::explain") << "\tLiteral came from THEORY_SAT_SOLVER. Kepping it." << endl
;
1880 explanationVector
[j
++] = explanationVector
[i
++];
1884 // If an and, expand it
1885 if (toExplain
.d_node
.getKind() == kind::AND
)
1887 Debug("theory::explain")
1888 << "TheoryEngine::explain(): expanding " << toExplain
.d_node
1889 << " got from " << toExplain
.d_theory
<< endl
;
1890 for (unsigned k
= 0; k
< toExplain
.d_node
.getNumChildren(); ++k
)
1892 NodeTheoryPair
newExplain(
1893 toExplain
.d_node
[k
], toExplain
.d_theory
, toExplain
.d_timestamp
);
1894 explanationVector
.push_back(newExplain
);
1900 // See if it was sent to the theory by another theory
1901 PropagationMap::const_iterator find
= d_propagationMap
.find(toExplain
);
1902 if (find
!= d_propagationMap
.end()) {
1903 Debug("theory::explain")
1904 << "\tTerm was propagated by another theory (theory = "
1905 << getTheoryString((*find
).second
.d_theory
) << ")" << std::endl
;
1906 // There is some propagation, check if its a timely one
1907 if ((*find
).second
.d_timestamp
< toExplain
.d_timestamp
)
1909 Debug("theory::explain")
1910 << "\tRelevant timetsamp, pushing " << (*find
).second
.d_node
1911 << "to index = " << explanationVector
.size() << std::endl
;
1912 explanationVector
.push_back((*find
).second
);
1916 if (toExplain
.d_node
!= (*find
).second
.d_node
)
1918 Debug("pf::explain")
1919 << "TheoryEngine::getExplanation: Rewrite alert! toAssert = "
1920 << toExplain
.d_node
<< ", toExplain = " << (*find
).second
.d_node
1925 proofRecipe
->addRewriteRule(toExplain
.d_node
,
1926 (*find
).second
.d_node
);
1936 if (toExplain
.d_theory
== THEORY_BUILTIN
)
1938 explanation
= d_sharedTerms
.explain(toExplain
.d_node
);
1939 Debug("theory::explain") << "\tTerm was propagated by THEORY_BUILTIN. Explanation: " << explanation
<< std::endl
;
1943 TrustNode texp
= theoryOf(toExplain
.d_theory
)->explain(toExplain
.d_node
);
1944 explanation
= texp
.getNode();
1945 Debug("theory::explain") << "\tTerm was propagated by owner theory: "
1946 << theoryOf(toExplain
.d_theory
)->getId()
1947 << ". Explanation: " << explanation
<< std::endl
;
1950 Debug("theory::explain")
1951 << "TheoryEngine::explain(): got explanation " << explanation
1952 << " got from " << toExplain
.d_theory
<< endl
;
1953 Assert(explanation
!= toExplain
.d_node
)
1954 << "wasn't sent to you, so why are you explaining it trivially";
1955 // Mark the explanation
1956 NodeTheoryPair
newExplain(
1957 explanation
, toExplain
.d_theory
, toExplain
.d_timestamp
);
1958 explanationVector
.push_back(newExplain
);
1963 if (proofRecipe
&& inputAssertions
)
1965 // If we're expanding the target node of the explanation (this is the
1966 // first expansion...), we don't want to add it as a separate proof
1967 // step. It is already part of the assertions.
1968 if (!ContainsKey(*inputAssertions
, toExplain
.d_node
))
1970 LemmaProofRecipe::ProofStep
proofStep(toExplain
.d_theory
,
1972 if (explanation
.getKind() == kind::AND
)
1974 Node flat
= flattenAnd(explanation
);
1975 for (unsigned k
= 0; k
< flat
.getNumChildren(); ++k
)
1977 // If a true constant or a negation of a false constant we can
1979 if (!((flat
[k
].isConst() && flat
[k
].getConst
<bool>())
1980 || (flat
[k
].getKind() == kind::NOT
&& flat
[k
][0].isConst()
1981 && !flat
[k
][0].getConst
<bool>())))
1983 proofStep
.addAssertion(flat
[k
].negate());
1989 if (!((explanation
.isConst() && explanation
.getConst
<bool>())
1990 || (explanation
.getKind() == kind::NOT
1991 && explanation
[0].isConst()
1992 && !explanation
[0].getConst
<bool>())))
1994 proofStep
.addAssertion(explanation
.negate());
1997 proofRecipe
->addStep(proofStep
);
2003 // Keep only the relevant literals
2004 explanationVector
.resize(j
);
2008 // The remaining literals are the base of the proof
2009 for (unsigned k
= 0; k
< explanationVector
.size(); ++k
) {
2010 proofRecipe
->addBaseAssertion(explanationVector
[k
].d_node
.negate());
2016 void TheoryEngine::setUserAttribute(const std::string
& attr
,
2018 const std::vector
<Node
>& node_values
,
2019 const std::string
& str_value
)
2021 Trace("te-attr") << "set user attribute " << attr
<< " " << n
<< endl
;
2022 if( d_attr_handle
.find( attr
)!=d_attr_handle
.end() ){
2023 for( size_t i
=0; i
<d_attr_handle
[attr
].size(); i
++ ){
2024 d_attr_handle
[attr
][i
]->setUserAttribute(attr
, n
, node_values
, str_value
);
2027 //unhandled exception?
2031 void TheoryEngine::handleUserAttribute(const char* attr
, Theory
* t
) {
2032 Trace("te-attr") << "Handle user attribute " << attr
<< " " << t
<< endl
;
2033 std::string
str( attr
);
2034 d_attr_handle
[ str
].push_back( t
);
2037 void TheoryEngine::checkTheoryAssertionsWithModel(bool hardFailure
) {
2038 for(TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
2039 Theory
* theory
= d_theoryTable
[theoryId
];
2040 if(theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
2041 for(context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(),
2042 it_end
= theory
->facts_end();
2045 Node assertion
= (*it
).d_assertion
;
2046 if (!isRelevant(assertion
))
2048 // not relevant, skip
2051 Node val
= getModel()->getValue(assertion
);
2054 std::stringstream ss
;
2055 ss
<< " " << theoryId
2056 << " has an asserted fact that the model doesn't satisfy." << endl
2057 << "The fact: " << assertion
<< endl
2058 << "Model value: " << val
<< endl
;
2063 // Always an error if it is false
2064 InternalError() << ss
.str();
2068 // Otherwise just a warning. Notice this case may happen for
2069 // assertions with unevaluable operators, e.g. transcendental
2070 // functions. It also may happen for separation logic, where
2071 // check-model support is limited.
2072 Warning() << ss
.str();
2081 std::pair
<bool, Node
> TheoryEngine::entailmentCheck(options::TheoryOfMode mode
,
2084 TNode atom
= (lit
.getKind() == kind::NOT
) ? lit
[0] : lit
;
2085 if( atom
.getKind()==kind::AND
|| atom
.getKind()==kind::OR
|| atom
.getKind()==kind::IMPLIES
){
2086 //Boolean connective, recurse
2087 std::vector
< Node
> children
;
2088 bool pol
= (lit
.getKind()!=kind::NOT
);
2089 bool is_conjunction
= pol
==(lit
.getKind()==kind::AND
);
2090 for( unsigned i
=0; i
<atom
.getNumChildren(); i
++ ){
2092 if( pol
==( lit
.getKind()==kind::IMPLIES
&& i
==0 ) ){
2093 ch
= atom
[i
].negate();
2095 std::pair
<bool, Node
> chres
= entailmentCheck(mode
, ch
);
2097 if( !is_conjunction
){
2100 children
.push_back( chres
.second
);
2102 }else if( !chres
.first
&& is_conjunction
){
2103 return std::pair
<bool, Node
>(false, Node::null());
2106 if( is_conjunction
){
2107 return std::pair
<bool, Node
>(true, NodeManager::currentNM()->mkNode(kind::AND
, children
));
2109 return std::pair
<bool, Node
>(false, Node::null());
2111 }else if( atom
.getKind()==kind::ITE
|| ( atom
.getKind()==kind::EQUAL
&& atom
[0].getType().isBoolean() ) ){
2112 bool pol
= (lit
.getKind()!=kind::NOT
);
2113 for( unsigned r
=0; r
<2; r
++ ){
2118 std::pair
<bool, Node
> chres
= entailmentCheck(mode
, ch
);
2120 Node ch2
= atom
[ atom
.getKind()==kind::ITE
? r
+1 : 1 ];
2121 if( pol
==( atom
.getKind()==kind::ITE
? true : r
==1 ) ){
2124 std::pair
<bool, Node
> chres2
= entailmentCheck(mode
, ch2
);
2126 return std::pair
<bool, Node
>(true, NodeManager::currentNM()->mkNode(kind::AND
, chres
.second
, chres2
.second
));
2132 return std::pair
<bool, Node
>(false, Node::null());
2134 //it is a theory atom
2135 theory::TheoryId tid
= theory::Theory::theoryOf(mode
, atom
);
2136 theory::Theory
* th
= theoryOf(tid
);
2139 Trace("theory-engine-entc") << "Entailment check : " << lit
<< std::endl
;
2141 std::pair
<bool, Node
> chres
= th
->entailmentCheck(lit
);
2146 void TheoryEngine::spendResource(ResourceManager::Resource r
)
2148 d_resourceManager
->spendResource(r
);
2151 }/* CVC4 namespace */