| 1 | | % (c) 2020-2026 Lehrstuhl fuer Softwaretechnik und Programmiersprachen, |
| 2 | | % Heinrich Heine Universitaet Duesseldorf |
| 3 | | % This software is licenced under EPL 1.0 (http://www.eclipse.org/org/documents/epl-v10.html |
| 4 | | |
| 5 | | :- module(well_def_analyser, [analyse_wd_for_machine/3, analyse_wd_for_machine/4, |
| 6 | | compute_wd/4, compute_all_wd_pos/4, |
| 7 | | analyse_wd_for_expr/3, analyse_wd_for_expr/4, |
| 8 | | annotate_wd/2, transform_wd/4, |
| 9 | | tcltk_get_machine_wd_pos/4, |
| 10 | | get_hyps_for_top_level_operations/2, |
| 11 | | prove_sequent/1, |
| 12 | | prove_sequent/3, |
| 13 | | prove_sequent/4, |
| 14 | | analyse_invariants_for_machine/5, |
| 15 | | find_inconsistent_axiom/3, tcltk_check_for_inconsistent_axiom/1, |
| 16 | | toplevel_wd_pos/3 |
| 17 | | ]). |
| 18 | | |
| 19 | | :- use_module(probsrc(module_information),[module_info/2]). |
| 20 | | :- module_info(group,well_def_prover). |
| 21 | | :- module_info(description,'This module computes WD conditions in AST.'). |
| 22 | | |
| 23 | | :- use_module(probsrc(error_manager)). |
| 24 | | :- use_module(probsrc(debug)). |
| 25 | | :- use_module(probsrc(bsyntaxtree)). |
| 26 | | :- use_module(probsrc(b_ast_cleanup), [has_top_level_wd_condition/1]). |
| 27 | | :- use_module(probsrc(external_functions),[external_fun_has_wd_condition/1]). |
| 28 | | :- use_module(probsrc(specfile),[z_or_tla_minor_mode/0, eventb_mode/0]). |
| 29 | | |
| 30 | | :- use_module(library(ordsets)). |
| 31 | | :- use_module(library(avl)). |
| 32 | | :- use_module(wdsrc(well_def_hyps)). |
| 33 | | |
| 34 | | |
| 35 | | prove_sequent(Goal) :- |
| 36 | | prove_sequent(proving,Goal,[]). |
| 37 | | prove_sequent(Context,Goal,Hyps) :- |
| 38 | | prove_sequent(Context,Goal,Hyps,[push_more_hyps]). % push all hypotheses; usually not useful for WD proofs but useful if proof goals have other form than for WD POs |
| 39 | | prove_sequent(Context,Goal,Hyps,Opts) :- |
| 40 | | (Context=animation -> Val=true |
| 41 | | ; Context=proving -> Val=false |
| 42 | | ; add_internal_error('Unknown context:',Context), |
| 43 | | Val=false), |
| 44 | | temporary_set_preference(wd_analysis_for_animation,Val,Chng), |
| 45 | | call_cleanup(prove_sequent_cur_context(Goal,Hyps,Opts), |
| 46 | | reset_temporary_preference(wd_analysis_for_animation,Chng)). |
| 47 | | |
| 48 | | |
| 49 | | % utility for disprover |
| 50 | | prove_sequent_cur_context(_,Hyps,_) :- |
| 51 | ? | member(Falsity,Hyps), is_falsity(Falsity),!. % TO DO: upon pushing hyps |
| 52 | | prove_sequent_cur_context(Falsity,Hypotheses,Opts) :- |
| 53 | | is_falsity(Falsity), % we do not have a good way of detecting inconsistencies in the hyps yet |
| 54 | | append(NewHyps,[LastHyp],Hypotheses),!, |
| 55 | | negate_hyp(LastHyp,NewGoal), % pick last hypothesis and try and prove its negation as goal |
| 56 | | prove_sequent_cur_context(NewGoal,NewHyps,Opts). |
| 57 | | prove_sequent_cur_context(Goal,Hypotheses,Opts) :- |
| 58 | | empty_hyps(E), |
| 59 | | list_to_ord_set([discharge_po|Opts],Options), |
| 60 | | push_hyps(E,Hypotheses,Options,Hyps), |
| 61 | | prove_sequent_goal(Goal,Hyps,Options). |
| 62 | | |
| 63 | | % process complex sequent goals which arise in Rodin; not generated by our POG |
| 64 | | prove_sequent_goal(b(Formula,pred,I),Hyps,Options) :- !, |
| 65 | | process_sequent_aux(Formula,I,Hyps,Options). |
| 66 | | prove_sequent_goal(Goal,Hyps,Options) :- Goal = b(_,_,_), !, |
| 67 | | add_internal_error('Goal to prove not a predicate: ',prove_sequent_goal(Goal,Hyps,Options)),fail. |
| 68 | | prove_sequent_goal(Goal,Hyps,Options) :- |
| 69 | | add_internal_error('Goal to prove not wrapped: ',prove_sequent_goal(Goal,Hyps,Options)),fail. |
| 70 | | |
| 71 | ? | process_sequent_aux(negation(b(Pred,pred,_)),I,Hyps,Options) :- cnf_negate(Pred,NegPred),!, |
| 72 | | (debug_level_inactive_for(19) -> true |
| 73 | | ; print('Pushing negation in sequent goal: '), translate:print_bexpr(b(NegPred,pred,[])),nl), |
| 74 | | % example :prove x=3 => not( x=3 => x=2) |
| 75 | | process_sequent_aux(NegPred,I,Hyps,Options). |
| 76 | | process_sequent_aux(implication(A,B),_,Hyps,Options) :- !, |
| 77 | | (debug_level_inactive_for(19) -> true ; print('Peeling implication in sequent goal: '), translate:print_bexpr(A),nl), |
| 78 | | push_hyp(Hyps,A,Options,Hyps1), |
| 79 | | (prove_sequent_goal(B,Hyps1,Options) -> true |
| 80 | | ; negate_hyp(A,NegA), |
| 81 | | negate_hyp(B,NegB), push_hyp(Hyps,NegB,Options,Hyps2), % try not(B) => not(A) |
| 82 | | debug_println(19,trying_to_prove_contrapositive), |
| 83 | | prove_sequent_goal(NegA,Hyps2,Options) |
| 84 | | ). |
| 85 | | process_sequent_aux(equivalence(A,B),I,Hyps,Options) :- !, |
| 86 | | process_sequent_aux(implication(A,B),I,Hyps,Options), |
| 87 | | process_sequent_aux(implication(B,A),I,Hyps,Options). |
| 88 | | process_sequent_aux(if_predicate(Test,A,B),I,Hyps,Options) :- !, |
| 89 | | process_sequent_aux(implication(Test,A),I,Hyps,Options), |
| 90 | | negate_hyp(Test,NegTest), |
| 91 | | process_sequent_aux(implication(NegTest,B),I,Hyps,Options). |
| 92 | | process_sequent_aux(conjunct(A,B),_I,Hyps,Options) :- !, |
| 93 | | prove_sequent_goal(A,Hyps,Options), |
| 94 | | prove_sequent_goal(B,Hyps,Options). |
| 95 | | process_sequent_aux(disjunct(A,B),_I,Hyps,Options) :- !, |
| 96 | | (negate_hyp(B,NegB), |
| 97 | | push_hyp(Hyps,NegB,Options,Hyps2), % not(B) => A we have A or B ; OR_R rule from Abrial Event-B Chapter 9.2.2 |
| 98 | | % is a combination of OR_R proof rule and proof by case B, not(B) |
| 99 | | prove_sequent_goal(A,Hyps2,Options) |
| 100 | | -> true |
| 101 | | ; % not sure if it will really be often successful to try this branch if the first one failed |
| 102 | | negate_hyp(A,NegA), |
| 103 | | push_hyp(Hyps,NegA,Options,Hyps2), % not(A) => B we have A or B |
| 104 | | prove_sequent_goal(B,Hyps2,Options)). |
| 105 | | process_sequent_aux(forall(Ids,A,B),I,Hyps,Options) :- !, |
| 106 | | (debug_level_inactive_for(19) -> true ; print('Peeling forall in sequent goal: '), translate:print_bexpr(A),nl), |
| 107 | | add_new_hyp_variables(Hyps,Ids,Hyps1), |
| 108 | | prove_sequent_goal(b(implication(A,B),pred,I),Hyps1,Options). |
| 109 | | process_sequent_aux(Goal,I,Hyps,Options) :- |
| 110 | | get_normalized_and_renamed_predicate(b(Goal,pred,I),Hyps,_RenTarget,NT), |
| 111 | | % print('PROVING: '),translate:print_bexpr(_RenTarget),nl, |
| 112 | | (get_current_po_label(POLabel,Options) -> true ; POLabel = ''), |
| 113 | | prove_proof_obligation(POLabel,Goal,NT,Hyps,ProofTree), |
| 114 | | debug_format(19,'WD PROVER SUCCESSFUL: ~w~n',[ProofTree]). |
| 115 | | |
| 116 | | :- use_module(probsrc(bsyntaxtree),[create_negation/2]). |
| 117 | | cnf_negate(implication(A,B),conjunct(A,NotB)) :- create_negation(B,NotB). |
| 118 | | cnf_negate(equivalence(A,B),conjunct(b(implication(A,NotB),pred,[]), |
| 119 | | b(implication(NotA,B),pred,[]))) :- |
| 120 | | % not( A <=> B ) <----> A=> not(B) & not(A) => B |
| 121 | | create_negation(A,NotA), |
| 122 | | create_negation(B,NotB). |
| 123 | | cnf_negate(disjunct(A,B),conjunct(NotA,NotB)) :- create_negation(A,NotA), create_negation(B,NotB). |
| 124 | | cnf_negate(conjunct(A,B),disjunct(NotA,NotB)) :- create_negation(A,NotA), create_negation(B,NotB). |
| 125 | | cnf_negate(if_predicate(A,B,C),Res) :- create_negation(A,NA), |
| 126 | | cnf_negate(conjunct(implication(A,B),implication(NA,C)),Res). |
| 127 | | cnf_negate(NegA,A) :- negate_op(NegA,A). % deals with negation(A) -> A, truth->falsity, ... |
| 128 | | %cnf_negate(exists(Ids,Q),forall(Ids,LHS,RHS)) :- ... TODO |
| 129 | | |
| 130 | | compute_all_wd_pos(TExpr,OriginalHyps,Options,POs) :- |
| 131 | | findall(PO, compute_wd(TExpr,OriginalHyps,Options,PO), POs). |
| 132 | | |
| 133 | | |
| 134 | | % analyze and print WD POs for a given typed expression or predicate or subst: |
| 135 | | analyse_wd_for_expr(TExpr,ResStr,AllDischarged) :- |
| 136 | | analyse_wd_for_expr(TExpr,ResStr,AllDischarged,silent). |
| 137 | | |
| 138 | | % MsgLevel = silent, message, warning, error |
| 139 | | analyse_wd_for_expr(TExpr,_,_,MsgLevel) :- |
| 140 | | reset_stats, |
| 141 | | (silent_wd_mode(MsgLevel) -> true ; formatsilent('WD Proof Obligations:~n',[])), |
| 142 | | %empty_hyps(OriginalHyps), |
| 143 | | push_properties_invariant_hyps([],OriginalHyps), |
| 144 | | list_to_ord_set([create_full_po,create_not_discharged_msg(MsgLevel),discharge_po,ignore_wd_infos |
| 145 | | %,minimize_full_po |
| 146 | | %,prove_with_z3 % comment in to double-check with Z3 |
| 147 | | ],Options), |
| 148 | ? | compute_wd(TExpr,OriginalHyps,Options,PO), |
| 149 | | (silent_wd_mode(MsgLevel) -> true ; translate:nested_print_bexpr(PO),nl), |
| 150 | | fail. |
| 151 | | analyse_wd_for_expr(TExpr,ResStr,AllDischarged,MsgLevel) :- |
| 152 | | (silent_wd_mode(MsgLevel) -> true |
| 153 | | ; formatsilent('----~n',[]), |
| 154 | | print_stats |
| 155 | | ), |
| 156 | | get_discharged_result(ResStr,_,_,AllDischarged), |
| 157 | | empty_hyps(OriginalHyps), |
| 158 | | transform_wd(TExpr,OriginalHyps,[discharge_po],NewTExpr), |
| 159 | | (silent_wd_mode(MsgLevel) -> true |
| 160 | | ; format('Annotated formula:~n',[]), |
| 161 | | nested_print_wd_bexpr(NewTExpr) |
| 162 | | ). |
| 163 | | |
| 164 | | silent_wd_mode(MsgLevel) :- (MsgLevel=silent -> true ; silent_mode(on)). |
| 165 | | |
| 166 | | nested_print_wd_bexpr(NewTExpr) :- |
| 167 | | temporary_set_preference(pp_wd_infos,true,Chng), |
| 168 | | translate:nested_print_bexpr(NewTExpr),nl, |
| 169 | | reset_temporary_preference(pp_wd_infos,Chng). |
| 170 | | |
| 171 | | :- use_module(probsrc(translate),[translate_bexpression_with_limit/3]). |
| 172 | | |
| 173 | | tcltk_get_machine_wd_pos(only_goal,list([Header|POs]),ResStr,AllDischarged) :- !, |
| 174 | | reset_stats, |
| 175 | | Header = list(['PO Label','Discharged','Proof Obligation Goal', 'Source']), |
| 176 | | list_to_ord_set([discharge_po,ignore_wd_infos,reorder_conjuncts],Options), |
| 177 | | findall(list([POLabel,Discharged,POStr,Source]), |
| 178 | | (get_machine_wd_po(Options,PO,PO_Name), |
| 179 | | get_texpr_info(PO,Infos), |
| 180 | | (member(discharged(D,POLabel),Infos) |
| 181 | | -> (D=true -> Discharged='yes' ; Discharged='no') |
| 182 | | ; Discharged='UNKNOWN',POLabel=PO_Name), |
| 183 | | translate:translate_bexpression_with_limit(PO,100,POStr), |
| 184 | | get_tk_table_position_info(Infos,Source) |
| 185 | | ), POs), |
| 186 | | get_discharged_result(ResStr,_,_,AllDischarged). |
| 187 | | tcltk_get_machine_wd_pos(goal_and_hyps,list([Header|POs]),ResStr,AllDischarged) :- |
| 188 | | reset_stats, |
| 189 | | get_preference(translation_limit_for_table_commands,Limit), |
| 190 | | Header = list(['PO Label','Discharged','PO Goal', '(Necessary) Hypotheses', 'Source']), |
| 191 | | % in case a PO is proven we only show the hyps necessary for the proof |
| 192 | | list_to_ord_set([discharge_po,ignore_wd_infos,reorder_conjuncts, create_full_po,minimize_full_po],Options), |
| 193 | | findall(list([POLabel,Discharged,GoalStr,HypsStr,Source]), |
| 194 | | (get_machine_wd_po(Options,PO,PO_Name), |
| 195 | | get_texpr_info(PO,Infos), |
| 196 | | (member(discharged(D,POLabel),Infos) |
| 197 | | -> (D=true -> Discharged='yes' ; Discharged='no') |
| 198 | | ; Discharged='UNKNOWN',POLabel=PO_Name), |
| 199 | | decompose_po(PO,Hyps,Goal), |
| 200 | | translate_bexpression_with_limit(Hyps,Limit,HypsStr), |
| 201 | | translate_bexpression_with_limit(Goal,Limit,GoalStr), |
| 202 | | get_tk_table_position_info(Infos,Source) |
| 203 | | ), POs), |
| 204 | | get_discharged_result(ResStr,_,_,AllDischarged). |
| 205 | | |
| 206 | | decompose_po(b(implication(Hyps,Goal),pred,_),Hyps,Goal) :- !. |
| 207 | | decompose_po(Goal,b(truth,pred,[]),Goal). |
| 208 | | |
| 209 | | % analyse all WD POs for the loaded B machine |
| 210 | | analyse_wd_for_machine(NrDischarged,NrTot,Discharged) :- |
| 211 | | Options = [create_not_discharged_msg(warning),discharge_po,ignore_wd_infos,reorder_conjuncts], |
| 212 | | analyse_wd_for_machine(NrDischarged,NrTot,Discharged,Options). |
| 213 | | analyse_wd_for_machine_with_double_check(NrDischarged,NrTot,Discharged) :- |
| 214 | | Options = [create_not_discharged_msg(warning),discharge_po,ignore_wd_infos,reorder_conjuncts, |
| 215 | | create_full_po, prove_with_z3], |
| 216 | | analyse_wd_for_machine(NrDischarged,NrTot,Discharged,Options). |
| 217 | | |
| 218 | | analyse_wd_for_machine(NrDischarged,NrTot,Discharged,UnsortedOptions) :- reset_stats, |
| 219 | | list_to_ord_set(UnsortedOptions,Options), |
| 220 | | %list_to_ord_set([discharge_po,reorder_conjuncts],Options), |
| 221 | | statistics(walltime,[Start,_]), |
| 222 | ? | ( get_machine_wd_po(Options,_PO,_), |
| 223 | | fail |
| 224 | | ; |
| 225 | | statistics(walltime,[Stop,_]), Delta is Stop-Start, |
| 226 | | formatsilent('Analysis walltime: ~w ms~n',[Delta]), |
| 227 | | print_stats, |
| 228 | | get_discharged_result(_ResStr,NrDischarged,NrTot,Discharged) |
| 229 | | ). |
| 230 | | |
| 231 | | :- use_module(probsrc(bmachine), [b_get_properties_from_machine/1, b_get_machine_all_constants/1, |
| 232 | | b_get_machine_variables/1, b_get_invariant_from_machine/1, |
| 233 | | b_get_static_assertions_from_machine/1, b_get_dynamic_assertions_from_machine/1, |
| 234 | | b_get_machine_operation/6, b_get_initialisation_from_machine/2]). |
| 235 | | |
| 236 | | transl_hyp(Axiom,Str) :- |
| 237 | | translate:translate_bexpression_with_limit(Axiom,500,Str). |
| 238 | | |
| 239 | | % if successful: returns a message explaining that an axiom is in contradiction with some other properties |
| 240 | | tcltk_check_for_inconsistent_axiom(list(['The following predicate from PROPERTIES/axioms:',AxiomStr, |
| 241 | | 'is in contradiction with these predicates:' | TPS])) :- |
| 242 | | find_inconsistent_axiom([],Axiom,NecHyps), |
| 243 | | %get_specification_description(properties,PS), |
| 244 | | translate:translate_bexpression_with_limit(Axiom,500,AxiomStr), |
| 245 | | maplist(transl_hyp,NecHyps,TPS). |
| 246 | | |
| 247 | | % try to find inconsistency in properties/axioms: |
| 248 | | find_inconsistent_axiom(LOpt,Axiom,NecHyps) :- |
| 249 | | reset_stats, |
| 250 | | get_fresh_hyps_for_constants(OriginalHyps), |
| 251 | | b_get_properties_from_machine(Properties), |
| 252 | | list_to_ord_set([push_more_hyps|LOpt],Options), |
| 253 | | push_hyp(OriginalHyps,Properties,Options,Hyps1), |
| 254 | | member_in_conjunction(Axiom,Properties), |
| 255 | | (debug_mode(on) -> print(' checking for contradiction with ==> '),translate:print_bexpr(Axiom),nl ; true), |
| 256 | | NegAxiom = b(negation(Axiom),pred,[]), |
| 257 | | prove_sequent_goal(NegAxiom,Hyps1,Options), |
| 258 | | print('INCONSISTENCY FOUND, negation of axiom can be proven: '), |
| 259 | | translate:print_bexpr(Axiom),nl, |
| 260 | | % ord_member(minimize_full_po,Options), |
| 261 | | print('Finding NECESSARY Hypotheses:'),nl, |
| 262 | | minimize_necessary_hyps(Hyps1,NegAxiom,Options,NecHyps), |
| 263 | | (debug_mode(on) -> translate:nested_print_bexpr(NecHyps),nl ; true). |
| 264 | | %TODO: optionally take prob-ignore into account (predicate_has_ignore_pragma/1 and get_preference(use_ignore_pragmas,true)) |
| 265 | | |
| 266 | | minimize_necessary_hyps(hyp_rec(AvlNH,_),Goal,Options,NecHyps) :- |
| 267 | | avl_range(AvlNH,Hyps), |
| 268 | | minimize_hyps(Hyps,Goal,Options,NecHyps). |
| 269 | | |
| 270 | | |
| 271 | | get_fresh_hyps_for_constants(OriginalHyps) :- |
| 272 | | empty_hyps(E), |
| 273 | | b_get_machine_all_constants(Csts), |
| 274 | | add_new_hyp_variables(E,Csts,OriginalHyps). |
| 275 | | |
| 276 | | % get POs for loaded B machine |
| 277 | | get_machine_wd_po(LOpt,PO,PO_Name) :- |
| 278 | | reset_stats, |
| 279 | | list_to_ord_set(LOpt,Options), |
| 280 | | b_get_properties_from_machine(Properties), |
| 281 | | % TO DO: move Conjuncts without WD condition to front in first pass |
| 282 | | get_fresh_hyps_for_constants(OriginalHyps), |
| 283 | | ( PO_Name = 'AXM', |
| 284 | | debug_format(19,'Checking WD of PROPERTIES~n',[]), |
| 285 | | ord_add_element(Options,po_label(PO_Name),Opt2), |
| 286 | ? | compute_wd_with_reordering(Properties,OriginalHyps,Opt2,PO) |
| 287 | | |
| 288 | | %debug:time(well_def_analyser:transform_wd(Properties,OriginalHyps,Opt2,NewProperties)),nl,fail) |
| 289 | | |
| 290 | | ; % TO DO: for transform: only use assertions if assertion checking is on!? |
| 291 | | |
| 292 | | push_hyp(OriginalHyps,Properties,Options,Hyps1), |
| 293 | | b_get_static_assertions_from_machine(StaticAssertions), |
| 294 | | |
| 295 | | ( PO_Name = 'THM-AXM', |
| 296 | | ord_add_element(Options,po_label(PO_Name),Opt2), |
| 297 | | conjunct_predicates(StaticAssertions,SAssPred), |
| 298 | ? | compute_wd(SAssPred,Hyps1,Opt2,PO) |
| 299 | | ; |
| 300 | | push_hyps(Hyps1,StaticAssertions,Options,Hyps2), |
| 301 | | %portray_hyps(Hyps2),nl, |
| 302 | | b_get_machine_variables(Vars), |
| 303 | | add_new_hyp_variables(Hyps2,Vars,Hyps3), |
| 304 | | b_get_invariant_from_machine(Invariant), |
| 305 | | ( PO_Name = 'INV', |
| 306 | | debug_format(19,'Checking WD of INVARIANT~n',[]), |
| 307 | | ord_add_element(Options,po_label(PO_Name),Opt2), |
| 308 | ? | compute_wd_with_reordering(Invariant,Hyps3,Opt2,PO) |
| 309 | | ; |
| 310 | | push_hyp(Hyps3,Invariant,Options,Hyps4), |
| 311 | | b_get_dynamic_assertions_from_machine(DynAssertions), |
| 312 | | ( PO_Name = 'THM-INV', |
| 313 | | debug_format(19,'Checking WD of ASSERTIONS~n',[]), |
| 314 | | ord_add_element(Options,po_label(PO_Name),Opt2), |
| 315 | | conjunct_predicates(DynAssertions,AssPred), |
| 316 | ? | compute_wd(AssPred,Hyps4,Opt2,PO) |
| 317 | | ; push_hyps(Hyps4,DynAssertions,Options,Hyps5), |
| 318 | | ( |
| 319 | | b_get_initialisation_from_machine(Body,_OType), |
| 320 | | PO_Name = 'INIT', |
| 321 | | debug_format(19,'Checking WD of INITIALISATION~n',[]), |
| 322 | | ord_add_element(Options,po_label(PO_Name),Opt2), |
| 323 | ? | compute_wd(Body,Hyps5,Opt2,PO) |
| 324 | ? | ; b_get_machine_operation(OpName,OpResults,OpFormalParameters,Body,_OType,_TopLevel), |
| 325 | | PO_Name = OpName, |
| 326 | | debug_format(19,'Checking WD of OPERATION ~w~n',[OpName]), |
| 327 | | ord_add_element(Options,po_label(PO_Name),Opt2), |
| 328 | | add_new_hyp_variables(Hyps5,OpFormalParameters,Hyps6), |
| 329 | | add_new_hyp_variables(Hyps6,OpResults,Hyps7), |
| 330 | ? | compute_wd(Body,Hyps7,Opt2,PO) |
| 331 | | % TODO: optionally transform and store operation |
| 332 | | ) |
| 333 | | ) |
| 334 | | ) |
| 335 | | ) |
| 336 | | ), |
| 337 | | inc_counter(PO_Name). |
| 338 | | |
| 339 | | |
| 340 | | % -------------------- |
| 341 | | |
| 342 | | :- use_module(probsrc(tools_strings),[ajoin/2,ajoin_with_sep/3]). |
| 343 | | % get label of current PO from Options |
| 344 | | get_current_po_label(POLabel,Options) :- |
| 345 | | findall(Label,get_label(Label,Options),Labels), |
| 346 | | Labels \= [], |
| 347 | | ajoin_with_sep(Labels,'/',POLabel). |
| 348 | ? | get_label(Label,Options) :- member(po_label(L),Options), |
| 349 | | (L = [_|_] -> member(Label,L) ; Label=L). |
| 350 | | |
| 351 | | % -------------------- |
| 352 | | |
| 353 | | :- use_module(well_def_prover,[prove_po/3]). |
| 354 | | :- use_module(probsrc(tools_lists),[ord_member_nonvar_chk/2]). |
| 355 | | |
| 356 | | create_po(H,Target,Infos,Options,PO) :- create_po(H,Target,Infos,Options,PO,_). |
| 357 | | |
| 358 | | create_po(H,Target,Infos,Options,PO,D) :- (var(H) ; H \= hyp_rec(_,_) ; var(Options)),!, |
| 359 | | add_internal_error('Illegal hypotheses or options: ', create_po(H,Target,Infos,Options,PO,D)),fail. |
| 360 | | create_po(Hyps,Target,Infos,Options,PO,Discharged) :- |
| 361 | | get_normalized_and_renamed_predicate(Target,Hyps,RenTarget,NT), |
| 362 | | (get_current_po_label(POLabel,Options) -> true ; POLabel = ''), |
| 363 | | (ord_member(print_goal,Options) -> translate:print_bexpr(RenTarget),nl ; true), |
| 364 | | (ord_member(discharge_po,Options) |
| 365 | | -> (%nl,add_message(well_def_analyser,'Proving ',Target,Infos), |
| 366 | | prove_proof_obligation(POLabel,Target,NT,Hyps,ProofTree) |
| 367 | | -> debug_format(19,'PO ~w discharged: ~w~n',[POLabel,ProofTree]), %debug:nl_time, |
| 368 | | inc_counter(discharged_po), |
| 369 | | Discharged=true |
| 370 | | ; inc_counter(not_discharged_po), |
| 371 | | Discharged=false, |
| 372 | | (ord_member_nonvar_chk(create_not_discharged_msg(MsgType),Options) |
| 373 | ? | -> (prove_po(negation(NT),Hyps,_NegProofTree) |
| 374 | | -> NegProfStatus = ' (goal provably false)' |
| 375 | | % Negation can be proven; i.e., PO cannot be proven unless there is a contradiction in Hyps |
| 376 | | ; NegProfStatus = '' |
| 377 | | ), |
| 378 | | (POLabel = '' -> ajoin(['WD-PO not discharged', NegProfStatus, ': '],Msg) |
| 379 | | ; ajoin(['WD-PO [',POLabel,'] not discharged', NegProfStatus, ': '],Msg) |
| 380 | | ), |
| 381 | | ( MsgType=message -> add_message(well_def_analyser,Msg,Target,Infos) |
| 382 | | ; MsgType=warning -> add_warning(well_def_analyser,Msg,Target,Infos) |
| 383 | | ; MsgType=silent -> formatsilent('~w~w~n',[Msg,Target]) |
| 384 | | ; add_error(well_def_analyser,Msg,Target,Infos) |
| 385 | | ), |
| 386 | | debug_format(19,' Normalized Proof Target: ~w~n',[NT]) |
| 387 | | %,(debug_level_active_for(5) -> portray_hyps(Hyps) ; true) % hyps can be shown with create_full_po |
| 388 | | ; true |
| 389 | | ) |
| 390 | | ) |
| 391 | | ; Discharged=false % no discharging of POs |
| 392 | | ), |
| 393 | | extract_pos_infos(Infos,PosInfos), |
| 394 | | (ord_member(create_full_po,Options) |
| 395 | | -> Hyps = hyp_rec(AvlNH,_), |
| 396 | | avl_range(AvlNH,Hyp), |
| 397 | | (Discharged=true, ord_member(minimize_full_po,Options) |
| 398 | | -> minimize_hyps(Hyp,RenTarget,Options,NecHyps) % only show minimum core of hyps necessary for proving |
| 399 | | ; NecHyps=Hyp |
| 400 | | ), |
| 401 | | %length(NecHyps,Len), print(hyps(Len)),nl, |
| 402 | | conjunct_predicates(NecHyps,HypC), |
| 403 | | safe_create_texpr(implication(HypC,RenTarget),pred,[discharged(Discharged,POLabel)|PosInfos],PO), |
| 404 | | %nl,translate:print_bexpr(PO),nl, prove_po_with_atelierb(POLabel,[ml],PO,_), |
| 405 | | % terms:term_hash(PO,Hash), print(Hash),nl, |
| 406 | | %(ord_member(check_ast,Options) -> bsyntaxtree:check_ast(PO) ; true), |
| 407 | | (ord_member(prove_with_z3,Options) |
| 408 | | -> prove_po_with_smt(POLabel,z3,PO,Res),double_check(Discharged,z3,Res) ; true), |
| 409 | | (ord_member(prove_with_ml,Options) -> prove_po_with_atelierb(POLabel,[ml],PO,_) ; true), |
| 410 | | (ord_member(prove_with_pp,Options) -> prove_po_with_atelierb(POLabel,[pp],PO,_) ; true) |
| 411 | | ; RenTarget = b(POE,POT,POI), |
| 412 | | append([discharged(Discharged,POLabel)|PosInfos],POI,POInfos), |
| 413 | | PO = b(POE,POT,POInfos) |
| 414 | | ). |
| 415 | | |
| 416 | | double_check(true,Solver,solution(S)) :- !, |
| 417 | | add_error(Solver,'Double check of discharged PO failed, counter-example: ',S). |
| 418 | | double_check(_,_,_). |
| 419 | | |
| 420 | | % compute unsat core of hypotheses |
| 421 | | minimize_hyps(Hyps,Goal,Options,NecHyps) :- minimize_hyps_aux(Hyps,Goal,Options,NecHyps,NecHyps),nl. |
| 422 | | |
| 423 | | % TO DO: maybe do binary search / divide and conquer |
| 424 | | % we could also examine which hypotheses were retrieved during the proof |
| 425 | | % (but not easy; what if access inside a Prolog negation) |
| 426 | | minimize_hyps_aux([],_,_,_,[]). |
| 427 | | minimize_hyps_aux([H|T],Goal,Opts,NecessaryHyps,Tail) :- |
| 428 | | (ord_member(push_more_hyps,Opts) -> ProofOpts = [push_more_hyps] ; ProofOpts=[]), |
| 429 | | \+ (Tail=T,prove_sequent_cur_context(Goal,NecessaryHyps,ProofOpts)), % we need H to prove Goal |
| 430 | | !, |
| 431 | | write('+'), |
| 432 | | Tail = [H|TT], |
| 433 | | minimize_hyps_aux(T,Goal,Opts,NecessaryHyps,TT). |
| 434 | | minimize_hyps_aux([_|T],Goal,Opts,NecessaryHyps,Tail) :- |
| 435 | | write('-'), |
| 436 | | minimize_hyps_aux(T,Goal,Opts,NecessaryHyps,Tail). |
| 437 | | |
| 438 | | :- use_module(probsrc(runtime_profiler),[register_profiler_runtime/5]). |
| 439 | | :- use_module(extrasrc(atelierb_provers_interface),[prove_sequent_with_provers/3]). |
| 440 | | prove_po_with_atelierb(POLabel,Provers,PO,ProofRes) :- runtime_profiler:print_runtime_profile, |
| 441 | | format('Proving PO ~w with ~w~n',[POLabel,Provers]), |
| 442 | | statistics(walltime,[T1,_]), |
| 443 | | catch( |
| 444 | | prove_sequent_with_provers(Provers,PO,ProofRes), % we cannot use time_out as PP/ML/KRT are a separate process |
| 445 | | user_interrupt_signal, |
| 446 | | ProofRes = user_interrupt_signal), |
| 447 | | statistics(walltime,[T2,_]), WT is T2-T1, |
| 448 | | !, |
| 449 | | register_profiler_runtime(atelierb(ProofRes),well_def_analyser,POLabel,WT,WT), |
| 450 | | format('Result of ~w on PO = ~w (walltime ~w ms)~n',[Provers,ProofRes,WT]), |
| 451 | | (ProofRes=user_interrupt_signal |
| 452 | | -> write(' Continue? [y/n] => '), flush_output, read(Cont), |
| 453 | | (Cont='y' -> true ; Cont='yes' -> true ; throw(user_interrupt_signal)) |
| 454 | | ; true). |
| 455 | | |
| 456 | | :- use_module(probsrc(bsyntaxtree),[create_negation/2]). |
| 457 | | :- use_module(smt_solvers_interface(smt_solvers_interface),[smt_solve_predicate/4]). |
| 458 | | prove_po_with_smt(POLabel,Solver,PO,ProofRes) :- runtime_profiler:print_runtime_profile, |
| 459 | | format('Proving PO ~w with ~w~n',[POLabel,Solver]), |
| 460 | | %translate:print_bexpr(PO),nl, |
| 461 | | statistics(walltime,[T1,_]), |
| 462 | | create_negation(PO,NegPO), |
| 463 | | smt_solve_predicate(Solver,NegPO,_State,ProofRes),!, |
| 464 | | statistics(walltime,[T2,_]), WT is T2-T1, |
| 465 | | register_profiler_runtime(smt(Solver,ProofRes),well_def_analyser,POLabel,WT,WT), |
| 466 | | format('Result of ~w on PO = ~w (walltime ~w ms)~n',[Solver,ProofRes,WT]). |
| 467 | | |
| 468 | | % a wrapper to prove_po which also checks for obvious POs using type info: |
| 469 | | prove_proof_obligation(POLabel,Target,_NT,Hyps,ProofTree) :- |
| 470 | | obvious_po(Target,Hyps),!, |
| 471 | | debug_format(19,'Obvious PO (due to typing info): ~w~n',[POLabel]), |
| 472 | | register_profiler_runtime(wd_prob_prover(obvious_po),well_def_analyser,POLabel,0,0), |
| 473 | | ProofTree = obvious_po. |
| 474 | | prove_proof_obligation(POLabel,_Target,NT,Hyps,ProofTree) :- |
| 475 | | statistics(runtime,[RT1,_]), |
| 476 | | statistics(walltime,[T1,_]), |
| 477 | ? | (prove_po(NT,Hyps,ProofTree) -> Res=discharged |
| 478 | | ; Res=unknown,ProofTree='' % ,format('~n *********** WD PO UNKNOWN ~w~n~n',[POLabel]) |
| 479 | | ), |
| 480 | | statistics(runtime,[RT2,_]), RT is RT2-RT1, |
| 481 | | statistics(walltime,[T2,_]), WT is T2-T1, |
| 482 | | register_profiler_runtime(wd_prob_prover(Res),well_def_analyser,POLabel,RT,WT), |
| 483 | | (WT>10 -> format('Proof of \'~w\' took ~w ms, result=~w (~w)~n',[POLabel,WT,Res,ProofTree]) |
| 484 | | %, translate:print_bexpr(_Target),nl, assertz(well_def_prover:dt),(prove_po(NT,Hyps,_) -> true ; true), trace |
| 485 | | ; true), |
| 486 | | Res=discharged. |
| 487 | | |
| 488 | | %:- use_module(well_def_hyps,[is_finite_type_for_wd/2]). |
| 489 | | obvious_po(b(finite(Set),pred,_),Hyps) :- |
| 490 | | get_texpr_type(Set,Type), % check this proof rule here, as prove_po has no longer types in the AST |
| 491 | | is_finite_type_for_wd(Type,Hyps). |
| 492 | | |
| 493 | | % ------------------------------ |
| 494 | | |
| 495 | | :- dynamic counter/2. |
| 496 | | reset_stats :- retractall(counter(_,_)), |
| 497 | | assertz(counter(discharged_po,0)), |
| 498 | | assertz(counter(not_discharged_po,0)). |
| 499 | | |
| 500 | | inc_counter(C) :- (retract(counter(C,Nr)) -> N1 is Nr+1 ; N1 = 1), |
| 501 | | assertz(counter(C,N1)). |
| 502 | | |
| 503 | | print_stats :- silent_mode(on),!. |
| 504 | | print_stats :- findall(C/N,counter(C,N),L), format('WD Stats: ~w~n',[L]). |
| 505 | | |
| 506 | | %tcltk_get_stats(list([list(['Category','Nr'])|Stats])) :- |
| 507 | | % findall(list([C,N]),counter(C,N),Stats). |
| 508 | | |
| 509 | | get_discharged_result(ResStr,D,Tot,AllDischarged) :- counter(not_discharged_po,ND), |
| 510 | | counter(discharged_po,D), Tot is ND+D, |
| 511 | | ajoin([D,'/',Tot,' DISCHARGED'],ResStr), |
| 512 | | (ND=0 -> AllDischarged='TRUE' ; AllDischarged='FALSE'). |
| 513 | | |
| 514 | | % ------------------------------ |
| 515 | | |
| 516 | | annotate_wd(TExpr,AnnotatedTExpr) :- |
| 517 | | reset_stats, |
| 518 | | %empty_hyps(EH), |
| 519 | | push_properties_invariant_hyps([],EH), |
| 520 | | Options = [discharge_po,insert_assertion_expressions], |
| 521 | | transform_wd(TExpr,EH,Options,AnnotatedTExpr), |
| 522 | | print_bexpr_with_wd_info(AnnotatedTExpr). |
| 523 | | |
| 524 | | |
| 525 | | :- use_module(probsrc(preferences),[temporary_set_preference/3, reset_temporary_preference/2, get_preference/2]). |
| 526 | | print_bexpr_with_wd_info(TExpr) :- |
| 527 | | temporary_set_preference(pp_wd_infos,true,Chng), |
| 528 | | call_cleanup(translate:nested_print_bexpr(TExpr),reset_temporary_preference(pp_wd_infos,Chng)), |
| 529 | | nl. |
| 530 | | |
| 531 | | % transform an AST by adding annotations about discharged POs |
| 532 | | transform_wd(b(Expr,Type,Info),Hypotheses,Options,b(NewExpr0,Type,NewInfo0)) :- |
| 533 | | memberchk(contains_wd_condition,Info), |
| 534 | | !, |
| 535 | | syntaxtransformation(Expr,Subs,TNames,NSubs,NewExpr), |
| 536 | | add_new_hyp_variables(Hypotheses,TNames,Hyps2), |
| 537 | | (wd_transparent(Expr) |
| 538 | | -> l_transform_wd(Subs,Hyps2,Options,NSubs), adapt_info(Info,NSubs,NewInfo) |
| 539 | | ; wd_like_conjunction(Expr,Ids,A,B) |
| 540 | | -> l_transform_conj_wd([A,B],Hyps2,Options,[TA,TB]), |
| 541 | | check_top_level_wd(conj,Expr,Type,Info,Hyps2,Options, [TA,TB], NewInfo,_), |
| 542 | | wd_like_conjunction(NewExpr,Ids,TA,TB) |
| 543 | ? | ; transform_special_expr(Expr,Type,Info,Hyps2,Options,NewExpr,NewInfo) -> true |
| 544 | | ; l_transform_wd(Subs,Hyps2,Options,NSubs) |
| 545 | | -> |
| 546 | | check_top_level_wd(other,Expr,Type,Info,Hyps2,Options, NSubs, NewInfo, PO) |
| 547 | | ), |
| 548 | | % PO is either a real PO or discharged atom |
| 549 | | insert_assertions(PO,NewExpr,Type,NewInfo,Options,NewExpr0,NewInfo0). |
| 550 | | transform_wd(TExpr,_,_,TExpr). % copy entire expression if no contains_wd_condition info |
| 551 | | |
| 552 | | insert_assertions(discharged,NewExpr,_,NewInfo,_,NewExpr0,NewInfo0) :- !, NewExpr0=NewExpr,NewInfo0=NewInfo. |
| 553 | | insert_assertions(_,NewExpr,pred,NewInfo,_,NewExpr0,NewInfo0) :- !, NewExpr0=NewExpr,NewInfo0=NewInfo. |
| 554 | | insert_assertions(_,NewExpr,subst,NewInfo,_,NewExpr0,NewInfo0) :- !, NewExpr0=NewExpr,NewInfo0=NewInfo. |
| 555 | | insert_assertions(_,NewExpr,_,NewInfo,Options,NewExpr0,NewInfo0) :- |
| 556 | | nonmember(insert_assertion_expressions,Options), !, NewExpr0=NewExpr,NewInfo0=NewInfo. |
| 557 | | %insert_assertions(PO,NewExpr,Type,NewInfo,_Options,NewExpr0) :- !, |
| 558 | | % BOOL_EXPR = b(convert_bool(PO),boolean,NewInfo), |
| 559 | | % MSG = b(string('WD-ERROR'),string,[]), |
| 560 | | % % TODO: adapt ASSERT_EXPR to delays & check more strongly than assertion_expression |
| 561 | | % NewExpr0 = external_function_call('ASSERT_EXPR',[BOOL_EXPR,MSG, b(NewExpr,Type,NewInfo)]). |
| 562 | | insert_assertions(PO,NewExpr,Type,NewInfo,_Options,NewExpr0,NewInfo0) :- |
| 563 | | NewInfo0 = [prob_annotation(strong_check_with_delay)|NewInfo], % ensure we really guard the Expression |
| 564 | | % example usage in repl :wde f = [1,2,3,4,5] & f(x)=6 & x>6 |
| 565 | | % TODO: improve error message, stipulating at least the operator for which the PO is added |
| 566 | | % also check that we are not adding an assert for an assert |
| 567 | | NewExpr0 = assertion_expression(PO,'WD-ERROR', b(NewExpr,Type,NewInfo)). |
| 568 | | |
| 569 | | |
| 570 | | check_top_level_wd(conj,Expr,Type,Info,Hyps,Options, _NSubs, NewInfo, FullPO) :- |
| 571 | | Discharged=false, |
| 572 | | findall(PO,create_top_level_wd_po_conj_like(Expr,Type,Info,Hyps,Options,PO,Discharged),POs), |
| 573 | | POs \= [], |
| 574 | | !, % PO not proven; keep Info as is |
| 575 | | %write(-), flush_output, %print(not_discharged(PO)),nl, |
| 576 | | conjunct_predicates(POs,FullPO), |
| 577 | | NewInfo=Info. |
| 578 | | check_top_level_wd(other,Expr,Type,Info,Hyps,Options, _NSubs, NewInfo, FullPO) :- |
| 579 | | Discharged=false, |
| 580 | | findall(PO,create_top_level_wd_po(Expr,Type,Info,Hyps,Options,PO,Discharged),POs), |
| 581 | | POs \= [], |
| 582 | | !, % PO not proven; keep Info as is |
| 583 | | %write(-), flush_output, print(not_discharged(PO)),nl, |
| 584 | | conjunct_predicates(POs,FullPO), |
| 585 | | NewInfo=Info. |
| 586 | | check_top_level_wd(_,_Expr,_Type,Info,_Hyps,_Options, NSubs, NewInfo, discharged) :- % no top-level PO or PO proven |
| 587 | | adapt_info(Info,NSubs,NewInfo). |
| 588 | | |
| 589 | | %:- use_module(library(lists),[delete/3]). |
| 590 | | % adapt WD Info depending on result of analysis |
| 591 | ? | adapt_info(Info,Subs,NewInfo) :- subs_contain_wd_condition(Subs),!,NewInfo=Info. |
| 592 | | adapt_info(Info,_,[discharged_wd_po|NewInfo]) :- |
| 593 | | NewInfo=Info, memberchk(contains_wd_condition,Info). |
| 594 | | %delete(Info,contains_wd_condition,NewInfo). |
| 595 | | |
| 596 | | subs_contain_wd_condition(Subs) :- |
| 597 | ? | member(b(_,_,Infos),Subs), |
| 598 | | (memberchk(contains_wd_condition,Infos) -> nonmember(discharged_wd_po,Infos)). |
| 599 | | |
| 600 | | % transform independent sub-arguments |
| 601 | | l_transform_wd([],_Hyps,_Options,[]). |
| 602 | | l_transform_wd([Sub|T],Hyps,Options,[NSub|NT]) :- |
| 603 | | transform_wd(Sub,Hyps,Options,NSub), |
| 604 | | l_transform_wd(T,Hyps,Options,NT). |
| 605 | | |
| 606 | | % transform conjunction like sub-arguments, with left-to-right adding of hypotheses |
| 607 | | l_transform_conj_wd([],_Hyps,_Options,[]). |
| 608 | | l_transform_conj_wd([Sub|T],Hyps,Options,[NSub|NT]) :- |
| 609 | | transform_wd(Sub,Hyps,Options,NSub), |
| 610 | | push_hyp(Hyps,Sub,Options,Hyps2), |
| 611 | | l_transform_conj_wd(T,Hyps2,Options,NT). |
| 612 | | |
| 613 | | % transform special cases where sub-arguments are not independent nor conjunction-like |
| 614 | | % TO DO: assign |
| 615 | | transform_special_expr(disjunct(A,B),_,Info,Hyps,Options,disjunct(TA,TB),NewInfo) :- |
| 616 | | transform_wd(A,Hyps,Options,TA), |
| 617 | | negate_hyp(A,NA), |
| 618 | | push_hyp(Hyps,NA,Options,Hyps2), |
| 619 | | transform_wd(B,Hyps2,Options,TB), |
| 620 | | adapt_info(Info,[TA,TB],NewInfo). |
| 621 | | transform_special_expr(IFTE,_,Info,Hyps,Options,TransformedIFTE,NewInfo) :- |
| 622 | | is_ifte(IFTE,Functor,A,B,C), is_ifte(TransformedIFTE,Functor,TA,TB,TC), |
| 623 | | transform_wd(A,Hyps,Options,TA), |
| 624 | | push_hyp(Hyps,A,Options,Hyps2), |
| 625 | | transform_wd(B,Hyps2,Options,TB), |
| 626 | | negate_hyp(A,NA), |
| 627 | | push_hyp(Hyps,NA,Options,Hyps3), |
| 628 | | transform_wd(C,Hyps3,Options,TC), |
| 629 | | adapt_info(Info,[TA,TB,TC],NewInfo). |
| 630 | | transform_special_expr(recursive_let(ID,B),_,Info,Hyps,Options,recursive_let(ID,TB),NewInfo) :- NewInfo=Info, |
| 631 | | transform_wd(B,Hyps,Options,TB). |
| 632 | | transform_special_expr(general_sum(Ids,P,E),_Type,Info,Hyps,Options,general_sum(Ids,TP,TE),NewInfo) :- |
| 633 | | NewInfo=Info, % Note: we do not try to discharge finite PO; TODO: add |
| 634 | | transform_wd(P,Hyps,Options,TP), |
| 635 | | push_hyp(Hyps,P,Options,Hyps2), |
| 636 | | transform_wd(E,Hyps2,Options,TE). |
| 637 | | transform_special_expr(general_product(Ids,P,E),_Type,Info,Hyps,Options,general_product(Ids,TP,TE),NewInfo) :- |
| 638 | | NewInfo=Info, % Note: we do not try to discharge finite PO |
| 639 | | transform_wd(P,Hyps,Options,TP), |
| 640 | | push_hyp(Hyps,P,Options,Hyps2), |
| 641 | | transform_wd(E,Hyps2,Options,TE). |
| 642 | | transform_special_expr(if(List),_,Info,Hyps,Options,if(TList),NewInfo) :- |
| 643 | | list_transform_if_elsif_wd(List,Hyps,Options,TList), |
| 644 | | adapt_info(Info,TList,NewInfo). |
| 645 | | |
| 646 | | list_transform_if_elsif_wd([],_,_,[]). |
| 647 | | list_transform_if_elsif_wd([b(if_elsif(A,Body),Type,I) | T], Hyps,Options,Res) :- |
| 648 | | is_truth(A),!, |
| 649 | | Res=[b(if_elsif(A,TBody),Type,I) | T], |
| 650 | | transform_wd(Body,Hyps,Options,TBody). |
| 651 | | list_transform_if_elsif_wd([b(if_elsif(A,Body),Type,I) | T], Hyps,Options, |
| 652 | | [b(if_elsif(TA,TBody),Type,I) | TT]) :- |
| 653 | | transform_wd(A,Hyps,Options,TA), |
| 654 | | push_hyp(Hyps,A,Options,Hyps2), |
| 655 | | transform_wd(Body,Hyps2,Options,TBody), |
| 656 | | negate_hyp(A,NA), |
| 657 | | push_hyp(Hyps,NA,Options,Hyps3), |
| 658 | | list_transform_if_elsif_wd(T,Hyps3,Options,TT). |
| 659 | | |
| 660 | | % ------------------------------ |
| 661 | | |
| 662 | | :- use_module(probsrc(bsyntaxtree),[conjunction_to_list/2]). |
| 663 | | :- use_module(probsrc(tools),[split_list/4]). |
| 664 | | |
| 665 | | % process those conjuncts with no WD condition first; this means we have more hypotheses for proving and is safe for ProB |
| 666 | | % Option 'skip_finite_po' can be used to not generate finite(.) POs. |
| 667 | | % These POs are, e.g., irrelevant for constraint solving in ProB since the solver would exceed the timeout if finite(.) cannot be proven. |
| 668 | | compute_wd_with_reordering(TExpr,Hypotheses,Options,PO) :- \+ ord_member(reorder_conjuncts,Options),!, |
| 669 | | compute_wd(TExpr,Hypotheses,Options,PO). |
| 670 | | compute_wd_with_reordering(TExpr,Hypotheses,Options,PO) :- |
| 671 | | conjunction_to_list(TExpr,Conjuncts), |
| 672 | | split_list(is_well_defined_conjunct,Conjuncts,Conj1,Conj2), |
| 673 | | Conj2 \= [], % otherwise no WD condition anyway |
| 674 | | (ord_member(ignore_wd_infos,Options) |
| 675 | | -> append(Conj1,Conj2,Conj12), |
| 676 | ? | list_compute_wd(Conj12,Options,Hypotheses,PO) |
| 677 | | ; push_hyps(Hypotheses,Conj1,Options,Hyps2), % push the Hypotheses without WD checking |
| 678 | | list_compute_wd(Conj2,Options,Hyps2,PO) |
| 679 | | ). |
| 680 | | |
| 681 | | %is_well_defined_conjunct(TE) :- print('Checking conjunct: '), translate:print_bexpr(TE),nl,fail. |
| 682 | | is_well_defined_conjunct(b(_,_,Infos)) :- nonmember(contains_wd_condition,Infos),!. |
| 683 | | %is_well_defined_conjunct(TE) :- print('Not well defined: '), translate:print_bexpr(TE),nl,fail. |
| 684 | | |
| 685 | | compute_wd(TExpr,Hypotheses,Options,PO) :- |
| 686 | | syntaxtraversion(TExpr,Expr,Type,Infos,Subs,TNames), |
| 687 | | (ord_member(ignore_wd_infos,Options) -> true ; memberchk(contains_wd_condition,Infos) -> true), |
| 688 | | %(print(Expr),nl ; print(backtrack(Expr)),nl,fail), |
| 689 | ? | (get_info_labels(Infos,Label) -> ord_add_element(Options,po_label(Label),Opt2) ; Opt2=Options), |
| 690 | ? | compute_wd_aux(Expr,Type,Infos,Subs,TNames,Hypotheses,Opt2,PO), |
| 691 | | true. %check_if_po_expected(PO,TExpr,Infos). |
| 692 | | |
| 693 | | check_if_po_expected(PO,TExpr,Infos) :- |
| 694 | | ( memberchk(contains_wd_condition,Infos) -> true |
| 695 | | ; get_texpr_info(PO,POInfo), POInfo=[discharged(true,_)|_] -> true |
| 696 | | % Note: Sigma currently gets no contains_wd_condition, but has finiteness WD constraint |
| 697 | | ; add_error(well_def_analyser,'Unexpected WD-PO for expression marked to have no WD condition:',PO,TExpr) |
| 698 | | ). |
| 699 | | |
| 700 | | :- use_module(library(lists),[maplist/3]). |
| 701 | | % treat assignment substitution |
| 702 | | % see b_assign_values_or_functions in b_interpreter |
| 703 | | compute_wd_assign(Hyps,Options,PO,LHS,RHS) :- LHS=b(function(F,X),_,_), |
| 704 | | !, |
| 705 | | % special case for f(X) := RHS |
| 706 | | ( compute_wd(F,Hyps,Options,PO) % ? |
| 707 | | ; compute_wd(X,Hyps,Options,PO) |
| 708 | ? | ; compute_wd(RHS,Hyps,Options,PO) ). |
| 709 | | compute_wd_assign(Hyps,Options,PO,_,RHS) :- % LHS must be an identifier |
| 710 | ? | compute_wd(RHS,Hyps,Options,PO). |
| 711 | | |
| 712 | | compute_wd_aux(assign(LHSList,RHSList),_,_,_,[],Hypotheses,Options,PO) :- |
| 713 | | !, |
| 714 | ? | maplist(compute_wd_assign(Hypotheses,Options,PO),LHSList,RHSList). |
| 715 | | compute_wd_aux(Expr,_,_,Subs,TNames,Hypotheses,Options,PO) :- |
| 716 | | wd_transparent(Expr),!, |
| 717 | | % cut: only look at WD condition of all sub-arguments |
| 718 | | add_new_hyp_variables(Hypotheses,TNames,Hyps2), |
| 719 | ? | member(Sub,Subs), |
| 720 | ? | compute_wd(Sub,Hyps2,Options,PO). |
| 721 | | % Now the rules which do not look at all sub-arguments with original Hypotheses: |
| 722 | | compute_wd_aux(conjunct(A,B),_,_,_,_,Hypotheses,Options,PO) :- !, |
| 723 | | flatten_conjunct(A,B,List), % avoid re-pushing hyps if A is nested conjunct |
| 724 | ? | compute_wd_conjuncts(List,Hypotheses,Options,PO). |
| 725 | | compute_wd_aux(sequence(List),subst,_,_,_,Hypotheses,Options,PO) :- % sequential composition |
| 726 | | !, |
| 727 | ? | sequence_compute_wd(List,Options,Hypotheses,PO). |
| 728 | | compute_wd_aux(while(COND,STMT,INV,VARIANT),_,Infos,_,_,Hypotheses,Options,PO) :- !, |
| 729 | | (member(modifies(VarsModified),Infos) -> debug_println(9,computed_wd_while(VarsModified)) |
| 730 | | ; add_error(well_def_analyser,'While does not contain modifies info:',Infos,Infos), |
| 731 | | VarsModified=[] |
| 732 | | ), |
| 733 | | copy_hyp_variables(Hypotheses,VarsModified,Hyps2), % we can no longer make any assumption about the modified vars |
| 734 | | % this corresponds to a universal quantification |
| 735 | | ( compute_wd(INV,Hyps2,Options,PO) % Invariant must hold before and after WHILE loop |
| 736 | | ; |
| 737 | | push_hyp(Hyps2,INV,Options,Hyps3), % add INV to the hypotheses now for the other parts of the WHILE |
| 738 | | ( |
| 739 | | compute_wd(COND,Hyps3,Options,PO) |
| 740 | | ; |
| 741 | | compute_wd(VARIANT,Hyps3,Options,PO) % NAT proof rule for While must also hold if P is false according to Atelier-B handbook (otherwise we could have pushed COND onto the stack) |
| 742 | | ; |
| 743 | | push_hyp(Hyps3,COND,Options,Hyps4), |
| 744 | | compute_wd(STMT,Hyps4,Options,PO) % Statement is only executed if COND is true; INV is checked |
| 745 | | ) |
| 746 | | ). |
| 747 | | compute_wd_aux(Expr,Type,Infos,Subs,TNames,Hypotheses,Options,PO) :- |
| 748 | | wd_like_conjunction(Expr,_,A,B),!, |
| 749 | | add_new_hyp_variables(Hypotheses,TNames,Hyps2), |
| 750 | | ( create_top_level_wd_po_conj_like(Expr,Type,Infos,Hyps2,Options,PO,_Discharged) % e.g., for assertion_expression |
| 751 | | ; |
| 752 | ? | compute_wd_aux(conjunct(A,B),Type,Infos,Subs,TNames,Hyps2,Options,PO) |
| 753 | | ). |
| 754 | | compute_wd_aux(if(List),_,_,_,_,Hypotheses,Options,PO) :- !, |
| 755 | ? | list_compute_if_elsif_wd(List,Hypotheses,Options,PO). |
| 756 | | compute_wd_aux(disjunct(A,B),_,_,_,_,Hypotheses,Options,PO) :- !, |
| 757 | ? | (compute_wd(A,Hypotheses,Options,PO) |
| 758 | | ; |
| 759 | | negate_hyp(A,NA), |
| 760 | | push_hyp(Hypotheses,NA,Options,NewHyp), |
| 761 | ? | compute_wd(B,NewHyp,Options,PO)). |
| 762 | | compute_wd_aux(general_sum(Ids,P,E),Type,Infos,_,_,Hypotheses,Options,PO) :- !, % SIGMA, real or integer |
| 763 | | ( % first the sub arguments |
| 764 | | add_new_hyp_variables(Hypotheses,Ids,Hyps2), |
| 765 | | ( compute_wd(P,Hyps2,Options,PO) |
| 766 | | ; |
| 767 | | push_hyp(Hyps2,P,Options,NewHyp), |
| 768 | ? | compute_wd(E,NewHyp,Options,PO) |
| 769 | | ) |
| 770 | | ; % now the PO of general_sum itself |
| 771 | | create_top_level_wd_po(general_sum(Ids,P,E),Type,Infos,Hypotheses,Options,PO,_Discharged) |
| 772 | | ). |
| 773 | | compute_wd_aux(general_product(Ids,P,E),Type,Infos,Subs,TNames,Hypotheses,Options,PO) :- !, % PI |
| 774 | ? | compute_wd_aux(general_sum(Ids,P,E),Type,Infos,Subs,TNames,Hypotheses,Options,PO). |
| 775 | | compute_wd_aux(rlevent(_Name,_Sect,_Status,_Params,Guard,Theorems,Actions,VWit,PWit,_Unmod,_AbstractEvents), |
| 776 | | _,_Infos,_Subs,TNames,Hypotheses,Options,PO) :- !, |
| 777 | | add_new_hyp_variables(Hypotheses,TNames,Hyps2), |
| 778 | | % TO DO: treat nested lists VWit,... |
| 779 | | Act = b(parallel(Actions),subst,[]), |
| 780 | | append([[Guard],Theorems,VWit,PWit,[Act]],List), |
| 781 | ? | list_compute_wd(List,Options,Hyps2,PO). |
| 782 | | compute_wd_aux(recursive_let(_ID,Body),_,_,_,_,Hypotheses,Options,PO) :- !, |
| 783 | | % the ID does not have to be added to hypothesis stack ! |
| 784 | ? | compute_wd(Body,Hypotheses,Options,PO). |
| 785 | | compute_wd_aux(IFTE,_,_,_,_,Hypotheses,Options,PO) :- is_ifte(IFTE,_,A,B,C), !, |
| 786 | ? | (compute_wd(A,Hypotheses,Options,PO) |
| 787 | | ; |
| 788 | | push_hyp(Hypotheses,A,Options,NewHyp), |
| 789 | | compute_wd(B,NewHyp,Options,PO) |
| 790 | | ; |
| 791 | | negate_hyp(A,NA), |
| 792 | | push_hyp(Hypotheses,NA,Options,NewHyp), |
| 793 | ? | compute_wd(C,NewHyp,Options,PO)). |
| 794 | | % ---------------- |
| 795 | | % Now the rules where we also look at the sub-arguments with original Hypotheses: |
| 796 | | compute_wd_aux(_,_,_,Subs,TNames,Hypotheses,Options,PO) :- |
| 797 | | add_new_hyp_variables(Hypotheses,TNames,Hyp2), |
| 798 | | % look at WD condition of all sub-arguments independently |
| 799 | ? | member(Sub,Subs), |
| 800 | ? | compute_wd(Sub,Hyp2,Options,PO). |
| 801 | | % Now the specific rules: |
| 802 | | compute_wd_aux(Expr,Type,Infos,_,_,Hypotheses,Options,PO) :- |
| 803 | ? | create_top_level_wd_po(Expr,Type,Infos,Hypotheses,Options,PO,_Discharged). |
| 804 | | |
| 805 | | % treat a list of conjuncts (after flattening) |
| 806 | | %compute_wd_conjuncts([],_,_,_) :- fail. |
| 807 | | compute_wd_conjuncts([A|T],Hypotheses,Options,PO) :- |
| 808 | ? | (compute_wd(A,Hypotheses,Options,PO) |
| 809 | | ; |
| 810 | | T \= [], |
| 811 | | push_hyp(Hypotheses,A,Options,NewHyp), |
| 812 | ? | compute_wd_conjuncts(T,NewHyp,Options,PO)). |
| 813 | | |
| 814 | | % flatten conjuncts to avoid re-pushing the same hypotheses |
| 815 | | flatten_conjunct(ConjA,ConjB,List) :- |
| 816 | | flatten_conjunct_dl(ConjA,List,[ConjB]). % Tail not flattened; not necessary for performance |
| 817 | | flatten_conjunct_dl(b(conjunct(A,B),_,_)) --> !, flatten_conjunct_dl(A), flatten_conjunct_dl(B). |
| 818 | | flatten_conjunct_dl(X) --> [X]. |
| 819 | | |
| 820 | | is_ifte(if_then_else(A,B,C),if_then_else,A,B,C). |
| 821 | | is_ifte(if_predicate(A,B,C),if_predicate,A,B,C). |
| 822 | | |
| 823 | | % create top-level WD conditions for conjunction-like operators; not for sub-arguments |
| 824 | | % conjunction like operators can use the fact that LHS is true to prove WD of RHS |
| 825 | | % but here we only worry about additional top-level POs by the operator |
| 826 | | % the predicate must create a single full top-level PO and not succeed upon backtracking |
| 827 | | create_top_level_wd_po_conj_like(assertion_expression(A,_Msg,_),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 828 | | Target = A, |
| 829 | | ord_add_element(Options,po_label('ASSERT'),Options2), |
| 830 | | create_po(Hypotheses,Target,Infos,Options2,PO,Discharged). |
| 831 | | |
| 832 | | % create top-level WD conditions; not for sub-arguments |
| 833 | | create_top_level_wd_po(function(A,B),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 834 | | (get_texpr_type(B,TB), |
| 835 | | safe_create_texpr(domain(A),set(TB),[],DomA), |
| 836 | | safe_create_texpr(member(B,DomA),pred,[],Target), |
| 837 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged) |
| 838 | | %, tools_printing:print_term_summary(created_function_po(Target,PO)) |
| 839 | | ; |
| 840 | | create_partial_fun_target(A,Target), |
| 841 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged) |
| 842 | | ). |
| 843 | | create_top_level_wd_po(div(_,B),integer,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 844 | | create_texpr(integer(0),integer,[],Zero), |
| 845 | | safe_create_texpr(not_equal(B,Zero),pred,[],Target), |
| 846 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 847 | | create_top_level_wd_po(div_real(_,B),real,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 848 | | create_texpr(real('0.0'),real,[],Zero), |
| 849 | | safe_create_texpr(not_equal(B,Zero),pred,[],Target), |
| 850 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 851 | | create_top_level_wd_po(floored_div(_,B),integer,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 852 | | create_texpr(integer(0),integer,[],Zero), |
| 853 | | safe_create_texpr(not_equal(B,Zero),pred,[],Target), |
| 854 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 855 | | create_top_level_wd_po(modulo(A,B),integer,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 856 | | create_texpr(integer(0),integer,[],Zero), |
| 857 | | ( safe_create_texpr(greater(B,Zero),pred,[],Target), % does TLA require this to be positive?? |
| 858 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged) |
| 859 | | ; \+ z_or_tla_minor_mode, |
| 860 | | safe_create_texpr(greater_equal(A,Zero),pred,[],Target), % in B A must be positive |
| 861 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged) |
| 862 | | ). |
| 863 | | create_top_level_wd_po(power_of(A,B),integer,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 864 | | create_texpr(integer(0),integer,[],Zero), |
| 865 | | ( AB=B, % B >= 0 must hold in B and Event-B |
| 866 | | safe_create_texpr(greater_equal(AB,Zero),pred,[],Target), |
| 867 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged) |
| 868 | | ; eventb_mode, % TO DO: what happens in Z and TLA+? |
| 869 | | AB=A, % A >= 0 must hold in Event-B |
| 870 | | safe_create_texpr(greater_equal(AB,Zero),pred,[],Target), |
| 871 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged) |
| 872 | | ). |
| 873 | | create_top_level_wd_po(power_of_real(A,B),real,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 874 | | % power_of_real has a WD condition, real ** integer has not |
| 875 | | create_texpr(real('0.0'),real,[],Zero), |
| 876 | | ( % A < 0 => real(floor(B))=B |
| 877 | | safe_create_texpr(less_real(A,Zero),pred,[],LHS), |
| 878 | | safe_create_texpr(convert_int_floor(B),integer,[],FloorB), |
| 879 | | safe_create_texpr(convert_real(FloorB),real,[],BB), |
| 880 | | safe_create_texpr(equal(B,BB),pred,[],RHS), |
| 881 | | safe_create_texpr(implication(LHS,RHS),pred,[],Target), |
| 882 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged) |
| 883 | | ; % A = 0 => B >= 0 |
| 884 | | safe_create_texpr(equal(A,Zero),pred,[],LHS), |
| 885 | | safe_create_texpr(less_equal_real(Zero,B),pred,[],RHS), |
| 886 | | safe_create_texpr(implication(LHS,RHS),pred,[],Target), |
| 887 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged) |
| 888 | | ). |
| 889 | | create_top_level_wd_po(iteration(_Rel,Index),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 890 | | create_texpr(integer(0),integer,[],Zero), |
| 891 | | safe_create_texpr(greater_equal(Index,Zero),pred,[],Target), |
| 892 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 893 | | create_top_level_wd_po(card(S),integer,Infos,Hypotheses,Options,PO,Discharged) :- |
| 894 | | !, |
| 895 | | \+ skip_finite_pos(Options), |
| 896 | | safe_create_texpr(finite(S),pred,[contains_wd_condition],Target), |
| 897 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 898 | | create_top_level_wd_po(max(S),integer,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 899 | | get_texpr_type(S,TS), |
| 900 | | safe_create_texpr(not_equal(S,b(empty_set,TS,[])),pred,[],Target1), |
| 901 | | ( skip_finite_pos(Options) |
| 902 | | -> Target = Target1 |
| 903 | | ; safe_create_texpr(finite(S),pred,[contains_wd_condition],Target2), |
| 904 | | conjunct_predicates([Target1,Target2],Target) % this is a sufficient condition, not a necessary one |
| 905 | | ), |
| 906 | | % create a single PO, because of use in check_top_level_wd |
| 907 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 908 | | create_top_level_wd_po(min(S),integer,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 909 | | get_texpr_type(S,TS), |
| 910 | | safe_create_texpr(not_equal(S,b(empty_set,TS,[])),pred,[],Target1), |
| 911 | | ( skip_finite_pos(Options) |
| 912 | | -> Target = Target1 |
| 913 | | ; safe_create_texpr(finite(S),pred,[contains_wd_condition],Target2), |
| 914 | | conjunct_predicates([Target1,Target2],Target) % this is a sufficient condition, not a necessary one |
| 915 | | ), |
| 916 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 917 | | create_top_level_wd_po(max_real(S),real,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 918 | | create_top_level_wd_po(max(S),integer,Infos,Hypotheses,Options,PO,Discharged). % create same PO as for integer max |
| 919 | | create_top_level_wd_po(min_real(S),real,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 920 | | create_top_level_wd_po(min(S),integer,Infos,Hypotheses,Options,PO,Discharged). % ditto |
| 921 | | create_top_level_wd_po(general_intersection(A),TA,Infos,Hypotheses,Options,PO,Discharged) :- !, % inter |
| 922 | | safe_create_texpr(not_equal(A,b(empty_set,set(TA),[])),pred,[],Target), |
| 923 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 924 | | % Sequence operators: |
| 925 | | create_top_level_wd_po(size(S),integer,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 926 | | % we do not have to create a finite PO: sequences are by construction finite |
| 927 | | create_sequence_target(S,Target), |
| 928 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 929 | | create_top_level_wd_po(insert_tail(S,_),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 930 | | create_sequence_target(S,Target), create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 931 | | create_top_level_wd_po(insert_front(_,S),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 932 | | % page 174 of Abrial's book just requires that S is a partial function NATURAL1 +-> TYPE |
| 933 | | create_sequence_target(S,Target), create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 934 | | create_top_level_wd_po(rev(S),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 935 | | create_sequence_target(S,Target), create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 936 | | create_top_level_wd_po(concat(S1,S2),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 937 | | (create_sequence_target(S1,Target) ; create_sequence_target(S2,Target)), |
| 938 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 939 | | create_top_level_wd_po(general_concat(S),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 940 | | create_seq_seq_target(S,Target), create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 941 | | create_top_level_wd_po(first(S),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 942 | | create_sequence1_target(S,Target), create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 943 | | create_top_level_wd_po(last(S),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 944 | | create_sequence1_target(S,Target), create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 945 | | create_top_level_wd_po(front(S),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 946 | | create_sequence1_target(S,Target), create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 947 | | create_top_level_wd_po(tail(S),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 948 | | create_sequence1_target(S,Target), create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 949 | | create_top_level_wd_po(restrict_front(S,N),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 950 | | ( create_sequence_target(S,Target) ; create_seq_interval_target(S,N,Target) ), |
| 951 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 952 | | create_top_level_wd_po(restrict_tail(S,N),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 953 | | ( create_sequence_target(S,Target) ; create_seq_interval_target(S,N,Target) ), |
| 954 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 955 | | create_top_level_wd_po(mu(S),_,Infos,Hypotheses,Options,PO,Discharged) :- !, % Z MU Operator |
| 956 | | get_texpr_type(S,TS), |
| 957 | | safe_create_texpr(not_equal(S,b(empty_set,TS,[])),pred,[],Target1), |
| 958 | | create_texpr(integer(1),integer,[],One), |
| 959 | | safe_create_texpr(card(S),integer,[contains_wd_condition],CardS), |
| 960 | | safe_create_texpr(less_equal(CardS,One),pred,[],Target2), |
| 961 | | ( skip_finite_pos(Options) |
| 962 | | -> conjunct_predicates([Target1,Target2],Target) |
| 963 | | ; safe_create_texpr(finite(S),pred,[contains_wd_condition],Target3), |
| 964 | | conjunct_predicates([Target1,Target3,Target2],Target) |
| 965 | | ), |
| 966 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 967 | | % External Functions: |
| 968 | | create_top_level_wd_po(external_function_call('MU',[S]),T,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 969 | | create_top_level_wd_po(mu(S),T,Infos,Hypotheses,Options,PO,Discharged). |
| 970 | | create_top_level_wd_po(external_function_call('CHOOSE',[A]),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 971 | | get_texpr_type(A,TA), |
| 972 | | safe_create_texpr(not_equal(A,b(empty_set,set(TA),[])),pred,[],Target), |
| 973 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 974 | | create_top_level_wd_po(external_function_call('SQUASH',[A]),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 975 | | create_partial_fun_target(A,Target), |
| 976 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 977 | | create_top_level_wd_po(external_function_call(C,Args),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 978 | | % external_fun_has_wd_condition is true |
| 979 | | get_preference(wd_ignore_external_funs,false), |
| 980 | | create_wd_po_for_external_call(C,Args,Infos,Hypotheses,Options,PO,Discharged). |
| 981 | | create_top_level_wd_po(external_subst_call(C,_),_,Infos,Hypotheses,Options,PO,Discharged) :- !, % ditto |
| 982 | | get_preference(wd_ignore_external_funs,false), |
| 983 | | create_po(Hypotheses,b(unknown_truth_value(C),pred,[]),Infos,Options,PO,Discharged). |
| 984 | | create_top_level_wd_po(external_pred_call(C,Args),_,Infos,Hypotheses,Options,PO,Discharged) :- !, % ditto |
| 985 | | get_preference(wd_ignore_external_funs,false), |
| 986 | | create_wd_po_for_external_call(C,Args,Infos,Hypotheses,Options,PO,Discharged). |
| 987 | | create_top_level_wd_po(general_product(Ids,P,E),Type,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 988 | | create_top_level_wd_po(general_sum(Ids,P,E),Type,Infos,Hypotheses,Options,PO,Discharged). |
| 989 | | create_top_level_wd_po(general_sum(Ids,P,_E),_,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 990 | | \+ skip_finite_pos(Options), |
| 991 | | create_comprehension_set(Ids,P,[],TS), |
| 992 | | safe_create_texpr(finite(TS),pred,[contains_wd_condition],Target), |
| 993 | | create_po(Hypotheses,Target,Infos,Options,PO,Discharged). |
| 994 | | % Unsupported: |
| 995 | | create_top_level_wd_po(Expr,T,I,Hypotheses,Options,PO,Discharged) :- |
| 996 | | functor(Expr,F,N), |
| 997 | | ajoin(['Unsupported expression ',F,'/',N,': '],Msg), |
| 998 | | (ord_member_nonvar_chk(create_not_discharged_msg(MsgType),Options) |
| 999 | | -> (MsgType=silent -> true ; add_message(well_def_analyser,Msg,Expr,I)) % we create warning below |
| 1000 | | ; known_to_be_unsupported(F,N) |
| 1001 | | -> add_warning(well_def_analyser,Msg,Expr,I) |
| 1002 | | ; wd_transparent(Expr) |
| 1003 | | -> add_error(well_def_analyser,Msg,'transparent operator has no top-level WD condition',I) |
| 1004 | | ; (wd_like_conjunction(Expr,_,_,_) ; Expr=disjunct(_,_) ; Expr=if_predicate(_,_,_)) |
| 1005 | | -> add_error(well_def_analyser,Msg,'operator has no top-level WD condition',I) |
| 1006 | | ; add_internal_error(Msg,create_top_level_wd_po(Expr,T,I,_,Options,PO,Discharged)) |
| 1007 | | ), |
| 1008 | | inc_counter(unsupported), |
| 1009 | | create_po(Hypotheses,b(unknown_truth_value(F),pred,[wd(Expr)]),I,Options,PO,Discharged). |
| 1010 | | |
| 1011 | | % Note: % if wd_ignore_external_funs is true the WD POs will not be created |
| 1012 | | % This may be ok for ASSERT, under the assumption that ProB will check those ASSERTS at runtime |
| 1013 | | % In this way we can instrument a model with ASSERT_TRUE/ASSERT_EXPR and be sure that all WD issues will be detected |
| 1014 | | create_wd_po_for_external_call('ASSERT_TRUE',[BOOL_EXPR,_ErrString],Infos,Hypotheses,Options,PO,Discharged) :- |
| 1015 | | extract_assert_predicate(BOOL_EXPR,Pred),!, |
| 1016 | | create_po(Hypotheses,Pred,Infos,Options,PO,Discharged). |
| 1017 | | create_wd_po_for_external_call('ASSERT_EXPR',[BOOL_EXPR,_ErrString,_E],Infos,Hypotheses,Options,PO,Discharged) :- |
| 1018 | | extract_assert_predicate(BOOL_EXPR,Pred),!, |
| 1019 | | create_po(Hypotheses,Pred,Infos,Options,PO,Discharged). |
| 1020 | | create_wd_po_for_external_call(C,_Args,Infos,Hypotheses,Options,PO,Discharged) :- !, |
| 1021 | | create_po(Hypotheses,b(unknown_truth_value(C),pred,[]),Infos,Options,PO,Discharged). |
| 1022 | | |
| 1023 | | skip_finite_pos(Options) :- |
| 1024 | | (get_preference(wd_skip_finite_pos,true) -> true |
| 1025 | | ; ord_member(skip_finite_po, Options)). |
| 1026 | | |
| 1027 | | known_to_be_unsupported(freetype_destructor,3). % has WD condition, see check_freetype_case in b_interpreter |
| 1028 | | known_to_be_unsupported(lazy_let_expr,3). |
| 1029 | | known_to_be_unsupported(lazy_let_pred,3). |
| 1030 | | known_to_be_unsupported(lazy_let_subst,3). |
| 1031 | | known_to_be_unsupported(quantified_intersection,3). |
| 1032 | | |
| 1033 | | create_partial_fun_target(A,Target) :- |
| 1034 | | % see create_function_check in bvisual2 |
| 1035 | | get_texpr_type(A,TA), is_set_type(TA,couple(TDom,TRan)), |
| 1036 | | create_type_set(TDom,TDT), % we could also use create_maximal_type_set/2 |
| 1037 | | create_type_set(TRan,TRT), |
| 1038 | | safe_create_texpr(partial_function(TDT,TRT),set(TA),[],PF), |
| 1039 | | safe_create_texpr(member(A,PF),pred,[],Target). |
| 1040 | | |
| 1041 | | :- use_module(probsrc(bsyntaxtree),[is_set_type/2]). |
| 1042 | | % get texpr for set of all sequences: |
| 1043 | | create_seq_type_expr(Seq,Sequences) :- |
| 1044 | | get_texpr_type(Seq,ST), |
| 1045 | | is_set_type(ST,couple(_,TRan)), |
| 1046 | | create_type_set(TRan,TRT), |
| 1047 | | safe_create_texpr(seq(TRT),set(ST),[],Sequences). |
| 1048 | | create_seq1_type_expr(Seq,Sequences) :- |
| 1049 | | get_texpr_type(Seq,ST), |
| 1050 | | is_set_type(ST,couple(_,TRan)), |
| 1051 | | create_type_set(TRan,TRT), |
| 1052 | | safe_create_texpr(seq1(TRT),set(ST),[],Sequences). |
| 1053 | | create_seq_seq_type_expr(SeqSeq,SequencesOfSequences) :- |
| 1054 | | get_texpr_type(SeqSeq,SST), |
| 1055 | | is_set_type(SST,couple(_,SeqT)), % SeqT = type of the inner sequences |
| 1056 | | is_set_type(SeqT,couple(_,TRan)), % TRan is type elements in the inner sequence |
| 1057 | | create_type_set(TRan,TRT1), |
| 1058 | | safe_create_texpr(seq(TRT1),set(SeqT),[],Sequences), |
| 1059 | | safe_create_texpr(seq(Sequences),set(SST),[],SequencesOfSequences). |
| 1060 | | |
| 1061 | | create_type_set(boolean,Res) :- !, Res=b(bool_set,set(boolean),[]). % custom rule not necessary |
| 1062 | | create_type_set(integer,Res) :- !, Res=b(integer_set('INTEGER'),set(integer),[]). |
| 1063 | | create_type_set(string,Res) :- !, Res=b(string_set,set(string),[]). |
| 1064 | | create_type_set(Type,Res) :- create_texpr(typeset,set(Type),[],Res). |
| 1065 | | |
| 1066 | | create_sequence_target(S,Target) :- |
| 1067 | | create_seq_type_expr(S,Sequences), |
| 1068 | | extract_pos_infos(S,PosInfos), |
| 1069 | | safe_create_texpr(member(S,Sequences),pred,PosInfos,Target). |
| 1070 | | create_sequence1_target(S,Target) :- |
| 1071 | | create_seq1_type_expr(S,Sequences), |
| 1072 | | extract_pos_infos(S,PosInfos), |
| 1073 | | safe_create_texpr(member(S,Sequences),pred,PosInfos,Target). |
| 1074 | | create_seq_seq_target(S,Target) :- |
| 1075 | | create_seq_seq_type_expr(S,SeqSeq), |
| 1076 | | extract_pos_infos(S,PosInfos), |
| 1077 | | safe_create_texpr(member(S,SeqSeq),pred,PosInfos,Target). |
| 1078 | | |
| 1079 | | create_seq_interval_target(S,N,Target) :- |
| 1080 | | create_texpr(integer(0),integer,[],Zero), |
| 1081 | | safe_create_texpr(size(S),integer,[contains_wd_condition],MaxIdx), |
| 1082 | | safe_create_texpr(interval(Zero,MaxIdx),set(integer),[],ValidIdxs), |
| 1083 | | safe_create_texpr(member(N,ValidIdxs),pred,[],Target). |
| 1084 | | |
| 1085 | | % compute WD of a conjunction/sequence of formulas |
| 1086 | | list_compute_wd([A|_],Options,Hyps,PO) :- |
| 1087 | ? | compute_wd(A,Hyps,Options,PO). |
| 1088 | | list_compute_wd([A|T],Options,Hyps,PO) :- T \= [], |
| 1089 | | push_hyp(Hyps,A,Options,Hyps2), |
| 1090 | ? | list_compute_wd(T,Options,Hyps2,PO). |
| 1091 | | |
| 1092 | | % compute WD of a list of independent formulas |
| 1093 | | %list_indep_compute_wd([A|T],Options,Hyps,PO) :- |
| 1094 | | % (compute_wd(A,Hyps,Options,PO) |
| 1095 | | % ; |
| 1096 | | % list_indep_compute_wd(T,Options,Hyps,PO)). |
| 1097 | | |
| 1098 | | % compute WD of a list of IF-THEN-ELSE cases: |
| 1099 | | list_compute_if_elsif_wd([b(if_elsif(A,Body),_,_) | T], Hyps,Options,PO) :- |
| 1100 | | ( is_truth(A) -> compute_wd(Body,Hyps,Options,PO) |
| 1101 | ? | ; ( compute_wd(A,Hyps,Options,PO) |
| 1102 | | ; |
| 1103 | | push_hyp(Hyps,A,Options,NewHyp), |
| 1104 | ? | compute_wd(Body,NewHyp,Options,PO) |
| 1105 | | ; |
| 1106 | | T \= [], |
| 1107 | | negate_hyp(A,NA), |
| 1108 | | push_hyp(Hyps,NA,Options,NewHyp), |
| 1109 | | list_compute_if_elsif_wd(T, NewHyp,Options,PO) |
| 1110 | | ) |
| 1111 | | ). |
| 1112 | | |
| 1113 | | % compute WD of a conjunction/sequence of formulas |
| 1114 | | sequence_compute_wd([A|_],Options,Hyps,PO) :- |
| 1115 | ? | compute_wd(A,Hyps,Options,PO). |
| 1116 | | sequence_compute_wd([A|T],Options,Hyps,PO) :- T \= [], |
| 1117 | | update_hyp_for_sequence_lhs(Hyps,A,Options,Hyps2), |
| 1118 | ? | sequence_compute_wd(T,Options,Hyps2,PO). |
| 1119 | | |
| 1120 | | :- use_module(probsrc(b_read_write_info), [get_accessed_vars/4]). |
| 1121 | | % update the hypotheses depending on effect of LHS of a sequential composition: |
| 1122 | | update_hyp_for_sequence_lhs(Hyps,b(LHS,subst,_),Options,Hyps2) :- |
| 1123 | | process_seq_lhs_aux(LHS,Hyps,Options,Hyps2), |
| 1124 | | !. |
| 1125 | | update_hyp_for_sequence_lhs(Hyps,TStmt,_Options,Hyps2) :- |
| 1126 | | add_modified_vars_to_hyp(Hyps,TStmt,Hyps2). |
| 1127 | | %add_message(well_def_analyser,'Uncovered substitution in sequential composition: ',TStmt,TStmt). |
| 1128 | | |
| 1129 | | % add all modified vars as new hyp vars: new hypotheses and goals will thus refer to new version (like priming variables) |
| 1130 | | add_modified_vars_to_hyp(Hyps,TLHS,Hyps2) :- |
| 1131 | | (get_accessed_vars(TLHS,[],ModifiedVars,_Read) -> true |
| 1132 | | ; add_error(well_def_analyser,'Could not obtain modified vars:',TLHS,TLHS), ModifiedVars=[] |
| 1133 | | ), |
| 1134 | | maplist(construct_typed_var(Hyps),ModifiedVars,TModVars), |
| 1135 | | add_new_hyp_variables(Hyps,TModVars,Hyps2). |
| 1136 | | |
| 1137 | | construct_typed_var(Hyps,ID,b(identifier(ID),Type,[])) :- |
| 1138 | | (get_hyp_var_type(ID,Hyps,Type) -> true |
| 1139 | | ; add_internal_error('Unknown identifier in hyps:',ID), Type=any). |
| 1140 | | |
| 1141 | | rename_expr(Hyps,Expr,RenExpr) :- get_renamed_expression(Expr,Hyps,RenExpr). |
| 1142 | | :- use_module(probsrc(bsyntaxtree),[get_texpr_id/2]). |
| 1143 | | construct_equal(TID,RenExpr, b(equal(TID,RenExpr),pred,[])) :- get_texpr_id(TID,_),!. |
| 1144 | | construct_equal(_,_,b(truth,pred,[])). % TO DO: deal with more complex assignments f(i) := E -> f' = f <+ {i|->E} |
| 1145 | | |
| 1146 | | process_seq_lhs_aux(assign_single_id(TID,Expr),Hyps,Options,Hyps2) :- !, |
| 1147 | | get_renamed_expression(Expr,Hyps,RenExpr), % rename in old context; e.g., if we have x:=x+1 |
| 1148 | | add_new_hyp_variables(Hyps,[TID],Hyps1), |
| 1149 | | get_renamed_expression(TID,Hyps1,RenTID), |
| 1150 | | Eq = b(equal(RenTID,RenExpr),pred,[]), % print('Add: '), translate:print_bexpr(Eq),nl, |
| 1151 | | push_hyps_wo_renaming(Hyps1,[Eq],Options,Hyps2). %, portray_hyps(Hyps2). |
| 1152 | | process_seq_lhs_aux(assign(FTIDs,Exprs),Hyps,Options,Hyps2) :- !, |
| 1153 | | maplist(rename_expr(Hyps),Exprs,RenExprs),% rename in old context; e.g., if we have x:=x+1 |
| 1154 | | maplist(get_assigned_ids,FTIDs,TIDs), |
| 1155 | | add_new_hyp_variables(Hyps,TIDs,Hyps1), |
| 1156 | | maplist(rename_expr(Hyps1),TIDs,RenTIDs), |
| 1157 | | maplist(well_def_analyser:construct_equal,RenTIDs,RenExprs,Equalities), |
| 1158 | | push_hyps_wo_renaming(Hyps1,Equalities,Options,Hyps2). |
| 1159 | | |
| 1160 | | % get assigned ids for things like f(x) := E or r'f := E |
| 1161 | | get_assigned_ids(b(Expr,_,_),TID) :- get_assigned_id(Expr,F), !,get_assigned_ids(F,TID). |
| 1162 | | get_assigned_ids(TID,TID). |
| 1163 | | |
| 1164 | | get_assigned_id(function(F,_),F). |
| 1165 | | get_assigned_id(record_field(R,_),R). |
| 1166 | | |
| 1167 | | % wd_like_conjunction(Construct,NewTypedVars,Conjunct1,Conjunct2) |
| 1168 | | wd_like_conjunction(conjunct(A,B),[],A,B). |
| 1169 | | wd_like_conjunction(implication(A,B),[],A,B). |
| 1170 | | wd_like_conjunction(precondition(A,B),[],A,B). |
| 1171 | | wd_like_conjunction(assertion(A,B),[],A,B). |
| 1172 | | wd_like_conjunction(witness_then(A,B),[],A,B). |
| 1173 | | wd_like_conjunction(select_when(A,B),[],A,B). |
| 1174 | | wd_like_conjunction(assertion_expression(A,_Msg,B),[],A,B). % Note: this has associated WD condition |
| 1175 | | wd_like_conjunction(any(Ids,A,B),Ids,A,B). |
| 1176 | | wd_like_conjunction(forall(Ids,A,B),Ids,A,B). |
| 1177 | | wd_like_conjunction(quantified_union(Ids,A,B),Ids,A,B). % rewritten |
| 1178 | | wd_like_conjunction(let_predicate(Ids,E,P),Ids,A,P) :- construct_let_eq_pred(Ids,E,A). |
| 1179 | | wd_like_conjunction(let_expression(Ids,E,P),Ids,A,P) :- construct_let_eq_pred(Ids,E,A). |
| 1180 | | wd_like_conjunction(let(Ids,E,P),Ids,A,P) :- A=E. % this is already a predicate |
| 1181 | | |
| 1182 | | |
| 1183 | | :- use_module(library(lists),[maplist/4,append/2]). |
| 1184 | | construct_let_eq_pred(Ids,E,Pred) :- |
| 1185 | | (ground(Pred) |
| 1186 | | -> conjunction_to_list(Pred,Ps), % enable predicate to be used both ways |
| 1187 | | maplist(deconstruct_eq,Ids,E,Ps) |
| 1188 | | ; maplist(construct_eq,Ids,E,Ps), |
| 1189 | | conjunct_predicates(Ps,Pred) |
| 1190 | | ),!. |
| 1191 | | construct_let_eq_pred(Ids,E,Pred) :- add_internal_error('Call failed: ',construct_let_eq_pred(Ids,E,Pred)),fail. |
| 1192 | | |
| 1193 | | construct_eq(TID,E,EqPred) :- safe_create_texpr(equal(TID,E),pred,EqPred). |
| 1194 | | deconstruct_eq(TID,E,b(equal(TID,E),pred,_)). |
| 1195 | | |
| 1196 | | % The constructs which have no WD condition of their own; they just require checking the arguments: |
| 1197 | | wd_transparent(truth). |
| 1198 | | wd_transparent(falsity). |
| 1199 | | wd_transparent(negation(_)). |
| 1200 | | wd_transparent(equivalence(_,_)). |
| 1201 | | wd_transparent(equal(_,_)). |
| 1202 | | wd_transparent(not_equal(_,_)). |
| 1203 | | wd_transparent(member(_,_)). |
| 1204 | | wd_transparent(not_member(_,_)). |
| 1205 | | wd_transparent(subset(_,_)). |
| 1206 | | wd_transparent(subset_strict(_,_)). |
| 1207 | | wd_transparent(not_subset(_,_)). |
| 1208 | | wd_transparent(not_subset_strict(_,_)). |
| 1209 | | wd_transparent(less_equal(_,_)). |
| 1210 | | wd_transparent(less(_,_)). |
| 1211 | | wd_transparent(less_equal_real(_,_)). |
| 1212 | | wd_transparent(less_real(_,_)). |
| 1213 | | wd_transparent(greater_equal(_,_)). |
| 1214 | | wd_transparent(greater(_,_)). |
| 1215 | | wd_transparent(finite(_)). |
| 1216 | | wd_transparent(partition(_,_)). |
| 1217 | | wd_transparent(value(_)). |
| 1218 | | wd_transparent(boolean_true). |
| 1219 | | wd_transparent(boolean_false). |
| 1220 | | wd_transparent(max_int). |
| 1221 | | wd_transparent(min_int). |
| 1222 | | wd_transparent(empty_set). |
| 1223 | | wd_transparent(bool_set). |
| 1224 | | wd_transparent(float_set). |
| 1225 | | wd_transparent(real_set). |
| 1226 | | wd_transparent(string_set). |
| 1227 | | wd_transparent(convert_bool(_)). |
| 1228 | | wd_transparent(convert_int_ceiling(_)). |
| 1229 | | wd_transparent(convert_int_floor(_)). |
| 1230 | | wd_transparent(convert_real(_)). |
| 1231 | | wd_transparent(add(_,_)). |
| 1232 | | wd_transparent(add_real(_,_)). |
| 1233 | | wd_transparent(minus(_,_)). |
| 1234 | | wd_transparent(minus_real(_,_)). |
| 1235 | | wd_transparent(minus_or_set_subtract(_,_)). |
| 1236 | | wd_transparent(unary_minus(_)). |
| 1237 | | wd_transparent(unary_minus_real(_)). |
| 1238 | | wd_transparent(multiplication(_,_)). |
| 1239 | | wd_transparent(multiplication_real(_,_)). |
| 1240 | | wd_transparent(mult_or_cart(_,_)). |
| 1241 | | wd_transparent(cartesian_product(_,_)). |
| 1242 | | wd_transparent(successor). |
| 1243 | | wd_transparent(predecessor). |
| 1244 | | wd_transparent(couple(_,_)). |
| 1245 | | wd_transparent(pow_subset(_)). |
| 1246 | | wd_transparent(pow1_subset(_)). |
| 1247 | | wd_transparent(fin_subset(_)). |
| 1248 | | wd_transparent(fin1_subset(_)). |
| 1249 | | wd_transparent(general_union(_)). |
| 1250 | | wd_transparent(interval(_,_)). |
| 1251 | | wd_transparent(union(_,_)). |
| 1252 | | wd_transparent(intersection(_,_)). |
| 1253 | | wd_transparent(set_subtraction(_,_)). |
| 1254 | | wd_transparent(relations(_,_)). |
| 1255 | | wd_transparent(identity(_)). |
| 1256 | | wd_transparent(event_b_identity). |
| 1257 | | wd_transparent(reverse(_)). |
| 1258 | | wd_transparent(first_projection(_,_)). |
| 1259 | | wd_transparent(first_of_pair(_)). |
| 1260 | | wd_transparent(event_b_first_projection(_)). |
| 1261 | | wd_transparent(event_b_first_projection_v2). |
| 1262 | | wd_transparent(second_projection(_,_)). |
| 1263 | | wd_transparent(event_b_second_projection(_)). |
| 1264 | | wd_transparent(event_b_second_projection_v2). |
| 1265 | | wd_transparent(second_of_pair(_)). |
| 1266 | | wd_transparent(composition(_,_)). |
| 1267 | | wd_transparent(ring(_,_)). |
| 1268 | | wd_transparent(direct_product(_,_)). |
| 1269 | | wd_transparent(parallel_product(_,_)). |
| 1270 | | wd_transparent(trans_function(_)). |
| 1271 | | wd_transparent(trans_relation(_)). |
| 1272 | | %wd_transparent(iteration(_,_)). % has a WD condition on index of iteration |
| 1273 | | wd_transparent(reflexive_closure(_)). |
| 1274 | | wd_transparent(closure(_)). |
| 1275 | | wd_transparent(domain(_)). |
| 1276 | | wd_transparent(range(_)). |
| 1277 | | wd_transparent(image(_,_)). |
| 1278 | | wd_transparent(domain_restriction(_,_)). |
| 1279 | | wd_transparent(domain_subtraction(_,_)). |
| 1280 | | wd_transparent(range_restriction(_,_)). |
| 1281 | | wd_transparent(range_subtraction(_,_)). |
| 1282 | | wd_transparent(overwrite(_,_)). |
| 1283 | | wd_transparent(partial_function(_,_)). |
| 1284 | | wd_transparent(total_function(_,_)). |
| 1285 | | wd_transparent(partial_injection(_,_)). |
| 1286 | | wd_transparent(total_injection(_,_)). |
| 1287 | | wd_transparent(partial_surjection(_,_)). |
| 1288 | | wd_transparent(total_surjection(_,_)). |
| 1289 | | wd_transparent(total_bijection(_,_)). |
| 1290 | | wd_transparent(partial_bijection(_,_)). |
| 1291 | | wd_transparent(total_relation(_,_)). |
| 1292 | | wd_transparent(surjection_relation(_,_)). |
| 1293 | | wd_transparent(total_surjection_relation(_,_)). |
| 1294 | | wd_transparent(seq(_)). |
| 1295 | | wd_transparent(seq1(_)). |
| 1296 | | wd_transparent(iseq(_)). |
| 1297 | | wd_transparent(iseq1(_)). |
| 1298 | | wd_transparent(perm(_)). |
| 1299 | | wd_transparent(empty_sequence). |
| 1300 | | wd_transparent(identifier(_)). |
| 1301 | | wd_transparent(lazy_lookup_expr(_)). |
| 1302 | | wd_transparent(lazy_lookup_pred(_)). |
| 1303 | | wd_transparent(integer(_)). |
| 1304 | | wd_transparent(integer_set(_)). |
| 1305 | | wd_transparent(real(_)). |
| 1306 | | wd_transparent(string(_)). |
| 1307 | | wd_transparent(set_extension(_)). |
| 1308 | | wd_transparent(sequence_extension(_)). |
| 1309 | | wd_transparent(struct(_)). |
| 1310 | | wd_transparent(rec(_)). |
| 1311 | | wd_transparent(record_field(_,_)). |
| 1312 | | wd_transparent(typeset). |
| 1313 | | |
| 1314 | | wd_transparent(external_function_call(F,_)) :- \+ external_fun_has_wd_condition(F). |
| 1315 | | wd_transparent(external_pred_call(F,_)) :- \+ external_fun_has_wd_condition(F). |
| 1316 | | wd_transparent(external_subst_call(F,_)) :- \+ external_fun_has_wd_condition(F). |
| 1317 | | |
| 1318 | | wd_transparent(operation_call_in_expr(_,_)). % the operations will be checked for WD independently |
| 1319 | | % PRE conditions are not part of WD checking |
| 1320 | | |
| 1321 | | wd_transparent(freetype_set(_)). |
| 1322 | | wd_transparent(freetype_constructor(_,_,_)). |
| 1323 | | wd_transparent(freetype_case(_,_,_)). % predicate to check if we match a given case |
| 1324 | | |
| 1325 | | % substitutions: |
| 1326 | | wd_transparent(skip). |
| 1327 | | wd_transparent(block(_)). |
| 1328 | | wd_transparent(parallel(_)). |
| 1329 | | wd_transparent(choice(_)). |
| 1330 | | wd_transparent(assign(_,_)). % TO DO: f(X) := E ==> f := f <+ {X|->E}, etc,... |
| 1331 | | wd_transparent(assign_single_id(_,_)). |
| 1332 | | wd_transparent(select(_)). |
| 1333 | | wd_transparent(select(_,_)). % TOD: Else only reached if all cases do not apply |
| 1334 | | wd_transparent(becomes_element_of(_,_)). % in classical B we do not have to check set not empty? |
| 1335 | | wd_transparent(becomes_such(_,_)). % in classical B we do not have to check satisfiability |
| 1336 | | wd_transparent(operation_call(_,_,_)). % I.e., we do not see checking PRE condition checking as part of WD checking |
| 1337 | | wd_transparent(var(_,_)). |
| 1338 | | |
| 1339 | | wd_transparent(witness(_,_)). |
| 1340 | | |
| 1341 | | % transparent with new quantified variables |
| 1342 | | wd_transparent(comprehension_set(_,_)). |
| 1343 | | wd_transparent(exists(_,_)). % WD must be proven universally for all subexpression |
| 1344 | | |
| 1345 | | |
| 1346 | | /* |
| 1347 | | Not yet covered: |
| 1348 | | |
| 1349 | | syntaxelement(kodkod(PId,Ids), Ids,[],[Ids],PId, pred). |
| 1350 | | |
| 1351 | | syntaxelement(operation_call_in_expr(Id,As), [Id|As], [], [As], [], expr). |
| 1352 | | |
| 1353 | | % rewritten: |
| 1354 | | syntaxelement(event_b_comprehension_set(Ids,E,P),[E,P|Ids], Ids,[Ids], [], expr/only_typecheck). |
| 1355 | | syntaxelement(lambda(Ids,P,E), [P,E|Ids],Ids,[Ids], [], expr). |
| 1356 | | |
| 1357 | | syntaxelement(quantified_intersection(Ids,P,E), [P,E|Ids],Ids,[Ids], [], expr). |
| 1358 | | |
| 1359 | | |
| 1360 | | TREE operations |
| 1361 | | |
| 1362 | | syntaxelement(let_expression_global(Ids,As,Expr), Exprs, Ids, [Ids,As], [], expr) :- % version used by b_compiler |
| 1363 | | append([Ids,As,[Expr]],Exprs). |
| 1364 | | syntaxelement(lazy_let_expr(TID,A,Expr), Exprs, [TID], [[TID],[A]], [], expr) :- |
| 1365 | | append([[TID],[A],[Expr]],Exprs). |
| 1366 | | syntaxelement(lazy_let_pred(TID,A,Expr), Exprs, [TID], [[TID],[A]], [], pred) :- |
| 1367 | | append([[TID],[A],[Expr]],Exprs). |
| 1368 | | syntaxelement(lazy_let_subst(TID,A,Expr), Exprs, [TID], [[TID],[A]], [], subst) :- |
| 1369 | | append([[TID],[A],[Expr]],Exprs). |
| 1370 | | |
| 1371 | | syntaxelement(compaction(A), [A], [], [], [], expr). |
| 1372 | | syntaxelement(mu(A), [A], [], [], [], expr). |
| 1373 | | syntaxelement(bag_items(A), [A], [], [], [], expr). |
| 1374 | | |
| 1375 | | syntaxelement(freetype_set(Id), [], [], [], Id, expr). |
| 1376 | | syntaxelement(freetype_case(Type,Case,Expr), [Expr], [], [], [Type,Case], pred). |
| 1377 | | syntaxelement(freetype_constructor(Type,Case,Expr), [Expr], [], [], [Type,Case], expr). |
| 1378 | | syntaxelement(freetype_destructor(Type,Case,Expr), [Expr], [], [], [Type,Case], expr). |
| 1379 | | |
| 1380 | | rlevent(Name,Section,_Status,_Params,Guard,_Theorems,_Actions,_VWitnesses,_PWitnesses,_Unmod,_AbstractEvents), |
| 1381 | | |
| 1382 | | |
| 1383 | | |
| 1384 | | seval /Users/leuschel/git_root/private_examples/ClearSy/2020/03_Mar/wd_timeout/invalidRef_welldef.mch |
| 1385 | | :wd |
| 1386 | | Analysis walltime: 183 ms |
| 1387 | | |
| 1388 | | Stats: [AXM/1084,THM/104,unsupported/7,not_discharged_po/545,discharged_po/704,caval__rule__1__compute/61] |
| 1389 | | Stats: [unsupported/2,AXM/1085,THM/104,not_discharged_po/542,discharged_po/708,caval__rule__1__compute/61] |
| 1390 | | |
| 1391 | | Analysis walltime: 31 ms |
| 1392 | | Stats: [AXM/1085,THM/104,not_discharged_po/542,discharged_po/708,caval__rule__1__compute/61] |
| 1393 | | when reordering and not ignoring infos: |
| 1394 | | Analysis walltime: 17 ms |
| 1395 | | Stats: [AXM/1085,THM/104,not_discharged_po/540,discharged_po/710,caval__rule__1__compute/61] |
| 1396 | | |
| 1397 | | Tests: |
| 1398 | | |
| 1399 | | :wd a>0 & x>0 & x:1..10 & f:1..10-->INTEGER & f(x)=2 & x>1 |
| 1400 | | :wd %x.(x:2..4 | %x.(x:4..8|10/x)(2*x)) = x |
| 1401 | | |
| 1402 | | :wd x:NATURAL1 & y>=x & x mod y = x/y |
| 1403 | | -> same PO generated twice |
| 1404 | | |
| 1405 | | :wd f6 = %x.(x>10 & x<20|100) & res=f6(11) |
| 1406 | | :wd i5 = %x.(x>10|100+x) & i5(100) = 200 |
| 1407 | | seval /Users/leuschel/git_root/prob_examples/examples/B/ASTD/wetransfer-545a33/Case_Study_Handmade/TRAIN_CONTROL_M6.mch |
| 1408 | | |
| 1409 | | :wd n:NATURAL & a:1..n --> 1..10 & a /= {} & a(1)=1 |
| 1410 | | |
| 1411 | | -> support for $0 missing |
| 1412 | | -> support for ; and while (adding condition and invariant to loop body hyps) for transform |
| 1413 | | -> support for operation all in expression |
| 1414 | | -> Parallel in classical B: we could propagate guards from first to second subst; CarlaTravelAgency; but Atelier-B considers this to be not well-defined; each parallel construct should be WD on its own; we should make no assumption about order |
| 1415 | | -> CASE statement: treat cases specially |
| 1416 | | |
| 1417 | | % Processing file 2/3: /Users/leuschel/git_root/private_examples/ClearSy/2020/01_Jan/logxml_system_error/rule.mch |
| 1418 | | Proof of AXM took 169 ms, result=discharged ... |
| 1419 | | */ |
| 1420 | | |
| 1421 | | % --------------------------------- |
| 1422 | | % Annotating operations so that we can discharge WD conditions statically |
| 1423 | | |
| 1424 | | % this can be called once for all operations: it gets the hypotheses that are available for (all) operations |
| 1425 | | get_hyps_for_top_level_operations(Options,Hyps) :- |
| 1426 | | push_properties_invariant_hyps(Options,Hyps). |
| 1427 | | |
| 1428 | | :- public transform_machine_operation/7. |
| 1429 | | |
| 1430 | | % should call get_hyps_for_top_level_operations |
| 1431 | | % Note: should be run after global types are pre-compiled; otherwise we do not detect global constants |
| 1432 | | % TODO: pre-compile global sets before computing operations? |
| 1433 | | transform_machine_operation(OpName,OpResults,OpFormalParameters,Body,Hyps,Options,NewBody) :- |
| 1434 | | PO_Name = OpName, |
| 1435 | | format('Checking WD of OPERATION ~w~n',[OpName]), |
| 1436 | | ord_add_element(Options,po_label(PO_Name),Opt1), |
| 1437 | | add_new_hyp_variables(Hyps,OpFormalParameters,Hyps6), |
| 1438 | | add_new_hyp_variables(Hyps6,OpResults,Hyps7), |
| 1439 | | ord_add_element(Opt1,discharge_po,Opt2), |
| 1440 | | ord_add_element(Opt2,reorder_conjuncts,Opt3), |
| 1441 | | transform_wd(Body,Hyps7,Opt3,NewBody), |
| 1442 | | print_wd_subst(NewBody). |
| 1443 | | |
| 1444 | | print_wd_subst(NewTExpr) :- |
| 1445 | | temporary_set_preference(pp_wd_infos,true,Chng), |
| 1446 | | translate:print_subst(NewTExpr),nl, |
| 1447 | | reset_temporary_preference(pp_wd_infos,Chng). |
| 1448 | | |
| 1449 | | push_properties_invariant_hyps(Options,Hyps4) :- |
| 1450 | | b_get_properties_from_machine(Properties), |
| 1451 | | empty_hyps(E), |
| 1452 | | b_get_machine_all_constants(Csts), |
| 1453 | | add_new_hyp_variables(E,Csts,OriginalHyps), |
| 1454 | | push_hyp(OriginalHyps,Properties,Options,Hyps1), |
| 1455 | | b_get_static_assertions_from_machine(StaticAssertions), |
| 1456 | | push_hyps(Hyps1,StaticAssertions,Options,Hyps2), |
| 1457 | | b_get_machine_variables(Vars), |
| 1458 | | add_new_hyp_variables(Hyps2,Vars,Hyps3), |
| 1459 | | b_get_invariant_from_machine(Invariant), |
| 1460 | | push_hyp(Hyps3,Invariant,Options,Hyps4). |
| 1461 | | |
| 1462 | | % --------------------------------- |
| 1463 | | |
| 1464 | | :- use_module(probsrc(bsyntaxtree), [def_get_texpr_ids/2]). |
| 1465 | | :- use_module(probsrc(btypechecker),[prime_identifiers/2]). |
| 1466 | | :- use_module(extrasrc(before_after_predicates),[prime_bexpr_for_ids/4, |
| 1467 | | before_after_predicate_for_operation_no_equalities/5]). |
| 1468 | | % try and prove invariant preservation using BA predicate |
| 1469 | | prove_invariant_preservation(OpName,TargetInv,Proven,Options) :- |
| 1470 | | push_properties_invariant_hyps(Options,Hyps), |
| 1471 | | b_get_invariant_from_machine(Invariant), |
| 1472 | | conjunction_to_list(Invariant,Invs), |
| 1473 | | before_after_predicate_for_operation_no_equalities(OpName,Paras,Results,BAPred,TChangedIds), |
| 1474 | | add_new_hyp_variables(Hyps,Paras,Hyps1), |
| 1475 | | add_new_hyp_variables(Hyps1,Results,Hyps2), |
| 1476 | | prime_identifiers(TChangedIds,NewPrimedIds), |
| 1477 | | add_new_hyp_variables(Hyps2,NewPrimedIds,Hyps3), |
| 1478 | | push_hyp(Hyps3,BAPred,Options,Hyps4), |
| 1479 | | formatsilent('~nProving invariant preservation for operation ~w~n',[OpName]), |
| 1480 | | (silent_mode(on) -> true ; translate:print_bexpr(BAPred),nl), |
| 1481 | | member(TargetInv,Invs), |
| 1482 | | def_get_texpr_ids(TChangedIds,ChangedIds), |
| 1483 | | prime_bexpr_for_ids(TargetInv,ChangedIds,PrimedTargetInv,ChangesPerformed), |
| 1484 | | (ChangesPerformed=false |
| 1485 | | -> Proven=unchanged % Invariant unaffected by event |
| 1486 | | ; prove_sequent_goal(PrimedTargetInv,Hyps4,Options) |
| 1487 | | -> Proven=proven |
| 1488 | | ; Proven=unproven), |
| 1489 | | (silent_mode(on) -> true |
| 1490 | | ; format(' ~w => ',[Proven]), translate:print_bexpr(PrimedTargetInv),nl). |
| 1491 | | |
| 1492 | | % well_def_analyser:prove_invariant_preservation(OpName,Target,Proven),fail. |
| 1493 | | |
| 1494 | | :- use_module(probsrc(tools_lists),[count_occurences/2]). |
| 1495 | | |
| 1496 | | analyse_invariants_for_machine(UnchangedNr,ProvenNr,UnProvenNr,TotPOsNr,Options) :- |
| 1497 | | findall(Proven,prove_invariant_preservation(_Op,_,Proven,Options),Ls), |
| 1498 | | count_occurences(Ls,Res), |
| 1499 | | (member(proven-ProvenNr,Res) -> true ; ProvenNr=0), |
| 1500 | | (member(unchanged-UnchangedNr,Res) -> true ; UnchangedNr=0), |
| 1501 | | (member(unproven-UnProvenNr,Res) -> true ; UnProvenNr=0), |
| 1502 | | TotPOsNr is UnchangedNr + ProvenNr + UnProvenNr. |
| 1503 | | |
| 1504 | | % TODO: look at weakest_precondition/3: no need to prime? |
| 1505 | | |
| 1506 | | % --------------------------------- |
| 1507 | | |
| 1508 | | |
| 1509 | | %% toplevel_wd_pos(Predicate, Hypotheses, ProofObligations). |
| 1510 | | % |
| 1511 | | % Returns a list of proof obligations for the given Ast, but only those relevant |
| 1512 | | % for the root node. |
| 1513 | | toplevel_wd_pos(b(Node, _, _), _, []) :- |
| 1514 | | wd_transparent(Node), !. |
| 1515 | | toplevel_wd_pos(b(Node, Type, Info), Hyps, WDPOs) :- |
| 1516 | | wd_like_conjunction(Node, _, _, _), !, |
| 1517 | | findall(PO, create_top_level_wd_po_conj_like(Node, Type, Info, Hyps, [discharge_po], PO, _), WDPOs). |
| 1518 | | toplevel_wd_pos(b(Node, Type, Info), Hyps, WDPOs) :- |
| 1519 | ? | has_top_level_wd_condition(Node), !, |
| 1520 | | findall(PO, create_top_level_wd_po(Node, Type, Info, Hyps, [discharge_po], PO, _), WDPOs). |
| 1521 | | toplevel_wd_pos(_, _, []). |
| 1522 | | |