Module std::buf

Buf<T>, the growable buffer (Rust's Vec), and its algorithms: sort, search, retain, dedup. Growing asks for Alloc and destroying elements for Free; the index forms v[i], v[lo..hi], v.remove(i) require their index fact or use the _checked methods (Panic).

Source: std/buf.weir; committed interface: std/buf.iface. Index

• struct Buf: A growable buffer of T in region r: len initialised elements in storage for cap. It owns its elements: dropping it destroys them and frees the storage (Free), and a Buf of linear elements is itself linear, consumed by Buf::drain.
• struct BufIter: The iterator Buf::iter returns: copies of the elements, borrowing the buffer.

struct Buf

pub struct Buf<T: linear>: destruct unsafe portable(T) {
    pub len: usize,
    pub cap: usize,
    /* private fields */
} drop with Free in home

A growable buffer of T in region r: len initialised elements in storage for cap. It owns its elements: dropping it destroys them and frees the storage (Free), and a Buf of linear elements is itself linear, consumed by Buf::drain.

push grows the storage by doubling (amortised O(1)), under Alloc. Index with v[i] where i < v.len is known, or with the _checked methods, which raise Panic otherwise.

Fields:

• pub len: usize: The number of initialised elements, v.len(); writing it is unsafe (R-UnsafeScope).
• pub cap: usize: How many elements the storage holds, v.capacity(); v.len < v.cap is what push_within_capacity requires. Writing it is unsafe (R-UnsafeScope).

impl<T: linear, r> Buf<T> in r

method with_capacity

pub fn with_capacity(cap: usize) -> Buf<T> in r with Alloc in r

An empty buffer with storage for cap elements, allocated now (Alloc).

Committed interface (std/buf.iface):

bound Alloc: Alloc[r] any
aborts: Alloc.alloc

method new

pub fn new() -> Buf<T> in r with Alloc in r

An empty buffer with no capacity; the first push grows it.

Committed interface (std/buf.iface):

bound Alloc: Alloc[r] any
aborts: Alloc.alloc

method capacity

pub fn capacity(&self) -> usize

How many elements the storage holds before a push grows it.

Committed interface (std/buf.iface): the signature alone.

method reserve

pub fn reserve(&mut self, extra: usize) with Alloc in r

Grows the storage to hold at least extra more elements (at least doubling). A failing allocation leaves the buffer as it was, so it serves linear elements too.

Committed interface (std/buf.iface):

bound Alloc: Alloc[r] any
aborts: Alloc.alloc
writes through self: {cap, data} and its shape

method push_within_capacity

pub fn push_within_capacity(&mut self, x: T) requires self.len < self.cap

Appends x without allocating; the caller must establish self.len < self.cap, e.g. after Buf::reserve.

Committed interface (std/buf.iface):

writes through self: {len} and its shape
stores T in regions r

method try_push

pub fn try_push(&mut self, x: T) -> Result<Unit, T>

Appends x into a free slot, or hands it back as Err(x) when the storage is full; never allocates (Rust's push_within_capacity).

Committed interface (std/buf.iface):

writes through self: {len} and its shape
stores T in regions r

method drain

pub fn drain(self, each: fn(T) env {S}) with Free in r

Consumes the buffer, handing each element to each (last first), then frees its storage: the way to dispose of a Buf of linear elements.

Committed interface (std/buf.iface):

bound Free: Free[r] any
may diverge
callback each: envelope {S}; pinned: always; holds each
writes regions type T

method pop

pub fn pop(&mut self) -> Option<T>

Removes and returns the last element, or None when the buffer is empty.

Committed interface (std/buf.iface):

writes through self: {len} and its shape

method get_ref

pub fn get_ref(&self, i: usize) -> &{self[i]} T requires i < self.len

A shared reference to element i (what &v[i] uses); i must be below self.len.

Committed interface (std/buf.iface): the signature alone.

method get_ref_checked

pub fn get_ref_checked(&self, i: usize) -> &{self[i]} T with Panic {panic: raise}

A shared reference to element i, or a panic when i is out of bounds.

Committed interface (std/buf.iface):

bound Panic: Panic any
aborts: Panic.panic
scheduling point: Panic not quiet

method get_mut

pub fn get_mut(&mut self, i: usize) -> &{self[i]} mut T requires i < self.len

A mutable reference to element i (what &mut v[i] and v[i] = x use); i must be below self.len.

Committed interface (std/buf.iface): the signature alone.

method get_mut_checked

pub fn get_mut_checked(&mut self, i: usize) -> &{self[i]} mut T with Panic {panic: raise}

A mutable reference to element i, or a panic when i is out of bounds.

Committed interface (std/buf.iface):

bound Panic: Panic any
aborts: Panic.panic
scheduling point: Panic not quiet

method replace_at

pub fn replace_at(&mut self, i: usize, x: T) -> T requires i < self.len

Writes x into slot i and returns the old element, so it works for any T; i must be below self.len.

Committed interface (std/buf.iface):

stores T in regions r

method swap

pub fn swap(&mut self, i: usize, j: usize) requires i < self.len, j < self.len

Exchanges elements i and j (equal indices are fine); both must be below self.len.

Committed interface (std/buf.iface):

stores T in regions r

method swap_checked

pub fn swap_checked(&mut self, i: usize, j: usize) with Panic {panic: raise}

Buf::swap, or a panic when i or j is out of bounds.

Committed interface (std/buf.iface):

bound Panic: Panic any
aborts: Panic.panic
scheduling point: Panic not quiet
stores T in regions r

method remove

pub fn remove(&mut self, i: usize) -> T requires i < self.len

Removes and returns element i, shifting the later ones down (O(n), order kept); i must be below self.len.

Committed interface (std/buf.iface):

writes through self: {len} and its shape
stores T in regions r

method remove_checked

pub fn remove_checked(&mut self, i: usize) -> T with Panic {panic: raise}

Buf::remove, or a panic when i is out of bounds.

Committed interface (std/buf.iface):

bound Panic: Panic any
aborts: Panic.panic
scheduling point: Panic not quiet
writes through self: {len} and its shape
stores T in regions r

method swap_remove

pub fn swap_remove(&mut self, i: usize) -> T requires i < self.len

Removes and returns element i, moving the last element into its slot (O(1), order lost); i must be below self.len.

Committed interface (std/buf.iface):

writes through self: {len} and its shape
stores T in regions r

method swap_remove_checked

pub fn swap_remove_checked(&mut self, i: usize) -> T with Panic {panic: raise}

Buf::swap_remove, or a panic when i is out of bounds.

Committed interface (std/buf.iface):

bound Panic: Panic any
aborts: Panic.panic
scheduling point: Panic not quiet
writes through self: {len} and its shape
stores T in regions r

method slice

pub fn slice(
    &self,
    lo: usize,
    hi: usize,
) -> &{self[lo..hi]} Slice<T> in r requires lo <= hi, hi <= self.len

A view of elements lo..hi (what &v[lo..hi] uses), borrowing self; requires lo <= hi and hi <= self.len. See std::slice for what a view offers.

Committed interface (std/buf.iface): the signature alone.

method slice_checked

pub fn slice_checked(&self, lo: usize, hi: usize) -> &{self[lo..hi]} Slice<T> in r with
    Panic {panic: raise},

The view lo..hi, or a panic when the range is out of bounds.

Committed interface (std/buf.iface):

bound Panic: Panic any
aborts: Panic.panic
scheduling point: Panic not quiet

method slice_mut

pub fn slice_mut(
    &mut self,
    lo: usize,
    hi: usize,
) -> &{self[lo..hi]} mut Slice<T> in r requires lo <= hi, hi <= self.len

A mutable view of elements lo..hi; requires lo <= hi and hi <= self.len.

Committed interface (std/buf.iface): the signature alone.

method slice_mut_checked

pub fn slice_mut_checked(
    &mut self,
    lo: usize,
    hi: usize,
) -> &{self[lo..hi]} mut Slice<T> in r with Panic {panic: raise}

The mutable view lo..hi, or a panic when the range is out of bounds.

Committed interface (std/buf.iface):

bound Panic: Panic any
aborts: Panic.panic
scheduling point: Panic not quiet

impl<T: copy, r> Buf<T> in r

method get

pub fn get(&self, i: usize) -> T requires i < self.len

A copy of element i (what v[i] uses for copy elements); i must be below self.len.

Committed interface (std/buf.iface): the signature alone.

method get_checked

pub fn get_checked(&self, i: usize) -> T with Panic {panic: raise}

A copy of element i, or a panic when i is out of bounds.

Committed interface (std/buf.iface):

bound Panic: Panic any
aborts: Panic.panic
scheduling point: Panic not quiet

impl<T: copy> Buf<T>

method iter

pub fn iter(&self) -> BufIter<T>

An iterator over copies of the elements, first to last. It borrows the buffer while it lives, so the buffer cannot be changed until the last pull.

Committed interface (std/buf.iface): the signature alone.

impl<T, r> Buf<T> in r

method replace_at_checked

pub fn replace_at_checked(&mut self, i: usize, x: T) -> T with Panic {panic: terminal}

Buf::replace_at, or a panic when i is out of bounds. The Panic clause is terminal (the handler cannot resume), since x would otherwise be lost.

Committed interface (std/buf.iface):

bound Panic: Panic { panic: terminal } any
scheduling point: Panic not quiet
stores T in regions r

impl<T: drops {Alloc}, r> Buf<T> in r

method push

pub fn push(&mut self, x: T) with Alloc in r

Appends x, doubling the storage when full (amortised O(1)). A failing allocation leaves the buffer as it was and drops x.

Committed interface (std/buf.iface):

bound Alloc: Alloc[r] any
aborts: Alloc.alloc
writes through self: {cap, data, len} and its shape
destroys values of T

method insert

pub fn insert(&mut self, i: usize, x: T) with Alloc in r requires i <= self.len

Puts x at i, moving the elements from i on up one slot (O(n)); i must be at most self.len. A failing allocation leaves the buffer as it was and drops x.

Committed interface (std/buf.iface):

bound Alloc: Alloc[r] any
aborts: Alloc.alloc
writes through self: {cap, data, len} and its shape
destroys values of T

method insert_checked

pub fn insert_checked(&mut self, i: usize, x: T) with Alloc in r, Panic {panic: raise}

Buf::insert, or a panic when i > self.len (x is dropped first).

Committed interface (std/buf.iface):

bound Alloc: Alloc[r] any
bound Panic: Panic any
aborts: Alloc.alloc, Panic.panic
scheduling point: Panic not quiet
writes through self: {cap, data, len} and its shape
destroys values of T

impl<T: drops {Free}, r> Buf<T> in r

method truncate

pub fn truncate(&mut self, n: usize) with Free in r

Destroys the elements from n on, last first, keeping the storage; an n at or past len changes nothing.

Committed interface (std/buf.iface):

bound Free: Free[r] any
writes through self: {len} and its shape
destroys values of T

method clear

pub fn clear(&mut self) with Free in r

Destroys every element, keeping the storage for reuse.

Committed interface (std/buf.iface):

bound Free: Free[r] any
writes through self: {len} and its shape
destroys values of T

impl<T> Buf<T>

method position

pub fn position(&self, p: fn(&T) -> Bool) -> Option<usize>

The index of the first element p accepts, or None.

Committed interface (std/buf.iface):

enters the backing of self
callback p: envelope {A, S}; pinned: always; holds self, p
writes regions type T

method reverse

pub fn reverse(&mut self)

Reverses the order of the elements in place.

Committed interface (std/buf.iface):

stores T in regions _

method sort_by

pub fn sort_by(&mut self, less: fn(&T, &T) -> Bool)

Sorts in place by less, stably (equal elements keep their order): a merge sort that merges in place, so it allocates nothing. O(n log n) calls of less, O(n log² n) moves.

Committed interface (std/buf.iface):

enters the backing of self
stores T in regions _
callback less: envelope {A, S}; pinned: always; holds self, less
writes regions type T

impl<T: Eq> Buf<T>

method contains

pub fn contains(&self, x: &T) -> Bool

Whether some element equals x; a linear scan.

Committed interface (std/buf.iface):

bound Eq: Eq<T> any row {Diverge}
scheduling point: Eq not quiet
enters the backing of self, x
writes regions type T
loan of Eq across the backing of self
loan of Eq across the backing of x

impl<T: Ord> Buf<T>

method sort

pub fn sort(&mut self)

Sorts in place by Ord, stably: Buf::sort_by with a < b from cmp, so O(n log n) comparisons, O(n log² n) swaps and no allocation.

Committed interface (std/buf.iface):

bound Ord: Ord<T> any row {Diverge}
scheduling point: Ord not quiet
enters the backing of self
stores T in regions _
writes regions type T

method binary_search

pub fn binary_search(&self, x: &T) -> Result<usize, usize>

On a sorted buffer: Ok with an index holding x, else Err with the index where x would go to keep it sorted. O(log n).

Committed interface (std/buf.iface):

bound Ord: Ord<T> any row {Diverge}
scheduling point: Ord not quiet
enters the backing of self, x
writes regions type T
loan of Ord across the backing of self
loan of Ord across the backing of x

impl<T: drops {Free}> Buf<T>

method retain

pub fn retain(&mut self, keep: fn(&T) -> Bool) with Free

Keeps the elements keep accepts, in order, and destroys the others (Free).

Committed interface (std/buf.iface):

bound Free: Free any
writes through self: {len} and its shape
destroys values of T
callback keep: envelope {A, S}; pinned: always; holds self, keep
writes regions type T

impl<T: Eq + drops {Free}> Buf<T>

method dedup

pub fn dedup(&mut self) with Free

Removes consecutive equal elements, keeping the first of each run; sort first to remove all duplicates.

Committed interface (std/buf.iface):

bound Free: Free any
bound Eq: Eq<T> any row {Diverge}
scheduling point: Eq not quiet
writes through self: {len} and its shape
destroys values of T
writes regions type T
loan of Eq across the backing of self

impl<T: copy> Buf<T>

method extend_from_slice

pub fn extend_from_slice(&mut self, s: &Slice<T>) with Alloc

Appends a copy of each element of s, reserving room for all of them first: one copy of the slots, no push per element.

Committed interface (std/buf.iface):

bound Alloc: Alloc any
aborts: Alloc.alloc
writes through self: {cap, data, len} and its shape
stores T in regions _

impl<r> Buf<u8> in r

method as_bytes

pub fn as_bytes(&self) -> &[u8]

Its bytes as a borrowed &[u8], so a byte buffer goes wherever &[u8] is taken (a path, std::bytes). The view holds a loan of self: no push while it lives.

Committed interface (std/buf.iface): the signature alone.

method as_bytes_mut

pub fn as_bytes_mut(&mut self) -> &mut [u8]

Its bytes as a borrowed &mut [u8], what std::fs::Fs::read_at fills and the in-place std::bytes functions change. The view holds a loan of self.

Committed interface (std/buf.iface): the signature alone.

method extend_from_bytes

pub fn extend_from_bytes(&mut self, b: &[u8]) with Alloc in r

Appends the bytes of b, reserving room for all of them first: one copy, no push per byte (Rust's extend_from_slice of a &[u8]; Buf::extend_from_slice takes a &Slice<u8>).

Committed interface (std/buf.iface):

bound Alloc: Alloc[r] any
aborts: Alloc.alloc
writes through self: {cap, data, len} and its shape

method extend_from_str

pub fn extend_from_str(&mut self, s: Str) with Alloc in r

Appends the bytes of the literal s, as Buf::extend_from_bytes does.

Committed interface (std/buf.iface):

bound Alloc: Alloc[r] any
aborts: Alloc.alloc
writes through self: {cap, data, len} and its shape

struct BufIter

pub struct BufIter<T>: forget {
    /* private fields */
}

The iterator Buf::iter returns: copies of the elements, borrowing the buffer.

Implementations:

• impl<T: copy> Iterator for BufIter<T>