Generated on for Gecode by doxygen 1.17.0
reader.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 <unordered_map>
38
39namespace Gecode { namespace Instance {
40
41 namespace {
42
49 int triangle_from(bool upper, bool diag, int i) {
50 return upper ? (diag ? i : i+1) : 0;
51 }
54 int triangle_to(bool upper, bool diag, int n, int i) {
55 return upper ? n : (diag ? i+1 : i);
56 }
57
59 const char* describe(ReadType t) {
60 switch (t) {
61 case ReadType::INT: return "int";
62 case ReadType::FLOAT: return "float";
63 case ReadType::NUM: return "a number";
64 case ReadType::WORD: return "a word";
65 case ReadType::REST: return "the rest of the line";
66 default: return "a symbol";
67 }
68 }
69
71 class Range {
72 public:
74 bool low;
76 bool high;
78 long long int lo;
80 long long int hi;
82 Range(void)
83 : low(false), high(false), lo(0), hi(0) {}
85 bool contains(long long int v) const {
86 return (!low || (v >= lo)) && (!high || (v <= hi));
87 }
89 bool bounded(void) const {
90 return low || high;
91 }
92 };
93
95 class Domain {
96 public:
98 const Type& type;
100 Range range;
102 Domain(const Type& t, const Range& r)
103 : type(t), range(r) {}
105 std::string describe(void) const {
106 std::string d = Instance::describe(type.read);
107 if (range.bounded())
108 d = "an int in " + (range.low ? std::to_string(range.lo) : "") + ".." +
109 (range.high ? std::to_string(range.hi) : "");
110 return type.name.empty() ? d : type.name + " (" + d + ")";
111 }
112 };
113
115 class Interpreter : public Evaluator {
116 public:
118 Interpreter(const SpecImpl& s, const std::string& text, const std::string& origin, const Params& p, bool c)
119 : Evaluator(s, text, origin), params(p), trailing(false), catalog(c), instance_count(-1), select(false),
120 number(-1), current(0), instance_frame(0), selected(false), idle(0), token_start(0) {}
121
123 static void declared_params(const Block& b, Seq<std::string>& out) {
124 for (const std::unique_ptr<Stmt>& s : b) {
125 if (s->kind == Stmt::Kind::PARAM)
126 out.push(s->name);
127 if (s->kind == Stmt::Kind::INSTANCES)
128 out.push("instance");
129 declared_params(s->body, out);
130 declared_params(s->orelse, out);
131 for (const Arm& a : s->arms)
132 declared_params(a.body, out);
133 }
134 }
135
137 void run(DataImpl& d) {
138 // A misspelt parameter would otherwise be ignored silently
139 Seq<std::string> known;
140 declared_params(spec.body, known);
141 for (int i=0; i<params.size(); i++) {
142 bool found = false;
143 for (const std::string& k : known)
144 found = found || (k == params.name(i));
145 if (!found)
146 throw Error(spec.origin + ": the spec has no parameter '" + params.name(i) + "'");
147 }
148 exec(spec.body);
149 spec_line = 0;
150 // Reading stops after the selected instance
151 if (!trailing && !selected && in.skip_to_data())
152 fail("unexpected input after the end of the spec: " + quote(in.rest()));
153 if (catalog) {
154 // Only the number of instances and their names
155 Seq<Entry> c;
156 Entry n;
157 n.name = "instances";
158 n.value = Value::integer(instance_count < 0 ? 1 : instance_count);
159 c.push(std::move(n));
160 if (names.leaves() > 0) {
161 Entry e;
162 e.name = "name";
163 e.value = names;
164 c.push(std::move(e));
165 }
166 if (failures.leaves() > 0) {
167 Entry e;
168 e.name = "failed";
169 e.value = failures;
170 c.push(std::move(e));
171 }
172 frames[0] = std::move(c);
173 }
174 for (Entry& e : frames[0])
175 if (!is_internal(e.name)) {
176 e.value.index();
177 d.entries.push(std::move(e));
178 }
179 }
180
181 private:
183 const Params& params;
185 Seq<long long int> rows;
187 bool trailing;
189 bool catalog;
191 int instance_count;
193 Value names;
195 Value failures;
197 bool select;
199 std::string want;
201 long long int number;
203 int current;
205 int instance_frame;
207 std::string deferred_error;
209 std::string deferred_message;
211 bool selected;
213 long long int idle;
216 static const long long int max_idle = 1LL << 20;
218 std::unordered_map<const Stmt*, Range> type_ranges;
220 size_t token_start;
222 Seq<Value> spare;
224 static const int max_spare = 8;
225
227 void work(long long int k) {
228 idle += k;
229 if (idle > max_idle)
230 fail("too many repetitions or empty rows without reading input");
231 }
232
233
234 /*
235 * Reading
236 */
238 static bool convert(ReadType type, const std::string& t, Value& v) {
239 long long int iv;
240 double fv;
241 if ((type == ReadType::WORD) || (type == ReadType::REST)) {
242 v = Value::string(t);
243 return !t.empty();
244 }
245 if ((type != ReadType::FLOAT) && parse_int(t, iv)) {
246 v = Value::integer(iv);
247 return true;
248 }
249 if ((type != ReadType::INT) && parse_float(t, fv)) {
250 v = Value::real(fv);
251 return true;
252 }
253 return false;
254 }
255
257 [[noreturn]] void expected(const std::string& what) {
258 if (!in.skip_to_data())
259 fail("expected " + what + ", found end of input");
260 fail("expected " + what + ", found " + quote(in.peek()));
261 }
269 bool scan(ReadType type, Value& v) {
270 if (!in.skip_to_data())
271 return false;
272 token_start = in.pos;
273 if (type == ReadType::REST) {
274 v = Value::string(in.rest());
275 in.to_eol();
276 return true;
277 }
278 std::string t = in.token();
279 if (convert(type, t, v))
280 return true;
281 in.pos = token_start;
282 return false;
283 }
285 Value scalar(ReadType type, const std::string& what) {
286 Value v(ValueType::INT);
287 if (!scan(type, v))
288 expected(what);
289 return v;
290 }
292 Value scalar(const Domain& d) {
293 Value v(ValueType::INT);
294 if (!scan(d.type.read, v))
295 expected(d.describe());
296 return v;
297 }
300 long long int int_scalar(const Domain& d) {
301 long long int x;
302 if (!in.skip_to_data())
303 expected(d.describe());
304 token_start = in.pos;
305 if (!in.int_token(x))
306 expected(d.describe());
307 return x;
308 }
310 static bool fits(const Domain& d, const Value& v) {
311 return (v.type != ValueType::INT) || d.range.contains(v.ints[0]);
312 }
315 [[noreturn]] void outside(const Domain& d, size_t from, size_t to) {
316 std::string t = in.text.substr(from, to-from);
317 in.pos = from;
318 fail("expected " + d.describe() + ", found " + quote(t));
319 }
321 Value value(const Domain& d) {
322 Value v = scalar(d);
323 if (!fits(d, v))
324 outside(d, token_start, in.pos);
325 return v;
326 }
328 void push(const Domain& d, Value& v) {
329 if ((d.type.read == ReadType::INT) && (v.type == ValueType::INT)) {
330 long long int x = int_scalar(d);
331 if (!d.range.contains(x))
332 outside(d, token_start, in.pos);
333 v.ints.push(x);
334 } else {
335 v.push(value(d));
336 }
337 }
338
340 Range range(const Type& t) {
341 if (t.named != nullptr) {
342 auto r = type_ranges.find(t.named);
343 if (r == type_ranges.end())
344 fail("the type '" + t.name + "' is not defined yet");
345 return r->second;
346 }
347 Range r;
348 if (t.lo) {
349 r.low = true;
350 r.lo = bound(*t.lo);
351 }
352 if (t.hi) {
353 r.high = true;
354 r.hi = bound(*t.hi);
355 if (t.exclusive && !sub(r.hi, 1, r.hi))
356 fail("integer overflow in the upper bound of a range");
357 }
358 return r;
359 }
361 long long int bound(const Expr& e) {
362 // Ranges are evaluated for every value read, so common bounds
363 // such as 0 and -n avoid making a value
364 if (e.kind == Expr::Kind::INT)
365 return e.i;
366 if ((e.kind == Expr::Kind::UNARY) && (e.op == Expr::Op::NEG)) {
367 long long int x = bound(*e.args[0]);
368 if (x == LLONG_MIN)
369 fail("integer overflow in '-'");
370 return -x;
371 }
372 Value tmp(ValueType::INT);
373 const Value& v = ref(e, tmp);
374 if ((v.depth > 0) || (v.type != ValueType::INT))
375 fail("the bounds of a range must be integers");
376 return v.ints[0];
377 }
378
380 Value array(const Domain& d, const Seq<long long int>& dims) {
381 // Each factor is at most INT_MAX, so the product cannot overflow
382 long long int size = 1;
383 for (long long int n : dims) {
384 size *= n;
385 if (size > INT_MAX)
386 fail("array is too large");
387 }
388 // Rows before an empty dimension cost memory without reading any input
389 if (size == 0) {
390 long long int rows = 1;
391 for (int k=0; (k < dims.size()) && (dims[k] > 0); k++) {
392 rows *= dims[k];
393 work(rows);
394 }
395 }
396 Value v;
397 if (d.type.read == ReadType::FLOAT)
398 v.type = ValueType::FLOAT;
399 else if (d.type.read == ReadType::WORD)
400 v.type = ValueType::STRING;
401 // Read the values before allocating the structure, so that a wrong
402 // count fails at the end of the input rather than on allocation
403 for (long long int i=0; i<size; i++)
404 try {
405 push(d, v);
406 } catch (const ShapeError& e) {
407 fail(e, context.back().text);
408 }
409 v.depth = dims.size();
410 v.lengths.clear();
411 long long int lists = 1;
412 for (long long int n : dims) {
413 v.lengths.push(Seq<int>());
414 v.lengths.back().reserve(static_cast<int>(lists));
415 for (long long int i=0; i<lists; i++)
416 v.lengths.back().push(static_cast<int>(n));
417 lists *= n;
418 }
419 return v;
420 }
421
429 Value layout(const Domain& d, long long int n, long long int m, const std::string& f, long long int o) {
430 if (f == "FULL_MATRIX") {
431 Seq<long long int> dims;
432 dims.push(n); dims.push(m);
433 Value v = array(d, dims);
434 offset(v, o);
435 return v;
436 }
437 if (n != m)
438 fail("layout " + f + " needs a square matrix");
439 // Column-wise upper equals row-wise lower for symmetric matrices
440 bool upper, diag;
441 if ((f == "UPPER_ROW") || (f == "LOWER_COL")) {
442 upper = true; diag = false;
443 } else if ((f == "LOWER_ROW") || (f == "UPPER_COL")) {
444 upper = false; diag = false;
445 } else if ((f == "UPPER_DIAG_ROW") || (f == "LOWER_DIAG_COL")) {
446 upper = true; diag = true;
447 } else if ((f == "LOWER_DIAG_ROW") || (f == "UPPER_DIAG_COL")) {
448 upper = false; diag = true;
449 } else {
450 fail("unknown matrix layout " + quote(f));
451 }
452 if (n*n > INT_MAX)
453 fail("matrix is too large");
454 int nn = static_cast<int>(n);
455 // Read the stored triangle, then mirror it into a full matrix
456 Value t;
457 if (d.type.read == ReadType::FLOAT)
458 t.type = ValueType::FLOAT;
459 for (int i=0; i<nn; i++)
460 for (int j=triangle_from(upper, diag, i); j<triangle_to(upper, diag, nn, i); j++)
461 push(d, t);
462 offset(t, o);
463 Value v;
464 v.type = t.type;
465 v.depth = 2;
466 v.lengths.clear();
467 v.lengths.push(Seq<int>());
468 v.lengths[0].push(nn);
469 v.lengths.push(Seq<int>());
470 for (int i=0; i<nn; i++)
471 v.lengths[1].push(nn);
472 for (int k=0; k<nn*nn; k++)
473 if (v.type == ValueType::INT) v.ints.push(0); else v.reals.push(0.0);
474 int k = 0;
475 for (int i=0; i<nn; i++)
476 for (int j=triangle_from(upper, diag, i); j<triangle_to(upper, diag, nn, i); j++, k++)
477 if (v.type == ValueType::INT) {
478 v.ints[i*nn+j] = t.ints[k]; v.ints[j*nn+i] = t.ints[k];
479 } else {
480 v.reals[i*nn+j] = t.reals[k]; v.reals[j*nn+i] = t.reals[k];
481 }
482 return v;
483 }
484
486 void offset(Value& v, long long int o) {
487 for (long long int& x : v.ints)
488 if (!add(x, o, x))
489 fail("integer overflow when applying offset");
490 for (double& x : v.reals)
491 x += static_cast<double>(o);
492 }
493
495 long long int offset(const Stmt& s) {
496 if (!s.offset)
497 return 0;
498 Value o = eval(*s.offset);
499 if ((o.depth > 0) || (o.type != ValueType::INT))
500 fail("offset must be an integer");
501 return o.ints[0];
502 }
503
505 void store(const Stmt& s, Value&& v) {
506 if (s.name != "_")
507 set(s.name, std::move(v));
508 }
509
511 class Capture {
512 public:
514 const Pattern::Item* item;
516 Value value;
518 size_t from;
520 size_t to;
521 };
522
524 bool match(const Pattern& p) {
525 Seq<Capture> caps;
526 if (!matches(p, caps))
527 return false;
528 take(caps);
529 return true;
530 }
531
533 bool matches(const Pattern& p, Seq<Capture>& caps) {
534 in.skip();
535 if (in.pos >= in.text.size())
536 return false;
537 std::string l = in.rest();
538 size_t c = 0;
539 for (int k=0; k<p.items.size(); k++)
540 if (!match_item(p, k, l, c, caps))
541 return false;
542 while ((c < l.size()) && is_blank(l[c]))
543 c++;
544 return c == l.size();
545 }
546
548 void take(const Seq<Capture>& caps) {
549 // The captures can use each other in their ranges
550 for (const Capture& x : caps)
551 if (!x.item->text.empty() && (x.item->text != "_"))
552 set(x.item->text, Value(x.value));
553 for (const Capture& x : caps)
554 if (x.item->type.ranged()) {
555 Domain d(x.item->type, range(x.item->type));
556 if (!fits(d, x.value))
557 outside(d, in.pos + x.from, in.pos + x.to);
558 }
559 in.to_eol();
560 }
561
563 bool match_item(const Pattern& p, int k, const std::string& l, size_t& c, Seq<Capture>& caps) {
564 typedef Pattern::Item Item;
565 const Item& it = p.items[k];
566 switch (it.kind) {
567 case Item::Kind::SPACE: {
568 size_t c0 = c;
569 while ((c < l.size()) && is_blank(l[c]))
570 c++;
571 return !it.required || (c > c0) || (c == l.size());
572 }
573 case Item::Kind::LIT:
574 if (l.compare(c, it.text.size(), it.text) != 0)
575 return false;
576 c += it.text.size();
577 return true;
578 case Item::Kind::ANY:
579 c = l.size();
580 return true;
581 case Item::Kind::VAR: {
582 std::string want = variable(it.text);
583 if (want.empty() || (l.compare(c, want.size(), want) != 0))
584 return false;
585 c += want.size();
586 return true;
587 }
588 case Item::Kind::CAP: {
589 // A word ends before a literal that follows it directly
590 char stop = 0;
591 if ((k+1 < p.items.size()) && (p.items[k+1].kind == Item::Kind::LIT))
592 stop = p.items[k+1].text[0];
593 size_t c0 = c;
594 c = capture_end(it.type.read, l, c, stop);
595 std::string t = l.substr(c0, c-c0);
596 while (!t.empty() && is_blank(t[t.size()-1]))
597 t.erase(t.size()-1);
598 Capture x;
599 if (!convert(it.type.read, t, x.value))
600 return false;
601 x.item = &it;
602 x.from = c0;
603 x.to = c0 + t.size();
604 caps.push(std::move(x));
605 return true;
606 }
607 }
608 return false;
609 }
610
612 std::string variable(const std::string& n) {
613 const Value* v = lookup(n);
614 if (v == nullptr)
615 fail("'" + n + "' is not defined yet");
616 if ((v->depth == 0) && (v->type == ValueType::STRING))
617 return v->strs[0];
618 if ((v->depth == 0) && (v->type == ValueType::INT))
619 return std::to_string(v->ints[0]);
620 fail("'" + n + "' must be a string or an integer");
621 }
622
624 static size_t capture_end(ReadType type, const std::string& l, size_t c, char stop) {
625 switch (type) {
626 case ReadType::REST:
627 return l.size();
628 case ReadType::WORD:
629 while ((c < l.size()) && !is_blank(l[c]) && (l[c] != stop))
630 c++;
631 return c;
632 default:
633 // Numbers end where a following literal starts
634 return number_end(l, c, true, type != ReadType::INT);
635 }
636 }
637
638 void exec(const Block& b) {
639 for (const std::unique_ptr<Stmt>& s : b)
640 exec(*s);
641 }
642
643 void exec(const Stmt& s) {
644 spec_line = s.line;
645 switch (s.kind) {
647 for (const std::string& w : s.words) in.comments.push(w);
648 break;
649 case Stmt::Kind::STOP:
650 for (const std::string& w : s.words) in.stops.push(w);
651 break;
652 case Stmt::Kind::TOKENS: in.add_split(s.chars); break;
653 case Stmt::Kind::SEPARATORS: in.add_separators(s.chars); break;
654 case Stmt::Kind::TRAILING: trailing = true; break;
655 case Stmt::Kind::PARAM: param(s); break;
656 case Stmt::Kind::READ: read(s); break;
657 case Stmt::Kind::LIST: list(s); break;
658 case Stmt::Kind::LINE: line(s); break;
659 case Stmt::Kind::FIND: find(s); break;
660 case Stmt::Kind::SKIP: skip_lines(s); break;
661 case Stmt::Kind::EXPECT: expect(s); break;
662 case Stmt::Kind::INDEX: index(s); break;
663 case Stmt::Kind::REPEAT: repeat(s); break;
664 case Stmt::Kind::SECTIONS: sections(s); break;
665 case Stmt::Kind::INSTANCES: instances(s); break;
666 case Stmt::Kind::TYPE: type_ranges[&s] = range(s.type); break;
667 case Stmt::Kind::LET: set(s.name, eval(*s.expr)); break;
668 case Stmt::Kind::IF:
669 exec(truth(eval(*s.expr)) ? s.body : s.orelse);
670 break;
671 case Stmt::Kind::CHECK: check(s); break;
672 case Stmt::Kind::EACH: break;
673 }
674 }
675
682 void param(const Stmt& s) {
683 std::string v;
684 long long int iv;
685 double fv;
686 Value d;
687 if (s.expr)
688 d = eval(*s.expr);
689 if (!params.get(s.name, v)) {
690 if (!s.expr)
691 fail("parameter '" + s.name + "' must be given");
692 set(s.name, std::move(d));
693 } else if (s.expr && (d.type == ValueType::STRING)) {
694 set(s.name, Value::string(v));
695 } else if (parse_int(v, iv) && (!s.expr || (d.type == ValueType::INT))) {
696 set(s.name, Value::integer(iv));
697 } else if (parse_float(v, fv) && (!s.expr || (d.type == ValueType::FLOAT))) {
698 set(s.name, Value::real(fv));
699 } else if (!s.expr) {
700 set(s.name, Value::string(v));
701 } else {
702 fail("parameter '" + s.name + "' must be " + (d.type == ValueType::INT ? "an integer" : "a number") +
703 ", not " + quote(v));
704 }
705 }
706
708 void read(const Stmt& s) {
709 context.push(Context(s.name));
710 long long int o = offset(s);
711 Domain d(s.type, range(s.type));
712 if (s.dims.empty()) {
713 Value v = value(d);
714 offset(v, o);
715 store(s, std::move(v));
716 } else {
717 Seq<long long int> dims;
718 for (const std::unique_ptr<Expr>& e : s.dims)
719 dims.push(count(*e, "array size"));
720 if (s.type.read == ReadType::SYMBOL) {
721 store(s, symbols(s.type, dims[0], dims[1]));
722 } else if (s.expr) {
723 Value f = eval(*s.expr);
724 if ((f.depth > 0) || (f.type != ValueType::STRING))
725 fail("matrix layout must be a string");
726 store(s, layout(d, dims[0], dims[1], f.strs[0], o));
727 } else {
728 Value v = array(d, dims);
729 offset(v, o);
730 store(s, std::move(v));
731 }
732 }
733 context.pop();
734 }
735
737 void list(const Stmt& s) {
738 context.push(Context(s.name));
739 Value v(ValueType::INT);
740 if (!spare.empty()) {
741 v = std::move(spare.back());
742 spare.pop();
743 }
744 v.clear_list(s.type.read == ReadType::FLOAT ? ValueType::FLOAT :
746 Domain d(s.type, range(s.type));
747 try {
748 if (s.until_eol)
749 list_line(d, v);
750 else
751 list_until(s, d, v);
752 } catch (const ShapeError& e) {
753 fail(e, s.name);
754 }
755 v.lengths[0][0] = v.leaves();
756 offset(v, offset(s));
757 context.pop();
758 store(s, std::move(v));
759 }
761 void list_line(const Domain& d, Value& v) {
762 // The rest of the current line, or the next line if the current
763 // one is used up (skip_to_data() moves there)
764 if (!in.skip_to_line_data() && !in.skip_to_data())
765 fail("expected a line of values, found end of input");
766 while (in.skip_to_line_data())
767 push(d, v);
768 }
770 static bool same_number(const Value& x, const Value& y) {
771 if ((x.type == ValueType::INT) && (y.type == ValueType::INT))
772 return x.ints[0] == y.ints[0];
773 if ((x.type == ValueType::STRING) || (y.type == ValueType::STRING))
774 return false;
775 return x.as_double() == y.as_double();
776 }
778 void ints_until(const Domain& d, long long int stop, Value& v) {
779 for (;;) {
780 // The terminator need not be in the range
781 long long int x = int_scalar(d);
782 if (x == stop)
783 return;
784 if (!d.range.contains(x))
785 outside(d, token_start, in.pos);
786 v.ints.push(x);
787 }
788 }
790 void list_until(const Stmt& s, const Domain& d, Value& v) {
791 if ((d.type.read == ReadType::INT) && (s.sentinel->kind == Expr::Kind::INT)) {
792 ints_until(d, s.sentinel->i, v);
793 return;
794 }
795 Value stop = eval(*s.sentinel);
796 if (stop.depth > 0)
797 fail("list terminator must be a single value");
798 // Words end at the token spelling an integer terminator
799 if ((s.type.read == ReadType::WORD) && (stop.type == ValueType::INT))
800 stop = Value::string(std::to_string(stop.ints[0]));
801 if ((s.type.read == ReadType::WORD) && (stop.type == ValueType::FLOAT))
802 fail("a list of words needs a string or integer terminator");
803 if ((d.type.read == ReadType::INT) && (stop.type == ValueType::INT)) {
804 ints_until(d, stop.ints[0], v);
805 return;
806 }
807 for (;;) {
808 // A string terminator is compared before the token is read as
809 // a value, so "EOF" can end a list of numbers
810 if (stop.type == ValueType::STRING) {
811 if (!in.skip_to_data())
812 fail("expected " + quote(stop.strs[0]) + ", found end of input");
813 if (in.peek() == stop.strs[0]) {
814 (void) in.token();
815 return;
816 }
817 }
818 // The terminator need not be in the range
819 Value x = scalar(d);
820 if (same_number(x, stop))
821 return;
822 if (!fits(d, x))
823 outside(d, token_start, in.pos);
824 v.push(x);
825 }
826 }
827
830 void line(const Stmt& s) {
831 if (match(s.pattern))
832 return;
833 fail("expected a line matching \"" + s.pattern.source + "\"" +
834 (in.pos >= in.text.size() ? ", found end of input" : ""));
835 }
837 void find(const Stmt& s) {
838 while (!match(s.pattern)) {
839 if (!in.skip_to_data())
840 fail("no line matching \"" + s.pattern.source + "\" found");
841 in.to_eol();
842 }
843 }
845 void skip_lines(const Stmt& s) {
846 long long int n = count(*s.expr, "number of lines");
847 for (long long int k=0; k<n; k++) {
848 if (!in.skip_to_data())
849 fail("cannot skip a line at end of input");
850 in.to_eol();
851 }
852 }
854 void expect(const Stmt& s) {
855 for (const std::string& w : s.words) {
856 if (!in.skip_to_data())
857 fail("expected " + quote(w) + ", found end of input");
858 size_t p0 = in.pos;
859 std::string t = in.token();
860 if (t != w) {
861 in.pos = p0;
862 fail("expected " + quote(w) + ", found " + quote(t));
863 }
864 }
865 }
867 void index(const Stmt& s) {
868 if (rows.empty())
869 fail("'index' must be inside a repeat");
870 long long int want = rows.back() + count(*s.expr, "index base");
871 in.skip();
872 size_t p0 = in.pos;
873 Value v = scalar(ReadType::INT, describe(ReadType::INT));
874 if (v.ints[0] != want) {
875 in.pos = p0;
876 fail("expected index " + std::to_string(want) + ", found " + std::to_string(v.ints[0]));
877 }
878 }
879
881 bool until(const Stmt& s) {
882 if (!s.has_until || !in.skip_to_data())
883 return false;
884 std::string t = in.peek();
885 for (const std::string& w : s.words)
886 if (t == w) {
887 (void) in.token();
888 if (!s.store.empty())
889 set(s.store, Value::string(w));
890 return true;
891 }
892 return false;
893 }
894 std::string until_text(const Stmt& s) const {
895 std::string r;
896 for (int k=0; k<s.words.size(); k++)
897 r += (k > 0 ? " or " : "") + quote(s.words[k]);
898 return r;
899 }
900
908 bool may_be_skipped(void) const {
909 if (current == 0)
910 return false;
911 if (catalog)
912 return true;
913 if (!select)
914 return current != 1;
915 if (number > 0)
916 return current != number;
917 return instance_name(frames[instance_frame]) != want;
918 }
919
928 void reject(const std::string& e, const std::string& message) {
929 if (!may_be_skipped())
930 throw Error(e);
931 if (deferred_error.empty()) {
932 deferred_error = e;
933 deferred_message = message;
934 }
935 }
936
938 void check(const Stmt& s) {
939 std::string e;
940 if (!holds(s, e))
941 reject(e, s.message.empty() ? "check on line " + std::to_string(s.line) + " of the spec" : s.message);
942 }
943
944
946 Seq<Entry> instance(const Block& b, int n) {
947 current = n;
948 deferred_error.clear();
949 deferred_message.clear();
950 context.push(Context("instance", n));
951 frames.push(Seq<Entry>());
952 instance_frame = frames.size()-1;
953 try {
954 exec(b);
955 } catch (const Error& e) {
956 // The earlier rejection may explain the error
957 if (deferred_error.empty())
958 throw;
959 throw Error(std::string(e.what()) + "\n after an earlier error in the instance: " + deferred_message);
960 }
961 Seq<Entry> f = std::move(frames.back());
962 frames.pop();
963 context.pop();
964 current = 0;
965 return f;
966 }
967
969 static std::string instance_name(const Seq<Entry>& f) {
970 for (const Entry& e : f)
971 if ((e.name == "name") && (e.value.depth == 0)) {
972 if (e.value.type == ValueType::STRING) return e.value.strs[0];
973 if (e.value.type == ValueType::INT) return std::to_string(e.value.ints[0]);
974 }
975 return std::string();
976 }
977
994 void instances(const Stmt& s) {
995 select = params.get("instance", want);
996 long long int k = 0;
997 bool numbered = select && parse_int(want, k);
998 if (numbered && (k < 1))
999 fail("instance numbers start at 1");
1000 number = numbered ? k : -1;
1001 int n = 0;
1002 while (in.skip_to_data()) {
1003 n++;
1004 size_t start = in.pos;
1005 Seq<Entry> f = instance(s.body, n);
1006 spec_line = s.line;
1007 if (in.pos == start)
1008 fail("an instance must read some input");
1009 std::string name = instance_name(f);
1010 if (catalog) {
1011 names.push(Value::string(name));
1012 failures.push(Value::string(deferred_message));
1013 } else if (select ? ((number > 0) ? (number == n) : (name == want)) : (n == 1)) {
1014 // An instance selected by name may have been rejected before
1015 // its name was known
1016 if (!deferred_error.empty())
1017 throw Error(deferred_error);
1018 for (Entry& e : f)
1019 set(e.name, std::move(e.value));
1020 if (select) {
1021 selected = true;
1022 return;
1023 }
1024 }
1025 }
1026 instance_count = n;
1027 if (catalog) {
1028 // Keep the names only if every instance has one
1029 bool all = (n > 0);
1030 for (const std::string& v : names.strs)
1031 all = all && !v.empty();
1032 if (all)
1033 names.lengths[0][0] = n;
1034 else
1035 names = Value();
1036 bool failed = false;
1037 for (const std::string& m : failures.strs)
1038 failed = failed || !m.empty();
1039 if (failed)
1040 failures.lengths[0][0] = n;
1041 else
1042 failures = Value();
1043 return;
1044 }
1045 if (n == 0)
1046 fail("the file contains no instance");
1047 if (select)
1048 fail("there is no instance " + quote(want) + " (the file has " + std::to_string(n) + " instance" +
1049 (n == 1 ? "" : "s") + ")");
1050 if (n > 1)
1051 fail("the file has " + std::to_string(n) +
1052 " instances; select one with the parameter instance (a number from 1, or a name)");
1053 }
1054
1063 void repeat(const Stmt& s) {
1064 Seq<Decl> names;
1065 declared(s.body, names);
1066 long long int n = s.expr ? count(*s.expr, "repeat count") : -1;
1067 Seq<Column> columns;
1068 for (const Decl& d : names)
1069 columns.push(Column(d.type, d.depth));
1070 // Where each record starts, for errors in checks
1071 Value starts;
1072 // The frame of an iteration, kept between iterations for its memory
1073 Seq<Entry> frame;
1074 for (long long int r=0; (n < 0) || (r < n); r++) {
1075 if (s.until_eof && !in.skip_to_data())
1076 break;
1077 if (until(s))
1078 break;
1079 if (s.has_until && !in.skip_to_data())
1080 fail("expected " + until_text(s) + " before end of input");
1081 context.push(Context("repeat", r+1, n));
1082 frames.push(std::move(frame));
1083 rows.push(r);
1084 starts.ints.push(static_cast<long long int>(in.next_data()));
1085 size_t start = in.pos;
1086 exec(s.body);
1087 if (in.pos == start) {
1088 if (n < 0)
1089 fail("the body of a repeat until read no input");
1090 work(1);
1091 }
1092 rows.pop();
1093 Seq<Entry>& f = frames.back();
1094 for (int i=0; i<names.size(); i++) {
1095 Entry* e = nullptr;
1096 for (Entry& x : f)
1097 if (x.name == names[i].name)
1098 e = &x;
1099 try {
1100 if (e == nullptr)
1101 columns[i].skip();
1102 else
1103 columns[i].add(e->value);
1104 } catch (const ShapeError& err) {
1105 fail("'" + names[i].name + "' " + err.msg);
1106 }
1107 }
1108 // A list read in each iteration then needs no new memory
1109 for (Entry& e : f)
1110 if ((e.value.depth > 0) && (spare.size() < max_spare))
1111 spare.push(std::move(e.value));
1112 frame = std::move(frames.back());
1113 frame.clear();
1114 frames.pop();
1115 context.pop();
1116 spec_line = s.line;
1117 }
1118 for (int i=0; i<names.size(); i++)
1119 try {
1120 set(names[i].name, columns[i].finish());
1121 } catch (const ShapeError& err) {
1122 fail("'" + names[i].name + "' " + err.msg);
1123 }
1124 starts.lengths[0][0] = starts.ints.size();
1125 set(record_starts(s.id), std::move(starts));
1126 }
1127
1135 void sections(const Stmt& s) {
1136 // The line on which each arm matched, or 0
1137 Seq<int> seen;
1138 for (int k=0; k<s.arms.size(); k++)
1139 seen.push(0);
1140 std::string end = "the end of the input";
1141 Place end_at;
1142 for (;;) {
1143 spec_line = s.line;
1144 if (!in.skip_to_data()) {
1145 end_at = in.here();
1146 break;
1147 }
1148 Place at = in.here();
1149 if (until(s)) {
1150 end = until_text(s);
1151 end_at = at;
1152 break;
1153 }
1154 int found = -1;
1155 Seq<Capture> caps;
1156 for (int k=0; (found < 0) && (k < s.arms.size()); k++) {
1157 caps.clear();
1158 if (matches(s.arms[k].pattern, caps))
1159 found = k;
1160 }
1161 if (found < 0) {
1162 if (s.skip_other) {
1163 in.to_eol();
1164 continue;
1165 }
1166 std::string expected;
1167 for (int k=0; (k < s.arms.size()) && (k < 6); k++)
1168 expected += (k > 0 ? ", \"" : "\"") + s.arms[k].pattern.source + "\"";
1169 if (s.arms.size() > 6)
1170 expected += ", ...";
1171 fail("unexpected line; expected one of " + expected);
1172 }
1173 const Arm& a = s.arms[found];
1174 if (seen[found] > 0) {
1175 std::string m = "a second line matching \"" + a.pattern.source + "\"";
1176 reject(located(m + " (the first is on line " + std::to_string(seen[found]) + ")", at), m);
1177 } else {
1178 seen[found] = at.line;
1179 }
1180 take(caps);
1181 context.push(Context("section \"" + a.pattern.source + "\""));
1182 exec(a.body);
1183 context.pop();
1184 if (a.last) {
1185 end = "the line matching \"" + a.pattern.source + "\"";
1186 end_at = at;
1187 break;
1188 }
1189 }
1190 for (int k=0; k<s.arms.size(); k++)
1191 if (!s.arms[k].optional && (seen[k] == 0)) {
1192 std::string p = "\"" + s.arms[k].pattern.source + "\"";
1193 std::string e = located("expected a line matching " + p + " before " + end, end_at);
1194 // At the end of the input, no later instance can be hidden
1195 if (!in.skip_to_data())
1196 throw Error(e);
1197 reject(e, "no line matching " + p);
1198 return;
1199 }
1200 }
1201
1203 Value symbols(const Type& t, long long int r, long long int c) {
1204 if (r*c > INT_MAX)
1205 fail("array is too large");
1206 if (c == 0)
1207 work(r);
1208 Value g;
1209 for (long long int i=0; i<r; i++)
1210 for (long long int j=0; j<c; j++) {
1211 char ch;
1212 for (;;) {
1213 in.skip();
1214 if (in.pos >= in.text.size())
1215 fail("expected a symbol for row " + std::to_string(i+1) + ", column " + std::to_string(j+1) +
1216 ", found end of input");
1217 ch = in.text[in.pos];
1218 if (t.strip.find(ch) == std::string::npos)
1219 break;
1220 in.advance(in.pos+1);
1221 }
1222 size_t k = t.alphabet.find(ch);
1223 if (t.blank.find(ch) != std::string::npos) {
1224 g.ints.push(0);
1225 } else if (k != std::string::npos) {
1226 long long int v;
1227 if (!add(static_cast<long long int>(k), t.base, v))
1228 fail("integer overflow in the value of a symbol");
1229 g.ints.push(v);
1230 } else {
1231 fail("unexpected symbol " + quote(std::string(1, ch)) + ", expected one of " + quote(t.alphabet + t.blank));
1232 }
1233 in.advance(in.pos+1);
1234 }
1235 // The structure is built after reading, as for arrays
1236 g.depth = 2;
1237 g.lengths.clear();
1238 g.lengths.push(Seq<int>());
1239 g.lengths[0].push(static_cast<int>(r));
1240 g.lengths.push(Seq<int>());
1241 for (long long int i=0; i<r; i++)
1242 g.lengths[1].push(static_cast<int>(c));
1243 return g;
1244 }
1245 };
1246
1247 }
1248
1249 Data
1250 SpecImpl::read(const std::string& input, const std::string& o, const Params& p, bool catalog) const {
1251 std::shared_ptr<DataImpl> d = std::make_shared<DataImpl>();
1252 Interpreter i(*this, input, o, p, catalog);
1253 i.run(*d);
1254 Data r;
1255 r.impl = d;
1256 return r;
1257 }
1258
1259}}
1260
1261// STATISTICS: instance-any
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
Named values read from an instance.
Definition instance.hh:406
Evaluator of the expressions of a spec on an input.
Definition eval.hpp:367
Values for the param statements of a spec.
Definition instance.hh:364
Data read(const std::string &input, const std::string &origin, const Params &p, bool catalog) const
Read input from origin.
Definition reader.cpp:1250
static Value real(double v)
Float scalar.
Definition impl.hpp:287
static Value string(const std::string &v)
String scalar.
Definition impl.hpp:292
static Value integer(long long int v)
Integer scalar.
Definition impl.hpp:282
static const IntSet empty
Empty set.
Definition int.hh:302
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition script.cpp:42
void check(const FloatVal &n, const char *l)
Check whether float n is a valid number, otherwise throw out of limits exception with information l.
Definition limits.hpp:44
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 parse_float(const std::string &t, double &v)
Parse decimal float t into v, and return whether it is one.
Definition spec.cpp:72
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
void declared(const Block &b, Seq< Decl > &out)
Add the names that block b may define to out.
Definition spec.cpp:1207
ReadType
What a declaration or a capture reads.
Definition impl.hpp:520
@ NUM
An integer if possible, otherwise a float.
Definition impl.hpp:523
@ REST
The rest of the line as a string.
Definition impl.hpp:525
@ SYMBOL
A character of an alphabet, as an integer.
Definition impl.hpp:526
@ WORD
A token as a string.
Definition impl.hpp:524
bool parse_int(const std::string &t, long long int &v)
Parse decimal integer t into v, and return whether it is one.
Definition spec.cpp:62
size_t number_end(const std::string &s, size_t p, bool sign, bool real)
Return where the number starting at position p of s ends.
Definition impl.hpp:90
std::string quote(const std::string &s)
Return s in single quotes, with newlines and tabs escaped.
Definition eval.cpp:43
bool is_blank(char c)
Test whether c is white space within a line.
Definition impl.hpp:72
Seq< std::unique_ptr< Stmt > > Block
Sequence of statements.
Definition impl.hpp:603
bool is_internal(const std::string &n)
Test whether n is a name used internally (see record_starts).
Definition impl.hpp:515
RelTest holds(VX x, VX y)
Test whether x and y are equal.
Definition rel.hpp:145
ExecStatus scan(Space &home, IdxViewArray< VA > &iv, VB x0, VC x1, Propagator &p, RelTest rt)
Definition view.hpp:217
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition aliases.hpp:158
Gecode::FloatVal a(-8, 5)
Expr eval(const LinInstr *pc, Expr reg[])
Evaluate linear instructions.
Definition mm-lin.cpp:69
Case sections("Read::Sections", [](void) { const char *spec="sections until \"EOF\" {\n" " \"N : {n:int}\"\n" " \"DATA\" { x[n]: int }\n" " \"NAME : {name:word}\" optional\n" "}\n";Data d=read(spec, "NAME : a\nN: 2\nDATA\n5 6\nEOF\n");CHECK(d.integer("n")==2);CHECK(equal(d.ints("x"), {5, 6}));CHECK(d.text("name")=="a");CHECK(read(spec, "N : 1\nDATA\n4").ints("x").size()==1);CHECK(fails(spec, "N : 1\nXYZZY_PLUGH\n", "expected one of"));CHECK(read("sections skip other { \"v: {v:int}\" }", "junk\nv: 3\nmore junk\n").integer("v")==3);CHECK(fails(spec, "N : 1\nEOF\n", "test.txt:2:1: expected a line matching \"DATA\" before 'EOF'"));CHECK(fails(spec, "NAME : a\n", "expected a line matching \"N : {n:int}\" before the end of the input"));CHECK(fails(spec, "N : 1\nDATA\n4\nN : 2\n", "test.txt:4:1: a second line matching \"N : {n:int}\" (the first is on line 1)"));CHECK(fails(spec, "NAME : a\nN : 1\nDATA\n4\nNAME : b\n", "a second line matching \"NAME : {name:word}\""));const char *last="sections { \"a {a:int}\" \"end\" last } y: int";CHECK(read(last, "a 1\nend\n5").integer("y")==5);CHECK(fails(last, "a 1\n5", "expected one of"));CHECK(fails(last, "a 1", "expected a line matching \"end\" before the end of the input"));CHECK(fails(last, "end\n5", "test.txt:1:1: expected a line matching \"a {a:int}\" before the line matching \"end\""));const char *optional_last="sections { \"a {a:int}\" \"end\" optional last }";CHECK(read(optional_last, "a 1").integer("a")==1);CHECK(read(optional_last, "a 1\nend").integer("a")==1);return true;})
Case lists("Read::Lists", [](void) { Data d=read("list a: int until 0 list b: int until eol list c: int until eol list w: word until \"END\"", "1 2\n 3 0 4 5\n6 7\nx y END");CHECK(equal(d.ints("a"), {1, 2, 3}));CHECK(equal(d.ints("b"), {4, 5}));CHECK(equal(d.ints("c"), {6, 7}));CHECK(d.size("w")==2);CHECK(d.text("w", {1})=="y");return true;})
Case instances("Read::Instances", [](void) { const char *spec="comment \"+++\"\n" "instances {\n" " sections skip other {\n" " \"instance {name:word}\" optional\n" " \"{n:int}\" last { x[n]: int }\n" " }\n" "}\n";const char *text="header text\ninstance a\n2\n1 2\n+++\n" "instance b\ndescription\n1\n7\n+++ end\n";Params by_name, by_number, bad;by_name.set("instance", "b");by_number.set("instance", "1");bad.set("instance", "3");CHECK(equal(read(spec, text, by_name).ints("x"), {7}));CHECK(equal(read(spec, text, by_number).ints("x"), {1, 2}));CHECK(read(spec, text, by_number).text("name")=="a");CHECK(fails([&](void) {(void) read(spec, text, bad);}, "there is no instance '3' (the file has 2 instances)"));CHECK(fails(spec, text, "the file has 2 instances; select one"));CHECK(equal(read(spec, "3\n4 5 6\n").ints("x"), {4, 5, 6}));Spec s=Spec::parse(spec, "s");Data c=s.catalog_text(text);CHECK(c.integer("instances")==2);CHECK(c.text("name", {1})=="b");Data c1=s.catalog_text("3\n4 5 6\n");CHECK((c1.integer("instances")==1) &&!c1.has("name"));CHECK(Spec::parse("a: int", "s").catalog_text("5").integer("instances")==1);CHECK(fails(spec, "1\n2\njunk\n", "expected a line matching \"{n:int}\""));CHECK(fails("instances { a: int }", "", "the file contains no instance"));CHECK(fails([](void) {(void) Spec::parse("instances { a: int } b: int", "s");}, "'instances' must be the last statement"));CHECK(fails([](void) {(void) Spec::parse("repeat 2 { instances { a: int } }", "s");}, "'instances' must be at the top level"));CHECK(fails("instances { if 0 > 1 { a: int } }", "5", "an instance must read some input"));return true;})
Data read(const char *spec, const char *text, const Params &p=Params())
Read text with the spec spec.
Definition instance.cpp:64
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
const int r[4][2]
Definition dom.cpp:152