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 "proof/eager_proof_generator.h" |
24 |
|
#include "proof/proof_node.h" |
25 |
|
#include "proof/proof_node_manager.h" |
26 |
|
#include "theory/booleans/proof_circuit_propagator.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 |
13182 |
CircuitPropagator::CircuitPropagator(bool enableForward, bool enableBackward) |
38 |
|
: d_context(), |
39 |
|
d_propagationQueue(), |
40 |
|
d_propagationQueueClearer(&d_context, d_propagationQueue), |
41 |
26364 |
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 |
39546 |
d_proofExternal(nullptr) |
55 |
|
{ |
56 |
13182 |
} |
57 |
|
|
58 |
11045 |
void CircuitPropagator::finish() |
59 |
|
{ |
60 |
11045 |
Trace("circuit-prop") << "FINISH" << std::endl; |
61 |
11045 |
d_context.pop(); |
62 |
11045 |
} |
63 |
|
|
64 |
564749 |
void CircuitPropagator::assertTrue(TNode assertion) |
65 |
|
{ |
66 |
564749 |
Trace("circuit-prop") << "TRUE: " << assertion << std::endl; |
67 |
564749 |
if (assertion.getKind() == kind::CONST_BOOLEAN && !assertion.getConst<bool>()) |
68 |
|
{ |
69 |
699 |
makeConflict(assertion); |
70 |
|
} |
71 |
564050 |
else if (assertion.getKind() == kind::AND) |
72 |
|
{ |
73 |
6974 |
ProofCircuitPropagatorBackward prover{d_pnm, assertion, true}; |
74 |
3487 |
if (isProofEnabled()) |
75 |
|
{ |
76 |
828 |
addProof(assertion, prover.assume(assertion)); |
77 |
|
} |
78 |
487246 |
for (auto it = assertion.begin(); it != assertion.end(); ++it) |
79 |
|
{ |
80 |
483759 |
addProof(*it, prover.andTrue(it)); |
81 |
483759 |
assertTrue(*it); |
82 |
|
} |
83 |
|
} |
84 |
|
else |
85 |
|
{ |
86 |
|
// Analyze the assertion for back-edges and all that |
87 |
560563 |
computeBackEdges(assertion); |
88 |
|
// Assign the given assertion to true |
89 |
560563 |
if (isProofEnabled()) |
90 |
|
{ |
91 |
34506 |
assignAndEnqueue(assertion, true, d_pnm->mkAssume(assertion)); |
92 |
|
} |
93 |
|
else |
94 |
|
{ |
95 |
526057 |
assignAndEnqueue(assertion, true, nullptr); |
96 |
|
} |
97 |
|
} |
98 |
564749 |
} |
99 |
|
|
100 |
1087360 |
void CircuitPropagator::assignAndEnqueue(TNode n, |
101 |
|
bool value, |
102 |
|
std::shared_ptr<ProofNode> proof) |
103 |
|
{ |
104 |
2174720 |
Trace("circuit-prop") << "CircuitPropagator::assign(" << n << ", " |
105 |
1087360 |
<< (value ? "true" : "false") << ")" << std::endl; |
106 |
|
|
107 |
1087360 |
if (n.getKind() == kind::CONST_BOOLEAN) |
108 |
|
{ |
109 |
|
// Assigning a constant to the opposite value is dumb |
110 |
12023 |
if (value != n.getConst<bool>()) |
111 |
|
{ |
112 |
|
makeConflict(n); |
113 |
|
return; |
114 |
|
} |
115 |
|
} |
116 |
|
|
117 |
1087360 |
if (isProofEnabled()) |
118 |
|
{ |
119 |
82926 |
if (proof == nullptr) |
120 |
|
{ |
121 |
|
Warning() << "CircuitPropagator: Proof is missing for " << n << std::endl; |
122 |
|
Assert(false); |
123 |
|
} |
124 |
|
else |
125 |
|
{ |
126 |
82926 |
Assert(!proof->getResult().isNull()); |
127 |
165852 |
Node expected = value ? Node(n) : n.negate(); |
128 |
82926 |
if (proof->getResult() != expected) |
129 |
|
{ |
130 |
|
Warning() << "CircuitPropagator: Incorrect proof: " << expected |
131 |
|
<< " vs. " << proof->getResult() << std::endl |
132 |
|
<< *proof << std::endl; |
133 |
|
} |
134 |
82926 |
addProof(expected, std::move(proof)); |
135 |
|
} |
136 |
|
} |
137 |
|
|
138 |
|
// Get the current assignment |
139 |
1087360 |
AssignmentStatus state = d_state[n]; |
140 |
|
|
141 |
1087360 |
if (state != UNASSIGNED) |
142 |
|
{ |
143 |
|
// If the node is already assigned we might have a conflict |
144 |
407805 |
if (value != (state == ASSIGNED_TO_TRUE)) |
145 |
|
{ |
146 |
273 |
makeConflict(n); |
147 |
|
} |
148 |
|
} |
149 |
|
else |
150 |
|
{ |
151 |
|
// If unassigned, mark it as assigned |
152 |
679555 |
d_state[n] = value ? ASSIGNED_TO_TRUE : ASSIGNED_TO_FALSE; |
153 |
|
// Add for further propagation |
154 |
679555 |
d_propagationQueue.push_back(n); |
155 |
|
} |
156 |
|
} |
157 |
|
|
158 |
972 |
void CircuitPropagator::makeConflict(Node n) |
159 |
|
{ |
160 |
1920 |
auto bfalse = NodeManager::currentNM()->mkConst(false); |
161 |
972 |
ProofGenerator* g = nullptr; |
162 |
972 |
if (isProofEnabled()) |
163 |
|
{ |
164 |
361 |
if (d_epg->hasProofFor(bfalse)) |
165 |
|
{ |
166 |
24 |
return; |
167 |
|
} |
168 |
337 |
ProofCircuitPropagator pcp(d_pnm); |
169 |
337 |
if (n == bfalse) |
170 |
|
{ |
171 |
233 |
d_epg->setProofFor(bfalse, pcp.assume(bfalse)); |
172 |
|
} |
173 |
|
else |
174 |
|
{ |
175 |
208 |
d_epg->setProofFor(bfalse, |
176 |
208 |
pcp.conflict(pcp.assume(n), pcp.assume(n.negate()))); |
177 |
|
} |
178 |
337 |
g = d_proofInternal.get(); |
179 |
674 |
Trace("circuit-prop") << "Added conflict " << *d_epg->getProofFor(bfalse) |
180 |
337 |
<< std::endl; |
181 |
674 |
Trace("circuit-prop") << "\texpanded " << *g->getProofFor(bfalse) |
182 |
337 |
<< std::endl; |
183 |
|
} |
184 |
948 |
d_conflict = TrustNode::mkTrustLemma(bfalse, g); |
185 |
|
} |
186 |
|
|
187 |
560563 |
void CircuitPropagator::computeBackEdges(TNode node) |
188 |
|
{ |
189 |
1121126 |
Debug("circuit-prop") << "CircuitPropagator::computeBackEdges(" << node << ")" |
190 |
560563 |
<< endl; |
191 |
|
|
192 |
|
// Vector of nodes to visit |
193 |
1121126 |
vector<TNode> toVisit; |
194 |
|
|
195 |
|
// Start with the top node |
196 |
560563 |
if (d_seen.find(node) == d_seen.end()) |
197 |
|
{ |
198 |
546812 |
toVisit.push_back(node); |
199 |
546812 |
d_seen.insert(node); |
200 |
|
} |
201 |
|
|
202 |
|
// Initialize the back-edges for the root, so we don't have a special case |
203 |
560563 |
d_backEdges[node]; |
204 |
|
|
205 |
|
// Go through the visit list |
206 |
1566071 |
for (unsigned i = 0; i < toVisit.size(); ++i) |
207 |
|
{ |
208 |
|
// Node we need to visit |
209 |
2011016 |
TNode current = toVisit[i]; |
210 |
2011016 |
Debug("circuit-prop") |
211 |
1005508 |
<< "CircuitPropagator::computeBackEdges(): processing " << current |
212 |
1005508 |
<< endl; |
213 |
1005508 |
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 |
1005508 |
if (Theory::theoryOf(current) == THEORY_BOOL) |
217 |
|
{ |
218 |
2645617 |
for (unsigned child = 0, child_end = current.getNumChildren(); |
219 |
2645617 |
child < child_end; |
220 |
|
++child) |
221 |
|
{ |
222 |
3570422 |
TNode childNode = current[child]; |
223 |
|
// Add the back edge |
224 |
1785211 |
d_backEdges[childNode].push_back(current); |
225 |
|
// Add to the queue if not seen yet |
226 |
1785211 |
if (d_seen.find(childNode) == d_seen.end()) |
227 |
|
{ |
228 |
458696 |
toVisit.push_back(childNode); |
229 |
458696 |
d_seen.insert(childNode); |
230 |
|
} |
231 |
|
} |
232 |
|
} |
233 |
|
} |
234 |
560563 |
} |
235 |
|
|
236 |
551752 |
void CircuitPropagator::propagateBackward(TNode parent, bool parentAssignment) |
237 |
|
{ |
238 |
1103504 |
Debug("circuit-prop") << "CircuitPropagator::propagateBackward(" << parent |
239 |
551752 |
<< ", " << parentAssignment << ")" << endl; |
240 |
1103504 |
ProofCircuitPropagatorBackward prover{d_pnm, parent, parentAssignment}; |
241 |
|
|
242 |
|
// backward rules |
243 |
551752 |
switch (parent.getKind()) |
244 |
|
{ |
245 |
5812 |
case kind::AND: |
246 |
5812 |
if (parentAssignment) |
247 |
|
{ |
248 |
|
// AND = TRUE: forall children c, assign(c = TRUE) |
249 |
20824 |
for (TNode::iterator i = parent.begin(), i_end = parent.end(); |
250 |
20824 |
i != i_end; |
251 |
|
++i) |
252 |
|
{ |
253 |
19862 |
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 |
10283 |
find_if_unique(parent.begin(), parent.end(), [this](TNode x) { |
261 |
20566 |
return !isAssignedTo(x, true); |
262 |
25416 |
}); |
263 |
4850 |
if (holdout != parent.end()) |
264 |
|
{ |
265 |
402 |
assignAndEnqueue(*holdout, false, prover.andFalse(parent, holdout)); |
266 |
|
} |
267 |
|
} |
268 |
5812 |
break; |
269 |
471188 |
case kind::OR: |
270 |
471188 |
if (parentAssignment) |
271 |
|
{ |
272 |
|
// OR = TRUE: if all children BUT ONE == FALSE, assign(c = TRUE) |
273 |
|
TNode::iterator holdout = |
274 |
941075 |
find_if_unique(parent.begin(), parent.end(), [this](TNode x) { |
275 |
1882150 |
return !isAssignedTo(x, false); |
276 |
2352236 |
}); |
277 |
470086 |
if (holdout != parent.end()) |
278 |
|
{ |
279 |
507 |
assignAndEnqueue(*holdout, true, prover.orTrue(parent, holdout)); |
280 |
|
} |
281 |
|
} |
282 |
|
else |
283 |
|
{ |
284 |
|
// OR = FALSE: forall children c, assign(c = FALSE) |
285 |
5373 |
for (TNode::iterator i = parent.begin(), i_end = parent.end(); |
286 |
5373 |
i != i_end; |
287 |
|
++i) |
288 |
|
{ |
289 |
4271 |
assignAndEnqueue(*i, false, prover.orFalse(i)); |
290 |
|
} |
291 |
|
} |
292 |
471188 |
break; |
293 |
69361 |
case kind::NOT: |
294 |
|
// NOT = b: assign(c = !b) |
295 |
69361 |
assignAndEnqueue( |
296 |
138722 |
parent[0], !parentAssignment, prover.Not(!parentAssignment, parent)); |
297 |
69361 |
break; |
298 |
335 |
case kind::ITE: |
299 |
335 |
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 |
324 |
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 |
321 |
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 |
335 |
break; |
327 |
2170 |
case kind::EQUAL: |
328 |
2170 |
Assert(parent[0].getType().isBoolean()); |
329 |
2170 |
if (parentAssignment) |
330 |
|
{ |
331 |
|
// IFF x y = TRUE: if x [resp y] is assigned, assign(y = x.assignment |
332 |
|
// [resp x = y.assignment]) |
333 |
1567 |
if (isAssigned(parent[0])) |
334 |
|
{ |
335 |
493 |
assignAndEnqueue(parent[1], |
336 |
986 |
getAssignment(parent[0]), |
337 |
986 |
prover.eqYFromX(getAssignment(parent[0]), parent)); |
338 |
|
} |
339 |
1074 |
else if (isAssigned(parent[1])) |
340 |
|
{ |
341 |
23 |
assignAndEnqueue(parent[0], |
342 |
46 |
getAssignment(parent[1]), |
343 |
46 |
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 |
603 |
if (isAssigned(parent[0])) |
351 |
|
{ |
352 |
13 |
assignAndEnqueue(parent[1], |
353 |
26 |
!getAssignment(parent[0]), |
354 |
26 |
prover.neqYFromX(getAssignment(parent[0]), parent)); |
355 |
|
} |
356 |
590 |
else if (isAssigned(parent[1])) |
357 |
|
{ |
358 |
7 |
assignAndEnqueue(parent[0], |
359 |
14 |
!getAssignment(parent[1]), |
360 |
14 |
prover.neqXFromY(getAssignment(parent[1]), parent)); |
361 |
|
} |
362 |
|
} |
363 |
2170 |
break; |
364 |
2770 |
case kind::IMPLIES: |
365 |
2770 |
if (parentAssignment) |
366 |
|
{ |
367 |
2170 |
if (isAssignedTo(parent[0], true)) |
368 |
|
{ |
369 |
|
// IMPLIES x y = TRUE, and x == TRUE: assign(y = TRUE) |
370 |
572 |
assignAndEnqueue(parent[1], true, prover.impliesYFromX(parent)); |
371 |
|
} |
372 |
2170 |
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 |
600 |
assignAndEnqueue(parent[0], true, prover.impliesNegX()); |
382 |
600 |
assignAndEnqueue(parent[1], false, prover.impliesNegY()); |
383 |
|
} |
384 |
2770 |
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 |
551752 |
} |
432 |
|
|
433 |
676244 |
void CircuitPropagator::propagateForward(TNode child, bool childAssignment) |
434 |
|
{ |
435 |
|
// The assignment we have |
436 |
1352488 |
Debug("circuit-prop") << "CircuitPropagator::propagateForward(" << child |
437 |
676244 |
<< ", " << childAssignment << ")" << endl; |
438 |
|
|
439 |
|
// Get the back any nodes where this is child |
440 |
676244 |
const vector<Node>& parents = d_backEdges.find(child)->second; |
441 |
|
|
442 |
|
// Go through the parents and see if there is anything to propagate |
443 |
676244 |
vector<Node>::const_iterator parent_it = parents.begin(); |
444 |
676244 |
vector<Node>::const_iterator parent_it_end = parents.end(); |
445 |
1731108 |
for (; parent_it != parent_it_end && d_conflict.get().isNull(); ++parent_it) |
446 |
|
{ |
447 |
|
// The current parent of the child |
448 |
1054864 |
TNode parent = *parent_it; |
449 |
527432 |
Debug("circuit-prop") << "Parent: " << parent << endl; |
450 |
527432 |
Assert(expr::hasSubterm(parent, child)); |
451 |
|
|
452 |
1054864 |
ProofCircuitPropagatorForward prover{d_pnm, child, childAssignment, parent}; |
453 |
|
|
454 |
|
// Forward rules |
455 |
527432 |
switch (parent.getKind()) |
456 |
|
{ |
457 |
29539 |
case kind::AND: |
458 |
29539 |
if (childAssignment) |
459 |
|
{ |
460 |
25428 |
TNode::iterator holdout; |
461 |
19410424 |
holdout = find_if(parent.begin(), parent.end(), [this](TNode x) { |
462 |
38769992 |
return !isAssignedTo(x, true); |
463 |
38795420 |
}); |
464 |
|
|
465 |
25428 |
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 |
17710 |
assignAndEnqueue(parent, true, prover.andAllTrue()); |
470 |
|
} |
471 |
7718 |
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 |
3667 |
}); |
478 |
1129 |
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 |
412 |
assignAndEnqueue( |
483 |
824 |
*holdout, false, prover.andFalse(parent, holdout)); |
484 |
|
} |
485 |
|
} |
486 |
|
} |
487 |
|
else |
488 |
|
{ |
489 |
|
// AND ...(x=FALSE)...: assign(AND = FALSE) |
490 |
4111 |
assignAndEnqueue(parent, false, prover.andOneFalse()); |
491 |
|
} |
492 |
29539 |
break; |
493 |
422128 |
case kind::OR: |
494 |
422128 |
if (childAssignment) |
495 |
|
{ |
496 |
|
// OR ...(x=TRUE)...: assign(OR = TRUE) |
497 |
243395 |
assignAndEnqueue(parent, true, prover.orOneTrue()); |
498 |
|
} |
499 |
|
else |
500 |
|
{ |
501 |
178733 |
TNode::iterator holdout; |
502 |
924025 |
holdout = find_if(parent.begin(), parent.end(), [this](TNode x) { |
503 |
1490584 |
return !isAssignedTo(x, false); |
504 |
1669317 |
}); |
505 |
178733 |
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 |
4198 |
assignAndEnqueue(parent, false, prover.orFalse()); |
510 |
|
} |
511 |
174535 |
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 |
586208 |
}); |
518 |
171000 |
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 |
87426 |
assignAndEnqueue(*holdout, true, prover.orTrue(parent, holdout)); |
523 |
|
} |
524 |
|
} |
525 |
|
} |
526 |
422128 |
break; |
527 |
|
|
528 |
69285 |
case kind::NOT: |
529 |
|
// NOT (x=b): assign(NOT = !b) |
530 |
69285 |
assignAndEnqueue( |
531 |
138570 |
parent, !childAssignment, prover.Not(childAssignment, parent)); |
532 |
69285 |
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 |
1530 |
case kind::EQUAL: |
579 |
1530 |
Assert(parent[0].getType().isBoolean()); |
580 |
1530 |
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 |
1189 |
assignAndEnqueue(parent, |
585 |
2378 |
getAssignment(parent[0]) == getAssignment(parent[1]), |
586 |
2378 |
prover.eqEval(getAssignment(parent[0]), |
587 |
2378 |
getAssignment(parent[1]))); |
588 |
|
} |
589 |
|
else |
590 |
|
{ |
591 |
341 |
if (isAssigned(parent)) |
592 |
|
{ |
593 |
180 |
if (child == parent[0]) |
594 |
|
{ |
595 |
125 |
if (getAssignment(parent)) |
596 |
|
{ |
597 |
|
// IFF (x = b) y: if IFF is assigned to TRUE, assign(y = b) |
598 |
115 |
assignAndEnqueue(parent[1], |
599 |
|
childAssignment, |
600 |
230 |
prover.eqYFromX(childAssignment, parent)); |
601 |
|
} |
602 |
|
else |
603 |
|
{ |
604 |
|
// IFF (x = b) y: if IFF is assigned to FALSE, assign(y = !b) |
605 |
10 |
assignAndEnqueue(parent[1], |
606 |
10 |
!childAssignment, |
607 |
20 |
prover.neqYFromX(childAssignment, parent)); |
608 |
|
} |
609 |
|
} |
610 |
|
else |
611 |
|
{ |
612 |
55 |
Assert(child == parent[1]); |
613 |
55 |
if (getAssignment(parent)) |
614 |
|
{ |
615 |
|
// IFF x y = b: if IFF is assigned to TRUE, assign(x = b) |
616 |
55 |
assignAndEnqueue(parent[0], |
617 |
|
childAssignment, |
618 |
110 |
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 |
1530 |
break; |
631 |
4775 |
case kind::IMPLIES: |
632 |
4775 |
if (isAssigned(parent[0]) && isAssigned(parent[1])) |
633 |
|
{ |
634 |
|
// IMPLIES (x=v1) (y=v2): assign(IMPLIES = (!v1 || v2)) |
635 |
1916 |
assignAndEnqueue( |
636 |
|
parent, |
637 |
3832 |
!getAssignment(parent[0]) || getAssignment(parent[1]), |
638 |
3832 |
prover.impliesEval(getAssignment(parent[0]), |
639 |
3832 |
getAssignment(parent[1]))); |
640 |
|
} |
641 |
|
else |
642 |
|
{ |
643 |
10413 |
if (child == parent[0] && childAssignment |
644 |
10198 |
&& 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 |
9600 |
if (child == parent[1] && !childAssignment |
650 |
8584 |
&& 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 |
4775 |
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 |
676244 |
} |
695 |
|
|
696 |
11045 |
TrustNode CircuitPropagator::propagate() |
697 |
|
{ |
698 |
11045 |
Debug("circuit-prop") << "CircuitPropagator::propagate()" << std::endl; |
699 |
|
|
700 |
687289 |
for (unsigned i = 0; |
701 |
687289 |
i < d_propagationQueue.size() && d_conflict.get().isNull(); |
702 |
|
++i) |
703 |
|
{ |
704 |
|
// The current node we are propagating |
705 |
1352488 |
TNode current = d_propagationQueue[i]; |
706 |
1352488 |
Debug("circuit-prop") << "CircuitPropagator::propagate(): processing " |
707 |
676244 |
<< current << std::endl; |
708 |
676244 |
bool assignment = getAssignment(current); |
709 |
1352488 |
Debug("circuit-prop") << "CircuitPropagator::propagate(): assigned to " |
710 |
676244 |
<< (assignment ? "true" : "false") << std::endl; |
711 |
|
|
712 |
|
// Is this an atom |
713 |
2626557 |
bool atom = Theory::theoryOf(current) != THEORY_BOOL || current.isVar() |
714 |
2705120 |
|| (current.getKind() == kind::EQUAL |
715 |
678558 |
&& (current[0].isVar() && current[1].isVar())); |
716 |
|
|
717 |
|
// If an atom, add to the list for simplification |
718 |
676244 |
if (atom |
719 |
791606 |
|| (current.getKind() == kind::EQUAL |
720 |
678414 |
&& (current[0].isVar() || current[1].isVar()))) |
721 |
|
{ |
722 |
230724 |
Debug("circuit-prop") |
723 |
115362 |
<< "CircuitPropagator::propagate(): adding to learned: " |
724 |
115362 |
<< (assignment ? (Node)current : current.notNode()) << std::endl; |
725 |
230724 |
Node lit = assignment ? Node(current) : current.notNode(); |
726 |
|
|
727 |
115362 |
if (isProofEnabled()) |
728 |
|
{ |
729 |
28780 |
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 |
28780 |
ProofGenerator* pg = d_proofInternal.get(); |
734 |
28780 |
if (d_proofExternal != nullptr) |
735 |
|
{ |
736 |
28780 |
d_proofExternal->addLazyStep(lit, pg); |
737 |
28780 |
pg = d_proofExternal.get(); |
738 |
|
} |
739 |
57560 |
TrustNode tlit = TrustNode::mkTrustLemma(lit, pg); |
740 |
28780 |
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 |
173164 |
TrustNode tlit = TrustNode::mkTrustLemma(lit, nullptr); |
753 |
86582 |
d_learnedLiterals.push_back(tlit); |
754 |
|
} |
755 |
115362 |
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 |
676244 |
if (d_backwardPropagation && !atom && !current.isConst()) |
760 |
|
{ |
761 |
551752 |
propagateBackward(current, assignment); |
762 |
|
} |
763 |
|
// Propagate this value to the parents |
764 |
676244 |
if (d_forwardPropagation) |
765 |
|
{ |
766 |
676244 |
propagateForward(current, assignment); |
767 |
|
} |
768 |
|
} |
769 |
|
|
770 |
|
// No conflict |
771 |
11045 |
return d_conflict; |
772 |
|
} |
773 |
|
|
774 |
3786 |
void CircuitPropagator::setProof(ProofNodeManager* pnm, |
775 |
|
context::Context* ctx, |
776 |
|
ProofGenerator* defParent) |
777 |
|
{ |
778 |
3786 |
d_pnm = pnm; |
779 |
3786 |
d_epg.reset(new EagerProofGenerator(pnm, ctx)); |
780 |
11358 |
d_proofInternal.reset(new LazyCDProofChain( |
781 |
7572 |
pnm, true, ctx, d_epg.get(), true, "CircuitPropInternalLazyChain")); |
782 |
3786 |
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 |
7572 |
d_proofExternal.reset(new LazyCDProofChain( |
788 |
3786 |
pnm, true, ctx, defParent, false, "CircuitPropExternalLazyChain")); |
789 |
|
} |
790 |
3786 |
} |
791 |
|
|
792 |
2335257 |
bool CircuitPropagator::isProofEnabled() const |
793 |
|
{ |
794 |
2335257 |
return d_proofInternal != nullptr; |
795 |
|
} |
796 |
|
|
797 |
567513 |
void CircuitPropagator::addProof(TNode f, std::shared_ptr<ProofNode> pf) |
798 |
|
{ |
799 |
567513 |
if (isProofEnabled()) |
800 |
|
{ |
801 |
101727 |
if (!d_epg->hasProofFor(f)) |
802 |
|
{ |
803 |
88462 |
Trace("circuit-prop") << "Adding proof for " << f << std::endl |
804 |
44231 |
<< "\t" << *pf << std::endl; |
805 |
44231 |
d_epg->setProofFor(f, std::move(pf)); |
806 |
|
} |
807 |
|
else |
808 |
|
{ |
809 |
114992 |
auto prf = d_epg->getProofFor(f); |
810 |
114992 |
Trace("circuit-prop") << "Ignoring proof, we already have" << std::endl |
811 |
57496 |
<< "\t" << *prf << std::endl; |
812 |
|
} |
813 |
|
} |
814 |
567513 |
} |
815 |
|
|
816 |
|
} // namespace booleans |
817 |
|
} // namespace theory |
818 |
29502 |
} // namespace cvc5 |