A set of benchmarks to compare a new prototype MiniZinc implementation
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#ifndef __MINIZINC_MODEL_HH__
13#define __MINIZINC_MODEL_HH__
14
15#include <minizinc/ast.hh>
16#include <minizinc/gc.hh>
17
18#include <iterator>
19#include <unordered_map>
20#include <unordered_set>
21#include <vector>
22
23namespace MiniZinc {
24
25class VarDeclIterator;
26class ConstraintIterator;
27class FunctionIterator;
28
29class CopyMap;
30class EnvI;
31
32/// A MiniZinc model
33class Model {
34 friend class GC;
35 friend class FZNSolverInstance;
36 friend Model* copy(EnvI& env, CopyMap& cm, Model* m, bool isFlatModel);
37
38protected:
39 /// Previous model in root set list
40 Model* _roots_prev;
41 /// Next model in root set list
42 Model* _roots_next;
43
44 struct FnEntry {
45 std::vector<Type> t;
46 FunctionI* fi;
47 bool isPolymorphic;
48 FnEntry(FunctionI* fi0);
49 bool operator<(const FnEntry&) const;
50 static bool compare(const FnEntry& e1, const FnEntry& e2);
51 };
52
53 /// Add all instances of polymorphic entry \a fe to \a entries
54 void addPolymorphicInstances(Model::FnEntry& fe, std::vector<FnEntry>& entries);
55
56 /// Type of map from identifiers to function declarations
57 typedef ASTStringMap<std::vector<FnEntry> >::t FnMap;
58 /// Map from identifiers to function declarations
59 FnMap fnmap;
60
61 /// Type of map from Type (represented as int) to reverse mapper functions
62 typedef std::unordered_map<int, FunctionI*> RevMapperMap;
63 /// Map from Type (represented as int) to reverse mapper functions
64 RevMapperMap revmapmap;
65
66 /// Filename of the model
67 ASTString _filename;
68 /// Path of the model
69 ASTString _filepath;
70 /// Parent model if model was included
71 Model* _parent;
72 /// Items in the model
73 std::vector<Item*> _items;
74 /// Pointer to the solve item
75 SolveI* _solveItem;
76 /// Pointer to the output item
77 OutputI* _outputItem;
78 /// File-level documentation comment
79 std::string _docComment;
80
81 /// Store some declarations
82 struct FnDecls {
83 using TCheckedDecl = std::pair<bool, FunctionI*>; // bool means that it was checked
84 TCheckedDecl bounds_disj = {false, nullptr}; // SCIP's bound disjunction
85 } fnDecls;
86
87public:
88 /// Construct empty model
89 Model(void);
90 /// Destructor
91 ~Model(void);
92
93 /// Add \a i to the model
94 void addItem(Item* i);
95
96 /// Get parent model
97 Model* parent(void) const { return _parent; }
98 /// Set parent model to \a p
99 void setParent(Model* p) {
100 assert(_parent == NULL);
101 _parent = p;
102 }
103
104 /// Get file name
105 ASTString filename(void) const { return _filename; }
106 /// Get file path
107 ASTString filepath(void) const { return _filepath; }
108 /// Set file name
109 void setFilename(const std::string& f) {
110 assert(_filename.size() == 0);
111 _filename = ASTString(f);
112 }
113 /// Set file path
114 void setFilepath(const std::string& f) {
115 assert(_filepath.size() == 0);
116 _filepath = ASTString(f);
117 }
118
119 /// Register a builtin function item
120 void registerFn(EnvI& env, FunctionI* fi);
121 /// Sort functions by type
122 void sortFn(void);
123 /// Check that registered functions do not clash wrt overloading
124 void checkFnOverloading(EnvI& env);
125 /// Fix function table after type checking
126 void fixFnMap(void);
127 /// Return function declaration for \a id matching \a args
128 FunctionI* matchFn(EnvI& env, const ASTString& id, const std::vector<Expression*>& args,
129 bool strictEnums) const;
130 /// Return function declaration for \a id matching types \a t
131 FunctionI* matchFn(EnvI& env, const ASTString& id, const std::vector<Type>& t, bool strictEnums);
132 /// Return function declaration matching call \a c
133 FunctionI* matchFn(EnvI& env, Call* c, bool strictEnums) const;
134 /// Return function declaration for reverse mapper for type \a t
135 FunctionI* matchRevMap(EnvI& env, const Type& t) const;
136 /// Merge all builtin functions into \a m
137 void mergeStdLib(EnvI& env, Model* m) const;
138
139 /// Return item \a i
140 Item*& operator[](int i);
141 /// Return item \a i
142 const Item* operator[](int i) const;
143 /// Return number of items
144 unsigned int size(void) const;
145
146 typedef std::vector<Item*>::iterator iterator;
147 typedef std::vector<Item*>::const_iterator const_iterator;
148
149 /// Iterator for beginning of items
150 iterator begin(void);
151 /// Iterator for beginning of items
152 const_iterator begin(void) const;
153 /// Iterator for end of items
154 iterator end(void);
155 /// Iterator for end of items
156 const_iterator end(void) const;
157
158 ConstraintIterator begin_constraints(void);
159 ConstraintIterator end_constraints(void);
160 VarDeclIterator begin_vardecls(void);
161 VarDeclIterator end_vardecls(void);
162 FunctionIterator begin_functions(void);
163 FunctionIterator end_functions(void);
164
165 SolveI* solveItem(void);
166
167 OutputI* outputItem(void);
168 void setOutputItem(OutputI* oi);
169
170 /// Add a file-level documentation comment
171 void addDocComment(std::string s) { _docComment += s; }
172
173 /// Return the file-level documentation comment
174 const std::string& docComment(void) const { return _docComment; }
175
176 /// Remove all items marked as removed
177 void compact(void);
178
179 /// Get the stored function declarations
180 FnDecls& getFnDecls() { return fnDecls; }
181};
182
183class VarDeclIterator {
184 Model* _model;
185 Model::iterator _it;
186
187public:
188 typedef Model::iterator::difference_type difference_type;
189 typedef Model::iterator::value_type value_type;
190 typedef VarDeclI& reference;
191 typedef VarDeclI* pointer;
192 typedef std::forward_iterator_tag iterator_category;
193
194 VarDeclIterator() {}
195 VarDeclIterator(const VarDeclIterator& vi) : _it(vi._it) {}
196 VarDeclIterator(Model* model, const Model::iterator& it) : _model(model), _it(it) {
197 while (_it != _model->end() && !(*_it)->isa<VarDeclI>()) {
198 ++_it;
199 }
200 }
201 ~VarDeclIterator() {}
202
203 VarDeclIterator& operator=(const VarDeclIterator& vi) {
204 if (this != &vi) {
205 _it = vi._it;
206 }
207 return *this;
208 }
209 bool operator==(const VarDeclIterator& vi) const { return _it == vi._it; }
210 bool operator!=(const VarDeclIterator& vi) const { return _it != vi._it; }
211 VarDeclIterator& operator++() {
212 do {
213 ++_it;
214 } while (_it != _model->end() && !(*_it)->isa<VarDeclI>());
215 return *this;
216 }
217
218 reference operator*() const { return *(*_it)->cast<VarDeclI>(); }
219 pointer operator->() const { return (*_it)->cast<VarDeclI>(); }
220};
221
222class ConstraintIterator {
223 Model* _model;
224 Model::iterator _it;
225
226public:
227 typedef Model::iterator::difference_type difference_type;
228 typedef Model::iterator::value_type value_type;
229 typedef ConstraintI& reference;
230 typedef ConstraintI* pointer;
231 typedef std::forward_iterator_tag iterator_category;
232
233 ConstraintIterator() {}
234 ConstraintIterator(const ConstraintIterator& vi) : _it(vi._it) {}
235 ConstraintIterator(Model* model, const Model::iterator& it) : _model(model), _it(it) {
236 while (_it != _model->end() && !(*_it)->isa<ConstraintI>()) {
237 ++_it;
238 }
239 }
240 ~ConstraintIterator() {}
241
242 ConstraintIterator& operator=(const ConstraintIterator& vi) {
243 if (this != &vi) {
244 _it = vi._it;
245 }
246 return *this;
247 }
248 bool operator==(const ConstraintIterator& vi) const { return _it == vi._it; }
249 bool operator!=(const ConstraintIterator& vi) const { return _it != vi._it; }
250 ConstraintIterator& operator++() {
251 do {
252 ++_it;
253 } while (_it != _model->end() && !(*_it)->isa<ConstraintI>());
254 return *this;
255 }
256
257 reference operator*() const { return *(*_it)->cast<ConstraintI>(); }
258 pointer operator->() const { return (*_it)->cast<ConstraintI>(); }
259};
260
261class FunctionIterator {
262 Model* _model;
263 Model::iterator _it;
264
265public:
266 typedef Model::iterator::difference_type difference_type;
267 typedef Model::iterator::value_type value_type;
268 typedef FunctionI& reference;
269 typedef FunctionI* pointer;
270 typedef std::forward_iterator_tag iterator_category;
271
272 FunctionIterator() {}
273 FunctionIterator(const FunctionIterator& vi) : _it(vi._it) {}
274 FunctionIterator(Model* model, const Model::iterator& it) : _model(model), _it(it) {
275 while (_it != _model->end() && !(*_it)->isa<FunctionI>()) {
276 ++_it;
277 }
278 }
279 ~FunctionIterator() {}
280
281 FunctionIterator& operator=(const FunctionIterator& vi) {
282 if (this != &vi) {
283 _it = vi._it;
284 }
285 return *this;
286 }
287 bool operator==(const FunctionIterator& vi) const { return _it == vi._it; }
288 bool operator!=(const FunctionIterator& vi) const { return _it != vi._it; }
289 FunctionIterator& operator++() {
290 do {
291 ++_it;
292 } while (_it != _model->end() && !(*_it)->isa<FunctionI>());
293 return *this;
294 }
295
296 reference operator*() const { return *(*_it)->cast<FunctionI>(); }
297 pointer operator->() const { return (*_it)->cast<FunctionI>(); }
298};
299
300class EnvI;
301
302/// Environment
303class Env {
304private:
305 EnvI* e;
306
307public:
308 Env(Model* m = NULL, std::ostream& outstream = std::cout, std::ostream& errstream = std::cerr);
309 ~Env(void);
310
311 Model* model(void);
312 void model(Model* m);
313 Model* flat(void);
314 void swap();
315 Model* output(void);
316 EnvI& envi(void);
317 const EnvI& envi(void) const;
318 std::ostream& dumpErrorStack(std::ostream& os);
319 const std::vector<std::string>& warnings(void);
320 void clearWarnings(void);
321 unsigned int maxCallStack(void) const;
322 std::ostream& evalOutput(std::ostream& os);
323};
324
325class CallStackItem {
326public:
327 EnvI& env;
328 CallStackItem(EnvI& env0, Expression* e);
329 CallStackItem(EnvI& env0, Id* ident, IntVal i);
330 ~CallStackItem(void);
331};
332
333/// Visitor for model items
334class ItemVisitor {
335public:
336 /// Enter model
337 bool enterModel(Model* m) { return true; }
338 /// Enter item
339 bool enter(Item* m) { return true; }
340 /// Visit include item
341 void vIncludeI(IncludeI*) {}
342 /// Visit variable declaration
343 void vVarDeclI(VarDeclI*) {}
344 /// Visit assign item
345 void vAssignI(AssignI*) {}
346 /// Visit constraint item
347 void vConstraintI(ConstraintI*) {}
348 /// Visit solve item
349 void vSolveI(SolveI*) {}
350 /// Visit output item
351 void vOutputI(OutputI*) {}
352 /// Visit function item
353 void vFunctionI(FunctionI*) {}
354};
355
356/// Iterator over items in a model and all its included models
357template <class I>
358class ItemIter {
359protected:
360 I& iter;
361
362public:
363 ItemIter(I& iter0) : iter(iter0) {}
364 void run(Model* m) {
365 std::unordered_set<Model*> seen;
366 std::vector<Model*> models;
367 models.push_back(m);
368 seen.insert(m);
369 while (!models.empty()) {
370 Model* cm = models.back();
371 models.pop_back();
372 if (!iter.enterModel(cm)) continue;
373 std::vector<Model*> includedModels;
374 for (unsigned int i = 0; i < cm->size(); i++) {
375 if ((*cm)[i]->removed()) continue;
376 if (!iter.enter((*cm)[i])) continue;
377 switch ((*cm)[i]->iid()) {
378 case Item::II_INC:
379 if (seen.find((*cm)[i]->cast<IncludeI>()->m()) == seen.end()) {
380 includedModels.push_back((*cm)[i]->cast<IncludeI>()->m());
381 seen.insert((*cm)[i]->cast<IncludeI>()->m());
382 }
383 iter.vIncludeI((*cm)[i]->cast<IncludeI>());
384 break;
385 case Item::II_VD:
386 iter.vVarDeclI((*cm)[i]->cast<VarDeclI>());
387 break;
388 case Item::II_ASN:
389 iter.vAssignI((*cm)[i]->cast<AssignI>());
390 break;
391 case Item::II_CON:
392 iter.vConstraintI((*cm)[i]->cast<ConstraintI>());
393 break;
394 case Item::II_SOL:
395 iter.vSolveI((*cm)[i]->cast<SolveI>());
396 break;
397 case Item::II_OUT:
398 iter.vOutputI((*cm)[i]->cast<OutputI>());
399 break;
400 case Item::II_FUN:
401 iter.vFunctionI((*cm)[i]->cast<FunctionI>());
402 break;
403 }
404 }
405 for (unsigned int i = static_cast<unsigned int>(includedModels.size()); i--;) {
406 models.push_back(includedModels[i]);
407 }
408 }
409 }
410};
411
412/// Run iterator \a i over all items of model \a m
413template <class I>
414void iterItems(I& i, Model* m) {
415 ItemIter<I>(i).run(m);
416}
417
418} // namespace MiniZinc
419
420#endif