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 |
405907 |
LazyCDProof::LazyCDProof(ProofNodeManager* pnm, |
27 |
|
ProofGenerator* dpg, |
28 |
|
context::Context* c, |
29 |
|
const std::string& name, |
30 |
405907 |
bool autoSym) |
31 |
|
: CDProof(pnm, c, name, autoSym), |
32 |
|
d_gens(c ? c : &d_context), |
33 |
405907 |
d_defaultGen(dpg) |
34 |
|
{ |
35 |
405907 |
} |
36 |
|
|
37 |
499667 |
LazyCDProof::~LazyCDProof() {} |
38 |
|
|
39 |
1812939 |
std::shared_ptr<ProofNode> LazyCDProof::getProofFor(Node fact) |
40 |
|
{ |
41 |
1812939 |
Trace("lazy-cdproof") << "LazyCDProof::mkLazyProof " << fact << std::endl; |
42 |
|
// make the proof, which should always be non-null, since we construct an |
43 |
|
// assumption in the worst case. |
44 |
1812939 |
std::shared_ptr<ProofNode> opf = CDProof::getProofFor(fact); |
45 |
1812939 |
Assert(opf != nullptr); |
46 |
1812939 |
if (!hasGenerators()) |
47 |
|
{ |
48 |
730326 |
Trace("lazy-cdproof") << "...no generators, finished" << std::endl; |
49 |
|
// optimization: no generators, we are done |
50 |
730326 |
return opf; |
51 |
|
} |
52 |
|
// otherwise, we traverse the proof opf and fill in the ASSUME leafs that |
53 |
|
// have generators |
54 |
2165226 |
std::unordered_set<ProofNode*> visited; |
55 |
1082613 |
std::unordered_set<ProofNode*>::iterator it; |
56 |
2165226 |
std::vector<ProofNode*> visit; |
57 |
|
ProofNode* cur; |
58 |
1082613 |
visit.push_back(opf.get()); |
59 |
106745040 |
do |
60 |
|
{ |
61 |
107827653 |
cur = visit.back(); |
62 |
107827653 |
visit.pop_back(); |
63 |
107827653 |
it = visited.find(cur); |
64 |
|
|
65 |
107827653 |
if (it == visited.end()) |
66 |
|
{ |
67 |
47481365 |
visited.insert(cur); |
68 |
94962730 |
Node cfact = cur->getResult(); |
69 |
47481365 |
if (getProof(cfact).get() != cur) |
70 |
|
{ |
71 |
|
// We don't own this proof, skip it. This is to ensure that this method |
72 |
|
// is idempotent, since it may be the case that a previous call to |
73 |
|
// getProofFor connected a proof from a proof generator as a child of |
74 |
|
// a ProofNode in the range of the map in CDProof. Thus, this ensures |
75 |
|
// we don't touch such proofs. |
76 |
1197962 |
Trace("lazy-cdproof") << "...skip unowned proof" << std::endl; |
77 |
|
} |
78 |
46283403 |
else if (cur->getRule() == PfRule::ASSUME) |
79 |
|
{ |
80 |
1071528 |
bool isSym = false; |
81 |
1071528 |
ProofGenerator* pg = getGeneratorFor(cfact, isSym); |
82 |
1071528 |
if (pg != nullptr) |
83 |
|
{ |
84 |
1885750 |
Trace("lazy-cdproof") |
85 |
1885750 |
<< "LazyCDProof: Call generator " << pg->identify() |
86 |
942875 |
<< " for assumption " << cfact << std::endl; |
87 |
1885750 |
Node cfactGen = isSym ? CDProof::getSymmFact(cfact) : cfact; |
88 |
942875 |
Assert(!cfactGen.isNull()); |
89 |
|
// Do not use the addProofTo interface, instead use the update node |
90 |
|
// interface, since this ensures that we don't take ownership for |
91 |
|
// the current proof. Instead, it is only linked, and ignored on |
92 |
|
// future calls to getProofFor due to the check above. |
93 |
1885750 |
std::shared_ptr<ProofNode> pgc = pg->getProofFor(cfactGen); |
94 |
|
// If the proof was null, then the update is not performed. This is |
95 |
|
// not considered an error, since this behavior is equivalent to |
96 |
|
// if pg had provided the proof (ASSUME cfactGen). Ensuring the |
97 |
|
// proper behavior wrt closed proofs should be done outside this |
98 |
|
// method. |
99 |
942875 |
if (pgc != nullptr) |
100 |
|
{ |
101 |
1885750 |
Trace("lazy-cdproof-gen") |
102 |
942875 |
<< "LazyCDProof: stored proof: " << *pgc.get() << std::endl; |
103 |
|
|
104 |
942875 |
if (isSym) |
105 |
|
{ |
106 |
5125 |
if (pgc->getRule() == PfRule::SYMM) |
107 |
|
{ |
108 |
2 |
d_manager->updateNode(cur, pgc->getChildren()[0].get()); |
109 |
|
} |
110 |
|
else |
111 |
|
{ |
112 |
5123 |
d_manager->updateNode(cur, PfRule::SYMM, {pgc}, {}); |
113 |
|
} |
114 |
|
} |
115 |
|
else |
116 |
|
{ |
117 |
937750 |
d_manager->updateNode(cur, pgc.get()); |
118 |
|
} |
119 |
1885750 |
Trace("lazy-cdproof") << "LazyCDProof: Successfully added fact for " |
120 |
942875 |
<< cfactGen << std::endl; |
121 |
|
} |
122 |
|
} |
123 |
|
else |
124 |
|
{ |
125 |
257306 |
Trace("lazy-cdproof") << "LazyCDProof: " << identify() |
126 |
128653 |
<< " : No generator for " << cfact << std::endl; |
127 |
|
} |
128 |
|
// Notice that we do not traverse the proofs that have been generated |
129 |
|
// lazily by the proof generators here. In other words, we assume that |
130 |
|
// the proofs from provided proof generators are final and need |
131 |
|
// no further modification by this class. |
132 |
|
} |
133 |
|
else |
134 |
|
{ |
135 |
45211875 |
const std::vector<std::shared_ptr<ProofNode>>& cc = cur->getChildren(); |
136 |
151956915 |
for (const std::shared_ptr<ProofNode>& cp : cc) |
137 |
|
{ |
138 |
106745040 |
visit.push_back(cp.get()); |
139 |
|
} |
140 |
|
} |
141 |
|
} |
142 |
107827653 |
} while (!visit.empty()); |
143 |
|
// we have now updated the ASSUME leafs of opf, return it |
144 |
1082613 |
Trace("lazy-cdproof") << "...finished" << std::endl; |
145 |
1082613 |
Assert(opf->getResult() == fact); |
146 |
1082613 |
return opf; |
147 |
|
} |
148 |
|
|
149 |
1642717 |
void LazyCDProof::addLazyStep(Node expected, |
150 |
|
ProofGenerator* pg, |
151 |
|
PfRule idNull, |
152 |
|
bool isClosed, |
153 |
|
const char* ctx, |
154 |
|
bool forceOverwrite) |
155 |
|
{ |
156 |
1642717 |
if (pg == nullptr) |
157 |
|
{ |
158 |
|
// null generator, should have given a proof rule |
159 |
28929 |
if (idNull == PfRule::ASSUME) |
160 |
|
{ |
161 |
|
Unreachable() << "LazyCDProof::addLazyStep: " << identify() |
162 |
|
<< ": failed to provide proof generator for " << expected; |
163 |
|
return; |
164 |
|
} |
165 |
57858 |
Trace("lazy-cdproof") << "LazyCDProof::addLazyStep: " << expected |
166 |
28929 |
<< " set (trusted) step " << idNull << "\n"; |
167 |
28929 |
addStep(expected, idNull, {}, {expected}); |
168 |
28929 |
return; |
169 |
|
} |
170 |
3227576 |
Trace("lazy-cdproof") << "LazyCDProof::addLazyStep: " << expected |
171 |
1613788 |
<< " set to generator " << pg->identify() << "\n"; |
172 |
1613788 |
if (!forceOverwrite) |
173 |
|
{ |
174 |
1613788 |
NodeProofGeneratorMap::const_iterator it = d_gens.find(expected); |
175 |
1613788 |
if (it != d_gens.end()) |
176 |
|
{ |
177 |
|
// don't overwrite something that is already there |
178 |
676506 |
return; |
179 |
|
} |
180 |
|
} |
181 |
|
// just store now |
182 |
937282 |
d_gens.insert(expected, pg); |
183 |
|
// debug checking |
184 |
937282 |
if (isClosed) |
185 |
|
{ |
186 |
148057 |
Trace("lazy-cdproof-debug") << "Checking closed..." << std::endl; |
187 |
148057 |
pfgEnsureClosed(expected, pg, "lazy-cdproof-debug", ctx); |
188 |
|
} |
189 |
|
} |
190 |
|
|
191 |
1071528 |
ProofGenerator* LazyCDProof::getGeneratorFor(Node fact, bool& isSym) |
192 |
|
{ |
193 |
1071528 |
isSym = false; |
194 |
1071528 |
NodeProofGeneratorMap::const_iterator it = d_gens.find(fact); |
195 |
1071528 |
if (it != d_gens.end()) |
196 |
|
{ |
197 |
155284 |
return (*it).second; |
198 |
|
} |
199 |
1832488 |
Node factSym = CDProof::getSymmFact(fact); |
200 |
|
// could be symmetry |
201 |
916244 |
if (factSym.isNull()) |
202 |
|
{ |
203 |
|
// can't be symmetry, return the default generator |
204 |
315820 |
return d_defaultGen; |
205 |
|
} |
206 |
600424 |
it = d_gens.find(factSym); |
207 |
600424 |
if (it != d_gens.end()) |
208 |
|
{ |
209 |
5125 |
isSym = true; |
210 |
5125 |
return (*it).second; |
211 |
|
} |
212 |
|
// return the default generator |
213 |
595299 |
return d_defaultGen; |
214 |
|
} |
215 |
|
|
216 |
1812939 |
bool LazyCDProof::hasGenerators() const |
217 |
|
{ |
218 |
1812939 |
return !d_gens.empty() || d_defaultGen != nullptr; |
219 |
|
} |
220 |
|
|
221 |
164044 |
bool LazyCDProof::hasGenerator(Node fact) const |
222 |
|
{ |
223 |
164044 |
if (d_defaultGen != nullptr) |
224 |
|
{ |
225 |
|
return true; |
226 |
|
} |
227 |
164044 |
NodeProofGeneratorMap::const_iterator it = d_gens.find(fact); |
228 |
164044 |
if (it != d_gens.end()) |
229 |
|
{ |
230 |
1630 |
return true; |
231 |
|
} |
232 |
|
// maybe there is a symmetric fact? |
233 |
324828 |
Node factSym = CDProof::getSymmFact(fact); |
234 |
162414 |
if (!factSym.isNull()) |
235 |
|
{ |
236 |
16450 |
it = d_gens.find(factSym); |
237 |
|
} |
238 |
162414 |
return it != d_gens.end(); |
239 |
|
} |
240 |
|
|
241 |
31137 |
} // namespace cvc5 |