Generated on for Gecode by doxygen 1.17.0

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:

format dimacs-cnf
comment "c"
stop "%"
line "p cnf {vars:0..} {clauses:0..}"
repeat clauses {
list clause: -vars..vars until 0
}
void clause(Home home, BoolOpType o, const BoolVarArgs &x, const BoolVarArgs &y, BoolVar z, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for Boolean clause with positive variables x and negative variables...
Definition bool.cpp:955

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 e to 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, and rest read one token. A num is an integer if possible and a float otherwise; rest reads the rest of the line and cannot be an array.
  • lo..hi and lo..<hi are the integers from lo to hi, including hi or 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 as layout.
  • alphabet "123456789" blank "." strip "|-+" base 1 reads the characters of a two-dimensional array, such as cells[n][n]: alphabet "123456789" blank ".": symbol k of the alphabet has value k plus base (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 e times. 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 x if 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 each comes first in the body.
  • index b: inside a repeat, read the row number counted from b and 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 unless skip other is 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 instance selects it by number (from 1) if it is a number, and otherwise by the value of name, 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 },

check sum(row) + count(row) - 1 <= width "the clues of a row do not fit"
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
LinIntExpr sum(const IntVarArgs &x)
Construct linear expression as sum of integer variables.
Definition int-expr.cpp:953

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:

repeat n as nodes {
each node
ready: int
due: int
}
check node.ready <= node.due "the time window of a node is invalid"
check nodes[0].ready == 0 "the depot must open at time 0"

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.