Library zoo_parabs.ws_deques_public
Require Import zoo.prelude.
Require Import zoo.iris.bi.big_op.
Require Import zoo.base.
Require Import zoo_std.option.
Require Export zoo_parabs.base.
Require Export zoo_parabs.ws_deques_public__code.
Require Import zoo_parabs.ws_deques_public__types.
Require Import zoo.options.
Implicit Type v t queue round : val.
Implicit Type vs ws queues : list val.
Implicit Type vss : list (list val).
Implicit Type status : status.
Class WsDequesPublicG Σ `{zoo۰G : !ZooG Σ} :=
{ #[local] ws_deques_public۰G۰ws_deque۰G :: WsDeque2G Σ
}.
Definition ws_deques_public۰Σ :=
#[ws_deque_2۰Σ
].
#[global] Instance subGｰws_deques_public۰Σ Σ `{zoo۰G : !ZooG Σ} :
subG ws_deques_public۰Σ Σ →
WsDequesPublicG Σ.
Section ws_deques_public۰G.
Context `{ws_deques_public۰G : WsDequesPublicG Σ}.
Definition ws_deques_public۰inv t ι sz : iProp Σ :=
∃ queues,
⌜sz = length queues⌝ ∗
array۰model t DfracDiscarded queues ∗
[∗ list] queue ∈ queues,
ws_deque_2۰inv queue ι.
#[local] Instance : CustomIpat "inv" :=
" ( %queues{} & %Hqueues{}_length & #Hqueues{} & #Hqueues{}_inv ) ".
Definition ws_deques_public۰model t vss : iProp Σ :=
∃ queues,
array۰model t DfracDiscarded queues ∗
[∗ list] i ↦ queue; vs ∈ queues; vss,
ws_deque_2۰model queue vs.
#[local] Instance : CustomIpat "model" :=
" ( %queues{;_} & Hqueues{;_} & Hqueues{}_model ) ".
Definition ws_deques_public۰owner t i status ws : iProp Σ :=
∃ queues queue,
⌜queues !! i = Some queue⌝ ∗
array۰model t DfracDiscarded queues ∗
ws_deque_2۰owner queue ws.
#[local] Instance : CustomIpat "owner" :=
" ( %queues{;_} & %queue{} & %Hqueues{}_lookup & Hqueues{;_} & Hqueue{}_owner ) ".
#[global] Instance ws_deques_public۰modelｰtimeless t vss :
Timeless (ws_deques_public۰model t vss).
#[global] Instance ws_deques_public۰invｰpersistent t ι sz :
Persistent (ws_deques_public۰inv t ι sz).
Lemma ws_deques_public۰invｰagree t ι1 sz1 ι2 sz2 :
ws_deques_public۰inv t ι1 sz1 -∗
ws_deques_public۰inv t ι2 sz2 -∗
⌜sz1 = sz2⌝.
Lemma ws_deques_public۰ownerｰexclusive t i status1 ws1 status2 ws2 :
ws_deques_public۰owner t i status1 ws1 -∗
ws_deques_public۰owner t i status2 ws2 -∗
False.
Lemma ws_deques_publicｰinvｰmodel t ι sz vss :
ws_deques_public۰inv t ι sz -∗
ws_deques_public۰model t vss -∗
⌜length vss = sz⌝.
Lemma ws_deques_publicｰinvｰowner t ι sz i status ws :
ws_deques_public۰inv t ι sz -∗
ws_deques_public۰owner t i status ws -∗
⌜i < sz⌝.
Lemma ws_deques_publicｰmodelｰowner t vss i status ws :
ws_deques_public۰model t vss -∗
ws_deques_public۰owner t i status ws -∗
∃ vs,
⌜vss !! i = Some vs⌝ ∗
⌜vs `suffix_of` ws⌝.
Lemma ws_deques_public٠createｰspec ι sz :
(0 ≤ sz)%Z →
{{{
True
}}}
ws_deques_public٠create #sz
{{{
t
, RET t;
ws_deques_public۰inv t ι ₊sz ∗
ws_deques_public۰model t (replicate ₊sz []) ∗
[∗ list] i ∈ seq 0 ₊sz,
ws_deques_public۰owner t i Nonblocked []
}}}.
Lemma ws_deques_public٠sizeｰspec t ι sz :
{{{
ws_deques_public۰inv t ι sz
}}}
ws_deques_public٠size t
{{{
RET #sz;
True
}}}.
Lemma ws_deques_public٠blockｰspec t ι sz i i_ ws :
i = ⁺i_ →
{{{
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Nonblocked ws
}}}
ws_deques_public٠block t #i
{{{
RET ();
ws_deques_public۰owner t i_ Blocked ws
}}}.
Lemma ws_deques_public٠unblockｰspec t ι sz i i_ ws :
i = ⁺i_ →
{{{
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Blocked ws
}}}
ws_deques_public٠unblock t #i
{{{
RET ();
ws_deques_public۰owner t i_ Nonblocked ws
}}}.
Lemma ws_deques_public٠pushｰspec t ι sz i i_ ws v :
i = ⁺i_ →
<<<
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Nonblocked ws
| ∀∀ vss,
ws_deques_public۰model t vss
>>>
ws_deques_public٠push t #i v @ ↑ι
<<<
∃∃ vs,
⌜vss !! i_ = Some vs⌝ ∗
⌜vs `suffix_of` ws⌝ ∗
ws_deques_public۰model t (<[i_ := vs ++ [v]]> vss)
| RET ();
ws_deques_public۰owner t i_ Nonblocked (vs ++ [v])
>>>.
Lemma ws_deques_public٠popｰspec t ι sz i i_ ws :
i = ⁺i_ →
<<<
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Nonblocked ws
| ∀∀ vss,
ws_deques_public۰model t vss
>>>
ws_deques_public٠pop t #i @ ↑ι
<<<
∃∃ o ws',
match o with
| None ⇒
⌜vss !! i_ = Some []⌝ ∗
⌜ws' = []⌝ ∗
ws_deques_public۰model t vss
| Some v ⇒
∃ vs,
⌜vss !! i_ = Some (vs ++ [v])⌝ ∗
⌜vs ++ [v] `suffix_of` ws⌝ ∗
⌜ws' = vs⌝ ∗
ws_deques_public۰model t (<[i_ := vs]> vss)
end
| RET o;
ws_deques_public۰owner t i_ Nonblocked ws'
>>>.
Lemma ws_deques_public٠steal_toｰspec t ι (sz : nat) i i_ ws j :
i = ⁺i_ →
(0 ≤ j < sz)%Z →
<<<
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Blocked ws
| ∀∀ vss,
ws_deques_public۰model t vss
>>>
ws_deques_public٠steal_to t #i #j @ ↑ι
<<<
∃∃ o,
match o with
| None ⇒
ws_deques_public۰model t vss
| Some v ⇒
∃ vs,
⌜vss !! ₊j = Some (v :: vs)⌝ ∗
ws_deques_public۰model t (<[₊j := vs]> vss)
end
| RET o;
ws_deques_public۰owner t i_ Blocked ws
>>>.
End ws_deques_public۰G.
#[global] Opaque ws_deques_public۰inv.
#[global] Opaque ws_deques_public۰model.
#[global] Opaque ws_deques_public۰owner.
Section ws_deques_public۰G.
Context `{ws_deques_public۰G : WsDequesPublicG Σ}.
#[local] Lemma ws_deques_public٠steal_as₁ｰspec t ι (sz : nat) i i_ ws round (n : nat) :
i = ⁺i_ →
<<<
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Blocked ws ∗
random_round۰model' round (sz - 1) n
| ∀∀ vss,
ws_deques_public۰model t vss
>>>
ws_deques_public٠steal_as₁ t #sz #i round #n @ ↑ι
<<<
∃∃ o,
match o with
| None ⇒
ws_deques_public۰model t vss
| Some v ⇒
∃ j vs,
⌜₊i ≠ j⌝ ∗
⌜vss !! j = Some (v :: vs)⌝ ∗
ws_deques_public۰model t (<[j := vs]> vss)
end
| RET o;
∃ n,
ws_deques_public۰owner t i_ Blocked ws ∗
random_round۰model' round (sz - 1) n
>>>.
Lemma ws_deques_public٠steal_asｰspec t ι sz i i_ ws round :
i = ⁺i_ →
0 < sz →
<<<
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Blocked ws ∗
random_round۰model' round (sz - 1) (sz - 1)
| ∀∀ vss,
ws_deques_public۰model t vss
>>>
ws_deques_public٠steal_as t #i round @ ↑ι
<<<
∃∃ o,
match o with
| None ⇒
ws_deques_public۰model t vss
| Some v ⇒
∃ j vs,
⌜₊i ≠ j⌝ ∗
⌜vss !! j = Some (v :: vs)⌝ ∗
ws_deques_public۰model t (<[j := vs]> vss)
end
| RET o;
∃ n,
ws_deques_public۰owner t i_ Blocked ws ∗
random_round۰model' round (sz - 1) n
>>>.
End ws_deques_public۰G.
Require zoo_parabs.ws_deques_public__opaque.
Require Import zoo.iris.bi.big_op.
Require Import zoo.base.
Require Import zoo_std.option.
Require Export zoo_parabs.base.
Require Export zoo_parabs.ws_deques_public__code.
Require Import zoo_parabs.ws_deques_public__types.
Require Import zoo.options.
Implicit Type v t queue round : val.
Implicit Type vs ws queues : list val.
Implicit Type vss : list (list val).
Implicit Type status : status.
Class WsDequesPublicG Σ `{zoo۰G : !ZooG Σ} :=
{ #[local] ws_deques_public۰G۰ws_deque۰G :: WsDeque2G Σ
}.
Definition ws_deques_public۰Σ :=
#[ws_deque_2۰Σ
].
#[global] Instance subGｰws_deques_public۰Σ Σ `{zoo۰G : !ZooG Σ} :
subG ws_deques_public۰Σ Σ →
WsDequesPublicG Σ.
Section ws_deques_public۰G.
Context `{ws_deques_public۰G : WsDequesPublicG Σ}.
Definition ws_deques_public۰inv t ι sz : iProp Σ :=
∃ queues,
⌜sz = length queues⌝ ∗
array۰model t DfracDiscarded queues ∗
[∗ list] queue ∈ queues,
ws_deque_2۰inv queue ι.
#[local] Instance : CustomIpat "inv" :=
" ( %queues{} & %Hqueues{}_length & #Hqueues{} & #Hqueues{}_inv ) ".
Definition ws_deques_public۰model t vss : iProp Σ :=
∃ queues,
array۰model t DfracDiscarded queues ∗
[∗ list] i ↦ queue; vs ∈ queues; vss,
ws_deque_2۰model queue vs.
#[local] Instance : CustomIpat "model" :=
" ( %queues{;_} & Hqueues{;_} & Hqueues{}_model ) ".
Definition ws_deques_public۰owner t i status ws : iProp Σ :=
∃ queues queue,
⌜queues !! i = Some queue⌝ ∗
array۰model t DfracDiscarded queues ∗
ws_deque_2۰owner queue ws.
#[local] Instance : CustomIpat "owner" :=
" ( %queues{;_} & %queue{} & %Hqueues{}_lookup & Hqueues{;_} & Hqueue{}_owner ) ".
#[global] Instance ws_deques_public۰modelｰtimeless t vss :
Timeless (ws_deques_public۰model t vss).
#[global] Instance ws_deques_public۰invｰpersistent t ι sz :
Persistent (ws_deques_public۰inv t ι sz).
Lemma ws_deques_public۰invｰagree t ι1 sz1 ι2 sz2 :
ws_deques_public۰inv t ι1 sz1 -∗
ws_deques_public۰inv t ι2 sz2 -∗
⌜sz1 = sz2⌝.
Lemma ws_deques_public۰ownerｰexclusive t i status1 ws1 status2 ws2 :
ws_deques_public۰owner t i status1 ws1 -∗
ws_deques_public۰owner t i status2 ws2 -∗
False.
Lemma ws_deques_publicｰinvｰmodel t ι sz vss :
ws_deques_public۰inv t ι sz -∗
ws_deques_public۰model t vss -∗
⌜length vss = sz⌝.
Lemma ws_deques_publicｰinvｰowner t ι sz i status ws :
ws_deques_public۰inv t ι sz -∗
ws_deques_public۰owner t i status ws -∗
⌜i < sz⌝.
Lemma ws_deques_publicｰmodelｰowner t vss i status ws :
ws_deques_public۰model t vss -∗
ws_deques_public۰owner t i status ws -∗
∃ vs,
⌜vss !! i = Some vs⌝ ∗
⌜vs `suffix_of` ws⌝.
Lemma ws_deques_public٠createｰspec ι sz :
(0 ≤ sz)%Z →
{{{
True
}}}
ws_deques_public٠create #sz
{{{
t
, RET t;
ws_deques_public۰inv t ι ₊sz ∗
ws_deques_public۰model t (replicate ₊sz []) ∗
[∗ list] i ∈ seq 0 ₊sz,
ws_deques_public۰owner t i Nonblocked []
}}}.
Lemma ws_deques_public٠sizeｰspec t ι sz :
{{{
ws_deques_public۰inv t ι sz
}}}
ws_deques_public٠size t
{{{
RET #sz;
True
}}}.
Lemma ws_deques_public٠blockｰspec t ι sz i i_ ws :
i = ⁺i_ →
{{{
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Nonblocked ws
}}}
ws_deques_public٠block t #i
{{{
RET ();
ws_deques_public۰owner t i_ Blocked ws
}}}.
Lemma ws_deques_public٠unblockｰspec t ι sz i i_ ws :
i = ⁺i_ →
{{{
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Blocked ws
}}}
ws_deques_public٠unblock t #i
{{{
RET ();
ws_deques_public۰owner t i_ Nonblocked ws
}}}.
Lemma ws_deques_public٠pushｰspec t ι sz i i_ ws v :
i = ⁺i_ →
<<<
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Nonblocked ws
| ∀∀ vss,
ws_deques_public۰model t vss
>>>
ws_deques_public٠push t #i v @ ↑ι
<<<
∃∃ vs,
⌜vss !! i_ = Some vs⌝ ∗
⌜vs `suffix_of` ws⌝ ∗
ws_deques_public۰model t (<[i_ := vs ++ [v]]> vss)
| RET ();
ws_deques_public۰owner t i_ Nonblocked (vs ++ [v])
>>>.
Lemma ws_deques_public٠popｰspec t ι sz i i_ ws :
i = ⁺i_ →
<<<
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Nonblocked ws
| ∀∀ vss,
ws_deques_public۰model t vss
>>>
ws_deques_public٠pop t #i @ ↑ι
<<<
∃∃ o ws',
match o with
| None ⇒
⌜vss !! i_ = Some []⌝ ∗
⌜ws' = []⌝ ∗
ws_deques_public۰model t vss
| Some v ⇒
∃ vs,
⌜vss !! i_ = Some (vs ++ [v])⌝ ∗
⌜vs ++ [v] `suffix_of` ws⌝ ∗
⌜ws' = vs⌝ ∗
ws_deques_public۰model t (<[i_ := vs]> vss)
end
| RET o;
ws_deques_public۰owner t i_ Nonblocked ws'
>>>.
Lemma ws_deques_public٠steal_toｰspec t ι (sz : nat) i i_ ws j :
i = ⁺i_ →
(0 ≤ j < sz)%Z →
<<<
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Blocked ws
| ∀∀ vss,
ws_deques_public۰model t vss
>>>
ws_deques_public٠steal_to t #i #j @ ↑ι
<<<
∃∃ o,
match o with
| None ⇒
ws_deques_public۰model t vss
| Some v ⇒
∃ vs,
⌜vss !! ₊j = Some (v :: vs)⌝ ∗
ws_deques_public۰model t (<[₊j := vs]> vss)
end
| RET o;
ws_deques_public۰owner t i_ Blocked ws
>>>.
End ws_deques_public۰G.
#[global] Opaque ws_deques_public۰inv.
#[global] Opaque ws_deques_public۰model.
#[global] Opaque ws_deques_public۰owner.
Section ws_deques_public۰G.
Context `{ws_deques_public۰G : WsDequesPublicG Σ}.
#[local] Lemma ws_deques_public٠steal_as₁ｰspec t ι (sz : nat) i i_ ws round (n : nat) :
i = ⁺i_ →
<<<
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Blocked ws ∗
random_round۰model' round (sz - 1) n
| ∀∀ vss,
ws_deques_public۰model t vss
>>>
ws_deques_public٠steal_as₁ t #sz #i round #n @ ↑ι
<<<
∃∃ o,
match o with
| None ⇒
ws_deques_public۰model t vss
| Some v ⇒
∃ j vs,
⌜₊i ≠ j⌝ ∗
⌜vss !! j = Some (v :: vs)⌝ ∗
ws_deques_public۰model t (<[j := vs]> vss)
end
| RET o;
∃ n,
ws_deques_public۰owner t i_ Blocked ws ∗
random_round۰model' round (sz - 1) n
>>>.
Lemma ws_deques_public٠steal_asｰspec t ι sz i i_ ws round :
i = ⁺i_ →
0 < sz →
<<<
ws_deques_public۰inv t ι sz ∗
ws_deques_public۰owner t i_ Blocked ws ∗
random_round۰model' round (sz - 1) (sz - 1)
| ∀∀ vss,
ws_deques_public۰model t vss
>>>
ws_deques_public٠steal_as t #i round @ ↑ι
<<<
∃∃ o,
match o with
| None ⇒
ws_deques_public۰model t vss
| Some v ⇒
∃ j vs,
⌜₊i ≠ j⌝ ∗
⌜vss !! j = Some (v :: vs)⌝ ∗
ws_deques_public۰model t (<[j := vs]> vss)
end
| RET o;
∃ n,
ws_deques_public۰owner t i_ Blocked ws ∗
random_round۰model' round (sz - 1) n
>>>.
End ws_deques_public۰G.
Require zoo_parabs.ws_deques_public__opaque.