(* insert.ml. List insertion code. *) (* --- C syntax --- typedef struct A {int data; struct A *n} List; List *x; int a; List *t; /* x points to list; d is element to be inserted */ n1: t = (List* ) malloc (sizeof(List)); n2: t->data = a; n3: t->n = x; n4: x = t; ne: property: all addresses that are reachable from x initially are also reachable from x after the insertion of a. how to prove it: create a symbolic address "k", such that alloc(k) and reach[;"n"](x,k) holds initially. Now prove that alloc(k) and reach[;n](x,k) holds at end. Clearly, alloc(k) is unchanged (in backward direction) by any of the actions (only one to change it is free()) So now focus on showing reach[;n](x,k) *) open Syntax open Program let x = VAR "x" let t = VAR "t" let a = VAR "a" let k = VAR "k" let default_guard = GUARD(CONST(B(true))) let insert_decls = [ (* Data types *) ("List", STRUCT( [("data",INT); ("n",POINTER(TYPENAME("List")))])) ; (* Variables *) ("x",POINTER(TYPENAME("List"))) ; ("t",POINTER(TYPENAME("List"))) ; ("a",INT) ; ("k",POINTER(TYPENAME("List"))) ] let insert_cfg = ["n1", [ASGN(t, EXPR(MALLOC(TYPENAME("List")),[])), "n2"] (* n1 -> (t = (List* ) malloc (sizeof(List))) -> n2 *) ; "n2", [ASGN(EXPR(ARROW "data", [t]), a), "n3"] (* n2 -> (t->data = a) -> n3 *) ; "n3", [ASGN(EXPR(ARROW "n", [t]), x), "n4"] (* n3 -> (t->n = x) -> n4 *) ; "n4", [ASGN(x,t), "ne"] (* n4 -> ( x = t) -> ne *) ; "ne", [] (* ne has no successors *) ] let insert_inits = ["n1"] let insert = Final.make_program_from_lists insert_decls insert_cfg insert_inits (* abstraction stuff *) (* 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]) let insert_init_pred_list = [reach [] ["n"] x k, "ne"] (* no hints needed *) let insert_hints = [] let insert_ht = Hints.list_into_table insert_hints;; let test n = Final.abstract insert insert_ht insert_init_pred_list n;;