Source lean/Determinize/Finite/Shared.lean
import Determinize.Proof.FiniteModel.Quotenamespace Determinize.Finite.Sharedopen Leanstructure Definition where  name : Name  type : Lean.Expr  value : Lean.Exprstructure Builder where  namespacePrefix : Name := `certificateData  definitions : Array Definition := #[]  known : ExprMap Lean.Expr := {}  quoted : ExprMap Lean.Expr := {}private def sharedType? (e : Lean.Expr) : Option Lean.Expr := do  let .const name _ := e.getAppFn | none  let args := e.getAppArgs  if name.getPrefix == ``Spec.Paper.Expr && args.size ≥ 2 then    return mkApp2 (mkConst ``Spec.Paper.Expr) args[0]! args[1]!  if name.getPrefix == ``Value then return mkConst ``Value  if name.getPrefix == ``Frame then return mkConst ``Frame  if name.getPrefix == ``State then return mkConst ``State  if name == ``List.cons || name == ``List.nil then    let some type := args[0]? | none    if type == mkConst ``Value || type == mkConst ``Frame ||        type == toTypeExpr Spec.Paper.Core || type == mkConst ``Rat then      return mkApp (mkConst ``List [0]) type  noneprivate partial def share (e : Lean.Expr) : StateM Builder Lean.Expr := do  if let some result := (← get).quoted[e]? then return result  let args ← e.getAppArgs.mapM share  let body := mkAppN e.getAppFn args  let some type := sharedType? body | return body  if let some known := (← get).known[body]? then    modify fun s ↦ {s with quoted := s.quoted.insert e known}    return known  let s ← get  let name := s.namespacePrefix.str s!"d{s.definitions.size}"  let result := mkConst name  set {s with    definitions := s.definitions.push ⟨name, type, body⟩,    known := s.known.insert body result,    quoted := s.quoted.insert e result}  return resultdef quote {α : Type} [ToExpr α] (value : α) : StateM Builder Lean.Expr :=  share (toExpr value)def array (type : Lean.Expr) (values : Array Lean.Expr) : Lean.Expr :=  let nil := mkApp (mkConst ``List.nil [0]) type  let cons := mkApp (mkConst ``List.cons [0]) type  let list := values.foldr (fun value rest ↦ mkApp2 cons value rest) nil  mkApp2 (mkConst ``List.toArray [0]) type listdef rewardCandidate (candidate : Reward.Candidate) : StateM Builder Lean.Expr := do  let states ← candidate.states.mapM quote  let rows ← candidate.rows.mapM quote  return mkApp3 (mkConst ``Reward.Candidate.mk) (toExpr candidate.initial)    (array (toTypeExpr State) states) (array (toTypeExpr Reward.Row) rows)def candidate (candidate : Candidate) : StateM Builder Lean.Expr := do  let states ← candidate.states.mapM quote  let rows ← candidate.rows.mapM quote  return mkApp3 (mkConst ``Candidate.mk) (toExpr candidate.initial)    (array (toTypeExpr State) states) (array (toTypeExpr Row) rows)private partial def exprText (e : Lean.Expr) : String := Id.run do  if e.isAppOfArity ``OfNat.ofNat 3 then    let args := e.getAppArgs    if args[0]! == mkConst ``Nat then      if let some n := args[1]!.rawNatLit? then return toString n  if e.isAppOfArity ``List.toArray 2 then    let mut list := e.appArg!    let mut entries := #[]    while list.isAppOfArity ``List.cons 3 do      let args := list.getAppArgs      entries := entries.push (exprText args[1]!)      list := args[2]!    if list.isAppOfArity ``List.nil 1 then      return "#[" ++ String.intercalate ", " entries.toList ++ "]"  match e with  | .const name _ => return s!"@{name}"  | .lit (.natVal n) => return toString n  | .app .. =>    return "(" ++ exprText e.getAppFn ++ " " ++      String.intercalate " " (e.getAppArgs.toList.map exprText) ++ ")"  | _ => panic! "unexpected expression in shared certificate data"def Builder.text (s : Builder) (value : Lean.Expr) : String :=  let args := value.getAppArgs  let type := value.getAppFn.constName!.getPrefix  String.join (s.definitions.toList.map fun d ↦    s!"def {d.name} : {exprText d.type} := {exprText d.value}\n") ++  s!"\ndef candidate : {type} where\n  initial := {exprText args[0]!}\n" ++  s!"  states := {exprText args[1]!}\n  rows := {exprText args[2]!}\n"end Determinize.Finite.Shared