|
Gecode 6.4.0
|
Design written 2026-09-05. Original source baseline: 8ae59d5c1946abf47203172ba3cb89fbf5ea0a8b. The table/finite-domain, explicit-offset circuit and four-argument fixed cumulative slices below are now implemented with separate independent correctness gates. No parser, native solver or public model changes were needed for these compiler extensions. Current implemented admission is described in FLATZINC-COMPILER.md.
Reuse the existing typed TableData, CircuitData and CumulativeData; extend only the owning FlatZinc compiler and independent original-source evaluator. Keep the original raw predicates/domains and source-slot mapping intact. Publish an artifact only when every predicate is admitted and all resource checks pass. Do not use a broad gecode_/fzn_ prefix-stripping rule.
Implement in this order:
Keep reified tables, Boolean/optional tables, subcircuits, cost circuits, six-/seven-argument multi-machine scheduling, optional tasks, variable scheduling parameters, and unbounded integer variables explicitly unsupported. Table and holey-domain admission should land and pass its independent oracle before adding scheduling. No backend defaults or existing workflow policy changes are needed.
The authoritative implementation vocabulary is this repository's bundled Gecode MiniZinc library and registry at the source baseline above. Relevant local sources:
External primary references were read on 2026-09-05. The stable Handbook scheduling, Table and Circuit pages reported 2.10.1; the FlatZinc specification and Gecode index still reported 2.10.0. Stable URLs are rolling documentation, so these are observed page versions, not a claim that every solver-specific declaration belongs to a downloaded 2.10.1 source distribution. Release-tag raw source URLs were not retrievable in this research session. Pin the exact MiniZinc binary, bundled solver library path/version and generated .fzn fixture hash before integration tests. Do not label a mutable master source as a release-pinned specification.
VI below means a flat array of integer literals or integer variable references; PI means a flat parameter array of integer literals. Booleans do not become integer literals merely because the target Model also supports Binary variables. Captured parameter references have already been expanded by the parser.
| Source predicate/form | Verified contract | Initial compiler response |
|---|---|---|
| gecode_table_int(VI x, PI t) | Two arguments; t is row-major flat storage, tuple arity is len(x) | Admit len(x)>0, len(t)len(x)==0; materialize typed tuples after checked count admission |
| gecode_table_int([], []) | No tuple-count field remains after flattening | Explicit Unsupported initially; do not manufacture an empty tuple |
| gecode_table_int([], nonempty) | Cannot form a tuple of zero arity | InvalidInput, before division/indexing |
| table_int, fzn_table_int, fzn_gecode_table_int, gecode_gecode_table_int | Prefix aliases are not a general interface contract; MiniZinc fzn_table_int has a 2-D argument | Keep unsupported until an exact separate signature is documented; do not strip prefixes |
| Table Boolean, reified, implication or optional forms | Different argument types or truth/occurrence semantics | Unsupported in this slice |
| gecode_circuit(PI scalar offset, VI successors) | Literal offset first, successor array second | Admit nonempty array and nonnegative offset within the exact source range; check native range when solving |
| fzn_circuit(successors) | MiniZinc wrapper derives the original array index minimum | Unsupported as a direct low-level capture form without an explicit preserved index contract |
| Cost circuit and subcircuit names | Cost channels or permitted excluded/self-loop nodes change semantics | Unsupported |
| gecode_cumulatives(VI s, VI d, VI r, int-or-var-int b) | Four-argument single-resource poster | Admit equal array lengths, nonnegative fixed d, r, b; preserve source references used as fixed data |
| cumulatives(s,d,r,b) | Verified legacy alias of that same four-argument poster | Admit only exact four-argument shape under the same fixed-data contract |
| gecode_cumulatives(s,d,r,m,PI bounds,bool upper) | Six arguments: machine decisions and per-machine bounds, allowing different resource semantics | Unsupported, never truncate to four arguments |
| fzn_cumulatives(s,d,r,m,b,upper,min_m) | Bundled MiniZinc wrapper has seven arguments and shifts machine indices | Unsupported; not equivalent to the registry's synthetic fzn_cumulatives alias |
| gecode_schedule_cumulative_optional | Presence array and different five-argument order | Unsupported |
| Declared var {v1,...,vk} and existing int_in(x, set) | Exact finite-set membership | Admit bounded normalized finite membership, retaining all holes |
| set_in(int x, parameter set) | Standard integer membership spelling, overloaded locally with set-variable posting | Optional explicit spelling only for an integer operand and literal set; never admit set-variable membership or reification by name alone |
Registry::add(id,p) registers id, gecode_+id and fzn_+id. For an already prefixed name it even produces double-prefixed names. Thus gecode_table_int and gecode_circuit registrations do not establish unprefixed table_int or circuit. The scheduling registration cumulatives creates three spellings, but its six-argument branch and the separate seven-argument MiniZinc wrapper still need different contracts. A literal whitelist is safer and more reviewable.
Malformed shape/type/arity for a specifically admitted interface is InvalidInput. A known but unsupported overload or data class is Unsupported. Resource caps produce ResourceLimit; cancellation/time limits keep their own statuses. Do not label unsupported domains or arithmetic overflow as an infeasible model.
For arity n>0, evaluate a table by testing whether any complete original row tuple[j] == source_value(x[j]) holds for every column. The original evaluator must read the original flat relation, not ask Detail::global_satisfied about generated metadata. This provides an independent check on row reconstruction and mapping.
Reject noninteger tuple entries, nested arrays, wrong namespaces, and remainder cells before posting. Duplicated tuples are harmless. Repeated variables are positional equality requirements: [x,x] with only tuple [0,1] is infeasible; [0,0] is feasible at x=0. Do not deduplicate argument positions or silently replace repeated source variables with independent decisions. Fixed literals in x use the compiler's private fixed-slot cache and never appear as source outputs.
An empty relation with positive arity is exact false; post a typed empty table or an explicit false row. Every input still passes type and resource admission before constant folding. Compilation Complete means faithfully represented, not SAT.
Zero arity needs a deliberate representation boundary. TableData({}, {}) is false and TableData({}, {{}}) is true. A flattened [] loses this distinction. The current arg2tupleset chooses zero tuples when its flat input is empty, and otherwise divides by arity; it also silently floors a nondivisible cell count. Those implementation shortcuts are not a sufficient contract for reconstructing an arbitrary MiniZinc 2-D relation. Initial rejection avoids both invented truth and division by zero. A future counted-table predicate or retained original 2-D shape can support both zero-arity cases; that change requires its own parser and source-evaluator contract, not a guessed row count.
Replace the compiler's interval-only declaration accumulator with a bounded intersection representation: optional lower/upper limits plus, when present, a sorted unique vector of allowed integers. Do not enumerate a large interval. Intersect listed values with intervals and other listed sets, processing every original restriction on its declaration-alias representative. A finite member list can establish finite bounds for an otherwise var int representative. Clipping a list must not turn it into its hull unless every hull value is present.
Validate every original listed integer with the compiler's exact representation check before sorting/deduplicating. Normalize once per restriction, charge input cells, sort/merge work and stored allowed values. Use a metered deterministic sort or conservative precharged comparison budget with a checkpoint around the sort; a library sort is not a hard cancellation-latency guarantee. Avoid multiplying large counts before checking storage/work ceilings.
After intersection:
Declared aliases may carry restrictions through synthesized raw-domain rows; collect those before posting. Ordinary int_eq rows remain original constraints, even if normalized parser records mark an alias equality. Do not use normalized records to discard raw membership predicates. The existing source evaluator's literal-set membership already supports holes; retain it independently of the lowered unary tables. Original Boolean declaration domains remain intersected with {0,1}; do not generalize Boolean-to-int predicate coercion beyond the existing captured/synthesized domain contract.
For n>0 and offset o, legal successors lie in [o,o+n-1]. Starting from node position zero, visit exactly n previously unvisited positions and require the next position to be zero. Out-of-range values, a premature repeated node, multiple cycles, or an unvisited node make the original predicate false. A singleton is feasible exactly when its sole successor equals o. A self-loop for n>1 cannot satisfy a full circuit. This is not a subcircuit or merely AllDifferent.
Evaluate the original successor array in source order, including aliased or literal terms. Bound-check before subtracting offset or indexing. o+n-1, the normalizing shifts and all source arithmetic use checked integer operations. Initial gecode_circuit admission rejects negative offsets because its bundled native low-level interface explicitly requires nonnegative offset. The generic typed Model supports negative bases by safe normalization; admitting that broader class under the low-level predicate's name should be a separate documented choice. The high-level bundled wrapper shifts negative index sets before emitting a nonnegative low-level offset. Do not infer a base of one from output dimensions.
Repeated handles are retained; the native bridge has its own equality-preserving argument preparation. Neither deduplication nor accidental independent clones may change the solution set. An empty successor array is InvalidInput for the admitted low-level signature, never vacuously a solved circuit.
All s, d and r arrays have equal lengths. Each d[i], r[i], and b must be a literal or resolve to a singleton from original declarations and exact domain intersections. Do not run a solver to discover whether they happen to be fixed. Their referenced source variables remain mapped and independently checked. Fixed negative durations/heights violate the declared assumptions and are InvalidInput. Negative capacity is Unsupported in this initial typed-global scope, including empty schedules where another high-level convention might be vacuous. Nonfixed parameters are unsupported, rather than copied from a current lower bound.
Task i contributes r[i] precisely when s[i] <= t < s[i]+d[i]. Zero duration or zero resource contributes nothing. Equal end/start times do not overlap. Repeated start handles still describe separate tasks, so demands add; identical tasks are not deduplicated. For the source evaluator, compute checked integer endpoints, sort/group events at equal time, remove ending demands and add starting demands before checking the interval following that time. An alternative independent tiny-instance oracle checks all integer times in the bounded test horizon; integer endpoints make that exhaustive for continuous time as well.
The old four-argument p_cumulatives has a singleton shortcut imposing height[0] <= bound without checking zero duration. For d=[0], r=[2], b=1, it rejects an assignment that the standard half-open predicate and current typed CumulativeData accept. The improved compiler should use the intended documented predicate, record this specific legacy disagreement in tests, and avoid treating the old executable as the sole oracle. This is a semantic bug fixture, not a performance comparison or permission to ignore other discrepancies.
For nonnegative capacity, an empty schedule is true. A positive-duration task whose height exceeds capacity makes the model infeasible regardless of start. Do not replace cumulative with AllDifferent or unary scheduling merely because some heights are large; the native adapter already implements guarded choices.
Keep current public compiler signatures unchanged if practical. Existing max_variables, max_constraints, max_nonzeros, max_work, depth, deadline and cancellation controls can cap the new representations with explicit accounting:
| Representation | Storage/work to charge before allocation/posting |
|---|---|
| Flat table | Source arguments + every relation cell; typed row count and copied cells; one global constraint; private literal variables |
| Holey domain | Original and normalized members; intersection/sort work; unary table rows/cells; one global per noncontiguous representative |
| Circuit | Successor occurrences including repeats; one global; literal slots; source-evaluator visited array |
| Cumulative | All three arrays and scalar; fixed-value lookup; one global; start literal slots; at most two checker events per active task and bounded sorting storage |
The current public validate_flatzinc has no time/cancellation option. Its original checker allocations and work are bounded by the already admitted payload, but an outer caller can only checkpoint before/after it. Do not claim an internally interruptible checker or hard validation deadline without a separate interface change. Compiler-side normalization/copying continues to use its own Meter.
Global argument occurrences and table cells count toward max_nonzeros even though they are not matrix nonzeros. This extends the existing compiler's global payload accounting; document the meaning. No unchecked n*tuple_count, 2*n, offset+n-1, interval width or cumulative energy calculation may precede checks. Caps include constants/helpers; a partial failed artifact never escapes.
Compilation need not require a native build. Typed global constants retain the Model's exact [-2^53,2^53] boundary, while actual Native solves additionally use Int::Limits::min/max (±(INT_MAX-1) here). Native preflight already checks global argument/tuple counts, values and index endpoints. Cumulative has stricter endpoint, total-energy, task-count-squared and propagation-envelope admission: for retained positive-demand tasks it guards integer sums/products and the bound 2*capacity*time_magnitude + total_energy <= native_max*minimum_height where applicable. Reuse this code; do not claim that individually representable inputs alone guarantee a supported schedule. Overflow or a failed envelope guard yields Unsupported, not false infeasibility. Large literal/domain models can compile but remain unsupported by the selected backend.
Any remaining active Table/Circuit/Cumulative global causes explicit HiGHS solve rejection under the existing full-model capability check. Auto chooses Native for active typed globals. No continuous relaxation, omitted membership constraint, or silent decomposition is allowed. A holey-domain intersection that becomes contiguous may use only bounds and retain ordinary linear HiGHS capability; a remaining unary table does not. Missing Native must remain explicit unsupported. A separately folded constant contradiction may have no active globals and can be handled by either backend, with the original source check still retained.
The final result is accepted only after current validate_flatzinc checks owner, revision, full helper-inclusive slot layout, active mask, integral source values, all original declarations/aliases/domains and every admitted original predicate. Generated helper values are existential witnesses, not extra user decisions or source outputs. Source validation checks feasibility/objective only; it does not upgrade a Numerical vendor bound into an Exact proof. Satisfy/optimal/limit markers remain the existing driver's responsibility.
After these correctness gates, add small representative table/domain/scheduling cases to the existing bounded fast regression panel and benchmark the new admission against the existing native FlatZinc route. Performance measurements must use comparable source problems/configurations and run after concurrent builds and solver tests have stopped. This document itself makes no executed-test or performance claim.