spawn.v 3.1 KB
Newer Older
1
From iris.program_logic Require Export weakestpre.
2
From iris.heap_lang Require Export lang.
3
From iris.proofmode Require Import tactics.
Robbert Krebbers's avatar
Robbert Krebbers committed
4
From iris.heap_lang Require Import proofmode notation.
5
From iris.algebra Require Import excl.
Ralf Jung's avatar
Ralf Jung committed
6 7

Definition spawn : val :=
Robbert Krebbers's avatar
Robbert Krebbers committed
8
  λ: "f",
Robbert Krebbers's avatar
Robbert Krebbers committed
9 10
    let: "c" := ref NONE in
    Fork ("c" <- SOME ("f" #())) ;; "c".
Ralf Jung's avatar
Ralf Jung committed
11
Definition join : val :=
Robbert Krebbers's avatar
Robbert Krebbers committed
12
  rec: "join" "c" :=
13
    match: !"c" with
Robbert Krebbers's avatar
Robbert Krebbers committed
14 15
      SOME "x" => "x"
    | NONE => "join" "c"
Robbert Krebbers's avatar
Robbert Krebbers committed
16
    end.
17
Global Opaque spawn join.
Ralf Jung's avatar
Ralf Jung committed
18

19
(** The CMRA & functor we need. *)
Ralf Jung's avatar
Ralf Jung committed
20
(* Not bundling heapG, as it may be shared with other users. *)
21
Class spawnG Σ := SpawnG { spawn_tokG :> inG Σ (exclR unitC) }.
22
Definition spawnΣ : gFunctors := #[GFunctor (constRF (exclR unitC))].
23

24 25
Instance subG_spawnΣ {Σ} : subG spawnΣ Σ  spawnG Σ.
Proof. intros [?%subG_inG _]%subG_inv. split; apply _. Qed.
Ralf Jung's avatar
Ralf Jung committed
26 27 28

(** Now we come to the Iris part of the proof. *)
Section proof.
29
Context `{!heapG Σ, !spawnG Σ} (N : namespace).
Ralf Jung's avatar
Ralf Jung committed
30

31
Definition spawn_inv (γ : gname) (l : loc) (Ψ : val  iProp Σ) : iProp Σ :=
Robbert Krebbers's avatar
Robbert Krebbers committed
32 33
  ( lv, l  lv  (lv = NONEV 
                    v, lv = SOMEV v  (Ψ v  own γ (Excl ()))))%I.
Ralf Jung's avatar
Ralf Jung committed
34

35
Definition join_handle (l : loc) (Ψ : val  iProp Σ) : iProp Σ :=
36 37
  (heapN  N   γ, heap_ctx  own γ (Excl ()) 
                    inv N (spawn_inv γ l Ψ))%I.
Ralf Jung's avatar
Ralf Jung committed
38

Robbert Krebbers's avatar
Robbert Krebbers committed
39 40
Typeclasses Opaque join_handle.

Ralf Jung's avatar
Ralf Jung committed
41 42 43 44 45 46 47 48
Global Instance spawn_inv_ne n γ l :
  Proper (pointwise_relation val (dist n) ==> dist n) (spawn_inv γ l).
Proof. solve_proper. Qed.
Global Instance join_handle_ne n l :
  Proper (pointwise_relation val (dist n) ==> dist n) (join_handle l).
Proof. solve_proper. Qed.

(** The main proofs. *)
49
Lemma spawn_spec (Ψ : val  iProp Σ) e (f : val) :
Ralf Jung's avatar
Ralf Jung committed
50
  to_val e = Some f 
51
  heapN  N 
52
  {{{ heap_ctx  WP f #() {{ Ψ }} }}} spawn e {{{ l, RET #l; join_handle l Ψ }}}.
Ralf Jung's avatar
Ralf Jung committed
53
Proof.
Ralf Jung's avatar
Ralf Jung committed
54
  iIntros (<-%of_to_val ? Φ) "(#Hh & Hf) HΦ". rewrite /spawn /=.
55
  wp_let. wp_alloc l as "Hl". wp_let.
56 57
  iMod (own_alloc (Excl ())) as (γ) "Hγ"; first done.
  iMod (inv_alloc N _ (spawn_inv γ l Ψ) with "[Hl]") as "#?".
Robbert Krebbers's avatar
Robbert Krebbers committed
58
  { iNext. iExists NONEV. iFrame; eauto. }
59
  wp_apply wp_fork; simpl. iSplitR "Hf".
60
  - wp_seq. iApply "HΦ". rewrite /join_handle. eauto.
61
  - wp_bind (f _). iApply (wp_wand_r with "[ $Hf]"); iIntros (v) "Hv".
62 63
    iInv N as (v') "[Hl _]" "Hclose".
    wp_store. iApply "Hclose". iNext. iExists (SOMEV v). iFrame. eauto.
Ralf Jung's avatar
Ralf Jung committed
64 65
Qed.

66
Lemma join_spec (Ψ : val  iProp Σ) l :
67
  {{{ join_handle l Ψ }}} join #l {{{ v, RET v; Ψ v }}}.
Ralf Jung's avatar
Ralf Jung committed
68
Proof.
Ralf Jung's avatar
Ralf Jung committed
69
  rewrite /join_handle; iIntros (Φ) "[% H] HΦ". iDestruct "H" as (γ) "(#?&Hγ&#?)".
70
  iLöb as "IH". wp_rec. wp_bind (! _)%E. iInv N as (v) "[Hl Hinv]" "Hclose".
Robbert Krebbers's avatar
Robbert Krebbers committed
71
  wp_load. iDestruct "Hinv" as "[%|Hinv]"; subst.
72
  - iMod ("Hclose" with "[Hl]"); [iNext; iExists _; iFrame; eauto|].
Ralf Jung's avatar
Ralf Jung committed
73
    iModIntro. wp_match. iApply ("IH" with "Hγ [HΦ]"). auto.
74
  - iDestruct "Hinv" as (v') "[% [HΨ|Hγ']]"; simplify_eq/=.
75
    + iMod ("Hclose" with "[Hl Hγ]"); [iNext; iExists _; iFrame; eauto|].
Ralf Jung's avatar
Ralf Jung committed
76
      iModIntro. wp_match. by iApply "HΦ".
77
    + iCombine "Hγ" "Hγ'" as "Hγ". iDestruct (own_valid with "Hγ") as %[].
Ralf Jung's avatar
Ralf Jung committed
78
Qed.
Ralf Jung's avatar
Ralf Jung committed
79
End proof.
Robbert Krebbers's avatar
Robbert Krebbers committed
80 81

Typeclasses Opaque join_handle.