Source lean/Tests/ModelReplay.lean
import Tests.ReferenceExplorerimport Tests.Parsingimport Determinize.Checking.FiniteModelnamespace Determinize.Testsopen Frontend Checking Spec.Paper Spec.FiniteModel Determinize.Finiteprivate def duplicateLabels : Candidate := ⟨0,  #[.eval (.real 3) [] [], .eval (.real 3) [] [],    .deliver (.number 3) [], .deliver (.number 3) []],  #[⟨.transient, #[⟨2, 1⟩]⟩, ⟨.transient, #[⟨3, 1⟩]⟩,    ⟨.returned 3, #[⟨2, 1⟩]⟩, ⟨.returned 3, #[⟨3, 1⟩]⟩]⟩private def duplicateIndices (i : Fin duplicateLabels.states.size) (_ : Nat) : Nat :=  if i.val = 0 then 2 else 3private theorem duplicateReplay : duplicateLabels.IndexedReplayValid (.real 3) .source    duplicateIndices := by decide +kernelexample : (duplicateLabels.graphModel (indexedReplay_valid _ _ _ _ duplicateReplay)).Matches    (Subject.source.program (.real 3)) :=  Proof.FiniteModel.indexedReplay_matches _ _ duplicateReplayexample : ¬ duplicateLabels.IndexedReplayValid (.real 3) .source (fun _ _ ↦ 0) := by  decide +kernelprivate def candidateFor (text : String) (subject : Subject := .source) :    IO (Core × Candidate) := do  let p ← IO.ofExcept (compile text)  match ReferenceExplorer.explore p.source subject with  | .complete candidate => return (p.source, candidate)  | result => throw (IO.userError s!"expected complete graph: {reprStr result}")private def accepted (source : Core) (candidate : Candidate) (subject : Subject := .source) :    Bool :=  (checkModel source subject candidate).isSomeprivate def indexedAccepted (source : Core) (candidate : Candidate) (subject : Subject := .source) :    Bool :=  let indices := candidate.states.map fun state ↦ match step state with    | .ok (.next _ outcomes) => (outcomes.map fun (outcome : Rat × State) ↦        (candidate.states.toList.findIdx? fun s ↦ decide (s = outcome.2)).getD 0).toArray    | _ => #[]  decide (candidate.IndexedReplayValid source subject    (fun i k ↦ (indices[i.val]!)[k]!))private def setRow (candidate : Candidate) (i : Nat) (row : Row) : Candidate :=  {candidate with rows := candidate.rows.set! i row}def modelReplay : IO Unit := do  for text in [      "0.1 + 0.2", "6/2", "if false then 1/0 else 7", "let x = 4 in (fun y => x + y) 3",      "let f = rec f x => f x in f 0",      "let f = rec f x => if flip(0.5) then 3 else f x in f 0",      "discrete[G](0,0.25,0,0.75)", "discrete[E](*)",      "let p = bernoulli[E](0.5) in discrete[E](p/2,0.25,*)",      "let f = fun p => p :: 0.25 :: [] in discrete_list[E](f 0.25)",      "bernoulli[G](0)", "bernoulli[G](1)",      "let _ = observe(flip(0.5)) in 3",      "match 2::[] with [] => 0 | x::xs => x",      "let fact = rec f n => if n < 1 then 1 else n * f (n-1) in fact 4"] do    let (source, candidate) ← candidateFor text    check (accepted source candidate) s!"machine replay: {text}"    check (indexedAccepted source candidate) s!"indexed machine replay: {text}"  let divisionByZero : Candidate := ⟨0, #[    .eval (.div (.real 7) (.real 0)) [] [],    .eval (.real 7) [] [.left .div (.real 0) []],    .deliver (.number 7) [.left .div (.real 0) []],    .eval (.real 0) [] [.right .div (.number 7)],    .deliver (.number 0) [.right .div (.number 7)],    .deliver (.number 0) []],    (Array.range 5).map (fun i ↦ ⟨.transient, #[⟨i + 1, 1⟩]⟩) ++      #[⟨.returned 0, #[⟨5, 1⟩]⟩]⟩  check (!(accepted (.div (.real 7) (.real 0)) divisionByZero))    "certificate accepted a fabricated division-by-zero result"  let (threeSource, three) ← candidateFor "3"  let (sevenSource, seven) ← candidateFor "7"  let some checkedThree := checkModel threeSource .source three    | throw (IO.userError "expected checked model")  let some checkedSeven := checkModel sevenSource .source seven    | throw (IO.userError "expected checked model for seven")  check (decide (∃ state, checkedThree.model.kind state = .returned 3)) "extracted reward three"  check (decide (∃ state, checkedSeven.model.kind state = .returned 7)) "extracted reward seven"  let (targetSource, target) ← candidateFor "uniform[E](0,3)" .determinized  check (accepted targetSource target .determinized) "determinized mean replay"  check (!(checkModelReplay targetSource .source target).isSome) "wrong subject"  check (!(checkModelReplay (.real 7) .determinized target).isSome) "wrong source"  let (coinSource, coin) ← candidateFor "bernoulli[G](0.25)"  let some checkedCoin := checkModel coinSource .source coin    | throw (IO.userError "expected checked coin model")  check (checkedCoin.model.size == coin.states.size) "extracted model dimensions"  let accepted := accepted coinSource  let extra := coin.states.size  let oneExtra : Candidate :=    { coin with      states := coin.states.push .rejected      rows := coin.rows.push ⟨.rejected, #[⟨extra, 1⟩]⟩ }  check (accepted oneExtra) "unique unreachable state"  let duplicate : Candidate :=    { oneExtra with      states := oneExtra.states.push .rejected      rows := oneExtra.rows.push ⟨.rejected, #[⟨extra + 1, 1⟩]⟩ }  check (!accepted duplicate) "duplicate unreachable states"  check (indexedAccepted coinSource duplicate) "duplicate state labels in indexed replay"  for candidate in [coin, oneExtra,      {coin with initial := 1}, {coin with rows := coin.rows.pop},      {coin with states := coin.states.pop, rows := coin.rows.pop}] do    check (indexedAccepted coinSource candidate == accepted candidate)      "indexed replay agrees with full replay"  check (!indexedAccepted targetSource target .source) "indexed wrong subject"  check (!indexedAccepted (.real 7) target .determinized) "indexed wrong source"  let mut sampled := false  let mut terminal := false  for i in [:coin.rows.size] do    let row := coin.rows[i]?.getD ⟨.rejected, #[]⟩    if row.edges.size == 2 then      sampled := true      let first := row.edges[0]?.getD ⟨0, 0⟩      let second := row.edges[1]?.getD ⟨0, 0⟩      for replacement in [          {row with edges := #[⟨first.target, 1⟩]},          {row with edges := #[⟨first.target, 1 / 2⟩, ⟨second.target, 1 / 2⟩]},          {row with edges :=            #[⟨first.target, first.probability⟩, ⟨first.target, second.probability⟩]},          {row with edges := #[⟨coin.states.size, 1⟩]},          {row with kind := .returned 99}] do        check (!accepted (setRow coin i replacement)) "mutated sampled row"        check (!indexedAccepted coinSource (setRow coin i replacement))          "indexed mutated sampled row"    match row.kind with    | .returned reward =>      terminal := true      check (!accepted (setRow coin i {row with kind := .returned (reward + 1)})) "changed reward"      check (!accepted (setRow coin i {row with edges := #[⟨0, 1⟩]})) "nonabsorbing terminal"      check (!accepted (setRow coin i {row with kind := .rejected})) "changed outcome"    | _ => pure ()  check (sampled && terminal) "mutation fixtures exercised"  check (!accepted {coin with rows := coin.rows.pop}) "truncated rows"  check (!accepted {coin with states := coin.states.pop, rows := coin.rows.pop}) "truncated graph"  check (!accepted {coin with initial := coin.states.size}) "invalid initial index"  check (!accepted {coin with initial := 1}) "wrong initial state"  check (!accepted {coin with states := coin.states.set! 0 (.eval (.real 7) [] [])})    "changed initial expression"  check (!accepted {coin with states := coin.states.set! 1 (.eval (.bvar 99) [] [])})    "malformed reachable state"  let unusedFreeVariable : Core := .letE (.lam (.bvar 2)) (.real 3)  match ReferenceExplorer.explore unusedFreeVariable .source with  | .complete candidate =>    check (!(checkModel unusedFreeVariable .source candidate).isSome)      "free variable in unused closure"  | _ => throw (IO.userError "scope fixture must finish exploration")  let broken : Candidate := ⟨0, #[.eval (.bvar 0) [] []],    #[⟨.rejected, #[⟨0, 1⟩]⟩]⟩  check (!(checkModel (.bvar 0) .source broken).isSome) "stuck machine cannot be labeled rejected"#print axioms indexedStates_valid#print axioms indexedReplay_valid#print axioms Proof.FiniteModel.indexedReplay_matches#print axioms Proof.FiniteModel.replay_matches#print axioms checkModel#print axioms replay_reachable_covered#print axioms replay_reachable_no_failure#print axioms replay_successor_covered#print axioms replay_transition_weightend Determinize.Tests