Skip to content

Indexing and Sequence Contracts

Accepted

Accepted for V1 indexing, sequence, mutable sequence, and default index-iterator semantics.

This document records the standard contract families used by indexing and sequences.

Contract Families

The indexing and iteration model uses these semantic contracts:

fn require_concrete_sized(comptime T: Type, comptime what: []const u8) void {
  if !T.is_concrete() or !T.is_sized() {
    Compiler.err(.{ .message = what })
  }
}

fn Indexable(comptime T: Type) Type {
  require_concrete_sized(T, "Indexable element type must be concrete and sized")

  return contract {
    fn at(self: *const Self, index: usize) *const T
  }
}

fn MutableIndexable(comptime T: Type) Type {
  require_concrete_sized(T, "MutableIndexable element type must be concrete and sized")

  return contract(Indexable(T)) {
    fn at_mut(self: *Self, index: usize) *T
  }
}

fn Sequence(comptime T: Type) Type {
  require_concrete_sized(T, "Sequence element type must be concrete and sized")

  return contract(Indexable(T), Iterable(*const T)) {
    fn len(self: *const Self) usize

    fn iter(self: *const Self) comptime Iterator(*const T)
      if ContractSurface.current().is_static()
    {
      return IndexIterator(Self, T){ .seq = self, .index = 0 }
    }

    fn contains(self: *const Self, value: *const T) bool
      if T.implements(PartialEq(T))
    {
      for item in self {
        if item.* == value.* {
          return true
        }
      }

      return false
    }
  }
}

fn MutableSequence(comptime T: Type) Type {
  require_concrete_sized(T, "MutableSequence element type must be concrete and sized")

  return contract(Sequence(T), MutableIndexable(T), MutableIterable(*T)) {
    fn iter_mut(self: *Self) comptime Iterator(*T)
      if ContractSurface.current().is_static()
    {
      return MutableIndexIterator(Self, T){ .seq = self, .index = 0 }
    }
  }
}

MutableSequence(T) explicitly depends on both Sequence(T) and MutableIterable(*T). Sequence(T) provides readonly finite/index semantics and inherited Iterable(*const T). MutableIterable(*T) adds mutable iteration. This explicit dependency graph avoids a global mutable-to-readonly iterable coercion while still allowing mutable sequences to be used where readonly sequences are expected.

The helper is illustrative. These are ordinary comptime functions returning contract Type values, so parameter validation should use ordinary function-body checks and Compiler.err, not special contract syntax.

Indexable(T) means the type supports usize indexing syntax. It does not universally mean finite checked collection semantics. The implementation defines what indices mean. Compiler-owned array and slice implementations follow Catalyst's Checked safety-mode bounds policy.

Sequence(T) adds finite iteration semantics:

  • len() returns the finite iteration count
  • static iter() provides Iterable(*const T) through an index-based iterator
  • inherited Iterable(*const T).iter_dyn() provides dynamic iteration by boxing the static iterator and may fail if allocation fails
  • dyn Sequence(T) exposes len() and at() dynamically when the applied surface is dyn-safe
  • dynamic sequence iteration still yields *const T through inherited Iterable(*const T).iter_dyn(), not copied T values
  • contains() is available when T implements PartialEq(T)
  • every index in 0..len() is valid for Indexable.at
  • iteration order is from 0 to len, exclusive
  • behavior outside 0..len() belongs to the underlying Indexable semantics

Box(dyn Sequence(T)) and Box(dyn MutableSequence(T)) do not receive required V1 Sequence / MutableSequence forwarding implementations. The canonical owned dynamic Box model is documented in Box Resource. Sequence operations such as len, at, and at_mut are called through explicit borrowed dynamic pointers:

var seq: Box(dyn Sequence(T)) = ...
const n = seq.ptr_const().len()

Borrowed dynamic pointers expose inherited contract operations, so dynamic iteration over a boxed sequence can still be requested explicitly through the borrowed sequence surface:

var it = try seq.ptr_const().iter_dyn(alloc)
defer it.dispose()

Alternatively, ownership can be reshaped first with an explicit upcast to the inherited iterable surface:

var iterable = (move seq).upcast(Iterable(*const T))
var it = try iterable.iter_dyn(alloc)
defer it.dispose()

The direct owner call remains rejected unless the erased owner type is exactly one of the required boxed iterable forwarding cases:

var it = try seq.iter_dyn(alloc) // error

This preserves the closed boxed dynamic forwarding surface for iterator ergonomics only.

For a fixed readonly receiver state, Sequence(T) is repeatable and index-consistent: repeated len() calls produce the same count, indexes in 0..len() remain valid, at(i) refers to the same logical element, and iter() / iter_dyn() yield those elements in index order. Because Sequence(T) inherits Iterable(*const T), sequence iteration is location-consistent with indexing: the item yielded for index i is a pointer to the same logical element exposed by at(i), not merely an equal copied value. This is not a historical snapshot promise. Mutating the sequence may change later len, at, and iteration results. Existing iterator invalidation and element-pointer stability across mutation are type-specific unless the type documents stronger guarantees.

MutableIndexable(T) must be consistent with Indexable(T) for the same index. A mutable element access should refer to the same logical element that readonly indexing reads.

For MutableSequence(T), mutable iteration is location-consistent with at_mut(i): the item yielded for index i is a mutable pointer to the same logical element that at_mut(i) would expose in the same receiver state.

Source syntax mapping for loops, loop binding patterns, and item type annotations is documented in Iterator Loop Sources. Sequence-specific item shape follows from the sequence contract dependencies:

items[i]             // Indexable(T)
items[i] = value     // MutableIndexable(T)
for item in seq       // Sequence(T)'s Iterable(*const T)
for var item in seq   // MutableSequence(T)'s MutableIterable(*T)

For MutableSequence(T), plain for item in xs uses the readonly Iterable(*const T) dependency while for var item in xs uses MutableIterable(*T).

Value-read indexing loads or copies the element:

var x = items[i]
var p = &items[i]
items[i] = value

Plain Iterable(Item) is not inherently pointer-yielding. It may yield values, readonly pointers, mutable pointers, or resource values depending on Item. Range(T) and RangeInclusive(T) are canonical V1 value-yielding iterables: iterating a range yields integer values such as i32 or usize. Ranges do not implement Sequence(T) in V1. The pointer-yielding convention belongs specifically to Sequence(T) and MutableSequence(T) through their inherited Iterable(*const T) and MutableIterable(*T) contracts.

Sequence(T) provides Iterable(*const T) for free through its default static iter and dynamic iter_dyn. MutableSequence(T) provides MutableIterable(*T) for free through its default static iter_mut and dynamic iter_dyn_mut. Static dispatch and monomorphization are the normal performance path; optimized lowering may become direct pointer iteration when equivalent.

Sequence(T) does not declare its own separate dynamic iteration operation. Dynamic sequence iteration is exactly the inherited Iterable(*const T).iter_dyn() surface. Likewise, MutableSequence(T) uses the inherited MutableIterable(*T).iter_dyn_mut() surface. A sequence implementation may still override the inherited iterable operation when it has a better implementation, but the contract shape remains iterable, not sequence-specific.

IndexIterator and MutableIndexIterator are ordinary prelude helper type names used by the default Sequence.iter and MutableSequence.iter_mut implementations. They are not compiler magic. Implementations may override the defaults when they have a better static iterator type.