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