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/astexception.hh>
13#include <minizinc/flatten_internal.hh>
14#include <minizinc/model.hh>
15#include <minizinc/prettyprinter.hh>
16
17#undef MZN_DEBUG_FUNCTION_REGISTRY
18
19namespace MiniZinc {
20
21Model::FnEntry::FnEntry(FunctionI* fi0) : t(fi0->params().size()), fi(fi0), isPolymorphic(false) {
22 for (unsigned int i = 0; i < fi->params().size(); i++) {
23 t[i] = fi->params()[i]->type();
24 isPolymorphic |= (t[i].bt() == Type::BT_TOP);
25 }
26}
27
28bool Model::FnEntry::operator<(const Model::FnEntry& f) const {
29 assert(!compare(*this, f) || !compare(f, *this));
30 return compare(*this, f);
31}
32
33bool Model::FnEntry::compare(const Model::FnEntry& e1, const Model::FnEntry& e2) {
34 if (e1.t.size() < e2.t.size()) {
35 return true;
36 }
37 if (e1.t.size() == e2.t.size()) {
38 for (unsigned int i = 0; i < e1.t.size(); i++) {
39 if (e1.t[i] != e2.t[i]) {
40 if (e1.t[i].isSubtypeOf(e2.t[i], true)) {
41 return true;
42 } else {
43 if (e2.t[i].isSubtypeOf(e1.t[i], true)) return false;
44 switch (e1.t[i].cmp(e2.t[i])) {
45 case -1:
46 return true;
47 case 1:
48 return false;
49 default:
50 assert(false);
51 }
52 }
53 }
54 }
55 }
56 return false;
57}
58
59Model::Model(void) : _parent(NULL), _solveItem(NULL), _outputItem(NULL) { GC::add(this); }
60
61Model::~Model(void) {
62 for (unsigned int j = 0; j < _items.size(); j++) {
63 Item* i = _items[j];
64 if (IncludeI* ii = i->dyn_cast<IncludeI>()) {
65 if (ii->own() && ii->m()) {
66 delete ii->m();
67 ii->m(NULL);
68 }
69 }
70 }
71 GC::remove(this);
72}
73
74VarDeclIterator Model::begin_vardecls(void) { return VarDeclIterator(this, begin()); }
75VarDeclIterator Model::end_vardecls(void) { return VarDeclIterator(this, end()); }
76ConstraintIterator Model::begin_constraints(void) { return ConstraintIterator(this, begin()); }
77ConstraintIterator Model::end_constraints(void) { return ConstraintIterator(this, end()); }
78FunctionIterator Model::begin_functions(void) { return FunctionIterator(this, begin()); }
79FunctionIterator Model::end_functions(void) { return FunctionIterator(this, end()); }
80
81SolveI* Model::solveItem() { return _solveItem; }
82
83OutputI* Model::outputItem() { return _outputItem; }
84
85void Model::addItem(Item* i) {
86 _items.push_back(i);
87 if (i->isa<SolveI>()) {
88 Model* m = this;
89 while (m->_parent) m = m->_parent;
90 m->_solveItem = i->cast<SolveI>();
91 } else if (i->isa<OutputI>()) {
92 Model* m = this;
93 while (m->_parent) m = m->_parent;
94 m->_outputItem = i->cast<OutputI>();
95 }
96}
97
98void Model::setOutputItem(OutputI* oi) {
99 Model* m = this;
100 while (m->_parent) m = m->_parent;
101 m->_outputItem = oi;
102}
103
104namespace {
105/// Return lowest possible base type given other type-inst restrictions
106Type::BaseType lowestBt(const Type& t) {
107 if (t.st() == Type::ST_SET && t.ti() == Type::TI_VAR) return Type::BT_INT;
108 return Type::BT_BOOL;
109}
110/// Return highest possible base type given other type-inst restrictions
111Type::BaseType highestBt(const Type& t) {
112 if (t.st() == Type::ST_SET && t.ti() == Type::TI_VAR) return Type::BT_INT;
113 if (t.ti() == Type::TI_VAR || t.st() == Type::ST_SET) return Type::BT_FLOAT;
114 return Type::BT_ANN;
115}
116} // namespace
117
118void Model::addPolymorphicInstances(Model::FnEntry& fe, std::vector<FnEntry>& entries) {
119 entries.push_back(fe);
120 if (fe.isPolymorphic) {
121 FnEntry cur = fe;
122 std::vector<std::vector<Type*> > type_ids;
123
124 // First step: initialise all type variables to bool
125 // and collect them in the stack vector
126 for (unsigned int i = 0; i < cur.t.size(); i++) {
127 if (cur.t[i].bt() == Type::BT_TOP) {
128 std::vector<Type*> t;
129 for (unsigned int j = i; j < cur.t.size(); j++) {
130 assert(cur.fi->params()[i]->ti()->domain() &&
131 cur.fi->params()[i]->ti()->domain()->isa<TIId>());
132 if (cur.fi->params()[j]->ti()->domain() &&
133 cur.fi->params()[j]->ti()->domain()->isa<TIId>()) {
134 TIId* id0 = cur.fi->params()[i]->ti()->domain()->cast<TIId>();
135 TIId* id1 = cur.fi->params()[j]->ti()->domain()->cast<TIId>();
136 if (id0->v() == id1->v()) {
137 // Found parameter with same type variable
138 // Initialise to lowest concrete base type (bool)
139 cur.t[j].bt(lowestBt(cur.t[j]));
140 t.push_back(&cur.t[j]);
141 }
142 }
143 }
144 type_ids.push_back(t);
145 }
146 }
147
148 std::vector<int> stack;
149 for (unsigned int i = 0; i < type_ids.size(); i++) stack.push_back(i);
150 int final_id = static_cast<int>(type_ids.size()) - 1;
151
152 while (!stack.empty()) {
153 if (stack.back() == final_id) {
154 // If this instance isn't in entries yet, add it
155 bool alreadyDefined = false;
156 for (unsigned int i = 0; i < entries.size(); i++) {
157 if (entries[i].t == cur.t) {
158 alreadyDefined = true;
159 break;
160 }
161 }
162 if (!alreadyDefined) {
163 entries.push_back(cur);
164 }
165 }
166
167 Type& back_t = *type_ids[stack.back()][0];
168 if (back_t.bt() == highestBt(back_t) && back_t.st() == Type::ST_SET) {
169 // last type, remove this item
170 stack.pop_back();
171 } else {
172 if (back_t.bt() == highestBt(back_t)) {
173 // Create set type for current item
174 for (unsigned int i = 0; i < type_ids[stack.back()].size(); i++) {
175 type_ids[stack.back()][i]->st(Type::ST_SET);
176 type_ids[stack.back()][i]->bt(lowestBt(*type_ids[stack.back()][i]));
177 }
178 } else {
179 // Increment type of current item
180 Type::BaseType nextType = static_cast<Type::BaseType>(back_t.bt() + 1);
181 for (unsigned int i = 0; i < type_ids[stack.back()].size(); i++) {
182 type_ids[stack.back()][i]->bt(nextType);
183 }
184 }
185 // Reset types of all further items and push them
186 for (unsigned int i = stack.back() + 1; i < type_ids.size(); i++) {
187 for (unsigned int j = 0; j < type_ids[i].size(); j++) {
188 type_ids[i][j]->bt(lowestBt(*type_ids[i][j]));
189 }
190 stack.push_back(i);
191 }
192 }
193 }
194 }
195}
196
197void Model::registerFn(EnvI& env, FunctionI* fi) {
198 Model* m = this;
199 while (m->_parent) m = m->_parent;
200 FnMap::iterator i_id = m->fnmap.find(fi->id());
201 if (i_id == m->fnmap.end()) {
202 // new element
203 std::vector<FnEntry> v;
204 FnEntry fe(fi);
205 addPolymorphicInstances(fe, v);
206 m->fnmap.insert(std::pair<ASTString, std::vector<FnEntry> >(fi->id(), v));
207 } else {
208 // add to list of existing elements
209 std::vector<FnEntry>& v = i_id->second;
210 for (unsigned int i = 0; i < v.size(); i++) {
211 if (v[i].fi->params().size() == fi->params().size()) {
212 bool alleq = true;
213 for (unsigned int j = 0; j < fi->params().size(); j++) {
214 Type t1 = v[i].fi->params()[j]->type();
215 Type t2 = fi->params()[j]->type();
216 t1.enumId(0);
217 t2.enumId(0);
218 if (t1 != t2) {
219 alleq = false;
220 break;
221 }
222 }
223 if (alleq) {
224 if (v[i].fi->e() && fi->e() && !v[i].isPolymorphic) {
225 throw TypeError(
226 env, fi->loc(),
227 "function with the same type already defined in " + v[i].fi->loc().toString());
228 } else {
229 if (fi->e() || v[i].isPolymorphic) v[i] = fi;
230 return;
231 }
232 }
233 }
234 }
235 FnEntry fe(fi);
236 addPolymorphicInstances(fe, v);
237 }
238 if (fi->id() == "mzn_reverse_map_var") {
239 if (fi->params().size() != 1 || fi->ti()->type() != Type::varbool()) {
240 throw TypeError(env, fi->loc(),
241 "functions called `mzn_reverse_map_var` must have a single argument and "
242 "return type var bool");
243 }
244 Type t = fi->params()[0]->type();
245 revmapmap.insert(std::pair<int, FunctionI*>(t.toInt(), fi));
246 }
247}
248
249FunctionI* Model::matchFn(EnvI& env, const ASTString& id, const std::vector<Type>& t,
250 bool strictEnums) {
251 if (id == constants().var_redef->id()) return constants().var_redef;
252 Model* m = this;
253 while (m->_parent) m = m->_parent;
254 FnMap::iterator i_id = m->fnmap.find(id);
255 if (i_id == m->fnmap.end()) {
256 return NULL;
257 }
258 std::vector<FnEntry>& v = i_id->second;
259 for (unsigned int i = 0; i < v.size(); i++) {
260 std::vector<Type>& fi_t = v[i].t;
261#ifdef MZN_DEBUG_FUNCTION_REGISTRY
262 std::cerr << "try " << *v[i].fi;
263#endif
264 if (fi_t.size() == t.size()) {
265 bool match = true;
266 for (unsigned int j = 0; j < t.size(); j++) {
267 if (!env.isSubtype(t[j], fi_t[j], strictEnums)) {
268#ifdef MZN_DEBUG_FUNCTION_REGISTRY
269 std::cerr << t[j].toString(env) << " does not match " << fi_t[j].toString(env) << "\n";
270#endif
271 match = false;
272 break;
273 }
274 }
275 if (match) {
276 return v[i].fi;
277 }
278 }
279 }
280 return NULL;
281}
282
283void Model::mergeStdLib(EnvI& env, Model* m) const {
284 for (FnMap::const_iterator it = fnmap.begin(); it != fnmap.end(); ++it) {
285 for (std::vector<FnEntry>::const_iterator cit = it->second.begin(); cit != it->second.end();
286 ++cit) {
287 if ((*cit).fi->from_stdlib()) {
288 m->registerFn(env, (*cit).fi);
289 }
290 }
291 }
292}
293
294void Model::sortFn(void) {
295 Model* m = this;
296 while (m->_parent) m = m->_parent;
297 for (FnMap::iterator it = m->fnmap.begin(); it != m->fnmap.end(); ++it) {
298 // Sort all functions by type
299 std::sort(it->second.begin(), it->second.end());
300 }
301}
302
303void Model::fixFnMap(void) {
304 Model* m = this;
305 while (m->_parent) m = m->_parent;
306 for (FnMap::iterator it = m->fnmap.begin(); it != m->fnmap.end(); ++it) {
307 for (unsigned int i = 0; i < it->second.size(); i++) {
308 for (unsigned int j = 0; j < it->second[i].t.size(); j++) {
309 if (it->second[i].t[j].isunknown()) {
310 it->second[i].t[j] = it->second[i].fi->params()[j]->type();
311 }
312 }
313 }
314 }
315}
316
317void Model::checkFnOverloading(EnvI& env) {
318 Model* m = this;
319 while (m->_parent) m = m->_parent;
320 for (FnMap::iterator it = m->fnmap.begin(); it != m->fnmap.end(); ++it) {
321 std::vector<FnEntry>& fs = it->second;
322 for (unsigned int i = 0; i < fs.size() - 1; i++) {
323 FunctionI* cur = fs[i].fi;
324 for (unsigned int j = i + 1; j < fs.size(); j++) {
325 FunctionI* cmp = fs[j].fi;
326 if (cur == cmp || cur->params().size() != cmp->params().size()) break;
327 bool allEqual = true;
328 for (unsigned int i = 0; i < cur->params().size(); i++) {
329 Type t1 = cur->params()[i]->type();
330 Type t2 = cmp->params()[i]->type();
331 t1.enumId(0);
332 t2.enumId(0);
333 if (t1 != t2) {
334 allEqual = false;
335 break;
336 }
337 }
338 if (allEqual)
339 throw TypeError(env, cur->loc(),
340 "unsupported type of overloading. \nFunction/predicate with equivalent "
341 "signature defined in " +
342 cmp->loc().toString());
343 }
344 }
345 }
346}
347
348FunctionI* Model::matchFn(EnvI& env, const ASTString& id, const std::vector<Expression*>& args,
349 bool strictEnums) const {
350 if (id == constants().var_redef->id()) return constants().var_redef;
351 const Model* m = this;
352 while (m->_parent) m = m->_parent;
353 FnMap::const_iterator it = m->fnmap.find(id);
354 if (it == m->fnmap.end()) {
355 return NULL;
356 }
357 const std::vector<FnEntry>& v = it->second;
358 std::vector<FunctionI*> matched;
359 Expression* botarg = NULL;
360 for (unsigned int i = 0; i < v.size(); i++) {
361 const std::vector<Type>& fi_t = v[i].t;
362#ifdef MZN_DEBUG_FUNCTION_REGISTRY
363 std::cerr << "try " << *v[i].fi;
364#endif
365 if (fi_t.size() == args.size()) {
366 bool match = true;
367 for (unsigned int j = 0; j < args.size(); j++) {
368 if (!env.isSubtype(args[j]->type(), fi_t[j], strictEnums)) {
369#ifdef MZN_DEBUG_FUNCTION_REGISTRY
370 std::cerr << args[j]->type().toString(env) << " does not match " << fi_t[j].toString(env)
371 << "\n";
372#endif
373 match = false;
374 break;
375 }
376 if (args[j]->type().isbot() && fi_t[j].bt() != Type::BT_TOP) {
377 botarg = args[j];
378 }
379 }
380 if (match) {
381 if (botarg)
382 matched.push_back(v[i].fi);
383 else
384 return v[i].fi;
385 }
386 }
387 }
388 if (matched.empty()) return NULL;
389 if (matched.size() == 1) return matched[0];
390 Type t = matched[0]->ti()->type();
391 t.ti(Type::TI_PAR);
392 for (unsigned int i = 1; i < matched.size(); i++) {
393 if (!env.isSubtype(t, matched[i]->ti()->type(), strictEnums))
394 throw TypeError(env, botarg->loc(), "ambiguous overloading on return type of function");
395 }
396 return matched[0];
397}
398
399FunctionI* Model::matchFn(EnvI& env, Call* c, bool strictEnums) const {
400 if (c->id() == constants().var_redef->id()) return constants().var_redef;
401 const Model* m = this;
402 while (m->_parent) m = m->_parent;
403 FnMap::const_iterator it = m->fnmap.find(c->id());
404 if (it == m->fnmap.end()) {
405 return NULL;
406 }
407 const std::vector<FnEntry>& v = it->second;
408 std::vector<FunctionI*> matched;
409 Expression* botarg = NULL;
410 for (unsigned int i = 0; i < v.size(); i++) {
411 const std::vector<Type>& fi_t = v[i].t;
412#ifdef MZN_DEBUG_FUNCTION_REGISTRY
413 std::cerr << "try " << *v[i].fi;
414#endif
415 if (fi_t.size() == c->n_args()) {
416 bool match = true;
417 for (unsigned int j = 0; j < c->n_args(); j++) {
418 if (!env.isSubtype(c->arg(j)->type(), fi_t[j], strictEnums)) {
419#ifdef MZN_DEBUG_FUNCTION_REGISTRY
420 std::cerr << c->arg(j)->type().toString(env) << " does not match "
421 << fi_t[j].toString(env) << "\n";
422 std::cerr << "Wrong argument is " << *c->arg(j);
423#endif
424 match = false;
425 break;
426 }
427 if (c->arg(j)->type().isbot() && fi_t[j].bt() != Type::BT_TOP) {
428 botarg = c->arg(j);
429 }
430 }
431 if (match) {
432 if (botarg)
433 matched.push_back(v[i].fi);
434 else
435 return v[i].fi;
436 }
437 }
438 }
439 if (matched.empty()) return NULL;
440 if (matched.size() == 1) return matched[0];
441 Type t = matched[0]->ti()->type();
442 t.ti(Type::TI_PAR);
443 for (unsigned int i = 1; i < matched.size(); i++) {
444 if (!env.isSubtype(t, matched[i]->ti()->type(), strictEnums))
445 throw TypeError(env, botarg->loc(), "ambiguous overloading on return type of function");
446 }
447 return matched[0];
448}
449
450FunctionI* Model::matchRevMap(EnvI& env, const Type& t0) const {
451 const Model* m = this;
452 while (m->_parent) m = m->_parent;
453 Type t = t0;
454 t.enumId(0);
455 RevMapperMap::const_iterator it = revmapmap.find(t.toInt());
456 if (it != revmapmap.end()) {
457 return it->second;
458 } else {
459 return NULL;
460 }
461}
462
463Item*& Model::operator[](int i) {
464 assert(i < _items.size());
465 return _items[i];
466}
467const Item* Model::operator[](int i) const {
468 assert(i < _items.size());
469 return _items[i];
470}
471unsigned int Model::size(void) const { return static_cast<unsigned int>(_items.size()); }
472
473std::vector<Item*>::iterator Model::begin(void) { return _items.begin(); }
474
475std::vector<Item*>::const_iterator Model::begin(void) const { return _items.begin(); }
476
477std::vector<Item*>::iterator Model::end(void) { return _items.end(); }
478
479std::vector<Item*>::const_iterator Model::end(void) const { return _items.end(); }
480
481void Model::compact(void) {
482 struct {
483 bool operator()(const Item* i) { return i->removed(); }
484 } isremoved;
485 _items.erase(remove_if(_items.begin(), _items.end(), isremoved), _items.end());
486}
487
488} // namespace MiniZinc