proofmode.v 9.01 KB
Newer Older
1
From iris.program_logic Require Export weakestpre.
Robbert Krebbers's avatar
Robbert Krebbers committed
2
From iris.proofmode Require Import coq_tactics.
3
From iris.proofmode Require Export tactics.
4
From iris.heap_lang Require Export tactics lifting.
5
Set Default Proof Using "Type".
Robbert Krebbers's avatar
Robbert Krebbers committed
6
7
Import uPred.

8
9
10
11
12
13
14
Ltac wp_simpl :=
  try iStartProof;
  try lazymatch goal with
  | |- envs_entails ?Δ (wp ?E ?e ?Q) =>
      let e' := eval simpl in e in change (envs_entails Δ (wp E e' Q))
  end.

15
Lemma tac_wp_pure `{heapG Σ} Δ Δ' E e1 e2 φ Φ :
16
17
  PureExec φ e1 e2 
  φ 
18
  IntoLaterNEnvs 1 Δ Δ' 
19
20
  envs_entails Δ' (WP e2 @ E {{ Φ }}) 
  envs_entails Δ (WP e1 @ E {{ Φ }}).
21
Proof.
22
  rewrite /envs_entails=> ??? HΔ'. rewrite into_laterN_env_sound /=.
23
  rewrite HΔ' -wp_pure_step_later //.
24
Qed.
25

26
Lemma tac_wp_value `{heapG Σ} Δ E Φ e v :
27
  IntoVal e v 
28
  envs_entails Δ (Φ v)  envs_entails Δ (WP e @ E {{ Φ }}).
29
30
31
Proof. rewrite /envs_entails=> ? ->. by apply wp_value. Qed.

Ltac wp_value_head := eapply tac_wp_value; [apply _|lazy beta].
Robbert Krebbers's avatar
Robbert Krebbers committed
32

33
Tactic Notation "wp_pure" open_constr(efoc) :=
Robbert Krebbers's avatar
Robbert Krebbers committed
34
  iStartProof;
35
  lazymatch goal with
Robbert Krebbers's avatar
Robbert Krebbers committed
36
37
38
39
40
41
42
43
44
45
  | |- envs_entails _ (wp ?E ?e ?Q) =>
    let e := eval simpl in e in
    reshape_expr e ltac:(fun K e' =>
      unify e' efoc;
      eapply (tac_wp_pure _ _ _ (fill K e'));
      [apply _                        (* PureExec *)
      |try fast_done                  (* The pure condition for PureExec *)
      |apply _                        (* IntoLaters *)
      |simpl_subst; try wp_value_head (* new goal *)
      ])
46
47
   || fail "wp_pure: cannot find" efoc "in" e "or" efoc "is not a reduct"
  | _ => fail "wp_pure: not a 'wp'"
48
49
  end.

50
51
52
53
54
55
56
57
58
59
60
61
Tactic Notation "wp_if" := wp_pure (If _ _ _).
Tactic Notation "wp_if_true" := wp_pure (If (Lit (LitBool true)) _ _).
Tactic Notation "wp_if_false" := wp_pure (If (Lit (LitBool false)) _ _).
Tactic Notation "wp_unop" := wp_pure (UnOp _ _).
Tactic Notation "wp_binop" := wp_pure (BinOp _ _ _).
Tactic Notation "wp_op" := wp_unop || wp_binop.
Tactic Notation "wp_rec" := wp_pure (App _ _).
Tactic Notation "wp_lam" := wp_rec.
Tactic Notation "wp_let" := wp_lam.
Tactic Notation "wp_seq" := wp_lam.
Tactic Notation "wp_proj" := wp_pure (Fst _) || wp_pure (Snd _).
Tactic Notation "wp_case" := wp_pure (Case _ _ _).
62
Tactic Notation "wp_match" := wp_case; wp_let.
63

64
65
66
Lemma tac_wp_bind `{heapG Σ} K Δ E Φ e f :
  f = (λ e, fill K e)  (* as an eta expanded hypothesis so that we can `simpl` it *)
  envs_entails Δ (WP e @ E {{ v, WP f (of_val v) @ E {{ Φ }} }})%I 
67
  envs_entails Δ (WP fill K e @ E {{ Φ }}).
68
Proof. rewrite /envs_entails=> -> ->. by apply: wp_bind. Qed.
69

Robbert Krebbers's avatar
Robbert Krebbers committed
70
71
72
Ltac wp_bind_core K :=
  lazymatch eval hnf in K with
  | [] => idtac
73
  | _ => eapply (tac_wp_bind K); [simpl; reflexivity|lazy beta]
Robbert Krebbers's avatar
Robbert Krebbers committed
74
75
  end.

76
77
78
Tactic Notation "wp_bind" open_constr(efoc) :=
  iStartProof;
  lazymatch goal with
79
  | |- envs_entails _ (wp ?E ?e ?Q) =>
80
81
    reshape_expr e ltac:(fun K e' => unify e' efoc; wp_bind_core K)
    || fail "wp_bind: cannot find" efoc "in" e
82
83
84
85
  | _ => fail "wp_bind: not a 'wp'"
  end.

(** Heap tactics *)
Robbert Krebbers's avatar
Robbert Krebbers committed
86
Section heap.
87
Context `{heapG Σ}.
88
89
90
Implicit Types P Q : iProp Σ.
Implicit Types Φ : val  iProp Σ.
Implicit Types Δ : envs (iResUR Σ).
Robbert Krebbers's avatar
Robbert Krebbers committed
91

92
Lemma tac_wp_alloc Δ Δ' E j K e v Φ :
93
  IntoVal e v 
94
  IntoLaterNEnvs 1 Δ Δ' 
Robbert Krebbers's avatar
Robbert Krebbers committed
95
  ( l,  Δ'',
96
    envs_app false (Esnoc Enil j (l  v)) Δ' = Some Δ'' 
97
98
    envs_entails Δ'' (WP fill K (Lit (LitLoc l)) @ E {{ Φ }})) 
  envs_entails Δ (WP fill K (Alloc e) @ E {{ Φ }}).
Robbert Krebbers's avatar
Robbert Krebbers committed
99
Proof.
100
101
  rewrite /envs_entails=> ?? HΔ.
  rewrite -wp_bind. eapply wand_apply; first exact: wp_alloc.
102
  rewrite left_id into_laterN_env_sound; apply later_mono, forall_intro=> l.
Robbert Krebbers's avatar
Robbert Krebbers committed
103
104
105
106
  destruct (HΔ l) as (Δ''&?&HΔ'). rewrite envs_app_sound //; simpl.
  by rewrite right_id HΔ'.
Qed.

107
Lemma tac_wp_load Δ Δ' E i K l q v Φ :
108
  IntoLaterNEnvs 1 Δ Δ' 
Robbert Krebbers's avatar
Robbert Krebbers committed
109
  envs_lookup i Δ' = Some (false, l {q} v)%I 
110
111
  envs_entails Δ' (WP fill K (of_val v) @ E {{ Φ }}) 
  envs_entails Δ (WP fill K (Load (Lit (LitLoc l))) @ E {{ Φ }}).
Robbert Krebbers's avatar
Robbert Krebbers committed
112
Proof.
113
114
  rewrite /envs_entails=> ???.
  rewrite -wp_bind. eapply wand_apply; first exact: wp_load.
115
  rewrite into_laterN_env_sound -later_sep envs_lookup_split //; simpl.
Robbert Krebbers's avatar
Robbert Krebbers committed
116
117
118
  by apply later_mono, sep_mono_r, wand_mono.
Qed.

119
Lemma tac_wp_store Δ Δ' Δ'' E i K l v e v' Φ :
120
  IntoVal e v' 
121
  IntoLaterNEnvs 1 Δ Δ' 
Robbert Krebbers's avatar
Robbert Krebbers committed
122
123
  envs_lookup i Δ' = Some (false, l  v)%I 
  envs_simple_replace i false (Esnoc Enil i (l  v')) Δ' = Some Δ'' 
124
125
  envs_entails Δ'' (WP fill K (Lit LitUnit) @ E {{ Φ }}) 
  envs_entails Δ (WP fill K (Store (Lit (LitLoc l)) e) @ E {{ Φ }}).
Robbert Krebbers's avatar
Robbert Krebbers committed
126
Proof.
127
128
  rewrite /envs_entails=> ?????.
  rewrite -wp_bind. eapply wand_apply; first by eapply wp_store.
129
  rewrite into_laterN_env_sound -later_sep envs_simple_replace_sound //; simpl.
Robbert Krebbers's avatar
Robbert Krebbers committed
130
131
132
  rewrite right_id. by apply later_mono, sep_mono_r, wand_mono.
Qed.

133
Lemma tac_wp_cas_fail Δ Δ' E i K l q v e1 v1 e2 Φ :
Robbert Krebbers's avatar
Robbert Krebbers committed
134
  IntoVal e1 v1  AsVal e2 
135
  IntoLaterNEnvs 1 Δ Δ' 
Robbert Krebbers's avatar
Robbert Krebbers committed
136
  envs_lookup i Δ' = Some (false, l {q} v)%I  v  v1 
137
138
  envs_entails Δ' (WP fill K (Lit (LitBool false)) @ E {{ Φ }}) 
  envs_entails Δ (WP fill K (CAS (Lit (LitLoc l)) e1 e2) @ E {{ Φ }}).
Robbert Krebbers's avatar
Robbert Krebbers committed
139
Proof.
140
141
  rewrite /envs_entails=> ??????.
  rewrite -wp_bind. eapply wand_apply; first exact: wp_cas_fail.
142
  rewrite into_laterN_env_sound -later_sep envs_lookup_split //; simpl.
Robbert Krebbers's avatar
Robbert Krebbers committed
143
144
145
  by apply later_mono, sep_mono_r, wand_mono.
Qed.

146
Lemma tac_wp_cas_suc Δ Δ' Δ'' E i K l v e1 v1 e2 v2 Φ :
147
  IntoVal e1 v1  IntoVal e2 v2 
148
  IntoLaterNEnvs 1 Δ Δ' 
149
  envs_lookup i Δ' = Some (false, l  v)%I  v = v1 
Robbert Krebbers's avatar
Robbert Krebbers committed
150
  envs_simple_replace i false (Esnoc Enil i (l  v2)) Δ' = Some Δ'' 
151
152
  envs_entails Δ'' (WP fill K (Lit (LitBool true)) @ E {{ Φ }}) 
  envs_entails Δ (WP fill K (CAS (Lit (LitLoc l)) e1 e2) @ E {{ Φ }}).
Robbert Krebbers's avatar
Robbert Krebbers committed
153
Proof.
154
155
  rewrite /envs_entails=> ???????; subst.
  rewrite -wp_bind. eapply wand_apply; first exact: wp_cas_suc.
156
  rewrite into_laterN_env_sound -later_sep envs_simple_replace_sound //; simpl.
Robbert Krebbers's avatar
Robbert Krebbers committed
157
158
159
160
161
  rewrite right_id. by apply later_mono, sep_mono_r, wand_mono.
Qed.
End heap.

Tactic Notation "wp_apply" open_constr(lem) :=
162
163
  iPoseProofCore lem as false true (fun H =>
    lazymatch goal with
164
    | |- envs_entails _ (wp ?E ?e ?Q) =>
165
      reshape_expr e ltac:(fun K e' =>
166
        wp_bind_core K; iApplyHyp H; try iNext; wp_simpl) ||
167
168
169
170
171
      lazymatch iTypeOf H with
      | Some (_,?P) => fail "wp_apply: cannot apply" P
      end
    | _ => fail "wp_apply: not a 'wp'"
    end).
Robbert Krebbers's avatar
Robbert Krebbers committed
172
173

Tactic Notation "wp_alloc" ident(l) "as" constr(H) :=
174
  iStartProof;
175
  lazymatch goal with
176
  | |- envs_entails _ (wp ?E ?e ?Q) =>
177
    first
178
      [reshape_expr e ltac:(fun K e' =>
179
         eapply (tac_wp_alloc _ _ _ H K); [apply _|..])
180
      |fail 1 "wp_alloc: cannot find 'Alloc' in" e];
181
    [apply _
182
183
184
    |first [intros l | fail 1 "wp_alloc:" l "not fresh"];
      eexists; split;
        [env_cbv; reflexivity || fail "wp_alloc:" H "not fresh"
185
        |wp_simpl; try wp_value_head]]
186
  | _ => fail "wp_alloc: not a 'wp'"
Robbert Krebbers's avatar
Robbert Krebbers committed
187
  end.
188

189
190
Tactic Notation "wp_alloc" ident(l) :=
  let H := iFresh in wp_alloc l as H.
Robbert Krebbers's avatar
Robbert Krebbers committed
191
192

Tactic Notation "wp_load" :=
193
  iStartProof;
194
  lazymatch goal with
195
  | |- envs_entails _ (wp ?E ?e ?Q) =>
196
    first
197
      [reshape_expr e ltac:(fun K e' => eapply (tac_wp_load _ _ _ _ K))
198
      |fail 1 "wp_load: cannot find 'Load' in" e];
199
200
201
    [apply _
    |let l := match goal with |- _ = Some (_, (?l {_} _)%I) => l end in
     iAssumptionCore || fail "wp_load: cannot find" l "↦ ?"
202
    |wp_simpl; try wp_value_head]
203
  | _ => fail "wp_load: not a 'wp'"
Robbert Krebbers's avatar
Robbert Krebbers committed
204
205
206
  end.

Tactic Notation "wp_store" :=
207
  iStartProof;
208
  lazymatch goal with
209
  | |- envs_entails _ (wp ?E ?e ?Q) =>
210
    first
211
      [reshape_expr e ltac:(fun K e' =>
212
         eapply (tac_wp_store _ _ _ _ _ K); [apply _|..])
213
      |fail 1 "wp_store: cannot find 'Store' in" e];
214
    [apply _
215
216
217
    |let l := match goal with |- _ = Some (_, (?l {_} _)%I) => l end in
     iAssumptionCore || fail "wp_store: cannot find" l "↦ ?"
    |env_cbv; reflexivity
218
    |wp_simpl; try first [wp_pure (Seq (Lit LitUnit) _)|wp_value_head]]
219
  | _ => fail "wp_store: not a 'wp'"
Robbert Krebbers's avatar
Robbert Krebbers committed
220
221
222
  end.

Tactic Notation "wp_cas_fail" :=
223
  iStartProof;
224
  lazymatch goal with
225
  | |- envs_entails _ (wp ?E ?e ?Q) =>
226
    first
227
      [reshape_expr e ltac:(fun K e' =>
228
         eapply (tac_wp_cas_fail _ _ _ _ K); [apply _|apply _|..])
229
      |fail 1 "wp_cas_fail: cannot find 'CAS' in" e];
230
    [apply _
231
232
233
    |let l := match goal with |- _ = Some (_, (?l {_} _)%I) => l end in
     iAssumptionCore || fail "wp_cas_fail: cannot find" l "↦ ?"
    |try congruence
234
    |wp_simpl; try wp_value_head]
235
  | _ => fail "wp_cas_fail: not a 'wp'"
Robbert Krebbers's avatar
Robbert Krebbers committed
236
237
238
  end.

Tactic Notation "wp_cas_suc" :=
239
  iStartProof;
240
  lazymatch goal with
241
  | |- envs_entails _ (wp ?E ?e ?Q) =>
242
    first
243
      [reshape_expr e ltac:(fun K e' =>
244
         eapply (tac_wp_cas_suc _ _ _ _ _ K); [apply _|apply _|..])
245
      |fail 1 "wp_cas_suc: cannot find 'CAS' in" e];
246
    [apply _
247
248
249
250
    |let l := match goal with |- _ = Some (_, (?l {_} _)%I) => l end in
     iAssumptionCore || fail "wp_cas_suc: cannot find" l "↦ ?"
    |try congruence
    |env_cbv; reflexivity
251
    |wp_simpl; try wp_value_head]
252
  | _ => fail "wp_cas_suc: not a 'wp'"
Robbert Krebbers's avatar
Robbert Krebbers committed
253
  end.