Cairn · module

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

Order

Structures 4

structure

Cairn.Fuzz.Rng

lean/Cairn/Fuzz/Rng.lean:17
Rng : Type
Fields
state : UInt64
Instances

Repr Inhabited

structure

Cairn.Fuzz.Transition

lean/Cairn/Fuzz/Rng.lean:106
Transition (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.

Fields
before : S
msg : Option Msg
after : S
effects : List Effect
structure

Cairn.Fuzz.Server

lean/Cairn/Fuzz/Rng.lean:129
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.

Fields
W : Type

What the server holds. Threaded through the sequence without being copied: handle and tick get the only reference, so an Array or HashMap in it is updated in place (run with LEAN_ABORT_ON_NONLINEAR=1 and markLinear to check).

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 : Bool

Which 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 : String

The world in words, for a failure's message.

failBefore : Nat

How 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 : Nat
ticks : Nat
retransmit : Nat

How 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.

structure

Cairn.Fuzz.Custom

lean/Cairn/Fuzz/Rng.lean:182
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.

Fields
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 Nat

The 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))

Checks once a sequence ends and the host has answered everything outstanding (with replies or the default): every load finished, nothing still waiting. Counted under the claim as drained.

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 : Nat

How 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.

badge : List (ClaimId × (S → Option String → Bool))

Checks of the Dock badge, after every step: the state, and the label the host shows, the last badge effect's (none before any; ^1030). Counted under the claim as badge.

Instances

Inhabited

Definitions 18

def

Cairn.Fuzz.Rng.golden

lean/Cairn/Fuzz/Rng.lean:23
golden : UInt64
def

Cairn.Fuzz.Rng.mix

lean/Cairn/Fuzz/Rng.lean:26
mix (z : UInt64) : UInt64

The SplitMix64 finaliser.

def

Cairn.Fuzz.Rng.ofSeed

lean/Cairn/Fuzz/Rng.lean:31
ofSeed (seed : Nat) : Rng
def

Cairn.Fuzz.Rng.next

lean/Cairn/Fuzz/Rng.lean:33
next (g : Rng) : UInt64 × Rng
abbrev

Cairn.Fuzz.Gen

lean/Cairn/Fuzz/Rng.lean:40
Gen (α : Type) : Type

A generator: a state transformer over the PRNG.

def

Cairn.Fuzz.Gen.run

lean/Cairn/Fuzz/Rng.lean:44
run {α : Type} (g : Gen α) (r : Rng) : α × Rng
def

Cairn.Fuzz.Gen.u64

lean/Cairn/Fuzz/Rng.lean:46
u64 : Gen UInt64
def

Cairn.Fuzz.Gen.range

lean/Cairn/Fuzz/Rng.lean:54
range (lo hi : Nat) : Gen Nat

In [lo, hi].

def

Cairn.Fuzz.Gen.int

lean/Cairn/Fuzz/Rng.lean:56
int (lo hi : Int) : Gen Int
def

Cairn.Fuzz.Gen.bool

lean/Cairn/Fuzz/Rng.lean:59
bool : Gen Bool
def

Cairn.Fuzz.Gen.chance

lean/Cairn/Fuzz/Rng.lean:62
chance (num den : Nat) : Gen Bool

True with probability num / den.

def

Cairn.Fuzz.Gen.elem

lean/Cairn/Fuzz/Rng.lean:64
elem {α : Type} [Inhabited α] (xs : List α) : Gen α
def

Cairn.Fuzz.Gen.oneOf

lean/Cairn/Fuzz/Rng.lean:67
oneOf {α : Type} [Inhabited α] (gs : List (Gen α)) : Gen α
def

Cairn.Fuzz.Gen.weighted

lean/Cairn/Fuzz/Rng.lean:73
weighted {α : Type} [Inhabited α] (gs : List (Nat × Gen α)) : Gen α

Pick by weight.

def

Cairn.Fuzz.Gen.listOf

lean/Cairn/Fuzz/Rng.lean:81
listOf {α : Type} (n : Nat) (g : Gen α) : Gen (List α)
def

Cairn.Fuzz.Gen.pick

lean/Cairn/Fuzz/Rng.lean:88
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).

def

Cairn.Fuzz.Gen.seed

lean/Cairn/Fuzz/Rng.lean:99
seed : Gen Nat

A 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.

def

Cairn.Fuzz.Server.empty

lean/Cairn/Fuzz/Rng.lean:174
empty {S : Type} : Server S

No server: no world, no request handled.

Instances 3

instance

Cairn.Fuzz.instReprRng

lean/Cairn/Fuzz/Rng.lean:19
instReprRng : Repr Rng
instance

Cairn.Fuzz.instInhabitedRng

lean/Cairn/Fuzz/Rng.lean:19
instInhabitedRng : Inhabited Rng
instance

Cairn.Fuzz.instInhabitedCustom

lean/Cairn/Fuzz/Rng.lean:229
instInhabitedCustom {S : Type} : Inhabited (Custom S)