lshared: Local sharing. Definition: lshared(x,A,F,M) = (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): reach1(u,x,A,F,M) & reach1(v,x,A,F,M)) Wp: wlp(M := M[i <- c], lshared(x,A,F,M)) = (by definition) wlp(M := M[i <- c], (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): reach1(u,x,A,F,M) & reach1(v,x,A,F,M))) = (distributing wlp over \exists as update is deterministic and terminating) (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): wlp(M := M[i <- c],reach1(u,x,A,F,M)) & wlp(M := M[i <- c],reach1(v,x,A,F,M))) = (using wlp for reach1) (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): [F*(u,i,A) & ~A(i) & F*(c,x,A) | reach1(u,x,Ai,F,M)] & [F*(v,i,A) & ~A(i) & F*(c,x,A) | reach1(v,x,Ai,F,M)]) = (expanding; distributing \exists over |) (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): F*(u,i,A) & ~A(i) & F*(c,x,A) & F*(v,i,A)) | (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): F*(u,i,A) & ~A(i) & F*(c,x,A) & reach1(v,x,Ai,F,M)) | (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): reach1(u,x,Ai,F,M) & F*(v,i,A) & ~A(i) & F*(c,x,A)) | (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): reach1(u,x,Ai,F,M) & reach1(v,x,Ai,F,M)) = (re-writing and simplifying) (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): F*(u,i,A) & F*(v,i,A)) & ~A(i) & F*(c,x,A) | (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): F*(u,i,A) & reach1(v,x,Ai,F,M)) & ~A(i) & F*(c,x,A) | (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): reach1(u,x,Ai,F,M) & F*(v,i,A)) & ~A(i) & F*(c,x,A) | lshared(x,Ai,F,M) = (in general, reach1(x,y,Ai,F,M) => x\neq i. So,take u=i in (2) and v=i in (3)) (\exists u,v: ~(F*(u,v,A) | F*(v,u,A)): F*(u,i,A) & F*(v,i,A)) & ~A(i) & F*(c,x,A) | (\exists v: reach1(v,x,Ai,F,M)) & ~A(i) & F*(c,x,A) | (\exists u: reach1(u,x,Ai,F,M)) & ~A(i) & F*(c,x,A) | lshared(x,Ai,F,M) = (assumption 2 about F (below)) (\exists u: reach1(u,x,Ai,F,M)) & ~A(i) & F*(c,x,A) | lshared(x,Ai,F,M) = (definition) reach1_to(x,Ai,F,M) & ~A(i) & F*(c,x,A) | lshared(x,Ai,F,M) [] This creates the need for the predicate reach1_to(x,A,F,M) = (\exists u: reach1(u,x,A,F,M)) so we need to compute wlp for this predicate - see below. Assumption 2. F*(u,i,A) & F*(v,i,A) => (F*(u,v,A) | F*(v,u,A) i.e., if u and v both reach address i without dereferencing, then one must be reachable from the other; so they must be sub-components of the same struct type. Used in wlp calculation for lshared() Definition: reach1_to(x,A,F,M) = (\exists u: reach1(u,x,A,F,M)) Wp: wlp(M := M[i <- c], reach1_to(x,A,F,M)) = (expanding) wlp(M := M[i <- c], (\exists u: reach1(u,x,A,F,M))) = (distributing wlp through \exists, deterministic,terminating action) (\exists u: wlp(M := M[i <- c], reach1(u,x,A,F,M))) = (wlp for reach1) (\exists u: F*(u,i,A) & ~A(i) & F*(c,x,A) | reach1(u,x,Ai,F,M)) = (distributing \exists over | and simplifying) (\exists u: F*(u,i,A)) & ~A(i) & F*(c,x,A) | (\exists u: reach1(u,x,Ai,F,M)) = (simplifying -- take u=i to instantiate \exists in first term) ~A(i) & F*(c,x,A) | reach1_to(x,Ai,F,M) []