this repo has no description
dekker.one
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#include <minizinc/astexception.hh>
13#include <minizinc/astiterator.hh>
14#include <minizinc/copy.hh>
15#include <minizinc/eval_par.hh>
16#include <minizinc/flat_exp.hh>
17#include <minizinc/flatten.hh>
18#include <minizinc/hash.hh>
19#include <minizinc/iter.hh>
20
21#include <cmath>
22
23namespace MiniZinc {
24
25bool check_par_domain(EnvI& env, Expression* e, Expression* domain) {
26 if (e->type() == Type::parint()) {
27 IntSetVal* isv = eval_intset(env, domain);
28 if (!isv->contains(eval_int(env, e))) {
29 return false;
30 }
31 } else if (e->type() == Type::parfloat()) {
32 FloatSetVal* fsv = eval_floatset(env, domain);
33 if (!fsv->contains(eval_float(env, e))) {
34 return false;
35 }
36 } else if (e->type() == Type::parsetint()) {
37 IntSetVal* isv = eval_intset(env, domain);
38 IntSetRanges ir(isv);
39 IntSetVal* rsv = eval_intset(env, e);
40 IntSetRanges rr(rsv);
41 if (!Ranges::subset(rr, ir)) {
42 return false;
43 }
44 } else if (e->type() == Type::parsetfloat()) {
45 FloatSetVal* fsv = eval_floatset(env, domain);
46 FloatSetRanges fr(fsv);
47 FloatSetVal* rsv = eval_floatset(env, e);
48 FloatSetRanges rr(rsv);
49 if (!Ranges::subset(rr, fr)) {
50 return false;
51 }
52 }
53 return true;
54}
55
56void check_par_declaration(EnvI& env, VarDecl* vd) {
57 if (vd->type().dim() > 0) {
58 check_index_sets(env, vd, vd->e());
59 if (vd->ti()->domain() != nullptr) {
60 ArrayLit* al = eval_array_lit(env, vd->e());
61 for (unsigned int i = 0; i < al->size(); i++) {
62 if (!check_par_domain(env, (*al)[i], vd->ti()->domain())) {
63 throw ResultUndefinedError(env, vd->e()->loc(), "parameter value out of range");
64 }
65 }
66 }
67 } else {
68 if (vd->ti()->domain() != nullptr) {
69 if (!check_par_domain(env, vd->e(), vd->ti()->domain())) {
70 throw ResultUndefinedError(env, vd->e()->loc(), "parameter value out of range");
71 }
72 }
73 }
74}
75
76template <class E>
77typename E::Val eval_id(EnvI& env, Expression* e) {
78 Id* id = e->cast<Id>();
79 if (!id->decl()) {
80 throw EvalError(env, e->loc(), "undeclared identifier", id->str());
81 }
82 VarDecl* vd = id->decl();
83 while (vd->flat() && vd->flat() != vd) {
84 vd = vd->flat();
85 }
86 if (!vd->e()) {
87 throw EvalError(env, vd->loc(), "cannot evaluate expression", id->str());
88 }
89 typename E::Val r = E::e(env, vd->e());
90 if (!vd->evaluated() && (vd->toplevel() || vd->type().dim() > 0)) {
91 Expression* ne = E::exp(r);
92 vd->e(ne);
93 vd->evaluated(true);
94 }
95 return r;
96}
97
98bool EvalBase::evalBoolCV(EnvI& env, Expression* e) {
99 GCLock lock;
100 if (e->type().cv()) {
101 return eval_bool(env, flat_cv_exp(env, Ctx(), e)());
102 }
103 return eval_bool(env, e);
104};
105
106class EvalIntLit : public EvalBase {
107public:
108 typedef IntLit* Val;
109 typedef Expression* ArrayVal;
110 static IntLit* e(EnvI& env, Expression* e) { return IntLit::a(eval_int(env, e)); }
111 static Expression* exp(IntLit* e) { return e; }
112 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
113 throw InternalError("evaluating var assignment generator inside par expression not supported");
114 }
115};
116class EvalIntVal : public EvalBase {
117public:
118 typedef IntVal Val;
119 typedef IntVal ArrayVal;
120 static IntVal e(EnvI& env, Expression* e) { return eval_int(env, e); }
121 static Expression* exp(IntVal e) { return IntLit::a(e); }
122 static void checkRetVal(EnvI& env, Val v, FunctionI* fi) {
123 if ((fi->ti()->domain() != nullptr) && !fi->ti()->domain()->isa<TIId>()) {
124 IntSetVal* isv = eval_intset(env, fi->ti()->domain());
125 if (!isv->contains(v)) {
126 throw ResultUndefinedError(env, Location().introduce(),
127 "function result violates function type-inst");
128 }
129 }
130 }
131 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
132 throw InternalError("evaluating var assignment generator inside par expression not supported");
133 }
134};
135class EvalFloatVal : public EvalBase {
136public:
137 typedef FloatVal Val;
138 typedef FloatVal ArrayVal;
139 static FloatVal e(EnvI& env, Expression* e) { return eval_float(env, e); }
140 static Expression* exp(FloatVal e) { return FloatLit::a(e); }
141 static void checkRetVal(EnvI& env, Val v, FunctionI* fi) {
142 if ((fi->ti()->domain() != nullptr) && !fi->ti()->domain()->isa<TIId>()) {
143 FloatSetVal* fsv = eval_floatset(env, fi->ti()->domain());
144 if (!fsv->contains(v)) {
145 throw ResultUndefinedError(env, Location().introduce(),
146 "function result violates function type-inst");
147 }
148 }
149 }
150 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
151 throw InternalError("evaluating var assignment generator inside par expression not supported");
152 }
153};
154class EvalFloatLit : public EvalBase {
155public:
156 typedef FloatLit* Val;
157 typedef Expression* ArrayVal;
158 static FloatLit* e(EnvI& env, Expression* e) { return FloatLit::a(eval_float(env, e)); }
159 static Expression* exp(Expression* e) { return e; }
160 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
161 throw InternalError("evaluating var assignment generator inside par expression not supported");
162 }
163};
164class EvalString : public EvalBase {
165public:
166 typedef std::string Val;
167 typedef std::string ArrayVal;
168 static std::string e(EnvI& env, Expression* e) { return eval_string(env, e); }
169 static Expression* exp(const std::string& e) { return new StringLit(Location(), e); }
170 static void checkRetVal(EnvI& env, const Val& v, FunctionI* fi) {}
171 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
172 throw InternalError("evaluating var assignment generator inside par expression not supported");
173 }
174};
175class EvalStringLit : public EvalBase {
176public:
177 typedef StringLit* Val;
178 typedef Expression* ArrayVal;
179 static StringLit* e(EnvI& env, Expression* e) {
180 return new StringLit(Location(), eval_string(env, e));
181 }
182 static Expression* exp(Expression* e) { return e; }
183 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
184 throw InternalError("evaluating var assignment generator inside par expression not supported");
185 }
186};
187class EvalBoolLit : public EvalBase {
188public:
189 typedef BoolLit* Val;
190 typedef Expression* ArrayVal;
191 static BoolLit* e(EnvI& env, Expression* e) { return constants().boollit(eval_bool(env, e)); }
192 static Expression* exp(Expression* e) { return e; }
193 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
194 throw InternalError("evaluating var assignment generator inside par expression not supported");
195 }
196};
197class EvalBoolVal : public EvalBase {
198public:
199 typedef bool Val;
200 static bool e(EnvI& env, Expression* e) { return eval_bool(env, e); }
201 static Expression* exp(bool e) { return constants().boollit(e); }
202 static void checkRetVal(EnvI& env, Val v, FunctionI* fi) {}
203 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
204 throw InternalError("evaluating var assignment generator inside par expression not supported");
205 }
206};
207class EvalArrayLit : public EvalBase {
208public:
209 typedef ArrayLit* Val;
210 typedef Expression* ArrayVal;
211 static ArrayLit* e(EnvI& env, Expression* e) { return eval_array_lit(env, e); }
212 static Expression* exp(Expression* e) { return e; }
213 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
214 throw InternalError("evaluating var assignment generator inside par expression not supported");
215 }
216};
217class EvalArrayLitCopy : public EvalBase {
218public:
219 typedef ArrayLit* Val;
220 typedef Expression* ArrayVal;
221 static ArrayLit* e(EnvI& env, Expression* e) {
222 return copy(env, eval_array_lit(env, e), true)->cast<ArrayLit>();
223 }
224 static Expression* exp(Expression* e) { return e; }
225 static void checkRetVal(EnvI& env, Val v, FunctionI* fi) {
226 for (unsigned int i = 0; i < fi->ti()->ranges().size(); i++) {
227 if ((fi->ti()->ranges()[i]->domain() != nullptr) &&
228 !fi->ti()->ranges()[i]->domain()->isa<TIId>()) {
229 IntSetVal* isv = eval_intset(env, fi->ti()->ranges()[i]->domain());
230 bool bothEmpty = isv->min() > isv->max() && v->min(i) > v->max(i);
231 if (!bothEmpty && (v->min(i) != isv->min() || v->max(i) != isv->max())) {
232 std::ostringstream oss;
233 oss << "array index set " << (i + 1) << " of function result violates function type-inst";
234 throw ResultUndefinedError(env, fi->e()->loc(), oss.str());
235 }
236 }
237 }
238 if ((fi->ti()->domain() != nullptr) && !fi->ti()->domain()->isa<TIId>() &&
239 fi->ti()->type().ti() == Type::TI_PAR) {
240 Type base_t = fi->ti()->type();
241 if (base_t.bt() == Type::BT_INT) {
242 IntSetVal* isv = eval_intset(env, fi->ti()->domain());
243 if (base_t.st() == Type::ST_PLAIN) {
244 for (unsigned int i = 0; i < v->size(); i++) {
245 IntVal iv = eval_int(env, (*v)[i]);
246 if (!isv->contains(iv)) {
247 std::ostringstream oss;
248 oss << "array contains value " << iv << " which is not contained in " << *isv;
249 throw ResultUndefinedError(
250 env, fi->e()->loc(), "function result violates function type-inst, " + oss.str());
251 }
252 }
253 } else {
254 for (unsigned int i = 0; i < v->size(); i++) {
255 IntSetVal* iv = eval_intset(env, (*v)[i]);
256 IntSetRanges isv_r(isv);
257 IntSetRanges v_r(iv);
258 if (!Ranges::subset(v_r, isv_r)) {
259 std::ostringstream oss;
260 oss << "array contains value " << *iv << " which is not a subset of " << *isv;
261 throw ResultUndefinedError(
262 env, fi->e()->loc(), "function result violates function type-inst, " + oss.str());
263 }
264 }
265 }
266 } else if (base_t.bt() == Type::BT_FLOAT) {
267 FloatSetVal* fsv = eval_floatset(env, fi->ti()->domain());
268 if (base_t.st() == Type::ST_PLAIN) {
269 for (unsigned int i = 0; i < v->size(); i++) {
270 FloatVal fv = eval_float(env, (*v)[i]);
271 if (!fsv->contains(fv)) {
272 std::ostringstream oss;
273 oss << "array contains value " << fv << " which is not contained in " << *fsv;
274 throw ResultUndefinedError(
275 env, fi->e()->loc(), "function result violates function type-inst, " + oss.str());
276 }
277 }
278 } else {
279 for (unsigned int i = 0; i < v->size(); i++) {
280 FloatSetVal* fv = eval_floatset(env, (*v)[i]);
281 FloatSetRanges fsv_r(fsv);
282 FloatSetRanges v_r(fv);
283 if (!Ranges::subset(v_r, fsv_r)) {
284 std::ostringstream oss;
285 oss << "array contains value " << *fv << " which is not a subset of " << *fsv;
286 throw ResultUndefinedError(
287 env, fi->e()->loc(), "function result violates function type-inst, " + oss.str());
288 }
289 }
290 }
291 }
292 }
293 }
294 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
295 throw InternalError("evaluating var assignment generator inside par expression not supported");
296 }
297};
298class EvalIntSet : public EvalBase {
299public:
300 typedef IntSetVal* Val;
301 static IntSetVal* e(EnvI& env, Expression* e) { return eval_intset(env, e); }
302 static Expression* exp(IntSetVal* e) { return new SetLit(Location(), e); }
303 static void checkRetVal(EnvI& env, Val v, FunctionI* fi) {
304 if ((fi->ti()->domain() != nullptr) && !fi->ti()->domain()->isa<TIId>()) {
305 IntSetVal* isv = eval_intset(env, fi->ti()->domain());
306 IntSetRanges isv_r(isv);
307 IntSetRanges v_r(v);
308 if (!Ranges::subset(v_r, isv_r)) {
309 throw ResultUndefinedError(env, Location().introduce(),
310 "function result violates function type-inst");
311 }
312 }
313 }
314 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
315 throw InternalError("evaluating var assignment generator inside par expression not supported");
316 }
317};
318class EvalFloatSet : public EvalBase {
319public:
320 typedef FloatSetVal* Val;
321 static FloatSetVal* e(EnvI& env, Expression* e) { return eval_floatset(env, e); }
322 static Expression* exp(FloatSetVal* e) { return new SetLit(Location(), e); }
323 static void checkRetVal(EnvI& env, Val v, FunctionI* fi) {
324 if ((fi->ti()->domain() != nullptr) && !fi->ti()->domain()->isa<TIId>()) {
325 FloatSetVal* fsv = eval_floatset(env, fi->ti()->domain());
326 FloatSetRanges fsv_r(fsv);
327 FloatSetRanges v_r(v);
328 if (!Ranges::subset(v_r, fsv_r)) {
329 throw ResultUndefinedError(env, Location().introduce(),
330 "function result violates function type-inst");
331 }
332 }
333 }
334 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
335 throw InternalError("evaluating var assignment generator inside par expression not supported");
336 }
337};
338class EvalBoolSet : public EvalBase {
339public:
340 typedef IntSetVal* Val;
341 static IntSetVal* e(EnvI& env, Expression* e) { return eval_boolset(env, e); }
342 static Expression* exp(IntSetVal* e) {
343 auto* sl = new SetLit(Location(), e);
344 sl->type(Type::parsetbool());
345 return sl;
346 }
347 static void checkRetVal(EnvI& env, Val v, FunctionI* fi) {}
348 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
349 throw InternalError("evaluating var assignment generator inside par expression not supported");
350 }
351};
352class EvalSetLit : public EvalBase {
353public:
354 typedef SetLit* Val;
355 typedef Expression* ArrayVal;
356 static SetLit* e(EnvI& env, Expression* e) { return eval_set_lit(env, e); }
357 static Expression* exp(Expression* e) { return e; }
358 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
359 throw InternalError("evaluating var assignment generator inside par expression not supported");
360 }
361};
362class EvalFloatSetLit : public EvalBase {
363public:
364 typedef SetLit* Val;
365 typedef Expression* ArrayVal;
366 static SetLit* e(EnvI& env, Expression* e) { return new SetLit(e->loc(), eval_floatset(env, e)); }
367 static Expression* exp(Expression* e) { return e; }
368 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
369 throw InternalError("evaluating var assignment generator inside par expression not supported");
370 }
371};
372class EvalBoolSetLit : public EvalBase {
373public:
374 typedef SetLit* Val;
375 typedef Expression* ArrayVal;
376 static SetLit* e(EnvI& env, Expression* e) {
377 auto* sl = new SetLit(e->loc(), eval_boolset(env, e));
378 sl->type(Type::parsetbool());
379 return sl;
380 }
381 static Expression* exp(Expression* e) { return e; }
382 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
383 throw InternalError("evaluating var assignment generator inside par expression not supported");
384 }
385};
386class EvalCopy : public EvalBase {
387public:
388 typedef Expression* Val;
389 typedef Expression* ArrayVal;
390 static Expression* e(EnvI& env, Expression* e) { return copy(env, e, true); }
391 static Expression* exp(Expression* e) { return e; }
392 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
393 throw InternalError("evaluating var assignment generator inside par expression not supported");
394 }
395};
396class EvalPar : public EvalBase {
397public:
398 typedef Expression* Val;
399 typedef Expression* ArrayVal;
400 static Expression* e(EnvI& env, Expression* e) { return eval_par(env, e); }
401 static Expression* exp(Expression* e) { return e; }
402 static void checkRetVal(EnvI& env, Val v, FunctionI* fi) {}
403 static Expression* flatten(EnvI& /*env*/, Expression* /*e*/) {
404 throw InternalError("evaluating var assignment generator inside par expression not supported");
405 }
406};
407
408void check_dom(EnvI& env, Id* arg, IntSetVal* dom, Expression* e) {
409 bool oob = false;
410 if (!e->type().isOpt()) {
411 if (e->type().isIntSet()) {
412 IntSetVal* ev = eval_intset(env, e);
413 IntSetRanges ev_r(ev);
414 IntSetRanges dom_r(dom);
415 oob = !Ranges::subset(ev_r, dom_r);
416 } else {
417 oob = !dom->contains(eval_int(env, e));
418 }
419 }
420 if (oob) {
421 std::ostringstream oss;
422 oss << "value for argument `" << *arg << "' out of bounds";
423 throw EvalError(env, e->loc(), oss.str());
424 }
425}
426
427void check_dom(EnvI& env, Id* arg, FloatVal dom_min, FloatVal dom_max, Expression* e) {
428 if (!e->type().isOpt()) {
429 FloatVal ev = eval_float(env, e);
430 if (ev < dom_min || ev > dom_max) {
431 std::ostringstream oss;
432 oss << "value for argument `" << *arg << "' out of bounds";
433 throw EvalError(env, e->loc(), oss.str());
434 }
435 }
436}
437
438template <class Eval, class CallClass = Call>
439typename Eval::Val eval_call(EnvI& env, CallClass* ce) {
440 std::vector<Expression*> previousParameters(ce->decl()->params().size());
441 std::vector<Expression*> params(ce->decl()->params().size());
442 for (unsigned int i = 0; i < ce->decl()->params().size(); i++) {
443 params[i] = eval_par(env, ce->arg(i));
444 }
445 for (unsigned int i = ce->decl()->params().size(); i--;) {
446 VarDecl* vd = ce->decl()->params()[i];
447 if (vd->type().dim() > 0) {
448 // Check array index sets
449 auto* al = params[i]->cast<ArrayLit>();
450 for (unsigned int j = 0; j < vd->ti()->ranges().size(); j++) {
451 TypeInst* range_ti = vd->ti()->ranges()[j];
452 if (range_ti->domain() && !range_ti->domain()->isa<TIId>()) {
453 IntSetVal* isv = eval_intset(env, range_ti->domain());
454 if (isv->min() != al->min(j) || isv->max() != al->max(j)) {
455 std::ostringstream oss;
456 oss << "array index set " << (j + 1) << " of argument " << (i + 1)
457 << " does not match declared index set";
458 throw EvalError(env, ce->loc(), oss.str());
459 }
460 }
461 }
462 }
463 previousParameters[i] = vd->e();
464 vd->flat(vd);
465 vd->e(params[i]);
466 if (vd->e()->type().isPar()) {
467 if (Expression* dom = vd->ti()->domain()) {
468 if (!dom->isa<TIId>()) {
469 if (vd->e()->type().bt() == Type::BT_INT) {
470 IntSetVal* isv = eval_intset(env, dom);
471 if (vd->e()->type().dim() > 0) {
472 ArrayLit* al = eval_array_lit(env, vd->e());
473 for (unsigned int i = 0; i < al->size(); i++) {
474 check_dom(env, vd->id(), isv, (*al)[i]);
475 }
476 } else {
477 check_dom(env, vd->id(), isv, vd->e());
478 }
479 } else if (vd->e()->type().bt() == Type::BT_FLOAT) {
480 GCLock lock;
481 FloatSetVal* fsv = eval_floatset(env, dom);
482 FloatVal dom_min = fsv->min();
483 FloatVal dom_max = fsv->max();
484 check_dom(env, vd->id(), dom_min, dom_max, vd->e());
485 }
486 }
487 }
488 }
489 }
490 typename Eval::Val ret = Eval::e(env, ce->decl()->e());
491 Eval::checkRetVal(env, ret, ce->decl());
492 for (unsigned int i = ce->decl()->params().size(); i--;) {
493 VarDecl* vd = ce->decl()->params()[i];
494 vd->e(previousParameters[i]);
495 vd->flat(vd->e() ? vd : nullptr);
496 }
497 return ret;
498}
499
500ArrayLit* eval_array_comp(EnvI& env, Comprehension* e) {
501 ArrayLit* ret;
502 if (e->type() == Type::parint(1)) {
503 std::vector<Expression*> a = eval_comp<EvalIntLit>(env, e);
504 ret = new ArrayLit(e->loc(), a);
505 } else if (e->type() == Type::parbool(1)) {
506 std::vector<Expression*> a = eval_comp<EvalBoolLit>(env, e);
507 ret = new ArrayLit(e->loc(), a);
508 } else if (e->type() == Type::parfloat(1)) {
509 std::vector<Expression*> a = eval_comp<EvalFloatLit>(env, e);
510 ret = new ArrayLit(e->loc(), a);
511 } else if (e->type().st() == Type::ST_SET) {
512 std::vector<Expression*> a = eval_comp<EvalSetLit>(env, e);
513 ret = new ArrayLit(e->loc(), a);
514 } else if (e->type() == Type::parstring(1)) {
515 std::vector<Expression*> a = eval_comp<EvalStringLit>(env, e);
516 ret = new ArrayLit(e->loc(), a);
517 } else {
518 std::vector<Expression*> a = eval_comp<EvalCopy>(env, e);
519 ret = new ArrayLit(e->loc(), a);
520 }
521 ret->type(e->type());
522 return ret;
523}
524
525ArrayLit* eval_array_lit(EnvI& env, Expression* e) {
526 CallStackItem csi(env, e);
527 switch (e->eid()) {
528 case Expression::E_INTLIT:
529 case Expression::E_FLOATLIT:
530 case Expression::E_BOOLLIT:
531 case Expression::E_STRINGLIT:
532 case Expression::E_SETLIT:
533 case Expression::E_ANON:
534 case Expression::E_TI:
535 case Expression::E_TIID:
536 case Expression::E_VARDECL:
537 throw EvalError(env, e->loc(), "not an array expression");
538 case Expression::E_ID:
539 return eval_id<EvalArrayLit>(env, e);
540 case Expression::E_ARRAYLIT:
541 return e->cast<ArrayLit>();
542 case Expression::E_ARRAYACCESS:
543 throw EvalError(env, e->loc(), "arrays of arrays not supported");
544 case Expression::E_COMP:
545 return eval_array_comp(env, e->cast<Comprehension>());
546 case Expression::E_ITE: {
547 ITE* ite = e->cast<ITE>();
548 for (int i = 0; i < ite->size(); i++) {
549 if (eval_bool(env, ite->ifExpr(i))) {
550 return eval_array_lit(env, ite->thenExpr(i));
551 }
552 }
553 return eval_array_lit(env, ite->elseExpr());
554 }
555 case Expression::E_BINOP: {
556 auto* bo = e->cast<BinOp>();
557 if (bo->op() == BOT_PLUSPLUS) {
558 ArrayLit* al0 = eval_array_lit(env, bo->lhs());
559 ArrayLit* al1 = eval_array_lit(env, bo->rhs());
560 std::vector<Expression*> v(al0->size() + al1->size());
561 for (unsigned int i = al0->size(); (i--) != 0U;) {
562 v[i] = (*al0)[i];
563 }
564 for (unsigned int i = al1->size(); (i--) != 0U;) {
565 v[al0->size() + i] = (*al1)[i];
566 }
567 auto* ret = new ArrayLit(e->loc(), v);
568 ret->flat(al0->flat() && al1->flat());
569 ret->type(e->type());
570 return ret;
571 }
572 if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) {
573 return eval_call<EvalArrayLitCopy, BinOp>(env, bo);
574 }
575 throw EvalError(env, e->loc(), "not an array expression", bo->opToString());
576
577 } break;
578 case Expression::E_UNOP: {
579 UnOp* uo = e->cast<UnOp>();
580 if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) {
581 return eval_call<EvalArrayLitCopy, UnOp>(env, uo);
582 }
583 throw EvalError(env, e->loc(), "not an array expression");
584 }
585 case Expression::E_CALL: {
586 Call* ce = e->cast<Call>();
587 if (ce->decl() == nullptr) {
588 throw EvalError(env, e->loc(), "undeclared function", ce->id());
589 }
590
591 if (ce->decl()->builtins.e != nullptr) {
592 return eval_array_lit(env, ce->decl()->builtins.e(env, ce));
593 }
594
595 if (ce->decl()->e() == nullptr) {
596 std::ostringstream ss;
597 ss << "internal error: missing builtin '" << ce->id() << "'";
598 throw EvalError(env, ce->loc(), ss.str());
599 }
600
601 return eval_call<EvalArrayLitCopy>(env, ce);
602 }
603 case Expression::E_LET: {
604 Let* l = e->cast<Let>();
605 l->pushbindings();
606 for (unsigned int i = 0; i < l->let().size(); i++) {
607 // Evaluate all variable declarations
608 if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) {
609 vdi->e(eval_par(env, vdi->e()));
610 check_par_declaration(env, vdi);
611 } else {
612 // This is a constraint item. Since the let is par,
613 // it can only be a par bool expression. If it evaluates
614 // to false, it means that the value of this let is undefined.
615 if (!eval_bool(env, l->let()[i])) {
616 throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed");
617 }
618 }
619 }
620 ArrayLit* l_in = eval_array_lit(env, l->in());
621 auto* ret = copy(env, l_in, true)->cast<ArrayLit>();
622 ret->flat(l_in->flat());
623 l->popbindings();
624 return ret;
625 }
626 }
627 assert(false);
628 return nullptr;
629}
630
631Expression* eval_arrayaccess(EnvI& env, ArrayLit* al, const std::vector<IntVal>& idx,
632 bool& success) {
633 success = true;
634 assert(al->dims() == idx.size());
635 IntVal realidx = 0;
636 int realdim = 1;
637 for (int i = 0; i < al->dims(); i++) {
638 realdim *= al->max(i) - al->min(i) + 1;
639 }
640 for (int i = 0; i < al->dims(); i++) {
641 IntVal ix = idx[i];
642 if (ix < al->min(i) || ix > al->max(i)) {
643 success = false;
644 Type t = al->type();
645 t.dim(0);
646 if (t.isint()) {
647 return IntLit::a(0);
648 }
649 if (t.isbool()) {
650 return constants().literalFalse;
651 }
652 if (t.isfloat()) {
653 return FloatLit::a(0.0);
654 }
655 if (t.st() == Type::ST_SET || t.isbot()) {
656 auto* ret = new SetLit(Location(), std::vector<Expression*>());
657 ret->type(t);
658 return ret;
659 }
660 if (t.isstring()) {
661 return new StringLit(Location(), "");
662 }
663 throw EvalError(env, al->loc(), "Internal error: unexpected type in array access expression");
664 }
665 realdim /= al->max(i) - al->min(i) + 1;
666 realidx += (ix - al->min(i)) * realdim;
667 }
668 assert(realidx >= 0 && realidx <= al->size());
669 return (*al)[static_cast<unsigned int>(realidx.toInt())];
670}
671Expression* eval_arrayaccess(EnvI& env, ArrayAccess* e, bool& success) {
672 ArrayLit* al = eval_array_lit(env, e->v());
673 std::vector<IntVal> dims(e->idx().size());
674 for (unsigned int i = e->idx().size(); (i--) != 0U;) {
675 dims[i] = eval_int(env, e->idx()[i]);
676 }
677 return eval_arrayaccess(env, al, dims, success);
678}
679Expression* eval_arrayaccess(EnvI& env, ArrayAccess* e) {
680 bool success;
681 Expression* ret = eval_arrayaccess(env, e, success);
682 if (success) {
683 return ret;
684 }
685 throw ResultUndefinedError(env, e->loc(), "array access out of bounds");
686}
687
688SetLit* eval_set_lit(EnvI& env, Expression* e) {
689 switch (e->type().bt()) {
690 case Type::BT_INT:
691 case Type::BT_BOT:
692 return new SetLit(e->loc(), eval_intset(env, e));
693 case Type::BT_BOOL: {
694 auto* sl = new SetLit(e->loc(), eval_boolset(env, e));
695 sl->type(Type::parsetbool());
696 return sl;
697 }
698 case Type::BT_FLOAT:
699 return new SetLit(e->loc(), eval_floatset(env, e));
700 default:
701 throw InternalError("invalid set literal type");
702 }
703}
704
705IntSetVal* eval_intset(EnvI& env, Expression* e) {
706 if (auto* sl = e->dynamicCast<SetLit>()) {
707 if (sl->isv() != nullptr) {
708 return sl->isv();
709 }
710 }
711 CallStackItem csi(env, e);
712 switch (e->eid()) {
713 case Expression::E_SETLIT: {
714 auto* sl = e->cast<SetLit>();
715 std::vector<IntVal> vals;
716 for (unsigned int i = 0; i < sl->v().size(); i++) {
717 Expression* vi = eval_par(env, sl->v()[i]);
718 if (vi != constants().absent) {
719 vals.push_back(eval_int(env, vi));
720 }
721 }
722 return IntSetVal::a(vals);
723 }
724 case Expression::E_BOOLLIT:
725 case Expression::E_INTLIT:
726 case Expression::E_FLOATLIT:
727 case Expression::E_STRINGLIT:
728 case Expression::E_ANON:
729 case Expression::E_TIID:
730 case Expression::E_VARDECL:
731 case Expression::E_TI:
732 throw EvalError(env, e->loc(), "not a set of int expression");
733 break;
734 case Expression::E_ARRAYLIT: {
735 auto* al = e->cast<ArrayLit>();
736 std::vector<IntVal> vals(al->size());
737 for (unsigned int i = 0; i < al->size(); i++) {
738 vals[i] = eval_int(env, (*al)[i]);
739 }
740 return IntSetVal::a(vals);
741 } break;
742 case Expression::E_COMP: {
743 auto* c = e->cast<Comprehension>();
744 std::vector<IntVal> a = eval_comp<EvalIntVal>(env, c);
745 return IntSetVal::a(a);
746 }
747 case Expression::E_ID: {
748 GCLock lock;
749 return eval_id<EvalSetLit>(env, e)->isv();
750 } break;
751 case Expression::E_ARRAYACCESS: {
752 GCLock lock;
753 return eval_intset(env, eval_arrayaccess(env, e->cast<ArrayAccess>()));
754 } break;
755 case Expression::E_ITE: {
756 ITE* ite = e->cast<ITE>();
757 for (int i = 0; i < ite->size(); i++) {
758 if (eval_bool(env, ite->ifExpr(i))) {
759 return eval_intset(env, ite->thenExpr(i));
760 }
761 }
762 return eval_intset(env, ite->elseExpr());
763 } break;
764 case Expression::E_BINOP: {
765 auto* bo = e->cast<BinOp>();
766 if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) {
767 return eval_call<EvalIntSet, BinOp>(env, bo);
768 }
769 Expression* lhs = eval_par(env, bo->lhs());
770 Expression* rhs = eval_par(env, bo->rhs());
771 if (lhs->type().isIntSet() && rhs->type().isIntSet()) {
772 IntSetVal* v0 = eval_intset(env, lhs);
773 IntSetVal* v1 = eval_intset(env, rhs);
774 IntSetRanges ir0(v0);
775 IntSetRanges ir1(v1);
776 switch (bo->op()) {
777 case BOT_UNION: {
778 Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1);
779 return IntSetVal::ai(u);
780 }
781 case BOT_DIFF: {
782 Ranges::Diff<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1);
783 return IntSetVal::ai(u);
784 }
785 case BOT_SYMDIFF: {
786 Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1);
787 Ranges::Inter<IntVal, IntSetRanges, IntSetRanges> i(ir0, ir1);
788 Ranges::Diff<IntVal, Ranges::Union<IntVal, IntSetRanges, IntSetRanges>,
789 Ranges::Inter<IntVal, IntSetRanges, IntSetRanges>>
790 sd(u, i);
791 return IntSetVal::ai(sd);
792 }
793 case BOT_INTERSECT: {
794 Ranges::Inter<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1);
795 return IntSetVal::ai(u);
796 }
797 default:
798 throw EvalError(env, e->loc(), "not a set of int expression", bo->opToString());
799 }
800 } else if (lhs->type().isint() && rhs->type().isint()) {
801 if (bo->op() != BOT_DOTDOT) {
802 throw EvalError(env, e->loc(), "not a set of int expression", bo->opToString());
803 }
804 return IntSetVal::a(eval_int(env, lhs), eval_int(env, rhs));
805 } else {
806 throw EvalError(env, e->loc(), "not a set of int expression", bo->opToString());
807 }
808 } break;
809 case Expression::E_UNOP: {
810 UnOp* uo = e->cast<UnOp>();
811 if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) {
812 return eval_call<EvalIntSet, UnOp>(env, uo);
813 }
814 throw EvalError(env, e->loc(), "not a set of int expression");
815 }
816 case Expression::E_CALL: {
817 Call* ce = e->cast<Call>();
818 if (ce->decl() == nullptr) {
819 throw EvalError(env, e->loc(), "undeclared function", ce->id());
820 }
821
822 if (ce->decl()->builtins.s != nullptr) {
823 return ce->decl()->builtins.s(env, ce);
824 }
825
826 if (ce->decl()->builtins.e != nullptr) {
827 return eval_intset(env, ce->decl()->builtins.e(env, ce));
828 }
829
830 if (ce->decl()->e() == nullptr) {
831 std::ostringstream ss;
832 ss << "internal error: missing builtin '" << ce->id() << "'";
833 throw EvalError(env, ce->loc(), ss.str());
834 }
835
836 return eval_call<EvalIntSet>(env, ce);
837 } break;
838 case Expression::E_LET: {
839 Let* l = e->cast<Let>();
840 l->pushbindings();
841 for (unsigned int i = 0; i < l->let().size(); i++) {
842 // Evaluate all variable declarations
843 if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) {
844 vdi->e(eval_par(env, vdi->e()));
845 check_par_declaration(env, vdi);
846 } else {
847 // This is a constraint item. Since the let is par,
848 // it can only be a par bool expression. If it evaluates
849 // to false, it means that the value of this let is undefined.
850 if (!eval_bool(env, l->let()[i])) {
851 throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed");
852 }
853 }
854 }
855 IntSetVal* ret = eval_intset(env, l->in());
856 l->popbindings();
857 return ret;
858 } break;
859 default:
860 assert(false);
861 return nullptr;
862 }
863}
864
865FloatSetVal* eval_floatset(EnvI& env, Expression* e) {
866 if (auto* sl = e->dynamicCast<SetLit>()) {
867 if (sl->fsv() != nullptr) {
868 return sl->fsv();
869 }
870 if (sl->isv() != nullptr) {
871 IntSetRanges isr(sl->isv());
872 return FloatSetVal::ai(isr);
873 }
874 }
875 CallStackItem csi(env, e);
876 switch (e->eid()) {
877 case Expression::E_SETLIT: {
878 auto* sl = e->cast<SetLit>();
879 std::vector<FloatVal> vals;
880 for (unsigned int i = 0; i < sl->v().size(); i++) {
881 Expression* vi = eval_par(env, sl->v()[i]);
882 if (vi != constants().absent) {
883 vals.push_back(eval_float(env, vi));
884 }
885 }
886 return FloatSetVal::a(vals);
887 }
888 case Expression::E_BOOLLIT:
889 case Expression::E_INTLIT:
890 case Expression::E_FLOATLIT:
891 case Expression::E_STRINGLIT:
892 case Expression::E_ANON:
893 case Expression::E_TIID:
894 case Expression::E_VARDECL:
895 case Expression::E_TI:
896 throw EvalError(env, e->loc(), "not a set of float expression");
897 break;
898 case Expression::E_ARRAYLIT: {
899 auto* al = e->cast<ArrayLit>();
900 std::vector<FloatVal> vals(al->size());
901 for (unsigned int i = 0; i < al->size(); i++) {
902 vals[i] = eval_float(env, (*al)[i]);
903 }
904 return FloatSetVal::a(vals);
905 } break;
906 case Expression::E_COMP: {
907 auto* c = e->cast<Comprehension>();
908 std::vector<FloatVal> a = eval_comp<EvalFloatVal>(env, c);
909 return FloatSetVal::a(a);
910 }
911 case Expression::E_ID: {
912 GCLock lock;
913 return eval_floatset(env, eval_id<EvalFloatSetLit>(env, e));
914 } break;
915 case Expression::E_ARRAYACCESS: {
916 GCLock lock;
917 return eval_floatset(env, eval_arrayaccess(env, e->cast<ArrayAccess>()));
918 } break;
919 case Expression::E_ITE: {
920 ITE* ite = e->cast<ITE>();
921 for (int i = 0; i < ite->size(); i++) {
922 if (eval_bool(env, ite->ifExpr(i))) {
923 return eval_floatset(env, ite->thenExpr(i));
924 }
925 }
926 return eval_floatset(env, ite->elseExpr());
927 } break;
928 case Expression::E_BINOP: {
929 auto* bo = e->cast<BinOp>();
930 if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) {
931 return eval_call<EvalFloatSet, BinOp>(env, bo);
932 }
933 Expression* lhs = eval_par(env, bo->lhs());
934 Expression* rhs = eval_par(env, bo->rhs());
935 if (lhs->type().isFloatSet() && rhs->type().isFloatSet()) {
936 FloatSetVal* v0 = eval_floatset(env, lhs);
937 FloatSetVal* v1 = eval_floatset(env, rhs);
938 FloatSetRanges fr0(v0);
939 FloatSetRanges fr1(v1);
940 switch (bo->op()) {
941 case BOT_UNION: {
942 Ranges::Union<FloatVal, FloatSetRanges, FloatSetRanges> u(fr0, fr1);
943 return FloatSetVal::ai(u);
944 }
945 case BOT_DIFF: {
946 Ranges::Diff<FloatVal, FloatSetRanges, FloatSetRanges> u(fr0, fr1);
947 return FloatSetVal::ai(u);
948 }
949 case BOT_SYMDIFF: {
950 Ranges::Union<FloatVal, FloatSetRanges, FloatSetRanges> u(fr0, fr1);
951 Ranges::Inter<FloatVal, FloatSetRanges, FloatSetRanges> i(fr0, fr1);
952 Ranges::Diff<FloatVal, Ranges::Union<FloatVal, FloatSetRanges, FloatSetRanges>,
953 Ranges::Inter<FloatVal, FloatSetRanges, FloatSetRanges>>
954 sd(u, i);
955 return FloatSetVal::ai(sd);
956 }
957 case BOT_INTERSECT: {
958 Ranges::Inter<FloatVal, FloatSetRanges, FloatSetRanges> u(fr0, fr1);
959 return FloatSetVal::ai(u);
960 }
961 default:
962 throw EvalError(env, e->loc(), "not a set of int expression", bo->opToString());
963 }
964 } else if (lhs->type().isfloat() && rhs->type().isfloat()) {
965 if (bo->op() != BOT_DOTDOT) {
966 throw EvalError(env, e->loc(), "not a set of float expression", bo->opToString());
967 }
968 return FloatSetVal::a(eval_float(env, lhs), eval_float(env, rhs));
969 } else {
970 throw EvalError(env, e->loc(), "not a set of float expression", bo->opToString());
971 }
972 } break;
973 case Expression::E_UNOP: {
974 UnOp* uo = e->cast<UnOp>();
975 if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) {
976 return eval_call<EvalFloatSet, UnOp>(env, uo);
977 }
978 throw EvalError(env, e->loc(), "not a set of float expression");
979 }
980 case Expression::E_CALL: {
981 Call* ce = e->cast<Call>();
982 if (ce->decl() == nullptr) {
983 throw EvalError(env, e->loc(), "undeclared function", ce->id());
984 }
985
986 if (ce->decl()->builtins.e != nullptr) {
987 return eval_floatset(env, ce->decl()->builtins.e(env, ce));
988 }
989
990 if (ce->decl()->e() == nullptr) {
991 std::ostringstream ss;
992 ss << "internal error: missing builtin '" << ce->id() << "'";
993 throw EvalError(env, ce->loc(), ss.str());
994 }
995
996 return eval_call<EvalFloatSet>(env, ce);
997 } break;
998 case Expression::E_LET: {
999 Let* l = e->cast<Let>();
1000 l->pushbindings();
1001 for (unsigned int i = 0; i < l->let().size(); i++) {
1002 // Evaluate all variable declarations
1003 if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) {
1004 vdi->e(eval_par(env, vdi->e()));
1005 check_par_declaration(env, vdi);
1006 } else {
1007 // This is a constraint item. Since the let is par,
1008 // it can only be a par bool expression. If it evaluates
1009 // to false, it means that the value of this let is undefined.
1010 if (!eval_bool(env, l->let()[i])) {
1011 throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed");
1012 }
1013 }
1014 }
1015 FloatSetVal* ret = eval_floatset(env, l->in());
1016 l->popbindings();
1017 return ret;
1018 } break;
1019 default:
1020 assert(false);
1021 return nullptr;
1022 }
1023}
1024
1025bool eval_bool(EnvI& env, Expression* e) {
1026 CallStackItem csi(env, e);
1027 try {
1028 if (auto* bl = e->dynamicCast<BoolLit>()) {
1029 return bl->v();
1030 }
1031 switch (e->eid()) {
1032 case Expression::E_INTLIT:
1033 case Expression::E_FLOATLIT:
1034 case Expression::E_STRINGLIT:
1035 case Expression::E_ANON:
1036 case Expression::E_TIID:
1037 case Expression::E_SETLIT:
1038 case Expression::E_ARRAYLIT:
1039 case Expression::E_COMP:
1040 case Expression::E_VARDECL:
1041 case Expression::E_TI:
1042 assert(false);
1043 throw EvalError(env, e->loc(), "not a bool expression");
1044 break;
1045 case Expression::E_ID: {
1046 GCLock lock;
1047 return eval_id<EvalBoolLit>(env, e)->v();
1048 } break;
1049 case Expression::E_ARRAYACCESS: {
1050 GCLock lock;
1051 return eval_bool(env, eval_arrayaccess(env, e->cast<ArrayAccess>()));
1052 } break;
1053 case Expression::E_ITE: {
1054 ITE* ite = e->cast<ITE>();
1055 for (int i = 0; i < ite->size(); i++) {
1056 if (eval_bool(env, ite->ifExpr(i))) {
1057 return eval_bool(env, ite->thenExpr(i));
1058 }
1059 }
1060 return eval_bool(env, ite->elseExpr());
1061 } break;
1062 case Expression::E_BINOP: {
1063 auto* bo = e->cast<BinOp>();
1064 Expression* lhs = bo->lhs();
1065 if (lhs->type().bt() == Type::BT_TOP) {
1066 lhs = eval_par(env, lhs);
1067 }
1068 Expression* rhs = bo->rhs();
1069 if (rhs->type().bt() == Type::BT_TOP) {
1070 rhs = eval_par(env, rhs);
1071 }
1072 if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) {
1073 return eval_call<EvalBoolVal, BinOp>(env, bo);
1074 }
1075
1076 if (lhs->type().isbool() && rhs->type().isbool()) {
1077 try {
1078 switch (bo->op()) {
1079 case BOT_LE:
1080 return static_cast<int>(eval_bool(env, lhs)) <
1081 static_cast<int>(eval_bool(env, rhs));
1082 case BOT_LQ:
1083 return static_cast<int>(eval_bool(env, lhs)) <=
1084 static_cast<int>(eval_bool(env, rhs));
1085 case BOT_GR:
1086 return static_cast<int>(eval_bool(env, lhs)) >
1087 static_cast<int>(eval_bool(env, rhs));
1088 case BOT_GQ:
1089 return static_cast<int>(eval_bool(env, lhs)) >=
1090 static_cast<int>(eval_bool(env, rhs));
1091 case BOT_EQ:
1092 return eval_bool(env, lhs) == eval_bool(env, rhs);
1093 case BOT_NQ:
1094 return eval_bool(env, lhs) != eval_bool(env, rhs);
1095 case BOT_EQUIV:
1096 return eval_bool(env, lhs) == eval_bool(env, rhs);
1097 case BOT_IMPL:
1098 return (!eval_bool(env, lhs)) || eval_bool(env, rhs);
1099 case BOT_RIMPL:
1100 return (!eval_bool(env, rhs)) || eval_bool(env, lhs);
1101 case BOT_OR:
1102 return eval_bool(env, lhs) || eval_bool(env, rhs);
1103 case BOT_AND:
1104 return eval_bool(env, lhs) && eval_bool(env, rhs);
1105 case BOT_XOR:
1106 return eval_bool(env, lhs) ^ eval_bool(env, rhs);
1107 default:
1108 assert(false);
1109 throw EvalError(env, e->loc(), "not a bool expression", bo->opToString());
1110 }
1111 } catch (ResultUndefinedError&) {
1112 return false;
1113 }
1114 } else if (lhs->type().isint() && rhs->type().isint()) {
1115 try {
1116 IntVal v0 = eval_int(env, lhs);
1117 IntVal v1 = eval_int(env, rhs);
1118 switch (bo->op()) {
1119 case BOT_LE:
1120 return v0 < v1;
1121 case BOT_LQ:
1122 return v0 <= v1;
1123 case BOT_GR:
1124 return v0 > v1;
1125 case BOT_GQ:
1126 return v0 >= v1;
1127 case BOT_EQ:
1128 return v0 == v1;
1129 case BOT_NQ:
1130 return v0 != v1;
1131 default:
1132 assert(false);
1133 throw EvalError(env, e->loc(), "not a bool expression", bo->opToString());
1134 }
1135 } catch (ResultUndefinedError&) {
1136 return false;
1137 }
1138 } else if (lhs->type().isfloat() && rhs->type().isfloat()) {
1139 try {
1140 FloatVal v0 = eval_float(env, lhs);
1141 FloatVal v1 = eval_float(env, rhs);
1142 switch (bo->op()) {
1143 case BOT_LE:
1144 return v0 < v1;
1145 case BOT_LQ:
1146 return v0 <= v1;
1147 case BOT_GR:
1148 return v0 > v1;
1149 case BOT_GQ:
1150 return v0 >= v1;
1151 case BOT_EQ:
1152 return v0 == v1;
1153 case BOT_NQ:
1154 return v0 != v1;
1155 default:
1156 assert(false);
1157 throw EvalError(env, e->loc(), "not a bool expression", bo->opToString());
1158 }
1159 } catch (ResultUndefinedError&) {
1160 return false;
1161 }
1162 } else if (lhs->type().isint() && rhs->type().isIntSet()) {
1163 try {
1164 IntVal v0 = eval_int(env, lhs);
1165 GCLock lock;
1166 IntSetVal* v1 = eval_intset(env, rhs);
1167 switch (bo->op()) {
1168 case BOT_IN:
1169 return v1->contains(v0);
1170 default:
1171 assert(false);
1172 throw EvalError(env, e->loc(), "not a bool expression", bo->opToString());
1173 }
1174 } catch (ResultUndefinedError&) {
1175 return false;
1176 }
1177 } else if (lhs->type().isfloat() && rhs->type().isFloatSet()) {
1178 try {
1179 FloatVal v0 = eval_float(env, lhs);
1180 GCLock lock;
1181 FloatSetVal* v1 = eval_floatset(env, rhs);
1182 switch (bo->op()) {
1183 case BOT_IN:
1184 return v1->contains(v0);
1185 default:
1186 assert(false);
1187 throw EvalError(env, e->loc(), "not a bool expression", bo->opToString());
1188 }
1189 } catch (ResultUndefinedError&) {
1190 return false;
1191 }
1192 } else if (lhs->type().isSet() && rhs->type().isSet()) {
1193 try {
1194 GCLock lock;
1195 IntSetVal* v0 = eval_intset(env, lhs);
1196 IntSetVal* v1 = eval_intset(env, rhs);
1197 IntSetRanges ir0(v0);
1198 IntSetRanges ir1(v1);
1199 switch (bo->op()) {
1200 case BOT_LE:
1201 return Ranges::less(ir0, ir1);
1202 case BOT_LQ:
1203 return Ranges::less_eq(ir0, ir1);
1204 case BOT_GR:
1205 return Ranges::less(ir1, ir0);
1206 case BOT_GQ:
1207 return Ranges::less_eq(ir1, ir0);
1208 case BOT_EQ:
1209 return Ranges::equal(ir0, ir1);
1210 case BOT_NQ:
1211 return !Ranges::equal(ir0, ir1);
1212 case BOT_SUBSET:
1213 return Ranges::subset(ir0, ir1);
1214 case BOT_SUPERSET:
1215 return Ranges::subset(ir1, ir0);
1216 default:
1217 throw EvalError(env, e->loc(), "not a bool expression", bo->opToString());
1218 }
1219 } catch (ResultUndefinedError&) {
1220 return false;
1221 }
1222 } else if (lhs->type().isstring() && rhs->type().isstring()) {
1223 try {
1224 GCLock lock;
1225 std::string s0 = eval_string(env, lhs);
1226 std::string s1 = eval_string(env, rhs);
1227 switch (bo->op()) {
1228 case BOT_EQ:
1229 return s0 == s1;
1230 case BOT_NQ:
1231 return s0 != s1;
1232 case BOT_LE:
1233 return s0 < s1;
1234 case BOT_LQ:
1235 return s0 <= s1;
1236 case BOT_GR:
1237 return s0 > s1;
1238 case BOT_GQ:
1239 return s0 >= s1;
1240 default:
1241 throw EvalError(env, e->loc(), "not a bool expression", bo->opToString());
1242 }
1243 } catch (ResultUndefinedError&) {
1244 return false;
1245 }
1246 } else if (bo->op() == BOT_EQ && lhs->type().isAnn()) {
1247 return Expression::equal(lhs, rhs);
1248 } else if (bo->op() == BOT_EQ && lhs->type().dim() > 0 && rhs->type().dim() > 0) {
1249 try {
1250 ArrayLit* al0 = eval_array_lit(env, lhs);
1251 ArrayLit* al1 = eval_array_lit(env, rhs);
1252 if (al0->size() != al1->size()) {
1253 return false;
1254 }
1255 for (unsigned int i = 0; i < al0->size(); i++) {
1256 if (!Expression::equal(eval_par(env, (*al0)[i]), eval_par(env, (*al1)[i]))) {
1257 return false;
1258 }
1259 }
1260 return true;
1261 } catch (ResultUndefinedError&) {
1262 return false;
1263 }
1264 } else {
1265 throw EvalError(env, e->loc(), "not a bool expression", bo->opToString());
1266 }
1267 } break;
1268 case Expression::E_UNOP: {
1269 UnOp* uo = e->cast<UnOp>();
1270 if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) {
1271 return eval_call<EvalBoolVal, UnOp>(env, uo);
1272 }
1273 bool v0 = eval_bool(env, uo->e());
1274 switch (uo->op()) {
1275 case UOT_NOT:
1276 return !v0;
1277 default:
1278 assert(false);
1279 throw EvalError(env, e->loc(), "not a bool expression", uo->opToString());
1280 }
1281 } break;
1282 case Expression::E_CALL: {
1283 try {
1284 Call* ce = e->cast<Call>();
1285 if (ce->decl() == nullptr) {
1286 throw EvalError(env, e->loc(), "undeclared function", ce->id());
1287 }
1288
1289 if (ce->decl()->builtins.b != nullptr) {
1290 return ce->decl()->builtins.b(env, ce);
1291 }
1292
1293 if (ce->decl()->builtins.e != nullptr) {
1294 return eval_bool(env, ce->decl()->builtins.e(env, ce));
1295 }
1296
1297 if (ce->decl()->e() == nullptr) {
1298 std::ostringstream ss;
1299 ss << "internal error: missing builtin '" << ce->id() << "'";
1300 throw EvalError(env, ce->loc(), ss.str());
1301 }
1302
1303 return eval_call<EvalBoolVal>(env, ce);
1304 } catch (ResultUndefinedError&) {
1305 return false;
1306 }
1307 } break;
1308 case Expression::E_LET: {
1309 Let* l = e->cast<Let>();
1310 l->pushbindings();
1311 bool ret = true;
1312 for (unsigned int i = 0; i < l->let().size(); i++) {
1313 // Evaluate all variable declarations
1314 if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) {
1315 vdi->e(eval_par(env, vdi->e()));
1316 bool maybe_partial = vdi->ann().contains(constants().ann.maybe_partial);
1317 if (maybe_partial) {
1318 env.inMaybePartial++;
1319 }
1320 try {
1321 check_par_declaration(env, vdi);
1322 } catch (ResultUndefinedError&) {
1323 ret = false;
1324 }
1325 if (maybe_partial) {
1326 env.inMaybePartial--;
1327 }
1328 } else {
1329 // This is a constraint item. Since the let is par,
1330 // it can only be a par bool expression. If it evaluates
1331 // to false, it means that the value of this let is false.
1332 if (!eval_bool(env, l->let()[i])) {
1333 if (l->let()[i]->ann().contains(constants().ann.maybe_partial)) {
1334 ret = false;
1335 } else {
1336 throw ResultUndefinedError(env, l->let()[i]->loc(),
1337 "domain constraint in let failed");
1338 }
1339 }
1340 }
1341 }
1342 ret = ret && eval_bool(env, l->in());
1343 l->popbindings();
1344 return ret;
1345 } break;
1346 default:
1347 assert(false);
1348 return false;
1349 }
1350 } catch (ResultUndefinedError&) {
1351 // undefined means false
1352 return false;
1353 }
1354}
1355
1356IntSetVal* eval_boolset(EnvI& env, Expression* e) {
1357 CallStackItem csi(env, e);
1358 switch (e->eid()) {
1359 case Expression::E_SETLIT: {
1360 auto* sl = e->cast<SetLit>();
1361 if (sl->isv() != nullptr) {
1362 return sl->isv();
1363 }
1364 std::vector<IntVal> vals;
1365 for (unsigned int i = 0; i < sl->v().size(); i++) {
1366 Expression* vi = eval_par(env, sl->v()[i]);
1367 if (vi != constants().absent) {
1368 vals.push_back(eval_int(env, vi));
1369 }
1370 }
1371 return IntSetVal::a(vals);
1372 }
1373 case Expression::E_BOOLLIT:
1374 case Expression::E_INTLIT:
1375 case Expression::E_FLOATLIT:
1376 case Expression::E_STRINGLIT:
1377 case Expression::E_ANON:
1378 case Expression::E_TIID:
1379 case Expression::E_VARDECL:
1380 case Expression::E_TI:
1381 throw EvalError(env, e->loc(), "not a set of bool expression");
1382 break;
1383 case Expression::E_ARRAYLIT: {
1384 auto* al = e->cast<ArrayLit>();
1385 std::vector<IntVal> vals(al->size());
1386 for (unsigned int i = 0; i < al->size(); i++) {
1387 vals[i] = static_cast<long long>(eval_bool(env, (*al)[i]));
1388 }
1389 return IntSetVal::a(vals);
1390 } break;
1391 case Expression::E_COMP: {
1392 auto* c = e->cast<Comprehension>();
1393 std::vector<IntVal> a = eval_comp<EvalIntVal>(env, c);
1394 return IntSetVal::a(a);
1395 }
1396 case Expression::E_ID: {
1397 GCLock lock;
1398 return eval_id<EvalBoolSetLit>(env, e)->isv();
1399 } break;
1400 case Expression::E_ARRAYACCESS: {
1401 GCLock lock;
1402 return eval_boolset(env, eval_arrayaccess(env, e->cast<ArrayAccess>()));
1403 } break;
1404 case Expression::E_ITE: {
1405 ITE* ite = e->cast<ITE>();
1406 for (int i = 0; i < ite->size(); i++) {
1407 if (eval_bool(env, ite->ifExpr(i))) {
1408 return eval_boolset(env, ite->thenExpr(i));
1409 }
1410 }
1411 return eval_boolset(env, ite->elseExpr());
1412 } break;
1413 case Expression::E_BINOP: {
1414 auto* bo = e->cast<BinOp>();
1415 if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) {
1416 return eval_call<EvalBoolSet, BinOp>(env, bo);
1417 }
1418 Expression* lhs = eval_par(env, bo->lhs());
1419 Expression* rhs = eval_par(env, bo->rhs());
1420 if (lhs->type().isIntSet() && rhs->type().isIntSet()) {
1421 IntSetVal* v0 = eval_boolset(env, lhs);
1422 IntSetVal* v1 = eval_boolset(env, rhs);
1423 IntSetRanges ir0(v0);
1424 IntSetRanges ir1(v1);
1425 switch (bo->op()) {
1426 case BOT_UNION: {
1427 Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1);
1428 return IntSetVal::ai(u);
1429 }
1430 case BOT_DIFF: {
1431 Ranges::Diff<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1);
1432 return IntSetVal::ai(u);
1433 }
1434 case BOT_SYMDIFF: {
1435 Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1);
1436 Ranges::Inter<IntVal, IntSetRanges, IntSetRanges> i(ir0, ir1);
1437 Ranges::Diff<IntVal, Ranges::Union<IntVal, IntSetRanges, IntSetRanges>,
1438 Ranges::Inter<IntVal, IntSetRanges, IntSetRanges>>
1439 sd(u, i);
1440 return IntSetVal::ai(sd);
1441 }
1442 case BOT_INTERSECT: {
1443 Ranges::Inter<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1);
1444 return IntSetVal::ai(u);
1445 }
1446 default:
1447 throw EvalError(env, e->loc(), "not a set of bool expression", bo->opToString());
1448 }
1449 } else if (lhs->type().isbool() && rhs->type().isbool()) {
1450 if (bo->op() != BOT_DOTDOT) {
1451 throw EvalError(env, e->loc(), "not a set of bool expression", bo->opToString());
1452 }
1453 return IntSetVal::a(static_cast<long long>(eval_bool(env, lhs)),
1454 static_cast<long long>(eval_bool(env, rhs)));
1455 } else {
1456 throw EvalError(env, e->loc(), "not a set of bool expression", bo->opToString());
1457 }
1458 } break;
1459 case Expression::E_UNOP: {
1460 UnOp* uo = e->cast<UnOp>();
1461 if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) {
1462 return eval_call<EvalBoolSet, UnOp>(env, uo);
1463 }
1464 throw EvalError(env, e->loc(), "not a set of bool expression");
1465 }
1466 case Expression::E_CALL: {
1467 Call* ce = e->cast<Call>();
1468 if (ce->decl() == nullptr) {
1469 throw EvalError(env, e->loc(), "undeclared function", ce->id());
1470 }
1471
1472 if (ce->decl()->builtins.s != nullptr) {
1473 return ce->decl()->builtins.s(env, ce);
1474 }
1475
1476 if (ce->decl()->builtins.e != nullptr) {
1477 return eval_boolset(env, ce->decl()->builtins.e(env, ce));
1478 }
1479
1480 if (ce->decl()->e() == nullptr) {
1481 std::ostringstream ss;
1482 ss << "internal error: missing builtin '" << ce->id() << "'";
1483 throw EvalError(env, ce->loc(), ss.str());
1484 }
1485
1486 return eval_call<EvalBoolSet>(env, ce);
1487 } break;
1488 case Expression::E_LET: {
1489 Let* l = e->cast<Let>();
1490 l->pushbindings();
1491 for (unsigned int i = 0; i < l->let().size(); i++) {
1492 // Evaluate all variable declarations
1493 if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) {
1494 vdi->e(eval_par(env, vdi->e()));
1495 check_par_declaration(env, vdi);
1496 } else {
1497 // This is a constraint item. Since the let is par,
1498 // it can only be a par bool expression. If it evaluates
1499 // to false, it means that the value of this let is undefined.
1500 if (!eval_bool(env, l->let()[i])) {
1501 throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed");
1502 }
1503 }
1504 }
1505 IntSetVal* ret = eval_boolset(env, l->in());
1506 l->popbindings();
1507 return ret;
1508 } break;
1509 default:
1510 assert(false);
1511 return nullptr;
1512 }
1513}
1514
1515IntVal eval_int(EnvI& env, Expression* e) {
1516 if (e->type().isbool()) {
1517 return static_cast<long long>(eval_bool(env, e));
1518 }
1519 if (auto* il = e->dynamicCast<IntLit>()) {
1520 return il->v();
1521 }
1522 CallStackItem csi(env, e);
1523 try {
1524 switch (e->eid()) {
1525 case Expression::E_FLOATLIT:
1526 case Expression::E_BOOLLIT:
1527 case Expression::E_STRINGLIT:
1528 case Expression::E_ANON:
1529 case Expression::E_TIID:
1530 case Expression::E_SETLIT:
1531 case Expression::E_ARRAYLIT:
1532 case Expression::E_COMP:
1533 case Expression::E_VARDECL:
1534 case Expression::E_TI:
1535 throw EvalError(env, e->loc(), "not an integer expression");
1536 break;
1537 case Expression::E_ID: {
1538 GCLock lock;
1539 return eval_id<EvalIntLit>(env, e)->v();
1540 } break;
1541 case Expression::E_ARRAYACCESS: {
1542 GCLock lock;
1543 return eval_int(env, eval_arrayaccess(env, e->cast<ArrayAccess>()));
1544 } break;
1545 case Expression::E_ITE: {
1546 ITE* ite = e->cast<ITE>();
1547 for (int i = 0; i < ite->size(); i++) {
1548 if (eval_bool(env, ite->ifExpr(i))) {
1549 return eval_int(env, ite->thenExpr(i));
1550 }
1551 }
1552 return eval_int(env, ite->elseExpr());
1553 } break;
1554 case Expression::E_BINOP: {
1555 auto* bo = e->cast<BinOp>();
1556 if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) {
1557 return eval_call<EvalIntVal, BinOp>(env, bo);
1558 }
1559 IntVal v0 = eval_int(env, bo->lhs());
1560 IntVal v1 = eval_int(env, bo->rhs());
1561 switch (bo->op()) {
1562 case BOT_PLUS:
1563 return v0 + v1;
1564 case BOT_MINUS:
1565 return v0 - v1;
1566 case BOT_MULT:
1567 return v0 * v1;
1568 case BOT_POW:
1569 return v0.pow(v1);
1570 case BOT_IDIV:
1571 if (v1 == 0) {
1572 throw ResultUndefinedError(env, e->loc(), "division by zero");
1573 }
1574 return v0 / v1;
1575 case BOT_MOD:
1576 if (v1 == 0) {
1577 throw ResultUndefinedError(env, e->loc(), "division by zero");
1578 }
1579 return v0 % v1;
1580 default:
1581 throw EvalError(env, e->loc(), "not an integer expression", bo->opToString());
1582 }
1583 } break;
1584 case Expression::E_UNOP: {
1585 UnOp* uo = e->cast<UnOp>();
1586 if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) {
1587 return eval_call<EvalIntVal, UnOp>(env, uo);
1588 }
1589 IntVal v0 = eval_int(env, uo->e());
1590 switch (uo->op()) {
1591 case UOT_PLUS:
1592 return v0;
1593 case UOT_MINUS:
1594 return -v0;
1595 default:
1596 throw EvalError(env, e->loc(), "not an integer expression", uo->opToString());
1597 }
1598 } break;
1599 case Expression::E_CALL: {
1600 Call* ce = e->cast<Call>();
1601 if (ce->decl() == nullptr) {
1602 throw EvalError(env, e->loc(), "undeclared function", ce->id());
1603 }
1604 if (ce->decl()->builtins.i != nullptr) {
1605 return ce->decl()->builtins.i(env, ce);
1606 }
1607
1608 if (ce->decl()->builtins.e != nullptr) {
1609 return eval_int(env, ce->decl()->builtins.e(env, ce));
1610 }
1611
1612 if (ce->decl()->e() == nullptr) {
1613 std::ostringstream ss;
1614 ss << "internal error: missing builtin '" << ce->id() << "'";
1615 throw EvalError(env, ce->loc(), ss.str());
1616 }
1617
1618 return eval_call<EvalIntVal>(env, ce);
1619 } break;
1620 case Expression::E_LET: {
1621 Let* l = e->cast<Let>();
1622 l->pushbindings();
1623 for (unsigned int i = 0; i < l->let().size(); i++) {
1624 // Evaluate all variable declarations
1625 if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) {
1626 vdi->e(eval_par(env, vdi->e()));
1627 check_par_declaration(env, vdi);
1628 } else {
1629 // This is a constraint item. Since the let is par,
1630 // it can only be a par bool expression. If it evaluates
1631 // to false, it means that the value of this let is undefined.
1632 if (!eval_bool(env, l->let()[i])) {
1633 throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed");
1634 }
1635 }
1636 }
1637 IntVal ret = eval_int(env, l->in());
1638 l->popbindings();
1639 return ret;
1640 } break;
1641 default:
1642 assert(false);
1643 return 0;
1644 }
1645 } catch (ArithmeticError& err) {
1646 throw EvalError(env, e->loc(), err.msg());
1647 }
1648}
1649
1650FloatVal eval_float(EnvI& env, Expression* e) {
1651 if (e->type().isint()) {
1652 return static_cast<double>(eval_int(env, e).toInt());
1653 }
1654 if (e->type().isbool()) {
1655 return static_cast<double>(eval_bool(env, e));
1656 }
1657 CallStackItem csi(env, e);
1658 try {
1659 if (auto* fl = e->dynamicCast<FloatLit>()) {
1660 return fl->v();
1661 }
1662 switch (e->eid()) {
1663 case Expression::E_INTLIT:
1664 case Expression::E_BOOLLIT:
1665 case Expression::E_STRINGLIT:
1666 case Expression::E_ANON:
1667 case Expression::E_TIID:
1668 case Expression::E_SETLIT:
1669 case Expression::E_ARRAYLIT:
1670 case Expression::E_COMP:
1671 case Expression::E_VARDECL:
1672 case Expression::E_TI:
1673 throw EvalError(env, e->loc(), "not a float expression");
1674 break;
1675 case Expression::E_ID: {
1676 GCLock lock;
1677 return eval_id<EvalFloatLit>(env, e)->v();
1678 } break;
1679 case Expression::E_ARRAYACCESS: {
1680 GCLock lock;
1681 return eval_float(env, eval_arrayaccess(env, e->cast<ArrayAccess>()));
1682 } break;
1683 case Expression::E_ITE: {
1684 ITE* ite = e->cast<ITE>();
1685 for (int i = 0; i < ite->size(); i++) {
1686 if (eval_bool(env, ite->ifExpr(i))) {
1687 return eval_float(env, ite->thenExpr(i));
1688 }
1689 }
1690 return eval_float(env, ite->elseExpr());
1691 } break;
1692 case Expression::E_BINOP: {
1693 auto* bo = e->cast<BinOp>();
1694 if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) {
1695 return eval_call<EvalFloatVal, BinOp>(env, bo);
1696 }
1697 FloatVal v0 = eval_float(env, bo->lhs());
1698 FloatVal v1 = eval_float(env, bo->rhs());
1699 switch (bo->op()) {
1700 case BOT_PLUS:
1701 return v0 + v1;
1702 case BOT_MINUS:
1703 return v0 - v1;
1704 case BOT_MULT:
1705 return v0 * v1;
1706 case BOT_POW:
1707 return std::pow(v0.toDouble(), v1.toDouble());
1708 case BOT_DIV:
1709 if (v1 == 0.0) {
1710 throw ResultUndefinedError(env, e->loc(), "division by zero");
1711 }
1712 return v0 / v1;
1713 default:
1714 throw EvalError(env, e->loc(), "not a float expression", bo->opToString());
1715 }
1716 } break;
1717 case Expression::E_UNOP: {
1718 UnOp* uo = e->cast<UnOp>();
1719 if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) {
1720 return eval_call<EvalFloatVal, UnOp>(env, uo);
1721 }
1722 FloatVal v0 = eval_float(env, uo->e());
1723 switch (uo->op()) {
1724 case UOT_PLUS:
1725 return v0;
1726 case UOT_MINUS:
1727 return -v0;
1728 default:
1729 throw EvalError(env, e->loc(), "not a float expression", uo->opToString());
1730 }
1731 } break;
1732 case Expression::E_CALL: {
1733 Call* ce = e->cast<Call>();
1734 if (ce->decl() == nullptr) {
1735 throw EvalError(env, e->loc(), "undeclared function", ce->id());
1736 }
1737 if (ce->decl()->builtins.f != nullptr) {
1738 return ce->decl()->builtins.f(env, ce);
1739 }
1740
1741 if (ce->decl()->builtins.e != nullptr) {
1742 return eval_float(env, ce->decl()->builtins.e(env, ce));
1743 }
1744
1745 if (ce->decl()->e() == nullptr) {
1746 std::ostringstream ss;
1747 ss << "internal error: missing builtin '" << ce->id() << "'";
1748 throw EvalError(env, ce->loc(), ss.str());
1749 }
1750
1751 return eval_call<EvalFloatVal>(env, ce);
1752 } break;
1753 case Expression::E_LET: {
1754 Let* l = e->cast<Let>();
1755 l->pushbindings();
1756 for (unsigned int i = 0; i < l->let().size(); i++) {
1757 // Evaluate all variable declarations
1758 if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) {
1759 vdi->e(eval_par(env, vdi->e()));
1760 check_par_declaration(env, vdi);
1761 } else {
1762 // This is a constraint item. Since the let is par,
1763 // it can only be a par bool expression. If it evaluates
1764 // to false, it means that the value of this let is undefined.
1765 if (!eval_bool(env, l->let()[i])) {
1766 throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed");
1767 }
1768 }
1769 }
1770 FloatVal ret = eval_float(env, l->in());
1771 l->popbindings();
1772 return ret;
1773 } break;
1774 default:
1775 assert(false);
1776 return 0.0;
1777 }
1778 } catch (ArithmeticError& err) {
1779 throw EvalError(env, e->loc(), err.msg());
1780 }
1781}
1782
1783std::string eval_string(EnvI& env, Expression* e) {
1784 CallStackItem csi(env, e);
1785 switch (e->eid()) {
1786 case Expression::E_STRINGLIT: {
1787 ASTString str = e->cast<StringLit>()->v();
1788 return std::string(str.c_str(), str.size());
1789 }
1790 case Expression::E_FLOATLIT:
1791 case Expression::E_INTLIT:
1792 case Expression::E_BOOLLIT:
1793 case Expression::E_ANON:
1794 case Expression::E_TIID:
1795 case Expression::E_SETLIT:
1796 case Expression::E_ARRAYLIT:
1797 case Expression::E_COMP:
1798 case Expression::E_VARDECL:
1799 case Expression::E_TI:
1800 throw EvalError(env, e->loc(), "not a string expression");
1801 break;
1802 case Expression::E_ID: {
1803 GCLock lock;
1804 ASTString str = eval_id<EvalStringLit>(env, e)->v();
1805 return std::string(str.c_str(), str.size());
1806 } break;
1807 case Expression::E_ARRAYACCESS: {
1808 GCLock lock;
1809 return eval_string(env, eval_arrayaccess(env, e->cast<ArrayAccess>()));
1810 } break;
1811 case Expression::E_ITE: {
1812 ITE* ite = e->cast<ITE>();
1813 for (int i = 0; i < ite->size(); i++) {
1814 if (eval_bool(env, ite->ifExpr(i))) {
1815 return eval_string(env, ite->thenExpr(i));
1816 }
1817 }
1818 return eval_string(env, ite->elseExpr());
1819 } break;
1820 case Expression::E_BINOP: {
1821 auto* bo = e->cast<BinOp>();
1822 if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) {
1823 return eval_call<EvalString, BinOp>(env, bo);
1824 }
1825 std::string v0 = eval_string(env, bo->lhs());
1826 std::string v1 = eval_string(env, bo->rhs());
1827 switch (bo->op()) {
1828 case BOT_PLUSPLUS:
1829 return v0 + v1;
1830 default:
1831 throw EvalError(env, e->loc(), "not a string expression", bo->opToString());
1832 }
1833 } break;
1834 case Expression::E_UNOP: {
1835 UnOp* uo = e->cast<UnOp>();
1836 if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) {
1837 return eval_call<EvalString, UnOp>(env, uo);
1838 }
1839 throw EvalError(env, e->loc(), "not a string expression");
1840 } break;
1841 case Expression::E_CALL: {
1842 Call* ce = e->cast<Call>();
1843 if (ce->decl() == nullptr) {
1844 throw EvalError(env, e->loc(), "undeclared function", ce->id());
1845 }
1846
1847 if (ce->decl()->builtins.str != nullptr) {
1848 return ce->decl()->builtins.str(env, ce);
1849 }
1850 if (ce->decl()->builtins.e != nullptr) {
1851 return eval_string(env, ce->decl()->builtins.e(env, ce));
1852 }
1853
1854 if (ce->decl()->e() == nullptr) {
1855 std::ostringstream ss;
1856 ss << "internal error: missing builtin '" << ce->id() << "'";
1857 throw EvalError(env, ce->loc(), ss.str());
1858 }
1859
1860 return eval_call<EvalString>(env, ce);
1861 } break;
1862 case Expression::E_LET: {
1863 Let* l = e->cast<Let>();
1864 l->pushbindings();
1865 for (unsigned int i = 0; i < l->let().size(); i++) {
1866 // Evaluate all variable declarations
1867 if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) {
1868 vdi->e(eval_par(env, vdi->e()));
1869 check_par_declaration(env, vdi);
1870 } else {
1871 // This is a constraint item. Since the let is par,
1872 // it can only be a par bool expression. If it evaluates
1873 // to false, it means that the value of this let is undefined.
1874 if (!eval_bool(env, l->let()[i])) {
1875 throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed");
1876 }
1877 }
1878 }
1879 std::string ret = eval_string(env, l->in());
1880 l->popbindings();
1881 return ret;
1882 } break;
1883 default:
1884 assert(false);
1885 return "";
1886 }
1887}
1888
1889Expression* eval_par(EnvI& env, Expression* e) {
1890 if (e == nullptr) {
1891 return nullptr;
1892 }
1893 switch (e->eid()) {
1894 case Expression::E_ANON:
1895 case Expression::E_TIID: {
1896 return e;
1897 }
1898 case Expression::E_COMP:
1899 if (e->cast<Comprehension>()->set()) {
1900 return EvalSetLit::e(env, e);
1901 }
1902 // fall through
1903 case Expression::E_ARRAYLIT: {
1904 ArrayLit* al = eval_array_lit(env, e);
1905 std::vector<Expression*> args(al->size());
1906 for (unsigned int i = al->size(); (i--) != 0U;) {
1907 args[i] = eval_par(env, (*al)[i]);
1908 }
1909 std::vector<std::pair<int, int>> dims(al->dims());
1910 for (unsigned int i = al->dims(); (i--) != 0U;) {
1911 dims[i].first = al->min(i);
1912 dims[i].second = al->max(i);
1913 }
1914 auto* ret = new ArrayLit(al->loc(), args, dims);
1915 Type t = al->type();
1916 if (t.isbot() && ret->size() > 0) {
1917 t.bt((*ret)[0]->type().bt());
1918 }
1919 ret->type(t);
1920 return ret;
1921 }
1922 case Expression::E_VARDECL: {
1923 auto* vd = e->cast<VarDecl>();
1924 throw EvalError(env, vd->loc(), "cannot evaluate variable declaration", vd->id()->v());
1925 }
1926 case Expression::E_TI: {
1927 auto* t = e->cast<TypeInst>();
1928 ASTExprVec<TypeInst> r;
1929 if (t->ranges().size() > 0) {
1930 std::vector<TypeInst*> rv(t->ranges().size());
1931 for (unsigned int i = t->ranges().size(); (i--) != 0U;) {
1932 rv[i] = static_cast<TypeInst*>(eval_par(env, t->ranges()[i]));
1933 }
1934 r = ASTExprVec<TypeInst>(rv);
1935 }
1936 return new TypeInst(Location(), t->type(), r, eval_par(env, t->domain()));
1937 }
1938 case Expression::E_ID: {
1939 if (e == constants().absent) {
1940 return e;
1941 }
1942 Id* id = e->cast<Id>();
1943 if (id->decl() == nullptr) {
1944 throw EvalError(env, e->loc(), "undefined identifier", id->v());
1945 }
1946 if (id->decl()->ti()->domain() != nullptr) {
1947 if (auto* bl = id->decl()->ti()->domain()->dynamicCast<BoolLit>()) {
1948 return bl;
1949 }
1950 if (id->decl()->ti()->type().isint()) {
1951 if (auto* sl = id->decl()->ti()->domain()->dynamicCast<SetLit>()) {
1952 if ((sl->isv() != nullptr) && sl->isv()->min() == sl->isv()->max()) {
1953 return IntLit::a(sl->isv()->min());
1954 }
1955 }
1956 } else if (id->decl()->ti()->type().isfloat()) {
1957 if (id->decl()->ti()->domain() != nullptr) {
1958 FloatSetVal* fsv = eval_floatset(env, id->decl()->ti()->domain());
1959 if (fsv->min() == fsv->max()) {
1960 return FloatLit::a(fsv->min());
1961 }
1962 }
1963 }
1964 }
1965 if (id->decl()->e() == nullptr) {
1966 return id;
1967 }
1968 return eval_par(env, id->decl()->e());
1969 }
1970 case Expression::E_STRINGLIT:
1971 return e;
1972 default: {
1973 if (e->type().dim() != 0) {
1974 ArrayLit* al = eval_array_lit(env, e);
1975 std::vector<Expression*> args(al->size());
1976 for (unsigned int i = al->size(); (i--) != 0U;) {
1977 args[i] = eval_par(env, (*al)[i]);
1978 }
1979 std::vector<std::pair<int, int>> dims(al->dims());
1980 for (unsigned int i = al->dims(); (i--) != 0U;) {
1981 dims[i].first = al->min(i);
1982 dims[i].second = al->max(i);
1983 }
1984 auto* ret = new ArrayLit(al->loc(), args, dims);
1985 Type t = al->type();
1986 if ((t.bt() == Type::BT_BOT || t.bt() == Type::BT_TOP) && ret->size() > 0) {
1987 t.bt((*ret)[0]->type().bt());
1988 }
1989 ret->type(t);
1990 return ret;
1991 }
1992 if (e->type().isPar()) {
1993 if (e->type().isSet()) {
1994 return EvalSetLit::e(env, e);
1995 }
1996 if (e->type() == Type::parint()) {
1997 return EvalIntLit::e(env, e);
1998 }
1999 if (e->type() == Type::parbool()) {
2000 return EvalBoolLit::e(env, e);
2001 }
2002 if (e->type() == Type::parfloat()) {
2003 return EvalFloatLit::e(env, e);
2004 }
2005 if (e->type() == Type::parstring()) {
2006 return EvalStringLit::e(env, e);
2007 }
2008 }
2009 switch (e->eid()) {
2010 case Expression::E_ITE: {
2011 ITE* ite = e->cast<ITE>();
2012 for (int i = 0; i < ite->size(); i++) {
2013 if (ite->ifExpr(i)->type() == Type::parbool()) {
2014 if (eval_bool(env, ite->ifExpr(i))) {
2015 return eval_par(env, ite->thenExpr(i));
2016 }
2017 } else {
2018 std::vector<Expression*> e_ifthen(ite->size() * 2);
2019 for (int i = 0; i < ite->size(); i++) {
2020 e_ifthen[2 * i] = eval_par(env, ite->ifExpr(i));
2021 e_ifthen[2 * i + 1] = eval_par(env, ite->thenExpr(i));
2022 }
2023 ITE* n_ite = new ITE(ite->loc(), e_ifthen, eval_par(env, ite->elseExpr()));
2024 n_ite->type(ite->type());
2025 return n_ite;
2026 }
2027 }
2028 return eval_par(env, ite->elseExpr());
2029 }
2030 case Expression::E_CALL: {
2031 Call* c = e->cast<Call>();
2032 if (c->decl() != nullptr) {
2033 if (c->decl()->builtins.e != nullptr) {
2034 return eval_par(env, c->decl()->builtins.e(env, c));
2035 }
2036 if (c->decl()->e() == nullptr) {
2037 if (c->id() == "deopt" && Expression::equal(c->arg(0), constants().absent)) {
2038 throw ResultUndefinedError(env, e->loc(), "deopt(<>) is undefined");
2039 }
2040 return c;
2041 }
2042 return eval_call<EvalPar>(env, c);
2043 }
2044 std::vector<Expression*> args(c->argCount());
2045 for (unsigned int i = 0; i < args.size(); i++) {
2046 args[i] = eval_par(env, c->arg(i));
2047 }
2048 Call* nc = new Call(c->loc(), c->id(), args);
2049 nc->type(c->type());
2050 return nc;
2051 }
2052 case Expression::E_BINOP: {
2053 auto* bo = e->cast<BinOp>();
2054 if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) {
2055 return eval_call<EvalPar, BinOp>(env, bo);
2056 }
2057 auto* nbo =
2058 new BinOp(e->loc(), eval_par(env, bo->lhs()), bo->op(), eval_par(env, bo->rhs()));
2059 nbo->type(bo->type());
2060 return nbo;
2061 }
2062 case Expression::E_UNOP: {
2063 UnOp* uo = e->cast<UnOp>();
2064 if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) {
2065 return eval_call<EvalPar, UnOp>(env, uo);
2066 }
2067 UnOp* nuo = new UnOp(e->loc(), uo->op(), eval_par(env, uo->e()));
2068 nuo->type(uo->type());
2069 return nuo;
2070 }
2071 case Expression::E_ARRAYACCESS: {
2072 auto* aa = e->cast<ArrayAccess>();
2073 for (unsigned int i = 0; i < aa->idx().size(); i++) {
2074 if (!aa->idx()[i]->type().isPar()) {
2075 std::vector<Expression*> idx(aa->idx().size());
2076 for (unsigned int j = 0; j < aa->idx().size(); j++) {
2077 idx[j] = eval_par(env, aa->idx()[j]);
2078 }
2079 auto* aa_new = new ArrayAccess(e->loc(), eval_par(env, aa->v()), idx);
2080 aa_new->type(aa->type());
2081 return aa_new;
2082 }
2083 }
2084 return eval_par(env, eval_arrayaccess(env, aa));
2085 }
2086 case Expression::E_LET: {
2087 Let* l = e->cast<Let>();
2088 assert(l->type().isPar());
2089 l->pushbindings();
2090 for (unsigned int i = 0; i < l->let().size(); i++) {
2091 // Evaluate all variable declarations
2092 if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) {
2093 vdi->e(eval_par(env, vdi->e()));
2094 check_par_declaration(env, vdi);
2095 } else {
2096 // This is a constraint item. Since the let is par,
2097 // it can only be a par bool expression. If it evaluates
2098 // to false, it means that the value of this let is undefined.
2099 if (!eval_bool(env, l->let()[i])) {
2100 throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed");
2101 }
2102 }
2103 }
2104 Expression* ret = eval_par(env, l->in());
2105 l->popbindings();
2106 return ret;
2107 }
2108 default:
2109 return e;
2110 }
2111 }
2112 }
2113}
2114
2115class ComputeIntBounds : public EVisitor {
2116public:
2117 typedef std::pair<IntVal, IntVal> Bounds;
2118 std::vector<Bounds> bounds;
2119 bool valid;
2120 EnvI& env;
2121 ComputeIntBounds(EnvI& env0) : valid(true), env(env0) {}
2122 bool enter(Expression* e) {
2123 if (e->type().isAnn()) {
2124 return false;
2125 }
2126 if (e->isa<VarDecl>()) {
2127 return false;
2128 }
2129 if (e->type().dim() > 0) {
2130 return false;
2131 }
2132 if (e->type().isPar()) {
2133 if (e->type().isint()) {
2134 Expression* exp = eval_par(env, e);
2135 if (exp == constants().absent) {
2136 valid = false;
2137 } else {
2138 IntVal v = exp->cast<IntLit>()->v();
2139 bounds.emplace_back(v, v);
2140 }
2141 } else {
2142 valid = false;
2143 }
2144 return false;
2145 }
2146 if (e->type().isint()) {
2147 if (ITE* ite = e->dynamicCast<ITE>()) {
2148 Bounds itebounds(IntVal::infinity(), -IntVal::infinity());
2149 for (int i = 0; i < ite->size(); i++) {
2150 if (ite->ifExpr(i)->type().isPar() &&
2151 static_cast<int>(ite->ifExpr(i)->type().cv()) == Type::CV_NO) {
2152 if (eval_bool(env, ite->ifExpr(i))) {
2153 BottomUpIterator<ComputeIntBounds> cbi(*this);
2154 cbi.run(ite->thenExpr(i));
2155 Bounds& back = bounds.back();
2156 back.first = std::min(itebounds.first, back.first);
2157 back.second = std::max(itebounds.second, back.second);
2158 return false;
2159 }
2160 } else {
2161 BottomUpIterator<ComputeIntBounds> cbi(*this);
2162 cbi.run(ite->thenExpr(i));
2163 Bounds back = bounds.back();
2164 bounds.pop_back();
2165 itebounds.first = std::min(itebounds.first, back.first);
2166 itebounds.second = std::max(itebounds.second, back.second);
2167 }
2168 }
2169 BottomUpIterator<ComputeIntBounds> cbi(*this);
2170 cbi.run(ite->elseExpr());
2171 Bounds& back = bounds.back();
2172 back.first = std::min(itebounds.first, back.first);
2173 back.second = std::max(itebounds.second, back.second);
2174 return false;
2175 }
2176 return true;
2177 }
2178 return false;
2179 }
2180 /// Visit integer literal
2181 void vIntLit(const IntLit& i) { bounds.emplace_back(i.v(), i.v()); }
2182 /// Visit floating point literal
2183 void vFloatLit(const FloatLit& /*f*/) {
2184 valid = false;
2185 bounds.emplace_back(0, 0);
2186 }
2187 /// Visit Boolean literal
2188 void vBoolLit(const BoolLit& /*b*/) {
2189 valid = false;
2190 bounds.emplace_back(0, 0);
2191 }
2192 /// Visit set literal
2193 void vSetLit(const SetLit& /*sl*/) {
2194 valid = false;
2195 bounds.emplace_back(0, 0);
2196 }
2197 /// Visit string literal
2198 void vStringLit(const StringLit& /*sl*/) {
2199 valid = false;
2200 bounds.emplace_back(0, 0);
2201 }
2202 /// Visit identifier
2203 void vId(const Id& id) {
2204 VarDecl* vd = id.decl();
2205 while ((vd->flat() != nullptr) && vd->flat() != vd) {
2206 vd = vd->flat();
2207 }
2208 if (vd->ti()->domain() != nullptr) {
2209 GCLock lock;
2210 IntSetVal* isv = eval_intset(env, vd->ti()->domain());
2211 if (isv->size() == 0) {
2212 valid = false;
2213 bounds.emplace_back(0, 0);
2214 } else {
2215 bounds.emplace_back(isv->min(0), isv->max(isv->size() - 1));
2216 }
2217 } else {
2218 if (vd->e() != nullptr) {
2219 BottomUpIterator<ComputeIntBounds> cbi(*this);
2220 cbi.run(vd->e());
2221 } else {
2222 bounds.emplace_back(-IntVal::infinity(), IntVal::infinity());
2223 }
2224 }
2225 }
2226 /// Visit anonymous variable
2227 void vAnonVar(const AnonVar& /*v*/) {
2228 valid = false;
2229 bounds.emplace_back(0, 0);
2230 }
2231 /// Visit array literal
2232 void vArrayLit(const ArrayLit& /*al*/) {}
2233 /// Visit array access
2234 void vArrayAccess(ArrayAccess& aa) {
2235 bool parAccess = true;
2236 for (unsigned int i = aa.idx().size(); (i--) != 0U;) {
2237 bounds.pop_back();
2238 if (!aa.idx()[i]->type().isPar()) {
2239 parAccess = false;
2240 }
2241 }
2242 if (Id* id = aa.v()->dynamicCast<Id>()) {
2243 while ((id->decl()->e() != nullptr) && id->decl()->e()->isa<Id>()) {
2244 id = id->decl()->e()->cast<Id>();
2245 }
2246 if (parAccess && (id->decl()->e() != nullptr)) {
2247 bool success;
2248 Expression* e = eval_arrayaccess(env, &aa, success);
2249 if (success) {
2250 BottomUpIterator<ComputeIntBounds> cbi(*this);
2251 cbi.run(e);
2252 return;
2253 }
2254 }
2255 if (id->decl()->ti()->domain() != nullptr) {
2256 GCLock lock;
2257 IntSetVal* isv = eval_intset(env, id->decl()->ti()->domain());
2258 if (isv->size() > 0) {
2259 bounds.emplace_back(isv->min(0), isv->max(isv->size() - 1));
2260 return;
2261 }
2262 }
2263 }
2264 valid = false;
2265 bounds.emplace_back(0, 0);
2266 }
2267 /// Visit array comprehension
2268 void vComprehension(const Comprehension& c) {
2269 valid = false;
2270 bounds.emplace_back(0, 0);
2271 }
2272 /// Visit if-then-else
2273 void vITE(const ITE& /*ite*/) {
2274 valid = false;
2275 bounds.emplace_back(0, 0);
2276 }
2277 /// Visit binary operator
2278 void vBinOp(const BinOp& bo) {
2279 Bounds b1 = bounds.back();
2280 bounds.pop_back();
2281 Bounds b0 = bounds.back();
2282 bounds.pop_back();
2283 if (!b1.first.isFinite() || !b1.second.isFinite() || !b0.first.isFinite() ||
2284 !b0.second.isFinite()) {
2285 valid = false;
2286 bounds.emplace_back(0, 0);
2287 } else {
2288 switch (bo.op()) {
2289 case BOT_PLUS:
2290 bounds.emplace_back(b0.first + b1.first, b0.second + b1.second);
2291 break;
2292 case BOT_MINUS:
2293 bounds.emplace_back(b0.first - b1.second, b0.second - b1.first);
2294 break;
2295 case BOT_MULT: {
2296 IntVal x0 = b0.first * b1.first;
2297 IntVal x1 = b0.first * b1.second;
2298 IntVal x2 = b0.second * b1.first;
2299 IntVal x3 = b0.second * b1.second;
2300 IntVal m = std::min(x0, std::min(x1, std::min(x2, x3)));
2301 IntVal n = std::max(x0, std::max(x1, std::max(x2, x3)));
2302 bounds.emplace_back(m, n);
2303 } break;
2304 case BOT_IDIV: {
2305 IntVal b0f = b0.first == 0 ? 1 : b0.first;
2306 IntVal b0s = b0.second == 0 ? -1 : b0.second;
2307 IntVal b1f = b1.first == 0 ? 1 : b1.first;
2308 IntVal b1s = b1.second == 0 ? -1 : b1.second;
2309 IntVal x0 = b0f / b1f;
2310 IntVal x1 = b0f / b1s;
2311 IntVal x2 = b0s / b1f;
2312 IntVal x3 = b0s / b1s;
2313 IntVal m = std::min(x0, std::min(x1, std::min(x2, x3)));
2314 IntVal n = std::max(x0, std::max(x1, std::max(x2, x3)));
2315 bounds.emplace_back(m, n);
2316 } break;
2317 case BOT_MOD: {
2318 IntVal b0f = b0.first == 0 ? 1 : b0.first;
2319 IntVal b0s = b0.second == 0 ? -1 : b0.second;
2320 IntVal b1f = b1.first == 0 ? 1 : b1.first;
2321 IntVal b1s = b1.second == 0 ? -1 : b1.second;
2322 IntVal x0 = b0f % b1f;
2323 IntVal x1 = b0f % b1s;
2324 IntVal x2 = b0s % b1f;
2325 IntVal x3 = b0s % b1s;
2326 IntVal m = std::min(x0, std::min(x1, std::min(x2, x3)));
2327 IntVal n = std::max(x0, std::max(x1, std::max(x2, x3)));
2328 bounds.emplace_back(m, n);
2329 } break;
2330 case BOT_POW: {
2331 IntVal exp_min = std::min(0, b1.first);
2332 IntVal exp_max = std::min(0, b1.second);
2333
2334 IntVal x0 = b0.first.pow(exp_min);
2335 IntVal x1 = b0.first.pow(exp_max);
2336 IntVal x2 = b0.second.pow(exp_min);
2337 IntVal x3 = b0.second.pow(exp_max);
2338 IntVal m = std::min(x0, std::min(x1, std::min(x2, x3)));
2339 IntVal n = std::max(x0, std::max(x1, std::max(x2, x3)));
2340 bounds.emplace_back(m, n);
2341 } break;
2342 case BOT_DIV:
2343 case BOT_LE:
2344 case BOT_LQ:
2345 case BOT_GR:
2346 case BOT_GQ:
2347 case BOT_EQ:
2348 case BOT_NQ:
2349 case BOT_IN:
2350 case BOT_SUBSET:
2351 case BOT_SUPERSET:
2352 case BOT_UNION:
2353 case BOT_DIFF:
2354 case BOT_SYMDIFF:
2355 case BOT_INTERSECT:
2356 case BOT_PLUSPLUS:
2357 case BOT_EQUIV:
2358 case BOT_IMPL:
2359 case BOT_RIMPL:
2360 case BOT_OR:
2361 case BOT_AND:
2362 case BOT_XOR:
2363 case BOT_DOTDOT:
2364 valid = false;
2365 bounds.emplace_back(0, 0);
2366 }
2367 }
2368 }
2369 /// Visit unary operator
2370 void vUnOp(const UnOp& uo) {
2371 switch (uo.op()) {
2372 case UOT_PLUS:
2373 break;
2374 case UOT_MINUS:
2375 bounds.back().first = -bounds.back().first;
2376 bounds.back().second = -bounds.back().second;
2377 std::swap(bounds.back().first, bounds.back().second);
2378 break;
2379 case UOT_NOT:
2380 valid = false;
2381 }
2382 }
2383 /// Visit call
2384 void vCall(Call& c) {
2385 if (c.id() == constants().ids.lin_exp || c.id() == constants().ids.sum) {
2386 bool le = c.id() == constants().ids.lin_exp;
2387 ArrayLit* coeff = le ? eval_array_lit(env, c.arg(0)) : nullptr;
2388 if (c.arg(le ? 1 : 0)->type().isOpt()) {
2389 valid = false;
2390 bounds.emplace_back(0, 0);
2391 return;
2392 }
2393 ArrayLit* al = eval_array_lit(env, c.arg(le ? 1 : 0));
2394 if (le) {
2395 bounds.pop_back(); // remove constant (third arg) from stack
2396 }
2397
2398 IntVal d = le ? c.arg(2)->cast<IntLit>()->v() : 0;
2399 int stacktop = static_cast<int>(bounds.size());
2400 for (unsigned int i = al->size(); (i--) != 0U;) {
2401 BottomUpIterator<ComputeIntBounds> cbi(*this);
2402 cbi.run((*al)[i]);
2403 if (!valid) {
2404 for (unsigned int j = al->size() - 1; j > i; j--) {
2405 bounds.pop_back();
2406 }
2407 return;
2408 }
2409 }
2410 assert(stacktop + al->size() == bounds.size());
2411 IntVal lb = d;
2412 IntVal ub = d;
2413 for (unsigned int i = 0; i < al->size(); i++) {
2414 Bounds b = bounds.back();
2415 bounds.pop_back();
2416 IntVal cv = le ? eval_int(env, (*coeff)[i]) : 1;
2417 if (cv > 0) {
2418 if (b.first.isFinite()) {
2419 if (lb.isFinite()) {
2420 lb += cv * b.first;
2421 }
2422 } else {
2423 lb = b.first;
2424 }
2425 if (b.second.isFinite()) {
2426 if (ub.isFinite()) {
2427 ub += cv * b.second;
2428 }
2429 } else {
2430 ub = b.second;
2431 }
2432 } else {
2433 if (b.second.isFinite()) {
2434 if (lb.isFinite()) {
2435 lb += cv * b.second;
2436 }
2437 } else {
2438 lb = -b.second;
2439 }
2440 if (b.first.isFinite()) {
2441 if (ub.isFinite()) {
2442 ub += cv * b.first;
2443 }
2444 } else {
2445 ub = -b.first;
2446 }
2447 }
2448 }
2449 bounds.emplace_back(lb, ub);
2450 } else if (c.id() == "card") {
2451 if (IntSetVal* isv = compute_intset_bounds(env, c.arg(0))) {
2452 IntSetRanges isr(isv);
2453 bounds.emplace_back(0, Ranges::cardinality(isr));
2454 } else {
2455 valid = false;
2456 bounds.emplace_back(0, 0);
2457 }
2458 } else if (c.id() == "int_times") {
2459 Bounds b1 = bounds.back();
2460 bounds.pop_back();
2461 Bounds b0 = bounds.back();
2462 bounds.pop_back();
2463 if (!b1.first.isFinite() || !b1.second.isFinite() || !b0.first.isFinite() ||
2464 !b0.second.isFinite()) {
2465 valid = false;
2466 bounds.emplace_back(0, 0);
2467 } else {
2468 IntVal x0 = b0.first * b1.first;
2469 IntVal x1 = b0.first * b1.second;
2470 IntVal x2 = b0.second * b1.first;
2471 IntVal x3 = b0.second * b1.second;
2472 IntVal m = std::min(x0, std::min(x1, std::min(x2, x3)));
2473 IntVal n = std::max(x0, std::max(x1, std::max(x2, x3)));
2474 bounds.emplace_back(m, n);
2475 }
2476 } else if (c.id() == constants().ids.bool2int) {
2477 bounds.emplace_back(0, 1);
2478 } else if (c.id() == "abs") {
2479 Bounds b0 = bounds.back();
2480 if (b0.first < 0) {
2481 bounds.pop_back();
2482 if (b0.second < 0) {
2483 bounds.emplace_back(-b0.second, -b0.first);
2484 } else {
2485 bounds.emplace_back(0, std::max(-b0.first, b0.second));
2486 }
2487 }
2488 } else if (c.id() == "int_uniform") {
2489 Bounds b0 = bounds.back();
2490 bounds.pop_back();
2491 Bounds b1 = bounds.back();
2492 bounds.pop_back();
2493 assert(b0.first == b0.second && b1.first == b1.second);
2494 bounds.emplace_back(b0.first, b1.first);
2495 } else if (c.id() == "int_sol" || c.id() == "int_lastval") {
2496 // Take bounds of the argument
2497 } else if ((c.decl() != nullptr) && (c.decl()->ti()->domain() != nullptr) &&
2498 !c.decl()->ti()->domain()->isa<TIId>()) {
2499 for (int i = 0; i < c.argCount(); i++) {
2500 if (c.arg(i)->type().isint()) {
2501 assert(!bounds.empty());
2502 bounds.pop_back();
2503 }
2504 }
2505 IntSetVal* isv = eval_intset(env, c.decl()->ti()->domain());
2506 bounds.emplace_back(isv->min(), isv->max());
2507 } else {
2508 valid = false;
2509 bounds.emplace_back(0, 0);
2510 }
2511 }
2512 /// Visit let
2513 void vLet(const Let& l) {
2514 valid = false;
2515 bounds.emplace_back(0, 0);
2516 }
2517 /// Visit variable declaration
2518 void vVarDecl(const VarDecl& vd) {
2519 valid = false;
2520 bounds.emplace_back(0, 0);
2521 }
2522 /// Visit annotation
2523 void vAnnotation(const Annotation& e) {
2524 valid = false;
2525 bounds.emplace_back(0, 0);
2526 }
2527 /// Visit type inst
2528 void vTypeInst(const TypeInst& e) {
2529 valid = false;
2530 bounds.emplace_back(0, 0);
2531 }
2532 /// Visit TIId
2533 void vTIId(const TIId& e) {
2534 valid = false;
2535 bounds.emplace_back(0, 0);
2536 }
2537};
2538
2539IntBounds compute_int_bounds(EnvI& env, Expression* e) {
2540 try {
2541 ComputeIntBounds cb(env);
2542 BottomUpIterator<ComputeIntBounds> cbi(cb);
2543 cbi.run(e);
2544 if (cb.valid) {
2545 assert(cb.bounds.size() == 1);
2546 return IntBounds(cb.bounds.back().first, cb.bounds.back().second, true);
2547 }
2548 return IntBounds(0, 0, false);
2549
2550 } catch (ResultUndefinedError&) {
2551 return IntBounds(0, 0, false);
2552 }
2553}
2554
2555class ComputeFloatBounds : public EVisitor {
2556protected:
2557 typedef std::pair<FloatVal, FloatVal> FBounds;
2558
2559public:
2560 std::vector<FBounds> bounds;
2561 bool valid;
2562 EnvI& env;
2563 ComputeFloatBounds(EnvI& env0) : valid(true), env(env0) {}
2564 bool enter(Expression* e) {
2565 if (e->type().isAnn()) {
2566 return false;
2567 }
2568 if (e->isa<VarDecl>()) {
2569 return false;
2570 }
2571 if (e->type().dim() > 0) {
2572 return false;
2573 }
2574 if (e->type().isPar()) {
2575 if (e->type().isfloat()) {
2576 Expression* exp = eval_par(env, e);
2577 if (exp == constants().absent) {
2578 valid = false;
2579 } else {
2580 FloatVal v = exp->cast<FloatLit>()->v();
2581 bounds.emplace_back(v, v);
2582 }
2583 }
2584 return false;
2585 }
2586 if (e->type().isfloat()) {
2587 if (ITE* ite = e->dynamicCast<ITE>()) {
2588 FBounds itebounds(FloatVal::infinity(), -FloatVal::infinity());
2589 for (int i = 0; i < ite->size(); i++) {
2590 if (ite->ifExpr(i)->type().isPar() &&
2591 static_cast<int>(ite->ifExpr(i)->type().cv()) == Type::CV_NO) {
2592 if (eval_bool(env, ite->ifExpr(i))) {
2593 BottomUpIterator<ComputeFloatBounds> cbi(*this);
2594 cbi.run(ite->thenExpr(i));
2595 FBounds& back = bounds.back();
2596 back.first = std::min(itebounds.first, back.first);
2597 back.second = std::max(itebounds.second, back.second);
2598 return false;
2599 }
2600 } else {
2601 BottomUpIterator<ComputeFloatBounds> cbi(*this);
2602 cbi.run(ite->thenExpr(i));
2603 FBounds back = bounds.back();
2604 bounds.pop_back();
2605 itebounds.first = std::min(itebounds.first, back.first);
2606 itebounds.second = std::max(itebounds.second, back.second);
2607 }
2608 }
2609 BottomUpIterator<ComputeFloatBounds> cbi(*this);
2610 cbi.run(ite->elseExpr());
2611 FBounds& back = bounds.back();
2612 back.first = std::min(itebounds.first, back.first);
2613 back.second = std::max(itebounds.second, back.second);
2614 return false;
2615 }
2616 return true;
2617 }
2618 return false;
2619 }
2620 /// Visit integer literal
2621 void vIntLit(const IntLit& i) {
2622 valid = false;
2623 bounds.emplace_back(0.0, 0.0);
2624 }
2625 /// Visit floating point literal
2626 void vFloatLit(const FloatLit& f) { bounds.emplace_back(f.v(), f.v()); }
2627 /// Visit Boolean literal
2628 void vBoolLit(const BoolLit& /*b*/) {
2629 valid = false;
2630 bounds.emplace_back(0.0, 0.0);
2631 }
2632 /// Visit set literal
2633 void vSetLit(const SetLit& /*sl*/) {
2634 valid = false;
2635 bounds.emplace_back(0.0, 0.0);
2636 }
2637 /// Visit string literal
2638 void vStringLit(const StringLit& /*sl*/) {
2639 valid = false;
2640 bounds.emplace_back(0.0, 0.0);
2641 }
2642 /// Visit identifier
2643 void vId(const Id& id) {
2644 VarDecl* vd = id.decl();
2645 while ((vd->flat() != nullptr) && vd->flat() != vd) {
2646 vd = vd->flat();
2647 }
2648 if (vd->ti()->domain() != nullptr) {
2649 GCLock lock;
2650 FloatSetVal* fsv = eval_floatset(env, vd->ti()->domain());
2651 if (fsv->size() == 0) {
2652 valid = false;
2653 bounds.emplace_back(0, 0);
2654 } else {
2655 bounds.emplace_back(fsv->min(0), fsv->max(fsv->size() - 1));
2656 }
2657 } else {
2658 if (vd->e() != nullptr) {
2659 BottomUpIterator<ComputeFloatBounds> cbi(*this);
2660 cbi.run(vd->e());
2661 } else {
2662 bounds.emplace_back(-FloatVal::infinity(), FloatVal::infinity());
2663 }
2664 }
2665 }
2666 /// Visit anonymous variable
2667 void vAnonVar(const AnonVar& v) {
2668 valid = false;
2669 bounds.emplace_back(0.0, 0.0);
2670 }
2671 /// Visit array literal
2672 void vArrayLit(const ArrayLit& al) {}
2673 /// Visit array access
2674 void vArrayAccess(ArrayAccess& aa) {
2675 bool parAccess = true;
2676 for (unsigned int i = aa.idx().size(); (i--) != 0U;) {
2677 if (!aa.idx()[i]->type().isPar()) {
2678 parAccess = false;
2679 }
2680 }
2681 if (Id* id = aa.v()->dynamicCast<Id>()) {
2682 while ((id->decl()->e() != nullptr) && id->decl()->e()->isa<Id>()) {
2683 id = id->decl()->e()->cast<Id>();
2684 }
2685 if (parAccess && (id->decl()->e() != nullptr)) {
2686 bool success;
2687 Expression* e = eval_arrayaccess(env, &aa, success);
2688 if (success) {
2689 BottomUpIterator<ComputeFloatBounds> cbi(*this);
2690 cbi.run(e);
2691 return;
2692 }
2693 }
2694 if (id->decl()->ti()->domain() != nullptr) {
2695 FloatSetVal* fsv = eval_floatset(env, id->decl()->ti()->domain());
2696 FBounds b(fsv->min(), fsv->max());
2697 bounds.push_back(b);
2698 return;
2699 }
2700 }
2701 valid = false;
2702 bounds.emplace_back(0.0, 0.0);
2703 }
2704 /// Visit array comprehension
2705 void vComprehension(const Comprehension& c) {
2706 valid = false;
2707 bounds.emplace_back(0.0, 0.0);
2708 }
2709 /// Visit if-then-else
2710 void vITE(const ITE& ite) {
2711 valid = false;
2712 bounds.emplace_back(0.0, 0.0);
2713 }
2714 /// Visit binary operator
2715 void vBinOp(const BinOp& bo) {
2716 FBounds b1 = bounds.back();
2717 bounds.pop_back();
2718 FBounds b0 = bounds.back();
2719 bounds.pop_back();
2720 if (!b1.first.isFinite() || !b1.second.isFinite() || !b0.first.isFinite() ||
2721 !b0.second.isFinite()) {
2722 valid = false;
2723 bounds.emplace_back(0.0, 0.0);
2724 } else {
2725 switch (bo.op()) {
2726 case BOT_PLUS:
2727 bounds.emplace_back(b0.first + b1.first, b0.second + b1.second);
2728 break;
2729 case BOT_MINUS:
2730 bounds.emplace_back(b0.first - b1.second, b0.second - b1.first);
2731 break;
2732 case BOT_MULT: {
2733 FloatVal x0 = b0.first * b1.first;
2734 FloatVal x1 = b0.first * b1.second;
2735 FloatVal x2 = b0.second * b1.first;
2736 FloatVal x3 = b0.second * b1.second;
2737 FloatVal m = std::min(x0, std::min(x1, std::min(x2, x3)));
2738 FloatVal n = std::max(x0, std::max(x1, std::max(x2, x3)));
2739 bounds.emplace_back(m, n);
2740 } break;
2741 case BOT_POW: {
2742 FloatVal x0 = std::pow(b0.first.toDouble(), b1.first.toDouble());
2743 FloatVal x1 = std::pow(b0.first.toDouble(), b1.second.toDouble());
2744 FloatVal x2 = std::pow(b0.second.toDouble(), b1.first.toDouble());
2745 FloatVal x3 = std::pow(b0.second.toDouble(), b1.second.toDouble());
2746 FloatVal m = std::min(x0, std::min(x1, std::min(x2, x3)));
2747 FloatVal n = std::max(x0, std::max(x1, std::max(x2, x3)));
2748 bounds.emplace_back(m, n);
2749 } break;
2750 case BOT_DIV:
2751 case BOT_IDIV:
2752 case BOT_MOD:
2753 case BOT_LE:
2754 case BOT_LQ:
2755 case BOT_GR:
2756 case BOT_GQ:
2757 case BOT_EQ:
2758 case BOT_NQ:
2759 case BOT_IN:
2760 case BOT_SUBSET:
2761 case BOT_SUPERSET:
2762 case BOT_UNION:
2763 case BOT_DIFF:
2764 case BOT_SYMDIFF:
2765 case BOT_INTERSECT:
2766 case BOT_PLUSPLUS:
2767 case BOT_EQUIV:
2768 case BOT_IMPL:
2769 case BOT_RIMPL:
2770 case BOT_OR:
2771 case BOT_AND:
2772 case BOT_XOR:
2773 case BOT_DOTDOT:
2774 valid = false;
2775 bounds.emplace_back(0.0, 0.0);
2776 }
2777 }
2778 }
2779 /// Visit unary operator
2780 void vUnOp(const UnOp& uo) {
2781 switch (uo.op()) {
2782 case UOT_PLUS:
2783 break;
2784 case UOT_MINUS:
2785 bounds.back().first = -bounds.back().first;
2786 bounds.back().second = -bounds.back().second;
2787 break;
2788 case UOT_NOT:
2789 valid = false;
2790 bounds.emplace_back(0.0, 0.0);
2791 }
2792 }
2793 /// Visit call
2794 void vCall(Call& c) {
2795 if (c.id() == constants().ids.lin_exp || c.id() == constants().ids.sum) {
2796 bool le = c.id() == constants().ids.lin_exp;
2797 ArrayLit* coeff = le ? eval_array_lit(env, c.arg(0)) : nullptr;
2798 if (le) {
2799 bounds.pop_back(); // remove constant (third arg) from stack
2800 }
2801 if (c.arg(le ? 1 : 0)->type().isOpt()) {
2802 valid = false;
2803 bounds.emplace_back(0.0, 0.0);
2804 return;
2805 }
2806 ArrayLit* al = eval_array_lit(env, c.arg(le ? 1 : 0));
2807 FloatVal d = le ? c.arg(2)->cast<FloatLit>()->v() : 0.0;
2808 int stacktop = static_cast<int>(bounds.size());
2809 for (unsigned int i = al->size(); (i--) != 0U;) {
2810 BottomUpIterator<ComputeFloatBounds> cbi(*this);
2811 cbi.run((*al)[i]);
2812 if (!valid) {
2813 return;
2814 }
2815 }
2816 assert(stacktop + al->size() == bounds.size());
2817 FloatVal lb = d;
2818 FloatVal ub = d;
2819 for (unsigned int i = 0; i < (*al).size(); i++) {
2820 FBounds b = bounds.back();
2821 bounds.pop_back();
2822 FloatVal cv = le ? eval_float(env, (*coeff)[i]) : 1.0;
2823
2824 if (cv > 0) {
2825 if (b.first.isFinite()) {
2826 if (lb.isFinite()) {
2827 lb += cv * b.first;
2828 }
2829 } else {
2830 lb = b.first;
2831 }
2832 if (b.second.isFinite()) {
2833 if (ub.isFinite()) {
2834 ub += cv * b.second;
2835 }
2836 } else {
2837 ub = b.second;
2838 }
2839 } else {
2840 if (b.second.isFinite()) {
2841 if (lb.isFinite()) {
2842 lb += cv * b.second;
2843 }
2844 } else {
2845 lb = -b.second;
2846 }
2847 if (b.first.isFinite()) {
2848 if (ub.isFinite()) {
2849 ub += cv * b.first;
2850 }
2851 } else {
2852 ub = -b.first;
2853 }
2854 }
2855 }
2856 bounds.emplace_back(lb, ub);
2857 } else if (c.id() == "float_times") {
2858 BottomUpIterator<ComputeFloatBounds> cbi(*this);
2859 cbi.run(c.arg(0));
2860 cbi.run(c.arg(1));
2861 FBounds b1 = bounds.back();
2862 bounds.pop_back();
2863 FBounds b0 = bounds.back();
2864 bounds.pop_back();
2865 if (!b1.first.isFinite() || !b1.second.isFinite() || !b0.first.isFinite() ||
2866 !b0.second.isFinite()) {
2867 valid = false;
2868 bounds.emplace_back(0, 0);
2869 } else {
2870 FloatVal x0 = b0.first * b1.first;
2871 FloatVal x1 = b0.first * b1.second;
2872 FloatVal x2 = b0.second * b1.first;
2873 FloatVal x3 = b0.second * b1.second;
2874 FloatVal m = std::min(x0, std::min(x1, std::min(x2, x3)));
2875 FloatVal n = std::max(x0, std::max(x1, std::max(x2, x3)));
2876 bounds.emplace_back(m, n);
2877 }
2878 } else if (c.id() == "int2float") {
2879 ComputeIntBounds ib(env);
2880 BottomUpIterator<ComputeIntBounds> cbi(ib);
2881 cbi.run(c.arg(0));
2882 if (!ib.valid) {
2883 valid = false;
2884 }
2885 ComputeIntBounds::Bounds result = ib.bounds.back();
2886 if (!result.first.isFinite() || !result.second.isFinite()) {
2887 valid = false;
2888 bounds.emplace_back(0.0, 0.0);
2889 } else {
2890 bounds.emplace_back(static_cast<double>(result.first.toInt()),
2891 static_cast<double>(result.second.toInt()));
2892 }
2893 } else if (c.id() == "abs") {
2894 BottomUpIterator<ComputeFloatBounds> cbi(*this);
2895 cbi.run(c.arg(0));
2896 FBounds b0 = bounds.back();
2897 if (b0.first < 0) {
2898 bounds.pop_back();
2899 if (b0.second < 0) {
2900 bounds.emplace_back(-b0.second, -b0.first);
2901 } else {
2902 bounds.emplace_back(0.0, std::max(-b0.first, b0.second));
2903 }
2904 }
2905 } else if (c.id() == "float_sol" || c.id() == "float_lastval") {
2906 // Take bounds of the argument
2907 } else if ((c.decl() != nullptr) && (c.decl()->ti()->domain() != nullptr) &&
2908 !c.decl()->ti()->domain()->isa<TIId>()) {
2909 for (int i = 0; i < c.argCount(); i++) {
2910 if (c.arg(i)->type().isfloat()) {
2911 assert(!bounds.empty());
2912 bounds.pop_back();
2913 }
2914 }
2915 FloatSetVal* fsv = eval_floatset(env, c.decl()->ti()->domain());
2916 bounds.emplace_back(fsv->min(), fsv->max());
2917 } else {
2918 valid = false;
2919 bounds.emplace_back(0.0, 0.0);
2920 }
2921 }
2922 /// Visit let
2923 void vLet(const Let& l) {
2924 valid = false;
2925 bounds.emplace_back(0.0, 0.0);
2926 }
2927 /// Visit variable declaration
2928 void vVarDecl(const VarDecl& vd) {
2929 valid = false;
2930 bounds.emplace_back(0.0, 0.0);
2931 }
2932 /// Visit annotation
2933 void vAnnotation(const Annotation& e) {
2934 valid = false;
2935 bounds.emplace_back(0.0, 0.0);
2936 }
2937 /// Visit type inst
2938 void vTypeInst(const TypeInst& e) {
2939 valid = false;
2940 bounds.emplace_back(0.0, 0.0);
2941 }
2942 /// Visit TIId
2943 void vTIId(const TIId& e) {
2944 valid = false;
2945 bounds.emplace_back(0.0, 0.0);
2946 }
2947};
2948
2949FloatBounds compute_float_bounds(EnvI& env, Expression* e) {
2950 try {
2951 ComputeFloatBounds cb(env);
2952 BottomUpIterator<ComputeFloatBounds> cbi(cb);
2953 cbi.run(e);
2954 if (cb.valid) {
2955 assert(!cb.bounds.empty());
2956 return FloatBounds(cb.bounds.back().first, cb.bounds.back().second, true);
2957 }
2958 return FloatBounds(0.0, 0.0, false);
2959
2960 } catch (ResultUndefinedError&) {
2961 return FloatBounds(0.0, 0.0, false);
2962 }
2963}
2964
2965class ComputeIntSetBounds : public EVisitor {
2966public:
2967 std::vector<IntSetVal*> bounds;
2968 bool valid;
2969 EnvI& env;
2970 ComputeIntSetBounds(EnvI& env0) : valid(true), env(env0) {}
2971 bool enter(Expression* e) {
2972 if (e->type().isAnn()) {
2973 return false;
2974 }
2975 if (e->isa<VarDecl>()) {
2976 return false;
2977 }
2978 if (e->type().dim() > 0) {
2979 return false;
2980 }
2981 if (!e->type().isIntSet()) {
2982 return false;
2983 }
2984 if (e->type().isPar()) {
2985 bounds.push_back(eval_intset(env, e));
2986 return false;
2987 }
2988 return true;
2989 }
2990 /// Visit set literal
2991 void vSetLit(const SetLit& sl) {
2992 assert(sl.type().isvar());
2993 assert(sl.isv() == nullptr);
2994
2995 IntSetVal* isv = IntSetVal::a();
2996 for (unsigned int i = 0; i < sl.v().size(); i++) {
2997 IntSetRanges i0(isv);
2998 IntBounds ib = compute_int_bounds(env, sl.v()[i]);
2999 if (!ib.valid || !ib.l.isFinite() || !ib.u.isFinite()) {
3000 valid = false;
3001 bounds.push_back(nullptr);
3002 return;
3003 }
3004 Ranges::Const<IntVal> cr(ib.l, ib.u);
3005 Ranges::Union<IntVal, IntSetRanges, Ranges::Const<IntVal>> u(i0, cr);
3006 isv = IntSetVal::ai(u);
3007 }
3008 bounds.push_back(isv);
3009 }
3010 /// Visit identifier
3011 void vId(const Id& id) {
3012 if ((id.decl()->ti()->domain() != nullptr) && !id.decl()->ti()->domain()->isa<TIId>()) {
3013 bounds.push_back(eval_intset(env, id.decl()->ti()->domain()));
3014 } else {
3015 if (id.decl()->e() != nullptr) {
3016 BottomUpIterator<ComputeIntSetBounds> cbi(*this);
3017 cbi.run(id.decl()->e());
3018 } else {
3019 valid = false;
3020 bounds.push_back(nullptr);
3021 }
3022 }
3023 }
3024 /// Visit anonymous variable
3025 void vAnonVar(const AnonVar& v) {
3026 valid = false;
3027 bounds.push_back(nullptr);
3028 }
3029 /// Visit array access
3030 void vArrayAccess(ArrayAccess& aa) {
3031 bool parAccess = true;
3032 for (unsigned int i = aa.idx().size(); (i--) != 0U;) {
3033 if (!aa.idx()[i]->type().isPar()) {
3034 parAccess = false;
3035 break;
3036 }
3037 }
3038 if (Id* id = aa.v()->dynamicCast<Id>()) {
3039 while ((id->decl()->e() != nullptr) && id->decl()->e()->isa<Id>()) {
3040 id = id->decl()->e()->cast<Id>();
3041 }
3042 if (parAccess && (id->decl()->e() != nullptr)) {
3043 bool success;
3044 Expression* e = eval_arrayaccess(env, &aa, success);
3045 if (success) {
3046 BottomUpIterator<ComputeIntSetBounds> cbi(*this);
3047 cbi.run(e);
3048 return;
3049 }
3050 }
3051 if (id->decl()->ti()->domain() != nullptr) {
3052 bounds.push_back(eval_intset(env, id->decl()->ti()->domain()));
3053 return;
3054 }
3055 }
3056 valid = false;
3057 bounds.push_back(nullptr);
3058 }
3059 /// Visit array comprehension
3060 void vComprehension(const Comprehension& c) {
3061 valid = false;
3062 bounds.push_back(nullptr);
3063 }
3064 /// Visit if-then-else
3065 void vITE(const ITE& ite) {
3066 valid = false;
3067 bounds.push_back(nullptr);
3068 }
3069 /// Visit binary operator
3070 void vBinOp(const BinOp& bo) {
3071 if (bo.op() == BOT_DOTDOT) {
3072 IntBounds lb = compute_int_bounds(env, bo.lhs());
3073 IntBounds ub = compute_int_bounds(env, bo.rhs());
3074 valid = valid && lb.valid && ub.valid;
3075 bounds.push_back(IntSetVal::a(lb.l, ub.u));
3076 } else {
3077 IntSetVal* b1 = bounds.back();
3078 bounds.pop_back();
3079 IntSetVal* b0 = bounds.back();
3080 bounds.pop_back();
3081 switch (bo.op()) {
3082 case BOT_INTERSECT:
3083 case BOT_UNION: {
3084 IntSetRanges b0r(b0);
3085 IntSetRanges b1r(b1);
3086 Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(b0r, b1r);
3087 bounds.push_back(IntSetVal::ai(u));
3088 } break;
3089 case BOT_DIFF: {
3090 bounds.push_back(b0);
3091 } break;
3092 case BOT_SYMDIFF:
3093 valid = false;
3094 bounds.push_back(nullptr);
3095 break;
3096 case BOT_PLUS:
3097 case BOT_MINUS:
3098 case BOT_MULT:
3099 case BOT_POW:
3100 case BOT_DIV:
3101 case BOT_IDIV:
3102 case BOT_MOD:
3103 case BOT_LE:
3104 case BOT_LQ:
3105 case BOT_GR:
3106 case BOT_GQ:
3107 case BOT_EQ:
3108 case BOT_NQ:
3109 case BOT_IN:
3110 case BOT_SUBSET:
3111 case BOT_SUPERSET:
3112 case BOT_PLUSPLUS:
3113 case BOT_EQUIV:
3114 case BOT_IMPL:
3115 case BOT_RIMPL:
3116 case BOT_OR:
3117 case BOT_AND:
3118 case BOT_XOR:
3119 case BOT_DOTDOT:
3120 valid = false;
3121 bounds.push_back(nullptr);
3122 }
3123 }
3124 }
3125 /// Visit unary operator
3126 void vUnOp(const UnOp& uo) {
3127 valid = false;
3128 bounds.push_back(nullptr);
3129 }
3130 /// Visit call
3131 void vCall(Call& c) {
3132 if (valid && (c.id() == "set_intersect" || c.id() == "set_union")) {
3133 IntSetVal* b0 = bounds.back();
3134 bounds.pop_back();
3135 IntSetVal* b1 = bounds.back();
3136 bounds.pop_back();
3137 IntSetRanges b0r(b0);
3138 IntSetRanges b1r(b1);
3139 Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(b0r, b1r);
3140 bounds.push_back(IntSetVal::ai(u));
3141 } else if (valid && c.id() == "set_diff") {
3142 IntSetVal* b0 = bounds.back();
3143 bounds.pop_back();
3144 bounds.pop_back(); // don't need bounds of right hand side
3145 bounds.push_back(b0);
3146 } else if ((c.decl() != nullptr) && (c.decl()->ti()->domain() != nullptr) &&
3147 !c.decl()->ti()->domain()->isa<TIId>()) {
3148 for (int i = 0; i < c.argCount(); i++) {
3149 if (c.arg(i)->type().isIntSet()) {
3150 assert(!bounds.empty());
3151 bounds.pop_back();
3152 }
3153 }
3154 IntSetVal* fsv = eval_intset(env, c.decl()->ti()->domain());
3155 bounds.push_back(fsv);
3156 } else {
3157 valid = false;
3158 bounds.push_back(nullptr);
3159 }
3160 }
3161 /// Visit let
3162 void vLet(const Let& l) {
3163 valid = false;
3164 bounds.push_back(nullptr);
3165 }
3166 /// Visit variable declaration
3167 void vVarDecl(const VarDecl& vd) {
3168 valid = false;
3169 bounds.push_back(nullptr);
3170 }
3171 /// Visit annotation
3172 void vAnnotation(const Annotation& e) {
3173 valid = false;
3174 bounds.push_back(nullptr);
3175 }
3176 /// Visit type inst
3177 void vTypeInst(const TypeInst& e) {
3178 valid = false;
3179 bounds.push_back(nullptr);
3180 }
3181 /// Visit TIId
3182 void vTIId(const TIId& e) {
3183 valid = false;
3184 bounds.push_back(nullptr);
3185 }
3186};
3187
3188IntSetVal* compute_intset_bounds(EnvI& env, Expression* e) {
3189 try {
3190 ComputeIntSetBounds cb(env);
3191 BottomUpIterator<ComputeIntSetBounds> cbi(cb);
3192 cbi.run(e);
3193 if (cb.valid) {
3194 return cb.bounds.back();
3195 }
3196 return nullptr;
3197
3198 } catch (ResultUndefinedError&) {
3199 return nullptr;
3200 }
3201}
3202
3203Expression* follow_id(Expression* e) {
3204 for (;;) {
3205 if (e == nullptr) {
3206 return nullptr;
3207 }
3208 if (e->eid() == Expression::E_ID && e != constants().absent) {
3209 e = e->cast<Id>()->decl()->e();
3210 } else {
3211 return e;
3212 }
3213 }
3214}
3215
3216Expression* follow_id_to_decl(Expression* e) {
3217 for (;;) {
3218 if (e == nullptr) {
3219 return nullptr;
3220 }
3221 if (e == constants().absent) {
3222 return e;
3223 }
3224 switch (e->eid()) {
3225 case Expression::E_ID:
3226 e = e->cast<Id>()->decl();
3227 break;
3228 case Expression::E_VARDECL: {
3229 Expression* vd_e = e->cast<VarDecl>()->e();
3230 if ((vd_e != nullptr) && vd_e->isa<Id>() && vd_e != constants().absent) {
3231 e = vd_e;
3232 } else {
3233 return e;
3234 }
3235 break;
3236 }
3237 default:
3238 return e;
3239 }
3240 }
3241}
3242
3243Expression* follow_id_to_value(Expression* e) {
3244 Expression* decl = follow_id_to_decl(e);
3245 if (auto* vd = decl->dynamicCast<VarDecl>()) {
3246 if ((vd->e() != nullptr) && vd->e()->type().isPar()) {
3247 return vd->e();
3248 }
3249 return vd->id();
3250 }
3251 return decl;
3252}
3253
3254} // namespace MiniZinc