1% module shared_graph. /* Shape-graph with sharing information */
2
3% export var_edge(bff).
4% export sel_edge(bfff).
5% export is_shared(bf).
6
7:- import member/2 from basics.
8
9/* Auxiliary functions ----------------------------------------------- */
10
11singleton(X,NX) :- create_set(Temp), add_elem(X,Temp,NX).
12
13del_elem(X,NX,NY) :- singleton(X,Xset), difference(NX,Xset,NY).
14
15:- table transitively_points_to/3.
16
17transitively_points_to(U, NX, Z) :- var_edge(U, Z, NX).
18transitively_points_to(U, NX, Z) :- sel_edge(U, NY, _, NX),
19               		            transitively_points_to(U, NY, Z).
20
21disjoint_or_equal(X,Y) :- set_equal(X, Y).
22disjoint_or_equal(X,Y) :- inter(X, Y, []).
23
24rename_var_to_var(NT,X,Y,NZ) :- member(Y,NT), add_elem(X,NT,NZ).
25rename_var_to_var(NT,_,Y,NZ) :- not member(Y,NT), set_equal(NT, NZ).
26
27:- table var_edge/3, sel_edge/4, is_shared/2.
28
29/* Explicit Initializations */
30var_edge(V, X, NX) :- init_var_edge(V, X, NX).
31sel_edge(V, NX1,Sel,NX2) :- init_sel_edge(V, NX1, Sel, NX2).
32is_shared(V, NX) :- init_is_shared(V, NX).
33
34/* Edges with no pointer manipulation */
35var_edge(V,X,NX) :- identity(U, V), var_edge(U, X, NX).
36sel_edge(V,NX1,Sel,NX2) :- identity(U, V), sel_edge(U, NX1, Sel, NX2).
37is_shared(V,NX) :- identity(U, V), is_shared(U, NX).
38
39/* x := nil ------------------------------------------------------- */
40
41var_edge(V, Y, NYP) :-
42    assign_nil_to_var(U,V,X),
43    var_edge(U, Y ,NY),
44    Y\==X,
45    del_elem(X, NY, NYP).
46sel_edge(V, NY1P, Sel, NY2P) :-
47    assign_nil_to_var(U,V,X),
48    sel_edge(U, NY1, Sel, NY2),
49    transitively_points_to(U, NY1, Y1),
50    Y1 \== X,
51    transitively_points_to(U, NY2, Y2),
52    Y2 \== X,
53    del_elem(X, NY1, NY1P),
54    del_elem(X, NY2, NY2P).
55is_shared(V, NYP) :-
56    assign_nil_to_var(U,V,X),
57    is_shared(U, NY),
58    transitively_points_to(U, NY, Y),
59    Y \== X,
60    del_elem(X, NY, NYP).
61
62/* x.sel_0 := nil ----------------------------------------------------- */
63var_edge(V, Z, NZ) :-
64    assign_nil_to_sel(U,V,_,_Sel0),
65    var_edge(U, Z, NZ).
66
67sel_edge(V, NZ1, Sel, NZ2) :-
68    assign_nil_to_sel(U,V,_,Sel0),
69    sel_edge(U, NZ1, Sel, NZ2),
70    Sel \== Sel0.
71sel_edge(V, NZ1, Sel, NZ2) :-
72    assign_nil_to_sel(U,V,X,_Sel0),
73    sel_edge(U, NZ1, Sel, NZ2),
74    not member(X,NZ1).
75
76is_shared(V, NZ) :-
77    assign_nil_to_sel(U,V,_,_Sel0),
78    is_shared(U, NZ),
79    sel_edge(V, NZ1, _, NZ),
80    sel_edge(V, NZ2, _, NZ),
81    inter(NZ1, NZ2, []).
82is_shared(V, NZ) :-
83    assign_nil_to_sel(U,V,_,_Sel0),
84    is_shared(U, NZ),
85    sel_edge(V, NW, Sel1, NZ),
86    sel_edge(V, NW, Sel2, NZ),
87    Sel1 \== Sel2.
88
89/*  x := new  ------------------------------------ */
90
91var_edge(V, Z, NZ) :-
92    assign_new_to_var(U,V,_),
93    var_edge(U, Z, NZ).
94var_edge(V, X, NX) :-	/* Create the new var_edge from X */
95    assign_new_to_var(_,V,X),
96    singleton(X,NX).
97sel_edge(V, NY, Sel, NZ) :-
98    assign_new_to_var(U,V,_),
99    sel_edge(U, NY, Sel, NZ).
100is_shared(V, NZ) :-
101    assign_new_to_var(U,V,_),
102    is_shared(U, NZ).
103
104/* x := y --------------------------- */
105
106var_edge(V, Z, NZP) :-
107    assign_var_to_var(U,V,X,Y),
108    var_edge(U, Z, NZ),
109    rename_var_to_var(NZ,X,Y,NZP).
110var_edge(V, X, NXY) :-
111    assign_var_to_var(U,V,X,Y),
112    var_edge(U, Y, NY),
113    rename_var_to_var(NY,X,Y,NXY).
114sel_edge(V, NZ1P, Sel, NZ2P) :-
115    assign_var_to_var(U,V,X,Y),
116    sel_edge(U, NZ1, Sel, NZ2),
117    rename_var_to_var(NZ1,X,Y,NZ1P),
118    rename_var_to_var(NZ2,X,Y,NZ2P).
119is_shared(V, NZP) :-
120    assign_var_to_var(U,V,X,Y),
121    is_shared(U, NZ),
122    rename_var_to_var(NZ,X,Y,NZP).
123
124/* x := y.sel0 ---------------------------- */
125
126var_edge(V, Z, NZ) :-
127    assign_sel_to_var(U,V,_X,_Y,_Sel0),
128    var_edge(U, Z, NZ).
129var_edge(V, X, NXZ) :-
130    assign_sel_to_var(U,V,X,Y,Sel0),
131    var_edge(U, Y, NY),
132    sel_edge(U, NY, Sel0, NZ),
133    add_elem(X,NZ,NXZ).
134var_edge(V, Z, NXZ) :-
135    assign_sel_to_var(U,V,X,Y,Sel0),
136    var_edge(U, Y, NY),
137    sel_edge(U, NY, Sel0, NZ),
138    add_elem(X,NZ,NXZ),
139    var_edge(U, Z, NZ).
140/* old -> old */
141sel_edge(V, NZ1, Sel, NZ2) :-
142    assign_sel_to_var(U,V,_X,Y,_Sel0),
143    sel_edge(U, NZ1, Sel, NZ2),
144    not member(Y,NZ1).
145/* old -> old */
146sel_edge(V, NZ1, Sel, NZ2) :-
147    assign_sel_to_var(U,V,_X,_Y,Sel0),
148    sel_edge(U, NZ1, Sel, NZ2),
149    Sel \== Sel0.
150/* old -> new */
151sel_edge(V, NY, Sel0, NXZ) :-
152    assign_sel_to_var(U,V,X,Y,Sel0),
153    var_edge(U, Y, NY),
154    sel_edge(U, NY, Sel0, NZ),
155    add_elem(X,NZ,NXZ),
156    not set_equal(NY, NZ).
157%    NY \== NZ.
158/* new -> old */
159sel_edge(V, NXZ, Sel, NT) :-
160    assign_sel_to_var(U,V,X,Y,Sel0),
161    var_edge(U, Y, NY),
162    sel_edge(U, NY, Sel0, NZ),
163    add_elem(X,NZ,NXZ),
164    sel_edge(U, NZ, Sel, NT),
165    not set_equal(NZ, NY),
166%    NZ \== NY,
167    disjoint_or_equal(NXZ, NT). /* Can be replaced by NZ <> NT or NZ = {} */
168/* new -> old */
169sel_edge(V, NXZ, Sel, NT) :-
170    assign_sel_to_var(U,V,X,Y,Sel0),
171    var_edge(U, Y, NY),
172    sel_edge(U, NY, Sel0, NZ),
173    add_elem(X,NZ,NXZ),
174    sel_edge(U, NZ, Sel, NT),
175    Sel \== Sel0,
176    disjoint_or_equal(NXZ, NT). /* Can be replaced by NZ <> NT or NZ = {} */
177/* new -> new */
178sel_edge(V, NXY, Sel0, NXY1) :-
179    assign_sel_to_var(U,V,X,Y,Sel0),
180    var_edge(U, Y, NY),
181    sel_edge(U, NY, Sel0, NY),
182    add_elem(X,NY,NXY),
183    set_equal(NXY, NXY1).
184/* new -> new */
185sel_edge(V, NXZ, Sel, NXZ1) :-
186    assign_sel_to_var(U,V,X,Y,Sel0),
187    var_edge(U, Y, NY),
188    sel_edge(U, NY, Sel0, NZ),
189    is_shared(U, NZ),
190    sel_edge(U, NZ, Sel, NZ),
191    add_elem(X,NZ,NXZ),
192    set_equal(NXZ, NXZ1).
193/* old -> new */
194sel_edge(V, NT, Sel, NXZ) :-
195    assign_sel_to_var(U,V,X,Y,Sel0),
196    var_edge(U, Y, NY),
197    sel_edge(U, NY, Sel0, NZ),
198    is_shared(U, NZ),
199    add_elem(X,NZ,NXZ),
200    sel_edge(U, NT, Sel, NZ),
201    not member(Y,NT),
202    disjoint_or_equal(NT, NXZ). /* Can be replaced by NT <> NZ or NT = {} */
203/* old -> new */
204sel_edge(V, NT, Sel, NXZ) :-
205    assign_sel_to_var(U,V,X,Y,Sel0),
206    var_edge(U, Y, NY),
207    sel_edge(U, NY, Sel0, NZ),
208    is_shared(U, NZ),
209    add_elem(X,NZ,NXZ),
210    sel_edge(U, NT, Sel, NZ),
211    Sel \== Sel0,
212    disjoint_or_equal(NT, NXZ). /* Can be replaced by NT <> NZ or NT = {} */
213is_shared(V, NZ) :-
214    assign_sel_to_var(U,V,_X,_Y,_Sel0),
215    is_shared(U, NZ).
216is_shared(V, NXZ) :-
217    assign_sel_to_var(U,V,X,Y,Sel0),
218    is_shared(U,NZ),
219    var_edge(U, Y, NY),
220    sel_edge(U, NY, Sel0, NZ),
221    add_elem(X,NZ,NXZ).
222
223/* x.sel0 := y ------------------------------------------- */
224
225var_edge(V, Z, NZ) :-
226    assign_var_to_sel(U,V,_X,_Sel0,_Y),
227    var_edge(U, Z, NZ).
228/* old edges */
229sel_edge(V, NZ, Sel, NT) :-
230    assign_var_to_sel(U,V,_X,_Sel0,_Y),
231    sel_edge(U, NZ, Sel, NT).
232/* new edges */
233sel_edge(V, NX, Sel0, NY) :-
234    assign_var_to_sel(U,V,X,Sel0,Y),
235    var_edge(U, X, NX),
236    var_edge(U, Y, NY),
237    disjoint_or_equal(NX, NY).
238is_shared(V, NZ) :-
239    assign_var_to_sel(U,V,_X,_Sel0,_Y),
240    is_shared(U, NZ).
241is_shared(V, NY) :-
242    assign_var_to_sel(U,V,_X,_Sel0,Y),
243    var_edge(U, Y, NY),
244    sel_edge(U, _, _, NY).
245
246