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 "expr/lazy_proof.h" |
17 |
|
|
18 |
|
#include "expr/proof_ensure_closed.h" |
19 |
|
#include "expr/proof_node.h" |
20 |
|
#include "expr/proof_node_manager.h" |
21 |
|
|
22 |
|
using namespace cvc5::kind; |
23 |
|
|
24 |
|
namespace cvc5 { |
25 |
|
|
26 |
269947 |
LazyCDProof::LazyCDProof(ProofNodeManager* pnm, |
27 |
|
ProofGenerator* dpg, |
28 |
|
context::Context* c, |
29 |
269947 |
std::string name) |
30 |
269947 |
: CDProof(pnm, c, name), d_gens(c ? c : &d_context), d_defaultGen(dpg) |
31 |
|
{ |
32 |
269947 |
} |
33 |
|
|
34 |
325764 |
LazyCDProof::~LazyCDProof() {} |
35 |
|
|
36 |
1594531 |
std::shared_ptr<ProofNode> LazyCDProof::getProofFor(Node fact) |
37 |
|
{ |
38 |
1594531 |
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 |
1594531 |
std::shared_ptr<ProofNode> opf = CDProof::getProofFor(fact); |
42 |
1594531 |
Assert(opf != nullptr); |
43 |
1594531 |
if (!hasGenerators()) |
44 |
|
{ |
45 |
694144 |
Trace("lazy-cdproof") << "...no generators, finished" << std::endl; |
46 |
|
// optimization: no generators, we are done |
47 |
694144 |
return opf; |
48 |
|
} |
49 |
|
// otherwise, we traverse the proof opf and fill in the ASSUME leafs that |
50 |
|
// have generators |
51 |
1800774 |
std::unordered_set<ProofNode*> visited; |
52 |
900387 |
std::unordered_set<ProofNode*>::iterator it; |
53 |
1800774 |
std::vector<ProofNode*> visit; |
54 |
|
ProofNode* cur; |
55 |
900387 |
visit.push_back(opf.get()); |
56 |
57421574 |
do |
57 |
|
{ |
58 |
58321961 |
cur = visit.back(); |
59 |
58321961 |
visit.pop_back(); |
60 |
58321961 |
it = visited.find(cur); |
61 |
|
|
62 |
58321961 |
if (it == visited.end()) |
63 |
|
{ |
64 |
18298897 |
visited.insert(cur); |
65 |
36597794 |
Node cfact = cur->getResult(); |
66 |
18298897 |
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 |
485383 |
Trace("lazy-cdproof") << "...skip unowned proof" << std::endl; |
74 |
|
} |
75 |
17813514 |
else if (cur->getRule() == PfRule::ASSUME) |
76 |
|
{ |
77 |
1057967 |
bool isSym = false; |
78 |
1057967 |
ProofGenerator* pg = getGeneratorFor(cfact, isSym); |
79 |
1057967 |
if (pg != nullptr) |
80 |
|
{ |
81 |
1818986 |
Trace("lazy-cdproof") |
82 |
1818986 |
<< "LazyCDProof: Call generator " << pg->identify() |
83 |
909493 |
<< " for assumption " << cfact << std::endl; |
84 |
1818986 |
Node cfactGen = isSym ? CDProof::getSymmFact(cfact) : cfact; |
85 |
909493 |
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 |
1818986 |
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 |
909493 |
if (pgc != nullptr) |
97 |
|
{ |
98 |
1818986 |
Trace("lazy-cdproof-gen") |
99 |
909493 |
<< "LazyCDProof: stored proof: " << *pgc.get() << std::endl; |
100 |
|
|
101 |
909493 |
if (isSym) |
102 |
|
{ |
103 |
8109 |
d_manager->updateNode(cur, PfRule::SYMM, {pgc}, {}); |
104 |
|
} |
105 |
|
else |
106 |
|
{ |
107 |
901384 |
d_manager->updateNode(cur, pgc.get()); |
108 |
|
} |
109 |
1818986 |
Trace("lazy-cdproof") << "LazyCDProof: Successfully added fact for " |
110 |
909493 |
<< cfactGen << std::endl; |
111 |
|
} |
112 |
|
} |
113 |
|
else |
114 |
|
{ |
115 |
296948 |
Trace("lazy-cdproof") << "LazyCDProof: " << identify() |
116 |
148474 |
<< " : No generator for " << cfact << std::endl; |
117 |
|
} |
118 |
|
// Notice that we do not traverse the proofs that have been generated |
119 |
|
// lazily by the proof generators here. In other words, we assume that |
120 |
|
// the proofs from provided proof generators are final and need |
121 |
|
// no further modification by this class. |
122 |
|
} |
123 |
|
else |
124 |
|
{ |
125 |
16755547 |
const std::vector<std::shared_ptr<ProofNode>>& cc = cur->getChildren(); |
126 |
74177121 |
for (const std::shared_ptr<ProofNode>& cp : cc) |
127 |
|
{ |
128 |
57421574 |
visit.push_back(cp.get()); |
129 |
|
} |
130 |
|
} |
131 |
|
} |
132 |
58321961 |
} while (!visit.empty()); |
133 |
|
// we have now updated the ASSUME leafs of opf, return it |
134 |
900387 |
Trace("lazy-cdproof") << "...finished" << std::endl; |
135 |
900387 |
Assert(opf->getResult() == fact); |
136 |
900387 |
return opf; |
137 |
|
} |
138 |
|
|
139 |
1104333 |
void LazyCDProof::addLazyStep(Node expected, |
140 |
|
ProofGenerator* pg, |
141 |
|
PfRule idNull, |
142 |
|
bool isClosed, |
143 |
|
const char* ctx, |
144 |
|
bool forceOverwrite) |
145 |
|
{ |
146 |
1104333 |
if (pg == nullptr) |
147 |
|
{ |
148 |
|
// null generator, should have given a proof rule |
149 |
28424 |
if (idNull == PfRule::ASSUME) |
150 |
|
{ |
151 |
|
Unreachable() << "LazyCDProof::addLazyStep: " << identify() |
152 |
|
<< ": failed to provide proof generator for " << expected; |
153 |
|
return; |
154 |
|
} |
155 |
56848 |
Trace("lazy-cdproof") << "LazyCDProof::addLazyStep: " << expected |
156 |
28424 |
<< " set (trusted) step " << idNull << "\n"; |
157 |
28424 |
addStep(expected, idNull, {}, {expected}); |
158 |
28424 |
return; |
159 |
|
} |
160 |
2151818 |
Trace("lazy-cdproof") << "LazyCDProof::addLazyStep: " << expected |
161 |
1075909 |
<< " set to generator " << pg->identify() << "\n"; |
162 |
1075909 |
if (!forceOverwrite) |
163 |
|
{ |
164 |
1075909 |
NodeProofGeneratorMap::const_iterator it = d_gens.find(expected); |
165 |
1075909 |
if (it != d_gens.end()) |
166 |
|
{ |
167 |
|
// don't overwrite something that is already there |
168 |
445676 |
return; |
169 |
|
} |
170 |
|
} |
171 |
|
// just store now |
172 |
630233 |
d_gens.insert(expected, pg); |
173 |
|
// debug checking |
174 |
630233 |
if (isClosed) |
175 |
|
{ |
176 |
158836 |
Trace("lazy-cdproof-debug") << "Checking closed..." << std::endl; |
177 |
158836 |
pfgEnsureClosed(expected, pg, "lazy-cdproof-debug", ctx); |
178 |
|
} |
179 |
|
} |
180 |
|
|
181 |
1057967 |
ProofGenerator* LazyCDProof::getGeneratorFor(Node fact, |
182 |
|
bool& isSym) |
183 |
|
{ |
184 |
1057967 |
isSym = false; |
185 |
1057967 |
NodeProofGeneratorMap::const_iterator it = d_gens.find(fact); |
186 |
1057967 |
if (it != d_gens.end()) |
187 |
|
{ |
188 |
145550 |
return (*it).second; |
189 |
|
} |
190 |
1824834 |
Node factSym = CDProof::getSymmFact(fact); |
191 |
|
// could be symmetry |
192 |
912417 |
if (factSym.isNull()) |
193 |
|
{ |
194 |
|
// can't be symmetry, return the default generator |
195 |
261954 |
return d_defaultGen; |
196 |
|
} |
197 |
650463 |
it = d_gens.find(factSym); |
198 |
650463 |
if (it != d_gens.end()) |
199 |
|
{ |
200 |
8109 |
isSym = true; |
201 |
8109 |
return (*it).second; |
202 |
|
} |
203 |
|
// return the default generator |
204 |
642354 |
return d_defaultGen; |
205 |
|
} |
206 |
|
|
207 |
1594531 |
bool LazyCDProof::hasGenerators() const |
208 |
|
{ |
209 |
1594531 |
return !d_gens.empty() || d_defaultGen != nullptr; |
210 |
|
} |
211 |
|
|
212 |
389539 |
bool LazyCDProof::hasGenerator(Node fact) const |
213 |
|
{ |
214 |
389539 |
if (d_defaultGen != nullptr) |
215 |
|
{ |
216 |
|
return true; |
217 |
|
} |
218 |
389539 |
NodeProofGeneratorMap::const_iterator it = d_gens.find(fact); |
219 |
389539 |
if (it != d_gens.end()) |
220 |
|
{ |
221 |
1435 |
return true; |
222 |
|
} |
223 |
|
// maybe there is a symmetric fact? |
224 |
776208 |
Node factSym = CDProof::getSymmFact(fact); |
225 |
388104 |
if (!factSym.isNull()) |
226 |
|
{ |
227 |
12355 |
it = d_gens.find(factSym); |
228 |
|
} |
229 |
388104 |
return it != d_gens.end(); |
230 |
|
} |
231 |
|
|
232 |
28194 |
} // namespace cvc5 |