A set of benchmarks to compare a new prototype MiniZinc implementation
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#ifndef __MINIZINC_AST_HH__
13#define __MINIZINC_AST_HH__
14
15#include <minizinc/aststring.hh>
16#include <minizinc/astvec.hh>
17#include <minizinc/gc.hh>
18#include <minizinc/type.hh>
19#include <minizinc/values.hh>
20
21#include <cstddef>
22#include <cstdint>
23#include <iostream>
24#include <limits>
25#include <utility>
26#include <vector>
27
28namespace MiniZinc {
29
30class IntLit;
31class FloatLit;
32class SetLit;
33class BoolLit;
34class StringLit;
35class Id;
36class AnonVar;
37class ArrayLit;
38class ArrayAccess;
39class Comprehension;
40class ITE;
41class BinOp;
42class UnOp;
43class Call;
44class VarDecl;
45class Let;
46class TypeInst;
47
48class Item;
49class FunctionI;
50
51class ExpressionSet;
52class ExpressionSetIter;
53
54/// %Location of an expression used during parsing
55class ParserLocation {
56protected:
57 /// Source code file name
58 ASTString _filename;
59 /// Line where expression starts
60 unsigned int _first_line;
61 /// Line where expression ends
62 unsigned int _last_line;
63 /// Column where expression starts
64 unsigned int _first_column;
65 /// Column where expression ends
66 unsigned int _last_column;
67
68public:
69 /// Construct empty location
70 ParserLocation(void) : _first_line(1), _last_line(1), _first_column(0), _last_column(0) {}
71
72 /// Construct location
73 ParserLocation(const ASTString& filename, unsigned int first_line, unsigned int first_column,
74 unsigned int last_line, unsigned int last_column)
75 : _filename(filename),
76 _first_line(first_line),
77 _last_line(last_line),
78 _first_column(first_column),
79 _last_column(last_column) {}
80
81 ASTString filename(void) const { return _filename; }
82 void filename(const ASTString& f) { _filename = f; }
83
84 unsigned int first_line(void) const { return _first_line; }
85 void first_line(unsigned int l) { _first_line = l; }
86
87 unsigned int last_line(void) const { return _last_line; }
88 void last_line(unsigned int l) { _last_line = l; }
89
90 unsigned int first_column(void) const { return _first_column; }
91 void first_column(unsigned int c) { _first_column = c; }
92
93 unsigned int last_column(void) const { return _last_column; }
94 void last_column(unsigned int c) { _last_column = c; }
95
96 std::string toString(void) const {
97 std::ostringstream oss;
98 oss << _filename << ":" << _first_line << "." << _first_column;
99 if (_first_line != _last_line) {
100 oss << "-" << _last_line << "." << _last_column;
101 } else if (_first_column != _last_column) {
102 oss << "-" << _last_column;
103 }
104 return oss.str();
105 }
106};
107
108/// %Location of an expression in the source code
109class Location {
110protected:
111 /// Internal representation of a Location
112 /// Layout depends on sizeof pointer and arguments
113 /// 32 bit pointers:
114 /// Layout 1: filename (32 bit), first line (8 bit), last line-first line (7 bit), first column
115 /// (6 bit), last column (7 bit) Layout 2: filename (32 bit), 4 IntLit for the lines/columns
116 /// 64 bit pointers:
117 /// Layout 1: filename (64 bit), first line (20 bit), last line-first line (20 bit), first
118 /// column (10 bit), last column (10 bit) Layout 2: filename (64 bit), 4 IntLit for the
119 /// lines/columns
120 class LocVec : public ASTVec {
121 protected:
122 LocVec(const ASTString& filename, unsigned int first_line, unsigned int first_column,
123 unsigned int last_line, unsigned int last_column);
124 LocVec(const ASTString& filename, IntVal combined);
125
126 public:
127 static LocVec* a(const ASTString& filename, unsigned int first_line, unsigned int first_column,
128 unsigned int last_line, unsigned int last_column);
129 void mark(void) {
130 _gc_mark = 1;
131 if (_data[0]) static_cast<ASTStringO*>(_data[0])->mark();
132 }
133
134 ASTString filename(void) const;
135 unsigned int first_line(void) const;
136 unsigned int last_line(void) const;
137 unsigned int first_column(void) const;
138 unsigned int last_column(void) const;
139 };
140
141 union LI {
142 LocVec* lv;
143 ptrdiff_t t;
144 } _loc_info;
145
146 LocVec* lv(void) const {
147 LI li = _loc_info;
148 li.t &= ~static_cast<ptrdiff_t>(1);
149 return li.lv;
150 }
151
152public:
153 /// Construct empty location
154 Location(void) { _loc_info.lv = NULL; }
155
156 /// Construct location
157 Location(const ASTString& filename, unsigned int first_line, unsigned int first_column,
158 unsigned int last_line, unsigned int last_column) {
159 if (last_line < first_line) throw InternalError("invalid location");
160 _loc_info.lv = LocVec::a(filename, first_line, first_column, last_line, last_column);
161 }
162
163 Location(const ParserLocation& loc) {
164 _loc_info.lv = LocVec::a(loc.filename(), loc.first_line(), loc.first_column(), loc.last_line(),
165 loc.last_column());
166 }
167
168 /// Return string representation
169 std::string toString(void) const;
170
171 /// Return filename
172 ASTString filename(void) const { return lv() ? lv()->filename() : ASTString(); }
173
174 /// Return first line number
175 unsigned int first_line(void) const { return lv() ? lv()->first_line() : 0; }
176
177 /// Return last line number
178 unsigned int last_line(void) const { return lv() ? lv()->last_line() : 0; }
179
180 /// Return first column number
181 unsigned int first_column(void) const { return lv() ? lv()->first_column() : 0; }
182
183 /// Return last column number
184 unsigned int last_column(void) const { return lv() ? lv()->last_column() : 0; }
185
186 /// Return whether location is introduced by the compiler
187 bool is_introduced(void) const { return _loc_info.lv == NULL || ((_loc_info.t & 1) != 0); }
188
189 /// Mark as alive for garbage collection
190 void mark(void) const;
191
192 /// Return location with introduced flag set
193 Location introduce(void) const;
194
195 /// Location used for un-allocated expressions
196 static Location nonalloc;
197
198 ParserLocation parserLocation(void) const {
199 return ParserLocation(filename(), first_line(), first_column(), last_line(), last_column());
200 }
201};
202
203/// Output operator for locations
204template <class Char, class Traits>
205std::basic_ostream<Char, Traits>& operator<<(std::basic_ostream<Char, Traits>& os,
206 const Location& loc) {
207 std::basic_ostringstream<Char, Traits> s;
208 s.copyfmt(os);
209 s.width(0);
210 if (loc.filename() == "") {
211 s << "unknown file";
212 } else {
213 s << loc.filename();
214 }
215 s << ":" << loc.first_line() << "." << loc.first_column();
216 if (loc.first_line() != loc.last_line()) {
217 s << "-" << loc.last_line() << "." << loc.last_column();
218 } else if (loc.first_column() != loc.last_column()) {
219 s << "-" << loc.last_column();
220 }
221
222 return os << s.str();
223}
224
225/**
226 * \brief Annotations
227 */
228class Annotation {
229private:
230 ExpressionSet* _s;
231
232 /// Delete
233 Annotation(const Annotation&);
234 /// Delete
235 Annotation& operator=(const Annotation&);
236
237public:
238 Annotation(void) : _s(NULL) {}
239 ~Annotation(void);
240 bool contains(Expression* e) const;
241 bool containsCall(const ASTString& id) const;
242 bool isEmpty(void) const;
243 ExpressionSetIter begin(void) const;
244 ExpressionSetIter end(void) const;
245 void add(Expression* e);
246 void add(std::vector<Expression*> e);
247 void remove(Expression* e);
248 void removeCall(const ASTString& id);
249 void clear(void);
250 void merge(const Annotation& ann);
251 Call* getCall(const ASTString& id) const;
252
253 static Annotation empty;
254};
255
256/// returns the Annotation specified by the string; returns NULL if not exists
257Expression* getAnnotation(const Annotation& ann, std::string str);
258
259/// returns the Annotation specified by the string; returns NULL if not exists
260Expression* getAnnotation(const Annotation& ann, const ASTString& str);
261
262/**
263 * \brief Base class for expressions
264 */
265class Expression : public ASTNode {
266protected:
267 /// The %MiniZinc type of the expression
268 Type _type;
269 /// The annotations
270 Annotation _ann;
271 /// The location of the expression
272 Location _loc;
273 /// The hash value of the expression
274 size_t _hash;
275
276public:
277 /// Identifier of the concrete expression type
278 enum ExpressionId {
279 E_INTLIT = ASTNode::NID_END + 1,
280 E_FLOATLIT,
281 E_SETLIT,
282 E_BOOLLIT,
283 E_STRINGLIT,
284 E_ID,
285 E_ANON,
286 E_ARRAYLIT,
287 E_ARRAYACCESS,
288 E_COMP,
289 E_ITE,
290 E_BINOP,
291 E_UNOP,
292 E_CALL,
293 E_VARDECL,
294 E_LET,
295 E_TI,
296 E_TIID,
297 EID_END = E_TIID
298 };
299
300 bool isUnboxedVal(void) const {
301 if (sizeof(double) <= sizeof(FloatLit*)) {
302 // bit 1 or bit 0 is set
303 return (reinterpret_cast<ptrdiff_t>(this) & static_cast<ptrdiff_t>(3)) != 0;
304 } else {
305 // bit 0 is set
306 return (reinterpret_cast<ptrdiff_t>(this) & static_cast<ptrdiff_t>(1)) != 0;
307 }
308 }
309 bool isUnboxedInt(void) const {
310 if (sizeof(double) <= sizeof(FloatLit*)) {
311 // bit 1 is set, bit 0 is not set
312 return (reinterpret_cast<ptrdiff_t>(this) & static_cast<ptrdiff_t>(3)) == 2;
313 } else {
314 // bit 0 is set
315 return (reinterpret_cast<ptrdiff_t>(this) & static_cast<ptrdiff_t>(1)) == 1;
316 }
317 }
318 bool isUnboxedFloatVal(void) const {
319 // bit 0 is set (and doubles fit inside pointers)
320 return (sizeof(double) <= sizeof(FloatLit*)) &&
321 (reinterpret_cast<ptrdiff_t>(this) & static_cast<ptrdiff_t>(1)) == 1;
322 }
323
324 ExpressionId eid(void) const {
325 return isUnboxedInt() ? E_INTLIT
326 : isUnboxedFloatVal() ? E_FLOATLIT
327 : static_cast<ExpressionId>(_id);
328 }
329
330 const Location& loc(void) const { return isUnboxedVal() ? Location::nonalloc : _loc; }
331 void loc(const Location& l) {
332 if (!isUnboxedVal()) _loc = l;
333 }
334 const Type& type(void) const {
335 return isUnboxedInt() ? Type::unboxedint : isUnboxedFloatVal() ? Type::unboxedfloat : _type;
336 }
337 void type(const Type& t);
338 size_t hash(void) const {
339 return isUnboxedInt() ? unboxedIntToIntVal().hash()
340 : isUnboxedFloatVal() ? unboxedFloatToFloatVal().hash()
341 : _hash;
342 }
343
344protected:
345 /// Combination function for hash values
346 void cmb_hash(size_t h) { _hash ^= h + 0x9e3779b9 + (_hash << 6) + (_hash >> 2); }
347 /// Combination function for hash values
348 size_t cmb_hash(size_t seed, size_t h) {
349 seed ^= h + 0x9e3779b9 + (seed << 6) + (seed >> 2);
350 return seed;
351 }
352
353 /// Compute base hash value
354 void init_hash(void) { _hash = cmb_hash(0, _id); }
355
356 /// Check if \a e0 and \a e1 are equal
357 static bool equal_internal(const Expression* e0, const Expression* e1);
358
359 /// Constructor
360 Expression(const Location& loc, const ExpressionId& eid, const Type& t)
361 : ASTNode(eid), _type(t), _loc(loc) {}
362
363public:
364 IntVal unboxedIntToIntVal(void) const {
365 assert(isUnboxedInt());
366 if (sizeof(double) <= sizeof(FloatVal*)) {
367 unsigned long long int i = reinterpret_cast<ptrdiff_t>(this) & ~static_cast<ptrdiff_t>(7);
368 bool pos = ((reinterpret_cast<ptrdiff_t>(this) & static_cast<ptrdiff_t>(4)) == 0);
369 if (pos) {
370 return i >> 3;
371 } else {
372 return -(static_cast<long long int>(i >> 3));
373 }
374 } else {
375 unsigned long long int i = reinterpret_cast<ptrdiff_t>(this) & ~static_cast<ptrdiff_t>(3);
376 bool pos = ((reinterpret_cast<ptrdiff_t>(this) & static_cast<ptrdiff_t>(2)) == 0);
377 if (pos) {
378 return i >> 2;
379 } else {
380 return -(static_cast<long long int>(i >> 2));
381 }
382 }
383 }
384 static IntLit* intToUnboxedInt(long long int i) {
385 static const unsigned int pointerBits = sizeof(IntLit*) * 8;
386 if (sizeof(double) <= sizeof(FloatVal*)) {
387 static const long long int maxUnboxedVal =
388 (static_cast<long long int>(1) << (pointerBits - 3)) - static_cast<long long int>(1);
389 if (i < -maxUnboxedVal || i > maxUnboxedVal) return NULL;
390 long long int j = i < 0 ? -i : i;
391 ptrdiff_t ubi_p = (static_cast<ptrdiff_t>(j) << 3) | static_cast<ptrdiff_t>(2);
392 if (i < 0) ubi_p = ubi_p | static_cast<ptrdiff_t>(4);
393 return reinterpret_cast<IntLit*>(ubi_p);
394 } else {
395 static const long long int maxUnboxedVal =
396 (static_cast<long long int>(1) << (pointerBits - 2)) - static_cast<long long int>(1);
397 if (i < -maxUnboxedVal || i > maxUnboxedVal) return NULL;
398 long long int j = i < 0 ? -i : i;
399 ptrdiff_t ubi_p = (static_cast<ptrdiff_t>(j) << 2) | static_cast<ptrdiff_t>(1);
400 if (i < 0) ubi_p = ubi_p | static_cast<ptrdiff_t>(2);
401 return reinterpret_cast<IntLit*>(ubi_p);
402 }
403 }
404 FloatVal unboxedFloatToFloatVal(void) const {
405 assert(isUnboxedFloatVal());
406 union {
407 double d;
408 uint64_t bits;
409 const Expression* p;
410 } _u;
411 _u.p = this;
412 _u.bits = _u.bits >> 1;
413 uint64_t exponent = (_u.bits & (static_cast<uint64_t>(0x3FF) << 52)) >> 52;
414 if (exponent != 0) {
415 exponent += 512; // reconstruct original bias of 1023
416 }
417 uint64_t sign = (_u.bits & (static_cast<uint64_t>(1) << 62) ? 1 : 0);
418 _u.bits = (sign << 63) | (exponent << 52) | (_u.bits & static_cast<uint64_t>(0xFFFFFFFFFFFFF));
419 return _u.d;
420 }
421 static FloatLit* doubleToUnboxedFloatVal(double d) {
422 if (sizeof(double) > sizeof(FloatLit*)) return NULL;
423 union {
424 double d;
425 uint64_t bits;
426 FloatLit* p;
427 } _u;
428 _u.d = d;
429
430 uint64_t exponent = (_u.bits & (static_cast<uint64_t>(0x7FF) << 52)) >> 52;
431 if (exponent != 0) {
432 if (exponent < 513 || exponent > 1534) return NULL; // exponent doesn't fit in 10 bits
433 exponent -= 512; // make exponent fit in 10 bits, with bias 511
434 }
435 bool sign = (_u.bits & (static_cast<uint64_t>(1) << 63)) != 0;
436
437 _u.bits = _u.bits &
438 ~(static_cast<uint64_t>(0x7FF) << 52); // mask out top 11 bits (previously exponent)
439 _u.bits = (_u.bits << 1) | 1u; // shift by one bit and add tag for double
440 _u.bits =
441 _u.bits | (static_cast<uint64_t>(sign) << 63) | (static_cast<uint64_t>(exponent) << 53);
442 return _u.p;
443 }
444
445 bool isTagged(void) const {
446 // only bit 2 is set
447 if (isUnboxedVal()) return false;
448 if (sizeof(double) <= sizeof(FloatVal*))
449 return (reinterpret_cast<ptrdiff_t>(this) & static_cast<ptrdiff_t>(7)) == 4;
450 else
451 return (reinterpret_cast<ptrdiff_t>(this) & static_cast<ptrdiff_t>(3)) == 2;
452 }
453
454 Expression* tag(void) const {
455 assert(!isUnboxedVal());
456 if (sizeof(double) <= sizeof(FloatVal*))
457 return reinterpret_cast<Expression*>(reinterpret_cast<ptrdiff_t>(this) |
458 static_cast<ptrdiff_t>(4));
459 else
460 return reinterpret_cast<Expression*>(reinterpret_cast<ptrdiff_t>(this) |
461 static_cast<ptrdiff_t>(2));
462 }
463 Expression* untag(void) {
464 if (isUnboxedVal()) return this;
465 if (sizeof(double) <= sizeof(FloatVal*))
466 return reinterpret_cast<Expression*>(reinterpret_cast<ptrdiff_t>(this) &
467 ~static_cast<ptrdiff_t>(4));
468 else
469 return reinterpret_cast<Expression*>(reinterpret_cast<ptrdiff_t>(this) &
470 ~static_cast<ptrdiff_t>(2));
471 }
472
473 /// Test if expression is of type \a T
474 template <class T>
475 bool isa(void) const {
476#ifdef __clang__
477#pragma clang diagnostic push
478#pragma clang diagnostic ignored "-Wtautological-undefined-compare"
479#endif
480 if (nullptr == this) throw InternalError("isa: nullptr");
481#ifdef __clang__
482#pragma clang diagnostic pop
483#endif
484 return isUnboxedInt() ? T::eid == E_INTLIT
485 : isUnboxedFloatVal() ? T::eid == E_FLOATLIT
486 : _id == T::eid;
487 }
488 /// Cast expression to type \a T*
489 template <class T>
490 T* cast(void) {
491 assert(isa<T>());
492 return static_cast<T*>(this);
493 }
494 /// Cast expression to type \a const T*
495 template <class T>
496 const T* cast(void) const {
497 assert(isa<T>());
498 return static_cast<const T*>(this);
499 }
500 /// Cast expression to type \a T* or NULL if types do not match
501 template <class T>
502 T* dyn_cast(void) {
503 return isa<T>() ? static_cast<T*>(this) : NULL;
504 }
505 /// Cast expression to type \a const T* or NULL if types do not match
506 template <class T>
507 const T* dyn_cast(void) const {
508 return isa<T>() ? static_cast<const T*>(this) : NULL;
509 }
510
511 /// Cast expression to type \a T*
512 template <class T>
513 static T* cast(Expression* e) {
514 return e == NULL ? NULL : e->cast<T>();
515 }
516 /// Cast expression to type \a const T*
517 template <class T>
518 static const T* cast(const Expression* e) {
519 return e == NULL ? NULL : e->cast<T>();
520 }
521 /// Cast expression to type \a T* or NULL if types do not match
522 template <class T>
523 static T* dyn_cast(Expression* e) {
524 return e == NULL ? NULL : e->dyn_cast<T>();
525 }
526 /// Cast expression to type \a const T* or NULL if types do not match
527 template <class T>
528 static const T* dyn_cast(const Expression* e) {
529 return e == NULL ? NULL : e->dyn_cast<T>();
530 }
531
532 /// Add annotation \a ann to the expression
533 void addAnnotation(Expression* ann);
534
535 /// Add annotation \a ann to the expression
536 void addAnnotations(std::vector<Expression*> ann);
537
538 const Annotation& ann(void) const { return isUnboxedVal() ? Annotation::empty : _ann; }
539 Annotation& ann(void) { return isUnboxedVal() ? Annotation::empty : _ann; }
540
541 /// Return hash value of \a e
542 static size_t hash(const Expression* e) { return e == NULL ? 0 : e->hash(); }
543
544 /// Check if \a e0 and \a e1 are equal
545 static bool equal(const Expression* e0, const Expression* e1);
546
547 /// Mark \a e as alive for garbage collection
548 static void mark(Expression* e);
549};
550
551/// \brief Integer literal expression
552class IntLit : public Expression {
553protected:
554 /// The value of this expression
555 IntVal _v;
556 /// Constructor
557 IntLit(const Location& loc, IntVal v);
558
559public:
560 /// The identifier of this expression type
561 static const ExpressionId eid = E_INTLIT;
562 /// Access value
563 IntVal v(void) const { return isUnboxedInt() ? unboxedIntToIntVal() : _v; }
564 /// Recompute hash value
565 void rehash(void);
566 /// Allocate literal
567 static IntLit* a(IntVal v);
568 /// Allocate literal for enumerated type (only used internally for generators)
569 static IntLit* aEnum(IntVal v, unsigned int enumId);
570};
571/// \brief Float literal expression
572class FloatLit : public Expression {
573protected:
574 /// The value of this expression
575 FloatVal _v;
576 /// Constructor
577 FloatLit(const Location& loc, FloatVal v);
578
579public:
580 /// The identifier of this expression type
581 static const ExpressionId eid = E_FLOATLIT;
582 /// Access value
583 FloatVal v(void) const { return isUnboxedFloatVal() ? unboxedFloatToFloatVal() : _v; }
584 /// Recompute hash value
585 void rehash(void);
586 /// Allocate literal
587 static FloatLit* a(FloatVal v);
588};
589/// \brief Set literal expression
590class SetLit : public Expression {
591protected:
592 /// The value of this expression
593 ASTExprVec<Expression> _v;
594 union {
595 /// A range-list based representation for an integer set, or NULL
596 IntSetVal* isv;
597 /// A range-list based representation for an float set, or NULL
598 FloatSetVal* fsv;
599 } _u;
600
601public:
602 /// The identifier of this expression type
603 static const ExpressionId eid = E_SETLIT;
604 /// Construct set \$f\{v1,\dots,vn\}\$f
605 SetLit(const Location& loc, const std::vector<Expression*>& v);
606 /// Construct set \$f\{v1,\dots,vn\}\$f
607 SetLit(const Location& loc, ASTExprVec<Expression> v);
608 /// Construct set
609 SetLit(const Location& loc, IntSetVal* isv);
610 /// Construct set
611 SetLit(const Location& loc, FloatSetVal* fsv);
612 /// Access value
613 ASTExprVec<Expression> v(void) const { return _v; }
614 /// Set value
615 void v(const ASTExprVec<Expression>& val) { _v = val; }
616 /// Access integer set value if present
617 IntSetVal* isv(void) const { return type().bt() == Type::BT_INT ? _u.isv : NULL; }
618 /// Set integer set value
619 void isv(IntSetVal* val) { _u.isv = val; }
620 /// Access float set value if present
621 FloatSetVal* fsv(void) const { return type().bt() == Type::BT_FLOAT ? _u.fsv : NULL; }
622 /// Set integer set value
623 void fsv(FloatSetVal* val) { _u.fsv = val; }
624 /// Recompute hash value
625 void rehash(void);
626};
627/// \brief Boolean literal expression
628class BoolLit : public Expression {
629protected:
630 /// The value of this expression
631 bool _v;
632
633public:
634 /// The identifier of this expression type
635 static const ExpressionId eid = E_BOOLLIT;
636 /// Constructor
637 BoolLit(const Location& loc, bool v);
638 /// Access value
639 bool v(void) const { return _v; }
640 /// Recompute hash value
641 void rehash(void);
642};
643/// \brief String literal expression
644class StringLit : public Expression {
645protected:
646 /// The value of this expression
647 ASTString _v;
648
649public:
650 /// The identifier of this expression type
651 static const ExpressionId eid = E_STRINGLIT;
652 /// Constructor
653 StringLit(const Location& loc, const std::string& v);
654 /// Constructor
655 StringLit(const Location& loc, const ASTString& v);
656 /// Access value
657 ASTString v(void) const { return _v; }
658 /// Set value
659 void v(const ASTString& val) { _v = val; }
660 /// Recompute hash value
661 void rehash(void);
662};
663/// \brief Identifier expression
664class Id : public Expression {
665protected:
666 /// The string identifier
667 void* _v_or_idn;
668 /// The declaration corresponding to this identifier (may be NULL)
669 Expression* _decl;
670
671public:
672 /// The identifier of this expression type
673 static const ExpressionId eid = E_ID;
674 /// Constructor (\a decl may be NULL)
675 Id(const Location& loc, const std::string& v, VarDecl* decl);
676 /// Constructor (\a decl may be NULL)
677 Id(const Location& loc, const ASTString& v, VarDecl* decl);
678 /// Constructor (\a decl may be NULL)
679 Id(const Location& loc, long long int idn, VarDecl* decl);
680 /// Access identifier
681 ASTString v(void) const;
682 /// Set identifier
683 void v(const ASTString& val) { _v_or_idn = val.aststr(); }
684 /// Access identifier number
685 long long int idn(void) const;
686 /// Set identifier number
687 void idn(long long int n) {
688 _v_or_idn =
689 reinterpret_cast<void*>((static_cast<ptrdiff_t>(n) << 1) | static_cast<ptrdiff_t>(1));
690 rehash();
691 }
692 /// Return identifier or X_INTRODUCED plus identifier number
693 ASTString str(void) const;
694 /// Access declaration
695 VarDecl* decl(void) const {
696 Expression* d = _decl;
697 while (d && d->isa<Id>()) d = d->cast<Id>()->_decl;
698 return Expression::cast<VarDecl>(d);
699 }
700 /// Set declaration
701 void decl(VarDecl* d);
702 /// Redirect to another Id \a id
703 void redirect(Id* id) {
704 assert(_decl == NULL || _decl->isa<VarDecl>());
705 _decl = id;
706 }
707 /// Recompute hash value
708 void rehash(void);
709};
710/// \brief Type-inst identifier expression
711class TIId : public Expression {
712protected:
713 /// The string identifier
714 ASTString _v;
715
716public:
717 /// The identifier of this expression type
718 static const ExpressionId eid = E_TIID;
719 /// Constructor
720 TIId(const Location& loc, const std::string& v);
721 /// Access identifier
722 ASTString v(void) const { return _v; }
723 /// Set identifier
724 void v(const ASTString& val) { _v = val; }
725 /// Check whether it is an enum identifier (starting with two $ signs)
726 bool isEnum(void) const { return _v.c_str()[0] == '$'; }
727 /// Recompute hash value
728 void rehash(void);
729};
730/// \brief Anonymous variable expression
731class AnonVar : public Expression {
732public:
733 /// The identifier of this expression type
734 static const ExpressionId eid = E_ANON;
735 /// Constructor
736 AnonVar(const Location& loc);
737 /// Recompute hash value
738 void rehash(void);
739};
740/// \brief Array literal expression
741class ArrayLit : public Expression {
742 friend class Expression;
743
744protected:
745 /// The array
746 union {
747 /// An expression vector (if _flag_2==false)
748 ASTExprVecO<Expression*>* _v;
749 /// Another array literal (if _flag_2==true)
750 ArrayLit* _al;
751 } _u;
752 /// The declared array dimensions
753 // If _flag_2 is true, then this is an array view. In that case,
754 // the _dims array holds the sliced dimensions
755 ASTIntVec _dims;
756 /// Set compressed vector (initial repetitions are removed)
757 void compress(const std::vector<Expression*>& v, const std::vector<int>& dims);
758
759public:
760 /// Index conversion from slice to original
761 int origIdx(int i) const;
762 /// Get element \a i of a sliced array
763 Expression* slice_get(int i) const;
764 /// Set element \a i of a sliced array
765 void slice_set(int i, Expression* e);
766
767public:
768 /// The identifier of this expression type
769 static const ExpressionId eid = E_ARRAYLIT;
770 /// Constructor
771 ArrayLit(const Location& loc, const std::vector<Expression*>& v,
772 const std::vector<std::pair<int, int> >& dims);
773 /// Constructor (existing content)
774 ArrayLit(const Location& loc, ArrayLit& v, const std::vector<std::pair<int, int> >& dims);
775 /// Constructor (one-dimensional, existing content)
776 ArrayLit(const Location& loc, ArrayLit& v);
777 /// Constructor (one-dimensional)
778 ArrayLit(const Location& loc, const std::vector<Expression*>& v);
779 /// Constructor (two-dimensional)
780 ArrayLit(const Location& loc, const std::vector<std::vector<Expression*> >& v);
781 /// Constructor for slices
782 ArrayLit(const Location& loc, ArrayLit* v, const std::vector<std::pair<int, int> >& dims,
783 const std::vector<std::pair<int, int> >& slice);
784 /// Constructor (one-dimensional)
785 ArrayLit(const Location& loc, const std::vector<KeepAlive>& v);
786 /// Recompute hash value
787 void rehash(void);
788
789 // The following methods are only used for copying
790
791 /// Access value
792 ASTExprVec<Expression> getVec(void) const {
793 assert(!_flag_2);
794 return _u._v;
795 }
796 /// Set value
797 void setVec(const ASTExprVec<Expression>& val) {
798 assert(!_flag_2);
799 _u._v = val.vec();
800 }
801 /// Get underlying array (if this is an array slice) or NULL
802 ArrayLit* getSliceLiteral(void) const { return _flag_2 ? _u._al : NULL; }
803 /// Get underlying _dims vector
804 ASTIntVec dimsInternal(void) const { return _dims; }
805
806 /// Return number of dimensions
807 int dims(void) const;
808 /// Return minimum index of dimension \a i
809 int min(int i) const;
810 /// Return maximum index of dimension \a i
811 int max(int i) const;
812 /// Return the length of the array
813 int length(void) const;
814 /// Turn into 1d array (only used at the end of flattening)
815 void make1d(void);
816 /// Check if this array was produced by flattening
817 bool flat(void) const { return _flag_1; }
818 /// Set whether this array was produced by flattening
819 void flat(bool b) { _flag_1 = b; }
820 /// Return size of underlying array
821 unsigned int size(void) const { return (_flag_2 || _u._v->flag()) ? length() : _u._v->size(); }
822 /// Access element \a i
823 Expression* operator[](int i) const {
824 return (_flag_2 || _u._v->flag()) ? slice_get(i) : (*_u._v)[i];
825 }
826 /// Set element \a i
827 void set(int i, Expression* e) {
828 if (_flag_2 || _u._v->flag()) {
829 slice_set(i, e);
830 } else {
831 (*_u._v)[i] = e;
832 }
833 }
834};
835/// \brief Array access expression
836class ArrayAccess : public Expression {
837protected:
838 /// The array to access
839 Expression* _v;
840 /// The indexes (for all array dimensions)
841 ASTExprVec<Expression> _idx;
842
843public:
844 /// The identifier of this expression type
845 static const ExpressionId eid = E_ARRAYACCESS;
846 /// Constructor
847 ArrayAccess(const Location& loc, Expression* v, const std::vector<Expression*>& idx);
848 /// Constructor
849 ArrayAccess(const Location& loc, Expression* v, ASTExprVec<Expression> idx);
850 /// Access value
851 Expression* v(void) const { return _v; }
852 /// Set value
853 void v(Expression* val) { _v = val; }
854 /// Access index sets
855 ASTExprVec<Expression> idx(void) const { return _idx; }
856 /// Set index sets
857 void idx(const ASTExprVec<Expression>& idx) { _idx = idx; }
858 /// Recompute hash value
859 void rehash(void);
860};
861/**
862 * \brief Generators for comprehensions
863 *
864 * A generator consists of a list of variable declarations, one for
865 * each generated variable, and the expression to generate. E.g.,
866 * the Zinc expression [ x[i,j,k] | i,j in 1..10, k in 1..5] contains
867 * two generators. The first one has variable declarations for i and j
868 * and the expression 1..10, and the second one has a variable declaration
869 * for k and the expression 1..5.
870 *
871 */
872class Generator {
873 friend class Comprehension;
874
875protected:
876 /// Variable declarations
877 std::vector<VarDecl*> _v;
878 /// in-expression
879 Expression* _in;
880 /// where-expression
881 Expression* _where;
882
883public:
884 /// Allocate
885 Generator(const std::vector<std::string>& v, Expression* in, Expression* where);
886 /// Allocate
887 Generator(const std::vector<ASTString>& v, Expression* in, Expression* where);
888 /// Allocate
889 Generator(const std::vector<Id*>& v, Expression* in, Expression* where);
890 /// Allocate
891 Generator(const std::vector<VarDecl*>& v, Expression* in, Expression* where);
892 /// Allocate single where clause (without generator) at position \a pos
893 Generator(int pos, Expression* where);
894};
895/// \brief A list of generators with one where-expression
896struct Generators {
897 /// %Generators
898 std::vector<Generator> _g;
899 /// Constructor
900 Generators(void) {}
901};
902/// \brief An expression representing an array- or set-comprehension
903class Comprehension : public Expression {
904 friend class Expression;
905
906protected:
907 /// The expression to generate
908 Expression* _e;
909 /// A list of generator expressions
910 ASTExprVec<Expression> _g;
911 /// A list of indices where generators start
912 ASTIntVec _g_idx;
913
914public:
915 /// The identifier of this expression type
916 static const ExpressionId eid = E_COMP;
917 /// Constructor
918 Comprehension(const Location& loc, Expression* e, Generators& g, bool set);
919 /// Recompute hash value
920 void rehash(void);
921 /// Whether comprehension is a set
922 bool set(void) const;
923
924 /// Return number of generators
925 int n_generators(void) const;
926 /// Return "in" expression for generator \a i
927 Expression* in(int i);
928 /// Return "in" expression for generator \a i
929 const Expression* in(int i) const;
930 /// Return number of declarations for generator \a i
931 int n_decls(int i) const;
932 /// Return declaration \a i for generator \a gen
933 VarDecl* decl(int gen, int i);
934 /// Return declaration \a i for generator \a gen
935 const VarDecl* decl(int gen, int i) const;
936 /// Return where clause for generator \a i
937 Expression* where(int i);
938 /// Return where clause for generator \a i
939 const Expression* where(int i) const;
940 /// Return generator body
941 Expression* e(void) const { return _e; }
942 /// Set generator body
943 void e(Expression* e0) { _e = e0; }
944 /// Re-construct (used for copying)
945 void init(Expression* e, Generators& g);
946};
947/// \brief If-then-else expression
948class ITE : public Expression {
949 friend class Expression;
950
951protected:
952 /// List of if-then-pairs
953 ASTExprVec<Expression> _e_if_then;
954 /// Else-expression
955 Expression* _e_else;
956
957public:
958 /// The identifier of this expression type
959 static const ExpressionId eid = E_ITE;
960 /// Constructor
961 ITE(const Location& loc, const std::vector<Expression*>& e_if_then, Expression* e_else);
962 int size(void) const { return _e_if_then.size() / 2; }
963 Expression* e_if(int i) { return _e_if_then[2 * i]; }
964 Expression* e_then(int i) { return _e_if_then[2 * i + 1]; }
965 Expression* e_else(void) { return _e_else; }
966 const Expression* e_if(int i) const { return _e_if_then[2 * i]; }
967 const Expression* e_then(int i) const { return _e_if_then[2 * i + 1]; }
968 const Expression* e_else(void) const { return _e_else; }
969 void e_then(int i, Expression* e) { _e_if_then[2 * i + 1] = e; }
970 void e_else(Expression* e) { _e_else = e; }
971 /// Recompute hash value
972 void rehash(void);
973 /// Re-construct (used for copying)
974 void init(const std::vector<Expression*>& e_if_then, Expression* e_else);
975};
976
977/// Type of binary operators
978enum BinOpType {
979 BOT_PLUS,
980 BOT_MINUS,
981 BOT_MULT,
982 BOT_DIV,
983 BOT_IDIV,
984 BOT_MOD,
985 BOT_POW,
986 BOT_LE,
987 BOT_LQ,
988 BOT_GR,
989 BOT_GQ,
990 BOT_EQ,
991 BOT_NQ,
992 BOT_IN,
993 BOT_SUBSET,
994 BOT_SUPERSET,
995 BOT_UNION,
996 BOT_DIFF,
997 BOT_SYMDIFF,
998 BOT_INTERSECT,
999 BOT_PLUSPLUS,
1000 BOT_EQUIV,
1001 BOT_IMPL,
1002 BOT_RIMPL,
1003 BOT_OR,
1004 BOT_AND,
1005 BOT_XOR,
1006 BOT_DOTDOT
1007};
1008/// \brief Binary-operator expression
1009class BinOp : public Expression {
1010protected:
1011 /// Left hand side expression
1012 Expression* _e0;
1013 /// Right hand side expression
1014 Expression* _e1;
1015 /// The predicate or function declaration (or NULL)
1016 FunctionI* _decl;
1017
1018public:
1019 /// The identifier of this expression type
1020 static const ExpressionId eid = E_BINOP;
1021 /// Constructor
1022 BinOp(const Location& loc, Expression* e0, BinOpType op, Expression* e1);
1023 /// Access left hand side
1024 Expression* lhs(void) const { return _e0; }
1025 /// Set left hand side
1026 void lhs(Expression* e) { _e0 = e; }
1027 /// Access right hand side
1028 Expression* rhs(void) const { return _e1; }
1029 /// Set right hand side
1030 void rhs(Expression* e) { _e1 = e; }
1031 /// Access argument \a i
1032 Expression* arg(int i) {
1033 assert(i == 0 || i == 1);
1034 return i == 0 ? _e0 : _e1;
1035 }
1036 /// Return number of arguments
1037 unsigned int n_args(void) const { return 2; }
1038 /// Access declaration
1039 FunctionI* decl(void) const { return _decl; }
1040 /// Set declaration
1041 void decl(FunctionI* f) { _decl = f; }
1042 /// Return string representation of the operator
1043 ASTString opToString(void) const;
1044 /// Recompute hash value
1045 void rehash(void);
1046 /// Return operator type
1047 BinOpType op(void) const;
1048};
1049
1050/// Type of unary operators
1051enum UnOpType { UOT_NOT, UOT_PLUS, UOT_MINUS };
1052/// \brief Unary-operator expressions
1053class UnOp : public Expression {
1054protected:
1055 /// %Expression
1056 Expression* _e0;
1057 /// The predicate or function declaration (or NULL)
1058 FunctionI* _decl;
1059
1060public:
1061 /// The identifier of this expression type
1062 static const ExpressionId eid = E_UNOP;
1063 /// Constructor
1064 UnOp(const Location& loc, UnOpType op, Expression* e);
1065 /// Access expression
1066 Expression* e(void) const { return _e0; }
1067 /// Set expression
1068 void e(Expression* e0) { _e0 = e0; }
1069 /// Access argument \a i
1070 Expression* arg(int i) {
1071 assert(i == 0);
1072 return _e0;
1073 }
1074 /// Return number of arguments
1075 unsigned int n_args(void) const { return 1; }
1076 /// Access declaration
1077 FunctionI* decl(void) const { return _decl; }
1078 /// Set declaration
1079 void decl(FunctionI* f) { _decl = f; }
1080 ASTString opToString(void) const;
1081 /// Recompute hash value
1082 void rehash(void);
1083 /// Return operator type
1084 UnOpType op(void) const;
1085};
1086
1087/// \brief A predicate or function call expression
1088class Call : public Expression {
1089 friend class Expression;
1090
1091protected:
1092 union {
1093 /// Identifier of called predicate or function
1094 ASTStringO* _id;
1095 /// The predicate or function declaration (or NULL)
1096 FunctionI* _decl;
1097 } _u_id;
1098 union {
1099 /// Single-argument call (tagged pointer)
1100 Expression* _oneArg;
1101 /// Arguments to the call
1102 ASTExprVecO<Expression*>* _args;
1103 } _u;
1104 /// Check if _u_id contains an id or a decl
1105 bool hasId(void) const;
1106
1107public:
1108 /// The identifier of this expression type
1109 static const ExpressionId eid = E_CALL;
1110 /// Constructor
1111 Call(const Location& loc, const std::string& id, const std::vector<Expression*>& args);
1112 /// Constructor
1113 Call(const Location& loc, const ASTString& id, const std::vector<Expression*>& args);
1114 /// Access identifier
1115 ASTString id(void) const;
1116 /// Set identifier (overwrites decl)
1117 void id(const ASTString& i);
1118 /// Number of arguments
1119 unsigned int n_args(void) const {
1120 return _u._oneArg->isUnboxedVal() || _u._oneArg->isTagged() ? 1 : _u._args->size();
1121 }
1122 /// Access argument \a i
1123 Expression* arg(int i) const {
1124 assert(i < n_args());
1125 if (_u._oneArg->isUnboxedVal() || _u._oneArg->isTagged()) {
1126 assert(i == 0);
1127 return _u._oneArg->isUnboxedVal() ? _u._oneArg : _u._oneArg->untag();
1128 } else {
1129 return (*_u._args)[i];
1130 }
1131 }
1132 /// Set argument \a i
1133 void arg(int i, Expression* e) {
1134 assert(i < n_args());
1135 if (_u._oneArg->isUnboxedVal() || _u._oneArg->isTagged()) {
1136 assert(i == 0);
1137 _u._oneArg = e->isUnboxedVal() ? e : e->tag();
1138 } else {
1139 (*_u._args)[i] = e;
1140 }
1141 }
1142 /// Set arguments
1143 void args(const ASTExprVec<Expression>& a) {
1144 if (a.size() == 1) {
1145 _u._oneArg = a[0]->isUnboxedVal() ? a[0] : a[0]->tag();
1146 } else {
1147 _u._args = a.vec();
1148 assert(!_u._oneArg->isTagged());
1149 }
1150 }
1151 /// Access declaration
1152 FunctionI* decl(void) const;
1153 /// Set declaration (overwrites id)
1154 void decl(FunctionI* f);
1155 /// Recompute hash value
1156 void rehash(void);
1157};
1158/// \brief A variable declaration expression
1159class VarDecl : public Expression {
1160protected:
1161 /// Type-inst of the declared variable
1162 TypeInst* _ti;
1163 /// Identifier
1164 Id* _id;
1165 /// Initialisation expression (can be NULL)
1166 Expression* _e;
1167 /// Flattened version of the VarDecl
1168 WeakRef _flat;
1169 /// Integer payload
1170 int _payload;
1171
1172public:
1173 /// The identifier of this expression type
1174 static const ExpressionId eid = E_VARDECL;
1175 /// Constructor
1176 VarDecl(const Location& loc, TypeInst* ti, const std::string& id, Expression* e = NULL);
1177 /// Constructor
1178 VarDecl(const Location& loc, TypeInst* ti, const ASTString& id, Expression* e = NULL);
1179 // Constructor
1180 VarDecl(const Location& loc, TypeInst* ti, long long int idn, Expression* e = NULL);
1181 /// Constructor
1182 VarDecl(const Location& loc, TypeInst* ti, Id* id, Expression* e = NULL);
1183
1184 /// Access TypeInst
1185 TypeInst* ti(void) const { return _ti; }
1186 /// Set TypeInst
1187 void ti(TypeInst* t) { _ti = t; }
1188 /// Access identifier
1189 Id* id(void) const { return _id; }
1190 /// Access initialisation expression
1191 Expression* e(void) const;
1192 /// Set initialisation expression
1193 void e(Expression* rhs);
1194 /// Access flattened version
1195 VarDecl* flat(void) { return _flat() ? _flat()->cast<VarDecl>() : NULL; }
1196 /// Set flattened version
1197 void flat(VarDecl* vd);
1198
1199 /// Recompute hash value
1200 void rehash(void);
1201 /// Whether variable is toplevel
1202 bool toplevel(void) const;
1203 /// Whether variable is toplevel
1204 void toplevel(bool t);
1205 /// Whether variable is introduced
1206 bool introduced(void) const;
1207 /// Whether variable is introduced
1208 void introduced(bool t);
1209 /// Whether variable has been evaluated
1210 bool evaluated(void) const;
1211 /// Whether variable has been evaluated
1212 void evaluated(bool t);
1213 /// Access payload
1214 int payload(void) const { return _payload; }
1215 /// Set payload
1216 void payload(int i) { _payload = i; }
1217 /// Put current value on trail
1218 void trail(void);
1219};
1220
1221class EnvI;
1222class CopyMap;
1223
1224/// \brief %Let expression
1225class Let : public Expression {
1226 friend Expression* copy(EnvI& env, CopyMap& m, Expression* e, bool followIds, bool copyFundecls,
1227 bool isFlatModel);
1228 friend class Expression;
1229
1230protected:
1231 /// List of local declarations
1232 ASTExprVec<Expression> _let;
1233 /// Copy of original local declarations
1234 ASTExprVec<Expression> _let_orig;
1235 /// Body of the let
1236 Expression* _in;
1237
1238public:
1239 /// The identifier of this expression type
1240 static const ExpressionId eid = E_LET;
1241 /// Constructor
1242 Let(const Location& loc, const std::vector<Expression*>& let, Expression* in);
1243 /// Recompute hash value
1244 void rehash(void);
1245
1246 /// Access local declarations
1247 ASTExprVec<Expression> let(void) const { return _let; }
1248 /// Access local declarations
1249 ASTExprVec<Expression> let_orig(void) const { return _let_orig; }
1250 /// Access body
1251 Expression* in(void) const { return _in; }
1252
1253 /// Remember current let bindings
1254 void pushbindings(void);
1255 /// Restore previous let bindings
1256 void popbindings(void);
1257};
1258
1259/// \brief Type-inst expression
1260class TypeInst : public Expression {
1261protected:
1262 /// Ranges of an array expression
1263 ASTExprVec<TypeInst> _ranges;
1264 /// Declared domain (or NULL)
1265 Expression* _domain;
1266
1267public:
1268 /// The identifier of this expression type
1269 static const ExpressionId eid = E_TI;
1270 /// Constructor
1271 TypeInst(const Location& loc, const Type& t, ASTExprVec<TypeInst> ranges,
1272 Expression* domain = NULL);
1273 /// Constructor
1274 TypeInst(const Location& loc, const Type& t, Expression* domain = NULL);
1275
1276 /// Access ranges
1277 ASTExprVec<TypeInst> ranges(void) const { return _ranges; }
1278 /// Access domain
1279 Expression* domain(void) const { return _domain; }
1280 //// Set domain
1281 void domain(Expression* d) { _domain = d; }
1282
1283 /// Set ranges to \a ranges
1284 void setRanges(const std::vector<TypeInst*>& ranges);
1285 bool isarray(void) const { return _ranges.size() > 0; }
1286 bool hasTiVariable(void) const;
1287 /// Recompute hash value
1288 void rehash(void);
1289 /// Check if domain is computed from right hand side of variable
1290 bool computedDomain(void) const { return _flag_1; }
1291 /// Set if domain is computed from right hand side of variable
1292 void setComputedDomain(bool b) { _flag_1 = b; }
1293 /// Check if this TypeInst represents an enum
1294 bool isEnum(void) const { return _flag_2; }
1295 /// Set if this TypeInst represents an enum
1296 void setIsEnum(bool b) { _flag_2 = b; }
1297};
1298
1299/**
1300 * \brief Base-class for items
1301 */
1302class Item : public ASTNode {
1303protected:
1304 /// Location of the item
1305 Location _loc;
1306
1307public:
1308 /// Identifier of the concrete item type
1309 enum ItemId {
1310 II_INC = Expression::EID_END + 1,
1311 II_VD,
1312 II_ASN,
1313 II_CON,
1314 II_SOL,
1315 II_OUT,
1316 II_FUN,
1317 II_END = II_FUN
1318 };
1319 ItemId iid(void) const { return static_cast<ItemId>(_id); }
1320
1321 const Location& loc(void) const { return _loc; }
1322
1323protected:
1324 /// Constructor
1325 Item(const Location& loc, const ItemId& iid) : ASTNode(iid), _loc(loc) { _flag_1 = false; }
1326
1327public:
1328 /// Test if item is of type \a T
1329 template <class T>
1330 bool isa(void) const {
1331 return _id == T::iid;
1332 }
1333 /// Cast item to type \a T*
1334 template <class T>
1335 T* cast(void) {
1336 assert(isa<T>());
1337 return static_cast<T*>(this);
1338 }
1339 /// Cast expression to type \a const T*
1340 template <class T>
1341 const T* cast(void) const {
1342 assert(isa<T>());
1343 return static_cast<const T*>(this);
1344 }
1345 /// Cast item to type \a T* or NULL if types do not match
1346 template <class T>
1347 T* dyn_cast(void) {
1348 return isa<T>() ? static_cast<T*>(this) : NULL;
1349 }
1350 /// Cast item to type \a const T* or NULL if types do not match
1351 template <class T>
1352 const T* dyn_cast(void) const {
1353 return isa<T>() ? static_cast<const T*>(this) : NULL;
1354 }
1355
1356 /// Cast item to type \a T*
1357 template <class T>
1358 static T* cast(Item* i) {
1359 return i == NULL ? NULL : i->cast<T>();
1360 }
1361 /// Cast item to type \a const T*
1362 template <class T>
1363 static const T* cast(const Item* i) {
1364 return i == NULL ? NULL : i->cast<T>();
1365 }
1366 /// Cast item to type \a T* or NULL if types do not match
1367 template <class T>
1368 static T* dyn_cast(Item* i) {
1369 return i == NULL ? NULL : i->dyn_cast<T>();
1370 }
1371 /// Cast item to type \a const T* or NULL if types do not match
1372 template <class T>
1373 static const T* dyn_cast(const Item* i) {
1374 return i == NULL ? NULL : i->dyn_cast<T>();
1375 }
1376
1377 /// Check if item should be removed
1378 bool removed(void) const { return _flag_1; }
1379 /// Set flag to remove item
1380 void remove(void) { _flag_1 = true; }
1381 /// Unset remove item flag (only possible if not already removed by compact())
1382 void unremove(void) { _flag_1 = false; }
1383};
1384
1385class Model;
1386
1387/// \brief Include item
1388class IncludeI : public Item {
1389protected:
1390 /// Filename to include
1391 ASTString _f;
1392 /// Model for that file
1393 Model* _m;
1394
1395public:
1396 /// The identifier of this item type
1397 static const ItemId iid = II_INC;
1398 /// Constructor
1399 IncludeI(const Location& loc, const ASTString& f);
1400 /// Access filename
1401 ASTString f(void) const { return _f; }
1402 /// Set filename
1403 void f(const ASTString& nf) { _f = nf; }
1404 /// Access model
1405 Model* m(void) const { return _m; }
1406 /// Set the model
1407 void m(Model* m0, bool own = true) {
1408 assert(_m == NULL || m0 == NULL);
1409 _m = m0;
1410 _flag_2 = own;
1411 }
1412 bool own(void) const { return _flag_2; }
1413};
1414
1415/// \brief Variable declaration item
1416class VarDeclI : public Item {
1417protected:
1418 /// The declaration expression
1419 VarDecl* _e;
1420
1421public:
1422 /// The identifier of this item type
1423 static const ItemId iid = II_VD;
1424 /// Constructor
1425 VarDeclI(const Location& loc, VarDecl* e);
1426 /// Access expression
1427 VarDecl* e(void) const { return _e; }
1428 /// Set expression
1429 void e(VarDecl* vd) { _e = vd; }
1430 /// Flag used during compilation
1431 bool flag(void) const { return _flag_2; }
1432 /// Set flag used during compilation
1433 void flag(bool b) { _flag_2 = b; }
1434};
1435
1436/// \brief Assign item
1437class AssignI : public Item {
1438protected:
1439 /// Identifier of variable to assign to
1440 ASTString _id;
1441 /// Expression to assign to the variable
1442 Expression* _e;
1443 /// Declaration of the variable to assign to
1444 VarDecl* _decl;
1445
1446public:
1447 /// The identifier of this item type
1448 static const ItemId iid = II_ASN;
1449 /// Constructor
1450 AssignI(const Location& loc, const std::string& id, Expression* e);
1451 /// Access identifier
1452 ASTString id(void) const { return _id; }
1453 /// Access expression
1454 Expression* e(void) const { return _e; }
1455 /// Set expression
1456 void e(Expression* e0) { _e = e0; }
1457 /// Access declaration
1458 VarDecl* decl(void) const { return _decl; }
1459 /// Set declaration
1460 void decl(VarDecl* d) { _decl = d; }
1461};
1462
1463/// \brief Constraint item
1464class ConstraintI : public Item {
1465protected:
1466 /// Constraint expression
1467 Expression* _e;
1468
1469public:
1470 /// The identifier of this item type
1471 static const ItemId iid = II_CON;
1472 /// Constructor
1473 ConstraintI(const Location& loc, Expression* e);
1474 /// Access expression
1475 Expression* e(void) const { return _e; }
1476 /// Set expression
1477 void e(Expression* e0) { _e = e0; }
1478 /// Flag used during compilation
1479 bool flag(void) const { return _flag_2; }
1480 /// Set flag used during compilation
1481 void flag(bool b) { _flag_2 = b; }
1482};
1483
1484/// \brief Solve item
1485class SolveI : public Item {
1486protected:
1487 /// Solve item annotation
1488 Annotation _ann;
1489 /// Expression for minimisation/maximisation (or NULL)
1490 Expression* _e;
1491 /// Constructor
1492 SolveI(const Location& loc, Expression* e);
1493
1494public:
1495 /// The identifier of this item type
1496 static const ItemId iid = II_SOL;
1497 /// Type of solving
1498 enum SolveType { ST_SAT, ST_MIN, ST_MAX };
1499 /// Allocate solve satisfy item
1500 static SolveI* sat(const Location& loc);
1501 /// Allocate solve minimize item
1502 static SolveI* min(const Location& loc, Expression* e);
1503 /// Allocate solve maximize item
1504 static SolveI* max(const Location& loc, Expression* e);
1505 /// Access solve annotation
1506 const Annotation& ann(void) const { return _ann; }
1507 /// Access solve annotation
1508 Annotation& ann(void) { return _ann; }
1509 /// Access expression for optimisation
1510 Expression* e(void) const { return _e; }
1511 /// Set expression for optimisation
1512 void e(Expression* e0) { _e = e0; }
1513 /// Return type of solving
1514 SolveType st(void) const;
1515 /// Set type of solving
1516 void st(SolveType s);
1517};
1518
1519/// \brief Output item
1520class OutputI : public Item {
1521protected:
1522 /// Expression to output
1523 Expression* _e;
1524
1525public:
1526 /// The identifier of this item type
1527 static const ItemId iid = II_OUT;
1528 /// Constructor
1529 OutputI(const Location& loc, Expression* e);
1530 /// Access expression
1531 Expression* e(void) const { return _e; }
1532 /// Update expression
1533 void e(Expression* e) { _e = e; }
1534};
1535
1536class EnvI;
1537
1538/// \brief Function declaration item
1539class FunctionI : public Item {
1540protected:
1541 /// Identifier of this function
1542 ASTString _id;
1543 /// Type-inst of the return value
1544 TypeInst* _ti;
1545 /// List of parameter declarations
1546 ASTExprVec<VarDecl> _params;
1547 /// Annotation
1548 Annotation _ann;
1549 /// Function body (or NULL)
1550 Expression* _e;
1551 /// Whether function is defined in the standard library
1552 bool _from_stdlib;
1553
1554public:
1555 /// The identifier of this item type
1556 static const ItemId iid = II_FUN;
1557
1558 /// Type of builtin expression-valued functions
1559 typedef Expression* (*builtin_e)(EnvI&, Call*);
1560 /// Type of builtin int-valued functions
1561 typedef IntVal (*builtin_i)(EnvI&, Call*);
1562 /// Type of builtin bool-valued functions
1563 typedef bool (*builtin_b)(EnvI&, Call*);
1564 /// Type of builtin float-valued functions
1565 typedef FloatVal (*builtin_f)(EnvI&, Call*);
1566 /// Type of builtin set-valued functions
1567 typedef IntSetVal* (*builtin_s)(EnvI&, Call*);
1568 /// Type of builtin string-valued functions
1569 typedef std::string (*builtin_str)(EnvI&, Call*);
1570
1571 /// Builtin functions (or NULL)
1572 struct {
1573 builtin_e e;
1574 builtin_i i;
1575 builtin_f f;
1576 builtin_b b;
1577 builtin_s s;
1578 builtin_str str;
1579 } _builtins;
1580
1581 /// Constructor
1582 FunctionI(const Location& loc, const std::string& id, TypeInst* ti,
1583 const std::vector<VarDecl*>& params, Expression* e = NULL);
1584 /// Constructor
1585 FunctionI(const Location& loc, const ASTString& id, TypeInst* ti,
1586 const ASTExprVec<VarDecl>& params, Expression* e = NULL);
1587
1588 /// Access identifier
1589 ASTString id(void) const { return _id; }
1590 /// Access TypeInst
1591 TypeInst* ti(void) const { return _ti; }
1592 /// Access parameters
1593 ASTExprVec<VarDecl> params(void) const { return _params; }
1594 /// Access annotation
1595 const Annotation& ann(void) const { return _ann; }
1596 /// Access annotation
1597 Annotation& ann(void) { return _ann; }
1598 /// Access body
1599 Expression* e(void) const { return _e; }
1600 /// Set body
1601 void e(Expression* b) { _e = b; }
1602
1603 /** \brief Compute return type given argument types \a ta
1604 */
1605 Type rtype(EnvI& env, const std::vector<Expression*>& ta, bool strictEnums);
1606 /** \brief Compute return type given argument types \a ta
1607 */
1608 Type rtype(EnvI& env, const std::vector<Type>& ta, bool strictEnums);
1609 /** \brief Compute expected type of argument \a n given argument types \a ta
1610 */
1611 Type argtype(EnvI& env, const std::vector<Expression*>& ta, int n);
1612
1613 /// Return whether function is defined in the standard library
1614 bool from_stdlib(void) const { return _from_stdlib; };
1615
1616 /// Mark for GC
1617 void mark(void) {
1618 _gc_mark = 1;
1619 loc().mark();
1620 }
1621};
1622
1623/**
1624 * \brief Visitor for expressions
1625 *
1626 * This class implements no-ops for all expression types.
1627 * Override the methods to implement custom behaviour.
1628 */
1629class EVisitor {
1630public:
1631 /// Visit integer literal
1632 void vIntLit(const IntLit&) {}
1633 /// Visit floating point literal
1634 void vFloatLit(const FloatLit&) {}
1635 /// Visit Boolean literal
1636 void vBoolLit(const BoolLit&) {}
1637 /// Visit set literal
1638 void vSetLit(const SetLit&) {}
1639 /// Visit string literal
1640 void vStringLit(const StringLit&) {}
1641 /// Visit identifier
1642 void vId(const Id&) {}
1643 /// Visit anonymous variable
1644 void vAnonVar(const AnonVar&) {}
1645 /// Visit array literal
1646 void vArrayLit(const ArrayLit&) {}
1647 /// Visit array access
1648 void vArrayAccess(const ArrayAccess&) {}
1649 /// Visit array comprehension
1650 void vComprehension(const Comprehension&) {}
1651 /// Visit array comprehension (only generator \a gen_i)
1652 void vComprehensionGenerator(const Comprehension&, int gen_i) { (void)gen_i; }
1653 /// Visit if-then-else
1654 void vITE(const ITE&) {}
1655 /// Visit binary operator
1656 void vBinOp(const BinOp&) {}
1657 /// Visit unary operator
1658 void vUnOp(const UnOp&) {}
1659 /// Visit call
1660 void vCall(const Call&) {}
1661 /// Visit let
1662 void vLet(const Let&) {}
1663 /// Visit variable declaration
1664 void vVarDecl(const VarDecl&) {}
1665 /// Visit type inst
1666 void vTypeInst(const TypeInst&) {}
1667 /// Visit TIId
1668 void vTIId(const TIId&) {}
1669 /// Determine whether to enter node
1670 bool enter(Expression* e) { return true; }
1671 /// Exit node after processing has finished
1672 void exit(Expression* e) {}
1673};
1674
1675/// Statically allocated constants
1676class Constants {
1677private:
1678 /// Garbage collection root set for constants
1679 Model* m;
1680
1681public:
1682 /// Literal true
1683 BoolLit* lit_true;
1684 /// Variable bound to true
1685 VarDecl* var_true;
1686 /// Literal false
1687 BoolLit* lit_false;
1688 /// Variable bound to false
1689 VarDecl* var_false;
1690 /// Special variable to signal compiler to ignore result
1691 VarDecl* var_ignore;
1692 /// Infinite set
1693 SetLit* infinity;
1694 /// Function item used to keep track of redefined variables
1695 FunctionI* var_redef;
1696 /// Literal absent value
1697 Expression* absent;
1698 /// Identifiers for builtins
1699 struct {
1700 ASTString forall;
1701 ASTString forall_reif;
1702 ASTString exists;
1703 ASTString clause;
1704 ASTString bool2int;
1705 ASTString int2float;
1706 ASTString bool2float;
1707 ASTString assert;
1708 ASTString trace;
1709
1710 ASTString sum;
1711 ASTString lin_exp;
1712 ASTString element;
1713
1714 ASTString show;
1715 ASTString fix;
1716 ASTString output;
1717
1718 struct {
1719 ASTString lin_eq;
1720 ASTString lin_le;
1721 ASTString lin_ne;
1722 ASTString plus;
1723 ASTString minus;
1724 ASTString times;
1725 ASTString div;
1726 ASTString mod;
1727 ASTString lt;
1728 ASTString le;
1729 ASTString gt;
1730 ASTString ge;
1731 ASTString eq;
1732 ASTString ne;
1733 } int_;
1734
1735 struct {
1736 ASTString lin_eq;
1737 ASTString lin_le;
1738 ASTString lin_ne;
1739 ASTString plus;
1740 ASTString minus;
1741 ASTString times;
1742 ASTString div;
1743 ASTString mod;
1744 ASTString lt;
1745 ASTString le;
1746 ASTString gt;
1747 ASTString ge;
1748 ASTString eq;
1749 ASTString ne;
1750 } int_reif;
1751
1752 struct {
1753 ASTString lin_eq;
1754 ASTString lin_le;
1755 ASTString lin_lt;
1756 ASTString lin_ne;
1757 ASTString plus;
1758 ASTString minus;
1759 ASTString times;
1760 ASTString div;
1761 ASTString mod;
1762 ASTString lt;
1763 ASTString le;
1764 ASTString gt;
1765 ASTString ge;
1766 ASTString eq;
1767 ASTString ne;
1768 ASTString in;
1769 ASTString dom;
1770 } float_;
1771
1772 struct {
1773 ASTString lin_eq;
1774 ASTString lin_le;
1775 ASTString lin_lt;
1776 ASTString lin_ne;
1777 ASTString plus;
1778 ASTString minus;
1779 ASTString times;
1780 ASTString div;
1781 ASTString mod;
1782 ASTString lt;
1783 ASTString le;
1784 ASTString gt;
1785 ASTString ge;
1786 ASTString eq;
1787 ASTString ne;
1788 ASTString in;
1789 } float_reif;
1790
1791 ASTString bool_eq;
1792 ASTString bool_eq_reif;
1793 ASTString array_bool_or;
1794 ASTString array_bool_and;
1795 ASTString bool_clause;
1796 ASTString bool_clause_reif;
1797 ASTString bool_xor;
1798 ASTString set_eq;
1799 ASTString set_in;
1800 ASTString set_card;
1801 ASTString pow;
1802
1803 ASTString introduced_var;
1804 ASTString anonEnumFromStrings;
1805 } ids;
1806
1807 /// Identifiers for Boolean contexts
1808 struct {
1809 Id* root;
1810 Id* pos;
1811 Id* neg;
1812 Id* mix;
1813 } ctx;
1814 /// Common annotations
1815 struct {
1816 Id* output_var;
1817 ASTString output_array;
1818 Id* add_to_output;
1819 Id* output_only;
1820 Id* mzn_check_var;
1821 ASTString mzn_check_enum_var;
1822 Id* is_defined_var;
1823 ASTString defines_var;
1824 Id* is_reverse_map;
1825 Id* promise_total;
1826 Id* maybe_partial;
1827 Id* _export;
1828 ASTString doc_comment;
1829 ASTString mzn_path;
1830 ASTString is_introduced;
1831 Id* user_cut; // MIP
1832 Id* lazy_constraint; // MIP
1833 Id* mzn_break_here;
1834 Id* rhs_from_assignment;
1835 Id* domain_change_constraint;
1836 ASTString global_register;
1837 } ann;
1838
1839 /// Command line options
1840 struct { /// basic MiniZinc command line options
1841 ASTString cmdlineData_str;
1842 ASTString cmdlineData_short_str;
1843 ASTString datafile_str;
1844 ASTString datafile_short_str;
1845 ASTString globalsDir_str;
1846 ASTString globalsDir_alt_str;
1847 ASTString globalsDir_short_str;
1848 ASTString help_str;
1849 ASTString help_short_str;
1850 ASTString ignoreStdlib_str;
1851 ASTString include_str;
1852 ASTString inputFromStdin_str;
1853 ASTString instanceCheckOnly_str;
1854 ASTString no_optimize_str;
1855 ASTString no_optimize_alt_str;
1856 ASTString no_outputOzn_str;
1857 ASTString no_outputOzn_short_str;
1858 ASTString no_typecheck_str;
1859 ASTString newfzn_str;
1860 ASTString outputBase_str;
1861 ASTString outputFznToStdout_str;
1862 ASTString outputFznToStdout_alt_str;
1863 ASTString outputOznToFile_str;
1864 ASTString outputOznToStdout_str;
1865 ASTString outputFznToFile_str;
1866 ASTString outputFznToFile_alt_str;
1867 ASTString outputFznToFile_short_str;
1868 ASTString rangeDomainsOnly_str;
1869 ASTString statistics_str;
1870 ASTString statistics_short_str;
1871 ASTString stdlib_str;
1872 ASTString verbose_str;
1873 ASTString verbose_short_str;
1874 ASTString version_str;
1875 ASTString werror_str;
1876
1877 struct {
1878 ASTString all_sols_str;
1879 ASTString fzn_solver_str;
1880 } solver;
1881
1882 } cli;
1883
1884 /// options strings to find setting in Options map
1885 struct {
1886 ASTString cmdlineData;
1887 ASTString datafile;
1888 ASTString datafiles;
1889 ASTString fznToStdout;
1890 ASTString fznToFile;
1891 ASTString globalsDir;
1892 ASTString ignoreStdlib;
1893 ASTString includeDir;
1894 ASTString includePaths;
1895 ASTString instanceCheckOnly;
1896 ASTString inputFromStdin;
1897 ASTString model;
1898 ASTString newfzn;
1899 ASTString noOznOutput;
1900 ASTString optimize;
1901 ASTString outputBase;
1902 ASTString oznToFile;
1903 ASTString oznToStdout;
1904 ASTString rangeDomainsOnly;
1905 ASTString statistics;
1906 ASTString stdlib;
1907 ASTString typecheck;
1908 ASTString verbose;
1909 ASTString werror;
1910
1911 struct {
1912 ASTString allSols;
1913 ASTString numSols;
1914 ASTString threads;
1915 ASTString fzn_solver;
1916 ASTString fzn_flags;
1917 ASTString fzn_flag;
1918 ASTString fzn_time_limit_ms;
1919 ASTString fzn_sigint;
1920 } solver;
1921
1922 } opts;
1923
1924 /// categories of the command line interface options
1925 struct {
1926 ASTString general;
1927 ASTString io;
1928 ASTString solver;
1929 ASTString translation;
1930 } cli_cat;
1931
1932 /// Keep track of allocated integer literals
1933 std::unordered_map<IntVal, WeakRef> integerMap;
1934 /// Keep track of allocated float literals
1935 std::unordered_map<FloatVal, WeakRef> floatMap;
1936 /// Constructor
1937 Constants(void);
1938 /// Return shared BoolLit
1939 BoolLit* boollit(bool b) { return b ? lit_true : lit_false; }
1940 static const int max_array_size = std::numeric_limits<int>::max() / 2;
1941};
1942
1943/// Return static instance
1944Constants& constants(void);
1945
1946} // namespace MiniZinc
1947
1948#include <minizinc/ast.hpp>
1949
1950#endif