import Determinize.Finite.Exploreimport Std.Data.HashMapnamespace Determinize.Tests.ReferenceExploreropen Determinize.Finiteopen Spec.Paper Spec.FiniteModel Checkinginductive Exploration where | complete (candidate : Candidate) | incomplete (limit : Limit) (discovered expanded edges : Nat) | failed (state : Nat) (failure : Failure)deriving Reprprivate def insertSuccessor (probability : Rat) (state : State) : List (Rat × State) → List (Rat × State) | [] => [(probability, state)] | (p, s) :: rest => if s == state then (p + probability, s) :: rest else (p, s) :: insertSuccessor probability state rest/-- Preserve first-discovery order, combine equal successors, and remove zero edges. -/def aggregate (successors : List (Rat × State)) : List (Rat × State) := successors.foldl (fun accumulated (p, s) ↦ if p == 0 then accumulated else insertSuccessor p s accumulated) []/-- Breadth-first exploration. Limits never produce a `Candidate`. Hash collisionsare resolved by structural equality; rational values retain exact normalized form. -/def explore (source : Core) (subject : Subject := .determinized) (limits : Limits := {}) : Exploration := Id.run do if limits.maxStates == 0 then return .incomplete .states 0 0 0 let program := match subject with | .source => source | .determinized => source.determinize let initial := State.eval program [] [] if (reprStr initial).utf8ByteSize > limits.maxStateBytes then return .incomplete .stateBytes 0 0 0 let mut states := #[initial] let mut indices : Std.HashMap State Nat := ({} : Std.HashMap State Nat).insert initial 0 let mut rows : Array Row := #[] let mut edgeCount := 0 let mut cursor := 0 while cursor < states.size do let state := states[cursor]! let action := step state if let .error failure := action then return .failed cursor failure let .ok action := action | unreachable! let (kind, successors) := match action with | .returned reward => (StateKind.returned reward, [(1, state)]) | .rejected => (.rejected, [(1, state)]) | .next _ successors => (.transient, successors) if successors.any (fun (p, _) ↦ p < 0) then return .failed cursor (.invalid "negative transition probability") let successors := aggregate successors if (successors.map Prod.fst).sum != 1 then return .failed cursor (.invalid "transition probabilities do not sum to one") let mut edges : Array Edge := #[] for (probability, next) in successors do if edgeCount ≥ limits.maxEdges then return .incomplete .edges states.size rows.size edgeCount let mut target := 0 match indices[next]? with | some index => target := index | none => if states.size ≥ limits.maxStates then return .incomplete .states states.size rows.size edgeCount if (reprStr next).utf8ByteSize > limits.maxStateBytes then return .incomplete .stateBytes states.size rows.size edgeCount target := states.size states := states.push next indices := indices.insert next target edges := edges.push ⟨target, probability⟩ edgeCount := edgeCount + 1 rows := rows.push ⟨kind, edges⟩ cursor := cursor + 1 return .complete ⟨0, states, rows⟩end Determinize.Tests.ReferenceExplorer