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/copy.hh>
13 #include <minizinc/hash.hh>
14 
15 namespace MiniZinc {
16 
insert(Expression * e0,Expression * e1)17 void CopyMap::insert(Expression* e0, Expression* e1) {
18   if (!e0->isUnboxedVal() && !e1->isUnboxedVal()) {
19     _nodeMap.insert(e0, e1);
20   }
21 }
find(Expression * e)22 Expression* CopyMap::find(Expression* e) { return static_cast<Expression*>(_nodeMap.find(e)); }
insert(Item * e0,Item * e1)23 void CopyMap::insert(Item* e0, Item* e1) { _nodeMap.insert(e0, e1); }
find(Item * e)24 Item* CopyMap::find(Item* e) { return static_cast<Item*>(_nodeMap.find(e)); }
insert(Model * e0,Model * e1)25 void CopyMap::insert(Model* e0, Model* e1) { _modelMap.insert(std::make_pair(e0, e1)); }
find(Model * e)26 Model* CopyMap::find(Model* e) {
27   auto it = _modelMap.find(e);
28   if (it == _modelMap.end()) {
29     return nullptr;
30   }
31   return it->second;
32 }
insert(IntSetVal * e0,IntSetVal * e1)33 void CopyMap::insert(IntSetVal* e0, IntSetVal* e1) { _nodeMap.insert(e0, e1); }
find(IntSetVal * e)34 IntSetVal* CopyMap::find(IntSetVal* e) { return static_cast<IntSetVal*>(_nodeMap.find(e)); }
insert(FloatSetVal * e0,FloatSetVal * e1)35 void CopyMap::insert(FloatSetVal* e0, FloatSetVal* e1) { _nodeMap.insert(e0, e1); }
find(FloatSetVal * e)36 FloatSetVal* CopyMap::find(FloatSetVal* e) { return static_cast<FloatSetVal*>(_nodeMap.find(e)); }
37 
copy_location(CopyMap & m,const Location & _loc)38 Location copy_location(CopyMap& m, const Location& _loc) { return _loc; }
copy_location(CopyMap & m,Expression * e)39 Location copy_location(CopyMap& m, Expression* e) { return copy_location(m, e->loc()); }
copy_location(CopyMap & m,Item * i)40 Location copy_location(CopyMap& m, Item* i) { return copy_location(m, i->loc()); }
41 
42 void copy_ann(EnvI& env, CopyMap& m, Annotation& oldAnn, Annotation& newAnn, bool followIds,
43               bool copyFundecls, bool isFlatModel);
44 
copy(EnvI & env,CopyMap & m,Expression * e,bool followIds,bool copyFundecls,bool isFlatModel)45 Expression* copy(EnvI& env, CopyMap& m, Expression* e, bool followIds, bool copyFundecls,
46                  bool isFlatModel) {
47   if (e == nullptr) {
48     return nullptr;
49   }
50   if (Expression* cached = m.find(e)) {
51     return cached;
52   }
53   Expression* ret = nullptr;
54   switch (e->eid()) {
55     case Expression::E_INTLIT: {
56       IntLit* c = IntLit::a(e->cast<IntLit>()->v());
57       m.insert(e, c);
58       ret = c;
59     } break;
60     case Expression::E_FLOATLIT: {
61       FloatLit* c = FloatLit::a(e->cast<FloatLit>()->v());
62       m.insert(e, c);
63       ret = c;
64     } break;
65     case Expression::E_SETLIT: {
66       auto* s = e->cast<SetLit>();
67       auto* c = new SetLit(copy_location(m, e), static_cast<IntSetVal*>(nullptr));
68       m.insert(e, c);
69       if (s->isv() != nullptr) {
70         IntSetVal* isv;
71         if (IntSetVal* isvc = m.find(s->isv())) {
72           isv = isvc;
73         } else {
74           IntSetRanges r(s->isv());
75           isv = IntSetVal::ai(r);
76           m.insert(s->isv(), isv);
77         }
78         c->isv(isv);
79       } else if (s->fsv() != nullptr) {
80         FloatSetVal* fsv;
81         if (FloatSetVal* fsvc = m.find(s->fsv())) {
82           fsv = fsvc;
83         } else {
84           FloatSetRanges r(s->fsv());
85           fsv = FloatSetVal::ai(r);
86           m.insert(s->fsv(), fsv);
87         }
88         c->fsv(fsv);
89       } else {
90         if (ASTExprVecO<Expression*>* ve = m.find(s->v())) {
91           c->v(ASTExprVec<Expression>(ve));
92         } else {
93           std::vector<Expression*> elems(s->v().size());
94           for (unsigned int i = s->v().size(); (i--) != 0U;) {
95             elems[i] = copy(env, m, s->v()[i], followIds, copyFundecls, isFlatModel);
96           }
97           ASTExprVec<Expression> ce(elems);
98           m.insert(s->v(), ce);
99           c->v(ce);
100         }
101       }
102       c->type(s->type());
103       ret = c;
104     } break;
105     case Expression::E_BOOLLIT: {
106       ret = e;
107     } break;
108     case Expression::E_STRINGLIT: {
109       auto* sl = e->cast<StringLit>();
110       auto* c = new StringLit(copy_location(m, e), sl->v());
111       m.insert(e, c);
112       ret = c;
113     } break;
114     case Expression::E_ID: {
115       if (e == constants().absent) {
116         return e;
117       }
118       Id* id = e->cast<Id>();
119 
120       if (followIds) {
121         Id* prevId = id;
122         Expression* cur = e;
123         bool done = false;
124         do {
125           if (cur == nullptr) {
126             cur = prevId;
127             done = true;
128           } else {
129             switch (cur->eid()) {
130               case Expression::E_ID:
131                 prevId = cur->cast<Id>();
132                 cur = prevId->decl();
133                 break;
134               case Expression::E_VARDECL:
135                 if (cur->cast<VarDecl>()->e() != nullptr) {
136                   cur = cur->cast<VarDecl>()->e();
137                 } else {
138                   cur = prevId;
139                   done = true;
140                 }
141                 break;
142               default:
143                 done = true;
144             }
145           }
146         } while (!done);
147         if (!cur->isa<Id>()) {
148           return copy(env, m, cur, false);
149         }
150         Id* curId = cur->cast<Id>();
151         if (id->decl() != nullptr) {
152           if (Expression* cached = m.find(id->decl())) {
153             return cached->cast<VarDecl>()->id();
154           }
155         }
156         return curId;
157       }
158       Id* c;
159       if (id->decl() != nullptr) {
160         auto* vd =
161             static_cast<VarDecl*>(copy(env, m, id->decl(), followIds, copyFundecls, isFlatModel));
162         c = vd->id();
163       } else {
164         if (id->idn() != -1) {
165           c = new Id(copy_location(m, e), id->idn(), nullptr);
166         } else {
167           c = new Id(copy_location(m, e), id->v(), nullptr);
168         }
169       }
170       m.insert(e, c);
171       ret = c;
172 
173     } break;
174     case Expression::E_ANON: {
175       auto* c = new AnonVar(copy_location(m, e));
176       m.insert(e, c);
177       ret = c;
178     } break;
179     case Expression::E_ARRAYLIT: {
180       auto* al = e->cast<ArrayLit>();
181       std::vector<std::pair<int, int>> dims(al->dims());
182       for (unsigned int i = 0; i < dims.size(); i++) {
183         dims[i].first = al->min(i);
184         dims[i].second = al->max(i);
185       }
186       if (ArrayLit* sliceView = al->getSliceLiteral()) {
187         ASTIntVec dimsInternal = al->dimsInternal();
188         unsigned int sliceDims = sliceView->dims();
189         unsigned int dimsOffset = al->dims() * 2;
190         std::vector<std::pair<int, int>> slice(sliceDims);
191         for (unsigned int i = 0; i < sliceDims; i++) {
192           slice[i].first = dimsInternal[dimsOffset + i * 2];
193           slice[i].second = dimsInternal[dimsOffset + i * 2 + 1];
194         }
195         auto* c = new ArrayLit(
196             copy_location(m, e),
197             copy(env, m, sliceView, followIds, copyFundecls, isFlatModel)->cast<ArrayLit>(), dims,
198             slice);
199         m.insert(e, c);
200         ret = c;
201       } else {
202         auto* c = new ArrayLit(copy_location(m, e), std::vector<Expression*>(), dims);
203         m.insert(e, c);
204 
205         ASTExprVecO<Expression*>* v;
206         if (ASTExprVecO<Expression*>* cv = m.find(al->getVec())) {
207           v = cv;
208         } else {
209           std::vector<Expression*> elems(al->size());
210           for (unsigned int i = al->size(); (i--) != 0U;) {
211             elems[i] = copy(env, m, (*al)[i], followIds, copyFundecls, isFlatModel);
212           }
213           ASTExprVec<Expression> ce(elems);
214           m.insert(al->getVec(), ce);
215           v = ce.vec();
216         }
217         c->setVec(ASTExprVec<Expression>(v));
218         ret = c;
219       }
220     } break;
221     case Expression::E_ARRAYACCESS: {
222       auto* aa = e->cast<ArrayAccess>();
223       auto* c = new ArrayAccess(copy_location(m, e), nullptr, std::vector<Expression*>());
224       m.insert(e, c);
225 
226       ASTExprVecO<Expression*>* idx;
227       if (ASTExprVecO<Expression*>* cidx = m.find(aa->idx())) {
228         idx = cidx;
229       } else {
230         std::vector<Expression*> elems(aa->idx().size());
231         for (unsigned int i = aa->idx().size(); (i--) != 0U;) {
232           elems[i] = copy(env, m, aa->idx()[i], followIds, copyFundecls, isFlatModel);
233         }
234         ASTExprVec<Expression> ce(elems);
235         m.insert(aa->idx(), ce);
236         idx = ce.vec();
237       }
238       c->v(copy(env, m, aa->v(), followIds, copyFundecls, isFlatModel));
239       c->idx(ASTExprVec<Expression>(idx));
240       ret = c;
241     } break;
242     case Expression::E_COMP: {
243       auto* c = e->cast<Comprehension>();
244       Generators g;
245       auto* cc = new Comprehension(copy_location(m, e), nullptr, g, c->set());
246       m.insert(c, cc);
247 
248       for (int i = 0; i < c->numberOfGenerators(); i++) {
249         std::vector<VarDecl*> vv;
250         for (int j = 0; j < c->numberOfDecls(i); j++) {
251           vv.push_back(static_cast<VarDecl*>(
252               copy(env, m, c->decl(i, j), followIds, copyFundecls, isFlatModel)));
253           // Comprehension VarDecl should not be assigned to a particular value when copying the
254           // full comprehension
255           assert(!c->decl(i, j)->e());
256         }
257         g.g.emplace_back(vv, copy(env, m, c->in(i), followIds, copyFundecls, isFlatModel),
258                          copy(env, m, c->where(i), followIds, copyFundecls, isFlatModel));
259       }
260       cc->init(copy(env, m, c->e(), followIds, copyFundecls, isFlatModel), g);
261       ret = cc;
262     } break;
263     case Expression::E_ITE: {
264       ITE* ite = e->cast<ITE>();
265       ITE* c = new ITE(copy_location(m, e), std::vector<Expression*>(), nullptr);
266       m.insert(e, c);
267       std::vector<Expression*> ifthen(2 * ite->size());
268       for (unsigned int i = ite->size(); (i--) != 0U;) {
269         ifthen[2 * i] = copy(env, m, ite->ifExpr(i), followIds, copyFundecls, isFlatModel);
270         ifthen[2 * i + 1] = copy(env, m, ite->thenExpr(i), followIds, copyFundecls, isFlatModel);
271       }
272       c->init(ifthen, copy(env, m, ite->elseExpr(), followIds, copyFundecls, isFlatModel));
273       ret = c;
274     } break;
275     case Expression::E_BINOP: {
276       auto* b = e->cast<BinOp>();
277       auto* c = new BinOp(copy_location(m, e), nullptr, b->op(), nullptr);
278       if (b->decl() != nullptr) {
279         if (copyFundecls) {
280           c->decl(Item::cast<FunctionI>(copy(env, m, b->decl())));
281         } else {
282           c->decl(b->decl());
283         }
284       }
285       m.insert(e, c);
286       c->lhs(copy(env, m, b->lhs(), followIds, copyFundecls, isFlatModel));
287       c->rhs(copy(env, m, b->rhs(), followIds, copyFundecls, isFlatModel));
288       ret = c;
289     } break;
290     case Expression::E_UNOP: {
291       UnOp* b = e->cast<UnOp>();
292       UnOp* c = new UnOp(copy_location(m, e), b->op(), nullptr);
293       if (b->decl() != nullptr) {
294         if (copyFundecls) {
295           c->decl(Item::cast<FunctionI>(copy(env, m, b->decl())));
296         } else {
297           c->decl(b->decl());
298         }
299       }
300       m.insert(e, c);
301       c->e(copy(env, m, b->e(), followIds, copyFundecls, isFlatModel));
302       ret = c;
303     } break;
304     case Expression::E_CALL: {
305       Call* ca = e->cast<Call>();
306       Call* c = new Call(copy_location(m, e), ca->id(), std::vector<Expression*>());
307 
308       if (ca->decl() != nullptr) {
309         if (copyFundecls) {
310           c->decl(Item::cast<FunctionI>(copy(env, m, ca->decl())));
311         } else {
312           c->decl(ca->decl());
313         }
314       }
315 
316       m.insert(e, c);
317       std::vector<Expression*> args(ca->argCount());
318       for (auto i = static_cast<unsigned int>(args.size()); (i--) != 0U;) {
319         args[i] = copy(env, m, ca->arg(i), followIds, copyFundecls, isFlatModel);
320       }
321       c->args(args);
322       ret = c;
323     } break;
324     case Expression::E_VARDECL: {
325       auto* vd = e->cast<VarDecl>();
326       VarDecl* c;
327       if (vd->id()->hasStr()) {
328         c = new VarDecl(copy_location(m, e), nullptr, vd->id()->v(), nullptr);
329       } else {
330         c = new VarDecl(copy_location(m, e), nullptr, vd->id()->idn(), nullptr);
331       }
332       c->toplevel(vd->toplevel());
333       c->introduced(vd->introduced());
334       if (isFlatModel && vd->flat() == vd) {
335         c->flat(c);
336       } else {
337         c->flat(vd->flat());
338       }
339       c->payload(vd->payload());
340       m.insert(e, c);
341       m.insert(c, c);
342       c->ti(static_cast<TypeInst*>(copy(env, m, vd->ti(), followIds, copyFundecls, isFlatModel)));
343       c->e(copy(env, m, vd->e(), followIds, copyFundecls, isFlatModel));
344       c->type(c->ti()->type());
345       c->id()->type(c->type());
346       ret = c;
347     } break;
348     case Expression::E_LET: {
349       Let* l = e->cast<Let>();
350       std::vector<Expression*> let(l->let().size());
351       for (unsigned int i = l->let().size(); (i--) != 0U;) {
352         let[i] = copy(env, m, l->let()[i], followIds, copyFundecls, isFlatModel);
353       }
354       Let* c = new Let(copy_location(m, e), let,
355                        copy(env, m, l->in(), followIds, copyFundecls, isFlatModel));
356       for (unsigned int i = l->_letOrig.size(); (i--) != 0U;) {
357         c->_letOrig[i] = copy(env, m, l->_letOrig[i], followIds, copyFundecls, isFlatModel);
358       }
359 
360       m.insert(e, c);
361       ret = c;
362     } break;
363     case Expression::E_TI: {
364       auto* t = e->cast<TypeInst>();
365       ASTExprVecO<TypeInst*>* r;
366       if (t->ranges().size() == 0) {
367         r = nullptr;
368       } else if (ASTExprVecO<TypeInst*>* cr = m.find(t->ranges())) {
369         r = cr;
370       } else {
371         std::vector<TypeInst*> rr(t->ranges().size());
372         for (unsigned int i = t->ranges().size(); (i--) != 0U;) {
373           rr[i] = static_cast<TypeInst*>(
374               copy(env, m, t->ranges()[i], followIds, copyFundecls, isFlatModel));
375         }
376         r = ASTExprVecO<TypeInst*>::a(rr);
377       }
378       auto* c = new TypeInst(copy_location(m, e), t->type(), ASTExprVec<TypeInst>(r),
379                              copy(env, m, t->domain(), followIds, copyFundecls, isFlatModel));
380       c->setIsEnum(t->isEnum());
381       m.insert(e, c);
382       ret = c;
383     } break;
384     case Expression::E_TIID: {
385       TIId* t = e->cast<TIId>();
386       TIId* c = new TIId(copy_location(m, e), t->v());
387       m.insert(e, c);
388       ret = c;
389     } break;
390     default:
391       assert(false);
392   }
393   if (!ret->isa<Id>() || ret->cast<Id>()->decl() == nullptr) {
394     ret->type(e->type());
395   }
396   copy_ann(env, m, e->ann(), ret->ann(), followIds, copyFundecls, isFlatModel);
397   return ret;
398 }
399 
copy_ann(EnvI & env,CopyMap & m,Annotation & oldAnn,Annotation & newAnn,bool followIds,bool copyFundecls,bool isFlatModel)400 void copy_ann(EnvI& env, CopyMap& m, Annotation& oldAnn, Annotation& newAnn, bool followIds,
401               bool copyFundecls, bool isFlatModel) {
402   for (ExpressionSetIter it = oldAnn.begin(); it != oldAnn.end(); ++it) {
403     newAnn.add(copy(env, m, *it, followIds, copyFundecls, isFlatModel));
404   }
405 }
406 
copy(EnvI & env,Expression * e,bool followIds,bool copyFundecls,bool isFlatModel)407 Expression* copy(EnvI& env, Expression* e, bool followIds, bool copyFundecls, bool isFlatModel) {
408   CopyMap m;
409   return copy(env, m, e, followIds, copyFundecls, isFlatModel);
410 }
411 
copy(EnvI & env,CopyMap & m,Item * i,bool followIds,bool copyFundecls,bool isFlatModel)412 Item* copy(EnvI& env, CopyMap& m, Item* i, bool followIds, bool copyFundecls, bool isFlatModel) {
413   if (i == nullptr) {
414     return nullptr;
415   }
416   if (Item* cached = m.find(i)) {
417     return cached;
418   }
419   switch (i->iid()) {
420     case Item::II_INC: {
421       auto* ii = i->cast<IncludeI>();
422       auto* c = new IncludeI(copy_location(m, i), ii->f());
423       m.insert(i, c);
424       c->m(copy(env, m, ii->m()), ii->own());
425       return c;
426     }
427     case Item::II_VD: {
428       auto* v = i->cast<VarDeclI>();
429       auto* c = new VarDeclI(copy_location(m, i), nullptr);
430       m.insert(i, c);
431       c->e(static_cast<VarDecl*>(copy(env, m, v->e(), followIds, copyFundecls, isFlatModel)));
432       return c;
433     }
434     case Item::II_ASN: {
435       auto* a = i->cast<AssignI>();
436       auto* c = new AssignI(copy_location(m, i), a->id(), nullptr);
437       m.insert(i, c);
438       c->e(copy(env, m, a->e(), followIds, copyFundecls, isFlatModel));
439       c->decl(static_cast<VarDecl*>(copy(env, m, a->decl(), followIds, copyFundecls, isFlatModel)));
440       return c;
441     }
442     case Item::II_CON: {
443       auto* cc = i->cast<ConstraintI>();
444       auto* c = new ConstraintI(copy_location(m, i), nullptr);
445       m.insert(i, c);
446       c->e(copy(env, m, cc->e(), followIds, copyFundecls, isFlatModel));
447       return c;
448     }
449     case Item::II_SOL: {
450       auto* s = i->cast<SolveI>();
451       SolveI* c;
452       switch (s->st()) {
453         case SolveI::ST_SAT:
454           c = SolveI::sat(Location());
455           break;
456         case SolveI::ST_MIN:
457           c = SolveI::min(Location(), copy(env, m, s->e(), followIds, copyFundecls, isFlatModel));
458           break;
459         case SolveI::ST_MAX:
460           c = SolveI::max(Location(), copy(env, m, s->e(), followIds, copyFundecls, isFlatModel));
461           break;
462       }
463       copy_ann(env, m, s->ann(), c->ann(), followIds, copyFundecls, isFlatModel);
464       m.insert(i, c);
465       return c;
466     }
467     case Item::II_OUT: {
468       auto* o = i->cast<OutputI>();
469       auto* c = new OutputI(copy_location(m, i),
470                             copy(env, m, o->e(), followIds, copyFundecls, isFlatModel));
471       m.insert(i, c);
472       return c;
473     }
474     case Item::II_FUN: {
475       auto* f = i->cast<FunctionI>();
476       std::vector<VarDecl*> params(f->params().size());
477       for (unsigned int j = f->params().size(); (j--) != 0U;) {
478         params[j] = static_cast<VarDecl*>(
479             copy(env, m, f->params()[j], followIds, copyFundecls, isFlatModel));
480       }
481       auto* c = new FunctionI(
482           copy_location(m, i), f->id(),
483           static_cast<TypeInst*>(copy(env, m, f->ti(), followIds, copyFundecls, isFlatModel)),
484           params, copy(env, m, f->e(), followIds, copyFundecls, isFlatModel));
485       c->builtins.e = f->builtins.e;
486       c->builtins.i = f->builtins.i;
487       c->builtins.f = f->builtins.f;
488       c->builtins.b = f->builtins.b;
489       c->builtins.s = f->builtins.s;
490       c->builtins.str = f->builtins.str;
491 
492       copy_ann(env, m, f->ann(), c->ann(), followIds, copyFundecls, isFlatModel);
493       m.insert(i, c);
494       return c;
495     }
496     default:
497       assert(false);
498       return nullptr;
499   }
500 }
501 
copy(EnvI & env,Item * i,bool followIds,bool copyFundecls,bool isFlatModel)502 Item* copy(EnvI& env, Item* i, bool followIds, bool copyFundecls, bool isFlatModel) {
503   CopyMap m;
504   return copy(env, m, i, followIds, copyFundecls, isFlatModel);
505 }
506 
copy(EnvI & env,CopyMap & cm,Model * m,bool isFlatModel)507 Model* copy(EnvI& env, CopyMap& cm, Model* m, bool isFlatModel) {
508   if (m == nullptr) {
509     return nullptr;
510   }
511   if (Model* cached = cm.find(m)) {
512     return cached;
513   }
514   auto* c = new Model;
515   for (auto& i : *m) {
516     c->addItem(copy(env, cm, i, false, true));
517   }
518 
519   for (auto& it : m->_fnmap) {
520     for (auto& i : it.second) {
521       c->registerFn(env, copy(env, cm, i.fi, false, true, isFlatModel)->cast<FunctionI>());
522     }
523   }
524   cm.insert(m, c);
525   return c;
526 }
copy(EnvI & env,Model * m)527 Model* copy(EnvI& env, Model* m) {
528   CopyMap cm;
529   return copy(env, cm, m);
530 }
531 
532 }  // namespace MiniZinc
533