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 first order model for full model check. |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "theory/quantifiers/fmf/first_order_model_fmc.h" |
17 |
|
|
18 |
|
#include "expr/attribute.h" |
19 |
|
#include "expr/skolem_manager.h" |
20 |
|
#include "theory/quantifiers/fmf/full_model_check.h" |
21 |
|
#include "theory/rewriter.h" |
22 |
|
|
23 |
|
using namespace cvc5::kind; |
24 |
|
|
25 |
|
namespace cvc5 { |
26 |
|
namespace theory { |
27 |
|
namespace quantifiers { |
28 |
|
namespace fmcheck { |
29 |
|
|
30 |
|
/** |
31 |
|
* Marks that a term represents the entire domain of quantified formula for |
32 |
|
* the finite model finding fmc algorithm. |
33 |
|
*/ |
34 |
|
struct IsStarAttributeId |
35 |
|
{ |
36 |
|
}; |
37 |
|
using IsStarAttribute = expr::Attribute<IsStarAttributeId, bool>; |
38 |
|
|
39 |
1341 |
FirstOrderModelFmc::FirstOrderModelFmc(QuantifiersState& qs, |
40 |
|
QuantifiersRegistry& qr, |
41 |
1341 |
TermRegistry& tr) |
42 |
1341 |
: FirstOrderModel(qs, qr, tr) |
43 |
|
{ |
44 |
1341 |
} |
45 |
|
|
46 |
4023 |
FirstOrderModelFmc::~FirstOrderModelFmc() |
47 |
|
{ |
48 |
2319 |
for (std::pair<const Node, Def*>& d : d_models) |
49 |
|
{ |
50 |
978 |
delete d.second; |
51 |
|
} |
52 |
2682 |
} |
53 |
|
|
54 |
3890 |
void FirstOrderModelFmc::processInitialize(bool ispre) |
55 |
|
{ |
56 |
3890 |
if (!ispre) |
57 |
|
{ |
58 |
1945 |
return; |
59 |
|
} |
60 |
8660 |
for (std::pair<const Node, Def*>& d : d_models) |
61 |
|
{ |
62 |
6715 |
d.second->reset(); |
63 |
|
} |
64 |
|
} |
65 |
|
|
66 |
170081 |
void FirstOrderModelFmc::processInitializeModelForTerm(Node n) |
67 |
|
{ |
68 |
170081 |
if (n.getKind() == APPLY_UF) |
69 |
|
{ |
70 |
|
// cannot be a bound variable |
71 |
63860 |
Node op = n.getOperator(); |
72 |
31930 |
if (op.getKind() != BOUND_VARIABLE) |
73 |
|
{ |
74 |
31561 |
if (d_models.find(op) == d_models.end()) |
75 |
|
{ |
76 |
978 |
d_models[op] = new Def; |
77 |
|
} |
78 |
|
} |
79 |
|
} |
80 |
170081 |
} |
81 |
|
|
82 |
2254950 |
bool FirstOrderModelFmc::isStar(Node n) |
83 |
|
{ |
84 |
2254950 |
return n.getAttribute(IsStarAttribute()); |
85 |
|
} |
86 |
|
|
87 |
868041 |
Node FirstOrderModelFmc::getStar(TypeNode tn) |
88 |
|
{ |
89 |
868041 |
std::map<TypeNode, Node>::iterator it = d_type_star.find(tn); |
90 |
868041 |
if (it != d_type_star.end()) |
91 |
|
{ |
92 |
867324 |
return it->second; |
93 |
|
} |
94 |
717 |
SkolemManager* sm = NodeManager::currentNM()->getSkolemManager(); |
95 |
|
Node st = |
96 |
1434 |
sm->mkDummySkolem("star", tn, "skolem created for full-model checking"); |
97 |
717 |
d_type_star[tn] = st; |
98 |
717 |
st.setAttribute(IsStarAttribute(), true); |
99 |
717 |
return st; |
100 |
|
} |
101 |
|
|
102 |
7693 |
Node FirstOrderModelFmc::getFunctionValue(Node op, const char* argPrefix) |
103 |
|
{ |
104 |
7693 |
Trace("fmc-model") << "Get function value for " << op << std::endl; |
105 |
7693 |
NodeManager* nm = NodeManager::currentNM(); |
106 |
15386 |
TypeNode type = op.getType(); |
107 |
15386 |
std::vector<Node> vars; |
108 |
20272 |
for (size_t i = 0, nargs = type.getNumChildren() - 1; i < nargs; i++) |
109 |
|
{ |
110 |
25158 |
std::stringstream ss; |
111 |
12579 |
ss << argPrefix << (i + 1); |
112 |
25158 |
Node b = nm->mkBoundVar(ss.str(), type[i]); |
113 |
12579 |
vars.push_back(b); |
114 |
|
} |
115 |
15386 |
Node boundVarList = nm->mkNode(BOUND_VAR_LIST, vars); |
116 |
15386 |
Node curr; |
117 |
7693 |
Def* odef = d_models[op]; |
118 |
27191 |
for (size_t i = 0, ncond = odef->d_cond.size(); i < ncond; i++) |
119 |
|
{ |
120 |
19498 |
size_t ii = (ncond - 1) - i; |
121 |
38996 |
Node v = odef->d_value[ii]; |
122 |
19498 |
Trace("fmc-model-func") << "Value is : " << v << std::endl; |
123 |
19498 |
Assert(v.isConst()); |
124 |
19498 |
if (curr.isNull()) |
125 |
|
{ |
126 |
7693 |
Trace("fmc-model-func") << "base : " << v << std::endl; |
127 |
7693 |
curr = v; |
128 |
|
} |
129 |
|
else |
130 |
|
{ |
131 |
|
// make the condition |
132 |
23610 |
Node cond = odef->d_cond[ii]; |
133 |
11805 |
Trace("fmc-model-func") << "...cond : " << cond << std::endl; |
134 |
23610 |
std::vector<Node> children; |
135 |
33507 |
for (size_t j = 0, nchild = cond.getNumChildren(); j < nchild; j++) |
136 |
|
{ |
137 |
43404 |
TypeNode tn = vars[j].getType(); |
138 |
21702 |
if (!isStar(cond[j])) |
139 |
|
{ |
140 |
43404 |
Node c = getRepresentative(cond[j]); |
141 |
21702 |
c = getRepresentative(c); |
142 |
21702 |
children.push_back(nm->mkNode(EQUAL, vars[j], c)); |
143 |
|
} |
144 |
|
} |
145 |
11805 |
Assert(!children.empty()); |
146 |
23610 |
Node cc = nm->mkAnd(children); |
147 |
|
|
148 |
23610 |
Trace("fmc-model-func") |
149 |
11805 |
<< "condition : " << cc << ", value : " << v << std::endl; |
150 |
11805 |
curr = nm->mkNode(ITE, cc, v, curr); |
151 |
|
} |
152 |
|
} |
153 |
7693 |
Trace("fmc-model") << "Made " << curr << " for " << op << std::endl; |
154 |
7693 |
curr = Rewriter::rewrite(curr); |
155 |
15386 |
return nm->mkNode(LAMBDA, boundVarList, curr); |
156 |
|
} |
157 |
|
|
158 |
|
} // namespace fmcheck |
159 |
|
} // namespace quantifiers |
160 |
|
} // namespace theory |
161 |
28194 |
} // namespace cvc5 |