(* File containing memory update expressions for the transitions in * the list reversal program. *) open Syntax open Program let x = VAR "x" let y = VAR "y" let t = VAR "t" let default_guard = GUARD(CONST(B(true))) let listrev_decls = [ (* Data types *) ("List", STRUCT( [("data",INT); ("n",POINTER(TYPENAME("List")))])) ; (* Variables *) ("x",POINTER(TYPENAME("List"))) ; ("y",POINTER(TYPENAME("List"))) ; ("t",POINTER(TYPENAME("List"))) ] (* control flow graph in ML notation *) let listrev_cfg = ["n_1", [ASGN(y, CONST(NULL)), "n_2"] (* n_1 -> (y = null) n_2 *) ; "n_2", [GUARD(EXPR(EQ,[x;CONST(NULL)])), "n_e"; (* n_2 (x == null) -> skip n_e *) SKIP, "n_e"; GUARD(EXPR(OP(NOT),[EXPR(EQ,[x;CONST(NULL)])])), "n_3"; (* n_2 (x != null) -> skip n_3 *) SKIP, "n_3"] ; "n_3", [ASGN(t, y), "n_4"] (* n_3 -> (t = y) n_4 *) ; "n_4", [ASGN(y, x), "n_5"] (* n_4 -> (y = x) n_5 *) ; "n_5", [ASGN(x, EXPR(ARROW "n", [x])), "n_6"] (* n_5 -> (x = x->n) n_6 *) ; "n_6", [ASGN(EXPR(ARROW "n",[y]), CONST(NULL)), "n_7"] (* n_6 -> (y->n = null) n_7 *) ; "n_7", [ASGN(EXPR(ARROW "n",[y]), t), "n_8"] (* n_7 -> (y->n = t) n_8 *) ; "n_8", [SKIP, "n_2"] (* n_8 true -> skip n_2 *) ; "n_e", (* exit node; no successors *) [] ] let listrev_inits = ["n_1"] let listrev = Final.make_program_from_lists listrev_decls listrev_cfg listrev_inits (* continue with abstraction stuff *) let listrev_init_pred_list = [(EXPR(CYCLIC([],["n"]), [y]), "n_e")] (* helpful constructors *) let null = CONST(NULL) let nondet = CONST(NONDET(BOOL)) let ff = CONST(B(false)) let tt = CONST(B(true)) let eq x y = EXPR(EQ,[x;y]) let reachp a f x y = EXPR(REACHP(a,f),[x;y]) let reach a f x y = EXPR(REACH(a,f),[x;y]) let dshared a f x y = EXPR(DSHARED(a,f),[x;y]) let cyclic a f x = EXPR(CYCLIC(a,f),[x]) let ite c x y = EXPR(ITE,[c;x;y]) let not x = EXPR(OP(NOT),[x]) let addrof x = EXPR(ADDROF,[x]) let dot x n = EXPR(DOT(n),[x]) let arrow x n = EXPR(ARROW(n),[x]) let deref x = EXPR(DEREF, [x]) let adot x n = EXPR(ADOT(n),[x]) (* Hints *) let listrev_hints = [ (* approx. (x==null)@n_2 with nondeterminism *) (eq x null, "n_2"), nondet ; (* approx. reach[(&(y->n),&(\*(x).n->n));n](t,*(x).n) @n_5 with ~dshared[;n](x,t)@n_5 to false *) (reach [(adot y "n");(adot (dot (deref x) "n") "n")] ["n"] t (dot (deref x) "n"), "n_5"), (ite (not (dshared [] ["n"] x t)) ff nondet) ; (* approx. reach[(&(y->n),&(\*(x).n->n));n](t,y) @n_5 with ~dshared[;n](x,t)@n_5 to reach[&(y->n);n](t,y) *) (reach [(adot y "n");(adot (dot (deref x) "n") "n")] ["n"] t y, "n_5"), (ite (not (dshared [] ["n"] x t)) (reach [(adot y "n")] ["n"] t y) nondet) ; (* approx. cyclic[(&(y->n),&(\*(x).n->n));n]t @n_5 with ~dshared[;n](x,t)@n_5 to cyclic[&(y->n);n]t *) (cyclic [(adot y "n");(adot (dot (deref x) "n") "n")] ["n"] t, "n_5"), (ite (not (dshared [] ["n"] x t)) (cyclic [(adot y "n")] ["n"] t) nondet) ; (* approx. (x==*(x).n) @n_4 with ~cyclic[;n]x to false *) (eq x (dot (deref x) "n"), "n_4"), (ite (not (cyclic [] ["n"] x)) ff nondet) ; (* approx. cyclic[&(x->n);n]*(x).n @n_4 with ~cyclic[;n]x to false *) (cyclic [(adot x "n")] ["n"] (dot (deref x) "n"), "n_4"), (ite (not (cyclic [] ["n"] x)) ff nondet) ; (* approx. dshared[&(y->n);n](\*(x).n,t) @n_5 with ~dshared[;n](x,t)@n_5 to false *) (dshared [(adot y "n")] ["n"] (dot (deref x) "n") t, "n_5"), (ite (not (dshared [] ["n"] x t)) ff nondet) ; (* approx. reach[&(x->n);n](\*(x).n,x) @n_4 with ~cyclic[;n]x to false *) (reach [(adot x "n")] ["n"] (dot (deref x) "n") x, "n_4"), (ite (not (cyclic [] ["n"] x)) ff nondet) ]