1 | % (c) 2009-2016 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(weakest_preconditions, [weakest_precondition/3,set_reference_machine/1,delete_reference_machine/0]). | |
6 | ||
7 | :- use_module(module_information,[module_info/2]). | |
8 | :- module_info(group,cbc). | |
9 | :- module_info(description,'This module provides weakest precondition calculation for B and Event-B operations.'). | |
10 | ||
11 | :- use_module(library(lists)). | |
12 | :- use_module(library(sets), [subset/2]). | |
13 | ||
14 | :- use_module(bsyntaxtree, [get_texpr_expr/2, | |
15 | get_texpr_id/2, get_texpr_ids/2, | |
16 | get_texpr_type/2, | |
17 | create_texpr/4, safe_create_texpr/3, | |
18 | create_forall/3, | |
19 | create_negation/2, | |
20 | conjunct_predicates/2, | |
21 | replace_id_by_expr/4, | |
22 | replace_ids_by_exprs/4, | |
23 | find_typed_identifier_uses/2, | |
24 | remove_all_infos/2]). | |
25 | :- use_module(b_read_write_info, [get_accessed_vars/4]). | |
26 | :- use_module(bmachine_eventb, [prime_variables/2, | |
27 | prime_variable/2, is_primed_id/1]). | |
28 | :- use_module(error_manager, [add_error_fail/3]). | |
29 | :- use_module(tools, [assert_once/1]). | |
30 | :- use_module(bmachine, [b_get_machine_operation/4]). | |
31 | :- use_module(bmachine_structure, [get_section/3]). | |
32 | ||
33 | :- use_module(probsrc(translate),[translate_substitution/2,print_subst/1]). | |
34 | :- use_module(probsrc(debug),[debug_mode/1]). | |
35 | ||
36 | % dynamic predicate may contain a machine in which operations are looked up | |
37 | % this is nessasary for the wp of operation calls, if the operation does not | |
38 | % belong to the currently loaded machine | |
39 | % (but for example to a refinement/abstraction) | |
40 | :- volatile machine/1. | |
41 | :- dynamic machine/1. | |
42 | ||
43 | set_reference_machine(M) :- | |
44 | delete_reference_machine, | |
45 | assert_once(machine(M)). | |
46 | delete_reference_machine :- | |
47 | retractall(machine(_)). | |
48 | ||
49 | % lookup operations in the reference machine if it exists | |
50 | % otherwise, lookup in loaded machine | |
51 | lookup_operation(Name,Results,Parameters,Body) :- | |
52 | ground(Name), % only for lookup of operations | |
53 | get_texpr_id(Name,op(OperationName)), | |
54 | (machine(M) | |
55 | -> get_section(operation_bodies,M,Ops), | |
56 | get_texpr_expr(Op,operation(TId,Results,Parameters,Body)), | |
57 | get_texpr_id(TId,op(Name)), | |
58 | member(Op,Ops) | |
59 | ; b_get_machine_operation(OperationName,Results,Parameters,Body)). | |
60 | ||
61 | :- mode weakest_precondition(+Action, +Pred,-WP). | |
62 | weakest_precondition(Action,Pred,WP) :- | |
63 | get_texpr_expr(Action,Expr), | |
64 | weakest_precondition2(Expr,Pred,WP). | |
65 | ||
66 | % any statement. see schneider p. 126 | |
67 | weakest_precondition2(any(Parameters,PreCond,Body),Pred,WP) :- !, | |
68 | weakest_precondition(Body,Pred,InnerWP), | |
69 | safe_create_texpr(implication(PreCond,InnerWP),pred,UnquantifiedWP), | |
70 | create_forall(Parameters,UnquantifiedWP,WP). | |
71 | weakest_precondition2(assign(TIds,Exprs),Pred,WP) :- !, | |
72 | function_assignment_to_overwrite(TIds,Exprs,TIds2,Exprs2), | |
73 | get_texpr_ids(TIds2,StrippedIDs), | |
74 | replace_ids_by_exprs(Pred,StrippedIDs,Exprs2,WP). | |
75 | weakest_precondition2(assign_single_id(TId,Expr),Pred,WP) :- !, | |
76 | function_assignment_to_overwrite([TId],[Expr],[TId2],[Expr2]), | |
77 | get_texpr_id(TId2,Id), | |
78 | replace_id_by_expr(Pred,Id,Expr2,WP). | |
79 | % nondeterministic choice. see schneider p. 126 | |
80 | weakest_precondition2(becomes_element_of(IDs,Set),Pred,WP) :- !, | |
81 | create_members(Set,IDs,MemberOf), | |
82 | safe_create_texpr(implication(MemberOf,Pred),pred,InnerWP), | |
83 | create_forall(IDs,InnerWP,WP). | |
84 | % nondet choice of action. see schneider p. 129 | |
85 | weakest_precondition2(choice(Choices),Pred,WP) :- !, | |
86 | choice_wps(Choices,Pred,WPs), | |
87 | conjunct_predicates(WPs,WP). | |
88 | weakest_precondition2(if(IfList),Pred,WP) :- !, | |
89 | if_wp(IfList,Pred,WP). | |
90 | % let statement: local variable with value. see schneider p. 125 | |
91 | weakest_precondition2(let(Parameters,Defs,Body),Pred,WP) :- !, | |
92 | weakest_precondition(Body,Pred,InnerWP), | |
93 | safe_create_texpr(implication(Defs,InnerWP),pred,UnquantifiedWP), | |
94 | create_forall(Parameters,UnquantifiedWP,WP). | |
95 | weakest_precondition2(operation_call(Operation,ResultsCall,ParametersCall),Pred,WP) :- !, | |
96 | lookup_operation(Operation,ResultsOperation,ParametersOperation,Body), | |
97 | % replace parameter/results identifiers | |
98 | append([ResultsOperation,ParametersOperation],IDs), append([ResultsCall,ParametersCall],Replacements), | |
99 | get_texpr_ids(IDs,StrippedIDs), | |
100 | replace_ids_by_exprs(Body,StrippedIDs,Replacements,NewBody), | |
101 | weakest_precondition(NewBody,Pred,WP). | |
102 | weakest_precondition2(parallel(Actions),Pred,WP) :- !, | |
103 | merge_parallels(Actions,Action), | |
104 | weakest_precondition(Action,Pred,WP). | |
105 | weakest_precondition2(precondition(Condition,Action),Pred,WP) :- !, | |
106 | weakest_precondition(Action,Pred,InnerWP), | |
107 | conjunct_predicates([Condition,InnerWP],WP). | |
108 | % weakest precondition for event-b events | |
109 | weakest_precondition2(rlevent(_Name,_Section,_Stat,Parameters,Guard,_Thm,Act,_VWit,_PWit,_Unmod,_AbsEvents),Pred,WP) :- !, | |
110 | (is_list(Act) | |
111 | -> create_texpr(parallel(Act),subst,[],NewAct) | |
112 | ; NewAct=Act | |
113 | ), | |
114 | weakest_precondition2(any(Parameters,Guard,NewAct),Pred,WP). | |
115 | % there are two kinds of selects: just whens and whens/else | |
116 | % the else case just collects all guards and negates them | |
117 | % see schneider p. 132 | |
118 | weakest_precondition2(select(Whens),Pred,WP) :- !, | |
119 | select_whens_wps(Whens,Pred,WPs), | |
120 | conjunct_predicates(WPs,WP). | |
121 | weakest_precondition2(select(Whens,Else),Pred,WP) :- !, | |
122 | select_whens_wps(Whens,Pred,WPs), | |
123 | conjunct_predicates(WPs,WhensWP), | |
124 | % collect all guards and negate them | |
125 | % => precondition for else-case | |
126 | findall(PC,(member(SW,Whens),get_texpr_expr(SW,select_when(PC,_))), AllPreconds), | |
127 | maplist(create_negation,AllPreconds,NegAllPreconds), | |
128 | conjunct_predicates(NegAllPreconds,ElsePrecond), | |
129 | % imply [T_n]S | |
130 | weakest_precondition(Else,Pred,InnerWP), | |
131 | safe_create_texpr(implication(ElsePrecond,InnerWP),pred,ElseWP), | |
132 | conjunct_predicates([WhensWP,ElseWP],WP). | |
133 | weakest_precondition2(sequence(Actions),Pred,WP) :- !, | |
134 | sequence_wp(Actions,Pred,WP). | |
135 | weakest_precondition2(skip,Pred,WP) :- !,WP=Pred. | |
136 | weakest_precondition2(var(IDs,Subst),Pred,WP) :- !, | |
137 | weakest_precondition(Subst,Pred,InnerWP), | |
138 | create_forall(IDs,InnerWP,WP). | |
139 | weakest_precondition2(while(P,S,I,V),R,WP) :- !, | |
140 | % [while P DO S INVARIANT I VARIANT V END] R | |
141 | % see abrial, b-book, p. 395: | |
142 | % there are five predicates. their conjunction is equal to the weakest precondition | |
143 | % first, create the list of all variables modified by the Stmt (used in forall) | |
144 | find_typed_identifier_uses(S,AllIdentifiersInStmt), | |
145 | get_accessed_vars(S,[],ModifiedVarsInStmt,_Reads), | |
146 | % the identifiers in ModifiedVarsInStmt are not typed. fetch the types from the list of all identifiers | |
147 | % TypedModifiedVarsInStmt = X | |
148 | get_texpr_ids(TypedModifiedVarsInStmt,ModifiedVarsInStmt), | |
149 | subset(TypedModifiedVarsInStmt,AllIdentifiersInStmt), | |
150 | ||
151 | ForAlls = TypedModifiedVarsInStmt, | |
152 | ||
153 | % first obligation: the invariant | |
154 | WP1 = I, | |
155 | ||
156 | % second obligation: forall x in X: (I & P => [S]I) | |
157 | conjunct_predicates([I,P],LHS2), | |
158 | weakest_precondition(S,I,RHS2), | |
159 | safe_create_texpr(implication(LHS2,RHS2),pred,Inner2), | |
160 | create_forall(ForAlls,Inner2,WP2), | |
161 | ||
162 | % third obligation: forall x in X: (I => v in N) | |
163 | safe_create_texpr(member(V,b(integer_set('NATURAL'),set(integer),[])),pred,RHS3), | |
164 | safe_create_texpr(implication(I,RHS3),pred,Inner3), | |
165 | create_forall(ForAlls,Inner3,WP3), | |
166 | ||
167 | % fourth obligation: forall x in X: I & P => [gamma:=V][S](V<gamma) | |
168 | create_texpr(identifier('gamma\''),integer,[],Gamma), | |
169 | create_texpr(assign_single_id(Gamma,V),subst,[],AssignVariantToGamma), | |
170 | safe_create_texpr(less(V,Gamma),pred,VLessGamma), | |
171 | weakest_precondition(S,VLessGamma,RHS4T), | |
172 | weakest_precondition(AssignVariantToGamma,RHS4T,RHS4), | |
173 | LHS4 = LHS2, | |
174 | safe_create_texpr(implication(LHS4,RHS4),pred,Inner4), | |
175 | create_forall(ForAlls,Inner4,WP4), | |
176 | ||
177 | % fifth obligation: forall x in X: (I & not P) => R | |
178 | create_negation(P,NotP), conjunct_predicates([I,NotP],LHS5), | |
179 | safe_create_texpr(implication(LHS5,R),pred,Inner5), | |
180 | create_forall(ForAlls,Inner5,WP5), | |
181 | ||
182 | % conjunct them all together | |
183 | conjunct_predicates([WP1,WP2,WP3,WP4,WP5],WP). | |
184 | weakest_precondition2(Action,Pred,_WeakestPrecondition) :- !, | |
185 | get_texpr_expr(Action,ActionExpr), | |
186 | add_error_fail(weakest_precondition,'weakest-precondition implementation missing: ',[ActionExpr,Pred]). | |
187 | ||
188 | choice_wps([],_Pred,[]). | |
189 | choice_wps([Choice|Choices],Pred,[ChoiceWP|WPs]) :- | |
190 | weakest_precondition(Choice,Pred,ChoiceWP), | |
191 | choice_wps(Choices,Pred,WPs). | |
192 | ||
193 | % see schneider p. 38 | |
194 | % [if E then S else T end] P = (E => [S]P) & (not E => [T]P) | |
195 | if_wp([IF|IFs],Pred,WP) :- | |
196 | get_texpr_expr(IF,if_elsif(Test,Body)), | |
197 | % if-part | |
198 | weakest_precondition(Body,Pred,InnerWP), | |
199 | safe_create_texpr(implication(Test,InnerWP),pred,IfWP), | |
200 | % if there are further else/elseif parts, create pos | |
201 | (if_wp(IFs,Pred,SubWP) | |
202 | -> create_negation(Test,NegTest), | |
203 | safe_create_texpr(implication(NegTest,SubWP),pred,ElseWP), | |
204 | conjunct_predicates([IfWP,ElseWP],WP) | |
205 | ; WP = IfWP). | |
206 | ||
207 | merge_parallels(ParallelAssigns,Result) :- %trace, | |
208 | create_texpr(truth,pred,[],True), | |
209 | create_texpr(parallel([]),subst,[],Body), | |
210 | EmptyAny = any([],True,Body), | |
211 | EmptyAssign = assign([],[]), | |
212 | merge_parallels1(ParallelAssigns,EmptyAssign,EmptyAny,Assigns,Anys,Rest), | |
213 | (Rest == [] -> | |
214 | merge_assigns_and_anys(Assigns,Anys,Res), | |
215 | create_texpr(Res,subst,[],Result), | |
216 | (debug_mode(on) -> print_subst(Result),nl; true) | |
217 | ; otherwise -> | |
218 | add_error_fail(merge_parallels, 'merging of parallel executions failed (implementation missing?):', Rest) | |
219 | ). | |
220 | ||
221 | merge_parallels1([],Assigns,Anys,Assigns,Anys,[]). | |
222 | merge_parallels1([Subst|Substs],assign(IDs2,Exprs2),any(Par2,PreCond2,Body2),ResAssigns,ResAnys,Rest) :- | |
223 | get_texpr_expr(Subst,Expr), | |
224 | merge_parallels_normalize(Expr,ExprN), | |
225 | (ExprN = assign(IDs1,Exprs1) -> | |
226 | append(IDs2,IDs1,IDs3), | |
227 | append(Exprs2,Exprs1,Exprs3), | |
228 | NewAssign = assign(IDs3,Exprs3), | |
229 | NewAny = any(Par2,PreCond2,Body2), | |
230 | Rest = Rest1 | |
231 | ; ExprN = any(Par1,PreCond1,Body1) -> | |
232 | append(Par2,Par1,Par3), | |
233 | conjunct_predicates([PreCond2,PreCond1],PreCond3), | |
234 | get_texpr_expr(Body2,parallel(AnySubsts2)), | |
235 | create_texpr(parallel([Body1|AnySubsts2]),subst,[],Body3), | |
236 | NewAny = any(Par3,PreCond3,Body3), | |
237 | NewAssign = assign(IDs2,Exprs2), | |
238 | Rest = Rest1 | |
239 | ; ExprN = skip -> | |
240 | NewAssign = assign(IDs2,Exprs2), | |
241 | NewAny = any(Par2,PreCond2,Body2), | |
242 | Rest = Rest1 | |
243 | ; otherwise -> | |
244 | NewAssign = assign(IDs2,Exprs2), | |
245 | NewAny = any(Par2,PreCond2,Body2), | |
246 | Rest = [Subst|Rest1] | |
247 | ), !, % do not backtrack once the a substitution is merged to the assignment or any generator | |
248 | merge_parallels1(Substs,NewAssign,NewAny,ResAssigns,ResAnys,Rest1). | |
249 | ||
250 | merge_assigns_and_anys(Assign,Any,Result) :- | |
251 | (empty_any_statement(Any),empty_assign_statement(Assign) -> | |
252 | add_error_fail(merge_assigns_and_anys,'merging of parallel executions failed (empty assignment and any statements): ', (Assign,Any)) | |
253 | ; empty_any_statement(Any) -> | |
254 | Result = Assign | |
255 | ; empty_assign_statement(Assign) -> | |
256 | Result = Any | |
257 | ; otherwise -> | |
258 | Any = any(Par,PreCond,Body), | |
259 | get_texpr_expr(Body,parallel(Actions)), | |
260 | create_texpr(Assign,subst,[],BAssign), | |
261 | create_texpr(parallel([BAssign|Actions]),subst,[],NewBody), | |
262 | Result = any(Par,PreCond,NewBody) | |
263 | ). | |
264 | ||
265 | empty_any_statement(any([],_Precond,b(parallel([]),subst,_))). | |
266 | ||
267 | empty_assign_statement(assign([],[])). | |
268 | ||
269 | % The old implementation for merging parallel assignments | |
270 | ||
271 | %% merge_parallels([X],X) :- !. | |
272 | %% merge_parallels([A1,A2|As],X) :- | |
273 | %% merge_parallels2(A1,A2,AMerged), !, | |
274 | %% merge_parallels([AMerged|As],X). | |
275 | %% merge_parallels([A1,A2|As],X) :- | |
276 | %% merge_parallels2(A2,A1,AMerged), !, | |
277 | %% merge_parallels([AMerged|As],X). | |
278 | %% merge_parallels([A1,A2|_As],_X) :- | |
279 | %% get_texpr_expr(A1,A1E), get_texpr_expr(A2,A2E), | |
280 | %% add_error_fail(merge_parallels,'merging of parallel executions failed (implementation missing?): ',(A1E,A2E)). | |
281 | ||
282 | %% merge_parallels2(A1,A2,AMerged) :- | |
283 | %% get_texpr_expr(A1,A1Expr), get_texpr_expr(A2,A2Expr), | |
284 | %% merge_parallels_normalize(A1Expr,A1ExprN), | |
285 | %% merge_parallels_normalize(A2Expr,A2ExprN), | |
286 | %% merge_parallels3(A1ExprN,A2ExprN,AMergedExpr), | |
287 | %% create_texpr(AMergedExpr,subst,[],AMerged). | |
288 | ||
289 | %% merge_parallels3(assign(IDs1,Exprs1),assign(IDs2,Exprs2),assign(IDs3,Exprs3)) :- | |
290 | %% append(IDs1,IDs2,IDs3), append(Exprs1,Exprs2,Exprs3). | |
291 | %% merge_parallels3(any(Parameters,PreCond,Body),SomeSubstitution,any(Parameters,PreCond,NewBody)) :- | |
292 | %% create_texpr(SomeSubstitution,subst,[],SomeSubstitutionTExpr), | |
293 | %% create_texpr(parallel([Body,SomeSubstitutionTExpr]),subst,[],NewBody). | |
294 | % in case we have more than two substitutions in a parallel block (see for example B/Ivo/WeakestPreconditon/Tickets/MergeParallels.mch WP: [Evt1](G(Evt2))) | |
295 | ||
296 | merge_parallels_normalize(assign_single_id(ID,Expr),assign([ID],[Expr])) :- !. | |
297 | merge_parallels_normalize(becomes_element_of(IDs,Set), any(Parameters,PreCond,Body)) :- !, | |
298 | prime_variables(IDs,Parameters), create_members(Set,Parameters,PreCond), | |
299 | create_texpr(assign(IDs,Parameters),subst,[],Body). | |
300 | merge_parallels_normalize(becomes_such(Vars,Condition),any(PrimedIDs,Condition,Body)) :- !, | |
301 | find_typed_identifier_uses(Condition,UsedIDs), | |
302 | get_primed_ids(UsedIDs,PrimedIDs), | |
303 | get_non_represented_vars(Vars,PrimedIDs,NonRepresented), | |
304 | (NonRepresented\=[] -> | |
305 | get_texpr_ids(NonRepresented,VarsIDs), | |
306 | create_texpr(becomes_such(Vars,Condition),subst,[],TExpr), | |
307 | translate_substitution(TExpr,Subst), | |
308 | add_error_fail(merge_parallels_normalize,'Normalising becomes_such(...) costruct failed because the following variables were not reprsented by prime variables: ', (VarsIDs,Subst)) | |
309 | ;otherwise -> | |
310 | create_texpr(assign(Vars,PrimedIDs),subst,[],Body) | |
311 | ). | |
312 | % Functional overrides in Event-B will be translated to assignments using the override operator (<+) | |
313 | merge_parallels_normalize(X,X). | |
314 | ||
315 | get_non_represented_vars([],_PrimedVars,[]). | |
316 | get_non_represented_vars([Var|Vars],PrimedVars,NonRepresented) :- | |
317 | prime_variable(Var,VarPrimed), | |
318 | remove_all_infos(VarPrimed,VarPrimedNoInfos), | |
319 | (member(VarPrimedNoInfos,PrimedVars) -> | |
320 | NonRepresented = NonRepresented1 | |
321 | ; otherwise -> | |
322 | NonRepresented = [Var|NonRepresented1] | |
323 | ), | |
324 | get_non_represented_vars(Vars,PrimedVars,NonRepresented1). | |
325 | ||
326 | get_primed_ids([],[]). | |
327 | get_primed_ids([ID|IDs],[ID|Rest]) :- | |
328 | get_texpr_id(ID,I), | |
329 | is_primed_id(I),!, | |
330 | get_primed_ids(IDs,Rest). | |
331 | get_primed_ids([_ID|IDs],Rest) :- | |
332 | get_primed_ids(IDs,Rest). | |
333 | ||
334 | sequence_wp(Actions,Pred,WP) :- | |
335 | reverse(Actions,ReversedActions), | |
336 | sequence_wp2(ReversedActions,Pred,WP). | |
337 | sequence_wp2([],Pred,Pred). | |
338 | sequence_wp2([Action|Actions],PredIn,PredOut) :- | |
339 | weakest_precondition(Action,PredIn,PredT), | |
340 | sequence_wp2(Actions,PredT,PredOut). | |
341 | ||
342 | select_whens_wps([],_Pred,[]). | |
343 | select_whens_wps([When|Whens],Pred,[WP|WPs]) :- | |
344 | get_texpr_expr(When,select_when(PreCond, Body)), | |
345 | weakest_precondition(Body,Pred,InnerWP), | |
346 | safe_create_texpr(implication(PreCond,InnerWP),pred,WP), | |
347 | select_whens_wps(Whens,Pred,WPs). | |
348 | ||
349 | create_members(Set,IDs,MemberOf) :- | |
350 | maplist(create_member(Set),IDs,Preds), | |
351 | conjunct_predicates(Preds,MemberOf). | |
352 | create_member(Set,ID,Res) :- | |
353 | safe_create_texpr(member(ID,Set),pred,Res). | |
354 | ||
355 | %create_renaming(I1,I2,rename(I1,I2)). | |
356 | ||
357 | function_assignment_to_overwrite([],[],[],[]). | |
358 | function_assignment_to_overwrite([b(identifier(ID),Type,Infos)|IdOrFuns],[Expr|Exprs],[b(identifier(ID),Type,Infos)|IdOuts],[Expr|ExprOuts]) :- | |
359 | function_assignment_to_overwrite(IdOrFuns,Exprs,IdOuts,ExprOuts). | |
360 | function_assignment_to_overwrite([b(function(Function,Argument),_Type,_Infos)|IdOrFuns],[Expr|Exprs],[Function|IdOuts],[ExprOut|ExprOuts]) :- | |
361 | get_texpr_type(Argument,ArgumentType), get_texpr_type(Expr,ExprType), | |
362 | get_texpr_type(Function,FunctionType), | |
363 | CoupleType = couple(ArgumentType,ExprType), | |
364 | safe_create_texpr(couple(Argument,Expr),CoupleType,OverwriteCouple), | |
365 | safe_create_texpr(set_extension([OverwriteCouple]),set(CoupleType),CoupleInSet), | |
366 | safe_create_texpr(overwrite(Function,CoupleInSet),FunctionType,ExprOut), | |
367 | function_assignment_to_overwrite(IdOrFuns,Exprs,IdOuts,ExprOuts). |