src/HOL/Tools/Nitpick/nitpick_kodkod.ML
changeset 35177 168041f24f80
parent 35078 6fd1052fe463
child 35178 29a0e3be0be1
equal deleted inserted replaced
35087:e385fa507468 35177:168041f24f80
   315          let val ts = KK.TupleAtomSeq (epsilon - delta, delta + j0) in
   315          let val ts = KK.TupleAtomSeq (epsilon - delta, delta + j0) in
   316            if R2 = Formula Neut then
   316            if R2 = Formula Neut then
   317              [ts] |> not exclusive ? cons (KK.TupleSet [])
   317              [ts] |> not exclusive ? cons (KK.TupleSet [])
   318            else
   318            else
   319              [KK.TupleSet [],
   319              [KK.TupleSet [],
   320               if (* ### exclusive andalso*) T1 = T2 andalso epsilon > delta then
   320               if T1 = T2 andalso epsilon > delta then
   321                 index_seq delta (epsilon - delta)
   321                 index_seq delta (epsilon - delta)
   322                 |> map (fn j =>
   322                 |> map (fn j =>
   323                            KK.TupleProduct (KK.TupleSet [Kodkod.Tuple [j + j0]],
   323                            KK.TupleProduct (KK.TupleSet [Kodkod.Tuple [j + j0]],
   324                                             KK.TupleAtomSeq (j, j0)))
   324                                             KK.TupleAtomSeq (j, j0)))
   325                 |> foldl1 KK.TupleUnion
   325                 |> foldl1 KK.TupleUnion
   768                      o #const) constrs)
   768                      o #const) constrs)
   769 
   769 
   770 val empty_rel = KK.Product (KK.None, KK.None)
   770 val empty_rel = KK.Product (KK.None, KK.None)
   771 
   771 
   772 (* nfa_table -> typ -> typ -> KK.rel_expr list *)
   772 (* nfa_table -> typ -> typ -> KK.rel_expr list *)
   773 fun direct_path_rel_exprs nfa start final =
   773 fun direct_path_rel_exprs nfa start_T final_T =
   774   case AList.lookup (op =) nfa final of
   774   case AList.lookup (op =) nfa final_T of
   775     SOME trans => map fst (filter (curry (op =) start o snd) trans)
   775     SOME trans => map fst (filter (curry (op =) start_T o snd) trans)
   776   | NONE => []
   776   | NONE => []
   777 (* kodkod_constrs -> nfa_table -> typ list -> typ -> typ -> KK.rel_expr *)
   777 (* kodkod_constrs -> nfa_table -> typ list -> typ -> typ -> KK.rel_expr *)
   778 and any_path_rel_expr ({kk_union, ...} : kodkod_constrs) nfa [] start final =
   778 and any_path_rel_expr ({kk_union, ...} : kodkod_constrs) nfa [] start_T
   779     fold kk_union (direct_path_rel_exprs nfa start final)
   779                       final_T =
   780          (if start = final then KK.Iden else empty_rel)
   780     fold kk_union (direct_path_rel_exprs nfa start_T final_T)
   781   | any_path_rel_expr (kk as {kk_union, ...}) nfa (q :: qs) start final =
   781          (if start_T = final_T then KK.Iden else empty_rel)
   782     kk_union (any_path_rel_expr kk nfa qs start final)
   782   | any_path_rel_expr (kk as {kk_union, ...}) nfa (T :: Ts) start_T final_T =
   783              (knot_path_rel_expr kk nfa qs start q final)
   783     kk_union (any_path_rel_expr kk nfa Ts start_T final_T)
       
   784              (knot_path_rel_expr kk nfa Ts start_T T final_T)
   784 (* kodkod_constrs -> nfa_table -> typ list -> typ -> typ -> typ
   785 (* kodkod_constrs -> nfa_table -> typ list -> typ -> typ -> typ
   785    -> KK.rel_expr *)
   786    -> KK.rel_expr *)
   786 and knot_path_rel_expr (kk as {kk_join, kk_reflexive_closure, ...}) nfa qs start
   787 and knot_path_rel_expr (kk as {kk_join, kk_reflexive_closure, ...}) nfa Ts
   787                        knot final =
   788                        start_T knot_T final_T =
   788   kk_join (kk_join (any_path_rel_expr kk nfa qs knot final)
   789   kk_join (kk_join (any_path_rel_expr kk nfa Ts knot_T final_T)
   789                    (kk_reflexive_closure (loop_path_rel_expr kk nfa qs knot)))
   790                    (kk_reflexive_closure (loop_path_rel_expr kk nfa Ts knot_T)))
   790           (any_path_rel_expr kk nfa qs start knot)
   791           (any_path_rel_expr kk nfa Ts start_T knot_T)
   791 (* kodkod_constrs -> nfa_table -> typ list -> typ -> KK.rel_expr *)
   792 (* kodkod_constrs -> nfa_table -> typ list -> typ -> KK.rel_expr *)
   792 and loop_path_rel_expr ({kk_union, ...} : kodkod_constrs) nfa [] start =
   793 and loop_path_rel_expr ({kk_union, ...} : kodkod_constrs) nfa [] start_T =
   793     fold kk_union (direct_path_rel_exprs nfa start start) empty_rel
   794     fold kk_union (direct_path_rel_exprs nfa start_T start_T) empty_rel
   794   | loop_path_rel_expr (kk as {kk_union, kk_closure, ...}) nfa (q :: qs) start =
   795   | loop_path_rel_expr (kk as {kk_union, kk_closure, ...}) nfa (T :: Ts)
   795     if start = q then
   796                        start_T =
   796       kk_closure (loop_path_rel_expr kk nfa qs start)
   797     if start_T = T then
       
   798       kk_closure (loop_path_rel_expr kk nfa Ts start_T)
   797     else
   799     else
   798       kk_union (loop_path_rel_expr kk nfa qs start)
   800       kk_union (loop_path_rel_expr kk nfa Ts start_T)
   799                (knot_path_rel_expr kk nfa qs start q start)
   801                (knot_path_rel_expr kk nfa Ts start_T T start_T)
   800 
   802 
   801 (* nfa_table -> unit NfaGraph.T *)
   803 (* nfa_table -> unit NfaGraph.T *)
   802 fun graph_for_nfa nfa =
   804 fun graph_for_nfa nfa =
   803   let
   805   let
   804     (* typ -> unit NfaGraph.T -> unit NfaGraph.T *)
   806     (* typ -> unit NfaGraph.T -> unit NfaGraph.T *)
   805     fun new_node q = perhaps (try (NfaGraph.new_node (q, ())))
   807     fun new_node T = perhaps (try (NfaGraph.new_node (T, ())))
   806     (* nfa_table -> unit NfaGraph.T -> unit NfaGraph.T *)
   808     (* nfa_table -> unit NfaGraph.T -> unit NfaGraph.T *)
   807     fun add_nfa [] = I
   809     fun add_nfa [] = I
   808       | add_nfa ((_, []) :: nfa) = add_nfa nfa
   810       | add_nfa ((_, []) :: nfa) = add_nfa nfa
   809       | add_nfa ((q, ((_, q') :: transitions)) :: nfa) =
   811       | add_nfa ((T, ((_, T') :: transitions)) :: nfa) =
   810         add_nfa ((q, transitions) :: nfa) o NfaGraph.add_edge (q, q') o
   812         add_nfa ((T, transitions) :: nfa) o NfaGraph.add_edge (T, T') o
   811         new_node q' o new_node q
   813         new_node T' o new_node T
   812   in add_nfa nfa NfaGraph.empty end
   814   in add_nfa nfa NfaGraph.empty end
   813 
   815 
   814 (* nfa_table -> nfa_table list *)
   816 (* nfa_table -> nfa_table list *)
   815 fun strongly_connected_sub_nfas nfa =
   817 fun strongly_connected_sub_nfas nfa =
   816   nfa |> graph_for_nfa |> NfaGraph.strong_conn
   818   nfa |> graph_for_nfa |> NfaGraph.strong_conn
   817       |> map (fn keys => filter (member (op =) keys o fst) nfa)
   819       |> map (fn keys => filter (member (op =) keys o fst) nfa)
   818 
   820 
   819 (* dtype_spec list -> kodkod_constrs -> nfa_table -> typ -> KK.formula *)
   821 (* kodkod_constrs -> dtype_spec list -> nfa_table -> typ -> KK.formula *)
   820 fun acyclicity_axiom_for_datatype dtypes kk nfa start =
   822 fun acyclicity_axiom_for_datatype kk dtypes nfa start_T =
   821   #kk_no kk (#kk_intersect kk
   823   #kk_no kk (#kk_intersect kk
   822                  (loop_path_rel_expr kk nfa (map fst nfa) start) KK.Iden)
   824                  (loop_path_rel_expr kk nfa (map fst nfa) start_T) KK.Iden)
   823 (* hol_context -> kodkod_constrs -> nut NameTable.table -> dtype_spec list
   825 (* hol_context -> kodkod_constrs -> nut NameTable.table -> dtype_spec list
   824    -> KK.formula list *)
   826    -> KK.formula list *)
   825 fun acyclicity_axioms_for_datatypes hol_ctxt kk rel_table dtypes =
   827 fun acyclicity_axioms_for_datatypes hol_ctxt kk rel_table dtypes =
   826   map_filter (nfa_entry_for_datatype hol_ctxt kk rel_table dtypes) dtypes
   828   map_filter (nfa_entry_for_datatype hol_ctxt kk rel_table dtypes) dtypes
   827   |> strongly_connected_sub_nfas
   829   |> strongly_connected_sub_nfas
   828   |> maps (fn nfa => map (acyclicity_axiom_for_datatype dtypes kk nfa o fst)
   830   |> maps (fn nfa =>
   829                          nfa)
   831               map (acyclicity_axiom_for_datatype kk dtypes nfa o fst) nfa)
   830 
   832 
   831 (* hol_context -> int -> kodkod_constrs -> nut NameTable.table -> KK.rel_expr
   833 (* hol_context -> int -> kodkod_constrs -> nut NameTable.table -> KK.rel_expr
   832    -> constr_spec -> int -> KK.formula *)
   834    -> constr_spec -> int -> KK.formula *)
   833 fun sel_axiom_for_sel hol_ctxt j0
   835 fun sel_axiom_for_sel hol_ctxt j0
   834         (kk as {kk_all, kk_implies, kk_formula_if, kk_subset, kk_rel_eq, kk_no,
   836         (kk as {kk_all, kk_implies, kk_formula_if, kk_subset, kk_rel_eq, kk_no,