src/HOL/Tools/SMT/verit_proof.ML

add reconstruction by veriT in method smt

(*  Title:      HOL/Tools/SMT/verit_proof.ML
    Author:     Mathias Fleury, ENS Rennes
    Author:     Sascha Boehme, TU Muenchen

VeriT proofs: parsing and abstract syntax tree.
*)

signature VERIT_PROOF =
sig
  (*proofs*)
  datatype veriT_step = VeriT_Step of {
    id: string,
    rule: string,
    prems: string list,
    proof_ctxt: term list,
    concl: term,
    fixes: string list}

  datatype veriT_replay_node = VeriT_Replay_Node of {
    id: string,
    rule: string,
    args: term list,
    prems: string list,
    proof_ctxt: term list,
    concl: term,
    bounds: (string * typ) list,
    subproof: (string * typ) list * term list * veriT_replay_node list}

  (*proof parser*)
  val parse: typ Symtab.table -> term Symtab.table -> string list ->
    Proof.context -> veriT_step list * Proof.context
  val parse_replay: typ Symtab.table -> term Symtab.table -> string list ->
    Proof.context -> veriT_replay_node list * Proof.context

  val map_replay_prems: (string list -> string list) -> veriT_replay_node -> veriT_replay_node
  val veriT_step_prefix : string
  val veriT_input_rule: string
  val veriT_normalized_input_rule: string
  val veriT_la_generic_rule : string
  val veriT_rewrite_rule : string
  val veriT_simp_arith_rule : string
  val veriT_tmp_skolemize_rule : string
  val veriT_subproof_rule : string
  val veriT_local_input_rule : string
end;

structure VeriT_Proof: VERIT_PROOF =
struct

open SMTLIB_Proof

datatype raw_veriT_node = Raw_VeriT_Node of {
  id: string,
  rule: string,
  args: SMTLIB.tree,
  prems: string list,
  concl: SMTLIB.tree,
  subproof: raw_veriT_node list}

fun mk_raw_node id rule args prems concl subproof =
  Raw_VeriT_Node {id = id, rule = rule, args = args, prems = prems, concl = concl,
    subproof = subproof}

datatype veriT_node = VeriT_Node of {
  id: string,
  rule: string,
  prems: string list,
  proof_ctxt: term list,
  concl: term,
  bounds: string list}

fun mk_node id rule prems proof_ctxt concl bounds =
  VeriT_Node {id = id, rule = rule, prems = prems, proof_ctxt = proof_ctxt, concl = concl,
    bounds = bounds}

datatype veriT_replay_node = VeriT_Replay_Node of {
  id: string,
  rule: string,
  args: term list,
  prems: string list,
  proof_ctxt: term list,
  concl: term,
  bounds: (string * typ) list,
  subproof: (string * typ) list * term list * veriT_replay_node list}

fun mk_replay_node id rule args prems proof_ctxt concl bounds subproof =
  VeriT_Replay_Node {id = id, rule = rule, args = args, prems = prems, proof_ctxt = proof_ctxt,
    concl = concl, bounds = bounds, subproof = subproof}

datatype veriT_step = VeriT_Step of {
  id: string,
  rule: string,
  prems: string list,
  proof_ctxt: term list,
  concl: term,
  fixes: string list}

fun mk_step id rule prems proof_ctxt concl fixes =
  VeriT_Step {id = id, rule = rule, prems = prems, proof_ctxt = proof_ctxt, concl = concl,
    fixes = fixes}

val veriT_step_prefix = ".c"
val veriT_input_rule = "input"
val veriT_la_generic_rule = "la_generic"
val veriT_normalized_input_rule = "__normalized_input" (* arbitrary *)
val veriT_rewrite_rule = "__rewrite" (* arbitrary *)
val veriT_subproof_rule = "subproof"
val veriT_local_input_rule = "__local_input" (* arbitrary *)
val veriT_simp_arith_rule = "simp_arith"

(* Even the veriT developer do not know if the following rule can still appear in proofs: *)
val veriT_tmp_skolemize_rule = "tmp_skolemize"

(* proof parser *)

fun node_of p cx =
  ([], cx)
  ||>> `(with_fresh_names (term_of p))
  |>> snd

fun find_type_in_formula (Abs (v, T, u)) var_name =
    if String.isPrefix var_name v then SOME T else find_type_in_formula u var_name
  | find_type_in_formula (u $ v) var_name =
    (case find_type_in_formula u var_name of
      NONE => find_type_in_formula v var_name
    | some_T => some_T)
  | find_type_in_formula (Free(v, T)) var_name =
    if String.isPrefix var_name v then SOME T else NONE
  | find_type_in_formula _ _ = NONE

fun find_type_of_free_in_formula (Free (v, T) $ u) var_name =
    if String.isPrefix var_name v then SOME T else find_type_in_formula u var_name
  | find_type_of_free_in_formula (Abs (v, T, u)) var_name =
    if String.isPrefix var_name v then SOME T else find_type_in_formula u var_name
  | find_type_of_free_in_formula (u $ v) var_name =
    (case find_type_in_formula u var_name of
      NONE => find_type_in_formula v var_name
    | some_T => some_T)
  | find_type_of_free_in_formula _ _ = NONE

fun add_bound_variables_to_ctxt concl =
  fold (update_binding o
    (fn s => (s, Term (Free (s, the_default dummyT (find_type_in_formula concl s))))))


local

  fun remove_Sym (SMTLIB.Sym y) = y

  fun extract_symbols bds =
    bds
    |> map (fn SMTLIB.S [SMTLIB.Key _, SMTLIB.Sym x, SMTLIB.Sym y] => [x, y]
            | SMTLIB.S syms => map remove_Sym syms)
    |> flat

  fun extract_symbols_map bds =
    bds
    |> map (fn SMTLIB.S [SMTLIB.Key _, SMTLIB.Sym x, _] => [x]
            | SMTLIB.S syms =>  map remove_Sym syms)
    |> flat
in

fun bound_vars_by_rule "bind" (SMTLIB.S bds) = extract_symbols bds
  | bound_vars_by_rule "qnt_simplify" (SMTLIB.S bds) = extract_symbols_map bds
  | bound_vars_by_rule "sko_forall" (SMTLIB.S bds) = extract_symbols_map bds
  | bound_vars_by_rule "sko_ex" (SMTLIB.S bds) = extract_symbols_map bds
  | bound_vars_by_rule _ _ = []

fun global_bound_vars_by_rule _ _ = []

(* VeriT adds "?" before some variable. *)
fun remove_all_qm (SMTLIB.Sym v :: l) =
    SMTLIB.Sym (perhaps (try (unprefix "?")) v) :: remove_all_qm l
  | remove_all_qm (SMTLIB.S l :: l') = SMTLIB.S (remove_all_qm l) :: remove_all_qm l'
  | remove_all_qm (SMTLIB.Key v :: l) = SMTLIB.Key v :: remove_all_qm l
  | remove_all_qm (v :: l) = v :: remove_all_qm l
  | remove_all_qm [] = []

fun remove_all_qm2 (SMTLIB.Sym v) = SMTLIB.Sym (perhaps (try (unprefix "?")) v)
  | remove_all_qm2 (SMTLIB.S l) = SMTLIB.S (remove_all_qm l)
  | remove_all_qm2 (SMTLIB.Key v) = SMTLIB.Key v
  | remove_all_qm2 v = v

val parse_rule_and_args =
  let
    fun parse_rule_name (SMTLIB.Sym rule :: l) = (rule, l)
      | parse_rule_name l = (veriT_subproof_rule, l)
    fun parse_args (SMTLIB.Key "args" :: args :: l) = (remove_all_qm2 args, l)
      | parse_args l = (SMTLIB.S [], l)
  in
    parse_rule_name
    ##> parse_args
  end

end

fun parse_raw_proof_step (p :  SMTLIB.tree) : raw_veriT_node =
  let
    fun rotate_pair (a, (b, c)) = ((a, b), c)
    fun get_id (SMTLIB.S [SMTLIB.Sym "set", SMTLIB.Sym id, SMTLIB.S l]) = (id, l)
      | get_id t = raise Fail ("unrecognized VeriT proof " ^ @{make_string} t)
    fun parse_source (SMTLIB.Key "clauses" :: SMTLIB.S source ::l) =
        (SOME (map (fn (SMTLIB.Sym id) => id) source), l)
      | parse_source l = (NONE, l)
    fun parse_subproof rule args id_of_father_step ((subproof_step as SMTLIB.S (SMTLIB.Sym "set" :: _)) :: l) =
        let
          val subproof_steps = parse_raw_proof_step subproof_step
        in
          apfst (curry (op ::) subproof_steps) (parse_subproof rule args id_of_father_step l)
        end
      | parse_subproof _ _  _ l = ([], l)

    fun parse_and_clausify_conclusion (SMTLIB.Key "conclusion" :: SMTLIB.S [] :: []) =
          SMTLIB.Sym "false"
      | parse_and_clausify_conclusion (SMTLIB.Key "conclusion" :: SMTLIB.S concl :: []) =
          (SMTLIB.S (remove_all_qm (SMTLIB.Sym "or" :: concl)))

    fun to_raw_node ((((((id, rule), args), prems), subproof), concl)) =
      (mk_raw_node id rule args (the_default [] prems) concl subproof)
  in
    (get_id
    ##> parse_rule_and_args
    #> rotate_pair
    #> rotate_pair
    ##> parse_source
    #> rotate_pair
    #> (fn ((((id, rule), args), prems), sub) =>
      ((((id, rule), args), prems), parse_subproof rule args id sub))
    #> rotate_pair
    ##> parse_and_clausify_conclusion
    #> to_raw_node)
    p
  end

fun proof_ctxt_of_rule "bind" t = t
  | proof_ctxt_of_rule "sko_forall" t = t
  | proof_ctxt_of_rule "sko_ex" t = t
  | proof_ctxt_of_rule "let" t = t
  | proof_ctxt_of_rule "qnt_simplify" t = t
  | proof_ctxt_of_rule _ _ = []

fun args_of_rule "forall_inst" t = t
  | args_of_rule _ _ = []

fun map_replay_prems f (VeriT_Replay_Node {id, rule, args, prems, proof_ctxt, concl, bounds,
      subproof = (bound, assms, subproof)}) =
  (VeriT_Replay_Node {id = id, rule = rule, args = args, prems = f prems, proof_ctxt = proof_ctxt,
    concl = concl, bounds = bounds, subproof = (bound, assms, map (map_replay_prems f) subproof)})

fun map_replay_id f (VeriT_Replay_Node {id, rule, args, prems, proof_ctxt, concl, bounds,
      subproof = (bound, assms, subproof)}) =
  (VeriT_Replay_Node {id = f id, rule = rule, args = args, prems = prems, proof_ctxt = proof_ctxt,
    concl = concl, bounds = bounds, subproof = (bound, assms, map (map_replay_id f) subproof)})

fun id_of_last_step prems =
  if null prems then []
  else
    let val VeriT_Replay_Node {id, ...} = List.last prems in [id] end

val extract_assumptions_from_subproof =
  let fun extract_assumptions_from_subproof (VeriT_Replay_Node {rule, concl, ...}) =
    if rule = veriT_local_input_rule then [concl] else []
  in
    map extract_assumptions_from_subproof
    #> flat
  end

fun normalized_rule_name id rule =
  (case (rule = veriT_input_rule, can (unprefix SMTLIB_Interface.assert_prefix) id) of
    (true, true) => veriT_normalized_input_rule
  | (true, _) => veriT_local_input_rule
  | _ => rule)

fun is_assm_repetition id rule =
  rule = veriT_input_rule andalso can (unprefix SMTLIB_Interface.assert_prefix) id

fun postprocess_proof ctxt step =
  let fun postprocess (Raw_VeriT_Node {id = id, rule = rule, args = args,
     prems = prems, concl = concl, subproof = subproof}) cx =
    let
      val ((concl, bounds), cx') = node_of concl cx

      val bound_vars = bound_vars_by_rule rule args

      (* postprocess conclusion *)
      val new_global_bounds = global_bound_vars_by_rule rule args
      val concl = SMTLIB_Isar.unskolemize_names ctxt concl

      val _ = (SMT_Config.veriT_msg ctxt) (fn () => @{print} ("id =", id, "concl =", concl))
      val _ = (SMT_Config.veriT_msg ctxt) (fn () => @{print} ("id =", id, "cx' =", cx',
        "bound_vars =", bound_vars))
      val bound_vars = filter_out (member ((op =)) new_global_bounds) bound_vars
      val bound_tvars =
        map (fn s => (s, the (find_type_in_formula concl s))) bound_vars
      val subproof_cx = add_bound_variables_to_ctxt concl bound_vars cx
      val (p : veriT_replay_node list list, _) =
        fold_map postprocess subproof subproof_cx

      (* postprocess assms *)
      val SMTLIB.S stripped_args = args
      val sanitized_args =
        proof_ctxt_of_rule rule stripped_args
        |> map
            (fn SMTLIB.S [SMTLIB.Key "=", x, y] => SMTLIB.S [SMTLIB.Sym "=", x, y]
            | SMTLIB.S syms =>
                SMTLIB.S (SMTLIB.Sym "and" :: map (fn x => SMTLIB.S [SMTLIB.Sym "=", x, x]) syms)
            | x => x)
      val (termified_args, _) = fold_map node_of sanitized_args subproof_cx |> apfst (map fst)
      val normalized_args = map (SMTLIB_Isar.unskolemize_names ctxt) termified_args

      val subproof_assms = proof_ctxt_of_rule rule normalized_args

      (* postprocess arguments *)
      val rule_args = args_of_rule rule stripped_args
      val (termified_args, _) = fold_map term_of rule_args subproof_cx
      val normalized_args = map (SMTLIB_Isar.unskolemize_names ctxt) termified_args
      val rule_args = normalized_args

      (* fix subproof *)
      val p = flat p
      val p = map (map_replay_prems (map (curry (op ^) id))) p
      val p = map (map_replay_id (curry (op ^) id)) p

      val extra_assms2 =
        (if rule = veriT_subproof_rule then extract_assumptions_from_subproof p else [])

      (* fix step *)
      val bound_t =
        bounds
        |> map (fn s => (s, the_default dummyT (find_type_of_free_in_formula concl s)))
      val fixed_prems =
        (if null subproof then prems else map (curry (op ^) id) prems) @
        (if is_assm_repetition id rule then [id] else []) @
        id_of_last_step p
      val normalized_rule = normalized_rule_name id rule
      val step = mk_replay_node id normalized_rule rule_args fixed_prems subproof_assms concl
        bound_t (bound_tvars, subproof_assms @ extra_assms2, p)
    in
       ([step], cx')
    end
  in postprocess step end


(*subproofs are written on multiple lines: SMTLIB can not parse then, because parentheses are
unbalanced on each line*)
fun seperate_into_steps lines =
  let
    fun count ("(" :: l) n = count l (n + 1)
      | count (")" :: l) n = count l (n - 1)
      | count (_ :: l) n = count l n
      | count [] n = n
    fun seperate (line :: l) actual_lines m =
        let val n = count (raw_explode line) 0 in
          if m + n = 0 then
            [actual_lines ^ line] :: seperate l "" 0
          else
            seperate l (actual_lines ^ line) (m + n)
        end
      | seperate [] _ 0 = []
  in
    seperate lines "" 0
  end

fun unprefix_all_syms c (SMTLIB.Sym v :: l) =
    SMTLIB.Sym (perhaps (try (unprefix c)) v) :: unprefix_all_syms c l
  | unprefix_all_syms c (SMTLIB.S l :: l') = SMTLIB.S (unprefix_all_syms c l) :: unprefix_all_syms c l'
  | unprefix_all_syms c (SMTLIB.Key v :: l) = SMTLIB.Key v :: unprefix_all_syms c l
  | unprefix_all_syms c (v :: l) = v :: unprefix_all_syms c l
  | unprefix_all_syms _ [] = []

(* VeriT adds "@" before every variable. *)
val remove_all_ats = unprefix_all_syms "@"

val linearize_proof =
  let
    fun linearize (VeriT_Replay_Node {id = id, rule = rule, args = _, prems = prems,
        proof_ctxt = proof_ctxt, concl = concl, bounds = bounds, subproof = (_, _, subproof)}) =
      let
        fun mk_prop_of_term concl =
          concl |> fastype_of concl = @{typ bool} ? curry (op $) @{term Trueprop}
        fun remove_assumption_id assumption_id prems =
          filter_out (curry (op =) assumption_id) prems
        fun inline_assumption assumption assumption_id
            (VeriT_Node {id, rule, prems, proof_ctxt, concl, bounds}) =
          mk_node id rule (remove_assumption_id assumption_id prems) proof_ctxt
            (@{const Pure.imp} $ mk_prop_of_term assumption $ mk_prop_of_term concl) bounds
        fun find_input_steps_and_inline [] = []
          | find_input_steps_and_inline
              (VeriT_Node {id = id', rule, prems, concl, bounds, ...} :: steps) =
            if rule = veriT_input_rule then
              find_input_steps_and_inline (map (inline_assumption concl id') steps)
            else
              mk_node (id') rule prems [] concl bounds :: find_input_steps_and_inline steps

        val subproof = flat (map linearize subproof)
        val subproof' = find_input_steps_and_inline subproof
      in
        subproof' @ [mk_node id rule prems proof_ctxt concl (map fst bounds)]
      end
  in linearize end

local
  fun import_proof_and_post_process typs funs lines ctxt =
    let
      val smtlib_lines_without_at =
      seperate_into_steps lines
      |> map SMTLIB.parse
      |> remove_all_ats
    in apfst flat (fold_map (fn l => postprocess_proof ctxt (parse_raw_proof_step l))
      smtlib_lines_without_at (empty_context ctxt typs funs)) end
in

fun parse typs funs lines ctxt =
  let
    val (u, env) = import_proof_and_post_process typs funs lines ctxt
    val t = flat (map linearize_proof u)
    fun node_to_step (VeriT_Node {id, rule, prems, concl, bounds, ...}) =
      mk_step id rule prems [] concl bounds
  in
    (map node_to_step t, ctxt_of env)
  end

fun parse_replay typs funs lines ctxt =
  let
    val (u, env) = import_proof_and_post_process typs funs lines ctxt
    val _ = (SMT_Config.veriT_msg ctxt) (fn () => @{print} u)
  in
    (u, ctxt_of env)
  end
end

end;