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