Generated on for Gecode by doxygen 1.18.0
eval.hpp
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
34#ifndef GECODE_INSTANCE_EVAL_HPP
35#define GECODE_INSTANCE_EVAL_HPP
36
38
39namespace Gecode { namespace Instance {
40
42 std::string quote(const std::string& s);
44 bool add(long long int x, long long int y, long long int& r);
46 bool sub(long long int x, long long int y, long long int& r);
47
54 class RecordRef {
55 public:
57 const Stmt* repeat;
62 : repeat(nullptr) {}
63 };
64
67 class Witness {
68 public:
70 std::string text;
72 size_t pos;
73 };
74
76 class Binding {
77 private:
79 const Binding*& innermost;
80 public:
82 const std::string& name;
84 const Value* value;
88 const Binding* outer;
90 Binding(const Binding*& b, const std::string& n)
91 : innermost(b), name(n), value(nullptr), record(nullptr), outer(b) {
92 innermost = this;
93 }
94
95 ~Binding(void) {
96 innermost = outer;
97 }
98 };
99
101 class Place {
102 public:
104 size_t pos;
106 int line;
108 size_t start;
109 };
110
112 class Context {
113 public:
115 std::string text;
117 long long int iteration;
119 long long int iterations;
121 explicit Context(const std::string& t, long long int i=0, long long int n=-1)
122 : text(t), iteration(i), iterations(n) {}
123 };
124
126 class Input {
127 private:
129 enum class CharKind : unsigned char {
130 PLAIN,
131 SEPARATOR,
132 SPLIT
133 };
135 CharKind kind[256];
137 CharKind kind_of(char c) const {
138 return kind[static_cast<unsigned char>(c)];
139 }
140 public:
142 const std::string& text;
144 std::string origin;
150 size_t pos;
152 int line;
154 size_t start;
155
157 Input(const std::string& t, const std::string& o)
158 : text(t), origin(o), pos(0), line(1), start(0) {
159 for (int c=0; c<256; c++)
160 kind[c] = is_space(static_cast<char>(c)) ? CharKind::SEPARATOR : CharKind::PLAIN;
161 }
162
164 void add_split(const std::string& cs) {
165 for (char c : cs)
166 if (kind_of(c) == CharKind::PLAIN)
167 kind[static_cast<unsigned char>(c)] = CharKind::SPLIT;
168 }
169
170 void add_separators(const std::string& cs) {
171 for (char c : cs)
172 kind[static_cast<unsigned char>(c)] = CharKind::SEPARATOR;
173 }
174
176 void advance(size_t p) {
177 while (pos < p) {
178 if (text[pos] == '\n') {
179 line++;
180 start = pos+1;
181 }
182 pos++;
183 }
184 }
185
186 bool line_start(void) const {
187 for (size_t k=start; k<pos; k++)
188 if (!is_blank(text[k]))
189 return false;
190 return true;
191 }
192
193 bool starts_with(const std::string& prefix) const {
194 if (prefix.empty() || (text.compare(pos, prefix.size(), prefix) != 0))
195 return false;
196 size_t after = pos + prefix.size();
197 return !is_alnum(prefix[prefix.size()-1]) || (after >= text.size()) || !is_alnum(text[after]);
198 }
199
200 void to_eol(void) {
201 size_t p = text.find('\n', pos);
202 advance(p == std::string::npos ? text.size() : p);
203 }
204
205 bool is_separator(char c) const {
206 return kind_of(c) == CharKind::SEPARATOR;
207 }
208
209 bool is_split(char c) const {
210 return kind_of(c) == CharKind::SPLIT;
211 }
212
213 bool in_line(size_t q) const {
214 return (q < text.size()) && (text[q] != '\n');
215 }
216
217 void skip(void) {
218 for (;;) {
219 const char* s = text.data();
220 size_t n = text.size();
221 while ((pos < n) && is_separator(s[pos])) {
222 if (s[pos] == '\n') {
223 line++;
224 start = pos+1;
225 }
226 pos++;
227 }
228 if ((pos >= text.size()) || !line_start())
229 return;
230 bool comment = false, stop = false;
231 for (const std::string& c : comments)
232 comment = comment || starts_with(c);
233 for (const std::string& s : stops)
234 stop = stop || starts_with(s);
235 if (comment) {
236 to_eol();
237 } else if (stop) {
238 advance(text.size());
239 return;
240 } else {
241 return;
242 }
243 }
244 }
245
246 bool skip_to_data(void) {
247 skip();
248 return pos < text.size();
249 }
250
251 bool skip_to_line_data(void) {
252 while (in_line(pos) && is_separator(text[pos]))
253 pos++;
254 return in_line(pos);
255 }
256
257 size_t token_end(void) const {
258 size_t q = pos;
259 if ((q < text.size()) && is_split(text[q]))
260 return q+1;
261 while ((q < text.size()) && (kind_of(text[q]) == CharKind::PLAIN))
262 q++;
263 return q;
264 }
265
266 std::string token(void) {
267 size_t q = token_end();
268 std::string t = text.substr(pos, q-pos);
269 advance(q);
270 return t;
271 }
272
278 bool int_token(long long int& v) {
279 const char* s = text.data();
280 size_t n = text.size(), p = pos;
281 if ((p < n) && is_split(s[p])) {
282 if (!is_digit(s[p]))
283 return false;
284 v = s[p] - '0';
285 pos = p+1;
286 return true;
287 }
288 bool negative = (p < n) && (s[p] == '-');
289 if ((p < n) && is_sign(s[p]))
290 p++;
291 size_t digits = p;
292 // The magnitude, which may be one more than LLONG_MAX if negative
293 unsigned long long int limit = static_cast<unsigned long long int>(LLONG_MAX) + (negative ? 1 : 0);
294 unsigned long long int m = 0;
295 for (; (p < n) && is_digit(s[p]) && (kind_of(s[p]) == CharKind::PLAIN); p++) {
296 unsigned int d = static_cast<unsigned int>(s[p] - '0');
297 if (m > (limit - d) / 10)
298 return false;
299 m = 10*m + d;
300 }
301 // The token must end after the digits
302 if ((p == digits) || ((p < n) && (kind_of(s[p]) == CharKind::PLAIN)))
303 return false;
304 v = negative ? static_cast<long long int>(0ULL - m) : static_cast<long long int>(m);
305 // A token holds no newline
306 pos = p;
307 return true;
308 }
309
310 std::string peek(void) {
311 size_t p0 = pos, s0 = start;
312 int l0 = line;
313 std::string t = skip_to_data() ? token() : std::string();
314 pos = p0; start = s0; line = l0;
315 return t;
316 }
317
318 std::string rest(void) const {
319 size_t q = text.find('\n', pos);
320 if (q == std::string::npos) q = text.size();
321 while ((q > pos) && is_blank(text[q-1])) q--;
322 return text.substr(pos, q-pos);
323 }
324
325 std::string line_at(size_t s) const {
326 size_t q = text.find('\n', s);
327 if (q == std::string::npos) q = text.size();
328 while ((q > s) && is_blank(text[q-1])) q--;
329 return text.substr(s, q-s);
330 }
331
332 Place here(void) const {
333 Place p;
334 p.pos = pos; p.line = line; p.start = start;
335 return p;
336 }
337
338 Place place(size_t q) const {
339 assert(q <= pos);
340 // Counted back from the current place, as q is usually close to it
341 Place p;
342 p.pos = q; p.line = line; p.start = q;
343 for (size_t k=q; k<pos; k++)
344 if (text[k] == '\n')
345 p.line--;
346 while ((p.start > 0) && (text[p.start-1] != '\n'))
347 p.start--;
348 return p;
349 }
350
351 size_t next_data(void) {
352 size_t p0 = pos, s0 = start;
353 int l0 = line;
354 skip();
355 size_t r = pos;
356 pos = p0; start = s0; line = l0;
357 return r;
358 }
359 };
360
367 class Evaluator {
368 public:
370 Evaluator(const SpecImpl& s, const std::string& text, const std::string& origin);
371 protected:
385 const Stmt* checked;
394 long long int effort;
397 const long long int max_effort;
399 static const long long int base_effort = 1LL << 20;
400
402 std::string located(const std::string& msg);
404 std::string located(const std::string& msg, const Place& at);
406 [[noreturn]] void fail(const std::string& msg);
408 [[noreturn]] void fail(const ShapeError& e, const std::string& n);
410 void visit(long long int k);
412 void set(const std::string& n, Value&& v);
414 const Value* lookup(const std::string& n) const;
415
416 /*
417 * Expressions
418 */
420 static bool truth(const Value& v);
422 static Value boolean(bool b);
429 const Value& ref(const Expr& e, Value& tmp);
432 Seq<int> record_path(int i) const;
435 const Value& starts(const Stmt* r, const std::string& n);
439 size_t record_start(const RecordRef& l, int i);
448 const Value& field(const Expr& e, Value& tmp);
450 long long int integer(const Value& v, const std::string& op);
452 static bool explains(const Expr& e);
454 Value eval(const Expr& e);
456 Value evaluate(const Expr& e);
458 bool test(const Expr& e);
460 bool explained(const Expr& e);
462 Value unary(const Expr& e);
464 Value binary(const Expr& e);
466 bool compare(const Value& a, const Value& b, const Expr& e);
468 Value call(const Expr& e);
470 bool defined(const Expr& e) const;
472 bool distinct(const Expr& e);
474 static std::string indexed(const Expr& e);
476 long long int index(const Expr& e);
483 std::string scalar_hint(const Expr& e) const;
487 static std::string array_name(const Expr& a);
490 RecordRef element_records(const Expr& e, const Expr& a);
493 void explain(const Expr& e, const RecordRef& r, int i);
504 long long int count(const Expr& e, const char* what);
513 bool holds(const Stmt& s, std::string& error);
516 bool ranges(const Stmt& s, int i, int level) const;
525 bool check_records(const Stmt& s, int deepest, Seq<int>& at, std::string& error);
528 size_t record_place(const Record& r, const Seq<int>& at);
531 Place place(size_t q) const;
533 static std::string record_text(const Record& r, const Seq<int>& at);
536 std::string failure(const Stmt& s, int deepest, const Seq<int>& at);
537 };
538
539}}
540
541#endif
542
543// STATISTICS: instance-any
A name bound by a comprehension, visible while the binding exists.
Definition eval.hpp:76
const Value * value
The value, unless a record.
Definition eval.hpp:84
const RecordRef * record
The record, if a record of a named repeat.
Definition eval.hpp:86
Binding(const Binding *&b, const std::string &n)
Bind n inside the bindings starting at b.
Definition eval.hpp:90
const Binding * outer
The binding of the enclosing comprehension, or null.
Definition eval.hpp:88
~Binding(void)
Remove the binding.
Definition eval.hpp:95
const std::string & name
The name.
Definition eval.hpp:82
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
Context(const std::string &t, long long int i=0, long long int n=-1)
Initialize for t in iteration i of n.
Definition eval.hpp:121
Value eval(const Expr &e)
Evaluate e, keeping why only if e explains it.
bool defined(const Expr &e) const
Test whether name e is defined.
static Value boolean(bool b)
Return b as an integer.
bool test(const Expr &e)
Return whether e is true, avoiding a copy for names.
long long int count(const Expr &e, const char *what)
Return the value of e, a count described by what.
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
static std::string array_name(const Expr &a)
Describe array a of a comprehension, for messages.
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.
RecordRef records_of(const Expr &e)
Evaluate e, a record or a list of records.
static bool truth(const Value &v)
Test whether v is true.
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
static std::string record_text(const Record &r, const Seq< int > &at)
Describe the records at of record name r, innermost first.
std::string located(const std::string &msg)
Return the error message msg with the location and context.
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
void set(const std::string &n, Value &&v)
Define n as v in the innermost frame.
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.
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.
Value call(const Expr &e)
Call a function (names and arguments are checked by the parser).
const Value * lookup(const std::string &n) const
Return the value of n, or null if it is not defined.
bool holds(const Stmt &s, std::string &error)
Test whether check s holds, and otherwise store why it fails in error.
bool explained(const Expr &e)
Return whether e is true, with only its own explanation in why.
void fail(const std::string &msg)
Throw an error with message msg at the current position.
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.
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.
bool distinct(const Expr &e)
Test whether all integers in the arguments of call e differ.
bool compare(const Value &a, const Value &b, const Expr &e)
Compare single values a and b with the operator of e.
const Value & field(const Expr &e, Value &tmp)
Evaluate field e of a record or a list of records.
long long int integer(const Value &v, const std::string &op)
Return the integer of single value v, or fail for op.
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.
static bool explains(const Expr &e)
Test whether e passes on why it is false (see why).
void fail(const ShapeError &e, const std::string &n)
Throw an error for the shape error e of the value of n.
const Value & ref(const Expr &e, Value &tmp)
Evaluate e, avoiding a copy for names.
void visit(long long int k)
Account for visiting k values in expressions.
Seq< Context > context
Description of the statements being executed, for errors.
Definition eval.hpp:379
Value unary(const Expr &e)
Evaluate unary expression e.
Input in
The input.
Definition eval.hpp:375
std::string located(const std::string &msg, const Place &at)
Return the error message msg at at with the context.
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.
std::string scalar_hint(const Expr &e) const
Return a hint for indexing e, a single value.
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,...
static std::string indexed(const Expr &e)
Describe the array of index expression e, for messages.
Value binary(const Expr &e)
Evaluate binary expression e.
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.
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.
Evaluator(const SpecImpl &s, const std::string &text, const std::string &origin)
Initialize for spec s and input text from origin.
Place place(size_t q) const
Return the place of position q in the input, or the current place if q is npos.
Value subscript(const Expr &e)
a[i]: element i, counted from 0, of the outermost list of a
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:...
Value evaluate(const Expr &e)
Evaluate e.
Instance text with a position and line tracking.
Definition eval.hpp:126
void advance(size_t p)
Move forward to p.
Definition eval.hpp:176
void add_split(const std::string &cs)
Make the characters cs tokens by themselves, unless they separate tokens.
Definition eval.hpp:164
std::string origin
Where the text comes from.
Definition eval.hpp:144
size_t next_data(void)
Return where the next data starts (see skip), without moving there.
Definition eval.hpp:351
int line
Current line (1-based).
Definition eval.hpp:152
Place place(size_t q) const
Return the place of position q, which is not after the current one.
Definition eval.hpp:338
bool int_token(long long int &v)
Read the token at the position as an integer v, and return whether it is one.
Definition eval.hpp:278
bool skip_to_line_data(void)
Skip blanks and separators, and return whether data follows on the line.
Definition eval.hpp:251
size_t start
Start of current line.
Definition eval.hpp:154
bool line_start(void) const
Test whether only blanks precede the position on its line.
Definition eval.hpp:186
size_t token_end(void) const
Return where the token at the position ends.
Definition eval.hpp:257
void skip(void)
Skip white space, comment lines, and everything after a stop line.
Definition eval.hpp:217
Seq< std::string > comments
Comment line prefixes.
Definition eval.hpp:146
Input(const std::string &t, const std::string &o)
Initialize for t from o.
Definition eval.hpp:157
bool skip_to_data(void)
Skip to the next data (see skip), and return whether there is any.
Definition eval.hpp:246
std::string rest(void) const
Return the rest of the current line without trailing blanks.
Definition eval.hpp:318
Place here(void) const
Return the current place.
Definition eval.hpp:332
std::string token(void)
Read the token at the position.
Definition eval.hpp:266
Seq< std::string > stops
Prefixes of lines that end the data.
Definition eval.hpp:148
size_t pos
Current position.
Definition eval.hpp:150
bool is_separator(char c) const
Test whether c separates tokens.
Definition eval.hpp:205
void to_eol(void)
Move to the end of the current line.
Definition eval.hpp:200
void add_separators(const std::string &cs)
Make the characters cs separate tokens like white space.
Definition eval.hpp:170
std::string line_at(size_t s) const
Return the line starting at s without trailing blanks.
Definition eval.hpp:325
bool is_split(char c) const
Test whether c forms a token by itself.
Definition eval.hpp:209
bool in_line(size_t q) const
Test whether position q is within the current line.
Definition eval.hpp:213
bool starts_with(const std::string &prefix) const
Test whether the text at the position starts with prefix.
Definition eval.hpp:193
const std::string & text
The text.
Definition eval.hpp:142
std::string peek(void)
Return the next token without consuming it.
Definition eval.hpp:310
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
RecordRef(void)
Initialize without a repeat.
Definition eval.hpp:61
A record name of a check.
Definition impl.hpp:492
Growable array on the Gecode heap.
Definition impl.hpp:118
Error about the shape or type of a value, located by the caller.
Definition impl.hpp:238
Implementation of Spec.
Definition impl.hpp:709
A value: scalar or nested (possibly ragged) array.
Definition impl.hpp:255
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
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.
bool is_digit(char c)
Test whether c is a digit.
Definition impl.hpp:56
bool sub(long long int x, long long int y, long long int &r)
Store x - y in r unless it overflows.
bool is_space(char c)
Test whether c is white space.
Definition impl.hpp:68
bool is_alnum(char c)
Test whether c can occur in a name.
Definition impl.hpp:64
std::string quote(const std::string &s)
Return s in single quotes, with newlines and tabs escaped.
bool is_blank(char c)
Test whether c is white space within a line.
Definition impl.hpp:72
bool is_sign(char c)
Test whether c is a sign.
Definition impl.hpp:76
Gecode toplevel namespace