class_instances.v 24.4 KB
Newer Older
1
From iris.proofmode Require Export classes.
2
From iris.algebra Require Import gmap.
3
From iris.prelude Require Import gmultiset.
4
From iris.base_logic Require Import big_op.
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Import uPred.

Section classes.
Context {M : ucmraT}.
Implicit Types P Q R : uPred M.

(* FromAssumption *)
Global Instance from_assumption_exact p P : FromAssumption p P P.
Proof. destruct p; by rewrite /FromAssumption /= ?always_elim. Qed.
Global Instance from_assumption_always_l p P Q :
  FromAssumption p P Q  FromAssumption p ( P) Q.
Proof. rewrite /FromAssumption=><-. by rewrite always_elim. Qed.
Global Instance from_assumption_always_r P Q :
  FromAssumption true P Q  FromAssumption true P ( Q).
Proof. rewrite /FromAssumption=><-. by rewrite always_always. Qed.
20
Global Instance from_assumption_bupd p P Q :
21
  FromAssumption p P Q  FromAssumption p P (|==> Q)%I.
22
Proof. rewrite /FromAssumption=>->. apply bupd_intro. Qed.
23
24

(* IntoPure *)
Ralf Jung's avatar
Ralf Jung committed
25
Global Instance into_pure_pure φ : @IntoPure M ⌜φ⌝ φ.
26
Proof. done. Qed.
27
Global Instance into_pure_eq {A : ofeT} (a b : A) :
28
29
  Timeless a  @IntoPure M (a  b) (a  b).
Proof. intros. by rewrite /IntoPure timeless_eq. Qed.
30
31
Global Instance into_pure_cmra_valid `{CMRADiscrete A} (a : A) :
  @IntoPure M ( a) ( a).
32
33
34
Proof. by rewrite /IntoPure discrete_valid. Qed.

(* FromPure *)
Ralf Jung's avatar
Ralf Jung committed
35
Global Instance from_pure_pure φ : @FromPure M ⌜φ⌝ φ.
36
Proof. done. Qed.
37
Global Instance from_pure_internal_eq {A : ofeT} (a b : A) :
38
39
40
41
  @FromPure M (a  b) (a  b).
Proof.
  rewrite /FromPure. eapply pure_elim; [done|]=> ->. apply internal_eq_refl'.
Qed.
42
43
Global Instance from_pure_cmra_valid {A : cmraT} (a : A) :
  @FromPure M ( a) ( a).
44
45
Proof.
  rewrite /FromPure. eapply pure_elim; [done|]=> ?.
46
  rewrite -cmra_valid_intro //. auto with I.
47
Qed.
48
Global Instance from_pure_bupd P φ : FromPure P φ  FromPure (|==> P) φ.
49
Proof. rewrite /FromPure=> ->. apply bupd_intro. Qed.
50
51
52
53
54
55
56
57
58
59
60
61

(* IntoPersistentP *)
Global Instance into_persistentP_always_trans P Q :
  IntoPersistentP P Q  IntoPersistentP ( P) Q | 0.
Proof. rewrite /IntoPersistentP=> ->. by rewrite always_always. Qed.
Global Instance into_persistentP_always P : IntoPersistentP ( P) P | 1.
Proof. done. Qed.
Global Instance into_persistentP_persistent P :
  PersistentP P  IntoPersistentP P P | 100.
Proof. done. Qed.

(* IntoLater *)
62
63
64
65
66
67
Global Instance into_laterN_default n P : IntoLaterN n P P | 1000.
Proof. apply laterN_intro. Qed.
Global Instance into_laterN_later n P Q :
  IntoLaterN n P Q  IntoLaterN (S n) ( P) Q.
Proof. by rewrite /IntoLaterN=>->. Qed.
Global Instance into_laterN_laterN n P : IntoLaterN n (^n P) P.
68
Proof. done. Qed.
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
Global Instance into_laterN_laterN_plus n m P Q :
  IntoLaterN m P Q  IntoLaterN (n + m) (^n P) Q.
Proof. rewrite /IntoLaterN=>->. by rewrite laterN_plus. Qed.

Global Instance into_laterN_and n P1 P2 Q1 Q2 :
  IntoLaterN n P1 Q1  IntoLaterN n P2 Q2  IntoLaterN n (P1  P2) (Q1  Q2).
Proof. intros ??; red. by rewrite laterN_and; apply and_mono. Qed.
Global Instance into_laterN_or n P1 P2 Q1 Q2 :
  IntoLaterN n P1 Q1  IntoLaterN n P2 Q2  IntoLaterN n (P1  P2) (Q1  Q2).
Proof. intros ??; red. by rewrite laterN_or; apply or_mono. Qed.
Global Instance into_laterN_sep n P1 P2 Q1 Q2 :
  IntoLaterN n P1 Q1  IntoLaterN n P2 Q2  IntoLaterN n (P1  P2) (Q1  Q2).
Proof. intros ??; red. by rewrite laterN_sep; apply sep_mono. Qed.

Global Instance into_laterN_big_sepL n {A} (Φ Ψ : nat  A  uPred M) (l: list A) :
  ( x k, IntoLaterN n (Φ k x) (Ψ k x)) 
  IntoLaterN n ([ list] k  x  l, Φ k x) ([ list] k  x  l, Ψ k x).
Proof.
  rewrite /IntoLaterN=> ?. rewrite big_sepL_laterN. by apply big_sepL_mono.
Qed.
Global Instance into_laterN_big_sepM n `{Countable K} {A}
90
    (Φ Ψ : K  A  uPred M) (m : gmap K A) :
91
92
  ( x k, IntoLaterN n (Φ k x) (Ψ k x)) 
  IntoLaterN n ([ map] k  x  m, Φ k x) ([ map] k  x  m, Ψ k x).
93
Proof.
94
  rewrite /IntoLaterN=> ?. rewrite big_sepM_laterN; by apply big_sepM_mono.
95
Qed.
96
Global Instance into_laterN_big_sepS n `{Countable A}
97
    (Φ Ψ : A  uPred M) (X : gset A) :
98
99
100
101
102
103
104
105
106
  ( x, IntoLaterN n (Φ x) (Ψ x)) 
  IntoLaterN n ([ set] x  X, Φ x) ([ set] x  X, Ψ x).
Proof.
  rewrite /IntoLaterN=> ?. rewrite big_sepS_laterN; by apply big_sepS_mono.
Qed.
Global Instance into_laterN_big_sepMS n `{Countable A}
    (Φ Ψ : A  uPred M) (X : gmultiset A) :
  ( x, IntoLaterN n (Φ x) (Ψ x)) 
  IntoLaterN n ([ mset] x  X, Φ x) ([ mset] x  X, Ψ x).
107
Proof.
108
  rewrite /IntoLaterN=> ?. rewrite big_sepMS_laterN; by apply big_sepMS_mono.
109
110
111
Qed.

(* FromLater *)
112
Global Instance from_laterN_later P :FromLaterN 1 ( P) P | 0.
113
Proof. done. Qed.
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
Global Instance from_laterN_laterN n P : FromLaterN n (^n P) P | 0.
Proof. done. Qed.

(* The instances below are used when stripping a specific number of laters, or
to balance laters in different branches of ∧, ∨ and ∗. *)
Global Instance from_laterN_0 P : FromLaterN 0 P P | 100. (* fallthrough *)
Proof. done. Qed.
Global Instance from_laterN_later_S n P Q :
  FromLaterN n P Q  FromLaterN (S n) ( P) Q.
Proof. by rewrite /FromLaterN=><-. Qed.
Global Instance from_laterN_later_plus n m P Q :
  FromLaterN m P Q  FromLaterN (n + m) (^n P) Q.
Proof. rewrite /FromLaterN=><-. by rewrite laterN_plus. Qed.

Global Instance from_later_and n P1 P2 Q1 Q2 :
  FromLaterN n P1 Q1  FromLaterN n P2 Q2  FromLaterN n (P1  P2) (Q1  Q2).
Proof. intros ??; red. by rewrite laterN_and; apply and_mono. Qed.
Global Instance from_later_or n P1 P2 Q1 Q2 :
  FromLaterN n P1 Q1  FromLaterN n P2 Q2  FromLaterN n (P1  P2) (Q1  Q2).
Proof. intros ??; red. by rewrite laterN_or; apply or_mono. Qed.
Global Instance from_later_sep n P1 P2 Q1 Q2 :
  FromLaterN n P1 Q1  FromLaterN n P2 Q2  FromLaterN n (P1  P2) (Q1  Q2).
Proof. intros ??; red. by rewrite laterN_sep; apply sep_mono. Qed.
137
138

(* IntoWand *)
139
Global Instance into_wand_wand P Q Q' :
140
  FromAssumption false Q Q'  IntoWand (P - Q) P Q'.
141
142
143
144
Proof. by rewrite /FromAssumption /IntoWand /= => ->. Qed.
Global Instance into_wand_impl P Q Q' :
  FromAssumption false Q Q'  IntoWand (P  Q) P Q'.
Proof. rewrite /FromAssumption /IntoWand /= => ->. by rewrite impl_wand. Qed.
145
146
147
148
Global Instance into_wand_iff_l P Q : IntoWand (P  Q) P Q.
Proof. by apply and_elim_l', impl_wand. Qed.
Global Instance into_wand_iff_r P Q : IntoWand (P  Q) Q P.
Proof. apply and_elim_r', impl_wand. Qed.
149

150
151
Global Instance into_wand_always R P Q : IntoWand R P Q  IntoWand ( R) P Q.
Proof. rewrite /IntoWand=> ->. apply always_elim. Qed.
152
153
154
155
156
157
Global Instance into_wand_later (R1 R2 P Q : uPred M) :
  IntoLaterN 1 R1 R2  IntoWand R2 P Q  IntoWand R1 ( P) ( Q) | 99.
Proof. rewrite /IntoLaterN /IntoWand=> -> ->. by rewrite -later_wand. Qed.
Global Instance into_wand_laterN n (R1 R2 P Q : uPred M) :
  IntoLaterN n R1 R2  IntoWand R2 P Q  IntoWand R1 (^n P) (^n Q) | 100.
Proof. rewrite /IntoLaterN /IntoWand=> -> ->. by rewrite -laterN_wand. Qed.
158
Global Instance into_wand_bupd R P Q :
159
  IntoWand R P Q  IntoWand R (|==> P) (|==> Q) | 98.
160
Proof. rewrite /IntoWand=>->. apply wand_intro_l. by rewrite bupd_wand_r. Qed.
161
162
163
164
165

(* FromAnd *)
Global Instance from_and_and P1 P2 : FromAnd (P1  P2) P1 P2.
Proof. done. Qed.
Global Instance from_and_sep_persistent_l P1 P2 :
166
  PersistentP P1  FromAnd (P1  P2) P1 P2 | 9.
167
168
Proof. intros. by rewrite /FromAnd always_and_sep_l. Qed.
Global Instance from_and_sep_persistent_r P1 P2 :
169
  PersistentP P2  FromAnd (P1  P2) P1 P2 | 10.
170
Proof. intros. by rewrite /FromAnd always_and_sep_r. Qed.
171
172
Global Instance from_and_pure φ ψ : @FromAnd M ⌜φ  ψ⌝ ⌜φ⌝ ⌜ψ⌝.
Proof. by rewrite /FromAnd pure_and. Qed.
173
174
175
176
177
178
Global Instance from_and_always P Q1 Q2 :
  FromAnd P Q1 Q2  FromAnd ( P) ( Q1) ( Q2).
Proof. rewrite /FromAnd=> <-. by rewrite always_and. Qed.
Global Instance from_and_later P Q1 Q2 :
  FromAnd P Q1 Q2  FromAnd ( P) ( Q1) ( Q2).
Proof. rewrite /FromAnd=> <-. by rewrite later_and. Qed.
179
180
181
Global Instance from_and_laterN n P Q1 Q2 :
  FromAnd P Q1 Q2  FromAnd (^n P) (^n Q1) (^n Q2).
Proof. rewrite /FromAnd=> <-. by rewrite laterN_and. Qed.
182
183

(* FromSep *)
184
Global Instance from_sep_sep P1 P2 : FromSep (P1  P2) P1 P2 | 100.
185
Proof. done. Qed.
186
187
188
189
Global Instance from_sep_ownM (a b1 b2 : M) :
  FromOp a b1 b2 
  FromSep (uPred_ownM a) (uPred_ownM b1) (uPred_ownM b2).
Proof. intros. by rewrite /FromSep -ownM_op from_op. Qed.
190
191
Global Instance from_sep_pure φ ψ : @FromSep M ⌜φ  ψ⌝ ⌜φ⌝ ⌜ψ⌝.
Proof. by rewrite /FromSep pure_and sep_and. Qed.
192
193
194
195
196
197
Global Instance from_sep_always P Q1 Q2 :
  FromSep P Q1 Q2  FromSep ( P) ( Q1) ( Q2).
Proof. rewrite /FromSep=> <-. by rewrite always_sep. Qed.
Global Instance from_sep_later P Q1 Q2 :
  FromSep P Q1 Q2  FromSep ( P) ( Q1) ( Q2).
Proof. rewrite /FromSep=> <-. by rewrite later_sep. Qed.
198
199
200
Global Instance from_sep_laterN n P Q1 Q2 :
  FromSep P Q1 Q2  FromSep (^n P) (^n Q1) (^n Q2).
Proof. rewrite /FromSep=> <-. by rewrite laterN_sep. Qed.
201
Global Instance from_sep_bupd P Q1 Q2 :
202
  FromSep P Q1 Q2  FromSep (|==> P) (|==> Q1) (|==> Q2).
203
Proof. rewrite /FromSep=><-. apply bupd_sep. Qed.
204

205
206
207
208
209
Global Instance from_sep_big_sepL {A} (Φ Ψ1 Ψ2 : nat  A  uPred M) l :
  ( k x, FromSep (Φ k x) (Ψ1 k x) (Ψ2 k x)) 
  FromSep ([ list] k  x  l, Φ k x)
    ([ list] k  x  l, Ψ1 k x) ([ list] k  x  l, Ψ2 k x).
Proof. rewrite /FromSep=>?. rewrite -big_sepL_sepL. by apply big_sepL_mono. Qed.
210
211
212
Global Instance from_sep_big_sepM
    `{Countable K} {A} (Φ Ψ1 Ψ2 : K  A  uPred M) m :
  ( k x, FromSep (Φ k x) (Ψ1 k x) (Ψ2 k x)) 
213
214
  FromSep ([ map] k  x  m, Φ k x)
    ([ map] k  x  m, Ψ1 k x) ([ map] k  x  m, Ψ2 k x).
215
Proof. rewrite /FromSep=>?. rewrite -big_sepM_sepM. by apply big_sepM_mono. Qed.
216
217
Global Instance from_sep_big_sepS `{Countable A} (Φ Ψ1 Ψ2 : A  uPred M) X :
  ( x, FromSep (Φ x) (Ψ1 x) (Ψ2 x)) 
218
  FromSep ([ set] x  X, Φ x) ([ set] x  X, Ψ1 x) ([ set] x  X, Ψ2 x).
219
220
221
222
Proof. rewrite /FromSep=>?. rewrite -big_sepS_sepS. by apply big_sepS_mono. Qed.
Global Instance from_sep_big_sepMS `{Countable A} (Φ Ψ1 Ψ2 : A  uPred M) X :
  ( x, FromSep (Φ x) (Ψ1 x) (Ψ2 x)) 
  FromSep ([ mset] x  X, Φ x) ([ mset] x  X, Ψ1 x) ([ mset] x  X, Ψ2 x).
223
Proof.
224
  rewrite /FromSep=> ?. rewrite -big_sepMS_sepMS. by apply big_sepMS_mono.
225
226
Qed.

227
228
229
230
231
232
233
234
235
236
237
238
239
240
(* FromOp *)
Global Instance from_op_op {A : cmraT} (a b : A) : FromOp (a  b) a b.
Proof. by rewrite /FromOp. Qed.
Global Instance from_op_persistent {A : cmraT} (a : A) :
  Persistent a  FromOp a a a.
Proof. intros. by rewrite /FromOp -(persistent_dup a). Qed.
Global Instance from_op_pair {A B : cmraT} (a b1 b2 : A) (a' b1' b2' : B) :
  FromOp a b1 b2  FromOp a' b1' b2' 
  FromOp (a,a') (b1,b1') (b2,b2').
Proof. by constructor. Qed.
Global Instance from_op_Some {A : cmraT} (a : A) b1 b2 :
  FromOp a b1 b2  FromOp (Some a) (Some b1) (Some b2).
Proof. by constructor. Qed.

241
242
243
244
245
246
247
248
249
250
251
252
253
254
(* IntoOp *)
Global Instance into_op_op {A : cmraT} (a b : A) : IntoOp (a  b) a b.
Proof. by rewrite /IntoOp. Qed.
Global Instance into_op_persistent {A : cmraT} (a : A) :
  Persistent a  IntoOp a a a.
Proof. intros; apply (persistent_dup a). Qed.
Global Instance into_op_pair {A B : cmraT} (a b1 b2 : A) (a' b1' b2' : B) :
  IntoOp a b1 b2  IntoOp a' b1' b2' 
  IntoOp (a,a') (b1,b1') (b2,b2').
Proof. by constructor. Qed.
Global Instance into_op_Some {A : cmraT} (a : A) b1 b2 :
  IntoOp a b1 b2  IntoOp (Some a) (Some b1) (Some b2).
Proof. by constructor. Qed.

255
(* IntoAnd *)
256
Global Instance into_and_sep p P Q : IntoAnd p (P  Q) P Q.
257
258
Proof. by apply mk_into_and_sep. Qed.
Global Instance into_and_ownM p (a b1 b2 : M) :
259
  IntoOp a b1 b2 
260
261
  IntoAnd p (uPred_ownM a) (uPred_ownM b1) (uPred_ownM b2).
Proof. intros. apply mk_into_and_sep. by rewrite (into_op a) ownM_op. Qed.
262

263
Global Instance into_and_and P Q : IntoAnd true (P  Q) P Q.
264
Proof. done. Qed.
265
266
267
268
269
270
271
Global Instance into_and_and_persistent_l P Q :
  PersistentP P  IntoAnd false (P  Q) P Q.
Proof. intros; by rewrite /IntoAnd /= always_and_sep_l. Qed.
Global Instance into_and_and_persistent_r P Q :
  PersistentP Q  IntoAnd false (P  Q) P Q.
Proof. intros; by rewrite /IntoAnd /= always_and_sep_r. Qed.

272
273
274
275
276
277
278
Global Instance into_and_pure p φ ψ : @IntoAnd M p ⌜φ  ψ⌝ ⌜φ⌝ ⌜ψ⌝.
Proof. apply mk_into_and_sep. by rewrite pure_and always_and_sep_r. Qed.
Global Instance into_and_always p P Q1 Q2 :
  IntoAnd true P Q1 Q2  IntoAnd p ( P) ( Q1) ( Q2).
Proof.
  rewrite /IntoAnd=>->. destruct p; by rewrite ?always_and always_and_sep_r.
Qed.
279
280
281
Global Instance into_and_later p P Q1 Q2 :
  IntoAnd p P Q1 Q2  IntoAnd p ( P) ( Q1) ( Q2).
Proof. rewrite /IntoAnd=>->. destruct p; by rewrite ?later_and ?later_sep. Qed.
282
283
284
Global Instance into_and_laterN n p P Q1 Q2 :
  IntoAnd p P Q1 Q2  IntoAnd p (^n P) (^n Q1) (^n Q2).
Proof. rewrite /IntoAnd=>->. destruct p; by rewrite ?laterN_and ?laterN_sep. Qed.
285

286
287
288
289
290
291
292
293
294
Global Instance into_and_big_sepL {A} (Φ Ψ1 Ψ2 : nat  A  uPred M) p l :
  ( k x, IntoAnd p (Φ k x) (Ψ1 k x) (Ψ2 k x)) 
  IntoAnd p ([ list] k  x  l, Φ k x)
    ([ list] k  x  l, Ψ1 k x) ([ list] k  x  l, Ψ2 k x).
Proof.
  rewrite /IntoAnd=> HΦ. destruct p.
  - rewrite -big_sepL_and. apply big_sepL_mono; auto.
  - rewrite -big_sepL_sepL. apply big_sepL_mono; auto.
Qed.
295
Global Instance into_and_big_sepM
296
    `{Countable K} {A} (Φ Ψ1 Ψ2 : K  A  uPred M) p m :
297
  ( k x, IntoAnd p (Φ k x) (Ψ1 k x) (Ψ2 k x)) 
298
299
  IntoAnd p ([ map] k  x  m, Φ k x)
    ([ map] k  x  m, Ψ1 k x) ([ map] k  x  m, Ψ2 k x).
300
Proof.
301
  rewrite /IntoAnd=> HΦ. destruct p.
302
  - rewrite -big_sepM_and. apply big_sepM_mono; auto.
303
  - rewrite -big_sepM_sepM. apply big_sepM_mono; auto.
304
Qed.
305
306
Global Instance into_and_big_sepS `{Countable A} (Φ Ψ1 Ψ2 : A  uPred M) p X :
  ( x, IntoAnd p (Φ x) (Ψ1 x) (Ψ2 x)) 
307
  IntoAnd p ([ set] x  X, Φ x) ([ set] x  X, Ψ1 x) ([ set] x  X, Ψ2 x).
308
Proof.
309
  rewrite /IntoAnd=> HΦ. destruct p.
310
  - rewrite -big_sepS_and. apply big_sepS_mono; auto.
311
  - rewrite -big_sepS_sepS. apply big_sepS_mono; auto.
312
Qed.
313
314
315
316
317
318
319
320
Global Instance into_and_big_sepMS `{Countable A} (Φ Ψ1 Ψ2 : A  uPred M) p X :
  ( x, IntoAnd p (Φ x) (Ψ1 x) (Ψ2 x)) 
  IntoAnd p ([ mset] x  X, Φ x) ([ mset] x  X, Ψ1 x) ([ mset] x  X, Ψ2 x).
Proof.
  rewrite /IntoAnd=> HΦ. destruct p.
  - rewrite -big_sepMS_and. apply big_sepMS_mono; auto.
  - rewrite -big_sepMS_sepMS. apply big_sepMS_mono; auto.
Qed.
321
322
323
324

(* Frame *)
Global Instance frame_here R : Frame R R True.
Proof. by rewrite /Frame right_id. Qed.
Ralf Jung's avatar
Ralf Jung committed
325
Global Instance frame_here_pure φ Q : FromPure Q φ  Frame ⌜φ⌝ Q True.
326
Proof. rewrite /FromPure /Frame=> ->. by rewrite right_id. Qed.
327

328
Class MakeSep (P Q PQ : uPred M) := make_sep : P  Q  PQ.
329
330
331
332
Global Instance make_sep_true_l P : MakeSep True P P.
Proof. by rewrite /MakeSep left_id. Qed.
Global Instance make_sep_true_r P : MakeSep P True P.
Proof. by rewrite /MakeSep right_id. Qed.
333
Global Instance make_sep_default P Q : MakeSep P Q (P  Q) | 100.
334
335
Proof. done. Qed.
Global Instance frame_sep_l R P1 P2 Q Q' :
336
  Frame R P1 Q  MakeSep Q P2 Q'  Frame R (P1  P2) Q' | 9.
337
338
Proof. rewrite /Frame /MakeSep => <- <-. by rewrite assoc. Qed.
Global Instance frame_sep_r R P1 P2 Q Q' :
339
  Frame R P2 Q  MakeSep P1 Q Q'  Frame R (P1  P2) Q' | 10.
340
Proof. rewrite /Frame /MakeSep => <- <-. by rewrite assoc (comm _ R) assoc. Qed.
341
342
343
344
345
346

Class MakeAnd (P Q PQ : uPred M) := make_and : P  Q  PQ.
Global Instance make_and_true_l P : MakeAnd True P P.
Proof. by rewrite /MakeAnd left_id. Qed.
Global Instance make_and_true_r P : MakeAnd P True P.
Proof. by rewrite /MakeAnd right_id. Qed.
347
Global Instance make_and_default P Q : MakeAnd P Q (P  Q) | 100.
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
Proof. done. Qed.
Global Instance frame_and_l R P1 P2 Q Q' :
  Frame R P1 Q  MakeAnd Q P2 Q'  Frame R (P1  P2) Q' | 9.
Proof. rewrite /Frame /MakeAnd => <- <-; eauto 10 with I. Qed.
Global Instance frame_and_r R P1 P2 Q Q' :
  Frame R P2 Q  MakeAnd P1 Q Q'  Frame R (P1  P2) Q' | 10.
Proof. rewrite /Frame /MakeAnd => <- <-; eauto 10 with I. Qed.

Class MakeOr (P Q PQ : uPred M) := make_or : P  Q  PQ.
Global Instance make_or_true_l P : MakeOr True P True.
Proof. by rewrite /MakeOr left_absorb. Qed.
Global Instance make_or_true_r P : MakeOr P True True.
Proof. by rewrite /MakeOr right_absorb. Qed.
Global Instance make_or_default P Q : MakeOr P Q (P  Q) | 100.
Proof. done. Qed.
Global Instance frame_or R P1 P2 Q1 Q2 Q :
  Frame R P1 Q1  Frame R P2 Q2  MakeOr Q1 Q2 Q  Frame R (P1  P2) Q.
Proof. rewrite /Frame /MakeOr => <- <- <-. by rewrite -sep_or_l. Qed.

Global Instance frame_wand R P1 P2 Q2 :
368
  Frame R P2 Q2  Frame R (P1 - P2) (P1 - Q2).
369
370
371
372
373
374
375
376
377
378
379
Proof.
  rewrite /Frame=> ?. apply wand_intro_l.
  by rewrite assoc (comm _ P1) -assoc wand_elim_r.
Qed.

Class MakeLater (P lP : uPred M) := make_later :  P  lP.
Global Instance make_later_true : MakeLater True True.
Proof. by rewrite /MakeLater later_True. Qed.
Global Instance make_later_default P : MakeLater P ( P) | 100.
Proof. done. Qed.

380
Global Instance frame_later R R' P Q Q' :
381
  IntoLaterN 1 R' R  Frame R P Q  MakeLater Q Q'  Frame R' ( P) Q'.
382
Proof.
383
384
385
386
387
388
389
390
391
392
393
394
395
  rewrite /Frame /MakeLater /IntoLaterN=>-> <- <-. by rewrite later_sep.
Qed.

Class MakeLaterN (n : nat) (P lP : uPred M) := make_laterN : ^n P  lP.
Global Instance make_laterN_true n : MakeLaterN n True True.
Proof. by rewrite /MakeLaterN laterN_True. Qed.
Global Instance make_laterN_default P : MakeLaterN n P (^n P) | 100.
Proof. done. Qed.

Global Instance frame_laterN n R R' P Q Q' :
  IntoLaterN n R' R  Frame R P Q  MakeLaterN n Q Q'  Frame R' (^n P) Q'.
Proof.
  rewrite /Frame /MakeLater /IntoLaterN=>-> <- <-. by rewrite laterN_sep.
396
397
Qed.

398
399
400
401
Class MakeExcept0 (P Q : uPred M) := make_except_0 :  P  Q.
Global Instance make_except_0_True : MakeExcept0 True True.
Proof. by rewrite /MakeExcept0 except_0_True. Qed.
Global Instance make_except_0_default P : MakeExcept0 P ( P) | 100.
402
403
Proof. done. Qed.

404
405
Global Instance frame_except_0 R P Q Q' :
  Frame R P Q  MakeExcept0 Q Q'  Frame R ( P) Q'.
406
Proof.
407
408
  rewrite /Frame /MakeExcept0=><- <-.
  by rewrite except_0_sep -(except_0_intro R).
409
410
Qed.

411
412
413
414
415
416
417
Global Instance frame_exist {A} R (Φ Ψ : A  uPred M) :
  ( a, Frame R (Φ a) (Ψ a))  Frame R ( x, Φ x) ( x, Ψ x).
Proof. rewrite /Frame=> ?. by rewrite sep_exist_l; apply exist_mono. Qed.
Global Instance frame_forall {A} R (Φ Ψ : A  uPred M) :
  ( a, Frame R (Φ a) (Ψ a))  Frame R ( x, Φ x) ( x, Ψ x).
Proof. rewrite /Frame=> ?. by rewrite sep_forall_l; apply forall_mono. Qed.

418
Global Instance frame_bupd R P Q : Frame R P Q  Frame R (|==> P) (|==> Q).
419
Proof. rewrite /Frame=><-. by rewrite bupd_frame_l. Qed.
420

421
422
423
(* FromOr *)
Global Instance from_or_or P1 P2 : FromOr (P1  P2) P1 P2.
Proof. done. Qed.
424
Global Instance from_or_bupd P Q1 Q2 :
425
  FromOr P Q1 Q2  FromOr (|==> P) (|==> Q1) (|==> Q2).
426
Proof. rewrite /FromOr=><-. apply or_elim; apply bupd_mono; auto with I. Qed.
427
428
Global Instance from_or_pure φ ψ : @FromOr M ⌜φ  ψ⌝ ⌜φ⌝ ⌜ψ⌝.
Proof. by rewrite /FromOr pure_or. Qed.
429
430
431
Global Instance from_or_always P Q1 Q2 :
  FromOr P Q1 Q2  FromOr ( P) ( Q1) ( Q2).
Proof. rewrite /FromOr=> <-. by rewrite always_or. Qed.
432
433
Global Instance from_or_later P Q1 Q2 :
  FromOr P Q1 Q2  FromOr ( P) ( Q1) ( Q2).
434
Proof. rewrite /FromOr=><-. by rewrite later_or. Qed.
435
436
437
Global Instance from_or_laterN n P Q1 Q2 :
  FromOr P Q1 Q2  FromOr (^n P) (^n Q1) (^n Q2).
Proof. rewrite /FromOr=><-. by rewrite laterN_or. Qed.
438
439
440
441

(* IntoOr *)
Global Instance into_or_or P Q : IntoOr (P  Q) P Q.
Proof. done. Qed.
442
443
444
445
446
Global Instance into_or_pure φ ψ : @IntoOr M ⌜φ  ψ⌝ ⌜φ⌝ ⌜ψ⌝.
Proof. by rewrite /IntoOr pure_or. Qed.
Global Instance into_or_always P Q1 Q2 :
  IntoOr P Q1 Q2  IntoOr ( P) ( Q1) ( Q2).
Proof. rewrite /IntoOr=>->. by rewrite always_or. Qed.
447
448
449
Global Instance into_or_later P Q1 Q2 :
  IntoOr P Q1 Q2  IntoOr ( P) ( Q1) ( Q2).
Proof. rewrite /IntoOr=>->. by rewrite later_or. Qed.
450
451
452
Global Instance into_or_laterN n P Q1 Q2 :
  IntoOr P Q1 Q2  IntoOr (^n P) (^n Q1) (^n Q2).
Proof. rewrite /IntoOr=>->. by rewrite laterN_or. Qed.
453
454

(* FromExist *)
455
Global Instance from_exist_exist {A} (Φ : A  uPred M): FromExist ( a, Φ a) Φ.
456
Proof. done. Qed.
457
Global Instance from_exist_bupd {A} P (Φ : A  uPred M) :
458
  FromExist P Φ  FromExist (|==> P) (λ a, |==> Φ a)%I.
459
460
461
Proof.
  rewrite /FromExist=><-. apply exist_elim=> a. by rewrite -(exist_intro a).
Qed.
462
463
464
465
466
467
468
469
Global Instance from_exist_pure {A} (φ : A  Prop) :
  @FromExist M A  x, φ x (λ a, ⌜φ a)%I.
Proof. by rewrite /FromExist pure_exist. Qed.
Global Instance from_exist_always {A} P (Φ : A  uPred M) :
  FromExist P Φ  FromExist ( P) (λ a,  (Φ a))%I.
Proof.
  rewrite /FromExist=> <-. apply exist_elim=>x. apply always_mono, exist_intro.
Qed.
470
471
Global Instance from_exist_later {A} P (Φ : A  uPred M) :
  FromExist P Φ  FromExist ( P) (λ a,  (Φ a))%I.
472
473
474
Proof.
  rewrite /FromExist=> <-. apply exist_elim=>x. apply later_mono, exist_intro.
Qed.
475
476
477
478
479
Global Instance from_exist_laterN {A} n P (Φ : A  uPred M) :
  FromExist P Φ  FromExist (^n P) (λ a, ^n (Φ a))%I.
Proof.
  rewrite /FromExist=> <-. apply exist_elim=>x. apply laterN_mono, exist_intro.
Qed.
480
481
482
483

(* IntoExist *)
Global Instance into_exist_exist {A} (Φ : A  uPred M) : IntoExist ( a, Φ a) Φ.
Proof. done. Qed.
484
485
486
Global Instance into_exist_pure {A} (φ : A  Prop) :
  @IntoExist M A  x, φ x (λ a, ⌜φ a)%I.
Proof. by rewrite /IntoExist pure_exist. Qed.
487
488
489
Global Instance into_exist_always {A} P (Φ : A  uPred M) :
  IntoExist P Φ  IntoExist ( P) (λ a,  (Φ a))%I.
Proof. rewrite /IntoExist=> HP. by rewrite HP always_exist. Qed.
490
491
492
493
494
495
Global Instance into_exist_later {A} P (Φ : A  uPred M) :
  IntoExist P Φ  Inhabited A  IntoExist ( P) (λ a,  (Φ a))%I.
Proof. rewrite /IntoExist=> HP ?. by rewrite HP later_exist. Qed.
Global Instance into_exist_laterN {A} n P (Φ : A  uPred M) :
  IntoExist P Φ  Inhabited A  IntoExist (^n P) (λ a, ^n (Φ a))%I.
Proof. rewrite /IntoExist=> HP ?. by rewrite HP laterN_exist. Qed.
496

497
498
499
500
501
502
503
504
505
(* IntoModal *)
Global Instance into_modal_later P : IntoModal P ( P).
Proof. apply later_intro. Qed.
Global Instance into_modal_bupd P : IntoModal P (|==> P).
Proof. apply bupd_intro. Qed.
Global Instance into_modal_except_0 P : IntoModal P ( P).
Proof. apply except_0_intro. Qed.

(* ElimModal *)
506
Global Instance elim_modal_wand P P' Q Q' R :
507
  ElimModal P P' Q Q'  ElimModal P P' (R - Q) (R - Q').
508
509
510
511
512
513
514
515
516
517
Proof.
  rewrite /ElimModal=> H. apply wand_intro_r.
  by rewrite wand_curry -assoc (comm _ P') -wand_curry wand_elim_l.
Qed.
Global Instance forall_modal_wand {A} P P' (Φ Ψ : A  uPred M) :
  ( x, ElimModal P P' (Φ x) (Ψ x))  ElimModal P P' ( x, Φ x) ( x, Ψ x).
Proof.
  rewrite /ElimModal=> H. apply forall_intro=> a. by rewrite (forall_elim a).
Qed.

Robbert Krebbers's avatar
Robbert Krebbers committed
518
519
520
Global Instance elim_modal_always P Q : ElimModal ( P) P Q Q.
Proof. intros. by rewrite /ElimModal always_elim wand_elim_r. Qed.

521
522
523
524
525
Global Instance elim_modal_bupd P Q : ElimModal (|==> P) P (|==> Q) (|==> Q).
Proof. by rewrite /ElimModal bupd_frame_r wand_elim_r bupd_trans. Qed.

Global Instance elim_modal_except_0 P Q : IsExcept0 Q  ElimModal ( P) P Q Q.
Proof.
526
  intros. rewrite /ElimModal (except_0_intro (_ - _)).
527
528
529
530
531
  by rewrite -except_0_sep wand_elim_r.
Qed.
Global Instance elim_modal_timeless_bupd P Q :
  TimelessP P  IsExcept0 Q  ElimModal ( P) P Q Q.
Proof.
532
  intros. rewrite /ElimModal (except_0_intro (_ - _)) (timelessP P).
533
534
  by rewrite -except_0_sep wand_elim_r.
Qed.
535
536
537
538
539
540
Global Instance elim_modal_timeless_bupd' p P Q :
  TimelessP P  IsExcept0 Q  ElimModal (?p P) P Q Q.
Proof.
  destruct p; simpl; auto using elim_modal_timeless_bupd.
  intros _ _. by rewrite /ElimModal wand_elim_r.
Qed.
541

542
543
544
545
546
Global Instance is_except_0_except_0 P : IsExcept0 ( P).
Proof. by rewrite /IsExcept0 except_0_idemp. Qed.
Global Instance is_except_0_later P : IsExcept0 ( P).
Proof. by rewrite /IsExcept0 except_0_later. Qed.
Global Instance is_except_0_bupd P : IsExcept0 P  IsExcept0 (|==> P).
547
Proof.
548
549
  rewrite /IsExcept0=> HP.
  by rewrite -{2}HP -(except_0_idemp P) -except_0_bupd -(except_0_intro P).
550
Qed.
551
End classes.