51 if ((stat(
path.c_str(), &st) == 0) && ((st.st_mode & S_IFMT) == S_IFDIR))
53 std::ifstream f(
path.c_str(), std::ios::binary);
56 std::ostringstream ss;
67 v = std::strtoll(t.c_str(), &end, 10);
68 return (errno == 0) && (end == t.c_str() + t.size());
74 if (t.empty() || (
number_end(t, 0,
true,
true) != t.size()))
77 std::istringstream in(t);
78 in.imbue(std::locale::classic());
80 return !in.fail() && (in.peek() == EOF);
84 fail_at(
const std::string& origin,
int line,
const std::string& m) {
85 throw Error(origin +
":" + std::to_string(line) +
": " + m);
94 enum class Kind { IDENT, INT, FLOAT, STRING, PUNCT, END } kind;
107 : kind(Kind::END), i(0), f(0.0), line(0), glued(false) {}
117 unescape(
char e,
const std::string& origin,
int line) {
119 case 'n':
return '\n';
120 case 't':
return '\t';
121 case '\\':
case '"':
return e;
122 case '\n':
fail_at(origin, line,
"unterminated string");
124 fail_at(origin, line, std::string(
"unknown escape '\\") + e +
"' in string (use \\n, \\t, \\\\, or \\\")");
130 name_end(
const std::string& src,
size_t p) {
131 while ((p < src.size()) &&
is_alnum(src[p]))
137 const std::string gecode_prefix =
"gecode.";
142 at_gecode_name(
const std::string& src,
size_t p,
size_t q) {
143 return (src.compare(p, q-p,
"gecode") == 0) && (q+1 < src.size()) && (src[q] ==
'.') &&
is_alnum(src[q+1]);
148 is_gecode_name(
const std::string& n) {
149 return n.compare(0, gecode_prefix.size(), gecode_prefix) == 0;
154 lex(
const std::string& src,
const std::string& origin, Seq<Token>& toks,
int line = 1) {
157 while (p < src.size()) {
159 if (c ==
'\n') { line++; p++; space =
true;
continue; }
160 if (
is_space(c)) { p++; space =
true;
continue; }
162 while ((p < src.size()) && (src[p] !=
'\n')) p++;
174 while ((p < src.size()) && (src[p] !=
'"')) {
176 fail_at(origin, line,
"unterminated string");
177 if (src[p] ==
'\\') {
178 if (p+1 >= src.size())
180 t.text += unescape(src[p+1], origin, line);
187 fail_at(origin, line,
"unterminated string");
189 t.kind = Token::Kind::STRING;
194 for (
size_t k=p; k+1<q; k++)
195 if (src.compare(k, 2,
"..") == 0) {
199 t.text = src.substr(p, q-p);
201 bool flt = (t.text.find_first_not_of(
"0123456789") != std::string::npos);
202 t.kind = flt ? Token::Kind::FLOAT : Token::Kind::INT;
204 fail_at(origin, line,
"bad number " + t.text);
206 size_t q = name_end(src, p);
208 if (at_gecode_name(src, p, q))
209 q = name_end(src, q+1);
210 t.text = src.substr(p, q-p);
212 t.kind = Token::Kind::IDENT;
215 static const char* ops[] = {
"..<",
"..",
"==",
"!=",
"<=",
">=",
"&&",
"||"};
216 t.kind = Token::Kind::PUNCT;
217 t.text = std::string(1, c);
218 for (
const char* o : ops)
219 if ((t.text.size() == 1) && (src.compare(p, std::strlen(o), o) == 0))
221 if ((t.text.size() == 1) && (std::strchr(
"{}[]()=<>+-*/%^!,.:", c) ==
nullptr))
222 fail_at(origin, line, std::string(
"unexpected character '") + c +
"'");
233 bool read_type(
const std::string& t, ReadType& r) {
234 if (t ==
"int")
r = ReadType::INT;
235 else if (t ==
"float")
r = ReadType::FLOAT;
236 else if (t ==
"num")
r = ReadType::NUM;
237 else if (t ==
"word")
r = ReadType::WORD;
238 else if (t ==
"rest")
r = ReadType::REST;
245 bool is_name(
const std::string& s) {
256 flush(Pattern& pat, std::string& lit) {
258 Pattern::Item it(Pattern::Item::Kind::LIT);
260 pat.items.push(std::move(it));
267 ends_word(
const Pattern::Item& it) {
268 typedef Pattern::Item::Kind Kind;
269 return (it.kind == Kind::CAP) || (it.kind == Kind::VAR) ||
270 ((it.kind == Kind::LIT) &&
is_alnum(it.text[it.text.size()-1]));
275 starts_word(
const Pattern::Item& it) {
276 typedef Pattern::Item::Kind Kind;
277 return (it.kind == Kind::CAP) || (it.kind == Kind::VAR) || ((it.kind == Kind::LIT) &&
is_alnum(it.text[0]));
283 compile(
const std::string& src, Seq<std::string>& types) {
284 typedef Pattern::Item Item;
289 while (p < src.size()) {
293 while ((p < src.size()) &&
is_blank(src[p])) p++;
294 pat.items.push(Item(Item::Kind::SPACE));
295 }
else if (c ==
'{') {
297 size_t q = src.find(
'}', p);
298 if (q == std::string::npos)
299 throw Error(
"unterminated capture in pattern \"" + src +
"\"");
300 std::string cap = src.substr(p+1, q-p-1);
302 if (!cap.empty() && (cap[0] ==
'$')) {
303 Item it(Item::Kind::VAR);
304 it.text = cap.substr(1);
305 if (!is_name(it.text))
306 throw Error(
"missing or bad name in pattern \"" + src +
"\"");
307 pat.items.push(std::move(it));
310 Item it(Item::Kind::CAP);
311 size_t colon = cap.find(
':');
312 it.text = cap.substr(0, colon);
313 if (!is_name(it.text) && !it.text.empty() && (it.text !=
"_"))
314 throw Error(
"capture name '" + it.text +
"' in pattern \"" + src +
"\" is not a name");
315 types.push((colon == std::string::npos) ?
"word" : cap.substr(colon+1));
316 pat.items.push(std::move(it));
317 }
else if (src.compare(p, 3,
"...") == 0) {
319 if (src.find_first_not_of(
" \t", p+3) != std::string::npos)
320 throw Error(
"'...' must end the pattern \"" + src +
"\"");
321 pat.items.push(Item(Item::Kind::ANY));
331 for (
int k=1; k+1<pat.items.size(); k++)
332 if (pat.items[k].kind == Item::Kind::SPACE)
333 pat.items[k].required = ends_word(pat.items[k-1]) && starts_word(pat.items[k+1]);
359 Parser(
const std::string& src,
const std::string& o)
360 : origin(o), p(0), depth(0), nesting(0),
repeats(0), repeat_start(false), each_ok(false) {
361 lex(src, origin, toks);
364 void parse(SpecImpl& s) {
365 while (peek().kind != Token::Kind::END) {
366 if (keyword(
"format")) {
368 if ((peek().kind != Token::Kind::IDENT) && (peek().kind != Token::Kind::STRING))
369 fail(
"expected a format name, found " + describe(peek()));
370 s.name = next().text;
372 while (at_name_joiner()) {
373 s.name += next().text;
374 s.name += next().text;
377 if (!s.body.empty() && (s.body.back()->kind == Stmt::Kind::INSTANCES))
378 fail(
"'instances' must be the last statement of the spec");
379 s.body.push(statement());
385 for (
const BoundName& b : bound_all)
386 for (
const Decl& d : names)
387 if (
d.name ==
b.name)
388 fail_at(origin,
b.line,
"'" +
b.name +
"' is bound by a comprehension but is also a name in the spec");
389 for (
const TypeName& t : types_all)
390 for (
const Decl& d : names)
391 if (
d.name == t.name)
392 fail_at(origin, t.def->line,
"'" + t.name +
"' names a type, so it cannot also name a value");
413 Seq<std::string> bound;
415 Seq<BoundName> bound_all;
419 Seq<TypeName> types_all;
421 static const int max_nesting = 256;
423 const Token& peek(
void)
const {
426 const Token& next(
void) {
427 const Token& t = toks[p];
428 if (p+1 < toks.size()) p++;
431 [[noreturn]]
void fail(
const std::string& m)
const {
432 fail_at(origin, peek().line, m);
434 static std::string describe(
const Token& t) {
435 if (t.kind == Token::Kind::END)
return "end of spec";
436 if (t.kind == Token::Kind::STRING)
return "\"" + t.text +
"\"";
437 return "'" + t.text +
"'";
439 bool keyword(
const char* k)
const {
440 return (peek().kind == Token::Kind::IDENT) && (peek().text == k);
442 bool punct(
const char* k)
const {
443 return (peek().kind == Token::Kind::PUNCT) && (peek().text == k);
447 bool at_name_joiner(
void)
const {
448 if (!(punct(
"-") || punct(
".")) || !peek().glued || (p+1 >= toks.size()))
450 const Token& t = toks[p+1];
451 return t.glued && ((t.kind == Token::Kind::IDENT) || (t.kind == Token::Kind::INT));
453 void expect_punct(
const char* k) {
455 fail(std::string(
"expected '") + k +
"', found " + describe(peek()));
458 void expect_keyword(
const char* k) {
460 fail(std::string(
"expected '") + k +
"', found " + describe(peek()));
463 std::string ident(
const char* what) {
464 if (peek().kind != Token::Kind::IDENT)
465 fail(std::string(
"expected ") + what +
", found " + describe(peek()));
469 std::string new_name(
const char* what) {
470 std::string n = ident(what);
471 if (is_gecode_name(n))
472 fail(
"'" + n +
"' cannot be defined: names starting with '" + gecode_prefix +
"' are Gecode constants");
475 std::string string(
const char* what) {
476 if (peek().kind != Token::Kind::STRING)
477 fail(std::string(
"expected ") + what +
" (a string), found " + describe(peek()));
480 Pattern pattern(
void) {
481 int line = peek().line;
482 std::string s = string(
"a line pattern");
484 Seq<std::string> texts;
486 pat = compile(s, texts);
487 }
catch (
const Error& e) {
488 fail_at(origin, line, e.what());
491 for (Pattern::Item& it : pat.items)
492 if (it.kind == Pattern::Item::Kind::CAP) {
493 it.type = capture_type(texts[k++], line);
494 if (it.type.read == ReadType::SYMBOL)
495 fail_at(origin, line,
"a capture cannot be of an alphabet type");
500 Type capture_type(
const std::string& text,
int line) {
503 lex(text, origin, sub, line);
505 fail_at(origin, line,
"a capture needs a type after ':'");
506 std::swap(toks, sub);
510 if (peek().kind != Token::Kind::END)
511 fail(
"unexpected " + describe(peek()) +
" in the capture type '" + text +
"'");
512 std::swap(toks, sub);
517 void enter(
int& n,
const char* what) {
518 if (++n > max_nesting)
519 fail(std::string(what) +
" are nested too deeply");
523 enter(depth,
"blocks");
525 int scope =
types.size();
527 while (!punct(
"}")) {
528 if (peek().kind == Token::Kind::END)
533 while (
types.size() > scope)
538 std::unique_ptr<Expr> integer(
long long int v) {
539 std::unique_ptr<Expr> e(
new Expr(Expr::Kind::INT));
545 bool accept(
const char* k) {
558 typedef void (Parser::*Parse)(Stmt& s,
const std::string& kw);
575 static const Keyword* statement_keyword(
const std::string& k) {
576 static const Keyword statements[] = {
577 {
"comment", Stmt::Kind::COMMENT, &Parser::words,
true},
578 {
"stop", Stmt::Kind::STOP, &Parser::words,
true},
579 {
"expect", Stmt::Kind::EXPECT, &Parser::words,
false},
580 {
"tokens", Stmt::Kind::TOKENS, &Parser::chars,
true},
581 {
"separators", Stmt::Kind::SEPARATORS, &Parser::chars,
true},
582 {
"ignore", Stmt::Kind::TRAILING, &Parser::trailing,
true},
583 {
"param", Stmt::Kind::PARAM, &Parser::param,
false},
584 {
"list", Stmt::Kind::LIST, &Parser::list,
false},
585 {
"line", Stmt::Kind::LINE, &Parser::line_pattern,
false},
586 {
"find", Stmt::Kind::FIND, &Parser::line_pattern,
false},
587 {
"skip", Stmt::Kind::SKIP, &Parser::skip,
false},
588 {
"index", Stmt::Kind::INDEX, &Parser::index,
false},
589 {
"repeat", Stmt::Kind::REPEAT, &Parser::repeat,
false},
590 {
"each", Stmt::Kind::EACH, &Parser::each,
false},
591 {
"instances", Stmt::Kind::INSTANCES, &Parser::instances,
false},
592 {
"sections", Stmt::Kind::SECTIONS, &Parser::sections,
false},
593 {
"if", Stmt::Kind::IF, &Parser::conditional,
false},
594 {
"let", Stmt::Kind::LET, &Parser::let,
false},
595 {
"check", Stmt::Kind::CHECK, &Parser::check,
false},
596 {
"type", Stmt::Kind::TYPE, &Parser::type_def,
false}
598 for (
const Keyword& e : statements)
610 bool at_declaration(
int k)
const {
611 if (toks[k].kind != Token::Kind::IDENT)
614 while ((toks[k].kind == Token::Kind::PUNCT) && (toks[k].text ==
"[")) {
617 if (toks[k].kind == Token::Kind::END)
619 if (toks[k].kind == Token::Kind::PUNCT)
620 open += (toks[k].text ==
"[") ? 1 : ((toks[k].text ==
"]") ? -1 : 0);
624 return (toks[k].kind == Token::Kind::PUNCT) && (toks[k].text ==
":");
627 std::unique_ptr<Stmt> statement(
void) {
628 const Token& t = peek();
629 each_ok = repeat_start;
630 repeat_start =
false;
631 if (t.kind != Token::Kind::IDENT)
632 fail(
"expected a statement, found " + describe(t));
633 if (at_declaration(p)) {
634 std::unique_ptr<Stmt> s(
new Stmt(Stmt::Kind::READ, t.line));
638 const Keyword* e = statement_keyword(t.text);
640 fail(
"unknown statement '" + t.text +
"'");
641 if (e->setting && (depth > 0))
642 fail(
"the setting '" + t.text +
"' must be at the top level of the spec");
643 std::unique_ptr<Stmt> s(
new Stmt(e->kind, t.line));
644 std::string kw = next().text;
645 (this->*e->parse)(*s, kw);
650 void words(Stmt& s,
const std::string&) {
651 s.words.push(
string(s.kind == Stmt::Kind::EXPECT ?
"a literal token" :
"a line prefix"));
652 while (peek().kind == Token::Kind::STRING)
653 s.words.push(next().text);
656 void chars(Stmt& s,
const std::string&) {
657 s.chars = string(s.kind == Stmt::Kind::TOKENS ?
"single-character tokens" :
"separator characters");
660 void trailing(Stmt&,
const std::string&) {
661 expect_keyword(
"trailing");
664 std::string defined(
const char* what) {
665 std::string n = new_name(what);
667 fail(
"'_' cannot be defined here");
671 void param(Stmt& s,
const std::string&) {
672 s.name = defined(
"a parameter name");
684 bool option(
const char* k) {
685 return !at_declaration(p) && accept(k);
688 static bool ends_range(
const std::string& k) {
689 return (statement_keyword(k) !=
nullptr) || (k ==
"layout") || (k ==
"offset") || (k ==
"until");
692 bool at_upper_bound(
void)
const {
693 const Token& t = peek();
695 case Token::Kind::IDENT:
696 return !ends_range(t.text) && !at_declaration(p);
697 case Token::Kind::PUNCT:
698 return punct(
"(") || punct(
"-") || punct(
"!");
699 case Token::Kind::END:
706 const Stmt* named_type(
const std::string& n)
const {
707 for (
int k=
types.size(); k--; )
708 if (types[k].name == n)
713 static bool is_base_type(
const std::string& n) {
715 return read_type(n, r) || (n ==
"alphabet");
726 if (peek().kind == Token::Kind::IDENT) {
727 const std::string& n = peek().text;
728 if (read_type(n, t.read)) {
732 if (n ==
"alphabet") {
737 if (
const Stmt* d = named_type(n)) {
739 Type u =
d->type.use(d);
744 if (!punct(
"..") && !punct(
"..<")) {
745 std::unique_ptr<Expr> lo =
expr();
746 if (!punct(
"..") && !punct(
"..<")) {
747 if (lo->kind == Expr::Kind::NAME)
748 fail(
"unknown type '" + lo->s +
"'");
749 fail(
"expected '..' or '..<' after the lower bound of a range, found " + describe(peek()));
751 t.lo = std::move(lo);
753 t.exclusive = punct(
"..<");
755 if (at_upper_bound())
757 if (t.exclusive && !t.hi)
758 fail(
"'..<' needs an upper bound");
760 fail(
"a range needs a lower or an upper bound");
764 void alphabet(Type& t) {
765 t.read = ReadType::SYMBOL;
766 t.alphabet = string(
"an alphabet");
768 if (option(
"blank")) {
769 t.blank = string(
"blank symbols");
770 }
else if (option(
"strip")) {
771 t.strip = string(
"symbols to strip");
772 }
else if (option(
"base")) {
773 bool neg = punct(
"-");
776 if (peek().kind != Token::Kind::INT)
777 fail(
"expected an integer, found " + describe(peek()));
778 t.base =
neg ? -next().i : next().i;
785 static bool numeric(
const Type& t) {
786 return (t.read == ReadType::INT) || (t.read == ReadType::FLOAT) || (t.read == ReadType::NUM);
789 void offset(Stmt& s) {
790 if (!option(
"offset"))
792 if (!numeric(s.type))
793 fail(
"'offset' needs numbers");
797 void declaration(Stmt& s) {
798 s.name = new_name(
"a name");
806 if ((s.type.read == ReadType::REST) && !s.dims.empty())
807 fail(
"'rest' values cannot be arrays");
808 if ((s.type.read == ReadType::SYMBOL) && (s.dims.size() != 2))
809 fail(
"an alphabet type needs a two-dimensional array");
810 if (option(
"layout")) {
811 if ((s.dims.size() != 2) || !numeric(s.type))
812 fail(
"'layout' needs a two-dimensional array of numbers");
818 void list(Stmt& s,
const std::string&) {
819 s.name = new_name(
"a name");
822 if ((s.type.read == ReadType::REST) || (s.type.read == ReadType::SYMBOL))
823 fail(
"a list cannot be of 'rest' or of an alphabet type");
824 expect_keyword(
"until");
832 void type_def(Stmt& s,
const std::string&) {
833 s.name = defined(
"a type name");
834 if (is_base_type(s.name))
835 fail(
"'" + s.name +
"' is a base type");
836 if (named_type(s.name) !=
nullptr)
837 fail(
"the type '" + s.name +
"' is already defined");
847 void line_pattern(Stmt& s,
const std::string&) {
848 s.pattern = pattern();
851 void skip(Stmt& s,
const std::string&) {
852 if (accept(
"line")) {
856 expect_keyword(
"lines");
860 void index(Stmt& s,
const std::string&) {
864 void until(Stmt& s) {
866 s.words.push(
string(
"a terminating token"));
867 while (peek().kind == Token::Kind::STRING)
868 s.words.push(next().text);
870 s.store = new_name(
"a name");
873 void repeat(Stmt& s,
const std::string&) {
875 if (accept(
"until")) {
884 s.list = new_name(
"a name for the records");
887 repeat_start =
false;
888 if (!s.body.empty() && (s.body[0]->kind == Stmt::Kind::EACH))
889 s.each = s.body[0]->name;
892 void each(Stmt& s,
const std::string&) {
894 fail(
"'each' must be the first statement of a repeat, and comes at most once");
895 s.name = new_name(
"a name for each record");
898 void instances(Stmt& s,
const std::string&) {
900 fail(
"'instances' must be at the top level of the spec");
904 void sections(Stmt& s,
const std::string&) {
906 if (accept(
"until")) {
908 }
else if (accept(
"skip")) {
909 expect_keyword(
"other");
916 while (!punct(
"}")) {
917 if (peek().kind == Token::Kind::END)
920 a.pattern = pattern();
921 a.optional = accept(
"optional");
922 a.last = accept(
"last");
925 s.arms.push(std::move(a));
930 void conditional(Stmt& s,
const std::string&) {
933 if (accept(
"else")) {
936 enter(depth,
"blocks");
937 s.orelse.push(statement());
945 void let(Stmt& s,
const std::string&) {
946 s.name = defined(
"a name");
951 void check(Stmt& s,
const std::string&) {
953 if (peek().kind == Token::Kind::STRING)
954 s.message = next().text;
959 std::unique_ptr<Expr>
expr(
void) {
964 static int binary_op(
const Token& t, Expr::Op& op) {
965 static const struct {
966 const char* text; Expr::Op op;
int precedence;
968 {
"||", Expr::Op::OR, 1}, {
"&&", Expr::Op::AND, 2},
969 {
"==", Expr::Op::EQ, 3}, {
"!=", Expr::Op::NE, 3},
970 {
"<", Expr::Op::LT, 4}, {
">", Expr::Op::GT, 4},
971 {
"<=", Expr::Op::LE, 4}, {
">=", Expr::Op::GE, 4},
972 {
"+", Expr::Op::ADD, 5}, {
"-", Expr::Op::SUB, 5},
973 {
"*", Expr::Op::MUL, 6}, {
"/", Expr::Op::DIV, 6}, {
"%", Expr::Op::MOD, 6}
975 if (t.kind == Token::Kind::PUNCT)
976 for (
const auto& o : ops)
977 if (t.text == o.text) {
984 std::unique_ptr<Expr> binary(
int min) {
985 std::unique_ptr<Expr> lhs =
unary();
990 int prec = binary_op(peek(), op);
991 if ((prec < 0) || (prec < min))
993 enter(nesting,
"expressions");
995 std::unique_ptr<Expr> e(
new Expr(Expr::Kind::BINARY));
998 e->args.push(std::move(lhs));
999 e->args.push(binary(prec+1));
1005 std::unique_ptr<Expr>
unary(
void) {
1006 enter(nesting,
"expressions");
1007 std::unique_ptr<Expr> e;
1008 if (punct(
"-") || punct(
"!")) {
1009 e.reset(
new Expr(Expr::Kind::UNARY));
1010 e->op = punct(
"-") ? Expr::Op::NEG : Expr::Op::NOT;
1012 e->args.push(
unary());
1021 std::unique_ptr<Expr>
power(
void) {
1022 std::unique_ptr<Expr> e = postfix();
1025 std::unique_ptr<Expr> x(
new Expr(Expr::Kind::BINARY));
1026 x->op = Expr::Op::POW;
1028 x->args.push(std::move(e));
1029 x->args.push(
unary());
1033 std::unique_ptr<Expr> postfix(
void) {
1034 std::unique_ptr<Expr> e = primary();
1037 while (punct(
"[") || punct(
".")) {
1038 bool field = punct(
".");
1040 enter(nesting,
"expressions");
1042 std::unique_ptr<Expr> x(
new Expr(field ? Expr::Kind::FIELD : Expr::Kind::INDEX));
1043 x->args.push(std::move(e));
1045 x->s = ident(
"a field name");
1047 x->args.push(
expr());
1058 void check_call(
const Expr& e,
int line) {
1059 const std::string&
f = e.s;
1060 int n = e.args.size();
1063 ok = (n == 1) && (e.args[0]->kind == Expr::Kind::NAME);
1064 else if ((f ==
"count") || (f ==
"size"))
1066 else if ((f ==
"min") || (f ==
"max") || (f ==
"sum") || (f ==
"distinct"))
1068 else if ((f ==
"all") || (f ==
"any"))
1069 fail_at(origin, line,
"'" + f +
"' needs the form " + f +
"(x in a: e)");
1071 fail_at(origin, line,
"unknown function '" + f +
"'");
1073 fail_at(origin, line,
"wrong arguments for function '" + f +
"'");
1076 long long int gecode_constant(
const std::string& n,
int line) {
1077 static const struct {
1078 const char* name;
long long int value;
1084 for (
const auto& c : constants) {
1087 known += (known.empty() ?
"" :
", ") + std::string(
c.name);
1089 fail_at(origin, line,
"unknown Gecode constant '" + n +
"' (known: " + known +
")");
1092 bool at_comprehension(
const std::string& f)
const {
1093 if ((f !=
"all") && (f !=
"any") && (f !=
"sum") && (f !=
"count"))
1095 if ((peek().kind != Token::Kind::IDENT) || (p+1 >= toks.size()))
1097 const Token& t = toks[p+1];
1098 return (t.kind == Token::Kind::IDENT) && (t.text ==
"in");
1101 std::unique_ptr<Expr> comprehension(
const std::string& f) {
1102 std::unique_ptr<Expr> e(
new Expr(Expr::Kind::COMPREHENSION));
1105 b.line = peek().line;
1106 b.name = new_name(
"a name");
1108 fail(
"'_' cannot be bound");
1109 for (
const std::string& o : bound)
1111 fail(
"'" +
b.name +
"' is already bound by an enclosing comprehension");
1113 expect_keyword(
"in");
1115 e->args.push(
expr());
1118 e->args.push(
expr());
1124 std::unique_ptr<Expr> primary(
void) {
1125 const Token& t = peek();
1126 if (t.kind == Token::Kind::INT)
1127 return integer(next().i);
1128 if (t.kind == Token::Kind::FLOAT) {
1129 std::unique_ptr<Expr> e(
new Expr(Expr::Kind::FLOAT));
1133 if (t.kind == Token::Kind::STRING) {
1134 std::unique_ptr<Expr> e(
new Expr(Expr::Kind::STR));
1140 std::unique_ptr<Expr> e =
expr();
1144 if ((t.kind == Token::Kind::IDENT) && is_gecode_name(t.text)) {
1146 return integer(gecode_constant(next().text, line));
1148 if (t.kind == Token::Kind::IDENT) {
1150 std::string n = next().text;
1153 if (at_comprehension(n))
1154 return comprehension(n);
1155 std::unique_ptr<Expr> e(
new Expr(Expr::Kind::CALL));
1158 e->args.push(
expr());
1159 while (punct(
",")) {
1161 e->args.push(
expr());
1165 check_call(*e, line);
1168 std::unique_ptr<Expr> e(
new Expr(Expr::Kind::NAME));
1172 fail(
"expected an expression, found " + describe(t));
1179 case ReadType::FLOAT:
return ValueType::FLOAT;
1180 case ReadType::WORD:
case ReadType::REST:
return ValueType::STRING;
1181 default:
return ValueType::INT;
1186 void declare(Seq<Decl>& out,
const std::string& n, ValueType t,
int d) {
1187 if (n.empty() || (n ==
"_"))
1189 for (
const Decl& o : out)
1193 x.name = n; x.type = t; x.depth =
d;
1198 void declare(Seq<Decl>& out,
const Pattern& p) {
1199 for (
const Pattern::Item& it : p.items)
1200 if (it.kind == Pattern::Item::Kind::CAP)
1201 declare(out, it.text, value_type(it.type.read), 0);
1208 for (
const std::unique_ptr<Stmt>& s : b) {
1211 declare(out, s->name, value_type(s->type.read), s->dims.
size());
1214 declare(out, s->name, value_type(s->type.read), 1);
1221 declare(out, s->pattern);
1229 for (
const Decl& d : inner)
1230 declare(out, d.name, d.type, d.depth+1);
1235 for (
const Arm& a : s->arms) {
1236 declare(out, a.pattern);
1265 : impl(
std::make_shared<
SpecImpl>(
"",
"<empty>")) {}
1270 s.impl = std::make_shared<SpecImpl>(text, origin);
1291 return impl->read(text, origin, p,
false);
1301 return impl->read(text, origin, p,
true);
Arm of a sections statement.
Named values read from an instance.
A name that a block may define, with the type and depth of its values.
Exception for errors in specs and instance files
Values for the param statements of a spec.
Growable array on the Gecode heap.
int size(void) const
Return number of elements.
SpecImpl(const std::string &text, const std::string &origin)
Parse text from origin.
std::string origin
Where the spec comes from.
Reader spec for a textual instance format.
static Spec load(const std::string &path)
Load the spec in file path.
static Spec parse(const std::string &text, const std::string &origin="<spec>")
Parse spec text, using origin in error messages.
Data read_text(const std::string &text, const std::string &origin="<input>", const Params &p=Params()) const
Read instance text, using origin in error messages.
Data read(const std::string &path, const Params &p=Params()) const
Read instance file path.
std::string name(void) const
Return the format name declared by the spec (may be empty).
Data catalog(const std::string &path, const Params &p=Params()) const
List the instances in file path.
Spec(void)
The empty spec (reads only empty input).
Data catalog_text(const std::string &text, const std::string &origin="<input>", const Params &p=Params()) const
List the instances in text, using origin in error messages.
static std::string str(bool b)
Map bool to string.
GECODE_FLATZINC_EXPORT FlatZincSpace * parse(const std::string &fileName, Printer &p, std::ostream &err=std::cerr, FlatZincSpace *fzs=nullptr, Rnd &rnd=defrnd)
Parse FlatZinc file fileName into fzs and return it.
bool neg(const View &x)
Test whether x is negative.
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.
Reading instance files described by reader specs.
void resolve(Block &b, const std::string &origin)
Resolve the names in the expressions of b, the body of a spec from origin.
ValueType
Type of the values in a data entry.
bool is_digit(char c)
Test whether c is a digit.
std::string record_starts(int id)
Return the name of the record starts of the repeat numbered id.
bool parse_float(const std::string &t, double &v)
Parse decimal float t into v, and return whether it is one.
bool sub(long long int x, long long int y, long long int &r)
Store x - y in r unless it overflows.
std::string read_file(const std::string &path)
Read file path into a string.
void declared(const Block &b, Seq< Decl > &out)
Add the names that block b may define to out.
bool is_space(char c)
Test whether c is white space.
ReadType
What a declaration or a capture reads.
bool is_alnum(char c)
Test whether c can occur in a name.
bool parse_int(const std::string &t, long long int &v)
Parse decimal integer t into v, and return whether it is one.
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.
void fail_at(const std::string &origin, int line, const std::string &m)
Throw an error with message m for line line of the spec from origin.
bool is_blank(char c)
Test whether c is white space within a line.
Seq< std::unique_ptr< Stmt > > Block
Sequence of statements.
const int min
Smallest allowed integer value.
const int max
Largest allowed integer value.
Gecode toplevel namespace
void lex(Home home, const IntVarArgs &x, IntRelType r, const IntVarArgs &y, IntPropLevel ipl=IPL_DEF)
Post lexical order between x and y.
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntPropLevel ipl=IPL_DEF)
Post propagators for scheduling tasks on unary resources.
Gecode::FloatVal b(9, 12)
Gecode::FloatVal a(-8, 5)
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 constants("Spec::GecodeConstants", [](void) { Data d=read("let a = gecode.int_max let b = gecode.int_min let c = gecode.int_max / 2\n" "gecode: int check gecode == 3", "3");CHECK(d.integer("a")==Gecode::Int::Limits::max);CHECK(d.integer("b")==Gecode::Int::Limits::min);CHECK(d.integer("c")==1073741823);CHECK(fails([](void) {(void) Spec::parse("let x = 1\nlet y = gecode.foo", "s");}, "s:2: unknown Gecode constant 'gecode.foo' (known: gecode.int_max, gecode.int_min)"));const char *defining[]={ "gecode.x: int", "let gecode.int_max = 3", "param gecode.p", "list gecode.l: int until 0", "gecode.g[1][1]: alphabet \"a\"", "repeat until \"x\" store gecode.t { a: int }", "a[2]: int check all(gecode.v in a: 1)" };for(const char *spec :defining) if(!fails([&](void) {(void) Spec::parse(spec, "s");}, "names starting with 'gecode.' are Gecode constants")) return false;return true;})
Case types("Spec::Types", [](void) { Data d=read("type time = 0..gecode.int_max / 2\n" "n: 1..\n" "repeat n { ready: time due: time }\n" "type cell = alphabet \"ab\" blank \".\"\n" "g[1][2]: cell", "2 1 2 3 4 a.");CHECK(equal(d.ints("due"), {2, 4}));CHECK(equal(d.ints("g"), {1, 0}));CHECK(fails("n: int type small = 0..n a: small", "3 4", "expected small (an int in 0..3), found '4'"));CHECK(fails("type w = word type v = w line \"{x:v} {y:0..1}\"", "a 2", "expected an int in 0..1"));CHECK(fails("n: int type t = 0..n let n2 = n repeat 2 { b: t }", "1 1 2", "expected t (an int in 0..1)"));Data k=read("line: int type: 0.. list: word each: int layout: int", "1 2 a 3 4");CHECK(k.integer("type")==2);CHECK(k.integer("layout")==4);CHECK(read("a: 0..\nb[2]: int check a == 0", "0 1 2").size("b")==2);CHECK(read("a: 0.. index: int", "0 1").integer("index")==1);CHECK(rejects("a: 0..<", "'..<' needs an upper bound"));CHECK(rejects("a: ..", "a range needs a lower or an upper bound"));CHECK(rejects("a: foo", "unknown type 'foo'"));CHECK(rejects("a: 1 + 2", "expected '..' or '..<' after the lower bound of a range"));CHECK(rejects("type int = 0..", "'int' is a base type"));CHECK(rejects("type t = int type t = word", "the type 't' is already defined"));CHECK(rejects("type t = int t: int", "s:1: 't' names a type, so it cannot also name a value"));CHECK(rejects("if 1 > 0 { type t = int } a: t", "unknown type 't'"));CHECK(rejects("a: word offset 1", "'offset' needs numbers"));CHECK(rejects("a[2]: int layout \"FULL_MATRIX\"", "'layout' needs a two-dimensional array of numbers"));CHECK(rejects("line \"{x:0..<}\"", "s:1: '..<' needs an upper bound"));CHECK(rejects("line \"{x:int int}\"", "unexpected 'int' in the capture type 'int int'"));CHECK(rejects("line \"{x:}\"", "a capture needs a type after ':'"));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;})
Case repeats("Read::Repeat", [](void) { Data d=read("n: int\n" "repeat n { index 1 k: int s[k]: int offset -1 }\n" "repeat until \"999\" { a: int }\n" "repeat until \">=\" \"=\" store op { c: int v: word }\n" "rhs: int\n" "repeat until eof { w: word }", "3\n1 2 4 5\n2 0\n3 1 1\n7 8 999\n" "2 x 3 y = 4\nfoo bar");CHECK(equal(d.ints("k"), {2, 0, 1}));CHECK(d.size("s")==3);CHECK(d.size("s", {1})==0);CHECK(equal(d.ints("s"), {3, 4, 0}));CHECK(equal(d.ints("s", {2}), {0}));CHECK(equal(d.ints("a"), {7, 8}));CHECK(d.text("op")=="=");CHECK(equal(d.ints("c"), {2, 3}));CHECK(d.integer("rhs")==4);CHECK(d.size("w")==2);CHECK(fails("n: int repeat n { index 1 x: int }", "2\n1 5\n3 6", "expected index 2, found 3"));Data e=read("repeat 2 { repeat 2 { x: int y: int } }", "1 2 3 4 5 6 7 8");CHECK(e.depth("x")==2);CHECK(equal(e.ints("x", {1}), {5, 7}));CHECK(equal(e.ints("y"), {2, 4, 6, 8}));return true;})
Case power("Read::Power", [](void) { Data d=read("let a = 2 * 3 ^ 2 let b = 2 ^ 3 ^ 2 let c = (2 ^ 3) ^ 2 let e = -2 ^ 2 let f = 1 + 2 ^ 2 * 3\n" "let k = (-2) ^ 2 let m = -2 ^ 3 ^ 2\n" "let g = 7 ^ 0 let h = (0 - 2) ^ 63 let i = 1 ^ 9223372036854775807 let j = 3 ^ 39", "");CHECK(d.integer("a")==18);CHECK(d.integer("b")==512);CHECK(d.integer("c")==64);CHECK(d.integer("e")==-4);CHECK(d.integer("k")==4);CHECK(d.integer("m")==-512);CHECK(d.integer("f")==13);CHECK(d.integer("g")==1);CHECK(d.integer("h")==LLONG_MIN);CHECK(d.integer("i")==1);CHECK(d.integer("j")==4052555153018976267LL);CHECK(fails("let x = 3 ^ 40", "", "integer overflow in '^'"));CHECK(fails("let x = 2 ^ 63", "", "integer overflow in '^'"));CHECK(fails("let x = 2 ^ -1", "", "negative exponent in '^'"));CHECK(fails("let x = 2 ^ -1 + 3", "", "negative exponent in '^'"));CHECK(fails("let x = -2 ^ 63", "", "integer overflow in '^'"));CHECK(fails("f: float let x = f ^ 2", "1.5", "'^' needs integers"));return true;})
Constraint precedence("Precede", Constraint::Kind::PRECEDE, 3)