blob: 57ec29259653d274cde885fc7f4fe48e9d97048a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
/********************* */
/*! \file sat.cpp
** \verbatim
** Original author: cconway
** Major contributors: mdeters, taking
** Minor contributors (to current version): dejan
** This file is part of the CVC4 prototype.
** Copyright (c) 2009, 2010 The Analysis of Computer Systems Group (ACSys)
** Courant Institute of Mathematical Sciences
** New York University
** See the file COPYING in the top-level source directory for licensing
** information.\endverbatim
**
** \brief [[ Add one-line brief description here ]]
**
** [[ Add lengthier description here ]]
** \todo document this file
**/
#include "cnf_stream.h"
#include "prop_engine.h"
#include "sat.h"
#include "context/context.h"
#include "theory/theory_engine.h"
namespace CVC4 {
namespace prop {
void SatSolver::theoryCheck(theory::Theory::Effort effort, SatClause& conflict) {
// Try theory propagation
bool ok = d_theoryEngine->check(effort);
// If in conflict construct the conflict clause
if (!ok) {
// We have a conflict, get it
Node conflictNode = d_theoryEngine->getConflict();
Debug("prop") << "SatSolver::theoryCheck() => conflict: " << conflictNode << std::endl;
// Go through the literals and construct the conflict clause
Node::const_iterator literal_it = conflictNode.begin();
Node::const_iterator literal_end = conflictNode.end();
while (literal_it != literal_end) {
// Get the literal corresponding to the node
SatLiteral l = d_cnfStream->getLiteral(*literal_it);
// Add the negation to the conflict clause and continue
conflict.push(~l);
literal_it ++;
}
}
}
void SatSolver::theoryPropagate(std::vector<SatLiteral>& output) {
// Propagate
d_theoryEngine->propagate();
// Get the propagated literals
const std::vector<TNode>& outputNodes = d_theoryEngine->getPropagatedLiterals();
// If any literals, make a clause
const unsigned i_end = outputNodes.size();
for (unsigned i = 0; i < i_end; ++ i) {
Debug("prop-explain") << "theoryPropagate() => " << outputNodes[i].toString() << std::endl;
// The second argument ("true") instructs the CNF stream to create
// a new literal mapping if it doesn't exist. This can happen due
// to a circular dependence, if a SAT literal "a" is asserted as a
// unit to the SAT solver, a round of theory propagation can occur
// before all Nodes have SAT variable mappings.
SatLiteral l = d_cnfStream->getLiteral(outputNodes[i], true);
output.push_back(l);
}
}
void SatSolver::explainPropagation(SatLiteral l, SatClause& explanation) {
TNode lNode = d_cnfStream->getNode(l);
Debug("prop-explain") << "explainPropagation(" << lNode.toString() << ")" << std::endl;
Node theoryExplanation = d_theoryEngine->getExplanation(lNode);
Debug("prop-explain") << "explainPropagation() => " << theoryExplanation.toString() << std::endl;
if (theoryExplanation.getKind() == kind::AND) {
Node::const_iterator it = theoryExplanation.begin();
Node::const_iterator it_end = theoryExplanation.end();
explanation.push(l);
for (; it != it_end; ++ it) {
explanation.push(~d_cnfStream->getLiteral(*it));
}
} else {
explanation.push(l);
explanation.push(~d_cnfStream->getLiteral(theoryExplanation));
}
}
void SatSolver::clearPropagatedLiterals() {
d_theoryEngine->clearPropagatedLiterals();
}
void SatSolver::enqueueTheoryLiteral(const SatLiteral& l) {
Node literalNode = d_cnfStream->getNode(l);
Debug("prop") << "enqueueing theory literal " << l << " " << literalNode << std::endl;
// We can get null from the prop engine if the literal is useless (i.e.)
// the expression is not in context anyomore
if(!literalNode.isNull()) {
d_theoryEngine->assertFact(literalNode);
}
}
void SatSolver::setCnfStream(CnfStream* cnfStream) {
d_cnfStream = cnfStream;
}
}/* CVC4::prop namespace */
}/* CVC4 namespace */
|