auth.v 9.92 KB
Newer Older
1
2
From iris.algebra Require Export excl.
From iris.algebra Require Import upred.
3
Local Arguments valid _ _ !_ /.
Robbert Krebbers's avatar
Robbert Krebbers committed
4
Local Arguments validN _ _ _ !_ /.
Robbert Krebbers's avatar
Robbert Krebbers committed
5

Robbert Krebbers's avatar
Robbert Krebbers committed
6
Record auth (A : Type) : Type := Auth { authoritative : excl A ; own : A }.
7
Add Printing Constructor auth.
Robbert Krebbers's avatar
Robbert Krebbers committed
8
Arguments Auth {_} _ _.
Robbert Krebbers's avatar
Robbert Krebbers committed
9
Arguments authoritative {_} _.
Robbert Krebbers's avatar
Robbert Krebbers committed
10
Arguments own {_} _.
11
12
Notation "◯ a" := (Auth ExclUnit a) (at level 20).
Notation "● a" := (Auth (Excl a) ) (at level 20).
Robbert Krebbers's avatar
Robbert Krebbers committed
13

Robbert Krebbers's avatar
Robbert Krebbers committed
14
(* COFE *)
15
16
Section cofe.
Context {A : cofeT}.
17
18
Implicit Types a : excl A.
Implicit Types b : A.
19
Implicit Types x y : auth A.
20
21

Instance auth_equiv : Equiv (auth A) := λ x y,
Robbert Krebbers's avatar
Robbert Krebbers committed
22
  authoritative x  authoritative y  own x  own y.
23
Instance auth_dist : Dist (auth A) := λ n x y,
24
  authoritative x {n} authoritative y  own x {n} own y.
Robbert Krebbers's avatar
Robbert Krebbers committed
25

26
Global Instance Auth_ne : Proper (dist n ==> dist n ==> dist n) (@Auth A).
Robbert Krebbers's avatar
Robbert Krebbers committed
27
Proof. by split. Qed.
28
29
Global Instance Auth_proper : Proper (() ==> () ==> ()) (@Auth A).
Proof. by split. Qed.
30
Global Instance authoritative_ne: Proper (dist n ==> dist n) (@authoritative A).
Robbert Krebbers's avatar
Robbert Krebbers committed
31
Proof. by destruct 1. Qed.
32
33
Global Instance authoritative_proper : Proper (() ==> ()) (@authoritative A).
Proof. by destruct 1. Qed.
34
Global Instance own_ne : Proper (dist n ==> dist n) (@own A).
Robbert Krebbers's avatar
Robbert Krebbers committed
35
Proof. by destruct 1. Qed.
36
37
Global Instance own_proper : Proper (() ==> ()) (@own A).
Proof. by destruct 1. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
38

39
Instance auth_compl : Compl (auth A) := λ c,
Robbert Krebbers's avatar
Robbert Krebbers committed
40
  Auth (compl (chain_map authoritative c)) (compl (chain_map own c)).
41
Definition auth_cofe_mixin : CofeMixin (auth A).
Robbert Krebbers's avatar
Robbert Krebbers committed
42
43
Proof.
  split.
44
  - intros x y; unfold dist, auth_dist, equiv, auth_equiv.
Robbert Krebbers's avatar
Robbert Krebbers committed
45
    rewrite !equiv_dist; naive_solver.
46
  - intros n; split.
Robbert Krebbers's avatar
Robbert Krebbers committed
47
48
    + by intros ?; split.
    + by intros ?? [??]; split; symmetry.
49
    + intros ??? [??] [??]; split; etrans; eauto.
50
  - by intros ? [??] [??] [??]; split; apply dist_S.
Robbert Krebbers's avatar
Robbert Krebbers committed
51
52
  - intros n c; split. apply (conv_compl n (chain_map authoritative c)).
    apply (conv_compl n (chain_map own c)).
Robbert Krebbers's avatar
Robbert Krebbers committed
53
Qed.
54
Canonical Structure authC := CofeT auth_cofe_mixin.
55
56
57
58
59
60

Global Instance Auth_timeless a b :
  Timeless a  Timeless b  Timeless (Auth a b).
Proof. by intros ?? [??] [??]; split; apply: timeless. Qed.
Global Instance auth_discrete : Discrete A  Discrete authC.
Proof. intros ? [??]; apply _. Qed.
61
Global Instance auth_leibniz : LeibnizEquiv A  LeibnizEquiv (auth A).
62
Proof. by intros ? [??] [??] [??]; f_equal/=; apply leibniz_equiv. Qed.
63
64
65
End cofe.

Arguments authC : clear implicits.
Robbert Krebbers's avatar
Robbert Krebbers committed
66
67

(* CMRA *)
68
69
Section cmra.
Context {A : cmraT}.
70
71
Implicit Types a b : A.
Implicit Types x y : auth A.
72
73

Global Instance auth_empty `{Empty A} : Empty (auth A) := Auth  .
74
75
Instance auth_valid : Valid (auth A) := λ x,
  match authoritative x with
Robbert Krebbers's avatar
Robbert Krebbers committed
76
  | Excl a => ( n, own x {n} a)   a
77
78
79
80
  | ExclUnit =>  own x
  | ExclBot => False
  end.
Global Arguments auth_valid !_ /.
81
Instance auth_validN : ValidN (auth A) := λ n x,
Robbert Krebbers's avatar
Robbert Krebbers committed
82
  match authoritative x with
Robbert Krebbers's avatar
Robbert Krebbers committed
83
  | Excl a => own x {n} a  {n} a
84
  | ExclUnit => {n} own x
85
  | ExclBot => False
Robbert Krebbers's avatar
Robbert Krebbers committed
86
  end.
87
Global Arguments auth_validN _ !_ /.
Ralf Jung's avatar
Ralf Jung committed
88
89
Instance auth_core : Core (auth A) := λ x,
  Auth (core (authoritative x)) (core (own x)).
90
Instance auth_op : Op (auth A) := λ x y,
Robbert Krebbers's avatar
Robbert Krebbers committed
91
  Auth (authoritative x  authoritative y) (own x  own y).
92

93
Lemma auth_included (x y : auth A) :
Robbert Krebbers's avatar
Robbert Krebbers committed
94
95
96
97
98
  x  y  authoritative x  authoritative y  own x  own y.
Proof.
  split; [intros [[z1 z2] Hz]; split; [exists z1|exists z2]; apply Hz|].
  intros [[z1 Hz1] [z2 Hz2]]; exists (Auth z1 z2); split; auto.
Qed.
99
Lemma authoritative_validN n (x : auth A) : {n} x  {n} authoritative x.
Robbert Krebbers's avatar
Robbert Krebbers committed
100
Proof. by destruct x as [[]]. Qed.
101
Lemma own_validN n (x : auth A) : {n} x  {n} own x.
102
Proof. destruct x as [[]]; naive_solver eauto using cmra_validN_includedN. Qed.
103
104

Definition auth_cmra_mixin : CMRAMixin (auth A).
Robbert Krebbers's avatar
Robbert Krebbers committed
105
106
Proof.
  split.
107
108
109
  - by intros n x y1 y2 [Hy Hy']; split; simpl; rewrite ?Hy ?Hy'.
  - by intros n y1 y2 [Hy Hy']; split; simpl; rewrite ?Hy ?Hy'.
  - intros n [x a] [y b] [Hx Ha]; simpl in *;
110
      destruct Hx; intros ?; cofe_subst; auto.
111
112
  - intros [[] ?]; rewrite /= ?cmra_included_includedN ?cmra_valid_validN;
      naive_solver eauto using O.
113
114
115
  - intros n [[] ?] ?; naive_solver eauto using cmra_includedN_S, cmra_validN_S.
  - by split; simpl; rewrite assoc.
  - by split; simpl; rewrite comm.
Ralf Jung's avatar
Ralf Jung committed
116
117
  - by split; simpl; rewrite ?cmra_core_l.
  - by split; simpl; rewrite ?cmra_core_idemp.
Robbert Krebbers's avatar
Robbert Krebbers committed
118
  - intros ??; rewrite! auth_included; intros [??].
Ralf Jung's avatar
Ralf Jung committed
119
    by split; simpl; apply cmra_core_preserving.
120
  - assert ( n (a b1 b2 : A), b1  b2 {n} a  b1 {n} a).
121
    { intros n a b1 b2 <-; apply cmra_includedN_l. }
Robbert Krebbers's avatar
Robbert Krebbers committed
122
   intros n [[a1| |] b1] [[a2| |] b2];
123
     naive_solver eauto using cmra_validN_op_l, cmra_validN_includedN.
124
125
126
127
128
129
  - intros n x y1 y2 ? [??]; simpl in *.
    destruct (cmra_extend n (authoritative x) (authoritative y1)
      (authoritative y2)) as (ea&?&?&?); auto using authoritative_validN.
    destruct (cmra_extend n (own x) (own y1) (own y2))
      as (b&?&?&?); auto using own_validN.
    by exists (Auth (ea.1) (b.1), Auth (ea.2) (b.2)).
Robbert Krebbers's avatar
Robbert Krebbers committed
130
Qed.
131
132
Canonical Structure authR : cmraT := CMRAT auth_cofe_mixin auth_cmra_mixin.
Global Instance auth_cmra_discrete : CMRADiscrete A  CMRADiscrete authR.
133
134
Proof.
  split; first apply _.
Robbert Krebbers's avatar
Robbert Krebbers committed
135
136
137
  intros [[] ?]; rewrite /= /cmra_valid /cmra_validN /=
    -?cmra_discrete_included_iff -?cmra_discrete_valid_iff; auto.
Admitted.
138

139
140
141
(** Internalized properties *)
Lemma auth_equivI {M} (x y : auth A) :
  (x  y)%I  (authoritative x  authoritative y  own x  own y : uPred M)%I.
142
Proof. by uPred.unseal. Qed.
143
144
145
146
147
148
Lemma auth_validI {M} (x : auth A) :
  ( x)%I  (match authoritative x with
             | Excl a => ( b, a  own x  b)   a
             | ExclUnit =>  own x
             | ExclBot => False
             end : uPred M)%I.
149
Proof. uPred.unseal. by destruct x as [[]]. Qed.
150

151
152
(** The notations ◯ and ● only work for CMRAs with an empty element. So, in
what follows, we assume we have an empty element. *)
Ralf Jung's avatar
Ralf Jung committed
153
Context `{Empty A, !CMRAUnit A}.
154

Ralf Jung's avatar
Ralf Jung committed
155
Global Instance auth_cmra_unit : CMRAUnit authR.
Robbert Krebbers's avatar
Robbert Krebbers committed
156
Proof.
157
  split; simpl.
Ralf Jung's avatar
Ralf Jung committed
158
  - by apply (@cmra_unit_valid A _).
159
160
  - by intros x; constructor; rewrite /= left_id.
  - apply _.
Robbert Krebbers's avatar
Robbert Krebbers committed
161
Qed.
162
Lemma auth_frag_op a b :  (a  b)   a   b.
Robbert Krebbers's avatar
Robbert Krebbers committed
163
Proof. done. Qed.
164
165
Lemma auth_both_op a b : Auth (Excl a) b   a   b.
Proof. by rewrite /op /auth_op /= left_id. Qed.
166
167

Lemma auth_update a a' b b' :
Ralf Jung's avatar
Ralf Jung committed
168
  ( n af, {n} a  a {n} a'  af  b {n} b'  af  {n} b) 
169
   a   a' ~~>  b   b'.
170
Proof.
Robbert Krebbers's avatar
Robbert Krebbers committed
171
  move=> Hab n [[?| |] bf1] // =>-[[bf2 Ha] ?]; do 2 red; simpl in *.
172
  destruct (Hab n (bf1  bf2)) as [Ha' ?]; auto.
173
174
  { by rewrite Ha left_id assoc. }
  split; [by rewrite Ha' left_id assoc; apply cmra_includedN_l|done].
175
Qed.
176

177
Lemma auth_local_update L `{!LocalUpdate Lv L} a a' :
178
  Lv a   L a' 
179
   a'   a ~~>  L a'   L a.
180
Proof.
181
  intros. apply auth_update=>n af ? EQ; split; last by apply cmra_valid_validN.
182
  by rewrite EQ (local_updateN L) // -EQ.
183
Qed.
184
185
186
187

Lemma auth_update_op_l a a' b :
   (b  a)   a   a' ~~>  (b  a)   (b  a').
Proof. by intros; apply (auth_local_update _). Qed.
188
Lemma auth_update_op_r a a' b :
189
   (a  b)   a   a' ~~>  (a  b)   (a'  b).
190
Proof. rewrite -!(comm _ b); apply auth_update_op_l. Qed.
191

Ralf Jung's avatar
Ralf Jung committed
192
(* This does not seem to follow from auth_local_update.
193
   The trouble is that given ✓ (L a ⋅ a'), Lv a
Ralf Jung's avatar
Ralf Jung committed
194
195
   we need ✓ (a ⋅ a'). I think this should hold for every local update,
   but adding an extra axiom to local updates just for this is silly. *)
196
197
198
Lemma auth_local_update_l L `{!LocalUpdate Lv L} a a' :
  Lv a   (L a  a') 
   (a  a')   a ~~>  (L a  a')   L a.
Ralf Jung's avatar
Ralf Jung committed
199
Proof.
200
  intros. apply auth_update=>n af ? EQ; split; last by apply cmra_valid_validN.
201
  by rewrite -(local_updateN L) // EQ -(local_updateN L) // -EQ.
Ralf Jung's avatar
Ralf Jung committed
202
Qed.
203
204
End cmra.

205
Arguments authR : clear implicits.
Robbert Krebbers's avatar
Robbert Krebbers committed
206
207

(* Functor *)
208
209
210
211
212
213
214
215
216
217
218
219
Definition auth_map {A B} (f : A  B) (x : auth A) : auth B :=
  Auth (excl_map f (authoritative x)) (f (own x)).
Lemma auth_map_id {A} (x : auth A) : auth_map id x = x.
Proof. by destruct x; rewrite /auth_map excl_map_id. Qed.
Lemma auth_map_compose {A B C} (f : A  B) (g : B  C) (x : auth A) :
  auth_map (g  f) x = auth_map g (auth_map f x).
Proof. by destruct x; rewrite /auth_map excl_map_compose. Qed.
Lemma auth_map_ext {A B : cofeT} (f g : A  B) x :
  ( x, f x  g x)  auth_map f x  auth_map g x.
Proof. constructor; simpl; auto using excl_map_ext. Qed.
Instance auth_map_cmra_ne {A B : cofeT} n :
  Proper ((dist n ==> dist n) ==> dist n ==> dist n) (@auth_map A B).
Robbert Krebbers's avatar
Robbert Krebbers committed
220
Proof.
221
  intros f g Hf [??] [??] [??]; split; [by apply excl_map_cmra_ne|by apply Hf].
Robbert Krebbers's avatar
Robbert Krebbers committed
222
Qed.
223
224
Instance auth_map_cmra_monotone {A B : cmraT} (f : A  B) :
  CMRAMonotone f  CMRAMonotone (auth_map f).
Robbert Krebbers's avatar
Robbert Krebbers committed
225
Proof.
Robbert Krebbers's avatar
Robbert Krebbers committed
226
227
228
229
230
  split; try apply _.
  - intros n [[a| |] b]; rewrite /= /cmra_validN /=; try
      naive_solver eauto using includedN_preserving, validN_preserving.
  - by intros [x a] [y b]; rewrite !auth_included /=;
      intros [??]; split; simpl; apply: included_preserving.
Robbert Krebbers's avatar
Robbert Krebbers committed
231
Qed.
232
Definition authC_map {A B} (f : A -n> B) : authC A -n> authC B :=
233
  CofeMor (auth_map f).
234
Lemma authC_map_ne A B n : Proper (dist n ==> dist n) (@authC_map A B).
Robbert Krebbers's avatar
Robbert Krebbers committed
235
Proof. intros f f' Hf [[a| |] b]; repeat constructor; apply Hf. Qed.
Ralf Jung's avatar
Ralf Jung committed
236

237
238
239
Program Definition authRF (F : rFunctor) : rFunctor := {|
  rFunctor_car A B := authR (rFunctor_car F A B);
  rFunctor_map A1 A2 B1 B2 fg := authC_map (rFunctor_map F fg)
Ralf Jung's avatar
Ralf Jung committed
240
|}.
241
242
243
Next Obligation.
  by intros F A1 A2 B1 B2 n f g Hfg; apply authC_map_ne, rFunctor_ne.
Qed.
Ralf Jung's avatar
Ralf Jung committed
244
Next Obligation.
245
246
  intros F A B x. rewrite /= -{2}(auth_map_id x).
  apply auth_map_ext=>y; apply rFunctor_id.
Ralf Jung's avatar
Ralf Jung committed
247
248
Qed.
Next Obligation.
249
250
  intros F A1 A2 A3 B1 B2 B3 f g f' g' x. rewrite /= -auth_map_compose.
  apply auth_map_ext=>y; apply rFunctor_compose.
Ralf Jung's avatar
Ralf Jung committed
251
Qed.
252
253
254
255
256
257

Instance authRF_contractive F :
  rFunctorContractive F  rFunctorContractive (authRF F).
Proof.
  by intros ? A1 A2 B1 B2 n f g Hfg; apply authC_map_ne, rFunctor_contractive.
Qed.