1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Andrew Reynolds, Aina Niemetz |
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 |
|
* Implementation of lazy proof utility. |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "proof/lazy_proof.h" |
17 |
|
|
18 |
|
#include "proof/proof_ensure_closed.h" |
19 |
|
#include "proof/proof_node.h" |
20 |
|
#include "proof/proof_node_manager.h" |
21 |
|
|
22 |
|
using namespace cvc5::kind; |
23 |
|
|
24 |
|
namespace cvc5 { |
25 |
|
|
26 |
278720 |
LazyCDProof::LazyCDProof(ProofNodeManager* pnm, |
27 |
|
ProofGenerator* dpg, |
28 |
|
context::Context* c, |
29 |
278720 |
const std::string& name) |
30 |
278720 |
: CDProof(pnm, c, name), d_gens(c ? c : &d_context), d_defaultGen(dpg) |
31 |
|
{ |
32 |
278720 |
} |
33 |
|
|
34 |
335285 |
LazyCDProof::~LazyCDProof() {} |
35 |
|
|
36 |
1616199 |
std::shared_ptr<ProofNode> LazyCDProof::getProofFor(Node fact) |
37 |
|
{ |
38 |
1616199 |
Trace("lazy-cdproof") << "LazyCDProof::mkLazyProof " << fact << std::endl; |
39 |
|
// make the proof, which should always be non-null, since we construct an |
40 |
|
// assumption in the worst case. |
41 |
1616199 |
std::shared_ptr<ProofNode> opf = CDProof::getProofFor(fact); |
42 |
1616199 |
Assert(opf != nullptr); |
43 |
1616199 |
if (!hasGenerators()) |
44 |
|
{ |
45 |
663049 |
Trace("lazy-cdproof") << "...no generators, finished" << std::endl; |
46 |
|
// optimization: no generators, we are done |
47 |
663049 |
return opf; |
48 |
|
} |
49 |
|
// otherwise, we traverse the proof opf and fill in the ASSUME leafs that |
50 |
|
// have generators |
51 |
1906300 |
std::unordered_set<ProofNode*> visited; |
52 |
953150 |
std::unordered_set<ProofNode*>::iterator it; |
53 |
1906300 |
std::vector<ProofNode*> visit; |
54 |
|
ProofNode* cur; |
55 |
953150 |
visit.push_back(opf.get()); |
56 |
57651641 |
do |
57 |
|
{ |
58 |
58604791 |
cur = visit.back(); |
59 |
58604791 |
visit.pop_back(); |
60 |
58604791 |
it = visited.find(cur); |
61 |
|
|
62 |
58604791 |
if (it == visited.end()) |
63 |
|
{ |
64 |
12529046 |
visited.insert(cur); |
65 |
25058092 |
Node cfact = cur->getResult(); |
66 |
12529046 |
if (getProof(cfact).get() != cur) |
67 |
|
{ |
68 |
|
// We don't own this proof, skip it. This is to ensure that this method |
69 |
|
// is idempotent, since it may be the case that a previous call to |
70 |
|
// getProofFor connected a proof from a proof generator as a child of |
71 |
|
// a ProofNode in the range of the map in CDProof. Thus, this ensures |
72 |
|
// we don't touch such proofs. |
73 |
892534 |
Trace("lazy-cdproof") << "...skip unowned proof" << std::endl; |
74 |
|
} |
75 |
11636512 |
else if (cur->getRule() == PfRule::ASSUME) |
76 |
|
{ |
77 |
1018994 |
bool isSym = false; |
78 |
1018994 |
ProofGenerator* pg = getGeneratorFor(cfact, isSym); |
79 |
1018994 |
if (pg != nullptr) |
80 |
|
{ |
81 |
1788032 |
Trace("lazy-cdproof") |
82 |
1788032 |
<< "LazyCDProof: Call generator " << pg->identify() |
83 |
894016 |
<< " for assumption " << cfact << std::endl; |
84 |
1788032 |
Node cfactGen = isSym ? CDProof::getSymmFact(cfact) : cfact; |
85 |
894016 |
Assert(!cfactGen.isNull()); |
86 |
|
// Do not use the addProofTo interface, instead use the update node |
87 |
|
// interface, since this ensures that we don't take ownership for |
88 |
|
// the current proof. Instead, it is only linked, and ignored on |
89 |
|
// future calls to getProofFor due to the check above. |
90 |
1788032 |
std::shared_ptr<ProofNode> pgc = pg->getProofFor(cfactGen); |
91 |
|
// If the proof was null, then the update is not performed. This is |
92 |
|
// not considered an error, since this behavior is equivalent to |
93 |
|
// if pg had provided the proof (ASSUME cfactGen). Ensuring the |
94 |
|
// proper behavior wrt closed proofs should be done outside this |
95 |
|
// method. |
96 |
894016 |
if (pgc != nullptr) |
97 |
|
{ |
98 |
1788032 |
Trace("lazy-cdproof-gen") |
99 |
894016 |
<< "LazyCDProof: stored proof: " << *pgc.get() << std::endl; |
100 |
|
|
101 |
894016 |
if (isSym) |
102 |
|
{ |
103 |
4872 |
if (pgc->getRule() == PfRule::SYMM) |
104 |
|
{ |
105 |
2 |
d_manager->updateNode(cur, pgc->getChildren()[0].get()); |
106 |
|
} |
107 |
|
else |
108 |
|
{ |
109 |
4870 |
d_manager->updateNode(cur, PfRule::SYMM, {pgc}, {}); |
110 |
|
} |
111 |
|
} |
112 |
|
else |
113 |
|
{ |
114 |
889144 |
d_manager->updateNode(cur, pgc.get()); |
115 |
|
} |
116 |
1788032 |
Trace("lazy-cdproof") << "LazyCDProof: Successfully added fact for " |
117 |
894016 |
<< cfactGen << std::endl; |
118 |
|
} |
119 |
|
} |
120 |
|
else |
121 |
|
{ |
122 |
249956 |
Trace("lazy-cdproof") << "LazyCDProof: " << identify() |
123 |
124978 |
<< " : No generator for " << cfact << std::endl; |
124 |
|
} |
125 |
|
// Notice that we do not traverse the proofs that have been generated |
126 |
|
// lazily by the proof generators here. In other words, we assume that |
127 |
|
// the proofs from provided proof generators are final and need |
128 |
|
// no further modification by this class. |
129 |
|
} |
130 |
|
else |
131 |
|
{ |
132 |
10617518 |
const std::vector<std::shared_ptr<ProofNode>>& cc = cur->getChildren(); |
133 |
68269159 |
for (const std::shared_ptr<ProofNode>& cp : cc) |
134 |
|
{ |
135 |
57651641 |
visit.push_back(cp.get()); |
136 |
|
} |
137 |
|
} |
138 |
|
} |
139 |
58604791 |
} while (!visit.empty()); |
140 |
|
// we have now updated the ASSUME leafs of opf, return it |
141 |
953150 |
Trace("lazy-cdproof") << "...finished" << std::endl; |
142 |
953150 |
Assert(opf->getResult() == fact); |
143 |
953150 |
return opf; |
144 |
|
} |
145 |
|
|
146 |
1632328 |
void LazyCDProof::addLazyStep(Node expected, |
147 |
|
ProofGenerator* pg, |
148 |
|
PfRule idNull, |
149 |
|
bool isClosed, |
150 |
|
const char* ctx, |
151 |
|
bool forceOverwrite) |
152 |
|
{ |
153 |
1632328 |
if (pg == nullptr) |
154 |
|
{ |
155 |
|
// null generator, should have given a proof rule |
156 |
29388 |
if (idNull == PfRule::ASSUME) |
157 |
|
{ |
158 |
|
Unreachable() << "LazyCDProof::addLazyStep: " << identify() |
159 |
|
<< ": failed to provide proof generator for " << expected; |
160 |
|
return; |
161 |
|
} |
162 |
58776 |
Trace("lazy-cdproof") << "LazyCDProof::addLazyStep: " << expected |
163 |
29388 |
<< " set (trusted) step " << idNull << "\n"; |
164 |
29388 |
addStep(expected, idNull, {}, {expected}); |
165 |
29388 |
return; |
166 |
|
} |
167 |
3205880 |
Trace("lazy-cdproof") << "LazyCDProof::addLazyStep: " << expected |
168 |
1602940 |
<< " set to generator " << pg->identify() << "\n"; |
169 |
1602940 |
if (!forceOverwrite) |
170 |
|
{ |
171 |
1602940 |
NodeProofGeneratorMap::const_iterator it = d_gens.find(expected); |
172 |
1602940 |
if (it != d_gens.end()) |
173 |
|
{ |
174 |
|
// don't overwrite something that is already there |
175 |
668505 |
return; |
176 |
|
} |
177 |
|
} |
178 |
|
// just store now |
179 |
934435 |
d_gens.insert(expected, pg); |
180 |
|
// debug checking |
181 |
934435 |
if (isClosed) |
182 |
|
{ |
183 |
170727 |
Trace("lazy-cdproof-debug") << "Checking closed..." << std::endl; |
184 |
170727 |
pfgEnsureClosed(expected, pg, "lazy-cdproof-debug", ctx); |
185 |
|
} |
186 |
|
} |
187 |
|
|
188 |
1018994 |
ProofGenerator* LazyCDProof::getGeneratorFor(Node fact, bool& isSym) |
189 |
|
{ |
190 |
1018994 |
isSym = false; |
191 |
1018994 |
NodeProofGeneratorMap::const_iterator it = d_gens.find(fact); |
192 |
1018994 |
if (it != d_gens.end()) |
193 |
|
{ |
194 |
144723 |
return (*it).second; |
195 |
|
} |
196 |
1748542 |
Node factSym = CDProof::getSymmFact(fact); |
197 |
|
// could be symmetry |
198 |
874271 |
if (factSym.isNull()) |
199 |
|
{ |
200 |
|
// can't be symmetry, return the default generator |
201 |
257384 |
return d_defaultGen; |
202 |
|
} |
203 |
616887 |
it = d_gens.find(factSym); |
204 |
616887 |
if (it != d_gens.end()) |
205 |
|
{ |
206 |
4872 |
isSym = true; |
207 |
4872 |
return (*it).second; |
208 |
|
} |
209 |
|
// return the default generator |
210 |
612015 |
return d_defaultGen; |
211 |
|
} |
212 |
|
|
213 |
1616199 |
bool LazyCDProof::hasGenerators() const |
214 |
|
{ |
215 |
1616199 |
return !d_gens.empty() || d_defaultGen != nullptr; |
216 |
|
} |
217 |
|
|
218 |
155420 |
bool LazyCDProof::hasGenerator(Node fact) const |
219 |
|
{ |
220 |
155420 |
if (d_defaultGen != nullptr) |
221 |
|
{ |
222 |
|
return true; |
223 |
|
} |
224 |
155420 |
NodeProofGeneratorMap::const_iterator it = d_gens.find(fact); |
225 |
155420 |
if (it != d_gens.end()) |
226 |
|
{ |
227 |
1535 |
return true; |
228 |
|
} |
229 |
|
// maybe there is a symmetric fact? |
230 |
307770 |
Node factSym = CDProof::getSymmFact(fact); |
231 |
153885 |
if (!factSym.isNull()) |
232 |
|
{ |
233 |
13417 |
it = d_gens.find(factSym); |
234 |
|
} |
235 |
153885 |
return it != d_gens.end(); |
236 |
|
} |
237 |
|
|
238 |
29505 |
} // namespace cvc5 |