(*  Title:      HOL/Tools/Sledgehammer/sledgehammer_mash.ML

    Author:     Jasmin Blanchette, TU Muenchen

    Author:     Cezary Kaliszyk, University of Innsbruck

Sledgehammer's machine-learning-based relevance filter (MaSh).

*)

signature SLEDGEHAMMER_MASH =

sig

  type stature = ATP_Problem_Generate.stature

  type raw_fact = Sledgehammer_Fact.raw_fact

  type fact = Sledgehammer_Fact.fact

  type fact_override = Sledgehammer_Fact.fact_override

  type params = Sledgehammer_Prover.params

  type prover_result = Sledgehammer_Prover.prover_result

  val trace : bool Config.T

  val duplicates : bool Config.T

  val MePoN : string

  val MaShN : string

  val MeShN : string

  val mepoN : string

  val mashN : string

  val meshN : string

  val unlearnN : string

  val learn_isarN : string

  val learn_proverN : string

  val relearn_isarN : string

  val relearn_proverN : string

  val fact_filters : string list

  val encode_str : string -> string

  val encode_strs : string list -> string

  val decode_str : string -> string

  val decode_strs : string -> string list

  datatype mash_algorithm =

    MaSh_NB

  | MaSh_kNN

  | MaSh_NB_kNN

  | MaSh_NB_Ext

  | MaSh_kNN_Ext

  val is_mash_enabled : unit -> bool

  val the_mash_algorithm : unit -> mash_algorithm

  val mesh_facts : ('a * 'a -> bool) -> int -> (real * (('a * real) list * 'a list)) list -> 'a list

  val nickname_of_thm : thm -> string

  val find_suggested_facts : Proof.context -> ('b * thm) list -> string list -> ('b * thm) list

  val crude_thm_ord : thm * thm -> order

  val thm_less : thm * thm -> bool

  val goal_of_thm : theory -> thm -> thm

  val run_prover_for_mash : Proof.context -> params -> string -> string -> fact list -> thm ->

    prover_result

  val features_of : Proof.context -> theory -> stature -> term list -> string list

  val trim_dependencies : string list -> string list option

  val isar_dependencies_of : string Symtab.table * string Symtab.table -> thm -> string list option

  val prover_dependencies_of : Proof.context -> params -> string -> int -> raw_fact list ->

    string Symtab.table * string Symtab.table -> thm -> bool * string list

  val attach_parents_to_facts : ('a * thm) list -> ('a * thm) list ->

    (string list * ('a * thm)) list

  val num_extra_feature_facts : int

  val extra_feature_factor : real

  val weight_facts_smoothly : 'a list -> ('a * real) list

  val weight_facts_steeply : 'a list -> ('a * real) list

  val find_mash_suggestions : Proof.context -> int -> string list -> ('a * thm) list ->

    ('a * thm) list -> ('a * thm) list -> ('a * thm) list * ('a * thm) list

  val mash_suggested_facts : Proof.context -> theory -> params -> int -> term list -> term ->

    raw_fact list -> fact list * fact list

  val mash_unlearn : unit -> unit

  val mash_learn_proof : Proof.context -> params -> term -> ('a * thm) list -> thm list -> unit

  val mash_learn_facts : Proof.context -> params -> string -> int -> bool -> Time.time ->

    raw_fact list -> string

  val mash_learn : Proof.context -> params -> fact_override -> thm list -> bool -> unit

  val mash_can_suggest_facts : Proof.context -> bool

  val generous_max_suggestions : int -> int

  val mepo_weight : real

  val mash_weight : real

  val relevant_facts : Proof.context -> params -> string -> int -> fact_override -> term list ->

    term -> raw_fact list -> (string * fact list) list

  val kill_learners : unit -> unit

  val running_learners : unit -> unit

end;

structure Sledgehammer_MaSh : SLEDGEHAMMER_MASH =

struct

open ATP_Util

open ATP_Problem_Generate

open Sledgehammer_Util

open Sledgehammer_Fact

open Sledgehammer_Prover

open Sledgehammer_Prover_Minimize

open Sledgehammer_MePo

val trace = Attrib.setup_config_bool @{binding sledgehammer_mash_trace} (K false)

val duplicates = Attrib.setup_config_bool @{binding sledgehammer_fact_duplicates} (K false)

fun trace_msg ctxt msg = if Config.get ctxt trace then tracing (msg ()) else ()

fun gen_eq_thm ctxt = if Config.get ctxt duplicates then Thm.eq_thm_strict else Thm.eq_thm_prop

val MePoN = "MePo"

val MaShN = "MaSh"

val MeShN = "MeSh"

val mepoN = "mepo"

val mashN = "mash"

val meshN = "mesh"

val fact_filters = [meshN, mepoN, mashN]

val unlearnN = "unlearn"

val learn_isarN = "learn_isar"

val learn_proverN = "learn_prover"

val relearn_isarN = "relearn_isar"

val relearn_proverN = "relearn_prover"

fun map_array_at ary f i = Array.update (ary, i, f (Array.sub (ary, i)))

type xtab = int * int Symtab.table

val empty_xtab = (0, Symtab.empty)

fun add_to_xtab key (next, tab) = (next + 1, Symtab.update_new (key, next) tab)

fun maybe_add_to_xtab key = perhaps (try (add_to_xtab key))

fun state_file () = Path.expand (Path.explode "$ISABELLE_HOME_USER/mash_state")

val remove_state_file = try File.rm o state_file

datatype mash_algorithm =

  MaSh_NB

| MaSh_kNN

| MaSh_NB_kNN

| MaSh_NB_Ext

| MaSh_kNN_Ext

(* TODO: eliminate "MASH" environment variable after Isabelle2014 release *)

fun mash_algorithm () =

  let val flag1 = Options.default_string @{system_option MaSh} in

    (case if flag1 <> "none" (* default *) then flag1 else getenv "MASH" of

      "yes" => SOME MaSh_NB_kNN

    | "sml" => SOME MaSh_NB_kNN

    | "nb" => SOME MaSh_NB

    | "knn" => SOME MaSh_kNN

    | "nb_knn" => SOME MaSh_NB_kNN

    | "nb_ext" => SOME MaSh_NB_Ext

    | "knn_ext" => SOME MaSh_kNN_Ext

    | "" => NONE

    | algorithm => (warning ("Unknown MaSh algorithm: " ^ quote algorithm ^ "."); NONE))

  end

val is_mash_enabled = is_some o mash_algorithm

val the_mash_algorithm = the_default MaSh_NB_kNN o mash_algorithm

fun scaled_avg [] = 0

  | scaled_avg xs = Real.ceil (100000000.0 * fold (curry (op +)) xs 0.0) div length xs

fun avg [] = 0.0

  | avg xs = fold (curry (op +)) xs 0.0 / Real.fromInt (length xs)

fun normalize_scores _ [] = []

  | normalize_scores max_facts xs =

    map (apsnd (curry Real.* (1.0 / avg (map snd (take max_facts xs))))) xs

fun mesh_facts fact_eq max_facts [(_, (sels, unks))] =

    distinct fact_eq (map fst (take max_facts sels) @ take (max_facts - length sels) unks)

  | mesh_facts fact_eq max_facts mess =

    let

      val mess = mess |> map (apsnd (apfst (normalize_scores max_facts)))

      fun score_in fact (global_weight, (sels, unks)) =

        let val score_at = try (nth sels) #> Option.map (fn (_, score) => global_weight * score) in

          (case find_index (curry fact_eq fact o fst) sels of

            ~1 => if member fact_eq unks fact then NONE else SOME 0.0

          | rank => score_at rank)

        end

      fun weight_of fact = mess |> map_filter (score_in fact) |> scaled_avg

    in

      fold (union fact_eq o map fst o take max_facts o fst o snd) mess []

      |> map (`weight_of) |> sort (int_ord o pairself fst o swap)

      |> map snd |> take max_facts

    end

fun smooth_weight_of_fact rank = Math.pow (1.3, 15.5 - 0.2 * Real.fromInt rank) + 15.0 (* FUDGE *)

fun steep_weight_of_fact rank = Math.pow (0.62, log2 (Real.fromInt (rank + 1))) (* FUDGE *)

fun weight_facts_smoothly facts = facts ~~ map smooth_weight_of_fact (0 upto length facts - 1)

fun weight_facts_steeply facts = facts ~~ map steep_weight_of_fact (0 upto length facts - 1)

fun rev_sort_array_prefix cmp bnd a =

  let

    exception BOTTOM of int

    val al = Array.length a

    fun maxson l i =

      let val i31 = i + i + i + 1 in

        if i31 + 2 < l then

          let val x = Unsynchronized.ref i31 in

            if cmp (Array.sub (a, i31), Array.sub (a, i31 + 1)) = LESS then x := i31 + 1 else ();

            if cmp (Array.sub (a, !x), Array.sub (a, i31 + 2)) = LESS then x := i31 + 2 else ();

            !x

          end

        else

          if i31 + 1 < l andalso cmp (Array.sub (a, i31), Array.sub (a, i31 + 1)) = LESS

          then i31 + 1 else if i31 < l then i31 else raise BOTTOM i

      end

    fun trickledown l i e =

      let val j = maxson l i in

        if cmp (Array.sub (a, j), e) = GREATER then

          (Array.update (a, i, Array.sub (a, j)); trickledown l j e)

        else

          Array.update (a, i, e)

      end

    fun trickle l i e = trickledown l i e handle BOTTOM i => Array.update (a, i, e)

    fun bubbledown l i =

      let val j = maxson l i in

        Array.update (a, i, Array.sub (a, j));

        bubbledown l j

      end

    fun bubble l i = bubbledown l i handle BOTTOM i => i

    fun trickleup i e =

      let val father = (i - 1) div 3 in

        if cmp (Array.sub (a, father), e) = LESS then

          (Array.update (a, i, Array.sub (a, father));

           if father > 0 then trickleup father e else Array.update (a, 0, e))

        else

          Array.update (a, i, e)

      end

    fun for i = if i < 0 then () else (trickle al i (Array.sub (a, i)); for (i - 1))

    fun for2 i =

      if i < Integer.max 2 (al - bnd) then

        ()

      else

        let val e = Array.sub (a, i) in

          Array.update (a, i, Array.sub (a, 0));

          trickleup (bubble i 0) e;

          for2 (i - 1)

        end

  in

    for (((al + 1) div 3) - 1);

    for2 (al - 1);

    if al > 1 then

      let val e = Array.sub (a, 1) in

        Array.update (a, 1, Array.sub (a, 0));

        Array.update (a, 0, e)

      end

    else

      ()

  end

fun rev_sort_list_prefix cmp bnd xs =

  let val ary = Array.fromList xs in

    rev_sort_array_prefix cmp bnd ary;

    Array.foldr (op ::) [] ary

  end

(*** Isabelle-agnostic machine learning ***)

structure MaSh =

struct

fun select_visible_facts big_number recommends =

  List.app (fn at =>

    let val (j, ov) = Array.sub (recommends, at) in

      Array.update (recommends, at, (j, big_number + ov))

    end)

fun wider_array_of_vector init vec =

  let val ary = Array.array init in

    Array.copyVec {src = vec, dst = ary, di = 0};

    ary

  end

val nb_def_prior_weight = 1000 (* FUDGE *)

fun learn_facts (tfreq0, sfreq0, dffreq0) num_facts0 num_facts num_feats depss featss =

  let

    val tfreq = wider_array_of_vector (num_facts, 0) tfreq0

    val sfreq = wider_array_of_vector (num_facts, Inttab.empty) sfreq0

    val dffreq = wider_array_of_vector (num_feats, 0) dffreq0

    fun learn_one th feats deps =

      let

        fun add_th weight t =

          let

            val im = Array.sub (sfreq, t)

            fun fold_fn s = Inttab.map_default (s, 0) (Integer.add weight)

          in

            map_array_at tfreq (Integer.add weight) t;

            Array.update (sfreq, t, fold fold_fn feats im)

          end

        val add_sym = map_array_at dffreq (Integer.add 1)

      in

        add_th nb_def_prior_weight th;

        List.app (add_th 1) deps;

        List.app add_sym feats

      end

    fun for i =

      if i = num_facts then ()

      else (learn_one i (Vector.sub (featss, i)) (Vector.sub (depss, i)); for (i + 1))

  in

    for num_facts0;

    (Array.vector tfreq, Array.vector sfreq, Array.vector dffreq)

  end

fun naive_bayes (tfreq, sfreq, dffreq) num_facts max_suggs visible_facts goal_feats =

  let

    val tau = 0.2 (* FUDGE *)

    val pos_weight = 5.0 (* FUDGE *)

    val def_val = ~18.0 (* FUDGE *)

    val init_val = 30.0 (* FUDGE *)

    val ln_afreq = Math.ln (Real.fromInt num_facts)

    val idf = Vector.map (fn i => ln_afreq - Math.ln (Real.fromInt i)) dffreq

    fun tfidf feat = Vector.sub (idf, feat)

    fun log_posterior i =

      let

        val tfreq = Real.fromInt (Vector.sub (tfreq, i))

        fun add_feat (f, fw0) (res, sfh) =

          (case Inttab.lookup sfh f of

            SOME sf =>

            (res + fw0 * tfidf f * Math.ln (pos_weight * Real.fromInt sf / tfreq),

             Inttab.delete f sfh)

          | NONE => (res + fw0 * tfidf f * def_val, sfh))

        val (res, sfh) = fold add_feat goal_feats (init_val * Math.ln tfreq, Vector.sub (sfreq, i))

        fun fold_sfh (f, sf) sow =

          sow + tfidf f * Math.ln (1.0 + (1.0 - Real.fromInt sf) / tfreq)

        val sum_of_weights = Inttab.fold fold_sfh sfh 0.0

      in

        res + tau * sum_of_weights

      end

    val posterior = Array.tabulate (num_facts, (fn j => (j, log_posterior j)))

    fun ret at acc =

      if at = num_facts then acc else ret (at + 1) (Array.sub (posterior, at) :: acc)

  in

    select_visible_facts 100000.0 posterior visible_facts;

    rev_sort_array_prefix (Real.compare o pairself snd) max_suggs posterior;

    ret (Integer.max 0 (num_facts - max_suggs)) []

  end

val initial_number_of_nearest_neighbors = 1

fun k_nearest_neighbors dffreq num_facts num_feats depss featss max_suggs visible_facts goal_feats =

  let

    exception EXIT of unit

    val ln_afreq = Math.ln (Real.fromInt num_facts)

    fun tfidf feat = ln_afreq - Math.ln (Real.fromInt (Vector.sub (dffreq, feat)))

    val overlaps_sqr = Array.tabulate (num_facts, rpair 0.0)

    val feat_facts = Array.array (num_feats, [])

    val _ = Vector.foldl (fn (feats, fact) =>

      (List.app (map_array_at feat_facts (cons fact)) feats; fact + 1)) 0 featss

    fun do_feat (s, sw0) =

      let

        val sw = sw0 * tfidf s

        val w6 = Math.pow (sw, 6.0)

        fun inc_overlap j =

          let val (_, ov) = Array.sub (overlaps_sqr, j) in

            Array.update (overlaps_sqr, j, (j, w6 + ov))

          end

      in

        List.app inc_overlap (Array.sub (feat_facts, s))

      end

    val _ = List.app do_feat goal_feats

    val _ = rev_sort_array_prefix (Real.compare o pairself snd) num_facts overlaps_sqr

    val no_recommends = Unsynchronized.ref 0

    val recommends = Array.tabulate (num_facts, rpair 0.0)

    val age = Unsynchronized.ref 500000000.0

    fun inc_recommend v j =

      let val (_, ov) = Array.sub (recommends, j) in

        if ov <= 0.0 then

          (no_recommends := !no_recommends + 1; Array.update (recommends, j, (j, !age + ov)))

        else Array.update (recommends, j, (j, v + ov))

      end

    val k = Unsynchronized.ref 0

    fun do_k k =

      if k >= num_facts then

        raise EXIT ()

      else

        let

          val deps_factor = 2.7 (* FUDGE *)

          val (j, o2) = Array.sub (overlaps_sqr, num_facts - k - 1)

          val _ = inc_recommend o2 j

          val ds = Vector.sub (depss, j)

          val l = Real.fromInt (length ds)

        in

          List.app (inc_recommend (deps_factor * o2 / l)) ds

        end

    fun while1 () =

      if !k = initial_number_of_nearest_neighbors then () else (do_k (!k); k := !k + 1; while1 ())

      handle EXIT () => ()

    fun while2 () =

      if !no_recommends >= max_suggs then ()

      else (do_k (!k); k := !k + 1; age := !age - 10000.0; while2 ())

      handle EXIT () => ()

    fun ret acc at =

      if at = num_facts then acc else ret (Array.sub (recommends, at) :: acc) (at + 1)

  in

    while1 ();

    while2 ();

    select_visible_facts 1000000000.0 recommends visible_facts;

    rev_sort_array_prefix (Real.compare o pairself snd) max_suggs recommends;

    ret [] (Integer.max 0 (num_facts - max_suggs))

  end

(* experimental *)

fun external_tool tool max_suggs learns goal_feats =

  let

    val ser = string_of_int (serial ()) (* poor person's attempt at thread-safety *)

    val ocs = TextIO.openOut ("adv_syms" ^ ser)

    val ocd = TextIO.openOut ("adv_deps" ^ ser)

    val ocq = TextIO.openOut ("adv_seq" ^ ser)

    val occ = TextIO.openOut ("adv_conj" ^ ser)

    fun os oc s = TextIO.output (oc, s)

    fun ol _ _ _ [] = ()

      | ol _ f _ [e] = f e

      | ol oc f sep (h :: t) = (f h; os oc sep; ol oc f sep t)

    fun do_learn (name, feats, deps) =

      (os ocs name; os ocs ":"; ol ocs (os ocs o quote) ", " feats; os ocs "\n";

       os ocd name; os ocd ":"; ol ocd (os ocd) " " deps; os ocd "\n"; os ocq name; os ocq "\n")

    fun forkexec no =

      let

        val cmd =

          "~/misc/" ^ tool ^ " adv_syms" ^ ser ^ " adv_deps" ^ ser ^ " " ^ string_of_int no ^

          " adv_seq" ^ ser ^ " < adv_conj" ^ ser

      in

        fst (Isabelle_System.bash_output cmd)

        |> space_explode " "

        |> filter_out (curry (op =) "")

      end

  in

    (List.app do_learn learns; ol occ (os occ o quote) ", " (map fst goal_feats);

     TextIO.closeOut ocs; TextIO.closeOut ocd; TextIO.closeOut ocq; TextIO.closeOut occ;

     forkexec max_suggs)

  end

val k_nearest_neighbors_ext =

  external_tool ("newknn/knn" ^ " " ^ string_of_int initial_number_of_nearest_neighbors)

val naive_bayes_ext = external_tool "predict/nbayes"

fun query_external ctxt algorithm max_suggs learns goal_feats =

  (trace_msg ctxt (fn () => "MaSh query external " ^ commas (map fst goal_feats));

   (case algorithm of

     MaSh_NB_Ext => naive_bayes_ext max_suggs learns goal_feats

   | MaSh_kNN_Ext => k_nearest_neighbors_ext max_suggs learns goal_feats))

fun query_internal ctxt algorithm num_facts num_feats (fact_names, featss, depss)

    (freqs as (_, _, dffreq)) visible_facts max_suggs goal_feats int_goal_feats =

  let

    fun nb () =

      naive_bayes freqs num_facts max_suggs visible_facts int_goal_feats

      |> map fst

    fun knn () =

      k_nearest_neighbors dffreq num_facts num_feats depss featss max_suggs visible_facts

        int_goal_feats

      |> map fst

  in

    (trace_msg ctxt (fn () => "MaSh query internal " ^ commas (map fst goal_feats) ^ " from {" ^

       elide_string 1000 (space_implode " " (Vector.foldr (op ::) [] fact_names)) ^ "}");

     (case algorithm of

       MaSh_NB => nb ()

     | MaSh_kNN => knn ()

     | MaSh_NB_kNN =>

       mesh_facts (op =) max_suggs

         [(0.5 (* FUDGE *), (weight_facts_steeply (nb ()), [])),

          (0.5 (* FUDGE *), (weight_facts_steeply (knn ()), []))])

     |> map (curry Vector.sub fact_names))

   end

end;

(*** Persistent, stringly-typed state ***)

fun meta_char c =

  if Char.isAlphaNum c orelse c = #"_" orelse c = #"." orelse c = #"(" orelse c = #")" orelse

     c = #"," then

    String.str c

  else

    (* fixed width, in case more digits follow *)

    "%" ^ stringN_of_int 3 (Char.ord c)

fun unmeta_chars accum [] = String.implode (rev accum)

  | unmeta_chars accum (#"%" :: d1 :: d2 :: d3 :: cs) =

    (case Int.fromString (String.implode [d1, d2, d3]) of

      SOME n => unmeta_chars (Char.chr n :: accum) cs

    | NONE => "" (* error *))

  | unmeta_chars _ (#"%" :: _) = "" (* error *)

  | unmeta_chars accum (c :: cs) = unmeta_chars (c :: accum) cs

val encode_str = String.translate meta_char

val decode_str = String.explode #> unmeta_chars []

val encode_strs = map encode_str #> space_implode " "

val decode_strs = space_explode " " #> map decode_str

datatype proof_kind = Isar_Proof | Automatic_Proof | Isar_Proof_wegen_Prover_Flop

fun str_of_proof_kind Isar_Proof = "i"

  | str_of_proof_kind Automatic_Proof = "a"

  | str_of_proof_kind Isar_Proof_wegen_Prover_Flop = "x"

fun proof_kind_of_str "a" = Automatic_Proof

  | proof_kind_of_str "x" = Isar_Proof_wegen_Prover_Flop

  | proof_kind_of_str _ (* "i" *) = Isar_Proof

fun add_edge_to name parent =

  Graph.default_node (parent, (Isar_Proof, [], []))

  #> Graph.add_edge (parent, name)

fun add_node kind name parents feats deps (access_G, (fact_xtab, feat_xtab), learns) =

  ((Graph.new_node (name, (kind, feats, deps)) access_G

    handle Graph.DUP _ => Graph.map_node name (K (kind, feats, deps)) access_G)

   |> fold (add_edge_to name) parents,

  (add_to_xtab name fact_xtab, fold maybe_add_to_xtab feats feat_xtab),

  (name, feats, deps) :: learns)

fun try_graph ctxt when def f =

  f ()

  handle

    Graph.CYCLES (cycle :: _) =>

    (trace_msg ctxt (fn () => "Cycle involving " ^ commas cycle ^ " when " ^ when); def)

  | Graph.DUP name =>

    (trace_msg ctxt (fn () => "Duplicate fact " ^ quote name ^ " when " ^ when); def)

  | Graph.UNDEF name =>

    (trace_msg ctxt (fn () => "Unknown fact " ^ quote name ^ " when " ^ when); def)

  | exn =>

    if Exn.is_interrupt exn then

      reraise exn

    else

      (trace_msg ctxt (fn () => "Internal error when " ^ when ^ ":\n" ^ Runtime.exn_message exn);

       def)

fun graph_info G =

  string_of_int (length (Graph.keys G)) ^ " node(s), " ^

  string_of_int (fold (Integer.add o length o snd) (Graph.dest G) 0) ^ " edge(s), " ^

  string_of_int (length (Graph.maximals G)) ^ " maximal"

type ffds = string vector * int list vector * int list vector

type freqs = int vector * int Inttab.table vector * int vector

type mash_state =

  {access_G : (proof_kind * string list * string list) Graph.T,

   xtabs : xtab * xtab,

   ffds : ffds,

   freqs : freqs,

   dirty_facts : string list option}

val empty_xtabs = (empty_xtab, empty_xtab)

val empty_ffds = (Vector.fromList [], Vector.fromList [], Vector.fromList []) : ffds

val empty_freqs = (Vector.fromList [], Vector.fromList [], Vector.fromList []) : freqs

val empty_state =

  {access_G = Graph.empty,

   xtabs = empty_xtabs,

   ffds = empty_ffds,

   freqs = empty_freqs,

   dirty_facts = SOME []} : mash_state

fun recompute_ffds_freqs_from_learns (learns : (string * string list * string list) list)

    ((num_facts, fact_tab), (num_feats, feat_tab)) num_facts0 (fact_names0, featss0, depss0) freqs0 =

  let

    val fact_names = Vector.concat [fact_names0, Vector.fromList (map #1 learns)]

    val featss = Vector.concat [featss0,

      Vector.fromList (map (map_filter (Symtab.lookup feat_tab) o #2) learns)]

    val depss = Vector.concat [depss0,

      Vector.fromList (map (map_filter (Symtab.lookup fact_tab) o #3) learns)]

  in

    ((fact_names, featss, depss),

     MaSh.learn_facts freqs0 num_facts0 num_facts num_feats depss featss)

  end

fun reorder_learns (num_facts, fact_tab) learns =

  let val ary = Array.array (num_facts, ("", [], [])) in

    List.app (fn learn as (fact, _, _) =>

        Array.update (ary, the (Symtab.lookup fact_tab fact), learn))

      learns;

    Array.foldr (op ::) [] ary

  end

fun recompute_ffds_freqs_from_access_G access_G (xtabs as (fact_xtab, _)) =

  let

    val learns =

      Graph.schedule (fn _ => fn (fact, (_, feats, deps)) => (fact, feats, deps)) access_G

      |> reorder_learns fact_xtab

  in

    recompute_ffds_freqs_from_learns learns xtabs 0 empty_ffds empty_freqs

  end

local

val version = "*** MaSh version 20140625 ***"

exception FILE_VERSION_TOO_NEW of unit

fun extract_node line =

  (case space_explode ":" line of

    [head, tail] =>

    (case (space_explode " " head, map (unprefix " ") (space_explode ";" tail)) of

      ([kind, name], [parents, feats, deps]) =>

      SOME (proof_kind_of_str kind, decode_str name, decode_strs parents, decode_strs feats,

        decode_strs deps)

    | _ => NONE)

  | _ => NONE)

fun load_state ctxt (time_state as (memory_time, _)) =

  let val path = state_file () in

    (case try OS.FileSys.modTime (Path.implode path) of

      NONE => time_state

    | SOME disk_time =>

      if Time.>= (memory_time, disk_time) then

        time_state

      else

        (disk_time,

         (case try File.read_lines path of

           SOME (version' :: node_lines) =>

           let

             fun extract_line_and_add_node line =

               (case extract_node line of

                 NONE => I (* should not happen *)

               | SOME (kind, name, parents, feats, deps) => add_node kind name parents feats deps)

             val empty_G_etc = (Graph.empty, empty_xtabs, [])

             val (access_G, xtabs, rev_learns) =

               (case string_ord (version', version) of

                 EQUAL =>

                 try_graph ctxt "loading state" empty_G_etc

                   (fn () => fold extract_line_and_add_node node_lines empty_G_etc)

               | LESS => (remove_state_file (); empty_G_etc) (* cannot parse old file *)

               | GREATER => raise FILE_VERSION_TOO_NEW ())

             val (ffds, freqs) =

               recompute_ffds_freqs_from_learns (rev rev_learns) xtabs 0 empty_ffds empty_freqs

           in

             trace_msg ctxt (fn () => "Loaded fact graph (" ^ graph_info access_G ^ ")");

             {access_G = access_G, xtabs = xtabs, ffds = ffds, freqs = freqs, dirty_facts = SOME []}

           end

         | _ => empty_state)))

  end

fun str_of_entry (kind, name, parents, feats, deps) =

  str_of_proof_kind kind ^ " " ^ encode_str name ^ ": " ^ encode_strs parents ^ "; " ^

  encode_strs feats ^ "; " ^ encode_strs deps ^ "\n"

fun save_state _ (time_state as (_, {dirty_facts = SOME [], ...})) = time_state

  | save_state ctxt (memory_time, {access_G, xtabs, ffds, freqs, dirty_facts}) =

    let

      fun append_entry (name, ((kind, feats, deps), (parents, _))) =

        cons (kind, name, Graph.Keys.dest parents, feats, deps)

      val path = state_file ()

      val dirty_facts' =

        (case try OS.FileSys.modTime (Path.implode path) of

          NONE => NONE

        | SOME disk_time => if Time.< (disk_time, memory_time) then dirty_facts else NONE)

      val (banner, entries) =

        (case dirty_facts' of

          SOME names => (NONE, fold (append_entry o Graph.get_entry access_G) names [])

        | NONE => (SOME (version ^ "\n"), Graph.fold append_entry access_G []))

    in

      (case banner of SOME s => File.write path s | NONE => ();

       entries |> chunk_list 500 |> List.app (File.append path o implode o map str_of_entry))

      handle IO.Io _ => ();

      trace_msg ctxt (fn () =>

        "Saved fact graph (" ^ graph_info access_G ^

        (case dirty_facts of

          SOME dirty_facts => "; " ^ string_of_int (length dirty_facts) ^ " dirty fact(s)"

        | _ => "") ^  ")");

      (Time.now (),

       {access_G = access_G, xtabs = xtabs, ffds = ffds, freqs = freqs, dirty_facts = SOME []})

    end

val global_state = Synchronized.var "Sledgehammer_MaSh.global_state" (Time.zeroTime, empty_state)

in

fun map_state ctxt f =

  Synchronized.change global_state (load_state ctxt ##> f #> save_state ctxt)

  handle FILE_VERSION_TOO_NEW () => ()

fun peek_state ctxt =

  Synchronized.change_result global_state (perhaps (try (load_state ctxt)) #> `snd)

fun clear_state () =

  Synchronized.change global_state (fn _ => (remove_state_file (); (Time.zeroTime, empty_state)))

end

(*** Isabelle helpers ***)

val local_prefix = "local" ^ Long_Name.separator

fun elided_backquote_thm threshold th =

  elide_string threshold (backquote_thm (Proof_Context.init_global (Thm.theory_of_thm th)) th)

val thy_name_of_thm = Context.theory_name o Thm.theory_of_thm

fun nickname_of_thm th =

  if Thm.has_name_hint th then

    let val hint = Thm.get_name_hint th in

      (* There must be a better way to detect local facts. *)

      (case try (unprefix local_prefix) hint of

        SOME suf =>

        thy_name_of_thm th ^ Long_Name.separator ^ suf ^ Long_Name.separator ^

        elided_backquote_thm 50 th

      | NONE => hint)

    end

  else

    elided_backquote_thm 200 th

fun find_suggested_facts ctxt facts =

  let

    fun add (fact as (_, th)) = Symtab.default (nickname_of_thm th, fact)

    val tab = fold add facts Symtab.empty

    fun lookup nick =

      Symtab.lookup tab nick

      |> tap (fn NONE => trace_msg ctxt (fn () => "Cannot find " ^ quote nick) | _ => ())

  in map_filter lookup end

fun free_feature_of s = "f" ^ s

fun thy_feature_of s = "y" ^ s

fun type_feature_of s = "t" ^ s

fun class_feature_of s = "s" ^ s

val local_feature = "local"

fun crude_theory_ord p =

  if Theory.subthy p then

    if Theory.eq_thy p then EQUAL else LESS

  else if Theory.subthy (swap p) then

    GREATER

  else

    (case int_ord (pairself (length o Theory.ancestors_of) p) of

      EQUAL => string_ord (pairself Context.theory_name p)

    | order => order)

fun crude_thm_ord p =

  (case crude_theory_ord (pairself theory_of_thm p) of

    EQUAL =>

    (* The hack below is necessary because of odd dependencies that are not reflected in the theory

       comparison. *)

    let val q = pairself nickname_of_thm p in

      (* Hack to put "xxx_def" before "xxxI" and "xxxE" *)

      (case bool_ord (pairself (String.isSuffix "_def") (swap q)) of

        EQUAL => string_ord q

      | ord => ord)

    end

  | ord => ord)

val thm_less_eq = Theory.subthy o pairself theory_of_thm

fun thm_less p = thm_less_eq p andalso not (thm_less_eq (swap p))

val freezeT = Type.legacy_freeze_type

fun freeze (t $ u) = freeze t $ freeze u

  | freeze (Abs (s, T, t)) = Abs (s, freezeT T, freeze t)

  | freeze (Var ((s, _), T)) = Free (s, freezeT T)

  | freeze (Const (s, T)) = Const (s, freezeT T)

  | freeze (Free (s, T)) = Free (s, freezeT T)

  | freeze t = t

fun goal_of_thm thy = prop_of #> freeze #> cterm_of thy #> Goal.init

fun run_prover_for_mash ctxt params prover goal_name facts goal =

  let

    val problem =

      {comment = "Goal: " ^ goal_name, state = Proof.init ctxt, goal = goal, subgoal = 1,

       subgoal_count = 1, factss = [("", facts)]}

  in

    get_minimizing_prover ctxt MaSh (K ()) prover params (K (K (K ""))) problem

  end

val bad_types = [@{type_name prop}, @{type_name bool}, @{type_name fun}]

val pat_tvar_prefix = "_"

val pat_var_prefix = "_"

(* try "Long_Name.base_name" for shorter names *)

fun massage_long_name s = s

val crude_str_of_sort = space_implode ":" o map massage_long_name o subtract (op =) @{sort type}

fun crude_str_of_typ (Type (s, [])) = massage_long_name s

  | crude_str_of_typ (Type (s, Ts)) = massage_long_name s ^ implode (map crude_str_of_typ Ts)

  | crude_str_of_typ (TFree (_, S)) = crude_str_of_sort S

  | crude_str_of_typ (TVar (_, S)) = crude_str_of_sort S

fun maybe_singleton_str _ "" = []

  | maybe_singleton_str pref s = [pref ^ s]

val max_pat_breadth = 10 (* FUDGE *)

fun term_features_of ctxt thy_name term_max_depth type_max_depth ts =

  let

    val thy = Proof_Context.theory_of ctxt

    val fixes = map snd (Variable.dest_fixes ctxt)

    val classes = Sign.classes_of thy

    fun add_classes @{sort type} = I

      | add_classes S =

        fold (`(Sorts.super_classes classes)

          #> swap #> op ::

          #> subtract (op =) @{sort type} #> map massage_long_name

          #> map class_feature_of

          #> union (op =)) S

    fun pattify_type 0 _ = []

      | pattify_type _ (Type (s, [])) =

        if member (op =) bad_types s then [] else [massage_long_name s]

      | pattify_type depth (Type (s, U :: Ts)) =

        let

          val T = Type (s, Ts)

          val ps = take max_pat_breadth (pattify_type depth T)

          val qs = take max_pat_breadth ("" :: pattify_type (depth - 1) U)

        in

          map_product (fn p => fn "" => p | q => p ^ "(" ^ q ^ ")") ps qs

        end

      | pattify_type _ (TFree (_, S)) = maybe_singleton_str pat_tvar_prefix (crude_str_of_sort S)

      | pattify_type _ (TVar (_, S)) = maybe_singleton_str pat_tvar_prefix (crude_str_of_sort S)

    fun add_type_pat depth T =

      union (op =) (map type_feature_of (pattify_type depth T))

    fun add_type_pats 0 _ = I

      | add_type_pats depth t = add_type_pat depth t #> add_type_pats (depth - 1) t

    fun add_type T =

      add_type_pats type_max_depth T

      #> fold_atyps_sorts (add_classes o snd) T

    fun add_subtypes (T as Type (_, Ts)) = add_type T #> fold add_subtypes Ts

      | add_subtypes T = add_type T

    fun pattify_term _ 0 _ = []

      | pattify_term _ _ (Const (s, _)) =

        if is_widely_irrelevant_const s then [] else [massage_long_name s]

      | pattify_term _ _ (Free (s, T)) =

        maybe_singleton_str pat_var_prefix (crude_str_of_typ T)

        |> (if member (op =) fixes s then

              cons (free_feature_of (massage_long_name (thy_name ^ Long_Name.separator ^ s)))

            else

              I)

      | pattify_term _ _ (Var (_, T)) = maybe_singleton_str pat_var_prefix (crude_str_of_typ T)

      | pattify_term Ts _ (Bound j) =

        maybe_singleton_str pat_var_prefix (crude_str_of_typ (nth Ts j))

      | pattify_term Ts depth (t $ u) =

        let

          val ps = take max_pat_breadth (pattify_term Ts depth t)

          val qs = take max_pat_breadth ("" :: pattify_term Ts (depth - 1) u)

        in

          map_product (fn p => fn "" => p | q => p ^ "(" ^ q ^ ")") ps qs

        end

      | pattify_term _ _ _ = []

    fun add_term_pat Ts = union (op =) oo pattify_term Ts

    fun add_term_pats _ 0 _ = I

      | add_term_pats Ts depth t = add_term_pat Ts depth t #> add_term_pats Ts (depth - 1) t

    fun add_term Ts = add_term_pats Ts term_max_depth

    fun add_subterms Ts t =

      (case strip_comb t of

        (Const (s, T), args) =>

        (not (is_widely_irrelevant_const s) ? add_term Ts t)

        #> add_subtypes T #> fold (add_subterms Ts) args

      | (head, args) =>

        (case head of

           Free (_, T) => add_term Ts t #> add_subtypes T

         | Var (_, T) => add_subtypes T

         | Abs (_, T, body) => add_subtypes T #> add_subterms (T :: Ts) body

         | _ => I)

        #> fold (add_subterms Ts) args)

  in

    fold (add_subterms []) ts []

  end

val term_max_depth = 2

val type_max_depth = 1

(* TODO: Generate type classes for types? *)

fun features_of ctxt thy (scope, _) ts =

  let val thy_name = Context.theory_name thy in

    thy_feature_of thy_name ::

    term_features_of ctxt thy_name term_max_depth type_max_depth ts

    |> scope <> Global ? cons local_feature

  end

(* Too many dependencies is a sign that a decision procedure is at work. There is not much to learn

   from such proofs. *)

val max_dependencies = 20

val prover_default_max_facts = 25

(* "type_definition_xxx" facts are characterized by their use of "CollectI". *)

val typedef_dep = nickname_of_thm @{thm CollectI}

(* Mysterious parts of the class machinery create lots of proofs that refer exclusively to

   "someI_ex" (and to some internal constructions). *)

val class_some_dep = nickname_of_thm @{thm someI_ex}

val fundef_ths =

  @{thms fundef_ex1_existence fundef_ex1_uniqueness fundef_ex1_iff fundef_default_value}

  |> map nickname_of_thm

(* "Rep_xxx_inject", "Abs_xxx_inverse", etc., are derived using these facts. *)

val typedef_ths =

  @{thms type_definition.Abs_inverse type_definition.Rep_inverse type_definition.Rep

      type_definition.Rep_inject type_definition.Abs_inject type_definition.Rep_cases

      type_definition.Abs_cases type_definition.Rep_induct type_definition.Abs_induct

      type_definition.Rep_range type_definition.Abs_image}

  |> map nickname_of_thm

fun is_size_def [dep] th =

    (case first_field ".rec" dep of

      SOME (pref, _) =>

      (case first_field ".size" (nickname_of_thm th) of

        SOME (pref', _) => pref = pref'

      | NONE => false)

    | NONE => false)

  | is_size_def _ _ = false

fun trim_dependencies deps =

  if length deps > max_dependencies then NONE else SOME deps

fun isar_dependencies_of name_tabs th =

  thms_in_proof max_dependencies (SOME name_tabs) th

  |> Option.map (fn deps =>

    if deps = [typedef_dep] orelse deps = [class_some_dep] orelse

       exists (member (op =) fundef_ths) deps orelse exists (member (op =) typedef_ths) deps orelse

       is_size_def deps th then

      []

    else

      deps)

fun prover_dependencies_of ctxt (params as {verbose, max_facts, ...}) prover auto_level facts

    name_tabs th =

  (case isar_dependencies_of name_tabs th of

    SOME [] => (false, [])

  | isar_deps0 =>

    let

      val isar_deps = these isar_deps0

      val thy = Proof_Context.theory_of ctxt

      val goal = goal_of_thm thy th

      val name = nickname_of_thm th

      val (_, hyp_ts, concl_t) = ATP_Util.strip_subgoal goal 1 ctxt

      val facts = facts |> filter (fn (_, th') => thm_less (th', th))

      fun nickify ((_, stature), th) = ((nickname_of_thm th, stature), th)

      fun is_dep dep (_, th) = nickname_of_thm th = dep

      fun add_isar_dep facts dep accum =

        if exists (is_dep dep) accum then

          accum

        else