A spec is a sequence of statements executed from top to bottom against the input. The input is read as whitespace-separated tokens, so line breaks do not matter unless a statement works on lines. Names defined by earlier statements can be used in later expressions. A spec for DIMACS CNF is:
Statements that read values, where t is a type (see below):
- x: t: read one value. The name
_discards it. - x[e1][e2]...: t: an array of fixed size, read row-major.
- w[n][n]: t layout e: a symmetric matrix stored in the TSPLIB layout named by
e(FULL_MATRIX,UPPER_ROW,LOWER_ROW,UPPER_DIAG_ROW,LOWER_DIAG_ROW, and the column-wise variants). - ... offset e: add
eto every number read, for example to make 1-based identifiers 0-based. For a triangular layout, the cells that are not read stay 0. - list x: t until 0 or until eol: a list ended by a sentinel value (which is not stored) or by the end of the line. A line list starts on the next line when the current one is used up; as blank lines are skipped, an empty row needs a marker in the format (such as
0) rather than a blank line.
The names of these statements can be keywords, as in line: int, because a name followed by a colon always declares a value.
Types:
int,float,num,word, andrestread one token. Anumis an integer if possible and a float otherwise;restreads the rest of the line and cannot be an array.- lo..hi and lo..<hi are the integers from
lotohi, includinghior not. One bound can be left out, so 0.. are the integers that are not negative, but ..< needs its upper bound. The bounds are expressions, evaluated once before the statement reads, and a value outside the range is an error such as expected an int in 0..9, found '12'. The range applies to the numbers read, before an offset, and not to the sentinel of a list. A range without an upper bound ends before a statement, a declaration, or an option such aslayout. - alphabet "123456789" blank "." strip "|-+" base 1 reads the characters of a two-dimensional array, such as cells[n][n]: alphabet "123456789" blank ".": symbol
kof the alphabet has valuekplusbase(1 by default), blank symbols are 0, and stripped symbols and white space are skipped. - type time = 0..gecode.int_max / 2 names a type, which later statements in the same block, and the blocks inside it, can use as in ready: time. Its bounds are evaluated where it is defined, and errors name it, as in expected time (an int in 0..1073741823), found '-1'. A type name must differ from the names of values.
Statements that structure the input:
- line "pattern": the rest of the current line must match the pattern, or the next line if the current one is used up.
- find "pattern": skip lines until one matches.
- skip line, skip e lines, expect "p" "cnf".
- repeat e { ... }: read a record
etimes. Every name defined in the body becomes an array with one entry per repetition, so records are stored column-wise. Rows may differ in length. A row that an iteration does not define is empty, which needs rows that are arrays. - repeat until "999" "EOF" store x { ... }, repeat until
eof { ... }: repeat until one of the tokens comes next (it is consumed, and stored in
xif given), or until the end of input. - repeat e as nodes { each node ... }: name the list of records and each record (see below); either is optional, and
eachcomes first in the body. - index b: inside a repeat, read the row number counted from
band check it. - sections until "EOF" skip other { "pattern" { ... } ... }: lines in any order, each handled by the first arm whose pattern matches it, until one of the tokens or the end of the input (the terminating token is optional, as for TSPLIB's
EOF, and store x keeps it as for repeat). Unknown lines are errors unlessskipotheris given. Each arm must match exactly one line, unless it is written "pattern" optional: then it matches at most one. An arm written "pattern" last { ... } ends the statement after it has run (an arm that is both is written optional last). - if e { ... } else { ... }, let x = e, check e "message" (see below for checks on records).
- param x or param x = e: a value given by the caller (see Params). A given value has the type of the default; a parameter without a default is an integer if possible, otherwise a float or a string.
- instances { ... }: a file with several instances, one per pass through the body. Only one instance is kept: the parameter
instanceselects it by number (from 1) if it is a number, and otherwise by the value ofname, which the body may define. Without the parameter, the file must contain a single instance. Reading stops after the selected instance, so this must be the last statement of a spec. A failed check, or a missing or repeated sections line, in an instance before the selected one does not stop reading, so that an invalid instance does not hide later ones; other errors do, as the input cannot be read on. Spec::catalog lists the instances of a file and the first such failure of each.
Settings: format name (the name of the format, see Spec::name), comment "c" ... (prefixes of comment lines), stop "%" (prefixes of lines that end the data; a prefix ending in a letter or digit must not be followed by one, so "c" matches c foo but not cfoo), tokens ";" (characters that form tokens by themselves), separators "," (characters that separate tokens like white space), and ignore
trailing (allow input after the last statement). Settings must be at the top level of the spec, not inside a block.
Strings in a spec are written in double quotes and end on the same line. The escapes \n, \t, \\, and \" stand for a newline, a tab, a backslash, and a double quote; other escapes are errors.
A line pattern is literal text with captures {x:t} of a type that is not an alphabet, such as {x:int} or {x:1..n}, and {$x} (the current value of x). A capture without a type, {x}, is a word; one without a name, such as {:int} or {_}, checks the text but does not store it. The ranges of captures are checked after the line matched, so they can use the captures before them. At the end of a pattern, ... matches the rest of the line. White space in a pattern matches any amount of white space; at least one blank is needed where two words would otherwise run together. A pattern must match the rest of the line.
Expressions have integer arithmetic (+ - * / % ^, where division truncates towards zero, ^ is the power, and overflow and negative exponents are errors), comparisons of numbers and strings (an integer compared with a float is converted to a float), && || !, string literals, and the functions count(a) and size(a) (the number of elements of a), min, max, and sum (over all integers in their arguments), distinct (whether these integers differ), and defined(x). The operators bind from loosest to tightest: ||, &&, == !=, < > <= >=, + -, * / %, the unary - !, and ^ (which groups to the right), so -2^2 is -4 and 2^-1 is 2^(-1). The constants gecode.int_max and gecode.int_min are the limits of Gecode's integer values (Int::Limits); a spec cannot define names that start with gecode..
a[i] is element i of array a, counted from 0 as in Data: a number for a one-dimensional array and a row otherwise, so a[i][j] works for arrays of rows. An index out of range is an error. The comprehensions all(x in a: e), any(x in a: e), count(x in a: e), and sum(x in a: e) evaluate e for each element x of a: whether e holds for all or some elements, for how many it holds, and the sum of its integer values (true, false, 0, and 0 for an empty array). The name x is defined only in e and must differ from the names of the spec and of enclosing comprehensions.
In a check, a name defined inside a repeat that does not enclose the check is a record name: it stands for one record, and the check must hold for every record. Checks can thus follow the statements that read the data. For the rows of a nonogram, read by repeat height { list row: int until eol },
checks every row, and a failure names the record, as in check
failed for record 3 of 'row', and points at its input. Record names of one repeat are taken from the same record. With names of nested repeats, the check holds for every inner record of every outer record (record 2 of record 3). A check cannot use the record names of two other repeats. A name directly after in and the argument of size and defined are whole arrays: size(row) == height counts the rows, and sum(r in row: sum(r)) adds all clues. Only checks range over records: in let, if, and counts a record name is the whole array, so let first = row[0] is the first row. A check cannot use a name defined both inside and outside a repeat, or in several repeats, unless all of them enclose the check. When an all makes a check fail, the message names the element that fails it, as in element 2 of 'a', or the record.
A repeat can name the list of its records and each record:
The fields of a record are the names defined in the repeat, and the lists of nested repeats. The list nodes is the whole list: nodes[i] is record i, and size(nodes) and x in nodes work as for arrays; a field needs one record, so nodes.ready is an error. The name node is a record name, like ready, and inside the repeat it is the current record. With repeat n as jobs { each job repeat m as steps { each step
machine: int } }, job.steps are the steps of a job and job.machine their machines, so check
distinct(job.machine) checks each job and names it on failure (record 3 of 'jobs'), while step.machine ranges over all steps (record 2 of 'steps' in record 3 of 'jobs'). Records are not values, and their names are not in the data and must differ from all other names.
The values that expressions visit, including the records of checks, are limited to a multiple of the size of the input, so that checks cannot take time far beyond reading.
