1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Andrew Reynolds |
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 |
|
* Theory UF rewriter |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "theory/uf/theory_uf_rewriter.h" |
17 |
|
|
18 |
|
#include "expr/node_algorithm.h" |
19 |
|
#include "theory/rewriter.h" |
20 |
|
#include "theory/substitutions.h" |
21 |
|
|
22 |
|
namespace cvc5 { |
23 |
|
namespace theory { |
24 |
|
namespace uf { |
25 |
|
|
26 |
15271 |
TheoryUfRewriter::TheoryUfRewriter(bool isHigherOrder) |
27 |
15271 |
: d_isHigherOrder(isHigherOrder) |
28 |
|
{ |
29 |
15271 |
} |
30 |
|
|
31 |
813638 |
RewriteResponse TheoryUfRewriter::postRewrite(TNode node) |
32 |
|
{ |
33 |
813638 |
if (node.getKind() == kind::EQUAL) |
34 |
|
{ |
35 |
164848 |
if (node[0] == node[1]) |
36 |
|
{ |
37 |
|
return RewriteResponse(REWRITE_DONE, |
38 |
54 |
NodeManager::currentNM()->mkConst(true)); |
39 |
|
} |
40 |
164794 |
else if (node[0].isConst() && node[1].isConst()) |
41 |
|
{ |
42 |
|
// uninterpreted constants are all distinct |
43 |
|
return RewriteResponse(REWRITE_DONE, |
44 |
30 |
NodeManager::currentNM()->mkConst(false)); |
45 |
|
} |
46 |
164764 |
if (node[0] > node[1]) |
47 |
|
{ |
48 |
|
Node newNode = |
49 |
61282 |
NodeManager::currentNM()->mkNode(node.getKind(), node[1], node[0]); |
50 |
30641 |
return RewriteResponse(REWRITE_DONE, newNode); |
51 |
|
} |
52 |
|
} |
53 |
782913 |
if (node.getKind() == kind::APPLY_UF) |
54 |
|
{ |
55 |
626410 |
if (node.getOperator().getKind() == kind::LAMBDA) |
56 |
|
{ |
57 |
23868 |
Trace("uf-ho-beta") << "uf-ho-beta : beta-reducing all args of : " << node |
58 |
11934 |
<< "\n"; |
59 |
23868 |
TNode lambda = node.getOperator(); |
60 |
23868 |
Node ret; |
61 |
|
// build capture-avoiding substitution since in HOL shadowing may have |
62 |
|
// been introduced |
63 |
11934 |
if (d_isHigherOrder) |
64 |
|
{ |
65 |
758 |
std::vector<Node> vars; |
66 |
758 |
std::vector<Node> subs; |
67 |
1122 |
for (const Node& v : lambda[0]) |
68 |
|
{ |
69 |
743 |
vars.push_back(v); |
70 |
|
} |
71 |
1122 |
for (const Node& s : node) |
72 |
|
{ |
73 |
743 |
subs.push_back(s); |
74 |
|
} |
75 |
379 |
if (Trace.isOn("uf-ho-beta")) |
76 |
|
{ |
77 |
|
Trace("uf-ho-beta") << "uf-ho-beta: ..sub of " << subs.size() |
78 |
|
<< " vars into " << subs.size() << " terms :\n"; |
79 |
|
for (unsigned i = 0, size = subs.size(); i < size; ++i) |
80 |
|
{ |
81 |
|
Trace("uf-ho-beta") |
82 |
|
<< "uf-ho-beta: .... " << vars[i] << " |-> " << subs[i] << "\n"; |
83 |
|
} |
84 |
|
} |
85 |
379 |
ret = expr::substituteCaptureAvoiding(lambda[1], vars, subs); |
86 |
379 |
Trace("uf-ho-beta") << "uf-ho-beta : ..result : " << ret << "\n"; |
87 |
|
} |
88 |
|
else |
89 |
|
{ |
90 |
23110 |
std::vector<TNode> vars(lambda[0].begin(), lambda[0].end()); |
91 |
23110 |
std::vector<TNode> subs(node.begin(), node.end()); |
92 |
11555 |
ret = lambda[1].substitute( |
93 |
|
vars.begin(), vars.end(), subs.begin(), subs.end()); |
94 |
|
} |
95 |
11934 |
return RewriteResponse(REWRITE_AGAIN_FULL, ret); |
96 |
|
} |
97 |
614476 |
else if (!canUseAsApplyUfOperator(node.getOperator())) |
98 |
|
{ |
99 |
38 |
return RewriteResponse(REWRITE_AGAIN_FULL, getHoApplyForApplyUf(node)); |
100 |
|
} |
101 |
|
} |
102 |
156503 |
else if (node.getKind() == kind::HO_APPLY) |
103 |
|
{ |
104 |
18568 |
if (node[0].getKind() == kind::LAMBDA) |
105 |
|
{ |
106 |
|
// resolve one argument of the lambda |
107 |
316 |
Trace("uf-ho-beta") << "uf-ho-beta : beta-reducing one argument of : " |
108 |
158 |
<< node[0] << " with " << node[1] << "\n"; |
109 |
|
|
110 |
|
// reconstruct the lambda first to avoid variable shadowing |
111 |
316 |
Node new_body = node[0][1]; |
112 |
158 |
if (node[0][0].getNumChildren() > 1) |
113 |
|
{ |
114 |
186 |
std::vector<Node> new_vars(node[0][0].begin() + 1, node[0][0].end()); |
115 |
186 |
std::vector<Node> largs; |
116 |
93 |
largs.push_back( |
117 |
186 |
NodeManager::currentNM()->mkNode(kind::BOUND_VAR_LIST, new_vars)); |
118 |
93 |
largs.push_back(new_body); |
119 |
93 |
new_body = NodeManager::currentNM()->mkNode(kind::LAMBDA, largs); |
120 |
186 |
Trace("uf-ho-beta") |
121 |
93 |
<< "uf-ho-beta : ....new lambda : " << new_body << "\n"; |
122 |
|
} |
123 |
|
|
124 |
|
// build capture-avoiding substitution since in HOL shadowing may have |
125 |
|
// been introduced |
126 |
158 |
if (d_isHigherOrder) |
127 |
|
{ |
128 |
316 |
Node arg = Rewriter::rewrite(node[1]); |
129 |
316 |
Node var = node[0][0][0]; |
130 |
158 |
new_body = expr::substituteCaptureAvoiding(new_body, var, arg); |
131 |
|
} |
132 |
|
else |
133 |
|
{ |
134 |
|
TNode arg = Rewriter::rewrite(node[1]); |
135 |
|
TNode var = node[0][0][0]; |
136 |
|
new_body = new_body.substitute(var, arg); |
137 |
|
} |
138 |
158 |
Trace("uf-ho-beta") << "uf-ho-beta : ..new body : " << new_body << "\n"; |
139 |
158 |
return RewriteResponse(REWRITE_AGAIN_FULL, new_body); |
140 |
|
} |
141 |
|
} |
142 |
770783 |
return RewriteResponse(REWRITE_DONE, node); |
143 |
|
} |
144 |
|
|
145 |
426491 |
RewriteResponse TheoryUfRewriter::preRewrite(TNode node) |
146 |
|
{ |
147 |
426491 |
if (node.getKind() == kind::EQUAL) |
148 |
|
{ |
149 |
92400 |
if (node[0] == node[1]) |
150 |
|
{ |
151 |
|
return RewriteResponse(REWRITE_DONE, |
152 |
2852 |
NodeManager::currentNM()->mkConst(true)); |
153 |
|
} |
154 |
89548 |
else if (node[0].isConst() && node[1].isConst()) |
155 |
|
{ |
156 |
|
// uninterpreted constants are all distinct |
157 |
|
return RewriteResponse(REWRITE_DONE, |
158 |
6370 |
NodeManager::currentNM()->mkConst(false)); |
159 |
|
} |
160 |
|
} |
161 |
417269 |
return RewriteResponse(REWRITE_DONE, node); |
162 |
|
} |
163 |
|
|
164 |
684288 |
Node TheoryUfRewriter::getHoApplyForApplyUf(TNode n) |
165 |
|
{ |
166 |
684288 |
Assert(n.getKind() == kind::APPLY_UF); |
167 |
684288 |
Node curr = n.getOperator(); |
168 |
2051153 |
for (unsigned i = 0; i < n.getNumChildren(); i++) |
169 |
|
{ |
170 |
1366865 |
curr = NodeManager::currentNM()->mkNode(kind::HO_APPLY, curr, n[i]); |
171 |
|
} |
172 |
684288 |
return curr; |
173 |
|
} |
174 |
|
Node TheoryUfRewriter::getApplyUfForHoApply(TNode n) |
175 |
|
{ |
176 |
|
Assert(n.getType().getNumChildren() == 2); |
177 |
|
std::vector<TNode> children; |
178 |
|
TNode curr = decomposeHoApply(n, children, true); |
179 |
|
// if operator is standard |
180 |
|
if (canUseAsApplyUfOperator(curr)) |
181 |
|
{ |
182 |
|
return NodeManager::currentNM()->mkNode(kind::APPLY_UF, children); |
183 |
|
} |
184 |
|
// cannot construct APPLY_UF if operator is partially applied or is not |
185 |
|
// standard |
186 |
|
return Node::null(); |
187 |
|
} |
188 |
355 |
Node TheoryUfRewriter::decomposeHoApply(TNode n, |
189 |
|
std::vector<TNode>& args, |
190 |
|
bool opInArgs) |
191 |
|
{ |
192 |
710 |
TNode curr = n; |
193 |
1521 |
while (curr.getKind() == kind::HO_APPLY) |
194 |
|
{ |
195 |
583 |
args.push_back(curr[1]); |
196 |
583 |
curr = curr[0]; |
197 |
|
} |
198 |
355 |
if (opInArgs) |
199 |
|
{ |
200 |
115 |
args.push_back(curr); |
201 |
|
} |
202 |
355 |
std::reverse(args.begin(), args.end()); |
203 |
710 |
return curr; |
204 |
|
} |
205 |
614706 |
bool TheoryUfRewriter::canUseAsApplyUfOperator(TNode n) { return n.isVar(); } |
206 |
|
|
207 |
|
} // namespace uf |
208 |
|
} // namespace theory |
209 |
31125 |
} // namespace cvc5 |