Section 18: Const Generics

Goal: Enable type parameters that are compile-time constant values

Criticality: Medium — Type-level programming, fixed-size arrays

Dependencies: Sections 1-2 (Type System Foundation), Section 5 (Type Declarations — for compound type eligibility in 18.8) Blocked by: Monomorphization infrastructure — base monomorphization must be complete before const generics can be compiled through AOT. The GenericArg enum and MonoInstance pipeline handle both type and const value arguments.

Design Decisions

Question	Decision	Rationale
Value types	`int`, `bool` initially	Start simple, expand later
Const-generic syntax	`$N: int`	Consistent with Ori’s `$` sigil for immutable bindings
Fixed-capacity list syntax	`[T, max N]`	Reads naturally, distinct from fixed-size arrays
Fixed-size array syntax	`[T, size N]` (future)	Clear distinction from max capacity
Const expressions	Limited initially	Avoid complexity
Default values	Supported	API ergonomics

Reference Implementation

Rust

~/projects/reference_repos/lang_repos/rust/compiler/rustc_middle/src/ty/consts.rs    # Const type representation
~/projects/reference_repos/lang_repos/rust/compiler/rustc_hir/src/def.rs             # ConstParam definition
~/projects/reference_repos/lang_repos/rust/compiler/rustc_hir_typeck/src/lib.rs      # Const generic checking

18.0 Const Evaluation Termination

Proposal: proposals/approved/const-evaluation-termination-proposal.md

Specifies termination guarantees and limits for compile-time constant evaluation, preventing infinite computation during compilation.

Implementation

18.1 Const Type Parameters

Proposal: proposals/approved/const-generics-proposal.md

Spec section: spec/08-types.md § Const Generic Parameters

Syntax

// Const parameter in type (using $ sigil for const)
type Array<T, $N: int> = {
    data: [T, max N],
    // len is known at compile time: N
}

// Usage
let arr: Array<int, 5> = Array.new()
arr[0] = 42

// In functions
@zeros<$N: int> () -> Array<int, N> = ...

let five_zeros: Array<int, 5> = zeros()

Grammar

TypeParameter = Identifier [ ':' TypeBound ]
              | '$' Identifier ':' ConstType ;
ConstType     = 'int' | 'bool' ;

Implementation

18.2 Fixed-Capacity Lists

Proposal: proposals/approved/fixed-capacity-list-proposal.md

Inline-allocated lists with compile-time maximum capacity and runtime-dynamic length.

Syntax

// Type: list of T with maximum capacity N
[T, max N]

// Examples
let buffer: [int, max 10] = []
buffer.push(1)          // OK
buffer.push(11)         // PANIC after 10 elements

// Generic over capacity
@swap_ends<T, $N: int> (items: [T, max N]) -> [T, max N] = ...

Implementation

18.3 Fixed-Size Arrays (Future)

Spec section: spec/08-types.md § Fixed-Size Arrays

Note: This is a future extension. Fixed-capacity lists ([T, max N]) are prioritized first. Fixed-size arrays always have exactly N elements, unlike fixed-capacity lists which have 0 to N elements.

Syntax (Proposed)

// Array type with fixed size (always exactly N elements)
let arr: [int, size 5] = [0, 0, 0, 0, 0]

// Array operations
let len = len(collection: arr)  // Const 5, known at compile time
let elem = arr[2]               // Bounds checked at compile time if index const

// Distinct from fixed-capacity: cannot have fewer than N elements
// [int, size 5] ≠ [int, max 5]

Type Rules

[T, size N] where N: int (const)
- Length always exactly N, known at compile time
- Inline allocated (no heap)
- Cannot be empty, cannot grow, cannot shrink
- Bounds checks can be optimized away for const indices

Implementation (Deferred)

18.4 Const Expressions in Types

Spec section: spec/08-types.md § Const Expressions

Syntax

// Arithmetic in const position
type Matrix<$ROWS: int, $COLS: int> = {
    data: [float, max ROWS * COLS],
}

// Const function in type
$double (n: int) -> int = n * 2

type DoubleArray<$N: int> = {
    data: [int, max $double(n: N)],
}

// Conditional const
type Buffer<$SIZE: int> = {
    data: [byte, max if SIZE > 0 then SIZE else 1],
}

Allowed Expressions

Const parameters: N, M
Literals: 5, true
Arithmetic: N + M, N * 2, N / 2
Comparison: N > 0, N == M
Const functions: $func(n: N)
Conditionals: if N > 0 then N else 1

Implementation

18.5 Const Bounds

Proposal: proposals/approved/const-generic-bounds-proposal.md

Spec section: spec/08-types.md § Const Bounds

Formalizes const generic bounds (e.g., where N > 0), including allowed constraints, evaluation semantics, constraint propagation, and error handling.

Syntax

// Bound on const parameter value
@non_empty_array<$N: int> () -> [int, max N]
    where N > 0  // Const bound
= ...

// Multiple bounds (combined with && or separate where clauses)
@matrix_multiply<$M: int, $N: int, $P: int> (
    a: Matrix<M, N>,
    b: Matrix<N, P>,
) -> Matrix<M, P>
    where M > 0 && N > 0 && P > 0
= ...

// Arithmetic and bitwise in bounds
@power_of_two<$N: int> ()
    where N > 0 && (N & (N - 1)) == 0  // Bit trick for power of 2
= ...

// Bool const generics with bounds
@either_or<$A: bool, $B: bool> () -> int
    where A || B  // At least one must be true
= if A then 1 else 2

Implementation

18.6 Default Const Values

Spec section: spec/08-types.md § Default Const Values

Syntax

// Default value for const parameter
type Buffer<$SIZE: int = 1024> = {
    data: [byte, max SIZE],
}

// Usage
let buf: Buffer = Buffer.new()           // SIZE = 1024
let small: Buffer<256> = Buffer.new()    // SIZE = 256

// In functions
@create_buffer<$SIZE: int = 4096> () -> Buffer<SIZE> = ...

let default_buf = create_buffer()         // 4096
let custom_buf = create_buffer<8192>()    // 8192

Implementation

18.7 Const in Trait Bounds

Spec section: spec/09-properties-of-types.md § Const in Traits

Syntax

// Trait with const parameter
trait FixedSize {
    $SIZE: int
}

impl [int, max 5]: FixedSize {
    $SIZE: int = 5
}

// Use in bounds
@total_size<T: FixedSize, $N: int> () -> int = T.SIZE * N

// Associated const in generic context
@print_size<T: FixedSize> () -> void = {
    print(msg: `Size: {T.SIZE}`)
}

Implementation

Section Completion Checklist

Exit Criteria: Can implement a matrix library with compile-time dimension checking

Verification Gaps (2026-03-29)

GAP-18-001: Parser-to-TypeChecker gap for const bounds [Major] — WhereClause::ConstBound parsed but silently ignored by type checker (as_type_bound() returns None, filtered by filter_map). where N > 0 compiles without enforcement. Location: compiler/ori_types/src/check/registration/impls.rs
GAP-18-002: Const param body binding without call-site resolution [Major] — Const params bind in function bodies but cannot be instantiated with concrete values (f<5>()). LLVM monomorphize has GenericArg::Const ready but type checker never produces ConstValue arguments. Location: compiler/ori_types/src/infer/expr/calls/
GAP-18-004: No negative tests for const generics [Major] — Zero #compile_fail tests. No verification that $N: str, $N: float, or type mismatches are rejected.
GAP-18-005: No LLVM/AOT coverage for any 18.x item [Major] — All ori_llvm/tests/const_generic_tests.rs references are non-existent files. Monomorphize infrastructure exists but is untested end-to-end.

Example: Matrix Library

type Matrix<$ROWS: int, $COLS: int> = {
    data: [float, max ROWS * COLS],
}

impl<$ROWS: int, $COLS: int> Matrix<ROWS, COLS> {
    @new () -> Matrix<ROWS, COLS> = Matrix {
        data: [],  // Will be filled with zeros
    }

    @get (self, row: int, col: int) -> float = {
        assert(condition: row >= 0 && row < ROWS)
        assert(condition: col >= 0 && col < COLS)
        self.data[row * COLS + col]
    }

    @set (self, row: int, col: int, value: float) -> void = {
        assert(condition: row >= 0 && row < ROWS)
        assert(condition: col >= 0 && col < COLS)
        self.data[row * COLS + col] = value
    }

    @rows (self) -> int = ROWS  // Compile-time constant

    @cols (self) -> int = COLS  // Compile-time constant
}

// Matrix multiplication with dimension checking at compile time
@multiply<$M: int, $N: int, $P: int> (
    a: Matrix<M, N>,
    b: Matrix<N, P>,
) -> Matrix<M, P> = {
    let result = Matrix.new()

    for i in 0..M do
        for j in 0..P do
            let sum = 0.0
            for k in 0..N do
                sum = sum + a.get(row: i, col: k) * b.get(row: k, col: j)
            result.set(row: i, col: j, value: sum)

    result
}

// Usage
let a: Matrix<2, 3> = Matrix.new()
let b: Matrix<3, 4> = Matrix.new()
let c: Matrix<2, 4> = multiply(a: a, b: b)  // Types checked at compile time!

// This would be a compile error:
// let bad: Matrix<2, 5> = multiply(a: a, b: b)  // Error: dimension mismatch

18.8 Expanded Const Generic Eligibility (Capability Unification)

Proposal: proposals/approved/capability-unification-generics-proposal.md — Phase 3

Replace the {int, bool} whitelist with: any type with Eq + Hashable is const-eligible. This expands const generics to str, char, byte, user enums, user structs, and compound types.

Blocked by: Section 5.5 (Compound Type Inference) — needed for [int] and (T, U) eligibility

Implementation

18.9 Associated Consts in Traits (Capability Unification)

Proposal: proposals/approved/capability-unification-generics-proposal.md — Phase 4

Add $name: Type syntax to trait definitions and impls. Extends the associated types pattern to compile-time values.

Blocked by: Section 18.0 (Const Evaluation Termination)

Implementation

18.10 Const Functions in Type Positions (Capability Unification)

Proposal: proposals/approved/capability-unification-generics-proposal.md — Phase 5

Allow $product(S), $len(S) etc. in type positions and where clauses. Most complex phase.

Blocked by: Section 18.9 (Associated Consts)