src/HOL/Tools/SMT/smt_solver.ML
author wenzelm
Sun Nov 26 21:08:32 2017 +0100 (18 months ago)
changeset 67091 1393c2340eec
parent 66661 fdab65297bd6
child 67522 9e712280cc37
permissions -rw-r--r--
more symbols;
     1 (*  Title:      HOL/Tools/SMT/smt_solver.ML
     2     Author:     Sascha Boehme, TU Muenchen
     3 
     4 SMT solvers registry and SMT tactic.
     5 *)
     6 
     7 signature SMT_SOLVER =
     8 sig
     9   (*configuration*)
    10   datatype outcome = Unsat | Sat | Unknown
    11 
    12   type parsed_proof =
    13     {outcome: SMT_Failure.failure option,
    14      fact_ids: (int * ((string * ATP_Problem_Generate.stature) * thm)) list option,
    15      atp_proof: unit -> (term, string) ATP_Proof.atp_step list}
    16 
    17   type solver_config =
    18     {name: string,
    19      class: Proof.context -> SMT_Util.class,
    20      avail: unit -> bool,
    21      command: unit -> string list,
    22      options: Proof.context -> string list,
    23      smt_options: (string * string) list,
    24      default_max_relevant: int,
    25      outcome: string -> string list -> outcome * string list,
    26      parse_proof: (Proof.context -> SMT_Translate.replay_data ->
    27        ((string * ATP_Problem_Generate.stature) * thm) list -> term list -> term -> string list ->
    28        parsed_proof) option,
    29      replay: (Proof.context -> SMT_Translate.replay_data -> string list -> thm) option}
    30 
    31   (*registry*)
    32   val add_solver: solver_config -> theory -> theory
    33   val default_max_relevant: Proof.context -> string -> int
    34 
    35   (*filter*)
    36   val smt_filter: Proof.context -> thm -> ((string * ATP_Problem_Generate.stature) * thm) list ->
    37     int -> Time.time -> parsed_proof
    38 
    39   (*tactic*)
    40   val smt_tac: Proof.context -> thm list -> int -> tactic
    41   val smt_tac': Proof.context -> thm list -> int -> tactic
    42 end;
    43 
    44 structure SMT_Solver: SMT_SOLVER =
    45 struct
    46 
    47 (* interface to external solvers *)
    48 
    49 local
    50 
    51 fun make_command command options problem_path proof_path =
    52   "(exec 2>&1;" :: map Bash.string (command () @ options) @
    53   [File.bash_path problem_path, ")", ">", File.bash_path proof_path]
    54   |> space_implode " "
    55 
    56 fun with_trace ctxt msg f x =
    57   let val _ = SMT_Config.trace_msg ctxt (fn () => msg) ()
    58   in f x end
    59 
    60 fun run ctxt name mk_cmd input =
    61   (case SMT_Config.certificates_of ctxt of
    62     NONE =>
    63       if not (SMT_Config.is_available ctxt name) then
    64         error ("The SMT solver " ^ quote name ^ " is not installed")
    65       else if Config.get ctxt SMT_Config.debug_files = "" then
    66         with_trace ctxt ("Invoking SMT solver " ^ quote name ^ " ...") (Cache_IO.run mk_cmd) input
    67       else
    68         let
    69           val base_path = Path.explode (Config.get ctxt SMT_Config.debug_files)
    70           val in_path = Path.ext "smt_in" base_path
    71           val out_path = Path.ext "smt_out" base_path
    72         in Cache_IO.raw_run mk_cmd input in_path out_path end
    73   | SOME certs =>
    74       (case Cache_IO.lookup certs input of
    75         (NONE, key) =>
    76           if Config.get ctxt SMT_Config.read_only_certificates then
    77             error ("Bad certificate cache: missing certificate")
    78           else
    79             Cache_IO.run_and_cache certs key mk_cmd input
    80       | (SOME output, _) =>
    81           with_trace ctxt ("Using cached certificate from " ^
    82             Path.print (Cache_IO.cache_path_of certs) ^ " ...") I output))
    83 
    84 (* Z3 returns 1 if "get-proof" or "get-model" fails. veriT returns 255. *)
    85 val normal_return_codes = [0, 1, 255]
    86 
    87 fun run_solver ctxt name mk_cmd input =
    88   let
    89     fun pretty tag lines = Pretty.string_of (Pretty.big_list tag (map Pretty.str lines))
    90 
    91     val _ = SMT_Config.trace_msg ctxt (pretty "Problem:" o split_lines) input
    92 
    93     val {redirected_output = res, output = err, return_code} =
    94       SMT_Config.with_timeout ctxt (run ctxt name mk_cmd) input
    95     val _ = SMT_Config.trace_msg ctxt (pretty "Solver:") err
    96 
    97     val output = fst (take_suffix (equal "") res)
    98     val _ = SMT_Config.trace_msg ctxt (pretty "Result:") output
    99 
   100     val _ = member (op =) normal_return_codes return_code orelse
   101       raise SMT_Failure.SMT (SMT_Failure.Abnormal_Termination return_code)
   102   in output end
   103 
   104 fun trace_assms ctxt =
   105   SMT_Config.trace_msg ctxt (Pretty.string_of o
   106     Pretty.big_list "Assertions:" o map (Thm.pretty_thm ctxt o snd))
   107 
   108 fun trace_replay_data ({context = ctxt, typs, terms, ...} : SMT_Translate.replay_data) =
   109   let
   110     fun pretty_eq n p = Pretty.block [Pretty.str n, Pretty.str " = ", p]
   111     fun p_typ (n, T) = pretty_eq n (Syntax.pretty_typ ctxt T)
   112     fun p_term (n, t) = pretty_eq n (Syntax.pretty_term ctxt t)
   113   in
   114     SMT_Config.trace_msg ctxt (fn () =>
   115       Pretty.string_of (Pretty.big_list "Names:" [
   116         Pretty.big_list "sorts:" (map p_typ (Symtab.dest typs)),
   117         Pretty.big_list "functions:" (map p_term (Symtab.dest terms))])) ()
   118   end
   119 
   120 in
   121 
   122 fun invoke name command smt_options ithms ctxt =
   123   let
   124     val options = SMT_Config.solver_options_of ctxt
   125     val comments = [space_implode " " options]
   126 
   127     val (str, replay_data as {context = ctxt', ...}) =
   128       ithms
   129       |> tap (trace_assms ctxt)
   130       |> SMT_Translate.translate ctxt smt_options comments
   131       ||> tap trace_replay_data
   132   in (run_solver ctxt' name (make_command command options) str, replay_data) end
   133 
   134 end
   135 
   136 
   137 (* configuration *)
   138 
   139 datatype outcome = Unsat | Sat | Unknown
   140 
   141 type parsed_proof =
   142   {outcome: SMT_Failure.failure option,
   143    fact_ids: (int * ((string * ATP_Problem_Generate.stature) * thm)) list option,
   144    atp_proof: unit -> (term, string) ATP_Proof.atp_step list}
   145 
   146 type solver_config =
   147   {name: string,
   148    class: Proof.context -> SMT_Util.class,
   149    avail: unit -> bool,
   150    command: unit -> string list,
   151    options: Proof.context -> string list,
   152    smt_options: (string * string) list,
   153    default_max_relevant: int,
   154    outcome: string -> string list -> outcome * string list,
   155    parse_proof: (Proof.context -> SMT_Translate.replay_data ->
   156      ((string * ATP_Problem_Generate.stature) * thm) list -> term list -> term -> string list ->
   157      parsed_proof) option,
   158    replay: (Proof.context -> SMT_Translate.replay_data -> string list -> thm) option}
   159 
   160 
   161 (* check well-sortedness *)
   162 
   163 val has_topsort = Term.exists_type (Term.exists_subtype (fn
   164     TFree (_, []) => true
   165   | TVar (_, []) => true
   166   | _ => false))
   167 
   168 (* top sorts cause problems with atomization *)
   169 fun check_topsort ctxt thm =
   170   if has_topsort (Thm.prop_of thm) then (SMT_Normalize.drop_fact_warning ctxt thm; TrueI) else thm
   171 
   172 
   173 (* registry *)
   174 
   175 type solver_info = {
   176   command: unit -> string list,
   177   smt_options: (string * string) list,
   178   default_max_relevant: int,
   179   parse_proof: Proof.context -> SMT_Translate.replay_data ->
   180     ((string * ATP_Problem_Generate.stature) * thm) list -> term list -> term -> string list ->
   181     parsed_proof,
   182   replay: Proof.context -> SMT_Translate.replay_data -> string list -> thm}
   183 
   184 structure Solvers = Generic_Data
   185 (
   186   type T = solver_info Symtab.table
   187   val empty = Symtab.empty
   188   val extend = I
   189   fun merge data = Symtab.merge (K true) data
   190 )
   191 
   192 local
   193   fun parse_proof outcome parse_proof0 outer_ctxt replay_data xfacts prems concl output =
   194     (case outcome output of
   195       (Unsat, lines) =>
   196         (case parse_proof0 of
   197           SOME pp => pp outer_ctxt replay_data xfacts prems concl lines
   198         | NONE => {outcome = NONE, fact_ids = NONE, atp_proof = K []})
   199     | (result, _) => raise SMT_Failure.SMT (SMT_Failure.Counterexample (result = Sat)))
   200 
   201   fun replay outcome replay0 oracle outer_ctxt
   202       (replay_data as {context = ctxt, ...} : SMT_Translate.replay_data) output =
   203     (case outcome output of
   204       (Unsat, lines) =>
   205         if Config.get ctxt SMT_Config.oracle then
   206           oracle ()
   207         else
   208           (case replay0 of
   209             SOME replay => replay outer_ctxt replay_data lines
   210           | NONE => error "No proof reconstruction for solver -- \
   211             \declare [[smt_oracle]] to allow oracle")
   212     | (result, _) => raise SMT_Failure.SMT (SMT_Failure.Counterexample (result = Sat)))
   213 
   214   val cfalse = Thm.cterm_of @{context} @{prop False}
   215 in
   216 
   217 fun add_solver ({name, class, avail, command, options, smt_options, default_max_relevant, outcome,
   218     parse_proof = parse_proof0, replay = replay0} : solver_config) =
   219   let
   220     fun solver oracle = {
   221       command = command,
   222       smt_options = smt_options,
   223       default_max_relevant = default_max_relevant,
   224       parse_proof = parse_proof (outcome name) parse_proof0,
   225       replay = replay (outcome name) replay0 oracle}
   226 
   227     val info = {name = name, class = class, avail = avail, options = options}
   228   in
   229     Thm.add_oracle (Binding.name name, K cfalse) #-> (fn (_, oracle) =>
   230     Context.theory_map (Solvers.map (Symtab.update_new (name, solver oracle)))) #>
   231     Context.theory_map (SMT_Config.add_solver info)
   232   end
   233 
   234 end
   235 
   236 fun get_info ctxt name = the (Symtab.lookup (Solvers.get (Context.Proof ctxt)) name)
   237 
   238 fun name_and_info_of ctxt =
   239   let val name = SMT_Config.solver_of ctxt
   240   in (name, get_info ctxt name) end
   241 
   242 val default_max_relevant = #default_max_relevant oo get_info
   243 
   244 fun apply_solver_and_replay ctxt thms0 =
   245   let
   246     val thms = map (check_topsort ctxt) thms0
   247     val (name, {command, smt_options, replay, ...}) = name_and_info_of ctxt
   248     val (output, replay_data) =
   249       invoke name command smt_options (SMT_Normalize.normalize ctxt thms) ctxt
   250   in replay ctxt replay_data output end
   251 
   252 
   253 (* filter *)
   254 
   255 fun smt_filter ctxt0 goal xfacts i time_limit =
   256   let
   257     val ctxt = ctxt0 |> Config.put SMT_Config.timeout (Time.toReal time_limit)
   258 
   259     val ({context = ctxt, prems, concl, ...}, _) = Subgoal.focus ctxt i NONE goal
   260     fun negate ct = Thm.dest_comb ct ||> Thm.apply @{cterm Not} |-> Thm.apply
   261     val cprop =
   262       (case try negate (Thm.rhs_of (SMT_Normalize.atomize_conv ctxt concl)) of
   263         SOME ct => ct
   264       | NONE => raise SMT_Failure.SMT (SMT_Failure.Other_Failure "cannot atomize goal"))
   265 
   266     val conjecture = Thm.assume cprop
   267     val facts = map snd xfacts
   268     val thms = conjecture :: prems @ facts
   269     val thms' = map (check_topsort ctxt) thms
   270 
   271     val (name, {command, smt_options, parse_proof, ...}) = name_and_info_of ctxt
   272     val (output, replay_data) =
   273       invoke name command smt_options (SMT_Normalize.normalize ctxt thms') ctxt
   274   in
   275     parse_proof ctxt replay_data xfacts (map Thm.prop_of prems) (Thm.term_of concl) output
   276   end
   277   handle SMT_Failure.SMT fail => {outcome = SOME fail, fact_ids = NONE, atp_proof = K []}
   278 
   279 
   280 (* SMT tactic *)
   281 
   282 local
   283   fun str_of ctxt fail =
   284     "Solver " ^ SMT_Config.solver_of ctxt ^ ": " ^ SMT_Failure.string_of_failure fail
   285 
   286   fun safe_solve ctxt facts = SOME (apply_solver_and_replay ctxt facts)
   287     handle
   288       SMT_Failure.SMT (fail as SMT_Failure.Counterexample _) =>
   289         (SMT_Config.verbose_msg ctxt (str_of ctxt) fail; NONE)
   290     | SMT_Failure.SMT (fail as SMT_Failure.Time_Out) =>
   291         error ("SMT: Solver " ^ quote (SMT_Config.solver_of ctxt) ^ ": " ^
   292           SMT_Failure.string_of_failure fail ^ " (setting the " ^
   293           "configuration option " ^ quote (Config.name_of SMT_Config.timeout) ^ " might help)")
   294     | SMT_Failure.SMT fail => error (str_of ctxt fail)
   295 
   296   fun resolve ctxt (SOME thm) = resolve_tac ctxt [thm] 1
   297     | resolve _ NONE = no_tac
   298 
   299   fun tac prove ctxt rules =
   300     CONVERSION (SMT_Normalize.atomize_conv ctxt)
   301     THEN' resolve_tac ctxt @{thms ccontr}
   302     THEN' SUBPROOF (fn {context = ctxt', prems, ...} =>
   303       resolve ctxt' (prove ctxt' (rules @ prems))) ctxt
   304 in
   305 
   306 val smt_tac = tac safe_solve
   307 val smt_tac' = tac (SOME oo apply_solver_and_replay)
   308 
   309 end
   310 
   311 end;