1 /********************* */
2 /*! \file bv_subtheory_core.cpp
4 ** Original author: Liana Hadarean
5 ** Major contributors: lianah
6 ** Minor contributors (to current version): none
7 ** This file is part of the CVC4 project.
8 ** Copyright (c) 2009-2013 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 Algebraic solver.
17 #include "theory/bv/bv_subtheory_core.h"
19 #include "theory/bv/theory_bv.h"
20 #include "theory/bv/theory_bv_utils.h"
21 #include "theory/bv/slicer.h"
22 #include "theory/theory_model.h"
23 #include "theory/bv/options.h"
27 using namespace CVC4::context
;
28 using namespace CVC4::theory
;
29 using namespace CVC4::theory::bv
;
30 using namespace CVC4::theory::bv::utils
;
32 CoreSolver::CoreSolver(context::Context
* c
, TheoryBV
* bv
)
33 : SubtheorySolver(c
, bv
),
35 d_equalityEngine(d_notify
, c
, "theory::bv::TheoryBV"),
36 d_slicer(new Slicer()),
37 d_isCoreTheory(c
, true),
41 // The kinds we are treating as function application in congruence
42 d_equalityEngine
.addFunctionKind(kind::BITVECTOR_CONCAT
, true);
43 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_AND);
44 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_OR);
45 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_XOR);
46 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_NOT);
47 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_NAND);
48 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_NOR);
49 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_XNOR);
50 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_COMP);
51 d_equalityEngine
.addFunctionKind(kind::BITVECTOR_MULT
, true);
52 d_equalityEngine
.addFunctionKind(kind::BITVECTOR_PLUS
, true);
53 d_equalityEngine
.addFunctionKind(kind::BITVECTOR_EXTRACT
, true);
54 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_SUB);
55 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_NEG);
56 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_UDIV);
57 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_UREM);
58 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_SDIV);
59 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_SREM);
60 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_SMOD);
61 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_SHL);
62 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_LSHR);
63 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_ASHR);
64 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_ULT);
65 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_ULE);
66 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_UGT);
67 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_UGE);
68 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_SLT);
69 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_SLE);
70 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_SGT);
71 // d_equalityEngine.addFunctionKind(kind::BITVECTOR_SGE);
74 CoreSolver::~CoreSolver() {
77 void CoreSolver::setMasterEqualityEngine(eq::EqualityEngine
* eq
) {
78 d_equalityEngine
.setMasterEqualityEngine(eq
);
81 void CoreSolver::preRegister(TNode node
) {
82 if (node
.getKind() == kind::EQUAL
) {
83 d_equalityEngine
.addTriggerEquality(node
);
84 if (options::bitvectorCoreSolver()) {
85 d_slicer
->processEquality(node
);
88 d_equalityEngine
.addTerm(node
);
93 void CoreSolver::explain(TNode literal
, std::vector
<TNode
>& assumptions
) {
94 bool polarity
= literal
.getKind() != kind::NOT
;
95 TNode atom
= polarity
? literal
: literal
[0];
96 if (atom
.getKind() == kind::EQUAL
) {
97 d_equalityEngine
.explainEquality(atom
[0], atom
[1], polarity
, assumptions
);
99 d_equalityEngine
.explainPredicate(atom
, polarity
, assumptions
);
103 Node
CoreSolver::getBaseDecomposition(TNode a
) {
104 std::vector
<Node
> a_decomp
;
105 d_slicer
->getBaseDecomposition(a
, a_decomp
);
106 Node new_a
= utils::mkConcat(a_decomp
);
107 Debug("bv-slicer") << "CoreSolver::getBaseDecomposition " << a
<<" => " << new_a
<< "\n";
111 bool CoreSolver::decomposeFact(TNode fact
) {
112 Debug("bv-slicer") << "CoreSolver::decomposeFact fact=" << fact
<< endl
;
113 // assert decompositions since the equality engine does not know the semantics of
115 // a == a_1 concat ... concat a_k
116 // b == b_1 concat ... concat b_k
117 Debug("bv-slicer") << "CoreSolver::decomposeFact fact=" << fact
<< endl
;
118 // FIXME: are this the right things to assert?
119 // assert decompositions since the equality engine does not know the semantics of
121 // a == a_1 concat ... concat a_k
122 // b == b_1 concat ... concat b_k
123 TNode eq
= fact
.getKind() == kind::NOT
? fact
[0] : fact
;
127 Node new_a
= getBaseDecomposition(a
);
128 Node new_b
= getBaseDecomposition(b
);
130 Assert (utils::getSize(new_a
) == utils::getSize(new_b
) &&
131 utils::getSize(new_a
) == utils::getSize(a
));
133 NodeManager
* nm
= NodeManager::currentNM();
134 Node a_eq_new_a
= nm
->mkNode(kind::EQUAL
, a
, new_a
);
135 Node b_eq_new_b
= nm
->mkNode(kind::EQUAL
, b
, new_b
);
138 ok
= assertFactToEqualityEngine(a_eq_new_a
, utils::mkTrue());
139 if (!ok
) return false;
140 ok
= assertFactToEqualityEngine(b_eq_new_b
, utils::mkTrue());
141 if (!ok
) return false;
142 ok
= assertFactToEqualityEngine(fact
, fact
);
143 if (!ok
) return false;
145 if (fact
.getKind() == kind::EQUAL
) {
146 // assert the individual equalities as well
148 if (new_a
.getKind() == kind::BITVECTOR_CONCAT
&&
149 new_b
.getKind() == kind::BITVECTOR_CONCAT
) {
151 Assert (new_a
.getNumChildren() == new_b
.getNumChildren());
152 for (unsigned i
= 0; i
< new_a
.getNumChildren(); ++i
) {
153 Node eq_i
= nm
->mkNode(kind::EQUAL
, new_a
[i
], new_b
[i
]);
154 ok
= assertFactToEqualityEngine(eq_i
, fact
);
155 if (!ok
) return false;
162 bool CoreSolver::check(Theory::Effort e
) {
163 Trace("bitvector::core") << "CoreSolver::check \n";
164 Assert (!d_bv
->inConflict());
165 ++(d_statistics
.d_numCallstoCheck
);
167 std::vector
<Node
> core_eqs
;
171 // update whether we are in the core fragment
172 if (d_isCoreTheory
&& !d_slicer
->isCoreTerm(fact
)) {
173 d_isCoreTheory
= false;
176 // only reason about equalities
177 if (fact
.getKind() == kind::EQUAL
|| (fact
.getKind() == kind::NOT
&& fact
[0].getKind() == kind::EQUAL
)) {
178 if (options::bitvectorCoreSolver()) {
179 ok
= decomposeFact(fact
);
181 ok
= assertFactToEqualityEngine(fact
, fact
);
184 ok
= assertFactToEqualityEngine(fact
, fact
);
190 if (Theory::fullEffort(e
) && isComplete()) {
197 void CoreSolver::buildModel() {
198 if (options::bitvectorCoreSolver()) {
203 Debug("bv-core") << "CoreSolver::buildModel() \n";
204 d_modelValues
.clear();
206 TNodeSet constants_in_eq_engine
;
207 // collect constants in equality engine
208 eq::EqClassesIterator eqcs_i
= eq::EqClassesIterator(&d_equalityEngine
);
209 while (!eqcs_i
.isFinished()) {
210 TNode repr
= *eqcs_i
;
211 if (repr
.getKind() == kind::CONST_BITVECTOR
) {
212 // must check if it's just the constant
213 eq::EqClassIterator
it(repr
, &d_equalityEngine
);
214 if (!(++it
).isFinished() || true) {
215 constants
.insert(repr
);
216 constants_in_eq_engine
.insert(repr
);
221 // build repr to value map
223 eqcs_i
= eq::EqClassesIterator(&d_equalityEngine
);
224 while (!eqcs_i
.isFinished()) {
225 TNode repr
= *eqcs_i
;
228 if (repr
.getKind() != kind::VARIABLE
&&
229 repr
.getKind() != kind::SKOLEM
&&
230 repr
.getKind() != kind::CONST_BITVECTOR
&&
231 !d_bv
->isSharedTerm(repr
)) {
235 TypeNode type
= repr
.getType();
236 if (type
.isBitVector() && repr
.getKind()!= kind::CONST_BITVECTOR
) {
237 Debug("bv-core-model") << " processing " << repr
<<"\n";
238 // we need to assign a value for it
239 TypeEnumerator
te(type
);
244 // Debug("bv-core-model") << " trying value " << val << "\n";
245 // Debug("bv-core-model") << " is in set? " << constants.count(val) << "\n";
246 // Debug("bv-core-model") << " enumerator done? " << te.isFinished() << "\n";
247 } while (constants
.count(val
) != 0 && !(te
.isFinished()));
249 if (te
.isFinished() && constants
.count(val
) != 0) {
250 // if we cannot enumerate anymore values we just return the lemma stating that
251 // at least two of the representatives are equal.
252 std::vector
<TNode
> representatives
;
253 representatives
.push_back(repr
);
255 for (TNodeSet::const_iterator it
= constants_in_eq_engine
.begin();
256 it
!= constants_in_eq_engine
.end(); ++it
) {
257 TNode constant
= *it
;
258 if (utils::getSize(constant
) == utils::getSize(repr
)) {
259 representatives
.push_back(constant
);
262 for (ModelValue::const_iterator it
= d_modelValues
.begin(); it
!= d_modelValues
.end(); ++it
) {
263 representatives
.push_back(it
->first
);
265 std::vector
<Node
> equalities
;
266 for (unsigned i
= 0; i
< representatives
.size(); ++i
) {
267 for (unsigned j
= i
+ 1; j
< representatives
.size(); ++j
) {
268 TNode a
= representatives
[i
];
269 TNode b
= representatives
[j
];
270 if (utils::getSize(a
) == utils::getSize(b
)) {
271 equalities
.push_back(utils::mkNode(kind::EQUAL
, a
, b
));
275 Node lemma
= utils::mkOr(equalities
);
277 Debug("bv-core") << " lemma: " << lemma
<< "\n";
280 Debug("bv-core-model") << " " << repr
<< " => " << val
<<"\n" ;
281 constants
.insert(val
);
282 d_modelValues
[repr
] = val
;
287 bool CoreSolver::assertFactToEqualityEngine(TNode fact
, TNode reason
) {
288 // Notify the equality engine
289 if (!d_bv
->inConflict() && (!d_bv
->wasPropagatedBySubtheory(fact
) || !d_bv
->getPropagatingSubtheory(fact
) == SUB_CORE
)) {
290 Debug("bv-slicer-eq") << "CoreSolver::assertFactToEqualityEngine fact=" << fact
<< endl
;
291 // Debug("bv-slicer-eq") << " reason=" << reason << endl;
292 bool negated
= fact
.getKind() == kind::NOT
;
293 TNode predicate
= negated
? fact
[0] : fact
;
294 if (predicate
.getKind() == kind::EQUAL
) {
297 d_equalityEngine
.assertEquality(predicate
, false, reason
);
300 d_equalityEngine
.assertEquality(predicate
, true, reason
);
303 // Adding predicate if the congruence over it is turned on
304 if (d_equalityEngine
.isFunctionKind(predicate
.getKind())) {
305 d_equalityEngine
.assertPredicate(predicate
, !negated
, reason
);
310 // checking for a conflict
311 if (d_bv
->inConflict()) {
317 bool CoreSolver::NotifyClass::eqNotifyTriggerEquality(TNode equality
, bool value
) {
318 Debug("bitvector::core") << "NotifyClass::eqNotifyTriggerEquality(" << equality
<< ", " << (value
? "true" : "false" )<< ")" << std::endl
;
320 return d_solver
.storePropagation(equality
);
322 return d_solver
.storePropagation(equality
.notNode());
326 bool CoreSolver::NotifyClass::eqNotifyTriggerPredicate(TNode predicate
, bool value
) {
327 Debug("bitvector::core") << "NotifyClass::eqNotifyTriggerPredicate(" << predicate
<< ", " << (value
? "true" : "false" ) << ")" << std::endl
;
329 return d_solver
.storePropagation(predicate
);
331 return d_solver
.storePropagation(predicate
.notNode());
335 bool CoreSolver::NotifyClass::eqNotifyTriggerTermEquality(TheoryId tag
, TNode t1
, TNode t2
, bool value
) {
336 Debug("bitvector::core") << "NotifyClass::eqNotifyTriggerTermMerge(" << t1
<< ", " << t2
<< ")" << std::endl
;
338 return d_solver
.storePropagation(t1
.eqNode(t2
));
340 return d_solver
.storePropagation(t1
.eqNode(t2
).notNode());
344 void CoreSolver::NotifyClass::eqNotifyConstantTermMerge(TNode t1
, TNode t2
) {
345 d_solver
.conflict(t1
, t2
);
348 bool CoreSolver::storePropagation(TNode literal
) {
349 return d_bv
->storePropagation(literal
, SUB_CORE
);
352 void CoreSolver::conflict(TNode a
, TNode b
) {
353 std::vector
<TNode
> assumptions
;
354 d_equalityEngine
.explainEquality(a
, b
, true, assumptions
);
355 Node conflict
= flattenAnd(assumptions
);
356 d_bv
->setConflict(conflict
);
359 void CoreSolver::collectModelInfo(TheoryModel
* m
, bool fullModel
) {
360 if (options::bitvectorCoreSolver()) {
364 if (Debug
.isOn("bitvector-model")) {
365 context::CDQueue
<Node
>::const_iterator it
= d_assertionQueue
.begin();
366 for (; it
!= d_assertionQueue
.end(); ++it
) {
367 Debug("bitvector-model") << "CoreSolver::collectModelInfo (assert "
372 d_bv
->computeRelevantTerms(termSet
);
373 m
->assertEqualityEngine(&d_equalityEngine
, &termSet
);
375 Debug("bitvector-model") << "CoreSolver::collectModelInfo complete.";
376 for (ModelValue::const_iterator it
= d_modelValues
.begin(); it
!= d_modelValues
.end(); ++it
) {
379 m
->assertEquality(a
, b
, true);
384 Node
CoreSolver::getModelValue(TNode var
) {
385 // we don't need to evaluate bv expressions and only look at variable values
386 // because this only gets called when the core theory is complete (i.e. no other bv
387 // function symbols are currently asserted)
388 Assert (d_slicer
->isCoreTerm(var
));
390 Debug("bitvector-model") << "CoreSolver::getModelValue (" << var
<<")";
391 Assert (isComplete());
392 TNode repr
= d_equalityEngine
.getRepresentative(var
);
393 Node result
= Node();
394 if (repr
.getKind() == kind::CONST_BITVECTOR
) {
396 } else if (d_modelValues
.find(repr
) == d_modelValues
.end()) {
397 // it may be a shared term that never gets asserted
398 // result is just Null
399 Assert(d_bv
->isSharedTerm(var
));
401 result
= d_modelValues
[repr
];
403 Debug("bitvector-model") << " => " << result
<<"\n";
407 CoreSolver::Statistics::Statistics()
408 : d_numCallstoCheck("theory::bv::CoreSolver::NumCallsToCheck", 0)
410 StatisticsRegistry::registerStat(&d_numCallstoCheck
);
412 CoreSolver::Statistics::~Statistics() {
413 StatisticsRegistry::unregisterStat(&d_numCallstoCheck
);