std.slice

std.slice provides ordering operations for the built-in owning slice ^[T]. Growth and length editing live on ^[T] itself as push, reserve, clear, insert, pop, and remove; shared clone duplicates a slice into a new owner. OutputSpan<T> is the sole append-only initialization session for the unused tail of an owning slice. This module adds one stable sort and one lower-bound binary_search. Owning construction is language syntax: ^[...], never an arity-specific standard-library helper. Views [T] and &[T] have no operation that changes length or capacity; &[T] still permits ordinary in-place element mutation.

Consume every element with for item in <-xs, which selects the owning slice's iter(^self) and leaves xs moved. Mutate elements in place with the canonical lending loop:

for item: &T in _ in &xs {
	item = replacement;
}

&xs selects the slice's concrete iter(&self) cursor and item: &T in _ explicitly names the per-iteration local loan. There is no iter_mut alias.

Quick Example

import std.slice;
import std.ordering;
import std.ordering.{ Ordering };
import std.mem.{ AllocError };

fn main() throws(AllocError) {
	let ascending = [] (left: i32, right: i32) -> Ordering {
		return ordering.compare_i32(left, right);
	};

	let values: ^[i32] = try ^[5, 2, 8, 1, 2];
	let sorted = slice.sort(<-values, &ascending);

	assert sorted[0] == 1;
	assert sorted[1] == 2;
	assert sorted[2] == 2;
	assert sorted[3] == 5;
	assert sorted[4] == 8;

	match slice.binary_search(sorted, 4, &ascending) {
		.Found(index) => { assert false; },
		.Insert(index) => { assert index == 3 as usize; },
	}
}

The comparator is always explicit. Zynx does not infer an order from the element type, operators, an interface implementation, or a default overload.

Owning Slice Growth And Editing

RFC 0052 defines one consuming path for changing the length or capacity of an owning slice:

// RFC 0052 target; implementation pending.
fn push(^self, value: ^T) throws(AllocError) -> ^[T];
fn reserve(^self, total: usize) throws(AllocError) -> ^[T];
fn clear(^self) -> ^[T];
fn insert(^self, index: usize, value: ^T) throws(AllocError) -> ^[T];
fn pop(^self) -> ^(^[T], ^T?);
fn remove(^self, index: usize) -> ^(^[T], ^T);
fn clone(self) throws(AllocError) -> ^[T];

A named consuming receiver is always written with an explicit take. The successor owner is then installed explicitly:

// RFC 0052 target; implementation pending.
var values: ^[Item] = ^[];

values = try (<-values).reserve(128);

let first = try make_item();
values = try (<-values).push(<-first);

let other = try make_item();
values = try (<-values).insert(0, <-other);

There is no slice append: adding one element is push. A future bulk move operation would need its own contract for partial progress and overlapping sources instead of overloading this primitive. RFC 0064 also excludes extend, delete, erase, and take aliases: insert selects a position, pop selects the sole obvious end, and remove selects an exact index.

Only ^[T] exposes readonly logical capacity; [T] and &[T] project only pointer and length. reserve(total) requests total capacity, not additional capacity. An already satisfied request is an exact no-op. push and insert reuse sufficient capacity without calling the allocator and otherwise perform at most one allocation growth. The rounding strategy is private, but a lineage of successful push operations is amortized O(1) per push and O(N) in aggregate relocation work. Private rounding overflow falls back to the exact representable minimum; an impossible layout reports AllocError.OutOfMemory.

clear is infallible. It drops initialized elements in reverse index order, sets the logical length to zero, and retains the exact pointer and capacity. Replacing the owner with ^[] is the explicit clear-and-release operation. pop likewise retains storage and returns the exact input owner with null when it is already empty:

// RFC 0052 target; implementation pending.
let (rest, value) = (<-values).pop();
values = <-rest;

if value != null {
	consume(<-value);
}

remove(index) returns the removed owner without a nullable branch:

// RFC 0052 target; implementation pending.
let (rest, removed) = (<-values).remove(index);
values = <-rest;
consume(<-removed);

insert accepts index <= length; a larger index traps before pointer arithmetic or element movement. remove traps when index >= length. These are defined bounds traps, not checked errors. pop on an empty owner does not trap.

A checked push, insert, or reserve failure drops every argument already taken by the call exactly once. For values = try (<-values).push(<-item), both values and item remain moved if allocation fails; no rollback owner or hidden recovery wrapper is synthesized. Prepare a fallible element before taking the slice.

Zero-sized T retains logical length and capacity but needs no physical allocation or pointer arithmetic. Growth can still report AllocError.OutOfMemory when the logical length is not representable, and clear still runs exactly one destructor per initialized element. Its signature and checked effect therefore do not depend on layout.

clone(self) shared-borrows the source and creates an independent owner. It is available when T is Copy, or when non-Copy T implements Clone. Elements are copied or cloned in increasing order; failure drops the completed prefix in reverse order and leaves the source unchanged.

Append-Only Output Initialization

RFC 0054 adds one initialization-aware path for building a contiguous suffix without first pretending that unused capacity contains live T values:

OutputSpan<T> is exported from std.slice; signatures below show it after an ordinary selective import.

// RFC 0054 target; implementation pending.
export struct OutputSpan<T>;

fn output(^self, additional: usize) throws(AllocError) -> ^OutputSpan<T>;
fn OutputSpan.push(&self, value: ^T);
fn OutputSpan.commit(^self) -> ^[T];
fn OutputSpan.cancel(^self) -> ^[T];

output(additional) consumes the original ^[T], reuses sufficient spare capacity or grows at most once, and returns a session that owns the complete allocation. additional bounds only the new suffix; zero needs no allocation. If required growth returns AllocError, the taken slice owner is dropped and its source binding remains moved; the call does not return a recovery owner. During the session, [0, base_length) contains the original live elements, [base_length, base_length + length) contains the newly initialized prefix, and the rest is raw storage. OutputSpan.length, capacity, and remaining are readonly and describe only that new suffix: written elements, its admitted limit, and the difference.

OutputSpan<T> is a sealed compiler/SDK-trusted affine nominal: it has no public initializer or fields and is neither Copy nor Clone. It is Send exactly when its owner and T are Send, and is never Sync. commit and cancel are trusted whole-owner transitions that disarm session cleanup before returning ^[T]; they do not create a general partial-move exception.

// RFC 0054 target; implementation pending.
var values: ^[Item] = ^[];
var output = try (<-values).output(128);

let first = try make_item();
(&output).push(<-first);

let second = try make_item();
(&output).push(<-second);

values = (<-output).commit();

push consumes its value and initializes exactly the next slot. Pushing when remaining == 0 is a defined bounds trap, not a checked capacity error. Producers that need recoverable bounded output inspect remaining and return their own domain error before pushing. There is no random-slot initialization, remove, clear, truncate, resize, or implicit growth during a session.

commit() publishes the new prefix by returning ^[T] with logical length base_length + length. cancel() reverse-drops only the new prefix and returns an owner at exactly base_length; storage grown when the session began may remain reserved. Neither operation can fail.

Dropping an unfinished OutputSpan<T> is deliberately different from cancel: it destroys every live value in the session, including the original prefix, and releases the owned allocation. There is no hidden commit, rollback, or recovery owner. Code that wants the original collection back must call cancel() explicitly.

Only OutputSpan<u8> has the raw foreign-output boundary:

// RFC 0054 target; implementation pending.
fn OutputSpan.spare_ptr(&self) -> *mut u8;
unsafe fn OutputSpan.advance(&self, count: usize);

spare_ptr() points at the next uninitialized byte. advance(count) checks count <= remaining, then trusts the caller's proof that the foreign operation initialized exactly that contiguous prefix. It cannot skip holes. A generic raw *mut T output escape is not provided because arbitrary T also carries validity, destruction, and zero-sized-layout obligations. Audited SDK implementations may use a private trusted generic initialization primitive for foreign producers such as UTF-16, but that primitive is not part of public OutputSpan<T>.

Public Surface

Conceptually, the complete ordering surface is:

export enum BinarySearchResult: Copy {
	Found(index: usize),
	Insert(index: usize),
}

export fn sort<
	T,
	C: (&self, T, T) -> Ordering,
>(values: ^[T], compare: &C) -> ^[T];

export fn binary_search<
	T,
	C: (&self, T, T) -> Ordering,
>(values: [T], target: T, compare: &C) -> BinarySearchResult;

C remains the concrete function-item or closure-environment type. The operation borrows that named value with explicit exclusive access; it neither erases nor owns the callable and performs no callback-selected allocation.

There are no natural-order overloads, sort_by, binary_search_by, raw pointer callbacks, Comparable<T>, or implicit order selection.

Comparator Contract

The comparator returns Ordering.Less, Ordering.Equal, or Ordering.Greater. Equal means equivalence under this chosen order; it does not imply the language's == operation and does not require every field to be equal.

A valid comparator obeys one coherent strict weak order:

• compare(a, a) is Equal;
• swapping the operands reverses Less and Greater and preserves Equal;
• Less and Greater are transitive;
• comparator-equivalence is transitive; and
• the relation remains unchanged for the complete operation.

The number and order of comparator calls are unspecified. A comparator may retain ordinary explicit state, but a caller cannot use that state to change the relation while sorting or searching. The comparator cannot throw.

Violating these laws, or searching input not sorted by the same relation, makes the returned ordering or search result unspecified. It does not permit out-of-bounds access, double drop, ownership corruption, or undefined behavior inside safe code.

Stable In-Place Sort

sort consumes the exact slice owner and returns that same owner, allocation, capacity, length, and element multiset. It may relocate elements within the buffer but never clones or implicitly drops them. Every input element remains armed in exactly one output slot, including for move-owning and zero-sized element types.

The operation is stable: elements for which the comparator returns Equal retain their input order.

import std.slice;
import std.ordering;
import std.ordering.{ Ordering };
import std.mem.{ AllocError };

struct Item: Copy {
	let key: i32,
	let arrival: i32,
}

fn main() throws(AllocError) {
	let by_key = [] (left: Item, right: Item) -> Ordering {
		return ordering.compare_i32(left.key, right.key);
	};

	let items: ^[Item] = try ^[
		Item { key: 1, arrival: 10 },
		Item { key: 1, arrival: 20 },
	];
	let sorted = slice.sort(<-items, &by_key);

	assert sorted[0].arrival == 10;
	assert sorted[1].arrival == 20;
}

Sorting itself performs no heap allocation and has no checked error; allocation explicitly performed by user comparator code is outside that guarantee. It uses at most O(n log n) comparator calls in the worst case and may use at most O(log n) machine words of control stack. The bound is deliberately about comparator calls, not the unspecified number of element relocations or total running time. The particular stable in-place algorithm and rotation strategy remain implementation details.

Lower-Bound Binary Search

binary_search borrows the slice and target and returns:

• .Found(index) when index is the first element comparator-equivalent to target; or
• .Insert(index) when no equivalent element exists and index is the first position at which target can be inserted while preserving the order.

Both variants therefore expose the lower-bound index. It lies between zero and values.length, inclusive; .Insert(values.length) is a valid result. Search performs no allocation, mutation, element move, or checked error and uses O(log n) comparator calls.

let result = slice.binary_search(sorted, target, &compare);

match result {
	.Found(index) => {
		use(sorted[index]);
	},
	.Insert(index) => {
		insert_at(index);
	},
}

Returning the first equivalent element makes duplicate handling deterministic; returning the insertion point preserves information the search already computed instead of collapsing a miss to null.

Floating-Point Order

Floating-point sorting is never selected implicitly. A caller that wants a complete IEEE 754 order chooses ordering.compare_total_f32 or ordering.compare_total_f64 explicitly:

let total = [] (left: f64, right: f64) -> Ordering {
	return ordering.compare_total_f64(left, right);
};

let sorted = slice.sort(<-values, &total);

That target-independent bit-key order distinguishes negative and positive zero, orders NaN sign/class/payload deterministically, and returns Equal only for identical complete bit patterns. See std.ordering.

Owning Literal And Element Model

Plain [...] is always a fixed inline array and never allocates. ^[...] is the sole dynamic owning-slice literal. Every form except exact ^[] is allocation-capable and therefore has checked AllocError; the use site must write try or catch:

let inline = [1, 2];
let owned: ^[T] = try ^[<-a, <-b];
let empty: ^[T] = ^[];

^[] is the canonical empty owner with length == capacity == 0, performs no allocation, and is infallible. Its pointer bits are a private, suitably aligned, non-dereferenceable empty representation rather than a promised null value. For an allocation-capable literal, layout preflight and any required allocation complete before an element expression is evaluated or moved. Nonzero-sized storage performs one exact-capacity allocation; a zero-sized layout may omit the physical allocator call. Elements then initialize from left to right. Checked failure while initializing element k drops the initialized prefix in reverse order and frees the buffer; the untouched suffix is never evaluated. Success produces length == capacity == N. The literal copies no move-only element and is sound for drop-owning element types.

Repeat form ^[value; N] requires T: Copy; its expression is evaluated exactly once after preflight. Even when N == 0, that value is evaluated and then ordinarily dropped because no element receives it. Every repeat, range, and expansion owning form is statically fallible even when its cardinality is zero or T is zero-sized; only the exact literal ^[] is infallible. std.slice has no of_one, of_two, variadic of, or other constructor alias.

Fixed arrays are not dynamic slice clone receivers. A Copy [T; N] uses ordinary copy; a non-Copy fixed array whose elements implement Clone clones to the same inline type. Neither operation creates ^[T]. An allocating fixed-array-to-slice conversion would require its own explicitly fallible API.

xs.clone() is the shared slice method described above: it copies Copy elements and delegates to Clone for non-Copy elements. Sorting never calls either path.

API Reference

Types

Type	Kind	Description
BinarySearchResult	enum: Copy	.Found(index) for the first comparator-equivalent element or .Insert(index) for the lower-bound insertion point.
OutputSpan<T>	opaque affine struct	Owns one ^[T] allocation while initializing a bounded contiguous suffix.

Functions

Function	Signature	Returns	Description
sort	sort<T, C: (&self, T, T) -> Ordering>(values: ^[T], compare: &C) -> ^[T]	^[T]	Stable in-place sort under the explicit comparator; returns the exact input owner.
binary_search	binary_search<T, C: (&self, T, T) -> Ordering>(values: [T], target: T, compare: &C) -> BinarySearchResult	BinarySearchResult	Returns the deterministic lower-bound hit or insertion point under the explicit comparator.

Output Methods And Fields

Member	Signature or type	Description
^[T].output	output(^self, additional: usize) throws(AllocError) -> ^OutputSpan<T>	Takes the owner and admits at most additional newly initialized elements, reusing capacity or growing once.
OutputSpan.push	push(&self, value: ^T)	Initializes the next element; traps when the session is full.
OutputSpan.commit	commit(^self) -> ^[T]	Publishes the initialized suffix and returns its owner.
OutputSpan.cancel	cancel(^self) -> ^[T]	Reverse-drops the new suffix and returns the old logical contents, retaining any grown storage.
OutputSpan.length	usize	Readonly count of newly initialized elements.
OutputSpan.capacity	usize	Readonly maximum new-element count admitted by this session.
OutputSpan.remaining	usize	Readonly capacity - length.
OutputSpan<u8>.spare_ptr	spare_ptr(&self) -> *mut u8	Returns the next uninitialized byte pointer for foreign output.
OutputSpan<u8>.advance	unsafe advance(&self, count: usize)	Trusts that the next count bytes were initialized and advances the prefix; traps beyond remaining.

Status

RFC 0047 defines the ordering target, RFC 0048 defines owning construction, RFC 0052 defines the consuming owning-slice method surface, RFC 0054 defines append-only output initialization, and RFC 0064 makes these mutation spellings exact rather than aliases. The checked-in implementation remains transitional until the old slice append and Taken result, as well as the natural overloads, _by functions, raw callbacks, heap scratch allocation, nullable arbitrary-hit result, Comparable<T> bridge, of_one/of_two, and contextual owning [...] lowering are removed and reserve/clear/output plus OutputSpan<T> are implemented. For the full exported surface, see Standard Library Inventory.