1 /********************* */
2 /*! \file smt_engine.cpp
4 ** Original author: Morgan Deters
5 ** Major contributors: Clark Barrett
6 ** Minor contributors (to current version): Christopher L. Conway, Tianyi Liang, Martin Brain <>, Kshitij Bansal, Liana Hadarean, Dejan Jovanovic, Tim King, Andrew Reynolds
7 ** This file is part of the CVC4 project.
8 ** Copyright (c) 2009-2014 New York University and The University of Iowa
9 ** See the file COPYING in the top-level source directory for licensing
10 ** information.\endverbatim
12 ** \brief The main entry point into the CVC4 library's SMT interface
14 ** The main entry point into the CVC4 library's SMT interface.
17 #include "smt/smt_engine.h"
21 #include <ext/hash_map>
29 #include "base/exception.h"
30 #include "base/listener.h"
31 #include "base/modal_exception.h"
32 #include "base/output.h"
33 #include "context/cdhashset.h"
34 #include "context/cdlist.h"
35 #include "context/context.h"
36 #include "decision/decision_engine.h"
37 #include "expr/attribute.h"
38 #include "expr/expr.h"
39 #include "expr/kind.h"
40 #include "expr/metakind.h"
41 #include "expr/node.h"
42 #include "expr/node_builder.h"
43 #include "expr/node_self_iterator.h"
44 #include "options/arith_options.h"
45 #include "options/arrays_options.h"
46 #include "options/base_options.h"
47 #include "options/boolean_term_conversion_mode.h"
48 #include "options/booleans_options.h"
49 #include "options/booleans_options.h"
50 #include "options/bv_options.h"
51 #include "options/datatypes_options.h"
52 #include "options/decision_mode.h"
53 #include "options/decision_options.h"
54 #include "options/main_options.h"
55 #include "options/option_exception.h"
56 #include "options/options_handler_interface.h"
57 #include "options/printer_options.h"
58 #include "options/prop_options.h"
59 #include "options/quantifiers_options.h"
60 #include "options/set_language.h"
61 #include "options/smt_options.h"
62 #include "options/strings_options.h"
63 #include "options/theory_options.h"
64 #include "options/uf_options.h"
65 #include "printer/printer.h"
66 #include "proof/proof.h"
67 #include "proof/proof_manager.h"
68 #include "proof/proof_manager.h"
69 #include "proof/theory_proof.h"
70 #include "proof/unsat_core.h"
71 #include "prop/prop_engine.h"
72 #include "smt/boolean_terms.h"
73 #include "smt/command_list.h"
74 #include "smt/logic_request.h"
75 #include "smt/model_postprocessor.h"
76 #include "smt/smt_engine_scope.h"
77 #include "smt/smt_options_handler.h"
78 #include "smt_util/boolean_simplification.h"
79 #include "smt_util/command.h"
80 #include "smt_util/ite_removal.h"
81 #include "smt_util/nary_builder.h"
82 #include "smt_util/node_visitor.h"
83 #include "theory/arith/pseudoboolean_proc.h"
84 #include "theory/booleans/circuit_propagator.h"
85 #include "theory/bv/bvintropow2.h"
86 #include "theory/bv/theory_bv_rewriter.h"
87 #include "theory/logic_info.h"
88 #include "theory/quantifiers/ce_guided_instantiation.h"
89 #include "theory/quantifiers/fun_def_process.h"
90 #include "theory/quantifiers/macros.h"
91 #include "theory/quantifiers/quantifiers_rewriter.h"
92 #include "theory/sort_inference.h"
93 #include "theory/strings/theory_strings.h"
94 #include "theory/substitutions.h"
95 #include "theory/theory_engine.h"
96 #include "theory/theory_model.h"
97 #include "theory/theory_traits.h"
98 #include "util/configuration.h"
99 #include "util/configuration_private.h"
100 #include "util/hash.h"
101 #include "util/proof.h"
102 #include "util/resource_manager.h"
105 using namespace CVC4
;
106 using namespace CVC4::smt
;
107 using namespace CVC4::prop
;
108 using namespace CVC4::context
;
109 using namespace CVC4::theory
;
115 /** Useful for counting the number of recursive calls. */
120 ScopeCounter(unsigned& d
) : d_depth(d
) {
129 * Representation of a defined function. We keep these around in
130 * SmtEngine to permit expanding definitions late (and lazily), to
131 * support getValue() over defined functions, to support user output
132 * in terms of defined functions, etc.
134 class DefinedFunction
{
136 vector
<Node
> d_formals
;
140 DefinedFunction(Node func
, vector
<Node
> formals
, Node formula
) :
145 Node
getFunction() const { return d_func
; }
146 vector
<Node
> getFormals() const { return d_formals
; }
147 Node
getFormula() const { return d_formula
; }
148 };/* class DefinedFunction */
150 class AssertionPipeline
{
151 vector
<Node
> d_nodes
;
155 size_t size() const { return d_nodes
.size(); }
157 void resize(size_t n
) { d_nodes
.resize(n
); }
158 void clear() { d_nodes
.clear(); }
160 Node
& operator[](size_t i
) { return d_nodes
[i
]; }
161 const Node
& operator[](size_t i
) const { return d_nodes
[i
]; }
162 void push_back(Node n
) { d_nodes
.push_back(n
); }
164 vector
<Node
>& ref() { return d_nodes
; }
165 const vector
<Node
>& ref() const { return d_nodes
; }
167 void replace(size_t i
, Node n
) {
168 PROOF( ProofManager::currentPM()->addDependence(n
, d_nodes
[i
]); );
171 };/* class AssertionPipeline */
173 struct SmtEngineStatistics
{
174 /** time spent in definition-expansion */
175 TimerStat d_definitionExpansionTime
;
176 /** time spent in Boolean term rewriting */
177 TimerStat d_rewriteBooleanTermsTime
;
178 /** time spent in non-clausal simplification */
179 TimerStat d_nonclausalSimplificationTime
;
180 /** time spent in miplib pass */
181 TimerStat d_miplibPassTime
;
182 /** number of assertions removed by miplib pass */
183 IntStat d_numMiplibAssertionsRemoved
;
184 /** number of constant propagations found during nonclausal simp */
185 IntStat d_numConstantProps
;
186 /** time spent in static learning */
187 TimerStat d_staticLearningTime
;
188 /** time spent in simplifying ITEs */
189 TimerStat d_simpITETime
;
190 /** time spent in simplifying ITEs */
191 TimerStat d_unconstrainedSimpTime
;
192 /** time spent removing ITEs */
193 TimerStat d_iteRemovalTime
;
194 /** time spent in theory preprocessing */
195 TimerStat d_theoryPreprocessTime
;
196 /** time spent in theory preprocessing */
197 TimerStat d_rewriteApplyToConstTime
;
198 /** time spent converting to CNF */
199 TimerStat d_cnfConversionTime
;
200 /** Num of assertions before ite removal */
201 IntStat d_numAssertionsPre
;
202 /** Num of assertions after ite removal */
203 IntStat d_numAssertionsPost
;
204 /** time spent in checkModel() */
205 TimerStat d_checkModelTime
;
206 /** time spent in checkProof() */
207 TimerStat d_checkProofTime
;
208 /** time spent in checkUnsatCore() */
209 TimerStat d_checkUnsatCoreTime
;
210 /** time spent in PropEngine::checkSat() */
211 TimerStat d_solveTime
;
212 /** time spent in pushing/popping */
213 TimerStat d_pushPopTime
;
214 /** time spent in processAssertions() */
215 TimerStat d_processAssertionsTime
;
217 /** Has something simplified to false? */
218 IntStat d_simplifiedToFalse
;
219 /** Number of resource units spent. */
220 ReferenceStat
<uint64_t> d_resourceUnitsUsed
;
222 SmtEngineStatistics() :
223 d_definitionExpansionTime("smt::SmtEngine::definitionExpansionTime"),
224 d_rewriteBooleanTermsTime("smt::SmtEngine::rewriteBooleanTermsTime"),
225 d_nonclausalSimplificationTime("smt::SmtEngine::nonclausalSimplificationTime"),
226 d_miplibPassTime("smt::SmtEngine::miplibPassTime"),
227 d_numMiplibAssertionsRemoved("smt::SmtEngine::numMiplibAssertionsRemoved", 0),
228 d_numConstantProps("smt::SmtEngine::numConstantProps", 0),
229 d_staticLearningTime("smt::SmtEngine::staticLearningTime"),
230 d_simpITETime("smt::SmtEngine::simpITETime"),
231 d_unconstrainedSimpTime("smt::SmtEngine::unconstrainedSimpTime"),
232 d_iteRemovalTime("smt::SmtEngine::iteRemovalTime"),
233 d_theoryPreprocessTime("smt::SmtEngine::theoryPreprocessTime"),
234 d_rewriteApplyToConstTime("smt::SmtEngine::rewriteApplyToConstTime"),
235 d_cnfConversionTime("smt::SmtEngine::cnfConversionTime"),
236 d_numAssertionsPre("smt::SmtEngine::numAssertionsPreITERemoval", 0),
237 d_numAssertionsPost("smt::SmtEngine::numAssertionsPostITERemoval", 0),
238 d_checkModelTime("smt::SmtEngine::checkModelTime"),
239 d_checkProofTime("smt::SmtEngine::checkProofTime"),
240 d_checkUnsatCoreTime("smt::SmtEngine::checkUnsatCoreTime"),
241 d_solveTime("smt::SmtEngine::solveTime"),
242 d_pushPopTime("smt::SmtEngine::pushPopTime"),
243 d_processAssertionsTime("smt::SmtEngine::processAssertionsTime"),
244 d_simplifiedToFalse("smt::SmtEngine::simplifiedToFalse", 0),
245 d_resourceUnitsUsed("smt::SmtEngine::resourceUnitsUsed")
248 smtStatisticsRegistry()->registerStat(&d_definitionExpansionTime
);
249 smtStatisticsRegistry()->registerStat(&d_rewriteBooleanTermsTime
);
250 smtStatisticsRegistry()->registerStat(&d_nonclausalSimplificationTime
);
251 smtStatisticsRegistry()->registerStat(&d_miplibPassTime
);
252 smtStatisticsRegistry()->registerStat(&d_numMiplibAssertionsRemoved
);
253 smtStatisticsRegistry()->registerStat(&d_numConstantProps
);
254 smtStatisticsRegistry()->registerStat(&d_staticLearningTime
);
255 smtStatisticsRegistry()->registerStat(&d_simpITETime
);
256 smtStatisticsRegistry()->registerStat(&d_unconstrainedSimpTime
);
257 smtStatisticsRegistry()->registerStat(&d_iteRemovalTime
);
258 smtStatisticsRegistry()->registerStat(&d_theoryPreprocessTime
);
259 smtStatisticsRegistry()->registerStat(&d_rewriteApplyToConstTime
);
260 smtStatisticsRegistry()->registerStat(&d_cnfConversionTime
);
261 smtStatisticsRegistry()->registerStat(&d_numAssertionsPre
);
262 smtStatisticsRegistry()->registerStat(&d_numAssertionsPost
);
263 smtStatisticsRegistry()->registerStat(&d_checkModelTime
);
264 smtStatisticsRegistry()->registerStat(&d_checkProofTime
);
265 smtStatisticsRegistry()->registerStat(&d_checkUnsatCoreTime
);
266 smtStatisticsRegistry()->registerStat(&d_solveTime
);
267 smtStatisticsRegistry()->registerStat(&d_pushPopTime
);
268 smtStatisticsRegistry()->registerStat(&d_processAssertionsTime
);
269 smtStatisticsRegistry()->registerStat(&d_simplifiedToFalse
);
270 smtStatisticsRegistry()->registerStat(&d_resourceUnitsUsed
);
273 ~SmtEngineStatistics() {
274 smtStatisticsRegistry()->unregisterStat(&d_definitionExpansionTime
);
275 smtStatisticsRegistry()->unregisterStat(&d_rewriteBooleanTermsTime
);
276 smtStatisticsRegistry()->unregisterStat(&d_nonclausalSimplificationTime
);
277 smtStatisticsRegistry()->unregisterStat(&d_miplibPassTime
);
278 smtStatisticsRegistry()->unregisterStat(&d_numMiplibAssertionsRemoved
);
279 smtStatisticsRegistry()->unregisterStat(&d_numConstantProps
);
280 smtStatisticsRegistry()->unregisterStat(&d_staticLearningTime
);
281 smtStatisticsRegistry()->unregisterStat(&d_simpITETime
);
282 smtStatisticsRegistry()->unregisterStat(&d_unconstrainedSimpTime
);
283 smtStatisticsRegistry()->unregisterStat(&d_iteRemovalTime
);
284 smtStatisticsRegistry()->unregisterStat(&d_theoryPreprocessTime
);
285 smtStatisticsRegistry()->unregisterStat(&d_rewriteApplyToConstTime
);
286 smtStatisticsRegistry()->unregisterStat(&d_cnfConversionTime
);
287 smtStatisticsRegistry()->unregisterStat(&d_numAssertionsPre
);
288 smtStatisticsRegistry()->unregisterStat(&d_numAssertionsPost
);
289 smtStatisticsRegistry()->unregisterStat(&d_checkModelTime
);
290 smtStatisticsRegistry()->unregisterStat(&d_checkProofTime
);
291 smtStatisticsRegistry()->unregisterStat(&d_checkUnsatCoreTime
);
292 smtStatisticsRegistry()->unregisterStat(&d_solveTime
);
293 smtStatisticsRegistry()->unregisterStat(&d_pushPopTime
);
294 smtStatisticsRegistry()->unregisterStat(&d_processAssertionsTime
);
295 smtStatisticsRegistry()->unregisterStat(&d_simplifiedToFalse
);
296 smtStatisticsRegistry()->unregisterStat(&d_resourceUnitsUsed
);
298 };/* struct SmtEngineStatistics */
301 class SoftResourceOutListener
: public Listener
{
303 SoftResourceOutListener(SmtEngine
& smt
) : d_smt(&smt
) {}
304 virtual void notify() {
305 SmtScope
scope(d_smt
);
306 Assert(smt::smtEngineInScope());
311 }; /* class SoftResourceOutListener */
314 class HardResourceOutListener
: public Listener
{
316 HardResourceOutListener(SmtEngine
& smt
) : d_smt(&smt
) {}
317 virtual void notify() {
318 SmtScope
scope(d_smt
);
319 theory::Rewriter::clearCaches();
323 }; /* class HardResourceOutListener */
327 * This is an inelegant solution, but for the present, it will work.
328 * The point of this is to separate the public and private portions of
329 * the SmtEngine class, so that smt_engine.h doesn't
330 * include "expr/node.h", which is a private CVC4 header (and can lead
331 * to linking errors due to the improper inlining of non-visible symbols
334 * The "real" solution (that which is usually implemented) is to move
335 * ALL the implementation to SmtEnginePrivate and maintain a
336 * heap-allocated instance of it in SmtEngine. SmtEngine (the public
337 * one) becomes an "interface shell" which simply acts as a forwarder
340 class SmtEnginePrivate
: public NodeManagerListener
{
344 * Manager for limiting time and abstract resource usage.
346 ResourceManager
* d_resourceManager
;
349 * Listener for the when a soft resource out occurs.
351 RegisterListener
* d_softResourceOutListener
;
354 * Listener for the when a hard resource out occurs.
356 RegisterListener
* d_hardResourceOutListener
;
358 /** Learned literals */
359 vector
<Node
> d_nonClausalLearnedLiterals
;
361 /** Size of assertions array when preprocessing starts */
362 unsigned d_realAssertionsEnd
;
364 /** The converter for Boolean terms -> BITVECTOR(1). */
365 BooleanTermConverter
* d_booleanTermConverter
;
367 /** A circuit propagator for non-clausal propositional deduction */
368 booleans::CircuitPropagator d_propagator
;
369 bool d_propagatorNeedsFinish
;
370 std::vector
<Node
> d_boolVars
;
372 /** Assertions in the preprocessing pipeline */
373 AssertionPipeline d_assertions
;
375 /** Whether any assertions have been processed */
376 CDO
<bool> d_assertionsProcessed
;
378 /** Index for where to store substitutions */
379 CDO
<unsigned> d_substitutionsIndex
;
385 * A context that never pushes/pops, for use by CD structures (like
386 * SubstitutionMaps) that should be "global".
388 context::Context d_fakeContext
;
391 * A map of AbsractValues to their actual constants. Only used if
392 * options::abstractValues() is on.
394 SubstitutionMap d_abstractValueMap
;
397 * A mapping of all abstract values (actual value |-> abstract) that
398 * we've handed out. This is necessary to ensure that we give the
399 * same AbstractValues for the same real constants. Only used if
400 * options::abstractValues() is on.
402 hash_map
<Node
, Node
, NodeHashFunction
> d_abstractValues
;
404 /** Number of calls of simplify assertions active.
406 unsigned d_simplifyAssertionsDepth
;
410 * Map from skolem variables to index in d_assertions containing
411 * corresponding introduced Boolean ite
413 IteSkolemMap d_iteSkolemMap
;
415 /** Instance of the ITE remover */
416 RemoveITE d_iteRemover
;
420 theory::arith::PseudoBooleanProcessor d_pbsProcessor
;
422 /** The top level substitutions */
423 SubstitutionMap d_topLevelSubstitutions
;
425 static const bool d_doConstantProp
= true;
428 * Runs the nonclausal solver and tries to solve all the assigned
431 * Returns false if the formula simplifies to "false"
433 bool nonClausalSimplify();
436 * Performs static learning on the assertions.
438 void staticLearning();
441 * Remove ITEs from the assertions.
445 Node
intToBV(TNode n
, std::hash_map
<Node
, Node
, NodeHashFunction
>& cache
);
446 Node
intToBVMakeBinary(TNode n
, std::hash_map
<Node
, Node
, NodeHashFunction
>& cache
);
449 * Helper function to fix up assertion list to restore invariants needed after ite removal
451 void collectSkolems(TNode n
, set
<TNode
>& skolemSet
, hash_map
<Node
, bool, NodeHashFunction
>& cache
);
454 * Helper function to fix up assertion list to restore invariants needed after ite removal
456 bool checkForBadSkolems(TNode n
, TNode skolem
, hash_map
<Node
, bool, NodeHashFunction
>& cache
);
458 // Lift bit-vectors of size 1 to booleans
461 // Abstract common structure over small domains to UF
462 // return true if changes were made.
463 void bvAbstraction();
465 // Simplify ITE structure
468 // Simplify based on unconstrained values
469 void unconstrainedSimp();
471 // Ensures the assertions asserted after before now
472 // effectively come before d_realAssertionsEnd
473 void compressBeforeRealAssertions(size_t before
);
476 * Any variable in an assertion that is declared as a subtype type
477 * (predicate subtype or integer subrange type) must be constrained
478 * to be in that type.
480 void constrainSubtypes(TNode n
, AssertionPipeline
& assertions
)
483 // trace nodes back to their assertions using CircuitPropagator's BackEdgesMap
484 void traceBackToAssertions(const std::vector
<Node
>& nodes
, std::vector
<TNode
>& assertions
);
485 // remove conjuncts in toRemove from conjunction n; return # of removed conjuncts
486 size_t removeFromConjunction(Node
& n
, const std::hash_set
<unsigned long>& toRemove
);
488 // scrub miplib encodings
489 void doMiplibTrick();
492 * Perform non-clausal simplification of a Node. This involves
493 * Theory implementations, but does NOT involve the SAT solver in
496 * Returns false if the formula simplifies to "false"
498 bool simplifyAssertions() throw(TypeCheckingException
, LogicException
, UnsafeInterruptException
);
502 SmtEnginePrivate(SmtEngine
& smt
) :
504 d_resourceManager(NULL
),
505 d_softResourceOutListener(NULL
),
506 d_hardResourceOutListener(NULL
),
507 d_nonClausalLearnedLiterals(),
508 d_realAssertionsEnd(0),
509 d_booleanTermConverter(NULL
),
510 d_propagator(d_nonClausalLearnedLiterals
, true, true),
511 d_propagatorNeedsFinish(false),
513 d_assertionsProcessed(smt
.d_userContext
, false),
514 d_substitutionsIndex(smt
.d_userContext
, 0),
516 d_abstractValueMap(&d_fakeContext
),
518 d_simplifyAssertionsDepth(0),
520 d_iteRemover(smt
.d_userContext
),
521 d_pbsProcessor(smt
.d_userContext
),
522 d_topLevelSubstitutions(smt
.d_userContext
)
524 d_smt
.d_nodeManager
->subscribeEvents(this);
525 d_true
= NodeManager::currentNM()->mkConst(true);
526 d_resourceManager
= NodeManager::currentResourceManager();
528 d_softResourceOutListener
= new RegisterListener(
529 d_resourceManager
->getSoftListeners(),
530 new SoftResourceOutListener(d_smt
));
532 d_hardResourceOutListener
= new RegisterListener(
533 d_resourceManager
->getHardListeners(),
534 new HardResourceOutListener(d_smt
));
538 ~SmtEnginePrivate() throw() {
539 delete d_hardResourceOutListener
;
540 d_hardResourceOutListener
= NULL
;
541 delete d_softResourceOutListener
;
542 d_softResourceOutListener
= NULL
;
544 if(d_propagatorNeedsFinish
) {
545 d_propagator
.finish();
546 d_propagatorNeedsFinish
= false;
548 if(d_booleanTermConverter
!= NULL
) {
549 delete d_booleanTermConverter
;
550 d_booleanTermConverter
= NULL
;
552 d_smt
.d_nodeManager
->unsubscribeEvents(this);
555 ResourceManager
* getResourceManager() { return d_resourceManager
; }
556 void spendResource(unsigned ammount
) throw(UnsafeInterruptException
) {
557 d_resourceManager
->spendResource(ammount
);
560 void nmNotifyNewSort(TypeNode tn
, uint32_t flags
) {
561 DeclareTypeCommand
c(tn
.getAttribute(expr::VarNameAttr()),
564 if((flags
& ExprManager::SORT_FLAG_PLACEHOLDER
) == 0) {
565 d_smt
.addToModelCommandAndDump(c
, flags
);
569 void nmNotifyNewSortConstructor(TypeNode tn
) {
570 DeclareTypeCommand
c(tn
.getAttribute(expr::VarNameAttr()),
571 tn
.getAttribute(expr::SortArityAttr()),
573 d_smt
.addToModelCommandAndDump(c
);
576 void nmNotifyNewDatatypes(const std::vector
<DatatypeType
>& dtts
) {
577 DatatypeDeclarationCommand
c(dtts
);
578 d_smt
.addToModelCommandAndDump(c
);
581 void nmNotifyNewVar(TNode n
, uint32_t flags
) {
582 DeclareFunctionCommand
c(n
.getAttribute(expr::VarNameAttr()),
584 n
.getType().toType());
585 if((flags
& ExprManager::VAR_FLAG_DEFINED
) == 0) {
586 d_smt
.addToModelCommandAndDump(c
, flags
);
588 if(n
.getType().isBoolean() && !options::incrementalSolving()) {
589 d_boolVars
.push_back(n
);
593 void nmNotifyNewSkolem(TNode n
, const std::string
& comment
, uint32_t flags
) {
594 string id
= n
.getAttribute(expr::VarNameAttr());
595 DeclareFunctionCommand
c(id
,
597 n
.getType().toType());
598 if(Dump
.isOn("skolems") && comment
!= "") {
599 Dump("skolems") << CommentCommand(id
+ " is " + comment
);
601 if((flags
& ExprManager::VAR_FLAG_DEFINED
) == 0) {
602 d_smt
.addToModelCommandAndDump(c
, flags
, false, "skolems");
604 if(n
.getType().isBoolean() && !options::incrementalSolving()) {
605 d_boolVars
.push_back(n
);
609 void nmNotifyDeleteNode(TNode n
) {
610 d_smt
.d_smtAttributes
->deleteAllAttributes(n
);
613 Node
applySubstitutions(TNode node
) const {
614 return Rewriter::rewrite(d_topLevelSubstitutions
.apply(node
));
618 * Process the assertions that have been asserted.
620 void processAssertions();
623 * Process a user pop. Clears out the non-context-dependent stuff in this
624 * SmtEnginePrivate. Necessary to clear out our assertion vectors in case
625 * someone does a push-assert-pop without a check-sat.
628 d_assertions
.clear();
629 d_nonClausalLearnedLiterals
.clear();
630 d_realAssertionsEnd
= 0;
631 d_iteSkolemMap
.clear();
635 * Adds a formula to the current context. Action here depends on
636 * the SimplificationMode (in the current Options scope); the
637 * formula might be pushed out to the propositional layer
638 * immediately, or it might be simplified and kept, or it might not
639 * even be simplified.
640 * the 2nd and 3rd arguments added for bookkeeping for proofs
642 void addFormula(TNode n
, bool inUnsatCore
, bool inInput
= true)
643 throw(TypeCheckingException
, LogicException
);
646 * Expand definitions in n.
648 Node
expandDefinitions(TNode n
, hash_map
<Node
, Node
, NodeHashFunction
>& cache
, bool expandOnly
= false)
649 throw(TypeCheckingException
, LogicException
, UnsafeInterruptException
);
652 * Rewrite Boolean terms in a Node.
654 Node
rewriteBooleanTerms(TNode n
);
657 * Simplify node "in" by expanding definitions and applying any
658 * substitutions learned from preprocessing.
660 Node
simplify(TNode in
) {
661 // Substitute out any abstract values in ex.
662 // Expand definitions.
663 hash_map
<Node
, Node
, NodeHashFunction
> cache
;
664 Node n
= expandDefinitions(in
, cache
).toExpr();
665 // Make sure we've done all preprocessing, etc.
666 Assert(d_assertions
.size() == 0);
667 return applySubstitutions(n
).toExpr();
671 * Substitute away all AbstractValues in a node.
673 Node
substituteAbstractValues(TNode n
) {
674 // We need to do this even if options::abstractValues() is off,
675 // since the setting might have changed after we already gave out
676 // some abstract values.
677 return d_abstractValueMap
.apply(n
);
681 * Make a new (or return an existing) abstract value for a node.
682 * Can only use this if options::abstractValues() is on.
684 Node
mkAbstractValue(TNode n
) {
685 Assert(options::abstractValues());
686 Node
& val
= d_abstractValues
[n
];
688 val
= d_smt
.d_nodeManager
->mkAbstractValue(n
.getType());
689 d_abstractValueMap
.addSubstitution(val
, n
);
691 // We are supposed to ascribe types to all abstract values that go out.
692 Node retval
= d_smt
.d_nodeManager
->mkNode(kind::APPLY_TYPE_ASCRIPTION
, d_smt
.d_nodeManager
->mkConst(AscriptionType(n
.getType().toType())), val
);
696 std::hash_map
<Node
, Node
, NodeHashFunction
> rewriteApplyToConstCache
;
697 Node
rewriteApplyToConst(TNode n
) {
698 Trace("rewriteApplyToConst") << "rewriteApplyToConst :: " << n
<< std::endl
;
700 if(n
.getMetaKind() == kind::metakind::CONSTANT
|| n
.getMetaKind() == kind::metakind::VARIABLE
) {
704 if(rewriteApplyToConstCache
.find(n
) != rewriteApplyToConstCache
.end()) {
705 Trace("rewriteApplyToConst") << "in cache :: " << rewriteApplyToConstCache
[n
] << std::endl
;
706 return rewriteApplyToConstCache
[n
];
708 if(n
.getKind() == kind::APPLY_UF
) {
709 if(n
.getNumChildren() == 1 && n
[0].isConst() && n
[0].getType().isInteger()) {
711 ss
<< n
.getOperator() << "_";
712 if(n
[0].getConst
<Rational
>() < 0) {
713 ss
<< "m" << -n
[0].getConst
<Rational
>();
717 Node newvar
= NodeManager::currentNM()->mkSkolem(ss
.str(), n
.getType(), "rewriteApplyToConst skolem", NodeManager::SKOLEM_EXACT_NAME
);
718 rewriteApplyToConstCache
[n
] = newvar
;
719 Trace("rewriteApplyToConst") << "made :: " << newvar
<< std::endl
;
723 ss
<< "The rewrite-apply-to-const preprocessor is currently limited;\n"
724 << "it only works if all function symbols are unary and with Integer\n"
725 << "domain, and all applications are to integer values.\n"
726 << "Found application: " << n
;
731 NodeBuilder
<> builder(n
.getKind());
732 if(n
.getMetaKind() == kind::metakind::PARAMETERIZED
) {
733 builder
<< n
.getOperator();
735 for(unsigned i
= 0; i
< n
.getNumChildren(); ++i
) {
736 builder
<< rewriteApplyToConst(n
[i
]);
739 rewriteApplyToConstCache
[n
] = rewr
;
740 Trace("rewriteApplyToConst") << "built :: " << rewr
<< std::endl
;
744 };/* class SmtEnginePrivate */
746 }/* namespace CVC4::smt */
748 SmtEngine::SmtEngine(ExprManager
* em
) throw() :
749 d_context(new Context()),
751 d_userContext(new UserContext()),
753 d_nodeManager(d_exprManager
->getNodeManager()),
754 d_decisionEngine(NULL
),
755 d_theoryEngine(NULL
),
757 d_proofManager(NULL
),
758 d_definedFunctions(NULL
),
759 d_fmfRecFunctionsAbs(NULL
),
760 d_fmfRecFunctionsConcrete(NULL
),
761 d_assertionList(NULL
),
763 d_modelGlobalCommands(),
764 d_modelCommands(NULL
),
768 d_originalOptions(em
->getOptions()),
770 d_fullyInited(false),
771 d_problemExtended(false),
773 d_needPostsolve(false),
774 d_earlyTheoryPP(true),
776 d_optionsHandler(new SmtOptionsHandler(this)),
778 d_smtAttributes(NULL
),
779 d_statisticsRegistry(NULL
),
781 d_globals(new SmtGlobals())
785 d_smtAttributes
= new expr::attr::SmtAttributes(d_context
);
786 d_private
= new smt::SmtEnginePrivate(*this);
787 d_statisticsRegistry
= new StatisticsRegistry();
788 d_stats
= new SmtEngineStatistics();
789 d_stats
->d_resourceUnitsUsed
.setData(
790 d_private
->getResourceManager()->getResourceUsage());
792 // The ProofManager is constructed before any other proof objects such as
793 // SatProof and TheoryProofs. The TheoryProofEngine and the SatProof are
794 // initialized in TheoryEngine and PropEngine respectively.
795 Assert(d_proofManager
== NULL
);
796 PROOF( d_proofManager
= new ProofManager(); );
798 // We have mutual dependency here, so we add the prop engine to the theory
799 // engine later (it is non-essential there)
800 d_theoryEngine
= new TheoryEngine(d_context
, d_userContext
,
801 d_private
->d_iteRemover
,
802 const_cast<const LogicInfo
&>(d_logic
),
806 for(TheoryId id
= theory::THEORY_FIRST
; id
< theory::THEORY_LAST
; ++id
) {
807 TheoryConstructor::addTheory(d_theoryEngine
, id
);
808 //register with proof engine if applicable
809 THEORY_PROOF(ProofManager::currentPM()->getTheoryProofEngine()->registerTheory(d_theoryEngine
->theoryOf(id
)); );
812 // global push/pop around everything, to ensure proper destruction
813 // of context-dependent data structures
814 d_userContext
->push();
817 d_definedFunctions
= new(true) DefinedFunctionMap(d_userContext
);
818 if( options::fmfFunWellDefined() || options::fmfFunWellDefinedRelevant() ){
819 d_fmfRecFunctionsAbs
= new(true) TypeNodeMap(d_userContext
);
820 d_fmfRecFunctionsConcrete
= new(true) NodeListMap(d_userContext
);
822 d_modelCommands
= new(true) smt::CommandList(d_userContext
);
825 void SmtEngine::finishInit() {
826 // ensure that our heuristics are properly set up
829 d_decisionEngine
= new DecisionEngine(d_context
, d_userContext
);
830 d_decisionEngine
->init(); // enable appropriate strategies
832 d_propEngine
= new PropEngine(d_theoryEngine
, d_decisionEngine
, d_context
,
833 d_userContext
, d_globals
);
835 d_theoryEngine
->setPropEngine(d_propEngine
);
836 d_theoryEngine
->setDecisionEngine(d_decisionEngine
);
837 d_theoryEngine
->finishInit();
839 // [MGD 10/20/2011] keep around in incremental mode, due to a
840 // cleanup ordering issue and Nodes/TNodes. If SAT is popped
841 // first, some user-context-dependent TNodes might still exist
843 if(options::produceAssertions() ||
844 options::incrementalSolving()) {
845 // In the case of incremental solving, we appear to need these to
846 // ensure the relevant Nodes remain live.
847 d_assertionList
= new(true) AssertionList(d_userContext
);
850 // dump out a set-logic command
851 if(Dump
.isOn("benchmark")) {
852 // Dump("benchmark") << SetBenchmarkLogicCommand(logic.getLogicString());
853 LogicInfo everything
;
855 Dump("benchmark") << CommentCommand("CVC4 always dumps the most general, all-supported logic (below), as some internals might require the use of a logic more general than the input.")
856 << SetBenchmarkLogicCommand(everything
.getLogicString());
859 // dump out any pending declaration commands
860 for(unsigned i
= 0; i
< d_dumpCommands
.size(); ++i
) {
861 Dump("declarations") << *d_dumpCommands
[i
];
862 delete d_dumpCommands
[i
];
864 d_dumpCommands
.clear();
866 PROOF( ProofManager::currentPM()->setLogic(d_logic
); );
869 void SmtEngine::finalOptionsAreSet() {
874 if(! d_logic
.isLocked()) {
878 // finish initialization, create the prop engine, etc.
881 AlwaysAssert( d_propEngine
->getAssertionLevel() == 0,
882 "The PropEngine has pushed but the SmtEngine "
883 "hasn't finished initializing!" );
885 d_fullyInited
= true;
886 Assert(d_logic
.isLocked());
888 d_propEngine
->assertFormula(NodeManager::currentNM()->mkConst
<bool>(true));
889 d_propEngine
->assertFormula(NodeManager::currentNM()->mkConst
<bool>(false).notNode());
892 void SmtEngine::shutdown() {
895 while(options::incrementalSolving() && d_userContext
->getLevel() > 1) {
899 // check to see if a postsolve() is pending
900 if(d_needPostsolve
) {
901 d_theoryEngine
->postsolve();
902 d_needPostsolve
= false;
905 if(d_propEngine
!= NULL
) {
906 d_propEngine
->shutdown();
908 if(d_theoryEngine
!= NULL
) {
909 d_theoryEngine
->shutdown();
911 if(d_decisionEngine
!= NULL
) {
912 d_decisionEngine
->shutdown();
916 SmtEngine::~SmtEngine() throw() {
922 // global push/pop around everything, to ensure proper destruction
923 // of context-dependent data structures
925 d_userContext
->popto(0);
927 if(d_assignments
!= NULL
) {
928 d_assignments
->deleteSelf();
931 if(d_assertionList
!= NULL
) {
932 d_assertionList
->deleteSelf();
935 for(unsigned i
= 0; i
< d_dumpCommands
.size(); ++i
) {
936 delete d_dumpCommands
[i
];
937 d_dumpCommands
[i
] = NULL
;
939 d_dumpCommands
.clear();
941 if(d_modelCommands
!= NULL
) {
942 d_modelCommands
->deleteSelf();
945 d_definedFunctions
->deleteSelf();
947 delete d_theoryEngine
;
948 d_theoryEngine
= NULL
;
951 delete d_decisionEngine
;
952 d_decisionEngine
= NULL
;
954 PROOF(delete d_proofManager
;);
955 PROOF(d_proofManager
= NULL
;);
959 delete d_statisticsRegistry
;
960 d_statisticsRegistry
= NULL
;
962 delete d_optionsHandler
;
963 d_optionsHandler
= NULL
;
968 delete d_smtAttributes
;
969 d_smtAttributes
= NULL
;
971 delete d_userContext
;
972 d_userContext
= NULL
;
979 } catch(Exception
& e
) {
980 Warning() << "CVC4 threw an exception during cleanup." << endl
985 void SmtEngine::setLogic(const LogicInfo
& logic
) throw(ModalException
) {
988 throw ModalException("Cannot set logic in SmtEngine after the engine has finished initializing");
994 void SmtEngine::setLogic(const std::string
& s
) throw(ModalException
, LogicException
) {
997 setLogic(LogicInfo(s
));
998 } catch(IllegalArgumentException
& e
) {
999 throw LogicException(e
.what());
1003 void SmtEngine::setLogic(const char* logic
) throw(ModalException
, LogicException
) {
1004 setLogic(string(logic
));
1007 LogicInfo
SmtEngine::getLogicInfo() const {
1011 void SmtEngine::setLogicInternal() throw() {
1012 Assert(!d_fullyInited
, "setting logic in SmtEngine but the engine has already finished initializing for this run");
1016 void SmtEngine::setDefaults() {
1017 if(options::forceLogic
.wasSetByUser()) {
1018 d_logic
= *(options::forceLogic());
1020 else if (options::solveIntAsBV() > 0) {
1021 d_logic
= LogicInfo("QF_BV");
1022 // } else if (d_logic.getLogicString() == "QF_UFBV" &&
1023 // options::bitblastMode() == theory::bv::BITBLAST_MODE_EAGER) {
1024 // d_logic = LogicInfo("QF_BV");
1028 /* - disabled for 1.4 release [MGD 2014.06.25]
1029 if(!d_logic.hasEverything() && d_logic.isTheoryEnabled(THEORY_STRINGS) ) {
1030 if(! options::stringExp.wasSetByUser()) {
1031 options::stringExp.set( true );
1032 Trace("smt") << "turning on strings-exp, for the theory of strings" << std::endl;
1037 if(options::stringExp()) {
1038 if( !d_logic
.isQuantified() ) {
1039 d_logic
= d_logic
.getUnlockedCopy();
1040 d_logic
.enableQuantifiers();
1042 Trace("smt") << "turning on quantifier logic, for strings-exp" << std::endl
;
1044 if(! options::finiteModelFind
.wasSetByUser()) {
1045 options::finiteModelFind
.set( true );
1046 Trace("smt") << "turning on finite-model-find, for strings-exp" << std::endl
;
1048 if(! options::fmfBoundInt
.wasSetByUser()) {
1049 if(! options::fmfBoundIntLazy
.wasSetByUser()) {
1050 options::fmfBoundIntLazy
.set( true );
1052 options::fmfBoundInt
.set( true );
1053 Trace("smt") << "turning on fmf-bound-int, for strings-exp" << std::endl
;
1056 if(! options::rewriteDivk.wasSetByUser()) {
1057 options::rewriteDivk.set( true );
1058 Trace("smt") << "turning on rewrite-divk, for strings-exp" << std::endl;
1061 if(! options::stringFMF.wasSetByUser()) {
1062 options::stringFMF.set( true );
1063 Trace("smt") << "turning on strings-fmf, for strings-exp" << std::endl;
1068 if(options::checkModels()) {
1069 if(! options::produceAssertions()) {
1070 Notice() << "SmtEngine: turning on produce-assertions to support check-models" << endl
;
1071 setOption("produce-assertions", SExpr("true"));
1075 if(options::unsatCores()) {
1076 if(options::simplificationMode() != SIMPLIFICATION_MODE_NONE
) {
1077 if(options::simplificationMode
.wasSetByUser()) {
1078 throw OptionException("simplification not supported with unsat cores");
1080 Notice() << "SmtEngine: turning off simplification to support unsat-cores" << endl
;
1081 options::simplificationMode
.set(SIMPLIFICATION_MODE_NONE
);
1084 if(options::unconstrainedSimp()) {
1085 if(options::unconstrainedSimp
.wasSetByUser()) {
1086 throw OptionException("unconstrained simplification not supported with unsat cores");
1088 Notice() << "SmtEngine: turning off unconstrained simplification to support unsat-cores" << endl
;
1089 options::unconstrainedSimp
.set(false);
1092 if(options::pbRewrites()) {
1093 if(options::pbRewrites
.wasSetByUser()) {
1094 throw OptionException("pseudoboolean rewrites not supported with unsat cores");
1096 Notice() << "SmtEngine: turning off pseudoboolean rewrites to support unsat-cores" << endl
;
1097 setOption("pb-rewrites", false);
1100 if(options::sortInference()) {
1101 if(options::sortInference
.wasSetByUser()) {
1102 throw OptionException("sort inference not supported with unsat cores");
1104 Notice() << "SmtEngine: turning off sort inference to support unsat-cores" << endl
;
1105 options::sortInference
.set(false);
1108 if(options::preSkolemQuant()) {
1109 if(options::preSkolemQuant
.wasSetByUser()) {
1110 throw OptionException("pre-skolemization not supported with unsat cores");
1112 Notice() << "SmtEngine: turning off pre-skolemization to support unsat-cores" << endl
;
1113 options::preSkolemQuant
.set(false);
1116 if(options::bitvectorToBool()) {
1117 if(options::bitvectorToBool
.wasSetByUser()) {
1118 throw OptionException("bv-to-bool not supported with unsat cores");
1120 Notice() << "SmtEngine: turning off bitvector-to-bool support unsat-cores" << endl
;
1121 options::bitvectorToBool
.set(false);
1124 if(options::bvIntroducePow2()) {
1125 if(options::bvIntroducePow2
.wasSetByUser()) {
1126 throw OptionException("bv-intro-pow2 not supported with unsat cores");
1128 Notice() << "SmtEngine: turning off bv-introduce-pow2 to support unsat-cores" << endl
;
1129 setOption("bv-intro-pow2", false);
1131 if(options::repeatSimp()) {
1132 if(options::repeatSimp
.wasSetByUser()) {
1133 throw OptionException("repeat-simp not supported with unsat cores");
1135 Notice() << "SmtEngine: turning off repeat-simp to support unsat-cores" << endl
;
1136 setOption("repeat-simp", false);
1141 if(options::produceAssignments() && !options::produceModels()) {
1142 Notice() << "SmtEngine: turning on produce-models to support produce-assignments" << endl
;
1143 setOption("produce-models", SExpr("true"));
1146 // Set the options for the theoryOf
1147 if(!options::theoryOfMode
.wasSetByUser()) {
1148 if(d_logic
.isSharingEnabled() &&
1149 !d_logic
.isTheoryEnabled(THEORY_BV
) &&
1150 !d_logic
.isTheoryEnabled(THEORY_STRINGS
) &&
1151 !d_logic
.isTheoryEnabled(THEORY_SETS
) ) {
1152 Trace("smt") << "setting theoryof-mode to term-based" << endl
;
1153 options::theoryOfMode
.set(THEORY_OF_TERM_BASED
);
1157 // strings require LIA, UF; widen the logic
1158 if(d_logic
.isTheoryEnabled(THEORY_STRINGS
)) {
1159 LogicInfo
log(d_logic
.getUnlockedCopy());
1160 // Strings requires arith for length constraints, and also UF
1161 if(!d_logic
.isTheoryEnabled(THEORY_UF
)) {
1162 Trace("smt") << "because strings are enabled, also enabling UF" << endl
;
1163 log
.enableTheory(THEORY_UF
);
1165 if(!d_logic
.isTheoryEnabled(THEORY_ARITH
) || d_logic
.isDifferenceLogic() || !d_logic
.areIntegersUsed()) {
1166 Trace("smt") << "because strings are enabled, also enabling linear integer arithmetic" << endl
;
1167 log
.enableTheory(THEORY_ARITH
);
1168 log
.enableIntegers();
1169 log
.arithOnlyLinear();
1175 // by default, symmetry breaker is on only for QF_UF
1176 if(! options::ufSymmetryBreaker
.wasSetByUser()) {
1177 bool qf_uf
= d_logic
.isPure(THEORY_UF
) && !d_logic
.isQuantified() && !options::proof();
1178 Trace("smt") << "setting uf symmetry breaker to " << qf_uf
<< endl
;
1179 options::ufSymmetryBreaker
.set(qf_uf
);
1181 // by default, nonclausal simplification is off for QF_SAT
1182 if(! options::simplificationMode
.wasSetByUser()) {
1183 bool qf_sat
= d_logic
.isPure(THEORY_BOOL
) && !d_logic
.isQuantified();
1184 Trace("smt") << "setting simplification mode to <" << d_logic
.getLogicString() << "> " << (!qf_sat
) << endl
;
1185 //simplification=none works better for SMT LIB benchmarks with quantifiers, not others
1186 //options::simplificationMode.set(qf_sat || quantifiers ? SIMPLIFICATION_MODE_NONE : SIMPLIFICATION_MODE_BATCH);
1187 options::simplificationMode
.set(qf_sat
? SIMPLIFICATION_MODE_NONE
: SIMPLIFICATION_MODE_BATCH
);
1190 // If in arrays, set the UF handler to arrays
1191 if(d_logic
.isTheoryEnabled(THEORY_ARRAY
) && ( !d_logic
.isQuantified() ||
1192 (d_logic
.isQuantified() && !d_logic
.isTheoryEnabled(THEORY_UF
)))) {
1193 Theory::setUninterpretedSortOwner(THEORY_ARRAY
);
1195 Theory::setUninterpretedSortOwner(THEORY_UF
);
1198 // Turn on ite simplification for QF_LIA and QF_AUFBV
1199 // WARNING: These checks match much more than just QF_AUFBV and
1200 // QF_LIA logics. --K [2014/10/15]
1201 if(! options::doITESimp
.wasSetByUser()) {
1202 bool qf_aufbv
= !d_logic
.isQuantified() &&
1203 d_logic
.isTheoryEnabled(THEORY_ARRAY
) &&
1204 d_logic
.isTheoryEnabled(THEORY_UF
) &&
1205 d_logic
.isTheoryEnabled(THEORY_BV
);
1206 bool qf_lia
= !d_logic
.isQuantified() &&
1207 d_logic
.isPure(THEORY_ARITH
) &&
1208 d_logic
.isLinear() &&
1209 !d_logic
.isDifferenceLogic() &&
1210 !d_logic
.areRealsUsed();
1212 bool iteSimp
= (qf_aufbv
|| qf_lia
);
1213 Trace("smt") << "setting ite simplification to " << iteSimp
<< endl
;
1214 options::doITESimp
.set(iteSimp
);
1216 if(! options::compressItes
.wasSetByUser() ){
1217 bool qf_lia
= !d_logic
.isQuantified() &&
1218 d_logic
.isPure(THEORY_ARITH
) &&
1219 d_logic
.isLinear() &&
1220 !d_logic
.isDifferenceLogic() &&
1221 !d_logic
.areRealsUsed();
1223 bool compressIte
= qf_lia
;
1224 Trace("smt") << "setting ite compression to " << compressIte
<< endl
;
1225 options::compressItes
.set(compressIte
);
1227 if(! options::simplifyWithCareEnabled
.wasSetByUser() ){
1228 bool qf_aufbv
= !d_logic
.isQuantified() &&
1229 d_logic
.isTheoryEnabled(THEORY_ARRAY
) &&
1230 d_logic
.isTheoryEnabled(THEORY_UF
) &&
1231 d_logic
.isTheoryEnabled(THEORY_BV
);
1233 bool withCare
= qf_aufbv
;
1234 Trace("smt") << "setting ite simplify with care to " << withCare
<< endl
;
1235 options::simplifyWithCareEnabled
.set(withCare
);
1237 // Turn off array eager index splitting for QF_AUFLIA
1238 if(! options::arraysEagerIndexSplitting
.wasSetByUser()) {
1239 if (not d_logic
.isQuantified() &&
1240 d_logic
.isTheoryEnabled(THEORY_ARRAY
) &&
1241 d_logic
.isTheoryEnabled(THEORY_UF
) &&
1242 d_logic
.isTheoryEnabled(THEORY_ARITH
)) {
1243 Trace("smt") << "setting array eager index splitting to false" << endl
;
1244 options::arraysEagerIndexSplitting
.set(false);
1247 // Turn on model-based arrays for QF_AX (unless models are enabled)
1248 // if(! options::arraysModelBased.wasSetByUser()) {
1249 // if (not d_logic.isQuantified() &&
1250 // d_logic.isTheoryEnabled(THEORY_ARRAY) &&
1251 // d_logic.isPure(THEORY_ARRAY) &&
1252 // !options::produceModels() &&
1253 // !options::checkModels()) {
1254 // Trace("smt") << "turning on model-based array solver" << endl;
1255 // options::arraysModelBased.set(true);
1258 // Turn on multiple-pass non-clausal simplification for QF_AUFBV
1259 if(! options::repeatSimp
.wasSetByUser()) {
1260 bool repeatSimp
= !d_logic
.isQuantified() &&
1261 (d_logic
.isTheoryEnabled(THEORY_ARRAY
) &&
1262 d_logic
.isTheoryEnabled(THEORY_UF
) &&
1263 d_logic
.isTheoryEnabled(THEORY_BV
)) &&
1264 !options::unsatCores();
1265 Trace("smt") << "setting repeat simplification to " << repeatSimp
<< endl
;
1266 options::repeatSimp
.set(repeatSimp
);
1268 // Turn on unconstrained simplification for QF_AUFBV
1269 if(!options::unconstrainedSimp
.wasSetByUser() ||
1270 options::incrementalSolving()) {
1271 // bool qf_sat = d_logic.isPure(THEORY_BOOL) && !d_logic.isQuantified();
1272 // bool uncSimp = false && !qf_sat && !options::incrementalSolving();
1273 bool uncSimp
= !options::incrementalSolving() &&
1274 !d_logic
.isQuantified() &&
1275 !options::produceModels() &&
1276 !options::produceAssignments() &&
1277 !options::checkModels() &&
1278 !options::unsatCores() &&
1279 (d_logic
.isTheoryEnabled(THEORY_ARRAY
) && d_logic
.isTheoryEnabled(THEORY_BV
));
1280 Trace("smt") << "setting unconstrained simplification to " << uncSimp
<< endl
;
1281 options::unconstrainedSimp
.set(uncSimp
);
1283 // Unconstrained simp currently does *not* support model generation
1284 if (options::unconstrainedSimp
.wasSetByUser() && options::unconstrainedSimp()) {
1285 if (options::produceModels()) {
1286 if (options::produceModels
.wasSetByUser()) {
1287 throw OptionException("Cannot use unconstrained-simp with model generation.");
1289 Notice() << "SmtEngine: turning off produce-models to support unconstrainedSimp" << endl
;
1290 setOption("produce-models", SExpr("false"));
1292 if (options::produceAssignments()) {
1293 if (options::produceAssignments
.wasSetByUser()) {
1294 throw OptionException("Cannot use unconstrained-simp with model generation (produce-assignments).");
1296 Notice() << "SmtEngine: turning off produce-assignments to support unconstrainedSimp" << endl
;
1297 setOption("produce-assignments", SExpr("false"));
1299 if (options::checkModels()) {
1300 if (options::checkModels
.wasSetByUser()) {
1301 throw OptionException("Cannot use unconstrained-simp with model generation (check-models).");
1303 Notice() << "SmtEngine: turning off check-models to support unconstrainedSimp" << endl
;
1304 setOption("check-models", SExpr("false"));
1309 if (options::bitblastMode() == theory::bv::BITBLAST_MODE_EAGER
&&
1310 options::incrementalSolving()) {
1311 if (options::incrementalSolving
.wasSetByUser()) {
1312 throw OptionException(std::string("Eager bit-blasting does not currently support incremental mode. \n\
1313 Try --bitblast=lazy"));
1315 Notice() << "SmtEngine: turning off incremental to support eager bit-blasting" << endl
;
1316 setOption("incremental", SExpr("false"));
1319 if (! options::bvEagerExplanations
.wasSetByUser() &&
1320 d_logic
.isTheoryEnabled(THEORY_ARRAY
) &&
1321 d_logic
.isTheoryEnabled(THEORY_BV
)) {
1322 Trace("smt") << "enabling eager bit-vector explanations " << endl
;
1323 options::bvEagerExplanations
.set(true);
1326 // Turn on arith rewrite equalities only for pure arithmetic
1327 if(! options::arithRewriteEq
.wasSetByUser()) {
1328 bool arithRewriteEq
= d_logic
.isPure(THEORY_ARITH
) && !d_logic
.isQuantified();
1329 Trace("smt") << "setting arith rewrite equalities " << arithRewriteEq
<< endl
;
1330 options::arithRewriteEq
.set(arithRewriteEq
);
1332 if(! options::arithHeuristicPivots
.wasSetByUser()) {
1333 int16_t heuristicPivots
= 5;
1334 if(d_logic
.isPure(THEORY_ARITH
) && !d_logic
.isQuantified()) {
1335 if(d_logic
.isDifferenceLogic()) {
1336 heuristicPivots
= -1;
1337 } else if(!d_logic
.areIntegersUsed()) {
1338 heuristicPivots
= 0;
1341 Trace("smt") << "setting arithHeuristicPivots " << heuristicPivots
<< endl
;
1342 options::arithHeuristicPivots
.set(heuristicPivots
);
1344 if(! options::arithPivotThreshold
.wasSetByUser()){
1345 uint16_t pivotThreshold
= 2;
1346 if(d_logic
.isPure(THEORY_ARITH
) && !d_logic
.isQuantified()){
1347 if(d_logic
.isDifferenceLogic()){
1348 pivotThreshold
= 16;
1351 Trace("smt") << "setting arith arithPivotThreshold " << pivotThreshold
<< endl
;
1352 options::arithPivotThreshold
.set(pivotThreshold
);
1354 if(! options::arithStandardCheckVarOrderPivots
.wasSetByUser()){
1355 int16_t varOrderPivots
= -1;
1356 if(d_logic
.isPure(THEORY_ARITH
) && !d_logic
.isQuantified()){
1357 varOrderPivots
= 200;
1359 Trace("smt") << "setting arithStandardCheckVarOrderPivots " << varOrderPivots
<< endl
;
1360 options::arithStandardCheckVarOrderPivots
.set(varOrderPivots
);
1362 // Turn off early theory preprocessing if arithRewriteEq is on
1363 if (options::arithRewriteEq()) {
1364 d_earlyTheoryPP
= false;
1367 // Set decision mode based on logic (if not set by user)
1368 if(!options::decisionMode
.wasSetByUser()) {
1369 decision::DecisionMode decMode
=
1371 d_logic
.hasEverything() ? decision::DECISION_STRATEGY_JUSTIFICATION
:
1373 (not d_logic
.isQuantified() &&
1374 d_logic
.isPure(THEORY_BV
)
1376 // QF_AUFBV or QF_ABV or QF_UFBV
1377 (not d_logic
.isQuantified() &&
1378 (d_logic
.isTheoryEnabled(THEORY_ARRAY
) ||
1379 d_logic
.isTheoryEnabled(THEORY_UF
)) &&
1380 d_logic
.isTheoryEnabled(THEORY_BV
)
1382 // QF_AUFLIA (and may be ends up enabling QF_AUFLRA?)
1383 (not d_logic
.isQuantified() &&
1384 d_logic
.isTheoryEnabled(THEORY_ARRAY
) &&
1385 d_logic
.isTheoryEnabled(THEORY_UF
) &&
1386 d_logic
.isTheoryEnabled(THEORY_ARITH
)
1389 (not d_logic
.isQuantified() &&
1390 d_logic
.isPure(THEORY_ARITH
) && d_logic
.isLinear() && !d_logic
.isDifferenceLogic() && !d_logic
.areIntegersUsed()
1393 d_logic
.isQuantified() ||
1395 d_logic
.isTheoryEnabled(THEORY_STRINGS
)
1396 ? decision::DECISION_STRATEGY_JUSTIFICATION
1397 : decision::DECISION_STRATEGY_INTERNAL
1402 d_logic
.hasEverything() || d_logic
.isTheoryEnabled(THEORY_STRINGS
) ? false :
1404 (not d_logic
.isQuantified() &&
1405 d_logic
.isTheoryEnabled(THEORY_ARRAY
) &&
1406 d_logic
.isTheoryEnabled(THEORY_UF
) &&
1407 d_logic
.isTheoryEnabled(THEORY_ARITH
)
1410 (not d_logic
.isQuantified() &&
1411 d_logic
.isPure(THEORY_ARITH
) && d_logic
.isLinear() && !d_logic
.isDifferenceLogic() && !d_logic
.areIntegersUsed()
1416 Trace("smt") << "setting decision mode to " << decMode
<< endl
;
1417 options::decisionMode
.set(decMode
);
1418 options::decisionStopOnly
.set(stoponly
);
1420 if( options::incrementalSolving() ){
1421 //disable modes not supported by incremental
1422 options::sortInference
.set( false );
1423 options::ufssFairnessMonotone
.set( false );
1425 //local theory extensions
1426 if( options::localTheoryExt() ){
1427 if( !options::instMaxLevel
.wasSetByUser() ){
1428 options::instMaxLevel
.set( 0 );
1431 if( d_logic
.hasCardinalityConstraints() ){
1432 //must have finite model finding on
1433 options::finiteModelFind
.set( true );
1435 if(options::fmfBoundIntLazy
.wasSetByUser() && options::fmfBoundIntLazy()) {
1436 options::fmfBoundInt
.set( true );
1438 //now have determined whether fmfBoundInt is on/off
1439 //apply fmfBoundInt options
1440 if( options::fmfBoundInt() ){
1441 //must have finite model finding on
1442 options::finiteModelFind
.set( true );
1443 if( ! options::mbqiMode
.wasSetByUser() ||
1444 ( options::mbqiMode()!=quantifiers::MBQI_NONE
&&
1445 options::mbqiMode()!=quantifiers::MBQI_FMC
&&
1446 options::mbqiMode()!=quantifiers::MBQI_FMC_INTERVAL
) ){
1447 //if bounded integers are set, use no MBQI by default
1448 options::mbqiMode
.set( quantifiers::MBQI_NONE
);
1450 if( ! options::prenexQuant
.wasSetByUser() ){
1451 options::prenexQuant
.set( quantifiers::PRENEX_NONE
);
1454 if( options::ufssSymBreak() ){
1455 options::sortInference
.set( true );
1457 if( options::fmfFunWellDefinedRelevant() ){
1458 if( !options::fmfFunWellDefined
.wasSetByUser() ){
1459 options::fmfFunWellDefined
.set( true );
1462 if( options::fmfFunWellDefined() ){
1463 if( !options::finiteModelFind
.wasSetByUser() ){
1464 options::finiteModelFind
.set( true );
1468 //now, have determined whether finite model find is on/off
1469 //apply finite model finding options
1470 if( options::finiteModelFind() ){
1471 if( !options::eMatching
.wasSetByUser() ){
1472 options::eMatching
.set( options::fmfInstEngine() );
1474 if( !options::instWhenMode
.wasSetByUser() ){
1475 //instantiate only on last call FIXME: remove?
1476 if( options::eMatching() ){
1477 options::instWhenMode
.set( quantifiers::INST_WHEN_LAST_CALL
);
1480 if( options::mbqiMode()==quantifiers::MBQI_ABS
){
1481 if( !options::preSkolemQuant
.wasSetByUser() ){
1482 options::preSkolemQuant
.set( true );
1484 if( !options::preSkolemQuantNested
.wasSetByUser() ){
1485 options::preSkolemQuantNested
.set( true );
1487 if( !options::fmfOneInstPerRound
.wasSetByUser() ){
1488 options::fmfOneInstPerRound
.set( true );
1493 //apply counterexample guided instantiation options
1494 if( options::cegqiSingleInv() ){
1495 options::ceGuidedInst
.set( true );
1497 if( options::ceGuidedInst() ){
1498 //counterexample-guided instantiation for sygus
1499 if( !options::cegqiSingleInv
.wasSetByUser() ){
1500 options::cegqiSingleInv
.set( true );
1502 if( !options::quantConflictFind
.wasSetByUser() ){
1503 options::quantConflictFind
.set( false );
1505 if( !options::instNoEntail
.wasSetByUser() ){
1506 options::instNoEntail
.set( false );
1508 //do not allow partial functions
1509 if( !options::bitvectorDivByZeroConst
.wasSetByUser() ){
1510 options::bitvectorDivByZeroConst
.set( true );
1512 if( !options::dtRewriteErrorSel
.wasSetByUser() ){
1513 options::dtRewriteErrorSel
.set( true );
1516 if( !options::miniscopeQuant
.wasSetByUser() ){
1517 options::miniscopeQuant
.set( false );
1519 if( !options::miniscopeQuantFreeVar
.wasSetByUser() ){
1520 options::miniscopeQuantFreeVar
.set( false );
1523 if( !options::rewriteDivk
.wasSetByUser()) {
1524 options::rewriteDivk
.set( true );
1527 if( !options::macrosQuant
.wasSetByUser()) {
1528 options::macrosQuant
.set( false );
1530 if( !options::cbqiPreRegInst
.wasSetByUser()) {
1531 options::cbqiPreRegInst
.set( true );
1534 //counterexample-guided instantiation for non-sygus
1535 // enable if any quantifiers with arithmetic or datatypes
1536 if( ( d_logic
.isQuantified() && ( d_logic
.isTheoryEnabled(THEORY_ARITH
) || d_logic
.isTheoryEnabled(THEORY_DATATYPES
) ) ) ||
1537 options::cbqiAll() ){
1538 if( !options::cbqi
.wasSetByUser() ){
1539 options::cbqi
.set( true );
1542 if( options::cbqiSplx() ){
1543 //implies more general option
1544 options::cbqi
.set( true );
1546 if( options::cbqi() ){
1548 if( !options::rewriteDivk
.wasSetByUser()) {
1549 options::rewriteDivk
.set( true );
1552 if( options::cbqi() && d_logic
.isPure(THEORY_ARITH
) ){
1553 options::cbqiAll
.set( false );
1554 if( !options::quantConflictFind
.wasSetByUser() ){
1555 options::quantConflictFind
.set( false );
1557 if( !options::instNoEntail
.wasSetByUser() ){
1558 options::instNoEntail
.set( false );
1560 if( !options::instWhenMode
.wasSetByUser() && options::cbqiModel() ){
1561 //only instantiation should happen at last call when model is avaiable
1562 if( !options::instWhenMode
.wasSetByUser() ){
1563 options::instWhenMode
.set( quantifiers::INST_WHEN_LAST_CALL
);
1569 //implied options...
1570 if( options::qcfMode
.wasSetByUser() || options::qcfTConstraint() ){
1571 options::quantConflictFind
.set( true );
1573 //for induction techniques
1574 if( options::quantInduction() ){
1575 if( !options::dtStcInduction
.wasSetByUser() ){
1576 options::dtStcInduction
.set( true );
1578 if( !options::intWfInduction
.wasSetByUser() ){
1579 options::intWfInduction
.set( true );
1582 if( options::dtStcInduction() ){
1583 //leads to unfairness FIXME
1584 if( !options::dtForceAssignment
.wasSetByUser() ){
1585 options::dtForceAssignment
.set( true );
1587 //try to remove ITEs from quantified formulas
1588 if( !options::iteDtTesterSplitQuant
.wasSetByUser() ){
1589 options::iteDtTesterSplitQuant
.set( true );
1591 if( !options::iteLiftQuant
.wasSetByUser() ){
1592 options::iteLiftQuant
.set( quantifiers::ITE_LIFT_QUANT_MODE_ALL
);
1595 if( options::intWfInduction() ){
1596 if( !options::purifyTriggers
.wasSetByUser() ){
1597 options::purifyTriggers
.set( true );
1600 if( options::conjectureNoFilter() ){
1601 if( !options::conjectureFilterActiveTerms
.wasSetByUser() ){
1602 options::conjectureFilterActiveTerms
.set( false );
1604 if( !options::conjectureFilterCanonical
.wasSetByUser() ){
1605 options::conjectureFilterCanonical
.set( false );
1607 if( !options::conjectureFilterModel
.wasSetByUser() ){
1608 options::conjectureFilterModel
.set( false );
1611 if( options::conjectureGenPerRound
.wasSetByUser() ){
1612 if( options::conjectureGenPerRound()>0 ){
1613 options::conjectureGen
.set( true );
1615 options::conjectureGen
.set( false );
1618 //can't pre-skolemize nested quantifiers without UF theory
1619 if( !d_logic
.isTheoryEnabled(THEORY_UF
) && options::preSkolemQuant() ){
1620 if( !options::preSkolemQuantNested
.wasSetByUser() ){
1621 options::preSkolemQuantNested
.set( false );
1625 //until bugs 371,431 are fixed
1626 if( ! options::minisatUseElim
.wasSetByUser()){
1627 if( d_logic
.isQuantified() || options::produceModels() || options::produceAssignments() || options::checkModels() ){
1628 options::minisatUseElim
.set( false );
1631 else if (options::minisatUseElim()) {
1632 if (options::produceModels()) {
1633 Notice() << "SmtEngine: turning off produce-models to support minisatUseElim" << endl
;
1634 setOption("produce-models", SExpr("false"));
1636 if (options::produceAssignments()) {
1637 Notice() << "SmtEngine: turning off produce-assignments to support minisatUseElim" << endl
;
1638 setOption("produce-assignments", SExpr("false"));
1640 if (options::checkModels()) {
1641 Notice() << "SmtEngine: turning off check-models to support minisatUseElim" << endl
;
1642 setOption("check-models", SExpr("false"));
1646 // For now, these array theory optimizations do not support model-building
1647 if (options::produceModels() || options::produceAssignments() || options::checkModels()) {
1648 options::arraysOptimizeLinear
.set(false);
1649 options::arraysLazyRIntro1
.set(false);
1652 // Non-linear arithmetic does not support models
1653 if (d_logic
.isTheoryEnabled(THEORY_ARITH
) &&
1654 !d_logic
.isLinear()) {
1655 if (options::produceModels()) {
1656 if(options::produceModels
.wasSetByUser()) {
1657 throw OptionException("produce-model not supported with nonlinear arith");
1659 Warning() << "SmtEngine: turning off produce-models because unsupported for nonlinear arith" << endl
;
1660 setOption("produce-models", SExpr("false"));
1662 if (options::produceAssignments()) {
1663 if(options::produceAssignments
.wasSetByUser()) {
1664 throw OptionException("produce-assignments not supported with nonlinear arith");
1666 Warning() << "SmtEngine: turning off produce-assignments because unsupported for nonlinear arith" << endl
;
1667 setOption("produce-assignments", SExpr("false"));
1669 if (options::checkModels()) {
1670 if(options::checkModels
.wasSetByUser()) {
1671 throw OptionException("check-models not supported with nonlinear arith");
1673 Warning() << "SmtEngine: turning off check-models because unsupported for nonlinear arith" << endl
;
1674 setOption("check-models", SExpr("false"));
1678 if(options::incrementalSolving() && (options::proof() || options::unsatCores())) {
1679 Warning() << "SmtEngine: turning off incremental solving mode (not yet supported with --proof or --produce-unsat-cores, try --tear-down-incremental instead)" << endl
;
1680 setOption("incremental", SExpr("false"));
1684 void SmtEngine::setInfo(const std::string
& key
, const CVC4::SExpr
& value
)
1685 throw(OptionException
, ModalException
) {
1687 SmtScope
smts(this);
1689 Trace("smt") << "SMT setInfo(" << key
<< ", " << value
<< ")" << endl
;
1691 if(Dump
.isOn("benchmark")) {
1692 if(key
== "status") {
1693 string s
= value
.getValue();
1694 BenchmarkStatus status
=
1695 (s
== "sat") ? SMT_SATISFIABLE
:
1696 ((s
== "unsat") ? SMT_UNSATISFIABLE
: SMT_UNKNOWN
);
1697 Dump("benchmark") << SetBenchmarkStatusCommand(status
);
1699 Dump("benchmark") << SetInfoCommand(key
, value
);
1703 // Check for CVC4-specific info keys (prefixed with "cvc4-" or "cvc4_")
1704 if(key
.length() > 5) {
1705 string prefix
= key
.substr(0, 5);
1706 if(prefix
== "cvc4-" || prefix
== "cvc4_") {
1707 string cvc4key
= key
.substr(5);
1708 if(cvc4key
== "logic") {
1709 if(! value
.isAtom()) {
1710 throw OptionException("argument to (set-info :cvc4-logic ..) must be a string");
1712 SmtScope
smts(this);
1713 d_logic
= value
.getValue();
1717 throw UnrecognizedOptionException();
1722 // Check for standard info keys (SMT-LIB v1, SMT-LIB v2, ...)
1723 if(key
== "source" ||
1724 key
== "category" ||
1725 key
== "difficulty" ||
1729 } else if(key
== "name") {
1730 d_filename
= value
.getValue();
1732 } else if(key
== "smt-lib-version") {
1733 if( (value
.isInteger() && value
.getIntegerValue() == Integer(2)) ||
1734 (value
.isRational() && value
.getRationalValue() == Rational(2)) ||
1735 value
.getValue() == "2" ||
1736 value
.getValue() == "2.0" ) {
1737 // supported SMT-LIB version
1738 if(!options::outputLanguage
.wasSetByUser() &&
1739 options::outputLanguage() == language::output::LANG_SMTLIB_V2_5
) {
1740 options::outputLanguage
.set(language::output::LANG_SMTLIB_V2_0
);
1741 *options::out() << language::SetLanguage(language::output::LANG_SMTLIB_V2_0
);
1744 } else if( (value
.isRational() && value
.getRationalValue() == Rational(5, 2)) ||
1745 value
.getValue() == "2.5" ) {
1746 // supported SMT-LIB version
1747 if(!options::outputLanguage
.wasSetByUser() &&
1748 options::outputLanguage() == language::output::LANG_SMTLIB_V2_0
) {
1749 options::outputLanguage
.set(language::output::LANG_SMTLIB_V2_5
);
1750 *options::out() << language::SetLanguage(language::output::LANG_SMTLIB_V2_5
);
1754 Warning() << "Warning: unsupported smt-lib-version: " << value
<< endl
;
1755 throw UnrecognizedOptionException();
1756 } else if(key
== "status") {
1758 if(value
.isAtom()) {
1759 s
= value
.getValue();
1761 if(s
!= "sat" && s
!= "unsat" && s
!= "unknown") {
1762 throw OptionException("argument to (set-info :status ..) must be "
1763 "`sat' or `unsat' or `unknown'");
1765 d_status
= Result(s
, d_filename
);
1768 throw UnrecognizedOptionException();
1771 CVC4::SExpr
SmtEngine::getInfo(const std::string
& key
) const
1772 throw(OptionException
, ModalException
) {
1774 SmtScope
smts(this);
1776 Trace("smt") << "SMT getInfo(" << key
<< ")" << endl
;
1777 if(key
== "all-statistics") {
1778 vector
<SExpr
> stats
;
1779 for(StatisticsRegistry::const_iterator i
= NodeManager::fromExprManager(d_exprManager
)->getStatisticsRegistry()->begin();
1780 i
!= NodeManager::fromExprManager(d_exprManager
)->getStatisticsRegistry()->end();
1783 v
.push_back((*i
).first
);
1784 v
.push_back((*i
).second
);
1787 for(StatisticsRegistry::const_iterator i
= d_statisticsRegistry
->begin();
1788 i
!= d_statisticsRegistry
->end();
1791 v
.push_back((*i
).first
);
1792 v
.push_back((*i
).second
);
1795 return SExpr(stats
);
1796 } else if(key
== "error-behavior") {
1797 // immediate-exit | continued-execution
1798 if( options::continuedExecution() || options::interactive() ) {
1799 return SExpr(SExpr::Keyword("continued-execution"));
1801 return SExpr(SExpr::Keyword("immediate-exit"));
1803 } else if(key
== "name") {
1804 return SExpr(Configuration::getName());
1805 } else if(key
== "version") {
1806 return SExpr(Configuration::getVersionString());
1807 } else if(key
== "authors") {
1808 return SExpr(Configuration::about());
1809 } else if(key
== "status") {
1810 // sat | unsat | unknown
1811 switch(d_status
.asSatisfiabilityResult().isSat()) {
1813 return SExpr(SExpr::Keyword("sat"));
1815 return SExpr(SExpr::Keyword("unsat"));
1817 return SExpr(SExpr::Keyword("unknown"));
1819 } else if(key
== "reason-unknown") {
1820 if(!d_status
.isNull() && d_status
.isUnknown()) {
1822 ss
<< d_status
.whyUnknown();
1823 string s
= ss
.str();
1824 transform(s
.begin(), s
.end(), s
.begin(), ::tolower
);
1825 return SExpr(SExpr::Keyword(s
));
1827 throw ModalException("Can't get-info :reason-unknown when the "
1828 "last result wasn't unknown!");
1830 } else if(key
== "assertion-stack-levels") {
1831 return SExpr(d_userLevels
.size());
1832 } else if(key
== "all-options") {
1833 // get the options, like all-statistics
1834 std::vector
< std::vector
<std::string
> > current_options
= Options::current()->getOptions();
1835 return SExpr::parseListOfListOfAtoms(current_options
);
1837 throw UnrecognizedOptionException();
1841 void SmtEngine::defineFunction(Expr func
,
1842 const std::vector
<Expr
>& formals
,
1844 Trace("smt") << "SMT defineFunction(" << func
<< ")" << endl
;
1845 for(std::vector
<Expr
>::const_iterator i
= formals
.begin(); i
!= formals
.end(); ++i
) {
1846 if((*i
).getKind() != kind::BOUND_VARIABLE
) {
1848 ss
<< "All formal arguments to defined functions must be BOUND_VARIABLEs, but in the\n"
1849 << "definition of function " << func
<< ", formal\n"
1850 << " " << *i
<< "\n"
1851 << "has kind " << (*i
).getKind();
1852 throw TypeCheckingException(func
, ss
.str());
1857 ss
<< language::SetLanguage(language::SetLanguage::getLanguage(Dump
.getStream()))
1859 DefineFunctionCommand
c(ss
.str(), func
, formals
, formula
);
1860 addToModelCommandAndDump(c
, ExprManager::VAR_FLAG_DEFINED
, true, "declarations");
1862 SmtScope
smts(this);
1864 PROOF( if (options::checkUnsatCores()) {
1865 d_defineCommands
.push_back(c
.clone());
1869 // Substitute out any abstract values in formula
1870 Expr form
= d_private
->substituteAbstractValues(Node::fromExpr(formula
)).toExpr();
1873 Type formulaType
= form
.getType(options::typeChecking());
1875 Type funcType
= func
.getType();
1876 // We distinguish here between definitions of constants and functions,
1877 // because the type checking for them is subtly different. Perhaps we
1878 // should instead have SmtEngine::defineFunction() and
1879 // SmtEngine::defineConstant() for better clarity, although then that
1880 // doesn't match the SMT-LIBv2 standard...
1881 if(formals
.size() > 0) {
1882 Type rangeType
= FunctionType(funcType
).getRangeType();
1883 if(! formulaType
.isComparableTo(rangeType
)) {
1885 ss
<< "Type of defined function does not match its declaration\n"
1886 << "The function : " << func
<< "\n"
1887 << "Declared type : " << rangeType
<< "\n"
1888 << "The body : " << formula
<< "\n"
1889 << "Body type : " << formulaType
;
1890 throw TypeCheckingException(func
, ss
.str());
1893 if(! formulaType
.isComparableTo(funcType
)) {
1895 ss
<< "Declared type of defined constant does not match its definition\n"
1896 << "The constant : " << func
<< "\n"
1897 << "Declared type : " << funcType
<< " " << Type::getTypeNode(funcType
)->getId() << "\n"
1898 << "The definition : " << formula
<< "\n"
1899 << "Definition type: " << formulaType
<< " " << Type::getTypeNode(formulaType
)->getId();
1900 throw TypeCheckingException(func
, ss
.str());
1903 TNode funcNode
= func
.getTNode();
1904 vector
<Node
> formalsNodes
;
1905 for(vector
<Expr
>::const_iterator i
= formals
.begin(),
1906 iend
= formals
.end();
1909 formalsNodes
.push_back((*i
).getNode());
1911 TNode formNode
= form
.getTNode();
1912 DefinedFunction
def(funcNode
, formalsNodes
, formNode
);
1913 // Permit (check-sat) (define-fun ...) (get-value ...) sequences.
1914 // Otherwise, (check-sat) (get-value ((! foo :named bar))) breaks
1915 // d_haveAdditions = true;
1916 Debug("smt") << "definedFunctions insert " << funcNode
<< " " << formNode
<< endl
;
1917 d_definedFunctions
->insert(funcNode
, def
);
1920 bool SmtEngine::isDefinedFunction( Expr func
){
1921 Node nf
= Node::fromExpr( func
);
1922 Debug("smt") << "isDefined function " << nf
<< "?" << std::endl
;
1923 return d_definedFunctions
->find(nf
) != d_definedFunctions
->end();
1926 Node
SmtEnginePrivate::expandDefinitions(TNode n
, hash_map
<Node
, Node
, NodeHashFunction
>& cache
, bool expandOnly
)
1927 throw(TypeCheckingException
, LogicException
, UnsafeInterruptException
) {
1929 stack
< triple
<Node
, Node
, bool> > worklist
;
1931 worklist
.push(make_triple(Node(n
), Node(n
), false));
1932 // The worklist is made of triples, each is input / original node then the output / rewritten node
1933 // and finally a flag tracking whether the children have been explored (i.e. if this is a downward
1937 spendResource(options::preprocessStep());
1938 n
= worklist
.top().first
; // n is the input / original
1939 Node node
= worklist
.top().second
; // node is the output / result
1940 bool childrenPushed
= worklist
.top().third
;
1943 // Working downwards
1944 if(!childrenPushed
) {
1945 Kind k
= n
.getKind();
1947 // Apart from apply, we can short circuit leaves
1948 if(k
!= kind::APPLY
&& n
.getNumChildren() == 0) {
1949 SmtEngine::DefinedFunctionMap::const_iterator i
= d_smt
.d_definedFunctions
->find(n
);
1950 if(i
!= d_smt
.d_definedFunctions
->end()) {
1951 // replacement must be closed
1952 if((*i
).second
.getFormals().size() > 0) {
1953 result
.push(d_smt
.d_nodeManager
->mkNode(kind::LAMBDA
, d_smt
.d_nodeManager
->mkNode(kind::BOUND_VAR_LIST
, (*i
).second
.getFormals()), (*i
).second
.getFormula()));
1956 // don't bother putting in the cache
1957 result
.push((*i
).second
.getFormula());
1960 // don't bother putting in the cache
1965 // maybe it's in the cache
1966 hash_map
<Node
, Node
, NodeHashFunction
>::iterator cacheHit
= cache
.find(n
);
1967 if(cacheHit
!= cache
.end()) {
1968 TNode ret
= (*cacheHit
).second
;
1969 result
.push(ret
.isNull() ? n
: ret
);
1973 // otherwise expand it
1974 bool doExpand
= ( k
== kind::APPLY
&& n
.getOperator().getKind() != kind::LAMBDA
);
1976 if( options::macrosQuant() ){
1977 //expand if we have inferred an operator corresponds to a defined function
1978 doExpand
= k
==kind::APPLY_UF
&& d_smt
.isDefinedFunction( n
.getOperator().toExpr() );
1982 // application of a user-defined symbol
1983 TNode func
= n
.getOperator();
1984 SmtEngine::DefinedFunctionMap::const_iterator i
= d_smt
.d_definedFunctions
->find(func
);
1985 if(i
== d_smt
.d_definedFunctions
->end()) {
1986 throw TypeCheckingException(n
.toExpr(), string("Undefined function: `") + func
.toString() + "'");
1988 DefinedFunction def
= (*i
).second
;
1989 vector
<Node
> formals
= def
.getFormals();
1991 if(Debug
.isOn("expand")) {
1992 Debug("expand") << "found: " << n
<< endl
;
1993 Debug("expand") << " func: " << func
<< endl
;
1994 string name
= func
.getAttribute(expr::VarNameAttr());
1995 Debug("expand") << " : \"" << name
<< "\"" << endl
;
1997 if(Debug
.isOn("expand")) {
1998 Debug("expand") << " defn: " << def
.getFunction() << endl
2000 if(formals
.size() > 0) {
2001 copy( formals
.begin(), formals
.end() - 1,
2002 ostream_iterator
<Node
>(Debug("expand"), ", ") );
2003 Debug("expand") << formals
.back();
2005 Debug("expand") << "]" << endl
2006 << " " << def
.getFunction().getType() << endl
2007 << " " << def
.getFormula() << endl
;
2010 TNode fm
= def
.getFormula();
2011 Node instance
= fm
.substitute(formals
.begin(), formals
.end(),
2012 n
.begin(), n
.end());
2013 Debug("expand") << "made : " << instance
<< endl
;
2015 Node expanded
= expandDefinitions(instance
, cache
, expandOnly
);
2016 cache
[n
] = (n
== expanded
? Node::null() : expanded
);
2017 result
.push(expanded
);
2020 } else if(! expandOnly
) {
2021 // do not do any theory stuff if expandOnly is true
2023 theory::Theory
* t
= d_smt
.d_theoryEngine
->theoryOf(node
);
2026 LogicRequest
req(d_smt
);
2027 node
= t
->expandDefinition(req
, n
);
2030 // there should be children here, otherwise we short-circuited a result-push/continue, above
2031 if (node
.getNumChildren() == 0) {
2032 Debug("expand") << "Unexpectedly no children..." << node
<< endl
;
2034 // This invariant holds at the moment but it is concievable that a new theory
2035 // might introduce a kind which can have children before definition expansion but doesn't
2036 // afterwards. If this happens, remove this assertion.
2037 Assert(node
.getNumChildren() > 0);
2039 // the partial functions can fall through, in which case we still
2040 // consider their children
2041 worklist
.push(make_triple(Node(n
), node
, true)); // Original and rewritten result
2043 for(size_t i
= 0; i
< node
.getNumChildren(); ++i
) {
2044 worklist
.push(make_triple(node
[i
], node
[i
], false)); // Rewrite the children of the result only
2049 // Reconstruct the node from it's (now rewritten) children on the stack
2051 Debug("expand") << "cons : " << node
<< endl
;
2052 //cout << "cons : " << node << endl;
2053 NodeBuilder
<> nb(node
.getKind());
2054 if(node
.getMetaKind() == kind::metakind::PARAMETERIZED
) {
2055 Debug("expand") << "op : " << node
.getOperator() << endl
;
2056 //cout << "op : " << node.getOperator() << endl;
2057 nb
<< node
.getOperator();
2059 for(size_t i
= 0; i
< node
.getNumChildren(); ++i
) {
2060 Assert(!result
.empty());
2061 Node expanded
= result
.top();
2063 //cout << "exchld : " << expanded << endl;
2064 Debug("expand") << "exchld : " << expanded
<< endl
;
2068 cache
[n
] = n
== node
? Node::null() : node
; // Only cache once all subterms are expanded
2071 } while(!worklist
.empty());
2073 AlwaysAssert(result
.size() == 1);
2075 return result
.top();
2078 //TODO: clean this up
2079 struct intToBV_stack_element
{
2081 bool children_added
;
2082 intToBV_stack_element(TNode node
)
2083 : node(node
), children_added(false) {}
2084 };/* struct intToBV_stack_element */
2086 typedef std::hash_map
<Node
, Node
, NodeHashFunction
> NodeMap
;
2088 Node
SmtEnginePrivate::intToBVMakeBinary(TNode n
, NodeMap
& cache
) {
2089 // Do a topological sort of the subexpressions and substitute them
2090 vector
<intToBV_stack_element
> toVisit
;
2091 toVisit
.push_back(n
);
2093 while (!toVisit
.empty())
2095 // The current node we are processing
2096 intToBV_stack_element
& stackHead
= toVisit
.back();
2097 TNode current
= stackHead
.node
;
2099 NodeMap::iterator find
= cache
.find(current
);
2100 if (find
!= cache
.end()) {
2104 if (stackHead
.children_added
) {
2105 // Children have been processed, so rebuild this node
2107 NodeManager
* nm
= NodeManager::currentNM();
2108 if (current
.getNumChildren() > 2 && (current
.getKind() == kind::PLUS
|| current
.getKind() == kind::MULT
)) {
2109 Assert(cache
.find(current
[0]) != cache
.end());
2110 result
= cache
[current
[0]];
2111 for (unsigned i
= 1; i
< current
.getNumChildren(); ++ i
) {
2112 Assert(cache
.find(current
[i
]) != cache
.end());
2113 Node child
= current
[i
];
2114 Node childRes
= cache
[current
[i
]];
2115 result
= nm
->mkNode(current
.getKind(), result
, childRes
);
2119 NodeBuilder
<> builder(current
.getKind());
2120 for (unsigned i
= 0; i
< current
.getNumChildren(); ++ i
) {
2121 Assert(cache
.find(current
[i
]) != cache
.end());
2122 builder
<< cache
[current
[i
]];
2126 cache
[current
] = result
;
2129 // Mark that we have added the children if any
2130 if (current
.getNumChildren() > 0) {
2131 stackHead
.children_added
= true;
2132 // We need to add the children
2133 for(TNode::iterator child_it
= current
.begin(); child_it
!= current
.end(); ++ child_it
) {
2134 TNode childNode
= *child_it
;
2135 NodeMap::iterator childFind
= cache
.find(childNode
);
2136 if (childFind
== cache
.end()) {
2137 toVisit
.push_back(childNode
);
2141 cache
[current
] = current
;
2149 Node
SmtEnginePrivate::intToBV(TNode n
, NodeMap
& cache
) {
2150 int size
= options::solveIntAsBV();
2151 AlwaysAssert(size
> 0);
2152 AlwaysAssert(!options::incrementalSolving());
2154 vector
<intToBV_stack_element
> toVisit
;
2155 NodeMap binaryCache
;
2156 Node n_binary
= intToBVMakeBinary(n
, binaryCache
);
2157 toVisit
.push_back(TNode(n_binary
));
2159 while (!toVisit
.empty())
2161 // The current node we are processing
2162 intToBV_stack_element
& stackHead
= toVisit
.back();
2163 TNode current
= stackHead
.node
;
2165 // If node is already in the cache we're done, pop from the stack
2166 NodeMap::iterator find
= cache
.find(current
);
2167 if (find
!= cache
.end()) {
2172 // Not yet substituted, so process
2173 NodeManager
* nm
= NodeManager::currentNM();
2174 if (stackHead
.children_added
) {
2175 // Children have been processed, so rebuild this node
2176 vector
<Node
> children
;
2178 for (unsigned i
= 0; i
< current
.getNumChildren(); ++ i
) {
2179 Assert(cache
.find(current
[i
]) != cache
.end());
2180 TNode childRes
= cache
[current
[i
]];
2181 TypeNode type
= childRes
.getType();
2182 if (type
.isBitVector()) {
2183 unsigned bvsize
= type
.getBitVectorSize();
2188 children
.push_back(childRes
);
2191 kind::Kind_t newKind
= current
.getKind();
2195 Assert(children
.size() == 2);
2196 newKind
= kind::BITVECTOR_PLUS
;
2200 Assert(children
.size() == 2);
2201 newKind
= kind::BITVECTOR_MULT
;
2205 Assert(children
.size() == 2);
2206 newKind
= kind::BITVECTOR_SUB
;
2210 Assert(children
.size() == 1);
2211 newKind
= kind::BITVECTOR_NEG
;
2215 newKind
= kind::BITVECTOR_SLT
;
2218 newKind
= kind::BITVECTOR_SLE
;
2221 newKind
= kind::BITVECTOR_SGT
;
2224 newKind
= kind::BITVECTOR_SGE
;
2230 if (Theory::theoryOf(current
) == THEORY_BOOL
) {
2233 throw TypeCheckingException(current
.toExpr(), string("Cannot translate to BV: ") + current
.toString());
2235 for (unsigned i
= 0; i
< children
.size(); ++i
) {
2236 TypeNode type
= children
[i
].getType();
2237 if (!type
.isBitVector()) {
2240 unsigned bvsize
= type
.getBitVectorSize();
2243 Node signExtendOp
= nm
->mkConst
<BitVectorSignExtend
>(BitVectorSignExtend(max
- bvsize
));
2244 children
[i
] = nm
->mkNode(signExtendOp
, children
[i
]);
2248 NodeBuilder
<> builder(newKind
);
2249 for (unsigned i
= 0; i
< children
.size(); ++i
) {
2250 builder
<< children
[i
];
2252 // Mark the substitution and continue
2253 Node result
= builder
;
2255 result
= Rewriter::rewrite(result
);
2256 cache
[current
] = result
;
2259 // Mark that we have added the children if any
2260 if (current
.getNumChildren() > 0) {
2261 stackHead
.children_added
= true;
2262 // We need to add the children
2263 for(TNode::iterator child_it
= current
.begin(); child_it
!= current
.end(); ++ child_it
) {
2264 TNode childNode
= *child_it
;
2265 NodeMap::iterator childFind
= cache
.find(childNode
);
2266 if (childFind
== cache
.end()) {
2267 toVisit
.push_back(childNode
);
2271 // It's a leaf: could be a variable or a numeral
2272 Node result
= current
;
2273 if (current
.isVar()) {
2274 if (current
.getType() == nm
->integerType()) {
2275 result
= nm
->mkSkolem("__intToBV_var", nm
->mkBitVectorType(size
),
2276 "Variable introduced in intToBV pass");
2279 AlwaysAssert(current
.getType() == nm
->booleanType());
2282 else if (current
.isConst()) {
2283 switch (current
.getKind()) {
2284 case kind::CONST_RATIONAL
: {
2285 Rational constant
= current
.getConst
<Rational
>();
2286 AlwaysAssert(constant
.isIntegral());
2287 BitVector
bv(size
, constant
.getNumerator());
2288 if (bv
.getValue() != constant
.getNumerator()) {
2289 throw TypeCheckingException(current
.toExpr(), string("Not enough bits for constant in intToBV: ") + current
.toString());
2291 result
= nm
->mkConst(bv
);
2294 case kind::CONST_BOOLEAN
:
2297 throw TypeCheckingException(current
.toExpr(), string("Cannot translate const to BV: ") + current
.toString());
2301 throw TypeCheckingException(current
.toExpr(), string("Cannot translate to BV: ") + current
.toString());
2303 cache
[current
] = result
;
2308 return cache
[n_binary
];
2311 void SmtEnginePrivate::removeITEs() {
2312 d_smt
.finalOptionsAreSet();
2313 spendResource(options::preprocessStep());
2314 Trace("simplify") << "SmtEnginePrivate::removeITEs()" << endl
;
2316 // Remove all of the ITE occurrences and normalize
2317 d_iteRemover
.run(d_assertions
.ref(), d_iteSkolemMap
, true);
2318 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
2319 d_assertions
.replace(i
, Rewriter::rewrite(d_assertions
[i
]));
2323 void SmtEnginePrivate::staticLearning() {
2324 d_smt
.finalOptionsAreSet();
2325 spendResource(options::preprocessStep());
2327 TimerStat::CodeTimer
staticLearningTimer(d_smt
.d_stats
->d_staticLearningTime
);
2329 Trace("simplify") << "SmtEnginePrivate::staticLearning()" << endl
;
2331 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
2333 NodeBuilder
<> learned(kind::AND
);
2334 learned
<< d_assertions
[i
];
2335 d_smt
.d_theoryEngine
->ppStaticLearn(d_assertions
[i
], learned
);
2336 if(learned
.getNumChildren() == 1) {
2339 d_assertions
.replace(i
, learned
);
2344 // do dumping (before/after any preprocessing pass)
2345 static void dumpAssertions(const char* key
, const AssertionPipeline
& assertionList
) {
2346 if( Dump
.isOn("assertions") &&
2347 Dump
.isOn(string("assertions:") + key
) ) {
2348 // Push the simplified assertions to the dump output stream
2349 for(unsigned i
= 0; i
< assertionList
.size(); ++ i
) {
2350 TNode n
= assertionList
[i
];
2351 Dump("assertions") << AssertCommand(Expr(n
.toExpr()));
2356 // returns false if it learns a conflict
2357 bool SmtEnginePrivate::nonClausalSimplify() {
2358 spendResource(options::preprocessStep());
2359 d_smt
.finalOptionsAreSet();
2361 if(options::unsatCores()) {
2365 TimerStat::CodeTimer
nonclausalTimer(d_smt
.d_stats
->d_nonclausalSimplificationTime
);
2367 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify()" << endl
;
2369 if(d_propagatorNeedsFinish
) {
2370 d_propagator
.finish();
2371 d_propagatorNeedsFinish
= false;
2373 d_propagator
.initialize();
2375 // Assert all the assertions to the propagator
2376 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): "
2377 << "asserting to propagator" << endl
;
2378 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
2379 Assert(Rewriter::rewrite(d_assertions
[i
]) == d_assertions
[i
]);
2380 // Don't reprocess substitutions
2381 if (d_substitutionsIndex
> 0 && i
== d_substitutionsIndex
) {
2384 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): asserting " << d_assertions
[i
] << endl
;
2385 Debug("cores") << "d_propagator assertTrue: " << d_assertions
[i
] << std::endl
;
2386 d_propagator
.assertTrue(d_assertions
[i
]);
2389 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): "
2390 << "propagating" << endl
;
2391 if (d_propagator
.propagate()) {
2392 // If in conflict, just return false
2393 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): "
2394 << "conflict in non-clausal propagation" << endl
;
2395 Node falseNode
= NodeManager::currentNM()->mkConst
<bool>(false);
2396 Assert(!options::unsatCores());
2397 d_assertions
.clear();
2398 addFormula(falseNode
, false, false);
2399 d_propagatorNeedsFinish
= true;
2403 // No conflict, go through the literals and solve them
2404 SubstitutionMap
constantPropagations(d_smt
.d_context
);
2405 SubstitutionMap
newSubstitutions(d_smt
.d_context
);
2406 SubstitutionMap::iterator pos
;
2408 for(unsigned i
= 0, i_end
= d_nonClausalLearnedLiterals
.size(); i
< i_end
; ++ i
) {
2409 // Simplify the literal we learned wrt previous substitutions
2410 Node learnedLiteral
= d_nonClausalLearnedLiterals
[i
];
2411 Assert(Rewriter::rewrite(learnedLiteral
) == learnedLiteral
);
2412 Assert(d_topLevelSubstitutions
.apply(learnedLiteral
) == learnedLiteral
);
2413 Node learnedLiteralNew
= newSubstitutions
.apply(learnedLiteral
);
2414 if (learnedLiteral
!= learnedLiteralNew
) {
2415 learnedLiteral
= Rewriter::rewrite(learnedLiteralNew
);
2418 learnedLiteralNew
= constantPropagations
.apply(learnedLiteral
);
2419 if (learnedLiteralNew
== learnedLiteral
) {
2422 ++d_smt
.d_stats
->d_numConstantProps
;
2423 learnedLiteral
= Rewriter::rewrite(learnedLiteralNew
);
2425 // It might just simplify to a constant
2426 if (learnedLiteral
.isConst()) {
2427 if (learnedLiteral
.getConst
<bool>()) {
2428 // If the learned literal simplifies to true, it's redundant
2431 // If the learned literal simplifies to false, we're in conflict
2432 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): "
2434 << d_nonClausalLearnedLiterals
[i
] << endl
;
2435 Assert(!options::unsatCores());
2436 d_assertions
.clear();
2437 addFormula(NodeManager::currentNM()->mkConst
<bool>(false), false, false);
2438 d_propagatorNeedsFinish
= true;
2443 // Solve it with the corresponding theory, possibly adding new
2444 // substitutions to newSubstitutions
2445 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): "
2446 << "solving " << learnedLiteral
<< endl
;
2448 Theory::PPAssertStatus solveStatus
=
2449 d_smt
.d_theoryEngine
->solve(learnedLiteral
, newSubstitutions
);
2451 switch (solveStatus
) {
2452 case Theory::PP_ASSERT_STATUS_SOLVED
: {
2453 // The literal should rewrite to true
2454 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): "
2455 << "solved " << learnedLiteral
<< endl
;
2456 Assert(Rewriter::rewrite(newSubstitutions
.apply(learnedLiteral
)).isConst());
2457 // vector<pair<Node, Node> > equations;
2458 // constantPropagations.simplifyLHS(d_topLevelSubstitutions, equations, true);
2459 // if (equations.empty()) {
2462 // Assert(equations[0].first.isConst() && equations[0].second.isConst() && equations[0].first != equations[0].second);
2463 // else fall through
2466 case Theory::PP_ASSERT_STATUS_CONFLICT
:
2467 // If in conflict, we return false
2468 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): "
2469 << "conflict while solving "
2470 << learnedLiteral
<< endl
;
2471 Assert(!options::unsatCores());
2472 d_assertions
.clear();
2473 addFormula(NodeManager::currentNM()->mkConst
<bool>(false), false, false);
2474 d_propagatorNeedsFinish
= true;
2477 if (d_doConstantProp
&& learnedLiteral
.getKind() == kind::EQUAL
&& (learnedLiteral
[0].isConst() || learnedLiteral
[1].isConst())) {
2478 // constant propagation
2481 if (learnedLiteral
[0].isConst()) {
2482 t
= learnedLiteral
[1];
2483 c
= learnedLiteral
[0];
2486 t
= learnedLiteral
[0];
2487 c
= learnedLiteral
[1];
2489 Assert(!t
.isConst());
2490 Assert(constantPropagations
.apply(t
) == t
);
2491 Assert(d_topLevelSubstitutions
.apply(t
) == t
);
2492 Assert(newSubstitutions
.apply(t
) == t
);
2493 constantPropagations
.addSubstitution(t
, c
);
2494 // vector<pair<Node,Node> > equations;
2495 // constantPropagations.simplifyLHS(t, c, equations, true);
2496 // if (!equations.empty()) {
2497 // Assert(equations[0].first.isConst() && equations[0].second.isConst() && equations[0].first != equations[0].second);
2498 // d_assertions.clear();
2499 // addFormula(NodeManager::currentNM()->mkConst<bool>(false), false, false);
2502 // d_topLevelSubstitutions.simplifyRHS(constantPropagations);
2506 d_nonClausalLearnedLiterals
[j
++] = d_nonClausalLearnedLiterals
[i
];
2511 #ifdef CVC4_ASSERTIONS
2512 // Check data structure invariants:
2513 // 1. for each lhs of d_topLevelSubstitutions, does not appear anywhere in rhs of d_topLevelSubstitutions or anywhere in constantPropagations
2514 // 2. each lhs of constantPropagations rewrites to itself
2515 // 3. if l -> r is a constant propagation and l is a subterm of l' with l' -> r' another constant propagation, then l'[l/r] -> r' should be a
2516 // constant propagation too
2517 // 4. each lhs of constantPropagations is different from each rhs
2518 for (pos
= newSubstitutions
.begin(); pos
!= newSubstitutions
.end(); ++pos
) {
2519 Assert((*pos
).first
.isVar());
2520 Assert(d_topLevelSubstitutions
.apply((*pos
).first
) == (*pos
).first
);
2521 Assert(d_topLevelSubstitutions
.apply((*pos
).second
) == (*pos
).second
);
2522 Assert(newSubstitutions
.apply(newSubstitutions
.apply((*pos
).second
)) == newSubstitutions
.apply((*pos
).second
));
2524 for (pos
= constantPropagations
.begin(); pos
!= constantPropagations
.end(); ++pos
) {
2525 Assert((*pos
).second
.isConst());
2526 Assert(Rewriter::rewrite((*pos
).first
) == (*pos
).first
);
2527 // Node newLeft = d_topLevelSubstitutions.apply((*pos).first);
2528 // if (newLeft != (*pos).first) {
2529 // newLeft = Rewriter::rewrite(newLeft);
2530 // Assert(newLeft == (*pos).second ||
2531 // (constantPropagations.hasSubstitution(newLeft) && constantPropagations.apply(newLeft) == (*pos).second));
2533 // newLeft = constantPropagations.apply((*pos).first);
2534 // if (newLeft != (*pos).first) {
2535 // newLeft = Rewriter::rewrite(newLeft);
2536 // Assert(newLeft == (*pos).second ||
2537 // (constantPropagations.hasSubstitution(newLeft) && constantPropagations.apply(newLeft) == (*pos).second));
2539 Assert(constantPropagations
.apply((*pos
).second
) == (*pos
).second
);
2541 #endif /* CVC4_ASSERTIONS */
2543 // Resize the learnt
2544 d_nonClausalLearnedLiterals
.resize(j
);
2546 hash_set
<TNode
, TNodeHashFunction
> s
;
2547 Trace("debugging") << "NonClausal simplify pre-preprocess\n";
2548 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
2549 Node assertion
= d_assertions
[i
];
2550 Node assertionNew
= newSubstitutions
.apply(assertion
);
2551 Trace("debugging") << "assertion = " << assertion
<< endl
;
2552 Trace("debugging") << "assertionNew = " << assertionNew
<< endl
;
2553 if (assertion
!= assertionNew
) {
2554 assertion
= Rewriter::rewrite(assertionNew
);
2555 Trace("debugging") << "rewrite(assertion) = " << assertion
<< endl
;
2557 Assert(Rewriter::rewrite(assertion
) == assertion
);
2559 assertionNew
= constantPropagations
.apply(assertion
);
2560 if (assertionNew
== assertion
) {
2563 ++d_smt
.d_stats
->d_numConstantProps
;
2564 Trace("debugging") << "assertionNew = " << assertionNew
<< endl
;
2565 assertion
= Rewriter::rewrite(assertionNew
);
2566 Trace("debugging") << "assertionNew = " << assertionNew
<< endl
;
2568 Trace("debugging") << "\n";
2569 s
.insert(assertion
);
2570 d_assertions
.replace(i
, assertion
);
2571 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): "
2572 << "non-clausal preprocessed: "
2573 << assertion
<< endl
;
2576 // If in incremental mode, add substitutions to the list of assertions
2577 if (d_substitutionsIndex
> 0) {
2578 NodeBuilder
<> substitutionsBuilder(kind::AND
);
2579 substitutionsBuilder
<< d_assertions
[d_substitutionsIndex
];
2580 pos
= newSubstitutions
.begin();
2581 for (; pos
!= newSubstitutions
.end(); ++pos
) {
2582 // Add back this substitution as an assertion
2583 TNode lhs
= (*pos
).first
, rhs
= newSubstitutions
.apply((*pos
).second
);
2584 Node n
= NodeManager::currentNM()->mkNode(lhs
.getType().isBoolean() ? kind::IFF
: kind::EQUAL
, lhs
, rhs
);
2585 substitutionsBuilder
<< n
;
2586 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): will notify SAT layer of substitution: " << n
<< endl
;
2588 if (substitutionsBuilder
.getNumChildren() > 1) {
2589 d_assertions
.replace(d_substitutionsIndex
,
2590 Rewriter::rewrite(Node(substitutionsBuilder
)));
2593 // If not in incremental mode, must add substitutions to model
2594 TheoryModel
* m
= d_smt
.d_theoryEngine
->getModel();
2596 for(pos
= newSubstitutions
.begin(); pos
!= newSubstitutions
.end(); ++pos
) {
2597 Node n
= (*pos
).first
;
2598 Node v
= newSubstitutions
.apply((*pos
).second
);
2599 Trace("model") << "Add substitution : " << n
<< " " << v
<< endl
;
2600 m
->addSubstitution( n
, v
);
2605 NodeBuilder
<> learnedBuilder(kind::AND
);
2606 Assert(d_realAssertionsEnd
<= d_assertions
.size());
2607 learnedBuilder
<< d_assertions
[d_realAssertionsEnd
- 1];
2609 for (unsigned i
= 0; i
< d_nonClausalLearnedLiterals
.size(); ++ i
) {
2610 Node learned
= d_nonClausalLearnedLiterals
[i
];
2611 Assert(d_topLevelSubstitutions
.apply(learned
) == learned
);
2612 Node learnedNew
= newSubstitutions
.apply(learned
);
2613 if (learned
!= learnedNew
) {
2614 learned
= Rewriter::rewrite(learnedNew
);
2616 Assert(Rewriter::rewrite(learned
) == learned
);
2618 learnedNew
= constantPropagations
.apply(learned
);
2619 if (learnedNew
== learned
) {
2622 ++d_smt
.d_stats
->d_numConstantProps
;
2623 learned
= Rewriter::rewrite(learnedNew
);
2625 if (s
.find(learned
) != s
.end()) {
2629 learnedBuilder
<< learned
;
2630 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): "
2631 << "non-clausal learned : "
2634 d_nonClausalLearnedLiterals
.clear();
2636 for (pos
= constantPropagations
.begin(); pos
!= constantPropagations
.end(); ++pos
) {
2637 Node cProp
= (*pos
).first
.eqNode((*pos
).second
);
2638 Assert(d_topLevelSubstitutions
.apply(cProp
) == cProp
);
2639 Node cPropNew
= newSubstitutions
.apply(cProp
);
2640 if (cProp
!= cPropNew
) {
2641 cProp
= Rewriter::rewrite(cPropNew
);
2642 Assert(Rewriter::rewrite(cProp
) == cProp
);
2644 if (s
.find(cProp
) != s
.end()) {
2648 learnedBuilder
<< cProp
;
2649 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): "
2650 << "non-clausal constant propagation : "
2654 // Add new substitutions to topLevelSubstitutions
2655 // Note that we don't have to keep rhs's in full solved form
2656 // because SubstitutionMap::apply does a fixed-point iteration when substituting
2657 d_topLevelSubstitutions
.addSubstitutions(newSubstitutions
);
2659 if(learnedBuilder
.getNumChildren() > 1) {
2660 d_assertions
.replace(d_realAssertionsEnd
- 1,
2661 Rewriter::rewrite(Node(learnedBuilder
)));
2664 d_propagatorNeedsFinish
= true;
2668 void SmtEnginePrivate::bvAbstraction() {
2669 Trace("bv-abstraction") << "SmtEnginePrivate::bvAbstraction()" << endl
;
2670 std::vector
<Node
> new_assertions
;
2671 bool changed
= d_smt
.d_theoryEngine
->ppBvAbstraction(d_assertions
.ref(), new_assertions
);
2672 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
2673 d_assertions
.replace(i
, Rewriter::rewrite(new_assertions
[i
]));
2675 // if we are using the lazy solver and the abstraction
2676 // applies, then UF symbols were introduced
2677 if (options::bitblastMode() == theory::bv::BITBLAST_MODE_LAZY
&&
2679 LogicRequest
req(d_smt
);
2680 req
.widenLogic(THEORY_UF
);
2685 void SmtEnginePrivate::bvToBool() {
2686 Trace("bv-to-bool") << "SmtEnginePrivate::bvToBool()" << endl
;
2687 spendResource(options::preprocessStep());
2688 std::vector
<Node
> new_assertions
;
2689 d_smt
.d_theoryEngine
->ppBvToBool(d_assertions
.ref(), new_assertions
);
2690 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
2691 d_assertions
.replace(i
, Rewriter::rewrite(new_assertions
[i
]));
2695 bool SmtEnginePrivate::simpITE() {
2696 TimerStat::CodeTimer
simpITETimer(d_smt
.d_stats
->d_simpITETime
);
2698 spendResource(options::preprocessStep());
2700 Trace("simplify") << "SmtEnginePrivate::simpITE()" << endl
;
2702 unsigned numAssertionOnEntry
= d_assertions
.size();
2703 for (unsigned i
= 0; i
< d_assertions
.size(); ++i
) {
2704 spendResource(options::preprocessStep());
2705 Node result
= d_smt
.d_theoryEngine
->ppSimpITE(d_assertions
[i
]);
2706 d_assertions
.replace(i
, result
);
2707 if(result
.isConst() && !result
.getConst
<bool>()){
2711 bool result
= d_smt
.d_theoryEngine
->donePPSimpITE(d_assertions
.ref());
2712 if(numAssertionOnEntry
< d_assertions
.size()){
2713 compressBeforeRealAssertions(numAssertionOnEntry
);
2718 void SmtEnginePrivate::compressBeforeRealAssertions(size_t before
){
2719 size_t curr
= d_assertions
.size();
2720 if(before
>= curr
||
2721 d_realAssertionsEnd
<= 0 ||
2722 d_realAssertionsEnd
>= curr
){
2727 // original: [0 ... d_realAssertionsEnd)
2729 // ites skolems [d_realAssertionsEnd, before)
2731 // added [before, curr)
2733 Assert(0 < d_realAssertionsEnd
);
2734 Assert(d_realAssertionsEnd
<= before
);
2735 Assert(before
< curr
);
2737 std::vector
<Node
> intoConjunction
;
2738 for(size_t i
= before
; i
<curr
; ++i
){
2739 intoConjunction
.push_back(d_assertions
[i
]);
2741 d_assertions
.resize(before
);
2742 size_t lastBeforeItes
= d_realAssertionsEnd
- 1;
2743 intoConjunction
.push_back(d_assertions
[lastBeforeItes
]);
2744 Node newLast
= util::NaryBuilder::mkAssoc(kind::AND
, intoConjunction
);
2745 d_assertions
.replace(lastBeforeItes
, newLast
);
2746 Assert(d_assertions
.size() == before
);
2749 void SmtEnginePrivate::unconstrainedSimp() {
2750 TimerStat::CodeTimer
unconstrainedSimpTimer(d_smt
.d_stats
->d_unconstrainedSimpTime
);
2751 spendResource(options::preprocessStep());
2752 Trace("simplify") << "SmtEnginePrivate::unconstrainedSimp()" << endl
;
2753 d_smt
.d_theoryEngine
->ppUnconstrainedSimp(d_assertions
.ref());
2757 void SmtEnginePrivate::constrainSubtypes(TNode top
, AssertionPipeline
& assertions
)
2760 Trace("constrainSubtypes") << "constrainSubtypes(): looking at " << top
<< endl
;
2763 stack
<TNode
> worklist
;
2768 TNode n
= worklist
.top();
2771 TypeNode t
= n
.getType();
2772 if(t
.isPredicateSubtype()) {
2773 WarningOnce() << "Warning: CVC4 doesn't yet do checking that predicate subtypes are nonempty domains" << endl
;
2774 Node pred
= t
.getSubtypePredicate();
2776 // pred can be a LAMBDA, a function constant, or a datatype tester
2777 Trace("constrainSubtypes") << "constrainSubtypes(): pred.getType() == " << pred
.getType() << endl
;
2778 if(d_smt
.d_definedFunctions
->find(pred
) != d_smt
.d_definedFunctions
->end()) {
2780 } else if(pred
.getType().isTester()) {
2781 k
= kind::APPLY_TESTER
;
2785 Node app
= NodeManager::currentNM()->mkNode(k
, pred
, n
);
2786 Trace("constrainSubtypes") << "constrainSubtypes(): assert(" << k
<< ") " << app
<< endl
;
2787 assertions
.push_back(app
);
2788 } else if(t
.isSubrange()) {
2789 SubrangeBounds bounds
= t
.getSubrangeBounds();
2790 Trace("constrainSubtypes") << "constrainSubtypes(): got bounds " << bounds
<< endl
;
2791 if(bounds
.lower
.hasBound()) {
2792 Node c
= NodeManager::currentNM()->mkConst(Rational(bounds
.lower
.getBound()));
2793 Node lb
= NodeManager::currentNM()->mkNode(kind::LEQ
, c
, n
);
2794 Trace("constrainSubtypes") << "constrainSubtypes(): assert " << lb
<< endl
;
2795 assertions
.push_back(lb
);
2797 if(bounds
.upper
.hasBound()) {
2798 Node c
= NodeManager::currentNM()->mkConst(Rational(bounds
.upper
.getBound()));
2799 Node ub
= NodeManager::currentNM()->mkNode(kind::LEQ
, n
, c
);
2800 Trace("constrainSubtypes") << "constrainSubtypes(): assert " << ub
<< endl
;
2801 assertions
.push_back(ub
);
2805 for(TNode::iterator i
= n
.begin(); i
!= n
.end(); ++i
) {
2806 if(done
.find(*i
) == done
.end()) {
2811 } while(! worklist
.empty());
2814 void SmtEnginePrivate::traceBackToAssertions(const std::vector
<Node
>& nodes
, std::vector
<TNode
>& assertions
) {
2815 const booleans::CircuitPropagator::BackEdgesMap
& backEdges
= d_propagator
.getBackEdges();
2816 for(vector
<Node
>::const_iterator i
= nodes
.begin(); i
!= nodes
.end(); ++i
) {
2817 booleans::CircuitPropagator::BackEdgesMap::const_iterator j
= backEdges
.find(*i
);
2818 // term must appear in map, otherwise how did we get here?!
2819 Assert(j
!= backEdges
.end());
2820 // if term maps to empty, that means it's a top-level assertion
2821 if(!(*j
).second
.empty()) {
2822 traceBackToAssertions((*j
).second
, assertions
);
2824 assertions
.push_back(*i
);
2829 size_t SmtEnginePrivate::removeFromConjunction(Node
& n
, const std::hash_set
<unsigned long>& toRemove
) {
2830 Assert(n
.getKind() == kind::AND
);
2831 size_t removals
= 0;
2832 for(Node::iterator j
= n
.begin(); j
!= n
.end(); ++j
) {
2833 size_t subremovals
= 0;
2835 if(toRemove
.find(sub
.getId()) != toRemove
.end() ||
2836 (sub
.getKind() == kind::AND
&& (subremovals
= removeFromConjunction(sub
, toRemove
)) > 0)) {
2837 NodeBuilder
<> b(kind::AND
);
2838 b
.append(n
.begin(), j
);
2839 if(subremovals
> 0) {
2840 removals
+= subremovals
;
2845 for(++j
; j
!= n
.end(); ++j
) {
2846 if(toRemove
.find((*j
).getId()) != toRemove
.end()) {
2848 } else if((*j
).getKind() == kind::AND
) {
2850 if((subremovals
= removeFromConjunction(sub
, toRemove
)) > 0) {
2851 removals
+= subremovals
;
2860 if(b
.getNumChildren() == 0) {
2863 } else if(b
.getNumChildren() == 1) {
2869 n
= Rewriter::rewrite(n
);
2874 Assert(removals
== 0);
2878 void SmtEnginePrivate::doMiplibTrick() {
2879 Assert(d_realAssertionsEnd
== d_assertions
.size());
2880 Assert(!options::incrementalSolving());
2882 const booleans::CircuitPropagator::BackEdgesMap
& backEdges
= d_propagator
.getBackEdges();
2883 hash_set
<unsigned long> removeAssertions
;
2885 NodeManager
* nm
= NodeManager::currentNM();
2886 Node zero
= nm
->mkConst(Rational(0)), one
= nm
->mkConst(Rational(1));
2888 hash_map
<TNode
, Node
, TNodeHashFunction
> intVars
;
2889 for(vector
<Node
>::const_iterator i
= d_boolVars
.begin(); i
!= d_boolVars
.end(); ++i
) {
2890 if(d_propagator
.isAssigned(*i
)) {
2891 Debug("miplib") << "ineligible: " << *i
<< " because assigned " << d_propagator
.getAssignment(*i
) << endl
;
2895 vector
<TNode
> assertions
;
2896 booleans::CircuitPropagator::BackEdgesMap::const_iterator j
= backEdges
.find(*i
);
2897 // if not in back edges map, the bool var is unconstrained, showing up in no assertions.
2898 // if maps to an empty vector, that means the bool var was asserted itself.
2899 if(j
!= backEdges
.end()) {
2900 if(!(*j
).second
.empty()) {
2901 traceBackToAssertions((*j
).second
, assertions
);
2903 assertions
.push_back(*i
);
2906 Debug("miplib") << "for " << *i
<< endl
;
2907 bool eligible
= true;
2908 map
<pair
<Node
, Node
>, uint64_t> marks
;
2909 map
<pair
<Node
, Node
>, vector
<Rational
> > coef
;
2910 map
<pair
<Node
, Node
>, vector
<Rational
> > checks
;
2911 map
<pair
<Node
, Node
>, vector
<TNode
> > asserts
;
2912 for(vector
<TNode
>::const_iterator j
= assertions
.begin(); j
!= assertions
.end(); ++j
) {
2913 Debug("miplib") << " found: " << *j
<< endl
;
2914 if((*j
).getKind() != kind::IMPLIES
) {
2916 Debug("miplib") << " -- INELIGIBLE -- (not =>)" << endl
;
2919 Node conj
= BooleanSimplification::simplify((*j
)[0]);
2920 if(conj
.getKind() == kind::AND
&& conj
.getNumChildren() > 6) {
2922 Debug("miplib") << " -- INELIGIBLE -- (N-ary /\\ too big)" << endl
;
2925 if(conj
.getKind() != kind::AND
&& !conj
.isVar() && !(conj
.getKind() == kind::NOT
&& conj
[0].isVar())) {
2927 Debug("miplib") << " -- INELIGIBLE -- (not /\\ or literal)" << endl
;
2930 if((*j
)[1].getKind() != kind::EQUAL
||
2931 !( ( (*j
)[1][0].isVar() &&
2932 (*j
)[1][1].getKind() == kind::CONST_RATIONAL
) ||
2933 ( (*j
)[1][0].getKind() == kind::CONST_RATIONAL
&&
2934 (*j
)[1][1].isVar() ) )) {
2936 Debug("miplib") << " -- INELIGIBLE -- (=> (and X X) X)" << endl
;
2939 if(conj
.getKind() == kind::AND
) {
2941 bool found_x
= false;
2942 map
<TNode
, bool> neg
;
2943 for(Node::iterator ii
= conj
.begin(); ii
!= conj
.end(); ++ii
) {
2945 posv
.push_back(*ii
);
2947 found_x
= found_x
|| *i
== *ii
;
2948 } else if((*ii
).getKind() == kind::NOT
&& (*ii
)[0].isVar()) {
2949 posv
.push_back((*ii
)[0]);
2950 neg
[(*ii
)[0]] = true;
2951 found_x
= found_x
|| *i
== (*ii
)[0];
2954 Debug("miplib") << " -- INELIGIBLE -- (non-var: " << *ii
<< ")" << endl
;
2957 if(d_propagator
.isAssigned(posv
.back())) {
2959 Debug("miplib") << " -- INELIGIBLE -- (" << posv
.back() << " asserted)" << endl
;
2968 Debug("miplib") << " --INELIGIBLE -- (couldn't find " << *i
<< " in conjunction)" << endl
;
2971 sort(posv
.begin(), posv
.end());
2972 const Node pos
= NodeManager::currentNM()->mkNode(kind::AND
, posv
);
2973 const TNode var
= ((*j
)[1][0].getKind() == kind::CONST_RATIONAL
) ? (*j
)[1][1] : (*j
)[1][0];
2974 const pair
<Node
, Node
> pos_var(pos
, var
);
2975 const Rational
& constant
= ((*j
)[1][0].getKind() == kind::CONST_RATIONAL
) ? (*j
)[1][0].getConst
<Rational
>() : (*j
)[1][1].getConst
<Rational
>();
2977 unsigned countneg
= 0, thepos
= 0;
2978 for(unsigned ii
= 0; ii
< pos
.getNumChildren(); ++ii
) {
2983 mark
|= (0x1 << ii
);
2986 if((marks
[pos_var
] & (1lu << mark
)) != 0) {
2988 Debug("miplib") << " -- INELIGIBLE -- (remarked)" << endl
;
2991 Debug("miplib") << "mark is " << mark
<< " -- " << (1lu << mark
) << endl
;
2992 marks
[pos_var
] |= (1lu << mark
);
2993 Debug("miplib") << "marks[" << pos
<< "," << var
<< "] now " << marks
[pos_var
] << endl
;
2994 if(countneg
== pos
.getNumChildren()) {
2997 Debug("miplib") << " -- INELIGIBLE -- (nonzero constant)" << endl
;
3000 } else if(countneg
== pos
.getNumChildren() - 1) {
3001 Assert(coef
[pos_var
].size() <= 6 && thepos
< 6);
3002 if(coef
[pos_var
].size() <= thepos
) {
3003 coef
[pos_var
].resize(thepos
+ 1);
3005 coef
[pos_var
][thepos
] = constant
;
3007 if(checks
[pos_var
].size() <= mark
) {
3008 checks
[pos_var
].resize(mark
+ 1);
3010 checks
[pos_var
][mark
] = constant
;
3012 asserts
[pos_var
].push_back(*j
);
3015 if(x
!= *i
&& x
!= (*i
).notNode()) {
3017 Debug("miplib") << " -- INELIGIBLE -- (x not present where I expect it)" << endl
;
3020 const bool xneg
= (x
.getKind() == kind::NOT
);
3021 x
= xneg
? x
[0] : x
;
3022 Debug("miplib") << " x:" << x
<< " " << xneg
<< endl
;
3023 const TNode var
= ((*j
)[1][0].getKind() == kind::CONST_RATIONAL
) ? (*j
)[1][1] : (*j
)[1][0];
3024 const pair
<Node
, Node
> x_var(x
, var
);
3025 const Rational
& constant
= ((*j
)[1][0].getKind() == kind::CONST_RATIONAL
) ? (*j
)[1][0].getConst
<Rational
>() : (*j
)[1][1].getConst
<Rational
>();
3026 unsigned mark
= (xneg
? 0 : 1);
3027 if((marks
[x_var
] & (1u << mark
)) != 0) {
3029 Debug("miplib") << " -- INELIGIBLE -- (remarked)" << endl
;
3032 marks
[x_var
] |= (1u << mark
);
3036 Debug("miplib") << " -- INELIGIBLE -- (nonzero constant)" << endl
;
3040 Assert(coef
[x_var
].size() <= 6);
3041 coef
[x_var
].resize(6);
3042 coef
[x_var
][0] = constant
;
3044 asserts
[x_var
].push_back(*j
);
3048 for(map
<pair
<Node
, Node
>, uint64_t>::const_iterator j
= marks
.begin(); j
!= marks
.end(); ++j
) {
3049 const TNode pos
= (*j
).first
.first
;
3050 const TNode var
= (*j
).first
.second
;
3051 const pair
<Node
, Node
>& pos_var
= (*j
).first
;
3052 const uint64_t mark
= (*j
).second
;
3053 const unsigned numVars
= pos
.getKind() == kind::AND
? pos
.getNumChildren() : 1;
3054 uint64_t expected
= (uint64_t(1) << (1 << numVars
)) - 1;
3055 expected
= (expected
== 0) ? -1 : expected
; // fix for overflow
3056 Debug("miplib") << "[" << pos
<< "] => " << hex
<< mark
<< " expect " << expected
<< dec
<< endl
;
3057 Assert(pos
.getKind() == kind::AND
|| pos
.isVar());
3058 if(mark
!= expected
) {
3059 Debug("miplib") << " -- INELIGIBLE " << pos
<< " -- (insufficiently marked, got " << mark
<< " for " << numVars
<< " vars, expected " << expected
<< endl
;
3061 if(mark
!= 3) { // exclude single-var case; nothing to check there
3062 uint64_t sz
= (uint64_t(1) << checks
[pos_var
].size()) - 1;
3063 sz
= (sz
== 0) ? -1 : sz
; // fix for overflow
3064 Assert(sz
== mark
, "expected size %u == mark %u", sz
, mark
);
3065 for(size_t k
= 0; k
< checks
[pos_var
].size(); ++k
) {
3066 if((k
& (k
- 1)) != 0) {
3068 Debug("miplib") << k
<< " => " << checks
[pos_var
][k
] << endl
;
3069 for(size_t v
= 1, kk
= k
; kk
!= 0; ++v
, kk
>>= 1) {
3070 if((kk
& 0x1) == 1) {
3071 Assert(pos
.getKind() == kind::AND
);
3072 Debug("miplib") << "var " << v
<< " : " << pos
[v
- 1] << " coef:" << coef
[pos_var
][v
- 1] << endl
;
3073 sum
+= coef
[pos_var
][v
- 1];
3076 Debug("miplib") << "checkSum is " << sum
<< " input says " << checks
[pos_var
][k
] << endl
;
3077 if(sum
!= checks
[pos_var
][k
]) {
3079 Debug("miplib") << " -- INELIGIBLE " << pos
<< " -- (nonlinear combination)" << endl
;
3083 Assert(checks
[pos_var
][k
] == 0, "checks[(%s,%s)][%u] should be 0, but it's %s", pos
.toString().c_str(), var
.toString().c_str(), k
, checks
[pos_var
][k
].toString().c_str()); // we never set for single-positive-var
3088 eligible
= true; // next is still eligible
3092 Debug("miplib") << " -- ELIGIBLE " << *i
<< " , " << pos
<< " --" << endl
;
3093 vector
<Node
> newVars
;
3094 expr::NodeSelfIterator ii
, iiend
;
3095 if(pos
.getKind() == kind::AND
) {
3099 ii
= expr::NodeSelfIterator::self(pos
);
3100 iiend
= expr::NodeSelfIterator::selfEnd(pos
);
3102 for(; ii
!= iiend
; ++ii
) {
3103 Node
& varRef
= intVars
[*ii
];
3104 if(varRef
.isNull()) {
3106 ss
<< "mipvar_" << *ii
;
3107 Node newVar
= nm
->mkSkolem(ss
.str(), nm
->integerType(), "a variable introduced due to scrubbing a miplib encoding", NodeManager::SKOLEM_EXACT_NAME
);
3108 Node geq
= Rewriter::rewrite(nm
->mkNode(kind::GEQ
, newVar
, zero
));
3109 Node leq
= Rewriter::rewrite(nm
->mkNode(kind::LEQ
, newVar
, one
));
3110 addFormula(Rewriter::rewrite(geq
.andNode(leq
)), false, false);
3111 SubstitutionMap
nullMap(&d_fakeContext
);
3112 Theory::PPAssertStatus status CVC4_UNUSED
; // just for assertions
3113 status
= d_smt
.d_theoryEngine
->solve(geq
, nullMap
);
3114 Assert(status
== Theory::PP_ASSERT_STATUS_UNSOLVED
,
3115 "unexpected solution from arith's ppAssert()");
3116 Assert(nullMap
.empty(),
3117 "unexpected substitution from arith's ppAssert()");
3118 status
= d_smt
.d_theoryEngine
->solve(leq
, nullMap
);
3119 Assert(status
== Theory::PP_ASSERT_STATUS_UNSOLVED
,
3120 "unexpected solution from arith's ppAssert()");
3121 Assert(nullMap
.empty(),
3122 "unexpected substitution from arith's ppAssert()");
3123 d_smt
.d_theoryEngine
->getModel()->addSubstitution(*ii
, newVar
.eqNode(one
));
3124 newVars
.push_back(newVar
);
3127 newVars
.push_back(varRef
);
3129 if(!d_smt
.d_logic
.areIntegersUsed()) {
3130 d_smt
.d_logic
= d_smt
.d_logic
.getUnlockedCopy();
3131 d_smt
.d_logic
.enableIntegers();
3132 d_smt
.d_logic
.lock();
3136 if(pos
.getKind() == kind::AND
) {
3137 NodeBuilder
<> sumb(kind::PLUS
);
3138 for(size_t ii
= 0; ii
< pos
.getNumChildren(); ++ii
) {
3139 sumb
<< nm
->mkNode(kind::MULT
, nm
->mkConst(coef
[pos_var
][ii
]), newVars
[ii
]);
3143 sum
= nm
->mkNode(kind::MULT
, nm
->mkConst(coef
[pos_var
][0]), newVars
[0]);
3145 Debug("miplib") << "vars[] " << var
<< endl
3146 << " eq " << Rewriter::rewrite(sum
) << endl
;
3147 Node newAssertion
= var
.eqNode(Rewriter::rewrite(sum
));
3148 if(d_topLevelSubstitutions
.hasSubstitution(newAssertion
[0])) {
3149 //Warning() << "RE-SUBSTITUTION " << newAssertion[0] << endl;
3150 //Warning() << "REPLACE " << newAssertion[1] << endl;
3151 //Warning() << "ORIG " << d_topLevelSubstitutions.getSubstitution(newAssertion[0]) << endl;
3152 Assert(d_topLevelSubstitutions
.getSubstitution(newAssertion
[0]) == newAssertion
[1]);
3153 } else if(pos
.getNumChildren() <= options::arithMLTrickSubstitutions()) {
3154 d_topLevelSubstitutions
.addSubstitution(newAssertion
[0], newAssertion
[1]);
3155 Debug("miplib") << "addSubs: " << newAssertion
[0] << " to " << newAssertion
[1] << endl
;
3157 Debug("miplib") << "skipSubs: " << newAssertion
[0] << " to " << newAssertion
[1] << " (threshold is " << options::arithMLTrickSubstitutions() << ")" << endl
;
3159 newAssertion
= Rewriter::rewrite(newAssertion
);
3160 Debug("miplib") << " " << newAssertion
<< endl
;
3161 addFormula(newAssertion
, false, false);
3162 Debug("miplib") << " assertions to remove: " << endl
;
3163 for(vector
<TNode
>::const_iterator k
= asserts
[pos_var
].begin(), k_end
= asserts
[pos_var
].end(); k
!= k_end
; ++k
) {
3164 Debug("miplib") << " " << *k
<< endl
;
3165 removeAssertions
.insert((*k
).getId());
3171 if(!removeAssertions
.empty()) {
3172 Debug("miplib") << "SmtEnginePrivate::simplify(): scrubbing miplib encoding..." << endl
;
3173 for(size_t i
= 0; i
< d_realAssertionsEnd
; ++i
) {
3174 if(removeAssertions
.find(d_assertions
[i
].getId()) != removeAssertions
.end()) {
3175 Debug("miplib") << "SmtEnginePrivate::simplify(): - removing " << d_assertions
[i
] << endl
;
3176 d_assertions
[i
] = d_true
;
3177 ++d_smt
.d_stats
->d_numMiplibAssertionsRemoved
;
3178 } else if(d_assertions
[i
].getKind() == kind::AND
) {
3179 size_t removals
= removeFromConjunction(d_assertions
[i
], removeAssertions
);
3181 Debug("miplib") << "SmtEnginePrivate::simplify(): - reduced " << d_assertions
[i
] << endl
;
3182 Debug("miplib") << "SmtEnginePrivate::simplify(): - by " << removals
<< " conjuncts" << endl
;
3183 d_smt
.d_stats
->d_numMiplibAssertionsRemoved
+= removals
;
3186 Debug("miplib") << "had: " << d_assertions
[i
] << endl
;
3187 d_assertions
[i
] = Rewriter::rewrite(d_topLevelSubstitutions
.apply(d_assertions
[i
]));
3188 Debug("miplib") << "now: " << d_assertions
[i
] << endl
;
3191 Debug("miplib") << "SmtEnginePrivate::simplify(): miplib pass found nothing." << endl
;
3193 d_realAssertionsEnd
= d_assertions
.size();
3197 // returns false if simplification led to "false"
3198 bool SmtEnginePrivate::simplifyAssertions()
3199 throw(TypeCheckingException
, LogicException
, UnsafeInterruptException
) {
3200 spendResource(options::preprocessStep());
3201 Assert(d_smt
.d_pendingPops
== 0);
3203 ScopeCounter
depth(d_simplifyAssertionsDepth
);
3205 Trace("simplify") << "SmtEnginePrivate::simplify()" << endl
;
3207 dumpAssertions("pre-nonclausal", d_assertions
);
3209 if(options::simplificationMode() != SIMPLIFICATION_MODE_NONE
) {
3210 // Perform non-clausal simplification
3211 Chat() << "...performing nonclausal simplification..." << endl
;
3212 Trace("simplify") << "SmtEnginePrivate::simplify(): "
3213 << "performing non-clausal simplification" << endl
;
3214 bool noConflict
= nonClausalSimplify();
3219 // We piggy-back off of the BackEdgesMap in the CircuitPropagator to
3220 // do the miplib trick.
3221 if( // check that option is on
3222 options::arithMLTrick() &&
3223 // miplib rewrites aren't safe in incremental mode
3224 ! options::incrementalSolving() &&
3225 // only useful in arith
3226 d_smt
.d_logic
.isTheoryEnabled(THEORY_ARITH
) &&
3227 // we add new assertions and need this (in practice, this
3228 // restriction only disables miplib processing during
3229 // re-simplification, which we don't expect to be useful anyway)
3230 d_realAssertionsEnd
== d_assertions
.size() ) {
3231 Chat() << "...fixing miplib encodings..." << endl
;
3232 Trace("simplify") << "SmtEnginePrivate::simplify(): "
3233 << "looking for miplib pseudobooleans..." << endl
;
3235 TimerStat::CodeTimer
miplibTimer(d_smt
.d_stats
->d_miplibPassTime
);
3239 Trace("simplify") << "SmtEnginePrivate::simplify(): "
3240 << "skipping miplib pseudobooleans pass (either incrementalSolving is on, or miplib pbs are turned off)..." << endl
;
3244 dumpAssertions("post-nonclausal", d_assertions
);
3245 Trace("smt") << "POST nonClausalSimplify" << endl
;
3246 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3248 // before ppRewrite check if only core theory for BV theory
3249 d_smt
.d_theoryEngine
->staticInitializeBVOptions(d_assertions
.ref());
3251 dumpAssertions("pre-theorypp", d_assertions
);
3253 // Theory preprocessing
3254 if (d_smt
.d_earlyTheoryPP
) {
3255 Chat() << "...doing early theory preprocessing..." << endl
;
3256 TimerStat::CodeTimer
codeTimer(d_smt
.d_stats
->d_theoryPreprocessTime
);
3257 // Call the theory preprocessors
3258 d_smt
.d_theoryEngine
->preprocessStart();
3259 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
3260 Assert(Rewriter::rewrite(d_assertions
[i
]) == d_assertions
[i
]);
3261 d_assertions
.replace(i
, d_smt
.d_theoryEngine
->preprocess(d_assertions
[i
]));
3262 Assert(Rewriter::rewrite(d_assertions
[i
]) == d_assertions
[i
]);
3266 dumpAssertions("post-theorypp", d_assertions
);
3267 Trace("smt") << "POST theoryPP" << endl
;
3268 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3270 // ITE simplification
3271 if(options::doITESimp() &&
3272 (d_simplifyAssertionsDepth
<= 1 || options::doITESimpOnRepeat())) {
3273 Chat() << "...doing ITE simplification..." << endl
;
3274 bool noConflict
= simpITE();
3276 Chat() << "...ITE simplification found unsat..." << endl
;
3281 dumpAssertions("post-itesimp", d_assertions
);
3282 Trace("smt") << "POST iteSimp" << endl
;
3283 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3285 // Unconstrained simplification
3286 if(options::unconstrainedSimp()) {
3287 Chat() << "...doing unconstrained simplification..." << endl
;
3288 unconstrainedSimp();
3291 dumpAssertions("post-unconstrained", d_assertions
);
3292 Trace("smt") << "POST unconstrainedSimp" << endl
;
3293 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3295 if(options::repeatSimp() && options::simplificationMode() != SIMPLIFICATION_MODE_NONE
) {
3296 Chat() << "...doing another round of nonclausal simplification..." << endl
;
3297 Trace("simplify") << "SmtEnginePrivate::simplify(): "
3298 << " doing repeated simplification" << endl
;
3299 bool noConflict
= nonClausalSimplify();
3305 dumpAssertions("post-repeatsimp", d_assertions
);
3306 Trace("smt") << "POST repeatSimp" << endl
;
3307 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3309 } catch(TypeCheckingExceptionPrivate
& tcep
) {
3310 // Calls to this function should have already weeded out any
3311 // typechecking exceptions via (e.g.) ensureBoolean(). But a
3312 // theory could still create a new expression that isn't
3313 // well-typed, and we don't want the C++ runtime to abort our
3314 // process without any error notice.
3316 ss
<< "A bad expression was produced. Original exception follows:\n"
3318 InternalError(ss
.str().c_str());
3323 Result
SmtEngine::check() {
3324 Assert(d_fullyInited
);
3325 Assert(d_pendingPops
== 0);
3327 Trace("smt") << "SmtEngine::check()" << endl
;
3329 ResourceManager
* resourceManager
= d_private
->getResourceManager();
3331 resourceManager
->beginCall();
3333 // Only way we can be out of resource is if cumulative budget is on
3334 if (resourceManager
->cumulativeLimitOn() &&
3335 resourceManager
->out()) {
3336 Result::UnknownExplanation why
= resourceManager
->outOfResources() ?
3337 Result::RESOURCEOUT
: Result::TIMEOUT
;
3338 return Result(Result::VALIDITY_UNKNOWN
, why
, d_filename
);
3341 // Make sure the prop layer has all of the assertions
3342 Trace("smt") << "SmtEngine::check(): processing assertions" << endl
;
3343 d_private
->processAssertions();
3345 // Turn off stop only for QF_LRA
3346 // TODO: Bring up in a meeting where to put this
3347 if(options::decisionStopOnly() && !options::decisionMode
.wasSetByUser() ){
3349 (not d_logic
.isQuantified() &&
3350 d_logic
.isPure(THEORY_ARITH
) && d_logic
.isLinear() && !d_logic
.isDifferenceLogic() && !d_logic
.areIntegersUsed()
3352 if(d_private
->d_iteSkolemMap
.empty()){
3353 options::decisionStopOnly
.set(false);
3354 d_decisionEngine
->clearStrategies();
3355 Trace("smt") << "SmtEngine::check(): turning off stop only" << endl
;
3360 TimerStat::CodeTimer
solveTimer(d_stats
->d_solveTime
);
3362 Chat() << "solving..." << endl
;
3363 Trace("smt") << "SmtEngine::check(): running check" << endl
;
3364 Result result
= d_propEngine
->checkSat();
3366 resourceManager
->endCall();
3367 Trace("limit") << "SmtEngine::check(): cumulative millis " << resourceManager
->getTimeUsage()
3368 << ", resources " << resourceManager
->getResourceUsage() << endl
;
3371 return Result(result
, d_filename
);
3374 Result
SmtEngine::quickCheck() {
3375 Assert(d_fullyInited
);
3376 Trace("smt") << "SMT quickCheck()" << endl
;
3377 return Result(Result::VALIDITY_UNKNOWN
, Result::REQUIRES_FULL_CHECK
, d_filename
);
3381 void SmtEnginePrivate::collectSkolems(TNode n
, set
<TNode
>& skolemSet
, hash_map
<Node
, bool, NodeHashFunction
>& cache
)
3383 hash_map
<Node
, bool, NodeHashFunction
>::iterator it
;
3385 if (it
!= cache
.end()) {
3389 size_t sz
= n
.getNumChildren();
3391 IteSkolemMap::iterator it
= d_iteSkolemMap
.find(n
);
3392 if (it
!= d_iteSkolemMap
.end()) {
3393 skolemSet
.insert(n
);
3400 for (; k
< sz
; ++k
) {
3401 collectSkolems(n
[k
], skolemSet
, cache
);
3407 bool SmtEnginePrivate::checkForBadSkolems(TNode n
, TNode skolem
, hash_map
<Node
, bool, NodeHashFunction
>& cache
)
3409 hash_map
<Node
, bool, NodeHashFunction
>::iterator it
;
3411 if (it
!= cache
.end()) {
3412 return (*it
).second
;
3415 size_t sz
= n
.getNumChildren();
3417 IteSkolemMap::iterator it
= d_iteSkolemMap
.find(n
);
3419 if (it
!= d_iteSkolemMap
.end()) {
3420 if (!((*it
).first
< n
)) {
3429 for (; k
< sz
; ++k
) {
3430 if (checkForBadSkolems(n
[k
], skolem
, cache
)) {
3440 Node
SmtEnginePrivate::rewriteBooleanTerms(TNode n
) {
3441 TimerStat::CodeTimer
codeTimer(d_smt
.d_stats
->d_rewriteBooleanTermsTime
);
3443 spendResource(options::preprocessStep());
3445 if(d_booleanTermConverter
== NULL
) {
3446 // This needs to be initialized _after_ the whole SMT framework is in place, subscribed
3447 // to ExprManager notifications, etc. Otherwise we might miss the "BooleanTerm" datatype
3448 // definition, and not dump it properly.
3449 d_booleanTermConverter
= new BooleanTermConverter(d_smt
);
3451 Node retval
= d_booleanTermConverter
->rewriteBooleanTerms(n
);
3453 switch(booleans::BooleanTermConversionMode mode
= options::booleanTermConversionMode()) {
3454 case booleans::BOOLEAN_TERM_CONVERT_TO_BITVECTORS
:
3455 case booleans::BOOLEAN_TERM_CONVERT_NATIVE
:
3456 if(!d_smt
.d_logic
.isTheoryEnabled(THEORY_BV
)) {
3457 d_smt
.d_logic
= d_smt
.d_logic
.getUnlockedCopy();
3458 d_smt
.d_logic
.enableTheory(THEORY_BV
);
3459 d_smt
.d_logic
.lock();
3462 case booleans::BOOLEAN_TERM_CONVERT_TO_DATATYPES
:
3463 if(!d_smt
.d_logic
.isTheoryEnabled(THEORY_DATATYPES
)) {
3464 d_smt
.d_logic
= d_smt
.d_logic
.getUnlockedCopy();
3465 d_smt
.d_logic
.enableTheory(THEORY_DATATYPES
);
3466 d_smt
.d_logic
.lock();
3476 void SmtEnginePrivate::processAssertions() {
3477 TimerStat::CodeTimer
paTimer(d_smt
.d_stats
->d_processAssertionsTime
);
3478 spendResource(options::preprocessStep());
3479 Assert(d_smt
.d_fullyInited
);
3480 Assert(d_smt
.d_pendingPops
== 0);
3482 // Dump the assertions
3483 dumpAssertions("pre-everything", d_assertions
);
3485 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() begin" << endl
;
3486 Trace("smt") << "SmtEnginePrivate::processAssertions()" << endl
;
3488 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3490 if (d_assertions
.size() == 0) {
3495 if (d_assertionsProcessed
&& options::incrementalSolving()) {
3496 // Placeholder for storing substitutions
3497 d_substitutionsIndex
= d_assertions
.size();
3498 d_assertions
.push_back(NodeManager::currentNM()->mkConst
<bool>(true));
3501 // Add dummy assertion in last position - to be used as a
3502 // placeholder for any new assertions to get added
3503 d_assertions
.push_back(NodeManager::currentNM()->mkConst
<bool>(true));
3504 // any assertions added beyond realAssertionsEnd must NOT affect the
3505 // equisatisfiability
3506 d_realAssertionsEnd
= d_assertions
.size();
3508 // Assertions are NOT guaranteed to be rewritten by this point
3510 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : pre-definition-expansion" << endl
;
3511 dumpAssertions("pre-definition-expansion", d_assertions
);
3513 Chat() << "expanding definitions..." << endl
;
3514 Trace("simplify") << "SmtEnginePrivate::simplify(): expanding definitions" << endl
;
3515 TimerStat::CodeTimer
codeTimer(d_smt
.d_stats
->d_definitionExpansionTime
);
3516 hash_map
<Node
, Node
, NodeHashFunction
> cache
;
3517 for(unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
3518 d_assertions
.replace(i
, expandDefinitions(d_assertions
[i
], cache
));
3521 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : post-definition-expansion" << endl
;
3522 dumpAssertions("post-definition-expansion", d_assertions
);
3524 // save the assertions now
3527 for (unsigned i
= 0; i
< d_assertions
.size(); ++i
) {
3528 ProofManager::currentPM()->addAssertion(d_assertions
[i
].toExpr());
3532 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3534 if( options::ceGuidedInst() ){
3535 //register sygus conjecture pre-rewrite (motivated by solution reconstruction)
3536 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
3537 d_smt
.d_theoryEngine
->getQuantifiersEngine()->getCegInstantiation()->preregisterAssertion( d_assertions
[i
] );
3541 if (options::solveIntAsBV() > 0) {
3542 Chat() << "converting ints to bit-vectors..." << endl
;
3543 hash_map
<Node
, Node
, NodeHashFunction
> cache
;
3544 for(unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
3545 d_assertions
.replace(i
, intToBV(d_assertions
[i
], cache
));
3549 if (options::bitblastMode() == theory::bv::BITBLAST_MODE_EAGER
&&
3550 !d_smt
.d_logic
.isPure(THEORY_BV
)) {
3551 // && d_smt.d_logic.getLogicString() != "QF_UFBV")
3552 throw ModalException("Eager bit-blasting does not currently support theory combination. "
3553 "Note that in a QF_BV problem UF symbols can be introduced for division. "
3554 "Try --bv-div-zero-const to interpret division by zero as a constant.");
3557 if (options::bitblastMode() == theory::bv::BITBLAST_MODE_EAGER
) {
3558 d_smt
.d_theoryEngine
->mkAckermanizationAsssertions(d_assertions
.ref());
3561 if ( options::bvAbstraction() &&
3562 !options::incrementalSolving()) {
3563 dumpAssertions("pre-bv-abstraction", d_assertions
);
3565 dumpAssertions("post-bv-abstraction", d_assertions
);
3568 dumpAssertions("pre-boolean-terms", d_assertions
);
3570 Chat() << "rewriting Boolean terms..." << endl
;
3571 for(unsigned i
= 0, i_end
= d_assertions
.size(); i
!= i_end
; ++i
) {
3572 d_assertions
.replace(i
, rewriteBooleanTerms(d_assertions
[i
]));
3575 dumpAssertions("post-boolean-terms", d_assertions
);
3577 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3579 dumpAssertions("pre-constrain-subtypes", d_assertions
);
3581 // Any variables of subtype types need to be constrained properly.
3582 // Careful, here: constrainSubtypes() adds to the back of
3583 // d_assertions, but we don't need to reprocess those.
3584 // We also can't use an iterator, because the vector may be moved in
3585 // memory during this loop.
3586 Chat() << "constraining subtypes..." << endl
;
3587 for(unsigned i
= 0, i_end
= d_assertions
.size(); i
!= i_end
; ++i
) {
3588 constrainSubtypes(d_assertions
[i
], d_assertions
);
3591 dumpAssertions("post-constrain-subtypes", d_assertions
);
3593 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3595 bool noConflict
= true;
3597 // Unconstrained simplification
3598 if(options::unconstrainedSimp()) {
3599 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : pre-unconstrained-simp" << endl
;
3600 dumpAssertions("pre-unconstrained-simp", d_assertions
);
3601 Chat() << "...doing unconstrained simplification..." << endl
;
3602 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
3603 d_assertions
.replace(i
, Rewriter::rewrite(d_assertions
[i
]));
3605 unconstrainedSimp();
3606 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : post-unconstrained-simp" << endl
;
3607 dumpAssertions("post-unconstrained-simp", d_assertions
);
3610 if(options::bvIntroducePow2()){
3611 theory::bv::BVIntroducePow2::pow2Rewrite(d_assertions
.ref());
3614 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : pre-substitution" << endl
;
3615 dumpAssertions("pre-substitution", d_assertions
);
3617 if(options::unsatCores()) {
3618 // special rewriting pass for unsat cores, since many of the passes below are skipped
3619 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
3620 d_assertions
.replace(i
, Rewriter::rewrite(d_assertions
[i
]));
3623 // Apply the substitutions we already have, and normalize
3624 if(!options::unsatCores()) {
3625 Chat() << "applying substitutions..." << endl
;
3626 Trace("simplify") << "SmtEnginePrivate::nonClausalSimplify(): "
3627 << "applying substitutions" << endl
;
3628 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
3629 Trace("simplify") << "applying to " << d_assertions
[i
] << endl
;
3630 spendResource(options::preprocessStep());
3631 d_assertions
.replace(i
, Rewriter::rewrite(d_topLevelSubstitutions
.apply(d_assertions
[i
])));
3632 Trace("simplify") << " got " << d_assertions
[i
] << endl
;
3636 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : post-substitution" << endl
;
3637 dumpAssertions("post-substitution", d_assertions
);
3639 // Assertions ARE guaranteed to be rewritten by this point
3641 // Lift bit-vectors of size 1 to bool
3642 if(options::bitvectorToBool()) {
3643 dumpAssertions("pre-bv-to-bool", d_assertions
);
3644 Chat() << "...doing bvToBool..." << endl
;
3646 dumpAssertions("post-bv-to-bool", d_assertions
);
3647 Trace("smt") << "POST bvToBool" << endl
;
3649 if( d_smt
.d_logic
.isTheoryEnabled(THEORY_STRINGS
) ) {
3650 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : pre-strings-preprocess" << endl
;
3651 dumpAssertions("pre-strings-pp", d_assertions
);
3652 if( !options::stringLazyPreproc() ){
3653 ((theory::strings::TheoryStrings
*)d_smt
.d_theoryEngine
->theoryOf(THEORY_STRINGS
))->getPreprocess()->simplify( d_assertions
.ref() );
3655 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : post-strings-preprocess" << endl
;
3656 dumpAssertions("post-strings-pp", d_assertions
);
3658 if( d_smt
.d_logic
.isQuantified() ){
3659 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : pre-quant-preprocess" << endl
;
3660 //remove rewrite rules
3661 for( unsigned i
=0; i
< d_assertions
.size(); i
++ ) {
3662 if( d_assertions
[i
].getKind() == kind::REWRITE_RULE
){
3663 Node prev
= d_assertions
[i
];
3664 Trace("quantifiers-rewrite-debug") << "Rewrite rewrite rule " << prev
<< "..." << std::endl
;
3665 d_assertions
.replace(i
, Rewriter::rewrite( quantifiers::QuantifiersRewriter::rewriteRewriteRule( d_assertions
[i
] ) ) );
3666 Trace("quantifiers-rewrite") << "*** rr-rewrite " << prev
<< endl
;
3667 Trace("quantifiers-rewrite") << " ...got " << d_assertions
[i
] << endl
;
3671 dumpAssertions("pre-skolem-quant", d_assertions
);
3672 if( options::preSkolemQuant() ){
3673 //apply pre-skolemization to existential quantifiers
3674 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
3675 Node prev
= d_assertions
[i
];
3676 Trace("quantifiers-rewrite-debug") << "Pre-skolemize " << prev
<< "..." << std::endl
;
3677 vector
< TypeNode
> fvTypes
;
3678 vector
< TNode
> fvs
;
3679 d_assertions
.replace(i
, quantifiers::QuantifiersRewriter::preSkolemizeQuantifiers( prev
, true, fvTypes
, fvs
));
3680 if( prev
!=d_assertions
[i
] ){
3681 d_assertions
.replace(i
, Rewriter::rewrite( d_assertions
[i
] ));
3682 Trace("quantifiers-rewrite") << "*** Pre-skolemize " << prev
<< endl
;
3683 Trace("quantifiers-rewrite") << " ...got " << d_assertions
[i
] << endl
;
3687 dumpAssertions("post-skolem-quant", d_assertions
);
3688 if( options::macrosQuant() ){
3689 //quantifiers macro expansion
3690 quantifiers::QuantifierMacros
qm( d_smt
.d_theoryEngine
->getQuantifiersEngine() );
3693 success
= qm
.simplify( d_assertions
.ref(), true );
3695 //finalize the definitions
3696 qm
.finalizeDefinitions();
3699 //fmf-fun : assume admissible functions, applying preprocessing reduction to FMF
3700 if( options::fmfFunWellDefined() ){
3701 quantifiers::FunDefFmf fdf
;
3702 //must carry over current definitions (for incremental)
3703 for( SmtEngine::TypeNodeMap::const_iterator fit
= d_smt
.d_fmfRecFunctionsAbs
->begin(); fit
!= d_smt
.d_fmfRecFunctionsAbs
->end(); ++fit
){
3704 Node f
= (*fit
).first
;
3705 TypeNode ft
= (*fit
).second
;
3706 fdf
.d_sorts
[f
] = ft
;
3707 SmtEngine::NodeListMap::const_iterator fcit
= d_smt
.d_fmfRecFunctionsConcrete
->find( f
);
3708 Assert( fcit
!=d_smt
.d_fmfRecFunctionsConcrete
->end() );
3709 SmtEngine::NodeList
* cl
= (*fcit
).second
;
3710 for( SmtEngine::NodeList::const_iterator cit
= cl
->begin(); cit
!= cl
->end(); ++cit
){
3711 fdf
.d_input_arg_inj
[f
].push_back( *cit
);
3714 fdf
.simplify( d_assertions
.ref() );
3715 //must store new definitions (for incremental)
3716 for( unsigned i
=0; i
<fdf
.d_funcs
.size(); i
++ ){
3717 Node f
= fdf
.d_funcs
[i
];
3718 d_smt
.d_fmfRecFunctionsAbs
->insert( f
, fdf
.d_sorts
[f
] );
3719 SmtEngine::NodeList
* cl
= new(true) SmtEngine::NodeList( d_smt
.d_userContext
);
3720 for( unsigned j
=0; j
<fdf
.d_input_arg_inj
[f
].size(); j
++ ){
3721 cl
->push_back( fdf
.d_input_arg_inj
[f
][j
] );
3723 d_smt
.d_fmfRecFunctionsConcrete
->insert( f
, cl
);
3726 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : post-quant-preprocess" << endl
;
3729 if( options::sortInference() || options::ufssFairnessMonotone() ){
3730 //sort inference technique
3731 SortInference
* si
= d_smt
.d_theoryEngine
->getSortInference();
3732 si
->simplify( d_assertions
.ref(), options::sortInference(), options::ufssFairnessMonotone() );
3733 for( std::map
< Node
, Node
>::iterator it
= si
->d_model_replace_f
.begin(); it
!= si
->d_model_replace_f
.end(); ++it
){
3734 d_smt
.setPrintFuncInModel( it
->first
.toExpr(), false );
3735 d_smt
.setPrintFuncInModel( it
->second
.toExpr(), true );
3739 if( options::pbRewrites() ){
3740 d_pbsProcessor
.learn(d_assertions
.ref());
3741 if(d_pbsProcessor
.likelyToHelp()){
3742 d_pbsProcessor
.applyReplacements(d_assertions
.ref());
3746 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : pre-simplify" << endl
;
3747 dumpAssertions("pre-simplify", d_assertions
);
3748 Chat() << "simplifying assertions..." << endl
;
3749 noConflict
= simplifyAssertions();
3751 ++(d_smt
.d_stats
->d_simplifiedToFalse
);
3753 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : post-simplify" << endl
;
3754 dumpAssertions("post-simplify", d_assertions
);
3756 dumpAssertions("pre-static-learning", d_assertions
);
3757 if(options::doStaticLearning()) {
3758 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : pre-static-learning" << endl
;
3759 // Perform static learning
3760 Chat() << "doing static learning..." << endl
;
3761 Trace("simplify") << "SmtEnginePrivate::simplify(): "
3762 << "performing static learning" << endl
;
3764 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : post-static-learning" << endl
;
3766 dumpAssertions("post-static-learning", d_assertions
);
3768 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3771 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : pre-ite-removal" << endl
;
3772 dumpAssertions("pre-ite-removal", d_assertions
);
3774 Chat() << "removing term ITEs..." << endl
;
3775 TimerStat::CodeTimer
codeTimer(d_smt
.d_stats
->d_iteRemovalTime
);
3776 // Remove ITEs, updating d_iteSkolemMap
3777 d_smt
.d_stats
->d_numAssertionsPre
+= d_assertions
.size();
3779 d_smt
.d_stats
->d_numAssertionsPost
+= d_assertions
.size();
3781 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : post-ite-removal" << endl
;
3782 dumpAssertions("post-ite-removal", d_assertions
);
3784 dumpAssertions("pre-repeat-simplify", d_assertions
);
3785 if(options::repeatSimp()) {
3786 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : pre-repeat-simplify" << endl
;
3787 Chat() << "re-simplifying assertions..." << endl
;
3788 ScopeCounter
depth(d_simplifyAssertionsDepth
);
3789 noConflict
&= simplifyAssertions();
3791 // Need to fix up assertion list to maintain invariants:
3792 // Let Sk be the set of Skolem variables introduced by ITE's. Let <_sk be the order in which these variables were introduced
3793 // during ite removal.
3794 // For each skolem variable sk, let iteExpr = iteMap(sk) be the ite expr mapped to by sk.
3796 // cache for expression traversal
3797 hash_map
<Node
, bool, NodeHashFunction
> cache
;
3799 // First, find all skolems that appear in the substitution map - their associated iteExpr will need
3800 // to be moved to the main assertion set
3801 set
<TNode
> skolemSet
;
3802 SubstitutionMap::iterator pos
= d_topLevelSubstitutions
.begin();
3803 for (; pos
!= d_topLevelSubstitutions
.end(); ++pos
) {
3804 collectSkolems((*pos
).first
, skolemSet
, cache
);
3805 collectSkolems((*pos
).second
, skolemSet
, cache
);
3808 // We need to ensure:
3809 // 1. iteExpr has the form (ite cond (sk = t) (sk = e))
3810 // 2. if some sk' in Sk appears in cond, t, or e, then sk' <_sk sk
3811 // If either of these is violated, we must add iteExpr as a proper assertion
3812 IteSkolemMap::iterator it
= d_iteSkolemMap
.begin();
3813 IteSkolemMap::iterator iend
= d_iteSkolemMap
.end();
3814 NodeBuilder
<> builder(kind::AND
);
3815 builder
<< d_assertions
[d_realAssertionsEnd
- 1];
3816 vector
<TNode
> toErase
;
3817 for (; it
!= iend
; ++it
) {
3818 if (skolemSet
.find((*it
).first
) == skolemSet
.end()) {
3819 TNode iteExpr
= d_assertions
[(*it
).second
];
3820 if (iteExpr
.getKind() == kind::ITE
&&
3821 iteExpr
[1].getKind() == kind::EQUAL
&&
3822 iteExpr
[1][0] == (*it
).first
&&
3823 iteExpr
[2].getKind() == kind::EQUAL
&&
3824 iteExpr
[2][0] == (*it
).first
) {
3826 bool bad
= checkForBadSkolems(iteExpr
[0], (*it
).first
, cache
);
3827 bad
= bad
|| checkForBadSkolems(iteExpr
[1][1], (*it
).first
, cache
);
3828 bad
= bad
|| checkForBadSkolems(iteExpr
[2][1], (*it
).first
, cache
);
3834 // Move this iteExpr into the main assertions
3835 builder
<< d_assertions
[(*it
).second
];
3836 d_assertions
[(*it
).second
] = NodeManager::currentNM()->mkConst
<bool>(true);
3837 toErase
.push_back((*it
).first
);
3839 if(builder
.getNumChildren() > 1) {
3840 while (!toErase
.empty()) {
3841 d_iteSkolemMap
.erase(toErase
.back());
3844 d_assertions
[d_realAssertionsEnd
- 1] = Rewriter::rewrite(Node(builder
));
3846 // For some reason this is needed for some benchmarks, such as
3847 // http://cvc4.cs.nyu.edu/benchmarks/smtlib2/QF_AUFBV/dwp_formulas/try5_small_difret_functions_dwp_tac.re_node_set_remove_at.il.dwp.smt2
3848 // Figure it out later
3850 // Assert(iteRewriteAssertionsEnd == d_assertions.size());
3852 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : post-repeat-simplify" << endl
;
3854 dumpAssertions("post-repeat-simplify", d_assertions
);
3856 dumpAssertions("pre-rewrite-apply-to-const", d_assertions
);
3857 if(options::rewriteApplyToConst()) {
3858 Chat() << "Rewriting applies to constants..." << endl
;
3859 TimerStat::CodeTimer
codeTimer(d_smt
.d_stats
->d_rewriteApplyToConstTime
);
3860 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
3861 d_assertions
[i
] = Rewriter::rewrite(rewriteApplyToConst(d_assertions
[i
]));
3864 dumpAssertions("post-rewrite-apply-to-const", d_assertions
);
3866 // begin: INVARIANT to maintain: no reordering of assertions or
3867 // introducing new ones
3868 #ifdef CVC4_ASSERTIONS
3869 unsigned iteRewriteAssertionsEnd
= d_assertions
.size();
3872 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3874 Debug("smt") << "SmtEnginePrivate::processAssertions() POST SIMPLIFICATION" << endl
;
3875 Debug("smt") << " d_assertions : " << d_assertions
.size() << endl
;
3877 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : pre-theory-preprocessing" << endl
;
3878 dumpAssertions("pre-theory-preprocessing", d_assertions
);
3880 Chat() << "theory preprocessing..." << endl
;
3881 TimerStat::CodeTimer
codeTimer(d_smt
.d_stats
->d_theoryPreprocessTime
);
3882 // Call the theory preprocessors
3883 d_smt
.d_theoryEngine
->preprocessStart();
3884 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
3885 d_assertions
.replace(i
, d_smt
.d_theoryEngine
->preprocess(d_assertions
[i
]));
3888 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() : post-theory-preprocessing" << endl
;
3889 dumpAssertions("post-theory-preprocessing", d_assertions
);
3891 // If we are using eager bit-blasting wrap assertions in fake atom so that
3892 // everything gets bit-blasted to internal SAT solver
3893 if (options::bitblastMode() == theory::bv::BITBLAST_MODE_EAGER
) {
3894 for (unsigned i
= 0; i
< d_assertions
.size(); ++i
) {
3895 TNode atom
= d_assertions
[i
];
3896 Node eager_atom
= NodeManager::currentNM()->mkNode(kind::BITVECTOR_EAGER_ATOM
, atom
);
3897 d_assertions
.replace(i
, eager_atom
);
3898 TheoryModel
* m
= d_smt
.d_theoryEngine
->getModel();
3899 m
->addSubstitution(eager_atom
, atom
);
3903 // Push the formula to decision engine
3905 Chat() << "pushing to decision engine..." << endl
;
3906 Assert(iteRewriteAssertionsEnd
== d_assertions
.size());
3907 d_smt
.d_decisionEngine
->addAssertions
3908 (d_assertions
.ref(), d_realAssertionsEnd
, d_iteSkolemMap
);
3911 // end: INVARIANT to maintain: no reordering of assertions or
3912 // introducing new ones
3914 Trace("smt-proc") << "SmtEnginePrivate::processAssertions() end" << endl
;
3915 dumpAssertions("post-everything", d_assertions
);
3917 //set instantiation level of everything to zero
3918 if( options::instLevelInputOnly() && options::instMaxLevel()!=-1 ){
3919 for( unsigned i
=0; i
< d_assertions
.size(); i
++ ) {
3920 theory::QuantifiersEngine::setInstantiationLevelAttr( d_assertions
[i
], 0 );
3924 // Push the formula to SAT
3926 Chat() << "converting to CNF..." << endl
;
3927 TimerStat::CodeTimer
codeTimer(d_smt
.d_stats
->d_cnfConversionTime
);
3928 for (unsigned i
= 0; i
< d_assertions
.size(); ++ i
) {
3929 Chat() << "+ " << d_assertions
[i
] << std::endl
;
3930 d_smt
.d_propEngine
->assertFormula(d_assertions
[i
]);
3934 d_assertionsProcessed
= true;
3936 d_assertions
.clear();
3937 d_iteSkolemMap
.clear();
3940 void SmtEnginePrivate::addFormula(TNode n
, bool inUnsatCore
, bool inInput
)
3941 throw(TypeCheckingException
, LogicException
) {
3948 Trace("smt") << "SmtEnginePrivate::addFormula(" << n
<< "), inUnsatCore = " << inUnsatCore
<< ", inInput = " << inInput
<< endl
;
3949 // Give it to proof manager
3952 // n is an input assertion
3953 if (inUnsatCore
|| options::dumpUnsatCores() || options::checkUnsatCores())
3954 ProofManager::currentPM()->addCoreAssertion(n
.toExpr());
3956 // n is the result of an unknown preprocessing step, add it to dependency map to null
3957 ProofManager::currentPM()->addDependence(n
, Node::null());
3959 // rewrite rules are by default in the unsat core because
3960 // they need to be applied until saturation
3961 if(options::unsatCores() &&
3962 n
.getKind() == kind::REWRITE_RULE
){
3963 ProofManager::currentPM()->addUnsatCore(n
.toExpr());
3967 // Add the normalized formula to the queue
3968 d_assertions
.push_back(n
);
3969 //d_assertions.push_back(Rewriter::rewrite(n));
3972 void SmtEngine::ensureBoolean(const Expr
& e
) throw(TypeCheckingException
) {
3973 Type type
= e
.getType(options::typeChecking());
3974 Type boolType
= d_exprManager
->booleanType();
3975 if(type
!= boolType
) {
3977 ss
<< "Expected " << boolType
<< "\n"
3978 << "The assertion : " << e
<< "\n"
3979 << "Its type : " << type
;
3980 throw TypeCheckingException(e
, ss
.str());
3984 Result
SmtEngine::checkSat(const Expr
& ex
, bool inUnsatCore
) throw(TypeCheckingException
, ModalException
, LogicException
) {
3986 Assert(ex
.isNull() || ex
.getExprManager() == d_exprManager
);
3987 SmtScope
smts(this);
3988 finalOptionsAreSet();
3991 Trace("smt") << "SmtEngine::checkSat(" << ex
<< ")" << endl
;
3993 if(d_queryMade
&& !options::incrementalSolving()) {
3994 throw ModalException("Cannot make multiple queries unless "
3995 "incremental solving is enabled "
3996 "(try --incremental)");
4001 // Substitute out any abstract values in ex.
4002 e
= d_private
->substituteAbstractValues(Node::fromExpr(ex
)).toExpr();
4003 // Ensure expr is type-checked at this point.
4007 // check to see if a postsolve() is pending
4008 if(d_needPostsolve
) {
4009 d_theoryEngine
->postsolve();
4010 d_needPostsolve
= false;
4016 // Note that a query has been made
4021 d_problemExtended
= true;
4022 if(d_assertionList
!= NULL
) {
4023 d_assertionList
->push_back(e
);
4025 d_private
->addFormula(e
.getNode(), inUnsatCore
);
4028 Result
r(Result::SAT_UNKNOWN
, Result::UNKNOWN_REASON
);
4029 r
= check().asSatisfiabilityResult();
4031 if (options::solveIntAsBV() > 0 &&r
.asSatisfiabilityResult().isSat() == Result::UNSAT
) {
4032 r
= Result(Result::SAT_UNKNOWN
, Result::UNKNOWN_REASON
);
4035 d_needPostsolve
= true;
4037 // Dump the query if requested
4038 if(Dump
.isOn("benchmark")) {
4039 // the expr already got dumped out if assertion-dumping is on
4040 Dump("benchmark") << CheckSatCommand(ex
);
4046 // Remember the status
4049 d_problemExtended
= false;
4051 Trace("smt") << "SmtEngine::checkSat(" << e
<< ") => " << r
<< endl
;
4053 // Check that SAT results generate a model correctly.
4054 if(options::checkModels()) {
4055 if(r
.asSatisfiabilityResult().isSat() == Result::SAT
||
4056 (r
.isUnknown() && r
.whyUnknown() == Result::INCOMPLETE
) ){
4057 checkModel(/* hard failure iff */ ! r
.isUnknown());
4060 // Check that UNSAT results generate a proof correctly.
4061 if(options::checkProofs()) {
4062 if(r
.asSatisfiabilityResult().isSat() == Result::UNSAT
) {
4063 TimerStat::CodeTimer
checkProofTimer(d_stats
->d_checkProofTime
);
4067 // Check that UNSAT results generate an unsat core correctly.
4068 if(options::checkUnsatCores()) {
4069 if(r
.asSatisfiabilityResult().isSat() == Result::UNSAT
) {
4070 TimerStat::CodeTimer
checkUnsatCoreTimer(d_stats
->d_checkUnsatCoreTime
);
4076 } catch (UnsafeInterruptException
& e
) {
4077 AlwaysAssert(d_private
->getResourceManager()->out());
4078 Result::UnknownExplanation why
= d_private
->getResourceManager()->outOfResources() ?
4079 Result::RESOURCEOUT
: Result::TIMEOUT
;
4080 return Result(Result::SAT_UNKNOWN
, why
, d_filename
);
4082 }/* SmtEngine::checkSat() */
4084 Result
SmtEngine::query(const Expr
& ex
, bool inUnsatCore
) throw(TypeCheckingException
, ModalException
, LogicException
) {
4085 Assert(!ex
.isNull());
4086 Assert(ex
.getExprManager() == d_exprManager
);
4087 SmtScope
smts(this);
4088 finalOptionsAreSet();
4090 Trace("smt") << "SMT query(" << ex
<< ")" << endl
;
4093 if(d_queryMade
&& !options::incrementalSolving()) {
4094 throw ModalException("Cannot make multiple queries unless "
4095 "incremental solving is enabled "
4096 "(try --incremental)");
4099 // Substitute out any abstract values in ex
4100 Expr e
= d_private
->substituteAbstractValues(Node::fromExpr(ex
)).toExpr();
4101 // Ensure that the expression is type-checked at this point, and Boolean
4104 // check to see if a postsolve() is pending
4105 if(d_needPostsolve
) {
4106 d_theoryEngine
->postsolve();
4107 d_needPostsolve
= false;
4113 // Note that a query has been made
4117 d_problemExtended
= true;
4118 if(d_assertionList
!= NULL
) {
4119 d_assertionList
->push_back(e
.notExpr());
4121 d_private
->addFormula(e
.getNode().notNode(), inUnsatCore
);
4124 Result
r(Result::SAT_UNKNOWN
, Result::UNKNOWN_REASON
);
4125 r
= check().asValidityResult();
4126 d_needPostsolve
= true;
4128 // Dump the query if requested
4129 if(Dump
.isOn("benchmark")) {
4130 // the expr already got dumped out if assertion-dumping is on
4131 Dump("benchmark") << QueryCommand(ex
);
4137 // Remember the status
4140 d_problemExtended
= false;
4142 Trace("smt") << "SMT query(" << e
<< ") ==> " << r
<< endl
;
4144 // Check that SAT results generate a model correctly.
4145 if(options::checkModels()) {
4146 if(r
.asSatisfiabilityResult().isSat() == Result::SAT
||
4147 (r
.isUnknown() && r
.whyUnknown() == Result::INCOMPLETE
) ){
4148 checkModel(/* hard failure iff */ ! r
.isUnknown());
4151 // Check that UNSAT results generate a proof correctly.
4152 if(options::checkProofs()) {
4153 if(r
.asSatisfiabilityResult().isSat() == Result::UNSAT
) {
4154 TimerStat::CodeTimer
checkProofTimer(d_stats
->d_checkProofTime
);
4158 // Check that UNSAT results generate an unsat core correctly.
4159 if(options::checkUnsatCores()) {
4160 if(r
.asSatisfiabilityResult().isSat() == Result::UNSAT
) {
4161 TimerStat::CodeTimer
checkUnsatCoreTimer(d_stats
->d_checkUnsatCoreTime
);
4167 } catch (UnsafeInterruptException
& e
) {
4168 AlwaysAssert(d_private
->getResourceManager()->out());
4169 Result::UnknownExplanation why
= d_private
->getResourceManager()->outOfResources() ?
4170 Result::RESOURCEOUT
: Result::TIMEOUT
;
4171 return Result(Result::VALIDITY_UNKNOWN
, why
, d_filename
);
4173 }/* SmtEngine::query() */
4175 Result
SmtEngine::assertFormula(const Expr
& ex
, bool inUnsatCore
) throw(TypeCheckingException
, LogicException
, UnsafeInterruptException
) {
4176 Assert(ex
.getExprManager() == d_exprManager
);
4177 SmtScope
smts(this);
4178 finalOptionsAreSet();
4181 Trace("smt") << "SmtEngine::assertFormula(" << ex
<< ")" << endl
;
4183 // Substitute out any abstract values in ex
4184 Expr e
= d_private
->substituteAbstractValues(Node::fromExpr(ex
)).toExpr();
4187 if(d_assertionList
!= NULL
) {
4188 d_assertionList
->push_back(e
);
4190 d_private
->addFormula(e
.getNode(), inUnsatCore
);
4191 return quickCheck().asValidityResult();
4192 }/* SmtEngine::assertFormula() */
4194 Node
SmtEngine::postprocess(TNode node
, TypeNode expectedType
) const {
4195 ModelPostprocessor mpost
;
4196 NodeVisitor
<ModelPostprocessor
> visitor
;
4197 Node value
= visitor
.run(mpost
, node
);
4198 Debug("boolean-terms") << "postproc: got " << value
<< " expect type " << expectedType
<< endl
;
4199 Node realValue
= mpost
.rewriteAs(value
, expectedType
);
4200 Debug("boolean-terms") << "postproc: realval " << realValue
<< " expect type " << expectedType
<< endl
;
4201 if(options::condenseFunctionValues()) {
4202 realValue
= Rewriter::rewrite(realValue
);
4203 Debug("boolean-terms") << "postproc: after rewrite " << realValue
<< endl
;
4208 Expr
SmtEngine::simplify(const Expr
& ex
) throw(TypeCheckingException
, LogicException
, UnsafeInterruptException
) {
4209 Assert(ex
.getExprManager() == d_exprManager
);
4210 SmtScope
smts(this);
4211 finalOptionsAreSet();
4213 Trace("smt") << "SMT simplify(" << ex
<< ")" << endl
;
4215 if(Dump
.isOn("benchmark")) {
4216 Dump("benchmark") << SimplifyCommand(ex
);
4219 Expr e
= d_private
->substituteAbstractValues(Node::fromExpr(ex
)).toExpr();
4220 if( options::typeChecking() ) {
4221 e
.getType(true); // ensure expr is type-checked at this point
4224 // Make sure all preprocessing is done
4225 d_private
->processAssertions();
4226 Node n
= d_private
->simplify(Node::fromExpr(e
));
4227 n
= postprocess(n
, TypeNode::fromType(e
.getType()));
4231 Expr
SmtEngine::expandDefinitions(const Expr
& ex
) throw(TypeCheckingException
, LogicException
, UnsafeInterruptException
) {
4232 d_private
->spendResource(options::preprocessStep());
4234 Assert(ex
.getExprManager() == d_exprManager
);
4235 SmtScope
smts(this);
4236 finalOptionsAreSet();
4238 Trace("smt") << "SMT expandDefinitions(" << ex
<< ")" << endl
;
4240 // Substitute out any abstract values in ex.
4241 Expr e
= d_private
->substituteAbstractValues(Node::fromExpr(ex
)).toExpr();
4242 if(options::typeChecking()) {
4243 // Ensure expr is type-checked at this point.
4246 if(Dump
.isOn("benchmark")) {
4247 Dump("benchmark") << ExpandDefinitionsCommand(e
);
4249 hash_map
<Node
, Node
, NodeHashFunction
> cache
;
4250 Node n
= d_private
->expandDefinitions(Node::fromExpr(e
), cache
, /* expandOnly = */ true);
4251 n
= postprocess(n
, TypeNode::fromType(e
.getType()));
4256 Expr
SmtEngine::getValue(const Expr
& ex
) const throw(ModalException
, TypeCheckingException
, LogicException
, UnsafeInterruptException
) {
4257 Assert(ex
.getExprManager() == d_exprManager
);
4258 SmtScope
smts(this);
4260 Trace("smt") << "SMT getValue(" << ex
<< ")" << endl
;
4261 if(Dump
.isOn("benchmark")) {
4262 Dump("benchmark") << GetValueCommand(ex
);
4265 if(!options::produceModels()) {
4267 "Cannot get value when produce-models options is off.";
4268 throw ModalException(msg
);
4270 if(d_status
.isNull() ||
4271 d_status
.asSatisfiabilityResult() == Result::UNSAT
||
4272 d_problemExtended
) {
4274 "Cannot get value unless immediately preceded by SAT/INVALID or UNKNOWN response.";
4275 throw ModalException(msg
);
4278 // Substitute out any abstract values in ex.
4279 Expr e
= d_private
->substituteAbstractValues(Node::fromExpr(ex
)).toExpr();
4281 // Ensure expr is type-checked at this point.
4282 e
.getType(options::typeChecking());
4284 // do not need to apply preprocessing substitutions (should be recorded
4285 // in model already)
4287 Node n
= Node::fromExpr(e
);
4288 Trace("smt") << "--- getting value of " << n
<< endl
;
4289 TypeNode expectedType
= n
.getType();
4291 // Expand, then normalize
4292 hash_map
<Node
, Node
, NodeHashFunction
> cache
;
4293 n
= d_private
->expandDefinitions(n
, cache
);
4294 // There are two ways model values for terms are computed (for historical
4295 // reasons). One way is that used in check-model; the other is that
4296 // used by the Model classes. It's not clear to me exactly how these
4297 // two are different, but they need to be unified. This ugly hack here
4298 // is to fix bug 554 until we can revamp boolean-terms and models [MGD]
4299 if(!n
.getType().isFunction()) {
4300 n
= d_private
->rewriteBooleanTerms(n
);
4301 n
= Rewriter::rewrite(n
);
4304 Trace("smt") << "--- getting value of " << n
<< endl
;
4305 TheoryModel
* m
= d_theoryEngine
->getModel();
4308 resultNode
= m
->getValue(n
);
4310 Trace("smt") << "--- got value " << n
<< " = " << resultNode
<< endl
;
4311 resultNode
= postprocess(resultNode
, expectedType
);
4312 Trace("smt") << "--- model-post returned " << resultNode
<< endl
;
4313 Trace("smt") << "--- model-post returned " << resultNode
.getType() << endl
;
4314 Trace("smt") << "--- model-post expected " << expectedType
<< endl
;
4316 // type-check the result we got
4317 Assert(resultNode
.isNull() || resultNode
.getType().isSubtypeOf(expectedType
),
4318 "Run with -t smt for details.");
4320 // ensure it's a constant
4321 Assert(resultNode
.getKind() == kind::LAMBDA
|| resultNode
.isConst());
4323 if(options::abstractValues() && resultNode
.getType().isArray()) {
4324 resultNode
= d_private
->mkAbstractValue(resultNode
);
4325 Trace("smt") << "--- abstract value >> " << resultNode
<< endl
;
4328 return resultNode
.toExpr();
4331 bool SmtEngine::addToAssignment(const Expr
& ex
) throw() {
4332 SmtScope
smts(this);
4333 finalOptionsAreSet();
4335 // Substitute out any abstract values in ex
4336 Expr e
= d_private
->substituteAbstractValues(Node::fromExpr(ex
)).toExpr();
4337 Type type
= e
.getType(options::typeChecking());
4339 PrettyCheckArgument(
4340 type
.isBoolean(), e
,
4341 "expected Boolean-typed variable or function application "
4342 "in addToAssignment()" );
4343 Node n
= e
.getNode();
4344 // must be an APPLY of a zero-ary defined function, or a variable
4345 PrettyCheckArgument(
4346 ( ( n
.getKind() == kind::APPLY
&&
4347 ( d_definedFunctions
->find(n
.getOperator()) !=
4348 d_definedFunctions
->end() ) &&
4349 n
.getNumChildren() == 0 ) ||
4351 "expected variable or defined-function application "
4352 "in addToAssignment(),\ngot %s", e
.toString().c_str() );
4353 if(!options::produceAssignments()) {
4356 if(d_assignments
== NULL
) {
4357 d_assignments
= new(true) AssignmentSet(d_context
);
4359 d_assignments
->insert(n
);
4364 CVC4::SExpr
SmtEngine::getAssignment() throw(ModalException
, UnsafeInterruptException
) {
4365 Trace("smt") << "SMT getAssignment()" << endl
;
4366 SmtScope
smts(this);
4367 finalOptionsAreSet();
4368 if(Dump
.isOn("benchmark")) {
4369 Dump("benchmark") << GetAssignmentCommand();
4371 if(!options::produceAssignments()) {
4373 "Cannot get the current assignment when "
4374 "produce-assignments option is off.";
4375 throw ModalException(msg
);
4377 if(d_status
.isNull() ||
4378 d_status
.asSatisfiabilityResult() == Result::UNSAT
||
4379 d_problemExtended
) {
4381 "Cannot get the current assignment unless immediately "
4382 "preceded by SAT/INVALID or UNKNOWN response.";
4383 throw ModalException(msg
);
4386 if(d_assignments
== NULL
) {
4387 return SExpr(vector
<SExpr
>());
4390 vector
<SExpr
> sexprs
;
4391 TypeNode boolType
= d_nodeManager
->booleanType();
4392 TheoryModel
* m
= d_theoryEngine
->getModel();
4393 for(AssignmentSet::key_iterator i
= d_assignments
->key_begin(),
4394 iend
= d_assignments
->key_end();
4397 Assert((*i
).getType() == boolType
);
4399 Trace("smt") << "--- getting value of " << *i
<< endl
;
4401 // Expand, then normalize
4402 hash_map
<Node
, Node
, NodeHashFunction
> cache
;
4403 Node n
= d_private
->expandDefinitions(*i
, cache
);
4404 n
= d_private
->rewriteBooleanTerms(n
);
4405 n
= Rewriter::rewrite(n
);
4407 Trace("smt") << "--- getting value of " << n
<< endl
;
4410 resultNode
= m
->getValue(n
);
4413 // type-check the result we got
4414 Assert(resultNode
.isNull() || resultNode
.getType() == boolType
);
4416 // ensure it's a constant
4417 Assert(resultNode
.isConst());
4420 if((*i
).getKind() == kind::APPLY
) {
4421 Assert((*i
).getNumChildren() == 0);
4422 v
.push_back(SExpr(SExpr::Keyword((*i
).getOperator().toString())));
4424 Assert((*i
).isVar());
4425 v
.push_back(SExpr(SExpr::Keyword((*i
).toString())));
4427 v
.push_back(SExpr(SExpr::Keyword(resultNode
.toString())));
4428 sexprs
.push_back(SExpr(v
));
4430 return SExpr(sexprs
);
4433 void SmtEngine::addToModelCommandAndDump(const Command
& c
, uint32_t flags
, bool userVisible
, const char* dumpTag
) {
4434 Trace("smt") << "SMT addToModelCommandAndDump(" << c
<< ")" << endl
;
4435 SmtScope
smts(this);
4436 // If we aren't yet fully inited, the user might still turn on
4437 // produce-models. So let's keep any commands around just in
4438 // case. This is useful in two cases: (1) SMT-LIBv1 auto-declares
4439 // sort "U" in QF_UF before setLogic() is run and we still want to
4440 // support finding card(U) with --finite-model-find, and (2) to
4441 // decouple SmtEngine and ExprManager if the user does a few
4442 // ExprManager::mkSort() before SmtEngine::setOption("produce-models")
4443 // and expects to find their cardinalities in the model.
4444 if(/* userVisible && */
4445 (!d_fullyInited
|| options::produceModels()) &&
4446 (flags
& ExprManager::VAR_FLAG_DEFINED
) == 0) {
4448 if(flags
& ExprManager::VAR_FLAG_GLOBAL
) {
4449 d_modelGlobalCommands
.push_back(c
.clone());
4451 d_modelCommands
->push_back(c
.clone());
4454 if(Dump
.isOn(dumpTag
)) {
4458 d_dumpCommands
.push_back(c
.clone());
4463 Model
* SmtEngine::getModel() throw(ModalException
, UnsafeInterruptException
) {
4464 Trace("smt") << "SMT getModel()" << endl
;
4465 SmtScope
smts(this);
4467 finalOptionsAreSet();
4469 if(Dump
.isOn("benchmark")) {
4470 Dump("benchmark") << GetModelCommand();
4473 if(d_status
.isNull() ||
4474 d_status
.asSatisfiabilityResult() == Result::UNSAT
||
4475 d_problemExtended
) {
4477 "Cannot get the current model unless immediately "
4478 "preceded by SAT/INVALID or UNKNOWN response.";
4479 throw ModalException(msg
);
4481 if(!options::produceModels()) {
4483 "Cannot get model when produce-models options is off.";
4484 throw ModalException(msg
);
4486 TheoryModel
* m
= d_theoryEngine
->getModel();
4487 m
->d_inputName
= d_filename
;
4491 void SmtEngine::checkUnsatCore() {
4492 Assert(options::unsatCores(), "cannot check unsat core if unsat cores are turned off");
4494 Notice() << "SmtEngine::checkUnsatCore(): generating unsat core" << endl
;
4495 UnsatCore core
= getUnsatCore();
4497 SmtEngine
coreChecker(d_exprManager
);
4498 coreChecker
.setLogic(getLogicInfo());
4501 std::vector
<Command
*>::const_iterator itg
= d_defineCommands
.begin();
4502 for (; itg
!= d_defineCommands
.end(); ++itg
) {
4503 (*itg
)->invoke(&coreChecker
);
4507 Notice() << "SmtEngine::checkUnsatCore(): pushing core assertions (size == " << core
.size() << ")" << endl
;
4508 for(UnsatCore::iterator i
= core
.begin(); i
!= core
.end(); ++i
) {
4509 Notice() << "SmtEngine::checkUnsatCore(): pushing core member " << *i
<< endl
;
4510 coreChecker
.assertFormula(*i
);
4512 const bool checkUnsatCores
= options::checkUnsatCores();
4515 options::checkUnsatCores
.set(false);
4516 options::checkProofs
.set(false);
4517 r
= coreChecker
.checkSat();
4519 options::checkUnsatCores
.set(checkUnsatCores
);
4522 Notice() << "SmtEngine::checkUnsatCore(): result is " << r
<< endl
;
4523 if(r
.asSatisfiabilityResult().isUnknown()) {
4524 InternalError("SmtEngine::checkUnsatCore(): could not check core result unknown.");
4527 if(r
.asSatisfiabilityResult().isSat()) {
4528 InternalError("SmtEngine::checkUnsatCore(): produced core was satisfiable.");
4532 void SmtEngine::checkModel(bool hardFailure
) {
4533 // --check-model implies --produce-assertions, which enables the
4534 // assertion list, so we should be ok.
4535 Assert(d_assertionList
!= NULL
, "don't have an assertion list to check in SmtEngine::checkModel()");
4537 TimerStat::CodeTimer
checkModelTimer(d_stats
->d_checkModelTime
);
4539 // Throughout, we use Notice() to give diagnostic output.
4541 // If this function is running, the user gave --check-model (or equivalent),
4542 // and if Notice() is on, the user gave --verbose (or equivalent).
4544 Notice() << "SmtEngine::checkModel(): generating model" << endl
;
4545 TheoryModel
* m
= d_theoryEngine
->getModel();
4547 // Check individual theory assertions
4548 d_theoryEngine
->checkTheoryAssertionsWithModel();
4553 // We have a "fake context" for the substitution map (we don't need it
4554 // to be context-dependent)
4555 context::Context fakeContext
;
4556 SubstitutionMap
substitutions(&fakeContext
, /* substituteUnderQuantifiers = */ false);
4558 for(size_t k
= 0; k
< m
->getNumCommands(); ++k
) {
4559 const DeclareFunctionCommand
* c
= dynamic_cast<const DeclareFunctionCommand
*>(m
->getCommand(k
));
4560 Notice() << "SmtEngine::checkModel(): model command " << k
<< " : " << m
->getCommand(k
) << endl
;
4562 // we don't care about DECLARE-DATATYPES, DECLARE-SORT, ...
4563 Notice() << "SmtEngine::checkModel(): skipping..." << endl
;
4565 // We have a DECLARE-FUN:
4567 // We'll first do some checks, then add to our substitution map
4568 // the mapping: function symbol |-> value
4570 Expr func
= c
->getFunction();
4571 Node val
= m
->getValue(func
);
4573 Notice() << "SmtEngine::checkModel(): adding substitution: " << func
<< " |-> " << val
<< endl
;
4575 // (1) if the value is a lambda, ensure the lambda doesn't contain the
4576 // function symbol (since then the definition is recursive)
4577 if (val
.getKind() == kind::LAMBDA
) {
4578 // first apply the model substitutions we have so far
4579 Debug("boolean-terms") << "applying subses to " << val
[1] << endl
;
4580 Node n
= substitutions
.apply(val
[1]);
4581 Debug("boolean-terms") << "++ got " << n
<< endl
;
4582 // now check if n contains func by doing a substitution
4583 // [func->func2] and checking equality of the Nodes.
4584 // (this just a way to check if func is in n.)
4585 SubstitutionMap
subs(&fakeContext
);
4586 Node func2
= NodeManager::currentNM()->mkSkolem("", TypeNode::fromType(func
.getType()), "", NodeManager::SKOLEM_NO_NOTIFY
);
4587 subs
.addSubstitution(func
, func2
);
4588 if(subs
.apply(n
) != n
) {
4589 Notice() << "SmtEngine::checkModel(): *** PROBLEM: MODEL VALUE DEFINED IN TERMS OF ITSELF ***" << endl
;
4591 ss
<< "SmtEngine::checkModel(): ERRORS SATISFYING ASSERTIONS WITH MODEL:" << endl
4592 << "considering model value for " << func
<< endl
4593 << "body of lambda is: " << val
<< endl
;
4595 ss
<< "body substitutes to: " << n
<< endl
;
4597 ss
<< "so " << func
<< " is defined in terms of itself." << endl
4598 << "Run with `--check-models -v' for additional diagnostics.";
4599 InternalError(ss
.str());
4603 // (2) check that the value is actually a value
4604 else if (!val
.isConst()) {
4605 Notice() << "SmtEngine::checkModel(): *** PROBLEM: MODEL VALUE NOT A CONSTANT ***" << endl
;
4607 ss
<< "SmtEngine::checkModel(): ERRORS SATISFYING ASSERTIONS WITH MODEL:" << endl
4608 << "model value for " << func
<< endl
4609 << " is " << val
<< endl
4610 << "and that is not a constant (.isConst() == false)." << endl
4611 << "Run with `--check-models -v' for additional diagnostics.";
4612 InternalError(ss
.str());
4615 // (3) check that it's the correct (sub)type
4616 // This was intended to be a more general check, but for now we can't do that because
4617 // e.g. "1" is an INT, which isn't a subrange type [1..10] (etc.).
4618 else if(func
.getType().isInteger() && !val
.getType().isInteger()) {
4619 Notice() << "SmtEngine::checkModel(): *** PROBLEM: MODEL VALUE NOT CORRECT TYPE ***" << endl
;
4621 ss
<< "SmtEngine::checkModel(): ERRORS SATISFYING ASSERTIONS WITH MODEL:" << endl
4622 << "model value for " << func
<< endl
4623 << " is " << val
<< endl
4624 << "value type is " << val
.getType() << endl
4625 << "should be of type " << func
.getType() << endl
4626 << "Run with `--check-models -v' for additional diagnostics.";
4627 InternalError(ss
.str());
4630 // (4) checks complete, add the substitution
4631 Debug("boolean-terms") << "cm: adding subs " << func
<< " :=> " << val
<< endl
;
4632 substitutions
.addSubstitution(func
, val
);
4636 // Now go through all our user assertions checking if they're satisfied.
4637 for(AssertionList::const_iterator i
= d_assertionList
->begin(); i
!= d_assertionList
->end(); ++i
) {
4638 Notice() << "SmtEngine::checkModel(): checking assertion " << *i
<< endl
;
4639 Node n
= Node::fromExpr(*i
);
4641 // Apply any define-funs from the problem.
4643 hash_map
<Node
, Node
, NodeHashFunction
> cache
;
4644 n
= d_private
->expandDefinitions(n
, cache
);
4646 Notice() << "SmtEngine::checkModel(): -- expands to " << n
<< endl
;
4648 // Apply our model value substitutions.
4649 Debug("boolean-terms") << "applying subses to " << n
<< endl
;
4650 n
= substitutions
.apply(n
);
4651 Debug("boolean-terms") << "++ got " << n
<< endl
;
4652 Notice() << "SmtEngine::checkModel(): -- substitutes to " << n
<< endl
;
4654 if( n
.getKind() != kind::REWRITE_RULE
){
4655 // In case it's a quantifier (or contains one), look up its value before
4656 // simplifying, or the quantifier might be irreparably altered.
4658 Notice() << "SmtEngine::checkModel(): -- get value : " << n
<< std::endl
;
4660 // Note this "skip" is done here, rather than above. This is
4661 // because (1) the quantifier could in principle simplify to false,
4662 // which should be reported, and (2) checking for the quantifier
4663 // above, before simplification, doesn't catch buried quantifiers
4664 // anyway (those not at the top-level).
4665 Notice() << "SmtEngine::checkModel(): -- skipping rewrite-rules assertion"
4670 // Simplify the result.
4671 n
= d_private
->simplify(n
);
4672 Notice() << "SmtEngine::checkModel(): -- simplifies to " << n
<< endl
;
4674 // Replace the already-known ITEs (this is important for ground ITEs under quantifiers).
4675 n
= d_private
->d_iteRemover
.replace(n
);
4676 Notice() << "SmtEngine::checkModel(): -- ite replacement gives " << n
<< endl
;
4678 // Apply our model value substitutions (again), as things may have been simplified.
4679 Debug("boolean-terms") << "applying subses to " << n
<< endl
;
4680 n
= substitutions
.apply(n
);
4681 Debug("boolean-terms") << "++ got " << n
<< endl
;
4682 Notice() << "SmtEngine::checkModel(): -- re-substitutes to " << n
<< endl
;
4684 // As a last-ditch effort, ask model to simplify it.
4685 // Presently, this is only an issue for quantifiers, which can have a value
4686 // but don't show up in our substitution map above.
4688 Notice() << "SmtEngine::checkModel(): -- model-substitutes to " << n
<< endl
;
4690 if( d_logic
.isQuantified() ){
4691 // AJR: since quantified formulas are not checkable, we assign them to true/false based on the satisfying assignment.
4692 // however, quantified formulas can be modified during preprocess, so they may not correspond to those in the satisfying assignment.
4693 // hence we use a relaxed version of check model here.
4694 // this is necessary until preprocessing passes explicitly record how they rewrite quantified formulas
4695 if( hardFailure
&& !n
.isConst() && n
.getKind() != kind::LAMBDA
){
4696 Notice() << "SmtEngine::checkModel(): -- relax check model wrt quantified formulas..." << endl
;
4697 AlwaysAssert( quantifiers::QuantifiersRewriter::containsQuantifiers( n
) );
4698 Warning() << "Warning : SmtEngine::checkModel(): cannot check simplified assertion : " << n
<< endl
;
4702 AlwaysAssert(!hardFailure
|| n
.isConst() || n
.getKind() == kind::LAMBDA
);
4704 // The result should be == true.
4705 if(n
!= NodeManager::currentNM()->mkConst(true)) {
4706 Notice() << "SmtEngine::checkModel(): *** PROBLEM: EXPECTED `TRUE' ***"
4709 ss
<< "SmtEngine::checkModel(): "
4710 << "ERRORS SATISFYING ASSERTIONS WITH MODEL:" << endl
4711 << "assertion: " << *i
<< endl
4712 << "simplifies to: " << n
<< endl
4713 << "expected `true'." << endl
4714 << "Run with `--check-models -v' for additional diagnostics.";
4716 InternalError(ss
.str());
4718 Warning() << ss
.str() << endl
;
4722 Notice() << "SmtEngine::checkModel(): all assertions checked out OK !" << endl
;
4725 UnsatCore
SmtEngine::getUnsatCore() throw(ModalException
, UnsafeInterruptException
) {
4726 Trace("smt") << "SMT getUnsatCore()" << endl
;
4727 SmtScope
smts(this);
4728 finalOptionsAreSet();
4729 if(Dump
.isOn("benchmark")) {
4730 Dump("benchmark") << GetUnsatCoreCommand();
4733 if(!options::unsatCores()) {
4734 throw ModalException("Cannot get an unsat core when produce-unsat-cores option is off.");
4736 if(d_status
.isNull() ||
4737 d_status
.asSatisfiabilityResult() != Result::UNSAT
||
4738 d_problemExtended
) {
4739 throw ModalException("Cannot get an unsat core unless immediately preceded by UNSAT/VALID response.");
4742 d_proofManager
->traceUnsatCore();// just to trigger core creation
4743 return UnsatCore(this, d_proofManager
->begin_unsat_core(), d_proofManager
->end_unsat_core());
4744 #else /* IS_PROOFS_BUILD */
4745 throw ModalException("This build of CVC4 doesn't have proof support (required for unsat cores).");
4746 #endif /* IS_PROOFS_BUILD */
4749 Proof
* SmtEngine::getProof() throw(ModalException
, UnsafeInterruptException
) {
4750 Trace("smt") << "SMT getProof()" << endl
;
4751 SmtScope
smts(this);
4752 finalOptionsAreSet();
4753 if(Dump
.isOn("benchmark")) {
4754 Dump("benchmark") << GetProofCommand();
4757 if(!options::proof()) {
4758 throw ModalException("Cannot get a proof when produce-proofs option is off.");
4760 if(d_status
.isNull() ||
4761 d_status
.asSatisfiabilityResult() != Result::UNSAT
||
4762 d_problemExtended
) {
4763 throw ModalException("Cannot get a proof unless immediately preceded by UNSAT/VALID response.");
4766 return ProofManager::getProof(this);
4767 #else /* IS_PROOFS_BUILD */
4768 throw ModalException("This build of CVC4 doesn't have proof support.");
4769 #endif /* IS_PROOFS_BUILD */
4772 void SmtEngine::printInstantiations( std::ostream
& out
) {
4773 SmtScope
smts(this);
4774 if( options::instFormatMode()==INST_FORMAT_MODE_SZS
){
4775 out
<< "% SZS output start Proof for " << d_filename
.c_str() << std::endl
;
4777 if( d_theoryEngine
){
4778 d_theoryEngine
->printInstantiations( out
);
4780 if( options::instFormatMode()==INST_FORMAT_MODE_SZS
){
4781 out
<< "% SZS output end Proof for " << d_filename
.c_str() << std::endl
;
4785 void SmtEngine::printSynthSolution( std::ostream
& out
) {
4786 SmtScope
smts(this);
4787 if( d_theoryEngine
){
4788 d_theoryEngine
->printSynthSolution( out
);
4792 vector
<Expr
> SmtEngine::getAssertions() throw(ModalException
) {
4793 SmtScope
smts(this);
4794 finalOptionsAreSet();
4796 if(Dump
.isOn("benchmark")) {
4797 Dump("benchmark") << GetAssertionsCommand();
4799 Trace("smt") << "SMT getAssertions()" << endl
;
4800 if(!options::produceAssertions()) {
4802 "Cannot query the current assertion list when not in produce-assertions mode.";
4803 throw ModalException(msg
);
4805 Assert(d_assertionList
!= NULL
);
4806 // copy the result out
4807 return vector
<Expr
>(d_assertionList
->begin(), d_assertionList
->end());
4810 void SmtEngine::push() throw(ModalException
, LogicException
, UnsafeInterruptException
) {
4811 SmtScope
smts(this);
4812 finalOptionsAreSet();
4814 Trace("smt") << "SMT push()" << endl
;
4815 d_private
->processAssertions();
4816 if(Dump
.isOn("benchmark")) {
4817 Dump("benchmark") << PushCommand();
4819 if(!options::incrementalSolving()) {
4820 throw ModalException("Cannot push when not solving incrementally (use --incremental)");
4823 // check to see if a postsolve() is pending
4824 if(d_needPostsolve
) {
4825 d_theoryEngine
->postsolve();
4826 d_needPostsolve
= false;
4829 // The problem isn't really "extended" yet, but this disallows
4830 // get-model after a push, simplifying our lives somewhat and
4831 // staying symmtric with pop.
4832 d_problemExtended
= true;
4834 d_userLevels
.push_back(d_userContext
->getLevel());
4836 Trace("userpushpop") << "SmtEngine: pushed to level "
4837 << d_userContext
->getLevel() << endl
;
4840 void SmtEngine::pop() throw(ModalException
, UnsafeInterruptException
) {
4841 SmtScope
smts(this);
4842 finalOptionsAreSet();
4843 Trace("smt") << "SMT pop()" << endl
;
4844 if(Dump
.isOn("benchmark")) {
4845 Dump("benchmark") << PopCommand();
4847 if(!options::incrementalSolving()) {
4848 throw ModalException("Cannot pop when not solving incrementally (use --incremental)");
4850 if(d_userLevels
.size() == 0) {
4851 throw ModalException("Cannot pop beyond the first user frame");
4854 // check to see if a postsolve() is pending
4855 if(d_needPostsolve
) {
4856 d_theoryEngine
->postsolve();
4857 d_needPostsolve
= false;
4860 // The problem isn't really "extended" yet, but this disallows
4861 // get-model after a pop, simplifying our lives somewhat. It might
4862 // not be strictly necessary to do so, since the pops occur lazily,
4863 // but also it would be weird to have a legally-executed (get-model)
4864 // that only returns a subset of the assignment (because the rest
4865 // is no longer in scope!).
4866 d_problemExtended
= true;
4868 AlwaysAssert(d_userContext
->getLevel() > 0);
4869 AlwaysAssert(d_userLevels
.back() < d_userContext
->getLevel());
4870 while (d_userLevels
.back() < d_userContext
->getLevel()) {
4873 d_userLevels
.pop_back();
4875 // Clear out assertion queues etc., in case anything is still in there
4876 d_private
->notifyPop();
4878 Trace("userpushpop") << "SmtEngine: popped to level "
4879 << d_userContext
->getLevel() << endl
;
4880 // FIXME: should we reset d_status here?
4881 // SMT-LIBv2 spec seems to imply no, but it would make sense to..
4884 void SmtEngine::internalPush() {
4885 Assert(d_fullyInited
);
4886 Trace("smt") << "SmtEngine::internalPush()" << endl
;
4888 if(options::incrementalSolving()) {
4889 d_private
->processAssertions();
4890 TimerStat::CodeTimer
pushPopTimer(d_stats
->d_pushPopTime
);
4891 d_userContext
->push();
4892 // the d_context push is done inside of the SAT solver
4893 d_propEngine
->push();
4897 void SmtEngine::internalPop(bool immediate
) {
4898 Assert(d_fullyInited
);
4899 Trace("smt") << "SmtEngine::internalPop()" << endl
;
4900 if(options::incrementalSolving()) {
4908 void SmtEngine::doPendingPops() {
4909 Assert(d_pendingPops
== 0 || options::incrementalSolving());
4910 while(d_pendingPops
> 0) {
4911 TimerStat::CodeTimer
pushPopTimer(d_stats
->d_pushPopTime
);
4912 d_propEngine
->pop();
4913 // the d_context pop is done inside of the SAT solver
4914 d_userContext
->pop();
4919 void SmtEngine::reset() throw() {
4920 SmtScope
smts(this);
4921 ExprManager
*em
= d_exprManager
;
4922 Trace("smt") << "SMT reset()" << endl
;
4923 if(Dump
.isOn("benchmark")) {
4924 Dump("benchmark") << ResetCommand();
4926 Options opts
= d_originalOptions
;
4928 NodeManager::fromExprManager(em
)->getOptions() = opts
;
4929 new(this) SmtEngine(em
);
4932 void SmtEngine::resetAssertions() throw() {
4933 SmtScope
smts(this);
4935 Trace("smt") << "SMT resetAssertions()" << endl
;
4936 if(Dump
.isOn("benchmark")) {
4937 Dump("benchmark") << ResetAssertionsCommand();
4940 while(!d_userLevels
.empty()) {
4944 // Also remember the global push/pop around everything.
4945 Assert(d_userLevels
.size() == 0 && d_userContext
->getLevel() == 1);
4946 d_context
->popto(0);
4947 d_userContext
->popto(0);
4948 d_modelGlobalCommands
.clear();
4949 d_userContext
->push();
4953 void SmtEngine::interrupt() throw(ModalException
) {
4954 if(!d_fullyInited
) {
4957 d_propEngine
->interrupt();
4958 d_theoryEngine
->interrupt();
4961 void SmtEngine::setResourceLimit(unsigned long units
, bool cumulative
) {
4962 d_private
->getResourceManager()->setResourceLimit(units
, cumulative
);
4964 void SmtEngine::setTimeLimit(unsigned long milis
, bool cumulative
) {
4965 d_private
->getResourceManager()->setTimeLimit(milis
, cumulative
);
4968 unsigned long SmtEngine::getResourceUsage() const {
4969 return d_private
->getResourceManager()->getResourceUsage();
4972 unsigned long SmtEngine::getTimeUsage() const {
4973 return d_private
->getResourceManager()->getTimeUsage();
4976 unsigned long SmtEngine::getResourceRemaining() const throw(ModalException
) {
4977 return d_private
->getResourceManager()->getResourceRemaining();
4980 unsigned long SmtEngine::getTimeRemaining() const throw(ModalException
) {
4981 return d_private
->getResourceManager()->getTimeRemaining();
4984 Statistics
SmtEngine::getStatistics() const throw() {
4985 return Statistics(*d_statisticsRegistry
);
4988 SExpr
SmtEngine::getStatistic(std::string name
) const throw() {
4989 return d_statisticsRegistry
->getStatistic(name
);
4992 void SmtEngine::setUserAttribute(const std::string
& attr
, Expr expr
, std::vector
<Expr
> expr_values
, std::string str_value
) {
4993 SmtScope
smts(this);
4994 std::vector
<Node
> node_values
;
4995 for( unsigned i
=0; i
<expr_values
.size(); i
++ ){
4996 node_values
.push_back( expr_values
[i
].getNode() );
4998 d_theoryEngine
->setUserAttribute(attr
, expr
.getNode(), node_values
, str_value
);
5001 void SmtEngine::setPrintFuncInModel(Expr f
, bool p
) {
5002 Trace("setp-model") << "Set printInModel " << f
<< " to " << p
<< std::endl
;
5003 for( unsigned i
=0; i
<d_modelGlobalCommands
.size(); i
++ ){
5004 Command
* c
= d_modelGlobalCommands
[i
];
5005 DeclareFunctionCommand
* dfc
= dynamic_cast<DeclareFunctionCommand
*>(c
);
5007 if( dfc
->getFunction()==f
){
5008 dfc
->setPrintInModel( p
);
5012 for( unsigned i
=0; i
<d_modelCommands
->size(); i
++ ){
5013 Command
* c
= (*d_modelCommands
)[i
];
5014 DeclareFunctionCommand
* dfc
= dynamic_cast<DeclareFunctionCommand
*>(c
);
5016 if( dfc
->getFunction()==f
){
5017 dfc
->setPrintInModel( p
);
5025 void SmtEngine::beforeSearch(SmtEngine
* smt
, const std::string
& option
) throw(ModalException
) {
5026 if(smt
!= NULL
&& smt
->d_fullyInited
) {
5027 std::stringstream ss
;
5028 ss
<< "cannot change option `" << option
<< "' after final initialization (i.e., after logic has been set)";
5029 throw ModalException(ss
.str());
5034 void SmtEngine::setOption(const std::string
& key
, const CVC4::SExpr
& value
)
5035 throw(OptionException
, ModalException
) {
5037 NodeManagerScope
nms(d_nodeManager
);
5038 Trace("smt") << "SMT setOption(" << key
<< ", " << value
<< ")" << endl
;
5040 if(Dump
.isOn("benchmark")) {
5041 Dump("benchmark") << SetOptionCommand(key
, value
);
5044 if(key
== "command-verbosity") {
5045 if(!value
.isAtom()) {
5046 const vector
<SExpr
>& cs
= value
.getChildren();
5047 if(cs
.size() == 2 &&
5048 (cs
[0].isKeyword() || cs
[0].isString()) &&
5049 cs
[1].isInteger()) {
5050 string c
= cs
[0].getValue();
5051 const Integer
& v
= cs
[1].getIntegerValue();
5052 if(v
< 0 || v
> 2) {
5053 throw OptionException("command-verbosity must be 0, 1, or 2");
5055 d_commandVerbosity
[c
] = v
;
5059 throw OptionException("command-verbosity value must be a tuple (command-name, integer)");
5062 if(!value
.isAtom()) {
5063 throw OptionException("bad value for :" + key
);
5066 string optionarg
= value
.getValue();
5068 d_optionsHandler
->setOption(key
, optionarg
);
5071 CVC4::SExpr
SmtEngine::getOption(const std::string
& key
) const
5072 throw(OptionException
) {
5074 NodeManagerScope
nms(d_nodeManager
);
5076 Trace("smt") << "SMT getOption(" << key
<< ")" << endl
;
5078 if(key
.length() >= 18 &&
5079 key
.compare(0, 18, "command-verbosity:") == 0) {
5080 map
<string
, Integer
>::const_iterator i
= d_commandVerbosity
.find(key
.c_str() + 18);
5081 if(i
!= d_commandVerbosity
.end()) {
5082 return SExpr((*i
).second
);
5084 i
= d_commandVerbosity
.find("*");
5085 if(i
!= d_commandVerbosity
.end()) {
5086 return SExpr((*i
).second
);
5088 return SExpr(Integer(2));
5091 if(Dump
.isOn("benchmark")) {
5092 Dump("benchmark") << GetOptionCommand(key
);
5095 if(key
== "command-verbosity") {
5096 vector
<SExpr
> result
;
5097 SExpr defaultVerbosity
;
5098 for(map
<string
, Integer
>::const_iterator i
= d_commandVerbosity
.begin();
5099 i
!= d_commandVerbosity
.end();
5102 v
.push_back(SExpr((*i
).first
));
5103 v
.push_back(SExpr((*i
).second
));
5104 if((*i
).first
== "*") {
5105 // put the default at the end of the SExpr
5106 defaultVerbosity
= SExpr(v
);
5108 result
.push_back(SExpr(v
));
5111 // put the default at the end of the SExpr
5112 if(!defaultVerbosity
.isAtom()) {
5113 result
.push_back(defaultVerbosity
);
5115 // ensure the default is always listed
5117 v
.push_back(SExpr("*"));
5118 v
.push_back(SExpr(Integer(2)));
5119 result
.push_back(SExpr(v
));
5121 return SExpr(result
);
5124 return SExpr::parseAtom(d_optionsHandler
->getOption(key
));
5127 }/* CVC4 namespace */