auth.v 8.61 KB
Newer Older
1
Require Export algebra.excl.
Ralf Jung's avatar
Ralf Jung committed
2
Require Import algebra.functor.
Robbert Krebbers's avatar
Robbert Krebbers committed
3
Local Arguments validN _ _ _ !_ /.
Robbert Krebbers's avatar
Robbert Krebbers committed
4

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

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

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

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

37
Instance auth_compl : Compl (auth A) := λ c,
Robbert Krebbers's avatar
Robbert Krebbers committed
38
  Auth (compl (chain_map authoritative c)) (compl (chain_map own c)).
39
Definition auth_cofe_mixin : CofeMixin (auth A).
Robbert Krebbers's avatar
Robbert Krebbers committed
40 41 42 43 44 45 46 47
Proof.
  split.
  * intros x y; unfold dist, auth_dist, equiv, auth_equiv.
    rewrite !equiv_dist; naive_solver.
  * intros n; split.
    + by intros ?; split.
    + by intros ?? [??]; split; symmetry.
    + intros ??? [??] [??]; split; etransitivity; eauto.
48
  * by intros ? [??] [??] [??]; split; apply dist_S.
Robbert Krebbers's avatar
Robbert Krebbers committed
49 50 51 52
  * by split.
  * intros c n; split. apply (conv_compl (chain_map authoritative c) n).
    apply (conv_compl (chain_map own c) n).
Qed.
53
Canonical Structure authC := CofeT auth_cofe_mixin.
54 55
Instance Auth_timeless (ea : excl A) (b : A) :
  Timeless ea  Timeless b  Timeless (Auth ea b).
56
Proof. by intros ?? [??] [??]; split; simpl in *; apply (timeless _). Qed.
57 58
Global Instance auth_leibniz : LeibnizEquiv A  LeibnizEquiv (auth A).
Proof. by intros ? [??] [??] [??]; f_equal'; apply leibniz_equiv. Qed.
59 60 61
End cofe.

Arguments authC : clear implicits.
Robbert Krebbers's avatar
Robbert Krebbers committed
62 63

(* CMRA *)
64 65
Section cmra.
Context {A : cmraT}.
66 67
Implicit Types a b : A.
Implicit Types x y : auth A.
68 69 70

Global Instance auth_empty `{Empty A} : Empty (auth A) := Auth  .
Instance auth_validN : ValidN (auth A) := λ n x,
Robbert Krebbers's avatar
Robbert Krebbers committed
71
  match authoritative x with
Robbert Krebbers's avatar
Robbert Krebbers committed
72 73
  | Excl a => own x {n} a  {n} a
  | ExclUnit => {n} (own x)
Robbert Krebbers's avatar
Robbert Krebbers committed
74 75
  | ExclBot => n = 0
  end.
76 77
Global Arguments auth_validN _ !_ /.
Instance auth_unit : Unit (auth A) := λ x,
Robbert Krebbers's avatar
Robbert Krebbers committed
78
  Auth (unit (authoritative x)) (unit (own x)).
79
Instance auth_op : Op (auth A) := λ x y,
Robbert Krebbers's avatar
Robbert Krebbers committed
80
  Auth (authoritative x  authoritative y) (own x  own y).
81
Instance auth_minus : Minus (auth A) := λ x y,
Robbert Krebbers's avatar
Robbert Krebbers committed
82
  Auth (authoritative x  authoritative y) (own x  own y).
83
Lemma auth_included (x y : auth A) :
Robbert Krebbers's avatar
Robbert Krebbers committed
84 85 86 87 88
  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.
89
Lemma auth_includedN n (x y : auth A) :
Robbert Krebbers's avatar
Robbert Krebbers committed
90 91 92 93 94
  x {n} y  authoritative x {n} authoritative y  own x {n} 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.
95
Lemma authoritative_validN n (x : auth A) : {n} x  {n} (authoritative x).
Robbert Krebbers's avatar
Robbert Krebbers committed
96
Proof. by destruct x as [[]]. Qed.
97
Lemma own_validN n (x : auth A) : {n} x  {n} (own x).
98
Proof. destruct x as [[]]; naive_solver eauto using cmra_validN_includedN. Qed.
99 100

Definition auth_cmra_mixin : CMRAMixin (auth A).
Robbert Krebbers's avatar
Robbert Krebbers committed
101 102
Proof.
  split.
Robbert Krebbers's avatar
Robbert Krebbers committed
103 104
  * 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'.
Robbert Krebbers's avatar
Robbert Krebbers committed
105 106 107
  * intros n [x a] [y b] [Hx Ha]; simpl in *;
      destruct Hx as [[][]| | |]; intros ?; cofe_subst; auto.
  * by intros n x1 x2 [Hx Hx'] y1 y2 [Hy Hy'];
Robbert Krebbers's avatar
Robbert Krebbers committed
108
      split; simpl; rewrite ?Hy ?Hy' ?Hx ?Hx'.
Robbert Krebbers's avatar
Robbert Krebbers committed
109
  * by intros [[] ?]; simpl.
110 111 112 113 114
  * intros n [[] ?] ?; naive_solver eauto using cmra_includedN_S, cmra_validN_S.
  * by split; simpl; rewrite associative.
  * by split; simpl; rewrite commutative.
  * by split; simpl; rewrite ?cmra_unit_l.
  * by split; simpl; rewrite ?cmra_unit_idempotent.
Robbert Krebbers's avatar
Robbert Krebbers committed
115
  * intros n ??; rewrite! auth_includedN; intros [??].
116
    by split; simpl; apply cmra_unit_preservingN.
117
  * assert ( n (a b1 b2 : A), b1  b2 {n} a  b1 {n} a).
118
    { intros n a b1 b2 <-; apply cmra_includedN_l. }
Robbert Krebbers's avatar
Robbert Krebbers committed
119
   intros n [[a1| |] b1] [[a2| |] b2];
120
     naive_solver eauto using cmra_validN_op_l, cmra_validN_includedN.
Robbert Krebbers's avatar
Robbert Krebbers committed
121 122 123
  * by intros n ??; rewrite auth_includedN;
      intros [??]; split; simpl; apply cmra_op_minus.
Qed.
124
Definition auth_cmra_extend_mixin : CMRAExtendMixin (auth A).
Robbert Krebbers's avatar
Robbert Krebbers committed
125 126 127
Proof.
  intros n x y1 y2 ? [??]; simpl in *.
  destruct (cmra_extend_op n (authoritative x) (authoritative y1)
128
    (authoritative y2)) as (ea&?&?&?); auto using authoritative_validN.
Robbert Krebbers's avatar
Robbert Krebbers committed
129
  destruct (cmra_extend_op n (own x) (own y1) (own y2))
130 131
    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
132
Qed.
133 134
Canonical Structure authRA : cmraT :=
  CMRAT auth_cofe_mixin auth_cmra_mixin auth_cmra_extend_mixin.
135 136 137 138 139 140

(** The notations ◯ and ● only work for CMRAs with an empty element. So, in
what follows, we assume we have an empty element. *)
Context `{Empty A, !CMRAIdentity A}.

Global Instance auth_cmra_identity : CMRAIdentity authRA.
Robbert Krebbers's avatar
Robbert Krebbers committed
141
Proof.
142 143 144 145
  split; simpl.
  * by apply (@cmra_empty_valid A _).
  * by intros x; constructor; rewrite /= left_id.
  * apply Auth_timeless; apply _.
Robbert Krebbers's avatar
Robbert Krebbers committed
146
Qed.
147
Lemma auth_frag_op a b :  (a  b)   a   b.
Robbert Krebbers's avatar
Robbert Krebbers committed
148
Proof. done. Qed.
149 150
Lemma auth_both_op a b : Auth (Excl a) b   a   b.
Proof. by rewrite /op /auth_op /= left_id. Qed.
151 152

Lemma auth_update a a' b b' :
153
  ( n af, {S n} a  a {S n} a'  af  b {S n} b'  af  {S n} b) 
154
   a   a' ~~>  b   b'.
155
Proof.
156 157
  move=> Hab [[?| |] bf1] n // =>-[[bf2 Ha] ?]; do 2 red; simpl in *.
  destruct (Hab n (bf1  bf2)) as [Ha' ?]; auto.
158 159 160 161
  { by rewrite Ha left_id associative. }
  split; [by rewrite Ha' left_id associative; apply cmra_includedN_l|done].
Qed.
Lemma auth_update_op_l a a' b :
162
   (b  a)   a   a' ~~>  (b  a)   (b  a').
163 164 165 166 167
Proof.
  intros; apply auth_update.
  by intros n af ? Ha; split; [by rewrite Ha associative|].
Qed.
Lemma auth_update_op_r a a' b :
168
   (a  b)   a   a' ~~>  (a  b)   (a'  b).
169
Proof. rewrite -!(commutative _ b); apply auth_update_op_l. Qed.
170 171 172
End cmra.

Arguments authRA : clear implicits.
Robbert Krebbers's avatar
Robbert Krebbers committed
173 174

(* Functor *)
175 176 177 178 179 180 181 182 183 184 185 186
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
187
Proof.
188
  intros f g Hf [??] [??] [??]; split; [by apply excl_map_cmra_ne|by apply Hf].
Robbert Krebbers's avatar
Robbert Krebbers committed
189
Qed.
190 191 192
Instance auth_map_cmra_monotone {A B : cmraT} (f : A  B) :
  ( n, Proper (dist n ==> dist n) f) 
  CMRAMonotone f  CMRAMonotone (auth_map f).
Robbert Krebbers's avatar
Robbert Krebbers committed
193 194
Proof.
  split.
195 196 197
  * by intros n [x a] [y b]; rewrite !auth_includedN /=;
      intros [??]; split; simpl; apply: includedN_preserving.
  * intros n [[a| |] b]; rewrite /= /cmra_validN;
Robbert Krebbers's avatar
Robbert Krebbers committed
198 199
      naive_solver eauto using @includedN_preserving, @validN_preserving.
Qed.
200
Definition authC_map {A B} (f : A -n> B) : authC A -n> authC B :=
201
  CofeMor (auth_map f).
202
Lemma authC_map_ne A B n : Proper (dist n ==> dist n) (@authC_map A B).
Robbert Krebbers's avatar
Robbert Krebbers committed
203
Proof. intros f f' Hf [[a| |] b]; repeat constructor; apply Hf. Qed.
Ralf Jung's avatar
Ralf Jung committed
204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219

Program Definition authF (Σ : iFunctor) : iFunctor := {|
  ifunctor_car := authRA  Σ; ifunctor_map A B := authC_map  ifunctor_map Σ
|}.
Next Obligation.
  by intros Σ A B n f g Hfg; apply authC_map_ne, ifunctor_map_ne.
Qed.
Next Obligation.
  intros Σ A x. rewrite /= -{2}(auth_map_id x).
  apply auth_map_ext=>y; apply ifunctor_map_id.
Qed.
Next Obligation.
  intros Σ A B C f g x. rewrite /= -auth_map_compose.
  apply auth_map_ext=>y; apply ifunctor_map_compose.
Qed.