Generated on for Gecode by doxygen 1.17.0
eval.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
36#include <climits>
37#include <iomanip>
38#include <sstream>
39
40namespace Gecode { namespace Instance {
41
42 std::string
43 quote(const std::string& s) {
44 std::string r = "'";
45 for (char c : s) {
46 if (c == '\n') r += "\\n";
47 else if (c == '\t') r += "\\t";
48 else r += c;
49 }
50 return r + "'";
51 }
52
53 bool
54 add(long long int x, long long int y, long long int& r) {
55 if (((y > 0) && (x > LLONG_MAX - y)) || ((y < 0) && (x < LLONG_MIN - y)))
56 return false;
57 r = x + y;
58 return true;
59 }
60
61 bool
62 sub(long long int x, long long int y, long long int& r) {
63 if (((y < 0) && (x > LLONG_MAX + y)) || ((y > 0) && (x < LLONG_MIN + y)))
64 return false;
65 r = x - y;
66 return true;
67 }
68
69 namespace {
70
72 bool mul(long long int x, long long int y, long long int& r) {
73 // Sign-aware bounds that never negate LLONG_MIN
74 bool ok;
75 if (x > 0)
76 ok = (y > 0) ? (x <= LLONG_MAX / y) : (y >= LLONG_MIN / x);
77 else if (x < 0)
78 ok = (y > 0) ? (x >= LLONG_MIN / y) : ((y == 0) || (y >= LLONG_MAX / x));
79 else
80 ok = true;
81 if (ok)
82 r = x * y;
83 return ok;
84 }
85
87 bool pow(long long int x, long long int y, long long int& r) {
88 // Squaring the base only overflows if the result does, as the base
89 // is squared only while bits of the exponent remain
90 r = 1;
91 while (y > 0) {
92 if (((y & 1) != 0) && !mul(r, x, r))
93 return false;
94 y >>= 1;
95 if ((y > 0) && !mul(x, x, x))
96 return false;
97 }
98 return true;
99 }
100
108 bool locate(const Value& v, const Seq<int>& path, int& level, int& pos) {
109 assert(v.starts.size() == v.depth);
110 level = 0;
111 pos = 0;
112 for (int i : path) {
113 if ((level >= v.depth) || (i < 0) || (i >= v.lengths[level][pos]))
114 return false;
115 pos = v.starts[level][pos] + i;
116 level++;
117 }
118 return true;
119 }
120
123 Value part(const Value& v, int level, int pos) {
124 Value r(v.type);
125 r.depth = v.depth-level;
126 // The lists of the part at each level, then its leaves
127 int from = pos, to = pos+1;
128 for (int k=level; k<v.depth; k++) {
129 r.lengths.push(Seq<int>());
130 for (int j=from; j<to; j++)
131 r.lengths.back().push(v.lengths[k][j]);
132 from = v.starts[k][from];
133 to = v.starts[k][to];
134 }
135 for (int j=from; j<to; j++)
136 switch (v.type) {
137 case ValueType::INT: r.ints.push(v.ints[j]); break;
138 case ValueType::FLOAT: r.reals.push(v.reals[j]); break;
139 default: r.strs.push(v.strs[j]); break;
140 }
141 r.index();
142 return r;
143 }
144
151 Value element(const Value& v, int i) {
152 assert((v.depth > 0) && (v.starts.size() == v.depth) && (i >= 0) && (i < v.size()));
153 return part(v, 1, i);
154 }
155
156 }
157
158 Evaluator::Evaluator(const SpecImpl& s, const std::string& text, const std::string& origin)
159 : spec(s), in(text, origin), spec_line(0), bindings(nullptr), checked(nullptr), record_at(nullptr), effort(0),
160 max_effort(base_effort + 16 * static_cast<long long int>(text.size())) {
161 frames.push(Seq<Entry>());
162 }
163
164 std::string
165 Evaluator::located(const std::string& msg) {
166 return located(msg, in.here());
167 }
168
169 std::string
170 Evaluator::located(const std::string& msg, const Place& at) {
171 std::ostringstream os;
172 size_t col = at.pos - at.start + 1;
173 os << in.origin << ":" << at.line << ":" << col << ": " << msg << "\n";
174 std::string l = in.line_at(at.start);
175 if (l.size() > 100) l = l.substr(0, 100) + "...";
176 os << std::setw(6) << at.line << " | " << l << "\n"
177 << " | " << std::string(col > 1 ? col-1 : 0, ' ') << "^";
178 if (!context.empty()) {
179 os << "\n while reading: ";
180 for (int k=0; k<context.size(); k++) {
181 const Context& x = context[k];
182 os << (k > 0 ? " > " : "") << x.text;
183 if (x.iteration > 0) {
184 os << " [" << x.iteration;
185 if (x.iterations >= 0)
186 os << " of " << x.iterations;
187 os << "]";
188 }
189 }
190 }
191 if (spec_line > 0)
192 os << "\n spec: " << spec.origin << ":" << spec_line;
193 return os.str();
194 }
195
196 void
197 Evaluator::fail(const std::string& msg) {
198 throw Error(located(msg));
199 }
200
201 void
202 Evaluator::fail(const ShapeError& e, const std::string& n) {
203 fail("'" + n + "': " + e.msg);
204 }
205
206 void
207 Evaluator::visit(long long int k) {
208 effort += k;
209 if (effort > max_effort)
210 fail("the expressions do too much work for the size of the input");
211 }
212
213 void
214 Evaluator::set(const std::string& n, Value&& v) {
215 // Expressions access the rows of arrays through the starts
216 v.index();
217 Seq<Entry>& f = frames.back();
218 for (Entry& e : f)
219 if (e.name == n) {
220 e.value = std::move(v);
221 return;
222 }
223 f.push(Entry(n, std::move(v)));
224 }
225
226 const Value*
227 Evaluator::lookup(const std::string& n) const {
228 for (const Binding* b = bindings; b != nullptr; b = b->outer)
229 if (b->name == n)
230 return b->value;
231 for (int k=frames.size(); k--; )
232 for (const Entry& e : frames[k])
233 if (e.name == n)
234 return &e.value;
235 return nullptr;
236 }
237
238 bool
240 if (v.depth > 0) return v.size() > 0;
241 switch (v.type) {
242 case ValueType::INT: return v.ints[0] != 0;
243 case ValueType::FLOAT: return v.reals[0] != 0.0;
244 default: return !v.strs[0].empty();
245 }
246 }
247
248 Value
250 return Value::integer(b ? 1 : 0);
251 }
252
253 const Value&
254 Evaluator::ref(const Expr& e, Value& tmp) {
255 assert(e.records == nullptr);
256 if (e.kind == Expr::Kind::NAME) {
257 const Value* v = (e.record >= 0) ? records[e.record] : lookup(e.s);
258 if (v == nullptr)
259 fail("'" + e.s + "' is not defined yet");
260 return *v;
261 }
262 if (e.kind == Expr::Kind::FIELD)
263 return field(e, tmp);
264 tmp = eval(e);
265 return tmp;
266 }
267
270 Seq<int> p;
271 for (int k=0; k<checked->records[i].repeats.size(); k++)
272 p.push((*record_at)[k]);
273 return p;
274 }
275
276 const Value&
277 Evaluator::starts(const Stmt* r, const std::string& n) {
278 const Value* v = lookup(record_starts(r->id));
279 if (v == nullptr)
280 fail("'" + n + "' is not defined yet");
281 return *v;
282 }
283
284 int
286 int level, pos;
287 const Value& v = starts(l.repeat, l.repeat->list);
288 if (!locate(v, l.path, level, pos) || (level >= v.depth))
289 return 0;
290 return v.lengths[level][pos];
291 }
292
293 size_t
295 const Value* v = lookup(record_starts(l.repeat->id));
296 Seq<int> p(l.path);
297 p.push(i);
298 int level, pos;
299 if ((v == nullptr) || !locate(*v, p, level, pos) || (level != v->depth))
300 return std::string::npos;
301 return static_cast<size_t>(v->ints[pos]);
302 }
303
306 assert(e.records != nullptr);
307 RecordRef r;
308 r.repeat = e.records;
309 if (e.record >= 0) {
310 // A list of records that a check ranges over
311 if (records[e.record] == nullptr)
312 fail("'" + checked->records[e.record].label + "' is not defined yet");
313 r.path = record_path(e.record);
314 return r;
315 }
316 switch (e.kind) {
317 case Expr::Kind::NAME:
318 for (const Binding* b = bindings; b != nullptr; b = b->outer)
319 if (b->name == e.s)
320 return *b->record;
321 // A record name outside a check is the current record
322 if (e.open > 0)
323 (void) starts(e.records, e.s);
324 return r;
326 // A list of records in a record
327 r.path = records_of(*e.args[0]).path;
328 return r;
329 default: {
330 r = records_of(*e.args[0]);
331 long long int k = index(*e.args[1]);
332 int n = count_records(r);
333 if ((k < 0) || (k >= n))
334 fail("index " + std::to_string(k) + " is out of range for '" + r.repeat->list + "' (size " +
335 std::to_string(n) + ", indices start at 0)");
336 r.path.push(static_cast<int>(k));
337 visit(1);
338 return r;
339 }
340 }
341 }
342
343 const Value&
344 Evaluator::field(const Expr& e, Value& tmp) {
345 if (e.record >= 0) {
346 if (records[e.record] == nullptr)
347 fail("'" + e.s + "' is not defined yet");
348 return *records[e.record];
349 }
350 RecordRef r = records_of(*e.args[0]);
351 const Value* v = lookup(e.s);
352 if (v == nullptr)
353 fail("'" + e.s + "' is not defined yet");
354 if (r.path.empty())
355 return *v;
356 int level, pos;
357 if (!locate(*v, r.path, level, pos))
358 fail("'" + e.s + "' is not defined in this record of '" + r.repeat->list + "'");
359 tmp = part(*v, level, pos);
360 visit(1 + tmp.leaves());
361 return tmp;
362 }
363
364 long long int
365 Evaluator::integer(const Value& v, const std::string& op) {
366 if ((v.depth > 0) || (v.type != ValueType::INT))
367 fail("'" + op + "' needs integers");
368 return v.ints[0];
369 }
370
371 bool
373 if (e.kind == Expr::Kind::BINARY)
374 return (e.op == Expr::Op::OR) || (e.op == Expr::Op::AND);
375 return (e.kind == Expr::Kind::COMPREHENSION) && (e.s == "all");
376 }
377
378 Value
380 Value r = evaluate(e);
381 if (!explains(e))
382 why.clear();
383 return r;
384 }
385
386 Value
388 switch (e.kind) {
389 case Expr::Kind::INT: return Value::integer(e.i);
390 case Expr::Kind::FLOAT: return Value::real(e.f);
391 case Expr::Kind::STR: return Value::string(e.s);
394 return ref(e, tmp);
395 }
396 case Expr::Kind::UNARY: return unary(e);
397 case Expr::Kind::BINARY: return binary(e);
398 case Expr::Kind::INDEX: return subscript(e);
400 default: return call(e);
401 }
402 }
403
404 bool
407 return truth(ref(e, tmp));
408 }
409
410 bool
412 why.clear();
413 return test(e);
414 }
415
416 Value
418 if (e.op == Expr::Op::NOT)
419 return boolean(!test(*e.args[0]));
421 const Value& a = ref(*e.args[0], tmp);
422 if (a.is_number() && (a.type == ValueType::FLOAT))
423 return Value::real(-a.reals[0]);
424 long long int x = integer(a, e.s);
425 if (x == LLONG_MIN)
426 fail("integer overflow in '-'");
427 return Value::integer(-x);
428 }
429
430 Value
432 // Only evaluate the second operand if needed
433 if (e.op == Expr::Op::OR)
434 return boolean(explained(*e.args[0]) || explained(*e.args[1]));
435 if (e.op == Expr::Op::AND)
436 return boolean(explained(*e.args[0]) && explained(*e.args[1]));
438 const Value& a = ref(*e.args[0], ta);
439 const Value& b = ref(*e.args[1], tb);
440 switch (e.op) {
441 case Expr::Op::EQ: case Expr::Op::NE: case Expr::Op::LT: case Expr::Op::GT:
442 case Expr::Op::LE: case Expr::Op::GE:
443 return boolean(compare(a, b, e));
444 default:
445 break;
446 }
447 // Arithmetic is on integers: specs compute sizes and counts
448 long long int x = integer(a, e.s), y = integer(b, e.s), r = 0;
449 bool ok;
450 switch (e.op) {
451 case Expr::Op::ADD: ok = add(x, y, r); break;
452 case Expr::Op::SUB: ok = sub(x, y, r); break;
453 case Expr::Op::MUL: ok = mul(x, y, r); break;
454 case Expr::Op::POW:
455 if (y < 0)
456 fail("negative exponent in '^'");
457 ok = pow(x, y, r);
458 break;
459 default:
460 // Division and remainder truncate towards zero
461 if (y == 0)
462 fail("division by zero");
463 ok = (x != LLONG_MIN) || (y != -1);
464 if (ok)
465 r = (e.op == Expr::Op::DIV) ? (x / y) : (x % y);
466 break;
467 }
468 if (!ok)
469 fail("integer overflow in '" + e.s + "'");
470 return Value::integer(r);
471 }
472
473 bool
474 Evaluator::compare(const Value& a, const Value& b, const Expr& e) {
475 if ((a.depth > 0) || (b.depth > 0))
476 fail("'" + e.s + "' compares single values, not arrays");
477 int c;
478 if ((a.type == ValueType::STRING) || (b.type == ValueType::STRING)) {
479 if ((e.op != Expr::Op::EQ) && (e.op != Expr::Op::NE))
480 fail("'" + e.s + "' compares numbers");
481 c = ((a.type == b.type) && (a.strs[0] == b.strs[0])) ? 0 : 1;
482 } else if ((a.type == ValueType::INT) && (b.type == ValueType::INT)) {
483 c = (a.ints[0] < b.ints[0]) ? -1 : (a.ints[0] > b.ints[0] ? 1 : 0);
484 } else {
485 // An integer compared with a float is converted to a float
486 c = (a.as_double() < b.as_double()) ? -1 : (a.as_double() > b.as_double() ? 1 : 0);
487 }
488 switch (e.op) {
489 case Expr::Op::EQ: return c == 0;
490 case Expr::Op::NE: return c != 0;
491 case Expr::Op::LT: return c < 0;
492 case Expr::Op::GT: return c > 0;
493 case Expr::Op::LE: return c <= 0;
494 default: return c >= 0;
495 }
496 }
497
498 Value
500 const std::string& f = e.s;
501 if (f == "defined")
502 return boolean(defined(*e.args[0]));
503 if (((f == "count") || (f == "size")) && (e.args[0]->records != nullptr))
505 if ((f == "count") || (f == "size")) {
507 const Value& v = ref(*e.args[0], tmp);
508 if (v.depth == 0)
509 fail("'" + f + "' takes an array");
510 return Value::integer(v.size());
511 }
512 if (f == "distinct")
513 return boolean(distinct(e));
514 // min, max, and sum over all integers in all arguments
515 bool any = false;
516 long long int r = 0;
517 for (const std::unique_ptr<Expr>& a : e.args) {
519 const Value& v = ref(*a, tmp);
520 if ((v.type != ValueType::INT) && (v.leaves() > 0))
521 fail("'" + f + "' takes integers");
522 visit(v.leaves());
523 for (long long int x : v.ints) {
524 if (f == "sum") {
525 if (!add(r, x, r))
526 fail("integer overflow in 'sum'");
527 } else if (!any || ((f == "min") ? (x < r) : (x > r))) {
528 r = x;
529 }
530 any = true;
531 }
532 }
533 if (!any && (f != "sum"))
534 fail("'" + f + "' of no integers");
535 return Value::integer(r);
536 }
537
538 bool
539 Evaluator::defined(const Expr& e) const {
540 for (const Binding* b = bindings; b != nullptr; b = b->outer)
541 if (b->name == e.s)
542 return true;
543 if (e.records != nullptr)
544 return lookup(record_starts(e.records->id)) != nullptr;
545 return lookup(e.s) != nullptr;
546 }
547
548 bool
551 for (const std::unique_ptr<Expr>& a : e.args) {
553 const Value& v = ref(*a, tmp);
554 if ((v.type != ValueType::INT) && (v.leaves() > 0))
555 fail("'distinct' takes integers");
556 visit(v.leaves());
557 for (long long int i : v.ints)
558 x.push(i);
559 }
560 Support::quicksort(x.begin(), x.size());
561 for (int k=1; k<x.size(); k++)
562 if (x[k-1] == x[k])
563 return false;
564 return true;
565 }
566
567 std::string
569 const Expr* a = e.args[0].get();
570 bool nested = false;
571 while (a->kind == Expr::Kind::INDEX) {
572 a = a->args[0].get();
573 nested = true;
574 }
575 if ((a->kind != Expr::Kind::NAME) && (a->kind != Expr::Kind::FIELD))
576 return "the array";
577 return (nested ? "an element of '" : "'") + a->s + "'";
578 }
579
580 long long int
583 const Value& i = ref(e, tmp);
584 if ((i.depth > 0) || (i.type != ValueType::INT))
585 fail("an index must be an integer");
586 return i.ints[0];
587 }
588
589 std::string
590 Evaluator::scalar_hint(const Expr& e) const {
591 if (e.record < 0)
592 return "";
593 const Record& r = checked->records[e.record];
594 const std::string& l = r.repeats.back()->list;
595 std::string m = ", which is one value of each record here; to index the records, ";
596 if (l.empty())
597 return m + "name them, as in 'repeat n as nodes { each node ... }', and use 'nodes[0]." + e.s + "'";
598 return m + "use '" + l + "[0]." + e.s + "'";
599 }
600
601 Value
603 assert(e.records == nullptr);
605 const Value& a = ref(*e.args[0], ta);
606 if (a.depth == 0)
607 fail("only arrays can be indexed, not " + indexed(e) + scalar_hint(*e.args[0]));
608 long long int k = index(*e.args[1]);
609 if ((k < 0) || (k >= a.size()))
610 fail("index " + std::to_string(k) + " is out of range for " + indexed(e) + " (size " +
611 std::to_string(a.size()) + ", indices start at 0)");
612 Value r = element(a, static_cast<int>(k));
613 visit(1 + r.leaves());
614 return r;
615 }
616
617 std::string
619 if (a.kind == Expr::Kind::NAME)
620 return "'" + a.s + "'";
621 if ((a.kind == Expr::Kind::FIELD) && (a.args[0]->kind == Expr::Kind::NAME))
622 return "'" + a.args[0]->s + "." + a.s + "'";
623 return "the array";
624 }
625
628 RecordRef r;
629 r.repeat = e.elements;
630 if (a.kind == Expr::Kind::FIELD)
631 r.path = records_of(*a.args[0]).path;
632 return r;
633 }
634
635 void
636 Evaluator::explain(const Expr& e, const RecordRef& r, int i) {
637 Witness w;
638 w.pos = std::string::npos;
639 std::string n = std::to_string(i+1);
640 if (e.elements == nullptr) {
641 w.text = "element " + n + " of " + array_name(*e.args[0]);
642 } else {
643 const std::string& l = e.elements->list;
644 w.text = "record " + n + " of " + (l.empty() ? array_name(*e.args[0]) : "'" + l + "'");
645 w.pos = record_start(r, i);
646 }
647 why.push(std::move(w));
648 }
649
650 Value
652 const std::string& f = e.s;
653 const Expr& source = *e.args[0];
655 const Value* a = nullptr;
656 RecordRef list, x;
657 int n;
658 if (source.records != nullptr) {
659 list = records_of(source);
660 n = count_records(list);
661 } else {
662 a = &ref(source, ta);
663 if (a->depth == 0)
664 fail("'" + f + "(" + e.var + " in ...)' needs an array");
665 n = a->size();
666 }
667 RecordRef elements;
668 if ((f == "all") && (e.elements != nullptr))
669 elements = (a == nullptr) ? list : element_records(e, source);
670 Binding b(bindings, e.var);
671 long long int r = 0;
672 for (int i=0; i<n; i++) {
673 Value v;
674 if (a != nullptr) {
675 v = element(*a, i);
676 visit(1 + v.leaves());
677 b.value = &v;
678 } else {
679 x = list;
680 x.path.push(i);
681 visit(1);
682 b.record = &x;
683 }
684 if (f == "sum") {
686 if (!add(r, integer(ref(*e.args[1], tv), "sum"), r))
687 fail("integer overflow in 'sum'");
688 } else if (explained(*e.args[1])) {
689 if (f == "any")
690 return boolean(true);
691 r++;
692 } else if (f == "all") {
693 explain(e, elements, i);
694 return boolean(false);
695 }
696 }
697 why.clear();
698 if ((f == "all") || (f == "any"))
699 return boolean(f == "all");
700 return Value::integer(r);
701 }
702
703 long long int
704 Evaluator::count(const Expr& e, const char* what) {
706 const Value& v = ref(e, tmp);
707 if ((v.depth > 0) || (v.type != ValueType::INT))
708 fail(std::string(what) + " must be an integer");
709 if (v.ints[0] < 0)
710 fail(std::string(what) + " is negative (" + std::to_string(v.ints[0]) + ")");
711 if (v.ints[0] > INT_MAX)
712 fail(std::string(what) + " is too large (" + std::to_string(v.ints[0]) + ")");
713 return v.ints[0];
714 }
715
716 bool
717 Evaluator::holds(const Stmt& s, std::string& error) {
718 records.clear();
719 int deepest = -1;
720 for (int i=0; i<s.records.size(); i++) {
721 records.push(lookup(s.records[i].name));
722 if (ranges(s, i, (deepest < 0) ? 0 : s.records[deepest].repeats.size()))
723 deepest = i;
724 }
725 Seq<int> at;
726 checked = &s;
727 record_at = &at;
728 bool ok = check_records(s, deepest, at, error);
729 checked = nullptr;
730 record_at = nullptr;
731 return ok;
732 }
733
734 bool
735 Evaluator::ranges(const Stmt& s, int i, int level) const {
736 return (records[i] != nullptr) && (s.records[i].repeats.size() > level);
737 }
738
739 bool
740 Evaluator::check_records(const Stmt& s, int deepest, Seq<int>& at, std::string& error) {
741 int level = at.size();
742 if ((deepest < 0) || (level == s.records[deepest].repeats.size())) {
743 if (explained(*s.expr))
744 return true;
745 error = failure(s, deepest, at);
746 return false;
747 }
748 int n = -1, first = -1;
749 for (int i=0; i<records.size(); i++)
750 if (ranges(s, i, level)) {
751 if (records[i]->depth == 0)
752 fail("'" + s.records[i].label + "' has no records");
753 if (first < 0) {
754 first = i;
755 n = records[i]->size();
756 } else if (records[i]->size() != n) {
757 fail("'" + s.records[first].label + "' and '" + s.records[i].label +
758 "' have different numbers of records");
759 }
760 }
762 Seq<Value> rows;
763 // No reallocation, so the record names can point at the rows
764 rows.reserve(records.size());
765 for (int r=0; r<n; r++) {
766 rows.clear();
767 for (int i=0; i<records.size(); i++)
768 if (ranges(s, i, level)) {
769 rows.push(element(*outer[i], r));
770 visit(1 + rows.back().leaves());
771 records[i] = &rows.back();
772 }
773 at.push(r);
774 bool ok = check_records(s, deepest, at, error);
775 at.pop();
776 if (!ok)
777 return false;
778 }
779 records = outer;
780 return true;
781 }
782
783 size_t
785 const Value* p = lookup(r.starts);
786 int level, pos;
787 if ((p == nullptr) || !locate(*p, at, level, pos) || (level != p->depth))
788 return std::string::npos;
789 return static_cast<size_t>(p->ints[pos]);
790 }
791
792 Place
793 Evaluator::place(size_t q) const {
794 return (q <= in.pos) ? in.place(q) : in.here();
795 }
796
797 std::string
799 bool named = true;
800 for (const Stmt* x : r.repeats)
801 named = named && !x->list.empty();
802 std::string m;
803 for (int k=at.size(); k--; ) {
804 m += "record " + std::to_string(at[k]+1) + " of ";
805 if (named)
806 m += "'" + r.repeats[k]->list + "'" + (k > 0 ? " in " : "");
807 }
808 return named ? m : m + "'" + r.label + "'";
809 }
810
811 std::string
812 Evaluator::failure(const Stmt& s, int deepest, const Seq<int>& at) {
813 // The innermost record found is where the check failed
814 std::string m;
815 size_t q = std::string::npos;
816 for (const Witness& w : why) {
817 m += (m.empty() ? "" : " in ") + w.text;
818 if (q == std::string::npos)
819 q = w.pos;
820 }
821 if (!at.empty()) {
822 m += (m.empty() ? "" : " in ") + record_text(s.records[deepest], at);
823 if (q == std::string::npos)
824 q = record_place(s.records[deepest], at);
825 }
826 m = "check failed" + (m.empty() ? "" : " for " + m);
827 if (!s.message.empty())
828 m += ": " + s.message;
829 return located(m, place(q));
830 }
831
832}}
833
834// STATISTICS: instance-any
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
A name bound by a comprehension, visible while the binding exists.
Definition eval.hpp:76
A statement being executed, for errors.
Definition eval.hpp:112
std::string text
What is executed, such as a name.
Definition eval.hpp:115
long long int iteration
The iteration of a repeat or instances statement, from 1, or 0.
Definition eval.hpp:117
long long int iterations
The number of iterations, or -1 if unknown.
Definition eval.hpp:119
A named value.
Definition impl.hpp:400
Exception for errors in specs and instance files
Definition instance.hh:337
Value eval(const Expr &e)
Evaluate e, keeping why only if e explains it.
Definition eval.cpp:379
bool defined(const Expr &e) const
Test whether name e is defined.
Definition eval.cpp:539
static Value boolean(bool b)
Return b as an integer.
Definition eval.cpp:249
bool test(const Expr &e)
Return whether e is true, avoiding a copy for names.
Definition eval.cpp:405
long long int count(const Expr &e, const char *what)
Return the value of e, a count described by what.
Definition eval.cpp:704
static bool explains(const Expr &e)
Test whether e passes on why it is false (see why).
Definition eval.cpp:372
const SpecImpl & spec
The spec.
Definition eval.hpp:373
static const long long int base_effort
Base of the limit for effort.
Definition eval.hpp:399
Seq< int > record_path(int i) const
Return the indices of the record at of the check that select the records of its record name i.
Definition eval.cpp:269
static std::string array_name(const Expr &a)
Describe array a of a comprehension, for messages.
Definition eval.cpp:618
RecordRef records_of(const Expr &e)
Evaluate e, a record or a list of records.
Definition eval.cpp:305
Seq< const Value * > records
Values of its record names (see Record).
Definition eval.hpp:387
Value comprehension(const Expr &e)
all, any, count, and sum over the elements of an array
Definition eval.cpp:651
std::string located(const std::string &msg)
Return the error message msg with the location and context.
Definition eval.cpp:165
static std::string indexed(const Expr &e)
Describe the array of index expression e, for messages.
Definition eval.cpp:568
const Seq< int > * record_at
The records of the deepest of them, one index per repeat level.
Definition eval.hpp:389
int spec_line
Spec line of the current statement.
Definition eval.hpp:381
static std::string record_text(const Record &r, const Seq< int > &at)
Describe the records at of record name r, innermost first.
Definition eval.cpp:798
static bool truth(const Value &v)
Test whether v is true.
Definition eval.cpp:239
void set(const std::string &n, Value &&v)
Define n as v in the innermost frame.
Definition eval.cpp:214
size_t record_place(const Record &r, const Seq< int > &at)
Return where the record at of record name r starts in the input, or npos if that is unknown.
Definition eval.cpp:784
const Stmt * checked
The check being evaluated, or null.
Definition eval.hpp:385
Seq< Witness > why
Why the last condition evaluated is false, for messages: the elements of the all-comprehensions that ...
Definition eval.hpp:392
long long int index(const Expr &e)
Return the value of index e.
Definition eval.cpp:581
Value call(const Expr &e)
Call a function (names and arguments are checked by the parser).
Definition eval.cpp:499
const Value * lookup(const std::string &n) const
Return the value of n, or null if it is not defined.
Definition eval.cpp:227
bool holds(const Stmt &s, std::string &error)
Test whether check s holds, and otherwise store why it fails in error.
Definition eval.cpp:717
bool explained(const Expr &e)
Return whether e is true, with only its own explanation in why.
Definition eval.cpp:411
void fail(const std::string &msg)
Throw an error with message msg at the current position.
Definition eval.cpp:197
const long long int max_effort
Limit for effort, which grows with the input, so that repeated or nested expressions cannot take time...
Definition eval.hpp:397
size_t record_start(const RecordRef &l, int i)
Return where record i of list l starts in the input, or npos.
Definition eval.cpp:294
std::string failure(const Stmt &s, int deepest, const Seq< int > &at)
Return why check s fails for the records at of its record name deepest.
Definition eval.cpp:812
bool distinct(const Expr &e)
Test whether all integers in the arguments of call e differ.
Definition eval.cpp:549
bool compare(const Value &a, const Value &b, const Expr &e)
Compare single values a and b with the operator of e.
Definition eval.cpp:474
const Value & field(const Expr &e, Value &tmp)
Evaluate field e of a record or a list of records.
Definition eval.cpp:344
long long int integer(const Value &v, const std::string &op)
Return the integer of single value v, or fail for op.
Definition eval.cpp:365
const Value & starts(const Stmt *r, const std::string &n)
Return the record starts of repeat r, failing for n if the repeat has not run yet.
Definition eval.cpp:277
const Value & ref(const Expr &e, Value &tmp)
Evaluate e, avoiding a copy for names.
Definition eval.cpp:254
void visit(long long int k)
Account for visiting k values in expressions.
Definition eval.cpp:207
Seq< Context > context
Description of the statements being executed, for errors.
Definition eval.hpp:379
Value unary(const Expr &e)
Evaluate unary expression e.
Definition eval.cpp:417
Input in
The input.
Definition eval.hpp:375
long long int effort
Values visited by expressions.
Definition eval.hpp:394
bool ranges(const Stmt &s, int i, int level) const
Test whether record name i of check s is defined and ranges over the repeat at level.
Definition eval.cpp:735
std::string scalar_hint(const Expr &e) const
Return a hint for indexing e, a single value.
Definition eval.cpp:590
bool check_records(const Stmt &s, int deepest, Seq< int > &at, std::string &error)
Evaluate check s for the records inside the records at of its record name deepest,...
Definition eval.cpp:740
Value binary(const Expr &e)
Evaluate binary expression e.
Definition eval.cpp:431
void explain(const Expr &e, const RecordRef &r, int i)
Add why element i of the array of all-comprehension e, with records r, is false.
Definition eval.cpp:636
Seq< Seq< Entry > > frames
Values: the outermost frame and one per active repeat iteration.
Definition eval.hpp:377
const Binding * bindings
Names bound by the comprehensions being evaluated.
Definition eval.hpp:383
int count_records(const RecordRef &l)
Return the number of records in list l.
Definition eval.cpp:285
Evaluator(const SpecImpl &s, const std::string &text, const std::string &origin)
Initialize for spec s and input text from origin.
Definition eval.cpp:158
Place place(size_t q) const
Return the place of position q in the input, or the current place if q is npos.
Definition eval.cpp:793
Value subscript(const Expr &e)
a[i]: element i, counted from 0, of the outermost list of a
Definition eval.cpp:602
RecordRef element_records(const Expr &e, const Expr &a)
Return the records that are the elements of array a of comprehension e, an array of values (see Expr:...
Definition eval.cpp:627
Value evaluate(const Expr &e)
Evaluate e.
Definition eval.cpp:387
const Stmt * elements
For a comprehension, the repeat whose records are the elements of its array, or null.
Definition impl.hpp:477
std::string var
Name bound by a comprehension.
Definition impl.hpp:468
long long int i
Integer literal.
Definition impl.hpp:462
std::string s
String literal, name, operator, or function.
Definition impl.hpp:466
int open
1 for a list of records of records, 0 for a record
Definition impl.hpp:474
double f
Float literal.
Definition impl.hpp:464
enum Gecode::Instance::Expr::Kind kind
int record
Index of a record name among the records of its check (-1 if none).
Definition impl.hpp:470
Seq< std::unique_ptr< Expr > > args
Operands or arguments.
Definition impl.hpp:479
const Stmt * records
The repeat whose records or lists of records this is, or null.
Definition impl.hpp:472
enum Gecode::Instance::Expr::Op op
A position in the input, with its line.
Definition eval.hpp:101
size_t pos
Position.
Definition eval.hpp:104
size_t start
Start of the line.
Definition eval.hpp:108
int line
Line (1-based).
Definition eval.hpp:106
Records or a list of records of a named repeat.
Definition eval.hpp:54
const Stmt * repeat
The repeat.
Definition eval.hpp:57
Seq< int > path
The indices.
Definition eval.hpp:59
A record name of a check.
Definition impl.hpp:492
Growable array on the Gecode heap.
Definition impl.hpp:118
bool empty(void) const
Test whether empty.
Definition impl.hpp:170
void reserve(int m)
Make room for m elements.
Definition impl.hpp:172
void push(const T &v)
Append a copy of v.
Definition impl.hpp:176
int size(void) const
Return number of elements.
Definition impl.hpp:168
T * begin(void)
Iteration support.
Definition impl.hpp:228
void pop(void)
Remove last element.
Definition impl.hpp:198
void clear(void)
Remove all elements.
Definition impl.hpp:203
T & back(void)
Return last element.
Definition impl.hpp:218
Error about the shape or type of a value, located by the caller.
Definition impl.hpp:238
std::string msg
Message.
Definition impl.hpp:241
Implementation of Spec.
Definition impl.hpp:709
Seq< Record > records
Record names of a check.
Definition impl.hpp:676
std::string message
Message of a check statement.
Definition impl.hpp:640
int id
Number of a repeat, in the order of the spec.
Definition impl.hpp:674
std::string list
Name of the list of records of a repeat.
Definition impl.hpp:644
std::unique_ptr< Expr > expr
Count, condition, layout, value, or default.
Definition impl.hpp:650
A value: scalar or nested (possibly ragged) array.
Definition impl.hpp:255
int leaves(void) const
Return number of leaves.
Definition impl.hpp:302
static Value real(double v)
Float scalar.
Definition impl.hpp:287
Seq< long long int > ints
Integer leaves.
Definition impl.hpp:266
static Value string(const std::string &v)
String scalar.
Definition impl.hpp:292
int depth
Nesting depth (0 for scalars).
Definition impl.hpp:260
static Value integer(long long int v)
Integer scalar.
Definition impl.hpp:282
A part of the explanation of a failed check, such as "record 3 of'jobs'", with the position of the re...
Definition eval.hpp:67
std::string text
The text.
Definition eval.hpp:70
size_t pos
The position, or npos.
Definition eval.hpp:72
bool pos(const View &x)
Test whether x is positive.
Definition mult.hpp:41
Reading instance files described by reader specs.
bool add(long long int x, long long int y, long long int &r)
Store x + y in r unless it overflows.
Definition eval.cpp:54
@ FLOAT
Floating point numbers.
Definition instance.hh:351
std::string record_starts(int id)
Return the name of the record starts of the repeat numbered id.
Definition impl.hpp:511
bool sub(long long int x, long long int y, long long int &r)
Store x - y in r unless it overflows.
Definition eval.cpp:62
std::string quote(const std::string &s)
Return s in single quotes, with newlines and tabs escaped.
Definition eval.cpp:43
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
Definition element.cpp:39
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
Definition circuit.cpp:169
void pow(Home home, FloatVar x0, int n, FloatVar x1)
Post propagator for for .
Gecode::IntArgs i({1, 2, 3, 4})
const int r[4][2]
Definition dom.cpp:152