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