Skip to content
STIMSMITH

Array constraint

Concept WIKI v1 · 6/5/2026

An array constraint is a constraint used in Constraint Logic Programming (CLP) and constraint satisfaction to represent read and write operations on array elements, generalizing the classical 'element' constraint and supporting propagation between index relationships and value relationships.

Array constraint

An array constraint is a constraint-domain construct used in constraint programming and Constraint Logic Programming (CLP) to model manipulations of arrays (indexed memory regions) declaratively, so that solvers can reason about both the indices and the values stored at those indices. It is a generalization of the classical element constraint and is studied in the context of constraint propagation, test generation, and program analysis (including non-termination proofs) [1].

Motivation and classical formulation

In earlier CLP-based approaches, array manipulations are expressed through equivalent Static Single Assignment (SSA) constructions. The core idea is to generate, for each assignment of an array element, a set of element-level constraints. A single assignment inside an array of size n thus introduces 2n − 1 element constraints — 2 constraints for each of the n − 1 indices that are not assigned, plus 1 for the index that is assigned [1].

For non-trivial memories this approach explodes: in functional descriptions of processors (e.g. the ST processor), memory is represented as an array addressed with 24-bit index registers, so an address register of size v implies a 2^v memory size. The classical element-constraint method would then require a number of element constraints proportional to (number of write accesses × v), which is infeasible in practice [1].

A first solver-level approach: tabRead and tabWrite

A more direct strategy is to introduce a native array type in the solver and add two new constraints for read and write accesses to array elements — tabRead and tabWrite. These constraints maintain the consistency of the array values by enforcing two equivalent rules, with the solver implementing both propagation directions (from index relationship to value relationship, and vice versa) [1]:

  • i = j ⇒ T[i] = T[j]
  • T[i] = T[j] ⇒ i = j

Limitations of this approach include [1]:

  • The tabRead/tabWrite constraints are order-dependent because the order of accesses in the original code must be preserved, which violates the classical constraint programming paradigm where constraint solving is order-independent.
  • Static dependency analysis between variables is very limited, since indices are typically only known dynamically.

A two-step strategy over index relationships

Because the complexity of array manipulation depends directly on whether indices are equal or not, a second strategy decouples the problem into two steps [2]:

  1. First, fix the relationships between indices (i.e. which array accesses are aliases — references to the same memory location — and which are not).
  2. Then, in a second step, push constraints that enforce the chosen relationships.

The number of possible relationships between n indices is the number of partitions of an n-set, i.e. the nth Bell number b_n, with the recurrence [2]:

  • b_0 = 1
  • b_{n+1} = Σ_{k=0..n} C(n, k) · b_k, where C(n, k) = n! / (k! (n − k)!) are binomial coefficients.

The exponential growth of the Bell numbers is considered acceptable because only one correct combination of index relationships is searched for. An alias coverage criterion can be defined to estimate coverage of the different choices of index relationships; this is meaningful for verifying self-referential memory accesses such as mem[mem[i]] where mem[i] = i [2].

Advantages

The two-step approach enables [2]:

  • Variable independence analysis to split the constraint store into independent groups of variables.
  • Graph analysis to derive heuristics for variable ordering, improving solver performance.

Drawbacks

  • The chosen set of index relationships can be inconsistent with other constraints in the store; the method relies on the backtracking mechanism of the constraint solver to recover from such failures.
  • In many cases, inconsistent choices are avoided by using a symbolic solver [2].

Application contexts

Array constraints are used in several settings:

  • Code-based test generation for functional processor descriptions, where the test-generation pipeline translates array read/write accesses in the processor model into array constraints so that the constraint solver can enumerate input stimuli and exercise aliased-memory paths. The use of an alias coverage criterion makes this approach suitable for processors with large indexed memories (e.g. 24-bit address registers) [b916660b-61da-415d-bca6-8834f5feb4f1, afdf5f7b-eeaa-4eb7-b8d9-0f794dfb0f80].
  • Non-termination analysis of bytecode: Dalvik bytecode programs can be compiled into CLP programs with array constraints so that non-termination of the resulting program entails non-termination of the original one, allowing non-termination techniques for CLP to be reused for Dalvik (see arXiv:1412.3729v1, public context).
  • General constraint propagation: array expressions can be used as constraints that generalize the element constraint, with theoretical study of domain-reduction rules and proof that an efficient encapsulating algorithm enforces arc-consistency (see arXiv:cs/0105024v1, public context).

LINKED ENTITIES

1 links
Code-based Test Generation for Validation of Functional Processor Descriptions USES

CITATIONS

7 sources
7 citations
[1] The classical approach to array manipulations in CLP uses SSA-style construction and generates 2n − 1 element constraints per array assignment, leading to a number of constraints proportional to (number of write accesses × v) for a v-bit address space. Code-based Test Generation for Validation of Functional Processor Descriptions (TACAS 2003, Section 3.3 Array Constraints)
[2] A solver-level array type with `tabRead` and `tabWrite` constraints enforces the propagation rules i = j ⇒ T[i] = T[j] and T[i] = T[j] ⇒ i = j, but the resulting constraints are order-dependent, violating the classical order-independence of constraint solving. Code-based Test Generation for Validation of Functional Processor Descriptions (TACAS 2003, Section 3.3 Array Constraints)
[3] The number of possible index-relationship combinations for n array accesses equals the nth Bell number, given by b_0 = 1 and b_{n+1} = Σ_{k=0..n} C(n,k) · b_k. Code-based Test Generation for Validation of Functional Processor Descriptions (TACAS 2003, Section 3.3 Array Constraints)
[4] An alias coverage criterion over index relationships enables verification of self-referential memory accesses such as mem[mem[i]] with mem[i] = i, and the two-step approach enables variable-independence analysis and graph-based variable-ordering heuristics. Code-based Test Generation for Validation of Functional Processor Descriptions (TACAS 2003, Section 3.3 Array Constraints)
[5] A drawback of the two-step index-relationship strategy is that the chosen relationships may be inconsistent with other constraints; the method relies on solver backtracking to recover from such failures, with a symbolic solver often avoiding inconsistent choices. Code-based Test Generation for Validation of Functional Processor Descriptions (TACAS 2003, Section 3.3 Array Constraints)
[6] Dalvik bytecode programs can be compiled to CLP programs with array constraints so that non-termination of the resulting program implies non-termination of the original program, allowing CLP non-termination techniques to be reused for Dalvik. Non-termination of Dalvik bytecode via compilation to CLP (arXiv:1412.3729v1)
[7] Array expressions used as constraints generalize the classical 'element' constraint, and an efficient algorithm encapsulating a set of domain-reduction rules enforces arc-consistency. Constraint Propagation in Presence of Arrays (arXiv:cs/0105024v1)