Cairn.Fuzz.Rng
lean/Cairn/Fuzz/Rng.lean
A seeded PRNG and generators
SplitMix64 (Steele, Lea and Flood, "Fast splittable pseudorandom number generators", 2014): a 64-bit state advanced by a constant, then mixed. Small, fast, good enough for test generation, and pure, so a seed replays a run exactly. Core only: no Plausible.
A module, so apps can write custom generators (Cairn.Fuzz.Custom) without linking Lean.
Imports Cairn.Input
Structures 4
Rng : Type
state : UInt64Transition (S : Type) : Type
One step the fuzzer took, for Custom.relations: the state before, the message the host
sent if the step was the host's (none for a person's operation), the state after, and the
effects the step put on the frame.
Server (S : Type) : Type 1
A server for the fuzz host to answer requests from (docs/fuzz.md, "A server"): a world W
that persists across the sequence, changed by the requests that reach it and by itself, and
checked against the app's state.
The host still schedules every reply (late, out of order, duplicated at the server, failed), and adds two faults that differ in what happened to the world:
- failed before: the request never reached the server, so the world is unchanged, and the
app hears
fault; - lost after: the server handled the request (the world changed), but its reply was lost,
and the app hears
fault.
The app can't tell them apart; a claim stated against W can. Everything is replayed from
seeds recorded in the sequence's operations, so a shrunk sequence rebuilds the world it needs.
A module (no Lean), so a fake server written for the fuzzer (cairn_atproto's fake PDS) can
live in a library an app imports.
W : Type
init : Gen self.W
The world a sequence starts with, from the sequence's seed: random, so other accounts' likes and posts differ between sequences. A generator rather than a constant, so the world is built per sequence and never shared with a global.
handles : BoolWhich requests go to the server. The rest (and every loadImage) are answered as without
one, by Custom.replies or the default.
handle : Gen (self.W × Reply)
The server handles request id: the world after and its reply. Called each time the
request reaches the server: once, or twice when the host delivers it twice (retransmit). A
reply that doesn't answer the request's kind (Reply.answers) is replaced by a failure.
tick : Gen self.W
The world acting on its own between steps: other accounts liking, new posts, the AppView catching up.
fault : Gen Reply
What the app hears for a fault (failed before, or lost after): by default a timeout or a network failure.
checks : List (ClaimId × (S → self.W → Bool))
Checks over the app's state and the world, after every step (the first frame included).
Counted under the claim as server.
drained : List (ClaimId × (S → self.W → Bool))
Checks once a sequence ends and the host has answered everything outstanding, every
request reaching the server first (no faults): "once every reply is in, each post shows what
the server holds". Counted under the claim as serverDrained.
describe : StringThe world in words, for a failure's message.
failBefore : NatHow often, relative to the 30 of handling a request and of delivering its reply, the host injects each fault and lets the world act (0: never).
loseAfter : Natticks : Natretransmit : NatHow often the host delivers a request the server has handled to it again, before its reply is sent (a proxy's retry): the server handles it twice, and the app hears the second answer. Off by default: a refusal of the second delivery after the first was applied is a "refused" that did something, which no client can tell from the reply, so it only makes sense for a server that answers a repeated request as it did the first time.
Custom (S : Type) : Type 1
What an app may add to the fuzzer, by defining fuzz : Cairn.Fuzz.Custom State in its
namespace (docs/fuzz.md). Every field has a default.
edits : Option (Gen (List TextOp))
Scripts of text operations for a field's edit move (by claim id), each operation sent as
its own event; none keeps the default generator.
minSize : Option Size
The smallest window the app supports in a state; none means the app's App.minSize, or
the view's preferred size when that is 0 × 0.
noControl : List ClaimId
Moves that have no control on purpose (keyboard-only), exempt from presence.
budgetNs : Option NatThe frame-time budget for one step (update, view, layout), in nanoseconds.
replies : Option (Gen Reply)
Replies for the fuzzer's host to answer request id with, in the current state
(docs/fuzz.md, "The host"): for structured answers, such as the JSON a parser expects. none
keeps the default, which knows only the reply's shape (random bytes, a status, a size, a
fault). A reply that doesn't answer the request's kind (Reply.answers) is replaced by a
failure, since the host never sends one.
subEvents : Option (Gen SubEvent)
Events for the fuzzer's host to send an active subscription; none keeps the default.
relations : List (ClaimId × (Transition S → Bool))
Checks over one step, for claims stated about every step rather than every state (a
reply to a request not waited for changes nothing; scores only improve). Counted under the
claim as relation. A message the runtime drops (a reply to a cancelled or unknown id, an
event from a stopped subscription) is also given straight to receive, so a claim about
every message is checked on those too.
drained : List (ClaimId × (S → Bool))
outstanding : List (ClaimId × (S → List Nat → Bool))
Checks against what the runtime still owes the app, after every step (the first frame
included): the state, and the ids of the requests the runtime holds for it, sent and not
answered or queued behind its in-flight limit, and not cancelled (World.entries: sent oldest
first, then queued). These are exactly the ids the app can still hear a reply under. Counted
under the claim as outstanding.
weights : NatHow often, relative to the others, the fuzzer picks a control's action among those enabled on screen (default 1): weight a move reachable only deep in the app up, one that ends the state under test (Sign out) down, or a few keys up so presses race their own replies. A weight of 0 never picks the control; its presence is still checked.
server : Option (Server S)
A server with a world of its own, for claims stated against what it holds (docs/fuzz.md,
"A server"). none answers every request with replies or the default.
Definitions 18
golden : UInt64
mix (z : UInt64) : UInt64
The SplitMix64 finaliser.
ofSeed (seed : Nat) : Rng
next (g : Rng) : UInt64 × Rng
Gen (α : Type) : Type
A generator: a state transformer over the PRNG.
run {α : Type} (g : Gen α) (r : Rng) : α × Rng
u64 : Gen UInt64
range (lo hi : Nat) : Gen Nat
In [lo, hi].
int (lo hi : Int) : Gen Int
bool : Gen Bool
chance (num den : Nat) : Gen Bool
True with probability num / den.
elem {α : Type} [Inhabited α] (xs : List α) : Gen α
oneOf {α : Type} [Inhabited α] (gs : List (Gen α)) : Gen α
weighted {α : Type} [Inhabited α] (gs : List (Nat × Gen α)) : Gen αPick by weight.
listOf {α : Type} (n : Nat) (g : Gen α) : Gen (List α)
pick {α : Type} (xs : List (Nat × α)) : Gen (Option α)One of xs, each picked in proportion to its weight; one of weight 0 never is. none when
every weight is 0 (or there is nothing to pick).
seed : Gen NatA seed for a generator to be run later (Rng.ofSeed), so the operation that runs it can
record the seed and replay without the stream it came from.
empty {S : Type} : Server SNo server: no world, no request handled.
Instances 3
instReprRng : Repr Rng
instInhabitedRng : Inhabited Rng
instInhabitedCustom {S : Type} : Inhabited (Custom S)