Collections

Chapter Scope

Fixed arrays, owning dynamic arrays, slices and ordinary indexing have already been covered in:

• Arrays;
• Slices;
• Indexing.

They remain part of Sec's overall collection model, but their full rules are not repeated here.

Chapter 46 covers shaped values such as tensors and matrices rather than ordinary general-purpose collections.

Core Collection Set

More specialized structures such as linked lists, ordered maps or ordered sets belong in libraries as distinct types.

list, map and set Are Compiler-Known Type Constructors

They use lowercase type-constructor syntax:

list[User]
map[UserID, User]
set[Permission]

They require no import and are not standard-library aliases.

Their public compiler-known members are part of the language/core semantic surface. A library cannot silently add privileged members to these types.

Shared Collection Properties

Collection state that is naturally observed is exposed as a property rather than a method.

Canonical spellings include:

collection.Len
collection.IsEmpty

Use uppercase public member spelling.

These are not canonical:

collection.len
collection.IsEmpty()

Len

Len is a read-only uint property.

let userCount := users.Len
let permissionCount := permissions.Len

Its meaning depends on the collection:

• list[T]: number of live logical elements;
• map[K,V]: number of stored entries;
• set[T]: number of stored unique values.

Len never means capacity or byte size.

Reading it does not allocate, consume, mutate or inspect collection elements.

IsEmpty

IsEmpty is a read-only bool property equivalent to Len == 0.

if users.IsEmpty {
    return
}

It evaluates the receiver once and does not allocate or mutate.

Ptr and Instance SizeOf

list[T] guarantees contiguous logical element storage in Sec 0.1. It therefore participates in the contiguous-storage surface:

values.Ptr
values.SizeOf

Ptr is an unsafe raw-pointer observation. It does not transfer ownership, extend lifetime, pin storage or prevent a later structural mutation from invalidating the backing incarnation.

Instance SizeOf describes the byte extent of the represented logical elements, not the size of the list descriptor and not unused capacity.

map[K,V] and set[T] do not expose Ptr. Their physical storage is not a public contiguous sequence contract.

Normal Absence Is Not an Error

Sec does not manufacture an Error merely because a collection operation returns a normal negative result.

Examples:

RemoveAt(invalidIndex)  -> None
Remove(missingValue)    -> false
Contains(missingValue)  -> false
IndexOf(missingValue)   -> None
set.Add(existingValue)  -> Ok(false)

Errors are reserved for failures that prevent a valid requested structural or resource operation from being completed.

CollectionError

Collection-facing structural/resource failure uses CollectionError.

Sec 0.1 defines collection-level cases including:

CollectionError.AllocationFailed
CollectionError.CapacityExceeded
CollectionError.SizeOverflow

The allocation subsystem may still use the lower-level AllocationError. A collection operation may translate that failure into CollectionError.AllocationFailed.

Access-specific errors such as index, range or key-access failures remain in their own error families when a checked access actually requires an Error.

Allocation and Growth

Dynamic collections may grow through the active Sec allocation model.

No hidden global heap is assumed. An allocation-capable structural operation must have a valid allocation context before lowering.

Bounded collection forms instead carry a compile-time maximum capacity and are intended for bounded/no-heap use cases where the relevant backing model can satisfy them.

Allocation, ownership of logical elements and reclamation authority for raw backing remain distinct concepts.

Structural Mutation Is Transactional Where Failure Is Possible

A structural operation that may fail during growth must not leave the collection half-mutated.

On failure, the collection must preserve its previous valid state, including:

• its previous logical length;
• all previously owned elements or entries;
• valid ownership state;
• no partially published new backing;
• no lost input value merely because growth failed.

This principle applies to fallible append, insert, map upsert, set insertion and other structural operations.

Borrowing and Structural Mutation

Ordinary borrow rules apply to collections.

A structural operation that may relocate, resize, rehash or otherwise invalidate storage cannot execute while a conflicting direct element reference, slice, iterator borrow or related dependency remains live.

In-place element mutation may remain legal when it preserves structural stability and ordinary borrow authority.

Sec does not introduce a runtime borrow checker for collections.

Collection Destruction

An owning list, map or set destroys every still-owned live logical element or entry exactly once according to its canonical destruction plan.

After logical element destruction, raw backing is reclaimed only through the resolved allocation/reclamation authority.

Backend container representation must not change source-level destruction semantics.

list[T]

list[T] is Sec's richer variable-length ordered linear collection.

list[User]
list[Packet]

Unlike a linked list, Sec 0.1 list[T] guarantees contiguous logical element storage.

This supports:

• zero-based indexing;
• explicit slices;
• Ptr;
• instance SizeOf;
• ordered iteration;
• order-preserving removal;
• sorting and reversal.

Dynamic and Bounded Lists

Dynamic form:

list[T]

Bounded form:

list[T, Capacity]

The dynamic form may grow through an approved allocation strategy.

The bounded form has runtime-variable Len and a compile-time maximum number of elements.

A bounded list:

• never exceeds its declared maximum capacity;
• does not perform hidden growth allocation beyond its resolved bounded backing model;
• reports capacity exhaustion explicitly;
• is suitable for no-heap targets.

For list[T, Capacity], Capacity must be greater than zero.

The exact physical backing representation is not source semantics.

Empty Lists

Both dynamic and bounded lists have a valid empty state independently of whether T itself is default-constructible.

Canonical explicit empty forms are:

list[T] {}
list[T, Capacity] {}

These are collection literals, not struct literals.

Empty reserved bounded backing does not mean any T value has been constructed.

List Properties

list[T] exposes:

Len
IsEmpty
Ptr
SizeOf
Capacity

Capacity is intentionally source-visible on lists.

For bounded lists it is the compile-time maximum capacity. For dynamic lists it is the currently available logical capacity according to the list contract.

This differs from T[], whose internal capacity is not public source state.

List Indexing

let item := values[index]
values[index] = replacement

let itemRef := ref values[index]
let itemMut := ref mut values[index]

Successful list indexing produces an element Place. Use context determines copy, borrow or mutation.

Runtime indexing does not implicitly move a move-only element out of the list. Use an explicit owning extraction operation such as RemoveAt.

Lists Support Explicit Slices

let all := ref values[..]
let middle := ref values[2..<5]
let writable := ref mut values[..]

Slice creation remains explicit. There is no required AsSlice() or Slice() helper.

A structural list mutation that can invalidate the backing is illegal while a conflicting slice remains live.

List Iteration Preserves Logical Index Order

for item in values {
    Use(item)
}

for index, ref item in values {
    Inspect(index, item)
}

for _, ref mut item in values {
    Update(item)
}

Plain element binding copies the yielded element and therefore requires an implicitly copyable T.

It never silently moves, borrows or clones a move-only element.

Structural mutation that invalidates iteration storage/range is forbidden while the iteration or an element borrow remains active.

Core List Operations

Append(value)
Insert(index, value)
RemoveAt(index)
Remove(value)
Clear()

Contains(value)
IndexOf(value)

Reverse()
Sort()
SortBy(compare)

ToString()
ToString(format)

Higher-level transformation algorithms may be supplied by libraries as free generic algorithms rather than privileged list members.

Append

try values.Append(value)

Append adds one value at the end of the current logical sequence.

It is a structural mutation and may require growth/allocation in the dynamic form.

The collection changes only after successful value transfer and any required growth. Failure must not lose the source value or corrupt the existing list.

Push is not a Sec 0.1 alias for Append.

Insert

Canonical semantic result:

Insert(index, value) -> Result[bool, CollectionError]

Meaning:

Ok(true)
    insertion succeeded

Ok(false)
    insertion position is invalid

Err(error)
    valid insertion could not be completed because of
    structural/resource failure

An invalid position is a normal unsuccessful request, not an IndexError.

Successful insertion preserves list order and may require structural growth.

RemoveAt

Canonical result:

RemoveAt(index) -> Option[T]

For a valid index:

• the removed T is moved out;
• later elements shift one logical position left;
• Len decreases by one;
• no readable hole remains;
• the operation does not allocate;
• the result is Some(removed).

Invalid or negative indices return None. Absence is not an Error.

let removed := values.RemoveAt(index)

Remove

Remove(value) removes one matching value according to the list's equality rules.

Remove(value) -> bool

true means a matching value was removed. false means no matching value existed.

A missing value is not an Error.

Contains and IndexOf

Contains(value) -> bool

IndexOf(value) -> Option[uint]

Contains requires equality semantics for T.

IndexOf returns the first matching logical index. No match returns None.

Clear

values.Clear()

Clearing destroys every still-owned live element, sets Len to zero and retains reusable backing where the representation provides it.

It does not allocate.

Reverse, Sort and SortBy

Reverse() mutates the list in place without allocation.

Sort() is available when T satisfies the required ordering contract.

SortBy(compare) uses the canonical comparison callable form defined by Sec's callable/lambda rules.

Sorting must not silently copy move-only values merely because the implementation algorithm was written for copyable data.

map[K, V]

A map stores unique keys associated with owned values.

map[UserID, User]
map[string, Configuration]

It provides:

• key lookup;
• insertion and replacement;
• removal;
• membership testing;
• entry iteration;
• owned key/value storage;
• stable equality/hash requirements for stored keys.

Hash-based behavior is the default semantic implementation family, but physical bucket representation is not source-visible.

Dynamic and Bounded Maps

Dynamic:

map[K, V]

Bounded:

map[K, V, Capacity]

The bounded form has a compile-time maximum entry count.

The dynamic form may grow through an approved allocation strategy. No hidden global heap is assumed.

Unlike lists, the Sec 0.1 map base surface does not expose a public Capacity property.

Map Iteration Order Is Unspecified

Programs must not depend on:

• insertion order;
• bucket order;
• sorted key order;
• target-specific traversal order.

Ordered associative behavior belongs in a separate ordered-map type.

Map Properties

The required read-only properties are:

Len
IsEmpty

A map does not provide base members:

Ptr
First
Last

First or Last would incorrectly make unspecified traversal order part of the public contract.

Map Lookup Uses Indexing Syntax

let user := try users[id]

A successful lookup produces the value Place for the existing entry.

Use context then determines whether the value is:

• copied;
• shared-borrowed;
• mutably borrowed.

A lookup does not insert.

A missing key is a checked key-access failure and can use ordinary try handling according to the access/error rules.

Map Mutation Uses Indexed Upsert Assignment

try users[id] = user

Semantics:

existing key:
    replace the stored V

missing key:
    insert a new K/V entry

When structural growth/resource failure is possible, the operation has the operation-level shape:

Result[void, CollectionError]

Sec does not add a separate Set() method.

The assignment operator is =, not :=. := remains declaration/initialization syntax.

Explicit move assignment may use ordinary canonical move assignment:

try users[id] <- user

Exact move behavior remains governed by ownership and assignment rules.

Remove

Remove(key) -> Option[V]

Some(value) transfers ownership of the removed value.

None means the key was absent. Missing keys are not an Error for removal.

ContainsKey

ContainsKey(key) -> bool

This tests key membership without performing insertion.

Map Iteration Has Exactly Two Logical Bindings

for key, value in users {
    Use(key, value)
}

for ref key, ref value in users {
    Inspect(key, value)
}

for ref key, ref mut value in users {
    Update(key, value)
}

A single-binding map loop is invalid because map iteration yields key and value as distinct logical components.

Plain bindings copy their components and therefore require those component types to be implicitly copyable.

A discarded component _ does not force a copy or move merely to discard it.

Structural mutation during a conflicting active iteration borrow is invalid.

Stored Map Keys Must Preserve Equality and Hash Identity

Mutable value references may be permitted when the map is mutably borrowed.

Mutable references to stored keys are not permitted:

for ref mut key, value in users {    // invalid
    ...
}

A stored key cannot be mutated in a way that changes the equality/hash identity under which it is stored.

set[T]

A set stores unique values and provides membership, insertion, removal, iteration and set algebra.

set[Permission]
set[UserID]

Stored values participate in the set's equality/hash identity while present.

Dynamic and Bounded Sets

Dynamic:

set[T]

Bounded:

set[T, Capacity]

The dynamic form may grow through an approved allocation strategy. The bounded form has a compile-time maximum value count.

The Sec 0.1 base set surface does not expose a public Capacity property.

Set Iteration Order Is Unspecified

A program cannot depend on insertion, bucket, sorted or target-specific traversal order.

Ordered-set semantics belong in a distinct collection type.

Set Properties

Len
IsEmpty

A set does not expose base members:

Ptr
First
Last

Its physical storage is not a public contiguous sequence contract.

Add

Canonical result:

Add(value) -> Result[bool, CollectionError]

Meaning:

Ok(true)
    value was inserted

Ok(false)
    value was already present

Err(error)
    valid insertion could not be completed because of
    structural/resource failure

Inserting a value already present is a normal successful non-insertion outcome, not an Error.

Remove and Contains

Remove(value) -> bool
Contains(value) -> bool

Remove returns false when the value was absent.

Contains reports membership.

Absence in either operation is not an Error.

Set Algebra

Sec 0.1 includes the non-mutating operations:

Union(other)
Intersection(other)
Difference(other)
SymmetricDifference(other)

They produce a new owning set.

Because the receiver remains intact, the operations require the ordinary non-consuming copy semantics needed to populate the result.

For move-only T, these non-consuming set-algebra members are unavailable. Use explicit ownership-moving logic instead.

When constructing the result may fail because of allocation or structural resources, the result is returned through:

Result[set[...], CollectionError]

The concrete bounded or dynamic set type is preserved according to the operation's collection rules.

No hidden element copying or hidden allocation is allowed.

Set Iteration

for value in activeUsers {
    Use(value)
}

for ref value in activeUsers {
    Inspect(value)
}

Plain iteration copies the stored value and therefore requires an implicitly copyable element type.

Shared-reference iteration is permitted when stable addressable storage is available.

Mutable-reference set iteration is invalid because mutating a stored value could change its equality/hash identity:

for ref mut value in activeUsers {    // invalid
    ...
}

Ordinary iteration never moves an owned element out of the set.

Move-Only Elements Are Never Silently Copied

Collection algorithms must preserve ordinary Sec copy/move classification.

In particular:

• plain iteration cannot copy a move-only element;
• ordinary indexed read does not move an element out merely because it is move-only;
• sorting must use move-aware implementation when needed;
• set algebra requiring non-consuming duplication is unavailable for move-only elements;
• explicit extraction operations transfer ownership according to their declared result.

A backend container implementation cannot introduce implicit clone/copy behavior to simplify implementation.

Collections and FFI

Lists, maps and sets do not have one general FFI-stable descriptor representation.

A foreign wrapper must use explicitly ABI-compatible components and define pointer, lifetime, retention and ownership rules.

For contiguous list data, low-level wrappers may use:

unsafe {
    ForeignCall(values.Ptr, values.SizeOf)
}

This exposes the current data pointer and logical payload byte extent. Neither operation transfers ownership or extends storage lifetime.

If the foreign API wants element count rather than byte count, pass values.Len instead.

Maps and sets require an explicit conversion or wrapper representation suitable for the foreign API rather than exposing their internal buckets.

Compiler Analysis Understands Collection Semantics

Collection operations are not treated as opaque arbitrary method calls.

Analysis tracks facts such as:

• logical Len changes;
• structural mutation;
• allocation capability;
• possible relocation;
• storage-domain/epoch invalidation;
• borrow conflicts;
• element destruction;
• element copy/move requirements;
• normal absence versus Error;
• fallible mutation and try propagation;
• iteration mutation restrictions;
• map/set key identity restrictions.

Static proof may remove checks or improve diagnostics without changing source-level result types.

Collection Categories Remain Distinct in Semantic IR

The compiler preserves distinct semantic categories equivalent to:

ListType(T, optional bounded capacity)
MapType(K, V, optional bounded capacity)
SetType(T, optional bounded capacity)

One category must not be lowered as another merely because a backend could share an implementation structure.

Structural operations remain visible until allocation effects, ownership transfer, destruction, borrow invalidation, storage transitions and error propagation have been verified.

Backend representation never chooses source semantics.

Diagnostics

Bounded capacity exhaustion

cannot append to `values`

the bounded list has reached its maximum capacity

type:
    list[Packet, 32]

help: remove an element
help: increase the compile-time capacity
help: use a dynamic list where allocation is permitted

Structural mutation during borrow

cannot structurally modify `values`

a live slice still depends on the current list backing:
    let view := ref values[..]

later use:
    Process(view)

Map iteration requires two bindings

map iteration yields key and value

invalid:
    for entry in users

use:
    for key, value in users

Mutable map key borrow

cannot mutably borrow a stored map key

map keys must preserve equality/hash identity while stored

help: remove the entry and insert it again with the new key

Mutable set element iteration

cannot iterate `set[T]` with `ref mut`

stored set values participate in equality/hash identity

help: iterate with `ref`
help: remove and reinsert values when identity must change

Move-only element copied by plain iteration

plain iteration would copy move-only element type `Resource`

help: borrow the element:
    for ref item in resources

Normal absence is not an error

`RemoveAt` returns Option[T]

an invalid position produces None rather than IndexError

help: match Some/None
help: use an access operation when checked indexing semantics are required

Diagnostics should distinguish invalid access, normal unsuccessful mutation, allocation/resource failure, capacity exhaustion, borrow conflict and forbidden identity mutation.

LSP and Tooling

The LSP consumes the same compiler-known collection semantics as Sema.

Tooling may expose:

• dynamic versus bounded collection form;
• logical length;
• list capacity;
• allocation capability;
• whether an operation is structural;
• possible backing invalidation;
• copy/move requirements;
• required equality/hash or ordering capabilities;
• normal absence result versus structural Error;
• iteration order guarantees;
• why a member is unavailable for a concrete element type.

Completion should not suggest non-canonical helpers such as Push, Set, AsSlice or Iterator as base collection APIs.

Best Practices

• Use list[T] when ordered indexed storage needs search/sort and source-visible capacity semantics.
• Use map[K,V] when values are addressed by unique keys.
• Use set[T] when only uniqueness and membership matter.
• Use bounded forms when a compile-time maximum is part of the memory/resource design.
• Do not rely on map or set iteration order.
• Use a distinct ordered collection type when order is semantically important.
• Use Len and IsEmpty as properties, not methods.
• Use Append, not a non-canonical Push alias.
• Use indexed assignment for map upsert rather than inventing Set().
• Use Option or bool for ordinary not-found/absence results.
• Reserve CollectionError for real structural or resource failures.
• Borrow move-only elements instead of relying on plain copying iteration.
• Use explicit extraction operations when ownership must leave a collection.
• Do not structurally mutate a collection while live references, slices or iterator borrows depend on its current backing.
• Never mutably borrow map keys or set elements while stored.
• Use Ptr only on collection types with a public contiguous-storage contract and only inside appropriate unsafe code.
• Do not expose internal map/set representation across FFI boundaries.

Summary

• Sec's richer built-in collection types are list[T], map[K,V] and set[T].
• They are compiler-known lowercase type constructors requiring no import.
• They are not standard-library aliases.
• Arrays, slices and indexing are covered in chapters 19–21 and are not repeated here.
• Shaped values are covered separately in chapter 46.
• Len is a read-only uint logical element/entry count.
• IsEmpty is a read-only bool property equivalent to Len == 0.
• Canonical public collection properties use uppercase spelling.
• Normal absence should use bool or Option, not an Error.
• Collection structural/resource failures use CollectionError.
• CollectionError includes allocation failure, bounded-capacity exhaustion and size overflow cases.
• Access errors remain in access-specific error families.
• No hidden global heap is assumed.
• Fallible structural growth is transactional.
• Structural mutation cannot invalidate a live conflicting reference, slice or iteration borrow.
• Owning collections destroy still-owned live elements/entries exactly once.
• Backing reclamation follows the resolved allocation/reclamation authority.
• list[T] is an ordered variable-length contiguous collection, not a linked list.
• list[T, Capacity] is a bounded list with runtime Len and compile-time maximum capacity.
• Bounded list Capacity must be greater than zero.
• Lists have canonical empty collection literals list[T] {} and list[T, Capacity] {}.
• An empty list does not construct any T merely because backing capacity exists.
• Lists expose Len, IsEmpty, Ptr, SizeOf and Capacity.
• List capacity is intentionally source-visible.
• List indexing produces an element Place.
• Runtime indexed access does not implicitly move move-only elements out of a list.
• Lists support explicit shared and mutable slices.
• List iteration preserves logical index order.
• Plain list iteration copies and therefore requires implicitly copyable elements.
• List iteration supports shared and mutable element borrows where authority permits.
• List structural mutation may not invalidate active iteration/slice dependencies.
• Core list operations include Append, Insert, RemoveAt, Remove, Clear, Contains, IndexOf, Reverse, Sort and SortBy.
• Push is not an alias for Append.
• List Insert returns Result[bool, CollectionError].
• Invalid Insert position is Ok(false), not an index Error.
• List RemoveAt returns Option[T].
• Valid RemoveAt moves the removed element out and shifts later elements left.
• Invalid RemoveAt returns None.
• List Remove returns bool.
• List Contains returns bool.
• List IndexOf returns Option[uint].
• List Clear destroys live elements, sets Len to zero and retains reusable backing where available.
• List Reverse mutates in place and does not allocate.
• List Sort is available when T satisfies ordering requirements.
• SortBy uses the canonical comparison callable form.
• Sorting cannot silently copy move-only elements.
• map[K,V] stores unique keys associated with values.
• map[K,V,Capacity] has a compile-time maximum entry count.
• Maps do not expose a base Capacity property in Sec 0.1.
• Hash-based behavior is the default semantic implementation family for maps.
• Map physical representation is not source-visible.
• Map iteration order is unspecified.
• Programs must not depend on insertion, bucket, sorted or target-specific map order.
• Maps expose Len and IsEmpty but not Ptr, First or Last.
• Map lookup uses indexing syntax.
• Successful map lookup produces the existing value Place.
• Map lookup does not insert.
• Missing-key access follows checked key-access semantics.
• Map upsert uses fallible indexed assignment such as try users[id] = user.
• Map upsert replaces an existing value or inserts a missing key/value entry.
• Sec does not define a base map Set() method.
• Map upsert uses =, not declaration operator :=.
• Explicit move upsert may use ordinary canonical move assignment.
• Map Remove returns Option[V] and transfers removed-value ownership.
• Map ContainsKey returns bool.
• Map iteration has exactly key and value binding positions.
• Plain map bindings copy their components and require implicit copyability.
• Shared references to map keys/values may be available when entries are stably addressable.
• Mutable map value references require mutable authority.
• Mutable map key references are invalid while the key is stored.
• Stored map keys must preserve equality/hash identity.
• set[T] stores unique values.
• set[T,Capacity] has a compile-time maximum value count.
• Sets do not expose a base Capacity property in Sec 0.1.
• Set iteration order is unspecified.
• Sets expose Len and IsEmpty but not Ptr, First or Last.
• Set Add returns Result[bool, CollectionError].
• Ok(true) means inserted; Ok(false) means already present.
• An already present set value is not an Error.
• Set Remove returns bool.
• Set Contains returns bool.
• Set algebra includes Union, Intersection, Difference and SymmetricDifference.
• Non-mutating set algebra produces a new owning set.
• Set algebra requiring element copying is unavailable for move-only T.
• Allocation-capable set algebra returns the new set through Result[..., CollectionError].
• Set iteration may copy or shared-borrow stored values.
• ref mut set iteration is invalid because stored values participate in equality/hash identity.
• Ordinary collection iteration never implicitly moves owned elements out.
• Move-only collection elements are never silently copied or cloned.
• Lists may expose Ptr/SizeOf because contiguous logical storage is part of their public contract.
• Maps and sets do not expose Ptr because their internal storage is not a public contiguous sequence.
• Lists, maps and sets do not have a general FFI-stable descriptor ABI.
• Collection Sema tracks Len changes, structural mutation, allocation, relocation, borrows, destruction, ownership and absence/error semantics.
• List, map and set remain distinct semantic IR categories even when backend implementation could share data structures.
• The backend does not choose collection source semantics.