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