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 }
43 if (e2.t[i].isSubtypeOf(e1.t[i], true)) {
44 return false;
45 }
46 switch (e1.t[i].cmp(e2.t[i])) {
47 case -1:
48 return true;
49 case 1:
50 return false;
51 default:
52 assert(false);
53 }
54 }
55 }
56 }
57 return false;
58}
59
60Model::Model() : _parent(nullptr), _solveItem(nullptr), _outputItem(nullptr) {}
61
62Model::~Model() {
63 for (auto* i : _items) {
64 if (auto* ii = i->dynamicCast<IncludeI>()) {
65 if (ii->own()) {
66 delete ii->m();
67 ii->m(nullptr);
68 }
69 }
70 }
71}
72
73VarDeclIteratorContainer Model::vardecls() { return VarDeclIteratorContainer(this); }
74ConstraintIteratorContainer Model::constraints() { return ConstraintIteratorContainer(this); }
75FunctionIteratorContainer Model::functions() { return FunctionIteratorContainer(this); }
76
77VarDeclIterator VarDeclIteratorContainer::begin() { return VarDeclIterator(_m, _m->begin()); }
78VarDeclIterator VarDeclIteratorContainer::end() { return VarDeclIterator(_m, _m->end()); }
79ConstraintIterator ConstraintIteratorContainer::begin() {
80 return ConstraintIterator(_m, _m->begin());
81}
82ConstraintIterator ConstraintIteratorContainer::end() { return ConstraintIterator(_m, _m->end()); }
83FunctionIterator FunctionIteratorContainer::begin() { return FunctionIterator(_m, _m->begin()); }
84FunctionIterator FunctionIteratorContainer::end() { return FunctionIterator(_m, _m->end()); }
85
86SolveI* Model::solveItem() { return _solveItem; }
87
88OutputI* Model::outputItem() { return _outputItem; }
89
90void Model::addItem(Item* i) {
91 _items.push_back(i);
92 if (i->isa<SolveI>()) {
93 Model* m = this;
94 while (m->_parent != nullptr) {
95 m = m->_parent;
96 }
97 m->_solveItem = i->cast<SolveI>();
98 } else if (i->isa<OutputI>()) {
99 Model* m = this;
100 while (m->_parent != nullptr) {
101 m = m->_parent;
102 }
103 m->_outputItem = i->cast<OutputI>();
104 }
105}
106
107void Model::setOutputItem(OutputI* oi) {
108 Model* m = this;
109 while (m->_parent != nullptr) {
110 m = m->_parent;
111 }
112 m->_outputItem = oi;
113}
114
115namespace {
116/// Return lowest possible base type given other type-inst restrictions
117Type::BaseType lowest_bt(const Type& t) {
118 if (t.st() == Type::ST_SET && t.ti() == Type::TI_VAR) {
119 return Type::BT_INT;
120 }
121 return Type::BT_BOOL;
122}
123/// Return highest possible base type given other type-inst restrictions
124Type::BaseType highest_bt(const Type& t) {
125 if (t.st() == Type::ST_SET && t.ti() == Type::TI_VAR) {
126 return Type::BT_INT;
127 }
128 if (t.ti() == Type::TI_VAR || t.st() == Type::ST_SET) {
129 return Type::BT_FLOAT;
130 }
131 return Type::BT_ANN;
132}
133} // namespace
134
135void Model::addPolymorphicInstances(Model::FnEntry& fe, std::vector<FnEntry>& entries) {
136 entries.push_back(fe);
137 if (fe.isPolymorphic) {
138 FnEntry cur = fe;
139 std::vector<std::vector<Type*> > type_ids;
140
141 // First step: initialise all type variables to bool
142 // and collect them in the stack vector
143 for (unsigned int i = 0; i < cur.t.size(); i++) {
144 if (cur.t[i].bt() == Type::BT_TOP) {
145 std::vector<Type*> t;
146 for (unsigned int j = i; j < cur.t.size(); j++) {
147 assert(cur.fi->params()[i]->ti()->domain() &&
148 cur.fi->params()[i]->ti()->domain()->isa<TIId>());
149 if ((cur.fi->params()[j]->ti()->domain() != nullptr) &&
150 cur.fi->params()[j]->ti()->domain()->isa<TIId>()) {
151 TIId* id0 = cur.fi->params()[i]->ti()->domain()->cast<TIId>();
152 TIId* id1 = cur.fi->params()[j]->ti()->domain()->cast<TIId>();
153 if (id0->v() == id1->v()) {
154 // Found parameter with same type variable
155 // Initialise to lowest concrete base type (bool)
156 cur.t[j].bt(lowest_bt(cur.t[j]));
157 t.push_back(&cur.t[j]);
158 }
159 }
160 }
161 type_ids.push_back(t);
162 }
163 }
164
165 std::vector<int> stack;
166 for (unsigned int i = 0; i < type_ids.size(); i++) {
167 stack.push_back(i);
168 }
169 int final_id = static_cast<int>(type_ids.size()) - 1;
170
171 while (!stack.empty()) {
172 if (stack.back() == final_id) {
173 // If this instance isn't in entries yet, add it
174 bool alreadyDefined = false;
175 for (auto& entry : entries) {
176 if (entry.t == cur.t) {
177 alreadyDefined = true;
178 break;
179 }
180 }
181 if (!alreadyDefined) {
182 entries.push_back(cur);
183 }
184 }
185
186 Type& back_t = *type_ids[stack.back()][0];
187 if (back_t.bt() == highest_bt(back_t) && back_t.st() == Type::ST_SET) {
188 // last type, remove this item
189 stack.pop_back();
190 } else {
191 if (back_t.bt() == highest_bt(back_t)) {
192 // Create set type for current item
193 for (auto& i : type_ids[stack.back()]) {
194 i->st(Type::ST_SET);
195 i->bt(lowest_bt(*i));
196 }
197 } else {
198 // Increment type of current item
199 auto nextType = static_cast<Type::BaseType>(back_t.bt() + 1);
200 for (auto& i : type_ids[stack.back()]) {
201 i->bt(nextType);
202 }
203 }
204 // Reset types of all further items and push them
205 for (unsigned int i = stack.back() + 1; i < type_ids.size(); i++) {
206 for (auto& j : type_ids[i]) {
207 j->bt(lowest_bt(*j));
208 }
209 stack.push_back(i);
210 }
211 }
212 }
213 }
214}
215
216bool Model::registerFn(EnvI& env, FunctionI* fi, bool keepSorted, bool throwIfDuplicate) {
217 Model* m = this;
218 while (m->_parent != nullptr) {
219 m = m->_parent;
220 }
221 auto i_id = m->_fnmap.find(fi->id());
222 if (i_id == m->_fnmap.end()) {
223 // new element
224 std::vector<FnEntry> v;
225 FnEntry fe(fi);
226 addPolymorphicInstances(fe, v);
227 m->_fnmap.insert(std::pair<ASTString, std::vector<FnEntry> >(fi->id(), v));
228 } else {
229 // add to list of existing elements
230 std::vector<FnEntry>& v = i_id->second;
231 for (auto& i : v) {
232 if (i.fi == fi) {
233 return true;
234 }
235 if (i.fi->params().size() == fi->params().size()) {
236 bool alleq = true;
237 for (unsigned int j = 0; j < fi->params().size(); j++) {
238 Type t1 = i.fi->params()[j]->type();
239 Type t2 = fi->params()[j]->type();
240 t1.enumId(0);
241 t2.enumId(0);
242 if (t1 != t2) {
243 alleq = false;
244 break;
245 }
246 }
247 if (alleq) {
248 if ((i.fi->e() != nullptr) && (fi->e() != nullptr) && !i.isPolymorphic) {
249 if (throwIfDuplicate) {
250 throw TypeError(
251 env, fi->loc(),
252 "function with the same type already defined in " + i.fi->loc().toString());
253 }
254 return false;
255 }
256 if ((fi->e() != nullptr) || i.isPolymorphic) {
257 if (Call* deprecated = i.fi->ann().getCall(constants().ann.mzn_deprecated)) {
258 fi->ann().add(deprecated);
259 }
260 i = fi;
261 } else if (Call* deprecated = fi->ann().getCall(constants().ann.mzn_deprecated)) {
262 i.fi->ann().add(deprecated);
263 }
264 return true;
265 }
266 }
267 }
268 FnEntry fe(fi);
269 addPolymorphicInstances(fe, v);
270 if (keepSorted) {
271 std::sort(i_id->second.begin(), i_id->second.end());
272 }
273 }
274 if (fi->id() == "mzn_reverse_map_var") {
275 if (fi->params().size() != 1 || fi->ti()->type() != Type::varbool()) {
276 throw TypeError(env, fi->loc(),
277 "functions called `mzn_reverse_map_var` must have a single argument and "
278 "return type var bool");
279 }
280 Type t = fi->params()[0]->type();
281 _revmapmap.insert(std::pair<int, FunctionI*>(t.toInt(), fi));
282 }
283 return true;
284}
285
286FunctionI* Model::matchFn(EnvI& env, const ASTString& id, const std::vector<Type>& t,
287 bool strictEnums) {
288 if (id == constants().varRedef->id()) {
289 return constants().varRedef;
290 }
291 Model* m = this;
292 while (m->_parent != nullptr) {
293 m = m->_parent;
294 }
295 auto i_id = m->_fnmap.find(id);
296 if (i_id == m->_fnmap.end()) {
297 return nullptr;
298 }
299 std::vector<FnEntry>& v = i_id->second;
300 for (auto& i : v) {
301 std::vector<Type>& fi_t = i.t;
302#ifdef MZN_DEBUG_FUNCTION_REGISTRY
303 std::cerr << "try " << *i.fi;
304#endif
305 if (fi_t.size() == t.size()) {
306 bool match = true;
307 for (unsigned int j = 0; j < t.size(); j++) {
308 if (!env.isSubtype(t[j], fi_t[j], strictEnums)) {
309#ifdef MZN_DEBUG_FUNCTION_REGISTRY
310 std::cerr << t[j].toString(env) << " does not match " << fi_t[j].toString(env) << "\n";
311#endif
312 match = false;
313 break;
314 }
315 }
316 if (match) {
317 return i.fi;
318 }
319 }
320 }
321 return nullptr;
322}
323
324void Model::mergeStdLib(EnvI& env, Model* m) const {
325 for (const auto& it : _fnmap) {
326 for (const auto& cit : it.second) {
327 if (cit.fi->fromStdLib()) {
328 (void)m->registerFn(env, cit.fi);
329 }
330 }
331 }
332 m->sortFn();
333}
334
335void Model::sortFn() {
336 Model* m = this;
337 while (m->_parent != nullptr) {
338 m = m->_parent;
339 }
340 for (auto& it : m->_fnmap) {
341 // Sort all functions by type
342 std::sort(it.second.begin(), it.second.end());
343 }
344}
345
346void Model::fixFnMap() {
347 Model* m = this;
348 while (m->_parent != nullptr) {
349 m = m->_parent;
350 }
351 for (auto& it : m->_fnmap) {
352 for (auto& i : it.second) {
353 for (unsigned int j = 0; j < i.t.size(); j++) {
354 if (i.t[j].isunknown()) {
355 i.t[j] = i.fi->params()[j]->type();
356 }
357 }
358 }
359 }
360}
361
362void Model::checkFnOverloading(EnvI& env) {
363 Model* m = this;
364 while (m->_parent != nullptr) {
365 m = m->_parent;
366 }
367 for (auto& it : m->_fnmap) {
368 std::vector<FnEntry>& fs = it.second;
369 for (unsigned int i = 0; i < fs.size() - 1; i++) {
370 FunctionI* cur = fs[i].fi;
371 for (unsigned int j = i + 1; j < fs.size(); j++) {
372 FunctionI* cmp = fs[j].fi;
373 if (cur == cmp || cur->params().size() != cmp->params().size()) {
374 break;
375 }
376 bool allEqual = true;
377 for (unsigned int i = 0; i < cur->params().size(); i++) {
378 Type t1 = cur->params()[i]->type();
379 Type t2 = cmp->params()[i]->type();
380 t1.enumId(0);
381 t2.enumId(0);
382 if (t1 != t2) {
383 allEqual = false;
384 break;
385 }
386 }
387 if (allEqual) {
388 throw TypeError(env, cur->loc(),
389 "unsupported type of overloading. \nFunction/predicate with equivalent "
390 "signature defined in " +
391 cmp->loc().toString());
392 }
393 }
394 }
395 }
396}
397
398namespace {
399int match_idx(std::vector<FunctionI*>& matched, Expression*& botarg, EnvI& env,
400 const std::vector<Model::FnEntry>& v, const std::vector<Expression*>& args,
401 bool strictEnums) {
402 botarg = nullptr;
403 for (unsigned int i = 0; i < v.size(); i++) {
404 const std::vector<Type>& fi_t = v[i].t;
405#ifdef MZN_DEBUG_FUNCTION_REGISTRY
406 std::cerr << "try " << *v[i].fi;
407#endif
408 if (fi_t.size() == args.size()) {
409 bool match = true;
410 for (unsigned int j = 0; j < args.size(); j++) {
411 if (!env.isSubtype(args[j]->type(), fi_t[j], strictEnums)) {
412#ifdef MZN_DEBUG_FUNCTION_REGISTRY
413 std::cerr << args[j]->type().toString(env) << " does not match " << fi_t[j].toString(env)
414 << "\n";
415#endif
416 match = false;
417 break;
418 }
419 if (args[j]->type().isbot() && fi_t[j].bt() != Type::BT_TOP) {
420 botarg = args[j];
421 }
422 }
423 if (match) {
424 matched.push_back(v[i].fi);
425 if (botarg == nullptr) {
426 return static_cast<int>(i);
427 }
428 }
429 }
430 }
431 return -1;
432}
433} // namespace
434
435FunctionI* Model::matchFn(EnvI& env, const ASTString& id, const std::vector<Expression*>& args,
436 bool strictEnums) const {
437 if (id == constants().varRedef->id()) {
438 return constants().varRedef;
439 }
440 const Model* m = this;
441 while (m->_parent != nullptr) {
442 m = m->_parent;
443 }
444 auto it = m->_fnmap.find(id);
445 if (it == m->_fnmap.end()) {
446 return nullptr;
447 }
448 const std::vector<FnEntry>& v = it->second;
449 std::vector<FunctionI*> matched;
450 Expression* botarg;
451 (void)match_idx(matched, botarg, env, v, args, strictEnums);
452 if (matched.empty()) {
453 return nullptr;
454 }
455 if (matched.size() == 1) {
456 return matched[0];
457 }
458 Type t = matched[0]->ti()->type();
459 t.ti(Type::TI_PAR);
460 for (unsigned int i = 1; i < matched.size(); i++) {
461 if (!env.isSubtype(t, matched[i]->ti()->type(), strictEnums)) {
462 throw TypeError(env, botarg->loc(), "ambiguous overloading on return type of function");
463 }
464 }
465 return matched[0];
466}
467
468FunctionI* Model::matchFn(EnvI& env, Call* c, bool strictEnums, bool throwIfNotFound) const {
469 if (c->id() == constants().varRedef->id()) {
470 return constants().varRedef;
471 }
472 const Model* m = this;
473 while (m->_parent != nullptr) {
474 m = m->_parent;
475 }
476 auto it = m->_fnmap.find(c->id());
477 if (it == m->_fnmap.end()) {
478 if (throwIfNotFound) {
479 std::ostringstream oss;
480 oss << "no function or predicate with name `";
481 oss << c->id() << "' found";
482
483 ASTString mostSimilar;
484 int minEdits = 3;
485 for (const auto& decls : m->_fnmap) {
486 if (std::abs(static_cast<int>(c->id().size()) - static_cast<int>(decls.first.size())) <=
487 3) {
488 int edits = c->id().levenshteinDistance(decls.first);
489 if (edits < minEdits && edits < std::min(c->id().size(), decls.first.size())) {
490 minEdits = edits;
491 mostSimilar = decls.first;
492 }
493 }
494 }
495 if (mostSimilar.size() > 0) {
496 oss << ", did you mean `" << mostSimilar << "'?";
497 }
498 throw TypeError(env, c->loc(), oss.str());
499 }
500 return nullptr;
501 }
502 const std::vector<FnEntry>& v = it->second;
503 std::vector<FunctionI*> matched;
504 Expression* botarg = nullptr;
505 for (const auto& i : v) {
506 const std::vector<Type>& fi_t = i.t;
507#ifdef MZN_DEBUG_FUNCTION_REGISTRY
508 std::cerr << "try " << *i.fi;
509#endif
510 if (fi_t.size() == c->argCount()) {
511 bool match = true;
512 for (unsigned int j = 0; j < c->argCount(); j++) {
513 if (!env.isSubtype(c->arg(j)->type(), fi_t[j], strictEnums)) {
514#ifdef MZN_DEBUG_FUNCTION_REGISTRY
515 std::cerr << c->arg(j)->type().toString(env) << " does not match "
516 << fi_t[j].toString(env) << "\n";
517 std::cerr << "Wrong argument is " << *c->arg(j);
518#endif
519 match = false;
520 break;
521 }
522 if (c->arg(j)->type().isbot() && fi_t[j].bt() != Type::BT_TOP) {
523 botarg = c->arg(j);
524 }
525 }
526 if (match) {
527 if (botarg != nullptr) {
528 matched.push_back(i.fi);
529 } else {
530 return i.fi;
531 }
532 }
533 }
534 }
535 if (matched.empty()) {
536 if (throwIfNotFound) {
537 std::ostringstream oss;
538 oss << "no function or predicate with this signature found: `";
539 oss << c->id() << "(";
540 for (unsigned int i = 0; i < c->argCount(); i++) {
541 oss << c->arg(i)->type().toString(env);
542 if (i < c->argCount() - 1) {
543 oss << ",";
544 }
545 }
546 oss << ")'\n";
547 oss << "Cannot use the following functions or predicates with the same identifier:\n";
548 Printer pp(oss, 0, false, &env);
549 for (const auto& i : v) {
550 const std::vector<Type>& fi_t = i.t;
551 Expression* body = i.fi->e();
552 i.fi->e(nullptr);
553 pp.print(i.fi);
554 i.fi->e(body);
555 if (fi_t.size() == c->argCount()) {
556 for (unsigned int j = 0; j < c->argCount(); j++) {
557 if (!env.isSubtype(c->arg(j)->type(), fi_t[j], strictEnums)) {
558 oss << " (argument " << (j + 1) << " expects type " << fi_t[j].toString(env);
559 oss << ", but type " << c->arg(j)->type().toString(env) << " given)\n";
560 }
561 if (c->arg(j)->type().isbot() && fi_t[j].bt() != Type::BT_TOP) {
562 botarg = c->arg(j);
563 }
564 }
565 } else {
566 oss << " (requires " << i.fi->params().size() << " argument"
567 << (i.fi->params().size() == 1 ? "" : "s") << ", but " << c->argCount()
568 << " given)\n";
569 }
570 }
571 throw TypeError(env, c->loc(), oss.str());
572 }
573 return nullptr;
574 }
575 if (matched.size() == 1) {
576 return matched[0];
577 }
578 Type t = matched[0]->ti()->type();
579 t.ti(Type::TI_PAR);
580 for (unsigned int i = 1; i < matched.size(); i++) {
581 if (!env.isSubtype(t, matched[i]->ti()->type(), strictEnums)) {
582 throw TypeError(env, botarg->loc(), "ambiguous overloading on return type of function");
583 }
584 }
585 return matched[0];
586}
587
588namespace {
589int first_overloaded(EnvI& env, const std::vector<Model::FnEntry>& v_f, int i_f) {
590 int first_i_f = i_f;
591 for (; (first_i_f--) != 0;) {
592 // find first instance overloaded on subtypes
593 if (v_f[first_i_f].t.size() != v_f[i_f].t.size()) {
594 break;
595 }
596 bool allSubtypes = true;
597 for (unsigned int i = 0; i < v_f[first_i_f].t.size(); i++) {
598 if (!env.isSubtype(v_f[first_i_f].t[i], v_f[i_f].t[i], false)) {
599 allSubtypes = false;
600 break;
601 }
602 }
603 if (!allSubtypes) {
604 break;
605 }
606 }
607 return first_i_f + 1;
608}
609} // namespace
610
611bool Model::sameOverloading(EnvI& env, const std::vector<Expression*>& args, FunctionI* f,
612 FunctionI* g) const {
613 const Model* m = this;
614 while (m->_parent != nullptr) {
615 m = m->_parent;
616 }
617 auto it_f = m->_fnmap.find(f->id());
618 auto it_g = m->_fnmap.find(g->id());
619 assert(it_f != m->_fnmap.end());
620 assert(it_g != m->_fnmap.end());
621 const std::vector<FnEntry>& v_f = it_f->second;
622 const std::vector<FnEntry>& v_g = it_g->second;
623
624 std::vector<FunctionI*> dummyMatched;
625 Expression* dummyBotarg;
626 int i_f = match_idx(dummyMatched, dummyBotarg, env, v_f, args, true);
627 if (i_f == -1) {
628 return false;
629 }
630 int i_g = match_idx(dummyMatched, dummyBotarg, env, v_g, args, true);
631 if (i_g == -1) {
632 return false;
633 }
634 assert(i_f < v_f.size());
635 assert(i_g < v_g.size());
636 unsigned int first_i_f = first_overloaded(env, v_f, i_f);
637 unsigned int first_i_g = first_overloaded(env, v_g, i_g);
638 if (i_f - first_i_f != i_g - first_i_g) {
639 // not the same number of overloaded versions
640 return false;
641 }
642 for (; first_i_f <= i_f; first_i_f++, first_i_g++) {
643 if (!(v_f[first_i_f].t == v_g[first_i_g].t)) {
644 // one of the overloaded versions does not agree in the types
645 return false;
646 }
647 }
648 return true;
649}
650
651FunctionI* Model::matchRevMap(EnvI& env, const Type& t0) const {
652 const Model* m = this;
653 while (m->_parent != nullptr) {
654 m = m->_parent;
655 }
656 Type t = t0;
657 t.enumId(0);
658 auto it = _revmapmap.find(t.toInt());
659 if (it != _revmapmap.end()) {
660 return it->second;
661 }
662 return nullptr;
663}
664
665Item*& Model::operator[](unsigned int i) {
666 assert(i < _items.size());
667 return _items[i];
668}
669const Item* Model::operator[](unsigned int i) const {
670 assert(i < _items.size());
671 return _items[i];
672}
673unsigned int Model::size() const { return static_cast<unsigned int>(_items.size()); }
674
675std::vector<Item*>::iterator Model::begin() { return _items.begin(); }
676
677std::vector<Item*>::const_iterator Model::begin() const { return _items.begin(); }
678
679std::vector<Item*>::iterator Model::end() { return _items.end(); }
680
681std::vector<Item*>::const_iterator Model::end() const { return _items.end(); }
682
683void Model::compact() {
684 struct {
685 bool operator()(const Item* i) { return i->removed(); }
686 } isremoved;
687 _items.erase(remove_if(_items.begin(), _items.end(), isremoved), _items.end());
688}
689
690} // namespace MiniZinc