1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
3 /*
4 * Main authors:
5 * Guido Tack <guido.tack@monash.edu>
6 */
7
8 /* This Source Code Form is subject to the terms of the Mozilla Public
9 * License, v. 2.0. If a copy of the MPL was not distributed with this
10 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
11
12 #pragma once
13
14 #include <minizinc/astexception.hh>
15 #include <minizinc/iter.hh>
16 #include <minizinc/model.hh>
17 #include <minizinc/prettyprinter.hh>
18
19 namespace MiniZinc {
20
21 /// Evaluate par int expression \a e
22 IntVal eval_int(EnvI& env, Expression* e);
23 /// Evaluate par bool expression \a e
24 bool eval_bool(EnvI& env, Expression* e);
25 /// Evaluate par float expression \a e
26 FloatVal eval_float(EnvI& env, Expression* e);
27 /// Evaluate an array expression \a e into an array literal
28 ArrayLit* eval_array_lit(EnvI& env, Expression* e);
29 /// Evaluate an access to array \a with indices \a idx and return whether
30 /// access succeeded in \a success
31 Expression* eval_arrayaccess(EnvI& env, ArrayLit* a, const std::vector<IntVal>& idx, bool& success);
32 /// Evaluate an array access \a e and return whether access succeeded in \a success
33 Expression* eval_arrayaccess(EnvI& env, ArrayAccess* e, bool& success);
34 /// Evaluate a set expression \a e into a set literal
35 SetLit* eval_set_lit(EnvI& env, Expression* e);
36 /// Evaluate a par integer set \a e
37 IntSetVal* eval_intset(EnvI& env, Expression* e);
38 /// Evaluate a par bool set \a e
39 IntSetVal* eval_boolset(EnvI& env, Expression* e);
40 /// Evaluate a par float set \a e
41 FloatSetVal* eval_floatset(EnvI& env, Expression* e);
42 /// Evaluate a par string \a e
43 std::string eval_string(EnvI& env, Expression* e);
44 /// Evaluate a par expression \a e and return it wrapped in a literal
45 Expression* eval_par(EnvI& env, Expression* e);
46 /// Check if variable declaration \a vd satisfies the domain and index set constraints
47 void check_par_declaration(EnvI& env, VarDecl* vd);
48
49 /// Representation for bounds of an integer expression
50 struct IntBounds {
51 /// Lower bound
52 IntVal l;
53 /// Upper bound
54 IntVal u;
55 /// Whether the bounds are valid
56 bool valid;
57 /// Constructor
IntBoundsMiniZinc::IntBounds58 IntBounds(IntVal l0, IntVal u0, bool valid0) : l(l0), u(u0), valid(valid0) {}
59 };
60
61 /// Compute bounds of an integer expression
62 IntBounds compute_int_bounds(EnvI& env, Expression* e);
63
64 /// Representation for bounds of a float expression
65 struct FloatBounds {
66 /// Lower bound
67 FloatVal l;
68 /// Upper bound
69 FloatVal u;
70 /// Whether the bounds are valid
71 bool valid;
72 /// Constructor
FloatBoundsMiniZinc::FloatBounds73 FloatBounds(FloatVal l0, FloatVal u0, bool valid0) : l(l0), u(u0), valid(valid0) {}
74 };
75
76 /// Compute bounds of an integer expression
77 FloatBounds compute_float_bounds(EnvI& env, Expression* e);
78
79 /**
80 * \brief Compute bounds of a set of int expression
81 *
82 * Returns NULL if bounds cannot be determined
83 */
84 IntSetVal* compute_intset_bounds(EnvI& env, Expression* e);
85
86 class EvalBase {
87 public:
88 /// Evaluate bool expression that may contain variables
89 static bool evalBoolCV(EnvI& env, Expression* e);
90 /// Flatten expression that may contain variables
91 static KeepAlive flattenCV(EnvI& env, Expression* e);
92 };
93
94 template <class Eval>
95 void eval_comp_array(EnvI& env, Eval& eval, Comprehension* e, int gen, int id, KeepAlive in,
96 std::vector<typename Eval::ArrayVal>& a);
97
98 template <class Eval>
99 void eval_comp_set(EnvI& env, Eval& eval, Comprehension* e, int gen, int id, KeepAlive in,
100 std::vector<typename Eval::ArrayVal>& a);
101
102 template <class Eval>
eval_comp_set(EnvI & env,Eval & eval,Comprehension * e,int gen,int id,IntVal i,KeepAlive in,std::vector<typename Eval::ArrayVal> & a)103 void eval_comp_set(EnvI& env, Eval& eval, Comprehension* e, int gen, int id, IntVal i, KeepAlive in,
104 std::vector<typename Eval::ArrayVal>& a) {
105 {
106 GCLock lock;
107 GC::mark();
108 e->decl(gen, id)->trail();
109 e->decl(gen, id)->e(IntLit::a(i));
110 }
111 CallStackItem csi(env, e->decl(gen, id)->id(), i);
112 if (id == e->numberOfDecls(gen) - 1) {
113 bool where = true;
114 if (e->where(gen) != nullptr && !e->where(gen)->type().isvar()) {
115 where = eval.evalBoolCV(env, e->where(gen));
116 }
117 if (where) {
118 if (gen == e->numberOfGenerators() - 1) {
119 a.push_back(eval.e(env, e->e()));
120 } else {
121 if (e->in(gen + 1) == nullptr) {
122 eval_comp_array<Eval>(env, eval, e, gen + 1, 0, 0, e->in(gen + 1), a);
123 } else {
124 KeepAlive nextin;
125 Expression* gen_in = e->in(gen + 1);
126 if (gen_in->type().isvar() || gen_in->type().cv()) {
127 gen_in = eval.flattenCV(env, e->in(gen + 1))();
128 }
129 if (gen_in->type().dim() == 0) {
130 GCLock lock;
131 nextin = new SetLit(Location(), eval_intset(env, gen_in));
132 } else {
133 GCLock lock;
134 nextin = eval_array_lit(env, gen_in);
135 }
136 if (e->in(gen + 1)->type().dim() == 0) {
137 eval_comp_set<Eval>(env, eval, e, gen + 1, 0, nextin, a);
138 } else {
139 eval_comp_array<Eval>(env, eval, e, gen + 1, 0, nextin, a);
140 }
141 }
142 }
143 }
144 } else {
145 eval_comp_set<Eval>(env, eval, e, gen, id + 1, in, a);
146 }
147 GC::untrail();
148 e->decl(gen, id)->flat(nullptr);
149 }
150
151 template <class Eval>
eval_comp_array(EnvI & env,Eval & eval,Comprehension * e,int gen,int id,IntVal i,KeepAlive in,std::vector<typename Eval::ArrayVal> & a)152 void eval_comp_array(EnvI& env, Eval& eval, Comprehension* e, int gen, int id, IntVal i,
153 KeepAlive in, std::vector<typename Eval::ArrayVal>& a) {
154 GC::mark();
155 e->decl(gen, id)->trail();
156 CallStackItem csi(env, e->decl(gen, id)->id(), i);
157 if (in() == nullptr) {
158 // this is an assignment generator
159 Expression* asn;
160 if (e->where(gen)->type().isvar() || e->where(gen)->type().cv()) {
161 asn = eval.flattenCV(env, e->where(gen))();
162 } else {
163 asn = eval_par(env, e->where(gen));
164 }
165 e->decl(gen, id)->e(asn);
166 e->rehash();
167 } else {
168 auto* al = in()->cast<ArrayLit>();
169 e->decl(gen, id)->e((*al)[static_cast<int>(i.toInt())]);
170 e->rehash();
171 }
172 if (id == e->numberOfDecls(gen) - 1) {
173 bool where = true;
174 if (e->in(gen) != nullptr && e->where(gen) != nullptr && !e->where(gen)->type().isvar()) {
175 where = eval.evalBoolCV(env, e->where(gen));
176 }
177 if (where) {
178 if (gen == e->numberOfGenerators() - 1) {
179 a.push_back(eval.e(env, e->e()));
180 } else {
181 if (e->in(gen + 1) == nullptr) {
182 eval_comp_array<Eval>(env, eval, e, gen + 1, 0, 0, e->in(gen + 1), a);
183 } else {
184 KeepAlive nextin;
185 Expression* gen_in = e->in(gen + 1);
186 if (gen_in->type().isvar() || gen_in->type().cv()) {
187 gen_in = eval.flattenCV(env, e->in(gen + 1))();
188 }
189 if (gen_in->type().dim() == 0) {
190 GCLock lock;
191 nextin = new SetLit(Location(), eval_intset(env, gen_in));
192 } else {
193 GCLock lock;
194 nextin = eval_array_lit(env, gen_in);
195 }
196 if (gen_in->type().dim() == 0) {
197 eval_comp_set<Eval>(env, eval, e, gen + 1, 0, nextin, a);
198 } else {
199 eval_comp_array<Eval>(env, eval, e, gen + 1, 0, nextin, a);
200 }
201 }
202 }
203 }
204 } else {
205 eval_comp_array<Eval>(env, eval, e, gen, id + 1, in, a);
206 }
207 GC::untrail();
208 e->decl(gen, id)->flat(nullptr);
209 }
210
211 /**
212 * \brief Evaluate comprehension expression
213 *
214 * Calls \a eval.e for every element of the comprehension \a e,
215 * where \a gen is the current generator, \a id is the current identifier
216 * in that generator, \a in is the expression of that generator, and
217 * \a a is the array in which to place the result.
218 */
219 template <class Eval>
eval_comp_set(EnvI & env,Eval & eval,Comprehension * e,int gen,int id,KeepAlive in,std::vector<typename Eval::ArrayVal> & a)220 void eval_comp_set(EnvI& env, Eval& eval, Comprehension* e, int gen, int id, KeepAlive in,
221 std::vector<typename Eval::ArrayVal>& a) {
222 IntSetVal* isv = eval_intset(env, in());
223 if (isv->card().isPlusInfinity()) {
224 throw EvalError(env, in()->loc(), "comprehension iterates over an infinite set");
225 }
226 IntSetRanges rsi(isv);
227 Ranges::ToValues<IntSetRanges> rsv(rsi);
228 for (; rsv(); ++rsv) {
229 eval_comp_set<Eval>(env, eval, e, gen, id, rsv.val(), in, a);
230 }
231 }
232
233 /**
234 * \brief Evaluate comprehension expression
235 *
236 * Calls \a eval.e for every element of the comprehension \a e,
237 * where \a gen is the current generator, \a id is the current identifier
238 * in that generator, \a in is the expression of that generator, and
239 * \a a is the array in which to place the result.
240 */
241 template <class Eval>
eval_comp_array(EnvI & env,Eval & eval,Comprehension * e,int gen,int id,KeepAlive in,std::vector<typename Eval::ArrayVal> & a)242 void eval_comp_array(EnvI& env, Eval& eval, Comprehension* e, int gen, int id, KeepAlive in,
243 std::vector<typename Eval::ArrayVal>& a) {
244 auto* al = in()->cast<ArrayLit>();
245 for (unsigned int i = 0; i < al->size(); i++) {
246 eval_comp_array<Eval>(env, eval, e, gen, id, i, in, a);
247 }
248 }
249
250 /**
251 * \brief Evaluate comprehension expression
252 *
253 * Calls \a eval.e for every element of the comprehension \a e and
254 * returns a vector with all the evaluated results.
255 */
256 template <class Eval>
eval_comp(EnvI & env,Eval & eval,Comprehension * e)257 std::vector<typename Eval::ArrayVal> eval_comp(EnvI& env, Eval& eval, Comprehension* e) {
258 std::vector<typename Eval::ArrayVal> a;
259 if (e->in(0) == nullptr) {
260 eval_comp_array<Eval>(env, eval, e, 0, 0, 0, e->in(0), a);
261 } else {
262 KeepAlive in;
263 {
264 GCLock lock;
265 if (e->in(0)->type().dim() == 0) {
266 if (e->in(0)->type().isvar()) {
267 in = new SetLit(Location(), compute_intset_bounds(env, e->in(0)));
268 } else {
269 in = new SetLit(Location(), eval_intset(env, e->in(0)));
270 }
271 } else {
272 if (e->in(0)->type().isvar() || e->in(0)->type().cv()) {
273 in = eval_array_lit(env, eval.flattenCV(env, e->in(0))());
274 } else {
275 in = eval_array_lit(env, e->in(0));
276 }
277 }
278 }
279 if (e->in(0)->type().dim() == 0) {
280 eval_comp_set<Eval>(env, eval, e, 0, 0, in, a);
281 } else {
282 eval_comp_array<Eval>(env, eval, e, 0, 0, in, a);
283 }
284 }
285 return a;
286 }
287
288 /**
289 * \brief Evaluate comprehension expression
290 *
291 * Calls \a Eval::e for every element of the comprehension \a e and
292 * returns a vector with all the evaluated results.
293 */
294 template <class Eval>
eval_comp(EnvI & env,Comprehension * e)295 std::vector<typename Eval::ArrayVal> eval_comp(EnvI& env, Comprehension* e) {
296 Eval eval;
297 return eval_comp(env, eval, e);
298 }
299
300 Expression* follow_id(Expression* e);
301 Expression* follow_id_to_decl(Expression* e);
302 Expression* follow_id_to_value(Expression* e);
303
304 } // namespace MiniZinc
305