Now I'm trying to prove a trivial array access procedure(file arr.c):
void set(int* arr, int key, int val)
{
arr[key] = val;
}
The file arr.c
is translated to arr.v
:
...
Definition f_set := {|
fn_return := tvoid;
fn_callconv := cc_default;
fn_params := ((_arr, (tptr tint)) :: (_key, tint) :: (_val, tint) :: nil);
fn_vars := nil;
fn_temps := nil;
fn_body :=
(Sassign
(Ederef
(Ebinop Oadd (Etempvar _arr (tptr tint)) (Etempvar _key tint)
(tptr tint)) tint) (Etempvar _val tint))
|}.
...
Here is the beginning of my proof (file verif_arr.v):
Require Import floyd.proofauto.
Require Import arr.
Local Open Scope logic.
Local Open Scope Z.
Inductive repr : Z -> val -> Prop :=
| mk_repr : forall z, z >= 0 -> z < Int.modulus -> repr z (Vint (Int.repr z)).
Function aPut (arr:Z -> val) (k:Z) (v:val) : Z -> val :=
fun (kk:Z) => if (Z.eq_dec k kk) then v else arr kk.
Definition set_spec :=
DECLARE _set
WITH sh : share, k : Z, arr : Z->val, vk : val, v : val, varr : val
PRE [_key OF tint, _val OF tint, _arr OF (tptr tint)]
PROP (0 <= k < 100; forall i, 0 <= i < 100 -> is_int (arr i);
writable_share sh; repr k vk)
LOCAL (`(eq vk) (eval_id _key);
`(eq varr) (eval_id _arr);
`(eq v) (eval_id _val);
`isptr (eval_id _arr))
SEP (`(array_at tint sh arr
0 100) (eval_id _arr))
POST [tvoid] `(array_at tint sh (aPut arr k v)
0 100 varr).
Definition Vprog : varspecs := nil.
Definition Gprog : funspecs := set_spec :: nil.
Lemma body_set: semax_body Vprog Gprog f_set set_spec.
Proof.
start_function.
name karg _key.
name arrarg _arr.
name valarg _val.
forward.
entailer!.
After the entailer!.
tactic, I've got:
3 subgoals, subgoal 1 (ID 1261)
Espec : OracleKind
sh : share
k : Z
arr : Z -> val
H : 0 <= k < 100
H0 : forall i : Z, 0 <= i < 100 -> is_int (arr i)
H1 : writable_share sh
Delta := abbreviate : tycontext
MORE_COMMANDS := abbreviate : statement
Struct_env := abbreviate : type_id_env.type_id_env
karg : name _key
arrarg : name _arr
valarg : name _val
rho : environ
H2 : repr k (eval_id _key rho)
POSTCONDITION := abbreviate : ret_assert
H3 : isptr (eval_id _arr rho)
============================
offset_val (Int.repr (sizeof tint * 0)) (eval_id _arr rho) =
force_val (sem_add_pi tint (eval_id _arr rho) (eval_id _key rho))
subgoal 2 (ID 1266) is:
?890 = force_val (sem_cast_neutral (eval_id _val rho))
subgoal 3 (ID 1235) is:
semax Delta
(PROP ()
LOCAL (`(eq vk) (eval_id _key); `(eq varr) (eval_id _arr);
`(eq v) (eval_id _val); `isptr (eval_id _arr))
SEP (`(array_at tint sh (upd arr 0 ?890) 0 100) (eval_id _arr)))
(Sreturn None) POSTCONDITION
Now the questions:
In the specification set_spec
there is a precondition '(array_at tint sh arr 0 100) (eval_id _arr)
(here instead of '
should be backtick, which breaks the formatting). Why is this statement not present in the hypotheses list?
The first subgoal seems to me like it tryes to dereference 0 cell of the array (arr + 0), and it should be equal to a key-th cell (arr + key). That has nothing to do with the code or postcondition and certainly unprovable. What did go wrong here?
I use:
VST version:
Definition svn_rev := "6834P".
Definition release := "1.5".
Definition date := "2014-10-02".
CompCert version: 2.4
Coq version:
The Coq Proof Assistant, version 8.4pl3 (January 2014)
compiled on Jan 19 2014 23:14:16 with OCaml 4.01.0
The last local ...
part in the post condition turned out redundant.
First, the precondition '(array_at tint sh arr 0 100) (eval_id _arr)
is actually present behind abbreviate
in Delta hypothesis.
Second, it turned out, that entailer!.
tactic is not safe, and can produce unprovable goals from eligible ones. In this case,
is_int v
to be able to assign it to a cell of an "all ints" array. Seemingly VST can't deduce the type from CompCert annotations.entailer!.
I need to prove first all propositions on the right hand side separately, and then I can apply entailer
to combine hypotheses.Here are the correct spec, and proof:
Inductive repr : Z -> val -> Prop :=
| mk_repr : forall z, z >= 0 -> z < Int.modulus -> repr z (Vint (Int.repr z)).
Function aPut (arr:Z -> val) (k:Z) (v:val) : Z -> val :=
fun (kk:Z) => if (Z.eq_dec k kk) then v else arr kk.
Definition set_spec :=
DECLARE _set
WITH sh : share, k : Z, arr : Z->val, vk : val, v : val, varr : val
PRE [_key OF tint, _val OF tint, _arr OF (tptr tint)]
PROP (0 <= k < 100; forall i, 0 <= i < 100 -> is_int (arr i);
writable_share sh; repr k vk; is_int v)
LOCAL (`(eq vk) (eval_id _key);
`(eq varr) (eval_id _arr);
`(eq v) (eval_id _val);
`isptr (eval_id _arr))
SEP (`(array_at tint sh arr
0 100) (eval_id _arr))
POST [tvoid] `(array_at tint sh (aPut arr k v)
0 100 varr).
Definition Vprog : varspecs := nil.
Definition Gprog : funspecs := set_spec :: nil.
Lemma body_set: semax_body Vprog Gprog f_set set_spec.
Proof.
start_function.
name karg _key.
name arrarg _arr.
name valarg _val.
forward.
instantiate (1:=v).
instantiate (2:=k).
assert (offset_val (Int.repr (sizeof tint * k)) (eval_id _arr rho) =
force_val (sem_add_pi tint (eval_id _arr rho) (eval_id _key rho))).
inversion H2.
rewrite sem_add_pi_ptr.
unfold force_val.
apply f_equal2.
rewrite mul_repr.
auto.
auto.
assumption.
assert (eval_id _val rho = force_val (sem_cast_neutral (eval_id _val rho))).
apply is_int_e in H3.
destruct H3 as [n VtoN].
rewrite VtoN.
auto.
entailer.
forward.
Qed.