one_shot.v 4.18 KB
Newer Older
1 2
From iris.program_logic Require Export weakestpre hoare.
From iris.heap_lang Require Export lang.
Ralf Jung's avatar
Ralf Jung committed
3
From iris.algebra Require Import excl agree csum.
4
From iris.heap_lang Require Import assert proofmode notation.
5
From iris.proofmode Require Import tactics.
6
Set Default Proof Using "Type".
Ralf Jung's avatar
Ralf Jung committed
7 8

Definition one_shot_example : val := λ: <>,
9
  let: "x" := ref NONE in (
Ralf Jung's avatar
Ralf Jung committed
10
  (* tryset *) (λ: "n",
11
    CAS "x" NONE (SOME "n")),
Ralf Jung's avatar
Ralf Jung committed
12
  (* check  *) (λ: <>,
13 14
    let: "y" := !"x" in λ: <>,
    match: "y" with
15 16
      NONE => #()
    | SOME "n" =>
17
       match: !"x" with
18 19
         NONE => assert: #false
       | SOME "m" => assert: "n" = "m"
Ralf Jung's avatar
Ralf Jung committed
20 21 22
       end
    end)).

Ralf Jung's avatar
Ralf Jung committed
23
Definition one_shotR := csumR (exclR unitC) (agreeR ZC).
24
Definition Pending : one_shotR := (Cinl (Excl ()) : one_shotR).
Ralf Jung's avatar
Ralf Jung committed
25
Definition Shot (n : Z) : one_shotR := (Cinr (to_agree n) : one_shotR).
26

27 28 29 30
Class one_shotG Σ := { one_shot_inG :> inG Σ one_shotR }.
Definition one_shotΣ : gFunctors := #[GFunctor (constRF one_shotR)].
Instance subG_one_shotΣ {Σ} : subG one_shotΣ Σ  one_shotG Σ.
Proof. intros [?%subG_inG _]%subG_inv. split; apply _. Qed.
Jacques-Henri Jourdan's avatar
Jacques-Henri Jourdan committed
31

Ralf Jung's avatar
Ralf Jung committed
32
Section proof.
33
Set Default Proof Using "Type*".
34
Context `{!heapG Σ, !one_shotG Σ}.
Ralf Jung's avatar
Ralf Jung committed
35

36
Definition one_shot_inv (γ : gname) (l : loc) : iProp Σ :=
37
  (l  NONEV  own γ Pending   n : Z, l  SOMEV #n  own γ (Shot n))%I.
Ralf Jung's avatar
Ralf Jung committed
38

39
Lemma wp_one_shot (Φ : val  iProp Σ) :
40
  ( f1 f2 : val,
Ralf Jung's avatar
Ralf Jung committed
41
    ( n : Z,  WP f1 #n {{ w, w = #true  w = #false }}) 
42
     WP f2 #() {{ g,  WP g #() {{ _, True }} }} - Φ (f1,f2)%V)
Ralf Jung's avatar
Ralf Jung committed
43 44
   WP one_shot_example #() {{ Φ }}.
Proof.
45
  iIntros "Hf /=". pose proof (nroot .@ "N") as N.
46
  rewrite -wp_fupd /one_shot_example /=. wp_seq. wp_alloc l as "Hl". wp_let.
47 48
  iMod (own_alloc Pending) as (γ) "Hγ"; first done.
  iMod (inv_alloc N _ (one_shot_inv γ l) with "[Hl Hγ]") as "#HN".
Robbert Krebbers's avatar
Robbert Krebbers committed
49
  { iNext. iLeft. by iSplitL "Hl". }
50
  iModIntro. iApply "Hf"; iSplit.
Robbert Krebbers's avatar
Robbert Krebbers committed
51 52
  - iIntros (n) "!#". wp_let.
    iInv N as ">[[Hl Hγ]|H]" "Hclose"; last iDestruct "H" as (m) "[Hl Hγ]".
53
    + wp_cas_suc. iMod (own_update with "Hγ") as "Hγ".
54
      { by apply cmra_update_exclusive with (y:=Shot n). }
55
      iMod ("Hclose" with "[-]"); last eauto.
56
      iNext; iRight; iExists n; by iFrame.
57
    + wp_cas_fail. iMod ("Hclose" with "[-]"); last eauto.
58
      rewrite /one_shot_inv; eauto 10.
59
  - iIntros "!#". wp_seq. wp_bind (! _)%E.
Robbert Krebbers's avatar
Robbert Krebbers committed
60
    iInv N as ">Hγ" "Hclose".
Ralf Jung's avatar
Ralf Jung committed
61 62
    iAssert ( v, l  v  ((v = NONEV  own γ Pending) 
        n : Z, v = SOMEV #n  own γ (Shot n)))%I with "[Hγ]" as "Hv".
63
    { iDestruct "Hγ" as "[[Hl Hγ]|Hl]"; last iDestruct "Hl" as (m) "[Hl Hγ]".
64 65
      + iExists NONEV. iFrame. eauto.
      + iExists (SOMEV #m). iFrame. eauto. }
66
    iDestruct "Hv" as (v) "[Hl Hv]". wp_load.
Ralf Jung's avatar
Ralf Jung committed
67 68
    iAssert (one_shot_inv γ l  (v = NONEV   n : Z,
      v = SOMEV #n  own γ (Shot n)))%I with "[Hl Hv]" as "[Hinv #Hv]".
69
    { iDestruct "Hv" as "[[% ?]|Hv]"; last iDestruct "Hv" as (m) "[% ?]"; subst.
70 71
      + iSplit. iLeft; by iSplitL "Hl". eauto.
      + iSplit. iRight; iExists m; by iSplitL "Hl". eauto. }
72
    iMod ("Hclose" with "[Hinv]") as "_"; eauto; iModIntro.
73
    wp_let. iIntros "!#". wp_seq.
74
    iDestruct "Hv" as "[%|Hv]"; last iDestruct "Hv" as (m) "[% Hγ']"; subst.
75
    { by wp_match. }
76
    wp_match. wp_bind (! _)%E.
Robbert Krebbers's avatar
Robbert Krebbers committed
77
    iInv N as ">[[Hl Hγ]|H]" "Hclose"; last iDestruct "H" as (m') "[Hl Hγ]".
78
    { iCombine "Hγ" "Hγ'" as "Hγ". by iDestruct (own_valid with "Hγ") as %?. }
79
    wp_load.
Robbert Krebbers's avatar
Robbert Krebbers committed
80
    iCombine "Hγ" "Hγ'" as "Hγ".
Ralf Jung's avatar
Ralf Jung committed
81 82
    iDestruct (own_valid with "Hγ") as %?%agree_op_inv%to_agree_inj.
    fold_leibniz. subst. iMod ("Hclose" with "[Hl]") as "_".
83
    { iNext; iRight; by eauto. }
84
    iModIntro. wp_match. iApply wp_assert. wp_op=>?; simplify_eq/=; eauto.
Ralf Jung's avatar
Ralf Jung committed
85 86
Qed.

87
Lemma ht_one_shot (Φ : val  iProp Σ) :
88
  {{ True }} one_shot_example #()
89
    {{ ff,
Ralf Jung's avatar
Ralf Jung committed
90
      ( n : Z, {{ True }} Fst ff #n {{ w, w = #true  w = #false }}) 
91
      {{ True }} Snd ff #() {{ g, {{ True }} g #() {{ _, True }} }}
Ralf Jung's avatar
Ralf Jung committed
92 93
    }}.
Proof.
94
  iIntros "!# _". iApply wp_one_shot. iIntros (f1 f2) "[#Hf1 #Hf2]"; iSplit.
Robbert Krebbers's avatar
Robbert Krebbers committed
95 96
  - iIntros (n) "!# _". wp_proj. iApply "Hf1".
  - iIntros "!# _". wp_proj.
Robbert Krebbers's avatar
Robbert Krebbers committed
97
    iApply (wp_wand with "Hf2"). by iIntros (v) "#? !# _".
Ralf Jung's avatar
Ralf Jung committed
98 99
Qed.
End proof.