import Tests.ReferenceExplorerimport Determinize.Finite.Exploreimport Tests.Parsingimport Determinize.Finite.Exportnamespace Determinize.Testsopen Frontend Checking Spec.Paper Spec.FiniteModel Determinize.Finiteprivate def graph (text : String) (subject : Subject := .source) : IO Candidate := do let p ← IO.ofExcept (compile text) match explore p.source subject with | .complete candidate _ => let .complete previous := ReferenceExplorer.explore p.source subject | throw (IO.userError s!"reference exploration failed: {text}") check (candidate.states == previous.states) s!"changed state numbering: {text}" check (candidate.rows.size == previous.rows.size) s!"changed row count: {text}" for (currentRow, previousRow) in candidate.rows.toList.zip previous.rows.toList do check (currentRow.kind == previousRow.kind) s!"changed state kind: {text}" let weights := fun (row : Row) ↦ (row.edges.toList.map fun edge ↦ (edge.target, edge.probability)).mergeSort (fun a b ↦ a.1 ≤ b.1) check (weights currentRow == weights previousRow) s!"changed weights: {text}" return candidate | _ => throw (IO.userError s!"exploration failed: {text}")private def reward (candidate : Candidate) (steps : Nat) : Rat := Id.run do let mut values := Array.replicate candidate.states.size (0 : Rat) for _ in [:steps] do values := candidate.rows.map fun row ↦ match row.kind with | .returned r => r | .rejected => 0 | .transient => row.edges.foldl (fun total edge ↦ total + edge.probability * values[edge.target]!) 0 return values[candidate.initial]!def explorer : IO Unit := do for (text, expected) in [ ("0.1 + 0.2", (3 / 10 : Rat)), ("6 / 2", 3), ("if false then 1/0 else 7", 7), ("let x = 4 in let f = fun y => x + y in let x = 100 in f 3", 7), ("let fact = rec f n => if n < 1 then 1 else n * f (n-1) in fact 5", 120), ("match 2::3::[] with [] => 0 | x::xs => match xs with [] => 0 | y::ys => x*10+y", 23), ("match inr 7 with inl x => 0 | inr y => y", 7), ("match inl 9 with inl x => x | inr y => 0", 9), ("fst (2,3) + snd (4,5)", 7), ("if flip(0.25) then 8 else -4", -1), ("let _ = observe(flip(0.5)) in 3", 3 / 2), ("let _ = observe(false) in uniform[G](0,1)", 0), ("if flip(0) then uniform[G](0,1) else 7", 7), ("discrete[G](0,0.25,0,0.75)", 5 / 2), ("discrete[G](*)", 0), ("let p = bernoulli[E](0.5) in discrete[E](p/2,0.25,*)", 5 / 4), ("let f = fun p => p :: 0.25 :: [] in discrete_list[E](f 0.25)", 5 / 4), ("bernoulli[G](1)", 1), ("bernoulli[G](0)", 0)] do let candidate ← graph text check (reward candidate (candidate.states.size + 1) == expected) s!"exact reward: {text}" let files ← IO.ofExcept (render candidate) let again ← graph text check (files.candidate == candidateText again) "stable state numbering" for (text, expected) in [ ("uniform[E](0,3)", (3 / 2 : Rat)), ("gauss[E](3,2)", 3), ("poisson[E](4)", 4), ("exponential[E](2)", 1 / 2), ("gamma[E](6,2)", 3), ("beta[E](1,3)", 1 / 4), ("bernoulli[E](0.3)", 3 / 10), ("discrete[E](0,0.25,0,0.75)", 5 / 2)] do let candidate ← graph text .determinized check (reward candidate (candidate.states.size + 1) == expected) s!"exact mean: {text}" let loop ← graph "let f = rec f x => f x in f 0" check (loop.rows.all fun row ↦ row.kind == .transient) "closed nonterminating loop" check (reward loop 100 == 0) "nontermination contributes zero" let retry ← graph "let f = rec f x => if flip(0.5) then 3 else f x in f 0" check (retry.rows.toList.zipIdx.any fun (row, i) ↦ row.edges.any fun e ↦ e.target < i) "retry graph" check (reward retry 100 > 2 && reward retry 100 < 3) "geometric retry reward bound" let growing ← IO.ofExcept (compile "let f = rec f x => f (x+1) in f 0") match explore growing.source .source {maxStates := 100} with | .incomplete .states .. => pure () | _ => throw (IO.userError "growing recursion must exhaust states") for (limits, expected) in [ ({maxStates := 0 : Limits}, Limit.states), ({maxEdges := 0 : Limits}, Limit.edges), ({maxStateBytes := 0 : Limits}, Limit.stateBytes)] do match explore (.real 3) .source limits with | .incomplete actual .. => check (actual == expected) "resource limit classification" | _ => throw (IO.userError "expected incomplete exploration") for text in ["1/0", "1/bernoulli[G](0.5)", "uniform[E](0,1)/0", "uniform[G](0,1)", "poisson[G](3)", "gauss[G](0,1)", "uniform[E](0,uniform[G](1,2))", "uniform[E](2,1)", "bernoulli[G](2)", "true"] do let p ← IO.ofExcept (compile text) match explore p.source .determinized with | .failed .. => pure () | _ => throw (IO.userError s!"expected export failure: {text}") let state := State.deliver (.number 1) [] check (ReferenceExplorer.aggregate [(0, state), (1 / 3, state), (2 / 3, state)] == [(1, state)]) "duplicate successors" let terminal : Candidate := ⟨0, #[state], #[⟨.returned (-3), #[⟨0, 1⟩]⟩]⟩ let files ← IO.ofExcept (render terminal) check (files.transitions == "dtmc\n0 1 1\n1 1 1\n") "once-only terminal reward sink" check (files.positiveRewards == "" && files.negativeRewards == "0 3\n") "signed rewards" check (files.labels == "#DECLARATION\ninit returned rejected done\n#END\n0 init returned\n1 done\n") "initial terminal labels" for bad in [ {terminal with rows := #[]}, {terminal with initial := 1}, {terminal with rows := #[⟨.transient, #[⟨0, 1 / 2⟩]⟩]}, {terminal with rows := #[⟨.transient, #[⟨0, 1 / 2⟩, ⟨0, 1 / 2⟩]⟩]}, {terminal with rows := #[⟨.returned 3, #[⟨1, 1⟩]⟩]}] do check (match render bad with | .error _ => true | .ok _ => false) "malformed export rejected"end Determinize.Tests