/// Randomness, as an effect (ADR 0036). /// /// random.int(6) + 1 // a die /// random.token(16) // 32 hex characters, for a session /// random.shuffle([1, 2, 3]) /// /// Every function here reads random bytes through the `random` effect's one /// operation. The runtime handles it around `main`, each test and each /// actor, with the kernel's generator (`getrandom`/`/dev/urandom`): good /// for tokens and salts. A test can choose the bytes instead: /// /// random.with_seed(7, fn() { random.int(100) }) // always the same /// /// A handler installed with `with_seed` (or `handle`) does not follow /// `process.spawn`: a new actor always gets the system's randomness. import std/array.{type Array} import std/bytes as raw import std/float import std/int as bits import std/list import std/prng import std/ref import std/string import std/u64 /// Random bytes. pub effect random { /// `count` random bytes; panics if `count` is negative. fn bytes :: count: Int -> Bytes } /// A uniformly random Int in `0..below` (`below` excluded); panics unless /// `below` is positive. Any size: `random.int(bits.shift_left(1, 128))`. pub fn int :: below: Int -> Int / { if below < 1 { panic "random.int: the bound must be positive, got {below}" } let width = bits.bit_length (below - 1) below_by_rejection below width } /// Rejection sampling: draw `width` bits until they are below `below`, so /// every value is equally likely (fewer than 2 draws on average). fn below_by_rejection :: below: Int width: Int -> Int / { if width == 0 { 0 } else { let v = bits.low_bits (big_endian (bytes ((width + 7) / 8))) width if v < below { v } else { below_by_rejection below width } } } /// A uniformly random Int in `low..=high` (both included); panics if /// `high < low`. pub fn range :: low: Int high: Int -> Int / { if high < low { panic "random.range: {high} is below {low}" } low + int (high - low + 1) } /// A uniformly random Float in `[0, 1)`, from 53 random bits. pub fn float :: -> Float / { let v = bits.shift_right (big_endian (bytes 7)) 3 float.from_int v / 9007199254740992.0 } /// `xs` in a random order (Fisher–Yates: every order equally likely). pub fn shuffle :: xs: List -> List / { array.to_list (shuffle_from (array.from_list xs) (list.length xs - 1)) } fn shuffle_from :: a: Array i: Int -> Array / { if i < 1 { a } else { let j = int (i + 1) match (array.get a i, array.get a j) { (Some(x), Some(y)) -> shuffle_from (array.set (array.set a i y) j x) (i - 1) , _ -> a } } } /// A random element of `xs`; `None` if it is empty. pub fn choice :: xs: List -> Option / { match xs { [] -> None, _ -> array.get (array.from_list xs) (int (list.length xs)) } } /// `count` random bytes as lowercase hexadecimal (`2 * count` characters), /// for tokens and salts. pub fn token :: count: Int -> String / { let digits = raw.to_list (bytes count) |> list.map hex_byte string.concat digits } fn hex_byte :: b: Int -> String { "{hex_digit (b / 16)}{hex_digit (b % 16)}" } fn hex_digit :: d: Int -> String { match d { 10 -> "a" , 11 -> "b" , 12 -> "c" , 13 -> "d" , 14 -> "e" , 15 -> "f" , _ -> show d } } /// The bytes as an unsigned big-endian integer. fn big_endian :: b: Bytes -> Int { list.fold (raw.to_list b) 0 fn acc x { bits.or (bits.shift_left acc 8) x } } /// Run `action` with random bytes from a SplitMix64 generator seeded with /// `seed` (`std/prng`): the same seed gives the same values, on every /// backend and every run. Each `bytes(n)` draws `ceil(n / 8)` outputs and /// takes their bytes, low first. **Not for secrets**, only for tests and /// simulations. pub fn with_seed :: seed: Int action: fn() -> a / -> a / { region { let state = ref.new (prng.seeded seed) handle { action () } with { bytes count -> { if count < 0 { panic "random.bytes: negative count {count}" } let (out, next) = draw (ref.get state) count (raw.builder ()) ref.set state next out } } } } /// `count` bytes from `g`, appended to `acc`; the generator after them. fn draw :: g: prng.Prng count: Int acc: raw.Builder -> (Bytes, prng.Prng) { if count <= 0 { (raw.build acc, g) } else { let (x, next) = prng.next g draw next (count - 8) (append_low acc x if count < 8 { count } else { 8 }) } } /// The `n` low bytes of `x`, lowest first. fn append_low :: acc: raw.Builder x: u64.U64 n: Int -> raw.Builder { if n == 0 { acc } else { let byte = u64.to_int (u64.and x (u64.from_int 255)) append_low (raw.append_byte acc byte) (u64.shift_right x 8) (n - 1) } }