Design — multi-dimensional open arrays

Status: design + M1 helpers + M2 fixed storage + M3 open views + M4 builtins (2026-10-23). Rank-2/3 fixed and open arrays use the view ABI; array SIZE/TSIZE and view ADR are implemented. The 1-D open descriptor still uses its legacy {count,data} layout at ABI boundaries. Current gates: suite 295/295, fixpoint OK 3,480,366 bytes, corpus 518/612 compile-OK, 0 crashes.

Interactive decisions already taken:

Keep the per-level descriptor model for array types and indexing.
Payload semantics for SIZE: an array's payload bytes, not the descriptor header.
Full corpus scope: fixed/open 2-D and 3-D arrays, VAR formals, subarray views, row → 1-D open array, 2-D → ARRAY OF BYTE flattening, SIZE/HIGH/ADR, records and constructors.
Reconcile (1) with the corpus by using per-level view descriptors over one contiguous backing block. The existing inline per-row storage is replaced for multi-dimensional arrays only; 1-D arrays/strings keep their current descriptor.

This document records the proposed ABI and implementation plan before any code is changed.

1. Why the current representation cannot satisfy the corpus

V3 currently represents every array value as a descriptor address:

1-D array: { count, data... } (data starts at offset 8).
N-D fixed array: an outer descriptor whose elements are pointers to per-row descriptors; each row descriptor repeats the { count, data... } layout.
SIZE(array) uses ObjectSize, which includes the descriptor header.
ADR(fixed array) returns the descriptor address, not the first element.
ADR(open array) currently exposes the descriptor/slot address.

That layout fails the corpus requirements:

file	requirement
`unbounded`	`VAR a: ARRAY OF ARRAY OF CHAR`; `HIGH(a)`, `HIGH(a[0])`; `a[1,2]`; fixed 2-D actual
`unbounded2`	same, plus `ARRAY BOOLEAN OF ARRAY BOOLEAN OF CHAR`
`unbounded3`	`SIZE(a)=60`, `SIZE(a[0])=12`, `SIZE(a[0][0])=2`, `SIZE(a[0,0])=2`
`unbounded4`	`VAR`/value `ARRAY OF ARRAY OF REAL`; `p[i][j] := q[i,j]`
`unbounded6`	2-D `ARRAY OF CARDINAL` passed to `ARRAY OF BYTE`; `SIZE` agrees
`unbounded8`	row `a[0]` passed to `ARRAY OF BYTE`; `SIZE(a[0])` is row bytes
`array9`	compile an empty 2-D-open procedure
`adrunbounded3`	`ADR(m)=ADR(m[0])=ADR(m[0][0])` for row/element 0; row passed to 1-D `ARRAY OF REAL`

adrunbounded3 and unbounded3 require a flat contiguous view and payload SIZE. Per-row inline descriptors and descriptor-address ADR cannot provide that.

2. Chosen representation

2.1 Type model is unchanged

SymTab keeps the existing array chain:

FArray / FOpenArr -> element type -> element type -> ... -> scalar

ArrayElem, ArrayLo, ArrayHi, ArrayDepth, IsOpenArray and the grammar's nested array construction remain. What changes is the runtime representation of multi-dimensional arrays.

2.2 Two storage families

Keep the current layout for one-dimensional arrays:

1-D fixed/open descriptor: { count, data... }

This preserves strings, ARRAY OF CHAR, FileIO, printf, pointer to array (ADR(a) for a fixed 1-D array), and all existing one-dimensional tests.

For arrays of rank ≥ 2, use one contiguous backing block plus a chain of per-level view descriptors:

ArrayView = record
  count    : LONGCARD;   (* elements at this level *)
  elemBytes: LONGCARD;   (* bytes in one element at this level *)
  stride   : LONGCARD;   (* bytes between adjacent indices *)
  base     : ADDRESS;    (* address of the first element at this level *)
  next     : ADDRESS;    (* next-level view template, or 0 at the leaf *)
end

For a contiguous array stride = elemBytes. elemBytes at an outer level is the size of one lower-dimensional slice; at the final level it is the scalar element size.

Example ARRAY [0..4], [0..5], [0..1] OF CHAR:

outer view:  count=5, elemBytes=12, stride=12, base=payload,
             next -> row template
row template: count=6, elemBytes=2, stride=2, base=0,
             next -> cell template
cell template: count=2, elemBytes=1, stride=1, base=0, next=0

payload: 5 * 6 * 2 contiguous bytes

SIZE is count * elemBytes at each level:

outer: 5 * 12 = 60
row: 6 * 2 = 12
cell (1-D row): 2 * 1 = 2

2.3 Subarray views

m[i] on a multi-dimensional view:

bounds-check i against count;
if next = 0, return base + i * stride (scalar address);
otherwise copy the next template into a fresh stack ArrayView, set its base to base + i * stride, and return the view pointer.

The copied view is an expression temporary. It is valid for the duration of the enclosing expression/call. Open-array variables cannot escape a procedure, so this is sufficient for the supported language.

This gives:

ADR(m[i]) = the copied view's base (first element of row i);
ADR(m[i][j]) = element address;
HIGH(m[i]) = next.count - 1;
passing m[i] to ARRAY OF REAL = build a 1-D open descriptor from the copied view.

2.4 Fixed multi-dimensional arrays

A fixed multi-dimensional array has:

a flat payload block, and
an outer view plus its static per-level templates.

The view can be stored in static data:

data $a_view = { l 5, l 12, l 12, l $a_data, l $a_row }
data $a_row  = { l 6, l 2,  l 2,  l 0,       l $a_cell }
data $a_cell = { l 2, l 1,  l 1,  l 0,       l 0 }
data $a_data = { ... flat payload ... }

For a local fixed array, the view/templates live in the local frame and the payload is a local allocation. Existing one-dimensional arrays keep their current inline descriptor allocation.

A fixed multi-dimensional array field in a record uses inline flat payload storage; a view over that payload is synthesized when the field is indexed/passed. This avoids a heap allocation per record element. One-dimensional array fields stay as they are today.

2.5 Open multi-dimensional formals

An open multi-dimensional formal is passed as a pointer to the outer ArrayView (l), just as 1-D open arrays are passed as an l descriptor pointer.

At a call:

fixed multi actual: materialize the outer view over the fixed payload; its templates are static;
open multi actual to matching-rank formal: pass the existing view;
row subview actual: pass the synthesized row view;
1-D formal: build the existing {count, data} descriptor;
ARRAY OF BYTE/SBYTE formal: build a 1-D byte descriptor with count = payload bytes and data = view.base.

VAR and value open parameters use the same view pointer. Element writes go through base; no payload copy is made. Whole-array copy uses the payload counts and a byte/structured copy.

3. Semantics

3.1 `HIGH`

1-D array: existing count - 1.
multi view: count - 1.
HIGH(m[0]): the copied row view's count - 1.

3.2 `SIZE`

For an array value, SIZE returns payload bytes:

1-D fixed/open: count * elemBytes, excluding the descriptor header;
multi view: count * elemBytes at the current level;
scalar: existing type size.

ObjectSize remains the internal allocation footprint (8 + payload for 1-D inline arrays, plus view/templates for multi). SIZE no longer uses ObjectSize for arrays.

For compatibility, TSIZE should follow the same array payload rule in the first implementation; the internal allocator continues to use ObjectSize. This is called out in the open questions.

3.3 `ADR`

multi-dimensional array/view: first payload element (view.base);
open 1-D array: first payload element (descriptor + 8);
fixed 1-D array: existing descriptor address, keeping POINTER TO ARRAY (t_addrptr) working;
scalar: its address.

The fixed-1-D exception is deliberate. It is documented as a V3 pointer-to-array compatibility rule.

3.4 Indexing

1-D: existing ElemAddr (base + 8 + (i-lo)*elemSize).
multi view: base + (i-lo)*stride, then either scalar address or a copied next-level view.
Multi-index syntax m[i,j] is lowered as the existing chained m[i][j]; no separate layout.
Bounds checks use the type's lower bound and the runtime view count.

3.5 Assignment and whole-array copy

Element assignment uses scalar address.
Row assignment uses the row view payload.
Whole-array assignment checks counts and copies payload bytes (or element-wise for nested records/sets); descriptor/templates are not copied from the source view.
ARRAY OF BYTE flattening is a view, not a copy, so VAR writes are visible to the original array.

3.6 Character arrays

Existing 1-D ARRAY OF CHAR keeps its NUL-terminator slot and HIGH = count-1/OpenHiChar behavior. Multi-dimensional inner CHAR arrays use the declared element counts with no hidden per-row terminator, matching unbounded3 (SIZE(a[0][0])=2 for two CHARs). When a row is adapted to a 1-D ARRAY OF CHAR formal, the adapter uses the row's payload count; the terminator slot is not added implicitly. This is an open question to confirm against ISO.

4. Type system changes

Add queries in SymTab (implemented in M1):

ArrayRank        (t) : CARDINAL       (* ArrayDepth under an ABI name *)
IsMultiArray     (t) : BOOLEAN
ArrayLeafBytes   (t) : CARDINAL       (* scalar/record leaf bytes *)
ArrayStride      (t, level) : CARDINAL
ArrayPayloadSize (t) : CARDINAL       (* only fully fixed arrays *)

ArrayStride/ArrayPayloadSize return 0 for open/unknown counts; M3 will use the runtime view metadata for those cases.

Compatibility rules:

same-rank fixed/open arrays remain compatible by element type and bounds (existing Assignable/VarParamOk rules, extended to rank > 1);
a fixed/open multi view can be passed to a same-rank open formal;
a rank-1 open formal of BYTE/SBYTE accepts any array/view and uses its total payload byte count (unbounded6/unbounded8);
a rank-1 open formal of another element type accepts a rank-1 row view of that element type;
a multi-dimensional actual cannot silently become a 1-D formal of a non-byte element type.

ObjectSize, FieldSize, ElemBytes, TypeSizeD and ArrObjSize need multi-array cases. For a multi array variable/field, the inline slot is the view pointer; the payload is separate/static/local. For 1-D arrays, nothing changes.

5. Lower / QbeGen changes

5.1 New helpers

MakeArrayView(actualType, actualAddr, formalType, VAR q)
ViewBase(view)
ViewCount(view)
ViewSize(view)
ViewHigh(view)
ViewIndex(view, i, lo, lowerType, VAR q)
ViewSub(view, i, VAR q)
FlattenToByteDescriptor(view, VAR q)

The view descriptor is 5 words (40 bytes) per level.

5.2 Call sites

LowerCall needs a small conversion layer before CallArg:

actual rank = formal rank: build/pass view;
actual rank > formal rank 1 and formal is BYTE/SBYTE: flatten;
actual rank = 1 / formal rank = 1: existing descriptor path;
actual row/view to rank-1 open: build 1-D descriptor.

The conversion must not copy VAR payloads. Temporary views may be stack alloc8 objects.

5.3 Builtins

SIZE/TSIZE array arguments dispatch to view size or 1-D count*elem.
HIGH/LEN dispatch to view count.
ADR dispatch as in §3.3.
CopyArray handles flat multi payloads and subviews.
NEW/DISPOSE and ALLOCATE for multi arrays use ObjectSize / payload allocation, not the view size.

5.4 Static data and locals

ArrBodyItems/DeclArr: multi-dimensional static arrays emit view data, templates and flat payload; arrays of records with multi fields recurse per element.
AllocLocal/InitStack: allocate view/templates and payload for local multi arrays.
DeclVar/DeclConst: multi array constructors emit flat payload and views.
Existing one-dimensional array emission remains unchanged.

6. Corpus test mapping

file	expected result after implementation
`unbounded`	`HIGH(a)=4`, `HIGH(a[0])=5`; writes survive
`unbounded2`	same for fixed 2-D `CHAR` and Boolean-index arrays
`unbounded3`	`SIZE` = 60, 12, 2, 2
`unbounded4`	`VAR`/value 2-D REAL assignment works
`unbounded6`	`SIZE(2-D CARDINAL)` equals `SIZE(ARRAY OF BYTE)` (600 bytes)
`unbounded8`	row `a[0]` flattening gives `SIZE=120`
`array9`	compiles and runs
`adrunbounded3`	`ADR` base/row/element, row to 1-D open, `VAR` writes

Unit regressions:

t_multidim fixed 2-D layout/indexing;
t_addrptr fixed 1-D ADR compatibility;
t_arrrecfld 1-D array fields unchanged;
new t_open2d_size, t_open2d_var, t_open2d_high, t_open2d_adr, t_open_flatten_byte, t_open_row_to_1d.

Gates after each step: suite, fixpoint, corpus.

7. Milestones

M1 — type/ABI helpers — done (2026-10-23)
- ArrayRank, IsMultiArray, ArrayLeafBytes, ArrayStride, ArrayPayloadSize in SymTab.
- MaxDefer raised from 256 to 512 (the compiler now declares 257 procedures) and the session SSA buffer raised from 4 to 8 MiB.
- No array layout/codegen change.
M2 — fixed multi storage — done (2026-10-23)
- Static and local rank-2/3 arrays use one contiguous payload and a chain of 40-byte {count, elemBytes, stride, base, next} views.
- ViewIndex produces subviews for array selectors and element addresses for the final scalar selector.
- Pointer-to-multi indexing and NEW/local initialization work.
- Whole-array copy handles new-view sources, plus old nested static constructors via CopyOldNestedToView.
- A compatibility copy-in/copy-back path adapts rank-1 row views to the legacy 1-D {count, data} descriptor for fixed/open formals; this is intentionally temporary until M3.
- Multi-dimensional record fields still use the legacy inline nested layout (M5); t_nestarr remains the regression.
- Tests: t_multidim, t_multidim_local, t_array, t_ctor3, t_nestidx, t_nestarr, t_ptrnest, showcase6; suite 284/284, fixpoint OK, corpus 512/612 with 0 crashes.
M3 — open view descriptors — done (2026-10-23)
- Nested open array formals (ARRAY OF ARRAY OF ...) parse correctly.
- Fixed/open multi-dimensional actuals and rank-2/3 subviews are passed as ArrayView pointers; VAR writes go straight to base.
- Open multi formals index through the view (count, stride, base, next), and HIGH/LEN read the view count. A fixed array, an open formal, a row subview and a forwarded subview all work without rebuilding the payload.
- ARRAY OF BYTE/SBYTE and row → 1-D conversions remain adapted to the legacy 1-D {count, data} descriptor. The temporary adapter allocates a descriptor and, for VAR, copies the payload back; this preserves write-through while the compiler still has the old 1-D ABI and C shims. It is freed after the call. Migrating that legacy 1-D path to a pointer-based view remains a follow-up.
- Tests: t_open2d, t_open2d_value, t_open2d_high, t_open2d_nested, t_open3d, t_open3d_row, t_open_row_to_1d, t_open_flatten_byte. Corpus gains unbounded, unbounded2, unbounded3, unbounded4 and array9 (compile gate).
M4 — array builtins — done (2026-10-23)
- SIZE/TSIZE now use payload bytes for arrays: fixed 1-D count*leaf, open 1-D count*element, and runtime count*elemBytes for every view level. The old descriptor header and 1-D CHAR terminator are excluded.
- ADR returns the first payload byte for multi views, row subviews and 1-D open descriptors; fixed 1-D arrays retain their descriptor address for POINTER TO ARRAY compatibility.
- The M3 row/ARRAY OF BYTE compatibility adapter now appends the legacy CHAR/UCHAR terminator when materialising an external 1-D descriptor, and is freed after VAR copy-back.
- Tests: t_open2d_size, t_open2d_adr, t_open1d_size_adr, plus the M3 open-array tests. unbounded3 runs successfully with SIZE 60/12/2/2.
- Still deferred: migrating the legacy 1-D descriptor itself to a pointer-based view (row ADR identity through a 1-D internal call). The current adapter preserves writes but is copy-based. This does not block the corpus cases that reach the compiler today.
M5 — records/constructors/corpus (multi array fields, records arrays, constructors; run the 8 corpus cases).
M6 — docs/gates/tag v3-open-arrays.

unbounded5 remains a declaration-order case, not this feature.

8. Risks and open questions

View lifetime: subarray views are stack temporaries. Open array parameters cannot escape a procedure, so this is sound for the supported language; storing a view pointer in a global would be invalid and must be rejected or documented.
VAR aliasing: view-based writes must not copy payloads. This needs dedicated tests for nested VAR parameters.
ADR compatibility: fixed 1-D arrays keep descriptor ADR; multi/open arrays use payload base. This asymmetry must be documented.
SIZE/TSIZE: payload vs allocation footprint needs a final decision; the proposed rule is payload for both builtins, ObjectSize for internal allocation.
CHAR terminators: 1-D strings keep a terminator; multi rows use exact counts. Confirm against ISO and unbounded3.
Records/constructors: multi-dimensional array fields and constructors are the highest-risk part; they are not corpus-driven but are in the chosen full scope.
Descriptor chain copies: each m[i] may allocate a 40-byte stack view; nested loops could allocate many views. The allocator is stack bump allocation; no heap lifetime issue.
Multi-index parser: m[i,j] must keep expanding to chained subviews.
Bounds: lower bounds come from the type; views store counts only.
1-D compatibility: all existing string/FileIO/ARRAY OF CHAR behavior must remain byte-identical.

9. Explicit non-goals for the first implementation

ISO generic array descriptors beyond rank 3 (the corpus needs 3).
Open arrays as function results or stored open-array variables.
Dynamic rank.
Changing one-dimensional array/string layout.
Separate compilation of array descriptors (future work).

design-open-arrays.md 18 KB Riwayat Mentahan