1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Andrew Reynolds, Tim King, Tianyi Liang |
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 |
|
* The extended theory callback for non-linear arithmetic |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "theory/arith/nl/ext_theory_callback.h" |
17 |
|
|
18 |
|
#include "theory/arith/arith_utilities.h" |
19 |
|
#include "theory/uf/equality_engine.h" |
20 |
|
|
21 |
|
using namespace cvc5::kind; |
22 |
|
|
23 |
|
namespace cvc5 { |
24 |
|
namespace theory { |
25 |
|
namespace arith { |
26 |
|
namespace nl { |
27 |
|
|
28 |
5210 |
NlExtTheoryCallback::NlExtTheoryCallback(eq::EqualityEngine* ee) : d_ee(ee) |
29 |
|
{ |
30 |
5210 |
d_zero = NodeManager::currentNM()->mkConst(Rational(0)); |
31 |
5210 |
} |
32 |
|
|
33 |
4462 |
bool NlExtTheoryCallback::getCurrentSubstitution( |
34 |
|
int effort, |
35 |
|
const std::vector<Node>& vars, |
36 |
|
std::vector<Node>& subs, |
37 |
|
std::map<Node, std::vector<Node>>& exp) |
38 |
|
{ |
39 |
|
// get the constant equivalence classes |
40 |
8924 |
std::map<Node, std::vector<int>> rep_to_subs_index; |
41 |
|
|
42 |
4462 |
bool retVal = false; |
43 |
29903 |
for (unsigned i = 0; i < vars.size(); i++) |
44 |
|
{ |
45 |
50882 |
Node n = vars[i]; |
46 |
25441 |
if (d_ee->hasTerm(n)) |
47 |
|
{ |
48 |
38444 |
Node nr = d_ee->getRepresentative(n); |
49 |
19222 |
if (nr.isConst()) |
50 |
|
{ |
51 |
4079 |
subs.push_back(nr); |
52 |
8158 |
Trace("nl-subs") << "Basic substitution : " << n << " -> " << nr |
53 |
4079 |
<< std::endl; |
54 |
4079 |
exp[n].push_back(n.eqNode(nr)); |
55 |
4079 |
retVal = true; |
56 |
|
} |
57 |
|
else |
58 |
|
{ |
59 |
15143 |
rep_to_subs_index[nr].push_back(i); |
60 |
15143 |
subs.push_back(n); |
61 |
|
} |
62 |
|
} |
63 |
|
else |
64 |
|
{ |
65 |
6219 |
subs.push_back(n); |
66 |
|
} |
67 |
|
} |
68 |
|
|
69 |
|
// return true if the substitution is non-trivial |
70 |
8924 |
return retVal; |
71 |
|
} |
72 |
|
|
73 |
6976 |
bool NlExtTheoryCallback::isExtfReduced( |
74 |
|
int effort, Node n, Node on, std::vector<Node>& exp, ExtReducedId& id) |
75 |
|
{ |
76 |
6976 |
if (n != d_zero) |
77 |
|
{ |
78 |
4484 |
Kind k = n.getKind(); |
79 |
8168 |
if (k != NONLINEAR_MULT && !isTranscendentalKind(k) && k != IAND |
80 |
7394 |
&& k != POW2) |
81 |
|
{ |
82 |
2910 |
id = ExtReducedId::ARITH_SR_LINEAR; |
83 |
2910 |
return true; |
84 |
|
} |
85 |
1574 |
return false; |
86 |
|
} |
87 |
2492 |
Assert(n == d_zero); |
88 |
2492 |
id = ExtReducedId::ARITH_SR_ZERO; |
89 |
2492 |
if (on.getKind() == NONLINEAR_MULT) |
90 |
|
{ |
91 |
4602 |
Trace("nl-ext-zero-exp") |
92 |
2301 |
<< "Infer zero : " << on << " == " << n << std::endl; |
93 |
|
// minimize explanation if a substitution+rewrite results in zero |
94 |
2301 |
const std::set<Node> vars(on.begin(), on.end()); |
95 |
|
|
96 |
2361 |
for (unsigned i = 0, size = exp.size(); i < size; i++) |
97 |
|
{ |
98 |
4722 |
Trace("nl-ext-zero-exp") |
99 |
2361 |
<< " exp[" << i << "] = " << exp[i] << std::endl; |
100 |
2421 |
std::vector<Node> eqs; |
101 |
2361 |
if (exp[i].getKind() == EQUAL) |
102 |
|
{ |
103 |
2361 |
eqs.push_back(exp[i]); |
104 |
|
} |
105 |
|
else if (exp[i].getKind() == AND) |
106 |
|
{ |
107 |
|
for (const Node& ec : exp[i]) |
108 |
|
{ |
109 |
|
if (ec.getKind() == EQUAL) |
110 |
|
{ |
111 |
|
eqs.push_back(ec); |
112 |
|
} |
113 |
|
} |
114 |
|
} |
115 |
|
|
116 |
2421 |
for (unsigned j = 0; j < eqs.size(); j++) |
117 |
|
{ |
118 |
4782 |
for (unsigned r = 0; r < 2; r++) |
119 |
|
{ |
120 |
4722 |
if (eqs[j][r] == d_zero && vars.find(eqs[j][1 - r]) != vars.end()) |
121 |
|
{ |
122 |
4602 |
Trace("nl-ext-zero-exp") |
123 |
2301 |
<< "...single exp : " << eqs[j] << std::endl; |
124 |
2301 |
exp.clear(); |
125 |
2301 |
exp.push_back(eqs[j]); |
126 |
2301 |
return true; |
127 |
|
} |
128 |
|
} |
129 |
|
} |
130 |
|
} |
131 |
|
} |
132 |
191 |
return true; |
133 |
|
} |
134 |
|
|
135 |
|
} // namespace nl |
136 |
|
} // namespace arith |
137 |
|
} // namespace theory |
138 |
29505 |
} // namespace cvc5 |