Standard Library

#Random

Status: standard library specification draft.

This chapter defines std.random, which lib/std writes in ordinary hd over the language tier:

• the host capability trait Random;
• SeededRandom, its deterministic provider;
• Rng, a seeded generator with the draws that scripts need, and rng.

Which provider a command binds is CLI tier (Host Capabilities).

#Random Source

Random draws values from a source of randomness:

pub trait Random:
    fn next_u64(&mut self) -> u64
    fn fill(&mut self, count: usize) -> List[u8]

1. std-random.decl-refstd.random declares the host capability trait Random with the methods above. Code imports it, as in use std.random.Random.
2. std-random.nextnext_u64 returns the next value of the provider's source.
3. std-random.fillfill(count) returns count values of that source, as bytes.
4. std-random.plainBoth methods are plain calls, not bang calls.
5. std-random.mut-ref.reference-valuesBoth take &mut self, so Random is a mutable requirement trait, $.use(Random) is a &mut dyn Random by req.ref.use.reference-values, and a seeded provider may advance its own state.
6. std-random.fill-freestd.random declares pub fn fill(count: usize) -> List[u8] $ Random. It returns fill(count) of the Random provider that covers the call.

use std.random.Random

fn roll() -> u64 $ Random:
    $.use(Random).next_u64() % 6 + 1

Why. A random draw returns a value from the host, as a clock read does, so it needs no driver. A test installs a seeded provider, and replay records each draw at the boundary.

Note. Random.fill and the free fill are the calls for a secret, such as a session token (hex_encode(fill(16))), because the default host provider draws from the system source. An Rng repeats for one seed, so it is never a source of secrets.

Note. A property test's random draws also come from a Random provider, one that std.testing seeds from the test runner (std-testing.runner.random).

#Seeded Random

SeededRandom is the deterministic Random provider. A test supplies it with $.with, and each seed gives one fixed sequence of draws:

use std.random.{Random, SeededRandom}
fn roll() -> u64 $ Random:
    $.use(Random).next_u64() % 6 + 1

tests:
    use std.testing.assert_equal

    it("one seed, one sequence"):
        first := SeededRandom::new(7)
        again := SeededRandom::new(7)
        let rolled: u64 = 0
        $.with(Random=first):
            rolled = roll()
        $.with(Random=again):
            assert_equal(roll(), rolled, reason="the same seed rolls the same")

1. std-random.seeded.decl-refstd.random declares the struct SeededRandom, which implements Random, with private fields. Code imports it, as in use std.random.SeededRandom. Its methods take &mut self, as the trait's do, so a SeededRandom serves as a provider through a reference to it.
2. std-random.seeded.new-refSeededRandom::new(seed: u64) -> *mut SeededRandom returns a provider that seed starts, a new object. A provider installed from that reference, and every copy of it, draw from the one state, so a draw through the provider advances the generator the caller holds.
3. std-random.seeded.same-seedTwo providers that one seed starts return the same values for the same sequence of next_u64 and fill calls.
4. std-random.seeded.no-hostA SeededRandom draws from its own state only. It reads nothing from the host.

Note. These rules fix no generator, so a seed's values may differ between implementations. A test compares draws with each other, not with written numbers. An Rng fixes its generator, as Rng Generator states.

See also: Mutable Providers.

#Rng

Rng is a generator value with the draws that scripts need. A seed starts it, or rng seeds it from the Random provider:

use std.random.{Random, Rng, rng}

fn roll() -> i64 $ Random:
    dice := rng()
    dice.int(1..=6)

fn deal(seed: u64) -> List[string]:
    deck := Rng::new(seed)
    let mut cards: List[string] = ["A", "K", "Q", "J"]
    deck.shuffle(&mut cards)
    cards

1. std-random.rng.decl-structstd.random declares the struct Rng, with private fields, and the methods above. Code imports it, as in use std.random.Rng.
2. std-random.rng.new-refRng::new(seed: u64) -> *mut Rng returns a generator that seed starts, a new object, as SeededRandom::new returns a provider. Every copy of the reference, and every callee given it, draws from that one generator.
3. std-random.rng.from-random-refstd.random declares pub fn rng() -> *mut Rng $ Random. It draws one next_u64 from the Random provider that covers the call, and returns Rng::new of that draw.
4. std-random.rng.plainEvery Rng method is a plain call with the empty requirement row. An Rng reads nothing from the host.
5. std-random.rng.ref-receiversEvery method takes &mut self, since each draw advances the generator.

Why. A script that draws many values pays for one host draw, and a seeded Rng needs no provider at all. Go's math/rand/v2 pairs a seeded generator value with a host-seeded default the same way.

#Rng Generator

An Rng's generator is fixed, so a seed gives the same draws in every implementation:

1. std-random.rng.generatorAn Rng's state is four 32-bit words, and each 32-bit draw is one step of xoshiro128** 1.0, as the reference code below gives.
2. std-random.rng.seedingRng::new folds the seed to the 32-bit z = (seed ^ (seed >> 32)) mod 2^32. Then for each state word in order, z advances by 0x9E3779B9 modulo 2^32, and the word is mix32(z).
3. std-random.rng.mixmix32 is the 32-bit finalizer of MurmurHash3, as the reference code gives.
4. std-random.rng.next-u64next_u64 takes two 32-bit draws. The first is the high half of the result, and the second the low half.

uint32_t mix32(uint32_t z) {
    z = (z ^ (z >> 16)) * 0x85EBCA6B;
    z = (z ^ (z >> 13)) * 0xC2B2AE35;
    return z ^ (z >> 16);
}

uint32_t rotl(uint32_t x, int k) { return (x << k) | (x >> (32 - k)); }

uint32_t next32(uint32_t s[4]) {
    uint32_t result = rotl(s[1] * 5, 7) * 9;
    uint32_t t = s[1] << 9;
    s[2] ^= s[0]; s[3] ^= s[1]; s[1] ^= s[2]; s[0] ^= s[3];
    s[2] ^= t;
    s[3] = rotl(s[3], 11);
    return result;
}

Why. A seeded Rng serves output that must repeat, such as a level that a seed names or a fixture's sample. Its draws therefore cannot depend on the implementation. xoshiro128** needs only 32-bit steps, so no implementation needs a wide multiplication.

Note. lib/std's SeededRandom uses the same generator, but Seeded Random does not require it.

#Integer Ranges

int takes either form of Range, so 0..10 draws from 0 through 9 and 1..=6 from 1 through 6. It is generic over the integer type, so int(0..items.len()) is a usize and int(0..=255) can be a u8:

1. std-random.rng.int.countThe count n of range is end - start for a .. range and end - start + 1 for a ..= range, computed exactly.
2. std-random.rng.int.emptyA range with no integer, where n is 0 or less, panics. Panic: explicit-panic.
3. std-random.rng.int.offsetint returns start + below(n).
4. std-random.rng.int.u64int draws and counts in u64, converting bounds and the result with Integer.to_u64 and Integer.from_u64. It never overflows N, and a negative bound is converted through its magnitude. For an i64 range, a seed draws the same values as the i64-only int did.
5. std-random.rng.belowbelow(n) draws next_u64 values until one, x, is at least 2^64 mod n. It returns x mod n.
6. std-random.rng.below.fullWhen n is 2^64, the whole i64 or u64 range, below(n) is one next_u64 draw.

use std.random.Rng

fn two_rolls(seed: u64) -> List[i64]:
    dice := Rng::new(seed)
    [dice.int(0..10), dice.int(1..=6)]
    # two_rolls(7) is [7, 5]

Why. Rejection keeps the result unbiased. The accepted draws, from 2^64 mod n up, number a multiple of n, so each remainder has the same share. Fewer than two draws are needed on average, as in OpenBSD's arc4random_uniform.

Note. below is not a public method. The rules name it so that the list methods can use it.

#Floats And Booleans

1. std-random.rng.float.bitsfloat is the top 53 bits of one next_u64 draw, times 2^-53. So it is a multiple of 2^-53, and below 1.0.
2. std-random.rng.bool.bitbool is true exactly when the top bit of one next_u64 draw is set.

use std.random.Rng

fn coin_and_fraction(seed: u64) -> (f64, bool):
    gen := Rng::new(seed)
    (gen.float(), gen.bool())
    # coin_and_fraction(7) is (0.23382771772151634, false)

#Lists

1. std-random.rng.choose.indexFor a list that is not empty, choose returns .Some(items[below(len)]).
2. std-random.rng.choose.emptyFor an empty list, choose returns .None and draws nothing.
3. std-random.rng.shuffle.ordershuffle is the Fisher–Yates shuffle from the back. For each i from len - 1 down to 1, it swaps the items at i and at below(i + 1).
4. std-random.rng.shuffle.permutationSo shuffle keeps every item and changes only their order.
5. std-random.rng.shuffle.shortA list of fewer than two items is unchanged, and shuffle draws nothing.
6. std-random.rng.sample.ordersample shuffles a copy of items from the front, for count steps. Step i, from 0, swaps the copy's items at i and at i + below(len - i).
7. std-random.rng.sample.resultsample returns the copy's first count items.
8. std-random.rng.sample.inputitems itself is unchanged.
9. std-random.rng.sample.countA count above the list's length panics. Panic: explicit-panic.

use std.random.Rng

fn pick_three(seed: u64) -> List[i64]:
    gen := Rng::new(seed)
    gen.sample([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 3)
    # pick_three(7) is [8, 3, 4]

fn one_letter(seed: u64) -> string?:
    gen := Rng::new(seed)
    gen.choose(["a", "b", "c"])
    # one_letter(7) is .Some("c")

Why. A count past the length is a bug in the caller, so it panics, as chunks(0) does. Python's random.sample rejects it too.

See also: Range Expressions.