# 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:

1. **Keep the per-level descriptor model** for array types and indexing.
2. **Payload semantics** for `SIZE`: an array's payload bytes, not the
   descriptor header.
3. **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.
4. 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:

```text
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:

```text
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**:

```text
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`:

```text
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:

1. bounds-check `i` against `count`;
2. if `next = 0`, return `base + i * stride` (scalar address);
3. 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:

```qbe
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):

```text
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

```text
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

1. **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.
2. **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.
3. **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).
4. **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.
5. **M5 — records/constructors/corpus**
   (multi array fields, records arrays, constructors; run the 8 corpus
   cases).
6. **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).