| 1 | % (c) 2009-2024 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(kodkod_translate, | |
| 6 | [ kodkod_translate/4 | |
| 7 | , remove_optional_set/2 | |
| 8 | ]). | |
| 9 | ||
| 10 | :- use_module(library(lists)). | |
| 11 | :- use_module(library(avl)). | |
| 12 | :- use_module(library(ordsets)). | |
| 13 | ||
| 14 | :- use_module(probsrc(module_information),[module_info/2]). | |
| 15 | :- use_module(probsrc(bsyntaxtree)). | |
| 16 | :- use_module(probsrc(bmachine)). | |
| 17 | :- use_module(probsrc(translate), [pretty_type/2,translate_bexpression/2]). | |
| 18 | :- use_module(probsrc(custom_explicit_sets),[expand_custom_set_to_list/2]). | |
| 19 | :- use_module(probsrc(tools),[foldl/4]). | |
| 20 | ||
| 21 | :- use_module(kodkod_tools). | |
| 22 | ||
| 23 | :- module_info(group,kodkod). | |
| 24 | :- module_info(description,'This module contains the code to translate B expressions and predicates into Kodkod.'). | |
| 25 | ||
| 26 | kodkod_translate(TExpr,Typemap,Idmap,KExpr) :- | |
| 27 | create_environment(Typemap,Idmap,KEnv), | |
| 28 | kodkod_translate1(TExpr,KEnv,KExpr). | |
| 29 | ||
| 30 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 31 | % the translation environment: It stores | |
| 32 | % 1) the types (and represented by which relation), | |
| 33 | % 2) the identifiers (and represented by which relation), | |
| 34 | % 3) the quantified variables (and their relation) | |
| 35 | create_environment(Typemap,Idmap,kenv(Typemap,Idmap,Varmap)) :- | |
| 36 | empty_avl(Varmap). | |
| 37 | lookup_type_relation(Type,kenv(Typemap,_,_),Relname) :- | |
| 38 | avl_fetch(Type,Typemap,V), | |
| 39 | V = relation(Relname,_Size,_Relspec). | |
| 40 | lookup_id_relation(Id,kenv(_,Idmap,_),Relname,Types) :- | |
| 41 | avl_fetch(Id,Idmap,reldef(Relname,Types,_,_,_)). | |
| 42 | lookup_var(Id,kenv(_,_,Varmap),Varname) :- | |
| 43 | avl_fetch(Id,Varmap,Varname). | |
| 44 | add_var_to_environment(Id,Ref,kenv(Typemap,Idmap,VarmapIn),kenv(Typemap,Idmap,VarmapOut)) :- | |
| 45 | avl_store(Id,VarmapIn,Ref,VarmapOut). | |
| 46 | ||
| 47 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 48 | % initialise the Kodkod environment | |
| 49 | ||
| 50 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 51 | % translate predicates and expressions | |
| 52 | kodkod_translate1(TExpr,Env,KExpr) :- | |
| 53 | get_texpr_expr(TExpr,Expr), | |
| 54 | get_texpr_type(TExpr,Type1), remove_seq_type(Type1,Type), | |
| 55 | get_texpr_info(TExpr,Info), | |
| 56 | kodkod_translate2(Expr,Type,Info,Env,KExpr1), | |
| 57 | % enforce the use of integer atoms for integers used in sets | |
| 58 | ( Type = set(integer), KExpr1 \= _:_ -> | |
| 59 | KExpr = KExpr1:rel([IntAtoms]), | |
| 60 | intset_relation_kodkod_name(IntAtoms) | |
| 61 | ; | |
| 62 | KExpr = KExpr1). | |
| 63 | ||
| 64 | remove_seq_type(seq(T),Set) :- !,Set=set(couple(integer,T)). | |
| 65 | remove_seq_type(T,T). | |
| 66 | ||
| 67 | :- use_module(probsrc(bsyntaxtree),[get_texpr_set_type/2]). | |
| 68 | :- use_module(probsrc(typing_tools),[create_maximal_type_set/2]). | |
| 69 | ||
| 70 | kodkod_translate2(member(BElem,BSet),pred,Info,Env,K) :- | |
| 71 | get_texpr_expr(BSet,BFun), | |
| 72 | BFun =.. [FunFunctor,BDom,BRange], | |
| 73 | KFun =.. [FunFunctor,KDom,KRange], | |
| 74 | get_texpr_type(BSet,Type), | |
| 75 | kodkod_translate_binary_membership(KFun,KElem,Type,Info,K),!, | |
| 76 | kodkod_translate1(BElem,Env,KElem), | |
| 77 | kodkod_translate1(BDom,Env,KDom), | |
| 78 | kodkod_translate1(BRange,Env,KRange). | |
| 79 | kodkod_translate2(not_member(BElem,BSet),pred,Info,Env,not(K)) :- | |
| 80 | !,kodkod_translate2(member(BElem,BSet),pred,Info,Env,K). | |
| 81 | kodkod_translate2(domain_restriction(Dom,Rel),set(couple(_,RhType)),_,Env, | |
| 82 | intersection(product(KDom,relref(KRhRel)),KRel)) :- | |
| 83 | !,kodkod_translate1(Dom,Env,KDom), | |
| 84 | kodkod_translate1(Rel,Env,KRel), | |
| 85 | lookup_type_relation(RhType,Env,KRhRel). | |
| 86 | kodkod_translate2(domain_subtraction(Dom,Rel),set(couple(_,RhType)),_,Env, | |
| 87 | intersection(product(difference(univ,KDom),relref(KRhRel)),KRel)) :- | |
| 88 | !,kodkod_translate1(Dom,Env,KDom), | |
| 89 | kodkod_translate1(Rel,Env,KRel), | |
| 90 | lookup_type_relation(RhType,Env,KRhRel). | |
| 91 | kodkod_translate2(range_restriction(Rel,Dom),set(couple(LhType,_)),_,Env, | |
| 92 | intersection(KRel,product(relref(KLhRel),KDom))) :- | |
| 93 | !,kodkod_translate1(Dom,Env,KDom), | |
| 94 | kodkod_translate1(Rel,Env,KRel), | |
| 95 | lookup_type_relation(LhType,Env,KLhRel). | |
| 96 | kodkod_translate2(range_subtraction(Rel,Dom),set(couple(LhType,_)),_,Env, | |
| 97 | intersection(KRel,product(relref(KLhRel),difference(univ,KDom)))) :- | |
| 98 | !,kodkod_translate1(Dom,Env,KDom), | |
| 99 | kodkod_translate1(Rel,Env,KRel), | |
| 100 | lookup_type_relation(LhType,Env,KLhRel). | |
| 101 | kodkod_translate2(identifier(Id),_BType,_Info,Env,Ref) :- !, | |
| 102 | ( lookup_var(Id,Env,Varname) -> | |
| 103 | Ref = varref(Varname) | |
| 104 | ; lookup_id_relation(Id,Env,Relname,_KTypes) -> | |
| 105 | Ref = relref(Relname) | |
| 106 | ; lookup_type_relation(global(Id),Env,Relname) -> | |
| 107 | Ref = relref(Relname)). | |
| 108 | kodkod_translate2(set_extension([]),BType,Info,Env,Result) :- | |
| 109 | !, % normally should not happen, unless AST constructed by hand | |
| 110 | kodkod_translate2(empty_set,BType,Info,Env,Result). | |
| 111 | kodkod_translate2(set_extension(List),_BType,_,Env,Result) :- | |
| 112 | !, kodkod_translate_l(List,Env,KList), | |
| 113 | kodkod_extension_set(KList,Result). | |
| 114 | kodkod_translate2(forall(BIds,_,_),pred,_,_Env,true) :- | |
| 115 | % If there is an identifier without possible solution, the result is always true | |
| 116 | somechk(is_inconsistent_expression,BIds),!. | |
| 117 | kodkod_translate2(forall(BIds, Condition, Predicate),pred,_,Env, | |
| 118 | forall(Decls,Result)) :- | |
| 119 | !,kodkod_declarations1(BIds,Env,Subenv,ProvDecls), | |
| 120 | kodkod_translate1(Condition,Subenv,KCond), | |
| 121 | kodkod_translate1(Predicate,Subenv,KPred), | |
| 122 | kodkod_declarations2(ProvDecls,Env,KCond,NewKCond,Decls), | |
| 123 | kodkod_implication(NewKCond,KPred,Result). | |
| 124 | kodkod_translate2(exists(BIds,_),pred,_,_Env,false) :- | |
| 125 | % If there is an identifier without possible solution, the result is always false | |
| 126 | somechk(is_inconsistent_expression,BIds),!. | |
| 127 | kodkod_translate2(exists([BId], Membership),pred,_,Env,some(KSet)) :- | |
| 128 | % translate #e.e:M to some(M) | |
| 129 | get_texpr_expr(Membership,member(Elem,Set)), | |
| 130 | get_texpr_id(BId,Id),get_texpr_id(Elem,Id),!, | |
| 131 | kodkod_translate1(Set,Env,KSet). | |
| 132 | kodkod_translate2(exists(BIds, Predicate),pred,_,Env,exists(Decls,Result)) :- | |
| 133 | !,kodkod_declarations1(BIds,Env,Subenv,ProvDecls), | |
| 134 | kodkod_translate1(Predicate,Subenv,KPred), | |
| 135 | kodkod_declarations2(ProvDecls,Env,KPred,Result,Decls). | |
| 136 | kodkod_translate2(comprehension_set(BIds,_),BType,Info,Env,KEmptySet) :- | |
| 137 | % If there is an identifier without possible solution, the result is always empty | |
| 138 | somechk(is_inconsistent_expression,BIds),!, | |
| 139 | kodkod_translate2(empty_set,BType,Info,Env,KEmptySet). | |
| 140 | kodkod_translate2(comprehension_set(BIds,Predicate),set(_BType),_,Env, | |
| 141 | comp(Decls,Result)) :- | |
| 142 | !,kodkod_declarations1(BIds,Env,Subenv,ProvDecls), | |
| 143 | kodkod_translate1(Predicate,Subenv,KPred), | |
| 144 | kodkod_declarations2(ProvDecls,Env,KPred,Result,Decls). | |
| 145 | kodkod_translate2(domain(Rel),_,_,Env,K) :- | |
| 146 | !,get_texpr_type(Rel,RelType), | |
| 147 | kodkod_domain(KRel,RelType,K), | |
| 148 | kodkod_translate1(Rel,Env,KRel). | |
| 149 | kodkod_translate2(range(Rel),_,_,Env,K) :- | |
| 150 | !,get_texpr_type(Rel,RelType), | |
| 151 | kodkod_range(KRel,RelType,K), | |
| 152 | kodkod_translate1(Rel,Env,KRel). | |
| 153 | kodkod_translate2(first_of_pair(Couple),Type,Info,Env,K) :- | |
| 154 | !,kodkod_translate2(domain(Couple),Type,Info,Env,K). | |
| 155 | kodkod_translate2(second_of_pair(Couple),Type,Info,Env,K) :- | |
| 156 | !,kodkod_translate2(range(Couple),Type,Info,Env,K). | |
| 157 | kodkod_translate2(composition(A,B),_BType,_,Env,join(KA,KB)) :- | |
| 158 | get_texpr_set_type(A,couple(_,IType)), | |
| 159 | type_arity(IType,1),!, | |
| 160 | kodkod_translate1(A,Env,KA), | |
| 161 | kodkod_translate1(B,Env,KB). | |
| 162 | kodkod_translate2(function(BFun,BArg),_BType,_,Env,Res) :- | |
| 163 | !, kodkod_function_application(BFun,BArg,Env,Res). | |
| 164 | kodkod_translate2(image(BRel,BArg),_BType,_,Env,Res) :- | |
| 165 | !, kodkod_function_application(BRel,BArg,Env,Res). | |
| 166 | kodkod_translate2(reverse(BRel),_BType,_,Env,Res) :- | |
| 167 | !, kodkod_reverse(BRel,Env,Res). | |
| 168 | kodkod_translate2(integer(I),integer,_,_Env,int(I)) :- !. | |
| 169 | kodkod_translate2(unary_minus(TExpr),integer,_,_Env,int(N)) :- | |
| 170 | % Expressions of the form "-(1)" are translated to "-1" | |
| 171 | % there is another rule below for other forms of unary minus (translating "-x" to "0-x") | |
| 172 | get_texpr_expr(TExpr,integer(P)),!,N is -P. | |
| 173 | kodkod_translate2(general_sum([TId],TPred,Expr),integer,_,Env,sum(KSet)) :- | |
| 174 | % we support only a restricted sort of the general sum: | |
| 175 | % SIGMA (x).(x:S|x) | |
| 176 | % The rewriting rules (see kodkod2.pl) convert the more general form "SIGMA (x).(P|x)" | |
| 177 | % into this form by "SIGMA (x).(x:{x|P}|x)" | |
| 178 | % The expression must only contain the quantified variable: | |
| 179 | get_texpr_id(TId,Id), get_texpr_id(Expr,Id),!, | |
| 180 | % Simple form: the predicate is of the form x:S | |
| 181 | get_texpr_expr(TPred,member(TElem,TSet)),get_texpr_id(TElem,Id), | |
| 182 | kodkod_translate1(TSet,Env,KSet). | |
| 183 | kodkod_translate2(boolean_true,boolean,_,Env,relref(Relname)) :- !, | |
| 184 | lookup_id_relation('__kodkod__true',Env,Relname,_KTypes). | |
| 185 | kodkod_translate2(boolean_false,boolean,_,Env,relref(Relname)) :- !, | |
| 186 | lookup_id_relation('__kodkod__false',Env,Relname,_KTypes). | |
| 187 | kodkod_translate2(bool_set,set(boolean),_,Env,relref(Relname)) :- !, | |
| 188 | lookup_type_relation(boolean,Env,Relname). | |
| 189 | kodkod_translate2(empty_set,set(T),_,Env,Empty) :- !, | |
| 190 | kodkod_type_as_list(T,Env,Typelist), | |
| 191 | create_empty_set(Typelist,Empty). | |
| 192 | kodkod_translate2(partition(Set,Subsets),_,_,Env,and(KEquals,KDisjunct)) :- !, | |
| 193 | kodkod_translate_l([Set|Subsets],Env,[KSet|KSubsets]), | |
| 194 | kodkod_extension_set(KSubsets,KUnion), | |
| 195 | KEquals = equals(KSet,KUnion), | |
| 196 | all_disjunct(KSubsets,KDisjunct). | |
| 197 | kodkod_translate2(convert_bool(BCond),boolean,_,Env,if(KCond,KTrue,KFalse)) :- !, | |
| 198 | kodkod_translate1(BCond,Env,KCond), | |
| 199 | kodkod_translate2(boolean_true,boolean,[],Env,KTrue), | |
| 200 | kodkod_translate2(boolean_false,boolean,[],Env,KFalse). | |
| 201 | kodkod_translate2(concat(BA,BB),_,_,Env,union(KA,join(Adder,KB))) :- !, | |
| 202 | % To compute A^B, we use a form A \/ Adder[B] | |
| 203 | kodkod_translate1(BA,Env,KA), | |
| 204 | kodkod_translate1(BB,Env,KB), | |
| 205 | intset_relation_kodkod_name(I), | |
| 206 | % Adder is a set of the form {a,b | a=b+card(A)} | |
| 207 | Adder = comp([decl(lhr,1,one,relref(I)),decl(rhr,1,one,relref(I))], | |
| 208 | equals(sum(varref(lhr)),add(sum(varref(rhr)),card(KA)))). | |
| 209 | kodkod_translate2(value(V),Type,_Info,Env,K) :- ground(V), %print(try_translate_value(V)),nl, | |
| 210 | translate_value_to_kodkod(Type,Env,V,K),!. | |
| 211 | kodkod_translate2(value(Val),Type,Infos,Env,K) :- | |
| 212 | was_identifier(Val,Infos,ID),!, % identifier was compiled to value; this is a bit dangerous; we should ensure that the identifier ID is used only once | |
| 213 | %print(kodkod_value_as_id(V,ID)),nl, | |
| 214 | kodkod_translate2(identifier(ID),Type,Infos,Env,K). | |
| 215 | kodkod_translate2(event_b_identity,set(couple(Type,Type)),Info,Env,K) :- !, | |
| 216 | create_maximal_type_set(Type,TSet), | |
| 217 | kodkod_translate2(identity(TSet),set(couple(Type,Type)),Info,Env,K). | |
| 218 | kodkod_translate2(external_pred_call('LEQ_SYM',_),Type,Info,Env,K) :- !, | |
| 219 | kodkod_translate2(truth,Type,Info,Env,K). | |
| 220 | kodkod_translate2(external_pred_call('LEQ_SYM_BREAK',_),Type,Info,Env,K) :- !, | |
| 221 | kodkod_translate2(truth,Type,Info,Env,K). | |
| 222 | kodkod_translate2(Expr,_,Info,Env,Result) :- | |
| 223 | functor(Expr,Functor,Arity), | |
| 224 | functor(Tmp,Functor,Arity), | |
| 225 | kodkod_short(Tmp,_,SC),!, | |
| 226 | check_side_condition(SC,Expr,Info), | |
| 227 | Expr =.. [Functor|Args], | |
| 228 | same_length(Args,TArgs), | |
| 229 | Lookup =.. [Functor|TArgs], | |
| 230 | kodkod_translate_l(Args,Env,TArgs), | |
| 231 | kodkod_short(Lookup,Result,_). | |
| 232 | kodkod_translate2(E,T,I,_,_) :- | |
| 233 | create_texpr(E,T,I,TE), | |
| 234 | %print(expr(E,T)),nl, | |
| 235 | throw(kodkod(unsupported_expression(TE))). | |
| 236 | ||
| 237 | was_identifier(_V,Infos,ID) :- member(was_identifier(ID),Infos). | |
| 238 | was_identifier(Val,_,GS) :- nonvar(Val), Val=global_set(GS). | |
| 239 | ||
| 240 | check_side_condition(none,_Expr,_). | |
| 241 | check_side_condition(cond(_,_),Expr,Info) :- | |
| 242 | kodkod_short(Expr,_,cond(Msg,Condition)), | |
| 243 | ( call(Condition) -> true | |
| 244 | ; | |
| 245 | translate_bexpression(Expr,PPExpr), | |
| 246 | throw(kodkod(side_condition(Msg,PPExpr,Info)))). | |
| 247 | ||
| 248 | translate_value_to_kodkod(integer,_Env,int(I),int(I)) :- !. | |
| 249 | translate_value_to_kodkod(set(Type),Env,V,K) :- !, | |
| 250 | kodkod_type_as_list(Type,Env,Typelist), | |
| 251 | expand_custom_set_to_list(V,List), | |
| 252 | maplist(translate_value_to_kodkod1(Type,Env),List,KList), | |
| 253 | ( KList = [] -> create_empty_set(Typelist,K) | |
| 254 | ; KList = [H|T] -> foldl(union_kvalues,T,H,K)). | |
| 255 | translate_value_to_kodkod(Type,Env,V,K) :- | |
| 256 | translate_value_to_kodkod1(Type,Env,V,K). | |
| 257 | ||
| 258 | :- use_module(probsrc(b_global_sets),[is_b_global_constant/3]). | |
| 259 | translate_value_to_kodkod1(integer,_Env,int(I),int(I):rel([IntAtoms])) :- !, | |
| 260 | intset_relation_kodkod_name(IntAtoms). | |
| 261 | translate_value_to_kodkod1(couple(TA,TB),Env,(A,B),product(KA,KB)) :- !, | |
| 262 | translate_value_to_kodkod1(TA,Env,A,KA), | |
| 263 | translate_value_to_kodkod1(TB,Env,B,KB). | |
| 264 | translate_value_to_kodkod1(global(GS),Env,fd(Nr,GS),Res) :- !, | |
| 265 | is_b_global_constant(GS,Nr,CstId), | |
| 266 | lookup_id_relation(CstId,Env,Relname,_KTypes), Res=relref(Relname). | |
| 267 | translate_value_to_kodkod1(boolean,Env,Val,KodkodResult) :- !, | |
| 268 | translate_boolean(Val,Env,KodkodResult). | |
| 269 | translate_value_to_kodkod1(Type,_,_,_) :- | |
| 270 | format('Cannot translate type in value/1 to kodkod: ~w~n',[Type]),fail. | |
| 271 | ||
| 272 | translate_boolean(pred_true,Env,relref(Relname)) :- | |
| 273 | lookup_id_relation('__kodkod__true',Env,Relname,_KTypes). | |
| 274 | translate_boolean(pred_false,Env,relref(Relname)) :- | |
| 275 | lookup_id_relation('__kodkod__false',Env,Relname,_KTypes). | |
| 276 | ||
| 277 | union_kvalues(A,B,union(A,B)). | |
| 278 | ||
| 279 | create_empty_set([Type],R) :- !,R=empty:rel([Type]). | |
| 280 | create_empty_set([Type|Rest],product(empty:rel([Type]),R)) :- | |
| 281 | create_empty_set(Rest,R). | |
| 282 | ||
| 283 | :- use_module(probsrc(error_manager),[add_warning/3]). | |
| 284 | ||
| 285 | kodkod_short(B,K,none) :- kodkod_short(B,K),!. | |
| 286 | kodkod_short(B,K,cond(Msg,Cond)) :- kodkod_short(B,K,Msg,Cond). | |
| 287 | ||
| 288 | kodkod_short(truth,true). | |
| 289 | kodkod_short(falsity,false). | |
| 290 | kodkod_short(negation(A),not(A)). | |
| 291 | kodkod_short(conjunct(A,B),and(A,B)). | |
| 292 | kodkod_short(disjunct(A,B), or(A,B)). | |
| 293 | kodkod_short(implication(A,B),implies(A,B)). | |
| 294 | kodkod_short(equivalence(A,B), iff(A,B)). | |
| 295 | ||
| 296 | kodkod_short(equal(A,B),equals(A,B)). | |
| 297 | ||
| 298 | kodkod_short(member(A,B),in(A,B)). | |
| 299 | kodkod_short(subset(A,B),K) :- kodkod_short(member(A,B),K). | |
| 300 | kodkod_short(not_subset(A,B),not(K)) :- kodkod_short(subset(A,B),K). | |
| 301 | kodkod_short(subset_strict(A,B),and(in(A,B),not(equals(A,B)))). | |
| 302 | kodkod_short(not_subset_strict(A,B),or(not(in(A,B)),equals(A,B))). | |
| 303 | ||
| 304 | kodkod_short(cartesian_product(A,B),product(A,B)). | |
| 305 | kodkod_short(intersection(A,B),intersection(A,B)). | |
| 306 | kodkod_short(union(A,B),union(A,B)). | |
| 307 | kodkod_short(closure(E),closure(E)). | |
| 308 | kodkod_short(set_subtraction(A,B),difference(A,B)). | |
| 309 | kodkod_short(overwrite(A,B),overwrite(A,B)). | |
| 310 | kodkod_short(couple(A,B),product(A,B)). | |
| 311 | ||
| 312 | kodkod_short(card(X),card(X)). | |
| 313 | kodkod_short(size(X),card(X)). | |
| 314 | kodkod_short(greater(A,B),gt(A,B)). | |
| 315 | kodkod_short(greater_equal(A,B),gte(A,B)). | |
| 316 | kodkod_short(less(A,B),lt(A,B)). | |
| 317 | kodkod_short(less_equal(A,B),lte(A,B)). | |
| 318 | ||
| 319 | kodkod_short(add(A,B),add(A,B)). | |
| 320 | kodkod_short(minus(A,B),sub(A,B)). | |
| 321 | kodkod_short(multiplication(A,B),mul(A,B)). | |
| 322 | kodkod_short(div(A,B),div(A,B)). | |
| 323 | kodkod_short(floored_div(A,B),div(A,B)) :- | |
| 324 | add_warning(kodkod_translate,'Translating floored division as truncated division: ',div(A,B)). | |
| 325 | kodkod_short(modulo(A,B),mod(A,B)). | |
| 326 | kodkod_short(unary_minus(A),sub(int(0),A)). | |
| 327 | %kodkod_short(event_b_identity,iden). % this leads to error in test 711; maybe iden is the function over all types | |
| 328 | ||
| 329 | kodkod_short(identity(A),intersection(product(A,A),iden), | |
| 330 | 'Identity is supported only on unary sets', | |
| 331 | side_condition_type_arity(A,1)). | |
| 332 | kodkod_short(reflexive_closure(A),closure(union(intersection(product(All,All),iden),A)), | |
| 333 | 'Reflexive closure is supported only on binary relations on unary sets', | |
| 334 | side_condition_type_arity(A,2)) :- All=union(prj([0],A),prj([1],A)). | |
| 335 | ||
| 336 | :- public side_condition_type_arity/2. | |
| 337 | side_condition_type_arity(Expr,Arity) :- | |
| 338 | get_texpr_type(Expr,Type), | |
| 339 | type_arity(Type,Arity). | |
| 340 | ||
| 341 | kodkod_translate_l([],_,[]). | |
| 342 | kodkod_translate_l([E|ERest],Env,[K|KRest]) :- | |
| 343 | kodkod_translate1(E,Env,K), | |
| 344 | kodkod_translate_l(ERest,Env,KRest). | |
| 345 | ||
| 346 | kodkod_translate_binary_membership(partial_function(D,R),F,T,Info,pfunc(F,D,R)) :- is_binary_relation(T,Info). | |
| 347 | kodkod_translate_binary_membership(total_function(D,R),F,T,Info,func(F,D,R)) :- is_binary_relation(T,Info). | |
| 348 | kodkod_translate_binary_membership(partial_injection(D,R),F,T,Info,and(pfunc(F,D,R),Inj)) :- | |
| 349 | is_binary_relation(T,Info),k_is_injective(F,Inj). | |
| 350 | kodkod_translate_binary_membership(total_injection(D,R),F,T,Info,and(func(F,D,R),Inj)) :- | |
| 351 | is_binary_relation(T,Info),k_is_injective(F,Inj). | |
| 352 | kodkod_translate_binary_membership(partial_surjection(D,R),F,T,Info,and(pfunc(F,D,R),Surj)) :- | |
| 353 | is_binary_relation(T,Info),k_is_surjective(F,R,T,Surj). | |
| 354 | kodkod_translate_binary_membership(total_surjection(D,R),F,T,Info,and(func(F,D,R),Surj)) :- | |
| 355 | is_binary_relation(T,Info),k_is_surjective(F,R,T,Surj). | |
| 356 | kodkod_translate_binary_membership(partial_bijection(D,R),F,T,Info,and(pfunc(F,D,R),Bij)) :- | |
| 357 | is_binary_relation(T,Info),k_is_bijective(F,R,T,Bij). | |
| 358 | kodkod_translate_binary_membership(total_bijection(D,R),F,T,Info,and(func(F,D,R),Bij)) :- | |
| 359 | is_binary_relation(T,Info),k_is_bijective(F,R,T,Bij). | |
| 360 | kodkod_translate_binary_membership(total_relation(D,R),F,set(T),_Info,and(equals(Dom,D),in(Ran,R))) :- | |
| 361 | kodkod_domain(F,T,Dom), kodkod_range(F,T,Ran). | |
| 362 | kodkod_translate_binary_membership(surjection_relation(D,R),F,set(T),_Info,and(in(Dom,D),equals(Ran,R))) :- | |
| 363 | kodkod_domain(F,T,Dom), kodkod_range(F,T,Ran). | |
| 364 | ||
| 365 | is_binary_relation(Type,_) :- type_arity(Type,2),!. | |
| 366 | is_binary_relation(Type,Info) :- | |
| 367 | pretty_type(Type,PType), | |
| 368 | throw(kodkod(side_condition('Functions are only supported for binary relations',PType,Info))). | |
| 369 | ||
| 370 | k_is_injective(F,in(join(F,transpose(F)),iden)). | |
| 371 | k_is_surjective(F,R,set(Type),in(R,Range)) :- | |
| 372 | kodkod_range(F,Type,Range). | |
| 373 | k_is_bijective(F,R,Type,and(Inj,Surj)) :- | |
| 374 | k_is_injective(F,Inj), k_is_surjective(F,R,Type,Surj). | |
| 375 | ||
| 376 | kodkod_domain(KRel,BType,prj(Positions,KRel)) :- | |
| 377 | remove_optional_set(BType,couple(DType,_RType)), | |
| 378 | type_arity(DType,Arity),enumerate(Arity,0,Positions). | |
| 379 | kodkod_range(KRel,BType,prj(Positions,KRel)) :- | |
| 380 | remove_optional_set(BType,couple(DType,RType)), | |
| 381 | type_arity(DType,Start),type_arity(RType,Arity), | |
| 382 | enumerate(Arity,Start,Positions). | |
| 383 | ||
| 384 | % function application / relational image | |
| 385 | % kodkod_function_application(+BFun,+BArg,+Env,-K): | |
| 386 | % translate a function application f(x) where BFun is f and x is BArg to Kodkod | |
| 387 | % Usually a function application f(x) can be translated to join(kx,kf) | |
| 388 | % when kx is unary. But for n-ary kx (n>1) we have to apply several joins manually | |
| 389 | kodkod_function_application(BFun,BArg,Env,K) :- | |
| 390 | kodkod_translate1(BFun,Env,KFun), | |
| 391 | kodkod_translate1(BArg,Env,KArg), | |
| 392 | get_texpr_type(BArg,ArgType), type_arity(ArgType,ArgArity), | |
| 393 | get_texpr_type(BFun,FunType), type_arity(FunType,FunArity), | |
| 394 | kodkod_function_application_aux(ArgArity,FunArity,KFun,KArg,K). | |
| 395 | kodkod_function_application_aux(1,_,KFun,KArg,K) :- !, | |
| 396 | K = join(KArg,KFun). | |
| 397 | kodkod_function_application_aux(ArgArity,FunArity,KFun,KArg,K) :- | |
| 398 | % We translate f(x) resp. f[{x}] to | |
| 399 | % prj( nx..(nf-1), { e : f | prj( 0..(nx-1), e ) = x } ) | |
| 400 | % with nf resp. nx being the arity of f resp. x | |
| 401 | K = prj(RightPos,CompSet), | |
| 402 | CompSet = comp([decl(KId,FunArity,one,KFun)],equals(prj(LeftPos,varref(KId)),KArg)), | |
| 403 | % LeftPos is 0..(nx-1) (contains ArgArity elements starting with 0) | |
| 404 | enumerate(ArgArity,0,LeftPos), | |
| 405 | % RightPos is nx..(nf-1) (contains FunArity-ArgArity elements starting with nx) | |
| 406 | RemainingPos is FunArity-ArgArity, | |
| 407 | enumerate(RemainingPos,ArgArity,RightPos), | |
| 408 | % e is some unique identifier | |
| 409 | unique_identifier(KId). | |
| 410 | ||
| 411 | kodkod_reverse(BArg,Env,K) :- | |
| 412 | kodkod_translate1(BArg,Env,KArg), | |
| 413 | get_texpr_type(BArg,ArgType), type_arity(ArgType,ArgArity), | |
| 414 | kodkod_reverse_aux(ArgArity,KArg,K). | |
| 415 | kodkod_reverse_aux(2,KArg,transpose(KArg)) :- !. | |
| 416 | kodkod_reverse_aux(Arity,KArg,prj(Rev,KArg)) :- | |
| 417 | enumerate(Arity,0,Positions), | |
| 418 | reverse(Positions,Rev). | |
| 419 | ||
| 420 | ||
| 421 | % two-phase handling of declarations in forall, exists, etc. | |
| 422 | kodkod_declarations1([],SubEnv,SubEnv,[]). | |
| 423 | kodkod_declarations1([TExpr|IRest], | |
| 424 | Env,Env2, | |
| 425 | [provdecl(KId,Type,Analysis)|DRest]) :- | |
| 426 | get_texpr_id(TExpr,Id), | |
| 427 | get_texpr_type(TExpr,Type), | |
| 428 | get_texpr_info(TExpr,Info), | |
| 429 | (memberchk(analysis(Analysis),Info) -> true ; Analysis=[]), | |
| 430 | unique_identifier(v,Id,KId), | |
| 431 | add_var_to_environment(Id,KId,Env,SubEnv), | |
| 432 | kodkod_declarations1(IRest,SubEnv,Env2,DRest). | |
| 433 | ||
| 434 | kodkod_declarations2([],_,KCond,KCond,[]). | |
| 435 | kodkod_declarations2([provdecl(KId,Type,Analysis)|PRest], | |
| 436 | Env,KCond,KCond2, | |
| 437 | [decl(KId,Arity,Mult,Expr)|DRest]) :- | |
| 438 | type_arity(Type,Arity), | |
| 439 | kodkod_declaration(Type,KId,Analysis,Env,KCond,NewKCond,Mult,Expr), | |
| 440 | kodkod_declarations2(PRest,Env,NewKCond,KCond2,DRest). | |
| 441 | kodkod_declaration(integer,_KId,_Analysis,_Env,KCond,KCond,Mult,Expr) :- | |
| 442 | % TODO: we have to make a decision whether a quantified integer | |
| 443 | % variable should be the bit-representation of the value | |
| 444 | % (for variables that can take large values) | |
| 445 | % or a the item of the integer relation. | |
| 446 | % currently we do only the latter: | |
| 447 | !,Mult = one, | |
| 448 | intset_relation_kodkod_name(IntsetRelation), | |
| 449 | Expr = relref(IntsetRelation). | |
| 450 | kodkod_declaration(Type,KId,_Analysis,Env,KCond,NewKCond,Mult,Expr) :- | |
| 451 | (Type=set(_) -> Mult=set; Mult=one), | |
| 452 | ( find_in(KCond,KId,Expr,NewKCond) -> | |
| 453 | true | |
| 454 | ; | |
| 455 | % here we have to insert a possible choice for | |
| 456 | % integer variables. That possible choice should be returned | |
| 457 | % as a variable and later its value determine the outcome | |
| 458 | % of the choice. | |
| 459 | kodkod_type(Type,Env,Expr), | |
| 460 | NewKCond = KCond). | |
| 461 | ||
| 462 | find_in(Formula,Id,Expression,NewFormula) :- | |
| 463 | disassemble_conjunction(Formula,Parts), | |
| 464 | find_in2(Parts,Id,Expression,Rest), | |
| 465 | kodkod_conjunction(Rest,NewFormula). | |
| 466 | find_in2([in(varref(Id),Expr)|Rest], Id, Expr, Rest) :- !. | |
| 467 | find_in2([Pred|Rest], Id, Expr, [Pred|Result]) :- | |
| 468 | find_in2(Rest,Id,Expr,Result). | |
| 469 | ||
| 470 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 471 | % A Kodkod environment contains two maps: | |
| 472 | % a) The first one maps Kodkod types to references to relations that will | |
| 473 | % represents all elements to the given type | |
| 474 | % b) The second one maps an identifier to a reference to the relations that | |
| 475 | % represents the variable in | |
| 476 | ||
| 477 | %kodkod_subenv(Id,Ref,kenv(Types,OldBinds),kenv(Types,NewBinds)) :- | |
| 478 | % avl_store(Id,OldBinds,Ref,NewBinds). | |
| 479 | ||
| 480 | % End: Environment | |
| 481 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 482 | ||
| 483 | kodkod_type(T,Env,K) :- | |
| 484 | remove_optional_set(T,T2), | |
| 485 | kodkod_type2(T2,T2,Env,K). | |
| 486 | kodkod_type2(couple(A,B),_,Env,product(KA,KB)) :- !, | |
| 487 | kodkod_type2(A,A,Env,KA), | |
| 488 | kodkod_type2(B,B,Env,KB). | |
| 489 | kodkod_type2(Type,_,Env,relref(Ref)) :- | |
| 490 | lookup_type_relation(Type,Env,Ref),!. | |
| 491 | kodkod_type2(_,T,_Env,_Ref) :- | |
| 492 | throw(kodkod(unsupported_type(T))). | |
| 493 | ||
| 494 | kodkod_type_as_list(T,Env,TypeList) :- | |
| 495 | remove_optional_set(T,T2), | |
| 496 | kodkod_type_as_list2(T2,Env,TypeList). | |
| 497 | kodkod_type_as_list2(couple(A,B),Env,TypeList) :- !, | |
| 498 | kodkod_type_as_list2(A,Env,ATL), | |
| 499 | kodkod_type_as_list2(B,Env,BTL), | |
| 500 | append(ATL,BTL,TypeList). | |
| 501 | kodkod_type_as_list2(BType,Env,[KType]) :- | |
| 502 | lookup_type_relation(BType,Env,KType). | |
| 503 | ||
| 504 | remove_optional_set(set(A),B) :- !,A=B. | |
| 505 | remove_optional_set(T,T). | |
| 506 | ||
| 507 | type_arity(set(T),A) :- type_arity(T,A). | |
| 508 | type_arity(integer,1). | |
| 509 | type_arity(boolean,1). | |
| 510 | type_arity(global(_),1). | |
| 511 | type_arity(couple(A,B),Arity) :- | |
| 512 | type_arity(A,AA),type_arity(B,AB),Arity is AA+AB. | |
| 513 | ||
| 514 | % extension sets | |
| 515 | kodkod_extension_set([],none) :- !. | |
| 516 | kodkod_extension_set([Elem],Elem) :- !. | |
| 517 | kodkod_extension_set([Elem|Rest],union(Elem,Ext)) :- | |
| 518 | kodkod_extension_set(Rest,Ext). | |
| 519 | ||
| 520 | all_disjunct(Sets,K) :- | |
| 521 | all_disjunct2(Sets,Dis,[]), | |
| 522 | kodkod_conjunction(Dis,K). | |
| 523 | all_disjunct2([]) --> !. | |
| 524 | all_disjunct2([S|Rest]) --> | |
| 525 | all_disjunct3(Rest,S), | |
| 526 | all_disjunct2(Rest). | |
| 527 | all_disjunct3([],_) --> !. | |
| 528 | all_disjunct3([B|Rest],A) --> | |
| 529 | [no(intersection(A,B))], | |
| 530 | all_disjunct3(Rest,A). | |
| 531 | ||
| 532 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 533 | % helper predicates | |
| 534 | ||
| 535 | ||
| 536 | enumerate(0,_,[]) :- !. | |
| 537 | enumerate(N,S,[S|Rest]) :- N2 is N-1, S2 is S+1, enumerate(N2,S2,Rest). | |
| 538 |