Generated on for Gecode by doxygen 1.17.0
resolve.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
35
36namespace Gecode { namespace Instance {
37
38 namespace {
39
41 class Definition {
42 public:
44 std::string name;
46 Seq<const Stmt*> repeats;
47 };
48
50 class List {
51 public:
53 const Stmt* repeat;
55 Seq<const Stmt*> repeats;
56 };
57
60 class Bound {
61 public:
63 std::string name;
65 const Stmt* records;
66 };
67
69 bool
70 is_prefix(const Seq<const Stmt*>& a, const Seq<const Stmt*>& b) {
71 if (a.size() > b.size())
72 return false;
73 for (int k=0; k<a.size(); k++)
74 if (a[k] != b[k])
75 return false;
76 return true;
77 }
78
80 bool
81 contains(const Seq<const Stmt*>& rs, const Stmt* r) {
82 for (const Stmt* x : rs)
83 if (x == r)
84 return true;
85 return false;
86 }
87
94 bool
95 whole_array(const Expr& e, int k) {
96 if (e.kind == Expr::Kind::COMPREHENSION)
97 return k == 0;
98 return (e.kind == Expr::Kind::CALL) && ((e.s == "size") || (e.s == "defined"));
99 }
100
108 class Resolver {
109 public:
111 explicit Resolver(const std::string& o)
112 : origin(o), stmt(nullptr) {}
114 void run(Block& b) {
115 define(b);
116 check_lists();
117 visit(b);
118 }
119 private:
121 std::string origin;
123 Seq<Definition> definitions;
125 Seq<List> lists;
127 Seq<const Stmt*> repeats;
129 Stmt* stmt;
131 Seq<Bound> bound;
132
133 [[noreturn]] void fail(const std::string& m) const {
134 fail_at(origin, stmt->line, m);
135 }
137 void define(const std::string& n) {
138 if (n.empty() || (n == "_"))
139 return;
140 Definition d;
141 d.name = n;
142 d.repeats = repeats;
143 definitions.push(std::move(d));
144 }
146 void define(const Pattern& p) {
147 for (const Pattern::Item& it : p.items)
148 if (it.kind == Pattern::Item::Kind::CAP)
149 define(it.text);
150 }
152 void define(const Block& b) {
153 for (const std::unique_ptr<Stmt>& s : b) {
154 switch (s->kind) {
157 define(s->name);
158 break;
160 define(s->pattern);
161 break;
163 define(s->store);
164 if (!s->list.empty() || !s->each.empty()) {
165 List l;
166 l.repeat = s.get();
167 l.repeats = repeats;
168 lists.push(std::move(l));
169 }
170 repeats.push(s.get());
171 define(s->body);
172 repeats.pop();
173 break;
175 define(s->store);
176 for (const Arm& a : s->arms) {
177 define(a.pattern);
178 define(a.body);
179 }
180 break;
181 case Stmt::Kind::IF:
182 define(s->body);
183 define(s->orelse);
184 break;
186 define(s->body);
187 break;
188 default:
189 break;
190 }
191 }
192 }
194 bool names_records(const std::string& n) const {
195 for (const List& l : lists)
196 if ((l.repeat->list == n) || (l.repeat->each == n))
197 return true;
198 return false;
199 }
202 void check_name(const std::string& n, int i) const {
203 const Stmt* r = lists[i].repeat;
204 if (n.empty())
205 return;
206 for (int j=0; j<i; j++)
207 if ((lists[j].repeat->list == n) || (lists[j].repeat->each == n))
208 fail_at(origin, r->line, "'" + n + "' already names records");
209 for (const Definition& d : definitions)
210 if (d.name == n)
211 fail_at(origin, r->line, "'" + n + "' names records, so it cannot also be defined");
212 }
215 void check_lists(void) const {
216 for (int i=0; i<lists.size(); i++) {
217 const Stmt* r = lists[i].repeat;
218 check_name(r->list, i);
219 if (r->each == r->list)
220 fail_at(origin, r->line, "'" + r->each + "' cannot name both the list and each record");
221 check_name(r->each, i);
222 }
223 }
225 const List* find_list(const std::string& n) const {
226 for (const List& l : lists)
227 if (l.repeat->list == n)
228 return &l;
229 return nullptr;
230 }
232 const List* find_each(const std::string& n) const {
233 for (const List& l : lists)
234 if (l.repeat->each == n)
235 return &l;
236 return nullptr;
237 }
239 static const std::string& records_name(const Stmt* r) {
240 return r->list.empty() ? r->each : r->list;
241 }
243 bool is_bound(const std::string& n) const {
244 for (const Bound& b : bound)
245 if (b.name == n)
246 return true;
247 return false;
248 }
251 const List* nested_list(const Stmt* r, const std::string& n) const {
252 const List* m = find_list(n);
253 if ((m == nullptr) || !contains(m->repeats, r))
254 return nullptr;
255 if (m->repeats.back() != r)
256 fail("'" + n + "' is inside a repeat without a list name in the records of '" + records_name(r) +
257 "'; name that list with 'as' to reach it");
258 if (contains(repeats, m->repeat))
259 fail("'" + n + "' cannot be used inside its own repeat");
260 return m;
261 }
263 std::string fields(const Stmt* r) const {
264 Seq<std::string> f;
265 for (const Definition& d : definitions)
266 if (contains(d.repeats, r))
267 f.push(d.name);
268 for (const List& l : lists)
269 if (!l.repeats.empty() && (l.repeats.back() == r) && !l.repeat->list.empty())
270 f.push(l.repeat->list);
271 std::string s;
272 for (int i=0; i<f.size(); i++) {
273 bool seen = false;
274 for (int j=0; j<i; j++)
275 seen = seen || (f[j] == f[i]);
276 if (!seen)
277 s += (s.empty() ? "" : ", ") + f[i];
278 }
279 return s;
280 }
283 std::string example(const Stmt* r, bool list) const {
284 std::string f = fields(r);
285 size_t c = f.find(',');
286 std::string x = (list || r->each.empty()) ? r->list + "[0]" : r->each;
287 return f.empty() ? x : x + "." + ((c == std::string::npos) ? f : f.substr(0, c));
288 }
290 static int position(const Seq<const Stmt*>& rs, const Stmt* r) {
291 for (int k=0; k<rs.size(); k++)
292 if (rs[k] == r)
293 return k;
294 return -1;
295 }
299 bool incomplete(const Definition& d, const Stmt* r) const {
300 int common = 0;
301 while ((common < d.repeats.size()) && (common < repeats.size()) && (d.repeats[common] == repeats[common]))
302 common++;
303 return common > position(d.repeats, r) + 1;
304 }
306 void require_field(const Stmt* r, const std::string& f) const {
307 bool inside = false, outside = false;
308 for (const Definition& d : definitions)
309 if (d.name == f) {
310 inside = inside || contains(d.repeats, r);
311 outside = outside || !contains(d.repeats, r);
312 }
313 if (!inside) {
314 std::string known = fields(r);
315 fail("the records of '" + records_name(r) + "' have no field '" + f + "'" +
316 (known.empty() ? std::string(" (they have none)") : " (they have " + known + ")"));
317 }
318 if (outside)
319 fail("'" + f + "' is defined inside and outside the repeat of '" + records_name(r) +
320 "', so it cannot be a field of its records");
321 for (const Definition& d : definitions)
322 if ((d.name == f) && incomplete(d, r))
323 fail("the field '" + f + "' cannot be used inside the repeat that reads it");
324 }
326 void require_value(const Expr& e) const {
327 const Stmt* r = e.records;
328 if (r == nullptr)
329 return;
330 if (e.open == 0)
331 fail("a record of '" + records_name(r) + "' is not a value; use one of its fields, as in '" +
332 example(r, false) + "'");
333 fail("'" + r->list + "' is a list of records, not a value; use size(" + r->list +
334 "), an index, or a field of a record, as in '" + example(r, true) + "'");
335 }
336
338 void visit(Block& b) {
339 for (std::unique_ptr<Stmt>& s : b) {
340 statement(*s);
341 bool repeat = (s->kind == Stmt::Kind::REPEAT);
342 if (repeat)
343 repeats.push(s.get());
344 visit(s->body);
345 if (repeat)
346 repeats.pop();
347 visit(s->orelse);
348 for (Arm& a : s->arms)
349 visit(a.body);
350 }
351 }
353 void statement(Stmt& s) {
354 stmt = &s;
355 type(s.type);
356 pattern(s.pattern);
357 for (Arm& a : s.arms)
358 pattern(a.pattern);
359 for (std::unique_ptr<Expr>& d : s.dims)
360 value(*d);
361 if (s.expr)
362 value(*s.expr);
363 if (s.sentinel)
364 value(*s.sentinel);
365 if (s.offset)
366 value(*s.offset);
367 if (s.kind == Stmt::Kind::CHECK)
368 check_chain(s);
369 }
371 void type(Type& t) {
372 if (t.lo)
373 value(*t.lo);
374 if (t.hi)
375 value(*t.hi);
376 }
378 void pattern(Pattern& p) {
379 for (Pattern::Item& it : p.items)
380 type(it.type);
381 }
384 bool lifting(void) const {
385 return stmt->kind == Stmt::Kind::CHECK;
386 }
389 void check_chain(const Stmt& s) const {
390 int deepest = 0;
391 for (int i=1; i<s.records.size(); i++)
392 if (s.records[i].repeats.size() > s.records[deepest].repeats.size())
393 deepest = i;
394 for (int i=0; i<s.records.size(); i++)
395 if (!is_prefix(s.records[i].repeats, s.records[deepest].repeats))
396 fail("a check can only range over the records of one repeat, but '" +
397 s.records[std::min(i, deepest)].label + "' and '" + s.records[std::max(i, deepest)].label +
398 "' are defined in different repeats");
399 }
400
402 void value(Expr& e) {
403 resolve(e, false);
404 require_value(e);
405 }
407 void resolve(Expr& e, bool whole) {
408 switch (e.kind) {
409 case Expr::Kind::NAME:
410 name(e, whole);
411 break;
413 field(e);
414 break;
416 index(e);
417 break;
419 comprehension(e);
420 break;
421 case Expr::Kind::CALL:
422 call(e);
423 break;
424 default:
425 for (std::unique_ptr<Expr>& a : e.args)
426 value(*a);
427 break;
428 }
429 }
431 void name(Expr& e, bool whole) {
432 for (int k=bound.size(); k--; )
433 if (bound[k].name == e.s) {
434 e.records = bound[k].records;
435 return;
436 }
437 if (const List* l = find_list(e.s))
438 list(e, *l);
439 else if (const List* r = find_each(e.s))
440 record_name(e, *r);
441 else if (lifting() && !whole)
442 e.record = record(e.s);
443 }
445 Seq<const Stmt*> beyond(const Seq<const Stmt*>& d) const {
446 int common = 0;
447 while ((common < d.size()) && (common < repeats.size()) && (d[common] == repeats[common]))
448 common++;
449 Seq<const Stmt*> r;
450 for (int k=common; k<d.size(); k++)
451 r.push(d[k]);
452 return r;
453 }
455 void list(Expr& e, const List& l) {
456 e.records = l.repeat;
457 e.open = 1;
458 if (contains(repeats, l.repeat))
459 fail("'" + e.s + "' cannot be used inside its own repeat");
460 if (beyond(l.repeats).empty())
461 return;
462 // One list for each record of the repeat around it
463 const std::string& outer = l.repeats.back()->each;
464 fail("'" + e.s + "' is a list in each record of the repeat around it; " +
465 (outer.empty() ? "name each of these records with 'each' and use its field '" + e.s + "'"
466 : "use '" + outer + "." + e.s + "'"));
467 }
474 void record_name(Expr& e, const List& l) {
475 e.records = l.repeat;
476 if (contains(repeats, l.repeat))
477 return;
478 if (!lifting())
479 fail("'" + e.s + "' is each record of a repeat, so only checks can use it outside that repeat");
480 Seq<const Stmt*> o = beyond(l.repeats);
481 o.push(l.repeat);
482 e.record = lift(record_starts(l.repeat->id), o, e.s);
483 }
485 void field(Expr& e) {
486 Expr& base = *e.args[0];
487 resolve(base, false);
488 const Stmt* r = base.records;
489 const std::string& f = e.s;
490 if (r == nullptr)
491 fail("only records have fields such as '." + f + "'; to name each record of a repeat, write "
492 "'repeat n as nodes { each node ... }' and use 'node." + f + "' or 'nodes[0]." + f + "'");
493 if (base.open > 0)
494 fail("'" + r->list + "' is a list of records, so '." + f + "' needs one of them: use '" + r->list + "[i]." +
495 f + "', or " + (r->each.empty() ? "name each record with 'each' in the repeat and use its field"
496 : "'" + r->each + "." + f + "' for each record"));
497 if (const List* m = nested_list(r, f)) {
498 e.records = m->repeat;
499 e.open = 1;
500 } else {
501 require_field(r, f);
502 }
503 }
505 void index(Expr& e) {
506 Expr& a = *e.args[0];
507 resolve(a, false);
508 value(*e.args[1]);
509 if (a.records == nullptr)
510 return;
511 if (a.open == 0)
512 fail("a record of '" + records_name(a.records) + "' cannot be indexed; use one of its fields, as in '" +
513 example(a.records, false) + "'");
514 e.records = a.records;
515 }
517 const Stmt* elements(const Expr& a) const {
518 if (a.records != nullptr)
519 return a.records;
520 if (a.kind == Expr::Kind::FIELD)
521 return outermost(a.s, a.args[0]->records);
522 if ((a.kind != Expr::Kind::NAME) || is_bound(a.s))
523 return nullptr;
524 return outermost(a.s, nullptr);
525 }
533 const Stmt* outermost(const std::string& n, const Stmt* r) const {
534 const Stmt* o = nullptr;
535 bool found = false;
536 for (const Definition& d : definitions)
537 if (d.name == n) {
538 int k = (r == nullptr) ? d.repeats.size() - beyond(d.repeats).size() : position(d.repeats, r) + 1;
539 const Stmt* x = (k < d.repeats.size()) ? d.repeats[k] : nullptr;
540 if (found && (x != o))
541 return nullptr;
542 o = x;
543 found = true;
544 }
545 return o;
546 }
548 void comprehension(Expr& e) {
549 if (names_records(e.var))
550 fail("'" + e.var + "' is bound by a comprehension but names records");
551 Expr& a = *e.args[0];
552 resolve(a, true);
553 if ((a.records != nullptr) && (a.open == 0))
554 fail("a record of '" + records_name(a.records) + "' is not a list; use one of its fields");
555 e.elements = elements(a);
556 Bound b;
557 b.name = e.var;
558 b.records = a.records;
559 bound.push(b);
560 value(*e.args[1]);
561 bound.pop();
562 }
564 void call(Expr& e) {
565 for (int k=0; k<e.args.size(); k++) {
566 Expr& a = *e.args[k];
567 resolve(a, whole_array(e, k));
568 bool counted = (e.s == "size") || (e.s == "count") || (e.s == "defined");
569 if (!counted || (a.open == 0))
570 require_value(a);
571 }
572 }
573
581 int record(const std::string& n) {
582 bool found = false;
583 Seq<const Stmt*> outside;
584 for (const Definition& d : definitions) {
585 if (d.name != n)
586 continue;
587 Seq<const Stmt*> o = beyond(d.repeats);
588 if (found && !(is_prefix(o, outside) && is_prefix(outside, o)))
589 fail("'" + n + "' is defined in several repeats, or inside and outside a repeat, so "
590 "a check here cannot range over its records");
591 outside = std::move(o);
592 found = true;
593 }
594 if (outside.empty())
595 return -1;
596 return lift(n, outside, n);
597 }
601 int lift(const std::string& n, const Seq<const Stmt*>& rs, const std::string& label) {
602 Seq<Record>& records = stmt->records;
603 for (int i=0; i<records.size(); i++)
604 if ((records[i].name == n) && (records[i].repeats.size() == rs.size()))
605 return i;
606 Record r;
607 r.name = n;
608 r.label = label;
609 r.repeats = rs;
610 r.starts = record_starts(rs.back()->id);
611 records.push(std::move(r));
612 return records.size()-1;
613 }
614 };
615
616 }
617
618 void
619 resolve(Block& b, const std::string& origin) {
620 Resolver(origin).run(b);
621 }
622
623}}
624
625// STATISTICS: instance-any
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
Growable array on the Gecode heap.
Definition impl.hpp:118
unsigned int size(void) const
Return size (cardinality) of set.
virtual bool run(void)
Run the test.
Definition instance.cpp:123
Reading instance files described by reader specs.
void resolve(Block &b, const std::string &origin)
Resolve the names in the expressions of b, the body of a spec from origin.
Definition resolve.cpp:619
std::string record_starts(int id)
Return the name of the record starts of the repeat numbered id.
Definition impl.hpp:511
void fail_at(const std::string &origin, int line, const std::string &m)
Throw an error with message m for line line of the spec from origin.
Definition spec.cpp:84
Seq< std::unique_ptr< Stmt > > Block
Sequence of statements.
Definition impl.hpp:603
const double base
Base for geometric restart sequence.
Definition search.hh:134
Gecode toplevel namespace
Gecode::FloatVal b(9, 12)
Gecode::FloatVal a(-8, 5)
Case records("Read::Records", [](void) { const char *rows="n: int repeat n { list row: int until eol } width: int\n" "check sum(row) + count(row) - 1 <= width \"the clues do not fit\"";CHECK(read(rows, "2\n1 1\n2\n3").size("row")==2);CHECK(fails(rows, "2\n1 1\n 2 2\n3", "test.txt:3:3: check failed for record 2 of 'row': the clues do not fit"));CHECK(read(rows, "2\n1 1\n2\n3").entries()==3);const char *windows="n: int repeat n { ready: int due: int } check ready <= due \"window\"";CHECK(read(windows, "2 3 5 0 1").size("ready")==2);CHECK(fails(windows, "3 0 5 2 4 6 1", "check failed for record 3 of 'ready': window"));const char *jobs="j: int m: int repeat j { k: int repeat m { x: int } } check x < k \"x below k\"";CHECK(read(jobs, "2 2\n5 1 2\n3 1 2\n").size("x")==2);CHECK(fails(jobs, "2 2\n5 1 2\n3 1 4\n", "test.txt:3:5: check failed for record 2 of record 2 of 'x': x below k"));Data d=read("n: int repeat n { list row: int until eol }\n" "check size(row) == 2 && count(row) == 3 && sum(r in row: sum(r)) == 21\n" "check count(r in row: count(r) == 3) == size(row) && defined(row)", "2\n1 2 3\n4 5 6\n");CHECK(d.size("row")==2);CHECK(fails("n: int lim[2]: int repeat n { x: int } check all(l in lim: x < l) \"below\"", "2 5 3 1 4", "check failed for element 2 of 'lim' in record 2 of 'x': below"));const char *optional="sections { \"A\" optional { repeat 2 { x: int } } \"B\" optional } check !defined(x) || x > 0 \"positive\"";CHECK(!read(optional, "B").has("x"));CHECK(read(optional, "A\n1 2").size("x")==2);CHECK(fails(optional, "A\n1 0", "check failed for record 2 of 'x': positive"));CHECK(fails("n: int repeat n { list row: int until eol check count(row) == 2 \"two\" }", "2\n1 2\n3\n", "check failed: two"));CHECK(fails("n: int repeat n { list row: int until eol check count(row) == 2 \"two\" }", "2\n1 2\n3\n", "while reading: repeat [2 of 2]"));CHECK(read("repeat 2 { repeat 2 { x: int } check size(x) == 2 && x > 0 }", "1 2 3 4").size("x")==2);CHECK(fails("repeat 2 { repeat 2 { x: int } check x > 0 \"positive\" }", "1 2 3 0", "check failed for record 2 of 'x': positive"));Data l=read("n: int repeat n { x: int } let s = sum(x) let f = x[0] if count(x) == 2 { let t = 1 }", "2 3 4");CHECK(l.integer("s")==7);CHECK(l.integer("f")==3);CHECK(l.has("t"));CHECK(read("n: int repeat n { x: int } check x > 0 && 1 > 2", "0").size("x")==0);return true;})
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
const int r[4][2]
Definition dom.cpp:152
double position(const Space &home, IntVar x, int i)
Definition ldsb.cpp:1266