1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Andrew Reynolds, Haniel Barbosa |
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 a utility for updating proof nodes. |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "proof/proof_node_updater.h" |
17 |
|
|
18 |
|
#include "proof/lazy_proof.h" |
19 |
|
#include "proof/proof_ensure_closed.h" |
20 |
|
#include "proof/proof_node_algorithm.h" |
21 |
|
#include "proof/proof_node_manager.h" |
22 |
|
|
23 |
|
namespace cvc5 { |
24 |
|
|
25 |
8790 |
ProofNodeUpdaterCallback::ProofNodeUpdaterCallback() {} |
26 |
8790 |
ProofNodeUpdaterCallback::~ProofNodeUpdaterCallback() {} |
27 |
|
|
28 |
|
bool ProofNodeUpdaterCallback::update(Node res, |
29 |
|
PfRule id, |
30 |
|
const std::vector<Node>& children, |
31 |
|
const std::vector<Node>& args, |
32 |
|
CDProof* cdp, |
33 |
|
bool& continueUpdate) |
34 |
|
{ |
35 |
|
return false; |
36 |
|
} |
37 |
|
|
38 |
10347 |
ProofNodeUpdater::ProofNodeUpdater(ProofNodeManager* pnm, |
39 |
|
ProofNodeUpdaterCallback& cb, |
40 |
|
bool mergeSubproofs, |
41 |
10347 |
bool autoSym) |
42 |
|
: d_pnm(pnm), |
43 |
|
d_cb(cb), |
44 |
|
d_debugFreeAssumps(false), |
45 |
|
d_mergeSubproofs(mergeSubproofs), |
46 |
10347 |
d_autoSym(autoSym) |
47 |
|
{ |
48 |
10347 |
} |
49 |
|
|
50 |
8417 |
void ProofNodeUpdater::process(std::shared_ptr<ProofNode> pf) |
51 |
|
{ |
52 |
8417 |
if (d_debugFreeAssumps) |
53 |
|
{ |
54 |
|
if (Trace.isOn("pfnu-debug")) |
55 |
|
{ |
56 |
|
Trace("pfnu-debug2") << "Initial proof: " << *pf.get() << std::endl; |
57 |
|
Trace("pfnu-debug") << "ProofNodeUpdater::process" << std::endl; |
58 |
|
Trace("pfnu-debug") << "Expected free assumptions: " << std::endl; |
59 |
|
for (const Node& fa : d_freeAssumps) |
60 |
|
{ |
61 |
|
Trace("pfnu-debug") << "- " << fa << std::endl; |
62 |
|
} |
63 |
|
std::vector<Node> assump; |
64 |
|
expr::getFreeAssumptions(pf.get(), assump); |
65 |
|
Trace("pfnu-debug") << "Current free assumptions: " << std::endl; |
66 |
|
for (const Node& fa : assump) |
67 |
|
{ |
68 |
|
Trace("pfnu-debug") << "- " << fa << std::endl; |
69 |
|
} |
70 |
|
} |
71 |
|
} |
72 |
8417 |
processInternal(pf, d_freeAssumps); |
73 |
8417 |
} |
74 |
|
|
75 |
8417 |
void ProofNodeUpdater::processInternal(std::shared_ptr<ProofNode> pf, |
76 |
|
std::vector<Node>& fa) |
77 |
|
{ |
78 |
|
// Note that processInternal uses a single scope; fa is updated based on |
79 |
|
// the current free assumptions of the proof nodes on the stack. |
80 |
|
|
81 |
|
// The list of proof nodes we are currently traversing beneath. This is used |
82 |
|
// for checking for cycles in the overall proof. |
83 |
16834 |
std::vector<std::shared_ptr<ProofNode>> traversing; |
84 |
|
// Map from formulas to (closed) proof nodes that prove that fact |
85 |
16834 |
std::map<Node, std::shared_ptr<ProofNode>> resCache; |
86 |
|
// Map from formulas to non-closed proof nodes that prove that fact. These |
87 |
|
// are replaced by proofs in the above map when applicable. |
88 |
16834 |
std::map<Node, std::vector<std::shared_ptr<ProofNode>>> resCacheNcWaiting; |
89 |
|
// Map from proof nodes to whether they contain assumptions |
90 |
16834 |
std::unordered_map<const ProofNode*, bool> cfaMap; |
91 |
8417 |
Trace("pf-process") << "ProofNodeUpdater::process" << std::endl; |
92 |
16834 |
std::unordered_map<std::shared_ptr<ProofNode>, bool> visited; |
93 |
8417 |
std::unordered_map<std::shared_ptr<ProofNode>, bool>::iterator it; |
94 |
16834 |
std::vector<std::shared_ptr<ProofNode>> visit; |
95 |
16834 |
std::shared_ptr<ProofNode> cur; |
96 |
8417 |
visit.push_back(pf); |
97 |
8417 |
std::map<Node, std::shared_ptr<ProofNode>>::iterator itc; |
98 |
16834 |
Node res; |
99 |
15936146 |
do |
100 |
|
{ |
101 |
15944563 |
cur = visit.back(); |
102 |
15944563 |
visit.pop_back(); |
103 |
15944563 |
it = visited.find(cur); |
104 |
15944563 |
res = cur->getResult(); |
105 |
15944563 |
if (it == visited.end()) |
106 |
|
{ |
107 |
5854105 |
if (d_mergeSubproofs) |
108 |
|
{ |
109 |
2482105 |
itc = resCache.find(res); |
110 |
2705174 |
if (itc != resCache.end()) |
111 |
|
{ |
112 |
|
// already have a proof, merge it into this one |
113 |
223069 |
visited[cur] = true; |
114 |
223069 |
d_pnm->updateNode(cur.get(), itc->second.get()); |
115 |
|
// does not contain free assumptions since the range of resCache does |
116 |
|
// not contain free assumptions |
117 |
223069 |
cfaMap[cur.get()] = false; |
118 |
1001264 |
continue; |
119 |
|
} |
120 |
|
} |
121 |
|
// run update to a fixed point |
122 |
5631036 |
bool continueUpdate = true; |
123 |
5978666 |
while (runUpdate(cur, fa, continueUpdate) && continueUpdate) |
124 |
|
{ |
125 |
173815 |
Trace("pf-process-debug") << "...updated proof." << std::endl; |
126 |
|
} |
127 |
5631036 |
visited[cur] = !continueUpdate; |
128 |
6186162 |
if (!continueUpdate) |
129 |
|
{ |
130 |
|
// no further changes should be made to cur according to the callback |
131 |
1110252 |
Trace("pf-process-debug") |
132 |
555126 |
<< "...marked to not continue update." << std::endl; |
133 |
555126 |
runFinalize(cur, fa, resCache, resCacheNcWaiting, cfaMap); |
134 |
555126 |
continue; |
135 |
|
} |
136 |
5075910 |
traversing.push_back(cur); |
137 |
5075910 |
visit.push_back(cur); |
138 |
|
// If we are not the top-level proof, we were a scope, or became a scope |
139 |
|
// after updating, we do a separate recursive call to this method. This |
140 |
|
// allows us to properly track the assumptions in scope, which is |
141 |
|
// important for example to merge or to determine updates based on free |
142 |
|
// assumptions. |
143 |
5075910 |
if (cur->getRule() == PfRule::SCOPE) |
144 |
|
{ |
145 |
78563 |
const std::vector<Node>& args = cur->getArguments(); |
146 |
78563 |
fa.insert(fa.end(), args.begin(), args.end()); |
147 |
|
} |
148 |
5075910 |
const std::vector<std::shared_ptr<ProofNode>>& ccp = cur->getChildren(); |
149 |
|
// now, process children |
150 |
15936146 |
for (const std::shared_ptr<ProofNode>& cp : ccp) |
151 |
|
{ |
152 |
32580708 |
if (std::find(traversing.begin(), traversing.end(), cp) |
153 |
32580708 |
!= traversing.end()) |
154 |
|
{ |
155 |
|
Unhandled() |
156 |
|
<< "ProofNodeUpdater::processInternal: cyclic proof! (use " |
157 |
|
"--proof-eager-checking)" |
158 |
|
<< std::endl; |
159 |
|
} |
160 |
10860236 |
visit.push_back(cp); |
161 |
|
} |
162 |
|
} |
163 |
10090458 |
else if (!it->second) |
164 |
|
{ |
165 |
5075910 |
Assert(!traversing.empty()); |
166 |
5075910 |
traversing.pop_back(); |
167 |
5075910 |
visited[cur] = true; |
168 |
|
// finalize the node |
169 |
5075910 |
if (cur->getRule() == PfRule::SCOPE) |
170 |
|
{ |
171 |
78563 |
const std::vector<Node>& args = cur->getArguments(); |
172 |
78563 |
Assert(fa.size() >= args.size()); |
173 |
78563 |
fa.resize(fa.size() - args.size()); |
174 |
|
} |
175 |
5075910 |
runFinalize(cur, fa, resCache, resCacheNcWaiting, cfaMap); |
176 |
|
} |
177 |
15944563 |
} while (!visit.empty()); |
178 |
8417 |
Trace("pf-process") << "ProofNodeUpdater::process: finished" << std::endl; |
179 |
8417 |
} |
180 |
|
|
181 |
5804851 |
bool ProofNodeUpdater::runUpdate(std::shared_ptr<ProofNode> cur, |
182 |
|
const std::vector<Node>& fa, |
183 |
|
bool& continueUpdate) |
184 |
|
{ |
185 |
|
// should it be updated? |
186 |
5804851 |
if (!d_cb.shouldUpdate(cur, fa, continueUpdate)) |
187 |
|
{ |
188 |
4815016 |
return false; |
189 |
|
} |
190 |
989835 |
PfRule id = cur->getRule(); |
191 |
|
// use CDProof to open a scope for which the callback updates |
192 |
1979670 |
CDProof cpf(d_pnm, nullptr, "ProofNodeUpdater::CDProof", d_autoSym); |
193 |
989835 |
const std::vector<std::shared_ptr<ProofNode>>& cc = cur->getChildren(); |
194 |
1979670 |
std::vector<Node> ccn; |
195 |
2969680 |
for (const std::shared_ptr<ProofNode>& cp : cc) |
196 |
|
{ |
197 |
3959690 |
Node cpres = cp->getResult(); |
198 |
1979845 |
ccn.push_back(cpres); |
199 |
|
// store in the proof |
200 |
1979845 |
cpf.addProof(cp); |
201 |
|
} |
202 |
1979670 |
Node res = cur->getResult(); |
203 |
1979670 |
Trace("pf-process-debug") |
204 |
989835 |
<< "Updating (" << cur->getRule() << "): " << res << std::endl; |
205 |
|
// only if the callback updated the node |
206 |
989835 |
if (d_cb.update(res, id, ccn, cur->getArguments(), &cpf, continueUpdate)) |
207 |
|
{ |
208 |
1457882 |
std::shared_ptr<ProofNode> npn = cpf.getProofFor(res); |
209 |
1457882 |
std::vector<Node> fullFa; |
210 |
728941 |
if (d_debugFreeAssumps) |
211 |
|
{ |
212 |
|
expr::getFreeAssumptions(cur.get(), fullFa); |
213 |
|
Trace("pfnu-debug") << "Original proof : " << *cur << std::endl; |
214 |
|
} |
215 |
|
// then, update the original proof node based on this one |
216 |
728941 |
Trace("pf-process-debug") << "Update node..." << std::endl; |
217 |
728941 |
d_pnm->updateNode(cur.get(), npn.get()); |
218 |
728941 |
Trace("pf-process-debug") << "...update node finished." << std::endl; |
219 |
728941 |
if (d_debugFreeAssumps) |
220 |
|
{ |
221 |
|
fullFa.insert(fullFa.end(), fa.begin(), fa.end()); |
222 |
|
// We have that npn is a node we occurring the final updated version of |
223 |
|
// the proof. We can now debug based on the expected set of free |
224 |
|
// assumptions. |
225 |
|
Trace("pfnu-debug") << "Ensure update closed..." << std::endl; |
226 |
|
pfnEnsureClosedWrt( |
227 |
|
npn.get(), fullFa, "pfnu-debug", "ProofNodeUpdater:postupdate"); |
228 |
|
} |
229 |
728941 |
Trace("pf-process-debug") << "..finished" << std::endl; |
230 |
728941 |
return true; |
231 |
|
} |
232 |
260894 |
Trace("pf-process-debug") << "..finished" << std::endl; |
233 |
260894 |
return false; |
234 |
|
} |
235 |
|
|
236 |
5631036 |
void ProofNodeUpdater::runFinalize( |
237 |
|
std::shared_ptr<ProofNode> cur, |
238 |
|
const std::vector<Node>& fa, |
239 |
|
std::map<Node, std::shared_ptr<ProofNode>>& resCache, |
240 |
|
std::map<Node, std::vector<std::shared_ptr<ProofNode>>>& resCacheNcWaiting, |
241 |
|
std::unordered_map<const ProofNode*, bool>& cfaMap) |
242 |
|
{ |
243 |
5631036 |
if (d_mergeSubproofs) |
244 |
|
{ |
245 |
4518072 |
Node res = cur->getResult(); |
246 |
|
// cache the result if we don't contain an assumption |
247 |
2259036 |
if (!expr::containsAssumption(cur.get(), cfaMap)) |
248 |
|
{ |
249 |
|
// cache result if we are merging subproofs |
250 |
665056 |
resCache[res] = cur; |
251 |
|
// go back and merge into the non-closed proofs of the same fact |
252 |
|
std::map<Node, std::vector<std::shared_ptr<ProofNode>>>::iterator itnw = |
253 |
665056 |
resCacheNcWaiting.find(res); |
254 |
665056 |
if (itnw != resCacheNcWaiting.end()) |
255 |
|
{ |
256 |
597 |
for (std::shared_ptr<ProofNode>& ncp : itnw->second) |
257 |
|
{ |
258 |
323 |
d_pnm->updateNode(ncp.get(), cur.get()); |
259 |
|
} |
260 |
274 |
resCacheNcWaiting.erase(res); |
261 |
|
} |
262 |
|
} |
263 |
|
else |
264 |
|
{ |
265 |
1593980 |
resCacheNcWaiting[res].push_back(cur); |
266 |
|
} |
267 |
|
} |
268 |
5631036 |
if (d_debugFreeAssumps) |
269 |
|
{ |
270 |
|
// We have that npn is a node we occurring the final updated version of |
271 |
|
// the proof. We can now debug based on the expected set of free |
272 |
|
// assumptions. |
273 |
|
Trace("pfnu-debug") << "Ensure update closed..." << std::endl; |
274 |
|
pfnEnsureClosedWrt( |
275 |
|
cur.get(), fa, "pfnu-debug", "ProofNodeUpdater:finalize"); |
276 |
|
} |
277 |
5631036 |
} |
278 |
|
|
279 |
|
void ProofNodeUpdater::setDebugFreeAssumptions( |
280 |
|
const std::vector<Node>& freeAssumps) |
281 |
|
{ |
282 |
|
d_freeAssumps.clear(); |
283 |
|
d_freeAssumps.insert( |
284 |
|
d_freeAssumps.end(), freeAssumps.begin(), freeAssumps.end()); |
285 |
|
d_debugFreeAssumps = true; |
286 |
|
} |
287 |
|
|
288 |
29322 |
} // namespace cvc5 |