1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
3 /*
4 * Main authors:
5 * Guido Tack <guido.tack@monash.edu>
6 */
7
8 /* This Source Code Form is subject to the terms of the Mozilla Public
9 * License, v. 2.0. If a copy of the MPL was not distributed with this
10 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
11
12 #pragma once
13
14 #include <minizinc/ast.hh>
15 #include <minizinc/hash.hh>
16
17 namespace MiniZinc {
18
19 /**
20 * \brief Bottom-up iterator for expressions
21 */
22 template <class T>
23 class BottomUpIterator {
24 protected:
25 /// The visitor to call back during iteration
26 T& _t;
27
28 /// Stack item
29 struct C {
30 /// Expression on the stack
31 Expression* e;
32 /// Whether this expression has been visited before
33 bool done;
34 /// If part of a generator expression, which one it is
35 int genNumber;
36 /// Constructor
CMiniZinc::BottomUpIterator::C37 C(Expression* e0) : e(e0), done(false), genNumber(-1) {}
38 /// Constructor for generator expression
CMiniZinc::BottomUpIterator::C39 C(Expression* e0, int genNumber0) : e(e0), done(true), genNumber(genNumber0) {}
40 };
41
42 /// Push all elements of \a v onto \a stack
43 template <class E>
pushVec(std::vector<C> & stack,ASTExprVec<E> v)44 void pushVec(std::vector<C>& stack, ASTExprVec<E> v) {
45 for (unsigned int i = 0; i < v.size(); i++) {
46 stack.push_back(C(v[i]));
47 }
48 }
49
50 public:
51 /// Constructor
BottomUpIterator(T & t)52 BottomUpIterator(T& t) : _t(t) {}
53 /// Run iterator on expression \a e
54 void run(Expression* root);
55 };
56
57 template <class T>
bottom_up(T & t,Expression * e)58 void bottom_up(T& t, Expression* e) {
59 BottomUpIterator<T>(t).run(e);
60 }
61
62 /**
63 * \brief Leaf iterator for expressions
64 */
65 template <class T>
66 class TopDownIterator {
67 protected:
68 /// The visitor to call back during iteration
69 T& _t;
70
71 /// Push all elements of \a v onto \a stack
72 template <class E>
pushVec(std::vector<Expression * > & stack,ASTExprVec<E> v)73 static void pushVec(std::vector<Expression*>& stack, ASTExprVec<E> v) {
74 for (unsigned int i = 0; i < v.size(); i++) {
75 stack.push_back(v[i]);
76 }
77 }
78
79 public:
80 /// Constructor
TopDownIterator(T & t)81 TopDownIterator(T& t) : _t(t) {}
82 /// Run iterator on expression \a e
83 void run(Expression* root);
84 };
85
86 template <class T>
top_down(T & t,Expression * root)87 void top_down(T& t, Expression* root) {
88 TopDownIterator<T>(t).run(root);
89 }
90
91 /* IMPLEMENTATION */
92
93 template <class T>
run(Expression * root)94 void BottomUpIterator<T>::run(Expression* root) {
95 std::vector<C> stack;
96 if (_t.enter(root)) {
97 stack.push_back(C(root));
98 }
99 while (!stack.empty()) {
100 C& c = stack.back();
101 if (c.e == nullptr) {
102 stack.pop_back();
103 continue;
104 }
105 if (c.done) {
106 switch (c.e->eid()) {
107 case Expression::E_INTLIT:
108 _t.vIntLit(*c.e->template cast<IntLit>());
109 break;
110 case Expression::E_FLOATLIT:
111 _t.vFloatLit(*c.e->template cast<FloatLit>());
112 break;
113 case Expression::E_SETLIT:
114 _t.vSetLit(*c.e->template cast<SetLit>());
115 break;
116 case Expression::E_BOOLLIT:
117 _t.vBoolLit(*c.e->template cast<BoolLit>());
118 break;
119 case Expression::E_STRINGLIT:
120 _t.vStringLit(*c.e->template cast<StringLit>());
121 break;
122 case Expression::E_ID:
123 _t.vId(*c.e->template cast<Id>());
124 break;
125 case Expression::E_ANON:
126 _t.vAnonVar(*c.e->template cast<AnonVar>());
127 break;
128 case Expression::E_ARRAYLIT:
129 _t.vArrayLit(*c.e->template cast<ArrayLit>());
130 break;
131 case Expression::E_ARRAYACCESS:
132 _t.vArrayAccess(*c.e->template cast<ArrayAccess>());
133 break;
134 case Expression::E_COMP:
135 if (c.genNumber >= 0) {
136 _t.vComprehensionGenerator(*c.e->template cast<Comprehension>(), c.genNumber);
137 } else {
138 _t.vComprehension(*c.e->template cast<Comprehension>());
139 }
140 break;
141 case Expression::E_ITE:
142 _t.vITE(*c.e->template cast<ITE>());
143 break;
144 case Expression::E_BINOP:
145 _t.vBinOp(*c.e->template cast<BinOp>());
146 break;
147 case Expression::E_UNOP:
148 _t.vUnOp(*c.e->template cast<UnOp>());
149 break;
150 case Expression::E_CALL:
151 _t.vCall(*c.e->template cast<Call>());
152 break;
153 case Expression::E_VARDECL:
154 _t.vVarDecl(*c.e->template cast<VarDecl>());
155 break;
156 case Expression::E_LET:
157 _t.vLet(*c.e->template cast<Let>());
158 break;
159 case Expression::E_TI:
160 _t.vTypeInst(*c.e->template cast<TypeInst>());
161 break;
162 case Expression::E_TIID:
163 _t.vTIId(*c.e->template cast<TIId>());
164 break;
165 }
166 _t.exit(c.e);
167 stack.pop_back();
168 } else {
169 c.done = true;
170 Expression* ce = c.e;
171 for (ExpressionSetIter it = ce->ann().begin(); it != ce->ann().end(); ++it) {
172 if (_t.enter(*it)) {
173 stack.push_back(C(*it));
174 }
175 }
176 if (_t.enter(ce)) {
177 switch (ce->eid()) {
178 case Expression::E_INTLIT:
179 case Expression::E_FLOATLIT:
180 case Expression::E_BOOLLIT:
181 case Expression::E_STRINGLIT:
182 case Expression::E_ANON:
183 case Expression::E_ID:
184 case Expression::E_TIID:
185 break;
186 case Expression::E_SETLIT:
187 pushVec(stack, ce->template cast<SetLit>()->v());
188 break;
189 case Expression::E_ARRAYLIT: {
190 for (unsigned int i = 0; i < ce->cast<ArrayLit>()->size(); i++) {
191 stack.push_back((*ce->cast<ArrayLit>())[i]);
192 }
193 } break;
194 case Expression::E_ARRAYACCESS:
195 pushVec(stack, ce->template cast<ArrayAccess>()->idx());
196 stack.push_back(C(ce->template cast<ArrayAccess>()->v()));
197 break;
198 case Expression::E_COMP: {
199 auto* comp = ce->template cast<Comprehension>();
200 stack.push_back(C(comp->e()));
201 for (unsigned int i = comp->numberOfGenerators(); (i--) != 0U;) {
202 for (unsigned int j = comp->numberOfDecls(i); (j--) != 0U;) {
203 stack.push_back(C(comp->decl(i, j)));
204 }
205 if (comp->in(i) != nullptr) {
206 stack.push_back(C(comp->where(i)));
207 stack.push_back(C(comp, i));
208 stack.push_back(C(comp->in(i)));
209 } else {
210 stack.push_back(C(comp, i));
211 stack.push_back(C(comp->where(i)));
212 }
213 }
214 } break;
215 case Expression::E_ITE: {
216 ITE* ite = ce->template cast<ITE>();
217 stack.push_back(C(ite->elseExpr()));
218 for (int i = 0; i < ite->size(); i++) {
219 stack.push_back(C(ite->ifExpr(i)));
220 stack.push_back(C(ite->thenExpr(i)));
221 }
222 } break;
223 case Expression::E_BINOP:
224 stack.push_back(C(ce->template cast<BinOp>()->rhs()));
225 stack.push_back(C(ce->template cast<BinOp>()->lhs()));
226 break;
227 case Expression::E_UNOP:
228 stack.push_back(C(ce->template cast<UnOp>()->e()));
229 break;
230 case Expression::E_CALL:
231 for (unsigned int i = 0; i < ce->template cast<Call>()->argCount(); i++) {
232 stack.push_back(ce->template cast<Call>()->arg(i));
233 }
234 break;
235 case Expression::E_VARDECL:
236 stack.push_back(C(ce->template cast<VarDecl>()->e()));
237 stack.push_back(C(ce->template cast<VarDecl>()->ti()));
238 break;
239 case Expression::E_LET:
240 stack.push_back(C(ce->template cast<Let>()->in()));
241 pushVec(stack, ce->template cast<Let>()->let());
242 break;
243 case Expression::E_TI:
244 stack.push_back(C(ce->template cast<TypeInst>()->domain()));
245 pushVec(stack, ce->template cast<TypeInst>()->ranges());
246 break;
247 }
248 } else {
249 c.e = nullptr;
250 }
251 }
252 }
253 }
254
255 template <class T>
run(Expression * root)256 void TopDownIterator<T>::run(Expression* root) {
257 std::vector<Expression*> stack;
258 if (_t.enter(root)) {
259 stack.push_back(root);
260 }
261 while (!stack.empty()) {
262 Expression* e = stack.back();
263 stack.pop_back();
264 if (e == nullptr) {
265 continue;
266 }
267 if (!_t.enter(e)) {
268 continue;
269 }
270 for (ExpressionSetIter it = e->ann().begin(); it != e->ann().end(); ++it) {
271 stack.push_back(*it);
272 }
273 switch (e->eid()) {
274 case Expression::E_INTLIT:
275 _t.vIntLit(*e->template cast<IntLit>());
276 break;
277 case Expression::E_FLOATLIT:
278 _t.vFloatLit(*e->template cast<FloatLit>());
279 break;
280 case Expression::E_SETLIT:
281 _t.vSetLit(*e->template cast<SetLit>());
282 pushVec(stack, e->template cast<SetLit>()->v());
283 break;
284 case Expression::E_BOOLLIT:
285 _t.vBoolLit(*e->template cast<BoolLit>());
286 break;
287 case Expression::E_STRINGLIT:
288 _t.vStringLit(*e->template cast<StringLit>());
289 break;
290 case Expression::E_ID:
291 _t.vId(*e->template cast<Id>());
292 break;
293 case Expression::E_ANON:
294 _t.vAnonVar(*e->template cast<AnonVar>());
295 break;
296 case Expression::E_ARRAYLIT:
297 _t.vArrayLit(*e->template cast<ArrayLit>());
298 for (unsigned int i = 0; i < e->cast<ArrayLit>()->size(); i++) {
299 stack.push_back((*e->cast<ArrayLit>())[i]);
300 }
301 break;
302 case Expression::E_ARRAYACCESS:
303 _t.vArrayAccess(*e->template cast<ArrayAccess>());
304 pushVec(stack, e->template cast<ArrayAccess>()->idx());
305 stack.push_back(e->template cast<ArrayAccess>()->v());
306 break;
307 case Expression::E_COMP:
308 _t.vComprehension(*e->template cast<Comprehension>());
309 {
310 auto* comp = e->template cast<Comprehension>();
311 for (unsigned int i = comp->numberOfGenerators(); (i--) != 0U;) {
312 stack.push_back(comp->where(i));
313 stack.push_back(comp->in(i));
314 for (unsigned int j = comp->numberOfDecls(i); (j--) != 0U;) {
315 stack.push_back(comp->decl(i, j));
316 }
317 }
318 stack.push_back(comp->e());
319 }
320 break;
321 case Expression::E_ITE:
322 _t.vITE(*e->template cast<ITE>());
323 {
324 ITE* ite = e->template cast<ITE>();
325 stack.push_back(ite->elseExpr());
326 for (int i = 0; i < ite->size(); i++) {
327 stack.push_back(ite->ifExpr(i));
328 stack.push_back(ite->thenExpr(i));
329 }
330 }
331 break;
332 case Expression::E_BINOP:
333 _t.vBinOp(*e->template cast<BinOp>());
334 stack.push_back(e->template cast<BinOp>()->rhs());
335 stack.push_back(e->template cast<BinOp>()->lhs());
336 break;
337 case Expression::E_UNOP:
338 _t.vUnOp(*e->template cast<UnOp>());
339 stack.push_back(e->template cast<UnOp>()->e());
340 break;
341 case Expression::E_CALL:
342 _t.vCall(*e->template cast<Call>());
343 for (unsigned int i = 0; i < e->template cast<Call>()->argCount(); i++) {
344 stack.push_back(e->template cast<Call>()->arg(i));
345 }
346 break;
347 case Expression::E_VARDECL:
348 _t.vVarDecl(*e->template cast<VarDecl>());
349 stack.push_back(e->template cast<VarDecl>()->e());
350 stack.push_back(e->template cast<VarDecl>()->ti());
351 break;
352 case Expression::E_LET:
353 _t.vLet(*e->template cast<Let>());
354 stack.push_back(e->template cast<Let>()->in());
355 pushVec(stack, e->template cast<Let>()->let());
356 break;
357 case Expression::E_TI:
358 _t.vTypeInst(*e->template cast<TypeInst>());
359 stack.push_back(e->template cast<TypeInst>()->domain());
360 pushVec(stack, e->template cast<TypeInst>()->ranges());
361 break;
362 case Expression::E_TIID:
363 _t.vTIId(*e->template cast<TIId>());
364 break;
365 }
366 }
367 }
368
369 } // namespace MiniZinc
370