1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Gereon Kremer, Morgan Deters, Dejan Jovanovic |
4 |
|
* |
5 |
|
* This file is part of the cvc5 project. |
6 |
|
* |
7 |
|
* Copyright (c) 2009-2021 by the authors listed in the file AUTHORS |
8 |
|
* in the top-level source directory and their institutional affiliations. |
9 |
|
* All rights reserved. See the file COPYING in the top-level source |
10 |
|
* directory for licensing information. |
11 |
|
* **************************************************************************** |
12 |
|
* |
13 |
|
* A non-clausal circuit propagator for Boolean simplification. |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "theory/booleans/circuit_propagator.h" |
17 |
|
|
18 |
|
#include <algorithm> |
19 |
|
#include <stack> |
20 |
|
#include <vector> |
21 |
|
|
22 |
|
#include "expr/node_algorithm.h" |
23 |
|
#include "expr/proof_node.h" |
24 |
|
#include "expr/proof_node_manager.h" |
25 |
|
#include "theory/booleans/proof_circuit_propagator.h" |
26 |
|
#include "theory/eager_proof_generator.h" |
27 |
|
#include "theory/theory.h" |
28 |
|
#include "util/hash.h" |
29 |
|
#include "util/utility.h" |
30 |
|
|
31 |
|
using namespace std; |
32 |
|
|
33 |
|
namespace cvc5 { |
34 |
|
namespace theory { |
35 |
|
namespace booleans { |
36 |
|
|
37 |
10092 |
CircuitPropagator::CircuitPropagator(bool enableForward, bool enableBackward) |
38 |
|
: d_context(), |
39 |
|
d_propagationQueue(), |
40 |
|
d_propagationQueueClearer(&d_context, d_propagationQueue), |
41 |
20184 |
d_conflict(&d_context, TrustNode()), |
42 |
|
d_learnedLiterals(), |
43 |
|
d_learnedLiteralClearer(&d_context, d_learnedLiterals), |
44 |
|
d_backEdges(), |
45 |
|
d_backEdgesClearer(&d_context, d_backEdges), |
46 |
|
d_seen(&d_context), |
47 |
|
d_state(&d_context), |
48 |
|
d_forwardPropagation(enableForward), |
49 |
|
d_backwardPropagation(enableBackward), |
50 |
|
d_needsFinish(false), |
51 |
|
d_pnm(nullptr), |
52 |
|
d_epg(nullptr), |
53 |
|
d_proofInternal(nullptr), |
54 |
30276 |
d_proofExternal(nullptr) |
55 |
|
{ |
56 |
10092 |
} |
57 |
|
|
58 |
10277 |
void CircuitPropagator::finish() |
59 |
|
{ |
60 |
10277 |
Trace("circuit-prop") << "FINISH" << std::endl; |
61 |
10277 |
d_context.pop(); |
62 |
10277 |
} |
63 |
|
|
64 |
575748 |
void CircuitPropagator::assertTrue(TNode assertion) |
65 |
|
{ |
66 |
575748 |
Trace("circuit-prop") << "TRUE: " << assertion << std::endl; |
67 |
575748 |
if (assertion.getKind() == kind::CONST_BOOLEAN && !assertion.getConst<bool>()) |
68 |
|
{ |
69 |
660 |
makeConflict(assertion); |
70 |
|
} |
71 |
575088 |
else if (assertion.getKind() == kind::AND) |
72 |
|
{ |
73 |
6318 |
ProofCircuitPropagatorBackward prover{d_pnm, assertion, true}; |
74 |
3159 |
if (isProofEnabled()) |
75 |
|
{ |
76 |
807 |
addProof(assertion, prover.assume(assertion)); |
77 |
|
} |
78 |
498520 |
for (auto it = assertion.begin(); it != assertion.end(); ++it) |
79 |
|
{ |
80 |
495361 |
addProof(*it, prover.andTrue(it)); |
81 |
495361 |
assertTrue(*it); |
82 |
|
} |
83 |
|
} |
84 |
|
else |
85 |
|
{ |
86 |
|
// Analyze the assertion for back-edges and all that |
87 |
571929 |
computeBackEdges(assertion); |
88 |
|
// Assign the given assertion to true |
89 |
571929 |
if (isProofEnabled()) |
90 |
|
{ |
91 |
46945 |
assignAndEnqueue(assertion, true, d_pnm->mkAssume(assertion)); |
92 |
|
} |
93 |
|
else |
94 |
|
{ |
95 |
524984 |
assignAndEnqueue(assertion, true, nullptr); |
96 |
|
} |
97 |
|
} |
98 |
575748 |
} |
99 |
|
|
100 |
1099209 |
void CircuitPropagator::assignAndEnqueue(TNode n, |
101 |
|
bool value, |
102 |
|
std::shared_ptr<ProofNode> proof) |
103 |
|
{ |
104 |
2198418 |
Trace("circuit-prop") << "CircuitPropagator::assign(" << n << ", " |
105 |
1099209 |
<< (value ? "true" : "false") << ")" << std::endl; |
106 |
|
|
107 |
1099209 |
if (n.getKind() == kind::CONST_BOOLEAN) |
108 |
|
{ |
109 |
|
// Assigning a constant to the opposite value is dumb |
110 |
11239 |
if (value != n.getConst<bool>()) |
111 |
|
{ |
112 |
|
makeConflict(n); |
113 |
|
return; |
114 |
|
} |
115 |
|
} |
116 |
|
|
117 |
1099209 |
if (isProofEnabled()) |
118 |
|
{ |
119 |
96588 |
if (proof == nullptr) |
120 |
|
{ |
121 |
|
Warning() << "CircuitPropagator: Proof is missing for " << n << std::endl; |
122 |
|
Assert(false); |
123 |
|
} |
124 |
|
else |
125 |
|
{ |
126 |
96588 |
Assert(!proof->getResult().isNull()); |
127 |
193176 |
Node expected = value ? Node(n) : n.negate(); |
128 |
96588 |
if (proof->getResult() != expected) |
129 |
|
{ |
130 |
|
Warning() << "CircuitPropagator: Incorrect proof: " << expected |
131 |
|
<< " vs. " << proof->getResult() << std::endl |
132 |
|
<< *proof << std::endl; |
133 |
|
} |
134 |
96588 |
addProof(expected, std::move(proof)); |
135 |
|
} |
136 |
|
} |
137 |
|
|
138 |
|
// Get the current assignment |
139 |
1099209 |
AssignmentStatus state = d_state[n]; |
140 |
|
|
141 |
1099209 |
if (state != UNASSIGNED) |
142 |
|
{ |
143 |
|
// If the node is already assigned we might have a conflict |
144 |
408459 |
if (value != (state == ASSIGNED_TO_TRUE)) |
145 |
|
{ |
146 |
271 |
makeConflict(n); |
147 |
|
} |
148 |
|
} |
149 |
|
else |
150 |
|
{ |
151 |
|
// If unassigned, mark it as assigned |
152 |
690750 |
d_state[n] = value ? ASSIGNED_TO_TRUE : ASSIGNED_TO_FALSE; |
153 |
|
// Add for further propagation |
154 |
690750 |
d_propagationQueue.push_back(n); |
155 |
|
} |
156 |
|
} |
157 |
|
|
158 |
931 |
void CircuitPropagator::makeConflict(Node n) |
159 |
|
{ |
160 |
1839 |
auto bfalse = NodeManager::currentNM()->mkConst(false); |
161 |
931 |
ProofGenerator* g = nullptr; |
162 |
931 |
if (isProofEnabled()) |
163 |
|
{ |
164 |
341 |
if (d_epg->hasProofFor(bfalse)) |
165 |
|
{ |
166 |
23 |
return; |
167 |
|
} |
168 |
318 |
ProofCircuitPropagator pcp(d_pnm); |
169 |
318 |
if (n == bfalse) |
170 |
|
{ |
171 |
215 |
d_epg->setProofFor(bfalse, pcp.assume(bfalse)); |
172 |
|
} |
173 |
|
else |
174 |
|
{ |
175 |
206 |
d_epg->setProofFor(bfalse, |
176 |
206 |
pcp.conflict(pcp.assume(n), pcp.assume(n.negate()))); |
177 |
|
} |
178 |
318 |
g = d_proofInternal.get(); |
179 |
636 |
Trace("circuit-prop") << "Added conflict " << *d_epg->getProofFor(bfalse) |
180 |
318 |
<< std::endl; |
181 |
636 |
Trace("circuit-prop") << "\texpanded " << *g->getProofFor(bfalse) |
182 |
318 |
<< std::endl; |
183 |
|
} |
184 |
908 |
d_conflict = TrustNode::mkTrustLemma(bfalse, g); |
185 |
|
} |
186 |
|
|
187 |
571929 |
void CircuitPropagator::computeBackEdges(TNode node) |
188 |
|
{ |
189 |
1143858 |
Debug("circuit-prop") << "CircuitPropagator::computeBackEdges(" << node << ")" |
190 |
571929 |
<< endl; |
191 |
|
|
192 |
|
// Vector of nodes to visit |
193 |
1143858 |
vector<TNode> toVisit; |
194 |
|
|
195 |
|
// Start with the top node |
196 |
571929 |
if (d_seen.find(node) == d_seen.end()) |
197 |
|
{ |
198 |
558024 |
toVisit.push_back(node); |
199 |
558024 |
d_seen.insert(node); |
200 |
|
} |
201 |
|
|
202 |
|
// Initialize the back-edges for the root, so we don't have a special case |
203 |
571929 |
d_backEdges[node]; |
204 |
|
|
205 |
|
// Go through the visit list |
206 |
1598245 |
for (unsigned i = 0; i < toVisit.size(); ++i) |
207 |
|
{ |
208 |
|
// Node we need to visit |
209 |
2052632 |
TNode current = toVisit[i]; |
210 |
2052632 |
Debug("circuit-prop") |
211 |
1026316 |
<< "CircuitPropagator::computeBackEdges(): processing " << current |
212 |
1026316 |
<< endl; |
213 |
1026316 |
Assert(d_seen.find(current) != d_seen.end()); |
214 |
|
|
215 |
|
// If this not an atom visit all the children and compute the back edges |
216 |
1026316 |
if (Theory::theoryOf(current) == THEORY_BOOL) |
217 |
|
{ |
218 |
2707206 |
for (unsigned child = 0, child_end = current.getNumChildren(); |
219 |
2707206 |
child < child_end; |
220 |
|
++child) |
221 |
|
{ |
222 |
3656204 |
TNode childNode = current[child]; |
223 |
|
// Add the back edge |
224 |
1828102 |
d_backEdges[childNode].push_back(current); |
225 |
|
// Add to the queue if not seen yet |
226 |
1828102 |
if (d_seen.find(childNode) == d_seen.end()) |
227 |
|
{ |
228 |
468292 |
toVisit.push_back(childNode); |
229 |
468292 |
d_seen.insert(childNode); |
230 |
|
} |
231 |
|
} |
232 |
|
} |
233 |
|
} |
234 |
571929 |
} |
235 |
|
|
236 |
564188 |
void CircuitPropagator::propagateBackward(TNode parent, bool parentAssignment) |
237 |
|
{ |
238 |
1128376 |
Debug("circuit-prop") << "CircuitPropagator::propagateBackward(" << parent |
239 |
564188 |
<< ", " << parentAssignment << ")" << endl; |
240 |
1128376 |
ProofCircuitPropagatorBackward prover{d_pnm, parent, parentAssignment}; |
241 |
|
|
242 |
|
// backward rules |
243 |
564188 |
switch (parent.getKind()) |
244 |
|
{ |
245 |
5789 |
case kind::AND: |
246 |
5789 |
if (parentAssignment) |
247 |
|
{ |
248 |
|
// AND = TRUE: forall children c, assign(c = TRUE) |
249 |
20914 |
for (TNode::iterator i = parent.begin(), i_end = parent.end(); |
250 |
20914 |
i != i_end; |
251 |
|
++i) |
252 |
|
{ |
253 |
19962 |
assignAndEnqueue(*i, true, prover.andTrue(i)); |
254 |
|
} |
255 |
|
} |
256 |
|
else |
257 |
|
{ |
258 |
|
// AND = FALSE: if all children BUT ONE == TRUE, assign(c = FALSE) |
259 |
|
TNode::iterator holdout = |
260 |
10257 |
find_if_unique(parent.begin(), parent.end(), [this](TNode x) { |
261 |
20514 |
return !isAssignedTo(x, true); |
262 |
25351 |
}); |
263 |
4837 |
if (holdout != parent.end()) |
264 |
|
{ |
265 |
400 |
assignAndEnqueue(*holdout, false, prover.andFalse(parent, holdout)); |
266 |
|
} |
267 |
|
} |
268 |
5789 |
break; |
269 |
483704 |
case kind::OR: |
270 |
483704 |
if (parentAssignment) |
271 |
|
{ |
272 |
|
// OR = TRUE: if all children BUT ONE == FALSE, assign(c = TRUE) |
273 |
|
TNode::iterator holdout = |
274 |
966099 |
find_if_unique(parent.begin(), parent.end(), [this](TNode x) { |
275 |
1932198 |
return !isAssignedTo(x, false); |
276 |
2414796 |
}); |
277 |
482598 |
if (holdout != parent.end()) |
278 |
|
{ |
279 |
510 |
assignAndEnqueue(*holdout, true, prover.orTrue(parent, holdout)); |
280 |
|
} |
281 |
|
} |
282 |
|
else |
283 |
|
{ |
284 |
|
// OR = FALSE: forall children c, assign(c = FALSE) |
285 |
5402 |
for (TNode::iterator i = parent.begin(), i_end = parent.end(); |
286 |
5402 |
i != i_end; |
287 |
|
++i) |
288 |
|
{ |
289 |
4296 |
assignAndEnqueue(*i, false, prover.orFalse(i)); |
290 |
|
} |
291 |
|
} |
292 |
483704 |
break; |
293 |
69069 |
case kind::NOT: |
294 |
|
// NOT = b: assign(c = !b) |
295 |
69069 |
assignAndEnqueue( |
296 |
138138 |
parent[0], !parentAssignment, prover.Not(!parentAssignment, parent)); |
297 |
69069 |
break; |
298 |
329 |
case kind::ITE: |
299 |
329 |
if (isAssignedTo(parent[0], true)) |
300 |
|
{ |
301 |
|
// ITE c x y = v: if c is assigned and TRUE, assign(x = v) |
302 |
11 |
assignAndEnqueue(parent[1], parentAssignment, prover.iteC(true)); |
303 |
|
} |
304 |
318 |
else if (isAssignedTo(parent[0], false)) |
305 |
|
{ |
306 |
|
// ITE c x y = v: if c is assigned and FALSE, assign(y = v) |
307 |
3 |
assignAndEnqueue(parent[2], parentAssignment, prover.iteC(false)); |
308 |
|
} |
309 |
315 |
else if (isAssigned(parent[1]) && isAssigned(parent[2])) |
310 |
|
{ |
311 |
|
if (getAssignment(parent[1]) == parentAssignment |
312 |
|
&& getAssignment(parent[2]) != parentAssignment) |
313 |
|
{ |
314 |
|
// ITE c x y = v: if c is unassigned, x and y are assigned, x==v and |
315 |
|
// y!=v, assign(c = TRUE) |
316 |
|
assignAndEnqueue(parent[0], true, prover.iteIsCase(1)); |
317 |
|
} |
318 |
|
else if (getAssignment(parent[1]) != parentAssignment |
319 |
|
&& getAssignment(parent[2]) == parentAssignment) |
320 |
|
{ |
321 |
|
// ITE c x y = v: if c is unassigned, x and y are assigned, x!=v and |
322 |
|
// y==v, assign(c = FALSE) |
323 |
|
assignAndEnqueue(parent[0], false, prover.iteIsCase(0)); |
324 |
|
} |
325 |
|
} |
326 |
329 |
break; |
327 |
2352 |
case kind::EQUAL: |
328 |
2352 |
Assert(parent[0].getType().isBoolean()); |
329 |
2352 |
if (parentAssignment) |
330 |
|
{ |
331 |
|
// IFF x y = TRUE: if x [resp y] is assigned, assign(y = x.assignment |
332 |
|
// [resp x = y.assignment]) |
333 |
1772 |
if (isAssigned(parent[0])) |
334 |
|
{ |
335 |
668 |
assignAndEnqueue(parent[1], |
336 |
1336 |
getAssignment(parent[0]), |
337 |
1336 |
prover.eqYFromX(getAssignment(parent[0]), parent)); |
338 |
|
} |
339 |
1104 |
else if (isAssigned(parent[1])) |
340 |
|
{ |
341 |
40 |
assignAndEnqueue(parent[0], |
342 |
80 |
getAssignment(parent[1]), |
343 |
80 |
prover.eqXFromY(getAssignment(parent[1]), parent)); |
344 |
|
} |
345 |
|
} |
346 |
|
else |
347 |
|
{ |
348 |
|
// IFF x y = FALSE: if x [resp y] is assigned, assign(y = !x.assignment |
349 |
|
// [resp x = !y.assignment]) |
350 |
580 |
if (isAssigned(parent[0])) |
351 |
|
{ |
352 |
5 |
assignAndEnqueue(parent[1], |
353 |
10 |
!getAssignment(parent[0]), |
354 |
10 |
prover.neqYFromX(getAssignment(parent[0]), parent)); |
355 |
|
} |
356 |
575 |
else if (isAssigned(parent[1])) |
357 |
|
{ |
358 |
3 |
assignAndEnqueue(parent[0], |
359 |
6 |
!getAssignment(parent[1]), |
360 |
6 |
prover.neqXFromY(getAssignment(parent[1]), parent)); |
361 |
|
} |
362 |
|
} |
363 |
2352 |
break; |
364 |
2829 |
case kind::IMPLIES: |
365 |
2829 |
if (parentAssignment) |
366 |
|
{ |
367 |
2196 |
if (isAssignedTo(parent[0], true)) |
368 |
|
{ |
369 |
|
// IMPLIES x y = TRUE, and x == TRUE: assign(y = TRUE) |
370 |
594 |
assignAndEnqueue(parent[1], true, prover.impliesYFromX(parent)); |
371 |
|
} |
372 |
2196 |
if (isAssignedTo(parent[1], false)) |
373 |
|
{ |
374 |
|
// IMPLIES x y = TRUE, and y == FALSE: assign(x = FALSE) |
375 |
50 |
assignAndEnqueue(parent[0], false, prover.impliesXFromY(parent)); |
376 |
|
} |
377 |
|
} |
378 |
|
else |
379 |
|
{ |
380 |
|
// IMPLIES x y = FALSE: assign(x = TRUE) and assign(y = FALSE) |
381 |
633 |
assignAndEnqueue(parent[0], true, prover.impliesNegX()); |
382 |
633 |
assignAndEnqueue(parent[1], false, prover.impliesNegY()); |
383 |
|
} |
384 |
2829 |
break; |
385 |
116 |
case kind::XOR: |
386 |
116 |
if (parentAssignment) |
387 |
|
{ |
388 |
105 |
if (isAssigned(parent[0])) |
389 |
|
{ |
390 |
|
// XOR x y = TRUE, and x assigned, assign(y = !assignment(x)) |
391 |
|
assignAndEnqueue( |
392 |
|
parent[1], |
393 |
|
!getAssignment(parent[0]), |
394 |
|
prover.xorYFromX( |
395 |
|
!parentAssignment, getAssignment(parent[0]), parent)); |
396 |
|
} |
397 |
105 |
else if (isAssigned(parent[1])) |
398 |
|
{ |
399 |
|
// XOR x y = TRUE, and y assigned, assign(x = !assignment(y)) |
400 |
6 |
assignAndEnqueue( |
401 |
|
parent[0], |
402 |
12 |
!getAssignment(parent[1]), |
403 |
30 |
prover.xorXFromY( |
404 |
18 |
!parentAssignment, getAssignment(parent[1]), parent)); |
405 |
|
} |
406 |
|
} |
407 |
|
else |
408 |
|
{ |
409 |
11 |
if (isAssigned(parent[0])) |
410 |
|
{ |
411 |
|
// XOR x y = FALSE, and x assigned, assign(y = assignment(x)) |
412 |
5 |
assignAndEnqueue( |
413 |
|
parent[1], |
414 |
10 |
getAssignment(parent[0]), |
415 |
25 |
prover.xorYFromX( |
416 |
15 |
!parentAssignment, getAssignment(parent[0]), parent)); |
417 |
|
} |
418 |
6 |
else if (isAssigned(parent[1])) |
419 |
|
{ |
420 |
|
// XOR x y = FALSE, and y assigned, assign(x = assignment(y)) |
421 |
3 |
assignAndEnqueue( |
422 |
|
parent[0], |
423 |
6 |
getAssignment(parent[1]), |
424 |
15 |
prover.xorXFromY( |
425 |
9 |
!parentAssignment, getAssignment(parent[1]), parent)); |
426 |
|
} |
427 |
|
} |
428 |
116 |
break; |
429 |
|
default: Unhandled(); |
430 |
|
} |
431 |
564188 |
} |
432 |
|
|
433 |
687390 |
void CircuitPropagator::propagateForward(TNode child, bool childAssignment) |
434 |
|
{ |
435 |
|
// The assignment we have |
436 |
1374780 |
Debug("circuit-prop") << "CircuitPropagator::propagateForward(" << child |
437 |
687390 |
<< ", " << childAssignment << ")" << endl; |
438 |
|
|
439 |
|
// Get the back any nodes where this is child |
440 |
687390 |
const vector<Node>& parents = d_backEdges.find(child)->second; |
441 |
|
|
442 |
|
// Go through the parents and see if there is anything to propagate |
443 |
687390 |
vector<Node>::const_iterator parent_it = parents.begin(); |
444 |
687390 |
vector<Node>::const_iterator parent_it_end = parents.end(); |
445 |
1743854 |
for (; parent_it != parent_it_end && d_conflict.get().isNull(); ++parent_it) |
446 |
|
{ |
447 |
|
// The current parent of the child |
448 |
1056464 |
TNode parent = *parent_it; |
449 |
528232 |
Debug("circuit-prop") << "Parent: " << parent << endl; |
450 |
528232 |
Assert(expr::hasSubterm(parent, child)); |
451 |
|
|
452 |
1056464 |
ProofCircuitPropagatorForward prover{d_pnm, child, childAssignment, parent}; |
453 |
|
|
454 |
|
// Forward rules |
455 |
528232 |
switch (parent.getKind()) |
456 |
|
{ |
457 |
29715 |
case kind::AND: |
458 |
29715 |
if (childAssignment) |
459 |
|
{ |
460 |
25566 |
TNode::iterator holdout; |
461 |
19413517 |
holdout = find_if(parent.begin(), parent.end(), [this](TNode x) { |
462 |
38775902 |
return !isAssignedTo(x, true); |
463 |
38801468 |
}); |
464 |
|
|
465 |
25566 |
if (holdout == parent.end()) |
466 |
|
{ // all children are assigned TRUE |
467 |
|
// AND ...(x=TRUE)...: if all children now assigned to TRUE, |
468 |
|
// assign(AND = TRUE) |
469 |
17808 |
assignAndEnqueue(parent, true, prover.andAllTrue()); |
470 |
|
} |
471 |
7758 |
else if (isAssignedTo(parent, false)) |
472 |
|
{ // the AND is FALSE |
473 |
|
// is the holdout unique ? |
474 |
|
TNode::iterator other = |
475 |
1269 |
find_if(holdout + 1, parent.end(), [this](TNode x) { |
476 |
2538 |
return !isAssignedTo(x, true); |
477 |
3665 |
}); |
478 |
1127 |
if (other == parent.end()) |
479 |
|
{ // the holdout is unique |
480 |
|
// AND ...(x=TRUE)...: if all children BUT ONE now assigned to |
481 |
|
// TRUE, and AND == FALSE, assign(last_holdout = FALSE) |
482 |
410 |
assignAndEnqueue( |
483 |
820 |
*holdout, false, prover.andFalse(parent, holdout)); |
484 |
|
} |
485 |
|
} |
486 |
|
} |
487 |
|
else |
488 |
|
{ |
489 |
|
// AND ...(x=FALSE)...: assign(AND = FALSE) |
490 |
4149 |
assignAndEnqueue(parent, false, prover.andOneFalse()); |
491 |
|
} |
492 |
29715 |
break; |
493 |
422161 |
case kind::OR: |
494 |
422161 |
if (childAssignment) |
495 |
|
{ |
496 |
|
// OR ...(x=TRUE)...: assign(OR = TRUE) |
497 |
243394 |
assignAndEnqueue(parent, true, prover.orOneTrue()); |
498 |
|
} |
499 |
|
else |
500 |
|
{ |
501 |
178767 |
TNode::iterator holdout; |
502 |
937228 |
holdout = find_if(parent.begin(), parent.end(), [this](TNode x) { |
503 |
1516922 |
return !isAssignedTo(x, false); |
504 |
1695689 |
}); |
505 |
178767 |
if (holdout == parent.end()) |
506 |
|
{ // all children are assigned FALSE |
507 |
|
// OR ...(x=FALSE)...: if all children now assigned to FALSE, |
508 |
|
// assign(OR = FALSE) |
509 |
4223 |
assignAndEnqueue(parent, false, prover.orFalse()); |
510 |
|
} |
511 |
174544 |
else if (isAssignedTo(parent, true)) |
512 |
|
{ // the OR is TRUE |
513 |
|
// is the holdout unique ? |
514 |
|
TNode::iterator other = |
515 |
207604 |
find_if(holdout + 1, parent.end(), [this](TNode x) { |
516 |
415208 |
return !isAssignedTo(x, false); |
517 |
586209 |
}); |
518 |
171001 |
if (other == parent.end()) |
519 |
|
{ // the holdout is unique |
520 |
|
// OR ...(x=FALSE)...: if all children BUT ONE now assigned to |
521 |
|
// FALSE, and OR == TRUE, assign(last_holdout = TRUE) |
522 |
87427 |
assignAndEnqueue(*holdout, true, prover.orTrue(parent, holdout)); |
523 |
|
} |
524 |
|
} |
525 |
|
} |
526 |
422161 |
break; |
527 |
|
|
528 |
69007 |
case kind::NOT: |
529 |
|
// NOT (x=b): assign(NOT = !b) |
530 |
69007 |
assignAndEnqueue( |
531 |
138014 |
parent, !childAssignment, prover.Not(childAssignment, parent)); |
532 |
69007 |
break; |
533 |
|
|
534 |
66 |
case kind::ITE: |
535 |
66 |
if (child == parent[0]) |
536 |
|
{ |
537 |
32 |
if (childAssignment) |
538 |
|
{ |
539 |
23 |
if (isAssigned(parent[1])) |
540 |
|
{ |
541 |
|
// ITE (c=TRUE) x y: if x is assigned, assign(ITE = x.assignment) |
542 |
3 |
assignAndEnqueue(parent, |
543 |
6 |
getAssignment(parent[1]), |
544 |
6 |
prover.iteEvalThen(getAssignment(parent[1]))); |
545 |
|
} |
546 |
|
} |
547 |
|
else |
548 |
|
{ |
549 |
9 |
if (isAssigned(parent[2])) |
550 |
|
{ |
551 |
|
// ITE (c=FALSE) x y: if y is assigned, assign(ITE = y.assignment) |
552 |
5 |
assignAndEnqueue(parent, |
553 |
10 |
getAssignment(parent[2]), |
554 |
10 |
prover.iteEvalElse(getAssignment(parent[2]))); |
555 |
|
} |
556 |
|
} |
557 |
|
} |
558 |
66 |
if (child == parent[1]) |
559 |
|
{ |
560 |
24 |
if (isAssignedTo(parent[0], true)) |
561 |
|
{ |
562 |
|
// ITE c (x=v) y: if c is assigned and TRUE, assign(ITE = v) |
563 |
14 |
assignAndEnqueue( |
564 |
28 |
parent, childAssignment, prover.iteEvalThen(childAssignment)); |
565 |
|
} |
566 |
|
} |
567 |
66 |
if (child == parent[2]) |
568 |
|
{ |
569 |
10 |
Assert(child == parent[2]); |
570 |
10 |
if (isAssignedTo(parent[0], false)) |
571 |
|
{ |
572 |
|
// ITE c x (y=v): if c is assigned and FALSE, assign(ITE = v) |
573 |
6 |
assignAndEnqueue( |
574 |
12 |
parent, childAssignment, prover.iteEvalElse(childAssignment)); |
575 |
|
} |
576 |
|
} |
577 |
66 |
break; |
578 |
1927 |
case kind::EQUAL: |
579 |
1927 |
Assert(parent[0].getType().isBoolean()); |
580 |
1927 |
if (isAssigned(parent[0]) && isAssigned(parent[1])) |
581 |
|
{ |
582 |
|
// IFF x y: if x and y is assigned, assign(IFF = (x.assignment <=> |
583 |
|
// y.assignment)) |
584 |
1587 |
assignAndEnqueue(parent, |
585 |
3174 |
getAssignment(parent[0]) == getAssignment(parent[1]), |
586 |
3174 |
prover.eqEval(getAssignment(parent[0]), |
587 |
3174 |
getAssignment(parent[1]))); |
588 |
|
} |
589 |
|
else |
590 |
|
{ |
591 |
340 |
if (isAssigned(parent)) |
592 |
|
{ |
593 |
176 |
if (child == parent[0]) |
594 |
|
{ |
595 |
100 |
if (getAssignment(parent)) |
596 |
|
{ |
597 |
|
// IFF (x = b) y: if IFF is assigned to TRUE, assign(y = b) |
598 |
98 |
assignAndEnqueue(parent[1], |
599 |
|
childAssignment, |
600 |
196 |
prover.eqYFromX(childAssignment, parent)); |
601 |
|
} |
602 |
|
else |
603 |
|
{ |
604 |
|
// IFF (x = b) y: if IFF is assigned to FALSE, assign(y = !b) |
605 |
2 |
assignAndEnqueue(parent[1], |
606 |
2 |
!childAssignment, |
607 |
4 |
prover.neqYFromX(childAssignment, parent)); |
608 |
|
} |
609 |
|
} |
610 |
|
else |
611 |
|
{ |
612 |
76 |
Assert(child == parent[1]); |
613 |
76 |
if (getAssignment(parent)) |
614 |
|
{ |
615 |
|
// IFF x y = b: if IFF is assigned to TRUE, assign(x = b) |
616 |
76 |
assignAndEnqueue(parent[0], |
617 |
|
childAssignment, |
618 |
152 |
prover.eqXFromY(childAssignment, parent)); |
619 |
|
} |
620 |
|
else |
621 |
|
{ |
622 |
|
// IFF x y = b y: if IFF is assigned to FALSE, assign(x = !b) |
623 |
|
assignAndEnqueue(parent[0], |
624 |
|
!childAssignment, |
625 |
|
prover.neqXFromY(childAssignment, parent)); |
626 |
|
} |
627 |
|
} |
628 |
|
} |
629 |
|
} |
630 |
1927 |
break; |
631 |
5247 |
case kind::IMPLIES: |
632 |
5247 |
if (isAssigned(parent[0]) && isAssigned(parent[1])) |
633 |
|
{ |
634 |
|
// IMPLIES (x=v1) (y=v2): assign(IMPLIES = (!v1 || v2)) |
635 |
2022 |
assignAndEnqueue( |
636 |
|
parent, |
637 |
4044 |
!getAssignment(parent[0]) || getAssignment(parent[1]), |
638 |
4044 |
prover.impliesEval(getAssignment(parent[0]), |
639 |
4044 |
getAssignment(parent[1]))); |
640 |
|
} |
641 |
|
else |
642 |
|
{ |
643 |
11727 |
if (child == parent[0] && childAssignment |
644 |
11493 |
&& isAssignedTo(parent, true)) |
645 |
|
{ |
646 |
|
// IMPLIES (x=TRUE) y [with IMPLIES == TRUE]: assign(y = TRUE) |
647 |
80 |
assignAndEnqueue(parent[1], true, prover.impliesYFromX(parent)); |
648 |
|
} |
649 |
10848 |
if (child == parent[1] && !childAssignment |
650 |
9682 |
&& isAssignedTo(parent, true)) |
651 |
|
{ |
652 |
|
// IMPLIES x (y=FALSE) [with IMPLIES == TRUE]: assign(x = FALSE) |
653 |
6 |
assignAndEnqueue(parent[0], false, prover.impliesXFromY(parent)); |
654 |
|
} |
655 |
|
// Note that IMPLIES == FALSE doesn't need any cases here |
656 |
|
// because if that assignment has been done, we've already |
657 |
|
// propagated all the children (in back-propagation). |
658 |
|
} |
659 |
5247 |
break; |
660 |
109 |
case kind::XOR: |
661 |
109 |
if (isAssigned(parent)) |
662 |
|
{ |
663 |
35 |
if (child == parent[0]) |
664 |
|
{ |
665 |
|
// XOR (x=v) y [with XOR assigned], assign(y = (v ^ XOR) |
666 |
20 |
assignAndEnqueue( |
667 |
|
parent[1], |
668 |
40 |
childAssignment != getAssignment(parent), |
669 |
80 |
prover.xorYFromX( |
670 |
40 |
!getAssignment(parent), childAssignment, parent)); |
671 |
|
} |
672 |
|
else |
673 |
|
{ |
674 |
15 |
Assert(child == parent[1]); |
675 |
|
// XOR x (y=v) [with XOR assigned], assign(x = (v ^ XOR)) |
676 |
15 |
assignAndEnqueue( |
677 |
|
parent[0], |
678 |
30 |
childAssignment != getAssignment(parent), |
679 |
60 |
prover.xorXFromY( |
680 |
30 |
!getAssignment(parent), childAssignment, parent)); |
681 |
|
} |
682 |
|
} |
683 |
109 |
if (isAssigned(parent[0]) && isAssigned(parent[1])) |
684 |
|
{ |
685 |
37 |
assignAndEnqueue(parent, |
686 |
74 |
getAssignment(parent[0]) != getAssignment(parent[1]), |
687 |
74 |
prover.xorEval(getAssignment(parent[0]), |
688 |
74 |
getAssignment(parent[1]))); |
689 |
|
} |
690 |
109 |
break; |
691 |
|
default: Unhandled(); |
692 |
|
} |
693 |
|
} |
694 |
687390 |
} |
695 |
|
|
696 |
10277 |
TrustNode CircuitPropagator::propagate() |
697 |
|
{ |
698 |
10277 |
Debug("circuit-prop") << "CircuitPropagator::propagate()" << std::endl; |
699 |
|
|
700 |
697667 |
for (unsigned i = 0; |
701 |
697667 |
i < d_propagationQueue.size() && d_conflict.get().isNull(); |
702 |
|
++i) |
703 |
|
{ |
704 |
|
// The current node we are propagating |
705 |
1374780 |
TNode current = d_propagationQueue[i]; |
706 |
1374780 |
Debug("circuit-prop") << "CircuitPropagator::propagate(): processing " |
707 |
687390 |
<< current << std::endl; |
708 |
687390 |
bool assignment = getAssignment(current); |
709 |
1374780 |
Debug("circuit-prop") << "CircuitPropagator::propagate(): assigned to " |
710 |
687390 |
<< (assignment ? "true" : "false") << std::endl; |
711 |
|
|
712 |
|
// Is this an atom |
713 |
2671742 |
bool atom = Theory::theoryOf(current) != THEORY_BOOL || current.isVar() |
714 |
2749704 |
|| (current.getKind() == kind::EQUAL |
715 |
689886 |
&& (current[0].isVar() && current[1].isVar())); |
716 |
|
|
717 |
|
// If an atom, add to the list for simplification |
718 |
687390 |
if (atom |
719 |
802389 |
|| (current.getKind() == kind::EQUAL |
720 |
689742 |
&& (current[0].isVar() || current[1].isVar()))) |
721 |
|
{ |
722 |
229998 |
Debug("circuit-prop") |
723 |
114999 |
<< "CircuitPropagator::propagate(): adding to learned: " |
724 |
114999 |
<< (assignment ? (Node)current : current.notNode()) << std::endl; |
725 |
229998 |
Node lit = assignment ? Node(current) : current.notNode(); |
726 |
|
|
727 |
114999 |
if (isProofEnabled()) |
728 |
|
{ |
729 |
29259 |
if (d_epg->hasProofFor(lit)) |
730 |
|
{ |
731 |
|
// if we have a parent proof generator that provides proofs of the |
732 |
|
// inputs to this class, we must use the lazy proof chain |
733 |
29259 |
ProofGenerator* pg = d_proofInternal.get(); |
734 |
29259 |
if (d_proofExternal != nullptr) |
735 |
|
{ |
736 |
29259 |
d_proofExternal->addLazyStep(lit, pg); |
737 |
29259 |
pg = d_proofExternal.get(); |
738 |
|
} |
739 |
58518 |
TrustNode tlit = TrustNode::mkTrustLemma(lit, pg); |
740 |
29259 |
d_learnedLiterals.push_back(tlit); |
741 |
|
} |
742 |
|
else |
743 |
|
{ |
744 |
|
Warning() << "CircuitPropagator: Proof is missing for " << lit |
745 |
|
<< std::endl; |
746 |
|
TrustNode tlit = TrustNode::mkTrustLemma(lit, nullptr); |
747 |
|
d_learnedLiterals.push_back(tlit); |
748 |
|
} |
749 |
|
} |
750 |
|
else |
751 |
|
{ |
752 |
171480 |
TrustNode tlit = TrustNode::mkTrustLemma(lit, nullptr); |
753 |
85740 |
d_learnedLiterals.push_back(tlit); |
754 |
|
} |
755 |
114999 |
Trace("circuit-prop") << "Added proof for " << lit << std::endl; |
756 |
|
} |
757 |
|
|
758 |
|
// Propagate this value to the children (if not an atom or a constant) |
759 |
687390 |
if (d_backwardPropagation && !atom && !current.isConst()) |
760 |
|
{ |
761 |
564188 |
propagateBackward(current, assignment); |
762 |
|
} |
763 |
|
// Propagate this value to the parents |
764 |
687390 |
if (d_forwardPropagation) |
765 |
|
{ |
766 |
687390 |
propagateForward(current, assignment); |
767 |
|
} |
768 |
|
} |
769 |
|
|
770 |
|
// No conflict |
771 |
10277 |
return d_conflict; |
772 |
|
} |
773 |
|
|
774 |
3600 |
void CircuitPropagator::setProof(ProofNodeManager* pnm, |
775 |
|
context::Context* ctx, |
776 |
|
ProofGenerator* defParent) |
777 |
|
{ |
778 |
3600 |
d_pnm = pnm; |
779 |
3600 |
d_epg.reset(new EagerProofGenerator(pnm, ctx)); |
780 |
7200 |
d_proofInternal.reset( |
781 |
3600 |
new LazyCDProofChain(pnm, true, ctx, d_epg.get(), true)); |
782 |
3600 |
if (defParent != nullptr) |
783 |
|
{ |
784 |
|
// If we provide a parent proof generator (defParent), we want the ASSUME |
785 |
|
// leafs of proofs provided by this class to call the getProofFor method on |
786 |
|
// the parent. To do this, we use a LazyCDProofChain. |
787 |
7200 |
d_proofExternal.reset( |
788 |
3600 |
new LazyCDProofChain(pnm, true, ctx, defParent, false)); |
789 |
|
} |
790 |
3600 |
} |
791 |
|
|
792 |
2382983 |
bool CircuitPropagator::isProofEnabled() const |
793 |
|
{ |
794 |
2382983 |
return d_proofInternal != nullptr; |
795 |
|
} |
796 |
|
|
797 |
592756 |
void CircuitPropagator::addProof(TNode f, std::shared_ptr<ProofNode> pf) |
798 |
|
{ |
799 |
592756 |
if (isProofEnabled()) |
800 |
|
{ |
801 |
127013 |
if (!d_epg->hasProofFor(f)) |
802 |
|
{ |
803 |
113562 |
Trace("circuit-prop") << "Adding proof for " << f << std::endl |
804 |
56781 |
<< "\t" << *pf << std::endl; |
805 |
56781 |
d_epg->setProofFor(f, std::move(pf)); |
806 |
|
} |
807 |
|
else |
808 |
|
{ |
809 |
140464 |
auto prf = d_epg->getProofFor(f); |
810 |
140464 |
Trace("circuit-prop") << "Ignoring proof, we already have" << std::endl |
811 |
70232 |
<< "\t" << *prf << std::endl; |
812 |
|
} |
813 |
|
} |
814 |
592756 |
} |
815 |
|
|
816 |
|
} // namespace booleans |
817 |
|
} // namespace theory |
818 |
28191 |
} // namespace cvc5 |