M2compiler-V3/docs/summary_showcase23-dlist-2026-10-16.md

Showcase 23 — generic doubly linked list (2026-10-16)

Branch resolve-check, tree clean. Suite 218/218; fixpoint OK (3,711,046 bytes); corpus 372 OK / 0 crash.

The showcase

showcase23.mod builds a doubly linked list with the generic module DList (T : TYPE) instantiated as IntList = DList(INTEGER):

GENERIC DEFINITION MODULE DList (T : TYPE);
TYPE
  Node = POINTER TO NodeRec;
  NodeRec = RECORD val : T; prev, next : Node; END;
  List = RECORD head, tail : Node; count : INTEGER; END;
PROCEDURE Init(VAR l : List);
PROCEDURE Append(VAR l : List; v : T);
PROCEDURE Prepend(VAR l : List; v : T);
PROCEDURE Count(VAR l : List) : INTEGER;
PROCEDURE Get(VAR l : List; i : INTEGER) : T;
PROCEDURE First / Last(VAR l : List) : T;
PROCEDURE Reverse(VAR l : List);
END DList.

Run wired as expect_run_files_out Showcase23 35 "list: 5 10 20":

list: 5 10 20
reversed: 20 10 5
sum=35

Files: showcase23lib.def/.mod (the generic), showcase23int.def/.mod (IntList = DList(INTEGER)), showcase23.mod (the program).

Bug found and fixed (general, not generic-specific)

While writing it, WHILE i < IntList.Count(l) DO … END returned 0. The cause was in QbeGen.RecItems: a record's static data initialiser emitted w 0 (4 bytes) for every scalar field, including pointers and LONGINT/proc (8-byte) fields, while the record layout gives them 8 bytes. A global of such a record was therefore under-sized, and the next globals overlapped and clobbered its tail — here List.count.

VAR g : L; a : INTEGER;      (* L = RECORD head, tail : P; n : INTEGER END *)
g.n := 5; a := 37;           (* a clobbered g.n, at offset 16 *)

Fixed by emitting l 0 for ClPtr/ClLong/ClProc fields (real/char/ set/array/record were already size-correct). Regression: t_recptr (exits 42 only when g.n survives). $g now emits { l 0, l 0, w 0 } instead of { w 0, w 0, w 0 }.

Limitations met (not fixed — recorded)

1. Arithmetic on a type formal in a template. Sum over T (s : T; s := s + n^.val) is 211 at template parse: an unbound formal alias is class ClPtr (pointer-like), so numeric checks fail. Workaround used: do the arithmetic in the concrete program (acc := acc + Get(l, i)). A principled fix is to let checks skip an unbound type formal (a distinct form from an opaque alias).
2. Proc-typed formals in a DEFINITION/IMPLEMENTATION pair trip a false 235 ("implementation does not match definition"): proc types are not deduped, so the def's and impl's constructed proc type have different TypeIndexes and the signature snapshot compares unequal. Not used in the showcase for that reason.

Both are follow-ups; neither affects the showcase.

Verify

cd .../m2compiler-V3/compiler
./M2 ../stdlib/sysio.def ../stdlib/sysio.mod \
    tests/showcase23lib.def tests/showcase23lib.mod \
    tests/showcase23int.def tests/showcase23int.mod tests/showcase23.mod