M2compiler-V3/docs/summary_session-2026-10-24-dynamic-sets.md

Session 2026-10-24 — dynamic SET OF CARDINAL / INTEGER

Gates: suite 310/310, one-shot fixpoint OK (3,845,439 bytes), separate-object fixpoint OK (11 objects), corpus 521/612 compile-OK, 0 crashes.

Representation

SET OF CARDINAL and SET OF INTEGER now use a sorted linked list of disjoint inclusive ranges rather than a wide inline bit-vector:

BigSet = pointer to
  { lo : CARDINAL; hi : CARDINAL; next : pointer }

• empty set = null pointer
• adjacent ranges are merged
• ranges are ordered
• INTEGER values are mapped with the sign-bit flip VAL(CARDINAL, x) XOR 0x80000000
• the full 32-bit base range is available; no 1,000,000-bit window

The runtime helpers live in runtime/syslib/shim.c:

m2bs_incl, m2bs_excl, m2bs_incl_range, m2bs_in
m2bs_copy_to, m2bs_equal, m2bs_bin

What works

• empty and range literals: CS{}, CS{1, 3, 5..7}, IS{-5..-3, 100000}
• INCL / EXCL / IN
• assignment and value/VAR parameters
• equality
• union, intersection, difference and symmetric difference
• record fields (basic use)
• SET OF INTEGER including negative values and the full signed range

Bounded sets such as SET OF [0..100000] keep the existing inline bit-vector representation and the 1,000,000-bit limit.

Limits

• Dynamic SET CONST is not supported yet: a CONST of SET OF CARDINAL/INTEGER is a loud 230 (t_bad_bigconst).
• Record/array assignment containing dynamic sets currently copies the pointer value; deep-copy of such composites is a follow-up.
• The range-list nodes are allocated with malloc; assignment frees the previous list, but there is no GC. Program-exit cleanup is omitted.
• PACKEDSET is unchanged and remains bounded to 32 bits.
• SET OF CARDINAL/INTEGER is not used by the compiler itself, so the fixpoint image remains self-hosting.

Tests

• t_wide_set — bounded wide set plus dynamic cardinal set
• t_bad_setbase — now tests full-range SET OF INTEGER
• t_big_ops — literals/ranges, copy, equality, all four set operators, EXCL, negative integer elements
• t_bad_bigconst — dynamic set constants are rejected for now

Showcase

compiler/tests/showcase25.mod demonstrates the last additions:

• dynamic SET OF CARDINAL and SET OF INTEGER
• union/intersection/difference, INCL/EXCL/IN
• a bounded wide SET OF [0..100000]
• ADDRESS/pointer identity (ADR(p^) = p)

Expected output:

showcase25 sets=42 addr=ok

Tags

• v3-dynamic-sets
• v3-showcase25