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/quantifiers_options.h"
32 #include "options/theory_options.h"
33 #include "preprocessing/assertion_pipeline.h"
34 #include "smt/logic_exception.h"
35 #include "smt/term_formula_removal.h"
36 #include "theory/arith/arith_ite_utils.h"
37 #include "theory/bv/theory_bv_utils.h"
38 #include "theory/care_graph.h"
39 #include "theory/combination_care_graph.h"
40 #include "theory/decision_manager.h"
41 #include "theory/quantifiers/first_order_model.h"
42 #include "theory/quantifiers/fmf/model_engine.h"
43 #include "theory/quantifiers/theory_quantifiers.h"
44 #include "theory/quantifiers_engine.h"
45 #include "theory/relevance_manager.h"
46 #include "theory/rewriter.h"
47 #include "theory/theory.h"
48 #include "theory/theory_engine_proof_generator.h"
49 #include "theory/theory_id.h"
50 #include "theory/theory_model.h"
51 #include "theory/theory_traits.h"
52 #include "theory/uf/equality_engine.h"
53 #include "util/resource_manager.h"
57 using namespace CVC4::preprocessing
;
58 using namespace CVC4::theory
;
62 /* -------------------------------------------------------------------------- */
67 * IMPORTANT: The order of the theories is important. For example, strings
68 * depends on arith, quantifiers needs to come as the very last.
69 * Do not change this order.
72 #define CVC4_FOR_EACH_THEORY \
73 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BUILTIN) \
74 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BOOL) \
75 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_UF) \
76 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_ARITH) \
77 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BV) \
78 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_FP) \
79 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_ARRAYS) \
80 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_DATATYPES) \
81 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_SEP) \
82 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_SETS) \
83 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_STRINGS) \
84 CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_QUANTIFIERS)
88 /* -------------------------------------------------------------------------- */
90 inline void flattenAnd(Node n
, std::vector
<TNode
>& out
){
91 Assert(n
.getKind() == kind::AND
);
92 for(Node::iterator i
=n
.begin(), i_end
=n
.end(); i
!= i_end
; ++i
){
94 if(curr
.getKind() == kind::AND
){
95 flattenAnd(curr
, out
);
102 inline Node
flattenAnd(Node n
){
103 std::vector
<TNode
> out
;
105 return NodeManager::currentNM()->mkNode(kind::AND
, out
);
109 * Compute the string for a given theory id. In this module, we use
110 * THEORY_SAT_SOLVER as an id, which is not a normal id but maps to
111 * THEORY_LAST. Thus, we need our own string conversion here.
113 * @param id The theory id
114 * @return The string corresponding to the theory id
116 std::string
getTheoryString(theory::TheoryId id
)
118 if (id
== theory::THEORY_SAT_SOLVER
)
120 return "THEORY_SAT_SOLVER";
124 std::stringstream ss
;
130 void TheoryEngine::finishInit() {
131 // NOTE: This seems to be required since
132 // theory::TheoryTraits<THEORY>::isParametric cannot be accessed without
133 // using the CVC4_FOR_EACH_THEORY_STATEMENT macro. -AJR
134 std::vector
<theory::Theory
*> paraTheories
;
135 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
136 #undef CVC4_FOR_EACH_THEORY_STATEMENT
138 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
139 if (theory::TheoryTraits<THEORY>::isParametric \
140 && d_logicInfo.isTheoryEnabled(THEORY)) \
142 paraTheories.push_back(theoryOf(THEORY)); \
144 // Collect the parametric theories, which are given to the theory combination
146 CVC4_FOR_EACH_THEORY
;
148 // Initialize the theory combination architecture
149 if (options::tcMode() == options::TcMode::CARE_GRAPH
)
151 d_tc
.reset(new CombinationCareGraph(*this, paraTheories
, d_pnm
));
155 Unimplemented() << "TheoryEngine::finishInit: theory combination mode "
156 << options::tcMode() << " not supported";
158 // create the relevance filter if any option requires it
159 if (options::relevanceFilter())
162 new RelevanceManager(d_userContext
, theory::Valuation(this)));
165 // initialize the quantifiers engine
166 if (d_logicInfo
.isQuantified())
168 // initialize the quantifiers engine
169 d_quantEngine
= new QuantifiersEngine(this, *d_decManager
.get(), d_pnm
);
171 // initialize the theory combination manager, which decides and allocates the
172 // equality engines to use for all theories.
175 // set the core equality engine on quantifiers engine
176 if (d_logicInfo
.isQuantified())
178 d_quantEngine
->setMasterEqualityEngine(d_tc
->getCoreEqualityEngine());
181 // finish initializing the theories by linking them with the appropriate
182 // utilities and then calling their finishInit method.
183 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
; ++ theoryId
) {
184 Theory
* t
= d_theoryTable
[theoryId
];
189 // setup the pointers to the utilities
190 const EeTheoryInfo
* eeti
= d_tc
->getEeTheoryInfo(theoryId
);
191 Assert(eeti
!= nullptr);
192 // the theory's official equality engine is the one specified by the
193 // equality engine manager
194 t
->setEqualityEngine(eeti
->d_usedEe
);
195 // set the quantifiers engine
196 t
->setQuantifiersEngine(d_quantEngine
);
197 // set the decision manager for the theory
198 t
->setDecisionManager(d_decManager
.get());
199 // finish initializing the theory
204 TheoryEngine::TheoryEngine(context::Context
* context
,
205 context::UserContext
* userContext
,
207 RemoveTermFormulas
& iteRemover
,
208 const LogicInfo
& logicInfo
)
209 : d_propEngine(nullptr),
211 d_userContext(userContext
),
212 d_logicInfo(logicInfo
),
217 d_pnm
, nullptr, d_userContext
, "TheoryEngine::LazyCDProof")
219 d_tepg(new TheoryEngineProofGenerator(d_pnm
, d_userContext
)),
220 d_sharedTerms(this, context
),
222 d_quantEngine(nullptr),
223 d_decManager(new DecisionManager(userContext
)),
224 d_relManager(nullptr),
225 d_preRegistrationVisitor(this, context
),
226 d_sharedTermsVisitor(d_sharedTerms
),
227 d_eager_model_building(false),
228 d_possiblePropagations(context
),
229 d_hasPropagated(context
),
230 d_inConflict(context
, false),
232 d_hasShutDown(false),
233 d_incomplete(context
, false),
234 d_propagationMap(context
),
235 d_propagationMapTimestamp(context
, 0),
236 d_propagatedLiterals(context
),
237 d_propagatedLiteralsIndex(context
, 0),
238 d_atomRequests(context
),
239 d_tpp(*this, iteRemover
),
240 d_combineTheoriesTime("TheoryEngine::combineTheoriesTime"),
243 d_interrupted(false),
244 d_resourceManager(rm
),
245 d_inPreregister(false),
246 d_factsAsserted(context
, false),
248 d_arithSubstitutionsAdded("theory::arith::zzz::arith::substitutions", 0)
250 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
;
253 d_theoryTable
[theoryId
] = NULL
;
254 d_theoryOut
[theoryId
] = NULL
;
257 smtStatisticsRegistry()->registerStat(&d_combineTheoriesTime
);
258 d_true
= NodeManager::currentNM()->mkConst
<bool>(true);
259 d_false
= NodeManager::currentNM()->mkConst
<bool>(false);
261 smtStatisticsRegistry()->registerStat(&d_arithSubstitutionsAdded
);
264 TheoryEngine::~TheoryEngine() {
265 Assert(d_hasShutDown
);
267 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
!= theory::THEORY_LAST
; ++ theoryId
) {
268 if(d_theoryTable
[theoryId
] != NULL
) {
269 delete d_theoryTable
[theoryId
];
270 delete d_theoryOut
[theoryId
];
274 delete d_quantEngine
;
276 smtStatisticsRegistry()->unregisterStat(&d_combineTheoriesTime
);
277 smtStatisticsRegistry()->unregisterStat(&d_arithSubstitutionsAdded
);
280 void TheoryEngine::interrupt() { d_interrupted
= true; }
281 void TheoryEngine::preRegister(TNode preprocessed
) {
283 Debug("theory") << "TheoryEngine::preRegister( " << preprocessed
<< ")" << std::endl
;
284 if(Dump
.isOn("missed-t-propagations")) {
285 d_possiblePropagations
.push_back(preprocessed
);
287 d_preregisterQueue
.push(preprocessed
);
289 if (!d_inPreregister
) {
290 // We're in pre-register
291 d_inPreregister
= true;
293 // Process the pre-registration queue
294 while (!d_preregisterQueue
.empty()) {
295 // Get the next atom to pre-register
296 preprocessed
= d_preregisterQueue
.front();
297 d_preregisterQueue
.pop();
299 if (d_logicInfo
.isSharingEnabled() && preprocessed
.getKind() == kind::EQUAL
) {
300 // When sharing is enabled, we propagate from the shared terms manager also
301 d_sharedTerms
.addEqualityToPropagate(preprocessed
);
304 // the atom should not have free variables
305 Debug("theory") << "TheoryEngine::preRegister: " << preprocessed
307 Assert(!expr::hasFreeVar(preprocessed
));
309 // Pre-register the terms in the atom
310 theory::TheoryIdSet theories
= NodeVisitor
<PreRegisterVisitor
>::run(
311 d_preRegistrationVisitor
, preprocessed
);
312 theories
= TheoryIdSetUtil::setRemove(THEORY_BOOL
, theories
);
313 // Remove the top theory, if any more that means multiple theories were
315 bool multipleTheories
=
316 TheoryIdSetUtil::setRemove(Theory::theoryOf(preprocessed
), theories
);
317 if (Configuration::isAssertionBuild())
320 // This should never throw an exception, since theories should be
321 // guaranteed to be initialized.
322 // These checks don't work with finite model finding, because it
323 // uses Rational constants to represent cardinality constraints,
324 // even though arithmetic isn't actually involved.
325 if (!options::finiteModelFind())
327 while ((i
= TheoryIdSetUtil::setPop(theories
)) != THEORY_LAST
)
329 if (!d_logicInfo
.isTheoryEnabled(i
))
331 LogicInfo newLogicInfo
= d_logicInfo
.getUnlockedCopy();
332 newLogicInfo
.enableTheory(i
);
334 std::stringstream ss
;
335 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
336 << ", which doesn't include " << i
337 << ", but found a term in that theory." << std::endl
338 << "You might want to extend your logic to "
339 << newLogicInfo
.getLogicString() << std::endl
;
340 throw LogicException(ss
.str());
345 if (multipleTheories
) {
346 // Collect the shared terms if there are multiple theories
347 NodeVisitor
<SharedTermsVisitor
>::run(d_sharedTermsVisitor
,
352 // Leaving pre-register
353 d_inPreregister
= false;
357 void TheoryEngine::printAssertions(const char* tag
) {
358 if (Trace
.isOn(tag
)) {
360 for (TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
361 Theory
* theory
= d_theoryTable
[theoryId
];
362 if (theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
363 Trace(tag
) << "--------------------------------------------" << endl
;
364 Trace(tag
) << "Assertions of " << theory
->getId() << ": " << endl
;
366 context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(),
369 for (unsigned i
= 0; it
!= it_end
; ++it
, ++i
)
371 if ((*it
).d_isPreregistered
)
373 Trace(tag
) << "[" << i
<< "]: ";
377 Trace(tag
) << "(" << i
<< "): ";
379 Trace(tag
) << (*it
).d_assertion
<< endl
;
383 if (d_logicInfo
.isSharingEnabled()) {
384 Trace(tag
) << "Shared terms of " << theory
->getId() << ": " << endl
;
385 context::CDList
<TNode
>::const_iterator it
= theory
->shared_terms_begin(), it_end
= theory
->shared_terms_end();
386 for (unsigned i
= 0; it
!= it_end
; ++ it
, ++i
) {
387 Trace(tag
) << "[" << i
<< "]: " << (*it
) << endl
;
395 void TheoryEngine::dumpAssertions(const char* tag
) {
396 if (Dump
.isOn(tag
)) {
397 Dump(tag
) << CommentCommand("Starting completeness check");
398 for (TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
399 Theory
* theory
= d_theoryTable
[theoryId
];
400 if (theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
401 Dump(tag
) << CommentCommand("Completeness check");
402 Dump(tag
) << PushCommand();
404 // Dump the shared terms
405 if (d_logicInfo
.isSharingEnabled()) {
406 Dump(tag
) << CommentCommand("Shared terms");
407 context::CDList
<TNode
>::const_iterator it
= theory
->shared_terms_begin(), it_end
= theory
->shared_terms_end();
408 for (unsigned i
= 0; it
!= it_end
; ++ it
, ++i
) {
411 Dump(tag
) << CommentCommand(ss
.str());
415 // Dump the assertions
416 Dump(tag
) << CommentCommand("Assertions");
417 context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(), it_end
= theory
->facts_end();
418 for (; it
!= it_end
; ++ it
) {
420 Node assertionNode
= (*it
).d_assertion
;
421 // Purify all the terms
423 if ((*it
).d_isPreregistered
)
425 Dump(tag
) << CommentCommand("Preregistered");
429 Dump(tag
) << CommentCommand("Shared assertion");
431 Dump(tag
) << AssertCommand(assertionNode
.toExpr());
433 Dump(tag
) << CheckSatCommand();
435 Dump(tag
) << PopCommand();
442 * Check all (currently-active) theories for conflicts.
443 * @param effort the effort level to use
445 void TheoryEngine::check(Theory::Effort effort
) {
448 // Reset the interrupt flag
449 d_interrupted
= false;
451 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
452 #undef CVC4_FOR_EACH_THEORY_STATEMENT
454 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
455 if (theory::TheoryTraits<THEORY>::hasCheck \
456 && d_logicInfo.isTheoryEnabled(THEORY)) \
458 theoryOf(THEORY)->check(effort); \
461 Debug("conflict") << THEORY << " in conflict. " << std::endl; \
469 // Mark the output channel unused (if this is FULL_EFFORT, and nothing
470 // is done by the theories, no additional check will be needed)
471 d_outputChannelUsed
= false;
473 // Mark the lemmas flag (no lemmas added)
474 d_lemmasAdded
= false;
476 Debug("theory") << "TheoryEngine::check(" << effort
<< "): d_factsAsserted = " << (d_factsAsserted
? "true" : "false") << endl
;
478 // If in full effort, we have a fake new assertion just to jumpstart the checking
479 if (Theory::fullEffort(effort
)) {
480 d_factsAsserted
= true;
481 // Reset round for the relevance manager, which notice only sets a flag
482 // to indicate that its information must be recomputed.
483 if (d_relManager
!= nullptr)
485 d_relManager
->resetRound();
491 while (d_factsAsserted
&& !d_inConflict
&& !d_lemmasAdded
) {
493 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running check" << endl
;
495 Trace("theory::assertions") << endl
;
496 if (Trace
.isOn("theory::assertions")) {
497 printAssertions("theory::assertions");
500 if(Theory::fullEffort(effort
)) {
501 Trace("theory::assertions::fulleffort") << endl
;
502 if (Trace
.isOn("theory::assertions::fulleffort")) {
503 printAssertions("theory::assertions::fulleffort");
507 // Note that we've discharged all the facts
508 d_factsAsserted
= false;
511 CVC4_FOR_EACH_THEORY
;
513 if(Dump
.isOn("missed-t-conflicts")) {
514 Dump("missed-t-conflicts")
515 << CommentCommand("Completeness check for T-conflicts; expect sat")
516 << CheckSatCommand();
519 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running propagation after the initial check" << endl
;
521 // We are still satisfiable, propagate as much as possible
524 // We do combination if all has been processed and we are in fullcheck
525 if (Theory::fullEffort(effort
) && d_logicInfo
.isSharingEnabled() && !d_factsAsserted
&& !d_lemmasAdded
&& !d_inConflict
) {
526 // Do the combination
527 Debug("theory") << "TheoryEngine::check(" << effort
<< "): running combination" << endl
;
529 TimerStat::CodeTimer
combineTheoriesTimer(d_combineTheoriesTime
);
530 d_tc
->combineTheories();
532 if(d_logicInfo
.isQuantified()){
533 d_quantEngine
->notifyCombineTheories();
538 // Must consult quantifiers theory for last call to ensure sat, or otherwise add a lemma
539 if( Theory::fullEffort(effort
) && ! d_inConflict
&& ! needCheck() ) {
540 Trace("theory::assertions-model") << endl
;
541 if (Trace
.isOn("theory::assertions-model")) {
542 printAssertions("theory::assertions-model");
544 // reset the model in the combination engine
546 //checks for theories requiring the model go at last call
547 for (TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
548 if( theoryId
!=THEORY_QUANTIFIERS
){
549 Theory
* theory
= d_theoryTable
[theoryId
];
550 if (theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
551 if( theory
->needsCheckLastEffort() ){
552 if (!d_tc
->buildModel())
556 theory
->check(Theory::EFFORT_LAST_CALL
);
563 if(d_logicInfo
.isQuantified()) {
564 // quantifiers engine must check at last call effort
565 d_quantEngine
->check(Theory::EFFORT_LAST_CALL
);
568 if (!d_inConflict
&& !needCheck())
570 // If d_eager_model_building is false, then we only mark that we
571 // are in "SAT mode". We build the model later only if the user asks
572 // for it via getBuiltModel.
574 if (d_eager_model_building
)
581 Debug("theory") << "TheoryEngine::check(" << effort
<< "): done, we are " << (d_inConflict
? "unsat" : "sat") << (d_lemmasAdded
? " with new lemmas" : " with no new lemmas");
582 Debug("theory") << ", need check = " << (needCheck() ? "YES" : "NO") << endl
;
584 if( Theory::fullEffort(effort
) && !d_inConflict
&& !needCheck()) {
585 // Do post-processing of model from the theories (e.g. used for THEORY_SEP
586 // to construct heap model)
587 d_tc
->postProcessModel(d_incomplete
.get());
589 } catch(const theory::Interrupted
&) {
590 Trace("theory") << "TheoryEngine::check() => interrupted" << endl
;
592 // If fulleffort, check all theories
593 if(Dump
.isOn("theory::fullcheck") && Theory::fullEffort(effort
)) {
594 if (!d_inConflict
&& !needCheck()) {
595 dumpAssertions("theory::fullcheck");
600 void TheoryEngine::propagate(Theory::Effort effort
)
602 // Reset the interrupt flag
603 d_interrupted
= false;
605 // Definition of the statement that is to be run by every theory
606 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
607 #undef CVC4_FOR_EACH_THEORY_STATEMENT
609 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
610 if (theory::TheoryTraits<THEORY>::hasPropagate && d_logicInfo.isTheoryEnabled(THEORY)) { \
611 theoryOf(THEORY)->propagate(effort); \
614 // Reset the interrupt flag
615 d_interrupted
= false;
617 // Propagate for each theory using the statement above
618 CVC4_FOR_EACH_THEORY
;
620 if(Dump
.isOn("missed-t-propagations")) {
621 for(unsigned i
= 0; i
< d_possiblePropagations
.size(); ++i
) {
622 Node atom
= d_possiblePropagations
[i
];
624 if(d_propEngine
->hasValue(atom
, value
)) {
627 // Doesn't have a value, check it (and the negation)
628 if(d_hasPropagated
.find(atom
) == d_hasPropagated
.end()) {
629 Dump("missed-t-propagations")
630 << CommentCommand("Completeness check for T-propagations; expect invalid")
631 << EchoCommand(atom
.toString())
632 << QueryCommand(atom
.toExpr())
633 << EchoCommand(atom
.notNode().toString())
634 << QueryCommand(atom
.notNode().toExpr());
640 Node
TheoryEngine::getNextDecisionRequest()
642 return d_decManager
->getNextDecisionRequest();
645 bool TheoryEngine::properConflict(TNode conflict
) const {
647 if (conflict
.getKind() == kind::AND
) {
648 for (unsigned i
= 0; i
< conflict
.getNumChildren(); ++ i
) {
649 if (! getPropEngine()->hasValue(conflict
[i
], value
)) {
650 Debug("properConflict") << "Bad conflict is due to unassigned atom: "
651 << conflict
[i
] << endl
;
655 Debug("properConflict") << "Bad conflict is due to false atom: "
656 << conflict
[i
] << endl
;
659 if (conflict
[i
] != Rewriter::rewrite(conflict
[i
])) {
660 Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
661 << conflict
[i
] << " vs " << Rewriter::rewrite(conflict
[i
]) << endl
;
666 if (! getPropEngine()->hasValue(conflict
, value
)) {
667 Debug("properConflict") << "Bad conflict is due to unassigned atom: "
672 Debug("properConflict") << "Bad conflict is due to false atom: "
676 if (conflict
!= Rewriter::rewrite(conflict
)) {
677 Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
678 << conflict
<< " vs " << Rewriter::rewrite(conflict
) << endl
;
685 TheoryModel
* TheoryEngine::getModel()
687 Assert(d_tc
!= nullptr);
688 TheoryModel
* m
= d_tc
->getModel();
689 Assert(m
!= nullptr);
693 TheoryModel
* TheoryEngine::getBuiltModel()
695 Assert(d_tc
!= nullptr);
696 // If this method was called, we should be in SAT mode, and produceModels
698 AlwaysAssert(options::produceModels());
701 // not available, perhaps due to interuption.
704 // must build model at this point
705 if (!d_tc
->buildModel())
709 return d_tc
->getModel();
712 bool TheoryEngine::buildModel()
714 Assert(d_tc
!= nullptr);
715 return d_tc
->buildModel();
718 bool TheoryEngine::getSynthSolutions(
719 std::map
<Node
, std::map
<Node
, Node
>>& sol_map
)
723 return d_quantEngine
->getSynthSolutions(sol_map
);
725 // we are not in a quantified logic, there is no synthesis solution
729 bool TheoryEngine::presolve() {
730 // Reset the interrupt flag
731 d_interrupted
= false;
733 // Reset the decision manager. This clears its decision strategies that are
734 // no longer valid in this user context.
735 d_decManager
->presolve();
738 // Definition of the statement that is to be run by every theory
739 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
740 #undef CVC4_FOR_EACH_THEORY_STATEMENT
742 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
743 if (theory::TheoryTraits<THEORY>::hasPresolve) { \
744 theoryOf(THEORY)->presolve(); \
750 // Presolve for each theory using the statement above
751 CVC4_FOR_EACH_THEORY
;
752 } catch(const theory::Interrupted
&) {
753 Trace("theory") << "TheoryEngine::presolve() => interrupted" << endl
;
755 // return whether we have a conflict
757 }/* TheoryEngine::presolve() */
759 void TheoryEngine::postsolve() {
760 // no longer in SAT mode
762 // Reset the interrupt flag
763 d_interrupted
= false;
764 bool CVC4_UNUSED wasInConflict
= d_inConflict
;
767 // Definition of the statement that is to be run by every theory
768 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
769 #undef CVC4_FOR_EACH_THEORY_STATEMENT
771 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
772 if (theory::TheoryTraits<THEORY>::hasPostsolve) \
774 theoryOf(THEORY)->postsolve(); \
775 Assert(!d_inConflict || wasInConflict) \
776 << "conflict raised during postsolve()"; \
779 // Postsolve for each theory using the statement above
780 CVC4_FOR_EACH_THEORY
;
781 } catch(const theory::Interrupted
&) {
782 Trace("theory") << "TheoryEngine::postsolve() => interrupted" << endl
;
784 }/* TheoryEngine::postsolve() */
787 void TheoryEngine::notifyRestart() {
788 // Reset the interrupt flag
789 d_interrupted
= false;
791 // Definition of the statement that is to be run by every theory
792 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
793 #undef CVC4_FOR_EACH_THEORY_STATEMENT
795 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
796 if (theory::TheoryTraits<THEORY>::hasNotifyRestart && d_logicInfo.isTheoryEnabled(THEORY)) { \
797 theoryOf(THEORY)->notifyRestart(); \
800 // notify each theory using the statement above
801 CVC4_FOR_EACH_THEORY
;
804 void TheoryEngine::ppStaticLearn(TNode in
, NodeBuilder
<>& learned
) {
805 // Reset the interrupt flag
806 d_interrupted
= false;
808 // Definition of the statement that is to be run by every theory
809 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
810 #undef CVC4_FOR_EACH_THEORY_STATEMENT
812 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
813 if (theory::TheoryTraits<THEORY>::hasPpStaticLearn) { \
814 theoryOf(THEORY)->ppStaticLearn(in, learned); \
817 // static learning for each theory using the statement above
818 CVC4_FOR_EACH_THEORY
;
821 bool TheoryEngine::isRelevant(Node lit
) const
823 if (d_relManager
!= nullptr)
825 return d_relManager
->isRelevant(lit
);
827 // otherwise must assume its relevant
831 void TheoryEngine::shutdown() {
832 // Set this first; if a Theory shutdown() throws an exception,
833 // at least the destruction of the TheoryEngine won't confound
835 d_hasShutDown
= true;
837 // Shutdown all the theories
838 for(TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
; ++theoryId
) {
839 if(d_theoryTable
[theoryId
]) {
840 theoryOf(theoryId
)->shutdown();
847 theory::Theory::PPAssertStatus
TheoryEngine::solve(TNode literal
, SubstitutionMap
& substitutionOut
) {
848 // Reset the interrupt flag
849 d_interrupted
= false;
851 TNode atom
= literal
.getKind() == kind::NOT
? literal
[0] : literal
;
852 Trace("theory::solve") << "TheoryEngine::solve(" << literal
<< "): solving with " << theoryOf(atom
)->getId() << endl
;
854 if(! d_logicInfo
.isTheoryEnabled(Theory::theoryOf(atom
)) &&
855 Theory::theoryOf(atom
) != THEORY_SAT_SOLVER
) {
857 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
858 << ", which doesn't include " << Theory::theoryOf(atom
)
859 << ", but got a preprocessing-time fact for that theory." << endl
860 << "The fact:" << endl
862 throw LogicException(ss
.str());
865 Theory::PPAssertStatus solveStatus
= theoryOf(atom
)->ppAssert(literal
, substitutionOut
);
866 Trace("theory::solve") << "TheoryEngine::solve(" << literal
<< ") => " << solveStatus
<< endl
;
870 void TheoryEngine::preprocessStart() { d_tpp
.clearCache(); }
872 Node
TheoryEngine::preprocess(TNode assertion
) {
873 TrustNode trn
= d_tpp
.theoryPreprocess(assertion
);
879 return trn
.getNode();
882 void TheoryEngine::notifyPreprocessedAssertions(
883 const std::vector
<Node
>& assertions
) {
884 // call all the theories
885 for (TheoryId theoryId
= theory::THEORY_FIRST
; theoryId
< theory::THEORY_LAST
;
887 if (d_theoryTable
[theoryId
]) {
888 theoryOf(theoryId
)->ppNotifyAssertions(assertions
);
891 if (d_relManager
!= nullptr)
893 d_relManager
->notifyPreprocessedAssertions(assertions
);
897 bool TheoryEngine::markPropagation(TNode assertion
, TNode originalAssertion
, theory::TheoryId toTheoryId
, theory::TheoryId fromTheoryId
) {
899 // What and where we are asserting
900 NodeTheoryPair
toAssert(assertion
, toTheoryId
, d_propagationMapTimestamp
);
901 // What and where it came from
902 NodeTheoryPair
toExplain(originalAssertion
, fromTheoryId
, d_propagationMapTimestamp
);
904 // See if the theory already got this literal
905 PropagationMap::const_iterator find
= d_propagationMap
.find(toAssert
);
906 if (find
!= d_propagationMap
.end()) {
907 // The theory already knows this
908 Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): already there" << endl
;
912 Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): marking [" << d_propagationMapTimestamp
<< "] " << assertion
<< ", " << toTheoryId
<< " from " << originalAssertion
<< ", " << fromTheoryId
<< endl
;
914 // Mark the propagation
915 d_propagationMap
[toAssert
] = toExplain
;
916 d_propagationMapTimestamp
= d_propagationMapTimestamp
+ 1;
922 void TheoryEngine::assertToTheory(TNode assertion
, TNode originalAssertion
, theory::TheoryId toTheoryId
, theory::TheoryId fromTheoryId
) {
924 Trace("theory::assertToTheory") << "TheoryEngine::assertToTheory(" << assertion
<< ", " << originalAssertion
<< "," << toTheoryId
<< ", " << fromTheoryId
<< ")" << endl
;
926 Assert(toTheoryId
!= fromTheoryId
);
927 if(toTheoryId
!= THEORY_SAT_SOLVER
&&
928 ! d_logicInfo
.isTheoryEnabled(toTheoryId
)) {
930 ss
<< "The logic was specified as " << d_logicInfo
.getLogicString()
931 << ", which doesn't include " << toTheoryId
932 << ", but got an asserted fact to that theory." << endl
933 << "The fact:" << endl
935 throw LogicException(ss
.str());
942 // If sharing is disabled, things are easy
943 if (!d_logicInfo
.isSharingEnabled()) {
944 Assert(assertion
== originalAssertion
);
945 if (fromTheoryId
== THEORY_SAT_SOLVER
) {
946 // Send to the apropriate theory
947 theory::Theory
* toTheory
= theoryOf(toTheoryId
);
948 // We assert it, and we know it's preregistereed
949 toTheory
->assertFact(assertion
, true);
950 // Mark that we have more information
951 d_factsAsserted
= true;
953 Assert(toTheoryId
== THEORY_SAT_SOLVER
);
954 // Check for propositional conflict
956 if (d_propEngine
->hasValue(assertion
, value
)) {
958 Trace("theory::propagate") << "TheoryEngine::assertToTheory(" << assertion
<< ", " << toTheoryId
<< ", " << fromTheoryId
<< "): conflict (no sharing)" << endl
;
959 Trace("dtview::conflict")
960 << ":THEORY-CONFLICT: " << assertion
<< std::endl
;
966 d_propagatedLiterals
.push_back(assertion
);
971 // Polarity of the assertion
972 bool polarity
= assertion
.getKind() != kind::NOT
;
974 // Atom of the assertion
975 TNode atom
= polarity
? assertion
: assertion
[0];
977 // If sending to the shared terms database, it's also simple
978 if (toTheoryId
== THEORY_BUILTIN
) {
979 Assert(atom
.getKind() == kind::EQUAL
)
980 << "atom should be an EQUALity, not `" << atom
<< "'";
981 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
982 d_sharedTerms
.assertEquality(atom
, polarity
, assertion
);
987 // Things from the SAT solver are already normalized, so they go
988 // directly to the apropriate theory
989 if (fromTheoryId
== THEORY_SAT_SOLVER
) {
990 // We know that this is normalized, so just send it off to the theory
991 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
992 // Is it preregistered
993 bool preregistered
= d_propEngine
->isSatLiteral(assertion
) && Theory::theoryOf(assertion
) == toTheoryId
;
995 theoryOf(toTheoryId
)->assertFact(assertion
, preregistered
);
996 // Mark that we have more information
997 d_factsAsserted
= true;
1002 // Propagations to the SAT solver are just enqueued for pickup by
1003 // the SAT solver later
1004 if (toTheoryId
== THEORY_SAT_SOLVER
) {
1005 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1006 // Enqueue for propagation to the SAT solver
1007 d_propagatedLiterals
.push_back(assertion
);
1008 // Check for propositional conflicts
1010 if (d_propEngine
->hasValue(assertion
, value
) && !value
) {
1011 Trace("theory::propagate")
1012 << "TheoryEngine::assertToTheory(" << assertion
<< ", "
1013 << toTheoryId
<< ", " << fromTheoryId
<< "): conflict (sharing)"
1015 Trace("dtview::conflict")
1016 << ":THEORY-CONFLICT: " << assertion
<< std::endl
;
1017 d_inConflict
= true;
1023 Assert(atom
.getKind() == kind::EQUAL
);
1026 Node normalizedLiteral
= Rewriter::rewrite(assertion
);
1028 // See if it rewrites false directly -> conflict
1029 if (normalizedLiteral
.isConst()) {
1030 if (!normalizedLiteral
.getConst
<bool>()) {
1031 // Mark the propagation for explanations
1032 if (markPropagation(normalizedLiteral
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1033 // special case, trust node has no proof generator
1034 TrustNode trnn
= TrustNode::mkTrustConflict(normalizedLiteral
);
1035 // Get the explanation (conflict will figure out where it came from)
1036 conflict(trnn
, toTheoryId
);
1044 // Try and assert (note that we assert the non-normalized one)
1045 if (markPropagation(assertion
, originalAssertion
, toTheoryId
, fromTheoryId
)) {
1046 // Check if has been pre-registered with the theory
1047 bool preregistered
= d_propEngine
->isSatLiteral(assertion
) && Theory::theoryOf(assertion
) == toTheoryId
;
1049 theoryOf(toTheoryId
)->assertFact(assertion
, preregistered
);
1050 d_factsAsserted
= true;
1056 void TheoryEngine::assertFact(TNode literal
)
1058 Trace("theory") << "TheoryEngine::assertFact(" << literal
<< ")" << endl
;
1062 // If we're in conflict, nothing to do
1068 bool polarity
= literal
.getKind() != kind::NOT
;
1069 TNode atom
= polarity
? literal
: literal
[0];
1071 if (d_logicInfo
.isSharingEnabled()) {
1072 // If any shared terms, it's time to do sharing work
1073 if (d_sharedTerms
.hasSharedTerms(atom
)) {
1074 // Notify the theories the shared terms
1075 SharedTermsDatabase::shared_terms_iterator it
= d_sharedTerms
.begin(atom
);
1076 SharedTermsDatabase::shared_terms_iterator it_end
= d_sharedTerms
.end(atom
);
1077 for (; it
!= it_end
; ++ it
) {
1079 theory::TheoryIdSet theories
=
1080 d_sharedTerms
.getTheoriesToNotify(atom
, term
);
1081 for (TheoryId id
= THEORY_FIRST
; id
!= THEORY_LAST
; ++ id
) {
1082 if (TheoryIdSetUtil::setContains(id
, theories
))
1084 theoryOf(id
)->addSharedTerm(term
);
1087 d_sharedTerms
.markNotified(term
, theories
);
1091 // If it's an equality, assert it to the shared term manager, even though the terms are not
1092 // yet shared. As the terms become shared later, the shared terms manager will then add them
1093 // to the assert the equality to the interested theories
1094 if (atom
.getKind() == kind::EQUAL
) {
1095 // Assert it to the the owning theory
1096 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1097 // Shared terms manager will assert to interested theories directly, as
1098 // the terms become shared
1099 assertToTheory(literal
, literal
, /* to */ THEORY_BUILTIN
, /* from */ THEORY_SAT_SOLVER
);
1101 // Now, let's check for any atom triggers from lemmas
1102 AtomRequests::atom_iterator it
= d_atomRequests
.getAtomIterator(atom
);
1103 while (!it
.done()) {
1104 const AtomRequests::Request
& request
= it
.get();
1106 polarity
? (Node
)request
.d_atom
: request
.d_atom
.notNode();
1107 Debug("theory::atoms") << "TheoryEngine::assertFact(" << literal
<< "): sending requested " << toAssert
<< endl
;
1109 toAssert
, literal
, request
.d_toTheory
, THEORY_SAT_SOLVER
);
1114 // Not an equality, just assert to the appropriate theory
1115 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1118 // Assert the fact to the appropriate theory directly
1119 assertToTheory(literal
, literal
, /* to */ Theory::theoryOf(atom
), /* from */ THEORY_SAT_SOLVER
);
1123 bool TheoryEngine::propagate(TNode literal
, theory::TheoryId theory
) {
1124 Debug("theory::propagate") << "TheoryEngine::propagate(" << literal
<< ", " << theory
<< ")" << endl
;
1126 Trace("dtview::prop") << std::string(d_context
->getLevel(), ' ')
1127 << ":THEORY-PROP: " << literal
<< endl
;
1131 if(Dump
.isOn("t-propagations")) {
1132 Dump("t-propagations") << CommentCommand("negation of theory propagation: expect valid")
1133 << QueryCommand(literal
.toExpr());
1135 if(Dump
.isOn("missed-t-propagations")) {
1136 d_hasPropagated
.insert(literal
);
1140 bool polarity
= literal
.getKind() != kind::NOT
;
1141 TNode atom
= polarity
? literal
: literal
[0];
1143 if (d_logicInfo
.isSharingEnabled() && atom
.getKind() == kind::EQUAL
) {
1144 if (d_propEngine
->isSatLiteral(literal
)) {
1145 // We propagate SAT literals to SAT
1146 assertToTheory(literal
, literal
, /* to */ THEORY_SAT_SOLVER
, /* from */ theory
);
1148 if (theory
!= THEORY_BUILTIN
) {
1149 // Assert to the shared terms database
1150 assertToTheory(literal
, literal
, /* to */ THEORY_BUILTIN
, /* from */ theory
);
1153 // Just send off to the SAT solver
1154 Assert(d_propEngine
->isSatLiteral(literal
));
1155 assertToTheory(literal
, literal
, /* to */ THEORY_SAT_SOLVER
, /* from */ theory
);
1158 return !d_inConflict
;
1161 const LogicInfo
& TheoryEngine::getLogicInfo() const { return d_logicInfo
; }
1163 theory::EqualityStatus
TheoryEngine::getEqualityStatus(TNode a
, TNode b
) {
1164 Assert(a
.getType().isComparableTo(b
.getType()));
1165 if (d_sharedTerms
.isShared(a
) && d_sharedTerms
.isShared(b
)) {
1166 if (d_sharedTerms
.areEqual(a
,b
)) {
1167 return EQUALITY_TRUE_AND_PROPAGATED
;
1169 else if (d_sharedTerms
.areDisequal(a
,b
)) {
1170 return EQUALITY_FALSE_AND_PROPAGATED
;
1173 return theoryOf(Theory::theoryOf(a
.getType()))->getEqualityStatus(a
, b
);
1176 Node
TheoryEngine::getModelValue(TNode var
) {
1179 // the model value of a constant must be itself
1182 Assert(d_sharedTerms
.isShared(var
));
1183 return theoryOf(Theory::theoryOf(var
.getType()))->getModelValue(var
);
1187 Node
TheoryEngine::ensureLiteral(TNode n
) {
1188 Debug("ensureLiteral") << "rewriting: " << n
<< std::endl
;
1189 Node rewritten
= Rewriter::rewrite(n
);
1190 Debug("ensureLiteral") << " got: " << rewritten
<< std::endl
;
1191 Node preprocessed
= preprocess(rewritten
);
1192 Debug("ensureLiteral") << "preprocessed: " << preprocessed
<< std::endl
;
1193 d_propEngine
->ensureLiteral(preprocessed
);
1194 return preprocessed
;
1198 void TheoryEngine::printInstantiations( std::ostream
& out
) {
1199 if( d_quantEngine
){
1200 d_quantEngine
->printInstantiations( out
);
1202 out
<< "Internal error : instantiations not available when quantifiers are not present." << std::endl
;
1207 void TheoryEngine::printSynthSolution( std::ostream
& out
) {
1208 if( d_quantEngine
){
1209 d_quantEngine
->printSynthSolution( out
);
1211 out
<< "Internal error : synth solution not available when quantifiers are not present." << std::endl
;
1216 void TheoryEngine::getInstantiatedQuantifiedFormulas( std::vector
< Node
>& qs
) {
1217 if( d_quantEngine
){
1218 d_quantEngine
->getInstantiatedQuantifiedFormulas( qs
);
1224 void TheoryEngine::getInstantiations( Node q
, std::vector
< Node
>& insts
) {
1225 if( d_quantEngine
){
1226 d_quantEngine
->getInstantiations( q
, insts
);
1232 void TheoryEngine::getInstantiationTermVectors( Node q
, std::vector
< std::vector
< Node
> >& tvecs
) {
1233 if( d_quantEngine
){
1234 d_quantEngine
->getInstantiationTermVectors( q
, tvecs
);
1240 void TheoryEngine::getInstantiations( std::map
< Node
, std::vector
< Node
> >& insts
) {
1241 if( d_quantEngine
){
1242 d_quantEngine
->getInstantiations( insts
);
1248 void TheoryEngine::getInstantiationTermVectors( std::map
< Node
, std::vector
< std::vector
< Node
> > >& insts
) {
1249 if( d_quantEngine
){
1250 d_quantEngine
->getInstantiationTermVectors( insts
);
1256 Node
TheoryEngine::getInstantiatedConjunction( Node q
) {
1257 if( d_quantEngine
){
1258 return d_quantEngine
->getInstantiatedConjunction( q
);
1261 return Node::null();
1266 static Node
mkExplanation(const std::vector
<NodeTheoryPair
>& explanation
) {
1268 std::set
<TNode
> all
;
1269 for (unsigned i
= 0; i
< explanation
.size(); ++ i
) {
1270 Assert(explanation
[i
].d_theory
== THEORY_SAT_SOLVER
);
1271 all
.insert(explanation
[i
].d_node
);
1274 if (all
.size() == 0) {
1275 // Normalize to true
1276 return NodeManager::currentNM()->mkConst
<bool>(true);
1279 if (all
.size() == 1) {
1280 // All the same, or just one
1281 return explanation
[0].d_node
;
1284 NodeBuilder
<> conjunction(kind::AND
);
1285 std::set
<TNode
>::const_iterator it
= all
.begin();
1286 std::set
<TNode
>::const_iterator it_end
= all
.end();
1287 while (it
!= it_end
) {
1295 TrustNode
TheoryEngine::getExplanation(TNode node
)
1297 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
1298 << "): current propagation index = "
1299 << d_propagationMapTimestamp
<< endl
;
1301 bool polarity
= node
.getKind() != kind::NOT
;
1302 TNode atom
= polarity
? node
: node
[0];
1304 // If we're not in shared mode, explanations are simple
1305 if (!d_logicInfo
.isSharingEnabled())
1307 Debug("theory::explain")
1308 << "TheoryEngine::getExplanation: sharing is NOT enabled. "
1309 << " Responsible theory is: " << theoryOf(atom
)->getId() << std::endl
;
1311 TrustNode texplanation
= theoryOf(atom
)->explain(node
);
1312 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
1313 << ") => " << texplanation
.getNode() << endl
;
1314 return texplanation
;
1317 Debug("theory::explain") << "TheoryEngine::getExplanation: sharing IS enabled"
1320 // Initial thing to explain
1321 NodeTheoryPair
toExplain(node
, THEORY_SAT_SOLVER
, d_propagationMapTimestamp
);
1322 Assert(d_propagationMap
.find(toExplain
) != d_propagationMap
.end());
1324 NodeTheoryPair nodeExplainerPair
= d_propagationMap
[toExplain
];
1325 Debug("theory::explain")
1326 << "TheoryEngine::getExplanation: explainer for node "
1327 << nodeExplainerPair
.d_node
1328 << " is theory: " << nodeExplainerPair
.d_theory
<< std::endl
;
1330 // Create the workplace for explanations
1331 std::vector
<NodeTheoryPair
> explanationVector
;
1332 explanationVector
.push_back(d_propagationMap
[toExplain
]);
1333 // Process the explanation
1334 TrustNode texplanation
= getExplanation(explanationVector
);
1335 Debug("theory::explain") << "TheoryEngine::getExplanation(" << node
<< ") => "
1336 << texplanation
.getNode() << endl
;
1337 return texplanation
;
1340 struct AtomsCollect
{
1342 std::vector
<TNode
> d_atoms
;
1343 std::unordered_set
<TNode
, TNodeHashFunction
> d_visited
;
1347 typedef void return_type
;
1349 bool alreadyVisited(TNode current
, TNode parent
) {
1350 // Check if already visited
1351 if (d_visited
.find(current
) != d_visited
.end()) return true;
1352 // Don't visit non-boolean
1353 if (!current
.getType().isBoolean()) return true;
1358 void visit(TNode current
, TNode parent
) {
1359 if (Theory::theoryOf(current
) != theory::THEORY_BOOL
) {
1360 d_atoms
.push_back(current
);
1362 d_visited
.insert(current
);
1365 void start(TNode node
) {}
1366 void done(TNode node
) {}
1368 std::vector
<TNode
> getAtoms() const {
1373 void TheoryEngine::ensureLemmaAtoms(const std::vector
<TNode
>& atoms
, theory::TheoryId atomsTo
) {
1374 for (unsigned i
= 0; i
< atoms
.size(); ++ i
) {
1376 // Non-equality atoms are either owned by theory or they don't make sense
1377 if (atoms
[i
].getKind() != kind::EQUAL
) {
1383 // Simple normalization to not repeat stuff
1384 if (eq
[0] > eq
[1]) {
1385 eq
= eq
[1].eqNode(eq
[0]);
1388 // Rewrite the equality
1389 Node eqNormalized
= Rewriter::rewrite(atoms
[i
]);
1391 Debug("theory::atoms") << "TheoryEngine::ensureLemmaAtoms(): " << eq
<< " with nf " << eqNormalized
<< endl
;
1393 // If the equality is a boolean constant, we send immediately
1394 if (eqNormalized
.isConst()) {
1395 if (eqNormalized
.getConst
<bool>()) {
1396 assertToTheory(eq
, eqNormalized
, /** to */ atomsTo
, /** Sat solver */ theory::THEORY_SAT_SOLVER
);
1398 assertToTheory(eq
.notNode(), eqNormalized
.notNode(), /** to */ atomsTo
, /** Sat solver */ theory::THEORY_SAT_SOLVER
);
1401 }else if( eqNormalized
.getKind() != kind::EQUAL
){
1402 Assert(eqNormalized
.getKind() == kind::BOOLEAN_TERM_VARIABLE
1403 || (eqNormalized
.getKind() == kind::NOT
1404 && eqNormalized
[0].getKind() == kind::BOOLEAN_TERM_VARIABLE
));
1405 // this happens for Boolean term equalities V = true that are rewritten to V, we should skip
1406 // TODO : revisit this
1410 // If the normalization did the just flips, keep the flip
1411 if (eqNormalized
[0] == eq
[1] && eqNormalized
[1] == eq
[0]) {
1415 // Check if the equality is already known by the sat solver
1416 if (d_propEngine
->isSatLiteral(eqNormalized
)) {
1418 if (d_propEngine
->hasValue(eqNormalized
, value
)) {
1420 assertToTheory(eq
, eqNormalized
, atomsTo
, theory::THEORY_SAT_SOLVER
);
1423 assertToTheory(eq
.notNode(), eqNormalized
.notNode(), atomsTo
, theory::THEORY_SAT_SOLVER
);
1429 // If the theory is asking about a different form, or the form is ok but if will go to a different theory
1430 // then we must figure it out
1431 if (eqNormalized
!= eq
|| Theory::theoryOf(eq
) != atomsTo
) {
1432 // If you get eqNormalized, send atoms[i] to atomsTo
1433 d_atomRequests
.add(eqNormalized
, eq
, atomsTo
);
1438 theory::LemmaStatus
TheoryEngine::lemma(theory::TrustNode tlemma
,
1439 theory::LemmaProperty p
,
1440 theory::TheoryId atomsTo
,
1441 theory::TheoryId from
)
1443 // For resource-limiting (also does a time check).
1445 Assert(tlemma
.getKind() == TrustNodeKind::LEMMA
1446 || tlemma
.getKind() == TrustNodeKind::CONFLICT
);
1448 Node node
= tlemma
.getNode();
1449 Node lemma
= tlemma
.getProven();
1451 // when proofs are enabled, we ensure the trust node has a generator by
1452 // adding a trust step to the lazy proof maintained by this class
1453 if (isProofEnabled())
1455 // ensure proof: set THEORY_LEMMA if no generator is provided
1456 if (tlemma
.getGenerator() == nullptr)
1458 // internal lemmas should have generators
1459 Assert(from
!= THEORY_LAST
);
1460 // add theory lemma step to proof
1461 Node tidn
= builtin::BuiltinProofRuleChecker::mkTheoryIdNode(from
);
1462 d_lazyProof
->addStep(lemma
, PfRule::THEORY_LEMMA
, {}, {lemma
, tidn
});
1463 // update the trust node
1464 tlemma
= TrustNode::mkTrustLemma(lemma
, d_lazyProof
.get());
1467 tlemma
.debugCheckClosed("te-proof-debug", "TheoryEngine::lemma_initial");
1470 // Do we need to check atoms
1471 if (atomsTo
!= theory::THEORY_LAST
) {
1472 Debug("theory::atoms") << "TheoryEngine::lemma(" << node
<< ", " << atomsTo
<< ")" << endl
;
1473 AtomsCollect collectAtoms
;
1474 NodeVisitor
<AtomsCollect
>::run(collectAtoms
, node
);
1475 ensureLemmaAtoms(collectAtoms
.getAtoms(), atomsTo
);
1478 if(Dump
.isOn("t-lemmas")) {
1479 // we dump the negation of the lemma, to show validity of the lemma
1480 Node n
= lemma
.negate();
1481 Dump("t-lemmas") << CommentCommand("theory lemma: expect valid")
1482 << CheckSatCommand(n
.toExpr());
1484 bool removable
= isLemmaPropertyRemovable(p
);
1485 bool preprocess
= isLemmaPropertyPreprocess(p
);
1487 // call preprocessor
1488 std::vector
<TrustNode
> newLemmas
;
1489 std::vector
<Node
> newSkolems
;
1491 d_tpp
.preprocess(lemma
, newLemmas
, newSkolems
, preprocess
);
1492 // the preprocessed lemma
1494 if (tplemma
.isNull())
1500 Assert(tplemma
.getKind() == TrustNodeKind::REWRITE
);
1501 lemmap
= tplemma
.getNode();
1503 // must update the trust lemma
1504 if (lemmap
!= lemma
)
1506 // process the preprocessing
1507 if (isProofEnabled())
1509 Assert(d_lazyProof
!= nullptr);
1510 // add the original proof to the lazy proof
1511 d_lazyProof
->addLazyStep(tlemma
.getProven(), tlemma
.getGenerator());
1512 // only need to do anything if lemmap changed in a non-trivial way
1513 if (!CDProof::isSame(lemmap
, lemma
))
1515 d_lazyProof
->addLazyStep(tplemma
.getProven(),
1516 tplemma
.getGenerator(),
1518 "TheoryEngine::lemma_pp",
1520 PfRule::PREPROCESS_LEMMA
);
1521 // ---------- from d_lazyProof -------------- from theory preprocess
1522 // lemma lemma = lemmap
1523 // ------------------------------------------ MACRO_SR_PRED_TRANSFORM
1525 std::vector
<Node
> pfChildren
;
1526 pfChildren
.push_back(lemma
);
1527 pfChildren
.push_back(tplemma
.getProven());
1528 std::vector
<Node
> pfArgs
;
1529 pfArgs
.push_back(lemmap
);
1530 d_lazyProof
->addStep(
1531 lemmap
, PfRule::MACRO_SR_PRED_TRANSFORM
, pfChildren
, pfArgs
);
1534 tlemma
= TrustNode::mkTrustLemma(lemmap
, d_lazyProof
.get());
1538 // must use an assertion pipeline due to decision engine below
1539 AssertionPipeline lemmas
;
1540 // make the assertion pipeline
1541 lemmas
.push_back(lemmap
);
1542 lemmas
.updateRealAssertionsEnd();
1543 Assert(newSkolems
.size() == newLemmas
.size());
1544 for (size_t i
= 0, nsize
= newLemmas
.size(); i
< nsize
; i
++)
1546 // store skolem mapping here
1547 IteSkolemMap
& imap
= lemmas
.getIteSkolemMap();
1548 imap
[newSkolems
[i
]] = lemmas
.size();
1549 lemmas
.push_back(newLemmas
[i
].getNode());
1552 // If specified, we must add this lemma to the set of those that need to be
1553 // justified, where note we pass all auxiliary lemmas in lemmas, since these
1554 // by extension must be justified as well.
1555 if (d_relManager
!= nullptr && isLemmaPropertyNeedsJustify(p
))
1557 d_relManager
->notifyPreprocessedAssertions(lemmas
.ref());
1560 // do final checks on the lemmas we are about to send
1561 if (isProofEnabled())
1563 Assert(tlemma
.getGenerator() != nullptr);
1564 // ensure closed, make the proof node eagerly here to debug
1565 tlemma
.debugCheckClosed("te-proof-debug", "TheoryEngine::lemma");
1566 for (size_t i
= 0, lsize
= newLemmas
.size(); i
< lsize
; ++i
)
1568 Assert(newLemmas
[i
].getGenerator() != nullptr);
1569 newLemmas
[i
].debugCheckClosed("te-proof-debug",
1570 "TheoryEngine::lemma_new");
1574 // now, send the lemmas to the prop engine
1575 d_propEngine
->assertLemma(tlemma
.getProven(), false, removable
);
1576 for (size_t i
= 0, lsize
= newLemmas
.size(); i
< lsize
; ++i
)
1578 d_propEngine
->assertLemma(newLemmas
[i
].getProven(), false, removable
);
1581 // assert to decision engine
1584 d_propEngine
->addAssertionsToDecisionEngine(lemmas
);
1587 // Mark that we added some lemmas
1588 d_lemmasAdded
= true;
1590 // Lemma analysis isn't online yet; this lemma may only live for this
1592 Node retLemma
= lemmas
[0];
1593 if (lemmas
.size() > 1)
1595 // the returned lemma is the conjunction of all additional lemmas.
1596 retLemma
= NodeManager::currentNM()->mkNode(kind::AND
, lemmas
.ref());
1598 return theory::LemmaStatus(retLemma
, d_userContext
->getLevel());
1601 void TheoryEngine::conflict(theory::TrustNode tconflict
, TheoryId theoryId
)
1603 Assert(tconflict
.getKind() == TrustNodeKind::CONFLICT
);
1604 TNode conflict
= tconflict
.getNode();
1605 Trace("theory::conflict") << "TheoryEngine::conflict(" << conflict
<< ", "
1606 << theoryId
<< ")" << endl
;
1607 Trace("te-proof-debug") << "Check closed conflict" << std::endl
;
1608 // doesn't require proof generator, yet, since THEORY_LEMMA is added below
1609 tconflict
.debugCheckClosed(
1610 "te-proof-debug", "TheoryEngine::conflict_initial", false);
1612 Trace("dtview::conflict") << ":THEORY-CONFLICT: " << conflict
<< std::endl
;
1614 // Mark that we are in conflict
1615 d_inConflict
= true;
1617 if(Dump
.isOn("t-conflicts")) {
1618 Dump("t-conflicts") << CommentCommand("theory conflict: expect unsat")
1619 << CheckSatCommand(conflict
.toExpr());
1622 // In the multiple-theories case, we need to reconstruct the conflict
1623 if (d_logicInfo
.isSharingEnabled()) {
1624 // Create the workplace for explanations
1625 std::vector
<NodeTheoryPair
> vec
;
1627 NodeTheoryPair(conflict
, theoryId
, d_propagationMapTimestamp
));
1629 // Process the explanation
1630 TrustNode tncExp
= getExplanation(vec
);
1631 Trace("te-proof-debug")
1632 << "Check closed conflict explained with sharing" << std::endl
;
1633 tncExp
.debugCheckClosed("te-proof-debug",
1634 "TheoryEngine::conflict_explained_sharing");
1635 Node fullConflict
= tncExp
.getNode();
1637 if (isProofEnabled())
1639 Trace("te-proof-debug") << "Process conflict: " << conflict
<< std::endl
;
1640 Trace("te-proof-debug") << "Conflict " << tconflict
<< " from "
1641 << tconflict
.identifyGenerator() << std::endl
;
1642 Trace("te-proof-debug") << "Explanation " << tncExp
<< " from "
1643 << tncExp
.identifyGenerator() << std::endl
;
1644 Assert(d_lazyProof
!= nullptr);
1645 if (tconflict
.getGenerator() != nullptr)
1647 d_lazyProof
->addLazyStep(tconflict
.getProven(),
1648 tconflict
.getGenerator());
1652 // add theory lemma step
1653 Node tidn
= builtin::BuiltinProofRuleChecker::mkTheoryIdNode(theoryId
);
1654 Node conf
= tconflict
.getProven();
1655 d_lazyProof
->addStep(conf
, PfRule::THEORY_LEMMA
, {}, {conf
, tidn
});
1657 // store the explicit step, which should come from a different
1658 // generator, e.g. d_tepg.
1659 Node proven
= tncExp
.getProven();
1660 Assert(tncExp
.getGenerator() != d_lazyProof
.get());
1661 Trace("te-proof-debug") << "add lazy step " << tncExp
.identifyGenerator()
1662 << " for " << proven
<< std::endl
;
1663 d_lazyProof
->addLazyStep(proven
, tncExp
.getGenerator());
1664 pfgEnsureClosed(proven
,
1667 "TheoryEngine::conflict_during");
1668 Node fullConflictNeg
= fullConflict
.notNode();
1669 std::vector
<Node
> children
;
1670 children
.push_back(proven
);
1671 std::vector
<Node
> args
;
1672 args
.push_back(fullConflictNeg
);
1673 if (conflict
== d_false
)
1675 AlwaysAssert(proven
== fullConflictNeg
);
1679 if (fullConflict
!= conflict
)
1681 // ------------------------- explained ---------- from theory
1682 // fullConflict => conflict ~conflict
1683 // --------------------------------------------
1684 // MACRO_SR_PRED_TRANSFORM ~fullConflict
1685 children
.push_back(conflict
.notNode());
1686 args
.push_back(mkMethodId(MethodId::SB_LITERAL
));
1687 d_lazyProof
->addStep(
1688 fullConflictNeg
, PfRule::MACRO_SR_PRED_TRANSFORM
, children
, args
);
1692 // pass the processed trust node
1694 TrustNode::mkTrustConflict(fullConflict
, d_lazyProof
.get());
1695 Debug("theory::conflict") << "TheoryEngine::conflict(" << conflict
<< ", " << theoryId
<< "): full = " << fullConflict
<< endl
;
1696 Assert(properConflict(fullConflict
));
1697 Trace("te-proof-debug")
1698 << "Check closed conflict with sharing" << std::endl
;
1699 tconf
.debugCheckClosed("te-proof-debug", "TheoryEngine::conflict:sharing");
1700 lemma(tconf
, LemmaProperty::REMOVABLE
);
1702 // When only one theory, the conflict should need no processing
1703 Assert(properConflict(conflict
));
1704 // pass the trust node that was sent from the theory
1705 lemma(tconflict
, LemmaProperty::REMOVABLE
, THEORY_LAST
, theoryId
);
1709 theory::TrustNode
TheoryEngine::getExplanation(
1710 std::vector
<NodeTheoryPair
>& explanationVector
)
1712 Assert(explanationVector
.size() > 0);
1714 unsigned i
= 0; // Index of the current literal we are processing
1715 unsigned j
= 0; // Index of the last literal we are keeping
1717 // cache of nodes we have already explained by some theory
1718 std::unordered_map
<Node
, size_t, NodeHashFunction
> cache
;
1720 while (i
< explanationVector
.size()) {
1721 // Get the current literal to explain
1722 NodeTheoryPair toExplain
= explanationVector
[i
];
1724 Debug("theory::explain")
1725 << "[i=" << i
<< "] TheoryEngine::explain(): processing ["
1726 << toExplain
.d_timestamp
<< "] " << toExplain
.d_node
<< " sent from "
1727 << toExplain
.d_theory
<< endl
;
1729 if (cache
.find(toExplain
.d_node
) != cache
.end()
1730 && cache
[toExplain
.d_node
] < toExplain
.d_timestamp
)
1735 cache
[toExplain
.d_node
] = toExplain
.d_timestamp
;
1737 // If a true constant or a negation of a false constant we can ignore it
1738 if (toExplain
.d_node
.isConst() && toExplain
.d_node
.getConst
<bool>())
1743 if (toExplain
.d_node
.getKind() == kind::NOT
&& toExplain
.d_node
[0].isConst()
1744 && !toExplain
.d_node
[0].getConst
<bool>())
1750 // If from the SAT solver, keep it
1751 if (toExplain
.d_theory
== THEORY_SAT_SOLVER
)
1753 Debug("theory::explain") << "\tLiteral came from THEORY_SAT_SOLVER. Kepping it." << endl
;
1754 explanationVector
[j
++] = explanationVector
[i
++];
1758 // If an and, expand it
1759 if (toExplain
.d_node
.getKind() == kind::AND
)
1761 Debug("theory::explain")
1762 << "TheoryEngine::explain(): expanding " << toExplain
.d_node
1763 << " got from " << toExplain
.d_theory
<< endl
;
1764 for (unsigned k
= 0; k
< toExplain
.d_node
.getNumChildren(); ++k
)
1766 NodeTheoryPair
newExplain(
1767 toExplain
.d_node
[k
], toExplain
.d_theory
, toExplain
.d_timestamp
);
1768 explanationVector
.push_back(newExplain
);
1774 // See if it was sent to the theory by another theory
1775 PropagationMap::const_iterator find
= d_propagationMap
.find(toExplain
);
1776 if (find
!= d_propagationMap
.end()) {
1777 Debug("theory::explain")
1778 << "\tTerm was propagated by another theory (theory = "
1779 << getTheoryString((*find
).second
.d_theory
) << ")" << std::endl
;
1780 // There is some propagation, check if its a timely one
1781 if ((*find
).second
.d_timestamp
< toExplain
.d_timestamp
)
1783 Debug("theory::explain")
1784 << "\tRelevant timetsamp, pushing " << (*find
).second
.d_node
1785 << "to index = " << explanationVector
.size() << std::endl
;
1786 explanationVector
.push_back((*find
).second
);
1794 if (toExplain
.d_theory
== THEORY_BUILTIN
)
1796 explanation
= d_sharedTerms
.explain(toExplain
.d_node
);
1797 Debug("theory::explain") << "\tTerm was propagated by THEORY_BUILTIN. Explanation: " << explanation
<< std::endl
;
1801 TrustNode texp
= theoryOf(toExplain
.d_theory
)->explain(toExplain
.d_node
);
1802 explanation
= texp
.getNode();
1803 Debug("theory::explain") << "\tTerm was propagated by owner theory: "
1804 << theoryOf(toExplain
.d_theory
)->getId()
1805 << ". Explanation: " << explanation
<< std::endl
;
1808 Debug("theory::explain")
1809 << "TheoryEngine::explain(): got explanation " << explanation
1810 << " got from " << toExplain
.d_theory
<< endl
;
1811 Assert(explanation
!= toExplain
.d_node
)
1812 << "wasn't sent to you, so why are you explaining it trivially";
1813 // Mark the explanation
1814 NodeTheoryPair
newExplain(
1815 explanation
, toExplain
.d_theory
, toExplain
.d_timestamp
);
1816 explanationVector
.push_back(newExplain
);
1821 // Keep only the relevant literals
1822 explanationVector
.resize(j
);
1824 Node expNode
= mkExplanation(explanationVector
);
1825 return theory::TrustNode::mkTrustLemma(expNode
, nullptr);
1828 bool TheoryEngine::isProofEnabled() const { return d_pnm
!= nullptr; }
1830 void TheoryEngine::setUserAttribute(const std::string
& attr
,
1832 const std::vector
<Node
>& node_values
,
1833 const std::string
& str_value
)
1835 Trace("te-attr") << "set user attribute " << attr
<< " " << n
<< endl
;
1836 if( d_attr_handle
.find( attr
)!=d_attr_handle
.end() ){
1837 for( size_t i
=0; i
<d_attr_handle
[attr
].size(); i
++ ){
1838 d_attr_handle
[attr
][i
]->setUserAttribute(attr
, n
, node_values
, str_value
);
1841 //unhandled exception?
1845 void TheoryEngine::handleUserAttribute(const char* attr
, Theory
* t
) {
1846 Trace("te-attr") << "Handle user attribute " << attr
<< " " << t
<< endl
;
1847 std::string
str( attr
);
1848 d_attr_handle
[ str
].push_back( t
);
1851 void TheoryEngine::checkTheoryAssertionsWithModel(bool hardFailure
) {
1852 for(TheoryId theoryId
= THEORY_FIRST
; theoryId
< THEORY_LAST
; ++theoryId
) {
1853 Theory
* theory
= d_theoryTable
[theoryId
];
1854 if(theory
&& d_logicInfo
.isTheoryEnabled(theoryId
)) {
1855 for(context::CDList
<Assertion
>::const_iterator it
= theory
->facts_begin(),
1856 it_end
= theory
->facts_end();
1859 Node assertion
= (*it
).d_assertion
;
1860 if (!isRelevant(assertion
))
1862 // not relevant, skip
1865 Node val
= d_tc
->getModel()->getValue(assertion
);
1868 std::stringstream ss
;
1869 ss
<< " " << theoryId
1870 << " has an asserted fact that the model doesn't satisfy." << endl
1871 << "The fact: " << assertion
<< endl
1872 << "Model value: " << val
<< endl
;
1877 // Always an error if it is false
1878 InternalError() << ss
.str();
1882 // Otherwise just a warning. Notice this case may happen for
1883 // assertions with unevaluable operators, e.g. transcendental
1884 // functions. It also may happen for separation logic, where
1885 // check-model support is limited.
1886 Warning() << ss
.str();
1895 std::pair
<bool, Node
> TheoryEngine::entailmentCheck(options::TheoryOfMode mode
,
1898 TNode atom
= (lit
.getKind() == kind::NOT
) ? lit
[0] : lit
;
1899 if( atom
.getKind()==kind::AND
|| atom
.getKind()==kind::OR
|| atom
.getKind()==kind::IMPLIES
){
1900 //Boolean connective, recurse
1901 std::vector
< Node
> children
;
1902 bool pol
= (lit
.getKind()!=kind::NOT
);
1903 bool is_conjunction
= pol
==(lit
.getKind()==kind::AND
);
1904 for( unsigned i
=0; i
<atom
.getNumChildren(); i
++ ){
1906 if( pol
==( lit
.getKind()==kind::IMPLIES
&& i
==0 ) ){
1907 ch
= atom
[i
].negate();
1909 std::pair
<bool, Node
> chres
= entailmentCheck(mode
, ch
);
1911 if( !is_conjunction
){
1914 children
.push_back( chres
.second
);
1916 }else if( !chres
.first
&& is_conjunction
){
1917 return std::pair
<bool, Node
>(false, Node::null());
1920 if( is_conjunction
){
1921 return std::pair
<bool, Node
>(true, NodeManager::currentNM()->mkNode(kind::AND
, children
));
1923 return std::pair
<bool, Node
>(false, Node::null());
1925 }else if( atom
.getKind()==kind::ITE
|| ( atom
.getKind()==kind::EQUAL
&& atom
[0].getType().isBoolean() ) ){
1926 bool pol
= (lit
.getKind()!=kind::NOT
);
1927 for( unsigned r
=0; r
<2; r
++ ){
1932 std::pair
<bool, Node
> chres
= entailmentCheck(mode
, ch
);
1934 Node ch2
= atom
[ atom
.getKind()==kind::ITE
? r
+1 : 1 ];
1935 if( pol
==( atom
.getKind()==kind::ITE
? true : r
==1 ) ){
1938 std::pair
<bool, Node
> chres2
= entailmentCheck(mode
, ch2
);
1940 return std::pair
<bool, Node
>(true, NodeManager::currentNM()->mkNode(kind::AND
, chres
.second
, chres2
.second
));
1946 return std::pair
<bool, Node
>(false, Node::null());
1948 //it is a theory atom
1949 theory::TheoryId tid
= theory::Theory::theoryOf(mode
, atom
);
1950 theory::Theory
* th
= theoryOf(tid
);
1953 Trace("theory-engine-entc") << "Entailment check : " << lit
<< std::endl
;
1955 std::pair
<bool, Node
> chres
= th
->entailmentCheck(lit
);
1960 void TheoryEngine::spendResource(ResourceManager::Resource r
)
1962 d_resourceManager
->spendResource(r
);
1965 }/* CVC4 namespace */