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