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